Block-Structured AMR Software Framework
Loading...
Searching...
No Matches
AMReX_CArena.H
Go to the documentation of this file.
1#ifndef BL_CARENA_H
2#define BL_CARENA_H
3#include <AMReX_Config.H>
4
9
10#include <AMReX_Arena.H>
11
12#include <algorithm>
13#include <atomic>
14#include <cstddef>
15#include <functional>
16#include <iosfwd>
17#include <map>
18#include <mutex>
19#include <string>
20#include <unordered_set>
21#include <vector>
22
23namespace amrex {
24
34class CArena
35 :
36 public Arena
37{
38public:
45 CArena (std::size_t hunk_size = 0, ArenaInfo info = ArenaInfo());
46
47 CArena (const CArena& rhs) = delete;
48 CArena (CArena&& rhs) = delete;
49 CArena& operator= (const CArena& rhs) = delete;
50 CArena& operator= (CArena&& rhs) = delete;
51
53 ~CArena () override;
54
56 [[nodiscard]] void* alloc (std::size_t nbytes) final;
57
79 [[nodiscard]] std::pair<void*,std::size_t>
80 alloc_in_place (void* pt, std::size_t szmin, std::size_t szmax) final;
81
95 [[nodiscard]] void*
96 shrink_in_place (void* pt, std::size_t new_size) final;
97
104 void free (void* vp) final;
105
110 std::size_t freeUnused () final;
111
115 [[nodiscard]] std::size_t freeableMemory () const;
116
118 [[nodiscard]] std::size_t largestFreeBlock () const final;
119
128 [[nodiscard]] bool hasFreeDeviceMemory (std::size_t sz) final;
129
131 std::size_t heap_space_used () const noexcept;
132
134 std::size_t heap_space_actually_used () const noexcept;
135
141 std::size_t sizeOf (void* p) const noexcept;
142
158 void PrintUsage (std::string const& name, bool print_max_usage) const;
159
172 void PrintUsage (std::ostream& os, std::string const& name, std::string const& space) const;
173
175 void ResetMaxUsageCounter () final {
177 }
178
180 constexpr static std::size_t DefaultHunkSize = 1024*1024*8;
181
182protected:
183
184 void* alloc_protected (std::size_t nbytes);
185
186 std::size_t freeUnused_protected () final;
187
189 class Node
190 {
191 public:
192 Node (void* a_block, void* a_owner, std::size_t a_size, MemStat* a_stat=nullptr) noexcept
193 :
194 m_block(a_block), m_owner(a_owner), m_size(a_size), m_stat(a_stat) {}
195
196 Node (const Node& rhs) = default;
197 Node (Node&& rhs) = default;
198 Node& operator= (const Node& rhs) = default;
199 Node& operator= (Node&& rhs) = default;
200 ~Node () = default;
201
203 bool operator< (const Node& rhs) const noexcept
204 {
205 return std::less<>{}(m_block, rhs.m_block);
206 }
207
209 bool operator== (const Node& rhs) const noexcept
210 {
211 return m_block == rhs.m_block;
212 }
213
215 [[nodiscard]] void* block () const noexcept { return m_block; }
216
218 void block (void* blk) noexcept { m_block = blk; }
219
221 [[nodiscard]] std::size_t size () const noexcept { return m_size; }
222
224 void size (std::size_t sz) noexcept { m_size = sz; }
225
226 [[nodiscard]] void* owner () const noexcept { return m_owner; }
227
228 [[nodiscard]] bool coalescable (const Node& rhs) const noexcept {
229 return m_owner == rhs.m_owner;
230 }
231
233 [[nodiscard]] MemStat* mem_stat () const { return m_stat; }
234
236 void mem_stat (MemStat* a_stat) noexcept { m_stat = a_stat; }
237
238 struct hash {
239 std::size_t operator() (const Node& n) const noexcept {
240 return std::hash<void*>{}(n.m_block);
241 }
242 };
243
244 private:
246 void* m_block;
248 void* m_owner;
250 std::size_t m_size;
252 MemStat* m_stat;
253 };
254
255
257 public:
258
260 m_nodes.reserve(1024);
261 }
262
263 [[nodiscard]] int getFirstFit (std::size_t size) const {
264 int curr = m_root;
265 if (curr == -1 || m_nodes[curr].m_max_subtree_size < size) {
266 return -1;
267 }
268 while (curr != -1) {
269 int left = m_nodes[curr].m_left;
270 if (left != -1 && m_nodes[left].m_max_subtree_size >= size) {
271 curr = left;
272 } else if (m_nodes[curr].m_node.size() >= size) {
273 break;
274 } else {
275 curr = m_nodes[curr].m_right;
276 }
277 }
278 return curr;
279 }
280
281 [[nodiscard]] std::size_t getLargestFreeBlock () const {
282 if (m_root == -1) {
283 return 0;
284 }
285 return m_nodes[m_root].m_max_subtree_size;
286 }
287
288 [[nodiscard]] const Node& viewNode (int idx) const {
289 return m_nodes.at(idx).m_node;
290 }
291
292 Node extractNode (int idx) {
293 Node node = m_nodes.at(idx).m_node;
294 m_root = remove(m_root, node);
295 return node;
296 }
297
298 void insertNode (const Node& node) {
299 m_root = insert(m_root, node);
300 }
301
302 [[nodiscard]] int find (const Node& node) const {
303 int curr = m_root;
304 while (curr != -1) {
305 if (node < m_nodes[curr].m_node) {
306 curr = m_nodes[curr].m_left;
307 } else if (m_nodes[curr].m_node < node) {
308 curr = m_nodes[curr].m_right;
309 } else {
310 return curr;
311 }
312 }
313 return curr;
314 }
315
316 [[nodiscard]] int findPredecessor (const Node& node) const {
317 int curr = m_root;
318 int pred = -1;
319 while (curr != -1) {
320 if (node < m_nodes[curr].m_node) {
321 curr = m_nodes[curr].m_left;
322 } else {
323 pred = curr;
324 curr = m_nodes[curr].m_right;
325 }
326 }
327 return pred;
328 }
329
330 [[nodiscard]] int findSuccessor (const Node& node) const {
331 int curr = m_root;
332 int succ = -1;
333 while (curr != -1) {
334 if (m_nodes[curr].m_node < node) {
335 curr = m_nodes[curr].m_right;
336 } else {
337 succ = curr;
338 curr = m_nodes[curr].m_left;
339 }
340 }
341 return succ;
342 }
343
344 [[nodiscard]] int size () const {
345 return static_cast<int>(m_nodes.size())
346 - static_cast<int>(m_free_node_indices.size());
347 }
348
349 template<class F>
350 void iterate (const F& f) const {
351 iterate_imp(m_root, f);
352 }
353
354 private:
355
356 struct NodeWithSize {
357 Node m_node;
359 std::size_t m_max_subtree_size;
360 int m_height;
361 int m_left;
362 int m_right;
363 };
364
365 std::vector<NodeWithSize> m_nodes;
366 std::vector<int> m_free_node_indices;
367 int m_root = -1;
368
369 int createNode (const Node& node) {
370 int idx;
371 if (!m_free_node_indices.empty()) {
372 idx = m_free_node_indices.back();
373 m_free_node_indices.pop_back();
374 m_nodes[idx] = {
375 .m_node=node, .m_max_subtree_size=node.size(),
376 .m_height=1, .m_left=-1, .m_right=-1
377 };
378 } else {
379 idx = static_cast<int>(m_nodes.size());
380 m_nodes.push_back(NodeWithSize{
381 .m_node=node, .m_max_subtree_size=node.size(),
382 .m_height=1, .m_left=-1, .m_right=-1
383 });
384 }
385 return idx;
386 }
387
388 void destroyNode (int idx) {
389 m_free_node_indices.push_back(idx);
390 }
391
392 [[nodiscard]] std::size_t getMax (int idx) const {
393 return idx != -1 ? m_nodes[idx].m_max_subtree_size : 0;
394 }
395
396 [[nodiscard]] int getHeight (int idx) const {
397 return idx != -1 ? m_nodes[idx].m_height : 0;
398 }
399
400 [[nodiscard]] int getBalance (int idx) const {
401 return idx != -1 ?
402 getHeight(m_nodes[idx].m_left) - getHeight(m_nodes[idx].m_right) : 0;
403 }
404
405 void updateMetadata (int idx) {
406 if (idx == -1) {
407 return;
408 }
409 int l = m_nodes[idx].m_left;
410 int r = m_nodes[idx].m_right;
411 m_nodes[idx].m_height = 1 + std::max(getHeight(l), getHeight(r));
412 m_nodes[idx].m_max_subtree_size = std::max({
413 m_nodes[idx].m_node.size(),
414 getMax(l),
415 getMax(r)
416 });
417 }
418
419 int rotateRight (int y) {
420 int x = m_nodes[y].m_left;
421 int T2 = m_nodes[x].m_right;
422
423 m_nodes[x].m_right = y;
424 m_nodes[y].m_left = T2;
425
426 updateMetadata(y);
427 updateMetadata(x);
428 return x;
429 }
430
431 int rotateLeft (int x) {
432 int y = m_nodes[x].m_right;
433 int T2 = m_nodes[y].m_left;
434
435 m_nodes[y].m_left = x;
436 m_nodes[x].m_right = T2;
437
438 updateMetadata(x);
439 updateMetadata(y);
440 return y;
441 }
442
443 int balanceNode (int idx) {
444 updateMetadata(idx);
445 int balance = getBalance(idx);
446 if (balance > 1) {
447 if (getBalance(m_nodes[idx].m_left) < 0) {
448 m_nodes[idx].m_left = rotateLeft(m_nodes[idx].m_left);
449 }
450 return rotateRight(idx);
451 }
452 if (balance < -1) {
453 if (getBalance(m_nodes[idx].m_right) > 0) {
454 m_nodes[idx].m_right = rotateRight(m_nodes[idx].m_right);
455 }
456 return rotateLeft(idx);
457 }
458 return idx;
459 }
460
461 int insert (int idx, const Node& node) {
462 if (idx == -1) {
463 return createNode(node);
464 }
465 if (node < m_nodes[idx].m_node) {
466 m_nodes[idx].m_left = insert(m_nodes[idx].m_left, node);
467 } else {
468 m_nodes[idx].m_right = insert(m_nodes[idx].m_right, node);
469 }
470 return balanceNode(idx);
471 }
472
473 [[nodiscard]] int findMin (int idx) const {
474 while (m_nodes[idx].m_left != -1) {
475 idx = m_nodes[idx].m_left;
476 }
477 return idx;
478 }
479
480 int remove (int idx, const Node& node) {
481 if (idx == -1) {
482 return -1;
483 }
484 if (node < m_nodes[idx].m_node) {
485 m_nodes[idx].m_left = remove(m_nodes[idx].m_left, node);
486 } else if (m_nodes[idx].m_node < node) {
487 m_nodes[idx].m_right = remove(m_nodes[idx].m_right, node);
488 } else {
489 if (m_nodes[idx].m_left == -1 || m_nodes[idx].m_right == -1) {
490 int temp = (m_nodes[idx].m_left != -1) ?
491 m_nodes[idx].m_left : m_nodes[idx].m_right;
492 destroyNode(idx);
493 return temp;
494 } else {
495 int temp = findMin(m_nodes[idx].m_right);
496 m_nodes[idx].m_node = m_nodes[temp].m_node;
497 m_nodes[idx].m_max_subtree_size = m_nodes[temp].m_max_subtree_size;
498 m_nodes[idx].m_right = remove(m_nodes[idx].m_right, m_nodes[temp].m_node);
499 }
500 }
501 return balanceNode(idx);
502 }
503
504 template<class F>
505 void iterate_imp (int idx, const F& f) const {
506 if (idx != -1) {
507 iterate_imp(m_nodes[idx].m_left, f);
508 f(m_nodes[idx].m_node);
509 iterate_imp(m_nodes[idx].m_right, f);
510 }
511 }
512 };
513
515 std::vector<std::pair<void*,std::size_t> > m_alloc;
516
521
527
532// NL m_busylist;
533 std::unordered_set<Node, Node::hash> m_busylist;
535 std::size_t m_hunk;
538 std::atomic<std::size_t> m_used{0};
540 std::size_t m_max_used{0};
543 std::atomic<std::size_t> m_actually_used{0};
545 std::size_t m_max_actually_used{0};
546
547 mutable std::mutex carena_mutex;
548
550 friend std::ostream& operator<< (std::ostream& os, const CArena& arena);
551};
552
553}
554
555#endif /*BL_CARENA_H*/
Memory arena base class and global arena accessors.
while parser_exe_t p
Definition AMReX_Parser_Exe_Body.H:33
Arena() noexcept=default
Definition AMReX_CArena.H:256
int findSuccessor(const Node &node) const
Definition AMReX_CArena.H:330
void iterate(const F &f) const
Definition AMReX_CArena.H:350
int findPredecessor(const Node &node) const
Definition AMReX_CArena.H:316
Node extractNode(int idx)
Definition AMReX_CArena.H:292
void insertNode(const Node &node)
Definition AMReX_CArena.H:298
const Node & viewNode(int idx) const
Definition AMReX_CArena.H:288
int size() const
Definition AMReX_CArena.H:344
NodeTreeWithSize()
Definition AMReX_CArena.H:259
std::size_t getLargestFreeBlock() const
Definition AMReX_CArena.H:281
int find(const Node &node) const
Definition AMReX_CArena.H:302
int getFirstFit(std::size_t size) const
Definition AMReX_CArena.H:263
The nodes in our free list and block list.
Definition AMReX_CArena.H:190
std::size_t size() const noexcept
The size of the memory block.
Definition AMReX_CArena.H:221
void block(void *blk) noexcept
Set block address.
Definition AMReX_CArena.H:218
void size(std::size_t sz) noexcept
Set size.
Definition AMReX_CArena.H:224
void * owner() const noexcept
Definition AMReX_CArena.H:226
MemStat * mem_stat() const
Get the MemStat object of the function where this block was allocated.
Definition AMReX_CArena.H:233
Node(Node &&rhs)=default
void mem_stat(MemStat *a_stat) noexcept
Set MemStat.
Definition AMReX_CArena.H:236
bool coalescable(const Node &rhs) const noexcept
Definition AMReX_CArena.H:228
void * block() const noexcept
The block address.
Definition AMReX_CArena.H:215
Node(void *a_block, void *a_owner, std::size_t a_size, MemStat *a_stat=nullptr) noexcept
Definition AMReX_CArena.H:192
Node(const Node &rhs)=default
NL m_freelist
The free list of allocated but not currently used blocks. Maintained in lo to hi memory sorted order.
Definition AMReX_CArena.H:526
std::size_t sizeOf(void *p) const noexcept
Return the size of the allocation referenced by p (0 if unknown).
Definition AMReX_CArena.cpp:478
CArena(const CArena &rhs)=delete
NodeTreeWithSize NL
The type of our freelist.
Definition AMReX_CArena.H:520
std::atomic< std::size_t > m_actually_used
Definition AMReX_CArena.H:543
static constexpr std::size_t DefaultHunkSize
The default memory hunk size to grab from the heap.
Definition AMReX_CArena.H:180
void * shrink_in_place(void *pt, std::size_t new_size) final
Shrink allocation size in-place.
Definition AMReX_CArena.cpp:245
CArena(std::size_t hunk_size=0, ArenaInfo info=ArenaInfo())
Construct a coalescing memory manager.
Definition AMReX_CArena.cpp:33
std::mutex carena_mutex
Definition AMReX_CArena.H:547
std::size_t freeUnused_protected() final
Definition AMReX_CArena.cpp:402
std::size_t m_max_actually_used
The max amount of memory given out via alloc().
Definition AMReX_CArena.H:545
std::size_t heap_space_actually_used() const noexcept
Return the total amount of memory given out via alloc. Thread-safe.
Definition AMReX_CArena.cpp:472
std::size_t heap_space_used() const noexcept
The current amount of heap space used by the CArena object. Thread-safe.
Definition AMReX_CArena.cpp:466
std::pair< void *, std::size_t > alloc_in_place(void *pt, std::size_t szmin, std::size_t szmax) final
Allocate memory in-place if possible.
Definition AMReX_CArena.cpp:170
CArena & operator=(const CArena &rhs)=delete
friend std::ostream & operator<<(std::ostream &os, const CArena &arena)
Print a summary of the arena's free and busy lists to os.
Definition AMReX_CArena.cpp:530
void ResetMaxUsageCounter() final
Reset the maximum usage counter.
Definition AMReX_CArena.H:175
std::size_t m_hunk
The minimal size of hunks to request from system.
Definition AMReX_CArena.H:535
std::size_t freeUnused() final
Free unused memory back to the system. Return value is the amount of memory freed.
Definition AMReX_CArena.cpp:372
std::unordered_set< Node, Node::hash > m_busylist
The list of busy blocks. A block is either on the freelist or on the blocklist, but not on both.
Definition AMReX_CArena.H:533
void * alloc(std::size_t nbytes) final
Allocate some memory.
Definition AMReX_CArena.cpp:49
CArena(CArena &&rhs)=delete
void free(void *vp) final
Free up allocated memory. Merge neighboring free memory chunks into largest possible chunk.
Definition AMReX_CArena.cpp:301
std::size_t largestFreeBlock() const final
Return the largest free memory block already held by this CArena.
Definition AMReX_CArena.cpp:395
~CArena() override
The destructor.
Definition AMReX_CArena.cpp:41
bool hasFreeDeviceMemory(std::size_t sz) final
Does the device have enough free memory for allocating this much memory? For CPU builds,...
Definition AMReX_CArena.cpp:439
void * alloc_protected(std::size_t nbytes)
Definition AMReX_CArena.cpp:57
void PrintUsage(std::string const &name, bool print_max_usage) const
Print memory usage information of this arena.
Definition AMReX_CArena.cpp:493
std::vector< std::pair< void *, std::size_t > > m_alloc
The list of blocks allocated.
Definition AMReX_CArena.H:515
std::atomic< std::size_t > m_used
Definition AMReX_CArena.H:538
std::size_t freeableMemory() const
Return the amount of memory that can be released back to the heap.
Definition AMReX_CArena.cpp:379
std::size_t m_max_used
The max amount of heap space currently allocated.
Definition AMReX_CArena.H:540
Definition AMReX_Amr.cpp:50
@ F
Definition AMReX_Order.H:7
bool operator==(A1 const &a1, A2 const &a2)
Definition AMReX_GpuAllocators.H:214
@ y
Definition AMReX_Orientation.H:14
@ x
Definition AMReX_Orientation.H:14
Configuration options for constructing an Arena.
Definition AMReX_Arena.H:92
Definition AMReX_CArena.H:238
Definition AMReX_Arena.H:21