c2ce635080
spinlock/ticket: Remove dead variable.
10 years ago
a5b4ca9ffc
ck_pr/ppc64: Use unsafe for ugly aliasing hack.
...
Once we migrate to using the wrappers, this ugliness won't be
necessary. Last argument can be macro-expanded instead.
10 years ago
e693cb9afe
ck_*lock: Migrate all locking primitives to lock / unlock.
...
This only affects RMO. This adds stricter semantics for critical section
serialization. In addition to this, asymmetric synchronization primitives will
now provide load ordering with respect to readers.
This also modifies locked operations to have acquire semantics
(they're there for elision predicates, and this doesn't impact them
in any way). There are several performance improvements included in this
as well (redundant fence was removed from days of wanting to support
Alpha).
10 years ago
1537c8091d
ck_pr: Introduce ck_pr_fence_lock and fence_unlock.
...
These primitives are meant to be used in lock implementations
where control dependency ordering is sufficient to enforce
ordering of critical section. At the moment, this only affects
PPC. Currently, we rely on lwsync for entry into critical sections
which is insufficient. sync is rather heavy-weight, and assuming
we aren't falling victim into compiler re-ordering, isync should
be sufficient.
There is follow-up work to be done in ARM, as we may have cheaper
(but target-specialized) ISB-tricks for load-load ordering.
10 years ago
787cffe9c9
ck_pr/arm: store_load requires DMB.
...
Emit full synchronize for store_load.
10 years ago
b2407aa3f0
whitespace/mcs: Wrap to 80 columns.
10 years ago
060ef37e5e
whitespace/ck_bitmap: Fix minor typo in comments.
...
Urban Dictionary reveals a particular interpretation of exclusing.
10 years ago
0e8d445049
ck_epoch: Specialize begin according to memory model.
...
Previously, we were specializing for x86.
10 years ago
a26c891f1a
ck_hp_fifo: Migrate to ck_hp_set_fence.
...
On Pentium M, this yields 30%-40% reduction in latency.
10 years ago
419ddca3ad
ck_hp_stack: Switch to ck_hp_set_fence.
10 years ago
9efb74da4b
ck_hp: Implement ck_hp_set_fence.
...
On TSO architectures, this relies on atomic ordering guarantees
rather than a full barrier. On Pentium M, this results in
approximately 30% improvement in latency for stack.
10 years ago
8b0bdb1901
ck_rhs: Introduce ck_rhs_set_load_factor() to change the load factor.
...
The default value is still 50, but that may be revisited later.
Also, pre-calculate the max number of entries before growing, toi avoid
having to do it at each insert.
10 years ago
e9d96eb9f6
ck_ring: make a few arguments const
10 years ago
477b37b249
gcc/ck_pr: I made up my mind, ck_pr_stale() has to provide a compiler barrier.
10 years ago
a30c54f64a
gcc/ck_pr: Revert previous commit
10 years ago
6dc4d2664f
gcc/ck_pr: ck_pr_stall() should act as a compiler barrier too.
10 years ago
63d6c00c3d
gcc/ck_pr: GCC-backed primitives should serve as compiler barriers.
...
Olivier pointed out that he was seeing some load / store operations
get optimized away and / or re-ordered otherwise.
10 years ago
8ee26212f9
ck_pr: Reference MD-implementation for CAS wrapper.
10 years ago
cb7620ed78
ck_pr: Re-order definitions for readability.
10 years ago
780a573fb2
ck_pr: Rename ck_pr_[load|store]_ptr to ck_pr_md_[load|store]_ptr in the
...
generic module, as was done in every MD version.
10 years ago
3729eedee9
ck_bytelock: Rely on TSO ordering to remove write-side barrier.
...
The cost is an atomic on read-side.
10 years ago
c217428f1b
whitespace/gcc: Missed some files during EOF sweep.
10 years ago
b8be614461
ck_cc: Add DECONST_PTR and RESTRICT.
...
DECONST_PTR is a hack to deconstify void pointer values
that is safe in presence of -Wcast-qual. CK_CC_RESTRICT
is restrict qualifier that can be disabled for only
partially C99 compliant compilers.
10 years ago
4ef225172e
Make ck_pr_store_* and ck_pr_load_* a bit more type safe.
...
We use some macro trickery to enforce that ck_pr_store_* is actually
storing the correct type into the target variable, without any actual
side effects--by making the assignment into an rvalue and using a
comma expression, the compiler should optimize it away.
On the load side, we simply cast the result to the type of the target
variable for pointer loads.
There is an unsafe version of the store_ptr macro called
ck_pr_store_ptr_unsafe for those times when you are _really_ sure that
you know what you're doing.
This commit also updates some of the source files (ck_ht, ck_hs,
ck_rhs): ck_ht now uses the unsafe macro, as its conversion between
uintptr_t and void * is invalid under the new macros. ck_hs and ck_rhs
have had some casts added to preserve validity.
10 years ago
421d4d1901
arm/ck_pr: Make sure 64bits load/store are atomic.
...
Depending on the CPU implementation, ldrd/strd may or may not be atomic.
Use ldrexd/strexd instead.
10 years ago
c1381a4e24
arm/ck_pr: add missing conversion to CK_ namespace
...
Commit 554e2f08
10 years ago
554e2f0874
whitespace: Strictly conform to C namespacing rules.
10 years ago
3c2c91daa4
spinlock/mcs: Migrate to acquire semantics on lock.
...
No functional impact on target architectures.
10 years ago
d99feda642
*clh: Migrate to acquire interface for lock.
...
No functional impact on existing targets.
10 years ago
0029650be1
Merge branch 'master' of https://github.com/concurrencykit/ck
10 years ago
851098b552
ck_fifo: Add fences to ABA-friendly operations.
10 years ago
f95c2c2413
ck_stack: Add fences for ABA-friendly push_mpmc.
10 years ago
6faceae8ad
ck_ht: Make deprecation official.
10 years ago
4214561c97
ck_pr: (Re-)introduce ck_pr_rfo.
...
This was accidentally grouped into previous commit.
The destiny of this interface for internal use is still unclear (in context of
utilization in built-in data structures). The interface is enabled by default
on x86, as it is compatible with read-side prefetch* operations and
binary-compatible with 3DNow! extension. Older compilers will waste an
additional byte (they generate 3DNow! variant) on this, but older compilers
waste more on spillage if we encode instruction. Power support is coming soon.
10 years ago
1474471445
ck_pr: Add basic ck_pr_rfo interface.
...
This leverages prefetchw that is now finally available on both AMD and Intel
processors. Additional ports coming.
10 years ago
dc8f36c96c
whitespace/spinlock: Remove extraneous end of file lines.
10 years ago
8b20998ecd
whitespace/ck_swlock: Fix typo in comment.
10 years ago
0dfd145aa6
whitespace: Update Copyright messages.
10 years ago
ae3a579216
ppc*: -Wcast-qual clean-up.
10 years ago
a6ac5b81fb
x86_64: Add const qualifier to load_ptr_2.
10 years ago
9d59c3d004
x86: -Wcast-qual clean-up.
10 years ago
4224f53159
ck_cc: -Wcast-qual clean-up.
10 years ago
7d70240449
general: First pass cast qualifier warning fixes.
10 years ago
508e92d2fc
ck_backoff: Remove usage of volatile.
...
This avoids memory traffic in busy-wait loops. Been on TODO list for a while,
may as well bite the bullet. No regressions introduced in recent versions of
GCC, clang and ICC.
10 years ago
0f7827f479
ck_pr: Prettify the arm bits.
...
gcc is smart enough to use an even register for 64bits operations, and provide
a way to access the first and the second words, so use that instead of
hardcoding registers.
10 years ago
3aa63b3912
ck_rhs: Implement ck_rhs_apply, similarly to what has been done in ck_hs.
10 years ago
e39223da44
ck_sequence: Constify read-only operations.
10 years ago
d6ba2a6273
whitespace: Sweeping whitespace changes.
...
Removing trailing whitespaces and newlines.
10 years ago
01aa93f05a
regressions/ck_hs: Additional ck_hs_apply coverage.
10 years ago
40c7a1f24c
ck_bitmap: Wrap long lines (style).
10 years ago
1d7057eb58
ck_bitmap: add a ck_bitmap_bts function.
...
Signed-off-by: Samy Al Bahra <sbahra@backtrace.io>
10 years ago
de0e582eba
Add ck_pr_fence_acquire/release to generic GCC version
...
Signed-off-by: Marcin Juszkiewicz <mjuszkiewicz@redhat.com>
10 years ago
b45f94a611
Merge branch 'master' of github.com:sbahra/ck
11 years ago
a514e81209
Fix typo in ck_rhs.h
...
This prevented use of both ck_hs and ck_rhs in the same file.
11 years ago
be11635b12
ck_bitmap: Consistent Copyright.
11 years ago
cd17fed7dc
ck_pflock: Migrate to acquire / release fences.
11 years ago
6b2f5130f7
ck_swlock: Whitespace changes.
11 years ago
11f79b64f7
ck_swlock: cleanup
11 years ago
d95c609090
Merge remote-tracking branch 'upstream/swlock' into ck_swlock
11 years ago
b70a5479ca
ck_swlock: snapshot
11 years ago
217f7a2f32
ck_swlock: Load spin on write bit.
11 years ago
4d7f4fff6d
ck_swlock: Fix latch operation.
11 years ago
bbad068f5a
ck_swlock: Make latch operation write-biased.
11 years ago
e2f7df0f1d
ck_swlock: Various improvements.
...
- Remove recursive locks.
- Remove unnecessary fences.
- Add necessary fences.
- Simplify state machine.
11 years ago
66aee95dd1
Merge branch 'ck_swlock' of github.com:skjaidev/ck into swlock
...
Conflicts:
regressions/Makefile
11 years ago
c246865ce7
ck_swlock: Removed comment
11 years ago
4471ea2df8
ck_swlock: Acquire semantics
11 years ago
e6feed1f89
ck_swlock: Rename lock field
11 years ago
0f44d50e33
ck_swlock: Use single word for lock bits
11 years ago
411afc3c47
*lock: Simplify initialization semantics.
...
Compiler barrier used for backwards compatibility.
11 years ago
f3539396c2
*lock: Simply use compiler barrier on initialization.
11 years ago
b24a9af88a
ck_pflock: Migrate initializer to use compiler barrier.
11 years ago
722f526a0e
ck_tflock: Remove extraneous newline.
11 years ago
46042c7996
tflock: Task-fair reader-writer locks reference implementation.
11 years ago
9ee4334e10
Merge remote-tracking branch 'upstream/master' into ck_swlock
...
Conflicts:
.gitignore
11 years ago
15a0485c01
ck_swlock: make ck_swlock_recursive_write_unlatch() wait-free.
11 years ago
ca70ce684c
ck_swlock: Unlatch operation should be wait-free.
11 years ago
27a79623a6
ck_swlock: Need to lock cache-line on write lock
11 years ago
0ee31c1557
ck_swlock: Need barrier
11 years ago
bf8779ab13
ck_swlock: Decrement n_readers in TATAS style loop.
11 years ago
8646990847
Merge remote-tracking branch 'jsridhar-dev/ck_swlock' into ck_swlock
...
Conflicts:
include/ck_swlock.h
regressions/ck_swlock/validate/validate.c
11 years ago
1f03809acb
ck_swlock: We shouldn't decrement n_readers when
...
ck_swlock_read_latchlocks observers a writer if the unlatch
operation sets n_readers to 0.
The unlatch operation now just unsets the latch bit, we can safely
decrement n_readers in ck_swlock_read_latchlocks().
+ Fixes to validation tests & ELIDE coverage.
11 years ago
f06a5c4a71
ck_bitmap: more bulk operations, less space, more tests
...
* new bulk rmw: intersection, intersection_negate (with complement),
* new bulk reads: empty, full, count, count_intersect
* ck_bitmap_iterator fixes: avoid out of bounds read on empty bitmaps,
and ck_bitmap_next is marginally faster on sparse bitmaps .
* less space: the bitmap itself is an array of unsigned int, which
eliminates alignment padding between the n_bit field and the bitmap.
* more unit tests.
11 years ago
96fdf1efbd
ck_cc: new bitwise ops
...
GCC and compatible compilers support ffs/ctz/clz/popcount. Expose that
in ck_cc and default to slow but portable software emulation.
11 years ago
bfc9837d4f
ck_swlock: Whitespace change.
11 years ago
63b79c7b1e
ck_swlock: Fix Copyright ordering.
11 years ago
6fe2bba224
ck_swlock: Fix-up TATAS loop.
11 years ago
a1daff18ea
ck_swlock: Switch to TATAS style loop for latch operations.
11 years ago
82f33b3fe9
ck_swlock: First round fixes for ck_swlock.
...
- Add necessary memory barriers.
- Style conformance.
11 years ago
9732e2bdb3
ck_swlock: A single writer rwlock.
...
This lock is copy-safe when the latch operations are used.
Simplified write side operations lead to lower latencies than ck_rwlock
for single writer workloads.
11 years ago
176dfce5c3
ck_rwlock: Fix conflict.
...
ck_swlock will be a copy-safe single-writer multi-reader lock that
will meet our requirements.
11 years ago
e2913ab9c0
Revert "ck_rwlock: Migrate to 32-bit primitives and add a write_latch operation."
...
This reverts commit 210b724061
11 years ago
6ccfb84d81
Revert "ck_rwlock: Use sub for unlatch operation."
...
This reverts commit b7c3c8a43d
11 years ago
ed476a617c
Revert "ck_rwlock: Clear reader bits on unlatch operation."
...
This reverts commit 7f945460bc
11 years ago
cdfac8213f
Revert "ck_rwlock: Re-observe latch bits if necessary."
...
This reverts commit fa28622386
11 years ago
88d323f40d
Revert "ck_rwlock: Acquire semantics for ordering on latch bits."
...
This reverts commit 2b567320de
11 years ago
9ebd19a124
Revert "ck_rwlock: Add ck_rwlock_read_latchlock operation."
...
This reverts commit bc7ebc62eb
11 years ago
cf097db790
Revert "ck_rwlock: Ignore latch bits on write lock operation."
...
This reverts commit 8173b937bf
11 years ago
e2bd885953
Revert "ck_rwlock: Re-organization of write-side operations and latch support for write_trylock."
...
This reverts commit ab22fda4e7
11 years ago
9aad0125af
Revert "ck_rwlock: Additional re-organization of write-side functions."
...
This reverts commit d9b86d2d89
11 years ago
d3a7adaf8c
Revert "ck_rwlock: Additional reorganization."
...
This reverts commit 56de32fffd
11 years ago
2a701163eb
ck_rwlock: Ditch ck_rwlock latch for ck_swlock.
11 years ago
56de32fffd
ck_rwlock: Additional reorganization.
11 years ago
d9b86d2d89
ck_rwlock: Additional re-organization of write-side functions.
11 years ago
ab22fda4e7
ck_rwlock: Re-organization of write-side operations and latch support for write_trylock.
11 years ago
8173b937bf
ck_rwlock: Ignore latch bits on write lock operation.
11 years ago
bc7ebc62eb
ck_rwlock: Add ck_rwlock_read_latchlock operation.
...
This avoids degradation on read_lock path for use-cases not
requiring latch semantics.
11 years ago
2b567320de
ck_rwlock: Acquire semantics for ordering on latch bits.
11 years ago
fa28622386
ck_rwlock: Re-observe latch bits if necessary.
11 years ago
7f945460bc
ck_rwlock: Clear reader bits on unlatch operation.
11 years ago
b7c3c8a43d
ck_rwlock: Use sub for unlatch operation.
11 years ago
3cae483bce
Merge branch 'master' of git.concurrencykit.org:ck
11 years ago
210b724061
ck_rwlock: Migrate to 32-bit primitives and add a write_latch operation.
...
write_latch allows writers to prevent incoming read acquisitions from
succeeding while permitting write_lock operations to complete. This is
useful if multiple writers are cooperating in linearizing a non-blocking
data structure and allows for lock state to be copied by the write lock
holder safely.
In collaboration with Paul Khuong and Jaidev Sridhar.
11 years ago
f8b41af77c
x86_64: Require 32-bit immediate values for expansion.
...
Pointed out by Paul Khuong, who ran into issues with immediates
while working on improvements to ck_bitmap.
11 years ago
cefd6bc9ec
ck_ring: Remove stale comment from pre-memcpy implementation.
11 years ago
396ceb16bb
ck_ring: Fix typo in type-specialized ck_ring_dequeue_tryspmc.
...
Thanks to Paul Khuong <pkhuong@appnexus> for patch.
11 years ago
6e0f79c70e
ck_tflock: Initial check-in of reference implementation.
11 years ago
671d067ea0
ck_bytelock: Fix casting error affecting 32-bit architectures.
11 years ago
81f267ce62
Merge branch 'master' of git.concurrencykit.org:ck
11 years ago
b97b0021f9
ck_barrier: Just pass-through tournament barrier with only one participating thread.
11 years ago
15ce0501d2
ck_sequence: Add branch hint for short-circuit.
11 years ago
cb8f5f9ebb
ck_hp_fifo: Add deinit routine to allow reclaiming stub node.
11 years ago
c75e470ed4
ck_fifo_spsc: De-initialize from head.
11 years ago
06feae82f3
ck_hp_fifo: No need for volatile atomic stores on initialization.
11 years ago
5ec8191ded
ck_fifo: Add ck_fifo_*_deinit routines.
...
These allow for reclamation of garbage node in an empty FIFO.
Based on patch submitted by Rajesh R <rr01803@gm....>.
11 years ago
15ac0bc691
ck_bitmap: Fix length calculation error in ck_bitmap_union (crasher).
11 years ago
08be876fa6
ck_bytelock: Correctly compute byte sequence length for readers.
...
Thanks to Albi Kavo <albi.kavo@gm...> for spotting this.
11 years ago
190b204059
ck_bitmap: Drop _mpmc suffix and add union operation.
...
The _mpmc suffix is not useful. I see little benefit to specializing
the bitmap to begin with.
11 years ago
76e43825a7
Merge remote-tracking branch 'origin/cognet'
11 years ago
b8c801136a
ck_bytelock: Fix deadlock for unslotted reader workloads.
...
There is an off-by-one for slot ID sizeof(bytelock->readers) + 1.
This patch fixes the handling of this slot ID. Based off a patch
submitted by Albi Kavo <albi.kavo@gma....>.
11 years ago
59cedf10c6
ck_rhs: Add a read mostly mode.
...
Add a read-mostly mode, in which entries won't share cache lines with
associated datas (probes, probe_bound, etc).
This makes write operations slower, but make get faster.
11 years ago
bf686c0a42
ck_rhs: Add.
...
Introduce ck_rhs, a variant of ck_hs that uses the robin hood algorithm for
insertion, and backward shift delete for deletion.
11 years ago
c197b37df1
legal: Update Copyright statements.
11 years ago
0c4ed1d14f
ck_pflock: Use store barrier on init.
11 years ago
0353cdcb23
ck_rwlock: Migrate to acquire / release and other barrier improvements.
11 years ago
38c40315a2
ck_brlock: Use store barrier on initialization.
11 years ago
ac8397d8b5
ck_rwcohort: Migrate to acquire / release.
11 years ago
5280253974
ck_pflock: Use precise barrier in read_unlock.
11 years ago
febdb8c164
ck_brlock: Use precise barrier for read_unlock.
11 years ago
0c205740aa
ck_pflock: Migrate to acquire / release.
11 years ago
ad5e00cfb9
ck_epoch: Read-side latency improvements on x86.
11 years ago
cad7b53273
ck_epoch: Migrate to acquire / release.
11 years ago
e8051b79c2
ck_elide: Add comment indicating purposeful omission of barriers.
11 years ago
16f7568e5c
ck_cohort: Migrate to acquire / release.
11 years ago
44689f7e69
ck_bytelock: Migrate to acquire / release.
11 years ago
f314b52035
ck_brlock: Migrate to acquire/release.
11 years ago
0bbb6f0eff
ck_pr: Fix typo in preprocessor usage.
11 years ago
e57bfd5865
spinlock: Migrate to acquire / release interface.
11 years ago
661f3948ed
ck_pr: Add acquire and release fences.
11 years ago
057f719796
ck_ring: Add type-specialized ring.
11 years ago
Samy Al Bahra
Samy Al Bahra
Olivier Houchard
William Light
John Wittrock
Emilio G. Cota
David Joseph
Marcin Juszkiewicz
Bruce Spang
Jaidev Sridhar
Samy Al Bahra
Jaidev Sridhar
Paul Khuong
User Doginou