1/**************************************************************************/
2/* paged_allocator.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef PAGED_ALLOCATOR_H
32#define PAGED_ALLOCATOR_H
33
34#include "core/core_globals.h"
35#include "core/os/memory.h"
36#include "core/os/spin_lock.h"
37#include "core/string/ustring.h"
38#include "core/typedefs.h"
39
40#include <type_traits>
41#include <typeinfo>
42
43template <class T, bool thread_safe = false>
44class PagedAllocator {
45 T **page_pool = nullptr;
46 T ***available_pool = nullptr;
47 uint32_t pages_allocated = 0;
48 uint32_t allocs_available = 0;
49
50 uint32_t page_shift = 0;
51 uint32_t page_mask = 0;
52 uint32_t page_size = 0;
53 SpinLock spin_lock;
54
55public:
56 enum {
57 DEFAULT_PAGE_SIZE = 4096
58 };
59
60 template <class... Args>
61 T *alloc(const Args &&...p_args) {
62 if (thread_safe) {
63 spin_lock.lock();
64 }
65 if (unlikely(allocs_available == 0)) {
66 uint32_t pages_used = pages_allocated;
67
68 pages_allocated++;
69 page_pool = (T **)memrealloc(page_pool, sizeof(T *) * pages_allocated);
70 available_pool = (T ***)memrealloc(available_pool, sizeof(T **) * pages_allocated);
71
72 page_pool[pages_used] = (T *)memalloc(sizeof(T) * page_size);
73 available_pool[pages_used] = (T **)memalloc(sizeof(T *) * page_size);
74
75 for (uint32_t i = 0; i < page_size; i++) {
76 available_pool[0][i] = &page_pool[pages_used][i];
77 }
78 allocs_available += page_size;
79 }
80
81 allocs_available--;
82 T *alloc = available_pool[allocs_available >> page_shift][allocs_available & page_mask];
83 if (thread_safe) {
84 spin_lock.unlock();
85 }
86 memnew_placement(alloc, T(p_args...));
87 return alloc;
88 }
89
90 void free(T *p_mem) {
91 if (thread_safe) {
92 spin_lock.lock();
93 }
94 p_mem->~T();
95 available_pool[allocs_available >> page_shift][allocs_available & page_mask] = p_mem;
96 allocs_available++;
97 if (thread_safe) {
98 spin_lock.unlock();
99 }
100 }
101
102private:
103 void _reset(bool p_allow_unfreed) {
104 if (!p_allow_unfreed || !std::is_trivially_destructible<T>::value) {
105 ERR_FAIL_COND(allocs_available < pages_allocated * page_size);
106 }
107 if (pages_allocated) {
108 for (uint32_t i = 0; i < pages_allocated; i++) {
109 memfree(page_pool[i]);
110 memfree(available_pool[i]);
111 }
112 memfree(page_pool);
113 memfree(available_pool);
114 page_pool = nullptr;
115 available_pool = nullptr;
116 pages_allocated = 0;
117 allocs_available = 0;
118 }
119 }
120
121public:
122 void reset(bool p_allow_unfreed = false) {
123 if (thread_safe) {
124 spin_lock.lock();
125 }
126 _reset(p_allow_unfreed);
127 if (thread_safe) {
128 spin_lock.unlock();
129 }
130 }
131
132 bool is_configured() const {
133 if (thread_safe) {
134 spin_lock.lock();
135 }
136 bool result = page_size > 0;
137 if (thread_safe) {
138 spin_lock.unlock();
139 }
140 return result;
141 }
142
143 void configure(uint32_t p_page_size) {
144 if (thread_safe) {
145 spin_lock.lock();
146 }
147 ERR_FAIL_COND(page_pool != nullptr); //sanity check
148 ERR_FAIL_COND(p_page_size == 0);
149 page_size = nearest_power_of_2_templated(p_page_size);
150 page_mask = page_size - 1;
151 page_shift = get_shift_from_power_of_2(page_size);
152 if (thread_safe) {
153 spin_lock.unlock();
154 }
155 }
156
157 // Power of 2 recommended because of alignment with OS page sizes.
158 // Even if element is bigger, it's still a multiple and gets rounded to amount of pages.
159 PagedAllocator(uint32_t p_page_size = DEFAULT_PAGE_SIZE) {
160 configure(p_page_size);
161 }
162
163 ~PagedAllocator() {
164 if (thread_safe) {
165 spin_lock.lock();
166 }
167 bool leaked = allocs_available < pages_allocated * page_size;
168 if (leaked) {
169 if (CoreGlobals::leak_reporting_enabled) {
170 ERR_PRINT(String("Pages in use exist at exit in PagedAllocator: ") + String(typeid(T).name()));
171 }
172 } else {
173 _reset(false);
174 }
175 if (thread_safe) {
176 spin_lock.unlock();
177 }
178 }
179};
180
181#endif // PAGED_ALLOCATOR_H
182