History log of /haiku/src/system/kernel/vm/VMUserAddressSpace.h
Revision Date Author Comments
# 299385f7 29-May-2020 Michael Lotz <mmlr@mlotz.ch>

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@gmail.com>


# a626bdab 29-May-2020 Michael Lotz <mmlr@mlotz.ch>

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@gmail.com>


# 6d9329be 24-May-2020 Michael Lotz <mmlr@mlotz.ch>

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@gmail.com>


# 7bf85edf 30-Nov-2013 Ingo Weinhold <ingo_weinhold@gmx.de>

Allow disabling ASLR via DISABLE_ASLR environment variable

* VMAddressSpace: Add randomizingEnabled property.
* VMUserAddressSpace: Randomize addresses only when randomizingEnabled
property is set.
* create_team_arg(): Check, if the team's environment contains
"DISABLE_ASLR=1". Set the team's address space property
randomizingEnabled accordingly in load_image_internal() and
exec_team().


# bf65fc1d 09-Apr-2013 Pawel Dziepak <pdziepak@quarnos.org>

vm: remove B_RANDOMIZED_IMAGE_ADDRESS address specification

This address specification is actually not needed since PIC images can be
located anywhere. Only their size is restriced but that is the compiler and
linker concern. Thanks to Alex Smith for pointing that out.


# 65ed4fa9 03-Apr-2013 Pawel Dziepak <pdziepak@quarnos.org>

vm: implement B_RANDOMIZED_IMAGE_ADDRESS address specification

On some 64 bit architectures program and library images have to be mapped in
the lower 2 GB of the address space (due to instruction pointer relative
addressing). Address specification B_RANDOMIZED_IMAGE_ADDRESS ensures that
created area satisfies that requirement.


# b3e4c677 26-Feb-2013 Pawel Dziepak <pdziepak@quarnos.org>

vm: implement B_RANDOMIZED_ANY_ADDRESS address specification

Randomized equivalent of B_ANY_ADDRESS. When a free space is found (as in
B_ANY_ADDRESS) the base adress is then randomized using _RandomizeAddress
pretty much like it is done in B_RANDOMIZED_BASE_ADDRESS.


# f9bab525 25-Feb-2013 Pawel Dziepak <pdziepak@quarnos.org>

vm: implement B_RANDOMIZED_BASE_ADDRESS address specification

B_RAND_BASE_ADDRESS is basically B_BASE_ADDRESS with non-deterministic created
area's base address.

Initial start address is randomized and then the algorithm looks for a large
enough free space in the interval [randomized start, end]. If it fails then
the search is repeated in the interval [original start, randomized start]. In
case it also fails the algorithm falls back to B_ANY_ADDRESS
(B_RANDOMIZED_ANY_ADDRESS when it is implemented) just like B_BASE_ADDRESS does.

Randomization range is limited by kMaxRandomize and kMaxInitialRandomize.


# a8ad734f 14-Jun-2010 Ingo Weinhold <ingo_weinhold@gmx.de>

* Introduced structures {virtual,physical}_address_restrictions, which specify
restrictions for virtual/physical addresses.
* vm_page_allocate_page_run():
- Fixed conversion of base/limit to array indexes. sPhysicalPageOffset was not
taken into account.
- Takes a physical_address_restrictions instead of base/limit and also
supports alignment and boundary restrictions, now.
* map_backing_store(), VM[User,Kernel]AddressSpace::InsertArea()/
ReserveAddressRange() take a virtual_address_restrictions parameter, now. They
also support an alignment independent from the range size.
* create_area_etc(), vm_create_anonymous_area(): Take
{virtual,physical}_address_restrictions parameters, now.
* Removed no longer needed B_PHYSICAL_BASE_ADDRESS.
* DMAResources:
- Fixed potential overflows of uint32 when initializing from device node
attributes.
- Fixed bounce buffer creation TODOs: By using create_area_etc() with the
new restrictions parameters we can directly support physical high address,
boundary, and alignment.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@37131 a95241bf-73f2-0310-859d-f6bbb57e9c96


# d62afe7a 28-Apr-2010 Ingo Weinhold <ingo_weinhold@gmx.de>

VMUserAddressSpace::LookupArea(): Although only a read-lock is the
precondition for calling the function it read/write accessed the fAreaHint
attribute in a non-atomic manner. I.e. if executed concurrently by two
threads of the same team one could return the wrong area. The most likely
problem could be caused in vm_soft_fault(), leading to pages being added to
the wrong caches.
The bug itself is inherited from NewOS, but is triggered way more likely
since the page daemon unmaps inactive pages (r35485). Probably fixes #5413.
Might also fix the sporadically occurring crashes/asserts in the hoard
allocator -- at least inactive pages being replaced by zeroed ones would be
an excellent explanation.
[Thanks to Matt for providing remote debug access to his machine.]


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36523 a95241bf-73f2-0310-859d-f6bbb57e9c96


# deee8524 26-Jan-2010 Ingo Weinhold <ingo_weinhold@gmx.de>

* Introduced {malloc,memalign,free}_etc() which take an additional "flags"
argument. They replace the previous special-purpose allocation functions
(malloc_nogrow(), vip_io_request_malloc()).
* Moved the I/O VIP heap to heap.cpp accordingly.
* Added quite a bit of passing around of allocation flags in the VM,
particularly in the VM*AddressSpace classes.
* Fixed IOBuffer::GetNextVirtualVec(): It was ignoring the VIP flag and always
allocated on the normal heap.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35316 a95241bf-73f2-0310-859d-f6bbb57e9c96


# 40cd019e 06-Dec-2009 Ingo Weinhold <ingo_weinhold@gmx.de>

* Renamed VMAddressSpace::ResizeArea{Head,Tail}() to ShrinkArea{Head,Tail}()
to clarify that they never enlarge the area.
* Reimplemented VMKernelAddressSpace. It is somewhat inspired by Bonwick's
vmem resource allocator (though we have different requirements):
- We consider the complete address space to be divided into contiguous
ranges of type free, reserved, or area, each range being represented by
a VMKernelAddressRange object.
- The range objects are managed in an AVL tree and a doubly linked list
(the latter only for faster iteration) sorted by address. This provides
O(log(n)) lookup, insertion and removal.
- For each power of two size we maintain a list of free ranges of at least
that size. Thus for the most common case of B_ANY*_ADDRESS area
allocation, we find a free range in constant time (the rest of the
processing being O(log(n))) with a rather good fit. This should also
help avoiding address space fragmentation.
While the new implementation should be faster, particularly with an
increasing number of areas, I couldn't measure any difference in the -j2
haiku build. From a cursory test the -j8 build hasn't tangibly benefitted
either.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34528 a95241bf-73f2-0310-859d-f6bbb57e9c96


# 2c1886ae 04-Dec-2009 Ingo Weinhold <ingo_weinhold@gmx.de>

* Added VMArea subclasses VM{Kernel,User}Area and moved the address space list
link to them.
* VM{Kernel,User}AddressSpace manage the respective VMArea subclass now, and
VMAddressSpace has grown factory methods {Create,Delete}Area.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34493 a95241bf-73f2-0310-859d-f6bbb57e9c96


# e2518ddb 04-Dec-2009 Ingo Weinhold <ingo_weinhold@gmx.de>

Made VMAddressSpace an abstract base class and moved the area management into
new derived classes VM{Kernel,User}AddressSpace. Currently those are
identical, but that will change.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34492 a95241bf-73f2-0310-859d-f6bbb57e9c96


# 7bf85edf58b140433802e19e992d32f0a824b702 30-Nov-2013 Ingo Weinhold <ingo_weinhold@gmx.de>

Allow disabling ASLR via DISABLE_ASLR environment variable

* VMAddressSpace: Add randomizingEnabled property.
* VMUserAddressSpace: Randomize addresses only when randomizingEnabled
property is set.
* create_team_arg(): Check, if the team's environment contains
"DISABLE_ASLR=1". Set the team's address space property
randomizingEnabled accordingly in load_image_internal() and
exec_team().


# bf65fc1dfe8daefa37b83d5551a85ec8fd65a8d5 09-Apr-2013 Pawel Dziepak <pdziepak@quarnos.org>

vm: remove B_RANDOMIZED_IMAGE_ADDRESS address specification

This address specification is actually not needed since PIC images can be
located anywhere. Only their size is restriced but that is the compiler and
linker concern. Thanks to Alex Smith for pointing that out.


# 65ed4fa908cce8864aee0905014bb802857d601d 03-Apr-2013 Pawel Dziepak <pdziepak@quarnos.org>

vm: implement B_RANDOMIZED_IMAGE_ADDRESS address specification

On some 64 bit architectures program and library images have to be mapped in
the lower 2 GB of the address space (due to instruction pointer relative
addressing). Address specification B_RANDOMIZED_IMAGE_ADDRESS ensures that
created area satisfies that requirement.


# b3e4c67739c7cc1e70dce20110fdeaea44155e1a 26-Feb-2013 Pawel Dziepak <pdziepak@quarnos.org>

vm: implement B_RANDOMIZED_ANY_ADDRESS address specification

Randomized equivalent of B_ANY_ADDRESS. When a free space is found (as in
B_ANY_ADDRESS) the base adress is then randomized using _RandomizeAddress
pretty much like it is done in B_RANDOMIZED_BASE_ADDRESS.


# f9bab525f6dc0e5ed6a164ebd9b3a9dde9c6ba6f 25-Feb-2013 Pawel Dziepak <pdziepak@quarnos.org>

vm: implement B_RANDOMIZED_BASE_ADDRESS address specification

B_RAND_BASE_ADDRESS is basically B_BASE_ADDRESS with non-deterministic created
area's base address.

Initial start address is randomized and then the algorithm looks for a large
enough free space in the interval [randomized start, end]. If it fails then
the search is repeated in the interval [original start, randomized start]. In
case it also fails the algorithm falls back to B_ANY_ADDRESS
(B_RANDOMIZED_ANY_ADDRESS when it is implemented) just like B_BASE_ADDRESS does.

Randomization range is limited by kMaxRandomize and kMaxInitialRandomize.


# a8ad734f1c698917badb15e1641e0f38b3e9a013 14-Jun-2010 Ingo Weinhold <ingo_weinhold@gmx.de>

* Introduced structures {virtual,physical}_address_restrictions, which specify
restrictions for virtual/physical addresses.
* vm_page_allocate_page_run():
- Fixed conversion of base/limit to array indexes. sPhysicalPageOffset was not
taken into account.
- Takes a physical_address_restrictions instead of base/limit and also
supports alignment and boundary restrictions, now.
* map_backing_store(), VM[User,Kernel]AddressSpace::InsertArea()/
ReserveAddressRange() take a virtual_address_restrictions parameter, now. They
also support an alignment independent from the range size.
* create_area_etc(), vm_create_anonymous_area(): Take
{virtual,physical}_address_restrictions parameters, now.
* Removed no longer needed B_PHYSICAL_BASE_ADDRESS.
* DMAResources:
- Fixed potential overflows of uint32 when initializing from device node
attributes.
- Fixed bounce buffer creation TODOs: By using create_area_etc() with the
new restrictions parameters we can directly support physical high address,
boundary, and alignment.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@37131 a95241bf-73f2-0310-859d-f6bbb57e9c96


# d62afe7ab01c79574766f6abd08cee1d00819579 28-Apr-2010 Ingo Weinhold <ingo_weinhold@gmx.de>

VMUserAddressSpace::LookupArea(): Although only a read-lock is the
precondition for calling the function it read/write accessed the fAreaHint
attribute in a non-atomic manner. I.e. if executed concurrently by two
threads of the same team one could return the wrong area. The most likely
problem could be caused in vm_soft_fault(), leading to pages being added to
the wrong caches.
The bug itself is inherited from NewOS, but is triggered way more likely
since the page daemon unmaps inactive pages (r35485). Probably fixes #5413.
Might also fix the sporadically occurring crashes/asserts in the hoard
allocator -- at least inactive pages being replaced by zeroed ones would be
an excellent explanation.
[Thanks to Matt for providing remote debug access to his machine.]


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36523 a95241bf-73f2-0310-859d-f6bbb57e9c96


# deee8524b7534d9b586cbcbf366d0660c9769a8e 26-Jan-2010 Ingo Weinhold <ingo_weinhold@gmx.de>

* Introduced {malloc,memalign,free}_etc() which take an additional "flags"
argument. They replace the previous special-purpose allocation functions
(malloc_nogrow(), vip_io_request_malloc()).
* Moved the I/O VIP heap to heap.cpp accordingly.
* Added quite a bit of passing around of allocation flags in the VM,
particularly in the VM*AddressSpace classes.
* Fixed IOBuffer::GetNextVirtualVec(): It was ignoring the VIP flag and always
allocated on the normal heap.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35316 a95241bf-73f2-0310-859d-f6bbb57e9c96


# 40cd019ea0415011db2a82c736e716a22ca842cc 06-Dec-2009 Ingo Weinhold <ingo_weinhold@gmx.de>

* Renamed VMAddressSpace::ResizeArea{Head,Tail}() to ShrinkArea{Head,Tail}()
to clarify that they never enlarge the area.
* Reimplemented VMKernelAddressSpace. It is somewhat inspired by Bonwick's
vmem resource allocator (though we have different requirements):
- We consider the complete address space to be divided into contiguous
ranges of type free, reserved, or area, each range being represented by
a VMKernelAddressRange object.
- The range objects are managed in an AVL tree and a doubly linked list
(the latter only for faster iteration) sorted by address. This provides
O(log(n)) lookup, insertion and removal.
- For each power of two size we maintain a list of free ranges of at least
that size. Thus for the most common case of B_ANY*_ADDRESS area
allocation, we find a free range in constant time (the rest of the
processing being O(log(n))) with a rather good fit. This should also
help avoiding address space fragmentation.
While the new implementation should be faster, particularly with an
increasing number of areas, I couldn't measure any difference in the -j2
haiku build. From a cursory test the -j8 build hasn't tangibly benefitted
either.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34528 a95241bf-73f2-0310-859d-f6bbb57e9c96


# 2c1886aeae1be8dc6bb9656701b2aab5bf3311ca 04-Dec-2009 Ingo Weinhold <ingo_weinhold@gmx.de>

* Added VMArea subclasses VM{Kernel,User}Area and moved the address space list
link to them.
* VM{Kernel,User}AddressSpace manage the respective VMArea subclass now, and
VMAddressSpace has grown factory methods {Create,Delete}Area.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34493 a95241bf-73f2-0310-859d-f6bbb57e9c96


# e2518ddbb14677f379b8dc8f66088473c553b113 04-Dec-2009 Ingo Weinhold <ingo_weinhold@gmx.de>

Made VMAddressSpace an abstract base class and moved the area management into
new derived classes VM{Kernel,User}AddressSpace. Currently those are
identical, but that will change.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34492 a95241bf-73f2-0310-859d-f6bbb57e9c96