jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2021, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include "RangeAllocator.h"
8#include <AK/BinarySearch.h>
9#include <AK/Checked.h>
10#include <AK/Random.h>
11
12#define VM_GUARD_PAGES
13#define PAGE_MASK ((FlatPtr)0xfffff000u)
14
15namespace UserspaceEmulator {
16
17RangeAllocator::RangeAllocator()
18 : m_total_range({}, 0)
19{
20}
21
22void RangeAllocator::initialize_with_range(VirtualAddress base, size_t size)
23{
24 m_total_range = { base, size };
25 m_available_ranges.append({ base, size });
26}
27
28void RangeAllocator::dump() const
29{
30 dbgln("RangeAllocator({})", this);
31 for (auto const& range : m_available_ranges) {
32 dbgln(" {:x} -> {:x}", range.base().get(), range.end().get() - 1);
33 }
34}
35
36void RangeAllocator::carve_at_index(int index, Range const& range)
37{
38 auto remaining_parts = m_available_ranges[index].carve(range);
39 VERIFY(remaining_parts.size() >= 1);
40 VERIFY(m_total_range.contains(remaining_parts[0]));
41 m_available_ranges[index] = remaining_parts[0];
42 if (remaining_parts.size() == 2) {
43 VERIFY(m_total_range.contains(remaining_parts[1]));
44 m_available_ranges.insert(index + 1, move(remaining_parts[1]));
45 }
46}
47
48Optional<Range> RangeAllocator::allocate_randomized(size_t size, size_t alignment)
49{
50 if (!size)
51 return {};
52
53 VERIFY((size % PAGE_SIZE) == 0);
54 VERIFY((alignment % PAGE_SIZE) == 0);
55
56 // FIXME: I'm sure there's a smarter way to do this.
57 static constexpr size_t maximum_randomization_attempts = 1000;
58 for (size_t i = 0; i < maximum_randomization_attempts; ++i) {
59 VirtualAddress random_address { round_up_to_power_of_two(get_random<FlatPtr>(), alignment) };
60
61 if (!m_total_range.contains(random_address, size))
62 continue;
63
64 auto range = allocate_specific(random_address, size);
65 if (range.has_value())
66 return range;
67 }
68
69 return allocate_anywhere(size, alignment);
70}
71
72Optional<Range> RangeAllocator::allocate_anywhere(size_t size, size_t alignment)
73{
74 if (!size)
75 return {};
76
77 VERIFY((size % PAGE_SIZE) == 0);
78 VERIFY((alignment % PAGE_SIZE) == 0);
79
80#ifdef VM_GUARD_PAGES
81 // NOTE: We pad VM allocations with a guard page on each side.
82 if (Checked<size_t>::addition_would_overflow(size, PAGE_SIZE * 2))
83 return {};
84
85 size_t effective_size = size + PAGE_SIZE * 2;
86 size_t offset_from_effective_base = PAGE_SIZE;
87#else
88 size_t effective_size = size;
89 size_t offset_from_effective_base = 0;
90#endif
91
92 if (Checked<size_t>::addition_would_overflow(effective_size, alignment))
93 return {};
94
95 for (size_t i = 0; i < m_available_ranges.size(); ++i) {
96 auto& available_range = m_available_ranges[i];
97 // FIXME: This check is probably excluding some valid candidates when using a large alignment.
98 if (available_range.size() < (effective_size + alignment))
99 continue;
100
101 FlatPtr initial_base = available_range.base().offset(offset_from_effective_base).get();
102 FlatPtr aligned_base = round_up_to_power_of_two(initial_base, alignment);
103
104 Range allocated_range(VirtualAddress(aligned_base), size);
105 VERIFY(m_total_range.contains(allocated_range));
106
107 if (available_range == allocated_range) {
108 m_available_ranges.remove(i);
109 return allocated_range;
110 }
111 carve_at_index(i, allocated_range);
112 return allocated_range;
113 }
114 dbgln("RangeAllocator: Failed to allocate anywhere: size={}, alignment={}", size, alignment);
115 return {};
116}
117
118Optional<Range> RangeAllocator::allocate_specific(VirtualAddress base, size_t size)
119{
120 if (!size)
121 return {};
122
123 VERIFY(base.is_page_aligned());
124 VERIFY((size % PAGE_SIZE) == 0);
125
126 Range allocated_range(base, size);
127 if (!m_total_range.contains(allocated_range)) {
128 dbgln("Unallocatable mmap request?! {:p}+{:p}", base.get(), size);
129 return {};
130 }
131 for (size_t i = 0; i < m_available_ranges.size(); ++i) {
132 auto& available_range = m_available_ranges[i];
133 if (!available_range.contains(base, size))
134 continue;
135 if (available_range == allocated_range) {
136 m_available_ranges.remove(i);
137 return allocated_range;
138 }
139 carve_at_index(i, allocated_range);
140 return allocated_range;
141 }
142 return {};
143}
144
145void RangeAllocator::deallocate(Range const& range)
146{
147 VERIFY(m_total_range.contains(range));
148 VERIFY(range.size());
149 VERIFY((range.size() % PAGE_SIZE) == 0);
150 VERIFY(range.base() < range.end());
151 VERIFY(!m_available_ranges.is_empty());
152
153 size_t nearby_index = 0;
154 auto* existing_range = binary_search(
155 m_available_ranges.span(),
156 range,
157 &nearby_index,
158 [](auto& a, auto& b) { return a.base().get() - b.end().get(); });
159
160 size_t inserted_index = 0;
161 if (existing_range) {
162 existing_range->m_size += range.size();
163 inserted_index = nearby_index;
164 } else {
165 m_available_ranges.insert_before_matching(
166 Range(range), [&](auto& entry) {
167 return entry.base() >= range.end();
168 },
169 nearby_index, &inserted_index);
170 }
171
172 if (inserted_index < (m_available_ranges.size() - 1)) {
173 // We already merged with previous. Try to merge with next.
174 auto& inserted_range = m_available_ranges[inserted_index];
175 auto& next_range = m_available_ranges[inserted_index + 1];
176 if (inserted_range.end() == next_range.base()) {
177 inserted_range.m_size += next_range.size();
178 m_available_ranges.remove(inserted_index + 1);
179 return;
180 }
181 }
182}
183
184void RangeAllocator::reserve_user_range(VirtualAddress begin, size_t size)
185{
186 auto end = round_up_to_power_of_two(begin.offset(size).get(), PAGE_SIZE);
187 auto allocated_range = allocate_specific(begin.page_base(), end - begin.page_base().get());
188 VERIFY(allocated_range.has_value());
189}
190
191}