/* -*- 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 */