5 ms·

The Real WTF is "to make pid collisions less likely", presumably to paper over a race condition triggered when a pid gets reallocated too quickly.

by im3w1l 7y ago

gdhgxhs 7y ago
No, it's because it isn't unreasonable to have more than 32,768 processes on a sufficiently large host.
- im3w1l 7y ago
  I quoted from the code comment.
londons_explore 7y ago
If you have a 64 bit PID, and guarantee they will never be reused, you have just eliminated a whole slew of race conditions and security vulnerabilities, and can probably eliminate a lot of other code designed to avoid said things.
- zaarn 7y ago
  I would go for a 128bit PID; a 64bit PID runs danger of collision if 2^32 processes have been created and killed. A 128bit PID is unlikely to ever collide and you can write code with the assumption that a PID is uniquely identifying to a process and will not be reused or collide in any reasonable timeframe (100 years or so).
  - im3w1l 7y ago
    The pids are allocated sequentially rather than randomly, so birthday paradox isn't an issue here.
    - zaarn 7y ago
      If going for big PIDs I'd do random assignment, means people will stop doign any kind of assumption about PIDs and stops potential side-channel leakage.
      - londons_explore 7y ago
        You can still do random assignment but never allocate the same ID twice. There are a bunch of methods to do that quickly and securely - for example use the result of encrypting a counter with a key only the kernel knows. There are benefits to sequential allocation - for one thing, the PID doesn't need to be stored anywhere (which can matter on very low memory machines), and optimizations can be made when there are only a handful of PID's.
        perl4ever 7y ago
        "There are a bunch of methods to do that quickly and securely - for example use the result of encrypting a counter with a key only the kernel knows." That isn't a guarantee, technically though, is it? And if you consider it guaranteed, then why wouldn't a (P)RNG be just as trustworthy? Is there a mathematical argument why it's better?
        wahern 7y ago
        For the inner parts of a cipher (before you get into "modes"), it is guaranteed. A cipher's transformation has to be reversible, otherwise you can't decrypt. If different inputs produce the same output, then it's not reversible. Block cipher modes like CTR, CBC, etc, are built by combining this basic, reversible building block--a permutation--with additional state. The modes provide additional features, but they necessarily require additional state so that transformations are reversible. Stream ciphers, like RC4, have implicit state, such that to decrypt you have to iterate the function from the beginning state. Modern stream ciphers are built more like CTR-mode block ciphers. You can build reversible transformations from non-reversible functions, such as a one-way hash function, using methods like the Feistel construction (https://en.wikipedia.org/wiki/Feistel_cipher https://en.wikipedia.org/wiki/Feistel_cipher), which was the traditional method for building block ciphers. For my DNS library I used a simple, 16-bit Feistel "cipher" to generate non-repeating QIDs.[1] Most DNS libraries shuffle a 65536-element array (e.g. using a Knuth shuffle), or keep a 65536-bit set to filter values generated by a PRNG. I preferred the cipher approach because the only state necessary was a single integer "key" for each DNS query context, which may need to send a small number of packets to resolve a record. Plus I got to try out a new technique. [1] Non-repeating until you've cycled through all 2^16 values. But even a cryptographically secure permutation becomes increasingly easier to guess the more values you can observe. And of course if you can observe the whole series then you can always guess with 100% accuracy successive values--it just cycles again. For my DNS library I got to generate a new key for every context, which resulted in a new permutation. But for system PIDs it's self-defeating to use a new key to produce a new permutation; the whole point was to avoid having to deal with potential collisions. That's why operating systems like OpenBSD don't bother with this technique for generating random PIDs or ephemeral port numbers.
jraph 7y ago
It immediately made me think about CRIU - Checkpoint / Restore in Userspace [1], which needs to be able to restore a process with the same PID as when the checkpoint is taken. When restoring, if a process already has this PID, restoring fails. [1] https://criu.org/ https://criu.org/
- touisteur 7y ago
  More and more I wonder if the future of criu isn't all namespaces...
  - jraph 7y ago
    They do advise using namespaces, and one of their main use cases is indeed docker container migration.
    - touisteur 7y ago
      Thanks for the info. Do you know where to find recent news and follow the progress of the criu project?
      - jraph 7y ago
        Sorry, I just noticed your comment. Upvoting you, hoping that you will notice mine. Unfortunately I don't know anything specific, I haven't followed CRIU. I noticed they did a number of releases during the last years, since I needed to compile CRIU for work. I would take a look at their website [1], it seems to list recent events and they have a mailing list. [1] https://criu.org/Main_Page https://criu.org/Main_Page
zaarn 7y ago
There is quite a few fun bugs you can have. HTOP can race when it reads the process PID and then tries to kill it. If in the meantime, that process dies and a new process gets it's PID, then HTOP will kill the wrong process. There is procfd's nowadays that let you have a consistent handle on a specific process, but it doesn't solve the problem for anything that looks at PIDs. It also naturally limits you to hosting only 32K processes; my browser at work consumes almost 1000 PIDs mainly via a lot of threads running at the same time. At home where I have even more tabs open, it's likely that it is getting close to 5000 threads running. Of those 32K processes, only 27k remain, which is a significant chunk. I believe PID is a bit of a dated way to refer to processes and ultimately we should move to opaque process handles (like procfd).
- im3w1l 7y ago
  Do all syscalls that take a pid have a procfd equivalent?
  - zbentley 7y ago
    No.
- JdeBP 7y ago
  Like the procdesc system on FreeBSD, which has some rather unfortunate semantics though. (Closing last open descriptors kills processes, by default.) One could make a collection of bugs that are revealed by (quite normal) process ID re-use. One of particular note in this context is the bug that occurs when one is using Linux control groups in lieu of proper job objects (which Linux does not have) and trying to do what on an actual first-class job object would be a "terminate all processes in this job" system call. * http://jdebp.uk./FGA/linux-control-groups-are-not-jobs.html http://jdebp.uk./FGA/linux-control-groups-are-not-jobs.html * https://github.com/systemd/systemd/issues/6803 https://github.com/systemd/systemd/issues/6803

The Real WTF is "to make pid collisions less likely", presumably to paper over a race condition triggered when a pid gets reallocated too quickly.

by im3w1l 7y ago

The Real WTF is "to make pid collisions less likely", presumably to paper over a race condition triggered when a pid gets reallocated too quickly.

gdhgxhs 7y ago

No, it's because it isn't unreasonable to have more than 32,768 processes on a sufficiently large host.

im3w1l 7y ago
I quoted from the code comment.

londons_explore 7y ago

If you have a 64 bit PID, and guarantee they will never be reused, you have just eliminated a whole slew of race conditions and security vulnerabilities, and can probably eliminate a lot of other code designed to avoid said things.

zaarn 7y ago
I would go for a 128bit PID; a 64bit PID runs danger of collision if 2^32 processes have been created and killed. A 128bit PID is unlikely to ever collide and you can write code with the assumption that a PID is uniquely identifying to a process and will not be reused or collide in any reasonable timeframe (100 years or so).
- im3w1l 7y ago
  The pids are allocated sequentially rather than randomly, so birthday paradox isn't an issue here.
  - zaarn 7y ago
    If going for big PIDs I'd do random assignment, means people will stop doign any kind of assumption about PIDs and stops potential side-channel leakage.
    - londons_explore 7y ago
      You can still do random assignment but never allocate the same ID twice. There are a bunch of methods to do that quickly and securely - for example use the result of encrypting a counter with a key only the kernel knows. There are benefits to sequential allocation - for one thing, the PID doesn't need to be stored anywhere (which can matter on very low memory machines), and optimizations can be made when there are only a handful of PID's.
      - perl4ever 7y ago
        "There are a bunch of methods to do that quickly and securely - for example use the result of encrypting a counter with a key only the kernel knows." That isn't a guarantee, technically though, is it? And if you consider it guaranteed, then why wouldn't a (P)RNG be just as trustworthy? Is there a mathematical argument why it's better?
        wahern 7y ago
        For the inner parts of a cipher (before you get into "modes"), it is guaranteed. A cipher's transformation has to be reversible, otherwise you can't decrypt. If different inputs produce the same output, then it's not reversible. Block cipher modes like CTR, CBC, etc, are built by combining this basic, reversible building block--a permutation--with additional state. The modes provide additional features, but they necessarily require additional state so that transformations are reversible. Stream ciphers, like RC4, have implicit state, such that to decrypt you have to iterate the function from the beginning state. Modern stream ciphers are built more like CTR-mode block ciphers. You can build reversible transformations from non-reversible functions, such as a one-way hash function, using methods like the Feistel construction (https://en.wikipedia.org/wiki/Feistel_cipher https://en.wikipedia.org/wiki/Feistel_cipher), which was the traditional method for building block ciphers. For my DNS library I used a simple, 16-bit Feistel "cipher" to generate non-repeating QIDs.[1] Most DNS libraries shuffle a 65536-element array (e.g. using a Knuth shuffle), or keep a 65536-bit set to filter values generated by a PRNG. I preferred the cipher approach because the only state necessary was a single integer "key" for each DNS query context, which may need to send a small number of packets to resolve a record. Plus I got to try out a new technique. [1] Non-repeating until you've cycled through all 2^16 values. But even a cryptographically secure permutation becomes increasingly easier to guess the more values you can observe. And of course if you can observe the whole series then you can always guess with 100% accuracy successive values--it just cycles again. For my DNS library I got to generate a new key for every context, which resulted in a new permutation. But for system PIDs it's self-defeating to use a new key to produce a new permutation; the whole point was to avoid having to deal with potential collisions. That's why operating systems like OpenBSD don't bother with this technique for generating random PIDs or ephemeral port numbers.

jraph 7y ago

It immediately made me think about CRIU - Checkpoint / Restore in Userspace [1], which needs to be able to restore a process with the same PID as when the checkpoint is taken. When restoring, if a process already has this PID, restoring fails. [1] https://criu.org/ https://criu.org/

touisteur 7y ago
More and more I wonder if the future of criu isn't all namespaces...
- jraph 7y ago
  They do advise using namespaces, and one of their main use cases is indeed docker container migration.
  - touisteur 7y ago
    Thanks for the info. Do you know where to find recent news and follow the progress of the criu project?
    - jraph 7y ago
      Sorry, I just noticed your comment. Upvoting you, hoping that you will notice mine. Unfortunately I don't know anything specific, I haven't followed CRIU. I noticed they did a number of releases during the last years, since I needed to compile CRIU for work. I would take a look at their website [1], it seems to list recent events and they have a mailing list. [1] https://criu.org/Main_Page https://criu.org/Main_Page

zaarn 7y ago

There is quite a few fun bugs you can have. HTOP can race when it reads the process PID and then tries to kill it. If in the meantime, that process dies and a new process gets it's PID, then HTOP will kill the wrong process. There is procfd's nowadays that let you have a consistent handle on a specific process, but it doesn't solve the problem for anything that looks at PIDs. It also naturally limits you to hosting only 32K processes; my browser at work consumes almost 1000 PIDs mainly via a lot of threads running at the same time. At home where I have even more tabs open, it's likely that it is getting close to 5000 threads running. Of those 32K processes, only 27k remain, which is a significant chunk. I believe PID is a bit of a dated way to refer to processes and ultimately we should move to opaque process handles (like procfd).

im3w1l 7y ago
Do all syscalls that take a pid have a procfd equivalent?
- zbentley 7y ago
  No.
JdeBP 7y ago
Like the procdesc system on FreeBSD, which has some rather unfortunate semantics though. (Closing last open descriptors kills processes, by default.) One could make a collection of bugs that are revealed by (quite normal) process ID re-use. One of particular note in this context is the bug that occurs when one is using Linux control groups in lieu of proper job objects (which Linux does not have) and trying to do what on an actual first-class job object would be a "terminate all processes in this job" system call. * http://jdebp.uk./FGA/linux-control-groups-are-not-jobs.html http://jdebp.uk./FGA/linux-control-groups-are-not-jobs.html * https://github.com/systemd/systemd/issues/6803 https://github.com/systemd/systemd/issues/6803