BioDynaMo  v1.05.0-137fdb15
memory_manager.cc
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------
2 //
3 // Copyright (C) 2021 CERN & University of Surrey for the benefit of the
4 // BioDynaMo collaboration. All Rights Reserved.
5 //
6 // Licensed under the Apache License, Version 2.0 (the "License");
7 // you may not use this file except in compliance with the License.
8 //
9 // See the LICENSE file distributed with this work for details.
10 // See the NOTICE file distributed with this work for additional information
11 // regarding copyright ownership.
12 //
13 // -----------------------------------------------------------------------------
14 
16 #include <unistd.h>
17 #include <algorithm>
18 #include <cmath>
19 #include <cstdlib>
20 #include <limits>
21 #include <mutex>
22 #include "core/util/log.h"
23 #include "core/util/string.h"
24 
25 namespace bdm {
26 namespace memory_manager_detail {
27 
28 List::List(uint64_t n) : n_(n) {}
29 
30 List::List(const List& other)
31  : head_(other.head_),
32  tail_(other.tail_),
33  skip_list_(other.skip_list_),
34  size_(other.size_),
35  nodes_before_skip_list_(other.nodes_before_skip_list_),
36  n_(other.n_) {}
37 
39  if (!Empty()) {
40  auto* ret = head_;
41  head_ = head_->next;
42  if (head_ != nullptr) {
43  __builtin_prefetch(head_->next);
44  }
45  if (tail_ == ret) {
46  tail_ = nullptr;
47  }
48  --size_;
49  if (skip_list_.back() == ret) {
50  skip_list_.pop_back();
52  } else if (size_ != 0) {
54  }
55  return ret;
56  }
57  return nullptr;
58 }
59 
60 void List::PushFront(Node* head) {
61  assert(head != nullptr);
62 
63  auto* old_head = head_;
64  head_ = head;
65  head_->next = old_head;
66  if (old_head == nullptr) {
67  tail_ = head_;
68  }
69  ++size_;
71 
72  if (nodes_before_skip_list_ >= n_ && size_ > n_) {
73  skip_list_.push_back(head_);
75  }
76 }
77 
79  std::lock_guard<Spinlock> guard(lock_);
80  PushFront(head);
81 }
82 
83 void List::PushBackN(Node* head, Node* tail) {
84  assert(head != nullptr);
85  assert(tail != nullptr);
86 
87  if (head_ == nullptr) {
88  head_ = head;
89  tail_ = tail;
90  size_ = n_;
92  return;
93  }
94 
95  skip_list_.push_front(tail_);
96  tail_->next = head;
97  tail_ = tail;
98  size_ += n_;
99 }
100 
101 void List::PushBackNThreadSafe(Node* head, Node* tail) {
102  std::lock_guard<Spinlock> guard(lock_);
103  PushBackN(head, tail);
104 }
105 
106 void List::PopBackN(Node** head, Node** tail) {
107  assert(head_ != nullptr);
108  assert(tail_ != nullptr);
109 
110  if (skip_list_.size() == 0) {
111  return;
112  }
113 
114  *head = skip_list_.front()->next;
115  skip_list_.front()->next = nullptr;
116  *tail = tail_;
117  tail_ = skip_list_.front();
118  skip_list_.pop_front();
119  size_ -= n_;
120 }
121 
122 void List::PopBackNThreadSafe(Node** head, Node** tail) {
123  std::lock_guard<Spinlock> guard(lock_);
124  PopBackN(head, tail);
125 }
126 
127 bool List::Empty() const { return head_ == nullptr; }
128 
129 bool List::CanPopBackN() const { return skip_list_.size() != 0; }
130 
131 uint64_t List::Size() const { return size_; }
132 
133 uint64_t List::GetN() const { return n_; }
134 
135 // -----------------------------------------------------------------------------
138 }
139 
140 void AllocatedBlock::GetNextPageBatch(uint64_t size_n_pages, char** start,
141  uint64_t* size) {
142  *start = initialized_until_;
143  initialized_until_ += size_n_pages;
144  *size = size_n_pages;
146  *size = end_pointer_ - *start;
147  }
148 }
149 
150 // -----------------------------------------------------------------------------
152  uint64_t size_n_pages, real_t growth_rate,
153  uint64_t max_mem_per_thread_factor)
154  : size_n_pages_(size_n_pages),
155  growth_rate_(growth_rate),
156  max_nodes_per_thread_((size_n_pages_ - kMetadataSize) / size *
157  max_mem_per_thread_factor),
158  num_elements_per_n_pages_((size_n_pages_ - kMetadataSize) / size),
159  size_(size),
160  nid_(nid),
161  tinfo_(ThreadInfo::GetInstance()),
162  central_(num_elements_per_n_pages_) {
163  free_lists_.reserve(tinfo_->GetMaxThreads());
164  for (int i = 0; i < tinfo_->GetMaxThreads(); ++i) {
166  }
167 }
168 
170  for (auto& block : memory_blocks_) {
171  uint64_t size = block.end_pointer_ - block.start_pointer_;
172  numa_free(block.start_pointer_, size);
173  }
174 }
175 
176 void* NumaPoolAllocator::New(int tid) {
177  assert(static_cast<uint64_t>(tid) < free_lists_.size());
178  auto& tl_list = free_lists_[tid];
179  if (!tl_list.Empty()) {
180  auto* ret = tl_list.PopFront();
181  assert(ret != nullptr);
182  return ret;
183  } else if (central_.CanPopBackN()) {
184  Node *head = nullptr, *tail = nullptr;
185  central_.PopBackNThreadSafe(&head, &tail);
186  if (head == nullptr) {
187  return New(tid);
188  }
189  tl_list.PushBackN(head, tail);
190  auto* ret = tl_list.PopFront();
191  assert(ret != nullptr);
192  return ret;
193  } else {
194  lock_.lock();
195  if (memory_blocks_.size() == 0 ||
196  memory_blocks_.back().IsFullyInitialized()) {
197  auto size =
198  std::max(total_size_ * (growth_rate_ - 1.0), size_n_pages_ * 2.0);
199  size = RoundUpTo(size, size_n_pages_);
200  AllocNewMemoryBlock(size);
201  }
202  char* start_pointer;
203  uint64_t size;
204  memory_blocks_.back().GetNextPageBatch(size_n_pages_, &start_pointer,
205  &size);
206  lock_.unlock();
207  // remaining memory not enough to store one element
208  if ((size - kMetadataSize) < size_) {
209  return New(tid);
210  }
211  InitializeNPages(&tl_list, start_pointer, size);
212  auto* ret = tl_list.PopFront();
213  assert(ret != nullptr);
214  return ret;
215  }
216 }
217 
219  auto* node = new (p) Node();
220  auto tid = tinfo_->GetMyThreadId();
221  auto& tl_list = free_lists_[tid];
222  tl_list.PushFront(node);
223  // migrate too much unused memory to the central list agent other threads
224  // can obtain it
225  while (tl_list.Size() > max_nodes_per_thread_ && tl_list.CanPopBackN()) {
226  Node* head = nullptr;
227  Node* tail = nullptr;
228  tl_list.PopBackN(&head, &tail);
229  central_.PushBackNThreadSafe(head, tail);
230  }
231 }
232 
233 uint64_t NumaPoolAllocator::GetSize() const { return size_; }
234 
236  // check if size is multiple of N pages aligned
237  assert((size & (size_n_pages_ - 1)) == 0 &&
238  "Size must be a multiple of MemoryManager::kSizeNPages");
239  void* block = numa_alloc_onnode(size, nid_);
240  if (block == nullptr) {
241  Log::Fatal("NumaPoolAllocator::AllocNewMemoryBlock", "Allocation failed");
242  }
243  total_size_ += size;
244  auto n_pages_aligned =
245  RoundUpTo(reinterpret_cast<uint64_t>(block), size_n_pages_);
246  auto* start = reinterpret_cast<char*>(block);
247  char* end = start + size;
248  memory_blocks_.push_back(
249  {start, end, reinterpret_cast<char*>(n_pages_aligned)});
250 }
251 
252 void NumaPoolAllocator::InitializeNPages(List* tl_list, char* block,
253  uint64_t mem_block_size) {
254  assert((reinterpret_cast<uint64_t>(block) & (size_n_pages_ - 1)) == 0 &&
255  "block is not N page aligned");
256  auto* block_npa = reinterpret_cast<NumaPoolAllocator**>(block);
257  *block_npa = this;
258 
259  auto* start_pointer = static_cast<char*>(block + kMetadataSize);
260  auto* pointer = start_pointer;
261  const uint64_t num_elements = (mem_block_size - kMetadataSize) / size_;
262 
263  if (tl_list->GetN() == num_elements) {
264  auto* head = new (pointer) Node();
265  assert(head->next == nullptr);
266  auto* tail = head;
267 
268  for (uint64_t i = 1; i < num_elements; ++i) {
269  assert(pointer >= static_cast<char*>(block));
270  assert(pointer <= start_pointer + mem_block_size - size_);
271  __builtin_prefetch(pointer + size_);
272  auto* node = new (pointer) Node();
273  tail->next = node;
274  tail = node;
275  pointer += size_;
276  }
277  tl_list->PushBackN(head, tail);
278  } else {
279  for (uint64_t i = 0; i < num_elements; ++i) {
280  assert(pointer >= static_cast<char*>(block));
281  assert(pointer <= start_pointer + mem_block_size - size_);
282  __builtin_prefetch(pointer + size_);
283  tl_list->PushFront(new (pointer) Node());
284  pointer += size_;
285  }
286  }
287 }
288 
289 uint64_t NumaPoolAllocator::RoundUpTo(uint64_t number, uint64_t multiple) {
290  assert((multiple & (multiple - 1)) == 0 && multiple &&
291  "multiple must be a power of two and non-zero");
292  return (number + multiple - 1) &
293  (std::numeric_limits<uint64_t>::max() - (multiple - 1));
294 }
295 
296 // -----------------------------------------------------------------------------
297 PoolAllocator::PoolAllocator(std::size_t size, uint64_t size_n_pages,
298  real_t growth_rate,
299  uint64_t max_mem_per_thread_factor)
300  : size_(size), tinfo_(ThreadInfo::GetInstance()) {
301  for (int nid = 0; nid < tinfo_->GetNumaNodes(); ++nid) {
302  void* ptr = numa_alloc_onnode(sizeof(NumaPoolAllocator), nid);
303  numa_allocators_.push_back(new (ptr) NumaPoolAllocator(
304  size, nid, size_n_pages, growth_rate, max_mem_per_thread_factor));
305  }
306 }
307 
309  : size_(other.size_),
310  tinfo_(other.tinfo_),
311  numa_allocators_(std::move(other.numa_allocators_)) {}
312 
314  for (auto* el : numa_allocators_) {
315  el->~NumaPoolAllocator();
316  numa_free(el, sizeof(NumaPoolAllocator));
317  }
318  numa_allocators_.clear();
319 }
320 
321 void* PoolAllocator::New(std::size_t size) {
322  assert(size_ == size && "Requested size does not match this PoolAllocator");
323  auto tid = tinfo_->GetMyThreadId();
324  auto nid = tinfo_->GetNumaNode(tid);
325  assert(static_cast<uint64_t>(nid) < numa_allocators_.size());
326  return numa_allocators_[nid]->New(tid);
327 }
328 
329 } // namespace memory_manager_detail
330 
331 // -----------------------------------------------------------------------------
332 MemoryManager::MemoryManager(uint64_t aligned_pages_shift, real_t growth_rate,
333  uint64_t max_mem_per_thread_factor)
334  : growth_rate_(growth_rate),
335  max_mem_per_thread_factor_(max_mem_per_thread_factor),
336  page_size_(sysconf(_SC_PAGESIZE)),
337  page_shift_(static_cast<uint64_t>(std::log2(page_size_))),
338  num_threads_(ThreadInfo::GetInstance()->GetMaxThreads()) {
339  aligned_pages_shift_ = aligned_pages_shift;
342 
343  if (max_mem_per_thread_factor_ < 1) {
344  Log::Fatal("MemoryManager",
345  "The parameter mem_mgr_max_mem_per_thread_factor must be "
346  "greater than 0");
347  }
348 
349  allocators_.reserve(num_threads_ * 2 + 100);
350 }
351 
353  for (auto& pair : allocators_) {
354  delete pair.second;
355  }
356 }
357 
358 void* MemoryManager::New(std::size_t size) {
359  if (allocators_.Capacity() > num_threads_) {
360  auto it = allocators_.find(size);
361  if (it != allocators_.end()) {
362  return it->second->New(size);
363  } else {
364  std::lock_guard<Spinlock> guard(lock_);
365  // check again, another thread might have created it in between
366  if (allocators_.find(size) == allocators_.end()) {
367  allocators_.insert(
368  std::make_pair(size, new memory_manager_detail::PoolAllocator(
371  }
372  return New(size);
373  }
374  } else {
375  std::lock_guard<Spinlock> guard(lock_);
376  auto it = allocators_.find(size);
377  if (it != allocators_.end()) {
378  return it->second->New(size);
379  } else {
380  allocators_.insert(std::make_pair(
381  size,
384  return allocators_.find(size)->second;
385  }
386  }
387 }
388 
389 void MemoryManager::Delete(void* p) {
390  if (ignore_delete_) {
391  return;
392  }
393  auto addr = reinterpret_cast<uint64_t>(p);
394  auto page_number = addr >> (page_shift_ + aligned_pages_shift_);
395  auto* page_addr = reinterpret_cast<char*>(
396  page_number << (page_shift_ + aligned_pages_shift_));
397  auto* npa =
398  *reinterpret_cast<memory_manager_detail::NumaPoolAllocator**>(page_addr);
399  npa->Delete(p);
400 }
401 
402 void MemoryManager::SetIgnoreDelete(bool value) { ignore_delete_ = value; }
403 
404 } // namespace bdm
bdm::memory_manager_detail::NumaPoolAllocator
Pool allocator for a specific allocation size and numa node. .
Definition: memory_manager.h:94
bdm::memory_manager_detail::PoolAllocator::tinfo_
ThreadInfo * tinfo_
Definition: memory_manager.h:143
bdm::memory_manager_detail::NumaPoolAllocator::kMetadataSize
static constexpr uint64_t kMetadataSize
Definition: memory_manager.h:110
bdm::memory_manager_detail::AllocatedBlock::initialized_until_
char * initialized_until_
Memory to the left has been initialized.
Definition: memory_manager.h:90
bdm::memory_manager_detail::List::nodes_before_skip_list_
uint64_t nodes_before_skip_list_
Definition: memory_manager.h:75
bdm::memory_manager_detail::List::PushBackN
void PushBackN(Node *head, Node *tail)
Definition: memory_manager.cc:83
bdm::memory_manager_detail::PoolAllocator::numa_allocators_
std::vector< NumaPoolAllocator * > numa_allocators_
Definition: memory_manager.h:144
bdm::MemoryManager::growth_rate_
real_t growth_rate_
Definition: memory_manager.h:163
bdm
Definition: agent.cc:39
bdm::memory_manager_detail::PoolAllocator::size_
std::size_t size_
Definition: memory_manager.h:142
string.h
bdm::memory_manager_detail::PoolAllocator::PoolAllocator
PoolAllocator(std::size_t size, uint64_t size_n_pages, real_t growth_rate, uint64_t max_mem_per_thread_factor)
Definition: memory_manager.cc:297
bdm::memory_manager_detail::NumaPoolAllocator::size_n_pages_
uint64_t size_n_pages_
Definition: memory_manager.h:111
bdm::MemoryManager::SetIgnoreDelete
void SetIgnoreDelete(bool value)
Definition: memory_manager.cc:402
bdm::memory_manager_detail::NumaPoolAllocator::lock_
Spinlock lock_
Definition: memory_manager.h:122
bdm::ThreadInfo::GetNumaNodes
int GetNumaNodes() const
Returns the number of NUMA nodes on this machine.
Definition: thread_info.h:48
bdm::MemoryManager::page_shift_
uint64_t page_shift_
Definition: memory_manager.h:166
bdm::memory_manager_detail::PoolAllocator::New
void * New(std::size_t size)
Definition: memory_manager.cc:321
bdm::MemoryManager::lock_
Spinlock lock_
Definition: memory_manager.h:176
bdm::Spinlock::lock
void lock()
Definition: spinlock.h:30
bdm::real_t
double real_t
Definition: real_t.h:21
bdm::MemoryManager::~MemoryManager
~MemoryManager()
Definition: memory_manager.cc:352
bdm::memory_manager_detail::NumaPoolAllocator::max_nodes_per_thread_
uint64_t max_nodes_per_thread_
Definition: memory_manager.h:113
bdm::memory_manager_detail::NumaPoolAllocator::memory_blocks_
std::vector< AllocatedBlock > memory_blocks_
Definition: memory_manager.h:119
bdm::MemoryManager::aligned_pages_shift_
uint64_t aligned_pages_shift_
Definition: memory_manager.h:167
bdm::MemoryManager::Delete
void Delete(void *p)
Definition: memory_manager.cc:389
bdm::memory_manager_detail::NumaPoolAllocator::free_lists_
std::vector< List > free_lists_
Definition: memory_manager.h:120
bdm::MemoryManager::ignore_delete_
bool ignore_delete_
Definition: memory_manager.h:171
numa_free
void numa_free(void *p, uint64_t)
Definition: numa.h:37
bdm::memory_manager_detail::List::PopBackN
void PopBackN(Node **head, Node **tail)
Definition: memory_manager.cc:106
bdm::memory_manager_detail::NumaPoolAllocator::nid_
int nid_
Definition: memory_manager.h:117
bdm::memory_manager_detail::List::head_
Node * head_
Definition: memory_manager.h:71
bdm::memory_manager_detail::NumaPoolAllocator::RoundUpTo
static uint64_t RoundUpTo(uint64_t number, uint64_t multiple)
Definition: memory_manager.cc:289
bdm::memory_manager_detail::NumaPoolAllocator::Delete
void Delete(void *p)
Definition: memory_manager.cc:218
bdm::MemoryManager::allocators_
UnorderedFlatmap< std::size_t, memory_manager_detail::PoolAllocator * > allocators_
Definition: memory_manager.h:174
bdm::memory_manager_detail::List::skip_list_
std::list< Node * > skip_list_
Definition: memory_manager.h:73
bdm::memory_manager_detail::NumaPoolAllocator::GetSize
uint64_t GetSize() const
Definition: memory_manager.cc:233
bdm::memory_manager_detail::List::n_
uint64_t n_
Number of nodes for which fast migrations are supported.
Definition: memory_manager.h:77
bdm::memory_manager_detail::NumaPoolAllocator::AllocNewMemoryBlock
void AllocNewMemoryBlock(std::size_t size)
Definition: memory_manager.cc:235
bdm::MemoryManager::max_mem_per_thread_factor_
uint64_t max_mem_per_thread_factor_
Definition: memory_manager.h:164
bdm::memory_manager_detail::NumaPoolAllocator::New
void * New(int tid)
Definition: memory_manager.cc:176
bdm::MemoryManager::aligned_pages_
uint64_t aligned_pages_
Definition: memory_manager.h:168
bdm::memory_manager_detail::List::PopBackNThreadSafe
void PopBackNThreadSafe(Node **head, Node **tail)
Definition: memory_manager.cc:122
bdm::memory_manager_detail::List::size_
uint64_t size_
Definition: memory_manager.h:74
bdm::memory_manager_detail::NumaPoolAllocator::~NumaPoolAllocator
~NumaPoolAllocator()
Definition: memory_manager.cc:169
bdm::memory_manager_detail::List::PushFront
void PushFront(Node *head)
Definition: memory_manager.cc:60
bdm::Log::Fatal
static void Fatal(const std::string &location, const Args &... parts)
Prints fatal error message.
Definition: log.h:115
bdm::memory_manager_detail::Node
Definition: memory_manager.h:32
numa_alloc_onnode
void * numa_alloc_onnode(uint64_t size, int nid)
Definition: numa.h:36
bdm::memory_manager_detail::NumaPoolAllocator::num_elements_per_n_pages_
uint64_t num_elements_per_n_pages_
Definition: memory_manager.h:114
bdm::memory_manager_detail::List::PopFront
Node * PopFront()
Definition: memory_manager.cc:38
bdm::memory_manager_detail::List::List
List(uint64_t n)
Definition: memory_manager.cc:28
log.h
bdm::memory_manager_detail::List
Definition: memory_manager.h:40
bdm::memory_manager_detail::AllocatedBlock::GetNextPageBatch
void GetNextPageBatch(uint64_t size_n_pages, char **start, uint64_t *size)
Definition: memory_manager.cc:140
memory_manager.h
bdm::memory_manager_detail::List::PushBackNThreadSafe
void PushBackNThreadSafe(Node *head, Node *tail)
Definition: memory_manager.cc:101
bdm::memory_manager_detail::NumaPoolAllocator::central_
List central_
Definition: memory_manager.h:121
bdm::memory_manager_detail::List::CanPopBackN
bool CanPopBackN() const
Definition: memory_manager.cc:129
bdm::memory_manager_detail::NumaPoolAllocator::size_
uint64_t size_
Definition: memory_manager.h:116
std
Definition: agent_uid.h:117
bdm::memory_manager_detail::List::Size
uint64_t Size() const
Definition: memory_manager.cc:131
bdm::MemoryManager::New
void * New(std::size_t size)
Definition: memory_manager.cc:358
bdm::MemoryManager::num_threads_
uint64_t num_threads_
Definition: memory_manager.h:170
bdm::MemoryManager::size_n_pages_
uint64_t size_n_pages_
Definition: memory_manager.h:169
bdm::memory_manager_detail::NumaPoolAllocator::total_size_
uint64_t total_size_
Definition: memory_manager.h:115
bdm::memory_manager_detail::Node::next
Node * next
Definition: memory_manager.h:33
bdm::ThreadInfo::GetMaxThreads
int GetMaxThreads() const
Return the maximum number of threads.
Definition: thread_info.h:66
bdm::memory_manager_detail::NumaPoolAllocator::InitializeNPages
void InitializeNPages(List *tl_list, char *block, uint64_t mem_block_size)
Definition: memory_manager.cc:252
bdm::memory_manager_detail::List::Empty
bool Empty() const
Definition: memory_manager.cc:127
bdm::memory_manager_detail::List::lock_
Spinlock lock_
Definition: memory_manager.h:78
bdm::memory_manager_detail::NumaPoolAllocator::growth_rate_
real_t growth_rate_
Definition: memory_manager.h:112
bdm::memory_manager_detail::NumaPoolAllocator::tinfo_
ThreadInfo * tinfo_
Definition: memory_manager.h:118
bdm::memory_manager_detail::PoolAllocator
Definition: memory_manager.h:129
bdm::ThreadInfo::GetMyThreadId
int GetMyThreadId() const
Definition: thread_info.h:39
bdm::memory_manager_detail::List::GetN
uint64_t GetN() const
Definition: memory_manager.cc:133
bdm::memory_manager_detail::PoolAllocator::~PoolAllocator
~PoolAllocator()
Definition: memory_manager.cc:313
bdm::memory_manager_detail::AllocatedBlock::IsFullyInitialized
bool IsFullyInitialized() const
Definition: memory_manager.cc:136
bdm::ThreadInfo
This class stores information about each thread. (e.g. to which NUMA node it belongs to....
Definition: thread_info.h:31
bdm::memory_manager_detail::NumaPoolAllocator::NumaPoolAllocator
NumaPoolAllocator(uint64_t size, int nid, uint64_t size_n_pages, real_t growth_rate, uint64_t max_mem_per_thread_factor)
Definition: memory_manager.cc:151
bdm::memory_manager_detail::List::tail_
Node * tail_
Definition: memory_manager.h:72
bdm::Spinlock::unlock
void unlock()
Definition: spinlock.h:37
bdm::MemoryManager::MemoryManager
MemoryManager(uint64_t aligned_pages_shift, real_t growth_rate, uint64_t max_mem_per_thread_factor)
Definition: memory_manager.cc:332
bdm::ThreadInfo::GetNumaNode
int GetNumaNode(int omp_thread_id) const
Returns the numa node the given openmp thread is bound to.
Definition: thread_info.h:51
bdm::memory_manager_detail::AllocatedBlock::end_pointer_
char * end_pointer_
Definition: memory_manager.h:88
bdm::memory_manager_detail::List::PushFrontThreadSafe
void PushFrontThreadSafe(Node *head)
Definition: memory_manager.cc:78