Re: PID sequences

David S. Miller (
Tue, 24 Feb 1998 14:17:30 -0800

Date: Mon, 23 Feb 1998 21:19:44 -0800 (PST)
From: Dean Gaudet <>

I have a concern. Whether or not this is valid is for you folks to
decide. Read the theory that describes apache 1.3's mod_unique_id
<>. Essentially I
make an assumption that pid reuse is unlikely to occur within a
single second. I'm sure I'm not the only one making this
assumption (think Message-ID generation, tmp filename generation,

If you can do this with 15-bit "random" pids that's great.
Otherwise maybe pids have to go 31-bits. I didn't look at your
scheme closely, but it didn't seem to be "random".

Yes, there are some issues. Richard Henderson gave me some ideas last
night. Here is what I have so far.

I can just imagine some program caching the parent pid, the parent
goes away (or changes, due to debugging for example), and the parent
pid gets reused very quickly (very likely with my suggested
algorithm). The child probes the parent by sending some harmless kill
signal to it, poof, disaster.

Solution involves some changes, which I think on the whole should not
add too much of a performance hit, and perhaps will still perform
significantly better than what we have right now.

Firstly, re-implement the task slot list to free items to the end of
the list, and allocate from the head. This gives us a a NR_TASKS

This is still not enough, create now a version counter. This version
gets shifted left to just past the taskslot number space, this gives a
satisfactory level of protection. The version number here works in
much the same way as the MMU context versioning used on the Alpha,
Sparc64, and MIPS work.

David S. Miller

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to