Re: cvs commit: src/sys/ddb db_ps.c src/sys/kern init_main.c kern_exit.c kern_fork.c kern_resource.c kern_sig.c sys_generic.c src/sys/platform/pc32/i386 pmap.c src/sys/platform/vkernel/platform pmap.c src/sys/sys proc.h tree.h src/sys/vm vm_vmspace.c

["Simon 'corecode' Schubert" <corecode@xxxxxxxxxxxx>]

Matthew Dillon wrote:
>     Now we could argue over which data structure is the best, and if you
>     want to implement the final solution we come up with that's fine with
>     me.  But we aren't going to back out these fixes.  A linear list is bad,
>     period.

So I was wondering if we even have to try to avoid reuse of tids.  I don't think so, because they are not user visible.  So why don't we just use a simple array to store the pointers?  Granted, that's going to waste memory if you first spawn 100000 threads and then close all but one.  But apart from that, it would be O(1) and *very* easy to use/understand.  Tid allocation and thread creation could even be lock-free (two atomic instructions, though, so maybe no gain).

If we need to try to avoid reusing tids (like we should for pids), there is this cool O(1) pid allocator from NetBSD, using some fancy array with special data handling.

cheers
 simon

--
Serve - BSD     +++  RENT this banner advert  +++    ASCII Ribbon   /"\
Work - Mac      +++  space for low €€€ NOW!1  +++      Campaign     \ /
Party Enjoy Relax   |   http://dragonflybsd.org      Against  HTML   \
Dude 2c 2 the max   !   http://golden-apple.biz       Mail + News   / \