[RFC][PATCH] Binutils changes for RISC-V overlay system

[Ed Jones]

Hi all,

Some colleagues (Craig Blackmore and Simon Cook @ Embecosm) and I have
been working on changes to implement the proposed overlay system for
RISC-V (https://github.com/riscv-software-src/riscv-overlay/). We're
at a stage where it would be useful to get community feedback.

Below is a high level description of the system and how it's
implemented. A patch is attached which implements the binutils
changes in its entirety.


## Introduction

The RISC-V overlay system allows functions and data to exist in
one or more overlay groups which are swapped in and out of active
memory on demand by the runtime engine. The proposed changes here
cover the binutils changes necessary to link objects which use
this system.

A high level description for the overlay can be found here:
- [overlay-hld.adoc on
GitHub](https://github.com/riscv-software-src/riscv-overlay/blob/master/docs/overlay-hld.adoc)

There are also accompanying changes for Clang/LLVM:
- [LLVM patch on reviews.llvm.org](https://reviews.llvm.org/D109371)
- [Clang patch on reviews.llvm.org](https://reviews.llvm.org/D109372)

The goal of this RFC is to get feedback on the design and current
binutils changes with the aim of eventually merging the changes
with the main source tree.


## Glossary

- resident memory

  The data and code which is currently loaded and in active
  memory. Includes both memory not managed by the overlay runtime
  which is always 'resident' as well as the memory of the overlay
  group(s) which are currently loaded in.

- overlay runtime engine

  Runtime routines linked into the final executable. Tracks the
  currently loaded overlay group(s) and handles the swapping of
  groups into resident memory as appropriate.

- token

  A value which represents where a symbol can be found by the
  overlay runtime engine. Used in place of an address when
  making a call or otherwise referencing an overlay symbol.

- overlay PLT entry

  A stub function representing an overlay symbol. The stub
  functions materializes the token for the symbol and then
  calls into the overlay runtime engine. These entries are
  generated when the address of a overlay function is taken
  and used out of its original context - for example when it
  is stored in a function pointer.

- grouping file

  A `.csv` file containing a one-to-many mapping of overlay
  symbol names to the number of each group which they should
  exist in.

- grouping tool

  An optional user-provided executable that can be used to
  generate a grouping file at link time.

- grouping table

  A table generated by the linker and consumed by the overlay
  runtime engine. There is an entry for every group which
  gives the last page number for that group. By multiplying
  this by the page size the runtime engine can work out
  where the start and end of a given group is in the overlay
  memory and load it.

- multigroup table

  Holds a list for each symbol which exists in multiple groups.
  The list contains token values for each group that the
  given symbol exists in. The token value representing the
  symbol for relocations will then reference the multigroup
  table instead of directly encoding the group and offset.

- `.ovlgrps`

  The single monolithic output section which contains both
  the grouping table and multigroup table as well as the
  contents of all of the overlay groups.


## The RISC-V Overlay System

Most of the details about the overlay system can be found in the
High Level Document, however below is a brief summary leading in
to the binutils changes.

There are two primary ways a user interacts with the overlay
system.

1. By marking a function declaration with a
   `__attribute__((overlay))` attribute to signify that the
   function will be handled by the overlay system.
2. By providing a list of groups which each 'overlay' function
   exists in.

The role of the compiler and linker are to take the above
user inputs and produce an executable that can be managed by the
overlay runtime engine also linked into that executable. In more
detail the roles of the compiler and linker are as follows:

Compiler:

1. Place each symbol marked as `__attribute__((overlay))` in
   its own section identifiable by the linker. Each symbol ends
   up in a section named `.ovlinput.<symbol>`.
2. Reserve registers used exclusively by the overlay runtime
   engine.
3. Update calls to `__attribute__((overlay))` functions so that
   they are redirected through the overlay runtime engine.

Linker:

1. Read in the group assignments for each symbol from a
   user-provided grouping file, or assign groups automatically.
2. Build the grouping table which maps from a group to the
   page immediate after the end of that group.
3. Build the multigroup table which holds a one-to-many mapping
   from a symbol to a list of tokens for the multiple groups it
   exists in.
4. Assign all 'overlay' symbols into a special output section
   called `.ovlgrps`. Create duplicate input sections for symbols
   assigned to multiple groups.
5. Sort all of the 'overlay' symbol input sections within the
   `.ovlgrps` output section by their group number, with a
   special padding section between each group.
6. Fill in overlay relocations
7. Build overlay 'PLT' entries to handle indirect calls.


## Implementation details

All functions marked by the 'overlay' attribute eventually end
up in a single monolithic output section called `.ovlgrps`.
This section contains both the loadable contents of each overlay
group as well as the metadata tables consumed by the runtime
engine to locate and load groups on demand and call overlay
functions (the metadata table is also consumed by GDB when
debugging overlay executables).

The `.ovlgrps` output section is itself built from the
user-provided sections with the prefix `.ovlinput.`, and a
number of internal sections generated by the linker with the
prefix `.ovlinput.__internal.`. These linker-generated sections
are as follows:

- `.ovlinput.__internal.grouptables`

  Section containing the contents of the grouping table and the
  multigroup table. This section occupies the area allocated
  for the first group (group 0) `.ovlgrps`.

- `.ovlinput.__internal.padding.<group>`

  A special padding section which is placed after the last
  `.ovlinput.<symbol>` section assigned to a given group. This
  pads the group size up to the next `OVL_GROUP_PAGE_SIZE`.
  This section is filled with the 16-bit group number as
  padding and the final 32-bits contains a CRC of the
  entire group contents.

- `.ovlinput.__internal.duplicate.<group>.<symbol>`

  When a symbol exists in multiple overlay groups the contents
  need to be duplicated into each output group. The
  duplicate sections fulfill this role. Note that the
  original symbol and its debug information remains associated
  with the first group it is assigned to.

In addition to the above input sections there is also a linker
generated `.ovlplt` section, and unlike the other linker
generated sections this section is always held in resident
memory. The `.ovlplt` section is used to hold stub functions which
materialize an overlay token value and jump into the overlay
engine. The address of the stub function can then be used in a
normal indirect call sequence. The `.ovlplt` entries are
generated for symbols referred to by the `R_RISCV_OVLPLT_LO12_I`,
`R_RISCV_OVLPLT_HI20` and `R_RISCV_OVLPLT32` relocations.

When the linker maps the `.ovlinput` groups into `.ovlgrps`,
it does a custom sort which lays them out in the correct order.
Pseudo-code for this layout is as follows:

```
Layout .ovlinput.__internal.grouptables
Layout .ovlinput.__internal.padding.0
for each group in 1 to ${max_group}
  for each symbol in ${group}
    if .ovlinput.${symbols} exists
      Layout .ovlinput.${symbol}
    else if .ovlinput.__internal.duplicate.${group}.${symbol} exists
      Layout .ovlinput.__internal.duplicate.${group}.${symbol}
  Layout .ovlinput.__internal.padding.${group}
```

Essentially all of the sections which make up the contents of a
given overlay group are then followed by the padding section which
contains the padding, crc, and rounds the size up to the next
page boundary.

The group and offset of each `.ovlinput.<symbol>` section is
tracked, and this is used to populate the grouping table in
`.ovlinput.__internal.grouptables` and also when materializing the
token values to fill in `R_RISCV_OVLTOK_LO12_I`,
`R_RISCV_OVLTOK_HI20` and `R_RISCV_OVLTOK32` relocations.

Symbols which are assigned to multiple groups also generate
entries in the multigroup table in `.ovlinput.__internal.grouptables`,
and affect the token values which are materialized - the tokens
refer into the multigroup table instead of the grouping table.

To achieve all of the above, the entry points below are called
by the linker in approximately their listed order:

### riscv_elf_overlay_check_relocation

- Marks symbols as requiring a group assignment if they
  are referred to by any overlay relocations.
- Creates and allocates space in the `.ovlplt` section for any
  symbols referenced by overlay PLT relocations.

### riscv_elf_overlay_generate_tables

- Initializes internal data structures to track group
  assignments.
- Populates data structures with symbols that are pending
  a group assignment.
- Assigns groups using an external tool, a provided
  `.csv` grouping file, or automatically.

### riscv_elf_overlay_create_ovlgrps

- Creates the `.ovlinput.__internal.grouptables` section.

### riscv_elf_overlay_duplicate_multigroup_sections

- Creates `.ovlinput.__internal.duplicate.<group>.<symbol>`
  sections for any symbol assigned to multiple groups.

### riscv_elf_overlay_pad_groups

- Creates the padding section for each group.

### riscv_elf_overlay_sort_value

- Correctly lays out all of the user-provided and linker-generated
  input sections assigned to `.ovlgrps`

### riscv_overlay_relax_delete_bytes

- Resizes the padding section for a group when any of the
  input sections are resized due to relaxation. Ensures
  the group ends on an overlay page boundary.
- Resizes any overlay duplicate sections to match the size
  of the original.

### riscv_overlay_handle_relocation

- Materializes token values and uses them to fill in overlay
  relocations.

### riscv_overlay_finish_sections

- Fills in the `.ovlplt` entries and the grouping table and
  multigroup table in `.ovlinput.__internal.grouptables`.
- Duplicates the contents for multigroup symbols in `.ovlgrps`
  to all of their assigned groups.
- Emits the padding and crc at the end of each group.


## Open issues

This is a (probably incomplete) list of issues and questions
which need to be resolved.

- It has not yet been settled about how to avoid overlay and
  non-overlay code from being linked. This is important as the
  overlay system requires user code to avoid using a number of
  registers. We have a work in progress patch to add a new
  attribute tag `TAG_reserved_regs` which could achieve this.
  Alternatively it could be achieved through a new ABI variant.
- Currently the linker changes work by creating a bunch of input
  sections and then using a custom sort to arrange them
  appropriately in the output section along with special padding
  sections. Is there a simpler design to acheive this?
- There's a significant amount of code added to the riscv
  emulation file to parse new options, and there are also some
  changes to generic code (addition of `by_overlay` sorting)
  which are clumsy. Can these changes be isolated or made more
  generic?
- Currently the changes use custom relocation numbers. Final
  relocation numbers are awaiting allocation.
- Given the scale of the changes, how can this be maintained
  and bitrot avoided?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: binutils.patch
Type: text/x-patch
Size: 209793 bytes
Desc: not available
URL: <https://sourceware.org/pipermail/binutils/attachments/20220425/2a83a74a/attachment-0001.bin>