Line data Source code
1 : /*
2 : * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
3 : * Copyright Contributors to the OpenSDN project
4 : */
5 : #include <vr_os.h>
6 : #include <vrouter.h>
7 : #include <vr_htable.h>
8 : #include <vr_btable.h>
9 : #include <vr_hash.h>
10 : #include <vrouter.h>
11 :
12 : #define VR_HENTRIES_PER_BUCKET 4
13 :
14 : #define VR_HENTRY_FLAG_VALID 0x1
15 : #define VR_HENTRY_FLAG_DELETE_MARKED 0x2
16 : #define VR_HENTRY_FLAG_DELETE_PROCESSED 0x4
17 : #define VR_HENTRY_FLAG_UNDER_DELETION (VR_HENTRY_FLAG_DELETE_MARKED | \
18 : VR_HENTRY_FLAG_DELETE_PROCESSED)
19 : #define VR_HENTRY_FLAG_IN_FREE_LIST 0x8
20 :
21 :
22 : struct vr_htable {
23 : struct vrouter *ht_router;
24 : unsigned int ht_hentries;
25 : unsigned int ht_oentries;
26 : unsigned int ht_entry_size;
27 : unsigned int ht_key_size;
28 : unsigned int ht_bucket_size;
29 : struct vr_btable *ht_htable;
30 : struct vr_btable *ht_otable;
31 : struct vr_btable *ht_dtable;
32 : get_hentry_key ht_get_key;
33 : vr_hentry_t *ht_free_oentry_head;
34 : unsigned int ht_used_oentries;
35 : unsigned int ht_used_entries;
36 : };
37 :
38 : struct vr_hentry_delete_data {
39 : struct vr_htable *hd_table;
40 : unsigned int hd_index;
41 : unsigned short hd_count;
42 : unsigned short hd_scheduled;
43 : };
44 :
45 : void vr_htable_hentry_scheduled_delete(void *arg);
46 :
47 : int
48 6321 : vr_htable_trav_range(vr_htable_t htable, unsigned int start,
49 : unsigned int range, htable_trav_cb cb, void *data)
50 : {
51 6321 : unsigned int i, hindex = 0;
52 : vr_hentry_t *ent;
53 6321 : struct vr_htable *table = (struct vr_htable *)htable;
54 :
55 6321 : if (!table || !cb)
56 0 : return -EINVAL;
57 :
58 21111985 : for (i = start; i < start + range; i++) {
59 21105664 : hindex = i % (table->ht_oentries + table->ht_hentries);
60 21105664 : ent = vr_htable_get_hentry_by_index(htable, hindex);
61 21105664 : cb(htable, ent, hindex, data);
62 : }
63 :
64 6321 : return hindex;
65 : }
66 :
67 : int
68 13 : vr_htable_trav(vr_htable_t htable, unsigned int marker,
69 : htable_trav_cb cb, void *data)
70 : {
71 : unsigned int range;
72 13 : struct vr_htable *table = (struct vr_htable *)htable;
73 13 : if(!table)
74 0 : return -EINVAL;
75 :
76 13 : range = (table->ht_hentries + table->ht_oentries - marker);
77 13 : return vr_htable_trav_range(htable, marker, range, cb, data);
78 :
79 : }
80 :
81 : static vr_hentry_t *
82 0 : vr_htable_get_free_oentry(struct vr_htable *table)
83 : {
84 : vr_hentry_t *ent;
85 :
86 0 : if (!table)
87 0 : return NULL;
88 :
89 : do {
90 :
91 : /*
92 : * Get the head of the free list. And move the head to next free
93 : * entry. This can become NULL while the loop is in progress
94 : */
95 0 : ent = table->ht_free_oentry_head;
96 0 : if (!ent)
97 0 : return NULL;
98 :
99 0 : if (vr_sync_bool_compare_and_swap_p(&table->ht_free_oentry_head,
100 : ent, ent->hentry_next)) {
101 0 : ent->hentry_next = NULL;
102 0 : (void)vr_sync_add_and_fetch_32u(&table->ht_used_oentries, 1);
103 0 : ent->hentry_flags &= ~VR_HENTRY_FLAG_IN_FREE_LIST;
104 0 : return ent;
105 : }
106 :
107 : } while (1);
108 :
109 : return NULL;
110 : }
111 :
112 : static void
113 0 : vr_htable_put_free_oentry(struct vr_htable *table, vr_hentry_t *ent)
114 : {
115 :
116 : vr_hentry_t *tmp;
117 :
118 0 : if (!table || !ent || ent->hentry_index < table->ht_hentries)
119 0 : return;
120 :
121 0 : if (ent->hentry_flags & VR_HENTRY_FLAG_IN_FREE_LIST)
122 0 : return;
123 :
124 0 : ent->hentry_flags |= VR_HENTRY_FLAG_IN_FREE_LIST;
125 :
126 0 : tmp = NULL;
127 : do {
128 :
129 : /*
130 : * Insert this new entry as head.
131 : */
132 0 : tmp = table->ht_free_oentry_head;
133 0 : ent->hentry_next = tmp;
134 :
135 0 : if (vr_sync_bool_compare_and_swap_p(&table->ht_free_oentry_head,
136 : tmp, ent)) {
137 0 : (void)vr_sync_sub_and_fetch_32u(&table->ht_used_oentries, 1);
138 0 : return;
139 : }
140 :
141 : } while (1);
142 :
143 : return;
144 : }
145 :
146 :
147 : /*
148 : * Returns the hash entry given an index. Does not validate whether the
149 : * entry is Valid or not
150 : */
151 : vr_hentry_t *
152 71199878 : __vr_htable_get_hentry_by_index(vr_htable_t htable, unsigned int index)
153 : {
154 71199878 : struct vr_htable *table = (struct vr_htable *)htable;
155 :
156 71199878 : if (!table)
157 0 : return NULL;
158 :
159 71199878 : if (index < table->ht_hentries)
160 60007905 : return vr_btable_get(table->ht_htable, index);
161 :
162 11191973 : if (index < (table->ht_oentries + table->ht_hentries))
163 11191973 : return vr_btable_get(table->ht_otable, (index - table->ht_hentries));
164 :
165 0 : return NULL;
166 : }
167 :
168 : /*
169 : * Returns the hash entry, given an index, only if Valid
170 : */
171 : vr_hentry_t *
172 21106822 : vr_htable_get_hentry_by_index(vr_htable_t htable, unsigned int index)
173 : {
174 : vr_hentry_t *ent;
175 :
176 21106822 : ent = __vr_htable_get_hentry_by_index(htable, index);
177 21106822 : if (ent && (ent->hentry_flags & VR_HENTRY_FLAG_VALID))
178 1114 : return ent;
179 :
180 21105708 : return NULL;
181 : }
182 :
183 : static void
184 0 : vr_htable_oentry_invalidate(struct vr_htable *table, vr_hentry_t *ent)
185 : {
186 0 : if (!table || !ent || (ent->hentry_index < table->ht_hentries))
187 0 : return;
188 :
189 : /* Clear all the flags except free list */
190 0 : ent->hentry_flags &= VR_HENTRY_FLAG_IN_FREE_LIST;
191 0 : ent->hentry_bucket_index = VR_INVALID_HENTRY_INDEX;
192 0 : ent->hentry_next_index = VR_INVALID_HENTRY_INDEX;
193 0 : ent->hentry_next = NULL;
194 :
195 0 : vr_htable_put_free_oentry(table, ent);
196 : }
197 :
198 : static void
199 0 : vr_htable_hentry_defer_delete(struct vrouter *router, void *arg)
200 : {
201 : vr_hentry_t *ent;
202 : struct vr_hentry_delete_data *defer_data;
203 : struct vr_htable *table;
204 :
205 0 : defer_data = (struct vr_hentry_delete_data *)arg;
206 0 : table = (struct vr_htable *)(defer_data->hd_table);
207 :
208 0 : ent = __vr_htable_get_hentry_by_index((vr_htable_t)table,
209 : defer_data->hd_index);
210 0 : vr_htable_oentry_invalidate(table, ent);
211 :
212 0 : return;
213 : }
214 :
215 : void
216 0 : vr_htable_hentry_scheduled_delete(void *arg)
217 : {
218 : unsigned int count;
219 : struct vr_hentry_delete_data *delete_data, *defer_data;
220 : vr_hentry_t *head_ent, *ent, *prev, *next;
221 : struct vr_htable *table;
222 :
223 :
224 0 : delete_data = (struct vr_hentry_delete_data *)arg;
225 0 : table = delete_data->hd_table;
226 :
227 0 : head_ent = __vr_htable_get_hentry_by_index((vr_htable_t)(table),
228 : delete_data->hd_index);
229 :
230 0 : if (!head_ent)
231 0 : return;
232 :
233 0 : (void)vr_sync_bool_compare_and_swap_16u(&delete_data->hd_scheduled, 1, 0);
234 :
235 : /*
236 : * We attempt to delete only those many entries that have been
237 : * delete marked. If some new entries are delete marked while
238 : * processing these, they will get scheduled in new work item
239 : */
240 0 : count = delete_data->hd_count;
241 0 : (void)vr_sync_sub_and_fetch_16u(&delete_data->hd_count, count);
242 :
243 0 : prev = head_ent;
244 0 : ent = vr_sync_fetch_and_add_64u(&head_ent->hentry_next, 0);
245 :
246 0 : while (count && ent) {
247 :
248 : /*
249 : * Process only if delete marked. If already processed,
250 : * delete marking is changed to delete processed
251 : */
252 0 : if (ent->hentry_flags & VR_HENTRY_FLAG_DELETE_MARKED) {
253 :
254 : /*
255 : * As the insertion happens only at head entry, it has
256 : * to be verified if something is inserted while delete
257 : * attemped. If inserted, traversal needs to restart, to
258 : * get hold of the new previous
259 : */
260 0 : if (prev == head_ent) {
261 0 : if (!vr_sync_bool_compare_and_swap_p(&prev->hentry_next,
262 : ent, ent->hentry_next)) {
263 0 : prev = head_ent;
264 0 : ent = head_ent->hentry_next;
265 0 : continue;
266 : }
267 : } else {
268 0 : prev->hentry_next = ent->hentry_next;
269 : }
270 :
271 0 : count--;
272 :
273 : /* update next index for the previous */
274 0 : if (ent->hentry_next)
275 0 : prev->hentry_next_index = ent->hentry_next->hentry_index;
276 : else
277 0 : prev->hentry_next_index = VR_INVALID_HENTRY_INDEX;
278 :
279 0 : ent->hentry_flags &= ~VR_HENTRY_FLAG_DELETE_MARKED;
280 0 : ent->hentry_flags |= VR_HENTRY_FLAG_DELETE_PROCESSED;
281 : }
282 :
283 0 : next = ent->hentry_next;
284 :
285 : /*
286 : * A separate check for VR_HENTRY_FLAG_DELETE_PROCESSED flag to
287 : * defer the entry if we ever failed to allocate memeory while
288 : * deferring it
289 : */
290 0 : if (ent->hentry_flags & VR_HENTRY_FLAG_DELETE_PROCESSED) {
291 :
292 : /*
293 : * Defer the entry to reset the values. If alloc of
294 : * defer data fails, this entry will be in delete state
295 : * for ever
296 : */
297 0 : if (!vr_not_ready) {
298 0 : defer_data = vr_get_defer_data(sizeof(*defer_data));
299 0 : if (defer_data) {
300 0 : defer_data->hd_table = delete_data->hd_table;
301 0 : defer_data->hd_index = ent->hentry_index;
302 0 : vr_defer(delete_data->hd_table->ht_router,
303 : vr_htable_hentry_defer_delete, (void *)defer_data);
304 : }
305 : } else {
306 0 : vr_htable_oentry_invalidate(table, ent);
307 0 : ent = next;
308 0 : continue;
309 : }
310 : }
311 :
312 : /* Previous should not be under deletion */
313 0 : if (!(ent->hentry_flags & VR_HENTRY_FLAG_UNDER_DELETION))
314 0 : prev = ent;
315 :
316 0 : ent = next;
317 : }
318 :
319 0 : return;
320 : }
321 :
322 : void
323 106 : vr_htable_reset(vr_htable_t htable, htable_trav_cb cb, void *data)
324 : {
325 : unsigned int i;
326 : vr_hentry_t *ent, *next;
327 106 : struct vr_htable *table = (struct vr_htable *)htable;
328 :
329 106 : if (!table || !cb)
330 0 : return;
331 :
332 50093162 : for (i = 0; i < table->ht_hentries + table->ht_oentries; i++) {
333 50093056 : ent = __vr_htable_get_hentry_by_index(htable, i);
334 :
335 50093056 : cb(htable, ent, i, data);
336 :
337 50093056 : if (ent->hentry_flags & VR_HENTRY_FLAG_VALID) {
338 0 : ent->hentry_flags &= ~VR_HENTRY_FLAG_VALID;
339 0 : (void)vr_sync_sub_and_fetch_32u(&table->ht_used_entries, 1);
340 : }
341 :
342 :
343 50093056 : if ((i < table->ht_hentries) && ent->hentry_next) {
344 0 : next = ent->hentry_next;
345 0 : ent->hentry_next = NULL;
346 0 : ent->hentry_next_index = VR_INVALID_HENTRY_INDEX;
347 0 : ent = next;
348 :
349 0 : while (ent) {
350 0 : next = ent->hentry_next;
351 :
352 0 : if (ent->hentry_flags & VR_HENTRY_FLAG_VALID) {
353 0 : ent->hentry_flags &= ~VR_HENTRY_FLAG_VALID;
354 0 : (void)vr_sync_sub_and_fetch_32u(&table->ht_used_entries, 1);
355 : }
356 :
357 0 : vr_htable_oentry_invalidate(table, ent);
358 :
359 0 : ent = next;
360 : }
361 : }
362 : }
363 :
364 106 : return;
365 : }
366 :
367 :
368 : void
369 16715983 : vr_htable_release_hentry(vr_htable_t htable, vr_hentry_t *ent)
370 : {
371 : unsigned int cpu_num, delete_index;
372 : struct vr_hentry_delete_data *delete_data;
373 : vr_hentry_t *head_ent;
374 16715983 : struct vr_htable *table = (struct vr_htable *)htable;
375 :
376 16715983 : if (!(ent->hentry_flags & VR_HENTRY_FLAG_VALID))
377 16715783 : return;
378 :
379 200 : (void)vr_sync_sub_and_fetch_32u(&table->ht_used_entries, 1);
380 :
381 : /* Mark it as Invalid */
382 200 : ent->hentry_flags &= ~VR_HENTRY_FLAG_VALID;
383 :
384 200 : if (ent->hentry_index < table->ht_hentries)
385 200 : return;
386 :
387 0 : if (vr_not_ready)
388 0 : return;
389 :
390 0 : ent->hentry_flags |= VR_HENTRY_FLAG_DELETE_MARKED;
391 :
392 0 : head_ent = __vr_htable_get_hentry_by_index(htable, ent->hentry_bucket_index);
393 0 : delete_index = head_ent->hentry_index / table->ht_bucket_size;
394 0 : delete_data = vr_btable_get(table->ht_dtable, delete_index);
395 :
396 0 : (void)vr_sync_add_and_fetch_16u(&delete_data->hd_count, 1);
397 :
398 : /* Schedule the deltion only if it is not already scheduled */
399 0 : if (vr_sync_bool_compare_and_swap_16u(&delete_data->hd_scheduled, 0, 1)) {
400 :
401 0 : delete_data->hd_table = (struct vr_htable *)htable;
402 0 : delete_data->hd_index = head_ent->hentry_index;
403 :
404 : /* Schedule the deletion on a cpu based on bucket index */
405 0 : cpu_num = head_ent->hentry_index % vr_num_cpus;
406 0 : if (vr_schedule_work(cpu_num, vr_htable_hentry_scheduled_delete,
407 : (void *)delete_data)) {
408 : /*
409 : * We can only write back the status as not scheduled. There
410 : * might be some entries that get marked as Deleted, but
411 : * would not be pushed to free list as work queue is not
412 : * scheduled. These marked entries would be deleted only if
413 : * this hash bucket is revisisted
414 : */
415 0 : (void)vr_sync_bool_compare_and_swap_16u(&delete_data->hd_scheduled,1, 0);
416 : }
417 : }
418 :
419 0 : return;
420 : }
421 :
422 : vr_hentry_t *
423 200 : vr_htable_find_free_hentry(vr_htable_t htable, void *key, unsigned int key_size)
424 : {
425 : unsigned int hash, tmp_hash, i;
426 200 : struct vr_htable *table = (struct vr_htable *)htable;
427 : vr_hentry_t *ent, *o_ent;
428 : int ind, bucket_index;
429 :
430 200 : if (!table || !key)
431 0 : return NULL;
432 :
433 200 : if (!key_size) {
434 91 : key_size = table->ht_key_size;
435 91 : if (!key_size)
436 0 : return NULL;
437 : }
438 :
439 200 : hash = vr_hash(key, key_size, 0);
440 200 : tmp_hash = hash % table->ht_hentries;
441 200 : tmp_hash &= ~(table->ht_bucket_size - 1);
442 :
443 200 : ind = 0;
444 200 : ent = NULL;
445 200 : for (i = 0; i < table->ht_bucket_size; i++) {
446 200 : ind = tmp_hash + i;
447 200 : ent = vr_btable_get(table->ht_htable, ind);
448 200 : if (!(ent->hentry_flags & VR_HENTRY_FLAG_VALID)) {
449 200 : if (vr_sync_bool_compare_and_swap_8u(&ent->hentry_flags,
450 : (ent->hentry_flags & ~VR_HENTRY_FLAG_VALID),
451 : VR_HENTRY_FLAG_VALID)) {
452 200 : ent->hentry_bucket_index = VR_INVALID_HENTRY_INDEX;
453 200 : (void)vr_sync_add_and_fetch_32u(&table->ht_used_entries, 1);
454 200 : return ent;
455 : }
456 : }
457 : }
458 :
459 0 : bucket_index = ind;
460 :
461 0 : if (table->ht_oentries) {
462 :
463 0 : o_ent = vr_htable_get_free_oentry(table);
464 0 : if (!o_ent) {
465 0 : return NULL;
466 : }
467 :
468 0 : o_ent->hentry_bucket_index = bucket_index;
469 0 : o_ent->hentry_next_index = VR_INVALID_HENTRY_INDEX;
470 0 : o_ent->hentry_flags = VR_HENTRY_FLAG_VALID;
471 :
472 : /* Link the overflow entry at the start */
473 : do {
474 0 : o_ent->hentry_next = vr_sync_fetch_and_add_64u(&ent->hentry_next, 0);
475 :
476 : /* Update the next entry's index in o_ent */
477 0 : if (o_ent->hentry_next)
478 0 : o_ent->hentry_next_index = o_ent->hentry_next->hentry_index;
479 :
480 0 : if (vr_sync_bool_compare_and_swap_p(&ent->hentry_next,
481 : o_ent->hentry_next, o_ent)) {
482 :
483 : /*
484 : * ent->hentry_next need not be o_ent for the below
485 : * statement, if some new entry is inserted after 'ent'.
486 : * So updating hentry_next_index by taking hentry_next
487 : * pointer should still do the right thing
488 : */
489 0 : ent->hentry_next_index = ent->hentry_next->hentry_index;
490 0 : (void)vr_sync_add_and_fetch_32u(&table->ht_used_entries, 1);
491 0 : return o_ent;
492 : }
493 : } while (1);
494 : }
495 :
496 0 : return NULL;
497 : }
498 :
499 : int
500 0 : vr_htable_find_duplicate_hentry_index(vr_htable_t htable, vr_hentry_t *hentry)
501 : {
502 : unsigned int hash, tmp_hash, ind, i, key_len, ent_key_len;
503 : vr_hentry_t *ent;
504 : vr_hentry_key hkey;
505 0 : struct vr_htable *table = (struct vr_htable *)htable;
506 :
507 0 : if (!table || !hentry)
508 0 : return -1;
509 :
510 0 : hkey = table->ht_get_key(htable, hentry, &key_len);
511 0 : if (!key_len) {
512 0 : key_len = table->ht_key_size;
513 0 : if (!key_len)
514 0 : return -1;
515 : }
516 :
517 0 : hash = vr_hash(hkey, key_len, 0);
518 :
519 : /* Look into the hash table from hash */
520 0 : tmp_hash = hash % table->ht_hentries;
521 0 : tmp_hash &= ~(table->ht_bucket_size - 1);
522 0 : for (i = 0; i < table->ht_bucket_size; i++) {
523 0 : ind = tmp_hash + i;
524 0 : ent = vr_btable_get(table->ht_htable, ind);
525 :
526 0 : if (ent->hentry_index == VR_INVALID_HENTRY_INDEX)
527 0 : continue;
528 :
529 0 : if (ent == hentry)
530 0 : continue;
531 :
532 0 : hkey = table->ht_get_key(htable, ent, &ent_key_len);
533 0 : if (!hkey || (ent_key_len != key_len))
534 0 : continue;
535 :
536 0 : if (memcmp(hkey, hentry, key_len) != 0)
537 0 : continue;
538 0 : return ind;
539 : }
540 :
541 : /* Look into the complete over flow table starting from hash*/
542 0 : tmp_hash = hash % table->ht_oentries;
543 0 : for (i = 0; i < table->ht_oentries; i++) {
544 0 : ind = table->ht_hentries + ((tmp_hash + i) % table->ht_oentries);
545 0 : ent = vr_btable_get(table->ht_otable, ((tmp_hash + i) % table->ht_oentries));
546 :
547 0 : if (ent->hentry_index == VR_INVALID_HENTRY_INDEX)
548 0 : continue;
549 :
550 0 : if (ent == hentry)
551 0 : continue;
552 :
553 0 : hkey = table->ht_get_key(htable, ent, &ent_key_len);
554 0 : if (!hkey || (ent_key_len != key_len))
555 0 : continue;
556 :
557 0 : if (memcmp(hkey, hentry, table->ht_key_size) != 0)
558 0 : continue;
559 :
560 0 : return ind;
561 : }
562 :
563 : /* No duplicate entry is found */
564 0 : return -1;
565 : }
566 :
567 : vr_hentry_t *
568 526 : vr_htable_find_hentry(vr_htable_t htable, void *key, unsigned int key_len)
569 : {
570 : unsigned int hash, tmp_hash, ind, i, ent_key_len;
571 : vr_hentry_t *ent, *o_ent;
572 : vr_hentry_key ent_key;
573 526 : struct vr_htable *table = (struct vr_htable *)htable;
574 :
575 526 : if (!table || !key)
576 0 : return NULL;
577 :
578 526 : if (!key_len) {
579 350 : key_len = table->ht_key_size;
580 350 : if (!key_len)
581 0 : return NULL;
582 : }
583 :
584 526 : ent = NULL;
585 :
586 526 : hash = vr_hash(key, key_len, 0);
587 :
588 : /* Look into the hash table from hash*/
589 526 : tmp_hash = hash % table->ht_hentries;
590 526 : tmp_hash &= ~(table->ht_bucket_size - 1);
591 1490 : for (i = 0; i < table->ht_bucket_size; i++) {
592 :
593 1249 : ind = tmp_hash + i;
594 :
595 1249 : ent = vr_btable_get(table->ht_htable, ind);
596 1249 : if (!(ent->hentry_flags & VR_HENTRY_FLAG_VALID))
597 964 : continue;
598 :
599 285 : ent_key = table->ht_get_key(htable, ent, &ent_key_len);
600 285 : if (!ent_key || (key_len != ent_key_len))
601 0 : continue;
602 :
603 285 : if (memcmp(ent_key, key, key_len) == 0)
604 285 : return ent;
605 : }
606 :
607 241 : for (o_ent = ent->hentry_next; o_ent; o_ent = o_ent->hentry_next) {
608 :
609 : /* Though in the list, can be under the deletion */
610 0 : if (!(o_ent->hentry_flags & VR_HENTRY_FLAG_VALID))
611 0 : continue;
612 :
613 0 : ent_key = table->ht_get_key(htable, o_ent, &ent_key_len);
614 0 : if (!ent_key || (key_len != ent_key_len))
615 0 : continue;
616 :
617 0 : if (memcmp(ent_key, key, key_len) == 0)
618 0 : return o_ent;
619 : }
620 :
621 : /* Entry not found */
622 241 : return NULL;
623 : }
624 :
625 : unsigned int
626 13 : vr_htable_used_oflow_entries(vr_htable_t htable)
627 : {
628 13 : struct vr_htable *table = (struct vr_htable *)htable;
629 :
630 13 : if (table)
631 13 : return table->ht_used_oentries;
632 :
633 0 : return 0;
634 : }
635 :
636 : unsigned int
637 13 : vr_htable_used_total_entries(vr_htable_t htable)
638 : {
639 13 : struct vr_htable *table = (struct vr_htable *)htable;
640 :
641 13 : if (table)
642 13 : return table->ht_used_entries;
643 :
644 0 : return 0;
645 : }
646 :
647 : unsigned int
648 0 : vr_htable_size(vr_htable_t htable)
649 : {
650 0 : struct vr_htable *table = (struct vr_htable *)htable;
651 0 : unsigned int size = 0;
652 :
653 0 : if (table) {
654 0 : if (table->ht_htable)
655 0 : size = vr_btable_size(table->ht_htable);
656 0 : if (table->ht_otable)
657 0 : size += vr_btable_size(table->ht_otable);
658 : }
659 :
660 0 : return size;
661 : }
662 :
663 : void *
664 0 : vr_htable_get_address(vr_htable_t htable, uint64_t offset)
665 : {
666 0 : struct vr_htable *table = (struct vr_htable *)htable;
667 0 : unsigned int size = vr_btable_size(table->ht_htable);
668 : struct vr_btable *btable;
669 :
670 0 : btable = table->ht_htable;
671 0 : if (offset >= size) {
672 0 : offset -= size;
673 0 : btable = table->ht_otable;
674 : }
675 :
676 0 : return vr_btable_get_address(btable, offset);
677 : }
678 :
679 : static vr_htable_t
680 159 : __vr_htable_create(struct vrouter *router, unsigned int entries,
681 : void *htable, unsigned int oentries, void *otable,
682 : unsigned int entry_size, unsigned int key_size,
683 : unsigned int bucket_size, get_hentry_key get_entry_key)
684 : {
685 : int i;
686 : struct vr_htable *table;
687 : vr_hentry_t *ent, *prev;
688 : struct iovec iov;
689 :
690 159 : if (!entry_size || !entries || !get_entry_key)
691 0 : return NULL;
692 :
693 159 : if ((bucket_size != 0) && (bucket_size != VR_HENTRIES_PER_BUCKET)) {
694 0 : vr_printf("Err: Non default bucket size is not supported\n");
695 0 : return NULL;
696 : }
697 159 : bucket_size = VR_HENTRIES_PER_BUCKET;
698 :
699 : /* Ceil to near upper number, which is dividable by bucket_size */
700 159 : entries = ((entries + bucket_size -1) / bucket_size) * bucket_size;
701 :
702 159 : table = vr_zalloc(sizeof(struct vr_htable), VR_HTABLE_OBJECT);
703 159 : if (!table) {
704 0 : vr_module_error(-ENOMEM, __FUNCTION__, __LINE__,
705 : sizeof(struct vr_htable));
706 0 : goto exit;
707 : }
708 :
709 159 : if (!htable) {
710 53 : table->ht_htable = vr_btable_alloc(entries, entry_size);
711 : } else {
712 106 : iov.iov_base = htable;
713 106 : iov.iov_len = entry_size * entries;
714 106 : table->ht_htable = vr_btable_attach(&iov, 1, entry_size);
715 : }
716 :
717 159 : if (!table->ht_htable) {
718 0 : vr_module_error(-ENOMEM, __FUNCTION__, __LINE__, entries);
719 0 : goto exit;
720 : }
721 :
722 159 : if (oentries) {
723 :
724 159 : if (!otable) {
725 53 : table->ht_otable = vr_btable_alloc(oentries, entry_size);
726 : } else {
727 106 : iov.iov_base = otable;
728 106 : iov.iov_len = entry_size * oentries;
729 106 : table->ht_otable = vr_btable_attach(&iov, 1, entry_size);
730 : }
731 :
732 159 : if (!table->ht_otable) {
733 0 : vr_module_error(-ENOMEM, __FUNCTION__, __LINE__, oentries);
734 0 : goto exit;
735 : }
736 :
737 : /*
738 : * If there is an over flow table, create the delete data for
739 : * main flow table
740 : */
741 159 : i = entries / bucket_size;
742 159 : table->ht_dtable = vr_btable_alloc(i,
743 : sizeof(struct vr_hentry_delete_data));
744 159 : if (!table->ht_dtable) {
745 0 : vr_module_error(-ENOMEM, __FUNCTION__, __LINE__, i);
746 0 : goto exit;
747 : }
748 : }
749 :
750 42115231 : for (i = 0; i < entries; i++) {
751 42115072 : ent = vr_btable_get(table->ht_htable, i);
752 42115072 : ent->hentry_index = i;
753 42115072 : ent->hentry_next_index = VR_INVALID_HENTRY_INDEX;
754 : }
755 :
756 :
757 159 : prev = NULL;
758 8466591 : for (i = 0; i < oentries; i++) {
759 8466432 : ent = vr_btable_get(table->ht_otable, i);
760 8466432 : ent->hentry_index = entries + i;
761 8466432 : ent->hentry_next_index = VR_INVALID_HENTRY_INDEX;
762 8466432 : if (i == 0)
763 159 : table->ht_free_oentry_head = ent;
764 : else
765 8466273 : prev->hentry_next = ent;
766 :
767 8466432 : ent->hentry_flags |= VR_HENTRY_FLAG_IN_FREE_LIST;
768 8466432 : prev = ent;
769 : }
770 :
771 159 : table->ht_hentries = entries;
772 159 : table->ht_oentries = oentries;
773 159 : table->ht_entry_size = entry_size;
774 159 : table->ht_key_size = key_size;
775 159 : table->ht_get_key = get_entry_key;
776 159 : table->ht_bucket_size = bucket_size;
777 159 : table->ht_router = router;
778 159 : table->ht_used_oentries = 0;
779 :
780 159 : return (vr_htable_t)table;
781 :
782 0 : exit:
783 0 : vr_htable_delete((vr_htable_t)table);
784 :
785 0 : return NULL;
786 : }
787 :
788 : vr_htable_t
789 106 : vr_htable_attach(struct vrouter *router, unsigned int entries,
790 : void *htable, unsigned int oentries, void *otable,
791 : unsigned int entry_size, unsigned int key_size,
792 : unsigned int bucket_size, get_hentry_key get_entry_key)
793 : {
794 106 : if (!entries || (otable && !oentries)) {
795 0 : return NULL;
796 : }
797 :
798 106 : return __vr_htable_create(router, entries, htable, oentries, otable,
799 : entry_size, key_size, bucket_size, get_entry_key);
800 : }
801 :
802 : void
803 159 : vr_htable_delete(vr_htable_t htable)
804 : {
805 159 : struct vr_htable *table = (struct vr_htable *)htable;
806 :
807 159 : if (!table)
808 0 : return;
809 :
810 159 : if (table->ht_htable)
811 159 : vr_btable_free(table->ht_htable);
812 :
813 159 : if (table->ht_otable)
814 159 : vr_btable_free(table->ht_otable);
815 :
816 159 : if (table->ht_dtable)
817 159 : vr_btable_free(table->ht_dtable);
818 :
819 159 : vr_free(table, VR_HTABLE_OBJECT);
820 :
821 159 : return;
822 : }
823 :
824 : vr_htable_t
825 53 : vr_htable_create(struct vrouter *router, unsigned int entries,
826 : unsigned int oentries, unsigned int entry_size, unsigned int key_size,
827 : unsigned int bucket_size, get_hentry_key get_entry_key)
828 : {
829 53 : return __vr_htable_create(router, entries, NULL, oentries, NULL,
830 : entry_size, key_size, bucket_size, get_entry_key);
831 : }
832 :
833 109 : vr_hentry_t *vr_htable_get_bucket(vr_htable_t htable, void *key,
834 : unsigned int key_len)
835 : {
836 109 : struct vr_htable *table = (struct vr_htable *)htable;
837 109 : unsigned int hash = vr_hash(key, key_len, 0);
838 109 : unsigned int tmp_hash = hash % table->ht_hentries;
839 109 : tmp_hash &= ~(table->ht_bucket_size - 1);
840 109 : return vr_btable_get(table->ht_htable, tmp_hash);
841 : }
|
