Changeset 82cbf8c6 in mainline for kernel/generic/src/synch/futex.c

Timestamp:

2017-10-08T19:37:24Z (8 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

2fd26bb

Parents:

81b9d3e

Message:

Replace the old hash table implementation in the kernel with the newer one

This replaces the original hash table implementation with the resizable one
already used in uspace. Along the way, the IRQ hash table code was streamlined
and cleaned up.

File:

• kernel/generic/src/synch/futex.c (modified) (10 diffs)

kernel/generic/src/synch/futex.c

@@ -74 +74 @@
 #include <genarch/mm/page_ht.h>
 #include <adt/cht.h>
+#include <adt/hash.h>
 #include <adt/hash_table.h>
 #include <adt/list.h>
@@ -80 +81 @@
 #include <panic.h>
 #include <errno.h>
-
-#define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
 
 /** Task specific pointer to a global kernel futex object. */
@@ -108 +107 @@
 static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr);
 
-static size_t futex_ht_hash(sysarg_t *key);
-static bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item);
-static void futex_ht_remove_callback(link_t *item);
+static size_t futex_ht_hash(const ht_link_t *item);
+static size_t futex_ht_key_hash(void *key);
+static bool futex_ht_key_equal(void *key, const ht_link_t *item);
+static void futex_ht_remove_callback(ht_link_t *item);
 
 static size_t task_fut_ht_hash(const cht_link_t *link);
@@ -131 +131 @@
 
 /** Global kernel futex hash table operations. */
-static hash_table_operations_t futex_ht_ops = {
+static hash_table_ops_t futex_ht_ops = {
         .hash = futex_ht_hash,
-        .compare = futex_ht_compare,
+        .key_hash = futex_ht_key_hash,
+        .key_equal = futex_ht_key_equal,
         .remove_callback = futex_ht_remove_callback
 };
@@ -149 +150 @@
 void futex_init(void)
 {
-        hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
+        hash_table_create(&futex_ht, 0, 0, &futex_ht_ops);
 }
 
@@ -234 +235 @@
 {
         waitq_initialize(&futex->wq);
-        link_initialize(&futex->ht_link);
         futex->paddr = paddr;
         futex->refcount = 1;
@@ -256 +256 @@
         
         if (0 == futex->refcount) {
-                hash_table_remove(&futex_ht, &futex->paddr, 1);
+                hash_table_remove(&futex_ht, &futex->paddr);
         }
 }
@@ -347 +347 @@
         spinlock_lock(&futex_ht_lock);
         
-        link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
+        ht_link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
         
         if (fut_link) {
@@ -355 +355 @@
         } else {
                 futex_initialize(futex, phys_addr);
-                hash_table_insert(&futex_ht, &phys_addr, &futex->ht_link);
+                hash_table_insert(&futex_ht, &futex->ht_link);
         }
         
@@ -437 +437 @@
 
 
-/** Compute hash index into futex hash table.
- *
- * @param key           Address where the key (i.e. physical address of futex
- *                      counter) is stored.
- *
- * @return              Index into futex hash table.
- */
-size_t futex_ht_hash(sysarg_t *key)
-{
-        return (*key & (FUTEX_HT_SIZE - 1));
-}
-
-/** Compare futex hash table item with a key.
- *
- * @param key           Address where the key (i.e. physical address of futex
- *                      counter) is stored.
- *
- * @return              True if the item matches the key. False otherwise.
- */
-bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item)
+/** Return the hash of the key stored in the item */
+size_t futex_ht_hash(const ht_link_t *item)
+{
+        futex_t *futex = hash_table_get_inst(item, futex_t, ht_link);
+        return hash_mix(futex->paddr);
+}
+
+/** Return the hash of the key */
+size_t futex_ht_key_hash(void *key)
+{
+        uintptr_t *paddr = (uintptr_t *) key;
+        return hash_mix(*paddr);
+}
+
+/** Return true if the key is equal to the item's lookup key. */
+bool futex_ht_key_equal(void *key, const ht_link_t *item)
+{
+        uintptr_t *paddr = (uintptr_t *) key;
+        futex_t *futex = hash_table_get_inst(item, futex_t, ht_link);
+        return *paddr == futex->paddr;
+}
+
+/** Callback for removal items from futex hash table.
+ *
+ * @param item          Item removed from the hash table.
+ */
+void futex_ht_remove_callback(ht_link_t *item)
 {
         futex_t *futex;
 
-        assert(keys == 1);
-
-        futex = hash_table_get_instance(item, futex_t, ht_link);
-        return *key == futex->paddr;
-}
-
-/** Callback for removal items from futex hash table.
- *
- * @param item          Item removed from the hash table.
- */
-void futex_ht_remove_callback(link_t *item)
-{
-        futex_t *futex;
-
-        futex = hash_table_get_instance(item, futex_t, ht_link);
+        futex = hash_table_get_inst(item, futex_t, ht_link);
         free(futex);
 }