Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2020 Intel Corporation
3 : : * Copyright(c) 2020, Alan Liu <zaoxingliu@gmail.com>
4 : : */
5 : :
6 : : #ifndef RTE_MEMBER_HEAP_H
7 : : #define RTE_MEMBER_HEAP_H
8 : :
9 : : #include "member.h"
10 : : #include <rte_ring_elem.h>
11 : : #include "rte_member.h"
12 : :
13 : : #define LCHILD(x) (2 * x + 1)
14 : : #define RCHILD(x) (2 * x + 2)
15 : : #define PARENT(x) ((x - 1) / 2)
16 : :
17 : : #define HASH_BKT_SIZE 16
18 : : #define HASH_HP_MULTI 4
19 : : #define HASH_RESIZE_MULTI 2
20 : :
21 : : struct hash_bkt {
22 : : uint16_t sig[HASH_BKT_SIZE];
23 : : uint16_t idx[HASH_BKT_SIZE];
24 : : };
25 : :
26 : : struct hash {
27 : : uint16_t bkt_cnt;
28 : : uint16_t num_item;
29 : : uint32_t seed;
30 : : struct hash_bkt buckets[];
31 : : };
32 : :
33 : : struct node {
34 : : void *key;
35 : : uint64_t count;
36 : : };
37 : :
38 : : struct minheap {
39 : : uint32_t key_len;
40 : : uint32_t size;
41 : : uint32_t socket;
42 : : struct hash *hashtable;
43 : : struct node *elem;
44 : : };
45 : :
46 : : static int
47 : 254 : hash_table_insert(const void *key, int value, int key_len, struct hash *table)
48 : : {
49 : 254 : uint32_t hash = MEMBER_HASH_FUNC(key, key_len, table->seed);
50 : 254 : uint16_t idx = hash % table->bkt_cnt;
51 : 254 : uint16_t sig = hash >> 16;
52 : : int i;
53 : :
54 [ + - ]: 527 : for (i = 0; i < HASH_BKT_SIZE; i++) {
55 [ + + ]: 527 : if (table->buckets[idx].idx[i] == 0) {
56 : 254 : table->buckets[idx].idx[i] = value;
57 : 254 : table->buckets[idx].sig[i] = sig;
58 : 254 : table->num_item++;
59 : 254 : return 0;
60 : : }
61 : : }
62 : :
63 : : return -ENOMEM;
64 : : }
65 : :
66 : : static int
67 : 1467 : hash_table_update(const void *key, int old_value, int value, int key_len, struct hash *table)
68 : : {
69 : 1467 : uint32_t hash = MEMBER_HASH_FUNC(key, key_len, table->seed);
70 : 1467 : uint16_t idx = hash % table->bkt_cnt;
71 : 1467 : uint16_t sig = hash >> 16;
72 : : int i;
73 : :
74 [ + - ]: 3381 : for (i = 0; i < HASH_BKT_SIZE; i++) {
75 [ + + + - ]: 3381 : if (table->buckets[idx].sig[i] == sig && table->buckets[idx].idx[i] == old_value) {
76 : 1467 : table->buckets[idx].idx[i] = value;
77 : 1467 : return 0;
78 : : }
79 : : }
80 : :
81 : : return -1;
82 : : }
83 : :
84 : : static int
85 : 206 : hash_table_del(const void *key, uint16_t value, int key_len, struct hash *table)
86 : : {
87 : 206 : uint32_t hash = MEMBER_HASH_FUNC(key, key_len, table->seed);
88 : 206 : uint16_t idx = hash % table->bkt_cnt;
89 : 206 : uint16_t sig = hash >> 16;
90 : : int i;
91 : :
92 [ + - ]: 410 : for (i = 0; i < HASH_BKT_SIZE; i++) {
93 [ + + + - ]: 410 : if (table->buckets[idx].sig[i] == sig && table->buckets[idx].idx[i] == value) {
94 : 206 : table->buckets[idx].idx[i] = 0;
95 : 206 : table->num_item--;
96 : 206 : return 0;
97 : : }
98 : : }
99 : :
100 : : return -1;
101 : : }
102 : :
103 : : static int
104 : 73189 : hash_table_lookup(const void *key, int key_len, struct minheap *hp)
105 : : {
106 : 73189 : struct hash *table = hp->hashtable;
107 : 73189 : uint32_t hash = MEMBER_HASH_FUNC(key, key_len, table->seed);
108 : 73189 : uint16_t idx = hash % table->bkt_cnt;
109 : 73189 : uint16_t sig = hash >> 16;
110 : : int i;
111 : :
112 [ + + ]: 174127 : for (i = 0; i < HASH_BKT_SIZE; i++) {
113 [ + + + + ]: 173873 : if (table->buckets[idx].sig[i] == sig && table->buckets[idx].idx[i] != 0) {
114 : 72935 : uint32_t hp_idx = table->buckets[idx].idx[i] - 1;
115 : :
116 [ + - ]: 72935 : if (memcmp(hp->elem[hp_idx].key, key, hp->key_len) == 0)
117 : 72935 : return hp_idx;
118 : : }
119 : : }
120 : :
121 : : return -ENOENT; /* key doesn't exist */
122 : : }
123 : :
124 : : static int
125 : 0 : resize_hash_table(struct minheap *hp)
126 : : {
127 : : uint32_t i;
128 : : uint32_t new_bkt_cnt;
129 : :
130 : : while (1) {
131 : 0 : new_bkt_cnt = hp->hashtable->bkt_cnt * HASH_RESIZE_MULTI;
132 : :
133 : 0 : MEMBER_LOG(ERR, "Sketch Minheap HT load factor is [%f]",
134 : : hp->hashtable->num_item / ((float)hp->hashtable->bkt_cnt * HASH_BKT_SIZE));
135 : 0 : MEMBER_LOG(ERR, "Sketch Minheap HT resize happen!");
136 : 0 : rte_free(hp->hashtable);
137 : 0 : hp->hashtable = rte_zmalloc_socket(NULL, sizeof(struct hash) +
138 : 0 : new_bkt_cnt * sizeof(struct hash_bkt),
139 : 0 : RTE_CACHE_LINE_SIZE, hp->socket);
140 : :
141 [ # # ]: 0 : if (hp->hashtable == NULL) {
142 : 0 : MEMBER_LOG(ERR, "Sketch Minheap HT allocation failed");
143 : 0 : return -ENOMEM;
144 : : }
145 : :
146 : 0 : hp->hashtable->bkt_cnt = new_bkt_cnt;
147 : :
148 [ # # ]: 0 : for (i = 0; i < hp->size; ++i) {
149 [ # # ]: 0 : if (hash_table_insert(hp->elem[i].key,
150 : 0 : i + 1, hp->key_len, hp->hashtable) < 0) {
151 : 0 : MEMBER_LOG(ERR,
152 : : "Sketch Minheap HT resize insert fail!");
153 : 0 : break;
154 : : }
155 : : }
156 [ # # ]: 0 : if (i == hp->size)
157 : : break;
158 : : }
159 : :
160 : : return 0;
161 : : }
162 : :
163 : : /* find the item in the given minheap */
164 : : static int
165 : : rte_member_minheap_find(struct minheap *hp, const void *key)
166 : : {
167 : 73187 : int idx = hash_table_lookup(key, hp->key_len, hp);
168 : : return idx;
169 : : }
170 : :
171 : : static int
172 : 4 : rte_member_minheap_init(struct minheap *heap, int size,
173 : : uint32_t socket, uint32_t seed)
174 : : {
175 : 4 : heap->elem = rte_zmalloc_socket(NULL, sizeof(struct node) * size,
176 : : RTE_CACHE_LINE_SIZE, socket);
177 [ - + ]: 4 : if (heap->elem == NULL) {
178 : 0 : MEMBER_LOG(ERR, "Sketch Minheap elem allocation failed");
179 : 0 : return -ENOMEM;
180 : : }
181 : :
182 [ - + ]: 4 : uint32_t hash_bkt_cnt = rte_align32pow2(size * HASH_HP_MULTI) / HASH_BKT_SIZE;
183 : :
184 [ - + ]: 4 : if (hash_bkt_cnt == 0)
185 : : hash_bkt_cnt = 1;
186 : :
187 : 8 : heap->hashtable = rte_zmalloc_socket(NULL, sizeof(struct hash) +
188 : 4 : hash_bkt_cnt * sizeof(struct hash_bkt),
189 : : RTE_CACHE_LINE_SIZE, socket);
190 : :
191 [ - + ]: 4 : if (heap->hashtable == NULL) {
192 : 0 : MEMBER_LOG(ERR, "Sketch Minheap HT allocation failed");
193 : 0 : rte_free(heap->elem);
194 : 0 : return -ENOMEM;
195 : : }
196 : :
197 : 4 : heap->hashtable->seed = seed;
198 : 4 : heap->hashtable->bkt_cnt = hash_bkt_cnt;
199 : 4 : heap->socket = socket;
200 : :
201 : 4 : return 0;
202 : : }
203 : :
204 : : /* swap the minheap nodes */
205 : : static __rte_always_inline void
206 : : rte_member_heap_swap(struct node *n1, struct node *n2)
207 : : {
208 : 566 : struct node temp = *n1;
209 : 566 : *n1 = *n2;
210 : 566 : *n2 = temp;
211 : : }
212 : :
213 : : /* heapify function */
214 : : static void
215 : 29286 : rte_member_heapify(struct minheap *hp, uint32_t idx, bool update_hash)
216 : : {
217 : : uint32_t smallest;
218 : :
219 [ + + ]: 29286 : if (LCHILD(idx) < hp->size &&
220 [ + + ]: 7294 : hp->elem[LCHILD(idx)].count < hp->elem[idx].count)
221 : 399 : smallest = LCHILD(idx);
222 : : else
223 : : smallest = idx;
224 : :
225 [ + + ]: 29286 : if (RCHILD(idx) < hp->size &&
226 [ + + ]: 6001 : hp->elem[RCHILD(idx)].count < hp->elem[smallest].count)
227 : : smallest = RCHILD(idx);
228 : :
229 [ + + ]: 29286 : if (smallest != idx) {
230 : 514 : rte_member_heap_swap(&(hp->elem[idx]), &(hp->elem[smallest]));
231 : :
232 [ + + ]: 514 : if (update_hash) {
233 [ - + ]: 446 : if (hash_table_update(hp->elem[smallest].key, idx + 1, smallest + 1,
234 : 446 : hp->key_len, hp->hashtable) < 0) {
235 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table update failed");
236 : 0 : return;
237 : : }
238 : :
239 [ - + ]: 446 : if (hash_table_update(hp->elem[idx].key, smallest + 1, idx + 1,
240 : : hp->key_len, hp->hashtable) < 0) {
241 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table update failed");
242 : 0 : return;
243 : : }
244 : : }
245 : 514 : rte_member_heapify(hp, smallest, update_hash);
246 : : }
247 : : }
248 : :
249 : : /* insert a node into the minheap */
250 : : static int
251 : 50 : rte_member_minheap_insert_node(struct minheap *hp, const void *key,
252 : : int counter, void *key_slot,
253 : : struct rte_ring *free_key_slot)
254 : : {
255 : : struct node nd;
256 : : uint32_t slot_id;
257 : :
258 : : if (rte_ring_sc_dequeue_elem(free_key_slot, &slot_id, sizeof(uint32_t)) != 0) {
259 : 0 : MEMBER_LOG(ERR, "Minheap get empty keyslot failed");
260 : 0 : return -1;
261 : : }
262 : :
263 : 50 : nd.count = counter;
264 : 50 : nd.key = RTE_PTR_ADD(key_slot, slot_id * hp->key_len);
265 : :
266 : 50 : memcpy(nd.key, key, hp->key_len);
267 : :
268 : 50 : uint32_t i = (hp->size)++;
269 : :
270 [ + + + + ]: 51 : while (i && nd.count < hp->elem[PARENT(i)].count) {
271 : 1 : hp->elem[i] = hp->elem[PARENT(i)];
272 [ - + ]: 1 : if (hash_table_update(hp->elem[i].key, PARENT(i) + 1, i + 1,
273 : 1 : hp->key_len, hp->hashtable) < 0) {
274 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table update failed");
275 : 0 : return -1;
276 : : }
277 : : i = PARENT(i);
278 : : }
279 : 50 : hp->elem[i] = nd;
280 : :
281 [ - + ]: 50 : if (hash_table_insert(key, i + 1, hp->key_len, hp->hashtable) < 0) {
282 [ # # ]: 0 : if (resize_hash_table(hp) < 0) {
283 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table resize failed");
284 : 0 : return -1;
285 : : }
286 : : }
287 : :
288 : : return 0;
289 : : }
290 : :
291 : : /* delete a key from the minheap */
292 : : static int
293 : 2 : rte_member_minheap_delete_node(struct minheap *hp, const void *key,
294 : : void *key_slot, struct rte_ring *free_key_slot)
295 : : {
296 : : int idx = rte_member_minheap_find(hp, key);
297 : 2 : uint32_t offset = RTE_PTR_DIFF(hp->elem[idx].key, key_slot) / hp->key_len;
298 : :
299 [ - + ]: 2 : if (hash_table_del(key, idx + 1, hp->key_len, hp->hashtable) < 0) {
300 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table delete failed");
301 : 0 : return -1;
302 : : }
303 : :
304 : : rte_ring_sp_enqueue_elem(free_key_slot, &offset, sizeof(uint32_t));
305 : :
306 [ - + ]: 2 : if (idx == (int)(hp->size - 1)) {
307 : 0 : hp->size--;
308 : 0 : return 0;
309 : : }
310 : :
311 : 2 : hp->elem[idx] = hp->elem[hp->size - 1];
312 : :
313 [ - + ]: 2 : if (hash_table_update(hp->elem[idx].key, hp->size, idx + 1,
314 : 2 : hp->key_len, hp->hashtable) < 0) {
315 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table update failed");
316 : 0 : return -1;
317 : : }
318 : 2 : hp->size--;
319 : 2 : rte_member_heapify(hp, idx, true);
320 : :
321 : 2 : return 0;
322 : : }
323 : :
324 : : /* replace a min node with a new key. */
325 : : static int
326 : 204 : rte_member_minheap_replace_node(struct minheap *hp,
327 : : const void *new_key,
328 : : int new_counter)
329 : : {
330 : : struct node nd;
331 : : void *recycle_key = NULL;
332 : :
333 : 204 : recycle_key = hp->elem[0].key;
334 : :
335 [ - + ]: 204 : if (hash_table_del(recycle_key, 1, hp->key_len, hp->hashtable) < 0) {
336 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table delete failed");
337 : 0 : return -1;
338 : : }
339 : :
340 : 204 : hp->elem[0] = hp->elem[hp->size - 1];
341 : :
342 [ - + ]: 204 : if (hash_table_update(hp->elem[0].key, hp->size, 1,
343 : : hp->key_len, hp->hashtable) < 0) {
344 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table update failed");
345 : 0 : return -1;
346 : : }
347 : 204 : hp->size--;
348 : :
349 : 204 : rte_member_heapify(hp, 0, true);
350 : :
351 : 204 : nd.count = new_counter;
352 : : nd.key = recycle_key;
353 : :
354 : 204 : memcpy(nd.key, new_key, hp->key_len);
355 : :
356 : 204 : uint32_t i = (hp->size)++;
357 : :
358 [ + + + + ]: 572 : while (i && nd.count < hp->elem[PARENT(i)].count) {
359 : 368 : hp->elem[i] = hp->elem[PARENT(i)];
360 [ - + ]: 368 : if (hash_table_update(hp->elem[i].key, PARENT(i) + 1, i + 1,
361 : 368 : hp->key_len, hp->hashtable) < 0) {
362 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table update failed");
363 : 0 : return -1;
364 : : }
365 : : i = PARENT(i);
366 : : }
367 : :
368 : 204 : hp->elem[i] = nd;
369 : :
370 [ - + ]: 204 : if (hash_table_insert(new_key, i + 1, hp->key_len, hp->hashtable) < 0) {
371 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table replace insert failed");
372 [ # # ]: 0 : if (resize_hash_table(hp) < 0) {
373 : 0 : MEMBER_LOG(ERR, "Minheap Hash Table replace resize failed");
374 : 0 : return -1;
375 : : }
376 : : }
377 : :
378 : : return 0;
379 : : }
380 : :
381 : : /* sort the heap into a descending array */
382 : : static void
383 : 6 : rte_member_heapsort(struct minheap *hp, struct node *result_array)
384 : : {
385 : : struct minheap new_hp;
386 : :
387 : : /* build a new heap for using the given array */
388 : 6 : new_hp.size = hp->size;
389 : 6 : new_hp.key_len = hp->key_len;
390 : 6 : new_hp.elem = result_array;
391 : 6 : memcpy(result_array, hp->elem, hp->size * sizeof(struct node));
392 : :
393 : : /* sort the new heap */
394 [ + + ]: 58 : while (new_hp.size > 1) {
395 : 52 : rte_member_heap_swap(&(new_hp.elem[0]), &(new_hp.elem[new_hp.size - 1]));
396 : 52 : new_hp.size--;
397 : 52 : rte_member_heapify(&new_hp, 0, false);
398 : : }
399 : 6 : }
400 : :
401 : : static void
402 : 4 : rte_member_minheap_free(struct minheap *hp)
403 : : {
404 [ + - ]: 4 : if (hp == NULL)
405 : : return;
406 : :
407 : 4 : rte_free(hp->elem);
408 : 4 : rte_free(hp->hashtable);
409 : : }
410 : :
411 : : static void
412 : 1 : rte_member_minheap_reset(struct minheap *hp)
413 : : {
414 [ + - ]: 1 : if (hp == NULL)
415 : : return;
416 : :
417 : 1 : memset(hp->elem, 0, sizeof(struct node) * hp->size);
418 : 1 : hp->size = 0;
419 : :
420 : 1 : memset((char *)hp->hashtable + sizeof(struct hash), 0,
421 : 1 : hp->hashtable->bkt_cnt * sizeof(struct hash_bkt));
422 : 1 : hp->hashtable->num_item = 0;
423 : : }
424 : :
425 : : #endif /* RTE_MEMBER_HEAP_H */
|
