1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
|
/*
* 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.
*/
#include <config.h>
#include "pvector.h"
/* Writers will preallocate space for some entries at the end to avoid future
* reallocations. */
enum { PVECTOR_EXTRA_ALLOC = 4 };
static struct pvector_impl *
pvector_impl_get(const struct pvector *pvec)
{
return ovsrcu_get(struct pvector_impl *, &pvec->impl);
}
static struct pvector_impl *
pvector_impl_alloc(size_t size)
{
struct pvector_impl *impl;
impl = xmalloc(sizeof *impl + size * sizeof impl->vector[0]);
atomic_init(&impl->size, 0);
impl->allocated = size;
return impl;
}
static struct pvector_impl *
pvector_impl_dup(struct pvector_impl *old)
{
struct pvector_impl *impl;
size_t alloc = old->size + PVECTOR_EXTRA_ALLOC;
impl = xmalloc(sizeof *impl + alloc * sizeof impl->vector[0]);
impl->allocated = alloc;
impl->size = old->size;
memcpy(impl->vector, old->vector, old->size * sizeof old->vector[0]);
return impl;
}
/* Initializes 'pvec' as an empty concurrent priority vector. */
void
pvector_init(struct pvector *pvec)
{
ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC));
pvec->temp = NULL;
}
/* Destroys 'pvec'.
*
* The client is responsible for destroying any data previously held in
* 'pvec'. */
void
pvector_destroy(struct pvector *pvec)
{
free(pvec->temp);
pvec->temp = NULL;
ovsrcu_postpone(free, pvector_impl_get(pvec));
ovsrcu_set(&pvec->impl, NULL); /* Poison. */
}
/* Iterators for callers that need the 'index' afterward. */
#define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL) \
for ((INDEX) = 0; \
(INDEX) < (IMPL)->size \
&& ((ENTRY) = &(IMPL)->vector[INDEX], true); \
(INDEX)++)
static int
pvector_entry_cmp(const void *a_, const void *b_)
{
const struct pvector_entry *ap = a_;
const struct pvector_entry *bp = b_;
int a = ap->priority;
int b = bp->priority;
return a > b ? -1 : a < b;
}
static void
pvector_impl_sort(struct pvector_impl *impl)
{
qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp);
}
/* Returns the index of the 'ptr' in the vector, or -1 if none is found. */
static int
pvector_impl_find(struct pvector_impl *impl, void *target)
{
const struct pvector_entry *entry;
int index;
PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
if (entry->ptr == target) {
return index;
}
}
return -1;
}
void
pvector_insert(struct pvector *pvec, void *ptr, int priority)
{
struct pvector_impl *temp = pvec->temp;
struct pvector_impl *old = pvector_impl_get(pvec);
size_t size;
ovs_assert(ptr != NULL);
/* There is no possible concurrent writer. Insertions must be protected
* by mutex or be always excuted from the same thread. */
atomic_read_relaxed(&old->size, &size);
/* Check if can add to the end without reallocation. */
if (!temp && old->allocated > size &&
(!size || priority <= old->vector[size - 1].priority)) {
old->vector[size].ptr = ptr;
old->vector[size].priority = priority;
/* Size increment must not be visible to the readers before the new
* entry is stored. */
atomic_store_explicit(&old->size, size + 1, memory_order_release);
} else {
if (!temp) {
temp = pvector_impl_dup(old);
pvec->temp = temp;
} else if (temp->size == temp->allocated) {
temp = pvector_impl_dup(temp);
free(pvec->temp);
pvec->temp = temp;
}
/* Insert at the end, publish will sort. */
temp->vector[temp->size].ptr = ptr;
temp->vector[temp->size].priority = priority;
temp->size += 1;
}
}
void
pvector_remove(struct pvector *pvec, void *ptr)
{
struct pvector_impl *temp = pvec->temp;
int index;
if (!temp) {
temp = pvector_impl_dup(pvector_impl_get(pvec));
pvec->temp = temp;
}
ovs_assert(temp->size > 0);
index = pvector_impl_find(temp, ptr);
ovs_assert(index >= 0);
/* Now at the index of the entry to be deleted.
* Swap another entry in if needed, publish will sort anyway. */
temp->size--;
if (index != temp->size) {
temp->vector[index] = temp->vector[temp->size];
}
}
/* Change entry's 'priority' and keep the vector ordered. */
void
pvector_change_priority(struct pvector *pvec, void *ptr, int priority)
{
struct pvector_impl *old = pvec->temp;
int index;
if (!old) {
old = pvector_impl_get(pvec);
}
index = pvector_impl_find(old, ptr);
ovs_assert(index >= 0);
/* Now at the index of the entry to be updated. */
/* Check if can not update in place. */
if ((priority > old->vector[index].priority && index > 0
&& priority > old->vector[index - 1].priority)
|| (priority < old->vector[index].priority && index < old->size - 1
&& priority < old->vector[index + 1].priority)) {
/* Have to use a temp. */
if (!pvec->temp) {
/* Have to reallocate to reorder. */
pvec->temp = pvector_impl_dup(old);
old = pvec->temp;
/* Publish will sort. */
}
}
old->vector[index].priority = priority;
}
/* Make the modified pvector available for iteration. */
void pvector_publish__(struct pvector *pvec)
{
struct pvector_impl *temp = pvec->temp;
pvec->temp = NULL;
pvector_impl_sort(temp); /* Also removes gaps. */
ovsrcu_postpone(free, ovsrcu_get_protected(struct pvector_impl *,
&pvec->impl));
ovsrcu_set(&pvec->impl, temp);
}
|
