1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2015-2015. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 // See http://www.boost.org/libs/container for documentation.
8 //
9 //////////////////////////////////////////////////////////////////////////////
10
11 #include <boost/container/pmr/global_resource.hpp>
12 #include <boost/core/lightweight_test.hpp>
13
14 #include <boost/intrusive/detail/math.hpp>
15
16 #include "derived_from_memory_resource.hpp"
17 #include "memory_resource_logger.hpp"
18
19 using namespace boost::container::pmr;
20
21 template<class PoolResource>
22 struct derived_from_pool_resource
23 : public PoolResource
24 {
derived_from_pool_resourcederived_from_pool_resource25 derived_from_pool_resource(const pool_options& opts, memory_resource* upstream)
26 : PoolResource(opts, upstream)
27 {}
28
derived_from_pool_resourcederived_from_pool_resource29 explicit derived_from_pool_resource(memory_resource *p)
30 : PoolResource(p)
31 {}
32
derived_from_pool_resourcederived_from_pool_resource33 explicit derived_from_pool_resource(const pool_options &opts)
34 : PoolResource(opts)
35 {}
36
derived_from_pool_resourcederived_from_pool_resource37 derived_from_pool_resource()
38 : PoolResource()
39 {}
40
41 using PoolResource::do_allocate;
42 using PoolResource::do_deallocate;
43 using PoolResource::do_is_equal;
44 };
45
46 template<class PoolResource>
test_default_constructor()47 void test_default_constructor()
48 {
49 //With default options/resource
50 {
51 derived_from_memory_resource dmr;
52 dmr.reset();
53 PoolResource m;
54 //test postconditions
55 BOOST_TEST(m.upstream_resource() == get_default_resource());
56 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
57 BOOST_TEST(m.options().largest_required_pool_block == pool_options_default_largest_required_pool_block);
58 //test it does not allocate any memory
59 BOOST_TEST(dmr.do_allocate_called == false);
60 }
61 }
62
63 template<class PoolResource>
test_upstream_constructor()64 void test_upstream_constructor()
65 {
66 //With a resource, default options
67 {
68 derived_from_memory_resource dmr;
69 dmr.reset();
70 PoolResource m(&dmr);
71 //test postconditions
72 BOOST_TEST(m.upstream_resource() == &dmr);
73 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
74 BOOST_TEST(m.options().largest_required_pool_block == pool_options_default_largest_required_pool_block);
75 //test it does not allocate any memory
76 BOOST_TEST(dmr.do_allocate_called == false);
77 }
78 }
79
80 template<class PoolResource>
test_options_constructor()81 void test_options_constructor()
82 {
83 //Default options
84 {
85 memory_resource_logger mrl;
86 BOOST_TEST(mrl.m_info.size() == 0u);
87 set_default_resource(&mrl);
88 pool_options opts;
89 PoolResource m(opts);
90 //test postconditions
91 BOOST_TEST(m.upstream_resource() == get_default_resource());
92 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
93 BOOST_TEST(m.options().largest_required_pool_block == pool_options_default_largest_required_pool_block);
94 //test it does not allocate any memory
95 BOOST_TEST(mrl.m_info.size() == 0u);
96 }
97 //Too large option values
98 {
99 memory_resource_logger mrl;
100 BOOST_TEST(mrl.m_info.size() == 0u);
101 set_default_resource(&mrl);
102 pool_options opts;
103 opts.max_blocks_per_chunk = pool_options_default_max_blocks_per_chunk+1;
104 opts.largest_required_pool_block = pool_options_default_largest_required_pool_block+1;
105 PoolResource m(opts);
106 //test postconditions
107 BOOST_TEST(m.upstream_resource() == get_default_resource());
108 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
109 BOOST_TEST(m.options().largest_required_pool_block == pool_options_default_largest_required_pool_block);
110 //test it does not allocate any memory
111 BOOST_TEST(mrl.m_info.size() == 0u);
112 }
113 //Too small option values
114 {
115 memory_resource_logger mrl;
116 BOOST_TEST(mrl.m_info.size() == 0u);
117 set_default_resource(&mrl);
118 pool_options opts;
119 opts.largest_required_pool_block = pool_options_minimum_largest_required_pool_block-1u;
120 PoolResource m(opts);
121 //test postconditions
122 BOOST_TEST(m.upstream_resource() == get_default_resource());
123 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
124 BOOST_TEST(m.options().largest_required_pool_block == pool_options_minimum_largest_required_pool_block);
125 //test it does not allocate any memory
126 BOOST_TEST(mrl.m_info.size() == 0u);
127 }
128 //In range option values
129 {
130 memory_resource_logger mrl;
131 BOOST_TEST(mrl.m_info.size() == 0u);
132 set_default_resource(&mrl);
133 pool_options opts;
134 opts.max_blocks_per_chunk = pool_options_default_max_blocks_per_chunk;
135 opts.largest_required_pool_block = pool_options_minimum_largest_required_pool_block;
136 PoolResource m(opts);
137 //test postconditions
138 BOOST_TEST(m.upstream_resource() == get_default_resource());
139 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
140 BOOST_TEST(m.options().largest_required_pool_block == pool_options_minimum_largest_required_pool_block);
141 //test it does not allocate any memory
142 BOOST_TEST(mrl.m_info.size() == 0u);
143 }
144 }
145
146 template<class PoolResource>
test_options_upstream_constructor()147 void test_options_upstream_constructor()
148 {
149 //Default options
150 {
151 derived_from_memory_resource dmr;
152 dmr.reset();
153 pool_options opts;
154 PoolResource m(opts, &dmr);
155 //test postconditions
156 BOOST_TEST(m.upstream_resource() == &dmr);
157 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
158 BOOST_TEST(m.options().largest_required_pool_block == pool_options_default_largest_required_pool_block);
159 //test it does not allocate any memory
160 BOOST_TEST(dmr.do_allocate_called == false);
161 }
162 //Too large option values
163 {
164 derived_from_memory_resource dmr;
165 dmr.reset();
166 pool_options opts;
167 opts.max_blocks_per_chunk = pool_options_default_max_blocks_per_chunk+1;
168 opts.largest_required_pool_block = pool_options_default_largest_required_pool_block+1;
169 PoolResource m(opts, &dmr);
170 //test postconditions
171 BOOST_TEST(m.upstream_resource() == &dmr);
172 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
173 BOOST_TEST(m.options().largest_required_pool_block == pool_options_default_largest_required_pool_block);
174 //test it does not allocate any memory
175 BOOST_TEST(dmr.do_allocate_called == false);
176 }
177 //Too small option values
178 {
179 derived_from_memory_resource dmr;
180 dmr.reset();
181 pool_options opts;
182 opts.largest_required_pool_block = pool_options_minimum_largest_required_pool_block-1u;
183 PoolResource m(opts, &dmr);
184 //test postconditions
185 BOOST_TEST(m.upstream_resource() == &dmr);
186 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
187 BOOST_TEST(m.options().largest_required_pool_block == pool_options_minimum_largest_required_pool_block);
188 //test it does not allocate any memory
189 BOOST_TEST(dmr.do_allocate_called == false);
190 }
191 //In range option values
192 {
193 derived_from_memory_resource dmr;
194 dmr.reset();
195 pool_options opts;
196 opts.max_blocks_per_chunk = pool_options_default_max_blocks_per_chunk;
197 opts.largest_required_pool_block = pool_options_minimum_largest_required_pool_block;
198 PoolResource m(opts, &dmr);
199 //test postconditions
200 BOOST_TEST(m.upstream_resource() == &dmr);
201 //max blocks is unchanged in this implementation
202 BOOST_TEST(m.options().max_blocks_per_chunk == pool_options_default_max_blocks_per_chunk);
203 //largest block is rounded to pow2
204 BOOST_TEST(m.options().largest_required_pool_block == bi::detail::ceil_pow2(opts.largest_required_pool_block));
205 //test it does not allocate any memory
206 BOOST_TEST(dmr.do_allocate_called == false);
207 }
208 }
209
210 template<class PoolResource>
test_options()211 void test_options()
212 {
213 //In range option values
214 {
215 derived_from_memory_resource dmr;
216 dmr.reset();
217 pool_options opts;
218 opts.max_blocks_per_chunk = pool_options_default_max_blocks_per_chunk/2u;
219 opts.largest_required_pool_block = (pool_options_default_largest_required_pool_block
220 - pool_options_minimum_largest_required_pool_block) | std::size_t(1); //guaranteed to be non power of 2.
221 PoolResource m(opts, &dmr);
222 //test postconditions
223 BOOST_TEST(m.upstream_resource() == &dmr);
224 //max blocks is unchanged in this implementation
225 BOOST_TEST(m.options().max_blocks_per_chunk == opts.max_blocks_per_chunk);
226 //largest block is rounded to pow2
227 BOOST_TEST(m.options().largest_required_pool_block == bi::detail::ceil_pow2(opts.largest_required_pool_block));
228 //test it does not allocate any memory
229 BOOST_TEST(dmr.do_allocate_called == false);
230 }
231 }
232
233 template<class PoolResource>
test_do_allocate_deallocate()234 void test_do_allocate_deallocate()
235 {
236 memory_resource_logger mrl;
237 {
238 derived_from_pool_resource<PoolResource> dmbr(&mrl);
239 {
240 //First block from pool 0
241 dmbr.do_allocate(1, 1);
242 //It should allocate the pool array plus an initial block
243 BOOST_TEST(mrl.m_info.size() == 2u);
244 //Second block from pool 0
245 dmbr.do_allocate(1, 1);
246 //It should allocate again (with 2 chunks per block)
247 BOOST_TEST(mrl.m_info.size() == 3u);
248 //Third block from pool 0
249 dmbr.do_allocate(1, 1);
250 //It should NOT allocate again (previous was a 2 block chunk)
251 BOOST_TEST(mrl.m_info.size() == 3u);
252 }
253 }
254 BOOST_TEST(mrl.m_mismatches == 0u);
255 BOOST_TEST(mrl.m_info.size() == 0u);
256
257 //Allocate and deallocate from the same chunk to test block caching
258 {
259 derived_from_pool_resource<PoolResource> dmbr(&mrl);
260 {
261 //First block from pool 0
262 void *p = dmbr.do_allocate(1, 1);
263 //It should allocate the pool array plus an initial block
264 BOOST_TEST(mrl.m_info.size() == 2u);
265 //No cached, as initial blocks per chunk is 1
266 BOOST_TEST(dmbr.pool_cached_blocks(0u) == 0u);
267 //Deallocate and allocate again
268 dmbr.do_deallocate(p, 1, 1);
269 //Cached
270 BOOST_TEST(dmbr.pool_cached_blocks(0u) == 1u);
271 p = dmbr.do_allocate(1, 1);
272 //Reused
273 BOOST_TEST(dmbr.pool_cached_blocks(0u) == 0u);
274 //It should have NOT allocated (block reuse)
275 BOOST_TEST(mrl.m_info.size() == 2u);
276
277 //Allocate again 2 times (a 2 block chunk is exhausted)
278 void *p2 = dmbr.do_allocate(1, 1);
279 //1 left cached
280 BOOST_TEST(dmbr.pool_cached_blocks(0u) == 1u);
281 void *p3 = dmbr.do_allocate(1, 1);
282 //Cache exhausted
283 BOOST_TEST(dmbr.pool_cached_blocks(0u) == 0u);
284 //Single chunk allocation happened
285 BOOST_TEST(mrl.m_info.size() == 3u);
286
287 //Now deallocate all (no memory is freed, all cached)
288 dmbr.do_deallocate(p2, 1, 1);
289 dmbr.do_deallocate(p3, 1, 1);
290 dmbr.do_deallocate(p, 1, 1);
291 BOOST_TEST(dmbr.pool_cached_blocks(0u) == 3u);
292 BOOST_TEST(mrl.m_info.size() == 3u);
293 }
294 }
295 BOOST_TEST(mrl.m_mismatches == 0u);
296 BOOST_TEST(mrl.m_info.size() == 0u);
297
298 //Now test max block per chunk
299 {
300 pool_options opts;
301 //so after max_blocks_per_chunk*2-1 allocations, all new chunks must hold max_blocks_per_chunk blocks
302 opts.max_blocks_per_chunk = 32u;
303 derived_from_pool_resource<PoolResource> dmbr(opts, &mrl);
304 {
305 std::size_t loops = opts.max_blocks_per_chunk*2-1u;
306 while(loops--){
307 dmbr.do_allocate(1, 1);
308 }
309 //pool array + log2(max_blocks_per_chunk)+1 chunks (sizes [1, 2, 4, ...])
310 const std::size_t num_chunks = bi::detail::floor_log2(opts.max_blocks_per_chunk)+1u;
311 BOOST_TEST(mrl.m_info.size() == 1u + num_chunks);
312 //Next allocation should allocate max_blocks_per_chunk blocks in a chunk so max_blocks_per_chunk-1 should remain free
313 dmbr.do_allocate(1, 1);
314 BOOST_TEST(mrl.m_info.size() == 1u + num_chunks + 1u);
315 BOOST_TEST(dmbr.pool_cached_blocks(0u) == (opts.max_blocks_per_chunk-1u));
316 //Exhaust the chunk and allocate a new one, test max_blocks_per_chunk is not passed again
317 loops = opts.max_blocks_per_chunk;
318 while(loops--){
319 dmbr.do_allocate(1, 1);
320 }
321 BOOST_TEST(mrl.m_info.size() == 1u + num_chunks + 2u);
322 BOOST_TEST(dmbr.pool_cached_blocks(0u) == (opts.max_blocks_per_chunk-1u));
323 }
324 }
325 BOOST_TEST(mrl.m_mismatches == 0u);
326 BOOST_TEST(mrl.m_info.size() == 0u);
327
328 //Now test max block per chunk
329 {
330 pool_options opts;
331 //so after max_blocks_per_chunk*2-1 allocations, all new chunks must hold max_blocks_per_chunk blocks
332 opts.max_blocks_per_chunk = 32u;
333 derived_from_pool_resource<PoolResource> dmbr(opts, &mrl);
334 {
335 std::size_t loops = opts.max_blocks_per_chunk*2-1u;
336 while(loops--){
337 dmbr.do_allocate(1, 1);
338 }
339 //pool array + log2(max_blocks_per_chunk)+1 chunks (sizes [1, 2, 4, ...])
340 BOOST_TEST(dmbr.pool_next_blocks_per_chunk(0u) == opts.max_blocks_per_chunk);
341 const std::size_t num_chunks = bi::detail::floor_log2(opts.max_blocks_per_chunk)+1u;
342 BOOST_TEST(mrl.m_info.size() == 1u + num_chunks);
343 //Next allocation should allocate max_blocks_per_chunk blocks in a chunk so max_blocks_per_chunk-1 should remain free
344 dmbr.do_allocate(1, 1);
345 BOOST_TEST(dmbr.pool_next_blocks_per_chunk(0u) == opts.max_blocks_per_chunk);
346 BOOST_TEST(mrl.m_info.size() == 1u + num_chunks + 1u);
347 BOOST_TEST(dmbr.pool_cached_blocks(0u) == (opts.max_blocks_per_chunk-1u));
348 }
349 }
350 BOOST_TEST(mrl.m_mismatches == 0u);
351 BOOST_TEST(mrl.m_info.size() == 0u);
352
353 //Now test different pool sizes
354 {
355 pool_options opts;
356 //so after max_blocks_per_chunk*2-1 allocations, all new chunks must hold max_blocks_per_chunk blocks
357 opts.max_blocks_per_chunk = 1u;
358 derived_from_pool_resource<PoolResource> dmbr(opts, &mrl);
359 const pool_options &final_opts = dmbr.options();
360
361 //Force pool creation
362 dmbr.do_deallocate(dmbr.do_allocate(1, 1), 1, 1);
363 //pool array plus first pool's chunk allocation
364 BOOST_TEST(mrl.m_info.size() == 2u);
365 //pool count must be:
366 // log2(the maximum block) - log2(the minimum block) + 1. Example if minimum block is 8, and maximum 32:
367 // log(32) - log2(8) + 1u = 3 pools (block sizes: 8, 16, and 32)
368 const std::size_t minimum_size = dmbr.pool_block(0u);
369 const std::size_t maximum_size = final_opts.largest_required_pool_block;
370 BOOST_TEST(dmbr.pool_count() == (1u + bi::detail::floor_log2(maximum_size) - bi::detail::floor_log2(minimum_size)));
371 for(std::size_t i = 0, s = minimum_size, max = dmbr.pool_count(); i != max; ++i, s*=2){
372 //Except in the first pool, each cache should be empty
373 BOOST_TEST(dmbr.pool_cached_blocks(i) == std::size_t(i == 0));
374 dmbr.do_deallocate(dmbr.do_allocate(s/2+1, 1), s/2+1, 1);
375 dmbr.do_deallocate(dmbr.do_allocate(s-1, 1), s-1, 1);
376 dmbr.do_deallocate(dmbr.do_allocate(s, 1), s, 1);
377 //pool array plus each previous chunk allocation
378 BOOST_TEST(mrl.m_info.size() == (1u + i + 1u));
379 //as we limited max_blocks_per_chunk to 1, no cached blocks should be available except one
380 BOOST_TEST(dmbr.pool_cached_blocks(i) == 1u);
381 }
382 //Now test out of maximum values, which should go directly to upstream
383 //it should be directly deallocated.
384 void *p = dmbr.do_allocate(maximum_size+1, 1);
385 BOOST_TEST(mrl.m_info.size() == (1u + dmbr.pool_count() + 1u));
386 dmbr.do_deallocate(p, maximum_size+1, 1);
387 BOOST_TEST(mrl.m_info.size() == (1u + dmbr.pool_count()));
388 }
389 BOOST_TEST(mrl.m_mismatches == 0u);
390 BOOST_TEST(mrl.m_info.size() == 0u);
391 }
392
393 template<class PoolResource>
test_do_is_equal()394 void test_do_is_equal()
395 {
396 //`this == dynamic_cast<const PoolResource*>(&other)`.
397 memory_resource_logger mrl;
398 derived_from_pool_resource<PoolResource> dmbr(&mrl);
399 derived_from_pool_resource<PoolResource> dmbr2(&mrl);
400 BOOST_TEST(true == dmbr.do_is_equal(dmbr));
401 BOOST_TEST(false == dmbr.do_is_equal(dmbr2));
402 //A different type should be always different
403 derived_from_memory_resource dmr;
404 BOOST_TEST(false == dmbr.do_is_equal(dmr));
405 }
406
407 template<class PoolResource>
test_release()408 void test_release()
409 {
410 memory_resource_logger mrl;
411 {
412 pool_options opts;
413 //so after max_blocks_per_chunk*2-1 allocations, all new chunks must hold max_blocks_per_chunk blocks
414 opts.max_blocks_per_chunk = 4u;
415 derived_from_pool_resource<PoolResource> dmbr(opts, &mrl);
416 const pool_options &final_opts = dmbr.options();
417 const std::size_t minimum_size = dmbr.pool_block(0u);
418 const std::size_t maximum_size = final_opts.largest_required_pool_block;
419 const std::size_t pool_count = 1u + bi::detail::floor_log2(maximum_size) - bi::detail::floor_log2(minimum_size);
420
421 std::size_t expected_memory_allocs = 0;
422 for(std::size_t i = 0, imax = pool_count, s = minimum_size; i != imax; s*=2, ++i){
423 for(std::size_t j = 0, j_max = opts.max_blocks_per_chunk*2u-1u; j != j_max; ++j){
424 dmbr.do_allocate(s, 1);
425 }
426 //One due to the pool array, and for each pool, log2(max_blocks_per_chunk)+1 allocations
427 expected_memory_allocs = 1 + (bid::floor_log2(opts.max_blocks_per_chunk) + 1u)*(i+1);
428 //pool array plus each previous chunk allocation
429 BOOST_TEST(mrl.m_info.size() == expected_memory_allocs);
430 }
431 //Now with out-of-pool sizes
432 for(std::size_t j = 0, j_max = opts.max_blocks_per_chunk*2u-1u; j != j_max; ++j){
433 dmbr.do_allocate(maximum_size+1, 1);
434 BOOST_TEST(mrl.m_info.size() == ++expected_memory_allocs);
435 }
436 //Now release memory and check all memory allocated through do_allocate was deallocated to upstream
437 dmbr.release();
438 BOOST_TEST(mrl.m_info.size() == 1u);
439 }
440 BOOST_TEST(mrl.m_mismatches == 0u);
441 BOOST_TEST(mrl.m_info.size() == 0u);
442 }
443
444 template<class PoolResource>
test_destructor()445 void test_destructor()
446 {
447 memory_resource_logger mrl;
448 {
449 pool_options opts;
450 //so after max_blocks_per_chunk*2-1 allocations, all new chunks must hold max_blocks_per_chunk blocks
451 opts.max_blocks_per_chunk = 4u;
452 derived_from_pool_resource<PoolResource> dmbr(opts, &mrl);
453 const pool_options &final_opts = dmbr.options();
454 const std::size_t minimum_size = dmbr.pool_block(0u);
455 const std::size_t maximum_size = final_opts.largest_required_pool_block;
456 const std::size_t pool_count = 1u + bi::detail::floor_log2(maximum_size) - bi::detail::floor_log2(minimum_size);
457
458 std::size_t expected_memory_allocs = 0;
459 for(std::size_t i = 0, imax = pool_count, s = minimum_size; i != imax; s*=2, ++i){
460 for(std::size_t j = 0, j_max = opts.max_blocks_per_chunk*2u-1u; j != j_max; ++j){
461 dmbr.do_allocate(s, 1);
462 }
463 //One due to the pool array, and for each pool, log2(max_blocks_per_chunk)+1 allocations
464 expected_memory_allocs = 1 + (bid::floor_log2(opts.max_blocks_per_chunk) + 1u)*(i+1);
465 //pool array plus each previous chunk allocation
466 BOOST_TEST(mrl.m_info.size() == expected_memory_allocs);
467 }
468 //Now with out-of-pool sizes
469 for(std::size_t j = 0, j_max = opts.max_blocks_per_chunk*2u-1u; j != j_max; ++j){
470 dmbr.do_allocate(maximum_size+1, 1);
471 BOOST_TEST(mrl.m_info.size() == ++expected_memory_allocs);
472 }
473 //Don't release, all memory, including internal allocations, should be automatically
474 //released after the destructor is run
475 }
476 BOOST_TEST(mrl.m_mismatches == 0u);
477 BOOST_TEST(mrl.m_info.size() == 0u);
478 }
479
480
481 template<class PoolResource>
test_pool_resource()482 void test_pool_resource()
483 {
484 test_options_upstream_constructor<PoolResource>();
485 test_default_constructor<PoolResource>();
486 test_upstream_constructor<PoolResource>();
487 test_options_constructor<PoolResource>();
488 test_options<PoolResource>();
489 test_do_allocate_deallocate<PoolResource>();
490 test_do_is_equal<PoolResource>();
491 test_release<PoolResource>();
492 test_destructor<PoolResource>();
493 }
494