xref: /titanic_41/usr/src/uts/common/inet/ip/ip_listutils.c (revision 7c478bd95313f5f23a4c958a745db2134aa03244)
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 2005 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 <sys/types.h>
30 #include <sys/stream.h>
31 #include <sys/dlpi.h>
32 #include <sys/stropts.h>
33 #include <sys/strlog.h>
34 #include <sys/systm.h>
35 #include <sys/ddi.h>
36 #include <sys/cmn_err.h>
37 
38 #include <sys/param.h>
39 #include <sys/tihdr.h>
40 #include <netinet/in.h>
41 #include <netinet/ip6.h>
42 
43 #include <inet/common.h>
44 #include <inet/mi.h>
45 #include <inet/ip.h>
46 #include <inet/ip6.h>
47 #include <inet/ip_listutils.h>
48 
49 /*
50  * These functions perform set operations on sets of ipv6 addresses.
51  * The sets are formatted as slist_t's (defined in <inet/ip.h>):
52  *	typedef struct slist_s {
53  *		int		sl_nusmrc;
54  *		in6_addr_t	sl_addr[MAX_FILTER_SIZE];
55  *	} slist_t;
56  *
57  * The functions were designed specifically for the implementation of
58  * IGMPv3 and MLDv2 in ip; they were not meant to be general-purpose.
59  */
60 
61 /*
62  * Tells if lists A and B are different or not - true if different;
63  * caller guarantees that lists are <= MAX_FILTER_SIZE
64  */
65 boolean_t
lists_are_different(const slist_t * a,const slist_t * b)66 lists_are_different(const slist_t *a, const slist_t *b)
67 {
68 	int i, j;
69 	int acnt = SLIST_CNT(a);
70 	int bcnt = SLIST_CNT(b);
71 	boolean_t found;
72 
73 	if (acnt != bcnt)
74 		return (B_TRUE);
75 
76 	ASSERT(acnt <= MAX_FILTER_SIZE);
77 	ASSERT(bcnt <= MAX_FILTER_SIZE);
78 
79 	for (i = 0; i < acnt; i++) {
80 		found = B_FALSE;
81 		for (j = 0; j < bcnt; j++) {
82 			if (IN6_ARE_ADDR_EQUAL(
83 			    &a->sl_addr[i], &b->sl_addr[j])) {
84 				found = B_TRUE;
85 				break;
86 			}
87 		}
88 		if (!found)
89 			return (B_TRUE);
90 	}
91 	return (B_FALSE);
92 }
93 
94 /*
95  * Tells if list a contains address addr - true if it does, false if not;
96  * caller guarantees that list is <= MAX_FILTER_SIZE.
97  */
98 boolean_t
list_has_addr(const slist_t * a,const in6_addr_t * addr)99 list_has_addr(const slist_t *a, const in6_addr_t *addr)
100 {
101 	int i;
102 
103 	if (SLIST_IS_EMPTY(a))
104 		return (B_FALSE);
105 
106 	ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
107 
108 	for (i = 0; i < a->sl_numsrc; i++) {
109 		if (IN6_ARE_ADDR_EQUAL(&a->sl_addr[i], addr))
110 			return (B_TRUE);
111 	}
112 	return (B_FALSE);
113 }
114 
115 /*
116  * Implements a * b and stores the result in target; caller guarantees
117  * that a and b are <= MAX_FILTER_SIZE, and that target is a valid pointer.
118  * target must not be the same as a or b; for that case see
119  * l_intersection_in_a().
120  */
121 void
l_intersection(const slist_t * a,const slist_t * b,slist_t * target)122 l_intersection(const slist_t *a, const slist_t *b, slist_t *target)
123 {
124 	int i, j;
125 
126 	target->sl_numsrc = 0;
127 
128 	if (SLIST_IS_EMPTY(a) || SLIST_IS_EMPTY(b))
129 		return;
130 
131 	ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
132 	ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);
133 
134 	for (i = 0; i < a->sl_numsrc; i++) {
135 		for (j = 0; j < b->sl_numsrc; j++) {
136 			if (IN6_ARE_ADDR_EQUAL(
137 			    &a->sl_addr[i], &b->sl_addr[j])) {
138 				target->sl_addr[target->sl_numsrc++] =
139 				    a->sl_addr[i];
140 				break;
141 			}
142 		}
143 	}
144 }
145 
146 /*
147  * Implements a - b and stores the result in target; caller guarantees
148  * that a and b are <= MAX_FILTER_SIZE, and that target is a valid pointer.
149  * target must not be the same as a or b; for that case see l_difference_in_a().
150  */
151 void
l_difference(const slist_t * a,const slist_t * b,slist_t * target)152 l_difference(const slist_t *a, const slist_t *b, slist_t *target)
153 {
154 	int i, j;
155 	boolean_t found = B_FALSE;
156 
157 	target->sl_numsrc = 0;
158 
159 	if (SLIST_IS_EMPTY(a))
160 		return;
161 
162 	if (SLIST_IS_EMPTY(b)) {
163 		l_copy(a, target);
164 		return;
165 	}
166 
167 	ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
168 	ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);
169 
170 	for (i = 0; i < a->sl_numsrc; i++) {
171 		for (j = 0; j < b->sl_numsrc; j++) {
172 			if (IN6_ARE_ADDR_EQUAL(
173 			    &a->sl_addr[i], &b->sl_addr[j])) {
174 				found = B_TRUE;
175 				break;
176 			}
177 		}
178 		if (!found) {
179 			target->sl_addr[target->sl_numsrc++] = a->sl_addr[i];
180 		} else {
181 			found = B_FALSE;
182 		}
183 	}
184 }
185 
186 /*
187  * Removes addr from list a.  Caller guarantees that addr is a valid
188  * pointer, and that a <= MAX_FILTER_SIZE.  addr will only be removed
189  * once from the list; if it appears in the list multiple times, extra
190  * copies may remain.
191  */
192 void
l_remove(slist_t * a,const in6_addr_t * addr)193 l_remove(slist_t *a, const in6_addr_t *addr)
194 {
195 	int i, mvsize;
196 
197 	if (SLIST_IS_EMPTY(a))
198 		return;
199 
200 	ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
201 
202 	for (i = 0; i < a->sl_numsrc; i++) {
203 		if (IN6_ARE_ADDR_EQUAL(&a->sl_addr[i], addr)) {
204 			a->sl_numsrc--;
205 			mvsize = (a->sl_numsrc - i) * sizeof (in6_addr_t);
206 			(void) memmove(&a->sl_addr[i], &a->sl_addr[i + 1],
207 			    mvsize);
208 			break;
209 		}
210 	}
211 }
212 
213 /*
214  * Make a copy of list a by allocating a new slist_t and copying only
215  * a->sl_numsrc addrs.  Caller guarantees that a <= MAX_FILTER_SIZE.
216  * Return a pointer to the newly alloc'd list, or NULL if a is empty
217  * (no memory is alloc'd in this case).
218  */
219 slist_t *
l_alloc_copy(const slist_t * a)220 l_alloc_copy(const slist_t *a)
221 {
222 	slist_t *b;
223 
224 	if (SLIST_IS_EMPTY(a))
225 		return (NULL);
226 
227 	if ((b = l_alloc()) == NULL)
228 		return (NULL);
229 
230 	l_copy(a, b);
231 
232 	return (b);
233 }
234 
235 /*
236  * Copy the address list from slist a into slist b, overwriting anything
237  * that might already be in slist b.  Assumes that a <= MAX_FILTER_SIZE
238  * and that b points to a properly allocated slist.
239  */
240 void
l_copy(const slist_t * a,slist_t * b)241 l_copy(const slist_t *a, slist_t *b)
242 {
243 	if (SLIST_IS_EMPTY(a)) {
244 		b->sl_numsrc = 0;
245 		return;
246 	}
247 
248 	ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
249 
250 	b->sl_numsrc = a->sl_numsrc;
251 	(void) memcpy(b->sl_addr, a->sl_addr,
252 	    a->sl_numsrc * sizeof (in6_addr_t));
253 }
254 
255 /*
256  * Append to a any addrs in b that are not already in a (i.e. perform
257  * a + b and store the result in a).  If b is empty, the function returns
258  * without taking any action.
259  *
260  * Caller guarantees that a and b are <= MAX_FILTER_SIZE, and that a
261  * and overflow are valid pointers.
262  *
263  * If an overflow occurs (a + b > MAX_FILTER_SIZE), a will contain the
264  * first MAX_FILTER_SIZE addresses of the union, and *overflow will be
265  * set to true.  Otherwise, *overflow will be set to false.
266  */
267 void
l_union_in_a(slist_t * a,const slist_t * b,boolean_t * overflow)268 l_union_in_a(slist_t *a, const slist_t *b, boolean_t *overflow)
269 {
270 	int i, j;
271 	boolean_t found;
272 
273 	*overflow = B_FALSE;
274 
275 	if (SLIST_IS_EMPTY(b))
276 		return;
277 
278 	ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
279 	ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);
280 
281 	for (i = 0; i < b->sl_numsrc; i++) {
282 		found = B_FALSE;
283 		for (j = 0; j < a->sl_numsrc; j++) {
284 			if (IN6_ARE_ADDR_EQUAL(
285 			    &b->sl_addr[i], &a->sl_addr[j])) {
286 				found = B_TRUE;
287 				break;
288 			}
289 		}
290 		if (!found) {
291 			if (a->sl_numsrc == MAX_FILTER_SIZE) {
292 				*overflow = B_TRUE;
293 				break;
294 			} else {
295 				a->sl_addr[a->sl_numsrc++] = b->sl_addr[i];
296 			}
297 		}
298 	}
299 }
300 
301 /*
302  * Remove from list a any addresses that are not also in list b
303  * (i.e. perform a * b and store the result in a).
304  *
305  * Caller guarantees that a and b are <= MAX_FILTER_SIZE, and that
306  * a is a valid pointer.
307  */
308 void
l_intersection_in_a(slist_t * a,const slist_t * b)309 l_intersection_in_a(slist_t *a, const slist_t *b)
310 {
311 	int i, j, shift;
312 	boolean_t found;
313 
314 	if (SLIST_IS_EMPTY(b)) {
315 		a->sl_numsrc = 0;
316 		return;
317 	}
318 
319 	ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
320 	ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);
321 
322 	shift = 0;
323 	for (i = 0; i < a->sl_numsrc; i++) {
324 		found = B_FALSE;
325 		for (j = 0; j < b->sl_numsrc; j++) {
326 			if (IN6_ARE_ADDR_EQUAL(
327 			    &a->sl_addr[i], &b->sl_addr[j])) {
328 				found = B_TRUE;
329 				break;
330 			}
331 		}
332 		if (!found)
333 			shift++;
334 		else if (shift > 0)
335 			a->sl_addr[i - shift] = a->sl_addr[i];
336 	}
337 	a->sl_numsrc -= shift;
338 }
339 
340 /*
341  * Remove from list a any addresses that are in list b (i.e. perform
342  * a - b and store the result in a).
343  *
344  * Caller guarantees that a and b are <= MAX_FILTER_SIZE.  If either
345  * list is empty (or a null pointer), the function returns without
346  * taking any action.
347  */
348 void
l_difference_in_a(slist_t * a,const slist_t * b)349 l_difference_in_a(slist_t *a, const slist_t *b)
350 {
351 	int i, j, shift;
352 	boolean_t found;
353 
354 	if (SLIST_IS_EMPTY(a) || SLIST_IS_EMPTY(b))
355 		return;
356 
357 	ASSERT(a->sl_numsrc <= MAX_FILTER_SIZE);
358 	ASSERT(b->sl_numsrc <= MAX_FILTER_SIZE);
359 
360 	shift = 0;
361 	for (i = 0; i < a->sl_numsrc; i++) {
362 		found = B_FALSE;
363 		for (j = 0; j < b->sl_numsrc; j++) {
364 			if (IN6_ARE_ADDR_EQUAL(
365 			    &a->sl_addr[i], &b->sl_addr[j])) {
366 				found = B_TRUE;
367 				break;
368 			}
369 		}
370 		if (found)
371 			shift++;
372 		else if (shift > 0)
373 			a->sl_addr[i - shift] = a->sl_addr[i];
374 	}
375 	a->sl_numsrc -= shift;
376 }
377 
378 /*
379  * Wrapper function to alloc an slist_t.
380  */
381 slist_t *
l_alloc()382 l_alloc()
383 {
384 	slist_t *p;
385 
386 	p = (slist_t *)mi_alloc(sizeof (slist_t), BPRI_MED);
387 	if (p != NULL)
388 		p->sl_numsrc = 0;
389 	return (p);
390 }
391 
392 /*
393  * Frees an slist_t structure.  Provided for symmetry with l_alloc().
394  */
395 void
l_free(slist_t * a)396 l_free(slist_t *a)
397 {
398 	mi_free(a);
399 }
400