include/ck_pflock.h

   1 /*
   2  * Copyright 2013 John Wittrock.
   3  * Copyright 2013-2015 Samy Al Bahra.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  */
  27
  28 #ifndef CK_PFLOCK_H
  29 #define CK_PFLOCK_H
  30
  31 /*
  32  * This is an implementation of phase-fair locks derived from the work
  33  * described in:
  34  *    Brandenburg, B. and Anderson, J. 2010. Spin-Based
  35  *    Reader-Writer Synchronization for Multiprocessor Real-Time Systems
  36  */
  37
  38 #include <ck_cc.h>
  39 #include <ck_pr.h>
  40
  41 struct ck_pflock {
  42         uint32_t rin;
  43         uint32_t rout;
  44         uint32_t win;
  45         uint32_t wout;
  46 };
  47 typedef struct ck_pflock ck_pflock_t;
  48
  49 #define CK_PFLOCK_LSB   0xFFFFFFF0
  50 #define CK_PFLOCK_RINC  0x100           /* Reader increment value. */
  51 #define CK_PFLOCK_WBITS 0x3             /* Writer bits in reader. */
  52 #define CK_PFLOCK_PRES  0x2             /* Writer present bit. */
  53 #define CK_PFLOCK_PHID  0x1             /* Phase ID bit. */
  54
  55 #define CK_PFLOCK_INITIALIZER {0, 0, 0, 0}
  56
  57 CK_CC_INLINE static void
  58 ck_pflock_init(struct ck_pflock *pf)
  59 {
  60
  61         pf->rin = 0;
  62         pf->rout = 0;
  63         pf->win = 0;
  64         pf->wout = 0;
  65         ck_pr_barrier();
  66
  67         return;
  68 }
  69
  70 CK_CC_INLINE static void
  71 ck_pflock_write_unlock(ck_pflock_t *pf)
  72 {
  73
  74         ck_pr_fence_unlock();
  75
  76         /* Migrate from write phase to read phase. */
  77         ck_pr_and_32(&pf->rin, CK_PFLOCK_LSB);
  78
  79         /* Allow other writers to continue. */
  80         ck_pr_faa_32(&pf->wout, 1);
  81         return;
  82 }
  83
  84 CK_CC_INLINE static void
  85 ck_pflock_write_lock(ck_pflock_t *pf)
  86 {
  87         uint32_t ticket;
  88
  89         /* Acquire ownership of write-phase. */
  90         ticket = ck_pr_faa_32(&pf->win, 1);
  91         while (ck_pr_load_32(&pf->wout) != ticket)
  92                 ck_pr_stall();
  93
  94         /*
  95          * Acquire ticket on read-side in order to allow them
  96          * to flush. Indicates to any incoming reader that a
  97          * write-phase is pending.
  98          */
  99         ticket = ck_pr_faa_32(&pf->rin,
 100             (ticket & CK_PFLOCK_PHID) | CK_PFLOCK_PRES);
 101
 102         /* Wait for any pending readers to flush. */
 103         while (ck_pr_load_32(&pf->rout) != ticket)
 104                 ck_pr_stall();
 105
 106         ck_pr_fence_lock();
 107         return;
 108 }
 109
 110 CK_CC_INLINE static void
 111 ck_pflock_read_unlock(ck_pflock_t *pf)
 112 {
 113
 114         ck_pr_fence_unlock();
 115         ck_pr_faa_32(&pf->rout, CK_PFLOCK_RINC);
 116         return;
 117 }
 118
 119 CK_CC_INLINE static void
 120 ck_pflock_read_lock(ck_pflock_t *pf)
 121 {
 122         uint32_t w;
 123
 124         /*
 125          * If no writer is present, then the operation has completed
 126          * successfully.
 127          */
 128         w = ck_pr_faa_32(&pf->rin, CK_PFLOCK_RINC) & CK_PFLOCK_WBITS;
 129         if (w == 0)
 130                 goto leave;
 131
 132         /* Wait for current write phase to complete. */
 133         while ((ck_pr_load_32(&pf->rin) & CK_PFLOCK_WBITS) == w)
 134                 ck_pr_stall();
 135
 136 leave:
 137         /* Acquire semantics with respect to readers. */
 138         ck_pr_fence_lock();
 139         return;
 140 }
 141
 142 #endif /* CK_PFLOCK_H */