Changeset 8e3ed06 in mainline


Ignore:
Timestamp:
2012-07-29T17:28:45Z (12 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
5b03a72
Parents:
d99fac9
Message:

rcu: Allowed inlining of the RCU read side.

Location:
kernel
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/include/adt/cht.h

    rd99fac9 r8e3ed06  
    3838#include <stdint.h>
    3939#include <adt/list.h>
    40 #include <synch/rcu.h>
     40#include <synch/rcu_types.h>
    4141#include <macros.h>
    4242#include <synch/workqueue.h>

  • kernel/generic/include/cpu.h

    rd99fac9 r8e3ed06  
    3838#include <mm/tlb.h>
    3939#include <synch/spinlock.h>
    40 #include <synch/rcu.h>
     40#include <synch/rcu_types.h>
    4141#include <proc/scheduler.h>
    4242#include <arch/cpu.h>

  • kernel/generic/include/proc/thread.h

    rd99fac9 r8e3ed06  
    4141#include <cpu.h>
    4242#include <synch/spinlock.h>
    43 #include <synch/rcu.h>
     43#include <synch/rcu_types.h>
    4444#include <adt/avl.h>
    4545#include <mm/slab.h>

  • kernel/generic/include/synch/rcu.h

    rd99fac9 r8e3ed06  
    3636#define KERN_RCU_H_
    3737
    38 #include <adt/list.h>
    39 #include <synch/semaphore.h>
     38#include <synch/rcu_types.h>
    4039#include <compiler/barrier.h>
    4140
    4241
    43 /* Fwd decl. */
    44 struct thread;
    45 struct rcu_item;
    46 
    47 /** Grace period number typedef. */
    48 typedef uint64_t rcu_gp_t;
    49 
    50 /** RCU callback type. The passed rcu_item_t maybe freed. */
    51 typedef void (*rcu_func_t)(struct rcu_item *rcu_item);
    52 
    53 typedef struct rcu_item {
    54         rcu_func_t func;
    55         struct rcu_item *next;
    56 } rcu_item_t;
    57 
    58 
    59 /** RCU related per-cpu data. */
    60 typedef struct rcu_cpu_data {
    61         /** The cpu recorded a quiescent state last time during this grace period */
    62         rcu_gp_t last_seen_gp;
    63        
    64         /** Pointer to the currently used nesting count (THREAD's or CPU's). */
    65         size_t *pnesting_cnt;
    66         /** Temporary nesting count if THREAD is NULL, eg in scheduler(). */
    67         size_t tmp_nesting_cnt;
    68 
    69         /** Callbacks to invoke once the current grace period ends, ie cur_cbs_gp.
    70          * Accessed by the local reclaimer only.
    71          */
    72         rcu_item_t *cur_cbs;
    73         /** Number of callbacks in cur_cbs. */
    74         size_t cur_cbs_cnt;
    75         /** Callbacks to invoke once the next grace period ends, ie next_cbs_gp.
    76          * Accessed by the local reclaimer only.
    77          */
    78         rcu_item_t *next_cbs;
    79         /** Number of callbacks in next_cbs. */
    80         size_t next_cbs_cnt;
    81         /** New callbacks are place at the end of this list. */
    82         rcu_item_t *arriving_cbs;
    83         /** Tail of arriving_cbs list. Disable interrupts to access. */
    84         rcu_item_t **parriving_cbs_tail;
    85         /** Number of callbacks currently in arriving_cbs.
    86          * Disable interrupts to access.
    87          */
    88         size_t arriving_cbs_cnt;
    89 
    90         /** At the end of this grace period callbacks in cur_cbs will be invoked.*/
    91         rcu_gp_t cur_cbs_gp;
    92         /** At the end of this grace period callbacks in next_cbs will be invoked.
    93          *
    94          * Should be the next grace period but it allows the reclaimer to
    95          * notice if it missed a grace period end announcement. In that
    96          * case it can execute next_cbs without waiting for another GP.
    97          *
    98          * Invariant: next_cbs_gp >= cur_cbs_gp
    99          */
    100         rcu_gp_t next_cbs_gp;
    101        
    102         /** This cpu has not yet passed a quiescent state and it is delaying the
    103          * detector. Once it reaches a QS it must sema_up(rcu.remaining_readers).
    104          */
    105         bool is_delaying_gp;
    106        
    107         /** Positive if there are callbacks pending in arriving_cbs. */
    108         semaphore_t arrived_flag;
    109        
    110         /** The reclaimer should expedite GPs for cbs in arriving_cbs. */
    111         bool expedite_arriving;
    112        
    113         /** Protected by global rcu.barrier_mtx. */
    114         rcu_item_t barrier_item;
    115        
    116         /** Interruptable attached reclaimer thread. */
    117         struct thread *reclaimer_thr;
    118        
    119         /* Some statistics. */
    120         size_t stat_max_cbs;
    121         size_t stat_avg_cbs;
    122         size_t stat_missed_gps;
    123         size_t stat_missed_gp_in_wait;
    124         size_t stat_max_slice_cbs;
    125         size_t last_arriving_cnt;
    126 } rcu_cpu_data_t;
    127 
    128 
    129 /** RCU related per-thread data. */
    130 typedef struct rcu_thread_data {
    131         /** The number of times an RCU reader section is nested.
    132          *
    133          * If positive, it is definitely executing reader code. If zero,
    134          * the thread might already be executing reader code thanks to
    135          * cpu instruction reordering.
    136          */
    137         size_t nesting_cnt;
    138        
    139         /** True if the thread was preempted in a reader section.
    140          *
    141          * The thread is place into rcu.cur_preempted or rcu.next_preempted
    142          * and must remove itself in rcu_read_unlock().
    143          *
    144          * Access with interrupts disabled.
    145          */
    146         bool was_preempted;
    147         /** Preempted threads link. Access with rcu.prempt_lock.*/
    148         link_t preempt_link;
    149 } rcu_thread_data_t;
    15042
    15143
    … …  
    20193#define rcu_access(ptr) ACCESS_ONCE(ptr)
    20294
    203 extern void rcu_read_lock(void);
    204 extern void rcu_read_unlock(void);
     95
     96
     97
     98#include <debug.h>
     99#include <preemption.h>
     100#include <cpu.h>
     101#include <proc/thread.h>
     102
     103
    205104extern bool rcu_read_locked(void);
    206105extern void rcu_synchronize(void);
    … …  
    224123extern void _rcu_synchronize(bool expedite);
    225124
     125
     126/* Fwd decl. required by the inlined implementation. Not part of public API. */
     127extern rcu_gp_t _rcu_cur_gp;
     128extern void _rcu_signal_read_unlock(void);
     129
     130
     131/** Unconditionally records a quiescent state for the local cpu. */
     132static inline void _rcu_record_qs(void)
     133{
     134        ASSERT(PREEMPTION_DISABLED || interrupts_disabled());
     135       
     136        /*
     137         * A new GP was started since the last time we passed a QS.
     138         * Notify the detector we have reached a new QS.
     139         */
     140        if (CPU->rcu.last_seen_gp != _rcu_cur_gp) {
     141                rcu_gp_t cur_gp = ACCESS_ONCE(_rcu_cur_gp);
     142                /*
     143                 * Contain memory accesses within a reader critical section.
     144                 * If we are in rcu_lock() it also makes changes prior to the
     145                 * start of the GP visible in the reader section.
     146                 */
     147                memory_barrier();
     148                /*
     149                 * Acknowledge we passed a QS since the beginning of rcu.cur_gp.
     150                 * Cache coherency will lazily transport the value to the
     151                 * detector while it sleeps in gp_sleep().
     152                 *
     153                 * Note that there is a theoretical possibility that we
     154                 * overwrite a more recent/greater last_seen_gp here with
     155                 * an older/smaller value. If this cpu is interrupted here
     156                 * while in rcu_lock() reader sections in the interrupt handler
     157                 * will update last_seen_gp to the same value as is currently
     158                 * in local cur_gp. However, if the cpu continues processing
     159                 * interrupts and the detector starts a new GP immediately,
     160                 * local interrupt handlers may update last_seen_gp again (ie
     161                 * properly ack the new GP) with a value greater than local cur_gp.
     162                 * Resetting last_seen_gp to a previous value here is however
     163                 * benign and we only have to remember that this reader may end up
     164                 * in cur_preempted even after the GP ends. That is why we
     165                 * append next_preempted to cur_preempted rather than overwriting
     166                 * it as if cur_preempted were empty.
     167                 */
     168                CPU->rcu.last_seen_gp = cur_gp;
     169        }
     170}
     171
     172/** Delimits the start of an RCU reader critical section.
     173 *
     174 * Reader sections may be nested and are preemptable. You must not
     175 * however block/sleep within reader sections.
     176 */
     177static inline void rcu_read_lock(void)
     178{
     179        ASSERT(CPU);
     180        preemption_disable();
     181
     182        /* Record a QS if not in a reader critical section. */
     183        if (0 == *CPU->rcu.pnesting_cnt)
     184                _rcu_record_qs();
     185
     186        ++(*CPU->rcu.pnesting_cnt);
     187
     188        preemption_enable();
     189}
     190
     191/** Delimits the end of an RCU reader critical section. */
     192static inline void rcu_read_unlock(void)
     193{
     194        ASSERT(CPU);
     195        preemption_disable();
     196       
     197        if (0 == --(*CPU->rcu.pnesting_cnt)) {
     198                _rcu_record_qs();
     199               
     200                /*
     201                 * The thread was preempted while in a critical section or
     202                 * the detector is eagerly waiting for this cpu's reader
     203                 * to finish.
     204                 *
     205                 * Note that THREAD may be 0 in scheduler() and not just during boot.
     206                 */
     207                if ((THREAD && THREAD->rcu.was_preempted) || CPU->rcu.is_delaying_gp) {
     208                        /* Rechecks with disabled interrupts. */
     209                        _rcu_signal_read_unlock();
     210                }
     211        }
     212
     213       
     214        preemption_enable();
     215}
     216
     217
    226218#endif
    227219

  • kernel/generic/src/synch/rcu.c

    rd99fac9 r8e3ed06  
    7171#define UINT32_MAX_HALF    2147483648U
    7272
     73/**
     74 * The current grace period number. Increases monotonically.
     75 * Lock rcu.gp_lock or rcu.preempt_lock to get a current value.
     76 */
     77rcu_gp_t _rcu_cur_gp;
    7378
    7479/** Global RCU data. */
    … …  
    97102        /** Number of consecutive grace periods to detect quickly and aggressively.*/
    98103        size_t req_expedited_cnt;
    99         /**
    100          * The current grace period number. Increases monotonically.
    101          * Lock gp_lock or preempt_lock to get a current value.
    102          */
    103         rcu_gp_t cur_gp;
    104104        /**
    105          * The number of the most recently completed grace period.
    106          * At most one behind cur_gp. If equal to cur_gp, a grace
    107          * period detection is not in progress and the detector
    108          * is idle.
     105         * The number of the most recently completed grace period. At most
     106         * one behind _rcu_cur_gp. If equal to _rcu_cur_gp, a grace period
     107         * detection is not in progress and the detector is idle.
    109108         */
    110109        rcu_gp_t completed_gp;
    … …  
    152151static void start_detector(void);
    153152static void start_reclaimers(void);
    154 static void rcu_read_unlock_impl(size_t *pnesting_cnt);
     153static void read_unlock_impl(size_t *pnesting_cnt);
    155154static void synch_complete(rcu_item_t *rcu_item);
    156155static void add_barrier_cb(void *arg);
    157156static void barrier_complete(rcu_item_t *barrier_item);
    158 static void check_qs(void);
    159 static void record_qs(void);
    160 static void signal_read_unlock(void);
    161157static bool arriving_cbs_empty(void);
    162158static bool next_cbs_empty(void);
    … …  
    198194        rcu.req_gp_end_cnt = 0;
    199195        rcu.req_expedited_cnt = 0;
    200         rcu.cur_gp = 0;
     196        _rcu_cur_gp = 0;
    201197        rcu.completed_gp = 0;
    202198       
    … …  
    300296        if (0 < THREAD->rcu.nesting_cnt) {
    301297                THREAD->rcu.nesting_cnt = 1;
    302                 rcu_read_unlock_impl(&THREAD->rcu.nesting_cnt);
     298                read_unlock_impl(&THREAD->rcu.nesting_cnt);
    303299        }
    304300}
    … …  
    373369}
    374370
    375 /** Delimits the start of an RCU reader critical section.
    376  *
    377  * Reader sections may be nested and are preemptable. You must not
    378  * however block/sleep within reader sections.
    379  */
    380 void rcu_read_lock(void)
    381 {
    382         ASSERT(CPU);
    383         preemption_disable();
    384 
    385         check_qs();
    386         ++(*CPU->rcu.pnesting_cnt);
    387 
    388         preemption_enable();
    389 }
    390 
    391 /** Delimits the end of an RCU reader critical section. */
    392 void rcu_read_unlock(void)
    393 {
    394         ASSERT(CPU);
    395         preemption_disable();
    396        
    397         rcu_read_unlock_impl(CPU->rcu.pnesting_cnt);
    398        
    399         preemption_enable();
    400 }
    401 
    402371/** Returns true if in an rcu reader section. */
    403372bool rcu_read_locked(void)
    … …  
    417386 *           THREAD->rcu.nesting_cnt.
    418387 */
    419 static void rcu_read_unlock_impl(size_t *pnesting_cnt)
     388static void read_unlock_impl(size_t *pnesting_cnt)
    420389{
    421390        ASSERT(PREEMPTION_DISABLED || interrupts_disabled());
    422391       
    423392        if (0 == --(*pnesting_cnt)) {
    424                 record_qs();
     393                _rcu_record_qs();
    425394               
    426395                /*
    … …  
    433402                if ((THREAD && THREAD->rcu.was_preempted) || CPU->rcu.is_delaying_gp) {
    434403                        /* Rechecks with disabled interrupts. */
    435                         signal_read_unlock();
     404                        _rcu_signal_read_unlock();
    436405                }
    437406        }
    438407}
    439408
    440 /** Records a QS if not in a reader critical section. */
    441 static void check_qs(void)
    442 {
    443         ASSERT(PREEMPTION_DISABLED || interrupts_disabled());
    444        
    445         if (0 == *CPU->rcu.pnesting_cnt)
    446                 record_qs();
    447 }
    448 
    449 /** Unconditionally records a quiescent state for the local cpu. */
    450 static void record_qs(void)
    451 {
    452         ASSERT(PREEMPTION_DISABLED || interrupts_disabled());
    453        
    454         /*
    455          * A new GP was started since the last time we passed a QS.
    456          * Notify the detector we have reached a new QS.
    457          */
    458         if (CPU->rcu.last_seen_gp != rcu.cur_gp) {
    459                 rcu_gp_t cur_gp = ACCESS_ONCE(rcu.cur_gp);
    460                 /*
    461                  * Contain memory accesses within a reader critical section.
    462                  * If we are in rcu_lock() it also makes changes prior to the
    463                  * start of the GP visible in the reader section.
    464                  */
    465                 memory_barrier();
    466                 /*
    467                  * Acknowledge we passed a QS since the beginning of rcu.cur_gp.
    468                  * Cache coherency will lazily transport the value to the
    469                  * detector while it sleeps in gp_sleep().
    470                  *
    471                  * Note that there is a theoretical possibility that we
    472                  * overwrite a more recent/greater last_seen_gp here with
    473                  * an older/smaller value. If this cpu is interrupted here
    474                  * while in rcu_lock() reader sections in the interrupt handler
    475                  * will update last_seen_gp to the same value as is currently
    476                  * in local cur_gp. However, if the cpu continues processing
    477                  * interrupts and the detector starts a new GP immediately,
    478                  * local interrupt handlers may update last_seen_gp again (ie
    479                  * properly ack the new GP) with a value greater than local cur_gp.
    480                  * Resetting last_seen_gp to a previous value here is however
    481                  * benign and we only have to remember that this reader may end up
    482                  * in cur_preempted even after the GP ends. That is why we
    483                  * append next_preempted to cur_preempted rather than overwriting
    484                  * it as if cur_preempted were empty.
    485                  */
    486                 CPU->rcu.last_seen_gp = cur_gp;
    487         }
    488 }
    489 
    490409/** If necessary, signals the detector that we exited a reader section. */
    491 static void signal_read_unlock(void)
     410void _rcu_signal_read_unlock(void)
    492411{
    493412        ASSERT(PREEMPTION_DISABLED || interrupts_disabled());
    … …  
    871790       
    872791                /* Exec next_cbs at the end of the next GP. */
    873                 CPU->rcu.next_cbs_gp = rcu.cur_gp + 1;
     792                CPU->rcu.next_cbs_gp = _rcu_cur_gp + 1;
    874793               
    875794                /*
    … …  
    936855       
    937856        ASSERT(CPU->rcu.cur_cbs_gp <= CPU->rcu.next_cbs_gp);
    938         ASSERT(rcu.cur_gp <= CPU->rcu.cur_cbs_gp);
     857        ASSERT(_rcu_cur_gp <= CPU->rcu.cur_cbs_gp);
    939858       
    940859        /*
    … …  
    943862         * new callbacks will arrive while we're waiting; hence +1.
    944863         */
    945         size_t remaining_gp_ends = (size_t) (CPU->rcu.next_cbs_gp - rcu.cur_gp);
     864        size_t remaining_gp_ends = (size_t) (CPU->rcu.next_cbs_gp - _rcu_cur_gp);
    946865        req_detection(remaining_gp_ends + (arriving_cbs_empty() ? 0 : 1));
    947866       
    … …  
    990909
    991910                if (detector_idle) {
    992                         ASSERT(rcu.cur_gp == rcu.completed_gp);
     911                        ASSERT(_rcu_cur_gp == rcu.completed_gp);
    993912                        condvar_signal(&rcu.req_gp_changed);
    994913                }
    … …  
    1069988       
    1070989        /* Start a new GP. Announce to readers that a quiescent state is needed. */
    1071         ++rcu.cur_gp;
     990        ++_rcu_cur_gp;
    1072991       
    1073992        /*
    … …  
    1077996         *
    1078997         * Preempted readers from the previous GP have finished so
    1079          * cur_preempted is empty, but see comment in record_qs().
     998         * cur_preempted is empty, but see comment in _rcu_record_qs().
    1080999         */
    10811000        list_concat(&rcu.cur_preempted, &rcu.next_preempted);
    … …  
    10881007        ASSERT(spinlock_locked(&rcu.gp_lock));
    10891008       
    1090         rcu.completed_gp = rcu.cur_gp;
     1009        rcu.completed_gp = _rcu_cur_gp;
    10911010        --rcu.req_gp_end_cnt;
    10921011       
    … …  
    11951114                 * state since the beginning of this GP.
    11961115                 *
    1197                  * rcu.cur_gp is modified by local detector thread only.
     1116                 * _rcu_cur_gp is modified by local detector thread only.
    11981117                 * Therefore, it is up-to-date even without a lock.
    11991118                 */
    1200                 bool cpu_acked_gp = (cpus[cpu_id].rcu.last_seen_gp == rcu.cur_gp);
     1119                bool cpu_acked_gp = (cpus[cpu_id].rcu.last_seen_gp == _rcu_cur_gp);
    12011120               
    12021121                /*
    12031122                 * Either the cpu is idle or it is exiting away from idle mode
    1204                  * and already sees the most current rcu.cur_gp. See comment
     1123                 * and already sees the most current _rcu_cur_gp. See comment
    12051124                 * in wait_for_readers().
    12061125                 */
    … …  
    12781197       
    12791198        /* Cpu did not pass a quiescent state yet. */
    1280         if (CPU->rcu.last_seen_gp != rcu.cur_gp) {
     1199        if (CPU->rcu.last_seen_gp != _rcu_cur_gp) {
    12811200                /* Interrupted a reader in a reader critical section. */
    12821201                if (0 < (*CPU->rcu.pnesting_cnt)) {
    … …  
    13011220                         */
    13021221                        memory_barrier();
    1303                         CPU->rcu.last_seen_gp = rcu.cur_gp;
     1222                        CPU->rcu.last_seen_gp = _rcu_cur_gp;
    13041223                }
    13051224        } else {
    … …  
    13651284                irq_spinlock_lock(&rcu.preempt_lock, false);
    13661285               
    1367                 if (CPU->rcu.last_seen_gp != rcu.cur_gp) {
     1286                if (CPU->rcu.last_seen_gp != _rcu_cur_gp) {
    13681287                        /* The reader started before the GP started - we must wait for it.*/
    13691288                        list_append(&THREAD->rcu.preempt_link, &rcu.cur_preempted);
    … …  
    13831302         * no readers running on this cpu so this is a quiescent state.
    13841303         */
    1385         record_qs();
     1304        _rcu_record_qs();
    13861305
    13871306        /*

  • kernel/test/cht/cht1.c

    rd99fac9 r8e3ed06  
    3131#include <debug.h>
    3232#include <adt/cht.h>
     33#include <synch/rcu.h>
    3334
    3435typedef struct val {
Note: See TracChangeset for help on using the changeset viewer.