diff options
author | antirez <antirez@gmail.com> | 2015-02-05 10:51:05 +0100 |
---|---|---|
committer | antirez <antirez@gmail.com> | 2015-02-11 10:52:26 +0100 |
commit | cd0fcf11e7704c72b68a19f92e093bc5976fe7fc (patch) | |
tree | 36c6ddb72e71e102ddb9a6360ce40b5354cbe9f5 /src | |
parent | 777020839a1ba68ea5bd77a5b17648f4b831caf7 (diff) | |
download | redis-cd0fcf11e7704c72b68a19f92e093bc5976fe7fc.tar.gz |
dict.c: put a bound to max work dictRehash() call can do.
Related to issue #2306.
Diffstat (limited to 'src')
-rw-r--r-- | src/dict.c | 13 |
1 files changed, 11 insertions, 2 deletions
diff --git a/src/dict.c b/src/dict.c index 26707dd58..ad74d222a 100644 --- a/src/dict.c +++ b/src/dict.c @@ -235,9 +235,15 @@ int dictExpand(dict *d, unsigned long size) /* Performs N steps of incremental rehashing. Returns 1 if there are still * keys to move from the old to the new hash table, otherwise 0 is returned. + * * Note that a rehashing step consists in moving a bucket (that may have more - * than one key as we use chaining) from the old to the new hash table. */ + * than one key as we use chaining) from the old to the new hash table, however + * since part of the hash table may be composed of empty spaces, it is not + * guaranteed that this function will rehash even a single bucket, since it + * will visit at max N*10 empty buckets in total, otherwise the amount of + * work it does would be unbound and the function may block for a long time. */ int dictRehash(dict *d, int n) { + int empty_visits = n*10; /* Max number of empty buckets to visit. */ if (!dictIsRehashing(d)) return 0; while(n--) { @@ -255,7 +261,10 @@ int dictRehash(dict *d, int n) { /* Note that rehashidx can't overflow as we are sure there are more * elements because ht[0].used != 0 */ assert(d->ht[0].size > (unsigned long)d->rehashidx); - while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++; + while(d->ht[0].table[d->rehashidx] == NULL) { + d->rehashidx++; + if (--empty_visits == 0) return 1; + } de = d->ht[0].table[d->rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ while(de) { |