Contiki-NG
pt.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2004-2005, Swedish Institute of Computer Science.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the Institute nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
29 * This file is part of the Contiki operating system.
30 *
31 * Author: Adam Dunkels <adam@sics.se>
32 *
33 */
34
35/**
36 * \addtogroup threads
37 * @{
38 */
39
40/**
41 * \defgroup pt Protothreads
42 *
43 * Protothreads are a type of lightweight stackless threads designed for
44 * severly memory constrained systems such as deeply embedded systems or
45 * sensor network nodes. Protothreads provides linear code execution for
46 * event-driven systems implemented in C. Protothreads can be used with
47 * or without an RTOS.
48 *
49 * Protothreads are a extremely lightweight, stackless type of threads
50 * that provides a blocking context on top of an event-driven system,
51 * without the overhead of per-thread stacks. The purpose of protothreads
52 * is to implement sequential flow of control without complex state
53 * machines or full multi-threading. Protothreads provides conditional
54 * blocking inside C functions.
55 *
56 * The advantage of protothreads over a purely event-driven approach is
57 * that protothreads provides a sequential code structure that allows for
58 * blocking functions. In purely event-driven systems, blocking must be
59 * implemented by manually breaking the function into two pieces - one
60 * for the piece of code before the blocking call and one for the code
61 * after the blocking call. This makes it hard to use control structures
62 * such as if() conditionals and while() loops.
63 *
64 * The advantage of protothreads over ordinary threads is that a
65 * protothread does not require a separate stack. In memory constrained
66 * systems, the overhead of allocating multiple stacks can consume large
67 * amounts of the available memory. In contrast, each protothread only
68 * requires between two and twelve bytes of state, depending on the
69 * architecture.
70 *
71 * \note Because protothreads do not save the stack context across a
72 * blocking call, <b>local variables are not preserved when the
73 * protothread blocks</b>. This means that local variables should be used
74 * with utmost care - <b>if in doubt, do not use local variables inside a
75 * protothread!</b>
76 *
77 *
78 * Main features:
79 *
80 * - No machine specific code - the protothreads library is pure C
81 *
82 * - Does not use error-prone functions such as longjmp()
83 *
84 * - Very small RAM overhead - only two bytes per protothread
85 *
86 * - Can be used with or without an OS
87 *
88 * - Provides blocking wait without full multi-threading or
89 * stack-switching
90 *
91 * Examples applications:
92 *
93 * - Memory constrained systems
94 *
95 * - Event-driven protocol stacks
96 *
97 * - Deeply embedded systems
98 *
99 * - Sensor network nodes
100 *
101 * The protothreads API consists of four basic operations:
102 * initialization: PT_INIT(), execution: PT_BEGIN(), conditional
103 * blocking: PT_WAIT_UNTIL() and exit: PT_END(). On top of these, two
104 * convenience functions are built: reversed condition blocking:
105 * PT_WAIT_WHILE() and protothread blocking: PT_WAIT_THREAD().
106 *
107 * \sa \ref pt "Protothreads API documentation"
108 *
109 * The protothreads library is released under a BSD-style license that
110 * allows for both non-commercial and commercial usage. The only
111 * requirement is that credit is given.
112 *
113 * \section authors Authors
114 *
115 * The protothreads library was written by Adam Dunkels <adam@sics.se>
116 * with support from Oliver Schmidt <ol.sc@web.de>.
117 *
118 * \section pt-desc Protothreads
119 *
120 * Protothreads are a extremely lightweight, stackless threads that
121 * provides a blocking context on top of an event-driven system, without
122 * the overhead of per-thread stacks. The purpose of protothreads is to
123 * implement sequential flow of control without using complex state
124 * machines or full multi-threading. Protothreads provides conditional
125 * blocking inside a C function.
126 *
127 * In memory constrained systems, such as deeply embedded systems,
128 * traditional multi-threading may have a too large memory overhead. In
129 * traditional multi-threading, each thread requires its own stack, that
130 * typically is over-provisioned. The stacks may use large parts of the
131 * available memory.
132 *
133 * The main advantage of protothreads over ordinary threads is that
134 * protothreads are very lightweight: a protothread does not require its
135 * own stack. Rather, all protothreads run on the same stack and context
136 * switching is done by stack rewinding. This is advantageous in memory
137 * constrained systems, where a stack for a thread might use a large part
138 * of the available memory. A protothread only requires only two bytes of
139 * memory per protothread. Moreover, protothreads are implemented in pure
140 * C and do not require any machine-specific assembler code.
141 *
142 * A protothread runs within a single C function and cannot span over
143 * other functions. A protothread may call normal C functions, but cannot
144 * block inside a called function. Blocking inside nested function calls
145 * is instead made by spawning a separate protothread for each
146 * potentially blocking function. The advantage of this approach is that
147 * blocking is explicit: the programmer knows exactly which functions
148 * that block that which functions the never blocks.
149 *
150 * Protothreads are similar to asymmetric co-routines. The main
151 * difference is that co-routines uses a separate stack for each
152 * co-routine, whereas protothreads are stackless. The most similar
153 * mechanism to protothreads are Python generators. These are also
154 * stackless constructs, but have a different purpose. Protothreads
155 * provides blocking contexts inside a C function, whereas Python
156 * generators provide multiple exit points from a generator function.
157 *
158 * \section pt-autovars Local variables
159 *
160 * \note
161 * Because protothreads do not save the stack context across a blocking
162 * call, local variables are not preserved when the protothread
163 * blocks. This means that local variables should be used with utmost
164 * care - if in doubt, do not use local variables inside a protothread!
165 *
166 * \section pt-scheduling Scheduling
167 *
168 * A protothread is driven by repeated calls to the function in which the
169 * protothread is running. Each time the function is called, the
170 * protothread will run until it blocks or exits. Thus the scheduling of
171 * protothreads is done by the application that uses protothreads.
172 *
173 * \section pt-impl Implementation
174 *
175 * Protothreads are implemented using \ref lc "local continuations". A
176 * local continuation represents the current state of execution at a
177 * particular place in the program, but does not provide any call history
178 * or local variables. A local continuation can be set in a specific
179 * function to capture the state of the function. After a local
180 * continuation has been set can be resumed in order to restore the state
181 * of the function at the point where the local continuation was set.
182 *
183 *
184 * Local continuations can be implemented in a variety of ways:
185 *
186 * -# by using machine specific assembler code,
187 * -# by using standard C constructs, or
188 * -# by using compiler extensions.
189 *
190 * The first way works by saving and restoring the processor state,
191 * except for stack pointers, and requires between 16 and 32 bytes of
192 * memory per protothread. The exact amount of memory required depends on
193 * the architecture.
194 *
195 * The standard C implementation requires only two bytes of state per
196 * protothread and utilizes the C switch() statement in a non-obvious way
197 * that is similar to Duff's device. This implementation does, however,
198 * impose a slight restriction to the code that uses protothreads in that
199 * the code cannot use switch() statements itself.
200 *
201 * Certain compilers has C extensions that can be used to implement
202 * protothreads. GCC supports label pointers that can be used for this
203 * purpose. With this implementation, protothreads require 4 bytes of RAM
204 * per protothread.
205 *
206 * @{
207 *
208 * \file
209 * Protothreads implementation.
210 * \author
211 * Adam Dunkels <adam@sics.se>
212 */
213
214#ifndef PT_H_
215#define PT_H_
216
217#include "sys/lc.h"
218
219struct pt {
220 lc_t lc;
221};
222
223#define PT_WAITING 0
224#define PT_YIELDED 1
225#define PT_EXITED 2
226#define PT_ENDED 3
227
228/**
229 * \name Initialization
230 * @{
231 */
232
233/**
234 * Initialize a protothread.
235 *
236 * Initializes a protothread. Initialization must be done prior to
237 * starting to execute the protothread.
238 *
239 * \param pt A pointer to the protothread control structure.
240 *
241 * \sa PT_SPAWN()
242 *
243 * \hideinitializer
244 */
245#define PT_INIT(pt) LC_INIT((pt)->lc)
246
247/** @} */
248
249/**
250 * \name Declaration and definition
251 * @{
252 */
253
254/**
255 * Declaration of a protothread.
256 *
257 * This macro is used to declare a protothread. All protothreads must
258 * be declared with this macro.
259 *
260 * \param name_args The name and arguments of the C function
261 * implementing the protothread.
262 *
263 * \hideinitializer
264 */
265#define PT_THREAD(name_args) char name_args
266
267/**
268 * Declare the start of a protothread inside the C function
269 * implementing the protothread.
270 *
271 * This macro is used to declare the starting point of a
272 * protothread. It should be placed at the start of the function in
273 * which the protothread runs. All C statements above the PT_BEGIN()
274 * invokation will be executed each time the protothread is scheduled.
275 *
276 * \param pt A pointer to the protothread control structure.
277 *
278 * \hideinitializer
279 */
280#define PT_BEGIN(pt) { char PT_YIELD_FLAG = 1; if (PT_YIELD_FLAG) {;} LC_RESUME((pt)->lc)
281
282/**
283 * Declare the end of a protothread.
284 *
285 * This macro is used for declaring that a protothread ends. It must
286 * always be used together with a matching PT_BEGIN() macro.
287 *
288 * \param pt A pointer to the protothread control structure.
289 *
290 * \hideinitializer
291 */
292#define PT_END(pt) LC_END((pt)->lc); PT_YIELD_FLAG = 0; \
293 PT_INIT(pt); return PT_ENDED; }
294
295/** @} */
296
297/**
298 * \name Blocked wait
299 * @{
300 */
301
302/**
303 * Block and wait until condition is true.
304 *
305 * This macro blocks the protothread until the specified condition is
306 * true.
307 *
308 * \param pt A pointer to the protothread control structure.
309 * \param condition The condition.
310 *
311 * \hideinitializer
312 */
313#define PT_WAIT_UNTIL(pt, condition) \
314 do { \
315 LC_SET((pt)->lc); \
316 if(!(condition)) { \
317 return PT_WAITING; \
318 } \
319 } while(0)
320
321/**
322 * Block and wait while condition is true.
323 *
324 * This function blocks and waits while condition is true. See
325 * PT_WAIT_UNTIL().
326 *
327 * \param pt A pointer to the protothread control structure.
328 * \param cond The condition.
329 *
330 * \hideinitializer
331 */
332#define PT_WAIT_WHILE(pt, cond) PT_WAIT_UNTIL((pt), !(cond))
333
334/** @} */
335
336/**
337 * \name Hierarchical protothreads
338 * @{
339 */
340
341/**
342 * Block and wait until a child protothread completes.
343 *
344 * This macro schedules a child protothread. The current protothread
345 * will block until the child protothread completes.
346 *
347 * \note The child protothread must be manually initialized with the
348 * PT_INIT() function before this function is used.
349 *
350 * \param pt A pointer to the protothread control structure.
351 * \param thread The child protothread with arguments
352 *
353 * \sa PT_SPAWN()
354 *
355 * \hideinitializer
356 */
357#define PT_WAIT_THREAD(pt, thread) PT_WAIT_WHILE((pt), PT_SCHEDULE(thread))
358
359/**
360 * Spawn a child protothread and wait until it exits.
361 *
362 * This macro spawns a child protothread and waits until it exits. The
363 * macro can only be used within a protothread.
364 *
365 * \param pt A pointer to the protothread control structure.
366 * \param child A pointer to the child protothread's control structure.
367 * \param thread The child protothread with arguments
368 *
369 * \hideinitializer
370 */
371#define PT_SPAWN(pt, child, thread) \
372 do { \
373 PT_INIT((child)); \
374 PT_WAIT_THREAD((pt), (thread)); \
375 } while(0)
376
377/** @} */
378
379/**
380 * \name Exiting and restarting
381 * @{
382 */
383
384/**
385 * Restart the protothread.
386 *
387 * This macro will block and cause the running protothread to restart
388 * its execution at the place of the PT_BEGIN() call.
389 *
390 * \param pt A pointer to the protothread control structure.
391 *
392 * \hideinitializer
393 */
394#define PT_RESTART(pt) \
395 do { \
396 PT_INIT(pt); \
397 return PT_WAITING; \
398 } while(0)
399
400/**
401 * Exit the protothread.
402 *
403 * This macro causes the protothread to exit. If the protothread was
404 * spawned by another protothread, the parent protothread will become
405 * unblocked and can continue to run.
406 *
407 * \param pt A pointer to the protothread control structure.
408 *
409 * \hideinitializer
410 */
411#define PT_EXIT(pt) \
412 do { \
413 PT_INIT(pt); \
414 return PT_EXITED; \
415 } while(0)
416
417/** @} */
418
419/**
420 * \name Calling a protothread
421 * @{
422 */
423
424/**
425 * Schedule a protothread.
426 *
427 * This function schedules a protothread. The return value of the
428 * function is non-zero if the protothread is running or zero if the
429 * protothread has exited.
430 *
431 * \param f The call to the C function implementing the protothread to
432 * be scheduled
433 *
434 * \hideinitializer
435 */
436#define PT_SCHEDULE(f) ((f) < PT_EXITED)
437
438/** @} */
439
440/**
441 * \name Yielding from a protothread
442 * @{
443 */
444
445/**
446 * Yield from the current protothread.
447 *
448 * This function will yield the protothread, thereby allowing other
449 * processing to take place in the system.
450 *
451 * \param pt A pointer to the protothread control structure.
452 *
453 * \hideinitializer
454 */
455#define PT_YIELD(pt) \
456 do { \
457 PT_YIELD_FLAG = 0; \
458 LC_SET((pt)->lc); \
459 if(PT_YIELD_FLAG == 0) { \
460 return PT_YIELDED; \
461 } \
462 } while(0)
463
464/**
465 * \brief Yield from the protothread until a condition occurs.
466 * \param pt A pointer to the protothread control structure.
467 * \param cond The condition.
468 *
469 * This function will yield the protothread, until the
470 * specified condition evaluates to true.
471 *
472 *
473 * \hideinitializer
474 */
475#define PT_YIELD_UNTIL(pt, cond) \
476 do { \
477 PT_YIELD_FLAG = 0; \
478 LC_SET((pt)->lc); \
479 if((PT_YIELD_FLAG == 0) || !(cond)) { \
480 return PT_YIELDED; \
481 } \
482 } while(0)
483
484/** @} */
485
486#endif /* PT_H_ */
487
488/**
489 * @}
490 * @}
491 */
void * lc_t
The local continuation type.
Definition: lc-addrlabels.h:63
Local continuations.