From patchwork Tue Nov 29 12:49:11 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alan Modra X-Patchwork-Id: 128286 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 5B9AAB6F75 for ; Tue, 29 Nov 2011 23:49:41 +1100 (EST) Received: (qmail 27016 invoked by alias); 29 Nov 2011 12:49:38 -0000 Received: (qmail 27007 invoked by uid 22791); 29 Nov 2011 12:49:36 -0000 X-SWARE-Spam-Status: No, hits=-2.6 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW X-Spam-Check-By: sourceware.org Received: from mail-yx0-f175.google.com (HELO mail-yx0-f175.google.com) (209.85.213.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 29 Nov 2011 12:49:19 +0000 Received: by yenl4 with SMTP id l4so2058219yen.20 for ; Tue, 29 Nov 2011 04:49:19 -0800 (PST) Received: by 10.236.78.72 with SMTP id f48mr70151941yhe.121.1322570958991; Tue, 29 Nov 2011 04:49:18 -0800 (PST) Received: from bubble.grove.modra.org ([115.187.252.19]) by mx.google.com with ESMTPS id c10sm56592763yhj.2.2011.11.29.04.49.15 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 29 Nov 2011 04:49:18 -0800 (PST) Received: by bubble.grove.modra.org (Postfix, from userid 1000) id ABD37170C2BF; Tue, 29 Nov 2011 23:19:11 +1030 (CST) Date: Tue, 29 Nov 2011 23:19:11 +1030 From: Alan Modra To: Richard Henderson , Jakub Jelinek , gcc-patches@gcc.gnu.org Subject: Re: Fix libgomp semaphores Message-ID: <20111129124911.GR7827@bubble.grove.modra.org> Mail-Followup-To: Richard Henderson , Jakub Jelinek , gcc-patches@gcc.gnu.org References: <20111125000328.GD5085@bubble.grove.modra.org> <20111125073839.GN27242@tyan-ft48-01.lab.bos.redhat.com> <20111127225343.GA7827@bubble.grove.modra.org> <4ED4208A.8080803@redhat.com> <20111129005240.GM7827@bubble.grove.modra.org> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20111129005240.GM7827@bubble.grove.modra.org> User-Agent: Mutt/1.5.20 (2009-06-14) X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Since there were a number of changes requested, and some confusion over what was happening in this code, it might be better if I post a new patch and we start over. In this patch I'm still using the MSB for the wait flag, and count in the low 31 bits, as that way is slightly more efficient on powerpc. However, if some other target generates really bad code for the masking operations, then I'm happy enough to change the comment and use #define SEM_WAIT 1 #define SEM_INC 2 Tested both ways on powerpc-linux. PR libgomp/51249 * config/linux/sem.h: Rewrite. * config/linux/sem.c: Rewrite. Index: libgomp/config/linux/sem.h =================================================================== --- libgomp/config/linux/sem.h (revision 181770) +++ libgomp/config/linux/sem.h (working copy) @@ -1,4 +1,4 @@ -/* Copyright (C) 2005, 2009 Free Software Foundation, Inc. +/* Copyright (C) 2005, 2009, 2011 Free Software Foundation, Inc. Contributed by Richard Henderson . This file is part of the GNU OpenMP Library (libgomp). @@ -24,34 +24,65 @@ /* This is a Linux specific implementation of a semaphore synchronization mechanism for libgomp. This type is private to the library. This - implementation uses atomic instructions and the futex syscall. */ + counting semaphore implementation uses atomic instructions and the + futex syscall, and a single 32-bit int to store semaphore state. + The low 31 bits are the count, the top bit is a flag set when some + threads may be waiting. */ #ifndef GOMP_SEM_H #define GOMP_SEM_H 1 +#include /* For INT_MIN */ + typedef int gomp_sem_t; +#define SEM_WAIT INT_MIN +#define SEM_INC 1 + +extern void gomp_sem_wait_slow (gomp_sem_t *, int); +extern void gomp_sem_post_slow (gomp_sem_t *); -static inline void gomp_sem_init (gomp_sem_t *sem, int value) +static inline void +gomp_sem_init (gomp_sem_t *sem, int value) { - *sem = value; + *sem = value * SEM_INC; } -extern void gomp_sem_wait_slow (gomp_sem_t *); -static inline void gomp_sem_wait (gomp_sem_t *sem) +static inline void +gomp_sem_destroy (gomp_sem_t *sem) { - if (!__sync_bool_compare_and_swap (sem, 1, 0)) - gomp_sem_wait_slow (sem); } -extern void gomp_sem_post_slow (gomp_sem_t *); -static inline void gomp_sem_post (gomp_sem_t *sem) +static inline bool +likely_compare_exchange (int *ptr, int *expected, int val, bool weak, + enum memmodel succ, enum memmodel fail) { - if (!__sync_bool_compare_and_swap (sem, 0, 1)) - gomp_sem_post_slow (sem); + return __builtin_expect (__atomic_compare_exchange_n (ptr, expected, val, + weak, succ, fail), 1); } -static inline void gomp_sem_destroy (gomp_sem_t *sem) +static inline void +gomp_sem_wait (gomp_sem_t *sem) { + int count = *sem; + + while ((count & ~SEM_WAIT) != 0) + if (likely_compare_exchange (sem, &count, count - SEM_INC, + false, MEMMODEL_ACQUIRE, MEMMODEL_RELAXED)) + return; + gomp_sem_wait_slow (sem, count); } +static inline void +gomp_sem_post (gomp_sem_t *sem) +{ + int count = *sem; + + while (1) + if (likely_compare_exchange (sem, &count, ((count + SEM_INC) & ~SEM_WAIT), + false, MEMMODEL_RELEASE, MEMMODEL_RELAXED)) + break; + + if (__builtin_expect (count & SEM_WAIT, 0)) + gomp_sem_post_slow (sem); +} #endif /* GOMP_SEM_H */ Index: libgomp/config/linux/sem.c =================================================================== --- libgomp/config/linux/sem.c (revision 181770) +++ libgomp/config/linux/sem.c (working copy) @@ -1,4 +1,4 @@ -/* Copyright (C) 2005, 2008, 2009 Free Software Foundation, Inc. +/* Copyright (C) 2005, 2008, 2009, 2011 Free Software Foundation, Inc. Contributed by Richard Henderson . This file is part of the GNU OpenMP Library (libgomp). @@ -28,34 +28,56 @@ #include "wait.h" - void -gomp_sem_wait_slow (gomp_sem_t *sem) +gomp_sem_wait_slow (gomp_sem_t *sem, int count) { + /* First loop spins a while. */ + while (count == 0) + if (do_spin (sem, 0) + /* Spin timeout, nothing changed. Set waiting flag. */ + && likely_compare_exchange (sem, &count, SEM_WAIT, + false, MEMMODEL_ACQUIRE, MEMMODEL_RELAXED)) + { + futex_wait (sem, SEM_WAIT); + count = *sem; + break; + } + /* Something changed. If it wasn't the wait flag, we're good to go. */ + else if (__builtin_expect (((count = *sem) & SEM_WAIT) == 0 && count != 0, + 1)) + { + if (likely_compare_exchange (sem, &count, count - SEM_INC, + false, MEMMODEL_ACQUIRE, MEMMODEL_RELAXED)) + return; + } + + /* Second loop waits until semaphore is posted. We always exit this + loop with wait flag set, so next post will awaken a thread. */ while (1) { - int val = __sync_val_compare_and_swap (sem, 0, -1); - if (val > 0) + unsigned int wake = count & ~SEM_WAIT; + int newval = SEM_WAIT; + + if (wake != 0) + newval |= wake - SEM_INC; + if (likely_compare_exchange (sem, &count, newval, + false, MEMMODEL_ACQUIRE, MEMMODEL_RELAXED)) { - if (__sync_bool_compare_and_swap (sem, val, val - 1)) - return; + if (wake != 0) + { + /* If we can wake more threads, do so now. */ + if (wake > SEM_INC) + gomp_sem_post_slow (sem); + break; + } + do_wait (sem, SEM_WAIT); + count = *sem; } - do_wait (sem, -1); } } void gomp_sem_post_slow (gomp_sem_t *sem) { - int old, tmp = *sem, wake; - - do - { - old = tmp; - wake = old > 0 ? old + 1 : 1; - tmp = __sync_val_compare_and_swap (sem, old, wake); - } - while (old != tmp); - - futex_wake (sem, wake); + futex_wake (sem, 1); }