]>
Commit | Line | Data |
---|---|---|
12c86877 BH |
1 | /* |
2 | PowerDNS Versatile Database Driven Nameserver | |
61b26744 | 3 | Copyright (C) 2002 - 2009 PowerDNS.COM BV |
12c86877 BH |
4 | |
5 | This program is free software; you can redistribute it and/or modify | |
33988bfb BH |
6 | it under the terms of the GNU General Public License version 2 as |
7 | published by the Free Software Foundation | |
12c86877 | 8 | |
f782fe38 MH |
9 | Additionally, the license of this program contains a special |
10 | exception which allows to distribute the program in binary form when | |
11 | it is linked against OpenSSL. | |
12 | ||
12c86877 BH |
13 | This program is distributed in the hope that it will be useful, |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with this program; if not, write to the Free Software | |
06bd9ccf | 20 | Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
12c86877 | 21 | */ |
15a0aaef | 22 | |
12c86877 | 23 | #include "mtasker.hh" |
34e779bc | 24 | #include "misc.hh" |
12c86877 BH |
25 | #include <stdio.h> |
26 | #include <iostream> | |
27 | ||
bdc9f8d2 | 28 | /** \page MTasker |
12c86877 BH |
29 | Simple system for implementing cooperative multitasking of functions, with |
30 | support for waiting on events which can return values. | |
31 | ||
32 | \section copyright Copyright and License | |
a2745e89 | 33 | MTasker is (c) 2002 - 2009 by bert hubert. It is licensed to you under the terms of the GPL version 2. |
12c86877 BH |
34 | |
35 | \section overview High level overview | |
36 | MTasker is designed to support very simple cooperative multitasking to facilitate writing | |
37 | code that would ordinarily require a statemachine, for which the author does not consider | |
38 | himself smart enough. | |
39 | ||
40 | This class does not perform any magic it only makes calls to makecontext() and swapcontext(). | |
41 | Getting the details right however is complicated and MTasker does that for you. | |
42 | ||
43 | If preemptive multitasking or more advanced concepts such as semaphores, locks or mutexes | |
44 | are required, the use of POSIX threads is advised. | |
45 | ||
46 | MTasker is designed to offer the performance of statemachines while maintaining simple thread semantics. It is not | |
47 | a replacement for a full threading system. | |
48 | ||
abc1d928 | 49 | \section compatibility Compatibility |
d3491d5a BH |
50 | MTasker is only guaranteed to work on Linux with glibc 2.2.5 and higher. It does not work on FreeBSD and notably, |
51 | not on Red Hat 6.0. It may work on Solaris, please test. | |
52 | ||
12c86877 BH |
53 | \section concepts Concepts |
54 | ||
55 | There are two important concepts, the 'kernel' and the 'thread'. Each thread starts out as a function, | |
56 | which is passed to MTasker::makeThread(), together with a possible argument. | |
57 | ||
58 | This function is now free to do whatever it wants, but realise that MTasker implements cooperative | |
59 | multitasking, which means that the coder has the responsiblilty of not taking the CPU overly long. | |
60 | Other threads can only get the CPU if MTasker::yield() is called or if a thread sleeps to wait for an event, | |
61 | using the MTasker::waitEvent() method. | |
62 | ||
63 | \section kernel The Kernel | |
64 | The Kernel consists of functions that do housekeeping, but also of code that the client coder | |
65 | can call to report events. A minimal kernel loop looks like this: | |
66 | \code | |
67 | for(;;) { | |
68 | MT.schedule(); | |
69 | if(MT.noProcesses()) // exit if no processes are left | |
70 | break; | |
71 | } | |
72 | \endcode | |
73 | ||
74 | The kernel typically starts from the main() function of your program. New threads are also | |
75 | created from the kernel. This can also happen before entering the main loop. To start a thread, | |
76 | the method MTasker::makeThread is provided. | |
77 | ||
78 | \section events Events | |
79 | By default, Events are recognized by an int and their value is also an int. | |
abc1d928 | 80 | This can be overridden by specifying the EventKey and EventVal template parameters. |
12c86877 BH |
81 | |
82 | An event can be a keypress, but also a UDP packet, or a bit of data from a TCP socket. The | |
83 | sample code provided works with keypresses, but that is just a not very useful example. | |
84 | ||
85 | A thread can also wait for an event only for a limited time, and receive a timeout of that | |
86 | event did not occur within the specified timeframe. | |
87 | ||
88 | \section example A simple menu system | |
89 | \code | |
90 | MTasker<> MT; | |
91 | ||
92 | void menuHandler(void *p) | |
93 | { | |
94 | int num=(int)p; | |
95 | cout<<"Key handler for key "<<num<<" launched"<<endl; | |
96 | ||
97 | MT.waitEvent(num); | |
98 | cout<<"Key "<<num<<" was pressed!"<<endl; | |
99 | } | |
100 | ||
101 | ||
102 | int main() | |
103 | { | |
104 | char line[10]; | |
105 | ||
106 | for(int i=0;i<10;++i) | |
107 | MT.makeThread(menuHandler,(void *)i); | |
108 | ||
109 | for(;;) { | |
110 | while(MT.schedule()); // do everything we can do | |
111 | if(MT.noProcesses()) // exit if no processes are left | |
112 | break; | |
113 | ||
114 | if(!fgets(line,sizeof(line),stdin)) | |
115 | break; | |
116 | ||
117 | MT.sendEvent(*line-'0'); | |
118 | } | |
119 | } | |
120 | \endcode | |
121 | ||
122 | \section example2 Canonical multitasking example | |
123 | This implements the canonical multitasking example, alternately printing an 'A' and a 'B'. The Linux kernel | |
124 | started this way too. | |
125 | \code | |
126 | void printer(void *p) | |
127 | { | |
128 | char c=(char)p; | |
129 | for(;;) { | |
130 | cout<<c<<endl; | |
131 | MT.yield(); | |
132 | } | |
133 | ||
134 | } | |
135 | ||
136 | int main() | |
137 | { | |
138 | MT.makeThread(printer,(void*)'a'); | |
139 | MT.makeThread(printer,(void*)'b'); | |
140 | ||
141 | for(;;) { | |
142 | while(MT.schedule()); // do everything we can do | |
143 | if(MT.noProcesses()) // exit if no processes are left | |
144 | break; | |
145 | } | |
146 | } | |
147 | \endcode | |
148 | ||
149 | */ | |
150 | ||
151 | //! puts a thread to sleep waiting until a specified event arrives | |
152 | /** Threads can call waitEvent to register that they are waiting on an event with a certain key. | |
abc1d928 | 153 | If so desired, the event can carry data which is returned in val in case that is non-zero. |
12c86877 BH |
154 | |
155 | Furthermore, a timeout can be specified in seconds. | |
156 | ||
157 | Only one thread can be waiting on a key, results of trying to have more threads | |
158 | waiting on the same key are undefined. | |
159 | ||
160 | \param key Event key to wait for. Needs to match up to a key reported to sendEvent | |
161 | \param val If non-zero, the value of the event will be stored in *val | |
162 | \param timeout If non-zero, number of seconds to wait for an event. | |
163 | ||
164 | \return returns -1 in case of error, 0 in case of timeout, 1 in case of an answer | |
165 | */ | |
166 | ||
5b0ddd18 | 167 | template<class EventKey, class EventVal>int MTasker<EventKey,EventVal>::waitEvent(EventKey &key, EventVal *val, unsigned int timeoutMsec, struct timeval* now) |
12c86877 | 168 | { |
f9f05db4 BH |
169 | if(d_waiters.count(key)) { // there was already an exact same waiter |
170 | return -1; | |
171 | } | |
172 | ||
12c86877 BH |
173 | Waiter w; |
174 | w.context=new ucontext_t; | |
5b0ddd18 BH |
175 | w.ttd.tv_sec = 0; w.ttd.tv_usec = 0; |
176 | if(timeoutMsec) { | |
177 | struct timeval increment; | |
178 | increment.tv_sec = timeoutMsec / 1000; | |
179 | increment.tv_usec = 1000 * (timeoutMsec % 1000); | |
180 | if(now) | |
181 | w.ttd = increment + *now; | |
182 | else { | |
183 | struct timeval realnow; | |
184 | gettimeofday(&realnow, 0); | |
185 | w.ttd = increment + realnow; | |
186 | } | |
187 | } | |
f6c254c1 | 188 | |
12c86877 | 189 | w.tid=d_tid; |
27af6ab1 BH |
190 | w.key=key; |
191 | ||
192 | d_waiters.insert(w); | |
12c86877 | 193 | |
27af6ab1 | 194 | if(swapcontext(d_waiters.find(key)->context,&d_kernel)) { // 'A' will return here when 'key' has arrived, hands over control to kernel first |
9170fbaf BH |
195 | perror("swapcontext"); |
196 | exit(EXIT_FAILURE); // no way we can deal with this | |
197 | } | |
12c86877 BH |
198 | if(val && d_waitstatus==Answer) |
199 | *val=d_waitval; | |
b636533b | 200 | d_tid=w.tid; |
ec6eacbc BH |
201 | if((char*)&w < d_threads[d_tid].highestStackSeen) { |
202 | d_threads[d_tid].highestStackSeen = (char*)&w; | |
203 | } | |
35ce8576 | 204 | key=d_eventkey; |
12c86877 BH |
205 | return d_waitstatus; |
206 | } | |
207 | ||
208 | //! yields control to the kernel or other threads | |
209 | /** Hands over control to the kernel, allowing other processes to run, or events to arrive */ | |
210 | ||
211 | template<class Key, class Val>void MTasker<Key,Val>::yield() | |
212 | { | |
213 | d_runQueue.push(d_tid); | |
ec6eacbc | 214 | if(swapcontext(d_threads[d_tid].context ,&d_kernel) < 0) { // give control to the kernel |
9170fbaf BH |
215 | perror("swapcontext in yield"); |
216 | exit(EXIT_FAILURE); | |
217 | } | |
12c86877 BH |
218 | } |
219 | ||
220 | //! reports that an event took place for which threads may be waiting | |
7c696097 | 221 | /** From the kernel loop, sendEvent can be called to report that something occurred for which there may be waiters. |
12c86877 BH |
222 | \param key Key of the event for which threads may be waiting |
223 | \param val If non-zero, pointer to the content of the event | |
224 | \return Returns -1 in case of error, 0 if there were no waiters, 1 if a thread was woken up. | |
50c81227 BH |
225 | |
226 | WARNING: when passing val as zero, d_waitval is undefined, and hence waitEvent will return undefined! | |
12c86877 BH |
227 | */ |
228 | template<class EventKey, class EventVal>int MTasker<EventKey,EventVal>::sendEvent(const EventKey& key, const EventVal* val) | |
229 | { | |
d903b428 BH |
230 | typename waiters_t::iterator waiter=d_waiters.find(key); |
231 | ||
232 | if(waiter == d_waiters.end()) { | |
9170fbaf | 233 | // cout<<"Event sent nobody was waiting for!"<<endl; |
12c86877 BH |
234 | return 0; |
235 | } | |
236 | ||
237 | d_waitstatus=Answer; | |
238 | if(val) | |
239 | d_waitval=*val; | |
240 | ||
d903b428 BH |
241 | ucontext_t *userspace=waiter->context; |
242 | d_tid=waiter->tid; // set tid | |
35ce8576 | 243 | d_eventkey=waiter->key; // pass waitEvent the exact key it was woken for |
d903b428 | 244 | d_waiters.erase(waiter); // removes the waitpoint |
9170fbaf BH |
245 | if(swapcontext(&d_kernel,userspace)) { // swaps back to the above point 'A' |
246 | perror("swapcontext in sendEvent"); | |
247 | exit(EXIT_FAILURE); | |
248 | } | |
12c86877 BH |
249 | delete userspace; |
250 | return 1; | |
251 | } | |
252 | ||
782be36c BH |
253 | inline pair<uint32_t, uint32_t> splitPointer(void *ptr) |
254 | { | |
255 | uint64_t ll = (uint64_t) ptr; | |
256 | return make_pair(ll >> 32, ll & 0xffffffff); | |
257 | } | |
258 | ||
259 | inline void* joinPtr(uint32_t val1, uint32_t val2) | |
260 | { | |
261 | return (void*)(((uint64_t)val1 << 32) | (uint64_t)val2); | |
262 | } | |
263 | ||
12c86877 BH |
264 | //! launches a new thread |
265 | /** The kernel can call this to make a new thread, which starts at the function start and gets passed the val void pointer. | |
266 | \param start Pointer to the function which will form the start of the thread | |
267 | \param val A void pointer that can be used to pass data to the thread | |
268 | */ | |
d23a4bc7 | 269 | template<class Key, class Val>void MTasker<Key,Val>::makeThread(tfunc_t *start, void* val) |
12c86877 BH |
270 | { |
271 | ucontext_t *uc=new ucontext_t; | |
272 | getcontext(uc); | |
273 | ||
274 | uc->uc_link = &d_kernel; // come back to kernel after dying | |
275 | uc->uc_stack.ss_sp = new char[d_stacksize]; | |
276 | ||
277 | uc->uc_stack.ss_size = d_stacksize; | |
782be36c BH |
278 | pair<uint32_t, uint32_t> valpair = splitPointer(val); |
279 | pair<uint32_t, uint32_t> thispair = splitPointer(this); | |
280 | ||
281 | makecontext (uc, (void (*)(void))threadWrapper, 6, thispair.first, thispair.second, start, d_maxtid, valpair.first, valpair.second); | |
a2745e89 | 282 | |
ec6eacbc | 283 | d_threads[d_maxtid].context = uc; |
12c86877 BH |
284 | d_runQueue.push(d_maxtid++); // will run at next schedule invocation |
285 | } | |
286 | ||
287 | ||
288 | //! needs to be called periodically so threads can run and housekeeping can be performed | |
289 | /** The kernel should call this function every once in a while. It makes sense | |
290 | to call this function if you: | |
291 | - reported an event | |
292 | - called makeThread | |
293 | - want to have threads running waitEvent() to get a timeout if enough time passed | |
294 | ||
295 | \return Returns if there is more work scheduled and recalling schedule now would be useful | |
296 | ||
297 | */ | |
5b0ddd18 | 298 | template<class Key, class Val>bool MTasker<Key,Val>::schedule(struct timeval* now) |
12c86877 | 299 | { |
12c86877 BH |
300 | if(!d_runQueue.empty()) { |
301 | d_tid=d_runQueue.front(); | |
ec6eacbc | 302 | if(swapcontext(&d_kernel, d_threads[d_tid].context)) { |
9170fbaf BH |
303 | perror("swapcontext in schedule"); |
304 | exit(EXIT_FAILURE); | |
305 | } | |
306 | ||
12c86877 BH |
307 | d_runQueue.pop(); |
308 | return true; | |
309 | } | |
310 | if(!d_zombiesQueue.empty()) { | |
ec6eacbc BH |
311 | delete[] (char *)d_threads[d_zombiesQueue.front()].context->uc_stack.ss_sp; |
312 | delete d_threads[d_zombiesQueue.front()].context; | |
12c86877 BH |
313 | d_threads.erase(d_zombiesQueue.front()); |
314 | d_zombiesQueue.pop(); | |
315 | return true; | |
316 | } | |
317 | if(!d_waiters.empty()) { | |
5b0ddd18 | 318 | struct timeval rnow; |
f6c254c1 | 319 | if(!now) |
5b0ddd18 BH |
320 | gettimeofday(&rnow, 0); |
321 | else | |
322 | rnow = *now; | |
27af6ab1 | 323 | |
b786789d BH |
324 | typedef typename waiters_t::template index<KeyTag>::type waiters_by_ttd_index_t; |
325 | // waiters_by_ttd_index_t& ttdindex=d_waiters.template get<KeyTag>(); | |
326 | waiters_by_ttd_index_t& ttdindex=boost::multi_index::get<KeyTag>(d_waiters); | |
327 | ||
27af6ab1 | 328 | for(typename waiters_by_ttd_index_t::iterator i=ttdindex.begin(); i != ttdindex.end(); ) { |
5b0ddd18 | 329 | if(i->ttd.tv_sec && i->ttd < rnow) { |
4957a608 BH |
330 | d_waitstatus=TimeOut; |
331 | d_eventkey=i->key; // pass waitEvent the exact key it was woken for | |
332 | ucontext_t* uc = i->context; | |
e19a1ced | 333 | d_tid = i->tid; |
4957a608 BH |
334 | ttdindex.erase(i++); // removes the waitpoint |
335 | ||
336 | if(swapcontext(&d_kernel, uc)) { // swaps back to the above point 'A' | |
337 | perror("swapcontext in schedule2"); | |
338 | exit(EXIT_FAILURE); | |
339 | } | |
340 | delete uc; | |
12c86877 | 341 | } |
5b0ddd18 | 342 | else if(i->ttd.tv_sec) |
4957a608 | 343 | break; |
12c86877 BH |
344 | } |
345 | } | |
346 | return false; | |
347 | } | |
348 | ||
349 | //! returns true if there are no processes | |
350 | /** Call this to check if no processes are running anymore | |
351 | \return true if no processes are left | |
352 | */ | |
353 | template<class Key, class Val>bool MTasker<Key,Val>::noProcesses() | |
354 | { | |
355 | return d_threads.empty(); | |
356 | } | |
357 | ||
e5d684f9 BH |
358 | //! returns the number of processes running |
359 | /** Call this to perhaps limit activities if too many threads are running | |
360 | \return number of processes running | |
361 | */ | |
362 | template<class Key, class Val>unsigned int MTasker<Key,Val>::numProcesses() | |
363 | { | |
364 | return d_threads.size(); | |
365 | } | |
366 | ||
12c86877 BH |
367 | //! gives access to the list of Events threads are waiting for |
368 | /** The kernel can call this to get a list of Events threads are waiting for. This is very useful | |
369 | to setup 'select' or 'poll' or 'aio' events needed to satisfy these requests. | |
370 | getEvents clears the events parameter before filling it. | |
371 | ||
372 | \param events Vector which is to be filled with keys threads are waiting for | |
373 | */ | |
374 | template<class Key, class Val>void MTasker<Key,Val>::getEvents(std::vector<Key>& events) | |
375 | { | |
376 | events.clear(); | |
377 | for(typename waiters_t::const_iterator i=d_waiters.begin();i!=d_waiters.end();++i) { | |
378 | events.push_back(i->first); | |
379 | } | |
380 | } | |
381 | ||
782be36c | 382 | template<class Key, class Val>void MTasker<Key,Val>::threadWrapper(uint32_t self1, uint32_t self2, tfunc_t *tf, int tid, uint32_t val1, uint32_t val2) |
12c86877 | 383 | { |
782be36c BH |
384 | void* val = joinPtr(val1, val2); |
385 | MTasker* self = (MTasker*) joinPtr(self1, self2); | |
ec6eacbc | 386 | self->d_threads[self->d_tid].startOfStack = self->d_threads[self->d_tid].highestStackSeen = (char*)&val; |
12c86877 BH |
387 | (*tf)(val); |
388 | self->d_zombiesQueue.push(tid); | |
389 | ||
390 | // we now jump to &kernel, automatically | |
391 | } | |
392 | ||
c836dc19 BH |
393 | //! Returns the current Thread ID (tid) |
394 | /** Processes can call this to get a numerical representation of their current thread ID. | |
395 | This can be useful for logging purposes. | |
396 | */ | |
397 | template<class Key, class Val>int MTasker<Key,Val>::getTid() | |
398 | { | |
399 | return d_tid; | |
400 | } | |
ec6eacbc BH |
401 | |
402 | ||
403 | //! Returns the maximum stack usage so far of this MThread | |
404 | template<class Key, class Val>unsigned int MTasker<Key,Val>::getMaxStackUsage() | |
405 | { | |
406 | return d_threads[d_tid].startOfStack - d_threads[d_tid].highestStackSeen; | |
407 | } |