commit 634434514059256235d329d9430f91fb31044fd9 Author: Nick Mathewson nickm@torproject.org Date: Thu Nov 6 13:57:17 2014 -0500

Add correctness assertions for hashtable iteration

This is meant to prevent memory corruption bugs from doing unspeakable infinite-loop-like things to the hashtables. Addresses ticket 11737. We should disable these if they turn out to be expensive. --- changes/ticket11737 | 4 ++++ src/ext/ht.h | 24 ++++++++++++++++++++---- 2 files changed, 24 insertions(+), 4 deletions(-)

diff --git a/changes/ticket11737 b/changes/ticket11737 new file mode 100644 index 0000000..5c5f9dc --- /dev/null +++ b/changes/ticket11737 @@ -0,0 +1,4 @@ + o Minor features: + - Prevent bugs from causing infinite loops in our hash-table + iteration code by adding assertions that cached hash values have + not been corrupted. Closes ticket 11737. diff --git a/src/ext/ht.h b/src/ext/ht.h index 09f5dcc..ee64e55 100644 --- a/src/ext/ht.h +++ b/src/ext/ht.h @@ -121,16 +121,24 @@ ht_string_hash(const char *s) ((void)0) #endif

+#define HT_BUCKET_NUM_(head, field, elm, hashfn) \ + (HT_ELT_HASH_(elm,field,hashfn) % head->hth_table_length) + /* Helper: alias for the bucket containing 'elm'. */ #define HT_BUCKET_(head, field, elm, hashfn) \ - ((head)->hth_table[HT_ELT_HASH_(elm,field,hashfn) \ - % head->hth_table_length]) + ((head)->hth_table[HT_BUCKET_NUM_(head, field, elm, hashfn)])

#define HT_FOREACH(x, name, head) \ for ((x) = HT_START(name, head); \ (x) != NULL; \ (x) = HT_NEXT(name, head, x))

+#ifndef HT_NDEBUG +#define HT_ASSERT_(x) tor_assert(x) +#else +#define HT_ASSERT_(x) (void)0 +#endif + #define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \ int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ void name##_HT_CLEAR(struct name *ht); \ @@ -257,8 +265,11 @@ ht_string_hash(const char *s) { \ unsigned b = 0; \ while (b < head->hth_table_length) { \ - if (head->hth_table[b]) \ + if (head->hth_table[b]) { \ + HT_ASSERT_(b == \ + HT_BUCKET_NUM_(head,field,head->hth_table[b],hashfn)); \ return &head->hth_table[b]; \ + } \ ++b; \ } \ return NULL; \ @@ -272,13 +283,18 @@ ht_string_hash(const char *s) name##_HT_NEXT(struct name *head, struct type **elm) \ { \ if ((*elm)->field.hte_next) { \ + HT_ASSERT_(HT_BUCKET_NUM_(head,field,*elm,hashfn) == \ + HT_BUCKET_NUM_(head,field,(*elm)->field.hte_next,hashfn)); \ return &(*elm)->field.hte_next; \ } else { \ unsigned b = (HT_ELT_HASH_(*elm, field, hashfn) \ % head->hth_table_length)+1; \ while (b < head->hth_table_length) { \ - if (head->hth_table[b]) \ + if (head->hth_table[b]) { \ + HT_ASSERT_(b == \ + HT_BUCKET_NUM_(head,field,head->hth_table[b],hashfn)); \ return &head->hth_table[b]; \ + } \ ++b; \ } \ return NULL; \