1 /*
2 * *********************************************************************
3 * * Copyright (C) 1988, 1990 Stanford University. *
4 * * Permission to use, copy, modify, and distribute this *
5 * * software and its documentation for any purpose and without *
6 * * fee is hereby granted, provided that the above copyright *
7 * * notice appear in all copies. Stanford University *
8 * * makes no representations about the suitability of this *
9 * * software for any purpose. It is provided "as is" without *
10 * * express or implied warranty. Export of this software outside *
11 * * of the United States of America may require an export license. *
12 * *********************************************************************
13 */
14
15 /*
16 * This is a very low overhead storage allocator for managing many
17 * "small" objects.
18 *
19 * The allocator recognizes 2 different types of objects: (1) small
20 * fixed size objects, and (2) large or variable size objects.
21 *
22 * Variable size objects are allocated on demand, using a next-fit
23 * algorithm. The same is used for large objects.
24 *
25 * When a small fixed size object is requested, the allocator will
26 * pre-allocate as many such objects as will fit in one page (4Kbytes in-
27 * this implementation). The unused objects are put in a free list for
28 * quick access later on. A separate free list for every object size is
29 * maintained. When such an object is freed, it is simply put back in
30 * its respective free list (small objects don't migrate from one free
31 * list to another).
32 *
33 * All objects returned by Malloc are word aligned: a word is defined to
34 * be the smallest size integer into which an address can be cast. All
35 * requests are rounded to a multiple of words (as defined above).
36 *
37 * The allocator does not "remember" the size of fixed-size objects. Keeping
38 * this information is left to the user. It does however, remeber the size of
39 * objects allocated using Valloc.
40 *
41 * The allocator provides the following interfaces:
42 * 1) Falloc( nbytes )
43 * returns a pointer to nbytes of storage. For fixed size objects.
44 * 2) Valloc( nbytes )
45 * returns a pointer to nbytes of storage. For variable size objects.
46 * 3) MallocList( size )
47 * returns a linked list of 'size' bytes objects.
48 * 4) Ffree( ptr, nbytes )
49 * deallocate the fixed size object of 'nbytes' pointed to by 'ptr'.
50 * 4) Vfree( ptr )
51 * deallocate the variable object of 'nbytes' pointed to by 'ptr'.
52 *
53 * The argument to Ffree can be any any object obtained from Falloc, or
54 * any one of the elements obtained from MallocList.
55 */
56
57
58
59 #include <stdio.h>
60 #include <unistd.h>
61 #include <stdlib.h>
62 #include <sys/types.h>
63 #include <sys/time.h>
64 #include <sys/resource.h>
65
66 #include "defs.h"
67
68 /* number of bytes in a word */
69 #define WORDSIZE ( sizeof( Object ) )
70
71 /* round x to nearest z (ceiling function) */
72 #define ROUND( x, z ) ( ((x) + (z) - 1) / (z) )
73
74 /* convert size in bytes to nearest number of words */
75 #define NWORDS( x ) ROUND( x, WORDSIZE )
76
77 /* number of bytes/words per page */
78 #define DATABYTES 4096
79 #define DATAWORDS ( DATABYTES / WORDSIZE )
80
81 /* objects larger than this many words are considered large */
82 #define BIG_OBJ 40
83
84 #define NBINS (BIG_OBJ + 1)
85
86
87 typedef union Object *Pointer;
88
89 typedef union Object /* Basic data object (i.e. `machine word') */
90 {
91 Pointer ptr;
92 int num;
93 double dble;
94 int align[1];
95 } Object;
96
97
98
99 /* export this definition for the user's sake */
100 public typedef union MElem
101 {
102 union MElem *next; /* points to next element in linked list */
103 int align[1]; /* dummy used to force word alignment */
104 } *MList;
105
106
107 typedef struct
108 {
109 Pointer free1; /* Lists of free objects of this size */
110 Pointer free2;
111 } Bucket;
112
113
114 private Bucket bucket[NBINS]; /* free list hash table */
115
116 #if !defined(CYGWIN) && !defined(__APPLE__)
117 /* External definitions */
118 extern int etext;
119 extern unsigned sleep();
120 #endif /* CYGWIN */
121
122 #define SBRK_FAIL ( (char *) -1 )
123 #define MAXTRIES 5
124
125 #define PAGE_SIZE 1024 /* for alignment */
126 #define PAGE_MASK ( PAGE_SIZE - 1 )
127
128 #define FPRINTF (void) fprintf
129 #if defined(CYGWIN) || defined(__APPLE__) || defined(__FreeBSD__)
GetMoreCore(npages)130 private Pointer GetMoreCore( npages )
131 int npages;
132 {
133 void *ret;
134 int nbytes;
135
136 nbytes = npages * DATABYTES + PAGE_SIZE;
137
138 ret = malloc(nbytes);
139 return ( (Pointer) ret);
140 }
141 #else
142
143 /*
144 * Interface to the system's sbrk call. If sbrk fails, try to determine
145 * what's happening and attempt to solve it. If all fails return NULL.
146 */
147
148 #ifdef SYS_V
149
GetMoreCore(npages)150 private Pointer GetMoreCore( npages )
151 int npages;
152 {
153 void *ret;
154 long cursize, newsize, nbytes;
155 long tries, inc;
156 long lim;
157
158 cursize = (long) sbrk( 0 ); /* align on 1K boundary */
159 inc = PAGE_SIZE - (cursize & PAGE_MASK) & PAGE_MASK;
160
161 nbytes = npages * DATABYTES + inc;
162
163 ret = sbrk( nbytes );
164 if( ret != SBRK_FAIL )
165 return( (Pointer) ret );
166
167 newsize = cursize + nbytes;
168 lim = ulimit( 3, 0 );
169
170 ret = SBRK_FAIL;
171
172 if( newsize <= lim )
173 {
174 for( tries = 0; tries < MAXTRIES and ret == SBRK_FAIL; tries++ )
175 {
176 if( tries == 0 )
177 {
178 FPRINTF( stderr, "*** MEMORY WARNING ***\n" );
179 FPRINTF( stderr, "Current data size: %ld (%ldK)\n", cursize,
180 ROUND( cursize, 1024 ));
181 FPRINTF( stderr, "New data size = %ld (%ldK)\n", newsize,
182 ROUND( newsize, 1024 ) );
183 FPRINTF( stderr, "Hard limit = %d (%dK)\n", lim,
184 ROUND( lim, 1024 ));
185 }
186 FPRINTF( stderr, "I seem to be short on swap space\n" );
187 FPRINTF( stderr, "Will sleep for 15 seconds and try again\n");
188 (void) sleep( 15 );
189 ret = sbrk( nbytes );
190 }
191 }
192
193 return( ( ret == SBRK_FAIL ) ? (Pointer) NULL : (Pointer) ret );
194 }
195
196 #else /* BSD */
197
198 #ifdef host_mips /* kludge for mips based systems */
199 # define heap_start (char *) 0x10000000
200 #else
201 # define heap_start (char *) &etext
202 #endif
203
GetMoreCore(npages)204 private Pointer GetMoreCore( npages )
205 int npages;
206 {
207 void *ret;
208 long cursize, newsize, nbytes;
209 long tries, inc;
210 struct rlimit lim;
211
212 cursize = (long) sbrk( 0 ); /* align on 1K boundary */
213 inc = PAGE_SIZE - ((cursize & PAGE_MASK) & PAGE_MASK);
214
215 nbytes = npages * DATABYTES + inc;
216
217 ret = sbrk( nbytes );
218 if( ret != SBRK_FAIL )
219 return( (Pointer) ret );
220
221 cursize -= (long) heap_start;
222 newsize = cursize + nbytes;
223 (void) getrlimit( RLIMIT_DATA, &lim );
224
225 if( newsize > lim.rlim_max )
226 {
227 FPRINTF( stderr, "Memory Error: Hard limit exceeded %d\n",
228 (int)ROUND( lim.rlim_max, 1024 ) );
229 return( (Pointer) NULL );
230 }
231
232 ret = SBRK_FAIL;
233 for( tries = 0; tries < MAXTRIES and ret == SBRK_FAIL; tries++ )
234 {
235 if( newsize < lim.rlim_cur )
236 {
237 if( tries == 0 )
238 {
239 FPRINTF( stderr, "*** MEMORY WARNING ***\n" );
240 FPRINTF( stderr, "Current data size: %ld (%ldK)\n", cursize,
241 ROUND( cursize, 1024 ));
242 FPRINTF( stderr, "New data size = %ld (%ldK)\n", newsize,
243 ROUND( newsize, 1024 ) );
244 FPRINTF( stderr, "Soft limit = %d (%dK)\n", (int)lim.rlim_cur,
245 (int)ROUND( lim.rlim_cur, 1024 ));
246 FPRINTF( stderr, "Hard limit = %d (%dK)\n", (int)lim.rlim_max,
247 (int)ROUND( lim.rlim_max, 1024 ));
248 }
249 FPRINTF( stderr, "I seem to be short on swap space\n" );
250 FPRINTF( stderr, "Will sleep for 15 seconds and try again\n");
251 (void) sleep( 15 );
252 }
253 else if( newsize < lim.rlim_max )
254 {
255 int softlim = lim.rlim_cur;
256
257 FPRINTF( stderr, "MEMORY WARNING: Soft limit exceeded\n" );
258 lim.rlim_cur = lim.rlim_max;
259 if( setrlimit( RLIMIT_DATA, &lim ) == 0 )
260 {
261 FPRINTF( stderr,
262 " => Soft limit increased from %d (%dK) to %d (%d)\n",
263 softlim, ROUND( softlim, 1024 ),
264 (int)lim.rlim_max, (int)ROUND( lim.rlim_max, 1024 ) );
265 }
266 else
267 {
268 FPRINTF( stderr,
269 " => Can NOT increase Soft limit [%d (%dK)] to %d (%d)\n",
270 softlim, ROUND( softlim, 1024 ),
271 (int)lim.rlim_max, (int)ROUND( lim.rlim_max, 1024 ) );
272 FPRINTF( stderr, "I Will try again in 15 seconds\n" );
273 (void) sleep( 15 );
274 }
275 }
276 ret = sbrk( nbytes );
277 }
278
279 return( ( ret == SBRK_FAIL ) ? (Pointer) NULL : (Pointer) ret );
280 }
281
282 #endif /* SYS_V */
283 #endif /* CYGWIN */
284
285 /*
286 * Get nPages contiguous pages. Make sure new pages are aligned on system
287 * page boundaries.
288 * If 'size' is <> 0, the elements in the page(s) are linked into a list.
289 */
GetPage(nPages,size,no_mem_exit)290 private Pointer GetPage( nPages, size, no_mem_exit )
291 int nPages;
292 int size;
293 int no_mem_exit;
294 {
295 Pointer pg;
296 int inc;
297
298 pg = GetMoreCore( nPages );
299
300 if( pg == NULL )
301 {
302 if( no_mem_exit == 0 )
303 return( pg );
304 FPRINTF( stderr, "Out of memory.\n" );
305 exit( 1 );
306 }
307
308 if( size != 0 ) /* Initialize the new page */
309 {
310 register Pointer p, page;
311 register int n, np, nwords;
312
313 inc = DATAWORDS / size;
314 nwords = size;
315 page = pg;
316 np = nPages;
317 while( np-- > 0 )
318 {
319 n = inc;
320 for( p = page; --n > 0; p->ptr = p + nwords, p += nwords );
321 p->ptr = (np == 0) ? NULL : (page += DATAWORDS);
322 }
323 }
324 return( pg );
325 }
326
327
328 /* forward references */
329 private MList MallocBigList();
330 char *Valloc();
331 void Ffree(), Vfree();
332
333
Falloc(nbytes,no_mem_exit)334 public char *Falloc( nbytes, no_mem_exit )
335 int nbytes;
336 int no_mem_exit;
337 {
338 register Bucket *bin;
339 register Pointer p;
340 register int nwords;
341
342 if( nbytes <= 0 ) /* ubiquitous check */
343 return( NULL );
344
345 nwords = NWORDS( nbytes );
346 if( nwords >= NBINS )
347 return( Valloc( nbytes, no_mem_exit ) );
348
349 bin = &(bucket[nwords]);
350 if( (p = bin->free1) != NULL )
351 {
352 if( (bin->free1 = p->ptr) == NULL )
353 {
354 bin->free1 = bin->free2;
355 bin->free2 = NULL;
356 }
357 }
358 else
359 {
360 int n;
361
362 p = GetPage( 1, nwords, no_mem_exit );
363 if( p == NULL ) /* Out of memory */
364 return( NULL );
365
366 n = nwords * ((DATAWORDS / nwords) / 2);
367 bin->free1 = p->ptr;
368 bin->free2 = p + n;
369 p[n - nwords].ptr = NULL;
370 }
371 return( (char *) p );
372 }
373
374
Ffree(p,nbytes)375 public void Ffree( p, nbytes )
376 Pointer p;
377 int nbytes;
378 {
379 register int nwords;
380
381 if( p == NULL or nbytes <= 0 ) /* sanity ? */
382 return;
383
384 nwords = NWORDS( nbytes );
385 if( nwords >= NBINS ) /* big block */
386 Vfree( p );
387 else /* return to its corresponding bin */
388 {
389 p->ptr = bucket[nwords].free1;
390 bucket[nwords].free1 = p;
391 }
392 }
393
394 /*
395 * Return a linked list of elements, each 'nbytes' long in size.
396 */
MallocList(nbytes,no_mem_exit)397 public MList MallocList( nbytes, no_mem_exit )
398 int nbytes;
399 int no_mem_exit;
400 {
401 register Pointer p;
402 register int nwords, n;
403 register Bucket *bin;
404
405 if( nbytes <= 0 )
406 return( NULL );
407
408 nwords = NWORDS( nbytes );
409 if( nwords >= NBINS )
410 return( MallocBigList( nbytes, no_mem_exit ) );
411
412 bin = &(bucket[nwords]);
413 if( (p = bin->free1) != NULL )
414 {
415 bin->free1 = bin->free2;
416 bin->free2 = NULL;
417 }
418 else
419 {
420 p = GetPage( 1, nwords, no_mem_exit );
421 if( p == NULL ) /* Out of memory */
422 return( NULL );
423
424 n = nwords * ((DATAWORDS / nwords) / 2);
425 bin->free1 = p + n; /* save 2nd half of the page */
426 bin->free2 = NULL;
427 p[n - nwords].ptr = NULL;
428 }
429
430 return( (MList) p );
431 }
432
433
434 /*
435 * Handle the large (infrequent) case.
436 */
MallocBigList(nbytes,no_mem_exit)437 private MList MallocBigList( nbytes, no_mem_exit )
438 int nbytes;
439 int no_mem_exit;
440 {
441 int nelem;
442 Pointer head, tail;
443
444 nelem = ( nbytes < 2 * DATABYTES ) ? DATABYTES / nbytes : 2;
445 head = tail = (Pointer) Valloc( nbytes, no_mem_exit );
446 if( head == NULL )
447 return( NULL );
448
449 while( --nelem > 0 )
450 {
451 tail->ptr = (Pointer) Valloc( nbytes, no_mem_exit );
452 if( tail->ptr == NULL )
453 {
454 while( head != NULL )
455 { /* free everything already Malloc`d */
456 tail = head->ptr;
457 Vfree( head );
458 head = tail;
459 }
460 return( NULL );
461 }
462 tail = tail->ptr;
463 }
464 tail->ptr = NULL;
465 return( (MList) head );
466 }
467
468
469
470 /*
471 * Next-fit storage allocation for variable (infrequent) size objects.
472 * Algorithm and variable names from Knuth V1, p 437. See Exercise 2.5.6.
473 */
474 private Object avail[2]; /* dummy header that points to first
475 * free element. Free list is kept
476 * in address order */
477 private Pointer rover = avail; /* pointer into the free list */
478
479
480 #define NEXT( blk ) ( (blk)->ptr ) /* next block in free list */
481 #define SIZE( blk ) ( blk[1].num ) /* words available in block */
482
483
484 /*
485 * Add the block pointed to by 'ptr' to the free list.
486 */
Vfree(ptr)487 public void Vfree( ptr )
488 Pointer ptr;
489 {
490 register Pointer p, q, r;
491 register int nwords;
492
493 if( ptr == NULL )
494 return;
495
496 ptr--;
497 nwords = ptr->num;
498 if( nwords <= 0 )
499 return;
500
501 q = avail;
502 r = ptr;
503 p = NEXT( q );
504
505 while( (p != NULL) and (p < r) ) /* search for the right place */
506 {
507 q = p;
508 p = NEXT( p );
509 }
510 /* this is where it should go */
511 /* note: since NULL = 0, if p = NULL, p != r + nwords */
512
513 if( p == r + nwords ) /* new block abuts p, consolidate */
514 {
515 nwords += SIZE( p );
516 NEXT( r ) = NEXT( p );
517 }
518 else /* does not abut, just connect */
519 {
520 NEXT( r ) = p;
521 }
522
523 if( r == q + SIZE( q ) ) /* new block abuts q, consolidate */
524 {
525 SIZE( q ) += nwords;
526 NEXT( q ) = NEXT( r );
527 }
528 else /* does not abut, just connect */
529 {
530 NEXT( q ) = r;
531 SIZE( r ) = nwords;
532 }
533 rover = q; /* start searching here next time */
534 }
535
536
537 /*
538 * Return a pointer to (at least) n bytes of storage.
539 */
Valloc(nbytes,no_mem_exit)540 public char *Valloc( nbytes, no_mem_exit )
541 int nbytes;
542 int no_mem_exit;
543 {
544 register Pointer p, q;
545 register int nwords;
546 int firstTime;
547
548 if( nbytes <= 0 ) /* ubiquitous check */
549 return( NULL );
550
551 nwords = (NWORDS( nbytes ) + 2) & ~1;
552
553 Start :
554 if( (q = rover) == NULL )
555 {
556 q = rover = avail;
557 firstTime = 0;
558 }
559 else
560 firstTime = 1;
561
562 again:
563 p = NEXT( q );
564 while( p != NULL ) /* search for a block large enough */
565 {
566 if( SIZE( p ) >= nwords )
567 goto found;
568 q = p;
569 p = NEXT( p );
570 }
571
572 if( firstTime )
573 {
574 q = avail; /* first time, one more chance */
575 firstTime = 0;
576 goto again;
577 }
578
579 { /* fall through: out of memory, get some more */
580 int nPages;
581 Pointer pg;
582
583 nPages = 2 * (ROUND( nwords, DATAWORDS ));
584 pg = GetPage( nPages, 0, no_mem_exit );
585 if( pg == NULL )
586 return( NULL );
587
588 pg->num = nPages * DATAWORDS;
589 Vfree( pg + 1 );
590 goto Start; /* try again */
591 }
592
593 found :
594 if( SIZE( p ) == nwords ) /* exact match. remove block */
595 {
596 NEXT( q ) = NEXT( p );
597 }
598 else /* SIZE( p ) > nwords => too large. take part of it */
599 {
600 register Pointer r;
601
602 r = p + nwords; /* remaining free area */
603 NEXT( q ) = r;
604 NEXT( r ) = NEXT( p );
605 SIZE( r ) = SIZE( p ) - nwords;
606 }
607 rover = q; /* start looking here next time */
608
609 p->num = nwords;
610 p++;
611 return( (char *) p );
612 }
613