Augment lldb's symbol table with external symbols in Mach-O's dyld trie

[jasonmolenda]

Summary

In addition to the traditional nlist records in Mach-O binaries, the dynamic linker dyld has a trie structure that it uses to record symbols with external linkage. It uses this structure when resolving symbols at runtime; the nlist records can be completely stripped from a binary without detriment. lldb has read the special class of reexport symbols out of the dyld trie until now.

This patch has four parts -

1. Remove checks for an empty string table / nlist table as meaning there is no symbol table.

2. Changes ParseTrieEntries to recognize the externally-visible symbols and add them to a second array of TrieEntries.

3. After populating the symbol table from the nlist records, looks for any matching symbol addresses that we read from the trie, marks them as already seen so we don't add duplicated symbols in the table.

4. Adds the trie entries that hadn't already been seen, and marks any function starts with those addresses as already-added.

There is a test case that has a variety of text and data symbols with different linkage visibility and a test case that checks that we don't have duplicate symbol table entries, and that we can still find the externally visible symbols after stripping the binary.

The patch at this point is pretty straightforward. It's easy to make mistakes in ObjectFileMachO::ParseSymtab, and in the process of writing this I think I made all of them. But I'm open to any feedback about how things might be done more clearly.

Adrian, I wasn't sure how well I'm conforming to best practices on the testsuite Makefile, where I'm compiling my main.cpp has a dylib, then making a stripped copy. This works, but if you have a chance to look at it and provide feedback, I would appreciate it.

[aprantl]

I only have a bunch of superficial comments but this seems reasonable as far as I can tell.

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

1988

Flags(e.entry.flags).Test(EXPORT_SYMBOL_FLAGS_REEXPORT) ?

1990

Super nit-picky nit pick:

// Add symbols that are reexport symbols with a valid import name.

2012

Flags(e.entry.flags).Test(EXPORT_SYMBOL_FLAGS_REEXPORT) ?

4496

Ah I see. the normal operator< sorts by offset.

4499

Do we need llvm::stable_sort here to have reproducible behavior or does it not matter?

4500

Does for (auto &current_sym : sym) work here?

4512

GetFlags().test(MACHO_NLIST_ARM_SYMBOL_IS_THUMB) ?

Up to taste; it's more verbose but it's kind of confusing to combine && and & in the same expression.

4514

This block looks like it could be a lambda because it's the same code as above?

4546

Shows that I don't know the operater precedence rules of C very well, but without extra parenthesis this makes me uneasy :-)

4554

Wouldn't this automatically fail if function_starts_count == 0?

4556

if (!symbol_is_thumb ?

4566

High-level comment what this block is doing?

lldb/test/API/macosx/dyld-trie-symbols/Makefile

11

What does $(CFLAGS_NO_DEBUG) achieve in the *linker* invocation?

Could you get rid of this entire rule and just specify LD_EXTRAS = -dynamiclib?

18

Same question here

[jasonmolenda]

Thanks Adrian, great comments, incorporated most of them. The use of the block to search the trie entries when eliminating duplication between nlist/tries was a good idea, much cleaner now.

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

4500

This idiom is used everywhere else in ParseSymtab, just for consistency I want to stick with the older style.

4566

Added. It was largely the same thing as the function starts symbol table entries - we compute which section the address is in, to set the type of the symbol in the symtab.

[jasonmolenda]

Update patch with Adrian's suggestions.

[jasonmolenda]

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

4499

The dyld trie should not have multiple exported symbols with the same address, so sorting the vector by address should be fine. If that were to happen, we'd probably only clear the first one from the trie and we would eventually add the second one when we iterate over the table. I don't that's something I'll check in the code tho, it doesn't make much sense.

[JDevlieghere]

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

1926

return flags == LLDB_INVALID_ADDRESS

1990

Mega nit-picky nit pick: comment should be sentences and start with a capital.

4508

You don't need the else after a return.

4569

I guess this could be an else if

4598

This could make a great ternary operator ;-)

[jingham]

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

1926

This sort of change has the downside that you can't break when flags == LLDB_INVALID_ADDRESS without adding a condition. That seems in this case like a condition you are likely to want to break on, and given this looks like a function that gets called a lot, it's probably good to pay the cost of a condition.

I'm not sure I'm in favor of this sort of rewrite. It just saves one line, and isn't particularly easier to read. Does it have some benefit I'm missing?

[clayborg]

So I know the mach-o symbol table parsing code is a mess already, but it seems like this patch can be simpler if we make a std::set<lldb:addr_t> at the top of ObjectFileMachO::ParseSymtab() and every time we add a symbol that has a valid address value, add the file addr to this set. This will avoid the need to do any sorting. This std::set can be used to not add LC_FUNCTION_START entries that already have a symbol at the address, and it can be used to only add TrieEntry values that have symbols. Thoughts?

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

1924

The only bits that are used in this field are:

enum {
  EXPORT_SYMBOL_FLAGS_KIND_MASK = 0x03u,
  EXPORT_SYMBOL_FLAGS_WEAK_DEFINITION = 0x04u,
  EXPORT_SYMBOL_FLAGS_REEXPORT = 0x08u,
  EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER = 0x10u
};

enum ExportSymbolKind {
  EXPORT_SYMBOL_FLAGS_KIND_REGULAR = 0x00u,
  EXPORT_SYMBOL_FLAGS_KIND_THREAD_LOCAL = 0x01u,
  EXPORT_SYMBOL_FLAGS_KIND_ABSOLUTE = 0x02u
};

So why not just set the highest bit and avoid clobbering all of the other flags?:

#define EXPORT_SYMBOL_FLAGS_LLDB_ALREADY_PRESENT 1ull << 63
void SymbolAlreadyPresent() { flags |= EXPORT_SYMBOL_FLAGS_LLDB_ALREADY_PRESENT; }

1926

So is "flags" initially used just after parsing, but before we mark TrieEntry values as already present? These flags mean something when we first parse them. I would rather add an extra bool entry to this structure, since they don't stay around for long.

1926

return (flags & EXPORT_SYMBOL_FLAGS_LLDB_ALREADY_PRESENT) != 0;

1965

s/resoler/resolver/

2503–2516

Maybe we should run this before ParseTrieEntries and pass text_segment_file_addr in as an argument and add this to the offset as we parse the TrieEntry objects?

4490

Might be easier to create a std::set<lldb::addr_t> at the top of the ObjectFileMachO::ParseSymtab() function. Anyone who adds a symbol, would add the file address to that set. Then we wouldn't have to sort these entries, we would just iterator through them. We must do something like this for LC_FUNCTION_STARTS already right?

[jasonmolenda]

In D76758#1944612, @clayborg wrote:

So I know the mach-o symbol table parsing code is a mess already, but it seems like this patch can be simpler if we make a std::set<lldb:addr_t> at the top of ObjectFileMachO::ParseSymtab() and every time we add a symbol that has a valid address value, add the file addr to this set. This will avoid the need to do any sorting. This std::set can be used to not add LC_FUNCTION_START entries that already have a symbol at the address, and it can be used to only add TrieEntry values that have symbols. Thoughts?

That's a solid idea, let me try rewriting for that. LC_FUNCTION_STARTS already has a 'done' bool with each one to indicate whether it should be added to the symtab at the end. & yeah, I should have just added a new flag to indicate that the thing had already been seen -- for the exported symbols from the trie I wasn't use flags at all so I just clobbered it, but that's not a very nice way to do it. Let me try doing the std::set thing I think that'll remove a bunch of code across the function.

[jasonmolenda]

Updated the patch to incorporate Jonas and Greg's suggestions.

Most importantly, Greg's suggestion to have a set of addresses added to the symbol table; now that we've added a third symbol source, this was a much cleaner way to track which symbols should be added - process them in most-information-ful to least-information-ful order using this set to track if it has already been added.

This opened up the FunctionStarts data bool which was used to track if the func_start should be added, and I've used this (and a flag in the TrieEntry) to track if a function is thumb codegen; this further simplified a lot of code that was tracking this bit of metadata in the 0th bit of the addresses, complicating address comparisons etc - only the actual addresses are stored in these structures now.

[clayborg]

Much cleaner!

lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

 
     VMRange vm_range;
     SectionSP section_sp;
   };
   SectionList *m_section_list;
   std::vector<SectionInfo> m_section_infos;
 };
 
+#define TRIE_SYMBOL_IS_THUMB (1ULL << 63)
 struct TrieEntry {
   void Dump() const {
     printf("0x%16.16llx 0x%16.16llx 0x%16.16llx \"%s\"",
            static_cast<unsigned long long>(address),
            static_cast<unsigned long long>(flags),
            static_cast<unsigned long long>(other), name.GetCString());
     if (import_name)
       printf(" -> \"%s\"\n", import_name.GetCString());
     else
       printf("\n");
   }
   ConstString name;
   uint64_t address = LLDB_INVALID_ADDRESS;
-  uint64_t flags = 0;
+  uint64_t flags =
+      0; // EXPORT_SYMBOL_FLAGS_REEXPORT, EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER,
+         // TRIE_SYMBOL_IS_THUMB
   uint64_t other = 0;
   ConstString import_name;
 };
 
 struct TrieEntryWithOffset {
   lldb::offset_t nodeOffset;
   TrieEntry entry;
 
   TrieEntryWithOffset(lldb::offset_t offset) : nodeOffset(offset), entry() {}
 
   void Dump(uint32_t idx) const {
     printf("[%3u] 0x%16.16llx: ", idx,
            static_cast<unsigned long long>(nodeOffset));
     entry.Dump();
   }
 
   bool operator<(const TrieEntryWithOffset &other) const {
     return (nodeOffset < other.nodeOffset);
   }
 };
 
 static bool ParseTrieEntries(DataExtractor &data, lldb::offset_t offset,
-                             const bool is_arm,
+                             const bool is_arm, addr_t text_seg_base_addr,
                              std::vector<llvm::StringRef> &nameSlices,
                              std::set<lldb::addr_t> &resolver_addresses,
-                             std::vector<TrieEntryWithOffset> &output) {
+                             std::vector<TrieEntryWithOffset> &reexports,
+                             std::vector<TrieEntryWithOffset> &ext_symbols) {
   if (!data.ValidOffset(offset))
     return true;
 
+  // Terminal node -- end of a branch, possibly add this to
+  // the symbol table or resolver table.
   const uint64_t terminalSize = data.GetULEB128(&offset);
   lldb::offset_t children_offset = offset + terminalSize;
   if (terminalSize != 0) {
     TrieEntryWithOffset e(offset);
     e.entry.flags = data.GetULEB128(&offset);
     const char *import_name = nullptr;
     if (e.entry.flags & EXPORT_SYMBOL_FLAGS_REEXPORT) {
       e.entry.address = 0;
       e.entry.other = data.GetULEB128(&offset); // dylib ordinal
       import_name = data.GetCStr(&offset);
     } else {
       e.entry.address = data.GetULEB128(&offset);
+      if (text_seg_base_addr != LLDB_INVALID_ADDRESS)
+        e.entry.address += text_seg_base_addr;
       if (e.entry.flags & EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER) {
         e.entry.other = data.GetULEB128(&offset);
         uint64_t resolver_addr = e.entry.other;
         if (is_arm)
           resolver_addr &= THUMB_ADDRESS_BIT_MASK;
         resolver_addresses.insert(resolver_addr);
       } else
         e.entry.other = 0;
     }
-    // Only add symbols that are reexport symbols with a valid import name
-    if (EXPORT_SYMBOL_FLAGS_REEXPORT & e.entry.flags && import_name &&
-        import_name[0]) {
+    bool add_this_entry = false;
+    if (Flags(e.entry.flags).Test(EXPORT_SYMBOL_FLAGS_REEXPORT) &&
+        import_name && import_name[0]) {
+      // add symbols that are reexport symbols with a valid import name.
+      add_this_entry = true;
+    } else if (e.entry.flags == 0 &&
+               (import_name == nullptr || import_name[0] == '\0')) {
+      // add externally visible symbols, in case the nlist record has
+      // been stripped/omitted.
+      add_this_entry = true;
+    }
+    if (add_this_entry) {
       std::string name;
       if (!nameSlices.empty()) {
         for (auto name_slice : nameSlices)
           name.append(name_slice.data(), name_slice.size());
       }
       if (name.size() > 1) {
         // Skip the leading '_'
         e.entry.name.SetCStringWithLength(name.c_str() + 1, name.size() - 1);
       }
       if (import_name) {
         // Skip the leading '_'
         e.entry.import_name.SetCString(import_name + 1);
       }
-      output.push_back(e);
+      if (Flags(e.entry.flags).Test(EXPORT_SYMBOL_FLAGS_REEXPORT)) {
+        reexports.push_back(e);
+      } else {
+        if (is_arm && (e.entry.address & 1)) {
+          e.entry.flags |= TRIE_SYMBOL_IS_THUMB;
+          e.entry.address &= THUMB_ADDRESS_BIT_MASK;
+        }
+        ext_symbols.push_back(e);
+      }
     }
   }
 
   const uint8_t childrenCount = data.GetU8(&children_offset);
   for (uint8_t i = 0; i < childrenCount; ++i) {
     const char *cstr = data.GetCStr(&children_offset);
     if (cstr)
       nameSlices.push_back(llvm::StringRef(cstr));
     else
       return false; // Corrupt data
     lldb::offset_t childNodeOffset = data.GetULEB128(&children_offset);
     if (childNodeOffset) {
-      if (!ParseTrieEntries(data, childNodeOffset, is_arm, nameSlices,
-                            resolver_addresses, output)) {
+      if (!ParseTrieEntries(data, childNodeOffset, is_arm, text_seg_base_addr,
+                            nameSlices, resolver_addresses, reexports,
+                            ext_symbols)) {
         return false;
       }
     }
     nameSlices.pop_back();
   }
   return true;
 }
 

                      m_file.GetFilename().AsCString(""));
   ModuleSP module_sp(GetModule());
   if (!module_sp)
     return 0;
 
   struct symtab_command symtab_load_command = {0, 0, 0, 0, 0, 0};
   struct linkedit_data_command function_starts_load_command = {0, 0, 0, 0};
   struct dyld_info_command dyld_info = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+  // The data element of type bool indicates that this entry is thumb
+  // code.
   typedef AddressDataArray<lldb::addr_t, bool, 100> FunctionStarts;
+
+  // Record the address of every function/data that we add to the symtab.
+  // We add symbols to the table in the order of most information (nlist
+  // records) to least (function starts), and avoid duplicating symbols
+  // via this set.
+  std::set<addr_t> symbols_added;
   FunctionStarts function_starts;
   lldb::offset_t offset = MachHeaderSizeFromMagic(m_header.magic);
   uint32_t i;
   FileSpecList dylib_files;
   Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_SYMBOLS));
   llvm::StringRef g_objc_v2_prefix_class("_OBJC_CLASS_$_");
   llvm::StringRef g_objc_v2_prefix_metaclass("_OBJC_METACLASS_$_");
   llvm::StringRef g_objc_v2_prefix_ivar("_OBJC_IVAR_$_");
 
   for (i = 0; i < m_header.ncmds; ++i) {
     const lldb::offset_t cmd_offset = offset;
     // Read in the load command and load command size
     struct load_command lc;
     if (m_data.GetU32(&offset, &lc, 2) == nullptr)
       break;
     // Watch for the symbol table load command
     switch (lc.cmd) {
     case LC_SYMTAB:
       symtab_load_command.cmd = lc.cmd;
       symtab_load_command.cmdsize = lc.cmdsize;
       // Read in the rest of the symtab load command
       if (m_data.GetU32(&offset, &symtab_load_command.symoff, 4) ==
           nullptr) // fill in symoff, nsyms, stroff, strsize fields
         return 0;
-      if (symtab_load_command.symoff == 0) {
-        if (log)
-          module_sp->LogMessage(log, "LC_SYMTAB.symoff == 0");
-        return 0;
-      }
-
-      if (symtab_load_command.stroff == 0) {
-        if (log)
-          module_sp->LogMessage(log, "LC_SYMTAB.stroff == 0");
-        return 0;
-      }
-
-      if (symtab_load_command.nsyms == 0) {
-        if (log)
-          module_sp->LogMessage(log, "LC_SYMTAB.nsyms == 0");
-        return 0;
-      }
-
-      if (symtab_load_command.strsize == 0) {
-        if (log)
-          module_sp->LogMessage(log, "LC_SYMTAB.strsize == 0");
-        return 0;
-      }
       break;
 
     case LC_DYLD_INFO:
     case LC_DYLD_INFO_ONLY:
       if (m_data.GetU32(&offset, &dyld_info.rebase_off, 10)) {
         dyld_info.cmd = lc.cmd;
         dyld_info.cmdsize = lc.cmdsize;
       } else {

                                          m_dysymtab.nindirectsyms * 4);
     }
     if (function_starts_load_command.cmd) {
       function_starts_data.SetData(m_data, function_starts_load_command.dataoff,
                                    function_starts_load_command.datasize);
     }
   }
 
-  if (nlist_data.GetByteSize() == 0 &&
-      memory_module_load_level == eMemoryModuleLoadLevelComplete) {
-    if (log)
-      module_sp->LogMessage(log, "failed to read nlist data");
-    return 0;
-  }
-
   const bool have_strtab_data = strtab_data.GetByteSize() > 0;
-  if (!have_strtab_data) {
-    if (process) {
-      if (strtab_addr == LLDB_INVALID_ADDRESS) {
-        if (log)
-          module_sp->LogMessage(log, "failed to locate the strtab in memory");
-        return 0;
-      }
-    } else {
-      if (log)
-        module_sp->LogMessage(log, "failed to read strtab data");
-      return 0;
-    }
-  }
 
   ConstString g_segment_name_TEXT = GetSegmentNameTEXT();
   ConstString g_segment_name_DATA = GetSegmentNameDATA();
   ConstString g_segment_name_DATA_DIRTY = GetSegmentNameDATA_DIRTY();
   ConstString g_segment_name_DATA_CONST = GetSegmentNameDATA_CONST();
   ConstString g_segment_name_OBJC = GetSegmentNameOBJC();
   ConstString g_section_name_eh_frame = GetSectionNameEHFrame();
   SectionSP text_section_sp(

   if (text_section_sp.get())
     eh_frame_section_sp = text_section_sp->GetChildren().FindSectionByName(
         g_section_name_eh_frame);
   else
     eh_frame_section_sp =
         section_list->FindSectionByName(g_section_name_eh_frame);
 
   const bool is_arm = (m_header.cputype == llvm::MachO::CPU_TYPE_ARM);
+  const bool always_thumb = GetArchitecture().IsAlwaysThumbInstructions();
 
   // lldb works best if it knows the start address of all functions in a
   // module. Linker symbols or debug info are normally the best source of
   // information for start addr / size but they may be stripped in a released
   // binary. Two additional sources of information exist in Mach-O binaries:
   //    LC_FUNCTION_STARTS - a list of ULEB128 encoded offsets of each
   //    function's start address in the
   //                         binary, relative to the text section.

     function_start_entry.data = false;
     lldb::offset_t function_start_offset = 0;
     function_start_entry.addr = text_section_sp->GetFileAddress();
     uint64_t delta;
     while ((delta = function_starts_data.GetULEB128(&function_start_offset)) >
            0) {
       // Now append the current entry
       function_start_entry.addr += delta;
+      if (is_arm) {
+        if (function_start_entry.addr & 1) {
+          function_start_entry.addr &= THUMB_ADDRESS_BIT_MASK;
+          function_start_entry.data = true;
+        } else if (always_thumb) {
+          function_start_entry.data = true;
+        }
+      }
       function_starts.Append(function_start_entry);
     }
   } else {
     // If m_type is eTypeDebugInfo, then this is a dSYM - it will have the
     // load command claiming an eh_frame but it doesn't actually have the
     // eh_frame content.  And if we have a dSYM, we don't need to do any of
     // this fill-in-the-missing-symbols works anyway - the debug info should
     // give us all the functions in the module.
     if (text_section_sp.get() && eh_frame_section_sp.get() &&
         m_type != eTypeDebugInfo) {
       DWARFCallFrameInfo eh_frame(*this, eh_frame_section_sp,
                                   DWARFCallFrameInfo::EH);
       DWARFCallFrameInfo::FunctionAddressAndSizeVector functions;
       eh_frame.GetFunctionAddressAndSizeVector(functions);
       addr_t text_base_addr = text_section_sp->GetFileAddress();
       size_t count = functions.GetSize();
       for (size_t i = 0; i < count; ++i) {
         const DWARFCallFrameInfo::FunctionAddressAndSizeVector::Entry *func =
             functions.GetEntryAtIndex(i);
         if (func) {
           FunctionStarts::Entry function_start_entry;
           function_start_entry.addr = func->base - text_base_addr;
+          if (is_arm) {
+            if (function_start_entry.addr & 1) {
+              function_start_entry.addr &= THUMB_ADDRESS_BIT_MASK;
+              function_start_entry.data = true;
+            } else if (always_thumb) {
+              function_start_entry.data = true;
+            }
+          }
           function_starts.Append(function_start_entry);
         }
       }
     }
   }
 
   const size_t function_starts_count = function_starts.GetSize();
 

   MachSymtabSectionInfo section_info(section_list);
   std::vector<uint32_t> N_FUN_indexes;
   std::vector<uint32_t> N_NSYM_indexes;
   std::vector<uint32_t> N_INCL_indexes;
   std::vector<uint32_t> N_BRAC_indexes;
   std::vector<uint32_t> N_COMM_indexes;
   typedef std::multimap<uint64_t, uint32_t> ValueToSymbolIndexMap;
   typedef llvm::DenseMap<uint32_t, uint32_t> NListIndexToSymbolIndexMap;
   typedef llvm::DenseMap<const char *, uint32_t> ConstNameToSymbolIndexMap;
   ValueToSymbolIndexMap N_FUN_addr_to_sym_idx;
   ValueToSymbolIndexMap N_STSYM_addr_to_sym_idx;
   ConstNameToSymbolIndexMap N_GSYM_name_to_sym_idx;
   // Any symbols that get merged into another will get an entry in this map
   // so we know
   NListIndexToSymbolIndexMap m_nlist_idx_to_sym_idx;
   uint32_t nlist_idx = 0;
   Symbol *symbol_ptr = nullptr;
 
   uint32_t sym_idx = 0;
   Symbol *sym = nullptr;
   size_t num_syms = 0;
   std::string memory_symbol_name;
   uint32_t unmapped_local_symbols_found = 0;
 
-  std::vector<TrieEntryWithOffset> trie_entries;
+  std::vector<TrieEntryWithOffset> reexport_trie_entries;
+  std::vector<TrieEntryWithOffset> external_sym_trie_entries;
   std::set<lldb::addr_t> resolver_addresses;
 
   if (dyld_trie_data.GetByteSize() > 0) {
-    std::vector<llvm::StringRef> nameSlices;
-    ParseTrieEntries(dyld_trie_data, 0, is_arm, nameSlices, resolver_addresses,
-                     trie_entries);
-
     ConstString text_segment_name("__TEXT");
     SectionSP text_segment_sp =
         GetSectionList()->FindSectionByName(text_segment_name);
-    if (text_segment_sp) {
-      const lldb::addr_t text_segment_file_addr =
-          text_segment_sp->GetFileAddress();
-      if (text_segment_file_addr != LLDB_INVALID_ADDRESS) {
-        for (auto &e : trie_entries)
-          e.entry.address += text_segment_file_addr;
-      }
-    }
+    lldb::addr_t text_segment_file_addr = LLDB_INVALID_ADDRESS;
+    if (text_segment_sp)
+      text_segment_file_addr = text_segment_sp->GetFileAddress();
+    std::vector<llvm::StringRef> nameSlices;
+    ParseTrieEntries(dyld_trie_data, 0, is_arm, text_segment_file_addr,
+                     nameSlices, resolver_addresses, reexport_trie_entries,
+                     external_sym_trie_entries);
   }
 
   typedef std::set<ConstString> IndirectSymbols;
   IndirectSymbols indirect_symbol_names;
 
 #if defined(__APPLE__) &&                                                      \
     (defined(__arm__) || defined(__arm64__) || defined(__aarch64__))
 

                                     GSYM_sym_idx;
                                 // Copy the address, because often the N_GSYM
                                 // address has an invalid address of zero
                                 // when the global is a common symbol
                                 sym[GSYM_sym_idx].GetAddressRef().SetSection(
                                     symbol_section);
                                 sym[GSYM_sym_idx].GetAddressRef().SetOffset(
                                     symbol_value);
+                                symbols_added.insert(sym[GSYM_sym_idx]
+                                                         .GetAddress()
+                                                         .GetFileAddress());
                                 // We just need the flags from the linker
                                 // symbol, so put these flags
                                 // into the N_GSYM flags to avoid duplicate
                                 // symbols in the symbol table
                                 sym[GSYM_sym_idx].SetFlags(nlist.n_type << 16 |
                                                            nlist.n_desc);
                                 sym[sym_idx].Clear();
                                 continue;
                               }
                             }
                           }
                         }
                       }
 
                       sym[sym_idx].SetID(nlist_idx);
                       sym[sym_idx].SetType(type);
                       if (set_value) {
                         sym[sym_idx].GetAddressRef().SetSection(symbol_section);
                         sym[sym_idx].GetAddressRef().SetOffset(symbol_value);
+                        symbols_added.insert(
+                            sym[sym_idx].GetAddress().GetFileAddress());
                       }
                       sym[sym_idx].SetFlags(nlist.n_type << 16 | nlist.n_desc);
 
                       if (symbol_byte_size > 0)
                         sym[sym_idx].SetByteSize(symbol_byte_size);
 
                       if (demangled_is_synthesized)
                         sym[sym_idx].SetDemangledNameIsSynthesized(true);

                   N_GSYM_name_to_sym_idx.find(gsym_name);
               if (pos != N_GSYM_name_to_sym_idx.end()) {
                 const uint32_t GSYM_sym_idx = pos->second;
                 m_nlist_idx_to_sym_idx[nlist_idx] = GSYM_sym_idx;
                 // Copy the address, because often the N_GSYM address has an
                 // invalid address of zero when the global is a common symbol.
                 sym[GSYM_sym_idx].GetAddressRef().SetSection(symbol_section);
                 sym[GSYM_sym_idx].GetAddressRef().SetOffset(symbol_value);
+                symbols_added.insert(
+                    sym[GSYM_sym_idx].GetAddress().GetFileAddress());
                 // We just need the flags from the linker symbol, so put these
                 // flags into the N_GSYM flags to avoid duplicate symbols in
                 // the symbol table.
                 sym[GSYM_sym_idx].SetFlags(nlist.n_type << 16 | nlist.n_desc);
                 sym[sym_idx].Clear();
                 return true;
               }
             }
           }
         }
       }
 
       sym[sym_idx].SetID(nlist_idx);
       sym[sym_idx].SetType(type);
       if (set_value) {
         sym[sym_idx].GetAddressRef().SetSection(symbol_section);
         sym[sym_idx].GetAddressRef().SetOffset(symbol_value);
+        symbols_added.insert(sym[sym_idx].GetAddress().GetFileAddress());
       }
       sym[sym_idx].SetFlags(nlist.n_type << 16 | nlist.n_desc);
       if (nlist.n_desc & N_WEAK_REF)
         sym[sym_idx].SetIsWeak(true);
 
       if (symbol_byte_size > 0)
         sym[sym_idx].SetByteSize(symbol_byte_size);
 

         nlists.push_back(*nlist);
       else
         break;
     }
 
     // Now parse all the debug symbols. This is needed to merge non-debug
     // symbols in the next step. Non-debug symbols are always coalesced into
     // the debug symbol. Doing this in one step would mean that some symbols
     // won't be merged.
     nlist_idx = 0;
     for (auto &nlist : nlists) {
       if (!ParseSymbolLambda(nlist, nlist_idx++, DebugSymbols))
         break;
     }
 
     // Finally parse all the non debug symbols.
     nlist_idx = 0;
     for (auto &nlist : nlists) {
       if (!ParseSymbolLambda(nlist, nlist_idx++, NonDebugSymbols))
         break;
     }
 
     for (const auto &pos : reexport_shlib_needs_fixup) {
       const auto undef_pos = undefined_name_to_desc.find(pos.second);
       if (undef_pos != undefined_name_to_desc.end()) {
         const uint8_t dylib_ordinal =
             llvm::MachO::GET_LIBRARY_ORDINAL(undef_pos->second);
         if (dylib_ordinal > 0 && dylib_ordinal < dylib_files.GetSize())
           sym[pos.first].SetReExportedSymbolSharedLibrary(
               dylib_files.GetFileSpecAtIndex(dylib_ordinal - 1));
       }
     }
   }
 
+  // Count how many trie symbols we'll add to the symbol table
+  int trie_symbol_table_augment_count = 0;
+  for (auto &e : external_sym_trie_entries) {
+    if (symbols_added.find(e.entry.address) == symbols_added.end())
+      trie_symbol_table_augment_count++;
+  }
+
+  if (num_syms < sym_idx + trie_symbol_table_augment_count) {
+    num_syms = sym_idx + trie_symbol_table_augment_count;
+    sym = symtab->Resize(num_syms);
+  }
   uint32_t synthetic_sym_id = symtab_load_command.nsyms;
 
+  // Add symbols from the trie to the symbol table.
+  for (auto &e : external_sym_trie_entries) {
+    if (symbols_added.find(e.entry.address) != symbols_added.end())
+      continue;
+
+    // Find the section that this trie address is in, use that to annotate
+    // symbol type as we add the trie address and name to the symbol table.
+    Address symbol_addr;
+    if (module_sp->ResolveFileAddress(e.entry.address, symbol_addr)) {
+      SectionSP symbol_section(symbol_addr.GetSection());
+      if (symbol_section) {
+        sym[sym_idx].SetID(synthetic_sym_id++);
+        sym[sym_idx].GetMangled().SetMangledName(e.entry.name);
+        switch (symbol_section->GetType()) {
+        case eSectionTypeCode:
+          sym[sym_idx].SetType(eSymbolTypeCode);
+          break;
+        case eSectionTypeOther:
+        case eSectionTypeData:
+        case eSectionTypeZeroFill:
+          sym[sym_idx].SetType(eSymbolTypeData);
+          break;
+        default:
+          break;
+        }
+        sym[sym_idx].SetIsSynthetic(false);
+        sym[sym_idx].SetExternal(true);
+        sym[sym_idx].GetAddressRef() = symbol_addr;
+        symbols_added.insert(symbol_addr.GetFileAddress());
+        if (e.entry.flags & TRIE_SYMBOL_IS_THUMB)
+          sym[sym_idx].SetFlags(MACHO_NLIST_ARM_SYMBOL_IS_THUMB);
+        ++sym_idx;
+      }
+    }
+  }
+
   if (function_starts_count > 0) {
     uint32_t num_synthetic_function_symbols = 0;
     for (i = 0; i < function_starts_count; ++i) {
-      if (!function_starts.GetEntryRef(i).data)
+      if (symbols_added.find(function_starts.GetEntryRef(i).addr) ==
+          symbols_added.end())
         ++num_synthetic_function_symbols;
     }
 
     if (num_synthetic_function_symbols > 0) {
       if (num_syms < sym_idx + num_synthetic_function_symbols) {
         num_syms = sym_idx + num_synthetic_function_symbols;
         sym = symtab->Resize(num_syms);
       }
       for (i = 0; i < function_starts_count; ++i) {
         const FunctionStarts::Entry *func_start_entry =
             function_starts.GetEntryAtIndex(i);
-        if (!func_start_entry->data) {
+        if (symbols_added.find(func_start_entry->addr) == symbols_added.end()) {
           addr_t symbol_file_addr = func_start_entry->addr;
           uint32_t symbol_flags = 0;
-          if (is_arm) {
-            if (symbol_file_addr & 1)
-              symbol_flags = MACHO_NLIST_ARM_SYMBOL_IS_THUMB;
-            symbol_file_addr &= THUMB_ADDRESS_BIT_MASK;
-          }
+          if (func_start_entry->data)
+            symbol_flags = MACHO_NLIST_ARM_SYMBOL_IS_THUMB;
           Address symbol_addr;
           if (module_sp->ResolveFileAddress(symbol_file_addr, symbol_addr)) {
             SectionSP symbol_section(symbol_addr.GetSection());
             uint32_t symbol_byte_size = 0;
             if (symbol_section) {
               const addr_t section_file_addr = symbol_section->GetFileAddress();
               const FunctionStarts::Entry *next_func_start_entry =
                   function_starts.FindNextEntry(func_start_entry);
               const addr_t section_end_file_addr =
                   section_file_addr + symbol_section->GetByteSize();
               if (next_func_start_entry) {
                 addr_t next_symbol_file_addr = next_func_start_entry->addr;
                 if (is_arm)
                   next_symbol_file_addr &= THUMB_ADDRESS_BIT_MASK;
                 symbol_byte_size = std::min<lldb::addr_t>(
                     next_symbol_file_addr - symbol_file_addr,
                     section_end_file_addr - symbol_file_addr);
               } else {
                 symbol_byte_size = section_end_file_addr - symbol_file_addr;
               }
               sym[sym_idx].SetID(synthetic_sym_id++);
               sym[sym_idx].GetMangled().SetDemangledName(
                   GetNextSyntheticSymbolName());
               sym[sym_idx].SetType(eSymbolTypeCode);
               sym[sym_idx].SetIsSynthetic(true);
               sym[sym_idx].GetAddressRef() = symbol_addr;
+              symbols_added.insert(symbol_addr.GetFileAddress());
               if (symbol_flags)
                 sym[sym_idx].SetFlags(symbol_flags);
               if (symbol_byte_size)
                 sym[sym_idx].SetByteSize(symbol_byte_size);
               ++sym_idx;
             }
           }
         }

                   sym[sym_idx].GetMangled() = stub_symbol_mangled_name;
                   if (resolver_addresses.find(symbol_stub_addr) ==
                       resolver_addresses.end())
                     sym[sym_idx].SetType(eSymbolTypeTrampoline);
                   else
                     sym[sym_idx].SetType(eSymbolTypeResolver);
                   sym[sym_idx].SetIsSynthetic(true);
                   sym[sym_idx].GetAddressRef() = so_addr;
+                  symbols_added.insert(so_addr.GetFileAddress());
                   sym[sym_idx].SetByteSize(symbol_stub_byte_size);
                   ++sym_idx;
                 }
               } else {
                 if (log)
                   log->Warning("symbol stub referencing symbol table symbol "
                                "%u that isn't in our minimal symbol table, "
                                "fix this!!!",
                                stub_sym_id);
               }
             }
           }
         }
       }
     }
   }
 
-  if (!trie_entries.empty()) {
-    for (const auto &e : trie_entries) {
+  if (!reexport_trie_entries.empty()) {
+    for (const auto &e : reexport_trie_entries) {
       if (e.entry.import_name) {
         // Only add indirect symbols from the Trie entries if we didn't have
         // a N_INDR nlist entry for this already
         if (indirect_symbol_names.find(e.entry.name) ==
             indirect_symbol_names.end()) {
           // Make a synthetic symbol to describe re-exported symbol.
           if (sym_idx >= num_syms)
             sym = symtab->Resize(++num_syms);

lldb/test/API/macosx/dyld-trie-symbols/Makefile

+CXX_SOURCES := main.cpp
+EXE := a.out
+MAKE_DSYM := NO
+LD_EXTRAS = -dynamiclib -image_base 0x8000
+CFLAGS = $(CFLAGS_NO_DEBUG)
+
+include Makefile.rules
+
+all: a.out a.out-stripped
+
+a.out-stripped:
+  cp a.out a.out-stripped
+  strip a.out-stripped

lldb/test/API/macosx/dyld-trie-symbols/TestDyldTrieSymbols.py

+"""
+Test that we read the exported symbols from the dyld trie
+"""
+
+import lldb
+from lldbsuite.test.decorators import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+
+class DyldTrieSymbolsTestCase(TestBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+
+    NO_DEBUG_INFO_TESTCASE = True
+
+    @skipIfRemote
+    @skipUnlessDarwin
+    
+    def test_dyld_trie_symbols(self):
+        """Test that we make create symbol table entries from the dyld trie data structure."""
+        self.build()
+        unstripped_exe = self.getBuildArtifact("a.out")
+        stripped_exe = self.getBuildArtifact("a.out-stripped")
+
+        unstripped_target = self.dbg.CreateTarget(unstripped_exe)
+        self.assertTrue(unstripped_target.IsValid(), "Got a vaid stripped target.")
+
+        # Verify that the expected symbols are present in an unstripped
+        # binary, and that we didn't duplicate the entries in the symbol
+        # table.
+        unstripped_bazval_symbols = unstripped_target.FindSymbols("bazval")
+        self.assertEqual(unstripped_bazval_symbols.GetSize(), 1)
+        unstripped_patval_symbols = unstripped_target.FindSymbols("patval")
+        self.assertEqual(unstripped_patval_symbols.GetSize(), 1)
+        unstripped_Z3foo_symbols = unstripped_target.FindSymbols("_Z3foov")
+        self.assertEqual(unstripped_Z3foo_symbols.GetSize(), 1)
+        unstripped_foo_symbols = unstripped_target.FindSymbols("foo")
+        self.assertEqual(unstripped_foo_symbols.GetSize(), 1)
+
+        # make sure we can look up the mangled name, demangled base name,
+        # demangled name with argument.
+        unstripped_Z3pat_symbols = unstripped_target.FindSymbols("_Z3pati")
+        self.assertEqual(unstripped_Z3pat_symbols.GetSize(), 1)
+        unstripped_pat_symbols = unstripped_target.FindSymbols("pat")
+        self.assertEqual(unstripped_pat_symbols.GetSize(), 1)
+        unstripped_patint_symbols = unstripped_target.FindSymbols("pat(int)")
+        self.assertEqual(unstripped_patint_symbols.GetSize(), 1)
+
+        unstripped_bar_symbols = unstripped_target.FindSymbols("bar")
+        self.assertEqual(unstripped_bar_symbols.GetSize(), 1)
+
+
+
+        # Verify that we can retrieve all the symbols with external
+        # linkage after the binary has been stripped; they should not
+        # exist in the nlist records at this point and can only be
+        # retrieved from the dyld trie structure.
+
+        stripped_target = self.dbg.CreateTarget(stripped_exe)
+        self.assertTrue(stripped_target.IsValid(), "Got a vaid stripped target.")
+
+        # Check that we're able to still retrieve all the symbols after
+        # the binary has been stripped. Check that one we know will be
+        # removed is absent.
+        stripped_bazval_symbols = stripped_target.FindSymbols("bazval")
+        self.assertEqual(stripped_bazval_symbols.GetSize(), 1)
+        stripped_patval_symbols = stripped_target.FindSymbols("patval")
+        self.assertEqual(stripped_patval_symbols.GetSize(), 1)
+        stripped_Z3foo_symbols = stripped_target.FindSymbols("_Z3foov")
+        self.assertEqual(stripped_Z3foo_symbols.GetSize(), 1)
+        stripped_foo_symbols = stripped_target.FindSymbols("foo")
+        self.assertEqual(stripped_foo_symbols.GetSize(), 1)
+
+        # make sure we can look up the mangled name, demangled base name,
+        # demangled name with argument.
+        stripped_Z3pat_symbols = stripped_target.FindSymbols("_Z3pati")
+        self.assertEqual(stripped_Z3pat_symbols.GetSize(), 1)
+        stripped_pat_symbols = stripped_target.FindSymbols("pat")
+        self.assertEqual(stripped_pat_symbols.GetSize(), 1)
+        stripped_patint_symbols = stripped_target.FindSymbols("pat(int)")
+        self.assertEqual(stripped_patint_symbols.GetSize(), 1)
+
+        # bar should have been strippped.  We should not find it, or the
+        # stripping went wrong.
+        stripped_bar_symbols = stripped_target.FindSymbols("bar")
+        self.assertEqual(stripped_bar_symbols.GetSize(), 0)
+

lldb/test/API/macosx/dyld-trie-symbols/main.cpp

+int patval;          // external symbol, will not be completely stripped
+int pat(int in) {    // external symbol, will not be completely stripped
+  if (patval == 0)
+    patval = in;
+  return patval;
+}
+
+static int fooval;  // static symbol, stripped
+int foo() {         // external symbol, will not be completely stripped
+  if (fooval == 0)
+    fooval = 5;
+  return fooval;
+}
+
+int bazval = 10;   // external symbol, will not be completely stripped
+int baz () {       // external symbol, will not be completely stripped
+  return foo() + bazval;
+}
+
+static int barval = 15; // static symbol, stripped
+static int bar () {     // static symbol, stripped; __lldb_unnamed_symbol from func starts
+  return baz() + barval;
+}
+
+int calculate ()   // external symbol, will not be completely stripped
+{
+  return bar();
+}
+