]>
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 PADDED_MEMBERS(CACHE_LINE_SIZE
,
106 unsigned int n_unique
; /* Number of in-use nodes. */
107 unsigned int n
; /* Number of hashes inserted. */
108 unsigned int max_n
; /* Max nodes before enlarging. */
109 unsigned int min_n
; /* Min nodes before shrinking. */
110 uint32_t mask
; /* Number of 'buckets', minus one. */
111 uint32_t basis
; /* Basis for rehashing client's
114 struct ccmap_bucket buckets
[];
116 BUILD_ASSERT_DECL(sizeof(struct ccmap_impl
) == CACHE_LINE_SIZE
);
118 static struct ccmap_impl
*ccmap_rehash(struct ccmap
*, uint32_t mask
);
120 /* Given a rehashed value 'hash', returns the other hash for that rehashed
121 * value. This is symmetric: other_hash(other_hash(x)) == x. (See also "Hash
122 * Functions" at the top of cmap.c.) */
124 other_hash(uint32_t hash
)
126 return (hash
<< 16) | (hash
>> 16);
129 /* Returns the rehashed value for 'hash' within 'impl'. (See also "Hash
130 * Functions" at the top of this file.) */
132 rehash(const struct ccmap_impl
*impl
, uint32_t hash
)
134 return hash_finish(impl
->basis
, hash
);
137 static struct ccmap_impl
*
138 ccmap_get_impl(const struct ccmap
*ccmap
)
140 return ovsrcu_get(struct ccmap_impl
*, &ccmap
->impl
);
144 calc_max_n(uint32_t mask
)
146 return ((uint64_t) (mask
+ 1) * CCMAP_K
* CCMAP_MAX_LOAD
) >> 32;
150 calc_min_n(uint32_t mask
)
152 return ((uint64_t) (mask
+ 1) * CCMAP_K
* CCMAP_MIN_LOAD
) >> 32;
155 static struct ccmap_impl
*
156 ccmap_impl_create(uint32_t mask
)
158 struct ccmap_impl
*impl
;
160 ovs_assert(is_pow2(mask
+ 1));
162 impl
= xzalloc_cacheline(sizeof *impl
163 + (mask
+ 1) * sizeof *impl
->buckets
);
166 impl
->max_n
= calc_max_n(mask
);
167 impl
->min_n
= calc_min_n(mask
);
169 impl
->basis
= random_uint32();
174 /* Initializes 'ccmap' as an empty concurrent hash map. */
176 ccmap_init(struct ccmap
*ccmap
)
178 ovsrcu_set(&ccmap
->impl
, ccmap_impl_create(0));
183 * The client is responsible for destroying any data previously held in
186 ccmap_destroy(struct ccmap
*ccmap
)
189 ovsrcu_postpone(free_cacheline
, ccmap_get_impl(ccmap
));
193 /* Returns the number of hashes inserted in 'ccmap', including duplicates. */
195 ccmap_count(const struct ccmap
*ccmap
)
197 return ccmap_get_impl(ccmap
)->n
;
200 /* Returns true if 'ccmap' is empty, false otherwise. */
202 ccmap_is_empty(const struct ccmap
*ccmap
)
204 return ccmap_count(ccmap
) == 0;
207 /* returns 0 if not found. Map does not contain zero counts. */
209 ccmap_find_in_bucket(const struct ccmap_bucket
*bucket
, uint32_t hash
)
211 for (int i
= 0; i
< CCMAP_K
; i
++) {
212 uint64_t node
= ccmap_node_get(&bucket
->nodes
[i
]);
214 if (ccmap_node_hash(node
) == hash
) {
215 return ccmap_node_count(node
);
221 /* Searches 'ccmap' for a node with the specified 'hash'. If one is
222 * found, returns the count associated with it, otherwise zero.
225 ccmap_find(const struct ccmap
*ccmap
, uint32_t hash
)
227 const struct ccmap_impl
*impl
= ccmap_get_impl(ccmap
);
228 uint32_t h
= rehash(impl
, hash
);
231 count
= ccmap_find_in_bucket(&impl
->buckets
[h
& impl
->mask
], hash
);
234 count
= ccmap_find_in_bucket(&impl
->buckets
[h
& impl
->mask
], hash
);
240 ccmap_find_slot_protected(struct ccmap_bucket
*b
, uint32_t hash
,
243 for (int i
= 0; i
< CCMAP_K
; i
++) {
244 uint64_t node
= ccmap_node_get_protected(&b
->nodes
[i
]);
246 *count
= ccmap_node_count(node
);
247 if (ccmap_node_hash(node
) == hash
&& *count
) {
255 ccmap_find_empty_slot_protected(struct ccmap_bucket
*b
)
257 for (int i
= 0; i
< CCMAP_K
; i
++) {
258 uint64_t node
= ccmap_node_get_protected(&b
->nodes
[i
]);
260 if (!ccmap_node_count(node
)) {
268 ccmap_set_bucket(struct ccmap_bucket
*b
, int i
, uint32_t count
, uint32_t hash
)
270 ccmap_node_set_protected(&b
->nodes
[i
], ccmap_node(count
, hash
));
273 /* Searches 'b' for a node with the given 'hash'. If it finds one, increments
274 * the associated count by 'inc' and returns the new value. Otherwise returns
277 ccmap_inc_bucket_existing(struct ccmap_bucket
*b
, uint32_t hash
, uint32_t inc
)
281 int i
= ccmap_find_slot_protected(b
, hash
, &count
);
286 ccmap_set_bucket(b
, i
, count
, hash
);
290 /* Searches 'b' for an empty slot. If successful, stores 'inc' and 'hash' in
291 * the slot and returns 'inc'. Otherwise, returns 0. */
293 ccmap_inc_bucket_new(struct ccmap_bucket
*b
, uint32_t hash
, uint32_t inc
)
295 int i
= ccmap_find_empty_slot_protected(b
);
299 ccmap_set_bucket(b
, i
, inc
, hash
);
303 /* Returns the other bucket that b->nodes[slot] could occupy in 'impl'. (This
304 * might be the same as 'b'.) */
305 static struct ccmap_bucket
*
306 other_bucket_protected(struct ccmap_impl
*impl
, struct ccmap_bucket
*b
, int slot
)
308 uint64_t node
= ccmap_node_get_protected(&b
->nodes
[slot
]);
310 uint32_t h1
= rehash(impl
, ccmap_node_hash(node
));
311 uint32_t h2
= other_hash(h1
);
312 uint32_t b_idx
= b
- impl
->buckets
;
313 uint32_t other_h
= (h1
& impl
->mask
) == b_idx
? h2
: h1
;
315 return &impl
->buckets
[other_h
& impl
->mask
];
318 /* Count 'inc' for 'hash' is to be inserted into 'impl', but both candidate
319 * buckets 'b1' and 'b2' are full. This function attempts to rearrange buckets
320 * within 'impl' to make room for 'hash'.
322 * Returns 'inc' if the new count for the 'hash' was inserted, otherwise
325 * The implementation is a general-purpose breadth-first search. At first
326 * glance, this is more complex than a random walk through 'impl' (suggested by
327 * some references), but random walks have a tendency to loop back through a
328 * single bucket. We have to move nodes backward along the path that we find,
329 * so that no node actually disappears from the hash table, which means a
330 * random walk would have to be careful to deal with loops. By contrast, a
331 * successful breadth-first search always finds a *shortest* path through the
332 * hash table, and a shortest path will never contain loops, so it avoids that
336 ccmap_inc_bfs(struct ccmap_impl
*impl
, uint32_t hash
,
337 struct ccmap_bucket
*b1
, struct ccmap_bucket
*b2
, uint32_t inc
)
339 enum { MAX_DEPTH
= 4 };
341 /* A path from 'start' to 'end' via the 'n' steps in 'slots[]'.
343 * One can follow the path via:
345 * struct ccmap_bucket *b;
349 * for (i = 0; i < path->n; i++) {
350 * b = other_bucket_protected(impl, b, path->slots[i]);
352 * ovs_assert(b == path->end);
355 struct ccmap_bucket
*start
; /* First bucket along the path. */
356 struct ccmap_bucket
*end
; /* Last bucket on the path. */
357 uint8_t slots
[MAX_DEPTH
]; /* Slots used for each hop. */
358 int n
; /* Number of slots[]. */
361 /* We need to limit the amount of work we do trying to find a path. It
362 * might actually be impossible to rearrange the ccmap, and after some time
363 * it is likely to be easier to rehash the entire ccmap.
365 * This value of MAX_QUEUE is an arbitrary limit suggested by one of the
366 * references. Empirically, it seems to work OK. */
367 enum { MAX_QUEUE
= 500 };
368 struct ccmap_path queue
[MAX_QUEUE
];
372 /* Add 'b1' and 'b2' as starting points for the search. */
373 queue
[head
].start
= b1
;
374 queue
[head
].end
= b1
;
378 queue
[head
].start
= b2
;
379 queue
[head
].end
= b2
;
384 while (tail
< head
) {
385 const struct ccmap_path
*path
= &queue
[tail
++];
386 struct ccmap_bucket
*this = path
->end
;
389 for (i
= 0; i
< CCMAP_K
; i
++) {
390 struct ccmap_bucket
*next
= other_bucket_protected(impl
, this, i
);
397 j
= ccmap_find_empty_slot_protected(next
);
399 /* We've found a path along which we can rearrange the hash
400 * table: Start at path->start, follow all the slots in
401 * path->slots[], then follow slot 'i', then the bucket you
402 * arrive at has slot 'j' empty. */
403 struct ccmap_bucket
*buckets
[MAX_DEPTH
+ 2];
404 int slots
[MAX_DEPTH
+ 2];
407 /* Figure out the full sequence of slots. */
408 for (k
= 0; k
< path
->n
; k
++) {
409 slots
[k
] = path
->slots
[k
];
412 slots
[path
->n
+ 1] = j
;
414 /* Figure out the full sequence of buckets. */
415 buckets
[0] = path
->start
;
416 for (k
= 0; k
<= path
->n
; k
++) {
417 buckets
[k
+ 1] = other_bucket_protected(impl
, buckets
[k
], slots
[k
]);
420 /* Now the path is fully expressed. One can start from
421 * buckets[0], go via slots[0] to buckets[1], via slots[1] to
422 * buckets[2], and so on.
424 * Move all the nodes across the path "backward". After each
425 * step some node appears in two buckets. Thus, every node is
426 * always visible to a concurrent search. */
427 for (k
= path
->n
+ 1; k
> 0; k
--) {
428 uint64_t node
= ccmap_node_get_protected
429 (&buckets
[k
- 1]->nodes
[slots
[k
- 1]]);
430 ccmap_node_set_protected(&buckets
[k
]->nodes
[slots
[k
]],
434 /* Finally, insert the count. */
435 ccmap_set_bucket(buckets
[0], slots
[0], inc
, hash
);
440 if (path
->n
< MAX_DEPTH
&& head
< MAX_QUEUE
) {
441 struct ccmap_path
*new_path
= &queue
[head
++];
444 new_path
->end
= next
;
445 new_path
->slots
[new_path
->n
++] = i
;
453 /* Increments the count associated with 'hash', in 'impl', by 'inc'. */
455 ccmap_try_inc(struct ccmap_impl
*impl
, uint32_t hash
, uint32_t inc
)
457 uint32_t h1
= rehash(impl
, hash
);
458 uint32_t h2
= other_hash(h1
);
459 struct ccmap_bucket
*b1
= &impl
->buckets
[h1
& impl
->mask
];
460 struct ccmap_bucket
*b2
= &impl
->buckets
[h2
& impl
->mask
];
463 return OVS_UNLIKELY(count
= ccmap_inc_bucket_existing(b1
, hash
, inc
))
464 ? count
: OVS_UNLIKELY(count
= ccmap_inc_bucket_existing(b2
, hash
, inc
))
465 ? count
: OVS_LIKELY(count
= ccmap_inc_bucket_new(b1
, hash
, inc
))
466 ? count
: OVS_LIKELY(count
= ccmap_inc_bucket_new(b2
, hash
, inc
))
467 ? count
: ccmap_inc_bfs(impl
, hash
, b1
, b2
, inc
);
470 /* Increments the count of 'hash' values in the 'ccmap'. The caller must
471 * ensure that 'ccmap' cannot change concurrently (from another thread).
473 * Returns the current count of the given hash value after the incremention. */
475 ccmap_inc(struct ccmap
*ccmap
, uint32_t hash
)
477 struct ccmap_impl
*impl
= ccmap_get_impl(ccmap
);
480 if (OVS_UNLIKELY(impl
->n_unique
>= impl
->max_n
)) {
481 COVERAGE_INC(ccmap_expand
);
482 impl
= ccmap_rehash(ccmap
, (impl
->mask
<< 1) | 1);
485 while (OVS_UNLIKELY(!(count
= ccmap_try_inc(impl
, hash
, 1)))) {
486 impl
= ccmap_rehash(ccmap
, impl
->mask
);
495 /* Decrement the count associated with 'hash' in the bucket identified by
496 * 'h'. Return the OLD count if successful, or 0. */
498 ccmap_dec__(struct ccmap_impl
*impl
, uint32_t hash
, uint32_t h
)
500 struct ccmap_bucket
*b
= &impl
->buckets
[h
& impl
->mask
];
503 int slot
= ccmap_find_slot_protected(b
, hash
, &count
);
508 ccmap_set_bucket(b
, slot
, count
- 1, hash
);
512 /* Decrements the count associated with 'hash'. The caller must
513 * ensure that 'ccmap' cannot change concurrently (from another thread).
515 * Returns the current count related to 'hash' in the ccmap after the
518 ccmap_dec(struct ccmap
*ccmap
, uint32_t hash
)
520 struct ccmap_impl
*impl
= ccmap_get_impl(ccmap
);
521 uint32_t h1
= rehash(impl
, hash
);
522 uint32_t h2
= other_hash(h1
);
524 uint32_t old_count
= ccmap_dec__(impl
, hash
, h1
);
526 old_count
= ccmap_dec__(impl
, hash
, h2
);
528 ovs_assert(old_count
);
532 if (old_count
== 0) {
534 if (OVS_UNLIKELY(impl
->n_unique
< impl
->min_n
)) {
535 COVERAGE_INC(ccmap_shrink
);
536 impl
= ccmap_rehash(ccmap
, impl
->mask
>> 1);
544 ccmap_try_rehash(const struct ccmap_impl
*old
, struct ccmap_impl
*new)
546 const struct ccmap_bucket
*b
;
548 for (b
= old
->buckets
; b
<= &old
->buckets
[old
->mask
]; b
++) {
549 for (int i
= 0; i
< CCMAP_K
; i
++) {
550 uint64_t node
= ccmap_node_get_protected(&b
->nodes
[i
]);
551 uint32_t count
= ccmap_node_count(node
);
553 if (count
&& !ccmap_try_inc(new, ccmap_node_hash(node
), count
)) {
561 static struct ccmap_impl
*
562 ccmap_rehash(struct ccmap
*ccmap
, uint32_t mask
)
564 struct ccmap_impl
*old
= ccmap_get_impl(ccmap
);
565 struct ccmap_impl
*new = ccmap_impl_create(mask
);
567 ovs_assert(old
->n_unique
< new->max_n
);
569 while (!ccmap_try_rehash(old
, new)) {
570 memset(new->buckets
, 0, (mask
+ 1) * sizeof *new->buckets
);
571 new->basis
= random_uint32();
575 new->n_unique
= old
->n_unique
;
576 ovsrcu_set(&ccmap
->impl
, new);
577 ovsrcu_postpone(free_cacheline
, old
);