Minix1.5/mm/alloc.c
/* This file is concerned with allocating and freeing arbitrary-size blocks of
* physical memory on behalf of the FORK and EXEC system calls. The key data
* structure used is the hole table, which maintains a list of holes in memory.
* It is kept sorted in order of increasing memory address. The addresses
* it contains refer to physical memory, starting at absolute address 0
* (i.e., they are not relative to the start of MM). During system
* initialization, that part of memory containing the interrupt vectors,
* kernel, and MM are "allocated" to mark them as not available and to
* remove them from the hole list.
*
* The entry points into this file are:
* alloc_mem: allocate a given sized chunk of memory
* free_mem: release a previously allocated chunk of memory
* mem_init: initialize the tables when MM start up
* max_hole: returns the largest hole currently available
* mem_left: returns the sum of the sizes of all current holes
*/
#include "mm.h"
#define NR_HOLES 128 /* max # entries in hole table */
#define NIL_HOLE (struct hole *) 0
PRIVATE struct hole {
phys_clicks h_base; /* where does the hole begin? */
phys_clicks h_len; /* how big is the hole? */
struct hole *h_next; /* pointer to next entry on the list */
} hole[NR_HOLES];
PRIVATE struct hole *hole_head; /* pointer to first hole */
PRIVATE struct hole *free_slots; /* ptr to list of unused table slots */
FORWARD void del_slot();
FORWARD void merge();
/*===========================================================================*
* alloc_mem *
*===========================================================================*/
PUBLIC phys_clicks alloc_mem(clicks)
phys_clicks clicks; /* amount of memory requested */
{
/* Allocate a block of memory from the free list using first fit. The block
* consists of a sequence of contiguous bytes, whose length in clicks is
* given by 'clicks'. A pointer to the block is returned. The block is
* always on a click boundary. This procedure is called when memory is
* needed for FORK or EXEC.
*/
register struct hole *hp, *prev_ptr;
phys_clicks old_base;
hp = hole_head;
while (hp != NIL_HOLE) {
if (hp->h_len >= clicks) {
/* We found a hole that is big enough. Use it. */
old_base = hp->h_base; /* remember where it started */
hp->h_base += clicks; /* bite a piece off */
hp->h_len -= clicks; /* ditto */
/* If hole is only partly used, reduce size and return. */
if (hp->h_len != 0) return(old_base);
/* The entire hole has been used up. Manipulate free list. */
del_slot(prev_ptr, hp);
return(old_base);
}
prev_ptr = hp;
hp = hp->h_next;
}
return(NO_MEM);
}
/*===========================================================================*
* free_mem *
*===========================================================================*/
PUBLIC void free_mem(base, clicks)
phys_clicks base; /* base address of block to free */
phys_clicks clicks; /* number of clicks to free */
{
/* Return a block of free memory to the hole list. The parameters tell where
* the block starts in physical memory and how big it is. The block is added
* to the hole list. If it is contiguous with an existing hole on either end,
* it is merged with the hole or holes.
*/
register struct hole *hp, *new_ptr, *prev_ptr;
if ( (new_ptr = free_slots) == NIL_HOLE) panic("Hole table full", NO_NUM);
new_ptr->h_base = base;
new_ptr->h_len = clicks;
free_slots = new_ptr->h_next;
hp = hole_head;
/* If this block's address is numerically less than the lowest hole currently
* available, or if no holes are currently available, put this hole on the
* front of the hole list.
*/
if (hp == NIL_HOLE || base <= hp->h_base) {
/* Block to be freed goes on front of the hole list. */
new_ptr->h_next = hp;
hole_head = new_ptr;
merge(new_ptr);
return;
}
/* Block to be returned does not go on front of hole list. */
while (hp != NIL_HOLE && base > hp->h_base) {
prev_ptr = hp;
hp = hp->h_next;
}
/* We found where it goes. Insert block after 'prev_ptr'. */
new_ptr->h_next = prev_ptr->h_next;
prev_ptr->h_next = new_ptr;
merge(prev_ptr); /* sequence is 'prev_ptr', 'new_ptr', 'hp' */
}
/*===========================================================================*
* del_slot *
*===========================================================================*/
PRIVATE void del_slot(prev_ptr, hp)
register struct hole *prev_ptr; /* pointer to hole entry just ahead of 'hp' */
register struct hole *hp; /* pointer to hole entry to be removed */
{
/* Remove an entry from the hole list. This procedure is called when a
* request to allocate memory removes a hole in its entirety, thus reducing
* the numbers of holes in memory, and requiring the elimination of one
* entry in the hole list.
*/
if (hp == hole_head)
hole_head = hp->h_next;
else
prev_ptr->h_next = hp->h_next;
hp->h_next = free_slots;
free_slots = hp;
}
/*===========================================================================*
* merge *
*===========================================================================*/
PRIVATE void merge(hp)
register struct hole *hp; /* ptr to hole to merge with its successors */
{
/* Check for contiguous holes and merge any found. Contiguous holes can occur
* when a block of memory is freed, and it happens to abut another hole on
* either or both ends. The pointer 'hp' points to the first of a series of
* three holes that can potentially all be merged together.
*/
register struct hole *next_ptr;
/* If 'hp' points to the last hole, no merging is possible. If it does not,
* try to absorb its successor into it and free the successor's table entry.
*/
if ( (next_ptr = hp->h_next) == NIL_HOLE) return;
if (hp->h_base + hp->h_len == next_ptr->h_base) {
hp->h_len += next_ptr->h_len; /* first one gets second one's mem */
del_slot(hp, next_ptr);
} else {
hp = next_ptr;
}
/* If 'hp' now points to the last hole, return; otherwise, try to absorb its
* successor into it.
*/
if ( (next_ptr = hp->h_next) == NIL_HOLE) return;
if (hp->h_base + hp->h_len == next_ptr->h_base) {
hp->h_len += next_ptr->h_len;
del_slot(hp, next_ptr);
}
}
/*===========================================================================*
* max_hole *
*===========================================================================*/
PUBLIC phys_clicks max_hole()
{
/* Scan the hole list and return the largest hole. */
register struct hole *hp;
register phys_clicks max;
hp = hole_head;
max = 0;
while (hp != NIL_HOLE) {
if (hp->h_len > max) max = hp->h_len;
hp = hp->h_next;
}
return(max);
}
/*===========================================================================*
* mem_init *
*===========================================================================*/
PUBLIC void mem_init()
{
/* Initialize hole lists. There are two lists: 'hole_head' points to a linked
* list of all the holes (unused memory) in the system; 'free_slots' points to
* a linked list of table entries that are not in use. Initially, the former
* list has one entry for each chunk of physical memory, and the second
* list links together the remaining table slots. As memory becomes more
* fragmented in the course of time (i.e., the initial big holes break up into
* smaller holes), new table slots are needed to represent them. These slots
* are taken from the list headed by 'free_slots'.
*/
register struct hole *hp;
phys_clicks base; /* base address of chunk */
phys_clicks size; /* size of chunk */
/* Put all holes on the free list. */
for (hp = &hole[0]; hp < &hole[NR_HOLES]; hp++) hp->h_next = hp + 1;
hole[NR_HOLES-1].h_next = NIL_HOLE;
hole_head = NIL_HOLE;
free_slots = &hole[0];
/* Allocate a hole for each chunk of physical memory. */
while ( (size = get_mem(&base, FALSE)) != 0)
free_mem(base, size);
}
/*===========================================================================*
* mem_left *
*===========================================================================*/
PUBLIC phys_clicks mem_left()
{
/* Determine how much memory is left. This procedure is called just after
* initialization to find the original amount.
*/
register struct hole *hp;
phys_clicks tot;
for (hp = hole_head, tot = 0; hp != NIL_HOLE; hp = hp->h_next)
tot += hp->h_len;
return(tot);
}