xref: /trafficserver/include/tscore/MemArena.h (revision 5051e299)
1 /** @file
2 
3     Memory arena for allocations
4 
5     @section license License
6 
7     Licensed to the Apache Software Foundation (ASF) under one
8     or more contributor license agreements.  See the NOTICE file
9     distributed with this work for additional information
10     regarding copyright ownership.  The ASF licenses this file
11     to you under the Apache License, Version 2.0 (the
12     "License"); you may not use this file except in compliance
13     with the License.  You may obtain a copy of the License at
14 
15     http://www.apache.org/licenses/LICENSE-2.0
16 
17     Unless required by applicable law or agreed to in writing, software
18     distributed under the License is distributed on an "AS IS" BASIS,
19     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20     See the License for the specific language governing permissions and
21     limitations under the License.
22  */
23 
24 #pragma once
25 
26 #include <new>
27 #include <mutex>
28 #include <memory>
29 #include <utility>
30 #include "tscpp/util/MemSpan.h"
31 #include "tscore/Scalar.h"
32 #include "tscore/IntrusivePtr.h"
33 
34 /// Apache Traffic Server commons.
35 namespace ts
36 {
37 /** A memory arena.
38 
39     The intended use is for allocating many small chunks of memory - few, large allocations are best
40     handled through other mechanisms. The purpose is to amortize the cost of allocation of each
41     chunk across larger internal allocations ("reserving memory"). In addition the allocated memory
42     chunks are presumed to have similar lifetimes so all of the memory in the arena can be released
43     when the arena is destroyed.
44  */
45 class MemArena
46 {
47   using self_type = MemArena; ///< Self reference type.
48 protected:
49   struct Block; // Forward declare
50   using BlockPtr = ts::IntrusivePtr<Block>;
51   friend struct IntrusivePtrPolicy<Block>;
52   /** Simple internal arena block of memory. Maintains the underlying memory.
53    *
54    * Intrusive pointer is used to keep all of the memory in this single block. This struct is just
55    * the header on the full memory block allowing the raw memory and the meta data to be obtained
56    * in a single memory allocation.
57    */
58   struct Block : public ts::IntrusivePtrCounter {
59     size_t size;         ///< Actual block size.
60     size_t allocated{0}; ///< Current allocated (in use) bytes.
61     BlockPtr next;       ///< List of previous blocks.
62 
63     /** Construct to have @a n bytes of available storage.
64      *
65      * Note this is descriptive - this presumes use via placement new and the size value describes
66      * memory already allocated immediately after this instance.
67      * @param n The amount of storage.
68      */
69     Block(size_t n);
70 
71     /// Get the start of the data in this block.
72     char *data();
73 
74     /// Get the start of the data in this block.
75     const char *data() const;
76 
77     /// Amount of unallocated storage.
78     size_t remaining() const;
79 
80     /// Span of unallocated storage.
81     MemSpan<void> remnant();
82 
83     /** Allocate @a n bytes from this block.
84      *
85      * @param n Number of bytes to allocate.
86      * @return The span of memory allocated.
87      */
88     MemSpan<void> alloc(size_t n);
89 
90     /** Check if the byte at address @a ptr is in this block.
91      *
92      * @param ptr Address of byte to check.
93      * @return @c true if @a ptr is in this block, @c false otherwise.
94      */
95     bool contains(const void *ptr) const;
96 
97     /** Override standard delete.
98      *
99      * This is required because the allocated memory size is larger than the class size which requires
100      * calling @c free differently.
101      *
102      * @param ptr Memory to be de-allocated.
103      */
104     static void operator delete(void *ptr);
105   };
106 
107 public:
108   /** Construct with reservation hint.
109    *
110    * No memory is initially reserved, but when memory is needed this will be done so at least
111    * @a n bytes of available memory is reserved.
112    *
113    * To pre-reserve call @c alloc(0), e.g.
114    * @code
115    * MemArena arena(512); // Make sure at least 512 bytes available in first block.
116    * arena.alloc(0); // Force allocation of first block.
117    * @endcode
118    *
119    * @param n Minimum number of available bytes in the first internally reserved block.
120    */
121   explicit MemArena(size_t n = DEFAULT_BLOCK_SIZE);
122 
123   /** Allocate @a n bytes of storage.
124 
125       Returns a span of memory within the arena. alloc() is self expanding but DOES NOT self
126       coalesce. This means that no matter the arena size, the caller will always be able to alloc()
127       @a n bytes.
128 
129       @param n number of bytes to allocate.
130       @return a MemSpan of the allocated memory.
131    */
132   MemSpan<void> alloc(size_t n);
133 
134   /** Allocate and initialize a block of memory.
135 
136       The template type specifies the type to create and any arguments are forwarded to the constructor. Example:
137       @code
138       struct Thing { ... };
139       Thing* thing = arena.make<Thing>(...constructor args...);
140       @endcode
141 
142       Do @b not call @c delete an object created this way - that will attempt to free the memory and break. A
143       destructor may be invoked explicitly but the point of this class is that no object in it needs to be
144       deleted, the memory will all be reclaimed when the Arena is destroyed. In general it is a bad idea
145       to make objects in the Arena that own memory that is not also in the Arena.
146   */
147   template <typename T, typename... Args> T *make(Args &&... args);
148 
149   /** Freeze reserved memory.
150 
151       All internal memory blocks are frozen and will not be involved in future allocations. Subsequent
152       allocation will reserve new internal blocks. By default the first reserved block will be large
153       enough to contain all frozen memory. If this is not correct a different target can be
154       specified as @a n.
155 
156       @param n Target number of available bytes in the next reserved internal block.
157       @return @c *this
158    */
159   MemArena &freeze(size_t n = 0);
160 
161   /** Unfreeze arena.
162    *
163    * Frozen memory is released.
164    *
165    * @return @c *this
166    */
167   self_type &thaw();
168 
169   /** Release all memory.
170 
171       Empties the entire arena and deallocates all underlying memory. The hint for the next reserved block size will
172       be @a n if @a n is not zero, otherwise it will be the sum of all allocations when this method was called.
173 
174       @return @c *this
175 
176    */
177   MemArena &clear(size_t n = 0);
178 
179   /// @returns the memory allocated in the generation.
180   size_t size() const;
181 
182   /// @returns the @c remaining space within the generation.
183   size_t remaining() const;
184 
185   /// @returns the remaining contiguous space in the active generation.
186   MemSpan<void> remnant() const;
187 
188   /// @returns the total number of bytes allocated within the arena.
189   size_t allocated_size() const;
190 
191   /** Check if a the byte at @a ptr is in memory owned by this arena.
192    *
193    * @param ptr Address of byte to check.
194    * @return @c true if the byte at @a ptr is in the arena, @c false if not.
195    */
196   bool contains(const void *ptr) const;
197 
198   /** Total memory footprint, including wasted space.
199    * @return Total memory footprint.
200    */
201   size_t reserved_size() const;
202 
203 protected:
204   /** Internally allocates a new block of memory of size @a n bytes.
205    *
206    * @param n Size of block to allocate.
207    * @return
208    */
209   BlockPtr make_block(size_t n);
210 
211   using Page      = ts::Scalar<4096>; ///< Size for rounding block sizes.
212   using Paragraph = ts::Scalar<16>;   ///< Minimum unit of memory allocation.
213 
214   static constexpr size_t ALLOC_HEADER_SIZE = 16; ///< Guess of overhead of @c malloc
215   /// Initial block size to allocate if not specified via API.
216   static constexpr size_t DEFAULT_BLOCK_SIZE = Page::SCALE - Paragraph{round_up(ALLOC_HEADER_SIZE + sizeof(Block))};
217 
218   size_t _active_allocated = 0; ///< Total allocations in the active generation.
219   size_t _active_reserved  = 0; ///< Total current reserved memory.
220   /// Total allocations in the previous generation. This is only non-zero while the arena is frozen.
221   size_t _prev_allocated = 0;
222   /// Total frozen reserved memory.
223   size_t _prev_reserved = 0;
224 
225   /// Minimum free space needed in the next allocated block.
226   /// This is not zero iff @c reserve was called.
227   size_t _reserve_hint = 0;
228 
229   BlockPtr _prev;   ///< Previous generation, frozen memory.
230   BlockPtr _active; ///< Current generation. Allocate here.
231 };
232 
233 // Implementation
234 
Block(size_t n)235 inline MemArena::Block::Block(size_t n) : size(n) {}
236 
237 inline char *
data()238 MemArena::Block::data()
239 {
240   return reinterpret_cast<char *>(this + 1);
241 }
242 
243 inline const char *
data() const244 MemArena::Block::data() const
245 {
246   return reinterpret_cast<const char *>(this + 1);
247 }
248 
249 inline bool
contains(const void * ptr) const250 MemArena::Block::contains(const void *ptr) const
251 {
252   const char *base = this->data();
253   return base <= ptr && ptr < base + size;
254 }
255 
256 inline size_t
remaining() const257 MemArena::Block::remaining() const
258 {
259   return size - allocated;
260 }
261 
262 inline MemSpan<void>
alloc(size_t n)263 MemArena::Block::alloc(size_t n)
264 {
265   ink_assert(n <= this->remaining());
266   MemSpan<void> zret = this->remnant().prefix(n);
267   allocated += n;
268   return zret;
269 }
270 
271 template <typename T, typename... Args>
272 T *
make(Args &&...args)273 MemArena::make(Args &&... args)
274 {
275   return new (this->alloc(sizeof(T)).data()) T(std::forward<Args>(args)...);
276 }
277 
MemArena(size_t n)278 inline MemArena::MemArena(size_t n) : _reserve_hint(n) {}
279 
280 inline MemSpan<void>
remnant()281 MemArena::Block::remnant()
282 {
283   return {this->data() + allocated, this->remaining()};
284 }
285 
286 inline size_t
size() const287 MemArena::size() const
288 {
289   return _active_allocated;
290 }
291 
292 inline size_t
allocated_size() const293 MemArena::allocated_size() const
294 {
295   return _prev_allocated + _active_allocated;
296 }
297 
298 inline size_t
remaining() const299 MemArena::remaining() const
300 {
301   return _active ? _active->remaining() : 0;
302 }
303 
304 inline MemSpan<void>
remnant() const305 MemArena::remnant() const
306 {
307   return _active ? _active->remnant() : MemSpan<void>{};
308 }
309 
310 inline size_t
reserved_size() const311 MemArena::reserved_size() const
312 {
313   return _active_reserved + _prev_reserved;
314 }
315 
316 } // namespace ts
317