thread ids, task ids and subsystems

[Marcus Brinkmann]

Hi,

one of the decisions we have to make for the Hurd on L4 is how to use the
global thread ids that are available in L4.  As a reminder: The local thread
id on i386 is just the address of the user-level thread control block (%gs).
The global thread id is arbitrary, but only the upper 18 (on 64 bit arches
32) bits are used to identify the thread, while the lower 14 bits are
checked but not otherwise used (according to the specs, they can be used as
a version number to make thread ids unique in time).

Now, there will be a root server that creates tasks and threads (there must
be, as according to the specs only a privileged thread is allowed to create
threads, and only the threads in the initial address space are privileged).

I suggest that we use the version id as a task id, or, the other way round:
store the task id in the version id of the thread.  This allows to determine
the task id of a global thread id by just masking out the lower bits, which
is very fast of course.  It also guarantees some uniqueness in time as task
ids are not reused often.

14 bits (which must not be all 0 to differentiate global and local thread
ids) means that there will be an upper limit of 2^14 - 1 = 16383 tasks in
the whole system for 32 bit arches, which is good enough, I think.
For 64 bit arches, there is a limit of 2^32-1 tasks - certainly enough.

For running several subsystems, you would want to bite off another few bits
from the global thread id to identify the subsystem (subhurd, or whatever)
that the thread is in.

I think that it has strategic advantages if you use bits from the
non-version part here, because then the relevant bits of the thread ids
are not shared across subsystems, and each subsystem can manage its own
thread ids along with the task ids.  This makes the root server lean and
clean and simple.  On 32 bit arches, there are not that many bits, but for a
few number of subsystems (4, 8 or 16), it should work quite well.  For 64
bit systems, you can use much more (1024 or even 4096 subsystems is no
problem).

This leads to the following setup:

N bits for subsystem ID   18-N (32-N) bits for thread ID   14 (32) version id

N can be 1 to 4 on 32 bit arches and 1 to 18 on 64 bit arches.

The value of N can be set at compile time, or even at boot time (if you have
a query interface).

The subsystem 0 should be reserved for the root server, the irq threads, the
system threads, and whatever else we put in the layer between the subsystem
and L4.  (If you are a purist and want to allow N to be 0, then I have some
ideas how that can be done, too).

The root server considers all threads with a subsystem of 0, or with a
thread number of 0 (masking out the subsystem bits) as privileged, and
allows those threads to control *any* other thread.  (This is important as
you must be able to create, control and destroy one subsystem from another
one for debugging and maintenance).  The root server itself does not need to
keep any state: It just checks bits in the thread id.  The responsibility to
manage thread numbers and version numbers is completely within the special 0
threads.  It also contains no mechanism to concurrently allocate unique
subsystem ids, although that is something you might want in a real world
system (but that could be added later).

Here is an example with N being 3.  There are two systems running, a Hurdish
one and a non-hurdish one.  A "metaserver" is one running between L4 and the
Subsystems, like device sharing servers, or other cooperation or
communication layers.

Thread (subsystem id, thread number, version id)        Purpose
000 000000000000000 00000000000000                      nilthread
000 000000000000001 00000000000001                      IRQ 1
000 000000000000010 00000000000001                      IRQ 2
...
000 Systembase      00000000000001                      Systemthread 1
000 Systembase + 1  00000000000001                      Systemthread 2
...
000 Userbase        00000000000001                      Metaserver 1
000 Userbase + 1    00000000000001                      Metaserver 2
...
001 000000000000000 00000000000001                      priv. thread in hurd
001 000000000000001 00000000000010                      1st thread in task 2
001 000000000000010 00000000000010                      2nd thread in task 2
001 000000000010101 00000000000011                      some thread in task 3
...
010 000000000000000 anything (except 0)                 priv. thread in other
010 anything        anything (except 0)                 some thread in other
...
111 111111111111111 00000000000000                      any local thread
111 111111111111111 11111111111111                      any thread

as you can see, the subsystem -1 has to be a bit careful about the thread
number -1.

I think this setup is flexible enough to allow peaceful coexistance between
different, even non-hurdish subsystems.  A subsystem that previously assumed
it has control over the whole L4 system only needs minimal changes to be
adjusted (it needs to copy the first N bits of its initial thread id to all
thread ids it allocates, and not touch any other threads - and of course it
needs some bootstrap stuff adjusted and use the root server instead L4
directly).

Hurd systems code the task id in the thread id.  So a Hurd server can tell
from which subsystem and task an RPC comes, and take appropriate security
measures.  The task ID will of course be the PID (and a more global PID can
be constructed from the subsystem id and the task id).

Thanks,
Marcus

-- 
`Rhubarb is no Egyptian god.' GNU      http://www.gnu.org    address@hidden
Marcus Brinkmann              The Hurd http://www.gnu.org/software/hurd/
address@hidden
http://www.marcus-brinkmann.de/