[prev in list] [next in list] [prev in thread] [next in thread] 

List:       eros-arch
Subject:    Re: [eros-arch] rendevous queues (was EROS Mistake #3: Persistence)
From:       "Jonathan S. Shapiro" <shap () eros-os ! org>
Date:       2003-12-18 18:18:18
[Download RAW message or body]

On Tue, 2003-12-16 at 02:33, Bill Frantz wrote:

> [A general suggestion is to figure out a way to "charge for" the use of the
> process table.  It appears to be a critical resource that is not controlled
> in the current design, which would allow it to be abused.]
> 
> 
> 
> I think the objections to the Apache pattern come down to:
> 
> * Poor cache behavior on multi-processor systems.
> * Forking the return to the client puts pressure on the process table.
> * A forwarding IPC is required.

Forking the return is fortunately required. This is good, because there
is a larger problem with 'fork' being a blocking operation.

> Starting with the Apache pattern, we introduce the idea of CPU affinity for
> the server threads.  The dispatcher process needs to be able to read the
> CPU ID (it is best if the CPU ID can be used as an index) so it can keep a
> stack of worker processes by CPU.  I think that one change makes a major
> dent in the cache trashing problem.
>
> [This change allows processes with the Get_CPU_ID capability to find what
> CPU ID they are currently running on.  Does anyone think allowing this
> information is a problem?]

I see no problem with reading my current CPU index, though it does
expose something that really shouldn't be exposed outside the kernel.
Unfortunately, it doesn't help. By the time the dispatcher process gets
the CPU ID, it is already too late. The problem is that the dispatcher
is itself running on the wrong CPU. *THIS* is the cache trashing that we
are talking about.

There is a second objection to the dispatcher pattern. Fundamentally,
its job is to spend O(2000) cycles (best case) in order to do what
amounts to a dequeue operation on the worker thread. This just isn't a
reasonable design choice.

> We can reorder the return to have the worker process first call the
> dispatcher process to cause add it to the available queue, and then
> promptly return to the caller.

We successfully avoided the need for this in EROS. We can assume that
the dispatcher and the worker share an address space. All the worker has
to do is set a bit that says "I'll be available real soon". No extra
call (and no extra 2000 cycles entailed) is required.

> However we can save a few jumps by having the re-queue operation performed
> by a special kernel function.  There are a number of ways this function
> could be designed.  One might be:
> 
> Define two capability slots which are part of the process and accessible to
> the process keeper.  One slot is the stack slot which, when the process is
> on the stack, points to the next stack member of NULL.  The other points to
> the array of stack heads.  The first capability in the stack head array is
> a number capability whose value is called the limit.  The limit defines the
> number of stack heads.

You need two such slots, because we need to be able to destroy one of
these processes without breaking the chain. The chain therefore needs to
be doubly linked.

> The kernel Return_And_Queue function is invoked via return passing 2
> capabilities to be returned to the client, a process capability to the
> process to be pushed on the stack (usually the process doing the return),
> and the resume capability to the client.

Yuck. Screwed up return conventions like this are things to be abhored.
They are visible all the way up into the user-level API, and they don't
need to be. They make building a reasonable IDL compiler nearly
impossible. Your objective is fine; it's the interface I do not like.
It's also hideously complicated to do all of this in any sort of fast
path. You're going to end up giving up significant performance in every
fast path call in order to check for an unlikely case.

> The forwarding IPC can also be eliminated.  One possible design is:
> 
> Define a new capability type which acts like a gate capability, but allows
> the kernel to select one of several processes from an array of stacks of
> process keys...

Now I have to do capability array traversal in the fast path too. Not a
happy-making strategy. Once again a reasonable general strategy, but we
need to look at the data structure. I need to send out another note for
archival purposes before I can propose an alternative.
-- 
Jonathan S. Shapiro <shap@eros-os.org>

_______________________________________________
eros-arch mailing list
eros-arch@mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/eros-arch
[prev in list] [next in list] [prev in thread] [next in thread]