[roll] Roll fuchsia [kernel][vm] Use BTree for VmPageList

Replaces the usage of the WAVLTree in the VmPageList for a BTree. There
are two primary benefits of this:
 1. The BTree consumes less total memory for metadata compared to the
    intrusive WAVL tree state in the VmPageListNode
 2. Traversing and searching the BTree is more cache friendly than an
    intrusive WAVL tree.

There are a few consequences to the implementation from the use of the
btree:
 * With the node offset stored as the key in the btree it is redundant
   to also store it in the VmPageListNode, requiring it be passed in
   instead.
 * Iterators over the BTree yield key/value pairs, instead of just
   values, resulting in many minor code updates.
 * Insertion into the BTree can fail as it may require an allocation.
 * Iterators are invalidated on insert or erase and some paths need to
   be slightly restructured to avoid this.

Although the BTree provides better cache locality, in microbenchmarks
it can sometimes perform slightly worse, especially when the test fits
in cache with a single VmPageListNode as the WAVL tree avoids an extra
indirection that case.

Some other benchmark cases also perform worse, especially VMO clone
and close. These code paths have previously been structured and
optimized under assumptions on the VmPageList using a WAVL tree and
can be re-optimized for a BTree in the future (b/495140301).

Measurements show that in Starnix workloads this canreduce kernel
memory usage by ~9MiB

Run-All-Tests: True
Original-Bug: 475632731
Original-Bug: 495140301
Original-Reviewed-on: https://fuchsia-review.googlesource.com/c/fuchsia/+/1451830
Original-Revision: 5668cefb7dade127bab01fff78535316dd0c3608
GitOrigin-RevId: ef2568471b41748e118e145b2389a05993473dbb
Change-Id: I84787adfd2740728547995cead44e4ae2a1cd107
1 file changed
tree: 90f76d95071b7ac0b0e3c602a49ae8352dd9100f
  1. ctf/
  2. git-hooks/
  3. infra/
  4. third_party/
  5. cobalt
  6. flower
  7. jiri.lock
  8. MILESTONE
  9. minimal
  10. prebuilts
  11. README.md
  12. stem
  13. test_durations
README.md

Integration

This repository contains Fuchsia's Global Integration manifest files.

Making changes

All changes should be made to the internal version of this repository. Our infrastructure automatically updates this version when the internal one changes.

Currently all changes must be made by a Google employee. Non-Google employees wishing to make a change can ask for assistance in one of the communication channels documented at get involved.

Obtaining the source

First install Jiri.

Next run:

$ jiri init
$ jiri import minimal https://fuchsia.googlesource.com/integration
$ jiri update

Third party

Third party projects should have their own subdirectory in ./third_party.