Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Sistemas Operativos/Trabajo final/alloc original

De Wikilibros, la colección de libros de texto de contenido libre.
/* Este archivo tiene que ver con la alocación y liberación de bloques memoria física de
 * tamaño arbitrario en favor de las llamadas al sistema FORK y EXEC. La principal estructura
 * de datos utilizada es la tabla de huecos, que mantiene una lista de los huecos en la memoria.
 * Se mantiene ordenada en orden creciente de dirección de memoria.
 * Las direcciones que contiene se refieren a memoria física, empezando en la dirección
 * absoluta 0 (es decir que no son relativas al comienzo del MM). Durante la inicialización
 * del sistema, las partes de la memoria que contiene el vector de interrupciones, kernel y MM
 * son "alocadas" para ser marcadas como no disponibles y ser removidas de la lista de huecos.
 *
 * Los puntos de entrada a este archivo son:
 *   alloc_mem: aloca un sector de memoria de un tamaño dado.
 *   free_mem: libera un sector de memoria previamente alocado.
 *   mem_init: inicializa las tablas cuando el MM se inicia.
 *   max_hole: retorno el hueco más grande actualmente disponible.
 */
#include "mm.h"
#include <minix/com.h>

#define NR_HOLES         128 /* máximo número de entradas en la tabla de huecos */
#define NIL_HOLE (struct hole *) 0

PRIVATE struct hole {
  phys_clicks h_base;  /* comienzo del hueco */
  phys_clicks h_len;   /* tamaño del hueco */
  struct hole *h_next; /* puntero a la siguiente entrada de la lista */
} hole[NR_HOLES];

PRIVATE struct hole *hole_head;  /* puntero al primer hueco */
PRIVATE struct hole *free_slots; /* puntero a la lista de ranuras de la tabla no usadas */

FORWARD _PROTOTYPE( void del_slot, (struct hole *prev_ptr, struct hole *hp) );
FORWARD _PROTOTYPE( void merge, (struct hole *hp)       );
/*===========================================================================*
 *                                 alloc_mem                                 *
 *===========================================================================*/
PUBLIC phys_clicks alloc_mem(clicks)
phys_clicks clicks;  /* cantidad de memoria solicitada */
{
/* Aloca un bloque de memoria de la lista de bloques libres, usando la técnica
 * del "primero en ajustar". El bloque consiste en bytes contiguos, cuyo tamaño
 * en clicks está dado por 'clicks'. Se devuelve un puntero al bloque. El bloque
 * siempre está en el borde de un click. Este procedimiento se llama cuando FORK
 * o EXEC necesitan memoria.
 *
 * El algoritmo del "primero en ajustar" deberá ser reemplazado por el del sistema
 * compañero, para lo cual ya no será necesaria la lista de huecos, y podrá ser
 * reemplazada por una estructura del tipo heap, que representará a un árbol que
 * a su vez representará a cada uno de los bloques factibles de ser particionados,
 * comenzando por el bloque mayor, cuyos hijos serán los bloquen en los cuales éste
 * se particiona.
 * Un 0 en la posición correspondiente significará que el bloque está disponible.
 * Un 1 significará que el bloque está ocupado, o que una de sus particiones lo
 * está, lo que en ambos casos significa que el bloque no está disponible.
 * Un recorrido secuencial de esta estructura permite encontrar el primer bloque
 * libre que mejor ajuste a la cantidad de memoria solicitada.
 * Una liberación es una operación muy simple, ya que solo requiere verificar
 * el estado del bloque hermano, y, en caso de realizarse una fusión, se continuará
 * iterativamente hasta que no haya fusión posible.
 */

  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 (clicks == 0) return;
  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(total, free)
phys_clicks *total, *free;  /* memory size summaries */
{
/* 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 */
  message mess;

  /* 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];

  /* Ask the kernel for chunks of physical memory and allocate a hole for
   * each of them.  The SYS_MEM call responds with the base and size of the
   * next chunk and the total amount of memory.
   *
   * Se le piden al kernel los trozos de memoria. Una vez obtenidos,
   * debería tomarse el bloque completo más grande,
   * y ésta será nuestra área de memoria contigua a alocar.
   * Otra opción es asegurarse de que el kernel devuelva un gran sector
   * de memoria contigua.
   */
  *free = 0;
  for (;;)
  {
    mess.m_type = SYS_MEM;
    if (sendrec(SYSTASK, &mess) != OK) panic("bad SYS_MEM?", NO_NUM);
    base = mess.m1_i1;
    size = mess.m1_i2;
    if (size == 0) break;  /* no more? */

    free_mem(base, size);
    *total = mess.m1_i3;
    *free += size;
  }
}