keyset.c

C++ 编写的EROS RTOS

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

/* Keyset object

   Holds a logical "set" of keys.  This set supports the operations:

   Adding a key to the set
   Removing a key from the set
   Checking if a key is in the set
   Emptying the set
   **Count of number of items in the set?
   **Merging the keys from another set? -- this would seem to require
                                           some way of authorizing
					   the transfer.
   
   Note that there is *NO* way to get back a key after adding it to
   the set.  You have to keep a copy of it.

   For efficiency, keys are *not* actually even held by the keyset.
   Their keybits are stored in a balanced tree for rapid searching.

   For now, keyset is mainly an *internal* object, as there are
   problems with the way it stores the keys. ( it is possible to
   create and object, rescind it, then create another object, and test
   that the new object is in the keyset.  This is bad. )
   
   **longer note on dangers / what happens if a key is rescinded?
 
   ** Add a "readonly" key?
  
   NEED MORE DESCRIPTION */

#include <eros/target.h>
#include <eros/Invoke.h>
#include <domain/Runtime.h>
#include <eros/Key.h>
#include <eros/ProcessKey.h>
#include <eros/DiscrimKey.h>
#include <eros/NodeKey.h>
#include <eros/KeyBitsKey.h>
#include <eros/StdKeyType.h>
#include <eros/SegmentKey.h>
#include <domain/SpaceBankKey.h>
#include <domain/ProtoSpace.h>
#include <domain/ConstructorKey.h>
#include <domain/ProcessCreatorKey.h>
#include <domain/KeySetKey.h>
#include <domain/Runtime.h>

#include <domain/domdbg.h>

#include "keyset.h"
#include "constituents.h"

#define Normal_KeyData     (0u)
#define ReadOnly_KeyData   (1u)
#define GetSegment_KeyData (0xFACEu)

#define RC_Internal_KeyToSelf  (0xFACEu)

#define OC_KeySet_Internal_GetSegment (0xFEEDFACEu)

/* NOTE:
 *   The "Internal" protocol goes like this:
 * 1 Someone requests that this keyset do some operation with another
 *  keyset.  They have passed in the key to the other set.
 *
 * 2 The called keyset checks the passed in key with its domain creator
 *  to make sure that it is a valid key to a keyset.
 *
 * 3 This keyset makes a start key with a distinguished KeyData field,
 *  to validate itself to the other keyset.  It then CALLs the other
 *  keyset, using a distinguished request code, and passing in the
 *  distinguished start key.  The first keyset is now Waiting for the
 *  other keyset's response.
 *
 * 4 The other keyset now has control.  It recognizes the request code,
 *  and uses its domain creator to validate the key's authenticity and
 *  KeyData. Note that from now forward, the second keyset is *NOT*
 *  Available, and any requests to it will block.
 *
 * 5 Having validated the first keyset, the second now CALLs the resume
 *  key to the first keyset, passing with it a read-only segment key to
 *  its keylist (which is sorted first).  The second keyset is now Waiting
 *  for the first keyset to finish reading its data.
 *
 * 6 The first keyset takes the passed in segment, and shoves it into
 *  its own address space.
 *
 * 7 The first keyset then does whatever processing of the other
 *  address space that is needed.
 *
 * 8 When it is done, it removes the segment from its address space and
 *  CALLs the resume key to the second segment.  The first keyset is now
 *  Waiting for the other keyset to finish cleanup.
 *
 * 9 The second process now cleans up and goes back into its main loop,
 *  RETURNing to the first process.  The second process is now
 *  Available for requests.
 *
 *10 The first process finishes its processing and returns its results
 *  to its caller, and also becomes Available for requests
 *
 *  There is a single complication to this, which is that if some
 * bonehead asks a keyset to do an operation with itself, the right
 * thing *MUST* happen.  We *CAN'T* use this protocol, since CALLing a
 * start key to yourself means you block forever.  The solution is we
 * have a function which checks if a key is a start key to ourselves,
 * and the functions have the job of checking this *BEFORE* they start
 * the protocol, and returning the correct thing if it is a key to us.
 *
 * The protocol is implemented in four functions, plus some handling
 * code in ProcessRequest:
 *
 * VerifyAndGetSegmentOfSet:  Does steps 2, 3, and 6 of the protocol.
 *                           Stores the Return key from the second
 *                           keyset in KR_SETRESUME.  Returns
 *                           RC_Internal_KeyToSelf if the key is to me.
 *
 *            SlaveProtocol:  Does steps 4, 5, and 9 of the protocol.
 *                           Stores the new resume key in KR_RESUME
 *                           for the final RETURN, which is done in
 *                           main.
 *
 *            ReturnSegment:  Calls KR_SETRESUM, doing step 8 of the
 *                           protocol.
 *
 */
 

#define OUR_TABLE_SLOT 3
#define OTH_TABLE_SLOT 2

/* I keep all of the current status information in a structure at the
   top of the stack.  This code here sets up STAT, a pointer to this
   structure.  Since a push decrements SP then writes, my starting SP
   should be the same as &STAT. */

struct KeySetStat STAT;

#define ADDR_SLOT_SIZE     (1u << (EROS_ADDRESS_BITS - EROS_NODE_LGSIZE))
#define SLOT_TO_ADDR(slot) (slot * ADDR_SLOT_SIZE)
/* assumes that the outermost node is the full address space */

struct table_entry * const the_table   = (void *)SLOT_TO_ADDR(OUR_TABLE_SLOT);
/* ^^^ where we installed our VCS */

struct table_entry * const other_table = (void *)SLOT_TO_ADDR(OTH_TABLE_SLOT);
/* ^^^ where we store the other guy */

void require_sorted_table(void)
{
  if (STAT.numUnsorted) {
    STAT.numSorted += STAT.numUnsorted;
    STAT.numUnsorted = 0;

    sortTable(the_table, STAT.numSorted);
  }
}

volatile void
teardown(void);

void
Initialize(void)
{
  uint32_t result;
  uint32_t keyType;

  STAT.initstate = START;

  node_copy(KR_CONSTIT, KC_OSTREAM,  KR_OSTREAM);
  node_copy(KR_CONSTIT, KC_KEYBITS,  KR_KEYBITS);
  node_copy(KR_CONSTIT, KC_RETURNER, KR_RETURNER);
  node_copy(KR_CONSTIT, KC_DISCRIM,  KR_DISCRIM);

  STAT.numSorted = 0;
  STAT.numUnsorted = 0;
  STAT.end_of_table = the_table;
  
  GetKeyBits(KR_KEYBITS,
	     KR_VOID,
	     &STAT.startKeyBitsVersion,
	     NULL);

  kprintf(KR_OSTREAM, "Initializing Keyset\n");
  /* Using KR_ARG0, KR_SCRATCH as scratch registers */

  /* Buy a new root node for address space: */
  result = spcbank_buy_nodes(KR_BANK, 1, KR_ADDRNODE, KR_VOID, KR_VOID);
  if (result != RC_OK) {
    DEBUG(init) 
      kdprintf(KR_OSTREAM, "KeySet: spcbank nodes exhausted\n", result);
    teardown();
  }

  /* make that node LSS=EROS_ADDRESS_BLSS */
  node_make_node_key(KR_ADDRNODE, EROS_ADDRESS_BLSS, KR_ADDRNODE);

  DEBUG(init) kdprintf(KR_OSTREAM, "KeySet: fetch my own space\n", result);
  process_copy(KR_SELF, ProcAddrSpace, KR_SCRATCH);

  DEBUG(init) kdprintf(KR_OSTREAM,
		       "KeySet: plug self spc into new spc root\n",
		       result);
  node_swap(KR_ADDRNODE, 0, KR_SCRATCH, KR_VOID);
  
  DEBUG(init) kdprintf(KR_OSTREAM, "KeySet: before lobotomy\n", result);
  process_swap(KR_SELF, ProcAddrSpace, KR_ADDRNODE, KR_VOID);
  DEBUG(init) kdprintf(KR_OSTREAM, "KeySet: post lobotomy\n", result);

  STAT.initstate = LOBOTOMIZED;

  /* Construct the ZSF that will hold the actual directory data */
  DEBUG(init) kdprintf(KR_OSTREAM, "KeySet: Building ZSF\n");

  node_copy(KR_CONSTIT, KC_ZSF, KR_SCRATCH);
  result = constructor_request(KR_SCRATCH,
			       KR_BANK,
			       KR_SCHED,
			       KR_VOID,
			       KR_SCRATCH);

  DEBUG(init) kdprintf(KR_OSTREAM, "KeySet: Result is: 0x%08x\n", result);

  key_kt(KR_SCRATCH, &keyType, 0);

  if (result != RC_OK
      || keyType == RC_Void ) {
    DEBUG(init) kdprintf(KR_OSTREAM, "KeySet: Failed to build ZS.\n");
    teardown();
  }
  /* plug in newly allocated ZSF */
  DEBUG(init) kdprintf(KR_OSTREAM,
		       "KeySet: plugging zsf into new spc root\n", result);
  node_swap(KR_ADDRNODE, OUR_TABLE_SLOT, KR_SCRATCH, KR_VOID);

  /* if we add more initialization: STAT.initstat = ZSBOUGHT; */

  STAT.initstate = RUNNING;
  return;
}

volatile void
teardown(void)
{
  uint32_t result;

  /* this is in reverse order of construction.  
     FALL THROUGHS ARE INTENTIONAL. */

  switch(STAT.initstate) {  
  case RUNNING:
  case ZSBOUGHT:
    /* destroy the vcs */
    node_copy(KR_ADDRNODE, OUR_TABLE_SLOT, KR_SCRATCH);
    
    result = key_destroy(KR_SCRATCH);
    if (result != RC_OK) {
      kdprintf(KR_OSTREAM,
	       "KeySet: Failed to destroy my VCS (0x%08x)!\n", result);
    }
    /* FALL THROUGH */
  case LOBOTOMIZED:
    /* first, lets get our address space back to its original form */
    node_copy(KR_ADDRNODE, 0, KR_SCRATCH);
    process_swap(KR_SELF, ProcAddrSpace, KR_SCRATCH, KR_VOID);

    /* return the node */
    result = spcbank_return_node(KR_BANK, KR_ADDRNODE);
    if (result != RC_OK) {
      kdprintf(KR_OSTREAM,
	       "KeySet: Failed to return address space node (0x%08x)!\n",
	       result);
    }
    /* FALL THROUGH */
  case START:
  }

  /* now, shoot myself in the head: */
  
  /* get the protospace */
  node_copy(KR_CONSTIT, KC_PROTOSPC, KR_SCRATCH);

  /* destroy as small space. */
  protospace_destroy(KR_RETURNER, KR_SCRATCH, KR_SELF, KR_CREATOR,
		     KR_BANK, 1);
  /* NOTREACHED */
}

uint32_t
VerifyAndGetSegmentOfSet(uint32_t krOtherSet,
			 uint32_t *retNumItems)
{
  Message msg;
  uint32_t result;
  uint32_t keyInfo;
  uint32_t isEqual;

  /* it's got to be a KEYDATA 0u start key */
  result = proccre_amplify_gate(KR_CREATOR, krOtherSet, KR_SCRATCH2,
				0, &keyInfo);
  if (result != RC_OK ||
      (keyInfo != Normal_KeyData       /* writable */
       && keyInfo != ReadOnly_KeyData)) { /* read-only */
    DEBUG(protocol)
      kprintf(KR_OSTREAM,
	      "Validation failed.  Got result %08x\n",result);  
    return KT; /* nice try, fool. */
  }

  discrim_compare(KR_DISCRIM, KR_SELF, KR_SCRATCH2, &isEqual);
  
  if (isEqual)
    return RC_Internal_KeyToSelf;

  DEBUG(protocol)
    kprintf(KR_OSTREAM,
	    "Validated.  Starting MasterProtocol.\n");

  result = process_make_start_key(KR_SELF,
				 GetSegment_KeyData,
				 KR_SCRATCH2);

  if (result != RC_OK) {
    kdprintf(KR_OSTREAM,
	     "KeySet: Error creating Protocol Start Key. \n");
  }

  DEBUG(protocol) ShowKey(KR_OSTREAM, KR_KEYBITS, KR_SCRATCH2);

  msg.snd_w1 = 0u;
  msg.snd_w2 = 0u;
  msg.snd_w3 = 0u;
  
  msg.snd_key0 = KR_SCRATCH2;
  msg.snd_key1 = KR_VOID;
  msg.snd_key2 = KR_VOID;
  msg.snd_key3 = KR_VOID;
  msg.snd_len = 0;

  msg.rcv_key0 = KR_SCRATCH2;
  msg.rcv_key1 = KR_VOID;
  msg.rcv_key2 = KR_VOID;
  msg.rcv_key3 = KR_SETRESUME;
  msg.rcv_len = 0;

  msg.snd_code = OC_KeySet_Internal_GetSegment;
  msg.snd_invKey = krOtherSet;
  
  result = CALL(&msg);
  if (result == RC_KeySet_SetInvalid)
    return RC_KeySet_PassedSetInvalid;
  else if (result != RC_OK) {
    kdprintf(KR_OSTREAM,
	     "KeySet1: Hey! We just failed to start Internal "
	     "protocol.(%08x)\n",
	     msg.rcv_code);
    return RC_RequestError;
  }
  
  node_swap(KR_ADDRNODE, OTH_TABLE_SLOT, KR_SCRATCH2, KR_VOID);
  /* Now, it's mapped in memory. */

  /* give our caller the number if items in the other guy. */
  if (retNumItems) *retNumItems = msg.rcv_w1;
  
  DEBUG(protocol) 
    if (msg.rcv_w1) {  /* there is data */
      uint32_t tmp;
      kprintf(KR_OSTREAM,"KeySet1: Checking mapping\n");
      tmp = other_table[0].w[0];
      kprintf(KR_OSTREAM,"KeySet1: other_table[0].w[0] = %08x\n",tmp);
      tmp = other_table[msg.rcv_w1 - 1].w[0];
      kprintf(KR_OSTREAM,
              "KeySet1: other_table[numTheirItems].w[0] = %08x\n",tmp);
      kprintf(KR_OSTREAM,"KeySet1: It's all there.\n"); 
    }

  DEBUG(protocol) kprintf(KR_OSTREAM,"KeySet1: Segment mapped into memory\n");

  return RC_OK;
}

uint32_t
SlaveProtocol(void)
{
  Message myMsg;
  uint32_t keyInfo;
  uint32_t result = proccre_amplify_gate(KR_CREATOR, KR_ARG0, KR_VOID,
					 0, &keyInfo);
  DEBUG(protocol)
    kprintf(KR_OSTREAM,
	    "2ndKeySet: Amplify Gate returned 0x%04x\n",
	    result);

  DEBUG(protocol) ShowKey(KR_OSTREAM, KR_KEYBITS, KR_ARG0);

  if (result != RC_OK || keyInfo != GetSegment_KeyData) {
    DEBUG(protocol)
      kprintf(KR_OSTREAM,
	      "Validation failed.  Returning RC_UnknownRequest.\n");
    /* Internal Protocol? what's that? */
    return RC_UnknownRequest;
  }
  DEBUG(protocol)
    kprintf(KR_OSTREAM,
	    "2ndKeySet: Validated.  Starting SlaveProtocol.\n");

  /* first, make sure my segment is sorted. */
  require_sorted_table();

  /* get my segment */
  node_copy(KR_ADDRNODE, OUR_TABLE_SLOT, KR_SCRATCH);
  
  /* make the segment read-only 
      -- he sure doesn't need to be able to write it */
  seg_make_segment_key(KR_SCRATCH, SEGMODE_RO, KR_SCRATCH);
  
  myMsg.snd_w1 = STAT.numSorted;
  myMsg.snd_w2 = 0u;
  myMsg.snd_w3 = 0u;
  
  myMsg.snd_key0 = KR_SCRATCH;
  myMsg.snd_key1 = KR_VOID;
  myMsg.snd_key2 = KR_VOID;
  myMsg.snd_key3 = KR_VOID;
  myMsg.snd_len = 0;
  
  myMsg.rcv_key0 = KR_VOID;
  myMsg.rcv_key1 = KR_VOID;
  myMsg.rcv_key2 = KR_VOID;
  myMsg.rcv_key3 = KR_RETURN; /* for their new resume key */
  myMsg.rcv_len = 0;
  
  myMsg.snd_code = RC_OK;
  myMsg.snd_invKey = KR_RETURN;

  /* CALL them so we won't be interrupted */
  if (CALL(&myMsg) != RC_OK) {
    kdprintf(KR_OSTREAM,
	     "KeySet2: Hey! We just failed to complete Internal protocol.\n");
  }

  DEBUG(protocol)
    kprintf(KR_OSTREAM,
	    "Finished SlaveProtocol successfully.\n");
  
  /* the CALL on the passed in resume key passed us a new resume
     key, which we will return to */
  return RC_OK; /* return success to them, completing the protocol */
}

uint32_t
ReturnSegment(void)
{
  Message msg;

  DEBUG(protocol)
    kprintf(KR_OSTREAM,
	    "KeySet1: Returning segment to KeySet2\n");

  node_swap(KR_ADDRNODE, OTH_TABLE_SLOT, KR_VOID, KR_VOID);
  /* Now, it's unmapped from memory. */
  
  msg.snd_w1 = 0u;
  msg.snd_w2 = 0u;
  msg.snd_w3 = 0u;
  
  msg.snd_key0 = KR_VOID;
  msg.snd_key1 = KR_VOID;
  msg.snd_key2 = KR_VOID;
  msg.snd_key3 = KR_VOID;
  msg.snd_len = 0;

  msg.rcv_key0 = KR_SCRATCH2;
  msg.rcv_key1 = KR_VOID;
  msg.rcv_key2 = KR_VOID;
  msg.rcv_key3 = KR_SETRESUME;
  msg.rcv_len = 0;

  msg.snd_code = RC_OK;
  msg.snd_invKey = KR_SETRESUME;

  return CALL(&msg);
}

/* FIXME: options regarding data fields? */
uint32_t
AddKeysFromSet(uint32_t krOtherSet)
{
  uint32_t theirCount;
  uint32_t myCount = STAT.numSorted;
  uint32_t result;

  struct table_entry *myEntry = the_table;
  struct table_entry *theirEntry = other_table;
  
  result = VerifyAndGetSegmentOfSet(krOtherSet, &theirCount);
  if (result == RC_Internal_KeyToSelf) 
    return RC_OK; /* I've already got all of my keys */
  else if (result == RC_KeySet_PassedSetInvalid)
    return RC_KeySet_PassedSetInvalid;
  else if (result != RC_OK) {
    /* nice try. */
    return RC_RequestError;
  }
  /* now we've got the other segment */

  /* search through their table for items not in mine, and add them to
     the unsorted list (note that both of the lists are sorted coming
     into this code) */
  
  while (theirCount && myCount) {
    int cmpres = compare(myEntry->w, theirEntry->w);
    
    if (cmpres == 0) {
      /* We match -- increment both */
      myEntry++;
      myCount--;
      
      theirEntry++;
      theirCount--;
    } else if (cmpres > 1) {