Minix Memory Allocation

RAM is managed in the alloc.c file of the Minix operating system.  In Minix memory is allocated in units called phys_clicks.  On Intel based systems, a click is equal to 256 bytes.  The size of a click in unimportant to the memory allocation functions since everything is done in units of phys_clicks.

The default implementation of alloc.c uses the First Fit algorithm.  A linked list is used to keep track of the available memory slots.  The items in the linked lists are structures called a hole.

struct hole {
  phys_clicks h_base;   /* address of the beginning of the available memory area in RAM */
  phys_clicks h_len;    /* size of the available memory area */
  struct hole *h_next;  /* pointer to next hole entry on the list */

} hole[NR_HOLES];

The linked list entries are kept in the array hole.  In a user level program, you would probably dynamically acquire linked list entries using the new command.  The memory manager of the operating system could get caught in a recursive loop if it used dynamic memory objects.  When an entire available slot is allocated, the hole data structure needs to be removed from the available slot linked list.  The internal function del_slot is used to do this.  When RAM is released, new entries are created in the available slot linked list.  If two available memory areas are adjacent in RAM, the memory manager should merge the two free areas together into one large free area.  The internal function merge does this.

There are four public functions that you must implement in alloc.c

void mem_init(phys_clicks *total, phys_clicks *free);

This function is called once during the boot process to initialize the memory management system.  The two parameters to this function are not used.  The function sends a message to another part of Minix to get the size of available RAM.  Several messages are sent to get all of the available RAM which may not be contiguous.

phys_clicks alloc_mem(phys_clicks clicks);

This is the basic memory allocation function.  This is called by other parts of Minix to acquire memory space.  The parameter specifies how much memory is required.  The function returns the address of the beginning of the memory area the caller is to use.  The function returns the value NO_MEM if the request cannot be satisfied.

void free_mem(phys_clicks base, phys_clicks clicks);

This function is called to release memory previously acquired by a call to alloc_mem.  The parameters specify the beginning address of the area to be released and the size of that memory area.

phys_clicks max_hole();

This function returns the size of the largest contiguous memory area currently available.

void del_slot(struct hole *prev_ptr, struct hole *hp);

This internal function removes the hole data structure pointed to by hp.  The pointer prev_ptr must point to the item in the linked list just before the item to be removed.  The h_next pointer of prev_ptr should be equal to hp.

void merge(struct hole *hp);

This internal  function checks if the hole data structure pointed to by hp can be merged with the following holes.