[LU-8272] Use granted extent tree to update kms

• Type: Improvement
• Resolution: Fixed
• Priority: Major
• Fix Version/s: Lustre 2.10.0
• Labels: patch
• Assignee: WC Triage
• Reporter: Patrick Farrell

Description

Currently, ldlm_extent_shift_kms does a linear search of
the list of granted locks on the resource when looking for
the lock to use to update the kms.

When cleaning up all locks on a resource, we end up doing
a linear search of this list for every lock on the object;
so, complexity n^2.

For resources with thousands of locks, this can take
multiple seconds, and scales quickly to tens of seconds per
resource. This can happen in normal usage with a weird I/O
pattern, but it is particularly a problem with lock ahead, which
creates large numbers of locks deliberately.

This can be avoided by using the binary trees which store
the extents of granted locks, reducing the complexity of an
individual search from 'n' to 'log n', and the total
complexity from n^2 to n*log.

Note that there are multiple trees, one for each lock mode.
This necessitates using kms and old_kms, since we check
every tree, even though we check the kms against only one
lock per tree.