Decode the destination operand of BSR/BSF as a second source.

From peter.goodman on June 06, 2013 18:11:38

Problem: OP_bsr/OP_bsf are 1dst, 1src. The AMD64 manual specifies that the destination operand is unchanged when the source operand is zero. The Intelx86-64 manual specifies that the destination operand is undefined when the source is zero; however, evidence [1] suggests that Intel64 behaves in the same way as AMD64.

Importance: When doing a reverse scan of instructions to revive/kill registers, visiting BSF/BSR will inadvertently mark the destination operand (if it is a register) as dead. If instrumentation is added before such an instruction that clobbers this register then programs (e.g. older versions of the Linux kernel than cited in [1]) that depend on the destination operand being unchanged will inadvertently clobber the destination operand, and likely result in undefined behaviour.

Context: Instrumenting Linux kernel code, and Linux kernel modules using either DynamoRIO Kernel or Granary (which internally uses DR's instruction encoder/decoder).

Possible Approaches:

1. Extend the encoding of OP_bsr/OP_bsf to include a new but ignored (from the perspective of the encoder) source operand. This operand serves to document the current behaviour of the x86-64 implementations, especially to utilities that attempt to determine which registers are live/dead.
2. Status quo. The behaviour is undefined in Intel64, and is only "defined" through side-channel communications between Intel architects and Linux kernel developers. Thus, a reasonable argument can be made that no changes are necessary. However, AMD64 defines the behaviour, so for compatibility purposes, it does not hurt to

Challenges:

1. Making the decoder be able to set the same (variable) operand to be both a source and a destination, and having a mechanism to express this runtime behaviour within the current instruction decoder. This might be similar to how some instructions have a useless operand that can exist for documentation; however, I am not sure if DR includes those at the moment.
2. Making the encoder ignore the operand, but check that the destination and the second source operands match.

Current approach: DynamoRIO correctly encodes and decodes this instruction, but lacks some semantic information that reflects how the instruction behaves in practice. This semantic information would be useful for tools, especially those that determine register liveness.

References: [1] http://lxr.free-electrons.com/source/arch/x86/include/asm/bitops.h#L412

Original issue: http://code.google.com/p/dynamorio/issues/detail?id=1181