1/* Emulate Emacs heap dumping to test malloc_set_state.
2 Copyright (C) 2001-2022 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
18
19#include <errno.h>
20#include <stdbool.h>
21#include <stdio.h>
22#include <string.h>
23#include <libc-symbols.h>
24#include <shlib-compat.h>
25#include <support/check.h>
26#include <support/support.h>
27#include <support/test-driver.h>
28
29#include "malloc.h"
30
31/* Make the compatibility symbols availabile to this test case. */
32void *malloc_get_state (void);
33compat_symbol_reference (libc, malloc_get_state, malloc_get_state, GLIBC_2_0);
34int malloc_set_state (void *);
35compat_symbol_reference (libc, malloc_set_state, malloc_set_state, GLIBC_2_0);
36
37/* Maximum object size in the fake heap. */
38enum { max_size = 64 };
39
40/* Allocation actions. These are randomized actions executed on the
41 dumped heap (see allocation_tasks below). They are interspersed
42 with operations on the new heap (see heap_activity). */
43enum allocation_action
44 {
45 action_free, /* Dumped and freed. */
46 action_realloc, /* Dumped and realloc'ed. */
47 action_realloc_same, /* Dumped and realloc'ed, same size. */
48 action_realloc_smaller, /* Dumped and realloc'ed, shrinked. */
49 action_count
50 };
51
52/* Dumped heap. Initialize it, so that the object is placed into the
53 .data section, for increased realism. The size is an upper bound;
54 we use about half of the space. */
55static size_t dumped_heap[action_count * max_size * max_size
56 / sizeof (size_t)] = {1};
57
58/* Next free space in the dumped heap. Also top of the heap at the
59 end of the initialization procedure. */
60static size_t *next_heap_chunk;
61
62/* Copied from malloc.c and hooks.c. The version is deliberately
63 lower than the final version of malloc_set_state. */
64# define NBINS 128
65# define MALLOC_STATE_MAGIC 0x444c4541l
66# define MALLOC_STATE_VERSION (0 * 0x100l + 4l)
67static struct
68{
69 long magic;
70 long version;
71 void *av[NBINS * 2 + 2];
72 char *sbrk_base;
73 int sbrked_mem_bytes;
74 unsigned long trim_threshold;
75 unsigned long top_pad;
76 unsigned int n_mmaps_max;
77 unsigned long mmap_threshold;
78 int check_action;
79 unsigned long max_sbrked_mem;
80 unsigned long max_total_mem;
81 unsigned int n_mmaps;
82 unsigned int max_n_mmaps;
83 unsigned long mmapped_mem;
84 unsigned long max_mmapped_mem;
85 int using_malloc_checking;
86 unsigned long max_fast;
87 unsigned long arena_test;
88 unsigned long arena_max;
89 unsigned long narenas;
90} save_state =
91 {
92 .magic = MALLOC_STATE_MAGIC,
93 .version = MALLOC_STATE_VERSION,
94 };
95
96/* Allocate a blob in the fake heap. */
97static void *
98dumped_heap_alloc (size_t length)
99{
100 /* malloc needs three state bits in the size field, so the minimum
101 alignment is 8 even on 32-bit architectures. malloc_set_state
102 should be compatible with such heaps even if it currently
103 provides more alignment to applications. */
104 enum
105 {
106 heap_alignment = 8,
107 heap_alignment_mask = heap_alignment - 1
108 };
109 _Static_assert (sizeof (size_t) <= heap_alignment,
110 "size_t compatible with heap alignment");
111
112 /* Need at least this many bytes for metadata and application
113 data. */
114 size_t chunk_size = sizeof (size_t) + length;
115 /* Round up the allocation size to the heap alignment. */
116 chunk_size += heap_alignment_mask;
117 chunk_size &= ~heap_alignment_mask;
118 TEST_VERIFY_EXIT ((chunk_size & 3) == 0);
119 if (next_heap_chunk == NULL)
120 /* Initialize the top of the heap. Add one word of zero padding,
121 to match existing practice. */
122 {
123 dumped_heap[0] = 0;
124 next_heap_chunk = dumped_heap + 1;
125 }
126 else
127 /* The previous chunk is allocated. */
128 chunk_size |= 1;
129 *next_heap_chunk = chunk_size;
130
131 /* User data starts after the chunk header. */
132 void *result = next_heap_chunk + 1;
133 next_heap_chunk += chunk_size / sizeof (size_t);
134
135 /* Mark the previous chunk as used. */
136 *next_heap_chunk = 1;
137 return result;
138}
139
140/* Global seed variable for the random number generator. */
141static unsigned long long global_seed;
142
143/* Simple random number generator. The numbers are in the range from
144 0 to UINT_MAX (inclusive). */
145static unsigned int
146rand_next (unsigned long long *seed)
147{
148 /* Linear congruential generated as used for MMIX. */
149 *seed = *seed * 6364136223846793005ULL + 1442695040888963407ULL;
150 return *seed >> 32;
151}
152
153/* Fill LENGTH bytes at BUFFER with random contents, as determined by
154 SEED. */
155static void
156randomize_buffer (unsigned char *buffer, size_t length,
157 unsigned long long seed)
158{
159 for (size_t i = 0; i < length; ++i)
160 buffer[i] = rand_next (seed: &seed);
161}
162
163/* Dumps the buffer to standard output, in hexadecimal. */
164static void
165dump_hex (unsigned char *buffer, size_t length)
166{
167 for (int i = 0; i < length; ++i)
168 printf (format: " %02X", buffer[i]);
169}
170
171/* Set to true if an error is encountered. */
172static bool errors = false;
173
174/* Keep track of object allocations. */
175struct allocation
176{
177 unsigned char *data;
178 unsigned int size;
179 unsigned int seed;
180};
181
182/* Check that the allocation task allocation has the expected
183 contents. */
184static void
185check_allocation (const struct allocation *alloc, int index)
186{
187 size_t size = alloc->size;
188 if (alloc->data == NULL)
189 {
190 printf (format: "error: NULL pointer for allocation of size %zu at %d, seed %u\n",
191 size, index, alloc->seed);
192 errors = true;
193 return;
194 }
195
196 unsigned char expected[4096];
197 if (size > sizeof (expected))
198 {
199 printf (format: "error: invalid allocation size %zu at %d, seed %u\n",
200 size, index, alloc->seed);
201 errors = true;
202 return;
203 }
204 randomize_buffer (buffer: expected, length: size, seed: alloc->seed);
205 if (memcmp (alloc->data, expected, size) != 0)
206 {
207 printf (format: "error: allocation %d data mismatch, size %zu, seed %u\n",
208 index, size, alloc->seed);
209 printf (format: " expected:");
210 dump_hex (buffer: expected, length: size);
211 putc (c: '\n', stdout);
212 printf (format: " actual:");
213 dump_hex (buffer: alloc->data, length: size);
214 putc (c: '\n', stdout);
215 errors = true;
216 }
217}
218
219/* A heap allocation combined with pending actions on it. */
220struct allocation_task
221{
222 struct allocation allocation;
223 enum allocation_action action;
224};
225
226/* Allocation tasks. Initialized by init_allocation_tasks and used by
227 perform_allocations. */
228enum { allocation_task_count = action_count * max_size };
229static struct allocation_task allocation_tasks[allocation_task_count];
230
231/* Fisher-Yates shuffle of allocation_tasks. */
232static void
233shuffle_allocation_tasks (void)
234{
235 for (int i = 0; i < allocation_task_count - 1; ++i)
236 {
237 /* Pick pair in the tail of the array. */
238 int j = i + (rand_next (seed: &global_seed)
239 % ((unsigned) (allocation_task_count - i)));
240 TEST_VERIFY_EXIT (j >= 0 && j < allocation_task_count);
241 /* Exchange. */
242 struct allocation_task tmp = allocation_tasks[i];
243 allocation_tasks[i] = allocation_tasks[j];
244 allocation_tasks[j] = tmp;
245 }
246}
247
248/* Set up the allocation tasks and the dumped heap. */
249static void
250initial_allocations (void)
251{
252 /* Initialize in a position-dependent way. */
253 for (int i = 0; i < allocation_task_count; ++i)
254 allocation_tasks[i] = (struct allocation_task)
255 {
256 .allocation =
257 {
258 .size = 1 + (i / action_count),
259 .seed = i,
260 },
261 .action = i % action_count
262 };
263
264 /* Execute the tasks in a random order. */
265 shuffle_allocation_tasks ();
266
267 /* Initialize the contents of the dumped heap. */
268 for (int i = 0; i < allocation_task_count; ++i)
269 {
270 struct allocation_task *task = allocation_tasks + i;
271 task->allocation.data = dumped_heap_alloc (length: task->allocation.size);
272 randomize_buffer (buffer: task->allocation.data, length: task->allocation.size,
273 seed: task->allocation.seed);
274 }
275
276 for (int i = 0; i < allocation_task_count; ++i)
277 check_allocation (alloc: &allocation_tasks[i].allocation, index: i);
278}
279
280/* Indicates whether init_heap has run. This variable needs to be
281 volatile because malloc is declared __THROW, which implies it is a
282 leaf function, but we expect it to run our hooks. */
283static volatile bool heap_initialized;
284
285/* Executed by glibc malloc, through __malloc_initialize_hook
286 below. */
287static void
288init_heap (void)
289{
290 if (test_verbose)
291 printf (format: "info: performing heap initialization\n");
292 heap_initialized = true;
293
294 /* Populate the dumped heap. */
295 initial_allocations ();
296
297 /* Complete initialization of the saved heap data structure. */
298 save_state.sbrk_base = (void *) dumped_heap;
299 save_state.sbrked_mem_bytes = sizeof (dumped_heap);
300 /* Top pointer. Adjust so that it points to the start of struct
301 malloc_chunk. */
302 save_state.av[2] = (void *) (next_heap_chunk - 1);
303
304 /* Integrate the dumped heap into the process heap. */
305 TEST_VERIFY_EXIT (malloc_set_state (&save_state) == 0);
306}
307
308/* Interpose the initialization callback. */
309void (*volatile __malloc_initialize_hook) (void) = init_heap;
310compat_symbol_reference (libc, __malloc_initialize_hook,
311 __malloc_initialize_hook, GLIBC_2_0);
312
313/* Simulate occasional unrelated heap activity in the non-dumped
314 heap. */
315enum { heap_activity_allocations_count = 32 };
316static struct allocation heap_activity_allocations
317 [heap_activity_allocations_count] = {};
318static int heap_activity_seed_counter = 1000 * 1000;
319
320static void
321heap_activity (void)
322{
323 /* Only do this from time to time. */
324 if ((rand_next (seed: &global_seed) % 4) == 0)
325 {
326 int slot = rand_next (seed: &global_seed) % heap_activity_allocations_count;
327 struct allocation *alloc = heap_activity_allocations + slot;
328 if (alloc->data == NULL)
329 {
330 alloc->size = rand_next (seed: &global_seed) % (4096U + 1);
331 alloc->data = xmalloc (n: alloc->size);
332 alloc->seed = heap_activity_seed_counter++;
333 randomize_buffer (buffer: alloc->data, length: alloc->size, seed: alloc->seed);
334 check_allocation (alloc, index: 1000 + slot);
335 }
336 else
337 {
338 check_allocation (alloc, index: 1000 + slot);
339 free (ptr: alloc->data);
340 alloc->data = NULL;
341 }
342 }
343}
344
345static void
346heap_activity_deallocate (void)
347{
348 for (int i = 0; i < heap_activity_allocations_count; ++i)
349 free (ptr: heap_activity_allocations[i].data);
350}
351
352/* Perform a full heap check across the dumped heap allocation tasks,
353 and the simulated heap activity directly above. */
354static void
355full_heap_check (void)
356{
357 /* Dumped heap. */
358 for (int i = 0; i < allocation_task_count; ++i)
359 if (allocation_tasks[i].allocation.data != NULL)
360 check_allocation (alloc: &allocation_tasks[i].allocation, index: i);
361
362 /* Heap activity allocations. */
363 for (int i = 0; i < heap_activity_allocations_count; ++i)
364 if (heap_activity_allocations[i].data != NULL)
365 check_allocation (alloc: heap_activity_allocations + i, index: i);
366}
367
368/* Used as an optimization barrier to force a heap allocation. */
369__attribute__ ((noinline, noclone))
370static void
371my_free (void *ptr)
372{
373 free (ptr: ptr);
374}
375
376static int
377do_test (void)
378{
379 my_free (ptr: malloc (size: 1));
380 TEST_VERIFY_EXIT (heap_initialized);
381
382 /* The first pass performs the randomly generated allocation
383 tasks. */
384 if (test_verbose)
385 printf (format: "info: first pass through allocation tasks\n");
386 full_heap_check ();
387
388 /* Execute the post-undump tasks in a random order. */
389 shuffle_allocation_tasks ();
390
391 for (int i = 0; i < allocation_task_count; ++i)
392 {
393 heap_activity ();
394 struct allocation_task *task = allocation_tasks + i;
395 switch (task->action)
396 {
397 case action_free:
398 check_allocation (alloc: &task->allocation, index: i);
399 free (ptr: task->allocation.data);
400 task->allocation.data = NULL;
401 break;
402
403 case action_realloc:
404 check_allocation (alloc: &task->allocation, index: i);
405 task->allocation.data = xrealloc
406 (o: task->allocation.data, n: task->allocation.size + max_size);
407 check_allocation (alloc: &task->allocation, index: i);
408 break;
409
410 case action_realloc_same:
411 check_allocation (alloc: &task->allocation, index: i);
412 task->allocation.data = xrealloc
413 (o: task->allocation.data, n: task->allocation.size);
414 check_allocation (alloc: &task->allocation, index: i);
415 break;
416
417 case action_realloc_smaller:
418 check_allocation (alloc: &task->allocation, index: i);
419 size_t new_size = task->allocation.size - 1;
420 task->allocation.data = xrealloc (o: task->allocation.data, n: new_size);
421 if (new_size == 0)
422 {
423 if (task->allocation.data != NULL)
424 {
425 printf (format: "error: realloc with size zero did not deallocate\n");
426 errors = true;
427 }
428 /* No further action on this task. */
429 task->action = action_free;
430 }
431 else
432 {
433 task->allocation.size = new_size;
434 check_allocation (alloc: &task->allocation, index: i);
435 }
436 break;
437
438 case action_count:
439 FAIL_EXIT1 ("task->action should never be action_count");
440 }
441 full_heap_check ();
442 }
443
444 /* The second pass frees the objects which were allocated during the
445 first pass. */
446 if (test_verbose)
447 printf (format: "info: second pass through allocation tasks\n");
448
449 shuffle_allocation_tasks ();
450 for (int i = 0; i < allocation_task_count; ++i)
451 {
452 heap_activity ();
453 struct allocation_task *task = allocation_tasks + i;
454 switch (task->action)
455 {
456 case action_free:
457 /* Already freed, nothing to do. */
458 break;
459
460 case action_realloc:
461 case action_realloc_same:
462 case action_realloc_smaller:
463 check_allocation (alloc: &task->allocation, index: i);
464 free (ptr: task->allocation.data);
465 task->allocation.data = NULL;
466 break;
467
468 case action_count:
469 FAIL_EXIT1 ("task->action should never be action_count");
470 }
471 full_heap_check ();
472 }
473
474 heap_activity_deallocate ();
475
476 /* Check that the malloc_get_state stub behaves in the intended
477 way. */
478 errno = 0;
479 if (malloc_get_state () != NULL)
480 {
481 printf (format: "error: malloc_get_state succeeded\n");
482 errors = true;
483 }
484 if (errno != ENOSYS)
485 {
486 printf (format: "error: malloc_get_state: %m\n");
487 errors = true;
488 }
489
490 return errors;
491}
492
493#include <support/test-driver.c>
494

source code of glibc/malloc/tst-mallocstate.c