timing.c

一个用在mips体系结构中的操作系统

   thread = ThreadLookup(tree, threadName);
   if (!thread) {
      thread = ThreadCreate(tree, threadName, startState, numStartStates);
      CPUPrint("TIMING: CPUNum %d created thread %s\n", CPUNum, threadName); 
   } else {
      ASSERT(!thread->active);
      /* If we switch back to an existing thread, it should have been
         in the desched state */
      ThreadEndPhase(tree, thread, "DESCHED");
   }

   thread->active = 1;
   tree->currentThread[CPUNum] = thread;

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: Switch to thread %s\n", thread->name);
   TimingStackList(thread->stack);
#endif

   return TCL_OK;
}

/*****************************************************************
 * CmdTerminate
 *
 * Thread is finished, cleanup its stack.
 ****************************************************************/
static int 
CmdTerminate(Tcl_Interp *interp, int argc, char *argv[])
{
   TimingTree *tree;
   TimingThread *thread;
   char *treeName;
   char *threadName;
   
   treeName  = argv[2];
   threadName = argv[3];
   
   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }
   
   thread = tree->currentThread[CPUNum];

   if (strcmp(thread->name, threadName)) {
      Tcl_AppendResult(interp, "\"", threadName, "\" is not current thread", NULL);
      return TCL_ERROR;
   }

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: Exit thread %s\n", thread->name);
   TimingStackList(thread->stack);
#endif
   
   ThreadExit(tree, tree->currentThread[CPUNum]);

   return TCL_OK;
}

/*****************************************************************
 * CmdDump
 *****************************************************************/
static int 
CmdDump(Tcl_Interp *interp, int argc, char *argv[])
{
   TimingTree  *tree;
   char *treeName;

   if ((argc != 3)) {
      Tcl_AppendResult(interp, "wrong # args: should be \"",
                       argv[0], timingCmds[5].usage, "\"", NULL);
      return TCL_ERROR;
   }

   treeName  = argv[2];
   
   if ((tree = TreeLookup(treeName)) == NULL) {
      Tcl_AppendResult(interp, "no tree named \"", treeName, "\"", NULL);
      return TCL_ERROR;
   }

   TreeDump(tree);

   return TCL_OK;
}

/*****************************************************************
 * CmdFields
 *****************************************************************/
static int 
CmdFields(Tcl_Interp *interp, int argc, char *argv[])
{

   if ((argc != 2)) {
      Tcl_AppendResult(interp, "wrong # args: should be \"",
                       argv[0], timingCmds[8].usage, "\"", NULL);
      return TCL_ERROR;
   }

   Tcl_AppendResult(TCLInterp,"TIMING: ", NULL);
   StatRecordDumpFields();

   return TCL_OK;
}

/****************************************************************
 * TreeCreate 
 *
 ****************************************************************/
TimingTree *
TreeCreate(char *treeName)
{
   TimingTree *tree;
   TimingNode *node;
   int new = 0;
   Tcl_HashEntry *entry = Tcl_CreateHashEntry(&trees, treeName, &new);
   char rootName[24];
   
   if (!new) {
      return NULL;
   }

   tree = (TimingTree *)ZMALLOC(sizeof(TimingTree),"TimingTree");

   Tcl_InitHashTable(&(tree->threads), TCL_STRING_KEYS);

   tree->name = Tcl_GetHashKey(&trees, entry);
   tree->numThreads = 0;
   tree->currentThread[0] = NULL;
   tree->selector = StatRecordNewSwitch("timing");

   CPUPrint("TIMING: new tree %s\n", treeName);
#ifdef notdef
   CPUPrint("TIMING: ");
   StatRecordDumpFields();
#endif
   
   sprintf(rootName, "ROOT");

   node = NodeFind(NULL, rootName);
   tree->root = node;

   Tcl_SetHashValue(entry, tree);

   return tree;
}

/*****************************************************************
 * TreeLookup
 *
 *****************************************************************/
TimingTree *
TreeLookup(char *treeName)
{
   TimingTree *tree = NULL;
   Tcl_HashEntry *entry = Tcl_FindHashEntry(&trees, treeName);
   
   if (entry) {
      tree = Tcl_GetHashValue(entry);
      ASSERT(tree);
   }
   return tree;
}

/*****************************************************************
 * TreeDump
 *****************************************************************/
static void DumpTree(char *name, TimingNode *node, char *parentName, 
                     int depth);

static void
TreeDump(TimingTree *tree)
{
   ASSERT(tree != NULL);
   ASSERT(tree->root);
   DumpTree(tree->name, tree->root, tree->root->name, 0);
   Tcl_AppendResult(TCLInterp, "TIMING: tree ", tree->name, " END\n", NULL);
}

static void
DumpTree(char *name, TimingNode *node, char *parentName, int depth)
{
   char buf[32];
   if (!node)  return;

   sprintf(buf,"%d",depth);
   Tcl_AppendResult(TCLInterp, "TIMING: tree ",name," depth ", buf, 
                    " name ", node->name, " parent ", parentName, " ", NULL);
   StatsList(node->stats, "TIMING: ");
   StatRecordDumpBucket(node->name, node->bucket, "TIMING: ");

   DumpTree(name, node->child, node->name, depth+1);
   DumpTree(name, node->sibling, parentName, depth);
}


/*****************************************************************
 * ThreadCreate
 *
 *****************************************************************/
TimingThread *
ThreadCreate(TimingTree *tree, char *threadName, char **startStates,
             int numStartStates)
{
   TimingThread *thread;
   TimingNode *node, *node2;
   int i;
   int new = 0;

   Tcl_HashEntry *entry = Tcl_CreateHashEntry(&(tree->threads), 
                                              threadName, &new);
   ASSERT(new);

   thread = (TimingThread *)ZMALLOC(sizeof(TimingThread),"TimingThread");

   ASSERT(thread);

   thread->name  = Tcl_GetHashKey(&(tree->threads), entry);
   thread->stack = StackInit();

   StackPush(thread->stack, PTR_TO_UINT64(tree->root));
   StackPush(thread->stack, (StackItem)CPUVec.CycleCount(CPUNum));
   StackPush(thread->stack, (StackItem)0);

   node = tree->root;
   for (i=0; i<numStartStates; i++) {
      node2 = NodeFind(node, startStates[i]);
      ASSERT(node2);
      StackPush(thread->stack, PTR_TO_UINT64(node2));
      StackPush(thread->stack, (StackItem)CPUVec.CycleCount(CPUNum));
      StackPush(thread->stack, (StackItem)0);
      node = node2;
   }

   thread->compStart = CPUVec.CycleCount(CPUNum);
   thread->active = 1;
   
   Tcl_SetHashValue(entry, thread);

   StatRecordSetSwitch(tree->selector, CPUNum, node->bucket);
   thread->compStart = CPUVec.CycleCount(CPUNum);

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: Create %s thread %s\n", tree->name, threadName); 
   for (i=numStartStates-1; i>=0; i--) {
      CPUPrint("\t[%d] %s\n", i, startStates[i]);
   }
#endif
   
   return thread;
}

/*****************************************************************
 * ThreadLookup
 *****************************************************************/
TimingThread *
ThreadLookup(TimingTree *tree, char *threadName)
{
   TimingThread *thread = NULL;
   Tcl_HashEntry *entry = Tcl_FindHashEntry(&(tree->threads), threadName);
   
   if (entry) {
      thread = Tcl_GetHashValue(entry);
   } else {
      thread = NULL;
   }
   
   return thread;
}

/*****************************************************************
 * ThreadExit
 *****************************************************************/
static void
ThreadExit(TimingTree *tree, TimingThread *thread)
{  
   TimingNode *node = NULL;
   TimingNode *next = NULL;
   uint64 compTotal;
   uint64 compTime;   
   uint64 startTime;
   
   ASSERT(thread != NULL);

   if (!StackEmpty(thread->stack)) {
      if (thread->compStart) {
         compTime = (uint64)StackPop(thread->stack);
         StackPush(thread->stack,
                   (StackItem)(compTime + (CPUVec.CycleCount(CPUNum)
                                           - thread->compStart)));
      }      
      
      while (!StackEmpty(thread->stack)) {
         compTotal = (uint64)StackPop(thread->stack);
         startTime = (uint64)StackPop(thread->stack);
         node =  UINT64_TO_PTR(StackPop(thread->stack));
         StatsEntry(node->stats, CPUVec.CycleCount(CPUNum) - startTime, compTotal);
         if (node->mutable) {
            ASSERT(!node->sibling);
            next = UINT64_TO_PTR(StackIndex(thread->stack, 2));
            ASSERT(next);
            NodeZip(tree, node, NodeFind(next, node->name));
         }
      }
      
      ASSERT(!node || !strncmp(node->name, "ROOT", 4));
   }
}

/*****************************************************************
 * ThreadStartPhase
 *****************************************************************/
static int
ThreadStartPhase(TimingTree *tree, TimingThread *thread, char *phaseName, int mutable)
{
   TimingNode *parent;
   TimingNode *node;
   uint64 compTime;

   parent = UINT64_TO_PTR(StackIndex(thread->stack, 2));
   ASSERT(parent);
   
   compTime = (uint64)StackPop(thread->stack);
   StackPush(thread->stack, (StackItem)(compTime + (CPUVec.CycleCount(CPUNum)
                                       - thread->compStart)));

   if (mutable) {
      node = NodeCreate(phaseName);
      node->sibling = NULL;
      node->mutable = 1;
   } else {
      node = NodeFind(parent, phaseName);
      ASSERT(!node->mutable);
   }
   
   /* node for node */
   if (StackPush(thread->stack, PTR_TO_UINT64(node))) {
      return TCL_ERROR;
   }
   
   /* cycle count for latency */
   if (StackPush(thread->stack, (StackItem)CPUVec.CycleCount(CPUNum))) {
      (void) StackPop(thread->stack);
      return TCL_ERROR;
   }
   
   /* sum for computation */
   if (StackPush(thread->stack, (StackItem)0)) {
      (void) StackPop(thread->stack);
      (void) StackPop(thread->stack);
      return TCL_ERROR;
   }

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: Start %s on thread %s at %lld %#llx\n", 
            node->name, thread->name, CPUVec.CycleCount(CPUNum),
            CPUVec.CurrentPC(CPUNum));
   TimingStackList(thread->stack);
#endif

   StatRecordSetSwitch(tree->selector, CPUNum, node->bucket);
   thread->compStart = CPUVec.CycleCount(CPUNum);
   
   return TCL_OK;
}

/*****************************************************************
 * ThreadEndPhase
 *****************************************************************/
static void
ThreadEndPhase(TimingTree *tree, TimingThread *thread, char *phaseName)
{
   TimingNode *node;
   TimingNode *next;
   uint64 comp;
   uint64 compTotal;
   uint64 latTotal;

   node =  UINT64_TO_PTR(StackIndex(thread->stack, 2));
   ASSERT(node);

   if (strcmp(phaseName, node->name)) {
      CPUWarning("TIMING: %d tree %s thread %s ending \"%s\" but in \"%\"\n",
                 CPUNum, tree->name, thread->name, phaseName, node->name);
      TimingStackList(thread->stack);
      return;
   }

   comp = (CPUVec.CycleCount(CPUNum) - thread->compStart);
   /* on embra we have the problem the cycle count may go backwards */
   comp = ((int64)comp > 0) ? comp : 0;
   compTotal = (uint64)StackPop(thread->stack) + comp;

   latTotal = CPUVec.CycleCount(CPUNum) - (uint64)StackPop(thread->stack);
   /* on embra we have the problem the cycle count may go backwards */
   latTotal = ((int64)latTotal > 0) ? latTotal : 0;
   
   node = UINT64_TO_PTR(StackPop(thread->stack));
   ASSERT(node);

   StatsEntry(node->stats, latTotal, compTotal);

   next = UINT64_TO_PTR(StackIndex(thread->stack, 2));

   if (!next) {
      CPUError("TIMING: CPU %d: Popping ROOT???\n", CPUNum);  
   }

   if (node->mutable) {
      ASSERT(!node->sibling);
      NodeZip(tree, node, NodeFind(next, node->name));
   }

#ifdef TIMING_DEBUG
   CPUPrint("TIMING: End %s on thread %s at %lld %#llx\n", 
            node->name, thread->name, CPUVec.CycleCount(CPUNum),
            CPUVec.CurrentPC(CPUNum));
   TimingStackList(thread->stack);
#endif

   StatRecordSetSwitch(tree->selector, CPUNum, next->bucket); 
   thread->compStart = CPUVec.CycleCount(CPUNum);
}

/*****************************************************************
 * NodeCreate
 *****************************************************************/
static TimingNode *
NodeCreate(char *name)
{
   TimingNode *n;

   n = (TimingNode *)ZMALLOC(sizeof(TimingNode),"TimingNode");

   n->name = SaveString(name);
   n->bucket = StatRecordNewBucket();
   n->stats = StatsCreate(0, 0, 0); 
   n->child = NULL;
   n->sibling = NULL;
   n->mutable = 0;
   
   return n;
}

/*****************************************************************
 * NodeFind
 *****************************************************************/
static TimingNode *
NodeFind(TimingNode *parent, char *name)
{
   TimingNode *n;
   
   if (!parent) {
      return NodeCreate(name);
   }

   n = parent->child;
   
   while (n) {
      if (!strcmp(n->name, name)) {
         return n;
      } else {
         n = n->sibling;
      }
   }
   
   n =  NodeCreate(name);
   n->sibling = parent->child;
   parent->child = n;

   return n;
}

/*****************************************************************
 * NodeFind
 *****************************************************************/
static void
NodeZip(TimingTree *tree, TimingNode *src, TimingNode *dest)
{
   TimingNode *child;
   TimingNode *kill;
   
   ASSERT(src);
   ASSERT(dest);

   StatRecordTransferBucket(tree->selector, src->bucket, dest->bucket);
   StatsTransfer(src->stats, dest->stats);
   
   child = src->child;
   while (child) {
      kill = child;
      child = child->sibling;
      NodeZip(tree, kill, NodeFind(dest, kill->name));
   }

   free(src->name);
   StatRecordFreeBucket(src->bucket);
   StatsDestroy(src->stats);
   free(src);
}

/*****************************************************************
 * TimingStackList - Helpful debugging routine
 *****************************************************************/
void
TimingStackList(Stack *stack) 
{
   TimingNode *node;
   int i = stack->head;
   int j;

   while (i >= 0) {
      node =  UINT64_TO_PTR((stack->element[i-2]));
      j = (int)stack->element[i-1];
      CPUPrint("\t[%2d] = %12s started at %12d", i/3, node->name, j);
      if (node->mutable) {
         CPUPrint(" mutable");
      }
      CPUPrint("\n");
      i -= 3;
   }
}

/*****************************************************************
 * Stack overflow -- print history of nodes for debugging
 *****************************************************************/

static void
OverflowDebug(Tcl_Interp *interp, TimingThread *thread)
{
  int i;

  Tcl_AppendResult(interp, "stack overflow for ", thread->name, ":", NULL);
  for (i = 2; ; i += 3) {
    TimingNode *node = (TimingNode*) StackIndex(thread->stack, i);
    if (!node) break;
    Tcl_AppendResult(interp, " ", node->name, NULL);
  }
}