/*-------------------------------------------------------------------------
** Name: adlookup.cpp
**
** Title: Address Lookup Routines
**
** Purpose:
**  Supplies the routines defined in symblsvr.h for looking up a symbol by
**  its address.  "address" is an abstract term which can be:
**      physical address
**      offset from stack frame context
**      register index for register variables
**
** Status: PRELIMINARY |
**
** $Log:   S:/tbird/arcppc/symbol/adlookup.cpv  $
** 
**    Rev 1.3   31 Mar 1998 12:00:08   Winky
** No change.
** 
**    Rev 1.2   12 Mar 1997 14:47:24   hera
** No change.
** 
**    Rev 1.1   03 Mar 1997 15:47:10   hera
** 
**    Rev 1.0   07 Sep 1995 11:16:28   gene
** Initial revision.
** 
**    Rev 1.16   28 Feb 1994 15:46:54   marilyn
** Removed references to ADDR_LOGICAL.
** 
**    Rev 1.15   27 Apr 1993 16:56:02   nghia
** Fixed bug: Symbol server failed to search for symbol when load Sierra 
** file with mergeSections is ON.  This problem occurred when section bases are
** overlapped and the cacheAddrLookupBaseOffset is the last base on the list.
** According to Bruce, it should continue at the top of the list and search 
** again.  
** 
**    Rev 1.14   18 Dec 1992 18:20:14   brucea
** Cleanup: removed localRetCode, took out (U8) cast for .symType & 0xF
** 
**    Rev 1.13   12 Aug 1992 10:07:56   brucea
** Bug fix in SymMapLinenum2FuncOrBlock: was not returning correct outputSymbol;
**    now returns outSymbol rather than funcDescriptor
** 
** 
**    Rev 1.12   06 Aug 1992 10:17:32   brucea
** Changed access to .typeIndex.symType to use &0xF
** 
**    Rev 1.11   20 Jul 1992 16:18:10   brucea
** Changed: search for parent function now skips over blocks until function found
** Cosmetic changes
** 
**    Rev 1.10   19 Jul 1992 22:06:26   brucea
** Fixed bug: address lookup wasn't returning correct symbol type
** 
**    Rev 1.9   10 Jul 1992 19:03:04   brucea
** Added: check at beginning of SymMapAddr2Symbol for whether there are any bases
**    which indirectly indicates if any symbols are loaded or not.  This was put
**    in for C&T because they use virtual addresses
** 
**    Rev 1.8   15 Jun 1992 15:34:24   brucea
** Commented out: return localRetCode because of patch - should be resolved
** 
**    Rev 1.7   20 Apr 1992 08:44:28   brucea
** Added: AdlookupREsetCacheVars to fix PPR5473
** 
**    Rev 1.6   27 Feb 1992 22:48:34   brucea
** Added: Gross patch to SymMapAddr2Symbol to force an address search to continue
**        to other based even though it was in the range of another base and yet
**        the symbol was not found.  This temporarily patches the problem that
**        the ????STACKTOP public var is being added to the variable base and
**        setting the minimum address to cover all the code addresses.  This
**        needs to be fixed in the loader.
** 
**    Rev 1.5   11 Dec 1991 17:06:10   brucea
** Removed MAX_BASE_INDEX_SIZE
** 
**    Rev 1.4   11 Dec 1991 16:18:52   brucea
** Added tests for return value for all addr.h Adr... calls
** Added test for selector not a valid base index
** 
**    Rev 1.3   09 Dec 1991 17:28:44   brucea
** Changes follow:

** In SymMapAddr2Symbol, added SYM_BLOCK to allowable symbol type return in
**   the funcDescriptor slot.
** Implemented SymMapLinenum2FuncOrBlock
** 
**    Rev 1.2   29 Nov 1991 20:01:28   brucea
** changed LOGICAL_ADDR_TYPE to DESCRIPTOR
** NULL to NULL_SYMBOL
** Added calls to addr.h routines: AdrGetAddrType,
**   AdrGetLdtSelector, AdrGetAddrOffset
** Process the address different to support selector:offset or
**   logical addresses
** Changed logicalAddr to OffsetAddr
** 
**    Rev 1.1   18 Nov 1991 15:34:38   brucea
** Changed first parameter to SymMapAddr2Symbol to LOGICAL_ADDR_TYPE
** Changed code with accessed structure; this code will change with
**    new addr.h
** 
**    Rev 1.0   01 Nov 1991 11:04:12   brucea
** Initial revision.
** 
** $Header:   S:/tbird/arcppc/symbol/adlookup.cpv   1.3   31 Mar 1998 12:00:08   Winky  $
**
** Copyright (C) 1991 Microtek International.  All rights reserved.
**
**------------------------------------------------------------------------*/

                       /****************************
                        *                          *
                        *       INCLUDE FILES      *
                        *                          *
                        ****************************/
#ifndef _ADDR_
#include "addr.h"
#endif

#ifndef _SYMBLSVR_
#include "symblsvr.h"
#endif

#ifndef _BASETBL_
#include "basetbl.h"
#endif

#ifndef _BYADRTBL_
#include "byadrtbl.h"
#endif

                       /****************************
                        *                          *
                        *        EXTERNALS         *
                        *                          *
                        ****************************/

extern BaseIndexTable bit; // base index table
extern MemPool st;         // symbol table

//--------------------------------------------------------------------------
// AdlookupResetCacheVars
//--------------------------------------------------------------------------
VOID AdlookupResetCacheVars(VOID);

                        /***************************
                        *                          *
                        *      LOCAL STATICS       *
                        *                          *
                        ****************************/

PRIVATE TABLE_OFFSET cachedAddrLookupBaseOffset;

                       /****************************
                        *                          *
                        *     EXECUTABLE CODE      *
                        *                          *
                        ****************************/


//--------------------------------------------------------------------------
// AdlookupResetCacheVars
//--------------------------------------------------------------------------
VOID AdlookupResetCacheVars(VOID) {

   cachedAddrLookupBaseOffset = NULL_SYMBOL;
}


//--------------------------------------------------------------------------
// SymMapAddr2Symbol
//
// Purpose:
//    Map an abstract address to a symbol that contains it.  It returns
//    the symbol with a starting address closest to the requested
//    address.  It also returns its type and parent information.  This
//    routine returns a symbol descriptor, then the caller
//    makes another call to get specific information about the symbol.
//
// Input parameters;
//    addr: abstract address to be looked up.
//
// Output parameters:
//    memoryClass:
//       what basic symbol class; to be completed with hints when they are
//       implemented.  If an address match is not found, the memoryClass
//       value gives the caller more general information about the address
//    symbolType: basic symbol type - part of every symbol
//    offset:
//        distance the requested address is from the function's start address
//    outputSymbol:
//        descriptor to the symbol found that is closest to the requested addr
//    funcDescriptor: offset to parent function; can be a function or unnamed
//        block; NULL if none exists
//    moduleDescriptor: offset to parent module; NULL if none exists
//
// Error:
//    Error reported if abstract address cannot be translated to an address
//    that can be looked up
//    Error reported if address not found
//
// Pseudo-code:
//    if address is logical, find base that holds requested address
//       (must convert to offset address before comparing to base address
//       range.  Offset address = logical address - base address)
//    if address is SELECTOR_OFFSET, the selector portion is the base index
//       which is looked up in the base index table to get the offset to
//       the base itself.  The offset component of the structure is then the
//       logical address to look up directly - no subtraction.
//    Start address search with cached base index lookup.  If address doesn't
//       match base range...
//    Beginning with the first base loaded, walk the base objects that are
//       singly linked.  Find one that contains the address requested.  If
//       none, fill in the <memoryClass> with the appropriate type.
//    When a base is found that contains the requested address, do a binary
//       search on the ByAddressTable to find a symbol that contains the
//       requested address.  It is possible not to find the address because
//       the end address may not include the address requested.
//       Return error ER_ADDRESS_NOT_FOUND if this occurs.
//    Search down in the table for an address range whose start address is
//       closer to the requested address.  Stop when it exceeds requested addr
//    Initialize return descriptors to NULL.
//    Access symbol.  Fill in <symbolType>, <offset>, <memoryClass>, and
//       <outputSymbol>. If any parent is a function, fill in
//       <funcDescriptor>.  If any parent is a module (may be a public which
//       points to root) fill in <moduleDescriptor>.
//------------------------------------------------------------------------
RETCODE EXPORT
SymMapAddr2Symbol(DESCRIPTOR     addrDesc,
                  MEM_ADDR_CLASS *memoryClass,
                  SYM_TYPE_TYPE  *symbolType,
                  U32            *offset,
                  SYM_DESCRIPTOR *outputSymbol,
                  SYM_DESCRIPTOR *funcDescriptor,
                  SYM_DESCRIPTOR *moduleDescriptor)  {

   RETCODE           retCode;
   TABLE_OFFSET      tableOffset, byAddrOffset;
   BaseSymbol        *basePtr;       // ptr to Base object
   ByAddressTable    *byAddrPtr;     // ptr to by-address table object
   COMMON_SYMBOL_HEADER *symPtr;     // ptr to a symbol common header
   OFFSET_ADDR_TYPE  offsetAddr;
   U32               requestedAddr;
   SYMBOL_INFO_TYPE  symbolInfo;
   ADDR_TYPE         addrType;
   U32               ldt;            // holds ldt selector
   BOOLEAN           useCacheBaseLookup;

   // check for symbols loaded or not
   if (NULL_SYMBOL == (tableOffset = bit.GetRootBaseSymbolOffset())) {
      return ER_ADDRESS_NOT_FOUND;
   }

   // initialize the return parameters to the status of the address NOT FOUND
   *memoryClass = UNDEFINED_ADDR;
   *symbolType =  SYM_UNDEFINED;
   *offset = 0L;
   *outputSymbol = *funcDescriptor = *moduleDescriptor = NULL_SYMBOL;

   // check the type of address request
   // get address type
   if (SUCCESS != (retCode = AdrGetAddrType(addrDesc, &addrType)))
      return retCode;

//@@@ does ADDR_SEGSEL_TYPE have to be checked here first???
   switch (addrType) {
      case ADDR_VIRTUAL: {
         // check for valid selector
         // get address selector
         if (SUCCESS != (retCode = AdrGetLdtSelector(addrDesc, &ldt)))
            return retCode;

         // check for ldt out of bounds of allowed base index
         if (ldt > MAX_BASE_INDEX_SIZE)
            return ER_INDEX_OUT_OF_BOUNDS;
         // get offset
         if ((retCode = bit.GetOffset(ldt, tableOffset))
             != SUCCESS)  return retCode;
         basePtr = (BaseSymbol *)st.GetHugeDataPtr(tableOffset);

         //get address offset and put into <offsetAddr>
         if (SUCCESS != (retCode = AdrGetAddrOffset(addrDesc, &offsetAddr)))
            return retCode;
         break;
         }

      case ADDR_LINEAR:  {
         // code type is logical or linear; must extract base address
         // and subtract from requested logical address to look up
         // the offset

         if (SUCCESS !=(retCode = AdrGetAddrOffset(addrDesc, &requestedAddr)))
            return retCode;
         // start with last used base offset
         if (cachedAddrLookupBaseOffset != NULL_SYMBOL)  {
            basePtr =
               (BaseSymbol *)st.GetHugeDataPtr(cachedAddrLookupBaseOffset);
            useCacheBaseLookup = TRUE;
            // subtract off base address to reduce to offset address
            offsetAddr = requestedAddr - (basePtr->GetBaseAddress());
            if ((basePtr -> CompareAddrVars(offsetAddr)))  {
               // patch code?  !!!
               tableOffset = bit.GetRootBaseSymbolOffset();
               break;  // jump out of switch and move to next stage

            } // end of if (basePtr)
         } // end of if (cachedAddrLookupBaseOffset)

         // not found with cached offset or cached offset is NULL_SYMBOL
         // must walk the BaseSymbol linked list to search for included
         // address; start with the root and follow links

         while (TRUE) {
            // must be here because of while loop; checks for end of
            // linked list of base table pointers
searchTop:  if (tableOffset == NULL_SYMBOL) {
               // insert HINT lookup and set memoryClass accordingly
               // !!! when HINTS are implemented
               // leave if no BaseSymbols loaded or no address range match
               return ER_ADDRESS_NOT_FOUND;
            }
            basePtr = (BaseSymbol *)st.GetHugeDataPtr(tableOffset);
            // subtract off base address to reduce to offset address
            offsetAddr = requestedAddr - (basePtr -> GetBaseAddress());
            if ((basePtr -> CompareAddrVars(offsetAddr)))  {
               break;  // match found
            }
searchAgain:
            // get link to next base object
            tableOffset = basePtr->GetNextBaseOffset();
         }  // end of while
         // save found base
         cachedAddrLookupBaseOffset = tableOffset;
         break;
      } // end of case LOGICAL, LINEAR

      default: return ER_INVALID_ADDRESS_TYPE;
   } // end of switch

   // basePtr points to base containing address
   // offsetAddr holds requested address in offset form

   // do a binary search on by-address table
   byAddrOffset = basePtr->GetByAddressTableOffset();
   byAddrPtr = (ByAddressTable *)st.GetHugeDataPtr(byAddrOffset);
   if (GOOD != byAddrPtr -> SearchForAddr(offsetAddr, symbolInfo)) {
      // insert HINT lookup and set memoryClass accordingly when HINTS are
      // implemented
      // Continue searching the base tables from top until none left
      if (useCacheBaseLookup) {
         useCacheBaseLookup = FALSE;  // Reset flag to avoid loop forever
         tableOffset = bit.GetRootBaseSymbolOffset(); // get the first base
         goto searchTop;
      }
      goto searchAgain;
   }
   
   // save information retrieved
   *offset = symbolInfo.delta;
   *outputSymbol = tableOffset = symbolInfo.symbolOffset;
   symPtr = (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(tableOffset);
   // must cast to get unsigned value for switch statement below
   *symbolType = symPtr->typeIndex.symType & 0xF;
   // set <memoryClass>;  previously set to UNDEFINED_ADDR
   // default to code and change to data if the type is a data type
   switch (*symbolType) {
      default:
         *memoryClass = CODE_ADDR;
         break;

      case SYM_GLOBAL_VAR:
      case SYM_LOCAL_VAR:
      case SYM_USER_DEFINED_VAR:
      case SYM_PUBLIC_VAR:
         *memoryClass = DATA_ADDR;
         break;
   }

   // fill in the funcDescriptor and moduleDescriptor fields; must follow the
   // parent symbol linkages

   SYM_TYPE_TYPE     tmpType;
   BOOLEAN           funcFound = FALSE;
   while (TRUE) {
      if (tableOffset == NULL_SYMBOL)  return SUCCESS;
      // get symbol pointer, then its type
      symPtr = (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(tableOffset);
      tmpType = (symPtr->typeIndex.symType) & 0xF;
      switch(tmpType) {
         case SYM_ROOT:
              SYM_UNDEFINED:
                 return SUCCESS;

         case SYM_MODULE:
            *moduleDescriptor = tableOffset;
            return SUCCESS;

         case SYM_BLOCK:
            break;      // don't stop at block; find function parent

         case SYM_FUNCTION:  // match function or block
            if (!funcFound) {
               *funcDescriptor = tableOffset;  // found parent function
               funcFound = TRUE;  // once found, ignore any other higher
                                  // level nested functions
               break;
            }
      } // end of switch
      tableOffset = symPtr -> symParentOffset;
   } // end of while loop
}  // end of SymMapAddr2Symbol


//--------------------------------------------------------------------------
// SymMapLinenum2FuncOrBlock
//
// Purpose:
//    Given a line number and its context, look up the most local function or
//    block that contains it.  Return the type (function or block), and a
//    descriptor to it.
//
// Error:
//    Reports error if:
//        moduleName not found
//        linenum not in module context
//        type returned is not a function or block
//--------------------------------------------------------------------------
RETCODE EXPORT
SymMapLinenum2FuncOrBlock(SYM_DESCRIPTOR module,
                          LINENUM_TYPE   linenum,
                          SYM_TYPE_TYPE  *symType,
                          SYM_DESCRIPTOR *outputSymbol)  {

   RETCODE            retCode;
   DESCRIPTOR         addrDesc;
   LINENUM_TYPE       actualLinenum;
   COLUMN_TYPE        actualColumn;
   LINENUM_DESCRIPTOR nextIndex;
   

   if (SUCCESS != (retCode = AdrCreateAddress(&addrDesc)))
      return retCode;

   // convert module and linenum to address
   if (SUCCESS != (retCode = SymGetLinenum(module,
                                           linenum,
                                           addrDesc,
                                           &actualLinenum,
                                           &actualColumn,
                                           &nextIndex)))
      return retCode;

   MEM_ADDR_CLASS memoryClass;
   U32            offset;
   SYM_DESCRIPTOR outSymbol;
   SYM_DESCRIPTOR funcDescriptor;
   SYM_DESCRIPTOR moduleDescriptor;

   // look up address for function or block that contains it
   if (SUCCESS != (retCode = SymMapAddr2Symbol(addrDesc,
                                               &memoryClass,
                                               symType,     //func input param
                                               &offset,
                                               &outSymbol,
                                               &funcDescriptor,
                                               &moduleDescriptor)))
      return retCode;

   *outputSymbol = outSymbol;  // copy the lowest-level descriptor to output
   // check for valid function or block type
   if (funcDescriptor == NULL_SYMBOL)
      return ER_SYMBOL_NOT_FOUND;

   return AdrDestroyAddress(addrDesc);
}  // end of SymMapLinenum2FuncOrBlock

/******************************** E O F ****************************/
