/* $OpenBSD: addr_range.c,v 1.8 2024/08/22 07:56:47 florian Exp $ */ /*- * Copyright (c) 2009 Internet Initiative Japan Inc. * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ /* * addr_range.c - Parser/aggregator for varios address/network expressions. * * Input: 192.168.0.0/24 192.168.1.0/24 * Output: 192.168.0.0/23 * * Input: 192.168.0.128-192.168.0.255 * Output: 192.168.0.128/25 * * Notice: * - Byte order of 'addr' and 'mask' (members of struct in_addr_range) * are host byte order. * - Parsing address range like 192.168.0.0-192.168.255.255 costs much of * cpu/memory. * * Example code: * * struct in_addr_range *list = NULL, *cur; * * in_addr_range_list_add(&list, "192.168.0.128-192.168.0.255"); * in_addr_range_list_add(&list, "192.168.1.128-192.168.1.255"); * for (cur = list; cur != NULL; cur = cur->next) { * // do something * struct in_addr a, m; * a.s_addr = htonl(cur->addr); * m.s_addr = htonl(cur->mask); * } * in_addr_range_list_remove_all(&list); * * Author: * Yasuoka Masahiko * * $Id: addr_range.c,v 1.8 2024/08/22 07:56:47 florian Exp $ */ #ifdef ADDR_RANGE_DEBUG #define IIJDEBUG #endif #include #include #include #include #include #include #include #include #include #ifdef IIJDEBUG #include static int saved_errno; #define INT4_CHARS(x) \ ((x) & 0xff000000) >> 24, ((x) & 0x00ff0000) >> 16, \ ((x) & 0x0000ff00) >> 8, ((x) & 0x000000ff) #endif #include "addr_range.h" static void in_addr_range_list_uniq(struct in_addr_range **); static int in_addr_range_list_add0(struct in_addr_range **, u_int32_t, u_int32_t); static int bitmask2masklen(u_int32_t); struct in_addr_range * in_addr_range_create() { struct in_addr_range *_this; if ((_this = malloc(sizeof(struct in_addr_range))) == NULL) return NULL; memset(_this, 0xff, sizeof(struct in_addr_range)); _this->next = NULL; return _this; } void in_addr_range_destroy(struct in_addr_range *_this) { free(_this); } void in_addr_range_list_remove_all(struct in_addr_range **list) { struct in_addr_range *cur0, *cur; cur = *list; while (cur != NULL) { cur0 = cur; cur = cur->next; in_addr_range_destroy(cur0); } *list = NULL; } static void in_addr_range_list_uniq(struct in_addr_range **list) { u_int32_t m0; struct in_addr_range **cur, *a, *b; restart: for (cur = list; *cur != NULL; cur = &(*cur)->next) { if ((*cur)->next == NULL) continue; a = *cur; b = (*cur)->next; m0 = 0xffffffff ^ a->mask; if (a->mask == b->mask && ( a->addr - b->addr == m0 + 1 || b->addr - a->addr == m0 + 1)) { m0 = m0 * 2 + 1; m0 ^= 0xffffffff; if ((a->addr & m0) != (b->addr & m0)) continue; if (a->addr > b->addr) { #ifdef IIJDEBUG log_printf(LOG_DL_2, "%d.%d.%d.%d/%d + %d.%d.%d.%d/%d = %d.%d.%d.%d/%d" , INT4_CHARS(a->addr), bitmask2masklen(a->mask) , INT4_CHARS(b->addr), bitmask2masklen(b->mask) , INT4_CHARS(b->addr), bitmask2masklen(m0) ); #endif b->mask = m0; *cur = b; in_addr_range_destroy(a); } else { #ifdef IIJDEBUG log_printf(LOG_DL_2, "==>%d.%d.%d.%d/%d + %d.%d.%d.%d/%d = %d.%d.%d.%d/%d" , INT4_CHARS(a->addr), bitmask2masklen(a->mask) , INT4_CHARS(b->addr), bitmask2masklen(b->mask) , INT4_CHARS(a->addr), bitmask2masklen(m0) ); #endif a->mask = m0; (*cur)->next = b->next; in_addr_range_destroy(b); } goto restart; } } } int in_addr_range_list_includes(struct in_addr_range **list, struct in_addr *addr) { struct in_addr_range *cur; u_int32_t addr0 = ntohl(addr->s_addr); for (cur = *list; cur != NULL; cur = cur->next) { if ((addr0 & cur->mask) == (cur->addr & cur->mask)) return 1; } return 0; } static int in_addr_range_list_add0(struct in_addr_range **list, u_int32_t addr, u_int32_t mask) { struct in_addr_range *ent; struct in_addr_range **cur; if ((ent = in_addr_range_create()) == NULL) return -1; ent->addr = addr; ent->mask = mask; for (cur = list; *cur != NULL; cur = &(*cur)->next) { if ((ent->addr & (*cur)->mask) == ((*cur)->addr & (*cur)->mask)) { in_addr_range_destroy(ent); in_addr_range_list_uniq(list); return 0; } if ((ent->addr & ent->mask) == ((*cur)->addr & ent->mask)) { ent->next = (*cur)->next; free(*cur); *cur = ent; in_addr_range_list_uniq(list); return 0; } if ((*cur)->addr > ent->addr) break; } if (cur != NULL) { ent->next = *cur; *cur = ent; in_addr_range_list_uniq(list); } return 0; } int in_addr_range_list_add(struct in_addr_range **list, const char *str) { int is_range = 0, is_masklen = 0, is_maskaddr = 0, mask; char *p0, *p1; struct in_addr a0, a1; u_int32_t i0, i1; if ((p0 = strdup(str)) == NULL) { #ifdef IIJDEBUG saved_errno = errno; log_printf(LOG_DL_1, "malloc() failed: %m"); errno = saved_errno; #endif return -1; } if ((p1 = strchr(p0, '-')) != NULL) { *p1++ = '\0'; is_range = 1; } else if ((p1 = strchr(p0, '/')) != NULL) { *p1++ = '\0'; if (sscanf(p1, "%d", &mask) != 1) { #ifdef IIJDEBUG saved_errno = errno; log_printf(LOG_DL_1, "sscanf(%s) failed: %m", p1); errno = saved_errno; #endif free(p0); return -1; } if (mask < 0 || 32 < mask) { #ifdef IIJDEBUG log_printf(LOG_DL_1, "must be 0 <= masklen <= 32: %d", mask); errno = EINVAL; #endif free(p0); return -1; } is_masklen = 1; } else if ((p1 = strchr(p0, ':')) != NULL) { *p1++ = '\0'; is_maskaddr = 1; } if (inet_pton(AF_INET, p0, &a0) != 1) { if (errno == 0) errno = EINVAL; #ifdef IIJDEBUG saved_errno = errno; log_printf(LOG_DL_1, "inet_pton(%s) failed: %m", p0); errno = saved_errno; #endif free(p0); return -1; } if ((is_range || is_maskaddr) && inet_pton(AF_INET, p1, &a1) != 1) { if (errno == 0) errno = EINVAL; #ifdef IIJDEBUG saved_errno = errno; log_printf(LOG_DL_1, "inet_pton(%s) failed: %m", p1); errno = saved_errno; #endif free(p0); return -1; } free(p0); if (is_range) { i0 = ntohl(a0.s_addr); i1 = ntohl(a1.s_addr); for (; i0 <= i1; i0++) in_addr_range_list_add0(list, i0, 0xffffffff); } else if (is_masklen) { i0 = ntohl(a0.s_addr); if (mask == 0) i1 = 0x0; else i1 = 0xffffffffL << (32 - mask); if ((i0 & i1) != i0) { #ifdef IIJDEBUG log_printf(LOG_DL_1, "invalid addr/mask pair: " "%d.%d.%d.%d/%d", INT4_CHARS(i0), bitmask2masklen(i1)); #endif errno = EINVAL; return -1; } in_addr_range_list_add0(list, i0, i1); } else if (is_maskaddr) { i0 = ntohl(a0.s_addr); i1 = ntohl(a1.s_addr); if ((i0 & i1) != i0 || bitmask2masklen(i1) < 0) { #ifdef IIJDEBUG log_printf(LOG_DL_1, "invalid addr/mask pair: " "%d.%d.%d.%d/%d", INT4_CHARS(i0), bitmask2masklen(i1)); #endif errno = EINVAL; return -1; } in_addr_range_list_add0(list, i0, i1); } else { i0 = ntohl(a0.s_addr); in_addr_range_list_add0(list, i0, 0xffffffff); } return 0; } static int bitmask2masklen(u_int32_t mask) { switch(mask) { case 0x00000000: return 0; case 0x80000000: return 1; case 0xC0000000: return 2; case 0xE0000000: return 3; case 0xF0000000: return 4; case 0xF8000000: return 5; case 0xFC000000: return 6; case 0xFE000000: return 7; case 0xFF000000: return 8; case 0xFF800000: return 9; case 0xFFC00000: return 10; case 0xFFE00000: return 11; case 0xFFF00000: return 12; case 0xFFF80000: return 13; case 0xFFFC0000: return 14; case 0xFFFE0000: return 15; case 0xFFFF0000: return 16; case 0xFFFF8000: return 17; case 0xFFFFC000: return 18; case 0xFFFFE000: return 19; case 0xFFFFF000: return 20; case 0xFFFFF800: return 21; case 0xFFFFFC00: return 22; case 0xFFFFFE00: return 23; case 0xFFFFFF00: return 24; case 0xFFFFFF80: return 25; case 0xFFFFFFC0: return 26; case 0xFFFFFFE0: return 27; case 0xFFFFFFF0: return 28; case 0xFFFFFFF8: return 29; case 0xFFFFFFFC: return 30; case 0xFFFFFFFE: return 31; case 0xFFFFFFFF: return 32; } return -1; } #ifdef ADDR_RANGE_DEBUG #include static void usage(void); static void usage() { fprintf(stderr, "usage: addr_range [-d] [addr_exp]...\n" "\taddr_exp: 192.168.0.1 (equals 192.168.0.1/32) or \n" "\t 192.168.32.1-192.168.32.255 or \n" "\t 192.168.4.0:255.255.254.0 or \n" "\t 10.0.0.1/24\n" ); } int main(int argc, char *argv[]) { int i, ch; struct in_addr_range *list = NULL, *cur; debugfp = stderr; debuglevel = 0; while ((ch = getopt(argc, argv, "d")) != -1) { switch (ch) { case 'd': debuglevel++; break; default: usage(); exit(1); } } argc -= optind; argv += optind; if (argc <= 0) { usage(); exit(1); } for (i = 0; i < argc; i++) { if (in_addr_range_list_add(&list, argv[i])) { perror(argv[i]); } } for (cur = list; cur != NULL; cur = cur->next) { fprintf(stderr, "%d.%d.%d.%d/%d\n" , INT4_CHARS(cur->addr), bitmask2masklen(cur->mask) ); } in_addr_range_list_remove_all(&list); return 0; } #endif