GitLab

Ben Gamari pushed to branch wip/T25989 at Glasgow Haskell Compiler / GHC

Commits:

f4996065

by Ben Gamari at 2025-05-17T14:28:55-04:00

rts/linker: Factor out ProddableBlocks machinery

88dc662f

by Ben Gamari at 2025-05-19T12:30:34-04:00

rts/linker: Improve efficiency of proddable blocks structure

Previously the linker's "proddable blocks" check relied on a simple
linked list of spans. This resulted in extremely poor complexity while
linking objects with lots of small sections (e.g. objects built with
split sections).

Rework the mechanism to instead use a simple interval set implemented
via binary search.

Fixes #26009.

8 changed files:

rts/Linker.c
rts/LinkerInternals.h
rts/linker/Elf.c
rts/linker/MachO.c
rts/linker/PEi386.c
+ rts/linker/ProddableBlocks.c
+ rts/linker/ProddableBlocks.h
rts/rts.cabal

Changes:

rts/Linker.c

@@ -1194,7 +1194,7 @@ void freeObjectCode (ObjectCode *oc)
          stgFree(oc->sections);
+     }
 -    freeProddableBlocks(oc);
 +    freeProddableBlocks(&oc->proddables);
      freeSegments(oc);
      /* Free symbol_extras.  On x86_64 Windows, symbol_extras are allocated
@@ -1279,7 +1279,7 @@ mkOc( ObjectType type, pathchar *path, char *image, int imageSize,
     oc->sections          = NULL;
     oc->n_segments        = 0;
     oc->segments          = NULL;
 -   oc->proddables        = NULL;
 +   initProddableBlockSet(&oc->proddables);
     oc->foreign_exports   = NULL;
  #if defined(NEED_SYMBOL_EXTRAS)
     oc->symbol_extras     = NULL;
@@ -1834,50 +1834,6 @@ OStatus getObjectLoadStatus (pathchar *path)
      return r;
+ }
 -/* -----------------------------------------------------------------------------
 - * Sanity checking.  For each ObjectCode, maintain a list of address ranges
 - * which may be prodded during relocation, and abort if we try and write
 - * outside any of these.
 - */
 -void
 -addProddableBlock ( ObjectCode* oc, void* start, int size )
 -{
 -   ProddableBlock* pb
 -      = stgMallocBytes(sizeof(ProddableBlock), "addProddableBlock");
+-
 -   IF_DEBUG(linker, debugBelch("addProddableBlock: %p %p %d\n", oc, start, size));
 -   ASSERT(size > 0);
 -   pb->start      = start;
 -   pb->size       = size;
 -   pb->next       = oc->proddables;
 -   oc->proddables = pb;
 -}
+-
 -void
 -checkProddableBlock (ObjectCode *oc, void *addr, size_t size )
 -{
 -   ProddableBlock* pb;
+-
 -   for (pb = oc->proddables; pb != NULL; pb = pb->next) {
 -      char* s = (char*)(pb->start);
 -      char* e = s + pb->size;
 -      char* a = (char*)addr;
 -      if (a >= s && (a+size) <= e) return;
 -   }
 -   barf("checkProddableBlock: invalid fixup in runtime linker: %p", addr);
 -}
+-
 -void freeProddableBlocks (ObjectCode *oc)
 -{
 -    ProddableBlock *pb, *next;
+-
 -    for (pb = oc->proddables; pb != NULL; pb = next) {
 -        next = pb->next;
 -        stgFree(pb);
 -    }
 -    oc->proddables = NULL;
 -}
+-
  /* -----------------------------------------------------------------------------
   * Section management.
   */

rts/LinkerInternals.h

@@ -12,6 +12,7 @@
  #include "RtsSymbols.h"
  #include "Hash.h"
  #include "linker/M32Alloc.h"
 +#include "linker/ProddableBlocks.h"
  #if RTS_LINKER_USE_MMAP
  #include <sys/mman.h>
@@ -175,14 +176,6 @@ struct _Section {
    struct SectionFormatInfo* info;
  };
 -typedef
 -   struct _ProddableBlock {
 -      void* start;
 -      int   size;
 -      struct _ProddableBlock* next;
 -   }
 -   ProddableBlock;
+-
  typedef struct _Segment {
      void *start;                /* page aligned start address of a segment */
      size_t size;                /* page rounded size of a segment */
@@ -328,7 +321,7 @@ struct _ObjectCode {
      /* SANITY CHECK ONLY: a list of the only memory regions which may
         safely be prodded during relocation.  Any attempt to prod
         outside one of these is an error in the linker. */
 -    ProddableBlock* proddables;
 +    ProddableBlockSet proddables;
  #if defined(NEED_SYMBOL_EXTRAS)
      SymbolExtra    *symbol_extras;
@@ -434,10 +427,6 @@ void exitLinker( void );
  void freeObjectCode (ObjectCode *oc);
  SymbolAddr* loadSymbol(SymbolName *lbl, RtsSymbolInfo *pinfo);
 -void addProddableBlock ( ObjectCode* oc, void* start, int size );
 -void checkProddableBlock (ObjectCode *oc, void *addr, size_t size );
 -void freeProddableBlocks (ObjectCode *oc);
+-
  void addSection (Section *s, SectionKind kind, SectionAlloc alloc,
                   void* start, StgWord size, StgWord mapped_offset,
                   void* mapped_start, StgWord mapped_size);

rts/linker/Elf.c

@@ -924,7 +924,7 @@ ocGetNames_ELF ( ObjectCode* oc )
            oc->sections[i].info->stubs = NULL;
  #endif
 -          addProddableBlock(oc, start, size);
 +          addProddableBlock(&oc->proddables, start, size);
        } else {
            addSection(&oc->sections[i], kind, alloc, oc->image+offset, size,
 , 0, 0);
@@ -1272,7 +1272,7 @@ do_Elf_Rel_relocations ( ObjectCode* oc, char* ehdrC,
                  debugBelch("Reloc: P = %p   S = %p   A = %p   type=%d\n",
                             (void*)P, (void*)S, (void*)A, reloc_type ));
  #if defined(DEBUG)
 -       checkProddableBlock ( oc, pP, sizeof(Elf_Word) );
 +       checkProddableBlock ( &oc->proddables, pP, sizeof(Elf_Word) );
  #else
         (void) pP; /* suppress unused varialbe warning in non-debug build */
  #endif
@@ -1684,7 +1684,7 @@ do_Elf_Rela_relocations ( ObjectCode* oc, char* ehdrC,
  #if defined(DEBUG)
        IF_DEBUG(linker_verbose,debugBelch("Reloc: P = %p   S = %p   A = %p\n",
                                           (void*)P, (void*)S, (void*)A ));
 -      checkProddableBlock(oc, (void*)P, sizeof(Elf_Word));
 +      checkProddableBlock(&oc->proddables, (void*)P, sizeof(Elf_Word));
  #endif
  #if defined(powerpc_HOST_ARCH) || defined(x86_64_HOST_ARCH)

rts/linker/MachO.c

@@ -253,7 +253,7 @@ resolveImports(
              return 0;
+         }
 -        checkProddableBlock(oc,
 +        checkProddableBlock(&oc->proddables,
                              ((void**)(oc->image + sect->offset)) + i,
                              sizeof(void *));
          ((void**)(oc->image + sect->offset))[i] = addr;
@@ -287,7 +287,7 @@ decodeAddend(ObjectCode * oc, Section * section, MachORelocationInfo * ri) {
      /* the instruction. It is 32bit wide */
      uint32_t * p = (uint32_t*)((uint8_t*)section->start + ri->r_address);
 -    checkProddableBlock(oc, (void*)p, 1 << ri->r_length);
 +    checkProddableBlock(&oc->proddables, (void*)p, 1 << ri->r_length);
      switch(ri->r_type) {
          case ARM64_RELOC_UNSIGNED: {
@@ -364,7 +364,7 @@ encodeAddend(ObjectCode * oc, Section * section,
               MachORelocationInfo * ri, int64_t addend) {
      uint32_t * p = (uint32_t*)((uint8_t*)section->start + ri->r_address);
 -    checkProddableBlock(oc, (void*)p, 1 << ri->r_length);
 +    checkProddableBlock(&oc->proddables, (void*)p, 1 << ri->r_length);
      switch (ri->r_type) {
          case ARM64_RELOC_UNSIGNED: {
@@ -788,7 +788,7 @@ relocateSection(ObjectCode* oc, int curSection)
              default:
                  barf("Unknown size.");
+         }
 -        checkProddableBlock(oc,thingPtr,relocLenBytes);
 +        checkProddableBlock(&oc->proddables,thingPtr,relocLenBytes);
          /*
           * With SIGNED_N the relocation is not at the end of the
@@ -1034,9 +1034,9 @@ relocateSection(ObjectCode* oc, int curSection)
           */
          if (0 == reloc->r_extern) {
              if (reloc->r_pcrel) {
 -                checkProddableBlock(oc, (void *)((char *)thing + baseValue), 1);
 +                checkProddableBlock(&oc->proddables, (void *)((char *)thing + baseValue), 1);
              } else {
 -                checkProddableBlock(oc, (void *)thing, 1);
 +                checkProddableBlock(&oc->proddables, (void *)thing, 1);
+             }
+         }
@@ -1343,7 +1343,7 @@ ocGetNames_MachO(ObjectCode* oc)
                  secArray[sec_idx].info->stub_size = 0;
                  secArray[sec_idx].info->stubs = NULL;
  #endif
 -                addProddableBlock(oc, start, section->size);
 +                addProddableBlock(&oc->proddables, start, section->size);
+             }
              curMem = (char*) secMem + section->size;

rts/linker/PEi386.c

@@ -1658,7 +1658,7 @@ ocGetNames_PEi386 ( ObjectCode* oc )
+       }
        addSection(section, kind, SECTION_NOMEM, start, sz, 0, 0, 0);
 -      addProddableBlock(oc, oc->sections[i].start, sz);
 +      addProddableBlock(&oc->proddables, oc->sections[i].start, sz);
+    }
     /* Copy exported symbols into the ObjectCode. */
@@ -1690,7 +1690,7 @@ ocGetNames_PEi386 ( ObjectCode* oc )
                    SECTIONKIND_RWDATA, SECTION_MALLOC,
                    bss, globalBssSize, 0, 0, 0);
         IF_DEBUG(linker_verbose, debugBelch("bss @ %p %" FMT_Word "\n", bss, globalBssSize));
 -       addProddableBlock(oc, bss, globalBssSize);
 +       addProddableBlock(&oc->proddables, bss, globalBssSize);
     } else {
         addSection(&oc->sections[oc->n_sections-1],
                    SECTIONKIND_OTHER, SECTION_NOMEM, NULL, 0, 0, 0, 0);
@@ -2067,13 +2067,13 @@ ocResolve_PEi386 ( ObjectCode* oc )
           IF_DEBUG(linker_verbose, debugBelch("S=%zx\n", S));
           /* All supported relocations write at least 4 bytes */
 -         checkProddableBlock(oc, pP, 4);
 +         checkProddableBlock(&oc->proddables, pP, 4);
           switch (reloc->Type) {
  #if defined(x86_64_HOST_ARCH)
              case 1: /* R_X86_64_64 (ELF constant 1) - IMAGE_REL_AMD64_ADDR64 (PE constant 1) */
+                {
                     uint64_t A;
 -                   checkProddableBlock(oc, pP, 8);
 +                   checkProddableBlock(&oc->proddables, pP, 8);
                     A = *(uint64_t*)pP;
                     *(uint64_t *)pP = S + A;
                     break;
@@ -2114,7 +2114,7 @@ ocResolve_PEi386 ( ObjectCode* oc )
+                {
                     /* mingw will emit this for a pc-rel 64 relocation */
                     uint64_t A;
 -                   checkProddableBlock(oc, pP, 8);
 +                   checkProddableBlock(&oc->proddables, pP, 8);
                     A = *(uint64_t*)pP;
                     *(uint64_t *)pP = S + A - (intptr_t)pP;
                     break;

rts/linker/ProddableBlocks.c

 +/* -----------------------------------------------------------------------------
 + *
 + * (c) The GHC Team, 2025
 + *
 + * RTS Object Linker
 + *
 + * ---------------------------------------------------------------------------*/
++
++
 +/*
 + * Sanity checking.  For each ObjectCode, maintain a list of address ranges
 + * which may be prodded during relocation, and abort if we try and write
 + * outside any of these.
 + */
++
 +#include "Rts.h"
 +#include "RtsUtils.h"
 +#include "linker/ProddableBlocks.h"
++
 +#include <stdlib.h>
 +#include <string.h>
++
 +typedef struct _ProddableBlock {
 +    uintptr_t start;  // inclusive
 +    uintptr_t end;    // inclusive
 +} ProddableBlock;
++
 +void
 +initProddableBlockSet ( ProddableBlockSet* set )
 +{
 +    set->data = NULL;
 +    set->capacity = 0;
 +    set->size = 0;
 +}
++
 +void freeProddableBlocks (ProddableBlockSet *set)
 +{
 +    stgFree(set->data);
 +    set->data = NULL;
 +    set->size = 0;
 +    set->capacity = 0;
 +}
++
 +// Binary search for the first interval with start >= value. Returns index or
 +// size if none.
 +static size_t
 +findLower(const ProddableBlockSet *set, uintptr_t value)
 +{
 +    size_t l = 0;
 +    size_t r = set->size;
 +    while (l < r) {
 +        size_t mid = l + (r - l) / 2;
 +        if (set->data[mid].start < value) {
 +            l = mid + 1;
 +        } else {
 +            r = mid;
 +        }
 +    }
 +    return l;
 +}
++
 +// Check whether a given value is a member of the set.
 +bool
 +containsSpan ( const ProddableBlockSet *set, uintptr_t start, uintptr_t end )
 +{
 +    size_t i = findLower(set, start+1);
 +    return i > 0
 +      && set->data[i-1].start <= start
 +      && end <= set->data[i-1].end;
 +}
++
 +void
 +checkProddableBlock (const ProddableBlockSet *set, void *addr, size_t size )
 +{
 +    if (! containsSpan(set, (uintptr_t) addr, (uintptr_t) addr+size)) {
 +        barf("checkProddableBlock: invalid fixup in runtime linker: %p", addr);
 +    }
 +}
++
 +// Ensure capacity for at least new_capacity intervals
 +static void
 +ensureCapacity(ProddableBlockSet *set, size_t new_capacity) {
 +    if (new_capacity > set->capacity) {
 +        size_t cap = set->capacity ? set->capacity * 2 : 4;
 +        if (cap < new_capacity) {
 +            cap = new_capacity;
 +        }
 +        ProddableBlock *tmp = stgReallocBytes(set->data, cap * sizeof(ProddableBlock), "addProddableBlock");
 +        set->data = tmp;
 +        set->capacity = cap;
 +    }
 +}
++
 +void
 +addProddableBlock ( ProddableBlockSet* set, void* start_ptr, size_t size )
 +{
 +    const uintptr_t start = (uintptr_t) start_ptr;
 +    const uintptr_t end = (uintptr_t) start + size;
 +    size_t i = findLower(set, start);
++
 +    // check previous interval if it is overlapping or adjacent
 +    if (i > 0 && start <= set->data[i-1].end + 1) {
 +        // merge with left interval
 +        i--;
 +        if (end > set->data[i].end) {
 +            set->data[i].end = end;
 +        }
 +    } else {
 +        // insert new interval
 +        ensureCapacity(set, set->size + 1);
 +        memmove(&set->data[i+1], &set->data[i], sizeof(ProddableBlock) * (set->size - i));
 +        set->data[i].start = start;
 +        set->data[i].end = end;
 +        set->size++;
 +    }
++
 +    // coalesce overlaps on right
 +    size_t j = i;
 +    while (j < set->size && set->data[j].start <= set->data[i].end + 1) {
 +        set->data[i].end = set->data[j].end;
 +        j++;
 +    }
++
 +    if (j != i) {
 +        memmove(&set->data[i+1], &set->data[j], sizeof(ProddableBlock) * (set->size - j));
 +        set->size -= j - i - 1;
 +    }
 +}
++

rts/linker/ProddableBlocks.h

 +/* -----------------------------------------------------------------------------
 + *
 + * (c) The GHC Team, 2025
 + *
 + * RTS Object Linker
 + *
 + * ---------------------------------------------------------------------------*/
++
 +#pragma once
++
 +#include <stdbool.h>
 +#include <stddef.h>
 +#include <stdint.h>
++
 +// An interval set on uintptr_t.
 +struct _ProddableBlock;
++
 +typedef struct {
 +    size_t size;
 +    size_t capacity;
 +    // sorted list of disjoint (start,end) pairs
 +    struct _ProddableBlock *data;
 +} ProddableBlockSet;
++
 +void initProddableBlockSet ( ProddableBlockSet* set );
++
 +// Insert an interval.
 +void addProddableBlock ( ProddableBlockSet* set, void* start, size_t size );
++
 +// Check that an address belongs to the set.
 +void checkProddableBlock (const ProddableBlockSet *set, void *addr, size_t size );
++
++
 +// Free a set.
 +void freeProddableBlocks (ProddableBlockSet *set);
++
 +// For testing.
 +bool containsSpan ( const ProddableBlockSet *set, uintptr_t start, uintptr_t end );

rts/rts.cabal

@@ -491,6 +491,7 @@ library
                   linker/MachO.c
                   linker/macho/plt.c
                   linker/macho/plt_aarch64.c
 +                 linker/ProddableBlocks.c
                   linker/PEi386.c
                   linker/SymbolExtras.c
                   linker/elf_got.c