diff -u --recursive --new-file linux/include/net/br.h linux-vlan-2.1.59/include/net/br.h
--- linux/include/net/br.h Thu Mar 27 23:40:11 1997
+++ linux-vlan-2.1.59/include/net/br.h Sat Jul 25 10:44:41 1998
@@ -19,6 +19,8 @@
#define Forwarding 3 /* (4 4 4) */
#define Blocking 4 /* (4.4.1) */
+#define DEFAULT_VLAN_ID 0x01
+
#define No_of_ports 8
/* arbitrary choice, to allow the code below to compile */
@@ -131,6 +133,7 @@
unsigned short designated_port; /* (4.5.5.7) */
unsigned int top_change_ack; /* (4.5.5.8) */
unsigned int config_pending; /* (4.5.5.9) */
+ unsigned int vlan_id;
struct device *dev;
struct fdb *fdb; /* head of per port fdb chain */
} Port_data;
@@ -151,6 +154,9 @@
unsigned int timer;
unsigned int flags;
#define FDB_ENT_VALID 0x01
+#define FDB_ENT_STATIC 0x11
+/* List of vlan's for each MAC address */
+ unsigned int vlan_id;
/* AVL tree of all addresses, sorted by address */
short fdb_avl_height;
struct fdb *fdb_avl_left;
@@ -159,6 +165,24 @@
struct fdb *fdb_next;
};
+/* Types for MAC-address - VLAN_ID table */
+struct swdb {
+ unsigned char ula[6];
+ unsigned char pad[2];
+ unsigned short port;
+ unsigned int timer;
+ unsigned int flags;
+#define FDB_ENT_VALID 0x01
+/* List of vlan's for each MAC address */
+ unsigned int vlan_id;
+/* AVL tree of all addresses, sorted by address */
+ short swdb_avl_height;
+ struct swdb *swdb_avl_left;
+ struct swdb *swdb_avl_right;
+/* linked list of addresses for each port */
+ struct swdb *swdb_next;
+};
+
#define IS_BRIDGED 0x2e
@@ -189,6 +213,7 @@
unsigned int cmd;
unsigned int arg1;
unsigned int arg2;
+ unsigned char ula[6];
};
/* defined cmds */
@@ -207,6 +232,8 @@
#define BRCMD_ENABLE_PROT_STATS 13
#define BRCMD_DISABLE_PROT_STATS 14
#define BRCMD_ZERO_PROT_STATS 15
+#define BRCMD_VLAN_CONFIG 16
+#define BRCMD_MAC_VLAN 17
/* prototypes of exported bridging functions... */
@@ -219,8 +246,9 @@
struct fdb *br_avl_find_addr(unsigned char addr[6]);
int br_avl_insert (struct fdb * new_node);
+struct swdb *sw_avl_find_addr(unsigned char addr[6]);
+int sw_avl_insert (struct swdb * new_node);
+
/* externs */
extern struct br_stat br_stats;
-
-
diff -u --recursive --new-file linux/include/net/netlink.h linux-vlan-2.1.59/include/net/netlink.h
--- linux/include/net/netlink.h Thu Sep 4 22:25:28 1997
+++ linux-vlan-2.1.59/include/net/netlink.h Wed Jun 17 14:05:58 1998
@@ -57,6 +57,7 @@
#define NETLINK_FIREWALL 3 /* Firewalling hook */
#define NETLINK_FREE 4 /* PSI devices - 4 to 7 (obsolete) */
#define NETLINK_ARPD 8 /* ARP daemon for big switched networks */
+#define NETLINK_BRD 9 /* Bridge daemon */
#define NETLINK_IPSEC 10 /* IPSEC (JI) */
#define NETLINK_ROUTE6 11 /* Af_inet6 route communication channel */
#define NETLINK_IP6_FW 13 /* IPv6 firewall trap outs */
diff -u --recursive --new-file linux/net/bridge/Makefile linux-vlan-2.1.59/net/bridge/Makefile
--- linux/net/bridge/Makefile Mon Apr 7 20:35:32 1997
+++ linux-vlan-2.1.59/net/bridge/Makefile Wed Jun 17 14:06:59 1998
@@ -8,7 +8,7 @@
# Note 2! The CFLAGS definition is now in the main makefile...
O_TARGET := bridge.o
-O_OBJS := br.o br_tree.o
+O_OBJS := br.o br_tree.o sw_tree.o
M_OBJS := $(O_TARGET)
ifeq ($(CONFIG_SYSCTL),y)
diff -u --recursive --new-file linux/net/bridge/br.c linux-vlan-2.1.59/net/bridge/br.c
--- linux/net/bridge/br.c Sun Sep 7 23:00:24 1997
+++ linux-vlan-2.1.59/net/bridge/br.c Thu Aug 13 13:12:37 1998
@@ -26,7 +26,7 @@
* Bridge SNMP stats.
*
*/
-
+
#include <linux/errno.h>
#include <linux/types.h>
#include <linux/socket.h>
@@ -46,6 +46,7 @@
#include <asm/uaccess.h>
#include <asm/system.h>
#include <net/br.h>
+#include <net/netlink.h>
static void transmit_config(int port_no);
static int root_bridge(void);
@@ -77,6 +78,8 @@
static void topology_change_timer_expiry(void);
static void hold_timer_expiry(int port_no);
static void br_init_port(int port_no);
+static void set_port_vlan_id(int port_no, unsigned int vlan_id);
+static int set_mac_vlan_id(unsigned int vlan_id, unsigned char *ula);
static void enable_port(int port_no);
static void disable_port(int port_no);
static void set_bridge_priority(bridge_id_t *new_bridge_id);
@@ -109,9 +112,13 @@
static int send_tcn_bpdu(int port_no, Tcn_bpdu *bpdu);
static int send_config_bpdu(int port_no, Config_bpdu *config_bpdu);
static int find_port(struct device *dev);
+static int check_vlan_id(struct fdb *s, struct fdb *f);
static int br_flood(struct sk_buff *skb, int port);
static int br_drop(struct sk_buff *skb);
static int br_learn(struct sk_buff *skb, int port); /* 3.8 */
+static int brd_send(unsigned short port, unsigned char *ula,
+ unsigned int timer, unsigned int flags, unsigned int vlan_id);
+static int brd_callback(int minor, struct sk_buff *skb);
static unsigned char bridge_ula[ETH_ALEN] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 };
static Bridge_data bridge_info; /* (4.5.3) */
@@ -128,6 +135,9 @@
/* entries timeout after this many seconds */
unsigned int fdb_aging_time = FDB_TIMEOUT;
+/* set if bridged wasn't started */
+static int brd_not_running;
+
struct br_stat br_stats;
static struct timer_list tl; /* for 1 second timer... */
@@ -729,6 +739,9 @@
port_state_selection(); /* (4.8.1.5) */
config_bpdu_generation(); /* (4.8.1.6) */
+ /* attach the netlink device */
+ netlink_attach(NETLINK_BRD, brd_callback);
+
/* initialize system timer */
tl.expires = jiffies+HZ; /* 1 second */
tl.function = br_tick;
@@ -747,11 +760,66 @@
set_port_state(port_no, Blocking); /* (4.8.1.4.2) */
port_info[port_no].top_change_ack = 0;
port_info[port_no].config_pending = FALSE;/* (4.8.1.4.4) */
+ /* port belongs to default vlan */
+ set_port_vlan_id(port_no, DEFAULT_VLAN_ID);
+/* port_info[port_no].vlan_id = DEFAULT_VLAN_ID; */
stop_message_age_timer(port_no); /* (4.8.1.4.5) */
stop_forward_delay_timer(port_no); /* (4.8.1.4.6) */
stop_hold_timer(port_no); /* (4.8.1.4.7) */
}
+static void set_port_vlan_id(int port_no, unsigned int vlan_id)
+{
+ port_info[port_no].vlan_id = vlan_id;
+}
+
+static int set_mac_vlan_id(unsigned int vlan_id, unsigned char *ula)
+{
+ struct swdb *s, *m = NULL;
+
+ s = (struct swdb *)kmalloc(sizeof(struct swdb), GFP_ATOMIC);
+ if (!s) {
+ printk(KERN_DEBUG "br_learn: unable to malloc swdb\n");
+ return(-1);
+ }
+
+ m = sw_avl_find_addr(ula);
+ if (m) {
+ s->port = m->port;
+ }
+ else { /* unknown MAC-address */
+ printk(KERN_DEBUG "set_mac_vlan_id: unknown mac address\n");
+ return(-2);
+ }
+
+ printk("port %i vlan 0x%08x\
+ mac %02x:%02x:%02x:%02x:%02x:%02x\n",
+ m->port,
+ vlan_id,
+ ula[0],
+ ula[1],
+ ula[2],
+ ula[3],
+ ula[4],
+ ula[5]);
+
+ memcpy(s->ula, ula, 6); /* specified mac address */
+ s->timer = CURRENT_TIME;
+ s->flags = FDB_ENT_VALID;
+
+ s->vlan_id = vlan_id; /* specified vlan_id */
+
+ if (sw_avl_insert(s) == 0) { /* update */
+ kfree(s);
+ return(0);
+ }
+ else { /* unknown MAC-address */
+ printk(KERN_DEBUG "set_mac_vlan_id: unknown mac address\n");
+ kfree(s);
+ return(-2);
+ }
+}
+
static void enable_port(int port_no) /* (4.8.2) */
{
br_init_port(port_no);
@@ -1317,6 +1385,11 @@
skb->mac.raw = skb->h.raw = skb->data;
eth = skb->mac.ethernet;
port = 0; /* an impossible port */
+
+ /* set vlan_id for the host stack, if it isn't set yet */
+ if ( !port_info[port].vlan_id )
+ set_port_vlan_id(port, DEFAULT_VLAN_ID);
+
if (br_stats.flags & BR_DEBUG)
printk("br_tx_fr : port %i src %02x:%02x:%02x:%02x:%02x:%02x\
dest %02x:%02x:%02x:%02x:%02x:%02x\n",
@@ -1344,7 +1417,9 @@
static int br_learn(struct sk_buff *skb, int port) /* 3.8 */
{
- struct fdb *f;
+ struct fdb *f,*n = NULL;
+ struct swdb *s,*m = NULL;
+ int status;
switch (port_info[port].state) {
case Listening:
@@ -1359,6 +1434,7 @@
if (skb->mac.ethernet->h_source[0] & 0x01)
return(-1);
+
f = (struct fdb *)kmalloc(sizeof(struct fdb),
GFP_ATOMIC);
@@ -1366,10 +1442,52 @@
printk(KERN_DEBUG "br_learn: unable to malloc fdb\n");
return(-1);
}
+
f->port = port; /* source port */
memcpy(f->ula, skb->mac.ethernet->h_source, 6);
f->timer = CURRENT_TIME;
f->flags = FDB_ENT_VALID;
+
+ n = br_avl_find_addr(skb->mac.ethernet->h_source);
+ if (n) {
+ f->vlan_id = n->vlan_id;
+ }
+ else { /* set default vlan_id */
+ f->vlan_id = DEFAULT_VLAN_ID;
+ }
+
+ s = (struct swdb *)kmalloc(sizeof(struct swdb),
+ GFP_ATOMIC);
+
+ if (!s) {
+ printk(KERN_DEBUG "br_learn: unable to malloc swdb\n");
+ return(-1);
+ }
+
+ s->port = port; /* source port */
+ memcpy(s->ula, skb->mac.ethernet->h_source, 6);
+ s->timer = CURRENT_TIME;
+ s->flags = FDB_ENT_VALID;
+
+ m = sw_avl_find_addr(skb->mac.ethernet->h_source);
+ if (m) {
+ s->vlan_id = m->vlan_id;
+ }
+ else { /* set default vlan_id */
+ s->vlan_id = DEFAULT_VLAN_ID;
+ }
+
+ /*
+ * add entity to SW_AVL tree. If entity already
+ * exists in the tree, update the fields with
+ * what we have here.
+ */
+ if (sw_avl_insert(s) == 0) { /* update */
+ kfree(s);
+ } /* new MAC-address */
+ else
+ printk(KERN_DEBUG "sw_avl_insert: new MAC\n");
+
/*
* add entity to AVL tree. If entity already
* exists in the tree, update the fields with
@@ -1379,6 +1497,21 @@
kfree(f);
return(0);
}
+
+ status = (brd_send(f->port,
+ f->ula,
+ f->timer,
+ f->flags,
+ f->vlan_id));
+
+ if (status != 0) {
+ printk(KERN_DEBUG "br_learn: unable to contact bridge daemon, status: %d\n",status);
+ }
+
+ /* add to head of port chain */
+ s->swdb_next = port_info[port].fdb;
+ port_info[port].fdb = s;
+
/* add to head of port chain */
f->fdb_next = port_info[port].fdb;
port_info[port].fdb = f;
@@ -1388,6 +1521,68 @@
}
/*
+ * netlink support
+ * post port and ula to netlink
+ */
+
+static int brd_callback(int minor, struct sk_buff *skb)
+{
+ struct fdb *retreq;
+
+ brd_not_running = 0;
+
+ if (skb->len != sizeof(struct fdb))
+ {
+ kfree_skb(skb, FREE_READ);
+ return -EINVAL;
+ }
+
+ retreq = (struct fdb *)skb->data;
+
+/* start_bh_atomic();
+ * brd_send(retreq->port, retreq->ula, rtereq->timer, retreq->flags, retreq->vlan_id);
+ */ end_bh_atomic();
+
+ kfree_skb(skb, FREE_READ);
+ return sizeof(struct fdb);
+}
+
+static int brd_send(unsigned short port, unsigned char *ula,
unsigned int timer, unsigned int flags, unsigned int vlan_id)
+{
+ int retval;
+ struct sk_buff *skb;
+ struct fdb *brreq;
+
+ skb = alloc_skb(sizeof(struct fdb), GFP_ATOMIC);
+ if (skb == NULL)
+ return(-2);
+
+ brreq=(struct fdb *)skb_put(skb, sizeof(struct fdb));
+ brreq->port = port;
+ brreq->timer = timer;
+ brreq->flags = flags;
+ brreq->vlan_id = vlan_id;
+
+ if (ula)
+ memcpy(brreq->ula, ula, sizeof(brreq->ula));
+
+ retval = netlink_post(NETLINK_BRD, skb);
+
+ if (retval)
+ {
+ kfree_skb(skb, FREE_WRITE);
+ if (retval == -EUNATCH)
+ brd_not_running = 1;
+ }
+ else brd_not_running = 0;
+
+ if (brd_not_running)
+ return(-1);
+
+ return (0);
+}
+
+/*
* this routine always consumes the frame
*/
@@ -1418,7 +1613,7 @@
static int br_forward(struct sk_buff *skb, int port) /* 3.7 */
{
- struct fdb *f;
+ struct fdb *f, *s;
/*
* flood all ports with frames destined for a group
@@ -1441,7 +1636,58 @@
return(0);
} else {
/* locate port to forward to */
- f = br_avl_find_addr(skb->mac.ethernet->h_dest);
+ f = sw_avl_find_addr(skb->mac.ethernet->h_dest);
+
+ if ((f) && (br_stats.flags & BR_DEBUG)) {
+ printk("sw_avl_find_addr(f): port %i vlan 0x%08x\
+ dest-mac %02x:%02x:%02x:%02x:%02x:%02x\n",
+ f->port,
+ f->vlan_id,
+ f->ula[0],
+ f->ula[1],
+ f->ula[2],
+ f->ula[3],
+ f->ula[4],
+ f->ula[5]);
+ }
+
+ /* locate source port */
+ s = sw_avl_find_addr(skb->mac.ethernet->h_source);
+
+ if (br_stats.flags & BR_DEBUG) {
+ if (s) {
+ printk("sw_avl_find_addr(s): port %i vlan 0x%08x\
+ source-mac %02x:%02x:%02x:%02x:%02x:%02x\n",
+ s->port,
+ s->vlan_id,
+ s->ula[0],
+ s->ula[1],
+ s->ula[2],
+ s->ula[3],
+ s->ula[4],
+ s->ula[5]);
+ }
+ else printk("sw_avl_find_addr(s): not found\n");
+ }
+
+ /*
+ * frame received from the host stack;
+ * no source MAC in avl tree ->
+ * bridge itself is in all VLAN's
+ */
+ if (!s && port==0) {
+ if (br_stats.flags & BR_DEBUG)
+ printk("frame received from the host stack\n");
+ s=f;
+ }
+
+ /* source MAC not found */
+ else if (!s) {
+ if (br_stats.flags & BR_DEBUG)
+ printk("source MAC not known\n");
+ return(br_dev_drop(skb));
+ }
+
/*
* Send flood and drop.
*/
@@ -1452,10 +1698,20 @@
}
/*
* Sending
+ * only if: source-port != destination-port
+ * port.state == Forwarding
+ * source.address.vlan_id == dest.address.vlan_id
+ * source.port.vlan_id == dest.port.vlan_id
*/
- if (f->port!=port && port_info[f->port].state == Forwarding) {
+ if (f->port!=port && port_info[f->port].state == Forwarding
+ &&
+ check_vlan_id(s, f)
+ &&
+ ((port_info[f->port].vlan_id & port_info[port].vlan_id) != 0) )
+ {
/* has entry expired? */
- if (f->timer + fdb_aging_time < CURRENT_TIME) {
+ if ( (f->timer + fdb_aging_time < CURRENT_TIME )
+ && (f->flags != FDB_ENT_STATIC) ) {
/* timer expired, invalidate entry */
f->flags &= ~FDB_ENT_VALID;
if (br_stats.flags & BR_DEBUG)
@@ -1482,6 +1738,8 @@
* We send this still locked
*/
skb->priority = 1;
+ if (br_stats.flags & BR_DEBUG)
+ printk("forward on known port\n");
dev_queue_xmit(skb);
return(1); /* skb has been consumed */
} else {
@@ -1493,6 +1751,44 @@
}
}
+
+/*
+ * This routine compares the vlan_id of the source and the destination
+ * MAC address. It returns true, if they belong to the same VLAN,
+ * false, if not.
+ */
+
+static int check_vlan_id(struct fdb *s, struct fdb *f)
+{
+ if (br_stats.flags & BR_DEBUG) {
+ printk("port %i vlan 0x%08x\
+ source-mac %02x:%02x:%02x:%02x:%02x:%02x\n",
+ s->port,
+ s->vlan_id,
+ s->ula[0],
+ s->ula[1],
+ s->ula[2],
+ s->ula[3],
+ s->ula[4],
+ s->ula[5]);
+
+ printk("port %i vlan 0x%08x\
+ dest-mac %02x:%02x:%02x:%02x:%02x:%02x\n",
+ f->port,
+ f->vlan_id,
+ f->ula[0],
+ f->ula[1],
+ f->ula[2],
+ f->ula[3],
+ f->ula[4],
+ f->ula[5]);
+ }
+ if ((s->vlan_id & f->vlan_id) == 0)
+ return(FALSE);
+ return (TRUE);
+}
+
+
/*
* this routine sends a copy of the frame to all forwarding ports
* with the exception of the port given. This routine never
@@ -1508,8 +1804,15 @@
{
if (i == port)
continue;
- if (port_info[i].state == Forwarding)
- {
+
+ /*
+ * forward only, if port state is forwarding
+ * and source.port.vlan_id == dest.port.vlan_id
+ */
+ if ((port_info[i].state == Forwarding)
+ &&
+ ((port_info[i].vlan_id & port_info[port].vlan_id) != 0))
+ {
nskb = skb_clone(skb, GFP_ATOMIC);
if(nskb==NULL)
continue;
@@ -1639,6 +1942,19 @@
printk(KERN_DEBUG "br: disabling port %i\n",bcf.arg1);
disable_port(bcf.arg1);
break;
+
+ /*
+ * configure vlan_id of specified port
+ */
+ case BRCMD_VLAN_CONFIG:
+ printk(KERN_DEBUG "br: configuring vlan_id %i for port %i\n",bcf.arg2,bcf.arg1);
+ set_port_vlan_id(bcf.arg1, bcf.arg2);
+ break;
+
+ case BRCMD_MAC_VLAN:
+ set_mac_vlan_id(bcf.arg1, &bcf.ula[0]);
+ break;
+
case BRCMD_SET_BRIDGE_PRIORITY:
set_bridge_priority((bridge_id_t *)&bcf.arg1);
break;
diff -u --recursive --new-file linux/net/bridge/br_tree.c linux-vlan-2.1.59/net/bridge/br_tree.c
--- linux/net/bridge/br_tree.c Thu Mar 27 23:40:14 1997
+++ linux-vlan-2.1.59/net/bridge/br_tree.c Wed Jun 17 14:08:02 1998
@@ -217,6 +217,7 @@
if (addr_cmp(new_node->ula, node->ula) == 0) { /* update */
node->flags = new_node->flags;
node->timer = new_node->timer;
+ node->vlan_id = new_node->vlan_id;
return(0);
}
if (addr_cmp(new_node->ula, node->ula) < 0) {
diff -u --recursive --new-file linux/net/bridge/sw_tree.c linux-vlan-2.1.59/net/bridge/sw_tree.c
--- linux/net/bridge/sw_tree.c
+++ linux-vlan-2.1.59/net/bridge/sw_tree.c Wed Jul 22 13:06:56 1998
@@ -0,0 +1,404 @@
+/*
+ * this code is derived from the avl functions in mmap.c
+ */
+#include <linux/kernel.h>
+#include <linux/errno.h>
+#include <linux/string.h>
+#include <linux/malloc.h>
+#include <linux/skbuff.h>
+
+#include <net/br.h>
+#define _SW_DEBUG_AVL
+
+/*
+ * Use an AVL (Adelson-Velskii and Landis) tree to speed up this search
+ * from O(n) to O(log n), where n is the number of ULAs.
+ * Written by Bruno Haible <haible@ma2s2.mathematik.uni-karlsruhe.de>.
+ * Taken from mmap.c, extensively modified by John Hayes
+ * <hayes@netplumbing.com>
+ */
+
+static struct swdb sw_fdb_head;
+static struct swdb *sw_fhp = &sw_fdb_head;
+static struct swdb **sw_fhpp = &sw_fhp;
+static int sw_fdb_inited = 0;
+
+static int sw_addr_cmp(unsigned char *a1, unsigned char *a2);
+
+/*
+ * sw_fdb_head is the AVL tree corresponding to swdb
+ * or, more exactly, its root.
+ * A swdb has the following fields:
+ * swdb_avl_left left son of a tree node
+ * swdb_avl_right right son of a tree node
+ * swdb_avl_height 1+max(heightof(left),heightof(right))
+ * The empty tree is represented as NULL.
+ */
+
+#ifndef avl_sw_empty
+#define avl_sw_empty (struct swdb *) NULL
+#endif
+
+/* Since the trees are balanced, their height will never be large. */
+#define sw_avl_maxheight 127
+#define heightof(tree) ((tree) == avl_sw_empty ? 0 : (tree)->swdb_avl_height)
+/*
+ * Consistency and balancing rules:
+ * 1. tree->swdb_avl_height == 1+max(heightof(tree->swdb_avl_left),heightof(tree->swdb_avl_right))
+ * 2. abs( heightof(tree->swdb_avl_left) - heightof(tree->swdb_avl_right) ) <= 1
+ * 3. foreach node in tree->swdb_avl_left: node->swdb_avl_key <= tree->swdb_avl_key,
+ * foreach node in tree->swdb_avl_right: node->swdb_avl_key >= tree->swdb_avl_key.
+ */
+
+static int
+sw_fdb_init(void)
+{
+ sw_fdb_head.swdb_avl_height = 0;
+ sw_fdb_head.swdb_avl_left = (struct swdb *)0;
+ sw_fdb_head.swdb_avl_right = (struct swdb *)0;
+ sw_fdb_inited = 1;
+ return(0);
+}
+
+struct swdb *sw_avl_find_addr(unsigned char addr[6])
+{
+ struct swdb * result = NULL;
+ struct swdb * tree;
+
+ if (!sw_fdb_inited)
+ sw_fdb_init();
+#if (SW_DEBUG_AVL)
+ printk("searching for ula %02x:%02x:%02x:%02x:%02x:%02x\n",
+ addr[0],
+ addr[1],
+ addr[2],
+ addr[3],
+ addr[4],
+ addr[5]);
+#endif /* SW_DEBUG_AVL */
+ for (tree = &sw_fdb_head ; ; ) {
+ if (tree == avl_sw_empty) {
+#if (SW_DEBUG_AVL)
+ printk("search failed, returning node 0x%x\n", (unsigned int)result);
+#endif /* SW_DEBUG_AVL */
+ return result;
+ }
+
+#if (SW_DEBUG_AVL)
+ printk("node 0x%x: checking ula %02x:%02x:%02x:%02x:%02x:%02x\n",
+ (unsigned int)tree,
+ tree->ula[0],
+ tree->ula[1],
+ tree->ula[2],
+ tree->ula[3],
+ tree->ula[4],
+ tree->ula[5]);
+#endif /* SW_DEBUG_AVL */
+ if (sw_addr_cmp(addr, tree->ula) == 0) {
+#if (SW_DEBUG_AVL)
+ printk("found node 0x%x\n", (unsigned int)tree);
+#endif /* SW_DEBUG_AVL */
+ return tree;
+ }
+ if (sw_addr_cmp(addr, tree->ula) < 0) {
+ tree = tree->swdb_avl_left;
+ } else {
+ tree = tree->swdb_avl_right;
+ }
+ }
+}
+
+
+#if (0)
+/*
+ * Rebalance a tree.
+ * After inserting or deleting a node of a tree we have a sequence of subtrees
+ * nodes[0]..nodes[k-1] such that
+ * nodes[0] is the root and nodes[i+1] = nodes[i]->{swdb_avl_left|swdb_avl_right}.
+ */
+static void sw_avl_rebalance (struct swdb *** nodeplaces_ptr, int count)
+{
+ if (!sw_fdb_inited)
+ sw_fdb_init();
+ for ( ; count > 0 ; count--) {
+ struct swdb ** nodeplace = *--nodeplaces_ptr;
+ struct swdb * node = *nodeplace;
+ struct swdb * nodeleft = node->swdb_avl_left;
+ struct swdb * noderight = node->swdb_avl_right;
+ int heightleft = heightof(nodeleft);
+ int heightright = heightof(noderight);
+ if (heightright + 1 < heightleft) {
+ /* */
+ /* * */
+ /* / \ */
+ /* n+2 n */
+ /* */
+ struct swdb * nodeleftleft = nodeleft->swdb_avl_left;
+ struct swdb * nodeleftright = nodeleft->swdb_avl_right;
+ int heightleftright = heightof(nodeleftright);
+ if (heightof(nodeleftleft) >= heightleftright) {
+ /* */
+ /* * n+2|n+3 */
+ /* / \ / \ */
+ /* n+2 n --> / n+1|n+2 */
+ /* / \ | / \ */
+ /* n+1 n|n+1 n+1 n|n+1 n */
+ /* */
+ node->swdb_avl_left = nodeleftright;
+ nodeleft->swdb_avl_right = node;
+ nodeleft->swdb_avl_height = 1 + (node->swdb_avl_height = 1 + heightleftright);
+ *nodeplace = nodeleft;
+ } else {
+ /* */
+ /* * n+2 */
+ /* / \ / \ */
+ /* n+2 n --> n+1 n+1 */
+ /* / \ / \ / \ */
+ /* n n+1 n L R n */
+ /* / \ */
+ /* L R */
+ /* */
+ nodeleft->swdb_avl_right = nodeleftright->swdb_avl_left;
+ node->swdb_avl_left = nodeleftright->swdb_avl_right;
+ nodeleftright->swdb_avl_left = nodeleft;
+ nodeleftright->swdb_avl_right = node;
+ nodeleft->swdb_avl_height = node->swdb_avl_height = heightleftright;
+ nodeleftright->swdb_avl_height = heightleft;
+ *nodeplace = nodeleftright;
+ }
+ } else if (heightleft + 1 < heightright) {
+ /* similar to the above, just interchange 'left' <--> 'right' */
+ struct swdb * noderightright = noderight->swdb_avl_right;
+ struct swdb * noderightleft = noderight->swdb_avl_left;
+ int heightrightleft = heightof(noderightleft);
+ if (heightof(noderightright) >= heightrightleft) {
+ node->swdb_avl_right = noderightleft;
+ noderight->swdb_avl_left = node;
+ noderight->swdb_avl_height = 1 + (node->swdb_avl_height = 1 + heightrightleft);
+ *nodeplace = noderight;
+ } else {
+ noderight->swdb_avl_left = noderightleft->swdb_avl_right;
+ node->swdb_avl_right = noderightleft->swdb_avl_left;
+ noderightleft->swdb_avl_right = noderight;
+ noderightleft->swdb_avl_left = node;
+ noderight->swdb_avl_height = node->swdb_avl_height = heightrightleft;
+ noderightleft->swdb_avl_height = heightright;
+ *nodeplace = noderightleft;
+ }
+ } else {
+ int height = (heightleft<heightright ? heightright : heightleft) + 1;
+ if (height == node->swdb_avl_height)
+ break;
+ node->swdb_avl_height = height;
+ }
+ }
+#ifdef SW_DEBUG_AVL
+ printk_sw_avl(&sw_fdb_head);
+#endif /* SW_DEBUG_AVL */
+}
+#endif /* (0) */
+
+/* Insert a node into a tree. */
+int sw_avl_insert (struct swdb * new_node)
+{
+ struct swdb ** nodeplace = sw_fhpp;
+ struct swdb ** stack[sw_avl_maxheight];
+ int stack_count = 0;
+ struct swdb *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
+ if (!sw_fdb_inited)
+ sw_fdb_init();
+ for (;;) {
+ struct swdb *node;
+
+ node = *nodeplace;
+ if (node == avl_sw_empty)
+ break;
+ *stack_ptr++ = nodeplace; stack_count++;
+ if (sw_addr_cmp(new_node->ula, node->ula) == 0) { /* update */
+ node->flags = new_node->flags;
+ node->timer = new_node->timer;
+ node->vlan_id = new_node->vlan_id;
+ return(0);
+ }
+ if (sw_addr_cmp(new_node->ula, node->ula) < 0) {
+ nodeplace = &node->swdb_avl_left;
+ } else {
+ nodeplace = &node->swdb_avl_right;
+ }
+ }
+#if (SW_DEBUG_AVL)
+ printk("node 0x%x: adding ula %02x:%02x:%02x:%02x:%02x:%02x\n",
+ (unsigned int)new_node,
+ new_node->ula[0],
+ new_node->ula[1],
+ new_node->ula[2],
+ new_node->ula[3],
+ new_node->ula[4],
+ new_node->ula[5]);
+#endif /* (SW_DEBUG_AVL) */
+ new_node->swdb_avl_left = avl_sw_empty;
+ new_node->swdb_avl_right = avl_sw_empty;
+ new_node->swdb_avl_height = 1;
+ *nodeplace = new_node;
+#if (0)
+ sw_avl_rebalance(stack_ptr,stack_count);
+#endif /* (0) */
+#ifdef SW_DEBUG_AVL
+ printk_sw_avl(&sw_fdb_head);
+#endif /* SW_DEBUG_AVL */
+ return(1);
+}
+
+
+#if (0)
+/* Removes a node out of a tree. */
+static int sw_avl_remove (struct swdb * node_to_delete)
+{
+ struct swdb ** nodeplace = sw_fhpp;
+ struct swdb ** stack[sw_avl_maxheight];
+ int stack_count = 0;
+ struct swdb *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
+ struct swdb ** nodeplace_to_delete;
+ if (!sw_fdb_inited)
+ sw_fdb_init();
+ for (;;) {
+ struct swdb * node = *nodeplace;
+ if (node == avl_sw_empty) {
+ /* what? node_to_delete not found in tree? */
+ printk(KERN_ERR "sw: avl_remove: node to delete not found in tree\n");
+ return(-1);
+ }
+ *stack_ptr++ = nodeplace; stack_count++;
+ if (sw_addr_cmp(node_to_delete->ula, node->ula) == 0)
+ break;
+ if (sw_addr_cmp(node_to_delete->ula, node->ula) < 0)
+ nodeplace = &node->swdb_avl_left;
+ else
+ nodeplace = &node->swdb_avl_right;
+ }
+ nodeplace_to_delete = nodeplace;
+ /* Have to remove node_to_delete = *nodeplace_to_delete. */
+ if (node_to_delete->swdb_avl_left == avl_sw_empty) {
+ *nodeplace_to_delete = node_to_delete->swdb_avl_right;
+ stack_ptr--; stack_count--;
+ } else {
+ struct swdb *** stack_ptr_to_delete = stack_ptr;
+ struct swdb ** nodeplace = &node_to_delete->swdb_avl_left;
+ struct swdb * node;
+ for (;;) {
+ node = *nodeplace;
+ if (node->swdb_avl_right == avl_sw_empty)
+ break;
+ *stack_ptr++ = nodeplace; stack_count++;
+ nodeplace = &node->swdb_avl_right;
+ }
+ *nodeplace = node->swdb_avl_left;
+ /* node replaces node_to_delete */
+ node->swdb_avl_left = node_to_delete->swdb_avl_left;
+ node->swdb_avl_right = node_to_delete->swdb_avl_right;
+ node->swdb_avl_height = node_to_delete->swdb_avl_height;
+ *nodeplace_to_delete = node; /* replace node_to_delete */
+ *stack_ptr_to_delete = &node->swdb_avl_left; /* replace &node_to_delete->swdb_avl_left */
+ }
+ sw_avl_rebalance(stack_ptr,stack_count);
+ return(0);
+}
+#endif /* (0) */
+
+#ifdef SW_DEBUG_AVL
+
+/* print a tree */
+static void printk_sw_avl (struct swdb * tree)
+{
+ if (tree != avl_sw_empty) {
+ printk("(");
+ printk("%02x:%02x:%02x:%02x:%02x:%02x",
+ tree->ula[0],
+ tree->ula[1],
+ tree->ula[2],
+ tree->ula[3],
+ tree->ula[4],
+ tree->ula[5]);
+ if (tree->swdb_avl_left != avl_sw_empty) {
+ printk_sw_avl(tree->swdb_avl_left);
+ printk("<");
+ }
+ if (tree->swdb_avl_right != avl_sw_empty) {
+ printk(">");
+ printk_sw_avl(tree->swdb_avl_right);
+ }
+ printk(")\n");
+ }
+}
+
+#if (0)
+static char *sw_avl_check_point = "somewhere";
+
+/* check a tree's consistency and balancing */
+static void sw_avl_checkheights (struct swdb * tree)
+{
+ int h, hl, hr;
+
+ if (tree == avl_sw_empty)
+ return;
+ sw_avl_checkheights(tree->swdb_avl_left);
+ sw_avl_checkheights(tree->swdb_avl_right);
+ h = tree->swdb_avl_height;
+ hl = heightof(tree->swdb_avl_left);
+ hr = heightof(tree->swdb_avl_right);
+ if ((h == hl+1) && (hr <= hl) && (hl <= hr+1))
+ return;
+ if ((h == hr+1) && (hl <= hr) && (hr <= hl+1))
+ return;
+ printk("%s: sw_avl_checkheights: heights inconsistent\n",sw_avl_check_point);
+}
+
+/* check that all values stored in a tree are < key */
+static void sw_avl_checkleft (struct swdb * tree, swdb_avl_key_t key)
+{
+ if (tree == avl_sw_empty)
+ return;
+ sw_avl_checkleft(tree->swdb_avl_left,key);
+ sw_avl_checkleft(tree->swdb_avl_right,key);
+ if (tree->swdb_avl_key < key)
+ return;
+ printk("%s: sw_avl_checkleft: left key %lu >= top key %lu\n",sw_avl_check_point,tree->swdb_avl_key,key);
+}
+
+/* check that all values stored in a tree are > key */
+static void sw_avl_checkright (struct swdb * tree, swdb_avl_key_t key)
+{
+ if (tree == avl_sw_empty)
+ return;
+ sw_avl_checkright(tree->swdb_avl_left,key);
+ sw_avl_checkright(tree->swdb_avl_right,key);
+ if (tree->swdb_avl_key > key)
+ return;
+ printk("%s: sw_avl_checkright: right key %lu <= top key %lu\n",sw_avl_check_point,tree->swdb_avl_key,key);
+}
+
+/* check that all values are properly increasing */
+static void sw_avl_checkorder (struct swdb * tree)
+{
+ if (tree == avl_sw_empty)
+ return;
+ sw_avl_checkorder(tree->swdb_avl_left);
+ sw_avl_checkorder(tree->swdb_avl_right);
+ sw_avl_checkleft(tree->swdb_avl_left,tree->swdb_avl_key);
+ sw_avl_checkright(tree->swdb_avl_right,tree->swdb_avl_key);
+}
+
+#endif /* (0) */
+#endif /* SW_DEBUG_AVL */
+
+static int sw_addr_cmp(unsigned char a1[], unsigned char a2[])
+{
+ int i;
+
+ for (i=0; i<6; i++) {
+ if (a1[i] > a2[i]) return(1);
+ if (a1[i] < a2[i]) return(-1);
+ }
+ return(0);
+}
+