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