Jolt Physics
A multi core friendly Game Physics Engine
Loading...
Searching...
No Matches
FixedSizeFreeList.inl
Go to the documentation of this file.
1// Jolt Physics Library (https://github.com/jrouwe/JoltPhysics)
2// SPDX-FileCopyrightText: 2021 Jorrit Rouwe
3// SPDX-License-Identifier: MIT
4
6
7template <typename Object>
9{
10 // Check if we got our Init call
11 if (mPages != nullptr)
12 {
13 // Ensure everything is freed before the freelist is destructed
14 JPH_ASSERT(mNumFreeObjects.load(memory_order_relaxed) == mNumPages * mPageSize);
15
16 // Free memory for pages
17 uint32 num_pages = mNumObjectsAllocated.load(memory_order_relaxed) / mPageSize;
18 for (uint32 page = 0; page < num_pages; ++page)
19 AlignedFree(mPages[page]);
20 Free(mPages);
21 }
22}
23
24template <typename Object>
25void FixedSizeFreeList<Object>::Init(uint inMaxObjects, uint inPageSize)
26{
27 // Check sanity
28 JPH_ASSERT(inPageSize > 0 && IsPowerOf2(inPageSize));
29 JPH_ASSERT(mPages == nullptr);
30
31 // Store configuration parameters
32 mNumPages = (inMaxObjects + inPageSize - 1) / inPageSize;
33 mPageSize = inPageSize;
34 mPageShift = CountTrailingZeros(inPageSize);
35 mObjectMask = inPageSize - 1;
36 JPH_IF_ENABLE_ASSERTS(mNumFreeObjects = mNumPages * inPageSize;)
37
38 // Allocate page table
39 mPages = reinterpret_cast<ObjectStorage **>(Allocate(mNumPages * sizeof(ObjectStorage *)));
40
41 // We didn't yet use any objects of any page
42 mNumObjectsAllocated.store(0, memory_order_relaxed);
43 mFirstFreeObjectInNewPage = 0;
44
45 // Start with 1 as the first tag
46 mAllocationTag = 1;
47
48 // Set first free object (with tag 0)
49 mFirstFreeObjectAndTag = cInvalidObjectIndex;
50}
51
52template <typename Object>
53template <typename... Parameters>
55{
56 for (;;)
57 {
58 // Get first object from the linked list
59 uint64 first_free_object_and_tag = mFirstFreeObjectAndTag.load(memory_order_acquire);
60 uint32 first_free = uint32(first_free_object_and_tag);
61 if (first_free == cInvalidObjectIndex)
62 {
63 // The free list is empty, we take an object from the page that has never been used before
64 first_free = mFirstFreeObjectInNewPage.fetch_add(1, memory_order_relaxed);
65 if (first_free >= mNumObjectsAllocated.load(memory_order_acquire)) // Acquire to ensure we see the page pointer if the page was allocated by another thread
66 {
67 // Allocate new page
68 lock_guard lock(mPageMutex);
69 uint32 num_objects_allocated = mNumObjectsAllocated.load(memory_order_relaxed); // Only modified under lock
70 while (first_free >= num_objects_allocated)
71 {
72 uint32 next_page = num_objects_allocated / mPageSize;
73 if (next_page == mNumPages)
74 return cInvalidObjectIndex; // Out of space!
75 mPages[next_page] = reinterpret_cast<ObjectStorage *>(AlignedAllocate(mPageSize * sizeof(ObjectStorage), max<size_t>(alignof(ObjectStorage), JPH_CACHE_LINE_SIZE)));
76 num_objects_allocated += mPageSize;
77 mNumObjectsAllocated.store(num_objects_allocated, memory_order_release); // Release so that the page pointer is visible to threads that read the new value
78 }
79 }
80
81 // Allocation successful
82 JPH_IF_ENABLE_ASSERTS(mNumFreeObjects.fetch_sub(1, memory_order_relaxed);)
83 ObjectStorage &storage = GetStorage(first_free);
84 new (&storage.mObject) Object(std::forward<Parameters>(inParameters)...);
85 storage.mNextFreeObject.store(first_free, memory_order_release);
86 return first_free;
87 }
88 else
89 {
90 // Load next pointer
91 uint32 new_first_free = GetStorage(first_free).mNextFreeObject.load(memory_order_acquire);
92
93 // Construct a new first free object tag
94 uint64 new_first_free_object_and_tag = uint64(new_first_free) + (uint64(mAllocationTag.fetch_add(1, memory_order_relaxed)) << 32);
95
96 // Compare and swap
97 if (mFirstFreeObjectAndTag.compare_exchange_weak(first_free_object_and_tag, new_first_free_object_and_tag, memory_order_release))
98 {
99 // Allocation successful
100 JPH_IF_ENABLE_ASSERTS(mNumFreeObjects.fetch_sub(1, memory_order_relaxed);)
101 ObjectStorage &storage = GetStorage(first_free);
102 new (&storage.mObject) Object(std::forward<Parameters>(inParameters)...);
103 storage.mNextFreeObject.store(first_free, memory_order_release);
104 return first_free;
105 }
106 }
107 }
108}
109
110template <typename Object>
112{
113 JPH_ASSERT(ioBatch.mNumObjects != uint32(-1), "Trying to reuse a batch that has already been freed");
114
115 // Reset next index
116 atomic<uint32> &next_free_object = GetStorage(inObjectIndex).mNextFreeObject;
117 JPH_ASSERT(next_free_object.load(memory_order_relaxed) == inObjectIndex, "Trying to add a object to the batch that is already in a free list");
118 next_free_object.store(cInvalidObjectIndex, memory_order_release);
119
120 // Link object in batch to free
122 ioBatch.mFirstObjectIndex = inObjectIndex;
123 else
124 GetStorage(ioBatch.mLastObjectIndex).mNextFreeObject.store(inObjectIndex, memory_order_release);
125 ioBatch.mLastObjectIndex = inObjectIndex;
126 ioBatch.mNumObjects++;
127}
128
129template <typename Object>
131{
133 {
134 // Call destructors
135 if constexpr (!std::is_trivially_destructible<Object>())
136 {
137 uint32 object_idx = ioBatch.mFirstObjectIndex;
138 do
139 {
140 ObjectStorage &storage = GetStorage(object_idx);
141 storage.mObject.~Object();
142 object_idx = storage.mNextFreeObject.load(memory_order_relaxed);
143 }
144 while (object_idx != cInvalidObjectIndex);
145 }
146
147 // Add to objects free list
148 ObjectStorage &storage = GetStorage(ioBatch.mLastObjectIndex);
149 for (;;)
150 {
151 // Get first object from the list
152 uint64 first_free_object_and_tag = mFirstFreeObjectAndTag.load(memory_order_acquire);
153 uint32 first_free = uint32(first_free_object_and_tag);
154
155 // Make it the next pointer of the last object in the batch that is to be freed
156 storage.mNextFreeObject.store(first_free, memory_order_release);
157
158 // Construct a new first free object tag
159 uint64 new_first_free_object_and_tag = uint64(ioBatch.mFirstObjectIndex) + (uint64(mAllocationTag.fetch_add(1, memory_order_relaxed)) << 32);
160
161 // Compare and swap
162 if (mFirstFreeObjectAndTag.compare_exchange_weak(first_free_object_and_tag, new_first_free_object_and_tag, memory_order_release))
163 {
164 // Free successful
165 JPH_IF_ENABLE_ASSERTS(mNumFreeObjects.fetch_add(ioBatch.mNumObjects, memory_order_relaxed);)
166
167 // Mark the batch as freed
168#ifdef JPH_ENABLE_ASSERTS
169 ioBatch.mNumObjects = uint32(-1);
170#endif
171 return;
172 }
173 }
174 }
175}
176
177template <typename Object>
179{
180 JPH_ASSERT(inObjectIndex != cInvalidObjectIndex);
181
182 // Call destructor
183 ObjectStorage &storage = GetStorage(inObjectIndex);
184 storage.mObject.~Object();
185
186 // Add to object free list
187 for (;;)
188 {
189 // Get first object from the list
190 uint64 first_free_object_and_tag = mFirstFreeObjectAndTag.load(memory_order_acquire);
191 uint32 first_free = uint32(first_free_object_and_tag);
192
193 // Make it the next pointer of the last object in the batch that is to be freed
194 storage.mNextFreeObject.store(first_free, memory_order_release);
195
196 // Construct a new first free object tag
197 uint64 new_first_free_object_and_tag = uint64(inObjectIndex) + (uint64(mAllocationTag.fetch_add(1, memory_order_relaxed)) << 32);
198
199 // Compare and swap
200 if (mFirstFreeObjectAndTag.compare_exchange_weak(first_free_object_and_tag, new_first_free_object_and_tag, memory_order_release))
201 {
202 // Free successful
203 JPH_IF_ENABLE_ASSERTS(mNumFreeObjects.fetch_add(1, memory_order_relaxed);)
204 return;
205 }
206 }
207}
208
209template<typename Object>
211{
212 return reinterpret_cast<const ObjectStorage *>(inObject)->mNextFreeObject.load(memory_order_relaxed);
213}
214
215template<typename Object>
217{
218 uint32 index = GetObjectIndex(inObject);
219 JPH_ASSERT(index < mNumObjectsAllocated.load(memory_order_relaxed));
220 DestructObject(index);
221}
222
#define JPH_CACHE_LINE_SIZE
Definition Core.h:613
std::uint64_t uint64
Definition Core.h:569
unsigned int uint
Definition Core.h:564
#define JPH_NAMESPACE_END
Definition Core.h:487
std::uint32_t uint32
Definition Core.h:567
#define JPH_NAMESPACE_BEGIN
Definition Core.h:481
#define JPH_IF_ENABLE_ASSERTS(...)
Definition IssueReporting.h:30
#define JPH_ASSERT(...)
Definition IssueReporting.h:28
constexpr bool IsPowerOf2(T inV)
Check if inV is a power of 2.
Definition Math.h:161
uint CountTrailingZeros(uint32 inValue)
Compute number of trailing zero bits (how many low bits are zero).
Definition Math.h:183
AllocateFunction Allocate
Definition Memory.cpp:68
FreeFunction Free
Definition Memory.cpp:70
AlignedFreeFunction AlignedFree
Definition Memory.cpp:72
AlignedAllocateFunction AlignedAllocate
Definition Memory.cpp:71
@ Object
Start of a new object.
Definition SerializableAttribute.h:20
void Init(uint inMaxObjects, uint inPageSize)
Initialize the free list, up to inMaxObjects can be allocated.
Definition FixedSizeFreeList.inl:25
void DestructObjectBatch(Batch &ioBatch)
Lockless destruct batch of objects.
Definition FixedSizeFreeList.inl:130
uint32 GetObjectIndex(const Object *inObject) const
Get the index of an object that was created by this free list.
Definition FixedSizeFreeList.inl:210
uint32 ConstructObject(Parameters &&... inParameters)
Lockless construct a new object, inParameters are passed on to the constructor.
Definition FixedSizeFreeList.inl:54
~FixedSizeFreeList()
Destructor.
Definition FixedSizeFreeList.inl:8
void DestructObject(uint32 inObjectIndex)
Lockless destruct an object and return it to the free pool.
Definition FixedSizeFreeList.inl:178
static const uint32 cInvalidObjectIndex
Invalid index.
Definition FixedSizeFreeList.h:77
void AddObjectToBatch(Batch &ioBatch, uint32 inObjectIndex)
Definition FixedSizeFreeList.inl:111
A batch of objects that can be destructed.
Definition FixedSizeFreeList.h:100
uint32 mFirstObjectIndex
Definition FixedSizeFreeList.h:101
uint32 mNumObjects
Definition FixedSizeFreeList.h:103
uint32 mLastObjectIndex
Definition FixedSizeFreeList.h:102