[netfilter-cvslog] r7307 - in trunk/conntrack-tools: . include src
pablo at netfilter.org
pablo at netfilter.org
Tue Jan 29 14:54:24 CET 2008
Author: pablo at netfilter.org
Date: 2008-01-29 14:54:24 +0100 (Tue, 29 Jan 2008)
New Revision: 7307
Added:
trunk/conntrack-tools/include/linux_rbtree.h
trunk/conntrack-tools/src/rbtree.c
Modified:
trunk/conntrack-tools/ChangeLog
trunk/conntrack-tools/include/Makefile.am
trunk/conntrack-tools/include/alarm.h
trunk/conntrack-tools/src/Makefile.am
trunk/conntrack-tools/src/alarm.c
trunk/conntrack-tools/src/cache_timer.c
trunk/conntrack-tools/src/run.c
trunk/conntrack-tools/src/sync-alarm.c
trunk/conntrack-tools/src/sync-ftfw.c
Log:
implement a rb-tree based alarm framework
Modified: trunk/conntrack-tools/ChangeLog
===================================================================
--- trunk/conntrack-tools/ChangeLog 2008-01-29 13:48:05 UTC (rev 7306)
+++ trunk/conntrack-tools/ChangeLog 2008-01-29 13:54:24 UTC (rev 7307)
@@ -39,7 +39,7 @@
o fix logfiles permissions, do not default to umask
o wake up the daemon iff there are real events to handle instead of polling
o add support for tagged vlan interfaces in the config file, e.g. eth0.1
-o improve alarm framework based on suggestions from Max Kellerman
+o implement a rb-tree based alarm framework
o constify queue_iterate()
o use list_del_init() and list_empty() to check if a node is in the list
o remove unix socket file on exit
Modified: trunk/conntrack-tools/include/Makefile.am
===================================================================
--- trunk/conntrack-tools/include/Makefile.am 2008-01-29 13:48:05 UTC (rev 7306)
+++ trunk/conntrack-tools/include/Makefile.am 2008-01-29 13:54:24 UTC (rev 7307)
@@ -1,5 +1,5 @@
-noinst_HEADERS = alarm.h jhash.h slist.h cache.h linux_list.h \
+noinst_HEADERS = alarm.h jhash.h slist.h cache.h linux_list.h linux_rbtree.h \
sync.h conntrackd.h local.h us-conntrack.h \
debug.h log.h hash.h mcast.h conntrack.h \
state_helper.h network.h ignore.h queue.h \
Modified: trunk/conntrack-tools/include/alarm.h
===================================================================
--- trunk/conntrack-tools/include/alarm.h 2008-01-29 13:48:05 UTC (rev 7306)
+++ trunk/conntrack-tools/include/alarm.h 2008-01-29 13:54:24 UTC (rev 7307)
@@ -1,30 +1,28 @@
-#ifndef _TIMER_H_
-#define _TIMER_H_
+#ifndef _ALARM_H_
+#define _ALARM_H_
+#include "linux_rbtree.h"
#include "linux_list.h"
#include <sys/time.h>
-struct alarm_list {
- struct list_head head;
+struct alarm_block {
+ struct rb_node node;
+ struct list_head list;
struct timeval tv;
void *data;
- void (*function)(struct alarm_list *a, void *data);
+ void (*function)(struct alarm_block *a, void *data);
};
-int init_alarm_hash(void);
-
-void destroy_alarm_hash(void);
-
-void init_alarm(struct alarm_list *t,
+void init_alarm(struct alarm_block *t,
void *data,
- void (*fcn)(struct alarm_list *a, void *data));
+ void (*fcn)(struct alarm_block *a, void *data));
-void add_alarm(struct alarm_list *alarm, unsigned long sc, unsigned long usc);
+void add_alarm(struct alarm_block *alarm, unsigned long sc, unsigned long usc);
-void del_alarm(struct alarm_list *alarm);
+void del_alarm(struct alarm_block *alarm);
-int alarm_pending(struct alarm_list *alarm);
+int alarm_pending(struct alarm_block *alarm);
struct timeval *
get_next_alarm_run(struct timeval *next_alarm);
Added: trunk/conntrack-tools/include/linux_rbtree.h
===================================================================
--- trunk/conntrack-tools/include/linux_rbtree.h (rev 0)
+++ trunk/conntrack-tools/include/linux_rbtree.h 2008-01-29 13:54:24 UTC (rev 7307)
@@ -0,0 +1,160 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea at suse.de>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/include/linux/rbtree.h
+
+ To use rbtrees you'll have to implement your own insert and search cores.
+ This will avoid us to use callbacks and to drop drammatically performances.
+ I know it's not the cleaner way, but in C (not in C++) to get
+ performances and genericity...
+
+ Some example of insert and search follows here. The search is a plain
+ normal search over an ordered tree. The insert instead must be implemented
+ int two steps: as first thing the code must insert the element in
+ order as a red leaf in the tree, then the support library function
+ rb_insert_color() must be called. Such function will do the
+ not trivial work to rebalance the rbtree if necessary.
+
+-----------------------------------------------------------------------
+static inline struct page * rb_search_page_cache(struct inode * inode,
+ unsigned long offset)
+{
+ struct rb_node * n = inode->i_rb_page_cache.rb_node;
+ struct page * page;
+
+ while (n)
+ {
+ page = rb_entry(n, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ n = n->rb_left;
+ else if (offset > page->offset)
+ n = n->rb_right;
+ else
+ return page;
+ }
+ return NULL;
+}
+
+static inline struct page * __rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
+ struct rb_node * parent = NULL;
+ struct page * page;
+
+ while (*p)
+ {
+ parent = *p;
+ page = rb_entry(parent, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ p = &(*p)->rb_left;
+ else if (offset > page->offset)
+ p = &(*p)->rb_right;
+ else
+ return page;
+ }
+
+ rb_link_node(node, parent, p);
+
+ return NULL;
+}
+
+static inline struct page * rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct page * ret;
+ if ((ret = __rb_insert_page_cache(inode, offset, node)))
+ goto out;
+ rb_insert_color(node, &inode->i_rb_page_cache);
+ out:
+ return ret;
+}
+-----------------------------------------------------------------------
+*/
+
+#ifndef _LINUX_RBTREE_H
+#define _LINUX_RBTREE_H
+
+#include <stdlib.h>
+
+struct rb_node
+{
+ unsigned long rb_parent_color;
+#define RB_RED 0
+#define RB_BLACK 1
+ struct rb_node *rb_right;
+ struct rb_node *rb_left;
+} __attribute__((aligned(sizeof(long))));
+ /* The alignment might seem pointless, but allegedly CRIS needs it */
+
+struct rb_root
+{
+ struct rb_node *rb_node;
+};
+
+
+#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
+#define rb_color(r) ((r)->rb_parent_color & 1)
+#define rb_is_red(r) (!rb_color(r))
+#define rb_is_black(r) rb_color(r)
+#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
+#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+ rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void rb_set_color(struct rb_node *rb, int color)
+{
+ rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
+}
+
+#define RB_ROOT { NULL, }
+#define rb_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
+#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
+#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
+
+extern void rb_insert_color(struct rb_node *, struct rb_root *);
+extern void rb_erase(struct rb_node *, struct rb_root *);
+
+/* Find logical next and previous nodes in a tree */
+extern struct rb_node *rb_next(struct rb_node *);
+extern struct rb_node *rb_prev(struct rb_node *);
+extern struct rb_node *rb_first(struct rb_root *);
+extern struct rb_node *rb_last(struct rb_root *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root);
+
+static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
+ struct rb_node ** rb_link)
+{
+ node->rb_parent_color = (unsigned long )parent;
+ node->rb_left = node->rb_right = NULL;
+
+ *rb_link = node;
+}
+
+#endif /* _LINUX_RBTREE_H */
Modified: trunk/conntrack-tools/src/Makefile.am
===================================================================
--- trunk/conntrack-tools/src/Makefile.am 2008-01-29 13:48:05 UTC (rev 7306)
+++ trunk/conntrack-tools/src/Makefile.am 2008-01-29 13:54:24 UTC (rev 7307)
@@ -10,7 +10,7 @@
conntrack_LDADD = ../extensions/libct_proto_tcp.la ../extensions/libct_proto_udp.la ../extensions/libct_proto_icmp.la
conntrack_LDFLAGS = $(all_libraries) @LIBNETFILTER_CONNTRACK_LIBS@
-conntrackd_SOURCES = alarm.c main.c run.c hash.c queue.c \
+conntrackd_SOURCES = alarm.c main.c run.c hash.c queue.c rbtree.c \
local.c log.c mcast.c netlink.c \
ignore_pool.c \
cache.c cache_iterators.c \
Modified: trunk/conntrack-tools/src/alarm.c
===================================================================
--- trunk/conntrack-tools/src/alarm.c 2008-01-29 13:48:05 UTC (rev 7306)
+++ trunk/conntrack-tools/src/alarm.c 2008-01-29 13:54:24 UTC (rev 7307)
@@ -1,5 +1,5 @@
/*
- * (C) 2006 by Pablo Neira Ayuso <pablo at netfilter.org>
+ * (C) 2006-2008 by Pablo Neira Ayuso <pablo at netfilter.org>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
@@ -17,41 +17,45 @@
*/
#include "alarm.h"
-#include "jhash.h"
#include <stdlib.h>
#include <limits.h>
-#define ALARM_HASH_SIZE 2048
+static struct rb_root alarm_root = RB_ROOT;
+static LIST_HEAD(alarm_run_queue);
-static struct list_head *alarm_hash;
-
-void init_alarm(struct alarm_list *t,
+void init_alarm(struct alarm_block *t,
void *data,
- void (*fcn)(struct alarm_list *a, void *data))
+ void (*fcn)(struct alarm_block *a, void *data))
{
/* initialize the head to check whether a node is inserted */
- INIT_LIST_HEAD(&t->head);
+ RB_CLEAR_NODE(&t->node);
timerclear(&t->tv);
t->data = data;
t->function = fcn;
}
-static void
-__add_alarm(struct alarm_list *alarm)
+static void __add_alarm(struct alarm_block *alarm)
{
- struct alarm_list *t;
- int i = jhash(alarm, sizeof(alarm), 0) % ALARM_HASH_SIZE;
+ struct rb_node **new = &(alarm_root.rb_node);
+ struct rb_node *parent = NULL;
- list_for_each_entry(t, &alarm_hash[i], head) {
- if (timercmp(&alarm->tv, &t->tv, <)) {
- list_add_tail(&alarm->head, &t->head);
- return;
- }
+ while (*new) {
+ struct alarm_block *this;
+
+ this = container_of(*new, struct alarm_block, node);
+
+ parent = *new;
+ if (timercmp(&alarm->tv, &this->tv, <))
+ new = &((*new)->rb_left);
+ else
+ new = &((*new)->rb_right);
}
- list_add_tail(&alarm->head, &alarm_hash[i]);
+
+ rb_link_node(&alarm->node, parent, new);
+ rb_insert_color(&alarm->node, &alarm_root);
}
-void add_alarm(struct alarm_list *alarm, unsigned long sc, unsigned long usc)
+void add_alarm(struct alarm_block *alarm, unsigned long sc, unsigned long usc)
{
struct timeval tv;
@@ -63,16 +67,18 @@
__add_alarm(alarm);
}
-void del_alarm(struct alarm_list *alarm)
+void del_alarm(struct alarm_block *alarm)
{
/* don't remove a non-inserted node */
- if (!list_empty(&alarm->head))
- list_del_init(&alarm->head);
+ if (!RB_EMPTY_NODE(&alarm->node)) {
+ rb_erase(&alarm->node, &alarm_root);
+ RB_CLEAR_NODE(&alarm->node);
+ }
}
-int alarm_pending(struct alarm_list *alarm)
+int alarm_pending(struct alarm_block *alarm)
{
- if (list_empty(&alarm->head))
+ if (RB_EMPTY_NODE(&alarm->node))
return 0;
return 1;
@@ -99,101 +105,47 @@
struct timeval *
get_next_alarm_run(struct timeval *next_run)
{
- int i;
- struct alarm_list *t;
+ struct rb_node *node = alarm_root.rb_node;
struct timeval tv;
- struct timeval cand = {
- .tv_sec = LONG_MAX,
- .tv_usec = LONG_MAX
- };
gettimeofday(&tv, NULL);
- for (i=0; i<ALARM_HASH_SIZE; i++) {
- if (!list_empty(&alarm_hash[i])) {
- t = list_entry(alarm_hash[i].next,
- struct alarm_list,
- head);
- if (timercmp(&t->tv, &cand, <)) {
- cand.tv_sec = t->tv.tv_sec;
- cand.tv_usec = t->tv.tv_usec;
- }
- }
+ node = rb_first(&alarm_root);
+ if (node) {
+ struct alarm_block *this;
+ this = container_of(node, struct alarm_block, node);
+ return calculate_next_run(&this->tv, &tv, next_run);
}
-
- return calculate_next_run(&cand, &tv, next_run);
+ return NULL;
}
-static inline int
-tv_compare(struct alarm_list *a, struct timeval *cur, struct timeval *cand)
-{
- if (timercmp(&a->tv, cur, >)) {
- /* select the next alarm candidate */
- if (timercmp(&a->tv, cand, <)) {
- cand->tv_sec = a->tv.tv_sec;
- cand->tv_usec = a->tv.tv_usec;
- }
- return 1;
- }
- return 0;
-}
-
struct timeval *
do_alarm_run(struct timeval *next_run)
{
- int i;
- struct alarm_list *t, *next, *prev;
+ struct rb_node *node = alarm_root.rb_node;
+ struct alarm_block *this, *tmp;
struct timeval tv;
- struct timeval cand = {
- .tv_sec = LONG_MAX,
- .tv_usec = LONG_MAX
- };
gettimeofday(&tv, NULL);
- for (i=0; i<ALARM_HASH_SIZE; i++) {
- list_for_each_entry_safe(t, next, &alarm_hash[i], head) {
- if (tv_compare(t, &tv, &cand))
- break;
+ node = rb_first(&alarm_root);
+ while (node) {
+ this = container_of(node, struct alarm_block, node);
- /* annotate previous alarm */
- prev = list_entry(next->head.prev,
- struct alarm_list,
- head);
+ if (timercmp(&this->tv, &tv, >))
+ break;
- del_alarm(t);
- t->function(t, t->data);
+ node = rb_next(node);
- /* Special case: One deleted node is inserted
- * again in the same place */
- if (next->head.prev == &prev->head) {
- t = list_entry(next->head.prev,
- struct alarm_list,
- head);
- if (tv_compare(t, &tv, &cand))
- break;
- }
- }
+ list_add(&this->list, &alarm_run_queue);
}
- return calculate_next_run(&cand, &tv, next_run);
-}
+ list_for_each_entry_safe(this, tmp, &alarm_run_queue, list) {
+ list_del(&this->list);
+ rb_erase(&this->node, &alarm_root);
+ RB_CLEAR_NODE(&this->node);
+ this->function(this, this->data);
+ }
-int init_alarm_hash(void)
-{
- int i;
-
- alarm_hash = malloc(sizeof(struct list_head) * ALARM_HASH_SIZE);
- if (alarm_hash == NULL)
- return -1;
-
- for (i=0; i<ALARM_HASH_SIZE; i++)
- INIT_LIST_HEAD(&alarm_hash[i]);
-
- return 0;
+ return get_next_alarm_run(next_run);
}
-
-void destroy_alarm_hash(void)
-{
- free(alarm_hash);
-}
Modified: trunk/conntrack-tools/src/cache_timer.c
===================================================================
--- trunk/conntrack-tools/src/cache_timer.c 2008-01-29 13:48:05 UTC (rev 7306)
+++ trunk/conntrack-tools/src/cache_timer.c 2008-01-29 13:54:24 UTC (rev 7307)
@@ -24,7 +24,7 @@
#include <stdio.h>
-static void timeout(struct alarm_list *a, void *data)
+static void timeout(struct alarm_block *a, void *data)
{
struct us_conntrack *u = data;
@@ -34,7 +34,7 @@
static void timer_add(struct us_conntrack *u, void *data)
{
- struct alarm_list *alarm = data;
+ struct alarm_block *alarm = data;
init_alarm(alarm, u, timeout);
add_alarm(alarm, CONFIG(cache_timeout), 0);
@@ -42,20 +42,20 @@
static void timer_update(struct us_conntrack *u, void *data)
{
- struct alarm_list *alarm = data;
+ struct alarm_block *alarm = data;
add_alarm(alarm, CONFIG(cache_timeout), 0);
}
static void timer_destroy(struct us_conntrack *u, void *data)
{
- struct alarm_list *alarm = data;
+ struct alarm_block *alarm = data;
del_alarm(alarm);
}
static int timer_dump(struct us_conntrack *u, void *data, char *buf, int type)
{
struct timeval tv, tmp;
- struct alarm_list *alarm = data;
+ struct alarm_block *alarm = data;
if (type == NFCT_O_XML)
return 0;
@@ -69,7 +69,7 @@
}
struct cache_feature timer_feature = {
- .size = sizeof(struct alarm_list),
+ .size = sizeof(struct alarm_block),
.add = timer_add,
.update = timer_update,
.destroy = timer_destroy,
Added: trunk/conntrack-tools/src/rbtree.c
===================================================================
--- trunk/conntrack-tools/src/rbtree.c (rev 0)
+++ trunk/conntrack-tools/src/rbtree.c 2008-01-29 13:54:24 UTC (rev 7307)
@@ -0,0 +1,389 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea at suse.de>
+ (C) 2002 David Woodhouse <dwmw2 at infradead.org>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/lib/rbtree.c
+*/
+
+#include "linux_rbtree.h"
+
+static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *right = node->rb_right;
+ struct rb_node *parent = rb_parent(node);
+
+ if ((node->rb_right = right->rb_left))
+ rb_set_parent(right->rb_left, node);
+ right->rb_left = node;
+
+ rb_set_parent(right, parent);
+
+ if (parent)
+ {
+ if (node == parent->rb_left)
+ parent->rb_left = right;
+ else
+ parent->rb_right = right;
+ }
+ else
+ root->rb_node = right;
+ rb_set_parent(node, right);
+}
+
+static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *left = node->rb_left;
+ struct rb_node *parent = rb_parent(node);
+
+ if ((node->rb_left = left->rb_right))
+ rb_set_parent(left->rb_right, node);
+ left->rb_right = node;
+
+ rb_set_parent(left, parent);
+
+ if (parent)
+ {
+ if (node == parent->rb_right)
+ parent->rb_right = left;
+ else
+ parent->rb_left = left;
+ }
+ else
+ root->rb_node = left;
+ rb_set_parent(node, left);
+}
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *parent, *gparent;
+
+ while ((parent = rb_parent(node)) && rb_is_red(parent))
+ {
+ gparent = rb_parent(parent);
+
+ if (parent == gparent->rb_left)
+ {
+ {
+ register struct rb_node *uncle = gparent->rb_right;
+ if (uncle && rb_is_red(uncle))
+ {
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_right == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_left(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ __rb_rotate_right(gparent, root);
+ } else {
+ {
+ register struct rb_node *uncle = gparent->rb_left;
+ if (uncle && rb_is_red(uncle))
+ {
+ rb_set_black(uncle);
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->rb_left == node)
+ {
+ register struct rb_node *tmp;
+ __rb_rotate_right(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ rb_set_black(parent);
+ rb_set_red(gparent);
+ __rb_rotate_left(gparent, root);
+ }
+ }
+
+ rb_set_black(root->rb_node);
+}
+
+static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+ struct rb_root *root)
+{
+ struct rb_node *other;
+
+ while ((!node || rb_is_black(node)) && node != root->rb_node)
+ {
+ if (parent->rb_left == node)
+ {
+ other = parent->rb_right;
+ if (rb_is_red(other))
+ {
+ rb_set_black(other);
+ rb_set_red(parent);
+ __rb_rotate_left(parent, root);
+ other = parent->rb_right;
+ }
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
+ {
+ rb_set_red(other);
+ node = parent;
+ parent = rb_parent(node);
+ }
+ else
+ {
+ if (!other->rb_right || rb_is_black(other->rb_right))
+ {
+ struct rb_node *o_left;
+ if ((o_left = other->rb_left))
+ rb_set_black(o_left);
+ rb_set_red(other);
+ __rb_rotate_right(other, root);
+ other = parent->rb_right;
+ }
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
+ if (other->rb_right)
+ rb_set_black(other->rb_right);
+ __rb_rotate_left(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ else
+ {
+ other = parent->rb_left;
+ if (rb_is_red(other))
+ {
+ rb_set_black(other);
+ rb_set_red(parent);
+ __rb_rotate_right(parent, root);
+ other = parent->rb_left;
+ }
+ if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+ (!other->rb_right || rb_is_black(other->rb_right)))
+ {
+ rb_set_red(other);
+ node = parent;
+ parent = rb_parent(node);
+ }
+ else
+ {
+ if (!other->rb_left || rb_is_black(other->rb_left))
+ {
+ register struct rb_node *o_right;
+ if ((o_right = other->rb_right))
+ rb_set_black(o_right);
+ rb_set_red(other);
+ __rb_rotate_left(other, root);
+ other = parent->rb_left;
+ }
+ rb_set_color(other, rb_color(parent));
+ rb_set_black(parent);
+ if (other->rb_left)
+ rb_set_black(other->rb_left);
+ __rb_rotate_right(parent, root);
+ node = root->rb_node;
+ break;
+ }
+ }
+ }
+ if (node)
+ rb_set_black(node);
+}
+
+void rb_erase(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *child, *parent;
+ int color;
+
+ if (!node->rb_left)
+ child = node->rb_right;
+ else if (!node->rb_right)
+ child = node->rb_left;
+ else
+ {
+ struct rb_node *old = node, *left;
+
+ node = node->rb_right;
+ while ((left = node->rb_left) != NULL)
+ node = left;
+ child = node->rb_right;
+ parent = rb_parent(node);
+ color = rb_color(node);
+
+ if (child)
+ rb_set_parent(child, parent);
+ if (parent == old) {
+ parent->rb_right = child;
+ parent = node;
+ } else
+ parent->rb_left = child;
+
+ node->rb_parent_color = old->rb_parent_color;
+ node->rb_right = old->rb_right;
+ node->rb_left = old->rb_left;
+
+ if (rb_parent(old))
+ {
+ if (rb_parent(old)->rb_left == old)
+ rb_parent(old)->rb_left = node;
+ else
+ rb_parent(old)->rb_right = node;
+ } else
+ root->rb_node = node;
+
+ rb_set_parent(old->rb_left, node);
+ if (old->rb_right)
+ rb_set_parent(old->rb_right, node);
+ goto color;
+ }
+
+ parent = rb_parent(node);
+ color = rb_color(node);
+
+ if (child)
+ rb_set_parent(child, parent);
+ if (parent)
+ {
+ if (parent->rb_left == node)
+ parent->rb_left = child;
+ else
+ parent->rb_right = child;
+ }
+ else
+ root->rb_node = child;
+
+ color:
+ if (color == RB_BLACK)
+ __rb_erase_color(child, parent, root);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *rb_first(struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_left)
+ n = n->rb_left;
+ return n;
+}
+
+struct rb_node *rb_last(struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_right)
+ n = n->rb_right;
+ return n;
+}
+
+struct rb_node *rb_next(struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a right-hand child, go down and then left as far
+ as we can. */
+ if (node->rb_right) {
+ node = node->rb_right;
+ while (node->rb_left)
+ node=node->rb_left;
+ return node;
+ }
+
+ /* No right-hand children. Everything down and left is
+ smaller than us, so any 'next' node must be in the general
+ direction of our parent. Go up the tree; any time the
+ ancestor is a right-hand child of its parent, keep going
+ up. First time it's a left-hand child of its parent, said
+ parent is our 'next' node. */
+ while ((parent = rb_parent(node)) && node == parent->rb_right)
+ node = parent;
+
+ return parent;
+}
+
+struct rb_node *rb_prev(struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a left-hand child, go down and then right as far
+ as we can. */
+ if (node->rb_left) {
+ node = node->rb_left;
+ while (node->rb_right)
+ node=node->rb_right;
+ return node;
+ }
+
+ /* No left-hand children. Go up till we find an ancestor which
+ is a right-hand child of its parent */
+ while ((parent = rb_parent(node)) && node == parent->rb_left)
+ node = parent;
+
+ return parent;
+}
+
+void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root)
+{
+ struct rb_node *parent = rb_parent(victim);
+
+ /* Set the surrounding nodes to point to the replacement */
+ if (parent) {
+ if (victim == parent->rb_left)
+ parent->rb_left = new;
+ else
+ parent->rb_right = new;
+ } else {
+ root->rb_node = new;
+ }
+ if (victim->rb_left)
+ rb_set_parent(victim->rb_left, new);
+ if (victim->rb_right)
+ rb_set_parent(victim->rb_right, new);
+
+ /* Copy the pointers/colour from the victim to the replacement */
+ *new = *victim;
+}
Modified: trunk/conntrack-tools/src/run.c
===================================================================
--- trunk/conntrack-tools/src/run.c 2008-01-29 13:48:05 UTC (rev 7306)
+++ trunk/conntrack-tools/src/run.c 2008-01-29 13:54:24 UTC (rev 7307)
@@ -42,7 +42,6 @@
ignore_pool_destroy(STATE(ignore_pool));
local_server_destroy(&STATE(local));
STATE(mode)->kill();
- destroy_alarm_hash();
unlink(CONFIG(lockfile));
dlog(LOG_NOTICE, "---- shutdown received ----");
close_log();
@@ -103,11 +102,6 @@
STATE(mode) = &stats_mode;
}
- if (init_alarm_hash() == -1) {
- dlog(LOG_ERR, "can't initialize alarm hash");
- return -1;
- }
-
/* Initialization */
if (STATE(mode)->init() == -1) {
dlog(LOG_ERR, "initialization failed");
Modified: trunk/conntrack-tools/src/sync-alarm.c
===================================================================
--- trunk/conntrack-tools/src/sync-alarm.c 2008-01-29 13:48:05 UTC (rev 7306)
+++ trunk/conntrack-tools/src/sync-alarm.c 2008-01-29 13:54:24 UTC (rev 7307)
@@ -27,7 +27,7 @@
#include <stdlib.h>
#include <string.h>
-static void refresher(struct alarm_list *a, void *data)
+static void refresher(struct alarm_block *a, void *data)
{
size_t len;
struct nethdr *net;
@@ -46,7 +46,7 @@
static void cache_alarm_add(struct us_conntrack *u, void *data)
{
- struct alarm_list *alarm = data;
+ struct alarm_block *alarm = data;
init_alarm(alarm, u, refresher);
add_alarm(alarm,
@@ -56,7 +56,7 @@
static void cache_alarm_update(struct us_conntrack *u, void *data)
{
- struct alarm_list *alarm = data;
+ struct alarm_block *alarm = data;
add_alarm(alarm,
random() % CONFIG(refresh) + 1,
((random() % 5 + 1) * 200000) - 1);
@@ -64,12 +64,12 @@
static void cache_alarm_destroy(struct us_conntrack *u, void *data)
{
- struct alarm_list *alarm = data;
+ struct alarm_block *alarm = data;
del_alarm(alarm);
}
static struct cache_extra cache_alarm_extra = {
- .size = sizeof(struct alarm_list),
+ .size = sizeof(struct alarm_block),
.add = cache_alarm_add,
.update = cache_alarm_update,
.destroy = cache_alarm_destroy
Modified: trunk/conntrack-tools/src/sync-ftfw.c
===================================================================
--- trunk/conntrack-tools/src/sync-ftfw.c 2008-01-29 13:48:05 UTC (rev 7306)
+++ trunk/conntrack-tools/src/sync-ftfw.c 2008-01-29 13:54:24 UTC (rev 7307)
@@ -83,9 +83,9 @@
queue_add(tx_queue, &ack, NETHDR_ACK_SIZ);
}
-static struct alarm_list alive_alarm;
+static struct alarm_block alive_alarm;
-static void do_alive_alarm(struct alarm_list *a, void *data)
+static void do_alive_alarm(struct alarm_block *a, void *data)
{
tx_queue_add_ctlmsg(NET_F_ALIVE, 0, 0);
More information about the netfilter-cvslog
mailing list