Index: kernel/genarch/include/genarch/mm/as_ht.h =================================================================== --- kernel/genarch/include/genarch/mm/as_ht.h (revision 24abb85d299db39cc03f429adc41bb1ed4f23e23) +++ kernel/genarch/include/genarch/mm/as_ht.h (revision 84a1a546f62a2ba0f913f8f1bfce8d4bc68d7aa4) @@ -37,5 +37,5 @@ #include -#include +#include #include @@ -46,5 +46,5 @@ typedef struct pte { - link_t link; /**< Page hash table link. */ + ht_link_t link; /**< Page hash table link. */ struct as *as; /**< Address space. */ uintptr_t page; /**< Virtual memory page. */ Index: kernel/genarch/include/genarch/mm/page_ht.h =================================================================== --- kernel/genarch/include/genarch/mm/page_ht.h (revision 24abb85d299db39cc03f429adc41bb1ed4f23e23) +++ kernel/genarch/include/genarch/mm/page_ht.h (revision 84a1a546f62a2ba0f913f8f1bfce8d4bc68d7aa4) @@ -46,10 +46,6 @@ #include -#define PAGE_HT_KEYS 2 #define KEY_AS 0 #define KEY_PAGE 1 - -#define PAGE_HT_ENTRIES_BITS 13 -#define PAGE_HT_ENTRIES (1 << PAGE_HT_ENTRIES_BITS) /* Macros for querying page hash table PTEs. */ @@ -66,5 +62,5 @@ extern slab_cache_t *pte_cache; extern hash_table_t page_ht; -extern hash_table_operations_t ht_operations; +extern hash_table_ops_t ht_ops; #endif Index: kernel/genarch/src/mm/as_ht.c =================================================================== --- kernel/genarch/src/mm/as_ht.c (revision 24abb85d299db39cc03f429adc41bb1ed4f23e23) +++ kernel/genarch/src/mm/as_ht.c (revision 84a1a546f62a2ba0f913f8f1bfce8d4bc68d7aa4) @@ -75,5 +75,5 @@ { if (flags & FLAG_AS_KERNEL) { - hash_table_create(&page_ht, PAGE_HT_ENTRIES, 2, &ht_operations); + hash_table_create(&page_ht, 0, 0, &ht_ops); pte_cache = slab_cache_create("pte_t", sizeof(pte_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); Index: kernel/genarch/src/mm/page_ht.c =================================================================== --- kernel/genarch/src/mm/page_ht.c (revision 24abb85d299db39cc03f429adc41bb1ed4f23e23) +++ kernel/genarch/src/mm/page_ht.c (revision 84a1a546f62a2ba0f913f8f1bfce8d4bc68d7aa4) @@ -49,10 +49,12 @@ #include #include +#include #include #include -static size_t hash(sysarg_t[]); -static bool compare(sysarg_t[], size_t, link_t *); -static void remove_callback(link_t *); +static size_t ht_hash(const ht_link_t *); +static size_t ht_key_hash(void *); +static bool ht_key_equal(void *, const ht_link_t *); +static void ht_remove_callback(ht_link_t *); static void ht_mapping_insert(as_t *, uintptr_t, uintptr_t, unsigned int); @@ -80,8 +82,9 @@ /** Hash table operations for page hash table. */ -hash_table_operations_t ht_operations = { - .hash = hash, - .compare = compare, - .remove_callback = remove_callback +hash_table_ops_t ht_ops = { + .hash = ht_hash, + .key_hash = ht_key_hash, + .key_equal = ht_key_equal, + .remove_callback = ht_remove_callback }; @@ -95,78 +98,43 @@ }; -/** Compute page hash table index. - * - * @param key Array of two keys (i.e. page and address space). - * - * @return Index into page hash table. - * - */ -size_t hash(sysarg_t key[]) -{ - as_t *as = (as_t *) key[KEY_AS]; - uintptr_t page = (uintptr_t) key[KEY_PAGE]; - - /* - * Virtual page addresses have roughly the same probability - * of occurring. Least significant bits of VPN compose the - * hash index. - * - */ - size_t index = ((page >> PAGE_WIDTH) & (PAGE_HT_ENTRIES - 1)); - - /* - * Address space structures are likely to be allocated from - * similar addresses. Least significant bits compose the - * hash index. - * - */ - index |= ((sysarg_t) as) & (PAGE_HT_ENTRIES - 1); - - return index; -} - -/** Compare page hash table item with page and/or address space. - * - * @param key Array of one or two keys (i.e. page and/or address space). - * @param keys Number of keys passed. - * @param item Item to compare the keys with. - * - * @return true on match, false otherwise. - * - */ -bool compare(sysarg_t key[], size_t keys, link_t *item) +/** Return the hash of the key stored in the item */ +size_t ht_hash(const ht_link_t *item) +{ + pte_t *pte = hash_table_get_inst(item, pte_t, link); + size_t hash = 0; + hash = hash_combine(hash, (uintptr_t) pte->as); + hash = hash_combine(hash, pte->page >> PAGE_WIDTH); + return hash; +} + +/** Return the hash of the key. */ +size_t ht_key_hash(void *arg) +{ + uintptr_t *key = (uintptr_t *) arg; + size_t hash = 0; + hash = hash_combine(hash, key[KEY_AS]); + hash = hash_combine(hash, key[KEY_PAGE] >> PAGE_WIDTH); + return hash; +} + +/** Return true if the key is equal to the item's lookup key. */ +bool ht_key_equal(void *arg, const ht_link_t *item) +{ + uintptr_t *key = (uintptr_t *) arg; + pte_t *pte = hash_table_get_inst(item, pte_t, link); + return (key[KEY_AS] == (uintptr_t) pte->as) && + (key[KEY_PAGE] == pte->page); +} + +/** Callback on page hash table item removal. + * + * @param item Page hash table item being removed. + * + */ +void ht_remove_callback(ht_link_t *item) { assert(item); - assert(keys > 0); - assert(keys <= PAGE_HT_KEYS); - - /* - * Convert item to PTE. - * - */ - pte_t *pte = hash_table_get_instance(item, pte_t, link); - - if (keys == PAGE_HT_KEYS) - return (key[KEY_AS] == (uintptr_t) pte->as) && - (key[KEY_PAGE] == pte->page); - - return (key[KEY_AS] == (uintptr_t) pte->as); -} - -/** Callback on page hash table item removal. - * - * @param item Page hash table item being removed. - * - */ -void remove_callback(link_t *item) -{ - assert(item); - - /* - * Convert item to PTE. - * - */ - pte_t *pte = hash_table_get_instance(item, pte_t, link); - + + pte_t *pte = hash_table_get_inst(item, pte_t, link); slab_free(pte_cache, pte); } @@ -186,7 +154,7 @@ unsigned int flags) { - sysarg_t key[2] = { - (uintptr_t) as, - page = ALIGN_DOWN(page, PAGE_SIZE) + uintptr_t key[2] = { + [KEY_AS] = (uintptr_t) as, + [KEY_PAGE] = ALIGN_DOWN(page, PAGE_SIZE) }; @@ -218,5 +186,5 @@ write_barrier(); - hash_table_insert(&page_ht, key, &pte->link); + hash_table_insert(&page_ht, &pte->link); } @@ -236,7 +204,7 @@ void ht_mapping_remove(as_t *as, uintptr_t page) { - sysarg_t key[2] = { - (uintptr_t) as, - page = ALIGN_DOWN(page, PAGE_SIZE) + uintptr_t key[2] = { + [KEY_AS] = (uintptr_t) as, + [KEY_PAGE] = ALIGN_DOWN(page, PAGE_SIZE) }; @@ -249,21 +217,22 @@ * by remove_callback(). */ - hash_table_remove(&page_ht, key, 2); + hash_table_remove(&page_ht, key); irq_spinlock_unlock(&page_ht_lock, true); } -static pte_t *ht_mapping_find_internal(as_t *as, uintptr_t page, bool nolock) -{ - sysarg_t key[2] = { - (uintptr_t) as, - page = ALIGN_DOWN(page, PAGE_SIZE) +static pte_t * +ht_mapping_find_internal(as_t *as, uintptr_t page, bool nolock) +{ + uintptr_t key[2] = { + [KEY_AS] = (uintptr_t) as, + [KEY_PAGE] = ALIGN_DOWN(page, PAGE_SIZE) }; assert(nolock || page_table_locked(as)); - link_t *cur = hash_table_find(&page_ht, key); + ht_link_t *cur = hash_table_find(&page_ht, key); if (cur) - return hash_table_get_instance(cur, pte_t, link); + return hash_table_get_inst(cur, pte_t, link); return NULL;