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 */ 43typedef uint32_t btlog_recordindex_t; /* only 24 bits used */ 44#define BTLOG_RECORDINDEX_NONE (0xFFFFFF) 45#define BTLOG_MAX_RECORDS (0xFFFFFF /* 16777215 */) 46 47typedef 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 57struct 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 77extern boolean_t vm_kernel_ready; 78extern boolean_t kmem_alloc_ready; 79 80#define lookup_btrecord(btlog, index) \ 81 ((btlog_record_t *)(btlog->btrecords + index * btlog->btrecord_size)) 82 83btlog_t * 84btlog_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); 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 */ 162static btlog_recordindex_t 163btlog_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 */ 179static btlog_recordindex_t 180btlog_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 */ 201static void 202btlog_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 215void 216btlog_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 256void 257btlog_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} 335