hi folks,

I found that there are yet more scalability problems that show up with
the fork+exit microbenchmark, this time in the pool code.  there are two
problems:

 (1) we have a single list for all the pages allocated to a pool, which we
     traverse at various times looking for a page to allocate from.

 (2) each pool has an 8-bucket hash table for page headers that don't
     fit nicely in the page itself.


the diff at ftp://ftp.netbsd.org/pub/NetBSD/misc/chs/diff.pool
fixes these problems by:

 (1) split the list of pages allocated to a pool into three lists:
     completely full, partially full, and completely empty.
     there is no longer any need to traverse any list looking for a
     certain type of page.

 (2) replace the hash table with a splay tree.  yes, this is probably
     not the ideal data structure for this, but it'll do until we have
     something better, and it's not measurably worse in this context
     than the hash table when there are few entries.


after these changes (and david's changes to child-tracking), we have
linear scaling for the fork+exit benchmark.  the profile looks like:

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
  8.07      0.41     0.41  2475675     0.17     0.17  pvtree_SPLAY
  7.09      0.77     0.36                             Xspllower
  5.71      1.06     0.29    40032     7.24     7.24  memcpy
  3.74      1.25     0.19   663043     0.29     0.56  pmap_enter
  3.35      1.42     0.17   192230     0.88     7.16  uvm_fault
  2.36      1.54     0.12   769850     0.16     0.16  lockmgr
  2.17      1.65     0.11     8000    13.75    35.21  uvmspace_fork
  1.77      1.74     0.09    64044     1.41     6.53  pmap_remove_ptes
  1.57      1.82     0.08  2517396     0.03     0.03  uvm_rb_subtree_space
  1.38      1.89     0.07   184333     0.38     6.68  trap
  1.18      1.95     0.06   832428     0.07     0.07  pmap_extract
  1.18      2.01     0.06     8003     7.50     8.09  sigactsinit
  1.18      2.07     0.06                             Xtrap0e


-Chuck