]>
git.proxmox.com Git - mirror_ovs.git/blob - lib/ccmap.c
2 * Copyright (c) 2014, 2016 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
26 COVERAGE_DEFINE(ccmap_expand
);
27 COVERAGE_DEFINE(ccmap_shrink
);
29 /* A count-only version of the cmap. */
31 /* Allow protected access to the value without atomic semantics. This makes
32 * the exclusive writer somewhat faster. */
34 unsigned long long protected_value
;
35 ATOMIC(unsigned long long) atomic_value
;
37 BUILD_ASSERT_DECL(sizeof(ccmap_node_t
) == sizeof(uint64_t));
40 ccmap_node_get(const ccmap_node_t
*node
)
44 atomic_read_relaxed(&CONST_CAST(ccmap_node_t
*, node
)->atomic_value
,
50 /* It is safe to allow compiler optimize reads by the exclusive writer. */
52 ccmap_node_get_protected(const ccmap_node_t
*node
)
54 return node
->protected_value
;
58 ccmap_node_set_protected(ccmap_node_t
*node
, uint64_t value
)
60 atomic_store_relaxed(&node
->atomic_value
, value
);
64 ccmap_node(uint32_t count
, uint32_t hash
)
66 return (uint64_t)count
<< 32 | hash
;
70 ccmap_node_hash(uint64_t node
)
76 ccmap_node_count(uint64_t node
)
81 /* Number of nodes per bucket. */
82 #define CCMAP_K (CACHE_LINE_SIZE / sizeof(ccmap_node_t))
84 /* A cuckoo hash bucket. Designed to be cache-aligned and exactly one cache
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
];
91 BUILD_ASSERT_DECL(sizeof(struct ccmap_bucket
) == CACHE_LINE_SIZE
);
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))
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))
103 /* The implementation of a concurrent hash map. */
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. */
112 /* Padding to make ccmap_impl exactly one cache line long. */
113 uint8_t pad
[CACHE_LINE_SIZE
- sizeof(unsigned int) * 6];
115 struct ccmap_bucket buckets
[];
117 BUILD_ASSERT_DECL(sizeof(struct ccmap_impl
) == CACHE_LINE_SIZE
);
119 static struct ccmap_impl
*ccmap_rehash(struct ccmap
*, uint32_t mask
);
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.) */
125 other_hash(uint32_t hash
)
127 return (hash
<< 16) | (hash
>> 16);
130 /* Returns the rehashed value for 'hash' within 'impl'. (See also "Hash
131 * Functions" at the top of this file.) */
133 rehash(const struct ccmap_impl
*impl
, uint32_t hash
)
135 return hash_finish(impl
->basis
, hash
);
138 static struct ccmap_impl
*
139 ccmap_get_impl(const struct ccmap
*ccmap
)
141 return ovsrcu_get(struct ccmap_impl
*, &ccmap
->impl
);
145 calc_max_n(uint32_t mask
)
147 return ((uint64_t) (mask
+ 1) * CCMAP_K
* CCMAP_MAX_LOAD
) >> 32;
151 calc_min_n(uint32_t mask
)
153 return ((uint64_t) (mask
+ 1) * CCMAP_K
* CCMAP_MIN_LOAD
) >> 32;
156 static struct ccmap_impl
*
157 ccmap_impl_create(uint32_t mask
)
159 struct ccmap_impl
*impl
;
161 ovs_assert(is_pow2(mask
+ 1));
163 impl
= xzalloc_cacheline(sizeof *impl
164 + (mask
+ 1) * sizeof *impl
->buckets
);
167 impl
->max_n
= calc_max_n(mask
);
168 impl
->min_n
= calc_min_n(mask
);
170 impl
->basis
= random_uint32();
175 /* Initializes 'ccmap' as an empty concurrent hash map. */
177 ccmap_init(struct ccmap
*ccmap
)
179 ovsrcu_set(&ccmap
->impl
, ccmap_impl_create(0));
184 * The client is responsible for destroying any data previously held in
187 ccmap_destroy(struct ccmap
*ccmap
)
190 ovsrcu_postpone(free_cacheline
, ccmap_get_impl(ccmap
));
194 /* Returns the number of hashes inserted in 'ccmap', including duplicates. */
196 ccmap_count(const struct ccmap
*ccmap
)
198 return ccmap_get_impl(ccmap
)->n
;
201 /* Returns true if 'ccmap' is empty, false otherwise. */
203 ccmap_is_empty(const struct ccmap
*ccmap
)
205 return ccmap_count(ccmap
) == 0;
208 /* returns 0 if not found. Map does not contain zero counts. */
210 ccmap_find_in_bucket(const struct ccmap_bucket
*bucket
, uint32_t hash
)
212 for (int i
= 0; i
< CCMAP_K
; i
++) {
213 uint64_t node
= ccmap_node_get(&bucket
->nodes
[i
]);
215 if (ccmap_node_hash(node
) == hash
) {
216 return ccmap_node_count(node
);
222 /* Searches 'ccmap' for a node with the specified 'hash'. If one is
223 * found, returns the count associated with it, otherwise zero.
226 ccmap_find(const struct ccmap
*ccmap
, uint32_t hash
)
228 const struct ccmap_impl
*impl
= ccmap_get_impl(ccmap
);
229 uint32_t h
= rehash(impl
, hash
);
232 count
= ccmap_find_in_bucket(&impl
->buckets
[h
& impl
->mask
], hash
);
235 count
= ccmap_find_in_bucket(&impl
->buckets
[h
& impl
->mask
], hash
);
241 ccmap_find_slot_protected(struct ccmap_bucket
*b
, uint32_t hash
,
244 for (int i
= 0; i
< CCMAP_K
; i
++) {
245 uint64_t node
= ccmap_node_get_protected(&b
->nodes
[i
]);
247 *count
= ccmap_node_count(node
);
248 if (ccmap_node_hash(node
) == hash
&& *count
) {
256 ccmap_find_empty_slot_protected(struct ccmap_bucket
*b
)
258 for (int i
= 0; i
< CCMAP_K
; i
++) {
259 uint64_t node
= ccmap_node_get_protected(&b
->nodes
[i
]);
261 if (!ccmap_node_count(node
)) {
269 ccmap_set_bucket(struct ccmap_bucket
*b
, int i
, uint32_t count
, uint32_t hash
)
271 ccmap_node_set_protected(&b
->nodes
[i
], ccmap_node(count
, hash
));
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
278 ccmap_inc_bucket_existing(struct ccmap_bucket
*b
, uint32_t hash
, uint32_t inc
)
282 int i
= ccmap_find_slot_protected(b
, hash
, &count
);
287 ccmap_set_bucket(b
, i
, count
, hash
);
291 /* Searches 'b' for an empty slot. If successful, stores 'inc' and 'hash' in
292 * the slot and returns 'inc'. Otherwise, returns 0. */
294 ccmap_inc_bucket_new(struct ccmap_bucket
*b
, uint32_t hash
, uint32_t inc
)
296 int i
= ccmap_find_empty_slot_protected(b
);
300 ccmap_set_bucket(b
, i
, inc
, hash
);
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 other_bucket_protected(struct ccmap_impl
*impl
, struct ccmap_bucket
*b
, int slot
)
309 uint64_t node
= ccmap_node_get_protected(&b
->nodes
[slot
]);
311 uint32_t h1
= rehash(impl
, ccmap_node_hash(node
));
312 uint32_t h2
= other_hash(h1
);
313 uint32_t b_idx
= b
- impl
->buckets
;
314 uint32_t other_h
= (h1
& impl
->mask
) == b_idx
? h2
: h1
;
316 return &impl
->buckets
[other_h
& impl
->mask
];
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'.
323 * Returns 'inc' if the new count for the 'hash' was inserted, otherwise
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
337 ccmap_inc_bfs(struct ccmap_impl
*impl
, uint32_t hash
,
338 struct ccmap_bucket
*b1
, struct ccmap_bucket
*b2
, uint32_t inc
)
340 enum { MAX_DEPTH
= 4 };
342 /* A path from 'start' to 'end' via the 'n' steps in 'slots[]'.
344 * One can follow the path via:
346 * struct ccmap_bucket *b;
350 * for (i = 0; i < path->n; i++) {
351 * b = other_bucket_protected(impl, b, path->slots[i]);
353 * ovs_assert(b == path->end);
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[]. */
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.
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
];
373 /* Add 'b1' and 'b2' as starting points for the search. */
374 queue
[head
].start
= b1
;
375 queue
[head
].end
= b1
;
379 queue
[head
].start
= b2
;
380 queue
[head
].end
= b2
;
385 while (tail
< head
) {
386 const struct ccmap_path
*path
= &queue
[tail
++];
387 struct ccmap_bucket
*this = path
->end
;
390 for (i
= 0; i
< CCMAP_K
; i
++) {
391 struct ccmap_bucket
*next
= other_bucket_protected(impl
, this, i
);
398 j
= ccmap_find_empty_slot_protected(next
);
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];
408 /* Figure out the full sequence of slots. */
409 for (k
= 0; k
< path
->n
; k
++) {
410 slots
[k
] = path
->slots
[k
];
413 slots
[path
->n
+ 1] = j
;
415 /* Figure out the full sequence of buckets. */
416 buckets
[0] = path
->start
;
417 for (k
= 0; k
<= path
->n
; k
++) {
418 buckets
[k
+ 1] = other_bucket_protected(impl
, buckets
[k
], slots
[k
]);
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.
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 for (k
= path
->n
+ 1; k
> 0; k
--) {
429 uint64_t node
= ccmap_node_get_protected
430 (&buckets
[k
- 1]->nodes
[slots
[k
- 1]]);
431 ccmap_node_set_protected(&buckets
[k
]->nodes
[slots
[k
]],
435 /* Finally, insert the count. */
436 ccmap_set_bucket(buckets
[0], slots
[0], inc
, hash
);
441 if (path
->n
< MAX_DEPTH
&& head
< MAX_QUEUE
) {
442 struct ccmap_path
*new_path
= &queue
[head
++];
445 new_path
->end
= next
;
446 new_path
->slots
[new_path
->n
++] = i
;
454 /* Increments the count associated with 'hash', in 'impl', by 'inc'. */
456 ccmap_try_inc(struct ccmap_impl
*impl
, uint32_t hash
, uint32_t inc
)
458 uint32_t h1
= rehash(impl
, hash
);
459 uint32_t h2
= other_hash(h1
);
460 struct ccmap_bucket
*b1
= &impl
->buckets
[h1
& impl
->mask
];
461 struct ccmap_bucket
*b2
= &impl
->buckets
[h2
& impl
->mask
];
464 return OVS_UNLIKELY(count
= ccmap_inc_bucket_existing(b1
, hash
, inc
))
465 ? count
: OVS_UNLIKELY(count
= ccmap_inc_bucket_existing(b2
, hash
, inc
))
466 ? count
: OVS_LIKELY(count
= ccmap_inc_bucket_new(b1
, hash
, inc
))
467 ? count
: OVS_LIKELY(count
= ccmap_inc_bucket_new(b2
, hash
, inc
))
468 ? count
: ccmap_inc_bfs(impl
, hash
, b1
, b2
, inc
);
471 /* Increments the count of 'hash' values in the 'ccmap'. The caller must
472 * ensure that 'ccmap' cannot change concurrently (from another thread).
474 * Returns the current count of the given hash value after the incremention. */
476 ccmap_inc(struct ccmap
*ccmap
, uint32_t hash
)
478 struct ccmap_impl
*impl
= ccmap_get_impl(ccmap
);
481 if (OVS_UNLIKELY(impl
->n_unique
>= impl
->max_n
)) {
482 COVERAGE_INC(ccmap_expand
);
483 impl
= ccmap_rehash(ccmap
, (impl
->mask
<< 1) | 1);
486 while (OVS_UNLIKELY(!(count
= ccmap_try_inc(impl
, hash
, 1)))) {
487 impl
= ccmap_rehash(ccmap
, impl
->mask
);
496 /* Decrement the count associated with 'hash' in the bucket identified by
497 * 'h'. Return the OLD count if successful, or 0. */
499 ccmap_dec__(struct ccmap_impl
*impl
, uint32_t hash
, uint32_t h
)
501 struct ccmap_bucket
*b
= &impl
->buckets
[h
& impl
->mask
];
504 int slot
= ccmap_find_slot_protected(b
, hash
, &count
);
509 ccmap_set_bucket(b
, slot
, count
- 1, hash
);
513 /* Decrements the count associated with 'hash'. The caller must
514 * ensure that 'ccmap' cannot change concurrently (from another thread).
516 * Returns the current count related to 'hash' in the ccmap after the
519 ccmap_dec(struct ccmap
*ccmap
, uint32_t hash
)
521 struct ccmap_impl
*impl
= ccmap_get_impl(ccmap
);
522 uint32_t h1
= rehash(impl
, hash
);
523 uint32_t h2
= other_hash(h1
);
525 uint32_t old_count
= ccmap_dec__(impl
, hash
, h1
);
527 old_count
= ccmap_dec__(impl
, hash
, h2
);
529 ovs_assert(old_count
);
533 if (old_count
== 0) {
535 if (OVS_UNLIKELY(impl
->n_unique
< impl
->min_n
)) {
536 COVERAGE_INC(ccmap_shrink
);
537 impl
= ccmap_rehash(ccmap
, impl
->mask
>> 1);
545 ccmap_try_rehash(const struct ccmap_impl
*old
, struct ccmap_impl
*new)
547 const struct ccmap_bucket
*b
;
549 for (b
= old
->buckets
; b
<= &old
->buckets
[old
->mask
]; b
++) {
550 for (int i
= 0; i
< CCMAP_K
; i
++) {
551 uint64_t node
= ccmap_node_get_protected(&b
->nodes
[i
]);
552 uint32_t count
= ccmap_node_count(node
);
554 if (count
&& !ccmap_try_inc(new, ccmap_node_hash(node
), count
)) {
562 static struct ccmap_impl
*
563 ccmap_rehash(struct ccmap
*ccmap
, uint32_t mask
)
565 struct ccmap_impl
*old
= ccmap_get_impl(ccmap
);
566 struct ccmap_impl
*new = ccmap_impl_create(mask
);
568 ovs_assert(old
->n_unique
< new->max_n
);
570 while (!ccmap_try_rehash(old
, new)) {
571 memset(new->buckets
, 0, (mask
+ 1) * sizeof *new->buckets
);
572 new->basis
= random_uint32();
576 new->n_unique
= old
->n_unique
;
577 ovsrcu_set(&ccmap
->impl
, new);
578 ovsrcu_postpone(free_cacheline
, old
);