[RFC] Improve linker script handing in LLD

Authors: Hongyu Chen, Daniel Thornburgh, Prabhu Karthikeyan Rajasekaran
Reviewers: Fangrui Song, Paul Kirth, Petr Hosek

Background

In contrast to high level programming languages, linker scripts suffer from inadequate support and tooling, making tasks such as writing correct linker scripts and debugging them quite challenging. To improve the status quo, the linker script lexer and parser implementation in LLD must account for the needs of embedded development such as better diagnostics, debuggability of LLD’s internal states, support for LTO code generation and even possibly developing an intermediate representation for linker script within LLD. We would like to propose a well contained improvement to the underlying data structures used in linker script parser to get us started towards the above mentioned long term goals.

Replace use of Expr lambda

Expressions in linker script are represented as lambdas within LLD. Current Expr type declaration: link

using Expr = std::function<ExprValue()>;

It was a practical choice to leverage lambdas to construct and evaluate expressions. It offers a straightforward way of implementing expression handling in the current parser implementation to help modify the global state as needed while parsing the linker script. However, this prevents us from decoupling expression evaluation from the parser.

We propose transitioning from lambdas to new, well-defined expression types (a.k.a ScriptExpr) to streamline and clarify the management of state within the linker script parser. The current challenge lies in the fact that these lambdas currently gather state from various parts of the linker, making the process opaque and difficult to manage. Our goal is to ensure that this state is systematically accessible to the expression evaluator through a well-defined context, whether this involves creating a new context object or adapting an existing one. This approach not only improves the organization of the code but also sets the stage for more maintainable and extensible future developments.

Why?

  1. Improved debuggability. Current use of callbacks makes it nearly impossible to dump linker scripts in a human-readable format which is one of our long term goals.
  2. Holding lambdas for expression evaluation limits the flexibility and efficiency of expression handling.
  3. Performance.
    1. The current lambda approach incurs a performance cost, as each assignment requires a separate memory allocation, leading to inefficiencies. By replacing `Expr` lambdas with syntactic types, we can leverage LLD’s `make` bump pointer allocation, allowing for efficient bulk allocation without requiring individual deallocations.
    2. This approach can significantly improve evaluation time by eliminating the function pointer calls inherent in lambdas, potentially replacing them with an inlined evaluator structured as a single giant switch table.

Example use of Expr lambda within LLD

Expr combine(StringRef op, Expr l, Expr r);
Expr readExpr();
Expr readExpr1(Expr lhs, int minPrec);
Expr readPrimary();
Expr readTernary(Expr cond);
Expr readParenExpr();

...
//https://github.com/llvm/llvm-project/blob/f86594788ce93b696675c94f54016d27a6c21d18/lld/ELF/ScriptParser.cpp#L1474 
if (tok == "MAX" || tok == "MIN") {                                                                
    expect("(");                                                                                     
    Expr a = readExpr();                                                                             
    expect(",");                                                                                     
    Expr b = readExpr();                                                                             
    expect(")");                                                                                     
    if (tok == "MIN")                                                                                
      return [=] { return std::min(a().getValue(), b().getValue()); };                               
    return [=] { return std::max(a().getValue(), b().getValue()); };                                 
  }  

Proposed new types

Our proposed direction is inspired by MCExpr in llvm: https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/MC/MCExpr.h.

class ScriptExpr {
// Base class for linker script expressions which are needed for parsing.
     public:
         enum class ExprKind: uint8_t {
             Constant,
             Dynamic,
             Unary,
             Binary
         };
     private:
         ExprKind kind_;
     protected:
         explicit ScriptExpr(ExprKind kind): kind_(kind) {}
     public:
         ExprKind getKind() const { return kind_; }
 };
 
 class ConstantExpr: public ScriptExpr {
// Represents a constant integer expression.
 public:
     ConstantExpr(ExprValue val):
         ScriptExpr(ExprKind::Constant), val_(val) {}
     ConstantExpr(uint64_t val):
         ScriptExpr(ExprKind::Constant), val_(ExprValue(val)) {}
     ExprValue getVal() const { return val_; }
 private:
     ExprValue val_;
 };
 
 class DynamicExpr: public ScriptExpr {
 public:
DynamicExpr(std::function<ExprValue()> impl)
         : ScriptExpr(ExprKind::Dynamic), impl_(impl) {}
std::function<ExprValue()> getImpl() const { return impl_; }

 private:
     std::function<ExprValue()> impl_;
 };
 
 class UnaryExpr: public ScriptExpr {
 public:
UnaryExpr(const ScriptExpr *operand)
: ScriptExpr(ExprKind::Unary), operand_(operand){}
private:
	const ScriptExpr *operand_;
 };

 class BinaryExpr: public ScriptExpr {
 public:
     BinaryExpr(const ScriptExpr *LHS, const ScriptExpr *RHS)
         : ScriptExpr(ExprKind::Binary), LHS(LHS), RHS(RHS) {}
 private:
     const ScriptExpr *LHS, *RHS;
 };
 

Evaluation

Following are some of the preconditions we would like to meet prior to landing our changes.

  1. All existing LLD tests pass.
  2. Add new LLD tests to reflect our changes.
  3. Performance.
    1. While proposing this new direction for handling linker script expressions, we recognize that the ultimate impact on performance remains uncertain until the implementation is complete. To address this, we plan to thoroughly profile LLD to ensure these changes do not adversely affect performance. Given that this project is more experimental in nature, it’s valuable to us to collect important insights for future developments.

Prototype implementation

Here’s a link to our work in progress implementation.
Branch: https://github.com/yugier/llvm-project/tree/lld-elf-script-expr

Please share your thoughts on the proposed changes to LLD. We invite ideas to improve our direction as well as strategies we could develop to help understand the performance impact of these changes.

3 Likes
  1. I was missing the alternatives considered section.
  2. Could lld ever interpret Python files as linker scripts:

from lld import Section;

Thank you for writing this up. These are some initial thoughts based on the RFC alone. I haven’t yet had a chance to look at the prototype.

I agree with the approach of separating the representation of the script, from the actions required to implement the script. There have been times where I’ve wanted to evaluate parts of an expression, but was not able to due to the side-effects caused by the lambda functions.

Some other areas where this kind of approach could benefit:

Measuring performance could be interesting as the majority of the larger linux/Android applications won’t use a linker script. It will still be important to measure performance of these so that the non-linker script case isn’t affected. The linux kernel is probably the largest open-source program that I know of with a complex linker script. I suspect that there may be examples in BSD too.

It could be worth looking at extreme cases of linker scripts, maybe not for average case performance, but at least to make sure there are no performance bottlenecks that only show up with large quantities. For example, auto-generating a script that puts every input section in its own output section with linker generated symbols for every output section. Large programs like web-browsers could be useful real-world inputs for these scripts.

2 Likes

Could lld ever interpret Python files as linker scripts

That is an interesting question. I think it would depend on what the programming model is in the script. Apologies if this is a little incoherent there’s quite a lot of possible ways this could work. I suspect it’s likely out of scope of the goals of the RFC.

Most, if not all, linker script languages, that I’ve come across tend to be more on the declarative side. These tend to map into a low-level internal representation that closely represent ELF data structures. This helps to abstract away the implementation details, as well as limiting the amount of errors a user can make (although linker scripts are not the best example). It does limit what the advanced user can do though.

I don’t think an imperative style python script that directly creates the low-level data structures via an API will work well. There would be too much that a user could get wrong, and it could end up limiting future expansion of the linker to support the API.

On the opposite side. a python interface that enabled some introspection such as “is this symbol defined?”, “is this section present?” that generated a linker-script or some high-level DSL could be powerful. A proprietary linker that I worked on had an interface to launch a preprocessor on the linker script prior to processing it. This enabled #include, macro expansion and conditional compilation in a convenient place, although it didn’t provide any additional introspection.

3 Likes