Introduce a new feature to IPFW2: lookup tables. These are useful

for handling large sparse address sets.  Initial implementation by
Vsevolod Lobko <seva@ip.net.ua>, refined by me.

MFC after:	1 week

2 files changed, 169 insertions, 4 deletions

diff --git a/sbin/ipfw/ipfw.8 b/sbin/ipfw/ipfw.8
index 4265686..1845c68 100644
--- a/sbin/ipfw/ipfw.8
+++ b/sbin/ipfw/ipfw.8
@@ -1,7 +1,7 @@
 .\"
 .\" $FreeBSD$
 .\"
-.Dd December 1, 2003
+.Dd June 9, 2004
 .Dt IPFW 8
 .Os
 .Sh NAME
@@ -43,6 +43,15 @@
 .Cm set show
 .Pp
 .Nm
+.Cm table Ar number Cm add Ar addr Ns Oo / Ns Ar masklen Oc Op Ar value
+.Nm
+.Cm table Ar number Cm delete Ar addr Ns Op / Ns Ar masklen
+.Nm
+.Cm table Ar number Cm flush
+.Nm
+.Cm table Ar number Cm list
+.Pp
+.Nm
 .Brq Cm pipe | queue
 .Ar number
 .Cm config
@@ -758,13 +767,26 @@ The second format (
 .Em or-block
 with multiple addresses) is provided for convenience only and
 its use is discouraged.
-.It Ar addr : Oo Cm not Oc Brq Cm any | me | Ar addr-list | Ar addr-set
+.It Ar addr : Oo Cm not Oc Bro
+.Cm any | me |
+.Cm table Ns Pq Ar number Ns Op , Ns Ar value
+.Ar | addr-list | addr-set
+.Brc
 .It Cm any
 matches any IP address.
 .It Cm me
 matches any IP address configured on an interface in the system.
 The address list is evaluated at the time the packet is
 analysed.
+.It Cm table Ns Pq Ar number Ns Op , Ns Ar value
+Matches any IP address for which an entry exists in the lookup table
+.Ar number .
+If an optional 32-bit unsigned
+.Ar value
+is also specified, an entry will match only if it has this value.
+See the
+.Sx LOOKUP TABLES
+section below for more information on lookup tables.
 .It Ar addr-list : ip-addr Ns Op Ns , Ns Ar addr-list
 .It Ar ip-addr :
 A host or subnet address specified in one of the following ways:
@@ -1248,6 +1270,43 @@ the Cisco IOS command:
 This option can be used to make anti-spoofing rules to reject all
 packets whose source address is unreachable.
 .El
+.Sh LOOKUP TABLES
+Lookup tables are useful to handle large sparse address sets,
+typically from a hundred to several thousands of entries.
+There could be 128 different lookup tables, numbered 0 to 127.
+.Pp
+Each entry is represented by an
+.Ar addr Ns Op / Ns Ar masklen
+and will match all addresses with base
+.Ar addr
+(specified as a dotted quad or a hostname)
+and mask width of
+.Ar masklen
+bits.
+If
+.Ar masklen
+is not specified, it defaults to 32.
+When looking up an IP address in a table, the most specific
+entry will match.
+Associated with each entry is a 32-bit unsigned
+.Ar value ,
+which can optionally be checked by a rule matching code.
+When adding an entry, if
+.Ar value
+is not specified, it defaults to 0.
+.Pp
+An entry can be added to a table
+.Pq Cm add ,
+removed from a table
+.Pq Cm delete ,
+a table can be examined
+.Pq Cm list
+or flushed
+.Pq Cm flush .
+.Pp
+Internally, each table is stored in a Radix tree, the same way as
+the routing table (see
+.Xr route 4 ) .
 .Sh SETS OF RULES
 Each rule belongs to one of 32 different
 .Em sets
diff --git a/sbin/ipfw/ipfw2.c b/sbin/ipfw/ipfw2.c
index b2e4d10..69561af 100644
--- a/sbin/ipfw/ipfw2.c
+++ b/sbin/ipfw/ipfw2.c
@@ -385,7 +385,8 @@ do_cmd(int optname, void *optval, uintptr_t optlen)
 		err(EX_UNAVAILABLE, "socket");
 
 	if (optname == IP_FW_GET || optname == IP_DUMMYNET_GET ||
-	    optname == IP_FW_ADD)
+	    optname == IP_FW_ADD || optname == IP_FW_TABLE_LIST ||
+	    optname == IP_FW_TABLE_GETSIZE)
 		i = getsockopt(s, IPPROTO_IP, optname, optval,
 			(socklen_t *)optlen);
 	else
@@ -714,6 +715,14 @@ print_ip(ipfw_insn_ip *cmd, char const *s)
 		printf("me");
 		return;
 	}
+	if (cmd->o.opcode == O_IP_SRC_LOOKUP ||
+	    cmd->o.opcode == O_IP_DST_LOOKUP) {
+		printf("table(%u", ((ipfw_insn *)cmd)->arg1);
+		if (len == F_INSN_SIZE(ipfw_insn_u32))
+			printf(",%u", *a);
+		printf(")");
+		return;
+	}
 	if (cmd->o.opcode == O_IP_SRC_SET || cmd->o.opcode == O_IP_DST_SET) {
 		uint32_t x, *map = (uint32_t *)&(cmd->mask);
 		int i, j;
@@ -1088,6 +1097,7 @@ show_ipfw(struct ip_fw *rule, int pcwidth, int bcwidth)
 			break;
 
 		case O_IP_SRC:
+		case O_IP_SRC_LOOKUP:
 		case O_IP_SRC_MASK:
 		case O_IP_SRC_ME:
 		case O_IP_SRC_SET:
@@ -1102,6 +1112,7 @@ show_ipfw(struct ip_fw *rule, int pcwidth, int bcwidth)
 			break;
 
 		case O_IP_DST:
+		case O_IP_DST_LOOKUP:
 		case O_IP_DST_MASK:
 		case O_IP_DST_ME:
 		case O_IP_DST_SET:
@@ -1870,13 +1881,14 @@ help(void)
 "{pipe|queue} N config PIPE-BODY\n"
 "[pipe|queue] {zero|delete|show} [N{,N}]\n"
 "set [disable N... enable N...] | move [rule] X to Y | swap X Y | show\n"
+"table N {add ip[/bits] [value] | delete ip[/bits] | flush | list}\n"
 "\n"
 "RULE-BODY:	check-state [LOG] | ACTION [LOG] ADDR [OPTION_LIST]\n"
 "ACTION:	check-state | allow | count | deny | reject | skipto N |\n"
 "		{divert|tee} PORT | forward ADDR | pipe N | queue N\n"
 "ADDR:		[ MAC dst src ether_type ] \n"
 "		[ from IPADDR [ PORT ] to IPADDR [ PORTLIST ] ]\n"
-"IPADDR:	[not] { any | me | ip/bits{x,y,z} | IPLIST }\n"
+"IPADDR:	[not] { any | me | ip/bits{x,y,z} | table(t[,v]) | IPLIST }\n"
 "IPLIST:	{ ip | ip/bits | ip:mask }[,IPLIST]\n"
 "OPTION_LIST:	OPTION [OPTION_LIST]\n"
 "OPTION:	bridged | {dst-ip|src-ip} ADDR | {dst-port|src-port} LIST |\n"
@@ -1932,6 +1944,21 @@ fill_ip(ipfw_insn_ip *cmd, char *av)
 		return;
 	}
 
+	if (!strncmp(av, "table(", 6)) {
+		char *p = strchr(av + 6, ',');
+
+		if (p)
+			*p++ = '\0';
+		cmd->o.opcode = O_IP_DST_LOOKUP;
+		cmd->o.arg1 = strtoul(av + 6, NULL, 0);
+		if (p) {
+			cmd->o.len |= F_INSN_SIZE(ipfw_insn_u32);
+			d[0] = strtoul(p, NULL, 0);
+		} else
+			cmd->o.len |= F_INSN_SIZE(ipfw_insn);
+		return;
+	}
+
     while (av) {
 	/*
 	 * After the address we can have '/' or ':' indicating a mask,
@@ -2663,6 +2690,8 @@ add_srcip(ipfw_insn *cmd, char *av)
 	fill_ip((ipfw_insn_ip *)cmd, av);
 	if (cmd->opcode == O_IP_DST_SET)			/* set */
 		cmd->opcode = O_IP_SRC_SET;
+	else if (cmd->opcode == O_IP_DST_LOOKUP)		/* table */
+		cmd->opcode = O_IP_SRC_LOOKUP;
 	else if (F_LEN(cmd) == F_INSN_SIZE(ipfw_insn))		/* me */
 		cmd->opcode = O_IP_SRC_ME;
 	else if (F_LEN(cmd) == F_INSN_SIZE(ipfw_insn_u32))	/* one IP */
@@ -2678,6 +2707,8 @@ add_dstip(ipfw_insn *cmd, char *av)
 	fill_ip((ipfw_insn_ip *)cmd, av);
 	if (cmd->opcode == O_IP_DST_SET)			/* set */
 		;
+	else if (cmd->opcode == O_IP_DST_LOOKUP)		/* table */
+		;
 	else if (F_LEN(cmd) == F_INSN_SIZE(ipfw_insn))		/* me */
 		cmd->opcode = O_IP_DST_ME;
 	else if (F_LEN(cmd) == F_INSN_SIZE(ipfw_insn_u32))	/* one IP */
@@ -3593,6 +3624,79 @@ free_args(int ac, char **av)
 }
 
 /*
+ * This one handles all table-related commands
+ * 	ipfw table N add addr[/masklen] [value]
+ * 	ipfw table N delete addr[/masklen]
+ * 	ipfw table N flush
+ * 	ipfw table N list
+ */
+static void
+table_handler(int ac, char *av[])
+{
+	ipfw_table_entry ent;
+	ipfw_table *tbl;
+	int do_add;
+	char *p;
+	socklen_t l;
+	uint32_t a;
+
+	ac--; av++;
+	if (ac && isdigit(**av)) {
+		ent.tbl = atoi(*av);
+		ac--; av++;
+	} else
+		errx(EX_USAGE, "table number required");
+	NEED1("table needs command");
+	if (strncmp(*av, "add", strlen(*av)) == 0 ||
+	    strncmp(*av, "delete", strlen(*av)) == 0) {
+		do_add = **av == 'a';
+		ac--; av++;
+		if (!ac)
+			errx(EX_USAGE, "IP address required");
+		p = strchr(*av, '/');
+		if (p) {
+			*p++ = '\0';
+			ent.masklen = atoi(p);
+			if (ent.masklen > 32)
+				errx(EX_DATAERR, "bad width ``%s''", p);
+		} else
+			ent.masklen = 32;
+		if (lookup_host(*av, (struct in_addr *)&ent.addr) != 0)
+			errx(EX_NOHOST, "hostname ``%s'' unknown", av);
+		ac--; av++;
+		if (do_add && ac)
+			ent.value = strtoul(*av, NULL, 0);
+		else
+			ent.value = 0;
+		if (do_cmd(do_add ? IP_FW_TABLE_ADD : IP_FW_TABLE_DEL,
+		    &ent, sizeof(ent)) < 0)
+			err(EX_OSERR, "setsockopt(IP_FW_TABLE_%s)",
+			    do_add ? "ADD" : "DEL");
+	} else if (strncmp(*av, "flush", strlen(*av)) == 0) {
+		if (do_cmd(IP_FW_TABLE_FLUSH, &ent.tbl, sizeof(ent.tbl)) < 0)
+			err(EX_OSERR, "setsockopt(IP_FW_TABLE_FLUSH)");
+	} else if (strncmp(*av, "list", strlen(*av)) == 0) {
+		a = ent.tbl;
+		l = sizeof(a);
+		if (do_cmd(IP_FW_TABLE_GETSIZE, &a, (uintptr_t)&l) < 0)
+			err(EX_OSERR, "getsockopt(IP_FW_TABLE_GETSIZE)");
+		l = sizeof(*tbl) + a * sizeof(ipfw_table_entry);
+		tbl = malloc(l);
+		if (tbl == NULL)
+			err(EX_OSERR, "malloc");
+		tbl->tbl = ent.tbl;
+		if (do_cmd(IP_FW_TABLE_LIST, tbl, (uintptr_t)&l) < 0)
+			err(EX_OSERR, "getsockopt(IP_FW_TABLE_LIST)");
+		for (a = 0; a < tbl->cnt; a++) {
+			printf("%s/%u %u\n",
+			    inet_ntoa(*(struct in_addr *)&tbl->ent[a].addr),
+			    tbl->ent[a].masklen, tbl->ent[a].value);
+		}
+	} else
+		errx(EX_USAGE, "invalid table command %s", *av);
+}
+
+/*
  * Called with the arguments (excluding program name).
  * Returns 0 if successful, 1 if empty command, errx() in case of errors.
  */
@@ -3822,6 +3926,8 @@ ipfw_main(int oldac, char **oldav)
 		list(ac, av, do_acct);
 	else if (!strncmp(*av, "set", strlen(*av)))
 		sets_handler(ac, av);
+	else if (!strncmp(*av, "table", strlen(*av)))
+		table_handler(ac, av);
 	else if (!strncmp(*av, "enable", strlen(*av)))
 		sysctl_handler(ac, av, 1);
 	else if (!strncmp(*av, "disable", strlen(*av)))