2 * Copyright (c) 2009 Luigi Rizzo Universita` di Pisa
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: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_fw_table.c 200601 2009-12-16 10:48:40Z luigi $");
30 * Rule and pipe lookup support for ipfw.
33 ipfw and dummynet need to quickly find objects (rules, pipes)
34 that may be dynamically created or destroyed.
35 To address the problem, we label each new object with a unique
36 32-bit identifier whose low K bits are the index in a lookup
37 table. All existing objects are referred by the lookup table,
38 and identifiers are chosen so that for each slot there is
39 at most one active object (whose identifier points to the slot).
40 This is almost a hash table, except that we can pick the
41 identifiers after looking at the table's occupation so
42 we have a trivial hash function and are collision free.
44 With this structure, operations are very fast and simple:
45 - the table has N entries s[i] with two fields, 'id' and 'ptr',
46 with N <= M = 2^k (M is an upper bound to the size of the table);
47 - initially, all slots have s[i].id = i, and the pointers
48 are used to build a freelist (tailq).
49 - a slot is considered empty if ptr == NULL or s[0] <= ptr < s[N].
50 This is easy to detect and we can use ptr to build the freelist.
51 - when a new object is created, we put it in the empty slot i at the
52 head of the freelist, and set the id to s[i].id;
53 - when an object is destroyed, we append its slot i to the end
54 of the freelist, and set s[i].id += M (note M, not N).
55 - on a lookup for id = X, we look at slot i = X & (M-1),
56 and consider the lookup successful only if the slot is not
57 empty and s[i].id == X;
58 - wraps occur at most every F * 2^32/M operations, where F is
59 the number of free slots. Because F is usually a reasonable
60 fraction of M, we should not worry too much.
61 - if the table fills up, we can extend it by increasing N
62 - shrinking the table is more difficult as we might create
63 collisions during the rehashing.
67 #include <sys/cdefs.h>
69 #include <sys/param.h>
70 #include <sys/systm.h>
71 #include <sys/malloc.h>
72 #include <sys/kernel.h>
74 #include <sys/rwlock.h>
75 MALLOC_DEFINE(M_IPFW_LUT, "ipfw_lookup", "IpFw lookup");
76 #define Malloc(n) malloc(n, M_IPFW_LUT, M_WAITOK)
77 #define Calloc(n) calloc(n, M_IPFW_LUT, M_WAITOK | M_ZERO)
78 #define Free(p) free(p, M_IPFW_LUT)
80 #define log(x, arg...)
83 #include <sys/types.h>
87 #define Malloc(n) malloc(n)
88 #define Calloc(n) calloc(1, n)
89 #define Free(p) free(p)
90 #define log(x, arg...) fprintf(stderr, "%s: " x "\n", __FUNCTION__, ##arg)
101 int mask; /* 2^k -1, used for hashing */
102 struct entry *f_head, *f_tail; /* freelist */
103 struct entry * s; /* slots, array of N entries */
106 static __inline int empty(struct lookup_table *head, const void *p)
108 const struct entry *ep = p;
109 return (ep == NULL ||
110 (ep >= head->s && ep < &head->s[head->_size]));
114 * init or reinit a table
116 struct lookup_table *
117 ipfw_lut_init(struct lookup_table *head, int new_size, int mask)
120 struct entry *s; /* the new slots */
121 struct entry *fh, *ft; /* the freelist */
125 if (new_size <= head->_size)
127 if (new_size >= mask+1) {
128 log("size larger than mask");
132 log("old is null, initialize");
133 head = Calloc(sizeof(*head));
136 if (new_size >= mask)
138 if (mask & (mask -1)) {
139 for (i = 1; i < mask; i += i)
141 log("mask %d not 2^k, round up to %d", mask, i);
144 mask = head->mask = mask - 1;
147 s = Calloc(new_size * sizeof(*s));
155 /* remap the entries, adjust the freelist */
156 for (i = 0; i < new_size; i++) {
157 s[i].id = (i >= head->_size) ? i : head->s[i].id;
158 if (i < head->_size && !empty(head, head->s[i].ptr)) {
159 s[i].ptr = head->s[i].ptr;
171 /* write lock on the structure, to protect the readers */
174 head->_size = new_size;
175 /* release write lock */
182 /* insert returns the id */
184 ipfw_lut_insert(struct lookup_table *head, void *d)
191 head->f_head = e->ptr;
197 /* delete, returns the original entry */
199 ipfw_lut_delete(struct lookup_table *head, int id)
201 int i = id & head->mask;
205 if (i >= head->_size)
211 /* write lock to invalidate the entry to readers */
212 e->id += head->mask + 1; /* prepare for next insert */
214 /* release write lock */
215 if (head->f_head == NULL)
218 head->f_tail->ptr = e;
225 ipfw_lut_lookup(struct lookup_table *head, int id)
227 int i = id & head->mask;
230 if (i >= head->_size)
233 return (e->id == id) ? e->ptr : NULL;
237 ipfw_lut_dump(struct lookup_table *head)
241 log("head %p size %d used %d freelist %d",
242 head, head->_size, head->used, head->f_head ?
243 head->f_head - head->s : -1);
244 for (i = 0; i < head->_size; i++) {
245 struct entry *e = &head->s[i];
246 char ee = empty(head, e->ptr) ? 'E' : ' ';
247 log("%5d %5d %c %p", i, e->id, ee,
248 ee == 'E' && e->ptr != NULL ?
249 (void *)((struct entry *)e->ptr - head->s) : e->ptr);
254 void dump_p(struct lookup_table *p, int *map)
257 for (i = 0; i < p->_size; i++) {
258 int id = (int)ipfw_lut_lookup(p, map[i]);
259 log("%3d: %3d: %c", map[i] % 64, i, id);
262 int main(int argc, char *argv[])
267 struct lookup_table *p;
268 struct lookup_table *p1;
269 const char *m = "nel mezzo del cammin di nostra vita mi ritrovai"
270 " in una selva oscura e la diritta via era smarrita!";
272 fprintf(stderr, "testing lookup\n");
276 p = ipfw_lut_init(NULL, 120, 33);
279 for (i = 0; i < l; i++) {
281 int id = ipfw_lut_insert(p, (void *)x);
284 for (j=0; j < 10; j++) {
285 id = ipfw_lut_insert(p, (void *)'a');
287 ipfw_lut_delete(p, id);
293 p1 = ipfw_lut_init(p, 23, 0);
297 p1 = ipfw_lut_init(p1, 120, 0);