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