![[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 / contrib / emacs / src|
Return to malloc.c CVS log | Up to [CSRG BSD Unix] / 43BSD / contrib / emacs / src |
1.1 root 1: /* Dynamic memory allocation for GNU.
2: Copyright (C) 1985 Richard M. Stallman,
3: based mostly on the public domain work of others.
4:
5: This program is distributed in the hope that it will be useful,
6: but without any warranty. No author or distributor
7: accepts responsibility to anyone for the consequences of using it
8: or for whether it serves any particular purpose or works at all,
9: unless he says so in writing.
10:
11: Permission is granted to anyone to distribute verbatim copies
12: of this program's source code as received, in any medium, provided that
13: the copyright notice, the nonwarraty notice above
14: and this permission notice are preserved,
15: and that the distributor grants the recipient all rights
16: for further redistribution as permitted by this notice,
17: and informs him of these rights.
18:
19: Permission is granted to distribute modified versions of this
20: program's source code, or of portions of it, under the above
21: conditions, plus the conditions that all changed files carry
22: prominent notices stating who last changed them and that the
23: derived material, including anything packaged together with it and
24: conceptually functioning as a modification of it rather than an
25: application of it, is in its entirety subject to a permission
26: notice identical to this one.
27:
28: Permission is granted to distribute this program (verbatim or
29: as modified) in compiled or executable form, provided verbatim
30: redistribution is permitted as stated above for source code, and
31: A. it is accompanied by the corresponding machine-readable
32: source code, under the above conditions, or
33: B. it is accompanied by a written offer, with no time limit,
34: to distribute the corresponding machine-readable source code,
35: under the above conditions, to any one, in return for reimbursement
36: of the cost of distribution. Verbatim redistribution of the
37: written offer must be permitted. Or,
38: C. it is distributed by someone who received only the
39: compiled or executable form, and is accompanied by a copy of the
40: written offer of source code which he received along with it.
41:
42: Permission is granted to distribute this program (verbatim or as modified)
43: in executable form as part of a larger system provided that the source
44: code for this program, including any modifications used,
45: is also distributed or offered as stated in the preceding paragraph.
46:
47: In other words, you are welcome to use, share and improve this program.
48: You are forbidden to forbid anyone else to use, share and improve
49: what you give them. Help stamp out software-hoarding! */
50:
51:
52: /*
53: * @(#)nmalloc.c 1 (Caltech) 2/21/82
54: *
55: * U of M Modified: 20 Jun 1983 ACT: strange hacks for Emacs
56: *
57: * Nov 1983, Mike@BRL, Added support for 4.1C/4.2 BSD.
58: *
59: * This is a very fast storage allocator. It allocates blocks of a small
60: * number of different sizes, and keeps free lists of each size. Blocks
61: * that don't exactly fit are passed up to the next larger size. In this
62: * implementation, the available sizes are (2^n)-4 (or -16) bytes long.
63: * This is designed for use in a program that uses vast quantities of
64: * memory, but bombs when it runs out. To make it a little better, it
65: * warns the user when he starts to get near the end.
66: *
67: * June 84, ACT: modified rcheck code to check the range given to malloc,
68: * rather than the range determined by the 2-power used.
69: *
70: * Jan 85, RMS: calls malloc_warning to issue warning on nearly full.
71: * No longer Emacs-specific; can serve as all-purpose malloc for GNU.
72: * You should call malloc_init to reinitialize after loading dumped Emacs.
73: * Call malloc_stats to get info on memory stats if MSTATS turned on.
74: * realloc knows how to return same block given, just changing its size,
75: * if the power of 2 is correct.
76: */
77:
78: /*
79: * nextf[i] is the pointer to the next free block of size 2^(i+3). The
80: * smallest allocatable block is 8 bytes. The overhead information will
81: * go in the first int of the block, and the returned pointer will point
82: * to the second.
83: *
84: #ifdef MSTATS
85: * nmalloc[i] is the difference between the number of mallocs and frees
86: * for a given block size.
87: #endif /* MSTATS */
88:
89: #ifdef emacs
90: #include "config.h"
91: #endif /* emacs */
92:
93: #include <sys/param.h>
94:
95: /* Determine which kind of system this is. */
96: #include <signal.h>
97: #ifndef SIGTSTP
98: #define USG
99: #else /* SIGTSTP */
100: #ifdef SIGIO
101: #define BSD42
102: #endif /* SIGIO */
103: #endif /* SIGTSTP */
104:
105: #ifndef BSD42
106: #ifndef USG
107: #include <sys/vlimit.h> /* warn the user when near the end */
108: #endif
109: #else /* if BSD42 */
110: #include <sys/time.h>
111: #include <sys/resource.h>
112: #endif /* BSD42 */
113:
114:
115: #if defined (BSD4_1) || defined (USG)
116: #ifdef EXEC_PAGESIZE
117: #define getpagesize() EXEC_PAGESIZE
118: #else
119: #ifdef NBPG
120: #define getpagesize() NBPG * CLSIZE
121: #ifndef CLSIZE
122: #define CLSIZE 1
123: #endif /* no CLSIZE */
124: #else /* no NBPG */
125: #define getpagesize() NBPC
126: #endif /* no NBPG */
127: #endif /* no EXEC_PAGESIZE */
128: #endif /* BSD4_1 or USG */
129:
130:
131: #define ISALLOC ((char) 0xf7) /* magic byte that implies allocation */
132: #define ISFREE ((char) 0x54) /* magic byte that implies free block */
133: /* this is for error checking only */
134: #define ISMEMALIGN ((char) 0xd6) /* Stored before the value returned by
135: memalign, with the rest of the word
136: being the distance to the true
137: beginning of the block. */
138:
139: extern char etext;
140: extern char *start_of_data ();
141:
142: /* These two are for user programs to look at, when they are interested. */
143:
144: int malloc_sbrk_used; /* amount of data space used now */
145: int malloc_sbrk_unused; /* amount more we can have */
146:
147: /* start of data space; can be changed by calling init_malloc */
148: static char *data_space_start;
149:
150: #ifdef MSTATS
151: static int nmalloc[30];
152: static int nmal, nfre;
153: #endif /* MSTATS */
154:
155: /* If range checking is not turned on, all we have is a flag indicating
156: whether memory is allocated, an index in nextf[], and a size field; to
157: realloc() memory we copy either size bytes or 1<<(index+3) bytes depending
158: on whether the former can hold the exact size (given the value of
159: 'index'). If range checking is on, we always need to know how much space
160: is allocated, so the 'size' field is never used. */
161:
162: struct mhead {
163: char mh_alloc; /* ISALLOC or ISFREE */
164: char mh_index; /* index in nextf[] */
165: /* Remainder are valid only when block is allocated */
166: unsigned short mh_size; /* size, if < 0x10000 */
167: #ifdef rcheck
168: unsigned mh_nbytes; /* number of bytes allocated */
169: int mh_magic4; /* should be == MAGIC4 */
170: #endif /* rcheck */
171: };
172:
173: /* Access free-list pointer of a block.
174: It is stored at block + 4.
175: This is not a field in the mhead structure
176: because we want sizeof (struct mhead)
177: to describe the overhead for when the block is in use,
178: and we do not want the free-list pointer to count in that. */
179:
180: #define CHAIN(a) \
181: (*(struct mhead **) (sizeof (char *) + (char *) (a)))
182:
183: #ifdef rcheck
184:
185: /* To implement range checking, we write magic values in at the beginning and
186: end of each allocated block, and make sure they are undisturbed whenever a
187: free or a realloc occurs. */
188: /* Written in each of the 4 bytes following the block's real space */
189: #define MAGIC1 0x55
190: /* Written in the 4 bytes before the block's real space */
191: #define MAGIC4 0x55555555
192: #define ASSERT(p) if (!(p)) botch("p"); else
193: #define EXTRA 4 /* 4 bytes extra for MAGIC1s */
194: #else
195: #define ASSERT(p)
196: #define EXTRA 0
197: #endif /* rcheck */
198:
199:
200: /* nextf[i] is free list of blocks of size 2**(i + 3) */
201:
202: static struct mhead *nextf[30];
203:
204: /* Number of bytes of writable memory we can expect to be able to get */
205: static int lim_data;
206: /* Level number of warnings already issued.
207: 0 -- no warnings issued.
208: 1 -- 75% warning already issued.
209: 2 -- 85% warning already issued.
210: */
211: static int warnlevel;
212:
213: /* nonzero once initial bunch of free blocks made */
214: static int gotpool;
215:
216: /* Cause reinitialization based on job parameters;
217: also declare where the end of pure storage is. */
218: malloc_init (start)
219: char *start;
220: {
221: data_space_start = start;
222: lim_data = 0;
223: warnlevel = 0;
224: }
225:
226: static
227: morecore (nu) /* ask system for more memory */
228: register int nu; /* size index to get more of */
229: {
230: char *sbrk ();
231: register char *cp;
232: register int nblks;
233: register int siz;
234:
235: if (!data_space_start)
236: {
237: #if defined(USG) && defined (emacs)
238: data_space_start = start_of_data ();
239: #else /* not USG, or not Emacs */
240: data_space_start = &etext;
241: #endif /* not USG, or not Emacs */
242: }
243:
244: if (lim_data == 0)
245: get_lim_data ();
246:
247: /* On initial startup, get two blocks of each size up to 1k bytes */
248: if (!gotpool)
249: getpool (), getpool (), gotpool = 1;
250:
251: /* Find current end of memory and issue warning if getting near max */
252:
253: cp = sbrk (0);
254: siz = cp - data_space_start;
255: malloc_sbrk_used = siz;
256: malloc_sbrk_unused = lim_data - siz;
257:
258: switch (warnlevel)
259: {
260: case 0:
261: if (siz > (lim_data / 4) * 3)
262: {
263: warnlevel++;
264: malloc_warning ("Warning: past 75% of memory limit");
265: }
266: break;
267: case 1:
268: if (siz > (lim_data / 20) * 17)
269: {
270: warnlevel++;
271: malloc_warning ("Warning: past 85% of memory limit");
272: }
273: break;
274: case 2:
275: if (siz > (lim_data / 20) * 19)
276: {
277: warnlevel++;
278: malloc_warning ("Warning: past 95% of memory limit");
279: }
280: break;
281: }
282:
283: if ((int) cp & 0x3ff) /* land on 1K boundaries */
284: sbrk (1024 - ((int) cp & 0x3ff));
285:
286: /* Take at least 2k, and figure out how many blocks of the desired size
287: we're about to get */
288: nblks = 1;
289: if ((siz = nu) < 8)
290: nblks = 1 << ((siz = 8) - nu);
291:
292: if ((cp = sbrk (1 << (siz + 3))) == (char *) -1)
293: return; /* no more room! */
294: if ((int) cp & 7)
295: { /* shouldn't happen, but just in case */
296: cp = (char *) (((int) cp + 8) & ~7);
297: nblks--;
298: }
299:
300: /* save new header and link the nblks blocks together */
301: nextf[nu] = (struct mhead *) cp;
302: siz = 1 << (nu + 3);
303: while (1)
304: {
305: ((struct mhead *) cp) -> mh_alloc = ISFREE;
306: ((struct mhead *) cp) -> mh_index = nu;
307: if (--nblks <= 0) break;
308: CHAIN ((struct mhead *) cp) = (struct mhead *) (cp + siz);
309: cp += siz;
310: }
311: /* CHAIN ((struct mhead *) cp) = 0; */
312: /* since sbrk() returns cleared core, this is already set */
313: }
314:
315: static
316: getpool ()
317: {
318: register int nu;
319: register char *cp = sbrk (0);
320:
321: if ((int) cp & 0x3ff) /* land on 1K boundaries */
322: sbrk (1024 - ((int) cp & 0x3ff));
323:
324: /* Get 2k of storage */
325:
326: cp = sbrk (04000);
327: if (cp == (char *) -1)
328: return;
329:
330: /* Divide it into an initial 8-word block
331: plus one block of size 2**nu for nu = 3 ... 10. */
332:
333: CHAIN (cp) = nextf[0];
334: nextf[0] = (struct mhead *) cp;
335: ((struct mhead *) cp) -> mh_alloc = ISFREE;
336: ((struct mhead *) cp) -> mh_index = 0;
337: cp += 8;
338:
339: for (nu = 0; nu < 7; nu++)
340: {
341: CHAIN (cp) = nextf[nu];
342: nextf[nu] = (struct mhead *) cp;
343: ((struct mhead *) cp) -> mh_alloc = ISFREE;
344: ((struct mhead *) cp) -> mh_index = nu;
345: cp += 8 << nu;
346: }
347: }
348:
349: char *
350: malloc (n) /* get a block */
351: unsigned n;
352: {
353: register struct mhead *p;
354: register unsigned int nbytes;
355: register int nunits = 0;
356:
357: /* Figure out how many bytes are required, rounding up to the nearest
358: multiple of 4, then figure out which nextf[] area to use */
359: nbytes = (n + sizeof *p + EXTRA + 3) & ~3;
360: {
361: register unsigned int shiftr = (nbytes - 1) >> 2;
362:
363: while (shiftr >>= 1)
364: nunits++;
365: }
366:
367: /* If there are no blocks of the appropriate size, go get some */
368: /* COULD SPLIT UP A LARGER BLOCK HERE ... ACT */
369: if (nextf[nunits] == 0)
370: morecore (nunits);
371:
372: /* Get one block off the list, and set the new list head */
373: if ((p = nextf[nunits]) == 0)
374: return 0;
375: nextf[nunits] = CHAIN (p);
376:
377: /* Check for free block clobbered */
378: /* If not for this check, we would gobble a clobbered free chain ptr */
379: /* and bomb out on the NEXT allocate of this size block */
380: if (p -> mh_alloc != ISFREE || p -> mh_index != nunits)
381: #ifdef rcheck
382: botch ("block on free list clobbered");
383: #else /* not rcheck */
384: abort ();
385: #endif /* not rcheck */
386:
387: /* Fill in the info, and if range checking, set up the magic numbers */
388: p -> mh_alloc = ISALLOC;
389: #ifdef rcheck
390: p -> mh_nbytes = n;
391: p -> mh_magic4 = MAGIC4;
392: {
393: register char *m = (char *) (p + 1) + n;
394:
395: *m++ = MAGIC1, *m++ = MAGIC1, *m++ = MAGIC1, *m = MAGIC1;
396: }
397: #else /* not rcheck */
398: p -> mh_size = n;
399: #endif /* not rcheck */
400: #ifdef MSTATS
401: nmalloc[nunits]++;
402: nmal++;
403: #endif /* MSTATS */
404: return (char *) (p + 1);
405: }
406:
407: free (mem)
408: char *mem;
409: {
410: register struct mhead *p;
411: {
412: register char *ap = mem;
413:
414: if (ap == 0)
415: return;
416:
417: p = (struct mhead *) ap - 1;
418: if (p -> mh_alloc == ISMEMALIGN)
419: {
420: ap -= p->mh_size;
421: p = (struct mhead *) ap - 1;
422: }
423:
424: if (p -> mh_alloc != ISALLOC)
425: abort ();
426:
427: #ifdef rcheck
428: ASSERT (p -> mh_magic4 == MAGIC4);
429: ap += p -> mh_nbytes;
430: ASSERT (*ap++ == MAGIC1); ASSERT (*ap++ == MAGIC1);
431: ASSERT (*ap++ == MAGIC1); ASSERT (*ap == MAGIC1);
432: #endif /* rcheck */
433: }
434: {
435: register int nunits = p -> mh_index;
436:
437: ASSERT (nunits <= 29);
438: p -> mh_alloc = ISFREE;
439: CHAIN (p) = nextf[nunits];
440: nextf[nunits] = p;
441: #ifdef MSTATS
442: nmalloc[nunits]--;
443: nfre++;
444: #endif /* MSTATS */
445: }
446: }
447:
448: char *
449: realloc (mem, n)
450: char *mem;
451: register unsigned n;
452: {
453: register struct mhead *p;
454: register unsigned int tocopy;
455: register int nbytes;
456: register int nunits;
457:
458: if ((p = (struct mhead *) mem) == 0)
459: return malloc (n);
460: p--;
461: nunits = p -> mh_index;
462: ASSERT (p -> mh_alloc == ISALLOC);
463: #ifdef rcheck
464: ASSERT (p -> mh_magic4 == MAGIC4);
465: {
466: register char *m = mem + (tocopy = p -> mh_nbytes);
467: ASSERT (*m++ == MAGIC1); ASSERT (*m++ == MAGIC1);
468: ASSERT (*m++ == MAGIC1); ASSERT (*m == MAGIC1);
469: }
470: #else /* not rcheck */
471: if (p -> mh_index >= 13)
472: tocopy = (1 << (p -> mh_index + 3)) - sizeof *p;
473: else
474: tocopy = p -> mh_size;
475: #endif /* not rcheck */
476:
477: /* See if desired size rounds to same power of 2 as actual size. */
478: nbytes = (n + sizeof *p + EXTRA + 7) & ~7;
479:
480: /* If ok, use the same block, just marking its size as changed. */
481: if (nbytes > (4 << nunits) && nbytes <= (8 << nunits))
482: {
483: #ifdef rcheck
484: register char *m = mem + tocopy;
485: *m++ = 0; *m++ = 0; *m++ = 0; *m++ = 0;
486: p-> mh_nbytes = n;
487: m = mem + n;
488: *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1; *m++ = MAGIC1;
489: #else /* not rcheck */
490: p -> mh_size = n;
491: #endif /* not rcheck */
492: return mem;
493: }
494:
495: if (n < tocopy)
496: tocopy = n;
497: {
498: register char *new;
499:
500: if ((new = malloc (n)) == 0)
501: return 0;
502: bcopy (mem, new, tocopy);
503: free (mem);
504: return new;
505: }
506: }
507:
508: char *
509: memalign (alignment, size)
510: unsigned alignment, size;
511: {
512: register char *ptr = malloc (size + alignment);
513: register char *aligned;
514: register struct mhead *p;
515:
516: if (ptr == 0)
517: return 0;
518: /* If entire block has the desired alignment, just accept it. */
519: if (((int) ptr & (alignment - 1)) == 0)
520: return ptr;
521: /* Otherwise, get address of byte in the block that has that alignment. */
522: aligned = (char *) (((int) ptr + alignment - 1) & -alignment);
523:
524: /* Store a suitable indication of how to free the block,
525: so that free can find the true beginning of it. */
526: p = (struct mhead *) aligned - 1;
527: p -> mh_size = aligned - ptr;
528: p -> mh_alloc = ISMEMALIGN;
529: return aligned;
530: }
531:
532: #ifndef HPUX
533: /* This runs into trouble with getpagesize on HPUX.
534: Patching out seems cleaner than the ugly fix needed. */
535: char *
536: valloc (size)
537: {
538: return memalign (getpagesize (), size);
539: }
540: #endif /* not HPUX */
541:
542: #ifdef MSTATS
543: /* Return statistics describing allocation of blocks of size 2**n. */
544:
545: struct mstats_value
546: {
547: int blocksize;
548: int nfree;
549: int nused;
550: };
551:
552: struct mstats_value
553: malloc_stats (size)
554: int size;
555: {
556: struct mstats_value v;
557: register int i;
558: register struct mhead *p;
559:
560: v.nfree = 0;
561:
562: if (size < 0 || size >= 30)
563: {
564: v.blocksize = 0;
565: v.nused = 0;
566: return v;
567: }
568:
569: v.blocksize = 1 << (size + 3);
570: v.nused = nmalloc[size];
571:
572: for (p = nextf[size]; p; p = CHAIN (p))
573: v.nfree++;
574:
575: return v;
576: }
577: #endif /* MSTATS */
578:
579: /*
580: * This function returns the total number of bytes that the process
581: * will be allowed to allocate via the sbrk(2) system call. On
582: * BSD systems this is the total space allocatable to stack and
583: * data. On USG systems this is the data space only.
584: */
585:
586: #ifdef USG
587:
588: get_lim_data ()
589: {
590: extern long ulimit ();
591:
592: lim_data = ulimit (3, 0);
593: lim_data -= (long) data_space_start;
594: }
595:
596: #else /* not USG */
597: #ifndef BSD42
598:
599: get_lim_data ()
600: {
601: lim_data = vlimit (LIM_DATA, -1);
602: }
603:
604: #else /* BSD42 */
605:
606: get_lim_data ()
607: {
608: struct rlimit XXrlimit;
609:
610: getrlimit (RLIMIT_DATA, &XXrlimit);
611: lim_data = XXrlimit.rlim_cur; /* soft limit */
612: }
613:
614: #endif /* BSD42 */
615: #endif /* not USG */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.