[PATCH v10 14/28] OAv2 merge: plumbing of generic merge logic during linkage

[Jan Beulich]

On 20.11.2025 18:59, Matthieu Longo wrote:
> This patch adds the plumbing for the OAv2 generic merge logic in the
> linker. The linker is an "advanced" consumer of OAv2. After parsing,
> it deduplicates them, merges them, detects any compatibility issues,
> and finally translates them to GNU properties.
> 
> ** Overall design
> 
> The OAv2 processing pipeline follows a map-reduce pattern. Obviously,
> the actual processing in GNU ld is not multi-threaded, and the
> operations are not necessarily executed directly one after another.
> 
> * Phase 1, map: successive per-file operations applied on the list of
>   compatible input objects.
>   1. Parsing of the OAv2 section's data (also used by objcopy).
>   2. Translation of relevant GNU properties to OAv2. This is required
>      for the backward-compatibility with input objects only marked
>      using GNU properties.
>   3. Sorting of the subsections and object attributes. Further
>      operations rely on the ordering to perform some optimization in
>      the processing of the data.
>   4. Deduplication of subsections and object attributes, and detection
>      of any conflict between duplicated subsections or tags.
>   5. Translation of relevant OAv2 to GNU properties for a forward
>      -compatibility with the GNU properties merge.
>   6. Marking of unknown subsections to skip them during the merge
>      (in phase 2), and to prune them before the output object's
>      serialization (in phase 3).
> 
> * Phase 2, reduce: OAv2 in input objects are merged together.
>   1. Gathering of "frozen" values (=coming from the command-line
>      arguments) into a virtual read-only list of subsections and
>      attributes.
>   2. Merging of OAv2 from an input file and the frozen input.
>   3. Merging of the results of step 2 together. Since the OAv2 merge
>      is commutative and associative, it can be implemented as a reduce.
>      However, GNU ld implements it as an accumulate because it does
>      not support multithreading.
>   Notes: the two merge phases also perform a marking of unsupported/
>   invalid subsections and attributes. This marking can be used for
>   debugging, and also more practically, to drop unsupported optional
>   subsections from the output.
> 
> * Phase 3, finalization of the output.
>   1. Pruning of the unknown / unsupported / invalid subsections and
>      attributes.
>   2. Serialization of OAv2 data (also used by objcopy).
>   Notes:
>    - There is no translation of the merged OAv2 to GNU properties
>      at this stage, as the GNU properties merge process has already
>      all the needed information (translated in step 5 of stage 1) to
>      produce the GNU properties equivalents.
>    - The GNU properties are currently required as the runtime linker
>      does not understand OAv2 yet.
>    - Phase 3 should also include a compatibility check between the
>      final merge result of the current link unit and input shared
>      objects. I opted for postponing this compatibility check, and
>      GNU properties merge will take care of it as it already does.

And with the split of patches, the one here deals with how much of this?
Even the paragraph ahead of the "Overall design" part looks to still
describe the entire process (but I may be wrong there).

> --- a/bfd/elf-attrs.c
> +++ b/bfd/elf-attrs.c
> @@ -18,6 +18,126 @@
>     Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
>     MA 02110-1301, USA.  */
>  
> +/* Design note regarding the merge of Object Attributes v2 during linkage
> +
> +   Entry point: _bfd_elf_link_setup_object_attributes
> +
> +   The linker is an "advanced" consumer of OAv2.  After parsing, it deduplicates
> +   them, merges them, detects any compatibility issues, and finally translates
> +   them to GNU properties.
> +
> +   ** Overall design
> +
> +   The OAv2 processing pipeline follows a map-reduce pattern.  Obviously, the
> +   actual processing in GNU ld is not multi-threaded, and the operations are not
> +   necessarily executed directly one after another.
> +
> +   * Phase 1, map: successive per-file operations applied on the list of
> +     compatible input objects.
> +     1. Parsing of the OAv2 section's data (also used by objcopy).
> +     2. Translation of relevant GNU properties to OAv2. This is required for the
> +        backward-compatibility with input objects only marked using GNU
> +        properties.
> +     3. Sorting of the subsections and object attributes. Further operations
> +        rely on the ordering to perform some optimization in the processing of
> +        the data.
> +     4. Deduplication of subsections and object attributes, and detection of any
> +        conflict between duplicated subsections or tags.
> +     5. Translation of relevant OAv2 to GNU properties for a forward
> +        -compatibility with the GNU properties merge.
> +     6. Marking of unknown subsections to skip them during the merge (in
> +        phase 2), and to prune them before the output object's serialization
> +        (in phase 3).
> +
> +   * Phase 2, reduce: OAv2 in input objects are merged together.
> +     1. Gathering of "frozen" values (=coming from the command-line arguments)
> +        into a virtual read-only list of subsections and attributes.
> +     2. Merging of OAv2 from an input file and the frozen input.
> +     3. Merging of the results of step 2 together. Since the OAv2 merge is
> +        commutative and associative, it can be implemented as a reduce.
> +        However, GNU ld implements it as an accumulate because it does not
> +        support multithreading.
> +     Notes: the two merge phases also perform a marking of unsupported / invalid
> +     subsections and attributes.  This marking can be used for debugging, and
> +     also more practically to drop unsupported optional subsections from the
> +     output.
> +
> +   * Phase 3, finalization of the output.
> +     1. Pruning of the unknown / unsupported / invalid subsections and
> +        attributes.
> +     2. Serialization of OAv2 data (also used by objcopy).
> +     Notes:
> +      - There is no translation of the merged OAv2 to GNU properties at this
> +        stage, as the GNU properties merge process has already all the needed
> +        information (translated in step 5 of stage 1) to produce the GNU
> +        properties.
> +      - The GNU properties are currently required as the runtime linker does
> +        not understand OAv2 yet.
> +      - Phase 3 should also include a compatibility check between the final
> +        merge result of the current link unit and input shared objects.  I opted
> +        for postponing this compatibility check, and GNU properties merge will
> +        take care of it as it already does.
> +
> +   The Object Ottributes merge process must handle both optional and required
> +   subsections.  It also treats the first merge of the frozen set specially, as
> +   the OAv2 list in the input BFD serves as the accumulator for subsequent
> +   merges.
> +
> +   ** Optional subsections
> +
> +   Optional subsections are processed as if merging two ordered sets — by
> +   iterating linearly through both, checking whether an element of a given
> +   ordinality is present in the opposite set, and adding it to the accumulator.
> +   The added diffuculty with subsections and attributes lies in the fact that
> +   missing elements have default values, and these must be merged with existing
> +   ones to produce the final value to be stored.
> +
> +   ** Required subsections
> +
> +   Required subsections are processed slightly differently from the optional
> +   subsections, as they cannot be pruned since they are mandatory, hence an
> +   error will be raised by the linker if it is not recognized.
> +
> +   For now, the subsection for PAuth ABI is the only one use case, and no merge
> +   is applied on the values.  The values simply need to match.
> +   This implementation choice might be challenged in the future if required
> +   subsections can have the same diversity as optional subsections.  If the case
> +   arises, the refactoring to handle this new behavior should consist in adding
> +   a new merge policy MERGE-EQUAL, or something similar.  Some "if required"
> +   should be added in the optional subsections merge logic to error on any
> +   missing elements, or mismatch, and messages should also be rephrased to point
> +   out that the error is for a required subsection.
> +
> +   ** Important note regarding support for testing
> +
> +   In order to test this generic logic, AArch64's use cases are not offering
> +   enough coverage, so a "GNU testing namespace" which corresponds to the name
> +   of the subsection was introduced.  It follows the following pattern:
> +     gnu_testing_<XXXXXX>_MERGE_<POLICY>
> +   with:
> +     - <XXXXXX>: an arbitrary name for your testing subsection.
> +     - <POLICY>: the name of the merging policy to apply on the values in the
> +       subsection.  The currently supported merge policy are:
> +         * _MERGE_AND: bitwise AND applied on numerical values.
> +         * _MERGE_OR: bitwise OR applied on numerical values.
> +         * _MERGE_ADD: concatenates strings together with a '+' in-between.
> +       Note: "_MERGE_ADD" does not make really sense, and will very likely never
> +       be used for a real merge.  Its only purpose is to test the correct
> +       handling of merges with strings.
> +   Any subsection name matching neither names supported by the backend, nor
> +   following the pattern corresponding GNU testing namespace will be considered
> +   unknown and its status set to obj_attr_subsection_v2_unknown.  This will have
> +   for consequence the pruning of this subsection.
> +
> +   Additionally, the first two tags in gnu_testing namespace, GNUTestTag_0 and
> +   GNUTestTag_1, are known, and so have a name and can be initialized to the
> +   default value ('0' or NULL) depending on the encoding specified on the
> +   subsection.  Any tags above 1 will be considered unknown, so will be default
> +   -initialized in the same way but its status will be set to obj_attr_v2_unknown.
> +   This behavior of the testing tags allows to test the pruning of unknown
> +   attributes.  */
> +
> +
>  #include "sysdep.h"

I understand this may be deliberate, but can we please avoid multiple adjacent
blank lines? They serve particularly badly as patch context.

> @@ -593,6 +713,311 @@ oav2_encoding_to_string (obj_attr_encoding_v2_t encoding)
>    return (encoding == OA_ENC_ULEB128) ? "ULEB128" : "NTBS";
>  }
>  
> +/* Structure storing the result of a search in the list of input BFDs.  */
> +typedef struct
> +{
> +  /* A pointer to a BFD.  This BFD can either point to a file having
> +     object attributes, or a candidate file which does not have any.  */
> +  bfd *pbfd;
> +
> +  /* A boolean indicating whether the file actually contains object
> +     attributes.  */
> +  bool has_object_attributes;
> +
> +  /* A pointer to the section containing the object attributes, if any
> +     were found.  */
> +  asection *sec;
> +} bfd_search_result_t;

And if multiple such sections were found, multiple instances of this struct
would result? How would they connect with one another, when there's no link
field?

> +/* Search for the first input object file containing object attributes.
> +   If no such object is found, PBFD points to the last object file that
> +   could have contained object attributes.  HAS_OBJECT_ATTRIBUTES allows
> +   to distinguish the cases when PBFD contains or does not contain object
> +   attributes.  If no candidate file is found, PBFD will stay NULL.  */

The uppercase parts of such a comment are generally understood to refer to
parameters of the function they describe; this function ...

> +static bfd_search_result_t
> +bfd_linear_find_first_with_obj_attrs (const struct bfd_link_info *info)

... only has an INFO parameter, though. (Comment applies elsewhere as well.)

> +/* Wrapper for the high-level logic of merging a single file.
> +   It handles both of the following cases:
> +   - ABFD (future REF_BFD) merged against FROZEN.
> +   - ABFD (input) and FROZEN_CFG merged into REF_BFD.
> +   The first step translates existing GNU properties to object attributes. Next,
> +   any duplicates entries in the input are merged, and the resulting object
> +   attributes are written back into GNU properties so that the GNU properties
> +   merge process can correctly diagnose potential issues. Before merging,
> +   unknown subsections and attributes are marked so they can be skipped during
> +   processing.
> +   Return True on success, False on failure.  */
> +static bool
> +oav2_merge_one (const struct bfd_link_info *info,
> +		bfd *ref_bfd, bfd *abfd,
> +		const obj_attr_subsection_list_t *frozen_cfg,
> +		bool *has_obj_attrs_after_translation)
> +{
> +    /* ABFD is an input file that may contain GNU properties, object
> +     attributes, or both.  Before merging object attributes, we must first
> +     translate any GNU properties into their equivalent object attributes
> +     (if such equivalents exist) since they may not already be present.  */
> +  oav2_translate_gnu_props_to_obj_attrs (abfd);
> +  if (has_obj_attrs_after_translation
> +      && elf_obj_attr_subsections (abfd).size > 0)
> +    *has_obj_attrs_after_translation = true;

How do you know that elf_obj_attr_subsections().size is non-zero because of
translated GNU properties (and not because there was an attributes section)?
Is the caller (by passing (non-)NULL) responsible for the distinction (in
which case imo this absolutely needs saying in the comment ahead of the
function)?

Jan