[netfilter-cvslog] r7377 - in branches/ulog/ulogd2: include/ulogd input/flow src
pablo at netfilter.org
pablo at netfilter.org
Tue Feb 19 19:53:08 CET 2008
Author: pablo at netfilter.org
Date: 2008-02-19 19:53:07 +0100 (Tue, 19 Feb 2008)
New Revision: 7377
Added:
branches/ulog/ulogd2/include/ulogd/linux_rbtree.h
branches/ulog/ulogd2/src/rbtree.c
Modified:
branches/ulog/ulogd2/include/ulogd/Makefile.am
branches/ulog/ulogd2/include/ulogd/ulogd.h
branches/ulog/ulogd2/input/flow/ulogd_inpflow_NFCT.c
branches/ulog/ulogd2/src/Makefile.am
branches/ulog/ulogd2/src/select.c
branches/ulog/ulogd2/src/timer.c
branches/ulog/ulogd2/src/ulogd.c
Log:
- implement a synchronous timer framework
- fix crash when enabling pollinterval clause in flow-based accounting
Modified: branches/ulog/ulogd2/include/ulogd/Makefile.am
===================================================================
--- branches/ulog/ulogd2/include/ulogd/Makefile.am 2008-02-19 16:04:48 UTC (rev 7376)
+++ branches/ulog/ulogd2/include/ulogd/Makefile.am 2008-02-19 18:53:07 UTC (rev 7377)
@@ -1,2 +1,2 @@
-noinst_HEADERS = conffile.h db.h ipfix_protocol.h linuxlist.h ulogd.h printpkt.h printflow.h common.h
+noinst_HEADERS = conffile.h db.h ipfix_protocol.h linuxlist.h ulogd.h printpkt.h printflow.h common.h linux_rbtree.h timer.h
Added: branches/ulog/ulogd2/include/ulogd/linux_rbtree.h
===================================================================
--- branches/ulog/ulogd2/include/ulogd/linux_rbtree.h (rev 0)
+++ branches/ulog/ulogd2/include/ulogd/linux_rbtree.h 2008-02-19 18:53:07 UTC (rev 7377)
@@ -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: branches/ulog/ulogd2/include/ulogd/ulogd.h
===================================================================
--- branches/ulog/ulogd2/include/ulogd/ulogd.h 2008-02-19 16:04:48 UTC (rev 7376)
+++ branches/ulog/ulogd2/include/ulogd/ulogd.h 2008-02-19 18:53:07 UTC (rev 7377)
@@ -242,20 +242,11 @@
int ulogd_register_fd(struct ulogd_fd *ufd);
void ulogd_unregister_fd(struct ulogd_fd *ufd);
-int ulogd_select_main();
+int ulogd_select_main(struct timeval *tv);
/***********************************************************************
* timer handling
***********************************************************************/
+#include <ulogd/timer.h>
-struct ulogd_timer {
- struct llist_head list;
- struct timeval expires;
- void (*cb)(void *data);
- void *data;
-};
-
-int ulogd_register_timer(struct ulogd_timer *timer);
-void ulogd_unregister_timer(struct ulogd_timer *timer);
-
#endif /* _ULOGD_H */
Modified: branches/ulog/ulogd2/input/flow/ulogd_inpflow_NFCT.c
===================================================================
--- branches/ulog/ulogd2/input/flow/ulogd_inpflow_NFCT.c 2008-02-19 16:04:48 UTC (rev 7376)
+++ branches/ulog/ulogd2/input/flow/ulogd_inpflow_NFCT.c 2008-02-19 18:53:07 UTC (rev 7377)
@@ -3,6 +3,7 @@
* ulogd input plugin for ctnetlink
*
* (C) 2005 by Harald Welte <laforge at netfilter.org>
+ * (C) 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 version 2
@@ -35,6 +36,7 @@
#include <ulogd/linuxlist.h>
#include <ulogd/ulogd.h>
+#include <ulogd/timer.h>
#include <ulogd/ipfix_protocol.h>
#include <libnetfilter_conntrack/libnetfilter_conntrack.h>
@@ -551,6 +553,7 @@
return 0;
}
+/* XXX: pollinterval needs a different handler */
static int event_handler(void *arg, unsigned int flags, int type,
void *data)
{
@@ -593,11 +596,14 @@
return nfct_dump_conntrack_table_reset_counters(cpi->cth, AF_INET);
}
-static void getctr_timer_cb(void *data)
+static void getctr_timer_cb(struct ulogd_timer *t, void *data)
{
struct ulogd_pluginstance *upi = data;
+ struct nfct_pluginstance *cpi =
+ (struct nfct_pluginstance *)upi->private;
get_ctr_zero(upi);
+ ulogd_add_timer(&cpi->timer, pollint_ce(upi->config_kset).u.value);
}
static int configure_nfct(struct ulogd_pluginstance *upi,
@@ -610,17 +616,11 @@
ret = config_parse_file(upi->id, upi->config_kset);
if (ret < 0)
return ret;
-
- /* initialize getctrzero timer structure */
- memset(&cpi->timer, 0, sizeof(cpi->timer));
- cpi->timer.cb = &getctr_timer_cb;
- cpi->timer.data = cpi;
- if (pollint_ce(upi->config_kset).u.value != 0) {
- cpi->timer.expires.tv_sec =
- pollint_ce(upi->config_kset).u.value;
- ulogd_register_timer(&cpi->timer);
- }
+ ulogd_init_timer(&cpi->timer, upi, getctr_timer_cb);
+ if (pollint_ce(upi->config_kset).u.value != 0)
+ ulogd_add_timer(&cpi->timer,
+ pollint_ce(upi->config_kset).u.value);
return 0;
}
@@ -631,8 +631,6 @@
(struct nfct_pluginstance *)upi->private;
int prealloc;
- memset(cpi, 0, sizeof(*cpi));
-
/* FIXME: make eventmask configurable */
cpi->cth = nfct_open(NFNL_SUBSYS_CTNETLINK, NF_NETLINK_CONNTRACK_NEW|
NF_NETLINK_CONNTRACK_DESTROY);
Modified: branches/ulog/ulogd2/src/Makefile.am
===================================================================
--- branches/ulog/ulogd2/src/Makefile.am 2008-02-19 16:04:48 UTC (rev 7376)
+++ branches/ulog/ulogd2/src/Makefile.am 2008-02-19 18:53:07 UTC (rev 7377)
@@ -5,5 +5,5 @@
sbin_PROGRAMS = ulogd
-ulogd_SOURCES = ulogd.c select.c timer.c conffile.c
+ulogd_SOURCES = ulogd.c select.c timer.c rbtree.c conffile.c
ulogd_LDFLAGS = -export-dynamic
Added: branches/ulog/ulogd2/src/rbtree.c
===================================================================
--- branches/ulog/ulogd2/src/rbtree.c (rev 0)
+++ branches/ulog/ulogd2/src/rbtree.c 2008-02-19 18:53:07 UTC (rev 7377)
@@ -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 <ulogd/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: branches/ulog/ulogd2/src/select.c
===================================================================
--- branches/ulog/ulogd2/src/select.c 2008-02-19 16:04:48 UTC (rev 7376)
+++ branches/ulog/ulogd2/src/select.c 2008-02-19 18:53:07 UTC (rev 7377)
@@ -55,7 +55,7 @@
llist_del(&fd->list);
}
-int ulogd_select_main()
+int ulogd_select_main(struct timeval *tv)
{
struct ulogd_fd *ufd;
fd_set readset, writeset, exceptset;
@@ -77,7 +77,7 @@
FD_SET(ufd->fd, &exceptset);
}
- i = select(maxfd+1, &readset, &writeset, &exceptset, NULL);
+ i = select(maxfd+1, &readset, &writeset, &exceptset, tv);
if (i > 0) {
/* call registered callback functions */
llist_for_each_entry(ufd, &ulogd_fds, list) {
Modified: branches/ulog/ulogd2/src/timer.c
===================================================================
--- branches/ulog/ulogd2/src/timer.c 2008-02-19 16:04:48 UTC (rev 7376)
+++ branches/ulog/ulogd2/src/timer.c 2008-02-19 18:53:07 UTC (rev 7377)
@@ -4,11 +4,15 @@
*
* userspace logging daemon for the netfilter subsystem
*
+ * (C) 2006-2008 by Pablo Neira Ayuso <pablo at netfilter.org>
+ *
+ * based on previous works by:
+ *
* (C) 2000-2005 by Harald Welte <laforge at gnumonks.org>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2
- * as published by the Free Software Foundation
+ * as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ -17,151 +21,146 @@
*
* 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
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ * Description:
+ * This is the timer framework for ulogd, it works together with select()
+ * so that the daemon only wakes up when there are timers expired to run.
+ * This approach is more simple than the previous signal-based implementation
+ * that could wake up the daemon while running at any part of the code.
+ *
+ * TODO:
+ * - This piece of code has been extracted from conntrackd. Probably
+ * ulogd doesn't require such O(log n) scalable timer framework. Anyhow,
+ * we can simplify this code using the same API later, that would be
+ * quite straight forward.
*/
-#include <unistd.h>
+#include <ulogd/timer.h>
#include <stdlib.h>
-#include <string.h>
-#include <sys/time.h>
-#include <time.h>
+#include <limits.h>
-#include <ulogd/ulogd.h>
-#include <ulogd/linuxlist.h>
+static struct rb_root alarm_root = RB_ROOT;
-static LLIST_HEAD(ulogd_timers);
-
-static void tv_normalize(struct timeval *out)
+void ulogd_init_timer(struct ulogd_timer *t,
+ void *data,
+ void (*cb)(struct ulogd_timer *a, void *data))
{
- out->tv_sec += (out->tv_usec / 1000000);
- out->tv_usec = (out->tv_usec % 1000000);
+ /* initialize the head to check whether a node is inserted */
+ RB_CLEAR_NODE(&t->node);
+ timerclear(&t->tv);
+ t->data = data;
+ t->cb = cb;
}
-/* subtract two struct timevals */
-static int tv_sub(struct timeval *res, const struct timeval *from,
- const struct timeval *sub)
+static void __add_timer(struct ulogd_timer *alarm)
{
- /* FIXME: this stinks. Deal with wraps, carry, ... */
- res->tv_sec = from->tv_sec - sub->tv_sec;
- res->tv_usec = from->tv_usec - sub->tv_usec;
+ struct rb_node **new = &(alarm_root.rb_node);
+ struct rb_node *parent = NULL;
- return 0;
-}
+ while (*new) {
+ struct ulogd_timer *this;
-static int tv_add(struct timeval *res, const struct timeval *a1,
- const struct timeval *a2)
-{
- unsigned int carry;
+ this = container_of(*new, struct ulogd_timer, node);
- res->tv_sec = a1->tv_sec + a2->tv_sec;
- res->tv_usec = a1->tv_usec + a2->tv_usec;
+ parent = *new;
+ if (timercmp(&alarm->tv, &this->tv, <))
+ new = &((*new)->rb_left);
+ else
+ new = &((*new)->rb_right);
+ }
- tv_normalize(res);
+ rb_link_node(&alarm->node, parent, new);
+ rb_insert_color(&alarm->node, &alarm_root);
}
-static int tv_later(const struct timeval *expires, const struct timeval *now)
+void ulogd_add_timer(struct ulogd_timer *alarm, unsigned long sc)
{
- if (expires->tv_sec < now->tv_sec)
- return 0;
- else if (expires->tv_sec > now->tv_sec)
- return 1;
- else /* if (expires->tv_sec == now->tv_sec */ {
- if (expires->tv_usec >= now->tv_usec)
- return 1;
- }
+ struct timeval tv;
- return 0;
+ ulogd_del_timer(alarm);
+ alarm->tv.tv_sec = sc;
+ alarm->tv.tv_usec = 0;
+ gettimeofday(&tv, NULL);
+ timeradd(&alarm->tv, &tv, &alarm->tv);
+ __add_timer(alarm);
}
-static int tv_smaller(const struct timeval *t1, const struct timeval *t2)
+void ulogd_del_timer(struct ulogd_timer *alarm)
{
- return tv_later(t2, t1);
+ /* don't remove a non-inserted node */
+ if (!RB_EMPTY_NODE(&alarm->node)) {
+ rb_erase(&alarm->node, &alarm_root);
+ RB_CLEAR_NODE(&alarm->node);
+ }
}
-static int calc_next_expiration(void)
+int ulogd_timer_pending(struct ulogd_timer *alarm)
{
- struct ulogd_timer *cur;
- struct timeval min, now, diff;
- struct itimerval iti;
- int ret;
-
-retry:
- if (llist_empty(&ulogd_timers))
+ if (RB_EMPTY_NODE(&alarm->node))
return 0;
- llist_for_each_entry(cur, &ulogd_timers, list) {
- if (ulogd_timers.next == &cur->list)
- min = cur->expires;
+ return 1;
+}
- if (tv_smaller(&cur->expires, &min))
- min = cur->expires;
+static struct timeval *
+calculate_next_run(struct timeval *cand,
+ struct timeval *tv,
+ struct timeval *next_run)
+{
+ if (cand->tv_sec != LONG_MAX) {
+ if (timercmp(cand, tv, >))
+ timersub(cand, tv, next_run);
+ else {
+ /* loop again inmediately */
+ next_run->tv_sec = 0;
+ next_run->tv_usec = 0;
+ }
+ return next_run;
}
-
- if (tv_sub(&diff, &min, &now) < 0) {
- /* FIXME: run expired timer callbacks */
- /* we cannot run timers from here since we might be
- * called from register_timer() within check_n_run() */
-
- /* FIXME: restart with next minimum timer */
- goto retry;
- }
-
- /* re-set kernel timer */
- memset(&iti, 0, sizeof(iti));
- memcpy(&iti.it_value, &diff, sizeof(iti.it_value));
- ret = setitimer(ITIMER_REAL, &iti, NULL);
- if (ret < 0)
- return ret;
-
- return 0;
+ return NULL;
}
-void ulogd_timer_check_n_run(void)
+struct timeval *ulogd_get_next_timer_run(struct timeval *next_run)
{
- struct ulogd_timer *cur, *cur2;
- struct timeval now;
+ struct rb_node *node;
+ struct timeval tv;
- if (gettimeofday(&now, NULL) < 0)
- return;
+ gettimeofday(&tv, NULL);
- llist_for_each_entry_safe(cur, cur2, &ulogd_timers, list) {
- if (tv_later(&cur->expires, &now)) {
- /* fist delete it from the list of timers */
- llist_del(&cur->list);
- /* then call. called function can re-add it */
- (cur->cb)(cur->data);
- }
+ node = rb_first(&alarm_root);
+ if (node) {
+ struct ulogd_timer *this;
+ this = container_of(node, struct ulogd_timer, node);
+ return calculate_next_run(&this->tv, &tv, next_run);
}
-
- calc_next_expiration();
+ return NULL;
}
-
-int ulogd_register_timer(struct ulogd_timer *timer)
+struct timeval *ulogd_do_timer_run(struct timeval *next_run)
{
- int ret;
+ struct llist_head alarm_run_queue;
+ struct rb_node *node;
+ struct ulogd_timer *this;
struct timeval tv;
- ret = gettimeofday(&tv, NULL);
- if (ret < 0)
- return ret;
+ gettimeofday(&tv, NULL);
- /* convert expiration time into absoulte time */
- timer->expires.tv_sec += tv.tv_sec;
- timer->expires.tv_usec += tv.tv_usec;
+ INIT_LLIST_HEAD(&alarm_run_queue);
+ for (node = rb_first(&alarm_root); node; node = rb_next(node)) {
+ this = container_of(node, struct ulogd_timer, node);
- llist_add_tail(&timer->list, &ulogd_timers);
+ if (timercmp(&this->tv, &tv, >))
+ break;
- /* re-calculate next expiration */
- calc_next_expiration();
+ llist_add(&this->list, &alarm_run_queue);
+ }
- return 0;
-}
+ llist_for_each_entry(this, &alarm_run_queue, list) {
+ rb_erase(&this->node, &alarm_root);
+ RB_CLEAR_NODE(&this->node);
+ this->cb(this, this->data);
+ }
-void ulogd_unregister_timer(struct ulogd_timer *timer)
-{
- llist_del(&timer->list);
-
- /* re-calculate next expiration */
- calc_next_expiration();
+ return ulogd_get_next_timer_run(next_run);
}
Modified: branches/ulog/ulogd2/src/ulogd.c
===================================================================
--- branches/ulog/ulogd2/src/ulogd.c 2008-02-19 16:04:48 UTC (rev 7376)
+++ branches/ulog/ulogd2/src/ulogd.c 2008-02-19 18:53:07 UTC (rev 7377)
@@ -61,6 +61,7 @@
#include <pwd.h>
#include <grp.h>
#include <syslog.h>
+#include <sys/time.h>
#include <ulogd/conffile.h>
#include <ulogd/ulogd.h>
#ifdef DEBUG
@@ -828,27 +829,24 @@
}
-static int ulogd_main_loop(void)
+static void ulogd_main_loop(void)
{
- int ret = 0;
+ int ret;
+ struct timeval next_alarm;
+ struct timeval *next = NULL;
while (1) {
- ret = ulogd_select_main();
- if (ret == 0)
- continue;
+ /* XXX: signal blocking? */
+ if (next != NULL && !timerisset(next))
+ next = ulogd_do_timer_run(&next_alarm);
+ else
+ next = ulogd_get_next_timer_run(&next_alarm);
- if (ret < 0) {
- if (errno == -EINTR)
- continue;
- else {
- ulogd_log(ULOGD_ERROR, "select returned %s\n",
- strerror(errno));
- break;
- }
- }
+ ret = ulogd_select_main(next);
+ if (ret < 0 && errno != -EINTR)
+ ulogd_log(ULOGD_ERROR, "select says %s\n",
+ strerror(errno));
}
-
- return ret;
}
/* open the logfile */
@@ -953,9 +951,6 @@
sigterm_handler(signal);
}
break;
- case SIGALRM:
- ulogd_timer_check_n_run();
- break;
default:
break;
}
More information about the netfilter-cvslog
mailing list