diff options
| author | Donald Sharp <donaldsharp72@gmail.com> | 2023-04-23 15:06:59 -0400 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-04-23 15:06:59 -0400 |
| commit | 3eefea924914b8ff48391e24b475b769afa7c45b (patch) | |
| tree | be185da9c64dcde20eddd9144b714e27e3808b6a /lib | |
| parent | 97ed21a5467d1df5f34e93e29359bfd00360b6b6 (diff) | |
| parent | 5523a505f4bd6ce57f951ccb0cc7b9b29a963d7c (diff) | |
Merge pull request #13350 from opensourcerouting/typesafe-fixes-20230421
lib: typesafe shenanigans
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/typesafe.c | 9 | ||||
| -rw-r--r-- | lib/typesafe.h | 15 |
2 files changed, 22 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) \ |