Re: [net-next PATCH] net: ptr_ring: otherwise safe empty checks can overrun array bounds

["Michael S. Tsirkin" <mst@redhat.com>]

On Wed, Jan 03, 2018 at 09:46:15AM -0800, John Fastabend wrote:
> On 01/03/2018 07:50 AM, Michael S. Tsirkin wrote:
> > On Tue, Jan 02, 2018 at 04:25:03PM -0800, John Fastabend wrote:
> >>>
> >>> More generally, what makes this usage safe?
> >>> Is there a way to formalize it at the API level?
> >>>
> >>
> >> Right I think these are good questions. I think the ptr_ring API should
> >> allow a peek operation to be used without a lock. The user has to ensure
> >> they only use it as a hint and if its dereferenced the user needs to
> >> ensure the object is not free'd from some other codepath while it is
> >> being dereferenced. The existing API seems to match this.
> >>
> >> This is how I used it in pfifo_fast expecting the above to be true. The
> >> API allows for false negatives which _should_ be OK if the user is expecting
> >> this. Alternatively, we could make it false positives if you want and
> >> that would also work for me considering this case is hit very rarely.
> > 
> > By now I'm confused by which are positives and which are negatives :)
> > OK so the guarantees we want would be:
> > 
> > - empty can return false if ring is empty.
> >   caller must re-check with consumer lock taken
> 
> Correct.
> 
> > - if multiple threads call it, only one thread
> 
> What is "it" here, __skb_array_empty() presumably.
> 
> >   is guaranteed that empty will not return true
> >   if ring is non empty.
> >   after detecting that ring is not empty,
> >   this thread shall ....
> > 
> The guarantee is even weaker.
> 
>   - if __skb_array_empty() returns true, either the
>     ring is empty OR a consumer operation is in
>     progress.

Well I'm not sure that's guaranteed actually, in that
in progress isn't all that well defined on multi-core
systems.

E.g. write of NULL could bypass index write and
empty will return true on another CPU even though
both completed on our CPU.

I still think our use is ok, I'm just still having
trouble formulating the exact rules.

> 
> For pfifo_fast this is OK because some thread is making
> progress at this point.
>
>
> Note, even if multiple threads
> are calling __skb_array_empty() there is no guarantee
> any of them will return false even if the ring has
> elements.
>
> > can you help me fill in the blank please?
> > 
> 
> Did that help?
> 
> > 
> > 
> > 
> > 
> >>>>> John, others, could you pls confirm it's not too bad performance-wise?
> >>>>> I'll then split it up properly and re-post.
> >>>>>
> >>>>
> >>>> I haven't benchmarked it but in the dequeue case taking a lock for
> >>>> every priority even when its empty seems unneeded.
> >>>
> >>> Well it does seem to make the code more comprehensible and more robust.
> >>>
> >>
> >> Its a trade-off between performance and robustness.
> >>
> >>> But OK -  I was looking at fixing the unlocked empty API to make sure it
> >>> actually does what it's supposed to. I posted a draft earlier in this
> >>> thread, it needs to be looked at in depth to figure out whether it can
> >>> ever give false negatives or positives, and document the results.
> >>>
> >>>
> >>
> >> I'll look at it. But I still think keeping a lockless version makes sense
> >> for many use cases.
> > 
> > Fine. Just let's try to document what are the guarantees.
> > 
> 
> Yep. Guarantees should be (on ptr_ring implementation and similar
> on skb_array implementation)
> 
>   - if __ptr_ring_empty returns true, the ring may be empty
>     user must use operation with consumer lock to guarantee the
>     ring is empty. Note, when run with concurrent consumer operations
>     it is possible to return true when ring has elements. This
>     occurs when ring consumer head rolls over ring size. Also,
>     producer operations may put object in the ring concurrently
>     making empty check incorrect. To avoid this use locked
>     ptr_ring_empty() API.
> 
>   - if __ptr_ring_empty returns false, the ring may have elements.
>     Possibly, scenario is consumer operation and __ptr_ring_empty
>     operation run concurrently causing false to be returned when
>     ring is empty. To avoid this use locked ptr_ring_empty() API.
> 
> >>>
> >>>>> -->
> >>>>>
> >>>>> net: don't misuse ptr_ring_peek
> >>>>>
> >>>>> ptr_ring_peek only claims to be safe if the result is never
> >>>>> dereferenced, which isn't the case for its use in sch_generic.
> >>>>> Add locked API variants and use the bh one here.
> >>>>>
> >>>>> Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
> >>>>>
> >>>>> ---
> >>>>>
> >>>>
> >>>> [...]
> >>>>
> >>>>> --- a/net/sched/sch_generic.c
> >>>>> +++ b/net/sched/sch_generic.c
> >>>>> @@ -659,7 +659,7 @@ static struct sk_buff *pfifo_fast_peek(struct Qdisc *qdisc)
> >>>>>  	for (band = 0; band < PFIFO_FAST_BANDS && !skb; band++) {
> >>>>>  		struct skb_array *q = band2list(priv, band);
> >>>>>  
> >>>>> -		skb = __skb_array_peek(q);
> >>>>> +		skb = skb_array_peek_bh(q);
> >>>>
> >>>> Ah I should have added a comment here. For now peek() is only used from
> >>>> locking qdiscs. So peek and consume/produce operations will never happen
> >>>> in parallel. In this case we should never hit the false negative case with
> >>>> my patch or the out of bounds reference without my patch.
> > 
> > OK so this is the part I missed. Can you add a comment please?
> > 
> > 
> 
> Yes, working on a documentation patch set to address misleading and missing
> comments/documentation in qdisc layer now.
> 
> >>>> Doing a peek() op without qdisc lock is a bit problematic anyways. With
> >>>> current code another cpu could consume the skb and free it. Either we
> >>>> can ensure a single consumer runs at a time on an array (not the same as
> >>>> qdisc maybe) or just avoid peek operations in this case. My current plan
> >>>> was to just avoid peek() ops altogether, they seem unnecessary with the
> >>>> types of qdiscs I want to be build.
> >>>>
> >>>> Thanks,
> >>>> John
> >>>
> >>> For the lockless qdisc, for net-next, do we need the patch above until you fix that though?
> >>>
> >>
> >> No, I think after this patch (net: ptr_ring: otherwise safe empty checks...) is
> >> applied we do not need any additional fixes in net-next. Future work will
> >> require the above patch (the one you provided) though so its useful work.
> > 
> > The one that avoids allocating extra memory?
> > 
> 
> Let me try summarize again.
> 
> We need the extra memory slot patch if we expose the
> __ptr_ring_empty/__skb_array_empty API. Otherwise we hit the out
> of bounds issues. And for qdisc layer the __skb_array_empty() API
> call is useful so we should not remove it.
> 
> In addition to the qdisc layer using the __skb_array_empty() API if
> we need a peek() API that works without the qdisc lock then your patch,
> the one adding the locked peek API, will be needed. It is not needed
> though until we have a qdisc that would use it without the lock.
> 
> In summary we keep the extra allocation to make the __skb_array_empty() API
> usable. And hold off exposing the skb_array_peek()/ptr_ring_peek() until we
> have a user for it. We can roll your proposed patch into any series we come
> up with for a new/updated qdisc.
> 
> > 
> >> I'll do another review of the false positive case though to be sure the
> >> current code is OK wrt handling false positives and any potential stalls.
> > 
> > 
> > Thanks!
> > 
> >>>>>  	}
> >>>>>  
> >>>>>  	return skb;
> >>>>>