1/* Debug allocators for the Expat test suite
2                            __  __            _
3                         ___\ \/ /_ __   __ _| |_
4                        / _ \\  /| '_ \ / _` | __|
5                       |  __//  \| |_) | (_| | |_
6                        \___/_/\_\ .__/ \__,_|\__|
7                                 |_| XML parser
8
9   Copyright (c) 1997-2000 Thai Open Source Software Center Ltd
10   Copyright (c) 2000-2017 Expat development team
11   Licensed under the MIT license:
12
13   Permission is  hereby granted,  free of charge,  to any  person obtaining
14   a  copy  of  this  software   and  associated  documentation  files  (the
15   "Software"),  to  deal in  the  Software  without restriction,  including
16   without  limitation the  rights  to use,  copy,  modify, merge,  publish,
17   distribute, sublicense, and/or sell copies of the Software, and to permit
18   persons  to whom  the Software  is  furnished to  do so,  subject to  the
19   following conditions:
20
21   The above copyright  notice and this permission notice  shall be included
22   in all copies or substantial portions of the Software.
23
24   THE  SOFTWARE  IS  PROVIDED  "AS  IS",  WITHOUT  WARRANTY  OF  ANY  KIND,
25   EXPRESS  OR IMPLIED,  INCLUDING  BUT  NOT LIMITED  TO  THE WARRANTIES  OF
26   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
27   NO EVENT SHALL THE AUTHORS OR  COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
28   DAMAGES OR  OTHER LIABILITY, WHETHER  IN AN  ACTION OF CONTRACT,  TORT OR
29   OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
30   USE OR OTHER DEALINGS IN THE SOFTWARE.
31*/
32
33#include <stdio.h>
34#include <stdlib.h>
35#include "memcheck.h"
36
37
38/* Structures to keep track of what has been allocated.  Speed isn't a
39 * big issue for the tests this is required for, so we will use a
40 * doubly-linked list to make deletion easier.
41 */
42
43typedef struct allocation_entry {
44    struct allocation_entry * next;
45    struct allocation_entry * prev;
46    void * allocation;
47    size_t num_bytes;
48} AllocationEntry;
49
50static AllocationEntry *alloc_head = NULL;
51static AllocationEntry *alloc_tail = NULL;
52
53static AllocationEntry *find_allocation(void *ptr);
54
55
56/* Allocate some memory and keep track of it. */
57void *
58tracking_malloc(size_t size)
59{
60    AllocationEntry *entry = malloc(sizeof(AllocationEntry));
61
62    if (entry == NULL) {
63        printf("Allocator failure\n");
64        return NULL;
65    }
66    entry->num_bytes = size;
67    entry->allocation = malloc(size);
68    if (entry->allocation == NULL) {
69        free(entry);
70        return NULL;
71    }
72    entry->next = NULL;
73
74    /* Add to the list of allocations */
75    if (alloc_head == NULL) {
76        entry->prev = NULL;
77        alloc_head = alloc_tail = entry;
78    } else {
79        entry->prev = alloc_tail;
80        alloc_tail->next = entry;
81        alloc_tail = entry;
82    }
83
84    return entry->allocation;
85}
86
87static AllocationEntry *
88find_allocation(void *ptr)
89{
90    AllocationEntry *entry;
91
92    for (entry = alloc_head; entry != NULL; entry = entry->next) {
93        if (entry->allocation == ptr) {
94            return entry;
95        }
96    }
97    return NULL;
98}
99
100/* Free some memory and remove the tracking for it */
101void
102tracking_free(void *ptr)
103{
104    AllocationEntry *entry;
105
106    if (ptr == NULL) {
107        /* There won't be an entry for this */
108        return;
109    }
110
111    entry = find_allocation(ptr);
112    if (entry != NULL) {
113        /* This is the relevant allocation.  Unlink it */
114        if (entry->prev != NULL)
115            entry->prev->next = entry->next;
116        else
117            alloc_head = entry->next;
118        if (entry->next != NULL)
119            entry->next->prev = entry->prev;
120        else
121            alloc_tail = entry->next;
122        free(entry);
123    } else {
124        printf("Attempting to free unallocated memory at %p\n", ptr);
125    }
126    free(ptr);
127}
128
129/* Reallocate some memory and keep track of it */
130void *
131tracking_realloc(void *ptr, size_t size)
132{
133    AllocationEntry *entry;
134
135    if (ptr == NULL) {
136        /* By definition, this is equivalent to malloc(size) */
137        return tracking_malloc(size);
138    }
139    if (size == 0) {
140        /* By definition, this is equivalent to free(ptr) */
141        tracking_free(ptr);
142        return NULL;
143    }
144
145    /* Find the allocation entry for this memory */
146    entry = find_allocation(ptr);
147    if (entry == NULL) {
148        printf("Attempting to realloc unallocated memory at %p\n", ptr);
149        entry = malloc(sizeof(AllocationEntry));
150        if (entry == NULL) {
151            printf("Reallocator failure\n");
152            return NULL;
153        }
154        entry->allocation = realloc(ptr, size);
155        if (entry->allocation == NULL) {
156            free(entry);
157            return NULL;
158        }
159
160        /* Add to the list of allocations */
161        entry->next = NULL;
162        if (alloc_head == NULL) {
163            entry->prev = NULL;
164            alloc_head = alloc_tail = entry;
165        } else {
166            entry->prev = alloc_tail;
167            alloc_tail->next = entry;
168            alloc_tail = entry;
169        }
170    } else {
171        entry->allocation = realloc(ptr, size);
172        if (entry->allocation == NULL) {
173            /* Realloc semantics say the original is still allocated */
174            entry->allocation = ptr;
175            return NULL;
176        }
177    }
178
179    entry->num_bytes = size;
180    return entry->allocation;
181}
182
183int
184tracking_report(void)
185{
186    AllocationEntry *entry;
187
188    if (alloc_head == NULL)
189        return 1;
190
191    /* Otherwise we have allocations that haven't been freed */
192    for (entry = alloc_head; entry != NULL; entry = entry->next)
193    {
194        printf("Allocated %lu bytes at %p\n",
195                (long unsigned)entry->num_bytes, entry->allocation);
196    }
197    return 0;
198}
199