Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-only
2 : : /*
3 : : * Copyright (c) Meta Platforms, Inc. and affiliates.
4 : : */
5 : :
6 : : #include "bpfilter/core/hashset.h"
7 : :
8 : : #include <errno.h>
9 : : #include <stdlib.h>
10 : :
11 : : #include "bpfilter/helper.h"
12 : : #include "bpfilter/logger.h"
13 : :
14 : : #define _BF_HASHSET_TOMBSTONE ((bf_hashset_elem *)1)
15 : : #define _BF_HASHSET_INIT_CAP 16UL
16 : : /* Maximum load factor before growing. Lowering this number reduces collisions
17 : : * but causes higher memory usage. */
18 : : #define _BF_HASHSET_MAX_LOAD_NUM 5
19 : : #define _BF_HASHSET_MAX_LOAD_DEN 10
20 : : /* Largest power-of-two element count (2^60) that still leaves headroom for
21 : : * load-factor arithmetic (slots_in_use * 10, cap * 5) without overflowing
22 : : * size_t. */
23 : : #define _BF_HASHSET_MAX_CAP (SIZE_MAX / 16 + 1)
24 : :
25 : 1090 : static inline size_t _bf_round_next_power_of_2(size_t value)
26 : : {
27 [ + - ]: 1090 : if (value == 0)
28 : : return 1;
29 : :
30 : 1090 : value--;
31 : 1090 : value |= value >> 1;
32 : 1090 : value |= value >> 2;
33 : 1090 : value |= value >> 4;
34 : 1090 : value |= value >> 8;
35 : 1090 : value |= value >> 16;
36 : : #if SIZE_MAX > 0xFFFFFFFFU
37 : 1090 : value |= value >> 32;
38 : : #endif
39 : :
40 : 1090 : return ++value;
41 : : }
42 : :
43 : : static inline bool _bf_hashset_slot_is_tombstone(const bf_hashset_elem *slot)
44 : : {
45 : : return slot == _BF_HASHSET_TOMBSTONE;
46 : : }
47 : :
48 : : // Caller must ensure set->cap > 0 to avoid division by zero.
49 : : static size_t _bf_hashset_index(const bf_hashset *set, const void *data)
50 : : {
51 : : assert(set);
52 : : assert(data);
53 : :
54 : 8766 : return set->ops.hash(data, set->ctx) % set->cap;
55 : : }
56 : :
57 : 3073 : static int _bf_hashset_resize(bf_hashset *set, size_t new_cap)
58 : : {
59 : : bf_hashset_elem **new_slots;
60 : :
61 : : assert(set);
62 : :
63 : : // We must have enough space for all elements.
64 [ + - ]: 3073 : if (new_cap <= set->len)
65 : : return -EINVAL;
66 : :
67 : 3073 : new_slots = (bf_hashset_elem **)calloc(new_cap, sizeof(*new_slots));
68 [ + - ]: 3073 : if (!new_slots)
69 : : return -ENOMEM;
70 : :
71 [ + + + + ]: 6648 : bf_hashset_foreach (set, elem) {
72 : 256 : size_t idx = set->ops.hash(elem->data, set->ctx) % new_cap;
73 [ - + ]: 256 : while (new_slots[idx])
74 : 0 : idx = (idx + 1) % new_cap;
75 [ + + ]: 256 : new_slots[idx] = elem;
76 : : }
77 : :
78 : 3073 : BF_FREEP(&set->slots);
79 : 3073 : set->slots = new_slots;
80 : 3073 : set->cap = new_cap;
81 : 3073 : set->slots_in_use = set->len;
82 : :
83 : 3073 : return 0;
84 : : }
85 : :
86 : 1983 : static int _bf_hashset_grow(bf_hashset *set)
87 : : {
88 : : size_t new_cap;
89 : :
90 : : assert(set);
91 : :
92 [ + - ]: 1983 : if (set->cap >= _BF_HASHSET_MAX_CAP)
93 : : return -ENOMEM;
94 [ + + ]: 1983 : new_cap = set->cap ? set->cap * 2 : _BF_HASHSET_INIT_CAP;
95 : :
96 : 1983 : return _bf_hashset_resize(set, new_cap);
97 : : }
98 : :
99 : : static bool _bf_hashset_needs_grow(const bf_hashset *set)
100 : : {
101 : : assert(set);
102 : :
103 : 6034 : return set->slots_in_use * _BF_HASHSET_MAX_LOAD_DEN >=
104 : 6034 : set->cap * _BF_HASHSET_MAX_LOAD_NUM;
105 : : }
106 : :
107 : : /**
108 : : * @brief Checks if an element is present in the hashset.
109 : : *
110 : : * If it is, also sets `found_index` to the index of the found element.
111 : : * If it is not, also sets `free_index` to the index of the first free slot,
112 : : * if there is any free slot.
113 : : *
114 : : * @param set Hashset to search. Can't be NULL.
115 : : * @param data Element to search for. Can't be NULL.
116 : : * @param found_index If non-NULL, set to the index of the matching element
117 : : * when found.
118 : : * @param free_index If non-NULL, set to the index of the first free slot
119 : : * when no match is found.
120 : : * @return true if the element was found, false otherwise.
121 : : */
122 : 10744 : static bool _bf_hashset_find(const bf_hashset *set, const void *data,
123 : : size_t *found_index, size_t *free_index)
124 : : {
125 : : size_t idx;
126 : : size_t first_free = SIZE_MAX;
127 : :
128 : : assert(set);
129 : : assert(data);
130 : :
131 [ + + ]: 10744 : if (set->cap == 0)
132 : : return false;
133 : :
134 : : idx = _bf_hashset_index(set, data);
135 : :
136 [ + - ]: 9211 : for (size_t i = 0; i < set->cap; ++i) {
137 : 9211 : bf_hashset_elem *slot = set->slots[idx];
138 : :
139 [ + + ]: 9211 : if (!slot) {
140 [ + + ]: 6193 : if (free_index)
141 [ + + ]: 12083 : *free_index = first_free != SIZE_MAX ? first_free : idx;
142 : : return false;
143 : : }
144 : :
145 [ + + ]: 3018 : if (_bf_hashset_slot_is_tombstone(slot)) {
146 [ + + ]: 26 : if (first_free == SIZE_MAX)
147 : : first_free = idx;
148 [ + + ]: 2992 : } else if (set->ops.equal(slot->data, data, set->ctx)) {
149 [ + + ]: 2573 : if (found_index)
150 : 1551 : *found_index = idx;
151 : : return true;
152 : : }
153 : :
154 : 445 : idx = (idx + 1) % set->cap;
155 : : }
156 : :
157 [ # # ]: 0 : if (free_index && first_free != SIZE_MAX)
158 : 0 : *free_index = first_free;
159 : :
160 : : return false;
161 : : }
162 : :
163 : 2 : int bf_hashset_new(bf_hashset **set, const bf_hashset_ops *ops, void *ctx)
164 : : {
165 : 2 : _free_bf_hashset_ bf_hashset *_set = NULL;
166 : :
167 : : assert(set);
168 : : assert(ops);
169 : : assert(ops->hash);
170 : : assert(ops->equal);
171 : :
172 : 2 : _set = calloc(1, sizeof(*_set));
173 [ + - ]: 2 : if (!_set)
174 : : return -ENOMEM;
175 : :
176 : 2 : bf_hashset_init(_set, ops, ctx);
177 : :
178 : 2 : *set = TAKE_PTR(_set);
179 : :
180 : 2 : return 0;
181 : : }
182 : :
183 : 4 : void bf_hashset_free(bf_hashset **set)
184 : : {
185 : : assert(set);
186 : :
187 [ + + ]: 4 : if (!*set)
188 : : return;
189 : :
190 : 2 : bf_hashset_clean(*set);
191 : 2 : BF_FREEP(set);
192 : : }
193 : :
194 : 2776 : void bf_hashset_init(bf_hashset *set, const bf_hashset_ops *ops, void *ctx)
195 : : {
196 : : assert(set);
197 : : assert(ops);
198 : : assert(ops->hash);
199 : : assert(ops->equal);
200 : :
201 : 2776 : *set = bf_hashset_default(ops, ctx);
202 : 2776 : }
203 : :
204 : 19789 : void bf_hashset_clean(bf_hashset *set)
205 : : {
206 : : assert(set);
207 : :
208 [ + + + + ]: 48507 : bf_hashset_foreach (set, elem) {
209 [ + + ]: 5983 : if (set->ops.free)
210 : 5232 : set->ops.free(&elem->data, set->ctx);
211 [ + + ]: 5983 : BF_FREEP(&elem);
212 : : }
213 : :
214 : 19789 : BF_FREEP(&set->slots);
215 : 19789 : set->cap = 0;
216 : 19789 : set->len = 0;
217 : 19789 : set->slots_in_use = 0;
218 : 19789 : set->head = NULL;
219 : 19789 : set->tail = NULL;
220 : 19789 : }
221 : :
222 : 3251 : size_t bf_hashset_size(const bf_hashset *set)
223 : : {
224 : : assert(set);
225 : 3251 : return set->len;
226 : : }
227 : :
228 : 6795 : bf_hashset bf_hashset_move(bf_hashset *set)
229 : : {
230 : : bf_hashset moved;
231 : :
232 : : assert(set);
233 : :
234 : 6795 : moved = *set;
235 : 6795 : *set = bf_hashset_default(&moved.ops, moved.ctx);
236 : :
237 : 6795 : return moved;
238 : : }
239 : :
240 : 3449 : bool bf_hashset_is_empty(const bf_hashset *set)
241 : : {
242 : : assert(set);
243 : 3449 : return set->len == 0;
244 : : }
245 : :
246 : 2566 : int bf_hashset_reserve(bf_hashset *set, size_t count)
247 : : {
248 : : size_t needed, new_cap;
249 : :
250 : : assert(set);
251 : :
252 [ + + ]: 2566 : if (count == 0)
253 : : return 0;
254 : :
255 [ + - ]: 1092 : if (count > _BF_HASHSET_MAX_CAP)
256 : : return -ENOMEM;
257 : :
258 : 1092 : needed = count * _BF_HASHSET_MAX_LOAD_DEN / _BF_HASHSET_MAX_LOAD_NUM;
259 [ + + ]: 1092 : if (needed <= set->cap)
260 : : return 0;
261 : :
262 : 1090 : new_cap = _bf_round_next_power_of_2(bf_max(needed, _BF_HASHSET_INIT_CAP));
263 [ + - ]: 1090 : if (new_cap > _BF_HASHSET_MAX_CAP)
264 : : return -ENOMEM;
265 : :
266 : 1090 : return _bf_hashset_resize(set, new_cap);
267 : : }
268 : :
269 : 6055 : int bf_hashset_add(bf_hashset *set, void **data)
270 : : {
271 : : bf_hashset_elem *elem;
272 : 6055 : size_t free_idx = SIZE_MAX;
273 : : bool was_tombstone;
274 : : int r;
275 : :
276 : : assert(set);
277 : : assert(data);
278 : : assert(*data);
279 : :
280 [ + + ]: 6055 : if (_bf_hashset_find(set, *data, NULL, &free_idx))
281 : : return -EEXIST;
282 : :
283 [ - + ]: 6034 : if (set->len >= _BF_HASHSET_MAX_CAP)
284 [ # # ]: 0 : return bf_err_r(-ENOMEM, "hashset reached maximum capacity");
285 : :
286 [ + + ]: 6034 : if (_bf_hashset_needs_grow(set)) {
287 : 1983 : r = _bf_hashset_grow(set);
288 [ + - ]: 1983 : if (r)
289 : : return r;
290 : : // Find new free_idx for this element.
291 [ + - ]: 1983 : if (_bf_hashset_find(set, *data, NULL, &free_idx))
292 : : return -EEXIST;
293 : : }
294 : :
295 : 6034 : elem = malloc(sizeof(*elem));
296 [ + - ]: 6034 : if (!elem)
297 : : return -ENOMEM;
298 : :
299 : 6034 : elem->data = TAKE_PTR(*data);
300 : :
301 : 6034 : was_tombstone = _bf_hashset_slot_is_tombstone(set->slots[free_idx]);
302 : 6034 : set->slots[free_idx] = elem;
303 : :
304 : 6034 : elem->prev = set->tail;
305 : 6034 : elem->next = NULL;
306 [ + + ]: 6034 : if (set->tail)
307 : 2970 : set->tail->next = elem;
308 : : else
309 : 3064 : set->head = elem;
310 : 6034 : set->tail = elem;
311 : :
312 : 6034 : ++set->len;
313 : :
314 [ + + ]: 6034 : if (!was_tombstone)
315 : 6029 : ++set->slots_in_use;
316 : :
317 : : return 0;
318 : : }
319 : :
320 : 1135 : bool bf_hashset_contains(const bf_hashset *set, const void *data)
321 : : {
322 : : assert(set);
323 : : assert(data);
324 : :
325 : 1135 : return _bf_hashset_find(set, data, NULL, NULL);
326 : : }
327 : :
328 : 1516 : void *bf_hashset_get(const bf_hashset *set, const void *key)
329 : : {
330 : : size_t index;
331 : :
332 : : assert(set);
333 : : assert(key);
334 : :
335 [ + + ]: 1516 : if (!_bf_hashset_find(set, key, &index, NULL))
336 : : return NULL;
337 : :
338 : 1500 : return set->slots[index]->data;
339 : : }
340 : :
341 : 51 : static void _bf_hashset_unlink(bf_hashset *set, size_t found_idx)
342 : : {
343 : 51 : bf_hashset_elem *elem = set->slots[found_idx];
344 : :
345 [ + + ]: 51 : if (elem->prev)
346 : 8 : elem->prev->next = elem->next;
347 : : else
348 : 43 : set->head = elem->next;
349 : :
350 [ + + ]: 51 : if (elem->next)
351 : 22 : elem->next->prev = elem->prev;
352 : : else
353 : 29 : set->tail = elem->prev;
354 : :
355 : 51 : set->slots[found_idx] = _BF_HASHSET_TOMBSTONE;
356 : 51 : BF_FREEP(&elem);
357 : 51 : --set->len;
358 : 51 : }
359 : :
360 : 26 : int bf_hashset_delete(bf_hashset *set, const void *data)
361 : : {
362 : 26 : size_t found_idx = SIZE_MAX;
363 : :
364 : : assert(set);
365 : : assert(data);
366 : :
367 [ + + ]: 26 : if (!_bf_hashset_find(set, data, &found_idx, NULL))
368 : : return -ENOENT;
369 : :
370 [ + - ]: 23 : if (set->ops.free)
371 : 23 : set->ops.free(&set->slots[found_idx]->data, set->ctx);
372 : :
373 : 23 : _bf_hashset_unlink(set, found_idx);
374 : :
375 : 23 : return 0;
376 : : }
377 : :
378 : 29 : int bf_hashset_take(bf_hashset *set, const void *key, void **data)
379 : : {
380 : 29 : size_t found_idx = SIZE_MAX;
381 : :
382 : : assert(set);
383 : : assert(key);
384 : : assert(data);
385 : :
386 [ + + ]: 29 : if (!_bf_hashset_find(set, key, &found_idx, NULL))
387 : : return -ENOENT;
388 : :
389 : 28 : *data = set->slots[found_idx]->data;
390 : 28 : _bf_hashset_unlink(set, found_idx);
391 : :
392 : 28 : return 0;
393 : : }
|
