Scheduler/FIFORunner.cc

   1 // $Id$
   2 //
   3 // Copyright (C) 2008
   4 // Fraunhofer Institute for Open Communication Systems (FOKUS)
   5 // Competence Center NETwork research (NET), St. Augustin, GERMANY
   6 //     Stefan Bund <g0dil@berlios.de>
   7 //
   8 // This program is free software; you can redistribute it and/or modify
   9 // it under the terms of the GNU General Public License as published by
  10 // the Free Software Foundation; either version 2 of the License, or
  11 // (at your option) any later version.
  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
  20 // Free Software Foundation, Inc.,
  21 // 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  22
  23 /** \file
  24     \brief FIFORunner non-inline non-template implementation */
  25
  26 #include "FIFORunner.hh"
  27 //#include "FIFORunner.ih"
  28
  29 // Custom includes
  30 #include <signal.h>
  31 #include <time.h>
  32 #include <boost/lambda/lambda.hpp>
  33 #include "../Utils/Exception.hh"
  34 #include "../Utils/senfassert.hh"
  35 #include "../Utils/ScopeExit.hh"
  36 #include <execinfo.h>
  37 #include "../config.hh"
  38 #include <stdint.h>
  39
  40 //#include "FIFORunner.mpp"
  41 #define prefix_
  42 ///////////////////////////////cc.p////////////////////////////////////////
  43
  44 prefix_ senf::scheduler::detail::FIFORunner::FIFORunner()
  45     : tasks_ (), next_ (tasks_.end()), watchdogRunning_ (false), watchdogMs_ (1000),
  46       watchdogAbort_ (false), watchdogCount_(0), hangCount_ (0), yield_ (false)
  47 {
  48     struct sigevent ev;
  49     ::memset(&ev, 0, sizeof(ev));
  50     ev.sigev_notify = SIGEV_SIGNAL;
  51     ev.sigev_signo = SIGURG;
  52     ev.sigev_value.sival_ptr = this;
  53     if (timer_create(CLOCK_MONOTONIC, &ev, &watchdogId_) < 0)
  54         SENF_THROW_SYSTEM_EXCEPTION("timer_create()");
  55
  56     struct sigaction sa;
  57     ::memset(&sa, 0, sizeof(sa));
  58     sa.sa_sigaction = &watchdog;
  59     sa.sa_flags = SA_SIGINFO;
  60     if (sigaction(SIGURG, &sa, 0) < 0)
  61         SENF_THROW_SYSTEM_EXCEPTION("sigaction()");
  62
  63     sigset_t mask;
  64     sigemptyset(&mask);
  65     sigaddset(&mask, SIGURG);
  66     if (sigprocmask(SIG_UNBLOCK, &mask, 0) < 0)
  67         SENF_THROW_SYSTEM_EXCEPTION("sigprocmask()");
  68
  69     tasks_.push_back(highPriorityEnd_);
  70     tasks_.push_back(normalPriorityEnd_);
  71 }
  72
  73 prefix_ senf::scheduler::detail::FIFORunner::~FIFORunner()
  74 {
  75     timer_delete(watchdogId_);
  76     signal(SIGURG, SIG_DFL);
  77 }
  78
  79 prefix_ void senf::scheduler::detail::FIFORunner::startWatchdog()
  80 {
  81     if (watchdogMs_ > 0) {
  82         struct itimerspec timer;
  83         ::memset(&timer, 0, sizeof(timer));
  84
  85         timer.it_interval.tv_sec = watchdogMs_ / 1000;
  86         timer.it_interval.tv_nsec = (watchdogMs_ % 1000) * 1000000ul;
  87         timer.it_value.tv_sec = timer.it_interval.tv_sec;
  88         timer.it_value.tv_nsec = timer.it_interval.tv_nsec;
  89
  90         if (timer_settime(watchdogId_, 0, &timer, 0) < 0)
  91             SENF_THROW_SYSTEM_EXCEPTION("timer_settime()");
  92
  93         watchdogRunning_ = true;
  94     }
  95     else
  96         stopWatchdog();
  97 }
  98
  99 prefix_ void senf::scheduler::detail::FIFORunner::stopWatchdog()
 100 {
 101     struct itimerspec timer;
 102     ::memset(&timer, 0, sizeof(timer));
 103
 104     if (timer_settime(watchdogId_, 0, &timer, 0) < 0)
 105         SENF_THROW_SYSTEM_EXCEPTION("timer_settime()");
 106
 107     watchdogRunning_ = false;
 108 }
 109
 110 // At the moment, the FIFORunner is not very efficient with many non-runnable tasks since the
 111 // complete list of tasks is traversed on each run().
 112 //
 113 // To optimize this, we woould need a way to find the relative ordering of two tasks in O(1) (at the
 114 // moment, this is an O(N) operation by traversing the list).
 115 //
 116 // One idea is, to give each task an 'order' value. Whenever a task is added at the end, it's order
 117 // value is set to the order value of the last task + 1. Whenever the order value such added exceeds
 118 // some threshold (e.g. 2^31 -1 or some such), the task list is traversed from beginning to end to
 119 // assign new consecutive order values. This O(N) operation is so seldom, that it is amortized over
 120 // a very long time.
 121 //
 122 // With this value at hand, we can do several optimizations: One idea would be the following: The
 123 // runnable set always has two types of tasks: There are tasks, which are heavily active and are
 124 // signaled constantly and other tasks which lie dormant most of the time. Those dormant tasks will
 125 // end up at the beginning of the task queue.
 126 //
 127 // With the above defined 'ordering' field available, we can manage an iterator pointing to the
 128 // first and the last runnable task. This will often help a lot since the group of runnable tasks
 129 // will mostly be localized to the end of the queue. only occasionally one of the dormant tasks will
 130 // be runnable. This additional traversal time will be amortized over a larger time.
 131
 132 prefix_ void senf::scheduler::detail::FIFORunner::dequeue(TaskInfo * task)
 133 {
 134     TaskList::iterator i (TaskList::current(*task));
 135     if (next_ == i)
 136         ++next_;
 137     tasks_.erase(i);
 138 }
 139
 140 prefix_ void senf::scheduler::detail::FIFORunner::run()
 141 {
 142     for(;;) {
 143         TaskList::iterator f (tasks_.begin());
 144         TaskList::iterator l (TaskList::current(highPriorityEnd_));
 145         run(f, l);
 146         if (yield_) {
 147             yield_ = false;
 148             continue;
 149         }
 150
 151         f = l; ++f;
 152         l = TaskList::current(normalPriorityEnd_);
 153         run(f, l);
 154         if (yield_) {
 155             yield_ = false;
 156             continue;
 157         }
 158
 159         f = l; ++f;
 160         l = tasks_.end();
 161         run(f, l);
 162         if (yield_) {
 163             yield_ = false;
 164             continue;
 165         }
 166         break;
 167     }
 168 }
 169
 170 prefix_ void senf::scheduler::detail::FIFORunner::run(TaskList::iterator f, TaskList::iterator l)
 171 {
 172     if (f == l)
 173         // We'll have problems inserting NullTask between f and l below, so just explicitly bail out
 174         return;
 175
 176     // This algorithm is carefully adjusted to make it work even when arbitrary tasks are removed
 177     // from the queue
 178     // - Before we begin, we add a NullTask to the queue. The only purpose of this node is, to mark
 179     //   the current end of the queue. The iterator to this node becomes the end iterator of the
 180     //   range to process
 181     // - We update the TaskInfo and move it to the next queue Element before calling the callback so
 182     //   we don't access the TaskInfo if it is removed while the callback is running
 183     // - We keep the next to-be-processed node in a class variable which is checked and updated
 184     //   whenever a node is removed.
 185
 186     NullTask null;
 187     tasks_.insert(l, null);
 188     TaskList::iterator end (TaskList::current(null));
 189     next_ = f;
 190
 191     using namespace boost::lambda;
 192     ScopeExit atExit ((
 193                           var(watchdogCount_) = 0,
 194                           var(next_) = l
 195                      ));
 196
 197     while (next_ != end) {
 198         TaskInfo & task (*next_);
 199         if (task.runnable_) {
 200             task.runnable_ = false;
 201             runningName_ = task.name();
 202 #       ifdef SENF_DEBUG
 203             runningBacktrace_ = task.backtrace_;
 204 #       endif
 205             TaskList::iterator i (next_);
 206             ++ next_;
 207             tasks_.splice(l, tasks_, i);
 208             watchdogCount_ = 1;
 209             yield_ = false;
 210             task.run();
 211             if (yield_)
 212                 return;
 213         }
 214         else
 215             ++ next_;
 216     }
 217 }
 218
 219 prefix_ senf::scheduler::detail::FIFORunner::TaskList::iterator
 220 senf::scheduler::detail::FIFORunner::priorityEnd(TaskInfo::Priority p)
 221 {
 222     switch (p) {
 223     case senf::scheduler::detail::FIFORunner::TaskInfo::PRIORITY_LOW :
 224         return tasks_.end();
 225     case senf::scheduler::detail::FIFORunner::TaskInfo::PRIORITY_NORMAL :
 226         return TaskList::current(normalPriorityEnd_);
 227     case senf::scheduler::detail::FIFORunner::TaskInfo::PRIORITY_HIGH :
 228         return TaskList::current(highPriorityEnd_);
 229     }
 230     return tasks_.begin();
 231 }
 232
 233 prefix_ void senf::scheduler::detail::FIFORunner::watchdog(int, siginfo_t * si, void *)
 234 {
 235     FIFORunner & runner (*static_cast<FIFORunner *>(si->si_value.sival_ptr));
 236     if (runner.watchdogCount_ > 0) {
 237         ++ runner.watchdogCount_;
 238         if (runner.watchdogCount_ > 2) {
 239             ++ runner.hangCount_;
 240             runner.watchdogError();
 241         }
 242     }
 243 }
 244
 245 prefix_ void senf::scheduler::detail::FIFORunner::watchdogError()
 246 {
 247     static char const hex[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
 248                                 'a', 'b', 'c', 'd', 'e', 'f' };
 249     static void * entries[SENF_DEBUG_BACKTRACE_NUMCALLERS];
 250
 251     write(1, "\n\n*** Scheduler task hanging: ", 30);
 252     write(1, runningName_.c_str(), runningName_.size());
 253     write(1, " at\n ", 3);
 254
 255     unsigned nEntries( ::backtrace(entries, SENF_DEBUG_BACKTRACE_NUMCALLERS) );
 256     for (unsigned i (0); i < nEntries; ++i) {
 257         write(1, " 0x", 3);
 258         for (unsigned j (sizeof(void*)); j > 0; --j) {
 259              ::uintptr_t v( ::uintptr_t (entries[i])>>(8*(j-1)));
 260             write(1, &(hex[ (v >> 4) & 0x0f ]), 1);
 261             write(1, &(hex[ (v     ) & 0x0f ]), 1);
 262         }
 263     }
 264     write(1, "\n", 1);
 265
 266 #ifdef SENF_DEBUG
 267     write(1, "Task was initialized at\n", 24);
 268     write(1, runningBacktrace_.c_str(), runningBacktrace_.size());
 269 #endif
 270     write(1, "\n", 1);
 271     if (watchdogAbort_)
 272         assert(false);
 273 }
 274
 275 ///////////////////////////////cc.e////////////////////////////////////////
 276 #undef prefix_
 277 //#include "FIFORunner.mpp"
 278
 279 \f
 280 // Local Variables:
 281 // mode: c++
 282 // fill-column: 100
 283 // comment-column: 40
 284 // c-file-style: "senf"
 285 // indent-tabs-mode: nil
 286 // ispell-local-dictionary: "american"
 287 // compile-command: "scons -u test"
 288 // End: