vcsk.c

C++ 编写的EROS RTOS

		 " zero subsegment\n");
      return RC_OK;
    }
    
  case FC_Access:
    {
      /* Subseg is read-only */

      uint16_t subsegBlss;
      
      uint32_t result;
      uint32_t orig_offset = offset;
      
      bool_t needTraverse = true;

      DEBUG(access)
	kdprintf(KR_OSTREAM, "FC_Access at 0x%08x %08x\n",
		 (uint32_t) (offset>>32),
		 (uint32_t) offset);
      
#if KR_L1_NODE != KR_SEGMENT
      /* If the last thing we got hit with was an access fault, and
	 the present fault would land within the same L1 node, there
	 is no need to re-execute the traversal; simply reuse the
	 result from the last traversal:

	 It is fairly obvious that this is safe if the access pattern
	 is of the form

	     0b=========00001xxxx
	     0b=========00002xxxx

	 It is also safe if the access pattern was:
	 
	     ???

	 Because the second fault will result in an invalid address
	 before generating the access violation, which will cause the
	 segment to grow and invalidate the walk cache.

	 The tricky one is if the pattern is the other way:

	     0b=========00001xxxx
	     0b=========00000xxxx

         In this case, we will have done tree expansion in the first
	 path and have cached the right information.
	 
	 This hack only possible with 32-slot nodes. */
      
      if (pState->was_access) {
	uint64_t xoff = offset ^ pState->last_offset;
	xoff >>= (EROS_PAGE_ADDR_BITS + EROS_NODE_LGSIZE);
	if (xoff == 0) {
	  needTraverse = false;
	  slot = (offset >> EROS_PAGE_ADDR_BITS) & EROS_NODE_SLOT_MASK;
	  subsegBlss = 2;
	  node_copy(KR_L1_NODE, slot, KR_SCRATCH);

	  DEBUG(access)
	    kdprintf(KR_OSTREAM, "Re-traverse suppressed at slot %d!\n", slot);
	}
      }
#endif
      
      if (needTraverse) {
	pState->was_access = false; /* we COULD fail! */
	
	/* fetch out the subseg key */
	node_copy(KR_SEGMENT, slot, KR_SCRATCH);

	/* find out it's BLSS: */
	result = node_get_key_data(KR_SCRATCH, &subsegBlss);
	if (result == RC_UnknownRequest)
	  subsegBlss = EROS_PAGE_BLSS; /* it must be a page key */
      
	subsegBlss &= SEGMODE_BLSS_MASK;
	segBlss = subsegBlss + 1;
      
	DEBUG(access) kprintf(KR_OSTREAM, "  traverse slot %d, blss %d, offset 0x%08x %08x\n",
			      slot, segBlss,
			      (uint32_t) (offset >> 32),
			      (uint32_t) offset);

	/* Traverse downward past all writable capages: */

	while (subsegBlss > EROS_PAGE_BLSS) {
	  uint32_t w2;
	
	  DEBUG(access) kdprintf(KR_OSTREAM, "  Walking down: subsegBlss %d\n",
				 subsegBlss);

	  result = key_kt(KR_SCRATCH, &kt, &w2);
	  if (result != RC_OK || kt != AKT_Node || (w2 & SEGMODE_RO)) {
	    DEBUG(access) kdprintf(KR_OSTREAM, "  subsegBlss %d unwritable!\n",
				   subsegBlss);
	    break;
	  }

	  copy_key_reg(KR_RETURNER, KR_SCRATCH, KR_SEGMENT);

	  slot = BlssSlotNdx(offset, subsegBlss);
	  offset &= BlssMask(subsegBlss-1);

	  DEBUG(access) kprintf(KR_OSTREAM, "  traverse slot %d, blss %d, offset 0x%08x %08x %08x\n",
				slot, subsegBlss,
				(uint32_t) (offset>>32),
				(uint32_t) offset);

	  subsegBlss--;
	
	  node_copy(KR_SEGMENT, slot, KR_SCRATCH);
	}
      
	/* Have now hit a read-only subtree, which we need to traverse,
	   turning the R/O CaPage's into R/W capages. */

	while (subsegBlss > EROS_PAGE_BLSS) {
	  DEBUG(access) kdprintf(KR_OSTREAM, "  Walking down: COW subsegBlss %d\n",
				 subsegBlss);

	  /* Buy a new read-write capage: */
	  if (spcbank_buy_nodes(KR_BANK, 1, KR_NEWOBJ, KR_VOID, KR_VOID) !=
	      RC_OK)
	    return RC_NoMoreNodes;
      
	  /* Make that node have BLSS == subsegBlss: */
	  node_make_node_key(KR_NEWOBJ, subsegBlss, KR_NEWOBJ);

	  /* Copy the values from the old subseg into the new: */
	  node_clone(KR_NEWOBJ, KR_SCRATCH);

	  /* Replace the old subseg with the new */
	  node_swap(KR_SEGMENT, slot, KR_NEWOBJ, KR_VOID);

	  copy_key_reg(KR_RETURNER, KR_NEWOBJ, KR_SEGMENT);

	  /* Now traverse downward in the tree: */
	  slot = BlssSlotNdx(offset, subsegBlss);
	  offset &= BlssMask(subsegBlss-1);

	  DEBUG(access) kprintf(KR_OSTREAM, "  traverse slot %d, blss %d, offset 0x%08x %08x\n",
				slot, subsegBlss,
				(uint32_t) (offset>>32),
				(uint32_t) offset);

	  subsegBlss--;

	  node_copy(KR_SEGMENT, slot, KR_SCRATCH);
	}

#if KR_L1_NODE != KR_SEGMENT
	/* KR_SEGMENT now points to the parent of the page key we are
	   COWing. If we are doing the L1 node memoization, record the
	   last manipulated L1 node here. */
	copy_key_reg(KR_RETURNER, KR_SEGMENT, KR_L1_NODE);
#endif
      }

      /* Now KR_SCRATCH names a page and KR_L1_NODE is it's containing
	 node, and KR_L1_NODE[slot] == KR_SCRATCH. */

      DEBUG(access) kdprintf(KR_OSTREAM, "  Walking down: COW"
			     " subsegBlss %d (target page)\n"
			     " orig_offset 0x%08x first zero offset 0x%08x\n",
			     subsegBlss, orig_offset,
			     pState->first_zero_offset);
      
      if (orig_offset >= pState->first_zero_offset) {
	uint32_t count;
	
	/* Insert new zero pages at this location. As an optimization,
	   insert ZERO_EXTEND_BY pages at a time. */
	for (count = 0; ((slot < EROS_NODE_SIZE) &&
			 (count < ZERO_EXTEND_BY)); count++, slot++) {
	  uint32_t kr = AllocPage(pState);

	  if (kr == KR_VOID) {
	    if (count)
	      break;
	    else
	      return RC_NoMorePages;
	  }

	  node_swap(KR_L1_NODE, slot, kr, KR_VOID);

	  pState->was_access = true;
	  pState->last_offset = 
	    (orig_offset & ~EROS_PAGE_MASK) + (count-1) * EROS_PAGE_SIZE;
	}
	DEBUG(returns)
	  kdprintf(KR_OSTREAM,
		   "Returning from FC_Access after appending %d empty"
		   " pages at 0x%08x\n", count, orig_offset);
	return RC_OK;
      }
      else {
	uint32_t kr = AllocPage(pState);
	if (kr == KR_VOID)
	  return RC_NoMorePages;

	page_clone(kr, KR_SCRATCH);
	    
	/* Replace the old page with the new */
	node_swap(KR_L1_NODE, slot, kr, KR_VOID);

	pState->was_access = true;
	pState->last_offset = orig_offset;
	
	/* We assume at this point that the page in question no longer
	   contains zeros, so the first zero offset must be above this
	   point. */
	if (orig_offset >= pState->first_zero_offset)
	  pState->first_zero_offset =
	    (orig_offset & ~EROS_PAGE_MASK) + EROS_PAGE_SIZE;

	DEBUG(returns)
	  kdprintf(KR_OSTREAM,
		   "Returning from FC_Access after duplicating"
		   " page at 0x%08x\n", orig_offset);

	return RC_OK;
      }
    }

  default:
    return pMsg->rcv_w1;	/* fault code */
  }
}

int
ProcessRequest(Message *argmsg, state *pState)
{
  uint32_t result = RC_OK;
  
  switch(argmsg->rcv_code) {
  case OC_KeyType:			/* check alleged keytype */
    {
      argmsg->snd_w1 = AKT_VcskSeg;
      break;
    }      
  case OC_Vcsk_InvokeKeeper:
    if (pState->frozen) {
      result = RC_RequestError;
      break;
    }
    
    result = HandleSegmentFault(argmsg, pState);
    break;

  case OC_Vcsk_MakeSpaceKey:
    {
      uint16_t keyData;
      
      /* FIX: A node_restrict operation might be useful here... */
		
      node_get_key_data(KR_SEGMENT, &keyData);
      keyData |= (argmsg->rcv_w1 & SEGMODE_ATTRIBUTE_MASK);
      node_make_segment_key(KR_SEGMENT, keyData, KR_SEGMENT);
      argmsg->snd_key0 = KR_SEGMENT;
      result = RC_OK;
      break;
    }

#if 0
  case OC_Vcsk_Truncate:
  case OC_Vcsk_Pack:
    if (pState->frozen) {
      result = RC_RequestError;
      break;
    }
#endif
    
  case OC_Destroy:
    {
      DestroySegment(pState);

      Sepuku();
      break;
    }
    
    /* above not implemented yet */
  default:
    result = RC_UnknownRequest;
    break;
  }
  
  argmsg->snd_code = result;
  return 1;
}

/* In spite of unorthodox fabrication, the constructor self-destructs
   in the usual way. */
void
Sepuku()
{
  node_copy(KR_CONSTIT, KC_PROTOSPC, KR_SEGMENT);

  spcbank_return_node(KR_BANK, KR_CONSTIT);

  /* Invoke the protospace with arguments indicating that we should be
     demolished as a small space domain */
  protospace_destroy(KR_RETURNER, KR_SEGMENT, KR_SELF,
		     KR_DOMCRE, KR_BANK, 1);
}

/* Tree destruction is a little tricky.  We know the height of the
   tree, but we have no simple way to build a stack of node pointers
   as we traverse it.

   The following algorithm is pathetically brute force.
   */
int
ReturnWritableSubtree(uint32_t krTree)
{
  uint32_t w1;
  uint32_t kt;
  uint32_t result = key_kt(krTree, &kt, &w1);
  
  for (;;) {
    if (result != RC_OK || kt == RC_Void) {
      /* Segment has been fully demolished. */
      return 0;
    }
    else if (w1 & SEGMODE_RO) {
      /* This case can occur if the entire segment is both tall and
         unmodified. */
      return 0;
    }
    else if (kt == AKT_Page) {
      spcbank_return_data_page(KR_BANK, krTree);
      return 1;			/* more to do */
    }
    else if (kt == AKT_Node) {
      int i;
      for (i = 0; i < EROS_NODE_SIZE; i++) {
	uint32_t sub_kt;
	uint32_t result;
	node_copy(krTree, i, KR_SCRATCH2);
      
	result = key_kt(KR_SCRATCH2, &sub_kt, &w1);

	if (w1 & SEGMODE_RO) {
	  /* do nothing */
	}
	else if (sub_kt == AKT_Page) {
	  spcbank_return_data_page(KR_BANK, KR_SCRATCH2);
	}
	else if (sub_kt == AKT_Node) {
	  copy_key_reg(KR_RETURNER, KR_SCRATCH2, KR_SCRATCH);
	  kt = sub_kt;
	  break;
	}
      }

      if (i == EROS_NODE_SIZE) {
	/* If we get here, this node has no children.  Return it, but
	   also return 1 because it may have a parent node. */
	spcbank_return_node(KR_BANK, KR_SCRATCH);
	return 1;
      }
    }
    else {
      kdprintf(KR_OSTREAM, "Returning a key with kt=0x%x\n", kt);
    }
  }
}

void
DestroySegment(state *mystate)
{
  nk_value offset;

  offset.value[0] = 0;
  offset.value[1] = 0;
  offset.value[2] = 0;

  for(;;) {
    node_copy(KR_SEGMENT, 0, KR_SCRATCH);

    if (!ReturnWritableSubtree(KR_SCRATCH))
      break;
  }

  DEBUG(destroy) kdprintf(KR_OSTREAM, "Destroying red seg root\n");
  spcbank_return_node(KR_BANK, KR_SEGMENT);
}

void
Initialize(state *mystate)
{
  uint32_t result;
  uint16_t segBlss;
  nk_value nkv;
  
  mystate->was_access = false;
  mystate->first_zero_offset = ~0ull; /* until proven otherwise below */
  mystate->npage = 0;
  
  node_copy(KR_CONSTIT, KC_OSTREAM, KR_OSTREAM);
  node_copy(KR_CONSTIT, KC_RETURNER, KR_RETURNER);
  node_copy(KR_CONSTIT, KC_ZINDEX, KR_ZINDEX);
  node_copy(KR_CONSTIT, KC_FROZEN_SEG, KR_RK0);

  DEBUG(init) kdprintf(KR_OSTREAM, "Fetch BLSS of frozen seg\n");
  
  /* find out BLSS of frozen segment: */
  result = node_get_key_data(KR_RK0, &segBlss);
  if (result == RC_UnknownRequest)
    segBlss = EROS_PAGE_BLSS; /* it must be a page key */
      
  segBlss &= SEGMODE_BLSS_MASK;

  DEBUG(init) kdprintf(KR_OSTREAM, "BLSS of frozen seg was %d\n", segBlss);
  
  mystate->first_zero_offset =
    EROS_PAGE_SIZE << ( (segBlss - EROS_PAGE_BLSS) * EROS_NODE_LGSIZE);
    
  DEBUG(init) kdprintf(KR_OSTREAM, "Offsets above 0x%08x%08x are"
		       " presumed to be zero\n",
		       (uint32_t) (mystate->first_zero_offset >> 32),
		       (uint32_t) mystate->first_zero_offset);

  segBlss += 1;
  
  DEBUG(init) kdprintf(KR_OSTREAM, "Buy new seg node\n");
  
  spcbank_buy_nodes(KR_BANK, 1, KR_SEGMENT, KR_VOID, KR_VOID);

  DEBUG(init) kdprintf(KR_OSTREAM, "Make it red\n");

  /* make it a red ***capage*** */
  node_make_node_key(KR_SEGMENT, 1, KR_SEGMENT);

  /* write the format key */
#ifdef KT_Wrapper
  nkv.value[0] = WRAPPER_SEND_NODE | WRAPPER_KEEPER;
  WRAPPER_SET_BLSS(nkv, segBlss);
  nkv.value[1] = 0;
  nkv.value[2] = 0;

  node_write_number(KR_SEGMENT, WrapperFormat, &nkv);
#else
  nkv.value[0] = 0;
  REDSEG_SET_INITIAL_SLOTS(nkv, 1);
  REDSEG_SET_SENDNODE(nkv, REDSEG_SEND_NODE);
  REDSEG_SET_KPR_SLOT(nkv, RedSegKeeper);
  REDSEG_SET_BG_SLOT(nkv, RedSegFormat); /* none */
  REDSEG_SET_BLSS(nkv, segBlss); /* none */
  nkv.value[1] = 0;
  nkv.value[2] = 0;

  node_write_number(KR_SEGMENT, RedSegFormat, &nkv);
#endif

  /* write the immutable seg to slot 0 */
  node_swap(KR_SEGMENT, 0, KR_RK0, KR_VOID);

  /* make a start key to ourself and write that in slot 14 */
  process_make_start_key(KR_SELF, 0, KR_RK0);
#ifdef KT_Wrapper
  node_swap(KR_SEGMENT, WrapperKeeper, KR_RK0, KR_VOID);

  node_make_wrapper_key(KR_SEGMENT, 0, KR_SEGMENT);
#else
  node_swap(KR_SEGMENT, RedSegKeeper, KR_RK0, KR_VOID);

  node_make_segment_key(KR_SEGMENT, 1, KR_SEGMENT);
#endif

  DEBUG(init) kdprintf(KR_OSTREAM, "Red seg now constructed... returning\n");
}

int
main()
{
  Message msg;

  state mystate;

  Initialize(&mystate);

  DEBUG(init) kdprintf(KR_OSTREAM, "Initialized VCSK\n");
    
  msg.snd_invKey = KR_RESUME;
  msg.snd_key0 = KR_SEGMENT;	/* first return: seg key */
  msg.snd_key1 = KR_VOID;
  msg.snd_key2 = KR_VOID;
  msg.snd_key3 = KR_VOID;
  msg.snd_data = 0;
  msg.snd_len = 0;
  msg.snd_code = 0;
  msg.snd_w1 = 0;
  msg.snd_w2 = 0;
  msg.snd_w3 = 0;

  msg.rcv_key0 = KR_RK0;
  msg.rcv_key1 = KR_RK1;
  msg.rcv_key2 = KR_RK2;
  msg.rcv_key3 = KR_RESUME;
  msg.rcv_len = 0;
  msg.rcv_code = 0;
  msg.rcv_w1 = 0;
  msg.rcv_w2 = 0;
  msg.rcv_w3 = 0;

  do {
    msg.rcv_len = 0;
    RETURN(&msg);
    mystate.frozen = msg.rcv_keyInfo;
    msg.snd_key0 = KR_VOID;	/* until otherwise proven */
  } while ( ProcessRequest(&msg, &mystate) );

  return 0;
}