Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2014, 2016 Nicira, Inc.
3 : : *
4 : : * Licensed under the Apache License, Version 2.0 (the "License");
5 : : * you may not use this file except in compliance with the License.
6 : : * You may obtain a copy of the License at:
7 : : *
8 : : * http://www.apache.org/licenses/LICENSE-2.0
9 : : *
10 : : * Unless required by applicable law or agreed to in writing, software
11 : : * distributed under the License is distributed on an "AS IS" BASIS,
12 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : : * See the License for the specific language governing permissions and
14 : : * limitations under the License.
15 : : */
16 : :
17 : : #include <config.h>
18 : : #include "ccmap.h"
19 : : #include "coverage.h"
20 : : #include "bitmap.h"
21 : : #include "hash.h"
22 : : #include "ovs-rcu.h"
23 : : #include "random.h"
24 : : #include "util.h"
25 : :
26 : 100890 : COVERAGE_DEFINE(ccmap_expand);
27 : 434382 : COVERAGE_DEFINE(ccmap_shrink);
28 : :
29 : : /* A count-only version of the cmap. */
30 : :
31 : : /* Allow protected access to the value without atomic semantics. This makes
32 : : * the exclusive writer somewhat faster. */
33 : : typedef union {
34 : : unsigned long long protected_value;
35 : : ATOMIC(unsigned long long) atomic_value;
36 : : } ccmap_node_t;
37 : : BUILD_ASSERT_DECL(sizeof(ccmap_node_t) == sizeof(uint64_t));
38 : :
39 : : static uint64_t
40 : 452120700 : ccmap_node_get(const ccmap_node_t *node)
41 : : {
42 : : uint64_t value;
43 : :
44 : 452120700 : atomic_read_relaxed(&CONST_CAST(ccmap_node_t *, node)->atomic_value,
45 : : &value);
46 : :
47 : 452120700 : return value;
48 : : }
49 : :
50 : : /* It is safe to allow compiler optimize reads by the exclusive writer. */
51 : : static uint64_t
52 : 2577192 : ccmap_node_get_protected(const ccmap_node_t *node)
53 : : {
54 : 2577192 : return node->protected_value;
55 : : }
56 : :
57 : : static void
58 : 207699 : ccmap_node_set_protected(ccmap_node_t *node, uint64_t value)
59 : : {
60 : 207699 : atomic_store_relaxed(&node->atomic_value, value);
61 : 207699 : }
62 : :
63 : : static uint64_t
64 : 207324 : ccmap_node(uint32_t count, uint32_t hash)
65 : : {
66 : 207324 : return (uint64_t)count << 32 | hash;
67 : : }
68 : :
69 : : static uint32_t
70 : 453978663 : ccmap_node_hash(uint64_t node)
71 : : {
72 : 453978663 : return node;
73 : : }
74 : :
75 : : static uint32_t
76 : 19437092 : ccmap_node_count(uint64_t node)
77 : : {
78 : 19437092 : return node >> 32;
79 : : }
80 : :
81 : : /* Number of nodes per bucket. */
82 : : #define CCMAP_K (CACHE_LINE_SIZE / sizeof(ccmap_node_t))
83 : :
84 : : /* A cuckoo hash bucket. Designed to be cache-aligned and exactly one cache
85 : : * line long. */
86 : : struct ccmap_bucket {
87 : : /* Each node incudes both the hash (low 32-bits) and the count (high
88 : : * 32-bits), allowing readers always getting a consistent pair. */
89 : : ccmap_node_t nodes[CCMAP_K];
90 : : };
91 : : BUILD_ASSERT_DECL(sizeof(struct ccmap_bucket) == CACHE_LINE_SIZE);
92 : :
93 : : /* Default maximum load factor (as a fraction of UINT32_MAX + 1) before
94 : : * enlarging a ccmap. Reasonable values lie between about 75% and 93%. Smaller
95 : : * values waste memory; larger values increase the average insertion time. */
96 : : #define CCMAP_MAX_LOAD ((uint32_t) (UINT32_MAX * .85))
97 : :
98 : : /* Default minimum load factor (as a fraction of UINT32_MAX + 1) before
99 : : * shrinking a ccmap. Currently, the value is chosen to be 20%, this
100 : : * means ccmap will have a 40% load factor after shrink. */
101 : : #define CCMAP_MIN_LOAD ((uint32_t) (UINT32_MAX * .20))
102 : :
103 : : /* The implementation of a concurrent hash map. */
104 : : struct ccmap_impl {
105 : : unsigned int n_unique; /* Number of in-use nodes. */
106 : : unsigned int n; /* Number of hashes inserted. */
107 : : unsigned int max_n; /* Max nodes before enlarging. */
108 : : unsigned int min_n; /* Min nodes before shrinking. */
109 : : uint32_t mask; /* Number of 'buckets', minus one. */
110 : : uint32_t basis; /* Basis for rehashing client's hash values. */
111 : :
112 : : /* Padding to make ccmap_impl exactly one cache line long. */
113 : : uint8_t pad[CACHE_LINE_SIZE - sizeof(unsigned int) * 6];
114 : :
115 : : struct ccmap_bucket buckets[];
116 : : };
117 : : BUILD_ASSERT_DECL(sizeof(struct ccmap_impl) == CACHE_LINE_SIZE);
118 : :
119 : : static struct ccmap_impl *ccmap_rehash(struct ccmap *, uint32_t mask);
120 : :
121 : : /* Given a rehashed value 'hash', returns the other hash for that rehashed
122 : : * value. This is symmetric: other_hash(other_hash(x)) == x. (See also "Hash
123 : : * Functions" at the top of cmap.c.) */
124 : : static uint32_t
125 : 26221922 : other_hash(uint32_t hash)
126 : : {
127 : 26221922 : return (hash << 16) | (hash >> 16);
128 : : }
129 : :
130 : : /* Returns the rehashed value for 'hash' within 'impl'. (See also "Hash
131 : : * Functions" at the top of this file.) */
132 : : static uint32_t
133 : 42119932 : rehash(const struct ccmap_impl *impl, uint32_t hash)
134 : : {
135 : 42119932 : return hash_finish(impl->basis, hash);
136 : : }
137 : :
138 : : static struct ccmap_impl *
139 : 42223224 : ccmap_get_impl(const struct ccmap *ccmap)
140 : : {
141 : 42223224 : return ovsrcu_get(struct ccmap_impl *, &ccmap->impl);
142 : : }
143 : :
144 : : static uint32_t
145 : 119374 : calc_max_n(uint32_t mask)
146 : : {
147 : 119374 : return ((uint64_t) (mask + 1) * CCMAP_K * CCMAP_MAX_LOAD) >> 32;
148 : : }
149 : :
150 : : static uint32_t
151 : 119374 : calc_min_n(uint32_t mask)
152 : : {
153 : 119374 : return ((uint64_t) (mask + 1) * CCMAP_K * CCMAP_MIN_LOAD) >> 32;
154 : : }
155 : :
156 : : static struct ccmap_impl *
157 : 119374 : ccmap_impl_create(uint32_t mask)
158 : : {
159 : : struct ccmap_impl *impl;
160 : :
161 [ - + ]: 119374 : ovs_assert(is_pow2(mask + 1));
162 : :
163 : 119374 : impl = xzalloc_cacheline(sizeof *impl
164 : 119374 : + (mask + 1) * sizeof *impl->buckets);
165 : 119374 : impl->n_unique = 0;
166 : 119374 : impl->n = 0;
167 : 119374 : impl->max_n = calc_max_n(mask);
168 : 119374 : impl->min_n = calc_min_n(mask);
169 : 119374 : impl->mask = mask;
170 : 119374 : impl->basis = random_uint32();
171 : :
172 : 119374 : return impl;
173 : : }
174 : :
175 : : /* Initializes 'ccmap' as an empty concurrent hash map. */
176 : : void
177 : 61104 : ccmap_init(struct ccmap *ccmap)
178 : : {
179 : 61104 : ovsrcu_set(&ccmap->impl, ccmap_impl_create(0));
180 : 61104 : }
181 : :
182 : : /* Destroys 'ccmap'.
183 : : *
184 : : * The client is responsible for destroying any data previously held in
185 : : * 'ccmap'. */
186 : : void
187 : 60862 : ccmap_destroy(struct ccmap *ccmap)
188 : : {
189 [ + - ]: 60862 : if (ccmap) {
190 : 60862 : ovsrcu_postpone(free_cacheline, ccmap_get_impl(ccmap));
191 : : }
192 : 60862 : }
193 : :
194 : : /* Returns the number of hashes inserted in 'ccmap', including duplicates. */
195 : : size_t
196 : 12000 : ccmap_count(const struct ccmap *ccmap)
197 : : {
198 : 12000 : return ccmap_get_impl(ccmap)->n;
199 : : }
200 : :
201 : : /* Returns true if 'ccmap' is empty, false otherwise. */
202 : : bool
203 : 6000 : ccmap_is_empty(const struct ccmap *ccmap)
204 : : {
205 : 6000 : return ccmap_count(ccmap) == 0;
206 : : }
207 : :
208 : : /* returns 0 if not found. Map does not contain zero counts. */
209 : : static uint32_t
210 : 67924861 : ccmap_find_in_bucket(const struct ccmap_bucket *bucket, uint32_t hash)
211 : : {
212 [ + + ]: 503184119 : for (int i = 0; i < CCMAP_K; i++) {
213 : 452120697 : uint64_t node = ccmap_node_get(&bucket->nodes[i]);
214 : :
215 [ + + ]: 452120700 : if (ccmap_node_hash(node) == hash) {
216 : 16861445 : return ccmap_node_count(node);
217 : : }
218 : : }
219 : 51063422 : return 0;
220 : : }
221 : :
222 : : /* Searches 'ccmap' for a node with the specified 'hash'. If one is
223 : : * found, returns the count associated with it, otherwise zero.
224 : : */
225 : : uint32_t
226 : 41911438 : ccmap_find(const struct ccmap *ccmap, uint32_t hash)
227 : : {
228 : 41911438 : const struct ccmap_impl *impl = ccmap_get_impl(ccmap);
229 : 41911438 : uint32_t h = rehash(impl, hash);
230 : : uint32_t count;
231 : :
232 : 41911438 : count = ccmap_find_in_bucket(&impl->buckets[h & impl->mask], hash);
233 [ + + ]: 41911440 : if (!count) {
234 : 26013428 : h = other_hash(h);
235 : 26013428 : count = ccmap_find_in_bucket(&impl->buckets[h & impl->mask], hash);
236 : : }
237 : 41911438 : return count;
238 : : }
239 : :
240 : : static int
241 : 310859 : ccmap_find_slot_protected(struct ccmap_bucket *b, uint32_t hash,
242 : : uint32_t *count)
243 : : {
244 [ + + ]: 2036796 : for (int i = 0; i < CCMAP_K; i++) {
245 : 1830124 : uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
246 : :
247 : 1830124 : *count = ccmap_node_count(node);
248 [ + + ][ + + ]: 1830124 : if (ccmap_node_hash(node) == hash && *count) {
249 : 104187 : return i;
250 : : }
251 : : }
252 : 206672 : return -1;
253 : : }
254 : :
255 : : static int
256 : 105063 : ccmap_find_empty_slot_protected(struct ccmap_bucket *b)
257 : : {
258 [ + + ]: 232353 : for (int i = 0; i < CCMAP_K; i++) {
259 : 230427 : uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
260 : :
261 [ + + ]: 230427 : if (!ccmap_node_count(node)) {
262 : 103137 : return i;
263 : : }
264 : : }
265 : 1926 : return -1;
266 : : }
267 : :
268 : : static void
269 : 207324 : ccmap_set_bucket(struct ccmap_bucket *b, int i, uint32_t count, uint32_t hash)
270 : : {
271 : 207324 : ccmap_node_set_protected(&b->nodes[i], ccmap_node(count, hash));
272 : 207324 : }
273 : :
274 : : /* Searches 'b' for a node with the given 'hash'. If it finds one, increments
275 : : * the associated count by 'inc' and returns the new value. Otherwise returns
276 : : * 0. */
277 : : static uint32_t
278 : 220522 : ccmap_inc_bucket_existing(struct ccmap_bucket *b, uint32_t hash, uint32_t inc)
279 : : {
280 : : uint32_t count;
281 : :
282 : 220522 : int i = ccmap_find_slot_protected(b, hash, &count);
283 [ + + ]: 220522 : if (i < 0) {
284 : 206298 : return 0;
285 : : }
286 : 14224 : count += inc;
287 : 14224 : ccmap_set_bucket(b, i, count, hash);
288 : 220522 : return count;
289 : : }
290 : :
291 : : /* Searches 'b' for an empty slot. If successful, stores 'inc' and 'hash' in
292 : : * the slot and returns 'inc'. Otherwise, returns 0. */
293 : : static uint32_t
294 : 104490 : ccmap_inc_bucket_new(struct ccmap_bucket *b, uint32_t hash, uint32_t inc)
295 : : {
296 : 104490 : int i = ccmap_find_empty_slot_protected(b);
297 [ + + ]: 104490 : if (i < 0) {
298 : 1724 : return 0;
299 : : }
300 : 102766 : ccmap_set_bucket(b, i, inc, hash);
301 : 102766 : return inc;
302 : : }
303 : :
304 : : /* Returns the other bucket that b->nodes[slot] could occupy in 'impl'. (This
305 : : * might be the same as 'b'.) */
306 : : static struct ccmap_bucket *
307 : 1170 : other_bucket_protected(struct ccmap_impl *impl, struct ccmap_bucket *b, int slot)
308 : : {
309 : 1170 : uint64_t node = ccmap_node_get_protected(&b->nodes[slot]);
310 : :
311 : 1170 : uint32_t h1 = rehash(impl, ccmap_node_hash(node));
312 : 1170 : uint32_t h2 = other_hash(h1);
313 : 1170 : uint32_t b_idx = b - impl->buckets;
314 [ + + ]: 1170 : uint32_t other_h = (h1 & impl->mask) == b_idx ? h2 : h1;
315 : :
316 : 1170 : return &impl->buckets[other_h & impl->mask];
317 : : }
318 : :
319 : : /* Count 'inc' for 'hash' is to be inserted into 'impl', but both candidate
320 : : * buckets 'b1' and 'b2' are full. This function attempts to rearrange buckets
321 : : * within 'impl' to make room for 'hash'.
322 : : *
323 : : * Returns 'inc' if the new count for the 'hash' was inserted, otherwise
324 : : * returns 0.
325 : : *
326 : : * The implementation is a general-purpose breadth-first search. At first
327 : : * glance, this is more complex than a random walk through 'impl' (suggested by
328 : : * some references), but random walks have a tendency to loop back through a
329 : : * single bucket. We have to move nodes backward along the path that we find,
330 : : * so that no node actually disappears from the hash table, which means a
331 : : * random walk would have to be careful to deal with loops. By contrast, a
332 : : * successful breadth-first search always finds a *shortest* path through the
333 : : * hash table, and a shortest path will never contain loops, so it avoids that
334 : : * problem entirely.
335 : : */
336 : : static uint32_t
337 : 371 : ccmap_inc_bfs(struct ccmap_impl *impl, uint32_t hash,
338 : : struct ccmap_bucket *b1, struct ccmap_bucket *b2, uint32_t inc)
339 : : {
340 : : enum { MAX_DEPTH = 4 };
341 : :
342 : : /* A path from 'start' to 'end' via the 'n' steps in 'slots[]'.
343 : : *
344 : : * One can follow the path via:
345 : : *
346 : : * struct ccmap_bucket *b;
347 : : * int i;
348 : : *
349 : : * b = path->start;
350 : : * for (i = 0; i < path->n; i++) {
351 : : * b = other_bucket_protected(impl, b, path->slots[i]);
352 : : * }
353 : : * ovs_assert(b == path->end);
354 : : */
355 : : struct ccmap_path {
356 : : struct ccmap_bucket *start; /* First bucket along the path. */
357 : : struct ccmap_bucket *end; /* Last bucket on the path. */
358 : : uint8_t slots[MAX_DEPTH]; /* Slots used for each hop. */
359 : : int n; /* Number of slots[]. */
360 : : };
361 : :
362 : : /* We need to limit the amount of work we do trying to find a path. It
363 : : * might actually be impossible to rearrange the ccmap, and after some time
364 : : * it is likely to be easier to rehash the entire ccmap.
365 : : *
366 : : * This value of MAX_QUEUE is an arbitrary limit suggested by one of the
367 : : * references. Empirically, it seems to work OK. */
368 : : enum { MAX_QUEUE = 500 };
369 : : struct ccmap_path queue[MAX_QUEUE];
370 : 371 : int head = 0;
371 : 371 : int tail = 0;
372 : :
373 : : /* Add 'b1' and 'b2' as starting points for the search. */
374 : 371 : queue[head].start = b1;
375 : 371 : queue[head].end = b1;
376 : 371 : queue[head].n = 0;
377 : 371 : head++;
378 [ + + ]: 371 : if (b1 != b2) {
379 : 151 : queue[head].start = b2;
380 : 151 : queue[head].end = b2;
381 : 151 : queue[head].n = 0;
382 : 151 : head++;
383 : : }
384 : :
385 [ + - ]: 383 : while (tail < head) {
386 : 383 : const struct ccmap_path *path = &queue[tail++];
387 : 383 : struct ccmap_bucket *this = path->end;
388 : : int i;
389 : :
390 [ + + ]: 807 : for (i = 0; i < CCMAP_K; i++) {
391 : 795 : struct ccmap_bucket *next = other_bucket_protected(impl, this, i);
392 : : int j;
393 : :
394 [ + + ]: 795 : if (this == next) {
395 : 222 : continue;
396 : : }
397 : :
398 : 573 : j = ccmap_find_empty_slot_protected(next);
399 [ + + ]: 573 : if (j >= 0) {
400 : : /* We've found a path along which we can rearrange the hash
401 : : * table: Start at path->start, follow all the slots in
402 : : * path->slots[], then follow slot 'i', then the bucket you
403 : : * arrive at has slot 'j' empty. */
404 : : struct ccmap_bucket *buckets[MAX_DEPTH + 2];
405 : : int slots[MAX_DEPTH + 2];
406 : : int k;
407 : :
408 : : /* Figure out the full sequence of slots. */
409 [ + + ]: 375 : for (k = 0; k < path->n; k++) {
410 : 4 : slots[k] = path->slots[k];
411 : : }
412 : 371 : slots[path->n] = i;
413 : 371 : slots[path->n + 1] = j;
414 : :
415 : : /* Figure out the full sequence of buckets. */
416 : 371 : buckets[0] = path->start;
417 [ + + ]: 746 : for (k = 0; k <= path->n; k++) {
418 : 375 : buckets[k + 1] = other_bucket_protected(impl, buckets[k], slots[k]);
419 : : }
420 : :
421 : : /* Now the path is fully expressed. One can start from
422 : : * buckets[0], go via slots[0] to buckets[1], via slots[1] to
423 : : * buckets[2], and so on.
424 : : *
425 : : * Move all the nodes across the path "backward". After each
426 : : * step some node appears in two buckets. Thus, every node is
427 : : * always visible to a concurrent search. */
428 [ + + ]: 746 : for (k = path->n + 1; k > 0; k--) {
429 : 375 : uint64_t node = ccmap_node_get_protected
430 : 375 : (&buckets[k - 1]->nodes[slots[k - 1]]);
431 : 375 : ccmap_node_set_protected(&buckets[k]->nodes[slots[k]],
432 : : node);
433 : : }
434 : :
435 : : /* Finally, insert the count. */
436 : 371 : ccmap_set_bucket(buckets[0], slots[0], inc, hash);
437 : :
438 : 371 : return inc;
439 : : }
440 : :
441 [ + - ][ + - ]: 202 : if (path->n < MAX_DEPTH && head < MAX_QUEUE) {
442 : 202 : struct ccmap_path *new_path = &queue[head++];
443 : :
444 : 202 : *new_path = *path;
445 : 202 : new_path->end = next;
446 : 202 : new_path->slots[new_path->n++] = i;
447 : : }
448 : : }
449 : : }
450 : :
451 : 371 : return 0;
452 : : }
453 : :
454 : : /* Increments the count associated with 'hash', in 'impl', by 'inc'. */
455 : : static uint32_t
456 : 117361 : ccmap_try_inc(struct ccmap_impl *impl, uint32_t hash, uint32_t inc)
457 : : {
458 : 117361 : uint32_t h1 = rehash(impl, hash);
459 : 117361 : uint32_t h2 = other_hash(h1);
460 : 117361 : struct ccmap_bucket *b1 = &impl->buckets[h1 & impl->mask];
461 : 117361 : struct ccmap_bucket *b2 = &impl->buckets[h2 & impl->mask];
462 : : uint32_t count;
463 : :
464 : 117361 : return OVS_UNLIKELY(count = ccmap_inc_bucket_existing(b1, hash, inc))
465 [ + + ]: 220522 : ? count : OVS_UNLIKELY(count = ccmap_inc_bucket_existing(b2, hash, inc))
466 [ + + ]: 206298 : ? count : OVS_LIKELY(count = ccmap_inc_bucket_new(b1, hash, inc))
467 [ + + ]: 104490 : ? count : OVS_LIKELY(count = ccmap_inc_bucket_new(b2, hash, inc))
468 [ + + ]: 1353 : ? count : ccmap_inc_bfs(impl, hash, b1, b2, inc);
469 : : }
470 : :
471 : : /* Increments the count of 'hash' values in the 'ccmap'. The caller must
472 : : * ensure that 'ccmap' cannot change concurrently (from another thread).
473 : : *
474 : : * Returns the current count of the given hash value after the incremention. */
475 : : uint32_t
476 : 90691 : ccmap_inc(struct ccmap *ccmap, uint32_t hash)
477 : : {
478 : 90691 : struct ccmap_impl *impl = ccmap_get_impl(ccmap);
479 : : uint32_t count;
480 : :
481 [ + + ]: 90691 : if (OVS_UNLIKELY(impl->n_unique >= impl->max_n)) {
482 : 1344 : COVERAGE_INC(ccmap_expand);
483 : 1344 : impl = ccmap_rehash(ccmap, (impl->mask << 1) | 1);
484 : : }
485 : :
486 [ - + ]: 90691 : while (OVS_UNLIKELY(!(count = ccmap_try_inc(impl, hash, 1)))) {
487 : 0 : impl = ccmap_rehash(ccmap, impl->mask);
488 : : }
489 : 90691 : ++impl->n;
490 [ + + ]: 90691 : if (count == 1) {
491 : 76467 : ++impl->n_unique;
492 : : }
493 : 90691 : return count;
494 : : }
495 : :
496 : : /* Decrement the count associated with 'hash' in the bucket identified by
497 : : * 'h'. Return the OLD count if successful, or 0. */
498 : : static uint32_t
499 : 90337 : ccmap_dec__(struct ccmap_impl *impl, uint32_t hash, uint32_t h)
500 : : {
501 : 90337 : struct ccmap_bucket *b = &impl->buckets[h & impl->mask];
502 : : uint32_t count;
503 : :
504 : 90337 : int slot = ccmap_find_slot_protected(b, hash, &count);
505 [ + + ]: 90337 : if (slot < 0) {
506 : 374 : return 0;
507 : : }
508 : :
509 : 89963 : ccmap_set_bucket(b, slot, count - 1, hash);
510 : 90337 : return count;
511 : : }
512 : :
513 : : /* Decrements the count associated with 'hash'. The caller must
514 : : * ensure that 'ccmap' cannot change concurrently (from another thread).
515 : : *
516 : : * Returns the current count related to 'hash' in the ccmap after the
517 : : * decrement. */
518 : : uint32_t
519 : 89963 : ccmap_dec(struct ccmap *ccmap, uint32_t hash)
520 : : {
521 : 89963 : struct ccmap_impl *impl = ccmap_get_impl(ccmap);
522 : 89963 : uint32_t h1 = rehash(impl, hash);
523 : 89963 : uint32_t h2 = other_hash(h1);
524 : :
525 : 89963 : uint32_t old_count = ccmap_dec__(impl, hash, h1);
526 [ + + ]: 89963 : if (!old_count) {
527 : 374 : old_count = ccmap_dec__(impl, hash, h2);
528 : : }
529 [ - + ]: 89963 : ovs_assert(old_count);
530 : :
531 : 89963 : old_count--;
532 : :
533 [ + + ]: 89963 : if (old_count == 0) {
534 : 75979 : impl->n_unique--;
535 [ + + ]: 75979 : if (OVS_UNLIKELY(impl->n_unique < impl->min_n)) {
536 : 56926 : COVERAGE_INC(ccmap_shrink);
537 : 56926 : impl = ccmap_rehash(ccmap, impl->mask >> 1);
538 : : }
539 : : }
540 : 89963 : impl->n--;
541 : 89963 : return old_count;
542 : : }
543 : :
544 : : static bool
545 : 58270 : ccmap_try_rehash(const struct ccmap_impl *old, struct ccmap_impl *new)
546 : : {
547 : : const struct ccmap_bucket *b;
548 : :
549 [ + + ]: 122657 : for (b = old->buckets; b <= &old->buckets[old->mask]; b++) {
550 [ + + ]: 579483 : for (int i = 0; i < CCMAP_K; i++) {
551 : 515096 : uint64_t node = ccmap_node_get_protected(&b->nodes[i]);
552 : 515096 : uint32_t count = ccmap_node_count(node);
553 : :
554 [ + + ][ - + ]: 515096 : if (count && !ccmap_try_inc(new, ccmap_node_hash(node), count)) {
555 : 0 : return false;
556 : : }
557 : : }
558 : : }
559 : 58270 : return true;
560 : : }
561 : :
562 : : static struct ccmap_impl *
563 : 58270 : ccmap_rehash(struct ccmap *ccmap, uint32_t mask)
564 : : {
565 : 58270 : struct ccmap_impl *old = ccmap_get_impl(ccmap);
566 : 58270 : struct ccmap_impl *new = ccmap_impl_create(mask);
567 : :
568 [ - + ]: 58270 : ovs_assert(old->n_unique < new->max_n);
569 : :
570 [ - + ]: 58270 : while (!ccmap_try_rehash(old, new)) {
571 : 0 : memset(new->buckets, 0, (mask + 1) * sizeof *new->buckets);
572 : 0 : new->basis = random_uint32();
573 : : }
574 : :
575 : 58270 : new->n = old->n;
576 : 58270 : new->n_unique = old->n_unique;
577 : 58270 : ovsrcu_set(&ccmap->impl, new);
578 : 58270 : ovsrcu_postpone(free_cacheline, old);
579 : :
580 : 58270 : return new;
581 : : }
|
