Allow purging oldest N dirty pages in regionAllocator.

This PR (is part 3 of 3) resolves https://github.com/snazzy-d/sdc/issues/270 .

Requires the following:

Part 1 of 3: https://github.com/snazzy-d/sdc/pull/335
Part 2 of 3: https://github.com/snazzy-d/sdc/pull/336

regionAllocator.purgeDirtyPages(uint pages) purges the given number of dirty pages, always starting from the oldest run of dirty pages known to the regionAllocator, and continuing to the next-oldest, if such exists, and so on. The total number of pages that was actually purged is returned.

All purging of dirty pages happens strictly by way of purgeDirtyPages.

Theory of Operation

addrRangeRegionCmp is altered in such a way that the invariant in Region.merge() holds during the operation of purgeDirtyPages and at all other times:

assert(!leftRegion.hasClean || !rightRegion.hasDirt,
       "Merge would place dirty pages in front of clean pages !");

That is, region merges that would produce (inside one region) a dirty run of pages after a clean run are prohibited, as such merges would render the scalar dirtySize inaccurate with respect to partitions: one could then no longer reliably calculate the dirt of segments obtained by partitioning a dirty region without an unnecessarily-complicated set of moving parts (e.g. bitmap for tracking dirties, and the need to walk through it.)

Hence, the following merge pattern is prohibited (i.e. adjacently contacting regions that match this pattern are not merged, but are treated as separate regions while the given dirt pattern continues to hold), shown from left to right:

| fully clean or partially dirty | fully or partially dirty |

Note: this situation can only result from calling purgeDirtyPages(), and even then, only under particular distributions of dirt. So the practical cost of this mechanism is negligible. An invocation of purgeDirtyPages will in all cases partially-purge at most one region (while fully purging all dirty regions, starting from the oldest, until reaching the requested purged page count.)

For dirtySize to be a meaningful scalar under all possible partitions of a region, the region must be defined in such a way that if it contains dirty pages, they form precisely one contiguous run of dirt, and the latter resides at the region's bottom.

Dirt patterns in a pair of adjacently-contacting regions which will allow for a meaningful scalar dirtySize after merging, result in an immediate merge of the regions when they are available and adjacently-contacting during registerRegion, and follow the normal merge rules:

| fully clean | fully clean |
| fully dirty | fully or partially dirty |
| fully or partially dirty | fully clean |

Adjacently-contacting regions that are considered unmergeable remain as distinct regions until they become mergeable on account of a purge of dirty pages (or, in some cases, the reuse of a region by acquire, when it may gain dirt upon release) : when a region is fully or partially purged by purgeDirtyPages, it is re-registered, and merged with its neighbours whenever this becomes newly possible.

The revised addrRangeRegionCmp maintains consistent partial ordering and does not interfere with the expected operation of the red-black tree.

A regionsByDirtAge is introduced, which at all times tracks all regions containing dirty pages (i.e. where dirtySize > 0) by dirtEpoch, which is sampled from a counter of the corresponding name, incremented by release whenever new dirt is created (i.e. a region has been released by the regionAllocator.) purgeDirtyPages always starts from the oldest, by this measure, run of dirty pages, and continues until the requested number of dirty pages has been purged, or there are no more dirty pages remaining to be purged. Any adjacent regions that had been prevented from merging on account of the |clean|dirty| rule are merged as their dirt is purged.

When two regions, one or both of which contains dirt, are merged, and one of the merged regions supplied 50% or more of the dirt, the merged region will have the dirtEpoch of that region. In all cases, the total dirt is equal to the sum of the individual regions' dirt.

All other rules from https://github.com/snazzy-d/sdc/pull/335 continue to apply.

snazzy-d / sdc

Allow purging oldest N dirty pages in regionAllocator. #337