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