From a4079b61a30520b34309248a294aa0dca27b9ec3 Mon Sep 17 00:00:00 2001 From: Bart De Schuymer Date: Tue, 2 Sep 2003 22:43:25 +0000 Subject: Grzegorz Borowiak --- .../include/linux/netfilter_bridge/ebt_among.h | 72 ++++++++++++ kernel/linux/net/bridge/netfilter/ebt_among.c | 123 +++++++++++++++++++++ 2 files changed, 195 insertions(+) create mode 100644 kernel/linux/include/linux/netfilter_bridge/ebt_among.h create mode 100644 kernel/linux/net/bridge/netfilter/ebt_among.c (limited to 'kernel/linux') 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 + * + * August, 2003 + * + */ + +#include +#include +#include + +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"); -- cgit v1.2.3