Branch data     Line data    Source code

       1                 :            : /* SPDX-License-Identifier: BSD-3-Clause
       2                 :            :  * Copyright(c) 2021 Microsoft Corp.
       3                 :            :  * All rights reserved.
       4                 :            :  *
       5                 :            :  * Derived from Concurrency Kit
       6                 :            :  * Copyright 2011-2015 Samy Al Bahra.
       7                 :            :  */
       8                 :            : 
       9                 :            : #ifndef _RTE_PFLOCK_H_
      10                 :            : #define _RTE_PFLOCK_H_
      11                 :            : 
      12                 :            : /**
      13                 :            :  * @file
      14                 :            :  *
      15                 :            :  * Phase-fair locks
      16                 :            :  *
      17                 :            :  * This file defines an API for phase-fair reader writer locks,
      18                 :            :  * which is a variant of typical reader-writer locks that prevent
      19                 :            :  * starvation. In this type of lock, readers and writers alternate.
      20                 :            :  * This significantly reduces the worst-case blocking for readers and writers.
      21                 :            :  *
      22                 :            :  * This is an implementation derived from FreeBSD
      23                 :            :  * based on the work described in:
      24                 :            :  *    Brandenburg, B. and Anderson, J. 2010. Spin-Based
      25                 :            :  *    Reader-Writer Synchronization for Multiprocessor Real-Time Systems
      26                 :            :  *
      27                 :            :  * All locks must be initialised before use, and only initialised once.
      28                 :            :  */
      29                 :            : 
      30                 :            : #include <rte_common.h>
      31                 :            : #include <rte_pause.h>
      32                 :            : #include <rte_stdatomic.h>
      33                 :            : 
      34                 :            : #ifdef __cplusplus
      35                 :            : extern "C" {
      36                 :            : #endif
      37                 :            : 
      38                 :            : /**
      39                 :            :  * The rte_pflock_t type.
      40                 :            :  */
      41                 :            : struct rte_pflock {
      42                 :            :         struct {
      43                 :            :                 RTE_ATOMIC(uint16_t) in;
      44                 :            :                 RTE_ATOMIC(uint16_t) out;
      45                 :            :         } rd, wr;
      46                 :            : };
      47                 :            : typedef struct rte_pflock rte_pflock_t;
      48                 :            : 
      49                 :            : /*
      50                 :            :  * Allocation of bits to reader
      51                 :            :  *
      52                 :            :  * 15                 4 3 2 1 0
      53                 :            :  * +-------------------+---+-+-+
      54                 :            :  * | rin: reads issued |x|x| | |
      55                 :            :  * +-------------------+---+-+-+
      56                 :            :  *                          ^ ^
      57                 :            :  *                          | |
      58                 :            :  * PRES: writer present ----/ |
      59                 :            :  * PHID: writer phase id -----/
      60                 :            :  *
      61                 :            :  * 15                4 3 2 1 0
      62                 :            :  * +------------------+------+
      63                 :            :  * |rout:read complete|unused|
      64                 :            :  * +------------------+------+
      65                 :            :  *
      66                 :            :  * The maximum number of readers is 4095
      67                 :            :  */
      68                 :            : 
      69                 :            : /* Constants used to map the bits in reader counter */
      70                 :            : #define RTE_PFLOCK_WBITS 0x3    /* Writer bits in reader. */
      71                 :            : #define RTE_PFLOCK_PRES  0x2    /* Writer present bit. */
      72                 :            : #define RTE_PFLOCK_PHID  0x1    /* Phase ID bit. */
      73                 :            : #define RTE_PFLOCK_LSB   0xFFF0 /* reader bits. */
      74                 :            : #define RTE_PFLOCK_RINC  0x10   /* Reader increment. */
      75                 :            : 
      76                 :            : /**
      77                 :            :  * A static pflock initializer.
      78                 :            :  */
      79                 :            : #define RTE_PFLOCK_INITIALIZER {  }
      80                 :            : 
      81                 :            : /**
      82                 :            :  * Initialize the pflock to an unlocked state.
      83                 :            :  *
      84                 :            :  * @param pf
      85                 :            :  *   A pointer to the pflock.
      86                 :            :  */
      87                 :            : static inline void
      88                 :            : rte_pflock_init(struct rte_pflock *pf)
      89                 :            : {
      90                 :        129 :         pf->rd.in = 0;
      91                 :        129 :         pf->rd.out = 0;
      92                 :        129 :         pf->wr.in = 0;
      93                 :        129 :         pf->wr.out = 0;
      94                 :            : }
      95                 :            : 
      96                 :            : /**
      97                 :            :  * Take a pflock for read.
      98                 :            :  *
      99                 :            :  * @param pf
     100                 :            :  *   A pointer to a pflock structure.
     101                 :            :  */
     102                 :            : static inline void
     103                 :      29999 : rte_pflock_read_lock(rte_pflock_t *pf)
     104                 :            : {
     105                 :            :         uint16_t w;
     106                 :            : 
     107                 :            :         /*
     108                 :            :          * If no writer is present, then the operation has completed
     109                 :            :          * successfully.
     110                 :            :          */
     111                 :      29999 :         w = rte_atomic_fetch_add_explicit(&pf->rd.in, RTE_PFLOCK_RINC, rte_memory_order_acquire)
     112                 :            :                 & RTE_PFLOCK_WBITS;
     113         [ +  + ]:      29999 :         if (w == 0)
     114                 :            :                 return;
     115                 :            : 
     116                 :            :         /* Wait for current write phase to complete. */
     117         [ +  + ]:     117372 :         RTE_WAIT_UNTIL_MASKED(&pf->rd.in, RTE_PFLOCK_WBITS, !=, w, rte_memory_order_acquire);
     118                 :            : }
     119                 :            : 
     120                 :            : /**
     121                 :            :  * Release a pflock locked for reading.
     122                 :            :  *
     123                 :            :  * @param pf
     124                 :            :  *   A pointer to the pflock structure.
     125                 :            :  */
     126                 :            : static inline void
     127                 :            : rte_pflock_read_unlock(rte_pflock_t *pf)
     128                 :            : {
     129                 :      29653 :         rte_atomic_fetch_add_explicit(&pf->rd.out, RTE_PFLOCK_RINC, rte_memory_order_release);
     130                 :      29652 : }
     131                 :            : 
     132                 :            : /**
     133                 :            :  * Take the pflock for write.
     134                 :            :  *
     135                 :            :  * @param pf
     136                 :            :  *   A pointer to the pflock structure.
     137                 :            :  */
     138                 :            : static inline void
     139                 :      29698 : rte_pflock_write_lock(rte_pflock_t *pf)
     140                 :            : {
     141                 :            :         uint16_t ticket, w;
     142                 :            : 
     143                 :            :         /* Acquire ownership of write-phase.
     144                 :            :          * This is same as rte_ticketlock_lock().
     145                 :            :          */
     146                 :      29698 :         ticket = rte_atomic_fetch_add_explicit(&pf->wr.in, 1, rte_memory_order_relaxed);
     147                 :      29698 :         rte_wait_until_equal_16((uint16_t *)(uintptr_t)&pf->wr.out, ticket,
     148                 :            :                 rte_memory_order_acquire);
     149                 :            : 
     150                 :            :         /*
     151                 :            :          * Acquire ticket on read-side in order to allow them
     152                 :            :          * to flush. Indicates to any incoming reader that a
     153                 :            :          * write-phase is pending.
     154                 :            :          *
     155                 :            :          * The load of rd.out in wait loop could be executed
     156                 :            :          * speculatively.
     157                 :            :          */
     158                 :      30005 :         w = RTE_PFLOCK_PRES | (ticket & RTE_PFLOCK_PHID);
     159                 :      30005 :         ticket = rte_atomic_fetch_add_explicit(&pf->rd.in, w, rte_memory_order_relaxed);
     160                 :            : 
     161                 :            :         /* Wait for any pending readers to flush. */
     162                 :      30005 :         rte_wait_until_equal_16((uint16_t *)(uintptr_t)&pf->rd.out, ticket,
     163                 :            :                 rte_memory_order_acquire);
     164                 :      30005 : }
     165                 :            : 
     166                 :            : /**
     167                 :            :  * Release a pflock held for writing.
     168                 :            :  *
     169                 :            :  * @param pf
     170                 :            :  *   A pointer to a pflock structure.
     171                 :            :  */
     172                 :            : static inline void
     173                 :      30005 : rte_pflock_write_unlock(rte_pflock_t *pf)
     174                 :            : {
     175                 :            :         /* Migrate from write phase to read phase. */
     176                 :      30005 :         rte_atomic_fetch_and_explicit(&pf->rd.in, RTE_PFLOCK_LSB, rte_memory_order_release);
     177                 :            : 
     178                 :            :         /* Allow other writers to continue. */
     179                 :      30005 :         rte_atomic_fetch_add_explicit(&pf->wr.out, 1, rte_memory_order_release);
     180                 :      30005 : }
     181                 :            : 
     182                 :            : #ifdef __cplusplus
     183                 :            : }
     184                 :            : #endif
     185                 :            : 
     186                 :            : #endif /* RTE_PFLOCK_H */