[PATCH] An O1, nonrecursive ID allocator for Posix timers

[PATCH] An O1, nonrecursive ID allocator for Posix timers

[Joe Korty]

Hi George, Andrew, Linus, Jim, Everyone,

This is a drop-in replacement for the ID allocator that Jim Houston
wrote to support posix timers.  The inspiration for this came from
Andrew Morton's desire for a recursion-free allocator; in addition I
have made it O(1) while preserving the no-upper-limits-except-memory
attribute of the original.

I (actually Jim) spot-tested this with Jim's posix timers patch as
the base.  It passed a run of George's timers test suite
(http://sourceforge.net/projects/high-res-timers) and the timer
portion of the posix test suite (http://posixtest.sourceforge.net/).

To play with, apply Jim's posix timer patch to 2.5.51 and then delete

    kernel/id2ptr.c
    include/linux/id2ptr.h

then apply this patch.

This procedure might also work against George's timers patch, as he is
using the same ID allocator as Jim.

Jim's timer patch may be found at:
    http://marc.theaimsgroup.com/?l=linux-kernel&m=104006731324824&q=raw

George's timer patch may be found at:
    http://sourceforge.net/projects/high-res-timers 

Joe Korty - Concurrent Computer Corporation




--- 2.5.51/kernel/id2ptr.c	1969-12-31 19:00:00.000000000 -0500
+++ 2.5.51-jh-jak/kernel/id2ptr.c	2002-12-18 09:46:57.000000000 -0500
@@ -0,0 +1,353 @@
+/*
+ * kernel/id2ptr.c
+ *
+ * 2002-12-16  written by Joe Korty joe.korty@ccur.com
+ *	Copywrite (C) 2002 by Concurrent Computer Corporation
+ *	Distributed under the GNU GPL license version 2.
+ *
+ * An O(1) ID to pointer translation service.
+ *
+ * 17 bits from the ID data structure pointer are copied into the ID
+ * which, when that ID is passed back into the system, can be used to
+ * construct a pointer to a `block of IDs', within which the desired ID
+ * data structure can be found.  However, before that reconstructed pointer
+ * can be dereferenced, the above 17 bits must first index a bitmap to
+ * check if the pointer is valid.  The remaining ID bits hold the index
+ * of the desired ID data structure within the block and an arbitary
+ * value, used to keep IDs from being reused `too fast'.
+ *
+ * Design assumptions: A kmalloc that aligns a power-of-two request to
+ * the size and whose allocation address range spans at most 2^30 bytes.
+ *
+ * Design faults: 1) ID blocks are never kfree'ed once kmalloc'ed.  2)
+ * The bitmap may be prohibitively large on 64-bit architectures (to fix,
+ * vmalloc() might make a good kmalloc() substitute).  3) A bitmap is 4
+ * pages and ID blocks are 2 pages each, these sizes strain kmalloc.
+ */
+
+#include <linux/init.h>
+#include <linux/kernel.h>
+#include <linux/bitops.h>
+#include <linux/string.h>
+#include <linux/list.h>
+#include <linux/slab.h>
+#include <linux/smp_lock.h>
+#include <linux/id2ptr.h>
+#include <asm/semaphore.h>
+#include <asm/uaccess.h>
+
+/*
+ * These are the master tuning knobs of the ID allocator:
+ *
+ *    KMALLOCSZ_INBITS	- address range of a kmalloc call, in #bits.
+ *    IDSZ_INBITS	- #bits in a posix timer ID.
+ *    BLKSZ_INBITS	- allocation size of a block of IDs, in #bits.
+ *
+ * These are some of the more important 'sub-tunables', derived from the above:
+ *
+ *    KEYSZ_INBITS	- #bits from a ID pointer copied into an ID.
+ *    CODESZ_INBITS	- #bits in an ID available to hold misc encoded data:
+ *			    i   - index of ID data struct in an ID block
+ *			    arb - a arbitrary `random value', used to keep IDs
+ *				  from being reused 'too fast'
+ *    MAX_IDS_PERBLK	- #IDs in an ID block.
+ *    MAX_ARBS		- upper limit on the above `arb' random value.
+ *
+ * Relationships:
+ *
+ *    KEYSZ_INBITS + CODESZ_INBITS  == IDSZ_INBITS
+ *	(an ID is made up of only two fields, KEY and CODE)
+ *
+ *    KEYSZ_INBITS + BLKSZ_INBITS == KMALLOCSZ_INBITS
+ *	(all bits the kmalloc range must be accounted for by the KEY and
+ *	BLK fields)
+ *
+ *    MAX_ARBS * MAX_PTIMERS_PERBLOCK <= CODESZ
+ *	(required for the CODE field to hold an encoding of the `ID data
+ *	structure index' and the `arbitary value').
+ */
+#define KMALLOCSZ_INBITS	(30)
+#define KMALLOCSZ		(1 << KMALLOCSZ_INBITS)
+#define KMALLOCSZ_MASK		(KMALLOCSZ - 1)
+
+#define IDSZ_INBITS		(32)
+#define BYTESZ_INBITS		(8)
+
+#define BLKSZ_INBITS		(13)
+#define BLKSZ			(1 << BLKSZ_INBITS)
+#define BLKSZ_MASK		(BLKSZ - 1)
+
+#define KEYSZ_INBITS		(KMALLOCSZ_INBITS - BLKSZ_INBITS)
+#define KEYSZ			(1 << KEYSZ_INBITS)
+#define KEYSZ_MASK		(KEYSZ - 1)
+
+#define CODESZ_INBITS		(IDSZ_INBITS - KEYSZ_INBITS)
+#define CODESZ			(1 << CODESZ_INBITS)
+#define CODESZ_MASK		(CODESZ - 1)
+
+#define BITMAPSZ		(KEYSZ / BYTESZ_INBITS)
+
+#define MAX_IDS_PERBLK		(BLKSZ / sizeof(struct iddata))
+#define MAX_ARBS		(CODESZ / MAX_IDS_PERBLK)
+
+/*
+ * An ID namespace control structure.
+ */
+struct idspace {
+	struct list_head head;
+	unsigned long *bitmap;
+	spinlock_t lock;
+	struct semaphore sleeplock;
+};
+
+/*
+ * An ID control structure.
+ */
+struct iddata {
+	struct list_head list;
+	unsigned id;
+	unsigned ctr;
+	void *data;
+};
+
+/**
+ * id_init - create & initialize an ID namespace
+ * @isp - pointer to an uninitialized/unused ID namespace structure
+ *
+ * Large things are left uninitialized until first use.
+ */
+static void id_init(struct idspace *isp)
+{
+	spin_lock_init(&isp->lock);
+	sema_init(&isp->sleeplock, 1);
+	INIT_LIST_HEAD(&isp->head);
+	isp->bitmap = NULL;
+}
+
+/**
+ * id_init_finish - finish initializing an ID namespace
+ * @isp - pointer to a partially initialized ID namespace structure
+ *
+ * Invoked at first use of the namespace.  May race with other (potential)
+ * first-users, first one there gets to initialize; the others NOP.
+ */
+static void id_init_finish(struct idspace *isp)
+{
+	void *bp;
+
+	bp = kmalloc(BITMAPSZ, GFP_KERNEL);
+	memset(bp, 0, BITMAPSZ);
+
+	spin_lock_irq(&isp->lock);
+	if(likely(!isp->bitmap)) {
+		isp->bitmap = bp;
+	} else {
+		kfree(bp);
+	}
+	spin_unlock_irq(&isp->lock);
+}
+
+/**
+ * id_mk - make an ID out of a ID structure address and an arbitrary value.
+ * @p: pointer to a ID data structure in that namespace
+ * @arb: an arbitrary value.
+ *
+ * Callers should make `arb % MAX_ARBS' different each time id_mk is called
+ * with the same `p'.
+ */
+static inline unsigned id_mk(struct iddata *p, unsigned arb)
+{
+	unsigned base, off, i, key, code, id;
+
+	base = (unsigned) ((unsigned long)p - PAGE_OFFSET);
+
+	key = base >> BLKSZ_INBITS;
+	off = base & BLKSZ_MASK;
+	i = off / sizeof(struct iddata);
+	arb %= MAX_ARBS;
+	if (unlikely((arb|key|i) == 0))
+		arb=1; /* do not allow an ID == 0 to be created */
+	code = (i * MAX_ARBS) + arb;
+	id = (key << CODESZ_INBITS) + code;
+
+	BUG_ON(key >= KEYSZ);
+	BUG_ON(off % sizeof(struct iddata));
+	BUG_ON(i >= MAX_IDS_PERBLK);
+	BUG_ON(code >= CODESZ);
+
+	return id;
+}
+
+/**
+ * id_alloc - allocate an iddata data structure and assign it an ID.
+ * @isp: pointer to the ID namespace that the allocation is to be made in.
+ */
+static struct iddata *id_alloc(struct idspace *isp)
+{
+	struct iddata *p;
+	unsigned i, base, key;
+
+	might_sleep();
+
+	if (unlikely(!isp->bitmap)) {
+		id_init_finish(isp);
+	}
+	spin_lock_irq(&isp->lock);
+	while (unlikely(list_empty(&isp->head))) {
+		spin_unlock_irq(&isp->lock);
+		down(&isp->sleeplock);
+		spin_lock_irq(&isp->lock);
+		if (likely(list_empty(&isp->head))) {
+			spin_unlock_irq(&isp->lock);
+			p = kmalloc(BLKSZ, GFP_KERNEL);
+			base = (unsigned) ((unsigned long)p - PAGE_OFFSET);
+
+			BUG_ON(base & ~KMALLOCSZ_MASK);
+			BUG_ON(base & BLKSZ_MASK);
+
+			spin_lock_irq(&isp->lock);
+			for (i = 0; i < MAX_IDS_PERBLK; i++) {
+				list_add_tail(&p[i].list, &isp->head);
+				p[i].id = 0;
+			}
+			key = base >> BLKSZ_INBITS;
+			__set_bit(key, isp->bitmap);
+		}
+		up(&isp->sleeplock);
+	}
+	p = list_entry(isp->head.next, struct iddata, list);
+	list_del(&p->list);
+	spin_unlock_irq(&isp->lock);
+
+	p->id = id_mk(p, p->ctr++);
+	return p;
+}
+
+/**
+ * id_lookup_l - given an ID, return its iddata structure address or NULL
+ * if the ID is not in use.
+ * @isp: pointer to the ID namespace owning the ID
+ * @id: the ID in question
+ *
+ * isp->lock must be held on entry, remains held on exit.
+ */
+static struct iddata *id_lookup_l(struct idspace *isp, unsigned id)
+{
+	struct iddata *p;
+	unsigned key, code, i, base;
+
+	key = id >> CODESZ_INBITS;
+	code = id & CODESZ_MASK;
+	i = code / MAX_ARBS;
+	base = (key << BLKSZ_INBITS) + (i * sizeof(struct iddata));
+	p = (struct iddata *) ((unsigned long)base + PAGE_OFFSET);
+
+	if (unlikely (!isp->bitmap))
+		p = NULL;
+	else if (unlikely(i >= MAX_IDS_PERBLK))
+		p = NULL;
+	else if (unlikely(!test_bit(key, isp->bitmap)))
+		p = NULL;
+	else if (unlikely(p->id != id))
+		p = NULL;
+	return p;
+}
+
+
+/*
+ * Compatibility (user) interface to the above.
+ */
+
+
+/***
+ * id2ptr_new - allocate a new ID and associate a data value with it.
+ * @idp: ID namespace pointer, caller-visible version.
+ * @data: data value to be attached to the ID.
+ */
+int id2ptr_new(struct id *idp, void *data)
+{
+	struct idspace *isp = (struct idspace *)idp->data;
+	struct iddata *p;
+	unsigned id;
+
+	p = id_alloc(isp);
+	if (unlikely(!p)) {
+		id = 0;
+	} else {
+		p->data = data;
+		id = p->id;
+	}
+	return (int)id;
+}
+
+/***
+ * id2ptr_lookup - given an ID namespace and an ID, return the data value
+ * associated with it, or 0 if ID is not in use.
+ * @idp: ID namespace pointer, caller-visible version.
+ * @id: ID to look up.
+ */
+void *id2ptr_lookup(struct id *idp, int id)
+{
+	struct idspace *isp = (struct idspace *)idp->data;
+	unsigned long flags;
+	struct iddata *p;
+	void *data;
+
+	if (unlikely(!isp->bitmap)) {
+		return NULL;
+	}
+	spin_lock_irqsave(&isp->lock, flags);
+
+	p = id_lookup_l(isp, (unsigned)id);
+	if (unlikely(p == NULL)) {
+		data = NULL;
+	} else {
+		data = p->data;
+	}
+	spin_unlock_irqrestore(&isp->lock, flags);
+	return data;
+}
+
+/*** 
+ * id2ptr_remove - free up an ID, return that ID if successful or 0 if not.
+ * @idp: ID namespace pointer, caller-visible version.
+ * @id: the ID to be freed.
+ */
+int id2ptr_remove(struct id *idp, int id)
+{
+	struct idspace *isp = (struct idspace *)idp->data;
+	unsigned long flags;
+	struct iddata *p;
+	int ecode = 0;
+
+	if (unlikely(!isp->bitmap))
+		return 0;
+
+	spin_lock_irqsave(&isp->lock, flags);
+	p = id_lookup_l(isp, (unsigned)id);
+	if (likely(p != NULL)) {
+		p->id = 0;
+		list_add_tail(&p->list, &isp->head);
+		ecode = id;
+	}
+	spin_unlock_irqrestore(&isp->lock, flags);
+	return ecode;
+}
+
+/***
+ * id2ptr_init - initialize/create an ID namespace.
+ * @idp: ID namespace pointer, caller-visible version.
+ * @min_wrap: not used, present only for compatibility.
+ *
+ * No locking done; assumes no caller will try to multiply initialize an
+ * ID namespace.
+ */
+
+void id2ptr_init(struct id *idp, int min_wrap) {
+
+	struct idspace *isp;
+
+	isp = kmalloc(sizeof(*isp), GFP_KERNEL);
+	id_init(isp);
+	idp->data = (void *)isp;
+}
--- 2.5.51/include/linux/id2ptr.h	1969-12-31 19:00:00.000000000 -0500
+++ 2.5.51-jh-jak/include/linux/id2ptr.h	2002-12-17 14:40:40.000000000 -0500
@@ -0,0 +1,28 @@
+#ifndef LINUX_ID2PTR_H
+#define LINUX_ID2PTR_H
+
+/*
+ * include/linux/id2ptr.h
+ *
+ * 2002-12-16  written by Joe Korty joe.korty@ccur.com
+ *	Copyright (C) 2002 by Concurrent Computer Corporation
+ *	Distributed under the GNU GPL license version 2.
+ *
+ * Caller interface to the O(1) ID to pointer translation service.
+ */
+
+/*
+ * ID namespace control structure.  From the caller's point of
+ * view, this will be an opaque data type.
+ */
+
+struct id {
+	void *data;
+};
+
+extern void *id2ptr_lookup(struct id *idp, int id);
+extern int id2ptr_new(struct id *idp, void *data);
+extern int id2ptr_remove(struct id *idp, int id);
+extern void id2ptr_init(struct id *idp, int min_wrap);
+
+#endif /* LINUX_ID2PTR_H */

Re: [PATCH] An O1, nonrecursive ID allocator for Posix timers

[george anzinger]

Joe Korty wrote:
> 
> Hi George, Andrew, Linus, Jim, Everyone,
> 
> This is a drop-in replacement for the ID allocator that Jim Houston
> wrote to support posix timers.  The inspiration for this came from
> Andrew Morton's desire for a recursion-free allocator; in addition I
> have made it O(1) while preserving the no-upper-limits-except-memory
> attribute of the original.
> 
> I (actually Jim) spot-tested this with Jim's posix timers patch as
> the base.  It passed a run of George's timers test suite
> (http://sourceforge.net/projects/high-res-timers) and the timer
> portion of the posix test suite (http://posixtest.sourceforge.net/).
> 
> To play with, apply Jim's posix timer patch to 2.5.51 and then delete
> 
>     kernel/id2ptr.c
>     include/linux/id2ptr.h
> 
> then apply this patch.
> 
> This procedure might also work against George's timers patch, as he is
> using the same ID allocator as Jim.
> 
> Jim's timer patch may be found at:
>     http://marc.theaimsgroup.com/?l=linux-kernel&m=104006731324824&q=raw
> 
> George's timer patch may be found at:
>     http://sourceforge.net/projects/high-res-timers
> 
A few comments:

I have found that the locking needs on lookup require that
the object be locked before the id-look-up is unlocked. 
With out this it is possible to find an object and have it
"removed" by another prior to getting it locked.  This is
why, in my version, the lock is exported.  I am considering
removing the locking from the id code entirely.  The
radix-tree code does it this way.  Another issue with
locking is the irq required or not thing.  Irq locking is
VERY expensive and getting more so as cpu speeds go up and
I/O speeds stay the same.  If it is not needed, it is best
not to use it.  Again, exporting the locking to the caller
seems the best answer.

I would much prefer to return memory on release.  In my code
I currently only return the leaf nodes, but I consider this
something to be fixed rather than a feature.

While the code is order 1 it does do a divide which, as I
understand it, is rather expensive (risc machines do them
with subroutines).  It is rather easy to eliminate the
recursion in an radix-tree AND avoid the div at the same
time.

I would consider moving the "ctr" member to the root of the
tree and using the same one for all allocations.  I may be
wrong here, but I think it gives a better cycle time for the
bits used.
-- 
George Anzinger   george@mvista.com
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml

Re: [PATCH] An O1, nonrecursive ID allocator for Posix timers

[Joe Korty]

>> This is a drop-in replacement for the ID allocator that Jim Houston
>> wrote to support posix timers.  [...]
> 
> A few comments:
> 
> I have found that the locking needs on lookup require that
> the object be locked before the id-look-up is unlocked. 
> With out this it is possible to find an object and have it
> "removed" by another prior to getting it locked.  This is
> why, in my version, the lock is exported.



Hi George,
Ouch.  I completely missed this API flaw.  Good catch.

Some ideas: rather than exporting the lock, we could replace

    int id2ptr_lookup(...)

with a

    int id2ptr_get(...)
    void id2ptr_put(...)

pair.  id2ptr_get() would do the old id2ptr_lookup semantics plus
bump a use-count on the ID.  id2ptr_put() would decrement the
use-count and delete the ID if the use-count became zero.
id2ptr_new() and id2ptr_remove() would need similar use-count
adjustments.

Or, a callback capability could be added to the API.  The callback
function would be registered by a new argument to id2ptr_init() and
called by id2ptr_lookup() before it dropped the lock.  In this case,
we would change id2ptr_init to look like:

    void id2ptr_init(struct id *id, int min_wrap, void (*func)(void *data));

where the callback function is defined to take one argument, the
(void *) value attached to the ID.  You (&Jim) would use this
callback mechanism to provide a function that would lock down the
data structure represented by the (void *) passed-in argument.



> Another issue with locking is the irq required or not thing.  Irq
> locking is VERY expensive and getting more so as cpu speeds go up and
> I/O speeds stay the same.  If it is not needed, it is best not to use
> it.  Again, exporting the locking to the caller seems the best answer.

IIRC, it is the spin_lock_* part that is expensive, not the *_irq part.
Interrupt locking is merely setting/clearing a bit in the EFLAGS
register, which (if the i386 follows the PowerPC pattern, the CPU I
am most familiar with), is slower than setting/clearing a bit in a
general purpose register but not that much slower.

On the other hand, the bus locking of spin_lock_* stops all other cpus
and dma traffic from accessing the bus for the interval of the lock,
this can be devastating on systems with large numbers of cpus and/or
high IO traffic.  However, this is not a problem on all architectures.
The PowerPC, for one, provides a pair of instructions which one can
implement spin_lock without utilizing a bus lock.  I look forward to
the day Intel adds a similiar pair of instructions to their ISA.

In any case, all of the ID user interfaces have exactly one lock and
one unlock along their most commonly executed patch.  One can't get
any better than that without resorting to architecture tricks like
assuming reads and writes go out to memory in a certain order.



> I would much prefer to return memory on release.  In my code
> I currently only return the leaf nodes, but I consider this
> something to be fixed rather than a feature.

I have an adjustment in mind which would allow the O(1) ID allocator
to return excess memory.  Each ID block would do its own little free
list and those lists in turn would be chained together.  That way it
would be easy to kfree() an ID block once it became completely full
of freed IDs.



> While the code is order 1 it does do a divide which, as I
> understand it, is rather expensive (risc machines do them
> with subroutines).  It is rather easy to eliminate the
> recursion in an radix-tree AND avoid the div at the same
> time.

I will make this change.  Thanks.



> I would consider moving the "ctr" member to the root of the
> tree and using the same one for all allocations.  I may be
> wrong here, but I think it gives a better cycle time for the
> bits used.

A random value works just as well (actually a little better) than a
counter that is not unique to each ID data structure.  I may go the
(pseudo) random route & eliminate the ctr altogether.  Or I may be
able to find some unused bits in the ID data structure where I can
pack it in.

Thanks for your feedback,
Joe

Re: [PATCH] An O1, nonrecursive ID allocator for Posix timers

[george anzinger]

Joe Korty wrote:
> 
> >> This is a drop-in replacement for the ID allocator that Jim Houston
> >> wrote to support posix timers.  [...]
> >
> > A few comments:
> >
> > I have found that the locking needs on lookup require that
> > the object be locked before the id-look-up is unlocked.
> > With out this it is possible to find an object and have it
> > "removed" by another prior to getting it locked.  This is
> > why, in my version, the lock is exported.
> 
> Hi George,
> Ouch.  I completely missed this API flaw.  Good catch.
> 
> Some ideas: rather than exporting the lock, we could replace
> 
>     int id2ptr_lookup(...)
> 
> with a
> 
>     int id2ptr_get(...)
>     void id2ptr_put(...)
> 
> pair.  id2ptr_get() would do the old id2ptr_lookup semantics plus
> bump a use-count on the ID.  id2ptr_put() would decrement the
> use-count and delete the ID if the use-count became zero.
> id2ptr_new() and id2ptr_remove() would need similar use-count
> adjustments.
> 
> Or, a callback capability could be added to the API.  The callback
> function would be registered by a new argument to id2ptr_init() and
> called by id2ptr_lookup() before it dropped the lock.  In this case,
> we would change id2ptr_init to look like:
> 
>     void id2ptr_init(struct id *id, int min_wrap, void (*func)(void *data));
> 
> where the callback function is defined to take one argument, the
> (void *) value attached to the ID.  You (&Jim) would use this
> callback mechanism to provide a function that would lock down the
> data structure represented by the (void *) passed-in argument.

This might work, but consider this:  How might one remove an
ID and what it points at.  It needs to disappear atomically
or some cpu will end up with a valid ID that points at a
structure that has been returned.  One way of doing this
would be to do the id look up to get the structure and then,
under the same lock, do the id_remove.

The way I do it in the posix_timers is to look up, under the
look up, lock the structure, unlock the look up, flag the
structure as "gone" and then go about removing it.  This
way, another cpu will still find it but will also find a
"gone" flag, which must be checked on each lookup.  As I
write this, I realize that I would prefer the first way of
doing things.

Why not remove all locking from the id2ptr code and let the
user take care of it?  You might have to export one
additional function which "prepares to allocate an id" so
you can call the slab code without being locked.
> 
> > Another issue with locking is the irq required or not thing.  Irq
> > locking is VERY expensive and getting more so as cpu speeds go up and
> > I/O speeds stay the same.  If it is not needed, it is best not to use
> > it.  Again, exporting the locking to the caller seems the best answer.
> 
> IIRC, it is the spin_lock_* part that is expensive, not the *_irq part.
> Interrupt locking is merely setting/clearing a bit in the EFLAGS
> register, which (if the i386 follows the PowerPC pattern, the CPU I
> am most familiar with), is slower than setting/clearing a bit in a
> general purpose register but not that much slower.

I don't believe this is so.  The interrupt on/off change
needs to sync with the I/O system, to avoid in-flight stuff,
and so introduces stalls.  I suspect that sometimes it also
needs to flush the pipeline, but I am not that up on those
sorts of details.  I have, however, seen the results of some
timing studies done on the run_timer_list code which showed
that the whole of the run_timer_list function was shorter
that the interrupt off instruction.  I think this was on a
1.3GHZ PIII.  I know this was an issue on the PARISC (the
last machine I worked on) also, so I think it is common to
all modern machines that run the cpu faster and async to the
I/O bus.
> 
> On the other hand, the bus locking of spin_lock_* stops all other cpus
> and dma traffic from accessing the bus for the interval of the lock,

No, this is not true.  The lock is only for the access time
of the spinlock byte.  If spinning, the lock will be taken
quite often, but even then there are other unlocked
instructions in the loop.

> this can be devastating on systems with large numbers of cpus and/or
> high IO traffic.  However, this is not a problem on all architectures.
> The PowerPC, for one, provides a pair of instructions which one can
> implement spin_lock without utilizing a bus lock.  I look forward to
> the day Intel adds a similiar pair of instructions to their ISA.
> 
> In any case, all of the ID user interfaces have exactly one lock and
> one unlock along their most commonly executed patch.  One can't get
> any better than that without resorting to architecture tricks like
> assuming reads and writes go out to memory in a certain order.
> 
> > I would much prefer to return memory on release.  In my code
> > I currently only return the leaf nodes, but I consider this
> > something to be fixed rather than a feature.
> 
> I have an adjustment in mind which would allow the O(1) ID allocator
> to return excess memory.  Each ID block would do its own little free
> list and those lists in turn would be chained together.  That way it
> would be easy to kfree() an ID block once it became completely full
> of freed IDs.
> 
> > While the code is order 1 it does do a divide which, as I
> > understand it, is rather expensive (risc machines do them
> > with subroutines).  It is rather easy to eliminate the
> > recursion in an radix-tree AND avoid the div at the same
> > time.
> 
> I will make this change.  Thanks.
> 
> > I would consider moving the "ctr" member to the root of the
> > tree and using the same one for all allocations.  I may be
> > wrong here, but I think it gives a better cycle time for the
> > bits used.
> 
> A random value works just as well (actually a little better) than a
> counter that is not unique to each ID data structure.  I may go the
> (pseudo) random route & eliminate the ctr altogether.  Or I may be
> able to find some unused bits in the ID data structure where I can
> pack it in.

I have not looked at random number generators, but I assumed
a counter would be faster.  I could be wrong here...
> 
> Thanks for your feedback,
> Joe

-- 
George Anzinger   george@mvista.com
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml