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 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 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 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 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 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 * 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 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 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 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 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 * 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 396 l_free(slist_t *a) 397 { 398 mi_free(a); 399 } 400