VMUserAddressSpace: Don't print unset reserved area name in KDL.

Reserved areas don't have the name field initialized, so explicitly
print "reserved" instead.

Change-Id: I26bcfcb8facb8b5df11a58074506e96a41943e31
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2847
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

Cleanup: Various comment and whitespace fixes.

Change-Id: I37c3e3346813efc595df651421b7e8ff4fbf3339
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2845
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

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>

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>

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>

kernel/vm: Make sure the base address is larger than fBase.

This is technically only a functional change following the previous
commit, which unconditionally made sure the address was larger than
the base except for B_EXACT_ADDRESS. Essentially this makes sure
that if an address is passed which is smaller than the base is
passed in, it won't immediately fail just by being too small.

Checked against BeOS (0x0 passed to create_area with B_BASE_ADDRESS
succeeds, and returns 0x2000 consistently.) This is also needed
to not break userland initialization following the next commit.

kernel/vm: Remove VM86-related address space hacks.

VM86 was removed in 2012, so these are no longer needed.
The USER_BASE vs. USER_BASE_ANY distinction still seems like a
potentially useful one, though, so I've left all those changes in.

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().

VMUserAddressSpace: Use align_address() instead of ROUNDUP()

Mainly for aesthetical reasons.

VMUserAddressSpace::_InsertAreaSlot(): Fix base address handling

Unless a free range was found before the first area a specified base
address was ignored. In the non-randomized case this could result in
a range other than (i.e. starting before) the preferred one being
chosen, although the preferred range was available.

VMUserAddressSpace: Small coding style fixes

VMUserAddressSpace: Use std::min/max instead of min/max_c

vm: fix area insertion logic

* When looking for a place for new area the size of the area to be
inserted instead of the next area size was used to check whether
we are already past the upper bound.
* There was an attempt to insert area even if we were past the
upper bound.

vm: Fix off-by-one mistakes in _InsertAreaSlot

vm: make aslr use more secure PRNG

vm: remove unused static function log2()

vm: let aslr use kernel utils for random numbers

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.

vm: several improvements to VMUserAddressSpace::_InsertAreaSlot implementation
* B_BASE_ADDRESS honors requested alignment
* end of range is honored
* B_BASE_ADDRESS reuses B_ANY_ADDRESS code

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.

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.

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.

Prevent allocating address 0 when inserting an area with B_ANY_ADDRESS.

The USER_BASE_ANY definition exists to specify where to start searching
for B_ANY_ADDRESS allocations, but this was not being used correctly.
On x86_64, this was causing the runtime loader's heap to be allocated
at address 0 so NULL pointer accesses were not getting caught.

More 64-bit compilation/safety fixes.

* Fixed CID 1472: "next" could be NULL and dereferenced.
* Simplified code a bit.


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

* 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

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

* 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

* 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

Obvious copy and paste left-over. Totally missed it as I've been testing
the wrong image for quite a while. :-/


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

* 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

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

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().

VMUserAddressSpace: Use align_address() instead of ROUNDUP()

Mainly for aesthetical reasons.

VMUserAddressSpace::_InsertAreaSlot(): Fix base address handling

Unless a free range was found before the first area a specified base
address was ignored. In the non-randomized case this could result in
a range other than (i.e. starting before) the preferred one being
chosen, although the preferred range was available.

VMUserAddressSpace: Small coding style fixes

VMUserAddressSpace: Use std::min/max instead of min/max_c

vm: fix area insertion logic

* When looking for a place for new area the size of the area to be
inserted instead of the next area size was used to check whether
we are already past the upper bound.
* There was an attempt to insert area even if we were past the
upper bound.

vm: Fix off-by-one mistakes in _InsertAreaSlot

vm: make aslr use more secure PRNG

vm: remove unused static function log2()

vm: let aslr use kernel utils for random numbers

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.

vm: several improvements to VMUserAddressSpace::_InsertAreaSlot implementation
* B_BASE_ADDRESS honors requested alignment
* end of range is honored
* B_BASE_ADDRESS reuses B_ANY_ADDRESS code

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.

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.

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.

Prevent allocating address 0 when inserting an area with B_ANY_ADDRESS.

The USER_BASE_ANY definition exists to specify where to start searching
for B_ANY_ADDRESS allocations, but this was not being used correctly.
On x86_64, this was causing the runtime loader's heap to be allocated
at address 0 so NULL pointer accesses were not getting caught.

More 64-bit compilation/safety fixes.

* Fixed CID 1472: "next" could be NULL and dereferenced.
* Simplified code a bit.


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

* 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

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

* 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

* 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

Obvious copy and paste left-over. Totally missed it as I've been testing
the wrong image for quite a while. :-/


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

* 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

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