/*

 * Copyright (c) 2005 Hewlett-Packard Development Company, L.P.

 *

 * This file may be redistributed and/or modified under the

 * terms of the GNU General Public License as published by the Free Software

 * Foundation; either version 2, or (at your option) any later version.

 *

 * It is distributed in the hope that it will be useful, but WITHOUT ANY

 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

 * FOR A PARTICULAR PURPOSE.  See the GNU General Public License in the

 * file COPYING for more details.

 */

#if defined(HAVE_CONFIG_H)

# include "config.h"

#endif

#ifdef DONT_USE_MMAP /* for testing */

# undef HAVE_MMAP

#endif

#define AO_REQUIRE_CAS

#include "atomic_ops_malloc.h"

#include <string.h>     /* for ffs, which is assumed reentrant. */

#include <stdlib.h>

#include <assert.h>

#ifdef AO_TRACE_MALLOC

# include <stdio.h>

# include <pthread.h>

#endif

#if defined(AO_ADDRESS_SANITIZER) && !defined(AO_NO_MALLOC_POISON)

  /* #include "sanitizer/asan_interface.h" */

  void __asan_poison_memory_region(void *, size_t);

  void __asan_unpoison_memory_region(void *, size_t);

# define ASAN_POISON_MEMORY_REGION(addr, size) \

                __asan_poison_memory_region(addr, size)

# define ASAN_UNPOISON_MEMORY_REGION(addr, size) \

                __asan_unpoison_memory_region(addr, size)

#else

# define ASAN_POISON_MEMORY_REGION(addr, size) (void)0

# define ASAN_UNPOISON_MEMORY_REGION(addr, size) (void)0

#endif /* !AO_ADDRESS_SANITIZER */

#if (defined(_WIN32_WCE) || defined(__MINGW32CE__)) && !defined(AO_HAVE_abort)

# define abort() _exit(-1) /* there is no abort() in WinCE */

#endif

/*

 * We round up each allocation request to the next power of two

 * minus one word.

 * We keep one stack of free objects for each size.  Each object

 * has an initial word (offset -sizeof(AO_t) from the visible pointer)

 * which contains either

 *      The binary log of the object size in bytes (small objects)

 *      The object size (a multiple of CHUNK_SIZE) for large objects.

 * The second case only arises if mmap-based allocation is supported.

 * We align the user-visible part of each object on a GRANULARITY

 * byte boundary.  That means that the actual (hidden) start of

 * the object starts a word before this boundary.

 */

#ifndef LOG_MAX_SIZE

# define LOG_MAX_SIZE 16

        /* We assume that 2**LOG_MAX_SIZE is a multiple of page size. */

#endif

#ifndef ALIGNMENT

# define ALIGNMENT 16

        /* Assumed to be at least sizeof(AO_t).         */

#endif

#define CHUNK_SIZE (1 << LOG_MAX_SIZE)

#ifndef AO_INITIAL_HEAP_SIZE

#  define AO_INITIAL_HEAP_SIZE (2*(LOG_MAX_SIZE+1)*CHUNK_SIZE)

#endif

char AO_initial_heap[AO_INITIAL_HEAP_SIZE];

static volatile AO_t initial_heap_ptr = (AO_t)AO_initial_heap;

#if defined(HAVE_MMAP)

#include <sys/types.h>

#include <sys/stat.h>

#include <fcntl.h>

#include <sys/mman.h>

#if defined(MAP_ANONYMOUS) || defined(MAP_ANON)

# define USE_MMAP_ANON

#endif

#ifdef USE_MMAP_FIXED

# define GC_MMAP_FLAGS (MAP_FIXED | MAP_PRIVATE)

        /* Seems to yield better performance on Solaris 2, but can      */

        /* be unreliable if something is already mapped at the address. */

#else

# define GC_MMAP_FLAGS MAP_PRIVATE

#endif

#ifdef USE_MMAP_ANON

# if defined(CPPCHECK)

#   define OPT_MAP_ANON 0x20 /* taken from linux */

# elif defined(MAP_ANONYMOUS)

#   define OPT_MAP_ANON MAP_ANONYMOUS

# else

#   define OPT_MAP_ANON MAP_ANON

# endif

#else

# include <unistd.h> /* for close() */

# define OPT_MAP_ANON 0

#endif

static volatile AO_t mmap_enabled = 0;

void

AO_malloc_enable_mmap(void)

{

# if defined(__sun)

    AO_store_release(&mmap_enabled, 1);

            /* Workaround for Sun CC */

# else

    AO_store(&mmap_enabled, 1);

# endif

}

static char *get_mmaped(size_t sz)

{

  char * result;

# ifdef USE_MMAP_ANON

#   define zero_fd -1

# else

    int zero_fd;

# endif

  assert(!(sz & (CHUNK_SIZE - 1)));

  if (!mmap_enabled)

    return 0;

# ifndef USE_MMAP_ANON

    zero_fd = open("/dev/zero", O_RDONLY);

    if (zero_fd == -1)

      return 0;

# endif

  result = mmap(0, sz, PROT_READ | PROT_WRITE,

                GC_MMAP_FLAGS | OPT_MAP_ANON, zero_fd, 0/* offset */);

# ifndef USE_MMAP_ANON

    close(zero_fd);

# endif

  if (AO_EXPECT_FALSE(result == MAP_FAILED))

    result = NULL;

  return result;

}

#ifndef SIZE_MAX

# include <limits.h>

#endif

#if defined(SIZE_MAX) && !defined(CPPCHECK)

# define AO_SIZE_MAX ((size_t)SIZE_MAX)

            /* Extra cast to workaround some buggy SIZE_MAX definitions. */

#else

# define AO_SIZE_MAX (~(size_t)0)

#endif

/* Saturated addition of size_t values.  Used to avoid value wrap       */

/* around on overflow.  The arguments should have no side effects.      */

#define SIZET_SAT_ADD(a, b) \

    (AO_EXPECT_FALSE((a) >= AO_SIZE_MAX - (b)) ? AO_SIZE_MAX : (a) + (b))

/* Allocate an object of size (incl. header) of size > CHUNK_SIZE.      */

/* sz includes space for an AO_t-sized header.                          */

static char *

AO_malloc_large(size_t sz)

{

  char *result;

  /* The header will force us to waste ALIGNMENT bytes, incl. header.   */

  /* Round to multiple of CHUNK_SIZE.                                   */

  sz = SIZET_SAT_ADD(sz, ALIGNMENT + CHUNK_SIZE - 1) & ~(CHUNK_SIZE - 1);

  assert(sz > LOG_MAX_SIZE);

  result = get_mmaped(sz);

  if (AO_EXPECT_FALSE(NULL == result))

    return NULL;

  result += ALIGNMENT;

  ((AO_t *)result)[-1] = (AO_t)sz;

  return result;

}

static void

AO_free_large(char * p)

{

  AO_t sz = ((AO_t *)p)[-1];

  if (munmap(p - ALIGNMENT, (size_t)sz) != 0)

    abort();  /* Programmer error.  Not really async-signal-safe, but ... */

}

#else /*  No MMAP */

void

AO_malloc_enable_mmap(void)

{

}

#define get_mmaped(sz) ((char*)0)

#define AO_malloc_large(sz) ((char*)0)

#define AO_free_large(p) abort()

                /* Programmer error.  Not really async-signal-safe, but ... */

#endif /* No MMAP */

static char *

get_chunk(void)

{

  char *my_chunk_ptr;

  for (;;) {

    char *initial_ptr = (char *)AO_load(&initial_heap_ptr);

    my_chunk_ptr = (char *)(((AO_t)initial_ptr + (ALIGNMENT - 1))

                            & ~(ALIGNMENT - 1));

    if (initial_ptr != my_chunk_ptr)

      {

        /* Align correctly.  If this fails, someone else did it for us. */

        (void)AO_compare_and_swap_acquire(&initial_heap_ptr,

                                    (AO_t)initial_ptr, (AO_t)my_chunk_ptr);

      }

    if (AO_EXPECT_FALSE(my_chunk_ptr - AO_initial_heap

                        > AO_INITIAL_HEAP_SIZE - CHUNK_SIZE))

      break;

    if (AO_compare_and_swap(&initial_heap_ptr, (AO_t)my_chunk_ptr,

                            (AO_t)(my_chunk_ptr + CHUNK_SIZE))) {

      return my_chunk_ptr;

    }

  }

  /* We failed.  The initial heap is used up.   */

  my_chunk_ptr = get_mmaped(CHUNK_SIZE);

  assert (!((AO_t)my_chunk_ptr & (ALIGNMENT-1)));

  return my_chunk_ptr;

}

/* Object free lists.  Ith entry corresponds to objects         */

/* of total size 2**i bytes.                                    */

AO_stack_t AO_free_list[LOG_MAX_SIZE+1];

/* Break up the chunk, and add it to the object free list for   */

/* the given size.  We have exclusive access to chunk.          */

static void add_chunk_as(void * chunk, unsigned log_sz)

{

  size_t ofs, limit;

  size_t sz = (size_t)1 << log_sz;

  assert (CHUNK_SIZE >= sz);

  limit = (size_t)CHUNK_SIZE - sz;

  for (ofs = ALIGNMENT - sizeof(AO_t); ofs <= limit; ofs += sz) {

    ASAN_POISON_MEMORY_REGION((char *)chunk + ofs + sizeof(AO_t),

                              sz - sizeof(AO_t));

    AO_stack_push(&AO_free_list[log_sz], (AO_t *)((char *)chunk + ofs));

  }

}

static const unsigned char msbs[16] = {

  0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4

};

/* Return the position of the most significant set bit in the   */

/* argument.                                                    */

/* We follow the conventions of ffs(), i.e. the least           */

/* significant bit is number one.                               */

static unsigned msb(size_t s)

{

  unsigned result = 0;

  if ((s & 0xff) != s) {

#   if (__SIZEOF_SIZE_T__ == 8) && !defined(CPPCHECK)

      unsigned v = (unsigned)(s >> 32);

      if (AO_EXPECT_FALSE(v != 0))

        {

          s = v;

          result += 32;

        }

#   elif __SIZEOF_SIZE_T__ == 4

      /* No op. */

#   else

      unsigned v;

      /* The following is a tricky code ought to be equivalent to       */

      /* "(v = s >> 32) != 0" but suppresses warnings on 32-bit arch's. */

#     define SIZEOF_SIZE_T_GT_4 (sizeof(size_t) > 4)

      if (SIZEOF_SIZE_T_GT_4

          && (v = (unsigned)(s >> (SIZEOF_SIZE_T_GT_4 ? 32 : 0))) != 0)

        {

          s = v;

          result += 32;

        }

#   endif /* !defined(__SIZEOF_SIZE_T__) */

    if (AO_EXPECT_FALSE((s >> 16) != 0))

      {

        s >>= 16;

        result += 16;

      }

    if ((s >> 8) != 0)

      {

        s >>= 8;

        result += 8;

      }

  }

  if (s > 15)

    {

      s >>= 4;

      result += 4;

    }

  result += msbs[s];

  return result;

}

void *

AO_malloc(size_t sz)

{

  AO_t *result;

  unsigned log_sz;

  if (AO_EXPECT_FALSE(sz > CHUNK_SIZE - sizeof(AO_t)))

    return AO_malloc_large(sz);

  log_sz = msb(sz + (sizeof(AO_t) - 1));

  assert(log_sz <= LOG_MAX_SIZE);

  assert(((size_t)1 << log_sz) >= sz + sizeof(AO_t));

  result = AO_stack_pop(AO_free_list+log_sz);

  while (AO_EXPECT_FALSE(NULL == result)) {

    void * chunk = get_chunk();

    if (AO_EXPECT_FALSE(NULL == chunk))

      return NULL;

    add_chunk_as(chunk, log_sz);

    result = AO_stack_pop(AO_free_list+log_sz);

  }

  *result = log_sz;

# ifdef AO_TRACE_MALLOC

    fprintf(stderr, "%p: AO_malloc(%lu) = %p\n",

            (void *)pthread_self(), (unsigned long)sz, (void *)(result + 1));

# endif

  ASAN_UNPOISON_MEMORY_REGION(result + 1, sz);

  return result + 1;

}

void

AO_free(void *p)

{

  AO_t *base;

  int log_sz;

  if (AO_EXPECT_FALSE(NULL == p))

    return;

  base = (AO_t *)p - 1;

  log_sz = (int)(*base);

# ifdef AO_TRACE_MALLOC

    fprintf(stderr, "%p: AO_free(%p sz:%lu)\n", (void *)pthread_self(), p,

            log_sz > LOG_MAX_SIZE ? (unsigned)log_sz : 1UL << log_sz);

# endif

  if (AO_EXPECT_FALSE(log_sz > LOG_MAX_SIZE)) {

    AO_free_large(p);

  } else {

    ASAN_POISON_MEMORY_REGION(base + 1, ((size_t)1 << log_sz) - sizeof(AO_t));

    AO_stack_push(AO_free_list + log_sz, base);

  }

}