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/heap: Check for multiplication overflows in calloc.

Logic inspired by musl's.

kernel: Do not invoke memalign with 0 as the alignment argument.

The memalign() function has special semantics for its arguments
even when -fno-builtin is enabled, it seems (that may be a problem
on Clang's part, however.) The alloc_align attribute, which we apply
to the memalign_etc function, does not seem to have the same problems;
at least its documentation at GCC gives no indication that 0 is not a
legal value to pass.

Change-Id: Ie5ba090b924ac3577775165d20f11f9696be97f3

kernel: Remove malloc_referenced now that it is unused.

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

kernel: Fix compiling the debug heap on x86_64.

kernel: Use SMP_MAX_CPUS instead of B_MAX_CPU_COUNT

First round of 64-bit safety fixes in the kernel.

* Most of this is incorrect printf format strings. Changed all strings
causing errors to use the B_PRI* format string definitions, which
means the strings should be correct across all platforms.
* Some other fixes for errors, casts required, etc.

Add heap with guard pages to detect out of bound reads/writes.

This is a very simple heap implementation that allocates memory so that
the end of each allocation always coincides with a page end and is
followed by a guard page which is marked non-present. Out of bounds
access (both read and write) therefore cause a crash (unhandled page
fault).

Note that this allocator is neither speed nor space efficient, indeed it
wastes huge amounts of pages and address space so it is quite easy to
hit limits. It is intended as a pure debug feature.

Prefix the heap version of the "allocations" debugger command with "heap_".


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

Tiny cleanup.


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

bonefish+mmlr:
Move blocking the 0xcccccccc and 0xdeadbeef address ranges from heap to VM init
so that it also works when used in the slab allocator.


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

Make the heap debug functions available when USE_SLAB_ALLOCATOR_FOR_MALLOC is
enabled as well. As this heap implementation is still used for the port heap
(as it handles B_NO_LOCK areas) those are still useful.


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

* Allow heap.cpp to compile if both, KERNEL_HEAP_LEAK_CHECK, and
USE_SLAB_ALLOCATOR_FOR_MALLOC are defined.


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

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

Replaced no longer necessary send_signal_etc() work-arounds for
resume_thread().


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

Move the actual area deletion out of the locked section as we could otherwise
double/deadlock when we delete heap areas because of other area deletions.


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

Fixed typo in area name.


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

Made heap classes const just in case. They really already were though.


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

* Fixed compilation with PARANOID_HEAP_VALIDATION turned on.


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

* Improved panic output I recently ran into.


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

Must only advance by step sizes, otherwise we may end up with misaligned pages
again.


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

Sync kernel heap with alignment handling fixes, simplifications and performance
improvements from debug heap in r35422.


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

* Fixed build with PARANOID_HEAP_VALIDATION.
* heap_index_for(): Could return invalid index, if there hadn't been created
a set of heaps for each CPU.


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

* arch_debug_get_stack_trace():
- Replaced the "userOnly" parameter by a "flags" parameter, that allows to
specify kernel and userland stack traces individually.
- x86, m68k: Don't always skip the first frame as that prevents the caller
from being able to record its own address.
* capture_tracing_stack_trace(): Replaced the "userOnly" parameter by
"kernelOnly", since one is probably always interested in the kernel stack
trace, but might not want the userland stack trace.
* Added stack trace support for VM cache kernel tracing.


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

* Moved the VM headers into subdirectory vm/.
* Renamed vm_cache.h/vm_address_space.h to VMCache.h/VMAddressSpace.


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

* Added "address" specifier for the "allocations" KDL command.
* Removed superfluous malloc.h include.


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

Account for single page allocations. They aren't used anywhere right now because
the bin sizes ensure that when hitting this case it always allocates multiple
pages. This makes it more flexible for other use cases though.


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

mmlr+axeld:
* Fixed some minor issues of heap_create_allocator() when it should use the
kernel heap to allocate its heap structure.
* Fixed an off by one error in the max bin check.
* Changed the KDL "heap" command to allow the "stats" for any heap as well.


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

The allocation size wasn't updated on an area based realloc that would still
fit into the existing area. In that case further reallocs could then assume the
wrong previous size and then not copy enough from the original buffer, leading
to lost bytes at the end of the new buffer.


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

anevilyak+korli+mmlr:
* Check for overflows in memory allocation. If someone happened to (erroneously)
try to allocate a negative amount of memory we could overflow and crash
because of the sizes getting messed up.
* Review and update the alignment logic which was a bit broken for the huge
allocation case (reaching the area threshold). Also assert the results so
next time this will be easier to spot.


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

Make use of the address range blocking to guarantee that accessing 0xdeadbeef
and 0xcccccccc (and 64 pages thereafter) in any way will always lead to a crash.
Before it could happen that these ranges were allocated for an area and then
accessing these would not be as evident anymore. Only enabled when the
corresponding paranoid setting is enabled (which it currently is).


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

When we actually delete the area, we can obviously not access the next pointer
stored in there anymore.


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

Fix errors in maintaining the area list due to assumptions that are only true
for the page list but not the area one. Since multiple pages can be allocated
at once, even an area that is not at the top of the list can become empty. In
such a case the area list would previously have lost entries. Also because
we can remove more than one page from any area, not just the top one, we may
need to move forward in the list so that it stays ordered by free pages.
+alphabranch


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

We can return directly as we use handy locker objects. Adjusted and added
comments.


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

* Set freed memory to 0xdeadbeef before returning it to page. This allows us to
not hold the bin lock while setting and only protect the actual freeing. May
reduce bin lock contention a little bit.
* Tiny optimization for force-clearing 0xdeadbeef. Do it after setting to 0xcc,
so that it's less likely we have to do it.


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

* Fix KDL output to use kprintf instead of dprintf.
* Make the allocations command available even without leak checking. The sizes
that are dumped aren't as accurate without leak checking info, but having the
address and max size is already helpful.


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

* Style cleanup, mostly 80 character limit per line.


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

* The deferred_deleter() kernel daemon dropped out, if the list with
memory to free was empty, but didn't check the list with objects to
delete. So those were queued until someone used deferred_free().
Should fix #3128.
* Run the daemon once a second instead of every five seconds, so memory
is recycled a little quicker.


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

Added new parameter "skipIframes" to arch_debug_get_stack_trace(). That
many iframes are supposed to be skipped before recording the stack
trace. Currently implemented for x86 only.


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

Extended the "heap" debugger command to allow specifying the address of
the heap to print infos about.


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

* Renamed kernel_startup to gKernelStartup.


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

Removed superfluous whitespace.


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

* Change the fixed bin list to a generated one based on a few constraining
factors per heap class. The previous bin sizes would in many cases just have
wasted memory by not fully using up the available space while not providing
any more elements than a bigger size. The computed bins ensure that the best
sizes are used based on a min count, min size, alignment and max waste per
page. Also changed the heap sizes to more reasonable values and renamed them
to small, medium and large.
* Remove the shouldGrow parameter from heap_memalign() and just check it using
heap_should_grow() where appropriate.
* Fix readding a nun-full area to the area list, the added page count can be
bigger than one, therefore the check must be free_page_count == pageCount.
* Simplify ensuring correct alignment, just aligning the size instead of
checking each candidate bin for alignment is enough.

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

Make the all_areas list ordered by base and take advantage of this ordering
when looking up the target area on free(). This makes free() scale better with
large area counts, as the lookup can abort early when it knows that no area
below the only candidate can contain the address.

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

* Give the heaps a name so the grow heap can be distinguished from the small one.
* Rename sHeapList[] to sHeaps[], as there are no heap lists anymore.
* Rename the debug defines to be even more obvious.
* Also initialize allocations by area with non-null values when being paranoid.
* Disabled some debug output.

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

Fix missing newline.

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

* Implement freeing of empty heap areas. When a heap_area becomes completely
empty and there is another empty area already, it is now removed from the
heap and the underlying area is deleted.
* Fix grow suggestions to be based on 20% of a grow size instead of 10% of the
current page count, as the current page count obviously gets larger over time
making 10% of it larger than the grow size itself.
* Fix non-urgent grow request handling so that not two areas at once get added.
* Made some of the debug output more useful, turned off some other and fixed
some comments.

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

Another partial rewrite of the kernel heap. There are no heap lists anymore,
there is only one heap_allocator for each heap class. Instead of adding
complete allocators, individual areas can now be added to existing allocators.
This removes a lot of complexity in the frontend code and avoids the previous
duplications wasting resources (allocator lock, bin sizes, bin list).
The pages are now managed in heap_area structures that are attached to areas.
They store the page table, page free lists and local variables. The same
mechanism as used for heap_pages is now used for heap_areas too, i.e. they
are kept in a sorted list where the fullest but not yet completely full area
is always at the top. This favors areas to become completely full and other,
not as frequently used areas, to become completely empty over time so they can
be freed. Full areas are removed from the list, so they do not need to be
looked at/skipped when allocating new pages. Through this mechanism and as
there are no allocator lists anymore that grow bigger over time, allocations
should be far more scalable. Note that actually removing areas once they are
not needed anymore is still not implemented, but it is now a relatively easy
addition whereas previously it would have killed the whole design.

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

* Fix the broken size/alignment computations for area allocations by replacing
them with the ROUNDUP macro that was specifically made for this task so that
too tired developers do not mess up the calculations...
* Don't use area allocation during kernel startup (not that it really happened).
* Minor simplification of similar calculations in heap_attach().

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

Added grow request tracking again. In case an allocation fails due to lack of
contiguous pages, it will request growing even if there are still more than
10% free pages available. Previously that case was not handled anymore and the
allocation would have just failed. Note that this is a pretty rare case, as
there are no "large" allocations happening in either the small or large heap
classes, but only in the huge one for allocations between 128KB and 1MB.

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

Implement transparent allocation by area for huge allocations (> 1MB). This
does in fact happen, as there are objects used in the kernel that allocate
with new, which in turn uses the heap. The OpenHashTable used from the slab
allocator hit this case during an svn checkout here, because it grows it's new
allocated list by doubling the list size. Added some unconditional debug
output for those cases to monitor the usage for now. All of that not yet really
tested though.

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

Fix subtle logic error that would always cause a needless large allocation if an alignment was given.

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

The simple alignment trick used before doesn't work with the new heap classes
(it didn't really work previously anyway). The only alignment really used seems
to be B_PAGE_SIZE, which happened to always work out before, because anything
larger would have been allocated using individual pages anyway. Since larger
bins are now available and with kernel heap leak checking enabled an allocation
of B_PAGE_SIZE with B_PAGE_SIZE alignment is actually a bit bigger than
B_PAGE_SIZE, it got into the 5KB bin, which didn't guarantee the alignment
anymore. This would have caused a tripple fault on boot when kernel heap leak
checking was enabled. The alignment is now taken into account when picking
the bin for the allocation. Added a more detailed TODO as to why this isn't
the best thing (wastes space) and how it could be changed if deemed necessary.

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

Remove the B_PAGE_SIZE page size and replace it by a heap->page_size. This
allows for dynamic (heap)page sizes. It's currently just set to B_PAGE_SIZE
but I'm expermienting with the creation of differently sized heaps that could
use dynamic page sizes with that.

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

Take a shortcut when freeing in heap_realloc(), we already know the address belongs to our heap.

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

* Implement counting free pages in kernel heaps.
* Suggest growing when there are less than 10% free pages in the last heap.
Previously it would suggest growing when there were less than three free
pages, which wasn't really any good measure. In quite a few cases this could
have lead to too late growing and running out of heap space.
* Only panic when memory allocation fails while growing kernel heaps. Otherwise
just output a message and return NULL. Even this panic is not really
necessary and should be continueable, but for now I'd like to see if this
situation actually happens.

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

Directly use memalign instead of malloc to safe one indirection.

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

* When KERNEL_HEAP_LEAK_CHECK is enabled we also store the calling
function requesting the allocation.
* The "allocations" commands does also print the caller and can filter
by caller, now.
* Added new "allocations_per_caller" command, which sums up allocations
per caller and prints them in a table sorted by size or count.


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

* Removed old mutex implementation and renamed cutex to mutex.
* Trivial adjustments of code using mutexes. Mostly removing the
mutex_init() return value check.
* Added mutex_lock_threads_locked(), which is called with the threads
spinlock being held. The spinlock is released while waiting, of
course. This function is useful in cases where the existence of the
mutex object is ensured by holding the threads spinlock.
* Changed the two instances in the VFS code where an IO context of
another team needs to be locked to use mutex_lock_threads_locked().
Before it required a semaphore-based mutex implementation.


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

reverted r25227. Thanks for the hint Ingo :)


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

build fix (with no tracing conf)


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

* Changed macros that enable tracing for individual components from
defined/undefined to numeric values (0 for undefined). This allows for
trace levels.
* Set SYSCALL_TRACING_IGNORE_KTRACE_OUTPUT default to 1, since this is
what one usually wants.


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

Use a union instead of the macro.


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

Use the empty_index field as the allocation_id for large allocations and just
use the index of the first page of the allocation as an id. This removes the
need for separate id generation. This also fixes the possible problem of
multiple large allocations getting the same allocation_id (due to the limited
range of possible ids), which in the worst case (i.e. for adjacent allocations)
could cause pages to be freed that were still in use.

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

Fix bad error in calculating the leak check info address when updating the
size of a reallocated block. If you had kernel heap leak checking on, this
could have caused the first four bytes of the next block to be overwritten
with the size of the reallocation of the previous block.

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

* Add a "stats" argument to the kernel heap leak checker to only print the
total count of allocations and bytes.
* Also add a few more bin sizes (for 8, 24 and 48 bytes) turns out especially
allocations of 20-24 bytes are pretty common. And as it only wastes a few
bytes per page this doesn't hurt at all.

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

Only clear 0xdeadbeef if there is 0xdeadbeef present. The size field of the
heap leak check info would otherwise be overwritten for allocations that still
fit the 16 byte bin (i.e. allocations of 0-4 bytes).

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

Adding two debug features to the new heap implementation:

* Tracing of allocations, reallocations and frees
* Leak checking infrastructure to dump allocations

The leak checking code records the team and thread id when an allocation is
made as well as stores the originally requested size. It also adds the
"allocations" debugger command that can dump all current allocations (usually
a huge list) or filter by either a team or thread id. This way it's easily
possible to find leftover allocations of no more active teams/threads.
Combined with the tracing support one might be able to track down the time and
reason of an allocation and possibly find the corresponding leak if it is one.
Note that kernel heap leak checking has to be enabled manually by setting the
KERNEL_HEAP_LEAK_CHECK define to 1.

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

kernel: Use SMP_MAX_CPUS instead of B_MAX_CPU_COUNT

First round of 64-bit safety fixes in the kernel.

* Most of this is incorrect printf format strings. Changed all strings
causing errors to use the B_PRI* format string definitions, which
means the strings should be correct across all platforms.
* Some other fixes for errors, casts required, etc.

Add heap with guard pages to detect out of bound reads/writes.

This is a very simple heap implementation that allocates memory so that
the end of each allocation always coincides with a page end and is
followed by a guard page which is marked non-present. Out of bounds
access (both read and write) therefore cause a crash (unhandled page
fault).

Note that this allocator is neither speed nor space efficient, indeed it
wastes huge amounts of pages and address space so it is quite easy to
hit limits. It is intended as a pure debug feature.

Prefix the heap version of the "allocations" debugger command with "heap_".


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

Tiny cleanup.


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

bonefish+mmlr:
Move blocking the 0xcccccccc and 0xdeadbeef address ranges from heap to VM init
so that it also works when used in the slab allocator.


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

Make the heap debug functions available when USE_SLAB_ALLOCATOR_FOR_MALLOC is
enabled as well. As this heap implementation is still used for the port heap
(as it handles B_NO_LOCK areas) those are still useful.


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

* Allow heap.cpp to compile if both, KERNEL_HEAP_LEAK_CHECK, and
USE_SLAB_ALLOCATOR_FOR_MALLOC are defined.


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

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

Replaced no longer necessary send_signal_etc() work-arounds for
resume_thread().


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

Move the actual area deletion out of the locked section as we could otherwise
double/deadlock when we delete heap areas because of other area deletions.


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

Fixed typo in area name.


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

Made heap classes const just in case. They really already were though.


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

* Fixed compilation with PARANOID_HEAP_VALIDATION turned on.


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

* Improved panic output I recently ran into.


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

Must only advance by step sizes, otherwise we may end up with misaligned pages
again.


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

Sync kernel heap with alignment handling fixes, simplifications and performance
improvements from debug heap in r35422.


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

* Fixed build with PARANOID_HEAP_VALIDATION.
* heap_index_for(): Could return invalid index, if there hadn't been created
a set of heaps for each CPU.


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

* arch_debug_get_stack_trace():
- Replaced the "userOnly" parameter by a "flags" parameter, that allows to
specify kernel and userland stack traces individually.
- x86, m68k: Don't always skip the first frame as that prevents the caller
from being able to record its own address.
* capture_tracing_stack_trace(): Replaced the "userOnly" parameter by
"kernelOnly", since one is probably always interested in the kernel stack
trace, but might not want the userland stack trace.
* Added stack trace support for VM cache kernel tracing.


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

* Moved the VM headers into subdirectory vm/.
* Renamed vm_cache.h/vm_address_space.h to VMCache.h/VMAddressSpace.


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

* Added "address" specifier for the "allocations" KDL command.
* Removed superfluous malloc.h include.


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

Account for single page allocations. They aren't used anywhere right now because
the bin sizes ensure that when hitting this case it always allocates multiple
pages. This makes it more flexible for other use cases though.


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

mmlr+axeld:
* Fixed some minor issues of heap_create_allocator() when it should use the
kernel heap to allocate its heap structure.
* Fixed an off by one error in the max bin check.
* Changed the KDL "heap" command to allow the "stats" for any heap as well.


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

The allocation size wasn't updated on an area based realloc that would still
fit into the existing area. In that case further reallocs could then assume the
wrong previous size and then not copy enough from the original buffer, leading
to lost bytes at the end of the new buffer.


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

anevilyak+korli+mmlr:
* Check for overflows in memory allocation. If someone happened to (erroneously)
try to allocate a negative amount of memory we could overflow and crash
because of the sizes getting messed up.
* Review and update the alignment logic which was a bit broken for the huge
allocation case (reaching the area threshold). Also assert the results so
next time this will be easier to spot.


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

Make use of the address range blocking to guarantee that accessing 0xdeadbeef
and 0xcccccccc (and 64 pages thereafter) in any way will always lead to a crash.
Before it could happen that these ranges were allocated for an area and then
accessing these would not be as evident anymore. Only enabled when the
corresponding paranoid setting is enabled (which it currently is).


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

When we actually delete the area, we can obviously not access the next pointer
stored in there anymore.


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

Fix errors in maintaining the area list due to assumptions that are only true
for the page list but not the area one. Since multiple pages can be allocated
at once, even an area that is not at the top of the list can become empty. In
such a case the area list would previously have lost entries. Also because
we can remove more than one page from any area, not just the top one, we may
need to move forward in the list so that it stays ordered by free pages.
+alphabranch


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

We can return directly as we use handy locker objects. Adjusted and added
comments.


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

* Set freed memory to 0xdeadbeef before returning it to page. This allows us to
not hold the bin lock while setting and only protect the actual freeing. May
reduce bin lock contention a little bit.
* Tiny optimization for force-clearing 0xdeadbeef. Do it after setting to 0xcc,
so that it's less likely we have to do it.


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

* Fix KDL output to use kprintf instead of dprintf.
* Make the allocations command available even without leak checking. The sizes
that are dumped aren't as accurate without leak checking info, but having the
address and max size is already helpful.


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

* Style cleanup, mostly 80 character limit per line.


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

* The deferred_deleter() kernel daemon dropped out, if the list with
memory to free was empty, but didn't check the list with objects to
delete. So those were queued until someone used deferred_free().
Should fix #3128.
* Run the daemon once a second instead of every five seconds, so memory
is recycled a little quicker.


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

Added new parameter "skipIframes" to arch_debug_get_stack_trace(). That
many iframes are supposed to be skipped before recording the stack
trace. Currently implemented for x86 only.


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

Extended the "heap" debugger command to allow specifying the address of
the heap to print infos about.


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

* Renamed kernel_startup to gKernelStartup.


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

Removed superfluous whitespace.


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

* Change the fixed bin list to a generated one based on a few constraining
factors per heap class. The previous bin sizes would in many cases just have
wasted memory by not fully using up the available space while not providing
any more elements than a bigger size. The computed bins ensure that the best
sizes are used based on a min count, min size, alignment and max waste per
page. Also changed the heap sizes to more reasonable values and renamed them
to small, medium and large.
* Remove the shouldGrow parameter from heap_memalign() and just check it using
heap_should_grow() where appropriate.
* Fix readding a nun-full area to the area list, the added page count can be
bigger than one, therefore the check must be free_page_count == pageCount.
* Simplify ensuring correct alignment, just aligning the size instead of
checking each candidate bin for alignment is enough.

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

Make the all_areas list ordered by base and take advantage of this ordering
when looking up the target area on free(). This makes free() scale better with
large area counts, as the lookup can abort early when it knows that no area
below the only candidate can contain the address.

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

* Give the heaps a name so the grow heap can be distinguished from the small one.
* Rename sHeapList[] to sHeaps[], as there are no heap lists anymore.
* Rename the debug defines to be even more obvious.
* Also initialize allocations by area with non-null values when being paranoid.
* Disabled some debug output.

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

Fix missing newline.

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

* Implement freeing of empty heap areas. When a heap_area becomes completely
empty and there is another empty area already, it is now removed from the
heap and the underlying area is deleted.
* Fix grow suggestions to be based on 20% of a grow size instead of 10% of the
current page count, as the current page count obviously gets larger over time
making 10% of it larger than the grow size itself.
* Fix non-urgent grow request handling so that not two areas at once get added.
* Made some of the debug output more useful, turned off some other and fixed
some comments.

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

Another partial rewrite of the kernel heap. There are no heap lists anymore,
there is only one heap_allocator for each heap class. Instead of adding
complete allocators, individual areas can now be added to existing allocators.
This removes a lot of complexity in the frontend code and avoids the previous
duplications wasting resources (allocator lock, bin sizes, bin list).
The pages are now managed in heap_area structures that are attached to areas.
They store the page table, page free lists and local variables. The same
mechanism as used for heap_pages is now used for heap_areas too, i.e. they
are kept in a sorted list where the fullest but not yet completely full area
is always at the top. This favors areas to become completely full and other,
not as frequently used areas, to become completely empty over time so they can
be freed. Full areas are removed from the list, so they do not need to be
looked at/skipped when allocating new pages. Through this mechanism and as
there are no allocator lists anymore that grow bigger over time, allocations
should be far more scalable. Note that actually removing areas once they are
not needed anymore is still not implemented, but it is now a relatively easy
addition whereas previously it would have killed the whole design.

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

* Fix the broken size/alignment computations for area allocations by replacing
them with the ROUNDUP macro that was specifically made for this task so that
too tired developers do not mess up the calculations...
* Don't use area allocation during kernel startup (not that it really happened).
* Minor simplification of similar calculations in heap_attach().

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

Added grow request tracking again. In case an allocation fails due to lack of
contiguous pages, it will request growing even if there are still more than
10% free pages available. Previously that case was not handled anymore and the
allocation would have just failed. Note that this is a pretty rare case, as
there are no "large" allocations happening in either the small or large heap
classes, but only in the huge one for allocations between 128KB and 1MB.

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

Implement transparent allocation by area for huge allocations (> 1MB). This
does in fact happen, as there are objects used in the kernel that allocate
with new, which in turn uses the heap. The OpenHashTable used from the slab
allocator hit this case during an svn checkout here, because it grows it's new
allocated list by doubling the list size. Added some unconditional debug
output for those cases to monitor the usage for now. All of that not yet really
tested though.

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

Fix subtle logic error that would always cause a needless large allocation if an alignment was given.

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

The simple alignment trick used before doesn't work with the new heap classes
(it didn't really work previously anyway). The only alignment really used seems
to be B_PAGE_SIZE, which happened to always work out before, because anything
larger would have been allocated using individual pages anyway. Since larger
bins are now available and with kernel heap leak checking enabled an allocation
of B_PAGE_SIZE with B_PAGE_SIZE alignment is actually a bit bigger than
B_PAGE_SIZE, it got into the 5KB bin, which didn't guarantee the alignment
anymore. This would have caused a tripple fault on boot when kernel heap leak
checking was enabled. The alignment is now taken into account when picking
the bin for the allocation. Added a more detailed TODO as to why this isn't
the best thing (wastes space) and how it could be changed if deemed necessary.

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

Remove the B_PAGE_SIZE page size and replace it by a heap->page_size. This
allows for dynamic (heap)page sizes. It's currently just set to B_PAGE_SIZE
but I'm expermienting with the creation of differently sized heaps that could
use dynamic page sizes with that.

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

Take a shortcut when freeing in heap_realloc(), we already know the address belongs to our heap.

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

* Implement counting free pages in kernel heaps.
* Suggest growing when there are less than 10% free pages in the last heap.
Previously it would suggest growing when there were less than three free
pages, which wasn't really any good measure. In quite a few cases this could
have lead to too late growing and running out of heap space.
* Only panic when memory allocation fails while growing kernel heaps. Otherwise
just output a message and return NULL. Even this panic is not really
necessary and should be continueable, but for now I'd like to see if this
situation actually happens.

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

Directly use memalign instead of malloc to safe one indirection.

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

* When KERNEL_HEAP_LEAK_CHECK is enabled we also store the calling
function requesting the allocation.
* The "allocations" commands does also print the caller and can filter
by caller, now.
* Added new "allocations_per_caller" command, which sums up allocations
per caller and prints them in a table sorted by size or count.


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

* Removed old mutex implementation and renamed cutex to mutex.
* Trivial adjustments of code using mutexes. Mostly removing the
mutex_init() return value check.
* Added mutex_lock_threads_locked(), which is called with the threads
spinlock being held. The spinlock is released while waiting, of
course. This function is useful in cases where the existence of the
mutex object is ensured by holding the threads spinlock.
* Changed the two instances in the VFS code where an IO context of
another team needs to be locked to use mutex_lock_threads_locked().
Before it required a semaphore-based mutex implementation.


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

reverted r25227. Thanks for the hint Ingo :)


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

build fix (with no tracing conf)


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

* Changed macros that enable tracing for individual components from
defined/undefined to numeric values (0 for undefined). This allows for
trace levels.
* Set SYSCALL_TRACING_IGNORE_KTRACE_OUTPUT default to 1, since this is
what one usually wants.


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

Use a union instead of the macro.


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

Use the empty_index field as the allocation_id for large allocations and just
use the index of the first page of the allocation as an id. This removes the
need for separate id generation. This also fixes the possible problem of
multiple large allocations getting the same allocation_id (due to the limited
range of possible ids), which in the worst case (i.e. for adjacent allocations)
could cause pages to be freed that were still in use.

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

Fix bad error in calculating the leak check info address when updating the
size of a reallocated block. If you had kernel heap leak checking on, this
could have caused the first four bytes of the next block to be overwritten
with the size of the reallocation of the previous block.

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

* Add a "stats" argument to the kernel heap leak checker to only print the
total count of allocations and bytes.
* Also add a few more bin sizes (for 8, 24 and 48 bytes) turns out especially
allocations of 20-24 bytes are pretty common. And as it only wastes a few
bytes per page this doesn't hurt at all.

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

Only clear 0xdeadbeef if there is 0xdeadbeef present. The size field of the
heap leak check info would otherwise be overwritten for allocations that still
fit the 16 byte bin (i.e. allocations of 0-4 bytes).

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

Adding two debug features to the new heap implementation:

* Tracing of allocations, reallocations and frees
* Leak checking infrastructure to dump allocations

The leak checking code records the team and thread id when an allocation is
made as well as stores the originally requested size. It also adds the
"allocations" debugger command that can dump all current allocations (usually
a huge list) or filter by either a team or thread id. This way it's easily
possible to find leftover allocations of no more active teams/threads.
Combined with the tracing support one might be able to track down the time and
reason of an allocation and possibly find the corresponding leak if it is one.
Note that kernel heap leak checking has to be enabled manually by setting the
KERNEL_HEAP_LEAK_CHECK define to 1.

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