alloc.c

一个简单的操作系统minix的核心代码

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
				src/mm/alloc.c	 	 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

18800	/* This file is concerned with allocating and freeing arbitrary-size blocks of
18801	 * physical memory on behalf of the FORK and EXEC system calls.  The key data
18802	 * structure used is the hole table, which maintains a list of holes in memory.
18803	 * It is kept sorted in order of increasing memory address. The addresses
18804	 * it contains refer to physical memory, starting at absolute address 0
18805	 * (i.e., they are not relative to the start of MM).  During system
18806	 * initialization, that part of memory containing the interrupt vectors,
18807	 * kernel, and MM are "allocated" to mark them as not available and to
18808	 * remove them from the hole list.
18809	 *
18810	 * The entry points into this file are:
18811	 *   alloc_mem: allocate a given sized chunk of memory
18812	 *   free_mem:  release a previously allocated chunk of memory
18813	 *   mem_init:  initialize the tables when MM start up
18814	 *   max_hole:  returns the largest hole currently available
18815	 */
18816	
18817	#include "mm.h"
18818	#include <minix/com.h>
18819	
18820	#define NR_HOLES         128    /* max # entries in hole table */
18821	#define NIL_HOLE (struct hole *) 0
18822	
18823	PRIVATE struct hole {
18824	  phys_clicks h_base;           /* where does the hole begin? */
18825	  phys_clicks h_len;            /* how big is the hole? */
18826	  struct hole *h_next;          /* pointer to next entry on the list */
18827	} hole[NR_HOLES];
18828	
18829	
18830	PRIVATE struct hole *hole_head; /* pointer to first hole */
18831	PRIVATE struct hole *free_slots;        /* ptr to list of unused table slots */
18832	
18833	FORWARD _PROTOTYPE( void del_slot, (struct hole *prev_ptr, struct hole *hp) );
18834	FORWARD _PROTOTYPE( void merge, (struct hole *hp)                           );
18835	
18836	
18837	/*===========================================================================*
18838	 *                              alloc_mem                                    *
18839	 *===========================================================================*/
18840	PUBLIC phys_clicks alloc_mem(clicks)
18841	phys_clicks clicks;             /* amount of memory requested */
18842	{
18843	/* Allocate a block of memory from the free list using first fit. The block
18844	 * consists of a sequence of contiguous bytes, whose length in clicks is
18845	 * given by 'clicks'.  A pointer to the block is returned.  The block is
18846	 * always on a click boundary.  This procedure is called when memory is
18847	 * needed for FORK or EXEC.
18848	 */
18849	
18850	  register struct hole *hp, *prev_ptr;
18851	  phys_clicks old_base;
18852	
18853	  hp = hole_head;
18854	  while (hp != NIL_HOLE) {
18855	        if (hp->h_len >= clicks) {
18856	                /* We found a hole that is big enough.  Use it. */
18857	                old_base = hp->h_base;  /* remember where it started */
18858	                hp->h_base += clicks;   /* bite a piece off */
18859	                hp->h_len -= clicks;    /* ditto */
18860	
18861	                /* If hole is only partly used, reduce size and return. */
18862	                if (hp->h_len != 0) return(old_base);
18863	
18864	                /* The entire hole has been used up.  Manipulate free list. */
18865	                del_slot(prev_ptr, hp);
18866	                return(old_base);
18867	        }
18868	
18869	        prev_ptr = hp;
18870	        hp = hp->h_next;
18871	  }
18872	  return(NO_MEM);
18873	}
	
	
18876	/*===========================================================================*
18877	 *                              free_mem                                     *
18878	 *===========================================================================*/
18879	PUBLIC void free_mem(base, clicks)
18880	phys_clicks base;               /* base address of block to free */
18881	phys_clicks clicks;             /* number of clicks to free */
18882	{
18883	/* Return a block of free memory to the hole list.  The parameters tell where
18884	 * the block starts in physical memory and how big it is.  The block is added
18885	 * to the hole list.  If it is contiguous with an existing hole on either end,
18886	 * it is merged with the hole or holes.
18887	 */
18888	
18889	  register struct hole *hp, *new_ptr, *prev_ptr;
18890	
18891	  if (clicks == 0) return;
18892	  if ( (new_ptr = free_slots) == NIL_HOLE) panic("Hole table full", NO_NUM);
18893	  new_ptr->h_base = base;
18894	  new_ptr->h_len = clicks;
18895	  free_slots = new_ptr->h_next;
18896	  hp = hole_head;
18897	
18898	  /* If this block's address is numerically less than the lowest hole currently
18899	   * available, or if no holes are currently available, put this hole on the
18900	   * front of the hole list.
18901	   */
18902	  if (hp == NIL_HOLE || base <= hp->h_base) {
18903	        /* Block to be freed goes on front of the hole list. */
18904	        new_ptr->h_next = hp;
18905	        hole_head = new_ptr;
18906	        merge(new_ptr);
18907	        return;
18908	  }
18909	
18910	  /* Block to be returned does not go on front of hole list. */
18911	  while (hp != NIL_HOLE && base > hp->h_base) {
18912	        prev_ptr = hp;
18913	        hp = hp->h_next;
18914	  }
18915	
18916	  /* We found where it goes.  Insert block after 'prev_ptr'. */
18917	  new_ptr->h_next = prev_ptr->h_next;
18918	  prev_ptr->h_next = new_ptr;
18919	  merge(prev_ptr);              /* sequence is 'prev_ptr', 'new_ptr', 'hp' */
18920	}
	
	
18923	/*===========================================================================*
18924	 *                              del_slot                                     *
18925	 *===========================================================================*/
18926	PRIVATE void del_slot(prev_ptr, hp)
18927	register struct hole *prev_ptr; /* pointer to hole entry just ahead of 'hp' */
18928	register struct hole *hp;       /* pointer to hole entry to be removed */
18929	{
18930	/* Remove an entry from the hole list.  This procedure is called when a
18931	 * request to allocate memory removes a hole in its entirety, thus reducing
18932	 * the numbers of holes in memory, and requiring the elimination of one
18933	 * entry in the hole list.
18934	 */
18935	
18936	  if (hp == hole_head)
18937	        hole_head = hp->h_next;
18938	  else
18939	        prev_ptr->h_next = hp->h_next;
18940	
18941	  hp->h_next = free_slots;
18942	  free_slots = hp;
18943	}
	
	
18946	/*===========================================================================*
18947	 *                              merge                                        *
18948	 *===========================================================================*/
18949	PRIVATE void merge(hp)
18950	register struct hole *hp;       /* ptr to hole to merge with its successors */
18951	{
18952	/* Check for contiguous holes and merge any found.  Contiguous holes can occur
18953	 * when a block of memory is freed, and it happens to abut another hole on
18954	 * either or both ends.  The pointer 'hp' points to the first of a series of
18955	 * three holes that can potentially all be merged together.
18956	 */
18957	
18958	  register struct hole *next_ptr;
18959	
18960	  /* If 'hp' points to the last hole, no merging is possible.  If it does not,
18961	   * try to absorb its successor into it and free the successor's table entry.
18962	   */
18963	  if ( (next_ptr = hp->h_next) == NIL_HOLE) return;
18964	  if (hp->h_base + hp->h_len == next_ptr->h_base) {
18965	        hp->h_len += next_ptr->h_len;   /* first one gets second one's mem */
18966	        del_slot(hp, next_ptr);
18967	  } else {
18968	        hp = next_ptr;
18969	  }
18970	
18971	  /* If 'hp' now points to the last hole, return; otherwise, try to absorb its
18972	   * successor into it.
18973	   */
18974	  if ( (next_ptr = hp->h_next) == NIL_HOLE) return;
18975	  if (hp->h_base + hp->h_len == next_ptr->h_base) {
18976	        hp->h_len += next_ptr->h_len;
18977	        del_slot(hp, next_ptr);
18978	  }
18979	}
	
	
18982	/*===========================================================================*
18983	 *                              max_hole                                     *
18984	 *===========================================================================*/
18985	PUBLIC phys_clicks max_hole()
18986	{
18987	/* Scan the hole list and return the largest hole. */
18988	
18989	  register struct hole *hp;
18990	  register phys_clicks max;
18991	
18992	  hp = hole_head;
18993	  max = 0;
18994	  while (hp != NIL_HOLE) {
18995	        if (hp->h_len > max) max = hp->h_len;
18996	        hp = hp->h_next;
18997	  }
18998	  return(max);
18999	}
	
	
19002	/*===========================================================================*
19003	 *                              mem_init                                     *
19004	 *===========================================================================*/
19005	PUBLIC void mem_init(total, free)
19006	phys_clicks *total, *free;              /* memory size summaries */
19007	{
19008	/* Initialize hole lists.  There are two lists: 'hole_head' points to a linked
19009	 * list of all the holes (unused memory) in the system; 'free_slots' points to
19010	 * a linked list of table entries that are not in use.  Initially, the former
19011	 * list has one entry for each chunk of physical memory, and the second
19012	 * list links together the remaining table slots.  As memory becomes more
19013	 * fragmented in the course of time (i.e., the initial big holes break up into
19014	 * smaller holes), new table slots are needed to represent them.  These slots
19015	 * are taken from the list headed by 'free_slots'.
19016	 */
19017	
19018	  register struct hole *hp;
19019	  phys_clicks base;             /* base address of chunk */
19020	  phys_clicks size;             /* size of chunk */
19021	  message mess;
19022	
19023	  /* Put all holes on the free list. */
19024	  for (hp = &hole[0]; hp < &hole[NR_HOLES]; hp++) hp->h_next = hp + 1;
19025	  hole[NR_HOLES-1].h_next = NIL_HOLE;
19026	  hole_head = NIL_HOLE;
19027	  free_slots = &hole[0];
19028	
19029	  /* Ask the kernel for chunks of physical memory and allocate a hole for
19030	   * each of them.  The SYS_MEM call responds with the base and size of the
19031	   * next chunk and the total amount of memory.
19032	   */
19033	  *free = 0;
19034	  for (;;) {
19035	        mess.m_type = SYS_MEM;
19036	        if (sendrec(SYSTASK, &mess) != OK) panic("bad SYS_MEM?", NO_NUM);
19037	        base = mess.m1_i1;
19038	        size = mess.m1_i2;
19039	        if (size == 0) break;           /* no more? */
19040	
19041	        free_mem(base, size);
19042	        *total = mess.m1_i3;
19043	        *free += size;
19044	  }
19045	}