Re: Locality of extent status tree traversal

["Theodore Ts'o" <tytso@mit.edu>]

On Tue, May 07, 2019 at 11:12:07AM -0500, Probir Roy wrote:
> 
> I am running Phoronix-fio benchmark on Linux kernel 4.18.0-rc5. I
> observe the same nodes have been traversed on the extent status tree
> in "ext4_es_lookup_extent" function when ext4 write begins. What's the
> locality signature of "ext4_es_lookup_extent" in general? Is it
> possible that same logical block being looked up repeatedly
> (Temporal)? Is it possible that co-located logical blocks are searched
> by ext4_es_lookup_extent (spatial)?  Or is it totally random?

I'm not sure what you are asking.  The ext4_es_lookup_extent() is used
as a fast map of an inode's logical block number to find the physical
block number (e.g., the location on disk).  It's a cache; lookups are
fast, and is an in-memory lookup.  Well, it's a little more than a
cache, it also stores some information for delayed allocation buffered
writes.

If the workload is a random read or random write workload, then
accesses to look up logical to physical block maps will be random.  If
the workload is mostly a sequential read or sequential write access,
then the logical blocks looked up via ext4_es_lookup_extent() will
largely be sequential.

						- Ted