{-# LANGUAGE OverloadedStrings #-}
# LANGUAGE ScopedTypeVariables #
# LANGUAGE StandaloneDeriving #

  | Functionality for computing the names and addresses of PLT stub functions
-- in a dynamically linked ELF binary.
--
-- Note that the API in this library is somewhat experimental, and as we further
-- develop the underlying approach (see @Note [Dynamic lookup scope]@), we may
-- need to change the API accordingly.
module Data.Macaw.Memory.ElfLoader.DynamicDependencies
  ( loadDynamicDependencies
  , parseDynNeeded
  , DynamicLoadingError(..)
  ) where

import qualified Control.Exception as X
import qualified Control.Monad.Catch as CMC
import qualified Data.ByteString as BS
import qualified Data.ByteString.UTF8 as UTF8
import qualified Data.ElfEdit as EE
import qualified Data.Set as Set
import qualified Data.Sequence as Seq
import qualified Data.Type.Equality as DTE
import qualified Prettyprinter as PP
import qualified System.Directory as SD
import qualified System.FilePath as SF

-- | Given a binary, load all of the shared libraries that it transitively
-- depends on, returning the order in which they were encountered in a
  breadth - first search . Returning them in this order is important since we
-- rely on the assumption that the binaries are in the same order as the global
-- lookup scope. See @Note [Dynamic lookup scope]@.
--
-- This function makes a couple of simplifying assumptions about how shared
-- libraries work that are not true in general:
--
-- * All of the shared libraries that the main binary depends on are located in
--   a single directory.
--
-- * None of the binaries use @dlopen@, which can load additional shared
--   libraries at runtime.
loadDynamicDependencies ::
     forall w
   . EE.ElfMachine
  -- ^ The architecture of the main binary (x86-64, AArch32, etc.)
  -> EE.ElfClass w
  ^ Whether the main binary is 32 - bit or 64 - bit
  -> FilePath
  -- ^ The directory in which the shared libraries live
  -> EE.ElfHeaderInfo w
  -- ^ The main binary's ELF header info
  -> FilePath
  -- ^ The main binary's path
  -> IO [(EE.ElfHeaderInfo w, FilePath)]
  -- ^ The shared libraries in order of global lookup scope, paired with their
  -- file paths
loadDynamicDependencies expectedHeaderMachine expectedHeaderClass
                        sharedObjectDir mainBinaryEHI mainBinaryPath =
  First , parse the DT_NEEDED entries of the main binary .
   case parseDynNeeded mainBinaryEHI mainBinaryPath of
     -- If this returns Nothing, the binary isn't dynamically linked.
     -- We return an empty list of shared libraries in this case.
     Nothing -> pure []
  Otherwise , proceed with a breadth - first search of the DT_NEEDED entries
     -- in each of the shared libraries.
     Just dynNeededs -> do
       dynNeededs' <- either CMC.throwM pure dynNeededs
       go Set.empty $ Seq.fromList dynNeededs'
  where
  The main loop in the breadth - first search .
    go ::
      Set.Set BS.ByteString ->
      -- ^ The set of shared libraries that we have already loaded.
      Seq.Seq BS.ByteString ->
      -- ^ The queue of @DT_NEEDED@ entries that need to be processed.
      IO [(EE.ElfHeaderInfo w, FilePath)]
    go sosSeenSoFar dynQueue =
  Dequeue the next DT_NEEDED entry on the queue .
      case Seq.viewl dynQueue of
        Seq.EmptyL -> pure []
        dynNext Seq.:< dynRest
          |  -- If we have already loaded this shared library, skip it and
             -- process the rest of the queue.
             dynNext `Set.member` sosSeenSoFar
          -> go sosSeenSoFar dynRest
          |  otherwise
          -> do let dynNextFP = UTF8.toString dynNext
                let fullPath = sharedObjectDir SF.</> dynNextFP
                exists <- SD.doesFileExist fullPath
                -- We only attempt to load a shared library if it exists on the
                -- user-specified path. Otherwise, we skip it and process the
                -- rest of the queue.
                --
                -- This is a design choice, as we could just as well throw an
                -- error here if the shared library does not exist. We opt to
                -- be somewhat lenient here because it's common for binaries to
                -- link against shared libraries that aren't reached from most
                -- code paths, such as libc. We want to be able to analyze these
                -- code paths without requiring the user to hunt down every last
                -- shared library that the binary could potentially use.
                if exists
                  then do
                    -- Read the shared library from disk and load it.
                    soBytes <- BS.readFile fullPath
                    so <- loadSharedObject dynNextFP soBytes
                    case parseDynNeeded so dynNextFP of
                      -- By definition, each of the shared libraries
                      -- should be dynamically linked. If they're not,
                      -- something very fishy is going on, so throw an
                      -- error.
                      Nothing -> CMC.throwM $ ElfNonDynamicSharedLib dynNextFP
                      -- Otherwise, return the loaded shared library and
                      -- proceed. In the process of doing so, we add the
                      -- shared library to the set of already loaded
  libraries and add the DT_NEEDED entries from the
                      -- shared library to the back of the queue.
                      Just dynNeededs -> do
                        dynNeededs' <- either CMC.throwM pure dynNeededs
                        sos <- go (Set.insert dynNext sosSeenSoFar)
                                  (dynRest <> Seq.fromList dynNeededs')
                        pure ((so, dynNextFP):sos)
                   else go sosSeenSoFar dynRest

    -- Load a shared library from bytes.
    loadSharedObject ::
      FilePath ->
      -- ^ The path to the shared library
      BS.ByteString ->
      -- ^ The contents of the shared library
      IO (EE.ElfHeaderInfo w)
    loadSharedObject soName soBytes =
      case EE.decodeElfHeaderInfo soBytes of
        Right (EE.SomeElf ehi) -> do
          let hdr = EE.header ehi
          let actualHeaderClass = EE.headerClass hdr
          let actualHeaderMachine = EE.headerMachine hdr

          if actualHeaderMachine == expectedHeaderMachine
          then
            case DTE.testEquality actualHeaderClass expectedHeaderClass of
              Just DTE.Refl -> pure ehi
              _ -> CMC.throwM $ SoMismatchedElfClass actualHeaderClass
                                                     expectedHeaderClass
          else CMC.throwM $ SoMismatchedElfMachine actualHeaderMachine
                                                   expectedHeaderMachine
        Left _ -> CMC.throwM $ NonElfBinaryFormat soName

-- | Get values of @DT_NEEDED@ entries in an ELF file. If this is not a dynamic
-- executable, then @Nothing@ is returned.
parseDynNeeded ::
  EE.ElfHeaderInfo w ->
  FilePath ->
  -- ^ The path to the ELF file
  Maybe (Either DynamicLoadingError [BS.ByteString])
parseDynNeeded elfHeaderInfo elfFP = EE.elfClassInstances elfClass $
  case filter (\p -> EE.phdrSegmentType p == EE.PT_DYNAMIC) elfPhdrs of
    [dynPhdr] -> Just $
      let dynContents = EE.slice (EE.phdrFileRange dynPhdr) elfBytes
      in case EE.dynamicEntries (EE.headerData elfHeader) elfClass dynContents of
           Left dynError ->
             Left $ ElfDynamicParseError elfFP dynError
           Right dynSection -> do
             case EE.virtAddrMap elfBytes elfPhdrs of
               Nothing -> do
                 Left $ ElfVirtualAddressMapError elfFP
               Just phdrs ->
                 case EE.dynNeeded dynSection phdrs of
                   Left errMsg -> Left $ ElfDynamicNeededError elfFP errMsg
                   Right deps -> Right deps
    [] -> Nothing
    _  -> Just $ Left $ ElfMultipleDynamicHeaders elfFP
  where
    elfHeader = EE.header elfHeaderInfo
    elfPhdrs = EE.headerPhdrs elfHeaderInfo
    elfBytes = EE.headerFileContents elfHeaderInfo
    elfClass = EE.headerClass elfHeader

data DynamicLoadingError where
  -- | Encountered a non-ELF binary format, which is not supported.
  NonElfBinaryFormat ::
       FilePath
    -> DynamicLoadingError

  -- | Encountered an error when parsing a dynamic section in an ELF binary.
  ElfDynamicParseError ::
       FilePath
    -> EE.DynamicError
    -> DynamicLoadingError

  -- | Encountered an error when parsing the @DT_NEEDED@ entries in a dynamic
  -- ELF binary.
  ElfDynamicNeededError ::
       FilePath
    -> String
    -> DynamicLoadingError

  -- | Could not constuct a virtual address map for an ELF binary.
  ElfVirtualAddressMapError ::
       FilePath
    -> DynamicLoadingError

  -- | Encountered multiple @PT_DYNAMIC@ program headers when parsing an ELF
  -- binary.
  ElfMultipleDynamicHeaders ::
       FilePath
    -> DynamicLoadingError

  -- | Encountered a shared library that is not dynamically linked.
  ElfNonDynamicSharedLib ::
       FilePath
    -> DynamicLoadingError

  | A provided shared object had a different ELF machine value than the main
  binary . The first argument is the ' EE.ElfMachine ' for the shared object
  and the second argument is the ' EE.ElfMachine ' for the main binary .
  SoMismatchedElfMachine ::
       EE.ElfMachine
    -> EE.ElfMachine
    -> DynamicLoadingError

  -- | A provided shared object had a different ELF class value than the main
  binary . The first argument is the ' EE.ElfClass ' for the shared object
  and the second argument is the ' EE.ElfClass ' for the main binary .
  SoMismatchedElfClass ::
       EE.ElfClass w
    -> EE.ElfClass w'
    -> DynamicLoadingError

deriving instance Show DynamicLoadingError

instance X.Exception DynamicLoadingError where
  displayException = show . PP.pretty

instance PP.Pretty DynamicLoadingError where
  pretty e =
    case e of
      NonElfBinaryFormat p ->
        "Unsupported, non-ELF binary format for file" PP.<+>
        PP.dquotes (PP.pretty p)

      ElfDynamicParseError fp dynErr ->
        PP.vcat
          [ PP.viaShow dynErr
          , "In the file:" PP.<+> PP.pretty fp
          ]
      ElfVirtualAddressMapError fp ->
        PP.vcat
          [ "Could not construct virtual address map"
          , "In the file:" PP.<+> PP.pretty fp
          ]
      ElfDynamicNeededError fp errMsg ->
        PP.vcat
          [ PP.pretty errMsg
          , "In the file:" PP.<+> PP.pretty fp
          ]
      ElfMultipleDynamicHeaders fp ->
        PP.vcat
          [ "Encountered multiple PT_DYNAMIC program headers"
          , "In the file:" PP.<+> PP.pretty fp
          ]
      ElfNonDynamicSharedLib fp ->
        "The shared library" PP.<+> PP.pretty fp PP.<+>
        "is not dynamically linked"
      SoMismatchedElfMachine soMachine mainMachine ->
        PP.vcat
          [ "A shared object has a different ELF machine value than the main binary."
          , "Shared object has machine " PP.<+> PP.viaShow soMachine PP.<+>
            "and main binary has machine " PP.<+> PP.viaShow mainMachine
          ]
      SoMismatchedElfClass soClass mainClass ->
        PP.vcat
          [ "A shared object has a different ELF class value than the main binary."
          , "Shared object has class " PP.<+> PP.viaShow soClass PP.<+>
            "and main binary has class " PP.<+> PP.viaShow mainClass
          ]


 Note [ Dynamic lookup scope ] 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 When looking up a dynamically linked function , which shared libraries should be 
 searched , and in which order ? Answering this question precisely is tricky . 

 Section 1.5.4 of " How to Write Shared Libraries " on lookup scopes 
 ( /~sergey/cs258/ABI/UlrichDrepper-How-To-Write-Shared-Libraries.pdf ) 
 offers a very detailed answer , although it is quite involved since it tries to 
 specify the behavior of ` dlopen ` .  needs to care about lookup scopes to 
 some degree , since it affects the semantics of dynamically linked programs , but 
 for now we prefer to pretend that ` dlopen ` is n't a thing . To borrow section 
 1.5.4 's jargon , that means that we need to simulate the /global/ lookup scope , 
 but not local lookup scopes . 

 When  loads shared libraries , it returns them in the order dictated by the 
 global scope . An ELF binary 's direct shared library dependencies are contained 
 in the DT_NEEDED entries , so to determine the global scope , we perform a 
 breadth - first search over the DT_NEEDED entries of the main binary and the 
 entries of the libraries that it depends on . See ` loadDynamicDependencies ` for 
 the full details . 

 Having the loaded binaries be in the same order as the global scope becomes 
 important when resolving dynamic function symbols . It 's possible for two 
 binaries to define different functions of the same name . For example , imagine 
 this scenario : 

   // a.c 
   char f ( ) { return ' a ' ; } 

   //   char f ( ) { return ' b ' ; } 

   // main.c 
   char f ( ) ; 
   int main ( ) { printf("%c\n " , f ( ) ) ; } 

 Suppose a.c and   compiled to shared libraries liba.so and libb.so , 
 respectively , and that main.c is compiled to a main.exe binary that links 
 against both liba and  . What will main.exe print when invoked ? The answer 
 depends on the order of DT_NEEDED entries in main.exe , which in turn depends on 
 the order in which main.exe was linked against liba and  when compiled . If 
 it was compiled like so : 

   gcc -L. -la -lb main.c -o main.exe 

 Then the global scope will be : 

   [ main.exe , liba.so , libb.so ] 

 And looking up f ( ) will find liba.so first , causing ' a ' to be printed . By a 
 similar token , if main.exe is compiled with ` -lb -la ` instead , then main.exe 
 would print ' b ' . 

 This search order is implemented on the macaw - symbolic side in 
 Data . Macaw . Symbolic . Testing.runDiscovery , which puts all of the dynamic symbols 
 in a binary into a single Map . The symbols will be inserted into the map in the 
 order the binaries appear in the global scope , and in the event that we 
 encounter a symbol that has already been inserted into the map , we will always 
 prefer the already - inserted symbol , as that appears first in the global scope . 

 It 's worth emphasizing that this implementation fundamentally relies on the 
 absence of dlopen . If we need to model dlopen in the future , we will have to 
 pick a more sophisticated implementation approach . 

Note [Dynamic lookup scope]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
When looking up a dynamically linked function, which shared libraries should be
searched, and in which order? Answering this question precisely is tricky.

Section 1.5.4 of "How to Write Shared Libraries" on lookup scopes
(/~sergey/cs258/ABI/UlrichDrepper-How-To-Write-Shared-Libraries.pdf)
offers a very detailed answer, although it is quite involved since it tries to
specify the behavior of `dlopen`. macaw needs to care about lookup scopes to
some degree, since it affects the semantics of dynamically linked programs, but
for now we prefer to pretend that `dlopen` isn't a thing. To borrow section
1.5.4's jargon, that means that we need to simulate the /global/ lookup scope,
but not local lookup scopes.

When macaw loads shared libraries, it returns them in the order dictated by the
global scope. An ELF binary's direct shared library dependencies are contained
in the DT_NEEDED entries, so to determine the global scope, we perform a
breadth-first search over the DT_NEEDED entries of the main binary and the
entries of the libraries that it depends on. See `loadDynamicDependencies` for
the full details.

Having the loaded binaries be in the same order as the global scope becomes
important when resolving dynamic function symbols. It's possible for two
binaries to define different functions of the same name. For example, imagine
this scenario:

  // a.c
  char f() { return 'a'; }

  // b.c
  char f() { return 'b'; }

  // main.c
  char f();
  int main() { printf("%c\n", f()); }

Suppose a.c and b.c are compiled to shared libraries liba.so and libb.so,
respectively, and that main.c is compiled to a main.exe binary that links
against both liba and libb. What will main.exe print when invoked? The answer
depends on the order of DT_NEEDED entries in main.exe, which in turn depends on
the order in which main.exe was linked against liba and libb when compiled. If
it was compiled like so:

  gcc -L. -la -lb main.c -o main.exe

Then the global scope will be:

  [main.exe, liba.so, libb.so]

And looking up f() will find liba.so first, causing 'a' to be printed. By a
similar token, if main.exe is compiled with `-lb -la` instead, then main.exe
would print 'b'.

This search order is implemented on the macaw-symbolic side in
Data.Macaw.Symbolic.Testing.runDiscovery, which puts all of the dynamic symbols
in a binary into a single Map. The symbols will be inserted into the map in the
order the binaries appear in the global scope, and in the event that we
encounter a symbol that has already been inserted into the map, we will always
prefer the already-inserted symbol, as that appears first in the global scope.

It's worth emphasizing that this implementation fundamentally relies on the
absence of dlopen. If we need to model dlopen in the future, we will have to
pick a more sophisticated implementation approach.
-}

# LANGUAGE OverloadedStrings #
 in a dynamically linked ELF binary.

 Note that the API in this library is somewhat experimental, and as we further
 develop the underlying approach (see @Note [Dynamic lookup scope]@), we may
 need to change the API accordingly.
 | Given a binary, load all of the shared libraries that it transitively
 depends on, returning the order in which they were encountered in a
 rely on the assumption that the binaries are in the same order as the global
 lookup scope. See @Note [Dynamic lookup scope]@.

 This function makes a couple of simplifying assumptions about how shared
 libraries work that are not true in general:

 * All of the shared libraries that the main binary depends on are located in
   a single directory.

 * None of the binaries use @dlopen@, which can load additional shared
   libraries at runtime.
 ^ The architecture of the main binary (x86-64, AArch32, etc.)
 ^ The directory in which the shared libraries live
 ^ The main binary's ELF header info
 ^ The main binary's path
 ^ The shared libraries in order of global lookup scope, paired with their
 file paths
 If this returns Nothing, the binary isn't dynamically linked.
 We return an empty list of shared libraries in this case.
 in each of the shared libraries.
 ^ The set of shared libraries that we have already loaded.
 ^ The queue of @DT_NEEDED@ entries that need to be processed.
 If we have already loaded this shared library, skip it and
 process the rest of the queue.
 We only attempt to load a shared library if it exists on the
 user-specified path. Otherwise, we skip it and process the
 rest of the queue.

 This is a design choice, as we could just as well throw an
 error here if the shared library does not exist. We opt to
 be somewhat lenient here because it's common for binaries to
 link against shared libraries that aren't reached from most
 code paths, such as libc. We want to be able to analyze these
 code paths without requiring the user to hunt down every last
 shared library that the binary could potentially use.
 Read the shared library from disk and load it.
 By definition, each of the shared libraries
 should be dynamically linked. If they're not,
 something very fishy is going on, so throw an
 error.
 Otherwise, return the loaded shared library and
 proceed. In the process of doing so, we add the
 shared library to the set of already loaded
 shared library to the back of the queue.
 Load a shared library from bytes.
 ^ The path to the shared library
 ^ The contents of the shared library
 | Get values of @DT_NEEDED@ entries in an ELF file. If this is not a dynamic
 executable, then @Nothing@ is returned.
 ^ The path to the ELF file
 | Encountered a non-ELF binary format, which is not supported.
 | Encountered an error when parsing a dynamic section in an ELF binary.
 | Encountered an error when parsing the @DT_NEEDED@ entries in a dynamic
 ELF binary.
 | Could not constuct a virtual address map for an ELF binary.
 | Encountered multiple @PT_DYNAMIC@ program headers when parsing an ELF
 binary.
 | Encountered a shared library that is not dynamically linked.
 | A provided shared object had a different ELF class value than the main
# LANGUAGE ScopedTypeVariables #
# LANGUAGE StandaloneDeriving #

  | Functionality for computing the names and addresses of PLT stub functions
module Data.Macaw.Memory.ElfLoader.DynamicDependencies
  ( loadDynamicDependencies
  , parseDynNeeded
  , DynamicLoadingError(..)
  ) where

import qualified Control.Exception as X
import qualified Control.Monad.Catch as CMC
import qualified Data.ByteString as BS
import qualified Data.ByteString.UTF8 as UTF8
import qualified Data.ElfEdit as EE
import qualified Data.Set as Set
import qualified Data.Sequence as Seq
import qualified Data.Type.Equality as DTE
import qualified Prettyprinter as PP
import qualified System.Directory as SD
import qualified System.FilePath as SF

  breadth - first search . Returning them in this order is important since we
loadDynamicDependencies ::
     forall w
   . EE.ElfMachine
  -> EE.ElfClass w
  ^ Whether the main binary is 32 - bit or 64 - bit
  -> FilePath
  -> EE.ElfHeaderInfo w
  -> FilePath
  -> IO [(EE.ElfHeaderInfo w, FilePath)]
loadDynamicDependencies expectedHeaderMachine expectedHeaderClass
                        sharedObjectDir mainBinaryEHI mainBinaryPath =
  First , parse the DT_NEEDED entries of the main binary .
   case parseDynNeeded mainBinaryEHI mainBinaryPath of
     Nothing -> pure []
  Otherwise , proceed with a breadth - first search of the DT_NEEDED entries
     Just dynNeededs -> do
       dynNeededs' <- either CMC.throwM pure dynNeededs
       go Set.empty $ Seq.fromList dynNeededs'
  where
  The main loop in the breadth - first search .
    go ::
      Set.Set BS.ByteString ->
      Seq.Seq BS.ByteString ->
      IO [(EE.ElfHeaderInfo w, FilePath)]
    go sosSeenSoFar dynQueue =
  Dequeue the next DT_NEEDED entry on the queue .
      case Seq.viewl dynQueue of
        Seq.EmptyL -> pure []
        dynNext Seq.:< dynRest
             dynNext `Set.member` sosSeenSoFar
          -> go sosSeenSoFar dynRest
          |  otherwise
          -> do let dynNextFP = UTF8.toString dynNext
                let fullPath = sharedObjectDir SF.</> dynNextFP
                exists <- SD.doesFileExist fullPath
                if exists
                  then do
                    soBytes <- BS.readFile fullPath
                    so <- loadSharedObject dynNextFP soBytes
                    case parseDynNeeded so dynNextFP of
                      Nothing -> CMC.throwM $ ElfNonDynamicSharedLib dynNextFP
  libraries and add the DT_NEEDED entries from the
                      Just dynNeededs -> do
                        dynNeededs' <- either CMC.throwM pure dynNeededs
                        sos <- go (Set.insert dynNext sosSeenSoFar)
                                  (dynRest <> Seq.fromList dynNeededs')
                        pure ((so, dynNextFP):sos)
                   else go sosSeenSoFar dynRest

    loadSharedObject ::
      FilePath ->
      BS.ByteString ->
      IO (EE.ElfHeaderInfo w)
    loadSharedObject soName soBytes =
      case EE.decodeElfHeaderInfo soBytes of
        Right (EE.SomeElf ehi) -> do
          let hdr = EE.header ehi
          let actualHeaderClass = EE.headerClass hdr
          let actualHeaderMachine = EE.headerMachine hdr

          if actualHeaderMachine == expectedHeaderMachine
          then
            case DTE.testEquality actualHeaderClass expectedHeaderClass of
              Just DTE.Refl -> pure ehi
              _ -> CMC.throwM $ SoMismatchedElfClass actualHeaderClass
                                                     expectedHeaderClass
          else CMC.throwM $ SoMismatchedElfMachine actualHeaderMachine
                                                   expectedHeaderMachine
        Left _ -> CMC.throwM $ NonElfBinaryFormat soName

parseDynNeeded ::
  EE.ElfHeaderInfo w ->
  FilePath ->
  Maybe (Either DynamicLoadingError [BS.ByteString])
parseDynNeeded elfHeaderInfo elfFP = EE.elfClassInstances elfClass $
  case filter (\p -> EE.phdrSegmentType p == EE.PT_DYNAMIC) elfPhdrs of
    [dynPhdr] -> Just $
      let dynContents = EE.slice (EE.phdrFileRange dynPhdr) elfBytes
      in case EE.dynamicEntries (EE.headerData elfHeader) elfClass dynContents of
           Left dynError ->
             Left $ ElfDynamicParseError elfFP dynError
           Right dynSection -> do
             case EE.virtAddrMap elfBytes elfPhdrs of
               Nothing -> do
                 Left $ ElfVirtualAddressMapError elfFP
               Just phdrs ->
                 case EE.dynNeeded dynSection phdrs of
                   Left errMsg -> Left $ ElfDynamicNeededError elfFP errMsg
                   Right deps -> Right deps
    [] -> Nothing
    _  -> Just $ Left $ ElfMultipleDynamicHeaders elfFP
  where
    elfHeader = EE.header elfHeaderInfo
    elfPhdrs = EE.headerPhdrs elfHeaderInfo
    elfBytes = EE.headerFileContents elfHeaderInfo
    elfClass = EE.headerClass elfHeader

data DynamicLoadingError where
  NonElfBinaryFormat ::
       FilePath
    -> DynamicLoadingError

  ElfDynamicParseError ::
       FilePath
    -> EE.DynamicError
    -> DynamicLoadingError

  ElfDynamicNeededError ::
       FilePath
    -> String
    -> DynamicLoadingError

  ElfVirtualAddressMapError ::
       FilePath
    -> DynamicLoadingError

  ElfMultipleDynamicHeaders ::
       FilePath
    -> DynamicLoadingError

  ElfNonDynamicSharedLib ::
       FilePath
    -> DynamicLoadingError

  | A provided shared object had a different ELF machine value than the main
  binary . The first argument is the ' EE.ElfMachine ' for the shared object
  and the second argument is the ' EE.ElfMachine ' for the main binary .
  SoMismatchedElfMachine ::
       EE.ElfMachine
    -> EE.ElfMachine
    -> DynamicLoadingError

  binary . The first argument is the ' EE.ElfClass ' for the shared object
  and the second argument is the ' EE.ElfClass ' for the main binary .
  SoMismatchedElfClass ::
       EE.ElfClass w
    -> EE.ElfClass w'
    -> DynamicLoadingError

deriving instance Show DynamicLoadingError

instance X.Exception DynamicLoadingError where
  displayException = show . PP.pretty

instance PP.Pretty DynamicLoadingError where
  pretty e =
    case e of
      NonElfBinaryFormat p ->
        "Unsupported, non-ELF binary format for file" PP.<+>
        PP.dquotes (PP.pretty p)

      ElfDynamicParseError fp dynErr ->
        PP.vcat
          [ PP.viaShow dynErr
          , "In the file:" PP.<+> PP.pretty fp
          ]
      ElfVirtualAddressMapError fp ->
        PP.vcat
          [ "Could not construct virtual address map"
          , "In the file:" PP.<+> PP.pretty fp
          ]
      ElfDynamicNeededError fp errMsg ->
        PP.vcat
          [ PP.pretty errMsg
          , "In the file:" PP.<+> PP.pretty fp
          ]
      ElfMultipleDynamicHeaders fp ->
        PP.vcat
          [ "Encountered multiple PT_DYNAMIC program headers"
          , "In the file:" PP.<+> PP.pretty fp
          ]
      ElfNonDynamicSharedLib fp ->
        "The shared library" PP.<+> PP.pretty fp PP.<+>
        "is not dynamically linked"
      SoMismatchedElfMachine soMachine mainMachine ->
        PP.vcat
          [ "A shared object has a different ELF machine value than the main binary."
          , "Shared object has machine " PP.<+> PP.viaShow soMachine PP.<+>
            "and main binary has machine " PP.<+> PP.viaShow mainMachine
          ]
      SoMismatchedElfClass soClass mainClass ->
        PP.vcat
          [ "A shared object has a different ELF class value than the main binary."
          , "Shared object has class " PP.<+> PP.viaShow soClass PP.<+>
            "and main binary has class " PP.<+> PP.viaShow mainClass
          ]


 Note [ Dynamic lookup scope ] 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 When looking up a dynamically linked function , which shared libraries should be 
 searched , and in which order ? Answering this question precisely is tricky . 

 Section 1.5.4 of " How to Write Shared Libraries " on lookup scopes 
 ( /~sergey/cs258/ABI/UlrichDrepper-How-To-Write-Shared-Libraries.pdf ) 
 offers a very detailed answer , although it is quite involved since it tries to 
 specify the behavior of ` dlopen ` .  needs to care about lookup scopes to 
 some degree , since it affects the semantics of dynamically linked programs , but 
 for now we prefer to pretend that ` dlopen ` is n't a thing . To borrow section 
 1.5.4 's jargon , that means that we need to simulate the /global/ lookup scope , 
 but not local lookup scopes . 

 When  loads shared libraries , it returns them in the order dictated by the 
 global scope . An ELF binary 's direct shared library dependencies are contained 
 in the DT_NEEDED entries , so to determine the global scope , we perform a 
 breadth - first search over the DT_NEEDED entries of the main binary and the 
 entries of the libraries that it depends on . See ` loadDynamicDependencies ` for 
 the full details . 

 Having the loaded binaries be in the same order as the global scope becomes 
 important when resolving dynamic function symbols . It 's possible for two 
 binaries to define different functions of the same name . For example , imagine 
 this scenario : 

   // a.c 
   char f ( ) { return ' a ' ; } 

   //   char f ( ) { return ' b ' ; } 

   // main.c 
   char f ( ) ; 
   int main ( ) { printf("%c\n " , f ( ) ) ; } 

 Suppose a.c and   compiled to shared libraries liba.so and libb.so , 
 respectively , and that main.c is compiled to a main.exe binary that links 
 against both liba and  . What will main.exe print when invoked ? The answer 
 depends on the order of DT_NEEDED entries in main.exe , which in turn depends on 
 the order in which main.exe was linked against liba and  when compiled . If 
 it was compiled like so : 

   gcc -L. -la -lb main.c -o main.exe 

 Then the global scope will be : 

   [ main.exe , liba.so , libb.so ] 

 And looking up f ( ) will find liba.so first , causing ' a ' to be printed . By a 
 similar token , if main.exe is compiled with ` -lb -la ` instead , then main.exe 
 would print ' b ' . 

 This search order is implemented on the macaw - symbolic side in 
 Data . Macaw . Symbolic . Testing.runDiscovery , which puts all of the dynamic symbols 
 in a binary into a single Map . The symbols will be inserted into the map in the 
 order the binaries appear in the global scope , and in the event that we 
 encounter a symbol that has already been inserted into the map , we will always 
 prefer the already - inserted symbol , as that appears first in the global scope . 

 It 's worth emphasizing that this implementation fundamentally relies on the 
 absence of dlopen . If we need to model dlopen in the future , we will have to 
 pick a more sophisticated implementation approach . 

Note [Dynamic lookup scope]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
When looking up a dynamically linked function, which shared libraries should be
searched, and in which order? Answering this question precisely is tricky.

Section 1.5.4 of "How to Write Shared Libraries" on lookup scopes
(/~sergey/cs258/ABI/UlrichDrepper-How-To-Write-Shared-Libraries.pdf)
offers a very detailed answer, although it is quite involved since it tries to
specify the behavior of `dlopen`. macaw needs to care about lookup scopes to
some degree, since it affects the semantics of dynamically linked programs, but
for now we prefer to pretend that `dlopen` isn't a thing. To borrow section
1.5.4's jargon, that means that we need to simulate the /global/ lookup scope,
but not local lookup scopes.

When macaw loads shared libraries, it returns them in the order dictated by the
global scope. An ELF binary's direct shared library dependencies are contained
in the DT_NEEDED entries, so to determine the global scope, we perform a
breadth-first search over the DT_NEEDED entries of the main binary and the
entries of the libraries that it depends on. See `loadDynamicDependencies` for
the full details.

Having the loaded binaries be in the same order as the global scope becomes
important when resolving dynamic function symbols. It's possible for two
binaries to define different functions of the same name. For example, imagine
this scenario:

  // a.c
  char f() { return 'a'; }

  // b.c
  char f() { return 'b'; }

  // main.c
  char f();
  int main() { printf("%c\n", f()); }

Suppose a.c and b.c are compiled to shared libraries liba.so and libb.so,
respectively, and that main.c is compiled to a main.exe binary that links
against both liba and libb. What will main.exe print when invoked? The answer
depends on the order of DT_NEEDED entries in main.exe, which in turn depends on
the order in which main.exe was linked against liba and libb when compiled. If
it was compiled like so:

  gcc -L. -la -lb main.c -o main.exe

Then the global scope will be:

  [main.exe, liba.so, libb.so]

And looking up f() will find liba.so first, causing 'a' to be printed. By a
similar token, if main.exe is compiled with `-lb -la` instead, then main.exe
would print 'b'.

This search order is implemented on the macaw-symbolic side in
Data.Macaw.Symbolic.Testing.runDiscovery, which puts all of the dynamic symbols
in a binary into a single Map. The symbols will be inserted into the map in the
order the binaries appear in the global scope, and in the event that we
encounter a symbol that has already been inserted into the map, we will always
prefer the already-inserted symbol, as that appears first in the global scope.

It's worth emphasizing that this implementation fundamentally relies on the
absence of dlopen. If we need to model dlopen in the future, we will have to
pick a more sophisticated implementation approach.
-}
