path: root/usr.sbin/npppd/common/addr_range.c

/* $OpenBSD: addr_range.c,v 1.2 2010/07/01 03:38:17 yasuoka 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 <yasuoka@iij.ad.jp>
 *
 * $Id: addr_range.c,v 1.2 2010/07/01 03:38:17 yasuoka Exp $
 */
#ifdef ADDR_RANGE_DEBUG
#define IIJDEBUG
#endif

#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#include <errno.h>
#include <syslog.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#ifdef IIJDEBUG
#include <debugutil.h>
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 __P((struct in_addr_range **));
static int   in_addr_range_list_add0 __P((struct in_addr_range **, u_int32_t, u_int32_t));
static int   bitmask2masklen __P((u_int32_t));

struct in_addr_range *
in_addr_range_create()
{
	struct in_addr_range *_this;
	if ((_this = (struct in_addr_range *)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() failes: %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) failes: %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_aton(p0, &a0) != 1) {
		if (errno == 0)
			errno = EINVAL;
#ifdef IIJDEBUG
		saved_errno = errno;
		log_printf(LOG_DL_1, "inet_aton(%s) failes: %m", p0);
		errno = saved_errno;
#endif
		free(p0);
		return -1;
	}
	if ((is_range || is_maskaddr) && inet_aton(p1, &a1) != 1) {
		if (errno == 0)
			errno = EINVAL;
#ifdef IIJDEBUG
		saved_errno = errno;
		log_printf(LOG_DL_1, "inet_aton(%s) failes: %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(mask)
	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 <unistd.h>

static void usage __P ((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