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