jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2022, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/Format.h>
8#include <Kernel/Memory/AnonymousVMObject.h>
9#include <Kernel/Memory/MemoryManager.h>
10#include <Kernel/Memory/RegionTree.h>
11#include <Kernel/Random.h>
12
13namespace Kernel::Memory {
14
15RegionTree::~RegionTree()
16{
17 delete_all_regions_assuming_they_are_unmapped();
18}
19
20void RegionTree::delete_all_regions_assuming_they_are_unmapped()
21{
22 // FIXME: This could definitely be done in a more efficient manner.
23 while (!m_regions.is_empty()) {
24 auto& region = *m_regions.begin();
25 m_regions.remove(region.vaddr().get());
26 delete ®ion;
27 }
28}
29
30ErrorOr<VirtualRange> RegionTree::allocate_range_anywhere(size_t size, size_t alignment)
31{
32 if (!size)
33 return EINVAL;
34
35 VERIFY((size % PAGE_SIZE) == 0);
36 VERIFY((alignment % PAGE_SIZE) == 0);
37
38 if (Checked<size_t>::addition_would_overflow(size, alignment))
39 return EOVERFLOW;
40
41 VirtualAddress window_start = m_total_range.base();
42
43 auto allocate_from_window = [&](VirtualRange const& window) -> Optional<VirtualRange> {
44 // FIXME: This check is probably excluding some valid candidates when using a large alignment.
45 if (window.size() < (size + alignment))
46 return {};
47
48 FlatPtr initial_base = window.base().get();
49 FlatPtr aligned_base = round_up_to_power_of_two(initial_base, alignment);
50
51 VERIFY(size);
52
53 return VirtualRange { VirtualAddress(aligned_base), size };
54 };
55
56 for (auto it = m_regions.begin(); !it.is_end(); ++it) {
57 auto& region = *it;
58
59 if (window_start == region.vaddr()) {
60 window_start = region.range().end();
61 continue;
62 }
63
64 VirtualRange window { window_start, region.vaddr().get() - window_start.get() };
65 window_start = region.range().end();
66
67 if (auto maybe_range = allocate_from_window(window); maybe_range.has_value())
68 return maybe_range.release_value();
69 }
70
71 VirtualRange window { window_start, m_total_range.end().get() - window_start.get() };
72 if (m_total_range.contains(window)) {
73 if (auto maybe_range = allocate_from_window(window); maybe_range.has_value())
74 return maybe_range.release_value();
75 }
76
77 dmesgln("RegionTree: Failed to allocate anywhere: size={}, alignment={}", size, alignment);
78 return ENOMEM;
79}
80
81ErrorOr<VirtualRange> RegionTree::allocate_range_specific(VirtualAddress base, size_t size)
82{
83 if (!size)
84 return EINVAL;
85
86 VERIFY(base.is_page_aligned());
87 VERIFY((size % PAGE_SIZE) == 0);
88
89 VirtualRange const range { base, size };
90 if (!m_total_range.contains(range))
91 return ENOMEM;
92
93 auto* region = m_regions.find_largest_not_above(base.offset(size - 1).get());
94 if (!region) {
95 // The range can be accommodated below the current lowest range.
96 return range;
97 }
98
99 if (region->range().intersects(range)) {
100 // Requested range overlaps an existing range.
101 return ENOMEM;
102 }
103
104 // Requested range fits between first region and its next neighbor.
105 return range;
106}
107
108ErrorOr<VirtualRange> RegionTree::allocate_range_randomized(size_t size, size_t alignment)
109{
110 if (!size)
111 return EINVAL;
112
113 VERIFY((size % PAGE_SIZE) == 0);
114 VERIFY((alignment % PAGE_SIZE) == 0);
115
116 // FIXME: I'm sure there's a smarter way to do this.
117 constexpr size_t maximum_randomization_attempts = 1000;
118 for (size_t i = 0; i < maximum_randomization_attempts; ++i) {
119 VirtualAddress random_address { round_up_to_power_of_two(get_fast_random<FlatPtr>() % m_total_range.end().get(), alignment) };
120
121 if (!m_total_range.contains(random_address, size))
122 continue;
123
124 auto range_or_error = allocate_range_specific(random_address, size);
125 if (!range_or_error.is_error())
126 return range_or_error.release_value();
127 }
128
129 return allocate_range_anywhere(size, alignment);
130}
131
132ErrorOr<void> RegionTree::place_anywhere(Region& region, RandomizeVirtualAddress randomize_virtual_address, size_t size, size_t alignment)
133{
134 auto range = TRY(randomize_virtual_address == RandomizeVirtualAddress::Yes ? allocate_range_randomized(size, alignment) : allocate_range_anywhere(size, alignment));
135 region.m_range = range;
136 m_regions.insert(region.vaddr().get(), region);
137 return {};
138}
139
140ErrorOr<void> RegionTree::place_specifically(Region& region, VirtualRange const& range)
141{
142 auto allocated_range = TRY(allocate_range_specific(range.base(), range.size()));
143 region.m_range = allocated_range;
144 m_regions.insert(region.vaddr().get(), region);
145 return {};
146}
147
148bool RegionTree::remove(Region& region)
149{
150 return m_regions.remove(region.range().base().get());
151}
152
153Region* RegionTree::find_region_containing(VirtualAddress address)
154{
155 auto* region = m_regions.find_largest_not_above(address.get());
156 if (!region || !region->contains(address))
157 return nullptr;
158 return region;
159}
160
161Region* RegionTree::find_region_containing(VirtualRange range)
162{
163 auto* region = m_regions.find_largest_not_above(range.base().get());
164 if (!region || !region->contains(range))
165 return nullptr;
166 return region;
167}
168
169}