[userbinator]

You allocate a fixed amount of space for the jump instruction and come back later to "patch" that jump instruction with the correct byte offset.

Also worth noting there are "short" and "near" jumps, which trade off between a shorter encoding and a longer range of destination; if the target is a forward reference, not yet known at the time the jump is assembled, then nearly all assemblers will use the long variant, because they don't know yet whether the destination will be close enough. One notable exception is fasm, which starts off with being "optimistic" about jump sizes, and then increases only the ones which didn't quite make it, repeatedly, until all the offsets are large enough. Here's a series of very detailed posts about that from its author:

https://board.flatassembler.net/topic.php?t=20249

[waterhouse]

Glancing at the posts, I have a question: do they defend against the pathological cases that require O(n) passes, and therefore at least naively have O(n^2) or worse behavior? Let's say that a jump can be encoded with either an 8-bit signed offset in 2 bytes, or a 32-bit signed offset in 5 bytes. (Supposedly x86 has a 16-bit offset version, but that uses the same opcode as the 32-bit offset, and seems unsupported in 64-bit mode.) Consider the following:

  L0: jmp M0
  L1: jmp M1
  L2: jmp M2
  ...
  L25: jmp M25
  M0: jmp N0
  M1: jmp N1
  ...
  M25: jmp N25
  N0: jmp O0
  ...
  ...
  Z0: jmp LAST
  Z1: jmp LAST
  ...
  Z25: jmp LAST
  [more than 128 bytes of unrelated stuff]
  LAST:

If all the jmps are encoded with 5 bytes, then the offset from e.g. L0 to M0 is 130 bytes, which is over the limit of 127 you can get from an 8-bit signed offset. The optimistic approach will discover in the first pass that all the Z jmps have to be 5 bytes. Pass 2, assuming it goes left to right, will see that everything up to Y24 still has offset ≤ 127 (even "Y24: jmp Z24" could be 127 bytes or 130 depending on how Y25's jump is encoded), but will find that "Y25: jmp Z25" has an offset of 130 and must be 5 bytes. Pass 3 will discover that Y24 needs to be 5 bytes too, and discover nothing else. Pass 4 will discover the sole fact that Y23 needs to be 5 bytes, and so on. If the total number of jmps here is n, then it will take close to n passes to fix up all the jmps. (If the passes go from right to left, or even alternate the direction or randomize... I think it's still possible to construct an example where pessimizing Y10 kicks Y20 over the edge, which kicks Y9 over the edge, which triggers pessimizing Y21, etc.)

This isn't a flaw unique to the optimistic approach, by the way—I could construct a similar version where all the L, M, etc. chains go from 0 to 62, and the "more than 128 bytes of unrelated stuff" becomes "0 bytes of unrelated stuff"; then, in the pessimistic approach, once the Zs have settled down, the subsequent passes will discover, one at a time, that Y62 only has a 126-byte offset and can be encoded with 2 bytes, then that Y61 can be similarly encoded, and so on.

I'm sure this doesn't actually happen in practice, unless you're compiling malicious code off the internet (in which case there are likely worse vulnerabilities inside the compiler)... but I'm curious if assemblers have nonetheless seriously addressed the problem.

One of the posts talks about NUMBER_OF_PASSES; this suggests, but I don't think the post explicitly states, that the defense mechanism is "arbitrarily limiting the number of passes". Do you know if fasm and others actually do this? (Looks like nasm has a command-line switch to turn off multi-pass branch offset optimization.)

[brandmeyer]

There's a standard technique for this that is as old as variable-length ISA's. Yes, you've identified the fundamental problem with the optimistic approach.

You do start with a pessimistic approach and assume jump distances that are the maximum length instructions. On each pass, you restrict yourself to reducing the lengths of instructions. Each pass shrinks only those instructions which currently reach their targets and recomputes only those jump distances. Yes, you can construct pathological cases where you only get to compact one insn at a time.

It doesn't matter. The goal of the asssembler is not to produce the optimal encoding, it is to produce a valid encoding. The program was valid at every step of the way. So after running N passes, you just stop and emit the program you got.

Oddly enough, its the fixed-length RISC ISA's that have a bigger problem with this. A RISC-V branch usually only has 12 bits of jump distance available. That's good enough most of the time, but 5% of the time (varying widely with the program) the target isn't in range. To handle those cases, you have to emit a longer-distance unconditional jump, and invert the logic of the parent branch to hop over the long jump instead of falling through to the 'else' label. Essentially, its a 64-bit encoding of a branch instruction with 20 bits of jump distance. Pretty sure the RISC-V assembler assumes the case of 12-bit distances in 32-bit instructions at first.

Eventually, there is a pass limit for optimistic assemblers as well. But when the limit is reached, instead of emitting a program that is less than optimal, you just return an error, because you didn't have a valid program that you could emit at all.

[elderK]

Thanks for posting this.

I've been wondering about how assemblers handle this for a very long time :)