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