/src/openvswitch/lib/cmap.h

Source (jump to first uncovered line)
/*
 * Copyright (c) 2014, 2016 Nicira, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef CMAP_H
#define CMAP_H 1

#include <stdbool.h>
#include <stdint.h>
#include "ovs-rcu.h"
#include "util.h"

/* Concurrent hash map
 * ===================
 *
 * A single-writer, multiple-reader hash table that efficiently supports
 * duplicates.
 *
 *
 * Thread-safety
 * =============
 *
 * The general rules are:
 *
 *    - Only a single thread may safely call into cmap_insert(),
 *      cmap_remove(), or cmap_replace() at any given time.
 *
 *    - Any number of threads may use functions and macros that search or
 *      iterate through a given cmap, even in parallel with other threads
 *      calling cmap_insert(), cmap_remove(), or cmap_replace().
 *
 *      There is one exception: cmap_find_protected() is only safe if no thread
 *      is currently calling cmap_insert(), cmap_remove(), or cmap_replace().
 *      (Use ordinary cmap_find() if that is not guaranteed.)
 *
 *    - See "Iteration" below for additional thread safety rules.
 *
 * Writers must use special care to ensure that any elements that they remove
 * do not get freed or reused until readers have finished with them.  This
 * includes inserting the element back into its original cmap or a different
 * one.  One correct way to do this is to free them from an RCU callback with
 * ovsrcu_postpone().
 */

/* A concurrent hash map node, to be embedded inside the data structure being
 * mapped.
 *
 * All nodes linked together on a chain have exactly the same hash value. */
struct cmap_node {
    OVSRCU_TYPE(struct cmap_node *) next; /* Next node with same hash. */
};

static inline struct cmap_node *
cmap_node_next(const struct cmap_node *node)
{
    return ovsrcu_get(struct cmap_node *, &node->next);
}

static inline struct cmap_node *
cmap_node_next_protected(const struct cmap_node *node)
{
    return ovsrcu_get_protected(struct cmap_node *, &node->next);
}

/* Concurrent hash map. */
struct cmap {
    OVSRCU_TYPE(struct cmap_impl *) impl;
};

/* Initializer for an empty cmap. */
#define CMAP_INITIALIZER {                                              \
        .impl = OVSRCU_INITIALIZER((struct cmap_impl *) &empty_cmap)    \
    }
extern OVS_ALIGNED_VAR(CACHE_LINE_SIZE) const struct cmap_impl empty_cmap;

/* Initialization. */
void cmap_init(struct cmap *);
void cmap_destroy(struct cmap *);

/* Count. */
size_t cmap_count(const struct cmap *);
bool cmap_is_empty(const struct cmap *);

/* Insertion and deletion.  Return the current count after the operation. */
size_t cmap_insert(struct cmap *, struct cmap_node *, uint32_t hash);
static inline size_t cmap_remove(struct cmap *, struct cmap_node *,
                                 uint32_t hash);
size_t cmap_replace(struct cmap *, struct cmap_node *old_node,
                    struct cmap_node *new_node, uint32_t hash);

/* Search.
 *
 * These macros iterate NODE over all of the nodes in CMAP that have hash value
 * equal to HASH.  MEMBER must be the name of the 'struct cmap_node' member
 * within NODE.
 *
 * CMAP and HASH are evaluated only once.  NODE is evaluated many times.
 *
 * After a normal exit of the loop (not through a "break;" statement) NODE is
 * NULL.
 *
 * Thread-safety
 * =============
 *
 * CMAP_NODE_FOR_EACH will reliably visit each of the nodes starting with
 * CMAP_NODE, even with concurrent insertions and deletions.  (Of
 * course, if nodes are being inserted or deleted, it might or might not visit
 * the nodes actually being inserted or deleted.)
 *
 * CMAP_NODE_FOR_EACH_PROTECTED may only be used if the containing CMAP is
 * guaranteed not to change during iteration.  It may be only slightly faster.
 *
 * CMAP_FOR_EACH_WITH_HASH will reliably visit each of the nodes with the
 * specified hash in CMAP, even with concurrent insertions and deletions.  (Of
 * course, if nodes with the given HASH are being inserted or deleted, it might
 * or might not visit the nodes actually being inserted or deleted.)
 *
 * CMAP_FOR_EACH_WITH_HASH_PROTECTED may only be used if CMAP is guaranteed not
 * to change during iteration.  It may be very slightly faster.
 */
#define CMAP_NODE_FOR_EACH(NODE, MEMBER, CMAP_NODE)                        \
    for (INIT_MULTIVAR(NODE, MEMBER, CMAP_NODE, struct cmap_node);         \
         CONDITION_MULTIVAR(NODE, MEMBER, ITER_VAR(NODE) != NULL);         \
         UPDATE_MULTIVAR(NODE, cmap_node_next(ITER_VAR(NODE))))
#define CMAP_NODE_FOR_EACH_PROTECTED(NODE, MEMBER, CMAP_NODE)              \
    for (INIT_MULTIVAR(NODE, MEMBER, CMAP_NODE, struct cmap_node);         \
         CONDITION_MULTIVAR(NODE, MEMBER, ITER_VAR(NODE) != NULL);         \
         UPDATE_MULTIVAR(NODE, cmap_node_next_protected(ITER_VAR(NODE))))

#define CMAP_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, CMAP)   \
    CMAP_NODE_FOR_EACH(NODE, MEMBER, cmap_find(CMAP, HASH))
#define CMAP_FOR_EACH_WITH_HASH_PROTECTED(NODE, MEMBER, HASH, CMAP)     \
    CMAP_NODE_FOR_EACH_PROTECTED(NODE, MEMBER, cmap_find_protected(CMAP, HASH))

const struct cmap_node *cmap_find(const struct cmap *, uint32_t hash);
struct cmap_node *cmap_find_protected(const struct cmap *, uint32_t hash);

/* Find node by index or find index by hash. The 'index' of a cmap entry is a
 * way to combine the specific bucket and the entry of the bucket into a
 * convenient single integer value. In other words, it is the index of the
 * entry and each entry has an unique index. It is not used internally by
 * cmap.
 * Currently the functions assume index will not be larger than uint32_t. In
 * OvS table size is usually much smaller than this size.*/
const struct cmap_node * cmap_find_by_index(const struct cmap *,
                                            uint32_t index);
uint32_t cmap_find_index(const struct cmap *, uint32_t hash);

/* Looks up multiple 'hashes', when the corresponding bit in 'map' is 1,
 * and sets the corresponding pointer in 'nodes', if the hash value was
 * found from the 'cmap'.  In other cases the 'nodes' values are not changed,
 * i.e., no NULL pointers are stored there.
 * Returns a map where a bit is set to 1 if the corresponding 'nodes' pointer
 * was stored, 0 otherwise.
 * Generally, the caller wants to use CMAP_NODE_FOR_EACH to verify for
 * hash collisions. */
unsigned long cmap_find_batch(const struct cmap *cmap, unsigned long map,
                              uint32_t hashes[],
                              const struct cmap_node *nodes[]);

/* Iteration.
 *
 *
 * Thread-safety
 * =============
 *
 * Iteration is safe even in a cmap that is changing concurrently.  However:
 *
 *     - In the presence of concurrent calls to cmap_insert(), any given
 *       iteration might skip some nodes and might visit some nodes more than
 *       once.  If this is a problem, then the iterating code should lock the
 *       data structure (a rwlock can be used to allow multiple threads to
 *       iterate in parallel).
 *
 *     - Concurrent calls to cmap_remove() don't have the same problem.  (A
 *       node being deleted may be visited once or not at all.  Other nodes
 *       will be visited once.)
 *
 *     - If the cmap is changing, it is not safe to quiesce while iterating.
 *       Even if the changes are done by the same thread that's performing the
 *       iteration (Corollary: it is not safe to call cmap_remove() and quiesce
 *       in the loop body).
 *
 *
 * Example
 * =======
 *
 *     struct my_node {
 *         struct cmap_node cmap_node;
 *         int extra_data;
 *     };
 *
 *     struct cmap my_map;
 *     struct my_node *my_node;
 *
 *     cmap_init(&my_map);
 *     ...add data...
 *     CMAP_FOR_EACH (my_node, cmap_node, &my_map) {
 *         ...operate on my_node...
 *     }
 *
 * CMAP_FOR_EACH is "safe" in the sense of HMAP_FOR_EACH_SAFE.  That is, it is
 * safe to free the current node before going on to the next iteration.  Most
 * of the time, though, this doesn't matter for a cmap because node
 * deallocation has to be postponed until the next grace period.  This means
 * that this guarantee is useful only in deallocation code already executing at
 * postponed time, when it is known that the RCU grace period has already
 * expired.
 */

#define CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER)    \
    ((CURSOR)->node                                     \
     ? (INIT_CONTAINER(NODE, (CURSOR)->node, MEMBER),   \
        cmap_cursor_advance(CURSOR),                    \
        true)                                           \
     : (NODE = NULL, false))

#define CMAP_CURSOR_FOR_EACH(NODE, MEMBER, CURSOR, CMAP)    \
    for (*(CURSOR) = cmap_cursor_start(CMAP);               \
         CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER);      \
        )

#define CMAP_CURSOR_FOR_EACH_CONTINUE(NODE, MEMBER, CURSOR)   \
    while (CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER))

struct cmap_cursor {
    const struct cmap_impl *impl;
    uint32_t bucket_idx;
    int entry_idx;
    struct cmap_node *node;
};

struct cmap_cursor cmap_cursor_start(const struct cmap *);
void cmap_cursor_advance(struct cmap_cursor *);

/* Generate a unique name for the cursor with the __COUNTER__ macro to
 * allow nesting of CMAP_FOR_EACH loops. */
#define CMAP_FOR_EACH__(NODE, MEMBER, CMAP, CURSOR_NAME)           \
    for (struct cmap_cursor CURSOR_NAME = cmap_cursor_start(CMAP); \
         CMAP_CURSOR_FOR_EACH__(NODE, &CURSOR_NAME, MEMBER);       \
        )

#define CMAP_FOR_EACH(NODE, MEMBER, CMAP) \
          CMAP_FOR_EACH__(NODE, MEMBER, CMAP, \
                OVS_JOIN(cursor_, __COUNTER__))

static inline struct cmap_node *cmap_first(const struct cmap *);

/* Another, less preferred, form of iteration, for use in situations where it
 * is difficult to maintain a pointer to a cmap_node. */
struct cmap_position {
    unsigned int bucket;
    unsigned int entry;
    unsigned int offset;
};

struct cmap_node *cmap_next_position(const struct cmap *,
                                     struct cmap_position *);

/* Returns the first node in 'cmap', in arbitrary order, or a null pointer if
 * 'cmap' is empty. */
static inline struct cmap_node *
cmap_first(const struct cmap *cmap)
{
    struct cmap_position pos = { 0, 0, 0 };

    return cmap_next_position(cmap, &pos);
}

/* Removes 'node' from 'cmap'.  The caller must ensure that 'cmap' cannot
 * change concurrently (from another thread).
 *
 * 'node' must not be destroyed or modified or inserted back into 'cmap' or
 * into any other concurrent hash map while any other thread might be accessing
 * it.  One correct way to do this is to free it from an RCU callback with
 * ovsrcu_postpone().
 *
 * Returns the current number of nodes in the cmap after the removal. */
static inline size_t
cmap_remove(struct cmap *cmap, struct cmap_node *node, uint32_t hash)
{
    return cmap_replace(cmap, node, NULL, hash);
}

#endif /* cmap.h */

Coverage Report

Created: 2025-07-01 06:50

Line	Count	Source (jump to first uncovered line)
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		#ifndef CMAP_H
18		#define CMAP_H 1
19
20		#include <stdbool.h>
21		#include <stdint.h>
22		#include "ovs-rcu.h"
23		#include "util.h"
24
25		/* Concurrent hash map
26		* ===================
27		*
28		* A single-writer, multiple-reader hash table that efficiently supports
29		* duplicates.
30		*
31		*
32		* Thread-safety
33		* =============
34		*
35		* The general rules are:
36		*
37		* - Only a single thread may safely call into cmap_insert(),
38		* cmap_remove(), or cmap_replace() at any given time.
39		*
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().
43		*
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.)
47		*
48		* - See "Iteration" below for additional thread safety rules.
49		*
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
54		* ovsrcu_postpone().
55		*/
56
57		/* A concurrent hash map node, to be embedded inside the data structure being
58		* mapped.
59		*
60		* All nodes linked together on a chain have exactly the same hash value. */
61		struct cmap_node {
62		OVSRCU_TYPE(struct cmap_node ) next; / Next node with same hash. */
63		};
64
65		static inline struct cmap_node *
66		cmap_node_next(const struct cmap_node *node)
67	0	{
68	0	return ovsrcu_get(struct cmap_node *, &node->next);
69	0	} Unexecuted instantiation: ofctl_parse_target.c:cmap_node_next Unexecuted instantiation: ofp-util.c:cmap_node_next Unexecuted instantiation: meta-flow.c:cmap_node_next Unexecuted instantiation: netdev.c:cmap_node_next Unexecuted instantiation: nx-match.c:cmap_node_next Unexecuted instantiation: ofp-actions.c:cmap_node_next Unexecuted instantiation: ovs-router.c:cmap_node_next Unexecuted instantiation: tnl-ports.c:cmap_node_next Unexecuted instantiation: classifier.c:cmap_node_next Unexecuted instantiation: cmap.c:cmap_node_next Unexecuted instantiation: learn.c:cmap_node_next Unexecuted instantiation: netdev-offload.c:cmap_node_next Unexecuted instantiation: odp-execute.c:cmap_node_next Unexecuted instantiation: tnl-neigh-cache.c:cmap_node_next Unexecuted instantiation: conntrack.c:cmap_node_next Unexecuted instantiation: dpif-netdev.c:cmap_node_next Unexecuted instantiation: dpif-netdev-private-dfc.c:cmap_node_next Unexecuted instantiation: dpif-netdev-private-dpif.c:cmap_node_next Unexecuted instantiation: dpif-netdev-private-extract.c:cmap_node_next Unexecuted instantiation: conntrack-icmp.c:cmap_node_next Unexecuted instantiation: conntrack-tcp.c:cmap_node_next Unexecuted instantiation: conntrack-tp.c:cmap_node_next Unexecuted instantiation: conntrack-other.c:cmap_node_next Unexecuted instantiation: dpif-netdev-extract-study.c:cmap_node_next Unexecuted instantiation: dpif-netdev-lookup.c:cmap_node_next Unexecuted instantiation: dpif-netdev-lookup-autovalidator.c:cmap_node_next Unexecuted instantiation: dpif-netdev-lookup-generic.c:cmap_node_next
70
71		static inline struct cmap_node *
72		cmap_node_next_protected(const struct cmap_node *node)
73	0	{
74	0	return ovsrcu_get_protected(struct cmap_node *, &node->next);
75	0	} Unexecuted instantiation: ofctl_parse_target.c:cmap_node_next_protected Unexecuted instantiation: ofp-util.c:cmap_node_next_protected Unexecuted instantiation: meta-flow.c:cmap_node_next_protected Unexecuted instantiation: netdev.c:cmap_node_next_protected Unexecuted instantiation: nx-match.c:cmap_node_next_protected Unexecuted instantiation: ofp-actions.c:cmap_node_next_protected Unexecuted instantiation: ovs-router.c:cmap_node_next_protected Unexecuted instantiation: tnl-ports.c:cmap_node_next_protected Unexecuted instantiation: classifier.c:cmap_node_next_protected Unexecuted instantiation: cmap.c:cmap_node_next_protected Unexecuted instantiation: learn.c:cmap_node_next_protected Unexecuted instantiation: netdev-offload.c:cmap_node_next_protected Unexecuted instantiation: odp-execute.c:cmap_node_next_protected Unexecuted instantiation: tnl-neigh-cache.c:cmap_node_next_protected Unexecuted instantiation: conntrack.c:cmap_node_next_protected Unexecuted instantiation: dpif-netdev.c:cmap_node_next_protected Unexecuted instantiation: dpif-netdev-private-dfc.c:cmap_node_next_protected Unexecuted instantiation: dpif-netdev-private-dpif.c:cmap_node_next_protected Unexecuted instantiation: dpif-netdev-private-extract.c:cmap_node_next_protected Unexecuted instantiation: conntrack-icmp.c:cmap_node_next_protected Unexecuted instantiation: conntrack-tcp.c:cmap_node_next_protected Unexecuted instantiation: conntrack-tp.c:cmap_node_next_protected Unexecuted instantiation: conntrack-other.c:cmap_node_next_protected Unexecuted instantiation: dpif-netdev-extract-study.c:cmap_node_next_protected Unexecuted instantiation: dpif-netdev-lookup.c:cmap_node_next_protected Unexecuted instantiation: dpif-netdev-lookup-autovalidator.c:cmap_node_next_protected Unexecuted instantiation: dpif-netdev-lookup-generic.c:cmap_node_next_protected
76
77		/* Concurrent hash map. */
78		struct cmap {
79		OVSRCU_TYPE(struct cmap_impl *) impl;
80		};
81
82		/* Initializer for an empty cmap. */
83		#define CMAP_INITIALIZER { \
84		.impl = OVSRCU_INITIALIZER((struct cmap_impl *) &empty_cmap) \
85		}
86		extern OVS_ALIGNED_VAR(CACHE_LINE_SIZE) const struct cmap_impl empty_cmap;
87
88		/* Initialization. */
89		void cmap_init(struct cmap *);
90		void cmap_destroy(struct cmap *);
91
92		/* Count. */
93		size_t cmap_count(const struct cmap *);
94		bool cmap_is_empty(const struct cmap *);
95
96		/* Insertion and deletion. Return the current count after the operation. */
97		size_t cmap_insert(struct cmap , struct cmap_node , uint32_t hash);
98		static inline size_t cmap_remove(struct cmap , struct cmap_node ,
99		uint32_t hash);
100		size_t cmap_replace(struct cmap , struct cmap_node old_node,
101		struct cmap_node *new_node, uint32_t hash);
102
103		/* Search.
104		*
105		* These macros iterate NODE over all of the nodes in CMAP that have hash value
106		* equal to HASH. MEMBER must be the name of the 'struct cmap_node' member
107		* within NODE.
108		*
109		* CMAP and HASH are evaluated only once. NODE is evaluated many times.
110		*
111		* After a normal exit of the loop (not through a "break;" statement) NODE is
112		* NULL.
113		*
114		* Thread-safety
115		* =============
116		*
117		* CMAP_NODE_FOR_EACH will reliably visit each of the nodes starting with
118		* CMAP_NODE, even with concurrent insertions and deletions. (Of
119		* course, if nodes are being inserted or deleted, it might or might not visit
120		* the nodes actually being inserted or deleted.)
121		*
122		* CMAP_NODE_FOR_EACH_PROTECTED may only be used if the containing CMAP is
123		* guaranteed not to change during iteration. It may be only slightly faster.
124		*
125		* CMAP_FOR_EACH_WITH_HASH will reliably visit each of the nodes with the
126		* specified hash in CMAP, even with concurrent insertions and deletions. (Of
127		* course, if nodes with the given HASH are being inserted or deleted, it might
128		* or might not visit the nodes actually being inserted or deleted.)
129		*
130		* CMAP_FOR_EACH_WITH_HASH_PROTECTED may only be used if CMAP is guaranteed not
131		* to change during iteration. It may be very slightly faster.
132		*/
133		#define CMAP_NODE_FOR_EACH(NODE, MEMBER, CMAP_NODE) \
134	0	for (INIT_MULTIVAR(NODE, MEMBER, CMAP_NODE, struct cmap_node); \
135	0	CONDITION_MULTIVAR(NODE, MEMBER, ITER_VAR(NODE) != NULL); \
136	0	UPDATE_MULTIVAR(NODE, cmap_node_next(ITER_VAR(NODE))))
137		#define CMAP_NODE_FOR_EACH_PROTECTED(NODE, MEMBER, CMAP_NODE) \
138	0	for (INIT_MULTIVAR(NODE, MEMBER, CMAP_NODE, struct cmap_node); \
139	0	CONDITION_MULTIVAR(NODE, MEMBER, ITER_VAR(NODE) != NULL); \
140	0	UPDATE_MULTIVAR(NODE, cmap_node_next_protected(ITER_VAR(NODE))))
141
142		#define CMAP_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, CMAP) \
143	0	CMAP_NODE_FOR_EACH(NODE, MEMBER, cmap_find(CMAP, HASH))
144		#define CMAP_FOR_EACH_WITH_HASH_PROTECTED(NODE, MEMBER, HASH, CMAP) \
145	0	CMAP_NODE_FOR_EACH_PROTECTED(NODE, MEMBER, cmap_find_protected(CMAP, HASH))
146
147		const struct cmap_node cmap_find(const struct cmap , uint32_t hash);
148		struct cmap_node cmap_find_protected(const struct cmap , uint32_t hash);
149
150		/* Find node by index or find index by hash. The 'index' of a cmap entry is a
151		* way to combine the specific bucket and the entry of the bucket into a
152		* convenient single integer value. In other words, it is the index of the
153		* entry and each entry has an unique index. It is not used internally by
154		* cmap.
155		* Currently the functions assume index will not be larger than uint32_t. In
156		* OvS table size is usually much smaller than this size.*/
157		const struct cmap_node * cmap_find_by_index(const struct cmap *,
158		uint32_t index);
159		uint32_t cmap_find_index(const struct cmap *, uint32_t hash);
160
161		/* Looks up multiple 'hashes', when the corresponding bit in 'map' is 1,
162		* and sets the corresponding pointer in 'nodes', if the hash value was
163		* found from the 'cmap'. In other cases the 'nodes' values are not changed,
164		* i.e., no NULL pointers are stored there.
165		* Returns a map where a bit is set to 1 if the corresponding 'nodes' pointer
166		* was stored, 0 otherwise.
167		* Generally, the caller wants to use CMAP_NODE_FOR_EACH to verify for
168		* hash collisions. */
169		unsigned long cmap_find_batch(const struct cmap *cmap, unsigned long map,
170		uint32_t hashes[],
171		const struct cmap_node *nodes[]);
172
173		/* Iteration.
174		*
175		*
176		* Thread-safety
177		* =============
178		*
179		* Iteration is safe even in a cmap that is changing concurrently. However:
180		*
181		* - In the presence of concurrent calls to cmap_insert(), any given
182		* iteration might skip some nodes and might visit some nodes more than
183		* once. If this is a problem, then the iterating code should lock the
184		* data structure (a rwlock can be used to allow multiple threads to
185		* iterate in parallel).
186		*
187		* - Concurrent calls to cmap_remove() don't have the same problem. (A
188		* node being deleted may be visited once or not at all. Other nodes
189		* will be visited once.)
190		*
191		* - If the cmap is changing, it is not safe to quiesce while iterating.
192		* Even if the changes are done by the same thread that's performing the
193		* iteration (Corollary: it is not safe to call cmap_remove() and quiesce
194		* in the loop body).
195		*
196		*
197		* Example
198		* =======
199		*
200		* struct my_node {
201		* struct cmap_node cmap_node;
202		* int extra_data;
203		* };
204		*
205		* struct cmap my_map;
206		* struct my_node *my_node;
207		*
208		* cmap_init(&my_map);
209		* ...add data...
210		* CMAP_FOR_EACH (my_node, cmap_node, &my_map) {
211		* ...operate on my_node...
212		* }
213		*
214		* CMAP_FOR_EACH is "safe" in the sense of HMAP_FOR_EACH_SAFE. That is, it is
215		* safe to free the current node before going on to the next iteration. Most
216		* of the time, though, this doesn't matter for a cmap because node
217		* deallocation has to be postponed until the next grace period. This means
218		* that this guarantee is useful only in deallocation code already executing at
219		* postponed time, when it is known that the RCU grace period has already
220		* expired.
221		*/
222
223		#define CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER) \
224	0	((CURSOR)->node \
225	0	? (INIT_CONTAINER(NODE, (CURSOR)->node, MEMBER), \
226	0	cmap_cursor_advance(CURSOR), \
227	0	true) \
228	0	: (NODE = NULL, false))
229
230		#define CMAP_CURSOR_FOR_EACH(NODE, MEMBER, CURSOR, CMAP) \
231		for (*(CURSOR) = cmap_cursor_start(CMAP); \
232		CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER); \
233		)
234
235		#define CMAP_CURSOR_FOR_EACH_CONTINUE(NODE, MEMBER, CURSOR) \
236	0	while (CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER))
237
238		struct cmap_cursor {
239		const struct cmap_impl *impl;
240		uint32_t bucket_idx;
241		int entry_idx;
242		struct cmap_node *node;
243		};
244
245		struct cmap_cursor cmap_cursor_start(const struct cmap *);
246		void cmap_cursor_advance(struct cmap_cursor *);
247
248		/* Generate a unique name for the cursor with the __COUNTER__ macro to
249		* allow nesting of CMAP_FOR_EACH loops. */
250		#define CMAP_FOR_EACH__(NODE, MEMBER, CMAP, CURSOR_NAME) \
251	0	for (struct cmap_cursor CURSOR_NAME = cmap_cursor_start(CMAP); \
252	0	CMAP_CURSOR_FOR_EACH__(NODE, &CURSOR_NAME, MEMBER); \
253	0	)
254
255		#define CMAP_FOR_EACH(NODE, MEMBER, CMAP) \
256	0	CMAP_FOR_EACH__(NODE, MEMBER, CMAP, \
257	0	OVS_JOIN(cursor_, __COUNTER__))
258
259		static inline struct cmap_node cmap_first(const struct cmap );
260
261		/* Another, less preferred, form of iteration, for use in situations where it
262		* is difficult to maintain a pointer to a cmap_node. */
263		struct cmap_position {
264		unsigned int bucket;
265		unsigned int entry;
266		unsigned int offset;
267		};
268
269		struct cmap_node cmap_next_position(const struct cmap ,
270		struct cmap_position *);
271
272		/* Returns the first node in 'cmap', in arbitrary order, or a null pointer if
273		* 'cmap' is empty. */
274		static inline struct cmap_node *
275		cmap_first(const struct cmap *cmap)
276	0	{
277	0	struct cmap_position pos = { 0, 0, 0 };
278	0
279	0	return cmap_next_position(cmap, &pos);
280	0	} Unexecuted instantiation: ofctl_parse_target.c:cmap_first Unexecuted instantiation: ofp-util.c:cmap_first Unexecuted instantiation: meta-flow.c:cmap_first Unexecuted instantiation: netdev.c:cmap_first Unexecuted instantiation: nx-match.c:cmap_first Unexecuted instantiation: ofp-actions.c:cmap_first Unexecuted instantiation: ovs-router.c:cmap_first Unexecuted instantiation: tnl-ports.c:cmap_first Unexecuted instantiation: classifier.c:cmap_first Unexecuted instantiation: cmap.c:cmap_first Unexecuted instantiation: learn.c:cmap_first Unexecuted instantiation: netdev-offload.c:cmap_first Unexecuted instantiation: odp-execute.c:cmap_first Unexecuted instantiation: tnl-neigh-cache.c:cmap_first Unexecuted instantiation: conntrack.c:cmap_first Unexecuted instantiation: dpif-netdev.c:cmap_first Unexecuted instantiation: dpif-netdev-private-dfc.c:cmap_first Unexecuted instantiation: dpif-netdev-private-dpif.c:cmap_first Unexecuted instantiation: dpif-netdev-private-extract.c:cmap_first Unexecuted instantiation: conntrack-icmp.c:cmap_first Unexecuted instantiation: conntrack-tcp.c:cmap_first Unexecuted instantiation: conntrack-tp.c:cmap_first Unexecuted instantiation: conntrack-other.c:cmap_first Unexecuted instantiation: dpif-netdev-extract-study.c:cmap_first Unexecuted instantiation: dpif-netdev-lookup.c:cmap_first Unexecuted instantiation: dpif-netdev-lookup-autovalidator.c:cmap_first Unexecuted instantiation: dpif-netdev-lookup-generic.c:cmap_first
281
282		/* Removes 'node' from 'cmap'. The caller must ensure that 'cmap' cannot
283		* change concurrently (from another thread).
284		*
285		* 'node' must not be destroyed or modified or inserted back into 'cmap' or
286		* into any other concurrent hash map while any other thread might be accessing
287		* it. One correct way to do this is to free it from an RCU callback with
288		* ovsrcu_postpone().
289		*
290		* Returns the current number of nodes in the cmap after the removal. */
291		static inline size_t
292		cmap_remove(struct cmap cmap, struct cmap_node node, uint32_t hash)
293	0	{
294	0	return cmap_replace(cmap, node, NULL, hash);
295	0	} Unexecuted instantiation: ofctl_parse_target.c:cmap_remove Unexecuted instantiation: ofp-util.c:cmap_remove Unexecuted instantiation: meta-flow.c:cmap_remove Unexecuted instantiation: netdev.c:cmap_remove Unexecuted instantiation: nx-match.c:cmap_remove Unexecuted instantiation: ofp-actions.c:cmap_remove Unexecuted instantiation: ovs-router.c:cmap_remove Unexecuted instantiation: tnl-ports.c:cmap_remove Unexecuted instantiation: classifier.c:cmap_remove Unexecuted instantiation: cmap.c:cmap_remove Unexecuted instantiation: learn.c:cmap_remove Unexecuted instantiation: netdev-offload.c:cmap_remove Unexecuted instantiation: odp-execute.c:cmap_remove Unexecuted instantiation: tnl-neigh-cache.c:cmap_remove Unexecuted instantiation: conntrack.c:cmap_remove Unexecuted instantiation: dpif-netdev.c:cmap_remove Unexecuted instantiation: dpif-netdev-private-dfc.c:cmap_remove Unexecuted instantiation: dpif-netdev-private-dpif.c:cmap_remove Unexecuted instantiation: dpif-netdev-private-extract.c:cmap_remove Unexecuted instantiation: conntrack-icmp.c:cmap_remove Unexecuted instantiation: conntrack-tcp.c:cmap_remove Unexecuted instantiation: conntrack-tp.c:cmap_remove Unexecuted instantiation: conntrack-other.c:cmap_remove Unexecuted instantiation: dpif-netdev-extract-study.c:cmap_remove Unexecuted instantiation: dpif-netdev-lookup.c:cmap_remove Unexecuted instantiation: dpif-netdev-lookup-autovalidator.c:cmap_remove Unexecuted instantiation: dpif-netdev-lookup-generic.c:cmap_remove
296
297		#endif /* cmap.h */