Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_progcache_fd_progcache_clock_h
       2             : #define HEADER_fd_src_flamenco_progcache_fd_progcache_clock_h
       3             : 
       4             : /* fd_progcache_clock.h provides the cache eviction policy (CLOCK).
       5             : 
       6             :    A record is evicted when its size class is full: slots are drawn from that
       7             :    class's range, clearing the visited flag of any record that has it and
       8             :    evicting one that does not.  Access sets the flag.
       9             : 
      10             :    rec->state holds the flag, one byte per record including free ones:
      11             : 
      12             :      0                    free, or acquired and not yet published
      13             :      LOADING|MAPPED       published, program not yet loaded
      14             :      LIVE|MAPPED          holds a value and is reachable
      15             :      LIVE|VISITED|MAPPED  as above, recently accessed (CLOCK second chance)
      16             :      LOADING              unmapped mid-load; becomes a zombie when the load ends
      17             :      LIVE, LIVE|VISITED   zombie: unmapped; once detached and unheld, the next
      18             :                           eviction sweep hands its slot over (or a teardown
      19             :                           sweep frees it)
      20             : 
      21             :    It is the single source of truth for "is this record scannable" (rec->exists
      22             :    serves the different purpose of use-after-free detection on close). */
      23             : 
      24             : #include "fd_progcache_base.h"
      25             : #include "fd_progcache_rec.h"
      26             : 
      27    49611035 : #define FD_PROGCACHE_REC_LIVE    ((uchar)1)
      28    37450223 : #define FD_PROGCACHE_REC_VISITED ((uchar)2)
      29             : 
      30             : /* LOADING marks a record that is in the map but whose program is not loaded yet.  It
      31             :    serializes loaders: two tiles that miss on the same key do not both run
      32             :    fd_sbpf_program_load.  The first publishes the record LOADING and loads it; the rest
      33             :    find it in the map and wait.  It is not LIVE, so the CLOCK sweep steps over a record
      34             :    under load without a test of its own. */
      35             : 
      36     2751174 : #define FD_PROGCACHE_REC_LOADING ((uchar)4)
      37             : 
      38             : /* MAPPED marks a record reachable through the record map.  It is the only way to
      39             :    tell a rooted record, which stays mapped, from one a cancel or a sweep's claim
      40             :    unmapped: both have txn_idx==UINT_MAX. */
      41             : 
      42     1831184 : #define FD_PROGCACHE_REC_MAPPED  ((uchar)8)
      43             : 
      44             : FD_PROTOTYPES_BEGIN
      45             : 
      46             : /* The visited flag is a relaxed hint: CLOCK is approximate and a lost update is
      47             :    benign.  The load sentinel is not -- setting and clearing it are release stores,
      48             :    paired with the acquire in fd_prog_state_is_loading. */
      49             : 
      50             : /* fd_prog_state_load_begin marks the record at the given index LOADING|MAPPED
      51             :    ahead of fd_progcache_push inserting it; not LIVE.  Ended by fd_prog_state_touch. */
      52             : 
      53             : static inline void
      54             : fd_prog_state_load_begin( fd_progcache_rec_t * ele,
      55      917026 :                           ulong                rec_idx ) {
      56      917026 :   __atomic_store_n( &ele[ rec_idx ].state,
      57      917026 :                     (uchar)( FD_PROGCACHE_REC_LOADING|FD_PROGCACHE_REC_MAPPED ), __ATOMIC_RELEASE );
      58      917026 : }
      59             : 
      60             : /* fd_prog_state_touch marks the record at the given index as recently
      61             :    accessed, which makes it less likely to get evicted.  It also ends a load: the
      62             :    record becomes LIVE and the sentinel goes away in a single release store, so a
      63             :    waiter never observes both clear, and the loaded program is visible to anyone
      64             :    who sees LIVE. */
      65             : 
      66             : static inline void
      67             : fd_prog_state_touch( fd_progcache_rec_t * ele,
      68      917050 :                      ulong                rec_idx ) {
      69      917050 :   uchar cur = __atomic_load_n( &ele[ rec_idx ].state, __ATOMIC_RELAXED );
      70      917050 :   if( FD_UNLIKELY( cur & FD_PROGCACHE_REC_LOADING ) ) {
      71             :     /* LOADING is set and LIVE|VISITED clear here, so one xor performs the whole
      72             :        transition: a waiter never sees both LOADING and LIVE clear, and a
      73             :        concurrent unmap's MAPPED clear is not resurrected. */
      74      917026 :     __atomic_fetch_xor( &ele[ rec_idx ].state,
      75      917026 :                         (uchar)( FD_PROGCACHE_REC_LOADING|FD_PROGCACHE_REC_LIVE|FD_PROGCACHE_REC_VISITED ),
      76      917026 :                         __ATOMIC_RELEASE );
      77      917026 :     return;
      78      917026 :   }
      79          24 :   __atomic_fetch_or( &ele[ rec_idx ].state, (uchar)( FD_PROGCACHE_REC_LIVE|FD_PROGCACHE_REC_VISITED ), __ATOMIC_RELAXED );
      80          24 : }
      81             : 
      82             : /* fd_prog_state_is_loading returns 1 if a peer is still loading rec's program.  The
      83             :    acquire pairs with the release store in fd_prog_state_touch, so a caller that sees
      84             :    0 also sees the loaded program.  Deliberately not FD_FN_PURE: the value changes
      85             :    between calls, so a spin loop's calls must not be collapsed into one. */
      86             : 
      87             : static inline int
      88      917122 : fd_prog_state_is_loading( fd_progcache_rec_t const * rec ) {
      89      917122 :   return !!( __atomic_load_n( &rec->state, __ATOMIC_ACQUIRE ) & FD_PROGCACHE_REC_LOADING );
      90      917122 : }
      91             : 
      92             : /* fd_prog_state_clear marks the record at the given index as free / removed, run
      93             :    when the record is released or reinitialized.  The release keeps the preceding
      94             :    teardown ordered before the record reads as free. */
      95             : 
      96             : static inline void
      97             : fd_prog_state_clear( fd_progcache_rec_t * ele,
      98      921838 :                      ulong                rec_idx ) {
      99      921838 :   __atomic_store_n( &ele[ rec_idx ].state, (uchar)0, __ATOMIC_RELEASE );
     100      921838 : }
     101             : 
     102             : /* fd_prog_evict frees a record from the size class that fits sz
     103             :    and returns it read-locked and in-flight, as fd_progcache_rec_acquire does.
     104             :    Scans only that class's range, giving second chances and stepping over held
     105             :    records.  Returns NULL when the draws run out, the caller's cue to spill; that
     106             :    does not imply every record was held.  Release the return value with
     107             :    fd_progcache_rec_abandon. */
     108             : 
     109             : __attribute__((warn_unused_result))
     110             : fd_progcache_rec_t *
     111             : fd_prog_evict( fd_progcache_t * progcache,
     112             :                ulong            sz );
     113             : 
     114             : /* fd_prog_preevict tops up class class_idx's free list toward free_target: if
     115             :    the list is shorter, it runs one eviction sweep and releases the claimed
     116             :    victim's slot to the free list.  Evictions count into metrics (standard
     117             :    eviction counters) unless metrics is NULL.  Returns the number of slots
     118             :    freed (0 or 1).  Safe from any thread concurrently with everything;
     119             :    bounded by the sweep's 2*class_max draw budget. */
     120             : 
     121             : ulong
     122             : fd_prog_preevict( fd_progcache_join_t *    join,
     123             :                   fd_progcache_metrics_t * metrics,
     124             :                   ulong                    class_idx,
     125             :                   ulong                    free_target );
     126             : 
     127             : /* fd_progcache_housekeeping is one background maintenance tick: tops the next
     128             :    size class (round robin) toward 2 free slots via fd_prog_preevict, at most
     129             :    one slot per tick.  A zombie drawn by the sweep is handed over as-is (no
     130             :    second chance), so dead slots return to service without a separate
     131             :    collection pass.  Safe from any thread concurrently with everything. */
     132             : 
     133             : void
     134             : fd_progcache_housekeeping( fd_progcache_join_t *    join,
     135             :                            fd_progcache_metrics_t * metrics );
     136             : 
     137             : FD_PROTOTYPES_END
     138             : 
     139             : #endif /* HEADER_fd_src_flamenco_progcache_fd_progcache_clock_h */