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