1 /* $OpenBSD: addr_range.c,v 1.8 2024/08/22 07:56:47 florian 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.8 2024/08/22 07:56:47 florian Exp $ 60 */ 61 #ifdef ADDR_RANGE_DEBUG 62 #define IIJDEBUG 63 #endif 64 65 #include <sys/types.h> 66 #include <sys/socket.h> 67 #include <netinet/in.h> 68 #include <arpa/inet.h> 69 70 #include <errno.h> 71 #include <syslog.h> 72 #include <string.h> 73 #include <stdlib.h> 74 #include <stdio.h> 75 76 #ifdef IIJDEBUG 77 #include <debugutil.h> 78 static int saved_errno; 79 #define INT4_CHARS(x) \ 80 ((x) & 0xff000000) >> 24, ((x) & 0x00ff0000) >> 16, \ 81 ((x) & 0x0000ff00) >> 8, ((x) & 0x000000ff) 82 #endif 83 #include "addr_range.h" 84 85 static void in_addr_range_list_uniq(struct in_addr_range **); 86 static int in_addr_range_list_add0(struct in_addr_range **, u_int32_t, u_int32_t); 87 static int bitmask2masklen(u_int32_t); 88 89 struct in_addr_range * 90 in_addr_range_create() 91 { 92 struct in_addr_range *_this; 93 if ((_this = malloc(sizeof(struct in_addr_range))) == NULL) 94 return NULL; 95 memset(_this, 0xff, sizeof(struct in_addr_range)); 96 _this->next = NULL; 97 return _this; 98 } 99 100 101 void 102 in_addr_range_destroy(struct in_addr_range *_this) 103 { 104 free(_this); 105 } 106 107 void 108 in_addr_range_list_remove_all(struct in_addr_range **list) 109 { 110 struct in_addr_range *cur0, *cur; 111 112 cur = *list; 113 while (cur != NULL) { 114 cur0 = cur; 115 cur = cur->next; 116 in_addr_range_destroy(cur0); 117 } 118 *list = NULL; 119 } 120 121 static void 122 in_addr_range_list_uniq(struct in_addr_range **list) 123 { 124 u_int32_t m0; 125 struct in_addr_range **cur, *a, *b; 126 127 restart: 128 for (cur = list; *cur != NULL; cur = &(*cur)->next) { 129 if ((*cur)->next == NULL) 130 continue; 131 a = *cur; 132 b = (*cur)->next; 133 m0 = 0xffffffff ^ a->mask; 134 if (a->mask == b->mask && ( 135 a->addr - b->addr == m0 + 1 || 136 b->addr - a->addr == m0 + 1)) { 137 m0 = m0 * 2 + 1; 138 m0 ^= 0xffffffff; 139 if ((a->addr & m0) != (b->addr & m0)) 140 continue; 141 if (a->addr > b->addr) { 142 #ifdef IIJDEBUG 143 log_printf(LOG_DL_2, 144 "%d.%d.%d.%d/%d + %d.%d.%d.%d/%d = %d.%d.%d.%d/%d" 145 , INT4_CHARS(a->addr), bitmask2masklen(a->mask) 146 , INT4_CHARS(b->addr), bitmask2masklen(b->mask) 147 , INT4_CHARS(b->addr), bitmask2masklen(m0) 148 ); 149 #endif 150 b->mask = m0; 151 *cur = b; 152 in_addr_range_destroy(a); 153 } else { 154 #ifdef IIJDEBUG 155 log_printf(LOG_DL_2, 156 "==>%d.%d.%d.%d/%d + %d.%d.%d.%d/%d = %d.%d.%d.%d/%d" 157 , INT4_CHARS(a->addr), bitmask2masklen(a->mask) 158 , INT4_CHARS(b->addr), bitmask2masklen(b->mask) 159 , INT4_CHARS(a->addr), bitmask2masklen(m0) 160 ); 161 #endif 162 a->mask = m0; 163 (*cur)->next = b->next; 164 in_addr_range_destroy(b); 165 } 166 goto restart; 167 } 168 } 169 } 170 171 int 172 in_addr_range_list_includes(struct in_addr_range **list, struct in_addr *addr) 173 { 174 struct in_addr_range *cur; 175 u_int32_t addr0 = ntohl(addr->s_addr); 176 177 for (cur = *list; cur != NULL; cur = cur->next) { 178 if ((addr0 & cur->mask) == (cur->addr & cur->mask)) 179 return 1; 180 } 181 return 0; 182 } 183 184 static int 185 in_addr_range_list_add0(struct in_addr_range **list, u_int32_t addr, 186 u_int32_t mask) 187 { 188 struct in_addr_range *ent; 189 struct in_addr_range **cur; 190 191 if ((ent = in_addr_range_create()) == NULL) 192 return -1; 193 ent->addr = addr; 194 ent->mask = mask; 195 196 for (cur = list; *cur != NULL; cur = &(*cur)->next) { 197 if ((ent->addr & (*cur)->mask) == 198 ((*cur)->addr & (*cur)->mask)) { 199 in_addr_range_destroy(ent); 200 in_addr_range_list_uniq(list); 201 return 0; 202 } 203 if ((ent->addr & ent->mask) == ((*cur)->addr & ent->mask)) { 204 ent->next = (*cur)->next; 205 free(*cur); 206 *cur = ent; 207 in_addr_range_list_uniq(list); 208 return 0; 209 } 210 if ((*cur)->addr > ent->addr) 211 break; 212 } 213 if (cur != NULL) { 214 ent->next = *cur; 215 *cur = ent; 216 in_addr_range_list_uniq(list); 217 } 218 return 0; 219 } 220 221 int 222 in_addr_range_list_add(struct in_addr_range **list, const char *str) 223 { 224 int is_range = 0, is_masklen = 0, is_maskaddr = 0, mask; 225 char *p0, *p1; 226 struct in_addr a0, a1; 227 u_int32_t i0, i1; 228 229 if ((p0 = strdup(str)) == NULL) { 230 #ifdef IIJDEBUG 231 saved_errno = errno; 232 log_printf(LOG_DL_1, "malloc() failed: %m"); 233 errno = saved_errno; 234 #endif 235 return -1; 236 } 237 if ((p1 = strchr(p0, '-')) != NULL) { 238 *p1++ = '\0'; 239 is_range = 1; 240 } else if ((p1 = strchr(p0, '/')) != NULL) { 241 *p1++ = '\0'; 242 243 if (sscanf(p1, "%d", &mask) != 1) { 244 #ifdef IIJDEBUG 245 saved_errno = errno; 246 log_printf(LOG_DL_1, "sscanf(%s) failed: %m", 247 p1); 248 errno = saved_errno; 249 #endif 250 free(p0); 251 return -1; 252 } 253 if (mask < 0 || 32 < mask) { 254 #ifdef IIJDEBUG 255 log_printf(LOG_DL_1, "must be 0 <= masklen <= 32: %d", 256 mask); 257 errno = EINVAL; 258 #endif 259 free(p0); 260 return -1; 261 } 262 is_masklen = 1; 263 } else if ((p1 = strchr(p0, ':')) != NULL) { 264 *p1++ = '\0'; 265 is_maskaddr = 1; 266 } 267 268 if (inet_pton(AF_INET, p0, &a0) != 1) { 269 if (errno == 0) 270 errno = EINVAL; 271 #ifdef IIJDEBUG 272 saved_errno = errno; 273 log_printf(LOG_DL_1, "inet_pton(%s) failed: %m", p0); 274 errno = saved_errno; 275 #endif 276 free(p0); 277 return -1; 278 } 279 if ((is_range || is_maskaddr) && inet_pton(AF_INET, p1, &a1) != 1) { 280 if (errno == 0) 281 errno = EINVAL; 282 #ifdef IIJDEBUG 283 saved_errno = errno; 284 log_printf(LOG_DL_1, "inet_pton(%s) failed: %m", p1); 285 errno = saved_errno; 286 #endif 287 free(p0); 288 return -1; 289 } 290 free(p0); 291 if (is_range) { 292 i0 = ntohl(a0.s_addr); 293 i1 = ntohl(a1.s_addr); 294 for (; i0 <= i1; i0++) 295 in_addr_range_list_add0(list, i0, 0xffffffff); 296 } else if (is_masklen) { 297 i0 = ntohl(a0.s_addr); 298 if (mask == 0) 299 i1 = 0x0; 300 else 301 i1 = 0xffffffffL << (32 - mask); 302 if ((i0 & i1) != i0) { 303 #ifdef IIJDEBUG 304 log_printf(LOG_DL_1, "invalid addr/mask pair: " 305 "%d.%d.%d.%d/%d", 306 INT4_CHARS(i0), bitmask2masklen(i1)); 307 #endif 308 errno = EINVAL; 309 return -1; 310 } 311 in_addr_range_list_add0(list, i0, i1); 312 } else if (is_maskaddr) { 313 i0 = ntohl(a0.s_addr); 314 i1 = ntohl(a1.s_addr); 315 if ((i0 & i1) != i0 || bitmask2masklen(i1) < 0) { 316 #ifdef IIJDEBUG 317 log_printf(LOG_DL_1, "invalid addr/mask pair: " 318 "%d.%d.%d.%d/%d", 319 INT4_CHARS(i0), bitmask2masklen(i1)); 320 #endif 321 errno = EINVAL; 322 return -1; 323 } 324 in_addr_range_list_add0(list, i0, i1); 325 } else { 326 i0 = ntohl(a0.s_addr); 327 in_addr_range_list_add0(list, i0, 0xffffffff); 328 } 329 330 return 0; 331 } 332 333 static int bitmask2masklen(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