Mercurial > hg > Applications > mh

comparison miscellany/patch-2.0.12u8/malloc.c @ 0:bce86c4163a3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial revision
author kono
date Mon, 18 Apr 2005 23:46:02 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:bce86c4163a3
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
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
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
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++;}