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