4 // Fraunhofer Institute for Open Communication Systems (FOKUS)
5 // Competence Center NETwork research (NET), St. Augustin, GERMANY
6 // Stefan Bund <g0dil@berlios.de>
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.
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.
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.
24 \brief FIFORunner non-inline non-template implementation */
26 #include "FIFORunner.hh"
27 //#include "FIFORunner.ih"
32 #include <boost/lambda/lambda.hpp>
33 #include <senf/Utils/Exception.hh>
34 #include <senf/Utils/senfassert.hh>
35 #include <senf/Utils/ScopeExit.hh>
39 #include <senf/config.hh>
42 #include "senf/Utils/IgnoreValue.hh"
44 //#include "FIFORunner.mpp"
46 ///////////////////////////////cc.p////////////////////////////////////////
48 prefix_ senf::scheduler::detail::FIFORunner::FIFORunner()
49 : tasks_ (), next_ (tasks_.end()), watchdogRunning_ (false), watchdogMs_ (1000),
50 watchdogAbort_ (false), watchdogCount_(0), hangCount_ (0), yield_ (false)
53 ::memset(&ev, 0, sizeof(ev));
54 ev.sigev_notify = SIGEV_SIGNAL;
55 ev.sigev_signo = SIGURG;
56 ev.sigev_value.sival_ptr = this;
57 if (timer_create(CLOCK_MONOTONIC, &ev, &watchdogId_) < 0)
58 SENF_THROW_SYSTEM_EXCEPTION("timer_create()");
61 ::memset(&sa, 0, sizeof(sa));
62 sa.sa_sigaction = &watchdog;
63 sa.sa_flags = SA_SIGINFO;
64 if (sigaction(SIGURG, &sa, 0) < 0)
65 SENF_THROW_SYSTEM_EXCEPTION("sigaction()");
69 sigaddset(&mask, SIGURG);
70 if (sigprocmask(SIG_UNBLOCK, &mask, 0) < 0)
71 SENF_THROW_SYSTEM_EXCEPTION("sigprocmask()");
73 tasks_.push_back(highPriorityEnd_);
74 tasks_.push_back(normalPriorityEnd_);
77 prefix_ senf::scheduler::detail::FIFORunner::~FIFORunner()
79 timer_delete(watchdogId_);
80 signal(SIGURG, SIG_DFL);
83 prefix_ void senf::scheduler::detail::FIFORunner::startWatchdog()
85 if (watchdogMs_ > 0) {
86 struct itimerspec timer;
87 ::memset(&timer, 0, sizeof(timer));
89 timer.it_interval.tv_sec = watchdogMs_ / 1000;
90 timer.it_interval.tv_nsec = (watchdogMs_ % 1000) * 1000000ul;
91 timer.it_value.tv_sec = timer.it_interval.tv_sec;
92 timer.it_value.tv_nsec = timer.it_interval.tv_nsec;
94 if (timer_settime(watchdogId_, 0, &timer, 0) < 0)
95 SENF_THROW_SYSTEM_EXCEPTION("timer_settime()");
97 watchdogRunning_ = true;
103 prefix_ void senf::scheduler::detail::FIFORunner::stopWatchdog()
105 struct itimerspec timer;
106 ::memset(&timer, 0, sizeof(timer));
108 if (timer_settime(watchdogId_, 0, &timer, 0) < 0)
109 SENF_THROW_SYSTEM_EXCEPTION("timer_settime()");
111 watchdogRunning_ = false;
114 // At the moment, the FIFORunner is not very efficient with many non-runnable tasks since the
115 // complete list of tasks is traversed on each run().
117 // To optimize this, we woould need a way to find the relative ordering of two tasks in O(1) (at the
118 // moment, this is an O(N) operation by traversing the list).
120 // One idea is, to give each task an 'order' value. Whenever a task is added at the end, it's order
121 // value is set to the order value of the last task + 1. Whenever the order value such added exceeds
122 // some threshold (e.g. 2^31 -1 or some such), the task list is traversed from beginning to end to
123 // assign new consecutive order values. This O(N) operation is so seldom, that it is amortized over
126 // With this value at hand, we can do several optimizations: One idea would be the following: The
127 // runnable set always has two types of tasks: There are tasks, which are heavily active and are
128 // signaled constantly and other tasks which lie dormant most of the time. Those dormant tasks will
129 // end up at the beginning of the task queue.
131 // With the above defined 'ordering' field available, we can manage an iterator pointing to the
132 // first and the last runnable task. This will often help a lot since the group of runnable tasks
133 // will mostly be localized to the end of the queue. only occasionally one of the dormant tasks will
134 // be runnable. This additional traversal time will be amortized over a larger time.
136 prefix_ void senf::scheduler::detail::FIFORunner::dequeue(TaskInfo * task)
138 TaskList::iterator i (TaskList::current(*task));
144 prefix_ void senf::scheduler::detail::FIFORunner::run()
147 TaskList::iterator f (tasks_.begin());
148 TaskList::iterator l (TaskList::current(highPriorityEnd_));
156 l = TaskList::current(normalPriorityEnd_);
174 prefix_ void senf::scheduler::detail::FIFORunner::run(TaskList::iterator f, TaskList::iterator l)
177 // We'll have problems inserting NullTask between f and l below, so just explicitly bail out
180 // This algorithm is carefully adjusted to make it work even when arbitrary tasks are removed
182 // - Before we begin, we add a NullTask to the queue. The only purpose of this node is, to mark
183 // the current end of the queue. The iterator to this node becomes the end iterator of the
185 // - We update the TaskInfo and move it to the next queue Element before calling the callback so
186 // we don't access the TaskInfo if it is removed while the callback is running
187 // - We keep the next to-be-processed node in a class variable which is checked and updated
188 // whenever a node is removed.
191 tasks_.insert(l, null);
192 TaskList::iterator end (TaskList::current(null));
195 using namespace boost::lambda;
197 var(watchdogCount_) = 0,
201 while (next_ != end) {
202 TaskInfo & task (*next_);
203 if (task.runnable_) {
204 task.runnable_ = false;
205 runningName_ = task.name();
207 runningBacktrace_ = task.backtrace_;
209 TaskList::iterator i (next_);
211 tasks_.splice(l, tasks_, i);
223 prefix_ senf::scheduler::detail::FIFORunner::TaskList::iterator
224 senf::scheduler::detail::FIFORunner::priorityEnd(TaskInfo::Priority p)
227 case senf::scheduler::detail::FIFORunner::TaskInfo::PRIORITY_LOW :
229 case senf::scheduler::detail::FIFORunner::TaskInfo::PRIORITY_NORMAL :
230 return TaskList::current(normalPriorityEnd_);
231 case senf::scheduler::detail::FIFORunner::TaskInfo::PRIORITY_HIGH :
232 return TaskList::current(highPriorityEnd_);
234 return tasks_.begin();
237 prefix_ void senf::scheduler::detail::FIFORunner::watchdog(int, siginfo_t * si, void *)
239 FIFORunner & runner (*static_cast<FIFORunner *>(si->si_value.sival_ptr));
240 if (runner.watchdogCount_ > 0) {
241 ++ runner.watchdogCount_;
242 if (runner.watchdogCount_ > 2) {
243 ++ runner.hangCount_;
244 runner.watchdogError();
249 prefix_ void senf::scheduler::detail::FIFORunner::watchdogError()
251 static char const hex[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
252 'a', 'b', 'c', 'd', 'e', 'f' };
253 static void * entries[SENF_DEBUG_BACKTRACE_NUMCALLERS];
255 // We don't care if the write commands below fail, we just give our best to inform the user
256 senf::IGNORE( write(1, "\n\n*** Scheduler task hanging (pid ",34) );
258 ::snprintf(pid, 7, "%6d", ::getpid());
260 senf::IGNORE( write(1, pid, 6) );
261 senf::IGNORE( write(1, "): ", 3) );
262 senf::IGNORE( write(1, runningName_.c_str(), runningName_.size()) );
263 senf::IGNORE( write(1, " at\n ", 3) );
265 unsigned nEntries( ::backtrace(entries, SENF_DEBUG_BACKTRACE_NUMCALLERS) );
266 for (unsigned i (0); i < nEntries; ++i) {
267 senf::IGNORE( write(1, " 0x", 3) );
268 for (unsigned j (sizeof(void*)); j > 0; --j) {
269 uintptr_t v ( reinterpret_cast<uintptr_t>(entries[i]) >> (8*(j-1)) );
270 senf::IGNORE( write(1, &(hex[ (v >> 4) & 0x0f ]), 1) );
271 senf::IGNORE( write(1, &(hex[ (v ) & 0x0f ]), 1) );
275 senf::IGNORE( write(1, "\n", 1) );
278 senf::IGNORE( write(1, "Task was initialized at\n", 24) );
279 senf::IGNORE( write(1, runningBacktrace_.c_str(), runningBacktrace_.size()) );
281 senf::IGNORE( write(1, "\n", 1) );
286 ///////////////////////////////cc.e////////////////////////////////////////
288 //#include "FIFORunner.mpp"
294 // comment-column: 40
295 // c-file-style: "senf"
296 // indent-tabs-mode: nil
297 // ispell-local-dictionary: "american"
298 // compile-command: "scons -u test"