share/man/man9/token.9

   1 .\"
   2 .\" Copyright (c) 2010 The DragonFly Project.  All rights reserved.
   3 .\"
   4 .\" This code is derived from software contributed to The DragonFly Project
   5 .\" by Venkatesh Srinivas <me@endeavour.zapto.org>.
   6 .\"
   7 .\" Redistribution and use in source and binary forms, with or without
   8 .\" modification, are permitted provided that the following conditions
   9 .\" are met:
  10 .\"
  11 .\" 1. Redistributions of source code must retain the above copyright
  12 .\"    notice, this list of conditions and the following disclaimer.
  13 .\" 2. Redistributions in binary form must reproduce the above copyright
  14 .\"    notice, this list of conditions and the following disclaimer in
  15 .\"    the documentation and/or other materials provided with the
  16 .\"    distribution.
  17 .\" 3. Neither the name of The DragonFly Project nor the names of its
  18 .\"    contributors may be used to endorse or promote products derived
  19 .\"    from this software without specific, prior written permission.
  20 .\"
  21 .\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23 .\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24 .\" FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25 .\" COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26 .\" INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27 .\" BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28 .\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29 .\" AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30 .\" OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31 .\" OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32 .\" SUCH DAMAGE.
  33 .\"
  34 .Dd January 30, 2012
  35 .Dt TOKEN 9
  36 .Os
  37 .Sh NAME
  38 .Nm lwkt_token_init ,
  39 .Nm lwkt_token_uninit ,
  40 .Nm lwkt_gettoken ,
  41 .Nm lwkt_trytoken ,
  42 .Nm lwkt_reltoken ,
  43 .Nm lwkt_token_pool_lookup ,
  44 .Nm lwkt_getpooltoken ,
  45 .\".Nm lwkt_relpooltoken ,
  46 .Nm lwkt_token_swap
  47 .Nd soft token locks
  48 .Sh SYNOPSIS
  49 .In sys/thread.h
  50 .Ft void
  51 .Fn lwkt_token_init "struct lwkt_token *tok" "char *desc"
  52 .Ft void
  53 .Fn lwkt_token_uninit "struct lwkt_token *tok"
  54 .Ft void
  55 .Fn lwkt_gettoken "struct lwkt_token *tok"
  56 .Ft int
  57 .Fn lwkt_trytoken "struct lwkt_token *tok"
  58 .Ft void
  59 .Fn lwkt_reltoken "struct lwkt_token *tok"
  60 .Ft struct lwkt_token *
  61 .Fn lwkt_token_pool_lookup "void *ptr"
  62 .Ft struct lwkt_token *
  63 .Fn lwkt_getpooltoken "void *ptr"
  64 .Ft void
  65 .Fn lwkt_gettoken_shared "struct lwkt_token *tok"
  66 .Ft void
  67 .Fn lwkt_token_swap "void"
  68 .Sh DESCRIPTION
  69 A soft token is a lock which is only held while a thread is running.
  70 If a thread explicitly blocks, all its tokens are released, and reacquired
  71 when the thread resumes.
  72 While a thread blocks, the conditions protected by a soft token
  73 may change and may need to be reevaluated on wakeup.
  74 .Pp
  75 Tokens may be taken recursively.
  76 However, tokens must be released in the reverse order they were acquired.
  77 .Pp
  78 Tokens may be acquired in shared mode, allowing multiple concurrent holders,
  79 via
  80 .Fn lwkt_gettoken_shared ,
  81 or in exclusive mode, allowing only one holder, via
  82 .Fn lwkt_gettoken .
  83 It is safe to acquire a token shared while holding it exclusively.
  84 A thread attempting to acquire a token exclusively after holding it shared
  85 will deadlock.
  86 .Pp
  87 The pool token interface exists to allow using tokens with data structures
  88 which may be deallocated.
  89 It allows getting a token reference from an address, which
  90 is implemented by a set of statically allocated tokens and a hash function.
  91 .Pp
  92 It is not recommended to take pool tokens in shared mode.
  93 A hash collision
  94 from a subsequent exclusive pool token request will hit the
  95 exclusive-after-shared deadlock.
  96 .Pp
  97 The
  98 .Fn lwkt_token_init
  99 function is called to initialize a token.
 100 The
 101 .Fa desc
 102 argument specifies the wait string displayed when waiting for the token.
 103 The
 104 .Fn lwkt_token_uninit
 105 function is called to de-initialize one.
 106 Before using a token, it must be initialized.
 107 .Pp
 108 The
 109 .Fn lwkt_gettoken
 110 function attempts to acquire a token.
 111 If it is unsuccessful, the calling thread blocks.
 112 The
 113 .Fn lwkt_trytoken
 114 does the same thing; however, if it cannot acquire the token, it returns 0
 115 instead of blocking.
 116 The
 117 .Fn lwkt_reltoken
 118 function releases a previously acquired soft token.
 119 .Pp
 120 The
 121 .Fn lwkt_token_pool_lookup
 122 function takes an address and maps it to one of a number of statically
 123 allocated tokens.
 124 The
 125 .Fn lwkt_getpooltoken
 126 function acquires a token associated with an address.
 127 Use these two functions when tokens must protect a data structure,
 128 but the structure can be deallocated.
 129 Pool tokens do not need to be initialized.
 130 .Pp
 131 The
 132 .Fn lwkt_token_swap
 133 function swaps the two most recently acquired tokens; this allows release of
 134 tokens out-of-order.
 135 This function should not be called when less than two tokens are held.
 136 .Sh FILES
 137 The LWKT Token implementation is in
 138 .Pa /sys/kern/lwkt_token.c .
 139 .Sh EXAMPLES
 140 A simple example of using a token to protect access to a data structure:
 141 .Bd -literal
 142 /* Data structure to be protected */
 143 struct protected_data {
 144         struct lwkt_token tok;
 145         int data;
 146 };
 147
 148 struct protected_data pdata;
 149
 150 /* Called early in boot */
 151 void
 152 init(void)
 153 {
 154         lwkt_token_init(&pdata.tok, "example");
 155         pdata.data = 0;
 156 }
 157
 158 /*
 159  * A silly kthread; it uses a token to protect pdata.data.
 160  */
 161 void
 162 kthread1(void)
 163 {
 164         int local;
 165
 166         /*
 167          * Get the soft token.
 168          */
 169         lwkt_gettoken(&pdata.tok);
 170         for (;;) {
 171                 local = pdata.data++;
 172                 tsleep(pdata, 0, "sleep", 0);
 173                 /*
 174                  * While we are asleep, we do not hold the token. When we
 175                  * awake here, we will hold the token again, but we may not
 176                  * depend on local reflecting pdata.data.
 177                  */
 178
 179                 local = pdata.data;
 180                 if (local == 4)
 181                         break;
 182         }
 183         /*
 184          * Release the token.
 185          */
 186         lwkt_reltoken(&pdata.tok);
 187 }
 188 .Ed
 189 .Pp
 190 An example using pool tokens:
 191 .Bd -literal
 192 struct dynamic_data {
 193         int ref;
 194 };
 195
 196 /*
 197  * Use a token to protect a reference count in a dynamic structure.
 198  * Embedding a token in the structure would be inappropriate, since
 199  * another thread may attempt to take the token after we have freed
 200  * the object but before we have removed all external references to it.
 201  */
 202 void
 203 kfunction(struct dynamic_data *dynptr)
 204 {
 205         struct lwkt_token *tok;
 206
 207         /*
 208          * Get a token from the associated with the address of dynptr
 209          */
 210         tok = lwkt_getpooltoken(dynptr);
 211         dynptr->ref--;
 212         if (dynptr->ref == 0)
 213                 free(dynptr);
 214
 215         /*
 216          * Release the token via its reference, as above
 217          */
 218         lwkt_reltoken(tok);
 219 }
 220 .Ed
 221 .Sh NOTES
 222 Soft tokens are not released when a thread is preempted; they are only released
 223 when a thread explicitly blocks, such as via
 224 .Fn tsleep
 225 or
 226 .Fn lwkt_switch .
 227 .Pp
 228 If
 229 .Fn lwkt_gettoken
 230 blocks while attempting to acquire a token, all currently-held tokens will
 231 be released till a thread can acquire all of them again.
 232 .Pp
 233 When tokens are held and
 234 .Fn tsleep_interlock
 235 is used, tokens are not released until blocking happens - that is until the
 236 .Fn tsleep
 237 paired with the
 238 .Fn tsleep_interlock
 239 is called.
 240 .Sh SEE ALSO
 241 .Xr crit_enter 9 ,
 242 .Xr lockmgr 9 ,
 243 .Xr serializer 9 ,
 244 .Xr sleep 9 ,
 245 .Xr spinlock 9
 246 .Sh HISTORY
 247 LWKT tokens first appeared in
 248 .Dx 1.0 .
 249 Shared tokens first appeared in
 250 .Dx 2.11 .
 251 .Sh AUTHORS
 252 The
 253 .Nm token
 254 implementation was written by
 255 .An Matthew Dillon .