[llvm-install-name-tool] Merge rpath with id/change

[sameerarora101]

Summary

Merge -rpath option within the same loop as -id and
-change. This also simplifies -add_rpath.
Added another test case for -add_rpath to test the
new implementation. Depends on D82613

[sameerarora101]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

344

NOTE: Cannot store StringRef in OriginlRPaths (i.e cannot have set<StringRef> OriginalRPaths). This is because the StringRef CurrentRPath is a reference to the string stored inside LC and thus when we change the payload (via -rpath option) CurrentRPath is also updated to hold a reference to the new string. Hence I need to store the actual strings inside the set.

[Ktwu]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

344

nit: are these braces intentional? It's inconsistent with the other cases.

345

I think you have some options available depending on how clever you want to get with sets if you care about minimizing string cloning. Instead of tracking original rpaths, you can track operations on the config rpaths, for example (those strings shouldn't change unexpectedly beneath you, right)?

std::set<StringRef> UpdatedRPaths;

case Macho::LC_RPATH:
  StringRef CurrentRPath = ...
  auto FoundArg = ...
  if (FoundArg != end) {
    if (CurrentRPath in UpdatedRPaths) {
      // duplicate scenario
    }
    if (CurrentRPath in RPathToAdd) {
      // Also a dup scenario
    }
    updateLoadCommandPayloadString()
    UpdatedRPaths.insert(FoundArg->first);
  }
...

for (const auto &OldNew : Config.RPathsToUpdate) {
  std::tie(Old, New) = OldNew;
  if (Old not in UpdatedMap) {
    // no load command scenario
  }
  // dup scenario handled above
}

...
std::set<StringRef> AddedRPaths
for (StringRef RPath : Config.RPathToAdd) {
  if (RPath in AddedRPaths) {
    // dup
  }
  AddedRPaths.insert(RPath);
}

[jhenderson]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

344

You probably don't want a std::set here. Have you reviewed the Programmer's Manual on what set type to use?

344

I think the braces are required because of the declaration of CurrentRPath in this case statement.

351

I think the break should be inside the braces. It looks weird where it is.

356–360

I'd be tempted to move this code above the AddSection code so that all rpath related stuff is together.

[alexander-shaposhnikov]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

344

1. I wanted to mention it on one of the previous diffs but looks like I forgot - it would be better to place all the details related to updating load commands into a separate helper function rather than directly into handleArgs.

static Error updateLoadCommands(const CopyConfig &Config, Object &Obj)

handleArgs would invoke this function (updateLoadCommands) similarly to removeSections, updateAndRemoveSymbols etc.

Probably it would be even better first to refactor the code this way (on a separate diff) before moving forward if you don't mind
(now handleArgs is accumulating the details it should not really be aware of)

2. Please, take a look at StringSet, StringMap and their interfaces

(in particular, if I am not mistaken they would help you avoid some str() calls below)

Also this probably suggests that Config.RPathsToUpdate, Config.RPathsToUpdate should really be StringMap-s.

[Ktwu]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

344

Also this probably suggests that Config.RPathsToUpdate, Config.RPathsToUpdate should really be StringMap-s.

+1, although does StringMap have deterministic iteration? Maybe SetVector would work as well?

[sameerarora101]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

344

yup, that is indeed the case.

344

yup, I have replace it with a DenseSet<StringRef>

344

1. ok, so i refactored the code for updating LCs into a separate function updateLoadCommands and call that from handleArgs.

Also this probably suggests that Config.RPathsToUpdate, Config.RPathsToUpdate should really be StringMap-s.

I agree, but I think I should do that in a separate diff considering that it would require changing the way I parse options in CopyConfig.cpp. What do you think?

345

Thanks a lot for the clever tip, UpdatedRPaths.insert(FoundArg->first) was really helpful. However, I am not sure if I understood the logic completely (sorry if I missed something 😔). In particular, say I have
2 LC: lcA and lcB
and 1 -rpath option :lcB -> lcA

We want this to throw an error but it is currently passing with the above logic.

[sameerarora101]

Refactoring all load command operations into updateLoadCommands

[sameerarora101]

Adding comments over -change option

[Ktwu]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

344

What do you think?

Definitely do that in a separate diff -- it's much better to keep refactoring changes like that confined to their own diff instead of mixed up with new feature work.

345

Ah, my pseudocode is bad, sorry! You already fixed the crux of the problem I was talking about with the DenseSet<StringRef; no need to worry about my idea.

[sameerarora101]

Changing vector<Pair> to DenseMaps and refactoring

[sameerarora101]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

161

As recommended by @alexshap it is clearer to understand (and the code is cleaner too) if iterate through the LCs twice + use Maps (DenseMaps) down below.

[alexander-shaposhnikov]

I've added a few comments but other than that this version looks good to me

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

159

nit: what about renaming OriginalRPaths -> RPaths ?

161

yeah, thanks!

194

nit: FoundArg doesn't seem to be a very descriptive name

StringRef RPath = getPayloadString(LC);
StringRef NewRPath = Config.RPathsToUpdate.lookup(RPath);
...

205

StringRef InstallName = getPayloadString(LC);
NewInstallName = Config.InstallNamesToUpdate.lookup(InstallName)

[jhenderson]

llvm/tools/llvm-objcopy/CopyConfig.h

181–182 ↗

(On Diff #274659)

Would StringMap not work instead of DenseMap?

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

161

Nit here and below: you need full stops at the end of your comments.

162–165

I thought you were avoiding iterating twice over the LoadCommands before? Why are this loop and the update loop below separate?

[alexander-shaposhnikov]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

162–165

@jhenderson - I think this was my suggestion, imo splitting these steps makes the code easier to reason about.
From the performance perspective it doesn't matter much, even huge binaries have ~70 load commands.

[alexander-shaposhnikov]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

162–165

Also if I'm not mistaken it has enabled @sameerarora101 to move error reporting (lines 171 -180) earlier, before any changes / updates are made. This makes sense to me.

[sameerarora101]

llvm/tools/llvm-objcopy/CopyConfig.h

181–182 ↗

(On Diff #274659)

I think it would work too. However, if I am not mistaken, while comparing StringSet and DenseSet in a previous diff, @smeenai suggested that StringSet takes ownership of its strings (and copies them), which would be unnecessary copying (and so DenseSet would be better). I thought it would be the same case for StringMap vs DenseMap and so I implemented with DenseMap. What do you think?

[sameerarora101]

Resolving nits: changing variable names

[alexander-shaposhnikov]

LGTM

[jhenderson]

LGTM.

llvm/tools/llvm-objcopy/CopyConfig.h

181–182 ↗

(On Diff #274659)

Makes sense. I haven't looked at the data structures themselves.

FWIW, I don't think taking ownership is necessarily an issue, since there aren't going to be significant numbers of options so the string copying isn't going to be significant.

[smeenai]

llvm/tools/llvm-objcopy/CopyConfig.cpp

886 ↗

(On Diff #274811)

The pointer returned by calling .data() on a StringRef might not be null-terminated, so I don't think this is safe.

There's a form of createStringError that takes a twine instead of a format string, which is more efficient than the intermediate allocations associated with .str().c_str(). Given that this is an error path, efficiency really doesn't matter though :) The twine form should get implicitly used if you do something like

"cannot specify both -rpath " + It1->getFirst() + " " + It1->getSecond() + " and -rpath " + Old + " " + New

You could also get fancy and use the * precision specifier to specify the string length manually, instead of constructing the intermediate std::string. See https://en.cppreference.com/w/cpp/io/c/fprintf for details about *. Again though, this is purely academic; efficiency doesn't really matter that much for error paths. In other words, just doing .str().c_str() as before should be fine.

llvm/tools/llvm-objcopy/CopyConfig.h

181–182 ↗

(On Diff #274659)

Yeah, it's hard to say in general. From my understanding of the structures (and it's been a bit since I looked at them, so I may very well be mistaken):

• StringMap copies the string contents, which is unnecessary copying and memory usage.
• DenseMap allocates space for 64 key/value pairs by default (as soon as you insert a single entry), which is also unnecessary memory usage.
• StringMap does a heap allocation for every key you insert.
• DenseMap stores all key/value pairs in a single memory allocation, which is likely more cache-efficient when probing the hash table and iterating over all elements.
• StringMap caches the hash values of its keys, which means it can do cheap comparisons when probing, and doesn't need to recompute hash values when resizing the hash table.
• You can achieve the same with DenseMap by using CachedHashStringRef, however.

Over here, given the expected size of these things, I don't think it will end up mattering at all, but it is interesting to think through :)

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

63–64

Not related to this diff, but something I noticed: given that RPathsToRemove starts out as a copy of Config.RPathsToRemove and you're just removing elements from it, can't you just error out for any remaining entries in RPathsToRemove instead?

168

Can Old and New be declared inside the loop?

215

Nit: do we want to be adding new load commands in a function called updateLoadCommands? At least to me that function name seems like it should only be updating existing load commands, since we have a separate removeLoadCommands to handle removal. I'll leave it to the more experienced llvm-objcopy reviewers (@alexshap, @jhenderson) to decide if this is okay as-is or if we want a separate addLoadCommands function.

344

Good point about the deterministic iteration. Given that duplicate -rpath commands are an error instead of the last one winning out, I think non-deterministic iteration should be okay, though I haven't thought about it too hard.

[alexander-shaposhnikov]

llvm/tools/llvm-objcopy/CopyConfig.cpp

886 ↗

(On Diff #274811)

if I am not mistaken in this particular case they are null-terminated (see e.g. https://reviews.llvm.org/D81575),
but perhaps it would be better not to rely on this.

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

215

so basically the idea was to group together logical pieces of handleArgs (to some reasonable extent).
Besides error-reporting removeLoadCommands is ~10-12 lines of code, so I'd probably inline it into
updateLoadCommands for consistency.

[sameerarora101]

llvm/tools/llvm-objcopy/CopyConfig.cpp

886 ↗

(On Diff #274811)

I see, thanks! I have switched it to the twine format as suggested.

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

63–64

So the idea here was to raise an error for the first specified RPath that doesn't exist. For that purpose, we iterate through Config.RPathsToRemove and raise an error for the first RPath not deleted.

215

@alexshap Instead of inlining the whole removeLoadCommands inside updateLoadCommands I think it would cleaner if I just call

// Remove LCs.
if (Error E = removeLoadCommands(Config, Obj))
  return E;

from inside updateLoadCommands. This can allow for independent development of removeLoadCommands in future as well. What do you think? (I have updated the current diff with this change, however, I can update it again in case we want something else)

[alexander-shaposhnikov]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

215

I'm not sure that removeLoadCommands is realistically independent from updateLoadCommands, e.g. the order in which you modify the list of load commands appears to be important. Since it's small (~10 lines) it seems preferable to avoid creating this weird asymmetry between removing/adding.

[sameerarora101]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

215

I see. Ok, I have inlined removeLoadCommands into updateLoadCommands then. Thanks 😊

[sameerarora101]

Inlining removeLoadCommands into updateLoadCommands

[jhenderson]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

159

Nit: remove blank line at start of function.

215

There are two options. Either a) rename updateLoadCommands to something more generic (e.g. processLoadCommands, in which case I'd ensure all load command processing is done in that function), or b) think of it purely in conceptual terms where the load commands in the function name refers to the set of load commands, rather than each individual load command, if that makes sense. Thus you update that set by adding/removing elements, and also changing the existing elements.

[sameerarora101]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

215

I like processLoadCommands too. Updated (I can change it to something else too?)

[sameerarora101]

updateLoadCommands -> processLoadCommands

[alexander-shaposhnikov]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

215

+1

[smeenai]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

63–64

Got it. RPathsToRemove is a DenseSet though, and I don't believe that guarantees that iteration order will be the same as insertion order (or even that iteration order will be deterministic); you'd need a SetVector for that.

[sameerarora101]

updating std::tie(Old, New) = OldNew; as it was breaking on Darwin

[sameerarora101]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

196–197

this is the lates update. Would it work on Darwin? thanks

[smeenai]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

196–197

Yup, that builds. I believe this is a libc++ bug though, and I commented on https://bugs.llvm.org/show_bug.cgi?id=17550#c11

[sameerarora101]

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

196–197

ok, thanks a lot @smeenai . I'll commit this now and keep an eye on other buildbot failures

llvm/test/tools/llvm-objcopy/MachO/install-name-tool-add-rpath.test

 
 # DUPLICATE-RPATH: duplicate load command
 
 # RUN: not llvm-install-name-tool -add_rpath @executable_path/. 2>&1 \
 # RUN: | FileCheck --check-prefix=NO-INPUT %s
 
 # NO-INPUT: no input file specified
 
+## Add same RPATH twice:
+# RUN: not llvm-install-name-tool -add_rpath @executable_X \
+# RUN:                            -add_rpath @executable_X %t.i386 2>&1 \
+# RUN: | FileCheck --check-prefix=DOUBLE %s
+
+# DOUBLE: duplicate load command
+
 ## Check that cmdsize accounts for NULL terminator.
 # RUN: yaml2obj %p/Inputs/x86_64.yaml -o %t.x86_64
 # RUN: llvm-install-name-tool -add_rpath abcd %t.x86_64
 # RUN: llvm-objdump -p %t.x86_64 | FileCheck %s --check-prefix=RPATH-SIZE
 
 # RPATH-SIZE: cmd LC_RPATH
 # RPATH-SIZE-NEXT: cmdsize 24
 # RPATH-SIZE-NEXT: path abcd

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

LoadCommandPred RemovePred = [&RPathsToRemove](const LoadCommand &LC) {
     return false;
   };
 
   if (Error E = Obj.removeLoadCommands(RemovePred))
     return E;
 
   // Emit an error if the Mach-O binary does not contain an rpath path name
   // specified in -delete_rpath.
   for (StringRef RPath : Config.RPathsToRemove) {
     if (RPathsToRemove.count(RPath))
       return createStringError(errc::invalid_argument,
                                "no LC_RPATH load command with path: %s",
                                RPath.str().c_str());
   }
   return Error::success();
 }
 
 static Error removeSections(const CopyConfig &Config, Object &Obj) {
static LoadCommand buildRPathLoadCommand(StringRef Path) {
   RPathLC.path = sizeof(MachO::rpath_command);
   RPathLC.cmdsize = alignTo(sizeof(MachO::rpath_command) + Path.size() + 1, 8);
   LC.MachOLoadCommand.rpath_command_data = RPathLC;
   LC.Payload.assign(RPathLC.cmdsize - sizeof(MachO::rpath_command), 0);
   std::copy(Path.begin(), Path.end(), LC.Payload.begin());
   return LC;
 }
 
+static Error updateLoadCommands(const CopyConfig &Config, Object &Obj) {
+  DenseSet<StringRef> OriginalRPaths;
+  auto FindPair =
+      [](StringRef Old,
+         const std::vector<std::pair<StringRef, StringRef>> &Range) {
+        return find_if(Range, [=](const std::pair<StringRef, StringRef> Pair) {
+          return Pair.first == Old;
+        });
+      };
+
+  for (LoadCommand &LC : Obj.LoadCommands) {
+    switch (LC.MachOLoadCommand.load_command_data.cmd) {
+    case MachO::LC_ID_DYLIB:
+      if (Config.SharedLibId) {
+        StringRef Id = Config.SharedLibId.getValue();
+        if (Id.empty())
+          return createStringError(errc::invalid_argument,
+                                   "cannot specify an empty id");
+        updateLoadCommandPayloadString<MachO::dylib_command>(LC, Id);
+      }
+      break;
+
+    case MachO::LC_RPATH: {
+      StringRef CurrentRPath = getPayloadString(LC);
+      auto FoundArg = FindPair(CurrentRPath, Config.RPathsToUpdate);
+      if (FoundArg != Config.RPathsToUpdate.end()) {
+        updateLoadCommandPayloadString<MachO::rpath_command>(LC,
+                                                             FoundArg->second);
+        OriginalRPaths.insert(FoundArg->first);
+      } else {
+        OriginalRPaths.insert(CurrentRPath);
+      }
+      break;
+    }
+
+    case MachO::LC_LOAD_DYLIB:
+    case MachO::LC_LOAD_WEAK_DYLIB:
+      StringRef CurrentInstallName = getPayloadString(LC);
+      auto FoundArg = FindPair(CurrentInstallName, Config.InstallNamesToUpdate);
+      if (FoundArg != Config.InstallNamesToUpdate.end())
+        updateLoadCommandPayloadString<MachO::dylib_command>(LC,
+                                                             FoundArg->second);
+      break;
+    }
+  }
+
+  StringRef Old, New;
+  for (const auto &OldNew : Config.RPathsToUpdate) {
+    std::tie(Old, New) = OldNew;
+    if (OriginalRPaths.count(Old) == 0)
+      return createStringError(errc::invalid_argument,
+                               "no LC_RPATH load command with path: " + Old);
+    if (OriginalRPaths.count(New) != 0)
+      return createStringError(errc::invalid_argument,
+                               "rpath " + New +
+                                   " would create a duplicate load command");
+  }
+
+  for (StringRef RPath : Config.RPathToAdd) {
+    if (OriginalRPaths.count(RPath) != 0)
+      return createStringError(errc::invalid_argument,
+                               "rpath " + RPath +
+                                   " would create a duplicate load command");
+    OriginalRPaths.insert(RPath);
+    Obj.addLoadCommand(buildRPathLoadCommand(RPath));
+  }
+
+  return Error::success();
+}
+
 static Error dumpSectionToFile(StringRef SecName, StringRef Filename,
                                Object &Obj) {
   for (LoadCommand &LC : Obj.LoadCommands)
     for (const std::unique_ptr<Section> &Sec : LC.Sections) {
       if (Sec->CanonicalName == SecName) {
         Expected<std::unique_ptr<FileOutputBuffer>> BufferOrErr =
             FileOutputBuffer::create(Filename, Sec->Content.size());
         if (!BufferOrErr)
static Error handleArgs(const CopyConfig &Config, Object &Obj) {
 
   updateAndRemoveSymbols(Config, Obj);
 
   if (Config.StripAll)
     for (LoadCommand &LC : Obj.LoadCommands)
       for (std::unique_ptr<Section> &Sec : LC.Sections)
         Sec->Relocations.clear();
 
-  for (LoadCommand &LC : Obj.LoadCommands) {
-    switch (LC.MachOLoadCommand.load_command_data.cmd) {
-    case MachO::LC_ID_DYLIB:
-      if (Config.SharedLibId) {
-        StringRef Id = Config.SharedLibId.getValue();
-        if (Id.empty())
-          return createStringError(errc::invalid_argument,
-                                   "cannot specify an empty id");
-        updateLoadCommandPayloadString<MachO::dylib_command>(LC, Id);
-      }
-      break;
-
-    case MachO::LC_LOAD_DYLIB:
-    case MachO::LC_LOAD_WEAK_DYLIB:
-      StringRef Old, New;
-      StringRef CurrentInstallName = getPayloadString(LC);
-      for (const auto &InstallNamePair : Config.InstallNamesToUpdate) {
-        std::tie(Old, New) = InstallNamePair;
-        if (CurrentInstallName == Old) {
-          updateLoadCommandPayloadString<MachO::dylib_command>(LC, New);
-          break;
-        }
-      }
-    }
-  }
-
   for (const auto &Flag : Config.AddSection) {
     std::pair<StringRef, StringRef> SecPair = Flag.split("=");
     StringRef SecName = SecPair.first;
     StringRef File = SecPair.second;
     if (Error E = isValidMachOCannonicalName(SecName))
       return E;
     if (Error E = addSection(SecName, File, Obj))
       return E;
   }
 
   if (Error E = removeLoadCommands(Config, Obj))
     return E;
 
-  StringRef Old, New;
-  for (const auto &OldNew : Config.RPathsToUpdate) {
-    std::tie(Old, New) = OldNew;
-
-    auto FindRPathLC = [&Obj](StringRef RPath) {
-      return find_if(Obj.LoadCommands, [=](const LoadCommand &LC) {
-        return LC.MachOLoadCommand.load_command_data.cmd == MachO::LC_RPATH &&
-               getPayloadString(LC) == RPath;
-      });
-    };
-
-    auto NewIt = FindRPathLC(New);
-    if (NewIt != Obj.LoadCommands.end())
-      return createStringError(errc::invalid_argument,
-                               "rpath " + New +
-                                   " would create a duplicate load command");
-
-    auto OldIt = FindRPathLC(Old);
-    if (OldIt == Obj.LoadCommands.end())
-      return createStringError(errc::invalid_argument,
-                               "no LC_RPATH load command with path: " + Old);
-
-    updateLoadCommandPayloadString<MachO::rpath_command>(*OldIt, New);
-  }
+  if (Error E = updateLoadCommands(Config, Obj))
+    return E;
 
-  for (StringRef RPath : Config.RPathToAdd) {
-    for (LoadCommand &LC : Obj.LoadCommands) {
-      if (LC.MachOLoadCommand.load_command_data.cmd == MachO::LC_RPATH &&
-          RPath == getPayloadString(LC)) {
-        return createStringError(errc::invalid_argument,
-                                 "rpath " + RPath +
-                                     " would create a duplicate load command");
-      }
-    }
-    Obj.addLoadCommand(buildRPathLoadCommand(RPath));
-  }
   return Error::success();
 }
 
 Error executeObjcopyOnBinary(const CopyConfig &Config,
                              object::MachOObjectFile &In, Buffer &Out) {
   MachOReader Reader(In);
   std::unique_ptr<Object> O = Reader.create();
   if (!O)
     return createFileError(