[Bug 222639] fork: Time it takes to allocate random PID approach infinity as num_processes approach PID_MAX (related to: sysctl kern.randompid)

[bugzilla-noreply at freebsd.org]

https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=222639

            Bug ID: 222639
           Summary: fork: Time it takes to allocate random PID approach
                    infinity as num_processes approach PID_MAX (related
                    to: sysctl kern.randompid)
           Product: Base System
           Version: CURRENT
          Hardware: Any
                OS: Any
            Status: New
          Severity: Affects Only Me
          Priority: ---
         Component: kern
          Assignee: freebsd-bugs at FreeBSD.org
          Reporter: marieheleneka at gmail.com

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. ;)

-- 
You are receiving this mail because:
You are the assignee for the bug.