pdns/mtasker.cc

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