spacebank_test.c

C++ 编写的EROS RTOS

/*
 * Copyright (C) 1998, 1999, Jonathan Adams.
 * Copyright (C) 2001, The EROS Group, LLC.
 *
 * 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/KeyBitsKey.h>
#include <eros/NodeKey.h>
#include <eros/PageKey.h>
#include <eros/StdKeyType.h>
#include <eros/SleepKey.h>
#include <domain/SpaceBankKey.h>
#include <domain/domdbg.h>

#define NODE_ALLOC_CHECK

#ifdef GNU
#define INLINE inline
#else
#define INLINE
#endif

/* define the following if you want the test to stop after each stage */
/* #define STPRINTF kdprintf */
#define VERBOSE

#ifndef STPRINTF
#define STPRINTF kprintf
#endif

#define KR_VOID       0

#define KR_SPACEBANK  1
#define KR_CONSOLEKEY 2
#define KR_SLEEPKEY   3
#define KR_KEYBITS    4

#define KR_PARBANK    5
#define KR_SUBBANK    6

#define KR_TMP0       7
#define KR_TMP1       8
#define KR_TMP2       9
#define KR_TMP3      10

/* key stuff */
#define KR_KEYBASE   11
#define KR_KEY(x)    (KR_KEYBASE+(x))

#define NUM_KEYS     (EROS_PROCESS_KEYREGS-KR_KEYBASE)



#define SLEEP_TME  0 /* (100/7) */

/* define DIRTY_OBJECTS if you want all allocated objects dirtied */
#define DIRTY_OBJECTS 1


#define NUM_LEVELS (3u)
/* nnumber of levels in the node tree */

#define NUM_ITEMS (1u << (4*NUM_LEVELS))
/* == 16 ^ NUM_LEVELS */

/**Handle the stack stuff**/
const uint32_t __rt_stack_pages = 0;
const uint32_t __rt_stack_pointer = 0x10000;

/* key_array_info holds information about the tree of nodes used
   to store keys. 
   For each level i, KR_KEY(i) refers to the current node at level i,
   and alloced[i] is the number of slots used in the node at level i+1
   (except that if alloced[i+1]==0, i is the top level).
   The leaf nodes are at level 0. */
struct key_array_info
{
  uint32_t alloced[NUM_KEYS];  
  uint32_t curKeys;  /* number of keys in 0th-level node */
};

uint32_t
init_key_array(struct key_array_info *info,
	       const char *name,
	       uint32_t krBank)
{
  int idx;

  for (idx = 0; idx < NUM_KEYS; idx++) 
    info->alloced[idx] = 0;
  
  /* allocate the starting node */
  if (spcbank_buy_nodes(krBank,1,KR_KEY(0),KR_VOID,KR_VOID) 
      != RC_OK) {
    return 1;
  }

  info->alloced[0]++;  /*mark it as allocated */
  info->curKeys = 0;

  return 0;
}

uint32_t
insert_key(struct key_array_info *info, 
	   const char *name,
	   uint32_t krBank,
	   uint32_t fromSlot)
{
  if (info->curKeys >= EROS_NODE_SIZE) {
    /* We need to grow the tree. */
    uint32_t maxEff;
    uint32_t cur;
    uint32_t didAllocBase = 0;

    /* find the first non-full level */
    for (maxEff = 0;
          maxEff < NUM_KEYS
	  && info->alloced[maxEff] >= EROS_NODE_SIZE;
           maxEff++)
      ; /* NOTHING */
    
    if (maxEff >= NUM_KEYS
	|| info->alloced[maxEff] == 0 ) {
      /* SHOULDN'T HAPPEN */
      kdprintf(KR_CONSOLEKEY,
	       "%s: Impossible condition in insert_key %d %d\n",
	       name, maxEff, info->alloced[maxEff]);
      return 1;
    }
    
    if (maxEff == NUM_KEYS - 1) {
      kdprintf(KR_CONSOLEKEY,
               "%s: Hey!  We're going to use more than %d levels!\n"
	       "     That's pow(%d,%d) keys!\n",
	       name,NUM_KEYS,EROS_NODE_SIZE,NUM_KEYS);
      return 1; /* FAILED */
    }
    if (info->alloced[maxEff+1] == 0) {
      /* We need to increase the depth of the tree. */
      /* Buy the node for level maxEff+1 */
      if (spcbank_buy_nodes(krBank,1,KR_KEY(maxEff+1),KR_VOID,KR_VOID) 
	  != RC_OK) {
	kprintf(KR_CONSOLEKEY,
		"%s: Hey! Failed to allocate new head node (%d levels).\n",
		name,maxEff);
	return 1; /* FAILED */
      }
      /* mark level maxEff+1 as having a single node */
      info->alloced[maxEff+1]++;
      /* mark this true so we can remove it later. */
      didAllocBase = 1;

      /* copy in the maxEff level key as the first key in the new node */
      node_swap(KR_KEY(maxEff+1),0,KR_KEY(maxEff),KR_VOID);
      
#ifdef VERBOSE
      kprintf(KR_CONSOLEKEY,"%d", maxEff+1);
#endif
    }
    /* Now KR_KEY(maxEff) isn't the only key to its node. */
    /* loop, creating a new node at each level */
    cur = maxEff;
    do {
      if (spcbank_buy_nodes(krBank,1,KR_KEY(cur),KR_VOID,KR_VOID)
	  != RC_OK) {
	kprintf(KR_CONSOLEKEY,"\n%s: Failed to buy node.\n",name);
	/* clean up */
	while (cur < maxEff) {
	  cur++;
	  if (spcbank_return_node(krBank,KR_KEY(cur)) != RC_OK) {
	    kdprintf(KR_CONSOLEKEY,"%s: Failed to return node.\n",name);
	  }
	  info->alloced[cur]--;
	  node_copy(KR_KEY(cur + 1),info->alloced[cur],KR_KEY(cur));
	}
	if (didAllocBase) {
	  if (spcbank_return_node(krBank,KR_KEY(maxEff+1)) != RC_OK) {
	    kdprintf(KR_CONSOLEKEY,"%s: Failed to return node.\n",name);
	  }	  
	  info->alloced[maxEff+1] = 0;
	}
	return 1;
      }
      node_swap(KR_KEY(cur+1),
		info->alloced[cur],
		KR_KEY(cur),
		KR_VOID);
      info->alloced[cur]++;

#ifdef VERBOSE
      kprintf(KR_CONSOLEKEY,"+");
#endif
      
    } while (cur-- > 0);

    /* now that we have successfully allocated everything, update the
       table. */
    for (cur = 0; cur < maxEff; cur++) {
      info->alloced[cur] = 1; /* the higher node is empty 
                                 except for a pointer to this node */
    }
    info->curKeys = 0; /* we now have a new bottom level node */
  }

  /* curKeys is now guarenteed to be < EROS_NODE_SIZE -- we can insert
     the new key into the curKeys slot...*/

  node_swap(KR_KEY(0),
	    info->curKeys++,
	    fromSlot,
	    KR_VOID);

  return RC_OK;
}

uint32_t
dealloc_array(struct key_array_info *info,
	      const char *name,
	      uint32_t (*dealloc_func)(uint32_t fromSlot, uint32_t krBank),
	      uint32_t krBank,
	      uint32_t tmpSlot)
{
  /* smashes tmpSlot */

  uint32_t curpos[NUM_KEYS];
  uint32_t lvl;
  uint32_t maxLvl;
  uint32_t slotNum;
  uint32_t numDeallocs;

  
  /* clear the curpos array */
  for (lvl = 0; lvl < NUM_KEYS; lvl++)
    curpos[lvl] = 0;
 
  /* find the maximum level */
  maxLvl = 0;
  while(1) {
    if (info->alloced[maxLvl] == 1
	&& (maxLvl == NUM_KEYS-1 || info->alloced[maxLvl+1] == 0))
      break;

    maxLvl++;

    /* sanity check */
    if (maxLvl >= NUM_KEYS) {
      kdprintf(KR_CONSOLEKEY,"%s: dealloc_array Impossible condition\n",name);
      return 1;
    }
  }
  
  curpos[maxLvl] = 1;
  
  /* grab the first items all the way down the tree */
  lvl = maxLvl;
  while (lvl > 0) {
    lvl--;
    node_swap(KR_KEY(lvl+1),0,KR_VOID,KR_KEY(lvl));
  }

  /* the bottom level isn't incremented until we have deallocated it
   */
  curpos[0] = 0;

#ifdef VERBOSE
  /* NO NEWLINE -- we print a dot/object deallocated */
  kprintf(KR_CONSOLEKEY,"%s: Deallocating",name);
#endif

  numDeallocs = 0;

  while (maxLvl > 0) {
    /* first, deallocate the items in the key(0) slot */
    for (slotNum = 0; slotNum < info->curKeys; slotNum++) {
      numDeallocs++;
      
      node_swap(KR_KEY(0),slotNum,KR_VOID,tmpSlot);
      if ((*dealloc_func)(tmpSlot,krBank) != RC_OK) {
	kdprintf(KR_CONSOLEKEY,
		 "\n%s: Error deallocating object #%d.\n",
		 name,
		 numDeallocs);
	return 1;
      }
#ifdef VERBOSE
      kprintf(KR_CONSOLEKEY,".");
#endif
    }
    if (spcbank_return_node(krBank,KR_KEY(0)) != RC_OK) {
      kdprintf(KR_CONSOLEKEY,
	       "\n%s: Error deallocating node!\n",name);
      return 1;
    }
    curpos[0]++; /* we are done with this node */

#ifdef VERBOSE
      kprintf(KR_CONSOLEKEY,"+");
#endif

    for (lvl = 0;
	  lvl < maxLvl - 1
	  && curpos[lvl] == EROS_NODE_SIZE;
  	   lvl++) {
      /* this level is empty -- remove the enclosing node */
      if (spcbank_return_node(krBank,KR_KEY(lvl+1)) != RC_OK) {
	kdprintf(KR_CONSOLEKEY,
		 "\n%s: Error deallocating node.\n",
		 name);
      }
#ifdef VERBOSE
      kprintf(KR_CONSOLEKEY,"+");
#endif
      curpos[lvl+1]++;
      curpos[lvl] = 0;
    }

    if (maxLvl == lvl + 1
 	   && curpos[lvl] + 1 == info->alloced[lvl]) {
      /* We will be putting in the last node from the maxLvl pile.
	 get the last node by hand, and deallocate the outer node. */
      
      node_swap(KR_KEY(lvl+1),curpos[lvl],KR_VOID,KR_KEY(lvl));

      if (spcbank_return_node(krBank,KR_KEY(maxLvl)) != RC_OK) {
	kdprintf(KR_CONSOLEKEY,
		 "\n%s: Error deallocating node.\n",
		 name);
      }
#ifdef VERBOSE
      kprintf(KR_CONSOLEKEY,"+");
#endif
      maxLvl--;
      lvl--;
    } else if (maxLvl == lvl + 1 
	       && curpos[lvl] + 1 > info->alloced[lvl]) {
      kdprintf(KR_CONSOLEKEY,
	       "%s: Impossible condition in dealloc_tree\n",
	       name);
    }
    /* now, we need to walk back down, getting the new nodes and
       resetting the current pointers. */

    do {
      node_swap(KR_KEY(lvl+1),curpos[lvl],KR_VOID,KR_KEY(lvl));
    } while (lvl-- > 0);

  }

  /* do the last one by hand */
  for (slotNum = 0; slotNum < info->curKeys; slotNum++) {
    numDeallocs++;

    node_swap(KR_KEY(0),slotNum,KR_VOID,tmpSlot);
    if ((*dealloc_func)(tmpSlot,krBank) != RC_OK) {
      kdprintf(KR_CONSOLEKEY,
	       "\n%s: Error deallocating object #%d.\n",
	       name,
	       numDeallocs);
      return 1;
    }
#ifdef VERBOSE
    kprintf(KR_CONSOLEKEY,".");
#endif
  }
  if (spcbank_return_node(krBank,KR_KEY(0)) != RC_OK) {
    kdprintf(KR_CONSOLEKEY,
	     "\n%s: Error deallocating last node!\n",name);
    return 1;
  }
#ifdef VERBOSE
  kprintf(KR_CONSOLEKEY,"+");
#endif
  return 0;
}


uint32_t
RunAllocTest(const char *test_name,
             uint32_t (*alloc_func)(uint32_t toSlot, uint32_t sbSlot),
             uint32_t (*dealloc_func)(uint32_t fromSlot, uint32_t sbSlot))
{
  /* this is a generic testing interface -- It basically
    calls *alloc_func with a slot number repeatedly, storing the
    result key away somewhere, until it returns a non-zero value, or
    is unable to allocate more storage for the keys.  At this point,
    it walks through the allocated objects, calling *dealloc_func for
    each one.
   
    if dealloc_func is NULL, then the allocated objects are not

    SMASHES KR_TMP0 and KR_PARBANK!!!
   */

  struct key_array_info info;  /* holds the key array data */
  uint32_t count; /* number of alloced objects */

  /* first create a bank for the test */
#ifdef VERBOSE
  kprintf(KR_CONSOLEKEY,
	  "%s: Allocating bank\n",test_name);
#endif

  if (spcbank_create_subbank(KR_SPACEBANK,KR_PARBANK) != RC_OK) {
    kdprintf(KR_CONSOLEKEY,
	     "%s: Unable to create subbank for testing.\n",
	     test_name);
    return 1;
  }
  if (init_key_array(&info,test_name,KR_PARBANK) != RC_OK) {
    kdprintf(KR_CONSOLEKEY,
	     "%s: Unable in init Key Array.\n",
	     test_name);
    return 1;
  }