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