RangeAllocator.cpp 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
  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. #include <AK/BinarySearch.h>
  27. #include <AK/QuickSort.h>
  28. #include <Kernel/Random.h>
  29. #include <Kernel/Thread.h>
  30. #include <Kernel/VM/RangeAllocator.h>
  31. //#define VRA_DEBUG
  32. #define VM_GUARD_PAGES
  33. namespace Kernel {
  34. RangeAllocator::RangeAllocator()
  35. {
  36. }
  37. void RangeAllocator::initialize_with_range(VirtualAddress base, size_t size)
  38. {
  39. m_total_range = { base, size };
  40. m_available_ranges.append({ base, size });
  41. #ifdef VRA_DEBUG
  42. dump();
  43. #endif
  44. }
  45. void RangeAllocator::initialize_from_parent(const RangeAllocator& parent_allocator)
  46. {
  47. m_total_range = parent_allocator.m_total_range;
  48. m_available_ranges = parent_allocator.m_available_ranges;
  49. }
  50. RangeAllocator::~RangeAllocator()
  51. {
  52. }
  53. void RangeAllocator::dump() const
  54. {
  55. dbg() << "RangeAllocator{" << this << "}";
  56. for (auto& range : m_available_ranges) {
  57. dbg() << " " << String::format("%x", range.base().get()) << " -> " << String::format("%x", range.end().get() - 1);
  58. }
  59. }
  60. Vector<Range, 2> Range::carve(const Range& taken)
  61. {
  62. Vector<Range, 2> parts;
  63. if (taken == *this)
  64. return {};
  65. if (taken.base() > base())
  66. parts.append({ base(), taken.base().get() - base().get() });
  67. if (taken.end() < end())
  68. parts.append({ taken.end(), end().get() - taken.end().get() });
  69. #ifdef VRA_DEBUG
  70. 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);
  71. for (int i = 0; i < parts.size(); ++i)
  72. dbg() << " " << String::format("%x", parts[i].base().get()) << "-" << String::format("%x", parts[i].end().get() - 1);
  73. #endif
  74. return parts;
  75. }
  76. void RangeAllocator::carve_at_index(int index, const Range& range)
  77. {
  78. auto remaining_parts = m_available_ranges[index].carve(range);
  79. ASSERT(remaining_parts.size() >= 1);
  80. m_available_ranges[index] = remaining_parts[0];
  81. if (remaining_parts.size() == 2)
  82. m_available_ranges.insert(index + 1, move(remaining_parts[1]));
  83. }
  84. Range RangeAllocator::allocate_anywhere(size_t size, size_t alignment)
  85. {
  86. if (!size)
  87. return {};
  88. #ifdef VM_GUARD_PAGES
  89. // NOTE: We pad VM allocations with a guard page on each side.
  90. size_t effective_size = size + PAGE_SIZE * 2;
  91. size_t offset_from_effective_base = PAGE_SIZE;
  92. #else
  93. size_t effective_size = size;
  94. size_t offset_from_effective_base = 0;
  95. #endif
  96. for (size_t i = 0; i < m_available_ranges.size(); ++i) {
  97. auto& available_range = m_available_ranges[i];
  98. // FIXME: This check is probably excluding some valid candidates when using a large alignment.
  99. if (available_range.size() < (effective_size + alignment))
  100. continue;
  101. uintptr_t initial_base = available_range.base().offset(offset_from_effective_base).get();
  102. uintptr_t aligned_base = round_up_to_power_of_two(initial_base, alignment);
  103. Range allocated_range(VirtualAddress(aligned_base), size);
  104. if (available_range == allocated_range) {
  105. #ifdef VRA_DEBUG
  106. dbg() << "VRA: Allocated perfect-fit anywhere(" << String::format("%zu", size) << ", " << String::format("%zu", alignment) << "): " << String::format("%x", allocated_range.base().get());
  107. #endif
  108. m_available_ranges.remove(i);
  109. return allocated_range;
  110. }
  111. carve_at_index(i, allocated_range);
  112. #ifdef VRA_DEBUG
  113. dbg() << "VRA: Allocated anywhere(" << String::format("%zu", size) << ", " << String::format("%zu", alignment) << "): " << String::format("%x", allocated_range.base().get());
  114. dump();
  115. #endif
  116. return allocated_range;
  117. }
  118. klog() << "VRA: Failed to allocate anywhere: " << size << ", " << alignment;
  119. return {};
  120. }
  121. Range RangeAllocator::allocate_specific(VirtualAddress base, size_t size)
  122. {
  123. if (!size)
  124. return {};
  125. Range allocated_range(base, size);
  126. for (size_t i = 0; i < m_available_ranges.size(); ++i) {
  127. auto& available_range = m_available_ranges[i];
  128. if (!available_range.contains(base, size))
  129. continue;
  130. if (available_range == allocated_range) {
  131. m_available_ranges.remove(i);
  132. return allocated_range;
  133. }
  134. carve_at_index(i, allocated_range);
  135. #ifdef VRA_DEBUG
  136. dbg() << "VRA: Allocated specific(" << size << "): " << String::format("%x", available_range.base().get());
  137. dump();
  138. #endif
  139. return allocated_range;
  140. }
  141. dbg() << "VRA: Failed to allocate specific range: " << base << "(" << size << ")";
  142. return {};
  143. }
  144. void RangeAllocator::deallocate(Range range)
  145. {
  146. ASSERT(m_total_range.contains(range));
  147. ASSERT(range.size());
  148. ASSERT(range.base() < range.end());
  149. #ifdef VRA_DEBUG
  150. dbg() << "VRA: Deallocate: " << String::format("%x", range.base().get()) << "(" << range.size() << ")";
  151. dump();
  152. #endif
  153. ASSERT(!m_available_ranges.is_empty());
  154. int nearby_index = 0;
  155. auto* existing_range = binary_search(
  156. m_available_ranges.data(), m_available_ranges.size(), range, [](auto& a, auto& b) {
  157. return a.base().get() - b.end().get();
  158. },
  159. &nearby_index);
  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. if (inserted_index < (m_available_ranges.size() - 1)) {
  172. // We already merged with previous. Try to merge with next.
  173. auto& inserted_range = m_available_ranges[inserted_index];
  174. auto& next_range = m_available_ranges[inserted_index + 1];
  175. if (inserted_range.end() == next_range.base()) {
  176. inserted_range.m_size += next_range.size();
  177. m_available_ranges.remove(inserted_index + 1);
  178. return;
  179. }
  180. }
  181. #ifdef VRA_DEBUG
  182. dbg() << "VRA: After deallocate";
  183. dump();
  184. #endif
  185. }
  186. }