coalescing_free_list.hpp
1 /*
2  * Copyright (c) 2019-2021, NVIDIA CORPORATION.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <iterator>
20 #include <rmm/detail/error.hpp>
21 #include <rmm/mr/device/detail/free_list.hpp>
22 
23 #include <algorithm>
24 #include <cassert>
25 #include <cstddef>
26 #include <iostream>
27 #include <list>
28 
29 namespace rmm::mr::detail {
30 
36 struct block : public block_base {
37  block() = default;
38  block(char* ptr, std::size_t size, bool is_head)
39  : block_base{ptr}, size_bytes{size}, head{is_head}
40  {
41  }
42 
48  [[nodiscard]] inline char* pointer() const { return static_cast<char*>(ptr); }
49 
55  [[nodiscard]] inline std::size_t size() const { return size_bytes; }
56 
64  [[nodiscard]] inline bool is_head() const { return head; }
65 
75  inline bool operator<(block const& rhs) const noexcept { return pointer() < rhs.pointer(); };
76 
86  [[nodiscard]] inline block merge(block const& blk) const noexcept
87  {
88  assert(is_contiguous_before(blk));
89  return {pointer(), size() + blk.size(), is_head()};
90  }
91 
99  [[nodiscard]] inline bool is_contiguous_before(block const& blk) const noexcept
100  {
101  // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
102  return (pointer() + size() == blk.ptr) and not(blk.is_head());
103  }
104 
111  [[nodiscard]] inline bool fits(std::size_t bytes) const noexcept { return size() >= bytes; }
112 
121  [[nodiscard]] inline bool is_better_fit(std::size_t bytes, block const& blk) const noexcept
122  {
123  return fits(bytes) && (size() < blk.size() || blk.size() < bytes);
124  }
125 
126 #ifdef RMM_DEBUG_PRINT
127 
130  inline void print() const
131  {
132  std::cout << fmt::format("{} {} B", fmt::ptr(pointer()), size()) << std::endl;
133  }
134 #endif
135 
136  private:
137  std::size_t size_bytes{};
138  bool head{};
139 };
140 
141 #ifdef RMM_DEBUG_PRINT
142 inline std::ostream& operator<<(std::ostream& out, const block& blk)
144 {
145  out << fmt::format("{} {} B\n", fmt::ptr(blk.pointer()), blk.size());
146  return out;
147 }
148 #endif
149 
157 template <typename block_type>
159  // is_transparent (C++14 feature) allows search key type for set<block_type>::find()
160  using is_transparent = void;
161 
162  bool operator()(block_type const& lhs, block_type const& rhs) const { return lhs < rhs; }
163  bool operator()(char const* ptr, block_type const& rhs) const { return ptr < rhs.pointer(); }
164  bool operator()(block_type const& lhs, char const* ptr) const { return lhs.pointer() < ptr; };
165 };
166 
173  coalescing_free_list() = default;
174  ~coalescing_free_list() override = default;
175 
177  coalescing_free_list& operator=(coalescing_free_list const&) = delete;
179  coalescing_free_list& operator=(coalescing_free_list&&) = delete;
180 
187  void insert(block_type const& block)
188  {
189  if (is_empty()) {
191  return;
192  }
193 
194  // Find the right place (in ascending ptr order) to insert the block
195  // Can't use binary_search because it's a linked list and will be quadratic
196  auto const next =
197  std::find_if(begin(), end(), [block](block_type const& blk) { return block < blk; });
198  auto const previous = (next == cbegin()) ? next : std::prev(next);
199 
200  // Coalesce with neighboring blocks or insert the new block if it can't be coalesced
201  bool const merge_prev = previous->is_contiguous_before(block);
202  bool const merge_next = (next != cend()) && block.is_contiguous_before(*next);
203 
204  if (merge_prev && merge_next) {
205  *previous = previous->merge(block).merge(*next);
206  erase(next);
207  } else if (merge_prev) {
208  *previous = previous->merge(block);
209  } else if (merge_next) {
210  *next = block.merge(*next);
211  } else {
212  free_list::insert(next, block); // cannot be coalesced, just insert
213  }
214  }
215 
223  void insert(free_list&& other)
224  {
225  using std::make_move_iterator;
226  auto inserter = [this](block_type&& block) { this->insert(block); };
227  std::for_each(make_move_iterator(other.begin()), make_move_iterator(other.end()), inserter);
228  }
229 
238  block_type get_block(std::size_t size)
239  {
240  // find best fit block
241  auto finder = [size](block_type const& lhs, block_type const& rhs) {
242  return lhs.is_better_fit(size, rhs);
243  };
244  auto const iter = std::min_element(cbegin(), cend(), finder);
245 
246  if (iter != cend() && iter->fits(size)) {
247  // Remove the block from the free_list and return it.
248  block_type const found = *iter;
249  erase(iter);
250  return found;
251  }
252 
253  return block_type{}; // not found
254  }
255 
256 #ifdef RMM_DEBUG_PRINT
257 
260  void print() const
261  {
262  std::cout << size() << '\n';
263  std::for_each(cbegin(), cend(), [](auto const iter) { iter.print(); });
264  }
265 #endif
266 }; // coalescing_free_list
267 
268 } // namespace rmm::mr::detail
rmm::mr::detail::free_list< block >::cend
const_iterator cend() const noexcept
beginning of the free list
Definition: free_list.hpp:93
rmm::mr::detail::free_list< block >::cbegin
const_iterator cbegin() const noexcept
beginning of the free list
Definition: free_list.hpp:86
rmm::mr::detail::coalescing_free_list
An ordered list of free memory blocks that coalesces contiguous blocks on insertion.
Definition: coalescing_free_list.hpp:172
rmm::mr::detail::block::is_contiguous_before
bool is_contiguous_before(block const &blk) const noexcept
Verifies whether this block can be merged to the beginning of block b.
Definition: coalescing_free_list.hpp:99
rmm::mr::detail::free_list< block >::begin
iterator begin() noexcept
beginning of the free list
Definition: free_list.hpp:82
rmm::mr::detail::free_list< block >::erase
void erase(const_iterator iter)
Removes the block indicated by iter from the free list.
Definition: free_list.hpp:115
rmm::mr::detail::free_list
Base class defining an interface for a list of free memory blocks.
Definition: free_list.hpp:65
rmm::mr::detail::free_list< block >::size
size_type size() const noexcept
The size of the free list in blocks.
Definition: free_list.hpp:100
rmm::mr::detail::block
A simple block structure specifying the size and location of a block of memory, with a flag indicatin...
Definition: coalescing_free_list.hpp:36
rmm::mr::detail::free_list< block >::end
iterator end() noexcept
end of the free list
Definition: free_list.hpp:89
rmm::mr::detail::block::is_head
bool is_head() const
Returns whether this block is the start of an allocation from an upstream allocator.
Definition: coalescing_free_list.hpp:64
rmm::mr::detail::compare_blocks
Comparator for block types based on pointer address.
Definition: coalescing_free_list.hpp:158
rmm::mr::detail::coalescing_free_list::insert
void insert(block_type const &block)
Inserts a block into the free_list in the correct order, coalescing it with the preceding and followi...
Definition: coalescing_free_list.hpp:187
rmm::mr::detail::coalescing_free_list::insert
void insert(free_list &&other)
Moves blocks from free_list other into this free_list in their correct order, coalescing them with th...
Definition: coalescing_free_list.hpp:223
rmm::mr::detail::block_base::ptr
void * ptr
Raw memory pointer.
Definition: free_list.hpp:26
rmm::mr::detail::free_list< block >::is_empty
bool is_empty() const noexcept
checks whether the free_list is empty.
Definition: free_list.hpp:108
rmm::mr::detail::block::size
std::size_t size() const
Returns the size of the memory represented by this block.
Definition: coalescing_free_list.hpp:55
rmm::mr::detail::block::pointer
char * pointer() const
Returns the pointer to the memory represented by this block.
Definition: coalescing_free_list.hpp:48
rmm::mr::detail::free_list::insert
void insert(const_iterator pos, block_type const &block)
Insert a block in the free list before the specified position.
Definition: free_list.hpp:143
rmm::mr::detail::block::operator<
bool operator<(block const &rhs) const noexcept
Comparison operator to enable comparing blocks and storing in ordered containers.
Definition: coalescing_free_list.hpp:75
rmm::mr::detail::block::merge
block merge(block const &blk) const noexcept
Coalesce two contiguous blocks into one.
Definition: coalescing_free_list.hpp:86
rmm::mr::detail::block_base
Definition: free_list.hpp:25
rmm::mr::detail::coalescing_free_list::get_block
block_type get_block(std::size_t size)
Finds the smallest block in the free_list large enough to fit size bytes.
Definition: coalescing_free_list.hpp:238
rmm::mr::detail::block::fits
bool fits(std::size_t bytes) const noexcept
Is this block large enough to fit sz bytes?
Definition: coalescing_free_list.hpp:111
rmm::mr::detail::block::is_better_fit
bool is_better_fit(std::size_t bytes, block const &blk) const noexcept
Is this block a better fit for sz bytes than block b?
Definition: coalescing_free_list.hpp:121