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