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