/* da.cpp -- simple debugging allocator implementation
 *
 * NOTES
 *
 * 1. This code using 8-byte alignment, and may not be right for some
 *    architectures.
 *
 * 2. There needs to be a mutex on da_serial to be thread safe, but it doesn't
 *    matter very much.
 *
 *
 * LICENSE
 *
 * Copyright (C) 2000 Ravenbrook Limited <URL: http://www.ravenbrook.com/>.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by
 *      Ravenbrook Limited <URL: http://www.ravenbrook.com/>.
 * 4. Neither the name of Ravenbrook Limited nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY RAVENBROOK LIMITED AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL RAVENBROOK LIMITED OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.  */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "da.h"


#define ALIGNMENT	8u

#define ALIGN_UP(value, alignment) \
  (((value) + (alignment) - 1) & ~((alignment) - 1))

#define IS_ALIGNED(value, alignment) \
  (((value) & ((alignment) - 1)) == 0)


#define MALLOC_FILL	'M'
#define FREE_FILL	'F'
#define DEAD_BRAND	0xDEADBEEF


typedef struct leader_s *leader_t;

#define LEADER_BRAND	0xBD8EADE4

typedef struct leader_s {
  unsigned long brand;
  size_t size;
} leader_s;

#define LEADER_SIZE	ALIGN_UP(sizeof(leader_s), ALIGNMENT)


typedef struct trailer_s *trailer_t;

#define TRAILER_BRAND	0xBD24A11E

typedef struct trailer_s {
  unsigned long serial;
  unsigned long brand;
} trailer_s;  

#define TRAILER_SIZE	ALIGN_UP(sizeof(trailer_s), ALIGNMENT)


static unsigned long da_serial = 0;


static int da_block_check(void *p)
{
  leader_t leader;
  size_t size;
  size_t aligned_size;
  trailer_t trailer;

  assert(p != NULL);
  assert(IS_ALIGNED((unsigned long)p, ALIGNMENT));

  leader = (leader_t)((char *)p - LEADER_SIZE);

  assert((void *)leader < p);
  assert(leader->brand == LEADER_BRAND);

  size = leader->size;

  assert(size > 0);

  aligned_size = ALIGN_UP(size, ALIGNMENT);
  trailer = (trailer_t)((char *)p + aligned_size);

  assert(p < (void *)trailer);
  assert(trailer->brand == TRAILER_BRAND);
  assert(trailer->serial < da_serial);

  return 1;
}


static size_t da_block_info(void *p, leader_t *leader_o, trailer_t *trailer_o)
{
  leader_t leader;
  trailer_t trailer;
  size_t aligned_size;

  assert(da_block_check(p));

  leader = (leader_t)((char *)p - LEADER_SIZE);
  aligned_size = ALIGN_UP(leader->size, ALIGNMENT);
  trailer = (trailer_t)((char *)p + aligned_size);

  if(leader_o != NULL)
    *leader_o = leader;

  if(trailer_o != NULL)
    *trailer_o = trailer;

  return leader->size;
}


static void *da_malloc_inner(size_t size, const char *file, unsigned long line)
{
  size_t aligned_size;
  size_t block_size;
  void *block;
  leader_t leader;
  trailer_t trailer;
  void *p;

  assert(size >= 0);			/* some systems have signed sizes */
  assert(file != NULL);
  assert(line > 0);
  
  if(size == 0)				/* allocate a dummy byte for empty mallocs */
    size = 1;
  
  aligned_size = ALIGN_UP(size, ALIGNMENT);
  block_size = LEADER_SIZE + aligned_size + TRAILER_SIZE;  

  block = (malloc)(block_size);
  if(block == NULL)
    return NULL;

  assert(IS_ALIGNED((unsigned long)block, ALIGNMENT));

  leader = (leader_t)block;
  p = (void *)((char *)block +  LEADER_SIZE);
  trailer = (trailer_t)((char *)p + aligned_size);
  assert((char *)trailer + TRAILER_SIZE == (char *)block + block_size);
  
  leader->brand = LEADER_BRAND;
  leader->size = size;
  trailer->serial = da_serial++;
  trailer->brand = TRAILER_BRAND;

  memset(p, MALLOC_FILL, aligned_size);

  assert(da_block_check(p));

  return p;
}


extern void *da_malloc(size_t size, const char *file, unsigned long line)
{
  void *p;

  assert(file != NULL);
  assert(line > 0);

  p = da_malloc_inner(size, file, line);
  if(p == NULL) {
    fprintf(stderr,
           "malloc of %lu bytes in file \"%s\" line %lu failed",
           (unsigned long)size,
           file,
           line);
    return NULL;
  }
  
  return p;
}


extern void *da_realloc(void *p, size_t size, const char *file, unsigned long line)
{
  void *new_mem;

  assert(file != NULL);
  assert(line > 0);
  assert(p == NULL || da_block_check(p));
  
  new_mem = da_malloc_inner(size, file, line);
  if(new_mem == NULL) {
    fprintf(stderr,
           "realloc of 0x%lX to %lu bytes in file \"%s\" line %lu failed",
           (unsigned long)p,
           (unsigned long)size,
           file,
           line);
    return NULL;
  }  

  if(p != NULL) {
    size_t old_size = da_block_info(p, NULL, NULL);
    memcpy(new_mem, p, size < old_size ? size : old_size);
    da_free(p, file, line);
  }  

  assert(da_block_check(new_mem));

  return new_mem;
}


extern void da_free(void *p, const char *file, unsigned long line)
{
  leader_t leader;
  trailer_t trailer;

  (void)file;				/* unused parameter */
  (void)line;				/* unused parameter */

  /* There's an implicit block check in da_block_info. */
  (void)da_block_info(p, &leader, &trailer);
  
  memset(p, FREE_FILL, leader->size);

  /* Prevent double frees by making the brands illegal, but also record */
  /* when the free ocurred by XORing in the serial number. */
  leader->brand = DEAD_BRAND ^ da_serial;
  trailer->brand = DEAD_BRAND ^ da_serial;
  ++da_serial;

  (free)(leader);
}


extern void *da_calloc(size_t n, size_t size, const char *file, unsigned long line)
{
  size_t total;
  void *p;
  
  total = n * size;
  
  assert(total >= n);			/* overflow check */
  assert(total >= size);		/* overflow check */

  p = da_malloc_inner(size, file, line);
  if(p == NULL) {
    fprintf(stderr,
           "calloc of %lu objects of %lu bytes in file \"%s\" line %lu failed",
           (unsigned long)n,
           (unsigned long)size,
           file,
           line);
    return NULL;
  }

  memset(p, 0, size);
  
  return p;
}


extern char *da_strdup(const char *p, const char *file, unsigned long line)
{
  size_t size;
  char *new_mem;

  assert(p != NULL);
  size = strlen(p) + 1;
  assert(size > 0);

  new_mem = (char *)da_malloc_inner(size, file, line);
  if (new_mem == NULL) {
    fprintf(stderr,
           "strdup of 0x%lX (\"%s\") in file \"%s\" line %lu failed",
           (unsigned long)p,
           p,
           file,
           line);
    return NULL;
  }

  memcpy(new_mem, p, size);
  return new_mem;
}


/* This version of the delete operator has a signature that matches
   operator new so that Microsoft Visual C++ will call it in the event
   of an exception being thrown in a constructor.  In other
   circumstances the usual delete operator will be called.  I don't
   believe that this is part of the C++ standard (there's no mention of
   such a feature in Stroustrup 1997), but it may be necessary in MSVC++
   and it is harmless otherwise.  I don't know what arguments MSVC++
   will pass for the file and line arguments (hopefully the same ones as
   for the corresponding operator new). */
extern void operator delete(void *p, const char *file, unsigned long line)
{
  da_free(p, file, line);
}


extern void operator delete(void *p)
{
  /* As far as I know there's no way to get the real file and line
     here. Sorry. */
  da_free(p, __FILE__, __LINE__);
}


/* Avoid the operator definition below being stymied by the redefinition
   of new in da.h.  I would have liked to write (new) to avoid the
   macro, but operator() is special in C++. */
#undef new
extern void *operator new(size_t size, const char *file, unsigned long line)
{
  return da_malloc(size, file, line);
}


/* end of da.cpp */