From owner-freebsd-arch@FreeBSD.ORG Tue Sep 18 19:53:59 2012 Return-Path: Delivered-To: arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id EA9031065670 for ; Tue, 18 Sep 2012 19:53:59 +0000 (UTC) (envelope-from jilles@stack.nl) Received: from mx1.stack.nl (unknown [IPv6:2001:610:1108:5012::107]) by mx1.freebsd.org (Postfix) with ESMTP id 8861E8FC15 for ; Tue, 18 Sep 2012 19:53:59 +0000 (UTC) Received: from snail.stack.nl (snail.stack.nl [IPv6:2001:610:1108:5010::131]) by mx1.stack.nl (Postfix) with ESMTP id 353301203C1; Tue, 18 Sep 2012 21:53:54 +0200 (CEST) Received: by snail.stack.nl (Postfix, from userid 1677) id 0CAB92847B; Tue, 18 Sep 2012 21:53:54 +0200 (CEST) Date: Tue, 18 Sep 2012 21:53:53 +0200 From: Jilles Tjoelker To: Poul-Henning Kamp Message-ID: <20120918195353.GA56160@stack.nl> References: <95608.1347973160@critter.freebsd.dk> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <95608.1347973160@critter.freebsd.dk> User-Agent: Mutt/1.5.21 (2010-09-15) Cc: arch@freebsd.org Subject: Re: Aliasing issue with TAILQ on ppc64 ? X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 18 Sep 2012 19:54:00 -0000 On Tue, Sep 18, 2012 at 12:59:20PM +0000, Poul-Henning Kamp wrote: > In Varnish I have adopted 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