1/*-
2 * Copyright (c) 2004 Ruslan Ermilov and Vsevolod Lobko.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
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.
12 *
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
23 * SUCH DAMAGE.
24 */
25
26#include <sys/cdefs.h>
27__FBSDID("$FreeBSD: head/sys/netinet/ipfw/ip_fw_table.c 225518 2011-09-12 21:09:56Z jhb $");
28
29/*
30 * Lookup table support for ipfw
31 *
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
36 * (with a /32 mask).
37 *
38 * The table is protected by the IPFW lock even for manipulation coming
39 * from userland, because operations are typically fast.
40 */
41
42#include "opt_ipfw.h"
43#if !defined(KLD_MODULE)
44#include "opt_ipdivert.h"
45#include "opt_ipdn.h"
46#include "opt_inet.h"
47#ifndef INET
48#error IPFIREWALL requires INET.
49#endif /* INET */
50#endif
51#include "opt_inet6.h"
52#include "opt_ipsec.h"
53
54#include <sys/param.h>
55#include <sys/systm.h>
56#include <sys/malloc.h>
57#include <sys/kernel.h>
58#include <sys/lock.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>
64#include <net/vnet.h>
65
66#include <netinet/in.h>
67#include <netinet/ip_var.h> /* struct ipfw_rule_ref */
68#include <netinet/ip_fw.h>
69#include <sys/queue.h> /* LIST_HEAD */
70#include <netinet/ipfw/ip_fw_private.h>
71
72#ifdef MAC
73#include <security/mac/mac_framework.h>
74#endif
75
76MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
77
78struct table_entry {
79 struct radix_node rn[2];
80 struct sockaddr_in addr, mask;
81 u_int32_t value;
82};
83
84/*
85 * The radix code expects addr and mask to be array of bytes,
86 * with the first byte being the length of the array. rn_inithead
87 * is called with the offset in bits of the lookup key within the
88 * array. If we use a sockaddr_in as the underlying type,
89 * sin_len is conveniently located at offset 0, sin_addr is at
90 * offset 4 and normally aligned.
91 * But for portability, let's avoid assumption and make the code explicit
92 */
93#define KEY_LEN(v) *((uint8_t *)&(v))
94#define KEY_OFS (8*offsetof(struct sockaddr_in, sin_addr))
95
96int
97ipfw_add_table_entry(struct ip_fw_chain *ch, uint16_t tbl, in_addr_t addr,
98 uint8_t mlen, uint32_t value)
99{
100 struct radix_node_head *rnh;
101 struct table_entry *ent;
102 struct radix_node *rn;
103
104 if (tbl >= IPFW_TABLES_MAX)
105 return (EINVAL);
106 rnh = ch->tables[tbl];
107 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_NOWAIT | M_ZERO);
108 if (ent == NULL)
109 return (ENOMEM);
110 ent->value = value;
111 KEY_LEN(ent->addr) = KEY_LEN(ent->mask) = 8;
112 ent->mask.sin_addr.s_addr = htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
113 ent->addr.sin_addr.s_addr = addr & ent->mask.sin_addr.s_addr;
114 IPFW_WLOCK(ch);
115 rn = rnh->rnh_addaddr(&ent->addr, &ent->mask, rnh, (void *)ent);
116 if (rn == NULL) {
117 IPFW_WUNLOCK(ch);
118 free(ent, M_IPFW_TBL);
119 return (EEXIST);
120 }
121 IPFW_WUNLOCK(ch);
122 return (0);
123}
124
125int
126ipfw_del_table_entry(struct ip_fw_chain *ch, uint16_t tbl, in_addr_t addr,
127 uint8_t mlen)
128{
129 struct radix_node_head *rnh;
130 struct table_entry *ent;
131 struct sockaddr_in sa, mask;
132
133 if (tbl >= IPFW_TABLES_MAX)
134 return (EINVAL);
135 rnh = ch->tables[tbl];
136 KEY_LEN(sa) = KEY_LEN(mask) = 8;
137 mask.sin_addr.s_addr = htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
138 sa.sin_addr.s_addr = addr & mask.sin_addr.s_addr;
139 IPFW_WLOCK(ch);
140 ent = (struct table_entry *)rnh->rnh_deladdr(&sa, &mask, rnh);
141 if (ent == NULL) {
142 IPFW_WUNLOCK(ch);
143 return (ESRCH);
144 }
145 IPFW_WUNLOCK(ch);
146 free(ent, M_IPFW_TBL);
147 return (0);
148}
149
150static int
151flush_table_entry(struct radix_node *rn, void *arg)
152{
153 struct radix_node_head * const rnh = arg;
154 struct table_entry *ent;
155
156 ent = (struct table_entry *)
157 rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, rnh);
158 if (ent != NULL)
159 free(ent, M_IPFW_TBL);
160 return (0);
161}
162
163int
164ipfw_flush_table(struct ip_fw_chain *ch, uint16_t tbl)
165{
166 struct radix_node_head *rnh;
167
168 IPFW_WLOCK_ASSERT(ch);
169
170 if (tbl >= IPFW_TABLES_MAX)
171 return (EINVAL);
172 rnh = ch->tables[tbl];
173 KASSERT(rnh != NULL, ("NULL IPFW table"));
174 rnh->rnh_walktree(rnh, flush_table_entry, rnh);
175 return (0);
176}
177
178void
179ipfw_destroy_tables(struct ip_fw_chain *ch)
180{
181 uint16_t tbl;
182 struct radix_node_head *rnh;
183
184 IPFW_WLOCK_ASSERT(ch);
185
186 for (tbl = 0; tbl < IPFW_TABLES_MAX; tbl++) {
187 ipfw_flush_table(ch, tbl);
188 rnh = ch->tables[tbl];
189 rn_detachhead((void **)&rnh);
190 }
191}
192
193int
194ipfw_init_tables(struct ip_fw_chain *ch)
195{
196 int i;
197 uint16_t j;
198
199 for (i = 0; i < IPFW_TABLES_MAX; i++) {
200 if (!rn_inithead((void **)&ch->tables[i], KEY_OFS)) {
201 for (j = 0; j < i; j++) {
202 (void) ipfw_flush_table(ch, j);
203 }
204 return (ENOMEM);
205 }
206 }
207 return (0);
208}
209
210int
211ipfw_lookup_table(struct ip_fw_chain *ch, uint16_t tbl, in_addr_t addr,
212 uint32_t *val)
213{
214 struct radix_node_head *rnh;
215 struct table_entry *ent;
216 struct sockaddr_in sa;
217
218 if (tbl >= IPFW_TABLES_MAX)
219 return (0);
220 rnh = ch->tables[tbl];
221 KEY_LEN(sa) = 8;
222 sa.sin_addr.s_addr = addr;
223 ent = (struct table_entry *)(rnh->rnh_lookup(&sa, NULL, rnh));
224 if (ent != NULL) {
225 *val = ent->value;
226 return (1);
227 }
228 return (0);
229}
230
231static int
232count_table_entry(struct radix_node *rn, void *arg)
233{
234 u_int32_t * const cnt = arg;
235
236 (*cnt)++;
237 return (0);
238}
239
240int
241ipfw_count_table(struct ip_fw_chain *ch, uint32_t tbl, uint32_t *cnt)
242{
243 struct radix_node_head *rnh;
244
245 if (tbl >= IPFW_TABLES_MAX)
246 return (EINVAL);
247 rnh = ch->tables[tbl];
248 *cnt = 0;
249 rnh->rnh_walktree(rnh, count_table_entry, cnt);
250 return (0);
251}
252
253static int
254dump_table_entry(struct radix_node *rn, void *arg)
255{
256 struct table_entry * const n = (struct table_entry *)rn;
257 ipfw_table * const tbl = arg;
258 ipfw_table_entry *ent;
259
260 if (tbl->cnt == tbl->size)
261 return (1);
262 ent = &tbl->ent[tbl->cnt];
263 ent->tbl = tbl->tbl;
264 if (in_nullhost(n->mask.sin_addr))
265 ent->masklen = 0;
266 else
267 ent->masklen = 33 - ffs(ntohl(n->mask.sin_addr.s_addr));
268 ent->addr = n->addr.sin_addr.s_addr;
269 ent->value = n->value;
270 tbl->cnt++;
271 return (0);
272}
273
274int
275ipfw_dump_table(struct ip_fw_chain *ch, ipfw_table *tbl)
276{
277 struct radix_node_head *rnh;
278
279 if (tbl->tbl >= IPFW_TABLES_MAX)
280 return (EINVAL);
281 rnh = ch->tables[tbl->tbl];
282 tbl->cnt = 0;
283 rnh->rnh_walktree(rnh, dump_table_entry, tbl);
284 return (0);
285}
286/* end of file */
2 * Copyright (c) 2004 Ruslan Ermilov and Vsevolod Lobko.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
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.
12 *
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
23 * SUCH DAMAGE.
24 */
25
26#include <sys/cdefs.h>
27__FBSDID("$FreeBSD: head/sys/netinet/ipfw/ip_fw_table.c 225518 2011-09-12 21:09:56Z jhb $");
28
29/*
30 * Lookup table support for ipfw
31 *
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
36 * (with a /32 mask).
37 *
38 * The table is protected by the IPFW lock even for manipulation coming
39 * from userland, because operations are typically fast.
40 */
41
42#include "opt_ipfw.h"
43#if !defined(KLD_MODULE)
44#include "opt_ipdivert.h"
45#include "opt_ipdn.h"
46#include "opt_inet.h"
47#ifndef INET
48#error IPFIREWALL requires INET.
49#endif /* INET */
50#endif
51#include "opt_inet6.h"
52#include "opt_ipsec.h"
53
54#include <sys/param.h>
55#include <sys/systm.h>
56#include <sys/malloc.h>
57#include <sys/kernel.h>
58#include <sys/lock.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>
64#include <net/vnet.h>
65
66#include <netinet/in.h>
67#include <netinet/ip_var.h> /* struct ipfw_rule_ref */
68#include <netinet/ip_fw.h>
69#include <sys/queue.h> /* LIST_HEAD */
70#include <netinet/ipfw/ip_fw_private.h>
71
72#ifdef MAC
73#include <security/mac/mac_framework.h>
74#endif
75
76MALLOC_DEFINE(M_IPFW_TBL, "ipfw_tbl", "IpFw tables");
77
78struct table_entry {
79 struct radix_node rn[2];
80 struct sockaddr_in addr, mask;
81 u_int32_t value;
82};
83
84/*
85 * The radix code expects addr and mask to be array of bytes,
86 * with the first byte being the length of the array. rn_inithead
87 * is called with the offset in bits of the lookup key within the
88 * array. If we use a sockaddr_in as the underlying type,
89 * sin_len is conveniently located at offset 0, sin_addr is at
90 * offset 4 and normally aligned.
91 * But for portability, let's avoid assumption and make the code explicit
92 */
93#define KEY_LEN(v) *((uint8_t *)&(v))
94#define KEY_OFS (8*offsetof(struct sockaddr_in, sin_addr))
95
96int
97ipfw_add_table_entry(struct ip_fw_chain *ch, uint16_t tbl, in_addr_t addr,
98 uint8_t mlen, uint32_t value)
99{
100 struct radix_node_head *rnh;
101 struct table_entry *ent;
102 struct radix_node *rn;
103
104 if (tbl >= IPFW_TABLES_MAX)
105 return (EINVAL);
106 rnh = ch->tables[tbl];
107 ent = malloc(sizeof(*ent), M_IPFW_TBL, M_NOWAIT | M_ZERO);
108 if (ent == NULL)
109 return (ENOMEM);
110 ent->value = value;
111 KEY_LEN(ent->addr) = KEY_LEN(ent->mask) = 8;
112 ent->mask.sin_addr.s_addr = htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
113 ent->addr.sin_addr.s_addr = addr & ent->mask.sin_addr.s_addr;
114 IPFW_WLOCK(ch);
115 rn = rnh->rnh_addaddr(&ent->addr, &ent->mask, rnh, (void *)ent);
116 if (rn == NULL) {
117 IPFW_WUNLOCK(ch);
118 free(ent, M_IPFW_TBL);
119 return (EEXIST);
120 }
121 IPFW_WUNLOCK(ch);
122 return (0);
123}
124
125int
126ipfw_del_table_entry(struct ip_fw_chain *ch, uint16_t tbl, in_addr_t addr,
127 uint8_t mlen)
128{
129 struct radix_node_head *rnh;
130 struct table_entry *ent;
131 struct sockaddr_in sa, mask;
132
133 if (tbl >= IPFW_TABLES_MAX)
134 return (EINVAL);
135 rnh = ch->tables[tbl];
136 KEY_LEN(sa) = KEY_LEN(mask) = 8;
137 mask.sin_addr.s_addr = htonl(mlen ? ~((1 << (32 - mlen)) - 1) : 0);
138 sa.sin_addr.s_addr = addr & mask.sin_addr.s_addr;
139 IPFW_WLOCK(ch);
140 ent = (struct table_entry *)rnh->rnh_deladdr(&sa, &mask, rnh);
141 if (ent == NULL) {
142 IPFW_WUNLOCK(ch);
143 return (ESRCH);
144 }
145 IPFW_WUNLOCK(ch);
146 free(ent, M_IPFW_TBL);
147 return (0);
148}
149
150static int
151flush_table_entry(struct radix_node *rn, void *arg)
152{
153 struct radix_node_head * const rnh = arg;
154 struct table_entry *ent;
155
156 ent = (struct table_entry *)
157 rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, rnh);
158 if (ent != NULL)
159 free(ent, M_IPFW_TBL);
160 return (0);
161}
162
163int
164ipfw_flush_table(struct ip_fw_chain *ch, uint16_t tbl)
165{
166 struct radix_node_head *rnh;
167
168 IPFW_WLOCK_ASSERT(ch);
169
170 if (tbl >= IPFW_TABLES_MAX)
171 return (EINVAL);
172 rnh = ch->tables[tbl];
173 KASSERT(rnh != NULL, ("NULL IPFW table"));
174 rnh->rnh_walktree(rnh, flush_table_entry, rnh);
175 return (0);
176}
177
178void
179ipfw_destroy_tables(struct ip_fw_chain *ch)
180{
181 uint16_t tbl;
182 struct radix_node_head *rnh;
183
184 IPFW_WLOCK_ASSERT(ch);
185
186 for (tbl = 0; tbl < IPFW_TABLES_MAX; tbl++) {
187 ipfw_flush_table(ch, tbl);
188 rnh = ch->tables[tbl];
189 rn_detachhead((void **)&rnh);
190 }
191}
192
193int
194ipfw_init_tables(struct ip_fw_chain *ch)
195{
196 int i;
197 uint16_t j;
198
199 for (i = 0; i < IPFW_TABLES_MAX; i++) {
200 if (!rn_inithead((void **)&ch->tables[i], KEY_OFS)) {
201 for (j = 0; j < i; j++) {
202 (void) ipfw_flush_table(ch, j);
203 }
204 return (ENOMEM);
205 }
206 }
207 return (0);
208}
209
210int
211ipfw_lookup_table(struct ip_fw_chain *ch, uint16_t tbl, in_addr_t addr,
212 uint32_t *val)
213{
214 struct radix_node_head *rnh;
215 struct table_entry *ent;
216 struct sockaddr_in sa;
217
218 if (tbl >= IPFW_TABLES_MAX)
219 return (0);
220 rnh = ch->tables[tbl];
221 KEY_LEN(sa) = 8;
222 sa.sin_addr.s_addr = addr;
223 ent = (struct table_entry *)(rnh->rnh_lookup(&sa, NULL, rnh));
224 if (ent != NULL) {
225 *val = ent->value;
226 return (1);
227 }
228 return (0);
229}
230
231static int
232count_table_entry(struct radix_node *rn, void *arg)
233{
234 u_int32_t * const cnt = arg;
235
236 (*cnt)++;
237 return (0);
238}
239
240int
241ipfw_count_table(struct ip_fw_chain *ch, uint32_t tbl, uint32_t *cnt)
242{
243 struct radix_node_head *rnh;
244
245 if (tbl >= IPFW_TABLES_MAX)
246 return (EINVAL);
247 rnh = ch->tables[tbl];
248 *cnt = 0;
249 rnh->rnh_walktree(rnh, count_table_entry, cnt);
250 return (0);
251}
252
253static int
254dump_table_entry(struct radix_node *rn, void *arg)
255{
256 struct table_entry * const n = (struct table_entry *)rn;
257 ipfw_table * const tbl = arg;
258 ipfw_table_entry *ent;
259
260 if (tbl->cnt == tbl->size)
261 return (1);
262 ent = &tbl->ent[tbl->cnt];
263 ent->tbl = tbl->tbl;
264 if (in_nullhost(n->mask.sin_addr))
265 ent->masklen = 0;
266 else
267 ent->masklen = 33 - ffs(ntohl(n->mask.sin_addr.s_addr));
268 ent->addr = n->addr.sin_addr.s_addr;
269 ent->value = n->value;
270 tbl->cnt++;
271 return (0);
272}
273
274int
275ipfw_dump_table(struct ip_fw_chain *ch, ipfw_table *tbl)
276{
277 struct radix_node_head *rnh;
278
279 if (tbl->tbl >= IPFW_TABLES_MAX)
280 return (EINVAL);
281 rnh = ch->tables[tbl->tbl];
282 tbl->cnt = 0;
283 rnh->rnh_walktree(rnh, dump_table_entry, tbl);
284 return (0);
285}
286/* end of file */