kernel: Implement realloc_etc and make use of it.

kernel: Move aligned_alloc to heap.cpp alongside calloc.

It is independent of whatever heap implementation is actually in use,
so it belongs in here (even if this file is probably not the right
place for such functions in the first place.)

This allows the kernel to be built once again with things other than
the default slab heap.

kernel/slab: Make block_alloc and block_free static.

They are not used outside this file.

kernel/slab: Change checks in FreeRawOrReturnCache to panic instead.

The function is largely useless if we cannot lock kernel space,
and the consumers may not expect it to silently "fail." Hence,
we now put the invocation of deferred_free in free_etc directly.

kernel: Add aligned_alloc implementation.

Needed by default with GCC 11.

More trivial syntax and logic cleanup.

Spotted by Clang. No functional change intended.

kernel: use non-deprecated signatures for new/delete operators.

add posix_memalign(), needed for c++17.

mmlr + bonefish:
* Add optional stack trace capturing for slab memory manager tracing.
* Add allocation tracking for the slab allocator (enabled via
SLAB_ALLOCATION_TRACKING). The allocation tracking requires tracing
with stack traces to be enabled for object caches and/or the memory
manager.
- Add class AllocationTrackingInfo that associates an allocation with
its respective tracing entry. The structure is added to the end of
an allocation done by the memory manager. For the object caches
there's a separate array for each slab.
- Add code range markers to the slab code, so that the first caller
into the slab code can be retrieved from the stack traces.
- Add KDL command "allocations_per_caller" that lists all allocations
summarized by caller.
* Move debug definitions from slab_private.h to slab_debug.h.


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

* Removed a few superfluous "else" keywords.


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

* Added ObjectCache::alignment, the object alignment and used the alignment for
incrementing the cache color cycle. Using the fixed value (8) would
potentially misalign the object again.
* Don't use CACHE_ALIGN_ON_SIZE for object caches any longer -- we have the
alignment parameter anyway (the flag is still used for the MemoryManager,
though).
* ObjectCache::InitSlab(): Slab coloring *was* done when CACHE_ALIGN_ON_SIZE
was given, i.e. exactly the wrong way around. Also the cache_color_cycle
computation was weird -- color 0 was used twice in a row.
* The "slabs" and "slab_cache" KDL commands also print the alignment, now.



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

Changed the names of the block allocator object caches to avoid confusion
with the ones of the block cache.


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

* The low resource handler now empties the cache depot's magazines; before,
they were never freed unless the cache was destroyed (I just wondered why
my system would bury >1G in the magazines).
* Made the magazine capacity variable per cache, ie. for larger objects, it's
not a good idea to have 64*CPU buffers lying around in the worst case.
* Furthermore, the create_object_cache_etc()/object_depot_init() now have
arguments for the magazine capacity as well as the maximum number of full
unused magazines.
* By default, you might want to initialize both to zero, as then some hopefully
usable defaults are computed. Otherwise (the only current example is the
vm_page_mapping cache) you can just put in the values you'd want there.
The page mapping cache uses larger values, as its objects are usually
allocated and deleted in larger chunks.
* Beware, though, I couldn't test these changes yet as Qemu didn't like to run
today. I'll test these changes on another machine now.


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

MemoryManager:
* Added support to do larger raw allocations (up to one large chunk (128 pages))
in the slab areas. For an even larger allocation an area is created (haven't
seen that happen yet, though).
* Added kernel tracing (SLAB_MEMORY_MANAGER_TRACING).
* _FreeArea(): Copy and paste bug: The meta chunks of the to be freed area
would be added to the free lists instead of being removed from them. This
would corrupt the lists and also lead to all kinds of misuse of meta chunks.

object caches:
* Implemented CACHE_ALIGN_ON_SIZE. It is no longer set for all small object
caches, but the block allocator sets it on all power of two size caches.
* object_cache_reserve_internal(): Detect recursion and don't wait in such a
case. The function could deadlock itself, since
HashedObjectCache::CreateSlab() does allocate memory, thus potentially
reentering.
* object_cache_low_memory():
- I missed some returns when reworking that one in r35254, so the function
might stop early and also leave the cache in maintenance mode, which would
cause it to be ignored by object cache resizer and low memory handler from
that point on.
- Since ReturnSlab() potentially unlocks, the conditions weren't quite correct
and too many slabs could be freed.
- Simplified things a bit.
* object_cache_alloc(): Since object_cache_reserve_internal() does potentially
unlock the cache, the situation might have changed and their might not be an
empty slab available, but a partial one. The function would crash.
* Renamed the object cache tracing variable to SLAB_OBJECT_CACHE_TRACING.
* Renamed debugger command "cache_info" to "slab_cache" to avoid confusion with
the VMCache commands.
* ObjectCache::usage was not maintained anymore since I introduced the
MemoryManager. object_cache_get_usage() would thus always return 0 and the
block cache would not be considered cached memory. This was only of
informational relevance, though.

slab allocator misc.:
* Disable the object depots of block allocator caches for object sizes > 2 KB.
Allocations of those sizes aren't so common that the object depots yield any
benefit.
* The slab allocator is now fully self-sufficient. It allocates its bootstrap
memory from the MemoryManager, and the hash tables for HashedObjectCaches use
the block allocator instead of the heap, now.
* Added option to use the slab allocator for malloc() and friends
(USE_SLAB_ALLOCATOR_FOR_MALLOC). Currently disabled. Works in principle and
has virtually no lock contention. Handling for low memory situations is yet
missing, though.
* Improved the output of some debugger commands.


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

Replaced CACHE_DONT_SLEEP by two new flags CACHE_DONT_WAIT_FOR_MEMORY and
CACHE_DONT_LOCK_KERNEL_SPACE. If the former is given, the slab memory manager
does not wait when reserving memory or pages. The latter prevents area
operations. The new flags add a bit of flexibility. E.g. when allocating page
mapping objects for userland areas CACHE_DONT_WAIT_FOR_MEMORY is sufficient,
i.e. the allocation will succeed as long as pages are available.


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

slab allocator:
* Implemented a more elaborated raw memory allocation backend (MemoryManager).
We allocate 8 MB areas whose pages we allocate and map when needed. An area is
divided into equally-sized chunks which form the basic units of allocation. We
have areas with three possible chunk sizes (small, medium, large), which is
basically what the ObjectCache implementations were using anyway.
* Added "uint32 flags" parameter to several of the slab allocator's object
cache and object depot functions. E.g. object_depot_store() potentially wants
to allocate memory for a magazine. But also in pure freeing functions it
might eventually become useful to have those flags, since they could end up
deleting an area, which might not be allowable in all situations. We should
introduce specific flags to indicate that.
* Reworked the block allocator. Since the MemoryManager allocates block-aligned
areas, maintains a hash table for lookup, and maps chunks to object caches,
we can quickly find out which object cache a to be freed allocation belongs
to and thus don't need the boundary tags anymore.
* Reworked the slab boot strap process. We allocate from the initial area only
when really necessary, i.e. when the object cache for the respective
allocation size has not been created yet. A single page is thus sufficient.

other:
* vm_allocate_early(): Added boolean "blockAlign" parameter. If true, the
semantics is the same as for B_ANY_KERNEL_BLOCK_ADDRESS.
* Use an object cache for page mappings. This significantly reduces the
contention on the heap bin locks.


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

* Consequently propagate the CACHE_DONT_SLEEP flag.
* block_alloc(): Create B_FULL_LOCK area.


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

* Renamed headers/private/kernel/slab/Depot.h to ObjectDepot.h.
* Moved the object depot code to its own source file.


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

slab/cache: a couple more fixes.

- on CACHE_DURING_BOOT init benaphore count with 1.
- account for allocated space on early_allocate_pages.
- fixed slab position calculation in small slabs.
- we can now init all allocator sizes early rather than later.


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

cache allocator: keep allocation waste statistics. added debugger command 'show_waste'.


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

cache allocator: for allocations > 8k create areas, and delete them on free.


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

fixed the cache allocator's size_to_cache.


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

pushed the slab init a bit deeper. added a object cache based allocator, including a bootstrap mechanism to have it init during bootup.


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

mmlr + bonefish:
* Add optional stack trace capturing for slab memory manager tracing.
* Add allocation tracking for the slab allocator (enabled via
SLAB_ALLOCATION_TRACKING). The allocation tracking requires tracing
with stack traces to be enabled for object caches and/or the memory
manager.
- Add class AllocationTrackingInfo that associates an allocation with
its respective tracing entry. The structure is added to the end of
an allocation done by the memory manager. For the object caches
there's a separate array for each slab.
- Add code range markers to the slab code, so that the first caller
into the slab code can be retrieved from the stack traces.
- Add KDL command "allocations_per_caller" that lists all allocations
summarized by caller.
* Move debug definitions from slab_private.h to slab_debug.h.


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

* Removed a few superfluous "else" keywords.


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

* Added ObjectCache::alignment, the object alignment and used the alignment for
incrementing the cache color cycle. Using the fixed value (8) would
potentially misalign the object again.
* Don't use CACHE_ALIGN_ON_SIZE for object caches any longer -- we have the
alignment parameter anyway (the flag is still used for the MemoryManager,
though).
* ObjectCache::InitSlab(): Slab coloring *was* done when CACHE_ALIGN_ON_SIZE
was given, i.e. exactly the wrong way around. Also the cache_color_cycle
computation was weird -- color 0 was used twice in a row.
* The "slabs" and "slab_cache" KDL commands also print the alignment, now.



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

Changed the names of the block allocator object caches to avoid confusion
with the ones of the block cache.


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

* The low resource handler now empties the cache depot's magazines; before,
they were never freed unless the cache was destroyed (I just wondered why
my system would bury >1G in the magazines).
* Made the magazine capacity variable per cache, ie. for larger objects, it's
not a good idea to have 64*CPU buffers lying around in the worst case.
* Furthermore, the create_object_cache_etc()/object_depot_init() now have
arguments for the magazine capacity as well as the maximum number of full
unused magazines.
* By default, you might want to initialize both to zero, as then some hopefully
usable defaults are computed. Otherwise (the only current example is the
vm_page_mapping cache) you can just put in the values you'd want there.
The page mapping cache uses larger values, as its objects are usually
allocated and deleted in larger chunks.
* Beware, though, I couldn't test these changes yet as Qemu didn't like to run
today. I'll test these changes on another machine now.


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

MemoryManager:
* Added support to do larger raw allocations (up to one large chunk (128 pages))
in the slab areas. For an even larger allocation an area is created (haven't
seen that happen yet, though).
* Added kernel tracing (SLAB_MEMORY_MANAGER_TRACING).
* _FreeArea(): Copy and paste bug: The meta chunks of the to be freed area
would be added to the free lists instead of being removed from them. This
would corrupt the lists and also lead to all kinds of misuse of meta chunks.

object caches:
* Implemented CACHE_ALIGN_ON_SIZE. It is no longer set for all small object
caches, but the block allocator sets it on all power of two size caches.
* object_cache_reserve_internal(): Detect recursion and don't wait in such a
case. The function could deadlock itself, since
HashedObjectCache::CreateSlab() does allocate memory, thus potentially
reentering.
* object_cache_low_memory():
- I missed some returns when reworking that one in r35254, so the function
might stop early and also leave the cache in maintenance mode, which would
cause it to be ignored by object cache resizer and low memory handler from
that point on.
- Since ReturnSlab() potentially unlocks, the conditions weren't quite correct
and too many slabs could be freed.
- Simplified things a bit.
* object_cache_alloc(): Since object_cache_reserve_internal() does potentially
unlock the cache, the situation might have changed and their might not be an
empty slab available, but a partial one. The function would crash.
* Renamed the object cache tracing variable to SLAB_OBJECT_CACHE_TRACING.
* Renamed debugger command "cache_info" to "slab_cache" to avoid confusion with
the VMCache commands.
* ObjectCache::usage was not maintained anymore since I introduced the
MemoryManager. object_cache_get_usage() would thus always return 0 and the
block cache would not be considered cached memory. This was only of
informational relevance, though.

slab allocator misc.:
* Disable the object depots of block allocator caches for object sizes > 2 KB.
Allocations of those sizes aren't so common that the object depots yield any
benefit.
* The slab allocator is now fully self-sufficient. It allocates its bootstrap
memory from the MemoryManager, and the hash tables for HashedObjectCaches use
the block allocator instead of the heap, now.
* Added option to use the slab allocator for malloc() and friends
(USE_SLAB_ALLOCATOR_FOR_MALLOC). Currently disabled. Works in principle and
has virtually no lock contention. Handling for low memory situations is yet
missing, though.
* Improved the output of some debugger commands.


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

Replaced CACHE_DONT_SLEEP by two new flags CACHE_DONT_WAIT_FOR_MEMORY and
CACHE_DONT_LOCK_KERNEL_SPACE. If the former is given, the slab memory manager
does not wait when reserving memory or pages. The latter prevents area
operations. The new flags add a bit of flexibility. E.g. when allocating page
mapping objects for userland areas CACHE_DONT_WAIT_FOR_MEMORY is sufficient,
i.e. the allocation will succeed as long as pages are available.


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

slab allocator:
* Implemented a more elaborated raw memory allocation backend (MemoryManager).
We allocate 8 MB areas whose pages we allocate and map when needed. An area is
divided into equally-sized chunks which form the basic units of allocation. We
have areas with three possible chunk sizes (small, medium, large), which is
basically what the ObjectCache implementations were using anyway.
* Added "uint32 flags" parameter to several of the slab allocator's object
cache and object depot functions. E.g. object_depot_store() potentially wants
to allocate memory for a magazine. But also in pure freeing functions it
might eventually become useful to have those flags, since they could end up
deleting an area, which might not be allowable in all situations. We should
introduce specific flags to indicate that.
* Reworked the block allocator. Since the MemoryManager allocates block-aligned
areas, maintains a hash table for lookup, and maps chunks to object caches,
we can quickly find out which object cache a to be freed allocation belongs
to and thus don't need the boundary tags anymore.
* Reworked the slab boot strap process. We allocate from the initial area only
when really necessary, i.e. when the object cache for the respective
allocation size has not been created yet. A single page is thus sufficient.

other:
* vm_allocate_early(): Added boolean "blockAlign" parameter. If true, the
semantics is the same as for B_ANY_KERNEL_BLOCK_ADDRESS.
* Use an object cache for page mappings. This significantly reduces the
contention on the heap bin locks.


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

* Consequently propagate the CACHE_DONT_SLEEP flag.
* block_alloc(): Create B_FULL_LOCK area.


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

* Renamed headers/private/kernel/slab/Depot.h to ObjectDepot.h.
* Moved the object depot code to its own source file.


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

slab/cache: a couple more fixes.

- on CACHE_DURING_BOOT init benaphore count with 1.
- account for allocated space on early_allocate_pages.
- fixed slab position calculation in small slabs.
- we can now init all allocator sizes early rather than later.


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

cache allocator: keep allocation waste statistics. added debugger command 'show_waste'.


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

cache allocator: for allocations > 8k create areas, and delete them on free.


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

fixed the cache allocator's size_to_cache.


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

pushed the slab init a bit deeper. added a object cache based allocator, including a bootstrap mechanism to have it init during bootup.


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