my_alloc.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413
  1. /* Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights reserved.
  2. This program is free software; you can redistribute it and/or modify
  3. it under the terms of the GNU General Public License, version 2.0,
  4. as published by the Free Software Foundation.
  5. This program is also distributed with certain software (including
  6. but not limited to OpenSSL) that is licensed under separate terms,
  7. as designated in a particular file or component or in included license
  8. documentation. The authors of MySQL hereby grant you an additional
  9. permission to link the program and your derivative works with the
  10. separately licensed software that they have included with MySQL.
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. GNU General Public License, version 2.0, for more details.
  15. You should have received a copy of the GNU General Public License
  16. along with this program; if not, write to the Free Software
  17. Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
  18. /**
  19. * @file include/my_alloc.h
  20. *
  21. * This file follows Google coding style, except for the name MEM_ROOT (which is
  22. * kept for historical reasons).
  23. */
  24. #ifndef INCLUDE_MY_ALLOC_H_
  25. #define INCLUDE_MY_ALLOC_H_
  26. #include <string.h>
  27. #include <memory>
  28. #include <new>
  29. #include <type_traits>
  30. #include <utility>
  31. #include "my_compiler.h"
  32. #include "my_dbug.h"
  33. #include "my_inttypes.h"
  34. #include "my_pointer_arithmetic.h"
  35. #include "mysql/psi/psi_memory.h"
  36. /**
  37. * The MEM_ROOT is a simple arena, where allocations are carved out of
  38. * larger blocks. Using an arena over plain malloc gives you two main
  39. * advantages:
  40. *
  41. * * Allocation is very cheap (only a few CPU cycles on the fast path).
  42. * * You do not need to keep track of which memory you have allocated,
  43. * as it will all be freed when the arena is destroyed.
  44. *
  45. * Thus, if you need to do many small allocations that all are to have
  46. * roughly the same lifetime, the MEM_ROOT is probably a good choice.
  47. * The flip side is that _no_ memory is freed until the arena is destroyed,
  48. * and no destructors are run (although you can run them manually yourself).
  49. *
  50. *
  51. * This specific implementation works by allocating exponentially larger blocks
  52. * each time it needs more memory (generally increasing them by 50%), which
  53. * guarantees O(1) total calls to malloc and free. Only one free block is
  54. * ever used; as soon as there's an allocation that comes in that doesn't fit,
  55. * that block is stored away and never allocated from again. (There's an
  56. * exception for allocations larger than the block size; see #AllocSlow
  57. * for details.)
  58. *
  59. * The MEM_ROOT is thread-compatible but not thread-safe. This means you cannot
  60. * use the same instance from multiple threads at the same time without external
  61. * synchronization, but you can use different MEM_ROOTs concurrently in
  62. * different threads.
  63. *
  64. * For C compatibility reasons, MEM_ROOT is a struct, even though it is
  65. * logically a class and follows the style guide for classes.
  66. */
  67. struct MEM_ROOT {
  68. private:
  69. struct Block {
  70. Block *prev{nullptr}; /** Previous block; used for freeing. */
  71. };
  72. public:
  73. MEM_ROOT() : MEM_ROOT(0, 512) {} // 0 = PSI_NOT_INSTRUMENTED.
  74. MEM_ROOT(PSI_memory_key key, size_t block_size)
  75. : m_block_size(block_size),
  76. m_orig_block_size(block_size),
  77. m_psi_key(key) {}
  78. // MEM_ROOT is movable but not copyable.
  79. MEM_ROOT(const MEM_ROOT &) = delete;
  80. MEM_ROOT(MEM_ROOT &&other)
  81. noexcept
  82. : m_current_block(other.m_current_block),
  83. m_current_free_start(other.m_current_free_start),
  84. m_current_free_end(other.m_current_free_end),
  85. m_block_size(other.m_block_size),
  86. m_orig_block_size(other.m_orig_block_size),
  87. m_max_capacity(other.m_max_capacity),
  88. m_allocated_size(other.m_allocated_size),
  89. m_error_for_capacity_exceeded(other.m_error_for_capacity_exceeded),
  90. m_error_handler(other.m_error_handler),
  91. m_psi_key(other.m_psi_key) {
  92. other.m_current_block = nullptr;
  93. other.m_allocated_size = 0;
  94. other.m_block_size = m_orig_block_size;
  95. other.m_current_free_start = &s_dummy_target;
  96. other.m_current_free_end = &s_dummy_target;
  97. }
  98. MEM_ROOT &operator=(const MEM_ROOT &) = delete;
  99. MEM_ROOT &operator=(MEM_ROOT &&other) noexcept {
  100. Clear();
  101. ::new (this) MEM_ROOT(std::move(other));
  102. return *this;
  103. }
  104. ~MEM_ROOT() { Clear(); }
  105. /**
  106. * Allocate memory. Will return nullptr if there's not enough memory,
  107. * or if the maximum capacity is reached.
  108. *
  109. * Note that a zero-length allocation can return _any_ pointer, including
  110. * nullptr or a pointer that has been given out before. The current
  111. * implementation takes some pains to make sure we never return nullptr
  112. * (although it might return a bogus pointer), since there is code that
  113. * assumes nullptr always means “out of memory”, but you should not rely on
  114. * it, as it may change in the future.
  115. *
  116. * The returned pointer will always be 8-aligned.
  117. */
  118. void *Alloc(size_t length) MY_ATTRIBUTE((malloc)) {
  119. length = ALIGN_SIZE(length);
  120. // Skip the straight path if simulating OOM; it should always fail.
  121. DBUG_EXECUTE_IF("simulate_out_of_memory", return AllocSlow(length););
  122. // Fast path, used in the majority of cases. It would be faster here
  123. // (saving one register due to CSE) to instead test
  124. //
  125. // m_current_free_start + length <= m_current_free_end
  126. //
  127. // but it would invoke undefined behavior, and in particular be prone
  128. // to wraparound on 32-bit platforms.
  129. if (static_cast<size_t>(m_current_free_end - m_current_free_start) >=
  130. length) {
  131. void *ret = m_current_free_start;
  132. m_current_free_start += length;
  133. return ret;
  134. }
  135. return AllocSlow(length);
  136. }
  137. /**
  138. Allocate “num” objects of type T, and default-construct them.
  139. If the constructor throws an exception, behavior is undefined.
  140. We don't use new[], as it can put extra data in front of the array.
  141. */
  142. template <class T>
  143. T *ArrayAlloc(size_t num) {
  144. static_assert(alignof(T) <= 8, "MEM_ROOT only returns 8-aligned memory.");
  145. if (num * sizeof(T) < num) {
  146. // Overflow.
  147. return nullptr;
  148. }
  149. T *ret = static_cast<T *>(Alloc(num * sizeof(T)));
  150. // Default-construct all elements. For primitive types like int,
  151. // the entire loop will be optimized away.
  152. for (size_t i = 0; i < num; ++i) {
  153. new (&ret[i]) T;
  154. }
  155. return ret;
  156. }
  157. /**
  158. * Claim all the allocated memory for the current thread in the performance
  159. * schema. Use when transferring responsibility for a MEM_ROOT from one thread
  160. * to another.
  161. */
  162. void Claim();
  163. /**
  164. * Deallocate all the RAM used. The MEM_ROOT itself continues to be valid,
  165. * so you can make new calls to Alloc() afterwards.
  166. * @note
  167. * One can call this function either with a MEM_ROOT initialized with the
  168. * constructor, or with one that's memset() to all zeros.
  169. * It's also safe to call this multiple times with the same mem_root.
  170. */
  171. void Clear();
  172. /**
  173. * Similar to Clear(), but anticipates that the block will be reused for
  174. * further allocations. This means that even though all the data is gone,
  175. * one memory block (typically the largest allocated) will be kept and
  176. * made immediately available for calls to Alloc() without having to go to the
  177. * OS for new memory. This can yield performance gains if you use the same
  178. * MEM_ROOT many times. Also, the block size is not reset.
  179. */
  180. void ClearForReuse();
  181. /**
  182. Whether the constructor has run or not.
  183. This exists solely to support legacy code that memset()s the MEM_ROOT to
  184. all zeros, which wants to distinguish between that state and a properly
  185. initialized MEM_ROOT. If you do not run the constructor _nor_ do memset(),
  186. you are invoking undefined behavior.
  187. */
  188. bool inited() const { return m_block_size != 0; }
  189. /**
  190. * Set maximum capacity for this MEM_ROOT. Whenever the MEM_ROOT has
  191. * allocated more than this (not including overhead), and the free block
  192. * is empty, future allocations will fail.
  193. *
  194. * @param max_capacity Maximum capacity this mem_root can hold
  195. */
  196. void set_max_capacity(size_t max_capacity) { m_max_capacity = max_capacity; }
  197. /**
  198. * Return maximum capacity for this MEM_ROOT.
  199. */
  200. size_t get_max_capacity() const { return m_max_capacity; }
  201. /**
  202. * Enable/disable error reporting for exceeding the maximum capacity.
  203. * If error reporting is enabled, an error is flagged to indicate that the
  204. * capacity is exceeded. However, allocation will still happen for the
  205. * requested memory.
  206. *
  207. * @param report_error whether the error should be reported
  208. */
  209. void set_error_for_capacity_exceeded(bool report_error) {
  210. m_error_for_capacity_exceeded = report_error;
  211. }
  212. /**
  213. * Return whether error is to be reported when
  214. * maximum capacity exceeds for MEM_ROOT.
  215. */
  216. bool get_error_for_capacity_exceeded() const {
  217. return m_error_for_capacity_exceeded;
  218. }
  219. /**
  220. * Set the error handler on memory allocation failure (or nullptr for none).
  221. * The error handler is called called whenever my_malloc() failed to allocate
  222. * more memory from the OS (which causes my_alloc() to return nullptr).
  223. */
  224. void set_error_handler(void (*error_handler)(void)) {
  225. m_error_handler = error_handler;
  226. }
  227. /**
  228. * Amount of memory we have allocated from the operating system, not including
  229. * overhead.
  230. */
  231. size_t allocated_size() const { return m_allocated_size; }
  232. /**
  233. * Set the desired size of the next block to be allocated. Note that future
  234. * allocations
  235. * will grow in size over this, although a Clear() will reset the size again.
  236. */
  237. void set_block_size(size_t block_size) {
  238. m_block_size = m_orig_block_size = block_size;
  239. }
  240. private:
  241. /**
  242. * Something to point on that exists solely to never return nullptr
  243. * from Alloc(0).
  244. */
  245. static char s_dummy_target;
  246. /**
  247. Allocate a new block of the given length (plus overhead for the block
  248. header).
  249. */
  250. Block *AllocBlock(size_t length);
  251. /** Allocate memory that doesn't fit into the current free block. */
  252. void *AllocSlow(size_t length);
  253. /** Free all blocks in a linked list, starting at the given block. */
  254. static void FreeBlocks(Block *start);
  255. /** The current block we are giving out memory from. nullptr if none. */
  256. Block *m_current_block = nullptr;
  257. /** Start (inclusive) of the current free block. */
  258. char *m_current_free_start = &s_dummy_target;
  259. /** End (exclusive) of the current free block. */
  260. char *m_current_free_end = &s_dummy_target;
  261. /** Size of the _next_ block we intend to allocate. */
  262. size_t m_block_size;
  263. /** The original block size the user asked for on construction. */
  264. size_t m_orig_block_size;
  265. /**
  266. Maximum amount of memory this MEM_ROOT can hold. A value of 0
  267. implies there is no limit.
  268. */
  269. size_t m_max_capacity = 0;
  270. /**
  271. * Total allocated size for this MEM_ROOT. Does not include overhead
  272. * for block headers or malloc overhead, since especially the latter
  273. * is impossible to quantify portably.
  274. */
  275. size_t m_allocated_size = 0;
  276. /** If enabled, exceeding the capacity will lead to a my_error() call. */
  277. bool m_error_for_capacity_exceeded = false;
  278. void (*m_error_handler)(void) = nullptr;
  279. PSI_memory_key m_psi_key = 0;
  280. };
  281. // Legacy C thunks. Do not use in new code.
  282. static inline void init_alloc_root(PSI_memory_key key, MEM_ROOT *root,
  283. size_t block_size, size_t) {
  284. ::new (root) MEM_ROOT(key, block_size);
  285. }
  286. void free_root(MEM_ROOT *root, myf flags);
  287. /**
  288. * Allocate an object of the given type. Use like this:
  289. *
  290. * Foo *foo = new (mem_root) Foo();
  291. *
  292. * Note that unlike regular operator new, this will not throw exceptions.
  293. * However, it can return nullptr if the capacity of the MEM_ROOT has been
  294. * reached. This is allowed since it is not a replacement for global operator
  295. * new, and thus isn't used automatically by e.g. standard library containers.
  296. *
  297. * TODO: This syntax is confusing in that it could look like allocating
  298. * a MEM_ROOT using regular placement new. We should make a less ambiguous
  299. * syntax, e.g. new (On(mem_root)) Foo().
  300. */
  301. inline void *operator new(
  302. size_t size, MEM_ROOT *mem_root,
  303. const std::nothrow_t &arg MY_ATTRIBUTE((unused)) = std::nothrow) noexcept {
  304. return mem_root->Alloc(size);
  305. }
  306. inline void *operator new[](
  307. size_t size, MEM_ROOT *mem_root,
  308. const std::nothrow_t &arg MY_ATTRIBUTE((unused)) = std::nothrow) noexcept {
  309. return mem_root->Alloc(size);
  310. }
  311. inline void operator delete(void *, MEM_ROOT *,
  312. const std::nothrow_t &)noexcept {
  313. /* never called */
  314. }
  315. inline void operator delete[](void *, MEM_ROOT *,
  316. const std::nothrow_t &) noexcept {
  317. /* never called */
  318. }
  319. template <class T>
  320. inline void destroy(T *ptr) {
  321. if (ptr != nullptr) ptr->~T();
  322. }
  323. template <class T>
  324. inline void destroy_array(T *ptr, size_t count) {
  325. static_assert(!std::is_pointer<T>::value,
  326. "You're trying to destroy an array of pointers, "
  327. "not an array of objects. This is probably not "
  328. "what you intended.");
  329. if (ptr != nullptr) {
  330. for (size_t i = 0; i < count; ++i) destroy(&ptr[i]);
  331. }
  332. }
  333. /*
  334. * For std::unique_ptr with objects allocated on a MEM_ROOT, you shouldn't use
  335. * Default_deleter; use this deleter instead.
  336. */
  337. template <class T>
  338. class Destroy_only {
  339. public:
  340. void operator()(T *ptr) const { destroy(ptr); }
  341. };
  342. /** std::unique_ptr, but only destroying. */
  343. template <class T>
  344. using unique_ptr_destroy_only = std::unique_ptr<T, Destroy_only<T>>;
  345. template <typename T, typename... Args>
  346. unique_ptr_destroy_only<T> make_unique_destroy_only(MEM_ROOT *mem_root,
  347. Args &&... args) {
  348. return unique_ptr_destroy_only<T>(new (mem_root)
  349. T(std::forward<Args>(args)...));
  350. }
  351. #endif // INCLUDE_MY_ALLOC_H_