[PATCH] POSIX clocks & timers

This is version 23 or so of the POSIX timer code.

Internal changelog:

 - Changed the signals code to match the new order of things.  Also the
   new xtime_lock code needed to be picked up.  It made some things a lot
   simpler.

 - Fixed a spin lock hand off problem in locking timers (thanks
   to Randy).

 - Fixed nanosleep to test for out of bound nanoseconds
   (thanks to Julie).

 - Fixed a couple of id deallocation bugs that left old ids
   laying around (hey I get this one).

 - This version has a new timer id manager.  Andrew Morton
   suggested elimination of recursion (done) and I added code
   to allow it to release unused nodes.  The prior version only
   released the leaf nodes.  (The id manager uses radix tree
   type nodes.)  Also added is a reuse count so ids will not
   repeat for at least 256 alloc/ free cycles.

 - The changes for the new sys_call restart now allow one
   restart function to handle both nanosleep and clock_nanosleep.
   Saves a bit of code, nice.

 - All the requested changes and Lindent too :).

 - I also broke clock_nanosleep() apart much the same way
   nanosleep() was with the 2.5.50-bk5 changes.

TIMER STORMS

The POSIX clocks and timers code prevents "timer storms" by
not putting repeating timers back in the timer list until
the signal is delivered for the prior expiry.  Timer events
missed by this delay are accounted for in the timer overrun
count.  The net result is MUCH lower system overhead while
presenting the same info to the user as would be the case if
an interrupt and timer processing were required for each
increment in the overrun count.

1 files changed, 63 insertions, 0 deletions

diff --git a/include/linux/idr.h b/include/linux/idr.h
new file mode 100644
index 000000000000..40861ba1114c
--- /dev/null
+++ b/include/linux/idr.h
@@ -0,0 +1,63 @@
+/*
+ * include/linux/id.h
+ * 
+ * 2002-10-18  written by Jim Houston jim.houston@ccur.com
+ *	Copyright (C) 2002 by Concurrent Computer Corporation
+ *	Distributed under the GNU GPL license version 2.
+ *
+ * Small id to pointer translation service avoiding fixed sized
+ * tables.
+ */
+#include <linux/types.h>
+#include <asm/bitops.h>
+
+#define RESERVED_ID_BITS 8
+
+#if     BITS_PER_LONG == 32
+#define IDR_BITS 5
+#define IDR_FULL 0xffffffff
+#elif BITS_PER_LONG == 64
+#define IDR_BITS 6
+#define IDR_FULL 0xffffffffffffffff
+#else
+#error "BITS_PER_LONG is not 32 or 64"
+#endif
+
+#define IDR_MASK ((1 << IDR_BITS)-1)
+
+/* Leave the possibility of an incomplete final layer */
+#define MAX_LEVEL (BITS_PER_LONG - RESERVED_ID_BITS + IDR_BITS - 1) / IDR_BITS
+#define MAX_ID_SHIFT (BITS_PER_LONG - RESERVED_ID_BITS)
+#define MAX_ID_BIT (1 << MAX_ID_SHIFT)
+#define MAX_ID_MASK (MAX_ID_BIT - 1)
+
+/* Number of id_layer structs to leave in free list */
+#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
+
+struct idr_layer {
+	unsigned long	        bitmap;     // A zero bit means "space here"
+	int                     count;      // When zero, we can release it
+	struct idr_layer       *ary[1<<IDR_BITS];
+};
+
+struct idr {
+	struct idr_layer *top;
+	int		  layers;
+	int		  count;
+	struct idr_layer *id_free;
+	int               id_free_cnt;
+	spinlock_t        lock;
+};
+
+/*
+ * This is what we export.
+ */
+
+void *idr_find(struct idr *idp, int id);
+int idr_pre_get(struct idr *idp);
+int idr_get_new(struct idr *idp, void *ptr);
+void idr_remove(struct idr *idp, int id);
+void idr_init(struct idr *idp);
+
+extern kmem_cache_t *idr_layer_cache;
+