#include <vm/vm_map_store_rb.h>
RB_GENERATE(rb_head, vm_map_store, entry, rb_node_compare);
#define VME_FOR_STORE( store) \
(vm_map_entry_t)(((unsigned long)store) - ((unsigned long)sizeof(struct vm_map_links)))
void
vm_map_store_init_rb( struct vm_map_header* hdr )
{
RB_INIT(&(hdr->rb_head_store));
}
int rb_node_compare(struct vm_map_store *node, struct vm_map_store *parent)
{
vm_map_entry_t vme_c;
vm_map_entry_t vme_p;
vme_c = VME_FOR_STORE(node);
vme_p = VME_FOR_STORE(parent);
if (vme_c->vme_start < vme_p->vme_start)
return -1;
if (vme_c->vme_start >= vme_p->vme_end)
return 1;
return 0;
}
void vm_map_store_walk_rb( vm_map_t map, vm_map_entry_t *wrong_vme, vm_map_entry_t *vm_entry)
{
struct vm_map_header hdr = map->hdr;
struct vm_map_store *rb_entry = RB_ROOT(&(hdr.rb_head_store));
vm_map_entry_t cur = *vm_entry;
rb_entry = RB_FIND( rb_head, &(hdr.rb_head_store), &(cur->store));
if(rb_entry == NULL)
panic("NO SUCH ENTRY %p. Gave back %p", *vm_entry, *wrong_vme);
else
panic("Cur: %p, L: %p, R: %p", VME_FOR_STORE(rb_entry), VME_FOR_STORE(RB_LEFT(rb_entry,entry)), VME_FOR_STORE(RB_RIGHT(rb_entry,entry)));
}
boolean_t vm_map_store_lookup_entry_rb( vm_map_t map, vm_map_offset_t address, vm_map_entry_t *vm_entry)
{
struct vm_map_header hdr = map->hdr;
struct vm_map_store *rb_entry = RB_ROOT(&(hdr.rb_head_store));
vm_map_entry_t cur = vm_map_to_entry(map);
vm_map_entry_t prev = VM_MAP_ENTRY_NULL;
while (rb_entry != (struct vm_map_store*)NULL) {
cur = VME_FOR_STORE(rb_entry);
if(cur == VM_MAP_ENTRY_NULL)
panic("no entry");
if (address >= cur->vme_start) {
if (address < cur->vme_end) {
*vm_entry = cur;
return TRUE;
}
rb_entry = RB_RIGHT(rb_entry, entry);
prev = cur;
} else {
rb_entry = RB_LEFT(rb_entry, entry);
}
}
if( prev == VM_MAP_ENTRY_NULL){
prev = vm_map_to_entry(map);
}
*vm_entry = prev;
return FALSE;
}
void vm_map_store_entry_link_rb( struct vm_map_header *mapHdr, __unused vm_map_entry_t after_where, vm_map_entry_t entry)
{
struct rb_head *rbh = &(mapHdr->rb_head_store);
struct vm_map_store *store = &(entry->store);
struct vm_map_store *tmp_store;
if((tmp_store = RB_INSERT( rb_head, rbh, store )) != NULL) {
panic("VMSEL: INSERT FAILED: 0x%lx, 0x%lx, 0x%lx, 0x%lx", (uintptr_t)entry->vme_start, (uintptr_t)entry->vme_end,
(uintptr_t)(VME_FOR_STORE(tmp_store))->vme_start, (uintptr_t)(VME_FOR_STORE(tmp_store))->vme_end);
}
}
void vm_map_store_entry_unlink_rb( struct vm_map_header *mapHdr, vm_map_entry_t entry)
{
struct rb_head *rbh = &(mapHdr->rb_head_store);
struct vm_map_store *rb_entry;
struct vm_map_store *store = &(entry->store);
rb_entry = RB_FIND( rb_head, rbh, store);
if(rb_entry == NULL)
panic("NO ENTRY TO DELETE");
RB_REMOVE( rb_head, rbh, store );
}
void vm_map_store_copy_insert_rb( vm_map_t map, __unused vm_map_entry_t after_where, vm_map_copy_t copy)
{
struct vm_map_header *mapHdr = &(map->hdr);
struct rb_head *rbh = &(mapHdr->rb_head_store);
struct vm_map_store *store;
vm_map_entry_t entry = vm_map_copy_first_entry(copy);
int inserted=0, nentries = copy->cpy_hdr.nentries;
while (entry != vm_map_copy_to_entry(copy) && nentries > 0) {
vm_map_entry_t prev = entry;
store = &(entry->store);
if( RB_INSERT( rb_head, rbh, store ) != NULL){
panic("VMSCIR1: INSERT FAILED: %d: %p, %p, %p, 0x%lx, 0x%lx, 0x%lx, 0x%lx, 0x%lx, 0x%lx",inserted, prev, entry, vm_map_copy_to_entry(copy),
(uintptr_t)prev->vme_start, (uintptr_t)prev->vme_end, (uintptr_t)entry->vme_start, (uintptr_t)entry->vme_end,
(uintptr_t)(VME_FOR_STORE(rbh->rbh_root))->vme_start, (uintptr_t)(VME_FOR_STORE(rbh->rbh_root))->vme_end);
} else {
#if MAP_ENTRY_INSERTION_DEBUG
fastbacktrace(&entry->vme_insertion_bt[0],
(sizeof (entry->vme_insertion_bt) / sizeof (uintptr_t)));
#endif
entry = entry->vme_next;
inserted++;
nentries--;
}
}
}
void
vm_map_store_copy_reset_rb( vm_map_copy_t copy, vm_map_entry_t entry, int nentries )
{
struct vm_map_header *mapHdr = &(copy->cpy_hdr);
struct rb_head *rbh = &(mapHdr->rb_head_store);
struct vm_map_store *store;
int deleted=0;
while (entry != vm_map_copy_to_entry(copy) && nentries > 0) {
store = &(entry->store);
RB_REMOVE( rb_head, rbh, store );
entry = entry->vme_next;
deleted++;
nentries--;
}
}
void update_first_free_rb( __unused vm_map_t map, __unused vm_map_entry_t entry)
{
return ;
}