Merge pull request #13350 from opensourcerouting/typesafe-fixes-20230421

lib: typesafe shenanigans

3 files changed, 27 insertions, 2 deletions

diff --git a/lib/typesafe.c b/lib/typesafe.c
index 0da35d0f8c..c077447985 100644
--- a/lib/typesafe.c
+++ b/lib/typesafe.c
@@ -85,6 +85,15 @@ void typesafe_hash_grow(struct thash_head *head)
 	uint32_t newsize = head->count, i, j;
 	uint8_t newshift, delta;
 
+	/* note hash_grow is called after head->count++, so newsize is
+	 * guaranteed to be >= 1.  So the minimum argument to builtin_ctz
+	 * below is 2, which returns 1, and that makes newshift >= 2.
+	 *
+	 * Calling hash_grow with a zero head->count would result in a
+	 * malformed hash table that has tabshift == 1.
+	 */
+	assert(head->count > 0);
+
 	hash_consistency_check(head);
 
 	newsize |= newsize >> 1;
diff --git a/lib/typesafe.h b/lib/typesafe.h
index 3292b6ec8b..8eb59c33b7 100644
--- a/lib/typesafe.h
+++ b/lib/typesafe.h
@@ -783,6 +783,12 @@ struct thash_head {
 	struct thash_item **entries;
 	uint32_t count;
 
+	/* tabshift can be 0 if the hash table is empty and entries is NULL.
+	 * otherwise it will always be 2 or larger because it contains
+	 * the shift value *plus 1*.  This is a trick to make HASH_SIZE return
+	 * the correct value (with the >> 1) for tabshift == 0, without needing
+	 * a conditional branch.
+	 */
 	uint8_t tabshift;
 	uint8_t minshift, maxshift;
 };
@@ -791,8 +797,11 @@ struct thash_head {
 	((1U << (tabshift)) >> 1)
 #define HASH_SIZE(head) \
 	_HASH_SIZE((head).tabshift)
-#define _HASH_KEY(tabshift, val) \
-	((val) >> (33 - (tabshift)))
+#define _HASH_KEY(tabshift, val)                                               \
+	({                                                                     \
+		assume((tabshift) >= 2 && (tabshift) <= 33);                   \
+		(val) >> (33 - (tabshift));                                    \
+	})
 #define HASH_KEY(head, val) \
 	_HASH_KEY((head).tabshift, val)
 #define HASH_GROW_THRESHOLD(head) \
@@ -939,6 +948,8 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h)              \
 macro_pure bool prefix ## _member(const struct prefix##_head *h,               \
 				  const type *item)                            \
 {                                                                              \
+	if (!h->hh.tabshift)                                                   \
+		return NULL;                                                   \
 	uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \
 	const struct thash_item *hitem = h->hh.entries[hbits];                 \
 	while (hitem && hitem->hashval < hval)                                 \
diff --git a/tests/lib/test_typelist.h b/tests/lib/test_typelist.h
index 91528139b5..80c4005437 100644
--- a/tests/lib/test_typelist.h
+++ b/tests/lib/test_typelist.h
@@ -171,6 +171,11 @@ static void concat(test_, TYPE)(void)
 
 	ts_hash("init", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
 
+#if !IS_ATOMIC(REALTYPE)
+	assert(!list_member(&head, &itm[0]));
+	assert(!list_member(&head, &itm[1]));
+#endif
+
 #if IS_SORTED(REALTYPE)
 	prng = prng_new(0);
 	k = 0;