Document shared tokens in token(9).
[dragonfly.git] / 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 June 10, 2010
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. A hash collision
93 from a subsequent exclusive pool token request will hit the
94 exclusive-after-shared deadlock.
95 .Pp
96 The
97 .Fn lwkt_token_init
98 function is called to initialize a token.
99 The
100 .Fa desc
101 argument specifies the wait string displayed when waiting for the token.
102 The
103 .Fn lwkt_token_uninit
104 function is called to de-initialize one.
105 Before using a token, it must be initialized.
106 .Pp
107 The
108 .Fn lwkt_gettoken
109 function attempts to acquire a token.
110 If it is unsuccessful, the calling thread blocks.
111 The
112 .Fn lwkt_trytoken
113 does the same thing; however, if it cannot acquire the token, it returns 0
114 instead of blocking.
115 The
116 .Fn lwkt_reltoken
117 function releases a previously acquired soft token.
118 .Pp
119 The
120 .Fn lwkt_token_pool_lookup
121 function takes an address and maps it to one of a number of statically
122 allocated tokens.
123 The
124 .Fn lwkt_getpooltoken
125 function acquires a token associated with an address.
126 Use these two functions when tokens must protect a data structure,
127 but the structure can be deallocated.
128 Pool tokens do not need to be initialized.
129 .Pp
130 The
131 .Fn lwkt_token_swap
132 function swaps the two most recently acquired tokens; this allows release of
133 tokens out-of-order.
134 This function should not be called when less than two tokens are held.
135 .Sh EXAMPLES
136 A simple example of using a token to protect access to a data structure:
137 .Bd -literal
138 /* Data structure to be protected */
139 struct protected_data {
140         struct lwkt_token tok;
141         int data;
142 };
143
144 struct protected_data pdata;
145
146 /* Called early in boot */
147 void
148 init(void)
149 {
150         lwkt_token_init(&pdata.tok, "example");
151         pdata.data = 0;
152 }
153
154 /*
155  * A silly kthread; it uses a token to protect pdata.data.
156  */
157 void
158 kthread1(void)
159 {
160         int local;
161
162         /*
163          * Get the soft token.
164          */
165         lwkt_gettoken(&pdata.tok);
166         for (;;) {
167                 local = pdata.data++;
168                 tsleep(pdata, 0, "sleep", 0);
169                 /*
170                  * While we are asleep, we do not hold the token. When we
171                  * awake here, we will hold the token again, but we may not
172                  * depend on local reflecting pdata.data.
173                  */
174
175                 local = pdata.data;
176                 if (local == 4)
177                         break;
178         }
179         /*
180          * Release the token.
181          */
182         lwkt_reltoken(&pdata.tok);
183 }
184 .Ed
185 .Pp
186 An example using pool tokens:
187 .Bd -literal
188 struct dynamic_data {
189         int ref;
190 };
191
192 /*
193  * Use a token to protect a reference count in a dynamic structure.
194  * Embedding a token in the structure would be inappropriate, since
195  * another thread may attempt to take the token after we have freed
196  * the object but before we have removed all external references to it.
197  */
198 void
199 kfunction(struct dynamic_data *dynptr)
200 {
201         struct lwkt_token *tok;
202
203         /*
204          * Get a token from the associated with the address of dynptr
205          */
206         tok = lwkt_getpooltoken(dynptr);
207         dynptr->ref--;
208         if (dynptr->ref == 0)
209                 free(dynptr);
210
211         /*
212          * Release the token via its reference, as above
213          */
214         lwkt_reltoken(tok);
215 }
216 .Ed
217 .Sh NOTES
218 Soft tokens are not released when a thread is preempted; they are only released
219 when a thread explicitly blocks, such as via
220 .Fn tsleep
221 or
222 .Fn lwkt_switch .
223 .Pp
224 If
225 .Fn lwkt_gettoken
226 blocks while attempting to acquire a token, all currently-held tokens will
227 be released till a thread can acquire all of them again.
228 .Pp
229 When tokens are held and
230 .Fn tsleep_interlock
231 is used, tokens are not released until blocking happens - that is until the
232 .Fn tsleep
233 paired with the
234 .Fn tsleep_interlock
235 is called.
236 .Sh FILES
237 The LWKT Token implementation is in
238 .Pa /sys/kern/lwkt_token.c .
239 .Sh SEE ALSO
240 .Xr crit_enter 9 ,
241 .Xr lockmgr 9 ,
242 .Xr serializer 9 ,
243 .Xr sleep 9 ,
244 .Xr spinlock 9
245 .Sh HISTORY
246 LWKT tokens first appeared in
247 .Dx 1.0 .
248 Shared tokens first appeared in
249 .Dx 2.11 .
250 .Sh AUTHORS
251 The
252 .Nm token
253 implementation was written by
254 .An Matthew Dillon .