From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/7649 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Deduplicating atomics written in terms of CAS Date: Sun, 17 May 2015 00:55:36 -0400 Message-ID: <20150517045536.GA25046@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="u3/rZRmxL6MmkK24" X-Trace: ger.gmane.org 1431838564 26718 80.91.229.3 (17 May 2015 04:56:04 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 17 May 2015 04:56:04 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-7661-gllmg-musl=m.gmane.org@lists.openwall.com Sun May 17 06:55:59 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1YtqcG-0000IZ-3i for gllmg-musl@m.gmane.org; Sun, 17 May 2015 06:55:56 +0200 Original-Received: (qmail 28058 invoked by uid 550); 17 May 2015 04:55:54 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 28007 invoked from network); 17 May 2015 04:55:49 -0000 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:7649 Archived-At: --u3/rZRmxL6MmkK24 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Lots of archs define most or all of their atomics except a_cas in terms of a_cas. The attached atomic.h is a proposed replacement for arch-specific atomic.h that would live in src/internal. The arch atomic.h files would be replaced with atomic_arch.h, which could opt to define nothing but a_cas, or could define more primitives itself if it can do so more efficiently. The second attachment, atomic_generic.h, is an implementation of the atomics (and other non-atomic ops we've traditionally had in atomic.h) using GNU C builtins. This file can be used as-is for any new archs that satisfy the following conditions: - They're not supported by compilers too old to have the __sync_* builtins. - They don't need runtime switching/detection of atomic implementations. - GCC doesn't generate pathologically bad code for the builtins. Even if some of these conditions aren't met, atomic_generic.h may be useful when porting to help determine the right way to implement atomics by watching what the compiler does, and it may be suitable for early porting stages before a proper atomic.h is written. I'm not sure if I'll try to integrate this stuff right away or as part of the bits deduplication and build system overhaul that's been coming-soon for a long time. Comments welcome. Rich --u3/rZRmxL6MmkK24 Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="atomic.h" #ifndef _ATOMIC_H #define _ATOMIC_H #include "atomic_arch.h" #ifndef a_swap static inline int a_swap(volatile int *p, int v) { int old; do old = *p; while (a_cas(p, old, v) != old); return old; } #endif #ifndef a_fetch_add static inline int a_fetch_add(volatile int *p, int v) { int old; do old = *p; while (a_cas(p, old, old+v) != old); return old; } #endif #ifndef a_and static inline void a_and(volatile int *p, int v) { int old; do old = *p; while (a_cas(p, old, old&v) != old); } #endif #ifndef a_or static inline void a_or(volatile int *p, int v) { int old; do old = *p; while (a_cas(p, old, old|v) != old); } #endif #ifndef a_inc static inline void a_inc(volatile int *p) { a_fetch_add(p, 1); } #endif #ifndef a_dec static inline void a_dec(volatile int *p) { a_fetch_add(p, -1); } #endif #ifndef a_store static inline void a_store(volatile int *p, int v) { #ifdef a_barrier a_barrier(); *p = v; a_barrier(); #else a_swap(p, v); #endif } #endif #ifndef a_barrier static void a_barrier() { volatile int tmp = 0; a_cas(&tmp, 0, 0); } #endif #ifndef a_spin #define a_spin a_barrier #endif #ifndef a_and_64 static inline void a_and_64(volatile uint64_t *p, uint64_t v) { union { uint64_t v; uint32_t r[2]; } u = { v }; if (u.r[0]+1) a_and((int *)p, u.r[0]); if (u.r[1]+1) a_and((int *)p+1, u.r[1]); } #endif #ifndef a_or_64 static inline void a_or_64(volatile uint64_t *p, uint64_t v) { union { uint64_t v; uint32_t r[2]; } u = { v }; if (u.r[0]) a_or((int *)p, u.r[0]); if (u.r[1]) a_or((int *)p+1, u.r[1]); } #endif #ifndef a_cas_p static inline void *a_cas_p(volatile void *p, void *t, void *s) { return (void *)a_cas(p, (int)t, (int)s); } #endif #ifndef a_or_l static inline void a_or_l(volatile void *p, long v) { if (sizeof(long) == sizeof(int)) a_or(p, v); else a_or_64(p, v); } #endif #ifndef a_crash static inline void a_crash() { *(volatile char *)0=0; } #endif #ifndef a_ctz_64 static inline int a_ctz_64(uint64_t x) { static const char debruijn64[64] = { 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28, 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11, 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10, 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12 }; static const char debruijn32[32] = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14 }; if (sizeof(long) < 8) { uint32_t y = x; if (!y) { y = x>>32; return 32 + debruijn32[(y&-y)*0x076be629 >> 27]; } return debruijn32[(y&-y)*0x076be629 >> 27]; } return debruijn64[(x&-x)*0x022fdd63cc95386dull >> 58]; } #endif #ifndef a_ctz_l static inline int a_ctz_l(unsigned long x) { static const char debruijn32[32] = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14 }; if (sizeof(long) == 8) return a_ctz_64(x); return debruijn32[(x&-x)*0x076be629 >> 27]; } #endif #endif --u3/rZRmxL6MmkK24 Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="atomic_generic.h" static inline int a_cas(volatile int *p, int t, int s) { return __sync_val_compare_and_swap(p, t, s); } static inline void *a_cas_p(volatile void **p, void *t, void *s) { return __sync_val_compare_and_swap(p, t, s); } static inline int a_swap(volatile int *p, int v) { int old; do old = *p; while (!__sync_bool_compare_and_swap(p, old, v)); return old; } static inline int a_fetch_add(volatile int *p, int v) { return __sync_fetch_and_add(p, v); } static inline void a_and(volatile int *p, int v) { __sync_fetch_and_and(p, v); } static inline void a_or(volatile int *p, int v) { __sync_fetch_and_or(p, v); } static void a_barrier() { __sync_synchronize(); } static inline void a_crash() { __builtin_trap(); } static inline int a_ctz_l(unsigned long x) { return __builtin_ctzl(x); } static inline int a_ctz_64(uint64_t x) { return __builtin_ctzll(x); } #define a_cas a_cas #define a_cas_p a_cas_p #define a_swap a_swap #define a_fetch_add #define a_and #define a_or #define a_barrier #define a_crash #define a_ctz_l #define a_ctz_64 #endif --u3/rZRmxL6MmkK24--