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 */
65boolean_t
66lists_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 */
98boolean_t
99list_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 */
121void
122l_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 */
151void
152l_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 */
192void
193l_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 */
219slist_t *
220l_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 */
240void
241l_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 */
267void
268l_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 */
308void
309l_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 */
348void
349l_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 */
381slist_t *
382l_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 */
395void
396l_free(slist_t *a)
397{
398	mi_free(a);
399}
400