Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/runtime/memory/malloc.c
ViewVC logotype

Annotation of /sml/trunk/src/runtime/memory/malloc.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 250 - (view) (download) (as text)

1 : monnier 249 /*
2 :     A version of malloc/free/realloc written by Doug Lea and released to the
3 :     public domain.
4 :    
5 :     VERSION 2.5
6 :    
7 :     * History:
8 :     Based loosely on libg++-1.2X malloc. (It retains some of the overall
9 :     structure of old version, but most details differ.)
10 :     trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)
11 :     fixups Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)
12 :     * removed potential for odd address access in prev_chunk
13 :     * removed dependency on getpagesize.h
14 :     * misc cosmetics and a bit more internal documentation
15 :     * anticosmetics: mangled names in macros to evade debugger strangeness
16 :     * tested on sparc, hp-700, dec-mips, rs6000
17 :     with gcc & native cc (hp, dec only) allowing
18 :     Detlefs & Zorn comparison study (to appear, SIGPLAN Notices.)
19 :    
20 :     * Overview
21 :    
22 :     This malloc, like any other, is a compromised design.
23 :    
24 :     Chunks of memory are maintained using a `boundary tag' method as
25 :     described in e.g., Knuth or Standish. The size of the chunk is
26 :     stored both in the front of the chunk and at the end. This makes
27 :     consolidating fragmented chunks into bigger chunks very fast. The
28 :     size field also hold a bit representing whether a chunk is free or
29 :     in use.
30 :    
31 :     Malloced chunks have space overhead of 8 bytes: The preceding and
32 :     trailing size fields. When a chunk is freed, 8 additional bytes are
33 :     needed for free list pointers. Thus, the minimum allocatable size is
34 :     16 bytes. 8 byte alignment is currently hardwired into the design.
35 :     This seems to suffice for all current machines and C compilers.
36 :     Calling memalign will return a chunk that is both 8-byte aligned
37 :     and meets the requested (power of two) alignment.
38 :    
39 :     It is assumed that 32 bits suffice to represent chunk sizes. The
40 :     maximum size chunk is 2^31 - 8 bytes. malloc(0) returns a pointer
41 :     to something of the minimum allocatable size. Requests for negative
42 :     sizes (when size_t is signed) or with the highest bit set (when
43 :     unsigned) will also return a minimum-sized chunk.
44 :    
45 :     Available chunks are kept in doubly linked lists. The lists are
46 :     maintained in an array of bins using a power-of-two method, except
47 :     that instead of 32 bins (one for each 1 << i), there are 128: each
48 :     power of two is split in quarters. Chunk sizes up to 128 are
49 :     treated specially; they are categorized on 8-byte boundaries. This
50 :     both better distributes them and allows for special faster
51 :     processing.
52 :    
53 :     The use of very fine bin sizes closely approximates the use of one
54 :     bin per actually used size, without necessitating the overhead of
55 :     locating such bins. It is especially desirable in common
56 :     applications where large numbers of identically-sized blocks are
57 :     malloced/freed in some dynamic manner, and then later are all freed.
58 :     The finer bin sizes make finding blocks fast, with little wasted
59 :     overallocation. The consolidation methods ensure that once the
60 :     collection of blocks is no longer useful, fragments are gathered
61 :     into bigger chunks awaiting new roles.
62 :    
63 :     The bins av[i] serve as heads of the lists. Bins contain a dummy
64 :     header for the chunk lists. Each bin has two lists. The `dirty' list
65 :     holds chunks that have been returned (freed) and not yet either
66 :     re-malloc'ed or consolidated. (A third free-standing list contains
67 :     returned chunks that have not yet been processed at all.) The `clean'
68 :     list holds split-off fragments and consolidated space. All
69 :     procedures maintain the invariant that no clean chunk physically
70 :     borders another clean chunk. Thus, clean chunks never need to be
71 :     scanned during consolidation.
72 :    
73 :     * Algorithms
74 :    
75 :     Malloc:
76 :    
77 :     This is a very heavily disguised first-fit algorithm.
78 :     Most of the heuristics are designed to maximize the likelihood
79 :     that a usable chunk will most often be found very quickly,
80 :     while still minimizing fragmentation and overhead.
81 :    
82 :     The allocation strategy has several phases:
83 :    
84 :     0. Convert the request size into a usable form. This currently
85 :     means to add 8 bytes overhead plus possibly more to obtain
86 :     8-byte alignment. Call this size `nb'.
87 :    
88 :     1. Check if the last returned (free()'d) or preallocated chunk
89 :     is of the exact size nb. If so, use it. `Exact' means no
90 :     more than MINSIZE (currently 16) bytes larger than nb. This
91 :     cannot be reduced, since a chunk with size < MINSIZE cannot
92 :     be created to hold the remainder.
93 :    
94 :     This check need not fire very often to be effective. It
95 :     reduces overhead for sequences of requests for the same
96 :     preallocated size to a dead minimum.
97 :    
98 :     2. Look for a dirty chunk of exact size in the bin associated
99 :     with nb. `Dirty' chunks are those that have never been
100 :     consolidated. Besides the fact that they, but not clean
101 :     chunks require scanning for consolidation, these chunks are
102 :     of sizes likely to be useful because they have been
103 :     previously requested and then freed by the user program.
104 :    
105 :     Dirty chunks of bad sizes (even if too big) are never used
106 :     without consolidation. Among other things, this maintains the
107 :     invariant that split chunks (see below) are ALWAYS clean.
108 :    
109 :     2a If there are dirty chunks, but none of the right size,
110 :     consolidate them all, as well as any returned chunks
111 :     (i.e., the ones from step 3). This is all a heuristic for
112 :     detecting and dealing with excess fragmentation and
113 :     random traversals through memory that degrade
114 :     performance especially when the user program is running
115 :     out of physical memory.
116 :    
117 :     3. Pull other requests off the returned chunk list, using one if
118 :     it is of exact size, else distributing into the appropriate
119 :     bins.
120 :    
121 :     4. Try to use the last chunk remaindered during a previous
122 :     malloc. (The ptr to this chunk is kept in var last_remainder,
123 :     to make it easy to find and to avoid useless re-binning
124 :     during repeated splits. The code surrounding it is fairly
125 :     delicate. This chunk must be pulled out and placed in a bin
126 :     prior to any consolidation, to avoid having other pointers
127 :     point into the middle of it, or try to unlink it.) If
128 :     it is usable, proceed to step 9.
129 :    
130 :     5. Scan through clean chunks in the bin, choosing any of size >=
131 :     nb. Split later (step 9) if necessary below. (Unlike in step
132 :     2, it is good to split here, because it creates a chunk of a
133 :     known-to-be-useful size out of a fragment that happened to be
134 :     close in size.)
135 :    
136 :     6. Scan through the clean lists of all larger bins, selecting
137 :     any chunk at all. (It will surely be big enough since it is
138 :     in a bigger bin.) The scan goes upward from small bins to
139 :     large. It would be faster downward, but could lead to excess
140 :     fragmentation. If successful, proceed to step 9.
141 :    
142 :     7. Consolidate chunks in other dirty bins until a large enough
143 :     chunk is created. Break out to step 9 when one is found.
144 :    
145 :     Bins are selected for consolidation in a circular fashion
146 :     spanning across malloc calls. This very crudely approximates
147 :     LRU scanning -- it is an effective enough approximation for
148 :     these purposes.
149 :    
150 :     8. Get space from the system using sbrk.
151 :    
152 :     Memory is gathered from the system (via sbrk) in a way that
153 :     allows chunks obtained across different sbrk calls to be
154 :     consolidated, but does not require contiguous memory. Thus,
155 :     it should be safe to intersperse mallocs with other sbrk
156 :     calls.
157 :    
158 :     9. If the selected chunk is too big, then:
159 :    
160 :     9a If this is the second split request for nb bytes in a row,
161 :     use this chunk to preallocate up to MAX_PREALLOCS
162 :     additional chunks of size nb and place them on the
163 :     returned chunk list. (Placing them here rather than in
164 :     bins speeds up the most common case where the user
165 :     program requests an uninterrupted series of identically
166 :     sized chunks. If this is not true, the chunks will be
167 :     binned in step 3 next time.)
168 :    
169 :     9b Split off the remainder and place in last_remainder.
170 :     Because of all the above, the remainder is always a
171 :     `clean' chunk.
172 :    
173 :     10. Return the chunk.
174 :    
175 :    
176 :     Free:
177 :     Deallocation (free) consists only of placing the chunk on a list
178 :     of returned chunks. free(0) has no effect. Because freed chunks
179 :     may be overwritten with link fields, this malloc will often die
180 :     when freed memory is overwritten by user programs. This can be
181 :     very effective (albeit in an annoying way) in helping users track
182 :     down dangling pointers.
183 :    
184 :     Realloc:
185 :     Reallocation proceeds in the usual way. If a chunk can be extended,
186 :     it is, else a malloc-copy-free sequence is taken.
187 :    
188 :     Memalign, valloc:
189 :     memalign arequests more than enough space from malloc, finds a spot
190 :     within that chunk that meets the alignment request, and then
191 :     possibly frees the leading and trailing space. Overreliance on
192 :     memalign is a sure way to fragment space.
193 :    
194 :     * Other implementation notes
195 :    
196 :     This malloc is NOT designed to work in multiprocessing applications.
197 :     No semaphores or other concurrency control are provided to ensure
198 :     that multiple malloc or free calls don't run at the same time, which
199 :     could be disasterous. A single semaphore could be used across malloc,
200 :     realloc, and free. It would be hard to obtain finer granularity.
201 :    
202 :     The implementation is in straight, hand-tuned ANSI C. Among other
203 :     consequences, it uses a lot of macros. These would be nicer as
204 :     inlinable procedures, but using macros allows use with non-inlining
205 :     compilers, and also makes it a bit easier to control when they
206 :     should be expanded out by selectively embedding them in other macros
207 :     and procedures. (According to profile information, it is almost, but
208 :     not quite always best to expand.)
209 :    
210 :     */
211 :    
212 :    
213 :    
214 :     /* TUNABLE PARAMETERS */
215 :    
216 :     /*
217 :     SBRK_UNIT is a good power of two to call sbrk with It should
218 :     normally be system page size or a multiple thereof. If sbrk is very
219 :     slow on a system, it pays to increase this. Otherwise, it should
220 :     not matter too much.
221 :     */
222 :    
223 :     #define SBRK_UNIT 8192
224 :    
225 :     /*
226 :     MAX_PREALLOCS is the maximum number of chunks to preallocate. The
227 :     actual number to prealloc depends on the available space in a
228 :     selected victim, so typical numbers will be less than the maximum.
229 :     Because of this, the exact value seems not to matter too much, at
230 :     least within values from around 1 to 100. Since preallocation is
231 :     heuristic, making it too huge doesn't help though. It may blindly
232 :     create a lot of chunks when it turns out not to need any more, and
233 :     then consolidate them all back again immediatetly. While this is
234 :     pretty fast, it is better to avoid it.
235 :     */
236 :    
237 :     #define MAX_PREALLOCS 5
238 :    
239 :    
240 :    
241 :    
242 :     /* preliminaries */
243 :    
244 :     #include <stddef.h> /* for size_t */
245 :     #include <stdio.h> /* needed for malloc_stats */
246 :    
247 :     #ifdef __cplusplus
248 :     extern "C" {
249 :     #endif
250 :    
251 :     extern void* sbrk(size_t);
252 :    
253 :     /* mechanics for getpagesize; adapted from bsd/gnu getpagesize.h */
254 :    
255 :     #if defined(BSD) || defined(DGUX) || defined(sun) || defined(HAVE_GETPAGESIZE)
256 :     extern size_t getpagesize();
257 :     # define malloc_getpagesize getpagesize()
258 :     #else
259 :     # include <sys/param.h>
260 :     # ifdef EXEC_PAGESIZE
261 :     # define malloc_getpagesize EXEC_PAGESIZE
262 :     # else
263 :     # ifdef NBPG
264 :     # ifndef CLSIZE
265 :     # define malloc_getpagesize NBPG
266 :     # else
267 :     # define malloc_getpagesize (NBPG * CLSIZE)
268 :     # endif
269 :     # else
270 :     # ifdef NBPC
271 :     # define malloc_getpagesize NBPC
272 :     # else
273 :     # define malloc_getpagesize SBRK_UNIT /* just guess */
274 :     # endif
275 :     # endif
276 :     # endif
277 :     #endif
278 :    
279 :     #ifdef __cplusplus
280 :     }; /* end of extern "C" */
281 :     #endif
282 :    
283 :    
284 :    
285 :     /* CHUNKS */
286 :    
287 :    
288 :     struct malloc_chunk
289 :     {
290 :     size_t size; /* Size in bytes, including overhead. */
291 :     /* Or'ed with INUSE if in use. */
292 :    
293 :     struct malloc_chunk* fd; /* double links -- used only if free. */
294 :     struct malloc_chunk* bk;
295 :    
296 :     };
297 :    
298 :     typedef struct malloc_chunk* mchunkptr;
299 :    
300 :     /* sizes, alignments */
301 :    
302 :     #define SIZE_SZ (sizeof(size_t))
303 :     #define MALLOC_MIN_OVERHEAD (SIZE_SZ + SIZE_SZ)
304 :     #define MALLOC_ALIGN_MASK (MALLOC_MIN_OVERHEAD - 1)
305 :     #define MINSIZE (sizeof(struct malloc_chunk) + SIZE_SZ)
306 :    
307 :    
308 :     /* pad request bytes into a usable size */
309 :    
310 :     #define request2size(req) \
311 :     (((long)(req) <= 0) ? MINSIZE : \
312 :     (((req) + MALLOC_MIN_OVERHEAD + MALLOC_ALIGN_MASK) \
313 :     & ~(MALLOC_ALIGN_MASK)))
314 :    
315 :    
316 :     /* Check if m has acceptable alignment */
317 :    
318 :     #define aligned_OK(m) (((size_t)((m)) & (MALLOC_ALIGN_MASK)) == 0)
319 :    
320 :    
321 :     /* Check if a chunk is immediately usable */
322 :    
323 :     #define exact_fit(ptr, req) ((unsigned)((ptr)->size - (req)) < MINSIZE)
324 :    
325 :     /* maintaining INUSE via size field */
326 :    
327 :     #define INUSE 0x1 /* size field is or'd with INUSE when in use */
328 :     /* INUSE must be exactly 1, so can coexist with size */
329 :    
330 :     #define inuse(p) ((p)->size & INUSE)
331 :     #define set_inuse(p) ((p)->size |= INUSE)
332 :     #define clear_inuse(p) ((p)->size &= ~INUSE)
333 :    
334 :    
335 :    
336 :     /* Physical chunk operations */
337 :    
338 :     /* Ptr to next physical malloc_chunk. */
339 :    
340 :     #define next_chunk(p)\
341 :     ((mchunkptr)( ((char*)(p)) + ((p)->size & ~INUSE) ))
342 :    
343 :     /* Ptr to previous physical malloc_chunk */
344 :    
345 :     #define prev_chunk(p)\
346 :     ((mchunkptr)( ((char*)(p)) - ( *((size_t*)((char*)(p) - SIZE_SZ)) & ~INUSE)))
347 :    
348 :     /* place size at front and back of chunk */
349 :    
350 :     #define set_size(P, Sz) \
351 :     { \
352 :     size_t Sss = (Sz); \
353 :     (P)->size = *((size_t*)((char*)(P) + Sss - SIZE_SZ)) = Sss; \
354 :     } \
355 :    
356 :    
357 :     /* conversion from malloc headers to user pointers, and back */
358 :    
359 :     #define chunk2mem(p) ((void*)((char*)(p) + SIZE_SZ))
360 :     #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - SIZE_SZ))
361 :    
362 :    
363 :    
364 :    
365 :     /* BINS */
366 :    
367 :     struct malloc_bin
368 :     {
369 :     struct malloc_chunk dhd; /* dirty list header */
370 :     struct malloc_chunk chd; /* clean list header */
371 :     };
372 :    
373 :     typedef struct malloc_bin* mbinptr;
374 :    
375 :    
376 :     /* field-extraction macros */
377 :    
378 :     #define clean_head(b) (&((b)->chd))
379 :     #define first_clean(b) ((b)->chd.fd)
380 :     #define last_clean(b) ((b)->chd.bk)
381 :    
382 :     #define dirty_head(b) (&((b)->dhd))
383 :     #define first_dirty(b) ((b)->dhd.fd)
384 :     #define last_dirty(b) ((b)->dhd.bk)
385 :    
386 :    
387 :    
388 :    
389 :     /* The bins, initialized to have null double linked lists */
390 :    
391 :     #define NBINS 128 /* for 32 bit addresses */
392 :     #define LASTBIN (&(av[NBINS-1]))
393 :     #define FIRSTBIN (&(av[2])) /* 1st 2 bins unused but simplify indexing */
394 :    
395 :     /* Bins < MAX_SMALLBIN_OFFSET are special-cased since they are 8 bytes apart */
396 :    
397 :     #define MAX_SMALLBIN_OFFSET 18
398 :     #define MAX_SMALLBIN_SIZE 144 /* Max size for which small bin rules apply */
399 :    
400 :     /* Helper macro to initialize bins */
401 :     #define IAV(i)\
402 :     {{ 0, &(av[i].dhd), &(av[i].dhd) }, { 0, &(av[i].chd), &(av[i].chd) }}
403 :    
404 :     static struct malloc_bin av[NBINS] =
405 :     {
406 :     IAV(0), IAV(1), IAV(2), IAV(3), IAV(4),
407 :     IAV(5), IAV(6), IAV(7), IAV(8), IAV(9),
408 :     IAV(10), IAV(11), IAV(12), IAV(13), IAV(14),
409 :     IAV(15), IAV(16), IAV(17), IAV(18), IAV(19),
410 :     IAV(20), IAV(21), IAV(22), IAV(23), IAV(24),
411 :     IAV(25), IAV(26), IAV(27), IAV(28), IAV(29),
412 :     IAV(30), IAV(31), IAV(32), IAV(33), IAV(34),
413 :     IAV(35), IAV(36), IAV(37), IAV(38), IAV(39),
414 :     IAV(40), IAV(41), IAV(42), IAV(43), IAV(44),
415 :     IAV(45), IAV(46), IAV(47), IAV(48), IAV(49),
416 :     IAV(50), IAV(51), IAV(52), IAV(53), IAV(54),
417 :     IAV(55), IAV(56), IAV(57), IAV(58), IAV(59),
418 :     IAV(60), IAV(61), IAV(62), IAV(63), IAV(64),
419 :     IAV(65), IAV(66), IAV(67), IAV(68), IAV(69),
420 :     IAV(70), IAV(71), IAV(72), IAV(73), IAV(74),
421 :     IAV(75), IAV(76), IAV(77), IAV(78), IAV(79),
422 :     IAV(80), IAV(81), IAV(82), IAV(83), IAV(84),
423 :     IAV(85), IAV(86), IAV(87), IAV(88), IAV(89),
424 :     IAV(90), IAV(91), IAV(92), IAV(93), IAV(94),
425 :     IAV(95), IAV(96), IAV(97), IAV(98), IAV(99),
426 :     IAV(100), IAV(101), IAV(102), IAV(103), IAV(104),
427 :     IAV(105), IAV(106), IAV(107), IAV(108), IAV(109),
428 :     IAV(110), IAV(111), IAV(112), IAV(113), IAV(114),
429 :     IAV(115), IAV(116), IAV(117), IAV(118), IAV(119),
430 :     IAV(120), IAV(121), IAV(122), IAV(123), IAV(124),
431 :     IAV(125), IAV(126), IAV(127)
432 :     };
433 :    
434 :    
435 :    
436 :     /*
437 :     Auxiliary lists
438 :    
439 :     Even though they use bk/fd ptrs, neither of these are doubly linked!
440 :     They are null-terminated since only the first is ever accessed.
441 :     returned_list is just singly linked for speed in free().
442 :     last_remainder currently has length of at most one.
443 :    
444 :     */
445 :    
446 :     static mchunkptr returned_list = 0; /* List of (unbinned) returned chunks */
447 :     static mchunkptr last_remainder = 0; /* last remaindered chunk from malloc */
448 :    
449 :    
450 :    
451 :     /*
452 :     Indexing into bins
453 :    
454 :     Funny-looking mechanics:
455 :     For small bins, the index is just size/8.
456 :     For others, first find index corresponding to the power of 2
457 :     closest to size, using a variant of standard base-2 log
458 :     calculation that starts with the first non-small index and
459 :     adjusts the size so that zero corresponds with it. On each
460 :     iteration, the index is incremented across the four quadrants
461 :     per power of two. (This loop runs a max of 27 iterations;
462 :     usually much less.) After the loop, the remainder is quartered
463 :     to find quadrant. The offsets for loop termination and
464 :     quartering allow bins to start, not end at powers.
465 :     */
466 :    
467 :    
468 :     #define findbin(Sizefb, Bfb) \
469 :     { \
470 :     size_t Sfb = (Sizefb); \
471 :     if (Sfb < MAX_SMALLBIN_SIZE) \
472 :     (Bfb) = (av + (Sfb >> 3)); \
473 :     else \
474 :     { \
475 :     /* Offset wrt small bins */ \
476 :     size_t Ifb = MAX_SMALLBIN_OFFSET; \
477 :     Sfb >>= 3; \
478 :     /* find power of 2 */ \
479 :     while (Sfb >= (MINSIZE * 2)) { Ifb += 4; Sfb >>= 1; } \
480 :     /* adjust for quadrant */ \
481 :     Ifb += (Sfb - MINSIZE) >> 2; \
482 :     (Bfb) = av + Ifb; \
483 :     } \
484 :     } \
485 :    
486 :    
487 :    
488 :    
489 :     /* Keep track of the maximum actually used clean bin, to make loops faster */
490 :     /* (Not worth it to do the same for dirty ones) */
491 :    
492 :     static mbinptr maxClean = FIRSTBIN;
493 :    
494 :     #define reset_maxClean \
495 :     { \
496 :     while (maxClean > FIRSTBIN && clean_head(maxClean)==last_clean(maxClean)) \
497 :     --maxClean; \
498 :     } \
499 :    
500 :    
501 :     /* Macros for linking and unlinking chunks */
502 :    
503 :     /* take a chunk off a list */
504 :    
505 :     #define unlink(Qul) \
506 :     { \
507 :     mchunkptr Bul = (Qul)->bk; \
508 :     mchunkptr Ful = (Qul)->fd; \
509 :     Ful->bk = Bul; Bul->fd = Ful; \
510 :     } \
511 :    
512 :    
513 :     /* place a chunk on the dirty list of its bin */
514 :    
515 :     #define dirtylink(Qdl) \
516 :     { \
517 :     mchunkptr Pdl = (Qdl); \
518 :     mbinptr Bndl; \
519 :     mchunkptr Hdl, Fdl; \
520 :     \
521 :     findbin(Pdl->size, Bndl); \
522 :     Hdl = dirty_head(Bndl); \
523 :     Fdl = Hdl->fd; \
524 :     \
525 :     Pdl->bk = Hdl; Pdl->fd = Fdl; Fdl->bk = Hdl->fd = Pdl; \
526 :     } \
527 :    
528 :    
529 :    
530 :     /* Place a consolidated chunk on a clean list */
531 :    
532 :     #define cleanlink(Qcl) \
533 :     { \
534 :     mchunkptr Pcl = (Qcl); \
535 :     mbinptr Bcl; \
536 :     mchunkptr Hcl, Fcl; \
537 :     \
538 :     findbin(Qcl->size, Bcl); \
539 :     Hcl = clean_head(Bcl); \
540 :     Fcl = Hcl->fd; \
541 :     if (Hcl == Fcl && Bcl > maxClean) maxClean = Bcl; \
542 :     \
543 :     Pcl->bk = Hcl; Pcl->fd = Fcl; Fcl->bk = Hcl->fd = Pcl; \
544 :     } \
545 :    
546 :    
547 :    
548 :     /* consolidate one chunk */
549 :    
550 :     #define consolidate(Qc) \
551 :     { \
552 :     for (;;) \
553 :     { \
554 :     mchunkptr Pc = prev_chunk(Qc); \
555 :     if (!inuse(Pc)) \
556 :     { \
557 :     unlink(Pc); \
558 :     set_size(Pc, Pc->size + (Qc)->size); \
559 :     (Qc) = Pc; \
560 :     } \
561 :     else break; \
562 :     } \
563 :     for (;;) \
564 :     { \
565 :     mchunkptr Nc = next_chunk(Qc); \
566 :     if (!inuse(Nc)) \
567 :     { \
568 :     unlink(Nc); \
569 :     set_size((Qc), (Qc)->size + Nc->size); \
570 :     } \
571 :     else break; \
572 :     } \
573 :     } \
574 :    
575 :    
576 :    
577 :     /* Place the held remainder in its bin */
578 :     /* This MUST be invoked prior to ANY consolidation */
579 :    
580 :     #define clear_last_remainder \
581 :     { \
582 :     if (last_remainder != 0) \
583 :     { \
584 :     cleanlink(last_remainder); \
585 :     last_remainder = 0; \
586 :     } \
587 :     } \
588 :    
589 :    
590 :     /* Place a freed chunk on the returned_list */
591 :    
592 :     #define return_chunk(Prc) \
593 :     { \
594 :     (Prc)->fd = returned_list; \
595 :     returned_list = (Prc); \
596 :     } \
597 :    
598 :    
599 :    
600 :     /* Misc utilities */
601 :    
602 :     /* A helper for realloc */
603 :    
604 :     static void free_returned_list()
605 :     {
606 :     clear_last_remainder;
607 :     while (returned_list != 0)
608 :     {
609 :     mchunkptr p = returned_list;
610 :     returned_list = p->fd;
611 :     clear_inuse(p);
612 :     dirtylink(p);
613 :     }
614 :     }
615 :    
616 :     /* Utilities needed below for memalign */
617 :     /* Standard greatest common divisor algorithm */
618 :    
619 :     static size_t gcd(size_t a, size_t b)
620 :     {
621 :     size_t tmp;
622 :    
623 :     if (b > a)
624 :     {
625 :     tmp = a; a = b; b = tmp;
626 :     }
627 :     for(;;)
628 :     {
629 :     if (b == 0)
630 :     return a;
631 :     else if (b == 1)
632 :     return b;
633 :     else
634 :     {
635 :     tmp = b;
636 :     b = a % b;
637 :     a = tmp;
638 :     }
639 :     }
640 :     }
641 :    
642 :     static size_t lcm(size_t x, size_t y)
643 :     {
644 :     return x / gcd(x, y) * y;
645 :     }
646 :    
647 :    
648 :    
649 :    
650 :    
651 :     /* Dealing with sbrk */
652 :     /* This is one step of malloc; broken out for simplicity */
653 :    
654 :     static size_t sbrked_mem = 0; /* Keep track of total mem for malloc_stats */
655 :    
656 :     static mchunkptr malloc_from_sys(size_t nb)
657 :     {
658 :    
659 :     /* The end of memory returned from previous sbrk call */
660 :     static size_t* last_sbrk_end = 0;
661 :    
662 :     mchunkptr p; /* Will hold a usable chunk */
663 :     size_t* ip; /* to traverse sbrk ptr in size_t units */
664 :    
665 :     /* Find a good size to ask sbrk for. */
666 :     /* Minimally, we need to pad with enough space */
667 :     /* to place dummy size/use fields to ends if needed */
668 :    
669 :     size_t sbrk_size = ((nb + SBRK_UNIT - 1 + SIZE_SZ + SIZE_SZ)
670 :     / SBRK_UNIT) * SBRK_UNIT;
671 :    
672 :     ip = (size_t*)(sbrk(sbrk_size));
673 :     if ((char*)ip == (char*)(-1)) /* sbrk returns -1 on failure */
674 :     return 0;
675 :    
676 :     sbrked_mem += sbrk_size;
677 :    
678 :     if (last_sbrk_end != &ip[-1]) /* Is this chunk continguous with last? */
679 :     {
680 :     /* It's either first time through or someone else called sbrk. */
681 :     /* Arrange end-markers at front & back */
682 :    
683 :     /* Shouldn't be necessary, but better to be safe */
684 :     while (!aligned_OK(ip)) { ++ip; sbrk_size -= SIZE_SZ; }
685 :    
686 :     /* Mark the front as in use to prevent merging. (End done below.) */
687 :     /* Note we can get away with only 1 word, not MINSIZE overhead here */
688 :    
689 :     *ip++ = SIZE_SZ | INUSE;
690 :    
691 :     p = (mchunkptr)ip;
692 :     set_size(p,sbrk_size - (SIZE_SZ + SIZE_SZ));
693 :    
694 :     }
695 :     else
696 :     {
697 :     mchunkptr l;
698 :    
699 :     /* We can safely make the header start at end of prev sbrked chunk. */
700 :     /* We will still have space left at the end from a previous call */
701 :     /* to place the end marker, below */
702 :    
703 :     p = (mchunkptr)(last_sbrk_end);
704 :     set_size(p, sbrk_size);
705 :    
706 :     /* Even better, maybe we can merge with last fragment: */
707 :    
708 :     l = prev_chunk(p);
709 :     if (!inuse(l))
710 :     {
711 :     unlink(l);
712 :     set_size(l, p->size + l->size);
713 :     p = l;
714 :     }
715 :    
716 :     }
717 :    
718 :     /* mark the end of sbrked space as in use to prevent merging */
719 :    
720 :     last_sbrk_end = (size_t*)((char*)p + p->size);
721 :     *last_sbrk_end = SIZE_SZ | INUSE;
722 :    
723 :     return p;
724 :     }
725 :    
726 :    
727 :    
728 :    
729 :     /* Consolidate dirty chunks until create one big enough for current req. */
730 :     /* Call malloc_from_sys if can't create one. */
731 :     /* This is just one phase of malloc, but broken out for sanity */
732 :    
733 :     static mchunkptr malloc_find_space(size_t nb)
734 :     {
735 :     /* Circularly traverse bins so as not to pick on any one too much */
736 :     static mbinptr rover = LASTBIN; /* Circular roving ptr */
737 :    
738 :     mbinptr origin = rover;
739 :     mbinptr b = rover;
740 :    
741 :     /* Preliminaries. */
742 :     clear_last_remainder;
743 :     reset_maxClean;
744 :    
745 :     do
746 :     {
747 :     mchunkptr p;
748 :    
749 :     while ( (p = last_dirty(b)) != dirty_head(b))
750 :     {
751 :     unlink(p);
752 :     consolidate(p);
753 :    
754 :     if (p->size >= nb)
755 :     {
756 :     rover = b;
757 :     return p;
758 :     }
759 :     else
760 :     cleanlink(p);
761 :     }
762 :    
763 :     b = (b == FIRSTBIN)? LASTBIN : b - 1; /* circularly sweep down */
764 :    
765 :     } while (b != origin);
766 :    
767 :     /* If no return above, chain to the next step of malloc */
768 :     return malloc_from_sys(nb);
769 :     }
770 :    
771 :    
772 :     /* Clear out dirty chunks from a bin, along with the free list. */
773 :     /* Invoked from malloc when things look too fragmented */
774 :    
775 :     static void malloc_clean_bin(mbinptr bin)
776 :     {
777 :     mchunkptr p;
778 :    
779 :     clear_last_remainder;
780 :    
781 :     while ( (p = last_dirty(bin)) != dirty_head(bin))
782 :     {
783 :     unlink(p);
784 :     consolidate(p);
785 :     cleanlink(p);
786 :     }
787 :    
788 :     while (returned_list != 0)
789 :     {
790 :     p = returned_list;
791 :     returned_list = p->fd;
792 :     clear_inuse(p);
793 :     consolidate(p);
794 :     cleanlink(p);
795 :     }
796 :     }
797 :    
798 :    
799 :    
800 :    
801 :     /* Finally, the user-level functions */
802 :    
803 :    
804 :     void* malloc(size_t bytes)
805 :     {
806 :     static size_t previous_request = 0; /* To control preallocation */
807 :    
808 :     size_t nb = request2size(bytes); /* padded request size */
809 :     mbinptr bin; /* corresponding bin */
810 :     mchunkptr victim; /* will hold selected chunk */
811 :    
812 :     /* ----------- Peek at returned_list; hope for luck */
813 :    
814 :     if ((victim = returned_list) != 0 &&
815 :     exact_fit(victim, nb)) /* size check works even though INUSE set */
816 :     {
817 :     returned_list = victim->fd;
818 :     return chunk2mem(victim);
819 :     }
820 :    
821 :     findbin(nb, bin); /* Need to know bin for other traversals */
822 :    
823 :     /* ---------- Scan dirty list of own bin */
824 :    
825 :     /* Code for small bins special-cased out since */
826 :     /* no size check or traversal needed and */
827 :     /* clean bins are exact matches so might as well test now */
828 :    
829 :     if (nb < MAX_SMALLBIN_SIZE)
830 :     {
831 :     if ( ((victim = first_dirty(bin)) != dirty_head(bin)) ||
832 :     ((victim = last_clean(bin)) != clean_head(bin)))
833 :     {
834 :     unlink(victim);
835 :     set_inuse(victim);
836 :     return chunk2mem(victim);
837 :     }
838 :     }
839 :     else
840 :     {
841 :     if ( (victim = first_dirty(bin)) != dirty_head(bin))
842 :     {
843 :     do
844 :     {
845 :     if (exact_fit(victim, nb))
846 :     {
847 :     unlink(victim);
848 :     set_inuse(victim);
849 :     return chunk2mem(victim);
850 :     }
851 :     else victim = victim->fd;
852 :     } while (victim != dirty_head(bin));
853 :    
854 :     /* If there were chunks in there but none matched, then */
855 :     /* consolidate all chunks in this bin plus those on free list */
856 :     /* to prevent further traversals and fragmentation. */
857 :    
858 :     malloc_clean_bin(bin);
859 :     }
860 :     }
861 :    
862 :     /* ------------ Search free list */
863 :    
864 :     if ( (victim = returned_list) != 0)
865 :     {
866 :     do
867 :     {
868 :     mchunkptr next = victim->fd;
869 :     if (exact_fit(victim, nb))
870 :     {
871 :     returned_list = next;
872 :     return chunk2mem(victim);
873 :     }
874 :     else /* Place unusable chunks in their bins */
875 :     {
876 :     clear_inuse(victim);
877 :     dirtylink(victim);
878 :     victim = next;
879 :     }
880 :     } while (victim != 0);
881 :     returned_list = 0;
882 :     }
883 :    
884 :     /* -------------- Try the remainder from last successful split */
885 :    
886 :     if ( (victim = last_remainder) != 0 && victim->size >= nb)
887 :     {
888 :     last_remainder = 0; /* reset for next time */
889 :     goto split;
890 :     }
891 :    
892 :     /* -------------- Scan through own clean bin */
893 :    
894 :     /* (Traversing back-to-front tends to choose `old' */
895 :     /* chunks that could not be further consolidated.) */
896 :    
897 :     for (victim = last_clean(bin); victim != clean_head(bin); victim=victim->bk)
898 :     {
899 :     if (victim->size >= nb)
900 :     {
901 :     unlink(victim);
902 :     goto split;
903 :     }
904 :     }
905 :    
906 :     /* -------------- Try all bigger clean bins */
907 :    
908 :     /* (Scanning upwards is slower but prevents fragmenting big */
909 :     /* chunks that we might need later. If there aren't any smaller */
910 :     /* ones, most likely we got a big one from last_remainder anyway.) */
911 :    
912 :     {
913 :     mbinptr b;
914 :    
915 :     for (b = bin + 1; b <= maxClean; ++b)
916 :     {
917 :     if ( (victim = last_clean(b)) != clean_head(b) )
918 :     {
919 :     unlink(victim);
920 :     goto split;
921 :     }
922 :     }
923 :     }
924 :    
925 :     /* ------------- Consolidate or sbrk */
926 :    
927 :     victim = malloc_find_space(nb);
928 :    
929 :     if (victim == 0) /* propagate failure */
930 :     return 0;
931 :    
932 :     /* -------------- Possibly split victim chunk */
933 :    
934 :     split:
935 :     {
936 :     size_t room = victim->size - nb;
937 :     if (room >= MINSIZE)
938 :     {
939 :     mchunkptr v = victim; /* Hold so can break up in prealloc */
940 :    
941 :     set_size(victim, nb); /* Adjust size of chunk to be returned */
942 :    
943 :     /* ---------- Preallocate */
944 :    
945 :     /* Try to preallocate some more of this size if */
946 :     /* last (split) req was of same size */
947 :    
948 :     if (previous_request == nb)
949 :     {
950 :     int i;
951 :    
952 :     for (i = 0; i < MAX_PREALLOCS && room >= nb + MINSIZE; ++i)
953 :     {
954 :     room -= nb;
955 :    
956 :     v = (mchunkptr)((char*)(v) + nb);
957 :     set_size(v, nb);
958 :     set_inuse(v); /* free-list chunks must have inuse set */
959 :     return_chunk(v); /* add to free list */
960 :     }
961 :     }
962 :    
963 :     previous_request = nb; /* record for next time */
964 :    
965 :     /* ---------- Create remainder chunk */
966 :    
967 :     /* Get rid of the old one first */
968 :     if (last_remainder != 0) cleanlink(last_remainder);
969 :    
970 :     last_remainder = (mchunkptr)((char*)(v) + nb);
971 :     set_size(last_remainder, room);
972 :     }
973 :    
974 :     set_inuse(victim);
975 :     return chunk2mem(victim);
976 :     }
977 :     }
978 :    
979 :    
980 :    
981 :    
982 :     void free(void* mem)
983 :     {
984 :     if (mem != 0)
985 :     {
986 :     mchunkptr p = mem2chunk(mem);
987 :     return_chunk(p);
988 :     }
989 :     }
990 :    
991 :    
992 :    
993 :    
994 :     void* realloc(void* mem, size_t bytes)
995 :     {
996 :     if (mem == 0)
997 :     return malloc(bytes);
998 :     else
999 :     {
1000 :     size_t nb = request2size(bytes);
1001 :     mchunkptr p = mem2chunk(mem);
1002 :     size_t oldsize;
1003 :     long room;
1004 :     mchunkptr nxt;
1005 :    
1006 :     if (p == returned_list) /* support realloc-last-freed-chunk idiocy */
1007 :     returned_list = returned_list->fd;
1008 :    
1009 :     clear_inuse(p);
1010 :     oldsize = p->size;
1011 :    
1012 :     /* try to expand (even if already big enough), to clean up chunk */
1013 :    
1014 :     free_returned_list(); /* make freed chunks available to consolidate */
1015 :    
1016 :     while (!inuse(nxt = next_chunk(p))) /* Expand the chunk forward */
1017 :     {
1018 :     unlink(nxt);
1019 :     set_size(p, p->size + nxt->size);
1020 :     }
1021 :    
1022 :     room = p->size - nb;
1023 :     if (room >= 0) /* Successful expansion */
1024 :     {
1025 :     if (room >= MINSIZE) /* give some back if possible */
1026 :     {
1027 :     mchunkptr remainder = (mchunkptr)((char*)(p) + nb);
1028 :     set_size(remainder, room);
1029 :     cleanlink(remainder);
1030 :     set_size(p, nb);
1031 :     }
1032 :     set_inuse(p);
1033 :     return chunk2mem(p);
1034 :     }
1035 :     else /* Could not expand. Get another chunk and copy. */
1036 :     {
1037 :     void* newmem;
1038 :     size_t count;
1039 :     size_t* src;
1040 :     size_t* dst;
1041 :    
1042 :     set_inuse(p); /* don't let malloc consolidate us yet! */
1043 :     newmem = malloc(nb);
1044 :    
1045 :     /* Copy -- we know that alignment is at least `size_t' */
1046 :    
1047 :     src = (size_t*) mem;
1048 :     dst = (size_t*) newmem;
1049 :     count = (oldsize - SIZE_SZ) / sizeof(size_t);
1050 :     while (count-- > 0) *dst++ = *src++;
1051 :    
1052 :     free(mem);
1053 :     return newmem;
1054 :     }
1055 :     }
1056 :     }
1057 :    
1058 :    
1059 :    
1060 :     /* Return a pointer to space with at least the alignment requested */
1061 :     /* Alignment argument should be a power of two */
1062 :    
1063 :     void* memalign(size_t alignment, size_t bytes)
1064 :     {
1065 :     mchunkptr p;
1066 :     size_t nb = request2size(bytes);
1067 :     size_t room;
1068 :    
1069 :     /* find an alignment that both we and the user can live with: */
1070 :     /* least common multiple guarantees mutual happiness */
1071 :     size_t align = lcm(alignment, MALLOC_MIN_OVERHEAD);
1072 :    
1073 :     /* call malloc with worst case padding to hit alignment; */
1074 :     /* we will give back extra */
1075 :    
1076 :     size_t req = nb + align + MINSIZE;
1077 :     void* m = malloc(req);
1078 :    
1079 :     if (m == 0) return 0; /* propagate failure */
1080 :    
1081 :     p = mem2chunk(m);
1082 :     clear_inuse(p);
1083 :    
1084 :    
1085 :     if (((size_t)(m) % align) != 0) /* misaligned */
1086 :     {
1087 :    
1088 :     /* find an aligned spot inside chunk */
1089 :    
1090 :     mchunkptr ap = (mchunkptr)((((size_t)(m) + align-1) & -align) - SIZE_SZ);
1091 :    
1092 :     size_t gap = (size_t)(ap) - (size_t)(p);
1093 :    
1094 :     /* we need to give back leading space in a chunk of at least MINSIZE */
1095 :    
1096 :     if (gap < MINSIZE)
1097 :     {
1098 :     /* This works since align >= MINSIZE */
1099 :     /* and we've malloc'd enough total room */
1100 :    
1101 :     ap = (mchunkptr)( (size_t)(ap) + align );
1102 :     gap += align;
1103 :     }
1104 :    
1105 :     room = p->size - gap;
1106 :    
1107 :     /* give back leader */
1108 :     set_size(p, gap);
1109 :     dirtylink(p); /* Don't really know if clean or dirty; be safe */
1110 :    
1111 :     /* use the rest */
1112 :     p = ap;
1113 :     set_size(p, room);
1114 :     }
1115 :    
1116 :     /* also give back spare room at the end */
1117 :    
1118 :     room = p->size - nb;
1119 :     if (room >= MINSIZE)
1120 :     {
1121 :     mchunkptr remainder = (mchunkptr)((char*)(p) + nb);
1122 :     set_size(remainder, room);
1123 :     dirtylink(remainder); /* Don't really know; be safe */
1124 :     set_size(p, nb);
1125 :     }
1126 :    
1127 :     set_inuse(p);
1128 :     return chunk2mem(p);
1129 :    
1130 :     }
1131 :    
1132 :    
1133 :    
1134 :     /* Derivatives */
1135 :    
1136 :     void* valloc(size_t bytes)
1137 :     {
1138 :     /* Cache result of getpagesize */
1139 :     static size_t malloc_pagesize = 0;
1140 :    
1141 :     if (malloc_pagesize == 0) malloc_pagesize = malloc_getpagesize;
1142 :     return memalign (malloc_pagesize, bytes);
1143 :     }
1144 :    
1145 :    
1146 :     void* calloc(size_t n, size_t elem_size)
1147 :     {
1148 :     size_t sz = n * elem_size;
1149 :     void* p = malloc(sz);
1150 :     char* q = (char*) p;
1151 :     while (sz-- > 0) *q++ = 0;
1152 :     return p;
1153 :     }
1154 :    
1155 :     void cfree(void *mem)
1156 :     {
1157 :     free(mem);
1158 :     }
1159 :    
1160 :     size_t malloc_usable_size(void* mem)
1161 :     {
1162 :     if (mem == 0)
1163 :     return 0;
1164 :     else
1165 :     {
1166 :     mchunkptr p = (mchunkptr)((char*)(mem) - SIZE_SZ);
1167 :     size_t sz = p->size & ~(INUSE);
1168 :     /* report zero if not in use or detectably corrupt */
1169 :     if (p->size == sz || sz != *((size_t*)((char*)(p) + sz - SIZE_SZ)))
1170 :     return 0;
1171 :     else
1172 :     return sz - MALLOC_MIN_OVERHEAD;
1173 :     }
1174 :     }
1175 :    
1176 :    
1177 :     void malloc_stats()
1178 :     {
1179 :    
1180 :     /* Traverse through and count all sizes of all chunks */
1181 :    
1182 :     size_t avail = 0;
1183 :     size_t malloced_mem;
1184 :    
1185 :     mbinptr b;
1186 :    
1187 :     free_returned_list();
1188 :    
1189 :     for (b = FIRSTBIN; b <= LASTBIN; ++b)
1190 :     {
1191 :     mchunkptr p;
1192 :    
1193 :     for (p = first_dirty(b); p != dirty_head(b); p = p->fd)
1194 :     avail += p->size;
1195 :    
1196 :     for (p = first_clean(b); p != clean_head(b); p = p->fd)
1197 :     avail += p->size;
1198 :     }
1199 :    
1200 :     malloced_mem = sbrked_mem - avail;
1201 :    
1202 :     fprintf(stderr, "total mem = %10u\n", sbrked_mem);
1203 :     fprintf(stderr, "in use = %10u\n", malloced_mem);
1204 :    
1205 :     }
1206 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0