Bug 222639 - fork: Time it takes to allocate random PID approach infinity as num_processes approach PID_MAX (related to: sysctl kern.randompid)
Summary: fork: Time it takes to allocate random PID approach infinity as num_processes...
Status: New
Alias: None
Product: Base System
Classification: Unclassified
Component: kern (show other bugs)
Version: CURRENT
Hardware: Any Any
: --- Affects Only Me
Assignee: freebsd-bugs mailing list
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2017-09-27 10:07 UTC by Marie Helene Kvello-Aune
Modified: 2018-09-09 20:16 UTC (History)
3 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Marie Helene Kvello-Aune 2017-09-27 10:07:12 UTC
The current implementation of random PID generation is a bit opportunistic.
It currently generates a random value which is lastpid + (random_number capped to a max value of kern.randompid), but always at least 1 more than lastpid.
It then checks if this PID is available, and if not, tries again.

Therefore, as number of processes approach PID_MAX (i.e. number of available PIDs approach 0), the time to allocate a randomly generated PID approaches infinity.

Proposed solution:

Prequisite: Change how PIDs are tracked and allocated. Implement a bitmap of PIDs (I'm currently working on this) which is updated whenever anything in the PID namespace changes (a new PID/session ID/etc is created, or a PID/session ID/etc is considered available again). 
The bitmap should be an array of 4096 uint32_t where each bit represents a PID. A set (on) bit indicates an available PID.

New random PID generation algorithm:
Create an index of the bitmap consisting of 128 uint32_t. Each bit represents a single uint32_t in the bitmap, declaring whether it has any available PIDs.
When creating a random PID:
- Iterate the index and find all uint32_t which have at least one bit set.
- Select one of thee aforementioned at random.
- Select a random set bit from the selected, to decide which uint32_t in the bitmap to use for further selection.
- Select a random bit in the aforementioned to determine which PID to allocate.

Restrict allocation to lastpid < newpid < PID_MAX

I'm working on this, but describing it here so it's not lost. For feedback or just in case the "Bus Test" actually happens. ;)
Comment 1 Marie Helene Kvello-Aune 2018-09-09 19:53:51 UTC
Correction: PID randomization picks a random PID as described, but if it's not available, it'll increment the attempted PID by 1 and check if it's available again.
Comment 2 Conrad Meyer freebsd_committer 2018-09-09 20:16:19 UTC
(In reply to Marie Helene Kvello-Aune from comment #0)

> Prequisite: Change how PIDs are tracked and allocated. Implement a bitmap of PIDs
> (I'm currently working on this) which is updated whenever anything in the PID
> namespace changes (a new PID/session ID/etc is created, or a PID/session ID/etc
> is considered available again).
> The bitmap should be an array of 4096 uint32_t where each bit represents a PID.
> A set (on) bit indicates an available PID.

IIRC, there was some earlier effort to bitmap-ify PIDs.  I'm not sure where that went.  CC'ing Matt, who might remember if there is any work that can be reused (or if I am misremembering and the work got committed already).

If not, we have some abstractions for bitmaps in the kernel already which should probably be used in place of a raw u32 array — see BITSET(9) (if fixed size is ok) or vmem(9) (which in spite of the name is actually a general purpose allocater of integers in some range).  Apologies if you have already thought of this or discovered it since the 2017-09 description I responded to :-).