On 10/31/17 5:37 AM, Edward Cree wrote:
On 30/10/17 21:51, Alexei Starovoitov wrote:
the verifier got progressively smarter over time and size of its internal
state grew as well. Time to reduce the memory consumption.
Before:
sizeof(struct bpf_verifier_state) = 6520
After:
sizeof(struct bpf_verifier_state) = 896
Nice!
It's done by observing that majority of BPF programs use little to
no stack whereas verifier kept all of 512 stack slots ready always.
Instead dynamically reallocate struct verifier state when stack
access is detected.
Besides memory savings such approach gives few % runtime perf
improvement as well and small reduction in number of processed insns:
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This worries me. Not that improving pruning performance is a bad thing,
but I don't see anything in this patch that should affect it, which
suggests maybe a bug has been introduced that prunes too much?
that indeed turned out to be a missed case when poping a state
with smaller stack than the current one.
+static void copy_verifier_state(struct bpf_verifier_state *dst,
+ const struct bpf_verifier_state *src)
+{
+ int stack = dst->allocated_stack;
+
+ if (stack < src->allocated_stack) {
+ WARN_ON_ONCE(stack < src->allocated_stack);
Why not just
if (WARN_ON_ONCE(stack < src->allocated_stack)) {
?
done.
+ /* internal bug, make state invalid to reject the program */
+ memset(dst, 0, sizeof(*dst));
+ return;
Any reason this function couldn't return int instead?
I didn't do it, since it adds additional error checks to the code that
should never be taken, but I guess it makes the verifier a tiny bit
more robust in case of fatal errors, so done.
+ }
+ memcpy(dst, src, offsetof(struct bpf_verifier_state,
+ stack[src->allocated_stack / BPF_REG_SIZE]));
+ dst->allocated_stack = stack;
+}
Then again, I'm not entirely sure I like the idea of an array[0] at the
end of the struct anyway (which is what makes this copy_verifier_state()
necessary). I'd be happier with a *array member pointing to a separate
allocation;
I coded it up. It turned out to be a bit more complex than current
version, but the argument about keeping state pointer the same is
solid, so done.
though that would still need separate copying in
is_state_visited().
yes
I also worry about a stale *parent somewhere
pointing to the old state; I don't _think_ that can happen, but I'm not
'parent' can point to wrong thing since liveness was introduced,
so this doesn't change it. With stack[0] and *stack approach,
both need to copy parent. Specifically for that I had a comment
next to realloc_verifier_state() and kept the comment in
the new version.
as sure of that as I'd like to be. Using a *array instead would mean
that &state doesn't change when we grow it.
Also, why kzalloc() a new state (in realloc_verifier_state()) rather than
krealloc()ing the existing one and memset()ing the extra space? That way
you wouldn't need to then copy across all the old data.
because krealloc() unconditionally copies the data whereas we can make
it smarter by not copying always.
static int pop_stack(struct bpf_verifier_env *env, int *prev_insn_idx)
{
- struct bpf_verifier_stack_elem *elem;
+ struct bpf_verifier_state *cur = env->cur_state;
+ struct bpf_verifier_stack_elem *elem, *head = env->head;
int insn_idx;
if (env->head == NULL)
return -1;
- memcpy(&env->cur_state, &env->head->st, sizeof(env->cur_state));
- insn_idx = env->head->insn_idx;
+ if (cur && cur->allocated_stack < head->st.allocated_stack) {
+ cur = realloc_verifier_state(cur, head->st.allocated_stack);
+ if (!cur)
+ return -ENOMEM;
I don't think this does what you want. Calling code in do_check() will
get insn_idx = -ENOMEM, see that it's < 0, and break out of the loop.
Prog will then be accepted without further checking.
yeah. it was on my todo list to fix before submitting, but then slipped
my mind. Fixed now.
v2 is coming.
