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