interprocess messaging to/from many grandchildren

[phil-news-nospam@ipal.net]

I want to have a large number of child processes communicating
with a grandparent process. The number of children may be larger
than the number of file descriptors a process can have, so I do
need to rule out having separate pipes to each child. Further,
since it is the grandparent doing the communications, setting up
pipes in the middle process (child of the grandparent) which is
doing the network listen and forking each child, will be hard to
do, anyway. Byte stream pipes will also not be good because the
messages need to stay intact and not be mingled with other messages
coming from other children, while they may be larger than the
maximum a pipe can convey without that risk. And finally, the
grandparent needs to send messages back and be sure the correct
child gets it. I will not be using threads.

What is the best way to do this? What is the 2nd best way? It
does not need to be super portable, but it must work on Linux and
should work on the BSDs and Solaris.

--
-----------------------------------------------------------------------------
| Phil Howard KA9WGN | [url]http://linuxhomepage.com/[/url] [url]http://ham.org/[/url] |
| (first name) at ipal.net | [url]http://phil.ipal.org/[/url] [url]http://ka9wgn.ham.org/[/url] |
-----------------------------------------------------------------------------

[Eric Sosman]

[email]phil-news-nospam@ipal.net[/email] wrote:

>
> I want to have a large number of child processes communicating
> with a grandparent process. The number of children may be larger
> than the number of file descriptors a process can have, so I do
> need to rule out having separate pipes to each child. Further,
> since it is the grandparent doing the communications, setting up
> pipes in the middle process (child of the grandparent) which is
> doing the network listen and forking each child, will be hard to
> do, anyway. Byte stream pipes will also not be good because the
> messages need to stay intact and not be mingled with other messages
> coming from other children, while they may be larger than the
> maximum a pipe can convey without that risk. And finally, the
> grandparent needs to send messages back and be sure the correct
> child gets it. I will not be using threads.
>
> What is the best way to do this? What is the 2nd best way? It
> does not need to be super portable, but it must work on Linux and
> should work on the BSDs and Solaris.

1) Shared memory, a little synchronization, and a
home-brewed notify/ack protocol

2) Message queues

3) Grandparent sends to parent, parent forwards to
grandchild. Grandchildren send to parent, parent
multiplexes them upwards to grandparent.

0) Keep in mind that I don't know what your application
is trying to do

--
[email]Eric.Sosman@sun.com[/email]

[Marc Rochkind]

On 4 Aug 2003 20:55:55 GMT, <phil-news-nospam@ipal.net> wrote:

> I want to have a large number of child processes communicating
> with a grandparent process. The number of children may be larger
> than the number of file descriptors a process can have, so I do
> need to rule out having separate pipes to each child. Further,
> since it is the grandparent doing the communications, setting up
> pipes in the middle process (child of the grandparent) which is
> doing the network listen and forking each child, will be hard to
> do, anyway. Byte stream pipes will also not be good because the
> messages need to stay intact and not be mingled with other messages
> coming from other children, while they may be larger than the
> maximum a pipe can convey without that risk. And finally, the
> grandparent needs to send messages back and be sure the correct
> child gets it. I will not be using threads.
>
> What is the best way to do this? What is the 2nd best way? It
> does not need to be super portable, but it must work on Linux and
> should work on the BSDs and Solaris.
>

For small messages -- a couple of hundred bytes or fewer -- SysV messages
will probably be fastest, and are very easy to set up.

For large messages, shared memory + semaphores will be fastest.

However, be warned that the so-called "semaphore initialization solution"
that Stevens describes doesn't work on FreeBSD (and possibly on other BSD
systems) because their implementation doesn't properly set the times.

Also, one quasi-BSD system, Darwin, doesn't have SysV messages.

Best of all is to encapsulate the actual mechanism in a wrapper so you can
try alternatives once the application is running.

--Marc

[phil-news-nospam@ipal.net]

On Mon, 04 Aug 2003 16:54:56 -0600 Marc Rochkind <rochkind@basepath.com> wrote:

| On 4 Aug 2003 20:55:55 GMT, <phil-news-nospam@ipal.net> wrote:
|
|> I want to have a large number of child processes communicating
|> with a grandparent process. The number of children may be larger
|> than the number of file descriptors a process can have, so I do
|> need to rule out having separate pipes to each child. Further,
|> since it is the grandparent doing the communications, setting up
|> pipes in the middle process (child of the grandparent) which is
|> doing the network listen and forking each child, will be hard to
|> do, anyway. Byte stream pipes will also not be good because the
|> messages need to stay intact and not be mingled with other messages
|> coming from other children, while they may be larger than the
|> maximum a pipe can convey without that risk. And finally, the
|> grandparent needs to send messages back and be sure the correct
|> child gets it. I will not be using threads.
|>
|> What is the best way to do this? What is the 2nd best way? It
|> does not need to be super portable, but it must work on Linux and
|> should work on the BSDs and Solaris.
|>
|
| For small messages -- a couple of hundred bytes or fewer -- SysV messages
| will probably be fastest, and are very easy to set up.
|
| For large messages, shared memory + semaphores will be fastest.

The messages could be as much as 64K bytes. Sharing memory could be a
problem because of the large number of children, and stuffing that many
shared spaces into the grandparent process VM.


| However, be warned that the so-called "semaphore initialization solution"
| that Stevens describes doesn't work on FreeBSD (and possibly on other BSD
| systems) because their implementation doesn't properly set the times.

I'm really wanting to avoid semaphores of any kind. Shared memory plus
signals might work, if I can address the sharing problems effectively
(which I have doubts about).



| Also, one quasi-BSD system, Darwin, doesn't have SysV messages.

Darwin is not a big concern. It's a server application.


| Best of all is to encapsulate the actual mechanism in a wrapper so you can
| try alternatives once the application is running.

Hopefully I can do that. I'm starting to think at the moment to use UDP
bound to the localhost address. But each child will have to have its own
localhost port (the port would then by the identity of the child), and
that could be using up a lot of them. The grandparent needs to be able
to respond to the correct child, but it doesn't need to know it's PID.

I'm also going to think about some other models to do this instead of the
GP/P/C relationship I have now.

--
-----------------------------------------------------------------------------
| Phil Howard KA9WGN | [url]http://linuxhomepage.com/[/url] [url]http://ham.org/[/url] |
| (first name) at ipal.net | [url]http://phil.ipal.org/[/url] [url]http://ka9wgn.ham.org/[/url] |
-----------------------------------------------------------------------------

[Michael B Allen]

On Mon, 04 Aug 2003 20:52:18 -0400, phil-news-nospam wrote:

> | For small messages -- a couple of hundred bytes or fewer -- SysV
> messages | will probably be fastest, and are very easy to set up. | |
> For large messages, shared memory + semaphores will be fastest.
>
> The messages could be as much as 64K bytes. Sharing memory could be a
> problem because of the large number of children, and stuffing that many
> shared spaces into the grandparent process VM.

I think shared memory is probably the best bet. Just mmap once and all
the forked processes will inherit the mapping. So the parent process
only has one "shared space".

> | However, be warned that the so-called "semaphore initialization
> solution" | that Stevens describes doesn't work on FreeBSD (and possibly
> on other BSD | systems) because their implementation doesn't properly
> set the times.
>
> I'm really wanting to avoid semaphores of any kind. Shared memory plus
> signals might work, if I can address the sharing problems effectively
> (which I have doubts about).

Signals are ugly. I try not to use them for anything but
macro-manipulation (e.g. kill).

> | Best of all is to encapsulate the actual mechanism in a wrapper so you
> can | try alternatives once the application is running.
>
> Hopefully I can do that. I'm starting to think at the moment to use UDP
> bound to the localhost address. But each child will have to have its
> own localhost port (the port would then by the identity of the child),
> and that could be using up a lot of them. The grandparent needs to be
> able to respond to the correct child, but it doesn't need to know it's
> PID.

I would just mmap a shared memory area for all processes to acces and
do what Eric said which is to setup a homebrew wait notify mechanism
meaning just use two semaphores to protect the shared memory area. Also
I think semaphores can be inherited by children as well so that would
eliminate the initialization problem on BSDs.

Mike

[phil-news-nospam@ipal.net]

On Tue, 05 Aug 2003 04:26:38 -0400 Michael B Allen <mba2000@ioplex.com> wrote:
| On Mon, 04 Aug 2003 20:52:18 -0400, phil-news-nospam wrote:
|
|> | For small messages -- a couple of hundred bytes or fewer -- SysV
|> messages | will probably be fastest, and are very easy to set up. | |
|> For large messages, shared memory + semaphores will be fastest.
|>
|> The messages could be as much as 64K bytes. Sharing memory could be a
|> problem because of the large number of children, and stuffing that many
|> shared spaces into the grandparent process VM.
|
| I think shared memory is probably the best bet. Just mmap once and all
| the forked processes will inherit the mapping. So the parent process
| only has one "shared space".

But then the children trample on each other to store messages. Then you
have to have semaphores to avoid that, and that leads to children waiting
a while.


|> | However, be warned that the so-called "semaphore initialization
|> solution" | that Stevens describes doesn't work on FreeBSD (and possibly
|> on other BSD | systems) because their implementation doesn't properly
|> set the times.
|>
|> I'm really wanting to avoid semaphores of any kind. Shared memory plus
|> signals might work, if I can address the sharing problems effectively
|> (which I have doubts about).
|
| Signals are ugly. I try not to use them for anything but
| macro-manipulation (e.g. kill).

I thought I had a solution along those lines, but after more study it does
not appear like it would work.


|> | Best of all is to encapsulate the actual mechanism in a wrapper so you
|> can | try alternatives once the application is running.
|>
|> Hopefully I can do that. I'm starting to think at the moment to use UDP
|> bound to the localhost address. But each child will have to have its
|> own localhost port (the port would then by the identity of the child),
|> and that could be using up a lot of them. The grandparent needs to be
|> able to respond to the correct child, but it doesn't need to know it's
|> PID.
|
| I would just mmap a shared memory area for all processes to acces and
| do what Eric said which is to setup a homebrew wait notify mechanism
| meaning just use two semaphores to protect the shared memory area. Also
| I think semaphores can be inherited by children as well so that would
| eliminate the initialization problem on BSDs.

I really want to avoid any form of waiting, and get things down to a clean
messaging mechanism. It would have been nice to have had a mechanism to
simply send a message to a specific process by it's PID, and to know what
PID each message comes from (so you can send one back).

The solution I'm looking at right now is for each worker child to bind a
socket to a UDP port on localhost. The master process that all workers
send messages to will have its own specific UDP port the workers inherited
the knowledge of. As long as the MTU on the lo interface is high enough,
this should work.

--
-----------------------------------------------------------------------------
| Phil Howard KA9WGN | [url]http://linuxhomepage.com/[/url] [url]http://ham.org/[/url] |
| (first name) at ipal.net | [url]http://phil.ipal.org/[/url] [url]http://ka9wgn.ham.org/[/url] |
-----------------------------------------------------------------------------

[Eric Sosman]

[email]phil-news-nospam@ipal.net[/email] wrote:

>
> On Mon, 04 Aug 2003 16:54:56 -0600 Marc Rochkind <rochkind@basepath.com> wrote:
>
> | For large messages, shared memory + semaphores will be fastest.
>
> The messages could be as much as 64K bytes. Sharing memory could be a
> problem because of the large number of children, and stuffing that many
> shared spaces into the grandparent process VM.

Even on a pretty lame system, the grandparent's usable
VM will be at least two gigabytes. Let's be pessimistic and
say that half of this is tied up in the grandparent's own
local doodads: one gigabyte of VM is still available for
shared memory. At 64KB per message, that's enough for
sixteen thousand messages ...

When you refer to "the large number of children," just
how large is "large?" As I mentioned before, I don't know
what your application is -- but a design that requires tens
of thousands of processes seems a bit unusual ...

--
[email]Eric.Sosman@sun.com[/email]

[phil-news-nospam@ipal.net]

On Tue, 05 Aug 2003 10:39:34 -0400 Eric Sosman <Eric.Sosman@sun.com> wrote:
| [email]phil-news-nospam@ipal.net[/email] wrote:
|>
|> On Mon, 04 Aug 2003 16:54:56 -0600 Marc Rochkind <rochkind@basepath.com> wrote:
|>
|> | For large messages, shared memory + semaphores will be fastest.
|>
|> The messages could be as much as 64K bytes. Sharing memory could be a
|> problem because of the large number of children, and stuffing that many
|> shared spaces into the grandparent process VM.
|
| Even on a pretty lame system, the grandparent's usable
| VM will be at least two gigabytes. Let's be pessimistic and
| say that half of this is tied up in the grandparent's own
| local doodads: one gigabyte of VM is still available for
| shared memory. At 64KB per message, that's enough for
| sixteen thousand messages ...
|
| When you refer to "the large number of children," just
| how large is "large?" As I mentioned before, I don't know
| what your application is -- but a design that requires tens
| of thousands of processes seems a bit unusual ...

It is actually a general purpose daemon framework for which I want to make
sure it will scale well, while also having the ability for a monitoring
process (the one each work communicates with) to be able to quickly detect
patterns of abuse and take some action (telling a worker to slow down a
given client, for example). Potential uses include HTTP, SMTP, and IMAP.

--
-----------------------------------------------------------------------------
| Phil Howard KA9WGN | [url]http://linuxhomepage.com/[/url] [url]http://ham.org/[/url] |
| (first name) at ipal.net | [url]http://phil.ipal.org/[/url] [url]http://ka9wgn.ham.org/[/url] |
-----------------------------------------------------------------------------

[Gene Hightower]

>>>>> "Phil" == phil-news-nospam <phil-news-nospam@ipal.net> writes:

Phil> It is actually a general purpose daemon framework for which

Something like this, maybe?

<http://www.cs.wustl.edu/~schmidt/PDF/IWCDS-94.pdf>

-- Gene

[Michael B Allen]

On Tue, 05 Aug 2003 10:30:45 -0400, phil-news-nospam wrote:

> On Tue, 05 Aug 2003 04:26:38 -0400 Michael B Allen <mba2000@ioplex.com>
> wrote: | On Mon, 04 Aug 2003 20:52:18 -0400, phil-news-nospam wrote: |
> |> | For small messages -- a couple of hundred bytes or fewer -- SysV |>
> messages | will probably be fastest, and are very easy to set up. | | |>
> For large messages, shared memory + semaphores will be fastest. |> |>
> The messages could be as much as 64K bytes. Sharing memory could be a
> |> problem because of the large number of children, and stuffing that
> many |> shared spaces into the grandparent process VM. | | I think
> shared memory is probably the best bet. Just mmap once and all | the
> forked processes will inherit the mapping. So the parent process | only
> has one "shared space".
>
> But then the children trample on each other to store messages. Then you
> have to have semaphores to avoid that, and that leads to children
> waiting a while.

Regardless of what mechanism you use you will need to coordinate access
to resources with locks. Coordinating access to one shared memory region
with a pair of semaphores will be much faster than reading and writing to
sockets which wheather you realized it or not will trip over many locks
on it's way down through the c library, into the kernel, and back. If you
really must have fine grained locking you can create a semaphore set and
partition the shared memory into an array of messages with once semaphore
per index. Shared memory is the fastest IPC mechanism available. That's
a fact.

Mike