Initial commit of OpenSPARC T2 architecture model.

[OpenSPARC-T2-SAM] / sam-t2 / sam / system / blaze / include / symbols.h

/*
* ========== Copyright Header Begin ==========================================
* 
* OpenSPARC T2 Processor File: symbols.h
* Copyright (c) 2006 Sun Microsystems, Inc.  All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
* 
* The above named program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public
* License version 2 as published by the Free Software Foundation.
* 
* The above named 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 work; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
* 
* ========== Copyright Header End ============================================
*/
////////////////////////////////////////////////////////////
//
// File: symbols.h
//
// Symbol table submodule
//
// Copyright (C) 2006 Sun Microsystems, Inc.
// All rights reserved.
//
//
// Symbol table support.
//
// 1. maps address range to a symbol,
// lookup methods need to detect that address resides inside the range.
// more then one symbol could correspond to a particular address - 
// a label inside a routine or structure inside another structure. 
//
// 2. elf modules could be loaded at very low and very high virtual addresses;
// the size of address space coverage impacts the algorithm choice.
//
// 3. needs to provide a resonable performance for both searches : 
// by symbols name and by address.
//
// 4. kernel modules could have static symbols with the same name; 
// 


#ifndef _SYMBOLS_H
#define	_SYMBOLS_H

#include "types.h"
 

/////////////////////////////////////////////////////////
//
// Symbol class
//

class Symbol;

// For each symbol there is only one Symbol object, 
// but if that symbol cover a few pages - SymBase marker is used 
// for each page this symbol belongs to. 
// SymBase object points to original symbol object, 
// is is used to save some mem space when marking the range.
//
class SymBase
{
protected:
   SymBase    *m_origin; // prt to origin symbol 
   
   // symbols that have overlapped address range 
   // are kept in a link list
   SymBase    *m_link;   // prt to symbol if range overlaps
   
   
   // duplicate symbol reference for address range
   SymBase *dup()
   {
      SymBase *s = new SymBase (this);  
      return s;  
   }
   
   // attach symbol to list tail  
   void attach ( SymBase *sym )
   {
      SymBase* tail = this; 
      while(tail->m_link) 
         tail = tail->m_link; 
      tail->m_link = sym;     
   }
   
   
   SymBase (SymBase *o=NULL) { m_origin = o; m_link = NULL;}
   
   // base class better have a virtual destructor but 
   // virtual table takes additional mem space
   ~SymBase() {}
   
public: 
   SymBase* link() { return m_link; }
   
};



// Symbol class - maintain symbol information; 
// Each symbol is defined by name, starting address, 
// and size - number of bytes in address space covered by this symbol,
// e.g. routine, data structure and etc.  
// Only container object could add a new symbol objects to the table. 
class Symbol : public SymBase
{
   friend class SymTable;
   
public:
   
   enum 
   {
      NUCLEUS     = 0, 
      NO_CONTEXT  = ~uint32_t(1),
      ANY_CONTEXT = ~uint32_t(0)    
   };
   
private : 
   
   char*       m_name;    // symbol full name
   char*       m_sname;   // symbol name
   
   uint64_t    m_vaddr;   // virtual address for the the object
   uint64_t    m_size;    // object size in bytes  
   
   Symbol     *m_next;    // ptr to the next symbol in the hash table
   
   uint32_t    m_context; // 0 - kernel, -2 - hypervisor, <contextID> for user
   
   // private constructor - only container class can construct/destruct the symbol
   Symbol (char* mname=NULL, char* sname=NULL, uint64_t vaddr=~uint64_t(0), 
           uint64_t size =0, uint32_t context = NO_CONTEXT);
     
   // destructor
   ~Symbol (); 


public: // member functions

   char *   name  ()  { return m_name;  }
   uint64_t vaddr ()  { return m_vaddr; }
   uint64_t size  ()  { return m_size;  }
   Symbol*  next  ()  { return m_next;  }
   uint32_t context() { return m_context; }

};

//////////////////////////////////////////////////////////////
//
// Container class for all symbols
//
// - symbol addresses are mapped using nested address tables;
// - number of used address bits control how much of address space symbol table 
// will cover, if number of address bits for all tables sum up to 64 - 
// cover all address space. 
// - table size also control how much "meta data" space you are willing to 
// spend for address mapping;
// - for smaller number of table levels address search is faster but middle tables
// are bigger - a lot of memory is waisted to provide a faster search 
// - if symbols are loaded in a relatively small address range - 
// it requires a small number of middle tables.
// - the number of levels and size of tables  on each level is fixed 
// after construction phase.

// table indexes
//----------------------------------------------
// level 0 | level 1 |...|level n | offset n+1 |
//----------------------------------------------
//

class SymTable
{
public: 

   enum
   {
      // hash table size - should be power of 2
      SYM_TBL_SIZE = 1<<10,
      MAX_LEVEL = 6
   };


private:
   
   // hash table - quick search by name
   Symbol  *m_bucket [SYM_TBL_SIZE]; 
 
   // address tables - quick search by address; 
   // total number of tables is m_lev+1
   void**   m_tbl; 
   uint32_t m_lev;      // number of table levels minus one
 
   // arrays for each table level 
   uint32_t m_width[MAX_LEVEL+1]; // index width (number of bits)
   uint32_t m_size [MAX_LEVEL+1]; // table size   
   uint32_t m_sft  [MAX_LEVEL+1]; // index shift amount    
   uint64_t m_mask [MAX_LEVEL+1]; // index mask
   
   bool m_empty;        // true if there is no symbols
   
   
private:  // internal methods

   int sym_hash ( char *s)
   {
       uint64_t hash = 0;
   
       for(int i=0; i<strlen(s); i++)
       {
          hash = ( hash << 5 ) ^ s[i] ^ hash; 
       }
       return hash % SYM_TBL_SIZE;
   }

   // recursively delete all tables on deeper levels
   void delete_tbl ( void ** tbl, uint32_t level);
   
  
   // search symbol by specified address
   // return symbol poiner or NULL if not found
   SymBase* find ( uint64_t addr) 
   { 
      if ( this->is_empty() ) 
           return NULL; 
               
      void ** tbl = m_tbl; 
      void ** ptr = NULL;
      
       
      for ( int i=0; i<m_lev; i++)
      {
         ptr = tbl + ((addr>>m_sft[i]) & m_mask[i]);
         void **next = (void **)(*ptr); 
         if (next == NULL)
         {
            return NULL; 
         }
         tbl = next; 
      }
      
      // get a pointer from the leaf table
      return (SymBase *)tbl[(addr>>m_sft[m_lev]) & m_mask[m_lev]]; 
   }
   
   // get a pointer in multi level  addr tables;
   // nested tables are allocated if needed
   void **alloc( uint64_t addr );
   
   // recursively print symbols for all tables on deeper levels
   int print_tbl 
   ( 
      FILE *fp,         // output to the stream 
      void ** tbl,      // table pointer
      uint32_t level,   // table level
      uint64_t &total,  // symbol counter
      uint32_t context  // symbol context
   );

public:

   // constructor/destructor
   SymTable ( uint32_t levels = MAX_LEVEL+1, uint32_t *idx_width=NULL );
   ~SymTable ();
   
   // Member functions
   
   // check if container is empty
   bool is_empty () { return m_empty;  }

   // find() methods combines functionality of search and iterator 
   // - use it with start=NULL to find a head of the list;
   // to traverse the list call find() method again using start 
   // pointing to the previous symbol. 
  
   // search for address of symbol specified by symbol name;
   // return pointer to symbol if found; 0 otherwise;
   //
   // different modules could have static variables (symbols) with 
   // the same name - you will get a list of the symbols with 
   // same name that reside in different modules, 
   // you need to traverse the list to get the symbols; 
   Symbol * find 
   ( 
      char*   name,         // symbol name 
      Symbol* start=NULL    // start search from this one
   );

   // find symbol specified by address ;
   // return 1 if found, 0 otherwise;
   // if you make a search by address - it return a list of symbols 
   // that resides at that address. Symbols address ranges could overlap. 
   // You need to traverse that list and extract symbol names. 
   SymBase* find
   ( 
      uint64_t addr,       // address used to lookup the symbol
      SymBase* start       // start from this symbol 
   );
  
   // find and output address for all symbols specified by name;
   // return 1 if found, 0 otherwise;
   int fputs 
   ( 
      char     *name,   // name used to lookup the symbol
      uint32_t context, // symbol context
      FILE     *fp      // output symbol name to stream if found
   );
   
  
   // find and output full symbol name by specified address ;
   // return 1 if found, 0 otherwise;
   int fputs 
   ( 
      uint64_t addr,     // address used to lookup the symbol
      uint32_t context,  // symbol context
      FILE     *fp       // output symbol name to stream if found
   );
   

   // add a new symbol to the symbol table
   // return 1 if added, 0 otherwise
   int add
   (
      char * mname,           // module name
      char * name,            // symbol name   
      uint64_t vaddr,         // starting address
      uint64_t size=0,       // range covered
      uint32_t context=Symbol::NUCLEUS // symbol context
   );
  
   // print all symbols 
   // from low to upper addresses
   void print ( char *filename, uint32_t context );
    
   // print all symbols without any order - 
   // hash table order
   int hprint ( char *filename, uint32_t context );
 
};









     
#endif  //  _SYMBOLS_H