/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
*/
/* Copyright (c) 1988 AT&T */
/* All Rights Reserved */
#ifndef debug
#define NDEBUG
#endif
#include <stdlib.h>
#include <string.h>
#include "assert.h"
#include "malloc.h"
#include "mallint.h"
#include <thread.h>
#include <pthread.h>
#include <synch.h>
#include <unistd.h>
#include <limits.h>
#include <errno.h>
static void *malloc_unlocked(size_t, int);
static void *realloc_unlocked(void *, size_t);
static void free_unlocked(void *);
/*
* use level memory allocater (malloc, free, realloc)
*
* -malloc, free, realloc and mallopt form a memory allocator
* similar to malloc, free, and realloc. The routines
* here are much faster than the original, with slightly worse
* space usage (a few percent difference on most input). They
* do not have the property that data in freed blocks is left
* untouched until the space is reallocated.
*
* -Memory is kept in the "arena", a singly linked list of blocks.
* These blocks are of 3 types.
* 1. A free block. This is a block not in use by the
* user. It has a 3 word header. (See description
* of the free queue.)
* 2. An allocated block. This is a block the user has
* requested. It has only a 1 word header, pointing
* to the next block of any sort.
* 3. A permanently allocated block. This covers space
* aquired by the user directly through sbrk(). It
* has a 1 word header, as does 2.
* Blocks of type 1 have the lower bit of the pointer to the
* nextblock = 0. Blocks of type 2 and 3 have that bit set,
* to mark them busy.
*
* -Unallocated blocks are kept on an unsorted doubly linked
* free list.
*
* -Memory is allocated in blocks, with sizes specified by the
* user. A circular first-fit startegy is used, with a roving
* head of the free queue, which prevents bunching of small
* blocks at the head of the queue.
*
* -Compaction is performed at free time of any blocks immediately
* following the freed block. The freed block will be combined
* with a preceding block during the search phase of malloc.
* Since a freed block is added at the front of the free queue,
* which is moved to the end of the queue if considered and
* rejected during the search, fragmentation only occurs if
* a block with a contiguious preceding block that is free is
* freed and reallocated on the next call to malloc. The
* time savings of this strategy is judged to be worth the
* occasional waste of memory.
*
* -Small blocks (of size < MAXSIZE) are not allocated directly.
* A large "holding" block is allocated via a recursive call to
* malloc. This block contains a header and ?????? small blocks.
* Holding blocks for a given size of small block (rounded to the
* nearest ALIGNSZ bytes) are kept on a queue with the property that any
* holding block with an unused small block is in front of any without.
* A list of free blocks is kept within the holding block.
*/
/*
* description of arena, free queue, holding blocks etc.
*
* New compiler and linker does not guarentee order of initialized data.
* Define freeptr as arena[2-3] to guarentee it follows arena in memory.
* Later code depends on this order.
*/
{0, 0, 0},
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}
};
/*
* the second word is a minimal block to
* start the arena. The first is a busy
* block to be pointed to by the last block.
*/
/* first and last entry in free list */
/* to holding block chains */
/*
* In order to save time calculating indices, the array is 1 too
* large, and the first element is unused
*
* Variables controlling algorithm, esp. how holding blocs are used
*/
/* number of small block sizes to map to one size */
#ifdef debug
static int case1count = 0;
static void
checkq(void)
{
register struct header *p;
p = &freeptr[0];
/* check forward */
/*CSTYLED*/
while (p != &freeptr[1]) {
p = p->nextfree;
}
/* check backward */
/*CSTYLED*/
while (p != &freeptr[0]) {
p = p->prevfree;
}
}
#endif
/*
* malloc(nbytes) - give a user nbytes to use
*/
void *
{
void *ret;
(void) mutex_lock(&mlock);
(void) mutex_unlock(&mlock);
return (ret);
}
/*
* Use malloc_unlocked() to get the address to start with; Given this
* address, find out the closest address that aligns with the request
* and return that address after doing some house keeping (refer to the
* ascii art below).
*/
void *
{
void *alloc_buf;
static int realloc;
return (NULL);
}
return (NULL);
}
(void) mutex_lock(&mlock);
(void) mutex_unlock(&mlock);
return (NULL);
return (alloc_buf);
/*
* we hit an edge case, where the space ahead of aligned
* address is not sufficient to hold 'header' and hence we
* can't free it. So double the allocation request.
*/
realloc++;
if (alloc_size < size) {
return (NULL);
}
(void) mutex_lock(&mlock);
(void) mutex_unlock(&mlock);
return (NULL);
return (alloc_buf);
}
}
/*
* +-------+ +-------+
* +---| <a> | | <a> |--+
* | +-------+<--alloc_buf-->+-------+ |
* | | | | | |
* | | | | | |
* | | | | | |
* | | | hd--> +-------+ |
* | | | +---| <b> |<-+
* | | | | +-------+<--- fr
* | | | | | |
* | | | | | |
* | | | | | |
* | | | | | |
* | | | | | |
* | | | | | |
* | +-------+ | +-------+
* +-->| next | +-->| next |
* +-------+ +-------+
*
*/
(void) mutex_lock(&mlock);
(void) mutex_unlock(&mlock);
return ((void *)fr);
}
void *
{
static unsigned pagesize;
if (size == 0)
return (NULL);
if (!pagesize)
}
/*
* malloc_unlocked(nbytes, nosmall) - Do the real work for malloc
*/
static void *
{
/* on first call, initialize */
/* initialize arena */
/* initialize free queue */
/* mark that small blocks not init yet */
}
if (nbytes == 0)
return (NULL);
/*
* We can allocate out of a holding block
*/
if (!change) {
int i;
/*
* This allocates space for hold block
* pointers by calling malloc recursively.
* Maxfast is temporarily set to 0, to
* avoid infinite recursion. allocate
* space for an extra ptr so that an index
* ptr unused.
*/
/* no longer allowed */
/*
* temporarily alter maxfast, to avoid
* infinite recursion
*/
maxfast = 0;
malloc_unlocked(sizeof (struct holdblk *) *
(fastct + 1), 0);
return (malloc_unlocked(nbytes, 0));
for (i = 1; i <= fastct; i++) {
}
}
/*
* Note that this uses the absolute min header size (MINHEAD)
* unlike the large block case which uses minhead
*
* round up to nearest multiple of grain
* code assumes grain is a multiple of MINHEAD
*/
/* round up to grain */
/*
* look for space in the holding block. Blocks with
* space will be in front of those without
*/
/* there is space */
/*
* Now make lfreeq point to a free block.
* If lblk has been previously allocated and
* freed, it has a valid pointer to use.
* Otherwise, lblk is at the beginning of
* the unallocated blocks at the end of
* the holding block, so, if there is room, take
* the next space. If not, mark holdblk full,
* and move holdblk to the end of the queue
*/
/* move to next holdblk, if this one full */
LGROUND) {
}
} else {
}
/* mark as busy and small */
} else {
/* we need a new holding block */
return (NULL);
}
/* add to head of free queue */
} else {
}
/* set up newhold */
}
#ifdef debug
nbytes);
#endif /* debug */
} else {
/*
* We need an ordinary block
*/
/* get number of bytes we need */
/*
* see if there is a big enough block
* If none exists, you will get to freeptr[1].
* freeptr[1].next = &arena[0], so when you do the test,
* the result is a large positive number, since arena[0]
* comes before all blocks. Arena[0] is marked busy so
* that it will not be compacted. This kludge is for the
* sake of the almighty efficiency.
*/
/* check that a very large request won't cause an inf. loop */
return (NULL);
} else {
do {
/* see if we can compact */
do {
/*
* next will be at most == to lastblk,
* but I think the >= test is faster
*/
}
}
/*
* if we didn't find a block, get more memory
*/
/*
* careful coding could likely replace
* newend with arenaend
*/
/*
* Three cases - 1. There is space between arenaend
* and the break value that will become
* a permanently allocated block.
* 2. Case 1 is not true, and the last
* block is allocated.
* 3. Case 1 is not true, and the last
* block is free
*/
/* case 1 */
#ifdef debug
if (case1count++ > 0)
" brk or sbrk?\n", 41);
#endif
/* get size to fetch */
/* round up to a block */
/* get memory */
return (NULL);
/* add to arena */
- HEADSZ);
/* ??? newblk ?? */
/*
* space becomes a permanently allocated block.
* This is likely not mt-safe as lock is not
* shared with brk or sbrk
*/
/* adjust other pointers */
/* case 2 */
return (NULL);
/* block must be word aligned */
/*
* stub at old arenaend becomes first word
* in blk
*/
/* ??? newblk = arenaend; */
newend =
} else {
/* case 3 */
/*
* last block in arena is at end of memory and
* is free
*/
/* 1.7 had this backward without cast */
return (NULL);
/* combine with last block, put in arena */
/* set which block to use */
}
} else {
/* take block found of free queue */
/*
* make head of free queue immediately follow blk,
* unless blk was at the end of the queue
*/
}
}
/* blk now points to an adequate block */
/* carve out the right size block */
/* newblk will be the remainder */
/* mark the block busy */
/* if blk was lastblk, make newblk lastblk */
} else {
/* just mark the block busy */
}
}
}
/*
* free(ptr) - free block that user thinks starts at ptr
*
* input - ptr-1 contains the block header.
* If the header points forward, we have a normal
* block pointing to the next block
* if the header points backward, we have a small
* block from a holding block.
* In both cases, the busy bit must be set
*/
void
{
(void) mutex_lock(&mlock);
(void) mutex_unlock(&mlock);
}
/*
* free_unlocked(ptr) - Do the real work for free()
*/
void
{
/* queue containing blk's holder */
if (ptr <= (void *)0x00000001)
return;
/* allow twits (e.g. awk) to free a block twice */
return;
/* put lblk on its hold block's free list */
/* move holdblk to head of queue, if its not already there */
/* first take out of current spot */
/* now add at front */
}
} else {
/* take care of twits (e.g. awk) who return blocks twice */
return;
/* see if we can compact */
do {
}
}
}
/*
* realloc(ptr, size) - give the user a block of size "size", with
* the contents pointed to by ptr. Free ptr.
*/
void *
{
void *retval;
(void) mutex_lock(&mlock);
(void) mutex_unlock(&mlock);
return (retval);
}
/*
* realloc_unlocked(ptr) - Do the real work for realloc()
*/
static void *
{
if (size == 0) {
return ((void *)0x00000001);
}
if (ptr <= (void *)0x00000001)
return (malloc_unlocked(size, 0));
/*
* we have a special small block which can't be expanded
*
* This makes the assumption that even if the user is
* reallocating a free block, malloc doesn't alter the contents
* of small blocks
*/
return (NULL);
/* this isn't to save time--its to protect the twits */
}
} else {
/*
* deal with twits who reallocate free blocks
*
* if they haven't reset minblk via getopt, that's
* their problem
*/
}
/* make blk as big as possible */
do {
}
/* get size we really need */
/* see if we have enough */
/* this isn't really the copy size, but I need a register */
/* carve out the size we need */
/*
* carve out the right size block
* newblk will be the remainder
*/
trusize);
/* at this point, next is invalid */
/* if blk was lastblk, make newblk lastblk */
}
} else {
/* bite the bullet, and call malloc */
return (NULL);
}
}
return (newptr);
}
/*
* calloc - allocate and clear memory block
*/
void *
{
char *mp;
return (NULL);
}
return (NULL);
return (mp);
}
/*
* Mallopt - set options for allocation
*
* Mallopt provides for control over the allocation algorithm.
* The cmds available are:
*
* M_MXFAST Set maxfast to value. Maxfast is the size of the
* largest small, quickly allocated block. Maxfast
* may be set to 0 to disable fast allocation entirely.
*
* M_NLBLKS Set numlblks to value. Numlblks is the number of
* small blocks per holding block. Value must be
* greater than 0.
*
* M_GRAIN Set grain to value. The sizes of all blocks
* smaller than maxfast are considered to be rounded
* up to the nearest multiple of grain. The default
* value of grain is the smallest number of bytes
* which will allow alignment of any data type. Grain
* will be rounded up to a multiple of its default,
* and maxsize will be rounded up to a multiple of
* grain. Value must be greater than 0.
*
* M_KEEP Retain data in freed block until the next malloc,
* realloc, or calloc. Value is ignored.
* This option is provided only for compatibility with
* the old version of malloc, and is not recommended.
*
* returns - 0, upon successful completion
* 1, if malloc has previously been called or
* if value or cmd have illegal values
*/
int
{
/* disallow changes once a small block is allocated */
(void) mutex_lock(&mlock);
if (change) {
(void) mutex_unlock(&mlock);
return (1);
}
switch (cmd) {
case M_MXFAST:
if (value < 0) {
(void) mutex_unlock(&mlock);
return (1);
}
break;
case M_NLBLKS:
if (value <= 1) {
(void) mutex_unlock(&mlock);
return (1);
}
break;
case M_GRAIN:
if (value <= 0) {
(void) mutex_unlock(&mlock);
return (1);
}
/* round grain up to a multiple of ALIGNSZ */
/* reduce fastct appropriately */
break;
case M_KEEP:
(void) mutex_unlock(&mlock);
return (1);
}
break;
default:
(void) mutex_unlock(&mlock);
return (1);
}
(void) mutex_unlock(&mlock);
return (0);
}
/*
* mallinfo-provide information about space usage
*
* input - max; mallinfo will return the size of the
* largest block < max.
*
* output - a structure containing a description of
* of space usage, defined in malloc.h
*/
struct mallinfo
mallinfo(void)
{
int i; /* the ubiquitous counter */
(void) mutex_lock(&mlock);
(void) mutex_unlock(&mlock);
return (inf);
}
/* return total space used */
/*
* loop through arena, counting # of blocks, and
* and space used by blocks
*/
} else {
}
}
/*
* if any holding block have been allocated
* then examine space in holding blks
*/
for (i = fastct; i > 0; i--) { /* loop thru ea. chain */
/* do only if chain not empty */
sizeof (struct lblk) - sizeof (int);
do { /* loop thru 1 hold blk chain */
}
}
}
/* holding block were counted in ordblks, so subtract off */
(void) mutex_unlock(&mlock);
return (inf);
}
/*
* freespace - calc. how much space is used in the free
* small blocks in a given holding block
*
* input - hblk = given holding block
*
* returns space used in free small blocks of hblk
*/
static ssize_t
{
/* follow free chain */
}
return (space);
}
static void *
{
void * ret;
/*
* The request size is too big. We need to do this in
* chunks. Sbrk only takes an int for an arg.
*/
return ((void *)-1);
while (wad > 0) {
return ((void *)-1);
}
}
} else
return (ret);
}
#ifdef debug
int
check_arena(void)
{
(void) mutex_lock(&mlock);
(void) mutex_unlock(&mlock);
return (-1);
}
/* loop through arena, checking */
(4 | SMAL)) == 0);
7) == 0);
}
}
(void) mutex_unlock(&mlock);
return (0);
}
#endif
#ifdef RSTALLOC
/*
* rstalloc - reset alloc routines
*
* description - return allocated memory and reset
* allocation pointers.
*
* Warning - This is for debugging purposes only.
* It will return all memory allocated after
* the first call to malloc, even if some
* of it was fetched by a user's sbrk().
*/
void
rstalloc(void)
{
(void) mutex_lock(&mlock);
change = 0;
(void) mutex_unlock(&mlock);
return;
}
#ifdef debug
case1count = 0;
#endif
(void) mutex_unlock(&mlock);
}
#endif /* RSTALLOC */
/*
* cfree is an undocumented, obsolete function
*/
/* ARGSUSED1 */
void
{
free(p);
}
static void
{
(void) mutex_lock(&mlock);
}
static void
{
(void) mutex_unlock(&mlock);
}
#pragma init(malloc_init)
static void
malloc_init(void)
{
}