Annotation of src/usr.bin/patch/malloc.c, Revision 1.3
1.3 ! mpech 1: /* * $OpenBSD: malloc.c,v 1.2 1996/06/10 11:21:29 niklas Exp $*/
1.1 deraadt 2: /*
3: * from: @(#)nmalloc.c 1 (Caltech) 2/21/82
4: *
5: * U of M Modified: 20 Jun 1983 ACT: strange hacks for Emacs
6: *
7: * Nov 1983, Mike@BRL, Added support for 4.1C/4.2 BSD.
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
11: * that don't exactly fit are passed up to the next larger size. In this
12: * implementation, the available sizes are (2^n)-4 (or -16) bytes long.
13: * This is designed for use in a program that uses vast quantities of
14: * memory, but bombs when it runs out. To make it a little better, it
15: * warns the user when he starts to get near the end.
16: *
17: * June 84, ACT: modified rcheck code to check the range given to malloc,
18: * rather than the range determined by the 2-power used.
19: *
20: * Jan 85, RMS: calls malloc_warning to issue warning on nearly full.
21: * No longer Emacs-specific; can serve as all-purpose malloc for GNU.
22: * You should call malloc_init to reinitialize after loading dumped Emacs.
23: * Call malloc_stats to get info on memory stats if MSTATS turned on.
24: * realloc knows how to return same block given, just changing its size,
25: * if the power of 2 is correct.
26: */
27:
28: /*
29: * nextf[i] is the pointer to the next free block of size 2^(i+3). The
30: * smallest allocatable block is 8 bytes. The overhead information will
31: * go in the first int of the block, and the returned pointer will point
32: * to the second.
33: *
34: #ifdef MSTATS
35: * nmalloc[i] is the difference between the number of mallocs and frees
36: * for a given block size.
37: #endif /* MSTATS */
38: */
39:
40: #define ISALLOC ((char) 0xf7) /* magic byte that implies allocation */
41: #define ISFREE ((char) 0x54) /* magic byte that implies free block */
42: /* this is for error checking only */
43:
44: extern char etext;
45:
46: /* end of the program; can be changed by calling init_malloc */
47: static char *endofpure = &etext;
48:
49: #ifdef MSTATS
50: static int nmalloc[30];
51: static int nmal, nfre;
52: #endif /* MSTATS */
53:
54: /* If range checking is not turned on, all we have is a flag indicating
55: whether memory is allocated, an index in nextf[], and a size field; to
56: realloc() memory we copy either size bytes or 1<<(index+3) bytes depending
57: on whether the former can hold the exact size (given the value of
58: 'index'). If range checking is on, we always need to know how much space
59: is allocated, so the 'size' field is never used. */
60:
61: struct mhead {
62: char mh_alloc; /* ISALLOC or ISFREE */
63: char mh_index; /* index in nextf[] */
64: /* Remainder are valid only when block is allocated */
65: unsigned short mh_size; /* size, if < 0x10000 */
66: #ifdef rcheck
67: unsigned mh_nbytes; /* number of bytes allocated */
68: int mh_magic4; /* should be == MAGIC4 */
69: #endif /* rcheck */
70: };
71:
72: /* Access free-list pointer of a block.
73: It is stored at block + 4.
74: This is not a field in the mhead structure
75: because we want sizeof (struct mhead)
76: to describe the overhead for when the block is in use,
77: and we do not want the free-list pointer to count in that. */
78:
79: #define CHAIN(a) \
80: (*(struct mhead **) (sizeof (char *) + (char *) (a)))
81:
82: #ifdef rcheck
83:
84: /* To implement range checking, we write magic values in at the beginning and
85: end of each allocated block, and make sure they are undisturbed whenever a
86: free or a realloc occurs. */
87: /* Written in each of the 4 bytes following the block's real space */
88: #define MAGIC1 0x55
89: /* Written in the 4 bytes before the block's real space */
90: #define MAGIC4 0x55555555
91: #define ASSERT(p) if (!(p)) botch("p"); else
92: static
93: botch(s)
94: char *s;
95: {
96:
97: printf("assertion botched: %s\n", s);
98: abort();
99: }
100: #define EXTRA 4 /* 4 bytes extra for MAGIC1s */
101: #else
102: #define ASSERT(p)
103: #define EXTRA 0
104: #endif /* rcheck */
105:
106: /* nextf[i] is free list of blocks of size 2**(i + 3) */
107:
108: static struct mhead *nextf[30];
109:
110: #ifdef M_WARN
111: /* Number of bytes of writable memory we can expect to be able to get */
112: static int lim_data;
113: /* Level number of warnings already issued.
114: 0 -- no warnings issued.
115: 1 -- 75% warning already issued.
116: 2 -- 85% warning already issued.
117: */
118: static int warnlevel;
119: #endif /* M_WARN */
120:
121: /* nonzero once initial bunch of free blocks made */
122: static int gotpool;
123:
124: /* Cause reinitialization based on job parameters;
125: also declare where the end of pure storage is. */
126: malloc_init (end)
127: char *end; {
128: endofpure = end;
129: #ifdef M_WARN
130: lim_data = 0;
131: warnlevel = 0;
132: #endif /* M_WARN */
133: }
134:
135: static
136: morecore (nu) /* ask system for more memory */
1.3 ! mpech 137: int nu; { /* size index to get more of */
1.1 deraadt 138: char *sbrk ();
1.3 ! mpech 139: char *cp;
! 140: int nblks;
! 141: int siz;
1.1 deraadt 142:
143: #ifdef M_WARN
144: #ifndef BSD42
145: #ifdef USG
146: extern long ulimit ();
147: if (lim_data == 0) /* find out how much we can get */
148: lim_data = ulimit (3, 0) - TEXT_START;
149: #else /*HMS: was endif */
150: if (lim_data == 0) /* find out how much we can get */
151: lim_data = vlimit (LIM_DATA, -1);
152: #endif /* USG */ /HMS:* was not here */
153: #else
154: if (lim_data == 0) {
155: struct rlimit XXrlimit;
156:
157: getrlimit (RLIMIT_DATA, &XXrlimit);
158: lim_data = XXrlimit.rlim_cur;} /* soft limit */
159: #endif /* BSD42 */
160: #endif /* M_WARN */
161:
162: /* On initial startup, get two blocks of each size up to 1k bytes */
163: if (!gotpool)
164: getpool (), getpool (), gotpool = 1;
165:
166: /* Find current end of memory and issue warning if getting near max */
167:
168: cp = sbrk (0);
169: siz = cp - endofpure;
170: #ifdef M_WARN
171: switch (warnlevel) {
172: case 0:
173: if (siz > (lim_data / 4) * 3) {
174: warnlevel++;
175: malloc_warning ("Warning: past 75% of memory limit");}
176: break;
177: case 1:
178: if (siz > (lim_data / 20) * 17) {
179: warnlevel++;
180: malloc_warning ("Warning: past 85% of memory limit");}
181: break;
182: case 2:
183: if (siz > (lim_data / 20) * 19) {
184: warnlevel++;
185: malloc_warning ("Warning: past 95% of memory limit");}
186: break;}
187: #endif /* M_WARN */
188:
189: if ((int) cp & 0x3ff) /* land on 1K boundaries */
190: sbrk (1024 - ((int) cp & 0x3ff));
191:
192: /* Take at least 2k, and figure out how many blocks of the desired size we're about to get */
193: nblks = 1;
194: if ((siz = nu) < 8)
195: nblks = 1 << ((siz = 8) - nu);
196:
197: if ((cp = sbrk (1 << (siz + 3))) == (char *) -1)
198: return; /* no more room! */
199: if ((int) cp & 7) { /* shouldn't happen, but just in case */
200: cp = (char *) (((int) cp + 8) & ~7);
201: nblks--;}
202:
203: /* save new header and link the nblks blocks together */
204: nextf[nu] = (struct mhead *) cp;
205: siz = 1 << (nu + 3);
206: while (1) {
207: ((struct mhead *) cp) -> mh_alloc = ISFREE;
208: ((struct mhead *) cp) -> mh_index = nu;
209: if (--nblks <= 0) break;
210: CHAIN ((struct mhead *) cp) = (struct mhead *) (cp + siz);
211: cp += siz;}
212: /* CHAIN ((struct mhead *) cp) = 0; /* since sbrk() returns cleared core, this is already set */
213: }
214:
215: static
216: getpool () {
1.3 ! mpech 217: int nu;
! 218: char *cp = sbrk (0);
1.1 deraadt 219:
220: if ((int) cp & 0x3ff) /* land on 1K boundaries */
221: sbrk (1024 - ((int) cp & 0x3ff));
222:
223: /* Get 2k of storage */
224:
225: cp = sbrk (04000);
226: if (cp == (char *) -1)
227: return;
228:
229: /* Divide it into an initial 8-word block
230: plus one block of size 2**nu for nu = 3 ... 10. */
231:
232: CHAIN (cp) = nextf[0];
233: nextf[0] = (struct mhead *) cp;
234: ((struct mhead *) cp) -> mh_alloc = ISFREE;
235: ((struct mhead *) cp) -> mh_index = 0;
236: cp += 8;
237:
238: for (nu = 0; nu < 7; nu++) {
239: CHAIN (cp) = nextf[nu];
240: nextf[nu] = (struct mhead *) cp;
241: ((struct mhead *) cp) -> mh_alloc = ISFREE;
242: ((struct mhead *) cp) -> mh_index = nu;
243: cp += 8 << nu;}}
244:
245: char *
246: malloc (n) /* get a block */
247: unsigned n; {
1.3 ! mpech 248: struct mhead *p;
! 249: unsigned int nbytes;
! 250: int nunits = 0;
1.1 deraadt 251:
252: /* Figure out how many bytes are required, rounding up to the nearest
253: multiple of 4, then figure out which nextf[] area to use */
254: nbytes = (n + sizeof *p + EXTRA + 3) & ~3;
255: {
1.3 ! mpech 256: unsigned int shiftr = (nbytes - 1) >> 2;
1.1 deraadt 257:
258: while (shiftr >>= 1)
259: nunits++;
260: }
261:
262: /* If there are no blocks of the appropriate size, go get some */
263: /* COULD SPLIT UP A LARGER BLOCK HERE ... ACT */
264: if (nextf[nunits] == 0)
265: morecore (nunits);
266:
267: /* Get one block off the list, and set the new list head */
268: if ((p = nextf[nunits]) == 0)
269: return 0;
270: nextf[nunits] = CHAIN (p);
271:
272: /* Check for free block clobbered */
273: /* If not for this check, we would gobble a clobbered free chain ptr */
274: /* and bomb out on the NEXT allocate of this size block */
275: if (p -> mh_alloc != ISFREE || p -> mh_index != nunits)
276: #ifdef rcheck
277: botch ("block on free list clobbered");
278: #else
279: abort ();
280: #endif /* rcheck */
281:
282: /* Fill in the info, and if range checking, set up the magic numbers */
283: p -> mh_alloc = ISALLOC;
284: #ifdef rcheck
285: p -> mh_nbytes = n;
286: p -> mh_magic4 = MAGIC4;
287: {
1.3 ! mpech 288: char *m = (char *) (p + 1) + n;
1.1 deraadt 289:
290: *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1;
291: }
292: #else
293: p -> mh_size = n;
294: #endif /* rcheck */
295: #ifdef MSTATS
296: nmalloc[nunits]++;
297: nmal++;
298: #endif /* MSTATS */
299: return (char *) (p + 1);}
300:
301: free (mem)
302: char *mem; {
1.3 ! mpech 303: struct mhead *p;
1.1 deraadt 304: {
1.3 ! mpech 305: char *ap = mem;
1.1 deraadt 306:
307: ASSERT (ap != 0);
308: p = (struct mhead *) ap - 1;
309: ASSERT (p -> mh_alloc == ISALLOC);
310: #ifdef rcheck
311: ASSERT (p -> mh_magic4 == MAGIC4);
312: ap += p -> mh_nbytes;
313: ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1);
314: ASSERT (*ap++ == MAGIC1); ASSERT (*ap == MAGIC1);
315: #endif /* rcheck */
316: }
317: {
1.3 ! mpech 318: int nunits = p -> mh_index;
1.1 deraadt 319:
320: ASSERT (nunits <= 29);
321: p -> mh_alloc = ISFREE;
322: CHAIN (p) = nextf[nunits];
323: nextf[nunits] = p;
324: #ifdef MSTATS
325: nmalloc[nunits]--;
326: nfre++;
327: #endif /* MSTATS */
328: }
329: }
330:
331: char *
332: realloc (mem, n)
333: char *mem;
1.3 ! mpech 334: unsigned n; {
! 335: struct mhead *p;
! 336: unsigned int tocopy;
! 337: int nbytes;
! 338: int nunits;
1.1 deraadt 339:
340: if ((p = (struct mhead *) mem) == 0)
341: return malloc (n);
342: p--;
343: nunits = p -> mh_index;
344: ASSERT (p -> mh_alloc == ISALLOC);
345: #ifdef rcheck
346: ASSERT (p -> mh_magic4 == MAGIC4);
347: {
1.3 ! mpech 348: char *m = mem + (tocopy = p -> mh_nbytes);
1.1 deraadt 349: ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1);
350: ASSERT (*m++ == MAGIC1); ASSERT (*m == MAGIC1);
351: }
352: #else
353: if (p -> mh_index >= 13)
354: tocopy = (1 << (p -> mh_index + 3)) - sizeof *p;
355: else
356: tocopy = p -> mh_size;
357: #endif /* rcheck */
358:
359: /* See if desired size rounds to same power of 2 as actual size. */
360: nbytes = (n + sizeof *p + EXTRA + 7) & ~7;
361:
362: /* If ok, use the same block, just marking its size as changed. */
363: if (nbytes > (4 << nunits) && nbytes <= (8 << nunits)) {
364: #ifdef rcheck
1.3 ! mpech 365: char *m = mem + tocopy;
1.1 deraadt 366: *m++ = 0; *m++ = 0; *m++ = 0; *m++ = 0;
367: p-> mh_nbytes = n;
368: m = mem + n;
369: *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1;
370: #else
371: p -> mh_size = n;
372: #endif /* rcheck */
373: return mem;}
374:
375: if (n < tocopy)
376: tocopy = n;
377: {
1.3 ! mpech 378: char *new;
1.1 deraadt 379: void bcopy(); /*HMS: here? */
380:
381: if ((new = malloc (n)) == 0)
382: return 0;
383: bcopy (mem, new, tocopy);
384: free (mem);
385: return new;
386: }
387: }
388:
389: #ifdef MSTATS
390: /* Return statistics describing allocation of blocks of size 2**n. */
391:
392: struct mstats_value {
393: int blocksize;
394: int nfree;
395: int nused;
396: };
397:
398: struct mstats_value
399: malloc_stats (size)
400: int size; {
401: struct mstats_value v;
1.3 ! mpech 402: int i;
! 403: struct mhead *p;
1.1 deraadt 404:
405: v.nfree = 0;
406:
407: if (size < 0 || size >= 30) {
408: v.blocksize = 0;
409: v.nused = 0;
410: return v;}
411:
412: v.blocksize = 1 << (size + 3);
413: v.nused = nmalloc[size];
414:
415: for (p = nextf[size]; p; p = CHAIN (p))
416: v.nfree++;
417:
418: return v;}
419: #endif
420:
421: /* how much space is available? */
422:
423: unsigned freespace() {
1.3 ! mpech 424: int i, j;
! 425: struct mhead *p;
! 426: unsigned space = 0;
1.1 deraadt 427: int local; /* address only is used */
428:
429: space = (char *)&local - sbrk(0); /* stack space */
430:
431: for (i = 0; i < 30; i++) {
432: for (j = 0, p = nextf[i]; p; p = CHAIN (p), j++) ;
433: space += j * (1 << (i + 3));}
434:
435: return(space);}
436:
437: /* How big is this cell? */
438:
439: unsigned mc_size(cp)
440: char *cp;{
1.3 ! mpech 441: struct mhead *p;
1.1 deraadt 442:
443: if ((p = (struct mhead *) cp) == 0) {
444: /*HMS? */
445: }
446: p--;
447: #ifdef rcheck
448: return p -> mh_nbytes;
449: #else
450: return (1 << (p -> mh_index + 3)) - sizeof *p;
451: /**/
452: /* if (p -> mh_index >= 13)
453: /* return (1 << (p -> mh_index + 3)) - sizeof *p;
454: /* else
455: /* return p -> mh_size;
456: /**/
457: #endif /* rcheck */
458: }
459:
460: /*HMS: Really should use memcpy, if available... */
461:
462: void bcopy(source, dest, len)
1.3 ! mpech 463: char *source, *dest;
! 464: len; {
! 465: i;
1.1 deraadt 466:
467: for (i = 0; i < len; i++)
468: *dest++ = *source++;}
![[BACK]](/icons/back.gif){kind=icon}
Return to malloc.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / patch