1 files changed, 69 insertions, 37 deletions

diff --git a/kernel/posix-timers.c b/kernel/posix-timers.c
index 2a2e173d0a7a..34d75926b843 100644
--- a/kernel/posix-timers.c
+++ b/kernel/posix-timers.c
@@ -40,38 +40,31 @@
 #include <linux/list.h>
 #include <linux/init.h>
 #include <linux/compiler.h>
-#include <linux/idr.h>
+#include <linux/hash.h>
 #include <linux/posix-clock.h>
 #include <linux/posix-timers.h>
 #include <linux/syscalls.h>
 #include <linux/wait.h>
 #include <linux/workqueue.h>
 #include <linux/export.h>
+#include <linux/hashtable.h>
 
 /*
- * Management arrays for POSIX timers.   Timers are kept in slab memory
- * Timer ids are allocated by an external routine that keeps track of the
- * id and the timer.  The external interface is:
- *
- * void *idr_find(struct idr *idp, int id);           to find timer_id <id>
- * int idr_get_new(struct idr *idp, void *ptr);       to get a new id and
- *                                                    related it to <ptr>
- * void idr_remove(struct idr *idp, int id);          to release <id>
- * void idr_init(struct idr *idp);                    to initialize <idp>
- *                                                    which we supply.
- * The idr_get_new *may* call slab for more memory so it must not be
- * called under a spin lock.  Likewise idr_remore may release memory
- * (but it may be ok to do this under a lock...).
- * idr_find is just a memory look up and is quite fast.  A -1 return
- * indicates that the requested id does not exist.
+ * Management arrays for POSIX timers. Timers are now kept in static hash table
+ * with 512 entries.
+ * Timer ids are allocated by local routine, which selects proper hash head by
+ * key, constructed from current->signal address and per signal struct counter.
+ * This keeps timer ids unique per process, but now they can intersect between
+ * processes.
  */
 
 /*
  * Lets keep our timers in a slab cache :-)
  */
 static struct kmem_cache *posix_timers_cache;
-static struct idr posix_timers_id;
-static DEFINE_SPINLOCK(idr_lock);
+
+static DEFINE_HASHTABLE(posix_timers_hashtable, 9);
+static DEFINE_SPINLOCK(hash_lock);
 
 /*
  * we assume that the new SIGEV_THREAD_ID shares no bits with the other
@@ -152,6 +145,57 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags);
         __timr;                                                            \
 })
 
+static int hash(struct signal_struct *sig, unsigned int nr)
+{
+        return hash_32(hash32_ptr(sig) ^ nr, HASH_BITS(posix_timers_hashtable));
+}
+
+static struct k_itimer *__posix_timers_find(struct hlist_head *head,
+                                            struct signal_struct *sig,
+                                            timer_t id)
+{
+        struct hlist_node *node;
+        struct k_itimer *timer;
+
+        hlist_for_each_entry_rcu(timer, head, t_hash) {
+                if ((timer->it_signal == sig) && (timer->it_id == id))
+                        return timer;
+        }
+        return NULL;
+}
+
+static struct k_itimer *posix_timer_by_id(timer_t id)
+{
+        struct signal_struct *sig = current->signal;
+        struct hlist_head *head = &posix_timers_hashtable[hash(sig, id)];
+
+        return __posix_timers_find(head, sig, id);
+}
+
+static int posix_timer_add(struct k_itimer *timer)
+{
+        struct signal_struct *sig = current->signal;
+        int first_free_id = sig->posix_timer_id;
+        struct hlist_head *head;
+        int ret = -ENOENT;
+
+        do {
+                spin_lock(&hash_lock);
+                head = &posix_timers_hashtable[hash(sig, sig->posix_timer_id)];
+                if (!__posix_timers_find(head, sig, sig->posix_timer_id)) {
+                        hlist_add_head_rcu(&timer->t_hash, head);
+                        ret = sig->posix_timer_id;
+                }
+                if (++sig->posix_timer_id < 0)
+                        sig->posix_timer_id = 0;
+                if ((sig->posix_timer_id == first_free_id) && (ret == -ENOENT))
+                        /* Loop over all possible ids completed */
+                        ret = -EAGAIN;
+                spin_unlock(&hash_lock);
+        } while (ret == -ENOENT);
+        return ret;
+}
+
 static inline void unlock_timer(struct k_itimer *timr, unsigned long flags)
 {
         spin_unlock_irqrestore(&timr->it_lock, flags);
@@ -298,7 +342,6 @@ static __init int init_posix_timers(void)
         posix_timers_cache = kmem_cache_create("posix_timers_cache",
                                         sizeof (struct k_itimer), 0, SLAB_PANIC,
                                         NULL);
-        idr_init(&posix_timers_id);
         return 0;
 }
 
@@ -520,9 +563,9 @@ static void release_posix_timer(struct k_itimer *tmr, int it_id_set)
 {
         if (it_id_set) {
                 unsigned long flags;
-                spin_lock_irqsave(&idr_lock, flags);
-                idr_remove(&posix_timers_id, tmr->it_id);
-                spin_unlock_irqrestore(&idr_lock, flags);
+                spin_lock_irqsave(&hash_lock, flags);
+                hlist_del_rcu(&tmr->t_hash);
+                spin_unlock_irqrestore(&hash_lock, flags);
         }
         put_pid(tmr->it_pid);
         sigqueue_free(tmr->sigq);
@@ -568,22 +611,11 @@ SYSCALL_DEFINE3(timer_create, const clockid_t, which_clock,
                 return -EAGAIN;
 
         spin_lock_init(&new_timer->it_lock);
-
-        idr_preload(GFP_KERNEL);
-        spin_lock_irq(&idr_lock);
-        error = idr_alloc(&posix_timers_id, new_timer, 0, 0, GFP_NOWAIT);
-        spin_unlock_irq(&idr_lock);
-        idr_preload_end();
-        if (error < 0) {
-                /*
-                 * Weird looking, but we return EAGAIN if the IDR is
-                 * full (proper POSIX return value for this)
-                 */
-                if (error == -ENOSPC)
-                        error = -EAGAIN;
+        new_timer_id = posix_timer_add(new_timer);
+        if (new_timer_id < 0) {
+                error = new_timer_id;
                 goto out;
         }
-        new_timer_id = error;
 
         it_id_set = IT_ID_SET;
         new_timer->it_id = (timer_t) new_timer_id;
@@ -661,7 +693,7 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
                 return NULL;
 
         rcu_read_lock();
-        timr = idr_find(&posix_timers_id, (int)timer_id);
+        timr = posix_timer_by_id(timer_id);
         if (timr) {
                 spin_lock_irqsave(&timr->it_lock, *flags);
                 if (timr->it_signal == current->signal) {