You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by so...@apache.org on 2014/08/01 22:44:27 UTC
[14/20] TS-2950: Initial commit of libck.
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_ring_enqueue_spmc
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_ring_enqueue_spmc b/lib/ck/doc/ck_ring_enqueue_spmc
new file mode 100644
index 0000000..20fd6a8
--- /dev/null
+++ b/lib/ck/doc/ck_ring_enqueue_spmc
@@ -0,0 +1,115 @@
+.\"
+.\" 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 April 20, 2013
+.Dt CK_RING_ENQUEUE_SPMC 3
+.Sh NAME
+.Nm ck_ring_enqueue_spmc
+.Nd enqueue pointer into bounded FIFO
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_ring.h
+.Ft bool
+.Fn ck_ring_enqueue_spmc "ck_ring_t *ring" "ck_ring_buffer_t *buffer" "void *entry"
+.Sh DESCRIPTION
+The
+.Fn ck_ring_enqueue_spmc 3
+function enqueues the pointer
+.Fa entry
+into the bounded buffer pointed to by
+.Fa ring
+in FIFO fashion.
+The buffer pointed to by
+.Fa buffer
+must be unique to
+.Fa ring
+and point to an array of ck_ring_buffer_t of sufficient
+length (according to the power-of-2 elements in the buffer).
+The decoupling of the ring from the buffer serves
+to address use-cases involving multiple address spaces
+and DMA, among others.
+If you are on non-POSIX platforms or wish for strict
+compliance with C, then it is recommended to pass a
+pointer of type void ** for
+.Fa entry .
+This function is safe to call without locking for UINT_MAX
+concurrent invocations of
+.Fn ck_ring_dequeue_spmc 3
+or
+.Fn ck_ring_trydequeue_spmc 3 .
+This function provides wait-free progress
+guarantees for one active invocation.
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_ring.h>
+
+/* This ring was previously initialized with ck_ring_init. */
+ck_ring_t ring;
+
+/* The ring was initialized for 1023 elements. */
+ck_ring_buffer_t buffer[1024];
+
+void
+enqueue(void)
+{
+ void *entry = some_object;
+
+ /* Attempt to enqueue pointer to some_object into buffer. */
+ if (ck_ring_enqueue_spmc(&ring, &buffer, &entry) == false) {
+ /*
+ * The buffer was full and the enqueue operation
+ * has failed.
+ */
+ return;
+ }
+
+ /* Enqueue operation completed successfully. */
+ return;
+}
+.Ed
+.Sh RETURN VALUES
+The function returns true if the value of
+.Fa entry
+was successfully enqueued into
+.Fa ring .
+The function will return false if the value of
+.Fa entry
+could not be enqueued which only occurs if
+.Fa ring
+was full.
+.Sh SEE ALSO
+.Xr ck_ring_init 3 ,
+.Xr ck_ring_dequeue_spmc 3 ,
+.Xr ck_ring_trydequeue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc_size 3 ,
+.Xr ck_ring_dequeue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc_size 3 ,
+.Xr ck_ring_capacity 3 ,
+.Xr ck_ring_size 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_ring_enqueue_spmc_size
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_ring_enqueue_spmc_size b/lib/ck/doc/ck_ring_enqueue_spmc_size
new file mode 100644
index 0000000..900bd28
--- /dev/null
+++ b/lib/ck/doc/ck_ring_enqueue_spmc_size
@@ -0,0 +1,127 @@
+.\"
+.\" 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 April 20, 2013
+.Dt CK_RING_ENQUEUE_SPMC_SIZE 3
+.Sh NAME
+.Nm ck_ring_enqueue_spmc_size
+.Nd enqueue pointer into bounded FIFO and return size of buffer
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_ring.h
+.Ft bool
+.Fn ck_ring_enqueue_spmc_size "ck_ring_t *ring" "ck_ring_buffer_t *buffer" "void *entry" "unsigned int *length"
+.Sh DESCRIPTION
+The
+.Fn ck_ring_enqueue_spmc 3
+function enqueues the pointer
+.Fa entry
+into the bounded buffer pointed to by
+.Fa ring
+in FIFO fashion.
+The buffer pointed to by
+.Fa buffer
+must be unique to
+.Fa ring
+and point to an array of ck_ring_buffer_t of sufficient
+length (according to the power-of-2 elements in the buffer).
+The decoupling of the ring from the buffer serves
+to address use-cases involving multiple address spaces
+and DMA, among others.
+If you are on non-POSIX platforms or wish for strict
+compliance with C, then it is recommended to pass a
+pointer of type void ** for
+.Fa entry .
+This function is safe to call without locking for UINT_MAX
+concurrent invocations of
+.Fn ck_ring_dequeue_spmc 3
+or
+.Fn ck_ring_trydequeue_spmc 3 .
+This function provides wait-free progress
+guarantees for one active invocation.
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_ring.h>
+
+/* This ring was previously initialized with ck_ring_init. */
+ck_ring_t ring;
+
+/* The ring was initialized for 1023 elements. */
+ck_ring_buffer_t buffer[1024];
+
+void
+enqueue(void)
+{
+ void *entry = some_object;
+ unsigned int length;
+
+ /* Attempt to enqueue pointer to some_object into buffer. */
+ if (ck_ring_enqueue_spmc_size(&ring, &buffer, &entry, &length) == false) {
+ /*
+ * The buffer was full and the enqueue operation
+ * has failed.
+ */
+ return;
+ }
+
+ /*
+ * If entry was the 101st or greater pointer in the buffer,
+ * do something.
+ */
+ if (length > 100) {
+ do_something;
+ }
+
+ return;
+}
+.Ed
+.Sh RETURN VALUES
+The function returns true if the value of
+.Fa entry
+was successfully enqueued into
+.Fa ring .
+The function will return false if the value of
+.Fa entry
+could not be enqueued which only occurs if
+.Fa ring
+was full. The number of entries in the buffer
+with respect to the point in time that
+.Fa entry
+is enqueued is stored in the integer pointed to by
+.Fa length .
+.Sh SEE ALSO
+.Xr ck_ring_init 3 ,
+.Xr ck_ring_dequeue_spmc 3 ,
+.Xr ck_ring_trydequeue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc 3 ,
+.Xr ck_ring_dequeue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc_size 3 ,
+.Xr ck_ring_capacity 3 ,
+.Xr ck_ring_size 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_ring_enqueue_spsc
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_ring_enqueue_spsc b/lib/ck/doc/ck_ring_enqueue_spsc
new file mode 100644
index 0000000..e5fbbec
--- /dev/null
+++ b/lib/ck/doc/ck_ring_enqueue_spsc
@@ -0,0 +1,113 @@
+.\"
+.\" 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 April 20, 2013
+.Dt CK_RING_ENQUEUE_SPSC 3
+.Sh NAME
+.Nm ck_ring_enqueue_spsc
+.Nd enqueue pointer into bounded FIFO
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_ring.h
+.Ft bool
+.Fn ck_ring_enqueue_spsc "ck_ring_t *ring" "ck_ring_buffer_t *buffer" "void *entry"
+.Sh DESCRIPTION
+The
+.Fn ck_ring_enqueue_spsc 3
+function enqueues the pointer
+.Fa entry
+into the bounded buffer pointed to by
+.Fa ring
+in FIFO fashion.
+The buffer pointed to by
+.Fa buffer
+must be unique to
+.Fa ring
+and point to an array of ck_ring_buffer_t of sufficient
+length (according to the power-of-2 elements in the buffer).
+The decoupling of the ring from the buffer serves
+to address use-cases involving multiple address spaces
+and DMA, among others.
+If you are on non-POSIX platforms or wish for strict
+compliance with C, then it is recommended to pass a
+pointer of type void ** for
+.Fa entry .
+This function is safe to call without locking for up to
+one concurrent invocation of
+.Fn ck_ring_dequeue_spsc 3 .
+This function provides wait-free progress
+guarantees.
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_ring.h>
+
+/* This ring was previously initialized with ck_ring_init. */
+ck_ring_t ring;
+
+/* The ring was initialized for 1023 elements. */
+ck_ring_buffer_t buffer[1024];
+
+void
+enqueue(void)
+{
+ void *entry = some_object;
+
+ /* Attempt to enqueue pointer to some_object into buffer. */
+ if (ck_ring_enqueue_spsc(&ring, &buffer, &entry) == false) {
+ /*
+ * The buffer was full and the enqueue operation
+ * has failed.
+ */
+ return;
+ }
+
+ /* Enqueue operation completed successfully. */
+ return;
+}
+.Ed
+.Sh RETURN VALUES
+The function returns true if the value of
+.Fa entry
+was successfully enqueued into
+.Fa ring .
+The function will return false if the value of
+.Fa entry
+could not be enqueued which only occurs if
+.Fa ring
+was full.
+.Sh SEE ALSO
+.Xr ck_ring_init 3 ,
+.Xr ck_ring_dequeue_spmc 3 ,
+.Xr ck_ring_trydequeue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc_size 3 ,
+.Xr ck_ring_dequeue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc_size 3 ,
+.Xr ck_ring_capacity 3 ,
+.Xr ck_ring_size 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_ring_enqueue_spsc_size
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_ring_enqueue_spsc_size b/lib/ck/doc/ck_ring_enqueue_spsc_size
new file mode 100644
index 0000000..90bdf12
--- /dev/null
+++ b/lib/ck/doc/ck_ring_enqueue_spsc_size
@@ -0,0 +1,128 @@
+.\"
+.\" 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 April 20, 2013
+.Dt CK_RING_ENQUEUE_SPSC_SIZE 3
+.Sh NAME
+.Nm ck_ring_enqueue_spsc_size
+.Nd enqueue pointer into bounded FIFO and return size of buffer
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_ring.h
+.Ft bool
+.Fn ck_ring_enqueue_spsc_size "ck_ring_t *ring" "ck_ring_buffer_t *buffer" "void *entry" "unsigned int *size"
+.Sh DESCRIPTION
+The
+.Fn ck_ring_enqueue_spsc_size 3
+function enqueues the pointer
+.Fa entry
+into the bounded buffer pointed to by
+.Fa ring
+in FIFO fashion.
+The buffer pointed to by
+.Fa buffer
+must be unique to
+.Fa ring
+and point to an array of ck_ring_buffer_t of sufficient
+length (according to the power-of-2 elements in the buffer).
+The decoupling of the ring from the buffer serves
+to address use-cases involving multiple address spaces
+and DMA, among others.
+If you are on non-POSIX platforms or wish for strict
+compliance with C, then it is recommended to pass a
+pointer of type void ** for
+.Fa entry .
+This function is safe to call without locking for up to
+one concurrent invocation of
+.Fn ck_ring_dequeue_spsc 3 .
+This function provides wait-free progress
+guarantees.
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_ring.h>
+
+/* This ring was previously initialized with ck_ring_init. */
+ck_ring_t ring;
+
+/* The ring was initialized for 1023 elements. */
+ck_ring_buffer_t buffer[1024];
+
+void
+enqueue(void)
+{
+ void *entry = some_object;
+ unsigned int length;
+
+ /* Attempt to enqueue pointer to some_object into buffer. */
+ if (ck_ring_enqueue_spsc(&ring, &buffer, &entry, &length) == false) {
+ /*
+ * The buffer was full and the enqueue operation
+ * has failed.
+ */
+ return;
+ }
+
+ /*
+ * If buffer length was 100 items or more at the time entry was
+ * enqueued, do something.
+ */
+ if (length > 100) {
+ do_something;
+ }
+
+ return;
+}
+.Ed
+.Sh RETURN VALUES
+The function returns true if the value of
+.Fa entry
+was successfully enqueued into
+.Fa ring .
+This function will return the number of items
+in
+.Fa ring
+with respect to the linearization point (the
+point in item that
+.Fa entry
+is enqueued).
+The function will return false if the value of
+.Fa entry
+could not be enqueued which only occurs if
+.Fa ring
+was full.
+.Sh SEE ALSO
+.Xr ck_ring_init 3 ,
+.Xr ck_ring_dequeue_spmc 3 ,
+.Xr ck_ring_trydequeue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc_size 3 ,
+.Xr ck_ring_dequeue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc 3 ,
+.Xr ck_ring_capacity 3 ,
+.Xr ck_ring_size 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_ring_init
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_ring_init b/lib/ck/doc/ck_ring_init
new file mode 100644
index 0000000..914d1bb
--- /dev/null
+++ b/lib/ck/doc/ck_ring_init
@@ -0,0 +1,62 @@
+.\"
+.\" 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 April 20, 2013
+.Dt CK_RING_INIT 3
+.Sh NAME
+.Nm ck_ring_init
+.Nd initialize bounded FIFO
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_ring.h
+.Ft void
+.Fn ck_ring_init "ck_ring_t *ring" "unsigned int size"
+.Sh DESCRIPTION
+The
+.Fn ck_ring_init
+function initializes a bounded FIFO buffer pointed to by
+.Fa ring
+for the storage of up to
+.Fa size
+number of pointers.
+The
+.Fa size
+argument must be a power-of-two greater than or equal to 4.
+.Sh RETURN VALUES
+This function has no return value.
+.Sh SEE ALSO
+.Xr ck_ring_dequeue_spmc 3 ,
+.Xr ck_ring_trydequeue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc_size 3 ,
+.Xr ck_ring_dequeue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc_size 3 ,
+.Xr ck_ring_capacity 3 ,
+.Xr ck_ring_size 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_ring_size
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_ring_size b/lib/ck/doc/ck_ring_size
new file mode 100644
index 0000000..7ec69f4
--- /dev/null
+++ b/lib/ck/doc/ck_ring_size
@@ -0,0 +1,55 @@
+.\"
+.\" 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 April 20, 2013
+.Dt CK_RING_SIZE 3
+.Sh NAME
+.Nm ck_ring_size
+.Nd return number of pointers enqueued in bounded FIFO
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_ring.h
+.Ft unsigned int
+.Fn ck_ring_size "ck_ring_t *ring"
+.Sh DESCRIPTION
+The
+.Fn ck_ring_size 3
+function returns the number of pointers currently
+enqueued in the buffer pointed to by
+.Fa ring .
+.Sh SEE ALSO
+.Xr ck_ring_init 3 ,
+.Xr ck_ring_enqueue_spmc 3 ,
+.Xr ck_ring_dequeue_spmc 3 ,
+.Xr ck_ring_trydequeue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc_size 3 ,
+.Xr ck_ring_dequeue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc_size 3 ,
+.Xr ck_ring_capacity 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_ring_trydequeue_spmc
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_ring_trydequeue_spmc b/lib/ck/doc/ck_ring_trydequeue_spmc
new file mode 100644
index 0000000..52a92b6
--- /dev/null
+++ b/lib/ck/doc/ck_ring_trydequeue_spmc
@@ -0,0 +1,126 @@
+.\"
+.\" 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 April 20, 2013
+.Dt CK_RING_TRYDEQUEUE_SPMC 3
+.Sh NAME
+.Nm ck_ring_trydequeue_spmc
+.Nd dequeue from bounded FIFO and allow for spurious failure
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_ring.h
+.Ft bool
+.Fn ck_ring_trydequeue_spmc "ck_ring_t *ring" "ck_ring_buffer_t *buffer" "void *result"
+.Sh DESCRIPTION
+The
+.Fn ck_ring_trydequeue_spmc 3
+function attempts to dequeue a pointer from the bounded buffer
+pointed to by
+.Fa ring
+in FIFO fashion. The pointer is stored in the pointer
+pointed to by
+.Fa result .
+The buffer pointed to by
+.Fa buffer
+must be unique to
+.Fa ring
+and point to an array of ck_ring_buffer_t of sufficient
+length (according to the power-of-2 elements in the buffer).
+The decoupling of the ring from the buffer serves
+to address use-cases involving multiple address spaces
+and DMA, among others.
+If you are on non-POSIX platforms or wish for strict
+compliance with C, then it is recommended to pass a
+pointer of type void ** for
+.Fa result .
+This function is safe to call without locking for UINT_MAX
+concurrent
+.Fn ck_ring_dequeue_spmc 3
+or
+.Fn ck_ring_trydequeue_spmc 3
+invocations and up to one concurrent
+.Fn ck_ring_enqueue_spmc 3
+or
+.Fn ck_ring_tryenqueue_spmc 3
+invocation. This operation will always complete
+in a bounded number of steps. It is
+possible for the function to return false even
+if
+.Fa ring
+is non-empty. This
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_ring.h>
+
+/* This ring was previously initialized with ck_ring_init. */
+ck_ring_t ring;
+
+/* The ring was initialized for 1023 elements. */
+ck_ring_buffer_t buffer[1024];
+
+void
+dequeue(void)
+{
+ void *result;
+
+ /* Dequeue from ring until contention is actively observed. */
+ while (ck_ring_trydequeue_spmc(&ring, &buffer, &result) == true) {
+ /*
+ * Results contains the oldest pointer in ring
+ * since the dequeue operation returned true.
+ */
+ operation(result);
+ }
+
+ /* An empty ring was encountered, leave. */
+ return;
+}
+.Ed
+.Sh RETURN VALUES
+The function returns true if the dequeue operation
+completely successfully in a bounded number of steps.
+The result of the dequeue operation is stored in the
+value pointed to by
+.Fa result .
+Otherwise, the function will return false if the buffer was empty
+or if the operation could not be completed in a bounded
+number of steps. If the function returns false, then the contents
+of
+.Fa result
+are undefined.
+.Sh SEE ALSO
+.Xr ck_ring_init 3 ,
+.Xr ck_ring_dequeue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc 3 ,
+.Xr ck_ring_enqueue_spmc_size 3 ,
+.Xr ck_ring_dequeue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc 3 ,
+.Xr ck_ring_enqueue_spsc_size 3 ,
+.Xr ck_ring_capacity 3 ,
+.Xr ck_ring_size 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_rwcohort
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_rwcohort b/lib/ck/doc/ck_rwcohort
new file mode 100644
index 0000000..673261d
--- /dev/null
+++ b/lib/ck/doc/ck_rwcohort
@@ -0,0 +1,203 @@
+.\"
+.\" 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 April 23, 2013.
+.Dt ck_rwcohort 3
+.Sh NAME
+.Nm ck_rwcohort
+.Nd generalized interface for reader-writer locks using cohort locks
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_rwcohort.h
+In each of the following macros, "STRATEGY" should be replaced with either "NEUTRAL", "RP", or "WP"
+depending on which locking strategy the user prefers. RP and WP represent reader preference and
+writer preference, respectively, while NEUTRAL represents a strategy neutral to reads vs. writes.
+.Fn CK_RWCOHORT_STRATEGY_PROTOTYPE "COHORT_NAME cohort_name"
+.Fn CK_RWCOHORT_STRATEGY_NAME "COHORT_NAME cohort_name"
+.Fn CK_RWCOHORT_STRATEGY_INSTANCE "COHORT_NAME cohort_name"
+.Fn CK_RWCOHORT_STRATEGY_INIT "COHORT_NAME cohort_name" "RWCOHORT lock" "unsigned int wait_limit"
+Note: the wait_limit argument should be omitted for locks using the neutral strategy
+.Fn CK_RWCOHORT_STRATEGY_READ_LOCK "COHORT_NAME cohort_name" "RWCOHORT lock" "COHORT cohort" \
+"void *global_context" "void *local_context"
+.Fn CK_RWCOHORT_STRATEGY_READ_UNLOCK "COHORT_NAME cohort_name" "RWCOHORT lock" "COHORT cohort" \
+"void *global_context" "void *local_context"
+.Fn CK_RWCOHORT_STRATEGY_WRITE_LOCK "COHORT_NAME cohort_name" "RWCOHORT lock" "COHORT cohort" \
+"void *global_context" "void *local_context"
+.Fn CK_RWCOHORT_STRATEGY_WRITE_UNLOCK "COHORT_NAME cohort_name" "RWCOHORT lock" "COHORT cohort" \
+"void *global_context" "void *local_context"
+.Pp
+Arguments of type RWCOHORT must be pointers to structs defined using the
+.Xr CK_RWCOHORT_STRATEGY_PROTOTYPE 3
+macro with the same strategy and cohort name as the current call.
+.Pp
+Arguments of type COHORT must be pointers to structs defined using the
+.Xr CK_COHORT_PROTOTYPE 3
+macro.
+.Sh DESCRIPTION
+ck_rwcohort.h provides an interface for defining reader-writer locks
+that use cohort locks internally to increase performance on NUMA
+architectures. See
+.Xr ck_cohort 3
+for more information about cohort locks.
+.Pp
+Before using a reader-writer cohort lock, the user must define a cohort type using
+either the
+.Xr CK_COHORT_PROTOTYPE 3
+or the
+.Xr CK_COHORT_TRYLOCK_PROTOTYPE 3
+macros, and define a reader-writer lock type using the
+.Xr CK_RWCOHORT_PROTOTYPE 3
+macro.
+.Pp
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <stdlib.h>
+#include <pthread.h>
+
+#include <ck_pr.h>
+#include <ck_cohort.h>
+#include <ck_rwcohort.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)
+
+/* define a reader-writer type using the same cohort type */
+CK_RWCOHORT_WP_PROTOTYPE(test_cohort)
+
+static ck_spinlock_t global_lock = CK_SPINLOCK_INITIALIZER;
+static CK_COHORT_INSTANCE(test_cohort) *cohorts;
+static CK_RWCOHORT_WP_INSTANCE(test_cohort) rw_cohort = CK_RWCOHORT_WP_INITIALIZER;
+static unsigned int ready;
+
+static void *
+function(void *context)
+{
+ CK_COHORT_INSTANCE(test_cohort) *cohort = context;
+
+ while (ck_pr_load_uint(&ready) == 0);
+
+ while (ck_pr_load_uint(&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_rwlock
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_rwlock b/lib/ck/doc/ck_rwlock
new file mode 100644
index 0000000..60a18ab
--- /dev/null
+++ b/lib/ck/doc/ck_rwlock
@@ -0,0 +1,143 @@
+.\"
+.\" 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_rwlock 3
+.Sh NAME
+.Nm ck_rwlock_init ,
+.Nm ck_rwlock_write_lock ,
+.Nm ck_rwlock_write_unlock ,
+.Nm ck_rwlock_write_trylock ,
+.Nm ck_rwlock_write_downgrade ,
+.Nm ck_rwlock_locked_writer ,
+.Nm ck_rwlock_read_lock ,
+.Nm ck_rwlock_read_trylock ,
+.Nm ck_rwlock_read_unlock ,
+.Nm ck_rwlock_locked_reader ,
+.Nm ck_rwlock_recursive_write_lock ,
+.Nm ck_rwlock_recursive_write_trylock ,
+.Nm ck_rwlock_recurisve_write_unlock ,
+.Nm ck_rwlock_recursive_read_lock ,
+.Nm ck_rwlock_recursive_read_trylock ,
+.Nm ck_rwlock_recursive_read_unlock
+.Nd centralized write-biased reader-writer locks
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_rwlock.h
+.Pp
+.Dv ck_rwlock_t lock = CK_RWLOCK_INITIALIZER;
+.Pp
+.Ft void
+.Fn ck_rwlock_init "ck_rwlock_t *lock"
+.Ft void
+.Fn ck_rwlock_write_lock "ck_rwlock_t *lock"
+.Ft void
+.Fn ck_rwlock_write_unlock "ck_rwlock_t *lock"
+.Ft bool
+.Fn ck_rwlock_write_trylock "ck_rwlock_t *lock"
+.Ft bool
+.Fn ck_rwlock_write_downgrade "ck_rwlock_t *lock"
+.Ft bool
+.Fn ck_rwlock_locked_writer "ck_rwlock_t *lock"
+.Ft void
+.Fn ck_rwlock_read_lock "ck_rwlock_t *lock"
+.Ft bool
+.Fn ck_rwlock_read_trylock "ck_rwlock_t *lock"
+.Ft void
+.Fn ck_rwlock_read_unlock "ck_rwlock_t *lock"
+.Ft bool
+.Fn ck_rwlock_locked_reader "ck_rwlock_t *lock"
+.Pp
+.Dv ck_rwlock_recursive_t lock = CK_RWLOCK_RECURSIVE_INITIALIZER;
+.Pp
+.Ft void
+.Fn ck_rwlock_recursive_write_lock "ck_rwlock_recursive_t *lock" "unsigned int tid"
+.Ft bool
+.Fn ck_rwlock_recursive_write_trylock "ck_rwlock_recursive_t *lock" "unsigned int tid"
+.Ft void
+.Fn ck_rwlock_recurisve_write_unlock "ck_rwlock_recursive_t *lock"
+.Ft void
+.Fn ck_rwlock_recursive_read_lock "ck_rwlock_recursive_t *lock"
+.Ft bool
+.Fn ck_rwlock_recursive_read_trylock "ck_rwlock_recursive_t *lock"
+.Ft void
+.Fn ck_rwlock_recursive_read_unlock "ck_rwlock_recursive_t *lock"
+.Sh DESCRIPTION
+This is a centralized write-biased reader-writer lock. It
+requires very little space overhead and has a low latency
+fast path. Write-side recursion requires usage of ck_rwlock_recursive.
+Read-side recursion is disallowed. The
+.Fn ck_rwlock_write_downgrade
+function degrades the caller's write-side acquisition to a read-side
+acquisition without forfeit of current critical section.
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_rwlock.h>
+
+static ck_rwlock_t lock = CK_RWLOCK_INITIALIZER;
+
+static void
+reader(void)
+{
+
+ for (;;) {
+ ck_rwlock_read_lock(&lock);
+ /* Read-side critical section. */
+ ck_rwlock_read_unlock(&lock);
+
+ if (ck_rwlock_read_trylock(&lock) == true) {
+ /* Read-side critical section. */
+ ck_rwlock_read_unlock(&lock);
+ }
+ }
+
+ return;
+}
+
+static void
+writer(void)
+{
+
+ for (;;) {
+ ck_rwlock_write_lock(&lock);
+ /* Write-side critical section. */
+ ck_rwlock_write_unlock(&lock);
+
+ if (ck_rwlock_write_trylock(&lock, 1) == true) {
+ /* Write-side critical section. */
+ ck_rwlock_write_unlock(&lock);
+ }
+ }
+
+ return;
+}
+.Ed
+.Sh SEE ALSO
+.Xr ck_brlock 3 ,
+.Xr ck_elide 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_sequence
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_sequence b/lib/ck/doc/ck_sequence
new file mode 100644
index 0000000..ad06dbe
--- /dev/null
+++ b/lib/ck/doc/ck_sequence
@@ -0,0 +1,144 @@
+.\"
+.\" 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_sequence 3
+.Sh NAME
+.Nm ck_sequence_init ,
+.Nm ck_sequence_read_begin ,
+.Nm ck_sequence_read_retry ,
+.Nm ck_sequence_write_begin ,
+.Nm ck_sequence_write_end
+.Nd sequence locks
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_sequence.h
+.Pp
+.Dv ck_sequence_t seqlock = CK_SEQUENCE_INITIALIZER;
+.Pp
+.Ft void
+.Fn ck_sequence_init "ck_sequence_t *sq"
+.Ft unsigned int
+.Fn ck_sequence_read_begin "ck_sequence_t *sq"
+.Ft bool
+.Fn ck_sequence_read_retry "ck_sequence_t *sq" "unsigned int version"
+.Ft void
+.Fn ck_sequence_write_begin "ck_sequence_t *sq"
+.Ft void
+.Fn ck_sequence_write_end "ck_sequence_t *sq"
+.Sh DESCRIPTION
+It is recommended to use ck_sequence when a small amount of data that cannot be
+accessed atomically has to be synchronized with readers in a fashion that does
+not block any writer. Readers are able to execute their read-side critical
+sections without any atomic operations. A ck_sequence_t must be initialized
+before use. It may be initialized using either a static initializer
+(CK_SEQUENCE_INITIALIZER) or using
+.Fn ck_sequence_init .
+Before readers attempt to
+read data that may be concurrently modified they must first save the return
+value of
+.Fn ck_sequence_read_begin .
+While or after a reader has completed copying
+the data associated with a ck_sequence_t it must pass the earlier return value
+of
+.Fn ck_sequence_read_begin
+to
+.Fn "ck_sequence_read_retry". If
+.Fn ck_sequence_read_retry
+returns true then the copy of data may be inconsistent and the read process
+must be retried. Writers must rely on their own synchronization primitives.
+Once a writer has entered its respective critical section, it must call
+.Fn ck_sequence_write_begin
+to signal intent to update the data protected
+by the ck_sequence_t. Before the writer leaves its critical section it must
+execute
+.Fn ck_sequence_write_end
+to indicate that the updates have left respective objects in a consistent state.
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_sequence.h>
+#include <stdlib.h>
+
+static struct example {
+ int a;
+ int b;
+ int c;
+} global;
+
+static ck_sequence_t seqlock = CK_SEQUENCE_INITIALIZER;
+
+void
+reader(void)
+{
+ struct example copy;
+ unsigned int version;
+
+ /*
+ * Attempt a read of the data structure. If the structure
+ * has been modified between ck_sequence_read_begin and
+ * ck_sequence_read_retry then attempt another read since
+ * the data may be in an inconsistent state.
+ */
+ do {
+ version = ck_sequence_read_begin(&seqlock);
+ copy = global;
+ } while (ck_sequence_read_retry(&seqlock, version));
+
+ /*
+ * The previous may also be expressed using CK_SEQUENCE_READ.
+ * Generally recommend to only use ck_sequence_read_retry
+ * if you would like to detect a conflicting write at some
+ * higher granularity.
+ */
+ CK_SEQUENCE_READ(&seqlock, &version) {
+ copy = global;
+ }
+
+ return;
+}
+
+void
+writer(void)
+{
+
+ for (;;) {
+ ck_sequence_write_begin(&seqlock);
+ global.a = rand();
+ global.b = global.a + global.b;
+ global.c = global.b + global.c;
+ ck_sequence_write_end(&seqlock);
+ }
+
+ return;
+}
+.Ed
+.Sh SEE ALSO
+.Xr ck_brlock 3 ,
+.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_spinlock
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_spinlock b/lib/ck/doc/ck_spinlock
new file mode 100644
index 0000000..67d4555
--- /dev/null
+++ b/lib/ck/doc/ck_spinlock
@@ -0,0 +1,259 @@
+.\"
+.\" 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_spinlock 3
+.Sh NAME
+.Nm ck_spinlock_init ,
+.Nm ck_spinlock_lock ,
+.Nm ck_spinlock_unlock ,
+.Nm ck_spinlock_locked ,
+.Nm ck_spinlock_trylock ,
+.Nm ck_spinlock_anderson_init ,
+.Nm ck_spinlock_anderson_locked ,
+.Nm ck_spinlock_anderson_lock ,
+.Nm ck_spinlock_anderson_unlock ,
+.Nm ck_spinlock_cas_init ,
+.Nm ck_spinlock_cas_locked ,
+.Nm ck_spinlock_cas_lock ,
+.Nm ck_spinlock_cas_lock_eb ,
+.Nm ck_spinlock_cas_trylock ,
+.Nm ck_spinlock_cas_unlock ,
+.Nm ck_spinlock_clh_init ,
+.Nm ck_spinlock_clh_locked ,
+.Nm ck_spinlock_clh_lock ,
+.Nm ck_spinlock_clh_unlock ,
+.Nm ck_spinlock_dec_init ,
+.Nm ck_spinlock_dec_locked ,
+.Nm ck_spinlock_dec_lock ,
+.Nm ck_spinlock_dec_lock_eb ,
+.Nm ck_spinlock_dec_trylock ,
+.Nm ck_spinlock_dec_unlock ,
+.Nm ck_spinlock_fas_init ,
+.Nm ck_spinlock_fas_lock ,
+.Nm ck_spinlock_fas_lock_eb ,
+.Nm ck_spinlock_fas_locked ,
+.Nm ck_spinlock_fas_trylock ,
+.Nm ck_spinlock_fas_unlock ,
+.Nm ck_spinlock_hclh_init ,
+.Nm ck_spinlock_hclh_locked ,
+.Nm ck_spinlock_hclh_lock ,
+.Nm ck_spinlock_hclh_unlock ,
+.Nm ck_spinlock_mcs_init ,
+.Nm ck_spinlock_mcs_locked ,
+.Nm ck_spinlock_mcs_lock ,
+.Nm ck_spinlock_mcs_trylock ,
+.Nm ck_spinlock_mcs_unlock ,
+.Nm ck_spinlock_ticket_init ,
+.Nm ck_spinlock_ticket_locked ,
+.Nm ck_spinlock_ticket_lock ,
+.Nm ck_spinlock_ticket_lock_pb ,
+.Nm ck_spinlock_ticket_trylock ,
+.Nm ck_spinlock_ticket_unlock
+.Nd spinlock implementations
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_spinlock.h
+.Pp
+.Dv ck_spinlock_t spinlock = CK_SPINLOCK_INITIALIZER;
+.Ft void
+.Fn ck_spinlock_init "ck_spinlock_t *lock"
+.Ft void
+.Fn ck_spinlock_lock "ck_spinlock_t *lock"
+.Ft void
+.Fn ck_spinlock_unlock "ck_spinlock_t *lock"
+.Ft bool
+.Fn ck_spinlock_locked "ck_spinlock_t *lock"
+.Ft bool
+.Fn ck_spinlock_trylock "ck_spinlock_t *lock"
+.Ft void
+.Fn ck_spinlock_anderson_init "ck_spinlock_anderson_t *lock" "ck_spinlock_anderson_thread_t *slots" "unsigned int count"
+.Ft bool
+.Fn ck_spinlock_anderson_locked "ck_spinlock_anderson_t *lock"
+.Ft void
+.Fn ck_spinlock_anderson_lock "ck_spinlock_anderson_t *lock" "ck_spinlock_anderson_thread_t **slot"
+.Ft void
+.Fn ck_spinlock_anderson_unlock "ck_spinlock_anderson_t *lock" "ck_spinlock_anderson_thread_t *slot"
+.Pp
+.Dv ck_spinlock_cas_t spinlock = CK_SPINLOCK_CAS_INITIALIZER;
+.Ft void
+.Fn ck_spinlock_cas_init "ck_spinlock_cas_t *lock"
+.Ft bool
+.Fn ck_spinlock_cas_locked "ck_spinlock_cas_t *lock"
+.Ft void
+.Fn ck_spinlock_cas_lock "ck_spinlock_cas_t *lock"
+.Ft void
+.Fn ck_spinlock_cas_lock_eb "ck_spinlock_cas_t *lock"
+.Ft bool
+.Fn ck_spinlock_cas_trylock "ck_spinlock_cas_t *lock"
+.Ft void
+.Fn ck_spinlock_cas_unlock "ck_spinlock_cas_t *lock"
+.Ft void
+.Fn ck_spinlock_clh_init "ck_spinlock_clh_t **lock" "ck_spinlock_clh_t *unowned"
+.Ft bool
+.Fn ck_spinlock_clh_locked "ck_spinlock_clh_t **lock"
+.Ft void
+.Fn ck_spinlock_clh_lock "ck_spinlock_clh_t **lock" "ck_spinlock_clh_t *node"
+.Ft void
+.Fn ck_spinlock_clh_unlock "ck_spinlock_clh_t **node"
+.Pp
+.Dv ck_spinlock_dec_t spinlock = CK_SPINLOCK_DEC_INITIALIZER;
+.Ft void
+.Fn ck_spinlock_dec_init "ck_spinlock_dec_t *lock"
+.Ft bool
+.Fn ck_spinlock_dec_locked "ck_spinlock_dec_t *lock"
+.Ft void
+.Fn ck_spinlock_dec_lock "ck_spinlock_dec_t *lock"
+.Ft void
+.Fn ck_spinlock_dec_lock_eb "ck_spinlock_dec_t *lock"
+.Ft bool
+.Fn ck_spinlock_dec_trylock "ck_spinlock_dec_t *lock"
+.Ft void
+.Fn ck_spinlock_dec_unlock "ck_spinlock_dec_t *lock"
+.Pp
+.Dv ck_spinlock_fas_t spinlock = CK_SPINLOCK_FAS_INITIALIZER;
+.Ft void
+.Fn ck_spinlock_fas_init "ck_spinlock_fas_t *lock"
+.Ft void
+.Fn ck_spinlock_fas_lock "ck_spinlock_fas_t *lock"
+.Ft void
+.Fn ck_spinlock_fas_lock_eb "ck_spinlock_fas_t *lock"
+.Ft bool
+.Fn ck_spinlock_fas_locked "ck_spinlock_fas_t *lock"
+.Ft bool
+.Fn ck_spinlock_fas_trylock "ck_spinlock_fas_t *lock"
+.Ft void
+.Fn ck_spinlock_fas_unlock "ck_spinlock_fas_t *lock"
+.Pp
+.Ft void
+.Fn ck_spinlock_hclh_init "ck_spinlock_hclh_t **lock" "ck_spinlock_hclh_t *unowned"
+.Ft bool
+.Fn ck_spinlock_hclh_locked "ck_spinlock_hclh_t **lock"
+.Ft void
+.Fn ck_spinlock_hclh_lock "ck_spinlock_hclh_t **lock" "ck_spinlock_hclh_t *node"
+.Ft void
+.Fn ck_spinlock_hclh_unlock "ck_spinlock_hclh_t **node"
+.Pp
+.Dv ck_spinlock_mcs_t spinlock = CK_SPINLOCK_MCS_INITIALIZER;
+.Ft void
+.Fn ck_spinlock_mcs_init "ck_spinlock_mcs_t **lock"
+.Ft bool
+.Fn ck_spinlock_mcs_locked "ck_spinlock_mcs_t **lock"
+.Ft void
+.Fn ck_spinlock_mcs_lock "ck_spinlock_mcs_t **lock" "ck_spinlock_mcs_t *node"
+.Ft bool
+.Fn ck_spinlock_mcs_trylock "ck_spinlock_mcs_t **lock" "ck_spinlock_mcs_t *node"
+.Ft void
+.Fn ck_spinlock_mcs_unlock "ck_spinlock_mcs_t **lock" "ck_spinlock_mcs_t *node"
+.Pp
+.Dv ck_spinlock_ticket_t spinlock = CK_SPINLOCK_TICKET_INITIALIZER;
+.Ft void
+.Fn ck_spinlock_ticket_init "ck_spinlock_ticket_t *lock"
+.Ft bool
+.Fn ck_spinlock_ticket_locked "ck_spinlock_ticket_t *lock"
+.Ft void
+.Fn ck_spinlock_ticket_lock "ck_spinlock_ticket_t *lock"
+.Ft void
+.Fn ck_spinlock_ticket_lock_pb "ck_spinlock_ticket_t *lock" "unsigned int period"
+.Ft bool
+.Fn ck_spinlock_ticket_trylock "ck_spinlock_ticket_t *lock"
+.Ft void
+.Fn ck_spinlock_ticket_unlock "ck_spinlock_ticket_t *lock"
+.Sh DESCRIPTION
+A family of busy-wait spinlock implementations. The ck_spinlock_t implementation is simply
+a wrapper around the fetch-and-swap (ck_spinlock_fas_t) implementation. The table below
+provides a summary of the current implementations.
+.Bd -literal
+| Namespace | Algorithm | Type | Restrictions | Fair |
+\'----------------------|-----------------------------|---------------|-------------------------|--------'
+ ck_spinlock_anderson Anderson Array Fixed number of threads Yes
+ ck_spinlock_cas Compare-and-Swap Centralized None No
+ ck_spinlock_clh Craig, Landin and Hagersten Queue Lifetime requirements Yes
+ ck_spinlock_dec Decrement (Linux kernel) Centralized UINT_MAX concurrency No
+ ck_spinlock_fas Fetch-and-store Centralized None No
+ ck_spinlock_hclh Hierarchical CLH Queue Lifetime requirements Yes *
+ ck_spinlock_mcs Mellor-Crummey and Scott Queue None Yes
+ ck_spinlock_ticket Ticket Centralized None Yes
+.Ed
+.Pp
+* Hierarchical CLH only offers weak fairness for threads accross cluster
+nodes.
+.Pp
+If contention is low and there is no hard requirement for starvation-freedom
+then a centralized greedy (unfair) spinlock is recommended. If contention is
+high and there is no requirement for starvation-freedom then a centralized
+greedy spinlock is recommended to be used with an exponential backoff
+mechanism. If contention is generally low and there is a hard requirement for
+starvation-freedom then the ticket lock is recommended. If contention is high
+and there is a hard requirement for starvation-freedom then the Craig and
+Landin and Hagersten queue spinlock is recommended unless stack allocation is
+necessary or NUMA factor is high, in which case the Mellor-Crummey and Scott
+spinlock is recommended. If you cannot afford O(n) space-usage from array
+or queue spinlocks but still require fairness under high contention then
+the ticket lock with proportional back-off is recommended.
+If NUMA factor is high but prefer a greedy lock, then please see
+.Xr ck_cohort 3 .
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_spinlock.h>
+#include <stdbool.h>
+
+/*
+ * Alternatively, the mutex may be initialized at run-time with
+ * ck_spinlock_init(&mutex).
+ */
+ck_spinlock_t mutex = CK_SPINLOCK_INITIALIZER;
+
+void
+example(void)
+{
+
+ ck_spinlock_lock(&mutex);
+ /*
+ * Critical section.
+ */
+ ck_spinlock_unlock(&mutex);
+
+ ck_spinlock_lock_eb(&mutex);
+ /*
+ * Critical section.
+ */
+ ck_spinlock_unlock(&mutex);
+
+ if (ck_spinlock_trylock(&mutex) == true) {
+ /*
+ * Critical section.
+ */
+ ck_spinlock_unlock(&mutex);
+ }
+}
+.Ed
+.Sh SEE ALSO
+.Xr ck_cohort 3 ,
+.Xr ck_elide 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_swlock
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_swlock b/lib/ck/doc/ck_swlock
new file mode 100644
index 0000000..e101334
--- /dev/null
+++ b/lib/ck/doc/ck_swlock
@@ -0,0 +1,138 @@
+.\"
+.\" Copyright 2014 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 April 22, 2014.
+.Dt ck_swlock 3
+.Sh NAME
+.Nm ck_swlock_init ,
+.Nm ck_swlock_write_latch ,
+.Nm ck_swlock_write_unlatch ,
+.Nm ck_swlock_write_lock ,
+.Nm ck_swlock_write_unlock ,
+.Nm ck_swlock_write_trylock ,
+.Nm ck_swlock_write_downgrade ,
+.Nm ck_swlock_locked_writer ,
+.Nm ck_swlock_read_lock ,
+.Nm ck_swlock_read_trylock ,
+.Nm ck_swlock_read_unlock ,
+.Nm ck_swlock_locked_reader
+.Nd centralized copy-safe write-biased single-writer read-write locks
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_swlock.h
+.Pp
+.Dv ck_swlock_t lock = CK_SWLOCK_INITIALIZER;
+.Pp
+.Ft void
+.Fn ck_swlock_init "ck_swlock_t *lock"
+.Ft void
+.Fn ck_swlock_write_lock "ck_swlock_t *lock"
+.Ft void
+.Fn ck_swlock_write_unlock "ck_swlock_t *lock"
+.Ft void
+.Fn ck_swlatch_write_latch "ck_swlatch_t *latch"
+.Ft void
+.Fn ck_swlatch_write_unlatch "ck_swlatch_t *latch"
+.Ft bool
+.Fn ck_swlock_write_trylock "ck_swlock_t *lock"
+.Ft bool
+.Fn ck_swlock_write_downgrade "ck_swlock_t *lock"
+.Ft bool
+.Fn ck_swlock_locked_writer "ck_swlock_t *lock"
+.Ft void
+.Fn ck_swlock_read_lock "ck_swlock_t *lock"
+.Ft bool
+.Fn ck_swlock_read_trylock "ck_swlock_t *lock"
+.Ft void
+.Fn ck_swlock_read_unlock "ck_swlock_t *lock"
+.Ft bool
+.Fn ck_swlock_locked_reader "ck_swlock_t *lock"
+.Sh DESCRIPTION
+This is a centralized write-biased single-writer reader-writer lock. It
+requires half the space that ck_rwlock does and has a low latency
+fast path. The lock supports latch and unlatch operations that
+allow it to be used in a copy-safe manner (reader-bits may be
+over-written safely).
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_swlock.h>
+
+static ck_swlock_t lock = CK_SWLOCK_INITIALIZER;
+
+static void
+reader(void)
+{
+
+ for (;;) {
+ ck_swlock_read_lock(&lock);
+ /* Read-side critical section. */
+ ck_swlock_read_unlock(&lock);
+
+ if (ck_swlock_read_trylock(&lock) == true) {
+ /* Read-side critical section. */
+ ck_swlock_read_unlock(&lock);
+ }
+ }
+
+ return;
+}
+
+static void
+writer(void)
+{
+ ck_swlock_t contrived;
+
+ for (;;) {
+ ck_swlock_write_lock(&lock);
+ /* Write-side critical section. */
+ ck_swlock_write_unlock(&lock);
+
+ if (ck_swlock_write_trylock(&lock) == true) {
+ /* Write-side critical section. */
+ ck_swlock_write_unlock(&lock);
+ }
+
+ ck_swlock_write_latch(&lock);
+ /* Write-side critical section. */
+
+ /* This is safe to do with-in a latch. */
+ contrived = lock;
+ lock = contrived;
+ ck_swlock_write_unlatch(&lock);
+ }
+
+ return;
+}
+.Ed
+.Sh SEE ALSO
+.Xr ck_brlock 3 ,
+.Xr ck_elide 3 ,
+.Xr ck_pflock 3 ,
+.Xr ck_rwlock 3 ,
+.Xr ck_tflock 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/doc/ck_tflock
----------------------------------------------------------------------
diff --git a/lib/ck/doc/ck_tflock b/lib/ck/doc/ck_tflock
new file mode 100644
index 0000000..629dbd4
--- /dev/null
+++ b/lib/ck/doc/ck_tflock
@@ -0,0 +1,95 @@
+.\"
+.\" Copyright 2014 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 April 22, 2014.
+.Dt ck_tflock 3
+.Sh NAME
+.Nm ck_tflock_ticket_init ,
+.Nm ck_tflock_ticket_write_lock ,
+.Nm ck_tflock_ticket_write_unlock ,
+.Nm ck_tflock_ticket_read_lock ,
+.Nm ck_tflock_ticket_read_unlock ,
+.Nd centralized task-fair reader-writer locks
+.Sh LIBRARY
+Concurrency Kit (libck, \-lck)
+.Sh SYNOPSIS
+.In ck_tflock.h
+.Pp
+.Dv ck_tflock_ticket_t lock = CK_TFLOCK_TICKET_INITIALIZER;
+.Pp
+.Ft void
+.Fn ck_tflock_ticket_init "ck_tflock_ticket_t *lock"
+.Ft void
+.Fn ck_tflock_ticket_write_lock "ck_tflock_ticket_t *lock"
+.Ft void
+.Fn ck_tflock_ticket_write_unlock "ck_tflock_ticket_t *lock"
+.Ft void
+.Fn ck_tflock_ticket_read_lock "ck_tflock_ticket_t *lock"
+.Ft void
+.Fn ck_tflock_ticket_read_unlock "ck_tflock_ticket_t *lock"
+.Sh DESCRIPTION
+This is a centralized task-fair reader-writer lock. It
+requires little space overhead and has a low latency
+fast path.
+.Sh EXAMPLE
+.Bd -literal -offset indent
+#include <ck_tflock.h>
+
+static ck_tflock_ticket_t lock = CK_TFLOCK_INITIALIZER;
+
+static void
+reader(void)
+{
+
+ for (;;) {
+ ck_tflock_ticket_read_lock(&lock);
+ /* Read-side critical section. */
+ ck_tflock_ticket_read_unlock(&lock);
+ }
+
+ return;
+}
+
+static void
+writer(void)
+{
+
+ for (;;) {
+ ck_tflock_ticket_write_lock(&lock);
+ /* Write-side critical section. */
+ ck_tflock_ticket_write_unlock(&lock);
+ }
+
+ return;
+}
+.Ed
+.Sh SEE ALSO
+.Xr ck_brlock 3 ,
+.Xr ck_rwlock 3 ,
+.Xr ck_pflock 3 ,
+.Xr ck_swlock 3
+.Pp
+Additional information available at http://concurrencykit.org/
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/include/ck_array.h
----------------------------------------------------------------------
diff --git a/lib/ck/include/ck_array.h b/lib/ck/include/ck_array.h
new file mode 100644
index 0000000..e8e366b
--- /dev/null
+++ b/lib/ck/include/ck_array.h
@@ -0,0 +1,101 @@
+/*
+ * Copyright 2013-2014 Samy Al Bahra
+ * Copyright 2013-2014 AppNexus, Inc.
+ * 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 AUTHOR 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 AUTHOR 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.
+ */
+
+#ifndef _CK_ARRAY_H
+#define _CK_ARRAY_H
+
+#include <ck_cc.h>
+#include <ck_malloc.h>
+#include <ck_pr.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+struct _ck_array {
+ unsigned int n_committed;
+ unsigned int length;
+ void *values[];
+};
+
+struct ck_array {
+ struct ck_malloc *allocator;
+ struct _ck_array *active;
+ unsigned int n_entries;
+ struct _ck_array *transaction;
+};
+typedef struct ck_array ck_array_t;
+
+struct ck_array_iterator {
+ struct _ck_array *snapshot;
+};
+typedef struct ck_array_iterator ck_array_iterator_t;
+
+#define CK_ARRAY_MODE_SPMC 0U
+#define CK_ARRAY_MODE_MPMC (void) /* Unsupported. */
+
+bool ck_array_init(ck_array_t *, unsigned int, struct ck_malloc *, unsigned int);
+bool ck_array_commit(ck_array_t *);
+bool ck_array_put(ck_array_t *, void *);
+int ck_array_put_unique(ck_array_t *, void *);
+bool ck_array_remove(ck_array_t *, void *);
+void ck_array_deinit(ck_array_t *, bool);
+
+CK_CC_INLINE static unsigned int
+ck_array_length(struct ck_array *array)
+{
+ struct _ck_array *a = ck_pr_load_ptr(&array->active);
+
+ ck_pr_fence_load();
+ return ck_pr_load_uint(&a->n_committed);
+}
+
+CK_CC_INLINE static void *
+ck_array_buffer(struct ck_array *array, unsigned int *length)
+{
+ struct _ck_array *a = ck_pr_load_ptr(&array->active);
+
+ ck_pr_fence_load();
+ *length = ck_pr_load_uint(&a->n_committed);
+ return a->values;
+}
+
+CK_CC_INLINE static bool
+ck_array_initialized(struct ck_array *array)
+{
+
+ return ck_pr_load_ptr(&array->active) != NULL;
+}
+
+#define CK_ARRAY_FOREACH(a, i, b) \
+ (i)->snapshot = ck_pr_load_ptr(&(a)->active); \
+ ck_pr_fence_load(); \
+ for (unsigned int _ck_i = 0; \
+ _ck_i < (a)->active->n_committed && \
+ ((*b) = (a)->active->values[_ck_i], 1); \
+ _ck_i++)
+
+#endif /* _CK_ARRAY_H */
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/include/ck_backoff.h
----------------------------------------------------------------------
diff --git a/lib/ck/include/ck_backoff.h b/lib/ck/include/ck_backoff.h
new file mode 100644
index 0000000..f43c564
--- /dev/null
+++ b/lib/ck/include/ck_backoff.h
@@ -0,0 +1,58 @@
+/*
+ * Copyright 2009-2014 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 AUTHOR 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 AUTHOR 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.
+ */
+
+#ifndef _CK_BACKOFF_H
+#define _CK_BACKOFF_H
+
+#include <ck_cc.h>
+
+#ifndef CK_BACKOFF_CEILING
+#define CK_BACKOFF_CEILING ((1 << 20) - 1)
+#endif
+
+#define CK_BACKOFF_INITIALIZER (1 << 9)
+
+typedef volatile unsigned int ck_backoff_t;
+
+/*
+ * This is a exponential back-off implementation.
+ */
+CK_CC_INLINE static void
+ck_backoff_eb(volatile unsigned int *c)
+{
+ volatile unsigned int i;
+ unsigned int ceiling;
+
+ ceiling = *c;
+
+ for (i = 0; i < ceiling; i++);
+
+ *c = ceiling <<= ceiling < CK_BACKOFF_CEILING;
+ return;
+}
+
+#endif /* _CK_BACKOFF_H */
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/include/ck_barrier.h
----------------------------------------------------------------------
diff --git a/lib/ck/include/ck_barrier.h b/lib/ck/include/ck_barrier.h
new file mode 100644
index 0000000..52d3973
--- /dev/null
+++ b/lib/ck/include/ck_barrier.h
@@ -0,0 +1,165 @@
+/*
+ * Copyright 2011-2014 Samy Al Bahra.
+ * Copyright 2011 David Joseph.
+ * 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 AUTHOR 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 AUTHOR 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.
+ */
+
+#ifndef _CK_BARRIER_H
+#define _CK_BARRIER_H
+
+#include <ck_spinlock.h>
+
+struct ck_barrier_centralized {
+ unsigned int value;
+ unsigned int sense;
+};
+typedef struct ck_barrier_centralized ck_barrier_centralized_t;
+
+struct ck_barrier_centralized_state {
+ unsigned int sense;
+};
+typedef struct ck_barrier_centralized_state ck_barrier_centralized_state_t;
+
+#define CK_BARRIER_CENTRALIZED_INITIALIZER {0, 0}
+#define CK_BARRIER_CENTRALIZED_STATE_INITIALIZER {0}
+
+void ck_barrier_centralized(ck_barrier_centralized_t *,
+ ck_barrier_centralized_state_t *, unsigned int);
+
+struct ck_barrier_combining_group {
+ unsigned int k;
+ unsigned int count;
+ unsigned int sense;
+ struct ck_barrier_combining_group *parent;
+ struct ck_barrier_combining_group *left;
+ struct ck_barrier_combining_group *right;
+ struct ck_barrier_combining_group *next;
+} CK_CC_CACHELINE;
+typedef struct ck_barrier_combining_group ck_barrier_combining_group_t;
+
+struct ck_barrier_combining_state {
+ unsigned int sense;
+};
+typedef struct ck_barrier_combining_state ck_barrier_combining_state_t;
+
+#define CK_BARRIER_COMBINING_STATE_INITIALIZER {~0}
+
+struct ck_barrier_combining {
+ struct ck_barrier_combining_group *root;
+ ck_spinlock_fas_t mutex;
+};
+typedef struct ck_barrier_combining ck_barrier_combining_t;
+
+void ck_barrier_combining_init(ck_barrier_combining_t *, ck_barrier_combining_group_t *);
+
+void ck_barrier_combining_group_init(ck_barrier_combining_t *,
+ ck_barrier_combining_group_t *, unsigned int);
+
+void ck_barrier_combining(ck_barrier_combining_t *,
+ ck_barrier_combining_group_t *,
+ ck_barrier_combining_state_t *);
+
+struct ck_barrier_dissemination_flag {
+ unsigned int tflag;
+ unsigned int *pflag;
+};
+typedef struct ck_barrier_dissemination_flag ck_barrier_dissemination_flag_t;
+
+struct ck_barrier_dissemination {
+ unsigned int nthr;
+ unsigned int size;
+ unsigned int tid;
+ struct ck_barrier_dissemination_flag *flags[2];
+};
+typedef struct ck_barrier_dissemination ck_barrier_dissemination_t;
+
+struct ck_barrier_dissemination_state {
+ int parity;
+ unsigned int sense;
+ unsigned int tid;
+};
+typedef struct ck_barrier_dissemination_state ck_barrier_dissemination_state_t;
+
+void ck_barrier_dissemination_init(ck_barrier_dissemination_t *,
+ ck_barrier_dissemination_flag_t **, unsigned int);
+
+void ck_barrier_dissemination_subscribe(ck_barrier_dissemination_t *,
+ ck_barrier_dissemination_state_t *);
+
+unsigned int ck_barrier_dissemination_size(unsigned int);
+
+void ck_barrier_dissemination(ck_barrier_dissemination_t *,
+ ck_barrier_dissemination_state_t *);
+
+struct ck_barrier_tournament_round {
+ int role;
+ unsigned int *opponent;
+ unsigned int flag;
+};
+typedef struct ck_barrier_tournament_round ck_barrier_tournament_round_t;
+
+struct ck_barrier_tournament {
+ unsigned int tid;
+ unsigned int size;
+ struct ck_barrier_tournament_round **rounds;
+};
+typedef struct ck_barrier_tournament ck_barrier_tournament_t;
+
+struct ck_barrier_tournament_state {
+ unsigned int sense;
+ unsigned int vpid;
+};
+typedef struct ck_barrier_tournament_state ck_barrier_tournament_state_t;
+
+void ck_barrier_tournament_subscribe(ck_barrier_tournament_t *,
+ ck_barrier_tournament_state_t *);
+void ck_barrier_tournament_init(ck_barrier_tournament_t *,
+ ck_barrier_tournament_round_t **,
+ unsigned int);
+unsigned int ck_barrier_tournament_size(unsigned int);
+void ck_barrier_tournament(ck_barrier_tournament_t *, ck_barrier_tournament_state_t *);
+
+struct ck_barrier_mcs {
+ unsigned int tid;
+ unsigned int *children[2];
+ unsigned int childnotready[4];
+ unsigned int dummy;
+ unsigned int havechild[4];
+ unsigned int *parent;
+ unsigned int parentsense;
+};
+typedef struct ck_barrier_mcs ck_barrier_mcs_t;
+
+struct ck_barrier_mcs_state {
+ unsigned int sense;
+ unsigned int vpid;
+};
+typedef struct ck_barrier_mcs_state ck_barrier_mcs_state_t;
+
+void ck_barrier_mcs_init(ck_barrier_mcs_t *, unsigned int);
+void ck_barrier_mcs_subscribe(ck_barrier_mcs_t *, ck_barrier_mcs_state_t *);
+void ck_barrier_mcs(ck_barrier_mcs_t *, ck_barrier_mcs_state_t *);
+
+#endif /* _CK_BARRIER_H */
+
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/f098175e/lib/ck/include/ck_bitmap.h
----------------------------------------------------------------------
diff --git a/lib/ck/include/ck_bitmap.h b/lib/ck/include/ck_bitmap.h
new file mode 100644
index 0000000..3c0105e
--- /dev/null
+++ b/lib/ck/include/ck_bitmap.h
@@ -0,0 +1,491 @@
+/*
+ * Copyright 2012-2014 Samy Al Bahra.
+ * Copyright 2012-2014 AppNexus, Inc.
+ * Copyright 2014 Paul Khuong.
+ * 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 AUTHOR 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 AUTHOR 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.
+ */
+
+#ifndef _CK_BITMAP_H
+#define _CK_BITMAP_H
+
+#include <ck_cc.h>
+#include <ck_limits.h>
+#include <ck_pr.h>
+#include <ck_stdint.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <string.h>
+
+#if !defined(CK_F_PR_LOAD_UINT) || !defined(CK_F_PR_STORE_UINT) || \
+ !defined(CK_F_PR_AND_UINT) || !defined(CK_F_PR_OR_UINT) || \
+ !defined(CK_F_CC_CTZ)
+#error "ck_bitmap is not supported on your platform."
+#endif
+
+#define CK_BITMAP_BLOCK (sizeof(unsigned int) * CHAR_BIT)
+#define CK_BITMAP_BIT(i) (1U << ((i) % CK_BITMAP_BLOCK))
+#define CK_BITMAP_PTR(x, i) ((x) + ((i) / CK_BITMAP_BLOCK))
+#define CK_BITMAP_BLOCKS(n) (((n) + CK_BITMAP_BLOCK - 1) / CK_BITMAP_BLOCK)
+
+#define CK_BITMAP_INSTANCE(n_entries) \
+ union { \
+ struct { \
+ unsigned int n_bits; \
+ unsigned int map[CK_BITMAP_BLOCKS(n_entries)]; \
+ } content; \
+ struct ck_bitmap bitmap; \
+ }
+
+#define CK_BITMAP_ITERATOR_INIT(a, b) \
+ ck_bitmap_iterator_init((a), &(b)->bitmap)
+
+#define CK_BITMAP_INIT(a, b, c) \
+ ck_bitmap_init(&(a)->bitmap, (b), (c))
+
+#define CK_BITMAP_NEXT(a, b, c) \
+ ck_bitmap_next(&(a)->bitmap, (b), (c))
+
+#define CK_BITMAP_SET(a, b) \
+ ck_bitmap_set(&(a)->bitmap, (b))
+
+#define CK_BITMAP_RESET(a, b) \
+ ck_bitmap_reset(&(a)->bitmap, (b))
+
+#define CK_BITMAP_TEST(a, b) \
+ ck_bitmap_test(&(a)->bitmap, (b))
+
+#define CK_BITMAP_UNION(a, b) \
+ ck_bitmap_union(&(a)->bitmap, &(b)->bitmap)
+
+#define CK_BITMAP_INTERSECTION(a, b) \
+ ck_bitmap_intersection(&(a)->bitmap, &(b)->bitmap)
+
+#define CK_BITMAP_INTERSECTION_NEGATE(a, b) \
+ ck_bitmap_intersection_negate(&(a)->bitmap, &(b)->bitmap)
+
+#define CK_BITMAP_CLEAR(a) \
+ ck_bitmap_clear(&(a)->bitmap)
+
+#define CK_BITMAP_EMPTY(a, b) \
+ ck_bitmap_empty(&(a)->bitmap, b)
+
+#define CK_BITMAP_FULL(a, b) \
+ ck_bitmap_full(&(a)->bitmap, b)
+
+#define CK_BITMAP_COUNT(a, b) \
+ ck_bitmap_count(&(a)->bitmap, b)
+
+#define CK_BITMAP_COUNT_INTERSECT(a, b, c) \
+ ck_bitmap_count_intersect(&(a)->bitmap, b, c)
+
+#define CK_BITMAP_BITS(a) \
+ ck_bitmap_bits(&(a)->bitmap)
+
+#define CK_BITMAP_BUFFER(a) \
+ ck_bitmap_buffer(&(a)->bitmap)
+
+#define CK_BITMAP(a) \
+ (&(a)->bitmap)
+
+struct ck_bitmap {
+ unsigned int n_bits;
+ unsigned int map[];
+};
+typedef struct ck_bitmap ck_bitmap_t;
+
+struct ck_bitmap_iterator {
+ unsigned int cache;
+ unsigned int n_block;
+ unsigned int n_limit;
+};
+typedef struct ck_bitmap_iterator ck_bitmap_iterator_t;
+
+CK_CC_INLINE static unsigned int
+ck_bitmap_base(unsigned int n_bits)
+{
+
+ return CK_BITMAP_BLOCKS(n_bits) * sizeof(unsigned int);
+}
+
+/*
+ * Returns the required number of bytes for a ck_bitmap_t object supporting the
+ * specified number of bits.
+ */
+CK_CC_INLINE static unsigned int
+ck_bitmap_size(unsigned int n_bits)
+{
+
+ return ck_bitmap_base(n_bits) + sizeof(struct ck_bitmap);
+}
+
+/*
+ * Returns total number of bits in specified bitmap.
+ */
+CK_CC_INLINE static unsigned int
+ck_bitmap_bits(const struct ck_bitmap *bitmap)
+{
+
+ return bitmap->n_bits;
+}
+
+/*
+ * Returns a pointer to the bit buffer associated
+ * with the specified bitmap.
+ */
+CK_CC_INLINE static void *
+ck_bitmap_buffer(struct ck_bitmap *bitmap)
+{
+
+ return bitmap->map;
+}
+
+/*
+ * Sets the bit at the offset specified in the second argument.
+ */
+CK_CC_INLINE static void
+ck_bitmap_set(struct ck_bitmap *bitmap, unsigned int n)
+{
+
+ ck_pr_or_uint(CK_BITMAP_PTR(bitmap->map, n), CK_BITMAP_BIT(n));
+ return;
+}
+
+/*
+ * Resets the bit at the offset specified in the second argument.
+ */
+CK_CC_INLINE static void
+ck_bitmap_reset(struct ck_bitmap *bitmap, unsigned int n)
+{
+
+ ck_pr_and_uint(CK_BITMAP_PTR(bitmap->map, n), ~CK_BITMAP_BIT(n));
+ return;
+}
+
+/*
+ * Determines whether the bit at offset specified in the
+ * second argument is set.
+ */
+CK_CC_INLINE static bool
+ck_bitmap_test(const struct ck_bitmap *bitmap, unsigned int n)
+{
+ unsigned int block;
+
+ block = ck_pr_load_uint(CK_BITMAP_PTR(bitmap->map, n));
+ return block & CK_BITMAP_BIT(n);
+}
+
+/*
+ * Combines bits from second bitmap into the first bitmap. This is not a
+ * linearized operation with respect to the complete bitmap.
+ */
+CK_CC_INLINE static void
+ck_bitmap_union(struct ck_bitmap *dst, const struct ck_bitmap *src)
+{
+ unsigned int n;
+ unsigned int n_buckets = dst->n_bits;
+
+ if (src->n_bits < dst->n_bits)
+ n_buckets = src->n_bits;
+
+ n_buckets = CK_BITMAP_BLOCKS(n_buckets);
+ for (n = 0; n < n_buckets; n++) {
+ ck_pr_or_uint(&dst->map[n],
+ ck_pr_load_uint(&src->map[n]));
+ }
+
+ return;
+}
+
+/*
+ * Intersects bits from second bitmap into the first bitmap. This is
+ * not a linearized operation with respect to the complete bitmap.
+ * Any trailing bit in dst is cleared.
+ */
+CK_CC_INLINE static void
+ck_bitmap_intersection(struct ck_bitmap *dst, const struct ck_bitmap *src)
+{
+ unsigned int n;
+ unsigned int n_buckets = dst->n_bits;
+ unsigned int n_intersect = n_buckets;
+
+ if (src->n_bits < n_intersect)
+ n_intersect = src->n_bits;
+
+ n_buckets = CK_BITMAP_BLOCKS(n_buckets);
+ n_intersect = CK_BITMAP_BLOCKS(n_intersect);
+ for (n = 0; n < n_intersect; n++) {
+ ck_pr_and_uint(&dst->map[n],
+ ck_pr_load_uint(&src->map[n]));
+ }
+
+ for (; n < n_buckets; n++)
+ ck_pr_store_uint(&dst->map[n], 0);
+
+ return;
+}
+
+/*
+ * Intersects the complement of bits from second bitmap into the first
+ * bitmap. This is not a linearized operation with respect to the
+ * complete bitmap. Any trailing bit in dst is left as is.
+ */
+CK_CC_INLINE static void
+ck_bitmap_intersection_negate(struct ck_bitmap *dst, const struct ck_bitmap *src)
+{
+ unsigned int n;
+ unsigned int n_intersect = dst->n_bits;
+
+ if (src->n_bits < n_intersect)
+ n_intersect = src->n_bits;
+
+ n_intersect = CK_BITMAP_BLOCKS(n_intersect);
+ for (n = 0; n < n_intersect; n++) {
+ ck_pr_and_uint(&dst->map[n],
+ (~ck_pr_load_uint(&src->map[n])));
+ }
+
+ return;
+}
+
+/*
+ * Resets all bits in the provided bitmap. This is not a linearized
+ * operation in ck_bitmap.
+ */
+CK_CC_INLINE static void
+ck_bitmap_clear(struct ck_bitmap *bitmap)
+{
+ unsigned int n_buckets = ck_bitmap_base(bitmap->n_bits) / sizeof(unsigned int);
+ unsigned int i;
+
+ for (i = 0; i < n_buckets; i++)
+ ck_pr_store_uint(&bitmap->map[i], 0);
+
+ return;
+}
+
+/*
+ * Returns true if the first limit bits in bitmap are cleared. If
+ * limit is greater than the bitmap size, limit is truncated to that
+ * size.
+ */
+CK_CC_INLINE static bool
+ck_bitmap_empty(const ck_bitmap_t *bitmap, unsigned int limit)
+{
+ unsigned int i, words, slop;
+
+ if (limit > bitmap->n_bits)
+ limit = bitmap->n_bits;
+
+ words = limit / CK_BITMAP_BLOCK;
+ slop = limit % CK_BITMAP_BLOCK;
+ for (i = 0; i < words; i++) {
+ if (ck_pr_load_uint(&bitmap->map[i]) != 0) {
+ return false;
+ }
+ }
+
+ if (slop > 0) {
+ unsigned int word;
+
+ word = ck_pr_load_uint(&bitmap->map[i]);
+ if ((word & ((1U << slop) - 1)) != 0)
+ return false;
+ }
+
+ return true;
+}
+
+/*
+ * Returns true if the first limit bits in bitmap are set. If limit
+ * is greater than the bitmap size, limit is truncated to that size.
+ */
+CK_CC_UNUSED static bool
+ck_bitmap_full(const ck_bitmap_t *bitmap, unsigned int limit)
+{
+ unsigned int i, slop, words;
+
+ if (limit > bitmap->n_bits) {
+ limit = bitmap->n_bits;
+ }
+
+ words = limit / CK_BITMAP_BLOCK;
+ slop = limit % CK_BITMAP_BLOCK;
+ for (i = 0; i < words; i++) {
+ if (ck_pr_load_uint(&bitmap->map[i]) != -1U)
+ return false;
+ }
+
+ if (slop > 0) {
+ unsigned int word;
+
+ word = ~ck_pr_load_uint(&bitmap->map[i]);
+ if ((word & ((1U << slop) - 1)) != 0)
+ return false;
+ }
+ return true;
+}
+
+/*
+ * Returns the number of set bit in bitmap, upto (and excluding)
+ * limit. If limit is greater than the bitmap size, it is truncated
+ * to that size.
+ */
+CK_CC_INLINE static unsigned int
+ck_bitmap_count(const ck_bitmap_t *bitmap, unsigned int limit)
+{
+ unsigned int count, i, slop, words;
+
+ if (limit > bitmap->n_bits)
+ limit = bitmap->n_bits;
+
+ words = limit / CK_BITMAP_BLOCK;
+ slop = limit % CK_BITMAP_BLOCK;
+ for (i = 0, count = 0; i < words; i++)
+ count += ck_cc_popcount(ck_pr_load_uint(&bitmap->map[i]));
+
+ if (slop > 0) {
+ unsigned int word;
+
+ word = ck_pr_load_uint(&bitmap->map[i]);
+ count += ck_cc_popcount(word & ((1U << slop) - 1));
+ }
+ return count;
+}
+
+/*
+ * Returns the number of set bit in the intersection of two bitmaps,
+ * upto (and exclusing) limit. If limit is greater than either bitmap
+ * size, it is truncated to the smallest.
+ */
+CK_CC_INLINE static unsigned int
+ck_bitmap_count_intersect(const ck_bitmap_t *x, const ck_bitmap_t *y, unsigned int limit)
+{
+ unsigned int count, i, slop, words;
+
+ if (limit > x->n_bits)
+ limit = x->n_bits;
+
+ if (limit > y->n_bits)
+ limit = y->n_bits;
+
+ words = limit / CK_BITMAP_BLOCK;
+ slop = limit % CK_BITMAP_BLOCK;
+ for (i = 0, count = 0; i < words; i++) {
+ unsigned int xi, yi;
+
+ xi = ck_pr_load_uint(&x->map[i]);
+ yi = ck_pr_load_uint(&y->map[i]);
+ count += ck_cc_popcount(xi & yi);
+ }
+
+ if (slop > 0) {
+ unsigned int word, xi, yi;
+
+ xi = ck_pr_load_uint(&x->map[i]);
+ yi = ck_pr_load_uint(&y->map[i]);
+ word = xi & yi;
+ count += ck_cc_popcount(word & ((1U << slop) - 1));
+ }
+ return count;
+}
+
+/*
+ * Initializes a ck_bitmap pointing to a region of memory with
+ * ck_bitmap_size(n_bits) bytes. Third argument determines whether
+ * default bit value is 1 (true) or 0 (false).
+ */
+CK_CC_INLINE static void
+ck_bitmap_init(struct ck_bitmap *bitmap,
+ unsigned int n_bits,
+ bool set)
+{
+ unsigned int base = ck_bitmap_base(n_bits);
+
+ bitmap->n_bits = n_bits;
+ memset(bitmap->map, -(int)set, base);
+
+ if (set == true) {
+ unsigned int b = n_bits % CK_BITMAP_BLOCK;
+
+ if (b == 0)
+ return;
+
+ *CK_BITMAP_PTR(bitmap->map, n_bits - 1) &= (1U << b) - 1U;
+ }
+
+ return;
+}
+
+/*
+ * Initialize iterator for use with provided bitmap.
+ */
+CK_CC_INLINE static void
+ck_bitmap_iterator_init(struct ck_bitmap_iterator *i, const struct ck_bitmap *bitmap)
+{
+
+ i->n_block = 0;
+ i->n_limit = CK_BITMAP_BLOCKS(bitmap->n_bits);
+ if (i->n_limit > 0) {
+ i->cache = ck_pr_load_uint(&bitmap->map[0]);
+ } else {
+ i->cache = 0;
+ }
+ return;
+}
+
+/*
+ * Iterate to next bit.
+ */
+CK_CC_INLINE static bool
+ck_bitmap_next(const struct ck_bitmap *bitmap,
+ struct ck_bitmap_iterator *i,
+ unsigned int *bit)
+{
+ unsigned int cache = i->cache;
+ unsigned int n_block = i->n_block;
+ unsigned int n_limit = i->n_limit;
+
+ if (cache == 0) {
+ if (n_block >= n_limit)
+ return false;
+
+ for (n_block++; n_block < n_limit; n_block++) {
+ cache = ck_pr_load_uint(&bitmap->map[n_block]);
+ if (cache != 0)
+ goto non_zero;
+ }
+
+ i->cache = 0;
+ i->n_block = n_block;
+ return false;
+ }
+
+non_zero:
+ *bit = CK_BITMAP_BLOCK * n_block + ck_cc_ctz(cache);
+ i->cache = cache & (cache - 1);
+ i->n_block = n_block;
+ return true;
+}
+
+#endif /* _CK_BITMAP_H */