1 //////////////////////////////////////////////////////////////////////////////
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)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
11 #include <boost/container/pmr/global_resource.hpp>
12 #include <boost/core/lightweight_test.hpp>
14 #include <boost/intrusive/detail/math.hpp>
16 #include "derived_from_memory_resource.hpp"
17 #include "memory_resource_logger.hpp"
19 using namespace boost::container::pmr;
21 template<class PoolResource>
22 struct derived_from_pool_resource
25 derived_from_pool_resource(const pool_options& opts, memory_resource* upstream)
26 : PoolResource(opts, upstream)
29 explicit derived_from_pool_resource(memory_resource *p)
33 explicit derived_from_pool_resource(const pool_options &opts)
37 derived_from_pool_resource()
41 using PoolResource::do_allocate;
42 using PoolResource::do_deallocate;
43 using PoolResource::do_is_equal;
46 template<class PoolResource>
47 void test_default_constructor()
49 //With default options/resource
51 derived_from_memory_resource dmr;
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);
63 template<class PoolResource>
64 void test_upstream_constructor()
66 //With a resource, default options
68 derived_from_memory_resource dmr;
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);
80 template<class PoolResource>
81 void test_options_constructor()
85 memory_resource_logger mrl;
86 BOOST_TEST(mrl.m_info.size() == 0u);
87 set_default_resource(&mrl);
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);
97 //Too large option values
99 memory_resource_logger mrl;
100 BOOST_TEST(mrl.m_info.size() == 0u);
101 set_default_resource(&mrl);
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);
113 //Too small option values
115 memory_resource_logger mrl;
116 BOOST_TEST(mrl.m_info.size() == 0u);
117 set_default_resource(&mrl);
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);
128 //In range option values
130 memory_resource_logger mrl;
131 BOOST_TEST(mrl.m_info.size() == 0u);
132 set_default_resource(&mrl);
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);
146 template<class PoolResource>
147 void test_options_upstream_constructor()
151 derived_from_memory_resource dmr;
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);
162 //Too large option values
164 derived_from_memory_resource dmr;
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);
177 //Too small option values
179 derived_from_memory_resource dmr;
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);
191 //In range option values
193 derived_from_memory_resource dmr;
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);
210 template<class PoolResource>
213 //In range option values
215 derived_from_memory_resource dmr;
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);
233 template<class PoolResource>
234 void test_do_allocate_deallocate()
236 memory_resource_logger mrl;
238 derived_from_pool_resource<PoolResource> dmbr(&mrl);
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);
254 BOOST_TEST(mrl.m_mismatches == 0u);
255 BOOST_TEST(mrl.m_info.size() == 0u);
257 //Allocate and deallocate from the same chunk to test block caching
259 derived_from_pool_resource<PoolResource> dmbr(&mrl);
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);
270 BOOST_TEST(dmbr.pool_cached_blocks(0u) == 1u);
271 p = dmbr.do_allocate(1, 1);
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);
277 //Allocate again 2 times (a 2 block chunk is exhausted)
278 void *p2 = dmbr.do_allocate(1, 1);
280 BOOST_TEST(dmbr.pool_cached_blocks(0u) == 1u);
281 void *p3 = dmbr.do_allocate(1, 1);
283 BOOST_TEST(dmbr.pool_cached_blocks(0u) == 0u);
284 //Single chunk allocation happened
285 BOOST_TEST(mrl.m_info.size() == 3u);
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);
295 BOOST_TEST(mrl.m_mismatches == 0u);
296 BOOST_TEST(mrl.m_info.size() == 0u);
298 //Now test max block per chunk
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);
305 std::size_t loops = opts.max_blocks_per_chunk*2-1u;
307 dmbr.do_allocate(1, 1);
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;
319 dmbr.do_allocate(1, 1);
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));
325 BOOST_TEST(mrl.m_mismatches == 0u);
326 BOOST_TEST(mrl.m_info.size() == 0u);
328 //Now test max block per chunk
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);
335 std::size_t loops = opts.max_blocks_per_chunk*2-1u;
337 dmbr.do_allocate(1, 1);
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));
350 BOOST_TEST(mrl.m_mismatches == 0u);
351 BOOST_TEST(mrl.m_info.size() == 0u);
353 //Now test different pool sizes
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();
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);
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()));
389 BOOST_TEST(mrl.m_mismatches == 0u);
390 BOOST_TEST(mrl.m_info.size() == 0u);
393 template<class PoolResource>
394 void test_do_is_equal()
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));
407 template<class PoolResource>
410 memory_resource_logger mrl;
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);
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);
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);
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);
436 //Now release memory and check all memory allocated through do_allocate was deallocated to upstream
438 BOOST_TEST(mrl.m_info.size() == 1u);
440 BOOST_TEST(mrl.m_mismatches == 0u);
441 BOOST_TEST(mrl.m_info.size() == 0u);
444 template<class PoolResource>
445 void test_destructor()
447 memory_resource_logger mrl;
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);
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);
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);
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);
473 //Don't release, all memory, including internal allocations, should be automatically
474 //released after the destructor is run
476 BOOST_TEST(mrl.m_mismatches == 0u);
477 BOOST_TEST(mrl.m_info.size() == 0u);
481 template<class PoolResource>
482 void test_pool_resource()
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>();