alloctree.c

C++ 编写的EROS RTOS

/*
 * Copyright (C) 1998, 1999, 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/RangeKey.h>
#include <eros/Invoke.h>
#include <domain/Runtime.h>
#include <domain/domdbg.h>

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

#if CND_DEBUG(tree)
#define VERBOSE
#endif

#undef TREE_STATIC_ALLOC /* NO STATIC ALLOCATION */

#ifdef TREE_STATIC_ALLOC

#define NUM_TREENODES 512

TREENODE static_treenodes[NUM_TREENODES]; /* added to free list on
					   * startup
					   */

#endif

void debug_print_node(TREENODE *node);

/* head of the free list -- a list of free nodes linked by their right
 * links.
 */
static TREENODE *freehead = 0;

TREENODE *
tree_newNode(TREEKEY key)
{
  TREENODE *newNode;
  
  if (freehead == 0) {
    TREENODE *nodes;
    uint32_t x;
    
    DEBUG(malloc) kdprintf(KR_OSTREAM, "Allocating more tree nodes\n");
#ifdef TREE_STATIC_ALLOC
    kpanic(KR_OSTREAM,
	     "Spacebank: out of statically allocated Treenodes!\n");
    return TREE_NIL;
#else
    
#define NUM_NODES (8)
    
    nodes = malloc(sizeof(TREENODE) * NUM_NODES);
    x = NUM_NODES;

    DEBUG(malloc) kdprintf(KR_OSTREAM, " ... got data at 0x%08x\n",nodes);

    if (!nodes) {
      kpanic(KR_OSTREAM,
	     "Spacebank: mallocing Treenodes failed!\n");
    }

    /* add all of the new nodes to the freelist */
    while (x) {
      nodes[--x].parent = freehead;
      freehead = &nodes[x];
    }
#undef NUM_NODES
#endif
  }
  newNode = freehead;
  freehead = newNode->parent;

  {
    /* initialize value */
    uint32_t x;
    
    newNode->left = TREE_NIL;
    newNode->right = TREE_NIL;
    newNode->parent = TREE_NIL;
    newNode->color = TREE_BLACK;

    newNode->value = key;

    /* initialize body */
    for (x = 0; x < SB_FRAMES_PER_TREENODE; x++) {
      newNode->body.map[x] = 0u;
#ifndef TREE_NO_TYPES
      newNode->body.type[x] = SBOT_INVALID;
#endif      
    }
  }
  return newNode;
  
}

int
tree_deleteNode(TREENODE *node)
{
  if (node != NULL && node != TREE_NIL) {

    node->parent = freehead; /* link it in to free list */
    freehead = node;        /* then put it as head.    */
    
    return 1;
    
  } else {
    return 0;
  }
    
}

/* allocTree functions */
static void
_allocTree_clearCachedInfo(TREE *target);
/*   Clears any cached info in /target/ -- should be called any time a
 * node is going to be deleted from a tree, as this can make the
 * cached info incorrect.
 */

uint32_t
allocTree_Init(TREE *tree)
{
  static uint32_t inited = 0;

  if (!inited && (inited = 1) == 1 ) { /* run only once */
    tree_init();

    TREE_NIL->value = 1u; /* to match no possible value */
  
#ifndef TREE_STATIC_ALLOC
    freehead = 0;
#else /*TREE_STATIC_ALLOC*/
    {
      /* set up free list */
      int x;
      
      freehead = &static_treenodes[0]; /* the first node it our head */
      
      for (x = 0; x < NUM_TREENODES - 1; x++) {
	static_treenodes[x].parent = &static_treenodes[x+1];
	/* each node points to the next one. */
      }
      
      /* special case -- last node points to 0 */
      static_treenodes[x].parent = 0;
    }
#endif
  }
  tree->root = TREE_NIL; /* initialize the tree */

  _allocTree_clearCachedInfo(tree);
  return 0;
}

static void
_allocTree_clearCachedInfo(TREE *target)
{
  if (target) {
    target->lastInsert = TREE_NIL;
    target->lastRemove = TREE_NIL;
  }
}

uint32_t
allocTree_insertOIDs(TREE *tree, uint8_t type, OID oid, uint32_t count)
{
  register uint32_t curMap;
  register uint32_t newMask;
  
  TREENODE *theNode = TREE_NIL;

  OID treeKey = FLOOR2(oid, SB_OBJECTS_PER_TREENODE);
  uint32_t offset = MOD2(oid / EROS_OBJECTS_PER_FRAME, SB_FRAMES_PER_TREENODE);
  uint32_t objNum = oid & (EROS_OBJECTS_PER_FRAME - 1);

  if (treeKey == tree->lastInsert->value)
    /*  note that if tree->lastInsert == TREE_NIL, lastInsert->value
     * will never match treeKey, so tree_find will be run..
     */
    theNode = tree->lastInsert;
  else
    theNode = tree_find(tree->root,treeKey);

  if (theNode == TREE_NIL) {
    theNode = tree_newNode(treeKey);

    /* initialized the node -- now add it to the tree */
    tree->root = tree_insert(tree->root, theNode);
  }

  tree->lastInsert = theNode; /* store it for next time */
  
#ifndef TREE_NO_TYPES
#ifndef NDEBUT
  /* make sure the types match */
  if (theNode->body.type[offset] != SBOT_INVALID
      && (theNode->body.type[offset] != type
	  && theNode->body.map[offset] != 0u
         )) {
    debug_print_node(theNode);
    kpanic(KR_OSTREAM,
	     "Spacebank: allocTree_insert at 0x"DW_HEX" got type "
	     "conflict.  Offset %u says \n"
	     "           type %u, but caller says type %s!\n",
	     DW_HEX_ARG(treeKey),
	     offset,
	     (uint32_t)theNode->body.type[offset],
	     type_name(type)
	    );
    return 0; /* RETURN -- "error" */
  }
#endif
#endif

  DEBUG(alloc)
    if (!valid_type(type)) {
      kpanic(KR_OSTREAM,
	     "Spacebank: allocTree_insert(0x"DW_HEX") got sent "
	     "invalid type %u\n",
	     DW_HEX_ARG(oid),
	     type
	     );
      return 0; /* RETURN -- "error" */
    }

  /*  DEBUG(alloc)*/ if (1) 
    if (count + objNum > objects_per_frame[type]) {
      debug_print_node(theNode);
      kpanic(KR_OSTREAM,
	     "Spacebank: allocTree_insert(0x"DW_HEX",%s) got bad count\n"
	     "           (objNum (%d) + count (%d) > "
	                                 "objects_per_frame[] (%d)\n",
	     DW_HEX_ARG(oid),
	     type_name(type),
	     objNum,
	     count,
	     objects_per_frame[type]
	    );
      return 0; /* RETURN -- "error" */
    }

  curMap = theNode->body.map[offset]; /* get it from the node */

  /* muck with it */
#ifndef TREE_NO_TYPES
  if (curMap == 0u) {
    /* re-type the node */
    theNode->body.type[offset] = type;

    curMap = 0u; /* currently redundant -- might change later */
    /* could possibly be object_map_mask, but that makes tests slow */
  }
#endif

  newMask = (((1u << count) - 1) << objNum);

  /* test whether there are any ones where the mask is */
  if ( (curMap & newMask ) ) {
    debug_print_node(theNode);
    kpanic(KR_OSTREAM,
	   "Spacebank: allocTree_insert(0x"DW_HEX") "
	   "attempted to exceed type frame count limit\n"
	   "curMap: 0x%04x, new mask: %04x full map: %04x\n",
	   DW_HEX_ARG(oid),
	   curMap, newMask, objects_map_mask[type]);
  }

  /*  kprintf(KR_OSTREAM,
	  "SpaceBank:  AllocTree for 0x"DW_HEX" frame 0x%02x old "
	  "count %d new count %d\n",
	  DW_HEX_ARG(treeKey),
	  (uint32_t)offset,
	  curCount,
	  curCount + count);
   */

  /* FIXME: faster to do it directly? */
  
  curMap |= newMask;
  
  theNode->body.map[offset] = curMap; /* write it to
				       * theNode.
				       */

  return 1; /* RETURN -- "done" */
}

uint32_t
allocTree_checkForOID(TREE *tree, OID oid)
{
  TREENODE *theNode;

  OID treeKey = FLOOR2(oid, SB_OBJECTS_PER_TREENODE);
  uint32_t offset = MOD2(oid / EROS_OBJECTS_PER_FRAME, SB_FRAMES_PER_TREENODE);
  uint32_t objNum = oid & (EROS_OBJECTS_PER_FRAME - 1);

  if (treeKey == tree->lastRemove->value)
    /*  note that if tree->lastRemove == TREE_NIL, lastInsert->value
     * will never match treeKey, so tree_find will be run..
     */
    theNode = tree->lastRemove;
  else 
    theNode = tree_find(tree->root,treeKey);

  if (theNode == TREE_NIL) {
    return 0;	
  }
  tree->lastRemove = theNode;

  return (theNode->body.map[offset] & (1 << objNum));
}

uint32_t
allocTree_removeOID(TREE *tree, struct Bank *bank, uint8_t type, OID oid)
{
  TREENODE *theNode;

  OID treeKey = FLOOR2(oid, SB_OBJECTS_PER_TREENODE);
  uint32_t offset = MOD2(oid / EROS_OBJECTS_PER_FRAME, SB_FRAMES_PER_TREENODE);
  uint32_t objNum = oid & (EROS_OBJECTS_PER_FRAME - 1);

  register uint32_t curMap;