diff options
| -rw-r--r-- | kernel/linux/include/linux/netfilter_bridge/ebt_among.h | 72 | ||||
| -rw-r--r-- | kernel/linux/net/bridge/netfilter/ebt_among.c | 123 | ||||
| -rw-r--r-- | kernel/linux2.5/include/linux/netfilter_bridge/ebt_among.h | 72 | ||||
| -rw-r--r-- | kernel/linux2.5/net/bridge/netfilter/ebt_among.c | 122 | ||||
| -rw-r--r-- | userspace/ebtables2/extensions/ebt_among.c | 233 |
5 files changed, 622 insertions, 0 deletions
diff --git a/kernel/linux/include/linux/netfilter_bridge/ebt_among.h b/kernel/linux/include/linux/netfilter_bridge/ebt_among.h new file mode 100644 index 0000000..f98f5fb --- /dev/null +++ b/kernel/linux/include/linux/netfilter_bridge/ebt_among.h @@ -0,0 +1,72 @@ +#ifndef __LINUX_BRIDGE_EBT_AMONG_H +#define __LINUX_BRIDGE_EBT_AMONG_H + +#define EBT_AMONG_DST 0x01 +#define EBT_AMONG_SRC 0x02 + +/* Write-once-read-many hash table, used for checking if a given + * MAC address belongs to a set or not. It remembers up to 256 + * addresses. + * + * The hash value of an address is its last byte. + * + * In real-world ethernet addresses, values of the last byte are + * evenly distributed and there is no need to consider other bytes. + * It would only slow the routines down. + * + * For MAC address comparison speedup reasons, we introduce a trick. + * MAC address is mapped onto an array of two 32-bit integers. + * This pair of integers is compared with MAC addresses in the + * hash table, which are stored also in form of pairs of integers + * (in `cmp' array). This is quick as it requires only two elementary + * number comparisons in worst case. Further, we take advantage of + * fact that entropy of 3 last bytes of address is larger than entropy + * of 3 first bytes. So first we compare 4 last bytes of addresses and + * if they are the same we compare 2 first. + * + * Yes, it is a memory overhead, but in 2003 AD, who cares? + * + * `next_ofs' contains a "serialized" pointer to the next tuple in + * the synonym list. It is a difference between address of the next + * tuple and address of the entire wormhash structure, in bytes + * or 0 if there is no next tuple. + * + * `table' contains begins of the synonym lists for + * + * This was introduced to make wormhash structure movable. As you may + * guess, once structure is passed to the kernel, the real pointers + * would become invalid. Also comparison would not work if they were + * built of absolute pointers. + * + * From the other side, using indices of the `pool' array would be + * slower. CPU would have to multiply index * size of tuple at each + * access to a tuple and add this to the address of the beginning + * of the `pool' array. + * + * Summary: + * + * The code is damn unreadable and unclear, but - and that's the + * point - effective. + */ + +struct ebt_mac_wormhash_tuple +{ + int next_ofs; + uint32_t cmp[2]; +}; + +struct ebt_mac_wormhash +{ + int table[256]; + struct ebt_mac_wormhash_tuple pool[256]; +}; + +struct ebt_among_info +{ + uint32_t bitmask; + struct ebt_mac_wormhash wh_dst; + struct ebt_mac_wormhash wh_src; +}; +#define EBT_AMONG_MATCH "among" + +#endif diff --git a/kernel/linux/net/bridge/netfilter/ebt_among.c b/kernel/linux/net/bridge/netfilter/ebt_among.c new file mode 100644 index 0000000..e69246a --- /dev/null +++ b/kernel/linux/net/bridge/netfilter/ebt_among.c @@ -0,0 +1,123 @@ +/* + * ebt_among + * + * Authors: + * Grzegorz Borowiak <grzes@gnu.univ.gda.pl> + * + * August, 2003 + * + */ + +#include <linux/netfilter_bridge/ebtables.h> +#include <linux/netfilter_bridge/ebt_among.h> +#include <linux/module.h> + +static int ebt_mac_wormhash_contains(const struct ebt_mac_wormhash *wh, const char *mac) +{ + /* You may be puzzled as to how this code works. + * Some tricks were used, refer to include/linux/netfilter_bridge/ebt_among.h + * as there you can find a solution of this mystery. + */ + const struct ebt_mac_wormhash_tuple *p; + int offset; + const char *base = (const char*)wh; + uint32_t cmp[2] = { 0, 0 }; + int key = (const unsigned char)mac[5]; + memcpy(((char*)cmp)+2, mac, 6); + offset = wh->table[key]; + while (offset) { + p = (const struct ebt_mac_wormhash_tuple*)(base + offset); + if (cmp[1] == p->cmp[1] && cmp[0] == p->cmp[0]) + return 1; + offset = p->next_ofs; + } + return 0; +} + +static int ebt_mac_wormhash_check_integrity(const struct ebt_mac_wormhash *wh) +{ + int i, count; + const struct ebt_mac_wormhash_tuple *p; + int offset; + const char *base = (const char*)wh; + + count = 0; + for (i=256; i--;) { + offset = wh->table[i]; + while (offset) { + p = (const struct ebt_mac_wormhash_tuple*)(base + offset); + if (p < wh->pool) + return -1; + if (p > wh->pool + 256 - 1) + return -2; + count++; + if (count > 1000) + return -3; + offset = p->next_ofs; + } + } + return 0; +} + +static int ebt_filter_among(const struct sk_buff *skb, + const struct net_device *in, const struct net_device *out, const void *data, + unsigned int datalen) +{ + struct ebt_among_info *info = (struct ebt_among_info *) data; + + const char *dmac, *smac; + if (info->bitmask & EBT_AMONG_SRC) { + smac = skb->mac.ethernet->h_source; + if (!ebt_mac_wormhash_contains(&info->wh_src, smac)) + return EBT_NOMATCH; + } + + if (info->bitmask & EBT_AMONG_DST) { + dmac = skb->mac.ethernet->h_dest; + if (!ebt_mac_wormhash_contains(&info->wh_dst, dmac)) + return EBT_NOMATCH; + } + + return EBT_MATCH; +} + +static int ebt_among_check(const char *tablename, unsigned int hookmask, + const struct ebt_entry *e, void *data, unsigned int datalen) +{ + struct ebt_among_info *info = (struct ebt_among_info *) data; + + if (datalen != EBT_ALIGN(sizeof(struct ebt_among_info))) { + printk(KERN_WARNING "ebtables: among: wrong size\n"); + return -EINVAL; + } + if ((info->bitmask & EBT_AMONG_DST) && ebt_mac_wormhash_check_integrity(&info->wh_dst)) { + printk(KERN_WARNING "ebtables: among: dst integrity fail\n"); + return -EINVAL; + } + if ((info->bitmask & EBT_AMONG_SRC) && ebt_mac_wormhash_check_integrity(&info->wh_src)) { + printk(KERN_WARNING "ebtables: among: src integrity fail\n"); + return -EINVAL; + } + return 0; +} + +static struct ebt_match filter_among = +{ + {NULL, NULL}, EBT_AMONG_MATCH, ebt_filter_among, ebt_among_check, NULL, + THIS_MODULE +}; + +static int __init init(void) +{ + return ebt_register_match(&filter_among); +} + +static void __exit fini(void) +{ + ebt_unregister_match(&filter_among); +} + +module_init(init); +module_exit(fini); +EXPORT_NO_SYMBOLS; +MODULE_LICENSE("GPL"); diff --git a/kernel/linux2.5/include/linux/netfilter_bridge/ebt_among.h b/kernel/linux2.5/include/linux/netfilter_bridge/ebt_among.h new file mode 100644 index 0000000..f98f5fb --- /dev/null +++ b/kernel/linux2.5/include/linux/netfilter_bridge/ebt_among.h @@ -0,0 +1,72 @@ +#ifndef __LINUX_BRIDGE_EBT_AMONG_H +#define __LINUX_BRIDGE_EBT_AMONG_H + +#define EBT_AMONG_DST 0x01 +#define EBT_AMONG_SRC 0x02 + +/* Write-once-read-many hash table, used for checking if a given + * MAC address belongs to a set or not. It remembers up to 256 + * addresses. + * + * The hash value of an address is its last byte. + * + * In real-world ethernet addresses, values of the last byte are + * evenly distributed and there is no need to consider other bytes. + * It would only slow the routines down. + * + * For MAC address comparison speedup reasons, we introduce a trick. + * MAC address is mapped onto an array of two 32-bit integers. + * This pair of integers is compared with MAC addresses in the + * hash table, which are stored also in form of pairs of integers + * (in `cmp' array). This is quick as it requires only two elementary + * number comparisons in worst case. Further, we take advantage of + * fact that entropy of 3 last bytes of address is larger than entropy + * of 3 first bytes. So first we compare 4 last bytes of addresses and + * if they are the same we compare 2 first. + * + * Yes, it is a memory overhead, but in 2003 AD, who cares? + * + * `next_ofs' contains a "serialized" pointer to the next tuple in + * the synonym list. It is a difference between address of the next + * tuple and address of the entire wormhash structure, in bytes + * or 0 if there is no next tuple. + * + * `table' contains begins of the synonym lists for + * + * This was introduced to make wormhash structure movable. As you may + * guess, once structure is passed to the kernel, the real pointers + * would become invalid. Also comparison would not work if they were + * built of absolute pointers. + * + * From the other side, using indices of the `pool' array would be + * slower. CPU would have to multiply index * size of tuple at each + * access to a tuple and add this to the address of the beginning + * of the `pool' array. + * + * Summary: + * + * The code is damn unreadable and unclear, but - and that's the + * point - effective. + */ + +struct ebt_mac_wormhash_tuple +{ + int next_ofs; + uint32_t cmp[2]; +}; + +struct ebt_mac_wormhash +{ + int table[256]; + struct ebt_mac_wormhash_tuple pool[256]; +}; + +struct ebt_among_info +{ + uint32_t bitmask; + struct ebt_mac_wormhash wh_dst; + struct ebt_mac_wormhash wh_src; +}; +#define EBT_AMONG_MATCH "among" + +#endif diff --git a/kernel/linux2.5/net/bridge/netfilter/ebt_among.c b/kernel/linux2.5/net/bridge/netfilter/ebt_among.c new file mode 100644 index 0000000..1ae9ad4 --- /dev/null +++ b/kernel/linux2.5/net/bridge/netfilter/ebt_among.c @@ -0,0 +1,122 @@ +/* + * ebt_among + * + * Authors: + * Grzegorz Borowiak <grzes@gnu.univ.gda.pl> + * + * August, 2003 + * + */ + +#include <linux/netfilter_bridge/ebtables.h> +#include <linux/netfilter_bridge/ebt_among.h> +#include <linux/module.h> + +static int ebt_mac_wormhash_contains(const struct ebt_mac_wormhash *wh, const char *mac) +{ + /* You may be puzzled as to how this code works. + * Some tricks were used, refer to include/linux/netfilter_bridge/ebt_among.h + * as there you can find a solution of this mystery. + */ + const struct ebt_mac_wormhash_tuple *p; + int offset; + const char *base = (const char*)wh; + uint32_t cmp[2] = { 0, 0 }; + int key = (const unsigned char)mac[5]; + memcpy(((char*)cmp)+2, mac, 6); + offset = wh->table[key]; + while (offset) { + p = (const struct ebt_mac_wormhash_tuple*)(base + offset); + if (cmp[1] == p->cmp[1] && cmp[0] == p->cmp[0]) + return 1; + offset = p->next_ofs; + } + return 0; +} + +static int ebt_mac_wormhash_check_integrity(const struct ebt_mac_wormhash *wh) +{ + int i, count; + const struct ebt_mac_wormhash_tuple *p; + int offset; + const char *base = (const char*)wh; + + count = 0; + for (i=256; i--;) { + offset = wh->table[i]; + while (offset) { + p = (const struct ebt_mac_wormhash_tuple*)(base + offset); + if (p < wh->pool) + return -1; + if (p > wh->pool + 256 - 1) + return -2; + count++; + if (count > 1000) + return -3; + offset = p->next_ofs; + } + } + return 0; +} + +static int ebt_filter_among(const struct sk_buff *skb, + const struct net_device *in, const struct net_device *out, const void *data, + unsigned int datalen) +{ + struct ebt_among_info *info = (struct ebt_among_info *) data; + + const char *dmac, *smac; + if (info->bitmask & EBT_AMONG_SRC) { + smac = skb->mac.ethernet->h_source; + if (!ebt_mac_wormhash_contains(&info->wh_src, smac)) + return EBT_NOMATCH; + } + + if (info->bitmask & EBT_AMONG_DST) { + dmac = skb->mac.ethernet->h_dest; + if (!ebt_mac_wormhash_contains(&info->wh_dst, dmac)) + return EBT_NOMATCH; + } + + return EBT_MATCH; +} + +static int ebt_among_check(const char *tablename, unsigned int hookmask, + const struct ebt_entry *e, void *data, unsigned int datalen) +{ + struct ebt_among_info *info = (struct ebt_among_info *) data; + + if (datalen != EBT_ALIGN(sizeof(struct ebt_among_info))) { + printk(KERN_WARNING "ebtables: among: wrong size\n"); + return -EINVAL; + } + if ((info->bitmask & EBT_AMONG_DST) && ebt_mac_wormhash_check_integrity(&info->wh_dst)) { + printk(KERN_WARNING "ebtables: among: dst integrity fail\n"); + return -EINVAL; + } + if ((info->bitmask & EBT_AMONG_SRC) && ebt_mac_wormhash_check_integrity(&info->wh_src)) { + printk(KERN_WARNING "ebtables: among: src integrity fail\n"); + return -EINVAL; + } + return 0; +} + +static struct ebt_match filter_among = +{ + {NULL, NULL}, EBT_AMONG_MATCH, ebt_filter_among, ebt_among_check, NULL, + THIS_MODULE +}; + +static int __init init(void) +{ + return ebt_register_match(&filter_among); +} + +static void __exit fini(void) +{ + ebt_unregister_match(&filter_among); +} + +module_init(init); +module_exit(fini); +MODULE_LICENSE("GPL"); diff --git a/userspace/ebtables2/extensions/ebt_among.c b/userspace/ebtables2/extensions/ebt_among.c new file mode 100644 index 0000000..5ec8a45 --- /dev/null +++ b/userspace/ebtables2/extensions/ebt_among.c @@ -0,0 +1,233 @@ +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <getopt.h> +#include <ctype.h> +#include <netinet/ether.h> +#include "../include/ebtables_u.h" +#include "../include/ethernetdb.h" +#include <linux/if_ether.h> +#include <linux/netfilter_bridge/ebt_among.h> + +/* +#define DEBUG +*/ + +#define AMONG_DST '1' +#define AMONG_SRC '2' + +static struct option opts[] = +{ + { "among-dst" , required_argument, 0, AMONG_DST }, + { "among-src" , required_argument, 0, AMONG_SRC }, + { 0 } +}; + +#ifdef DEBUG +static void hexdump(const void *mem, int howmany) +{ + printf("\n"); + const unsigned char *p = mem; + int i; + for (i = 0; i < howmany; i++) { + if (i % 32 == 0) { + printf("\n%04x: ", i); + } + printf("%2.2x ", p[i]); + } + printf("\n"); +} +#endif /* DEBUG */ + +static void print_help() +{ + printf( +"`among' options:\n" +"--among-dst list : matches if ether dst is in list\n" +"--among-src list : matches if ether src is in list\n" +"list has form:\n" +"\txx:xx:xx:xx:xx:xx,yy:yy:yy:yy:yy:yy,...,zz:zz:zz:zz:zz:zz\n" +"i.e. MAC addresses separated by commas, without spaces.\n" +"Optional comma can be included after the last MAC address, i.e.:\n" +"\txx:xx:xx:xx:xx:xx,yy:yy:yy:yy:yy:yy,...,zz:zz:zz:zz:zz:zz,\n" +"Each list can contain up to 256 addresses.\n" + ); +} + +static void init(struct ebt_entry_match *match) +{ + struct ebt_among_info *amonginfo = (struct ebt_among_info *)match->data; + + memset(amonginfo, 0, sizeof(struct ebt_among_info)); +} + +static int fill_mac(char *mac, const char *string) +{ + char xnum[3]; + const char *p = string; + int i = 0; + int j = 0; + while (1) { + if (isxdigit(*p)) { + xnum[j] = *p; + j++; + if (j >= 3) { + /* 3 or more hex digits for a single byte */ + return -3; + } + } + else { + xnum[j] = 0; + j = 0; + mac[i] = strtol(xnum, 0, 16); + i++; + if (i >= 6) { + if (*p == ':') { + /* MAC address too long */ + return -2; + } + else { + return 0; + } + } + else { + if (*p != ':') { + /* MAC address too short */ + return -1; + } + } + } + p++; + } + +} + +static void fill_wormhash(struct ebt_mac_wormhash *wh, const char *arg) +{ + const char *pc = arg; + const char *anchor; + char mac[6]; + int index; + int nmacs = 0; + char *base = (char*)wh; + memset(wh, 0, sizeof(struct ebt_mac_wormhash)); + while (1) { + anchor = pc; + while (*pc && *pc != ',') pc++; + while (*pc && *pc == ',') pc++; + if (fill_mac(mac, anchor)) { + print_error("problem with MAC %20s...", anchor); + } + index = (unsigned char)mac[5]; + memcpy(((char*)wh->pool[nmacs].cmp)+2, mac, 6); + wh->pool[nmacs].next_ofs = wh->table[index]; + wh->table[index] = ((const char*)&wh->pool[nmacs]) - base; + nmacs++; + if (*pc && nmacs >= 256) { + print_error("--among-src/--among-dst list can contain no more than 256 addresses\n"); + } + if (!*pc) { + break; + } + } +} + +#define OPT_DST 0x01 +#define OPT_SRC 0x02 +static int parse(int c, char **argv, int argc, const struct ebt_u_entry *entry, + unsigned int *flags, struct ebt_entry_match **match) +{ + struct ebt_among_info *amonginfo = (struct ebt_among_info *)(*match)->data; + struct ebt_mac_wormhash *wh; + + switch (c) { + case AMONG_DST: + case AMONG_SRC: + if (c == AMONG_DST) { + check_option(flags, OPT_DST); + wh = &amonginfo->wh_dst; + amonginfo->bitmask |= EBT_AMONG_DST; + } else { + check_option(flags, OPT_SRC); + wh = &amonginfo->wh_src; + amonginfo->bitmask |= EBT_AMONG_SRC; + } + if (optind > argc) + print_error("No MAC list specified\n"); + fill_wormhash(wh, argv[optind - 1]); + break; + default: + return 0; + } + return 1; +} + +static void final_check(const struct ebt_u_entry *entry, + const struct ebt_entry_match *match, const char *name, + unsigned int hookmask, unsigned int time) +{ +} + +static void wormhash_printout(const struct ebt_mac_wormhash *wh) +{ + int i; + int offset; + for (i = 0; i < 256; i++) { + const struct ebt_mac_wormhash_tuple *p; + offset = wh->table[i]; + while (offset) { + p = (const struct ebt_mac_wormhash_tuple*)((const char*)wh + offset); + printf("%s,", ether_ntoa((const struct ether_addr *)(((const char*)&p->cmp[0]) + 2))); + offset = p->next_ofs; + } + } + printf(" "); +} + +static void print(const struct ebt_u_entry *entry, + const struct ebt_entry_match *match) +{ + struct ebt_among_info *amonginfo = (struct ebt_among_info *)match->data; + + if (amonginfo->bitmask & EBT_AMONG_DST) { + printf("--among-dst "); + wormhash_printout(&amonginfo->wh_dst); + } + if (amonginfo->bitmask & EBT_AMONG_SRC) { + printf("--among-src "); + wormhash_printout(&amonginfo->wh_src); + } +} + +static int compare(const struct ebt_entry_match *m1, + const struct ebt_entry_match *m2) +{ + struct ebt_among_info *amonginfo1 = (struct ebt_among_info *)m1->data; + struct ebt_among_info *amonginfo2 = (struct ebt_among_info *)m2->data; + +#ifdef DEBUG +// hexdump(amonginfo1, sizeof(struct ebt_among_info)); +// hexdump(amonginfo2, sizeof(struct ebt_among_info)); +#endif /* DEBUG */ + + return memcmp(amonginfo1, amonginfo2, sizeof(struct ebt_among_info)) == 0; +} + +static struct ebt_u_match among_match = +{ + EBT_AMONG_MATCH, + sizeof(struct ebt_among_info), + print_help, + init, + parse, + final_check, + print, + compare, + opts +}; + +static void _init(void) __attribute__ ((constructor)); +static void _init(void) +{ + register_match(&among_match); +} |