> Stupid question: shouldn't it be KEY_SPEC_PROCESS_KEYRING rather than KEY_SPEC_THREAD_KEYRING ?
Not a stupid question.
It doesn't really matter; the distinction between 'thread' and 'process' on linux is very thin: `CLONE_THREAD` and `CLONE_VM` are independant.
I chose to use `KEY_SPEC_THREAD_KEYRING` to err on the safe side.
In the back of my mind I also considered that thread-local would be 'more' local than process-local, and hence might be faster inside the kernel (but this is unverified).
Unless `madvise(ptr, size, MADV_DONTFORK)' is used. But in this case you have no information at all on the region (which may have been mapped by another library), but I might not have understood the initial OP suggestion.
No, I meant MAP_SHARED. That way the seed is shared across all forks and will only cause problems if the PRNG is being used as a cipher.
However there's another trick. If you have two counters: One in MAP_PRIVATE and one in MAP_SHARED you can detect the unsafe scenario by incrementing each counter and verifying lockstep.
If the counters mismatch, you've been forked: unmap and map new pages, and do whatever post-fork "reinitialisation" that is required.
That doesn't work because there's a race condition - if both processes increment the MAP_SHARED counter at the same time, they could end up seeing the same value and not think that a fork has occurred.
> The counters don't need to be 64-bits: Programs don't need a random number in one process and the 4 billionth only.
If this is going to be used for a CSPRNG, you have to take into account adversarial conditions. A 32 bit counter leaves insufficient safety margin: it's conceivable an attacker could induce an application to generate so many random numbers that the counter wraps around, causing another process to generate a duplicate random number. It may seem unlikely, but time after time security researchers have demonstrated that attacks previously considered "unlikely" are possible.
No they don't. 2 pages are used for each child that needs a random number from the shared seed, during the scope of the parent needing the seed. This is insignificant, and one of the pages can contain the seed.
The Right Thing is to have a "prng_init()" routine, since the program that fork()s will know what it needs to do.
This is pretty amazing. I can't decide if the right response is "<3" or "sigh", but it's one of those.
Is this the best way you know of? I'm reminded of how the best way to answer "is this process single-threaded" on Linux is apparently to stat /proc/self/task, which I suggested satirically to a friend but turned out to be the closest thing to a right answer.
You can tell (without a syscall!) if between two points there has been a fork or thread created by maintaining two counters: One in a MAP_SHARED and one in MAP_PRIVATE.
Every check, increment both counters, then compare them. If they disagree, then one of those pages has been copied (the MAP_PRIVATE) and one has not (MAP_SHARED).
The only way it could work is if you were guaranteed to also call check_fork synchronously in the parent. But if you had that degree of control over forks, then you just know when your forks are and you don't need these tricks.
The use case here is in an external library (e.g., OpenSSL) where it might be called post-fork by a semi-naive user of the library, or where the library might explicitly want to be usable post-fork (e.g., Apache prefork serving) and need to adjust some state. If you expect the caller to reliably inform the library of forks, then you don't need any trickery.
Another use case that I'm interested in is signal handlers, which could be delivered immediately post-fork. If your handler does something like write to a file descriptor (which is very common), those file descriptors mean something different in the parent and the child, so if the post-fork code in the child was in the middle of switching out file descriptors before exec, you might accidentally write to the wrong thing. So you want to be sure that you're still in the same process before writing to a particular file descriptor. UNIX doesn't offer a way to reset signal handlers on fork, unfortunately.
The algorithm works, though it doesn't distinguish between the parent and child - the first process to call check_fork() after the fork will return false, and the second process to call it will return true. (Note that upon returning true, it should remap and reset the state.) This is sufficient for the use case of reseeding a PRNG, though not for your signal handler/file descriptor use case.
The problem with the algorithm (which I'm discussing on another subthread) is that the increment of the shared counter needs to be atomic, and the integers need to be 64 bits to avoid wraparound, and I'm not sure that all architectures support atomic 64 bit increments.
Edit: I just realized that check_fork() would spuriously return true in the first process after the second process calls it, which isn't so nice. Maybe this can be prevented by comparing before you increment, but then I think there might be a race condition? It would be helpful if geocar could provide some pseudocode so we're not left guessing how the algorithm works.
Ah, gotcha, it works for a different use case from mine (but a valid one). And yes, I'd like to see code using well-defined atomic operations and orderings / barriers.
As agwa pointed out, it does work, but with a different definition of work (i.e., a different use case). The use case is for, say, a callback that might be called from different sides of fork, but shouldn't be. If you run this algorithm at the top of your callback, one side of fork will arbitrarily be okay, but the other side of fork will report a discrepancy between the two values. For some applications, that's all you need to know.
If the forking library never calls into your code from two different sides of fork, then that's fine (for this use case), and your algorithm will never detect a fork: as long as your code is only called from one side of every fork, the two numbers will stay in sync.
The use case is something like a random seed, where you don't want to branch the same seed into two timelines. If you follow only one timeline, that's acceptable, even if there are other timelines.
(This algorithm doesn't handle multiple threads either, I think.)
* Create an empty temporary file and set a fcntl(F_SETLK) lock on the whole thing. Those locks don't get inherited to child processes. Use fcntl(F_GETLK) to see if you can re-set that lock: if you can, you must be in the same process.
The downside of this approach is that it involves a file descriptor, and lots of post-fork code tends to like doing a `for i in 0..MAXFD {close(i);}` loop. You could instead store a path to the temporary file in global memory, but that might be more expensive than you'd like.
* Fork a child that sits around forever, e.g. on pause(). Then try to waitpid(WNOHANG) on it. If that returns ECHILD, you're no longer the parent of that child. I think this is reliable and portable, but incredibly ugly.
Sadly the kernel keyring option is looking like a better one than both of these.
Yeah, I'm asking a different question than the one that the post alludes to. I need to know from library code when I am on the `fork() == 0` side of a fork -- not just when I'm on a different side than I was previously on. (I'm writing a self-pipe signal handler, not a PRNG.) I don't think there's any way to answer my question without a syscall -- even the most naive approach uses getpid(). The post's solution works for my problem, but it uses a syscall.
Syscalls ought to be pretty fast: without benchmarking, I don't think I'd assume that the cost of a syscall like getpid() is going to be slower than the cost of a copy-on-write fault for a MAP_PRIVATE page, since they both require kernel entry. Especially on systems where there's a syscall instruction instead of going through the full exception path, syscall-and-read-structure sounds faster than exception-and-remap-page.
28 comments
[ 44.2 ms ] story [ 1307 ms ] threadNot a stupid question.
It doesn't really matter; the distinction between 'thread' and 'process' on linux is very thin: `CLONE_THREAD` and `CLONE_VM` are independant.
I chose to use `KEY_SPEC_THREAD_KEYRING` to err on the safe side. In the back of my mind I also considered that thread-local would be 'more' local than process-local, and hence might be faster inside the kernel (but this is unverified).
I assume you mean MAP_PRIVATE?
But that doesn't work. MAP_PRIVATE pages are copied to a fork.
However there's another trick. If you have two counters: One in MAP_PRIVATE and one in MAP_SHARED you can detect the unsafe scenario by incrementing each counter and verifying lockstep.
If the counters mismatch, you've been forked: unmap and map new pages, and do whatever post-fork "reinitialisation" that is required.
Also, the counters would need to be 64 bits so that wraparound isn't a concern. Do all architectures even have an atomic 64 bit increment?
The counters don't need to be 64-bits: Programs don't need a random number in one process and the 4 billionth only.
I have no clue what point you're trying to make.
> The counters don't need to be 64-bits: Programs don't need a random number in one process and the 4 billionth only.
If this is going to be used for a CSPRNG, you have to take into account adversarial conditions. A 32 bit counter leaves insufficient safety margin: it's conceivable an attacker could induce an application to generate so many random numbers that the counter wraps around, causing another process to generate a duplicate random number. It may seem unlikely, but time after time security researchers have demonstrated that attacks previously considered "unlikely" are possible.
I'm not sure if this is workable...
The Right Thing is to have a "prng_init()" routine, since the program that fork()s will know what it needs to do.
Is this the best way you know of? I'm reminded of how the best way to answer "is this process single-threaded" on Linux is apparently to stat /proc/self/task, which I suggested satirically to a friend but turned out to be the closest thing to a right answer.
Every check, increment both counters, then compare them. If they disagree, then one of those pages has been copied (the MAP_PRIVATE) and one has not (MAP_SHARED).
The use case here is in an external library (e.g., OpenSSL) where it might be called post-fork by a semi-naive user of the library, or where the library might explicitly want to be usable post-fork (e.g., Apache prefork serving) and need to adjust some state. If you expect the caller to reliably inform the library of forks, then you don't need any trickery.
Another use case that I'm interested in is signal handlers, which could be delivered immediately post-fork. If your handler does something like write to a file descriptor (which is very common), those file descriptors mean something different in the parent and the child, so if the post-fork code in the child was in the middle of switching out file descriptors before exec, you might accidentally write to the wrong thing. So you want to be sure that you're still in the same process before writing to a particular file descriptor. UNIX doesn't offer a way to reset signal handlers on fork, unfortunately.
The problem with the algorithm (which I'm discussing on another subthread) is that the increment of the shared counter needs to be atomic, and the integers need to be 64 bits to avoid wraparound, and I'm not sure that all architectures support atomic 64 bit increments.
Edit: I just realized that check_fork() would spuriously return true in the first process after the second process calls it, which isn't so nice. Maybe this can be prevented by comparing before you increment, but then I think there might be a race condition? It would be helpful if geocar could provide some pseudocode so we're not left guessing how the algorithm works.
That's the neat thing about the original article: you can know if a fork happened outside of your own code.
If the forking library never calls into your code from two different sides of fork, then that's fine (for this use case), and your algorithm will never detect a fork: as long as your code is only called from one side of every fork, the two numbers will stay in sync.
The use case is something like a random seed, where you don't want to branch the same seed into two timelines. If you follow only one timeline, that's acceptable, even if there are other timelines.
(This algorithm doesn't handle multiple threads either, I think.)
* Create an empty temporary file and set a fcntl(F_SETLK) lock on the whole thing. Those locks don't get inherited to child processes. Use fcntl(F_GETLK) to see if you can re-set that lock: if you can, you must be in the same process.
The downside of this approach is that it involves a file descriptor, and lots of post-fork code tends to like doing a `for i in 0..MAXFD {close(i);}` loop. You could instead store a path to the temporary file in global memory, but that might be more expensive than you'd like.
* Fork a child that sits around forever, e.g. on pause(). Then try to waitpid(WNOHANG) on it. If that returns ECHILD, you're no longer the parent of that child. I think this is reliable and portable, but incredibly ugly.
Sadly the kernel keyring option is looking like a better one than both of these.
Mine wastes a syscall in the worst-case scenario and always reinitialises the prng when it is used after a fork.
For background, see https://www.redhat.com/archives/libvir-list/2008-August/msg0...
Syscalls ought to be pretty fast: without benchmarking, I don't think I'd assume that the cost of a syscall like getpid() is going to be slower than the cost of a copy-on-write fault for a MAP_PRIVATE page, since they both require kernel entry. Especially on systems where there's a syscall instruction instead of going through the full exception path, syscall-and-read-structure sounds faster than exception-and-remap-page.
Using getpid/gettid (or the keyring trick) you are doing a syscall for every check.