[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
This repository contains Fuchsia's Global Integration manifest files.
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.
First install Jiri.
Next run:
$ jiri init $ jiri import minimal https://fuchsia.googlesource.com/integration $ jiri update
Third party projects should have their own subdirectory in ./third_party.