?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge remote-tracking branch 'origin/master'
[unleashed/lotheac.git] / usr / src / uts / common / ipp / ipgpc / trie.c
blob107e5088d6e7002df181d0e6b1390d3a774f44d9
1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright 2002-2003 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 #pragma ident "%Z%%M% %I% %E% SMI"
28
29 #include <ipp/ipgpc/trie.h>
30 #include <ipp/ipgpc/filters.h>
31 #include <ipp/ipgpc/classifier.h>
32 #include <inet/ip6.h>
33
34 /* trie data structure used for classifying IP addresses and TCP/UDP ports */
35
36 #define ZERO 0
37 #define ONE 1
38
39
40 /* Statics */
41 static void t_split(node_t **, uint8_t, uint8_t);
42 static boolean_t t_traverse_delete(node_t **, uint8_t, key_t, uint32_t,
43 uint32_t, trie_id_t **);
44
45 /*
46 * create_node(flag)
47 *
48 * generates a pointer to a new trie node
49 * flag is passed to kmem_alloc
50 * returns NULL to signify memory error
51 */
52 node_t *
53 create_node(int flag)
54 {
55 node_t *buf = kmem_cache_alloc(trie_node_cache, flag);
56
57 if (buf == NULL) {
58 return (NULL);
59 }
60 buf->elements = NULL;
61 buf->zero = NULL;
62 buf->one = NULL;
63 buf->pos = 0;
64 buf->bits = 0;
65 buf->val = 0;
66 buf->mask = 0;
67 buf->isroot = 0;
68 return (buf);
69 }
70
71
72 /*
73 * t_split(c_node, pos, key_len)
74 *
75 * performs a split on c_node for the following three cases:
76 * 1 a mismatch occured between the insert key and the value at the node
77 * 2 the insert key specifies a shorter key than the one at the node
78 * 3 the insert key specifies a longer key than the one at the node
79 * cases 1 and 2 are handled in the same way
80 * when t_split returns, c_node->one and c_node->zero must != NULL
81 *
82 * (note: we assume a key_len = n (where in the real world n = 16 | 32),
83 * and a "key" in this example is actaully some value of key_len n that
84 * has its high order bits masked.
85 * For example: key = 1011 with key_len = 8, would actaully be the key:mask
86 * combo 1011xxxx:11110000. I am using short keys for ease of example)
87 * Case 1 and 2:
88 *
89 * assume 8 bit keys for all examples
90 *
91 * trie A contains keys 111011, 0, 10
92 * *
93 * / \
94 * *
95 * / \
96 * * * bits = 4 pos = 5 val = 1011 mask = 00111100
97 * inserting 111100 would result in the following split
98 * *
99 * / \
100 * *
101 * / \
102 * * bits = 1 pos = 5 val = 1 mask = 00100000
103 * / \
104 * bits = 2 pos = 3 val=11* * (to be inserted: (bits = 2 pos = 3 val = 00
105 * mask = 00001100 mask = 00001100))
106 *
107 * Case 3:
108 *
109 * trie A same as above, before insert
110 * inserting key 11101111 would results in the following split
111 * *
112 * / \
113 * *
114 * / \
115 * * * bits = 4 pos = 5 val = 1011 mask = 00111100
116 * / \
117 * * * (to be inserted: bits = 1 pos = 0 val = 1 mask = 00000001)
118 */
119 /* ARGSUSED */
120 static void
121 t_split(node_t **c_node, uint8_t pos, uint8_t key_len)
122 {
123 uint8_t old_bits = 0;
124 uint8_t i;
125 int bit;
126 node_t *nodep = *c_node;
127 node_t *tnodep = NULL;
128
129 /* check if case is that the mask is longer */
130 if (pos == (nodep->pos - nodep->bits)) {
131 /* pos is past the last bit covered at this node */
132 ASSERT(nodep->one == NULL);
133 ASSERT(nodep->zero == NULL);
134 nodep->one = create_node(KM_SLEEP);
135 nodep->zero = create_node(KM_SLEEP);
136 } else { /* pos > (nodep->pos - nodep->bits) */
137 old_bits = nodep->bits; /* save old bits entry */
138 /* nodep->pos will remain the same */
139 nodep->bits = nodep->pos - pos;
140 /* find the mismatch bit */
141 bit = EXTRACTBIT(nodep->val, pos, key_len);
142 if (bit == ZERO) {
143 if ((nodep->one == NULL) && (nodep->zero == NULL)) {
144 nodep->one = create_node(KM_SLEEP);
145 nodep->zero = create_node(KM_SLEEP);
146 } else {
147 tnodep = create_node(KM_SLEEP);
148 tnodep->one = nodep->one;
149 tnodep->zero = nodep->zero;
150 nodep->zero = tnodep;
151 nodep->one = create_node(KM_SLEEP);
152 }
153 /* pos is before the last bit covered at this node */
154 nodep->zero->pos = pos - 1; /* link is one bit */
155 /* bits gets remaining bits minus the link */
156 nodep->zero->bits = (old_bits - nodep->bits) - 1;
157 /* set bits that are covered by this node */
158 for (i = 0; i < nodep->zero->bits; ++i) {
159 SETBIT(nodep->zero->val,
160 (nodep->zero->pos - i),
161 EXTRACTBIT(nodep->val,
162 (nodep->zero->pos - i), key_len),
163 key_len);
164 SETBIT(nodep->zero->mask,
165 (nodep->zero->pos - i), 1, key_len);
166 }
167 nodep->zero->elements = nodep->elements;
168 nodep->elements = NULL;
169 } else { /* bit == ONE */
170 if ((nodep->one == NULL) && (nodep->zero == NULL)) {
171 nodep->one = create_node(KM_SLEEP);
172 nodep->zero = create_node(KM_SLEEP);
173 } else {
174 tnodep = create_node(KM_SLEEP);
175 tnodep->one = nodep->one;
176 tnodep->zero = nodep->zero;
177 nodep->one = tnodep;
178 nodep->zero = create_node(KM_SLEEP);
179 }
180 /* pos is before the last bit covered at this node */
181 nodep->one->pos = pos - 1; /* link is one bit */
182 /* bits gets remaining bits minus the link */
183 nodep->one->bits = (old_bits - nodep->bits) - 1;
184 /* set bits that are covered by this node */
185 for (i = 0; i < nodep->one->bits; ++i) {
186 SETBIT(nodep->one->val, (nodep->one->pos - i),
187 EXTRACTBIT(nodep->val,
188 (nodep->one->pos - i), key_len),
189 key_len);
190 SETBIT(nodep->one->mask,
191 (nodep->one->pos - i), 1, key_len);
192 }
193 nodep->one->elements = nodep->elements;
194 nodep->elements = NULL;
195 }
196
197 /* clear bits no longer covered by this node, from pos=>0 */
198 for (i = 0; i <= pos; ++i) {
199 UNSETBIT(nodep->val, i, key_len);
200 UNSETBIT(nodep->mask, i, key_len);
201 }
202 }
203 }
204
205 /*
206 * t_insert(tid, id, key, mask)
207 *
208 * inserts a new value, id, into the trie, tid->trie with the input key
209 * - if node exists, id is appended to element list at the node, if id does
210 * not already exist.
211 * - if node does not exist, a new node is created and id is the head of a new
212 * element list
213 * return DONTCARE_VALUE if mask == 0, otherwise NORMAL_VALUE
214 */
215 int
216 t_insert(trie_id_t *tid, key_t id, uint32_t key, uint32_t mask)
217 {
218 node_t *c_node;
219 int bit;
220 uint8_t pos;
221 uint8_t key_len = (uint8_t)tid->key_len;
222
223 /* don't insert if don't care */
224 if (mask == 0) {
225 ++tid->stats.num_dontcare;
226 return (DONTCARE_VALUE);
227 }
228
229 rw_enter(&tid->rw_lock, RW_WRITER);
230 c_node = tid->trie; /* point at trie root */
231 key &= mask; /* apply mask */
232 /* traverse trie to the correct position */
233 for (pos = key_len; pos > 0; --pos) {
234 /* check if bit is significant */
235 /* bit in key is significant if it is covered by the mask */
236 if (EXTRACTBIT(mask, (pos - 1), key_len) != 1) {
237 /* check if this is a path compressed internal node */
238 if (c_node->bits > 0) {
239 /* check if split is needed */
240 if ((pos - 1) > (c_node->pos - c_node->bits)) {
241 t_split(&c_node, (pos - 1), key_len);
242 ASSERT(c_node->one != NULL);
243 ASSERT(c_node->zero != NULL);
244 }
245 }
246 break;
247 }
248 /* extra bit at current position */
249 bit = EXTRACTBIT(key, (pos - 1), key_len);
250 /* check if this is a path compressed internal node */
251 if (c_node->bits > 0) { /* path compressed node */
252 /* check if split is needed */
253 if ((pos - 1) > (c_node->pos - c_node->bits)) {
254 /* testing for mismatch */
255 if (bit != EXTRACTBIT(c_node->val, (pos - 1),
256 key_len)) {
257 t_split(&c_node, (pos - 1), key_len);
258 ASSERT(c_node->one != NULL);
259 ASSERT(c_node->zero != NULL);
260 } else {
261 continue; /* bits match, so go on */
262 }
263 } else if ((pos - 1) == (c_node->pos - c_node->bits)) {
264 /* check if at a leaf node with elements */
265 if ((c_node->one == NULL) &&
266 (c_node->zero == NULL) &&
267 (c_node->elements != NULL)) {
268 /*
269 * this case occurs when mask for key
270 * is longer than mask for key at
271 * current node
272 */
273 t_split(&c_node, (pos - 1), key_len);
274 ASSERT(c_node->one != NULL);
275 ASSERT(c_node->zero != NULL);
276 }
277 } /* else continue onto child */
278 }
279 if (bit == ZERO) {
280 if (c_node->zero == NULL) { /* leaf node */
281 if (c_node->bits == 0) {
282 c_node->pos = (pos - 1);
283 }
284 c_node->bits++;
285 /* bit at pos for node value should be 0 */
286 UNSETBIT(c_node->val, (pos - 1), key_len);
287 SETBIT(c_node->mask, (pos - 1), 1, key_len);
288 } else {
289 /* assert that trie is path compressed */
290 ASSERT(c_node->one != NULL);
291 c_node = c_node->zero; /* internal node */
292 }
293 } else { /* ONE bit */
294 if (c_node->one == NULL) { /* leaf node */
295 if (c_node->bits == 0) {
296 c_node->pos = (pos - 1);
297 }
298 c_node->bits++;
299 /* bit at pos for node value should be 1 */
300 SETBIT(c_node->val, (pos - 1), 1, key_len);
301 SETBIT(c_node->mask, (pos - 1), 1, key_len);
302 } else {
303 /* assert that trie is path compressed */
304 ASSERT(c_node->zero != NULL);
305 c_node = c_node->one; /* internal node */
306 }
307 }
308 }
309 /* insert at node */
310 (void) ipgpc_list_insert(&c_node->elements, id);
311 /* update stats */
312 ++tid->stats.num_inserted;
313 /*
314 * check if this is the first key to be inserted that is not a
315 * don't care (*)
316 */
317 if (tid->info.dontcareonly == B_TRUE) {
318 tid->info.dontcareonly = B_FALSE;
319 }
320 rw_exit(&tid->rw_lock);
321 return (NORMAL_VALUE);
322 }
323
324 /*
325 * t_insert6(tid, id, key, mask)
326 *
327 * specific to inserting keys of 128 bits in length
328 */
329 int
330 t_insert6(trie_id_t *tid, key_t id, in6_addr_t key, in6_addr_t mask)
331 {
332 node_t *c_node;
333 int bit, i;
334 uint8_t pos;
335 uint8_t type_len = IP_ABITS;
336 in6_addr_t zero_addr = IN6ADDR_ANY_INIT;
337
338 /* don't insert if don't care */
339 if (IN6_ARE_ADDR_EQUAL(&mask, &zero_addr)) {
340 ++tid->stats.num_dontcare;
341 return (DONTCARE_VALUE);
342 }
343
344 rw_enter(&tid->rw_lock, RW_WRITER);
345 c_node = tid->trie; /* point at root of trie */
346 V6_MASK_COPY(key, mask, key); /* apply mask to key */
347 /*
348 * A IPv6 address is structured as an array of four uint32_t
349 * values. The highest order of the bits are located in array[0]
350 */
351 for (i = 0; i < 4; ++i) {
352 /* traverse trie to the correct position */
353 for (pos = type_len; pos > 0; --pos) {
354 /* check if bit is significant */
355 if (EXTRACTBIT(mask.s6_addr32[i], (pos - 1), type_len)
356 != ONE) {
357 break;
358 }
359 bit = EXTRACTBIT(key.s6_addr32[i], (pos - 1), type_len);
360 if (bit == ZERO) {
361 if (c_node->zero == NULL) {
362 c_node->zero = create_node(KM_SLEEP);
363 }
364 c_node = c_node->zero;
365 } else { /* ONE bit */
366 if (c_node->one == NULL) {
367 c_node->one = create_node(KM_SLEEP);
368 }
369 c_node = c_node->one;
370 }
371
372 }
373 }
374 /* insert at node */
375 (void) ipgpc_list_insert(&c_node->elements, id);
376 /* update stats */
377 ++tid->stats.num_inserted;
378 /*
379 * check if this is the first key to be inserted that is not a
380 * don't care (*)
381 */
382 if (tid->info.dontcareonly == B_TRUE) {
383 tid->info.dontcareonly = B_FALSE;
384 }
385 rw_exit(&tid->rw_lock);
386 return (NORMAL_VALUE);
387 }
388
389 /*
390 * t_traverse_delete(in_node, pos, id, key, mask, tid)
391 *
392 * used to traverse to the node containing id, as found under key
393 * once id is found, it is removed from the trie.
394 * Upon removing the id from a given node in the trie, path compression
395 * will be applied to nodes that are no longer compressed.
396 * If the id is successfully removed, tid->stats are updated
397 */
398 static boolean_t
399 t_traverse_delete(node_t **in_node, uint8_t pos, key_t id, uint32_t key,
400 uint32_t mask, trie_id_t **tid)
401 {
402 node_t *c_node = *in_node;
403 node_t *t_node;
404 int bit;
405
406 if (c_node == NULL) {
407 return (B_FALSE); /* base failure case */
408 }
409
410 /* we've found the node the id is probably at */
411 if ((pos == 0) ||
412 (EXTRACTBIT(mask, (pos - 1), (uint8_t)(*tid)->key_len) != 1)) {
413 if (ipgpc_list_remove(&c_node->elements, id) == B_FALSE) {
414 ipgpc0dbg(("t_traverse_delete: id %d does not " \
415 "exist in trie\n", id));
416 return (B_FALSE); /* key does not exist at node */
417 } else {
418 /* update stats */
419 --(*tid)->stats.num_inserted;
420 /* check if 0 values are inserted in this trie */
421 if ((*tid)->stats.num_inserted == 0) {
422 /* update dontcareonly boolean */
423 (*tid)->info.dontcareonly = B_TRUE;
424 }
425 }
426 /* check if node has zero elements, is a LEAF node */
427 if ((c_node->elements == NULL) &&
428 ((c_node->one == NULL) && (c_node->zero == NULL))) {
429 /* make sure we don't delete the root */
430 if (c_node->isroot != 1) {
431 kmem_cache_free(trie_node_cache, c_node);
432 return (B_TRUE);
433 } else {
434 /* this is the root, just zero out the info */
435 c_node->pos = 0;
436 c_node->bits = 0;
437 c_node->val = 0;
438 c_node->mask = 0;
439 }
440 }
441 return (B_FALSE);
442 }
443
444 /* check to see if node describes bits to skip */
445 if (c_node->bits > 0) {
446 if ((key & c_node->mask) != c_node->val) {
447 ipgpc0dbg(("t_traverse_delete: id %d does not " \
448 "exist in trie\n", id));
449 return (B_FALSE); /* key does not exist at node */
450 }
451 pos = (c_node->pos - c_node->bits) + 1;
452 /* search should continue if mask and pos are valid */
453 if ((pos == 0) ||
454 (EXTRACTBIT(mask, (pos - 1), (uint8_t)(*tid)->key_len)
455 != 1)) {
456 /* this node probably contains the id */
457 if (ipgpc_list_remove(&c_node->elements,
458 id) == B_FALSE) {
459 ipgpc0dbg(("t_traverse_delete: id %d does" \
460 "not exist in trie\n", id));
461 return (B_FALSE);
462 } else {
463 /* update stats */
464 --(*tid)->stats.num_inserted;
465 /* check if 0 values are inserted */
466 if ((*tid)->stats.num_inserted == 0) {
467 /* update dontcare boolean */
468 (*tid)->info.dontcareonly = B_TRUE;
469 }
470 }
471 /* check if node has zero elements & is a LEAF node */
472 if ((c_node->elements == NULL) &&
473 ((c_node->one == NULL) &&
474 (c_node->zero == NULL))) {
475 /* make sure we don't delete the root */
476 if (c_node->isroot != 1) {
477 kmem_cache_free(trie_node_cache,
478 c_node);
479 return (B_TRUE);
480 } else {
481 /* this is the root, zero out info */
482 c_node->pos = 0;
483 c_node->bits = 0;
484 c_node->val = 0;
485 c_node->mask = 0;
486 }
487 }
488 return (B_FALSE);
489 }
490 }
491 /* extract next bit and test */
492 bit = EXTRACTBIT(key, (pos - 1), (uint8_t)(*tid)->key_len);
493 if (bit == ZERO) {
494 if (t_traverse_delete(&c_node->zero, (pos - 1), id, key, mask,
495 tid) == B_TRUE) {
496 c_node->zero = NULL;
497 }
498 } else { /* ONE bit */
499 if (t_traverse_delete(&c_node->one, (pos - 1), id, key, mask,
500 tid) == B_TRUE) {
501 c_node->one = NULL;
502 }
503 }
504 /*
505 * non path-compressed nodes will contain one child and no elements
506 * what occurs here:
507 * *
508 * / \
509 * * * <-- p_node->elements == NULL
510 * /
511 * * <-- c_node->elements = foo
512 * / \
513 * * * <-- children of c_node
514 * after:
515 * *
516 * / \
517 * * * <-- p_node->elements = foo
518 * / \
519 * * * <-- p_node adopts children of c_node
520 */
521 if ((c_node->one == NULL) && (c_node->zero != NULL)) {
522 if (c_node->elements == NULL) {
523 /* move child elements to parent */
524 c_node->elements = c_node->zero->elements;
525 /* be sure to include the link in the bits */
526 c_node->bits += c_node->zero->bits + 1;
527 /* c_node->pos will remain the same */
528 c_node->mask |= c_node->zero->mask;
529 /* don't forget to mark the link */
530 SETBIT(c_node->mask, (pos - 1), 1,
531 (uint8_t)(*tid)->key_len);
532 c_node->val |= c_node->zero->val;
533 /* don't forget to mark the link */
534 UNSETBIT(c_node->val, (pos - 1),
535 (uint8_t)(*tid)->key_len);
536 /* adopt children */
537 t_node = c_node->zero;
538 c_node->one = c_node->zero->one;
539 c_node->zero = c_node->zero->zero;
540 kmem_cache_free(trie_node_cache, t_node);
541 } else {
542 ASSERT(c_node->zero->one == NULL);
543 ASSERT(c_node->zero->zero == NULL);
544 kmem_cache_free(trie_node_cache, c_node->zero);
545 c_node->zero = NULL;
546 }
547 } else if ((c_node->one != NULL) && (c_node->zero == NULL)) {
548 if (c_node->elements == NULL) {
549 /* move child elements to parent */
550 c_node->elements = c_node->one->elements;
551 /* be sure to include the link in the bits */
552 c_node->bits += c_node->one->bits + 1;
553 /* c_node->pos will remain the same */
554 c_node->mask |= c_node->one->mask;
555 /* don't forget to mark the link */
556 SETBIT(c_node->mask, (pos - 1), 1,
557 (uint8_t)(*tid)->key_len);
558 c_node->val |= c_node->one->val;
559 /* don't forget to mark the link */
560 SETBIT(c_node->val, (pos - 1), 1,
561 (uint8_t)(*tid)->key_len);
562 /* adopt children */
563 t_node = c_node->one;
564 c_node->zero = c_node->one->zero;
565 c_node->one = c_node->one->one;
566 kmem_cache_free(trie_node_cache, t_node);
567 } else {
568 ASSERT(c_node->one->one == NULL);
569 ASSERT(c_node->one->zero == NULL);
570 kmem_cache_free(trie_node_cache, c_node->one);
571 c_node->one = NULL;
572 }
573 }
574 /* check if node has zero elements, is a LEAF node */
575 if ((c_node->elements == NULL) &&
576 ((c_node->one == NULL) && (c_node->zero == NULL))) {
577 /* make sure we don't delete the root */
578 if (c_node->isroot != 1) {
579 kmem_cache_free(trie_node_cache, c_node);
580 return (B_TRUE);
581 } else {
582 /* this is the root, just zero out the info */
583 c_node->pos = 0;
584 c_node->bits = 0;
585 c_node->val = 0;
586 c_node->mask = 0;
587 }
588 }
589 return (B_FALSE);
590 }
591
592
593
594 /*
595 * t_remove(tid, id, key, mask)
596 *
597 * removes a value associated with an id from the trie
598 * - if the item does not exist, nothing is removed
599 * - if more than one id share the same key, only the id specified is removed
600 */
601 void
602 t_remove(trie_id_t *tid, key_t id, uint32_t key, uint32_t mask)
603 {
604 node_t *c_node;
605
606 /* don't cares are not inserted */
607 if (mask == 0) {
608 --tid->stats.num_dontcare;
609 return;
610 }
611
612 key &= mask; /* apply mask */
613 /* traverse to node containing id and remove the id from the trie */
614 rw_enter(&tid->rw_lock, RW_WRITER);
615 c_node = tid->trie;
616 (void) t_traverse_delete(&c_node, (uint8_t)tid->key_len, id, key, mask,
617 &tid);
618 rw_exit(&tid->rw_lock);
619 }
620
621 /*
622 * t_remove6(tid, id, key, mask)
623 *
624 * specific to removing key of 128 bits in length
625 */
626 void
627 t_remove6(trie_id_t *tid, key_t id, in6_addr_t key, in6_addr_t mask)
628 {
629 node_t *c_node;
630 int bit, i;
631 uint8_t pos;
632 uint8_t type_len = IP_ABITS;
633 in6_addr_t zero_addr = IN6ADDR_ANY_INIT;
634
635 /* don't cares are not inserted */
636 if (IN6_ARE_ADDR_EQUAL(&mask, &zero_addr)) {
637 --tid->stats.num_dontcare;
638 return;
639 }
640
641 rw_enter(&tid->rw_lock, RW_WRITER);
642 c_node = tid->trie; /* point at root of trie */
643 V6_MASK_COPY(key, mask, key);
644 /*
645 * A IPv6 address is structured as an array of four uint32_t
646 * values. The higest order of the bits are located in array[0]
647 */
648 for (i = 0; i < 4; ++i) {
649 /* traverse trie to the correct position */
650 for (pos = type_len; pos > 0; --pos) {
651 /* check if bit is significant */
652 if (EXTRACTBIT(mask.s6_addr32[i], (pos - 1), type_len)
653 != ONE) {
654 break;
655 }
656 bit = EXTRACTBIT(key.s6_addr32[i], (pos - 1), type_len);
657 if (bit == ZERO) {
658 if (c_node->zero == NULL) {
659 break;
660 }
661 c_node = c_node->zero;
662 } else { /* ONE bit */
663 if (c_node->one == NULL) {
664 break;
665 }
666 c_node = c_node->one;
667 }
668
669 }
670 }
671 if (c_node != NULL) {
672 if (ipgpc_list_remove(&c_node->elements, id)) {
673 /* update stats */
674 --tid->stats.num_inserted;
675 /*
676 * check to see if only dontcare's are inserted
677 */
678 if (tid->stats.num_inserted <= 0) {
679 tid->info.dontcareonly = B_TRUE;
680 }
681 }
682 }
683 rw_exit(&tid->rw_lock);
684 }
685
686
687 /*
688 * t_retrieve(tid, key, fid_table)
689 *
690 * returns the number of found filters that match the input key
691 * - each value that matches either a partial or exact match on the key
692 * is inserted into the fid_table
693 * - some nodes may contain multiple id's, all items will be inserted
694 * into the fid_table
695 * - the find stops when an edge node is reached, the left and right nodes
696 * for the current node are null
697 * - 0 is returned if no matches are found, otherwise the number of matches
698 * is returned
699 * - (-1) is returned if a memory error occurred
700 */
701 int
702 t_retrieve(trie_id_t *tid, uint32_t key, ht_match_t *fid_table)
703 {
704 int bit;
705 uint8_t pos;
706 int num_found = 0;
707 int ret;
708 node_t *c_node;
709
710 rw_enter(&tid->rw_lock, RW_READER);
711 c_node = tid->trie; /* point at root of trie */
712
713 /* ensure trie structure is allocated */
714 if (c_node == NULL) {
715 rw_exit(&tid->rw_lock);
716 return (num_found);
717 }
718 /*
719 * foreach node encountered in the search, collect elements and append
720 * to a list to be returned
721 */
722 for (pos = (uint8_t)tid->key_len; pos > 0; --pos) {
723 /* check node for bits to check */
724 if (c_node->bits > 0) {
725 if ((key & c_node->mask) != c_node->val) {
726 rw_exit(&tid->rw_lock);
727 return (num_found); /* search is done */
728 }
729 /* pos is set to next bit not covered by node */
730 if ((pos = (c_node->pos - c_node->bits) + 1) == 0) {
731 /* if node covers rest of bits in key */
732 break;
733 }
734 }
735 /* check node for elements */
736 if (c_node->elements != NULL) {
737 if ((ret = ipgpc_mark_found(tid->info.mask,
738 c_node->elements, fid_table)) == -1) {
739 /* signifies a memory error */
740 rw_exit(&tid->rw_lock);
741 return (-1);
742 }
743 num_found += ret; /* increment num_found */
744 }
745
746 bit = EXTRACTBIT(key, (pos - 1), (uint8_t)tid->key_len);
747 if (bit == ZERO) { /* choose leaf */
748 c_node = c_node->zero;
749
750 } else { /* bit == ONE */
751 c_node = c_node->one;
752
753 }
754 if (c_node == NULL) {
755 /* search is finished, edge node reached */
756 rw_exit(&tid->rw_lock);
757 return (num_found);
758 }
759 }
760 /* see if current node contains elements */
761 if (c_node->elements != NULL) {
762 if ((ret = ipgpc_mark_found(tid->info.mask, c_node->elements,
763 fid_table)) == -1) {
764 rw_exit(&tid->rw_lock);
765 return (-1); /* signifies a memory error */
766 }
767 num_found += ret; /* increment num_found */
768 }
769 rw_exit(&tid->rw_lock);
770 return (num_found);
771 }
772
773 /*
774 * t_retrieve6(tid, key, fid_table)
775 *
776 * specific to retrieving keys of 128 bits in length
777 */
778 int
779 t_retrieve6(trie_id_t *tid, in6_addr_t key, ht_match_t *fid_table)
780 {
781 int bit, i;
782 uint8_t pos;
783 int num_found = 0;
784 int ret;
785 node_t *c_node;
786 uint8_t type_len = IP_ABITS;
787
788 rw_enter(&tid->rw_lock, RW_READER);
789 c_node = tid->trie;
790
791 /* ensure trie structure is allocated */
792 if (c_node == NULL) {
793 rw_exit(&tid->rw_lock);
794 return (num_found);
795 }
796 /*
797 * A IPv6 address is structured as an array of four uint32_t
798 * values. The higest order of the bits are located in array[0]
799 */
800 for (i = 0; i < 4; ++i) {
801 /*
802 * foreach node encountered in the search, collect elements
803 * and append to a list to be returned
804 */
805 for (pos = type_len; pos > 0; --pos) {
806 /* extract bit at pos */
807 bit =
808 EXTRACTBIT(key.s6_addr32[i], (pos - 1), type_len);
809 if (bit == ZERO) { /* choose leaf */
810 c_node = c_node->zero;
811
812 } else {
813 c_node = c_node->one;
814
815 }
816 if (c_node == NULL) {
817 /* search is finished, edge node reached */
818 rw_exit(&tid->rw_lock);
819 return (num_found);
820 }
821 /* see if current node contains elements */
822 if (c_node->elements != NULL) {
823 if ((ret = ipgpc_mark_found(tid->info.mask,
824 c_node->elements, fid_table)) == -1) {
825 /* signifies a memory error */
826 rw_exit(&tid->rw_lock);
827 return (-1);
828 }
829 num_found += ret; /* increment num_found */
830 }
831 }
832 }
833 rw_exit(&tid->rw_lock);
834 return (num_found);
835 }