Date: Tue, 18 Sep 2012 21:53:53 +0200 From: Jilles Tjoelker <jilles@stack.nl> To: Poul-Henning Kamp <phk@phk.freebsd.dk> Cc: arch@freebsd.org Subject: Re: Aliasing issue with TAILQ on ppc64 ? Message-ID: <20120918195353.GA56160@stack.nl> In-Reply-To: <95608.1347973160@critter.freebsd.dk> References: <95608.1347973160@critter.freebsd.dk>
next in thread | previous in thread | raw e-mail | index | archive | help
On Tue, Sep 18, 2012 at 12:59:20PM +0000, Poul-Henning Kamp wrote: > In Varnish I have adopted <sys/queue.h> and today I saw a weird issue > on a PPC64 platform, which makes me wonder if we have a potential > aliasing issue with TAILQs. > The backwards pointers in TAILQs point to the forward pointer of > the previous element, rather than to the top of the previous > element. > To go backwards you therefore have to go two steps backwards and > one step forward. > TAILQ_PREV and TAILQ_LAST do this by assuming that the head and > element structures for a TAILQ are the same, and casts the point > from &(elem->next) to &head, and dereferences head->last as a proxy > for elem->prev. This is elegant, but not type-safe. > I have not 100% confirmed, that in the in problem we had with PPC64, > the compiler in this case fails to spot the aliasing. When I made > the head-struct volatile, the problem went away, which it also did > when I put in a function call at the suspect place to force a > register spill. > I have previously tried to find a way to rewrite TAILQ_LAST/PREV > to be type-safe, but utterly failed, and I have reached the > conclusion that with the current "API" or minor modifications > thereof, that is patently impossible. > It may be a good idea to find some way to make sure the compiler > spots the potential aliasing, but I am not sufficiently up to > date on compiler optimizations to know a safe and reliable way > to do that. (Would explicitly casting throuh a void do it ?) > Details: > https://github.com/varnish/Varnish-Cache/blob/3.0/bin/varnishd/cache_ban.c > lines 388-393. > The problem happens on startup, when the ban_head list is empty, > and I belive the issue is that the (V)TAILQ_INSERT_HEAD() has not > stored the head->last pointer, by the time the (V)TAILQ_LAST() tries > to dereference it, and that the compiler does not spot the aliasing. I think the compiler considers this a strict-aliasing violation. Although the types of tqh_last and tqe_prev match, there is a problem when accessing a TAILQ_ENTRY using an lvalue of type TAILQ_HEAD. A dirty workaround is -fno-strict-aliasing but this reduces optimization opportunities all over the code. An obvious fix is to make TAILQ_ENTRY and TAILQ_HEAD the same type (and not just structurally identical) or to add an intermediate struct which is the same between them. However, I think the TAILQ_LAST and TAILQ_PREV macros are better rewritten using __containerof, also because a subtraction is cheaper than a pointer dereference. Unfortunately, this requires different parameters in the macros and/or the GCC typeof keyword, and will need an explicit check for an empty tail queue or the first element. Something like (untested): #define TAILQ_LAST(head, field) \ (TAILQ_EMPTY((head)) ? NULL : \ __containerof((head)->tqh_last, __typeof__(*(head)->tqh_first), \ field.tqe_prev)) #define TAILQ_PREV(elm, field) \ (*(elm)->tqe_prev != NULL ? NULL : \ __containerof((elm)->tqe_prev, __typeof__(*(elm)), \ field.tqe_prev)) -- Jilles Tjoelker
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20120918195353.GA56160>