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