jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
22 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
23 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <AK/BinarySearch.h>
28#include <AK/QuickSort.h>
29#include <Kernel/Random.h>
30#include <Kernel/Thread.h>
31#include <Kernel/VM/RangeAllocator.h>
32
33//#define VRA_DEBUG
34#define VM_GUARD_PAGES
35
36namespace Kernel {
37
38RangeAllocator::RangeAllocator()
39{
40}
41
42void RangeAllocator::initialize_with_range(VirtualAddress base, size_t size)
43{
44 m_total_range = { base, size };
45 m_available_ranges.append({ base, size });
46#ifdef VRA_DEBUG
47 dump();
48#endif
49}
50
51void RangeAllocator::initialize_from_parent(const RangeAllocator& parent_allocator)
52{
53 m_total_range = parent_allocator.m_total_range;
54 m_available_ranges = parent_allocator.m_available_ranges;
55}
56
57RangeAllocator::~RangeAllocator()
58{
59}
60
61void RangeAllocator::dump() const
62{
63 dbg() << "RangeAllocator{" << this << "}";
64 for (auto& range : m_available_ranges) {
65 dbg() << " " << String::format("%x", range.base().get()) << " -> " << String::format("%x", range.end().get() - 1);
66 }
67}
68
69Vector<Range, 2> Range::carve(const Range& taken)
70{
71 Vector<Range, 2> parts;
72 if (taken == *this)
73 return {};
74 if (taken.base() > base())
75 parts.append({ base(), taken.base().get() - base().get() });
76 if (taken.end() < end())
77 parts.append({ taken.end(), end().get() - taken.end().get() });
78#ifdef VRA_DEBUG
79 dbg() << "VRA: carve: take " << String::format("%x", taken.base().get()) << "-" << String::format("%x", taken.end().get() - 1) << " from " << String::format("%x", base().get()) << "-" << String::format("%x", end().get() - 1);
80 for (int i = 0; i < parts.size(); ++i)
81 dbg() << " " << String::format("%x", parts[i].base().get()) << "-" << String::format("%x", parts[i].end().get() - 1);
82#endif
83 return parts;
84}
85
86void RangeAllocator::carve_at_index(int index, const Range& range)
87{
88 auto remaining_parts = m_available_ranges[index].carve(range);
89 ASSERT(remaining_parts.size() >= 1);
90 m_available_ranges[index] = remaining_parts[0];
91 if (remaining_parts.size() == 2)
92 m_available_ranges.insert(index + 1, move(remaining_parts[1]));
93}
94
95Range RangeAllocator::allocate_anywhere(size_t size, size_t alignment)
96{
97 if (!size)
98 return {};
99
100#ifdef VM_GUARD_PAGES
101 // NOTE: We pad VM allocations with a guard page on each side.
102 size_t effective_size = size + PAGE_SIZE * 2;
103 size_t offset_from_effective_base = PAGE_SIZE;
104#else
105 size_t effective_size = size;
106 size_t offset_from_effective_base = 0;
107#endif
108
109 for (size_t i = 0; i < m_available_ranges.size(); ++i) {
110 auto& available_range = m_available_ranges[i];
111 // FIXME: This check is probably excluding some valid candidates when using a large alignment.
112 if (available_range.size() < (effective_size + alignment))
113 continue;
114
115 FlatPtr initial_base = available_range.base().offset(offset_from_effective_base).get();
116 FlatPtr aligned_base = round_up_to_power_of_two(initial_base, alignment);
117
118 Range allocated_range(VirtualAddress(aligned_base), size);
119 if (available_range == allocated_range) {
120#ifdef VRA_DEBUG
121 dbg() << "VRA: Allocated perfect-fit anywhere(" << String::format("%zu", size) << ", " << String::format("%zu", alignment) << "): " << String::format("%x", allocated_range.base().get());
122#endif
123 m_available_ranges.remove(i);
124 return allocated_range;
125 }
126 carve_at_index(i, allocated_range);
127#ifdef VRA_DEBUG
128 dbg() << "VRA: Allocated anywhere(" << String::format("%zu", size) << ", " << String::format("%zu", alignment) << "): " << String::format("%x", allocated_range.base().get());
129 dump();
130#endif
131 return allocated_range;
132 }
133 klog() << "VRA: Failed to allocate anywhere: " << size << ", " << alignment;
134 return {};
135}
136
137Range RangeAllocator::allocate_specific(VirtualAddress base, size_t size)
138{
139 if (!size)
140 return {};
141
142 Range allocated_range(base, size);
143 for (size_t i = 0; i < m_available_ranges.size(); ++i) {
144 auto& available_range = m_available_ranges[i];
145 if (!available_range.contains(base, size))
146 continue;
147 if (available_range == allocated_range) {
148 m_available_ranges.remove(i);
149 return allocated_range;
150 }
151 carve_at_index(i, allocated_range);
152#ifdef VRA_DEBUG
153 dbg() << "VRA: Allocated specific(" << size << "): " << String::format("%x", available_range.base().get());
154 dump();
155#endif
156 return allocated_range;
157 }
158 dbg() << "VRA: Failed to allocate specific range: " << base << "(" << size << ")";
159 return {};
160}
161
162void RangeAllocator::deallocate(Range range)
163{
164 ASSERT(m_total_range.contains(range));
165 ASSERT(range.size());
166 ASSERT(range.base() < range.end());
167
168#ifdef VRA_DEBUG
169 dbg() << "VRA: Deallocate: " << String::format("%x", range.base().get()) << "(" << range.size() << ")";
170 dump();
171#endif
172
173 ASSERT(!m_available_ranges.is_empty());
174
175 int nearby_index = 0;
176 auto* existing_range = binary_search(
177 m_available_ranges.data(), m_available_ranges.size(), range, [](auto& a, auto& b) {
178 return a.base().get() - b.end().get();
179 },
180 &nearby_index);
181
182 size_t inserted_index = 0;
183 if (existing_range) {
184 existing_range->m_size += range.size();
185 inserted_index = nearby_index;
186 } else {
187 m_available_ranges.insert_before_matching(
188 Range(range), [&](auto& entry) {
189 return entry.base() >= range.end();
190 },
191 nearby_index, &inserted_index);
192 }
193
194 if (inserted_index < (m_available_ranges.size() - 1)) {
195 // We already merged with previous. Try to merge with next.
196 auto& inserted_range = m_available_ranges[inserted_index];
197 auto& next_range = m_available_ranges[inserted_index + 1];
198 if (inserted_range.end() == next_range.base()) {
199 inserted_range.m_size += next_range.size();
200 m_available_ranges.remove(inserted_index + 1);
201 return;
202 }
203 }
204#ifdef VRA_DEBUG
205 dbg() << "VRA: After deallocate";
206 dump();
207#endif
208}
209
210}