osfmk/kern/btlog.c

   1 /*
   2  * Copyright (c) 2012 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #include <stddef.h>
  30 #include <kern/btlog.h>
  31 #include <kern/assert.h>
  32 #include <vm/vm_kern.h>
  33 #include <vm/vm_map.h>
  34 #include <vm/pmap.h>
  35 #include <mach/vm_param.h>
  36
  37 /*
  38  * Since all records are located contiguously in memory,
  39  * we use indices to them as the primary lookup mechanism,
  40  * and to maintain the linked list of active records
  41  * in chronological order.
  42  */
  43 typedef uint32_t btlog_recordindex_t; /* only 24 bits used */
  44 #define BTLOG_RECORDINDEX_NONE (0xFFFFFF)
  45 #define BTLOG_MAX_RECORDS (0xFFFFFF /* 16777215 */)
  46
  47 typedef struct btlog_record {
  48     btlog_recordindex_t next:24;
  49     uint8_t         operation;
  50 #if __LP64__
  51     uint32_t        _pad;
  52 #endif
  53     void           *element;
  54     void           *bt[]; /* variable sized, based on btlog_t params */
  55 } btlog_record_t;
  56
  57 struct btlog {
  58     vm_address_t    btlog_buffer;       /* all memory for this btlog_t */
  59     vm_size_t       btlog_buffersize;
  60
  61     btlog_lock_t    lock_callback;      /* caller-provided locking */
  62     btlog_unlock_t  unlock_callback;
  63     void           *callback_context;
  64
  65     uintptr_t       btrecords;      /* use btlog_recordindex_t to lookup */
  66     size_t          btrecord_count;
  67     size_t          btrecord_btdepth; /* BT entries per record */
  68     size_t          btrecord_size;
  69
  70     btlog_recordindex_t head; /* active record list */
  71     btlog_recordindex_t tail;
  72     size_t          activecount;
  73
  74     btlog_recordindex_t freelist;
  75 };
  76
  77 extern boolean_t vm_kernel_ready;
  78 extern boolean_t kmem_alloc_ready;
  79
  80 #define lookup_btrecord(btlog, index) \
  81         ((btlog_record_t *)(btlog->btrecords + index * btlog->btrecord_size))
  82
  83 btlog_t *
  84 btlog_create(size_t numrecords,
  85                          size_t record_btdepth,
  86                          btlog_lock_t lock_callback,
  87                          btlog_unlock_t unlock_callback,
  88                          void *callback_context)
  89 {
  90         btlog_t *btlog;
  91         vm_size_t buffersize_needed;
  92         vm_address_t buffer = 0;
  93         size_t i;
  94         kern_return_t ret;
  95         size_t btrecord_size;
  96
  97         if (vm_kernel_ready && !kmem_alloc_ready)
  98                 return NULL;
  99
 100         if (numrecords > BTLOG_MAX_RECORDS)
 101                 return NULL;
 102
 103         if (numrecords == 0)
 104                 return NULL;
 105
 106         if (record_btdepth > BTLOG_MAX_DEPTH)
 107                 return NULL;
 108
 109         if ((lock_callback && !unlock_callback) ||
 110                 (!lock_callback && unlock_callback))
 111                 return NULL;
 112
 113         /* btlog_record_t is variable-sized, calculate needs now */
 114         btrecord_size = sizeof(btlog_record_t)
 115                 + sizeof(void *) * record_btdepth;
 116
 117         buffersize_needed = sizeof(btlog_t) + numrecords * btrecord_size;
 118         buffersize_needed = round_page(buffersize_needed);
 119
 120         /* since rounding to a page size might hold more, recalculate */
 121         numrecords = MIN(BTLOG_MAX_RECORDS,
 122                                          (buffersize_needed - sizeof(btlog_t))/btrecord_size);
 123
 124         if (kmem_alloc_ready) {
 125                 ret = kmem_alloc(kernel_map, &buffer, buffersize_needed, VM_KERN_MEMORY_DIAG);
 126         } else {
 127                 buffer = (vm_address_t)pmap_steal_memory(buffersize_needed);
 128                 ret = KERN_SUCCESS;
 129         }
 130         if (ret != KERN_SUCCESS)
 131                 return NULL;
 132
 133         btlog = (btlog_t *)buffer;
 134         btlog->btlog_buffer = buffer;
 135         btlog->btlog_buffersize = buffersize_needed;
 136
 137         btlog->lock_callback = lock_callback;
 138         btlog->unlock_callback = unlock_callback;
 139         btlog->callback_context = callback_context;
 140
 141         btlog->btrecords = (uintptr_t)(buffer + sizeof(btlog_t));
 142         btlog->btrecord_count = numrecords;
 143         btlog->btrecord_btdepth = record_btdepth;
 144         btlog->btrecord_size = btrecord_size;
 145
 146         btlog->head = BTLOG_RECORDINDEX_NONE;
 147         btlog->tail = BTLOG_RECORDINDEX_NONE;
 148         btlog->activecount = 0;
 149
 150         /* populate freelist with all records in order */
 151         btlog->freelist = 0;
 152         for (i=0; i < (numrecords - 1); i++) {
 153                 btlog_record_t *rec = lookup_btrecord(btlog, i);
 154                 rec->next = (btlog_recordindex_t)(i + 1);
 155         }
 156         lookup_btrecord(btlog, i)->next = BTLOG_RECORDINDEX_NONE; /* terminate */
 157
 158         return btlog;
 159 }
 160
 161 /* Assumes btlog is already locked */
 162 static btlog_recordindex_t
 163 btlog_get_record_from_freelist(btlog_t *btlog)
 164 {
 165         btlog_recordindex_t     recindex = btlog->freelist;
 166
 167         if (recindex == BTLOG_RECORDINDEX_NONE) {
 168                 /* nothing on freelist */
 169                 return BTLOG_RECORDINDEX_NONE;
 170         } else {
 171                 /* remove the head of the freelist */
 172                 btlog_record_t *record = lookup_btrecord(btlog, recindex);
 173                 btlog->freelist = record->next;
 174                 return recindex;
 175         }
 176 }
 177
 178 /* Assumes btlog is already locked */
 179 static btlog_recordindex_t
 180 btlog_evict_record_from_activelist(btlog_t *btlog)
 181 {
 182         btlog_recordindex_t     recindex = btlog->head;
 183
 184         if (recindex == BTLOG_RECORDINDEX_NONE) {
 185                 /* nothing on active list */
 186                 return BTLOG_RECORDINDEX_NONE;
 187         } else {
 188                 /* remove the head of the active list */
 189                 btlog_record_t *record = lookup_btrecord(btlog, recindex);
 190                 btlog->head = record->next;
 191                 btlog->activecount--;
 192                 if (btlog->head == BTLOG_RECORDINDEX_NONE) {
 193                         /* active list is now empty, update tail */
 194                         btlog->tail = BTLOG_RECORDINDEX_NONE;
 195                 }
 196                 return recindex;
 197         }
 198 }
 199
 200 /* Assumes btlog is already locked */
 201 static void
 202 btlog_append_record_to_activelist(btlog_t *btlog, btlog_recordindex_t recindex)
 203 {
 204         if (btlog->head == BTLOG_RECORDINDEX_NONE) {
 205                 /* empty active list, update both head and tail */
 206                 btlog->head = btlog->tail = recindex;
 207         } else {
 208                 btlog_record_t *record = lookup_btrecord(btlog, btlog->tail);
 209                 record->next = recindex;
 210                 btlog->tail = recindex;
 211         }
 212         btlog->activecount++;
 213 }
 214
 215 void
 216 btlog_add_entry(btlog_t *btlog,
 217                                 void *element,
 218                                 uint8_t operation,
 219                                 void *bt[],
 220                                 size_t btcount)
 221 {
 222         btlog_recordindex_t recindex;
 223         btlog_record_t *record;
 224         size_t i;
 225
 226         if (btlog->lock_callback)
 227                 btlog->lock_callback(btlog->callback_context);
 228
 229         /* If there's a free record, use it */
 230         recindex = btlog_get_record_from_freelist(btlog);
 231         if (recindex == BTLOG_RECORDINDEX_NONE) {
 232                 /* Use the first active record (FIFO age-out) */
 233                 recindex = btlog_evict_record_from_activelist(btlog);
 234                 assert(recindex != BTLOG_RECORDINDEX_NONE);
 235         }
 236
 237         record = lookup_btrecord(btlog, recindex);
 238
 239         /* we always add to the tail, so there is no next pointer */
 240         record->next = BTLOG_RECORDINDEX_NONE;
 241         record->operation = operation;
 242         record->element = element;
 243         for (i=0; i < MIN(btcount, btlog->btrecord_btdepth); i++) {
 244                 record->bt[i] = bt[i];
 245         }
 246         for (; i < btlog->btrecord_btdepth; i++) {
 247                 record->bt[i] = NULL;
 248         }
 249
 250         btlog_append_record_to_activelist(btlog, recindex);
 251
 252         if (btlog->unlock_callback)
 253                 btlog->unlock_callback(btlog->callback_context);
 254 }
 255
 256 void
 257 btlog_remove_entries_for_element(btlog_t *btlog,
 258                                                                  void *element)
 259 {
 260         btlog_recordindex_t recindex;
 261         btlog_record_t *record;
 262
 263         if (btlog->lock_callback)
 264                 btlog->lock_callback(btlog->callback_context);
 265
 266         /*
 267          * Since the btlog_t anchors the active
 268          * list with a pointer to the head of
 269          * the list, first loop making sure
 270          * the head is correct (and doesn't
 271          * match the element being removed).
 272          */
 273         recindex = btlog->head;
 274         record = lookup_btrecord(btlog, recindex);
 275         while (recindex != BTLOG_RECORDINDEX_NONE) {
 276                 if (record->element == element) {
 277                         /* remove head of active list */
 278                         btlog->head = record->next;
 279                         btlog->activecount--;
 280
 281                         /* add to freelist */
 282                         record->next = btlog->freelist;
 283                         btlog->freelist = recindex;
 284
 285                         /* check the new head */
 286                         recindex = btlog->head;
 287                         record = lookup_btrecord(btlog, recindex);
 288                 } else {
 289                         /* head didn't match, so we can move on */
 290                         break;
 291                 }
 292         }
 293
 294         if (recindex == BTLOG_RECORDINDEX_NONE) {
 295                 /* we iterated over the entire active list removing the element */
 296                 btlog->tail = BTLOG_RECORDINDEX_NONE;
 297         } else {
 298                 /* the head of the active list is stable, now remove other entries */
 299                 btlog_recordindex_t precindex = recindex;
 300                 btlog_record_t *precord = record;
 301
 302                 recindex = precord->next;
 303                 record = lookup_btrecord(btlog, recindex);
 304                 while (recindex != BTLOG_RECORDINDEX_NONE) {
 305                         if (record->element == element) {
 306                                 /* remove in place */
 307                                 precord->next = record->next;
 308                                 btlog->activecount--;
 309
 310                                 /* add to freelist */
 311                                 record->next = btlog->freelist;
 312                                 btlog->freelist = recindex;
 313
 314                                 /* check the next record */
 315                                 recindex = precord->next;
 316                                 record = lookup_btrecord(btlog, recindex);
 317                         } else {
 318                                 /* check the next record */
 319                                 precindex = recindex;
 320                                 precord = record;
 321
 322                                 recindex = record->next;
 323                                 record = lookup_btrecord(btlog, recindex);
 324                         }
 325                 }
 326
 327                 /* We got to the end of the active list. Update the tail */
 328                 btlog->tail = precindex;
 329         }
 330
 331         if (btlog->unlock_callback)
 332                 btlog->unlock_callback(btlog->callback_context);
 333
 334 }