/*      $NetBSD: memcluster.c,v 1.1.1.2 2012/09/09 16:08:02 christos Exp $      */

/*
* Copyright (c) 2005 by Internet Systems Consortium, Inc. ("ISC")
* Copyright (c) 1997,1999 by Internet Software Consortium.
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
* OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/


/* When this symbol is defined allocations via memget are made slightly
  bigger and some debugging info stuck before and after the region given
  back to the caller. */
/* #define DEBUGGING_MEMCLUSTER */
#define MEMCLUSTER_ATEND


#if !defined(LINT) && !defined(CODECENTER)
static const char rcsid[] = "Id: memcluster.c,v 1.11 2006/08/30 23:34:38 marka Exp ";
#endif /* not lint */

#include "port_before.h"

#include <sys/types.h>
#include <sys/uio.h>
#include <sys/param.h>
#include <sys/stat.h>

#include <netinet/in.h>
#include <arpa/inet.h>
#include <arpa/nameser.h>

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include <isc/memcluster.h>
#include <isc/assertions.h>

#include "port_after.h"

#ifdef MEMCLUSTER_RECORD
#ifndef DEBUGGING_MEMCLUSTER
#define DEBUGGING_MEMCLUSTER
#endif
#endif

#define DEF_MAX_SIZE            1100
#define DEF_MEM_TARGET          4096

typedef u_int32_t fence_t;

typedef struct {
       void *                  next;
#if defined(DEBUGGING_MEMCLUSTER)
#if defined(MEMCLUSTER_RECORD)
       const char *            file;
       int                     line;
#endif
       size_t                  size;
       fence_t                 fencepost;
#endif
} memcluster_element;

#define SMALL_SIZE_LIMIT sizeof(memcluster_element)
#define P_SIZE sizeof(void *)
#define FRONT_FENCEPOST 0xfebafeba
#define BACK_FENCEPOST 0xabefabef
#define FENCEPOST_SIZE 4

#ifndef MEMCLUSTER_LITTLE_MALLOC
#define MEMCLUSTER_BIG_MALLOC 1
#define NUM_BASIC_BLOCKS 64
#endif

struct stats {
       u_long                  gets;
       u_long                  totalgets;
       u_long                  blocks;
       u_long                  freefrags;
};

#ifdef DO_PTHREADS
#include <pthread.h>
static pthread_mutex_t  memlock = PTHREAD_MUTEX_INITIALIZER;
#define MEMLOCK         (void)pthread_mutex_lock(&memlock)
#define MEMUNLOCK       (void)pthread_mutex_unlock(&memlock)
#else
/*
* Catch bad lock usage in non threaded build.
*/
static unsigned int     memlock = 0;
#define MEMLOCK         do { INSIST(memlock == 0); memlock = 1; } while (0)
#define MEMUNLOCK       do { INSIST(memlock == 1); memlock = 0; } while (0)
#endif  /* DO_PTHEADS */

/* Private data. */

static size_t                   max_size;
static size_t                   mem_target;
#ifndef MEMCLUSTER_BIG_MALLOC
static size_t                   mem_target_half;
static size_t                   mem_target_fudge;
#endif
static memcluster_element **    freelists;
#ifdef MEMCLUSTER_RECORD
static memcluster_element **    activelists;
#endif
#ifdef MEMCLUSTER_BIG_MALLOC
static memcluster_element *     basic_blocks;
#endif
static struct stats *           stats;

/* Forward. */

static size_t                   quantize(size_t);
#if defined(DEBUGGING_MEMCLUSTER)
static void                     check(unsigned char *, int, size_t);
#endif

/* Public. */

int
meminit(size_t init_max_size, size_t target_size) {

#if defined(DEBUGGING_MEMCLUSTER)
       INSIST(sizeof(fence_t) == FENCEPOST_SIZE);
#endif
       if (freelists != NULL) {
               errno = EEXIST;
               return (-1);
       }
       if (init_max_size == 0U)
               max_size = DEF_MAX_SIZE;
       else
               max_size = init_max_size;
       if (target_size == 0U)
               mem_target = DEF_MEM_TARGET;
       else
               mem_target = target_size;
#ifndef MEMCLUSTER_BIG_MALLOC
       mem_target_half = mem_target / 2;
       mem_target_fudge = mem_target + mem_target / 4;
#endif
       freelists = malloc(max_size * sizeof (memcluster_element *));
       stats = malloc((max_size+1) * sizeof (struct stats));
       if (freelists == NULL || stats == NULL) {
               errno = ENOMEM;
               return (-1);
       }
       memset(freelists, 0,
              max_size * sizeof (memcluster_element *));
       memset(stats, 0, (max_size + 1) * sizeof (struct stats));
#ifdef MEMCLUSTER_RECORD
       activelists = malloc((max_size + 1) * sizeof (memcluster_element *));
       if (activelists == NULL) {
               errno = ENOMEM;
               return (-1);
       }
       memset(activelists, 0,
              (max_size + 1) * sizeof (memcluster_element *));
#endif
#ifdef MEMCLUSTER_BIG_MALLOC
       basic_blocks = NULL;
#endif
       return (0);
}

void *
__memget(size_t size) {
       return (__memget_record(size, NULL, 0));
}

void *
__memget_record(size_t size, const char *file, int line) {
       size_t new_size = quantize(size);
#if defined(DEBUGGING_MEMCLUSTER)
       memcluster_element *e;
       char *p;
       fence_t fp = BACK_FENCEPOST;
#endif
       void *ret;

       MEMLOCK;

#if !defined(MEMCLUSTER_RECORD)
       UNUSED(file);
       UNUSED(line);
#endif
       if (freelists == NULL) {
               if (meminit(0, 0) == -1) {
                       MEMUNLOCK;
                       return (NULL);
               }
       }
       if (size == 0U) {
               MEMUNLOCK;
               errno = EINVAL;
               return (NULL);
       }
       if (size >= max_size || new_size >= max_size) {
               /* memget() was called on something beyond our upper limit. */
               stats[max_size].gets++;
               stats[max_size].totalgets++;
#if defined(DEBUGGING_MEMCLUSTER)
               e = malloc(new_size);
               if (e == NULL) {
                       MEMUNLOCK;
                       errno = ENOMEM;
                       return (NULL);
               }
               e->next = NULL;
               e->size = size;
#ifdef MEMCLUSTER_RECORD
               e->file = file;
               e->line = line;
               e->next = activelists[max_size];
               activelists[max_size] = e;
#endif
               MEMUNLOCK;
               e->fencepost = FRONT_FENCEPOST;
               p = (char *)e + sizeof *e + size;
               memcpy(p, &fp, sizeof fp);
               return ((char *)e + sizeof *e);
#else
               MEMUNLOCK;
               return (malloc(size));
#endif
       }

       /*
        * If there are no blocks in the free list for this size, get a chunk
        * of memory and then break it up into "new_size"-sized blocks, adding
        * them to the free list.
        */
       if (freelists[new_size] == NULL) {
               int i, frags;
               size_t total_size;
               void *new;
               char *curr, *next;

#ifdef MEMCLUSTER_BIG_MALLOC
               if (basic_blocks == NULL) {
                       new = malloc(NUM_BASIC_BLOCKS * mem_target);
                       if (new == NULL) {
                               MEMUNLOCK;
                               errno = ENOMEM;
                               return (NULL);
                       }
                       curr = new;
                       next = curr + mem_target;
                       for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
                               ((memcluster_element *)curr)->next = next;
                               curr = next;
                               next += mem_target;
                       }
                       /*
                        * curr is now pointing at the last block in the
                        * array.
                        */
                       ((memcluster_element *)curr)->next = NULL;
                       basic_blocks = new;
               }
               total_size = mem_target;
               new = basic_blocks;
               basic_blocks = basic_blocks->next;
#else
               if (new_size > mem_target_half)
                       total_size = mem_target_fudge;
               else
                       total_size = mem_target;
               new = malloc(total_size);
               if (new == NULL) {
                       MEMUNLOCK;
                       errno = ENOMEM;
                       return (NULL);
               }
#endif
               frags = total_size / new_size;
               stats[new_size].blocks++;
               stats[new_size].freefrags += frags;
               /* Set up a linked-list of blocks of size "new_size". */
               curr = new;
               next = curr + new_size;
               for (i = 0; i < (frags - 1); i++) {
#if defined (DEBUGGING_MEMCLUSTER)
                       memset(curr, 0xa5, new_size);
#endif
                       ((memcluster_element *)curr)->next = next;
                       curr = next;
                       next += new_size;
               }
               /* curr is now pointing at the last block in the array. */
#if defined (DEBUGGING_MEMCLUSTER)
               memset(curr, 0xa5, new_size);
#endif
               ((memcluster_element *)curr)->next = freelists[new_size];
               freelists[new_size] = new;
       }

       /* The free list uses the "rounded-up" size "new_size". */
#if defined (DEBUGGING_MEMCLUSTER)
       e = freelists[new_size];
       ret = (char *)e + sizeof *e;
       /*
        * Check to see if this buffer has been written to while on free list.
        */
       check(ret, 0xa5, new_size - sizeof *e);
       /*
        * Mark memory we are returning.
        */
       memset(ret, 0xe5, size);
#else
       ret = freelists[new_size];
#endif
       freelists[new_size] = freelists[new_size]->next;
#if defined(DEBUGGING_MEMCLUSTER)
       e->next = NULL;
       e->size = size;
       e->fencepost = FRONT_FENCEPOST;
#ifdef MEMCLUSTER_RECORD
       e->file = file;
       e->line = line;
       e->next = activelists[size];
       activelists[size] = e;
#endif
       p = (char *)e + sizeof *e + size;
       memcpy(p, &fp, sizeof fp);
#endif

       /*
        * The stats[] uses the _actual_ "size" requested by the
        * caller, with the caveat (in the code above) that "size" >= the
        * max. size (max_size) ends up getting recorded as a call to
        * max_size.
        */
       stats[size].gets++;
       stats[size].totalgets++;
       stats[new_size].freefrags--;
       MEMUNLOCK;
#if defined(DEBUGGING_MEMCLUSTER)
       return ((char *)e + sizeof *e);
#else
       return (ret);
#endif
}

/*%
* This is a call from an external caller,
* so we want to count this as a user "put".
*/
void
__memput(void *mem, size_t size) {
       __memput_record(mem, size, NULL, 0);
}

void
__memput_record(void *mem, size_t size, const char *file, int line) {
       size_t new_size = quantize(size);
#if defined (DEBUGGING_MEMCLUSTER)
       memcluster_element *e;
       memcluster_element *el;
#ifdef MEMCLUSTER_RECORD
       memcluster_element *prev;
#endif
       fence_t fp;
       char *p;
#endif

       MEMLOCK;

#if !defined (MEMCLUSTER_RECORD)
       UNUSED(file);
       UNUSED(line);
#endif

       REQUIRE(freelists != NULL);

       if (size == 0U) {
               MEMUNLOCK;
               errno = EINVAL;
               return;
       }

#if defined (DEBUGGING_MEMCLUSTER)
       e = (memcluster_element *) ((char *)mem - sizeof *e);
       INSIST(e->fencepost == FRONT_FENCEPOST);
       INSIST(e->size == size);
       p = (char *)e + sizeof *e + size;
       memcpy(&fp, p, sizeof fp);
       INSIST(fp == BACK_FENCEPOST);
       INSIST(((u_long)mem % 4) == 0);
#ifdef MEMCLUSTER_RECORD
       prev = NULL;
       if (size == max_size || new_size >= max_size)
               el = activelists[max_size];
       else
               el = activelists[size];
       while (el != NULL && el != e) {
               prev = el;
               el = el->next;
       }
       INSIST(el != NULL);     /*%< double free */
       if (prev == NULL) {
               if (size == max_size || new_size >= max_size)
                       activelists[max_size] = el->next;
               else
                       activelists[size] = el->next;
       } else
               prev->next = el->next;
#endif
#endif

       if (size == max_size || new_size >= max_size) {
               /* memput() called on something beyond our upper limit */
#if defined(DEBUGGING_MEMCLUSTER)
               free(e);
#else
               free(mem);
#endif

               INSIST(stats[max_size].gets != 0U);
               stats[max_size].gets--;
               MEMUNLOCK;
               return;
       }

       /* The free list uses the "rounded-up" size "new_size": */
#if defined(DEBUGGING_MEMCLUSTER)
       memset(mem, 0xa5, new_size - sizeof *e); /*%< catch write after free */
       e->size = 0;    /*%< catch double memput() */
#ifdef MEMCLUSTER_RECORD
       e->file = file;
       e->line = line;
#endif
#ifdef MEMCLUSTER_ATEND
       e->next = NULL;
       el = freelists[new_size];
       while (el != NULL && el->next != NULL)
               el = el->next;
       if (el)
               el->next = e;
       else
               freelists[new_size] = e;
#else
       e->next = freelists[new_size];
       freelists[new_size] = (void *)e;
#endif
#else
       ((memcluster_element *)mem)->next = freelists[new_size];
       freelists[new_size] = (memcluster_element *)mem;
#endif

       /*
        * The stats[] uses the _actual_ "size" requested by the
        * caller, with the caveat (in the code above) that "size" >= the
        * max. size (max_size) ends up getting recorded as a call to
        * max_size.
        */
       INSIST(stats[size].gets != 0U);
       stats[size].gets--;
       stats[new_size].freefrags++;
       MEMUNLOCK;
}

void *
__memget_debug(size_t size, const char *file, int line) {
       void *ptr;
       ptr = __memget_record(size, file, line);
       fprintf(stderr, "%s:%d: memget(%lu) -> %p\n", file, line,
               (u_long)size, ptr);
       return (ptr);
}

void
__memput_debug(void *ptr, size_t size, const char *file, int line) {
       fprintf(stderr, "%s:%d: memput(%p, %lu)\n", file, line, ptr,
               (u_long)size);
       __memput_record(ptr, size, file, line);
}

/*%
* Print the stats[] on the stream "out" with suitable formatting.
*/
void
memstats(FILE *out) {
       size_t i;
#ifdef MEMCLUSTER_RECORD
       memcluster_element *e;
#endif

       MEMLOCK;

       if (freelists == NULL) {
               MEMUNLOCK;
               return;
       }
       for (i = 1; i <= max_size; i++) {
               const struct stats *s = &stats[i];

               if (s->totalgets == 0U && s->gets == 0U)
                       continue;
               fprintf(out, "%s%5lu: %11lu gets, %11lu rem",
                       (i == max_size) ? ">=" : "  ",
                       (unsigned long)i, s->totalgets, s->gets);
               if (s->blocks != 0U)
                       fprintf(out, " (%lu bl, %lu ff)",
                               s->blocks, s->freefrags);
               fputc('\n', out);
       }
#ifdef MEMCLUSTER_RECORD
       fprintf(out, "Active Memory:\n");
       for (i = 1; i <= max_size; i++) {
               if ((e = activelists[i]) != NULL)
                       while (e != NULL) {
                               fprintf(out, "%s:%d %p:%lu\n",
                                       e->file != NULL ? e->file :
                                               "<UNKNOWN>", e->line,
                                       (char *)e + sizeof *e,
                                       (u_long)e->size);
                               e = e->next;
                       }
       }
#endif
       MEMUNLOCK;
}

int
memactive(void) {
       size_t i;

       if (stats == NULL)
               return (0);
       for (i = 1; i <= max_size; i++)
               if (stats[i].gets != 0U)
                       return (1);
       return (0);
}

/* Private. */

/*%
* Round up size to a multiple of sizeof(void *).  This guarantees that a
* block is at least sizeof void *, and that we won't violate alignment
* restrictions, both of which are needed to make lists of blocks.
*/
static size_t
quantize(size_t size) {
       int remainder;
       /*
        * If there is no remainder for the integer division of
        *
        *      (rightsize/P_SIZE)
        *
        * then we already have a good size; if not, then we need
        * to round up the result in order to get a size big
        * enough to satisfy the request _and_ aligned on P_SIZE boundaries.
        */
       remainder = size % P_SIZE;
       if (remainder != 0)
               size += P_SIZE - remainder;
#if defined(DEBUGGING_MEMCLUSTER)
       return (size + SMALL_SIZE_LIMIT + sizeof (int));
#else
       return (size);
#endif
}

#if defined(DEBUGGING_MEMCLUSTER)
static void
check(unsigned char *a, int value, size_t len) {
       size_t i;
       for (i = 0; i < len; i++)
               INSIST(a[i] == value);
}
#endif

/*! \file */

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.