OpenGrok

/*	$NetBSD: xmalloc.c,v 1.28 2026/07/20 18:46:37 riastradh Exp $	*/

/*
 * Copyright 1996 John D. Polstra.
 * Copyright 1996 Matt Thomas <matt (at) 3am-software.com>
 * All rights reserved.
 *
 * 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 John Polstra.
 * 4. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 THE AUTHOR 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.
 */

/*
 * Copyright (c) 1983 Regents of the University of California.
 * All rights reserved.
 *
 * 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. Neither the name of the University 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 THE REGENTS 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 THE REGENTS 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.
 */

#if defined(LIBC_SCCS) && !defined(lint)
/*static char *sccsid = "from: @(#)malloc.c	5.11 (Berkeley) 2/23/91";*/
#endif /* LIBC_SCCS and not lint */

/*
 * malloc.c (Caltech) 2/21/82
 * Chris Kingsley, kingsley@cit-20.
 *
 * This is a very fast storage allocator.  It allocates blocks of a small
 * number of different sizes, and keeps free lists of each size.  Blocks that
 * don't exactly fit are passed up to the next larger size.  In this
 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
 * This is designed for use in a virtual memory environment.
 */

#include <sys/cdefs.h>
#ifndef lint
__RCSID("$NetBSD: xmalloc.c,v 1.28 2026/07/20 18:46:37 riastradh Exp $");
#endif /* not lint */

#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>

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

#include "rtld.h"

/*
 * Pre-allocate mmap'ed pages
 */
#define	NPOOLPAGES	(32 * 1024 / pagesz)
static char 		*pagepool_start, *pagepool_end;
#define PAGEPOOL_SIZE	(size_t)(pagepool_end - pagepool_start)

/*
 * The overhead on a block is at least 4 bytes.  When free, this space
 * contains a pointer to the next free block, and the bottom two bits must
 * be zero.  When in use, the first byte is set to MAGIC, and the second
 * byte is the size index.  The remaining bytes are for alignment.
 */
union	overhead {
	union	overhead *ov_next;	/* when free */
	struct {
		uint16_t	ovu_index;	/* bucket # */
		uint8_t		ovu_magic;	/* magic number */
	} ovu;
#define	ov_magic	ovu.ovu_magic
#define	ov_index	ovu.ovu_index
};

static void morecore(size_t);
static int morepages(int);
static void *imalloc(size_t);

#define	MAGIC		0xef		/* magic # on accounting info */
#define	AMAGIC		0xdf		/* magic # for aligned alloc */


/*
 * nextf[i] is the pointer to the next free block of size
 * (FIRST_BUCKET_SIZE << i).  The overhead information precedes the data
 * area returned to the user.
 */
#define	FIRST_BUCKET_SHIFT	3
#define	FIRST_BUCKET_SIZE	(1U << FIRST_BUCKET_SHIFT)
#define	NBUCKETS 30
static	union overhead *nextf[NBUCKETS];

static	size_t pagesz;			/* page size */
static	size_t pageshift;		/* page size shift */

#ifdef MSTATS
/*
 * nmalloc[i] is the difference between the number of mallocs and frees
 * for a given block size.
 */
static	u_int nmalloc[NBUCKETS];
#endif

#if defined(MALLOC_DEBUG)
#define	ASSERT(p)	(__predict_false(!(p)) ? botch(#p) : (void)0)
static void
botch(const char *s)
{
	xwarnx("\r\nassertion botched: %s\r\n", s);
	abort();
}
#else
#define	ASSERT(p)	__nothing
#endif

#define TRACE()	xprintf("TRACE %s:%d\n", __FILE__, __LINE__)

static void *
cp2op(void *cp)
{
	return (((caddr_t)cp - sizeof(union overhead)));
}

static void *
imalloc(size_t nbytes)
{
	union overhead *op;
	size_t bucket;
	size_t amt;

	/*
	 * First time malloc is called, setup page size.
	 */
	if (pagesz == 0) {
		size_t n, m;
		pagesz = n = _rtld_pagesz;
		pageshift = ffs(pagesz) - 1;
		if (morepages(NPOOLPAGES) == 0)
			return NULL;
		op = (union overhead *)(pagepool_start);
		m = sizeof (*op) - (((char *)op - (char *)NULL) & (n - 1));
		if (n < m)
			n += pagesz - m;
		else
			n -= m;
		if (n) {
			pagepool_start += n;
		}
	}

	/*
	 * Convert amount of memory requested into closest block size
	 * stored in hash buckets which satisfies request.
	 * Account for space used per block for accounting.
	 */
	amt = FIRST_BUCKET_SIZE;
	bucket = 0;
	while (nbytes > amt - sizeof(*op)) {
		amt <<= 1;
		bucket++;
		if (amt == 0 || bucket >= NBUCKETS)
			return (NULL);
	}
	/*
	 * If nothing in hash bucket right now,
	 * request more memory from the system.
	 */
	if ((op = nextf[bucket]) == NULL) {
		morecore(bucket);
		if ((op = nextf[bucket]) == NULL)
			return (NULL);
	}
	/* remove from linked list */
	nextf[bucket] = op->ov_next;
	op->ov_magic = MAGIC;
	op->ov_index = bucket;
#ifdef MSTATS
	nmalloc[bucket]++;
#endif
	return ((char *)(op + 1));
}

void *
xmalloc_aligned(size_t size, size_t align, size_t offset)
{
	void *mem;
	union overhead *ov;
	uintptr_t x;

	ASSERT((align & (align - 1)) == 0);

	if (align < FIRST_BUCKET_SIZE)
		align = FIRST_BUCKET_SIZE;
	offset &= align - 1;
	mem = imalloc(size + align + offset + sizeof(union overhead));
	if (mem == NULL)
		return (NULL);
	x = roundup2((uintptr_t)mem + sizeof(union overhead), align);
	x += offset;
	ov = cp2op((void *)x);
	ov->ov_magic = AMAGIC;
	ov->ov_index = x - (uintptr_t)mem + sizeof(union overhead);

	return ((void *)x);
}

/*
 * Allocate more memory to the indicated bucket.
 */
static void
morecore(size_t bucket)
{
	union overhead *op;
	size_t sz;		/* size of desired block */
	size_t amt;		/* amount to allocate */
	size_t nblks;		/* how many blocks we get */

	sz = FIRST_BUCKET_SIZE << bucket;
	if (sz < pagesz) {
		amt = pagesz;
		nblks = amt >> (bucket + FIRST_BUCKET_SHIFT);
	} else {
		amt = sz;
		nblks = 1;
	}
	if (amt > PAGEPOOL_SIZE)
		if (morepages((amt >> pageshift) + NPOOLPAGES) == 0)
			return;
	op = (union overhead *)pagepool_start;
	pagepool_start += amt;

	/*
	 * Add new memory allocated to that on
	 * free list for this hash bucket.
	 */
	nextf[bucket] = op;
	while (--nblks > 0) {
		op->ov_next = (union overhead *)((caddr_t)op + sz);
		op = (union overhead *)((caddr_t)op + sz);
	}
}

void
xfree(void *cp)
{
	union overhead *op, *opx;
	size_t size;

	if (cp == NULL)
		return;
	opx = cp2op(cp);

	op = opx->ov_magic == AMAGIC ? (void *)((caddr_t)cp - opx->ov_index) :
	    opx;
	ASSERT(op->ov_magic == MAGIC);		/* make sure it was in use */
	if (op->ov_magic != MAGIC)
		return;				/* sanity */
	size = op->ov_index;
	ASSERT(size < NBUCKETS);
	op->ov_next = nextf[size];		/* also clobbers ov_magic */
	nextf[size] = op;
#ifdef MSTATS
	nmalloc[size]--;
#endif
}

static void *
irealloc(void *cp, size_t nbytes)
{
	size_t onb;
	size_t i;
	union overhead *op;
	char *res;

	if (cp == NULL)
		return (imalloc(nbytes));
	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
	if (op->ov_magic != MAGIC) {
		static const char *err_str =
		    "memory corruption or double free in realloc\n";
		extern char *__progname;
		write(STDERR_FILENO, __progname, strlen(__progname));
		write(STDERR_FILENO, err_str, strlen(err_str));
		abort();
	}

	i = op->ov_index;
	onb = 1 << (i + FIRST_BUCKET_SHIFT);
	if (onb < pagesz)
		onb -= sizeof (*op);
	else
		onb += pagesz - sizeof (*op);
	/* avoid the copy if same size block */
	if (i) {
		i = 1 << (i + 2);
		if (i < pagesz)
			i -= sizeof (*op);
		else
			i += pagesz - sizeof (*op);
	}
	if (nbytes <= onb && nbytes > i) {
		return(cp);
	}
	if ((res = imalloc(nbytes)) == NULL)
		return (NULL);
	if (cp != res) {	/* common optimization if "compacting" */
		memcpy(res, cp, (nbytes < onb) ? nbytes : onb);
		xfree(cp);
	}
	return (res);
}

#ifdef MSTATS
/*
 * mstats - print out statistics about malloc
 *
 * Prints two lines of numbers, one showing the length of the free list
 * for each size category, the second showing the number of mallocs -
 * frees for each size category.
 */
void
mstats(char *s)
{
	int i, j;
	union overhead *p;
	int totfree = 0,
	totused = 0;

	xprintf("Memory allocation statistics %s\nfree:\t", s);
	for (i = 0; i < NBUCKETS; i++) {
		for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
			;
		xprintf(" %d", j);
		totfree += j * (1 << (i + FIRST_BUCKET_SHIFT));
	}
	xprintf("\nused:\t");
	for (i = 0; i < NBUCKETS; i++) {
		xprintf(" %d", nmalloc[i]);
		totused += nmalloc[i] * (1 << (i + FIRST_BUCKET_SHIFT));
	}
	xprintf("\n\tTotal in use: %d, total free: %d\n",
	    totused, totfree);
}
#endif


static int
morepages(int n)
{
	int	fd = -1;
	int	offset;

#ifdef NEED_DEV_ZERO
	fd = open("/dev/zero", O_RDWR, 0);
	if (fd == -1)
		xerr(1, "/dev/zero");
#endif

	if (PAGEPOOL_SIZE > pagesz) {
		caddr_t	addr = (caddr_t)
			(((long)pagepool_start + pagesz - 1) & ~(pagesz - 1));
		if (munmap(addr, pagepool_end - addr) != 0)
			xwarn("morepages: munmap %p", addr);
	}

	offset = (long)pagepool_start - ((long)pagepool_start & ~(pagesz - 1));

	if ((pagepool_start = mmap(0, n * pagesz,
			PROT_READ|PROT_WRITE,
			MAP_ANON|MAP_PRIVATE, fd, 0)) == (caddr_t)-1) {
		xprintf("Cannot map anonymous memory");
		return 0;
	}
	pagepool_end = pagepool_start + n * pagesz;
	pagepool_start += offset;

#ifdef NEED_DEV_ZERO
	close(fd);
#endif
	return n;
}

void *
xcalloc(size_t size)
{

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

void *
xmalloc(size_t size)
{
	void *p = imalloc(size);

	if (p == NULL)
		xerr(1, "%s", xstrerror(errno));
	return p;
}

void *
xrealloc(void *p, size_t size)
{
	p = irealloc(p, size);

	if (p == NULL)
		xerr(1, "%s", xstrerror(errno));
	return p;
}

char *
xstrdup(const char *str)
{
	size_t len;
	char *copy;

	len = strlen(str) + 1;
	copy = xmalloc(len);
	memcpy(copy, str, len);
	return (copy);
}