#include <stddef.h>
#include <kern/btlog.h>
#include <kern/assert.h>
#include <vm/vm_kern.h>
#include <vm/vm_map.h>
#include <mach/vm_param.h>
typedef uint32_t btlog_recordindex_t;
#define BTLOG_RECORDINDEX_NONE (0xFFFFFF)
#define BTLOG_MAX_RECORDS (0xFFFFFF )
typedef struct btlog_record {
btlog_recordindex_t next:24;
uint8_t operation;
#if __LP64__
uint32_t _pad;
#endif
void *element;
void *bt[];
} btlog_record_t;
struct btlog {
vm_address_t btlog_buffer;
vm_size_t btlog_buffersize;
btlog_lock_t lock_callback;
btlog_unlock_t unlock_callback;
void *callback_context;
uintptr_t btrecords;
size_t btrecord_count;
size_t btrecord_btdepth;
size_t btrecord_size;
btlog_recordindex_t head;
btlog_recordindex_t tail;
size_t activecount;
btlog_recordindex_t freelist;
};
extern boolean_t kmem_alloc_ready;
#define lookup_btrecord(btlog, index) \
((btlog_record_t *)(btlog->btrecords + index * btlog->btrecord_size))
btlog_t *
btlog_create(size_t numrecords,
size_t record_btdepth,
btlog_lock_t lock_callback,
btlog_unlock_t unlock_callback,
void *callback_context)
{
btlog_t *btlog;
vm_size_t buffersize_needed;
vm_address_t buffer = 0;
size_t i;
kern_return_t ret;
size_t btrecord_size;
if (!kmem_alloc_ready)
return NULL;
if (numrecords > BTLOG_MAX_RECORDS)
return NULL;
if (numrecords == 0)
return NULL;
if (record_btdepth > BTLOG_MAX_DEPTH)
return NULL;
if ((lock_callback && !unlock_callback) ||
(!lock_callback && unlock_callback))
return NULL;
btrecord_size = sizeof(btlog_record_t)
+ sizeof(void *) * record_btdepth;
buffersize_needed = sizeof(btlog_t) + numrecords * btrecord_size;
buffersize_needed = round_page(buffersize_needed);
numrecords = MIN(BTLOG_MAX_RECORDS,
(buffersize_needed - sizeof(btlog_t))/btrecord_size);
ret = kmem_alloc(kernel_map, &buffer, buffersize_needed);
if (ret != KERN_SUCCESS)
return NULL;
btlog = (btlog_t *)buffer;
btlog->btlog_buffer = buffer;
btlog->btlog_buffersize = buffersize_needed;
btlog->lock_callback = lock_callback;
btlog->unlock_callback = unlock_callback;
btlog->callback_context = callback_context;
btlog->btrecords = (uintptr_t)(buffer + sizeof(btlog_t));
btlog->btrecord_count = numrecords;
btlog->btrecord_btdepth = record_btdepth;
btlog->btrecord_size = btrecord_size;
btlog->head = BTLOG_RECORDINDEX_NONE;
btlog->tail = BTLOG_RECORDINDEX_NONE;
btlog->activecount = 0;
btlog->freelist = 0;
for (i=0; i < (numrecords - 1); i++) {
btlog_record_t *rec = lookup_btrecord(btlog, i);
rec->next = (btlog_recordindex_t)(i + 1);
}
lookup_btrecord(btlog, i)->next = BTLOG_RECORDINDEX_NONE;
return btlog;
}
static btlog_recordindex_t
btlog_get_record_from_freelist(btlog_t *btlog)
{
btlog_recordindex_t recindex = btlog->freelist;
if (recindex == BTLOG_RECORDINDEX_NONE) {
return BTLOG_RECORDINDEX_NONE;
} else {
btlog_record_t *record = lookup_btrecord(btlog, recindex);
btlog->freelist = record->next;
return recindex;
}
}
static btlog_recordindex_t
btlog_evict_record_from_activelist(btlog_t *btlog)
{
btlog_recordindex_t recindex = btlog->head;
if (recindex == BTLOG_RECORDINDEX_NONE) {
return BTLOG_RECORDINDEX_NONE;
} else {
btlog_record_t *record = lookup_btrecord(btlog, recindex);
btlog->head = record->next;
btlog->activecount--;
if (btlog->head == BTLOG_RECORDINDEX_NONE) {
btlog->tail = BTLOG_RECORDINDEX_NONE;
}
return recindex;
}
}
static void
btlog_append_record_to_activelist(btlog_t *btlog, btlog_recordindex_t recindex)
{
if (btlog->head == BTLOG_RECORDINDEX_NONE) {
btlog->head = btlog->tail = recindex;
} else {
btlog_record_t *record = lookup_btrecord(btlog, btlog->tail);
record->next = recindex;
btlog->tail = recindex;
}
btlog->activecount++;
}
void
btlog_add_entry(btlog_t *btlog,
void *element,
uint8_t operation,
void *bt[],
size_t btcount)
{
btlog_recordindex_t recindex;
btlog_record_t *record;
size_t i;
if (btlog->lock_callback)
btlog->lock_callback(btlog->callback_context);
recindex = btlog_get_record_from_freelist(btlog);
if (recindex == BTLOG_RECORDINDEX_NONE) {
recindex = btlog_evict_record_from_activelist(btlog);
assert(recindex != BTLOG_RECORDINDEX_NONE);
}
record = lookup_btrecord(btlog, recindex);
record->next = BTLOG_RECORDINDEX_NONE;
record->operation = operation;
record->element = element;
for (i=0; i < MIN(btcount, btlog->btrecord_btdepth); i++) {
record->bt[i] = bt[i];
}
for (; i < btlog->btrecord_btdepth; i++) {
record->bt[i] = NULL;
}
btlog_append_record_to_activelist(btlog, recindex);
if (btlog->unlock_callback)
btlog->unlock_callback(btlog->callback_context);
}
void
btlog_remove_entries_for_element(btlog_t *btlog,
void *element)
{
btlog_recordindex_t recindex;
btlog_record_t *record;
if (btlog->lock_callback)
btlog->lock_callback(btlog->callback_context);
recindex = btlog->head;
record = lookup_btrecord(btlog, recindex);
while (recindex != BTLOG_RECORDINDEX_NONE) {
if (record->element == element) {
btlog->head = record->next;
btlog->activecount--;
record->next = btlog->freelist;
btlog->freelist = recindex;
recindex = btlog->head;
record = lookup_btrecord(btlog, recindex);
} else {
break;
}
}
if (recindex == BTLOG_RECORDINDEX_NONE) {
btlog->tail = BTLOG_RECORDINDEX_NONE;
} else {
btlog_recordindex_t precindex = recindex;
btlog_record_t *precord = record;
recindex = precord->next;
record = lookup_btrecord(btlog, recindex);
while (recindex != BTLOG_RECORDINDEX_NONE) {
if (record->element == element) {
precord->next = record->next;
btlog->activecount--;
record->next = btlog->freelist;
btlog->freelist = recindex;
recindex = precord->next;
record = lookup_btrecord(btlog, recindex);
} else {
precindex = recindex;
precord = record;
recindex = record->next;
record = lookup_btrecord(btlog, recindex);
}
}
btlog->tail = precindex;
}
if (btlog->unlock_callback)
btlog->unlock_callback(btlog->callback_context);
}