![[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 [Power 6/32 Unix Tahoe 4.2BSD] / cci / usr / src / lib / libc / gen|
Return to malloc.c CVS log | Up to [Power 6/32 Unix Tahoe 4.2BSD] / cci / usr / src / lib / libc / gen |
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: op->ov_next = NULL;
184: }
185:
186: free(cp)
187: char *cp;
188: {
189: register int size;
190: register union overhead *op;
191:
192: if (cp == NULL)
193: return;
194: op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
195: #ifdef debug
196: ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */
197: #else
198: if (op->ov_magic != MAGIC)
199: return; /* sanity */
200: #endif
201: #ifdef RCHECK
202: ASSERT(op->ov_rmagic == RMAGIC);
203: if (op->ov_index <= 13)
204: ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
205: #endif
206: ASSERT(op->ov_index < NBUCKETS);
207: size = op->ov_index;
208: op->ov_next = nextf[size];
209: nextf[size] = op;
210: #ifdef MSTATS
211: nmalloc[size]--;
212: #endif
213: }
214:
215: /*
216: * When a program attempts "storage compaction" as mentioned in the
217: * old malloc man page, it realloc's an already freed block. Usually
218: * this is the last block it freed; occasionally it might be farther
219: * back. We have to search all the free lists for the block in order
220: * to determine its bucket: 1st we make one pass thru the lists
221: * checking only the first block in each; if that fails we search
222: * ``realloc_srchlen'' blocks in each list for a match (the variable
223: * is extern so the caller can modify it). If that fails we just copy
224: * however many bytes was given to realloc() and hope it's not huge.
225: */
226: int realloc_srchlen = -1; /* 4 should be plenty, -1 =>'s whole list */
227:
228: char *
229: realloc(cp, nbytes)
230: char *cp;
231: unsigned nbytes;
232: {
233: register u_int onb;
234: union overhead *op;
235: char *res;
236: register int i;
237: int was_alloced = 0;
238:
239: if (cp == NULL)
240: return (malloc(nbytes));
241: op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
242: if (op->ov_magic == MAGIC) {
243: was_alloced++;
244: i = op->ov_index;
245: } else {
246: /*
247: * Already free, doing "compaction".
248: *
249: * Search for the old block of memory on the
250: * free list. First, check the most common
251: * case (last element free'd), then (this failing)
252: * the last ``realloc_srchlen'' items free'd.
253: * If all lookups fail, then assume the size of
254: * the memory block being realloc'd is the
255: * smallest possible.
256: */
257: if ((i = findbucket(op, 1)) < 0 &&
258: (i = findbucket(op, realloc_srchlen)) < 0)
259: i = 0;
260: }
261: onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
262: /* avoid the copy if same size block */
263: if (was_alloced &&
264: nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP)
265: return(cp);
266: if ((res = malloc(nbytes)) == NULL)
267: return (NULL);
268: if (cp != res) /* common optimization */
269: bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
270: if (was_alloced)
271: free(cp);
272: return (res);
273: }
274:
275: /*
276: * Search ``srchlen'' elements of each free list for a block whose
277: * header starts at ``freep''. If srchlen is -1 search the whole list.
278: * Return bucket number, or -1 if not found.
279: */
280: static
281: findbucket(freep, srchlen)
282: union overhead *freep;
283: int srchlen;
284: {
285: register union overhead *p;
286: register int i, j;
287:
288: for (i = 0; i < NBUCKETS; i++) {
289: j = 0;
290: for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
291: if (p == freep)
292: return (i);
293: j++;
294: }
295: }
296: return (-1);
297: }
298:
299: #ifdef MSTATS
300: /*
301: * mstats - print out statistics about malloc
302: *
303: * Prints two lines of numbers, one showing the length of the free list
304: * for each size category, the second showing the number of mallocs -
305: * frees for each size category.
306: */
307: mstats(s)
308: char *s;
309: {
310: register int i, j;
311: register union overhead *p;
312: int totfree = 0,
313: totused = 0;
314:
315: fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
316: for (i = 0; i < NBUCKETS; i++) {
317: for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
318: ;
319: fprintf(stderr, " %d", j);
320: totfree += j * (1 << (i + 3));
321: }
322: fprintf(stderr, "\nused:\t");
323: for (i = 0; i < NBUCKETS; i++) {
324: fprintf(stderr, " %d", nmalloc[i]);
325: totused += nmalloc[i] * (1 << (i + 3));
326: }
327: fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
328: totused, totfree);
329: }
330: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.