Changes in kernel/genarch/src/mm/page_ht.c [82cbf8c6:fb63c06] in mainline

File:

• kernel/genarch/src/mm/page_ht.c (modified) (10 diffs)

kernel/genarch/src/mm/page_ht.c

@@ -48 +48 @@
 #include <synch/spinlock.h>
 #include <arch.h>
-#include <assert.h>
-#include <adt/hash.h>
+#include <debug.h>
+#include <memstr.h>
 #include <adt/hash_table.h>
 #include <align.h>
 
-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 size_t hash(sysarg_t[]);
+static bool compare(sysarg_t[], size_t, link_t *);
+static void remove_callback(link_t *);
 
 static void ht_mapping_insert(as_t *, uintptr_t, uintptr_t, unsigned int);
@@ -82 +81 @@
 
 /** Hash table operations for page hash table. */
-hash_table_ops_t ht_ops = {
-        .hash = ht_hash,
-        .key_hash = ht_key_hash,
-        .key_equal = ht_key_equal,
-        .remove_callback = ht_remove_callback
+hash_table_operations_t ht_operations = {
+        .hash = hash,
+        .compare = compare,
+        .remove_callback = remove_callback
 };
 
@@ -98 +96 @@
 };
 
-/** 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);
+/** 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)
+{
+        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);
 }
 
@@ -132 +160 @@
  *
  */
-void ht_remove_callback(ht_link_t *item)
-{
-        assert(item);
-        
-        pte_t *pte = hash_table_get_inst(item, pte_t, link);
+void remove_callback(link_t *item)
+{
+        ASSERT(item);
+        
+        /*
+         * Convert item to PTE.
+         *
+         */
+        pte_t *pte = hash_table_get_instance(item, pte_t, link);
+        
         slab_free(pte_cache, pte);
 }
@@ -154 +187 @@
     unsigned int flags)
 {
-        uintptr_t key[2] = {
-                [KEY_AS] = (uintptr_t) as,
-                [KEY_PAGE] = ALIGN_DOWN(page, PAGE_SIZE)
+        sysarg_t key[2] = {
+                (uintptr_t) as,
+                page = ALIGN_DOWN(page, PAGE_SIZE)
         };
 
-        assert(page_table_locked(as));
+        ASSERT(page_table_locked(as));
 
         irq_spinlock_lock(&page_ht_lock, true);
@@ -165 +198 @@
         if (!hash_table_find(&page_ht, key)) {
                 pte_t *pte = slab_alloc(pte_cache, FRAME_LOWMEM | FRAME_ATOMIC);
-                assert(pte != NULL);
+                ASSERT(pte != NULL);
                 
                 pte->g = (flags & PAGE_GLOBAL) != 0;
@@ -186 +219 @@
                 write_barrier();
                 
-                hash_table_insert(&page_ht, &pte->link);
+                hash_table_insert(&page_ht, key, &pte->link);
         }
 
@@ -204 +237 @@
 void ht_mapping_remove(as_t *as, uintptr_t page)
 {
-        uintptr_t key[2] = {
-                [KEY_AS] = (uintptr_t) as,
-                [KEY_PAGE] = ALIGN_DOWN(page, PAGE_SIZE)
+        sysarg_t key[2] = {
+                (uintptr_t) as,
+                page = ALIGN_DOWN(page, PAGE_SIZE)
         };
 
-        assert(page_table_locked(as));
+        ASSERT(page_table_locked(as));
         
         irq_spinlock_lock(&page_ht_lock, true);
@@ -217 +250 @@
          * by remove_callback().
          */
-        hash_table_remove(&page_ht, key);
+        hash_table_remove(&page_ht, key, 2);
 
         irq_spinlock_unlock(&page_ht_lock, true);
 }
 
-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)
+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)
         };
 
-        assert(nolock || page_table_locked(as));
-
-        ht_link_t *cur = hash_table_find(&page_ht, key);
+        ASSERT(nolock || page_table_locked(as));
+
+        link_t *cur = hash_table_find(&page_ht, key);
         if (cur)
-                return hash_table_get_inst(cur, pte_t, link);
+                return hash_table_get_instance(cur, pte_t, link);
         
         return NULL;
@@ -276 +308 @@
                 panic("Updating non-existent PTE");
         
-        assert(pte->as == t->as);
-        assert(pte->page == t->page);
-        assert(pte->frame == t->frame);
-        assert(pte->g == t->g);
-        assert(pte->x == t->x);
-        assert(pte->w == t->w);
-        assert(pte->k == t->k);
-        assert(pte->c == t->c);
-        assert(pte->p == t->p);
+        ASSERT(pte->as == t->as);
+        ASSERT(pte->page == t->page);
+        ASSERT(pte->frame == t->frame);
+        ASSERT(pte->g == t->g);
+        ASSERT(pte->x == t->x);
+        ASSERT(pte->w == t->w);
+        ASSERT(pte->k == t->k);
+        ASSERT(pte->c == t->c);
+        ASSERT(pte->p == t->p);
 
         t->a = pte->a;