433 lines
11 KiB
C
433 lines
11 KiB
C
/*
|
|
* This file is part of ixemul.library for the Amiga.
|
|
* Copyright (C) 1991, 1992 Markus M. Wild
|
|
*
|
|
* This library is free software; you can redistribute it and/or
|
|
* modify it under the terms of the GNU Library General Public
|
|
* License as published by the Free Software Foundation; either
|
|
* version 2 of the License, or (at your option) any later version.
|
|
*
|
|
* This library is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
* Library General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU Library General Public
|
|
* License along with this library; if not, write to the Free
|
|
* Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
|
*
|
|
* $Id: buddy-alloc.c,v 1.1.1.1 2005/03/15 15:57:08 laire Exp $
|
|
*
|
|
*/
|
|
#define _KERNEL
|
|
#include "ixemul.h"
|
|
#include "kprintf.h"
|
|
#include <exec/memory.h>
|
|
#include <stddef.h>
|
|
|
|
#if 0 //ndef DEBUG_VERSION
|
|
#define BUDDY_DEBUG if (0)
|
|
#else
|
|
#define BUDDY_DEBUG
|
|
#endif
|
|
|
|
#ifdef USE_VMEM
|
|
# ifndef MEMF_SWAP
|
|
# define MEMF_SWAP (1L<<11)
|
|
# endif
|
|
#else
|
|
# undef MEMF_SWAP
|
|
# define MEMF_SWAP 0
|
|
#endif
|
|
|
|
#ifdef TRACK_ALLOCS
|
|
|
|
#undef AllocMem
|
|
#undef FreeMem
|
|
|
|
#define AllocMem(x,y) debug_AllocMem("malloc",x,y)
|
|
#define FreeMem(x,y) debug_FreeMem(x,y)
|
|
|
|
#define MEMMAGIC 0x45134384
|
|
|
|
struct mem_tracker {
|
|
struct ixnode node;
|
|
int magic;
|
|
int size;
|
|
const char *id;
|
|
};
|
|
|
|
struct ixlist memlist;
|
|
|
|
void
|
|
dump_memlist(void)
|
|
{
|
|
struct mem_tracker *p;
|
|
dprintf("---------- Allocated memory ----------\n");
|
|
Forbid();
|
|
for (p = (struct mem_tracker *)memlist.head; p; p = (struct mem_tracker *)p->node.next)
|
|
{
|
|
dprintf("0x%08lx 0x%08lx %s\n", p + 1, p->size, p->id);
|
|
}
|
|
Permit();
|
|
dprintf("--------------------------------------\n");
|
|
}
|
|
|
|
void *
|
|
debug_AllocMem(const char *id, int size, int reqs)
|
|
{
|
|
struct mem_tracker *p;
|
|
|
|
Forbid();
|
|
p = AllocVec(size + sizeof(*p), reqs);
|
|
if (p)
|
|
{
|
|
ixaddtail(&memlist, &p->node);
|
|
p->magic = MEMMAGIC;
|
|
p->size = size;
|
|
p->id = id;
|
|
++p;
|
|
}
|
|
Permit();
|
|
|
|
return p;
|
|
}
|
|
|
|
void
|
|
debug_FreeMem(void *p, int size)
|
|
{
|
|
if (p)
|
|
{
|
|
struct mem_tracker *q = (struct mem_tracker *)p - 1;
|
|
|
|
Forbid();
|
|
if (q->magic != MEMMAGIC)
|
|
{
|
|
dprintf("FreeMem a bad block: 0x%x size %d\n", p, size);
|
|
*(char *)0 = 0;
|
|
}
|
|
else if (q->size != size)
|
|
{
|
|
dprintf("FreeMem with bad size: 0x%x size %d old %d\n", p, size, q->size);
|
|
*(char *)0 = 0;
|
|
}
|
|
else
|
|
{
|
|
ixremove(&memlist, &q->node);
|
|
q->magic = 0;
|
|
FreeVec(q);
|
|
}
|
|
Permit();
|
|
}
|
|
}
|
|
|
|
#endif
|
|
|
|
|
|
/* this provides a straight replacement for AllocMem() and FreeMem().
|
|
Being this, it does *not* remember the size of allocation, the
|
|
clients have to do this instead. */
|
|
|
|
/* NOTE: currently only two pools are supported, MEMF_PUBLIC and
|
|
! MEMF_PUBLIC. No MEMF_CHIP pools are needed by the library
|
|
and are thus not supported */
|
|
|
|
|
|
/* TUNING: The two parameters that can be adjusted to fine tune
|
|
allocation strategy are MAXSIZE and BUDDY_LIMIT. By setting
|
|
MAXSIZE larger than BUDDY_LIMIT results in less Exec
|
|
overhead, since blocks stay longer in the buddy system.
|
|
Setting MAXSIZE==BUDDY_LIMIT sets memory usage to the
|
|
minimum, at the cost of more Exec calls. */
|
|
|
|
|
|
/* no request for memory can be lower than this */
|
|
#define MINLOG2 4
|
|
#define MINSIZE (1 << MINLOG2)
|
|
|
|
/* this is the size the buddy system gets memory pieces from Exec */
|
|
#define MAXLOG2 16 /* get 64K chunks */
|
|
#define MAXSIZE (1 << MAXLOG2)
|
|
|
|
/* this is the limit for b_alloc to go straight to Exec */
|
|
#define BUDDY_LIMIT (1 << (MAXLOG2 - 5)) /* but serve only upto 1K */
|
|
//#define BUDDY_LIMIT 8
|
|
#define PRIVATE_POOL 0
|
|
#define PUBLIC_POOL 1
|
|
#define NUMPOOLS 2 /* public and !public */
|
|
/* attention: don't go larger than 3 pools, or you'll have to change the
|
|
encoding in free_block (only 2 bits for now) */
|
|
|
|
struct free_list {
|
|
u_int exec_attr;
|
|
struct ix_mutex sem;
|
|
struct ixlist buckets[MAXLOG2 - MINLOG2];
|
|
} free_list[NUMPOOLS] = { { MEMF_SWAP, }, { MEMF_PUBLIC, } };
|
|
|
|
|
|
struct free_block {
|
|
/* to make the smallest allocatable block 16, and not 32 byte, stuff both
|
|
the freelist information and the exec-block address into one long. */
|
|
u_int pool:2, /* 0: block is free, > 0: POOL + 1 */
|
|
exec_block:30; /* shift left twice to get the real address */
|
|
|
|
/* from here on, fields only exist while the block is on the free list.
|
|
The application sees a block as a chunk of memory starting at &next */
|
|
struct free_block *next, *prev; /* ixnode compatible */
|
|
int index;
|
|
};
|
|
|
|
|
|
void
|
|
init_buddy (void)
|
|
{
|
|
int i, l;
|
|
|
|
/* don't want such a nightmare of bug-hunt any more... */
|
|
if (sizeof (struct free_block) > MINSIZE)
|
|
{
|
|
ix_panic ("buddy-system: MINSIZE/MINLOG2 too small, increase!");
|
|
Wait (0);
|
|
}
|
|
|
|
for (l = 0; l < NUMPOOLS; l++)
|
|
{
|
|
for (i = 0; i < MAXLOG2 - MINLOG2; i++)
|
|
ixnewlist ((struct ixlist *)&free_list[l].buckets[i]);
|
|
}
|
|
}
|
|
|
|
static inline struct free_block *
|
|
unlink_block (u_int free_pool, u_char ind, void *block)
|
|
{
|
|
struct free_block *fb = (struct free_block *) block;
|
|
struct free_list *fl = free_list + free_pool;
|
|
|
|
if (! fb)
|
|
{
|
|
fb = (struct free_block *)ixremhead((struct ixlist *)&fl->buckets[ind]);
|
|
if (fb)
|
|
{
|
|
fb = (struct free_block *) ((int)fb - offsetof (struct free_block, next));
|
|
fb->pool = free_pool + 1;
|
|
BUDDY_DEBUG KPRINTF((" unlink_block (%s, %ld) == $%lx\n",
|
|
free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), ind, fb));
|
|
|
|
}
|
|
}
|
|
else
|
|
{
|
|
BUDDY_DEBUG KPRINTF((" unlink_block (%s, %ld, $%lx)\n",
|
|
free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), ind, fb));
|
|
|
|
fb->pool = free_pool + 1;
|
|
ixremove ((struct ixlist *)&fl->buckets[fb->index], (struct ixnode *)&fb->next);
|
|
}
|
|
|
|
return fb;
|
|
}
|
|
|
|
static void inline
|
|
link_block (u_int free_pool, u_char ind, void *block)
|
|
{
|
|
struct free_block *fb = (struct free_block *) block;
|
|
struct free_list *fl = free_list + free_pool;
|
|
|
|
BUDDY_DEBUG KPRINTF((" link_block (%s, %ld, $%lx)\n",
|
|
free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), ind, fb));
|
|
|
|
fb->pool = 0; /* we're on the freelist of this pool */
|
|
fb->index = ind; /* and of this size */
|
|
ixaddhead ((struct ixlist *)&fl->buckets[ind], (struct ixnode *)&fb->next);
|
|
}
|
|
|
|
/* this is a very special log2() function that knows the upper bound
|
|
of its argument, and also automatically rounds to the next upper
|
|
power of two */
|
|
|
|
static inline int const
|
|
log2 (int size)
|
|
{
|
|
int pow = MAXLOG2;
|
|
int lower_bound = 1 << (MAXLOG2 - 1);
|
|
|
|
for (;;)
|
|
{
|
|
if (size > lower_bound)
|
|
return pow;
|
|
|
|
lower_bound >>= 1;
|
|
pow--;
|
|
}
|
|
}
|
|
|
|
|
|
static inline struct free_block *
|
|
get_block (u_int free_pool, u_char index)
|
|
{
|
|
struct free_block *fb, *buddy;
|
|
struct free_list *fl = free_list + free_pool;
|
|
|
|
BUDDY_DEBUG KPRINTF((" get_block (%s, %ld)\n",
|
|
free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), index, fb));
|
|
|
|
if (index == (MAXLOG2 - MINLOG2))
|
|
{
|
|
fb = (struct free_block *) AllocMem (MAXSIZE, fl->exec_attr);
|
|
if (! fb)
|
|
{
|
|
KPRINTF(("get_bloc: AllocMem(%ld, %lx) failed\n", MAXSIZE, fl->exec_attr));
|
|
return 0;
|
|
}
|
|
|
|
fb->exec_block = (int)fb >> 2; /* buddies are relative to this base address */
|
|
fb->pool = free_pool + 1; /* not free */
|
|
|
|
return fb;
|
|
}
|
|
else
|
|
{
|
|
if ((fb = unlink_block (free_pool, index, 0)))
|
|
return fb;
|
|
}
|
|
|
|
|
|
fb = get_block (free_pool, index + 1);
|
|
|
|
if (fb)
|
|
{
|
|
/* when splitting a block, we always free the upper buddy. So
|
|
we can just add the size, instead of or'ing the offset to the
|
|
Exec memory block */
|
|
buddy = (struct free_block *)((int)fb + (1 << (index + MINLOG2)));
|
|
|
|
buddy->exec_block = fb->exec_block;
|
|
|
|
link_block (free_pool, index, buddy);
|
|
}
|
|
|
|
return fb;
|
|
}
|
|
|
|
|
|
static inline void
|
|
free_block (u_int free_pool, u_char index, struct free_block *fb)
|
|
{
|
|
struct free_block *buddy;
|
|
|
|
buddy = (struct free_block *)
|
|
((((int)fb - (fb->exec_block<<2)) ^ (1 << (index + MINLOG2)))
|
|
+ (fb->exec_block<<2));
|
|
|
|
if (index == (MAXLOG2 - MINLOG2))
|
|
{
|
|
FreeMem (fb, MAXSIZE);
|
|
return;
|
|
}
|
|
else if (buddy->pool || buddy->index != index)
|
|
{
|
|
/* too bad, buddy is not on freelist or of wrong size */
|
|
link_block (free_pool, index, fb);
|
|
return;
|
|
}
|
|
|
|
/* reserve the buddy, then recombine both */
|
|
unlink_block (free_pool, index, buddy);
|
|
|
|
/* since the buddy is free as well, recombine both blocks
|
|
and free the twice as large block */
|
|
free_block (free_pool, index + 1, fb < buddy ? fb : buddy);
|
|
}
|
|
|
|
|
|
void *
|
|
b_alloc (int size, unsigned pool)
|
|
{
|
|
u_char bucket;
|
|
struct free_block *block;
|
|
struct free_list *fl = free_list + pool;
|
|
|
|
if (size < 0) /* Ridiculous size */
|
|
return 0;
|
|
if (size < MINSIZE)
|
|
size = MINSIZE;
|
|
|
|
/* the additional bytes are needed for the freelist pointer at
|
|
the beginning of each block in use and the base block originally
|
|
obtained from Exec. */
|
|
|
|
if (size >= BUDDY_LIMIT - offsetof (struct free_block, next))
|
|
return AllocMem (size, fl->exec_attr);
|
|
|
|
size += offsetof (struct free_block, next);
|
|
|
|
bucket = log2 (size) - MINLOG2;
|
|
|
|
/* have to differentiate between PUBLIC and PRIVATE memory here, sigh.
|
|
PRIVATE memory can safely be accessed by using a semaphore, PUBLIC
|
|
memory however is allocated and free'd inside Forbid(), and using a
|
|
semaphore there would possibly break a Forbid..
|
|
Note: this is safe for use in GigaMem, as GigaMem only uses non-PUBLIC
|
|
memory, if you don't fiddle with attribute masks.. */
|
|
/*if (pool == PRIVATE_POOL)
|
|
{
|
|
ix_mutex_lock(&fl->sem);
|
|
block = get_block (pool, bucket);
|
|
ix_mutex_unlock(&fl->sem);
|
|
}
|
|
else*/
|
|
{
|
|
Forbid();
|
|
block = get_block (pool, bucket);
|
|
Permit();
|
|
}
|
|
|
|
if (block)
|
|
return (void *) & block->next;
|
|
else
|
|
return block;
|
|
}
|
|
|
|
|
|
void
|
|
b_free (void *mem, int size)
|
|
{
|
|
u_char bucket;
|
|
struct free_list *fl;
|
|
struct free_block *fb;
|
|
int free_pool;
|
|
|
|
if (size < MINSIZE)
|
|
size = MINSIZE;
|
|
|
|
if (size >= BUDDY_LIMIT - offsetof (struct free_block, next))
|
|
{
|
|
FreeMem(mem, size);
|
|
return;
|
|
}
|
|
|
|
size += offsetof (struct free_block, next);
|
|
|
|
bucket = log2 (size) - MINLOG2;
|
|
fb = (struct free_block *) ((int)mem - offsetof (struct free_block, next));
|
|
free_pool = fb->pool - 1;
|
|
fl = free_list + free_pool;
|
|
|
|
/*if (free_pool == PRIVATE_POOL)
|
|
{
|
|
ix_mutex_lock(&fl->sem);
|
|
free_block (free_pool, bucket, fb);
|
|
ix_mutex_unlock(&fl->sem);
|
|
}
|
|
else*/
|
|
{
|
|
Forbid();
|
|
free_block (free_pool, bucket, fb);
|
|
Permit();
|
|
}
|
|
}
|
|
|
|
void cleanup_buddy(void)
|
|
{
|
|
}
|