David Laight implemented a new algorithm for pid allocation and proc/pgrp lookups. Main benefits include that searches aren't required when doing pid and pgrp lookups by id, smaller footprint, better scalability, and cleaner locking.

As he explained in his announcement mail:

"The basic idea is to ensure that you allocate a pid number which
references an empty slot in the lookup table. To do this a FIFO freelist
is linked through the free slots of the lookup table."

From: David Laight
To: tech-kern
Subject: new pid allocation code
Date: 03/11/2003 14:36:30

Hackers,

The code below implements a different pid allocation and proc/pgrp
lookup algorithm.

The main benefits are:
- pid and pgrp lookup (by id) doesn't require a search
- no dependency on MAXUSERS
- automatically scales well to large numbers of processes
- small data footprint for small systems
- ability to enumerate through all the processes without holding a lock
  for the entire duration, or having very messy locking rules.
  (the allproc list and p_list fields could be depracted later).

- Largely MP clean

The basic idea is to ensure that you allocate a pid number which
references an empty slot in the lookup table.  To do this a FIFO freelist
is linked through the free slots of the lookup table.
To avoid reusing pid numbers, the top bits of the pid are incremented
each time the slot is reused (the last value is kept in the table).
If the table is getting full (ie a pid would be reused in a relatively
small number of forks), then the table size is doubled.
Orphaned pgrps correctly stop the pid being reused, orphaned sessions
keep the pgrp allocated.

Below is the main part of the change, there are other bits lurking
in fork and exit.  If people think this code is ok, I'll sort out a
full diff against 'current' (and fix for sparc64).

(I've been running this code for months!)

	David

The full announcement, which includes the patch, can be found here