kern/{hash,list}: update from upstream

This commit fixes undefined behavior in hash_str, and RCU linked list
walking.

2 files changed, 38 insertions, 12 deletions

diff --git a/kern/hash.h b/kern/hash.h
index 9d7778e..19803eb 100644
--- a/kern/hash.h
+++ b/kern/hash.h
@@ -43,6 +43,7 @@
 #define KERN_HASH_H
 
 #include <assert.h>
+#include <stdbool.h>
 #include <stdint.h>
 
 #ifdef __LP64__
@@ -54,11 +55,19 @@ static_assert(sizeof(long) == 4, "unsupported data model");
 #define hash_long(n, bits) hash_int32(n, bits)
 #endif
 
+static inline bool
+hash_bits_valid(unsigned int bits)
+{
+    return (bits != 0) && (bits <= HASH_ALLBITS);
+}
+
 static inline uint32_t
 hash_int32(uint32_t n, unsigned int bits)
 {
     uint32_t hash;
 
+    assert(hash_bits_valid(bits));
+
     hash = n;
     hash = ~hash + (hash << 15);
     hash ^= (hash >> 12);
@@ -75,6 +84,8 @@ hash_int64(uint64_t n, unsigned int bits)
 {
     uint64_t hash;
 
+    assert(hash_bits_valid(bits));
+
     hash = n;
     hash = ~hash + (hash << 21);
     hash ^= (hash >> 24);
@@ -100,9 +111,11 @@ hash_ptr(const void *ptr, unsigned int bits)
 static inline unsigned long
 hash_str(const char *str, unsigned int bits)
 {
-    unsigned long hash;
+    unsigned long hash, mask;
     char c;
 
+    assert(hash_bits_valid(bits));
+
     for (hash = 0; /* no condition */; str++) {
         c = *str;
 
@@ -113,7 +126,13 @@ hash_str(const char *str, unsigned int bits)
         hash = ((hash << 5) - hash) + c;
     }
 
-    return hash & ((1UL << bits) - 1);
+    /*
+     * This mask construction avoids the undefined behavior that would
+     * result from directly shifting by the number of bits, if that number
+     * is equal to the width of the hash.
+     */
+    mask = (~0UL >> (HASH_ALLBITS - bits));
+    return hash & mask;
 }
 
 #endif /* KERN_HASH_H */
diff --git a/kern/list.h b/kern/list.h
index 832d94f..8163176 100644
--- a/kern/list.h
+++ b/kern/list.h
@@ -478,12 +478,12 @@ list_rcu_remove(struct list *node)
  * the node pointer can only be read once, preventing the combination
  * of lockless list_empty()/list_first_entry() variants.
  */
-#define list_rcu_first_entry(list, type, member)            \
+#define list_rcu_first_entry(head, type, member)            \
 MACRO_BEGIN                                                 \
     struct list *list___;                                   \
     struct list *first___;                                  \
                                                             \
-    list___ = (list);                                       \
+    list___ = (head);                                       \
     first___ = list_rcu_first(list___);                     \
     list_end(list___, first___)                             \
         ? NULL                                              \
@@ -497,8 +497,17 @@ MACRO_END
  * the node pointer can only be read once, preventing the combination
  * of lockless list_empty()/list_next_entry() variants.
  */
-#define list_rcu_next_entry(entry, member) \
-    list_rcu_first_entry(&entry->member, typeof(*entry), member)
+#define list_rcu_next_entry(head, entry, member)            \
+MACRO_BEGIN                                                 \
+    struct list *list___;                                   \
+    struct list *next___;                                   \
+                                                            \
+    list___ = (head);                                       \
+    next___ = list_rcu_next(&entry->member);                \
+    list_end(list___, next___)                              \
+        ? NULL                                              \
+        : list_entry(next___, typeof(*entry), member);      \
+MACRO_END
 
 /*
  * Forge a loop to process all nodes of a list.
@@ -515,11 +524,9 @@ for (node = list_rcu_first(list);           \
  *
  * The entry node must not be altered during the loop.
  */
-#define list_rcu_for_each_entry(list, entry, member)        \
-for (entry = list_rcu_entry(list_first(list),               \
-                               typeof(*entry), member);     \
-     !list_end(list, &entry->member);                       \
-     entry = list_rcu_entry(list_next(&entry->member),      \
-                               typeof(*entry), member))
+#define list_rcu_for_each_entry(list, entry, member)                \
+for (entry = list_rcu_first_entry(list, typeof(*entry), member);    \
+     entry != NULL;                                                 \
+     entry = list_rcu_next_entry(list, entry, member))
 
 #endif /* KERN_LIST_H */