[ELF] - Linkerscript: do not hang linker on infinite nested INCLUDE command.

[grimar]

Summary

It was easy to hang LLD when INCLUDE command including the same file.

Documentation says that nesting up to 10 levels is allowed:

INCLUDE filename
Include the linker script filename at this point. The file will be searched for in
the current directory, and in any directory specified with the ‘-L’ option. You
can nest calls to INCLUDE up to 10 levels deep.

Patch stores nesting level for each MemoryBufferRef we create,
so it is possible to error out when limit of 10 levels is reached.

[peter.smith]

Looks like a useful error message. I've checked that ld.bfd matches its documentation and has a maximum limit of 10. I've spotted one typo in the error message, and have made a minor stylistic suggestion but don't have a strong opinion on it.

ELF/ScriptLexer.cpp

93

typo: I think you meant "up to" instead of "up do". It may also be worth expressing the error explicitly, at the moment the user has to imply that they have exceeded the maximum limit. Perhaps something like "Maximum include nesting level of 10 exceeded."

ELF/ScriptLexer.h

49–50

getCurrentMB() is now returning <MemoryBuffer, depth> pair. In each of the cases where it is called only one of the two fields of the pair is used. Would it be better to have getCurrentMB() return first, and add a new function getCurrentMBDepth() that returns the second. That should allow the .firsts and .second from the calling code.

[grimar]

Thanks for comments, Peter !
I applied both your suggestions.

[ruiu]

Something's not right in this patch. I don't think you need to add code there. Instead, you could add code to ScriptParser::readInclude.

[grimar]

• Addressed review comments.

[ruiu]

This is still too clever and too complicated for a safety measure. We need more simple-minded one. I'll write it up and send it to you.

[grimar]

If favor of committed D37524.

ELF/ScriptLexer.h

public:
   StringRef next();
   StringRef peek();
   void skip();
   bool consume(StringRef Tok);
   void expect(StringRef Expect);
   bool consumeLabel(StringRef Tok);
   std::string getCurrentLocation();
 
-  std::vector<MemoryBufferRef> MBs;
+  std::vector<std::pair<MemoryBufferRef, uint8_t>> MBs;
   std::vector<StringRef> Tokens;
   bool InExpr = false;
   size_t Pos = 0;
 
 private:
   void maybeSplitExpr();
   StringRef getLine();
   size_t getLineNumber();
   size_t getColumnNumber();
 
   MemoryBufferRef getCurrentMB();
+  uint8_t getCurrentMBDepth();
 };
 
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/ScriptLexer.cpp

if (Pos)
     S += "\n>>> " + getLine().str() + "\n>>> " +
          std::string(getColumnNumber(), ' ') + "^";
   error(S);
 }
 
 // Split S into linker script tokens.
 void ScriptLexer::tokenize(MemoryBufferRef MB) {
   std::vector<StringRef> Vec;
-  MBs.push_back(MB);
+  uint8_t Depth = getCurrentMBDepth();
+  if (++Depth > 10)
+    setError("maximum include nesting level of 10 exceeded");
+
+  MBs.push_back({MB, Depth});
   StringRef S = MB.getBuffer();
   StringRef Begin = S;
 
   for (;;) {
     S = skipSpace(S);
     if (S.empty())
       break;
 
if (Tok != Expect)
     setError(Expect + " expected, but got " + Tok);
 }
 
 // Returns true if S encloses T.
 static bool encloses(StringRef S, StringRef T) {
   return S.bytes_begin() <= T.bytes_begin() && T.bytes_end() <= S.bytes_end();
 }
 
-MemoryBufferRef ScriptLexer::getCurrentMB() {
+static std::pair<MemoryBufferRef, uint8_t>
+getEnclosingMB(ArrayRef<std::pair<MemoryBufferRef, uint8_t>> V, StringRef Tok) {
   // Find input buffer containing the current token.
+  for (const std::pair<MemoryBufferRef, int8_t> &MB : V)
+    if (encloses(MB.first.getBuffer(), Tok))
+      return MB;
+  llvm_unreachable("getCurrentMB: failed to find a token");
+}
+
+MemoryBufferRef ScriptLexer::getCurrentMB() {
   assert(!MBs.empty());
   if (!Pos)
-    return MBs[0];
+    return MBs[0].first;
+  return getEnclosingMB(MBs, Tokens[Pos - 1]).first;
+}
 
-  for (MemoryBufferRef MB : MBs)
-    if (encloses(MB.getBuffer(), Tokens[Pos - 1]))
-      return MB;
-  llvm_unreachable("getCurrentMB: failed to find a token");
+uint8_t ScriptLexer::getCurrentMBDepth() {
+  if (MBs.empty() || !Pos)
+    return 0;
+  return getEnclosingMB(MBs, Tokens[Pos - 1]).second;
 }

test/ELF/linkerscript/linkerscript.s

 # RUN: FileCheck -check-prefix=INCLUDE_ERR %s < %t.log
 # INCLUDE_ERR: error: {{.+}}.script:1: cannot open foo.script
 # INCLUDE_ERR-NEXT: INCLUDE "foo.script"
 # RUN: ld.lld -L %T %t.script %t
 
 # RUN: echo "FOO(BAR)" > %t.script
 # RUN: not ld.lld -o foo %t.script > %t.log 2>&1
 # RUN: FileCheck -check-prefix=ERR1 %s < %t.log
-
 # ERR1: unknown directive: FOO
 
+# RUN: echo "INCLUDE \"%t.script3\"" > %t.script3
+# RUN: not ld.lld %t.script3 -o %t3 2>&1 | \
+# RUN:   FileCheck -check-prefix=ERR2 %s
+# ERR2: error: {{.*}}:1: maximum include nesting level of 10 exceeded
+
 .globl _start, _label
 _start:
   ret
 _label:
   ret