1 /*
2 * Copyright (c) 1983, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * %sccs.include.redist.c%
6 */
7
8 #if defined(LIBC_SCCS) && !defined(lint)
9 static char sccsid[] = "@(#)malloc.c 8.1 (Berkeley) 06/04/93";
10 #endif /* LIBC_SCCS and not lint */
11
12 /*
13 * malloc.c (Caltech) 2/21/82
14 * Chris Kingsley, kingsley@cit-20.
15 *
16 * This is a very fast storage allocator. It allocates blocks of a small
17 * number of different sizes, and keeps free lists of each size. Blocks that
18 * don't exactly fit are passed up to the next larger size. In this
19 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
20 * This is designed for use in a virtual memory environment.
21 */
22
23 #include <sys/types.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <unistd.h>
27
28 #define NULL 0
29
30 static void morecore();
31 static int findbucket();
32
33 /*
34 * The overhead on a block is at least 4 bytes. When free, this space
35 * contains a pointer to the next free block, and the bottom two bits must
36 * be zero. When in use, the first byte is set to MAGIC, and the second
37 * byte is the size index. The remaining bytes are for alignment.
38 * If range checking is enabled then a second word holds the size of the
39 * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
40 * The order of elements is critical: ov_magic must overlay the low order
41 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
42 */
43 union overhead {
44 union overhead *ov_next; /* when free */
45 struct {
46 u_char ovu_magic; /* magic number */
47 u_char ovu_index; /* bucket # */
48 #ifdef RCHECK
49 u_short ovu_rmagic; /* range magic number */
50 u_int ovu_size; /* actual block size */
51 #endif
52 } ovu;
53 #define ov_magic ovu.ovu_magic
54 #define ov_index ovu.ovu_index
55 #define ov_rmagic ovu.ovu_rmagic
56 #define ov_size ovu.ovu_size
57 };
58
59 #define MAGIC 0xef /* magic # on accounting info */
60 #define RMAGIC 0x5555 /* magic # on range info */
61
62 #ifdef RCHECK
63 #define RSLOP sizeof (u_short)
64 #else
65 #define RSLOP 0
66 #endif
67
68 /*
69 * nextf[i] is the pointer to the next free block of size 2^(i+3). The
70 * smallest allocatable block is 8 bytes. The overhead information
71 * precedes the data area returned to the user.
72 */
73 #define NBUCKETS 30
74 static union overhead *nextf[NBUCKETS];
75 extern char *sbrk();
76
77 static int pagesz; /* page size */
78 static int pagebucket; /* page size bucket */
79
80 #ifdef MSTATS
81 /*
82 * nmalloc[i] is the difference between the number of mallocs and frees
83 * for a given block size.
84 */
85 static u_int nmalloc[NBUCKETS];
86 #include <stdio.h>
87 #endif
88
89 #if defined(DEBUG) || defined(RCHECK)
90 #define ASSERT(p) if (!(p)) botch("p")
91 #include <stdio.h>
92 static
botch(s)93 botch(s)
94 char *s;
95 {
96 fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
97 (void) fflush(stderr); /* just in case user buffered it */
98 abort();
99 }
100 #else
101 #define ASSERT(p)
102 #endif
103
104 void *
malloc(nbytes)105 malloc(nbytes)
106 size_t nbytes;
107 {
108 register union overhead *op;
109 register int bucket, n;
110 register unsigned amt;
111
112 /*
113 * First time malloc is called, setup page size and
114 * align break pointer so all data will be page aligned.
115 */
116 if (pagesz == 0) {
117 pagesz = n = getpagesize();
118 op = (union overhead *)sbrk(0);
119 n = n - sizeof (*op) - ((int)op & (n - 1));
120 if (n < 0)
121 n += pagesz;
122 if (n) {
123 if (sbrk(n) == (char *)-1)
124 return (NULL);
125 }
126 bucket = 0;
127 amt = 8;
128 while (pagesz > amt) {
129 amt <<= 1;
130 bucket++;
131 }
132 pagebucket = bucket;
133 }
134 /*
135 * Convert amount of memory requested into closest block size
136 * stored in hash buckets which satisfies request.
137 * Account for space used per block for accounting.
138 */
139 if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
140 #ifndef RCHECK
141 amt = 8; /* size of first bucket */
142 bucket = 0;
143 #else
144 amt = 16; /* size of first bucket */
145 bucket = 1;
146 #endif
147 n = -(sizeof (*op) + RSLOP);
148 } else {
149 amt = pagesz;
150 bucket = pagebucket;
151 }
152 while (nbytes > amt + n) {
153 amt <<= 1;
154 if (amt == 0)
155 return (NULL);
156 bucket++;
157 }
158 /*
159 * If nothing in hash bucket right now,
160 * request more memory from the system.
161 */
162 if ((op = nextf[bucket]) == NULL) {
163 morecore(bucket);
164 if ((op = nextf[bucket]) == NULL)
165 return (NULL);
166 }
167 /* remove from linked list */
168 nextf[bucket] = op->ov_next;
169 op->ov_magic = MAGIC;
170 op->ov_index = bucket;
171 #ifdef MSTATS
172 nmalloc[bucket]++;
173 #endif
174 #ifdef RCHECK
175 /*
176 * Record allocated size of block and
177 * bound space with magic numbers.
178 */
179 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
180 op->ov_rmagic = RMAGIC;
181 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
182 #endif
183 return ((char *)(op + 1));
184 }
185
186 /*
187 * Allocate more memory to the indicated bucket.
188 */
189 static void
morecore(bucket)190 morecore(bucket)
191 int bucket;
192 {
193 register union overhead *op;
194 register int sz; /* size of desired block */
195 int amt; /* amount to allocate */
196 int nblks; /* how many blocks we get */
197
198 /*
199 * sbrk_size <= 0 only for big, FLUFFY, requests (about
200 * 2^30 bytes on a VAX, I think) or for a negative arg.
201 */
202 sz = 1 << (bucket + 3);
203 #ifdef DEBUG
204 ASSERT(sz > 0);
205 #else
206 if (sz <= 0)
207 return;
208 #endif
209 if (sz < pagesz) {
210 amt = pagesz;
211 nblks = amt / sz;
212 } else {
213 amt = sz + pagesz;
214 nblks = 1;
215 }
216 op = (union overhead *)sbrk(amt);
217 /* no more room! */
218 if ((int)op == -1)
219 return;
220 /*
221 * Add new memory allocated to that on
222 * free list for this hash bucket.
223 */
224 nextf[bucket] = op;
225 while (--nblks > 0) {
226 op->ov_next = (union overhead *)((caddr_t)op + sz);
227 op = (union overhead *)((caddr_t)op + sz);
228 }
229 }
230
231 void
free(cp)232 free(cp)
233 void *cp;
234 {
235 register int size;
236 register union overhead *op;
237
238 if (cp == NULL)
239 return;
240 op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
241 #ifdef DEBUG
242 ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */
243 #else
244 if (op->ov_magic != MAGIC)
245 return; /* sanity */
246 #endif
247 #ifdef RCHECK
248 ASSERT(op->ov_rmagic == RMAGIC);
249 ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
250 #endif
251 size = op->ov_index;
252 ASSERT(size < NBUCKETS);
253 op->ov_next = nextf[size]; /* also clobbers ov_magic */
254 nextf[size] = op;
255 #ifdef MSTATS
256 nmalloc[size]--;
257 #endif
258 }
259
260 /*
261 * When a program attempts "storage compaction" as mentioned in the
262 * old malloc man page, it realloc's an already freed block. Usually
263 * this is the last block it freed; occasionally it might be farther
264 * back. We have to search all the free lists for the block in order
265 * to determine its bucket: 1st we make one pass thru the lists
266 * checking only the first block in each; if that fails we search
267 * ``__realloc_srchlen'' blocks in each list for a match (the variable
268 * is extern so the caller can modify it). If that fails we just copy
269 * however many bytes was given to realloc() and hope it's not huge.
270 */
271 int __realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
272
273 void *
realloc(cp,nbytes)274 realloc(cp, nbytes)
275 void *cp;
276 size_t nbytes;
277 {
278 register u_int onb;
279 register int i;
280 union overhead *op;
281 char *res;
282 int was_alloced = 0;
283
284 if (cp == NULL)
285 return (malloc(nbytes));
286 op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
287 if (op->ov_magic == MAGIC) {
288 was_alloced++;
289 i = op->ov_index;
290 } else {
291 /*
292 * Already free, doing "compaction".
293 *
294 * Search for the old block of memory on the
295 * free list. First, check the most common
296 * case (last element free'd), then (this failing)
297 * the last ``__realloc_srchlen'' items free'd.
298 * If all lookups fail, then assume the size of
299 * the memory block being realloc'd is the
300 * largest possible (so that all "nbytes" of new
301 * memory are copied into). Note that this could cause
302 * a memory fault if the old area was tiny, and the moon
303 * is gibbous. However, that is very unlikely.
304 */
305 if ((i = findbucket(op, 1)) < 0 &&
306 (i = findbucket(op, __realloc_srchlen)) < 0)
307 i = NBUCKETS;
308 }
309 onb = 1 << (i + 3);
310 if (onb < pagesz)
311 onb -= sizeof (*op) + RSLOP;
312 else
313 onb += pagesz - sizeof (*op) - RSLOP;
314 /* avoid the copy if same size block */
315 if (was_alloced) {
316 if (i) {
317 i = 1 << (i + 2);
318 if (i < pagesz)
319 i -= sizeof (*op) + RSLOP;
320 else
321 i += pagesz - sizeof (*op) - RSLOP;
322 }
323 if (nbytes <= onb && nbytes > i) {
324 #ifdef RCHECK
325 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
326 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
327 #endif
328 return(cp);
329 } else
330 free(cp);
331 }
332 if ((res = malloc(nbytes)) == NULL)
333 return (NULL);
334 if (cp != res) /* common optimization if "compacting" */
335 bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
336 return (res);
337 }
338
339 /*
340 * Search ``srchlen'' elements of each free list for a block whose
341 * header starts at ``freep''. If srchlen is -1 search the whole list.
342 * Return bucket number, or -1 if not found.
343 */
344 static
345 findbucket(freep, srchlen)
346 union overhead *freep;
347 int srchlen;
348 {
349 register union overhead *p;
350 register int i, j;
351
352 for (i = 0; i < NBUCKETS; i++) {
353 j = 0;
354 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
355 if (p == freep)
356 return (i);
357 j++;
358 }
359 }
360 return (-1);
361 }
362
363 #ifdef MSTATS
364 /*
365 * mstats - print out statistics about malloc
366 *
367 * Prints two lines of numbers, one showing the length of the free list
368 * for each size category, the second showing the number of mallocs -
369 * frees for each size category.
370 */
mstats(s)371 mstats(s)
372 char *s;
373 {
374 register int i, j;
375 register union overhead *p;
376 int totfree = 0,
377 totused = 0;
378
379 fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
380 for (i = 0; i < NBUCKETS; i++) {
381 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
382 ;
383 fprintf(stderr, " %d", j);
384 totfree += j * (1 << (i + 3));
385 }
386 fprintf(stderr, "\nused:\t");
387 for (i = 0; i < NBUCKETS; i++) {
388 fprintf(stderr, " %d", nmalloc[i]);
389 totused += nmalloc[i] * (1 << (i + 3));
390 }
391 fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
392 totused, totfree);
393 }
394 #endif
395