/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (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
* or http://www.opensolaris.org/os/licensing.
* 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 2005 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#if 1
#undef DEBUG
#endif
/* #define DEBUG ON */
/*
* Conditions on use:
* kmem_alloc and kmem_free must not be called from interrupt level,
* except from software interrupt level. This is because they are
* not reentrant, and only block out software interrupts. They take
* too long to block any real devices. There is a routine
* kmem_free_intr that can be used to free blocks at interrupt level,
* but only up to splimp, not higher. This is because kmem_free_intr
* only spl's to splimp.
*
* Also, these routines are not that fast, so they should not be used
* in very frequent operations (e.g. operations that happen more often
* than, say, once every few seconds).
*/
/*
* description:
* Yet another memory allocator, this one based on a method
* described in C.J. Stephenson, "Fast Fits", IBM Sys. Journal
*
* The basic data structure is a "Cartesian" binary tree, in which
* nodes are ordered by ascending addresses (thus minimizing free
* list insertion time) and block sizes decrease with depth in the
* tree (thus minimizing search time for a block of a given size).
*
* In other words, for any node s, letting D(s) denote
* the set of descendents of s, we have:
*
* a. addr(D(left(s))) < addr(s) < addr(D(right(s)))
* b. len(D(left(s))) <= len(s) >= len(D(right(s)))
*/
#include <sys/param.h>
#include <sys/sysmacros.h>
#include <sys/salib.h>
#include <sys/saio.h>
#include <sys/promif.h>
/*
* The node header structure.
*
* To reduce storage consumption, a header block is associated with
* free blocks only, not allocated blocks.
* When a free block is allocated, its header block is put on
* a free header block list.
*
* This creates a header space and a free block space.
* The left pointer of a header blocks is used to chain free header
* blocks together.
*/
typedef enum {false, true} bool;
typedef struct freehdr *Freehdr;
typedef struct dblk *Dblk;
/*
* Description of a header for a free block
* Only free blocks have such headers.
*/
struct freehdr {
Freehdr left; /* Left tree pointer */
Freehdr right; /* Right tree pointer */
Dblk block; /* Ptr to the data block */
size_t size; /* Size of the data block */
};
#define NIL ((Freehdr) 0)
#define WORDSIZE sizeof (int)
#define SMALLEST_BLK 1 /* Size of smallest block */
/*
* Description of a data block.
*/
struct dblk {
char data[1]; /* Addr returned to the caller */
};
/*
* weight(x) is the size of a block, in bytes; or 0 if and only if x
* is a null pointer. It is the responsibility of kmem_alloc() and
* kmem_free() to keep zero-length blocks out of the arena.
*/
#define weight(x) ((x) == NIL? 0: (x->size))
#define nextblk(p, size) ((Dblk) ((char *)(p) + (size)))
#define max(a, b) ((a) < (b)? (b): (a))
void *kmem_alloc(size_t, int);
void kmem_free(void *ptr, size_t nbytes);
Freehdr getfreehdr(void);
static bool morecore(size_t);
void insert(Dblk p, size_t len, Freehdr *tree);
void freehdr(Freehdr p);
void delete(Freehdr *p);
static void check_need_to_free(void);
extern caddr_t resalloc(enum RESOURCES, size_t, caddr_t, int);
#ifdef __sparc
extern void resalloc_init(void);
#endif
extern int splnet(void);
extern int splimp(void);
extern void splx(int);
/*
* Structure containing various info about allocated memory.
*/
#define NEED_TO_FREE_SIZE 5
struct kmem_info {
Freehdr free_root;
Freehdr free_hdr_list;
struct map *map;
struct pte *pte;
caddr_t vaddr;
struct need_to_free {
caddr_t addr;
size_t nbytes;
} need_to_free_list, need_to_free[NEED_TO_FREE_SIZE];
} kmem_info;
struct map *kernelmap;
#ifdef DEBUG
static void prtree(Freehdr, char *);
#endif
/*
* Initialize kernel memory allocator
*/
void
kmem_init(void)
{
int i;
struct need_to_free *ntf;
#ifdef DEBUG
printf("kmem_init entered\n");
#endif
#ifdef __sparc
resalloc_init();
#endif
kmem_info.free_root = NIL;
kmem_info.free_hdr_list = NULL;
kmem_info.map = kernelmap;
kmem_info.need_to_free_list.addr = 0;
ntf = kmem_info.need_to_free;
for (i = 0; i < NEED_TO_FREE_SIZE; i++) {
ntf[i].addr = 0;
}
#ifdef DEBUG
printf("kmem_init returning\n");
prtree(kmem_info.free_root, "kmem_init");
#endif
}
/*
* Insert a new node in a cartesian tree or subtree, placing it
* in the correct position with respect to the existing nodes.
*
* algorithm:
* Starting from the root, a binary search is made for the new
* node. If this search were allowed to continue, it would
* eventually fail (since there cannot already be a node at the
* given address); but in fact it stops when it reaches a node in
* the tree which has a length less than that of the new node (or
* when it reaches a null tree pointer). The new node is then
* inserted at the root of the subtree for which the shorter node
* forms the old root (or in place of the null pointer).
*/
void
insert(Dblk p, /* Ptr to the block to insert */
size_t len, /* Length of new node */
Freehdr *tree) /* Address of ptr to root */
{
Freehdr x;
Freehdr *left_hook; /* Temp for insertion */
Freehdr *right_hook; /* Temp for insertion */
Freehdr newhdr;
x = *tree;
/*
* Search for the first node which has a weight less
* than that of the new node; this will be the
* point at which we insert the new node.
*/
while (weight(x) >= len) {
if (p < x->block)
tree = &x->left;
else
tree = &x->right;
x = *tree;
}
/*
* Perform root insertion. The variable x traces a path through
* the tree, and with the help of left_hook and right_hook,
* rewrites all links that cross the territory occupied
* by p. Note that this improves performance under
* paging.
*/
newhdr = getfreehdr();
*tree = newhdr;
left_hook = &newhdr->left;
right_hook = &newhdr->right;
newhdr->left = NIL;
newhdr->right = NIL;
newhdr->block = p;
newhdr->size = len;
while (x != NIL) {
/*
* Remark:
* The name 'left_hook' is somewhat confusing, since
* it is always set to the address of a .right link
* field. However, its value is always an address
* below (i.e., to the left of) p. Similarly
* for right_hook. The values of left_hook and
* right_hook converge toward the value of p,
* as in a classical binary search.
*/
if (x->block < p) {
/*
* rewrite link crossing from the left
*/
*left_hook = x;
left_hook = &x->right;
x = x->right;
} else {
/*
* rewrite link crossing from the right
*/
*right_hook = x;
right_hook = &x->left;
x = x->left;
} /* else */
} /* while */
*left_hook = *right_hook = NIL; /* clear remaining hooks */
} /* insert */
/*
* Delete a node from a cartesian tree. p is the address of
* a pointer to the node which is to be deleted.
*
* algorithm:
* The left and right sons of the node to be deleted define two
* subtrees which are to be merged and attached in place of the
* deleted node. Each node on the inside edges of these two
* subtrees is examined and longer nodes are placed above the
* shorter ones.
*
* On entry:
* *p is assumed to be non-null.
*/
void
delete(Freehdr *p)
{
Freehdr x;
Freehdr left_branch; /* left subtree of deleted node */
Freehdr right_branch; /* right subtree of deleted node */
x = *p;
left_branch = x->left;
right_branch = x->right;
while (left_branch != right_branch) {
/*
* iterate until left branch and right branch are
* both NIL.
*/
if (weight(left_branch) >= weight(right_branch)) {
/*
* promote the left branch
*/
*p = left_branch;
p = &left_branch->right;
left_branch = left_branch->right;
} else {
/*
* promote the right branch
*/
*p = right_branch;
p = &right_branch->left;
right_branch = right_branch->left;
} /* else */
} /* while */
*p = NIL;
freehdr(x);
} /* delete */
/*
* Demote a node in a cartesian tree, if necessary, to establish
* the required vertical ordering.
*
* algorithm:
* The left and right subtrees of the node to be demoted are to
* be partially merged and attached in place of the demoted node.
* The nodes on the inside edges of these two subtrees are
* examined and the longer nodes are placed above the shorter
* ones, until a node is reached which has a length no greater
* than that of the node being demoted (or until a null pointer
* is reached). The node is then attached at this point, and
* the remaining subtrees (if any) become its descendants.
*
* on entry:
* a. All the nodes in the tree, including the one to be demoted,
* must be correctly ordered horizontally;
* b. All the nodes except the one to be demoted must also be
* correctly positioned vertically. The node to be demoted
* may be already correctly positioned vertically, or it may
* have a length which is less than that of one or both of
* its progeny.
* c. *p is non-null
*/
static void
demote(Freehdr *p)
{
Freehdr x; /* addr of node to be demoted */
Freehdr left_branch;
Freehdr right_branch;
size_t wx;
x = *p;
left_branch = x->left;
right_branch = x->right;
wx = weight(x);
while (weight(left_branch) > wx || weight(right_branch) > wx) {
/*
* select a descendant branch for promotion
*/
if (weight(left_branch) >= weight(right_branch)) {
/*
* promote the left branch
*/
*p = left_branch;
p = &left_branch->right;
left_branch = *p;
} else {
/*
* promote the right branch
*/
*p = right_branch;
p = &right_branch->left;
right_branch = *p;
} /* else */
} /* while */
*p = x; /* attach demoted node here */
x->left = left_branch;
x->right = right_branch;
} /* demote */
/*
* Allocate a block of storage
*
* algorithm:
* The freelist is searched by descending the tree from the root
* so that at each decision point the "better fitting" child node
* is chosen (i.e., the shorter one, if it is long enough, or
* the longer one, otherwise). The descent stops when both
* child nodes are too short.
*
* function result:
* kmem_alloc returns a pointer to the allocated block; a null
* pointer indicates storage could not be allocated.
*/
/*
* We need to return blocks that are on word boundaries so that callers
* that are putting int's into the area will work. Since we allow
* arbitrary free'ing, we need a weight function that considers
* free blocks starting on an odd boundary special. Allocation is
* aligned to 8 byte boundaries (ALIGN).
*/
#define ALIGN 8 /* doubleword aligned .. */
#define ALIGNMASK (ALIGN-1)
#define ALIGNMORE(addr) (ALIGN - ((uintptr_t)(addr) & ALIGNMASK))
/*
* If it is empty then weight == 0
* If it is aligned then weight == size
* If it is unaligned
* if not enough room to align then weight == 0
* else weight == aligned size
*/
#define mweight(x) ((x) == NIL ? 0 : \
((((uintptr_t)(x)->block) & ALIGNMASK) == 0 ? (x)->size : \
(((x)->size <= ALIGNMORE((x)->block)) ? 0 : \
(x)->size - ALIGNMORE((x)->block))))
/*ARGSUSED1*/
void *
kmem_alloc(size_t nbytes, int kmflag)
{
Freehdr a; /* ptr to node to be allocated */
Freehdr *p; /* address of ptr to node */
size_t left_weight;
size_t right_weight;
Freehdr left_son;
Freehdr right_son;
char *retblock; /* Address returned to the user */
int s;
#ifdef DEBUG
printf("kmem_alloc(nbytes 0x%lx)\n", nbytes);
#endif /* DEBUG */
if (nbytes == 0) {
return (NULL);
}
s = splnet();
if (nbytes < SMALLEST_BLK) {
printf("illegal kmem_alloc call for %lx bytes\n", nbytes);
prom_panic("kmem_alloc");
}
check_need_to_free();
/*
* ensure that at least one block is big enough to satisfy
* the request.
*/
if (mweight(kmem_info.free_root) <= nbytes) {
/*
* the largest block is not enough.
*/
if (!morecore(nbytes)) {
printf("kmem_alloc failed, nbytes %lx\n", nbytes);
prom_panic("kmem_alloc");
}
}
/*
* search down through the tree until a suitable block is
* found. At each decision point, select the better
* fitting node.
*/
p = (Freehdr *) &kmem_info.free_root;
a = *p;
left_son = a->left;
right_son = a->right;
left_weight = mweight(left_son);
right_weight = mweight(right_son);
while (left_weight >= nbytes || right_weight >= nbytes) {
if (left_weight <= right_weight) {
if (left_weight >= nbytes) {
p = &a->left;
a = left_son;
} else {
p = &a->right;
a = right_son;
}
} else {
if (right_weight >= nbytes) {
p = &a->right;
a = right_son;
} else {
p = &a->left;
a = left_son;
}
}
left_son = a->left;
right_son = a->right;
left_weight = mweight(left_son);
right_weight = mweight(right_son);
} /* while */
/*
* allocate storage from the selected node.
*/
if (a->size - nbytes < SMALLEST_BLK) {
/*
* not big enough to split; must leave at least
* a dblk's worth of space.
*/
retblock = a->block->data;
delete(p);
} else {
/*
* split the node, allocating nbytes from the top.
* Remember we've already accounted for the
* allocated node's header space.
*/
Freehdr x;
x = getfreehdr();
if ((uintptr_t)a->block->data & ALIGNMASK) {
size_t size;
if (a->size <= ALIGNMORE(a->block->data))
prom_panic("kmem_alloc: short block allocated");
size = nbytes + ALIGNMORE(a->block->data);
x->block = a->block;
x->size = ALIGNMORE(a->block->data);
x->left = a->left;
x->right = a->right;
/*
* the node pointed to by *p has become smaller;
* move it down to its appropriate place in
* the tree.
*/
*p = x;
demote(p);
retblock = a->block->data + ALIGNMORE(a->block->data);
if (a->size > size) {
kmem_free((caddr_t)nextblk(a->block, size),
(size_t)(a->size - size));
}
freehdr(a);
} else {
x->block = nextblk(a->block, nbytes);
x->size = a->size - nbytes;
x->left = a->left;
x->right = a->right;
/*
* the node pointed to by *p has become smaller;
* move it down to its appropriate place in
* the tree.
*/
*p = x;
demote(p);
retblock = a->block->data;
freehdr(a);
}
}
#ifdef DEBUG
prtree(kmem_info.free_root, "kmem_alloc");
#endif
splx(s);
bzero(retblock, nbytes);
#ifdef DEBUG
printf("kmem_alloc bzero complete - returning %p\n", retblock);
#endif
return (retblock);
} /* kmem_alloc */
/*
* Return a block to the free space tree.
*
* algorithm:
* Starting at the root, search for and coalesce free blocks
* adjacent to one given. When the appropriate place in the
* tree is found, insert the given block.
*
* Do some sanity checks to avoid total confusion in the tree.
* If the block has already been freed, prom_panic.
* If the ptr is not from the arena, prom_panic.
*/
void
kmem_free(void *ptr, size_t nbytes)
{
Freehdr *np; /* For deletion from free list */
Freehdr neighbor; /* Node to be coalesced */
char *neigh_block; /* Ptr to potential neighbor */
size_t neigh_size; /* Size of potential neighbor */
int s;
#ifdef DEBUG
printf("kmem_free (ptr %p nbytes %lx)\n", ptr, nbytes);
prtree(kmem_info.free_root, "kmem_free");
#endif
#ifdef lint
neigh_block = bkmem_zalloc(nbytes);
neigh_block = neigh_block;
#endif
if (nbytes == 0) {
return;
}
if (ptr == 0) {
prom_panic("kmem_free of 0");
}
s = splnet();
/*
* Search the tree for the correct insertion point for this
* node, coalescing adjacent free blocks along the way.
*/
np = &kmem_info.free_root;
neighbor = *np;
while (neighbor != NIL) {
neigh_block = (char *)neighbor->block;
neigh_size = neighbor->size;
if ((char *)ptr < neigh_block) {
if ((char *)ptr + nbytes == neigh_block) {
/*
* Absorb and delete right neighbor
*/
nbytes += neigh_size;
delete(np);
} else if ((char *)ptr + nbytes > neigh_block) {
/*
* The block being freed overlaps
* another block in the tree. This
* is bad news.
*/
printf("kmem_free: free block overlap %p+%lx"
" over %p\n", (void *)ptr, nbytes,
(void *)neigh_block);
prom_panic("kmem_free: free block overlap");
} else {
/*
* Search to the left
*/
np = &neighbor->left;
}
} else if ((char *)ptr > neigh_block) {
if (neigh_block + neigh_size == ptr) {
/*
* Absorb and delete left neighbor
*/
ptr = neigh_block;
nbytes += neigh_size;
delete(np);
} else if (neigh_block + neigh_size > (char *)ptr) {
/*
* This block has already been freed
*/
prom_panic("kmem_free block already free");
} else {
/*
* search to the right
*/
np = &neighbor->right;
}
} else {
/*
* This block has already been freed
* as "ptr == neigh_block"
*/
prom_panic("kmem_free: block already free as neighbor");
} /* else */
neighbor = *np;
} /* while */
/*
* Insert the new node into the free space tree
*/
insert((Dblk) ptr, nbytes, &kmem_info.free_root);
#ifdef DEBUG
printf("exiting kmem_free\n");
prtree(kmem_info.free_root, "kmem_free");
#endif
splx(s);
} /* kmem_free */
/*
* Sigh. We include a header file which the kernel
* uses to declare (one of its many) kmem_free prototypes.
* In order not to use the kernel's namespace, then, we must
* define another name here for use by boot.
*/
void *
bkmem_alloc(size_t size)
{
return (kmem_alloc(size, 0));
}
/*
* Boot's kmem_alloc is really kmem_zalloc().
*/
void *
bkmem_zalloc(size_t size)
{
return (kmem_alloc(size, 0));
}
void
bkmem_free(void *p, size_t bytes)
{
kmem_free(p, bytes);
}
static void
check_need_to_free(void)
{
int i;
struct need_to_free *ntf;
caddr_t addr;
size_t nbytes;
int s;
again:
s = splimp();
ntf = &kmem_info.need_to_free_list;
if (ntf->addr) {
addr = ntf->addr;
nbytes = ntf->nbytes;
*ntf = *(struct need_to_free *)ntf->addr;
splx(s);
kmem_free(addr, nbytes);
goto again;
}
ntf = kmem_info.need_to_free;
for (i = 0; i < NEED_TO_FREE_SIZE; i++) {
if (ntf[i].addr) {
addr = ntf[i].addr;
nbytes = ntf[i].nbytes;
ntf[i].addr = 0;
splx(s);
kmem_free(addr, nbytes);
goto again;
}
}
splx(s);
}
/*
* Add a block of at least nbytes to the free space tree.
*
* return value:
* true if at least nbytes can be allocated
* false otherwise
*
* remark:
* free space (delimited by the static variable ubound) is
* extended by an amount determined by rounding nbytes up to
* a multiple of the system page size.
*/
static bool
morecore(size_t nbytes)
{
#ifdef __sparc
enum RESOURCES type = RES_BOOTSCRATCH_NOFAIL;
#else
enum RESOURCES type = RES_BOOTSCRATCH;
#endif
Dblk p;
#ifdef DEBUG
printf("morecore(nbytes 0x%lx)\n", nbytes);
#endif /* DEBUG */
nbytes = roundup(nbytes, PAGESIZE);
p = (Dblk) resalloc(type, nbytes, (caddr_t)0, 0);
if (p == 0) {
return (false);
}
kmem_free((caddr_t)p, nbytes);
#ifdef DEBUG
printf("morecore() returing, p = %p\n", p);
#endif
return (true);
} /* morecore */
/*
* Get a free block header
* There is a list of available free block headers.
* When the list is empty, allocate another pagefull.
*/
Freehdr
getfreehdr(void)
{
Freehdr r;
int n = 0;
#ifdef DEBUG
printf("getfreehdr()\n");
#endif /* DEBUG */
if (kmem_info.free_hdr_list != NIL) {
r = kmem_info.free_hdr_list;
kmem_info.free_hdr_list = kmem_info.free_hdr_list->left;
} else {
r = (Freehdr)resalloc(RES_BOOTSCRATCH, PAGESIZE, (caddr_t)0, 0);
if (r == 0) {
prom_panic("getfreehdr");
}
for (n = 1; n < PAGESIZE / sizeof (*r); n++) {
freehdr(&r[n]);
}
}
#ifdef DEBUG
printf("getfreehdr: freed %x headers\n", n);
printf("getfreehdr: returning %p\n", r);
#endif /* DEBUG */
return (r);
}
/*
* Free a free block header
* Add it to the list of available headers.
*/
void
freehdr(Freehdr p)
{
#ifdef DEBUG
printf("freehdr(%p)\n", p);
#endif /* DEBUG */
p->left = kmem_info.free_hdr_list;
p->right = NIL;
p->block = NULL;
kmem_info.free_hdr_list = p;
}
#ifdef DEBUG
/*
* Diagnostic routines
*/
static int depth = 0;
static void
prtree(Freehdr p, char *cp)
{
int n;
if (depth == 0) {
printf("prtree(p %p cp %s)\n", p, cp);
}
if (p != NIL) {
depth++;
prtree(p->left, (char *)NULL);
depth--;
for (n = 0; n < depth; n++) {
printf(" ");
}
printf(
"(%p): (left = %p, right = %p, block = %p, size = %lx)\n",
p, p->left, p->right, p->block, p->size);
depth++;
prtree(p->right, (char *)NULL);
depth--;
}
}
#endif /* DEBUG */