12 files changed, 298 insertions, 50 deletions

diff --git a/lib/Kconfig b/lib/Kconfig
index fa9bf2c06199..3116aa631af6 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -210,4 +210,7 @@ config GENERIC_ATOMIC64
 config LRU_CACHE
         tristate
 
+config AVERAGE
+        bool
+
 endmenu
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 28b42b9274d0..2d05adb98401 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -173,7 +173,8 @@ config LOCKUP_DETECTOR
           An NMI is generated every 60 seconds or so to check for hardlockups.
 
 config HARDLOCKUP_DETECTOR
-        def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI
+        def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI && \
+                 !ARCH_HAS_NMI_WATCHDOG
 
 config BOOTPARAM_SOFTLOCKUP_PANIC
         bool "Panic (Reboot) On Soft Lockups"
diff --git a/lib/Makefile b/lib/Makefile
index e6a3763b8212..d7b6e30a3a1e 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 timerqueue.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 \
@@ -106,6 +106,8 @@ obj-$(CONFIG_GENERIC_ATOMIC64) += atomic64.o
 
 obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o
 
+obj-$(CONFIG_AVERAGE) += average.o
+
 hostprogs-y     := gen_crc32table
 clean-files     := crc32table.h
 
diff --git a/lib/average.c b/lib/average.c
new file mode 100644
index 000000000000..5576c2841496
--- /dev/null
+++ b/lib/average.c
@@ -0,0 +1,61 @@
+/*
+ * lib/average.c
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2.  See the file COPYING for more details.
+ */
+
+#include <linux/module.h>
+#include <linux/average.h>
+#include <linux/bug.h>
+#include <linux/log2.h>
+
+/**
+ * DOC: Exponentially Weighted Moving Average (EWMA)
+ *
+ * These are generic functions for calculating Exponentially Weighted Moving
+ * Averages (EWMA). We keep a structure with the EWMA parameters and a scaled
+ * up internal representation of the average value to prevent rounding errors.
+ * The factor for scaling up and the exponential weight (or decay rate) have to
+ * be specified thru the init fuction. The structure should not be accessed
+ * directly but only thru the helper functions.
+ */
+
+/**
+ * ewma_init() - Initialize EWMA parameters
+ * @avg: Average structure
+ * @factor: Factor to use for the scaled up internal value. The maximum value
+ *      of averages can be ULONG_MAX/(factor*weight). For performance reasons
+ *      factor has to be a power of 2.
+ * @weight: Exponential weight, or decay rate. This defines how fast the
+ *      influence of older values decreases. For performance reasons weight has
+ *      to be a power of 2.
+ *
+ * Initialize the EWMA parameters for a given struct ewma @avg.
+ */
+void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
+{
+        WARN_ON(!is_power_of_2(weight) || !is_power_of_2(factor));
+
+        avg->weight = ilog2(weight);
+        avg->factor = ilog2(factor);
+        avg->internal = 0;
+}
+EXPORT_SYMBOL(ewma_init);
+
+/**
+ * ewma_add() - Exponentially weighted moving average (EWMA)
+ * @avg: Average structure
+ * @val: Current value
+ *
+ * Add a sample to the average.
+ */
+struct ewma *ewma_add(struct ewma *avg, unsigned long val)
+{
+        avg->internal = avg->internal  ?
+                (((avg->internal << avg->weight) - avg->internal) +
+                        (val << avg->factor)) >> avg->weight :
+                (val << avg->factor);
+        return avg;
+}
+EXPORT_SYMBOL(ewma_add);
diff --git a/lib/debug_locks.c b/lib/debug_locks.c
index 5bf0020b9248..b1c177307677 100644
--- a/lib/debug_locks.c
+++ b/lib/debug_locks.c
@@ -8,7 +8,6 @@
  *
  *  Copyright (C) 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
  */
-#include <linux/kernel.h>
 #include <linux/rwsem.h>
 #include <linux/mutex.h>
 #include <linux/module.h>
@@ -39,7 +38,6 @@ int debug_locks_off(void)
 {
         if (__debug_locks_off()) {
                 if (!debug_locks_silent) {
-                        oops_in_progress = 1;
                         console_verbose();
                         return 1;
                 }
diff --git a/lib/dynamic_debug.c b/lib/dynamic_debug.c
index 3094318bfea7..b335acb43be2 100644
--- a/lib/dynamic_debug.c
+++ b/lib/dynamic_debug.c
@@ -141,11 +141,10 @@ static void ddebug_change(const struct ddebug_query *query,
                         else if (!dp->flags)
                                 dt->num_enabled++;
                         dp->flags = newflags;
-                        if (newflags) {
-                                jump_label_enable(&dp->enabled);
-                        } else {
-                                jump_label_disable(&dp->enabled);
-                        }
+                        if (newflags)
+                                dp->enabled = 1;
+                        else
+                                dp->enabled = 0;
                         if (verbose)
                                 printk(KERN_INFO
                                         "ddebug: changed %s:%d [%s]%s %s\n",
diff --git a/lib/hexdump.c b/lib/hexdump.c
index 5d7a4802c562..b66b2bd67952 100644
--- a/lib/hexdump.c
+++ b/lib/hexdump.c
@@ -34,6 +34,22 @@ int hex_to_bin(char ch)
 EXPORT_SYMBOL(hex_to_bin);
 
 /**
+ * hex2bin - convert an ascii hexadecimal string to its binary representation
+ * @dst: binary result
+ * @src: ascii hexadecimal string
+ * @count: result length
+ */
+void hex2bin(u8 *dst, const char *src, size_t count)
+{
+        while (count--) {
+                *dst = hex_to_bin(*src++) << 4;
+                *dst += hex_to_bin(*src++);
+                dst++;
+        }
+}
+EXPORT_SYMBOL(hex2bin);
+
+/**
  * hex_dump_to_buffer - convert a blob of data to "hex ASCII" in memory
  * @buf: data blob to dump
  * @len: number of bytes in the @buf
diff --git a/lib/kref.c b/lib/kref.c
index d3d227a08a4b..3efb882b11db 100644
--- a/lib/kref.c
+++ b/lib/kref.c
@@ -62,6 +62,36 @@ int kref_put(struct kref *kref, void (*release)(struct kref *kref))
         return 0;
 }
 
+
+/**
+ * kref_sub - subtract a number of refcounts for object.
+ * @kref: object.
+ * @count: Number of recounts to subtract.
+ * @release: pointer to the function that will clean up the object when the
+ *           last reference to the object is released.
+ *           This pointer is required, and it is not acceptable to pass kfree
+ *           in as this function.
+ *
+ * Subtract @count from the refcount, and if 0, call release().
+ * Return 1 if the object was removed, otherwise return 0.  Beware, if this
+ * function returns 0, you still can not count on the kref from remaining in
+ * memory.  Only use the return value if you want to see if the kref is now
+ * gone, not present.
+ */
+int kref_sub(struct kref *kref, unsigned int count,
+             void (*release)(struct kref *kref))
+{
+        WARN_ON(release == NULL);
+        WARN_ON(release == (void (*)(struct kref *))kfree);
+
+        if (atomic_sub_and_test((int) count, &kref->refcount)) {
+                release(kref);
+                return 1;
+        }
+        return 0;
+}
+
 EXPORT_SYMBOL(kref_init);
 EXPORT_SYMBOL(kref_get);
 EXPORT_SYMBOL(kref_put);
+EXPORT_SYMBOL(kref_sub);
diff --git a/lib/nlattr.c b/lib/nlattr.c
index c4706eb98d3d..00e8a02681a6 100644
--- a/lib/nlattr.c
+++ b/lib/nlattr.c
@@ -15,7 +15,7 @@
 #include <linux/types.h>
 #include <net/netlink.h>
 
-static u16 nla_attr_minlen[NLA_TYPE_MAX+1] __read_mostly = {
+static const u16 nla_attr_minlen[NLA_TYPE_MAX+1] = {
         [NLA_U8]        = sizeof(u8),
         [NLA_U16]       = sizeof(u16),
         [NLA_U32]       = sizeof(u32),
@@ -23,7 +23,7 @@ static u16 nla_attr_minlen[NLA_TYPE_MAX+1] __read_mostly = {
         [NLA_NESTED]    = NLA_HDRLEN,
 };
 
-static int validate_nla(struct nlattr *nla, int maxtype,
+static int validate_nla(const struct nlattr *nla, int maxtype,
                         const struct nla_policy *policy)
 {
         const struct nla_policy *pt;
@@ -115,10 +115,10 @@ static int validate_nla(struct nlattr *nla, int maxtype,
  *
  * Returns 0 on success or a negative error code.
  */
-int nla_validate(struct nlattr *head, int len, int maxtype,
+int nla_validate(const struct nlattr *head, int len, int maxtype,
                  const struct nla_policy *policy)
 {
-        struct nlattr *nla;
+        const struct nlattr *nla;
         int rem, err;
 
         nla_for_each_attr(nla, head, len, rem) {
@@ -173,10 +173,10 @@ nla_policy_len(const struct nla_policy *p, int n)
  *
  * Returns 0 on success or a negative error code.
  */
-int nla_parse(struct nlattr *tb[], int maxtype, struct nlattr *head, int len,
-              const struct nla_policy *policy)
+int nla_parse(struct nlattr **tb, int maxtype, const struct nlattr *head,
+              int len, const struct nla_policy *policy)
 {
-        struct nlattr *nla;
+        const struct nlattr *nla;
         int rem, err;
 
         memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1));
@@ -191,7 +191,7 @@ int nla_parse(struct nlattr *tb[], int maxtype, struct nlattr *head, int len,
                                         goto errout;
                         }
 
-                        tb[type] = nla;
+                        tb[type] = (struct nlattr *)nla;
                 }
         }
 
@@ -212,14 +212,14 @@ errout:
  *
  * Returns the first attribute in the stream matching the specified type.
  */
-struct nlattr *nla_find(struct nlattr *head, int len, int attrtype)
+struct nlattr *nla_find(const struct nlattr *head, int len, int attrtype)
 {
-        struct nlattr *nla;
+        const struct nlattr *nla;
         int rem;
 
         nla_for_each_attr(nla, head, len, rem)
                 if (nla_type(nla) == attrtype)
-                        return nla;
+                        return (struct nlattr *)nla;
 
         return NULL;
 }
diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c
index 604678d7d06d..28f2c33c6b53 100644
--- a/lib/percpu_counter.c
+++ b/lib/percpu_counter.c
@@ -72,18 +72,16 @@ EXPORT_SYMBOL(percpu_counter_set);
 void __percpu_counter_add(struct percpu_counter *fbc, s64 amount, s32 batch)
 {
         s64 count;
-        s32 *pcount;
 
         preempt_disable();
-        pcount = this_cpu_ptr(fbc->counters);
-        count = *pcount + amount;
+        count = __this_cpu_read(*fbc->counters) + amount;
         if (count >= batch || count <= -batch) {
                 spin_lock(&fbc->lock);
                 fbc->count += count;
-                *pcount = 0;
+                __this_cpu_write(*fbc->counters, 0);
                 spin_unlock(&fbc->lock);
         } else {
-                *pcount = count;
+                __this_cpu_write(*fbc->counters, count);
         }
         preempt_enable();
 }
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 6f412ab4c24f..5086bb962b4d 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -82,6 +82,16 @@ struct radix_tree_preload {
 };
 static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
 
+static inline void *ptr_to_indirect(void *ptr)
+{
+        return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
+}
+
+static inline void *indirect_to_ptr(void *ptr)
+{
+        return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
+}
+
 static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
 {
         return root->gfp_mask & __GFP_BITS_MASK;
@@ -265,7 +275,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
                         return -ENOMEM;
 
                 /* Increase the height.  */
-                node->slots[0] = radix_tree_indirect_to_ptr(root->rnode);
+                node->slots[0] = indirect_to_ptr(root->rnode);
 
                 /* Propagate the aggregated tag info into the new root */
                 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
@@ -276,7 +286,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
                 newheight = root->height+1;
                 node->height = newheight;
                 node->count = 1;
-                node = radix_tree_ptr_to_indirect(node);
+                node = ptr_to_indirect(node);
                 rcu_assign_pointer(root->rnode, node);
                 root->height = newheight;
         } while (height > root->height);
@@ -309,7 +319,7 @@ int radix_tree_insert(struct radix_tree_root *root,
                         return error;
         }
 
-        slot = radix_tree_indirect_to_ptr(root->rnode);
+        slot = indirect_to_ptr(root->rnode);
 
         height = root->height;
         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
@@ -325,8 +335,7 @@ int radix_tree_insert(struct radix_tree_root *root,
                                 rcu_assign_pointer(node->slots[offset], slot);
                                 node->count++;
                         } else
-                                rcu_assign_pointer(root->rnode,
-                                        radix_tree_ptr_to_indirect(slot));
+                                rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
                 }
 
                 /* Go a level down */
@@ -374,7 +383,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
                         return NULL;
                 return is_slot ? (void *)&root->rnode : node;
         }
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         height = node->height;
         if (index > radix_tree_maxindex(height))
@@ -393,7 +402,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
                 height--;
         } while (height > 0);
 
-        return is_slot ? (void *)slot:node;
+        return is_slot ? (void *)slot : indirect_to_ptr(node);
 }
 
 /**
@@ -455,7 +464,7 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
         height = root->height;
         BUG_ON(index > radix_tree_maxindex(height));
 
-        slot = radix_tree_indirect_to_ptr(root->rnode);
+        slot = indirect_to_ptr(root->rnode);
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 
         while (height > 0) {
@@ -509,7 +518,7 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
 
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
         pathp->node = NULL;
-        slot = radix_tree_indirect_to_ptr(root->rnode);
+        slot = indirect_to_ptr(root->rnode);
 
         while (height > 0) {
                 int offset;
@@ -579,7 +588,7 @@ int radix_tree_tag_get(struct radix_tree_root *root,
 
         if (!radix_tree_is_indirect_ptr(node))
                 return (index == 0);
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         height = node->height;
         if (index > radix_tree_maxindex(height))
@@ -666,7 +675,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
         }
 
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-        slot = radix_tree_indirect_to_ptr(root->rnode);
+        slot = indirect_to_ptr(root->rnode);
 
         /*
          * we fill the path from (root->height - 2) to 0, leaving the index at
@@ -897,7 +906,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
                 results[0] = node;
                 return 1;
         }
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         max_index = radix_tree_maxindex(node->height);
 
@@ -916,7 +925,8 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
                         slot = *(((void ***)results)[ret + i]);
                         if (!slot)
                                 continue;
-                        results[ret + nr_found] = rcu_dereference_raw(slot);
+                        results[ret + nr_found] =
+                                indirect_to_ptr(rcu_dereference_raw(slot));
                         nr_found++;
                 }
                 ret += nr_found;
@@ -965,7 +975,7 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
                 results[0] = (void **)&root->rnode;
                 return 1;
         }
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         max_index = radix_tree_maxindex(node->height);
 
@@ -1090,7 +1100,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
                 results[0] = node;
                 return 1;
         }
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         max_index = radix_tree_maxindex(node->height);
 
@@ -1109,7 +1119,8 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
                         slot = *(((void ***)results)[ret + i]);
                         if (!slot)
                                 continue;
-                        results[ret + nr_found] = rcu_dereference_raw(slot);
+                        results[ret + nr_found] =
+                                indirect_to_ptr(rcu_dereference_raw(slot));
                         nr_found++;
                 }
                 ret += nr_found;
@@ -1159,7 +1170,7 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
                 results[0] = (void **)&root->rnode;
                 return 1;
         }
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         max_index = radix_tree_maxindex(node->height);
 
@@ -1195,7 +1206,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
                 void *newptr;
 
                 BUG_ON(!radix_tree_is_indirect_ptr(to_free));
-                to_free = radix_tree_indirect_to_ptr(to_free);
+                to_free = indirect_to_ptr(to_free);
 
                 /*
                  * The candidate node has more than one child, or its child
@@ -1208,16 +1219,39 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
 
                 /*
                  * We don't need rcu_assign_pointer(), since we are simply
-                 * moving the node from one part of the tree to another. If
-                 * it was safe to dereference the old pointer to it
+                 * moving the node from one part of the tree to another: if it
+                 * was safe to dereference the old pointer to it
                  * (to_free->slots[0]), it will be safe to dereference the new
-                 * one (root->rnode).
+                 * one (root->rnode) as far as dependent read barriers go.
                  */
                 newptr = to_free->slots[0];
                 if (root->height > 1)
-                        newptr = radix_tree_ptr_to_indirect(newptr);
+                        newptr = ptr_to_indirect(newptr);
                 root->rnode = newptr;
                 root->height--;
+
+                /*
+                 * We have a dilemma here. The node's slot[0] must not be
+                 * NULLed in case there are concurrent lookups expecting to
+                 * find the item. However if this was a bottom-level node,
+                 * then it may be subject to the slot pointer being visible
+                 * to callers dereferencing it. If item corresponding to
+                 * slot[0] is subsequently deleted, these callers would expect
+                 * their slot to become empty sooner or later.
+                 *
+                 * For example, lockless pagecache will look up a slot, deref
+                 * the page pointer, and if the page is 0 refcount it means it
+                 * was concurrently deleted from pagecache so try the deref
+                 * again. Fortunately there is already a requirement for logic
+                 * to retry the entire slot lookup -- the indirect pointer
+                 * problem (replacing direct root node with an indirect pointer
+                 * also results in a stale slot). So tag the slot as indirect
+                 * to force callers to retry.
+                 */
+                if (root->height == 0)
+                        *((unsigned long *)&to_free->slots[0]) |=
+                                                RADIX_TREE_INDIRECT_PTR;
+
                 radix_tree_node_free(to_free);
         }
 }
@@ -1254,7 +1288,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
                 root->rnode = NULL;
                 goto out;
         }
-        slot = radix_tree_indirect_to_ptr(slot);
+        slot = indirect_to_ptr(slot);
 
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
         pathp->node = NULL;
@@ -1296,8 +1330,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
                         radix_tree_node_free(to_free);
 
                 if (pathp->node->count) {
-                        if (pathp->node ==
-                                        radix_tree_indirect_to_ptr(root->rnode))
+                        if (pathp->node == indirect_to_ptr(root->rnode))
                                 radix_tree_shrink(root);
                         goto out;
                 }
diff --git a/lib/timerqueue.c b/lib/timerqueue.c
new file mode 100644
index 000000000000..e3a1050e6820
--- /dev/null
+++ b/lib/timerqueue.c
@@ -0,0 +1,107 @@
+/*
+ *  Generic Timer-queue
+ *
+ *  Manages a simple queue 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/timerqueue.h>
+#include <linux/rbtree.h>
+#include <linux/module.h>
+
+/**
+ * timerqueue_add - Adds timer to timerqueue.
+ *
+ * @head: head of timerqueue
+ * @node: timer node to be added
+ *
+ * Adds the timer node to the timerqueue, sorted by the
+ * node's expires value.
+ */
+void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
+{
+        struct rb_node **p = &head->head.rb_node;
+        struct rb_node *parent = NULL;
+        struct timerqueue_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 timerqueue_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;
+}
+EXPORT_SYMBOL_GPL(timerqueue_add);
+
+/**
+ * timerqueue_del - Removes a timer from the timerqueue.
+ *
+ * @head: head of timerqueue
+ * @node: timer node to be removed
+ *
+ * Removes the timer node from the timerqueue.
+ */
+void timerqueue_del(struct timerqueue_head *head, struct timerqueue_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 timerqueue_node, node) : NULL;
+        }
+        rb_erase(&node->node, &head->head);
+        RB_CLEAR_NODE(&node->node);
+}
+EXPORT_SYMBOL_GPL(timerqueue_del);
+
+/**
+ * timerqueue_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 timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
+{
+        struct rb_node *next;
+
+        if (!node)
+                return NULL;
+        next = rb_next(&node->node);
+        if (!next)
+                return NULL;
+        return container_of(next, struct timerqueue_node, node);
+}
+EXPORT_SYMBOL_GPL(timerqueue_iterate_next);