1 /* $OpenBSD: addr_range.c,v 1.6 2017/05/30 17:22:00 yasuoka Exp $ */ 2 /*- 3 * Copyright (c) 2009 Internet Initiative Japan Inc. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 */ 27 /* 28 * addr_range.c - Parser/aggregator for varios address/network expressions. 29 * 30 * Input: 192.168.0.0/24 192.168.1.0/24 31 * Output: 192.168.0.0/23 32 * 33 * Input: 192.168.0.128-192.168.0.255 34 * Output: 192.168.0.128/25 35 * 36 * Notice: 37 * - Byte order of 'addr' and 'mask' (members of struct in_addr_range) 38 * are host byte order. 39 * - Parsing address range like 192.168.0.0-192.168.255.255 costs much of 40 * cpu/memory. 41 * 42 * Example code: 43 * 44 * struct in_addr_range *list = NULL, *cur; 45 * 46 * in_addr_range_list_add(&list, "192.168.0.128-192.168.0.255"); 47 * in_addr_range_list_add(&list, "192.168.1.128-192.168.1.255"); 48 * for (cur = list; cur != NULL; cur = cur->next) { 49 * // do something 50 * struct in_addr a, m; 51 * a.s_addr = htonl(cur->addr); 52 * m.s_addr = htonl(cur->mask); 53 * } 54 * in_addr_range_list_remove_all(&list); 55 * 56 * Author: 57 * Yasuoka Masahiko <yasuoka@iij.ad.jp> 58 * 59 * $Id: addr_range.c,v 1.6 2017/05/30 17:22:00 yasuoka Exp $ 60 */ 61 #ifdef ADDR_RANGE_DEBUG 62 #define IIJDEBUG 63 #endif 64 65 #include <sys/types.h> 66 #include <netinet/in.h> 67 #include <arpa/inet.h> 68 69 #include <errno.h> 70 #include <syslog.h> 71 #include <string.h> 72 #include <stdlib.h> 73 #include <stdio.h> 74 75 #ifdef IIJDEBUG 76 #include <debugutil.h> 77 static int saved_errno; 78 #define INT4_CHARS(x) \ 79 ((x) & 0xff000000) >> 24, ((x) & 0x00ff0000) >> 16, \ 80 ((x) & 0x0000ff00) >> 8, ((x) & 0x000000ff) 81 #endif 82 #include "addr_range.h" 83 84 static void in_addr_range_list_uniq(struct in_addr_range **); 85 static int in_addr_range_list_add0(struct in_addr_range **, u_int32_t, u_int32_t); 86 static int bitmask2masklen(u_int32_t); 87 88 struct in_addr_range * 89 in_addr_range_create() 90 { 91 struct in_addr_range *_this; 92 if ((_this = malloc(sizeof(struct in_addr_range))) == NULL) 93 return NULL; 94 memset(_this, 0xff, sizeof(struct in_addr_range)); 95 _this->next = NULL; 96 return _this; 97 } 98 99 100 void 101 in_addr_range_destroy(struct in_addr_range *_this) 102 { 103 free(_this); 104 } 105 106 void 107 in_addr_range_list_remove_all(struct in_addr_range **list) 108 { 109 struct in_addr_range *cur0, *cur; 110 111 cur = *list; 112 while (cur != NULL) { 113 cur0 = cur; 114 cur = cur->next; 115 in_addr_range_destroy(cur0); 116 } 117 *list = NULL; 118 } 119 120 static void 121 in_addr_range_list_uniq(struct in_addr_range **list) 122 { 123 u_int32_t m0; 124 struct in_addr_range **cur, *a, *b; 125 126 restart: 127 for (cur = list; *cur != NULL; cur = &(*cur)->next) { 128 if ((*cur)->next == NULL) 129 continue; 130 a = *cur; 131 b = (*cur)->next; 132 m0 = 0xffffffff ^ a->mask; 133 if (a->mask == b->mask && ( 134 a->addr - b->addr == m0 + 1 || 135 b->addr - a->addr == m0 + 1)) { 136 m0 = m0 * 2 + 1; 137 m0 ^= 0xffffffff; 138 if ((a->addr & m0) != (b->addr & m0)) 139 continue; 140 if (a->addr > b->addr) { 141 #ifdef IIJDEBUG 142 log_printf(LOG_DL_2, 143 "%d.%d.%d.%d/%d + %d.%d.%d.%d/%d = %d.%d.%d.%d/%d" 144 , INT4_CHARS(a->addr), bitmask2masklen(a->mask) 145 , INT4_CHARS(b->addr), bitmask2masklen(b->mask) 146 , INT4_CHARS(b->addr), bitmask2masklen(m0) 147 ); 148 #endif 149 b->mask = m0; 150 *cur = b; 151 in_addr_range_destroy(a); 152 } else { 153 #ifdef IIJDEBUG 154 log_printf(LOG_DL_2, 155 "==>%d.%d.%d.%d/%d + %d.%d.%d.%d/%d = %d.%d.%d.%d/%d" 156 , INT4_CHARS(a->addr), bitmask2masklen(a->mask) 157 , INT4_CHARS(b->addr), bitmask2masklen(b->mask) 158 , INT4_CHARS(a->addr), bitmask2masklen(m0) 159 ); 160 #endif 161 a->mask = m0; 162 (*cur)->next = b->next; 163 in_addr_range_destroy(b); 164 } 165 goto restart; 166 } 167 } 168 } 169 170 int 171 in_addr_range_list_includes(struct in_addr_range **list, struct in_addr *addr) 172 { 173 struct in_addr_range *cur; 174 u_int32_t addr0 = ntohl(addr->s_addr); 175 176 for (cur = *list; cur != NULL; cur = cur->next) { 177 if ((addr0 & cur->mask) == (cur->addr & cur->mask)) 178 return 1; 179 } 180 return 0; 181 } 182 183 static int 184 in_addr_range_list_add0(struct in_addr_range **list, u_int32_t addr, 185 u_int32_t mask) 186 { 187 struct in_addr_range *ent; 188 struct in_addr_range **cur; 189 190 if ((ent = in_addr_range_create()) == NULL) 191 return -1; 192 ent->addr = addr; 193 ent->mask = mask; 194 195 for (cur = list; *cur != NULL; cur = &(*cur)->next) { 196 if ((ent->addr & (*cur)->mask) == 197 ((*cur)->addr & (*cur)->mask)) { 198 in_addr_range_destroy(ent); 199 in_addr_range_list_uniq(list); 200 return 0; 201 } 202 if ((ent->addr & ent->mask) == ((*cur)->addr & ent->mask)) { 203 ent->next = (*cur)->next; 204 free(*cur); 205 *cur = ent; 206 in_addr_range_list_uniq(list); 207 return 0; 208 } 209 if ((*cur)->addr > ent->addr) 210 break; 211 } 212 if (cur != NULL) { 213 ent->next = *cur; 214 *cur = ent; 215 in_addr_range_list_uniq(list); 216 } 217 return 0; 218 } 219 220 int 221 in_addr_range_list_add(struct in_addr_range **list, const char *str) 222 { 223 int is_range = 0, is_masklen = 0, is_maskaddr = 0, mask; 224 char *p0, *p1; 225 struct in_addr a0, a1; 226 u_int32_t i0, i1; 227 228 if ((p0 = strdup(str)) == NULL) { 229 #ifdef IIJDEBUG 230 saved_errno = errno; 231 log_printf(LOG_DL_1, "malloc() failed: %m"); 232 errno = saved_errno; 233 #endif 234 return -1; 235 } 236 if ((p1 = strchr(p0, '-')) != NULL) { 237 *p1++ = '\0'; 238 is_range = 1; 239 } else if ((p1 = strchr(p0, '/')) != NULL) { 240 *p1++ = '\0'; 241 242 if (sscanf(p1, "%d", &mask) != 1) { 243 #ifdef IIJDEBUG 244 saved_errno = errno; 245 log_printf(LOG_DL_1, "sscanf(%s) failed: %m", 246 p1); 247 errno = saved_errno; 248 #endif 249 free(p0); 250 return -1; 251 } 252 if (mask < 0 || 32 < mask) { 253 #ifdef IIJDEBUG 254 log_printf(LOG_DL_1, "must be 0 <= masklen <= 32: %d", 255 mask); 256 errno = EINVAL; 257 #endif 258 free(p0); 259 return -1; 260 } 261 is_masklen = 1; 262 } else if ((p1 = strchr(p0, ':')) != NULL) { 263 *p1++ = '\0'; 264 is_maskaddr = 1; 265 } 266 267 if (inet_aton(p0, &a0) != 1) { 268 if (errno == 0) 269 errno = EINVAL; 270 #ifdef IIJDEBUG 271 saved_errno = errno; 272 log_printf(LOG_DL_1, "inet_aton(%s) failed: %m", p0); 273 errno = saved_errno; 274 #endif 275 free(p0); 276 return -1; 277 } 278 if ((is_range || is_maskaddr) && inet_aton(p1, &a1) != 1) { 279 if (errno == 0) 280 errno = EINVAL; 281 #ifdef IIJDEBUG 282 saved_errno = errno; 283 log_printf(LOG_DL_1, "inet_aton(%s) failed: %m", p1); 284 errno = saved_errno; 285 #endif 286 free(p0); 287 return -1; 288 } 289 free(p0); 290 if (is_range) { 291 i0 = ntohl(a0.s_addr); 292 i1 = ntohl(a1.s_addr); 293 for (; i0 <= i1; i0++) 294 in_addr_range_list_add0(list, i0, 0xffffffff); 295 } else if (is_masklen) { 296 i0 = ntohl(a0.s_addr); 297 if (mask == 0) 298 i1 = 0x0; 299 else 300 i1 = 0xffffffffL << (32 - mask); 301 if ((i0 & i1) != i0) { 302 #ifdef IIJDEBUG 303 log_printf(LOG_DL_1, "invalid addr/mask pair: " 304 "%d.%d.%d.%d/%d", 305 INT4_CHARS(i0), bitmask2masklen(i1)); 306 #endif 307 errno = EINVAL; 308 return -1; 309 } 310 in_addr_range_list_add0(list, i0, i1); 311 } else if (is_maskaddr) { 312 i0 = ntohl(a0.s_addr); 313 i1 = ntohl(a1.s_addr); 314 if ((i0 & i1) != i0 || bitmask2masklen(i1) < 0) { 315 #ifdef IIJDEBUG 316 log_printf(LOG_DL_1, "invalid addr/mask pair: " 317 "%d.%d.%d.%d/%d", 318 INT4_CHARS(i0), bitmask2masklen(i1)); 319 #endif 320 errno = EINVAL; 321 return -1; 322 } 323 in_addr_range_list_add0(list, i0, i1); 324 } else { 325 i0 = ntohl(a0.s_addr); 326 in_addr_range_list_add0(list, i0, 0xffffffff); 327 } 328 329 return 0; 330 } 331 332 static int bitmask2masklen(mask) 333 u_int32_t mask; 334 { 335 switch(mask) { 336 case 0x00000000: return 0; 337 case 0x80000000: return 1; 338 case 0xC0000000: return 2; 339 case 0xE0000000: return 3; 340 case 0xF0000000: return 4; 341 case 0xF8000000: return 5; 342 case 0xFC000000: return 6; 343 case 0xFE000000: return 7; 344 case 0xFF000000: return 8; 345 case 0xFF800000: return 9; 346 case 0xFFC00000: return 10; 347 case 0xFFE00000: return 11; 348 case 0xFFF00000: return 12; 349 case 0xFFF80000: return 13; 350 case 0xFFFC0000: return 14; 351 case 0xFFFE0000: return 15; 352 case 0xFFFF0000: return 16; 353 case 0xFFFF8000: return 17; 354 case 0xFFFFC000: return 18; 355 case 0xFFFFE000: return 19; 356 case 0xFFFFF000: return 20; 357 case 0xFFFFF800: return 21; 358 case 0xFFFFFC00: return 22; 359 case 0xFFFFFE00: return 23; 360 case 0xFFFFFF00: return 24; 361 case 0xFFFFFF80: return 25; 362 case 0xFFFFFFC0: return 26; 363 case 0xFFFFFFE0: return 27; 364 case 0xFFFFFFF0: return 28; 365 case 0xFFFFFFF8: return 29; 366 case 0xFFFFFFFC: return 30; 367 case 0xFFFFFFFE: return 31; 368 case 0xFFFFFFFF: return 32; 369 } 370 return -1; 371 } 372 373 #ifdef ADDR_RANGE_DEBUG 374 #include <unistd.h> 375 376 static void usage(void); 377 378 static void 379 usage() 380 { 381 fprintf(stderr, 382 "usage: addr_range [-d] [addr_exp]...\n" 383 "\taddr_exp: 192.168.0.1 (equals 192.168.0.1/32) or \n" 384 "\t 192.168.32.1-192.168.32.255 or \n" 385 "\t 192.168.4.0:255.255.254.0 or \n" 386 "\t 10.0.0.1/24\n" 387 ); 388 } 389 390 int 391 main(int argc, char *argv[]) 392 { 393 int i, ch; 394 struct in_addr_range *list = NULL, *cur; 395 396 debugfp = stderr; 397 debuglevel = 0; 398 399 while ((ch = getopt(argc, argv, "d")) != -1) { 400 switch (ch) { 401 case 'd': 402 debuglevel++; 403 break; 404 default: 405 usage(); 406 exit(1); 407 } 408 } 409 410 argc -= optind; 411 argv += optind; 412 413 if (argc <= 0) { 414 usage(); 415 exit(1); 416 } 417 418 for (i = 0; i < argc; i++) { 419 if (in_addr_range_list_add(&list, argv[i])) { 420 perror(argv[i]); 421 } 422 } 423 for (cur = list; cur != NULL; cur = cur->next) { 424 fprintf(stderr, "%d.%d.%d.%d/%d\n" 425 , INT4_CHARS(cur->addr), bitmask2masklen(cur->mask) 426 ); 427 } 428 in_addr_range_list_remove_all(&list); 429 430 return 0; 431 } 432 #endif 433