To: gmp-bugs@gmplib.org
Subject: GMP 6.3.0 x86_64 Darwin: mpn_rsh1add_nc/mpn_rsh1sub_nc jump into the
         stub table, crashing every FFT multiply and square

Summary
=======

On x86_64 macOS, GMP 6.3.0 built with assembly enabled produces a libgmp in
which mpn_rsh1add_nc and mpn_rsh1sub_nc jump into the middle of the Mach-O
symbol stub table instead of into their shared code path.  Calling either one
crashes immediately.

Because mpn_mulmod_bnm1 and mpn_sqrmod_bnm1 call mpn_rsh1add_nc when
HAVE_NATIVE_mpn_rsh1add_nc is defined, every multiplication and squaring that
reaches the FFT range dies:

  mpz_mul(c,a,a)  crashes at exactly 4224 limbs  (= SQR_FFT_THRESHOLD)
  mpz_mul(c,a,b)  crashes at exactly 6272 limbs  (= MUL_FFT_THRESHOLD)

One limb below each threshold everything is fine.  `make -k check` fails 28 of
178 tests.  A --disable-assembly build of the same tarball on the same machine
passes 177/178 (1 skip, 0 fail).

The assembly source and the assembled object file are both correct.  The
damage is done by the static linker.

GMP version
===========

GMP 6.3.0, the official release tarball, unpatched.

  sha256(gmp-6.3.0.tar.xz) =
    a3c2b80201b89e68616f4ad30bc66aee4927c3ce50e33929ca819d5c43538898

Not pre-packaged and not patched.  Checked "Known Build Problems" in the
manual; the only MacOS X entry there concerns libtool and shared libraries and
is unrelated.

What is wrong
=============

mpn/x86_64/coreisbr/rsh1aors_n.asm defines the carry-in entry point and the
plain entry point as two separate global symbols, with the former jumping into
a label inside the latter:

	ALIGN(16)
  PROLOGUE(func_nc)
	FUNC_ENTRY(4)
  IFDOS(`	mov	56(%rsp), %r8	')
	push	%rbx
	push	%rbp

	neg	%r8			C set C flag from parameter
	mov	(up), %rbp
	ADCSBB	(vp), %rbp

	jmp	L(ent)			<--- into the middle of func_n
  EPILOGUE()

	ALIGN(16)
  PROLOGUE(func_n)
	FUNC_ENTRY(4)
	push	%rbx
	push	%rbp

	mov	(up), %rbp
	ADDSUB	(vp), %rbp
  L(ent):
	sbb	R32(%rbx), R32(%rbx)	C save cy
	...

Because L(ent) sits inside the range of another *global* symbol, the Darwin
assembler cannot resolve the branch locally.  It emits an external
X86_64_RELOC_BRANCH relocation against ___gmpn_rsh1add_n with addend +8.  The
object file is still correct:

  $ nm -n mpn/.libs/rsh1add_n.o
  0000000000000000 T ___gmpn_rsh1add_nc
  0000000000000010 T ___gmpn_rsh1add_n

  ___gmpn_rsh1add_nc:
     0: 53              pushq %rbx
     1: 55              pushq %rbp
     2: 49f7d8          negq  %r8
     5: 488b2e          movq  (%rsi), %rbp
     8: 48132a          adcq  (%rdx), %rbp
     b: e908000000      jmp   ___gmpn_rsh1add_n+8      <-- 0x18 == L(ent), correct
  ___gmpn_rsh1add_n:
    10: 53              pushq %rbx
    11: 55              pushq %rbp
    12: 488b2e          movq  (%rsi), %rbp
    15: 48032a          addq  (%rdx), %rbp
    18: 19db            sbbl  %ebx, %ebx               <-- L(ent)

  $ otool -r mpn/.libs/rsh1add_n.o
  address  pcrel length extern type    scattered symbolnum/value
  0000000c 1     2      1      2       0         0

After linking into libgmp.10.dylib, the branch has been redirected through the
symbol stub table, with the +8 addend applied to the *stub* address:

  libgmp.10.dylib`__gmpn_rsh1add_nc:
    0x1000d8130 <+0>:  pushq  %rbx
    0x1000d8131 <+1>:  pushq  %rbp
    0x1000d8132 <+2>:  negq   %r8
    0x1000d8135 <+5>:  movq   (%rsi), %rbp
    0x1000d8138 <+8>:  adcq   (%rdx), %rbp
    0x1000d813b <+11>: jmp    0x1000e26c1   ; symbol stub for: __gmpn_rsh1add_nc + 2

__gmpn_rsh1add_n starts at 0x1000d8140, so the jump should go to 0x1000d8148.
It goes to 0x1000e26c1 instead, which is 2 bytes into a 6-byte stub entry in
the __stubs section.  Execution resumes mid-instruction and the process dies.

The same happens to mpn_rsh1sub_nc (same source file, same structure); there
it lands on a different garbage instruction and raises SIGILL rather than
SIGSEGV.

mpn_add_nc and mpn_sub_nc have the same source structure but happen to link
correctly in this build, so the problem is not universal across the _nc/_n
pairs -- but it is not confined to rsh1 either.  Linking libgmp.a statically
shows how widespread the underlying "branch to global symbol + addend" pattern
is; ld refuses the link outright:

  ld: Found illegal text-relocations
    text-relocation in '___gmpn_add_nc'+0x218 (add_n.o) to '___gmpn_add_n'
    text-relocation in '___gmpn_sub_nc'+0x1E0 (sub_n.o) to '___gmpn_sub_n'
    text-relocation in '___gmpn_mul_1'+0x20 (mul_1.o) to '___gmpn_mul_1'
    text-relocation in '___gmpn_addmul_1'+0x20 (addmul_1.o) to '___gmpn_addmul_1'
    text-relocation in '___gmpn_mul_basecase'+0x358 (mul_basecase.o) to '___gmpn_mul_basecase'
    text-relocation in '___gmpn_sqr_basecase'+0xC98 (sqr_basecase.o) to '___gmpn_sqr_basecase'
    text-relocation in '___gmpn_mod_34lsub1'+0x98 (mod_34lsub1.o) to '___gmpn_mod_34lsub1'
    text-relocation in '___gmpn_addlsh_n'+0x1A8 (addlsh_n.o) to '___gmpn_addlsh_n'
    text-relocation in '___gmpn_bdiv_q_1'+0x19 (bdiv_q_1.o) to '___gmp_binvert_limb_table'
    ... (many more)

  ld: warning: disabling chained fixups because of unaligned pointers

Isolating the cause
===================

Three builds from the same tarball on the same machine with the same compiler:

  A. ./configure                        -> crashes (asm + x86_64/skylake mparam)
  B. ./configure --disable-assembly     -> clean  (C + generic mparam)
  C. ./configure --disable-assembly,
     then gmp-mparam.h replaced by
     mpn/x86_64/skylake/gmp-mparam.h    -> clean  (C + x86_64/skylake mparam)

C is the important one.  It uses byte-for-byte the same FFT thresholds and
FFT_TABLE3 entries as A -- MUL_FFT_THRESHOLD 6272, SQR_FFT_THRESHOLD 4224 --
and is completely clean at 4224 and 6272 limbs.  So the threshold table is not
implicated; the assembly build is.

I also confirmed that build B genuinely exercises the FFT code rather than
avoiding it, by breaking on __gmpn_mul_fft:

  * frame #0: __gmpn_mul_fft
    frame #1: __gmpn_sqrmod_bnm1 + 1196
    frame #2: __gmpn_sqrmod_bnm1 + 701

Below the FFT thresholds, builds A and B agree bit for bit.  Over every size
from 1 to 1200 limbs and then strided to 4223, balanced and unbalanced, mul
and sqr, an FNV hash of all results is identical:

  --disable-assembly   hash=1deba5f5a9c454a9
  assembly             hash=1deba5f5a9c454a9

and both pass an independent check that trusts neither library (reduce the
operands mod 2^61-1 with mpn_mod_1, multiply the residues in one limb, compare
against the product's residue): 0 failures.

Test programs
=============

Two are attached.

reproducer/rsh1add_nc.c -- the minimal one.  Calls the two entry points
directly with 16 limbs.  Operand size is irrelevant; no FFT needed.

  $ cc -O2 -I<prefix>/include rsh1add_nc.c -o rsh1add_nc \
       -L<prefix>/lib -lgmp -Wl,-rpath,<prefix>/lib
  $ ./rsh1add_nc
  calling __gmpn_rsh1add_n  ... returned 1
    result matches reference: yes
  calling __gmpn_rsh1add_nc ... Segmentation fault: 11

(This one only links against an assembly-enabled build; --disable-assembly has
no native mpn_rsh1add_n{,c}.)

reproducer/mpz_sqr_fft.c -- the same bug through the documented API, no
internal symbols:

  $ ./mpz_sqr_fft 4223
  mpz_mul(c,a,a) with 4223 limbs ... ok
  $ ./mpz_sqr_fft 4224
  mpz_mul(c,a,a) with 4224 limbs ... Segmentation fault: 11

reproducer/run.sh builds and runs both against a prefix you give it.

Backtrace
=========

  * thread #1, queue = 'com.apple.main-thread',
    stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
      frame #0: 0x00000001000ff6c3 libgmp.10.dylib`__gmpn_rsh1add_nc + 4
  libgmp.10.dylib`__gmpn_rsh1add_nc:
  ->  0x1000ff6c3 <+4>: addl   %eax, (%rax)
  libgmp.10.dylib`__gmpn_rsh1sub_n:
      0x1000ff6c5 <+0>: jmpq   *0x12f05(%rip)
  libgmp.10.dylib`__gmpn_rshift:
      0x1000ff6cb <+0>: jmpq   *0x12f07(%rip)

There are no further frames: the jump lands mid-instruction in the stub table
and the stack is not a valid frame at that point.  The symbol names shown are
the nearest preceding *stub* entries (6 bytes apart), not the real functions.

Configuration
=============

Failing build:

  ../configure --prefix=<pfx>

  Version:           GNU MP 6.3.0
  Host type:         kabylake-apple-darwin24.6.0
  ABI:               64
  Compiler:          gcc
  Static libraries:  yes
  Shared libraries:  yes

  CFLAGS='-O2 -pedantic -fomit-frame-pointer -m64 -mtune=skylake -march=broadwell'

  config.status: linking ../mpn/x86_64/coreisbr/rsh1aors_n.asm to mpn/rsh1add_n.asm
  config.status: linking ../mpn/x86_64/coreisbr/rsh1aors_n.asm to mpn/rsh1sub_n.asm
  config.status: linking ../mpn/x86_64/coreibwl/mul_basecase.asm to mpn/mul_basecase.asm
  config.status: linking ../mpn/x86_64/coreibwl/addmul_1.asm to mpn/addmul_1.asm
  config.status: linking ../mpn/x86_64/skylake/gmp-mparam.h to gmp-mparam.h

Working build:

  ../configure --prefix=<pfx> --disable-assembly

System
======

  $ uname -a
  Darwin 24.6.0 Darwin Kernel Version 24.6.0: Tue Jul 21 20:50:07 PDT 2026;
  root:xnu-11417.140.69.711.44~1/RELEASE_X86_64 x86_64

  macOS 15.7.9 (24G830), Intel Core i9-9980HK (Coffee Lake), MacBookPro15,1

  $ ./config.guess
  kabylake-apple-darwin24.6.0

  $ ./configfsf.guess
  x86_64-apple-darwin24.6.0

  $ gcc -v                     # /usr/bin/gcc, the Xcode clang shim
  Apple clang version 17.0.0 (clang-1700.6.4.2)
  Target: x86_64-apple-darwin24.6.0
  Thread model: posix
  InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/
                XcodeDefault.xctoolchain/usr/bin

  $ ld -v
  @(#)PROGRAM:ld  PROJECT:ld-1230.1
  BUILD 10:12:58 Jan  9 2026

The linker version looks central here, since the object file is correct and
only the linked image is wrong.  A GMP 6.2.0 shared library built on this same
machine some years ago with an older Xcode does *not* crash at these sizes;
I have not rebuilt 6.2.0 with the current toolchain, so that is suggestive of
a linker change rather than proof of one, and the GMP version differs too.

Ruled out
=========

  - Not stack exhaustion from TMP_ALLOC: raising the stack limit to 64 MB
    changes nothing, and both the working and failing builds use
    WANT_TMP_ALLOCA.
  - Not the FFT threshold table: build C above uses the identical table and
    is clean.
  - Not the assembler or the .asm source: the object file disassembles
    correctly and its single relocation is the expected one.

Workaround
==========

Configure with --disable-assembly.  That build passes 177/178 tests and, below
the FFT thresholds, is bit-identical to the assembly build.  It is of course
much slower.  Measured here with mpz_mul, both builds from this same 6.3.0
tarball, at sizes below the crash thresholds (best of 7, idle machine):

    operand      --disable-assembly      assembly       ratio
      1 Kbit             566.8 ns        112.3 ns        5.0x
      4 Kbit            5382.6 ns       1161.8 ns        4.6x
     64 Kbit           293.3   us        75.2  us        3.9x
    256 Kbit             1.365 ms       514.9   us       2.7x

Possible fix
============

The cross-symbol branch is what the Darwin toolchain mishandles.  Making the
shared tail reachable without a branch into another global symbol's body would
avoid it -- for instance by duplicating the few preamble instructions into
func_nc so it does not need `jmp L(ent)` at all, or by arranging the shared
code so that its label is not interior to a second global symbol.  You will
know far better than I do which shape fits the rest of the mpn asm.

Files attached
==============

  reproducer/rsh1add_nc.c    minimal reproducer (internal entry points)
  reproducer/mpz_sqr_fft.c   reproducer through the public API
  reproducer/run.sh          builds and runs both against a given prefix
  evidence/object-code.txt   .asm source, .o symbols, relocation, disassembly
  evidence/linked-code.txt   the same function after linking, and the crash
  evidence/configure.txt     configure summaries for both builds
  evidence/testsuite.txt     make check results for both builds
  evidence/static-link.txt   the illegal-text-relocation link failure
  evidence/environment.txt   uname, config.guess, configfsf.guess, cc, ld
