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