Quelle prmalloc.c Sprache: C

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "primpl.h"

/*
** We override malloc etc. on any platform which has preemption +
** nspr20 user level threads.  When we're debugging, we can make our
** version of malloc fail occasionally.
*/
#ifdef _PR_OVERRIDE_MALLOC

/*
** Thread safe version of malloc, calloc, realloc, free
*/
#  include <stdarg.h>

#  ifdef DEBUG
#    define SANITY
#    define EXTRA_SANITY
#  else
#    undef SANITY
#    undef EXTRA_SANITY
#  endif

/* Forward decls */
void* _PR_UnlockedMalloc(size_t size);
void _PR_UnlockedFree(void* ptr);
void* _PR_UnlockedRealloc(void* ptr, size_t size);
void* _PR_UnlockedCalloc(size_t n, size_t elsize);

/************************************************************************/

/*
* ----------------------------------------------------------------------------
* "THE BEER-WARE LICENSE" (Revision 42):
* <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
* can do whatever you want with this stuff. If we meet some day, and you think
* this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
* ----------------------------------------------------------------------------
*
*/

/*
* Defining SANITY will enable some checks which will tell you if the users
* program did botch something
*/

/*
* Defining EXTRA_SANITY will enable some checks which are mostly related
* to internal conditions in malloc.c
*/

/*
* Very verbose progress on stdout...
*/
#  if 0
#    define TRACE(foo) printf foo
static int malloc_event;
#  else
#    define TRACE(foo)
#  endif

/* XXX Pick a number, any number */
#  define malloc_pagesize 4096UL
#  define malloc_pageshift 12UL

#  ifdef XP_UNIX
#    include <stdio.h>
#    include <stdlib.h>
#    include <unistd.h>
#    include <string.h>
#    include <errno.h>
#    include <sys/types.h>
#    include <sys/mman.h>
#  endif

/*
* This structure describes a page's worth of chunks.
*/

struct pginfo {
  struct pginfo* next; /* next on the free list */
  char* page;          /* Pointer to the page */
  u_short size;        /* size of this page's chunks */
  u_short shift;       /* How far to shift for this size chunks */
  u_short free;        /* How many free chunks */
  u_short total;       /* How many chunk */
  u_long bits[1];      /* Which chunks are free */
};

struct pgfree {
  struct pgfree* next; /* next run of free pages */
  struct pgfree* prev; /* prev run of free pages */
  char* page;          /* pointer to free pages */
  char* end;           /* pointer to end of free pages */
  u_long size;         /* number of bytes free */
};

/*
* How many bits per u_long in the bitmap.
* Change only if not 8 bits/byte
*/
#  define MALLOC_BITS (8 * sizeof(u_long))

/*
* Magic values to put in the page_directory
*/
#  define MALLOC_NOT_MINE ((struct pginfo*)0)
#  define MALLOC_FREE ((struct pginfo*)1)
#  define MALLOC_FIRST ((struct pginfo*)2)
#  define MALLOC_FOLLOW ((struct pginfo*)3)
#  define MALLOC_MAGIC ((struct pginfo*)4)

/*
* Set to one when malloc_init has been called
*/
static unsigned initialized;

/*
* The size of a page.
* Must be a integral multiplum of the granularity of mmap(2).
* Your toes will curl if it isn't a power of two
*/
#  define malloc_pagemask ((malloc_pagesize) - 1)

/*
* The size of the largest chunk.
* Half a page.
*/
#  define malloc_maxsize ((malloc_pagesize) >> 1)

/*
* malloc_pagesize == 1 << malloc_pageshift
*/
#  ifndef malloc_pageshift
static unsigned malloc_pageshift;
#  endif /* malloc_pageshift */

/*
* The smallest allocation we bother about.
* Must be power of two
*/
#  ifndef malloc_minsize
static unsigned malloc_minsize;
#  endif /* malloc_minsize */

/*
* The largest chunk we care about.
* Must be smaller than pagesize
* Must be power of two
*/
#  ifndef malloc_maxsize
static unsigned malloc_maxsize;
#  endif /* malloc_maxsize */

#  ifndef malloc_cache
static unsigned malloc_cache;
#  endif /* malloc_cache */

/*
* The offset from pagenumber to index into the page directory
*/
static u_long malloc_origo;

/*
* The last index in the page directory we care about
*/
static u_long last_index;

/*
* Pointer to page directory.
* Allocated "as if with" malloc
*/
static struct pginfo** page_dir;

/*
* How many slots in the page directory
*/
static unsigned malloc_ninfo;

/*
* Free pages line up here
*/
static struct pgfree free_list;

/*
* Abort() if we fail to get VM ?
*/
static int malloc_abort;

#  ifdef SANITY
/*
* Are we trying to die ?
*/
static int suicide;
#  endif

/*
* dump statistics
*/
static int malloc_stats;

/*
* always realloc ?
*/
static int malloc_realloc;

/*
* my last break.
*/
static void* malloc_brk;

/*
* one location cache for free-list holders
*/
static struct pgfree* px;

static int set_pgdir(void* ptr, struct pginfo* info);
static int extend_page_directory(u_long index);

#  ifdef SANITY
void malloc_dump(FILE* fd) {
  struct pginfo** pd;
  struct pgfree* pf;
  int j;

  pd = page_dir;

  /* print out all the pages */
  for (j = 0; j <= last_index; j++) {
    fprintf(fd, "%08lx %5d ", (j + malloc_origo) << malloc_pageshift, j);
    if (pd[j] == MALLOC_NOT_MINE) {
      for (j++; j <= last_index && pd[j] == MALLOC_NOT_MINE; j++);
      j--;
      fprintf(fd, ".. %5d not mine\n", j);
    } else if (pd[j] == MALLOC_FREE) {
      for (j++; j <= last_index && pd[j] == MALLOC_FREE; j++);
      j--;
      fprintf(fd, ".. %5d free\n", j);
    } else if (pd[j] == MALLOC_FIRST) {
      for (j++; j <= last_index && pd[j] == MALLOC_FOLLOW; j++);
      j--;
      fprintf(fd, ".. %5d in use\n", j);
    } else if (pd[j] < MALLOC_MAGIC) {
      fprintf(fd, "(%p)\n", pd[j]);
    } else {
      fprintf(fd, "%p %d (of %d) x %d @ %p --> %p\n", pd[j], pd[j]->free,
              pd[j]->total, pd[j]->size, pd[j]->page, pd[j]->next);
    }
  }

  for (pf = free_list.next; pf; pf = pf->next) {
    fprintf(fd, "Free: @%p [%p...%p[ %ld ->%p <-%p\n", pf, pf->page, pf->end,
            pf->size, pf->prev, pf->next);
    if (pf == pf->next) {
      fprintf(fd, "Free_list loops.\n");
      break;
    }
  }

  /* print out various info */
  fprintf(fd, "Minsize\t%d\n", malloc_minsize);
  fprintf(fd, "Maxsize\t%ld\n", malloc_maxsize);
  fprintf(fd, "Pagesize\t%ld\n", malloc_pagesize);
  fprintf(fd, "Pageshift\t%ld\n", malloc_pageshift);
  fprintf(fd, "FirstPage\t%ld\n", malloc_origo);
  fprintf(fd, "LastPage\t%ld %lx\n", last_index + malloc_pageshift,
          (last_index + malloc_pageshift) << malloc_pageshift);
  fprintf(fd, "Break\t%ld\n", (u_long)sbrk(0) >> malloc_pageshift);
}

static void wrterror(char* fmt, ...) {
  char* q = "malloc() error: ";
  char buf[100];
  va_list ap;

  suicide = 1;

  va_start(ap, fmt);
  PR_vsnprintf(buf, sizeof(buf), fmt, ap);
  va_end(ap);
  fputs(q, stderr);
  fputs(buf, stderr);

  malloc_dump(stderr);
  PR_Abort();
}

static void wrtwarning(char* fmt, ...) {
  char* q = "malloc() warning: ";
  char buf[100];
  va_list ap;

  va_start(ap, fmt);
  PR_vsnprintf(buf, sizeof(buf), fmt, ap);
  va_end(ap);
  fputs(q, stderr);
  fputs(buf, stderr);
}
#  endif /* SANITY */

/*
* Allocate a number of pages from the OS
*/
static caddr_t map_pages(int pages, int update) {
  caddr_t result, tail;

  result = ((caddr_t)sbrk(0)) + malloc_pagemask - 1;
  result = (caddr_t)((u_long)result & ~malloc_pagemask);
  tail = result + (pages << malloc_pageshift);
  if (!brk(tail)) {
    last_index = ((u_long)tail >> malloc_pageshift) - malloc_origo - 1;
    malloc_brk = tail;
    TRACE(("%6d S %p .. %p\n", malloc_event++, result, tail));
    if (!update || last_index < malloc_ninfo ||
        extend_page_directory(last_index)) {
      return result;
    }
  }
  TRACE(("%6d s %d %p %d\n", malloc_event++, pages, sbrk(0), errno));
#  ifdef EXTRA_SANITY
  wrterror("map_pages fails\n");
#  endif
  return 0;
}

#  define set_bit(_pi, _bit) \
    (_pi)->bits[(_bit) / MALLOC_BITS] |= 1L << ((_bit) % MALLOC_BITS)

#  define clr_bit(_pi, _bit) \
    (_pi)->bits[(_bit) / MALLOC_BITS] &= ~(1L << ((_bit) % MALLOC_BITS));

#  define tst_bit(_pi, _bit) \
    ((_pi)->bits[(_bit) / MALLOC_BITS] & (1L << ((_bit) % MALLOC_BITS)))

/*
* Extend page directory
*/
static int extend_page_directory(u_long index) {
  struct pginfo **young, **old;
  int i;

  TRACE(("%6d E %lu\n", malloc_event++, index));

  /* Make it this many pages */
  i = index * sizeof *page_dir;
  i /= malloc_pagesize;
  i += 2;

  /* Get new pages, if you used this much mem you don't care :-) */
  young = (struct pginfo**)map_pages(i, 0);
  if (!young) {
    return 0;
  }

  /* Copy the old stuff */
  memset(young, 0, i * malloc_pagesize);
  memcpy(young, page_dir, malloc_ninfo * sizeof *page_dir);

  /* register the new size */
  malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;

  /* swap the pointers */
  old = page_dir;
  page_dir = young;

  /* Mark the pages */
  index = ((u_long)young >> malloc_pageshift) - malloc_origo;
  page_dir[index] = MALLOC_FIRST;
  while (--i) {
    page_dir[++index] = MALLOC_FOLLOW;
  }

  /* Now free the old stuff */
  _PR_UnlockedFree(old);
  return 1;
}

/*
* Set entry in page directory.
* Extend page directory if need be.
*/
static int set_pgdir(void* ptr, struct pginfo* info) {
  u_long index = ((u_long)ptr >> malloc_pageshift) - malloc_origo;

  if (index >= malloc_ninfo && !extend_page_directory(index)) {
    return 0;
  }
  page_dir[index] = info;
  return 1;
}

/*
* Initialize the world
*/
static void malloc_init(void) {
  int i;
  char* p;

  TRACE(("%6d I\n", malloc_event++));
#  ifdef DEBUG
  for (p = getenv("MALLOC_OPTIONS"); p && *p; p++) {
    switch (*p) {
      case 'a':
        malloc_abort = 0;
        break;
      case 'A':
        malloc_abort = 1;
        break;
      case 'd':
        malloc_stats = 0;
        break;
      case 'D':
        malloc_stats = 1;
        break;
      case 'r':
        malloc_realloc = 0;
        break;
      case 'R':
        malloc_realloc = 1;
        break;
      default:
        wrtwarning("Unknown chars in MALLOC_OPTIONS\n");
        break;
    }
  }
#  endif

#  ifndef malloc_pagesize
  /* determine our pagesize */
  malloc_pagesize = getpagesize();
#  endif /* malloc_pagesize */

#  ifndef malloc_pageshift
  /* determine how much we shift by to get there */
  for (i = malloc_pagesize; i > 1; i >>= 1) {
    malloc_pageshift++;
  }
#  endif /* malloc_pageshift */

#  ifndef malloc_cache
  malloc_cache = 50 << malloc_pageshift;
#  endif /* malloc_cache */

#  ifndef malloc_minsize
  /*
   * find the smallest size allocation we will bother about.
   * this is determined as the smallest allocation that can hold
   * it's own pginfo;
   */
  i = 2;
  for (;;) {
    int j;

    /* Figure out the size of the bits */
    j = malloc_pagesize / i;
    j /= 8;
    if (j < sizeof(u_long)) {
      j = sizeof(u_long);
    }
    if (sizeof(struct pginfo) + j - sizeof(u_long) <= i) {
      break;
    }
    i += i;
  }
  malloc_minsize = i;
#  endif /* malloc_minsize */

  /* Allocate one page for the page directory */
  page_dir = (struct pginfo**)map_pages(1, 0);
#  ifdef SANITY
  if (!page_dir) {
    wrterror("fatal: my first mmap failed. (check limits ?)\n");
  }
#  endif

  /*
   * We need a maximum of malloc_pageshift buckets, steal these from the
   * front of the page_directory;
   */
  malloc_origo = (u_long)page_dir >> malloc_pageshift;
  malloc_origo -= malloc_pageshift;

  /* Clear it */
  memset(page_dir, 0, malloc_pagesize);

  /* Find out how much it tells us */
  malloc_ninfo = malloc_pagesize / sizeof *page_dir;

  /* Plug the page directory into itself */
  i = set_pgdir(page_dir, MALLOC_FIRST);
#  ifdef SANITY
  if (!i) {
    wrterror("fatal: couldn't set myself in the page directory\n");
  }
#  endif

  /* Been here, done that */
  initialized++;
}

/*
* Allocate a number of complete pages
*/
static void* malloc_pages(size_t size) {
  void *p, *delay_free = 0;
  int i;
  struct pgfree* pf;
  u_long index;

  /* How many pages ? */
  size += (malloc_pagesize - 1);
  size &= ~malloc_pagemask;

  p = 0;
  /* Look for free pages before asking for more */
  for (pf = free_list.next; pf; pf = pf->next) {
#  ifdef EXTRA_SANITY
    if (pf->page == pf->end) {
      wrterror("zero entry on free_list\n");
    }
    if (pf->page > pf->end) {
      TRACE(("%6d !s %p %p %p <%d>\n", malloc_event++, pf, pf->page, pf->end,
             __LINE__));
      wrterror("sick entry on free_list\n");
    }
    if ((void*)pf->page >= (void*)sbrk(0)) {
      wrterror("entry on free_list past brk\n");
    }
    if (page_dir[((u_long)pf->page >> malloc_pageshift) - malloc_origo] !=
        MALLOC_FREE) {
      TRACE(("%6d !f %p %p %p <%d>\n", malloc_event++, pf, pf->page, pf->end,
             __LINE__));
      wrterror("non-free first page on free-list\n");
    }
    if (page_dir[((u_long)pf->end >> malloc_pageshift) - 1 - malloc_origo] !=
        MALLOC_FREE) {
      wrterror("non-free last page on free-list\n");
    }
#  endif /* EXTRA_SANITY */
    if (pf->size < size) {
      continue;
    } else if (pf->size == size) {
      p = pf->page;
      if (pf->next) {
        pf->next->prev = pf->prev;
      }
      pf->prev->next = pf->next;
      delay_free = pf;
      break;
    } else {
      p = pf->page;
      pf->page += size;
      pf->size -= size;
      break;
    }
  }
#  ifdef EXTRA_SANITY
  if (p &&
      page_dir[((u_long)p >> malloc_pageshift) - malloc_origo] != MALLOC_FREE) {
    wrterror("allocated non-free page on free-list\n");
  }
#  endif /* EXTRA_SANITY */

  size >>= malloc_pageshift;

  /* Map new pages */
  if (!p) {
    p = map_pages(size, 1);
  }

  if (p) {
    /* Mark the pages in the directory */
    index = ((u_long)p >> malloc_pageshift) - malloc_origo;
    page_dir[index] = MALLOC_FIRST;
    for (i = 1; i < size; i++) {
      page_dir[index + i] = MALLOC_FOLLOW;
    }
  }
  if (delay_free) {
    if (!px) {
      px = (struct pgfree*)delay_free;
    } else {
      _PR_UnlockedFree(delay_free);
    }
  }
  return p;
}

/*
* Allocate a page of fragments
*/

static int malloc_make_chunks(int bits) {
  struct pginfo* bp;
  void* pp;
  int i, k, l;

  /* Allocate a new bucket */
  pp = malloc_pages(malloc_pagesize);
  if (!pp) {
    return 0;
  }
  l = sizeof *bp - sizeof(u_long);
  l += sizeof(u_long) *
       (((malloc_pagesize >> bits) + MALLOC_BITS - 1) / MALLOC_BITS);
  if ((1 << (bits)) <= l + l) {
    bp = (struct pginfo*)pp;
  } else {
    bp = (struct pginfo*)_PR_UnlockedMalloc(l);
  }
  if (!bp) {
    return 0;
  }
  bp->size = (1 << bits);
  bp->shift = bits;
  bp->total = bp->free = malloc_pagesize >> bits;
  bp->next = page_dir[bits];
  bp->page = (char*)pp;
  i = set_pgdir(pp, bp);
  if (!i) {
    return 0;
  }

  /* We can safely assume that there is nobody in this chain */
  page_dir[bits] = bp;

  /* set all valid bits in the bits */
  k = bp->total;
  i = 0;
  /*
      for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
      bp->bits[i / MALLOC_BITS] = ~0;
  */
  for (; i < k; i++) {
    set_bit(bp, i);
  }

  if (bp != pp) {
    return 1;
  }

  /* We may have used the first ones already */
  for (i = 0; l > 0; i++) {
    clr_bit(bp, i);
    bp->free--;
    bp->total--;
    l -= (1 << bits);
  }
  return 1;
}

/*
* Allocate a fragment
*/
static void* malloc_bytes(size_t size) {
  size_t s;
  int j;
  struct pginfo* bp;
  int k;
  u_long *lp, bf;

  /* Don't bother with anything less than this */
  if (size < malloc_minsize) {
    size = malloc_minsize;
  }

  /* Find the right bucket */
  j = 1;
  s = size - 1;
  while (s >>= 1) {
    j++;
  }

  /* If it's empty, make a page more of that size chunks */
  if (!page_dir[j] && !malloc_make_chunks(j)) {
    return 0;
  }

  /* Find first word of bitmap which isn't empty */
  bp = page_dir[j];
  for (lp = bp->bits; !*lp; lp++);

  /* Find that bit */
  bf = *lp;
  k = 0;
  while ((bf & 1) == 0) {
    bf >>= 1;
    k++;
  }

  *lp ^= 1L << k; /* clear it */
  bp->free--;
  if (!bp->free) {
    page_dir[j] = bp->next;
    bp->next = 0;
  }
  k += (lp - bp->bits) * MALLOC_BITS;
  return bp->page + (k << bp->shift);
}

void* _PR_UnlockedMalloc(size_t size) {
  void* result;

  /* Round up to a multiple of 8 bytes */
  if (size & 7) {
    size = size + 8 - (size & 7);
  }

  if (!initialized) {
    malloc_init();
  }

#  ifdef SANITY
  if (suicide) {
    PR_Abort();
  }
#  endif

  if (size <= malloc_maxsize) {
    result = malloc_bytes(size);
  } else {
    result = malloc_pages(size);
  }
#  ifdef SANITY
  if (malloc_abort && !result) {
    wrterror("malloc() returns NULL\n");
  }
#  endif
  TRACE(("%6d M %p %d\n", malloc_event++, result, size));

  return result;
}

void* _PR_UnlockedMemalign(size_t alignment, size_t size) {
  void* result;

  /*
   * alignment has to be a power of 2
   */

  if ((size <= alignment) && (alignment <= malloc_maxsize)) {
    size = alignment;
  } else {
    size += alignment - 1;
  }

  /* Round up to a multiple of 8 bytes */
  if (size & 7) {
    size = size + 8 - (size & 7);
  }

  if (!initialized) {
    malloc_init();
  }

#  ifdef SANITY
  if (suicide) {
    abort();
  }
#  endif

  if (size <= malloc_maxsize) {
    result = malloc_bytes(size);
  } else {
    result = malloc_pages(size);
  }
#  ifdef SANITY
  if (malloc_abort && !result) {
    wrterror("malloc() returns NULL\n");
  }
#  endif
  TRACE(("%6d A %p %d\n", malloc_event++, result, size));

  if ((u_long)result & (alignment - 1)) {
    return ((void*)(((u_long)result + alignment) & ~(alignment - 1)));
  } else {
    return result;
  }
}

void* _PR_UnlockedCalloc(size_t n, size_t nelem) {
  void* p;

  /* Compute total size and then round up to a double word amount */
  n *= nelem;
  if (n & 7) {
    n = n + 8 - (n & 7);
  }

  /* Get the memory */
  p = _PR_UnlockedMalloc(n);
  if (p) {
    /* Zero it */
    memset(p, 0, n);
  }
  return p;
}

/*
* Change an allocation's size
*/
void* _PR_UnlockedRealloc(void* ptr, size_t size) {
  void* p;
  u_long osize, page, index, tmp_index;
  struct pginfo** mp;

  if (!initialized) {
    malloc_init();
  }

#  ifdef SANITY
  if (suicide) {
    PR_Abort();
  }
#  endif

  /* used as free() */
  TRACE(("%6d R %p %d\n", malloc_event++, ptr, size));
  if (ptr && !size) {
    _PR_UnlockedFree(ptr);
    return _PR_UnlockedMalloc(1);
  }

  /* used as malloc() */
  if (!ptr) {
    p = _PR_UnlockedMalloc(size);
    return p;
  }

  /* Find the page directory entry for the page in question */
  page = (u_long)ptr >> malloc_pageshift;
  index = page - malloc_origo;

  /*
   * check if memory was allocated by memalign
   */
  tmp_index = index;
  while (page_dir[tmp_index] == MALLOC_FOLLOW) {
    tmp_index--;
  }
  if (tmp_index != index) {
    /*
     * memalign-allocated memory
     */
    index = tmp_index;
    page = index + malloc_origo;
    ptr = (void*)(page << malloc_pageshift);
  }
  TRACE(("%6d R2 %p %d\n", malloc_event++, ptr, size));

  /* make sure it makes sense in some fashion */
  if (index < malloc_pageshift || index > last_index) {
#  ifdef SANITY
    wrtwarning("junk pointer passed to realloc()\n");
#  endif
    return 0;
  }

  /* find the size of that allocation, and see if we need to relocate */
  mp = &page_dir[index];
  if (*mp == MALLOC_FIRST) {
    osize = malloc_pagesize;
    while (mp[1] == MALLOC_FOLLOW) {
      osize += malloc_pagesize;
      mp++;
    }
    if (!malloc_realloc && size < osize && size > malloc_maxsize &&
        size > (osize - malloc_pagesize)) {
      return ptr;
    }
  } else if (*mp >= MALLOC_MAGIC) {
    osize = (*mp)->size;
    if (!malloc_realloc && size < osize &&
        (size > (*mp)->size / 2 || (*mp)->size == malloc_minsize)) {
      return ptr;
    }
  } else {
#  ifdef SANITY
    wrterror("realloc() of wrong page.\n");
#  endif
  }

  /* try to reallocate */
  p = _PR_UnlockedMalloc(size);

  if (p) {
    /* copy the lesser of the two sizes */
    if (osize < size) {
      memcpy(p, ptr, osize);
    } else {
      memcpy(p, ptr, size);
    }
    _PR_UnlockedFree(ptr);
  }
#  ifdef DEBUG
  else if (malloc_abort) {
    wrterror("realloc() returns NULL\n");
  }
#  endif

  return p;
}

/*
* Free a sequence of pages
*/

static void free_pages(char* ptr, u_long page, int index, struct pginfo* info) {
  int i;
  struct pgfree *pf, *pt;
  u_long l;
  char* tail;

  TRACE(("%6d FP %p %d\n", malloc_event++, ptr, page));
  /* Is it free already ? */
  if (info == MALLOC_FREE) {
#  ifdef SANITY
    wrtwarning("freeing free page at %p.\n", ptr);
#  endif
    return;
  }

#  ifdef SANITY
  /* Is it not the right place to begin ? */
  if (info != MALLOC_FIRST) {
    wrterror("freeing wrong page.\n");
  }

  /* Is this really a pointer to a page ? */
  if ((u_long)ptr & malloc_pagemask) {
    wrterror("freeing messed up page pointer.\n");
  }
#  endif

  /* Count how many pages it is anyway */
  page_dir[index] = MALLOC_FREE;
  for (i = 1; page_dir[index + i] == MALLOC_FOLLOW; i++) {
    page_dir[index + i] = MALLOC_FREE;
  }

  l = i << malloc_pageshift;

  tail = ptr + l;

  /* add to free-list */
  if (!px) {
    px = (struct pgfree*)_PR_UnlockedMalloc(sizeof *pt);
  }
  /* XXX check success */
  px->page = ptr;
  px->end = tail;
  px->size = l;
  if (!free_list.next) {
    px->next = free_list.next;
    px->prev = &free_list;
    free_list.next = px;
    pf = px;
    px = 0;
  } else {
    tail = ptr + l;
    for (pf = free_list.next; pf->next && pf->end < ptr; pf = pf->next);
    for (; pf; pf = pf->next) {
      if (pf->end == ptr) {
        /* append to entry */
        pf->end += l;
        pf->size += l;
        if (pf->next && pf->end == pf->next->page) {
          pt = pf->next;
          pf->end = pt->end;
          pf->size += pt->size;
          pf->next = pt->next;
          if (pf->next) {
            pf->next->prev = pf;
          }
          _PR_UnlockedFree(pt);
        }
      } else if (pf->page == tail) {
        /* prepend to entry */
        pf->size += l;
        pf->page = ptr;
      } else if (pf->page > ptr) {
        px->next = pf;
        px->prev = pf->prev;
        pf->prev = px;
        px->prev->next = px;
        pf = px;
        px = 0;
      } else if (!pf->next) {
        px->next = 0;
        px->prev = pf;
        pf->next = px;
        pf = px;
        px = 0;
      } else {
        continue;
      }
      break;
    }
  }
  if (!pf->next && pf->size > malloc_cache && pf->end == malloc_brk &&
      malloc_brk == (void*)sbrk(0)) {
    pf->end = pf->page + malloc_cache;
    pf->size = malloc_cache;
    TRACE(("%6d U %p %d\n", malloc_event++, pf->end, pf->end - pf->page));
    brk(pf->end);
    malloc_brk = pf->end;
    /* Find the page directory entry for the page in question */
    page = (u_long)pf->end >> malloc_pageshift;
    index = page - malloc_origo;
    /* Now update the directory */
    for (i = index; i <= last_index;) {
      page_dir[i++] = MALLOC_NOT_MINE;
    }
    last_index = index - 1;
  }
}

/*
* Free a chunk, and possibly the page it's on, if the page becomes empty.
*/

static void free_bytes(void* ptr, u_long page, int index, struct pginfo* info) {
  int i;
  struct pginfo** mp;
  void* vp;

  /* Make sure that pointer is multiplum of chunk-size */
#  ifdef SANITY
  if ((u_long)ptr & (info->size - 1)) {
    wrterror("freeing messed up chunk pointer\n");
  }
#  endif

  /* Find the chunk number on the page */
  i = ((u_long)ptr & malloc_pagemask) >> info->shift;

  /* See if it's free already */
  if (tst_bit(info, i)) {
#  ifdef SANITY
    wrtwarning("freeing free chunk at %p\n", ptr);
#  endif
    return;
  }

  /* Mark it free */
  set_bit(info, i);
  info->free++;

  /* If the page was full before, we need to put it on the queue now */
  if (info->free == 1) {
    mp = page_dir + info->shift;
    while (*mp && (*mp)->next && (*mp)->next->page < info->page) {
      mp = &(*mp)->next;
    }
    info->next = *mp;
    *mp = info;
    return;
  }

  /* If this page isn't empty, don't do anything. */
  if (info->free != info->total) {
    return;
  }

  /* We may want to keep at least one page of each size chunks around.  */
  mp = page_dir + info->shift;
  if (0 && (*mp == info) && !info->next) {
    return;
  }

  /* Find & remove this page in the queue */
  while (*mp != info) {
    mp = &((*mp)->next);
#  ifdef EXTRA_SANITY
    if (!*mp) {
      TRACE(("%6d !q %p\n", malloc_event++, info));
      wrterror("Not on queue\n");
    }
#  endif
  }
  *mp = info->next;

  /* Free the page & the info structure if need be */
  set_pgdir(info->page, MALLOC_FIRST);
  if ((void*)info->page == (void*)info) {
    _PR_UnlockedFree(info->page);
  } else {
    vp = info->page;
    _PR_UnlockedFree(info);
    _PR_UnlockedFree(vp);
  }
}

void _PR_UnlockedFree(void* ptr) {
  u_long page;
  struct pginfo* info;
  int index, tmp_index;

  TRACE(("%6d F %p\n", malloc_event++, ptr));
  /* This is legal */
  if (!ptr) {
    return;
  }

#  ifdef SANITY
  /* There wouldn't be anything to free */
  if (!initialized) {
    wrtwarning("free() called before malloc() ever got called\n");
    return;
  }
#  endif

#  ifdef SANITY
  if (suicide) {
    PR_Abort();
  }
#  endif

  /* Find the page directory entry for the page in question */
  page = (u_long)ptr >> malloc_pageshift;
  index = page - malloc_origo;

  /*
   * check if memory was allocated by memalign
   */
  tmp_index = index;
  while (page_dir[tmp_index] == MALLOC_FOLLOW) {
    tmp_index--;
  }
  if (tmp_index != index) {
    /*
     * memalign-allocated memory
     */
    index = tmp_index;
    page = index + malloc_origo;
    ptr = (void*)(page << malloc_pageshift);
  }
  /* make sure it makes sense in some fashion */
  if (index < malloc_pageshift) {
#  ifdef SANITY
    wrtwarning("junk pointer %p (low) passed to free()\n", ptr);
#  endif
    return;
  }
  if (index > last_index) {
#  ifdef SANITY
    wrtwarning("junk pointer %p (high) passed to free()\n", ptr);
#  endif
    return;
  }

  /* handle as page-allocation or chunk allocation */
  info = page_dir[index];
  if (info < MALLOC_MAGIC) {
    free_pages((char*)ptr, page, index, info);
  } else {
    free_bytes(ptr, page, index, info);
  }
  return;
}
#endif /* _PR_OVERRIDE_MALLOC */

quality87%

¤ Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.0.39Bemerkung: (vorverarbeitet) ¤

*Bot Zugriff

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.