patch-2.3.47 linux/net/bridge/br_tree.c
Next file: linux/net/bridge/sysctl_net_bridge.c
Previous file: linux/net/bridge/br_stp_timer.c
Back to the patch index
Back to the overall index
- Lines: 502
- Date:
Wed Dec 31 16:00:00 1969
- Orig file:
v2.3.46/linux/net/bridge/br_tree.c
- Orig date:
Wed Dec 29 13:13:21 1999
diff -u --recursive --new-file v2.3.46/linux/net/bridge/br_tree.c linux/net/bridge/br_tree.c
@@ -1,501 +0,0 @@
-/*
- * 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 <linux/netdevice.h>
-
-#include <net/br.h>
-#define _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>
- * 98-02 Modified by Jean-Rene Peulve jr.peulve@aix.pacwan.net
- * update port number when topology change
- * return oldfdb when updating, for broadcast storm checking
- * call addr_cmp once per node
- */
-
-static struct fdb fdb_head;
-static struct fdb *fhp = &fdb_head;
-static struct fdb **fhpp = &fhp;
-static int fdb_inited = 0;
-
-#ifdef DEBUG_AVL
-static void printk_avl (struct fdb * tree);
-#endif
-
-static int addr_cmp(unsigned char *a1, unsigned char *a2);
-
-/*
- * fdb_head is the AVL tree corresponding to fdb
- * or, more exactly, its root.
- * A fdb has the following fields:
- * fdb_avl_left left son of a tree node
- * fdb_avl_right right son of a tree node
- * fdb_avl_height 1+max(heightof(left),heightof(right))
- * The empty tree is represented as NULL.
- */
-
-#ifndef avl_br_empty
-#define avl_br_empty (struct fdb *) NULL
-#endif
-
-/* Since the trees are balanced, their height will never be large. */
-#define avl_maxheight 127
-#define heightof(tree) ((tree) == avl_br_empty ? 0 : (tree)->fdb_avl_height)
-/*
- * Consistency and balancing rules:
- * 1. tree->fdb_avl_height == 1+max(heightof(tree->fdb_avl_left),heightof(tree->fdb_avl_right))
- * 2. abs( heightof(tree->fdb_avl_left) - heightof(tree->fdb_avl_right) ) <= 1
- * 3. foreach node in tree->fdb_avl_left: node->fdb_avl_key <= tree->fdb_avl_key,
- * foreach node in tree->fdb_avl_right: node->fdb_avl_key >= tree->fdb_avl_key.
- */
-
-static int fdb_init(void)
-{
- fdb_head.fdb_avl_height = 0;
- fdb_head.fdb_avl_left = (struct fdb *)0;
- fdb_head.fdb_avl_right = (struct fdb *)0;
- fdb_inited = 1;
- return(0);
-}
-
-struct fdb *br_avl_find_addr(unsigned char addr[6])
-{
- struct fdb * result = NULL;
- struct fdb * tree;
-
- if (!fdb_inited)
- fdb_init();
-#if (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 /* DEBUG_AVL */
- for (tree = fhp ; ; ) {
- if (tree == avl_br_empty) {
-#if (DEBUG_AVL)
- printk("search failed, returning node 0x%x\n", (unsigned int)result);
-#endif /* DEBUG_AVL */
- return result;
- }
-
-#if (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 /* DEBUG_AVL */
- if (addr_cmp(addr, tree->ula) == 0) {
-#if (DEBUG_AVL)
- printk("found node 0x%x\n", (unsigned int)tree);
-#endif /* DEBUG_AVL */
- return tree;
- }
- if (addr_cmp(addr, tree->ula) < 0) {
- tree = tree->fdb_avl_left;
- } else {
- tree = tree->fdb_avl_right;
- }
- }
-}
-
-
-/*
- * 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]->{fdb_avl_left|fdb_avl_right}.
- */
-static void br_avl_rebalance (struct fdb *** nodeplaces_ptr, int count)
-{
- if (!fdb_inited)
- fdb_init();
- for ( ; count > 0 ; count--) {
- struct fdb ** nodeplace = *--nodeplaces_ptr;
- struct fdb * node = *nodeplace;
- struct fdb * nodeleft = node->fdb_avl_left;
- struct fdb * noderight = node->fdb_avl_right;
- int heightleft = heightof(nodeleft);
- int heightright = heightof(noderight);
- if (heightright + 1 < heightleft) {
- /* */
- /* * */
- /* / \ */
- /* n+2 n */
- /* */
- struct fdb * nodeleftleft = nodeleft->fdb_avl_left;
- struct fdb * nodeleftright = nodeleft->fdb_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->fdb_avl_left = nodeleftright;
- nodeleft->fdb_avl_right = node;
- nodeleft->fdb_avl_height = 1 + (node->fdb_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->fdb_avl_right = nodeleftright->fdb_avl_left;
- node->fdb_avl_left = nodeleftright->fdb_avl_right;
- nodeleftright->fdb_avl_left = nodeleft;
- nodeleftright->fdb_avl_right = node;
- nodeleft->fdb_avl_height = node->fdb_avl_height = heightleftright;
- nodeleftright->fdb_avl_height = heightleft;
- *nodeplace = nodeleftright;
- }
- } else if (heightleft + 1 < heightright) {
- /* similar to the above, just interchange 'left' <--> 'right' */
- struct fdb * noderightright = noderight->fdb_avl_right;
- struct fdb * noderightleft = noderight->fdb_avl_left;
- int heightrightleft = heightof(noderightleft);
- if (heightof(noderightright) >= heightrightleft) {
- node->fdb_avl_right = noderightleft;
- noderight->fdb_avl_left = node;
- noderight->fdb_avl_height = 1 + (node->fdb_avl_height = 1 + heightrightleft);
- *nodeplace = noderight;
- } else {
- noderight->fdb_avl_left = noderightleft->fdb_avl_right;
- node->fdb_avl_right = noderightleft->fdb_avl_left;
- noderightleft->fdb_avl_right = noderight;
- noderightleft->fdb_avl_left = node;
- noderight->fdb_avl_height = node->fdb_avl_height = heightrightleft;
- noderightleft->fdb_avl_height = heightright;
- *nodeplace = noderightleft;
- }
- } else {
- int height = (heightleft<heightright ? heightright : heightleft) + 1;
- if (height == node->fdb_avl_height)
- break;
- node->fdb_avl_height = height;
- }
- }
-#ifdef DEBUG_AVL
- printk_avl(&fdb_head);
-#endif /* DEBUG_AVL */
-}
-
-/* Insert a node into a tree.
- * Performance improvement:
- * call addr_cmp() only once per node and use result in a switch.
- * Return old node address if we knew that MAC address already
- * Return NULL if we insert the new node
- */
-struct fdb *br_avl_insert (struct fdb * new_node)
-{
- struct fdb ** nodeplace = fhpp;
- struct fdb ** stack[avl_maxheight];
- int stack_count = 0;
- struct fdb *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
- if (!fdb_inited)
- fdb_init();
- for (;;) {
- struct fdb *node;
-
- node = *nodeplace;
- if (node == avl_br_empty)
- break;
- *stack_ptr++ = nodeplace; stack_count++;
- switch(addr_cmp(new_node->ula, node->ula)) {
- case 0: /* update */
- if (node->port == new_node->port) {
- node->flags = new_node->flags;
- node->timer = new_node->timer;
- } else if (!(node->flags & FDB_ENT_VALID) &&
- node->port) {
- /* update fdb but never for local interfaces */
-#if (DEBUG_AVL)
- printk("node 0x%x:port changed old=%d new=%d\n",
- (unsigned int)node, node->port,new_node->port);
-#endif
- /* JRP: update port as well if the topology change !
- * Don't do this while entry is still valid otherwise
- * a broadcast that we flooded and is reentered by another
- * port would mess up the good port number.
- * The fdb list per port needs to be updated as well.
- */
- requeue_fdb(node, new_node->port);
- node->flags = new_node->flags;
- node->timer = new_node->timer;
-#if (DEBUG_AVL)
- printk_avl(&fdb_head);
-#endif /* DEBUG_AVL */
- }
- return node; /* pass old fdb to caller */
-
- case 1: /* new_node->ula > node->ula */
- nodeplace = &node->fdb_avl_right;
- break;
- default: /* -1 => new_node->ula < node->ula */
- nodeplace = &node->fdb_avl_left;
- }
- }
-#if (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 /* (DEBUG_AVL) */
- new_node->fdb_avl_left = avl_br_empty;
- new_node->fdb_avl_right = avl_br_empty;
- new_node->fdb_avl_height = 1;
- *nodeplace = new_node;
- br_avl_rebalance(stack_ptr,stack_count);
-#ifdef DEBUG_AVL
- printk_avl(&fdb_head);
-#endif /* DEBUG_AVL */
- return NULL; /* this is a new node */
-}
-
-
-/* Removes a node out of a tree. */
-static int br_avl_remove (struct fdb * node_to_delete)
-{
- struct fdb ** nodeplace = fhpp;
- struct fdb ** stack[avl_maxheight];
- int stack_count = 0;
- struct fdb *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
- struct fdb ** nodeplace_to_delete;
- if (!fdb_inited)
- fdb_init();
- for (;;) {
- struct fdb * node = *nodeplace;
- if (node == avl_br_empty) {
- /* what? node_to_delete not found in tree? */
- printk(KERN_ERR "br: avl_remove: node to delete not found in tree\n");
- return(-1);
- }
- *stack_ptr++ = nodeplace; stack_count++;
- if (addr_cmp(node_to_delete->ula, node->ula) == 0)
- break;
- if (addr_cmp(node_to_delete->ula, node->ula) < 0)
- nodeplace = &node->fdb_avl_left;
- else
- nodeplace = &node->fdb_avl_right;
- }
- nodeplace_to_delete = nodeplace;
- /* Have to remove node_to_delete = *nodeplace_to_delete. */
- if (node_to_delete->fdb_avl_left == avl_br_empty) {
- *nodeplace_to_delete = node_to_delete->fdb_avl_right;
- stack_ptr--; stack_count--;
- } else {
- struct fdb *** stack_ptr_to_delete = stack_ptr;
- struct fdb ** nodeplace = &node_to_delete->fdb_avl_left;
- struct fdb * node;
- for (;;) {
- node = *nodeplace;
- if (node->fdb_avl_right == avl_br_empty)
- break;
- *stack_ptr++ = nodeplace; stack_count++;
- nodeplace = &node->fdb_avl_right;
- }
- *nodeplace = node->fdb_avl_left;
- /* node replaces node_to_delete */
- node->fdb_avl_left = node_to_delete->fdb_avl_left;
- node->fdb_avl_right = node_to_delete->fdb_avl_right;
- node->fdb_avl_height = node_to_delete->fdb_avl_height;
- *nodeplace_to_delete = node; /* replace node_to_delete */
- *stack_ptr_to_delete = &node->fdb_avl_left; /* replace &node_to_delete->fdb_avl_left */
- }
- br_avl_rebalance(stack_ptr,stack_count);
- return(0);
-}
-
-#ifdef DEBUG_AVL
-
-/* print a tree */
-static void printk_avl (struct fdb * tree)
-{
- if (tree != avl_br_empty) {
- printk("(");
- printk("%02x:%02x:%02x:%02x:%02x:%02x(%d)",
- tree->ula[0],
- tree->ula[1],
- tree->ula[2],
- tree->ula[3],
- tree->ula[4],
- tree->ula[5],
- tree->port);
- if (tree->fdb_avl_left != avl_br_empty) {
- printk_avl(tree->fdb_avl_left);
- printk("<");
- }
- if (tree->fdb_avl_right != avl_br_empty) {
- printk(">");
- printk_avl(tree->fdb_avl_right);
- }
- printk(")\n");
- }
-}
-
-static char *avl_check_point = "somewhere";
-
-/* check a tree's consistency and balancing */
-static void avl_checkheights (struct fdb * tree)
-{
- int h, hl, hr;
-
- if (tree == avl_br_empty)
- return;
- avl_checkheights(tree->fdb_avl_left);
- avl_checkheights(tree->fdb_avl_right);
- h = tree->fdb_avl_height;
- hl = heightof(tree->fdb_avl_left);
- hr = heightof(tree->fdb_avl_right);
- if ((h == hl+1) && (hr <= hl) && (hl <= hr+1))
- return;
- if ((h == hr+1) && (hl <= hr) && (hr <= hl+1))
- return;
- printk("%s: avl_checkheights: heights inconsistent\n",avl_check_point);
-}
-
-/* check that all values stored in a tree are < key */
-static void avl_checkleft (struct fdb * tree, fdb_avl_key_t key)
-{
- if (tree == avl_br_empty)
- return;
- avl_checkleft(tree->fdb_avl_left,key);
- avl_checkleft(tree->fdb_avl_right,key);
- if (tree->fdb_avl_key < key)
- return;
- printk("%s: avl_checkleft: left key %lu >= top key %lu\n",avl_check_point,tree->fdb_avl_key,key);
-}
-
-/* check that all values stored in a tree are > key */
-static void avl_checkright (struct fdb * tree, fdb_avl_key_t key)
-{
- if (tree == avl_br_empty)
- return;
- avl_checkright(tree->fdb_avl_left,key);
- avl_checkright(tree->fdb_avl_right,key);
- if (tree->fdb_avl_key > key)
- return;
- printk("%s: avl_checkright: right key %lu <= top key %lu\n",avl_check_point,tree->fdb_avl_key,key);
-}
-
-/* check that all values are properly increasing */
-static void avl_checkorder (struct fdb * tree)
-{
- if (tree == avl_br_empty)
- return;
- avl_checkorder(tree->fdb_avl_left);
- avl_checkorder(tree->fdb_avl_right);
- avl_checkleft(tree->fdb_avl_left,tree->fdb_avl_key);
- avl_checkright(tree->fdb_avl_right,tree->fdb_avl_key);
-}
-
-#endif /* DEBUG_AVL */
-
-static int 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);
-}
-
-/* Vova Oksman: function for copy tree to the buffer */
-void sprintf_avl (char **pbuffer, struct fdb * tree, off_t *pos,
- int* len, off_t offset, int length)
-{
- int size;
-
- if( 0 == *pos){
- if(avl_br_empty == tree)
- /* begin from the root */
- tree = fhp;
- *pos = *len;
- }
-
- if (*pos >= offset+length)
- return;
-
- if (tree != avl_br_empty) {
- /* don't write the local device */
- if(tree->port != 0){
- size = sprintf(*pbuffer,
- "%02x:%02x:%02x:%02x:%02x:%02x %s %d %ld\n",
- tree->ula[0],tree->ula[1],tree->ula[2],
- tree->ula[3],tree->ula[4],tree->ula[5],
- port_info[tree->port].dev->name, tree->flags,CURRENT_TIME-tree->timer);
-
- (*pos)+=size;
- (*len)+=size;
- (*pbuffer)+=size;
- }
- if (*pos <= offset)
- *len=0;
-
- if (tree->fdb_avl_left != avl_br_empty) {
- sprintf_avl (pbuffer,tree->fdb_avl_left,pos,len,offset,length);
- }
- if (tree->fdb_avl_right != avl_br_empty) {
- sprintf_avl (pbuffer,tree->fdb_avl_right,pos,len,offset,length);
- }
-
- }
-
- return;
-}
-
-/*
- * Delete all nodes learnt by the port
- */
-void br_avl_delete_by_port(int port)
-{
- struct fdb *fdb, *next;
-
- if (!fdb_inited)
- fdb_init();
-
- for(fdb = port_info[port].fdb; fdb != NULL; fdb = next) {
- next = fdb->fdb_next;
- br_avl_remove(fdb);
- }
- port_info[port].fdb = NULL;
-
- /* remove the local mac too */
-/* next = br_avl_find_addr(port_info[port].dev->dev_addr); */
- next = br_avl_find_addr(port_info[port].ifmac.BRIDGE_ID_ULA);
- if (next != NULL)
- br_avl_remove(next);
-
- return;
-}
FUNET's LINUX-ADM group, linux-adm@nic.funet.fi
TCL-scripts by Sam Shen (who was at: slshen@lbl.gov)