2 * Copyright (c) 2014 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.
25 /* Concurrent hash map
28 * A single-writer, multiple-reader hash table that efficiently supports
35 * The general rules are:
37 * - Only a single thread may safely call into cmap_insert(),
38 * cmap_remove(), or cmap_replace() at any given time.
40 * - Any number of threads may use functions and macros that search or
41 * iterate through a given cmap, even in parallel with other threads
42 * calling cmap_insert(), cmap_remove(), or cmap_replace().
44 * There is one exception: cmap_find_protected() is only safe if no thread
45 * is currently calling cmap_insert(), cmap_remove(), or cmap_replace().
46 * (Use ordinary cmap_find() if that is not guaranteed.)
48 * - See "Iteration" below for additional thread safety rules.
50 * Writers must use special care to ensure that any elements that they remove
51 * do not get freed or reused until readers have finished with them. This
52 * includes inserting the element back into its original cmap or a different
53 * one. One correct way to do this is to free them from an RCU callback with
57 /* A concurrent hash map node, to be embedded inside the data structure being
60 * All nodes linked together on a chain have exactly the same hash value. */
62 OVSRCU_TYPE(struct cmap_node *) next; /* Next node with same hash. */
65 static inline struct cmap_node *
66 cmap_node_next(const struct cmap_node *node)
68 return ovsrcu_get(struct cmap_node *, &node->next);
71 static inline struct cmap_node *
72 cmap_node_next_protected(const struct cmap_node *node)
74 return ovsrcu_get_protected(struct cmap_node *, &node->next);
77 /* Concurrent hash map. */
79 OVSRCU_TYPE(struct cmap_impl *) impl;
83 void cmap_init(struct cmap *);
84 void cmap_destroy(struct cmap *);
87 size_t cmap_count(const struct cmap *);
88 bool cmap_is_empty(const struct cmap *);
90 /* Insertion and deletion. Return the current count after the operation. */
91 size_t cmap_insert(struct cmap *, struct cmap_node *, uint32_t hash);
92 static inline size_t cmap_remove(struct cmap *, struct cmap_node *,
94 size_t cmap_replace(struct cmap *, struct cmap_node *old_node,
95 struct cmap_node *new_node, uint32_t hash);
99 * These macros iterate NODE over all of the nodes in CMAP that have hash value
100 * equal to HASH. MEMBER must be the name of the 'struct cmap_node' member
103 * CMAP and HASH are evaluated only once. NODE is evaluated many times.
109 * CMAP_NODE_FOR_EACH will reliably visit each of the nodes starting with
110 * CMAP_NODE, even with concurrent insertions and deletions. (Of
111 * course, if nodes are being inserted or deleted, it might or might not visit
112 * the nodes actually being inserted or deleted.)
114 * CMAP_NODE_FOR_EACH_PROTECTED may only be used if the containing CMAP is
115 * guaranteed not to change during iteration. It may be only slightly faster.
117 * CMAP_FOR_EACH_WITH_HASH will reliably visit each of the nodes with the
118 * specified hash in CMAP, even with concurrent insertions and deletions. (Of
119 * course, if nodes with the given HASH are being inserted or deleted, it might
120 * or might not visit the nodes actually being inserted or deleted.)
122 * CMAP_FOR_EACH_WITH_HASH_PROTECTED may only be used if CMAP is guaranteed not
123 * to change during iteration. It may be very slightly faster.
125 #define CMAP_NODE_FOR_EACH(NODE, MEMBER, CMAP_NODE) \
126 for (INIT_CONTAINER(NODE, CMAP_NODE, MEMBER); \
127 (NODE) != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
128 ASSIGN_CONTAINER(NODE, cmap_node_next(&(NODE)->MEMBER), MEMBER))
129 #define CMAP_NODE_FOR_EACH_PROTECTED(NODE, MEMBER, CMAP_NODE) \
130 for (INIT_CONTAINER(NODE, CMAP_NODE, MEMBER); \
131 (NODE) != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
132 ASSIGN_CONTAINER(NODE, cmap_node_next_protected(&(NODE)->MEMBER), \
134 #define CMAP_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, CMAP) \
135 CMAP_NODE_FOR_EACH(NODE, MEMBER, cmap_find(CMAP, HASH))
136 #define CMAP_FOR_EACH_WITH_HASH_PROTECTED(NODE, MEMBER, HASH, CMAP) \
137 CMAP_NODE_FOR_EACH_PROTECTED(NODE, MEMBER, cmap_find_locked(CMAP, HASH))
139 const struct cmap_node *cmap_find(const struct cmap *, uint32_t hash);
140 struct cmap_node *cmap_find_protected(const struct cmap *, uint32_t hash);
142 /* Looks up multiple 'hashes', when the corresponding bit in 'map' is 1,
143 * and sets the corresponding pointer in 'nodes', if the hash value was
144 * found from the 'cmap'. In other cases the 'nodes' values are not changed,
145 * i.e., no NULL pointers are stored there.
146 * Returns a map where a bit is set to 1 if the corresponding 'nodes' pointer
147 * was stored, 0 otherwise.
148 * Generally, the caller wants to use CMAP_NODE_FOR_EACH to verify for
149 * hash collisions. */
150 unsigned long cmap_find_batch(const struct cmap *cmap, unsigned long map,
152 const struct cmap_node *nodes[]);
160 * Iteration is safe even in a cmap that is changing concurrently. However:
162 * - In the presence of concurrent calls to cmap_insert(), any given
163 * iteration might skip some nodes and might visit some nodes more than
164 * once. If this is a problem, then the iterating code should lock the
165 * data structure (a rwlock can be used to allow multiple threads to
166 * iterate in parallel).
168 * - Concurrent calls to cmap_remove() don't have the same problem. (A
169 * node being deleted may be visited once or not at all. Other nodes
170 * will be visited once.)
177 * struct cmap_node cmap_node;
181 * struct cmap_cursor cursor;
182 * struct my_node *iter;
183 * struct cmap my_map;
187 * CMAP_FOR_EACH (my_node, cmap_node, &cursor, &cmap) {
188 * ...operate on my_node...
191 * CMAP_FOR_EACH is "safe" in the sense of HMAP_FOR_EACH_SAFE. That is, it is
192 * safe to free the current node before going on to the next iteration. Most
193 * of the time, though, this doesn't matter for a cmap because node
194 * deallocation has to be postponed until the next grace period. This means
195 * that this guarantee is useful only in deallocation code already executing at
196 * postponed time, when it is known that the RCU grace period has already
200 #define CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER) \
202 ? (INIT_CONTAINER(NODE, (CURSOR)->node, MEMBER), \
203 cmap_cursor_advance(CURSOR), \
207 #define CMAP_CURSOR_FOR_EACH(NODE, MEMBER, CURSOR, CMAP) \
208 for (*(CURSOR) = cmap_cursor_start(CMAP); \
209 CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER); \
212 #define CMAP_CURSOR_FOR_EACH_CONTINUE(NODE, MEMBER, CURSOR) \
213 while (CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER))
216 const struct cmap_impl *impl;
219 struct cmap_node *node;
222 struct cmap_cursor cmap_cursor_start(const struct cmap *);
223 void cmap_cursor_advance(struct cmap_cursor *);
225 #define CMAP_FOR_EACH(NODE, MEMBER, CMAP) \
226 for (struct cmap_cursor cursor__ = cmap_cursor_start(CMAP); \
227 CMAP_CURSOR_FOR_EACH__(NODE, &cursor__, MEMBER); \
230 static inline struct cmap_node *cmap_first(const struct cmap *);
232 /* Another, less preferred, form of iteration, for use in situations where it
233 * is difficult to maintain a pointer to a cmap_node. */
234 struct cmap_position {
240 struct cmap_node *cmap_next_position(const struct cmap *,
241 struct cmap_position *);
243 /* Returns the first node in 'cmap', in arbitrary order, or a null pointer if
244 * 'cmap' is empty. */
245 static inline struct cmap_node *
246 cmap_first(const struct cmap *cmap)
248 struct cmap_position pos = { 0, 0, 0 };
250 return cmap_next_position(cmap, &pos);
253 /* Removes 'node' from 'cmap'. The caller must ensure that 'cmap' cannot
254 * change concurrently (from another thread).
256 * 'node' must not be destroyed or modified or inserted back into 'cmap' or
257 * into any other concurrent hash map while any other thread might be accessing
258 * it. One correct way to do this is to free it from an RCU callback with
261 * Returns the current number of nodes in the cmap after the removal. */
263 cmap_remove(struct cmap *cmap, struct cmap_node *node, uint32_t hash)
265 return cmap_replace(cmap, node, NULL, hash);