xorg-server-1.4/os/xalloc.c

   1 #define FATALERRORS 1
   2 /*
   3 Copyright (C) 1995 Pascal Haible.  All Rights Reserved.
   4
   5 Permission is hereby granted, free of charge, to any person obtaining a
   6 copy of this software and associated documentation files (the "Software"),
   7 to deal in the Software without restriction, including without limitation
   8 the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9 and/or sell copies of the Software, and to permit persons to whom the
  10 Software is furnished to do so, subject to the following conditions:
  11
  12 The above copyright notice and this permission notice shall be included in
  13 all copies or substantial portions of the Software.
  14
  15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18 PASCAL HAIBLE BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  19 WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
  20 OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21 SOFTWARE.
  22
  23 Except as contained in this notice, the name of Pascal Haible shall
  24 not be used in advertising or otherwise to promote the sale, use or other
  25 dealings in this Software without prior written authorization from
  26 Pascal Haible.
  27 */
  28
  29
  30 /* Only used if INTERNAL_MALLOC is defined
  31  * - otherwise xalloc() in utils.c is used
  32  */
  33 #ifdef HAVE_DIX_CONFIG_H
  34 #include <dix-config.h>
  35 #endif
  36
  37 #ifdef INTERNAL_MALLOC
  38
  39 #include <stdlib.h>     /* for malloc() etc. */
  40
  41 #include <X11/Xos.h>
  42 #include "misc.h"
  43 #include <X11/X.h>
  44
  45 #ifdef XALLOC_LOG
  46 #include <stdio.h>
  47 #endif
  48
  49 extern Bool Must_have_memory;
  50
  51 /*
  52  ***** New malloc approach for the X server *****
  53  * Pascal Haible 1995
  54  *
  55  * Some statistics about memory allocation of the X server
  56  * The test session included several clients of different size, including
  57  * xv, emacs and xpaint with a new canvas of 3000x2000, zoom 5.
  58  * All clients were running together.
  59  * A protocolling version of Xalloc recorded 318917 allocating actions
  60  * (191573 Xalloc, 85942 XNFalloc, 41438 Xrealloc, 279727 Xfree).
  61  * Results grouped by size, excluding the next lower size
  62  * (i.e. size=32 means 16<size<=32):
  63  *
  64  *    size   nr of alloc   max nr of blocks allocated together
  65  *       8      1114            287
  66  *      16      17341           4104
  67  *      32      147352          2068
  68  *      64      59053           2518
  69  *     128      46882           1230
  70  *     256      20544           1217
  71  *     512      6808            117
  72  *    1024      8254            171
  73  *    2048      4841            287
  74  *    4096      2429            84
  75  *    8192      3364            85
  76  *   16384      573             22
  77  *   32768      49              7
  78  *   65536      45              5
  79  *  131072      48              2
  80  *  262144      209             2
  81  *  524288      7               4
  82  * 1048576      2               1
  83  * 8388608      2               2
  84  *
  85  * The most used sizes:
  86  * count size
  87  * 24   136267
  88  * 40   37055
  89  * 72   17278
  90  * 56   13504
  91  * 80   9372
  92  * 16   8966
  93  * 32   8411
  94  * 136  8399
  95  * 104  7690
  96  * 12   7630
  97  * 120  5512
  98  * 88   4634
  99  * 152  3062
 100  * 52   2881
 101  * 48   2736
 102  * 156  1569
 103  * 168  1487
 104  * 160  1483
 105  * 28   1446
 106  * 1608 1379
 107  * 184  1305
 108  * 552  1270
 109  * 64   934
 110  * 320  891
 111  * 8    754
 112  *
 113  * Conclusions: more than the half of all allocations are <= 32 bytes.
 114  * But of these about 150,000 blocks, only a maximum of about 6,000 are
 115  * allocated together (including memory leaks..).
 116  * On the other side, only 935 of the 191573 or 0.5% were larger than 8kB
 117  * (362 or 0.2% larger than 16k).
 118  *
 119  * What makes the server really grow is the fragmentation of the heap,
 120  * and the fact that it can't shrink.
 121  * To cure this, we do the following:
 122  * - large blocks (>=11k) are mmapped on xalloc, and unmapped on xfree,
 123  *   so we don't need any free lists etc.
 124  *   As this needs 2 system calls, we only do this for the quite
 125  *   infrequent large (>=11k) blocks.
 126  * - instead of reinventing the wheel, we use system malloc for medium
 127  *   sized blocks (>256, <11k).
 128  * - for small blocks (<=256) we use an other approach:
 129  *   As we need many small blocks, and most ones for a short time,
 130  *   we don't go through the system malloc:
 131  *   for each fixed sizes a seperate list of free blocks is kept.
 132  *   to KISS (Keep it Small and Simple), we don't free them
 133  *   (not freeing a block of 32 bytes won't be worse than having fragmented
 134  *   a larger area on allocation).
 135  *   This way, we (almost) allways have a fitting free block right at hand,
 136  *   and don't have to walk any lists.
 137  */
 138
 139 /*
 140  * structure layout of a allocated block
 141  * unsigned long        size:
 142  *                              rounded up netto size for small and medium blocks
 143  *                              brutto size == mmap'ed area for large blocks
 144  * unsigned long        DEBUG ? MAGIC : unused
 145  * ....                 data
 146  * ( unsigned long      MAGIC2 ) only if SIZE_TAIL defined
 147  *
 148  */
 149
 150 /* use otherwise unused long in the header to store a magic */
 151 /* shouldn't this be removed for production release ? */
 152 #define XALLOC_DEBUG
 153
 154 #ifdef XALLOC_DEBUG
 155 /* Xfree fills the memory with a certain pattern (currently 0xF0) */
 156 /* this should really be removed for production release! */
 157 #define XFREE_ERASES
 158 #endif
 159
 160 /* this must be a multiple of SIZE_STEPS below */
 161 #define MAX_SMALL 264           /* quite many blocks of 264 */
 162
 163 #define MIN_LARGE (11*1024)
 164 /* worst case is 25% loss with a page size of 4k */
 165
 166 /* SIZE_STEPS defines the granularity of size of small blocks -
 167  * this makes blocks align to that, too! */
 168 #define SIZE_STEPS              (sizeof(double))
 169 #define SIZE_HEADER             (2*sizeof(long)) /* = sizeof(double) for 32bit */
 170 #ifdef XALLOC_DEBUG
 171 #if defined(__sparc__)
 172 #define SIZE_TAIL               (2*sizeof(long)) /* = sizeof(double) for 32bit */
 173 #else
 174 #define SIZE_TAIL               (sizeof(long))
 175 #endif
 176 #endif
 177
 178 #undef TAIL_SIZE
 179 #ifdef SIZE_TAIL
 180 #define TAIL_SIZE               SIZE_TAIL
 181 #else
 182 #define TAIL_SIZE               0
 183 #endif
 184
 185 #if defined (_LP64) || \
 186     defined(__alpha__) || defined(__alpha) || \
 187     defined(__ia64__) || defined(ia64) || \
 188     defined(__sparc64__) || \
 189     defined(__s390x__) || \
 190     defined(__amd64__) || defined(amd64) || \
 191     defined(__powerpc64__) || \
 192     (defined(sgi) && _MIPS_SZLONG == 64))
 193 #define MAGIC                   0x1404196414071968
 194 #define MAGIC_FREE              0x1506196615061966
 195 #define MAGIC2                  0x2515207525182079
 196 #else
 197 #define MAGIC                   0x14071968
 198 #define MAGIC_FREE              0x15061966
 199 #define MAGIC2                  0x25182079
 200 #endif
 201
 202 /* To get some statistics about memory allocation */
 203
 204 #ifdef XALLOC_LOG
 205 #define XALLOC_LOG_FILE "/tmp/Xalloc.log"       /* unsecure... */
 206 #define LOG_BODY(_body)                                 \
 207                 { FILE *f;                              \
 208                   f = fopen(XALLOC_LOG_FILE, "a");      \
 209                   if (NULL!=f) {                        \
 210                         _body;                          \
 211                         fclose(f);                      \
 212                   }                                     \
 213                 }
 214 #if defined(linux) && defined(i386)
 215 #define LOG_ALLOC(_fun, _size, _ret)                                            \
 216         {       unsigned long *from;                                            \
 217                 __asm__("movl %%ebp,%0" : /*OUT*/ "=r" (from) : /*IN*/ );       \
 218                 LOG_BODY(fprintf(f, "%s\t%i\t%p\t[%lu]\n", _fun, _size, _ret, *(from+1))) \
 219         }
 220 #else
 221 #define LOG_ALLOC(_fun, _size, _ret)                            \
 222         LOG_BODY(fprintf(f, "%s\t%i\t%p\n", _fun, _size, _ret))
 223 #endif
 224 #define LOG_REALLOC(_fun, _ptr, _size, _ret)                    \
 225         LOG_BODY(fprintf(f, "%s\t%p\t%i\t%p\n", _fun, _ptr, _size, _ret))
 226 #define LOG_FREE(_fun, _ptr)                                    \
 227         LOG_BODY(fprintf(f, "%s\t%p\n", _fun, _ptr))
 228 #else
 229 #define LOG_ALLOC(_fun, _size, _ret)
 230 #define LOG_REALLOC(_fun, _ptr, _size, _ret)
 231 #define LOG_FREE(_fun, _ptr)
 232 #endif /* XALLOC_LOG */
 233
 234 static unsigned long *free_lists[MAX_SMALL/SIZE_STEPS];
 235
 236 /*
 237  * systems that support it should define HAS_MMAP_ANON or MMAP_DEV_ZERO
 238  * and include the appropriate header files for
 239  * mmap(), munmap(), PROT_READ, PROT_WRITE, MAP_PRIVATE,
 240  * PAGE_SIZE or _SC_PAGESIZE (and MAP_ANON for HAS_MMAP_ANON).
 241  *
 242  * systems that don't support MAP_ANON fall through to the 2 fold behaviour
 243  */
 244
 245 #if defined(linux)
 246 #define HAS_MMAP_ANON
 247 #include <sys/types.h>
 248 #include <sys/mman.h>
 249 #include <asm/page.h>   /* PAGE_SIZE */
 250 #define HAS_SC_PAGESIZE /* _SC_PAGESIZE may be an enum for Linux */
 251 #define HAS_GETPAGESIZE
 252 #endif /* linux */
 253
 254 #if defined(__GNU__)
 255 #define HAS_MMAP_ANON
 256 #include <sys/types.h>
 257 #include <sys/mman.h>
 258 #include <mach/vm_param.h>     /* PAGE_SIZE */
 259 #define HAS_SC_PAGESIZE
 260 #define HAS_GETPAGESIZE
 261 #endif /* __GNU__ */
 262
 263 #if defined(CSRG_BASED)
 264 #define HAS_MMAP_ANON
 265 #define HAS_GETPAGESIZE
 266 #include <sys/types.h>
 267 #include <sys/mman.h>
 268 #endif /* CSRG_BASED */
 269
 270 #if defined(DGUX)
 271 #define HAS_GETPAGESIZE
 272 #define MMAP_DEV_ZERO
 273 #include <sys/types.h>
 274 #include <sys/mman.h>
 275 #include <unistd.h>
 276 #endif /* DGUX */
 277
 278 #if defined(SVR4) && !defined(DGUX)
 279 #define MMAP_DEV_ZERO
 280 #include <sys/types.h>
 281 #include <sys/mman.h>
 282 #include <unistd.h>
 283 #endif /* SVR4 && !DGUX */
 284
 285 #if defined(sun) && !defined(SVR4) /* SunOS */
 286 #define MMAP_DEV_ZERO   /* doesn't SunOS have MAP_ANON ?? */
 287 #define HAS_GETPAGESIZE
 288 #include <sys/types.h>
 289 #include <sys/mman.h>
 290 #endif /* sun && !SVR4 */
 291
 292 #ifdef XNO_SYSCONF
 293 #undef _SC_PAGESIZE
 294 #endif
 295
 296 #if defined(HAS_MMAP_ANON) || defined (MMAP_DEV_ZERO)
 297 static int pagesize;
 298 #endif
 299
 300 #ifdef MMAP_DEV_ZERO
 301 static int devzerofd = -1;
 302 #include <errno.h>
 303 #endif
 304
 305 /*
 306  * empty trap function for gdb. Breakpoint here
 307  * to find who tries to free a free area
 308  */
 309 void XfreeTrap(void)
 310 {
 311 }
 312
 313 _X_EXPORT void *
 314 Xalloc (unsigned long amount)
 315 {
 316     register unsigned long *ptr;
 317     int indx;
 318
 319     /* sanity checks */
 320
 321     /* zero size requested */
 322     if (amount == 0) {
 323         LOG_ALLOC("Xalloc=0", amount, 0);
 324         return NULL;
 325     }
 326     /* negative size (or size > 2GB) - what do we do? */
 327     if ((long)amount < 0) {
 328         /* Diagnostic */
 329 #ifdef FATALERRORS
 330         FatalError("Xalloc: Xalloc(<0)\n");
 331 #else
 332         ErrorF("Xalloc warning: Xalloc(<0) ignored..\n");
 333 #endif
 334         LOG_ALLOC("Xalloc<0", amount, 0);
 335         return NULL;
 336     }
 337
 338     /* alignment check */
 339 #if defined(__alpha__) || defined(__alpha) || \
 340     defined(__sparc__) || \
 341     defined(__mips__) || \
 342     defined(__powerpc__) || \
 343     defined(__arm32__) || \
 344     defined(__ia64__) || defined(ia64) || \
 345     defined(__s390x__) || defined(__s390__)
 346     amount = (amount + (sizeof(long)-1)) & ~(sizeof(long)-1);
 347 #endif
 348
 349     if (amount <= MAX_SMALL) {
 350         /*
 351          * small block
 352          */
 353         /* pick a ready to use small chunk */
 354         indx = (amount-1) / SIZE_STEPS;
 355         ptr = free_lists[indx];
 356         if (NULL == ptr) {
 357                 /* list empty - get 20 or 40 more */
 358                 /* amount = size rounded up */
 359                 amount = (indx+1) * SIZE_STEPS;
 360                 ptr = (unsigned long *)calloc(1,(amount+SIZE_HEADER+TAIL_SIZE)
 361                                                 * (amount<100 ? 40 : 20));
 362                 if (NULL!=ptr) {
 363                         int i;
 364                         unsigned long *p1, *p2;
 365                         p1 = 0;
 366                         p2 = (unsigned long *)((char *)ptr + SIZE_HEADER);
 367                         for (i=0; i<(amount<100 ? 40 : 20); i++) {
 368                                 p1 = p2;
 369                                 p1[-2] = amount;
 370 #ifdef XALLOC_DEBUG
 371                                 p1[-1] = MAGIC_FREE;
 372 #endif /* XALLOC_DEBUG */
 373 #ifdef SIZE_TAIL
 374                                 *(unsigned long *)((unsigned char *)p1 + amount) = MAGIC2;
 375 #endif /* SIZE_TAIL */
 376                                 p2 = (unsigned long *)((char *)p1 + SIZE_HEADER + amount + TAIL_SIZE);
 377                                 *(unsigned long **)p1 = p2;
 378                         }
 379                         /* last one has no next one */
 380                         *(unsigned long **)p1 = NULL;
 381                         /* put the second in the list */
 382                         free_lists[indx] = (unsigned long *)((char *)ptr + SIZE_HEADER + amount + TAIL_SIZE + SIZE_HEADER);
 383                         /* take the fist one */
 384                         ptr = (unsigned long *)((char *)ptr + SIZE_HEADER);
 385                         LOG_ALLOC("Xalloc-S", amount, ptr);
 386                         ptr[-1] = MAGIC;
 387                         return (void *)ptr;
 388                 } /* else fall through to 'Out of memory' */
 389         } else {
 390                 /* take that piece of mem out of the list */
 391                 free_lists[indx] = *((unsigned long **)ptr);
 392                 /* already has size (and evtl. magic) filled in */
 393 #ifdef XALLOC_DEBUG
 394                 ptr[-1] = MAGIC;
 395 #endif /* XALLOC_DEBUG */
 396                 LOG_ALLOC("Xalloc-S", amount, ptr);
 397                 return (void *)ptr;
 398         }
 399
 400 #if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
 401     } else if (amount >= MIN_LARGE) {
 402         /*
 403          * large block
 404          */
 405         /* mmapped malloc */
 406         /* round up amount */
 407         amount += SIZE_HEADER + TAIL_SIZE;
 408         /* round up brutto amount to a multiple of the page size */
 409         amount = (amount + pagesize-1) & ~(pagesize-1);
 410 #ifdef MMAP_DEV_ZERO
 411         ptr = (unsigned long *)mmap((caddr_t)0,
 412                                         (size_t)amount,
 413                                         PROT_READ | PROT_WRITE,
 414                                         MAP_PRIVATE,
 415                                         devzerofd,
 416                                         (off_t)0);
 417 #else
 418         ptr = (unsigned long *)mmap((caddr_t)0,
 419                                         (size_t)amount,
 420                                         PROT_READ | PROT_WRITE,
 421                                         MAP_ANON | MAP_PRIVATE,
 422                                         -1,
 423                                         (off_t)0);
 424 #endif
 425         if (-1!=(long)ptr) {
 426                 ptr[0] = amount - SIZE_HEADER - TAIL_SIZE;
 427 #ifdef XALLOC_DEBUG
 428                 ptr[1] = MAGIC;
 429 #endif /* XALLOC_DEBUG */
 430 #ifdef SIZE_TAIL
 431                 ((unsigned long *)((char *)ptr + amount - TAIL_SIZE))[0] = MAGIC2;
 432 #endif /* SIZE_TAIL */
 433                 ptr = (unsigned long *)((char *)ptr + SIZE_HEADER);
 434                 LOG_ALLOC("Xalloc-L", amount, ptr);
 435                 return (void *)ptr;
 436         } /* else fall through to 'Out of memory' */
 437 #endif /* HAS_MMAP_ANON || MMAP_DEV_ZERO */
 438     } else {
 439         /*
 440          * medium sized block
 441          */
 442         /* 'normal' malloc() */
 443         ptr=(unsigned long *)calloc(1,amount+SIZE_HEADER+TAIL_SIZE);
 444         if (ptr != (unsigned long *)NULL) {
 445                 ptr[0] = amount;
 446 #ifdef XALLOC_DEBUG
 447                 ptr[1] = MAGIC;
 448 #endif /* XALLOC_DEBUG */
 449 #ifdef SIZE_TAIL
 450                 *(unsigned long *)((char *)ptr + amount + SIZE_HEADER) = MAGIC2;
 451 #endif /* SIZE_TAIL */
 452                 ptr = (unsigned long *)((char *)ptr + SIZE_HEADER);
 453                 LOG_ALLOC("Xalloc-M", amount, ptr);
 454                 return (void *)ptr;
 455         }
 456     }
 457     if (Must_have_memory)
 458         FatalError("Out of memory");
 459     LOG_ALLOC("Xalloc-oom", amount, 0);
 460     return NULL;
 461 }
 462
 463 /*****************
 464  * XNFalloc
 465  * "no failure" realloc, alternate interface to Xalloc w/o Must_have_memory
 466  *****************/
 467
 468 _X_EXPORT pointer
 469 XNFalloc (unsigned long amount)
 470 {
 471     register pointer ptr;
 472
 473     /* zero size requested */
 474     if (amount == 0) {
 475         LOG_ALLOC("XNFalloc=0", amount, 0);
 476         return NULL;
 477     }
 478     /* negative size (or size > 2GB) - what do we do? */
 479     if ((long)amount < 0) {
 480         /* Diagnostic */
 481 #ifdef FATALERRORS
 482         FatalError("Xalloc: XNFalloc(<0)\n");
 483 #else
 484         ErrorF("Xalloc warning: XNFalloc(<0) ignored..\n");
 485 #endif
 486         LOG_ALLOC("XNFalloc<0", amount, 0);
 487         return (unsigned long *)NULL;
 488     }
 489     ptr = Xalloc(amount);
 490     if (!ptr)
 491     {
 492         FatalError("Out of memory");
 493     }
 494     return ptr;
 495 }
 496
 497 /*****************
 498  * Xcalloc
 499  *****************/
 500
 501 _X_EXPORT pointer
 502 Xcalloc (unsigned long amount)
 503 {
 504     pointer ret;
 505
 506     ret = Xalloc (amount);
 507     if (ret != 0
 508 #if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
 509             && (amount < MIN_LARGE)     /* mmaped anonymous mem is already cleared */
 510 #endif
 511        )
 512         bzero ((char *) ret, (int) amount);
 513     return ret;
 514 }
 515
 516 /*****************
 517  * XNFcalloc
 518  *****************/
 519 _X_EXPORT void *
 520 XNFcalloc (unsigned long amount)
 521 {
 522     pointer ret;
 523
 524     ret = XNFalloc (amount);
 525     if (ret != 0
 526 #if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
 527             && (amount < MIN_LARGE)     /* mmaped anonymous mem is already cleared */
 528 #endif
 529        )
 530         bzero ((char *) ret, (int) amount);
 531     return ret;
 532 }
 533
 534 /*****************
 535  * Xrealloc
 536  *****************/
 537
 538 _X_EXPORT void *
 539 Xrealloc (pointer ptr, unsigned long amount)
 540 {
 541     register unsigned long *new_ptr;
 542
 543     /* zero size requested */
 544     if (amount == 0) {
 545         if (ptr)
 546                 Xfree(ptr);
 547         LOG_REALLOC("Xrealloc=0", ptr, amount, 0);
 548         return NULL;
 549     }
 550     /* negative size (or size > 2GB) - what do we do? */
 551     if ((long)amount < 0) {
 552         /* Diagnostic */
 553 #ifdef FATALERRORS
 554         FatalError("Xalloc: Xrealloc(<0)\n");
 555 #else
 556         ErrorF("Xalloc warning: Xrealloc(<0) ignored..\n");
 557 #endif
 558         if (ptr)
 559                 Xfree(ptr);     /* ?? */
 560         LOG_REALLOC("Xrealloc<0", ptr, amount, 0);
 561         return NULL;
 562     }
 563
 564     new_ptr = Xalloc(amount);
 565     if ( (new_ptr) && (ptr) ) {
 566         unsigned long old_size;
 567         old_size = ((unsigned long *)ptr)[-2];
 568 #ifdef XALLOC_DEBUG
 569         if (MAGIC != ((unsigned long *)ptr)[-1]) {
 570             if (MAGIC_FREE == ((unsigned long *)ptr)[-1]) {
 571 #ifdef FATALERRORS
 572                 XfreeTrap();
 573                 FatalError("Xalloc error: range already freed in Xrealloc() :-(\n");
 574 #else
 575                 ErrorF("Xalloc error: range already freed in Xrealloc() :-(\a\n");
 576                 sleep(5);
 577                 XfreeTrap();
 578 #endif
 579                 LOG_REALLOC("Xalloc error: ranged already freed in Xrealloc() :-(",
 580                         ptr, amount, 0);
 581                 return NULL;
 582             }
 583 #ifdef FATALERRORS
 584             XfreeTrap();
 585                 FatalError("Xalloc error: header corrupt in Xrealloc() :-(\n");
 586 #else
 587                 ErrorF("Xalloc error: header corrupt in Xrealloc() :-(\n");
 588                 XfreeTrap();
 589 #endif
 590                 LOG_REALLOC("Xalloc error: header corrupt in Xrealloc() :-(",
 591                         ptr, amount, 0);
 592                 return NULL;
 593         }
 594 #endif /* XALLOC_DEBUG */
 595         /* copy min(old size, new size) */
 596         memcpy((char *)new_ptr, (char *)ptr, (amount < old_size ? amount : old_size));
 597     }
 598     if (ptr)
 599         Xfree(ptr);
 600     if (new_ptr) {
 601         LOG_REALLOC("Xrealloc", ptr, amount, new_ptr);
 602         return (void *)new_ptr;
 603     }
 604     if (Must_have_memory)
 605         FatalError("Out of memory");
 606     LOG_REALLOC("Xrealloc", ptr, amount, 0);
 607     return NULL;
 608 }
 609
 610 /*****************
 611  * XNFrealloc
 612  * "no failure" realloc, alternate interface to Xrealloc w/o Must_have_memory
 613  *****************/
 614
 615 _X_EXPORT void *
 616 XNFrealloc (pointer ptr, unsigned long amount)
 617 {
 618     if (( ptr = (pointer)Xrealloc( ptr, amount ) ) == NULL)
 619     {
 620         FatalError( "Out of memory" );
 621     }
 622     return ptr;
 623 }
 624
 625 /*****************
 626  *  Xfree
 627  *    calls free
 628  *****************/
 629
 630 _X_EXPORT void
 631 Xfree(pointer ptr)
 632 {
 633     unsigned long size;
 634     unsigned long *pheader;
 635
 636     /* free(NULL) IS valid :-(  - and widely used throughout the server.. */
 637     if (!ptr)
 638         return;
 639
 640     pheader = (unsigned long *)((char *)ptr - SIZE_HEADER);
 641 #ifdef XALLOC_DEBUG
 642     if (MAGIC != pheader[1]) {
 643         /* Diagnostic */
 644         if (MAGIC_FREE == pheader[1]) {
 645 #ifdef FATALERRORS
 646             XfreeTrap();
 647             FatalError("Xalloc error: range already freed in Xrealloc() :-(\n");
 648 #else
 649             ErrorF("Xalloc error: range already freed in Xrealloc() :-(\a\n");
 650             sleep(5);
 651             XfreeTrap();
 652 #endif
 653             LOG_FREE("Xalloc error: ranged already freed in Xrealloc() :-(", ptr);
 654             return;
 655         }
 656 #ifdef FATALERRORS
 657         XfreeTrap();
 658         FatalError("Xalloc error: Header corrupt in Xfree() :-(\n");
 659 #else
 660         ErrorF("Xalloc error: Header corrupt in Xfree() :-(\n");
 661         XfreeTrap();
 662 #endif
 663         LOG_FREE("Xalloc error:  Header corrupt in Xfree() :-(", ptr);
 664         return;
 665     }
 666 #endif /* XALLOC_DEBUG */
 667
 668     size = pheader[0];
 669     if (size <= MAX_SMALL) {
 670         int indx;
 671         /*
 672          * small block
 673          */
 674 #ifdef SIZE_TAIL
 675         if (MAGIC2 != *(unsigned long *)((char *)ptr + size)) {
 676                 /* Diagnostic */
 677 #ifdef FATALERRORS
 678                 XfreeTrap();
 679                 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));
 680 #else
 681                 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));
 682                 XfreeTrap();
 683 #endif
 684                 LOG_FREE("Xalloc error: Tail corrupt in Xfree() for small block", ptr);
 685                 return;
 686         }
 687 #endif /* SIZE_TAIL */
 688
 689 #ifdef XFREE_ERASES
 690         memset(ptr,0xF0,size);
 691 #endif /* XFREE_ERASES */
 692 #ifdef XALLOC_DEBUG
 693         pheader[1] = MAGIC_FREE;
 694 #endif
 695         /* put this small block at the head of the list */
 696         indx = (size-1) / SIZE_STEPS;
 697         *(unsigned long **)(ptr) = free_lists[indx];
 698         free_lists[indx] = (unsigned long *)ptr;
 699         LOG_FREE("Xfree", ptr);
 700         return;
 701
 702 #if defined(HAS_MMAP_ANON) || defined(MMAP_DEV_ZERO)
 703     } else if (size >= MIN_LARGE) {
 704         /*
 705          * large block
 706          */
 707 #ifdef SIZE_TAIL
 708         if (MAGIC2 != ((unsigned long *)((char *)ptr + size))[0]) {
 709                 /* Diagnostic */
 710 #ifdef FATALERRORS
 711             XfreeTrap();
 712                 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]);
 713 #else
 714                 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]);
 715                 XfreeTrap();
 716 #endif
 717                 LOG_FREE("Xalloc error: Tail corrupt in Xfree() for big block", ptr);
 718                 return;
 719         }
 720         size += SIZE_TAIL;
 721 #endif /* SIZE_TAIL */
 722
 723         LOG_FREE("Xfree", ptr);
 724         size += SIZE_HEADER;
 725         munmap((caddr_t)pheader, (size_t)size);
 726         /* no need to clear - mem is inaccessible after munmap.. */
 727 #endif /* HAS_MMAP_ANON */
 728
 729     } else {
 730         /*
 731          * medium sized block
 732          */
 733 #ifdef SIZE_TAIL
 734         if (MAGIC2 != *(unsigned long *)((char *)ptr + size)) {
 735                 /* Diagnostic */
 736 #ifdef FATALERRORS
 737             XfreeTrap();
 738                 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));
 739 #else
 740                 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));
 741                 XfreeTrap();
 742 #endif
 743                 LOG_FREE("Xalloc error: Tail corrupt in Xfree() for medium block", ptr);
 744                 return;
 745         }
 746 #endif /* SIZE_TAIL */
 747
 748 #ifdef XFREE_ERASES
 749         memset(pheader,0xF0,size+SIZE_HEADER);
 750 #endif /* XFREE_ERASES */
 751 #ifdef XALLOC_DEBUG
 752         pheader[1] = MAGIC_FREE;
 753 #endif
 754
 755         LOG_FREE("Xfree", ptr);
 756         free((char *)pheader);
 757     }
 758 }
 759
 760 void
 761 OsInitAllocator (void)
 762 {
 763     static Bool beenhere = FALSE;
 764
 765     if (beenhere)
 766         return;
 767     beenhere = TRUE;
 768
 769 #if defined(HAS_MMAP_ANON) || defined (MMAP_DEV_ZERO)
 770     pagesize = -1;
 771 #if defined(_SC_PAGESIZE) || defined(HAS_SC_PAGESIZE)
 772     pagesize = sysconf(_SC_PAGESIZE);
 773 #endif
 774 #ifdef _SC_PAGE_SIZE
 775     if (pagesize == -1)
 776         pagesize = sysconf(_SC_PAGE_SIZE);
 777 #endif
 778 #ifdef HAS_GETPAGESIZE
 779     if (pagesize == -1)
 780         pagesize = getpagesize();
 781 #endif
 782 #ifdef PAGE_SIZE
 783     if (pagesize == -1)
 784         pagesize = PAGE_SIZE;
 785 #endif
 786     if (pagesize == -1)
 787         FatalError("OsInitAllocator: Cannot determine page size\n");
 788 #endif
 789
 790     /* set up linked lists of free blocks */
 791     bzero ((char *) free_lists, MAX_SMALL/SIZE_STEPS*sizeof(unsigned long *));
 792
 793 #ifdef MMAP_DEV_ZERO
 794     /* open /dev/zero on systems that have mmap, but not MAP_ANON */
 795     if (devzerofd < 0) {
 796         if ((devzerofd = open("/dev/zero", O_RDWR, 0)) < 0)
 797             FatalError("OsInitAllocator: Cannot open /dev/zero (errno=%d)\n",
 798                         errno);
 799     }
 800 #endif
 801
 802 #ifdef XALLOC_LOG
 803     /* reset the log file to zero length */
 804     {
 805         FILE *f;
 806         f = fopen(XALLOC_LOG_FILE, "w");
 807         if (NULL!=f)
 808                 fclose(f);
 809     }
 810 #endif
 811 }
 812
 813 #else /* !INTERNAL_MALLOC */
 814 /* This is to avoid an empty .o */
 815 static int no_internal_xalloc;
 816 #endif /* INTERNAL_MALLOC */