Bug 446103 - Memcheck: `--track-origins=yes` causes extreme slowdowns for large mmap/munmap.
This patch rewrites the Level 2 origin-tracking cache (ocacheL2) so that
set-address-range-permissions (SARP) operations on it, for large ranges, are
at least a factor of 2.5 x faster. This is primarily targeted at SARPs in the
range of hundreds to thousands of megabytes. The Level 1 origin-tracking
cache covers 64MB address space, so SARPs that fit within it are mostly
unaffected. There are extensive comments in-line. Changes are:
* Change the Level 2 cache from a single AVL tree (OSet) into 4096 such trees,
selected by middle bits of the tag, hence "taking out" 12 significant bits
of search in any given tree.
* For the OCacheLine type, use a union so as to overlay the w32 and descr
arrays with an array of 64-bit values. This is used to speed up cases where
those fields are to be set to zero, or checked against zero.
* Due to the various fast-paths added by this patch, OC_BITS_PER_LINE has
pretty much been frozen at the current value, 5.
* ocache_sarp_Set_Origins, ocache_sarp_Clear_Origins: deal with large ranges
in 32-byte steps instead of 4-byte steps.
* MC_(helperc_b_store32), MC_(helperc_b_store16): rewrite these to be (much)
more efficient.
* fast-return cases for VG_(OSetGen_Lookup) and VG_(OSetGen_Remove) when the
tree is empty