lkml.org 
[lkml]   [2011]   [Jan]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 01/12] timers: Introduce timerlist infrastructure.
    Date
    The timerlist infrastructure is a thin layer over the rbtree
    code that implements a simple list of timers sorted by an
    expires value, and a getnext function that provides a pointer
    to the earliest timer.

    This infrastructure allows drivers and other kernel infrastructure
    to easily implement timers without duplicating code.

    Signed-off-by: John Stultz <john.stultz@linaro.org>
    LKML Reference: <1290136329-18291-2-git-send-email-john.stultz@linaro.org>
    Reviewed-by: Thomas Gleixner <tglx@linutronix.de>
    CC: Alessandro Zummo <a.zummo@towertech.it>
    CC: Thomas Gleixner <tglx@linutronix.de>
    CC: Richard Cochran <richardcochran@gmail.com>
    ---
    include/linux/timerlist.h | 37 ++++++++++++++
    lib/Makefile | 2 +-
    lib/timerlist.c | 118 +++++++++++++++++++++++++++++++++++++++++++++
    3 files changed, 156 insertions(+), 1 deletions(-)
    create mode 100644 include/linux/timerlist.h
    create mode 100644 lib/timerlist.c

    diff --git a/include/linux/timerlist.h b/include/linux/timerlist.h
    new file mode 100644
    index 0000000..c46b28a
    --- /dev/null
    +++ b/include/linux/timerlist.h
    @@ -0,0 +1,37 @@
    +#ifndef _LINUX_TIMERLIST_H
    +#define _LINUX_TIMERLIST_H
    +
    +#include <linux/rbtree.h>
    +#include <linux/ktime.h>
    +
    +
    +struct timerlist_node {
    + struct rb_node node;
    + ktime_t expires;
    +};
    +
    +struct timerlist_head {
    + struct rb_root head;
    + struct timerlist_node *next;
    +};
    +
    +
    +extern void timerlist_add(struct timerlist_head *head,
    + struct timerlist_node *node);
    +extern void timerlist_del(struct timerlist_head *head,
    + struct timerlist_node *node);
    +extern struct timerlist_node *timerlist_getnext(struct timerlist_head *head);
    +extern struct timerlist_node *timerlist_iterate_next(
    + struct timerlist_node *node);
    +
    +static inline void timerlist_init(struct timerlist_node *node)
    +{
    + RB_CLEAR_NODE(&node->node);
    +}
    +
    +static inline void timerlist_init_head(struct timerlist_head *head)
    +{
    + head->head = RB_ROOT;
    + head->next = NULL;
    +}
    +#endif /* _LINUX_TIMERLIST_H */
    diff --git a/lib/Makefile b/lib/Makefile
    index e6a3763..8b475cf 100644
    --- a/lib/Makefile
    +++ b/lib/Makefile
    @@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS))
    endif

    lib-y := ctype.o string.o vsprintf.o cmdline.o \
    - rbtree.o radix-tree.o dump_stack.o \
    + rbtree.o radix-tree.o dump_stack.o timerlist.o\
    idr.o int_sqrt.o extable.o prio_tree.o \
    sha1.o irq_regs.o reciprocal_div.o argv_split.o \
    proportions.o prio_heap.o ratelimit.o show_mem.o \
    diff --git a/lib/timerlist.c b/lib/timerlist.c
    new file mode 100644
    index 0000000..9101b42
    --- /dev/null
    +++ b/lib/timerlist.c
    @@ -0,0 +1,118 @@
    +/*
    + * Generic Timer-list
    + *
    + * Manages a simple list of timers, ordered by expiration time.
    + * Uses rbtrees for quick list adds and expiration.
    + *
    + * NOTE: All of the following functions need to be serialized
    + * to avoid races. No locking is done by this libary code.
    + *
    + * 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
    + */
    +
    +#include <linux/timerlist.h>
    +#include <linux/rbtree.h>
    +
    +/**
    + * timerlist_add - Adds timer to timerlist.
    + *
    + * @head: head of timerlist
    + * @node: timer node to be added
    + *
    + * Adds the timer node to the timerlist, sorted by the
    + * node's expires value.
    + */
    +void timerlist_add(struct timerlist_head *head, struct timerlist_node *node)
    +{
    + struct rb_node **p = &head->head.rb_node;
    + struct rb_node *parent = NULL;
    + struct timerlist_node *ptr;
    +
    + /* Make sure we don't add nodes that are already added */
    + WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
    +
    + while (*p) {
    + parent = *p;
    + ptr = rb_entry(parent, struct timerlist_node, node);
    + if (node->expires.tv64 < ptr->expires.tv64)
    + p = &(*p)->rb_left;
    + else
    + p = &(*p)->rb_right;
    + }
    + rb_link_node(&node->node, parent, p);
    + rb_insert_color(&node->node, &head->head);
    +
    + if (!head->next || node->expires.tv64 < head->next->expires.tv64)
    + head->next = node;
    +}
    +
    +/**
    + * timerlist_del - Removes a timer from the timerlist.
    + *
    + * @head: head of timerlist
    + * @node: timer node to be removed
    + *
    + * Removes the timer node from the timerlist.
    + */
    +void timerlist_del(struct timerlist_head *head, struct timerlist_node *node)
    +{
    + WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
    +
    + /* update next pointer */
    + if (head->next == node) {
    + struct rb_node *rbn = rb_next(&node->node);
    +
    + head->next = rbn ?
    + rb_entry(rbn, struct timerlist_node, node) : NULL;
    + }
    + rb_erase(&node->node, &head->head);
    + RB_CLEAR_NODE(&node->node);
    +}
    +
    +
    +/**
    + * timerlist_getnext - Returns the timer with the earlies expiration time
    + *
    + * @head: head of timerlist
    + *
    + * Returns a pointer to the timer node that has the
    + * earliest expiration time.
    + */
    +struct timerlist_node *timerlist_getnext(struct timerlist_head *head)
    +{
    + return head->next;
    +}
    +
    +
    +/**
    + * timerlist_iterate_next - Returns the timer after the provided timer
    + *
    + * @node: Pointer to a timer.
    + *
    + * Provides the timer that is after the given node. This is used, when
    + * necessary, to iterate through the list of timers in a timer list
    + * without modifying the list.
    + */
    +struct timerlist_node *timerlist_iterate_next(struct timerlist_node *node)
    +{
    + struct rb_node *next;
    +
    + if (!node)
    + return NULL;
    + next = rb_next(&node->node);
    + if (!next)
    + return NULL;
    + return container_of(next, struct timerlist_node, node);
    +}
    --
    1.7.3.2.146.gca209


    \
     
     \ /
      Last update: 2011-01-06 03:21    [W:0.034 / U:58.872 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site