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