1 /*---------------------------------------------------------------------------
2 * SMalloc Memory Manager
3 *
4 * Written and put into the public domain by Sean T. "Satoria" Barrett.
5 * FAST_FIT algorithm by Joern Rennecke.
6 * Small block consolidation by Lars Duening.
7 *---------------------------------------------------------------------------
8 * Satoria's malloc intended to be optimized for lpmud. This memory manager
9 * distinguishes between two sizes of blocks: small and large. It manages
10 * them separately in the hopes of avoiding fragmentation between them.
11 * It expects small blocks to mostly be temporaries. It expects an equal
12 * number of future requests as small block deallocations.
13 *
14 * smalloc IS NOT THREADSAFE. And the wrong way of fixing this would be
15 * to wrap all mem_alloc()/mem_free() calls into a mutex. The right way of doing
16 * this would be to allocate a set of management structures for each thread
17 * so that only the calls to system malloc()/sbrk() need to be guarded
18 * by mutexes.
19 *
20 * Allocations are measured in 'word_t's which are the same size as void*.
21 *
22 * For MALLOC_CHECK the allocated blocks are tagged with magic words. This
23 * costs a bit of time and memory, but is a good defense against the most
24 * basic memory misuses.
25 *
26 *
27 * -- Small Blocks --
28 *
29 * Small blocks are allocations of up to (SMALL_BLOCK_NUM+1)*4 Bytes, currently
30 * 68 Bytes. Such blocks are initially allocated from large memory blocks,
31 * called "small chunks", of 16 or 32 KByte size.
32 *
33 * To reduce fragmentation, the initial small chunk (ok, the first small chunk
34 * allocated after all arguments have been parsed) is of size
35 * min_small_malloced, hopefully chosen to be a large multiple of the typical
36 * small chunk size.
37 *
38 * When a small block is freed, it is entered in a free doubly-linked list
39 * for blocks of its size, so that later allocations can use the
40 * pre-allocated blocks in the free lists. The free lists use the first
41 * and last word in the "user area" for their link pointers; the small
42 * chunks are themselves kept in a list and use their first word for the
43 * list pointer. Small free blocks are defragmented as described below.
44 *
45 * If a small block can't be allocated from the appropriate free list nor
46 * the small chunk, the system tries two more strategies before allocating
47 * a new small chunk. First, it checks the list of oversized free small
48 * blocks for a block large enough to be split.
49 * If no such block exists,
50 * the allocator then searches the freelists of larger block sizes for a
51 * possible split.
52 * If finally a new small chunk has to be allocated, the memory not used to
53 * satisfy the allocation is entered as new oversized free small block into
54 * the appropriate freelist.
55 *
56 * When a small free block is split, the allocator makes sure that the
57 * remaining block is of at least SMALL_BLOCK_SPLIT_MIN words size (currently
58 * 3 words -> 12 Bytes).
59 * Experience has shown that the gamedriver doesn't need that many blocks of
60 * less than 12 Bytes. If the allocator's splits generated those small blocks,
61 * they would never be used and just tie up free space.
62 *
63 * To reduce memory fragmentation, the allocator implements a lazy
64 * defragmentation scheme for the small blocks: if checking free lists doesn't
65 * yield a suitable block, the allocator defragments the free lists and tries
66 * again. Only if this second attempt fails, a new small chunk is allocated.
67 * To save time, the defragmentation-on-allocation is terminated if a suitable
68 * block is can be constructed (but not before the current list under
69 * examination has been fully defragmented); a full defragmentation happens
70 * only as part of a garbage collection.
71 *
72 * Obviously the defragmenter can eat up a lot of time when the free lists
73 * get long, especially since most blocks can't be defragmented. So as an
74 * optimization the defragmenter sets the M_DEFRAG flag in each block it
75 * visited and decided as non-defragmentable. Newly freed blocks don't have
76 * this flag set and are also entered at the head of their free list; this way
77 * the defragmenter can stop scanning a free list as soon as it reaches the
78 * first block flagged to be non-defragmentable. And while it is possible
79 * that a flagged block changes to be defragmentable after all, this can
80 * happen only if another block is newly freed, and the defragmenter is
81 * guaranteed to find that one.
82 *
83 * -- Large Blocks --
84 *
85 * Large blocks are allocated from the system - if large allocation is
86 * too small (less than 256 KByte), the allocator allocates a 256 KByte
87 * block and enters the 'unnecessary' extra memory into the freelist.
88 * Large blocks are stored with boundary tags: the size field without flags
89 * is replicated in the last word of the block.
90 *
91 * The free large blocks are stored in an AVL tree for fast retrieval
92 * of best fits. The AVL structures are stored in the user area of the blocks.
93 *
94 #ifdef USE_AVL_FREELIST
95 * An AVL node is created for every distinct size of a large free block;
96 * if additional blocks of the same size are freed, they are kept in
97 * a double-linked list hanging of the node. Intention of this setup
98 * is to decrease the size of the AVL tree (and thus increase the
99 * locality large block lookups) in the case of multiple blocks of the
100 * same size.
101 *
102 * The double-links are not really required, as only the first block on the
103 * freelist or the node itself are selected for allocation, but it's
104 * algorithmically simple to implement, and we have the memory for the
105 * second pointer.
106 #ifdef MALLOC_ORDER_LARGE_FREELISTS
107 * The freelist is ordered by the starting address of the blocks (with
108 * the likely exception of the block holding the AVL node), in an attempt
109 * to reduce high heap fragmentation.
110 #endif
111 #else
112 * A new AVL node is created for every free large block.
113 #endif
114 *
115 #ifdef MALLOC_SBRK && SBRK_OK
116 * Memory is allocated from the system with sbrk() and brk(), which puts
117 * the whole heap under our control.
118 *
119 * In this mode, we replace the system malloc() and free() by our own
120 * functions, implementing all libc memory functions (malloc, free, calloc,
121 * realloc()).
122 #elif MALLOC_SBRK && HAVE_MMAP
123 * If brk/sbrk() are non-functional (e.g. on Darwin; remember: they are legacy
124 * and not POSIX anymore), we check if mmap() is available. If it is, we use
125 * it to map anonymous memory pages to get memory from the VM system.
126 *
127 * The allocated block (modulo joints) is tagged at both ends with fake
128 * "allocated" blocks of which cover the unallocated areas - large_malloc()
129 * will perceive this as a fragmented heap.
130 *
131 * In this mode, we replace the system malloc() and free() by our own
132 * functions, implementing all libc memory functions (malloc, free, calloc,
133 * realloc()).
134 #else
135 * malloc() is used to allocate a new block of memory. If this block borders
136 * previous ones, the blocks are joined.
137 *
138 * The allocated block (modulo joints) is tagged at both ends with fake
139 * "allocated" blocks of which cover the unallocated areas - large_malloc()
140 * will perceive this as a fragmented heap.
141 #endif
142 *
143 * -- Privilege Level --
144 *
145 * Memory is managed at three privilege levels: USER, MASTER and SYSTEM.
146 * For every level, a special memory reserve is held by the backend.
147 * If the system runs out of memory (or if the max_malloced limit has
148 * been reached), the following steps are taken:
149 *
150 * - free the user reserve, then try again.
151 * - if MASTER privilege: free the master reserve, then try again.
152 * - if SYSTEM privilege: free the system reserve, then try again.
153 * - if !SYSTEM privilege: set out_of_memory and return NULL
154 * - if SYSTEM privilege: dump the lpc backtrace and exit(2) resp. fatal().
155 *
156 * If any of the reserves is freed, the gc_request flag is set.
157 *
158 *
159 * -- Block Structure --
160 *
161 * The zeroth word in each large block is used to hold the size of the
162 * block (incl. all overhead). This extra word is necessary as on some
163 * systems large blocks can span half of the address space; however, it
164 * is necessary only for large blocks.
165 *
166 * The first word in each allocated block is used for the 'flag&size' field
167 * which holds the flags for a block, plust for small blocks the size (incl.
168 * all overhead):
169 *
170 * THIS_BLOCK: small: set if this block is not allocated
171 * large: set if this block is allocated
172 * PREV_BLOCK: small: set if the previous block is not allocated
173 * large: set if the previous block is allocated
174 * M_GC_FREE : set in allocated blocks if the GC may free this block if
175 * found lost
176 * M_DEFRAG : set in small free blocks which can't be defragmented further
177 * M_REF : set if this block is referenced (used during a GC)
178 *
179 * Because of the PREV_BLOCK flag, all chunk allocations (either the
180 * small chunks for the small block allocator, or the esbrk() chunks for the
181 * large block allocator) are initialized with a fake permanently allocatod
182 * block at the end of the chunk, consisting of not much more than the
183 * flag&size field with THIS_BLOCK cleared.
184 *
185 #ifdef MALLOC_CHECK
186 * The second word holds the magic word, which for small blocks is determined
187 * also by the size of the block.
188 #endif
189 *
190 * When accessing these header fields, the code in general keeps a pointer
191 * to the flag&size word.
192 *
193 * The user (aka payload) area of free blocks is used to manage the various
194 * free lists.
195 *
196 * Small free blocks:
197 *
198 * The first word of the user area holds the 'next' link of the free
199 * list, which is NULL for the last block in the list.
200 *
201 * The last word in the user area holds the 'prev' link of the free
202 * list, which for the first block in the list points to the block
203 * itself.
204 *
205 * For an oversized small block, the 'prev' link has the lowest bit
206 * set, and the second-to-last word in the user area holds the size
207 * of the block in words.
208 *
209 * This setup allows the allocator to determine the size of a preceeding
210 * free block by simply following the 'prev' link for normally sized
211 * blocks, and by directly reading the size for an oversize block. At the
212 * same time the management structure requires just two words at minimum.
213 *
214 * Large free blocks:
215 *
216 * The first words of the user area hold the AVL tree node structure.
217 *
218 * The last word in the user area holds the size of the block in words.
219 *
220 #ifdef HAVE_MADVISE
221 * TODO: Not tested for in configure, not documented.
222 #endif
223 *---------------------------------------------------------------------------
224 */
225
226 #include "driver.h"
227 #include "typedefs.h"
228
229 #if defined(HAVE_MADVISE) || defined(HAVE_MMAP) || defined(HAVE_POSIX_MADVISE)
230 # include <sys/types.h>
231 # include <sys/mman.h>
232 #endif
233
234 #ifdef HAVE_MADVISE
235 # define MADVISE(new,old) madvise(new,old,MADV_RANDOM)
236 #else
237 # define MADVISE(new,old) NOOP
238 #endif
239
240 // for sysconf()
241 #include <unistd.h>
242
243 #include "smalloc.h"
244
245 #include "mstrings.h"
246 #include "stdstrings.h"
247 #include "svalue.h"
248 #ifdef MALLOC_EXT_STATISTICS
249 #include "array.h"
250 #include "backend.h"
251 #endif /* MALLOC_EXT_STATISTICS */
252
253 #include "../mudlib/sys/debug_info.h"
254
255 /* This is the granularity of memory allocations.
256 * WARNING: This MUST be sizeof(word_t) at the moment. If you want to change
257 * the granularity, you have to check the whole allocator first... (Or change
258 * word_t.)
259 * word_t is defined in xalloc.c as being p_uint, that is, it has always the
260 * size of a pointer.
261 */
262 #define GRANULARITY sizeof(word_t)
263
264 /* If possible, request memory using sbrk().
265 * If sbrk/brk() are not working, but mmap() is, then use mmap() for getting
266 * memory. If that is also not available, use malloc().
267 */
268 #if defined(SBRK_OK)
269 # ifdef MALLOC_SBRK
270 # define REPLACE_MALLOC
271 # else
272 # undef SBRK_OK
273 # endif
274 #elif defined (HAVE_MMAP)
275 # ifdef MALLOC_SBRK
276 # define REPLACE_MALLOC
277 # endif
278 #endif // SBRK_OK
279
280 #define MEM_MAIN_THREADSAFE
281
282 /* #undef NO_MEM_BLOCK_SIZE */
283
284 /* Initialiser macros for the tables */
285
286 #define INIT4 0, 0, 0, 0
287 #define INIT4 0, 0, 0, 0
288 #define INIT8 INIT4, INIT4
289 #define INIT12 INIT8, INIT4
290 #define INIT16 INIT8, INIT8
291 #define INIT24 INIT16, INIT8
292 #define INIT32 INIT16, INIT16
293
294 /*-------------------------------------------------------------------------*/
295
296 /* A handy macro to statically determine the number of
297 * elements in an array.
298 */
299 #define NELEM(a) (sizeof (a) / sizeof (a)[0])
300
301 /* #undef DEBUG_AVL */
302 /* Define this to debug the AVL tree.
303 */
304
305 /* The extra smalloc header fields.
306 */
307
308 #define M_LSIZE (-1) /* (word_t) Size in word_t (large blocks only) */
309 #define M_SIZE (0) /* (word_t) Size in word_t, plus some flags */
310
311 #ifdef MALLOC_CHECK
312 # define M_OVERHEAD (2)
313 # define M_MAGIC (1) /* (word_t) The magic word */
314 #else
315 # define M_OVERHEAD (1)
316 #endif /* MALLOC_CHECK */
317
318 #define ML_OVERHEAD (M_OVERHEAD+1)
319 /* The overhead for large blocks. */
320
321 #define M_LINK M_OVERHEAD
322 /* Index of the 'next' link for the small free lists */
323
324 #define M_PLINK(size) ((size)-1)
325 /* Index of the 'prev' link for the small free lists.
326 * <size> is the block size in words.
327 */
328
329 #define BLOCK_NEXT(block) ((word_t *)(block[M_LINK]))
330 /* The 'next' link of free block <block>, properly typed */
331
332 #define BLOCK_PREV(block,size) ((word_t *)(block[M_PLINK(size)]))
333 /* The 'prev' link of free block <block>, properly typed */
334
335
336 #define T_OVERHEAD (M_OVERHEAD + XM_OVERHEAD)
337 /* Total overhead: it is used by smalloc to make smart decisions
338 * about when to split blocks.
339 */
340
341 #define TL_OVERHEAD (ML_OVERHEAD + XM_OVERHEAD)
342 /* Total overhead for large blocks.
343 */
344
345 #define SMALL_BLOCK_MIN (2)
346 /* Minimum size of a small block in words */
347
348 #define SMALL_BLOCK_NUM (16)
349 /* Number of different small block sizes.
350 */
351
352 #define INIT_SMALL_BLOCK INIT16
353 /* The proper initializer macro for all tables sized SMALL_BLOCK_NUM.
354 */
355
356 #define SMALL_BLOCK_SPLIT_MIN (3)
357 /* Minimum size of a small block created by a split, in words */
358
359 /* Derived values */
360
361 #define SMALL_BLOCK_MIN_BYTES (SMALL_BLOCK_MIN * GRANULARITY)
362 /* Minimum payload size of a small block.
363 */
364
365 #define SMALL_BLOCK_MAX (SMALL_BLOCK_NUM-1 + T_OVERHEAD + SMALL_BLOCK_MIN)
366 /* The maximum size (incl. overhead) of a small block in words
367 */
368
369 #define SMALL_BLOCK_MAX_BYTES ((SMALL_BLOCK_NUM-1 + SMALL_BLOCK_MIN) * GRANULARITY)
370 /* Maximum payload size of a small block.
371 */
372
373
374 /* The chunk sizes.
375 * SMALL_CHUNK_SIZE: size of a chunk from which small blocks
376 * are allocated. The actual allocation size is
377 * SMALL_CHUNK_SIZE+sizeof(word_t*) to account for the block list
378 * pointer.
379 * CHUNK_SIZE: size of a chunk from which large blocks are allocated.
380 */
381
382 #if defined(MALLOC_SBRK) && (defined(SBRK_OK) || defined (HAVE_MMAP))
383 # define SMALL_CHUNK_SIZE 0x04000 /* 16 KByte */
384 # define CHUNK_SIZE 0x40000
385 #else
386 /* It seems to be advantagous to be just below a power of two
387 * make sure that the resulting chunk sizes are GRANULARITY aligned.
388 */
389 # define SMALL_CHUNK_SIZE \
390 (0x8000 - (M_OVERHEAD+1)*GRANULARITY+GRANULARITY - EXTERN_MALLOC_OVERHEAD)
391 /* large_malloc overhead ^ */
392
393 # define CHUNK_SIZE (0x40000 - GRANULARITY - EXTERN_MALLOC_OVERHEAD)
394 #endif
395
396
397 /* Bitflags for the size field:
398 * TODO: Assumes a 32-Bit word_t.
399 * TODO: define values for 64-bit word_t to support larger blocks.
400 */
401 #define PREV_BLOCK 0x80000000 /* Previous block is allocated */
402 #define THIS_BLOCK 0x40000000 /* This block is allocated */
403 #define M_REF 0x20000000 /* Block is referenced */
404 #define M_GC_FREE 0x10000000 /* GC may free this block */
405 #define M_DEFRAG (M_GC_FREE) /* Non-defragmentable small block */
406 #define M_MASK 0x0fffffff /* Mask for the size, measured in word_t's */
407
408
409 #ifdef MALLOC_CHECK
410
411 /* The magic words for free and allocated small blocks.
412 * Every small block size should get its own magic words, but
413 * if there are more sizes than words, the words of lower sizes
414 * are reused.
415 *
416 * There are enough words for 64 different sizes.
417 */
418
419 static word_t sfmagic[]
420 = { 0xde8f7d2d , 0xbd89a4b6 , 0xb667bbec , 0x475fae0a
421 , 0x39fc5582 , 0x32041f46 , 0x624a92f0 , 0x16dd36e2
422 , 0x7be9c1bd , 0x088aa102 , 0x3d38509b , 0x746b9fbe
423 , 0x2d04417f , 0x775d4351 , 0x53c48d96 , 0x02b26e0b
424 , 0x418fedcf , 0x19dbc19e , 0x78512adb , 0x1a1f5e2b
425 , 0x307d7761 , 0x6584c1f0 , 0x24e3c36f , 0x2232310f
426 , 0x2dac5ceb , 0x106e8b5a , 0x5a05a938 , 0x5e6392b6
427 , 0x66b90348 , 0x75264901 , 0x4174f402 , 0x618b18a4
428 , 0x3a6ab4bf , 0x3c4bc289 , 0x2657a9a9 , 0x4e68589b
429 , 0x09648aa6 , 0x3fc489bb , 0x1c1b715c , 0x054e4c63
430 , 0x484f2abd , 0x5953c1f8 , 0x79b9ec22 , 0x75536c3d
431 , 0x50b10549 , 0x4d7e79b8 , 0x7805da48 , 0x1240f318
432 , 0x675a3b56 , 0x70570523 , 0x2c605143 , 0x17d7b2b7
433 , 0x55dbc713 , 0x514414b2 , 0x3a09e3c7 , 0x038823ff
434 , 0x61b2a00c , 0x140f8cff , 0x61ebb6b5 , 0x486ba354
435 , 0x2360aab8 , 0x29f6bbf8 , 0x43a08abf , 0x5fac6d41
436 };
437
438 static word_t samagic[]
439 = { 0x34706efd , 0xfc2a5830 , 0x4e62041a , 0x2713945e
440 , 0xab58d8ab , 0xa372eeab , 0x71093c08 , 0xed2e6cc9
441 , 0x504e65a2 , 0x1208e35b , 0x6910f7e7 , 0x1012ef5d
442 , 0x2e2454b7 , 0x6e5f444b , 0x58621a1b , 0x077816af
443 , 0x6819306d , 0x4db58658 , 0x58291bf8 , 0x3597aa25
444 , 0x45bb60a0 , 0x6a6a0f11 , 0x1cf1e57c , 0x361265c4
445 , 0x16ca6054 , 0x34c99833 , 0x0bee2cd7 , 0x680e7507
446 , 0x6ed37bfa , 0x0f7650d6 , 0x49c11513 , 0x02e308f9
447 , 0x7162078c , 0x122cb868 , 0x0c18defa , 0x14c2b244
448 , 0x3c237460 , 0x4fb969b9 , 0x746f1f85 , 0x0c71da02
449 , 0x61c24d14 , 0x5d80176d , 0x1c84c960 , 0x0fe6a1cc
450 , 0x4bdf5bb8 , 0x74e6e37b , 0x175eb87b , 0x33f88c25
451 , 0x429c69d3 , 0x6f87d474 , 0x6990364a , 0x0857ca73
452 , 0x59f1e385 , 0x06821bc6 , 0x3e6a3037 , 0x70bc43d9
453 , 0x3b4bb3fa , 0x4a585d0f , 0x58cab8e0 , 0x2a1f2ff4
454 , 0x59ceade5 , 0x228bcdf4 , 0x2d0238ee , 0x4b30b571
455 };
456
457 #define LFMAGIC 0xdfaff2ee /* Magic word for free large blocks */
458 #define LAMAGIC 0xf460146e /* Magic word for allocated large blocks */
459
460 #endif /* MALLOC_CHECK */
461
462 /*-------------------------------------------------------------------------*/
463 /* Debugging macros */
464
465 /* Define this macro to get a log of all allocation requests which can't be
466 * immediately satisfied from a freelist. The log is written to
467 * gcollect_outfd.
468 */
469
470 /* #define DEBUG_MALLOC_ALLOCS */
471
472 #ifdef DEBUG_MALLOC_ALLOCS
473 # define ulog(s) \
474 write(gcollect_outfd, s, strlen(s))
475 # define ulog1f(s,t) \
476 dprintf1(gcollect_outfd, s, (p_int)(t))
477 # define ulog2f(s,t1,t2) \
478 dprintf2(gcollect_outfd, s, (p_int)(t1), (p_int)(t2))
479 # define ulog3f(s,t1,t2,t3) \
480 dprintf3(gcollect_outfd, s, (p_int)(t1), (p_int)(t2), (p_int)(t3))
481 #else
482 # define ulog(s) (void)0
483 # define ulog1f(s,t) (void)0
484 # define ulog2f(s,t1,t2) (void)0
485 # define ulog3f(s,t1,t2,t3) (void)0
486 #endif
487
488 /*-------------------------------------------------------------------------*/
489
490 static size_t smalloc_size;
491 /* Size of the current smalloc() request.
492 * It is used to print a diagnostic when the memory is running out.
493 */
494
495 /* --- Small Block variables --- */
496
497 #define DEFAULT_INITIAL_SC_SIZE (3 * SMALL_CHUNK_SIZE)
498 /* The default initial size of a small chunk. Currently the driver
499 * uses somewhat over 2*SMALL_CHUNK_SIZE for it's own tables.
500 */
501
502 static word_t small_chunk_size = DEFAULT_INITIAL_SC_SIZE;
503 /* The size of a small chunk. Usually SMALL_CHUNK_SIZE, the first
504 * small chunk of all can be allocated of min_small_malloced size;
505 * the allocator will then reset the value to SMALL_CHUNK_SIZE.
506 */
507
508 static word_t *last_small_chunk = NULL;
509 /* Pointer the most recently allocated small chunk.
510 * The first word of each chunk points to the previously allocated
511 * one.
512 */
513
514 static word_t *sfltable[SMALL_BLOCK_NUM+1] = {INIT_SMALL_BLOCK, 0};
515 /* List of free small blocks of the various sizes.
516 * The blocks are linked through the first non-header word_t.
517 * The last list is special: it keeps the oversized free blocks.
518 */
519
520 /* --- Large Block variables --- */
521
522 static word_t *heap_start = NULL;
523 /* First address on the heap.
524 */
525
526 static word_t *heap_end = NULL;
527 /* Current end address of the heap.
528 */
529
530 /* --- Statistics --- */
531
532 static t_stat small_alloc_stat = {0,0};
533 /* Number and size of small block allocations (incl overhead).
534 */
535
536 static t_stat small_free_stat = {0,0};
537 /* Number and size of small blocks deallocations (incl overhead).
538 */
539
540 static t_stat small_chunk_stat = {0,0};
541 /* Number and size of allocated small chunks.
542 */
543
544 static t_stat small_chunk_wasted = {0,0};
545 /* Number and size of wasted blocks in small chunks.
546 * This includes the large-block overhead of the chunks themselves.
547 */
548
549 static t_stat large_free_stat = {0,0};
550 /* Number and size of free large blocks.
551 */
552
553 static t_stat large_alloc_stat = {0,0};
554 /* Number and size of allocated large blocks.
555 */
556
557 static t_stat large_wasted_stat = {0,0};
558 /* Number and size of unusable memory frags around the large blocks.
559 */
560
561 static t_stat sbrk_stat;
562 /* Number and size of allocated heap blocks.
563 */
564
565 static t_stat perm_alloc_stat = {0,0};
566 /* Number and size of permanent allocations functions (incl overhead). This
567 * figure is a subset of {small,large}_alloc_stat.
568 */
569
570 static long defrag_calls_total = 0;
571 /* Total number of calls to defragment_small_lists().
572 */
573
574 static long defrag_calls_req = 0;
575 /* Number of calls to defragment_small_lists() with a desired size.
576 */
577
578 static long defrag_req_success = 0;
579 /* Number of times, a defragmentation for a desired size was successful.
580 */
581
582 static long defrag_blocks_inspected = 0;
583 /* Number of blocks inspected during defragmentations.
584 */
585
586 static long defrag_blocks_merged = 0;
587 /* Number of blocks merged during defragmentations.
588 */
589
590 static long defrag_blocks_result = 0;
591 /* Number of defragmented blocks (ie. merge results).
592 */
593
594 static long malloc_increment_size_calls = 0;
595 /* Number of calls to malloc_increment_size().
596 */
597
598 static long malloc_increment_size_success = 0;
599 /* Number of successfull calls to malloc_increment_size().
600 */
601
602 static long malloc_increment_size_total = 0;
603 /* Total memory allocated through to malloc_increment_size().
604 */
605
606 #ifdef USE_AVL_FREELIST
607 static long num_avl_nodes = 0;
608 /* Number of nodes in the AVL tree managing the large free blocks.
609 */
610 #endif /* USE_AVL_FREELIST */
611
612 /*-------------------------------------------------------------------------*/
613 /* Forward declarations */
614
615 static char *esbrk(word_t size, size_t * pExtra) __attribute__((malloc,warn_unused_result));
616
617 static char *large_malloc(word_t size, Bool force_m) __attribute__((malloc,warn_unused_result));
618 #define large_malloc_int(size, force_m) large_malloc(size, force_m)
619 static void large_free(char *ptr);
620 static INLINE size_t mem_overhead(void) __attribute__((const));
621
622
623 #ifdef MALLOC_EXT_STATISTICS
624 /*=========================================================================*/
625
626 /* EXTENDED STATISTICS */
627
628 /* Extended statistics, giving a better overview about what is allocated
629 * how often.
630 */
631
632 /*-------------------------------------------------------------------------*/
633 /* --- struct extstat_s: Statistics for one block size
634 */
635 typedef struct extstat_s {
636 unsigned long max_alloc; /* Max number of blocks allocated */
637 unsigned long cur_alloc; /* Current number of blocks allocated */
638 unsigned long max_free; /* Max number of free blocks */
639 unsigned long cur_free; /* Current number of free blocks */
640 unsigned long num_xalloc; /* Number of xalloc() requests since last avg */
641 unsigned long num_xfree; /* Number of xfree() requests since last avg */
642 double savg_xalloc; /* Sum of xalloc() requests/second */
643 double savg_xfree; /* Sum of xfree() requests/second */
644 /* On every call to mem_update_stats(), num_x{alloc,free} is averaged
645 * into a number of requests/second and then added to savg_. The
646 * total average is then later calculated using savg_ and the number
647 * of mem_update_stats() calls - this way overflows are avoided.
648 */
649 } extstat_t;
650
651 static unsigned long num_update_calls = 0;
652 /* Number of mem_update_stats() calls.
653 */
654
655 static mp_int last_update_time = 0;
656 /* Timestamp of last call to mem_update_stats().
657 */
658
659 #define SIZE_EXTSTATS (SMALL_BLOCK_NUM+2)
660
661 static extstat_t extstats[SIZE_EXTSTATS];
662 /* The statistics array. [SMALL_BLOCK_NUM+1] is for the large blocks.
663 */
664
665 /*-------------------------------------------------------------------------*/
666 static INLINE void
extstat_update_max(extstat_t * pStat)667 extstat_update_max (extstat_t * pStat)
668 {
669 if (pStat->cur_alloc > pStat->max_alloc)
670 pStat->max_alloc = pStat->cur_alloc;
671 if (pStat->cur_free > pStat->max_free)
672 pStat->max_free = pStat->cur_free;
673 } /* extstat_update_max() */
674
675 #endif /* MALLOC_EXT_STATISTICS */
676
677 /*=========================================================================*/
678
679 /* ASSOCIATED ROUTINES */
680
681 /*-------------------------------------------------------------------------*/
682 static INLINE size_t
mem_block_total_size(POINTER p)683 mem_block_total_size (POINTER p)
684
685 /* Return the size of block <p> (including internal overhead) in bytes.
686 */
687
688 {
689 word_t *q = ((word_t *) p) - M_OVERHEAD;
690 word_t size = q[M_SIZE] & M_MASK;
691 if (size > SMALL_BLOCK_MAX)
692 size = q[M_LSIZE];
693 return size*GRANULARITY;
694 } /* mem_block_total_size() */
695
696 /*-------------------------------------------------------------------------*/
697 static INLINE size_t
mem_block_size(POINTER p)698 mem_block_size (POINTER p)
699
700 /* Return the size of block <p> (sans internal overhead) in bytes.
701 */
702
703 {
704 word_t * q = ((word_t *)p) - M_OVERHEAD;
705
706 word_t size = (q[M_SIZE] & M_MASK);
707 if (size > SMALL_BLOCK_MAX)
708 return mem_block_total_size(p) - ML_OVERHEAD*GRANULARITY;
709 return mem_block_total_size(p) - mem_overhead();
710 } /* mem_block_size() */
711
712 /*-------------------------------------------------------------------------*/
713 static INLINE void
mem_mark_permanent(POINTER p)714 mem_mark_permanent (POINTER p)
715
716 /* Mark the allocated block at <p> as permanent, ie. it won't be subject
717 * to the GC.
718 */
719
720 {
721 word_t * q = (word_t *)p;
722 if (q[-M_OVERHEAD] & M_GC_FREE)
723 {
724 q[-M_OVERHEAD] &= ~M_GC_FREE;
725 count_up(&perm_alloc_stat, mem_block_total_size(q));
726 }
727 } /* mem_mark_permanent() */
728
729 /*-------------------------------------------------------------------------*/
730 static INLINE void
mem_mark_collectable(POINTER p)731 mem_mark_collectable (POINTER p)
732
733 /* Mark the allocated block at <p> as non-permant, ie. it is subject
734 * to the GC.
735 */
736
737 {
738 word_t * q = (word_t *)p;
739 if (!(q[-M_OVERHEAD] & M_GC_FREE))
740 {
741 q[-M_OVERHEAD] |= (M_REF|M_GC_FREE);
742 count_back(&perm_alloc_stat, mem_block_total_size(q));
743 }
744 } /* mem_mark_collectable() */
745
746 /*-------------------------------------------------------------------------*/
747 static INLINE size_t
mem_overhead(void)748 mem_overhead (void)
749
750 /* Return the size of each block's overhead in bytes.
751 */
752
753 {
754 return M_OVERHEAD*GRANULARITY;
755 } /* mem_overhead() */
756
757 /*-------------------------------------------------------------------------*/
758 #ifdef MALLOC_EXT_STATISTICS
759 void
mem_update_stats(void)760 mem_update_stats (void)
761
762 /* Update whatever extended statistics the allocator has. Called every
763 * backend cycle or so to allow for the calculation of averages over time.
764 */
765
766 {
767 int i;
768 double time_diff;
769
770 if (!last_update_time)
771 last_update_time = boot_time;
772
773 if (current_time <= last_update_time)
774 return;
775
776 time_diff = current_time - last_update_time;
777
778 for (i = 0; i < SIZE_EXTSTATS; ++i)
779 {
780 extstats[i].savg_xalloc += (double)extstats[i].num_xalloc / time_diff;
781 extstats[i].savg_xfree += (double)extstats[i].num_xfree / time_diff;
782 extstats[i].num_xalloc = 0;
783 extstats[i].num_xfree = 0;
784 }
785
786 num_update_calls++;
787 last_update_time = current_time;
788 } /* mem_update_stats() */
789 #endif /* MALLOC_EXT_STATISTICS */
790
791 /*-------------------------------------------------------------------------*/
792 void
mem_dump_data(strbuf_t * sbuf)793 mem_dump_data (strbuf_t *sbuf)
794
795 /* For the status commands and functions: add the smalloc statistic
796 * to the buffer <sbuf>.
797 */
798
799 {
800 #ifdef REPLACE_MALLOC
801 t_stat clib_st;
802 #endif
803 t_stat sbrk_st, perm_st, xalloc_st;
804 t_stat l_alloc, l_free, l_wasted;
805 t_stat s_alloc, s_free, s_wasted, s_chunk;
806
807 /* Get a snapshot of the statistics - strbuf_add() might do further
808 * allocations while we're reading them.
809 */
810
811 #ifdef MALLOC_EXT_STATISTICS
812 mem_update_stats();
813 #endif /* MALLOC_EXT_STATISTICS */
814
815 sbrk_st = sbrk_stat;
816 #ifdef REPLACE_MALLOC
817 clib_st = clib_alloc_stat;
818 #endif
819 xalloc_st = xalloc_stat;
820 perm_st = perm_alloc_stat;
821 l_alloc = large_alloc_stat; l_alloc.size *= GRANULARITY;
822 l_free = large_free_stat; l_free.size *= GRANULARITY;
823 l_wasted = large_wasted_stat;
824 s_alloc = small_alloc_stat;
825 s_free = small_free_stat;
826 s_wasted = small_chunk_wasted;
827 s_chunk = small_chunk_stat;
828
829 # define dump_stat(str,stat) strbuf_addf(sbuf, str,stat.counter,stat.size)
830
831 strbuf_add(sbuf, "Using LDMUD smalloc.\n");
832 strbuf_add(sbuf, "Type Count Space (bytes)\n");
833 dump_stat("xallocs: %8lu %10lu\n\n", xalloc_st);
834 dump_stat("sbrk requests: %8lu %10lu (a)\n",sbrk_st);
835 dump_stat("large blocks: %8lu %10lu (b)\n",l_alloc);
836 strbuf_addf(sbuf
837 , "large net avail: %10ld\n"
838 , l_alloc.size - l_alloc.counter * ML_OVERHEAD * GRANULARITY
839 );
840 dump_stat("large free blocks: %8lu %10lu (c)\n",l_free);
841 dump_stat("large wasted: %8lu %10lu (d)\n\n",l_wasted);
842 dump_stat("small chunks: %8lu %10lu (e)\n",s_chunk);
843 dump_stat("small blocks: %8lu %10lu (f)\n",s_alloc);
844 strbuf_addf(sbuf
845 , "small net avail: %10lu\n"
846 , s_alloc.size - s_alloc.counter * M_OVERHEAD * GRANULARITY
847 );
848 dump_stat("small free blocks: %8lu %10lu (g)\n",s_free);
849 dump_stat("small wasted: %8lu %10lu (h)\n\n",s_wasted);
850
851 dump_stat("permanent blocks: %8lu %10lu\n", perm_st);
852 #ifdef REPLACE_MALLOC
853 dump_stat("clib allocations: %8lu %10lu\n", clib_st);
854 #else
855 strbuf_addf(sbuf, "clib allocations: n/a n/a\n");
856 #endif
857 strbuf_add(sbuf, "\n");
858 #ifdef USE_AVL_FREELIST
859 strbuf_addf(sbuf, "AVL nodes: %8ld -\n", num_avl_nodes);
860 strbuf_add(sbuf, "\n");
861 #endif /* USE_AVL_FREELIST */
862
863 #undef dump_stat
864
865 strbuf_addf(sbuf,
866 "malloc_increment_size: calls %lu success %lu total %lu\n\n",
867 malloc_increment_size_calls,
868 malloc_increment_size_success,
869 malloc_increment_size_total
870 );
871 strbuf_addf(sbuf
872 , "Total storage: (b+c+d) %10lu should equal (a) %10lu\n"
873 , l_alloc.size + l_free.size + l_wasted.size
874 , sbrk_st.size
875 );
876 strbuf_addf(sbuf
877 , "Total small storage: (f+g+h) %10lu should equal (e) %10lu\n"
878 , s_alloc.size + s_free.size + s_wasted.size
879 , s_chunk.size
880 );
881 strbuf_addf(sbuf
882 , "Total storage in use: (b-g-h) %10lu net available: %10lu\n"
883 , l_alloc.size - s_free.size - s_wasted.size
884 , l_alloc.size - s_free.size - s_wasted.size
885 - l_alloc.counter * ML_OVERHEAD * GRANULARITY
886 - s_alloc.counter * M_OVERHEAD * GRANULARITY
887 - xalloc_st.counter * XM_OVERHEAD_SIZE
888 );
889 strbuf_addf(sbuf
890 , "Total storage unused: (c+d+g+h) %10lu\n\n"
891 , l_free.size + l_wasted.size
892 + s_free.size + s_wasted.size
893 );
894 strbuf_addf(sbuf,
895 "soft memory limit: %10lu, hard memory limit: %10lu\n\n",
896 get_memory_limit(MALLOC_SOFT_LIMIT),
897 get_memory_limit(MALLOC_HARD_LIMIT)
898 );
899
900 strbuf_addf(sbuf,
901 "Defragmentation: %lu calls (%lu for size: %lu successful)\n"
902 " %lu blocks inspected: %lu merged yielding %lu blocks\n"
903 , defrag_calls_total, defrag_calls_req, defrag_req_success
904 , defrag_blocks_inspected, defrag_blocks_merged, defrag_blocks_result
905 );
906 } /* mem_dump_data() */
907
908 /*-------------------------------------------------------------------------*/
909 void
mem_dump_extdata(strbuf_t * sbuf)910 mem_dump_extdata (strbuf_t *sbuf)
911
912 /* For the status commands and functions: add the extended smalloc statistic
913 * to the buffer <sbuf>.
914 */
915
916 {
917 #ifdef MALLOC_EXT_STATISTICS
918 int i;
919
920 strbuf_add(sbuf,
921 "Detailed Block Statistics:\n\n"
922 );
923 for (i = 0; i < SIZE_EXTSTATS; ++i)
924 {
925 if (i < SMALL_BLOCK_NUM)
926 strbuf_addf(sbuf, " Size %3zu: ", (i + SMALL_BLOCK_MIN) * GRANULARITY);
927 else if (i == SMALL_BLOCK_NUM)
928 strbuf_addf(sbuf, " Oversize: ");
929 else
930 strbuf_addf(sbuf, " Large: ");
931 strbuf_addf(sbuf, "Alloc: %7.1lf /s - %7lu / %7lu cur/max\n"
932 , num_update_calls ? extstats[i].savg_xalloc / num_update_calls
933 : 0.0
934 , extstats[i].cur_alloc, extstats[i].max_alloc
935 );
936 strbuf_addf(sbuf, " "
937 "Free: %7.1lf /s - %7lu / %7lu cur/max\n"
938 , num_update_calls ? extstats[i].savg_xfree / num_update_calls
939 : 0.0
940 , extstats[i].cur_free, extstats[i].max_free
941 );
942 }
943 #else
944 strbuf_add(sbuf, "No detailed blocks statistics available.\n");
945 #endif /* MALLOC_EXT_STATISTICS */
946 } /* mem_dump_extdata() */
947
948 /*-------------------------------------------------------------------------*/
949 void
mem_dinfo_data(svalue_t * svp,int value)950 mem_dinfo_data (svalue_t *svp, int value)
951
952 /* Fill in the data for debug_info(DINFO_DATA, DID_MEMORY) into the
953 * svalue-block svp.
954 */
955
956 {
957 #define ST_NUMBER(which,code) \
958 if (value == -1) svp[which].u.number = code; \
959 else if (value == which) svp->u.number = code
960
961 if (value == -1)
962 put_ref_string(svp+DID_MEM_NAME, STR_SMALLOC);
963 else if (value == DID_MEM_NAME)
964 put_ref_string(svp, STR_SMALLOC);
965
966 ST_NUMBER(DID_MEM_SBRK, sbrk_stat.counter);
967 ST_NUMBER(DID_MEM_SBRK_SIZE, sbrk_stat.size);
968 ST_NUMBER(DID_MEM_LARGE, large_alloc_stat.counter);
969 ST_NUMBER(DID_MEM_LARGE_SIZE, large_alloc_stat.size * GRANULARITY);
970 ST_NUMBER(DID_MEM_LFREE, large_free_stat.counter);
971 ST_NUMBER(DID_MEM_LFREE_SIZE, large_free_stat.size * GRANULARITY);
972 ST_NUMBER(DID_MEM_LWASTED, large_wasted_stat.counter);
973 ST_NUMBER(DID_MEM_LWASTED_SIZE, large_wasted_stat.size);
974 ST_NUMBER(DID_MEM_CHUNK, small_chunk_stat.counter);
975 ST_NUMBER(DID_MEM_CHUNK_SIZE, small_chunk_stat.size);
976 ST_NUMBER(DID_MEM_SMALL, small_alloc_stat.counter);
977 ST_NUMBER(DID_MEM_SMALL_SIZE, small_alloc_stat.size);
978 ST_NUMBER(DID_MEM_SFREE, small_free_stat.counter);
979 ST_NUMBER(DID_MEM_SFREE_SIZE, small_free_stat.size);
980 ST_NUMBER(DID_MEM_SWASTED, small_chunk_wasted.counter);
981 ST_NUMBER(DID_MEM_SWASTED_SIZE, small_chunk_wasted.size);
982 ST_NUMBER(DID_MEM_MINC_CALLS, malloc_increment_size_calls);
983 ST_NUMBER(DID_MEM_MINC_SUCCESS, malloc_increment_size_success);
984 ST_NUMBER(DID_MEM_MINC_SIZE, malloc_increment_size_total);
985 #ifdef REPLACE_MALLOC
986 ST_NUMBER(DID_MEM_CLIB, clib_alloc_stat.counter);
987 ST_NUMBER(DID_MEM_CLIB_SIZE, clib_alloc_stat.size);
988 #endif
989 ST_NUMBER(DID_MEM_PERM, perm_alloc_stat.counter);
990 ST_NUMBER(DID_MEM_PERM_SIZE, perm_alloc_stat.size);
991 ST_NUMBER(DID_MEM_OVERHEAD, T_OVERHEAD * GRANULARITY);
992 ST_NUMBER(DID_MEM_ALLOCATED, large_alloc_stat.size * GRANULARITY
993 - small_free_stat.size
994 - small_chunk_wasted.size);
995 ST_NUMBER(DID_MEM_USED, large_alloc_stat.size * GRANULARITY
996 - small_free_stat.size
997 - small_chunk_wasted.size
998 - large_alloc_stat.counter * ML_OVERHEAD * GRANULARITY
999 - small_alloc_stat.counter * M_OVERHEAD * GRANULARITY
1000 - xalloc_stat.counter * XM_OVERHEAD_SIZE
1001 );
1002 ST_NUMBER(DID_MEM_TOTAL_UNUSED, large_free_stat.size * GRANULARITY
1003 + large_wasted_stat.size
1004 + small_free_stat.size
1005 + small_chunk_wasted.size
1006 );
1007 ST_NUMBER(DID_MEM_DEFRAG_CALLS, defrag_calls_total);
1008 ST_NUMBER(DID_MEM_DEFRAG_CALLS_REQ, defrag_calls_req);
1009 ST_NUMBER(DID_MEM_DEFRAG_REQ_SUCCESS, defrag_req_success);
1010 ST_NUMBER(DID_MEM_DEFRAG_BLOCKS_INSPECTED, defrag_blocks_inspected);
1011 ST_NUMBER(DID_MEM_DEFRAG_BLOCKS_MERGED, defrag_blocks_merged);
1012 ST_NUMBER(DID_MEM_DEFRAG_BLOCKS_RESULT, defrag_blocks_result);
1013 #ifdef USE_AVL_FREELIST
1014 ST_NUMBER(DID_MEM_AVL_NODES, num_avl_nodes);
1015 #else
1016 ST_NUMBER(DID_MEM_AVL_NODES, large_free_stat.counter);
1017 #endif /* USE_AVL_FREELIST */
1018 #ifdef MALLOC_EXT_STATISTICS
1019 do {
1020 vector_t * top; /* Array holding the sub vectors */
1021 int i;
1022 Bool deallocate = MY_FALSE;
1023
1024 mem_update_stats();
1025 top = allocate_array(SMALL_BLOCK_NUM+2);
1026
1027 if (!top)
1028 break;
1029
1030 for (i = 0; i < SIZE_EXTSTATS; ++i)
1031 {
1032 vector_t *sub = allocate_array(DID_MEM_ES_MAX);
1033
1034 if (!sub)
1035 {
1036 deallocate = MY_TRUE;
1037 break;
1038 }
1039
1040 put_number(&sub->item[DID_MEM_ES_MAX_ALLOC], extstats[i].max_alloc);
1041 put_number(&sub->item[DID_MEM_ES_CUR_ALLOC], extstats[i].cur_alloc);
1042 put_number(&sub->item[DID_MEM_ES_MAX_FREE], extstats[i].max_free);
1043 put_number(&sub->item[DID_MEM_ES_CUR_FREE], extstats[i].cur_free);
1044 if (num_update_calls)
1045 {
1046 put_float(&sub->item[DID_MEM_ES_AVG_XALLOC], extstats[i].savg_xalloc / num_update_calls);
1047 put_float(&sub->item[DID_MEM_ES_AVG_XFREE], extstats[i].savg_xfree / num_update_calls);
1048 }
1049
1050 put_array(top->item + i, sub);
1051 }
1052
1053 if (deallocate)
1054 {
1055 free_array(top);
1056 ST_NUMBER(DID_MEM_EXT_STATISTICS, 0);
1057 }
1058 else
1059 {
1060 if (value == -1)
1061 put_array(svp+DID_MEM_EXT_STATISTICS, top);
1062 else if (value == DID_MEM_EXT_STATISTICS)
1063 put_array(svp, top);
1064 }
1065 } while(0);
1066 #else
1067 ST_NUMBER(DID_MEM_EXT_STATISTICS, 0);
1068 #endif /* MALLOC_EXT_STATISTICS */
1069
1070 #undef ST_NUMBER
1071 } /* mem_dinfo_data() */
1072
1073 /*-------------------------------------------------------------------------*/
1074 #ifdef CHECK_MAPPING_TOTAL
1075 mp_int
available_memory(void)1076 available_memory(void)
1077
1078 /* Return the amount of memory actually used by the driver. */
1079
1080 {
1081 return large_alloc_stat.size * GRANULARITY
1082 - small_free_stat.size
1083 - small_chunk_wasted.size
1084 - large_alloc_stat.counter * ML_OVERHEAD * GRANULARITY
1085 - small_alloc_stat.counter * M_OVERHEAD * GRANULARITY;
1086 } /* available_memory() */
1087 #endif /* CHECK_MAPPING_TOTAL */
1088
1089 /*=========================================================================*/
1090
1091 /* SMALL BLOCKS */
1092
1093 /*-------------------------------------------------------------------------*/
1094
1095 #define SIZE_INDEX(size) \
1096 ((size)/GRANULARITY - T_OVERHEAD - SMALL_BLOCK_MIN)
1097 /* Index to the proper array entry for a small
1098 * block of <size> (including overhead).
1099 */
1100
1101 #define SIZE_MOD_INDEX(size, table) \
1102 (((size)/GRANULARITY - T_OVERHEAD - SMALL_BLOCK_MIN) % NELEM(table))
1103 /* Index to the proper array entry for a small
1104 * block of <size> (including overhead), limited to the size of <table>.
1105 */
1106
1107 /*-------------------------------------------------------------------------*/
1108 static INLINE void
UNLINK_SMALL_FREE(word_t * block)1109 UNLINK_SMALL_FREE (word_t * block)
1110
1111 /* Unlink the small free <block> from its freelist
1112 */
1113
1114 {
1115 const word_t bsize = block[M_SIZE] & M_MASK;
1116 int ix;
1117 word_t flag;
1118
1119 if (bsize <= SMALL_BLOCK_MAX)
1120 {
1121 ix = bsize - T_OVERHEAD - SMALL_BLOCK_MIN;
1122 flag = 0;
1123 }
1124 else
1125 {
1126 ix = SMALL_BLOCK_NUM;
1127 flag = 1;
1128 }
1129
1130 #ifdef MALLOC_EXT_STATISTICS
1131 extstats[ix].cur_free--;
1132 #endif /* MALLOC_EXT_STATISTICS */
1133
1134 if (sfltable[ix] == block)
1135 {
1136 word_t * head = BLOCK_NEXT(block);
1137 if (head)
1138 head[M_PLINK(head[M_SIZE] & M_MASK)] = (word_t)head | flag;
1139 sfltable[ix] = head;
1140 }
1141 else
1142 {
1143 word_t * prev = (word_t *)(block[M_PLINK(bsize)] & ~1);
1144 word_t * next = BLOCK_NEXT(block);
1145 if (next)
1146 next[M_PLINK(next[M_SIZE] & M_MASK)] = (word_t)prev | flag;
1147 prev[M_LINK] = (word_t) next;
1148 }
1149 count_back(&small_free_stat, bsize * GRANULARITY);
1150
1151 } /* UNLINK_SMALL_FREE() */
1152
1153 /*-------------------------------------------------------------------------*/
1154 static INLINE
MAKE_SMALL_FREE(word_t * block,word_t bsize)1155 void MAKE_SMALL_FREE (word_t *block, word_t bsize)
1156
1157 /* The <bsize> words starting at <block> are a new free small block.
1158 * Set it up and insert it into the appropriate free list.
1159 */
1160
1161 {
1162 word_t * head;
1163 int ix;
1164 word_t flag;
1165
1166 if (bsize <= SMALL_BLOCK_MAX)
1167 {
1168 ix = bsize - T_OVERHEAD - SMALL_BLOCK_MIN;
1169 flag = 0;
1170 }
1171 else
1172 {
1173 ix = SMALL_BLOCK_NUM;
1174 flag = 1;
1175 }
1176
1177 #ifdef MALLOC_EXT_STATISTICS
1178 extstats[ix].cur_free++;
1179 extstat_update_max(extstats + ix);
1180 #endif /* MALLOC_EXT_STATISTICS */
1181
1182 block[M_SIZE] = bsize | (THIS_BLOCK|M_REF)
1183 | (block[M_SIZE] & PREV_BLOCK);
1184 block[bsize] |= PREV_BLOCK;
1185
1186 head = sfltable[ix];
1187 if (head)
1188 head[M_PLINK(head[M_SIZE] & M_MASK)] = (word_t)block | flag;
1189 block[M_LINK] = (word_t) head;
1190 block[M_PLINK(bsize)] = (word_t)block | flag;
1191 /* Let the PLINK point to block itself, to satisfy sanity checks */
1192
1193 if (flag)
1194 block[M_PLINK(bsize)-1] = bsize;
1195
1196 sfltable[ix] = block;
1197 count_up(&small_free_stat, bsize * GRANULARITY);
1198
1199 #ifdef MALLOC_CHECK
1200 block[M_MAGIC] = sfmagic[SIZE_MOD_INDEX(bsize * GRANULARITY, sfmagic)];
1201 #endif
1202 } /* MAKE_SMALL_FREE() */
1203
1204 /*-------------------------------------------------------------------------*/
1205 static Bool
defragment_small_lists(int req)1206 defragment_small_lists (int req)
1207
1208 /* Defragment some or all of the small block free lists.
1209 *
1210 * req = 0: defragment all of the free lists; result is MY_FALSE.
1211 * req > 0: the routine is called from the allocator for a small block
1212 * allocation for <req> words incl overhead. If the defragmentation
1213 * creates a block of a suitable size, the defragmentation
1214 * terminates at that point and the function returns MY_TRUE. If
1215 * all blocks are defragmented and no suitable block is found, the
1216 * function returns MY_FALSE.
1217 */
1218
1219 {
1220 word_t split_size = 0;
1221 /* Minimum blocksize for a block splittable into the requested
1222 * size, incl. overhead in words; 0 for 'none'
1223 */
1224 int ix; /* Freelist index */
1225 Bool found = MY_FALSE; /* Set to TRUE if a suitable block is found */
1226
1227 defrag_calls_total++;
1228
1229 if (req > 0)
1230 {
1231 split_size = req + SMALL_BLOCK_MIN + T_OVERHEAD;
1232 defrag_calls_req++;
1233 }
1234 else
1235 req = 0; /* Just to make sure */
1236
1237 /* Loop over the freelists, starting at the largest.
1238 */
1239 for (ix = SMALL_BLOCK_NUM; ix >= 0 && !found; ix--)
1240 {
1241 word_t *list = NULL;
1242 /* Local list of the defragmented blocks, linked through [M_LINK].
1243 */
1244 word_t *block;
1245 word_t *pred;
1246 /* <block> is the block currently analysed, <pred> the previously
1247 * analyzed block or NULL for the list header.
1248 */
1249
1250 /* Walk the current freelist and look for defragmentable blocks.
1251 * If one is found, remove it from the freelist, defragment it
1252 * and store the result in the local list.
1253 * Since the check for defragmentation occurs on both sides of
1254 * the free block, the defragmentation will never remove blocks from
1255 * this freelist which have already been visited.
1256 *
1257 * It is important that the loop is not terminated before the end
1258 * of the section of newly freed blocks (M_DEFRAG not set) is reached,
1259 * as the loop sets the M_DEFRAG flag as it goes along.
1260 */
1261 for (block = sfltable[ix], pred = NULL
1262 ; block != NULL && !(block[M_SIZE] & M_DEFRAG)
1263 ; )
1264 {
1265 Bool merged;
1266 word_t bsize = block[M_SIZE] & M_MASK;
1267
1268 defrag_blocks_inspected++;
1269
1270 /* Can this block be defragmented? */
1271 if ( !((block+bsize)[M_SIZE] & THIS_BLOCK)
1272 && !(block[M_SIZE] & PREV_BLOCK)
1273 )
1274 {
1275 /* No: flag this block as non-defragmentable and step to the
1276 * next block.
1277 */
1278 block[M_SIZE] |= M_DEFRAG;
1279 pred = block;
1280 block = (word_t *)block[M_LINK];
1281 continue;
1282 }
1283
1284 /* Yes: remove it from the freelist */
1285 UNLINK_SMALL_FREE(block);
1286
1287 /* Try to merge this free block with the following ones */
1288 do {
1289 word_t *next;
1290
1291 defrag_blocks_inspected++;
1292
1293 merged = MY_FALSE;
1294 next = block + bsize;
1295 if (next[M_SIZE] & THIS_BLOCK)
1296 {
1297 UNLINK_SMALL_FREE(next);
1298 bsize += next[M_SIZE] & M_MASK;
1299 merged = MY_TRUE;
1300
1301 defrag_blocks_merged++;
1302 }
1303
1304 if (req > 0 && (bsize == (word_t)req || bsize >= split_size))
1305 found = MY_TRUE;
1306
1307 } while (merged);
1308
1309 /* Try to merge the block with the ones in front of it */
1310 while ((block[M_SIZE] & PREV_BLOCK))
1311 {
1312 word_t *prev;
1313
1314 defrag_blocks_inspected++;
1315
1316 /* We use the 'prev' pointer first to get the size of previous
1317 * block, and from there we can determine it's address
1318 */
1319 prev = (word_t *)(block[-1]);
1320 if ((word_t)prev & 1)
1321 prev = block - block[-2];
1322 else
1323 prev = block - (prev[M_SIZE] & M_MASK);
1324
1325 #ifdef DEBUG
1326 /* TODO: Remove this test once it's been proven stable */
1327 if (!(prev[M_SIZE] & THIS_BLOCK))
1328 {
1329 in_malloc = 0;
1330 fatal("Block %p marks previous %p as free, but it isn't.\n"
1331 , block, prev);
1332 }
1333 #endif
1334 UNLINK_SMALL_FREE(prev);
1335 bsize += prev[M_SIZE] & M_MASK;
1336
1337 block = prev;
1338
1339 defrag_blocks_merged++;
1340
1341 if (req >= 0 && (bsize == (word_t)req || bsize >= split_size))
1342 found = MY_TRUE;
1343 } /* while() */
1344
1345 /* Update the block's size and move it into the local list.
1346 * Be careful not to clobber the flags in the size field.
1347 */
1348 block[M_SIZE] = bsize | (block[M_SIZE] & ~M_MASK);
1349 block[M_LINK] = (word_t)list;
1350 list = block;
1351
1352 defrag_blocks_result++;
1353
1354 /* Step to the next block using the still-value <pred> */
1355 if (pred)
1356 block = (word_t *)pred[M_LINK];
1357 else
1358 block = sfltable[ix];
1359 } /* for (blocks in freelist) */
1360
1361 /* Move the defragmented blocks from list back into their freelist.
1362 */
1363 while (list != NULL)
1364 {
1365 block = list;
1366 list = (word_t *)(list[M_LINK]);
1367 MAKE_SMALL_FREE(block, block[M_SIZE] & M_MASK);
1368 /* As we moved down the small block array, and the defragged
1369 * blocks already visited have been sorted into a list, setting
1370 * the M_DEFRAG flag would be possible here.
1371 * However, by not setting it we make the algorithm a bit
1372 * more robust, and lose only a few cycles the next time
1373 * around.
1374 */
1375 }
1376 } /* for (ix = SMALL_BLOCK_NUM..0 && !found) */
1377
1378 if (found)
1379 defrag_req_success++;
1380
1381 return found;
1382 } /* defragment_small_lists() */
1383
1384 /*-------------------------------------------------------------------------*/
1385 static INLINE void
defragment_small_block(word_t * block)1386 defragment_small_block (word_t *block)
1387
1388 /* Try to merge the small free block <block> with any following free blocks.
1389 * This routine is used by mem_increment_size().
1390 */
1391
1392 {
1393 word_t bsize = block[M_SIZE] & M_MASK;
1394 Bool merged;
1395 Bool defragged;
1396
1397 defragged = MY_FALSE;
1398
1399 UNLINK_SMALL_FREE(block);
1400
1401 /* Try to merge this free block with the following ones */
1402 do {
1403 word_t *next;
1404
1405 defrag_blocks_inspected++;
1406
1407 merged = MY_FALSE;
1408 next = block + bsize;
1409 if (next[M_SIZE] & THIS_BLOCK)
1410 {
1411 UNLINK_SMALL_FREE(next);
1412 bsize += next[M_SIZE] & M_MASK;
1413 merged = MY_TRUE;
1414 defragged = MY_TRUE;
1415
1416 defrag_blocks_inspected++;
1417 }
1418 } while (merged);
1419
1420 if (defragged)
1421 defrag_blocks_result++;
1422
1423 /* Reinsert the block into the freelists */
1424 MAKE_SMALL_FREE(block, bsize);
1425 } /* defragment_small_block() */
1426
1427 /*-------------------------------------------------------------------------*/
1428 /* Macro MAKE_SMALL_CHECK(block, size)
1429 * Macro MAKE_SMALL_CHECK_UNCHECKED(block, size)
1430 * If MALLOC_CHECK is defined, fill in the CHECK information
1431 * in the small block <block> of size <size> (in bytes incl overhead).
1432 * The _UNCHECKED macro is like the basic macro, except that it doesn't
1433 * check the M_MAGIC word before setting it.
1434 */
1435 #ifdef MALLOC_CHECK
1436 # define MAKE_SMALL_CHECK(block, size) do { \
1437 if (block[M_MAGIC] != sfmagic[SIZE_MOD_INDEX(size, sfmagic)] ) \
1438 { \
1439 in_malloc = 0; \
1440 fatal("allocation from free list for %zu bytes: " \
1441 "block %p (user %p) magic match failed, " \
1442 "expected %08"PRIxPTR", found %08"PRIxPTR"\n" \
1443 , size, block, block+T_OVERHEAD \
1444 , (intptr_t)sfmagic[SIZE_MOD_INDEX(size, sfmagic)] \
1445 , (intptr_t)block[M_MAGIC]); \
1446 } \
1447 block[M_MAGIC] = samagic[SIZE_MOD_INDEX(size, samagic)]; \
1448 } while(0)
1449 # define MAKE_SMALL_CHECK_UNCHECKED(block, size) do { \
1450 block[M_MAGIC] = samagic[SIZE_MOD_INDEX(size, samagic)]; \
1451 } while(0)
1452 #else
1453 # define MAKE_SMALL_CHECK(block, size) (void)0
1454 # define MAKE_SMALL_CHECK_UNCHECKED(block, size) (void)0
1455 #endif
1456
1457 /*-------------------------------------------------------------------------*/
1458 static POINTER
mem_alloc(size_t size)1459 mem_alloc (size_t size)
1460
1461 /* Allocate a memory block for <size> bytes at the source <file>:<line>.
1462 * Result is the pointer the memory block, or NULL when out of memory.
1463 */
1464
1465 {
1466 word_t *temp;
1467 Bool retry;
1468 #if defined(HAVE_MADVISE) || defined(DEBUG_MALLOC_ALLOCS)
1469 size_t orig_size = size;
1470 #endif
1471
1472 assert_stack_gap();
1473
1474 smalloc_size = size;
1475
1476 if (size == 0)
1477 {
1478 size++;
1479 }
1480
1481 /* TODO: For the following test, see SIZET_limits in port.h */
1482 if (size >= ULONG_MAX - (T_OVERHEAD+SMALL_BLOCK_MIN)*GRANULARITY
1483 || size >= (M_MASK + 1 - (T_OVERHEAD+SMALL_BLOCK_MIN))*GRANULARITY
1484 )
1485 {
1486 in_malloc = 0;
1487 if (malloc_privilege == MALLOC_SYSTEM)
1488 fatal("Malloc size exceeds numerical limit.\n");
1489 debug_message("Malloc size exceeds numerical limit.\n");
1490 return NULL;
1491 }
1492
1493 if (in_malloc++)
1494 {
1495 in_malloc = 0;
1496 writes(1,"Multiple threads in smalloc()\n");
1497 fatal("Multiple threads in smalloc()\n");
1498 /* NOTREACHED */
1499 return NULL;
1500 }
1501
1502 if (size > SMALL_BLOCK_MAX_BYTES + XM_OVERHEAD_SIZE)
1503 {
1504 void * rc = large_malloc(size, MY_FALSE);
1505 in_malloc--;
1506 return rc;
1507 }
1508
1509 /* --- It's a small block --- */
1510
1511 /* Get the block size rounded to the next multiple of a word
1512 * and with the overhead.
1513 */
1514 if (size < SMALL_BLOCK_MIN_BYTES + XM_OVERHEAD_SIZE)
1515 size = SMALL_BLOCK_MIN_BYTES + XM_OVERHEAD_SIZE;
1516
1517 size = (size+M_OVERHEAD*GRANULARITY+GRANULARITY-1) & ~(GRANULARITY-1);
1518
1519 /* Update statistics */
1520 count_up(&small_alloc_stat,size);
1521 #ifdef MALLOC_EXT_STATISTICS
1522 extstats[SIZE_INDEX(size)].num_xalloc++;
1523 extstats[SIZE_INDEX(size)].cur_alloc++;
1524 extstat_update_max(extstats + SIZE_INDEX(size));
1525 #endif /* MALLOC_EXT_STATISTICS */
1526
1527
1528 /* Try allocating the block from one of the free lists.
1529 *
1530 * This is done in a loop: if at the first attempt no block can be found,
1531 * the small block lists will be defragmented and the allocation attempt
1532 * is repeated. If that fails as well, the loop ends and we try to
1533 * get a new small chunk.
1534 */
1535
1536 retry = MY_FALSE;
1537 do {
1538 int ix;
1539
1540 /* First, check if the free list for this block size has one */
1541
1542 if ( NULL != (temp = sfltable[SIZE_INDEX(size)]))
1543 {
1544 /* allocate from the free list */
1545
1546 UNLINK_SMALL_FREE(temp);
1547
1548 /* Fill in the header (M_SIZE is already mostly ok) */
1549 MAKE_SMALL_CHECK(temp, size);
1550 temp[M_SIZE] |= (M_GC_FREE|M_REF);
1551 temp[M_SIZE] &= ~THIS_BLOCK;
1552 temp[temp[M_SIZE] & M_MASK] &= ~PREV_BLOCK;
1553
1554 temp += M_OVERHEAD;
1555
1556 MADVISE(temp, orig_size);
1557
1558 in_malloc--;
1559 return (POINTER)temp;
1560 }
1561
1562 /* There is nothing suitable in the normal free list - next try
1563 * allocating from the oversized block list.
1564 */
1565 {
1566 word_t *this;
1567 word_t wsize = size / GRANULARITY; /* size incl overhead in words */
1568
1569 for (this = sfltable[SMALL_BLOCK_NUM] ; this; this = BLOCK_NEXT(this))
1570 {
1571 word_t bsize = *this & M_MASK;
1572 word_t rsize = bsize - wsize;
1573
1574 /* Make sure that the split leaves a legal block behind */
1575 if (bsize < wsize + T_OVERHEAD + SMALL_BLOCK_SPLIT_MIN)
1576 continue;
1577
1578 /* If the split leaves behind a normally sized small
1579 * block, move it over to the appropriate free list.
1580 * Otherwise, just update the size and magic header fields
1581 * but keep this block in the oversized list.
1582 */
1583 if (rsize <= SMALL_BLOCK_MAX)
1584 {
1585 /* Unlink it from this list */
1586 UNLINK_SMALL_FREE(this);
1587
1588 /* Put it into the real free list */
1589 MAKE_SMALL_FREE(this, rsize);
1590 }
1591 else
1592 {
1593 /* Just modify the size and move the .prev pointer
1594 * and size field.
1595 */
1596 count_back(&small_free_stat, bsize * GRANULARITY);
1597
1598 this[M_SIZE] &= (PREV_BLOCK|M_DEFRAG);
1599 this[M_SIZE] |= rsize | (THIS_BLOCK|M_REF);
1600 this[M_PLINK(rsize)] = this[M_PLINK(bsize)];
1601 this[M_PLINK(rsize)-1] = rsize;
1602
1603 #ifdef MALLOC_CHECK
1604 this[M_MAGIC] = sfmagic[SIZE_MOD_INDEX(rsize*GRANULARITY, sfmagic)];
1605 #endif
1606
1607 count_up(&small_free_stat, rsize * GRANULARITY);
1608 }
1609
1610 /* Split off the allocated small block from the end
1611 * The front remains in the freelist.
1612 */
1613 this += rsize;
1614
1615 /* Fill in the header */
1616 this[M_SIZE] = wsize | (PREV_BLOCK|M_GC_FREE|M_REF);
1617 this[wsize] &= ~PREV_BLOCK;
1618 MAKE_SMALL_CHECK_UNCHECKED(this,size);
1619
1620 this += M_OVERHEAD;
1621
1622 MADVISE(this, orig_size);
1623
1624 #ifdef DEBUG_MALLOC_ALLOCS
1625 ulog2f("smalloc(%d / %d): Split oversized block "
1626 , orig_size, size);
1627 dprintf2( gcollect_outfd, "(%d / %d bytes): left with block of "
1628 , (p_int)(bsize - T_OVERHEAD) * GRANULARITY, (p_int)bsize * GRANULARITY);
1629 dprintf2( gcollect_outfd, "%d / %d bytes.\n"
1630 , (p_int)(rsize - T_OVERHEAD) * GRANULARITY
1631 , (p_int)rsize * GRANULARITY);
1632 #endif
1633
1634 in_malloc--;
1635 return (POINTER)this;
1636 }
1637 } /* allocation from oversized lists */
1638
1639 /* Next, try splitting off the memory from one of the larger
1640 * listed free small blocks.
1641 * Search from the largest blocks, and stop when splits
1642 * would result in too small blocks.
1643 */
1644 for ( ix = SMALL_BLOCK_NUM-1
1645 ; ix >= (int)(SIZE_INDEX(size) + T_OVERHEAD + SMALL_BLOCK_SPLIT_MIN)
1646 ; ix--
1647 )
1648 {
1649 word_t *pt, *split;
1650 size_t wsize, usize;
1651
1652 if (!sfltable[ix]) /* No block available */
1653 continue;
1654
1655 wsize = size / GRANULARITY; /* size incl. overhead in words */
1656
1657 /* Remove the block from the free list */
1658 pt = sfltable[ix];
1659 UNLINK_SMALL_FREE(pt);
1660
1661 /* Split off the unused part as new block */
1662 split = pt + wsize;
1663 usize = ix + T_OVERHEAD + SMALL_BLOCK_MIN - wsize;
1664 split[M_SIZE] = 0; /* No PREV_BLOCK */
1665 MAKE_SMALL_FREE(split, usize);
1666
1667 /* Initialize the header of the new block */
1668 pt[M_SIZE] &= PREV_BLOCK;
1669 pt[M_SIZE] |= wsize | (M_GC_FREE|M_REF);
1670 MAKE_SMALL_CHECK_UNCHECKED(pt, size);
1671
1672 pt += M_OVERHEAD;
1673
1674 MADVISE(pt, orig_size);
1675
1676 #ifdef DEBUG_MALLOC_ALLOCS
1677 ulog2f("smalloc(%d / %d): Split block "
1678 , orig_size, size);
1679 dprintf2( gcollect_outfd, "(%d / %d bytes): left with block of "
1680 , (p_int)(ix - T_OVERHEAD) * GRANULARITY, (p_int)ix * GRANULARITY);
1681 dprintf2( gcollect_outfd, "%d / %d bytes.\n"
1682 , (p_int)(usize - T_OVERHEAD) * GRANULARITY, (p_int)usize * GRANULARITY);
1683 #endif
1684
1685 in_malloc--;
1686 return (POINTER)pt;
1687 } /* allocation from larger blocks */
1688
1689 /* At this point, there was nothing in the free lists.
1690 * If this is the first pass, defragment the memory and try again
1691 * (the defragmentation routine returns whether a retry is useful).
1692 * If this is the second pass, force retry to be FALSE, thus
1693 * terminating the loop.
1694 */
1695 if (!retry)
1696 retry = defragment_small_lists(size / GRANULARITY);
1697 else
1698 retry = MY_FALSE;
1699 } while (retry);
1700
1701 /* At this point, we couldn't find a suitable block in the free lists,
1702 * thus allocate a new small chunk.
1703 * If this is the first small chunk of all, or if the small_chunk_size
1704 * has been modified from the default (happens for the second small
1705 * chunk allocation), try to get fresh memory from the system.
1706 *
1707 * Note: Changes here must be mirrored in mem_consolidate().
1708 */
1709 {
1710 word_t * new_chunk;
1711 word_t chunk_size;
1712
1713 new_chunk = (word_t*)large_malloc_int(small_chunk_size + sizeof(word_t*)
1714 , (last_small_chunk == NULL)
1715 || (small_chunk_size != SMALL_CHUNK_SIZE)
1716 );
1717
1718 /* If this is the first small chunk allocation, it might fail because
1719 * the driver was configured with a too big min_small_malloced value.
1720 * If that happens, try again with the normal value.
1721 */
1722 if (new_chunk == NULL && small_chunk_size != SMALL_CHUNK_SIZE)
1723 {
1724 dprintf1(2, "Low on MEMORY: Failed to allocated MIN_SMALL_MALLOCED "
1725 "block of %d bytes.\n"
1726 , (p_int)(small_chunk_size)
1727 );
1728 small_chunk_size = SMALL_CHUNK_SIZE;
1729 new_chunk = (word_t*)large_malloc_int(small_chunk_size+sizeof(word_t*)
1730 , MY_TRUE);
1731 }
1732
1733 if (new_chunk == NULL)
1734 {
1735 dprintf1(2, "Low on MEMORY: Failed to allocated small chunk "
1736 "block of %d bytes.\n"
1737 , (p_int)(small_chunk_size)
1738 );
1739 in_malloc--;
1740 return NULL;
1741 }
1742
1743 /* Enter the chunk into the chunk list and reset the small_cunk_size
1744 * to the ongoing value.
1745 */
1746
1747 chunk_size = new_chunk[-ML_OVERHEAD] - ML_OVERHEAD - 2;
1748 /* The payload size of the new chunk in words (ie. sans
1749 * large block overhead, chunk link pointer and final sentinel block).
1750 */
1751
1752 *new_chunk = (word_t)last_small_chunk;
1753 last_small_chunk = new_chunk++;
1754
1755 count_up(&small_chunk_stat, new_chunk[-ML_OVERHEAD-1] * GRANULARITY);
1756 count_up(&small_chunk_wasted, GRANULARITY*(M_OVERHEAD+1));
1757
1758 small_chunk_size = SMALL_CHUNK_SIZE;
1759
1760 /* The last word in the chunk is a fake permanently allocated small
1761 * block, so that the block merging routine has something to put the
1762 * PREV_BLOCK flag into.
1763 */
1764 new_chunk[chunk_size] = 1 | M_REF;
1765
1766 /* Use the end of the new chunk before the sentinel block to satisfy
1767 * the allocation and enter the rest at the front as free block into
1768 * the oversized free list.
1769 */
1770 chunk_size -= size / GRANULARITY;
1771 new_chunk[M_SIZE] = 0;
1772 MAKE_SMALL_FREE(new_chunk, chunk_size);
1773
1774 temp = new_chunk + chunk_size;
1775
1776 temp[M_SIZE] = (size / GRANULARITY) | (PREV_BLOCK|M_GC_FREE|M_REF);
1777 MAKE_SMALL_CHECK_UNCHECKED(temp, size);
1778
1779 temp += M_OVERHEAD;
1780
1781 MADVISE(temp, orig_size);
1782 in_malloc--;
1783 return (POINTER)temp;
1784 } /* allocate from a new small chunk */
1785 } /* mem_alloc() */
1786
1787 /*-------------------------------------------------------------------------*/
1788 static void
sfree(POINTER ptr)1789 sfree (POINTER ptr)
1790
1791 /* Return the memoryblock <ptr> to the allocator.
1792 * This function does the actual freeing, without checking for mutexes
1793 * and stack gaps; it is also used internally by the allocator to free
1794 * the memory reserves.
1795 */
1796
1797 {
1798 word_t *block;
1799 word_t bsize, i;
1800
1801 if (!ptr)
1802 return;
1803
1804 mem_mark_collectable(ptr);
1805
1806 /* Get the real block address and size */
1807 block = (word_t *) ptr;
1808 block -= M_OVERHEAD;
1809 bsize = i = block[M_SIZE] & M_MASK;
1810
1811 if (bsize > SMALL_BLOCK_MAX)
1812 {
1813 /* It's a big block */
1814 large_free(ptr);
1815 return;
1816 }
1817
1818 /* It's a small block: put it back into the free list */
1819
1820 count_back(&small_alloc_stat, bsize * GRANULARITY);
1821 i -= SMALL_BLOCK_MIN + T_OVERHEAD;
1822
1823 #ifdef MALLOC_EXT_STATISTICS
1824 extstats[i].num_xfree++;
1825 extstats[i].cur_alloc--;
1826 #endif /* MALLOC_EXT_STATISTICS */
1827
1828 #ifdef MALLOC_CHECK
1829 if (block[M_MAGIC] == sfmagic[i % NELEM(sfmagic)])
1830 {
1831 in_malloc = 0;
1832 fatal("mem_free: block %lx size %lu (user %lx) freed twice\n"
1833 , (unsigned long)block, (unsigned long)(i * GRANULARITY)
1834 , (unsigned long)ptr);
1835 }
1836 if (block[M_MAGIC] != samagic[i % NELEM(samagic)])
1837 {
1838 in_malloc = 0;
1839 fatal("mem_free: block %p magic match failed: "
1840 "size %lu, expected %lx, found %lx\n"
1841 , block, (unsigned long)(i * GRANULARITY), samagic[i], block[M_MAGIC]);
1842 }
1843 #endif
1844
1845 MAKE_SMALL_FREE(block, bsize);
1846 } /* sfree() */
1847
1848 /*-------------------------------------------------------------------------*/
1849 static void
mem_free(POINTER ptr)1850 mem_free (POINTER ptr)
1851
1852 /* Return the memoryblock <ptr> to the allocator.
1853 * This is a wrapper for sfree() which performs checks for stack-gaps
1854 * and such.
1855 */
1856
1857 {
1858 if (!ptr)
1859 return;
1860
1861 assert_stack_gap();
1862
1863 if (in_malloc++)
1864 {
1865 in_malloc = 0;
1866 writes(1, "Multiple threads in mem_free()\n");
1867 fatal("Multiple threads in mem_free()\n");
1868 /* NOTREACHED */
1869 return;
1870 }
1871
1872 sfree(ptr);
1873 in_malloc--;
1874 } /* mem_free() */
1875
1876 /*-------------------------------------------------------------------------*/
1877 static POINTER
mem_realloc(POINTER p,size_t size)1878 mem_realloc (POINTER p, size_t size)
1879
1880 /* Reallocate block <p> to the new size of <size> and return the pointer.
1881 * The memory is not aligned and subject to GC.
1882 */
1883
1884 {
1885 POINTER t;
1886 size_t old_size;
1887
1888 old_size = mem_block_size(p);
1889 if (old_size >= size)
1890 return p;
1891
1892 t = mem_alloc(size);
1893 if (t == NULL)
1894 return NULL;
1895
1896 memcpy(t, p, old_size);
1897 mem_free(p);
1898 return t;
1899 } /* mem_realloc() */
1900
1901 /*=========================================================================*/
1902
1903 /* LARGE BLOCKS */
1904
1905 /*-------------------------------------------------------------------------*/
1906
1907 #define l_next_block(p) ((p) + (p)[M_LSIZE] )
1908 #define l_prev_block(p) ((p) - (*((p)-2)) )
1909 /* Address the previous resp. this block.
1910 */
1911
1912 #define l_prev_free(p) (!(*(p) & PREV_BLOCK))
1913 #define l_next_free(p) (!(*l_next_block(p) & THIS_BLOCK))
1914 /* Check if the previous resp. the next block is free.
1915 */
1916
1917 /*-------------------------------------------------------------------------*/
1918
1919 /* Extra types and definitions for the AVL routines */
1920
1921 #if defined (sun) || defined(__linux__)
1922 /* there is a type signed char */
1923 typedef signed char balance_t;
1924 # define BALANCE_T_BITS 8
1925 #else
1926 typedef short balance_t;
1927 # define BALANCE_T_BITS 16
1928 #endif
1929 #if defined(sparc)
1930 /* try to avoid multiple shifts, because these are costly */
1931 # define NO_BARREL_SHIFT
1932 #endif
1933
1934 struct free_block
1935 {
1936 word_t size;
1937 struct free_block *parent, *left, *right;
1938 balance_t balance;
1939 #ifdef USE_AVL_FREELIST
1940 struct free_block * prev; /* prev free block in freelist
1941 * NULL for the AVL node
1942 */
1943 struct free_block * next; /* next free block in freelist */
1944 #endif /* USE_AVL_FREELIST */
1945 short align_dummy;
1946 };
1947
1948 /* Prepare two nodes for the free tree that will never be removed,
1949 * so that we can always assume that the tree is and remains non-empty.
1950 */
1951 extern struct free_block dummy2; /* forward */
1952
1953 static struct free_block dummy =
1954 { /* size */ 0
1955 , /* parent */ &dummy2, /* left */ 0, /* right */ 0, /* balance */ 0
1956 #ifdef USE_AVL_FREELIST
1957 , /* prev */ 0, /* next */ 0
1958 #endif /* USE_AVL_FREELIST */
1959 };
1960
1961 struct free_block dummy2 =
1962 { /* size */ 0
1963 , /* parent */ 0, /* left */ &dummy, /* right */ 0, /* balance */ -1
1964 #ifdef USE_AVL_FREELIST
1965 , /* prev */ 0, /* next */ 0
1966 #endif /* USE_AVL_FREELIST */
1967 };
1968
1969 static struct free_block *free_tree = &dummy2;
1970
1971 #ifdef DEBUG_AVL
1972
1973 static Bool inconsistency = MY_FALSE;
1974
1975 /*-------------------------------------------------------------------------*/
1976 static void
_check_next(struct free_block * p)1977 _check_next (struct free_block *p)
1978
1979 /* DEBUG_AVL: check this node <p> and both subnodes.
1980 */
1981
1982 {
1983 if (!p)
1984 return;
1985
1986 {
1987 word_t *q;
1988
1989 q = ((word_t *)p)-ML_OVERHEAD;
1990 q += *q;
1991 }
1992 _check_next(p->left);
1993 _check_next(p->right);
1994 } /* _check_next() */
1995
1996 /*-------------------------------------------------------------------------*/
1997 static void
check_next(void)1998 check_next(void)
1999
2000 /* DEBUG_AVL: check the free_tree.
2001 */
2002
2003 {
2004 _check_next(free_tree);
2005 } /* check_next() */
2006
2007 /*-------------------------------------------------------------------------*/
2008 static int
check_avl(struct free_block * parent,struct free_block * p)2009 check_avl (struct free_block *parent, struct free_block *p)
2010
2011 /* DEBUG_AVL: check the consistency of the AVL-(sub)tree in node <p>.
2012 * Return the size of the subtree, and set inconsistency to TRUE
2013 * if it is inconsistent.
2014 */
2015
2016 {
2017 int left, right;
2018
2019 if (!p)
2020 return 0;
2021
2022 left = check_avl(p, p->left );
2023 right = check_avl(p, p->right);
2024
2025 if (p->balance != right - left || p->balance < -1 || p->balance > 1)
2026 {
2027 writes (2, "Inconsistency in avl node: invalid balance!\n");
2028 dprintf1(2, " node:%x\n",(p_uint)p);
2029 dprintf1(2, " size: %d\n", p->size);
2030 dprintf1(2, " left node:%x\n",(p_uint)p->left);
2031 dprintf1(2, " left height: %d\n",left );
2032 dprintf1(2, " right node:%x\n",(p_uint)p->right);
2033 dprintf1(2, " right height: %d\n",right);
2034 dprintf1(2, " alleged balance: %d\n",p->balance);
2035 inconsistency = MY_TRUE;
2036 }
2037
2038 if (p->parent != parent)
2039 {
2040 writes (2, "Inconsistency in avl node: invalid parent!\n");
2041 dprintf1(2, " node:%x\n",(p_uint)p);
2042 dprintf1(2, " size: %d\n", p->size);
2043 dprintf1(2, " parent: %x\n", (p_uint)parent);
2044 dprintf1(2, " parent size: %d\n", parent->size);
2045 dprintf1(2, " alleged parent: %x\n", (p_uint)p->parent);
2046 dprintf1(2, " alleged parent size: %d\n", p->parent->size);
2047 dprintf1(2, " left height: %d\n",left );
2048 dprintf1(2, " right height: %d\n",right);
2049 dprintf1(2, " alleged balance: %d\n",p->balance);
2050 inconsistency = MY_TRUE;
2051 }
2052 return left > right ? left+1 : right+1;
2053 } /* check_avl() */
2054
2055 /*-------------------------------------------------------------------------*/
2056 static int
do_check_avl(void)2057 do_check_avl(void)
2058
2059 /* DEBUG_AVL: Check the free_tree for consistency.
2060 * Return 0 on success, otherwise abort the driver.
2061 */
2062
2063 {
2064 check_avl(0, free_tree);
2065 if (inconsistency)
2066 {
2067 fflush(stderr);
2068 fflush(stdout);
2069 in_malloc = 0;
2070 fatal("Inconsistency could crash the driver\n");
2071 }
2072 return 0;
2073 } /* do_check_avl() */
2074
2075 /*-------------------------------------------------------------------------*/
2076 static Bool
contains(struct free_block * p,struct free_block * q)2077 contains (struct free_block *p, struct free_block *q)
2078
2079 /* DEBUG_AVL: Check if free_block <q> is contained in the sub-tree at
2080 * and below <p>.
2081 */
2082
2083 {
2084 return p == q || (p && (contains(p->left, q) || contains(p->right, q)));
2085 } /* contains() */
2086
2087 /*-------------------------------------------------------------------------*/
2088 static int
check_free_block(void * m)2089 check_free_block (void *m)
2090
2091 /* DEBUG_AVL: Check if free memory at <m> is contained in the free_tree.
2092 * Return 0 on success, otherwise abort the driver.
2093 */
2094
2095 {
2096 word_t *p;
2097 int size;
2098
2099 p = (word_t *)(((char *)m)-M_OVERHEAD*GRANULARITY);
2100 size = p[M_LSIZE];
2101 if (!(*(p+size) & THIS_BLOCK))
2102 {
2103 if (!contains(free_tree, (struct free_block *)(p+size+T_OVERHEAD)) )
2104 {
2105 in_malloc = 0;
2106 fatal("not found\n");
2107 }
2108 }
2109 return 0;
2110 } /* check_free_block() */
2111
2112 #else /* !DEBUG_AVL */
2113
2114 #define do_check_avl() 0
2115
2116 #endif /* DEBUG_AVL */
2117
2118 /*-------------------------------------------------------------------------*/
2119 static void
remove_from_free_list(word_t * ptr)2120 remove_from_free_list (word_t *ptr)
2121
2122 /* Remove the memory block <ptr> from the free list.
2123 */
2124
2125 {
2126 struct free_block *p, *q, *r, *s, *t;
2127
2128 #ifdef MALLOC_CHECK
2129 if (ptr[M_MAGIC] != LFMAGIC)
2130 {
2131 in_malloc = 0;
2132 fatal("remove_from_free_list: block %p, "
2133 "magic match failed: expected %lx, "
2134 "found %lx\n"
2135 , ptr
2136 , (unsigned long)LFMAGIC
2137 , (unsigned long)ptr[M_MAGIC]
2138 );
2139 }
2140 #endif
2141 p = (struct free_block *)(ptr+M_OVERHEAD);
2142 count_back(&large_free_stat, p->size);
2143 #ifdef MALLOC_EXT_STATISTICS
2144 extstats[SMALL_BLOCK_NUM+1].cur_free--;
2145 #endif /* MALLOC_EXT_STATISTICS */
2146 #ifdef USE_AVL_FREELIST
2147 /* Unlink from AVL freelist */
2148 if (p->prev) p->prev->next = p->next;
2149 if (p->next) p->next->prev = p->prev;
2150 /* If the block is not the AVL node itself, we're done */
2151 if (p->prev)
2152 return;
2153
2154 /* <p> is the AVL node itself, but if there is another block free of
2155 * the same size, just transfer over the node.
2156 */
2157 if (p->next)
2158 {
2159 struct free_block *next = p->next;
2160
2161 if (p == free_tree)
2162 {
2163 #ifdef DEBUG
2164 if (p->parent)
2165 {
2166 fatal("(remove_from_free_list) Node %p (size %ld) is the AVL tree root, but has a parent\n", p, (long)p->size);
2167 }
2168 #endif
2169 free_tree = p->next;
2170 }
2171 else
2172 {
2173 #ifdef DEBUG
2174 if (!p->parent)
2175 {
2176 fatal("(remove_from_free_list) Node %p (size %ld) has neither a parent nor is it the AVL tree root.\n", p, (long)p->size);
2177 }
2178 #endif
2179 if (p->parent->left == p)
2180 p->parent->left = p->next;
2181 else
2182 p->parent->right = p->next;
2183 }
2184
2185 /* We must not clobber p->next->next when copying the node! */
2186 p->next = next->next;
2187 *next = *p;
2188
2189 /* Now adjust the parent pointer of the sub-nodes to the new
2190 * parent node.
2191 */
2192 if (p->left) p->left->parent = next;
2193 if (p->right) p->right->parent = next;
2194
2195 return;
2196 }
2197
2198 /* It's the AVL itself, and there is no other free block of the same
2199 * size: remove the node from the tree.
2200 */
2201 num_avl_nodes--;
2202 #endif /* USE_AVL_FREELIST */
2203 #ifdef DEBUG_AVL
2204 dprintf1(2, "node:%x\n",(p_uint)p);
2205 dprintf1(2, "size:%d\n",p->size);
2206 #endif
2207 if (p->left) {
2208 if ( NULL != (q = p->right) ) {
2209 /* two childs */
2210 s = q;
2211 do { r = q; q = r->left; } while(q != NULL);
2212 if (r == s) {
2213 r->left = s = p->left;
2214 s->parent = r;
2215 if ( NULL != (r->parent = s = p->parent) ) {
2216 if (p == s->left) {
2217 s->left = r;
2218 } else {
2219 s->right = r;
2220 }
2221 } else {
2222 free_tree = r;
2223 }
2224 r->balance = p->balance;
2225 p = r;
2226 goto balance_right;
2227 } else {
2228 t = r->parent;
2229 if ( NULL != (t->left = s = r->right) ) {
2230 s->parent = t;
2231 }
2232 r->balance = p->balance;
2233 r->left = s = p->left;
2234 s->parent = r;
2235 r->right = s = p->right;
2236 s->parent = r;
2237 if ( NULL != (r->parent = s = p->parent) ) {
2238 if (p == s->left) {
2239 s->left = r;
2240 } else {
2241 s->right = r;
2242 }
2243 } else {
2244 free_tree = r;
2245 }
2246 p = t;
2247 goto balance_left;
2248 }
2249 } else /* no right child, but left child */ {
2250 /* We set up the free list in a way so that there will remain at
2251 least two nodes, and the avl property ensures that the left
2252 child is a leaf ==> there is a parent */
2253 s = p;
2254 p = s->parent;
2255 r = s->left;
2256 r->parent = p;
2257 if (s == p->left) {
2258 p->left = r;
2259 goto balance_left;
2260 } else {
2261 p->right = r;
2262 goto balance_right;
2263 }
2264 }
2265 } else /* no left child */ {
2266 /* We set up the free list in a way so that there is a node left
2267 of all used nodes, so there is a parent */
2268 s = p;
2269 p = s->parent;
2270 if ( NULL != (q = r = s->right) ) {
2271 r->parent = p;
2272 }
2273 if (s == p->left) {
2274 p->left = r;
2275 goto balance_left;
2276 } else {
2277 p->right = r;
2278 goto balance_right;
2279 }
2280 }
2281 balance_q:
2282 r = p;
2283 p = q;
2284 if (r == p->right) {
2285 balance_t b;
2286 balance_right:
2287 b = p->balance;
2288 if (b > 0) {
2289 p->balance = 0;
2290 if (NULL != (q = p->parent)) goto balance_q;
2291 return;
2292 } else if (b < 0) {
2293 r = p->left;
2294 b = r->balance;
2295 if (b <= 0) {
2296 /* R-Rotation */
2297 #ifdef DEBUG_AVL
2298 dprintf1(2, "r->balance: %d\n", r->balance);
2299 #endif
2300 if ( NULL != (p->left = s = r->right) ) {
2301 s->parent = p;
2302 }
2303 r->right = p;
2304 s = p->parent;
2305 p->parent = r;
2306 b += 1;
2307 r->balance = b;
2308 b = -b;
2309 #ifdef DEBUG_AVL
2310 dprintf1(2, "node r: %x\n", (p_uint)r);
2311 dprintf1(2, "r->balance: %d\n", r->balance);
2312 dprintf1(2, "node p: %x\n", (p_uint)p);
2313 p->balance = b;
2314 dprintf1(2, "p->balance: %d\n", p->balance);
2315 dprintf1(2, "r-height: %d\n", check_avl(r->parent, r));
2316 #endif
2317 if ( NULL != (r->parent = s) ) {
2318 if ( 0 != (p->balance = b) ) {
2319 if (p == s->left) {
2320 s->left = r;
2321 return;
2322 } else {
2323 s->right = r;
2324 return;
2325 }
2326 }
2327 if (p == s->left) {
2328 /* left from parent */
2329 goto balance_left_s;
2330 } else {
2331 /* right from parent */
2332 p = s;
2333 p->right = r;
2334 goto balance_right;
2335 }
2336 }
2337 p->balance = b;
2338 free_tree = r;
2339 return;
2340 } else /* r->balance == +1 */ {
2341 /* LR-Rotation */
2342 balance_t b2;
2343
2344 t = r->right;
2345 b = t->balance;
2346 if ( NULL != (p->left = s = t->right) ) {
2347 s->parent = p;
2348 }
2349 if ( NULL != (r->right = s = t->left) ) {
2350 s->parent = r;
2351 }
2352 t->left = r;
2353 t->right = p;
2354 r->parent = t;
2355 s = p->parent;
2356 p->parent = t;
2357 #ifdef NO_BARREL_SHIFT
2358 b = -b;
2359 b2 = b >> 1;
2360 r->balance = b2;
2361 b -= b2;
2362 p->balance = b;
2363 #else
2364 b2 = (unsigned char)b >> 7;
2365 p->balance = b2;
2366 b2 = -b2 -b;
2367 r->balance = b2;
2368 #endif
2369 t->balance = 0;
2370 #ifdef DEBUG_AVL
2371 dprintf1(2, "t-height: %d\n", check_avl(t->parent, t));
2372 #endif
2373 if ( NULL != (t->parent = s) ) {
2374 if (p == s->left) {
2375 p = s;
2376 s->left = t;
2377 goto balance_left;
2378 } else {
2379 p = s;
2380 s->right = t;
2381 goto balance_right;
2382 }
2383 }
2384 free_tree = t;
2385 return;
2386 }
2387 } else /* p->balance == 0 */ {
2388 p->balance = -1;
2389 return;
2390 }
2391 } else /* r == p->left */ {
2392 balance_t b;
2393
2394 goto balance_left;
2395 balance_left_s:
2396 p = s;
2397 s->left = r;
2398 balance_left:
2399 b = p->balance;
2400 if (b < 0) {
2401 p->balance = 0;
2402 if ( NULL != (q = p->parent) ) goto balance_q;
2403 return;
2404 } else if (b > 0) {
2405 r = p->right;
2406 b = r->balance;
2407 if (b >= 0) {
2408 /* L-Rotation */
2409 #ifdef DEBUG_AVL
2410 dprintf1(2, "r->balance: %d\n", r->balance);
2411 #endif
2412 if ( NULL != (p->right = s = r->left) ) {
2413 s->parent = p;
2414 }
2415 /* subtree relocated */
2416 r->left = p;
2417 s = p->parent;
2418 p->parent = r;
2419 b -= 1;
2420 r->balance = b;
2421 b = -b;
2422 #ifdef DEBUG_AVL
2423 /* balances calculated */
2424 dprintf1(2, "node r: %x\n", (p_uint)r);
2425 dprintf1(2, "r->balance: %d\n", r->balance);
2426 dprintf1(2, "node p: %x\n", (p_uint)p);
2427 p->balance = b;
2428 dprintf1(2, "p->balance: %d\n", p->balance);
2429 dprintf1(2, "r-height: %d\n", check_avl(r->parent, r));
2430 #endif
2431 if ( NULL != (r->parent = s) ) {
2432 if ( 0 != (p->balance = b) ) {
2433 if (p == s->left) {
2434 s->left = r;
2435 return;
2436 } else {
2437 s->right = r;
2438 return;
2439 }
2440 }
2441 if (p == s->left) {
2442 /* left from parent */
2443 goto balance_left_s;
2444 } else {
2445 /* right from parent */
2446 p = s;
2447 p->right = r;
2448 goto balance_right;
2449 }
2450 }
2451 p->balance = b;
2452 free_tree = r;
2453 return;
2454 } else /* r->balance == -1 */ {
2455 /* RL-Rotation */
2456 balance_t b2;
2457
2458 t = r->left;
2459 b = t->balance;
2460 if ( NULL != (p->right = s = t->left) ) {
2461 s->parent = p;
2462 }
2463 if ( NULL != (r->left = s = t->right) ) {
2464 s->parent = r;
2465 }
2466 t->right = r;
2467 t->left = p;
2468 r->parent = t;
2469 s = p->parent;
2470 p->parent = t;
2471 #ifdef NO_BARREL_SHIFT
2472 b = -b;
2473 b2 = b >> 1;
2474 p->balance = b2;
2475 b -= b2;
2476 r->balance = b;
2477 #else
2478 b2 = (unsigned char)b >> 7;
2479 r->balance = b2;
2480 b2 = -b2 -b;
2481 p->balance = b2;
2482 #endif
2483 t->balance = 0;
2484 if ( NULL != (t->parent = s) ) {
2485 if (p == s->left) {
2486 p = s;
2487 s->left = t;
2488 goto balance_left;
2489 } else {
2490 s->right = t;
2491 p = s;
2492 goto balance_right;
2493 }
2494 }
2495 free_tree = t;
2496 return;
2497 }
2498 } else /* p->balance == 0 */ {
2499 p->balance++;
2500 return;
2501 }
2502 }
2503 } /* remove_from_free_list() */
2504
2505 /*-------------------------------------------------------------------------*/
2506 static void
add_to_free_list(word_t * ptr)2507 add_to_free_list (word_t *ptr)
2508
2509 /* Add the memory block <ptr> to the free list.
2510 */
2511
2512 {
2513 word_t size;
2514 struct free_block *p, *q, *r;
2515 /* When there is a distinction between data and address registers and/or
2516 accesses, gcc will choose data type for q, so an assignmnt to q will
2517 faciliate branching
2518 */
2519
2520 #ifdef MALLOC_CHECK
2521 ptr[M_MAGIC] = LFMAGIC;
2522 #endif
2523 size = ptr[M_LSIZE];
2524 #ifdef DEBUG_AVL
2525 dprintf1(2, "size:%d\n",size);
2526 #endif
2527 q = (struct free_block *)size; /* this assignment is just a hint for
2528 * register choice
2529 */
2530 r = (struct free_block *)(ptr+M_OVERHEAD);
2531 count_up(&large_free_stat, size);
2532 #ifdef MALLOC_EXT_STATISTICS
2533 extstats[SMALL_BLOCK_NUM+1].cur_free++;
2534 extstat_update_max(extstats+SMALL_BLOCK_NUM+1);
2535 #endif /* MALLOC_EXT_STATISTICS */
2536
2537 r->size = size;
2538 r->parent = NULL;
2539 r->left = 0;
2540 r->right = 0;
2541 r->balance = 0;
2542 #ifdef USE_AVL_FREELIST
2543 r->prev = NULL;
2544 r->next = NULL;
2545 #endif /* USE_AVL_FREELIST */
2546
2547 q = free_tree;
2548 for ( ; ; /*p = q*/) {
2549 p = q;
2550 #ifdef DEBUG_AVL
2551 dprintf1(2, "checked node size %d\n",p->size);
2552 #endif
2553
2554 #ifdef USE_AVL_FREELIST
2555 if (size == p->size)
2556 {
2557 /* We can attach the block to an existing node */
2558 #ifdef MALLOC_ORDER_LARGE_FREELISTS
2559 struct free_block * tail = p;
2560
2561 /* Find the proper node after which to insert */
2562 if (p->next != NULL)
2563 {
2564 while (tail->next && tail->next < r)
2565 {
2566 tail = tail->next;
2567 }
2568 }
2569
2570 r->next = tail->next;
2571 r->prev = tail;
2572
2573 if (r->next)
2574 r->next->prev = r;
2575 tail->next = r;
2576 #else
2577 r->next = p->next;
2578 r->prev = p;
2579
2580 if (r->next)
2581 r->next->prev = r;
2582 p->next = r;
2583 #endif /* MALLOC_ORDER_LARGE_FREELISTS */
2584
2585 return;
2586 }
2587 #endif /* USE_AVL_FREELIST */
2588 if (size < p->size) {
2589 if ( NULL != (q = p->left) ) {
2590 continue;
2591 }
2592 /* add left */
2593 p->left = r;
2594 break;
2595 } else /* >= */ {
2596 if ( NULL != (q = p->right) ) {
2597 continue;
2598 }
2599 /* add right */
2600 p->right = r;
2601 break;
2602 }
2603 }
2604
2605 /* new leaf */
2606 r->parent = p;
2607 #ifdef USE_AVL_FREELIST
2608 num_avl_nodes++;
2609 #endif /* USE_AVL_FREELIST */
2610 #ifdef DEBUG_AVL
2611 dprintf2(2, "p %x->balance:%d\n",p, p->balance);
2612 #endif
2613 do {
2614 struct free_block *s;
2615
2616 if (r == p->left) {
2617 balance_t b;
2618
2619 if ( !(b = p->balance) ) {
2620 #ifdef DEBUG_AVL
2621 dprintf1(2, "p: %x\n", p);
2622 dprintf1(2, " p->size: %d\n", p->size);
2623 dprintf1(2, " p->balance: %d := -1\n", p->balance);
2624 dprintf1(2, " p->right-h: %d\n", check_avl(p, p->right));
2625 dprintf1(2, " p->left -h: %d\n", check_avl(p, p->left ));
2626 #endif
2627 /* growth propagation from left side */
2628 p->balance = -1;
2629 } else if (b < 0) {
2630 #ifdef DEBUG_AVL
2631 dprintf2(2, "p %x->balance:%d\n",p, p->balance);
2632 #endif
2633 if (r->balance < 0) {
2634 /* R-Rotation */
2635 if ( NULL != (p->left = s = r->right) ) {
2636 s->parent = p;
2637 }
2638 r->right = p;
2639 p->balance = 0;
2640 r->balance = 0;
2641 s = p->parent;
2642 p->parent = r;
2643 if ( NULL != (r->parent = s) ) {
2644 if ( s->left == p) {
2645 s->left = r;
2646 } else {
2647 s->right = r;
2648 }
2649 } else {
2650 free_tree = r;
2651 }
2652 } else /* r->balance == +1 */ {
2653 /* LR-Rotation */
2654 balance_t b2;
2655 struct free_block *t = r->right;
2656
2657 #ifdef DEBUG_AVL
2658 dprintf1(2, "t = %x\n",(p_uint)t);
2659 dprintf1(2, "r->balance:%d\n",r->balance);
2660 #endif
2661 if ( NULL != (p->left = s = t->right) ) {
2662 s->parent = p;
2663 }
2664 /* relocated right subtree */
2665 t->right = p;
2666 if ( NULL != (r->right = s = t->left) ) {
2667 s->parent = r;
2668 }
2669 /* relocated left subtree */
2670 t->left = r;
2671 b = t->balance;
2672 #ifdef NO_BARREL_SHIFT
2673 b = -b;
2674 b2 = b >> 1;
2675 r->balance = b2;
2676 b -= b2;
2677 p->balance = b;
2678 #else
2679 b2 = (unsigned char)b >> 7;
2680 p->balance = b2;
2681 b2 = -b2 -b;
2682 r->balance = b2;
2683 #endif
2684 t->balance = 0;
2685 /* balances calculated */
2686 s = p->parent;
2687 p->parent = t;
2688 r->parent = t;
2689 if ( NULL != (t->parent = s) ) {
2690 if ( s->left == p) {
2691 s->left = t;
2692 } else {
2693 s->right = t;
2694 }
2695 } else {
2696 free_tree = t;
2697 }
2698 #ifdef DEBUG_AVL
2699 dprintf1(2, "p->balance:%d\n",p->balance);
2700 dprintf1(2, "r->balance:%d\n",r->balance);
2701 dprintf1(2, "t->balance:%d\n",t->balance);
2702 /* LR-Rotation completed */
2703 #endif
2704 }
2705 break;
2706 } else /* p->balance == +1 */ {
2707 p->balance = 0;
2708 /* growth of left side balanced the node */
2709 break;
2710 }
2711 } else /* r == p->right */ {
2712 balance_t b;
2713
2714 if ( !(b = p->balance) )
2715 {
2716 #ifdef DEBUG_AVL
2717 dprintf1(2, "p: %x\n", p);
2718 dprintf1(2, " p->size: %d\n", p->size);
2719 dprintf1(2, " p->balance: %d += 1\n", p->balance);
2720 dprintf1(2, " p->right-h: %d\n", check_avl(p, p->right));
2721 dprintf1(2, " p->left -h: %d\n", check_avl(p, p->left ));
2722 #endif
2723 /* growth propagation from right side */
2724 p->balance++;
2725 } else if (b > 0) {
2726 if (r->balance > 0) {
2727 /* L-Rotation */
2728 if ( NULL != (p->right = s = r->left) ) {
2729 s->parent = p;
2730 }
2731 r->left = p;
2732 p->balance = 0;
2733 r->balance = 0;
2734 s = p->parent;
2735 p->parent = r;
2736 if ( NULL != (r->parent = s) ) {
2737 if ( s->left == p) {
2738 s->left = r;
2739 } else {
2740 s->right = r;
2741 }
2742 } else {
2743 free_tree = r;
2744 }
2745 } else /* r->balance == -1 */ {
2746 /* RL-Rotation */
2747 balance_t b2;
2748 struct free_block *t = r->left;
2749
2750 #ifdef DEBUG_AVL
2751 dprintf1(2, "t = %x\n",(p_uint)t);
2752 dprintf1(2, "r->balance:%d\n",r->balance);
2753 #endif
2754 if ( NULL != (p->right = s = t->left) ) {
2755 s->parent = p;
2756 }
2757 /* relocated left subtree */
2758 t->left = p;
2759 if ( NULL != (r->left = s = t->right) ) {
2760 s->parent = r;
2761 }
2762 /* relocated right subtree */
2763 t->right = r;
2764 b = t->balance;
2765 #ifdef NO_BARREL_SHIFT
2766 b = -b;
2767 b2 = b >> 1;
2768 p->balance = b2;
2769 b -= b2;
2770 r->balance = b;
2771 #else
2772 b2 = (unsigned char)b >> 7;
2773 r->balance = b2;
2774 b2 = -b2 -b;
2775 p->balance = b2;
2776 #endif
2777 t->balance = 0;
2778 s = p->parent;
2779 p->parent = t;
2780 r->parent = t;
2781 if ( NULL != (t->parent = s) ) {
2782 if ( s->left == p) {
2783 s->left = t;
2784 } else {
2785 s->right = t;
2786 }
2787 } else {
2788 free_tree = t;
2789 }
2790 /* RL-Rotation completed */
2791 }
2792 break;
2793 } else /* p->balance == -1 */ {
2794 #ifdef DEBUG_AVL
2795 dprintf1(2, "p: %x\n", p);
2796 dprintf1(2, " p->balance: %d\n", p->balance);
2797 dprintf1(2, " p->right-h: %d\n", check_avl(p, p->right));
2798 dprintf1(2, " p->left -h: %d\n", check_avl(p, p->left ));
2799 #endif
2800 p->balance = 0;
2801 /* growth of right side balanced the node */
2802 break;
2803 }
2804 }
2805 r = p;
2806 p = p->parent;
2807 } while ( NULL != (q = p) );
2808 } /* add_to_free_list() */
2809
2810 /*-------------------------------------------------------------------------*/
2811 static void
build_block(word_t * ptr,word_t size)2812 build_block (word_t *ptr, word_t size)
2813
2814 /* Mark the memory block <ptr> of size <size> words(!) as unallocated.
2815 * Also used to initialize new memory blocks received from the system.
2816 */
2817
2818 {
2819 word_t tmp;
2820
2821 tmp = (*ptr & PREV_BLOCK);
2822 ptr[M_LSIZE] = size;
2823 *(ptr+size-2) = size; /* copy the size information */
2824 *(ptr) = tmp | M_MASK; /* marks this block as free */
2825 *(ptr+size) &= ~PREV_BLOCK; /* unset 'previous block' flag in next block */
2826 } /* build_block() */
2827
2828 /*-------------------------------------------------------------------------*/
2829 static void
mark_block(word_t * ptr)2830 mark_block (word_t *ptr)
2831
2832 /* Mark the memory block at <ptr> as allocated, used, and freeable
2833 * by the GC.
2834 */
2835
2836 {
2837 *l_next_block(ptr) |= PREV_BLOCK;
2838 *ptr |= THIS_BLOCK | M_GC_FREE | M_REF;
2839 } /* mark_block() */
2840
2841 /*-------------------------------------------------------------------------*/
2842 static word_t *
add_large_free(word_t * ptr,word_t block_size)2843 add_large_free (word_t *ptr, word_t block_size)
2844
2845 /* The large memory block <ptr> with size <block_size> is free:
2846 * add it to the free list after trying to coagulate it with adjacent
2847 * ones.
2848 * Result is the resulting pointer to the (possibly coagulated) free block.
2849 */
2850
2851 {
2852 /* If the next block is free, coagulate */
2853 if (!(*(ptr+block_size) & THIS_BLOCK))
2854 {
2855 remove_from_free_list(ptr+block_size);
2856 block_size += (ptr+block_size)[M_LSIZE];
2857 }
2858
2859 /* If the previous block is free, coagulate */
2860 if (l_prev_free(ptr))
2861 {
2862 remove_from_free_list(l_prev_block(ptr));
2863 block_size += l_prev_block(ptr)[M_LSIZE];
2864 ptr = l_prev_block(ptr);
2865 }
2866
2867 /* Mark the block as free and add it to the freelist */
2868 build_block(ptr, block_size);
2869 add_to_free_list(ptr);
2870
2871 return ptr;
2872 } /* add_large_free() */
2873
2874 /*-------------------------------------------------------------------------*/
2875 static char *
large_malloc(word_t size,Bool force_more)2876 large_malloc ( word_t size, Bool force_more)
2877
2878 /* Allocate a large or <size> bytes.
2879 *
2880 * If <force_more> is TRUE, the function first tries to allocate
2881 * more memory directly from the system. If that fails, it tries a normal
2882 * allocation. This feature is used to allocate small chunks for the
2883 * small block allocator.
2884 *
2885 * If memory from the system is allocated and <force_more>
2886 * is not TRUE (or it is in the retry), the allocator allocates at least
2887 * CHUNK_SIZE bytes. Any extra is immediately entered into the freelist.
2888 *
2889 * Return the pointer to the allocated memory block, or NULL when out
2890 * of memory (not when running in SYSTEM privilege).
2891 *
2892 * If the system runs out of memory, the following steps are taken:
2893 *
2894 * - if <force_more> is TRUE, it is set to FALSE and the allocation is tried
2895 * again, this time from the freelist.
2896 * - free the user reserve, then try again.
2897 * - if MASTER privilege: free the master reserve, then try again.
2898 * - if SYSTEM privilege: free the system reserve, then try again.
2899 * - if !SYSTEM privilege: set out_of_memory and return NULL
2900 * - if SYSTEM privilege: dump the lpc backtrace and exit(2) resp. fatal().
2901 *
2902 * If any of the reserves is freed, the gc_request flag is set.
2903 */
2904
2905 {
2906 word_t real_size;
2907 word_t *ptr;
2908 #if defined(HAVE_MADVISE) || defined(DEBUG) || defined(DEBUG_MALLOC_ALLOCS)
2909 size_t orig_size = size;
2910 #endif
2911
2912 size = (size + GRANULARITY*ML_OVERHEAD + GRANULARITY-1) / GRANULARITY; /* incl. overhead */
2913
2914 retry:
2915 ptr = NULL;
2916 if (!force_more)
2917 {
2918
2919 /* Find the best fit in the AVL tree */
2920
2921 struct free_block *p, *q, *r;
2922 word_t minsplit;
2923 word_t tempsize;
2924
2925 ptr += M_OVERHEAD; /* 'NULL' including overhead */
2926 minsplit = size + SMALL_BLOCK_MAX + 1;
2927 /* The split-off block must still count as 'large' */
2928 q = free_tree;
2929 for ( ; ; ) {
2930 p = q;
2931 #ifdef DEBUG_AVL
2932 dprintf1(2, "checked node size %d\n",p->size);
2933 #endif
2934 tempsize = p->size;
2935 if (minsplit < tempsize) {
2936 ptr = (word_t*)p; /* remember this fit */
2937 if ( NULL != (q = p->left) ) {
2938 continue;
2939 }
2940 /* We don't need that much, but that's the best fit we have */
2941 break;
2942 } else if (size > tempsize) {
2943 if ( NULL != (q = p->right) ) {
2944 continue;
2945 }
2946 break;
2947 } else /* size <= tempsize <= minsplit */ {
2948 if (size == tempsize) {
2949 ptr = (word_t*)p;
2950 break;
2951 }
2952 /* size < tempsize */
2953 if ( NULL != (q = p->left) ) {
2954 r = p;
2955 /* if r is used in the following loop instead of p,
2956 * gcc will handle q very inefficient throughout the
2957 * function large_malloc()
2958 */
2959 for (;;) {
2960 p = q;
2961 tempsize = p->size;
2962 if (size < tempsize) {
2963 if ( NULL != (q = p->left) ) {
2964 continue;
2965 }
2966 break;
2967 } else if (size > tempsize ) {
2968 if ( NULL != (q = p->right) ) {
2969 continue;
2970 }
2971 break;
2972 } else {
2973 ptr = (word_t*)p;
2974 goto found_fit;
2975 }
2976 }
2977 p = r;
2978 }
2979 tempsize = p->size;
2980 if (minsplit > tempsize) {
2981 if ( NULL != (q = p->right) ) {
2982 for (;;) {
2983 p = q;
2984 tempsize = p->size;
2985 if (minsplit <= tempsize) {
2986 ptr = (word_t*)p; /* remember this fit */
2987 if ( NULL != (q = p->left) ) {
2988 continue;
2989 }
2990 break;
2991 } else /* minsplit > tempsize */ {
2992 if ( NULL != (q = p->right) ) {
2993 continue;
2994 }
2995 break;
2996 }
2997 } /* end inner for */
2998 break;
2999 }
3000 break; /* no new fit */
3001 }
3002 /* minsplit == tempsize ==> best non-exact fit */
3003 ptr = (word_t*)p;
3004 break;
3005 }
3006 } /* end outer for */
3007
3008 found_fit:
3009 ptr -= M_OVERHEAD;
3010 } /* if (!force_more) */
3011
3012 if (!ptr)
3013 {
3014 /* No match, allocate more memory */
3015
3016 word_t chunk_size, block_size;
3017 size_t extra = 0; /* extra memory allocated by esbrk() */
3018
3019 block_size = size*GRANULARITY;
3020
3021 /* If force_more is true (read: we have to allocate a SMALL_CHUNK)
3022 * or if the if the requested block would leave only a 'small'
3023 * block or no block in the usual CHUNK_SIZEd chunk, then allocate
3024 * exactly the block requested. Otherwise allocate a CHUNK_SIZEd
3025 * chunk, of which the unneeded part is entered into the freelist.
3026 */
3027
3028 if (force_more
3029 || block_size > CHUNK_SIZE - SMALL_BLOCK_MAX_BYTES - T_OVERHEAD*GRANULARITY )
3030 {
3031 chunk_size = block_size;
3032
3033 }
3034 else
3035 {
3036 chunk_size = CHUNK_SIZE;
3037 }
3038
3039 /* Some systems like Darwin don't like odd sbrk()/malloc()s, therefore
3040 * we round up to the next multiple - 64 seems to work fine. That of
3041 * course might give an overhang of less than SMALL_BLOCK_MAX_BYTES,
3042 * so we have to add that and its own 64-Byte-fudge factor then, too.
3043 */
3044 # define ALLOC_MULTIPLE 63 /* Ok, the (multiple-1) */
3045
3046 if ((chunk_size & ALLOC_MULTIPLE) != 0)
3047 {
3048 // this expression is constant, so the compiler will remove the if
3049 // (gcc actually removes it even without any optimization).
3050 if (SMALL_BLOCK_MAX_BYTES > ALLOC_MULTIPLE)
3051 chunk_size += SMALL_BLOCK_MAX_BYTES + 2 * ALLOC_MULTIPLE;
3052 else
3053 chunk_size += ALLOC_MULTIPLE;
3054
3055 chunk_size &= ~ALLOC_MULTIPLE;
3056 }
3057
3058 if (force_more)
3059 ulog3f("lmalloc(%d / %d): Forced allocate new chunk of %d bytes\n"
3060 , orig_size, block_size, chunk_size);
3061 else
3062 ulog3f("lmalloc(%d / %d): Allocate new chunk of %d bytes\n"
3063 , orig_size, block_size, chunk_size);
3064
3065 /* Get <chunk_size> more bytes from the system */
3066 {
3067 if (max_malloced > 0
3068 && (mp_int)(sbrk_stat.size + chunk_size) > max_malloced
3069 && ( (mp_int)(sbrk_stat.size + (heap_start ? 0 : GRANULARITY)) >= max_malloced
3070 || (chunk_size = max_malloced - sbrk_stat.size
3071 - (heap_start?0:GRANULARITY) )
3072 < block_size
3073 )
3074 )
3075 {
3076 static const char mess[] = "HARD_MALLOC_LIMIT reached.\n";
3077 writes(2, mess);
3078
3079 ptr = NULL;
3080 }
3081 else
3082 {
3083 ptr = (word_t *)esbrk(chunk_size, &extra);
3084 }
3085 }
3086
3087 if (ptr == NULL)
3088 {
3089 /* Out of memory - try to recover */
3090 ulog2f("lmalloc(%d / %d): Didn't get the memory from the system.\n"
3091 , orig_size, block_size);
3092
3093 if (force_more)
3094 {
3095 /* The system is out of memory, but maybe we have some left
3096 * in the freelist.
3097 */
3098 force_more = MY_FALSE;
3099 goto retry;
3100 }
3101
3102 /* Give up */
3103 return NULL;
3104 }
3105
3106 /* Enough of the scary words - we got our memory block */
3107
3108 chunk_size += extra;
3109 block_size = chunk_size / GRANULARITY;
3110
3111 /* Add the block to the free memory */
3112 ptr = add_large_free(ptr, block_size);
3113 } /* end of creating a new chunk */
3114
3115 /* ptr is now a pointer to a free block in the free list */
3116
3117 #ifdef USE_AVL_FREELIST
3118 /* If there is more than one free block for this size, take
3119 * the first block from the freelist to avoid copying around
3120 * the AVL node information.
3121 */
3122 {
3123 struct free_block *p = (struct free_block *)(ptr + M_OVERHEAD);
3124 if (p->next)
3125 ptr = ((word_t *)(p->next)) - M_OVERHEAD;
3126 }
3127 #endif
3128
3129 remove_from_free_list(ptr);
3130 real_size = ptr[M_LSIZE];
3131
3132 if (real_size - size)
3133 {
3134 /* split block pointed to by ptr into two blocks */
3135
3136 ptr[size] = 0; /* Init the header word */
3137 build_block(ptr+size, real_size-size);
3138 #ifdef DEBUG
3139 if (real_size - size <= SMALL_BLOCK_MAX)
3140 {
3141 dprintf2(2,"DEBUG: lmalloc(%d / %d): "
3142 , orig_size, size * GRANULARITY);
3143 dprintf2(2
3144 , "Split off block of %d bytes, small limit is %d bytes.\n"
3145 , (p_int)(real_size - size) * GRANULARITY
3146 , (p_int)SMALL_BLOCK_MAX * GRANULARITY);
3147 #ifdef DEBUG_MALLOC_ALLOCS
3148 if (gcollect_outfd != 2)
3149 {
3150 dprintf2(gcollect_outfd
3151 ,"DEBUG: lmalloc(%d / %d): "
3152 , orig_size, size * GRANULARITY);
3153 dprintf2(gcollect_outfd
3154 , "Split off block of %d bytes, small limit is %d bytes.\n"
3155 , (p_int)(real_size - size) * GRANULARITY
3156 , (p_int)SMALL_BLOCK_MAX * GRANULARITY);
3157 }
3158 #endif
3159 }
3160 #endif
3161
3162 # ifndef SBRK_OK
3163 /* When we allocate a new chunk, it might differ slightly in size from
3164 * the desired size.
3165 */
3166 if (real_size - size <= SMALL_BLOCK_MAX)
3167 {
3168 mark_block(ptr+size);
3169 *(ptr+size) &= ~M_GC_FREE; /* Hands off, GC! */
3170 count_up(&large_wasted_stat, (*(ptr+size) & M_MASK) * GRANULARITY);
3171 }
3172 else
3173 # endif
3174 {
3175 /* At this point, it shouldn't happen that the split-off
3176 * block is too small to be allocated as a small block.
3177 */
3178 add_to_free_list(ptr+size);
3179 }
3180 build_block(ptr, size);
3181 }
3182
3183 /* The block at ptr is all ours */
3184
3185 mark_block(ptr);
3186 count_up(&large_alloc_stat, size);
3187 #ifdef MALLOC_EXT_STATISTICS
3188 extstats[SMALL_BLOCK_NUM+1].num_xalloc++;
3189 extstats[SMALL_BLOCK_NUM+1].cur_alloc++;
3190 extstat_update_max(extstats+SMALL_BLOCK_NUM+1);
3191 #endif /* MALLOC_EXT_STATISTICS */
3192 #ifdef MALLOC_CHECK
3193 ptr[M_MAGIC] = LAMAGIC;
3194 #endif
3195 MADVISE(ptr+M_OVERHEAD, orig_size);
3196 return (char *) (ptr + M_OVERHEAD);
3197 } /* large_malloc() */
3198
3199 /*-------------------------------------------------------------------------*/
3200 static void
large_free(char * ptr)3201 large_free (char *ptr)
3202
3203 /* Free the large memory block <ptr>. If possible, coagulate it with
3204 * neighbouring free blocks into one.
3205 */
3206
3207 {
3208 word_t size, *p;
3209
3210 /* Get the real block pointer */
3211 p = (word_t *) ptr;
3212 p -= M_OVERHEAD;
3213 size = p[M_LSIZE];
3214 count_back(&large_alloc_stat, size);
3215 #ifdef MALLOC_EXT_STATISTICS
3216 extstats[SMALL_BLOCK_NUM+1].num_xfree++;
3217 extstats[SMALL_BLOCK_NUM+1].cur_alloc--;
3218 #endif /* MALLOC_EXT_STATISTICS */
3219
3220 #ifdef MALLOC_CHECK
3221 if (p[M_MAGIC] == LFMAGIC)
3222 {
3223 in_malloc = 0;
3224 fatal("large_free: block %lx size %lu, (user %lx) freed twice\n"
3225 , (unsigned long)p, (unsigned long)(size * GRANULARITY)
3226 , (unsigned long)ptr);
3227 }
3228 if (p[M_MAGIC] != LAMAGIC)
3229 {
3230 in_malloc = 0;
3231 fatal("large_free(%p): block %p magic match failed: size %lu, "
3232 "expected %lx, found %lx\n"
3233 , ptr, p
3234 , (unsigned long)(size * GRANULARITY)
3235 , (unsigned long)LAMAGIC
3236 , (unsigned long)p[M_MAGIC]
3237 );
3238 }
3239 #endif
3240
3241 (void)add_large_free(p, size);
3242 } /* large_free() */
3243
3244 /*-------------------------------------------------------------------------*/
3245 static char *
esbrk(word_t size,size_t * pExtra)3246 esbrk (word_t size, size_t * pExtra)
3247
3248 /* Allocate a block of <size> bytes from the system and return its pointer.
3249 * If esbrk() allocated a larger block, the difference to <size> is
3250 * returned in *<pExtra>.
3251 *
3252 #ifdef SBRK_OK
3253 * It is system dependent how sbrk() aligns data, so we simpy use brk()
3254 * to insure that we have enough.
3255 * At the end of the newly expanded heap we create a fake allocated
3256 * block of 0 bytes so that large_malloc() knows where to stop.
3257 #else
3258 * Use malloc() to allocate a new block of memory. If this block borders
3259 * to the previous one, both blocks are joined.
3260 * The allocated block (modulo joints) is tagged at both ends with fake
3261 * "allocated" blocks of which cover the unallocated areas - large_malloc()
3262 * will perceive this as a fragmented heap.
3263 #endif
3264 */
3265
3266 {
3267 mdb_log_sbrk(size);
3268
3269 *pExtra = 0;
3270
3271 #ifdef SBRK_OK
3272
3273 if (!heap_end)
3274 {
3275 /* First call: allocate the first fake block */
3276 heap_start = heap_end = (word_t *)sbrk(0);
3277 if (!esbrk(2*GRANULARITY, pExtra))
3278 {
3279 in_malloc = 0;
3280 fatal("Couldn't malloc anything\n");
3281 }
3282 *heap_start = 2;
3283 *(heap_start+1) = PREV_BLOCK | M_MASK;
3284 count_up(&large_wasted_stat, 2*GRANULARITY);
3285 assert_stack_gap();
3286 }
3287
3288 /* Get the new block */
3289 if ((int)brk((char *)heap_end + size) == -1)
3290 return NULL;
3291
3292 count_up(&sbrk_stat, size);
3293 heap_end = (word_t*)((char *)heap_end + size);
3294 heap_end[-1] = THIS_BLOCK | M_MASK;
3295 heap_end[-2] = M_MASK;
3296 return (char *)(heap_end - 1) - size; /* overlap old memory block */
3297
3298 #else /* not SBRK_OK */
3299
3300 char *block;
3301 size_t req_size = size; // the requested size of memory.
3302 word_t *p; /* start of the fake block */
3303 const int overhead = TL_OVERHEAD;
3304 size_t overlap = 0;
3305 /* How much extra memory esbrk() could recycle from joining
3306 * the new allocation with the old one.
3307 */
3308
3309
3310 size += overhead * GRANULARITY; /* for the extra fake "allocated" block */
3311
3312 // get the new memory block
3313 #ifdef HAVE_MMAP
3314 {
3315 static size_t pagesize = 0; // pagesize - 1 for this system.
3316 if (!pagesize)
3317 pagesize = getpagesize() - 1;
3318 // round to multiples of the real pagesize
3319 if ((size & pagesize) != 0)
3320 {
3321 size += pagesize;
3322 size &= ~pagesize;
3323 }
3324 // get new page(s)
3325 block = mmap(0, size, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
3326 if (block == MAP_FAILED)
3327 return NULL;
3328 }
3329 #else
3330 block = malloc(size);
3331 if (!block)
3332 return NULL;
3333 #endif
3334
3335 assert_stack_gap();
3336
3337 /* p points to the start of the fake allocated block used
3338 * as sentinel/bridge
3339 */
3340 p = (word_t *)(block + size) - overhead + 1;
3341
3342 #ifdef MALLOC_TRACE
3343 p[M_OVERHEAD+XM_FILE] = (word_t)"sentinel/bridge";
3344 p[M_OVERHEAD+XM_LINE] = 0;
3345 #endif
3346 #ifdef MALLOC_LPC_TRACE
3347 p[M_OVERHEAD+XM_OBJ] = 0;
3348 p[M_OVERHEAD+XM_PROG] = 0;
3349 p[M_OVERHEAD+XM_PC] = 0;
3350 #endif
3351
3352 if (!heap_end)
3353 {
3354 /* First call: create the inital fake block */
3355 heap_start = (word_t*)block;
3356 heap_end = (word_t*)(block + size);
3357 *((word_t *)block+1) = PREV_BLOCK;
3358 p[M_LSIZE] = overhead;
3359 p[M_SIZE] = THIS_BLOCK | M_MASK; /* no M_GC_FREE */
3360 overlap = 0;
3361 }
3362 else
3363 {
3364 /* Try to join with the existing heap */
3365 if (block < (char *)heap_start)
3366 {
3367 /* New block before the known heap */
3368
3369 *((word_t *)block+1) = PREV_BLOCK|M_MASK; /* Lower sentinel */
3370 if (block + size == (char *)heap_start)
3371 {
3372 /* We can join with the existing heap */
3373 p[overhead] &= ~PREV_BLOCK;
3374 overlap = overhead * GRANULARITY;
3375 count_back(&large_wasted_stat, overlap);
3376 }
3377 else
3378 {
3379 /* Separate from the heap */
3380 p[M_LSIZE] = (heap_start - p + 1);
3381 p[M_SIZE] = THIS_BLOCK | M_MASK; /* no M_GC_FREE */
3382 overlap = 0;
3383 }
3384
3385 heap_start = (word_t *)block;
3386 }
3387 else if (block >= (char *)heap_end)
3388 {
3389 /* New block after the known heap */
3390
3391 p[M_SIZE] = THIS_BLOCK | M_MASK; /* no M_GC_FREE */
3392 p[M_LSIZE] = overhead;
3393 if (block == (char *)heap_end)
3394 {
3395 /* We can join with the existing heap */
3396 heap_end = (word_t *)(block + size);
3397 block -= overhead * GRANULARITY;
3398 overlap = overhead * GRANULARITY;
3399 count_back(&large_wasted_stat, overlap);
3400 }
3401 else
3402 {
3403 /* Separate from the heap */
3404 p = (word_t *)heap_end - overhead + 1;
3405 p[M_SIZE] = (p[M_SIZE] & (PREV_BLOCK|THIS_BLOCK|M_GC_FREE)) | M_MASK;
3406 p[M_LSIZE] = (word_t *)block - p + 1;
3407 heap_end = (word_t *)(block + size);
3408 *((word_t *)block+1) = PREV_BLOCK;
3409 overlap = 0;
3410 }
3411 }
3412 else
3413 {
3414 /* We got a block within the known heap.
3415 * Try to find it in the fake blocks created earlier.
3416 * This is slow, but it shouldn't happen too often.
3417 */
3418
3419 word_t *prev, *next;
3420
3421 /* Go to the block right before the one we got */
3422 next = heap_start;
3423 do {
3424 prev = next;
3425 next = prev + *prev;
3426 } while (next < (word_t *)block);
3427 overlap = 0;
3428
3429 if ((word_t *)block == prev + overhead)
3430 {
3431 /* Our block directly follows the one we found */
3432 block -= overhead * GRANULARITY;
3433 overlap += overhead * GRANULARITY;
3434 count_back(&large_wasted_stat, overhead * GRANULARITY);
3435 }
3436 else
3437 {
3438 /* We have to create a new bridge block */
3439 prev++;
3440 prev[M_SIZE] = (prev[M_SIZE] & (PREV_BLOCK|THIS_BLOCK|M_GC_FREE)) | M_MASK;
3441 prev[M_LSIZE] = (word_t*)block - prev + 1;
3442 #ifdef MALLOC_TRACE
3443 prev[M_OVERHEAD+XM_FILE] = (word_t)"block";
3444 prev[M_OVERHEAD+XM_LINE] = 0;
3445 #endif
3446 #ifdef MALLOC_LPC_TRACE
3447 prev[M_OVERHEAD+XM_OBJ] = 0;
3448 prev[M_OVERHEAD+XM_PROG] = 0;
3449 prev[M_OVERHEAD+XM_PC] = 0;
3450 #endif
3451 *((word_t *)block+1) = PREV_BLOCK | M_MASK;
3452 }
3453
3454 if (next - p == overhead)
3455 {
3456 /* Our block directly preceedes the next one */
3457 *(next+1) &= ~PREV_BLOCK;
3458 overlap += overhead * GRANULARITY;
3459 count_back(&large_wasted_stat, overhead * GRANULARITY);
3460 }
3461 else
3462 {
3463 /* We have to create a new bridge block */
3464 p[M_SIZE] = THIS_BLOCK | M_MASK; /* no M_GC_FREE */
3465 p[M_LSIZE] = next - p + 1;
3466 }
3467 }
3468 }
3469
3470 count_up(&sbrk_stat, size);
3471 count_up(&large_wasted_stat, overhead * GRANULARITY);
3472
3473 // amount of additional memory that was allocated
3474 #ifdef HAVE_MMAP
3475 *pExtra = overlap + (size - overhead * GRANULARITY - req_size);
3476 #else
3477 *pExtra = overlap;
3478 #endif
3479 return block + GRANULARITY;
3480 #endif /* !SBRK_OK */
3481 } /* esbrk() */
3482
3483
3484 /*-------------------------------------------------------------------------*/
3485 static INLINE void *
mem_increment_size(void * vp,size_t size)3486 mem_increment_size (void *vp, size_t size)
3487
3488 /* Try to extent the allocation block for <vp> to hold <size> more bytes.
3489 * If this is not possible, return NULL, otherwise return a pointer
3490 * to the start of the block extension.
3491 */
3492
3493 {
3494 char *p = vp;
3495 word_t *start, *start2, *start3, old_size, next;
3496 const word_t wsize = (size + GRANULARITY - 1)/ GRANULARITY;
3497
3498 malloc_increment_size_calls++;
3499
3500 start = (word_t*)p - M_OVERHEAD;
3501
3502 old_size = start[M_SIZE] & M_MASK;
3503
3504 if (old_size <= SMALL_BLOCK_MAX)
3505 {
3506 /* Extend a small block */
3507
3508 word_t new_size = (old_size + wsize) * GRANULARITY;
3509 start2 = &start[old_size];
3510 next = *start2;
3511
3512 if (old_size + wsize > SMALL_BLOCK_MAX)
3513 return NULL; /* New block would be too large */
3514
3515 if (!(next & THIS_BLOCK))
3516 return NULL; /* no following free block */
3517
3518 /* Make sure the following free block is as large as possible */
3519 defragment_small_block(start2);
3520
3521 next = start2[M_SIZE] & M_MASK; /* Might have changed */
3522
3523 if (next == wsize)
3524 {
3525 /* Next block fits perfectly */
3526
3527 UNLINK_SMALL_FREE(start2);
3528 start2[next] &= ~PREV_BLOCK;
3529
3530 start[M_SIZE] += wsize;
3531 MAKE_SMALL_CHECK_UNCHECKED(start, new_size);
3532
3533 malloc_increment_size_success++;
3534 malloc_increment_size_total += (start2 - start) - M_OVERHEAD;
3535
3536 count_add(&small_alloc_stat, wsize * GRANULARITY);
3537
3538 #ifdef MALLOC_EXT_STATISTICS
3539 extstats[SIZE_INDEX(old_size * GRANULARITY)].cur_alloc--;
3540 extstats[SIZE_INDEX(new_size)].cur_alloc++;
3541 extstat_update_max(extstats+SIZE_INDEX(new_size));
3542 #endif /* MALLOC_EXT_STATISTICS */
3543
3544 return start2;
3545 }
3546
3547 if (next >= wsize + SMALL_BLOCK_SPLIT_MIN + T_OVERHEAD)
3548 {
3549 /* Next block is large enough to be split */
3550
3551 UNLINK_SMALL_FREE(start2);
3552
3553 start3 = start2 + wsize;
3554 start3[M_SIZE] = 0; /* Clear PREV_BLOCK */
3555 MAKE_SMALL_FREE(start3, next - wsize);
3556
3557 start[M_SIZE] += wsize;
3558 MAKE_SMALL_CHECK_UNCHECKED(start, new_size);
3559
3560 malloc_increment_size_success++;
3561 malloc_increment_size_total += (start2 - start) - M_OVERHEAD;
3562
3563 count_add(&small_alloc_stat, wsize * GRANULARITY);
3564
3565 #ifdef MALLOC_EXT_STATISTICS
3566 extstats[SIZE_INDEX(old_size * GRANULARITY)].cur_alloc--;
3567 extstats[SIZE_INDEX(new_size)].cur_alloc++;
3568 extstat_update_max(extstats+SIZE_INDEX(new_size));
3569 #endif /* MALLOC_EXT_STATISTICS */
3570
3571 return start2;
3572 }
3573
3574 return NULL; /* No success */
3575 }
3576
3577 /* Extend a large block */
3578
3579 old_size = start[M_LSIZE];
3580 start2 = &start[old_size];
3581
3582 if (start2[M_SIZE] & THIS_BLOCK)
3583 return NULL; /* no following free block */
3584
3585 next = start2[M_LSIZE];
3586
3587 if (next == wsize)
3588 {
3589 /* Next block fits perfectly */
3590 remove_from_free_list(start2);
3591 start2[next] |= PREV_BLOCK;
3592 start[M_LSIZE] += wsize;
3593 malloc_increment_size_success++;
3594 malloc_increment_size_total += (start2 - start) - M_OVERHEAD;
3595 count_add(&large_alloc_stat, wsize);
3596
3597 return start2+M_LSIZE;
3598 }
3599
3600 if (next > wsize + SMALL_BLOCK_MAX + 1)
3601 {
3602 /* Split the next block, it is large enough */
3603
3604 remove_from_free_list(start2);
3605 start2[next-2] -= wsize;
3606 start3 = start2 + wsize;
3607 start3[M_SIZE] = M_MASK | PREV_BLOCK;
3608 start3[M_LSIZE] = (next-wsize);
3609 add_to_free_list(start3);
3610 start[M_LSIZE] += wsize;
3611 malloc_increment_size_success++;
3612 malloc_increment_size_total += (start2 - start) - M_OVERHEAD;
3613 count_add(&large_alloc_stat, wsize);
3614 return start2+M_LSIZE;
3615 }
3616
3617 /* No success */
3618 return NULL;
3619 } /* mem_increment_size() */
3620
3621
3622 /*=========================================================================*/
3623
3624 /* GARBAGE COLLECTOR */
3625
3626 /*-------------------------------------------------------------------------*/
3627 static INLINE void
mem_clear_ref(POINTER p)3628 mem_clear_ref (POINTER p)
3629
3630 /* GC Support: Clear the 'referenced' flag for block <p>.
3631 */
3632
3633 {
3634 ((word_t *)(p))[-M_OVERHEAD] &= ~M_REF;
3635 } /* mem_clear_ref() */
3636
3637 /*-------------------------------------------------------------------------*/
3638 static INLINE void
mem_mark_ref(POINTER p)3639 mem_mark_ref (POINTER p)
3640
3641 /* GC Support: Set the 'referenced' flag for block <p>.
3642 */
3643
3644 {
3645 ((word_t *)(p))[-M_OVERHEAD] |= M_REF;
3646 } /* mem_mark_ref() */
3647
3648 /*-------------------------------------------------------------------------*/
3649 static INLINE Bool
mem_test_ref(POINTER p)3650 mem_test_ref (POINTER p)
3651
3652 /* GC Support: Check the memory block marker for <p>, return TRUE if _not_
3653 * set.
3654 */
3655
3656 {
3657 return !( ((word_t *)(p))[-M_OVERHEAD] & M_REF );
3658 } /* mem_test_ref() */
3659
3660
3661 /*-------------------------------------------------------------------------*/
3662 Bool
mem_is_freed(void * p,p_uint minsize)3663 mem_is_freed (void *p, p_uint minsize)
3664
3665 /* Check if block for the allocation <p> is a free block of at least
3666 * <minsize>. Blocks outside the heap always qualify.
3667 * The function might return false for joined blocks.
3668 */
3669
3670 {
3671 word_t *block;
3672 word_t i;
3673
3674 block = (word_t *) p;
3675 block -= M_OVERHEAD;
3676
3677 if (block < heap_start || block + M_OVERHEAD >= heap_end)
3678 return MY_TRUE;
3679
3680 i = block[M_SIZE] & M_MASK;
3681 if (i >= SMALL_BLOCK_MAX)
3682 i = block[M_LSIZE];
3683
3684 if (i < M_OVERHEAD + ((minsize + GRANULARITY - 1) / GRANULARITY)
3685 || block + i >= heap_end)
3686 return MY_TRUE;
3687
3688 if (i >= SMALL_BLOCK_MAX)
3689 {
3690 word_t* block2;
3691
3692 block2 = block + i;
3693 return !(block[M_SIZE] & THIS_BLOCK)
3694 #ifdef MALLOC_CHECK
3695 || block[M_MAGIC] != LAMAGIC
3696 #endif /* MALLOC_CHECK */
3697 || !(*block2 & PREV_BLOCK);
3698 }
3699
3700 return (block[M_SIZE] & THIS_BLOCK) != 0;
3701 } /* mem_is_freed() */
3702
3703 /*-------------------------------------------------------------------------*/
3704 void
mem_clear_ref_flags(void)3705 mem_clear_ref_flags (void)
3706
3707 /* Walk through all allocated blocks and clear the M_REF flag in preparation
3708 * for a GC.
3709 */
3710
3711 {
3712 word_t *p, *q, *last;
3713 int i;
3714
3715 /* Clear the large blocks */
3716 last = heap_end - TL_OVERHEAD;
3717 for (p = heap_start; p < last; )
3718 {
3719 p[1] &= ~M_REF;
3720 if (p + *p > heap_end)
3721 {
3722 in_malloc = 0;
3723 fatal("pointer larger than brk: %p + %lx = %p > %p\n"
3724 , p, *p, p + *p , last);
3725 }
3726 p += *p;
3727 }
3728
3729 /* Now mark the memory used for the small chunks as ref'd,
3730 * then clear the small blocks.
3731 */
3732 for (p = last_small_chunk; p; p = *(word_t**)p)
3733 {
3734 word_t *end;
3735
3736 mem_mark_ref(p);
3737 end = p - ML_OVERHEAD + p[-ML_OVERHEAD];
3738 #ifdef DEBUG
3739 dprintf2(gcollect_outfd, "clearing M_REF in chunk %x, end %x\n",
3740 (word_t)(p - ML_OVERHEAD), (word_t)end
3741 );
3742 #endif
3743 for (q = p+1; q < end; )
3744 {
3745 word_t size = *q;
3746
3747 *q &= ~M_REF;
3748 q += size & M_MASK;
3749 }
3750
3751 if (q > end)
3752 {
3753 /* pass some variables to fatal() so that the optimizer
3754 * won't throw away the values, making them unreadable
3755 * in the core.
3756 */
3757 in_malloc = 0;
3758 fatal("Small block error, start: %lx, %lx vs. %lx\n",
3759 (long)(p+1), (long)q, (long)end);
3760 }
3761 }
3762
3763 /* We set M_REF for small free blocks that early for two reasons:
3764 * - if it's referenced anywhere else, we get a fatal.
3765 * - if the block gets malloced by the swapper in pass 5, it needs
3766 * M_REF to be already set.
3767 */
3768 for (i=0; i < SMALL_BLOCK_NUM + 1; i++)
3769 {
3770 for (p = sfltable[i]; p; p = BLOCK_NEXT(p) ) {
3771 *p |= M_REF;
3772 }
3773 }
3774 } /* mem_clear_ref_flags() */
3775
3776 /*-------------------------------------------------------------------------*/
3777 void
mem_free_unrefed_memory(void)3778 mem_free_unrefed_memory (void)
3779
3780 /* The GC marked all used memory as REF'd, now recover all blocks which
3781 * are allocated, but haven't been marked.
3782 */
3783
3784 {
3785 word_t *p, *q, *last;
3786 mp_int success = 0;
3787
3788 /* Scan the heap for lost large blocks */
3789 last = heap_end - TL_OVERHEAD;
3790 for (p = heap_start; p < last; )
3791 {
3792 word_t size, flags;
3793
3794 size = *p;
3795 flags = p[1];
3796 if ( (flags & (M_REF|THIS_BLOCK|M_GC_FREE)) == (THIS_BLOCK|M_GC_FREE) )
3797 {
3798 /* Large block marked as in use (THIS_BLOCK), but is not
3799 * referenced (no M_REF) - recover it.
3800 */
3801 word_t size2, flags2;
3802
3803 success++;
3804 count_back(&xalloc_stat, mem_block_size(p+ML_OVERHEAD));
3805 #if defined(MALLOC_TRACE) || defined(MALLOC_LPC_TRACE)
3806 dprintf1(gcollect_outfd, "freeing large block 0x%x", (p_uint)p);
3807 #endif
3808 #ifdef MALLOC_TRACE
3809 dprintf3(gcollect_outfd, " %s %d size 0x%x\n",
3810 p[XM_FILE+ML_OVERHEAD], p[XM_LINE+ML_OVERHEAD], size & M_MASK
3811 );
3812 #endif
3813 #ifdef MALLOC_LPC_TRACE
3814 write_lpc_trace(gcollect_outfd, p + ML_OVERHEAD, MY_FALSE);
3815 #endif
3816 print_block(gcollect_outfd, p + ML_OVERHEAD);
3817 size2 = p[size];
3818 flags2 = p[size + 1];
3819 large_free((char *)(p+ML_OVERHEAD));
3820 if ( !(flags2 & THIS_BLOCK) )
3821 size += size2;
3822 }
3823 p += size;
3824 }
3825 if (success)
3826 {
3827 dprintf1(gcollect_outfd, "%d large blocks freed\n", success);
3828 }
3829
3830 /* Scan the small chunks for lost small blocks.
3831 * Remember that small blocks in the free-lists are marked as ref'd.
3832 */
3833 success = 0;
3834 for (p = last_small_chunk; p; p = *(word_t**)p)
3835 {
3836 word_t *end;
3837
3838 end = p - ML_OVERHEAD + p[-ML_OVERHEAD];
3839 #ifdef DEBUG
3840 dprintf2(gcollect_outfd, "scanning chunk %x, end %x for unref'd blocks\n",
3841 (word_t)(p - M_OVERHEAD), (word_t)end
3842 );
3843 #endif
3844 for (q = p+1; q < end; )
3845 {
3846 word_t size = *q;
3847
3848 if ((*q & (M_REF|M_GC_FREE)) == M_GC_FREE)
3849 {
3850 /* Unref'd small blocks are definitely lost */
3851 success++;
3852 count_back(&xalloc_stat, mem_block_size(q+M_OVERHEAD));
3853 dprintf2(gcollect_outfd, "freeing small block 0x%x (user 0x%x)"
3854 , (p_uint)q, (p_uint)(q+M_OVERHEAD));
3855 #ifdef MALLOC_TRACE
3856 dprintf2(gcollect_outfd, " %s %d"
3857 , q[XM_FILE+M_OVERHEAD], q[XM_LINE+M_OVERHEAD]);
3858 #endif
3859 writes(gcollect_outfd, "\n");
3860 #ifdef MALLOC_LPC_TRACE
3861 write_lpc_trace(gcollect_outfd, q + M_OVERHEAD, MY_FALSE);
3862 #endif
3863 print_block(gcollect_outfd, q + M_OVERHEAD);
3864
3865 /* Recover the block */
3866 *q |= M_REF;
3867 sfree(q+M_OVERHEAD);
3868 }
3869 q += size & M_MASK;
3870 }
3871 }
3872 if (success) {
3873 dprintf1(gcollect_outfd, "%d small blocks freed\n", success);
3874 }
3875 } /* mem_free_unrefed_memory() */
3876
3877 /*-------------------------------------------------------------------------*/
3878 Bool
mem_dump_memory(int fd)3879 mem_dump_memory (int fd)
3880
3881 /* Print the location, size, and (if available) the TRACE information
3882 * of all memory blocks to file <fd>, and return TRUE.
3883 * If the allocator doesn't support this operation, print nothing
3884 * and return FALSE.
3885 *
3886 * If <fd> is -1, just return TRUE or FALSE (this is used to check if
3887 * the allocator supports memory dumps).
3888 */
3889
3890 {
3891 word_t *p, *q, *last;
3892
3893 if (fd < 0)
3894 return MY_TRUE;
3895
3896 writes(fd, "\n--- Large Blocks\n");
3897
3898 /* Dump the heap blocks */
3899 last = heap_end - TL_OVERHEAD;
3900 for (p = heap_start; p < last; )
3901 {
3902 word_t size, flags;
3903
3904 size = *p;
3905 flags = p[1];
3906 if ( flags & THIS_BLOCK )
3907 {
3908 Bool isSmallChunk = MY_FALSE;
3909
3910 dprintf4(fd, "%x .. %x %s size %x "
3911 , (p_uint)p, (p_uint)(p + size) - 1
3912 , (p_uint)((flags & M_GC_FREE) ? " " : "P")
3913 , (p_uint)size * GRANULARITY
3914 );
3915 for (q = last_small_chunk; q && !isSmallChunk; q = *(word_t**)q)
3916 {
3917 isSmallChunk = (q - ML_OVERHEAD == p);
3918 }
3919
3920 if (isSmallChunk)
3921 writes(fd, ": small chunk\n");
3922 else
3923 {
3924 #ifdef MALLOC_TRACE
3925 if (p[XM_FILE+ML_OVERHEAD])
3926 dprintf2(fd, ": %s %d "
3927 , p[XM_FILE+ML_OVERHEAD], p[XM_LINE+ML_OVERHEAD]
3928 );
3929 else
3930 writes(fd, ": - -");
3931 #endif
3932 #ifdef MALLOC_LPC_TRACE
3933 if (p[ML_OVERHEAD + XM_OBJ])
3934 {
3935 writes(fd, ": ");
3936 write_lpc_trace(fd, p + ML_OVERHEAD, MY_TRUE);
3937 }
3938 else
3939 #endif
3940 writes(fd, "\n");
3941 }
3942 }
3943 p += size;
3944 }
3945
3946 /* Dump the small chunks and their small blocks.
3947 */
3948 for (p = last_small_chunk; p; p = *(word_t**)p)
3949 {
3950 word_t *end;
3951
3952 end = p - ML_OVERHEAD + (p[-ML_OVERHEAD]);
3953
3954 {
3955 word_t size, flags;
3956
3957 q = p - ML_OVERHEAD;
3958 size = *q;
3959 flags = q[1];
3960
3961 dprintf4(fd, "\n--- Small Chunk: %x .. %x %s size %x\n"
3962 , (p_uint)q, (p_uint)(q + size) - 1
3963 , (p_uint)((flags & M_GC_FREE) ? " " : "P")
3964 , (p_uint)size * GRANULARITY
3965 );
3966 /* No trace information for small chunks */
3967 }
3968
3969 for (q = p+1; q < end; )
3970 {
3971 word_t size = *q;
3972
3973 if (!(*q & THIS_BLOCK))
3974 {
3975 dprintf4(fd, "%x .. %x %s size %x "
3976 , (p_uint)q, (p_uint)(q + (size&M_MASK)) - 1
3977 , (p_uint)((size & M_GC_FREE) ? " " : "P")
3978 , (p_uint)(size & M_MASK) * GRANULARITY
3979 );
3980
3981 /* The sentinel blocks in a small chunk consist of just
3982 * the size byte - don't try to dump those.
3983 */
3984 if ((size & M_MASK) > M_OVERHEAD)
3985 {
3986 #ifdef MALLOC_TRACE
3987 if (q[XM_FILE+M_OVERHEAD])
3988 dprintf2(fd, ": %s %d "
3989 , q[XM_FILE+M_OVERHEAD], q[XM_LINE+M_OVERHEAD]
3990 );
3991 else
3992 writes(fd, ": - - ");
3993 #endif
3994 #ifdef MALLOC_LPC_TRACE
3995 if (q[M_OVERHEAD + XM_OBJ])
3996 {
3997 writes(fd, ": ");
3998 write_lpc_trace(fd, q + M_OVERHEAD, MY_TRUE);
3999 }
4000 else
4001 #endif
4002 writes(fd, "\n");
4003 }
4004 else
4005 writes(fd, "\n");
4006 }
4007 q += size & M_MASK;
4008 }
4009 }
4010
4011 return MY_TRUE;
4012 } /* mem_dump_memory() */
4013
4014 /*-------------------------------------------------------------------------*/
4015 void
mem_consolidate(Bool force)4016 mem_consolidate (Bool force)
4017
4018 /* Consolidate the memory.
4019 *
4020 * If <force> is TRUE, the small free blocks are defragmented first.
4021 * Then, the function walks the list of small chunks and free all which are
4022 * totally unused.
4023 */
4024
4025 {
4026 word_t *prev, *this;
4027
4028 if (force)
4029 defragment_small_lists(0);
4030
4031 for (prev = NULL, this = last_small_chunk ; this != NULL ; )
4032 {
4033 word_t chunk_size = this[-ML_OVERHEAD];
4034
4035 /* If the chunk holds only one free block, it can be freed
4036 * altogether.
4037 */
4038 if ((this[1+M_SIZE] & THIS_BLOCK)
4039 && (this[1+M_SIZE] & M_MASK) == chunk_size - M_OVERHEAD - 2
4040 )
4041 {
4042 word_t * next = *(word_t **) this;
4043
4044 if (!prev)
4045 last_small_chunk = next;
4046 else
4047 *(word_t **)prev = next;
4048
4049 UNLINK_SMALL_FREE(this+1);
4050 large_free((char *)this);
4051
4052 count_back(&small_chunk_stat, chunk_size * GRANULARITY);
4053 count_back(&small_chunk_wasted, GRANULARITY*(M_OVERHEAD+2));
4054
4055 this = next;
4056 }
4057 else
4058 {
4059 prev = this;
4060 this = *(word_t**)this;
4061 }
4062 } /* for (all chunks) */
4063 } /* mem_consolidate() */
4064
4065
4066 /*-------------------------------------------------------------------------*/
4067 #if !defined(HAVE_GETPAGESIZE)
4068 static INLINE size_t
getpagesize()4069 getpagesize()
4070 /* get the pagesize for this system */
4071 {
4072 #ifdef(HAVE_SYSCONF)
4073 return sysconf(_SC_PAGESIZE);
4074 #else
4075 #error Unable to find out the system pagesize. Please report this issue.
4076 #endif
4077 }
4078 #endif /* HAVE_GETPAGESIZE */
4079 /***************************************************************************/
4080