hrev54275 adds 4 changesets to branch 'master'
old head: 621f53700fa3e6d84bfca3de0a36db31683427ae
new head: 299385f71979c1d45a3ed2bb62ae2f0189b23598
overview:
https://git.haiku-os.org/haiku/log/?qt=range&q=299385f71979+%5E621f53700fa3
----------------------------------------------------------------------------
6d9329be0582: VMUserAddressSpace: Make fAreas an AVLTree.
This is analogous to the AVLTree used for kernel address ranges in
VMKernelAddressSpace. It does not use an additional DoublyLinkedList
however.
Using a binary tree speeds up many operations that previously had to
iterate the area list linearly to find normal and reserved areas,
insertion start points, etc. It especially benefits LookupArea which is
called for every page fault and from area_for() when randomly accessing
different areas as that would make the previously used area hint (i.e.
a one level lookup cache) ineffective.
The overhead of the tree versus the doubly linked list for iteration,
insertion and removal is reasonably small and pales in comparison to
what the linear searches previously took up.
Fixes the lookup performance in #15995.
Change-Id: I48319fe6a2e4327826e90ebca7246c7c419b5218
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2839
Reviewed-by: waddlesplash <waddlesplash@xxxxxxxxx>
a626bdab774b: kernel/vm: Remove linear search from _get_next_area_info.
This introduces VMAddressSpace::FindClosestArea() that can be used to
find the closest area to a given address in either direction. This is
now trivial and efficient since both kernel and user address spaces use
a binary search tree.
Using FindClosestArea() getting multiple area infos is sped up
dramatically as it removes the need for a linear search from the first
area to the one given in the cookie on each successive invocation.
Change-Id: I227da87d915f6f3d3ef88bfeb6be5d4c97c3baaa
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2840
Reviewed-by: waddlesplash <waddlesplash@xxxxxxxxx>
a6926d42873a: kernel/vm: Introduce and use VMAddressSpace::AreaRangeIterator.
It iterates over all areas intersecting a given address range and
removes the need for manually skipping uninteresting initial areas. It
uses VMAddressSpace::FindClosestArea() to efficiently find the starting
area.
This speeds up the two iterations in unmap_address_range and one in
wait_if_address_range_is_wired and resolves a TODO in the latter hinting
at such a solution.
Change-Id: Iba1d39942db4e4b27e17706be194496f9d4279ed
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2841
Reviewed-by: waddlesplash <waddlesplash@xxxxxxxxx>
299385f71979: VMUserAddressSpace: Speed up area insertion with a hint.
The possible insertion range for B_*_ANY_ADDRESS always encompasses the
entire address space. Even though the initial starting point is now
looked up using a binary search tree, actually finding a free spot was
then still done using a linear search from there.
Store a simple insertion hint, the address directly following the
previous insertion of the same type, and use that as the next starting
point. In the common case this reduces the needed iterations to zero or
near zero.
No hint is used for B_*_BASE_ADDRESS specs as it is assumed that the
given base address already serves as such a hint.
Fixes the area creation performance part of #15995.
Change-Id: Ia8ce76eadc341b71de4cf8c34744c2459473bd06
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2842
Reviewed-by: waddlesplash <waddlesplash@xxxxxxxxx>
[ Michael Lotz <mmlr@xxxxxxxx> ]
----------------------------------------------------------------------------
7 files changed, 208 insertions(+), 144 deletions(-)
headers/private/kernel/vm/VMAddressSpace.h | 60 +++++++
src/system/kernel/vm/VMKernelAddressSpace.cpp | 12 ++
src/system/kernel/vm/VMKernelAddressSpace.h | 2 +
src/system/kernel/vm/VMUserAddressSpace.cpp | 185 +++++++++++-----------
src/system/kernel/vm/VMUserAddressSpace.h | 6 +-
src/system/kernel/vm/VMUserArea.h | 40 +++--
src/system/kernel/vm/vm.cpp | 47 ++----
############################################################################
Commit: 6d9329be0582419bab3dcdb119a7cb946f1e0d8b
URL: https://git.haiku-os.org/haiku/commit/?id=6d9329be0582
Author: Michael Lotz <mmlr@xxxxxxxx>
Date: Sun May 24 22:53:09 2020 UTC
Committer: waddlesplash <waddlesplash@xxxxxxxxx>
Commit-Date: Sat May 30 02:29:41 2020 UTC
Ticket: https://dev.haiku-os.org/ticket/15995
VMUserAddressSpace: Make fAreas an AVLTree.
This is analogous to the AVLTree used for kernel address ranges in
VMKernelAddressSpace. It does not use an additional DoublyLinkedList
however.
Using a binary tree speeds up many operations that previously had to
iterate the area list linearly to find normal and reserved areas,
insertion start points, etc. It especially benefits LookupArea which is
called for every page fault and from area_for() when randomly accessing
different areas as that would make the previously used area hint (i.e.
a one level lookup cache) ineffective.
The overhead of the tree versus the doubly linked list for iteration,
insertion and removal is reasonably small and pales in comparison to
what the linear searches previously took up.
Fixes the lookup performance in #15995.
Change-Id: I48319fe6a2e4327826e90ebca7246c7c419b5218
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2839
Reviewed-by: waddlesplash <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/system/kernel/vm/VMUserAddressSpace.cpp
b/src/system/kernel/vm/VMUserAddressSpace.cpp
index 9e91b6cdd5..86bdd5bd5e 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.cpp
+++ b/src/system/kernel/vm/VMUserAddressSpace.cpp
@@ -82,8 +82,7 @@ align_address(addr_t address, size_t alignment, uint32
addressSpec,
VMUserAddressSpace::VMUserAddressSpace(team_id id, addr_t base, size_t size)
:
- VMAddressSpace(id, base, size, "address space"),
- fAreaHint(NULL)
+ VMAddressSpace(id, base, size, "address space")
{
}
@@ -96,9 +95,9 @@ VMUserAddressSpace::~VMUserAddressSpace()
inline VMArea*
VMUserAddressSpace::FirstArea() const
{
- VMUserArea* area = fAreas.Head();
+ VMUserArea* area = fAreas.LeftMost();
while (area != NULL && area->id == RESERVED_AREA_ID)
- area = fAreas.GetNext(area);
+ area = fAreas.Next(area);
return area;
}
@@ -107,9 +106,9 @@ inline VMArea*
VMUserAddressSpace::NextArea(VMArea* _area) const
{
VMUserArea* area = static_cast<VMUserArea*>(_area);
- area = fAreas.GetNext(area);
+ area = fAreas.Next(area);
while (area != NULL && area->id == RESERVED_AREA_ID)
- area = fAreas.GetNext(area);
+ area = fAreas.Next(area);
return area;
}
@@ -135,23 +134,11 @@ VMUserAddressSpace::DeleteArea(VMArea* _area, uint32
allocationFlags)
VMArea*
VMUserAddressSpace::LookupArea(addr_t address) const
{
- // check the area hint first
- VMArea* areaHint = atomic_pointer_get(&fAreaHint);
- if (areaHint != NULL && areaHint->ContainsAddress(address))
- return areaHint;
+ VMUserArea* area = fAreas.FindClosest(address, true);
+ if (area == NULL || area->id == RESERVED_AREA_ID)
+ return NULL;
- for (VMUserAreaList::ConstIterator it = fAreas.GetIterator();
- VMUserArea* area = it.Next();) {
- if (area->id == RESERVED_AREA_ID)
- continue;
-
- if (area->ContainsAddress(address)) {
- atomic_pointer_set(&fAreaHint, area);
- return area;
- }
- }
-
- return NULL;
+ return area->ContainsAddress(address) ? area : NULL;
}
@@ -218,9 +205,6 @@ VMUserAddressSpace::RemoveArea(VMArea* _area, uint32
allocationFlags)
if (area->id != RESERVED_AREA_ID) {
IncrementChangeCount();
fFreeSpace += area->Size();
-
- if (area == fAreaHint)
- fAreaHint = NULL;
}
}
@@ -228,7 +212,7 @@ VMUserAddressSpace::RemoveArea(VMArea* _area, uint32
allocationFlags)
bool
VMUserAddressSpace::CanResizeArea(VMArea* area, size_t newSize)
{
- VMUserArea* next = fAreas.GetNext(static_cast<VMUserArea*>(area));
+ VMUserArea* next = fAreas.Next(static_cast<VMUserArea*>(area));
addr_t newEnd = area->Base() + (newSize - 1);
if (next == NULL)
@@ -254,7 +238,7 @@ VMUserAddressSpace::ResizeArea(VMArea* _area, size_t
newSize,
VMUserArea* area = static_cast<VMUserArea*>(_area);
addr_t newEnd = area->Base() + (newSize - 1);
- VMUserArea* next = fAreas.GetNext(area);
+ VMUserArea* next = fAreas.Next(area);
if (next != NULL && next->Base() <= newEnd) {
if (next->id != RESERVED_AREA_ID
|| (uint64)next->cache_offset > (uint64)area->Base()
@@ -355,14 +339,17 @@ VMUserAddressSpace::UnreserveAddressRange(addr_t address,
size_t size,
return B_BAD_TEAM_ID;
}
- // search area list and remove any matching reserved ranges
- addr_t endAddress = address + (size - 1);
- for (VMUserAreaList::Iterator it = fAreas.GetIterator();
- VMUserArea* area = it.Next();) {
- // the area must be completely part of the reserved range
- if (area->Base() + (area->Size() - 1) > endAddress)
- break;
- if (area->id == RESERVED_AREA_ID && area->Base() >=
(addr_t)address) {
+ // the area must be completely part of the reserved range
+ VMUserArea* area = fAreas.FindClosest(address, false);
+ if (area == NULL)
+ return B_OK;
+
+ addr_t endAddress = address + size - 1;
+ for (VMUserAreaTree::Iterator it = fAreas.GetIterator(area);
+ (area = it.Next()) != NULL
+ && area->Base() + area->Size() - 1 <= endAddress;) {
+
+ if (area->id == RESERVED_AREA_ID) {
// remove reserved range
RemoveArea(area, allocationFlags);
Put();
@@ -378,7 +365,7 @@ VMUserAddressSpace::UnreserveAddressRange(addr_t address,
size_t size,
void
VMUserAddressSpace::UnreserveAllAddressRanges(uint32 allocationFlags)
{
- for (VMUserAreaList::Iterator it = fAreas.GetIterator();
+ for (VMUserAreaTree::Iterator it = fAreas.GetIterator();
VMUserArea* area = it.Next();) {
if (area->id == RESERVED_AREA_ID) {
RemoveArea(area, allocationFlags);
@@ -394,11 +381,9 @@ void
VMUserAddressSpace::Dump() const
{
VMAddressSpace::Dump();
- kprintf("area_hint: %p\n", fAreaHint);
-
kprintf("area_list:\n");
- for (VMUserAreaList::ConstIterator it = fAreas.GetIterator();
+ for (VMUserAreaTree::ConstIterator it = fAreas.GetIterator();
VMUserArea* area = it.Next();) {
kprintf(" area 0x%" B_PRIx32 ": ", area->id);
kprintf("base_addr = 0x%lx ", area->Base());
@@ -450,71 +435,65 @@ status_t
VMUserAddressSpace::_InsertAreaIntoReservedRegion(addr_t start, size_t size,
VMUserArea* area, uint32 allocationFlags)
{
- VMUserArea* next;
-
- for (VMUserAreaList::Iterator it = fAreas.GetIterator();
- (next = it.Next()) != NULL;) {
- if (next->Base() <= start
- && next->Base() + (next->Size() - 1) >= start + (size -
1)) {
- // This area covers the requested range
- if (next->id != RESERVED_AREA_ID) {
- // but it's not reserved space, it's a real area
- return B_BAD_VALUE;
- }
-
- break;
- }
+ VMUserArea* reserved = fAreas.FindClosest(start, true);
+ if (reserved == NULL
+ || !reserved->ContainsAddress(start)
+ || !reserved->ContainsAddress(start + size - 1)) {
+ return B_ENTRY_NOT_FOUND;
}
- if (next == NULL)
- return B_ENTRY_NOT_FOUND;
+ // This area covers the requested range
+ if (reserved->id != RESERVED_AREA_ID) {
+ // but it's not reserved space, it's a real area
+ return B_BAD_VALUE;
+ }
// Now we have to transfer the requested part of the reserved
// range to the new area - and remove, resize or split the old
// reserved area.
- if (start == next->Base()) {
+ if (start == reserved->Base()) {
// the area starts at the beginning of the reserved range
- fAreas.Insert(next, area);
- if (size == next->Size()) {
- // the new area fully covers the reversed range
- fAreas.Remove(next);
+ if (size == reserved->Size()) {
+ // the new area fully covers the reserved range
+ fAreas.Remove(reserved);
Put();
- next->~VMUserArea();
- free_etc(next, allocationFlags);
+ reserved->~VMUserArea();
+ free_etc(reserved, allocationFlags);
} else {
// resize the reserved range behind the area
- next->SetBase(next->Base() + size);
- next->SetSize(next->Size() - size);
+ reserved->SetBase(reserved->Base() + size);
+ reserved->SetSize(reserved->Size() - size);
}
- } else if (start + size == next->Base() + next->Size()) {
+ } else if (start + size == reserved->Base() + reserved->Size()) {
// the area is at the end of the reserved range
- fAreas.Insert(fAreas.GetNext(next), area);
-
// resize the reserved range before the area
- next->SetSize(start - next->Base());
+ reserved->SetSize(start - reserved->Base());
} else {
// the area splits the reserved range into two separate ones
// we need a new reserved area to cover this space
- VMUserArea* reserved = VMUserArea::CreateReserved(this,
- next->protection, allocationFlags);
- if (reserved == NULL)
+ VMUserArea* newReserved = VMUserArea::CreateReserved(this,
+ reserved->protection, allocationFlags);
+ if (newReserved == NULL)
return B_NO_MEMORY;
Get();
- fAreas.Insert(fAreas.GetNext(next), reserved);
- fAreas.Insert(reserved, area);
// resize regions
- reserved->SetSize(next->Base() + next->Size() - start - size);
- next->SetSize(start - next->Base());
- reserved->SetBase(start + size);
- reserved->cache_offset = next->cache_offset;
+ newReserved->SetBase(start + size);
+ newReserved->SetSize(
+ reserved->Base() + reserved->Size() - start - size);
+ newReserved->cache_offset = reserved->cache_offset;
+
+ reserved->SetSize(start - reserved->Base());
+
+ fAreas.Insert(newReserved);
}
area->SetBase(start);
area->SetSize(size);
+ fAreas.Insert(area);
IncrementChangeCount();
return B_OK;
@@ -527,11 +506,6 @@ VMUserAddressSpace::_InsertAreaSlot(addr_t start, addr_t
size, addr_t end,
uint32 addressSpec, size_t alignment, VMUserArea* area,
uint32 allocationFlags)
{
- VMUserArea* last = NULL;
- VMUserArea* next;
- bool foundSpot = false;
- addr_t originalStart = 0;
-
TRACE(("VMUserAddressSpace::_InsertAreaSlot: address space %p, start "
"0x%lx, size %ld, end 0x%lx, addressSpec %" B_PRIu32 ", area
%p\n",
this, start, size, end, addressSpec, area));
@@ -563,6 +537,7 @@ VMUserAddressSpace::_InsertAreaSlot(addr_t start, addr_t
size, addr_t end,
start = align_address(start, alignment);
+ addr_t originalStart = 0;
if (fRandomizingEnabled && addressSpec == B_RANDOMIZED_BASE_ADDRESS) {
originalStart = start;
start = _RandomizeAddress(start, end - size + 1, alignment,
true);
@@ -570,19 +545,14 @@ VMUserAddressSpace::_InsertAreaSlot(addr_t start, addr_t
size, addr_t end,
// walk up to the spot where we should start searching
second_chance:
- VMUserAreaList::Iterator it = fAreas.GetIterator();
- while ((next = it.Next()) != NULL) {
- if (next->Base() > start + (size - 1)) {
- // we have a winner
- break;
- }
-
- last = next;
- }
+ VMUserArea* next = fAreas.FindClosest(start + size, false);
+ VMUserArea* last = next != NULL
+ ? fAreas.Previous(next) : fAreas.FindClosest(start +
size, true);
// find the right spot depending on the address specification - the area
// will be inserted directly after "last" ("next" is not referenced
anymore)
+ bool foundSpot = false;
switch (addressSpec) {
case B_ANY_ADDRESS:
case B_ANY_KERNEL_ADDRESS:
@@ -591,6 +561,9 @@ second_chance:
case B_BASE_ADDRESS:
case B_RANDOMIZED_BASE_ADDRESS:
{
+ VMUserAreaTree::Iterator it = fAreas.GetIterator(
+ next != NULL ? next : fAreas.LeftMost());
+
// find a hole big enough for a new area
if (last == NULL) {
// see if we can build it at the beginning of
the virtual map
@@ -667,13 +640,12 @@ second_chance:
addressSpec = B_RANDOMIZED_BASE_ADDRESS;
}
- last = NULL;
goto second_chance;
} else if (area->id != RESERVED_AREA_ID) {
// We didn't find a free spot - if there are
any reserved areas,
// we can now test those for free space
// TODO: it would make sense to start with the
biggest of them
- it.Rewind();
+ it = fAreas.GetIterator();
next = it.Next();
for (last = NULL; next != NULL; next =
it.Next()) {
if (next->id != RESERVED_AREA_ID) {
@@ -746,7 +718,6 @@ second_chance:
foundSpot = true;
next->SetSize(alignedBase -
next->Base());
area->SetBase(alignedBase);
- last = next;
break;
}
@@ -774,11 +745,7 @@ second_chance:
return addressSpec == B_EXACT_ADDRESS ? B_BAD_VALUE :
B_NO_MEMORY;
area->SetSize(size);
- if (last)
- fAreas.Insert(fAreas.GetNext(last), area);
- else
- fAreas.Insert(fAreas.Head(), area);
-
+ fAreas.Insert(area);
IncrementChangeCount();
return B_OK;
}
diff --git a/src/system/kernel/vm/VMUserAddressSpace.h
b/src/system/kernel/vm/VMUserAddressSpace.h
index bb26ca9221..1ae6e45b91 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.h
+++ b/src/system/kernel/vm/VMUserAddressSpace.h
@@ -69,8 +69,7 @@ private:
static const addr_t kMaxRandomize;
static const addr_t kMaxInitialRandomize;
- VMUserAreaList fAreas;
- mutable VMUserArea* fAreaHint;
+ VMUserAreaTree fAreas;
};
diff --git a/src/system/kernel/vm/VMUserArea.h
b/src/system/kernel/vm/VMUserArea.h
index 24dd0eeca7..48413a3b4d 100644
--- a/src/system/kernel/vm/VMUserArea.h
+++ b/src/system/kernel/vm/VMUserArea.h
@@ -6,13 +6,15 @@
#define VM_USER_AREA_H
+#include <util/AVLTree.h>
+
#include <vm/VMArea.h>
struct VMUserAddressSpace;
-struct VMUserArea : VMArea {
+struct VMUserArea : VMArea, AVLTreeNode {
VMUserArea(VMAddressSpace* addressSpace,
uint32
wiring, uint32 protection);
~VMUserArea();
@@ -22,32 +24,38 @@ struct VMUserArea : VMArea {
uint32
protection, uint32 allocationFlags);
static VMUserArea* CreateReserved(VMAddressSpace*
addressSpace,
uint32
flags, uint32 allocationFlags);
+};
- DoublyLinkedListLink<VMUserArea>& AddressSpaceLink()
- {
return fAddressSpaceLink; }
- const DoublyLinkedListLink<VMUserArea>&
AddressSpaceLink() const
- {
return fAddressSpaceLink; }
-private:
- DoublyLinkedListLink<VMUserArea> fAddressSpaceLink;
-};
+struct VMUserAreaTreeDefinition {
+ typedef addr_t Key;
+ typedef VMUserArea Value;
+
+ AVLTreeNode* GetAVLTreeNode(Value* value) const
+ {
+ return value;
+ }
+ Value* GetValue(AVLTreeNode* node) const
+ {
+ return static_cast<Value*>(node);
+ }
-struct VMUserAreaGetLink {
- inline DoublyLinkedListLink<VMUserArea>* operator()(
- VMUserArea* area) const
+ int Compare(addr_t a, const Value* _b) const
{
- return &area->AddressSpaceLink();
+ addr_t b = _b->Base();
+ if (a == b)
+ return 0;
+ return a < b ? -1 : 1;
}
- inline const DoublyLinkedListLink<VMUserArea>* operator()(
- const VMUserArea* area) const
+ int Compare(const Value* a, const Value* b) const
{
- return &area->AddressSpaceLink();
+ return Compare(a->Base(), b);
}
};
-typedef DoublyLinkedList<VMUserArea, VMUserAreaGetLink> VMUserAreaList;
+typedef AVLTree<VMUserAreaTreeDefinition> VMUserAreaTree;
#endif // VM_USER_AREA_H
############################################################################
Commit: a626bdab774b5e9e9845138fca79cb099c700afe
URL: https://git.haiku-os.org/haiku/commit/?id=a626bdab774b
Author: Michael Lotz <mmlr@xxxxxxxx>
Date: Fri May 29 12:25:43 2020 UTC
Committer: waddlesplash <waddlesplash@xxxxxxxxx>
Commit-Date: Sat May 30 02:29:41 2020 UTC
kernel/vm: Remove linear search from _get_next_area_info.
This introduces VMAddressSpace::FindClosestArea() that can be used to
find the closest area to a given address in either direction. This is
now trivial and efficient since both kernel and user address spaces use
a binary search tree.
Using FindClosestArea() getting multiple area infos is sped up
dramatically as it removes the need for a linear search from the first
area to the one given in the cookie on each successive invocation.
Change-Id: I227da87d915f6f3d3ef88bfeb6be5d4c97c3baaa
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2840
Reviewed-by: waddlesplash <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/vm/VMAddressSpace.h
b/headers/private/kernel/vm/VMAddressSpace.h
index aa8e4ee875..1c226a4ae1 100644
--- a/headers/private/kernel/vm/VMAddressSpace.h
+++ b/headers/private/kernel/vm/VMAddressSpace.h
@@ -76,6 +76,8 @@ public:
virtual VMArea* NextArea(VMArea* area) const =
0;
virtual VMArea* LookupArea(addr_t address)
const = 0;
+ virtual VMArea* FindClosestArea(addr_t address,
bool less) const
+ = 0;
virtual VMArea* CreateArea(const char* name,
uint32 wiring,
uint32
protection,
uint32
allocationFlags) = 0;
diff --git a/src/system/kernel/vm/VMKernelAddressSpace.cpp
b/src/system/kernel/vm/VMKernelAddressSpace.cpp
index 9c22638548..5db4eb055a 100644
--- a/src/system/kernel/vm/VMKernelAddressSpace.cpp
+++ b/src/system/kernel/vm/VMKernelAddressSpace.cpp
@@ -171,6 +171,18 @@ VMKernelAddressSpace::LookupArea(addr_t address) const
}
+//! You must hold the address space's read lock.
+VMArea*
+VMKernelAddressSpace::FindClosestArea(addr_t address, bool less) const
+{
+ Range* range = fRangeTree.FindClosest(address, less);
+ while (range != NULL && range->type != Range::RANGE_AREA)
+ range = fRangeTree.Next(range);
+
+ return range != NULL ? range->area : NULL;
+}
+
+
/*! This inserts the area you pass into the address space.
It will also set the "_address" argument to its base address when
the call succeeds.
diff --git a/src/system/kernel/vm/VMKernelAddressSpace.h
b/src/system/kernel/vm/VMKernelAddressSpace.h
index c8eecb7602..489c0173ef 100644
--- a/src/system/kernel/vm/VMKernelAddressSpace.h
+++ b/src/system/kernel/vm/VMKernelAddressSpace.h
@@ -26,6 +26,8 @@ public:
virtual VMArea* NextArea(VMArea* area) const;
virtual VMArea* LookupArea(addr_t address)
const;
+ virtual VMArea* FindClosestArea(addr_t address,
bool less)
+ const;
virtual VMArea* CreateArea(const char* name,
uint32 wiring,
uint32
protection, uint32 allocationFlags);
virtual void DeleteArea(VMArea* area,
diff --git a/src/system/kernel/vm/VMUserAddressSpace.cpp
b/src/system/kernel/vm/VMUserAddressSpace.cpp
index 86bdd5bd5e..90ff7f226a 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.cpp
+++ b/src/system/kernel/vm/VMUserAddressSpace.cpp
@@ -142,6 +142,17 @@ VMUserAddressSpace::LookupArea(addr_t address) const
}
+//! You must hold the address space's read lock.
+VMArea*
+VMUserAddressSpace::FindClosestArea(addr_t address, bool less) const
+{
+ VMUserArea* area = fAreas.FindClosest(address, less);
+ while (area != NULL && area->id == RESERVED_AREA_ID)
+ area = fAreas.Next(area);
+ return area;
+}
+
+
/*! This inserts the area you pass into the address space.
It will also set the "_address" argument to its base address when
the call succeeds.
diff --git a/src/system/kernel/vm/VMUserAddressSpace.h
b/src/system/kernel/vm/VMUserAddressSpace.h
index 1ae6e45b91..814b1ee699 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.h
+++ b/src/system/kernel/vm/VMUserAddressSpace.h
@@ -21,6 +21,8 @@ public:
virtual VMArea* NextArea(VMArea* area) const;
virtual VMArea* LookupArea(addr_t address)
const;
+ virtual VMArea* FindClosestArea(addr_t address,
bool less)
+ const;
virtual VMArea* CreateArea(const char* name,
uint32 wiring,
uint32
protection, uint32 allocationFlags);
virtual void DeleteArea(VMArea* area,
diff --git a/src/system/kernel/vm/vm.cpp b/src/system/kernel/vm/vm.cpp
index 850d8c09a8..a672595608 100644
--- a/src/system/kernel/vm/vm.cpp
+++ b/src/system/kernel/vm/vm.cpp
@@ -6050,21 +6050,14 @@ _get_next_area_info(team_id team, ssize_t* cookie,
area_info* info, size_t size)
if (!locker.IsLocked())
return B_BAD_TEAM_ID;
- VMArea* area;
- for (VMAddressSpace::AreaIterator it
- = locker.AddressSpace()->GetAreaIterator();
- (area = it.Next()) != NULL;) {
- if (area->Base() > nextBase)
- break;
- }
-
+ VMArea* area = locker.AddressSpace()->FindClosestArea(nextBase, false);
if (area == NULL) {
nextBase = (addr_t)-1;
return B_ENTRY_NOT_FOUND;
}
fill_area_info(area, info, size);
- *cookie = (ssize_t)(area->Base());
+ *cookie = (ssize_t)(area->Base() + 1);
return B_OK;
}
############################################################################
Commit: a6926d42873a80effd998e9e703a07a6e1c66f69
URL: https://git.haiku-os.org/haiku/commit/?id=a6926d42873a
Author: Michael Lotz <mmlr@xxxxxxxx>
Date: Fri May 29 12:33:55 2020 UTC
Committer: waddlesplash <waddlesplash@xxxxxxxxx>
Commit-Date: Sat May 30 02:29:41 2020 UTC
kernel/vm: Introduce and use VMAddressSpace::AreaRangeIterator.
It iterates over all areas intersecting a given address range and
removes the need for manually skipping uninteresting initial areas. It
uses VMAddressSpace::FindClosestArea() to efficiently find the starting
area.
This speeds up the two iterations in unmap_address_range and one in
wait_if_address_range_is_wired and resolves a TODO in the latter hinting
at such a solution.
Change-Id: Iba1d39942db4e4b27e17706be194496f9d4279ed
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2841
Reviewed-by: waddlesplash <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/vm/VMAddressSpace.h
b/headers/private/kernel/vm/VMAddressSpace.h
index 1c226a4ae1..378fb6efe5 100644
--- a/headers/private/kernel/vm/VMAddressSpace.h
+++ b/headers/private/kernel/vm/VMAddressSpace.h
@@ -23,6 +23,7 @@ struct virtual_address_restrictions;
struct VMAddressSpace {
public:
class AreaIterator;
+ class AreaRangeIterator;
public:
VMAddressSpace(team_id id, addr_t base,
@@ -67,6 +68,8 @@ public:
{
fRandomizingEnabled = enabled; }
inline AreaIterator GetAreaIterator();
+ inline AreaRangeIterator GetAreaRangeIterator(addr_t address,
+ addr_t
size);
VMAddressSpace*& HashTableLink() { return
fHashTableLink; }
@@ -202,6 +205,54 @@ private:
};
+class VMAddressSpace::AreaRangeIterator : public VMAddressSpace::AreaIterator {
+public:
+ AreaRangeIterator()
+ {
+ }
+
+ AreaRangeIterator(VMAddressSpace* addressSpace, addr_t address, addr_t
size)
+ :
+ fAddressSpace(addressSpace),
+ fNext(NULL),
+ fAddress(address),
+ fEndAddress(address + size - 1)
+ {
+ Rewind();
+ }
+
+ bool HasNext() const
+ {
+ return fNext != NULL;
+ }
+
+ VMArea* Next()
+ {
+ VMArea* result = fNext;
+ if (fNext != NULL) {
+ fNext = fAddressSpace->NextArea(fNext);
+ if (fNext != NULL && fNext->Base() > fEndAddress)
+ fNext = NULL;
+ }
+
+ return result;
+ }
+
+ void Rewind()
+ {
+ fNext = fAddressSpace->FindClosestArea(fAddress, true);
+ if (fNext != NULL && !fNext->ContainsAddress(fAddress))
+ Next();
+ }
+
+private:
+ VMAddressSpace* fAddressSpace;
+ VMArea* fNext;
+ addr_t fAddress;
+ addr_t fEndAddress;
+};
+
+
inline VMAddressSpace::AreaIterator
VMAddressSpace::GetAreaIterator()
{
@@ -209,6 +260,13 @@ VMAddressSpace::GetAreaIterator()
}
+inline VMAddressSpace::AreaRangeIterator
+VMAddressSpace::GetAreaRangeIterator(addr_t address, addr_t size)
+{
+ return AreaRangeIterator(this, address, size);
+}
+
+
#ifdef __cplusplus
extern "C" {
#endif
diff --git a/src/system/kernel/vm/vm.cpp b/src/system/kernel/vm/vm.cpp
index a672595608..c43a18f333 100644
--- a/src/system/kernel/vm/vm.cpp
+++ b/src/system/kernel/vm/vm.cpp
@@ -833,26 +833,26 @@ unmap_address_range(VMAddressSpace* addressSpace, addr_t
address, addr_t size,
bool kernel)
{
size = PAGE_ALIGN(size);
- addr_t lastAddress = address + (size - 1);
// Check, whether the caller is allowed to modify the concerned areas.
if (!kernel) {
- for (VMAddressSpace::AreaIterator it =
addressSpace->GetAreaIterator();
- VMArea* area = it.Next();) {
- addr_t areaLast = area->Base() + (area->Size() - 1);
- if (area->Base() < lastAddress && address < areaLast) {
- if ((area->protection & B_KERNEL_AREA) != 0) {
- dprintf("unmap_address_range: team %"
B_PRId32 " tried to "
- "unmap range of kernel area %"
B_PRId32 " (%s)\n",
- team_get_current_team_id(),
area->id, area->name);
- return B_NOT_ALLOWED;
- }
+ for (VMAddressSpace::AreaRangeIterator it
+ = addressSpace->GetAreaRangeIterator(address,
size);
+ VMArea* area = it.Next();) {
+
+ if ((area->protection & B_KERNEL_AREA) != 0) {
+ dprintf("unmap_address_range: team %" B_PRId32
" tried to "
+ "unmap range of kernel area %" B_PRId32
" (%s)\n",
+ team_get_current_team_id(), area->id,
area->name);
+ return B_NOT_ALLOWED;
}
}
}
- for (VMAddressSpace::AreaIterator it = addressSpace->GetAreaIterator();
- VMArea* area = it.Next();) {
+ for (VMAddressSpace::AreaRangeIterator it
+ = addressSpace->GetAreaRangeIterator(address, size);
+ VMArea* area = it.Next();) {
+
status_t error = cut_area(addressSpace, area, address, size,
NULL,
kernel);
if (error != B_OK)
@@ -1092,15 +1092,9 @@ static inline bool
wait_if_address_range_is_wired(VMAddressSpace* addressSpace, addr_t base,
size_t size, LockerType* locker)
{
- addr_t end = base + size - 1;
- for (VMAddressSpace::AreaIterator it = addressSpace->GetAreaIterator();
+ for (VMAddressSpace::AreaRangeIterator it
+ = addressSpace->GetAreaRangeIterator(base, size);
VMArea* area = it.Next();) {
- // TODO: Introduce a VMAddressSpace method to get a close
iterator!
- if (area->Base() > end)
- return false;
-
- if (base >= area->Base() + area->Size() - 1)
- continue;
AreaCacheLocker cacheLocker(vm_area_get_locked_cache(area));
############################################################################
Revision: hrev54275
Commit: 299385f71979c1d45a3ed2bb62ae2f0189b23598
URL: https://git.haiku-os.org/haiku/commit/?id=299385f71979
Author: Michael Lotz <mmlr@xxxxxxxx>
Date: Fri May 29 12:48:20 2020 UTC
Committer: waddlesplash <waddlesplash@xxxxxxxxx>
Commit-Date: Sat May 30 02:29:41 2020 UTC
Ticket: https://dev.haiku-os.org/ticket/15995
VMUserAddressSpace: Speed up area insertion with a hint.
The possible insertion range for B_*_ANY_ADDRESS always encompasses the
entire address space. Even though the initial starting point is now
looked up using a binary search tree, actually finding a free spot was
then still done using a linear search from there.
Store a simple insertion hint, the address directly following the
previous insertion of the same type, and use that as the next starting
point. In the common case this reduces the needed iterations to zero or
near zero.
No hint is used for B_*_BASE_ADDRESS specs as it is assumed that the
given base address already serves as such a hint.
Fixes the area creation performance part of #15995.
Change-Id: Ia8ce76eadc341b71de4cf8c34744c2459473bd06
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2842
Reviewed-by: waddlesplash <waddlesplash@xxxxxxxxx>
----------------------------------------------------------------------------
diff --git a/src/system/kernel/vm/VMUserAddressSpace.cpp
b/src/system/kernel/vm/VMUserAddressSpace.cpp
index 90ff7f226a..4e302bc387 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.cpp
+++ b/src/system/kernel/vm/VMUserAddressSpace.cpp
@@ -82,7 +82,8 @@ align_address(addr_t address, size_t alignment, uint32
addressSpec,
VMUserAddressSpace::VMUserAddressSpace(team_id id, addr_t base, size_t size)
:
- VMAddressSpace(id, base, size, "address space")
+ VMAddressSpace(id, base, size, "address space"),
+ fNextInsertHint(0)
{
}
@@ -548,10 +549,17 @@ VMUserAddressSpace::_InsertAreaSlot(addr_t start, addr_t
size, addr_t end,
start = align_address(start, alignment);
+ bool useHint
+ = addressSpec != B_EXACT_ADDRESS &&
!is_base_address_spec(addressSpec);
+
addr_t originalStart = 0;
if (fRandomizingEnabled && addressSpec == B_RANDOMIZED_BASE_ADDRESS) {
originalStart = start;
start = _RandomizeAddress(start, end - size + 1, alignment,
true);
+ } else if (useHint
+ && start <= fNextInsertHint && fNextInsertHint <= end - size +
1) {
+ originalStart = start;
+ start = fNextInsertHint;
}
// walk up to the spot where we should start searching
@@ -651,6 +659,10 @@ second_chance:
addressSpec = B_RANDOMIZED_BASE_ADDRESS;
}
+ goto second_chance;
+ } else if (useHint
+ && originalStart != 0 && start !=
originalStart) {
+ start = originalStart;
goto second_chance;
} else if (area->id != RESERVED_AREA_ID) {
// We didn't find a free spot - if there are
any reserved areas,
@@ -755,6 +767,9 @@ second_chance:
if (!foundSpot)
return addressSpec == B_EXACT_ADDRESS ? B_BAD_VALUE :
B_NO_MEMORY;
+ if (useHint)
+ fNextInsertHint = area->Base() + size;
+
area->SetSize(size);
fAreas.Insert(area);
IncrementChangeCount();
diff --git a/src/system/kernel/vm/VMUserAddressSpace.h
b/src/system/kernel/vm/VMUserAddressSpace.h
index 814b1ee699..8f9c918c0d 100644
--- a/src/system/kernel/vm/VMUserAddressSpace.h
+++ b/src/system/kernel/vm/VMUserAddressSpace.h
@@ -72,6 +72,7 @@ private:
static const addr_t kMaxInitialRandomize;
VMUserAreaTree fAreas;
+ addr_t fNextInsertHint;
};
