Date: Thu, 10 Oct 2002 14:01:40 -0700 From: Terry Lambert <tlambert2@mindspring.com> To: Stefan Farfeleder <e0026813@stud3.tuwien.ac.at> Cc: Don Lewis <dl-freebsd@catspoiler.org>, jhb@FreeBSD.ORG, jmallett@FreeBSD.ORG, current@FreeBSD.ORG, phk@FreeBSD.ORG Subject: Re: [PATCH] Re: Junior Kernel Hacker page updated... Message-ID: <3DA5EAB4.75F158BE@mindspring.com> References: <20021008204605.GA252@frog.fafoe> <200210090426.g994QTvU037393@gw.catspoiler.org> <20021009225606.GC306@frog.fafoe> <3DA4B6C1.ED1BACEB@mindspring.com> <20021010203053.GA265@frog.fafoe>
next in thread | previous in thread | raw e-mail | index | archive | help
Stefan Farfeleder wrote:
> Imagine this scenario where CPU 0 inserts a knote kn1 (the marker) in
> knote_scan and CPU 1 kn2 in kqueue_enqueue:
>
> CPU 0 | CPU 1
> --------------------------------+-------------------------------
> kn1->kn_tqe.tqe_next = NULL; |
> |
> --------------------------------+-------------------------------
> kn1->kn_tqe.tqe_prev = | kn2->kn_tqe.tqe_next = NULL;
> kq_head.tqh_last; |
> --------------------------------+-------------------------------
> *kq_head.tqh_last = kn1; | kn2->kn_tqe.tqe_prev =
> | kq_head.tqh_last;
> --------------------------------+-------------------------------
> kq_head.tqh_last = | *kq_head.tqh_last = kn2;
> &kn1->kn_tqe.tqe_next; |
> --------------------------------+-------------------------------
> | kq_head.tqh_last =
> | &kn2->kn_tqe.tqe_next;
>
> The marker would never appear on the queue.
The macro is broken. Here is a fix.
#define TAILQ_INSERT_TAIL(head, elm, field) do { \
void **savepp; \
(elm)->field.tqe_next = NULL; \
(elm)->field.tqe_prev = (head)->tqh_last; \
savepp = (head)->tqh_last; \
(head)->tqh_last = &(elm)->field.tqe_next; \
(elm)->field.tqe_prev = savepp; \
*savepp = (elm); \
} while (0)
I'm not sure that it's possible to totally close the race; I think the
way you would have to do it is to traverse the tqh_last pointer until
the tqh_last->file.tqe_next == NULL, before reference it (ugly). The
failure mode with the race is an inverted insertion order, which I
think, in this case, is not a problem. The double setting of the prev
guarantees it has a "harmless" value for a traversal during insertion;
it acts as if the insertion had not occurred, if there are two that
occurred simultaneously, until both sets of data are valid.
This is doable in Intel assembly, I think (CMPXCHGL). Ugh. On other
architectures, there's no way to avoid a mutex (e.g. MIPS).
I hate tailq's. 8-(.
-- Terry
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-current" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3DA5EAB4.75F158BE>