summaryrefslogtreecommitdiff
path: root/Kernel/VM/RangeAllocator.cpp
AgeCommit message (Collapse)Author
2021-08-06Kernel: Rename Kernel/VM/ to Kernel/Memory/Andreas Kling
This directory isn't just about virtual memory, it's about all kinds of memory management.
2021-07-18Kernel: Make allocate_randomized() work for 64-bit addressesGunnar Beutner
The odds of finding a suitable address in 1000 attempts were not in our favor given the size of the 64-bit address space.
2021-07-17Kernel: Declare VM/RangeAllocator trivial destructor as defaultBrian Gianforcaro
This is a clang tidy recommendation.
2021-07-17Kernel: Remove stale include from VM/RangeAllocator.cppBrian Gianforcaro
This was left over after the latest big refactor of the VM subsystem.
2021-07-17Kernel: Convert RangeAllocator VERIFY to proper error handlingBrian Gianforcaro
If a user allocates above 0x0 and below the allowable usermode virtual address space, we need to return error instead of asserting. Fixes: #8484
2021-07-15Kernel: Convert RangeAllocator to using a RedBlackTree internallyAndreas Kling
This data structure is a much better fit for what is essentially a sorted list of non-overlapping ranges. Not using Vector means we no longer have to worry about Vector buffers getting huge. Only nice & small allocations from now on.
2021-07-15Kernel: Hoist VERIFY from a loop in RangeAllocator::allocate_specific()Andreas Kling
2021-07-15Kernel: Convert RangeAllocator to east-const styleAndreas Kling
2021-07-11Kernel: Remove unused header includes in VM subtreeBrian Gianforcaro
2021-05-29Everywhere: Sort out superfluous QuickSort.h importsBen Wiederhake
They were sorta unneeded. :^)
2021-04-22Everything: Move to SPDX license identifiers in all files.Brian Gianforcaro
SPDX License Identifiers are a more compact / standardized way of representing file license information. See: https://spdx.dev/resources/use/#identifiers This was done with the `ambr` search and replace tool. ambr --no-parent-ignore --key-from-file --rep-from-file key.txt rep.txt *
2021-02-27Kernel: Use get_fast_random() for MAP_RANDOMIZED addressesAndreas Kling
Let's not block sys$mmap() on kernel randomness.
2021-02-25Kernel: Move the VM Range class to its own filesAndreas Kling
2021-02-23Everywhere: Rename ASSERT => VERIFYAndreas Kling
(...and ASSERT_NOT_REACHED => VERIFY_NOT_REACHED) Since all of these checks are done in release builds as well, let's rename them to VERIFY to prevent confusion, as everyone is used to assertions being compiled out in release. We can introduce a new ASSERT macro that is specifically for debug checks, but I'm doing this wholesale conversion first since we've accumulated thousands of these already, and it's not immediately obvious which ones are suitable for ASSERT.
2021-02-12Kernel: Make MAP_RANDOMIZED honor alignment requestsAndreas Kling
Previously, we only cared about the alignment on the fallback path.
2021-02-12Kernel: Convert klog() to dmesgln() in RangeAllocatorAndreas Kling
2021-02-11Kernel: Remove a handful of unused things in VM/ directoryAndreas Kling
Also add some missing initializers.
2021-01-29Kernel: RangeAllocator randomized correctly check if size is in bound. (#5164)Jorropo
The random address proposals were not checked with the size so it was increasely likely to try to allocate outside of available space with larger and larger sizes. Now they will be ignored instead of triggering a Kernel assertion failure. This is a continuation of: c8e7baf4b8d9da51e925d029254aaf3c8ed8c5e4
2021-01-29Kernel: Check for alignment size overflow when allocating VM rangesAndreas Kling
Also add some sanity check assertions that we're generating and returning ranges contained within the RangeAllocator's total range. Fixes #5162.
2021-01-28Kernel: Remove outdated debug logging from RangeAllocatorAndreas Kling
If someone wants to debug this code, it's better that they rewrite the logging code to take randomization and guard pages into account.
2021-01-28Kernel+LibC: Add MAP_RANDOMIZED flag for sys$mmap()Andreas Kling
This can be used to request random VM placement instead of the highly predictable regular mmap(nullptr, ...) VM allocation strategy. It will soon be used to implement ASLR in the dynamic loader. :^)
2021-01-28Kernel: Add sanity check assertion in RangeAllocator::allocate_specificAndreas Kling
The specific virtual address should always be page aligned.
2021-01-28Kernel: Add sanity check assertion in RangeAllocator::allocate_anywhereAndreas Kling
The requested alignment should always be a multiple of the page size.
2021-01-27Kernel: Remove Range "valid" state and use Optional<Range> insteadAndreas Kling
It's easier to understand VM ranges if they are always valid. We can simply use an empty Optional<Range> to encode absence when needed.
2021-01-27Kernel: Assert in RangeAllocator that sizes are multiple of PAGE_SIZEAndreas Kling
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: Debug macros instead of constexpr.asynts
This was done with the following script: find . \( -name '*.cpp' -o -name '*.h' -o -name '*.in' \) -not -path './Toolchain/*' -not -path './Build/*' -exec sed -i -E 's/dbgln<debug_([a-z_]+)>/dbgln<\U\1_DEBUG>/' {} \; find . \( -name '*.cpp' -o -name '*.h' -o -name '*.in' \) -not -path './Toolchain/*' -not -path './Build/*' -exec sed -i -E 's/if constexpr \(debug_([a-z0-9_]+)/if constexpr \(\U\1_DEBUG/' {} \;
2021-01-25Everywhere: Use CMake to generate AK/Debug.h.asynts
This was done with the help of several scripts, I dump them here to easily find them later: awk '/#ifdef/ { print "#cmakedefine01 "$2 }' AK/Debug.h.in for debug_macro in $(awk '/#ifdef/ { print $2 }' AK/Debug.h.in) do find . \( -name '*.cpp' -o -name '*.h' -o -name '*.in' \) -not -path './Toolchain/*' -not -path './Build/*' -exec sed -i -E 's/#ifdef '$debug_macro'/#if '$debug_macro'/' {} \; done # Remember to remove WRAPPER_GERNERATOR_DEBUG from the list. awk '/#cmake/ { print "set("$2" ON)" }' AK/Debug.h.in
2021-01-22Everywhere: 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.
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-09Everywhere: 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: The modifications in this commit were automatically made using the following command: find . -name '*.cpp' -exec sed -i -E 's/dbg\(\) << ("[^"{]*");/dbgln\(\1\);/' {} \;
2020-12-30AK: Make binary_search signature more generic.asynts
2020-11-11Kernel: Add locks around RangeAllocatorTom
We need to keep multiple processors from changing it at the same time.
2020-08-30Kernel: Unbreak building with extra debug macros, part 2Ben Wiederhake
2020-08-02AK: Fix overflow and mixed-signedness issues in binary_search() (#2961)Muhammad Zahalqa
2020-07-26Refactor: Change the AK::binary_search signature to use AK::Span.asynts
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-27RangeAllocator: Use dbg() instead of dbgprintf()Liav A
2020-02-25AK: Make Vector use size_t for its size and capacityAndreas Kling
2020-02-19Kernel: Refuse to allocate 0 bytes of virtual address spaceAndreas Kling
2020-02-16Kernel+LibC: Allow sys$mmap() callers to specify address alignmentAndreas Kling
This is exposed via the non-standard serenity_mmap() call in userspace.
2020-02-16Kernel: Move all code into the Kernel namespaceAndreas Kling
2020-02-10Kernel: Remove more <LibBareMetal/Output/kstdio.h> includesAndreas Kling
2020-02-09Kernel: Apply changes to use LibBareMetal definitionsLiav A
2020-01-30Kernel: Add some sanity assertions in RangeAllocator::deallocate()Andreas Kling
We should never end up deallocating an empty range, or a range that ends before it begins.
2020-01-19Kernel: Oops, fix bad sort order of available VM rangesAndreas Kling
This made the allocator perform worse, so here's another second off of the Kernel/Process.cpp compile time from a simple bugfix! (31s to 30s)
2020-01-19Kernel: Optimize VM range deallocation a bitAndreas Kling
Previously, when deallocating a range of VM, we would sort and merge the range list. This was quite slow for large processes. This patch optimizes VM deallocation in the following ways: - Use binary search instead of linear scan to find the place to insert the deallocated range. - Insert at the right place immediately, removing the need to sort. - Merge the inserted range with any adjacent range(s) in-line instead of doing a separate merge pass into a list copy. - Add Traits<Range> to inform Vector that Range objects are trivial and can be moved using memmove(). I've also added an assertion that deallocated ranges are actually part of the RangeAllocator's initial address range. I've benchmarked this using g++ to compile Kernel/Process.cpp. With these changes, compilation goes from ~41 sec to ~35 sec.
2020-01-18Meta: Add license header to source filesAndreas Kling
As suggested by Joshua, this commit adds the 2-clause BSD license as a comment block to the top of every source file. For the first pass, I've just added myself for simplicity. I encourage everyone to add themselves as copyright holders of any file they've added or modified in some significant way. If I've added myself in error somewhere, feel free to replace it with the appropriate copyright holder instead. Going forward, all new source files should include a license header.
2020-01-17Kernel: Add a random offset to the base of the per-process VM allocatorAndreas Kling
This is not ASLR, but it does de-trivialize exploiting the ELF loader which would previously always parse executables at 0x01001000 in every single exec(). I've taken advantage of this multiple times in my own toy exploits and it's starting to feel cheesy. :^)
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-16 21:53:18 +0000