* ========== 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 ============================================
////////////////////////////////////////////////////////////
// Symbol table submodule
// Copyright (C) 2006 Sun Microsystems, Inc.
// 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;
/////////////////////////////////////////////////////////
// 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.
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
*s
= new SymBase (this);
// attach symbol to list tail
void attach ( SymBase
*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
* 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
NO_CONTEXT
= ~uint32_t(1),
ANY_CONTEXT
= ~uint32_t(0)
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
);
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.
//----------------------------------------------
// level 0 | level 1 |...|level n | offset n+1 |
//----------------------------------------------
// hash table size - should be power of 2
// 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
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
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
)
for ( int i
=0; i
<m_lev
; i
++)
ptr
= tbl
+ ((addr
>>m_sft
[i
]) & m_mask
[i
]);
void **next
= (void **)(*ptr
);
// 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
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
// constructor/destructor
SymTable ( uint32_t levels
= MAX_LEVEL
+1, uint32_t *idx_width
=NULL
);
// 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;
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.
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;
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;
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
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
// from low to upper addresses
void print ( char *filename
, uint32_t context
);
// print all symbols without any order -
int hprint ( char *filename
, uint32_t context
);