external page headers use an RB tree to find the page header
authordlg <dlg@openbsd.org>
Mon, 18 Aug 2014 01:28:44 +0000 (01:28 +0000)
committerdlg <dlg@openbsd.org>
Mon, 18 Aug 2014 01:28:44 +0000 (01:28 +0000)
commit0a6fc1bd3878ab9c16a9596b1efe36689a65dd6b
tree53bb14cac6adeafc4ad3ffc1afd9587becc97607
parentfd2799592fbff2ac4ac7313db3b07e52661e362a
external page headers use an RB tree to find the page header
containing an item when its returned to the pool. this means you
need to do an inexact comparison between an items address and the
page address, cos a pool page can contain many items.

previously this used RB_FIND with a compare function that would do math
on every node comparison to see if one node (the key) was within the other
node (the tree element).

this cuts it over to using RB_NFIND to find the closest tree node
instead of the exact tree node. the node compares turns into simple
< and > operations, which inline very nicely with the RB_NFIND. the
constraint (an item must be within a page) is then checked only
once after the NFIND call.

feedback from matthew@ and tedu@
sys/kern/subr_pool.c