GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/npppd/npppd/../common/addr_range.c Lines: 0 144 0.0 %
Date: 2017-11-13 Branches: 0 106 0.0 %

Line Branch Exec Source
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