fuse: resolve extent maps in O(1) when possible

fuse_ext_map_iomap_begin() runs on every mapping fault of a DAX
extent-mapped file, meaning the TLB-miss-plus-page-table-miss case,
and on every chunk of every read/write.  These are not page faults in
the usual sense: nothing is read in from storage.  The fault only
installs page table entries for memory that is already there, so there
is no I/O to amortize the resolver's cost against; whatever it costs
is added to the cost of a memory access.

The rbtree it walks is built from individually allocated nodes.  Each
level is a dependent, un-prefetchable dereference and a potential LLC
miss (~100ns), so a striped file with S strips pays log2(S) of them
per resolution, and that is a large fraction of a mapping fault that
otherwise costs little more than the page table update itself.

Replace the rbtree in struct fuse_backing with a packed, sorted array
of fuse_iext extents, allocated once per map rather than once per
extent.  The array packs the extents into the fewest cache lines, and
fault handling is O(1) when the map allows it:

 - A cyclic (striped) map is required to have equal-length extents
   contiguous from zero, so a file offset converts arithmetically to a
   strip index and cycle number.  This patch validates that and does
   it.

 - A simple map whose extents happen to be equal-length and contiguous
   from zero (the common famfs allocation) resolves as offset / ext_len.
   This patch detects that at populate time and does it.

 - An irregular map falls back to a binary search of the packed array.

famfs currently always produces maps that resolve in O(1).

Because the extents are sorted at populate time, a cyclic map's extents
no longer have to arrive in offset order, and the overlap check is an
adjacent-pair compare over the sorted array rather than a check at each
rbtree insertion.  Error returns are unchanged: -EIO with a message for
malformed extents and overlaps, -EINVAL for a non-uniform cyclic map.

Signed-off-by: Miklos Szeredi <mszeredi@redhat.com>
Signed-off-by: John Groves <john@groves.net>

0 files changed, 0 insertions, 0 deletions