xref: /illumos-gate/usr/src/uts/common/ipp/ipgpc/trie.c (revision 2d6eb4a5)
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