/src/openvswitch/lib/pvector.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 PVECTOR_H
#define PVECTOR_H 1

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

/* Concurrent Priority Vector
 * ==========================
 *
 * Concurrent priority vector holds non-NULL pointers to objects in a
 * nondecreasing priority order and allows readers to traverse the vector
 * without being concerned about writers modifying the vector as they are
 * traversing it.
 *
 * Multiple elements of a given priority are allowed.
 *
 * The priority order is maintained as a linear vector of elements to allow
 * for efficient memory prefetching.
 *
 * Concurrency is implemented with OVS RCU so that the readers can assume
 * that once they have taken a pointer to the vector with
 * pvector_cursor_init(), the 'size' member will not decrease, so that
 * they can safely read 'size' entries from 'vector', and find that each
 * entry has a valid, non-NULL 'ptr', and the vector is in order from highest
 * to lowest 'priority'.  The 'priority' values can change any time, but only
 * so that the order of the entries does not change, so readers can use
 * 'priority' values read at any time after acquisition of the vector pointer.
 *
 * Writers can concurrently add entries to the end of the vector, incrementing
 * 'size', or update the 'priority' value of an entry, but only if that does
 * not change the ordering of the entries.  Writers will never change the 'ptr'
 * values, or decrement the 'size' on a copy that readers have access to.
 *
 * Most modifications are internally staged at the 'temp' vector, from which
 * they can be published at 'impl' by calling pvector_publish().  This saves
 * unnecessary memory allocations when many changes are done back-to-back.
 * 'temp' may contain NULL pointers and it may be in unsorted order.  It is
 * sorted before it is published at 'impl', which also removes the NULLs from
 * the published vector.
 *
 * Since the vector is RCU protected, the entry destruction after removal must
 * be RCU postponed.  Also, if it happens before changes published with
 * pvector_publish(), destruction must be double postponed, i.e., the second
 * ovsrcu_postpone() call to destruct the entry should be called from the first
 * RCU callback.  This is required because readers could still obtain the
 * unmodified vector until updated version is published.
 */

struct pvector_entry {
    int priority;
    void *ptr;
};

struct pvector_impl {
    atomic_size_t size;   /* Number of entries in the vector. */
    size_t allocated;     /* Number of allocated entries. */
    struct pvector_entry vector[];
};

/* Concurrent priority vector. */
struct pvector {
    OVSRCU_TYPE(struct pvector_impl *) impl;
    struct pvector_impl *temp;
};

/* Initialization. */
void pvector_init(struct pvector *);
void pvector_destroy(struct pvector *);

/* Insertion and deletion.  These work on 'temp'.  */
void pvector_insert(struct pvector *, void *, int priority);
void pvector_change_priority(struct pvector *, void *, int priority);
void pvector_remove(struct pvector *, void *);

/* Make the modified pvector available for iteration. */
static inline void pvector_publish(struct pvector *);

/* Count.  These operate on the published pvector. */
static inline size_t pvector_count(const struct pvector *);
static inline bool pvector_is_empty(const struct pvector *);

/* Iteration.
 *
 *
 * Thread-safety
 * =============
 *
 * Iteration is safe even in a pvector that is changing concurrently.
 * Multiple writers must exclude each other via e.g., a mutex.
 *
 * Example
 * =======
 *
 *     struct my_node {
 *         int data;
 *     };
 *
 *     struct my_node elem1, elem2, *iter;
 *     struct pvector my_pvector;
 *
 *     pvector_init(&my_pvector);
 *     ...add data...
 *     pvector_insert(&my_pvector, &elem1, 1);
 *     pvector_insert(&my_pvector, &elem2, 2);
 *     ...
 *     PVECTOR_FOR_EACH (iter, &my_pvector) {
 *         ...operate on '*iter'...
 *         ...elem2 to be seen before elem1...
 *     }
 *     ...
 *     pvector_destroy(&my_pvector);
 *
 * There is no PVECTOR_FOR_EACH_SAFE variant as iteration is performed on RCU
 * protected instance of the priority vector.  Any concurrent modifications
 * that would be disruptive for readers (such as deletions), will be performed
 * on a new instance.  To see any of the modifications, a new iteration loop
 * has to be started.
 *
 * The PVECTOR_FOR_EACH_PRIORITY limits the iteration to entries with higher
 * than or equal to the given priority and allows for object lookahead.
 *
 * The iteration loop must be completed without entering the OVS RCU quiescent
 * period.  That is, an old iteration loop must not be continued after any
 * blocking IO (VLOG is non-blocking, so that is OK).
 */
struct pvector_cursor {
    size_t size;        /* Number of entries in the vector. */
    size_t entry_idx;   /* Current index. */
    const struct pvector_entry *vector;
};

static inline struct pvector_cursor pvector_cursor_init(const struct pvector *,
                                                        size_t n_ahead,
                                                        size_t obj_size);
static inline void *pvector_cursor_next(struct pvector_cursor *,
                                        int lowest_priority,
                                        size_t n_ahead, size_t obj_size);
static inline void pvector_cursor_lookahead(const struct pvector_cursor *,
                                            int n, size_t size);

#define PVECTOR_FOR_EACH(PTR, PVECTOR)                                  \
    for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, 0, 0); \
         ((PTR) = pvector_cursor_next(&cursor__, INT_MIN, 0, 0)) != NULL; )

/* Loop while priority is higher than or equal to 'PRIORITY' and prefetch
 * objects of size 'SZ' 'N' objects ahead from the current object. */
#define PVECTOR_FOR_EACH_PRIORITY(PTR, PRIORITY, N, SZ, PVECTOR)        \
    for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, N, SZ); \
         ((PTR) = pvector_cursor_next(&cursor__, PRIORITY, N, SZ)) != NULL; )

#define PVECTOR_CURSOR_FOR_EACH(PTR, CURSOR, PVECTOR)                \
    for (*(CURSOR) = pvector_cursor_init(PVECTOR, 0, 0);             \
         ((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; )

#define PVECTOR_CURSOR_FOR_EACH_CONTINUE(PTR, CURSOR)                   \
    for (; ((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; )


/* Inline implementations. */

static inline struct pvector_cursor
pvector_cursor_init(const struct pvector *pvec,
                    size_t n_ahead, size_t obj_size)
{
    const struct pvector_impl *impl;
    struct pvector_cursor cursor;
    size_t size;

    impl = ovsrcu_get(struct pvector_impl *, &pvec->impl);

    /* Use memory_order_acquire to ensure entry access can not be
     * reordered to happen before size read. */
    atomic_read_explicit(&CONST_CAST(struct pvector_impl *, impl)->size,
                         &size, memory_order_acquire);
    ovs_prefetch_range(impl->vector, size * sizeof impl->vector[0]);

    cursor.size = size;
    cursor.vector = impl->vector;
    cursor.entry_idx = -1;

    for (size_t i = 0; i < n_ahead; i++) {
        /* Prefetch the first objects. */
        pvector_cursor_lookahead(&cursor, i, obj_size);
    }
    return cursor;
}

static inline void *pvector_cursor_next(struct pvector_cursor *cursor,
                                        int lowest_priority,
                                        size_t n_ahead, size_t obj_size)
{
    if (++cursor->entry_idx < cursor->size &&
        cursor->vector[cursor->entry_idx].priority >= lowest_priority) {
        if (n_ahead) {
            pvector_cursor_lookahead(cursor, n_ahead, obj_size);
        }
        return cursor->vector[cursor->entry_idx].ptr;
    }
    return NULL;
}

static inline void pvector_cursor_lookahead(const struct pvector_cursor *cursor,
                                            int n, size_t size)
{
    if (cursor->entry_idx + n < cursor->size) {
        ovs_prefetch_range(cursor->vector[cursor->entry_idx + n].ptr, size);
    }
}

static inline size_t pvector_count(const struct pvector *pvec)
{
    return ovsrcu_get(struct pvector_impl *, &pvec->impl)->size;
}

static inline bool pvector_is_empty(const struct pvector *pvec)
{
    return pvector_count(pvec) == 0;
}

void pvector_publish__(struct pvector *);

/* Make the modified pvector available for iteration. */
static inline void pvector_publish(struct pvector *pvec)
{
    if (pvec->temp) {
        pvector_publish__(pvec);
    }
}

#endif /* pvector.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 PVECTOR_H
18		#define PVECTOR_H 1
19
20		#include <stdbool.h>
21		#include <stdint.h>
22		#include <stdlib.h>
23		#include "ovs-rcu.h"
24		#include "util.h"
25
26		/* Concurrent Priority Vector
27		* ==========================
28		*
29		* Concurrent priority vector holds non-NULL pointers to objects in a
30		* nondecreasing priority order and allows readers to traverse the vector
31		* without being concerned about writers modifying the vector as they are
32		* traversing it.
33		*
34		* Multiple elements of a given priority are allowed.
35		*
36		* The priority order is maintained as a linear vector of elements to allow
37		* for efficient memory prefetching.
38		*
39		* Concurrency is implemented with OVS RCU so that the readers can assume
40		* that once they have taken a pointer to the vector with
41		* pvector_cursor_init(), the 'size' member will not decrease, so that
42		* they can safely read 'size' entries from 'vector', and find that each
43		* entry has a valid, non-NULL 'ptr', and the vector is in order from highest
44		* to lowest 'priority'. The 'priority' values can change any time, but only
45		* so that the order of the entries does not change, so readers can use
46		* 'priority' values read at any time after acquisition of the vector pointer.
47		*
48		* Writers can concurrently add entries to the end of the vector, incrementing
49		* 'size', or update the 'priority' value of an entry, but only if that does
50		* not change the ordering of the entries. Writers will never change the 'ptr'
51		* values, or decrement the 'size' on a copy that readers have access to.
52		*
53		* Most modifications are internally staged at the 'temp' vector, from which
54		* they can be published at 'impl' by calling pvector_publish(). This saves
55		* unnecessary memory allocations when many changes are done back-to-back.
56		* 'temp' may contain NULL pointers and it may be in unsorted order. It is
57		* sorted before it is published at 'impl', which also removes the NULLs from
58		* the published vector.
59		*
60		* Since the vector is RCU protected, the entry destruction after removal must
61		* be RCU postponed. Also, if it happens before changes published with
62		* pvector_publish(), destruction must be double postponed, i.e., the second
63		* ovsrcu_postpone() call to destruct the entry should be called from the first
64		* RCU callback. This is required because readers could still obtain the
65		* unmodified vector until updated version is published.
66		*/
67
68		struct pvector_entry {
69		int priority;
70		void *ptr;
71		};
72
73		struct pvector_impl {
74		atomic_size_t size; /* Number of entries in the vector. */
75		size_t allocated; /* Number of allocated entries. */
76		struct pvector_entry vector[];
77		};
78
79		/* Concurrent priority vector. */
80		struct pvector {
81		OVSRCU_TYPE(struct pvector_impl *) impl;
82		struct pvector_impl *temp;
83		};
84
85		/* Initialization. */
86		void pvector_init(struct pvector *);
87		void pvector_destroy(struct pvector *);
88
89		/* Insertion and deletion. These work on 'temp'. */
90		void pvector_insert(struct pvector , void , int priority);
91		void pvector_change_priority(struct pvector , void , int priority);
92		void pvector_remove(struct pvector , void );
93
94		/* Make the modified pvector available for iteration. */
95		static inline void pvector_publish(struct pvector *);
96
97		/* Count. These operate on the published pvector. */
98		static inline size_t pvector_count(const struct pvector *);
99		static inline bool pvector_is_empty(const struct pvector *);
100
101		/* Iteration.
102		*
103		*
104		* Thread-safety
105		* =============
106		*
107		* Iteration is safe even in a pvector that is changing concurrently.
108		* Multiple writers must exclude each other via e.g., a mutex.
109		*
110		* Example
111		* =======
112		*
113		* struct my_node {
114		* int data;
115		* };
116		*
117		* struct my_node elem1, elem2, *iter;
118		* struct pvector my_pvector;
119		*
120		* pvector_init(&my_pvector);
121		* ...add data...
122		* pvector_insert(&my_pvector, &elem1, 1);
123		* pvector_insert(&my_pvector, &elem2, 2);
124		* ...
125		* PVECTOR_FOR_EACH (iter, &my_pvector) {
126		* ...operate on '*iter'...
127		* ...elem2 to be seen before elem1...
128		* }
129		* ...
130		* pvector_destroy(&my_pvector);
131		*
132		* There is no PVECTOR_FOR_EACH_SAFE variant as iteration is performed on RCU
133		* protected instance of the priority vector. Any concurrent modifications
134		* that would be disruptive for readers (such as deletions), will be performed
135		* on a new instance. To see any of the modifications, a new iteration loop
136		* has to be started.
137		*
138		* The PVECTOR_FOR_EACH_PRIORITY limits the iteration to entries with higher
139		* than or equal to the given priority and allows for object lookahead.
140		*
141		* The iteration loop must be completed without entering the OVS RCU quiescent
142		* period. That is, an old iteration loop must not be continued after any
143		* blocking IO (VLOG is non-blocking, so that is OK).
144		*/
145		struct pvector_cursor {
146		size_t size; /* Number of entries in the vector. */
147		size_t entry_idx; /* Current index. */
148		const struct pvector_entry *vector;
149		};
150
151		static inline struct pvector_cursor pvector_cursor_init(const struct pvector *,
152		size_t n_ahead,
153		size_t obj_size);
154		static inline void pvector_cursor_next(struct pvector_cursor ,
155		int lowest_priority,
156		size_t n_ahead, size_t obj_size);
157		static inline void pvector_cursor_lookahead(const struct pvector_cursor *,
158		int n, size_t size);
159
160		#define PVECTOR_FOR_EACH(PTR, PVECTOR) \
161	0	for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, 0, 0); \
162	0	((PTR) = pvector_cursor_next(&cursor__, INT_MIN, 0, 0)) != NULL; )
163
164		/* Loop while priority is higher than or equal to 'PRIORITY' and prefetch
165		* objects of size 'SZ' 'N' objects ahead from the current object. */
166		#define PVECTOR_FOR_EACH_PRIORITY(PTR, PRIORITY, N, SZ, PVECTOR) \
167	0	for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, N, SZ); \
168	0	((PTR) = pvector_cursor_next(&cursor__, PRIORITY, N, SZ)) != NULL; )
169
170		#define PVECTOR_CURSOR_FOR_EACH(PTR, CURSOR, PVECTOR) \
171	0	for (*(CURSOR) = pvector_cursor_init(PVECTOR, 0, 0); \
172	0	((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; )
173
174		#define PVECTOR_CURSOR_FOR_EACH_CONTINUE(PTR, CURSOR) \
175	0	for (; ((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; )
176
177
178		/* Inline implementations. */
179
180		static inline struct pvector_cursor
181		pvector_cursor_init(const struct pvector *pvec,
182		size_t n_ahead, size_t obj_size)
183	0	{
184	0	const struct pvector_impl *impl;
185	0	struct pvector_cursor cursor;
186	0	size_t size;
187
188	0	impl = ovsrcu_get(struct pvector_impl *, &pvec->impl);
189
190		/* Use memory_order_acquire to ensure entry access can not be
191		* reordered to happen before size read. */
192	0	atomic_read_explicit(&CONST_CAST(struct pvector_impl *, impl)->size,
193	0	&size, memory_order_acquire);
194	0	ovs_prefetch_range(impl->vector, size * sizeof impl->vector[0]);
195
196	0	cursor.size = size;
197	0	cursor.vector = impl->vector;
198	0	cursor.entry_idx = -1;
199
200	0	for (size_t i = 0; i < n_ahead; i++) {
201		/* Prefetch the first objects. */
202	0	pvector_cursor_lookahead(&cursor, i, obj_size);
203	0	}
204	0	return cursor;
205	0	} Unexecuted instantiation: meta-flow.c:pvector_cursor_init Unexecuted instantiation: nx-match.c:pvector_cursor_init Unexecuted instantiation: ofp-util.c:pvector_cursor_init Unexecuted instantiation: ovs-router.c:pvector_cursor_init Unexecuted instantiation: pvector.c:pvector_cursor_init Unexecuted instantiation: tnl-ports.c:pvector_cursor_init Unexecuted instantiation: classifier.c:pvector_cursor_init Unexecuted instantiation: dpif-netdev.c:pvector_cursor_init Unexecuted instantiation: dpif-netdev-lookup-generic.c:pvector_cursor_init
206
207		static inline void pvector_cursor_next(struct pvector_cursor cursor,
208		int lowest_priority,
209		size_t n_ahead, size_t obj_size)
210	0	{
211	0	if (++cursor->entry_idx < cursor->size &&
212	0	cursor->vector[cursor->entry_idx].priority >= lowest_priority) {
213	0	if (n_ahead) {
214	0	pvector_cursor_lookahead(cursor, n_ahead, obj_size);
215	0	}
216	0	return cursor->vector[cursor->entry_idx].ptr;
217	0	}
218	0	return NULL;
219	0	} Unexecuted instantiation: meta-flow.c:pvector_cursor_next Unexecuted instantiation: nx-match.c:pvector_cursor_next Unexecuted instantiation: ofp-util.c:pvector_cursor_next Unexecuted instantiation: ovs-router.c:pvector_cursor_next Unexecuted instantiation: pvector.c:pvector_cursor_next Unexecuted instantiation: tnl-ports.c:pvector_cursor_next Unexecuted instantiation: classifier.c:pvector_cursor_next Unexecuted instantiation: dpif-netdev.c:pvector_cursor_next Unexecuted instantiation: dpif-netdev-lookup-generic.c:pvector_cursor_next
220
221		static inline void pvector_cursor_lookahead(const struct pvector_cursor *cursor,
222		int n, size_t size)
223	0	{
224	0	if (cursor->entry_idx + n < cursor->size) {
225	0	ovs_prefetch_range(cursor->vector[cursor->entry_idx + n].ptr, size);
226	0	}
227	0	} Unexecuted instantiation: meta-flow.c:pvector_cursor_lookahead Unexecuted instantiation: nx-match.c:pvector_cursor_lookahead Unexecuted instantiation: ofp-util.c:pvector_cursor_lookahead Unexecuted instantiation: ovs-router.c:pvector_cursor_lookahead Unexecuted instantiation: pvector.c:pvector_cursor_lookahead Unexecuted instantiation: tnl-ports.c:pvector_cursor_lookahead Unexecuted instantiation: classifier.c:pvector_cursor_lookahead Unexecuted instantiation: dpif-netdev.c:pvector_cursor_lookahead Unexecuted instantiation: dpif-netdev-lookup-generic.c:pvector_cursor_lookahead
228
229		static inline size_t pvector_count(const struct pvector *pvec)
230	0	{
231	0	return ovsrcu_get(struct pvector_impl *, &pvec->impl)->size;
232	0	} Unexecuted instantiation: meta-flow.c:pvector_count Unexecuted instantiation: nx-match.c:pvector_count Unexecuted instantiation: ofp-util.c:pvector_count Unexecuted instantiation: ovs-router.c:pvector_count Unexecuted instantiation: pvector.c:pvector_count Unexecuted instantiation: tnl-ports.c:pvector_count Unexecuted instantiation: classifier.c:pvector_count Unexecuted instantiation: dpif-netdev.c:pvector_count Unexecuted instantiation: dpif-netdev-lookup-generic.c:pvector_count
233
234		static inline bool pvector_is_empty(const struct pvector *pvec)
235	0	{
236	0	return pvector_count(pvec) == 0;
237	0	} Unexecuted instantiation: meta-flow.c:pvector_is_empty Unexecuted instantiation: nx-match.c:pvector_is_empty Unexecuted instantiation: ofp-util.c:pvector_is_empty Unexecuted instantiation: ovs-router.c:pvector_is_empty Unexecuted instantiation: pvector.c:pvector_is_empty Unexecuted instantiation: tnl-ports.c:pvector_is_empty Unexecuted instantiation: classifier.c:pvector_is_empty Unexecuted instantiation: dpif-netdev.c:pvector_is_empty Unexecuted instantiation: dpif-netdev-lookup-generic.c:pvector_is_empty
238
239		void pvector_publish__(struct pvector *);
240
241		/* Make the modified pvector available for iteration. */
242		static inline void pvector_publish(struct pvector *pvec)
243	0	{
244	0	if (pvec->temp) {
245	0	pvector_publish__(pvec);
246	0	}
247	0	} Unexecuted instantiation: meta-flow.c:pvector_publish Unexecuted instantiation: nx-match.c:pvector_publish Unexecuted instantiation: ofp-util.c:pvector_publish Unexecuted instantiation: ovs-router.c:pvector_publish Unexecuted instantiation: pvector.c:pvector_publish Unexecuted instantiation: tnl-ports.c:pvector_publish Unexecuted instantiation: classifier.c:pvector_publish Unexecuted instantiation: dpif-netdev.c:pvector_publish Unexecuted instantiation: dpif-netdev-lookup-generic.c:pvector_publish
248
249		#endif /* pvector.h */