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