741 lines
13 KiB
C
741 lines
13 KiB
C
#ident "$Header: /proj/irix6.5.7m/isms/irix/cmd/icrash_old/lib/libutil/RCS/alloc.c,v 1.1 1999/05/25 19:19:20 tjm Exp $"
|
|
|
|
#include <stdio.h>
|
|
#include <sys/types.h>
|
|
#include <sys/param.h>
|
|
#include <assert.h>
|
|
#include "icrash.h"
|
|
#include "alloc.h"
|
|
#include "extern.h"
|
|
|
|
/* Local variables
|
|
*/
|
|
page_t *phash[PHASHSIZE];
|
|
bucket_t bucket[NBUCKETS];
|
|
mempool_t mempool;
|
|
block_t *temp_blks = NULL; /* List of block headers for B_TEMP blocks */
|
|
int bucket_size[] = {8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, -1};
|
|
|
|
#ifdef ICRASH_DEBUG
|
|
block_t *perm_blks = NULL;
|
|
#endif
|
|
|
|
/*
|
|
* add_phash() -- Put page header on phash[] hash table.
|
|
*/
|
|
void
|
|
add_phash(page_t *page)
|
|
{
|
|
page_t **ph, *p;
|
|
|
|
ph = PHASH((unsigned)page->addr);
|
|
|
|
if (p = *ph) {
|
|
while(p) {
|
|
if (p->hash) {
|
|
p = p->hash;
|
|
}
|
|
else {
|
|
break;
|
|
}
|
|
}
|
|
p->hash = page;
|
|
}
|
|
else {
|
|
*ph = page;
|
|
}
|
|
page->hash = (page_t *)NULL;
|
|
}
|
|
|
|
/*
|
|
* rem_phash() -- Remove a page header from the phash[] hash table.
|
|
*/
|
|
int
|
|
rem_phash(page_t *page)
|
|
{
|
|
page_t **ph, *p;
|
|
|
|
ph = PHASH((unsigned)page->addr);
|
|
|
|
/* Get first page on hash list and see if it's the one we want
|
|
*/
|
|
if ((p = *ph) == page) {
|
|
*ph = page->hash;
|
|
page->hash = (page_t *)NULL;
|
|
return(0);
|
|
}
|
|
|
|
/* Otherwise walk the hash list
|
|
*/
|
|
while(p) {
|
|
if (p->hash == page) {
|
|
p->hash = page->hash;
|
|
page->hash = (page_t *)NULL;
|
|
return(0);
|
|
}
|
|
else {
|
|
p = p->hash;
|
|
}
|
|
}
|
|
|
|
/* We should NEVER get here -- active pages MUST be on page
|
|
* hash table.
|
|
*/
|
|
return(1);
|
|
}
|
|
|
|
/*
|
|
* find_page() -- See if page for addr is in phash[] hash table.
|
|
* If it is, return a pointer to the page header.
|
|
* Otherwise return NULL.
|
|
*/
|
|
page_t *
|
|
find_page(caddr_t *addr)
|
|
{
|
|
page_t *p;
|
|
|
|
p = *(page_t **)PHASH((unsigned)addr);
|
|
|
|
/* Search for page in hash queue
|
|
*/
|
|
while(p) {
|
|
if (((unsigned)addr >= (unsigned)p->addr) &&
|
|
((unsigned)addr < ((unsigned)p->addr + IO_NBPC))) {
|
|
break;
|
|
}
|
|
p = p->hash;
|
|
}
|
|
return(p);
|
|
}
|
|
|
|
/*
|
|
* alloc_pghdrs() -- Allocate count number of page headers and put them on
|
|
* pghdrs freelist in mempool.
|
|
*/
|
|
void
|
|
alloc_pghdrs(int count)
|
|
{
|
|
int i;
|
|
page_t *p;
|
|
|
|
if (!(p = (page_t *)malloc(sizeof(page_t) * count))) {
|
|
fatal("not enough memory to allocate page headers!\n");
|
|
}
|
|
bzero(p, sizeof(page_t) * count);
|
|
for (i = 0; i < count; i++) {
|
|
ENQUEUE(&mempool.pghdrs, p++);
|
|
}
|
|
mempool.npghdrs += count;
|
|
mempool.free_pghdrs += count;
|
|
}
|
|
|
|
/*
|
|
* get_pghdr()
|
|
*/
|
|
page_t *
|
|
get_pghdr()
|
|
{
|
|
page_t *p;
|
|
|
|
if (!(p = (page_t *)DEQUEUE(&mempool.pghdrs))) {
|
|
alloc_pghdrs(PGHDR_ALLOC);
|
|
p = (page_t *)DEQUEUE(&mempool.pghdrs);
|
|
}
|
|
mempool.free_pghdrs--;
|
|
return(p);
|
|
}
|
|
|
|
/*
|
|
* alloc_blkhdrs() -- Allocate count number of block headers and put them
|
|
* on mempool.free_blkhdrs.
|
|
*/
|
|
void
|
|
alloc_blkhdrs(int count)
|
|
{
|
|
int i;
|
|
block_t *b;
|
|
|
|
if (!(b = (block_t *)malloc(sizeof(block_t) * count))) {
|
|
fatal("not enough memory to allocate block headers!\n");
|
|
}
|
|
bzero(b, sizeof(block_t) * count);
|
|
for (i = 0; i < count; i++) {
|
|
ENQUEUE(&mempool.blkhdrs, b++);
|
|
}
|
|
mempool.nblkhdrs += count;
|
|
mempool.free_blkhdrs += count;
|
|
}
|
|
|
|
/*
|
|
* get_blkhdr()
|
|
*/
|
|
block_t *
|
|
get_blkhdr()
|
|
{
|
|
block_t *b;
|
|
|
|
if (!(b = (block_t *)DEQUEUE(&mempool.blkhdrs))) {
|
|
alloc_blkhdrs(BLKHDR_ALLOC);
|
|
b = (block_t *)DEQUEUE(&mempool.blkhdrs);
|
|
}
|
|
mempool.free_blkhdrs--;
|
|
return(b);
|
|
}
|
|
|
|
/*
|
|
* alloc_page() -- Allocate count pages of memory
|
|
*/
|
|
caddr_t *
|
|
alloc_pages(int count)
|
|
{
|
|
caddr_t *page;
|
|
|
|
if (!(page = (caddr_t *)memalign(IO_NBPC, IO_NBPC * count))) {
|
|
fprintf(KL_ERRORFP, "%s: not enough memory to allocate %d pages!\n",
|
|
program, count);
|
|
exit(1);
|
|
}
|
|
return(page);
|
|
}
|
|
|
|
/*
|
|
* get_page()
|
|
*/
|
|
page_t *
|
|
get_page(int index)
|
|
{
|
|
int i;
|
|
block_t *b;
|
|
caddr_t *page;
|
|
page_t *p;
|
|
|
|
TRY_AGAIN:
|
|
|
|
/* Check to see if there are any free pages in memory pool
|
|
*/
|
|
if (mempool.free_pgs) {
|
|
p = (page_t *)DEQUEUE(&mempool.pgs);
|
|
p->next = p->prev = (page_t *)NULL;
|
|
mempool.free_pgs--;
|
|
}
|
|
else {
|
|
|
|
/* Get some more pages for the memory pool
|
|
*/
|
|
page = (caddr_t *)alloc_pages(PAGE_ALLOC);
|
|
for (i = 0; i < PAGE_ALLOC; i++) {
|
|
p = get_pghdr();
|
|
p->addr = page;
|
|
p->blksz = 0;
|
|
p->state = P_AVAIL;
|
|
p->nfree = 0;
|
|
p->index = 0;
|
|
ENQUEUE(&mempool.pgs, p);
|
|
page += (IO_NBPC/4);
|
|
}
|
|
|
|
/* Bump global page/free counts
|
|
*/
|
|
mempool.npgs += PAGE_ALLOC;
|
|
mempool.free_pgs += PAGE_ALLOC;
|
|
goto TRY_AGAIN;
|
|
}
|
|
|
|
/* Update memory pool stats
|
|
*/
|
|
mempool.m_alloc++;
|
|
if (mempool.m_high < (mempool.npgs - mempool.free_pgs)) {
|
|
mempool.m_high = (mempool.npgs - mempool.free_pgs);
|
|
}
|
|
|
|
/* Update info for bucket we're getting page for
|
|
*/
|
|
bucket[index].nblks += (IO_NBPC / bucket_size[index]);
|
|
bucket[index].freeblks += (IO_NBPC / bucket_size[index]);
|
|
bucket[index].npages++;
|
|
|
|
/* Set up page header
|
|
*/
|
|
p->state = P_INUSE;
|
|
p->index = index;
|
|
p->blksz = bucket_size[index];
|
|
p->nblocks = p->nfree = (IO_NBPC / bucket_size[index]);
|
|
|
|
/* Break page into blocks and queue them on freelist
|
|
*/
|
|
for (i = 0; i < p->nblocks; i++) {
|
|
b = (block_t *)((unsigned)p->addr + (i * p->blksz));
|
|
ENQUEUE(&p->blklist, b);
|
|
}
|
|
|
|
/* put the new page in the hash table and on the bucket pagelist
|
|
*/
|
|
ENQUEUE(&bucket[index].pagelist, p);
|
|
add_phash(p);
|
|
return(p);
|
|
}
|
|
|
|
/*
|
|
* init_mempool() -- initialize the block memory buckets.
|
|
*/
|
|
void
|
|
init_mempool()
|
|
{
|
|
int i;
|
|
caddr_t *page;
|
|
page_t *p;
|
|
|
|
/* zero out the buckets and phash[] list
|
|
*/
|
|
bzero(&bucket, sizeof (bucket));
|
|
bzero(&phash, sizeof (phash));
|
|
|
|
/* allocate some block and page headers to start with
|
|
*/
|
|
alloc_pghdrs(PGHDR_INIT);
|
|
alloc_blkhdrs(BLKHDR_INIT);
|
|
|
|
/* Now get some pages for the memory pool.
|
|
*/
|
|
page = (caddr_t *)alloc_pages(PAGE_INIT);
|
|
for (i = 0; i < PAGE_INIT; i++) {
|
|
p = get_pghdr();
|
|
p->addr = page;
|
|
p->blksz = 0;
|
|
p->state = P_AVAIL;
|
|
p->nfree = 0;
|
|
p->index = 0;
|
|
ENQUEUE(&mempool.pgs, p);
|
|
page += (IO_NBPC/4);
|
|
}
|
|
|
|
/* Initialize memory pool structure
|
|
*/
|
|
mempool.npgs = PAGE_INIT;
|
|
mempool.free_pgs = PAGE_INIT;
|
|
mempool.m_alloc = 0;
|
|
mempool.m_free = 0;
|
|
mempool.m_high = 0;
|
|
|
|
/* Initialize the bucket structs (with no memory)
|
|
*/
|
|
for (i = 0; i < NBUCKETS; i++) {
|
|
bucket[i].blksize = bucket_size[i];
|
|
bucket[i].nblks = 0;
|
|
bucket[i].freeblks = 0;
|
|
bucket[i].npages = 0;
|
|
bucket[i].s_alloc = 0;
|
|
bucket[i].s_free = 0;
|
|
bucket[i].s_high = 0;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* alloc_block() -- Allocate a block of memory.
|
|
*
|
|
* Similar in function to the memalign() system call.
|
|
*/
|
|
k_ptr_t
|
|
#ifdef ICRASH_DEBUG
|
|
_alloc_block(int size, int flag, caddr_t *ra)
|
|
#else
|
|
alloc_block(int size, int flag)
|
|
#endif
|
|
{
|
|
int i, j;
|
|
caddr_t *blk;
|
|
page_t *p;
|
|
block_t *b = (block_t *)NULL;
|
|
|
|
/* silly, but ....
|
|
*/
|
|
if (size == 0) {
|
|
return((void *)NULL);
|
|
}
|
|
|
|
kl_hold_signals();
|
|
|
|
if (size > IO_NBPC) {
|
|
|
|
/* round size upto the next full page size
|
|
*/
|
|
if (size % IO_NBPC) {
|
|
size += (IO_NBPC - (size % IO_NBPC));
|
|
}
|
|
|
|
/* Check to see if there are any free oversized blocks that are
|
|
* greater than or equal to size.
|
|
*/
|
|
if (p = mempool.ovrszpgs) {
|
|
if (p == p->next) {
|
|
if (p->blksz >= size) {
|
|
REMQUEUE(&mempool.ovrszpgs, p);
|
|
}
|
|
else {
|
|
p = (page_t *)NULL;
|
|
}
|
|
}
|
|
else {
|
|
do {
|
|
if (p->blksz >= size) {
|
|
REMQUEUE(&mempool.ovrszpgs, p);
|
|
break;
|
|
}
|
|
p = p->next;
|
|
} while (p != mempool.ovrszpgs);
|
|
if (p == mempool.ovrszpgs) {
|
|
p = (page_t *)NULL;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (!p) {
|
|
|
|
/* Get a page header
|
|
*/
|
|
p = get_pghdr();
|
|
|
|
/* Get a page of memory
|
|
*/
|
|
if (!(p->addr = (caddr_t *)memalign(IO_NBPC, size))) {
|
|
if (DEBUG(DC_GLOBAL, 1)) {
|
|
fprintf(KL_ERRORFP, "not enough memory to allocate "
|
|
"%d bytes!\n", size);
|
|
}
|
|
return((void *)NULL);
|
|
}
|
|
|
|
/* Set up the page header
|
|
*/
|
|
p->nblocks = 1;
|
|
p->blksz = size;
|
|
p->state = P_OVRSZ;
|
|
p->nfree = 0;
|
|
p->blklist = (block_t *)NULL;
|
|
p->index = OVRSZBKT; /* set index to last bucket */
|
|
}
|
|
|
|
/* Now zero out the page
|
|
*/
|
|
bzero(p->addr, size);
|
|
|
|
/* Add the new page on the bucket pagelist
|
|
*/
|
|
ENQUEUE(&bucket[OVRSZBKT].pagelist, p);
|
|
|
|
/* Update info for oversize bucket
|
|
*/
|
|
bucket[OVRSZBKT].nblks++;
|
|
bucket[OVRSZBKT].npages += (p->blksz / IO_NBPC);
|
|
bucket[OVRSZBKT].s_alloc++;
|
|
|
|
/* Set the high water mark
|
|
*/
|
|
if (bucket[OVRSZBKT].s_high <
|
|
(bucket[OVRSZBKT].nblks - bucket[OVRSZBKT].freeblks)) {
|
|
bucket[OVRSZBKT].s_high =
|
|
(bucket[OVRSZBKT].nblks - bucket[OVRSZBKT].freeblks);
|
|
}
|
|
|
|
#ifdef ICRASH_DEBUG
|
|
b = get_blkhdr();
|
|
#else
|
|
/* All temporary blocks need to have a block header -- so they
|
|
* can be freed up in free_temp_blocks().
|
|
*/
|
|
if (flag == B_TEMP) {
|
|
b = get_blkhdr();
|
|
}
|
|
#endif
|
|
|
|
if (b) {
|
|
b->addr = p->addr;
|
|
#ifdef ICRASH_DEBUG
|
|
b->flag = flag;
|
|
b->page = p;
|
|
b->alloc_pc = ra - 8;
|
|
#endif
|
|
}
|
|
|
|
if (flag == B_TEMP) {
|
|
ENQUEUE(&temp_blks, b);
|
|
}
|
|
#ifdef ICRASH_DEBUG
|
|
else {
|
|
ENQUEUE(&perm_blks, b);
|
|
}
|
|
#endif
|
|
|
|
/* Put the page on the phash[] list
|
|
*/
|
|
add_phash(p);
|
|
|
|
kl_release_signals();
|
|
return(p->addr);
|
|
}
|
|
|
|
/* Find the bucket with the closest fit (next largest) block size.
|
|
* Then, get a block from that bucket.
|
|
*/
|
|
for (i = 0; i < (NBUCKETS - 1); i++) {
|
|
if (bucket[i].blksize < size) {
|
|
continue;
|
|
}
|
|
break;
|
|
}
|
|
|
|
/* Check to see if there are any free blocks.
|
|
*/
|
|
if (bucket[i].freeblks) {
|
|
p = bucket[i].pagelist;
|
|
while (p->blklist == 0) {
|
|
p = p->next;
|
|
#ifdef ICRASH_DEBUG
|
|
assert(p != bucket[i].pagelist);
|
|
#endif
|
|
}
|
|
}
|
|
else {
|
|
if (!(p = get_page(i))) {
|
|
return((void *)NULL);
|
|
}
|
|
}
|
|
|
|
blk = (caddr_t *)DEQUEUE(&p->blklist);
|
|
p->nfree--;
|
|
bzero(blk, p->blksz);
|
|
|
|
#ifdef ICRASH_DEBUG
|
|
b = get_blkhdr();
|
|
#else
|
|
/* All temporary blocks need to have a block header -- so they
|
|
* can be freed up in free_temp_blocks().
|
|
*/
|
|
if (flag == B_TEMP) {
|
|
b = get_blkhdr();
|
|
}
|
|
#endif
|
|
|
|
if (b) {
|
|
b->addr = blk;
|
|
#ifdef ICRASH_DEBUG
|
|
b->flag = flag;
|
|
b->page = p;
|
|
b->alloc_pc = ra - 8;
|
|
#endif
|
|
}
|
|
|
|
if (flag == B_TEMP) {
|
|
ENQUEUE(&temp_blks, b);
|
|
}
|
|
#ifdef ICRASH_DEBUG
|
|
else {
|
|
ENQUEUE(&perm_blks, b);
|
|
}
|
|
#endif
|
|
|
|
bucket[i].freeblks--;
|
|
bucket[i].s_alloc++;
|
|
if (bucket[i].s_high < (bucket[i].nblks - bucket[i].freeblks)) {
|
|
bucket[i].s_high = (bucket[i].nblks - bucket[i].freeblks);
|
|
}
|
|
|
|
|
|
/* Put page header on phash[]
|
|
*/
|
|
kl_release_signals();
|
|
return(blk);
|
|
}
|
|
|
|
/*
|
|
* dup_block()
|
|
*/
|
|
k_ptr_t
|
|
dup_block(caddr_t *b, int flag)
|
|
{
|
|
page_t *p;
|
|
block_t *b1;
|
|
|
|
kl_hold_signals();
|
|
|
|
/* Locate the page header for this block from the phash[] table
|
|
*/
|
|
if (!(p = find_page(b))) {
|
|
return((k_ptr_t)NULL);
|
|
}
|
|
|
|
b1 = alloc_block(p->blksz, flag);
|
|
bcopy(b, b1, p->blksz);
|
|
kl_release_signals();
|
|
return(b1);
|
|
}
|
|
|
|
/*
|
|
* free_blk()
|
|
*/
|
|
free_blk(page_t *p, caddr_t *block)
|
|
{
|
|
block_t *b;
|
|
|
|
/* Get the block header (if there is one) off the temp_blks list
|
|
*/
|
|
if (b = temp_blks) {
|
|
do {
|
|
if (b->addr == block) {
|
|
REMQUEUE(&temp_blks, b);
|
|
ENQUEUE(&mempool.blkhdrs, b);
|
|
mempool.free_blkhdrs++;
|
|
break;
|
|
}
|
|
b = b->next;
|
|
} while (b != temp_blks);
|
|
if (b == temp_blks) {
|
|
b = (block_t *)NULL;
|
|
}
|
|
}
|
|
|
|
#ifdef ICRASH_DEBUG
|
|
/* Try and find the block on the permenant block list
|
|
*/
|
|
if (!b) {
|
|
b = perm_blks;
|
|
do {
|
|
if (b->addr == block) {
|
|
REMQUEUE(&perm_blks, b);
|
|
b->addr = (caddr_t *)NULL;
|
|
ENQUEUE(&mempool.blkhdrs, b);
|
|
mempool.free_blkhdrs++;
|
|
break;
|
|
}
|
|
b = b->next;
|
|
} while (b != perm_blks);
|
|
if (b == perm_blks) {
|
|
b = (block_t *)NULL;
|
|
}
|
|
}
|
|
#endif
|
|
|
|
if (DEBUG(DC_ALLOC, 5)) {
|
|
if (b) {
|
|
fprintf(KL_ERRORFP, "free_blk: b=0x%x, addr=0x%x, alloc_pc=0x%x\n",
|
|
b, b->addr, b->alloc_pc);
|
|
}
|
|
}
|
|
|
|
#ifdef ICRASH_DEBUG
|
|
assert(b);
|
|
#endif
|
|
|
|
/* If the block is oversized...
|
|
*/
|
|
if (p->index == OVRSZBKT) {
|
|
|
|
/* Remove page from bucket pagelist and phash[] list
|
|
*/
|
|
REMQUEUE(&bucket[OVRSZBKT].pagelist, p);
|
|
bucket[OVRSZBKT].nblks--;
|
|
bucket[OVRSZBKT].npages -= (p->blksz / IO_NBPC);
|
|
bucket[OVRSZBKT].s_free++;
|
|
rem_phash(p);
|
|
|
|
#ifdef FREE_OVSZBLKS
|
|
/* Free the memory
|
|
*/
|
|
free (p->addr);
|
|
p->state = P_FREE;
|
|
ENQUEUE(&mempool.pghdrs, p);
|
|
mempool.free_pghdrs++;
|
|
#else
|
|
ENQUEUE(&mempool.ovrszpgs, p);
|
|
#endif
|
|
return(0);
|
|
}
|
|
|
|
/* Queue block on page's freelist
|
|
*/
|
|
ENQUEUE(&p->blklist, block);
|
|
p->nfree++;
|
|
bucket[p->index].freeblks++;
|
|
bucket[p->index].s_free++;
|
|
return(0);
|
|
}
|
|
|
|
/*
|
|
* free_block()
|
|
*/
|
|
int
|
|
free_block(caddr_t *block)
|
|
{
|
|
int ret;
|
|
page_t *p;
|
|
|
|
if (DEBUG(DC_ALLOC, 2) || DEBUG(DC_FUNCTRACE, 8)) {
|
|
fprintf(KL_ERRORFP, "free_block: block=0x%x\n", block);
|
|
}
|
|
|
|
kl_hold_signals();
|
|
|
|
#ifdef ICRASH_DEBUG
|
|
assert(block);
|
|
#endif
|
|
|
|
/* Locate the page header for this block from the phash[] table
|
|
*/
|
|
p = find_page(block);
|
|
|
|
#ifdef ICRASH_DEBUG
|
|
assert(p);
|
|
#endif
|
|
|
|
ret = free_blk(p, block);
|
|
kl_release_signals();
|
|
return(ret);
|
|
}
|
|
|
|
/*
|
|
* free_temp_blocks() -- Free all temporarily allocated blocks
|
|
*/
|
|
void
|
|
free_temp_blocks()
|
|
{
|
|
block_t *b;
|
|
page_t *p;
|
|
caddr_t *addr;
|
|
|
|
kl_hold_signals();
|
|
|
|
while(temp_blks) {
|
|
b = temp_blks;
|
|
p = find_page(b->addr);
|
|
|
|
if (DEBUG(DC_ALLOC, 1)) {
|
|
fprintf(KL_ERRORFP, "free_temp_blocks: b=0x%x, addr=0x%x, size=%d, "
|
|
"alloc_pc=0x%x\n", b, b->addr, p->blksz, b->alloc_pc);
|
|
}
|
|
#ifdef ICRASH_DEBUG
|
|
assert(p);
|
|
#endif
|
|
free_blk(p, b->addr);
|
|
}
|
|
kl_release_signals();
|
|
}
|
|
|
|
/*
|
|
* is_temp_block()
|
|
*/
|
|
int
|
|
is_temp_block(caddr_t *addr)
|
|
{
|
|
block_t *b1;
|
|
|
|
if (b1 = temp_blks) {
|
|
do {
|
|
if (b1->addr == addr) {
|
|
return(1);
|
|
}
|
|
b1 = b1->next;
|
|
} while (b1 != temp_blks);
|
|
}
|
|
return(0);
|
|
}
|