memory_allocator.h 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508
  1. // Copyright (c) 2011 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef COURGETTE_MEMORY_ALLOCATOR_H_
  5. #define COURGETTE_MEMORY_ALLOCATOR_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10. #include "base/files/file.h"
  11. #include "base/logging.h"
  12. #include "base/memory/raw_ptr.h"
  13. #include "base/process/memory.h"
  14. #include "build/build_config.h"
  15. #ifndef NDEBUG
  16. // A helper class to track down call sites that are not handling error cases.
  17. template<class T>
  18. class CheckReturnValue {
  19. public:
  20. // Not marked explicit on purpose.
  21. CheckReturnValue(T value) : value_(value), checked_(false) { // NOLINT
  22. }
  23. CheckReturnValue(const CheckReturnValue& other)
  24. : value_(other.value_), checked_(other.checked_) {
  25. other.checked_ = true;
  26. }
  27. CheckReturnValue& operator=(const CheckReturnValue& other) {
  28. if (this != &other) {
  29. DCHECK(checked_);
  30. value_ = other.value_;
  31. checked_ = other.checked_;
  32. other.checked_ = true;
  33. }
  34. return *this;
  35. }
  36. ~CheckReturnValue() {
  37. DCHECK(checked_);
  38. }
  39. operator const T&() const {
  40. checked_ = true;
  41. return value_;
  42. }
  43. private:
  44. T value_;
  45. mutable bool checked_;
  46. };
  47. typedef CheckReturnValue<bool> CheckBool;
  48. #else
  49. typedef bool CheckBool;
  50. #endif
  51. namespace courgette {
  52. // Allocates memory for an instance of type T, instantiates an object in that
  53. // memory with arguments |args| (of type ArgTypes), and returns the constructed
  54. // instance. Returns null if allocation fails.
  55. template <class T, class... ArgTypes>
  56. T* UncheckedNew(ArgTypes... args) {
  57. void* ram = nullptr;
  58. return base::UncheckedMalloc(sizeof(T), &ram) ? new (ram) T(args...)
  59. : nullptr;
  60. }
  61. // Complement of UncheckedNew(): destructs |object| and releases its memory.
  62. template <class T>
  63. void UncheckedDelete(T* object) {
  64. if (object) {
  65. object->T::~T();
  66. free(object);
  67. }
  68. }
  69. // A deleter for std::unique_ptr that will delete the object via
  70. // UncheckedDelete().
  71. template <class T>
  72. struct UncheckedDeleter {
  73. inline void operator()(T* ptr) const { UncheckedDelete(ptr); }
  74. };
  75. #if BUILDFLAG(IS_WIN)
  76. // Manages a read/write virtual mapping of a physical file.
  77. class FileMapping {
  78. public:
  79. FileMapping();
  80. ~FileMapping();
  81. // Map a file from beginning to |size|.
  82. bool Create(HANDLE file, size_t size);
  83. void Close();
  84. // Returns true iff a mapping has been created.
  85. bool valid() const;
  86. // Returns a writable pointer to the beginning of the memory mapped file.
  87. // If Create has not been called successfully, return value is nullptr.
  88. void* view() const;
  89. protected:
  90. bool InitializeView(size_t size);
  91. HANDLE mapping_;
  92. raw_ptr<void> view_;
  93. };
  94. // Manages a temporary file and a memory mapping of the temporary file.
  95. // The memory that this class manages holds a pointer back to the TempMapping
  96. // object itself, so that given a memory pointer allocated by this class,
  97. // you can get a pointer to the TempMapping instance that owns that memory.
  98. class TempMapping {
  99. public:
  100. TempMapping();
  101. ~TempMapping();
  102. // Creates a temporary file of size |size| and maps it into the current
  103. // process's address space.
  104. bool Initialize(size_t size);
  105. // Returns a writable pointer to the reserved memory.
  106. void* memory() const;
  107. // Returns true if the mapping is valid and memory is available.
  108. bool valid() const;
  109. // Returns a pointer to the TempMapping instance that allocated the |mem|
  110. // block of memory. It's the callers responsibility to make sure that
  111. // the memory block was allocated by the TempMapping class.
  112. static TempMapping* GetMappingFromPtr(void* mem);
  113. protected:
  114. base::File file_;
  115. FileMapping mapping_;
  116. };
  117. // A memory allocator class that allocates memory either from the heap or via a
  118. // temporary file. The interface is STL inspired but the class does not throw
  119. // STL exceptions on allocation failure. Instead it returns nullptr.
  120. // A file allocation will be made if either the requested memory size exceeds
  121. // |kMaxHeapAllocationSize| or if a heap allocation fails.
  122. // Allocating the memory as a mapping of a temporary file solves the problem
  123. // that there might not be enough physical memory and pagefile to support the
  124. // allocation. This can happen because these resources are too small, or
  125. // already committed to other processes. Provided there is enough disk, the
  126. // temporary file acts like a pagefile that other processes can't access.
  127. template<class T>
  128. class MemoryAllocator {
  129. public:
  130. typedef T value_type;
  131. typedef value_type* pointer;
  132. typedef value_type& reference;
  133. typedef const value_type* const_pointer;
  134. typedef const value_type& const_reference;
  135. typedef size_t size_type;
  136. typedef ptrdiff_t difference_type;
  137. // Each allocation is tagged with a single byte so that we know how to
  138. // deallocate it.
  139. enum AllocationType : uint8_t {
  140. HEAP_ALLOCATION = 0xF0, // Non-trivial constants to detect corruption.
  141. FILE_ALLOCATION = 0x0F,
  142. };
  143. // 5MB is the maximum heap allocation size that we'll attempt.
  144. // When applying a patch for Chrome 10.X we found that at this
  145. // threshold there were 17 allocations higher than this threshold
  146. // (largest at 136MB) 10 allocations just below the threshold and 6362
  147. // smaller allocations.
  148. static const size_t kMaxHeapAllocationSize = 1024 * 1024 * 5;
  149. template<class OtherT>
  150. struct rebind {
  151. // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
  152. typedef MemoryAllocator<OtherT> other;
  153. };
  154. MemoryAllocator() {}
  155. // We can't use an explicit constructor here, as dictated by our style guide.
  156. // The implementation of basic_string in Visual Studio 2010 prevents this.
  157. MemoryAllocator(const MemoryAllocator<T>& other) { // NOLINT
  158. }
  159. template <class OtherT>
  160. MemoryAllocator(const MemoryAllocator<OtherT>& other) { // NOLINT
  161. }
  162. ~MemoryAllocator() {
  163. }
  164. void deallocate(pointer ptr, size_type size) {
  165. uint8_t* mem = reinterpret_cast<uint8_t*>(ptr);
  166. mem -= sizeof(T);
  167. if (mem[0] == HEAP_ALLOCATION)
  168. free(mem);
  169. else if (mem[0] == FILE_ALLOCATION)
  170. UncheckedDelete(TempMapping::GetMappingFromPtr(mem));
  171. else
  172. LOG(FATAL);
  173. }
  174. pointer allocate(size_type count) {
  175. // We use the first byte of each allocation to mark the allocation type.
  176. // However, so that the allocation is properly aligned, we allocate an
  177. // extra element and then use the first byte of the first element
  178. // to mark the allocation type.
  179. count++;
  180. if (count > max_size())
  181. return nullptr;
  182. size_type bytes = count * sizeof(T);
  183. uint8_t* mem = nullptr;
  184. // First see if we can do this allocation on the heap.
  185. if (count < kMaxHeapAllocationSize &&
  186. base::UncheckedMalloc(bytes, reinterpret_cast<void**>(&mem))) {
  187. mem[0] = static_cast<uint8_t>(HEAP_ALLOCATION);
  188. } else {
  189. // Back the allocation with a temp file if either the request exceeds the
  190. // max heap allocation threshold or the heap allocation failed.
  191. TempMapping* mapping = UncheckedNew<TempMapping>();
  192. if (mapping) {
  193. if (mapping->Initialize(bytes)) {
  194. mem = reinterpret_cast<uint8_t*>(mapping->memory());
  195. mem[0] = static_cast<uint8_t>(FILE_ALLOCATION);
  196. } else {
  197. UncheckedDelete(mapping);
  198. }
  199. }
  200. }
  201. // If the above fails (e.g. because we are in a sandbox), just try the heap.
  202. if (!mem && base::UncheckedMalloc(bytes, reinterpret_cast<void**>(&mem))) {
  203. mem[0] = static_cast<uint8_t>(HEAP_ALLOCATION);
  204. }
  205. return mem ? reinterpret_cast<pointer>(mem + sizeof(T)) : nullptr;
  206. }
  207. pointer allocate(size_type count, const void* hint) {
  208. return allocate(count);
  209. }
  210. void construct(pointer ptr, const T& value) {
  211. ::new(ptr) T(value);
  212. }
  213. void destroy(pointer ptr) {
  214. ptr->~T();
  215. }
  216. size_type max_size() const {
  217. size_type count = static_cast<size_type>(-1) / sizeof(T);
  218. return (0 < count ? count : 1);
  219. }
  220. };
  221. #else // BUILDFLAG(IS_WIN)
  222. // On Mac, Linux, we use a bare bones implementation that only does
  223. // heap allocations.
  224. template<class T>
  225. class MemoryAllocator {
  226. public:
  227. typedef T value_type;
  228. typedef value_type* pointer;
  229. typedef value_type& reference;
  230. typedef const value_type* const_pointer;
  231. typedef const value_type& const_reference;
  232. typedef size_t size_type;
  233. typedef ptrdiff_t difference_type;
  234. template<class OtherT>
  235. struct rebind {
  236. // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
  237. typedef MemoryAllocator<OtherT> other;
  238. };
  239. MemoryAllocator() {
  240. }
  241. explicit MemoryAllocator(const MemoryAllocator<T>& other) {
  242. }
  243. template<class OtherT>
  244. explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) {
  245. }
  246. ~MemoryAllocator() {
  247. }
  248. void deallocate(pointer ptr, size_type size) { free(ptr); }
  249. pointer allocate(size_type count) {
  250. if (count > max_size())
  251. return nullptr;
  252. pointer result = nullptr;
  253. return base::UncheckedMalloc(count * sizeof(T),
  254. reinterpret_cast<void**>(&result))
  255. ? result
  256. : nullptr;
  257. }
  258. pointer allocate(size_type count, const void* hint) {
  259. return allocate(count);
  260. }
  261. void construct(pointer ptr, const T& value) {
  262. ::new(ptr) T(value);
  263. }
  264. void destroy(pointer ptr) {
  265. ptr->~T();
  266. }
  267. size_type max_size() const {
  268. size_type count = static_cast<size_type>(-1) / sizeof(T);
  269. return (0 < count ? count : 1);
  270. }
  271. };
  272. #endif // BUILDFLAG(IS_WIN)
  273. // Manages a growable buffer. The buffer allocation is done by the
  274. // MemoryAllocator class. This class will not throw exceptions so call sites
  275. // must be prepared to handle memory allocation failures.
  276. // The interface is STL inspired to avoid having to make too many changes
  277. // to code that previously was using STL.
  278. template<typename T, class Allocator = MemoryAllocator<T> >
  279. class NoThrowBuffer {
  280. public:
  281. typedef T value_type;
  282. static const size_t kAllocationFailure = 0xffffffff;
  283. static const size_t kStartSize = sizeof(T) > 0x100 ? 1 : 0x100 / sizeof(T);
  284. NoThrowBuffer() : buffer_(nullptr), size_(0), alloc_size_(0) {}
  285. ~NoThrowBuffer() {
  286. clear();
  287. }
  288. void clear() {
  289. if (buffer_) {
  290. alloc_.deallocate(buffer_, alloc_size_);
  291. buffer_ = nullptr;
  292. size_ = 0;
  293. alloc_size_ = 0;
  294. }
  295. }
  296. bool empty() const {
  297. return size_ == 0;
  298. }
  299. [[nodiscard]] CheckBool reserve(size_t size) {
  300. if (failed())
  301. return false;
  302. if (size <= alloc_size_)
  303. return true;
  304. if (size < kStartSize)
  305. size = kStartSize;
  306. T* new_buffer = alloc_.allocate(size);
  307. if (!new_buffer) {
  308. clear();
  309. alloc_size_ = kAllocationFailure;
  310. } else {
  311. if (buffer_) {
  312. memcpy(new_buffer, buffer_, size_ * sizeof(T));
  313. alloc_.deallocate(buffer_, alloc_size_);
  314. }
  315. buffer_ = new_buffer;
  316. alloc_size_ = size;
  317. }
  318. return !failed();
  319. }
  320. [[nodiscard]] CheckBool append(const T* data, size_t size) {
  321. if (failed())
  322. return false;
  323. if (size > alloc_.max_size() - size_)
  324. return false;
  325. if (!size)
  326. return true;
  327. // Disallow source range from overlapping with buffer_, since in this case
  328. // reallocation would cause use-after-free.
  329. DCHECK(data + size <= buffer_ || data >= buffer_ + alloc_size_);
  330. if ((alloc_size_ - size_) < size) {
  331. const size_t max_size = alloc_.max_size();
  332. size_t new_size = alloc_size_ ? alloc_size_ : kStartSize;
  333. while (new_size < size_ + size) {
  334. if (new_size < max_size - new_size) {
  335. new_size *= 2;
  336. } else {
  337. new_size = max_size;
  338. }
  339. }
  340. if (!reserve(new_size))
  341. return false;
  342. }
  343. memcpy(buffer_ + size_, data, size * sizeof(T));
  344. size_ += size;
  345. return true;
  346. }
  347. [[nodiscard]] CheckBool resize(size_t size, const T& init_value) {
  348. if (size > size_) {
  349. if (!reserve(size))
  350. return false;
  351. for (size_t i = size_; i < size; ++i)
  352. buffer_[i] = init_value;
  353. } else if (size < size_) {
  354. // TODO(tommi): Should we allocate a new, smaller buffer?
  355. // It might be faster for us to simply change the size.
  356. }
  357. size_ = size;
  358. return true;
  359. }
  360. [[nodiscard]] CheckBool push_back(const T& item) { return append(&item, 1); }
  361. const T& back() const {
  362. return buffer_[size_ - 1];
  363. }
  364. T& back() {
  365. return buffer_[size_ - 1];
  366. }
  367. const T* begin() const {
  368. if (!size_)
  369. return nullptr;
  370. return buffer_;
  371. }
  372. T* begin() {
  373. if (!size_)
  374. return nullptr;
  375. return buffer_;
  376. }
  377. const T* end() const {
  378. if (!size_)
  379. return nullptr;
  380. return buffer_ + size_;
  381. }
  382. T* end() {
  383. if (!size_)
  384. return nullptr;
  385. return buffer_ + size_;
  386. }
  387. const T& operator[](size_t index) const {
  388. DCHECK(index < size_);
  389. return buffer_[index];
  390. }
  391. T& operator[](size_t index) {
  392. DCHECK(index < size_);
  393. return buffer_[index];
  394. }
  395. size_t size() const {
  396. return size_;
  397. }
  398. size_t capacity() const {
  399. return alloc_size_;
  400. }
  401. T* data() const {
  402. return buffer_;
  403. }
  404. // Returns true if an allocation failure has ever occurred for this object.
  405. bool failed() const {
  406. return alloc_size_ == kAllocationFailure;
  407. }
  408. protected:
  409. raw_ptr<T> buffer_;
  410. size_t size_; // how much of the buffer we're using.
  411. size_t alloc_size_; // how much space we have allocated.
  412. Allocator alloc_;
  413. };
  414. } // namespace courgette
  415. #endif // COURGETTE_MEMORY_ALLOCATOR_H_