#
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
|