1: /* Malloc implementation for multiple threads without lock contention.
    2:    Copyright (C) 2001,2002,2003,2004,2005,2006,2007
    3:    Free Software Foundation, Inc.
    4:    This file is part of the GNU C Library.
    5:    Contributed by Wolfram Gloger <wg@malloc.de>, 2001.
    6: 
    7:    The GNU C Library is free software; you can redistribute it and/or
    8:    modify it under the terms of the GNU Lesser General Public License as
    9:    published by the Free Software Foundation; either version 2.1 of the
   10:    License, or (at your option) any later version.
   11: 
   12:    The GNU C Library is distributed in the hope that it will be useful,
   13:    but WITHOUT ANY WARRANTY; without even the implied warranty of
   14:    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   15:    Lesser General Public License for more details.
   16: 
   17:    You should have received a copy of the GNU Lesser General Public
   18:    License along with the GNU C Library; see the file COPYING.LIB.  If not,
   19:    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   20:    Boston, MA 02111-1307, USA.  */
   21: 
   22: #include <stdbool.h>
   23: 
   24: /* Compile-time constants.  */
   25: 
   26: #define HEAP_MIN_SIZE (32*1024)
   27: #ifndef HEAP_MAX_SIZE
   28: # ifdef DEFAULT_MMAP_THRESHOLD_MAX
   29: #  define HEAP_MAX_SIZE (2 * DEFAULT_MMAP_THRESHOLD_MAX)
   30: # else
   31: #  define HEAP_MAX_SIZE (1024*1024) /* must be a power of two */
   32: # endif
   33: #endif
   34: 
   35: /* HEAP_MIN_SIZE and HEAP_MAX_SIZE limit the size of mmap()ed heaps
   36:    that are dynamically created for multi-threaded programs.  The
   37:    maximum size must be a power of two, for fast determination of
   38:    which heap belongs to a chunk.  It should be much larger than the
   39:    mmap threshold, so that requests with a size just below that
   40:    threshold can be fulfilled without creating too many heaps.  */
   41: 
   42: 
   43: #ifndef THREAD_STATS
   44: #define THREAD_STATS 0
   45: #endif
   46: 
   47: /* If THREAD_STATS is non-zero, some statistics on mutex locking are
   48:    computed.  */
   49: 
   50: /***************************************************************************/
   51: 
   52: #define top(ar_ptr) ((ar_ptr)->top)
   53: 
   54: /* A heap is a single contiguous memory region holding (coalesceable)
   55:    malloc_chunks.  It is allocated with mmap() and always starts at an
   56:    address aligned to HEAP_MAX_SIZE.  Not used unless compiling with
   57:    USE_ARENAS. */
   58: 
   59: typedef struct _heap_info {
   60:   mstate ar_ptr; /* Arena for this heap. */
   61:   struct _heap_info *prev; /* Previous heap. */
   62:   size_t size;   /* Current size in bytes. */
   63:   size_t mprotect_size; /* Size in bytes that has been mprotected
   64:                            PROT_READ|PROT_WRITE.  */
   65:   /* Make sure the following data is properly aligned, particularly
   66:      that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
   67:      MALLOC_ALIGNMENT. */
   68:   char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
   69: } heap_info;
   70: 
   71: /* Get a compile-time error if the heap_info padding is not correct
   72:    to make alignment work as expected in sYSMALLOc.  */
   73: extern int sanity_check_heap_info_alignment[(sizeof (heap_info)
   74:                                              + 2 * SIZE_SZ) % MALLOC_ALIGNMENT
   75:                                             ? -1 : 1];
   76: 
   77: /* Thread specific data */
   78: 
   79: static tsd_key_t arena_key;
   80: static mutex_t list_lock;
   81: 
   82: #if THREAD_STATS
   83: static int stat_n_heaps;
   84: #define THREAD_STAT(x) x
   85: #else
   86: #define THREAD_STAT(x) do ; while(0)
   87: #endif
   88: 
   89: /* Mapped memory in non-main arenas (reliable only for NO_THREADS). */
   90: static unsigned long arena_mem;
   91: 
   92: /* Already initialized? */
   93: int __malloc_initialized = -1;
   94: 
   95: /**************************************************************************/
   96: 
   97: #if USE_ARENAS
   98: 
   99: /* arena_get() acquires an arena and locks the corresponding mutex.
  100:    First, try the one last locked successfully by this thread.  (This
  101:    is the common case and handled with a macro for speed.)  Then, loop
  102:    once over the circularly linked list of arenas.  If no arena is
  103:    readily available, create a new one.  In this latter case, `size'
  104:    is just a hint as to how much memory will be required immediately
  105:    in the new arena. */
  106: 
  107: #define arena_get(ptr, size) do { \
  108:   Void_t *vptr = NULL; \
  109:   ptr = (mstate)tsd_getspecific(arena_key, vptr); \
  110:   if(ptr && !mutex_trylock(&ptr->mutex)) { \
  111:     THREAD_STAT(++(ptr->stat_lock_direct)); \
  112:   } else \
  113:     ptr = arena_get2(ptr, (size)); \
  114: } while(0)
  115: 
  116: /* find the heap and corresponding arena for a given ptr */
  117: 
  118: #define heap_for_ptr(ptr) \
  119:  ((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1)))
  120: #define arena_for_chunk(ptr) \
  121:  (chunk_non_main_arena(ptr) ? heap_for_ptr(ptr)->ar_ptr : &main_arena)
  122: 
  123: #else /* !USE_ARENAS */
  124: 
  125: /* There is only one arena, main_arena. */
  126: 
  127: #if THREAD_STATS
  128: #define arena_get(ar_ptr, sz) do { \
  129:   ar_ptr = &main_arena; \
  130:   if(!mutex_trylock(&ar_ptr->mutex)) \
  131:     ++(ar_ptr->stat_lock_direct); \
  132:   else { \
  133:     (void)mutex_lock(&ar_ptr->mutex); \
  134:     ++(ar_ptr->stat_lock_wait); \
  135:   } \
  136: } while(0)
  137: #else
  138: #define arena_get(ar_ptr, sz) do { \
  139:   ar_ptr = &main_arena; \
  140:   (void)mutex_lock(&ar_ptr->mutex); \
  141: } while(0)
  142: #endif
  143: #define arena_for_chunk(ptr) (&main_arena)
  144: 
  145: #endif /* USE_ARENAS */
  146: 
  147: /**************************************************************************/
  148: 
  149: #ifndef NO_THREADS
  150: 
  151: /* atfork support.  */
  152: 
  153: static __malloc_ptr_t (*save_malloc_hook) (size_t __size,
  154:                                            __const __malloc_ptr_t);
  155: # if !defined _LIBC || (defined SHARED && !USE___THREAD)
  156: static __malloc_ptr_t (*save_memalign_hook) (size_t __align, size_t __size,
  157:                                              __const __malloc_ptr_t);
  158: # endif
  159: static void           (*save_free_hook) (__malloc_ptr_t __ptr,
  160:                                          __const __malloc_ptr_t);
  161: static Void_t*        save_arena;
  162: 
  163: /* Magic value for the thread-specific arena pointer when
  164:    malloc_atfork() is in use.  */
  165: 
  166: #define ATFORK_ARENA_PTR ((Void_t*)-1)
  167: 
  168: /* The following hooks are used while the `atfork' handling mechanism
  169:    is active. */
  170: 
  171: static Void_t*
  172: malloc_atfork(size_t sz, const Void_t *caller)
  173: {
  174:   Void_t *vptr = NULL;
  175:   Void_t *victim;
  176: 
  177:   tsd_getspecific(arena_key, vptr);
  178:   if(vptr == ATFORK_ARENA_PTR) {
  179:     /* We are the only thread that may allocate at all.  */
  180:     if(save_malloc_hook != malloc_check) {
  181:       return _int_malloc(&main_arena, sz);
  182:     } else {
  183:       if(top_check()<0)
  184:         return 0;
  185:       victim = _int_malloc(&main_arena, sz+1);
  186:       return mem2mem_check(victim, sz);
  187:     }
  188:   } else {
  189:     /* Suspend the thread until the `atfork' handlers have completed.
  190:        By that time, the hooks will have been reset as well, so that
  191:        mALLOc() can be used again. */
  192:     (void)mutex_lock(&list_lock);
  193:     (void)mutex_unlock(&list_lock);
  194:     return public_mALLOc(sz);
  195:   }
  196: }
  197: 
  198: static void
  199: free_atfork(Void_t* mem, const Void_t *caller)
  200: {
  201:   Void_t *vptr = NULL;
  202:   mstate ar_ptr;
  203:   mchunkptr p;                          /* chunk corresponding to mem */
  204: 
  205:   if (mem == 0)                              /* free(0) has no effect */
  206:     return;
  207: 
  208:   p = mem2chunk(mem);         /* do not bother to replicate free_check here */
  209: 
  210: #if HAVE_MMAP
  211:   if (chunk_is_mmapped(p))                       /* release mmapped memory. */
  212:   {
  213:     munmap_chunk(p);
  214:     return;
  215:   }
  216: #endif
  217: 
  218:   ar_ptr = arena_for_chunk(p);
  219:   tsd_getspecific(arena_key, vptr);
  220:   if(vptr != ATFORK_ARENA_PTR)
  221:     (void)mutex_lock(&ar_ptr->mutex);
  222:   _int_free(ar_ptr, mem);
  223:   if(vptr != ATFORK_ARENA_PTR)
  224:     (void)mutex_unlock(&ar_ptr->mutex);
  225: }
  226: 
  227: 
  228: /* Counter for number of times the list is locked by the same thread.  */
  229: static unsigned int atfork_recursive_cntr;
  230: 
  231: /* The following two functions are registered via thread_atfork() to
  232:    make sure that the mutexes remain in a consistent state in the
  233:    fork()ed version of a thread.  Also adapt the malloc and free hooks
  234:    temporarily, because the `atfork' handler mechanism may use
  235:    malloc/free internally (e.g. in LinuxThreads). */
  236: 
  237: static void
  238: ptmalloc_lock_all (void)
  239: {
  240:   mstate ar_ptr;
  241: 
  242:   if(__malloc_initialized < 1)
  243:     return;
  244:   if (mutex_trylock(&list_lock))
  245:     {
  246:       Void_t *my_arena;
  247:       tsd_getspecific(arena_key, my_arena);
  248:       if (my_arena == ATFORK_ARENA_PTR)
  249:         /* This is the same thread which already locks the global list.
  250:            Just bump the counter.  */
  251:         goto out;
  252: 
  253:       /* This thread has to wait its turn.  */
  254:       (void)mutex_lock(&list_lock);
  255:     }
  256:   for(ar_ptr = &main_arena;;) {
  257:     (void)mutex_lock(&ar_ptr->mutex);
  258:     ar_ptr = ar_ptr->next;
  259:     if(ar_ptr == &main_arena) break;
  260:   }
  261:   save_malloc_hook = __malloc_hook;
  262:   save_free_hook = __free_hook;
  263:   __malloc_hook = malloc_atfork;
  264:   __free_hook = free_atfork;
  265:   /* Only the current thread may perform malloc/free calls now. */
  266:   tsd_getspecific(arena_key, save_arena);
  267:   tsd_setspecific(arena_key, ATFORK_ARENA_PTR);
  268:  out:
  269:   ++atfork_recursive_cntr;
  270: }
  271: 
  272: static void
  273: ptmalloc_unlock_all (void)
  274: {
  275:   mstate ar_ptr;
  276: 
  277:   if(__malloc_initialized < 1)
  278:     return;
  279:   if (--atfork_recursive_cntr != 0)
  280:     return;
  281:   tsd_setspecific(arena_key, save_arena);
  282:   __malloc_hook = save_malloc_hook;
  283:   __free_hook = save_free_hook;
  284:   for(ar_ptr = &main_arena;;) {
  285:     (void)mutex_unlock(&ar_ptr->mutex);
  286:     ar_ptr = ar_ptr->next;
  287:     if(ar_ptr == &main_arena) break;
  288:   }
  289:   (void)mutex_unlock(&list_lock);
  290: }
  291: 
  292: #ifdef __linux__
  293: 
  294: /* In NPTL, unlocking a mutex in the child process after a
  295:    fork() is currently unsafe, whereas re-initializing it is safe and
  296:    does not leak resources.  Therefore, a special atfork handler is
  297:    installed for the child. */
  298: 
  299: static void
  300: ptmalloc_unlock_all2 (void)
  301: {
  302:   mstate ar_ptr;
  303: 
  304:   if(__malloc_initialized < 1)
  305:     return;
  306: #if defined _LIBC || defined MALLOC_HOOKS
  307:   tsd_setspecific(arena_key, save_arena);
  308:   __malloc_hook = save_malloc_hook;
  309:   __free_hook = save_free_hook;
  310: #endif
  311:   for(ar_ptr = &main_arena;;) {
  312:     mutex_init(&ar_ptr->mutex);
  313:     ar_ptr = ar_ptr->next;
  314:     if(ar_ptr == &main_arena) break;
  315:   }
  316:   mutex_init(&list_lock);
  317:   atfork_recursive_cntr = 0;
  318: }
  319: 
  320: #else
  321: 
  322: #define ptmalloc_unlock_all2 ptmalloc_unlock_all
  323: 
  324: #endif
  325: 
  326: #endif /* !defined NO_THREADS */
  327: 
  328: /* Initialization routine. */
  329: #ifdef _LIBC
  330: #include <string.h>
  331: extern char **_environ;
  332: 
  333: static char *
  334: internal_function
  335: next_env_entry (char ***position)
  336: {
  337:   char **current = *position;
  338:   char *result = NULL;
  339: 
  340:   while (*current != NULL)
  341:     {
  342:       if (__builtin_expect ((*current)[0] == 'M', 0)
  343:           && (*current)[1] == 'A'
  344:           && (*current)[2] == 'L'
  345:           && (*current)[3] == 'L'
  346:           && (*current)[4] == 'O'
  347:           && (*current)[5] == 'C'
  348:           && (*current)[6] == '_')
  349:         {
  350:           result = &(*current)[7];
  351: 
  352:           /* Save current position for next visit.  */
  353:           *position = ++current;
  354: 
  355:           break;
  356:         }
  357: 
  358:       ++current;
  359:     }
  360: 
  361:   return result;
  362: }
  363: #endif /* _LIBC */
  364: 
  365: /* Set up basic state so that _int_malloc et al can work.  */
  366: static void
  367: ptmalloc_init_minimal (void)
  368: {
  369: #if DEFAULT_TOP_PAD != 0
  370:   mp_.top_pad        = DEFAULT_TOP_PAD;
  371: #endif
  372:   mp_.n_mmaps_max    = DEFAULT_MMAP_MAX;
  373:   mp_.mmap_threshold = DEFAULT_MMAP_THRESHOLD;
  374:   mp_.trim_threshold = DEFAULT_TRIM_THRESHOLD;
  375:   mp_.pagesize       = malloc_getpagesize;
  376: }
  377: 
  378: 
  379: #ifdef _LIBC
  380: # ifdef SHARED
  381: static void *
  382: __failing_morecore (ptrdiff_t d)
  383: {
  384:   return (void *) MORECORE_FAILURE;
  385: }
  386: 
  387: extern struct dl_open_hook *_dl_open_hook;
  388: libc_hidden_proto (_dl_open_hook);
  389: # endif
  390: 
  391: # if defined SHARED && !USE___THREAD
  392: /* This is called by __pthread_initialize_minimal when it needs to use
  393:    malloc to set up the TLS state.  We cannot do the full work of
  394:    ptmalloc_init (below) until __pthread_initialize_minimal has finished,
  395:    so it has to switch to using the special startup-time hooks while doing
  396:    those allocations.  */
  397: void
  398: __libc_malloc_pthread_startup (bool first_time)
  399: {
  400:   if (first_time)
  401:     {
  402:       ptmalloc_init_minimal ();
  403:       save_malloc_hook = __malloc_hook;
  404:       save_memalign_hook = __memalign_hook;
  405:       save_free_hook = __free_hook;
  406:       __malloc_hook = malloc_starter;
  407:       __memalign_hook = memalign_starter;
  408:       __free_hook = free_starter;
  409:     }
  410:   else
  411:     {
  412:       __malloc_hook = save_malloc_hook;
  413:       __memalign_hook = save_memalign_hook;
  414:       __free_hook = save_free_hook;
  415:     }
  416: }
  417: # endif
  418: #endif
  419: 
  420: static void
  421: ptmalloc_init (void)
  422: {
  423: #if __STD_C
  424:   const char* s;
  425: #else
  426:   char* s;
  427: #endif
  428:   int secure = 0;
  429: 
  430:   if(__malloc_initialized >= 0) return;
  431:   __malloc_initialized = 0;
  432: 
  433: #ifdef _LIBC
  434: # if defined SHARED && !USE___THREAD
  435:   /* ptmalloc_init_minimal may already have been called via
  436:      __libc_malloc_pthread_startup, above.  */
  437:   if (mp_.pagesize == 0)
  438: # endif
  439: #endif
  440:     ptmalloc_init_minimal();
  441: 
  442: #ifndef NO_THREADS
  443: # if defined _LIBC
  444:   /* We know __pthread_initialize_minimal has already been called,
  445:      and that is enough.  */
  446: #   define NO_STARTER
  447: # endif
  448: # ifndef NO_STARTER
  449:   /* With some threads implementations, creating thread-specific data
  450:      or initializing a mutex may call malloc() itself.  Provide a
  451:      simple starter version (realloc() won't work). */
  452:   save_malloc_hook = __malloc_hook;
  453:   save_memalign_hook = __memalign_hook;
  454:   save_free_hook = __free_hook;
  455:   __malloc_hook = malloc_starter;
  456:   __memalign_hook = memalign_starter;
  457:   __free_hook = free_starter;
  458: #  ifdef _LIBC
  459:   /* Initialize the pthreads interface. */
  460:   if (__pthread_initialize != NULL)
  461:     __pthread_initialize();
  462: #  endif /* !defined _LIBC */
  463: # endif /* !defined NO_STARTER */
  464: #endif /* !defined NO_THREADS */
  465:   mutex_init(&main_arena.mutex);
  466:   main_arena.next = &main_arena;
  467: 
  468: #if defined _LIBC && defined SHARED
  469:   /* In case this libc copy is in a non-default namespace, never use brk.
  470:      Likewise if dlopened from statically linked program.  */
  471:   Dl_info di;
  472:   struct link_map *l;
  473: 
  474:   if (_dl_open_hook != NULL
  475:       || (_dl_addr (ptmalloc_init, &di, &l, NULL) != 0
  476:           && l->l_ns != LM_ID_BASE))
  477:     __morecore = __failing_morecore;
  478: #endif
  479: 
  480:   mutex_init(&list_lock);
  481:   tsd_key_create(&arena_key, NULL);
  482:   tsd_setspecific(arena_key, (Void_t *)&main_arena);
  483:   thread_atfork(ptmalloc_lock_all, ptmalloc_unlock_all, ptmalloc_unlock_all2);
  484: #ifndef NO_THREADS
  485: # ifndef NO_STARTER
  486:   __malloc_hook = save_malloc_hook;
  487:   __memalign_hook = save_memalign_hook;
  488:   __free_hook = save_free_hook;
  489: # else
  490: #  undef NO_STARTER
  491: # endif
  492: #endif
  493: #ifdef _LIBC
  494:   secure = __libc_enable_secure;
  495:   s = NULL;
  496:   if (__builtin_expect (_environ != NULL, 1))
  497:     {
  498:       char **runp = _environ;
  499:       char *envline;
  500: 
  501:       while (__builtin_expect ((envline = next_env_entry (&runp)) != NULL,
  502:                                0))
  503:         {
  504:           size_t len = strcspn (envline, "=");
  505: 
  506:           if (envline[len] != '=')
  507:             /* This is a "MALLOC_" variable at the end of the string
  508:                without a '=' character.  Ignore it since otherwise we
  509:                will access invalid memory below.  */
  510:             continue;
  511: 
  512:           switch (len)
  513:             {
  514:             case 6:
  515:               if (memcmp (envline, "CHECK_", 6) == 0)
  516:                 s = &envline[7];
  517:               break;
  518:             case 8:
  519:               if (! secure)
  520:                 {
  521:                   if (memcmp (envline, "TOP_PAD_", 8) == 0)
  522:                     mALLOPt(M_TOP_PAD, atoi(&envline[9]));
  523:                   else if (memcmp (envline, "PERTURB_", 8) == 0)
  524:                     mALLOPt(M_PERTURB, atoi(&envline[9]));
  525:                 }
  526:               break;
  527:             case 9:
  528:               if (! secure && memcmp (envline, "MMAP_MAX_", 9) == 0)
  529:                 mALLOPt(M_MMAP_MAX, atoi(&envline[10]));
  530:               break;
  531:             case 15:
  532:               if (! secure)
  533:                 {
  534:                   if (memcmp (envline, "TRIM_THRESHOLD_", 15) == 0)
  535:                     mALLOPt(M_TRIM_THRESHOLD, atoi(&envline[16]));
  536:                   else if (memcmp (envline, "MMAP_THRESHOLD_", 15) == 0)
  537:                     mALLOPt(M_MMAP_THRESHOLD, atoi(&envline[16]));
  538:                 }
  539:               break;
  540:             default:
  541:               break;
  542:             }
  543:         }
  544:     }
  545: #else
  546:   if (! secure)
  547:     {
  548:       if((s = getenv("MALLOC_TRIM_THRESHOLD_")))
  549:         mALLOPt(M_TRIM_THRESHOLD, atoi(s));
  550:       if((s = getenv("MALLOC_TOP_PAD_")))
  551:         mALLOPt(M_TOP_PAD, atoi(s));
  552:       if((s = getenv("MALLOC_PERTURB_")))
  553:         mALLOPt(M_PERTURB, atoi(s));
  554:       if((s = getenv("MALLOC_MMAP_THRESHOLD_")))
  555:         mALLOPt(M_MMAP_THRESHOLD, atoi(s));
  556:       if((s = getenv("MALLOC_MMAP_MAX_")))
  557:         mALLOPt(M_MMAP_MAX, atoi(s));
  558:     }
  559:   s = getenv("MALLOC_CHECK_");
  560: #endif
  561:   if(s && s[0]) {
  562:     mALLOPt(M_CHECK_ACTION, (int)(s[0] - '0'));
  563:     if (check_action != 0)
  564:       __malloc_check_init();
  565:   }
  566:   if(__malloc_initialize_hook != NULL)
  567:     (*__malloc_initialize_hook)();
  568:   __malloc_initialized = 1;
  569: }
  570: 
  571: /* There are platforms (e.g. Hurd) with a link-time hook mechanism. */
  572: #ifdef thread_atfork_static
  573: thread_atfork_static(ptmalloc_lock_all, ptmalloc_unlock_all, \
  574:                      ptmalloc_unlock_all2)
  575: #endif
  576: 
  577: ^L
  578: 
  579: /* Managing heaps and arenas (for concurrent threads) */
  580: 
  581: #if USE_ARENAS
  582: 
  583: #if MALLOC_DEBUG > 1
  584: 
  585: /* Print the complete contents of a single heap to stderr. */
  586: 
  587: static void
  588: #if __STD_C
  589: dump_heap(heap_info *heap)
  590: #else
  591: dump_heap(heap) heap_info *heap;
  592: #endif
  593: {
  594:   char *ptr;