1 // Copyright Maciej Sobczak 2008-2019.
2 // This file is part of YAMI4.
3 //
4 // YAMI4 is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // YAMI4 is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with YAMI4. If not, see <http://www.gnu.org/licenses/>.
16
17 #include "allocator.h"
18 #include "fatal_errors.h"
19 #include <cstdlib>
20
21 using namespace yami;
22 using namespace details;
23
24 namespace // unnamed
25 {
26
27 struct segment_header
28 {
29 segment_header * next_;
30 segment_header * prev_;
31
32 bool free_;
33
34 // used only when free_ == true
35 segment_header * next_free_;
36 segment_header * prev_free_;
37
38 union alignment
39 {
40 double dummy_;
41 char data_buffer_;
42 } aligned;
43 };
44
45 // the smallest segment that can be be split off (including header)
46 const std::size_t smallest_split_segment_size = 64;
47
48 // the round-up amount for alignment of split segments
49 const std::size_t round_up_amount = sizeof(double);
50
buffer_size(segment_header * segment,void * base,std::size_t total_size)51 std::size_t buffer_size(
52 segment_header * segment, void * base, std::size_t total_size)
53 {
54 std::size_t result;
55 if (segment->next_ != NULL)
56 {
57 // this is not the last segment
58
59 result = reinterpret_cast<char *>(segment->next_) -
60 &segment->aligned.data_buffer_;
61 }
62 else
63 {
64 // this is the last segment
65
66 result = total_size -
67 (&segment->aligned.data_buffer_ - reinterpret_cast<char *>(base));
68 }
69
70 return result;
71 }
72
73 } // namespace unnamed
74
allocator()75 allocator::allocator()
76 : base_(NULL), size_(0), first_free_segment_(NULL)
77 {
78 }
79
set_working_area(void * buf,std::size_t size)80 void allocator::set_working_area(void * buf, std::size_t size)
81 {
82 if (base_ != NULL)
83 {
84 fatal_failure(__FILE__, __LINE__);
85 }
86
87 if (buf != NULL && size != 0)
88 {
89 base_ = buf;
90 size_ = size;
91
92 segment_header * initial_segment =
93 reinterpret_cast<segment_header *>(base_);
94 initial_segment->next_ = NULL;
95 initial_segment->prev_ = NULL;
96 initial_segment->free_ = true;
97
98 initial_segment->next_free_ = NULL;
99 initial_segment->prev_free_ = NULL;
100
101 first_free_segment_ = initial_segment;
102 }
103 }
104
allocate(std::size_t requested_size)105 void * allocator::allocate(std::size_t requested_size)
106 {
107 void * result = NULL;
108
109 if (base_ == NULL)
110 {
111 result = std::malloc(requested_size);
112 }
113 else
114 {
115 // iterate over the list of free segments
116 // and find the first that is big enough
117
118 requested_size += round_up_amount - 1;
119 requested_size /= round_up_amount;
120 requested_size *= round_up_amount;
121
122 segment_header * segment =
123 reinterpret_cast<segment_header *>(first_free_segment_);
124 while (segment != NULL && result == NULL)
125 {
126 const std::size_t buf_size = buffer_size(segment, base_, size_);
127 if (buf_size >= requested_size)
128 {
129 std::size_t remaining_space = buf_size - requested_size;
130
131 if (remaining_space >= smallest_split_segment_size)
132 {
133 // the remaining space is enough
134 // to contain another segment
135 // -> split segments
136
137 segment_header * new_segment =
138 reinterpret_cast<segment_header *>(
139 &segment->aligned.data_buffer_
140 + buf_size - remaining_space);
141
142 new_segment->next_ = segment->next_;
143 new_segment->prev_ = segment;
144 new_segment->free_ = true;
145 segment->next_ = new_segment;
146 if (new_segment->next_ != NULL)
147 {
148 new_segment->next_->prev_ = new_segment;
149 }
150
151 new_segment->next_free_ = segment->next_free_;
152 new_segment->prev_free_ = segment;
153 segment->next_free_ = new_segment;
154 }
155
156 result = &segment->aligned.data_buffer_;
157 }
158 else
159 {
160 segment = segment->next_free_;
161 }
162 }
163
164 if (result != NULL)
165 {
166 // appropriate free segment was found
167 // -> mark it as not free and adjust free list links
168
169 segment->free_ = false;
170
171 if (segment->prev_free_ != NULL)
172 {
173 segment->prev_free_->next_free_ = segment->next_free_;
174 }
175 else
176 {
177 // this was the first free segment
178 first_free_segment_ = segment->next_free_;
179 }
180
181 if (segment->next_free_ != NULL)
182 {
183 segment->next_free_->prev_free_ = segment->prev_free_;
184 }
185 }
186 }
187
188 return result;
189 }
190
deallocate(const void * p)191 void allocator::deallocate(const void * p)
192 {
193 if (base_ == NULL)
194 {
195 std::free(const_cast<void *>(p));
196 }
197 else
198 {
199 segment_header * segment =
200 reinterpret_cast<segment_header *>(
201 static_cast<char *>(const_cast<void *>(p)) -
202 offsetof(segment_header, aligned));
203 segment->free_ = true;
204
205 // reestablish free list links
206
207 if (segment == first_free_segment_)
208 {
209 fatal_failure(__FILE__, __LINE__);
210 }
211
212 if (first_free_segment_ == NULL ||
213 segment < static_cast<segment_header *>(first_free_segment_))
214 {
215 // this segment should be the new first known free segment
216
217 segment->prev_free_ = NULL;
218 segment->next_free_ =
219 static_cast<segment_header *>(first_free_segment_);
220 if (first_free_segment_ != NULL)
221 {
222 static_cast<segment_header *>(
223 first_free_segment_)->prev_free_ = segment;
224 }
225
226 first_free_segment_ = segment;
227 }
228 else
229 {
230 // this segment is further than the first known free segment
231 // -> find the closest earlier free segment
232
233 segment_header * iter = segment->prev_;
234 while (iter->free_ == false)
235 {
236 iter = iter->prev_;
237 }
238
239 segment->prev_free_ = iter;
240 iter->next_free_ = segment;
241
242 // -> find the closest further free segment
243
244 iter = segment->next_;
245 while (iter != NULL && iter->free_ == false)
246 {
247 iter = iter->next_;
248 }
249
250 segment->next_free_ = iter;
251 if (iter != NULL)
252 {
253 iter->prev_free_ = segment;
254 }
255 }
256
257 if (segment->next_ != NULL)
258 {
259 // this is not the last segment
260 // -> attempt to join with the next one, if it is free
261
262 segment_header * next_segment = segment->next_;
263 if (next_segment->free_)
264 {
265 segment->next_ = next_segment->next_;
266 if (next_segment->next_ != NULL)
267 {
268 next_segment->next_->prev_ = segment;
269 }
270
271 segment->next_free_ = next_segment->next_free_;
272 if (next_segment->next_free_ != NULL)
273 {
274 next_segment->next_free_->prev_free_ = segment;
275 }
276 }
277 }
278
279 if (segment->prev_ != NULL)
280 {
281 // this is not the first segment
282 // -> attempt to join with the previous one, if it is free
283
284 segment_header * previous_segment = segment->prev_;
285 if (previous_segment->free_)
286 {
287 previous_segment->next_ = segment->next_;
288 if (segment->next_ != NULL)
289 {
290 segment->next_->prev_ = previous_segment;
291 }
292
293 previous_segment->next_free_ = segment->next_free_;
294 if (segment->next_free_ != NULL)
295 {
296 segment->next_free_->prev_free_ = previous_segment;
297 }
298 }
299 }
300 }
301 }
302
get_free_size(std::size_t & biggest,std::size_t & all) const303 void allocator::get_free_size(std::size_t & biggest, std::size_t & all) const
304 {
305 biggest = 0;
306 all = 0;
307
308 if (base_ != NULL)
309 {
310 segment_header * segment =
311 reinterpret_cast<segment_header *>(first_free_segment_);
312 while (segment != NULL)
313 {
314 const std::size_t buf_size = buffer_size(segment, base_, size_);
315 if (buf_size > biggest)
316 {
317 biggest = buf_size;
318 }
319
320 all += buf_size;
321
322 segment = segment->next_free_;
323 }
324 }
325 }
326