pdns/mtasker.cc

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