3#include <AMReX_Config.H>
20#include <unordered_set>
56 [[nodiscard]]
void*
alloc (std::size_t nbytes)
final;
79 [[nodiscard]] std::pair<void*,std::size_t>
80 alloc_in_place (
void* pt, std::size_t szmin, std::size_t szmax)
final;
104 void free (
void* vp)
final;
141 std::
size_t sizeOf (
void*
p) const noexcept;
158 void PrintUsage (std::
string const& name,
bool print_max_usage) const;
172 void PrintUsage (std::ostream& os, std::
string const& name, std::
string const& space) const;
192 Node (
void* a_block,
void* a_owner, std::size_t a_size,
MemStat* a_stat=
nullptr) noexcept
194 m_block(a_block), m_owner(a_owner), m_size(a_size), m_stat(a_stat) {}
203 bool operator< (
const Node& rhs)
const noexcept
205 return std::less<>{}(m_block, rhs.m_block);
211 return m_block == rhs.m_block;
215 [[nodiscard]]
void*
block () const noexcept {
return m_block; }
218 void block (
void* blk)
noexcept { m_block = blk; }
221 [[nodiscard]] std::size_t
size () const noexcept {
return m_size; }
224 void size (std::size_t sz)
noexcept { m_size = sz; }
226 [[nodiscard]]
void*
owner () const noexcept {
return m_owner; }
229 return m_owner == rhs.m_owner;
239 std::size_t operator() (
const Node& n)
const noexcept {
240 return std::hash<void*>{}(n.m_block);
260 m_nodes.reserve(1024);
265 if (curr == -1 || m_nodes[curr].m_max_subtree_size <
size) {
269 int left = m_nodes[curr].m_left;
270 if (left != -1 && m_nodes[left].m_max_subtree_size >=
size) {
272 }
else if (m_nodes[curr].m_node.size() >=
size) {
275 curr = m_nodes[curr].m_right;
285 return m_nodes[m_root].m_max_subtree_size;
289 return m_nodes.at(idx).m_node;
293 Node node = m_nodes.at(idx).m_node;
294 m_root = remove(m_root, node);
299 m_root = insert(m_root, node);
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;
320 if (node < m_nodes[curr].m_node) {
321 curr = m_nodes[curr].m_left;
324 curr = m_nodes[curr].m_right;
334 if (m_nodes[curr].m_node < node) {
335 curr = m_nodes[curr].m_right;
338 curr = m_nodes[curr].m_left;
344 [[nodiscard]]
int size ()
const {
345 return static_cast<int>(m_nodes.size())
346 -
static_cast<int>(m_free_node_indices.size());
351 iterate_imp(m_root, f);
356 struct NodeWithSize {
359 std::size_t m_max_subtree_size;
365 std::vector<NodeWithSize> m_nodes;
366 std::vector<int> m_free_node_indices;
369 int createNode (
const Node& node) {
371 if (!m_free_node_indices.empty()) {
372 idx = m_free_node_indices.back();
373 m_free_node_indices.pop_back();
375 .m_node=node, .m_max_subtree_size=node.size(),
376 .m_height=1, .m_left=-1, .m_right=-1
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
388 void destroyNode (
int idx) {
389 m_free_node_indices.push_back(idx);
392 [[nodiscard]] std::size_t getMax (
int idx)
const {
393 return idx != -1 ? m_nodes[idx].m_max_subtree_size : 0;
396 [[nodiscard]]
int getHeight (
int idx)
const {
397 return idx != -1 ? m_nodes[idx].m_height : 0;
400 [[nodiscard]]
int getBalance (
int idx)
const {
402 getHeight(m_nodes[idx].m_left) - getHeight(m_nodes[idx].m_right) : 0;
405 void updateMetadata (
int idx) {
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(),
419 int rotateRight (
int y) {
420 int x = m_nodes[
y].m_left;
421 int T2 = m_nodes[
x].m_right;
423 m_nodes[
x].m_right =
y;
424 m_nodes[
y].m_left = T2;
431 int rotateLeft (
int x) {
432 int y = m_nodes[
x].m_right;
433 int T2 = m_nodes[
y].m_left;
435 m_nodes[
y].m_left =
x;
436 m_nodes[
x].m_right = T2;
443 int balanceNode (
int idx) {
445 int balance = getBalance(idx);
447 if (getBalance(m_nodes[idx].m_left) < 0) {
448 m_nodes[idx].m_left = rotateLeft(m_nodes[idx].m_left);
450 return rotateRight(idx);
453 if (getBalance(m_nodes[idx].m_right) > 0) {
454 m_nodes[idx].m_right = rotateRight(m_nodes[idx].m_right);
456 return rotateLeft(idx);
461 int insert (
int idx,
const Node& node) {
463 return createNode(node);
465 if (node < m_nodes[idx].m_node) {
466 m_nodes[idx].m_left = insert(m_nodes[idx].m_left, node);
468 m_nodes[idx].m_right = insert(m_nodes[idx].m_right, node);
470 return balanceNode(idx);
473 [[nodiscard]]
int findMin (
int idx)
const {
474 while (m_nodes[idx].m_left != -1) {
475 idx = m_nodes[idx].m_left;
480 int remove (
int idx,
const Node& node) {
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);
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;
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);
501 return balanceNode(idx);
505 void iterate_imp (
int idx,
const F& f)
const {
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);
515 std::vector<std::pair<void*,std::size_t> >
m_alloc;
Memory arena base class and global arena accessors.
while parser_exe_t p
Definition AMReX_Parser_Exe_Body.H:33
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
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