POSIX clocks & timers - more choices

Hi Everyone,

The attached files are an experimental implementation of the Posix timers. If you want to play with it, you need to install George Anzinger's latest patch and layer these files on top.

I have been working with George's patch since March, and I'm quite happy with it. I would like to see it in the 2.5 tree!

Of course that doesn't stop me from wanting to play with some variation on the theme. Linus complained about the partial ticks but has not said what would make the patch acceptable. Perhaps some new code and an enthusiastic discussion would help?

The attached files include:

- A new queue just for Posix timers and code to
handle expiring timers. This supports high resolution without having to change the existing jiffie based timers.

I implemented this priority queue as a sort list with a rbtree to index the list. It is deterministic and fast.

- Change to use the slab allocator. This removes
the CONFIG option for the maximum number of timers.

- A new id allocator/lookup mechanism based on a
radix tree. It includes a bitmap to summarize the portion of the tree which is in use. Currently the Posix timers patch reuses the id immediately.

- I keep the timers in seconds and nano-seconds.
I'm hoping that the system time keeping will sort itself out and the Posix timers can just be a consumer. Posix timers need two clocks - the time since boot and the wall clock time.

Most of this code are experiments I have been playing with in user space. I pulled this together in the last couple days, and it passes some of the tests in George's support package. I have it wired into the normal timers with an add_timer

Jim Houston - Concurrent Computer Corp.

NOTE!! The attached "patch" is not realy a patch its complete files. It was created by diff'ing against an empty directory.

diff -urN empty/include/linux/id.h new/include/linux/id.h
@@ -0,0 +1,46 @@
+/*
+ * include/linux/id.h
+ * 
+ * 2002-10-18  written by Jim Houston [email protected]
+ *	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.
+ */
+
+#define ID_BITS 5
+#define ID_MASK ((1 << ID_BITS)-1)
+#define ID_FULL ((1 << (1 << ID_BITS))-1)
+
+/* Number of id_layer structs to leave in free list */
+#define ID_FREE_MAX 6
+
+struct id_layer {
+	unsigned int	bitmap: (1<<ID_BITS);
+	struct id_layer	*ary[1<<ID_BITS];
+};
+
+struct id {
+	int		layers;
+	int		last;
+	int		count;
+	int		min_wrap;
+	struct id_layer *top;
+};
+
+void *id_lookup(struct id *idp, int id);
+int id_new(struct id *idp, void *ptr);
+void id_remove(struct id *idp, int id);
+void id_init(struct id *idp, int min_wrap);
+
+static inline void update_bitmap(struct id_layer *p, int bit)
+{
+	if (p->ary[bit] && p->ary[bit]->bitmap == (typeof(p->bitmap))-1)
+		p->bitmap |= 1<<bit;
+	else
+		p->bitmap &= ~(1<<bit);
+}
+
+extern kmem_cache_t *id_layer_cache;
+