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