11 files changed, 392 insertions, 18 deletions

diff --git a/lib/Kconfig b/lib/Kconfig
index eeb429a52152..e43197efeb9c 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -72,6 +72,9 @@ config TEXTSEARCH
 config TEXTSEARCH_KMP
         tristate
 
+config TEXTSEARCH_BM
+        tristate
+
 config TEXTSEARCH_FSM
         tristate
 
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 0c421295e613..299f7f3b5b08 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -141,7 +141,7 @@ config DEBUG_IOREMAP
 
 config DEBUG_FS
         bool "Debug Filesystem"
-        depends on DEBUG_KERNEL
+        depends on DEBUG_KERNEL && SYSFS
         help
           debugfs is a virtual file system that kernel developers use to put
           debugging files into.  Enable this option to be able to read and
diff --git a/lib/Makefile b/lib/Makefile
index beed1585294c..3e2bd0df23bb 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -5,11 +5,11 @@
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
          bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
          idr.o div64.o int_sqrt.o bitmap.o extable.o prio_tree.o \
-         sha1.o halfmd4.o
+         sha1.o
 
 lib-y   += kobject.o kref.o kobject_uevent.o klist.o
 
-obj-y += sort.o parser.o
+obj-y += sort.o parser.o halfmd4.o
 
 ifeq ($(CONFIG_DEBUG_KOBJECT),y)
 CFLAGS_kobject.o += -DDEBUG
@@ -18,6 +18,7 @@ endif
 
 lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
+lib-$(CONFIG_SEMAPHORE_SLEEPERS) += semaphore-sleepers.o
 lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
 obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
 obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
@@ -38,6 +39,7 @@ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
 
 obj-$(CONFIG_TEXTSEARCH) += textsearch.o
 obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
+obj-$(CONFIG_TEXTSEARCH_BM) += ts_bm.o
 obj-$(CONFIG_TEXTSEARCH_FSM) += ts_fsm.o
 
 hostprogs-y     := gen_crc32table
diff --git a/lib/crc32.c b/lib/crc32.c
index 58b222783f9c..065198f98b3f 100644
--- a/lib/crc32.c
+++ b/lib/crc32.c
@@ -473,7 +473,7 @@ static u32 test_step(u32 init, unsigned char *buf, size_t len)
         init = bitreverse(init);
         crc2 = bitreverse(crc1);
         if (crc1 != bitreverse(crc2))
-                printf("\nBit reversal fail: 0x%08x -> %0x08x -> 0x%08x\n",
+                printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n",
                        crc1, crc2, bitreverse(crc2));
         crc1 = crc32_le(init, buf, len);
         if (crc1 != crc2)
diff --git a/lib/idr.c b/lib/idr.c
index c5be889de449..6415d053e2bf 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -207,7 +207,7 @@ build_up:
 }
 
 /**
- * idr_get_new_above - allocate new idr entry above a start id
+ * idr_get_new_above - allocate new idr entry above or equal to a start id
  * @idp: idr handle
  * @ptr: pointer you want associated with the ide
  * @start_id: id to start search at
diff --git a/lib/inflate.c b/lib/inflate.c
index 75e7d303c72e..6db6e98d1637 100644
--- a/lib/inflate.c
+++ b/lib/inflate.c
@@ -326,7 +326,7 @@ DEBG("huft1 ");
   {
     *t = (struct huft *)NULL;
     *m = 0;
-    return 0;
+    return 2;
   }
 
 DEBG("huft2 ");
@@ -374,6 +374,7 @@ DEBG("huft5 ");
     if ((j = *p++) != 0)
       v[x[j]++] = i;
   } while (++i < n);
+  n = x[g];                   /* set n to length of v */
 
 DEBG("h6 ");
 
@@ -410,12 +411,13 @@ DEBG1("1 ");
 DEBG1("2 ");
           f -= a + 1;           /* deduct codes from patterns left */
           xp = c + k;
-          while (++j < z)       /* try smaller tables up to z bits */
-          {
-            if ((f <<= 1) <= *++xp)
-              break;            /* enough codes to use up j bits */
-            f -= *xp;           /* else deduct codes from patterns */
-          }
+          if (j < z)
+            while (++j < z)       /* try smaller tables up to z bits */
+            {
+              if ((f <<= 1) <= *++xp)
+                break;            /* enough codes to use up j bits */
+              f -= *xp;           /* else deduct codes from patterns */
+            }
         }
 DEBG1("3 ");
         z = 1 << j;             /* table entries for j-bit table */
diff --git a/lib/klist.c b/lib/klist.c
index 738ab810160a..a70c836c5c4c 100644
--- a/lib/klist.c
+++ b/lib/klist.c
@@ -79,11 +79,11 @@ static void klist_node_init(struct klist * k, struct klist_node * n)
 
 /**
  *      klist_add_head - Initialize a klist_node and add it to front.
- *      @k:     klist it's going on.
  *      @n:     node we're adding.
+ *      @k:     klist it's going on.
  */
 
-void klist_add_head(struct klist * k, struct klist_node * n)
+void klist_add_head(struct klist_node * n, struct klist * k)
 {
         klist_node_init(k, n);
         add_head(k, n);
@@ -94,11 +94,11 @@ EXPORT_SYMBOL_GPL(klist_add_head);
 
 /**
  *      klist_add_tail - Initialize a klist_node and add it to back.
- *      @k:     klist it's going on.
  *      @n:     node we're adding.
+ *      @k:     klist it's going on.
  */
 
-void klist_add_tail(struct klist * k, struct klist_node * n)
+void klist_add_tail(struct klist_node * n, struct klist * k)
 {
         klist_node_init(k, n);
         add_tail(k, n);
diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c
index 8e49d21057e4..04ca4429ddfa 100644
--- a/lib/kobject_uevent.c
+++ b/lib/kobject_uevent.c
@@ -93,6 +93,7 @@ static int send_uevent(const char *signal, const char *obj,
                 }
         }
 
+        NETLINK_CB(skb).dst_group = 1;
         return netlink_broadcast(uevent_sock, skb, 0, 1, gfp_mask);
 }
 
@@ -153,7 +154,8 @@ EXPORT_SYMBOL_GPL(kobject_uevent_atomic);
 
 static int __init kobject_uevent_init(void)
 {
-        uevent_sock = netlink_kernel_create(NETLINK_KOBJECT_UEVENT, NULL);
+        uevent_sock = netlink_kernel_create(NETLINK_KOBJECT_UEVENT, 1, NULL,
+                                            THIS_MODULE);
 
         if (!uevent_sock) {
                 printk(KERN_ERR
diff --git a/lib/semaphore-sleepers.c b/lib/semaphore-sleepers.c
new file mode 100644
index 000000000000..4d5f18889fa5
--- /dev/null
+++ b/lib/semaphore-sleepers.c
@@ -0,0 +1,177 @@
+/*
+ * i386 and x86-64 semaphore implementation.
+ *
+ * (C) Copyright 1999 Linus Torvalds
+ *
+ * Portions Copyright 1999 Red Hat, Inc.
+ *
+ *      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.
+ *
+ * rw semaphores implemented November 1999 by Benjamin LaHaise <bcrl@kvack.org>
+ */
+#include <linux/config.h>
+#include <linux/sched.h>
+#include <linux/err.h>
+#include <linux/init.h>
+#include <asm/semaphore.h>
+
+/*
+ * Semaphores are implemented using a two-way counter:
+ * The "count" variable is decremented for each process
+ * that tries to acquire the semaphore, while the "sleeping"
+ * variable is a count of such acquires.
+ *
+ * Notably, the inline "up()" and "down()" functions can
+ * efficiently test if they need to do any extra work (up
+ * needs to do something only if count was negative before
+ * the increment operation.
+ *
+ * "sleeping" and the contention routine ordering is protected
+ * by the spinlock in the semaphore's waitqueue head.
+ *
+ * Note that these functions are only called when there is
+ * contention on the lock, and as such all this is the
+ * "non-critical" part of the whole semaphore business. The
+ * critical part is the inline stuff in <asm/semaphore.h>
+ * where we want to avoid any extra jumps and calls.
+ */
+
+/*
+ * Logic:
+ *  - only on a boundary condition do we need to care. When we go
+ *    from a negative count to a non-negative, we wake people up.
+ *  - when we go from a non-negative count to a negative do we
+ *    (a) synchronize with the "sleeper" count and (b) make sure
+ *    that we're on the wakeup list before we synchronize so that
+ *    we cannot lose wakeup events.
+ */
+
+fastcall void __up(struct semaphore *sem)
+{
+        wake_up(&sem->wait);
+}
+
+fastcall void __sched __down(struct semaphore * sem)
+{
+        struct task_struct *tsk = current;
+        DECLARE_WAITQUEUE(wait, tsk);
+        unsigned long flags;
+
+        tsk->state = TASK_UNINTERRUPTIBLE;
+        spin_lock_irqsave(&sem->wait.lock, flags);
+        add_wait_queue_exclusive_locked(&sem->wait, &wait);
+
+        sem->sleepers++;
+        for (;;) {
+                int sleepers = sem->sleepers;
+
+                /*
+                 * Add "everybody else" into it. They aren't
+                 * playing, because we own the spinlock in
+                 * the wait_queue_head.
+                 */
+                if (!atomic_add_negative(sleepers - 1, &sem->count)) {
+                        sem->sleepers = 0;
+                        break;
+                }
+                sem->sleepers = 1;      /* us - see -1 above */
+                spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+                schedule();
+
+                spin_lock_irqsave(&sem->wait.lock, flags);
+                tsk->state = TASK_UNINTERRUPTIBLE;
+        }
+        remove_wait_queue_locked(&sem->wait, &wait);
+        wake_up_locked(&sem->wait);
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+        tsk->state = TASK_RUNNING;
+}
+
+fastcall int __sched __down_interruptible(struct semaphore * sem)
+{
+        int retval = 0;
+        struct task_struct *tsk = current;
+        DECLARE_WAITQUEUE(wait, tsk);
+        unsigned long flags;
+
+        tsk->state = TASK_INTERRUPTIBLE;
+        spin_lock_irqsave(&sem->wait.lock, flags);
+        add_wait_queue_exclusive_locked(&sem->wait, &wait);
+
+        sem->sleepers++;
+        for (;;) {
+                int sleepers = sem->sleepers;
+
+                /*
+                 * With signals pending, this turns into
+                 * the trylock failure case - we won't be
+                 * sleeping, and we* can't get the lock as
+                 * it has contention. Just correct the count
+                 * and exit.
+                 */
+                if (signal_pending(current)) {
+                        retval = -EINTR;
+                        sem->sleepers = 0;
+                        atomic_add(sleepers, &sem->count);
+                        break;
+                }
+
+                /*
+                 * Add "everybody else" into it. They aren't
+                 * playing, because we own the spinlock in
+                 * wait_queue_head. The "-1" is because we're
+                 * still hoping to get the semaphore.
+                 */
+                if (!atomic_add_negative(sleepers - 1, &sem->count)) {
+                        sem->sleepers = 0;
+                        break;
+                }
+                sem->sleepers = 1;      /* us - see -1 above */
+                spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+                schedule();
+
+                spin_lock_irqsave(&sem->wait.lock, flags);
+                tsk->state = TASK_INTERRUPTIBLE;
+        }
+        remove_wait_queue_locked(&sem->wait, &wait);
+        wake_up_locked(&sem->wait);
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+        tsk->state = TASK_RUNNING;
+        return retval;
+}
+
+/*
+ * Trylock failed - make sure we correct for
+ * having decremented the count.
+ *
+ * We could have done the trylock with a
+ * single "cmpxchg" without failure cases,
+ * but then it wouldn't work on a 386.
+ */
+fastcall int __down_trylock(struct semaphore * sem)
+{
+        int sleepers;
+        unsigned long flags;
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+        sleepers = sem->sleepers + 1;
+        sem->sleepers = 0;
+
+        /*
+         * Add "everybody else" and us into it. They aren't
+         * playing, because we own the spinlock in the
+         * wait_queue_head.
+         */
+        if (!atomic_add_negative(sleepers, &sem->count)) {
+                wake_up_locked(&sem->wait);
+        }
+
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+        return 1;
+}
diff --git a/lib/ts_bm.c b/lib/ts_bm.c
new file mode 100644
index 000000000000..2cc79112ecc3
--- /dev/null
+++ b/lib/ts_bm.c
@@ -0,0 +1,185 @@
+/*
+ * lib/ts_bm.c          Boyer-Moore text search implementation
+ *
+ *              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.
+ *
+ * Authors:     Pablo Neira Ayuso <pablo@eurodev.net>
+ *
+ * ==========================================================================
+ * 
+ *   Implements Boyer-Moore string matching algorithm:
+ *
+ *   [1] A Fast String Searching Algorithm, R.S. Boyer and Moore.
+ *       Communications of the Association for Computing Machinery, 
+ *       20(10), 1977, pp. 762-772.
+ *       http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
+ *
+ *   [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004
+ *       http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
+ *
+ *   Note: Since Boyer-Moore (BM) performs searches for matchings from right 
+ *   to left, it's still possible that a matching could be spread over 
+ *   multiple blocks, in that case this algorithm won't find any coincidence.
+ *   
+ *   If you're willing to ensure that such thing won't ever happen, use the
+ *   Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose 
+ *   the proper string search algorithm depending on your setting. 
+ *
+ *   Say you're using the textsearch infrastructure for filtering, NIDS or 
+ *   any similar security focused purpose, then go KMP. Otherwise, if you 
+ *   really care about performance, say you're classifying packets to apply
+ *   Quality of Service (QoS) policies, and you don't mind about possible
+ *   matchings spread over multiple fragments, then go BM.
+ */
+
+#include <linux/config.h>
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/types.h>
+#include <linux/string.h>
+#include <linux/textsearch.h>
+
+/* Alphabet size, use ASCII */
+#define ASIZE 256
+
+#if 0
+#define DEBUGP printk
+#else
+#define DEBUGP(args, format...)
+#endif
+
+struct ts_bm
+{
+        u8 *            pattern;
+        unsigned int    patlen;
+        unsigned int    bad_shift[ASIZE];
+        unsigned int    good_shift[0];
+};
+
+static unsigned int bm_find(struct ts_config *conf, struct ts_state *state)
+{
+        struct ts_bm *bm = ts_config_priv(conf);
+        unsigned int i, text_len, consumed = state->offset;
+        const u8 *text;
+        int shift = bm->patlen, bs;
+
+        for (;;) {
+                text_len = conf->get_next_block(consumed, &text, conf, state);
+
+                if (unlikely(text_len == 0))
+                        break;
+
+                while (shift < text_len) {
+                        DEBUGP("Searching in position %d (%c)\n", 
+                                shift, text[shift]);
+                        for (i = 0; i < bm->patlen; i++) 
+                             if (text[shift-i] != bm->pattern[bm->patlen-1-i])
+                                     goto next;
+
+                        /* London calling... */
+                        DEBUGP("found!\n");
+                        return consumed += (shift-(bm->patlen-1));
+
+next:                   bs = bm->bad_shift[text[shift-i]];
+
+                        /* Now jumping to... */
+                        shift = max_t(int, shift-i+bs, shift+bm->good_shift[i]);
+                }
+                consumed += text_len;
+        }
+
+        return UINT_MAX;
+}
+
+static void compute_prefix_tbl(struct ts_bm *bm, const u8 *pattern,
+                               unsigned int len)
+{
+        int i, j, ended, l[ASIZE];
+
+        for (i = 0; i < ASIZE; i++)
+                bm->bad_shift[i] = len;
+        for (i = 0; i < len - 1; i++)
+                bm->bad_shift[pattern[i]] = len - 1 - i;
+
+        /* Compute the good shift array, used to match reocurrences 
+         * of a subpattern */
+        for (i = 1; i < bm->patlen; i++) {
+                for (j = 0; j < bm->patlen && bm->pattern[bm->patlen - 1 - j]
+                                == bm->pattern[bm->patlen - 1 - i - j]; j++);
+                l[i] = j;
+        }  
+
+        bm->good_shift[0] = 1;
+        for (i = 1; i < bm->patlen; i++)
+                bm->good_shift[i] = bm->patlen;
+        for (i = bm->patlen - 1; i > 0; i--)
+                bm->good_shift[l[i]] = i;
+        ended = 0;
+        for (i = 0; i < bm->patlen; i++) {
+                if (l[i] == bm->patlen - 1 - i)
+                        ended = i;
+                if (ended)
+                        bm->good_shift[i] = ended;
+        }
+}
+
+static struct ts_config *bm_init(const void *pattern, unsigned int len,
+                                 int gfp_mask)
+{
+        struct ts_config *conf;
+        struct ts_bm *bm;
+        unsigned int prefix_tbl_len = len * sizeof(unsigned int);
+        size_t priv_size = sizeof(*bm) + len + prefix_tbl_len;
+
+        conf = alloc_ts_config(priv_size, gfp_mask);
+        if (IS_ERR(conf))
+                return conf;
+
+        bm = ts_config_priv(conf);
+        bm->patlen = len;
+        bm->pattern = (u8 *) bm->good_shift + prefix_tbl_len;
+        compute_prefix_tbl(bm, pattern, len);
+        memcpy(bm->pattern, pattern, len);
+
+        return conf;
+}
+
+static void *bm_get_pattern(struct ts_config *conf)
+{
+        struct ts_bm *bm = ts_config_priv(conf);
+        return bm->pattern;
+}
+
+static unsigned int bm_get_pattern_len(struct ts_config *conf)
+{
+        struct ts_bm *bm = ts_config_priv(conf);
+        return bm->patlen;
+}
+
+static struct ts_ops bm_ops = {
+        .name             = "bm",
+        .find             = bm_find,
+        .init             = bm_init,
+        .get_pattern      = bm_get_pattern,
+        .get_pattern_len  = bm_get_pattern_len,
+        .owner            = THIS_MODULE,
+        .list             = LIST_HEAD_INIT(bm_ops.list)
+};
+
+static int __init init_bm(void)
+{
+        return textsearch_register(&bm_ops);
+}
+
+static void __exit exit_bm(void)
+{
+        textsearch_unregister(&bm_ops);
+}
+
+MODULE_LICENSE("GPL");
+
+module_init(init_bm);
+module_exit(exit_bm);
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index a9bda0a361f3..e4e9031dd9c3 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -269,6 +269,7 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args)
         int qualifier;          /* 'h', 'l', or 'L' for integer fields */
                                 /* 'z' support added 23/7/1999 S.H.    */
                                 /* 'z' changed to 'Z' --davidm 1/25/99 */
+                                /* 't' added for ptrdiff_t */
 
         /* Reject out-of-range values early */
         if (unlikely((int) size < 0)) {
@@ -339,7 +340,7 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args)
                 /* get the conversion qualifier */
                 qualifier = -1;
                 if (*fmt == 'h' || *fmt == 'l' || *fmt == 'L' ||
-                    *fmt =='Z' || *fmt == 'z') {
+                    *fmt =='Z' || *fmt == 'z' || *fmt == 't') {
                         qualifier = *fmt;
                         ++fmt;
                         if (qualifier == 'l' && *fmt == 'l') {
@@ -467,6 +468,8 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args)
                                 num = (signed long) num;
                 } else if (qualifier == 'Z' || qualifier == 'z') {
                         num = va_arg(args, size_t);
+                } else if (qualifier == 't') {
+                        num = va_arg(args, ptrdiff_t);
                 } else if (qualifier == 'h') {
                         num = (unsigned short) va_arg(args, int);
                         if (flags & SIGN)