share/man/man9/epoch.9

   1 .\"
   2 .\" Copyright (C) 2018 Matthew Macy <mmacy@FreeBSD.org>.
   3 .\"
   4 .\" Redistribution and use in source and binary forms, with or without
   5 .\" modification, are permitted provided that the following conditions
   6 .\" are met:
   7 .\" 1. Redistributions of source code must retain the above copyright
   8 .\"    notice(s), this list of conditions and the following disclaimer as
   9 .\"    the first lines of this file unmodified other than the possible
  10 .\"    addition of one or more copyright notices.
  11 .\" 2. Redistributions in binary form must reproduce the above copyright
  12 .\"    notice(s), 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 COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
  16 .\" EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  17 .\" WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18 .\" DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE LIABLE FOR ANY
  19 .\" DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  20 .\" (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  21 .\" SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  22 .\" 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 SUCH
  25 .\" DAMAGE.
  26 .\"
  27 .\" $FreeBSD$
  28 .\"
  29 .Dd June 28, 2019
  30 .Dt EPOCH 9
  31 .Os
  32 .Sh NAME
  33 .Nm epoch ,
  34 .Nm epoch_context ,
  35 .Nm epoch_alloc ,
  36 .Nm epoch_free ,
  37 .Nm epoch_enter ,
  38 .Nm epoch_exit ,
  39 .Nm epoch_wait ,
  40 .Nm epoch_call ,
  41 .Nm epoch_drain_callbacks ,
  42 .Nm in_epoch ,
  43 .Nd kernel epoch based reclamation
  44 .Sh SYNOPSIS
  45 .In sys/param.h
  46 .In sys/proc.h
  47 .In sys/epoch.h
  48 .Ft epoch_t
  49 .Fn epoch_alloc "int flags"
  50 .Ft void
  51 .Fn epoch_enter "epoch_t epoch"
  52 .Ft void
  53 .Fn epoch_enter_preempt "epoch_t epoch" "epoch_tracker_t et"
  54 .Ft void
  55 .Fn epoch_exit "epoch_t epoch"
  56 .Ft void
  57 .Fn epoch_exit_preempt "epoch_t epoch" "epoch_tracker_t et"
  58 .Ft void
  59 .Fn epoch_wait "epoch_t epoch"
  60 .Ft void
  61 .Fn epoch_wait_preempt "epoch_t epoch"
  62 .Ft void
  63 .Fn epoch_call "epoch_t epoch" "epoch_context_t ctx" "void (*callback) (epoch_context_t)"
  64 .Ft void
  65 .Fn epoch_drain_callbacks "epoch_t epoch"
  66 .Ft int
  67 .Fn in_epoch "epoch_t epoch"
  68 .Sh DESCRIPTION
  69 Epochs are used to guarantee liveness and immutability of data by
  70 deferring reclamation and mutation until a grace period has elapsed.
  71 Epochs do not have any lock ordering issues.
  72 Entering and leaving an epoch section will never block.
  73 .Pp
  74 Epochs are allocated with
  75 .Fn epoch_alloc
  76 and freed with
  77 .Fn epoch_free .
  78 The flags passed to epoch_alloc determine whether preemption is
  79 allowed during a section or not (the default), as specified by
  80 EPOCH_PREEMPT.
  81 Threads indicate the start of an epoch critical section by calling
  82 .Fn epoch_enter .
  83 The end of a critical section is indicated by calling
  84 .Fn epoch_exit .
  85 The _preempt variants can be used around code which requires preemption.
  86 A thread can wait until a grace period has elapsed
  87 since any threads have entered
  88 the epoch by calling
  89 .Fn epoch_wait
  90 or
  91 .Fn epoch_wait_preempt ,
  92 depending on the epoch_type.
  93 The use of a default epoch type allows one to use
  94 .Fn epoch_wait
  95 which is guaranteed to have much shorter completion times since
  96 we know that none of the threads in an epoch section will be preempted
  97 before completing its section.
  98 If the thread can't sleep or is otherwise in a performance sensitive
  99 path it can ensure that a grace period has elapsed by calling
 100 .Fn epoch_call
 101 with a callback with any work that needs to wait for an epoch to elapse.
 102 Only non-sleepable locks can be acquired during a section protected by
 103 .Fn epoch_enter_preempt
 104 and
 105 .Fn epoch_exit_preempt .
 106 INVARIANTS can assert that a thread is in an epoch by using
 107 .Fn in_epoch .
 108 .Pp
 109 The epoch API currently does not support sleeping in epoch_preempt sections.
 110 A caller should never call
 111 .Fn epoch_wait
 112 in the middle of an epoch section for the same epoch as this will lead to a deadlock.
 113 .Pp
 114 By default mutexes cannot be held across
 115 .Fn epoch_wait_preempt .
 116 To permit this the epoch must be allocated with
 117 EPOCH_LOCKED.
 118 When doing this one must be cautious of creating a situation where a deadlock is
 119 possible. Note that epochs are not a straight replacement for read locks.
 120 Callers must use safe list and tailq traversal routines in an epoch (see ck_queue).
 121 When modifying a list referenced from an epoch section safe removal
 122 routines must be used and the caller can no longer modify a list entry
 123 in place.
 124 An item to be modified must be handled with copy on write
 125 and frees must be deferred until after a grace period has elapsed.
 126 .Pp
 127 The
 128 .Fn epoch_drain_callbacks
 129 function is used to drain all pending callbacks which have been invoked by prior
 130 .Fn epoch_call
 131 function calls on the same epoch.
 132 This function is useful when there are shared memory structure(s)
 133 referred to by the epoch callback(s) which are not refcounted and are
 134 rarely freed.
 135 The typical place for calling this function is right before freeing or
 136 invalidating the shared resource(s) used by the epoch callback(s).
 137 This function can sleep and is not optimized for performance.
 138 .Sh RETURN VALUES
 139 .Fn in_epoch curepoch
 140 will return 1 if curthread is in curepoch, 0 otherwise.
 141 .Sh CAVEATS
 142 One must be cautious when using
 143 .Fn epoch_wait_preempt
 144 threads are pinned during epoch sections so if a thread in a section is then
 145 preempted by a higher priority compute bound thread on that CPU it can be
 146 prevented from leaving the section.
 147 Thus the wait time for the waiter is
 148 potentially unbounded.
 149 .Sh EXAMPLES
 150 Async free example:
 151 Thread 1:
 152 .Bd -literal
 153 int
 154 in_pcbladdr(struct inpcb *inp, struct in_addr *faddr, struct in_laddr *laddr,
 155     struct ucred *cred)
 156 {
 157    /* ... */
 158    epoch_enter(net_epoch);
 159     CK_STAILQ_FOREACH(ifa, &ifp->if_addrhead, ifa_link) {
 160         sa = ifa->ifa_addr;
 161         if (sa->sa_family != AF_INET)
 162             continue;
 163         sin = (struct sockaddr_in *)sa;
 164         if (prison_check_ip4(cred, &sin->sin_addr) == 0) {
 165              ia = (struct in_ifaddr *)ifa;
 166              break;
 167         }
 168     }
 169     epoch_exit(net_epoch);
 170    /* ... */
 171 }
 172 .Ed
 173 Thread 2:
 174 .Bd -literal
 175 void
 176 ifa_free(struct ifaddr *ifa)
 177 {
 178
 179     if (refcount_release(&ifa->ifa_refcnt))
 180         epoch_call(net_epoch, &ifa->ifa_epoch_ctx, ifa_destroy);
 181 }
 182
 183 void
 184 if_purgeaddrs(struct ifnet *ifp)
 185 {
 186
 187     /* .... *
 188     IF_ADDR_WLOCK(ifp);
 189     CK_STAILQ_REMOVE(&ifp->if_addrhead, ifa, ifaddr, ifa_link);
 190     IF_ADDR_WUNLOCK(ifp);
 191     ifa_free(ifa);
 192 }
 193 .Ed
 194 .Pp
 195 Thread 1 traverses the ifaddr list in an epoch.
 196 Thread 2 unlinks with the corresponding epoch safe macro, marks as logically free,
 197 and then defers deletion.
 198 More general mutation or a synchronous
 199 free would have to follow a call to
 200 .Fn epoch_wait .
 201 .Sh ERRORS
 202 None.
 203 .Sh NOTES
 204 The
 205 .Nm
 206 kernel programming interface is under development and is subject to change.
 207 .El
 208 .Sh SEE ALSO
 209 .Xr locking 9 ,
 210 .Xr mtx_pool 9 ,
 211 .Xr mutex 9 ,
 212 .Xr rwlock 9 ,
 213 .Xr sema 9 ,
 214 .Xr sleep 9 ,
 215 .Xr sx 9 ,
 216 .Xr timeout 9