http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_brlock ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_brlock b/lib/ck/doc/ck_brlock new file mode 100644 index 0000000..7972ee4 --- /dev/null +++ b/lib/ck/doc/ck_brlock @@ -0,0 +1,121 @@ +.\" +.\" Copyright 2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd July 26, 2013. +.Dt ck_brlock 3 +.Sh NAME +.Nm ck_brlock_init , +.Nm ck_brlock_write_lock , +.Nm ck_brlock_write_unlock , +.Nm ck_brlock_write_trylock , +.Nm ck_brlock_read_register , +.Nm ck_brlock_read_unregister , +.Nm ck_brlock_read_lock , +.Nm ck_brlock_read_trylock , +.Nm ck_brlock_read_unlock +.Nd big-reader locks +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_brlock.h +.Pp +.Dv ck_brlock_t brlock = CK_BRLOCK_INITIALIZER; +.Pp +.Dv ck_brlock_reader_t reader = CK_BRLOCK_READER_INITIALIZER; +.Pp +.Ft void +.Fn ck_brlock_init "ck_brlock_t *br" +.Ft void +.Fn ck_brlock_write_lock "ck_brlock_t *br" +.Ft void +.Fn ck_brlock_write_unlock "ck_brlock_t *br" +.Ft bool +.Fn ck_brlock_write_trylock "ck_brlock_t *br" "unsigned int factor" +.Ft void +.Fn ck_brlock_read_register "ck_brlock_t *br" "ck_brlock_reader_t *reader" +.Ft void +.Fn ck_brlock_read_unregister "ck_brlock_t *br" "ck_brlock_reader_t *reader" +.Ft void +.Fn ck_brlock_read_lock "ck_brlock_t *br" "ck_brlock_reader_t *reader" +.Ft bool +.Fn ck_brlock_read_trylock "ck_brlock_t *br" "ck_brlock_reader_t *reader" \ +"unsigned int factor" +.Ft void +.Fn ck_brlock_read_unlock "ck_brlock_reader_t *reader" +.Sh DESCRIPTION +Big reader locks are distributed reader-writer locks with low latency constant time +reader acquisition (with respect to number of concurrent readers). On the other +hand, writer acquisitions are a relatively expensive O(n) operation. This is a write-biased +lock. +.Sh EXAMPLE +.Bd -literal -offset indent +static ck_brlock_t lock = CK_BRLOCK_INITIALIZER; +static __thread ck_brlock_reader_t reader; + +static void +reader(void) +{ + + /* Add our thread as a lock participant. */ + ck_brlock_read_register(&lock, &reader); + + for (;;) { + ck_brlock_read_lock(&lock, &reader); + /* Read-side critical section. */ + ck_brlock_read_unlock(&reader); + + if (ck_brlock_read_trylock(&lock, &reader, 1) == true) { + /* Read-side critical section. */ + ck_brlock_read_unlock(&reader); + } + } + + return; +} + +static void +writer(void) +{ + + for (;;) { + ck_brlock_write_lock(&lock); + /* Write-side critical section. */ + ck_brlock_write_unlock(&lock); + + if (ck_brlock_write_trylock(&lock, 1) == true) { + /* Write-side critical section. */ + ck_brlock_write_unlock(&lock); + } + } + + return; +} +.Ed +.Sh SEE ALSO +.Xr ck_bytelock 3 , +.Xr ck_rwlock 3 +.Pp +Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_cohort ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_cohort b/lib/ck/doc/ck_cohort new file mode 100644 index 0000000..b033c91 --- /dev/null +++ b/lib/ck/doc/ck_cohort @@ -0,0 +1,211 @@ +.\" +.\" Copyright 2013 Brendon Scheinman. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd February 24, 2013. +.Dt ck_cohort 3 +.Sh NAME +.Nm ck_cohort +.Nd generalized interface for lock cohorts +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_cohort.h +.Fn CK_COHORT_PROTOTYPE "COHORT_NAME cohort_name" "LOCK_FXN global_lock_method" \ +"LOCK_FXN global_unlock_method" "LOCK_FXN local_lock_method" "LOCK_FXN local_unlock_method" +.Fn CK_COHORT_TRYLOCK_PROTOTYPE "COHORT_NAME cohort_name" \ +"LOCK_FXN global_lock_method" "LOCK_FXN global_unlock_method" \ +"BOOL_LOCK_FXN global_locked_method" "BOOL_LOCK_FXN global_trylock_method" \ +"LOCK_FXN local_lock_method" "LOCK_FXN local_unlock_method" \ +"BOOL_LOCK_FXN local_locked_method" "BOOL_LOCK_FXN local_trylock_method" +.Fn CK_COHORT_INSTANCE "COHORT_NAME cohort_name" +.Fn CK_COHORT_INIT "COHORT_NAME cohort_name" "ck_cohort *cohort" \ +"void *global_lock" "void *local_lock" "unsigned int pass_limit" +.Fn CK_COHORT_LOCK "COHORT_NAME cohort_name" "ck_cohort *cohort" \ +"void *global_context" "void *local_context" +.Fn CK_COHORT_UNLOCK "COHORT_NAME cohort_name" "ck_cohort *cohort" \ +"void *global_context" "void *local_context" +.Pp +Where LOCK_FXN refers to a method with the signature +.br +void(void *lock, void *context) +.br +BOOL_LOCK_FXN refers to a method with the signature +.br +bool(void *lock, void *context) +.Pp +The +.Fa context +argument in each signature is used to pass along any additional information that +the lock might need for its lock, unlock and trylock methods. The values for this +argument are provided to each call to +.Xr CK_COHORT_LOCK 3 , +.Xr CK_COHORT_UNLOCK 3 , +.Xr CK_COHORT_LOCKED 3 , +and +.Xr CK_COHORT_TRYLOCK 3 +. +.Sh DESCRIPTION +ck_cohort.h provides an interface for defining lock cohorts with +arbitrary lock types. Cohorts are a mechanism for coordinating +threads on NUMA architectures in order to reduce the frequency +with which a lock is passed between threads on different clusters. +.Pp +Before using a cohort, the user must define a cohort type using +either the +.Fn CK_COHORT_PROTOTYPE +or the +.Fn CK_COHORT_TRYLOCK_PROTOTYPE +macros. These macros allow the user to specify the lock methods that +they would like the cohort to use. See the +.Xr CK_COHORT_PROTOTYPE 3 +and +.Xr CK_COHORT_TRYLOCK_PROTOTYPE 3 +man pages for more details. +.Pp +.Sh EXAMPLE +.Bd -literal -offset indent +#include <stdlib.h> +#include <pthread.h> + +#include <ck_pr.h> +#include <ck_cohort.h> +#include <ck_spinlock.h> + +/* + * Create cohort methods with signatures that match + * the required signature + */ +static void +ck_spinlock_lock_with_context(ck_spinlock_t *lock, void *context) +{ + (void)context; + ck_spinlock_lock(lock); + return; +} + +static void +ck_spinlock_unlock_with_context(ck_spinlock_t *lock, void *context) +{ + (void)context; + ck_spinlock_unlock(lock); + return; +} + +static bool +ck_spinlock_locked_with_context(ck_spinlock_t *lock, void *context) +{ + (void)context; + return ck_spinlock_locked(lock); +} + +/* + * define a cohort type named "test_cohort" that will use + * the above methods for both its global and local locks + */ +CK_COHORT_PROTOTYPE(test_cohort, + ck_spinlock_lock_with_context, ck_spinlock_unlock_with_context, ck_spinlock_locked_with_context, + ck_spinlock_lock_with_context, ck_spinlock_unlock_with_context, ck_spinlock_locked_with_context) + +static ck_spinlock_t global_lock = CK_SPINLOCK_INITIALIZER; +static unsigned int ready; + +static void * +function(void *context) +{ + CK_COHORT_INSTANCE(test_cohort) *cohort = context; + + while (ready == 0); + + while (ready > 0) { + /* + * acquire the cohort lock before performing critical section. + * note that we pass NULL for both the global and local context + * arguments because neither the lock nor unlock functions + * will use them. + */ + CK_COHORT_LOCK(test_cohort, cohort, NULL, NULL); + + /* perform critical section */ + + /* relinquish cohort lock */ + CK_COHORT_UNLOCK(test_cohort, cohort, NULL, NULL); + } + + return NULL; +} + +int +main(void) +{ + unsigned int nthr = 4; + unsigned int n_cohorts = 2; + unsigned int i; + + /* allocate 2 cohorts of the defined type */ + CK_COHORT_INSTANCE(test_cohort) *cohorts = + calloc(n_cohorts, sizeof(CK_COHORT_INSTANCE(test_cohort))); + + /* create local locks to use with each cohort */ + ck_spinlock_t *local_locks = + calloc(n_cohorts, sizeof(ck_spinlock_t)); + + pthread_t *threads = + calloc(nthr, sizeof(pthread_t)); + + /* initialize each of the cohorts before using them */ + for (i = 0 ; i < n_cohorts ; ++i) { + CK_COHORT_INIT(test_cohort, cohorts + i, &global_lock, local_locks + i, + CK_COHORT_DEFAULT_LOCAL_PASS_LIMIT); + } + + /* start each thread and assign cohorts equally */ + for (i = 0 ; i < nthr ; ++i) { + pthread_create(threads + i, NULL, function, cohorts + (i % n_cohorts)); + } + + ck_pr_store_uint(&ready, 1); + sleep(10); + ck_pr_store_uint(&ready, 0); + + for (i = 0 ; i < nthr ; ++i) { + pthread_join(threads[i], NULL); + } + + return 0; +} +.Ed +.Sh SEE ALSO +.Xr CK_COHORT_PROTOTYPE 3 , +.Xr CK_COHORT_TRYLOCK_PROTOTYPE 3 , +.Xr CK_COHORT_INSTANCE 3 , +.Xr CK_COHORT_INITIALIZER 3 , +.Xr CK_COHORT_INIT 3 , +.Xr CK_COHORT_LOCK 3 , +.Xr CK_COHORT_UNLOCK 3 , +.Xr CK_COHORT_LOCKED 3 , +.Xr CK_COHORT_TRYLOCK 3 , +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_elide ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_elide b/lib/ck/doc/ck_elide new file mode 100644 index 0000000..3a63e74 --- /dev/null +++ b/lib/ck/doc/ck_elide @@ -0,0 +1,252 @@ +.\" +.\" Copyright 2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd July 13, 2013. +.Dt ck_elide 3 +.Sh NAME +.Nm CK_ELIDE_PROTOTYPE , +.Nm CK_ELIDE_LOCK_ADAPTIVE , +.Nm CK_ELIDE_UNLOCK_ADAPTIVE , +.Nm CK_ELIDE_LOCK , +.Nm CK_ELIDE_UNLOCK , +.Nm CK_ELIDE_TRYLOCK_PROTOTYPE , +.Nm CK_ELIDE_TRYLOCK +.Nd lock elision wrappers +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_elide.h +.Pp +.Dv ck_elide_stat_t stat = CK_ELIDE_STAT_INITIALIZER; +.Pp +.Ft void +.Fn ck_elide_stat_init "ck_elide_stat_t *" +.Pp +.Dv struct ck_elide_config config = CK_ELIDE_CONFIG_DEFAULT_INITIALIZER; +.Pp +.Bd -literal -offset +struct ck_elide_config { + unsigned short skip_busy; + short retry_busy; + unsigned short skip_other; + short retry_other; + unsigned short skip_conflict; + short retry_conflict; +}; +.Ed +.Pp +.Fn CK_ELIDE_PROTOTYPE "NAME" "TYPE" "LOCK_PREDICATE" "LOCK_FUNCTION" "UNLOCK_PREDICATE" "UNLOCK_FUNCTION" +.Fn CK_ELIDE_LOCK_ADAPTIVE "NAME" "ck_elide_stat_t *" "struct ck_elide_config *" "TYPE *" +.Fn CK_ELIDE_UNLOCK_ADAPTIVE "NAME" "ck_elide_stat_t *" "TYPE *" +.Fn CK_ELIDE_LOCK "NAME" "TYPE *" +.Fn CK_ELIDE_UNLOCK "NAME" "TYPE *" +.Fn CK_ELIDE_TRYLOCK_PROTOTYPE "NAME" "TYPE" "LOCK_PREDICATE" "TRYLOCK_FUNCTION" +.Sh DESCRIPTION +These macros implement lock elision wrappers for a user-specified single-argument +lock interface. The wrappers will attempt to elide lock acquisition, allowing +concurrent execution of critical sections that do not issue conflicting memory +operations. If any threads have successfully elided a lock acquisition, +conflicting memory operations will roll-back any side-effects of the critical +section and force every thread to retry the lock acquisition regularly. +.Pp +.Fn CK_ELIDE_LOCK , +.Fn CK_ELIDE_UNLOCK , +.Fn CK_ELIDE_LOCK_ADAPTIVE , +and +.Fn CK_ELIDE_UNLOCK_ADAPTIVE +macros require +a previous +.Fn CK_ELIDE_PROTOTYPE +with the same +.Fa NAME . +Elision is attempted if the +.Fa LOCK_PREDICATE +function returns false. If +.Fa LOCK_PREDICATE +returns true then elision is aborted and +.Fa LOCK_FUNCTION +is executed instead. If any threads are in an elided critical section, +.Fa LOCK_FUNCTION +must force them to rollback through a conflicting memory operation. +The +.Fa UNLOCK_PREDICATE +function must return true if the lock is acquired by the caller, meaning +that the lock was not successfully elided. If +.Fa UNLOCK_PREDICATE +returns true, then the +.Fa UNLOCK_FUNCTION +is executed. If RTM is unsupported (no CK_F_PR_RTM macro) then +.Fn CK_ELIDE_LOCK +and +.Fn CK_ELIDE_LOCK_ADAPTIVE +will immediately call +.Fn LOCK_FUNCTION . +.Fn CK_ELIDE_UNLOCK +and +.Fn CK_ELIDE_UNLOCK_ADAPTIVE +will immediately call +.Fn UNLOCK_FUNCTION . +.Pp +.Fn CK_ELIDE_TRYLOCK +requires a previous +.Fn CK_ELIDE_TRYLOCK_PROTOTYPE +with the same name. +Elision is attempted if the +.Fa LOCK_PREDICATE +function returns false. If +.Fa LOCK_PREDICATE +returns true or if elision fails then the +operation is aborted. If RTM is unsupported +(no CK_F_PR_RTM macro) then +.Fn CK_ELIDE_TRYLOCK +will immediately call +.Fn TRYLOCK_FUNCTION . +.Pp +.Fn CK_ELIDE_LOCK_ADAPTIVE +and +.Fn CK_ELIDE_UNLOCK_ADAPTIVE +will adapt the elision behavior associated with lock operations +according to the run-time behavior of the program. This behavior +is defined by the ck_elide_config structure pointer passed to +.Fn CK_ELIDE_LOCK_ADAPTIVE . +A thread-local ck_elide_stat structure must be passed to both +.Fn CK_ELIDE_LOCK_ADAPTIVE +and +.Fn CK_ELIDE_UNLOCK_ADAPTIVE . +This structure is expected to be unique for different workloads, +may not be re-used in recursive acquisitions and must match the +lifetime of the lock it is associated with. It is safe to mix +adaptive calls with best-effort calls. +.Pp +Both ck_spinlock.h and ck_rwlock.h define ck_elide wrappers under +the ck_spinlock and ck_rwlock namespace, respectively. +.Sh EXAMPLES +This example utilizes built-in lock elision facilities in ck_rwlock and ck_spinlock. +.Bd -literal -offset indent +#include <ck_rwlock.h> +#include <ck_spinlock.h> + +static ck_rwlock_t rw = CK_RWLOCK_INITIALIZER; +static struct ck_elide_config rw_config = + CK_ELIDE_CONFIG_DEFAULT_INITIALIZER; +static __thread ck_elide_stat_t rw_stat = + CK_ELIDE_STAT_INITIALIZER; + +static ck_spinlock_t spinlock = CK_SPINLOCK_INITIALIZER; +static struct ck_elide_config spinlock_config = + CK_ELIDE_CONFIG_DEFAULT_INITIALIZER; +static __thread ck_elide_stat_t spinlock_stat = + CK_ELIDE_STAT_INITIALIZER; + +void +function(void) +{ + + /* Lock-unlock write-side lock in weak best-effort manner. */ + CK_ELIDE_LOCK(ck_rwlock_write, &rw); + CK_ELIDE_UNLOCK(ck_rwlock_write, &rw); + + /* Attempt to acquire the write-side lock. */ + if (CK_ELIDE_TRYLOCK(ck_rwlock_write, &rw) == true) + CK_ELIDE_UNLOCK(ck_rwlock_write, &rw); + + /* Lock-unlock read-side lock in weak best-effort manner. */ + CK_ELIDE_LOCK(ck_rwlock_read, &rw); + CK_ELIDE_UNLOCK(ck_rwlock_read, &rw); + + /* Attempt to acquire the read-side lock. */ + if (CK_ELIDE_TRYLOCK(ck_rwlock_read, &rw) == true) + CK_ELIDE_UNLOCK(ck_rwlock_read, &rw); + + /* Lock-unlock write-side lock in an adaptive manner. */ + CK_ELIDE_LOCK_ADAPTIVE(ck_rwlock_write, &rw_stat, + &rw_config, &rw); + CK_ELIDE_UNLOCK_ADAPTIVE(ck_rwlock_write, &rw_stat, + &rw_config, &rw); + + /* Lock-unlock read-side lock in an adaptive manner. */ + CK_ELIDE_LOCK_ADAPTIVE(ck_rwlock_read, &rw_stat, + &rw_config, &rw); + CK_ELIDE_UNLOCK_ADAPTIVE(ck_rwlock_read, &rw_stat, + &rw_config, &rw); + + /* Lock-unlock spinlock in weak best-effort manner. */ + CK_ELIDE_LOCK(ck_spinlock, &spinlock); + CK_ELIDE_UNLOCK(ck_spinlock, &spinlock); + + /* Attempt to acquire the lock. */ + if (CK_ELIDE_TRYLOCK(ck_spinlock, &lock) == true) + CK_ELIDE_UNLOCK(ck_spinlock, &spinlock); + + /* Lock-unlock spinlock in an adaptive manner. */ + CK_ELIDE_LOCK_ADAPTIVE(ck_spinlock, &spinlock_stat, + &spinlock_config, &spinlock); + CK_ELIDE_UNLOCK_ADAPTIVE(ck_spinlock, &spinlock_stat, + &spinlock_config, &spinlock); +} +.Ed +.Pp +In this example, user-defined locking functions are provided an elision +implementation. +.Bd -literal -offset indent +/* Assume lock_t has been previously defined. */ +#include <ck_elide.h> + +/* + * This function returns true if the lock is unavailable at the time + * it was called or false if the lock is available. + */ +bool is_locked(lock_t *); + +/* + * This function acquires the supplied lock. + */ +void lock(lock_t *); + +/* + * This function releases the lock. + */ +void unlock(lock_t *); + +CK_ELIDE_PROTOTYPE(my_lock, lock_t, is_locked, lock, is_locked, unlock) + +static lock_t lock; + +void +function(void) +{ + + CK_ELIDE_LOCK(my_lock, &lock); + CK_ELIDE_UNLOCK(my_lock, &lock); +} +.Ed +.Sh SEE ALSO +.Xr ck_rwlock 3 , +.Xr ck_spinlock 3 +.Pp +Ravi Rajwar and James R. Goodman. 2001. Speculative lock elision: enabling highly concurrent multithreaded execution. In Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture (MICRO 34). IEEE Computer Society, Washington, DC, USA, 294-305. +.Pp +Additional information available at http://en.wikipedia.org/wiki/Transactional_Synchronization_Extensions and http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_barrier ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_barrier b/lib/ck/doc/ck_epoch_barrier new file mode 100644 index 0000000..80cc70e --- /dev/null +++ b/lib/ck/doc/ck_epoch_barrier @@ -0,0 +1,120 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_BARRIER 3 +.Sh NAME +.Nm ck_epoch_barrier +.Nd block until a grace period and all callbacks have been dispatched +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft void +.Fn ck_epoch_barrier "ck_epoch_t *epoch" "ck_epoch_record_t *record" +.Sh DESCRIPTION +The +.Fn ck_epoch_barrier 3 +function will block the caller until a grace period has been +detected, according to the semantics of epoch reclamation. +Any objects requiring safe memory reclamation which are logically +deleted are safe for physical deletion following a call to +.Fn ck_epoch_barrier 3 . This function will also dispatch all callbacks +associated with +.Fa epoch +that were previously scheduled via +.Fn ck_epoch_call 3 . +.Sh EXAMPLE +.Bd -literal -offset indent + +#include <ck_epoch.h> +#include <ck_stack.h> +#include <stdlib.h> + +/* + * epoch was previously initialized with ck_epoch_init. + * stack was previously initialized with ck_stack_init. + */ +ck_epoch_t *epoch; +ck_stack_t *stack; + +void +function(void) +{ + ck_epoch_record_t *record; + ck_stack_entry_t *s; + + record = malloc(sizeof *record); + ck_epoch_register(&epoch, record); + + /* + * We are using an epoch section here to guarantee no + * nodes in the stack are deleted while we are dereferencing + * them. This is needed here because there are multiple writers. + * If there was only one thread popping from the this stack, + * then there is no need to ck_epoch_begin/ck_epoch_end. + */ + ck_epoch_begin(epoch, record); + + /* Logically delete an object. */ + s = ck_stack_pop_upmc(stack); + + ck_epoch_end(epoch, record); + + /* + * Wait until no threads could possibly have a reference to the + * object we just popped (assume all threads are simply executing + * ck_stack_pop_upmc). + */ + ck_epoch_barrier(epoch, record); + + /* It is now safe to physically delete the object. */ + free(s); + return; +} +.Ed +.Sh RETURN VALUES +This function has no return value. +.Sh ERRORS +Behavior is undefined if the object pointed to by +.Fa epoch +is not a valid epoch object. The object pointed to by +.Fa record +must have been previously registered via +.Fn ck_epoch_register 3 . +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_register 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_synchronize 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_begin 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_begin ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_begin b/lib/ck/doc/ck_epoch_begin new file mode 100644 index 0000000..6a71860 --- /dev/null +++ b/lib/ck/doc/ck_epoch_begin @@ -0,0 +1,71 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_BEGIN 3 +.Sh NAME +.Nm ck_epoch_begin +.Nd begin epoch-protected segment of execution +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft void +.Fn ck_epoch_begin "ck_epoch_t *epoch" "ck_epoch_record_t *record" +.Sh DESCRIPTION +The +.Fn ck_epoch_begin 3 +function will mark the beginning of an epoch-protected code section. +An epoch-protected code section is delimited by a call to the +.Fn ck_epoch_end 3 +function. Though recursion is allowed for epoch-protected sections, +recursive calls will be associated with the +.Fn ck_epoch_begin 3 +that is at the top of the call stack. +.Sh RETURN VALUES +This function has no return value. +.Sh ERRORS +The object pointed to by +.Fa epoch +must have been previously initiated via +.Fn ck_epoch_init 3 . +The object pointed to by +.Fa record +must have been previously registered via +.Fn ck_epoch_register 3 . +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_register 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_synchronize 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_call ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_call b/lib/ck/doc/ck_epoch_call new file mode 100644 index 0000000..4f6286e --- /dev/null +++ b/lib/ck/doc/ck_epoch_call @@ -0,0 +1,136 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_CALL 3 +.Sh NAME +.Nm ck_epoch_call +.Nd defer function execution until a grace period +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +typedef struct ck_epoch_entry ck_epoch_entry_t; +.br +typedef void ck_epoch_cb_t(ck_epoch_entry_t *); +.Ft void +.Fn ck_epoch_call "ck_epoch_t *epoch" "ck_epoch_record_t *record" "ck_epoch_entry_t *entry" "ck_epoch_cb_t *function" +.Sh DESCRIPTION +The +.Fn ck_epoch_call 3 +function will defer the execution of the function pointed to by +.Fa function +until a grace-period has been detected in +.Fa epoch . +The function will be provided +the pointer specified by +.Fa entry . +The function will execute at some time in the future via calls to +.Fn ck_epoch_reclaim 3 , +.Fn ck_epoch_barrier 3 +or +.Fn ck_epoch_poll 3 . +.Sh EXAMPLE +.Bd -literal -offset indent + +#include <ck_epoch.h> +#include <ck_stack.h> +#include <stdlib.h> + +/* + * epoch was previously initialized with ck_epoch_init. + */ +ck_epoch_t *epoch; + +struct object { + int value; + ck_epoch_entry_t epoch_entry; +}; +static struct object *global; + +CK_EPOCH_CONTAINER(struct object, epoch_entry, object_container) + +void +destroy_object(ck_epoch_entry_t *e) +{ + struct object *o = object_container(e); + + free(o); + return; +} + +void +function(void) +{ + ck_epoch_record_t *record; + struct object *n; + + record = malloc(sizeof *record); + ck_epoch_register(&epoch, record); + + n = malloc(sizeof *n); + if (n == NULL) + return; + + n->value = 1; + + /* + * We are using an epoch section here because there are multiple + * writers. It is also an option to use other forms of blocking + * write-side synchronization such as mutexes. + */ + ck_epoch_begin(epoch, record); + n = ck_pr_fas_ptr(&global, n); + ck_epoch_end(epoch, record); + + /* Defer destruction of previous object. */ + ck_epoch_call(record, &n->epoch_entry, destroy_object); + + /* Poll epoch sub-system in non-blocking manner. */ + ck_epoch_poll(&epoch, record); + return; +} +.Ed +.Sh RETURN VALUES +This function has no return value. +.Sh ERRORS +The object pointed to by +.Fa record +must have been previously registered via +.Fn ck_epoch_register 3 . +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_register 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_synchronize 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_begin 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_end ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_end b/lib/ck/doc/ck_epoch_end new file mode 100644 index 0000000..eea2dad --- /dev/null +++ b/lib/ck/doc/ck_epoch_end @@ -0,0 +1,65 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_END 3 +.Sh NAME +.Nm ck_epoch_end +.Nd end epoch-protected segment of execution +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft void +.Fn ck_epoch_end "ck_epoch_t *epoch" "ck_epoch_record_t *record" +.Sh DESCRIPTION +The +.Fn ck_epoch_end 3 +function will mark the end of an epoch-protected code section. +.Sh RETURN VALUES +This function has no return value. +.Sh ERRORS +The object pointed to by +.Fa epoch +must have been previously initiated via +.Fn ck_epoch_init 3 . +The object pointed to by +.Fa record +must have been previously registered via +.Fn ck_epoch_register 3 . +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_register 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_synchronize 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_begin 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_init ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_init b/lib/ck/doc/ck_epoch_init new file mode 100644 index 0000000..e22294d --- /dev/null +++ b/lib/ck/doc/ck_epoch_init @@ -0,0 +1,69 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_INIT 3 +.Sh NAME +.Nm ck_epoch_init +.Nd initialize epoch reclamation object +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft void +.Fn ck_epoch_init "ck_epoch_t *epoch" +.Sh DESCRIPTION +The +.Fn ck_epoch_init +function initializes the epoch object pointed to by the +.Fa epoch +pointer. +.Sh RETURN VALUES +This function has no return value. +.Sh ERRORS +.Bl -tag -width Er +.Pp +The behavior of +.Fn ck_epoch_init +is undefined if +.Fa epoch +is not a pointer to a +.Tn ck_epoch_t +object. +.El +.Sh SEE ALSO +.Xr ck_epoch_register 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_synchronize 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_begin 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_poll ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_poll b/lib/ck/doc/ck_epoch_poll new file mode 100644 index 0000000..b80c42e --- /dev/null +++ b/lib/ck/doc/ck_epoch_poll @@ -0,0 +1,73 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_POLL 3 +.Sh NAME +.Nm ck_epoch_poll +.Nd non-blocking poll of epoch object for dispatch cycles +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft bool +.Fn ck_epoch_poll "ck_epoch_t *epoch" "ck_epoch_record_t *record" +.Sh DESCRIPTION +The +.Fn ck_epoch_poll 3 +function will attempt to dispatch any functions associated with the +object pointed to by +.Fa epoch +via +.Fn ck_epoch_call 3 +if deemed safe. This function is meant to be used in cases epoch +reclamation cost must be amortized over time in a manner that does +not affect caller progress. +.Sh RETURN VALUES +This function will return true if at least one function was dispatched. +This function will return false if it has determined not all threads have +observed the latest generation of epoch-protected objects. Neither value +indicates an error. +.Sh ERRORS +Behavior is undefined if the object pointed to by +.Fa epoch +is not a valid epoch object. The object pointed to by +.Fa record +must have been previously registered via +.Fn ck_epoch_register 3 . +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_register 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_synchronize 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_begin 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_reclaim ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_reclaim b/lib/ck/doc/ck_epoch_reclaim new file mode 100644 index 0000000..ffe3bac --- /dev/null +++ b/lib/ck/doc/ck_epoch_reclaim @@ -0,0 +1,92 @@ +.\" +.\" Copyright 2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd May 2, 2013 +.Dt CK_EPOCH_RECLAIM 3 +.Sh NAME +.Nm ck_epoch_reclaim +.Nd immediately execute all deferred callbacks +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft void +.Fn ck_epoch_reclaim "ck_epoch_record_t *record" +.Sh DESCRIPTION +The +.Fn ck_epoch_reclaim 3 +function will unconditionally execute all callbacks +that have been deferred with +.Fn ck_epoch_call 3 . +.Sh EXAMPLE +.Bd -literal -offset indent + +#include <ck_epoch.h> +#include <ck_stack.h> +#include <stdlib.h> + +/* + * epoch was previously initialized with ck_epoch_init. + */ +ck_epoch_t *epoch; + +void +function(void) +{ + ck_epoch_record_t *record; + + logically_delete(object); + ck_epoch_call(epoch, record, &object->epoch_entry, destructor); + + /* + * Wait until no threads could possibly have a reference to the + * object we just deleted. + */ + ck_epoch_synchronize(epoch, record); + + /* + * Execute all deferred callbacks. + */ + ck_epoch_reclaim(record); + + return; +} +.Ed +.Sh RETURN VALUES +This function has no return value. +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_register 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_begin 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_recycle ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_recycle b/lib/ck/doc/ck_epoch_recycle new file mode 100644 index 0000000..530079c --- /dev/null +++ b/lib/ck/doc/ck_epoch_recycle @@ -0,0 +1,102 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_RECYCLE 3 +.Sh NAME +.Nm ck_epoch_recycle +.Nd return an epoch record that may be used by caller +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft ck_epoch_record_t * +.Fn ck_epoch_recycle "ck_epoch_t *epoch" +.Sh DESCRIPTION +The +.Fn ck_epoch_recycle 3 +function attempts to return an unused epoch record object for use by +the caller. These epoch records were associated with previous calls +to the +.Fn ck_epoch_unregister 3 +function. +.Sh EXAMPLE +.Bd -literal -offset indent +#include <ck_epoch.h> +#include <stdlib.h> + +/* + * epoch was previously initialized with ck_epoch_init. + */ +ck_epoch_t *epoch; + +void +function(void) +{ + ck_epoch_record_t *record; + + record = ck_epoch_recycle(&epoch); + if (record == NULL) { + record = malloc(sizeof *record); + if (record == NULL) + return; + + ck_epoch_register(&epoch, record); + } + + /* + * After we are done, we will unregister the record so it + * can be used by other new participants in the epoch system + * provided by the object pointed to by "epoch". + */ + ck_epoch_unregister(&epoch, record); + return; +} +.Ed +.Sh RETURN VALUES +This function returns a pointer to a +.Dv ck_epoch_record_t +object. If no unused record was found to be associated with the +object pointed to by +.Fa epoch , +then the function will return NULL. +.Sh ERRORS +Behavior is undefined if the object pointed to by +.Fa epoch +is not a valid epoch object. +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_register 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_synchronize 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_begin 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_register ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_register b/lib/ck/doc/ck_epoch_register new file mode 100644 index 0000000..85ea461 --- /dev/null +++ b/lib/ck/doc/ck_epoch_register @@ -0,0 +1,67 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_REGISTER 3 +.Sh NAME +.Nm ck_epoch_register +.Nd register a thread for epoch reclamation +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft void +.Fn ck_epoch_register "ck_epoch_t *epoch" "ck_epoch_record_t *record" +.Sh DESCRIPTION +The +.Fn ck_epoch_register 3 +function associates a record object specified by the +.Fa record +pointer with the epoch object pointed to by +.Fa epoch . +Any thread or processor that will require safe memory reclamation +guarantees must register a unique record object. After registration, the +object pointed to by the +.Fa record +argument will have lifetime managed by the underlying epoch sub-system. +The record object must not be destroyed after it is associated with a +.Fn ck_epoch_register 3 +call. +.Sh RETURN VALUES +This function has no return value. +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_synchronize 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_begin 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_synchronize ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_synchronize b/lib/ck/doc/ck_epoch_synchronize new file mode 100644 index 0000000..33df67c --- /dev/null +++ b/lib/ck/doc/ck_epoch_synchronize @@ -0,0 +1,123 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_SYNCHRONIZE 3 +.Sh NAME +.Nm ck_epoch_synchronize +.Nd block until a grace period has been detected +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft void +.Fn ck_epoch_synchronize "ck_epoch_t *epoch" "ck_epoch_record_t *record" +.Sh DESCRIPTION +The +.Fn ck_epoch_synchronize 3 +function will block the caller until a grace period has been +detected, according to the semantics of epoch reclamation. +Any objects requiring safe memory reclamation which are logically +deleted are safe for physical deletion following a call to +.Fn ck_epoch_synchronize 3 . +If you require that all callbacks be dispatched, then it is suggested +that you use +.Fn ck_epoch_barrier 3 +instead or follow a call of +.Fn ck_epoch_synchronize 3 +with +.Fn ck_epoch_reclaim 3 . +.Sh EXAMPLE +.Bd -literal -offset indent + +#include <ck_epoch.h> +#include <ck_stack.h> +#include <stdlib.h> + +/* + * epoch was previously initialized with ck_epoch_init. + * stack was previously initialized with ck_stack_init. + */ +ck_epoch_t *epoch; +ck_stack_t *stack; + +void +function(void) +{ + ck_epoch_record_t *record; + ck_stack_entry_t *s; + + record = malloc(sizeof *record); + ck_epoch_register(&epoch, record); + + /* + * We are using an epoch section here to guarantee no + * nodes in the stack are deleted while we are dereferencing + * them. This is needed here because there are multiple writers. + * If there was only one thread popping from the this stack, + * then there is no need to ck_epoch_begin/ck_epoch_end. + */ + ck_epoch_begin(epoch, record); + + /* Logically delete an object. */ + s = ck_stack_pop_upmc(stack); + + ck_epoch_end(epoch, record); + + /* + * Wait until no threads could possibly have a reference to the + * object we just popped (assume all threads are simply executing + * ck_stack_pop_upmc). + */ + ck_epoch_synchronize(epoch, record); + + /* It is now safe to physically delete the object. */ + free(s); + return; +} +.Ed +.Sh RETURN VALUES +This function has no return value. +.Sh ERRORS +Behavior is undefined if the object pointed to by +.Fa epoch +is not a valid epoch object. The object pointed to by +.Fa record +must have been previously registered via +.Fn ck_epoch_register 3 . +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_register 3 , +.Xr ck_epoch_unregister 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_begin 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_epoch_unregister ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_epoch_unregister b/lib/ck/doc/ck_epoch_unregister new file mode 100644 index 0000000..9f297ee --- /dev/null +++ b/lib/ck/doc/ck_epoch_unregister @@ -0,0 +1,73 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 2, 2012 +.Dt CK_EPOCH_UNREGISTER 3 +.Sh NAME +.Nm ck_epoch_unregister +.Nd unregister a thread for epoch reclamation +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_epoch.h +.Ft void +.Fn ck_epoch_unregister "ck_epoch_t *epoch" "ck_epoch_record_t *record" +.Sh DESCRIPTION +The +.Fn ck_epoch_unregister 3 +function allows for the record pointed by the +.Fa record +pointer to be used as a return value by the +.Fn ck_epoch_recycle 3 +function. This record can now be used by another thread +of execution. Behavior is undefined if the object pointed by +.Fa record +is modified in any way, even after a call is made to the +.Fn ck_epoch_unregister 3 +function. +.Sh RETURN VALUES +This function has no return value. +.Sh ERRORS +Behavior is undefined if the object pointed to by +.Fa record +was not previously associated with the object pointed to by +.Fa epoch +through a previous call to the +.Fn ck_epoch_register 3 +function. +.Sh SEE ALSO +.Xr ck_epoch_init 3 , +.Xr ck_epoch_register 3 , +.Xr ck_epoch_recycle 3 , +.Xr ck_epoch_poll 3 , +.Xr ck_epoch_synchronize 3 , +.Xr ck_epoch_reclaim 3 , +.Xr ck_epoch_barrier 3 , +.Xr ck_epoch_call 3 , +.Xr ck_epoch_begin 3 , +.Xr ck_epoch_end 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_hs_count ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_hs_count b/lib/ck/doc/ck_hs_count new file mode 100644 index 0000000..c12d8f7 --- /dev/null +++ b/lib/ck/doc/ck_hs_count @@ -0,0 +1,70 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 17, 2012 +.Dt CK_HS_COUNT 3 +.Sh NAME +.Nm ck_hs_count +.Nd returns number of entries in hash set +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_hs.h +.Ft unsigned long +.Fn ck_hs_count "ck_hs_t *hs" +.Sh DESCRIPTION +The +.Fn ck_hs_count 3 +function returns the number of keys currently +stored in +.Fa hs . +.Sh ERRORS +Behavior is undefined if +.Fa hs +is uninitialized. Behavior is +undefined if this function is called by a non-writer +thread. +.Sh SEE ALSO +.Xr ck_hs_init 3 , +.Xr ck_hs_move 3 , +.Xr ck_hs_destroy 3 , +.Xr CK_HS_HASH 3 , +.Xr ck_hs_iterator_init 3 , +.Xr ck_hs_next 3 , +.Xr ck_hs_get 3 , +.Xr ck_hs_put 3 , +.Xr ck_hs_put_unique 3 , +.Xr ck_hs_set 3 , +.Xr ck_hs_fas 3 , +.Xr ck_hs_remove 3 , +.Xr ck_hs_grow 3 , +.Xr ck_hs_rebuild 3 , +.Xr ck_hs_gc 3 , +.Xr ck_hs_reset 3 , +.Xr ck_hs_reset_size 3 , +.Xr ck_hs_stat 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_hs_destroy ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_hs_destroy b/lib/ck/doc/ck_hs_destroy new file mode 100644 index 0000000..952502b --- /dev/null +++ b/lib/ck/doc/ck_hs_destroy @@ -0,0 +1,77 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 17, 2012 +.Dt CK_HS_DESTROY 3 +.Sh NAME +.Nm ck_hs_destroy +.Nd destroy hash set +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_hs.h +.Ft void +.Fn ck_hs_destroy "ck_hs_t *hs" +.Sh DESCRIPTION +The +.Fn ck_hs_destroy 3 +function will request that the underlying allocator, as specified by the +.Xr ck_hs_init 3 +function, immediately destroy the object pointed to by the +.Fa hs +argument. +The user must guarantee that no threads are accessing the object pointed to +by +.Fa hs +when +.Fn ck_hs_destroy 3 +is called. +.Sh RETURN VALUES +.Fn ck_hs_destroy 3 +has no return value. +.Sh ERRORS +This function is guaranteed not to fail. +.Sh SEE ALSO +.Xr ck_hs_init 3 , +.Xr ck_hs_move 3 , +.Xr CK_HS_HASH 3 , +.Xr ck_hs_iterator_init 3 , +.Xr ck_hs_next 3 , +.Xr ck_hs_get 3 , +.Xr ck_hs_put 3 , +.Xr ck_hs_put_unique 3 , +.Xr ck_hs_set 3 , +.Xr ck_hs_fas 3 , +.Xr ck_hs_remove 3 , +.Xr ck_hs_grow 3 , +.Xr ck_hs_rebuild 3 , +.Xr ck_hs_gc 3 , +.Xr ck_hs_count 3 , +.Xr ck_hs_reset 3 , +.Xr ck_hs_reset_size 3 , +.Xr ck_hs_stat 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_hs_fas ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_hs_fas b/lib/ck/doc/ck_hs_fas new file mode 100644 index 0000000..213cef6 --- /dev/null +++ b/lib/ck/doc/ck_hs_fas @@ -0,0 +1,98 @@ +.\" +.\" Copyright 2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd June 20, 2013 +.Dt CK_HS_FAS 3 +.Sh NAME +.Nm ck_hs_fas +.Nd fetch and store key in hash set +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_hs.h +.Ft bool +.Fn ck_hs_fas "ck_hs_t *hs" "unsigned long hash" "const void *key" "void **previous" +.Sh DESCRIPTION +The +.Fn ck_hs_fas 3 +function will fetch and store the key specified by the +.Fa key +argument in the hash set pointed to by the +.Fa hs +argument. The key specified by +.Fa key +is expected to have the hash value specified by the +.Fa hash +argument (which was previously generated using the +.Xr CK_HS_HASH 3 +macro). +.Pp +If the call to +.Fn ck_hs_fas 3 +was successful then the key specified by +.Fa key +was successfully stored in the hash set pointed to by +.Fa hs . +The key must already exist in the hash set, and is +replaced by +.Fa key +and the previous value is stored into the void pointer +pointed to by the +.Fa previous +argument. If the key does not exist in the hash set +then the function will return false and the hash set +is unchanged. This function +is guaranteed to be stable with respect to memory usage. +.Sh RETURN VALUES +Upon successful completion, +.Fn ck_hs_fas 3 +returns true and otherwise returns false on failure. +.Sh ERRORS +Behavior is undefined if +.Fa key +or +.Fa hs +are uninitialized. +.Sh SEE ALSO +.Xr ck_hs_init 3 , +.Xr ck_hs_move 3 , +.Xr ck_hs_destroy 3 , +.Xr CK_HS_HASH 3 , +.Xr ck_hs_iterator_init 3 , +.Xr ck_hs_next 3 , +.Xr ck_hs_get 3 , +.Xr ck_hs_put 3 , +.Xr ck_hs_put_unique 3 , +.Xr ck_hs_remove 3 , +.Xr ck_hs_grow 3 , +.Xr ck_hs_rebuild 3 , +.Xr ck_hs_gc 3 , +.Xr ck_hs_count 3 , +.Xr ck_hs_reset 3 , +.Xr ck_hs_reset_size 3 , +.Xr ck_hs_stat 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_hs_gc ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_hs_gc b/lib/ck/doc/ck_hs_gc new file mode 100644 index 0000000..85abba2 --- /dev/null +++ b/lib/ck/doc/ck_hs_gc @@ -0,0 +1,88 @@ +.\" +.\" Copyright 2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd December 17, 2013 +.Dt CK_HS_GC 3 +.Sh NAME +.Nm ck_hs_gc +.Nd perform maintenance on a hash set +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_hs.h +.Ft bool +.Fn ck_hs_gc "ck_hs_t *hs" "unsigned long cycles" "unsigned long seed" +.Sh DESCRIPTION +The +.Fn ck_hs_gc 3 +function will perform various maintenance routines on the hash set +pointed to by +.Fa hs , +including defragmentation of probe sequences with respect to tombstones +and in the case that the delete workload hint has been passed, recalculation +of probe sequence bounds. The +.Fa cycles +argument is used to indicate how many hash set entries should be subject +to attempted maintenance. If +.Fa cycles +is 0, then maintenance is performed on the complete hash set. The +.Fa seed +argument determines the start location of the maintenance process. If +.Fa cycles +is non-zero, it is recommended that +.Fa seed +is some random value. If the delete hint has been passed, the function +will require an additional 12% of memory (with respect to existing +memory usage of the set), until operation completion. +.Sh RETURN VALUES +Upon successful completion, +.Fn ck_hs_gc 3 +returns true and otherwise returns false on failure due to memory allocation +failure. +.Sh ERRORS +This function will only return false if there are internal memory allocation +failures. +.Sh SEE ALSO +.Xr ck_hs_init 3 , +.Xr ck_hs_move 3 , +.Xr ck_hs_destroy 3 , +.Xr CK_HS_HASH 3 , +.Xr ck_hs_iterator_init 3 , +.Xr ck_hs_next 3 , +.Xr ck_hs_get 3 , +.Xr ck_hs_put 3 , +.Xr ck_hs_put_unique 3 , +.Xr ck_hs_grow 3 , +.Xr ck_hs_rebuild 3 , +.Xr ck_hs_set 3 , +.Xr ck_hs_fas 3 , +.Xr ck_hs_remove 3 , +.Xr ck_hs_count 3 , +.Xr ck_hs_reset 3 , +.Xr ck_hs_reset_size 3 , +.Xr ck_hs_stat 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_hs_get ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_hs_get b/lib/ck/doc/ck_hs_get new file mode 100644 index 0000000..9c1600d --- /dev/null +++ b/lib/ck/doc/ck_hs_get @@ -0,0 +1,88 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 17, 2012 +.Dt CK_HS_GET 3 +.Sh NAME +.Nm ck_hs_get +.Nd load a key from a hash set +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_hs.h +.Ft void * +.Fn ck_hs_get "ck_hs_t *hs" "unsigned long hash" "const void *key" +.Sh DESCRIPTION +The +.Fn ck_hs_get 3 +function will return a pointer to a key in the hash set +.Fa hs +that is of equivalent value to the object pointed to by +.Fa key . +The key specified by +.Fa key +is expected to have the hash value specified by the +.Fa hash +argument (which is to have been previously generated using the +.Xr CK_HS_HASH 3 +macro). +.Sh RETURN VALUES +If the provided key is a member of +.Fa hs +then a pointer to the key as stored in +.Fa hs +is returned. If the key was not found in +.Fa hs +then a value of +.Dv NULL +is returned. +.Sh ERRORS +Behavior is undefined if +.Fa entry +or +.Fa hs +are uninitialized. +.Sh SEE ALSO +.Xr ck_hs_init 3 , +.Xr ck_hs_move 3 , +.Xr ck_hs_destroy 3 , +.Xr CK_HS_HASH 3 , +.Xr ck_hs_iterator_init 3 , +.Xr ck_hs_next 3 , +.Xr ck_hs_put 3 , +.Xr ck_hs_put_unique 3 , +.Xr ck_hs_set 3 , +.Xr ck_hs_fas 3 , +.Xr ck_hs_remove 3 , +.Xr ck_hs_grow 3 , +.Xr ck_hs_rebuild 3 , +.Xr ck_hs_gc 3 , +.Xr ck_hs_count 3 , +.Xr ck_hs_reset 3 , +.Xr ck_hs_reset_size 3 , +.Xr ck_hs_stat 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_hs_grow ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_hs_grow b/lib/ck/doc/ck_hs_grow new file mode 100644 index 0000000..ed35cd0 --- /dev/null +++ b/lib/ck/doc/ck_hs_grow @@ -0,0 +1,81 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 17, 2012 +.Dt CK_HS_GROW 3 +.Sh NAME +.Nm ck_hs_grow +.Nd enlarge hash set capacity +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_hs.h +.Ft bool +.Fn ck_hs_grow "ck_hs_t *hs" "unsigned long capacity" +.Sh DESCRIPTION +The +.Fn ck_hs_grow 3 +function will resize the hash set in order to be +able to store at least the number of entries specified by +.Fa capacity +at a load factor of one. The default hash set load factor +is 0.5. If you wish to minimize the likelihood of memory allocations +for a hash set meant to store n entries, then specify a +.Fa capacity +of 2n. The default behavior of ck_hs is to round +.Fa capacity +to the next power of two if it is not already a power of two. +.Sh RETURN VALUES +Upon successful completion, +.Fn ck_hs_grow 3 +returns true and otherwise returns false on failure. +.Sh ERRORS +Behavior is undefined if +.Fa hs +is uninitialized. This function will only +return false if there are internal memory allocation +failures. +.Sh SEE ALSO +.Xr ck_hs_init 3 , +.Xr ck_hs_move 3 , +.Xr ck_hs_destroy 3 , +.Xr CK_HS_HASH 3 , +.Xr ck_hs_iterator_init 3 , +.Xr ck_hs_next 3 , +.Xr ck_hs_get 3 , +.Xr ck_hs_put 3 , +.Xr ck_hs_put_unique 3 , +.Xr ck_hs_set 3 , +.Xr ck_hs_fas 3 , +.Xr ck_hs_remove 3 , +.Xr ck_hs_rebuild 3 , +.Xr ck_hs_gc 3 , +.Xr ck_hs_count 3 , +.Xr ck_hs_reset 3 , +.Xr ck_hs_reset_size 3 , +.Xr ck_hs_stat 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_hs_init ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_hs_init b/lib/ck/doc/ck_hs_init new file mode 100644 index 0000000..cfcbf63 --- /dev/null +++ b/lib/ck/doc/ck_hs_init @@ -0,0 +1,169 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 17, 2012 +.Dt CK_HS_INIT 3 +.Sh NAME +.Nm ck_hs_init +.Nd initialize a hash set +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_hs.h +.Ft typedef unsigned long +.Fn ck_hs_hash_cb_t "const void *key" "unsigned long seed" +.Ft typedef bool +.Fn ck_hs_compare_cb_t "const void *c1" "const void *c2" +.Ft bool +.Fn ck_hs_init "ck_hs_t *hs" "unsigned int mode" "ck_hs_hash_cb_t *hash_function" "ck_hs_compare_cb_t *compare" "struct ck_malloc *allocator" "unsigned long capacity" "unsigned long seed" +.Sh DESCRIPTION +The +.Fn ck_hs_init +function initializes the hash set pointed to by the +.Fa hs +pointer. +.Pp +The argument +.Fa mode +specifies the type of key-value pairs to be stored in the +hash set as well as the expected concurrent access model. +The value of +.Fa mode +consists of a bitfield of one of the following: +.Bl -tag -width indent +.It CK_HS_MODE_OBJECT +The hash set is meant to store pointers to objects. This provides +a hint that only CK_MD_VMA_BITS are necessary to encode the key +argument. Any unused pointer bits are leveraged for internal +optimizations. +.It CK_HS_MODE_DIRECT +The hash set is meant to directly store key values and that all +bits of the key are used to encode values. +.El +.Pp +The concurrent access model is specified by: +.Bl -tag -width indent +.It CK_HS_MODE_SPMC +The hash set should allow for concurrent readers in the +presence of a single writer. +.It CK_HS_MODE_MPMC +The hash set should allow for concurrent readers in the +presence of concurrent writers. This is currently unsupported. +.El +.Pp +The developer is free to specify additional workload hints. +These hints are one of: +.Bl -tag -width indent +.It CK_HS_MODE_DELETE +The hash set is expected to have a delete-heavy workload. +At the cost of approximately 13% increased memory usage, +allow for stronger per-slot probe bounds to combat the +effects of tombstone accumulation. +.El +.Pp +The argument +.Fa hash_function +is a mandatory pointer to a user-specified hash function. +A user-specified hash function takes two arguments. The +.Fa key +argument is a pointer to a key. The +.Fa seed +argument is the initial seed associated with the hash set. +This initial seed is specified by the user in +.Xr ck_hs_init 3 . +.Pp +The +.Fa compare +argument is an optional pointer to a user-specified +key comparison function. If NULL is specified in this +argument, then pointer equality will be used to determine +key equality. A user-specified comparison function takes +two arguments representing pointers to the objects being +compared for equality. It is expected to return true +if the keys are of equal value and false otherwise. +.Pp +The +.Fa allocator +argument is a pointer to a structure containing +.Fa malloc +and +.Fa free +function pointers which respectively define the memory allocation and +destruction functions to be used by the hash set being initialized. +.Pp +The argument +.Fa capacity +represents the initial number of keys the hash +set is expected to contain. This argument is simply a hint +and the underlying implementation is free to allocate more +or less memory than necessary to contain the number of entries +.Fa capacity +specifies. +.Pp +The argument +.Fa seed +specifies the initial seed used by the underlying hash function. +The user is free to choose a value of their choice. +.Sh RETURN VALUES +Upon successful completion +.Fn ck_hs_init +returns a value of +.Dv true +and otherwise returns a value of +.Dv false +to indicate an error. +.Sh ERRORS +.Bl -tag -width Er +.Pp +The behavior of +.Fn ck_hs_init +is undefined if +.Fa hs +is not a pointer to a +.Tn ck_hs_t +object. +.El +.Sh SEE ALSO +.Xr ck_hs_move 3 , +.Xr ck_hs_destroy 3 , +.Xr CK_HS_HASH 3 , +.Xr ck_hs_iterator_init 3 , +.Xr ck_hs_next 3 , +.Xr ck_hs_get 3 , +.Xr ck_hs_put 3 , +.Xr ck_hs_put_unique 3 , +.Xr ck_hs_set 3 , +.Xr ck_hs_fas 3 , +.Xr ck_hs_remove 3 , +.Xr ck_hs_grow 3 , +.Xr ck_hs_rebuild 3 , +.Xr ck_hs_gc 3 , +.Xr ck_hs_count 3 , +.Xr ck_hs_reset 3 , +.Xr ck_hs_reset_size 3 , +.Xr ck_hs_stat 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_hs_iterator_init ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_hs_iterator_init b/lib/ck/doc/ck_hs_iterator_init new file mode 100644 index 0000000..d2c25cc --- /dev/null +++ b/lib/ck/doc/ck_hs_iterator_init @@ -0,0 +1,78 @@ +.\" +.\" Copyright 2012-2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd September 17, 2012 +.Dt CK_HS_ITERATOR_INIT 3 +.Sh NAME +.Nm ck_hs_iterator_init +.Nd initialize hash set iterator +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_hs.h +.Pp +.Dv ck_hs_iterator_t iterator = CK_HS_ITERATOR_INITIALIZER +.Pp +.Ft void +.Fn ck_hs_iterator_init "ck_hs_iterator_t *iterator" +.Sh DESCRIPTION +The +.Fn ck_hs_iterator_init 3 +function will initialize the object pointed to +by the +.Fa iterator +argument. Alternatively, an iterator may be statically +initialized by assigning it to the CK_HS_ITERATOR_INITIALIZER value. +.Pp +An iterator is used to iterate through hash set entries with the +.Xr ck_hs_next 3 +function. +.Sh RETURN VALUES +.Fn ck_hs_iterator_init 3 +has no return value. +.Sh ERRORS +This function will not fail. +.Sh SEE ALSO +.Xr ck_hs_init 3 , +.Xr ck_hs_move 3 , +.Xr ck_hs_destroy 3 , +.Xr CK_HS_HASH 3 , +.Xr ck_hs_next 3 , +.Xr ck_hs_get 3 , +.Xr ck_hs_put 3 , +.Xr ck_hs_put_unique 3 , +.Xr ck_hs_set 3 , +.Xr ck_hs_fas 3 , +.Xr ck_hs_remove 3 , +.Xr ck_hs_grow 3 , +.Xr ck_hs_rebuild 3 , +.Xr ck_hs_gc 3 , +.Xr ck_hs_count 3 , +.Xr ck_hs_reset 3 , +.Xr ck_hs_reset_size 3 , +.Xr ck_hs_stat 3 +.Pp +Additional information available at http://concurrencykit.org/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_hs_move ---------------------------------------------------------------------- diff --git a/lib/ck/doc/ck_hs_move b/lib/ck/doc/ck_hs_move new file mode 100644 index 0000000..e843ea7 --- /dev/null +++ b/lib/ck/doc/ck_hs_move @@ -0,0 +1,90 @@ +.\" +.\" Copyright 2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd July 18, 2013 +.Dt CK_HS_MOVE 3 +.Sh NAME +.Nm ck_hs_move +.Nd move one from hash set to another +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_hs.h +.Ft bool +.Fn ck_hs_move "ck_hs_t *destination" "ck_hs_t *source" "ck_hs_hash_cb_t *hash_cb" "ck_hs_compare_cb_t *compare_cb" "struct ck_malloc *m" +.Sh DESCRIPTION +The +.Fn ck_hs_move 3 +function will initialize +.Fa source +from +.Fa destination . +The hash function is set to +.Fa hash_cb , +comparison function to +.Fa compare_cb +and the allocator callbacks to +.Fa m . +Further modifications to +.Fa source +will result in undefined behavior. Concurrent +.Xr ck_hs_get 3 +and +.Xr ck_hs_fas 3 +operations to +.Fa source +are legal until the next write operation to +.Fa destination . +.Pp +This operation moves ownership from one hash set object +to another and re-assigns callback functions to developer-specified +values. This allows for dynamic configuration of allocation +callbacks and is necessary for use-cases involving executable code +which may be unmapped underneath the hash set. +.Sh RETURN VALUES +Upon successful completion +.Fn ck_hs_move 3 +returns true and otherwise returns false to indicate an error. +.Sh SEE ALSO +.Xr ck_hs_init 3 , +.Xr ck_hs_destroy 3 , +.Xr CK_HS_HASH 3 , +.Xr ck_hs_iterator_init 3 , +.Xr ck_hs_next 3 , +.Xr ck_hs_put 3 , +.Xr ck_hs_put_unique 3 , +.Xr ck_hs_set 3 , +.Xr ck_hs_fas 3 , +.Xr ck_hs_remove 3 , +.Xr ck_hs_grow 3 , +.Xr ck_hs_rebuild 3 , +.Xr ck_hs_gc 3 , +.Xr ck_hs_count 3 , +.Xr ck_hs_reset 3 , +.Xr ck_hs_reset_size 3 , +.Xr ck_hs_stat 3 +.Pp +Additional information available at http://concurrencykit.org/
