Re: bad example in Documentation/atomic_ops.txt ?

[Artem Bityutskiy]

David,

do you have any comments on this? I paste the example below for
convenience.

Artem Bityutskiy wrote:
> I it looks like the example in the Documentation/atomic_ops.txt
> file at line 232 is not quite right. The obj->active = 0 will
> be delayed, but not further than spin_unlock() in obj_timeout().
> Becaus spin_unlock() has a memory barrier.
>
> I guess you would need to move spin_lock(&global_list_lock) to
> obj_list_del() to make the example valid.
>
> This confused me when I read the file.

static void obj_list_add(struct obj *obj)
{
       obj->active = 1;
       list_add(&obj->list);
}

static void obj_list_del(struct obj *obj)
{
       list_del(&obj->list);
       obj->active = 0;
}

static void obj_destroy(struct obj *obj)
{
       BUG_ON(obj->active);
       kfree(obj);
}

struct obj *obj_list_peek(struct list_head *head)
{
       if (!list_empty(head)) {
               struct obj *obj;

               obj = list_entry(head->next, struct obj, list);
               atomic_inc(&obj->refcnt);
               return obj;
       }
       return NULL;
}

void obj_poke(void)
{
       struct obj *obj;

       spin_lock(&global_list_lock);
       obj = obj_list_peek(&global_list);
       spin_unlock(&global_list_lock);

       if (obj) {
               obj->ops->poke(obj);
               if (atomic_dec_and_test(&obj->refcnt))
                       obj_destroy(obj);
       }
}

void obj_timeout(struct obj *obj)
{
       spin_lock(&global_list_lock);
       obj_list_del(obj);
       spin_unlock(&global_list_lock);

       if (atomic_dec_and_test(&obj->refcnt))
               obj_destroy(obj);
}

(This is a simplification of the ARP queue management in the
generic neighbour discover code of the networking.  Olaf Kirch
found a bug wrt. memory barriers in kfree_skb() that exposed
the atomic_t memory barrier requirements quite clearly.)

Given the above scheme, it must be the case that the obj->active
update done by the obj list deletion be visible to other processors
before the atomic counter decrement is performed.

Otherwise, the counter could fall to zero, yet obj->active would still
be set, thus triggering the assertion in obj_destroy().  The error
sequence looks like this:

       cpu 0                           cpu 1
       obj_poke()                      obj_timeout()
       obj = obj_list_peek();
       ... gains ref to obj, refcnt=2
                                       obj_list_del(obj);
                                       obj->active = 0 ...
                                       ... visibility delayed ...
                                       atomic_dec_and_test()
                                       ... refcnt drops to 1 ...
       atomic_dec_and_test()
       ... refcount drops to 0 ...
       obj_destroy()
       BUG() triggers since obj->active
       still seen as one
                                       obj->active update visibility occurs

With the memory barrier semantics required of the atomic_t operations
which return values, the above sequence of memory visibility can never
happen.  Specifically, in the above case the atomic_dec_and_test()
counter decrement would not become globally visible until the
obj->active update does.


--
Best Regards,
Artem Bityutskiy (ÐÑÑÑÐ ÐÐÑÑÑÐÐÐ)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/