universe@422: /*
universe@422:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@422:  *
universe@422:  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
universe@422:  *
universe@422:  * Redistribution and use in source and binary forms, with or without
universe@422:  * modification, are permitted provided that the following conditions are met:
universe@422:  *
universe@422:  *   1. Redistributions of source code must retain the above copyright
universe@422:  *      notice, this list of conditions and the following disclaimer.
universe@422:  *
universe@422:  *   2. Redistributions in binary form must reproduce the above copyright
universe@422:  *      notice, this list of conditions and the following disclaimer in the
universe@422:  *      documentation and/or other materials provided with the distribution.
universe@422:  *
universe@422:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@422:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@422:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@422:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@422:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@422:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@422:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@422:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@422:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@422:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@422:  * POSSIBILITY OF SUCH DAMAGE.
universe@422:  */
universe@422: 
universe@422: #include "util_allocator.h"
universe@770: #include "cx/test.h"
universe@422: 
universe@770: static void cx_testing_allocator_track(CxTestingAllocator *alloc, void *ptr) {
universe@770:     for (size_t i = 0; i < alloc->tracked_count; i++) {
universe@770:         if (alloc->tracked[i] == ptr) return; // is already tracked
universe@770:     }
universe@770: 
universe@770:     if (alloc->tracked_count == alloc->tracked_capacity) {
universe@770:         size_t newcapa = alloc->tracked_capacity + 64;
universe@770:         void *newarr = realloc(alloc->tracked, newcapa * sizeof(void *));
universe@770:         if (newarr == NULL) abort();
universe@770:         alloc->tracked = newarr;
universe@770:         alloc->tracked_capacity = newcapa;
universe@770:     }
universe@770: 
universe@770:     alloc->tracked[alloc->tracked_count] = ptr;
universe@770:     alloc->tracked_count++;
universe@770: }
universe@770: 
universe@770: static bool cx_testing_allocator_untrack(CxTestingAllocator *alloc, void *ptr) {
universe@770:     for (size_t i = 0; i < alloc->tracked_count; i++) {
universe@770:         if (alloc->tracked[i] == ptr) {
universe@770:             size_t last = alloc->tracked_count - 1;
universe@770:             if (i < last) {
universe@770:                 alloc->tracked[i] = alloc->tracked[last];
universe@770:             }
universe@770:             alloc->tracked_count--;
universe@770:             return true;
universe@770:         }
universe@770:     }
universe@770:     return false;
universe@770: }
universe@770: 
universe@770: static void *cx_malloc_testing(void *d, size_t n) {
universe@770:     CxTestingAllocator *data = d;
universe@422:     void *ptr = malloc(n);
universe@422:     data->alloc_total++;
universe@770:     if (ptr == NULL) {
universe@422:         data->alloc_failed++;
universe@422:     } else {
universe@770:         cx_testing_allocator_track(data, ptr);
universe@422:     }
universe@422:     return ptr;
universe@422: }
universe@422: 
universe@770: static void *cx_realloc_testing(void *d, void *mem, size_t n) {
universe@770:     CxTestingAllocator *data = d;
universe@422:     void *ptr = realloc(mem, n);
universe@422:     if (ptr == mem) {
universe@422:         return ptr;
universe@422:     } else {
universe@422:         data->alloc_total++;
universe@770:         if (ptr == NULL) {
universe@422:             data->alloc_failed++;
universe@422:         } else {
universe@422:             data->free_total++;
universe@770:             if (!cx_testing_allocator_untrack(data, mem)) {
universe@422:                 data->free_failed++;
universe@422:             }
universe@770:             cx_testing_allocator_track(data, ptr);
universe@422:         }
universe@422:         return ptr;
universe@422:     }
universe@422: }
universe@422: 
universe@770: static void *cx_calloc_testing(void *d, size_t nelem, size_t n) {
universe@770:     CxTestingAllocator *data = d;
universe@422:     void *ptr = calloc(nelem, n);
universe@422:     data->alloc_total++;
universe@770:     if (ptr == NULL) {
universe@422:         data->alloc_failed++;
universe@422:     } else {
universe@770:         cx_testing_allocator_track(data, ptr);
universe@422:     }
universe@422:     return ptr;
universe@422: }
universe@422: 
universe@770: static void cx_free_testing(void *d, void *mem) {
universe@770:     CxTestingAllocator *data = d;
universe@422:     data->free_total++;
universe@770:     if (cx_testing_allocator_untrack(data, mem)) {
universe@770:         free(mem);
universe@770:     } else {
universe@422:         data->free_failed++;
universe@422:         // do not even attempt to free mem, because it is likely to segfault
universe@422:     }
universe@422: }
universe@422: 
universe@422: cx_allocator_class cx_testing_allocator_class = {
universe@422:         cx_malloc_testing,
universe@422:         cx_realloc_testing,
universe@422:         cx_calloc_testing,
universe@422:         cx_free_testing
universe@422: };
universe@422: 
universe@770: 
universe@770: void cx_testing_allocator_init(CxTestingAllocator *alloc) {
universe@770:     alloc->base.cl = &cx_testing_allocator_class;
universe@770:     alloc->base.data = alloc;
universe@770:     alloc->alloc_failed = 0;
universe@770:     alloc->alloc_total = 0;
universe@770:     alloc->free_failed = 0;
universe@770:     alloc->free_total = 0;
universe@770:     size_t initial_capa = 16;
universe@770:     alloc->tracked_capacity = initial_capa;
universe@770:     alloc->tracked_count = 0;
universe@770:     alloc->tracked = calloc(sizeof(void *), initial_capa);
universe@422: }
universe@422: 
universe@770: void cx_testing_allocator_destroy(CxTestingAllocator *alloc) {
universe@770:     free(alloc->tracked);
universe@571: }
universe@571: 
universe@770: bool cx_testing_allocator_used(CxTestingAllocator const *alloc) {
universe@770:     return alloc->alloc_total > 0;
universe@770: }
universe@770: 
universe@770: bool cx_testing_allocator_verify(CxTestingAllocator const *alloc) {
universe@770:     return alloc->tracked_count == 0 && alloc->alloc_failed == 0 && alloc->free_failed == 0
universe@770:            && alloc->alloc_total == alloc->free_total;
universe@422: }
universe@518: 
universe@518: // SELF-TEST
universe@518: 
universe@770: CX_TEST(test_util_allocator_expect_free) {
universe@770:     CxTestingAllocator talloc;
universe@770:     cx_testing_allocator_init(&talloc);
universe@770:     CxAllocator *alloc = &talloc.base;
universe@770:     CX_TEST_DO {
universe@770:         CX_TEST_ASSERTM(cx_testing_allocator_verify(&talloc),
universe@770:                         "Fresh testing allocator fails to verify.");
universe@770:         CX_TEST_ASSERTM(!cx_testing_allocator_used(&talloc),
universe@770:                         "Fresh testing allocator already used.");
universe@770:         void *ptr = cxMalloc(alloc, 16);
universe@770:         CX_TEST_ASSERTM(!cx_testing_allocator_verify(&talloc),
universe@770:                         "Testing allocator verifies with unfreed memory.");
universe@770:         CX_TEST_ASSERT(cx_testing_allocator_used(&talloc));
universe@770:         CX_TEST_ASSERT(ptr != NULL);
universe@518: 
universe@770:         cxFree(alloc, ptr);
universe@770:         CX_TEST_ASSERTM(cx_testing_allocator_verify(&talloc),
universe@770:                         "Testing allocator fails to verify after everything freed.");
universe@770:     }
universe@770:     cx_testing_allocator_destroy(&talloc);
universe@518: }
universe@518: 
universe@770: CX_TEST(test_util_allocator_detect_double_free) {
universe@770:     CxTestingAllocator talloc;
universe@770:     cx_testing_allocator_init(&talloc);
universe@770:     CxAllocator *alloc = &talloc.base;
universe@770:     CX_TEST_DO {
universe@770:         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
universe@770:         void *ptr = cxMalloc(alloc, 16);
universe@770:         CX_TEST_ASSERT(ptr != NULL);
universe@770:         cxFree(alloc, ptr);
universe@770:         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
universe@770:         cxFree(alloc, ptr);
universe@770:         CX_TEST_ASSERTM(!cx_testing_allocator_verify(&talloc),
universe@770:                         "Testing allocator does not detect double-free.");
universe@770:     }
universe@770:     cx_testing_allocator_destroy(&talloc);
universe@518: }
universe@518: 
universe@770: CX_TEST(test_util_allocator_free_untracked) {
universe@770:     CxTestingAllocator talloc;
universe@770:     cx_testing_allocator_init(&talloc);
universe@770:     CxAllocator *alloc = &talloc.base;
universe@770:     void *ptr = malloc(16);
universe@770:     CX_TEST_DO {
universe@770:         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
universe@770:         cxFree(alloc, ptr);
universe@770:         CX_TEST_ASSERTM(!cx_testing_allocator_verify(&talloc),
universe@770:                         "Testing allocator does not detect free of untracked memory.");
universe@770:     }
universe@770:     free(ptr);
universe@770:     cx_testing_allocator_destroy(&talloc);
universe@518: }
universe@518: 
universe@770: CX_TEST(test_util_allocator_full_lifecycle_with_realloc) {
universe@770:     CxTestingAllocator talloc;
universe@770:     cx_testing_allocator_init(&talloc);
universe@770:     CxAllocator *alloc = &talloc.base;
universe@770:     CX_TEST_DO {
universe@770:         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
universe@770:         void *ptr = cxMalloc(alloc, 16);
universe@770:         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
universe@770:         CX_TEST_ASSERT(ptr != NULL);
universe@770:         CX_TEST_ASSERT(talloc.tracked_count == 1);
universe@770:         ptr = cxRealloc(alloc, ptr, 256);
universe@770:         CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
universe@770:         CX_TEST_ASSERT(ptr != NULL);
universe@770:         CX_TEST_ASSERT(talloc.tracked_count == 1);
universe@770:         cxFree(alloc, ptr);
universe@770:         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
universe@770:     }
universe@770:     cx_testing_allocator_destroy(&talloc);
universe@518: }
universe@518: 
universe@770: CX_TEST(test_util_allocator_calloc_initializes) {
universe@770:     CxTestingAllocator talloc;
universe@770:     cx_testing_allocator_init(&talloc);
universe@770:     CxAllocator *alloc = &talloc.base;
universe@770:     CX_TEST_DO {
universe@770:         const char zeros[16] = {0};
universe@770:         void *ptr = cxCalloc(alloc, 16, 1);
universe@770:         CX_TEST_ASSERT(memcmp(ptr, zeros, 16) == 0);
universe@770:         cxFree(alloc, ptr);
universe@770:         CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
universe@770:     }
universe@770:     cx_testing_allocator_destroy(&talloc);
universe@518: }
universe@770: 
universe@770: CxTestSuite *cx_test_suite_testing_allocator(void) {
universe@770:     CxTestSuite *suite = cx_test_suite_new("testing allocator self-test");
universe@770: 
universe@770:     cx_test_register(suite, test_util_allocator_expect_free);
universe@770:     cx_test_register(suite, test_util_allocator_detect_double_free);
universe@770:     cx_test_register(suite, test_util_allocator_free_untracked);
universe@770:     cx_test_register(suite, test_util_allocator_full_lifecycle_with_realloc);
universe@770:     cx_test_register(suite, test_util_allocator_calloc_initializes);
universe@770: 
universe@770:     return suite;
universe@770: }
universe@770: