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

Parent Directory | 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