1 // Copyright 2020 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_allocator/freelist.h"
16
17 namespace pw::allocator {
18
AddChunk(std::span<std::byte> chunk)19 Status FreeList::AddChunk(std::span<std::byte> chunk) {
20 // Check that the size is enough to actually store what we need
21 if (chunk.size() < sizeof(FreeListNode)) {
22 return Status::OutOfRange();
23 }
24
25 union {
26 FreeListNode* node;
27 std::byte* bytes;
28 } aliased;
29
30 aliased.bytes = chunk.data();
31
32 size_t chunk_ptr = FindChunkPtrForSize(chunk.size(), false);
33
34 // Add it to the correct list.
35 aliased.node->size = chunk.size();
36 aliased.node->next = chunks_[chunk_ptr];
37 chunks_[chunk_ptr] = aliased.node;
38
39 return OkStatus();
40 }
41
FindChunk(size_t size) const42 std::span<std::byte> FreeList::FindChunk(size_t size) const {
43 if (size == 0) {
44 return std::span<std::byte>();
45 }
46
47 size_t chunk_ptr = FindChunkPtrForSize(size, true);
48
49 // Check that there's data. This catches the case where we run off the
50 // end of the array
51 if (chunks_[chunk_ptr] == nullptr) {
52 return std::span<std::byte>();
53 }
54
55 // Now iterate up the buckets, walking each list to find a good candidate
56 for (size_t i = chunk_ptr; i < chunks_.size(); i++) {
57 union {
58 FreeListNode* node;
59 std::byte* data;
60 } aliased;
61 aliased.node = chunks_[i];
62
63 while (aliased.node != nullptr) {
64 if (aliased.node->size >= size) {
65 return std::span<std::byte>(aliased.data, aliased.node->size);
66 }
67
68 aliased.node = aliased.node->next;
69 }
70 }
71
72 // If we get here, we've checked every block in every bucket. There's
73 // nothing that can support this allocation.
74 return std::span<std::byte>();
75 }
76
RemoveChunk(std::span<std::byte> chunk)77 Status FreeList::RemoveChunk(std::span<std::byte> chunk) {
78 size_t chunk_ptr = FindChunkPtrForSize(chunk.size(), true);
79
80 // Walk that list, finding the chunk.
81 union {
82 FreeListNode* node;
83 std::byte* data;
84 } aliased, aliased_next;
85
86 // Check head first.
87 if (chunks_[chunk_ptr] == nullptr) {
88 return Status::NotFound();
89 }
90
91 aliased.node = chunks_[chunk_ptr];
92 if (aliased.data == chunk.data()) {
93 chunks_[chunk_ptr] = aliased.node->next;
94
95 return OkStatus();
96 }
97
98 // No? Walk the nodes.
99 aliased.node = chunks_[chunk_ptr];
100
101 while (aliased.node->next != nullptr) {
102 aliased_next.node = aliased.node->next;
103 if (aliased_next.data == chunk.data()) {
104 // Found it, remove this node out of the chain
105 aliased.node->next = aliased_next.node->next;
106 return OkStatus();
107 }
108
109 aliased.node = aliased.node->next;
110 }
111
112 return Status::NotFound();
113 }
114
FindChunkPtrForSize(size_t size,bool non_null) const115 size_t FreeList::FindChunkPtrForSize(size_t size, bool non_null) const {
116 size_t chunk_ptr = 0;
117 for (chunk_ptr = 0; chunk_ptr < sizes_.size(); chunk_ptr++) {
118 if (sizes_[chunk_ptr] >= size &&
119 (!non_null || chunks_[chunk_ptr] != nullptr)) {
120 break;
121 }
122 }
123
124 return chunk_ptr;
125 }
126
127 } // namespace pw::allocator
128