2 * Copyright (c) 2004 Ruslan Ermilov and Vsevolod Lobko.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
14 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
16 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
17 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
18 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
19 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
20 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
21 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
22 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 #include <sys/cdefs.h>
27 __FBSDID("$FreeBSD: head/sys/netinet/ipfw/ip_fw_table.c 200601 2009-12-16 10:48:40Z luigi $");
30 * Lookup table support for ipfw
32 * Lookup tables are implemented (at the moment) using the radix
33 * tree used for routing tables. Tables store key-value entries, where
34 * keys are network prefixes (addr/masklen), and values are integers.
35 * As a degenerate case we can interpret keys as 32-bit integers
38 * The table is protected by the IPFW lock even for manipulation coming
39 * from userland, because operations are typically fast.
42 #if !defined(KLD_MODULE)
44 #include "opt_ipdivert.h"
48 #error IPFIREWALL requires INET.
51 #include "opt_inet6.h"
52 #include "opt_ipsec.h"
54 #include <sys/param.h>
55 #include <sys/systm.h>
56 #include <sys/malloc.h>
57 #include <sys/kernel.h>
59 #include <sys/rwlock.h>
60 #include <sys/socket.h>
61 #include <net/if.h> /* ip_fw.h requires IFNAMSIZ */
62 #include <net/radix.h>
63 #include <net/route.h>
66 #include <netinet/in.h>
67 #include <netinet/ip_fw.h>
68 #include <netinet/ipfw/ip_fw_private.h>
71 #include <security/mac/mac_framework.h>
74 MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
77 struct radix_node rn[2];
78 struct sockaddr_in addr, mask;
83 * The radix code expects addr and mask to be array of bytes,
84 * with the first byte being the length of the array. rn_inithead
85 * is called with the offset in bits of the lookup key within the
86 * array. If we use a sockaddr_in as the underlying type,
87 * sin_len is conveniently located at offset 0, sin_addr is at
88 * offset 4 and normally aligned.
89 * But for portability, let's avoid assumption and make the code explicit
91 #define KEY_LEN(v) *((uint8_t *)&(v))
92 #define KEY_OFS (8*offsetof(struct sockaddr_in, sin_addr))
95 ipfw_add_table_entry(struct ip_fw_chain *ch, uint16_t tbl, in_addr_t addr,
96 uint8_t mlen, uint32_t value)
98 struct radix_node_head *rnh;
99 struct table_entry *ent;
100 struct radix_node *rn;
102 if (tbl >= IPFW_TABLES_MAX)
104 rnh = ch->tables[tbl];
105 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_NOWAIT | M_ZERO);
109 KEY_LEN(ent->addr) = KEY_LEN(ent->mask) = 8;
110 ent->mask.sin_addr.s_addr = htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
111 ent->addr.sin_addr.s_addr = addr & ent->mask.sin_addr.s_addr;
113 rn = rnh->rnh_addaddr(&ent->addr, &ent->mask, rnh, (void *)ent);
116 free(ent, M_IPFW_TBL);
124 ipfw_del_table_entry(struct ip_fw_chain *ch, uint16_t tbl, in_addr_t addr,
127 struct radix_node_head *rnh;
128 struct table_entry *ent;
129 struct sockaddr_in sa, mask;
131 if (tbl >= IPFW_TABLES_MAX)
133 rnh = ch->tables[tbl];
134 KEY_LEN(sa) = KEY_LEN(mask) = 8;
135 mask.sin_addr.s_addr = htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
136 sa.sin_addr.s_addr = addr & mask.sin_addr.s_addr;
138 ent = (struct table_entry *)rnh->rnh_deladdr(&sa, &mask, rnh);
144 free(ent, M_IPFW_TBL);
149 flush_table_entry(struct radix_node *rn, void *arg)
151 struct radix_node_head * const rnh = arg;
152 struct table_entry *ent;
154 ent = (struct table_entry *)
155 rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, rnh);
157 free(ent, M_IPFW_TBL);
162 ipfw_flush_table(struct ip_fw_chain *ch, uint16_t tbl)
164 struct radix_node_head *rnh;
166 IPFW_WLOCK_ASSERT(ch);
168 if (tbl >= IPFW_TABLES_MAX)
170 rnh = ch->tables[tbl];
171 KASSERT(rnh != NULL, ("NULL IPFW table"));
172 rnh->rnh_walktree(rnh, flush_table_entry, rnh);
177 ipfw_flush_tables(struct ip_fw_chain *ch)
181 IPFW_WLOCK_ASSERT(ch);
183 for (tbl = 0; tbl < IPFW_TABLES_MAX; tbl++)
184 ipfw_flush_table(ch, tbl);
188 ipfw_init_tables(struct ip_fw_chain *ch)
193 for (i = 0; i < IPFW_TABLES_MAX; i++) {
194 if (!rn_inithead((void **)&ch->tables[i], KEY_OFS)) {
195 for (j = 0; j < i; j++) {
196 (void) ipfw_flush_table(ch, j);
205 ipfw_lookup_table(struct ip_fw_chain *ch, uint16_t tbl, in_addr_t addr,
208 struct radix_node_head *rnh;
209 struct table_entry *ent;
210 struct sockaddr_in sa;
212 if (tbl >= IPFW_TABLES_MAX)
214 rnh = ch->tables[tbl];
216 sa.sin_addr.s_addr = addr;
217 ent = (struct table_entry *)(rnh->rnh_lookup(&sa, NULL, rnh));
226 count_table_entry(struct radix_node *rn, void *arg)
228 u_int32_t * const cnt = arg;
235 ipfw_count_table(struct ip_fw_chain *ch, uint32_t tbl, uint32_t *cnt)
237 struct radix_node_head *rnh;
239 if (tbl >= IPFW_TABLES_MAX)
241 rnh = ch->tables[tbl];
243 rnh->rnh_walktree(rnh, count_table_entry, cnt);
248 dump_table_entry(struct radix_node *rn, void *arg)
250 struct table_entry * const n = (struct table_entry *)rn;
251 ipfw_table * const tbl = arg;
252 ipfw_table_entry *ent;
254 if (tbl->cnt == tbl->size)
256 ent = &tbl->ent[tbl->cnt];
258 if (in_nullhost(n->mask.sin_addr))
261 ent->masklen = 33 - ffs(ntohl(n->mask.sin_addr.s_addr));
262 ent->addr = n->addr.sin_addr.s_addr;
263 ent->value = n->value;
269 ipfw_dump_table(struct ip_fw_chain *ch, ipfw_table *tbl)
271 struct radix_node_head *rnh;
273 if (tbl->tbl >= IPFW_TABLES_MAX)
275 rnh = ch->tables[tbl->tbl];
277 rnh->rnh_walktree(rnh, dump_table_entry, tbl);