Re: [dpdk-dev] [PATCH] mbuf: optimize refcnt handling during free

[Olivier MATZ <olivier.matz@6wind.com>]

Hi Neil,

On 03/27/2015 01:44 PM, Neil Horman wrote:
> On Fri, Mar 27, 2015 at 10:48:20AM +0000, Ananyev, Konstantin wrote:
>>
>>
>>> -----Original Message-----
>>> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Neil Horman
>>> Sent: Friday, March 27, 2015 10:26 AM
>>> To: Wiles, Keith
>>> Cc: dev@dpdk.org
>>> Subject: Re: [dpdk-dev] [PATCH] mbuf: optimize refcnt handling during free
>>>
>>> On Thu, Mar 26, 2015 at 09:00:33PM +0000, Wiles, Keith wrote:
>>>>
>>>>
>>>> On 3/26/15, 1:10 PM, "Zoltan Kiss" <zoltan.kiss@linaro.org> wrote:
>>>>
>>>>> The current way is not the most efficient: if m->refcnt is 1, the second
>>>>> condition never evaluates, and we set it to 0. If refcnt > 1, the 2nd
>>>>> condition fails again, although the code suggest otherwise to branch
>>>>> prediction. Instead we should keep the second condition only, and remove
>>>>> the
>>>>> duplicate set to zero.
>>>>>
>>>>> Signed-off-by: Zoltan Kiss <zoltan.kiss@linaro.org>
>>>>> ---
>>>>> lib/librte_mbuf/rte_mbuf.h | 5 +----
>>>>> 1 file changed, 1 insertion(+), 4 deletions(-)
>>>>>
>>>>> diff --git a/lib/librte_mbuf/rte_mbuf.h b/lib/librte_mbuf/rte_mbuf.h
>>>>> index 17ba791..3ec4024 100644
>>>>> --- a/lib/librte_mbuf/rte_mbuf.h
>>>>> +++ b/lib/librte_mbuf/rte_mbuf.h
>>>>> @@ -764,10 +764,7 @@ __rte_pktmbuf_prefree_seg(struct rte_mbuf *m)
>>>>> {
>>>>> 	__rte_mbuf_sanity_check(m, 0);
>>>>>
>>>>> -	if (likely (rte_mbuf_refcnt_read(m) == 1) ||
>>>>> -			likely (rte_mbuf_refcnt_update(m, -1) == 0)) {
>>>>> -
>>>>> -		rte_mbuf_refcnt_set(m, 0);
>>>>> +	if (likely (rte_mbuf_refcnt_update(m, -1) == 0)) {
>>>>>
>>>>> 		/* if this is an indirect mbuf, then
>>>>> 		 *  - detach mbuf
>>>>
>>>> I fell for this one too, but read Bruce¹s email
>>>> http://dpdk.org/ml/archives/dev/2015-March/014481.html
>>>
>>> This is still the right thing to do though, Bruce's reasoning is erroneous.
>>
>> No, it is not. I believe Bruce comments is absolutely correct here.
>>
> You and bruce are wrong, I proved that below.
> 
>>> Just because the return from rte_mbuf_refcnt_read returns 1, doesn't mean you
>>
>> It does.
>>
> assertions are meaningless without evidence.
> 
>>> are the last user of the mbuf,
>>> you are only guaranteed that if the update
>>> operation returns zero.
>>>
>>> In other words:
>>> rte_mbuf_refcnt_update(m, -1)
>>>
>>> is an atomic operation
>>>
>>> if (likely (rte_mbuf_refcnt_read(m) == 1) ||
>>>                     likely (rte_mbuf_refcnt_update(m, -1) == 0)) {
>>>
>>>
>>> is not.
>>>
>>> To illustrate, on two cpus, this might occur:
>>>
>>> CPU0					CPU1
>>> rte_mbuf_refcnt_read			...
>>>    returns 1				rte_mbuf_refcnt_read
>>> ...					   returns 1
>>> execute if clause			execute if clause
>>
>>
>> If you have an mbuf with refcnt==N and try to call free() for it N+1 times -
>> it is a bug in your code.
> At what point in time did I indicate this was about multiple frees?  Please
> re-read my post.
> 
>> Such code wouldn't work properly doesn't matter do we use:
>>
>>  if (likely (rte_mbuf_refcnt_read(m) == 1) || likely (rte_mbuf_refcnt_update(m, -1) == 0))
>>
>> or just: 
>> if (likely (rte_mbuf_refcnt_update(m, -1) == 0))
>>
>> To illustrate it with your example:
>> Suppose m.refcnt==1
>>
>> CPU0 executes: 
>>
>> rte_pktmbuf_free(m1)
>>         /*rte_mbuf_refcnt_update(m1, -1) returns 0, so we reset I'ts refcnt and next and put mbuf back to the pool.*/
>>
>> m2 = rte_pktmbuf_alloc(pool);
>>       /*as m1 is 'free' alloc could return same mbuf here, i.e: m2 == m1. */
>>
>> /* m2 refcnt ==1 start using m2 */
>>
> Really missing the point here.
> 
>> CPU1 executes:
>> rte_pktmbuf_free(m1)
>>         /*rte_mbuf_refcnt_update(m1, -1) returns 0, so we reset I'ts refcnt and next and put mbuf back to the pool.*/
>>
>> We just returnend to the pool mbuf that is in use and caused silent memory corruption of the mbuf's content.
>>
> Still missing the point. Please see below
> 
>>>
>>> In the above scenario both cpus fell into the if clause because they both held a
>>> pointer to the same buffer and both got a return value of one, so they skipped
>>> the update portion of the if clause and both executed the internal block of the
>>> conditional expression.  you might be tempted to think thats ok, since that
>>> block just sets the refcnt to zero, and doing so twice isn't harmful, but the
>>> entire purpose of that if conditional above was to ensure that only one
>>> execution context ever executed the conditional for a given buffer.  Look at
>>> what else happens in that conditional:
>>>
>>> static inline struct rte_mbuf* __attribute__((always_inline))
>>> __rte_pktmbuf_prefree_seg(struct rte_mbuf *m)
>>> {
>>>         __rte_mbuf_sanity_check(m, 0);
>>>
>>>         if (likely (rte_mbuf_refcnt_read(m) == 1) ||
>>>                         likely (rte_mbuf_refcnt_update(m, -1) == 0)) {
>>>
>>>                 rte_mbuf_refcnt_set(m, 0);
>>>
>>>                 /* if this is an indirect mbuf, then
>>>                  *  - detach mbuf
>>>                  *  - free attached mbuf segment
>>>                  */
>>>                 if (RTE_MBUF_INDIRECT(m)) {
>>>                         struct rte_mbuf *md = RTE_MBUF_FROM_BADDR(m->buf_addr);
>>>                         rte_pktmbuf_detach(m);
>>>                         if (rte_mbuf_refcnt_update(md, -1) == 0)
>>>                                 __rte_mbuf_raw_free(md);
>>>                 }
>>>                 return(m);
>>>         }
>>>         return (NULL);
>>> }
>>>
>>> If the buffer is indirect, another refcnt update occurs to the buf_addr mbuf,
>>> and in the scenario I outlined above, that refcnt will underflow, likely causing
>>> a buffer leak.  Additionally, the return code of this function is designed to
>>> indicate to the caller if they were the last user of the buffer.  In the above
>>> scenario, two execution contexts will be told that they were, which is wrong.
>>>
>>> Zoltans patch is a good fix
>>
>> I don't think so.
>>
>>
>>>
>>> Acked-by: Neil Horman <nhorman@tuxdriver.com>
>>
>>
>> NACKed-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
>>
> 
> Again, this has nothing to do with how many times you free an object and
> everything to do with why you use atomics here in the first place.  The purpose
> of the if conditional in the above code is to ensure that the contents of the
> conditional block only get executed a single time, correct?  Ostensibly you
> don't want to execution contexts getting in there at the same time right?
> 
> If you have a single buffer with refcnt=1, and two cpus are executing code that
> points to that buffer, and they both call __rte_pktmbuf_prefree_seg at around
> the same time, they can race and both wind up in that conditional block, leading
> to underflow of the md pointer refcnt, which is bad.


You cannot have a mbuf with refcnt=1 referenced by 2 cores, this does
not make sense. Even with the fix you have acked.

CPU0                                   CPU1

m = a_common_mbuf;                     m = a_common_mbuf;
rte_pktmbuf_free(m) // fully atomic
m2 = rte_pktmbuf_alloc()
// m2 returned the same addr than m
// as it was in the pool
                                       // should not access m here
                                       // whatever the operation


Your example below just shows that the current code is wrong if
several cores access a mbuf with refcnt=1 at the same time. That's
true, but that's not allowed.

- If you want to give a mbuf to another core, you put it in a ring
  and stop to reference it on core 0, here not need to have refcnt

- If you want to share a mbuf with another core, you increase the
  reference counter before sending it to core 1. Then, both cores
  will have to call rte_pktmbuf_free().



Regards,
Olivier




> 
> Lets look at another more practical example.  lets imagine that that the mbuf X
> is linked into a set that multiple cpus can query. X->refcnt is held by CPU0,
> and is about to be freed using the above refcnt test model (a read followed by
> an update that gets squashed, anda refcnt set in the free block.  Basically this
> pseudo code:
> 
> if (refcnt_read(X) == 1 || refcnt_update(X) == ) {
> 	refcnt_set(X,0)
> 	mbuf_free(X)
> }
> 
> at the same time CPU1 is preforming a lookup of our needed mbuf from the
> aforementioned set, finds it and takes a refcnt on it.
> 
> 
> CPU0						CPU1
> if(refcnt_read(X))				search for mbuf X
>      returns 1					get pointer to X
> ...						refcnt_update(X,1)
> refcnt_set(X, 0)				...
> mbuf_free(X)
> 
> 
> After the following sequence X is freed but CPU1 is left thinking that it has a
> valid reference to the mbuf.  This is broken.
> 
> As an alternate thought experiment, why use atomics here at all?  X86 is cache
> coherent right?  (ignore that new processor support, as this code predates it).
> If all cpus are able to see a consistent state of a variable, and if every
> context that has a pointer to a given mbuf also has a reference to an mbuf, then
> it should be safe to simply use an integer here rather than an atomic, right?
> If you know that you have a reference to a pointer, just decrement the refcnt
> and check for 0 instead of one, that will tell you that you are the last user of
> a buffer, right?  The answer is you can't because there are conditions in which
> you either need to make a set of conditions atomic (finding a pointer and
> increasing said refcnt under the protection of a lock), or you need some method
> to predicate the execution of some initial or finilazation event (like in
> __rte_pktmbuf_prefree_seg so that you don't have multiple contexts doing that
> same init/finalization and so that you don't provide small windows of
> inconsistency in your atomics, which is what you have above.
> 
> I wrote a demonstration program to illustrate (forgive me, its pretty quick and
> dirty), but I think it illustrates the point:
> 
> #define _GNU_SOURCE
> #include <stdlib.h>
> #include <stdio.h>
> #include <pthread.h>
> #include <stdatomic.h>
> 
> atomic_uint_fast64_t refcnt;
> 
> uint threads = 0;
> 
> static void * thread_exec(void *arg)
> {
>         int i;
>         int cpu = (int)(arg);
>         cpu_set_t cpuset;
>         pthread_t thread;
> 
>         thread = pthread_self();
>         CPU_ZERO(&cpuset);
>         CPU_SET(cpu, &cpuset);
>         pthread_setaffinity_np(thread, sizeof(cpu_set_t), &cpuset);
> 
>         for (i=0; i < 1000; i++) {
>                 if (((atomic_fetch_sub(&refcnt, 0) == 1) ||
>                         atomic_fetch_sub(&refcnt, 1) == 0)) {
>                         // There should only ever be one thread in here at a
>                         atomic_init(&refcnt, 0);
>                         threads |= cpu;
>                         printf("threads = %d\n", threads);
>                         threads &= ~cpu;
> 
> 			// Need to reset the refcnt for future iterations
> 			// but that should be fine since no other thread
> 			// should be in here but us
>                         atomic_init(&refcnt, 1);
>                 }
>         }
> 
>         pthread_exit(NULL);
> }
> 
> int main(int argc, char **argv)
> {
>         pthread_attr_t attr;
>         pthread_t thread_id1, thread_id2;
>         void *status;
> 
>         atomic_init(&refcnt, 1);
> 
>         pthread_attr_init(&attr);
> 
>         pthread_create(&thread_id1, &attr, thread_exec, (void *)1);
>         pthread_create(&thread_id2, &attr, thread_exec, (void *)2);
> 
>         pthread_attr_destroy(&attr);
> 
>         pthread_join(thread_id1, &status);
>         pthread_join(thread_id2, &status);
> 
> 
>         exit(0);
> 
> }
> 
> 
> If you run this on an smp system, you'll clearly see that, occasionally the
> value of threads is 3.  That indicates that you have points where you have
> multiple contexts executing in that conditional block that has clearly been
> coded to only expect one.  You can't make the assumption that every pointer has
> a held refcount here, you need to incur the update penalty.
> 
> Neil
>