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