1 //////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2007-2013. 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 //////////////////////////////////////////////////////////////////////////////
13 #pragma warning (disable:4702)
19 #include <algorithm> //std::remove
20 #include <boost/container/detail/dlmalloc.hpp>
22 namespace boost
{ namespace container
{ namespace test
{
24 static const std::size_t NumIt
= 200;
26 enum deallocation_type
{ DirectDeallocation
, InverseDeallocation
, MixedDeallocation
, EndDeallocationType
};
28 //This test allocates until there is no more memory
29 //and after that deallocates all in the inverse order
31 bool test_allocation()
33 if(!dlmalloc_all_deallocated())
35 dlmalloc_malloc_check();
36 for( deallocation_type t
= DirectDeallocation
37 ; t
!= EndDeallocationType
38 ; t
= (deallocation_type
)((int)t
+ 1)){
39 std::vector
<void*> buffers
;
40 //std::size_t free_memory = a.get_free_memory();
42 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
43 void *ptr
= dlmalloc_malloc(i
);
46 buffers
.push_back(ptr
);
50 case DirectDeallocation
:
52 for(std::size_t j
= 0, max
= buffers
.size()
55 dlmalloc_free(buffers
[j
]);
59 case InverseDeallocation
:
61 for(std::size_t j
= buffers
.size()
64 dlmalloc_free(buffers
[j
]);
68 case MixedDeallocation
:
70 for(std::size_t j
= 0, max
= buffers
.size()
73 std::size_t pos
= (j
%4)*(buffers
.size())/4;
74 dlmalloc_free(buffers
[pos
]);
75 buffers
.erase(buffers
.begin()+(std::ptrdiff_t)pos
);
82 if(!dlmalloc_all_deallocated())
84 //bool ok = free_memory == a.get_free_memory() &&
85 //a.all_memory_deallocated() && a.check_sanity();
88 dlmalloc_malloc_check();
89 return 0 != dlmalloc_all_deallocated();
92 //This test allocates until there is no more memory
93 //and after that tries to shrink all the buffers to the
94 //half of the original size
96 bool test_allocation_shrink()
98 dlmalloc_malloc_check();
99 std::vector
<void*> buffers
;
101 //Allocate buffers with extra memory
102 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
103 void *ptr
= dlmalloc_malloc(i
*2u);
106 buffers
.push_back(ptr
);
110 for(std::size_t i
= 0, max
= buffers
.size()
113 std::size_t try_received_size
= 0;
114 void* try_result
= dlmalloc_allocation_command
115 ( BOOST_CONTAINER_TRY_SHRINK_IN_PLACE
, 1, i
*2
116 , i
, &try_received_size
, (char*)buffers
[i
]).first
;
118 std::size_t received_size
= 0;
119 void* result
= dlmalloc_allocation_command
120 ( BOOST_CONTAINER_SHRINK_IN_PLACE
, 1, i
*2
121 , i
, &received_size
, (char*)buffers
[i
]).first
;
123 if(result
!= try_result
)
126 if(received_size
!= try_received_size
)
130 if(received_size
> std::size_t(i
*2)){
133 if(received_size
< std::size_t(i
)){
139 //Deallocate it in non sequential order
140 for(std::size_t j
= 0, max
= buffers
.size()
143 std::size_t pos
= (j
%4u)*(buffers
.size())/4u;
144 dlmalloc_free(buffers
[pos
]);
145 buffers
.erase(buffers
.begin()+(std::ptrdiff_t)pos
);
147 dlmalloc_malloc_check();
148 return 0 != dlmalloc_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
151 //This test allocates until there is no more memory
152 //and after that tries to expand all the buffers to
153 //avoid the wasted internal fragmentation
155 bool test_allocation_expand()
157 dlmalloc_malloc_check();
158 std::vector
<void*> buffers
;
160 //Allocate buffers with extra memory
161 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
162 void *ptr
= dlmalloc_malloc(i
);
165 buffers
.push_back(ptr
);
168 //Now try to expand to the double of the size
169 for(std::size_t i
= 0, max
= buffers
.size()
172 std::size_t received_size
= 0;
173 std::size_t min_size
= i
+1;
174 std::size_t preferred_size
= i
*2;
175 preferred_size
= min_size
> preferred_size
? min_size
: preferred_size
;
176 while(dlmalloc_allocation_command
177 ( BOOST_CONTAINER_EXPAND_FWD
, 1, min_size
178 , preferred_size
, &received_size
, (char*)buffers
[i
]).first
){
179 //Check received size is bigger than minimum
180 if(received_size
< min_size
){
183 //Now, try to expand further
184 min_size
= received_size
+1;
185 preferred_size
= min_size
*2;
189 //Deallocate it in non sequential order
190 for(std::size_t j
= 0, max
= buffers
.size()
193 std::size_t pos
= (j
%4u)*(buffers
.size())/4u;
194 dlmalloc_free(buffers
[pos
]);
195 buffers
.erase(buffers
.begin()+(std::ptrdiff_t)pos
);
197 dlmalloc_malloc_check();
198 return 0 != dlmalloc_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
201 //This test allocates until there is no more memory
202 //and after that tries to expand all the buffers to
203 //avoid the wasted internal fragmentation
204 bool test_allocation_shrink_and_expand()
206 std::vector
<void*> buffers
;
207 std::vector
<std::size_t> received_sizes
;
208 std::vector
<bool> size_reduced
;
210 //Allocate buffers wand store received sizes
211 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
212 std::size_t received_size
= 0;
213 void *ptr
= dlmalloc_allocation_command
214 (BOOST_CONTAINER_ALLOCATE_NEW
, 1u, i
, i
*2u, &received_size
, 0).first
;
216 ptr
= dlmalloc_allocation_command
217 ( BOOST_CONTAINER_ALLOCATE_NEW
, 1u, 1u, i
*2, &received_size
, 0).first
;
221 buffers
.push_back(ptr
);
222 received_sizes
.push_back(received_size
);
226 for(std::size_t i
= 0, max
= buffers
.size()
229 std::size_t received_size
= 0;
230 bool size_reduced_flag
;
231 if(true == (size_reduced_flag
= !!
232 dlmalloc_allocation_command
233 ( BOOST_CONTAINER_SHRINK_IN_PLACE
, 1, received_sizes
[i
]
234 , i
, &received_size
, (char*)buffers
[i
]).first
)){
235 if(received_size
> std::size_t(received_sizes
[i
])){
238 if(received_size
< std::size_t(i
)){
242 size_reduced
.push_back(size_reduced_flag
);
245 //Now try to expand to the original size
246 for(std::size_t i
= 0, max
= buffers
.size()
249 if(!size_reduced
[i
]) continue;
250 std::size_t received_size
= 0;
251 std::size_t request_size
= received_sizes
[i
];
252 if(dlmalloc_allocation_command
253 ( BOOST_CONTAINER_EXPAND_FWD
, 1, request_size
254 , request_size
, &received_size
, (char*)buffers
[i
]).first
){
255 if(received_size
!= request_size
){
264 //Deallocate it in non sequential order
265 for(std::size_t j
= 0, max
= buffers
.size()
268 std::size_t pos
= (j
%4u)*(buffers
.size())/4u;
269 dlmalloc_free(buffers
[pos
]);
270 buffers
.erase(buffers
.begin()+(std::ptrdiff_t)pos
);
273 return 0 != dlmalloc_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
276 //This test allocates until there is no more memory
277 //and after that deallocates the odd buffers to
278 //make room for expansions. The expansion will probably
279 //success since the deallocation left room for that.
281 bool test_allocation_deallocation_expand()
283 dlmalloc_malloc_check();
284 std::vector
<void*> buffers
;
286 //Allocate buffers with extra memory
287 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
288 void *ptr
= dlmalloc_malloc(i
);
291 buffers
.push_back(ptr
);
294 //Now deallocate the half of the blocks
295 //so expand maybe can merge new free blocks
296 for(std::size_t i
= 0, max
= buffers
.size()
300 dlmalloc_free(buffers
[i
]);
305 //Now try to expand to the double of the size
306 for(std::size_t i
= 0, max
= buffers
.size()
311 std::size_t received_size
= 0;
312 std::size_t min_size
= i
+1;
313 std::size_t preferred_size
= i
*2;
314 preferred_size
= min_size
> preferred_size
? min_size
: preferred_size
;
316 while(dlmalloc_allocation_command
317 ( BOOST_CONTAINER_EXPAND_FWD
, 1, min_size
318 , preferred_size
, &received_size
, (char*)buffers
[i
]).first
){
319 //Check received size is bigger than minimum
320 if(received_size
< min_size
){
323 //Now, try to expand further
324 min_size
= received_size
+1;
325 preferred_size
= min_size
*2;
330 //Now erase null values from the vector
331 buffers
.erase(std::remove(buffers
.begin(), buffers
.end(), (void*)0)
334 //Deallocate it in non sequential order
335 for(std::size_t j
= 0, max
= buffers
.size()
338 std::size_t pos
= (j
%4u)*(buffers
.size())/4u;
339 dlmalloc_free(buffers
[pos
]);
340 buffers
.erase(buffers
.begin()+(std::ptrdiff_t)pos
);
342 dlmalloc_malloc_check();
343 return 0 != dlmalloc_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
346 //This test allocates until there is no more memory
347 //and after that deallocates all except the last.
348 //If the allocation algorithm is a bottom-up algorithm
349 //the last buffer will be in the end of the segment.
350 //Then the test will start expanding backwards, until
351 //the buffer fills all the memory
353 bool test_allocation_with_reuse()
355 dlmalloc_malloc_check();
356 //We will repeat this test for different sized elements
357 for(std::size_t sizeof_object
= 1; sizeof_object
< 20; ++sizeof_object
){
358 std::vector
<void*> buffers
;
360 //Allocate buffers with extra memory
361 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
362 void *ptr
= dlmalloc_malloc(i
*sizeof_object
);
365 buffers
.push_back(ptr
);
368 //Now deallocate all except the latest
369 //Now try to expand to the double of the size
370 for(std::size_t i
= 0, max
= buffers
.size() - 1
373 dlmalloc_free(buffers
[i
]);
376 //Save the unique buffer and clear vector
377 void *ptr
= buffers
.back();
380 //Now allocate with reuse
381 std::size_t received_size
= 0;
382 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
383 std::size_t min_size
= (received_size
/sizeof_object
+ 1u)*sizeof_object
;
384 std::size_t prf_size
= (received_size
/sizeof_object
+ (i
+1u)*2u)*sizeof_object
;
385 dlmalloc_command_ret_t ret
= dlmalloc_allocation_command
386 ( BOOST_CONTAINER_EXPAND_BWD
, sizeof_object
, min_size
387 , prf_size
, &received_size
, (char*)ptr
);
388 //If we have memory, this must be a buffer reuse
391 //If we have memory, this must be a buffer reuse
394 if(received_size
< min_size
)
398 //There should be only a single block so deallocate it
400 dlmalloc_malloc_check();
401 if(!dlmalloc_all_deallocated())
408 //This test allocates memory with different alignments
409 //and checks returned memory is aligned.
411 bool test_aligned_allocation()
413 dlmalloc_malloc_check();
414 //Allocate aligned buffers in a loop
415 //and then deallocate it
416 for(std::size_t i
= 1u; i
!= (1u << (sizeof(int)/2u)); i
<<= 1u){
417 for(std::size_t j
= 1u; j
!= 512u; j
<<= 1){
418 void *ptr
= dlmalloc_memalign(i
-1, j
);
423 if(((std::size_t)ptr
& (j
- 1)) != 0)
426 //if(!a.all_memory_deallocated() || !a.check_sanity()){
431 dlmalloc_malloc_check();
432 return 0 != dlmalloc_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
435 //This test allocates memory with different alignments
436 //and checks returned memory is aligned.
438 bool test_continuous_aligned_allocation()
440 dlmalloc_malloc_check();
441 std::vector
<void*> buffers
;
442 //Allocate aligned buffers in a loop
443 //and then deallocate it
444 bool continue_loop
= true;
445 std::size_t MaxAlign
= 4096;
446 std::size_t MaxSize
= 4096;
447 for(std::size_t i
= 1; i
< MaxSize
; i
<<= 1){
448 for(std::size_t j
= 1; j
< MaxAlign
; j
<<= 1){
449 for(std::size_t k
= 0; k
!= NumIt
; ++k
){
450 void *ptr
= dlmalloc_memalign(i
-1, j
);
451 buffers
.push_back(ptr
);
453 continue_loop
= false;
457 if(((std::size_t)ptr
& (j
- 1)) != 0)
461 for(std::size_t k
= buffers
.size(); k
--;){
462 dlmalloc_free(buffers
[k
]);
465 //if(!a.all_memory_deallocated() && a.check_sanity())
471 dlmalloc_malloc_check();
472 return 0 != dlmalloc_all_deallocated();//a.all_memory_deallocated() && a.check_sanity();
475 //This test allocates multiple values until there is no more memory
476 //and after that deallocates all in the inverse order
477 bool test_many_equal_allocation()
479 dlmalloc_malloc_check();
480 for( deallocation_type t
= DirectDeallocation
481 ; t
!= EndDeallocationType
482 ; t
= (deallocation_type
)((int)t
+ 1)){
483 //std::size_t free_memory = a.get_free_memory();
485 std::vector
<void*> buffers2
;
487 //Allocate buffers with extra memory
488 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
489 void *ptr
= dlmalloc_malloc(i
);
492 //if(!a.check_sanity())
494 buffers2
.push_back(ptr
);
497 //Now deallocate the half of the blocks
498 //so expand maybe can merge new free blocks
499 for(std::size_t i
= 0, max
= buffers2
.size()
503 dlmalloc_free(buffers2
[i
]);
508 //if(!a.check_sanity())
511 std::vector
<void*> buffers
;
512 for(std::size_t i
= 0; i
!= NumIt
/10; ++i
){
513 dlmalloc_memchain chain
;
514 BOOST_CONTAINER_MEMCHAIN_INIT(&chain
);
515 dlmalloc_multialloc_nodes((i
+1)*2, i
+1, BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS
, &chain
);
516 dlmalloc_memchain_it it
= BOOST_CONTAINER_MEMCHAIN_BEGIN_IT(&chain
);
517 if(BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain
, it
))
521 for(; !BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain
, it
); ++n
){
522 buffers
.push_back(BOOST_CONTAINER_MEMIT_ADDR(it
));
523 BOOST_CONTAINER_MEMIT_NEXT(it
);
525 if(n
!= std::size_t((i
+1)*2))
529 //if(!a.check_sanity())
533 case DirectDeallocation
:
535 for(std::size_t j
= 0, max
= buffers
.size()
538 dlmalloc_free(buffers
[j
]);
542 case InverseDeallocation
:
544 for(std::size_t j
= buffers
.size()
547 dlmalloc_free(buffers
[j
]);
551 case MixedDeallocation
:
553 for(std::size_t j
= 0, max
= buffers
.size()
556 std::size_t pos
= (j
%4u)*(buffers
.size())/4u;
557 dlmalloc_free(buffers
[pos
]);
558 buffers
.erase(buffers
.begin()+(std::ptrdiff_t)pos
);
566 //Deallocate the rest of the blocks
568 //Deallocate it in non sequential order
569 for(std::size_t j
= 0, max
= buffers2
.size()
572 std::size_t pos
= (j
%4u)*(buffers2
.size())/4u;
573 dlmalloc_free(buffers2
[pos
]);
574 buffers2
.erase(buffers2
.begin()+(std::ptrdiff_t)pos
);
577 //bool ok = free_memory == a.get_free_memory() &&
578 //a.all_memory_deallocated() && a.check_sanity();
581 dlmalloc_malloc_check();
582 return 0 != dlmalloc_all_deallocated();
585 //This test allocates multiple values until there is no more memory
586 //and after that deallocates all in the inverse order
588 bool test_many_different_allocation()
590 dlmalloc_malloc_check();
591 const std::size_t ArraySize
= 11;
592 std::size_t requested_sizes
[ArraySize
];
593 for(std::size_t i
= 0; i
< ArraySize
; ++i
){
594 requested_sizes
[i
] = 4*i
;
597 for( deallocation_type t
= DirectDeallocation
598 ; t
!= EndDeallocationType
599 ; t
= (deallocation_type
)((int)t
+ 1)){
600 //std::size_t free_memory = a.get_free_memory();
602 std::vector
<void*> buffers2
;
604 //Allocate buffers with extra memory
605 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
606 void *ptr
= dlmalloc_malloc(i
);
609 buffers2
.push_back(ptr
);
612 //Now deallocate the half of the blocks
613 //so expand maybe can merge new free blocks
614 for(std::size_t i
= 0, max
= buffers2
.size()
618 dlmalloc_free(buffers2
[i
]);
623 std::vector
<void*> buffers
;
624 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
625 dlmalloc_memchain chain
;
626 BOOST_CONTAINER_MEMCHAIN_INIT(&chain
);
627 dlmalloc_multialloc_arrays(ArraySize
, requested_sizes
, 1, BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS
, &chain
);
628 dlmalloc_memchain_it it
= BOOST_CONTAINER_MEMCHAIN_BEGIN_IT(&chain
);
629 if(BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain
, it
))
632 for(; !BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain
, it
); ++n
){
633 buffers
.push_back(BOOST_CONTAINER_MEMIT_ADDR(it
));
634 BOOST_CONTAINER_MEMIT_NEXT(it
);
641 case DirectDeallocation
:
643 for(std::size_t j
= 0, max
= buffers
.size()
646 dlmalloc_free(buffers
[j
]);
650 case InverseDeallocation
:
652 for(std::size_t j
= buffers
.size()
655 dlmalloc_free(buffers
[j
]);
659 case MixedDeallocation
:
661 for(std::size_t j
= 0, max
= buffers
.size()
664 std::size_t pos
= (j
%4)*(buffers
.size())/4;
665 dlmalloc_free(buffers
[pos
]);
666 buffers
.erase(buffers
.begin()+(std::ptrdiff_t)pos
);
674 //Deallocate the rest of the blocks
676 //Deallocate it in non sequential order
677 for(std::size_t j
= 0, max
= buffers2
.size()
680 std::size_t pos
= (j
%4u)*(buffers2
.size())/4u;
681 dlmalloc_free(buffers2
[pos
]);
682 buffers2
.erase(buffers2
.begin()+(std::ptrdiff_t)pos
);
685 //bool ok = free_memory == a.get_free_memory() &&
686 //a.all_memory_deallocated() && a.check_sanity();
689 dlmalloc_malloc_check();
690 return 0 != dlmalloc_all_deallocated();
693 bool test_many_deallocation()
695 const std::size_t ArraySize
= 11;
696 std::vector
<dlmalloc_memchain
> buffers
;
697 std::size_t requested_sizes
[ArraySize
];
698 for(std::size_t i
= 0; i
< ArraySize
; ++i
){
699 requested_sizes
[i
] = 4*i
;
702 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
703 dlmalloc_memchain chain
;
704 BOOST_CONTAINER_MEMCHAIN_INIT(&chain
);
705 dlmalloc_multialloc_arrays(ArraySize
, requested_sizes
, 1, BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS
, &chain
);
706 dlmalloc_memchain_it it
= BOOST_CONTAINER_MEMCHAIN_BEGIN_IT(&chain
);
707 if(BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain
, it
))
709 buffers
.push_back(chain
);
711 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
712 dlmalloc_multidealloc(&buffers
[i
]);
716 dlmalloc_malloc_check();
717 if(!dlmalloc_all_deallocated())
720 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
721 dlmalloc_memchain chain
;
722 BOOST_CONTAINER_MEMCHAIN_INIT(&chain
);
723 dlmalloc_multialloc_nodes(ArraySize
, i
*4+1, BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS
, &chain
);
724 dlmalloc_memchain_it it
= BOOST_CONTAINER_MEMCHAIN_BEGIN_IT(&chain
);
725 if(BOOST_CONTAINER_MEMCHAIN_IS_END_IT(chain
, it
))
727 buffers
.push_back(chain
);
729 for(std::size_t i
= 0; i
!= NumIt
; ++i
){
730 dlmalloc_multidealloc(&buffers
[i
]);
734 dlmalloc_malloc_check();
735 if(!dlmalloc_all_deallocated())
741 //This function calls all tests
743 bool test_all_allocation()
745 std::cout
<< "Starting test_allocation"
748 if(!test_allocation()){
749 std::cout
<< "test_allocation_direct_deallocation failed"
754 std::cout
<< "Starting test_many_equal_allocation"
757 if(!test_many_equal_allocation()){
758 std::cout
<< "test_many_equal_allocation failed"
763 std::cout
<< "Starting test_many_different_allocation"
766 if(!test_many_different_allocation()){
767 std::cout
<< "test_many_different_allocation failed"
772 std::cout
<< "Starting test_allocation_shrink"
775 if(!test_allocation_shrink()){
776 std::cout
<< "test_allocation_shrink failed"
781 if(!test_allocation_shrink_and_expand()){
782 std::cout
<< "test_allocation_shrink_and_expand failed"
787 std::cout
<< "Starting test_allocation_expand"
790 if(!test_allocation_expand()){
791 std::cout
<< "test_allocation_expand failed"
796 std::cout
<< "Starting test_allocation_deallocation_expand"
799 if(!test_allocation_deallocation_expand()){
800 std::cout
<< "test_allocation_deallocation_expand failed"
805 std::cout
<< "Starting test_allocation_with_reuse"
808 if(!test_allocation_with_reuse()){
809 std::cout
<< "test_allocation_with_reuse failed"
814 std::cout
<< "Starting test_aligned_allocation"
817 if(!test_aligned_allocation()){
818 std::cout
<< "test_aligned_allocation failed"
823 std::cout
<< "Starting test_continuous_aligned_allocation"
826 if(!test_continuous_aligned_allocation()){
827 std::cout
<< "test_continuous_aligned_allocation failed"
832 if(!test_many_deallocation()){
833 std::cout
<< "test_many_deallocation failed"
838 return 0 != dlmalloc_all_deallocated();
841 }}} //namespace boost { namespace container { namespace test {
846 if(!boost::container::test::test_all_allocation())