![[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] / 43BSD / ucb / lisp / franz / vax|
Return to malloc.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ucb / lisp / franz / vax |
1.1 root 1: #ifndef lint
2: static char sccsid[] = "@(#)malloc.c 4.3 (Berkeley) 9/16/83";
3: #endif
4:
5: /*
6: * malloc.c (Caltech) 2/21/82
7: * Chris Kingsley, kingsley@cit-20.
8: *
9: * This is a very fast storage allocator. It allocates blocks of a small
10: * number of different sizes, and keeps free lists of each size. Blocks that
11: * don't exactly fit are passed up to the next larger size. In this
12: * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
13: * This is designed for use in a program that uses vast quantities of memory,
14: * but bombs when it runs out.
15: */
16:
17: #include <sys/types.h>
18:
19: #define NULL 0
20:
21: /*
22: * The overhead on a block is at least 4 bytes. When free, this space
23: * contains a pointer to the next free block, and the bottom two bits must
24: * be zero. When in use, the first byte is set to MAGIC, and the second
25: * byte is the size index. The remaining bytes are for alignment.
26: * If range checking is enabled and the size of the block fits
27: * in two bytes, then the top two bytes hold the size of the requested block
28: * plus the range checking words, and the header word MINUS ONE.
29: */
30: union overhead {
31: union overhead *ov_next; /* when free */
32: struct {
33: u_char ovu_magic; /* magic number */
34: u_char ovu_index; /* bucket # */
35: #ifdef RCHECK
36: u_short ovu_size; /* actual block size */
37: u_int ovu_rmagic; /* range magic number */
38: #endif
39: } ovu;
40: #define ov_magic ovu.ovu_magic
41: #define ov_index ovu.ovu_index
42: #define ov_size ovu.ovu_size
43: #define ov_rmagic ovu.ovu_rmagic
44: };
45:
46: #define MAGIC 0xff /* magic # on accounting info */
47: #define RMAGIC 0x55555555 /* magic # on range info */
48: #ifdef RCHECK
49: #define RSLOP sizeof (u_int)
50: #else
51: #define RSLOP 0
52: #endif
53:
54: /*
55: * nextf[i] is the pointer to the next free block of size 2^(i+3). The
56: * smallest allocatable block is 8 bytes. The overhead information
57: * precedes the data area returned to the user.
58: */
59: #define NBUCKETS 30
60: static union overhead *nextf[NBUCKETS];
61: extern char *sbrk();
62:
63: #ifdef MSTATS
64: /*
65: * nmalloc[i] is the difference between the number of mallocs and frees
66: * for a given block size.
67: */
68: static u_int nmalloc[NBUCKETS];
69: #include <stdio.h>
70: #endif
71:
72: #ifdef debug
73: #define ASSERT(p) if (!(p)) botch("p"); else
74: static
75: botch(s)
76: char *s;
77: {
78:
79: printf("assertion botched: %s\n", s);
80: abort();
81: }
82: #else
83: #define ASSERT(p)
84: #endif
85:
86: char *
87: malloc(nbytes)
88: register unsigned nbytes;
89: {
90: register union overhead *p;
91: register int bucket = 0;
92: register unsigned shiftr;
93:
94: /*
95: * Convert amount of memory requested into
96: * closest block size stored in hash buckets
97: * which satisfies request. Account for
98: * space used per block for accounting.
99: */
100: nbytes += sizeof (union overhead) + RSLOP;
101: nbytes = (nbytes + 3) &~ 3;
102: shiftr = (nbytes - 1) >> 2;
103: /* apart from this loop, this is O(1) */
104: while (shiftr >>= 1)
105: bucket++;
106: /*
107: * If nothing in hash bucket right now,
108: * request more memory from the system.
109: */
110: if (nextf[bucket] == NULL)
111: morecore(bucket);
112: if ((p = (union overhead *)nextf[bucket]) == NULL)
113: return (NULL);
114: /* remove from linked list */
115: nextf[bucket] = nextf[bucket]->ov_next;
116: p->ov_magic = MAGIC;
117: p->ov_index= bucket;
118: #ifdef MSTATS
119: nmalloc[bucket]++;
120: #endif
121: #ifdef RCHECK
122: /*
123: * Record allocated size of block and
124: * bound space with magic numbers.
125: */
126: if (nbytes <= 0x10000)
127: p->ov_size = nbytes - 1;
128: p->ov_rmagic = RMAGIC;
129: *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
130: #endif
131: return ((char *)(p + 1));
132: }
133:
134: /*
135: * Allocate more memory to the indicated bucket.
136: */
137: static
138: morecore(bucket)
139: register bucket;
140: {
141: register union overhead *op;
142: register int rnu; /* 2^rnu bytes will be requested */
143: register int nblks; /* become nblks blocks of the desired size */
144: register int siz;
145:
146: if (nextf[bucket])
147: return;
148: /*
149: * Insure memory is allocated
150: * on a page boundary. Should
151: * make getpageize call?
152: */
153: op = (union overhead *)sbrk(0);
154: if ((int)op & 0x3ff)
155: sbrk(1024 - ((int)op & 0x3ff));
156: /* take 2k unless the block is bigger than that */
157: rnu = (bucket <= 8) ? 11 : bucket + 3;
158: nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */
159: if (rnu < bucket)
160: rnu = bucket;
161: op = (union overhead *)sbrk(1 << rnu);
162: /* no more room! */
163: if ((int)op == -1)
164: return;
165: /*
166: * Round up to minimum allocation size boundary
167: * and deduct from block count to reflect.
168: */
169: if ((int)op & 7) {
170: op = (union overhead *)(((int)op + 8) &~ 7);
171: nblks--;
172: }
173: /*
174: * Add new memory allocated to that on
175: * free list for this hash bucket.
176: */
177: nextf[bucket] = op;
178: siz = 1 << (bucket + 3);
179: while (--nblks > 0) {
180: op->ov_next = (union overhead *)((caddr_t)op + siz);
181: op = (union overhead *)((caddr_t)op + siz);
182: }
183: }
184:
185: free(cp)
186: char *cp;
187: {
188: register int size;
189: register union overhead *op;
190:
191: if (cp == NULL)
192: return;
193: op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
194: #ifdef debug
195: ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */
196: #else
197: if (op->ov_magic != MAGIC)
198: return; /* sanity */
199: #endif
200: #ifdef RCHECK
201: ASSERT(op->ov_rmagic == RMAGIC);
202: if (op->ov_index <= 13)
203: ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
204: #endif
205: ASSERT(op->ov_index < NBUCKETS);
206: size = op->ov_index;
207: op->ov_next = nextf[size];
208: nextf[size] = op;
209: #ifdef MSTATS
210: nmalloc[size]--;
211: #endif
212: }
213:
214: /*
215: * When a program attempts "storage compaction" as mentioned in the
216: * old malloc man page, it realloc's an already freed block. Usually
217: * this is the last block it freed; occasionally it might be farther
218: * back. We have to search all the free lists for the block in order
219: * to determine its bucket: 1st we make one pass thru the lists
220: * checking only the first block in each; if that fails we search
221: * ``realloc_srchlen'' blocks in each list for a match (the variable
222: * is extern so the caller can modify it). If that fails we just copy
223: * however many bytes was given to realloc() and hope it's not huge.
224: */
225: int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
226:
227: char *
228: realloc(cp, nbytes)
229: char *cp;
230: unsigned nbytes;
231: {
232: register u_int onb;
233: union overhead *op;
234: char *res;
235: register int i;
236: int was_alloced = 0;
237:
238: if (cp == NULL)
239: return (malloc(nbytes));
240: op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
241: if (op->ov_magic == MAGIC) {
242: was_alloced++;
243: i = op->ov_index;
244: } else {
245: /*
246: * Already free, doing "compaction".
247: *
248: * Search for the old block of memory on the
249: * free list. First, check the most common
250: * case (last element free'd), then (this failing)
251: * the last ``realloc_srchlen'' items free'd.
252: * If all lookups fail, then assume the size of
253: * the memory block being realloc'd is the
254: * smallest possible.
255: */
256: if ((i = findbucket(op, 1)) < 0 &&
257: (i = findbucket(op, realloc_srchlen)) < 0)
258: i = 0;
259: }
260: onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
261: /* avoid the copy if same size block */
262: if (was_alloced &&
263: nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP)
264: return(cp);
265: if ((res = malloc(nbytes)) == NULL)
266: return (NULL);
267: if (cp != res) /* common optimization */
268: bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
269: if (was_alloced)
270: free(cp);
271: return (res);
272: }
273:
274: /*
275: * Search ``srchlen'' elements of each free list for a block whose
276: * header starts at ``freep''. If srchlen is -1 search the whole list.
277: * Return bucket number, or -1 if not found.
278: */
279: static
280: findbucket(freep, srchlen)
281: union overhead *freep;
282: int srchlen;
283: {
284: register union overhead *p;
285: register int i, j;
286:
287: for (i = 0; i < NBUCKETS; i++) {
288: j = 0;
289: for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
290: if (p == freep)
291: return (i);
292: j++;
293: }
294: }
295: return (-1);
296: }
297:
298: #ifdef MSTATS
299: /*
300: * mstats - print out statistics about malloc
301: *
302: * Prints two lines of numbers, one showing the length of the free list
303: * for each size category, the second showing the number of mallocs -
304: * frees for each size category.
305: */
306: mstats(s)
307: char *s;
308: {
309: register int i, j;
310: register union overhead *p;
311: int totfree = 0,
312: totused = 0;
313:
314: fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
315: for (i = 0; i < NBUCKETS; i++) {
316: for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
317: ;
318: fprintf(stderr, " %d", j);
319: totfree += j * (1 << (i + 3));
320: }
321: fprintf(stderr, "\nused:\t");
322: for (i = 0; i < NBUCKETS; i++) {
323: fprintf(stderr, " %d", nmalloc[i]);
324: totused += nmalloc[i] * (1 << (i + 3));
325: }
326: fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
327: totused, totfree);
328: }
329: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.