bank.c

C++ 编写的EROS RTOS

/*
 * Copyright (C) 1998, 1999, 2001, Jonathan Adams.
 *
 * 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.
 */


#include <eros/target.h>
#include <eros/Invoke.h>
#include <eros/Key.h>
#include <eros/RangeKey.h>
#include <eros/NodeKey.h>
#include <eros/NumberKey.h>
#include <eros/ProcessKey.h>
#include <eros/StdKeyType.h>
#include <domain/domdbg.h>
#include <domain/SpaceBankKey.h>
#include <domain/Runtime.h>

#include <string.h>

#include "misc.h"
#include "assert.h"
#include "spacebank.h"
#include "Bank.h"
#include "ObjSpace.h"
#include "malloc.h"
#include "debug.h"

Bank bank0;
Bank primebank;
Bank verifybank;

/* The keys given out to everyone before the spacebank starts
   running are readonly red segment key with a "bank address"
   of zero and a start key to the spacebank as the keeper.  A node
   key to the each of the premade red segments are passed in on
   startup.
   
   **DANGER** WILL ROBINSON: Every preallocated node MUST have
   the BANKPREC_NO_DELETE property, since either:
   
   A:  It is the primebank and therefore can never to deleted
   or
   B:  The preallocated segment is marked as allocated from the
      primebank, so trying to remove its key from the alloctree
      fails. */

struct premade_node_info {
  uint8_t keyReg;        /* Keyreg of preallocated node
		       *  -- KR_VOID indicates end of list
		       */
  Bank *bank;         /* Pointer to bank the preallocated node should
		       * point to.
		       */
  BankPrecludes limits;  /* Limits this key should have */
};

/* THIS MUST MATCH primebank.map!!! */
static struct premade_node_info premade_keys[] =
{
  {KR_PRIMEBANK, &primebank,BANKPREC_NO_DESTROY|
                       BANKPREC_NO_LIMITMODS},
  {KR_VERIFIER, &verifybank,BANKPREC_NO_DESTROY|
                        BANKPREC_NO_LIMITMODS},
  /* end marker */
  {KR_VOID, NULL, 0u}
};

static Bank* alloc_bank(void);
static void free_bank(Bank *);

static uint32_t
bank_deallocOID(Bank *bank, uint8_t type, OID oid);
/* bank_deallocOID:
 *     Returns the object described by /oid/ with type /type/ to the
 *     available object pool.
 */

static uint32_t
bank_containsOID(Bank *bank, uint8_t type, OID oid);

void
bank_initializeBank(Bank *bank,
		    Bank *parent,
		    uint64_t limit);
/* bank_initializeBank:
 *     Initializes /bank/ to be an empty bank with parent /parent/ and
 *   initial allocation limit /limit/.
 *
 *     Always succeeds.
 */

struct Bank_MOFrame *
bank_getTypeFrame(Bank *bank, uint8_t type);
/*    If /type/ is a multiple-object-per-frame type, returns the
 *  address of /bank/'s frameMap and frameOid cache for that type
 *  in *(/frameMap/) and *(/frameOid/), respectively.
 *    If /type/ is a single-object-per-frame type, returns NULL in
 *  both *(/frameMap/) and *(/frameOid/).
 *
 *    kpanics if the type is not recognized.
 *
 *    Implemented as a macro for speed.
 */
#define bank_getTypeFrame(bank, type) \
   (((type) == OT_Node)? (&(bank)->nodeFrame) \
      : (struct Bank_MOFrame *)NULL)

static uint32_t
bank_initKeyNode(uint32_t krNode, Bank *bank, BankPrecludes limits);
/* bank_initKeyNode:
 *     Takes the node /krNode/ and sets it up as a key to /bank/ with
 *   the restrictions outlined in /limits/.
 *
 *     If /krNode/ is already being used as a the node for a red
 *   segment key to a bank, bank_initKeyNode makes sure it remains
 *   valid while being changed.
 *
 *     Returns RC_OK on success, other on failure.
 */
     
static uint32_t
bank_initKeyNode(uint32_t krNode, Bank *bank, BankPrecludes limits)
{
  struct nk_value_s myKeyval;
  uint32_t retval;

  assert(limits < BANKPREC_NUM_PRECLUDES); /* make sure limits is valid */
  

#ifdef KT_Wrapper
  myKeyval.value[0] = WRAPPER_KEEPER | WRAPPER_SEND_WORD;
  myKeyval.value[1] = (uint32_t)bank;     /* pointer to /bank/ */
  myKeyval.value[2] = 0;

  /* new node is in /kr/. fill it with the information */
  retval = node_write_number(krNode, WrapperFormat, &myKeyval);

  assert ( "writing format number into node" && retval == RC_OK );

  /* use my domain key to make a start key with keyInfo /limits/ */
  retval = process_make_start_key(KR_SELF, limits, KR_TMP);
  assert ( "making start key" && retval == RC_OK );

  retval = node_swap(krNode, WrapperKeeper, KR_TMP, KR_VOID);
  assert ( "swapping start key into node" && retval == RC_OK );
#else
  myKeyval.value[0] = 0;

  REDSEG_SET_INITIAL_SLOTS(myKeyval, 0);
  REDSEG_SET_KPR_SLOT(myKeyval, RedSegKeeper);
  REDSEG_SET_BG_SLOT(myKeyval, RedSegFormat); /* none */
  REDSEG_SET_SENDNODE(myKeyval, REDSEG_SEND_UNALTERED);
  /* Any valid BLSS will do, since there are no initial slots. */
  REDSEG_SET_BLSS(myKeyval, EROS_PAGE_BLSS+1);
  myKeyval.value[1] = (uint32_t)bank;     /* pointer to /bank/ */
  myKeyval.value[2] = 0;

  /* new node is in /kr/. fill it with the information */
  retval = node_write_number(krNode, RedSegFormat, &myKeyval);

  assert ( "writing format number into node" && retval == RC_OK );

  /* use my domain key to make a start key with keyInfo /limits/ */
  retval = process_make_start_key(KR_SELF, limits, KR_TMP);
  assert ( "making start key" && retval == RC_OK );

  retval = node_swap(krNode, RedSegKeeper, KR_TMP, KR_VOID);
  assert ( "swapping start key into node" && retval == RC_OK );
#endif

  return RC_OK;
}

void
bank_initializeBank(Bank *bank,
		    Bank *parent,
		    uint64_t limit)
{
  uint32_t i;
#ifdef PARANOID
  if (parent == NULL && bank != &bank0) {
    kpanic(KR_OSTREAM,
	   "Spacebank: bank_initializeBank: attempt to initialize a "
	   "bank with no parent!\n");
  }
#endif
  
  bank->parent = parent;
  if (parent) {
    bank->nextSibling = parent->firstChild;
    parent->firstChild = bank;
  } else {
    bank->nextSibling = NULL;
  }

  bank->limit = limit;
  bank->allocCount = 0;

  for (i = 0; i < BANKPREC_NUM_PRECLUDES; i++)
    bank->exists[i] = false;
  
  allocTree_Init(&bank->allocTree);
  bank->nodeFrame.frameMap = 0u;
  bank->nodeFrame.frameOid = 0ull;
  
  for (i = 0; i < OT_NUM_TYPES; i++) {
    bank->allocs[i]   = 0u;
    bank->deallocs[i] = 0u;
  }
  return;
}
			 
void
bank_init(void)
{
  struct premade_node_info *curInfo;

  /* first, initialize the precreated banks */
  bank_initializeBank(&bank0,      /* bank0 */
		      NULL,        /* bank0 has no parent */
		      0);          /* bank0 starts with a 0 limit */
    

  bank_initializeBank(&primebank,   /* primebank */
		      &bank0,	    /* primebank's parent is bank0 */
		      UINT64_MAX);  /* primebank is not limited */
    
  bank_initializeBank(&verifybank, /* verifybank */
		      &primebank,  /* verifybank's parent is primebank */
		      0);          /* verifybank cannot be allocated
				      from. */

  /* See the comment by the premade_keys stuff for info on premade 
     keys.  We need to identify the oid of each of the premade key's
     associated node and store it in the premade keys's associated
     bank's limitedKey array.  We then need to update the node to
     hold the correct Bank  address and permissions using
     bank_initKeyNode. */


  for (curInfo = premade_keys;
         curInfo->keyReg != KR_VOID;
           curInfo++) {
    
    uint64_t offset;
    uint32_t obType;
    uint32_t result;
    
    /* identify the node and shove it's OID into the bank's
       limitedKey array. */
    result = range_identify(KR_SRANGE,
			    curInfo->keyReg,
			    &obType,
			    &offset);
    
    if (result != RC_OK) {
      kpanic(KR_OSTREAM,
	     "Spacebank: Hey! error identifying preall node in slot "
	     "%u! (0x%08x)\n",
	     curInfo->keyReg,
	     result);
    }
    if (obType != OT_Node) {
      kpanic(KR_OSTREAM,
	     "Spacebank: Hey! preall key in slot %u is not a node! "
	     "(is 0x%08x)\n",
	     curInfo->keyReg,
	     obType);
    }
    
    /* put it in as the correct limited key */
    curInfo->bank->limitedKey[curInfo->limits] = offset;
    curInfo->bank->exists[curInfo->limits] = true;
    
    /* now init the node correctly */
    result = bank_initKeyNode(curInfo->keyReg,
			      curInfo->bank,
			      curInfo->limits);
    
    if (result != RC_OK) {
      kpanic(KR_OSTREAM,
	     "Spacebank: Hey! bank_initKeyNode failed for the preall "
	     "key in slot %u! (0x%08x)\n",
	     curInfo->keyReg,
	     result);
    }
    
    /* The limitedkeys are included in the primebank's preallocated
       storage */
  }
}

uint32_t
bank_ReserveFrames(Bank *bank, uint32_t count)
{
  Bank *curBank = bank;

  DEBUG(limit)
    kprintf(KR_OSTREAM,
	    "SpaceBank: bank_ReserveFrame reserve %d frames for bank 0x%08x\n",
	    count,
	    bank);
  /* Loop up through bank0 (which has a NULL parent), adding
   * /count/ from the bank's allocCount if that doesn't go over limit.
   *
   * If we will go over the limit, we have to go back and undo all the
   * additions we did.
   */
  for (curBank = bank; curBank != NULL; curBank = curBank->parent) {
    DEBUG(limit)
      kprintf(KR_OSTREAM,
	      "SpaceBank: bank 0x%08x "
	      "limit=0x%08x%08x allocCount=0x%08x%08x\n",
	      bank,
	      DW_HEX_ARG(curBank->allocCount),
	      DW_HEX_ARG(curBank->limit));
    
    if (curBank->allocCount + count > curBank->limit)
      break;
    curBank->allocCount += count;
  }

  if (curBank != NULL) {
    DEBUG(limit)
      kdprintf(KR_OSTREAM,
               "SpaceBank: failed to reserve objects\n");
    
    /* we didn't make it to NULL -- loop bank up to curBank,
       unreserving as we go*/
    for ( ; bank != curBank; bank = bank->parent) {
      bank->allocCount -= count;
    }
    /* return failure */
    return RC_SB_LimitReached;
  }
  return RC_OK;
}

void
bank_UnreserveFrames(Bank *bank, uint32_t count)
{
  Bank *curBank;

  DEBUG(limit)
    kprintf(KR_OSTREAM,
	    "SpaceBank: bank_UnreserveFrames unreserving %d frames "
	    "from bank 0x%08x\n",count, bank);

  for (curBank = bank; curBank != NULL; curBank = curBank->parent) {
    DEBUG(limit)
      kprintf(KR_OSTREAM,
              "SpaceBank: bank %08x limit=0x"DW_HEX" "
              "allocCount=0x"DW_HEX"\n",
              curBank,
              DW_HEX_ARG(curBank->limit),
              DW_HEX_ARG(curBank->allocCount));
#ifdef PARANOID
    if (curBank->allocCount < (uint64_t)count)
      kpanic(KR_OSTREAM,
             "SpaceBank: Unreserving made allocCount < 0!\n");
#endif
    curBank->allocCount -= (uint64_t)count;
  }
}

uint32_t
BankSetLimits(Bank *bank, const struct bank_limits *newLimits)
{
  bank->limit = newLimits->frameLimit;
  return RC_OK;
}

uint32_t
BankGetLimits(Bank *bank, /*OUT*/ struct bank_limits *getLimits)
{
  uint64_t effFrameLimit = UINT64_MAX;
  uint64_t effAllocLimit = UINT64_MAX;

  getLimits->frameLimit = bank->limit;
  getLimits->allocCount = bank->allocCount;

  for ( ; bank != NULL; bank = bank->parent) {
    if (bank->limit < effFrameLimit) {
      effFrameLimit = bank->limit;
    }

    if (bank->limit < bank->allocCount) {
      effAllocLimit = 0u;
    } else if (bank->limit - bank->allocCount < effAllocLimit) {
      effAllocLimit = bank->limit - bank->allocCount;
    }
  }
  getLimits->effFrameLimit = effFrameLimit;
  getLimits->effAllocLimit = effAllocLimit;

  {
    int i;
    for (i = 0; i < OT_NUM_TYPES; i++) {
      getLimits->allocs[i]   = bank->allocs[i];
      getLimits->reclaims[i] = bank->deallocs[i];
    }
  }

  return RC_OK;
}

uint32_t
BankCreateKey(Bank *bank, BankPrecludes limits, uint32_t kr)
{
  uint32_t retval = RC_OK;

  assert(limits < BANKPREC_NUM_PRECLUDES);
  
  if (bank->exists[limits]) {
    /* we've already fab.ed the node, just make a new red segment key */
    
    retval = range_getobjectkey(KR_SRANGE,
				OT_Node,
				bank->limitedKey[limits],
				kr);

    if (retval != RC_OK) return retval;
  }
  else {
    OID oid;
    /* Fabricate a new node. */

    retval = BankAllocObjects(bank, OT_Node, 1u, kr);

    if (retval != RC_OK)
      return retval;

    retval = range_identify(KR_SRANGE, kr, NULL, &oid);

    assert( "range_identifying alloced node" && retval == RC_OK );
    
    retval = bank_initKeyNode(kr, bank, limits);
    assert( "calling bank_initKeyNode on alloced node" && retval == RC_OK );

    bank->exists[limits] = true;
    bank->limitedKey[limits] = oid;
  }
  
  /* now we have everything set up -- make the segment key */
    
#ifdef KT_Wrapper
  /* FIX: This is wrong -- what about permissions? */
  retval = node_make_wrapper_key(kr, 0, kr);
#else
  retval = node_make_segment_key(kr, RedSegBLSS, kr);
#endif

  assert( retval == RC_OK );

  return RC_OK;    

#if 0
cleanup:
  {
    uint32_t retval2 = BankDeallocObjects(bank, OT_Node, 1, kr);

    if (retval2 != RC_OK) {
      kpanic(KR_OSTREAM,
	     "SpaceBank: BankCreateKey failed to deallocate failed "
	     "node from failed bank_initKeyNode.\n");	     
    }
  }
  /* return why the initKeyNode failed. */
  return retval;
#endif  
}

uint32_t
BankCreateChild(Bank *parent, uint32_t kr)
{
  Bank *newBank = alloc_bank();
  uint32_t retval;
  
  if (!newBank) return RC_SB_LimitReached;

  bank_initializeBank(newBank,     /* newBank */
		      parent,      /* newBank's parent is /parent/ */
		      UINT64_MAX); /* newBank starts out unlimited */

  retval = BankCreateKey(newBank, 0u /* no limits */, kr);

  if (retval != RC_OK) {
    /* Couldn't create the key -- gotta return the child */
    assert ( parent->firstChild == newBank );

    /* unlink the child */
    parent->firstChild = newBank->nextSibling;
    
    free_bank(newBank);
  }      
  return retval;
}

static void
FlushBankCache(Bank * bank)
{
  /* move the node/proc cache into the b-tree */
  if (bank->nodeFrame.frameMap) {
    int idx;

    /* deallocate any unused items */
    for (idx = 0; idx < objects_per_frame[OT_Node]; idx++) {
      if (bank->nodeFrame.frameMap & (1 << idx)) {
	allocTree_removeOID(&bank->allocTree,
			    bank,
			    OT_Node,
			    bank->nodeFrame.frameOid | idx);
      }
    }
    bank->nodeFrame.frameOid = 0llu;
    bank->nodeFrame.frameMap = 0u;
  }
}

static void
DestroyStorage(Bank * bank)
{
  /* blow it all away */
  OID curFrame;

  /* use the incrementalDestroy to remove one frame at a time from
   * the tree
       */
  while (allocTree_IncrementalDestroy(&bank->allocTree,
				      &curFrame)) {
    uint32_t retVal;
    
    /* BIG UGLY HACK!
     *
     * This code takes advantage of the fact that if you ask for a key
     * of a different type than is in the frame, all of the objects in
     * the frame are rescinded.
     *
     * So by creating a key to the page for this frame, then
     * rescinding it, the code guarentees that no matter what the
     * frame was filled with, all of the objects in the frame are
     * rescinded. */

    DEBUG(children)
      kprintf(KR_OSTREAM,
	      "DestroyStorage: Destroying frame 0x"DW_HEX"\n",
	      DW_HEX_ARG(curFrame));

    retVal = range_getobjectkey(KR_SRANGE,OT_DataPage,curFrame,KR_TMP);
    if (retVal != RC_OK) {
      kdprintf(KR_OSTREAM,
	       "DestroyStorage: Error getting page key to "
	       "0x"DW_HEX"\n",
	       DW_HEX_ARG(curFrame));
    }
    
    retVal = range_rescind(KR_SRANGE, KR_TMP);
    if (retVal != RC_OK) {
      kdprintf(KR_OSTREAM,
	       "DestroyStorage: Error rescinding page key to "
	       "0x"DW_HEX"\n",
	       DW_HEX_ARG(curFrame));
    }

    /* unreserve the frame */
    bank_UnreserveFrames(bank, 1u);
    /* now mark it free in the object space */

    /* SHAP: this is correct, but inefficient -- the objects properly
       ought to go back according to frame type, but the following
       will suffice until I have time to figure out what to do about
       that. */
    ob_ReleasePageFrame(bank,curFrame);
  }