[Mesa-dev] [RFC 1/3] mesa: Add new fast mtx_t mutex type for basic use cases

[Tapani Pälli]

one error found below ..

On 10/10/2017 05:45 AM, Timothy Arceri wrote:
> While modern pthread mutexes are very fast, they still incur a call to an
> external DSO and overhead of the generality and features of pthread mutexes.
> Most mutexes in mesa only needs lock/unlock, and the idea here is that we can
> inline the atomic operation and make the fast case just two intructions.
> Mutexes are subtle and finicky to implement, so we carefully copy the
> implementation from Ulrich Dreppers well-written and well-reviewed paper:
> 
>    "Futexes Are Tricky"
>    http://www.akkadia.org/drepper/futex.pdf
> 
> We implement "mutex3", which gives us a mutex that has no syscalls on
> uncontended lock or unlock.  Further, the uncontended case boils down to a
> cmpxchg and an untaken branch and the uncontended unlock is just a locked decr
> and an untaken branch.  We use __builtin_expect() to indicate that contention
> is unlikely so that gcc will put the contention code out of the main code
> flow.
> 
> A fast mutex only supports lock/unlock, can't be recursive or used with
> condition variables.  We keep the pthread mutex implementation around as
> full_mtx_t for the few places where we use condition variables or recursive
> locking.  For platforms or compilers where futex and atomics aren't available,
> mtx_t falls back to the pthread mutex.
> 
> The pthread mutex lock/unlock overhead shows up on benchmarks for CPU bound
> applications.  Most CPU bound cases are helped and some of our internal
> bind_buffer_object heavy benchmarks gain up to 10%.
> 
> Signed-off-by: Kristian Høgsberg <krh at bitplanet.net>
> Signed-off-by: Timothy Arceri <tarceri at itsqueeze.com>
> ---
>   configure.ac          |   3 ++
>   src/util/simple_mtx.h | 146 ++++++++++++++++++++++++++++++++++++++++++++++++++
>   2 files changed, 149 insertions(+)
>   create mode 100644 src/util/simple_mtx.h
> 
> diff --git a/configure.ac b/configure.ac
> index 903a3979d4..47fe427d19 100644
> --- a/configure.ac
> +++ b/configure.ac
> @@ -887,20 +887,23 @@ linux* | cygwin* | darwin* | solaris* | *-gnu* | gnu*)
>       ;;
>   * )
>       pthread_stubs_possible="yes"
>       ;;
>   esac
>   
>   if test "x$pthread_stubs_possible" = xyes; then
>       PKG_CHECK_MODULES(PTHREADSTUBS, pthread-stubs >= 0.4)
>   fi
>   
> +dnl Check for futex for fast inline simple_mtx_t.
> +AC_CHECK_HEADER([linux/futex.h], [DEFINES="$DEFINES -DHAVE_FUTEX"])
> +
>   dnl SELinux awareness.
>   AC_ARG_ENABLE([selinux],
>       [AS_HELP_STRING([--enable-selinux],
>           [Build SELinux-aware Mesa @<:@default=disabled@:>@])],
>       [MESA_SELINUX="$enableval"],
>       [MESA_SELINUX=no])
>   if test "x$enable_selinux" = "xyes"; then
>       PKG_CHECK_MODULES([SELINUX], [libselinux], [],
>           [AC_CHECK_HEADER([selinux/selinux.h],[],
>                            [AC_MSG_ERROR([SELinux headers not found])])
> diff --git a/src/util/simple_mtx.h b/src/util/simple_mtx.h
> new file mode 100644
> index 0000000000..bd365ac237
> --- /dev/null
> +++ b/src/util/simple_mtx.h
> @@ -0,0 +1,146 @@
> +/*
> + * Copyright © 2015 Intel
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> + * IN THE SOFTWARE.
> + */
> +
> +#if defined(__GNUC__) && defined(HAVE_FUTEX)
> +
> +/* mtx_t - Fast, simple mutex
> + *
> + * While modern pthread mutexes are very fast (implemented using futex), they
> + * still incur a call to an external DSO and overhead of the generality and
> + * features of pthread mutexes.  Most mutexes in mesa only needs lock/unlock,
> + * and the idea here is that we can inline the atomic operation and make the
> + * fast case just two intructions.  Mutexes are subtle and finicky to
> + * implement, so we carefully copy the implementation from Ulrich Dreppers
> + * well-written and well-reviewed paper:
> + *
> + *   "Futexes Are Tricky"
> + *   http://www.akkadia.org/drepper/futex.pdf
> + *
> + * We implement "mutex3", which gives us a mutex that has no syscalls on
> + * uncontended lock or unlock.  Further, the uncontended case boils down to a
> + * locked cmpxchg and an untaken branch, the uncontended unlock is just a
> + * locked decr and an untaken branch.  We use __builtin_expect() to indicate
> + * that contention is unlikely so that gcc will put the contention code out of
> + * the main code flow.
> + *
> + * A fast mutex only supports lock/unlock, can't be recursive or used with
> + * condition variables.
> + */
> +
> +typedef struct {
> +   uint32_t val;
> +} simple_mtx_t;
> +
> +#define _SIMPLE_MTX_INITIALIZER_NP { 0 }
> +
> +#include <stdint.h>
> +#include <values.h>
> +#include <linux/futex.h>
> +#include <sys/time.h>
> +#include <sys/syscall.h>
> +
> +static inline long sys_futex(void *addr1, int op, int val1, struct timespec *timeout, void *addr2, int val3)
> +{
> +   return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3);
> +}
> +
> +static inline int futex_wake(uint32_t *addr) {
> +   return sys_futex(addr, FUTEX_WAKE, 1, NULL, NULL, 0);
> +}
> +
> +static inline int futex_wait(uint32_t *addr, int32_t value) {
> +   return sys_futex(addr, FUTEX_WAIT, value, NULL, NULL, 0);
> +}
> +
> +static inline void
> +simple_mtx_init(simple_mtx_t *mtx, int type)
> +{
> +   assert(type == mtx_plain);
> +
> +   mtx->val = 0;
> +}
> +
> +static inline void
> +simple_mtx_destroy(simple_mtx_t *mtx)
> +{
> +}
> +
> +static inline void
> +simple_mtx_lock(simple_mtx_t *mtx)
> +{
> +   uint32_t c;
> +
> +   c = __sync_val_compare_and_swap(&mtx->val, 0, 1);
> +   if (__builtin_expect(c != 0, 0)) {
> +      if (c != 2)
> +         c = __sync_lock_test_and_set(&mtx->val, 2);
> +      while (c != 0) {
> +         futex_wait(&mtx->val, 2);
> +         c = __sync_lock_test_and_set(&mtx->val, 2);
> +      }
> +   }
> +}
> +
> +static inline void
> +simple_mtx_unlock(simple_mtx_t *mtx)
> +{
> +   uint32_t c;
> +
> +   c = __sync_fetch_and_sub(&mtx->val, 1);
> +   if (__builtin_expect(c != 1, 0)) {
> +      mtx->val = 0;
> +      futex_wake(&mtx->val);
> +   }
> +}
> +
> +#else
> +
> +typedef simple_mtx_t mtx_t;

should be

typedef mtx_t simple_mtx_t

> +
> +#define _SIMPLE_MTX_INITIALIZER_NP _MTX_INITIALIZER_NP
> +
> +static inline void
> +simple_mtx_init(simple_mtx_t *mtx, int type)
> +{
> +   mtx_init(mtx, type);
> +}
> +
> +static inline void
> +simple_mtx_destroy(simple_mtx_t *mtx)
> +{
> +   mtx_destroy(mtx);
> +}
> +
> +static inline void
> +simple_mtx_lock(simple_mtx_t *mtx)
> +{
> +   mtx_lock(mtx);
> +}
> +
> +static inline void
> +simple_mtx_unlock(simple_mtx_t *mtx)
> +{
> +   mtx_unlock(mtx);
> +}
> +
> +#endif
>