2 Copyright (C) 1995 Pascal Haible. All Rights Reserved.
4 Permission is hereby granted, free of charge, to any person obtaining a
5 copy of this software and associated documentation files (the "Software"),
6 to deal in the Software without restriction, including without limitation
7 the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 and/or sell copies of the Software, and to permit persons to whom the
9 Software is furnished to do so, subject to the following conditions:
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 PASCAL HAIBLE BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
18 WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
19 OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 Except as contained in this notice, the name of Pascal Haible shall
23 not be used in advertising or otherwise to promote the sale, use or other
24 dealings in this Software without prior written authorization from
28 /* $XFree86: xc/programs/Xserver/os/xalloc.c,v 3.12.2.1 1997/05/10 07:03:02 hohndel Exp $ */
30 /* Only used if INTERNAL_MALLOC is defined
31 * - otherwise xalloc() in utils.c is used
33 #ifdef INTERNAL_MALLOC
35 #if defined(__STDC__) || defined(AMOEBA)
37 #include <stdlib.h> /* for malloc() etc. */
40 extern char *malloc();
41 extern char *calloc();
42 extern char *realloc();
53 extern Bool Must_have_memory;
56 ***** New malloc approach for the X server *****
59 * Some statistics about memory allocation of the X server
60 * The test session included several clients of different size, including
61 * xv, emacs and xpaint with a new canvas of 3000x2000, zoom 5.
62 * All clients were running together.
63 * A protocolling version of Xalloc recorded 318917 allocating actions
64 * (191573 Xalloc, 85942 XNFalloc, 41438 Xrealloc, 279727 Xfree).
65 * Results grouped by size, excluding the next lower size
66 * (i.e. size=32 means 16<size<=32):
68 * size nr of alloc max nr of blocks allocated together
89 * The most used sizes:
117 * Conclusions: more than the half of all allocations are <= 32 bytes.
118 * But of these about 150,000 blocks, only a maximum of about 6,000 are
119 * allocated together (including memory leaks..).
120 * On the other side, only 935 of the 191573 or 0.5% were larger than 8kB
121 * (362 or 0.2% larger than 16k).
123 * What makes the server really grow is the fragmentation of the heap,
124 * and the fact that it can't shrink.
125 * To cure this, we do the following:
126 * - large blocks (>=11k) are mmapped on xalloc, and unmapped on xfree,
127 * so we don't need any free lists etc.
128 * As this needs 2 system calls, we only do this for the quite
129 * infrequent large (>=11k) blocks.
130 * - instead of reinventing the wheel, we use system malloc for medium
131 * sized blocks (>256, <11k).
132 * - for small blocks (<=256) we use an other approach:
133 * As we need many small blocks, and most ones for a short time,
134 * we don't go through the system malloc:
135 * for each fixed sizes a seperate list of free blocks is kept.
136 * to KISS (Keep it Small and Simple), we don't free them
137 * (not freeing a block of 32 bytes won't be worse than having fragmented
138 * a larger area on allocation).
139 * This way, we (almost) allways have a fitting free block right at hand,
140 * and don't have to walk any lists.
144 * structure layout of a allocated block
145 * unsigned long size:
146 * rounded up netto size for small and medium blocks
147 * brutto size == mmap'ed area for large blocks
148 * unsigned long DEBUG ? MAGIC : unused
150 * ( unsigned long MAGIC2 ) only if SIZE_TAIL defined
154 /* use otherwise unused long in the header to store a magic */
155 /* shouldn't this be removed for production release ? */
159 /* Xfree fills the memory with a certain pattern (currently 0xF0) */
160 /* this should really be removed for production release! */
164 /* this must be a multiple of SIZE_STEPS below */
165 #define MAX_SMALL 264 /* quite many blocks of 264 */
167 #define MIN_LARGE (11*1024)
168 /* worst case is 25% loss with a page size of 4k */
170 /* SIZE_STEPS defines the granularity of size of small blocks -
171 * this makes blocks align to that, too! */
172 #define SIZE_STEPS (sizeof(double))
173 #define SIZE_HEADER (2*sizeof(long)) /* = sizeof(double) for 32bit */
175 #if defined(__sparc__) || defined(__hppa__)
176 #define SIZE_TAIL (2*sizeof(long)) /* = sizeof(double) for 32bit */
178 #define SIZE_TAIL (sizeof(long))
184 #define TAIL_SIZE SIZE_TAIL
190 #define MAGIC 0x1404196414071968
191 #define MAGIC2 0x2515207525182079
193 #define MAGIC 0x14071968
194 #define MAGIC2 0x25182079
197 /* To get some statistics about memory allocation */
200 #define XALLOC_LOG_FILE "/tmp/Xalloc.log" /* unsecure... */
201 #define LOG_BODY(_body) \
203 f = fopen(XALLOC_LOG_FILE, "a"); \
209 #if defined(linux) && defined(i386)
210 #define LOG_ALLOC(_fun, _size, _ret) \
211 { unsigned long *from; \
212 __asm__("movl %%ebp,%0" : /*OUT*/ "=r" (from) : /*IN*/ ); \
213 LOG_BODY(fprintf(f, "%s\t%i\t%p\t[%lu]\n", _fun, _size, _ret, *(from+1))) \
216 #define LOG_ALLOC(_fun, _size, _ret) \
217 LOG_BODY(fprintf(f, "%s\t%i\t%p\n", _fun, _size, _ret))
219 #define LOG_REALLOC(_fun, _ptr, _size, _ret) \
220 LOG_BODY(fprintf(f, "%s\t%p\t%i\t%p\n", _fun, _ptr, _size, _ret))
221 #define LOG_FREE(_fun, _ptr) \
222 LOG_BODY(fprintf(f, "%s\t%p\n", _fun, _ptr))
224 #define LOG_ALLOC(_fun, _size, _ret)
225 #define LOG_REALLOC(_fun, _ptr, _size, _ret)
226 #define LOG_FREE(_fun, _ptr)
227 #endif /* XALLOC_LOG */
229 static unsigned long *free_lists[MAX_SMALL/SIZE_STEPS];
232 * systems that support it should define HAS_MMAP_ANON or MMAP_DEV_ZERO
233 * and include the appropriate header files for
234 * mmap(), munmap(), PROT_READ, PROT_WRITE, MAP_PRIVATE,
235 * PAGE_SIZE or _SC_PAGESIZE (and MAP_ANON for HAS_MMAP_ANON).
237 * systems that don't support MAP_ANON fall through to the 2 fold behaviour
241 #define HAS_MMAP_ANON
242 #include <sys/types.h>
243 #include <sys/mman.h>
244 #include <asm/page.h> /* PAGE_SIZE */
247 #if defined(CSRG_BASED)
248 #define HAS_MMAP_ANON
249 #define HAS_GETPAGESIZE
250 #include <sys/types.h>
251 #include <sys/mman.h>
252 #endif /* CSRG_BASED */
255 #define MMAP_DEV_ZERO
256 #include <sys/types.h>
257 #include <sys/mman.h>
261 #if defined(sun) && !defined(SVR4) /* SunOS */
262 #define MMAP_DEV_ZERO /* doesn't SunOS have MAP_ANON ?? */
263 #define HAS_GETPAGESIZE
264 #include <sys/types.h>
265 #include <sys/mman.h>
266 #endif /* sun && !SVR4 */
272 #if defined(HAS_MMAP_ANON) || defined (MMAP_DEV_ZERO)
277 static int devzerofd = -1;
279 #ifdef X_NOT_STDC_ENV
287 unsigned long amount;
289 register unsigned long *ptr;
294 /* zero size requested */
296 LOG_ALLOC("Xalloc=0", amount, 0);
297 return (unsigned long *)NULL;
299 /* negative size (or size > 2GB) - what do we do? */
300 if ((long)amount < 0) {
303 FatalError("Xalloc: Xalloc(<0)\n");
305 ErrorF("Xalloc warning: Xalloc(<0) ignored..\n");
307 LOG_ALLOC("Xalloc<0", amount, 0);
308 return (unsigned long *)NULL;
311 /* alignment check */
312 #if defined(__alpha__) || defined(__sparc__) || defined(__mips__) || defined(__hppa__)
313 amount = (amount + (sizeof(long)-1)) & ~(sizeof(long)-1);
316 if (amount <= MAX_SMALL) {
320 /* pick a ready to use small chunk */
321 indx = (amount-1) / SIZE_STEPS;
322 ptr = free_lists[indx];
324 /* list empty - get 20 or 40 more */
325 /* amount = size rounded up */
326 amount = (indx+1) * SIZE_STEPS;
327 ptr = (unsigned long *)calloc(1,(amount+SIZE_HEADER+TAIL_SIZE)
328 * (amount<100 ? 40 : 20));
331 unsigned long *p1, *p2;
332 p2 = (unsigned long *)((char *)ptr + SIZE_HEADER);
333 for (i=0; i<(amount<100 ? 40 : 20); i++) {
338 #endif /* XALLOC_DEBUG */
340 *(unsigned long *)((unsigned char *)p1 + amount) = MAGIC2;
341 #endif /* SIZE_TAIL */
342 p2 = (unsigned long *)((char *)p1 + SIZE_HEADER + amount + TAIL_SIZE);
343 *(unsigned long **)p1 = p2;
345 /* last one has no next one */
346 *(unsigned long **)p1 = NULL;
347 /* put the second in the list */
348 free_lists[indx] = (unsigned long *)((char *)ptr + SIZE_HEADER + amount + TAIL_SIZE + SIZE_HEADER);
349 /* take the fist one */
350 ptr = (unsigned long *)((char *)ptr + SIZE_HEADER);
351 LOG_ALLOC("Xalloc-S", amount, ptr);
353 } /* else fall through to 'Out of memory' */
355 /* take that piece of mem out of the list */
356 free_lists[indx] = *((unsigned long **)ptr);
357 /* already has size (and evtl. magic) filled in */
358 LOG_ALLOC("Xalloc-S", amount, ptr);
362 #if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
363 } else if (amount >= MIN_LARGE) {
368 /* round up amount */
369 amount += SIZE_HEADER + TAIL_SIZE;
370 /* round up brutto amount to a multiple of the page size */
371 amount = (amount + pagesize-1) & ~(pagesize-1);
373 ptr = (unsigned long *)mmap((caddr_t)0,
375 PROT_READ | PROT_WRITE,
380 ptr = (unsigned long *)mmap((caddr_t)0,
382 PROT_READ | PROT_WRITE,
383 MAP_ANON | MAP_PRIVATE,
388 ptr[0] = amount - SIZE_HEADER - TAIL_SIZE;
391 #endif /* XALLOC_DEBUG */
394 /* reserved space for 2 * sizeof(long), so use correct one */
395 /* see SIZE_TAIL macro */
396 ((unsigned long *)((char *)ptr + amount))[-2] = MAGIC2;
398 ((unsigned long *)((char *)ptr + amount))[-1] = MAGIC2;
399 # endif /* __hppa__ */
400 #endif /* SIZE_TAIL */
401 ptr = (unsigned long *)((char *)ptr + SIZE_HEADER);
402 LOG_ALLOC("Xalloc-L", amount, ptr);
404 } /* else fall through to 'Out of memory' */
405 #endif /* HAS_MMAP_ANON || MMAP_DEV_ZERO */
410 /* 'normal' malloc() */
411 ptr=(unsigned long *)calloc(1,amount+SIZE_HEADER+TAIL_SIZE);
412 if (ptr != (unsigned long *)NULL) {
416 #endif /* XALLOC_DEBUG */
418 *(unsigned long *)((char *)ptr + amount + SIZE_HEADER) = MAGIC2;
419 #endif /* SIZE_TAIL */
420 ptr = (unsigned long *)((char *)ptr + SIZE_HEADER);
421 LOG_ALLOC("Xalloc-M", amount, ptr);
425 if (Must_have_memory)
426 FatalError("Out of memory");
427 LOG_ALLOC("Xalloc-oom", amount, 0);
428 return (unsigned long *)NULL;
433 * "no failure" realloc, alternate interface to Xalloc w/o Must_have_memory
438 unsigned long amount;
440 register unsigned long *ptr;
442 /* zero size requested */
444 LOG_ALLOC("XNFalloc=0", amount, 0);
445 return (unsigned long *)NULL;
447 /* negative size (or size > 2GB) - what do we do? */
448 if ((long)amount < 0) {
451 FatalError("Xalloc: XNFalloc(<0)\n");
453 ErrorF("Xalloc warning: XNFalloc(<0) ignored..\n");
455 LOG_ALLOC("XNFalloc<0", amount, 0);
456 return (unsigned long *)NULL;
458 ptr = Xalloc(amount);
461 FatalError("Out of memory");
472 unsigned long amount;
476 ret = Xalloc (amount);
478 #if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
479 && (amount < MIN_LARGE) /* mmaped anonymous mem is already cleared */
482 bzero ((char *) ret, (int) amount);
491 Xrealloc (ptr, amount)
492 register pointer ptr;
493 unsigned long amount;
495 register unsigned long *new_ptr;
497 /* zero size requested */
501 LOG_REALLOC("Xrealloc=0", ptr, amount, 0);
502 return (unsigned long *)NULL;
504 /* negative size (or size > 2GB) - what do we do? */
505 if ((long)amount < 0) {
508 FatalError("Xalloc: Xrealloc(<0)\n");
510 ErrorF("Xalloc warning: Xrealloc(<0) ignored..\n");
514 LOG_REALLOC("Xrealloc<0", ptr, amount, 0);
515 return (unsigned long *)NULL;
518 new_ptr = Xalloc(amount);
519 if ( (new_ptr) && (ptr) ) {
520 unsigned long old_size;
521 old_size = ((unsigned long *)ptr)[-2];
523 if (MAGIC != ((unsigned long *)ptr)[-1]) {
525 FatalError("Xalloc error: header corrupt in Xrealloc() :-(\n");
527 ErrorF("Xalloc error: header corrupt in Xrealloc() :-(\n");
529 LOG_REALLOC("Xalloc error: header corrupt in Xrealloc() :-(",
531 return (unsigned long *)NULL;
533 #endif /* XALLOC_DEBUG */
534 /* copy min(old size, new size) */
535 memcpy((char *)new_ptr, (char *)ptr, (amount < old_size ? amount : old_size));
540 LOG_REALLOC("Xrealloc", ptr, amount, new_ptr);
543 if (Must_have_memory)
544 FatalError("Out of memory");
545 LOG_REALLOC("Xrealloc", ptr, amount, 0);
546 return (unsigned long *)NULL;
551 * "no failure" realloc, alternate interface to Xrealloc w/o Must_have_memory
555 XNFrealloc (ptr, amount)
556 register pointer ptr;
557 unsigned long amount;
559 if (( ptr = (pointer)Xrealloc( ptr, amount ) ) == NULL)
561 FatalError( "Out of memory" );
563 return ((unsigned long *)ptr);
573 register pointer ptr;
576 unsigned long *pheader;
578 /* free(NULL) IS valid :-( - and widely used throughout the server.. */
582 pheader = (unsigned long *)((char *)ptr - SIZE_HEADER);
584 if (MAGIC != pheader[1]) {
587 FatalError("Xalloc error: Header corrupt in Xfree() :-(\n");
589 ErrorF("Xalloc error: Header corrupt in Xfree() :-(\n");
591 LOG_FREE("Xalloc error: Header corrupt in Xfree() :-(", ptr);
594 #endif /* XALLOC_DEBUG */
597 if (size <= MAX_SMALL) {
603 if (MAGIC2 != *(unsigned long *)((char *)ptr + size)) {
606 FatalError("Xalloc error: Tail corrupt in Xfree() for small block (adr=0x%x, val=0x%x)\n",(char *)ptr + size,*(unsigned long *)((char *)ptr + size));
608 ErrorF("Xalloc error: Tail corrupt in Xfree() for small block (adr=0x%x, val=0x%x)\n",(char *)ptr + size,*(unsigned long *)((char *)ptr + size));
610 LOG_FREE("Xalloc error: Tail corrupt in Xfree() for small block", ptr);
613 #endif /* SIZE_TAIL */
616 memset(ptr,0xF0,size);
617 #endif /* XFREE_ERASES */
619 /* put this small block at the head of the list */
620 indx = (size-1) / SIZE_STEPS;
621 *(unsigned long **)(ptr) = free_lists[indx];
622 free_lists[indx] = (unsigned long *)ptr;
623 LOG_FREE("Xfree", ptr);
626 #if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
627 } else if (size >= MIN_LARGE) {
632 if (MAGIC2 != ((unsigned long *)((char *)ptr + size))[0]) {
635 FatalError("Xalloc error: Tail corrupt in Xfree() for big block (adr=0x%x, val=0x%x)\n",(char *)ptr+size,((unsigned long *)((char *)ptr + size))[0]);
637 ErrorF("Xalloc error: Tail corrupt in Xfree() for big block (adr=0x%x, val=0x%x)\n",(char *)ptr+size,((unsigned long *)((char *)ptr + size))[0]);
639 LOG_FREE("Xalloc error: Tail corrupt in Xfree() for big block", ptr);
643 #endif /* SIZE_TAIL */
645 LOG_FREE("Xfree", ptr);
647 munmap((caddr_t)pheader, (size_t)size);
648 /* no need to clear - mem is inaccessible after munmap.. */
649 #endif /* HAS_MMAP_ANON */
656 if (MAGIC2 != *(unsigned long *)((char *)ptr + size)) {
659 FatalError("Xalloc error: Tail corrupt in Xfree() for medium block (adr=0x%x, val=0x%x)\n",(char *)ptr + size,*(unsigned long *)((char *)ptr + size));
661 ErrorF("Xalloc error: Tail corrupt in Xfree() for medium block (adr=0x%x, val=0x%x)\n",(char *)ptr + size,*(unsigned long *)((char *)ptr + size));
663 LOG_FREE("Xalloc error: Tail corrupt in Xfree() for medium block", ptr);
666 #endif /* SIZE_TAIL */
669 memset(pheader,0xF0,size+SIZE_HEADER);
670 #endif /* XFREE_ERASES */
672 LOG_FREE("Xfree", ptr);
673 free((char *)pheader);
680 static Bool beenhere = FALSE;
686 #if defined(HAS_MMAP_ANON) || defined (MMAP_DEV_ZERO)
687 #if defined(_SC_PAGESIZE) /* || defined(linux) */
688 pagesize = sysconf(_SC_PAGESIZE);
690 #ifdef HAS_GETPAGESIZE
691 pagesize = getpagesize();
693 pagesize = PAGE_SIZE;
698 /* set up linked lists of free blocks */
699 bzero ((char *) free_lists, MAX_SMALL/SIZE_STEPS*sizeof(unsigned long *));
702 /* open /dev/zero on systems that have mmap, but not MAP_ANON */
704 if ((devzerofd = open("/dev/zero", O_RDWR, 0)) < 0)
705 FatalError("OsInitAllocator: Cannot open /dev/zero (errno=%d)\n",
711 /* reset the log file to zero length */
714 f = fopen(XALLOC_LOG_FILE, "w");
721 #else /* !INTERNAL_MALLOC */
722 /* This is to avoid an empty .o */
723 static int no_internal_xalloc;
724 #endif /* INTERNAL_MALLOC */