On 2/10/23 8:55 AM, Kumar Kartikeya Dwivedi wrote:
> On Thu, Feb 09, 2023 at 06:41:41PM CET, Dave Marchevsky wrote:
>> Newly-added bpf_rbtree_{remove,first} kfuncs have some special properties
>> that require handling in the verifier:
>>
>> * both bpf_rbtree_remove and bpf_rbtree_first return the type containing
>> the bpf_rb_node field, with the offset set to that field's offset,
>> instead of a struct bpf_rb_node *
>> * mark_reg_graph_node helper added in previous patch generalizes
>> this logic, use it
>>
>> * bpf_rbtree_remove's node input is a node that's been inserted
>> in the tree - a non-owning reference.
>>
>> * bpf_rbtree_remove must invalidate non-owning references in order to
>> avoid aliasing issue. Use previously-added
>> invalidate_non_owning_refs helper to mark this function as a
>> non-owning ref invalidation point.
>>
>> * Unlike other functions, which convert one of their input arg regs to
>> non-owning reference, bpf_rbtree_first takes no arguments and just
>> returns a non-owning reference (possibly null)
>> * For now verifier logic for this is special-cased instead of
>> adding new kfunc flag.
>>
>> This patch, along with the previous one, complete special verifier
>> handling for all rbtree API functions added in this series.
>>
As I was writing this response I noticed that Alexei started a subthread
which makes similar points.
>
> I think there are two issues with the current approach. The fundamental
> assumption with non-owning references is that it is part of the collection. So
> bpf_rbtree_{add,first}, bpf_list_push_{front,back} will create them, as no node
> is being removed from collection. Marking bpf_rbtree_remove (and in the future
> bpf_list_del) as invalidation points is also right, since once a node has been
> removed it is going to be unclear whether existing non-owning references have
> the same value, and thus the property of 'part of the collection' will be
> broken.
>
> The first issue relates to usability. If I have non-owning references to nodes
> inserted into both a list and an rbtree, bpf_rbtree_remove should only
> invalidate the ones that are part of the particular rbtree. It should have no
> effect on others. Likewise for the bpf_list_del operation in the future.
> Therefore, we need to track the collection identity associated with each
> non-owning reference, then only invalidate non-owning references associated with
> the same collection.
>
> The case of bpf_spin_unlock is different, which should invalidate all non-owning
> references.
>
I agree that if we had "data structure" or "collection" identity we would be
able to make this optimization. I also agree that such an optimization is likely
necessary for good usability in nontrivial scenarios. Alexei convinced me to
punt on it for now (over VC, I think, so can't link a thread), with the goal
of keeping complexity of this series under control.
Since "invalidate all non-owning references" is a superset of "invalidate
non-owning references associated with a particular collection", I think it's
fine to proceed with this for now if it means we can avoid adding collection
identity until followup. But I do plan on adding it and was thinking along
similar lines to your struct bpf_collection_id below. Which brings us to
second issue...
> The second issue is more serious. By not tracking the collection identity, we
> will currently allow a non-owning reference for an object inserted into a list
> to be passed to bpf_rbtree_remove, because the verifier cannot discern between
> 'inserted into rbtree' vs 'inserted into list'. For it, both are currently
> equivalent in the verifier state. An object is allowed to have both
> bpf_list_node and bpf_rb_node, but it can only be part of one collection at a
> time (because of no shared ownership).
>
> struct obj {
> bpf_list_node ln;
> bpf_rb_node rn;
> };
>
> bpf_list_push_front(head, &obj->ln); // node is non-own-ref
> bpf_rbtree_remove(&obj->rn); // should not work, but does
>
> So some notion of a collection identity needs to be constructed, the amount of
> data which needs to be remembered in each non-owning reference's register state
> depends on our requirements.
>
> The first sanity check is that bpf_rbtree_remove only removes something in an
> rbtree, so probably an enum member indicating whether collection is a list or
> rbtree. To ensure proper scoped invalidation, we will unfortunately need more
> than just the reg->id of the reg holding the graph root, since map values of
> different maps may have same id (0). Hence, we need id and ptr similar to the
> active lock case for proper matching. Even this won't be enough, as there can be
> multiple list or rbtree roots in a particular memory region, therefore the
> offset also needs to be part of the collection identity.
>
I agree with your logic here: the logic in this series will consider your
example code a valid program when it should fail verification.
Since there's no support for "shared ownership" added in this series, we must
prevent an object from being part of both list and rbtree in your above example.
Adding "collection identity" as you propose seems like it would be sufficient,
but would increase complexity of this series. Alternatively, we could add a
small patch which causes btf_parse_fields to fail if a struct has both
bpf_list_node and bpf_rb_node. Then a "collection identity"-focused followup
could remove that kludge in favor of proper logic.
This was an oversight on my part, I wasn't separating "node can be part of both
list and rbtree" from "node can be part of either, but not both". So I see why
you mention this second issue being orthogonal from shared ownership in the
other subthread. But, at least for our current internal usecases, we always want
shared ownership, not "part of either, but not both". If it's possible to
turn both off for now and do "collection identity" and "shared ownership"
followups, I'd rather do that and ship complexity as gradually as possible.
> So it seems it will amount to:
>
> struct bpf_collection_id {
> enum bpf_collection_type type;
> void *ptr;
> int id;
> int off;
> };
>
> There might be ways to optimize the memory footprint of this struct, but I'm
> just trying to state why we'll need to include all four, so we don't miss out on
> a corner case again.
>
>> Signed-off-by: Dave Marchevsky <davemarchevsky@xxxxxx>
>> ---
>> [...]
