linux-kernel - Re: bad example in Documentation/atomic

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <483CED9A.4070102@yandex.ru>
Date:	Wed, 28 May 2008 08:28:58 +0300
From:	Artem Bityutskiy <dedekind@...dex.ru>
To:	David Miller <davem@...emloft.net>
CC:	Lennert Buytenhek <buytenh@...tstofly.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: bad example in Documentation/atomic_ops.txt ?

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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/