> On Wed, 2022-06-22 at 20:11 -0700, Alexei Starovoitov wrote:
[...]
> tbh sounds scary. We had so many bugs in the patch_insn over years.
> The code is subtle.
In terms of testing strategy the following could be done:
- use pseudo-random testing to verify that `bpf_patch_insn_data` and
the mechanism suggested in my email produce identical code.
- use pseudo-random testing to verify that offsets after rewrite point
to expected instructions (e.g. use .imm field as a unique marker for
the instruction).
- hand-written tests for corner cases.
Would you consider this to be sufficient? (Probably does not sound
too reassuring from the person[me] who submits patches with trivial
use after free errors :)
[...]
> Before proceeding too far based on artificial test please collect
> the number of patches and their sizes we currently do across all progs
> in selftests. Maybe it's not that bad in real code.
I will collect and share the stats on Saturday or Sunday.
> As far as algo the patch_and_copy_insn() assumes that 'dst' insn is a branch?
> I guess I'm missing some parts of the proposed algo.
Sorry, I made a mistake in the original email, the code for
patch_and_copy_insn() should look as follows:
static void patch_and_copy_insn(struct bpf_patching_state *state, int pc,
struct bpf_insn *dst, struct bpf_insn *src) {
memcpy(dst, src, sizeof(struct bpf_insn));
// TODO: other classes
// TODO: also adjust imm for calls
if (BPF_CLASS(src->code) == BPF_JMP) {
int new_pc = pc + lookup_delta_for_index(state, pc);
int dst_pc = pc + src->off + 1;
int new_dst = dst_pc + lookup_delta_for_index(state, dst_pc);
dst->off = new_dst - new_pc - 1;
}
}
The logic is as follows:
- compute new instruction index for the old pc
- compute new instruction index for the (old pc + offset)
- use these values to compute the new offset
The draft implementation of this algorithm is at the end of this
email.
> Instead of delaying everything maybe we can do all patching inline
> except bpf_adj_branches?
> Remember only:
> int offset; /* index inside the original program,
> * the instruction at this index would be replaced.
> */
> int insns_count; /* size of the patch */
> int delta; /* difference in indexes between original program and
> * new program after application of all patches up to
> * and including this one.
> */
> and do single bpf_adj_branches at the end ?
The algorithm consists of two parts:
- To avoid excessive copying patches are accumulated in a separate
array and size of this array is doubled each time the capacity is
not sufficient to fit a new patch. This should have O(log(n))
complexity in terms of copied bytes.
- To avoid excessive branch adjustment passes a single branch
adjustment pass is performed at the end. This pass visits each
instruction only once, however, for each instruction it will have
to query the delta value in a sorted array. Thus the overall
complexity of this pass would be O(n*log(n)). It is possible to
adjust some relevant fields in `env` during this pass as well.
If the first part is skipped and patching is done inline, then for
each patch:
- `realloc` is invoked (relatively cheap?)
- `memcpy` is invoked to copy the head and tail of the current
program. This has O(n**2) worst case complexity in terms of copied
memory.
Thanks,
Eduard
---
/* Draft implementation of the proposed algorithm, written as user
* space code, thus calls bzero etc. Should be buggy but I'll figure
* it out. */
#include <errno.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#define BPF_CLASS(code) ((code)&0x07)
#define BPF_JMP 0x05
struct bpf_insn {
uint8_t code;
uint8_t dst_reg : 4;
uint8_t src_reg : 4;
int16_t off;
int32_t imm;
};
struct bpf_patch {
int offset;
int insns_count;
int delta;
struct bpf_insn *insns;
};
struct bpf_patching_state {
struct bpf_patch *patches;
int patches_count;
int patches_capacity;
struct bpf_insn *insns;
int insns_count;
int insns_capacity;
};
static int init_patching_state(struct bpf_patching_state *state) {
bzero(state, sizeof(*state));
state->patches_count = 0;
state->patches_capacity = 1; // small number, just for testing
state->patches = calloc(state->patches_capacity, sizeof(struct bpf_patch));
if (!state->patches)
goto err;
state->insns_count = 0;
state->insns_capacity = 2; // small number, just for testing
state->insns = calloc(state->insns_capacity, sizeof(struct bpf_insn));
if (!state->insns)
goto err;
return 0;
err:
if (state->patches)
free(state->patches);
if (state->insns)
free(state->insns);
return -ENOMEM;
}
static void free_patching_state(struct bpf_patching_state *state) {
free(state->patches);
free(state->insns);
bzero(state, sizeof(*state));
}
static int add_patch(struct bpf_patching_state *state, int offset,
int insns_count, struct bpf_insn *insns)
{
if (state->patches_count == state->patches_capacity) {
struct bpf_patch *new_patches =
reallocarray(state->patches, state->patches_capacity * 2,
sizeof(struct bpf_patch));
if (!new_patches)
return -ENOMEM;
state->patches = new_patches;
state->patches_capacity *= 2;
}
int insns_available = state->insns_capacity - state->insns_count;
if (insns_available < insns_count) {
int cur_capacity = (state->insns_capacity > insns_count
? state->insns_capacity
: insns_count);
int new_capacity = cur_capacity * 2;
struct bpf_insn *new_insns =
reallocarray(state->insns, new_capacity, sizeof(struct bpf_insn));
if (!new_insns)
return -ENOMEM;
state->insns = new_insns;
state->insns_capacity = new_capacity;
}
struct bpf_patch *patch = &state->patches[state->patches_count];
struct bpf_insn *dest_insns = &state->insns[state->insns_count];
state->patches_count += 1;
state->insns_count += insns_count;
patch->offset = offset;
patch->insns_count = insns_count;
patch->insns = insns;
patch->delta = 0;
memcpy(dest_insns, insns, insns_count * sizeof(struct bpf_insn));
return 0;
}
static int lookup_delta_for_index(struct bpf_patching_state *state, int index)
{
struct bpf_patch *patches = state->patches;
if (state->patches_count == 0 || index < patches[0].offset)
return 0;
if (state->patches_count == 1)
return patches[0].delta;
int l = 0;
int r = state->patches_count - 1;
while (r - l != 1) {
int m = l + (r - l) / 2;
if (patches[m].offset < index)
l = m;
else
r = m;
}
if (patches[r].offset < index)
return patches[r].delta;
else
return patches[l].delta;
}
static void patch_and_copy_insn(struct bpf_patching_state *state, int pc,
struct bpf_insn *dst, struct bpf_insn *src) {
memcpy(dst, src, sizeof(struct bpf_insn));
// TODO: other classes
// TODO: also adjust imm for calls
if (BPF_CLASS(src->code) == BPF_JMP) {
int new_pc = pc + lookup_delta_for_index(state, pc);
int dst_pc = pc + src->off + 1;
int new_dst = dst_pc + lookup_delta_for_index(state, dst_pc);
dst->off = new_dst - new_pc - 1;
}
}
static struct bpf_insn *apply_patches(struct bpf_patching_state *state,
struct bpf_insn *prog, int *prog_size)
{
int delta = 0;
for (int i = 0; i < state->patches_count; ++i) {
delta += state->patches[i].insns_count - 1;
state->patches[i].delta = delta;
}
int old_prog_size = *prog_size;
int new_prog_size = old_prog_size + delta;
struct bpf_insn *new_prog = calloc(new_prog_size, sizeof(struct bpf_insn));
if (!new_prog)
return NULL;
*prog_size = new_prog_size;
struct bpf_insn *old_insn = prog;
struct bpf_insn *new_insn = new_prog;
int next_patch = 0;
for (int i = 0; i < old_prog_size; ++i) {
// TODO: deal with double-word immediate values correctly
if (next_patch < state->patches_count &&
state->patches[next_patch].offset == i) {
struct bpf_patch *patch = &state->patches[next_patch];
for (int j = 0; j < patch->insns_count; ++j) {
patch_and_copy_insn(state, i + j,
new_insn, &patch->insns[j]);
++new_insn;
}
++next_patch;
} else {
patch_and_copy_insn(state, i, new_insn, old_insn);
++new_insn;
}
++old_insn;
}
return new_prog;
}
static void show_prog(struct bpf_insn *prog, int cnt) {
for (int i = 0; i < cnt; ++i) {
printf("%02d: .code = %02d, .off = %+03d, .imm = %+03d", i, prog[i].code,
prog[i].off, prog[i].imm);
if (BPF_CLASS(prog[i].code) == BPF_JMP) {
int jmp_idx = i + prog[i].off + 1;
printf(", jmp to %02d .imm = %+03d", jmp_idx, prog[jmp_idx].imm);
}
printf("\n");
}
}
int main(int argc, char **argv) {
struct bpf_insn prog[] = {
{.code = 0, .imm = 0},
{.code = BPF_JMP, .off = 3, .imm = 1},
{.code = 0, .imm = 2},
{.code = 0, .imm = 3},
{.code = BPF_JMP, .off = 1, .imm = 4},
{.code = 0, .imm = 5},
{.code = 0, .imm = 6},
{.code = BPF_JMP, .off = -5, .imm = 7},
{.code = 0, .imm = 8},
{.code = BPF_JMP, .off = 0, .imm = 9},
{.code = 0, .imm = 10},
{.code = BPF_JMP, .off = -11, .imm = 11},
};
int cnt = sizeof(prog) / sizeof(prog[0]);
struct bpf_patching_state st;
init_patching_state(&st);
struct bpf_insn p1[] = {{.imm = -10}, {.imm = -11}};
add_patch(&st, 0, 2, p1);
struct bpf_insn p2[] = {
{.imm = -20},
{.imm = -21},
{.imm = -22},
};
add_patch(&st, 2, 3, p2);
struct bpf_insn p3[] = {
{.imm = -30},
{.imm = -31},
{.code = BPF_JMP, .off = 1, .imm = -32}, // jump out of patch by 1 insn
{.imm = -33}
};
add_patch(&st, 8, 4, p3);
int new_prog_cnt = cnt;
struct bpf_insn *new_prog = apply_patches(&st, prog, &new_prog_cnt);
free_patching_state(&st);
printf("Prog before:\n");
show_prog(prog, cnt);
printf("\nProg after:\n");
show_prog(new_prog, new_prog_cnt);
free(new_prog);
return 0;
}
