kernel/core/thread.cc

   1 // core/thread.cc -- Scheduler and thread creation/destruction
   2 //
   3 // This software is copyright (c) 2006 Scott Wood <scott@buserror.net>.
   4 //
   5 // Permission is hereby granted, free of charge, to any person obtaining a copy of
   6 // this software and associated documentation files (the "Software"), to deal with
   7 // the Software without restriction, including without limitation the rights to
   8 // use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
   9 // of the Software, and to permit persons to whom the Software is furnished to do
  10 // so, subject to the following condition:
  11 //
  12 // The above copyright notice and this permission notice shall be
  13 // included in all copies or substantial portions of the Software.
  14 //
  15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
  17 // FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  18 // CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
  21 // SOFTWARE.
  22
  23 #include <kern/thread.h>
  24 #include <kern/pagealloc.h>
  25 #include <kern/time.h>
  26 #include <kern/arch.h>
  27 #include <kern/irq.h>
  28 #include <lowlevel/bitops.h>
  29
  30 using namespace Lock;
  31
  32 namespace Threads {
  33         Thread *Sched::best_rt(int prio)
  34         {
  35                 Util::List *rq = &rt_runqueue[prio];
  36                 assert(!rq->empty());
  37
  38                 return rq->next->listentry(Thread, runqueue_node);
  39         }
  40
  41         void Sched::replenish_all()
  42         {
  43                 // All runnable tasks have depleted timeslices, so mark
  44                 // all depleted prios active.  Replenishment will happen
  45                 // lazily.
  46
  47                 last_replenish++;
  48                 ts_bitmap = ts_depleted_bitmap;
  49                 ts_depleted_bitmap = 0;
  50         }
  51
  52         void Sched::replenish_prio(int prio)
  53         {
  54                 // Move the depleted marker to the end, effectively moving
  55                 // all other tasks to the active list at once.
  56
  57                 ts_depleted[prio].del();
  58                 ts_runqueue[prio].add_back(&ts_depleted[prio]);
  59         }
  60
  61         void Thread::ts_add()
  62         {
  63                 assert(runqueue_node.empty());
  64
  65                 if (time_left) {
  66                         // This puts it at the end of the active list, not depleted.
  67                         sched.ts_depleted[ts_prio].add_back(&runqueue_node);
  68                 } else {
  69                         sched.ts_runqueue[ts_prio].add_back(&runqueue_node);
  70                 }
  71
  72                 sched.ts_bitmap |= 1 << (Sched::ts_prios - 1 - ts_prio);
  73         }
  74
  75         void Thread::ts_del()
  76         {
  77                 runqueue_node.del();
  78
  79                 if (sched.ts_runqueue[ts_prio].next == &sched.ts_depleted[ts_prio])
  80                         sched.ts_bitmap &= ~(1 << (Sched::ts_prios - 1 - ts_prio));
  81                 if (sched.ts_depleted[ts_prio].next == &sched.ts_runqueue[ts_prio])
  82                         sched.ts_depleted_bitmap &= ~(1 << (Sched::ts_prios - 1 - ts_prio));
  83         }
  84
  85         void Thread::ts_deplete()
  86         {
  87                 runqueue_node.del();
  88
  89                 if (sched.ts_runqueue[ts_prio].next == &sched.ts_depleted[ts_prio])
  90                         sched.ts_bitmap &= ~(1 << (Sched::ts_prios - 1 - ts_prio));
  91
  92                 // This puts it at the end of the depleted list, not active.
  93                 sched.ts_runqueue[ts_prio].add_back(&runqueue_node);
  94                 sched.ts_depleted_bitmap |= 1 << (Sched::ts_prios - 1 - ts_prio);
  95         }
  96
  97         inline void Thread::add()
  98         {
  99                 if (policy == TimeShared) {
 100                         prio_adjust();
 101                         ts_add();
 102                 } else {
 103                         sched.rt_runqueue[rt_prio].add_back(&runqueue_node);
 104                 }
 105
 106                 ll_multiword_set_bit(sched.bitmap, Sched::rt_prios - 1 - rt_prio);
 107         }
 108
 109         inline void Thread::del()
 110         {
 111                 if (policy == TimeShared) {
 112                         ts_del();
 113
 114                         if (!sched.ts_bitmap && !sched.ts_depleted_bitmap)
 115                                 ll_multiword_clear_bit(sched.bitmap, Sched::rt_prios - 1);
 116                 } else {
 117                         runqueue_node.del();
 118
 119                         if (sched.rt_runqueue[rt_prio].empty())
 120                                 ll_multiword_clear_bit(sched.bitmap, Sched::rt_prios - 1 - rt_prio);
 121                 }
 122         }
 123
 124         inline u32 Sched::prio_to_slice(int prio)
 125         {
 126                 assert(prio >= 1 && prio < ts_prios);
 127                 return prio * default_timeslice / 8;
 128         }
 129
 130         int Sched::slice_to_prio(u32 slice)
 131         {
 132                 return slice * 8 / default_timeslice;
 133         }
 134
 135         void Thread::prio_adjust()
 136         {
 137                 assert(runqueue_node.empty());
 138
 139                 if (last_replenish != sched.last_replenish) {
 140                         if (sched.last_replenish - last_replenish > 3) {
 141                                 time_left = time_slice * 2 - 1;
 142                         } else while (sched.last_replenish != last_replenish) {
 143                                 time_left = time_left / 2 + time_slice;
 144                                 assert(time_left < (s32)time_slice * 2);
 145                                 last_replenish++;
 146                         }
 147
 148                         last_replenish = sched.last_replenish;
 149
 150                         int new_prio = Sched::slice_to_prio(time_left);
 151
 152                         if (!(new_prio >= ts_static_prio && new_prio < Sched::ts_prios)) {
 153                                 printf("new prio %d, static %d, time left %d\n",
 154                                        new_prio, ts_static_prio, time_left);
 155                         }
 156
 157                         assert(new_prio >= ts_static_prio && new_prio < Sched::ts_prios);
 158                         ts_prio = new_prio;
 159                 }
 160         }
 161
 162         void Thread::replenish()
 163         {
 164                 assert(!runqueue_node.empty());
 165
 166                 if (last_replenish != sched.last_replenish) {
 167                         assert(time_left == 0);
 168                         time_left = time_slice;
 169                         last_replenish = sched.last_replenish;
 170
 171                         if (ts_static_prio != ts_prio) {
 172                                 assert(ts_static_prio < ts_prio);
 173                                 ts_del();
 174                                 ts_prio = ts_static_prio;
 175                                 ts_add();
 176                         }
 177                 }
 178         }
 179
 180         Thread *Sched::best_ts()
 181         {
 182                 if (!ts_bitmap)
 183                         replenish_all();
 184
 185                 assert(ts_bitmap);
 186                 int best = ts_prios - 1 - ll_ffs(ts_bitmap);
 187                 assert(best >= 1 && best < ts_prios);
 188
 189                 if (ts_runqueue[best].next == &ts_depleted[best])
 190                         replenish_prio(best);
 191
 192                 assert(ts_runqueue[best].next != &ts_depleted[best]);
 193                 assert(!ts_runqueue[best].empty());
 194                 Thread *t = ts_runqueue[best].next->listentry(Thread, runqueue_node);
 195
 196                 assert(!t->blocked_on);
 197                 assert(t->policy == Thread::TimeShared);
 198                 assert(t->rt_prio == 0);
 199                 assert(t->ts_prio == best);
 200
 201                 // The replenish can lower the threads priority if it was boosted;
 202                 // in some cases, this may mean that a different thread is now the
 203                 // highest priority thread.  As these aren't real-time threads, and
 204                 // as priorities are mainly to determine which threads can take the
 205                 // CPU immediately on wakeup rather than which CPU hog goes first,
 206                 // it's not important enough to worry about; the new priority will
 207                 // be used on the next schedule.
 208
 209                 t->replenish();
 210                 return t;
 211         }
 212
 213         void Sched::schedule_nolock()
 214         {
 215                 assert(!IRQ::in_irq);
 216                 need_resched = 0;
 217                 int rt = rt_prios - 1 - ll_multiword_ffs(bitmap, 0, rt_prios);
 218                 Thread *best;
 219
 220                 Time::Time now;
 221                 Time::monotonic_clock.get_time(&now);
 222
 223                 if (curthread != Arch::init_thread)
 224                         curthread->charge(now);
 225
 226                 if (rt == rt_prios)
 227                         best = Arch::init_thread;
 228                 else if (rt == 0)
 229                         best = best_ts();
 230                 else
 231                         best = best_rt(rt);
 232
 233                 if (best != curthread) {
 234                         if (best != Arch::init_thread) {
 235                                 best->last_time = now;
 236                                 Time::Time expiry = now + best->time_left;
 237                                 resched_timer.arm(expiry);
 238                         }
 239
 240                         Arch::switch_thread(best, curthread);
 241                 }
 242         }
 243
 244         void Sched::schedule()
 245         {
 246                 AutoSpinLockRecIRQ autolock(runqueue_lock);
 247                 schedule_nolock();
 248         }
 249
 250         void Sched::sched_new_thread()
 251         {
 252                 runqueue_lock.unlock_irq();
 253         }
 254
 255         Thread *Sched::new_thread(thread_func func, void *arg, char *name)
 256         {
 257                 // Allocate a page for the thread's stack, and stick the thread
 258                 // struct at the top of the stack.  It's placed at the top rather
 259                 // than the bottom to facilitate the possible eventual use of guard
 260                 // pages.
 261
 262                 Mem::Page *page = Mem::PageAlloc::alloc(1);
 263                 ulong addr = reinterpret_cast<ulong>(Mem::page_to_kvirt(page));
 264                 addr += Arch::ArchThread::size - thread_size;
 265
 266                 Thread *t = reinterpret_cast<Thread *>(addr);
 267
 268                 // Use placement new to run the constructors of lists
 269                 // (and any other self-constructing type that may be
 270                 // added).
 271
 272                 new(t) Thread;
 273
 274                 // FIXME: settable schedparams
 275
 276                 t->time_left = Sched::default_timeslice;
 277                 t->policy = Thread::TimeShared;
 278                 t->rt_prio = 0;
 279                 t->ts_static_prio = 8;
 280                 t->ts_prio = 8;
 281                 t->time_slice = prio_to_slice(t->ts_prio);
 282                 t->blocked_on = NULL;
 283                 t->last_replenish = 0;
 284                 t->addr_space = NULL;
 285                 t->active_addr_space = NULL;
 286
 287                 t->arch.init(reinterpret_cast<void *>(func), arg);
 288
 289                 if (name)
 290                         strncpy(t->name, name, Thread::name_len);
 291
 292                 threadlist_lock.lock_irq();
 293                 threadlist.add_back(&t->threadlist_node);
 294                 threadlist_lock.unlock_irq();
 295
 296                 return t;
 297         }
 298
 299         static void do_resched_timer(Time::KTimerEntry *timer)
 300         {
 301                 need_resched = 1;
 302         }
 303
 304         void Sched::init()
 305         {
 306                 assert(curthread == Arch::init_thread);
 307
 308                 resched_timer.mux = Time::monotonic_timers;
 309                 resched_timer.func = do_resched_timer;
 310                 resched_timer.data = NULL;
 311
 312                 for (int i = 0; i < ts_prios; i++)
 313                         ts_runqueue[i].add_front(&ts_depleted[i]);
 314
 315                 strcpy(curthread->name, "idle thread");
 316         }
 317
 318         Thread::~Thread()
 319         {
 320                 sched.threadlist_lock.lock_irq();
 321                 threadlist_node.del();
 322                 sched.threadlist_lock.unlock_irq();
 323
 324                 ulong addr = reinterpret_cast<ulong>(this);
 325                 addr &= ~(Arch::ArchThread::size - 1);
 326                 Mem::Page *page = Mem::kvirt_to_page(reinterpret_cast<void *>(addr));
 327                 Mem::PageAlloc::free(page, 1);
 328         }
 329
 330         void Thread::exit()
 331         {
 332                 printf("thread %p exiting...\n", this);
 333                 for(;;);
 334         }
 335
 336         void Thread::block(ThreadBlocker *blocker)
 337         {
 338                 AutoSpinLockRecIRQ autolock(sched.runqueue_lock);
 339                 assert(!runqueue_node.empty());
 340                 assert(!blocked_on);
 341                 assert(!IRQ::in_irq);
 342
 343                 if (blocker->blocked) {
 344                         blocked_on = blocker;
 345                         del();
 346                         assert(runqueue_node.empty());
 347                         sched.schedule_nolock();
 348                 }
 349         }
 350
 351         void Thread::wake_nolock()
 352         {
 353                 blocked_on = NULL;
 354
 355                 if (runqueue_node.empty()) {
 356                         add();
 357                         need_resched = 1;
 358                 }
 359         }
 360
 361         void Thread::wake()
 362         {
 363                 ulong irq = sched.runqueue_lock.lock_recirq();
 364                 wake_nolock();
 365                 sched.runqueue_lock.unlock_recirq(irq);
 366
 367                 if (ll_get_int_state() && need_resched)
 368                         sched.schedule();
 369         }
 370
 371         void Thread::charge(Time::Time &now)
 372         {
 373                 Time::Time ival;
 374                 ival = now - last_time;
 375                 last_time = now;
 376
 377                 if (ival.seconds != 0) {
 378                         time_left = 0;
 379                 } else {
 380                         time_left -= ival.nanos;
 381
 382                         if (time_left < 0)
 383                                 time_left = 0;
 384                 }
 385
 386                 if (!blocked_on && time_left == 0 && policy != FIFO) {
 387                         if (policy == TimeShared) {
 388                                 ts_deplete();
 389                         } else {
 390                                 del();
 391                                 add();
 392                         }
 393                 }
 394         }
 395
 396         void Thread::set_aspace(Mem::AddrSpace *aspace)
 397         {
 398                 // FIXME: lock thread against scheduling; this temporary method should
 399                 // be gone before SMP anyway.
 400
 401                 ll_ints_off();
 402                 addr_space = active_addr_space = aspace;
 403                 Arch::set_aspace(aspace);
 404                 ll_ints_on();
 405         }
 406
 407         void ThreadBlocker::wake()
 408         {
 409                 blocked = false;
 410                 thread->wake();
 411         }
 412
 413         void CascadeBlocker::wake()
 414         {
 415                 blocked = false;
 416                 blocker->wake();
 417         }
 418
 419         void ThreadBlocker::unblock()
 420         {
 421                 blocked = false;
 422         }
 423
 424         void CascadeBlocker::unblock()
 425         {
 426                 blocked = false;
 427                 blocker->unblock();
 428         }
 429
 430         void WaitQueue::block(Blocker *blocker)
 431         {
 432                 AutoSpinLockRecIRQ autolock(lock);
 433                 blockers.add_back(&blocker->list_node);
 434         }
 435
 436         void WaitQueue::unblock(Blocker *blocker)
 437         {
 438                 AutoSpinLockRecIRQ autolock(lock);
 439                 blocker->list_node.del();
 440         }
 441
 442         bool WaitQueue::empty()
 443         {
 444                 AutoSpinLockRecIRQ autolock(lock);
 445                 return blockers.empty();
 446         }
 447
 448         Blocker *WaitQueue::unblock_one_nolock()
 449         {
 450                 AutoSpinLock schedautolock(sched.runqueue_lock);
 451
 452                 int best_rt = -1;
 453                 int best_ts = 0;
 454                 Blocker *best = NULL;
 455
 456                 for (Util::List *node = blockers.next; node != &blockers;
 457                      node = node->next)
 458                 {
 459                         Blocker *b = node->listentry(Blocker, list_node);
 460                         Thread *t = b->thread;
 461
 462                         if (best_rt < t->rt_prio) {
 463                                 best_rt = t->rt_prio;
 464                                 best_ts = t->ts_prio;
 465                                 best = b;
 466                         }
 467
 468                         if (best_rt == t->rt_prio && best_rt == 0 && best_ts < t->ts_prio) {
 469                                 best_ts = t->ts_prio;
 470                                 best = b;
 471                         }
 472                 }
 473
 474                 if (best)
 475                         best->list_node.del();
 476
 477                 return best;
 478         }
 479
 480         Blocker *WaitQueue::unblock_one()
 481         {
 482                 AutoSpinLockRecIRQ autolock(lock);
 483                 return unblock_one_nolock();
 484         }
 485
 486         bool WaitQueue::wake_one()
 487         {
 488                 // The lock is held over the wake to make sure that we still
 489                 // have a valid reference to best.  For external calls to
 490                 // unblock_one(), the caller must use its own locks (or other
 491                 // mechanisms) to ensure that the blocker is still valid.
 492
 493                 ulong irq = lock.lock_recirq();
 494                 Blocker *best = unblock_one_nolock();
 495
 496                 if (best)
 497                         best->wake();
 498
 499                 lock.unlock_recirq(irq);
 500
 501                 if (ll_get_int_state() && need_resched)
 502                         sched.schedule();
 503
 504                 return false;
 505         }
 506
 507         int WaitQueue::wake_all()
 508         {
 509                 ulong irq = lock.lock_recirq();
 510                 sched.runqueue_lock.lock();
 511                 int count = 0;
 512
 513                 for (Util::List *node = blockers.next; node != &blockers;
 514                      node = node->next)
 515                 {
 516                         Blocker *b = node->listentry(Blocker, list_node);
 517                         b->unblock();
 518                         b->thread->wake_nolock();
 519                         b->list_node.del();
 520                         count++;
 521                 }
 522
 523                 sched.runqueue_lock.unlock();
 524                 lock.unlock_recirq(irq);
 525
 526                 if (ll_get_int_state() && need_resched)
 527                         sched.schedule();
 528
 529                 return count;
 530         }
 531
 532         Sched sched;
 533 }
 534
 535 extern "C" void exit_thread()
 536 {
 537         curthread->exit();
 538         assertl(0, Assert::Always);
 539 }
 540
 541 extern "C" void sched_new_thread()
 542 {
 543         Threads::sched.sched_new_thread();
 544 }
 545
 546 extern "C" void schedule()
 547 {
 548         Threads::sched.schedule();
 549 }
 550
 551 int need_resched;