Changeset 0db0df2 in mainline for kernel

Timestamp:

2025-04-07T17:53:53Z (3 months ago)

Author:

Jiří Zárevúcky <zarevucky.jiri@…>

Branches:

master

Children:

45226285, 93de384

Parents:

8f8818ac

git-author:

Jiří Zárevúcky <zarevucky.jiri@…> (2025-04-07 16:41:57)

git-committer:

Jiří Zárevúcky <zarevucky.jiri@…> (2025-04-07 17:53:53)

Message:

Hash table improvements

Implement hash_table_foreach macro, analogous to list_foreach.

Remove superfluous argument to hash_table_find_next().
(If the user needs to recheck the part of the list already
checked by hash_table_find(), they can just rerun that function.)

Add hash argument to hash_table_ops_t::key_equal.
The big change here is that users with big keys can store the hash
value alongside key in their entries, and for the low low cost of
sizeof(size_t) bytes eliminate a bunch of expensive key comparisons.

Also added a hash function for strings and arbitrary data.
Found this one by asking ChatGPT, because the latency of accesses
to my book collection is currently a couple of hours.

+ Some drive-by unused #include removal.

Location:

kernel

Files:

• genarch/src/mm/page_ht.c (modified) (2 diffs)
• generic/src/cap/cap.c (modified) (1 diff)
• generic/src/ddi/irq.c (modified) (4 diffs)
• generic/src/lib/ra.c (modified) (1 diff)

kernel/genarch/src/mm/page_ht.c

@@ -55 +55 @@
 static size_t ht_hash(const ht_link_t *);
 static size_t ht_key_hash(const void *);
-static bool ht_key_equal(const void *, const ht_link_t *);
+static bool ht_key_equal(const void *, size_t, const ht_link_t *);
 static void ht_remove_callback(ht_link_t *);
 
@@ -119 +119 @@
 
 /** Return true if the key is equal to the item's lookup key. */
-bool ht_key_equal(const void *arg, const ht_link_t *item)
+bool ht_key_equal(const void *arg, size_t hash, const ht_link_t *item)
 {
         const uintptr_t *key = arg;

kernel/generic/src/cap/cap.c

@@ -118 +118 @@
 }
 
-static bool caps_key_equal(const void *key, const ht_link_t *item)
+static bool caps_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         const cap_handle_t *handle = key;

kernel/generic/src/ddi/irq.c

@@ -75 +75 @@
 static size_t irq_ht_key_hash(const void *);
 static bool irq_ht_equal(const ht_link_t *, const ht_link_t *);
-static bool irq_ht_key_equal(const void *, const ht_link_t *);
+static bool irq_ht_key_equal(const void *, size_t, const ht_link_t *);
 
 static const hash_table_ops_t irq_ht_ops = {
@@ -141 +141 @@
 {
         irq_spinlock_lock(l, false);
-        ht_link_t *first = hash_table_find(h, &inr);
-        for (ht_link_t *lnk = first; lnk;
-            lnk = hash_table_find_next(h, first, lnk)) {
-                irq_t *irq = hash_table_get_inst(lnk, irq_t, link);
+
+        hash_table_foreach(h, &inr, link, irq_t, irq) {
                 irq_spinlock_lock(&irq->lock, false);
                 if (irq->claim(irq) == IRQ_ACCEPT) {
@@ -153 +151 @@
                 irq_spinlock_unlock(&irq->lock, false);
         }
+
         irq_spinlock_unlock(l, false);
 
@@ -223 +222 @@
 
 /** Return true if the key is equal to the item's lookup key. */
-bool irq_ht_key_equal(const void *key, const ht_link_t *item)
+bool irq_ht_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         const inr_t *inr = key;

kernel/generic/src/lib/ra.c

@@ -74 +74 @@
 
 /** Return true if the key is equal to the item's lookup key */
-static bool used_key_equal(const void *key, const ht_link_t *item)
+static bool used_key_equal(const void *key, size_t, const ht_link_t *item)
 {
         const uintptr_t *base = key;