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 */