[Ksummit-discuss] [TECH TOPIC] Maple Tree

[Ksummit-discuss] [TECH TOPIC] Maple Tree

[Theodore Ts'o]

From: Liam Howlett <Liam.Howlett@Oracle.com>,
      Matthew Wilcox <willy@infradead.org>

[ Note: The following abstract was submitted via the Linux Plumbers
  Conference website.  Per the instructions that were posted for the
  Maintainer's / Kernel Summit Call for Proposals[1], the proposal
  should also be posted on the ksummit-discuss list, so that people
  can comment on the proposal, and perhaps start a discussion before
  the summit.

  [1] https://lwn.net/Articles/788378/

  Please note that topic proposals for both the Kernel Summit and the
  Maintainer's Summit are still welcome, and the deadline has been
  extended to June 3rd. -- Ted ]

The Red-Black tree and Radix tree are used in many places in the
kernel to store ranges. Both of these trees have drawbacks when used
for ranges. The Red-Black tree requires writing your own insertion &
search code. It is also designed with the assumption that memory
accesses are cheap, which is no longer true. The Radix tree performs
acceptably well when ranges are aligned to a power of 2, but has awful
worst-case performance.

The Maple tree is a fast, cache efficient tree with a simple API. It
supports contiguous ranges efficiently, while suffering only minor
penalties for discontiguous ranges. Single entries are also supported
as a range of length one.

The Maple tree can optionally track free ranges to allow for more
efficient allocation. In order to allow it to be used as the basis for
the page cache, it will need support for search marks as well as
handling reclamation of shadow entries. Other potential users of the
Maple tree want more than the three search marks currently supported
by the Radix tree.

We want to discuss requirements with potential users of the Maple
tree, and to present development since the last Plumbers conference
where the broad outlines of the tree were first presented.