From ddde360e3e08b0e68635821b347cc0bae23ddb78 Mon Sep 17 00:00:00 2001 From: Ben Gras Date: Fri, 15 Oct 2010 09:10:14 +0000 Subject: [PATCH] vm - hash table for block cache --- servers/vm/exec.c | 3 - servers/vm/exit.c | 1 + servers/vm/fork.c | 1 - servers/vm/main.c | 3 + servers/vm/proto.h | 3 + servers/vm/region.c | 117 ++++++++++++++++++++++++++++------- servers/vm/slaballoc.c | 3 + servers/vm/utility.c | 4 -- servers/vm/vmproc.h | 2 +- servers/vm/yielded.h | 11 +++- servers/vm/yieldedavl_defs.h | 4 +- 11 files changed, 116 insertions(+), 36 deletions(-) diff --git a/servers/vm/exec.c b/servers/vm/exec.c index 049280e76..8d1d5752c 100644 --- a/servers/vm/exec.c +++ b/servers/vm/exec.c @@ -392,8 +392,5 @@ PUBLIC int proc_new(struct vmproc *vmp, panic("exec_newmem: pt_bind failed: %d", s); } - /* No yielded memory blocks. */ - yielded_init(&vmp->vm_yielded_blocks); - return OK; } diff --git a/servers/vm/exit.c b/servers/vm/exit.c index 1c876ed9c..45bc25f39 100644 --- a/servers/vm/exit.c +++ b/servers/vm/exit.c @@ -45,6 +45,7 @@ PUBLIC void clear_proc(struct vmproc *vmp) vmp->vm_callback = NULL; /* No pending vfs callback. */ vmp->vm_flags = 0; /* Clear INUSE, so slot is free. */ vmp->vm_heap = NULL; + vmp->vm_yielded = 0; #if VMSTATS vmp->vm_bytecopies = 0; #endif diff --git a/servers/vm/fork.c b/servers/vm/fork.c index 289a296a1..e2b690f6f 100644 --- a/servers/vm/fork.c +++ b/servers/vm/fork.c @@ -70,7 +70,6 @@ PUBLIC int do_fork(message *msg) *vmc = *vmp; vmc->vm_slot = childproc; region_init(&vmc->vm_regions_avl); - yielded_init(&vmc->vm_yielded_blocks); vmc->vm_endpoint = NONE; /* In case someone tries to use it. */ vmc->vm_pt = origpt; vmc->vm_flags &= ~VMF_HASPT; diff --git a/servers/vm/main.c b/servers/vm/main.c index 0ee74440a..c17cde965 100644 --- a/servers/vm/main.c +++ b/servers/vm/main.c @@ -255,6 +255,9 @@ PRIVATE int sef_cb_init_fresh(int type, sef_init_info_t *info) vmp->vm_flags |= VMF_SEPARATE; } + /* region management initialization. */ + map_region_init(); + /* Architecture-dependent initialization. */ pt_init(limit); diff --git a/servers/vm/proto.h b/servers/vm/proto.h index 98ffd6e5b..4651afd80 100644 --- a/servers/vm/proto.h +++ b/servers/vm/proto.h @@ -16,6 +16,7 @@ struct phys_region; #include #include "vm.h" +#include "yielded.h" /* alloc.c */ _PROTOTYPE( phys_clicks alloc_mem, (phys_clicks clicks, u32_t flags) ); @@ -137,6 +138,7 @@ _PROTOTYPE(int slabsane_f,(char *file, int line, void *mem, int bytes)); #endif /* region.c */ +_PROTOTYPE(void map_region_init, (void)); _PROTOTYPE(struct vir_region * map_page_region,(struct vmproc *vmp, \ vir_bytes min, vir_bytes max, vir_bytes length, vir_bytes what, \ u32_t flags, int mapflags)); @@ -159,6 +161,7 @@ _PROTOTYPE(int map_writept, (struct vmproc *vmp)); _PROTOTYPE(void printregionstats, (struct vmproc *vmp)); _PROTOTYPE(phys_bytes map_lookup_phys, (struct vmproc *vmp, u32_t tag)); _PROTOTYPE(void map_setparent, (struct vmproc *vmp)); +_PROTOTYPE(int yielded_block_cmp, (struct block_id *, struct block_id *)); _PROTOTYPE(struct vir_region * map_region_lookup_tag, (struct vmproc *vmp, u32_t tag)); _PROTOTYPE(void map_region_set_tag, (struct vir_region *vr, u32_t tag)); diff --git a/servers/vm/region.c b/servers/vm/region.c index 1f33982b8..89af5afca 100644 --- a/servers/vm/region.c +++ b/servers/vm/region.c @@ -10,6 +10,7 @@ #include #include #include +#include #include @@ -56,6 +57,36 @@ FORWARD _PROTOTYPE(struct phys_region *map_clone_ph_block, (struct vmproc *vmp, FORWARD _PROTOTYPE(void lrucheck, (void)); #endif +/* hash table of yielded blocks */ +#define YIELD_HASHSIZE 65536 +PRIVATE yielded_avl vm_yielded_blocks[YIELD_HASHSIZE]; + +PRIVATE int avl_inited = 0; + +PUBLIC void map_region_init(void) +{ + int h; + assert(!avl_inited); + for(h = 0; h < YIELD_HASHSIZE; h++) + yielded_init(&vm_yielded_blocks[h]); + avl_inited = 1; +} + +PRIVATE yielded_avl *get_yielded_avl(block_id_t id) +{ + u32_t h; + + assert(avl_inited); + + hash_i_64(id.owner, id.id, h); + h = h % YIELD_HASHSIZE; + + assert(h >= 0); + assert(h < YIELD_HASHSIZE); + + return &vm_yielded_blocks[h]; +} + PRIVATE char *map_name(struct vir_region *vr) { static char name[100]; @@ -435,9 +466,6 @@ PRIVATE vir_bytes region_find_slot_range(struct vmproc *vmp, nextvr = region_get_iter(&iter); FREEVRANGE(vr->vaddr + vr->length, nextvr ? nextvr->vaddr : VM_DATATOP); - if(!foundflag) { - printf("incr from 0x%lx to 0x%lx; v range 0x%lx-0x%lx\n", vr->vaddr, nextvr->vaddr); - } } } @@ -721,27 +749,52 @@ PRIVATE int map_free(struct vmproc *vmp, struct vir_region *region) return OK; } +/*===========================================================================* + * yielded_block_cmp * + *===========================================================================*/ +PUBLIC int yielded_block_cmp(struct block_id *id1, struct block_id *id2) +{ + if(id1->owner < id2->owner) + return -1; + if(id1->owner > id2->owner) + return 1; + return cmp64(id1->id, id2->id); +} + /*===========================================================================* * free_yielded_proc * *===========================================================================*/ PRIVATE vir_bytes free_yielded_proc(struct vmproc *vmp) { - yielded_t *yb; - int y = 0; vir_bytes total = 0; + int h; SANITYCHECK(SCL_FUNCTIONS); /* Free associated regions. */ - while((yb = yielded_search_root(&vmp->vm_yielded_blocks))) { - SLABSANE(yb); - total += freeyieldednode(yb, 1); - y++; + for(h = 0; h < YIELD_HASHSIZE && vmp->vm_yielded > 0; h++) { + yielded_t *yb; + yielded_iter iter; + yielded_avl *avl = &vm_yielded_blocks[h]; + yielded_start_iter_least(avl, &iter); + while((yb = yielded_get_iter(&iter))) { + yielded_t *next_yb; + SLABSANE(yb); + yielded_incr_iter(&iter); + if(yb->id.owner != vmp->vm_endpoint) + continue; + next_yb = yielded_get_iter(&iter); + total += freeyieldednode(yb, 1); + /* the above removal invalidated our iter; restart it + * for the node we want to start at. + */ + if(!next_yb) break; + yielded_start_iter(avl, &iter, next_yb->id, AVL_EQUAL); + assert(yielded_get_iter(&iter) == next_yb); + } } - yielded_init(&vmp->vm_yielded_blocks); - return total; } @@ -749,8 +802,9 @@ PRIVATE vir_bytes free_yielded_proc(struct vmproc *vmp) PRIVATE phys_bytes freeyieldednode(yielded_t *node, int freemem) { yielded_t *older, *younger, *removed; - int p; vir_bytes len; + yielded_avl *avl; + int p; SLABSANE(node); @@ -783,11 +837,13 @@ PRIVATE phys_bytes freeyieldednode(yielded_t *node, int freemem) /* Update AVL. */ - if(vm_isokendpt(node->owner, &p) != OK) - panic("out of date owner of yielded block %d", node->owner); - - removed = yielded_remove(&vmproc[p].vm_yielded_blocks, node->id); + if(vm_isokendpt(node->id.owner, &p) != OK) + panic("out of date owner of yielded block %d", node->id.owner); + avl = get_yielded_avl(node->id); + removed = yielded_remove(avl, node->id); assert(removed == node); + assert(vmproc[p].vm_yielded > 0); + vmproc[p].vm_yielded--; /* Free associated memory if requested. */ @@ -1199,7 +1255,6 @@ PUBLIC int map_pin_memory(struct vmproc *vmp) } region_incr_iter(&iter); } - return OK; } @@ -2388,9 +2443,14 @@ PRIVATE int getblock(struct vmproc *vmp, u64_t id, yielded_t *yb; struct phys_region *ph; struct vir_region *region; + yielded_avl *avl; + block_id_t blockid; /* Try to get the yielded block */ - if(!(yb = yielded_search(&vmp->vm_yielded_blocks, id, AVL_EQUAL))) { + blockid.owner = vmp->vm_endpoint; + blockid.id = id; + avl = get_yielded_avl(blockid); + if(!(yb = yielded_search(avl, blockid, AVL_EQUAL))) { return ESRCH; } @@ -2434,11 +2494,16 @@ PRIVATE int yieldblock(struct vmproc *vmp, u64_t id, vir_bytes mem_clicks, newmem, clicks; struct vir_region *region; struct phys_region *ph; + yielded_avl *avl; + block_id_t blockid; /* Makes no sense if yielded block ID already exists, and * is likely a serious bug in the caller. */ - if(yielded_search(&vmp->vm_yielded_blocks, id, AVL_EQUAL)) { + blockid.id = id; + blockid.owner = vmp->vm_endpoint; + avl = get_yielded_avl(blockid); + if(yielded_search(avl, blockid, AVL_EQUAL)) { printf("!"); return EINVAL; } @@ -2465,10 +2530,9 @@ PRIVATE int yieldblock(struct vmproc *vmp, u64_t id, /* Update yielded block info. */ USE(newyb, - newyb->id = id; + newyb->id = blockid; newyb->addr = ph->ph->phys; newyb->len = ph->ph->length; - newyb->owner = vmp->vm_endpoint; newyb->younger = NULL;); /* Set new phys block to new addr and update pagetable. */ @@ -2482,7 +2546,9 @@ PRIVATE int yieldblock(struct vmproc *vmp, u64_t id, } /* Remember yielded block. */ - yielded_insert(&vmp->vm_yielded_blocks, newyb); + + yielded_insert(avl, newyb); + vmp->vm_yielded++; /* Add to LRU list too. It's the youngest block. */ LRUCHECK; @@ -2542,6 +2608,8 @@ PUBLIC int do_forgetblock(message *m) endpoint_t caller = m->m_source; yielded_t *yb; u64_t id; + block_id_t blockid; + yielded_avl *avl; if(vm_isokendpt(caller, &n) != OK) panic("do_yield_block: message from strange source: %d", @@ -2556,7 +2624,10 @@ PUBLIC int do_forgetblock(message *m) id = make64(m->VMFB_IDLO, m->VMFB_IDHI); - if((yb = yielded_search(&vmp->vm_yielded_blocks, id, AVL_EQUAL))) { + blockid.id = id; + blockid.owner = vmp->vm_endpoint; + avl = get_yielded_avl(blockid); + if((yb = yielded_search(avl, blockid, AVL_EQUAL))) { freeyieldednode(yb, 1); } diff --git a/servers/vm/slaballoc.c b/servers/vm/slaballoc.c index a937c9db4..cf2a51c9d 100644 --- a/servers/vm/slaballoc.c +++ b/servers/vm/slaballoc.c @@ -467,6 +467,9 @@ PUBLIC void slabfree(void *mem, int bytes) #if SANITYCHECKS #if MEMPROTECT slabunlock(mem, bytes); +#endif +#if JUNKFREE + memset(mem, 0xa6, bytes); #endif *(u32_t *) mem = JUNK; nojunkwarning++; diff --git a/servers/vm/utility.c b/servers/vm/utility.c index 126c8f7d8..b25395bac 100644 --- a/servers/vm/utility.c +++ b/servers/vm/utility.c @@ -274,10 +274,6 @@ PUBLIC int swap_proc_slot(struct vmproc *src_vmp, struct vmproc *dst_vmp) dst_vmp->vm_endpoint = orig_dst_vmproc.vm_endpoint; dst_vmp->vm_slot = orig_dst_vmproc.vm_slot; - /* Preserve yielded blocks. */ - src_vmp->vm_yielded_blocks = orig_src_vmproc.vm_yielded_blocks; - dst_vmp->vm_yielded_blocks = orig_dst_vmproc.vm_yielded_blocks; - #if LU_DEBUG printf("VM: swap_proc: swapped %d (%d) and %d (%d)\n", src_vmp->vm_endpoint, src_vmp->vm_slot, diff --git a/servers/vm/vmproc.h b/servers/vm/vmproc.h index 2f67db371..0b7956bb7 100644 --- a/servers/vm/vmproc.h +++ b/servers/vm/vmproc.h @@ -32,7 +32,6 @@ struct vmproc { /* Regions in virtual address space. */ region_avl vm_regions_avl; vir_bytes vm_region_top; /* highest vaddr last inserted */ - yielded_avl vm_yielded_blocks; /* avl of yielded physblocks */ /* Heap for brk() to extend. */ struct vir_region *vm_heap; @@ -46,6 +45,7 @@ struct vmproc { int vm_callback_type; /* expected message type */ int vm_slot; /* process table slot */ + int vm_yielded; /* yielded regions */ union { struct { diff --git a/servers/vm/yielded.h b/servers/vm/yielded.h index 4df164779..a4f86c8a1 100644 --- a/servers/vm/yielded.h +++ b/servers/vm/yielded.h @@ -4,10 +4,17 @@ #include -typedef struct yielded { +typedef struct block_id { u64_t id; - phys_bytes addr, len; endpoint_t owner; +} block_id_t; + +typedef struct yielded { + /* the owner-given id and owner together + * uniquely identify a yielded block. + */ + block_id_t id; + phys_bytes addr, len; /* LRU fields */ struct yielded *younger, *older; diff --git a/servers/vm/yieldedavl_defs.h b/servers/vm/yieldedavl_defs.h index e7233f806..43eda779d 100644 --- a/servers/vm/yieldedavl_defs.h +++ b/servers/vm/yieldedavl_defs.h @@ -2,7 +2,7 @@ #define AVL_UNIQUE(id) yielded_ ## id #define AVL_HANDLE yielded_t * -#define AVL_KEY u64_t +#define AVL_KEY block_id_t #define AVL_MAX_DEPTH 30 /* good for 2 million nodes */ #define AVL_NULL NULL #define AVL_GET_LESS(h, a) (h)->less @@ -12,7 +12,7 @@ #define AVL_GET_BALANCE_FACTOR(h) (h)->factor #define AVL_SET_BALANCE_FACTOR(h, f) USE((h), (h)->factor = f;); #define AVL_SET_ROOT(h, v) (h)->root = v; -#define AVL_COMPARE_KEY_KEY(k1, k2) cmp64((k1), (k2)) +#define AVL_COMPARE_KEY_KEY(k1, k2) yielded_block_cmp(&(k1), &(k2)) #define AVL_COMPARE_KEY_NODE(k, h) AVL_COMPARE_KEY_KEY((k), (h)->id) #define AVL_COMPARE_NODE_NODE(h1, h2) AVL_COMPARE_KEY_KEY((h1)->id, (h2)->id) #define AVL_INSIDE_STRUCT char pad[4]; -- 2.44.0