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 *
in_addr_range_create()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
in_addr_range_destroy(struct in_addr_range * _this)102 in_addr_range_destroy(struct in_addr_range *_this)
103 {
104 free(_this);
105 }
106
107 void
in_addr_range_list_remove_all(struct in_addr_range ** list)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
in_addr_range_list_uniq(struct in_addr_range ** list)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
in_addr_range_list_includes(struct in_addr_range ** list,struct in_addr * addr)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
in_addr_range_list_add0(struct in_addr_range ** list,u_int32_t addr,u_int32_t mask)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
in_addr_range_list_add(struct in_addr_range ** list,const char * str)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
bitmask2masklen(u_int32_t mask)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
usage()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
main(int argc,char * argv[])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