[patch 25/37] Immediate Values - Jump

From: Mathieu Desnoyers
Date: Thu Apr 24 2008 - 11:14:38 EST


Adds a new imv_cond() macro to declare a byte read that is meant to be embedded
in unlikely(imv_cond(var)), so the kernel can dynamically detect patterns such
as mov, test, jne or mov, test, je and patch it with nops and a jump.

Changelog:
- fix !CONFIG_IMMEDIATE

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxx>
---
arch/x86/kernel/immediate.c | 406 +++++++++++++++++++++++++++++++++-------
include/asm-powerpc/immediate.h | 2
include/asm-x86/immediate.h | 34 +++
include/linux/immediate.h | 11 -
kernel/immediate.c | 6
5 files changed, 384 insertions(+), 75 deletions(-)

Index: linux-2.6-sched-devel/include/asm-x86/immediate.h
===================================================================
--- linux-2.6-sched-devel.orig/include/asm-x86/immediate.h 2008-04-24 10:10:15.000000000 -0400
+++ linux-2.6-sched-devel/include/asm-x86/immediate.h 2008-04-24 10:10:19.000000000 -0400
@@ -20,6 +20,7 @@ struct __imv {
* Pointer to the memory location of the
* immediate value within the instruction.
*/
+ int jmp_off; /* offset for jump target */
unsigned char size; /* Type size. */
unsigned char insn_size;/* Instruction size. */
} __attribute__ ((packed));
@@ -57,6 +58,7 @@ struct __imv {
".previous\n\t" \
".section __imv,\"aw\",@progbits\n\t" \
_ASM_PTR "%c1, (3f)-%c2\n\t" \
+ ".int 0\n\t" \
".byte %c2, (2b-1b)\n\t" \
".previous\n\t" \
"mov $0,%0\n\t" \
@@ -74,6 +76,7 @@ struct __imv {
".previous\n\t" \
".section __imv,\"aw\",@progbits\n\t" \
_ASM_PTR "%c1, (3f)-%c2\n\t" \
+ ".int 0\n\t" \
".byte %c2, (2b-1b)\n\t" \
".previous\n\t" \
".org . + ((-.-(2b-1b)) & (%c2-1)), 0x90\n\t" \
@@ -95,6 +98,7 @@ struct __imv {
".previous\n\t" \
".section __imv,\"aw\",@progbits\n\t" \
_ASM_PTR "%c1, (3f)-%c2\n\t" \
+ ".int 0\n\t" \
".byte %c2, (2b-1b)\n\t" \
".previous\n\t" \
".org . + ((-.-(2b-1b)) & (%c2-1)), 0x90\n\t" \
@@ -108,6 +112,34 @@ struct __imv {
value; \
})

-extern int arch_imv_update(const struct __imv *imv, int early);
+/*
+ * Uses %al.
+ * size is 0.
+ * Use in if (unlikely(imv_cond(var)))
+ * Given a char as argument.
+ */
+#define imv_cond(name) \
+ ({ \
+ __typeof__(name##__imv) value; \
+ BUILD_BUG_ON(sizeof(value) > 1); \
+ asm (".section __discard,\"\",@progbits\n\t" \
+ "1:\n\t" \
+ "mov $0,%0\n\t" \
+ "2:\n\t" \
+ ".previous\n\t" \
+ ".section __imv,\"aw\",@progbits\n\t" \
+ _ASM_PTR "%c1, (3f)-1\n\t" \
+ ".int 0\n\t" \
+ ".byte %c2, (2b-1b)\n\t" \
+ ".previous\n\t" \
+ "mov $0,%0\n\t" \
+ "3:\n\t" \
+ : "=a" (value) \
+ : "i" (&name##__imv), \
+ "i" (0)); \
+ value; \
+ })
+
+extern int arch_imv_update(struct __imv *imv, int early);

#endif /* _ASM_X86_IMMEDIATE_H */
Index: linux-2.6-sched-devel/arch/x86/kernel/immediate.c
===================================================================
--- linux-2.6-sched-devel.orig/arch/x86/kernel/immediate.c 2008-04-24 10:10:15.000000000 -0400
+++ linux-2.6-sched-devel/arch/x86/kernel/immediate.c 2008-04-24 10:13:27.000000000 -0400
@@ -80,13 +80,25 @@
#include <asm/cacheflush.h>

#define BREAKPOINT_INSTRUCTION 0xcc
+#define JMP_REL8 0xeb
+#define JMP_REL32 0xe9
+#define INSN_NOP1 0x90
+#define INSN_NOP2 0x89, 0xf6
#define BREAKPOINT_INS_LEN 1
#define NR_NOPS 10

+/*#define DEBUG_IMMEDIATE 1*/
+
+#ifdef DEBUG_IMMEDIATE
+#define printk_dbg printk
+#else
+#define printk_dbg(fmt , a...)
+#endif
+
static unsigned long target_after_int3; /* EIP of the target after the int3 */
static unsigned long bypass_eip; /* EIP of the bypass. */
static unsigned long bypass_after_int3; /* EIP after the end-of-bypass int3 */
-static unsigned long after_imv; /*
+static unsigned long after_imv; /*
* EIP where to resume after the
* single-stepping.
*/
@@ -142,6 +154,25 @@ static int imv_notifier(struct notifier_

if (die_val == DIE_INT3) {
if (args->regs->ip == target_after_int3) {
+ /* deal with non-relocatable jmp instructions */
+ switch (*(uint8_t *)bypass_eip) {
+ case JMP_REL8: /* eb cb jmp rel8 */
+ args->regs->ip +=
+ *(signed char *)(bypass_eip + 1) + 1;
+ return NOTIFY_STOP;
+ case JMP_REL32: /* e9 cw jmp rel16 (valid on ia32) */
+ /* e9 cd jmp rel32 */
+ args->regs->ip +=
+ *(int *)(bypass_eip + 1) + 4;
+ return NOTIFY_STOP;
+ case INSN_NOP1:
+ /* deal with insertion of nop + jmp_rel32 */
+ if (*((uint8_t *)bypass_eip + 1) == JMP_REL32) {
+ args->regs->ip +=
+ *(int *)(bypass_eip + 2) + 5;
+ return NOTIFY_STOP;
+ }
+ }
preempt_disable();
args->regs->ip = bypass_eip;
return NOTIFY_STOP;
@@ -159,71 +190,107 @@ static struct notifier_block imv_notify
.priority = 0x7fffffff, /* we need to be notified first */
};

-/**
- * arch_imv_update - update one immediate value
- * @imv: pointer of type const struct __imv to update
- * @early: early boot (1) or normal (0)
- *
- * Update one immediate value. Must be called with imv_mutex held.
+/*
+ * returns -1 if not found
+ * return 0 if found.
*/
-__kprobes int arch_imv_update(const struct __imv *imv, int early)
+static inline int detect_mov_test_jne(uint8_t *addr, uint8_t **opcode,
+ uint8_t **jmp_offset, int *offset_len)
{
- int ret;
- unsigned char opcode_size = imv->insn_size - imv->size;
- unsigned long insn = imv->imv - opcode_size;
- unsigned long len;
- char *vaddr;
- struct page *pages[1];
-
-#ifdef CONFIG_KPROBES
- /*
- * Fail if a kprobe has been set on this instruction.
- * (TODO: we could eventually do better and modify all the (possibly
- * nested) kprobes for this site if kprobes had an API for this.
- */
- if (unlikely(!early
- && *(unsigned char *)insn == BREAKPOINT_INSTRUCTION)) {
- printk(KERN_WARNING "Immediate value in conflict with kprobe. "
- "Variable at %p, "
- "instruction at %p, size %hu\n",
- (void *)imv->imv,
- (void *)imv->var, imv->size);
- return -EBUSY;
- }
-#endif
-
- /*
- * If the variable and the instruction have the same value, there is
- * nothing to do.
- */
- switch (imv->size) {
- case 1: if (*(uint8_t *)imv->imv
- == *(uint8_t *)imv->var)
- return 0;
- break;
- case 2: if (*(uint16_t *)imv->imv
- == *(uint16_t *)imv->var)
- return 0;
- break;
- case 4: if (*(uint32_t *)imv->imv
- == *(uint32_t *)imv->var)
+ printk_dbg(KERN_DEBUG "Trying at %p %hx %hx %hx %hx %hx %hx\n",
+ addr, addr[0], addr[1], addr[2], addr[3], addr[4], addr[5]);
+ /* b0 cb movb cb,%al */
+ if (addr[0] != 0xb0)
+ return -1;
+ /* 84 c0 test %al,%al */
+ if (addr[2] != 0x84 || addr[3] != 0xc0)
+ return -1;
+ printk_dbg(KERN_DEBUG "Found test %%al,%%al at %p\n", addr + 2);
+ switch (addr[4]) {
+ case 0x75: /* 75 cb jne rel8 */
+ printk_dbg(KERN_DEBUG "Found jne rel8 at %p\n", addr + 4);
+ *opcode = addr + 4;
+ *jmp_offset = addr + 5;
+ *offset_len = 1;
+ return 0;
+ case 0x0f:
+ switch (addr[5]) {
+ case 0x85: /* 0F 85 cw jne rel16 (valid on ia32) */
+ /* 0F 85 cd jne rel32 */
+ printk_dbg(KERN_DEBUG "Found jne rel16/32 at %p\n",
+ addr + 5);
+ *opcode = addr + 4;
+ *jmp_offset = addr + 6;
+ *offset_len = 4;
return 0;
+ default:
+ return -1;
+ }
break;
-#ifdef CONFIG_X86_64
- case 8: if (*(uint64_t *)imv->imv
- == *(uint64_t *)imv->var)
+ default: return -1;
+ }
+}
+
+/*
+ * returns -1 if not found
+ * return 0 if found.
+ */
+static inline int detect_mov_test_je(uint8_t *addr, uint8_t **opcode,
+ uint8_t **jmp_offset, int *offset_len)
+{
+ /* b0 cb movb cb,%al */
+ if (addr[0] != 0xb0)
+ return -1;
+ /* 84 c0 test %al,%al */
+ if (addr[2] != 0x84 || addr[3] != 0xc0)
+ return -1;
+ printk_dbg(KERN_DEBUG "Found test %%al,%%al at %p\n", addr + 2);
+ switch (addr[4]) {
+ case 0x74: /* 74 cb je rel8 */
+ printk_dbg(KERN_DEBUG "Found je rel8 at %p\n", addr + 4);
+ *opcode = addr + 4;
+ *jmp_offset = addr + 5;
+ *offset_len = 1;
+ return 0;
+ case 0x0f:
+ switch (addr[5]) {
+ case 0x84: /* 0F 84 cw je rel16 (valid on ia32) */
+ /* 0F 84 cd je rel32 */
+ printk_dbg(KERN_DEBUG "Found je rel16/32 at %p\n",
+ addr + 5);
+ *opcode = addr + 4;
+ *jmp_offset = addr + 6;
+ *offset_len = 4;
return 0;
+ default:
+ return -1;
+ }
break;
-#endif
- default:return -EINVAL;
+ default: return -1;
}
+}
+
+static int static_early;

- if (!early) {
- /* bypass is 10 bytes long for x86_64 long */
- WARN_ON(imv->insn_size > 10);
- _imv_bypass(&bypass_eip, &bypass_after_int3);
+/*
+ * Marked noinline because we prefer to have only one _imv_bypass. Not that it
+ * is required, but there is no need to edit two bypasses.
+ */
+static noinline int replace_instruction_safe(uint8_t *addr, uint8_t *newcode,
+ int size)
+{
+ char *vaddr;
+ struct page *pages[1];
+ int len;
+ int ret;
+
+ /* bypass is 10 bytes long for x86_64 long */
+ WARN_ON(size > 10);

- after_imv = imv->imv + imv->size;
+ _imv_bypass(&bypass_eip, &bypass_after_int3);
+
+ if (!static_early) {
+ after_imv = (unsigned long)addr + size;

/*
* Using the _early variants because nobody is executing the
@@ -238,22 +305,23 @@ __kprobes int arch_imv_update(const stru
vaddr = vmap(pages, 1, VM_MAP, PAGE_KERNEL);
BUG_ON(!vaddr);
text_poke_early(&vaddr[bypass_eip & ~PAGE_MASK],
- (void *)insn, imv->insn_size);
+ (void *)addr, size);
/*
* Fill the rest with nops.
*/
- len = NR_NOPS - imv->insn_size;
+ len = NR_NOPS - size;
add_nops((void *)
- &vaddr[(bypass_eip & ~PAGE_MASK) + imv->insn_size],
+ &vaddr[(bypass_eip & ~PAGE_MASK) + size],
len);
vunmap(vaddr);

- target_after_int3 = insn + BREAKPOINT_INS_LEN;
+ target_after_int3 = (unsigned long)addr + BREAKPOINT_INS_LEN;
/* register_die_notifier has memory barriers */
register_die_notifier(&imv_notify);
- /* The breakpoint will single-step the bypass */
- text_poke((void *)insn,
- ((unsigned char[]){BREAKPOINT_INSTRUCTION}), 1);
+ /* The breakpoint will execute the bypass */
+ text_poke((void *)addr,
+ ((unsigned char[]){BREAKPOINT_INSTRUCTION}),
+ BREAKPOINT_INS_LEN);
/*
* Make sure the breakpoint is set before we continue (visible
* to other CPUs and interrupts).
@@ -265,14 +333,18 @@ __kprobes int arch_imv_update(const stru
ret = on_each_cpu(imv_synchronize_core, NULL, 1, 1);
BUG_ON(ret != 0);

- text_poke((void *)(insn + opcode_size), (void *)imv->var,
- imv->size);
+ text_poke((void *)(addr + BREAKPOINT_INS_LEN),
+ &newcode[BREAKPOINT_INS_LEN],
+ size - BREAKPOINT_INS_LEN);
/*
* Make sure the value can be seen from other CPUs and
* interrupts.
*/
wmb();
- text_poke((void *)insn, (unsigned char *)bypass_eip, 1);
+#ifdef DEBUG_IMMEDIATE
+ mdelay(10); /* lets the breakpoint for a while */
+#endif
+ text_poke(addr, newcode, BREAKPOINT_INS_LEN);
/*
* Wait for all int3 handlers to end (interrupts are disabled in
* int3). This CPU is clearly not in a int3 handler, because
@@ -285,7 +357,203 @@ __kprobes int arch_imv_update(const stru
unregister_die_notifier(&imv_notify);
/* unregister_die_notifier has memory barriers */
} else
- text_poke_early((void *)imv->imv, (void *)imv->var,
- imv->size);
+ text_poke_early(addr, newcode, size);
+ return 0;
+}
+
+static int patch_jump_target(struct __imv *imv)
+{
+ uint8_t *opcode, *jmp_offset;
+ int offset_len;
+ int mov_test_j_found = 0;
+
+ if (!detect_mov_test_jne((uint8_t *)imv->imv - 1,
+ &opcode, &jmp_offset, &offset_len)) {
+ imv->insn_size = 1; /* positive logic */
+ mov_test_j_found = 1;
+ } else if (!detect_mov_test_je((uint8_t *)imv->imv - 1,
+ &opcode, &jmp_offset, &offset_len)) {
+ imv->insn_size = 0; /* negative logic */
+ mov_test_j_found = 1;
+ }
+
+ if (mov_test_j_found) {
+ int logicvar = imv->insn_size ? imv->var : !imv->var;
+ int newoff;
+
+ if (offset_len == 1) {
+ imv->jmp_off = *(signed char *)jmp_offset;
+ /* replace with JMP_REL8 opcode. */
+ replace_instruction_safe(opcode,
+ ((unsigned char[]){ JMP_REL8,
+ (logicvar ? (signed char)imv->jmp_off : 0) }),
+ 2);
+ } else {
+ /* replace with nop and JMP_REL16/32 opcode.
+ * It's ok to shrink an instruction, never ok to
+ * grow it afterward. */
+ imv->jmp_off = *(int *)jmp_offset;
+ newoff = logicvar ? (int)imv->jmp_off : 0;
+ replace_instruction_safe(opcode,
+ ((unsigned char[]){ INSN_NOP1, JMP_REL32,
+ ((unsigned char *)&newoff)[0],
+ ((unsigned char *)&newoff)[1],
+ ((unsigned char *)&newoff)[2],
+ ((unsigned char *)&newoff)[3] }),
+ 6);
+ }
+ /* now we can get rid of the movb */
+ replace_instruction_safe((uint8_t *)imv->imv - 1,
+ ((unsigned char[]){ INSN_NOP2 }),
+ 2);
+ /* now we can get rid of the testb */
+ replace_instruction_safe((uint8_t *)imv->imv + 1,
+ ((unsigned char[]){ INSN_NOP2 }),
+ 2);
+ /* remember opcode + 1 to enable the JMP_REL patching */
+ if (offset_len == 1)
+ imv->imv = (unsigned long)opcode + 1;
+ else
+ imv->imv = (unsigned long)opcode + 2; /* skip nop */
+ return 0;
+
+ }
+
+ if (*((uint8_t *)imv->imv - 1) == JMP_REL8) {
+ int logicvar = imv->insn_size ? imv->var : !imv->var;
+
+ printk_dbg(KERN_DEBUG "Found JMP_REL8 at %p\n",
+ ((uint8_t *)imv->imv - 1));
+ /* Speed up by skipping if not changed */
+ if (logicvar) {
+ if (*(int8_t *)imv->imv == (int8_t)imv->jmp_off)
+ return 0;
+ } else {
+ if (*(int8_t *)imv->imv == 0)
+ return 0;
+ }
+
+ replace_instruction_safe((uint8_t *)imv->imv - 1,
+ ((unsigned char[]){ JMP_REL8,
+ (logicvar ? (signed char)imv->jmp_off : 0) }),
+ 2);
+ return 0;
+ }
+
+ if (*((uint8_t *)imv->imv - 1) == JMP_REL32) {
+ int logicvar = imv->insn_size ? imv->var : !imv->var;
+ int newoff = logicvar ? (int)imv->jmp_off : 0;
+
+ printk_dbg(KERN_DEBUG "Found JMP_REL32 at %p, update with %x\n",
+ ((uint8_t *)imv->imv - 1), newoff);
+ /* Speed up by skipping if not changed */
+ if (logicvar) {
+ if (*(int *)imv->imv == (int)imv->jmp_off)
+ return 0;
+ } else {
+ if (*(int *)imv->imv == 0)
+ return 0;
+ }
+
+ replace_instruction_safe((uint8_t *)imv->imv - 1,
+ ((unsigned char[]){ JMP_REL32,
+ ((unsigned char *)&newoff)[0],
+ ((unsigned char *)&newoff)[1],
+ ((unsigned char *)&newoff)[2],
+ ((unsigned char *)&newoff)[3] }),
+ 5);
+ return 0;
+ }
+
+ /* Nothing known found. */
+ return -1;
+}
+
+/**
+ * arch_imv_update - update one immediate value
+ * @imv: pointer of type const struct __imv to update
+ * @early: early boot (1) or normal (0)
+ *
+ * Update one immediate value. Must be called with imv_mutex held.
+ */
+__kprobes int arch_imv_update(struct __imv *imv, int early)
+{
+ int ret;
+ uint8_t buf[10];
+ unsigned long insn, opcode_size;
+
+ static_early = early;
+
+ /*
+ * If imv_cond is encountered, try to patch it with
+ * patch_jump_target. Continue with normal immediate values if the area
+ * surrounding the instruction is not as expected.
+ */
+ if (imv->size == 0) {
+ ret = patch_jump_target(imv);
+ if (ret) {
+#ifdef DEBUG_IMMEDIATE
+ static int nr_fail;
+ printk(KERN_DEBUG
+ "Jump target fallback at %lX, nr fail %d\n",
+ imv->imv, ++nr_fail);
+#endif
+ imv->size = 1;
+ } else {
+#ifdef DEBUG_IMMEDIATE
+ static int nr_success;
+ printk(KERN_DEBUG "Jump target at %lX, nr success %d\n",
+ imv->imv, ++nr_success);
+#endif
+ return 0;
+ }
+ }
+
+ opcode_size = imv->insn_size - imv->size;
+ insn = imv->imv - opcode_size;
+
+#ifdef CONFIG_KPROBES
+ /*
+ * Fail if a kprobe has been set on this instruction.
+ * (TODO: we could eventually do better and modify all the (possibly
+ * nested) kprobes for this site if kprobes had an API for this.
+ */
+ if (unlikely(!early
+ && *(unsigned char *)insn == BREAKPOINT_INSTRUCTION)) {
+ printk(KERN_WARNING "Immediate value in conflict with kprobe. "
+ "Variable at %p, "
+ "instruction at %p, size %hu\n",
+ (void *)imv->var,
+ (void *)imv->imv, imv->size);
+ return -EBUSY;
+ }
+#endif
+
+ /*
+ * If the variable and the instruction have the same value, there is
+ * nothing to do.
+ */
+ switch (imv->size) {
+ case 1: if (*(uint8_t *)imv->imv == *(uint8_t *)imv->var)
+ return 0;
+ break;
+ case 2: if (*(uint16_t *)imv->imv == *(uint16_t *)imv->var)
+ return 0;
+ break;
+ case 4: if (*(uint32_t *)imv->imv == *(uint32_t *)imv->var)
+ return 0;
+ break;
+#ifdef CONFIG_X86_64
+ case 8: if (*(uint64_t *)imv->imv == *(uint64_t *)imv->var)
+ return 0;
+ break;
+#endif
+ default:return -EINVAL;
+ }
+
+ memcpy(buf, (uint8_t *)insn, opcode_size);
+ memcpy(&buf[opcode_size], (void *)imv->var, imv->size);
+ replace_instruction_safe((uint8_t *)insn, buf, imv->insn_size);
+
return 0;
}
Index: linux-2.6-sched-devel/include/linux/immediate.h
===================================================================
--- linux-2.6-sched-devel.orig/include/linux/immediate.h 2008-04-24 10:10:18.000000000 -0400
+++ linux-2.6-sched-devel/include/linux/immediate.h 2008-04-24 10:10:19.000000000 -0400
@@ -33,8 +33,7 @@
* Internal update functions.
*/
extern void core_imv_update(void);
-extern void imv_update_range(const struct __imv *begin,
- const struct __imv *end);
+extern void imv_update_range(struct __imv *begin, struct __imv *end);
extern void imv_unref_core_init(void);
extern void imv_unref(struct __imv *begin, struct __imv *end, void *start,
unsigned long size);
@@ -54,6 +53,14 @@ extern void imv_unref(struct __imv *begi
#define imv_read(name) _imv_read(name)

/**
+ * imv_cond - read immediate variable use as condition for if()
+ * @name: immediate value name
+ *
+ * Reads the value of @name.
+ */
+#define imv_cond(name) _imv_read(name)
+
+/**
* imv_set - set immediate variable (with locking)
* @name: immediate value name
* @i: required value
Index: linux-2.6-sched-devel/kernel/immediate.c
===================================================================
--- linux-2.6-sched-devel.orig/kernel/immediate.c 2008-04-24 10:10:18.000000000 -0400
+++ linux-2.6-sched-devel/kernel/immediate.c 2008-04-24 10:10:19.000000000 -0400
@@ -43,10 +43,10 @@ static DEFINE_MUTEX(imv_mutex);
*
* Updates a range of immediates.
*/
-void imv_update_range(const struct __imv *begin,
- const struct __imv *end)
+void imv_update_range(struct __imv *begin,
+ struct __imv *end)
{
- const struct __imv *iter;
+ struct __imv *iter;
int ret;
for (iter = begin; iter < end; iter++) {
mutex_lock(&imv_mutex);
Index: linux-2.6-sched-devel/include/asm-powerpc/immediate.h
===================================================================
--- linux-2.6-sched-devel.orig/include/asm-powerpc/immediate.h 2008-04-24 10:10:17.000000000 -0400
+++ linux-2.6-sched-devel/include/asm-powerpc/immediate.h 2008-04-24 10:10:19.000000000 -0400
@@ -68,6 +68,8 @@ struct __imv {
value; \
})

+#define imv_cond(name) imv_read(name)
+
extern int arch_imv_update(const struct __imv *imv, int early);

#endif /* _ASM_POWERPC_IMMEDIATE_H */

--
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/