23

Let say, from kernel 2.6 onwards.

I watch all the running processes on the system.

Are the PID of the children always greater than their parents' PIDs?

Is it possible to have special cases of "inversion"?

ilkkachu
  • 138,973
Massimo
  • 985

2 Answers2

47

No, for the very simple reason that there is a maximum numerical value the PID can have. If a process has the highest PID, no child it forks can have a greater PID. The alternative to giving the child a lower PID would be to fail the fork() altogether, which wouldn't be very productive.

The PIDs are allocated in order, and after the highest one is used, the system wraps around to reusing the (free) lower ones, so you can get lower PIDs for a child in other cases too.

The default maximum PID on my system (/proc/sys/kernel/pid_max) is just 32768, so it's not hard to reach the condition where the wraparound happens.

$ echo $$
27468
$ bash -c 'echo $$'
1296
$ bash -c 'echo $$'
1297

If your system were to allocate PIDs randomly (like OpenBSD appears to do) instead of consecutively (like Linux), there would be two options. Either the random choice was made over the whole space of possible PIDs, in which case it would be obvious that a child's PID can be lower than the parent's. Or, the child's PID would be chosen by random from the values greater than the parent's PID, which would on average put it halfway between the parent's PID and the maximum. Processes forking recursively would then quickly reach the maximum and we'd be at the same point as mentioned above: a new fork would need to use a lower PID to succeed.

ilkkachu
  • 138,973
  • 3
    FWIW, there exists systems where the PIDs are allocated randomly (by default on OpenBSD for example), and I'm sure I've seen a similar PID allocation scheme on Linux as well (or at least seen one suggested). – Kusalananda Sep 04 '18 at 11:31
  • @Kusalananda, yeah, I think there's been a question about that on unix.SE, too. I don't have the time to dig it up, but as far as I remember, the patch for Linux that did random PID choosing was old and abandoned as unnecessary. It doesn't matter though: as long as there's a (relatively low) maximum PID, once it's used the choices are either to give a lower PID, or drop an error on the fork. – ilkkachu Sep 04 '18 at 11:36
  • https://unix.stackexchange.com/questions/206096/how-to-enable-random-pids-on-linux and https://unix.stackexchange.com/questions/401327/what-determines-what-pid-a-process-will-be-assigned/401331#401331 for starters – Jeff Schaller Sep 04 '18 at 11:39
  • I read once upon a time of the rollover. I don't know about randomization (like in many other places, for security). thks – Massimo Sep 04 '18 at 13:05
  • 2
    @Massimo, the security aspect is discussed in this question on security.se: Do randomized PIDs bring more security? – ilkkachu Sep 04 '18 at 14:10
  • @ilkkachu: Regardless of whether they bring more security, they quickly catch bugs from bad assumptions like the one OP asked about. – R.. GitHub STOP HELPING ICE Sep 04 '18 at 19:29
  • Why is pid_max so low? I thought they boosted it to 2GB 15 years ago or more... – RonJohn Sep 05 '18 at 06:03
  • 1
    @RonJohn, well, I don't what values other Linuxes put there, but it's modifiable, you can set it to about 4 million (4194304, or 2^22) on 64-bit systems. (it's a number, not an amount of bytes) – ilkkachu Sep 05 '18 at 07:37
8

Also there exists the potential for security vulnerabilities using kernel notifications and forking yourself to avoid detection by a process table scan; this if done right results in your process having a lower PID and process tools not seeing the process in question.

http://cve.circl.lu/cve/CVE-2018-1121

procps-ng, procps is vulnerable to a process hiding through race condition. Since the kernel's proc_pid_readdir() returns PID entries in ascending numeric order, a process occupying a high PID can use inotify events to determine when the process list is being scanned, and fork/exec to obtain a lower PID, thus avoiding enumeration. An unprivileged attacker can hide a process from procps-ng's utilities by exploiting a race condition in reading /proc/PID entries. This vulnerability affects procps and procps-ng up to version 3.3.15, newer versions might be affected also.

thrig
  • 34,938