1 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set.h linux-2.6/include/linux/netfilter_ipv4/ip_set.h
2 --- linux-2.6./include/linux/netfilter_ipv4/ip_set.h 1970-01-01 01:00:00.000000000 +0100
3 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set.h 2005-10-13 10:53:58.000000000 +0200
8 +/* Copyright (C) 2000-2002 Joakim Axelsson <gozem@linux.nu>
9 + * Patrick Schaaf <bof@bof.de>
10 + * Martin Josefsson <gandalf@wlug.westbo.se>
11 + * Copyright (C) 2003-2004 Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>
13 + * This program is free software; you can redistribute it and/or modify
14 + * it under the terms of the GNU General Public License version 2 as
15 + * published by the Free Software Foundation.
23 + * A sockopt of such quality has hardly ever been seen before on the open
24 + * market! This little beauty, hardly ever used: above 64, so it's
25 + * traditionally used for firewalling, not touched (even once!) by the
26 + * 2.0, 2.2 and 2.4 kernels!
28 + * Comes with its own certificate of authenticity, valid anywhere in the
36 + * Heavily modify by Joakim Axelsson 08.03.2002
37 + * - Made it more modulebased
39 + * Additional heavy modifications by Jozsef Kadlecsik 22.02.2004
41 + * - in order to "deal with" backward compatibility, renamed to ipset
45 + * Used so that the kernel module and ipset-binary can match their versions
47 +#define IP_SET_PROTOCOL_VERSION 2
49 +#define IP_SET_MAXNAMELEN 32 /* set names and set typenames */
51 +/* Lets work with our own typedef for representing an IP address.
52 + * We hope to make the code more portable, possibly to IPv6...
54 + * The representation works in HOST byte order, because most set types
55 + * will perform arithmetic operations and compare operations.
57 + * For now the type is an uint32_t.
59 + * Make sure to ONLY use the functions when translating and parsing
60 + * in order to keep the host byte order and make it more portable:
65 + * (Joakim: where are they???)
68 +typedef uint32_t ip_set_ip_t;
70 +/* Sets are identified by an id in kernel space. Tweak with ip_set_id_t
71 + * and IP_SET_INVALID_ID if you want to increase the max number of sets.
73 +typedef uint16_t ip_set_id_t;
75 +#define IP_SET_INVALID_ID 65535
77 +/* How deep we follow bindings */
78 +#define IP_SET_MAX_BINDINGS 6
81 + * Option flags for kernel operations (ipt_set_info)
83 +#define IPSET_SRC 0x01 /* Source match/add */
84 +#define IPSET_DST 0x02 /* Destination match/add */
85 +#define IPSET_MATCH_INV 0x04 /* Inverse matching */
90 +#define IPSET_TYPE_IP 0x01 /* IP address type of set */
91 +#define IPSET_TYPE_PORT 0x02 /* Port type of set */
92 +#define IPSET_DATA_SINGLE 0x04 /* Single data storage */
93 +#define IPSET_DATA_DOUBLE 0x08 /* Double data storage */
95 +/* Reserved keywords */
96 +#define IPSET_TOKEN_DEFAULT ":default:"
97 +#define IPSET_TOKEN_ALL ":all:"
99 +/* SO_IP_SET operation constants, and their request struct types.
102 + * 0-99: commands with version checking
103 + * 100-199: add/del/test/bind/unbind
104 + * 200-299: list, save, restore
107 +/* Single shot operations:
108 + * version, create, destroy, flush, rename and swap
110 + * Sets are identified by name.
113 +#define IP_SET_REQ_STD \
115 + unsigned version; \
116 + char name[IP_SET_MAXNAMELEN]
118 +#define IP_SET_OP_CREATE 0x00000001 /* Create a new (empty) set */
119 +struct ip_set_req_create {
121 + char typename[IP_SET_MAXNAMELEN];
124 +#define IP_SET_OP_DESTROY 0x00000002 /* Remove a (empty) set */
125 +struct ip_set_req_std {
129 +#define IP_SET_OP_FLUSH 0x00000003 /* Remove all IPs in a set */
130 +/* Uses ip_set_req_std */
132 +#define IP_SET_OP_RENAME 0x00000004 /* Rename a set */
133 +/* Uses ip_set_req_create */
135 +#define IP_SET_OP_SWAP 0x00000005 /* Swap two sets */
136 +/* Uses ip_set_req_create */
138 +union ip_set_name_index {
139 + char name[IP_SET_MAXNAMELEN];
143 +#define IP_SET_OP_GET_BYNAME 0x00000006 /* Get set index by name */
144 +struct ip_set_req_get_set {
147 + union ip_set_name_index set;
150 +#define IP_SET_OP_GET_BYINDEX 0x00000007 /* Get set name by index */
151 +/* Uses ip_set_req_get_set */
153 +#define IP_SET_OP_VERSION 0x00000100 /* Ask kernel version */
154 +struct ip_set_req_version {
159 +/* Double shots operations:
160 + * add, del, test, bind and unbind.
162 + * First we query the kernel to get the index and type of the target set,
163 + * then issue the command. Validity of IP is checked in kernel in order
164 + * to minimalize sockopt operations.
167 +/* Get minimal set data for add/del/test/bind/unbind IP */
168 +#define IP_SET_OP_ADT_GET 0x00000010 /* Get set and type */
169 +struct ip_set_req_adt_get {
172 + union ip_set_name_index set;
173 + char typename[IP_SET_MAXNAMELEN];
176 +#define IP_SET_REQ_BYINDEX \
180 +struct ip_set_req_adt {
181 + IP_SET_REQ_BYINDEX;
184 +#define IP_SET_OP_ADD_IP 0x00000101 /* Add an IP to a set */
185 +/* Uses ip_set_req_adt, with type specific addage */
187 +#define IP_SET_OP_DEL_IP 0x00000102 /* Remove an IP from a set */
188 +/* Uses ip_set_req_adt, with type specific addage */
190 +#define IP_SET_OP_TEST_IP 0x00000103 /* Test an IP in a set */
191 +/* Uses ip_set_req_adt, with type specific addage */
193 +#define IP_SET_OP_BIND_SET 0x00000104 /* Bind an IP to a set */
194 +/* Uses ip_set_req_bind, with type specific addage */
195 +struct ip_set_req_bind {
196 + IP_SET_REQ_BYINDEX;
197 + char binding[IP_SET_MAXNAMELEN];
200 +#define IP_SET_OP_UNBIND_SET 0x00000105 /* Unbind an IP from a set */
201 +/* Uses ip_set_req_bind, with type speficic addage
202 + * index = 0 means unbinding for all sets */
204 +#define IP_SET_OP_TEST_BIND_SET 0x00000106 /* Test binding an IP to a set */
205 +/* Uses ip_set_req_bind, with type specific addage */
207 +/* Multiple shots operations: list, save, restore.
209 + * - check kernel version and query the max number of sets
210 + * - get the basic information on all sets
211 + * and size required for the next step
212 + * - get actual set data: header, data, bindings
215 +/* Get max_sets and the index of a queried set
217 +#define IP_SET_OP_MAX_SETS 0x00000020
218 +struct ip_set_req_max_sets {
221 + ip_set_id_t max_sets; /* max_sets */
222 + ip_set_id_t sets; /* real number of sets */
223 + union ip_set_name_index set; /* index of set if name used */
226 +/* Get the id and name of the sets plus size for next step */
227 +#define IP_SET_OP_LIST_SIZE 0x00000201
228 +#define IP_SET_OP_SAVE_SIZE 0x00000202
229 +struct ip_set_req_setnames {
231 + ip_set_id_t index; /* set to list/save */
232 + size_t size; /* size to get setdata/bindings */
233 + /* followed by sets number of struct ip_set_name_list */
236 +struct ip_set_name_list {
237 + char name[IP_SET_MAXNAMELEN];
238 + char typename[IP_SET_MAXNAMELEN];
243 +/* The actual list operation */
244 +#define IP_SET_OP_LIST 0x00000203
245 +struct ip_set_req_list {
246 + IP_SET_REQ_BYINDEX;
247 + /* sets number of struct ip_set_list in reply */
250 +struct ip_set_list {
252 + ip_set_id_t binding;
254 + size_t header_size; /* Set header data of header_size */
255 + size_t members_size; /* Set members data of members_size */
256 + size_t bindings_size; /* Set bindings data of bindings_size */
259 +struct ip_set_hash_list {
261 + ip_set_id_t binding;
264 +/* The save operation */
265 +#define IP_SET_OP_SAVE 0x00000204
266 +/* Uses ip_set_req_list, in the reply replaced by
267 + * sets number of struct ip_set_save plus a marker
268 + * ip_set_save followed by ip_set_hash_save structures.
270 +struct ip_set_save {
272 + ip_set_id_t binding;
273 + size_t header_size; /* Set header data of header_size */
274 + size_t members_size; /* Set members data of members_size */
277 +/* At restoring, ip == 0 means default binding for the given set: */
278 +struct ip_set_hash_save {
281 + ip_set_id_t binding;
284 +/* The restore operation */
285 +#define IP_SET_OP_RESTORE 0x00000205
286 +/* Uses ip_set_req_setnames followed by ip_set_restore structures
287 + * plus a marker ip_set_restore, followed by ip_set_hash_save
290 +struct ip_set_restore {
291 + char name[IP_SET_MAXNAMELEN];
292 + char typename[IP_SET_MAXNAMELEN];
294 + size_t header_size; /* Create data of header_size */
295 + size_t members_size; /* Set members data of members_size */
298 +static inline int bitmap_bytes(ip_set_ip_t a, ip_set_ip_t b)
300 + return 4 * ((((b - a + 8) / 8) + 3) / 4);
305 +#define ip_set_printk(format, args...) \
307 + printk("%s: %s: ", __FILE__, __FUNCTION__); \
308 + printk(format "\n" , ## args); \
311 +#if defined(IP_SET_DEBUG)
312 +#define DP(format, args...) \
314 + printk("%s: %s (DBG): ", __FILE__, __FUNCTION__);\
315 + printk(format "\n" , ## args); \
317 +#define IP_SET_ASSERT(x) \
320 + printk("IP_SET_ASSERT: %s:%i(%s)\n", \
321 + __FILE__, __LINE__, __FUNCTION__); \
324 +#define DP(format, args...)
325 +#define IP_SET_ASSERT(x)
331 + * The ip_set_type definition - one per set type, e.g. "ipmap".
333 + * Each individual set has a pointer, set->type, going to one
334 + * of these structures. Function pointers inside the structure implement
335 + * the real behaviour of the sets.
337 + * If not mentioned differently, the implementation behind the function
338 + * pointers of a set_type, is expected to return 0 if ok, and a negative
339 + * errno (e.g. -EINVAL) on error.
341 +struct ip_set_type {
342 + struct list_head list; /* next in list of set types */
344 + /* test for IP in set (kernel: iptables -m set src|dst)
345 + * return 0 if not in set, 1 if in set.
347 + int (*testip_kernel) (struct ip_set *set,
348 + const struct sk_buff * skb,
350 + const u_int32_t *flags,
351 + unsigned char index);
353 + /* test for IP in set (userspace: ipset -T set IP)
354 + * return 0 if not in set, 1 if in set.
356 + int (*testip) (struct ip_set *set,
357 + const void *data, size_t size,
361 + * Size of the data structure passed by when
362 + * adding/deletin/testing an entry.
366 + /* Add IP into set (userspace: ipset -A set IP)
367 + * Return -EEXIST if the address is already in the set,
368 + * and -ERANGE if the address lies outside the set bounds.
369 + * If the address was not already in the set, 0 is returned.
371 + int (*addip) (struct ip_set *set,
372 + const void *data, size_t size,
375 + /* Add IP into set (kernel: iptables ... -j SET set src|dst)
376 + * Return -EEXIST if the address is already in the set,
377 + * and -ERANGE if the address lies outside the set bounds.
378 + * If the address was not already in the set, 0 is returned.
380 + int (*addip_kernel) (struct ip_set *set,
381 + const struct sk_buff * skb,
383 + const u_int32_t *flags,
384 + unsigned char index);
386 + /* remove IP from set (userspace: ipset -D set --entry x)
387 + * Return -EEXIST if the address is NOT in the set,
388 + * and -ERANGE if the address lies outside the set bounds.
389 + * If the address really was in the set, 0 is returned.
391 + int (*delip) (struct ip_set *set,
392 + const void *data, size_t size,
395 + /* remove IP from set (kernel: iptables ... -j SET --entry x)
396 + * Return -EEXIST if the address is NOT in the set,
397 + * and -ERANGE if the address lies outside the set bounds.
398 + * If the address really was in the set, 0 is returned.
400 + int (*delip_kernel) (struct ip_set *set,
401 + const struct sk_buff * skb,
403 + const u_int32_t *flags,
404 + unsigned char index);
406 + /* new set creation - allocated type specific items
408 + int (*create) (struct ip_set *set,
409 + const void *data, size_t size);
411 + /* retry the operation after successfully tweaking the set
413 + int (*retry) (struct ip_set *set);
415 + /* set destruction - free type specific items
416 + * There is no return value.
417 + * Can be called only when child sets are destroyed.
419 + void (*destroy) (struct ip_set *set);
421 + /* set flushing - reset all bits in the set, or something similar.
422 + * There is no return value.
424 + void (*flush) (struct ip_set *set);
426 + /* Listing: size needed for header
428 + size_t header_size;
430 + /* Listing: Get the header
432 + * Fill in the information in "data".
433 + * This function is always run after list_header_size() under a
434 + * writelock on the set. Therefor is the length of "data" always
437 + void (*list_header) (const struct ip_set *set,
440 + /* Listing: Get the size for the set members
442 + int (*list_members_size) (const struct ip_set *set);
444 + /* Listing: Get the set members
446 + * Fill in the information in "data".
447 + * This function is always run after list_member_size() under a
448 + * writelock on the set. Therefor is the length of "data" always
451 + void (*list_members) (const struct ip_set *set,
454 + char typename[IP_SET_MAXNAMELEN];
455 + unsigned char features;
456 + int protocol_version;
458 + /* Set this to THIS_MODULE if you are a module, otherwise NULL */
462 +extern int ip_set_register_set_type(struct ip_set_type *set_type);
463 +extern void ip_set_unregister_set_type(struct ip_set_type *set_type);
465 +/* A generic ipset */
467 + char name[IP_SET_MAXNAMELEN]; /* the name of the set */
468 + rwlock_t lock; /* lock for concurrency control */
469 + ip_set_id_t id; /* set id for swapping */
470 + ip_set_id_t binding; /* default binding for the set */
471 + atomic_t ref; /* in kernel and in hash references */
472 + struct ip_set_type *type; /* the set types */
473 + void *data; /* pooltype specific data */
476 +/* Structure to bind set elements to sets */
477 +struct ip_set_hash {
478 + struct list_head list; /* list of clashing entries in hash */
479 + ip_set_ip_t ip; /* ip from set */
480 + ip_set_id_t id; /* set id */
481 + ip_set_id_t binding; /* set we bind the element to */
484 +/* register and unregister set references */
485 +extern ip_set_id_t ip_set_get_byname(const char name[IP_SET_MAXNAMELEN]);
486 +extern ip_set_id_t ip_set_get_byindex(ip_set_id_t id);
487 +extern void ip_set_put(ip_set_id_t id);
489 +/* API for iptables set match, and SET target */
490 +extern void ip_set_addip_kernel(ip_set_id_t id,
491 + const struct sk_buff *skb,
492 + const u_int32_t *flags);
493 +extern void ip_set_delip_kernel(ip_set_id_t id,
494 + const struct sk_buff *skb,
495 + const u_int32_t *flags);
496 +extern int ip_set_testip_kernel(ip_set_id_t id,
497 + const struct sk_buff *skb,
498 + const u_int32_t *flags);
500 +#endif /* __KERNEL__ */
502 +#endif /*_IP_SET_H*/
503 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_iphash.h linux-2.6/include/linux/netfilter_ipv4/ip_set_iphash.h
504 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_iphash.h 1970-01-01 01:00:00.000000000 +0100
505 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_iphash.h 2006-05-08 11:52:48.000000000 +0200
507 +#ifndef __IP_SET_IPHASH_H
508 +#define __IP_SET_IPHASH_H
510 +#include <linux/netfilter_ipv4/ip_set.h>
512 +#define SETTYPE_NAME "iphash"
513 +#define MAX_RANGE 0x0000FFFF
515 +struct ip_set_iphash {
516 + ip_set_ip_t *members; /* the iphash proper */
517 + uint32_t elements; /* number of elements */
518 + uint32_t hashsize; /* hash size */
519 + uint16_t probes; /* max number of probes */
520 + uint16_t resize; /* resize factor in percent */
521 + ip_set_ip_t netmask; /* netmask */
522 + void *initval[0]; /* initvals for jhash_1word */
525 +struct ip_set_req_iphash_create {
529 + ip_set_ip_t netmask;
532 +struct ip_set_req_iphash {
536 +#endif /* __IP_SET_IPHASH_H */
537 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_ipmap.h linux-2.6/include/linux/netfilter_ipv4/ip_set_ipmap.h
538 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_ipmap.h 1970-01-01 01:00:00.000000000 +0100
539 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_ipmap.h 2005-09-30 18:44:08.000000000 +0200
541 +#ifndef __IP_SET_IPMAP_H
542 +#define __IP_SET_IPMAP_H
544 +#include <linux/netfilter_ipv4/ip_set.h>
546 +#define SETTYPE_NAME "ipmap"
547 +#define MAX_RANGE 0x0000FFFF
549 +struct ip_set_ipmap {
550 + void *members; /* the ipmap proper */
551 + ip_set_ip_t first_ip; /* host byte order, included in range */
552 + ip_set_ip_t last_ip; /* host byte order, included in range */
553 + ip_set_ip_t netmask; /* subnet netmask */
554 + ip_set_ip_t sizeid; /* size of set in IPs */
555 + ip_set_ip_t hosts; /* number of hosts in a subnet */
558 +struct ip_set_req_ipmap_create {
561 + ip_set_ip_t netmask;
564 +struct ip_set_req_ipmap {
569 +mask_to_bits(ip_set_ip_t mask)
571 + unsigned int bits = 32;
572 + ip_set_ip_t maskaddr;
574 + if (mask == 0xFFFFFFFF)
577 + maskaddr = 0xFFFFFFFE;
578 + while (--bits >= 0 && maskaddr != mask)
585 +range_to_mask(ip_set_ip_t from, ip_set_ip_t to, unsigned int *bits)
587 + ip_set_ip_t mask = 0xFFFFFFFE;
590 + while (--(*bits) >= 0 && mask && (to & mask) != from)
596 +#endif /* __IP_SET_IPMAP_H */
597 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_ipporthash.h linux-2.6/include/linux/netfilter_ipv4/ip_set_ipporthash.h
598 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_ipporthash.h 1970-01-01 01:00:00.000000000 +0100
599 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_ipporthash.h 2006-05-08 11:52:48.000000000 +0200
601 +#ifndef __IP_SET_IPPORTHASH_H
602 +#define __IP_SET_IPPORTHASH_H
604 +#include <linux/netfilter_ipv4/ip_set.h>
606 +#define SETTYPE_NAME "ipporthash"
607 +#define MAX_RANGE 0x0000FFFF
608 +#define INVALID_PORT (MAX_RANGE + 1)
610 +struct ip_set_ipporthash {
611 + ip_set_ip_t *members; /* the ipporthash proper */
612 + uint32_t elements; /* number of elements */
613 + uint32_t hashsize; /* hash size */
614 + uint16_t probes; /* max number of probes */
615 + uint16_t resize; /* resize factor in percent */
616 + ip_set_ip_t first_ip; /* host byte order, included in range */
617 + ip_set_ip_t last_ip; /* host byte order, included in range */
618 + void *initval[0]; /* initvals for jhash_1word */
621 +struct ip_set_req_ipporthash_create {
629 +struct ip_set_req_ipporthash {
634 +#endif /* __IP_SET_IPPORTHASH_H */
635 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_iptree.h linux-2.6/include/linux/netfilter_ipv4/ip_set_iptree.h
636 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_iptree.h 1970-01-01 01:00:00.000000000 +0100
637 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_iptree.h 2006-05-08 11:52:48.000000000 +0200
639 +#ifndef __IP_SET_IPTREE_H
640 +#define __IP_SET_IPTREE_H
642 +#include <linux/netfilter_ipv4/ip_set.h>
644 +#define SETTYPE_NAME "iptree"
645 +#define MAX_RANGE 0x0000FFFF
647 +struct ip_set_iptreed {
648 + unsigned long expires[256]; /* x.x.x.ADDR */
651 +struct ip_set_iptreec {
652 + struct ip_set_iptreed *tree[256]; /* x.x.ADDR.* */
655 +struct ip_set_iptreeb {
656 + struct ip_set_iptreec *tree[256]; /* x.ADDR.*.* */
659 +struct ip_set_iptree {
660 + unsigned int timeout;
661 + unsigned int gc_interval;
663 + uint32_t elements; /* number of elements */
664 + struct timer_list gc;
665 + struct ip_set_iptreeb *tree[256]; /* ADDR.*.*.* */
669 +struct ip_set_req_iptree_create {
670 + unsigned int timeout;
673 +struct ip_set_req_iptree {
675 + unsigned int timeout;
678 +#endif /* __IP_SET_IPTREE_H */
679 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_iptreemap.h linux-2.6/include/linux/netfilter_ipv4/ip_set_iptreemap.h
680 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_iptreemap.h 1970-01-01 01:00:00.000000000 +0100
681 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_iptreemap.h 2007-08-28 13:29:12.000000000 +0200
683 +#ifndef __IP_SET_IPTREEMAP_H
684 +#define __IP_SET_IPTREEMAP_H
686 +#include <linux/netfilter_ipv4/ip_set.h>
688 +#define SETTYPE_NAME "iptreemap"
691 +struct ip_set_iptreemap_d {
692 + unsigned char bitmap[32]; /* x.x.x.y */
695 +struct ip_set_iptreemap_c {
696 + struct ip_set_iptreemap_d *tree[256]; /* x.x.y.x */
699 +struct ip_set_iptreemap_b {
700 + struct ip_set_iptreemap_c *tree[256]; /* x.y.x.x */
701 + unsigned char dirty[32];
705 +struct ip_set_iptreemap {
706 + unsigned int gc_interval;
708 + struct timer_list gc;
709 + struct ip_set_iptreemap_b *tree[256]; /* y.x.x.x */
713 +struct ip_set_req_iptreemap_create {
714 + unsigned int gc_interval;
717 +struct ip_set_req_iptreemap {
722 +#endif /* __IP_SET_IPTREEMAP_H */
723 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_jhash.h linux-2.6/include/linux/netfilter_ipv4/ip_set_jhash.h
724 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_jhash.h 1970-01-01 01:00:00.000000000 +0100
725 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_jhash.h 2004-12-01 10:49:36.000000000 +0100
727 +#ifndef _LINUX_IPSET_JHASH_H
728 +#define _LINUX_IPSET_JHASH_H
730 +/* This is a copy of linux/jhash.h but the types u32/u8 are changed
731 + * to __u32/__u8 so that the header file can be included into
732 + * userspace code as well. Jozsef Kadlecsik (kadlec@blackhole.kfki.hu)
735 +/* jhash.h: Jenkins hash support.
737 + * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
739 + * http://burtleburtle.net/bob/hash/
741 + * These are the credits from Bob's sources:
743 + * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
744 + * hash(), hash2(), hash3, and mix() are externally useful functions.
745 + * Routines to test the hash are included if SELF_TEST is defined.
746 + * You can use this free for any purpose. It has no warranty.
748 + * Copyright (C) 2003 David S. Miller (davem@redhat.com)
750 + * I've modified Bob's hash to be useful in the Linux kernel, and
751 + * any bugs present are surely my fault. -DaveM
754 +/* NOTE: Arguments are modified. */
755 +#define __jhash_mix(a, b, c) \
757 + a -= b; a -= c; a ^= (c>>13); \
758 + b -= c; b -= a; b ^= (a<<8); \
759 + c -= a; c -= b; c ^= (b>>13); \
760 + a -= b; a -= c; a ^= (c>>12); \
761 + b -= c; b -= a; b ^= (a<<16); \
762 + c -= a; c -= b; c ^= (b>>5); \
763 + a -= b; a -= c; a ^= (c>>3); \
764 + b -= c; b -= a; b ^= (a<<10); \
765 + c -= a; c -= b; c ^= (b>>15); \
768 +/* The golden ration: an arbitrary value */
769 +#define JHASH_GOLDEN_RATIO 0x9e3779b9
771 +/* The most generic version, hashes an arbitrary sequence
772 + * of bytes. No alignment or length assumptions are made about
775 +static inline __u32 jhash(void *key, __u32 length, __u32 initval)
777 + __u32 a, b, c, len;
781 + a = b = JHASH_GOLDEN_RATIO;
784 + while (len >= 12) {
785 + a += (k[0] +((__u32)k[1]<<8) +((__u32)k[2]<<16) +((__u32)k[3]<<24));
786 + b += (k[4] +((__u32)k[5]<<8) +((__u32)k[6]<<16) +((__u32)k[7]<<24));
787 + c += (k[8] +((__u32)k[9]<<8) +((__u32)k[10]<<16)+((__u32)k[11]<<24));
789 + __jhash_mix(a,b,c);
797 + case 11: c += ((__u32)k[10]<<24);
798 + case 10: c += ((__u32)k[9]<<16);
799 + case 9 : c += ((__u32)k[8]<<8);
800 + case 8 : b += ((__u32)k[7]<<24);
801 + case 7 : b += ((__u32)k[6]<<16);
802 + case 6 : b += ((__u32)k[5]<<8);
803 + case 5 : b += k[4];
804 + case 4 : a += ((__u32)k[3]<<24);
805 + case 3 : a += ((__u32)k[2]<<16);
806 + case 2 : a += ((__u32)k[1]<<8);
807 + case 1 : a += k[0];
810 + __jhash_mix(a,b,c);
815 +/* A special optimized version that handles 1 or more of __u32s.
816 + * The length parameter here is the number of __u32s in the key.
818 +static inline __u32 jhash2(__u32 *k, __u32 length, __u32 initval)
820 + __u32 a, b, c, len;
822 + a = b = JHASH_GOLDEN_RATIO;
830 + __jhash_mix(a, b, c);
837 + case 2 : b += k[1];
838 + case 1 : a += k[0];
841 + __jhash_mix(a,b,c);
847 +/* A special ultra-optimized versions that knows they are hashing exactly
848 + * 3, 2 or 1 word(s).
850 + * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
851 + * done at the end is not done here.
853 +static inline __u32 jhash_3words(__u32 a, __u32 b, __u32 c, __u32 initval)
855 + a += JHASH_GOLDEN_RATIO;
856 + b += JHASH_GOLDEN_RATIO;
859 + __jhash_mix(a, b, c);
864 +static inline __u32 jhash_2words(__u32 a, __u32 b, __u32 initval)
866 + return jhash_3words(a, b, 0, initval);
869 +static inline __u32 jhash_1word(__u32 a, __u32 initval)
871 + return jhash_3words(a, 0, 0, initval);
874 +#endif /* _LINUX_IPSET_JHASH_H */
875 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_macipmap.h linux-2.6/include/linux/netfilter_ipv4/ip_set_macipmap.h
876 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_macipmap.h 1970-01-01 01:00:00.000000000 +0100
877 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_macipmap.h 2004-12-01 10:49:36.000000000 +0100
879 +#ifndef __IP_SET_MACIPMAP_H
880 +#define __IP_SET_MACIPMAP_H
882 +#include <linux/netfilter_ipv4/ip_set.h>
884 +#define SETTYPE_NAME "macipmap"
885 +#define MAX_RANGE 0x0000FFFF
888 +#define IPSET_MACIP_MATCHUNSET 1
891 +#define IPSET_MACIP_ISSET 1
893 +struct ip_set_macipmap {
894 + void *members; /* the macipmap proper */
895 + ip_set_ip_t first_ip; /* host byte order, included in range */
896 + ip_set_ip_t last_ip; /* host byte order, included in range */
900 +struct ip_set_req_macipmap_create {
906 +struct ip_set_req_macipmap {
908 + unsigned char ethernet[ETH_ALEN];
911 +struct ip_set_macip {
912 + unsigned short flags;
913 + unsigned char ethernet[ETH_ALEN];
916 +#endif /* __IP_SET_MACIPMAP_H */
917 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_malloc.h linux-2.6/include/linux/netfilter_ipv4/ip_set_malloc.h
918 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_malloc.h 1970-01-01 01:00:00.000000000 +0100
919 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_malloc.h 2005-10-13 10:53:58.000000000 +0200
921 +#ifndef _IP_SET_MALLOC_H
922 +#define _IP_SET_MALLOC_H
926 +/* Memory allocation and deallocation */
927 +static size_t max_malloc_size = 0;
929 +static inline void init_max_malloc_size(void)
931 +#define CACHE(x) max_malloc_size = x;
932 +#include <linux/kmalloc_sizes.h>
936 +static inline void * ip_set_malloc(size_t bytes)
938 + if (bytes > max_malloc_size)
939 + return vmalloc(bytes);
941 + return kmalloc(bytes, GFP_KERNEL);
944 +static inline void ip_set_free(void * data, size_t bytes)
946 + if (bytes > max_malloc_size)
953 + size_t max_elements;
957 +static inline void *
958 +harray_malloc(size_t hashsize, size_t typesize, int flags)
960 + struct harray *harray;
961 + size_t max_elements, size, i, j;
963 + if (!max_malloc_size)
964 + init_max_malloc_size();
966 + if (typesize > max_malloc_size)
969 + max_elements = max_malloc_size/typesize;
970 + size = hashsize/max_elements;
971 + if (hashsize % max_elements)
974 + /* Last pointer signals end of arrays */
975 + harray = kmalloc(sizeof(struct harray) + (size + 1) * sizeof(void *),
981 + for (i = 0; i < size - 1; i++) {
982 + harray->arrays[i] = kmalloc(max_elements * typesize, flags);
983 + if (!harray->arrays[i])
985 + memset(harray->arrays[i], 0, max_elements * typesize);
987 + harray->arrays[i] = kmalloc((hashsize - i * max_elements) * typesize,
989 + if (!harray->arrays[i])
991 + memset(harray->arrays[i], 0, (hashsize - i * max_elements) * typesize);
993 + harray->max_elements = max_elements;
994 + harray->arrays[size] = NULL;
996 + return (void *)harray;
999 + for (j = 0; j < i; j++) {
1000 + kfree(harray->arrays[j]);
1006 +static inline void harray_free(void *h)
1008 + struct harray *harray = (struct harray *) h;
1011 + for (i = 0; harray->arrays[i] != NULL; i++)
1012 + kfree(harray->arrays[i]);
1016 +static inline void harray_flush(void *h, size_t hashsize, size_t typesize)
1018 + struct harray *harray = (struct harray *) h;
1021 + for (i = 0; harray->arrays[i+1] != NULL; i++)
1022 + memset(harray->arrays[i], 0, harray->max_elements * typesize);
1023 + memset(harray->arrays[i], 0,
1024 + (hashsize - i * harray->max_elements) * typesize);
1027 +#define HARRAY_ELEM(h, type, which) \
1029 + struct harray *__h = (struct harray *)(h); \
1030 + ((type)((__h)->arrays[(which)/(__h)->max_elements]) \
1031 + + (which)%(__h)->max_elements); \
1034 +#endif /* __KERNEL__ */
1036 +#endif /*_IP_SET_MALLOC_H*/
1037 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_nethash.h linux-2.6/include/linux/netfilter_ipv4/ip_set_nethash.h
1038 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_nethash.h 1970-01-01 01:00:00.000000000 +0100
1039 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_nethash.h 2006-05-08 11:52:48.000000000 +0200
1041 +#ifndef __IP_SET_NETHASH_H
1042 +#define __IP_SET_NETHASH_H
1044 +#include <linux/netfilter_ipv4/ip_set.h>
1046 +#define SETTYPE_NAME "nethash"
1047 +#define MAX_RANGE 0x0000FFFF
1049 +struct ip_set_nethash {
1050 + ip_set_ip_t *members; /* the nethash proper */
1051 + uint32_t elements; /* number of elements */
1052 + uint32_t hashsize; /* hash size */
1053 + uint16_t probes; /* max number of probes */
1054 + uint16_t resize; /* resize factor in percent */
1055 + unsigned char cidr[30]; /* CIDR sizes */
1056 + void *initval[0]; /* initvals for jhash_1word */
1059 +struct ip_set_req_nethash_create {
1060 + uint32_t hashsize;
1065 +struct ip_set_req_nethash {
1067 + unsigned char cidr;
1070 +static unsigned char shifts[] = {255, 253, 249, 241, 225, 193, 129, 1};
1072 +static inline ip_set_ip_t
1073 +pack(ip_set_ip_t ip, unsigned char cidr)
1075 + ip_set_ip_t addr, *paddr = &addr;
1076 + unsigned char n, t, *a;
1078 + addr = htonl(ip & (0xFFFFFFFF << (32 - (cidr))));
1080 + DP("ip:%u.%u.%u.%u/%u", NIPQUAD(addr), cidr);
1084 + a = &((unsigned char *)paddr)[n];
1085 + *a = *a /(1 << (8 - t)) + shifts[t];
1087 + DP("n: %u, t: %u, a: %u", n, t, *a);
1088 + DP("ip:%u.%u.%u.%u/%u, %u.%u.%u.%u",
1089 + HIPQUAD(ip), cidr, NIPQUAD(addr));
1092 + return ntohl(addr);
1095 +#endif /* __IP_SET_NETHASH_H */
1096 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ip_set_portmap.h linux-2.6/include/linux/netfilter_ipv4/ip_set_portmap.h
1097 --- linux-2.6./include/linux/netfilter_ipv4/ip_set_portmap.h 1970-01-01 01:00:00.000000000 +0100
1098 +++ linux-2.6/include/linux/netfilter_ipv4/ip_set_portmap.h 2004-12-01 10:49:36.000000000 +0100
1100 +#ifndef __IP_SET_PORTMAP_H
1101 +#define __IP_SET_PORTMAP_H
1103 +#include <linux/netfilter_ipv4/ip_set.h>
1105 +#define SETTYPE_NAME "portmap"
1106 +#define MAX_RANGE 0x0000FFFF
1107 +#define INVALID_PORT (MAX_RANGE + 1)
1109 +struct ip_set_portmap {
1110 + void *members; /* the portmap proper */
1111 + ip_set_ip_t first_port; /* host byte order, included in range */
1112 + ip_set_ip_t last_port; /* host byte order, included in range */
1115 +struct ip_set_req_portmap_create {
1120 +struct ip_set_req_portmap {
1124 +#endif /* __IP_SET_PORTMAP_H */
1125 diff -uNrp linux-2.6./include/linux/netfilter_ipv4/ipt_set.h linux-2.6/include/linux/netfilter_ipv4/ipt_set.h
1126 --- linux-2.6./include/linux/netfilter_ipv4/ipt_set.h 1970-01-01 01:00:00.000000000 +0100
1127 +++ linux-2.6/include/linux/netfilter_ipv4/ipt_set.h 2004-12-06 10:32:59.000000000 +0100
1132 +#include <linux/netfilter_ipv4/ip_set.h>
1134 +struct ipt_set_info {
1135 + ip_set_id_t index;
1136 + u_int32_t flags[IP_SET_MAX_BINDINGS + 1];
1140 +struct ipt_set_info_match {
1141 + struct ipt_set_info match_set;
1144 +struct ipt_set_info_target {
1145 + struct ipt_set_info add_set;
1146 + struct ipt_set_info del_set;
1149 +#endif /*_IPT_SET_H*/
1150 --- linux-2.6.22/include/linux/netfilter_ipv4/Kbuild 2005-12-16 15:49:47.000000000 +0100
1151 +++ linux-2.6.22/include/linux/netfilter_ipv4/Kbuild 2007-10-16 00:35:55.027634250 +0200
1153 +header-y += ip_set.h
1154 +header-y += ip_set_iphash.h
1155 +header-y += ip_set_ipmap.h
1156 +header-y += ip_set_ipporthash.h
1157 +header-y += ip_set_iptree.h
1158 +header-y += ip_set_iptreemap.h
1159 +header-y += ip_set_jhash.h
1160 +header-y += ip_set_macipmap.h
1161 +header-y += ip_set_malloc.h
1162 +header-y += ip_set_nethash.h
1163 +header-y += ip_set_portmap.h