Re: [RFC] ps command race fix

From: Albert Cahalan
Date: Tue Jul 25 2006 - 02:45:50 EST

Andrew Morton writes:
KAMEZAWA Hiroyuki <kamezawa.hiroyu@xxxxxxxxxxxxxx> wrote:

Hi, this is an experimental patch for the probelm
- "ps command can miss some pid occationally"
So I think we're still seeking a solution to this.

We have a solution, subject to some bit rot I'm sure.
The cookie/cursor hack should have been rejected.
I'm still wondering why that ever got accepted.

Hugh had a patch set containing a tree-based replacement
for the PID handling. It worked perfectly, letting /proc
look up the lowest-not-under PID for any given PID.

(can anybody find the patch set?)

BTW, here's a WONTFIX resolved bug that places the date
for the patch set as being prior to 2005-05-21.

Options might be:

a) Pin the most-recently-visited task in some manner, so that it is
still on the global task list when we return. That's fairly simple to
do (defer the release_task()) but it affects task lifetime and visibility
in rare and worrisome ways.

In state X perhaps?

b) Change proc_pid_readdir() so that it walks the pid_hash[] array
instead of the task list. Need to do something clever when traversing
each bucket's list, but I'm not sure what ;) It's the same problem.

Possibly what we could do here is to permit the task which is walking
/proc to pin a particular 'struct pid': take a ref on it then when we
next start walking one of the pid_hash[] chains, we _know_ that the
'struct pid' which we're looking for will still be there. Even if it
now refers to a departed process.

Well, we have to pin something if we don't use a tree.

If I remember right the cookie/cursor thing was mostly intended
to solve real-time problems. Obviously it fails at this too.
(not that attackable hashes are acceptable for real-time!)

c) Nuke the pid_hash[], convert the whole thing to a radix-tree.
They're super-simple to traverse. Not sure what we'd index it by

With the right kind of tree, you just look up by PID and get
back the nearest result which is not less than the desired one.
This is what the older patch set did.

I like trees. They have nice cache properties. Decent trees are
immune to being turned into linked lists via hash function attacks.
The non-crypto hashes in the kernel ought to worry people.
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at