You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by am...@apache.org on 2018/08/17 18:11:34 UTC
[trafficserver] branch master updated: MemArena: Add make method to
construct objects in the arena. Update documentation.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new 60e778e MemArena: Add make method to construct objects in the arena. Update documentation.
60e778e is described below
commit 60e778e177d36b6d4cb26689da2a9782821c8aa8
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Thu Jun 28 21:07:48 2018 -0500
MemArena: Add make method to construct objects in the arena.
Update documentation.
---
doc/conf.py | 3 +-
.../internal-libraries/MemArena.en.rst | 309 ++++++++-------------
lib/ts/MemArena.cc | 99 +++----
lib/ts/MemArena.h | 161 ++++++-----
lib/ts/unit-tests/test_MemArena.cc | 99 +++++--
5 files changed, 334 insertions(+), 337 deletions(-)
diff --git a/doc/conf.py b/doc/conf.py
index 1f09e42..54e7b10 100644
--- a/doc/conf.py
+++ b/doc/conf.py
@@ -167,7 +167,8 @@ pygments_style = 'sphinx'
#modindex_common_prefix = []
nitpicky = True
-nitpick_ignore = [
+nitpick_ignore = [ ('cpp:typeOrConcept', 'T')
+ , ('cpp:typeOrConcept', 'Args')
]
# Autolink issue references.
diff --git a/doc/developer-guide/internal-libraries/MemArena.en.rst b/doc/developer-guide/internal-libraries/MemArena.en.rst
index 76ffdb4..6b2bc02 100644
--- a/doc/developer-guide/internal-libraries/MemArena.en.rst
+++ b/doc/developer-guide/internal-libraries/MemArena.en.rst
@@ -1,22 +1,17 @@
.. Licensed to the Apache Software Foundation (ASF) under one
- or more contributor license agreements. See the NOTICE file
- distributed with this work for additional information
- regarding copyright ownership. The ASF licenses this file
- to you under the Apache License, Version 2.0 (the
- "License"); you may not use this file except in compliance
- with the License. You may obtain a copy of the License at
+ or more contributor license agreements. See the NOTICE file distributed with this work for
+ additional information regarding copyright ownership. The ASF licenses this file to you under the
+ Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with
+ the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
- Unless required by applicable law or agreed to in writing,
- software distributed under the License is distributed on an
- "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- KIND, either express or implied. See the License for the
- specific language governing permissions and limitations
- under the License.
-
-.. include:: ../../common.defs
+ Unless required by applicable law or agreed to in writing, software distributed under the License
+ is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing permissions and limitations under
+ the License.
+.. include:: ../../common.defs
.. highlight:: cpp
.. default-domain:: cpp
.. |MemArena| replace:: :class:`MemArena`
@@ -26,211 +21,133 @@
MemArena
*************
-|MemArena| provides a memory arena or pool for allocating memory. The intended use is for allocating many small chunks of memory - few, large allocations are best handled independently. The purpose is to amortize the cost of allocation of each chunk across larger allocations in a heap style. In addition the allocated memory is presumed to have similar lifetimes so that all of the memory in the arena can be de-allocatred en masse. This is a memory allocation style used by many cotainers - [...]
+|MemArena| provides a memory arena or pool for allocating memory. Internally |MemArena| reserves
+memory in large blocks and allocates pieces of those blocks when memory is requested. Upon
+destruction all of the reserved memory is released which also destroys all of the allocated memory.
+This is useful when the goal is any (or all) of trying to
+
+* amortize allocation costs for many small allocations.
+* create better memory locality for containers.
+* de-allocate memory in bulk.
Description
+++++++++++
-|MemArena| manages an internal list of memory blocks, out of which it provides allocated
-blocks of memory. When an instance is destructed all the internal blocks are also freed. The
-expected use of this class is as an embedded memory manager for a container class.
-
-To support coalescence and compaction of memory, the methods :func:`MemArena::freeze` and
-:func:`MemArena::thaw` are provided. These create in effect generations of memory allocation.
-Calling :func:`MemArena::freeze` marks a generation. After this call any further allocations will
-be in new internal memory blocks. The corresponding call to :func:`MemArena::thaw` cause older
-generations of internal memory to be freed. The general logic for the container would be to freeze,
-re-allocate and copy the container elements, then thaw. This would result in compacted memory
-allocation in a single internal block. The uses cases would be either a process static data
-structure after initialization (coalescing for locality performence) or a container that naturally
-re-allocates (such as a hash table during a bucket expansion). A container could also provide its
-own API for its clients to cause a coalesence.
-
-Other than freeze / thaw, this class does not offer any mechanism to release memory beyond its destruction. This is not an issue for either process globals or transient arenas.
-
-Internals
-+++++++++
-
-|MemArena| opperates in *generations* of internal blocks of memory. Each generation marks a series internal block of memory. Allocations always occur from the most recent block within a generation, as it is always the largest and has the most unallocated space. The most recent block (current) is also the head of the linked list of memory blocks. Allocations are given in the form of a :class:`MemSpan`. Once an internal block of memory has exhausted it's avaliable space, a new, larger, int [...]
-
-.. uml::
- :align: center
-
- component [block] as b1
- component [block] as b2
- component [block] as b3
- component [block] as b4
- component [block] as b5
- component [block] as b6
-
- b1 -> b2
- b2 -> b3
- b3 -> b4
- b4 -> b5
- b5 -> b6
-
- generation -u- b3
- current -u- b1
-
-A call to :func:`MemArena::thaw` will deallocate any generation that is not the current generation. Thus, currently it is impossible to deallocate ie. just the third generation. Everything after the generation pointer is in previous generations and everything before, and including, the generation pointer is in the current generation. Since blocks are reference counted, thawing is just a single assignment to drop everything after the generation pointer. After a :func:`MemArena::thaw`:
-
-.. uml::
- :align: center
-
- component [block] as b3
- component [block] as b4
- component [block] as b5
- component [block] as b6
-
-
- b3 -> b4
- b4 -> b5
- b5 -> b6
-
- current -u- b3
- generation -u- b6
-
-A generation can only be updated with an explicit call to :func:`MemArena::freeze`. The next generation is not actually allocated until a call to :func:`MemArena::alloc` happens. On the :func:`MemArena::alloc` following a :func:`MemArena::freeze` the next internal block of memory is the larger of the sum of all current allocations or the number of bytes requested. The reason for this is that the caller could :func:`MemArena::alloc` a size larger than all current allocations at which poin [...]
-
-.. uml::
- :align: center
-
- component [block] as b3
- component [block] as b4
- component [block] as b5
- component [block] as b6
-
-
- b3 -> b4
- b4 -> b5
- b5 -> b6
-
- current -u- b3
-
-After the next :func:`MemArena::alloc`:
-
-.. uml::
- :align: center
-
- component [block\nnew generation] as b3
- component [block] as b4
- component [block] as b5
- component [block] as b6
- component [block] as b7
-
-
- b3 -> b4
- b4 -> b5
- b5 -> b6
- b6 -> b7
-
- generation -u- b3
- current -u- b3
-
-A caller can actually :func:`MemArena::alloc` **any** number of bytes. Internally, if the arena is unable to allocate enough memory for the allocation, it will create a new internal block of memory large enough and allocate from that. So if the arena is allocated like:
-
-.. code-block:: cpp
-
- ts::MemArena *arena = new ts::MemArena(64);
-
-The caller can actually allocate more than 64 bytes.
-
-.. code-block:: cpp
-
- ts::MemSpan span1 = arena->alloc(16);
- ts::MemSpan span1 = arena->alloc(256);
-
-Now, span1 and span2 are in the same generation and can both be safely used. After:
-
-.. code-block:: cpp
-
- arena->freeze();
- ts::MemSpan span3 = arena->alloc(512);
- arena->thaw();
-
-span3 can still be used but span1 and span2 have been deallocated and usage is undefined.
-
-Internal blocks are adjusted for optimization. Each :class:`MemArena::Block` is just a header for the underlying memory it manages. The header and memory are allocated together for locality such that each :class:`MemArena::Block` is immediately followed with the memory it manages. If a :class:`MemArena::Block` is larger than a page (defaulted at 4KB), it is aligned to a power of two. The actual memory that a :class:`MemArena::Block` can allocate out is slightly smaller. This is because a [...]
+When a |MemArena| instance is constructed no memory is reserved. A hint can be provided so that the
+first internal reservation of memory will have close to but at least that amount of free space
+available to be allocated.
+
+In normal use memory is allocated from |MemArena| using :func:`MemArena::alloc` to get chunks
+of memory, or :func:`MemArena::make` to get constructed class instances. :func:`MemArena::make`
+takes an arbitrary set of arguments which it attempts to pass to a constructor for the type
+:code:`T` after allocating memory (:code:`sizeof(T)` bytes) for the object. If there isn't enough
+free reserved memory, a new internal block is reserved. The size of the new reserved memory will be at least
+the size of the currently reserved memory, making each reservation larger than the last.
+
+The arena can be **frozen** using :func:`MemArena::freeze` which locks down the currently reserved
+memory and forces the internal reservation of memory for the next allocation. By default this
+internal reservation will be the size of the frozen allocated memory. If this isn't the best value a
+hint can be provided to the :func:`MemArena::freeze` method to specify a different value, in the
+same manner as the hint to the constructor. When the arena is thawed (unfrozen) using
+:func:`MemArena::thaw` the frozen memory is released, which also destroys the frozen allocated
+memory. Doing this can be useful after a series of allocations, which can result in the allocated
+memory being in different internal blocks, along with possibly no longer in use memory. The result
+is to coalesce (or garbage collect) all of the in use memory in the arena into a single bulk
+internal reserved block. This improves memory efficiency and memory locality. This coalescence is
+done by
+
+#. Freezing the arena.
+#. Copying all objects back in to the arena.
+#. Thawing the arena.
+
+Because the default reservation hint is large enough for all of the previously allocated memory, all
+of the copied objects will be put in the same new internal block. If this for some reason this
+sizing isn't correct a hint can be passed to :func:`MemArena::freeze` to specify a different value
+(if, for instance, there is a lot of unused memory of known size). Generally this is most useful for
+data that is initialized on process start and not changed after process startup. After the process
+start initilization, the data can be coalesced for better performance after all modifications have
+been done. Alternatively, a container that allocates and de-allocates same sized objects (such as a
+:code:`std::map`) can use a free list to re-use objects before going to the |MemArena| for more
+memory and thereby avoiding collecting unused memory in the arena.
+
+Other than a freeze / thaw cycle, there is no mechanism to release memory except for the destruction
+of the |MemArena|. In such use cases either wasted memory must be small enough or temporary enough
+to not be an issue, or there must be a provision for some sort of garbage collection.
+
+Generally |MemArena| is not as useful for classes that allocate their own internal memory
+(such as :code:`std::string` or :code:`std::vector`), which includes most container classes. One
+container class that can be easily used is :class:`IntrusiveDList` because the links are in the
+instance and therefore also in the arena.
+
+Objects created in the arena must not have :code:`delete` called on them as this will corrupt
+memory, usually leading to an immediate crash. The memory for the instance will be released when the
+arena is destroyed. The destructor can be called if needed but in general if a destructor is needed
+it is probably not a class that should be constructed in the arena. Looking at
+:class:`IntrusiveDList` again for an example, if this is used to link objects in the arena, there is
+no need for a destructor to clean up the links - all of the objects will be de-allocated when the
+arena is destroyed. Whether this kind of situation can be arranged with reasonable effort is a good
+heuristic on whether |MemArena| is an appropriate choice.
+
+While |MemArena| will normally allocate memory in successive chunks from an internal block, if the
+allocation request is large (more than a memory page) and there is not enough space in the current
+internal block, a block just for that allocation will be created. This is useful if the purpose of
+|MemArena| is to track blocks of memory more than reduce the number of system level allocations.
Reference
+++++++++
.. class:: MemArena
- .. class:: Block
-
- Underlying memory allocated is owned by the :class:`Block`. A linked list.
-
- .. member:: size_t size
- .. member:: size_t allocated
- .. member:: std::shared_ptr<Block> next
- .. function:: Block(size_t n)
- .. function:: char* data()
-
- .. function:: MemArena()
+ .. function:: MemArena(size_t n)
- Construct an empty arena.
-
- .. function:: explicit MemArena(size_t n)
-
- Construct an arena with :arg:`n` bytes.
+ Construct a memory arena. :arg:`n` is optional. Initially not memory is reserved. If :arg:`n`
+ is provided this is a hint that the first internal memory reservation should provide roughly
+ and at least :arg:`n` bytes of free space. Otherwise the internal default hint is used. A call
+ to :code:`alloc(0)` will not allocate memory but will force the reservation of internal memory
+ if this should be done immediately rather than lazily.
.. function:: MemSpan alloc(size_t n)
- Allocate an :arg:`n` byte chunk of memory in the arena.
-
- .. function:: MemArena& freeze(size_t n = 0)
+ Allocate memory of size :arg:`n` bytes in the arena. If :arg:`n` is zero then internal memory
+ will be reserved if there is currently none, otherwise it is a no-op.
- Block all further allocation from any existing internal blocks. If :arg:`n` is zero then on the next allocation request a block twice as large as the current generation, otherwise the next internal block will be large enough to hold :arg:`n` bytes.
+ .. function:: template < typename T, typename ... Args > T * make(Args&& ... args)
- .. function:: MemArena& thaw()
-
- Unallocate all internal blocks that were allocated before the current generation.
-
- .. function:: MemArena& empty()
-
- Empties the entire arena and deallocates all underlying memory. Next block size will be equal to the sum of all allocations before the call to empty.
-
- .. function:: size_t size() const
-
- Get the current generation size. The default size of the arena is 32KB unless otherwise specified.
-
- .. function:: size_t remaining() const
-
- Amount of space left in the generation.
-
- .. function:: size_t allocated_size() const
-
- Total number of bytes allocated in the arena.
+ Create an instance of :arg:`T`. :code:`sizeof(T)` bytes of memory are allocated from the arena
+ and the constructor invoked. This method takes any set of arguments, which are passed to
+ the constructor. A pointer to the newly constructed instance of :arg:`T` is returned. Note if
+ the instance allocates other memory that memory will not be in the arena. Example constructing
+ a :code:`std::string_view` ::
- .. function:: size_t unallocated_size() const
+ std::string_view * sv = arena.make<std::string_view>(pointer, n);
- Total number of bytes unallocated in the arena. Can be used to see the internal fragmentation.
+ .. function:: MemArena& freeze(size_t n)
- .. function:: bool contains (void *ptr) const
+ Stop allocating from existing internal memory blocks. These blocks are now "frozen". Further
+ allocation calls will cause new memory to be reserved.
- Returns whether or not a pointer is in the arena.
-
- .. function:: Block* newInternalBlock(size_t n, bool custom)
+ :arg:`n` is optional. If not provided, make the hint for the next internal memory reservation
+ to be large enough to hold all currently (now frozen) memory allocation. If :arg:`n` is
+ provided it is used as the reservation hint.
- Create a new internal block and returns a pointer to the block.
-
- .. member:: size_t arena_size
-
- Current generation size.
-
- .. member:: size_t total_alloc
-
- Number of bytes allocated out.
-
- .. member:: size_t next_block_size
+ .. function:: MemArena& thaw()
- Size of next generation.
+ Release all frozen internal memory blocks, destroying all frozen allocations.
- .. member:: std::shared_ptr<Block> generation
+ .. function:: MemArena& clear(size_t n)
- Pointer to the current generation.
+ Release all memory, destroying all allocations. The next memory reservation will be the size
+ of the allocated memory (frozen and not) at the time of the call to :func:`MemArena::clear`.
+ :arg:`n` is optional. If this is provided it is used as the hint for the next reserved block,
+ otherwise the hint is the size of all allocated memory.
- .. member:: std::shared_ptr<Block> current
+Internals
++++++++++
- Pointer to most recent internal block of memory.
+Allocated memory is tracked by two linked lists, one for current memory and the other for frozen
+memory. The latter is used only while the arena is frozen. Because a shared pointer is used for the
+link, the list can be de-allocated by clearing the head pointer in |MemArena|. This pattern is
+similar to that used by the :code:`IOBuffer` data blocks, and so those were considered for use as
+the internal memory allcation blocks. However, that would have required some non-trivial tweaks and,
+with the move away from internal allocation pools to memory support from libraries like "jemalloc",
+unlikely to provide any benefit.
diff --git a/lib/ts/MemArena.cc b/lib/ts/MemArena.cc
index 9b3db24..1646282 100644
--- a/lib/ts/MemArena.cc
+++ b/lib/ts/MemArena.cc
@@ -39,9 +39,18 @@ MemArena::Block::operator delete(void *ptr)
MemArena::BlockPtr
MemArena::make_block(size_t n)
{
+ // If there's no reservation hint, use the extent. This is transient because the hint is cleared.
+ if (_reserve_hint == 0) {
+ if (_active_reserved) {
+ _reserve_hint = _active_reserved;
+ } else if (_prev_allocated) {
+ _reserve_hint = _prev_allocated;
+ }
+ }
+
// If post-freeze or reserved, allocate at least that much.
- n = std::max<size_t>(n, next_block_size);
- next_block_size = 0; // did this, clear for next time.
+ n = std::max<size_t>(n, _reserve_hint);
+ _reserve_hint = 0; // did this, clear for next time.
// Add in overhead and round up to paragraph units.
n = Paragraph{round_up(n + ALLOC_HEADER_SIZE + sizeof(Block))};
// If a page or more, round up to page unit size and clip back to account for alloc header.
@@ -51,50 +60,43 @@ MemArena::make_block(size_t n)
// Allocate space for the Block instance and the request memory and construct a Block at the front.
// In theory this could use ::operator new(n) but this causes a size mismatch during ::operator delete.
- // Easier to use malloc and not carry a memory block size value around.
- return BlockPtr(new (::malloc(n)) Block(n - sizeof(Block)));
-}
-
-MemArena::MemArena(size_t n)
-{
- next_block_size = 0; // Don't use default size.
- current = this->make_block(n);
+ // Easier to use malloc and override @c delete.
+ auto free_space = n - sizeof(Block);
+ _active_reserved += free_space;
+ return BlockPtr(new (::malloc(n)) Block(free_space));
}
MemSpan
MemArena::alloc(size_t n)
{
MemSpan zret;
- current_alloc += n;
-
- if (!current) {
- current = this->make_block(n);
- zret = current->alloc(n);
- } else if (n > current->remaining()) { // too big, need another block
- if (next_block_size < n) {
- next_block_size = 2 * current->size;
- }
+ _active_allocated += n;
+
+ if (!_active) {
+ _active = this->make_block(n);
+ zret = _active->alloc(n);
+ } else if (n > _active->remaining()) { // too big, need another block
BlockPtr block = this->make_block(n);
// For the new @a current, pick the block which will have the most free space after taking
// the request space out of the new block.
zret = block->alloc(n);
- if (block->remaining() > current->remaining()) {
- block->next = current;
- current = block;
+ if (block->remaining() > _active->remaining()) {
+ block->next = _active;
+ _active = block;
#if defined(__clang_analyzer__)
// Defeat another clang analyzer false positive. Unit tests validate the code is correct.
ink_assert(current.use_count() > 1);
#endif
} else {
- block->next = current->next;
- current->next = block;
+ block->next = _active->next;
+ _active->next = block;
#if defined(__clang_analyzer__)
// Defeat another clang analyzer false positive. Unit tests validate the code is correct.
ink_assert(block.use_count() > 1);
#endif
}
} else {
- zret = current->alloc(n);
+ zret = _active->alloc(n);
}
return zret;
}
@@ -102,11 +104,15 @@ MemArena::alloc(size_t n)
MemArena &
MemArena::freeze(size_t n)
{
- prev = current;
- prev_alloc = current_alloc;
- current.reset();
- next_block_size = n ? n : current_alloc;
- current_alloc = 0;
+ _prev = _active;
+ _active.reset(); // it's in _prev now, start fresh.
+ // Update the meta data.
+ _prev_allocated = _active_allocated;
+ _active_allocated = 0;
+ _prev_reserved = _active_reserved;
+ _active_reserved = 0;
+
+ _reserve_hint = n;
return *this;
}
@@ -114,20 +120,20 @@ MemArena::freeze(size_t n)
MemArena &
MemArena::thaw()
{
- prev_alloc = 0;
- prev.reset();
+ _prev.reset();
+ _prev_reserved = _prev_allocated = 0;
return *this;
}
bool
MemArena::contains(const void *ptr) const
{
- for (Block *b = current.get(); b; b = b->next.get()) {
+ for (Block *b = _active.get(); b; b = b->next.get()) {
if (b->contains(ptr)) {
return true;
}
}
- for (Block *b = prev.get(); b; b = b->next.get()) {
+ for (Block *b = _prev.get(); b; b = b->next.get()) {
if (b->contains(ptr)) {
return true;
}
@@ -137,26 +143,13 @@ MemArena::contains(const void *ptr) const
}
MemArena &
-MemArena::clear()
+MemArena::clear(size_t n)
{
- prev.reset();
- prev_alloc = 0;
- current.reset();
- current_alloc = 0;
+ _reserve_hint = n ? n : _prev_allocated + _active_allocated;
+ _prev.reset();
+ _prev_reserved = _prev_allocated = 0;
+ _active.reset();
+ _active_reserved = _active_allocated = 0;
return *this;
}
-
-size_t
-MemArena::extent() const
-{
- size_t zret{0};
- Block *b;
- for (b = current.get(); b; b = b->next.get()) {
- zret += b->size;
- }
- for (b = prev.get(); b; b = b->next.get()) {
- zret += b->size;
- }
- return zret;
-};
diff --git a/lib/ts/MemArena.h b/lib/ts/MemArena.h
index ad10cee..fe00eaf 100644
--- a/lib/ts/MemArena.h
+++ b/lib/ts/MemArena.h
@@ -26,6 +26,7 @@
#include <new>
#include <mutex>
#include <memory>
+#include <utility>
#include <ts/MemSpan.h>
#include <ts/Scalar.h>
#include <tsconfig/IntrusivePtr.h>
@@ -33,29 +34,31 @@
/// Apache Traffic Server commons.
namespace ts
{
-/** MemArena is a memory arena for allocations.
+/** A memory arena.
- The intended use is for allocating many small chunks of memory - few, large allocations are best handled independently.
- The purpose is to amortize the cost of allocation of each chunk across larger allocations in a heap style. In addition the
- allocated memory is presumed to have similar lifetimes so that all of the memory in the arena can be de-allocatred en masse.
-
- A generation is essentially a block of memory. The normal workflow is to freeze() the current generation, alloc() a larger and
- newer generation, copy the contents of the previous generation to the new generation, and then thaw() the previous generation.
- Note that coalescence must be done by the caller because MemSpan will only give a reference to the underlying memory.
+ The intended use is for allocating many small chunks of memory - few, large allocations are best
+ handled through other mechanisms. The purpose is to amortize the cost of allocation of each
+ chunk across larger internal allocations ("reserving memory"). In addition the allocated memory
+ chunks are presumed to have similar lifetimes so all of the memory in the arena can be released
+ when the arena is destroyed.
*/
class MemArena
{
using self_type = MemArena; ///< Self reference type.
protected:
- struct Block;
+ struct Block; // Forward declare
using BlockPtr = ts::IntrusivePtr<Block>;
friend struct IntrusivePtrPolicy<Block>;
/** Simple internal arena block of memory. Maintains the underlying memory.
+ *
+ * Intrusive pointer is used to keep all of the memory in this single block. This struct is just
+ * the header on the full memory block allowing the raw memory and the meta data to be obtained
+ * in a single memory allocation.
*/
struct Block : public ts::IntrusivePtrCounter {
size_t size; ///< Actual block size.
size_t allocated{0}; ///< Current allocated (in use) bytes.
- BlockPtr next; ///< Previously allocated block list.
+ BlockPtr next; ///< List of previous blocks.
/** Construct to have @a n bytes of available storage.
*
@@ -64,14 +67,19 @@ protected:
* @param n The amount of storage.
*/
Block(size_t n);
+
/// Get the start of the data in this block.
char *data();
+
/// Get the start of the data in this block.
const char *data() const;
+
/// Amount of unallocated storage.
size_t remaining() const;
+
/// Span of unallocated storage.
MemSpan remnant();
+
/** Allocate @a n bytes from this block.
*
* @param n Number of bytes to allocate.
@@ -89,7 +97,7 @@ protected:
/** Override standard delete.
*
* This is required because the allocated memory size is larger than the class size which requires
- * passing different parameters to de-allocate the memory.
+ * calling @c free differently.
*
* @param ptr Memory to be de-allocated.
*/
@@ -97,66 +105,76 @@ protected:
};
public:
- /** Default constructor.
- * Construct with no memory.
- */
- MemArena();
- /** Construct with @a n bytes of storage.
+ /** Construct with reservation hint.
*
- * @param n Number of bytes in the initial block.
+ * No memory is initially reserved, but when memory is needed this will be done so at least
+ * @a n bytes of available memory is reserved.
+ *
+ * To pre-reserve call @c alloc(0), e.g.
+ * @code
+ * MemArena arena(512); // Make sure at least 512 bytes available in first block.
+ * arena.alloc(0); // Force allocation of first block.
+ * @endcode
+ *
+ * @param n Minimum number of available bytes in the first internally reserved block.
*/
- explicit MemArena(size_t n);
+ explicit MemArena(size_t n = DEFAULT_BLOCK_SIZE);
/** Allocate @a n bytes of storage.
- Returns a span of memory within the arena. alloc() is self expanding but DOES NOT self coalesce. This means
- that no matter the arena size, the caller will always be able to alloc() @a n bytes.
+ Returns a span of memory within the arena. alloc() is self expanding but DOES NOT self
+ coalesce. This means that no matter the arena size, the caller will always be able to alloc()
+ @a n bytes.
@param n number of bytes to allocate.
@return a MemSpan of the allocated memory.
*/
MemSpan alloc(size_t n);
- /** Adjust future block allocation size.
- This does not cause allocation, but instead makes a note of the size @a n and when a new block
- is needed, it will be at least @a n bytes. This is most useful for default constructed instances
- where the initial allocation should be delayed until use.
- @param n Minimum size of next allocated block.
- @return @a this
- */
- self_type &reserve(size_t n);
+ /** Allocate and initialize a block of memory.
+
+ The template type specifies the type to create and any arguments are forwarded to the constructor. Example:
+ @code
+ struct Thing { ... };
+ Thing* thing = arena.make<Thing>(...constructor args...);
+ @endcode
- /** Freeze memory allocation.
+ Do @b not call @c delete an object created this way - that will attempt to free the memory and break. A
+ destructor may be invoked explicitly but the point of this class is that no object in it needs to be
+ deleted, the memory will all be reclaimed when the Arena is destroyed. In general it is a bad idea
+ to make objects in the Arena that own memory that is not also in the Arena.
+ */
+ template <typename T, typename... Args> T *make(Args &&... args);
- Will "freeze" a generation of memory. Any memory previously allocated can still be used. This is an
- important distinction as freeze does not mean that the memory is immutable, only that subsequent allocations
- will be in a new generation.
+ /** Freeze reserved memory.
- If @a n == 0, the first block of next generation will be large enough to hold all existing allocations.
- This enables coalescence for locality of reference.
+ All internal memory blocks are frozen and will not be involved in future allocations. Subsequent
+ allocation will reserve new internal blocks. By default the first reserved block will be large
+ enough to contain all frozen memory. If this is not correct a different target can be
+ specified as @a n.
- @param n Number of bytes for new generation.
+ @param n Target number of available bytes in the next reserved internal block.
@return @c *this
*/
MemArena &freeze(size_t n = 0);
- /** Unfreeze memory allocation, discard previously frozen memory.
-
- Will "thaw" away any previously frozen generations. Any generation that is not the current generation is considered
- frozen because there is no way to allocate in any of those memory blocks. thaw() is the only mechanism for deallocating
- memory in the arena (other than destroying the arena itself). Thawing away previous generations means that all spans
- of memory allocated in those generations are no longer safe to use.
-
- @return @c *this
+ /** Unfreeze arena.
+ *
+ * Frozen memory is released.
+ *
+ * @return @c *this
*/
- MemArena &thaw();
+ self_type &thaw();
/** Release all memory.
- Empties the entire arena and deallocates all underlying memory. Next block size will be equal to the sum of all
- allocations before the call to empty.
+ Empties the entire arena and deallocates all underlying memory. The hint for the next reservered block size will
+ be @a n if @a n is not zero, otherwise it will be the sum of all allocations when this method was called.
+
+ @return @c *this
+
*/
- MemArena &clear();
+ MemArena &clear(size_t n = 0);
/// @returns the memory allocated in the generation.
size_t size() const;
@@ -180,11 +198,9 @@ public:
/** Total memory footprint, including wasted space.
* @return Total memory footprint.
*/
- size_t extent() const;
+ size_t reserved_size() const;
protected:
- /// creates a new @c Block with at least @n free space.
-
/** Internally allocates a new block of memory of size @a n bytes.
*
* @param n Size of block to allocate.
@@ -199,14 +215,19 @@ protected:
/// Initial block size to allocate if not specified via API.
static constexpr size_t DEFAULT_BLOCK_SIZE = Page::SCALE - Paragraph{round_up(ALLOC_HEADER_SIZE + sizeof(Block))};
- size_t current_alloc = 0; ///< Total allocations in the active generation.
+ size_t _active_allocated = 0; ///< Total allocations in the active generation.
+ size_t _active_reserved = 0; ///< Total current reserved memory.
/// Total allocations in the previous generation. This is only non-zero while the arena is frozen.
- size_t prev_alloc = 0;
+ size_t _prev_allocated = 0;
+ /// Total frozen reserved memory.
+ size_t _prev_reserved = 0;
- size_t next_block_size = DEFAULT_BLOCK_SIZE; ///< Next internal block size
+ /// Minimum free space needed in the next allocated block.
+ /// This is not zero iff @c reserve was called.
+ size_t _reserve_hint = 0;
- BlockPtr prev; ///< Previous generation.
- BlockPtr current; ///< Head of allocations list. Allocate from this.
+ BlockPtr _prev; ///< Previous generation, frozen memory.
+ BlockPtr _active; ///< Current generation. Allocate here.
};
// Implementation
@@ -247,7 +268,14 @@ MemArena::Block::alloc(size_t n)
return zret;
}
-inline MemArena::MemArena() {}
+template <typename T, typename... Args>
+T *
+MemArena::make(Args &&... args)
+{
+ return new (this->alloc(sizeof(T)).data()) T(std::forward<Args>(args)...);
+}
+
+inline MemArena::MemArena(size_t n) : _reserve_hint(n) {}
inline MemSpan
MemArena::Block::remnant()
@@ -258,32 +286,31 @@ MemArena::Block::remnant()
inline size_t
MemArena::size() const
{
- return current_alloc;
+ return _active_allocated;
}
inline size_t
MemArena::allocated_size() const
{
- return prev_alloc + current_alloc;
-}
-
-inline MemArena &
-MemArena::reserve(size_t n)
-{
- next_block_size = n;
- return *this;
+ return _prev_allocated + _active_allocated;
}
inline size_t
MemArena::remaining() const
{
- return current ? current->remaining() : 0;
+ return _active ? _active->remaining() : 0;
}
inline MemSpan
MemArena::remnant() const
{
- return current ? current->remnant() : MemSpan{};
+ return _active ? _active->remnant() : MemSpan{};
+}
+
+inline size_t
+MemArena::reserved_size() const
+{
+ return _active_reserved + _prev_reserved;
}
} // namespace ts
diff --git a/lib/ts/unit-tests/test_MemArena.cc b/lib/ts/unit-tests/test_MemArena.cc
index 6e358b4..18d2dad 100644
--- a/lib/ts/unit-tests/test_MemArena.cc
+++ b/lib/ts/unit-tests/test_MemArena.cc
@@ -23,15 +23,20 @@
#include <catch.hpp>
+#include <string_view>
#include <ts/MemArena.h>
using ts::MemSpan;
using ts::MemArena;
+using namespace std::literals;
TEST_CASE("MemArena generic", "[libts][MemArena]")
{
ts::MemArena arena{64};
REQUIRE(arena.size() == 0);
- REQUIRE(arena.extent() >= 64);
+ REQUIRE(arena.reserved_size() == 0);
+ arena.alloc(0);
+ REQUIRE(arena.size() == 0);
+ REQUIRE(arena.reserved_size() >= 64);
ts::MemSpan span1 = arena.alloc(32);
REQUIRE(span1.size() == 32);
@@ -42,9 +47,9 @@ TEST_CASE("MemArena generic", "[libts][MemArena]")
REQUIRE(span1.data() != span2.data());
REQUIRE(arena.size() == 64);
- auto extent{arena.extent()};
+ auto extent{arena.reserved_size()};
span1 = arena.alloc(128);
- REQUIRE(extent < arena.extent());
+ REQUIRE(extent < arena.reserved_size());
}
TEST_CASE("MemArena freeze and thaw", "[libts][MemArena]")
@@ -53,45 +58,75 @@ TEST_CASE("MemArena freeze and thaw", "[libts][MemArena]")
MemSpan span1{arena.alloc(1024)};
REQUIRE(span1.size() == 1024);
REQUIRE(arena.size() == 1024);
+ REQUIRE(arena.reserved_size() >= 1024);
arena.freeze();
REQUIRE(arena.size() == 0);
REQUIRE(arena.allocated_size() == 1024);
- REQUIRE(arena.extent() >= 1024);
+ REQUIRE(arena.reserved_size() >= 1024);
arena.thaw();
REQUIRE(arena.size() == 0);
- REQUIRE(arena.extent() == 0);
+ REQUIRE(arena.allocated_size() == 0);
+ REQUIRE(arena.reserved_size() == 0);
- arena.reserve(2000);
+ span1 = arena.alloc(1024);
+ arena.freeze();
+ auto extent{arena.reserved_size()};
arena.alloc(512);
- arena.alloc(1024);
- REQUIRE(arena.extent() >= 1536);
- REQUIRE(arena.extent() < 3000);
- auto extent = arena.extent();
+ REQUIRE(arena.reserved_size() > extent); // new extent should be bigger.
+ arena.thaw();
+ REQUIRE(arena.size() == 512);
+ REQUIRE(arena.reserved_size() >= 1024);
+
+ arena.clear();
+ REQUIRE(arena.size() == 0);
+ REQUIRE(arena.reserved_size() == 0);
+ span1 = arena.alloc(262144);
arena.freeze();
+ extent = arena.reserved_size();
arena.alloc(512);
- REQUIRE(arena.extent() > extent); // new extent should be bigger.
+ REQUIRE(arena.reserved_size() > extent); // new extent should be bigger.
arena.thaw();
REQUIRE(arena.size() == 512);
- REQUIRE(arena.extent() > 1536);
+ REQUIRE(arena.reserved_size() >= 262144);
arena.clear();
- REQUIRE(arena.size() == 0);
- REQUIRE(arena.extent() == 0);
+
+ span1 = arena.alloc(262144);
+ extent = arena.reserved_size();
+ arena.freeze();
+ for (int i = 0; i < 262144 / 512; ++i)
+ arena.alloc(512);
+ REQUIRE(arena.reserved_size() > extent); // Bigger while frozen memory is still around.
+ arena.thaw();
+ REQUIRE(arena.size() == 262144);
+ REQUIRE(arena.reserved_size() == extent); // should be identical to before freeze.
arena.alloc(512);
arena.alloc(768);
arena.freeze(32000);
arena.thaw();
- arena.alloc(1);
- REQUIRE(arena.extent() >= 32000);
+ arena.alloc(0);
+ REQUIRE(arena.reserved_size() >= 32000);
+ REQUIRE(arena.reserved_size() < 2 * 32000);
}
TEST_CASE("MemArena helper", "[libts][MemArena]")
{
+ struct Thing {
+ int ten{10};
+ std::string name{"name"};
+
+ Thing() {}
+ Thing(int x) : ten(x) {}
+ Thing(std::string const &s) : name(s) {}
+ Thing(int x, std::string_view s) : ten(x), name(s) {}
+ Thing(std::string const &s, int x) : ten(x), name(s) {}
+ };
+
ts::MemArena arena{256};
REQUIRE(arena.size() == 0);
ts::MemSpan s = arena.alloc(56);
@@ -115,6 +150,31 @@ TEST_CASE("MemArena helper", "[libts][MemArena]")
arena.thaw();
REQUIRE(!arena.contains((char *)ptr));
REQUIRE(arena.contains((char *)ptr2));
+
+ Thing *thing_one{arena.make<Thing>()};
+
+ REQUIRE(thing_one->ten == 10);
+ REQUIRE(thing_one->name == "name");
+
+ thing_one = arena.make<Thing>(17, "bob"sv);
+
+ REQUIRE(thing_one->name == "bob");
+ REQUIRE(thing_one->ten == 17);
+
+ thing_one = arena.make<Thing>("Dave", 137);
+
+ REQUIRE(thing_one->name == "Dave");
+ REQUIRE(thing_one->ten == 137);
+
+ thing_one = arena.make<Thing>(9999);
+
+ REQUIRE(thing_one->ten == 9999);
+ REQUIRE(thing_one->name == "name");
+
+ thing_one = arena.make<Thing>("Persia");
+
+ REQUIRE(thing_one->ten == 10);
+ REQUIRE(thing_one->name == "Persia");
}
TEST_CASE("MemArena large alloc", "[libts][MemArena]")
@@ -170,17 +230,16 @@ TEST_CASE("MemArena block allocation", "[libts][MemArena]")
TEST_CASE("MemArena full blocks", "[libts][MemArena]")
{
// couple of large allocations - should be exactly sized in the generation.
- ts::MemArena arena;
size_t init_size = 32000;
+ ts::MemArena arena(init_size);
- arena.reserve(init_size);
MemSpan m1{arena.alloc(init_size - 64)};
MemSpan m2{arena.alloc(32000)};
MemSpan m3{arena.alloc(64000)};
REQUIRE(arena.remaining() >= 64);
- REQUIRE(arena.extent() > 32000 + 64000 + init_size);
- REQUIRE(arena.extent() < 2 * (32000 + 64000 + init_size));
+ REQUIRE(arena.reserved_size() > 32000 + 64000 + init_size);
+ REQUIRE(arena.reserved_size() < 2 * (32000 + 64000 + init_size));
// Let's see if that memory is really there.
memset(m1.data(), 0xa5, m1.size());