/*
* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* Copyright (c) 1983 Regents of the University of California.
* All rights reserved.
*
* Redistribution and use in source and binary forms are permitted
* provided that: (1) source distributions retain this entire copyright
* notice and comment, and (2) distributions including binaries display
* the following acknowledgement: ``This product includes software
* developed by the University of California, Berkeley and its contributors''
* in the documentation or other materials provided with the distribution
* and in all advertising materials mentioning features or use of this
* software. 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 ``AS IS'' AND WITHOUT ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*/
/*
* 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 bytes long (ILP32)
* or 2^n-8 bytes long (LP64).
*/
/*LINTLIBRARY*/
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <limits.h>
/*
* 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.
* The order of elements is critical: ov_magic must overlay the low order
* bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
* Overhead is 4 bytes for ILP32, 8 bytes for LP64
*/
union overhead {
struct {
#if defined(_LITTLE_ENDIAN)
#elif defined(_BIG_ENDIAN)
#else
#error "Endianness is not defined"
#endif
} ovu;
};
/*
* nextf[i] is the pointer to the next free block of size 2^(i+EXP).
* The smallest allocatable block is 8 bytes (ILP32) or 16 bytes (LP64).
* The overhead information precedes the data area returned to the user.
*/
#ifdef _LP64
#else
#endif
static void morecore(int);
static int findbucket(union overhead *, int);
void *
{
int bucket;
ssize_t n;
/*
* First time malloc is called, setup page size and
* align break pointer so all data will be page aligned.
*/
if (pagesz == 0) {
pagesz = getpagesize();
if (n < 0)
n += pagesz;
if (n) {
if (sbrk(n) == (void *)-1)
return (NULL);
/*
* We were careful to arrange that
* sbrk(0) + sizeof (union overhead)
* should end up on a page boundary.
* If the underlying sbrk() performs alignment
* then this is false. We compute the adjustment.
*/
} else {
sbrk_adjust = 0;
}
bucket = 0;
amt <<= 1;
bucket++;
}
pagebucket = bucket;
}
/*
* Convert amount of memory requested into closest block size
* stored in hash buckets which satisfies request.
* Account for space used per block for accounting.
*/
bucket = 0;
} else {
bucket = pagebucket;
}
amt <<= 1;
if (amt == 0)
return (NULL);
bucket++;
}
/*
* If nothing in hash bucket right now,
* request more memory from the system.
*/
return (NULL);
}
/* remove from linked list */
return (op + 1);
}
/*
* Allocate more memory to the indicated bucket.
*/
static void
{
if (sz == 0)
return;
} else {
nblks = 1;
}
if (amt <= 0)
return;
/*
* the value required is too big for sbrk() to deal with
* in one go, so use sbrk() at most 2 times instead.
*/
while (delta > 0) {
return;
}
}
}
else
/* no more room! */
return;
/* LINTED improper alignment */
/*
* Add new memory allocated to that on
* free list for this hash bucket.
*/
while (--nblks > 0) {
/* LINTED improper alignment */
/* LINTED improper alignment */
}
}
void
{
int size;
return;
/* LINTED improper alignment */
return; /* previously freed? */
}
/*
* When a program attempts "storage compaction" as mentioned in the
* old malloc man page, it realloc's an already freed block. Usually
* this is the last block it freed; occasionally it might be farther
* back. We have to search all the free lists for the block in order
* to determine its bucket: 1st we make one pass thru the lists
* checking only the first block in each; if that fails we search
* ``realloc_srchlen'' blocks in each list for a match (the variable
* is extern so the caller can modify it). If that fails we just copy
* however many bytes was given to realloc() and hope it's not huge.
*/
void *
{
int i;
char *res;
int was_alloced = 0;
/* LINTED improper alignment */
was_alloced++;
} else {
/*
* Already free, doing "compaction".
*
* Search for the old block of memory on the
* free list. First, check the most common
* case (last element free'd), then (this failing)
* the last ``realloc_srchlen'' items free'd.
* If all lookups fail, then just malloc() the
* space and copy the size of the new space.
*/
return (res);
}
}
else
/* avoid the copy if same size block */
if (was_alloced) {
if (i) {
else
}
return (cp);
} else
}
return (NULL);
return (res);
}
/*
* Search ``srchlen'' elements of each free list for a block whose
* header starts at ``freep''. If srchlen is -1 search the whole list.
* Return bucket number, or -1 if not found.
*/
static int
{
union overhead *p;
int i, j;
for (i = 0; i < NBUCKETS; i++) {
j = 0;
if (p == freep)
return (i);
j++;
}
}
return (-1);
}