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