![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to malloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / lib / libc / gen|
Return to malloc.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / lib / libc / gen |
1.1 root 1: /*
2: * Copyright (c) 1983 Regents of the University of California.
3: * All rights reserved. The Berkeley software License Agreement
4: * specifies the terms and conditions for redistribution.
5: */
6:
7: #if defined(LIBC_SCCS) && !defined(lint)
8: static char sccsid[] = "@(#)malloc.c 5.6 (Berkeley) 3/9/86";
9: #endif LIBC_SCCS and not lint
10:
11: /*
12: * malloc.c (Caltech) 2/21/82
13: * Chris Kingsley, kingsley@cit-20.
14: *
15: * This is a very fast storage allocator. It allocates blocks of a small
16: * number of different sizes, and keeps free lists of each size. Blocks that
17: * don't exactly fit are passed up to the next larger size. In this
18: * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
19: * This is designed for use in a virtual memory environment.
20: */
21:
22: #include <sys/types.h>
23:
24: #define NULL 0
25:
26: /*
27: * The overhead on a block is at least 4 bytes. When free, this space
28: * contains a pointer to the next free block, and the bottom two bits must
29: * be zero. When in use, the first byte is set to MAGIC, and the second
30: * byte is the size index. The remaining bytes are for alignment.
31: * If range checking is enabled then a second word holds the size of the
32: * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
33: * The order of elements is critical: ov_magic must overlay the low order
34: * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
35: */
36: union overhead {
37: union overhead *ov_next; /* when free */
38: struct {
39: u_char ovu_magic; /* magic number */
40: u_char ovu_index; /* bucket # */
41: #ifdef RCHECK
42: u_short ovu_rmagic; /* range magic number */
43: u_int ovu_size; /* actual block size */
44: #endif
45: } ovu;
46: #define ov_magic ovu.ovu_magic
47: #define ov_index ovu.ovu_index
48: #define ov_rmagic ovu.ovu_rmagic
49: #define ov_size ovu.ovu_size
50: };
51:
52: #define MAGIC 0xef /* magic # on accounting info */
53: #define RMAGIC 0x5555 /* magic # on range info */
54:
55: #ifdef RCHECK
56: #define RSLOP sizeof (u_short)
57: #else
58: #define RSLOP 0
59: #endif
60:
61: /*
62: * nextf[i] is the pointer to the next free block of size 2^(i+3). The
63: * smallest allocatable block is 8 bytes. The overhead information
64: * precedes the data area returned to the user.
65: */
66: #define NBUCKETS 30
67: static union overhead *nextf[NBUCKETS];
68: extern char *sbrk();
69:
70: static int pagesz; /* page size */
71: static int pagebucket; /* page size bucket */
72:
73: #ifdef MSTATS
74: /*
75: * nmalloc[i] is the difference between the number of mallocs and frees
76: * for a given block size.
77: */
78: static u_int nmalloc[NBUCKETS];
79: #include <stdio.h>
80: #endif
81:
82: #if defined(DEBUG) || defined(RCHECK)
83: #define ASSERT(p) if (!(p)) botch("p")
84: #include <stdio.h>
85: static
86: botch(s)
87: char *s;
88: {
89: fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
90: (void) fflush(stderr); /* just in case user buffered it */
91: abort();
92: }
93: #else
94: #define ASSERT(p)
95: #endif
96:
97: char *
98: malloc(nbytes)
99: unsigned nbytes;
100: {
101: register union overhead *op;
102: register int bucket;
103: register unsigned amt, n;
104:
105: /*
106: * First time malloc is called, setup page size and
107: * align break pointer so all data will be page aligned.
108: */
109: if (pagesz == 0) {
110: pagesz = n = getpagesize();
111: op = (union overhead *)sbrk(0);
112: n = n - sizeof (*op) - ((int)op & (n - 1));
113: if (n < 0)
114: n += pagesz;
115: if (n) {
116: if (sbrk(n) == (char *)-1)
117: return (NULL);
118: }
119: bucket = 0;
120: amt = 8;
121: while (pagesz > amt) {
122: amt <<= 1;
123: bucket++;
124: }
125: pagebucket = bucket;
126: }
127: /*
128: * Convert amount of memory requested into closest block size
129: * stored in hash buckets which satisfies request.
130: * Account for space used per block for accounting.
131: */
132: if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
133: #ifndef RCHECK
134: amt = 8; /* size of first bucket */
135: bucket = 0;
136: #else
137: amt = 16; /* size of first bucket */
138: bucket = 1;
139: #endif
140: n = -(sizeof (*op) + RSLOP);
141: } else {
142: amt = pagesz;
143: bucket = pagebucket;
144: }
145: while (nbytes > amt + n) {
146: amt <<= 1;
147: if (amt == 0)
148: return (NULL);
149: bucket++;
150: }
151: /*
152: * If nothing in hash bucket right now,
153: * request more memory from the system.
154: */
155: if ((op = nextf[bucket]) == NULL) {
156: morecore(bucket);
157: if ((op = nextf[bucket]) == NULL)
158: return (NULL);
159: }
160: /* remove from linked list */
161: nextf[bucket] = op->ov_next;
162: op->ov_magic = MAGIC;
163: op->ov_index = bucket;
164: #ifdef MSTATS
165: nmalloc[bucket]++;
166: #endif
167: #ifdef RCHECK
168: /*
169: * Record allocated size of block and
170: * bound space with magic numbers.
171: */
172: op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
173: op->ov_rmagic = RMAGIC;
174: *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
175: #endif
176: return ((char *)(op + 1));
177: }
178:
179: /*
180: * Allocate more memory to the indicated bucket.
181: */
182: morecore(bucket)
183: int bucket;
184: {
185: register union overhead *op;
186: register int sz; /* size of desired block */
187: int amt; /* amount to allocate */
188: int nblks; /* how many blocks we get */
189:
190: /*
191: * sbrk_size <= 0 only for big, FLUFFY, requests (about
192: * 2^30 bytes on a VAX, I think) or for a negative arg.
193: */
194: sz = 1 << (bucket + 3);
195: #ifdef DEBUG
196: ASSERT(sz > 0);
197: #else
198: if (sz <= 0)
199: return;
200: #endif
201: if (sz < pagesz) {
202: amt = pagesz;
203: nblks = amt / sz;
204: } else {
205: amt = sz + pagesz;
206: nblks = 1;
207: }
208: op = (union overhead *)sbrk(amt);
209: /* no more room! */
210: if ((int)op == -1)
211: return;
212: /*
213: * Add new memory allocated to that on
214: * free list for this hash bucket.
215: */
216: nextf[bucket] = op;
217: while (--nblks > 0) {
218: op->ov_next = (union overhead *)((caddr_t)op + sz);
219: op = (union overhead *)((caddr_t)op + sz);
220: }
221: }
222:
223: free(cp)
224: char *cp;
225: {
226: register int size;
227: register union overhead *op;
228:
229: if (cp == NULL)
230: return;
231: op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
232: #ifdef DEBUG
233: ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */
234: #else
235: if (op->ov_magic != MAGIC)
236: return; /* sanity */
237: #endif
238: #ifdef RCHECK
239: ASSERT(op->ov_rmagic == RMAGIC);
240: ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
241: #endif
242: size = op->ov_index;
243: ASSERT(size < NBUCKETS);
244: op->ov_next = nextf[size]; /* also clobbers ov_magic */
245: nextf[size] = op;
246: #ifdef MSTATS
247: nmalloc[size]--;
248: #endif
249: }
250:
251: /*
252: * When a program attempts "storage compaction" as mentioned in the
253: * old malloc man page, it realloc's an already freed block. Usually
254: * this is the last block it freed; occasionally it might be farther
255: * back. We have to search all the free lists for the block in order
256: * to determine its bucket: 1st we make one pass thru the lists
257: * checking only the first block in each; if that fails we search
258: * ``realloc_srchlen'' blocks in each list for a match (the variable
259: * is extern so the caller can modify it). If that fails we just copy
260: * however many bytes was given to realloc() and hope it's not huge.
261: */
262: int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
263:
264: char *
265: realloc(cp, nbytes)
266: char *cp;
267: unsigned nbytes;
268: {
269: register u_int onb, i;
270: union overhead *op;
271: char *res;
272: int was_alloced = 0;
273:
274: if (cp == NULL)
275: return (malloc(nbytes));
276: op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
277: if (op->ov_magic == MAGIC) {
278: was_alloced++;
279: i = op->ov_index;
280: } else {
281: /*
282: * Already free, doing "compaction".
283: *
284: * Search for the old block of memory on the
285: * free list. First, check the most common
286: * case (last element free'd), then (this failing)
287: * the last ``realloc_srchlen'' items free'd.
288: * If all lookups fail, then assume the size of
289: * the memory block being realloc'd is the
290: * largest possible (so that all "nbytes" of new
291: * memory are copied into). Note that this could cause
292: * a memory fault if the old area was tiny, and the moon
293: * is gibbous. However, that is very unlikely.
294: */
295: if ((i = findbucket(op, 1)) < 0 &&
296: (i = findbucket(op, realloc_srchlen)) < 0)
297: i = NBUCKETS;
298: }
299: onb = 1 << (i + 3);
300: if (onb < pagesz)
301: onb -= sizeof (*op) + RSLOP;
302: else
303: onb += pagesz - sizeof (*op) - RSLOP;
304: /* avoid the copy if same size block */
305: if (was_alloced) {
306: if (i) {
307: i = 1 << (i + 2);
308: if (i < pagesz)
309: i -= sizeof (*op) + RSLOP;
310: else
311: i += pagesz - sizeof (*op) - RSLOP;
312: }
313: if (nbytes <= onb && nbytes > i) {
314: #ifdef RCHECK
315: op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
316: *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
317: #endif
318: return(cp);
319: } else
320: free(cp);
321: }
322: if ((res = malloc(nbytes)) == NULL)
323: return (NULL);
324: if (cp != res) /* common optimization if "compacting" */
325: bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
326: return (res);
327: }
328:
329: /*
330: * Search ``srchlen'' elements of each free list for a block whose
331: * header starts at ``freep''. If srchlen is -1 search the whole list.
332: * Return bucket number, or -1 if not found.
333: */
334: static
335: findbucket(freep, srchlen)
336: union overhead *freep;
337: int srchlen;
338: {
339: register union overhead *p;
340: register int i, j;
341:
342: for (i = 0; i < NBUCKETS; i++) {
343: j = 0;
344: for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
345: if (p == freep)
346: return (i);
347: j++;
348: }
349: }
350: return (-1);
351: }
352:
353: #ifdef MSTATS
354: /*
355: * mstats - print out statistics about malloc
356: *
357: * Prints two lines of numbers, one showing the length of the free list
358: * for each size category, the second showing the number of mallocs -
359: * frees for each size category.
360: */
361: mstats(s)
362: char *s;
363: {
364: register int i, j;
365: register union overhead *p;
366: int totfree = 0,
367: totused = 0;
368:
369: fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
370: for (i = 0; i < NBUCKETS; i++) {
371: for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
372: ;
373: fprintf(stderr, " %d", j);
374: totfree += j * (1 << (i + 3));
375: }
376: fprintf(stderr, "\nused:\t");
377: for (i = 0; i < NBUCKETS; i++) {
378: fprintf(stderr, " %d", nmalloc[i]);
379: totused += nmalloc[i] * (1 << (i + 3));
380: }
381: fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
382: totused, totfree);
383: }
384: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.