Changeset 30f1a25 in mainline

Timestamp:

2018-03-14T18:54:08Z (6 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

67f11a0

Parents:

963037b0

Message:

Make hash_table_find_next immune to livelocks

By giving hash_table_find_next the item returned from hash_table_find,
we provide it with a fixed reference with which the outer loop which
calls hash_table_find_next can terminate even if the respective bucket
contains more matching elements.

Files:

• kernel/generic/include/adt/hash_table.h (modified) (1 diff)
• kernel/generic/src/adt/hash_table.c (modified) (2 diffs)
• kernel/generic/src/ddi/irq.c (modified) (1 diff)
• uspace/lib/c/generic/adt/hash_table.c (modified) (2 diffs)
• uspace/lib/c/include/adt/hash_table.h (modified) (1 diff)

kernel/generic/include/adt/hash_table.h

@@ -95 +95 @@
 extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
 extern ht_link_t *hash_table_find(const hash_table_t *, void *);
-extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
+extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *,
+    ht_link_t *);
 extern size_t hash_table_remove(hash_table_t *, void *);
 extern void hash_table_remove_item(hash_table_t *, ht_link_t *);

kernel/generic/src/adt/hash_table.c

@@ -269 +269 @@
 
 /** Find the next item equal to item. */
-ht_link_t *hash_table_find_next(const hash_table_t *h, ht_link_t *item)
+ht_link_t *
+hash_table_find_next(const hash_table_t *h, ht_link_t *first, ht_link_t *item)
 {
         assert(item);
@@ -277 +278 @@
 
         /* Traverse the circular list until we reach the starting item again. */
-        for (link_t *cur = item->link.next; cur != &item->link; cur = cur->next) {
+        for (link_t *cur = item->link.next; cur != &first->link;
+            cur = cur->next) {
                 assert(cur);
 

kernel/generic/src/ddi/irq.c

@@ -141 +141 @@
 {
         irq_spinlock_lock(l, false);
-        for (ht_link_t *lnk = hash_table_find(h, &inr); lnk;
-            lnk = hash_table_find_next(h, lnk)) {
+        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);
                 irq_spinlock_lock(&irq->lock, false);

uspace/lib/c/generic/adt/hash_table.c

@@ -269 +269 @@
 
 /** Find the next item equal to item. */
-ht_link_t *hash_table_find_next(const hash_table_t *h, ht_link_t *item)
+ht_link_t *
+hash_table_find_next(const hash_table_t *h, ht_link_t *first, ht_link_t *item)
 {
         assert(item);
@@ -277 +278 @@
 
         /* Traverse the circular list until we reach the starting item again. */
-        for (link_t *cur = item->link.next; cur != &item->link; cur = cur->next) {
+        for (link_t *cur = item->link.next; cur != &first->link;
+            cur = cur->next) {
                 assert(cur);
 

uspace/lib/c/include/adt/hash_table.h

@@ -95 +95 @@
 extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
 extern ht_link_t *hash_table_find(const hash_table_t *, void *);
-extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
+extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *,
+    ht_link_t *);
 extern size_t hash_table_remove(hash_table_t *, void *);
 extern void hash_table_remove_item(hash_table_t *, ht_link_t *);