#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--;
}
}
extern zone_t vm_map_holes_zone;
void
vm_map_combine_hole(vm_map_t map, vm_map_entry_t hole_entry);
void
vm_map_combine_hole(__unused vm_map_t map, vm_map_entry_t hole_entry)
{
vm_map_entry_t middle_hole_entry, last_hole_entry;
hole_entry->vme_end = hole_entry->vme_next->vme_end;
middle_hole_entry = hole_entry->vme_next;
last_hole_entry = middle_hole_entry->vme_next;
assert(last_hole_entry->vme_prev == middle_hole_entry);
assert(middle_hole_entry->vme_end != last_hole_entry->vme_start);
last_hole_entry->vme_prev = hole_entry;
hole_entry->vme_next = last_hole_entry;
middle_hole_entry->vme_prev = NULL;
middle_hole_entry->vme_next = NULL;
zfree(vm_map_holes_zone, middle_hole_entry);
assert(hole_entry->vme_start < hole_entry->vme_end);
assert(last_hole_entry->vme_start < last_hole_entry->vme_end);
}
void
vm_map_delete_hole(vm_map_t map, vm_map_entry_t hole_entry);
void
vm_map_delete_hole(vm_map_t map, vm_map_entry_t hole_entry)
{
if (hole_entry == (vm_map_entry_t) map->holes_list) {
if (hole_entry->vme_next == (vm_map_entry_t) map->holes_list) {
map->holes_list = NULL;
SAVE_HINT_HOLE_WRITE(map, NULL);
} else {
vm_map_entry_t l_next, l_prev;
l_next = (vm_map_entry_t) map->holes_list->next;
l_prev = (vm_map_entry_t) map->holes_list->prev;
map->holes_list = (struct vm_map_links*) l_next;
l_next->vme_prev = l_prev;
l_prev->vme_next = l_next;
SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) l_next);
}
} else {
SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry->vme_prev);
hole_entry->vme_prev->vme_next = hole_entry->vme_next;
hole_entry->vme_next->vme_prev = hole_entry->vme_prev;
}
hole_entry->vme_next = NULL;
hole_entry->vme_prev = NULL;
zfree(vm_map_holes_zone, hole_entry);
}
#if DEBUG
static void
check_map_sanity(vm_map_t map, vm_map_entry_t old_hole_entry)
{
vm_map_entry_t hole_entry, next_hole_entry;
vm_map_entry_t map_entry, next_map_entry;
if (map->holes_list == NULL) {
return;
}
hole_entry = (vm_map_entry_t) map->holes_list;
next_hole_entry = hole_entry->vme_next;
map_entry = vm_map_first_entry(map);
next_map_entry = map_entry->vme_next;
while(map_entry->vme_start > hole_entry->vme_start) {
hole_entry = next_hole_entry;
next_hole_entry = hole_entry->vme_next;
if (hole_entry == (vm_map_entry_t)map->holes_list)
break;
}
while (map_entry != vm_map_to_entry(map)) {
if (map_entry->vme_start >= map->max_offset)
break;
if (map_entry->vme_end != map_entry->vme_next->vme_start) {
if (map_entry->vme_next == vm_map_to_entry(map))
break;
if (hole_entry->vme_start != map_entry->vme_end) {
panic("hole_entry not aligned %p(0x%llx), %p (0x%llx), %p", hole_entry, (unsigned long long)hole_entry->vme_start, map_entry->vme_next, (unsigned long long)map_entry->vme_end, old_hole_entry);
assert(hole_entry->vme_start == map_entry->vme_end);
}
if (hole_entry->vme_end != map_entry->vme_next->vme_start) {
panic("hole_entry not next aligned %p(0x%llx), %p (0x%llx), %p", hole_entry, (unsigned long long)hole_entry->vme_end, map_entry->vme_next, (unsigned long long)map_entry->vme_next->vme_start, old_hole_entry);
assert(hole_entry->vme_end == map_entry->vme_next->vme_start);
}
hole_entry = next_hole_entry;
next_hole_entry = hole_entry->vme_next;
if (hole_entry == (vm_map_entry_t)map->holes_list)
break;
}
map_entry = map_entry->vme_next;
}
}
static void
copy_hole_info(vm_map_entry_t hole_entry, vm_map_entry_t old_hole_entry)
{
old_hole_entry->vme_prev = hole_entry->vme_prev;
old_hole_entry->vme_next = hole_entry->vme_next;
old_hole_entry->vme_start = hole_entry->vme_start;
old_hole_entry->vme_end = hole_entry->vme_end;
}
#endif
void
update_holes_on_entry_deletion(vm_map_t map, vm_map_entry_t old_entry);
void
update_holes_on_entry_deletion(vm_map_t map, vm_map_entry_t old_entry)
{
vm_map_entry_t hole_entry, next_hole_entry;
#if DEBUG
struct vm_map_entry old_hole_entry;
#endif
boolean_t create_new_hole = TRUE;
hole_entry = (vm_map_entry_t) map->hole_hint;
if (hole_entry) {
if (hole_entry->vme_end == old_entry->vme_start) {
} else if (hole_entry->vme_start == old_entry->vme_end) {
if (hole_entry != (vm_map_entry_t) map->holes_list) {
hole_entry = hole_entry->vme_prev;
}
} else if (hole_entry->vme_start > old_entry->vme_end) {
hole_entry = (vm_map_entry_t) map->holes_list;
}
if (hole_entry != (vm_map_entry_t) map->holes_list) {
if (hole_entry->vme_start > old_entry->vme_start) {
panic("Hole hint failed: Hole entry start: 0x%llx, entry start: 0x%llx, map hole start: 0x%llx, map hint start: 0x%llx\n",
(unsigned long long)hole_entry->vme_start,
(unsigned long long)old_entry->vme_start,
(unsigned long long)map->holes_list->start,
(unsigned long long)map->hole_hint->start);
}
if (hole_entry->vme_end > old_entry->vme_start) {
panic("Hole hint failed: Hole entry end: 0x%llx, entry start: 0x%llx, map hole start: 0x%llx, map hint start: 0x%llx\n",
(unsigned long long)hole_entry->vme_end,
(unsigned long long)old_entry->vme_start,
(unsigned long long)map->holes_list->start,
(unsigned long long)map->hole_hint->start);
}
}
while (1) {
next_hole_entry = hole_entry->vme_next;
if (hole_entry->vme_end == old_entry->vme_start) {
#if DEBUG
copy_hole_info(hole_entry, &old_hole_entry);
#endif
if (old_entry->vme_end == hole_entry->vme_next->vme_start) {
vm_map_combine_hole(map, hole_entry);
} else {
hole_entry->vme_end = old_entry->vme_end;
}
create_new_hole = FALSE;
#if DEBUG
check_map_sanity(map, &old_hole_entry);
#endif
break;
}
if (hole_entry->vme_start == old_entry->vme_end) {
#if DEBUG
copy_hole_info(hole_entry, &old_hole_entry);
#endif
hole_entry->vme_start = old_entry->vme_start;
create_new_hole = FALSE;
#if DEBUG
check_map_sanity(map, &old_hole_entry);
#endif
break;
}
if (hole_entry->vme_start > old_entry->vme_end) {
#if DEBUG
copy_hole_info(hole_entry, &old_hole_entry);
#endif
if (hole_entry != (vm_map_entry_t) map->holes_list) {
assert(hole_entry->vme_start != old_entry->vme_start);
hole_entry = hole_entry->vme_prev;
}
break;
}
hole_entry = next_hole_entry;
if (hole_entry == (vm_map_entry_t)map->holes_list) {
hole_entry = hole_entry->vme_prev;
break;
}
}
}
if (create_new_hole) {
struct vm_map_links *new_hole_entry = NULL;
vm_map_entry_t l_next, l_prev;
new_hole_entry = zalloc(vm_map_holes_zone);
if (map->holes_list == NULL || (hole_entry == (vm_map_entry_t) map->holes_list && hole_entry->vme_start > old_entry->vme_start)) {
if (map->holes_list == NULL) {
map->holes_list = new_hole_entry;
new_hole_entry->prev = new_hole_entry->next = (vm_map_entry_t)map->holes_list;
} else {
l_next = (vm_map_entry_t) map->holes_list;
l_prev = map->holes_list->prev;
map->holes_list = new_hole_entry;
new_hole_entry->next = l_next;
new_hole_entry->prev = l_prev;
l_prev->vme_next = l_next->vme_prev = (vm_map_entry_t) new_hole_entry;
}
} else {
l_next = hole_entry->vme_next;
l_prev = hole_entry->vme_next->vme_prev;
new_hole_entry->prev = hole_entry;
new_hole_entry->next = l_next;
hole_entry->vme_next = (vm_map_entry_t)new_hole_entry;
l_next->vme_prev = (vm_map_entry_t) new_hole_entry;
}
new_hole_entry->start = old_entry->vme_start;
new_hole_entry->end = old_entry->vme_end;
hole_entry = (vm_map_entry_t) new_hole_entry;
assert(new_hole_entry->start < new_hole_entry->end);
}
#if DEBUG
check_map_sanity(map, &old_hole_entry);
#endif
SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry);
return;
}
void
update_holes_on_entry_creation(vm_map_t map, vm_map_entry_t new_entry);
void
update_holes_on_entry_creation(vm_map_t map, vm_map_entry_t new_entry)
{
vm_map_entry_t hole_entry, next_hole_entry;
#if DEBUG
struct vm_map_entry old_hole_entry;
vm_map_entry_t tmp_entry;
boolean_t check_map_with_hole_sanity = TRUE;
#endif
hole_entry = (vm_map_entry_t) map->holes_list;
assert(hole_entry);
next_hole_entry = hole_entry->vme_next;
while (1) {
#if DEBUG
check_map_with_hole_sanity = vm_map_lookup_entry(map, new_entry->vme_start, &tmp_entry);
#endif
if (hole_entry->vme_start == new_entry->vme_start &&
hole_entry->vme_end == new_entry->vme_end) {
#if DEBUG
copy_hole_info(hole_entry, &old_hole_entry);
#endif
if (hole_entry == (vm_map_entry_t) map->holes_list) {
if (hole_entry->vme_next == (vm_map_entry_t) map->holes_list) {
next_hole_entry = vm_map_last_entry(map);
assert(next_hole_entry->vme_end >= map->max_offset);
}
}
vm_map_delete_hole(map, hole_entry);
#if DEBUG
if (check_map_with_hole_sanity)
check_map_sanity(map, &old_hole_entry);
#endif
return;
} else if (hole_entry->vme_start < new_entry->vme_start &&
hole_entry->vme_end > new_entry->vme_end) {
struct vm_map_links *new_hole_entry = NULL;
new_hole_entry = zalloc(vm_map_holes_zone);
#if DEBUG
copy_hole_info(hole_entry, &old_hole_entry);
#endif
new_hole_entry->prev = hole_entry;
new_hole_entry->next = hole_entry->vme_next;
hole_entry->vme_next->vme_prev = (vm_map_entry_t)new_hole_entry;
hole_entry->vme_next = (vm_map_entry_t)new_hole_entry;
new_hole_entry->start = new_entry->vme_end;
new_hole_entry->end = hole_entry->vme_end;
hole_entry->vme_end = new_entry->vme_start;
assert(hole_entry->vme_start < hole_entry->vme_end);
assert(new_hole_entry->start < new_hole_entry->end);
#if DEBUG
if (check_map_with_hole_sanity)
check_map_sanity(map, &old_hole_entry);
#endif
SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry);
return;
} else if ((new_entry->vme_start <= hole_entry->vme_start) && (hole_entry->vme_start < new_entry->vme_end)) {
#if DEBUG
copy_hole_info(hole_entry, &old_hole_entry);
#endif
if (hole_entry->vme_end <= new_entry->vme_end) {
vm_map_delete_hole(map, hole_entry);
} else {
hole_entry->vme_start = new_entry->vme_end;
SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry);
}
#if DEBUG
if (check_map_with_hole_sanity)
check_map_sanity(map, &old_hole_entry);
#endif
return;
} else if ((new_entry->vme_start < hole_entry->vme_end) && (hole_entry->vme_end <= new_entry->vme_end)) {
#if DEBUG
copy_hole_info(hole_entry, &old_hole_entry);
#endif
if (hole_entry->vme_start >= new_entry->vme_start) {
vm_map_delete_hole(map, hole_entry);
} else {
hole_entry->vme_end = new_entry->vme_start;
SAVE_HINT_HOLE_WRITE(map, (struct vm_map_links*) hole_entry);
}
#if DEBUG
if (check_map_with_hole_sanity)
check_map_sanity(map, &old_hole_entry);
#endif
return;
}
hole_entry = next_hole_entry;
next_hole_entry = hole_entry->vme_next;
if (hole_entry == (vm_map_entry_t)map->holes_list)
break;
}
panic("Illegal action: h1: %p, s:0x%llx, e:0x%llx...h2:%p, s:0x%llx, e:0x%llx...h3:0x%p, s:0x%llx, e:0x%llx\n",
hole_entry->vme_prev,
(unsigned long long)hole_entry->vme_prev->vme_start,
(unsigned long long)hole_entry->vme_prev->vme_end,
hole_entry,
(unsigned long long)hole_entry->vme_start,
(unsigned long long)hole_entry->vme_end,
hole_entry->vme_next,
(unsigned long long)hole_entry->vme_next->vme_start,
(unsigned long long)hole_entry->vme_next->vme_end);
}
void
update_first_free_rb(vm_map_t map, vm_map_entry_t entry, boolean_t new_entry_creation)
{
if (map->holelistenabled) {
vm_map_offset_t max_valid_offset = (map->max_offset > MACH_VM_MAX_ADDRESS) ? map->max_offset : MACH_VM_MAX_ADDRESS;
if (entry == NULL) {
return;
}
if (vm_map_trunc_page(entry->vme_start, VM_MAP_PAGE_MASK(map)) >= max_valid_offset) {
return;
}
if (new_entry_creation) {
update_holes_on_entry_creation(map, entry);
} else {
update_holes_on_entry_deletion(map, entry);
}
}
}