A new page allocator for UVM

[Andrew Doran <ad%netbsd.org@localhost>]

Hi,

Anyone interested in taking a look?  This solves the problem we have with
uvm_fpageqlock.  Here's the code, and the blurb is below:

	http://www.netbsd.org/~ad/2019/allocator.diff

Cheers,
Andrew


General overview

	The page allocator currently works in 4 dimensions, with freelist
	being the most important consideration, page colour the next, and so
	on.  It has a global counter tracking the number of free pages.

	uvm -> freelist[f] -> colour[c] -> queue[q] +-> global list
	                                            \-> local CPU list

	uvm -> uvmexp.free

	It turns out that this allocator has a "lock contention problem",
	which is actually more of a false sharing problem, because
	allocating a page involves touching and writing back to many cache
	lines.

	The new allocator is reduced to working in 3 dimensions.  The
	separate lists for zeroed/unknown pages have been deleted (but the
	ability to track whether an individual page is zeroed is retained),
	the CPU free lists have been deleted, and a new concept of "bucket"
	introduced.  Again freelist is the most important consideration,
	bucket is the next, and colour the last (* unless the experimental
	NUMA stuff is enabled, but that's disabled for now).

	uvm -> freelist[f] -> bucket[b] -> colour[c]
	                         \
	                          -> pgb_nfree

	The data structures to manage this are carefully arranged so that
	there's minimal false sharing, fewer write backs need to occur, and
	empty freelists (of which there are often many) can be skipped
	quickly without having to scan everything nor take locks.

Buckets

	In both old & new allocators we have the ability to dynamically
	rearrange the free lists to support an arbitrary number of page
	colours.  Buckets work this way too but there is a maximum number
	(PGFL_MAX_BUCKETS, currently 8).

	The number of buckets is sized at runtime according to the number of
	physical CPU packages in the system (ci->ci_package_id), and each
	logical CPU is assigned a preferred bucket to allocate from
	(ucpu->pgflbucket).

	This does a few things for us (when the system is not very low on
	memory):

	- It exponentially reduces lock contention by reducing the number of
	  CPUs competing for access to each bucket.

	- The lock and data structures for each bucket typically remain in
	  cache somewhere on the chip, and thereby don't need to go over the
	  bus, further reducing contention.

	- It has a positive effect on L2/L3 cache locality, because if we
	  free pages back to a bucket corresponding to the CPU where they
	  were last used, the pages held in free list are very likely to be
	  in cache on the chip they will next be allocated from.  The
	  current allocator has a problem where logical CPUs "hoard" L2/L3
	  cache by having their own free lists.

Experimental rudimentary NUMA support

	I thought it would be interesting to try this, just for fun.

	This changes the configuration of the buckets to correspond to NUMA
	node, assigns pages to buckets according to which node the hardware
	tells us they live on, changes the strategy for freeing pages so
	that pages ALWAYS go back to their assigned bucket, instead of
	moving about as they do with the L2/L3 strategy, and changes the
	strategy for allocating so that we consider allocating from the
	correct bucket to be more important than allocating from the correct
	free list.

	I have disabled this for now even if NUMA is enabled on the system
	because it's not quite there yet and more testing needs doing.  It
	does seem to work though (for a compile job).

Per-cpu caching

	There is a tiny per-CPU caching layer that can be paused and resumed
	at runtime, and it's only enabled when CPUs are sharing buckets. 
	This functions as a buffer, where pages are shuffled to and from
	buckets in batch.  On a typical Intel system, about 224kB worth of
	pages will be cached.  That's not much, but is enough to further
	reduce lock contention by an order of magnitude without exerting too
	much pressure on the L2/L3 cache by hoarding.

Idlezero

	I have removed the guts of this, but the hooks to support it are
	still in place.  I think it may be useful to experiment with zeroing
	the per-CPU cached pages, or try some other method, but what we have
	now doesn't work well on modern systems.

How this looks in practice

	Here is what the freelists look like on my system, and the dmesg
	from said system.

	http://www.netbsd.org/~ad/2019/freelist.txt
	http://www.netbsd.org/~ad/2019/dmesg.boot

Results:

	This from a "make -j96" kernel build, with a !DIAGNOSTIC, GENERIC
	kernel on the system mentioned above.  System time is the most
	interesting here.  With NUMA disabled in the BIOS:

	       74.55 real      1635.13 user       725.04 sys	before
	       72.66 real      1653.86 user       593.19 sys	after

	With NUMA enabled in the BIOS & the allocator:

	       76.81 real      1690.27 user       797.56 sys	before
	       71.10 real      1632.42 user       603.41 sys	after

	Lock contention before (no NUMA):

	Total%  Count   Time/ms          Lock          
	------ ------- --------- ----------------------
	 99.80 36756212 182656.88 uvm_fpageqlock       

	Lock contention after (no NUMA):

	Total%  Count   Time/ms          Lock
	------ ------- --------- ----------------------
	 20.21  196928    132.50 uvm_freelist_locks+40  <all>
	 18.72  180522    122.74 uvm_freelist_locks     <all>