Date:        Fri, 10 Nov 2000 13:04:07 -0500 (EST)
    From:        jchacon@genuity.net
    Message-ID:  <200011101804.NAA28270@dragon.tools.gtei.net>

  | Q: Why doesn't NetBSD implement random PID assignments like other free *IX's
  |    offer?
  | 
  | A: The stated reason this is done in other *IX's has often been touted as a
  |    security win. i.e. programs with exploits that depend upon pid guessing 
  |    are presumed to be harder to exploit when this feature is enabled.
  | 
  |    However under basic analysis this is shown to be false for a variety of
  |    reasons:


Which is all very fine, and true - but it assumes that the only reason
random pids might be useful is to pretend some increased security.

Not so - in some environments random pids can be faster to assign than
pid++ - the arithmetic in generating the next number is only dominant
if in the vast percentage of times it doesn't need to be repeated - otherwise
what matters is producing a new (unused) pid in as few attempts as possible,
almost irrespective of how much arithmetic is needed to actually create the
number.

The NetBSD algorithm (which doesn't look like it has changed since about
BSD4.2) works well when there are large blocks of unallocated (free) pids
available for use - which is going to be the common case in most workstation
(personal use type) systems, as well as in many of the timesharing type
systems that BSD started out on, and so is still a pretty good default for
NetBSD.    It is not very nice when you start getting lots of long
running processes sprinkled all through the pid space (it means way too
many linear scans through the process table).   There, a "random" pid
selection algorithm (well implemented, which probably means a bit map
of used/free pids) might just perform considerably better.

kre