kernel: Implement realloc_etc and make use of it.

kernel: Remove malloc_referenced now that it is unused.

It was added long before we had KernelReferenceable, which should
be used instead.

Allow gcc to know result is aligned

Someone on the internet found out gcc only understand posix_memalign.

The alloc_align attribute may be applied to a function that returns
a pointer and takes at least one argument of an integer or enumerated
type. It indicates that the returned pointer is aligned on a boundary
given by the function argument at position.

Change-Id: I4b0af6ef3020da1fb460652117286193d5d72f1e
Reviewed-on: https://review.haiku-os.org/c/haiku/+/4514
Reviewed-by: Fredrik Holmqvist <fredrik.holmqvist@gmail.com>
Reviewed-by: Adrien Destugues <pulkomandy@gmail.com>
Reviewed-by: waddlesplash <waddlesplash@gmail.com>
Tested-by: Commit checker robot <no-reply+buildbot@haiku-os.org>

Allow replacing the object cache with the guarded heap.

This allows to use the debug features of the guarded heap also on
allocations made through the object cache API. This is obivously
horrible for performance and uses up huge amounts of memory, so the
initial and grow sizes are adjusted accordingly.

Note that this is a rather simple hack, using the object_cache pointer
to transport the allocation size. The alignment is neglected completely.

Added a heap_init_post_area() which is called right after areas can be
created, and moved the heap's grow and VIP heap initialization to it. Should
fix #5956.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36855 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

* The alphabet is obviously hard, moved some tracing defines at their
(hopefully) correct place.
* It seems to be even harder to understand basic locking primitives: when you
think about it, it shouldn't surprise you that conditional variables never
return B_WOULD_BLOCK. This fixes gdb again.
* Added tracing support to the ports subsystem.
* get_port_message() will now resize the port heap if needed (but will also
take timeouts into account while doing so, more or less). The initial port
space is 4MB (as before), the growth rate is the same, and the system wide
limit is arbitrarily set to 64 MB (all swappable). A team limit has been set
to 8 MB, but is not enforced yet. Since ports are using up address space in
the kernel, those seems to be proper limits.
* This also fixes a strange, and rare lockup where the mouse cursor would still
move, but everything else would basically hang, but look perfectly normal from
KDL on the first look. As recently happened on Brecht's laptop, and debugged
by mmlr and me: the cbuf space got used up when lots of windows wanted to
redraw after a workspace switch. The app_server wouldn't answer anymore to
client requests, but thought it would have done so, as LinkSender::Flush()
doesn't care if it got a B_NO_MEMORY (the ports will now block until memory
is available if possible, so that should not be a problem anymore).
* Improved "port" KDL command, it now also prints the messages in the port.


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

* Implement per-CPU heaps. They only get enabled in case there's enough memory.
* Allow an allocator to be created on the heap to allow for non-locked
allocators to be created.
* Some cleanup.


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

Add a nogrow variant for new[] as well.


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

* Rework the heap locking strategy. Use a read-write lock for the area lock to
allow for more parallelism. Also introduce seperate locks for the bins and
for page allocation. This greatly reduces lock contention and reduces the
duration the locks are held due to them overall protecting less code. Now only
allocations of the same size hitting the same allocator or allocating larger
chunks of memory should block. Previously, basically any allocation and also
free would be mutually exclusive, making it scale pretty badely.
* Added memalign_nogrow(). As it uses heap_memalign() anyway, there's no real
reason not to allow for an alignment.
* Some cleanup.


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

* Use a singly linked list for the deferred free entries.
* Added deferred_delete() that takes a DeferredDeletable and deletes it
asynchronously.


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

* Moved more debug macros to kernel_debug_config.h.
* Turned the checks for all those macros to "#if"s instead of "#ifdef"s.
* Introduced macro KDEBUG_LEVEL which serves as a master setting.


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

Add throw() to the nogrow new operator. This will cause the right version to be
used that handles NULL returns and doesn't expect an exception. This fixes that
certain constructors would still be called even if the allocation failed in low
memory situations.


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

* Added heap_set_get_caller() which can be used when heap leak checking
is enabled to set a per-heap get_caller() function.
* Added "-h <heap>" option to the "allocations_per_caller" command. If
given only the allocation for the specified heap are considered.


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

* Instead of a heap class index heap_create_allocator() gets an actual
heap_class object now. Removed unused heap_allocator::heap_class.
* Made heap_class, heap_create_allocator(), heap_memalign(), heap_free()
public, so that a specialized allocator can be used elsewhere in the
kernel.


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

Merged branch haiku/branches/developer/bonefish/vm into trunk. This
introduces the following relevant changes:
* VMCache:
- Renamed vm_cache to VMCache, merged it with vm_store and made it a
C++ class with virtual methods (replacing the store operations).
Turned the different store implementations into subclasses.
- Introduced MergeStore() callback, changed semantics of Commit().
- Changed locking and referencing semantics. A reference can only be
acquired/released with the cache locked. An unreferenced cache is
deleted and a mergeable cache merged when it is unlocked. This
removes the "busy" state of a cache and simplifies the page fault
code.
* Added VMAnonymousCache, which will implement swap support (work by
Zhao Shuai). It is not integrated and used yet, though.
* Enabled the mutex/recursive lock holder asserts.
* Fixed DoublyLinkedList::Swap().
* Generalized the low memory handler to a low resource handler. And made
semaphores and reserved memory handled resources. Made
vm_try_resource_memory() optionally wait (with timeout), and used that
feature to reserve memory for areas.
...


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

Implement heap classes that each have their own range of allocation sizes they
serve, bin sizes and page size. This minimizes the amount of "large"
allocations made in heaps that don't have a bin for the allocation size
(combining multiple pages). This is desirable as such large allocations
are generally pretty inefficient, and also because it separates larger from
smaller allocations better, making the chance of a heap becoming empty higher.
For now there are three heap classes "small", "large" and "huge", with a
predefined set of bin sizes for each. This might need some finetuning later on.
Reduce the grow size to 4MB though as the allocations should now be spread
across heap classes which each grow on their own.

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

* Added malloc_nogrow() function that does allocation without triggering or
waiting for a heap grow.
* Use that nogrow version in the VM code to avoid a deadlock with the address
space lock when a grow operation would try to create an area while a malloc
happened from such a function in the VM.
* When waiting for a grow to happen, notify the waiting thread from the grower
also if it failed to allocate a new heap. Otherwise a thread would just sit
there and wait until another thread requested growing too and that one
succeeded (or just forever in the worst case).
* Make the dedicated grow heap growable too. If the current grow heaps run low
on memory it will instruct the grower to allocate a new grow heap. This
reduces the likelyhood of running out of memory with no way to grow to a
minimum. As the growing is done asynchronously it is still possible to
happen, but it is highly unlikely as the grow heap is solely used to
allocate memory in the process of creating new heap areas and it will even
try using normal public memory if the dedicated memory has run out.
* Reduced the dedicated grow heap from 2 to 1MB. As it can now grow itself, it
doesn't need to last so long.
* Extract heap creation into it's own function that does area creation and heap
attach and use this function for growing normal and grow heaps.

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

Added functions malloc_referenced[_{acquire,release}]() that implement
reference counted memory allocations. Can be used for sharing immutable
structures.


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

Added deferred_free() function, that can be used to free allocations
in code that has interrupts disabled. The chunks of memories are queued
and free()d periodically by a kernel daemon.


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

Use a dedicated heap to allocate everything that is needed during heap growth.
This eliminates the edge case where the grow thread would not be able to create
a new area because no memory could be allocated for the allocation of the area.
As this case cannot happen anymore, it is also not possible to deadlock in
memalign. Therefore the timeout (which would only have prevented the deadlock
but wouldn't have solved the edge case anyway) has been removed too.
Add options to dump the dedicated grow heap and to only print the current heap
count to the "heap" debugger command.

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

Complete rework of the heap implementation. Freelists are now part of the pages
and pages are now kept in lists as well. This allows to return free pages once
a bin does not need them anymore. Partially filled pages are kept in a sorted
linked list so that allocation will always happen on the fullest page - this
favours having full pages and makes it more likely lightly used pages will get
completely empty so they can be returned. Generally this now goes more in the
direction of a slab allocator.
The allocation logic has been extracted, so a heap is now simply attachable to
a region of memory. This allows for multiple heaps and for dynamic growing. In
case the allocator runs out of free pages, an asynchronous growing thread is
notified to create a new area and attach a new heap to it.
By default the kernel heap is now set to 16MB and grows by 8MB each time all
heaps run full.
This should solve quite a few issues, like certain bins just claiming all pages
so that even if there is free space nothing can be allocated. Also it obviously
does aways with filling the heap page by page until it overgrows.
I think this is now a well performing and scalable allocator we can live with
for quite some time. It is well tested under emulation and real hardware and
performs as expected. If problems come up there is an extensive sanity checker
that can be enabled by PARANOID_VALIDATION that covers most aspects of the
allocator. For normal operation this is not necessary though and is therefore
disabled by default.

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

Allow replacing the object cache with the guarded heap.

This allows to use the debug features of the guarded heap also on
allocations made through the object cache API. This is obivously
horrible for performance and uses up huge amounts of memory, so the
initial and grow sizes are adjusted accordingly.

Note that this is a rather simple hack, using the object_cache pointer
to transport the allocation size. The alignment is neglected completely.

Added a heap_init_post_area() which is called right after areas can be
created, and moved the heap's grow and VIP heap initialization to it. Should
fix #5956.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@36855 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

* The alphabet is obviously hard, moved some tracing defines at their
(hopefully) correct place.
* It seems to be even harder to understand basic locking primitives: when you
think about it, it shouldn't surprise you that conditional variables never
return B_WOULD_BLOCK. This fixes gdb again.
* Added tracing support to the ports subsystem.
* get_port_message() will now resize the port heap if needed (but will also
take timeouts into account while doing so, more or less). The initial port
space is 4MB (as before), the growth rate is the same, and the system wide
limit is arbitrarily set to 64 MB (all swappable). A team limit has been set
to 8 MB, but is not enforced yet. Since ports are using up address space in
the kernel, those seems to be proper limits.
* This also fixes a strange, and rare lockup where the mouse cursor would still
move, but everything else would basically hang, but look perfectly normal from
KDL on the first look. As recently happened on Brecht's laptop, and debugged
by mmlr and me: the cbuf space got used up when lots of windows wanted to
redraw after a workspace switch. The app_server wouldn't answer anymore to
client requests, but thought it would have done so, as LinkSender::Flush()
doesn't care if it got a B_NO_MEMORY (the ports will now block until memory
is available if possible, so that should not be a problem anymore).
* Improved "port" KDL command, it now also prints the messages in the port.


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

* Implement per-CPU heaps. They only get enabled in case there's enough memory.
* Allow an allocator to be created on the heap to allow for non-locked
allocators to be created.
* Some cleanup.


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

Add a nogrow variant for new[] as well.


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

* Rework the heap locking strategy. Use a read-write lock for the area lock to
allow for more parallelism. Also introduce seperate locks for the bins and
for page allocation. This greatly reduces lock contention and reduces the
duration the locks are held due to them overall protecting less code. Now only
allocations of the same size hitting the same allocator or allocating larger
chunks of memory should block. Previously, basically any allocation and also
free would be mutually exclusive, making it scale pretty badely.
* Added memalign_nogrow(). As it uses heap_memalign() anyway, there's no real
reason not to allow for an alignment.
* Some cleanup.


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

* Use a singly linked list for the deferred free entries.
* Added deferred_delete() that takes a DeferredDeletable and deletes it
asynchronously.


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

* Moved more debug macros to kernel_debug_config.h.
* Turned the checks for all those macros to "#if"s instead of "#ifdef"s.
* Introduced macro KDEBUG_LEVEL which serves as a master setting.


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

Add throw() to the nogrow new operator. This will cause the right version to be
used that handles NULL returns and doesn't expect an exception. This fixes that
certain constructors would still be called even if the allocation failed in low
memory situations.


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

* Added heap_set_get_caller() which can be used when heap leak checking
is enabled to set a per-heap get_caller() function.
* Added "-h <heap>" option to the "allocations_per_caller" command. If
given only the allocation for the specified heap are considered.


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

* Instead of a heap class index heap_create_allocator() gets an actual
heap_class object now. Removed unused heap_allocator::heap_class.
* Made heap_class, heap_create_allocator(), heap_memalign(), heap_free()
public, so that a specialized allocator can be used elsewhere in the
kernel.


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

Merged branch haiku/branches/developer/bonefish/vm into trunk. This
introduces the following relevant changes:
* VMCache:
- Renamed vm_cache to VMCache, merged it with vm_store and made it a
C++ class with virtual methods (replacing the store operations).
Turned the different store implementations into subclasses.
- Introduced MergeStore() callback, changed semantics of Commit().
- Changed locking and referencing semantics. A reference can only be
acquired/released with the cache locked. An unreferenced cache is
deleted and a mergeable cache merged when it is unlocked. This
removes the "busy" state of a cache and simplifies the page fault
code.
* Added VMAnonymousCache, which will implement swap support (work by
Zhao Shuai). It is not integrated and used yet, though.
* Enabled the mutex/recursive lock holder asserts.
* Fixed DoublyLinkedList::Swap().
* Generalized the low memory handler to a low resource handler. And made
semaphores and reserved memory handled resources. Made
vm_try_resource_memory() optionally wait (with timeout), and used that
feature to reserve memory for areas.
...


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

Implement heap classes that each have their own range of allocation sizes they
serve, bin sizes and page size. This minimizes the amount of "large"
allocations made in heaps that don't have a bin for the allocation size
(combining multiple pages). This is desirable as such large allocations
are generally pretty inefficient, and also because it separates larger from
smaller allocations better, making the chance of a heap becoming empty higher.
For now there are three heap classes "small", "large" and "huge", with a
predefined set of bin sizes for each. This might need some finetuning later on.
Reduce the grow size to 4MB though as the allocations should now be spread
across heap classes which each grow on their own.

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

* Added malloc_nogrow() function that does allocation without triggering or
waiting for a heap grow.
* Use that nogrow version in the VM code to avoid a deadlock with the address
space lock when a grow operation would try to create an area while a malloc
happened from such a function in the VM.
* When waiting for a grow to happen, notify the waiting thread from the grower
also if it failed to allocate a new heap. Otherwise a thread would just sit
there and wait until another thread requested growing too and that one
succeeded (or just forever in the worst case).
* Make the dedicated grow heap growable too. If the current grow heaps run low
on memory it will instruct the grower to allocate a new grow heap. This
reduces the likelyhood of running out of memory with no way to grow to a
minimum. As the growing is done asynchronously it is still possible to
happen, but it is highly unlikely as the grow heap is solely used to
allocate memory in the process of creating new heap areas and it will even
try using normal public memory if the dedicated memory has run out.
* Reduced the dedicated grow heap from 2 to 1MB. As it can now grow itself, it
doesn't need to last so long.
* Extract heap creation into it's own function that does area creation and heap
attach and use this function for growing normal and grow heaps.

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

Added functions malloc_referenced[_{acquire,release}]() that implement
reference counted memory allocations. Can be used for sharing immutable
structures.


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

Added deferred_free() function, that can be used to free allocations
in code that has interrupts disabled. The chunks of memories are queued
and free()d periodically by a kernel daemon.


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

Use a dedicated heap to allocate everything that is needed during heap growth.
This eliminates the edge case where the grow thread would not be able to create
a new area because no memory could be allocated for the allocation of the area.
As this case cannot happen anymore, it is also not possible to deadlock in
memalign. Therefore the timeout (which would only have prevented the deadlock
but wouldn't have solved the edge case anyway) has been removed too.
Add options to dump the dedicated grow heap and to only print the current heap
count to the "heap" debugger command.

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

Complete rework of the heap implementation. Freelists are now part of the pages
and pages are now kept in lists as well. This allows to return free pages once
a bin does not need them anymore. Partially filled pages are kept in a sorted
linked list so that allocation will always happen on the fullest page - this
favours having full pages and makes it more likely lightly used pages will get
completely empty so they can be returned. Generally this now goes more in the
direction of a slab allocator.
The allocation logic has been extracted, so a heap is now simply attachable to
a region of memory. This allows for multiple heaps and for dynamic growing. In
case the allocator runs out of free pages, an asynchronous growing thread is
notified to create a new area and attach a new heap to it.
By default the kernel heap is now set to 16MB and grows by 8MB each time all
heaps run full.
This should solve quite a few issues, like certain bins just claiming all pages
so that even if there is free space nothing can be allocated. Also it obviously
does aways with filling the heap page by page until it overgrows.
I think this is now a well performing and scalable allocator we can live with
for quite some time. It is well tested under emulation and real hardware and
performs as expected. If problems come up there is an extensive sanity checker
that can be enabled by PARANOID_VALIDATION that covers most aspects of the
allocator. For normal operation this is not necessary though and is therefore
disabled by default.

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