]>
git.proxmox.com Git - mirror_ovs.git/blob - lib/cmap.h
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. */
91 void cmap_insert(struct cmap
*, struct cmap_node
*, uint32_t hash
);
92 void cmap_remove(struct cmap
*, struct cmap_node
*, uint32_t hash
);
93 void cmap_replace(struct cmap
*, struct cmap_node
*old_node
,
94 struct cmap_node
*new_node
, uint32_t hash
);
98 * These macros iterate NODE over all of the nodes in CMAP that have hash value
99 * equal to HASH. MEMBER must be the name of the 'struct cmap_node' member
102 * CMAP and HASH are evaluated only once. NODE is evaluated many times.
108 * CMAP_FOR_EACH_WITH_HASH will reliably visit each of the nodes with the
109 * specified hash in CMAP, even with concurrent insertions and deletions. (Of
110 * course, if nodes with the given HASH are being inserted or deleted, it might
111 * or might not visit the nodes actually being inserted or deleted.)
113 * CMAP_FOR_EACH_WITH_HASH_PROTECTED may only be used if CMAP is guaranteed not
114 * to change during iteration. It may be very slightly faster.
116 #define CMAP_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, CMAP) \
117 for (ASSIGN_CONTAINER(NODE, cmap_find(CMAP, HASH), MEMBER); \
118 (NODE) != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
119 ASSIGN_CONTAINER(NODE, cmap_node_next(&(NODE)->MEMBER), MEMBER))
120 #define CMAP_FOR_EACH_WITH_HASH_PROTECTED(NODE, MEMBER, HASH, CMAP) \
121 for (ASSIGN_CONTAINER(NODE, cmap_find_locked(CMAP, HASH), MEMBER); \
122 (NODE) != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
123 ASSIGN_CONTAINER(NODE, cmap_node_next_protected(&(NODE)->MEMBER), \
126 struct cmap_node
*cmap_find(const struct cmap
*, uint32_t hash
);
127 struct cmap_node
*cmap_find_protected(const struct cmap
*, uint32_t hash
);
135 * Iteration is safe even in a cmap that is changing concurrently. However:
137 * - In the presence of concurrent calls to cmap_insert(), any given
138 * iteration might skip some nodes and might visit some nodes more than
139 * once. If this is a problem, then the iterating code should lock the
140 * data structure (a rwlock can be used to allow multiple threads to
141 * iterate in parallel).
143 * - Concurrent calls to cmap_remove() don't have the same problem. (A
144 * node being deleted may be visited once or not at all. Other nodes
145 * will be visited once.)
152 * struct cmap_node cmap_node;
156 * struct cmap_cursor cursor;
157 * struct my_node *iter;
158 * struct cmap my_map;
162 * CMAP_FOR_EACH (my_node, cmap_node, &cursor, &cmap) {
163 * ...operate on my_node...
166 * CMAP_FOR_EACH_SAFE variant is useful only in deallocation code already
167 * executing at postponed time, when it is known that the RCU grace period
168 * has already expired.
171 #define CMAP_CURSOR_FOR_EACH(NODE, MEMBER, CURSOR, CMAP) \
172 for (*(CURSOR) = cmap_cursor_start(CMAP); \
174 ? (ASSIGN_CONTAINER(NODE, (CURSOR)->node, MEMBER), true) \
176 cmap_cursor_advance(CURSOR))
178 #define CMAP_CURSOR_FOR_EACH_SAFE(NODE, MEMBER, CURSOR, CMAP) \
179 for (*(CURSOR) = cmap_cursor_start(CMAP); \
181 ? (ASSIGN_CONTAINER(NODE, (CURSOR)->node, MEMBER), \
182 cmap_cursor_advance(CURSOR), \
187 #define CMAP_CURSOR_FOR_EACH_CONTINUE(NODE, MEMBER, CURSOR) \
188 for (cmap_cursor_advance(CURSOR); \
190 ? (ASSIGN_CONTAINER(NODE, (CURSOR)->node, MEMBER), true) \
192 cmap_cursor_advance(CURSOR))
195 const struct cmap_impl
*impl
;
198 struct cmap_node
*node
;
201 struct cmap_cursor
cmap_cursor_start(const struct cmap
*);
202 void cmap_cursor_advance(struct cmap_cursor
*);
204 #define CMAP_FOR_EACH(NODE, MEMBER, CMAP) \
205 for (struct cmap_cursor cursor__ = cmap_cursor_start(CMAP); \
207 ? (ASSIGN_CONTAINER(NODE, cursor__.node, MEMBER), true) \
209 cmap_cursor_advance(&cursor__))
211 #define CMAP_FOR_EACH_SAFE(NODE, MEMBER, CMAP) \
212 for (struct cmap_cursor cursor__ = cmap_cursor_start(CMAP); \
214 ? (ASSIGN_CONTAINER(NODE, cursor__.node, MEMBER), \
215 cmap_cursor_advance(&cursor__), \
220 static inline struct cmap_node
*cmap_first(const struct cmap
*);
222 /* Another, less preferred, form of iteration, for use in situations where it
223 * is difficult to maintain a pointer to a cmap_node. */
224 struct cmap_position
{
230 struct cmap_node
*cmap_next_position(const struct cmap
*,
231 struct cmap_position
*);
233 /* Returns the first node in 'cmap', in arbitrary order, or a null pointer if
234 * 'cmap' is empty. */
235 static inline struct cmap_node
*
236 cmap_first(const struct cmap
*cmap
)
238 struct cmap_position pos
= { 0, 0, 0 };
240 return cmap_next_position(cmap
, &pos
);