swaparea.hxx

C++ 编写的EROS RTOS

#ifndef __SWAPAREA_HXX__
#define __SWAPAREA_HXX__
/*
 * Copyright (C) 1998, 1999, Jonathan S. Shapiro.
 *
 * This file is part of the EROS Operating System.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2,
 * or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */


/* A SwapArea is made up of some number of Swap Divisions.  Pages are
 * allocated in a SwapArea until the area is full, and then we
 * checkpoint.
 * 
 * Now what, exactly, full means is an interesting problem.  There are
 * three policies we might imagine:
 * 
 * 1. Paranoid.  Goal is to guarantee that every page in a swap area
 *    resides on two distinct disk drives.  Yes, I meant drives, not
 *    divisions.  Idea is to protect yourself from failure of a single
 *    drive.  This may mean being unable to use all of the
 *    theoretically available space in a swap area.
 * 
 * 2. Duplexed.  Goal is to guarantee that every page ends up in two
 *    swap areas, but it is okay for those areas to be on the same
 *    physical disk.  You are trying to protect agains sector dropout,
 *    but you trust your drives.
 * 
 * 3. Max utilization.  Just use all the space, forget about
 *    duplexing.
 * 
 * Note that 3 is the only choice possible if there is only one swap
 * division.
 * 
 * Given that you are duplexing and you trust your drives 2 is very
 * much better than 1, because of the bin packing problem described
 * below.
 * 
 * The EROS Swap Area logic implements all three policies.  It goes
 * for paranoid allocation first.  When it is unable to allocate swap
 * space in a paranoid fashion it falls back on duplexed.  If it has
 * only a single swap division it will go for Max utilization.  The
 * max utilization must be present for the system to work in the
 * absence of multiple swap divisions.  The duplexed strategy code can
 * be disabled.
 */


/* Now about the bin packing problem.  Consider a system with three
 * swap divisions on three drives.   Area A has 5 pages, Area B has 3
 * pages, and Area C has 2 pages.  Clearly we should be able to save 5
 * pages even under the paranoid strategy.  Suppose we write the pages
 * out as follows:
 * 
 * 	Page 1	to	A, B
 * 	Page 2	to	B, C
 * 	Page 3	to	C, A
 * 	Page 4	to	A, B
 * 
 * Note that we are unable to write a paranoid page 5.  To avoid this
 * problem, EROS uses the following policy to select pairs:
 * 
 * PARANOID PHASE:
 * 
 * We first select two swap divisions. swap division one is that swap
 * division with the greatest number of available pages.  Swap division
 * two is that swap division such that
 * 
 * 	1. It is on a distinct physical drive from the first swap
 * 	   division.
 * 	2. It is the smallest such swap division.  I.e. the swap
 *         division with the smallest number of available pages.
 * 
 * We write pages to this pair until we run off the end of either
 * division.  If we ran off the end of division two, we select a new
 * division two according the the same rules.  If we run off the end
 * of division one, we select a new division one such that it is the
 * most empty swap area on any disk and then select a new division two
 * according to the same division two rules. 
 * 
 * DUPLEXED PHASE
 * 
 * Same rules, except we remove the restriction about them being
 * different drives.
 * 
 * The net effect is to first maximize the number of paranoid pages
 * and then maximize the number of duplexed pages. If you have more
 * than one division in a swap area we simply will not write a page in
 * less than two places.  You want to run stupidly use a single swap
 * division.  Actually, we do so ourselves for the boot disk.
 */


/* need this for definition of DirEnt and DirEntPage... */
#include "CheckPoint.hxx"

class CoreDivision;
class CoreObject;

/* The SwapLoc map is a tree-structured table of SwapLocMappings: */
struct SwapLocMapping {
  struct LocFrame {
    uint16_t  divNdx;		/* index into Persist division table */
    uint16_t  divFrame;		/* page frame */
  } where[2];
};

#define SWAPLOC_MAPPINGS_PER_PAGE (EROS_PAGE_SIZE / sizeof(SwapLocMapping))

#define SWAP_DIR_HASH 43
#define NUM_SLM_ROOT 1024
#define MAX_SWAPLOC NUM_SLM_ROOT * SWAPLOC_MAPPINGS_PER_PAGE

class SwapArea {
  enum {
    Dirty,			/* in use as current paging area */
    Migrating,			/* currently being migrated. */
    Available,
  } status;
  
  CoreDivision* divOne;		/* division pointer for 1st swap division */
  CoreDivision* divTwo;		/* division pointer for 2nd swap division */
  
  DirEntPage* dirPageChain;	/* list of in-core directory pages. */
  int curDirEntNdx;		/* number of entries in current */
				/* directory page */
  
  DirEnt* dirPtr[SWAP_DIR_HASH];


  SwapLocMapping* slmRoots[NUM_SLM_ROOT];
  
  uint32_t availNodeEnt;		/* number of nodes available in the */
				/* current node pot before we need to
				 * allocate another one.
				 */
  
  uint32_t availDirEnt;		/* number of directory entries */
				/* available before  we need to allocate
				 * a new directory page.
				 */

  uint32_t areaIndex;		/* swap area 0 or swap area 1 */
  
  SwapLoc  nextLoc;		/* next swaploc we will write to. */
  SwapLoc  topLoc;		/* top loc that we know to be */
				/* available */

  int findSwapDivisions();
  
  int allocSwapDirent();
  int allocSwapFrame();

      /* return the SwapLocMapping structure associated with a
       * particular page:
       */
  SwapLocMapping* findPage(CDA cda);

      /* return the SwapLocMapping structure associated with the Node
       * Pot for a particular Node:
       */
  SwapLocMapping* findNode(CDA cda);
  
public:

  void reset();			/* reset the swap area */

      /* return 1 if we can mutate another node without running of the
       * end of the swap area.  Call this only the first time that you
       * mutate a node.
       */

      /* Node mutates are append only - the second write of a node
       * will end up in a different node pot than the first - so we
       * do not care what the CDA is.
       */
  int canMutateNode();

      /* return 1 if we can fit another page into this swap area.  If
       * so, allocate the relevant entries
       */

      /* If the CDA has already been given a SwapLoc, we will rewrite
       * to that SwapLoc, so we need to know...
       */
  
  int canMutatePage(CDA cda);
  
      /* cause a page to be written to the swap area.  As a side
       * effect, marks the CoreObject !dirty.  May return 0 (fail) if
       * DiskIoReq structures were unavailable.
       */
  int swapPageOut(CoreObject* co);

      /* cause a node pot to be written to the swap area.  As a side
       * effect marks all contained Nodes !dirty.  May return 0 (fail)
       * if DiskIoReq structures were unavailable.
       */
  int swapNodePot(CoreObject* co);
  
#if 0
      /* return 1 if it is possible to get another directory entry: */
  int allocDirEnt();
#endif

  SwapArea(uint32_t idx);
};

#endif /* __SWAPAREA_HXX__ */