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