kern/{hash,list}: update from upstream

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

1 files changed, 21 insertions, 2 deletions

diff --git a/kern/hash.h b/kern/hash.h
index 9d7778eb..19803eb2 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 */