summaryrefslogtreecommitdiff
path: root/Kernel/Heap
AgeCommit message (Collapse)Author
2021-01-26Meta: Split debug defines into multiple headers.asynts
The following script was used to make these changes: #!/bin/bash set -e tmp=$(mktemp -d) echo "tmp=$tmp" find Kernel \( -name '*.cpp' -o -name '*.h' \) | sort > $tmp/Kernel.files find . \( -path ./Toolchain -prune -o -path ./Build -prune -o -path ./Kernel -prune \) -o \( -name '*.cpp' -o -name '*.h' \) -print | sort > $tmp/EverythingExceptKernel.files cat $tmp/Kernel.files | xargs grep -Eho '[A-Z0-9_]+_DEBUG' | sort | uniq > $tmp/Kernel.macros cat $tmp/EverythingExceptKernel.files | xargs grep -Eho '[A-Z0-9_]+_DEBUG' | sort | uniq > $tmp/EverythingExceptKernel.macros comm -23 $tmp/Kernel.macros $tmp/EverythingExceptKernel.macros > $tmp/Kernel.unique comm -1 $tmp/Kernel.macros $tmp/EverythingExceptKernel.macros > $tmp/EverythingExceptKernel.unique cat $tmp/Kernel.unique | awk '{ print "#cmakedefine01 "$1 }' > $tmp/Kernel.header cat $tmp/EverythingExceptKernel.unique | awk '{ print "#cmakedefine01 "$1 }' > $tmp/EverythingExceptKernel.header for macro in $(cat $tmp/Kernel.unique) do cat $tmp/Kernel.files | xargs grep -l $macro >> $tmp/Kernel.new-includes ||: done cat $tmp/Kernel.new-includes | sort > $tmp/Kernel.new-includes.sorted for macro in $(cat $tmp/EverythingExceptKernel.unique) do cat $tmp/Kernel.files | xargs grep -l $macro >> $tmp/Kernel.old-includes ||: done cat $tmp/Kernel.old-includes | sort > $tmp/Kernel.old-includes.sorted comm -23 $tmp/Kernel.new-includes.sorted $tmp/Kernel.old-includes.sorted > $tmp/Kernel.includes.new comm -13 $tmp/Kernel.new-includes.sorted $tmp/Kernel.old-includes.sorted > $tmp/Kernel.includes.old comm -12 $tmp/Kernel.new-includes.sorted $tmp/Kernel.old-includes.sorted > $tmp/Kernel.includes.mixed for file in $(cat $tmp/Kernel.includes.new) do sed -i -E 's/#include <AK\/Debug\.h>/#include <Kernel\/Debug\.h>/' $file done for file in $(cat $tmp/Kernel.includes.mixed) do echo "mixed include in $file, requires manual editing." done
2021-01-25Everywhere: Hook up remaining debug macros to Debug.h.asynts
2021-01-25Everywhere: Remove unnecessary debug comments.asynts
It would be tempting to uncomment these statements, but that won't work with the new changes. This was done with the following commands: find . \( -name '*.cpp' -o -name '*.h' -o -name '*.in' \) -not -path './Toolchain/*' -not -path './Build/*' -exec awk -i inplace '$0 !~ /\/\/#define/ { if (!toggle) { print; } else { toggle = !toggle } } ; $0 ~/\/\/#define/ { toggle = 1 }' {} \; find . \( -name '*.cpp' -o -name '*.h' -o -name '*.in' \) -not -path './Toolchain/*' -not -path './Build/*' -exec awk -i inplace '$0 !~ /\/\/ #define/ { if (!toggle) { print; } else { toggle = !toggle } } ; $0 ~/\/\/ #define/ { toggle = 1 }' {} \;
2021-01-22Kernel: Move kmalloc heaps and super pages inside .bss segmentJean-Baptiste Boric
The kernel ignored the first 8 MiB of RAM while parsing the memory map because the kmalloc heaps and the super physical pages lived here. Move all that stuff inside the .bss segment so that those memory regions are accounted for, otherwise we risk overwriting boot modules placed next to the kernel.
2021-01-11Everywhere: Replace a bundle of dbg with dbgln.asynts
These changes are arbitrarily divided into multiple commits to make it easier to find potentially introduced bugs with git bisect.Everything:
2021-01-04Kernel: Specify default memory order for some non-synchronizing AtomicsTom
2021-01-01Kernel: Merge PurgeableVMObject into AnonymousVMObjectTom
This implements memory commitments and lazy-allocation of committed memory.
2021-01-01Kernel: Memory purging improvementsTom
This adds the ability for a Region to define volatile/nonvolatile areas within mapped memory using madvise(). This also means that memory purging takes into account all views of the PurgeableVMObject and only purges memory that is not needed by all of them. When calling madvise() to change an area to nonvolatile memory, return whether memory from that area was purged. At that time also try to remap all memory that is requested to be nonvolatile, and if insufficient pages are available notify the caller of that fact.
2020-12-31Kernel: Fix heap expansions deadlockTom
If a heap expansion is triggered by allocating from e.g. the RangeAllocator, which may be holding a spin lock, we cannot immediately allocate another block of backup memory, which could require the same locks to be acquired. So, defer allocating the backup memory Fixes #4675
2020-12-26Kernel: Remove subheap from list before removing memoryTom
When the ExpandableHeap calls the remove_memory function, the subheap is assumed to be removed and freed entirely. remove_memory may drop the underlying memory at any time, but it also may cause further allocation requests. Not removing it from the list before calling remove_memory could cause a memory allocation in that subheap while remove_memory is executing. which then causes issues once the underlying memory is actually freed.
2020-11-04Kernel: Defer kmalloc heap contractionTom
Because allocating/freeing regions may require locks that need to wait on other processors for completion, this needs to be delayed until it's safer. Otherwise it is possible to deadlock because we're holding the global heap lock.
2020-11-01Kernel: kmalloc_eternal should align pointersTom
2020-09-25Meta+Kernel: Make clang-format-10 cleanBen Wiederhake
2020-09-09Kernel: Fix heap expansion loopTom
By being a bit too greedy and only allocating how much we need for the failing allocation, we can end up in an infinite loop trying to expand the heap further. That's because there are other allocations (e.g. logging, vmobjects, regions, ...) that happen before we finally retry the failed allocation request. Also fix allocating in page size increments, which lead to an assertion when the heap had to grow more than the 1 MiB backup.
2020-09-02Kernel: Use removed memory as backup if backup hasn't been allocatedTom
It may be impossible to allocate more backup memory after expanding the heap if memory is running low. In that case we wouldn't allocate backup memory until trying to expand the heap again. But we also wouldn't take advantage of using removed memory as backup, which means that no backup memory would be available when the heap needs to grow again, causing subsequent expansion to fail because there is no backup memory.
2020-09-02Kernel: Prevent recursive expansion or removing memory while expanding itTom
The process of expanding memory requires allocations and deallocations on the heap itself. So, while we're trying to expand the heap, don't remove memory just because we might briefly not need it. Also prevent recursive expansion attempts.
2020-08-30Kernel: Make Heap implementation reusable, and make kmalloc expandableTom
Add an ExpandableHeap and switch kmalloc to use it, which allows for the kmalloc heap to grow as needed. In order to make heap expansion to work, we keep around a 1 MiB backup memory region, because creating a region would require space in the same heap. This means, the heap will grow as soon as the reported utilization is less than 1 MiB. It will also return memory if an entire subheap is no longer needed, although that is rarely possible.
2020-08-25Kernel: Optimize SlabAllocator to be lock-freeTom
2020-08-25Kernel: Fix kmalloc memory corruptionTom
Rather than hardcoding where the kmalloc pool should be, place it at the end of the kernel image instead. This avoids corrupting global variables or other parts of the kernel as it grows. Fixes #3257
2020-08-22Revert "Kernel: Fix kmalloc memory corruption"Andreas Kling
This reverts commit b306f240a4a3ef4a8f5797734457572e0026cc0c.
2020-08-22Kernel: Fix kmalloc memory corruptionTom
Rather than hardcoding where the kmalloc pool should be, place it at the end of the kernel image instead. This avoids corrupting global variables or other parts of the kernel as it grows. Fixes #3257
2020-08-16AK: Rename KB, MB, GB to KiB, MiB, GiBNico Weber
The SI prefixes "k", "M", "G" mean "10^3", "10^6", "10^9". The IEC prefixes "Ki", "Mi", "Gi" mean "2^10", "2^20", "2^30". Let's use the correct name, at least in code. Only changes the name of the constants, no other behavior change.
2020-08-14Kernel: mark kmalloc with attributesMuhammad Zahalqa
2020-08-10Kernel: Include the 128 byte slab allocator in for_each_allocatorTom
2020-08-10Kernel: Invoke heap constructors separately early onTom
By having a separate list of constructors for the kernel heap code, we can properly use constructors without re-running them after the heap was already initialized. This solves some problems where values were wiped out because they were overwritten by running their constructors later in the initialization process.
2020-07-06Kernel: Add SMP IPI supportTom
We can now properly initialize all processors without crashing by sending SMP IPI messages to synchronize memory between processors. We now initialize the APs once we have the scheduler running. This is so that we can process IPI messages from the other cores. Also rework interrupt handling a bit so that it's more of a 1:1 mapping. We need to allocate non-sharable interrupts for IPIs. This also fixes the occasional hang/crash because all CPUs now synchronize memory with each other.
2020-07-06Kernel: Add a SpinLock to the WaitQueueTom
We need to be able to prevent a WaitQueue from being modified by another CPU. So, add a SpinLock to it. Because this pushes some other class over the 64 byte limit, we also need to add another 128-byte bucket to the slab allocator.
2020-07-03Kernel: Change kmalloc lock to be recursiveTom
If the heap code dumps a stack trace (e.g. out of memory) then it may recursively call into it. Rather than deadlocking, allow recursion.
2020-07-01Kernel: Serialize debug outputTom
2020-06-17Meta: Scale back overly informal user-facing stringsAndreas Kling
We were getting a little overly memey in some places, so let's scale things back to business-casual. Informal language is fine in comments, commits and debug logs, but let's keep the runtime nice and presentable. :^)
2020-05-20Revert "Kernel: Add implementation of operator new and delete to kmalloc.cpp"Andreas Kling
This reverts commit 6d0d8487201eb3cc8d63a1d066a0735a97cdc6e3.
2020-05-20Kernel: Add implementation of operator new and delete to kmalloc.cppAndrew Kaster
This was missing before, we were getting it for free from libstdc++
2020-05-16Kernel: Absorb LibBareMetal back into the kernelAndreas Kling
This was supposed to be the foundation for some kind of pre-kernel environment, but nobody is working on it right now, so let's move everything back into the kernel and remove all the confusion.
2020-05-16Kernel: Use consistent names for kmalloc globals and remove volatileAndreas Kling
2020-04-30AK: Add ALWAYS_INLINE, NEVER_INLINE and FLATTEN macrosAndreas Kling
It's tedious to write (and look at) [[gnu::always_inline]] etc. :^)
2020-04-08Kernel: Update cryptically-named functions related to symbolicationAndreas Kling
2020-04-06Kernel: Support best fit allocation policy in kmalloc()nimelehin
Add find_best_fit() which implements best fit allocation algorithm. Kmalloc now uses a best fit allocation policy for large allocations.
2020-04-06Kernel: Implement kmalloc() using AK::Bitmapnimelehin
kmalloc's bitmap is wrapped with AK::Bitmap to access AK::Bitmap's functions.
2020-03-08Kernel: Add missing #includes now that <AK/StdLibExtras.h> is smallerAndreas Kling
2020-03-08AK: Add global FlatPtr typedef. It's u32 or u64, based on sizeof(void*)Andreas Kling
Use this instead of uintptr_t throughout the codebase. This makes it possible to pass a FlatPtr to something that has u32 and u64 overloads.
2020-03-02Kernel: Use klog() instead of kprintf()Liav A
Also, duplicate data in dbg() and klog() calls were removed. In addition, leakage of virtual address to kernel log is prevented. This is done by replacing kprintf() calls to dbg() calls with the leaked data instead. Also, other kprintf() calls were replaced with klog().
2020-02-27Kernel: Run clang-format on Heap/kmalloc.cppLiav A
2020-02-27Heap kmalloc: Use dbg() instead of dbgprintf()Liav A
2020-02-26Kernel: Sanitize memory coming in/out of the slab allocatorAndreas Kling
We were using SANITIZE_KMALLOC which was never defined in this .cpp file, oops. Now we actually scrub on slab_alloc() and slab_dealloc().
2020-02-22Kernel: Remove unnecessary allocation metadata from kmalloc() chunksAndreas Kling
Each allocation header was tracking its index into the chunk bitmap, but that index can be computed from the allocation address anyway. Removing this means that each allocation gets 4 more bytes of memory and this avoids allocating an extra chunk in many cases. :^)
2020-02-22Kernel: Tweak SlabAllocator's slab sizesAndreas Kling
Nobody was using the 8-byte slab size, so get rid of it and move all of its capacity to the new 64-byte slab size (which replaces 48-byte.)
2020-02-22Kernel: Increase kmalloc chunk size from 8 bytes to 32 bytesAndreas Kling
This gives a huge speedup when running "git status" in a SerenityOS repository directory. Most of the time was spent allocating strings.
2020-02-17Kernel: Replace "current" with Thread::current and Process::currentAndreas Kling
Suggested by Sergey. The currently running Thread and Process are now Thread::current and Process::current respectively. :^)
2020-02-16Kernel: Move all code into the Kernel namespaceAndreas Kling
2020-02-09Kernel: Apply changes to use LibBareMetal definitionsLiav A