xref: /illumos-gate/usr/src/uts/common/ipp/ipgpc/trie.c (revision 7c478bd9)
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 *
create_node(int flag)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
t_split(node_t ** c_node,uint8_t pos,uint8_t key_len)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
t_insert(trie_id_t * tid,key_t id,uint32_t key,uint32_t mask)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
t_insert6(trie_id_t * tid,key_t id,in6_addr_t key,in6_addr_t mask)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
t_traverse_delete(node_t ** in_node,uint8_t pos,key_t id,uint32_t key,uint32_t mask,trie_id_t ** tid)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
t_remove(trie_id_t * tid,key_t id,uint32_t key,uint32_t mask)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
t_remove6(trie_id_t * tid,key_t id,in6_addr_t key,in6_addr_t mask)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
t_retrieve(trie_id_t * tid,uint32_t key,ht_match_t * fid_table)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
t_retrieve6(trie_id_t * tid,in6_addr_t key,ht_match_t * fid_table)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 }
836