concurrencykit / ck Goto Github PK

Concurrency primitives, safe memory reclamation mechanisms and non-blocking (including lock-free) data structures designed to aid in the research, design and implementation of high performance concurrent systems developed in C99+.

Home Page: http://concurrencykit.org/

License: Other

C 96.12% C++ 0.45% Makefile 3.38% Shell 0.05%

ck's Introduction

Continuous Integration

Drone	Travis	Cirrus

Compilers tested in the past include gcc, clang, cygwin, icc, mingw32, mingw64 and suncc across all supported architectures. All new architectures are required to pass the integration test and under-go extensive code review.

Continuous integration is currently enabled for the following targets:

darwin/clang/x86-64
freebsd/clang/x86-64
linux/gcc/arm64
linux/gcc/x86-64
linux/clang/x86-64
linux/clang/ppc64le

Compile and Build

Step 1. ./configure For additional options try ./configure --help
Step 2. In order to compile regressions (requires POSIX threads) use make regressions. In order to compile libck use make all or make.
Step 3. In order to install use make install To uninstall use make uninstall.

See http://concurrencykit.org/ for more information.

Supported Architectures

Concurrency Kit supports any architecture using compiler built-ins as a fallback. There is usually a performance degradation associated with this.

Concurrency Kit has specialized assembly for the following architectures:

aarch64
arm
ppc
ppc64
riscv64
s390x
sparcv9+
x86
x86_64

Features

Concurrency Primitives

ck_pr

Concurrency primitives as made available by the underlying architecture, includes support for all atomic operations (natively), transactional memory, pipeline control, read-for-ownership and more.

ck_backoff

A simple and efficient (minimal noise) backoff function.

ck_cc

Abstracted compiler builtins when writing efficient concurrent data structures.

Safe Memory Reclamation

ck_epoch

A scalable safe memory reclamation mechanism with support idle threads and various optimizations that make it better than or competitive with many state-of-the-art solutions.

ck_hp

Implements support for hazard pointers, a simple and efficient lock-free safe memory reclamation mechanism.

Data Structures

ck_array

A simple concurrently-readable pointer array structure.

ck_bitmap

An efficient multi-reader and multi-writer concurrent bitmap structure.

ck_ring

Efficient concurrent bounded FIFO data structures with various performance trade-off. This includes specialization for single-reader, many-reader, single-writer and many-writer.

ck_fifo

A reference implementation of the first published lock-free FIFO algorithm, with specialization for single-enqueuer-single-dequeuer and many-enqueuer-single-dequeuer and extensions to allow for node re-use.

ck_hp_fifo

A reference implementation of the above algorithm, implemented with safe memory reclamation using hazard pointers.

ck_hp_stack

A reference implementation of a Treiber stack with support for hazard pointers.

ck_stack

A reference implementation of an efficient lock-free stack, with specialized variants for a variety of memory management strategies and bounded concurrency.

ck_queue

A concurrently readable friendly derivative of the BSD-queue interface. Coupled with a safe memory reclamation mechanism, implement scalable read-side queues with a simple search and replace.

ck_hs

An extremely efficient single-writer-many-reader hash set, that satisfies lock-freedom with bounded concurrency without any usage of atomic operations and allows for recycling of unused or deleted slots. This data structure is recommended for use as a general hash-set if it is possible to compute values from keys. Learn more at https://engineering.backtrace.io/workload-specialization/ and http://concurrencykit.org/articles/ck_hs.html.

ck_ht

A specialization of the ck_hs algorithm allowing for disjunct key-value pairs.

ck_rhs

A variant of ck_hs that utilizes robin-hood hashing to allow for improved performance with higher load factors and high deletion rates.

Synchronization Primitives

ck_ec

An extremely efficient event counter implementation, a better alternative to condition variables.

ck_barrier

A plethora of execution barriers including: centralized barriers, combining barriers, dissemination barriers, MCS barriers, tournament barriers.

ck_brlock

A simple big-reader lock implementation, write-biased reader-writer lock with scalable read-side locking.

ck_bytelock

An implementation of bytelocks, for research purposes, allowing for (in theory), fast read-side acquisition without the use of atomic operations. In reality, memory barriers are required on the fast path.

ck_cohort

A generic lock cohorting interface, allows you to turn any lock into a NUMA-friendly scalable NUMA lock. There is a significant trade-off in fast path acquisition cost. Specialization is included for all relevant lock implementations in Concurrency Kit. Learn more by reading "Lock Cohorting: A General Technique for Designing NUMA Locks".

ck_elide

A generic lock elision framework, allows you to turn any lock implementation into an elision-aware implementation. This requires support for restricted transactional memory by the underlying hardware.

ck_pflock

Phase-fair reader-writer mutex that provides strong fairness guarantees between readers and writers. Learn more by reading "Spin-Based Reader-Writer Synchronization for Multiprocessor Real-Time Systems".

ck_rwcohort

A generic read-write lock cohorting interface, allows you to turn any read-write lock into a NUMA-friendly scalable NUMA lock. There is a significant trade-off in fast path acquisition cost. Specialization is included for all relevant lock implementations in Concurrency Kit. Learn more by reading "Lock Cohorting: A General Technique for Designing NUMA Locks".

ck_rwlock

A simple centralized write-biased read-write lock.

ck_sequence

A sequence counter lock, popularized by the Linux kernel, allows for very fast read and write synchronization for simple data structures where deep copy is permitted.

ck_swlock

A single-writer specialized read-lock that is copy-safe, useful for data structures that must remain small, be copied and contain in-band mutexes.

ck_tflock

Task-fair locks are fair read-write locks, derived from "Scalable reader-writer synchronization for shared-memory multiprocessors".

ck_spinlock

A basic but very fast spinlock implementation.

ck_spinlock_anderson

Scalable and fast anderson spinlocks. This is here for reference, one of the earliest scalable and fair lock implementations.

ck_spinlock_cas

A basic spinlock utilizing compare_and_swap.

ck_spinlock_dec

A basic spinlock, a C adaption of the older optimized Linux kernel spinlock for x86. Primarily here for reference.

ck_spinlock_fas

A basic spinlock utilizing atomic exchange.

ck_spinlock_clh

An efficient implementation of the scalable CLH lock, providing many of the same performance properties of MCS with a better fast-path.

ck_spinlock_hclh

A NUMA-friendly CLH lock.

ck_spinlock_mcs

An implementation of the seminal scalable and fair MCS lock.

ck_spinlock_ticket

An implementation of fair centralized locks.

ck's People

Contributors

Stargazers

Watchers

Forkers

pkhuong skjaidev waytai dhobsd gburd clibs programfan ryanbaylorkillea martin-ly yunkai psudaemon m0rcq dmeearm flashbuckets dution89630 rahus koolhazz imace timwee pranith rileyberton llxwj pccq2002 abioy xingzhixi leverly chunshengster bobbyzhu swayer ericthemagician emaxerrno masterlvng postwait jacklicn zhangmobai mindis cota tddg ploki wittrock revanchegames ameyjadiye ezhangle wintersnow212 tk2510 llsdimple esvitech jonaskunze stromnov mhaberler cautonwong claudiouzelac johnnydotdev jisqyv tchen0123 auvi heymoon tomzhang springstar dxq-git xuanhan863 jweih arthursxl8 cdfpaz wenhuizhang imladenovic lizh06 wuchuguang aganno2 hm537 danieldc weinix bossjones awesomeleo bhanug chenbk85 pankaj-lakhina bklyn mlpesant hongyunnchen hincoin rkrn dawnft fengshao0907 rijalati rahulpathakgit riftio disigma-network xzturn bssrdf amin-jabri flying-pig zengyuxing007 fdotli roger2000hk mistuke guotie pirater w4ngyi ass-sniper

ck's Issues

Update includes for FreeBSD kernel

ck_cohort regression fails if CORES=1

make[2]: Entering directory '/home/mah/ck/regressions/ck_cohort/validate'
./validate `expr 1 / 2` 2 1
ERROR: Number of cohorts must be greater than 0

the validate.c program is just unhappy about argv[1] == "1"

please advise:

fix Makefile to suppress validate run if CORES=1
fix validate.c to exit(0) the test while giving a message

Loading of global epoch is questionably early in ck_epoch_begin

The epoch is loaded into a record's local epoch not-after the record is marked as active, so, for example, ck_epoch_poll may ignore an thread that is about to enter an epoch-protected section with an old epoch.

More concretely, imagine a sequentially consistent execution (so we can reason in terms of reorderings), which is more strict than the model concurrencykit is actually using.

thread A calls ck_epoch_begin, loads the global epoch G https://github.com/concurrencykit/ck/blob/3679c1fb8bc/include/ck_epoch.h#L96 and stops executing
thread B calls ck_epoch_poll several times:
- ck_epoch_scan is called https://github.com/concurrencykit/ck/blob/3679c1fb8bc/src/ck_epoch.c#L219
- ck_epoch_scan ignores thread A (since A's active flag hasn't been set yet) https://github.com/concurrencykit/ck/blob/3679c1fb8bc/src/ck_epoch.c#L247
- the global epoch is incremented https://github.com/concurrencykit/ck/blob/3679c1fb8bc/src/ck_epoch.c#L431
thread A is resumed, finally setting its active flag, but pinned to an epoch many generations old https://github.com/concurrencykit/ck/blob/3679c1fb8bc/include/ck_epoch.h#L109

This results in thread A and thread B executing concurrently while arbitrarily many generations apart, but a distance of 1 (or 2) generations is an assumption for correctness in the academic descriptions of the scheme that I have seen. I'm unfamiliar with the details of CK's variant, so this may be OK, but it seems to me that it needs more justification.

I believe moving the epoch manipulations to be after setting the active flag and fencing should defend against the failure mode described above, if it is indeed a problem.

(This possible problem was noticed and pointed out to me by @aturon.)

Regressions: ck_epoch validate: heap-use-after-free

$ LDFLAGS="-fsanitize=address -g -ggdb -O4 -fno-omit-frame-pointer" CFLAGS="${LDFLAGS}" CXXFLAGS="${LDFLAGS}" CPPFLAGS="${LDFLAGS}" ./configure 
Detecting operating system.......success [linux]
Detecting machine architecture...success [x86_64]
Finding dirname command..........success [/usr/bin/dirname]
Determining build directory......success [/home/lebedevri/src/ck]
Finding gzip tool................success [/bin/gzip]
Finding suitable compiler........success [/usr/bin/cc]
Detecting VMA bits...............success [48]
Checking header file usability...success [stdbool.h]
Checking header file usability...success [stddef.h]
Checking header file usability...success [stdint.h]
Checking header file usability...success [string.h]
Detecting git SHA................success [7f625a6]
Generating header files..........success
Generating build files...........success

           VERSION = 0.5.1
           GIT_SHA = 7f625a6
         BUILD_DIR = /home/lebedevri/src/ck
           SRC_DIR = /home/lebedevri/src/ck
            SYSTEM = linux
           PROFILE = x86_64
                CC = /usr/bin/cc
          COMPILER = gcc
            CFLAGS = -D_XOPEN_SOURCE=600 -D_BSD_SOURCE -D_DEFAULT_SOURCE -std=gnu99 -pedantic -Wall -W -Wundef -Wendif-labels -Wshadow -Wpointer-arith -Wcast-align -Wcast-qual -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -Wnested-externs -Winline -Wdisabled-optimization -fstrict-aliasing -O2 -pipe -Wno-parentheses -fsanitize=address -g -ggdb -O4 -fno-omit-frame-pointer -fPIC
    PTHREAD_CFLAGS = -pthread
                LD = /usr/bin/cc
            LDNAME = libck.so
    LDNAME_VERSION = libck.so.0.5.1
      LDNAME_MAJOR = libck.so.0
           LDFLAGS = -Wl,-soname,libck.so.0 -m64 -fsanitize=address -g -ggdb -O4 -fno-omit-frame-pointer -shared -fPIC
              GZIP = /bin/gzip -c
             CORES = 8
      POINTER_PACK = CK_MD_POINTER_PACK_DISABLE
          VMA_BITS = 48
      MEMORY_MODEL = CK_MD_TSO
               RTM = CK_MD_RTM_DISABLE

Headers will be installed in /usr/local/include
Libraries will be installed in /usr/local/lib
Documentation will be installed in /usr/local/share/man

$ cc -v
Using built-in specs.
COLLECT_GCC=cc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/5/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Debian 5.3.1-7' --with-bugurl=file:///usr/share/doc/gcc-5/README.Bugs --enable-languages=c,ada,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-5 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-libmpx --enable-plugin --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-5-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-5-amd64 --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-5-amd64 --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc --enable-multiarch --with-arch-32=i586 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 5.3.1 20160121 (Debian 5.3.1-7)

----[ Testing epoch....
make[2]: Entering directory '/home/lebedevri/src/ck/regressions/ck_epoch/validate'
./ck_stack 8 1
Deferrals: 4629421 (0.93)
Deferrals: 4690919 (0.94)
Peak: 22938 (0.46%), 908 pending
Reclamations: 4999092

Deferrals: 4657749 (0.93)
Peak: 18423 (0.37%), 16 pending
Reclamations: 4999984

Deferrals: 4670424 (0.93)
Peak: 16095 (0.32%), 15 pending
Reclamations: 4999985

Deferrals: 4514228 (0.90)
Peak: 18808 (0.38%), 4 pending
Reclamations: 4999996

Deferrals: 4491884 (0.90)
Deferrals: 4593448 (0.92)
Peak: 19770 (0.40%), 0 pending
Reclamations: 5000000

Peak: 20551 (0.41%), 6 pending
Reclamations: 4999994

Deferrals: 4544868 (0.91)
Peak: 23832 (0.48%), 16 pending
Reclamations: 4999984

Peak: 17372 (0.35%), 2 pending
Reclamations: 4999998

./ck_epoch_synchronize `expr 8 / 2` `expr 8 / 2` 1
[W] 0.45: |=================================================================
==7693==ERROR: AddressSanitizer: heap-use-after-free on address 0x603001119618 at pc 0x000000401aab bp 0x7fedcd7adc30 sp 0x7fedcd7adc28
READ of size 8 at 0x603001119618 thread T7
    #0 0x401aaa in ck_stack_pop_upmc ../../../include/ck_stack.h:105
    #1 0x401aaa in write_thread /home/lebedevri/src/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c:189
    #2 0x7fedd395e283 in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x7283)
    #3 0x7fedd369797c in clone (/lib/x86_64-linux-gnu/libc.so.6+0xe897c)

0x603001119618 is located 8 bytes inside of 32-byte region [0x603001119610,0x603001119630)
freed by thread T5 here:
    #0 0x7fedd3c0abfa in __interceptor_free (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x93bfa)
    #1 0x4019ca in destructor /home/lebedevri/src/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c:81
    #2 0x4019ca in write_thread /home/lebedevri/src/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c:206
    #3 0x7fedd395e283 in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x7283)

previously allocated by thread T6 here:
    #0 0x7fedd3c0ae9a in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x93e9a)
    #1 0x4016b9 in write_thread /home/lebedevri/src/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c:169
    #2 0x7fedd395e283 in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x7283)

Thread T7 created by T0 here:
    #0 0x7fedd3bacef4 in pthread_create (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x35ef4)
    #1 0x400ea0 in main /home/lebedevri/src/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c:249
    #2 0x7fedd35cf86f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2086f)

Thread T5 created by T0 here:
    #0 0x7fedd3bacef4 in pthread_create (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x35ef4)
    #1 0x400ea0 in main /home/lebedevri/src/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c:249
    #2 0x7fedd35cf86f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2086f)

Thread T6 created by T0 here:
    #0 0x7fedd3bacef4 in pthread_create (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x35ef4)
    #1 0x400ea0 in main /home/lebedevri/src/ck/regressions/ck_epoch/validate/ck_epoch_synchronize.c:249
    #2 0x7fedd35cf86f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2086f)

SUMMARY: AddressSanitizer: heap-use-after-free ../../../include/ck_stack.h:105 ck_stack_pop_upmc
Shadow bytes around the buggy address:
  0x0c068021b270: fd fd fa fa fd fd fd fd fa fa fd fd fd fd fa fa
  0x0c068021b280: fd fd fd fd fa fa fd fd fd fd fa fa fd fd fd fd
  0x0c068021b290: fa fa fd fd fd fd fa fa fd fd fd fd fa fa fd fd
  0x0c068021b2a0: fd fd fa fa fd fd fd fd fa fa fd fd fd fd fa fa
  0x0c068021b2b0: fd fd fd fd fa fa fd fd fd fd fa fa 00 00 00 00
=>0x0c068021b2c0: fa fa fd[fd]fd fd fa fa 00 00 00 00 fa fa 00 00
  0x0c068021b2d0: 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa
  0x0c068021b2e0: 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00
  0x0c068021b2f0: fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00
  0x0c068021b300: 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa
  0x0c068021b310: 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
==7693==ABORTING
Makefile:10: recipe for target 'check' failed
make[2]: *** [check] Error 1
make[2]: Leaving directory '/home/lebedevri/src/ck/regressions/ck_epoch/validate'

Implement volatile ck_cc_memcpy

This is primarily needed for ck_ring. On TSO / PSO, we can fall back to builtin / library implementation, otherwise, TSO architectures require regular store implementation to avoid additional synchronization on enqueue operation. Right now we rely on silent contract of sfence for larger block sizes but some folks do not guarantee this. In addition to this, https://twitter.com/pkhuong/status/553224121359007744

ck_cc_memcpy provides ordering guarantees with respect to ck_pr_fence.

Is it possible to make ck available on Android & IOS?

I tried and I failed to run configure.
Detecting operating system.......success [darwin]
Detecting machine architecture...success [arm]
Finding dirname command..........success [/usr/bin/dirname]
Determining build directory......success [/Users/kin/Documents/ude4/kmc_engine_ext/thirdparty/src/ck]
Finding gzip tool................success [/usr/bin/gzip]
Finding suitable compiler........./configure: line 599: ./.1: cannot execute binary file
failed [update compiler]

Support for gyp?

Hey there!

First off, thank you for all the hard work put into this library. The documentation is great, and where it falls down, the source is easy to understand. On top of all of that... it solves problems for me so I can focus on what I'm actually trying to do. :)

I've been using ck in a side project of mine that I decided to use gyp as the build system for. I basically got to a point where I have a gyp project file that I wrote for ck that compiles it on my architecture so I can use it as a native dependency in the main project.

So, long story short: would supporting gyp ever be something you'd consider? I realize there's already a good chunk of Makefile hand-crafted loving going on, but I would envision it as a "gyp and make living side by side" sort of thing. It's a single file addition, and as far as I can see, it has enough flexibility to tailor compiler/linker flags as needed for various platforms... and the logic to actually figure out what platform it's on.

(to add context, I'm asking because I'm curious if I should bother trying to make my project handle ck's usage of make directly, or if it's worth trying to port what ck's Makefile does now into a gyp project file, and then submit THAT as a PR to ck)

Regression suite core affinity utility function stack overflow

$ LDFLAGS="-fsanitize=address -g -ggdb -O4 -fno-omit-frame-pointer" CFLAGS="${LDFLAGS}" CXXFLAGS="${LDFLAGS}" CPPFLAGS="${LDFLAGS}" ./configure 
Detecting operating system.......success [linux]
Detecting machine architecture...success [x86_64]
Finding dirname command..........success [/usr/bin/dirname]
Determining build directory......success [/home/lebedevri/src/ck]
Finding gzip tool................success [/bin/gzip]
Finding suitable compiler........success [/usr/bin/cc]
Detecting VMA bits...............success [48]
Checking header file usability...success [stdbool.h]
Checking header file usability...success [stddef.h]
Checking header file usability...success [stdint.h]
Checking header file usability...success [string.h]
Detecting git SHA................success [7f625a6]
Generating header files..........success
Generating build files...........success

           VERSION = 0.5.1
           GIT_SHA = 7f625a6
         BUILD_DIR = /home/lebedevri/src/ck
           SRC_DIR = /home/lebedevri/src/ck
            SYSTEM = linux
           PROFILE = x86_64
                CC = /usr/bin/cc
          COMPILER = gcc
            CFLAGS = -D_XOPEN_SOURCE=600 -D_BSD_SOURCE -D_DEFAULT_SOURCE -std=gnu99 -pedantic -Wall -W -Wundef -Wendif-labels -Wshadow -Wpointer-arith -Wcast-align -Wcast-qual -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -Wnested-externs -Winline -Wdisabled-optimization -fstrict-aliasing -O2 -pipe -Wno-parentheses -fsanitize=address -g -ggdb -O4 -fno-omit-frame-pointer -fPIC
    PTHREAD_CFLAGS = -pthread
                LD = /usr/bin/cc
            LDNAME = libck.so
    LDNAME_VERSION = libck.so.0.5.1
      LDNAME_MAJOR = libck.so.0
           LDFLAGS = -Wl,-soname,libck.so.0 -m64 -fsanitize=address -g -ggdb -O4 -fno-omit-frame-pointer -shared -fPIC
              GZIP = /bin/gzip -c
             CORES = 8
      POINTER_PACK = CK_MD_POINTER_PACK_DISABLE
          VMA_BITS = 48
      MEMORY_MODEL = CK_MD_TSO
               RTM = CK_MD_RTM_DISABLE

Headers will be installed in /usr/local/include
Libraries will be installed in /usr/local/lib
Documentation will be installed in /usr/local/share/man

$ cc -v
Using built-in specs.
COLLECT_GCC=cc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/5/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Debian 5.3.1-7' --with-bugurl=file:///usr/share/doc/gcc-5/README.Bugs --enable-languages=c,ada,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-5 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-libmpx --enable-plugin --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-5-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-5-amd64 --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-5-amd64 --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc --enable-multiarch --with-arch-32=i586 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 5.3.1 20160121 (Debian 5.3.1-7)

----[ Testing spinlock....
make[2]: Entering directory '/home/lebedevri/src/ck/regressions/ck_spinlock/validate'
./ck_ticket 8 1
Creating threads (mutual exclusion)...done
Waiting for threads to finish correctness regression...done (passed)
./ck_mcs 8 1
Creating threads (mutual exclusion)...done
Waiting for threads to finish correctness regression...=================================================================
==11292==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7f5e64ffade0 at pc 0x7f5e68c476cc bp 0x7f5e64ffacf0 sp 0x7f5e64ffa4a0
WRITE of size 128 at 0x7f5e64ffade0 thread T2
    #0 0x7f5e68c476cb in __asan_memset (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x886cb)
    #1 0x40116f in aff_iterate_core ../../common.h:297
    #2 0x40116f in thread /home/lebedevri/src/ck/regressions/ck_spinlock/validate/validate.h:68
    #3 0x7f5e6869e283 in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x7283)
    #4 0x7f5e683d797c in clone (/lib/x86_64-linux-gnu/libc.so.6+0xe897c)

Address 0x7f5e64ffade0 is located in stack of thread T2 at offset 160 in frame
    #0 0x40109f in thread /home/lebedevri/src/ck/regressions/ck_spinlock/validate/validate.h:60

  This frame has 2 object(s):
    [64, 80) 'node'
    [192, 288) 's' <== Memory access at offset 160 partially underflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
Thread T2 created by T0 here:
    #0 0x7f5e68bf4ef4 in pthread_create (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x35ef4)
    #1 0x400cda in main /home/lebedevri/src/ck/regressions/ck_spinlock/validate/validate.h:166
    #2 0x7f5e6830f86f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2086f)

SUMMARY: AddressSanitizer: stack-buffer-overflow ??:0 __asan_memset
Shadow bytes around the buggy address:
  0x0fec4c9f7560: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fec4c9f7570: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fec4c9f7580: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fec4c9f7590: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fec4c9f75a0: 00 00 00 00 00 00 00 00 f1 f1 f1 f1 f1 f1 f1 f1
=>0x0fec4c9f75b0: 00 00 f4 f4 f2 f2 f2 f2 f2 f2 f2 f2[f2]f2 f2 f2
  0x0fec4c9f75c0: 00 00 00 00 00 00 00 00 00 00 00 00 f3 f3 f3 f3
  0x0fec4c9f75d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fec4c9f75e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fec4c9f75f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fec4c9f7600: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
==11292==ABORTING
Makefile:7: recipe for target 'check' failed
make[2]: *** [check] Error 1
make[2]: Leaving directory '/home/lebedevri/src/ck/regressions/ck_spinlock/validate'

ck tests fail if default gcc/ck_pr.h is used on MIPS64

While building package ck from latest source on MIPS64 (little endian) we have got following errors:

----[ Testing bytelock....
make[2]: Entering directory '/home/jurica/SBUILD/ck-mips64/NEW_GIT/git/ck/regressions/ck_bytelock/validate'
./validate 16 1
Creating threads (mutual exclusion)...done
Waiting for threads to finish correctness regression...ERROR [RD:113]: 3 != 0
Makefile:11: recipe for target 'check' failed
make[2]: *** [check] Error 1
make[2]: Leaving directory '/home/jurica/SBUILD/ck-mips64/NEW_GIT/git/ck/regressions/ck_bytelock/validate'

----[ Testing fifo....
make[2]: Entering directory '/home/jurica/SBUILD/ck-mips64/NEW_GIT/git/ck/regressions/ck_fifo/validate'
./ck_fifo_spsc 16 1 64000
T [3:0xffec014a70] 4 != 2
Makefile:8: recipe for target 'check' failed
make[2]: *** [check] Error 1
make[2]: Leaving directory '/home/jurica/SBUILD/ck-mips64/NEW_GIT/git/ck/regressions/ck_fifo/validate'

----[ Testing ring....
make[2]: Entering directory '/home/jurica/SBUILD/ck-mips64/NEW_GIT/git/ck/regressions/ck_ring/validate'
./ck_ring_spsc 16 1 16384
Makefile:9: recipe for target 'check' failed
make[2]: *** [check] Segmentation fault
make[2]: Leaving directory '/home/jurica/SBUILD/ck-mips64/NEW_GIT/git/ck/regressions/ck_ring/validate'

----[ Testing sequence....
make[2]: Entering directory '/home/jurica/SBUILD/ck-mips64/NEW_GIT/git/ck/regressions/ck_sequence/validate'
./ck_sequence 16 1
ERROR: Failed regression: copy->c (13064 != 6030 + 7030 / 13060)
Makefile:11: recipe for target 'check' failed
make[2]: *** [check] Error 1
make[2]: Leaving directory '/home/jurica/SBUILD/ck-mips64/NEW_GIT/git/ck/regressions/ck_sequence/validate'

Those failures does not occur on amd64 when gcc/ck_pr.h is used.

I do understand that gcc/ck_pr.h is only meant to serve as a lay-over until a native port is developed.
I would like, if possible, to have working lay-over before native port is done.

Later this package could be ported to different 32bit and 64bit MIPS architectures.

Any help is welcomed!

Previous patch:
#35
did resolve previous problem on MIPS64 also.

Thank you!

Regards,
Jurica

0.6.0 fails to build on PowerPC

Tried to build concurrencykit-0.6.0 as it is a dependency for sysbench-1.0.7. Unfortunately building concurrencykit did not work.

My machine:
System: Host: T801 Kernel: 4.10.17-gentoo ppc64 (32 bit) Desktop: MATE 1.18.0
Distro: Gentoo Base System release 2.3
Machine: No /sys/class/dmi; using dmidecode: dmidecode is not installed.
CPU: Dual core PPC970MP altivec supported (-MCP-) speed/max: 2300.000000MHz/2300 MHz
Graphics: Card-1: NVIDIA NV43 [GeForce 6600]
Card-2: Advanced Micro Devices [AMD/ATI] Cedar [Radeon HD 5000/6000/7350/8350 Series]
Display Server: X.org 1.19.3 driver: radeon tty size: 132x24 Advanced Data: N/A for root
Network: Card-1: Broadcom Limited NetXtreme BCM5780 Gigabit Ethernet driver: tg3

build.log:
build_log.txt

Building the library for multiple architectures

I've had some difficulty building CK for different architectures. Specifically, I'm developing a library which links to CK on iOS/32/64, Mac/32/64/Intel/PPC, Windows/32/64, Linux/32/64, Android32/64. The library is being developed in Xcode on Mac with strict C99 conformance. Here are some of the difficulties I've encountered.

Preference to compile with other code. I'd rather build an entire project at once rather than making separate libraries and then linking to them. For instance, adding the SQLite amalgamated source file to a project is infinitely easier than managing a full build from their source tree. CK requires a generated ck_md.h file from make, providing defines not available in my SDK, ie: VMA_BITS. If there's any way to provide these define values outside of make, it would help streamline my process.
No easy provision for multiple architectures. Developing in Xcode and building multiple targets which may compile for different architectures is extremely convenient. As CK must be built with the make system, there is no easy way to automate the build to coincide with the xcodebuild settings. It would be convenient if ./configure contained switches for CK's supported architectures. I would then reconfigure and build for each target architecture.

armv7-a: ck_pr_md_store_double not defined, however ck_pr_store_64 IS

what gives?
i.MX6:
mah@cubox-i:/next/home/mah/src/ck-cubox-i/regressions/ck_pr/validate$ ./ck_pr_load
ck_pr_load_64: SUCCESS
ck_pr_load_32: SUCCESS
ck_pr_load_16: SUCCESS
ck_pr_load_8: SUCCESS
mah@cubox-i:/next/home/mah/src/ck-cubox-i/regressions/ck_pr/validate$ ./ck_pr_store
ck_pr_store_64: SUCCESS
ck_pr_store_32: SUCCESS
ck_pr_store_16: SUCCESS
ck_pr_store_8: SUCCESS

Implicit switch fall through triggers warnings with GCC 7

ck_ht_hash.h contains a few switch() statements with implicit fall through logic. Which triggers GCC warnings with the -Wimplicit-fallthrough option introduced in GCC 7.

Code:

  switch(len & 3)
  {
  case 3: k1 ^= tail[2] << 16;
  case 2: k1 ^= tail[1] << 8;
  case 1: k1 ^= tail[0];
          k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
  };
...
  switch(len & 7)
  {
  case 7: h ^= (uint64_t)(data2[6]) << 48;
  case 6: h ^= (uint64_t)(data2[5]) << 40;
  case 5: h ^= (uint64_t)(data2[4]) << 32;
  case 4: h ^= (uint64_t)(data2[3]) << 24;
  case 3: h ^= (uint64_t)(data2[2]) << 16;
  case 2: h ^= (uint64_t)(data2[1]) << 8;
  case 1: h ^= (uint64_t)(data2[0]);
          h *= m;
  };
...
  switch(len)
  {
  case 3: h2 ^= ((const unsigned char*)data)[2] << 16;
  case 2: h2 ^= ((const unsigned char*)data)[1] << 8;
  case 1: h2 ^= ((const unsigned char*)data)[0];
      h2 *= m;
  };

Compiler warnings:

In file included from /build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht.c:44:0:

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h: In function ‘MurmurHash64A’:

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:198:13: warning: this statement may fall through [-Wimplicit-fallthrough=]

   case 7: h ^= (uint64_t)(data2[6]) << 48;

           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:199:3: note: here

   case 6: h ^= (uint64_t)(data2[5]) << 40;

   ^~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:199:13: warning: this statement may fall through [-Wimplicit-fallthrough=]

   case 6: h ^= (uint64_t)(data2[5]) << 40;

           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:200:3: note: here

   case 5: h ^= (uint64_t)(data2[4]) << 32;

   ^~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:200:13: warning: this statement may fall through [-Wimplicit-fallthrough=]

   case 5: h ^= (uint64_t)(data2[4]) << 32;

           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:201:3: note: here

   case 4: h ^= (uint64_t)(data2[3]) << 24;

   ^~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:201:13: warning: this statement may fall through [-Wimplicit-fallthrough=]

   case 4: h ^= (uint64_t)(data2[3]) << 24;

           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:202:3: note: here

   case 3: h ^= (uint64_t)(data2[2]) << 16;

   ^~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:202:13: warning: this statement may fall through [-Wimplicit-fallthrough=]

   case 3: h ^= (uint64_t)(data2[2]) << 16;

           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:203:3: note: here

   case 2: h ^= (uint64_t)(data2[1]) << 8;

   ^~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:203:13: warning: this statement may fall through [-Wimplicit-fallthrough=]

   case 2: h ^= (uint64_t)(data2[1]) << 8;

           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

/build/sysbench-1.0.10.13/third_party/concurrency_kit/tmp/ck/src/ck_ht_hash.h:204:3: note: here

   case 1: h ^= (uint64_t)(data2[0]);

   ^~~~

The manual lists a number of options to silence the warnings, which I guess is the right thing to do here. The most portable way seems to be adding /* fall through */ comments, which are also supported by Clang.

MIPS64 port

@cognet - I can take this on, pending remote access to MIPS64 box.

ck_sequence test vs docs

The test here shows different usage than the man page here.

Specifically, a56cac3 indicates a problem with the usage given in the man page.

I don't fully understand the complexity myself, but maybe this paper will be helpful while reviewing this.

eventcount merge

@pkhuong wrote a wonderful eventcount implementation which we would like to merge down. This ticket will track audit and merge process.

Publish to Homebrew

I'm not sure how often a user is using ck on OS X but it would be nice to install with Homebrew as well.

See Formulas for a list of formula format.

configure for a 'gcc builtins' (non-native) port?

http://concurrencykit.org/community.html 8) says:

If you don't want a native port, Concurrency Kit will drop-back to using GCC atomic intrinsics.

how do I achieve that?

It might be useful for us - as a baseline package which works everywhere, maybe just not with stellar performance

error: assigning to 'struct ck_spinlock_hclh ' from incompatible type 'void '

When trying to incorporate ck spinlock in my code I'm getting errors such as the following:

3rdparty/ck-0.6.0/include/spinlock/clh.h:81:13: error: assigning to 'struct ck_spinlock_clh *' from incompatible type 'void *'
        previous = ck_pr_fas_ptr(queue, thread);
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~

3rdparty/ck-0.6.0/include/spinlock/mcs.h:100:13: error: assigning to 'struct ck_spinlock_mcs *' from incompatible type 'void *'
        previous = ck_pr_fas_ptr(queue, node);
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~

3rdparty/ck-0.6.0/include/spinlock/hclh.h:89:13: error: assigning to 'struct ck_spinlock_hclh *' from incompatible type 'void *'
        previous = ck_pr_fas_ptr(local_queue, thread);
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The compiler used is clang 4.0.0

I am getting above error on compiling stack snippet provided in one the article of concurrencykit

USED :
g++ source.cpp -lpthread -std=c++0x -o a.out
./a.out

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<pthread.h>
#include<ck_pr.h>
#include<limits.h>
#include<cstdint>
using namespace std;
struct node {
    void *value;
    struct node *next;
};
void stack_push(struct node **top, struct node *entry, void *value)
{
    entry->value = (node *)value;



    do {

        entry->next = (node *)ck_pr_load_ptr(top);

    } while (ck_pr_cas_ptr(top, entry->next, entry) == false);



    return;

}



struct node *stack_pop(struct node **top)

{

    struct node *r, *next;



    do {

        r = (node *)ck_pr_load_ptr(top);

        if (r == NULL)

            return NULL;



        next = (node *)ck_pr_load_ptr(&r->next);

    } while (ck_pr_cas_ptr(top, r, next) == false);



    return r;

}

Compilation error

/usr/local/include/gcc/ck_pr.h: In function ‘void* ck_pr_load_ptr(const void*)’:
/usr/local/include/gcc/ck_pr.h:77:9: error: expected primary-expression before ‘volatile’
/usr/local/include/gcc/ck_pr.h:77:9: error: expected ‘)’ before ‘volatile’
/usr/local/include/gcc/ck_pr.h:77:39: error: expected ‘)’ before ‘;’ token
/usr/local/include/gcc/ck_pr.h: In function ‘void ck_pr_store_ptr(void*, const void*)’:
/usr/local/include/gcc/ck_pr.h:84:2: error: expected primary-expression before ‘volatile’
/usr/local/include/gcc/ck_pr.h:84:2: error: expected ‘)’ before ‘volatile’
/usr/local/include/gcc/ck_pr.h:84:44: error: expected ‘)’ before ‘;’ token
/usr/local/include/gcc/ck_pr.h: In function ‘char ck_pr_load_char(const char*)’:
/usr/local/include/gcc/ck_pr.h:90:1: error: expected primary-expression before ‘volatile’
/usr/local/include/gcc/ck_pr.h:90:1: error: expected ‘)’ before ‘volatile’
/usr/local/include/gcc/ck_pr.h:90:1: error: expected ‘)’ before ‘;’ token
/usr/local/include/gcc/ck_pr.h: In function ‘void ck_pr_store_char(char*, char)’:
/usr/local/include/gcc/ck_pr.h:90:1: error: expected primary-expression before ‘volatile’
/usr/local/include/gcc/ck_pr.h:90:1: error: expected ‘)’ before ‘volatile’
/usr/local/include/gcc/ck_pr.h:90:1: error: expected ‘)’ before ‘;’ token
/usr/local/include/gcc/ck_pr.h: In function ‘unsigned int ck_pr_load_uint(const unsigned int*)’:
/usr/local/include/gcc/ck_pr.h:91:1: error: expected primary-expression before ‘volatile’
/usr/local/include/gcc/ck_pr.h:91:1: error: expected ‘)’ before ‘volatile’
/usr/local/include/gcc/ck_pr.h:91:1: error: expected ‘)’ before ‘;’ token
/usr/local/include/gcc/ck_pr.h: In function ‘void ck_pr_store_uint(unsigned int*, unsignedint)’:
/usr/local/include/gcc/ck_pr.h:91:1: error: expected primary-expression before ‘volatile’
/usr/local/include/gcc/ck_pr.h:91:1: error: expected ‘)’ before ‘volatile’
/usr/local/include/gcc/ck_pr.h:91:1: error: expected ‘)’ before ‘;’ token
/usr/local/include/gcc/ck_pr.h: In function ‘int ck_pr_load_int(const int*)’:
/usr/local/include/gcc/ck_pr.h:92:1: error: expected primary-expression before ‘volatile’
/usr/local/include/gcc/ck_pr.h:92:1: error: expected ‘)’ before ‘volatile’
/usr/local/include/gcc/ck_pr.h:92:1: error: expected ‘)’ before ‘;’ token
/usr/local/include/gcc/ck_pr.h: In function ‘void ck_pr_store_int(int*, int)’:
/usr/local/include/gcc/ck_pr.h:92:1: error: expected primary-expression before ‘volatile’
/usr/local/include/gcc/ck_pr.h:92:1: error: expected ‘)’ before ‘volatile’

could you please help me with this , I am getting this wrong ..?

ck_ht usage

Please find test code and comments below:
std::map<int,void*> stdMap;
MC::Concurrency::HashTable htSPMC(CK_HT_MODE_BYTESTRING,MC::Concurrency::HashTable::Mode::M_MPMC);
char* data="123";
for(int i=1;i<50000;++i)
{
stdMap[i]=(void*)i;
htSPMC.Set((char*)(&i),sizeof(i),(void*)i);
};
printf("remaining %d %d\n",stdMap.size(), htSPMC.Size());
---> We got 49999 49999
for(int i=1;i<50000;++i)
{
stdMap[i]=(void*)i;
htSPMC.Set((char*)(&i),sizeof(i),(void*)i);
};
printf("remaining %d %d\n",stdMap.size(), htSPMC.Size());
---> We got 49999 50316

Building as sub-project

So I am trying to build ck as an autoconf/automake sub-package: http://www.gnu.org/software/automake/manual/html_node/Subpackages.html

Unfortunately ck is not auto* compliant.

=== configuring in lib/ck (/home/phil/git/trafficserver/trafficserver/lib/ck)
configure: running /bin/sh ./configure --disable-option-checking '--prefix=/usr/local'  --cache-file=/dev/null --srcdir=.
Unknown option --disable-option-checking
Unknown option --cache-file=/dev/null
Unknown option --srcdir=.

I have a small patch that is just a workaround, but wanted to solicit input as to what you think would be the best course of action. Would you consider integrating autoconf/automake into ck? Would you rather just put in stubs for these options so it doesn't error out?

Thanks.

Support section-ful and section-less protected sections in epoch

Requires test coverage and re-testing on target platforms. Section-ful invocation needs to make sure that no section-less invocations exist.

feature parity across all supported platforms: undo @f6a2cb1

the issue with @f6a2cb1b39326e90e5e1cd2789741d60808340dd (ck_pr/x86_32: Drop 64-bit operations..) is: it breaks feature parity across platforms, requiring ck users to fall back on emulating the missing operations with gcc/clang atomics or other means on that platform

I think 'feature parity on all supported platforms' would constitute a valuable goal for ck, as one could use it as a drop-in portability layer, and I would rate that goal higher than 'supporting only operations which perform better as builtins'.

I explicitly do not mind certain operations being less-than-optimal performers, for instance by falling back on cc-provided builtins.

Of course it remains sensible to exclude those operations a given platform just cannot support, like arm6 and 64bit atomics.

configure expects CC to be found in PATH

I was trying to build another project that included concurrencykit and need to set a path for my compiler. My compiler isn't in PATH. The configure command line for ck was something like:
CC=/really/long/path/to/my/gcc ./configure

With that ck uses /bin/gcc because $CC isn't found in my $PATH - see use of pathsearch in https://github.com/concurrencykit/ck/blob/master/configure#L563

My diff to get a working build is below. The idea for the diff is that if the user provided a value for CC then it can be used.

--- a/third_party/concurrency_kit/ck/configure
+++ b/third_party/concurrency_kit/ck/configure
@@ -560,11 +560,13 @@ else
GZIP_SUFFIX=".gz"
fi

-printf "Finding suitable compiler........"
+printf "Finding suitable compiler........ ${CC:-cc}"
+if test -z "$CC" ; then
CC=pathsearch "${CC:-cc}"
if test -z "$CC" -o ! -x "$CC"; then
CC=pathsearch "${CC:-gcc}"
fi
+fi
assert "$CC" "not found"

cat << EOF > .1.c

Ck fails to build from source if default gcc/ck_pr.h is used

gcc version 4.9.2 (Debian 4.9.2-16)
Target: x86_64-linux-gnu
ck: ck (0.4.4-1) Debian

Hello,

I am trying to build Debian package ck 0.4.4-1 on MIPS and MIPS64.
While trying to build this package I had problems with ck_epoch_synchronize test.
ck_epoch_synchronize test starts and never ends. It is running on all cores (100%) for hours.

Mips is not listed in include/ck_pr.h so for mips build gcc/ck_pr.h is used.

#if defined(__GNUC__)
#include "gcc/ck_pr.h"
#endif

I have changed define for x86_64 to test this issue on Intel:

diff -upNr ck-0.4.4-orig/include/ck_pr.h ck-0.4.4/include/ck_pr.h
--- ck-0.4.4-orig/include/ck_pr.h       2014-09-02 02:48:38.000000000 +0000
+++ ck-0.4.4/include/ck_pr.h    2015-05-06 11:31:44.606055785 +0000
@@ -35,7 +35,7 @@
 #include 

 #if defined(__x86_64__)
-#include "gcc/x86_64/ck_pr.h"
+#include "gcc/ck_pr.h"
 #elif defined(__x86__)
 #include "gcc/x86/ck_pr.h"
 #elif defined(__sparcv9__)

And when I use same gcc/ck_pr.h as for MIPS(64) package again run test for hours (22+), and does not end, on all cores on Intel i7 CPU.
(./ck_epoch_synchronize expr 8 / 2 expr 8 / 2 1)

Help or suggestions are welcomed.

Thanks!

Regards,
Jurica

libck.so name collision with the charm project

During building of multiple packages on Gentoo it was found that both concurrencykit and charm try to install libck.so in /usr/lib/libck.so. These are two completely different packages, but this means users cannot have them installed on a single machine in parallel.

Would it be possible to change the library name? For example concurrencykit should be unique :)

http://charm.cs.uiuc.edu/software

Unable to build on MSYS2

Hi,
I was attempting to build concurrencykit on msys2 and the configure script complained about being an "unsupprted" system. I was able to make the following change and get the whole thing to work.

diff --git a/configure b/configure
index dd78d76..d2ac714 100755

--- a/configure
+++ b/configure
@@ -351,6 +351,10 @@ case "$SYSTEM" in
                SYSTEM=mingw32
                LDFLAGS="-mthreads $LDFLAGS"
                ;;
+       MSYS_NT*)
+               SYSTEM=mingw32
+               LDFLAGS="-mthreads $LDFLAGS"
+               ;;
   CYGWIN_NT*)
     SYSTEM=cygwin
     LDFLAGS="-mthreads $LDFLAGS"

So it built cleanly on 32bit and 64bit variants of msys2. It would be really nice if this change is pulled in. Please let me know if you need anything more from me for this.

Regards,
Kashyap

Add sleepable version of epoch reclamation

This ticket will lay the ground-work for generic interfaces for sleepable versions of synchronization primitives. We will begin with the epoch reclamation use-case.

Samy: Prototype a user-space implementation to verify interface.
Hans: To investigate specialization of ck_epoch.
Paul: Paul it all up.

We'll converge after these steps and merge something in that's generic and addresses the requirements for FreeBSD.

Implement multilist

https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/multilist-2017.pdf

Add critical section fence

This has been around for a while, but the acquire fences are insufficient for RMO targets (and really dependent on fences in body of core logic of synchronization primitive). In addition to this, full fence is too strict. For this reason, we need to add a critical-section-specific primitive for proper ordering (isync is idiomatic for Power, though there is some interpretation in the architecture specification that allows lwsync in certain instances).

For common use-case, lwsync is fine but perhaps we consider exposing isync. Is it worth it? I will ping LKML folks and see what their thoughts are (in theory, isync should end up being more expensive than lwsync).

For reference (http://download.boulder.ibm.com/ibmdl/pub/software/dw/library/es-ppcbook2.zip):

If the shared data structure is in storage that is
neither Write Through Required nor Caching Inhibited,
an lwsync instruction can be used instead of the isync
instruction. If lwsync is used, the load from "data1"
may be performed before the stwcx.. But if the
stwcx. fails, the second branch is taken and the lwarx
is reexecuted. If the stwcx. succeeds, the value
returned by the load from "data1" is valid even if the
load is performed before the stwcx., because the
lwsync ensures that the load is performed after the
instance of the lwarx that created the reservation
used by the successful stwcx.

This interface is more relevant to ARM though since we can allow more re-ordering to occur.

Problems using CK_LIST

I'm trying to use concurrencykit in my project https://github.com/Secure-Labs/nextgen more specifically I'm trying to use CK_LIST but I can't find any documentation or examples other than the regression test that come with concurrencykit. I figured out how to use CK_LIST in a single process but when I try to use CK_LIST from shared memory between two processes the values in CK_LIST are garbage. This stackoverflow question shows examples: http://stackoverflow.com/questions/32361619/how-to-share-ck-list-across-processes .

reserved identifier violation

I would like to point out that identifiers like "_CK_FIFO_H" and "_CK_PR_H" do not fit to the expected naming convention of the C language standard.
Would you like to adjust your selection for unique names?

clang, i.MX6 quad: regressions/ck_fifo fails to compile

build passes

make regressions:

....
make -C ./ck_fifo/validate all
make[2]: Entering directory '/next/home/mah/src/ck-cubox-i/regressions/ck_fifo/validate'
/usr/bin/clang -D_XOPEN_SOURCE=600 -D_BSD_SOURCE -D_DEFAULT_SOURCE -std=gnu99 -pedantic -Wall -W -Wundef -Wendif-labels -Wshadow -Wpointer-arith -Wcast-align -Wcast-qual -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -Wnested-externs -Winline -Wdisabled-optimization -fstrict-aliasing -O2 -pipe -Wno-parentheses  -fPIC -I../../../include -DCORES=4 -D__arm__ -pthread -D_GNU_SOURCE -o ck_fifo_mpmc ck_fifo_mpmc.c
In file included from ck_fifo_mpmc.c:31:
In file included from ../../../include/ck_fifo.h:33:
In file included from ../../../include/ck_pr.h:48:
../../../include/gcc/arm/ck_pr.h:229:23: error: inline assembly requires more registers than available
        __asm__ __volatile__("1:"
                             ^
1 error generated.
Makefile:17: recipe for target 'ck_fifo_mpmc' failed

clang:

$ clang -v
Debian clang version 3.5.0-10 (tags/RELEASE_350/final) (based on LLVM 3.5.0)
Target: arm-unknown-linux-gnueabihf
Thread model: posix
Found candidate GCC installation: /usr/bin/../lib/gcc/arm-linux-gnueabihf/4.8
Found candidate GCC installation: /usr/bin/../lib/gcc/arm-linux-gnueabihf/4.8.4
Found candidate GCC installation: /usr/bin/../lib/gcc/arm-linux-gnueabihf/4.9
Found candidate GCC installation: /usr/bin/../lib/gcc/arm-linux-gnueabihf/4.9.2
Found candidate GCC installation: /usr/lib/gcc/arm-linux-gnueabihf/4.8
Found candidate GCC installation: /usr/lib/gcc/arm-linux-gnueabihf/4.8.4
Found candidate GCC installation: /usr/lib/gcc/arm-linux-gnueabihf/4.9
Found candidate GCC installation: /usr/lib/gcc/arm-linux-gnueabihf/4.9.2
Selected GCC installation: /usr/bin/../lib/gcc/arm-linux-gnueabihf/4.9
Candidate multilib: .;@m32
Selected multilib: .;@m32

platform:


$ uname -a
Linux cubox-i 3.14.14-cubox-i #6 SMP Fri Jun 5 20:43:50 CEST 2015 armv7l GNU/Linux

$ cat /proc/cpuo
cat: /proc/cpuo: No such file or directory
mah@cubox-i:/next/home/mah/src/ck-cubox-i$ cat /proc/cpuinfo
processor   : 0
model name  : ARMv7 Processor rev 10 (v7l)
Features    : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpd32
CPU implementer : 0x41
CPU architecture: 7
CPU variant : 0x2
CPU part    : 0xc09
CPU revision    : 10

processor   : 1
model name  : ARMv7 Processor rev 10 (v7l)
Features    : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpd32
CPU implementer : 0x41
CPU architecture: 7
CPU variant : 0x2
CPU part    : 0xc09
CPU revision    : 10

processor   : 2
model name  : ARMv7 Processor rev 10 (v7l)
Features    : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpd32
CPU implementer : 0x41
CPU architecture: 7
CPU variant : 0x2
CPU part    : 0xc09
CPU revision    : 10

processor   : 3
model name  : ARMv7 Processor rev 10 (v7l)
Features    : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpd32
CPU implementer : 0x41
CPU architecture: 7
CPU variant : 0x2
CPU part    : 0xc09
CPU revision    : 10

Hardware    : Freescale i.MX6 Quad/DualLite (Device Tree)
Revision    : 0000
Serial      : 0000000000000000

same thing on clang 3.5/ rpi2 - to be expected I guess

Make include guards unique

I find that include guards like "CK_HP_H" and "CK_PR_H" are too short for the safe reuse of your header files (when they belong to an application programming interface).

ck_hs / ck_ht single-threaded mode

Add a single-threaded mode that doesn't ever set defer flag to true on free / realloc callback.

Triple buffering primitive

Taking epoch reclamation principles, SPSC use-case can be made efficient. @pkhuong dumped the following, which is a good starting point for the facility. This is a "concept" below from Paul.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <ck_pr.h>

struct buffer_index {
    uint8_t byte;
};

/* We can obv. offset everything for 0 init, but let's keep things clear. */
#define BUFFER_INDEX_INIT = { 1 }

/* Not clear on the fencing; check ck_epoch... */
static inline size_t
buffer_index_read_index(const struct buffer_index *index)
{
    uint8_t byte = ck_pr_load_8(&index->byte);

    return byte >> 4;
}

static inline void
buffer_index_read_done(struct buffer_index *index)
{
    size_t next_read_index, read_index, write_index;
    uint8_t byte = ck_pr_load_8(&index->byte);

    read_index = byte >> 4;
    write_index = byte & 0xF;

    next_read_index = read_index + 1;
    if (next_read_index == 3) {
        next_read_index = 0;
    }

    if (next_read_index != write_index) {
        size_t prev_write_index = (write_index + 2) % 3;
        assert(prev_write_index == next_read_index);

        ck_pr_fence_load_store();
        ck_pr_store_8(&index->byte, (next_read_index << 4) | write_index);
    }

    return;
}

static inline size_t
buffer_index_write_index(const struct buffer_index *index)
{
    uint8_t byte = ck_pr_load_8(&index->byte);

    return byte & 0xF;
}

static inline size_t
buffer_index_write_start(struct buffer_index *index)
{
    size_t next_write_index, read_index, write_index;
    uint8_t byte = ck_pr_load_8(&index->byte);

    read_index = byte >> 4;
    write_index = byte & 0xF;

    next_write_index = write_index + 1;
    if (next_write_index == 3) {
        next_write_index = 0;
    }

    if (next_write_index == read_index) {
        return write_index;
    }

    assert(((read_index + 2) % 3) == next_write_index);
    ck_pr_store_8(&index->byte, (read_index << 4) | next_write_index);
    ck_pr_fence_store();
    return next_write_index;
}

Implement C11-style semantics

C++ syntax error when including ck_ring.h

g++ (GCC) 6.1.1 20160802 produces the following error:

In file included from /home/<redacted>/Repos/TickCaster/src/server/core.hpp:13:0,
                 from /home/<redacted>/Repos/TickCaster/src/server/core.cpp:1:
/usr/local/include/ck_ring.h:89:26: error: expected ‘,’ or ‘...’ before ‘buffer’
     void *CK_CC_RESTRICT buffer,
                          ^~~~~~
/usr/local/include/ck_ring.h: In function ‘bool _ck_ring_enqueue_sp(ck_ring*, void*)’:
/usr/local/include/ck_ring.h:100:6: error: ‘size’ was not declared in this scope
  if (size != NULL)
      ^~~~

clang c++ compilation unhappy

These casts are needed to appease the clang compiler in C++ mode:

diff --git a/0.5.1/src/ck-0.5.1/include/ck_stack.h b/0.5.1/src/ck-0.5.1/include/ck_stack.h
index eb2b685..6b86321 100644
--- a/0.5.1/src/ck-0.5.1/include/ck_stack.h
+++ b/0.5.1/src/ck-0.5.1/include/ck_stack.h
@@ -152,7 +152,7 @@ ck_stack_batch_pop_upmc(struct ck_stack *target)
 {
        struct ck_stack_entry *entry;

-       entry = ck_pr_fas_ptr(&target->head, NULL);
+       entry = (struct ck_stack_entry*)ck_pr_fas_ptr(&target->head, NULL);
        ck_pr_fence_load();
        return entry;
 }
@@ -276,7 +276,7 @@ ck_stack_push_mpnc(struct ck_stack *target, struct ck_stack_entry *entry)

        entry->next = NULL;
        ck_pr_fence_store_atomic();
-       stack = ck_pr_fas_ptr(&target->head, entry);
+       stack = (struct ck_stack_entry*)ck_pr_fas_ptr(&target->head, entry);
        ck_pr_store_ptr(&entry->next, stack);
        ck_pr_fence_store();

AArch64: missing clobbers in ck_pr_cas_64_2() and ck_pr_cas_64_2_value()

I'm looking at ck_pr_cas_64_2() and ck_pr_cas_64_2_value() implementations in include/gcc/aarch64/ck_pr.h. I think the embedded asm statements in those functions are missing "memory" and "cc" clobbers. Other CAS implementation in the same file have them. Also, implementations of the same functions for x86_64 have those clobbers.

For example, this is from include/gcc/aarch64/ck_pr.h:

CK_CC_INLINE static bool
ck_pr_cas_64_2(uint64_t target[2], uint64_t compare[2], uint64_t set[2])
{
	uint64_t tmp1, tmp2;
	__asm__ __volatile__("1:"
	   		     "ldxp %0, %1, [%2];"
			     "eor %0, %0, %3;"
			     "eor %1, %1, %4;"
			     "orr %1, %0, %1;"
			     "mov %w0, #0;"
			     "cbnz %1, 2f;"
			     "stxp %w0, %5, %6, [%2];"
			     "cbnz %w0, 1b;"
			     "mov %w0, #1;"
			     "2:"
			     : "=&r" (tmp1), "=&r" (tmp2) 
			     : "r" (target), "r" (compare[0]), "r" (compare[1]), "r" (set[0]), "r" (set[1]));

	return (tmp1);
}

And this is from include/gcc/x86_64/ck_pr.h:

CK_CC_INLINE static bool
ck_pr_cas_64_2(uint64_t target[2], uint64_t compare[2], uint64_t set[2])
{
	bool z;

	__asm__ __volatile__("movq 0(%4), %%rax;"
			     "movq 8(%4), %%rdx;"
			     CK_PR_LOCK_PREFIX "cmpxchg16b %0; setz %1"
				: "+m" (*target),
				  "=q" (z)
				: "b"  (set[0]),
				  "c"  (set[1]),
				  "q"  (compare)
				: "memory", "cc", "%rax", "%rdx");
	return z;
}

Shouldn't AArch64 implementations also clobber "memory" and "cc"?

Misbehavior when build in busybox environment

Versions:

ck master branch.
busybox 1.22.1/1.25.1

Steps to reproduce:

In a busybox environment, such as alpine linux, without GNU coreutils installed, run ./configure --prefix=/usr.

If you don't have such busybox environment, you can install busybox (apt install busybox on debians), and modify ./configure, line 172, change expr to busybox expr, and then run ./configure --prefix=/usr.

Actual result

expr: syntax error
...
Headers will be installed in /include
Libraries will be installed in /lib
Documentation will be installed in /share/man

It seems --prefix is misinterpreted as ""(empty) after a expr error.

Expected result

Headers/Libraries should be installed to /usr/include and /usr/lib, not /include and /lib.

The problem

It seems ./configure is incompatible with busybox's expr.

Suggestion

A simple workaround is installing GNU coreutils, but it would be nicer to make it compatible with busybox. At least, explicitly state that concurrencykit doesn't build in a busybox environment.

ck_ht replacement

To be called ck_hm, specification and discussion to come.

Add re-entrant / multi-writer versions of ck_epoch_begin / ck_epoch_end

This is something a few users have expressed interest in when using per-CPU structures or amortizing across a large number of threads.

ck_dec spinlock can acquire the already-acquired lock.

ck_dec spinlock can acquire the lock that is already acquired. You can reproduce the problem using the following code snippet, which is modified from ck/regressions/ck_spinlock/validate/validate.h. The underflow of lock->value at ck_spinlock_dec_lock_eb() is the root cause of the problem.

======= code to reproduce =======

LOCK_DEFINE;

int
main(int argc, char *argv[])
{
#ifdef LOCK_INIT
        LOCK_INIT;
#endif
#ifdef LOCK_STATE
        LOCK_STATE;
#endif
        printf("[1] try to acquite the lock\n");
        LOCK;
        printf("[2] the lock is acquired\n");

        printf("[3] try to acquite the lock\n");
        LOCK;
        printf("[4] the lock is acquired\n");
        return (0);
}

======= output =======

[1] try to acquite the lock
[2] the lock is acquired
[3] try to acquite the lock
[4] the lock is acquired

Fix aliasing violations in CAS2 operations

This has been around forever, and compilers will complain. Quick fix and localized. Problem code is below (which most CAS2 operations are built on).

CK_CC_INLINE static bool
ck_pr_cas_64_2(uint64_t target[2], uint64_t compare[2], uint64_t set[2])
{
        bool z;

        __asm__ __volatile__("movq 0(%4), %%rax;"
                             "movq 8(%4), %%rdx;"
                             CK_PR_LOCK_PREFIX "cmpxchg16b %0; setz %1"
                                : "+m" (*target),
                                  "=q" (z)
                                : "b"  (set[0]),
                                  "c"  (set[1]),
                                  "q"  (compare)
                                : "memory", "cc", "%rax", "%rdx");
        return z;
}

Other CAS2 variants affected.

ck_epoch documentation out of date

A number of the ck_epoch functions take an extra argument now. Discovering this at compile time rather than from the man pages is a bit disconcerting.

ck_backoff: add missing compiler barrier to busy loop body. (c.f. #23)

It's not clear if we want a ck_pr_stall or a plain barrier, but we want to prevent compilers from deleting the busy-wait loop as useless code.

make check on linux 64 bits fail to compile

/usr/bin/cc -DLATENCY -D_XOPEN_SOURCE=600 -D_BSD_SOURCE -std=gnu99 -pedantic -Wall -W -Wundef -Wendif-labels -Wshadow -Wpointer-arith -Wcast-align -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -Wnested-externs -Winline -Wdisabled-optimization -fstrict-aliasing -O2 -pipe -Wno-parentheses -fPIC -I../../../include -DCORES=2 -m64 -D__x86_64__ -pthread -D_GNU_SOURCE -lm -o ck_cohort.LATENCY ck_cohort.c
../../ck_spinlock/benchmark/../../common.h: Assembler messages:
../../ck_spinlock/benchmark/../../common.h:381: Error: invalid instruction suffix for push' ../../ck_spinlock/benchmark/../../common.h:388: Error: invalid instruction suffix forpop'
../../ck_spinlock/benchmark/../../common.h:381: Error: invalid instruction suffix for push' ../../ck_spinlock/benchmark/../../common.h:388: Error: invalid instruction suffix forpop'

used-before-initialized warnings in AArch64 implementation

I see the following warnings issued by the compiler (Ubuntu/Linaro 5.4.0-6ubuntu1~16.04.2) on a AArch64 machine:

/usr/bin/cc -D_XOPEN_SOURCE=600 -D_BSD_SOURCE -D_DEFAULT_SOURCE -std=gnu99 -pedantic -Wall -W -Wundef -Wendif-labels -Wshadow -Wpointer-arith -Wcast-align -Wcast-qual -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -Wnested-externs -Winline -Wdisabled-optimization -fstrict-aliasing -O2 -pipe -Wno-parentheses  -fPIC -I/home/ubuntu/src/git/ck/include -I/home/ubuntu/src/git/ck/include -c -o /home/ubuntu/src/git/ck/src/ck_epoch.o /home/ubuntu/src/git/ck/src/ck_epoch.c
In file included from /home/ubuntu/src/git/ck/include/ck_pr.h:51:0,
                 from /home/ubuntu/src/git/ck/include/ck_backoff.h:31,
                 from /home/ubuntu/src/git/ck/src/ck_epoch.c:33:
/home/ubuntu/src/git/ck/src/ck_epoch.c: In function ‘ck_pr_cas_ptr_value’:
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:244:3: warning: ‘previous’ is used uninitialized in this function [-Wuninitialized]
   __asm__ __volatile__("1:"    \
   ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:242:5: note: ‘previous’ was declared here
   T previous;      \
     ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:282:1: note: in expansion of macro ‘CK_PR_CAS’
 CK_PR_CAS(ptr, void, void *, "", "")
 ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:244:3: warning: ‘tmp’ is used uninitialized in this function [-Wuninitialized]
   __asm__ __volatile__("1:"    \
   ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:243:5: note: ‘tmp’ was declared here
   T tmp;       \
     ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:282:1: note: in expansion of macro ‘CK_PR_CAS’
 CK_PR_CAS(ptr, void, void *, "", "")
 ^
/home/ubuntu/src/git/ck/src/ck_epoch.c: In function ‘ck_pr_cas_uint_value’:
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:244:3: warning: ‘previous’ is used uninitialized in this function [-Wuninitialized]
   __asm__ __volatile__("1:"    \
   ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:242:5: note: ‘previous’ was declared here
   T previous;      \
     ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:284:33: note: in expansion of macro ‘CK_PR_CAS’
 #define CK_PR_CAS_S(N, M, W, R) CK_PR_CAS(N, M, M, W, R)
                                 ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:288:1: note: in expansion of macro ‘CK_PR_CAS_S’
 CK_PR_CAS_S(uint, unsigned int, "", "w")
 ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:244:3: warning: ‘tmp’ is used uninitialized in this function [-Wuninitialized]
   __asm__ __volatile__("1:"    \
   ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:243:5: note: ‘tmp’ was declared here
   T tmp;       \
     ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:284:33: note: in expansion of macro ‘CK_PR_CAS’
 #define CK_PR_CAS_S(N, M, W, R) CK_PR_CAS(N, M, M, W, R)
                                 ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:288:1: note: in expansion of macro ‘CK_PR_CAS_S’
 CK_PR_CAS_S(uint, unsigned int, "", "w")
 ^
/usr/bin/cc -D_XOPEN_SOURCE=600 -D_BSD_SOURCE -D_DEFAULT_SOURCE -std=gnu99 -pedantic -Wall -W -Wundef -Wendif-labels -Wshadow -Wpointer-arith -Wcast-align -Wcast-qual -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -Wnested-externs -Winline -Wdisabled-optimization -fstrict-aliasing -O2 -pipe -Wno-parentheses  -fPIC -I/home/ubuntu/src/git/ck/include -I/home/ubuntu/src/git/ck/include -c -o /home/ubuntu/src/git/ck/src/ck_ht.o /home/ubuntu/src/git/ck/src/ck_ht.c
/usr/bin/cc -D_XOPEN_SOURCE=600 -D_BSD_SOURCE -D_DEFAULT_SOURCE -std=gnu99 -pedantic -Wall -W -Wundef -Wendif-labels -Wshadow -Wpointer-arith -Wcast-align -Wcast-qual -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -Wnested-externs -Winline -Wdisabled-optimization -fstrict-aliasing -O2 -pipe -Wno-parentheses  -fPIC -I/home/ubuntu/src/git/ck/include -I/home/ubuntu/src/git/ck/include -c -o /home/ubuntu/src/git/ck/src/ck_hp.o /home/ubuntu/src/git/ck/src/ck_hp.c
In file included from /home/ubuntu/src/git/ck/include/ck_pr.h:51:0,
                 from /home/ubuntu/src/git/ck/include/ck_backoff.h:31,
                 from /home/ubuntu/src/git/ck/src/ck_hp.c:54:
/home/ubuntu/src/git/ck/src/ck_hp.c: In function ‘ck_pr_cas_ptr_value’:
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:244:3: warning: ‘previous’ is used uninitialized in this function [-Wuninitialized]
   __asm__ __volatile__("1:"    \
   ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:242:5: note: ‘previous’ was declared here
   T previous;      \
     ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:282:1: note: in expansion of macro ‘CK_PR_CAS’
 CK_PR_CAS(ptr, void, void *, "", "")
 ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:244:3: warning: ‘tmp’ is used uninitialized in this function [-Wuninitialized]
   __asm__ __volatile__("1:"    \
   ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:243:5: note: ‘tmp’ was declared here
   T tmp;       \
     ^
/home/ubuntu/src/git/ck/include/gcc/aarch64/ck_pr.h:282:1: note: in expansion of macro ‘CK_PR_CAS’
 CK_PR_CAS(ptr, void, void *, "", "")
 ^