Pardon the subject line! I think the PID algo. is actually pretty good and cheap.
I just think that a very minor tweak could actually make it *actually* do what it always intended to do (that is, satisfy the PID-AIM listed below)! No expanded PID renumbering, no incompatibility introduction, nothing, just a relatively *minor tweak*. *** QUICK SUMMARY: PROBLEM: PID gets re-used immediately as soon as it is freed. EXAMPLE: My program with PID 1323 uses temporary files that are of the form PID-<something>. It finishes in two days By this time, linux has circled PIDs back around five times. And, the counter happens to be right at 1323 right as the program finishes. As soon as the PID is freed, Linux thus re-uses the PID 1323. A trash-cleaner program (I know, I know) gets confused. 1323 exited uncleanly. The cleaner sees no 1323 running. It then proceeds to delete the temp files. But, by that time, the kernel started another 1323 which happens to use the very files. The cleaner ends up deleting files for the wrong, running program! This is just one example. There are many more examples of race conditions. A TINY TWEAK AS SOLUTION: The kernel already tries to do the right thing. The only minor tweak needed is that: ***When Linux Re-Uses A Pid, It Uses The Pid That Has Been Free For The Longest.*** That's it! RESULT: All PID-related race conditions are eliminated, period. No "good enough" hacks needed any more by utilities trying to avoid race conditions. A freshly freed PID will never get re-used immediately any more . No more race conditions. (The only time you will ever see an immediate re-use any more is when your machine actually has 32767(!) or (2^22-1) processes! And, by that time, you have FAR bigger problems.) ---- **** DETAILS: You don't have to google very much to see the 1000 algos and other bashisms that exist to avoid the very race condition. For example, when you want to read a PID list and deleting temporary files based on a PID. The concern is that Linux might have created a new process with the same PID by the time you read the file-list. We could argue endlessly that these bashisms are stupid and there are better ways. But, it seems to me that these better ways are not foolproof either; they are themselves hacks. And, a very simple tweak could alleviate 100% of these problems. Now, 32768, or even 2^22 are actually very small numbers. OTOH, 2^200 is not. In an ideal world, the PID would just sample from the 2^200 space and declare that there will never be PID re-use or conflicts, period. If there's a 32-bit limit, it could use multiple bytes and still use a 2^200 space, etc. But, all that would be a drastic change, which is why we are stuck with the 2^15 space. Is there a way to continue using the 2^15 (or 2^22) space, but more reasonably? I argue that the kernel already tries to satisfy a "PID-AIM" and already tries to Do The Right Thing, but there's just a tiny thinko in its current implementation that's easily corrected. PID-AIM: "No immediate re-use." The aim is to NOT immediately re-use a PID right after it's been freed. I argue that this aim can easily be satisfied, even within the limited 2^15 space. CURRENT IMPLEMENTATION: The creators had the right idea. Linux indeed tries to satisfy the PID-AIM condition. This is why it increments the counter even if the PID is actually available. But, looping happens (within a few hours for me). And, as soon as looping happens, satisfying the PID-AIM goes out the window. This tweak would ensure that immediate re-use never happens, period. COMPLEXITY, ETC: All that the entire system needs is one queue of free PIDs. Any time you need a PID, take it from the head. Any time a PID is newly freed, push it at the back of the queue. That's it! The overhead seems minimal to me. The queue is initially populated by 2-32768, of course. In fact, we could even use a smaller queue and not even activate the queue-mode till it is actually necessary; we could use various optimizing conditions and shortcuts, say, to push PIDs in the queue in batches. After all, it's not STRICTLY necessary to maintain exactly the correct order. The ONLY aim we really want to satisfy is that the latest-freed PID NOT go near the *head* of the queue; that's all. Also, the queue is only even needed in the first place until you've actually looped around. So, tiny rescue disk bootups would not even need to go the queue-mode.. (unless they've been running many days.) (Thanks to jd_1 and _mjg on for humoring and discussing this idea when I presented it on ##kernel.) Dave Goel (Please CC responses.) -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/