Scheduler.cpp 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548
  1. #include <AK/TemporaryChange.h>
  2. #include <Kernel/Arch/i386/PIT.h>
  3. #include <Kernel/Devices/PCSpeaker.h>
  4. #include <Kernel/FileSystem/FileDescription.h>
  5. #include <Kernel/Process.h>
  6. #include <Kernel/RTC.h>
  7. #include <Kernel/Scheduler.h>
  8. //#define LOG_EVERY_CONTEXT_SWITCH
  9. //#define SCHEDULER_DEBUG
  10. //#define SCHEDULER_RUNNABLE_DEBUG
  11. static u32 time_slice_for(Process::Priority priority)
  12. {
  13. // One time slice unit == 1ms
  14. switch (priority) {
  15. case Process::HighPriority:
  16. return 50;
  17. case Process::NormalPriority:
  18. return 15;
  19. case Process::LowPriority:
  20. return 5;
  21. case Process::IdlePriority:
  22. return 1;
  23. }
  24. ASSERT_NOT_REACHED();
  25. }
  26. Thread* current;
  27. Thread* g_last_fpu_thread;
  28. Thread* g_finalizer;
  29. static Process* s_colonel_process;
  30. u64 g_uptime;
  31. static u64 s_beep_timeout;
  32. struct TaskRedirectionData {
  33. u16 selector;
  34. TSS32 tss;
  35. };
  36. static TaskRedirectionData s_redirection;
  37. static bool s_active;
  38. bool Scheduler::is_active()
  39. {
  40. return s_active;
  41. }
  42. void Scheduler::beep()
  43. {
  44. PCSpeaker::tone_on(440);
  45. s_beep_timeout = g_uptime + 100;
  46. }
  47. Thread::FileDescriptionBlocker::FileDescriptionBlocker(const FileDescription& description)
  48. : m_blocked_description(description)
  49. {}
  50. const FileDescription& Thread::FileDescriptionBlocker::blocked_description() const
  51. {
  52. return m_blocked_description;
  53. }
  54. Thread::AcceptBlocker::AcceptBlocker(const FileDescription& description)
  55. : FileDescriptionBlocker(description)
  56. {
  57. }
  58. bool Thread::AcceptBlocker::should_unblock(Thread&, time_t, long)
  59. {
  60. auto& socket = *blocked_description().socket();
  61. return socket.can_accept();
  62. }
  63. Thread::ReceiveBlocker::ReceiveBlocker(const FileDescription& description)
  64. : FileDescriptionBlocker(description)
  65. {
  66. }
  67. bool Thread::ReceiveBlocker::should_unblock(Thread&, time_t now_sec, long now_usec)
  68. {
  69. auto& socket = *blocked_description().socket();
  70. // FIXME: Block until the amount of data wanted is available.
  71. bool timed_out = now_sec > socket.receive_deadline().tv_sec || (now_sec == socket.receive_deadline().tv_sec && now_usec >= socket.receive_deadline().tv_usec);
  72. if (timed_out || blocked_description().can_read())
  73. return true;
  74. return false;
  75. }
  76. Thread::ConnectBlocker::ConnectBlocker(const FileDescription& description)
  77. : FileDescriptionBlocker(description)
  78. {
  79. }
  80. bool Thread::ConnectBlocker::should_unblock(Thread&, time_t, long)
  81. {
  82. auto& socket = *blocked_description().socket();
  83. return socket.is_connected();
  84. }
  85. Thread::WriteBlocker::WriteBlocker(const FileDescription& description)
  86. : FileDescriptionBlocker(description)
  87. {
  88. }
  89. bool Thread::WriteBlocker::should_unblock(Thread&, time_t, long)
  90. {
  91. return blocked_description().can_write();
  92. }
  93. Thread::ReadBlocker::ReadBlocker(const FileDescription& description)
  94. : FileDescriptionBlocker(description)
  95. {
  96. }
  97. bool Thread::ReadBlocker::should_unblock(Thread&, time_t, long)
  98. {
  99. // FIXME: Block until the amount of data wanted is available.
  100. return blocked_description().can_read();
  101. }
  102. Thread::ConditionBlocker::ConditionBlocker(const char* state_string, Function<bool()>&& condition)
  103. : m_block_until_condition(move(condition))
  104. , m_state_string(state_string)
  105. {
  106. ASSERT(m_block_until_condition);
  107. }
  108. bool Thread::ConditionBlocker::should_unblock(Thread&, time_t, long)
  109. {
  110. return m_block_until_condition();
  111. }
  112. Thread::SleepBlocker::SleepBlocker(u64 wakeup_time)
  113. : m_wakeup_time(wakeup_time)
  114. {
  115. }
  116. bool Thread::SleepBlocker::should_unblock(Thread&, time_t, long)
  117. {
  118. return m_wakeup_time <= g_uptime;
  119. }
  120. Thread::SelectBlocker::SelectBlocker(const timeval& tv, bool select_has_timeout, const FDVector& read_fds, const FDVector& write_fds, const FDVector& except_fds)
  121. : m_select_timeout(tv)
  122. , m_select_has_timeout(select_has_timeout)
  123. , m_select_read_fds(read_fds)
  124. , m_select_write_fds(write_fds)
  125. , m_select_exceptional_fds(except_fds)
  126. {
  127. }
  128. bool Thread::SelectBlocker::should_unblock(Thread& thread, time_t now_sec, long now_usec)
  129. {
  130. if (m_select_has_timeout) {
  131. if (now_sec > m_select_timeout.tv_sec || (now_sec == m_select_timeout.tv_sec && now_usec >= m_select_timeout.tv_usec))
  132. return true;
  133. }
  134. auto& process = thread.process();
  135. for (int fd : m_select_read_fds) {
  136. if (process.m_fds[fd].description->can_read())
  137. return true;
  138. }
  139. for (int fd : m_select_write_fds) {
  140. if (process.m_fds[fd].description->can_write())
  141. return true;
  142. }
  143. return false;
  144. }
  145. Thread::WaitBlocker::WaitBlocker(int wait_options, pid_t& waitee_pid)
  146. : m_wait_options(wait_options)
  147. , m_waitee_pid(waitee_pid)
  148. {
  149. }
  150. bool Thread::WaitBlocker::should_unblock(Thread& thread, time_t, long)
  151. {
  152. bool should_unblock = false;
  153. thread.process().for_each_child([&](Process& child) {
  154. if (m_waitee_pid != -1 && m_waitee_pid != child.pid())
  155. return IterationDecision::Continue;
  156. bool child_exited = child.is_dead();
  157. bool child_stopped = child.main_thread().state() == Thread::State::Stopped;
  158. bool wait_finished = ((m_wait_options & WEXITED) && child_exited)
  159. || ((m_wait_options & WSTOPPED) && child_stopped);
  160. if (!wait_finished)
  161. return IterationDecision::Continue;
  162. m_waitee_pid = child.pid();
  163. should_unblock = true;
  164. return IterationDecision::Break;
  165. });
  166. return should_unblock;
  167. }
  168. Thread::SemiPermanentBlocker::SemiPermanentBlocker(Reason reason)
  169. : m_reason(reason)
  170. {}
  171. bool Thread::SemiPermanentBlocker::should_unblock(Thread&, time_t, long)
  172. {
  173. // someone else has to unblock us
  174. return false;
  175. }
  176. // Called by the scheduler on threads that are blocked for some reason.
  177. // Make a decision as to whether to unblock them or not.
  178. void Thread::consider_unblock(time_t now_sec, long now_usec)
  179. {
  180. switch (state()) {
  181. case Thread::Invalid:
  182. case Thread::Runnable:
  183. case Thread::Running:
  184. case Thread::Dead:
  185. case Thread::Stopped:
  186. /* don't know, don't care */
  187. return;
  188. case Thread::Blocked:
  189. ASSERT(m_blocker);
  190. if (m_blocker->should_unblock(*this, now_sec, now_usec))
  191. unblock();
  192. return;
  193. case Thread::Skip1SchedulerPass:
  194. set_state(Thread::Skip0SchedulerPasses);
  195. return;
  196. case Thread::Skip0SchedulerPasses:
  197. set_state(Thread::Runnable);
  198. return;
  199. case Thread::Dying:
  200. ASSERT(g_finalizer);
  201. if (g_finalizer->is_blocked())
  202. g_finalizer->unblock();
  203. return;
  204. }
  205. }
  206. bool Scheduler::pick_next()
  207. {
  208. ASSERT_INTERRUPTS_DISABLED();
  209. ASSERT(!s_active);
  210. TemporaryChange<bool> change(s_active, true);
  211. ASSERT(s_active);
  212. if (!current) {
  213. // XXX: The first ever context_switch() goes to the idle process.
  214. // This to setup a reliable place we can return to.
  215. return context_switch(s_colonel_process->main_thread());
  216. }
  217. struct timeval now;
  218. kgettimeofday(now);
  219. auto now_sec = now.tv_sec;
  220. auto now_usec = now.tv_usec;
  221. // Check and unblock threads whose wait conditions have been met.
  222. Thread::for_each_nonrunnable([&](Thread& thread) {
  223. thread.consider_unblock(now_sec, now_usec);
  224. return IterationDecision::Continue;
  225. });
  226. Process::for_each([&](Process& process) {
  227. if (process.is_dead()) {
  228. if (current != &process.main_thread() && (!process.ppid() || !Process::from_pid(process.ppid()))) {
  229. auto name = process.name();
  230. auto pid = process.pid();
  231. auto exit_status = Process::reap(process);
  232. dbgprintf("reaped unparented process %s(%u), exit status: %u\n", name.characters(), pid, exit_status);
  233. }
  234. return IterationDecision::Continue;
  235. }
  236. if (process.m_alarm_deadline && g_uptime > process.m_alarm_deadline) {
  237. process.m_alarm_deadline = 0;
  238. process.send_signal(SIGALRM, nullptr);
  239. }
  240. return IterationDecision::Continue;
  241. });
  242. // Dispatch any pending signals.
  243. // FIXME: Do we really need this to be a separate pass over the process list?
  244. Thread::for_each_living([](Thread& thread) -> IterationDecision {
  245. if (!thread.has_unmasked_pending_signals())
  246. return IterationDecision::Continue;
  247. // FIXME: It would be nice if the Scheduler didn't have to worry about who is "current"
  248. // For now, avoid dispatching signals to "current" and do it in a scheduling pass
  249. // while some other process is interrupted. Otherwise a mess will be made.
  250. if (&thread == current)
  251. return IterationDecision::Continue;
  252. // We know how to interrupt blocked processes, but if they are just executing
  253. // at some random point in the kernel, let them continue. They'll be in userspace
  254. // sooner or later and we can deliver the signal then.
  255. // FIXME: Maybe we could check when returning from a syscall if there's a pending
  256. // signal and dispatch it then and there? Would that be doable without the
  257. // syscall effectively being "interrupted" despite having completed?
  258. if (thread.in_kernel() && !thread.is_blocked() && !thread.is_stopped())
  259. return IterationDecision::Continue;
  260. // NOTE: dispatch_one_pending_signal() may unblock the process.
  261. bool was_blocked = thread.is_blocked();
  262. if (thread.dispatch_one_pending_signal() == ShouldUnblockThread::No)
  263. return IterationDecision::Continue;
  264. if (was_blocked) {
  265. dbgprintf("Unblock %s(%u) due to signal\n", thread.process().name().characters(), thread.pid());
  266. ASSERT(thread.m_blocker);
  267. thread.m_blocker->set_interrupted_by_signal();
  268. thread.unblock();
  269. }
  270. return IterationDecision::Continue;
  271. });
  272. #ifdef SCHEDULER_RUNNABLE_DEBUG
  273. dbgprintf("Non-runnables:\n");
  274. Thread::for_each_nonrunnable([](Thread& thread) -> IterationDecision {
  275. auto& process = thread.process();
  276. dbgprintf("[K%x] %-12s %s(%u:%u) @ %w:%x\n", &process, thread.state_string(), process.name().characters(), process.pid(), thread.tid(), thread.tss().cs, thread.tss().eip);
  277. return IterationDecision::Continue;
  278. });
  279. dbgprintf("Runnables:\n");
  280. Thread::for_each_runnable([](Thread& thread) -> IterationDecision {
  281. auto& process = thread.process();
  282. dbgprintf("[K%x] %-12s %s(%u:%u) @ %w:%x\n", &process, thread.state_string(), process.name().characters(), process.pid(), thread.tid(), thread.tss().cs, thread.tss().eip);
  283. return IterationDecision::Continue;
  284. });
  285. #endif
  286. auto& runnable_list = *Thread::g_runnable_threads;
  287. if (runnable_list.is_empty())
  288. return context_switch(s_colonel_process->main_thread());
  289. auto* previous_head = runnable_list.first();
  290. for (;;) {
  291. // Move head to tail.
  292. runnable_list.append(*previous_head);
  293. auto* thread = runnable_list.first();
  294. if (!thread->process().is_being_inspected() && (thread->state() == Thread::Runnable || thread->state() == Thread::Running)) {
  295. #ifdef SCHEDULER_DEBUG
  296. dbgprintf("switch to %s(%u:%u) @ %w:%x\n", thread->process().name().characters(), thread->process().pid(), thread->tid(), thread->tss().cs, thread->tss().eip);
  297. #endif
  298. return context_switch(*thread);
  299. }
  300. if (thread == previous_head) {
  301. // Back at process_head, nothing wants to run. Send in the colonel!
  302. return context_switch(s_colonel_process->main_thread());
  303. }
  304. }
  305. }
  306. bool Scheduler::donate_to(Thread* beneficiary, const char* reason)
  307. {
  308. InterruptDisabler disabler;
  309. if (!Thread::is_thread(beneficiary))
  310. return false;
  311. (void)reason;
  312. unsigned ticks_left = current->ticks_left();
  313. if (!beneficiary || beneficiary->state() != Thread::Runnable || ticks_left <= 1)
  314. return yield();
  315. unsigned ticks_to_donate = min(ticks_left - 1, time_slice_for(beneficiary->process().priority()));
  316. #ifdef SCHEDULER_DEBUG
  317. dbgprintf("%s(%u:%u) donating %u ticks to %s(%u:%u), reason=%s\n", current->process().name().characters(), current->pid(), current->tid(), ticks_to_donate, beneficiary->process().name().characters(), beneficiary->pid(), beneficiary->tid(), reason);
  318. #endif
  319. context_switch(*beneficiary);
  320. beneficiary->set_ticks_left(ticks_to_donate);
  321. switch_now();
  322. return false;
  323. }
  324. bool Scheduler::yield()
  325. {
  326. InterruptDisabler disabler;
  327. ASSERT(current);
  328. // dbgprintf("%s(%u:%u) yield()\n", current->process().name().characters(), current->pid(), current->tid());
  329. if (!pick_next())
  330. return false;
  331. // dbgprintf("yield() jumping to new process: sel=%x, %s(%u:%u)\n", current->far_ptr().selector, current->process().name().characters(), current->pid(), current->tid());
  332. switch_now();
  333. return true;
  334. }
  335. void Scheduler::pick_next_and_switch_now()
  336. {
  337. bool someone_wants_to_run = pick_next();
  338. ASSERT(someone_wants_to_run);
  339. switch_now();
  340. }
  341. void Scheduler::switch_now()
  342. {
  343. Descriptor& descriptor = get_gdt_entry(current->selector());
  344. descriptor.type = 9;
  345. flush_gdt();
  346. asm("sti\n"
  347. "ljmp *(%%eax)\n" ::"a"(&current->far_ptr()));
  348. }
  349. bool Scheduler::context_switch(Thread& thread)
  350. {
  351. thread.set_ticks_left(time_slice_for(thread.process().priority()));
  352. thread.did_schedule();
  353. if (current == &thread)
  354. return false;
  355. if (current) {
  356. // If the last process hasn't blocked (still marked as running),
  357. // mark it as runnable for the next round.
  358. if (current->state() == Thread::Running)
  359. current->set_state(Thread::Runnable);
  360. #ifdef LOG_EVERY_CONTEXT_SWITCH
  361. dbgprintf("Scheduler: %s(%u:%u) -> %s(%u:%u) %w:%x\n",
  362. current->process().name().characters(), current->process().pid(), current->tid(),
  363. thread.process().name().characters(), thread.process().pid(), thread.tid(),
  364. thread.tss().cs, thread.tss().eip);
  365. #endif
  366. }
  367. current = &thread;
  368. thread.set_state(Thread::Running);
  369. if (!thread.selector()) {
  370. thread.set_selector(gdt_alloc_entry());
  371. auto& descriptor = get_gdt_entry(thread.selector());
  372. descriptor.set_base(&thread.tss());
  373. descriptor.set_limit(0xffff);
  374. descriptor.dpl = 0;
  375. descriptor.segment_present = 1;
  376. descriptor.granularity = 1;
  377. descriptor.zero = 0;
  378. descriptor.operation_size = 1;
  379. descriptor.descriptor_type = 0;
  380. }
  381. auto& descriptor = get_gdt_entry(thread.selector());
  382. descriptor.type = 11; // Busy TSS
  383. flush_gdt();
  384. return true;
  385. }
  386. static void initialize_redirection()
  387. {
  388. auto& descriptor = get_gdt_entry(s_redirection.selector);
  389. descriptor.set_base(&s_redirection.tss);
  390. descriptor.set_limit(0xffff);
  391. descriptor.dpl = 0;
  392. descriptor.segment_present = 1;
  393. descriptor.granularity = 1;
  394. descriptor.zero = 0;
  395. descriptor.operation_size = 1;
  396. descriptor.descriptor_type = 0;
  397. descriptor.type = 9;
  398. flush_gdt();
  399. }
  400. void Scheduler::prepare_for_iret_to_new_process()
  401. {
  402. auto& descriptor = get_gdt_entry(s_redirection.selector);
  403. descriptor.type = 9;
  404. s_redirection.tss.backlink = current->selector();
  405. load_task_register(s_redirection.selector);
  406. }
  407. void Scheduler::prepare_to_modify_tss(Thread& thread)
  408. {
  409. // This ensures that a currently running process modifying its own TSS
  410. // in order to yield() and end up somewhere else doesn't just end up
  411. // right after the yield().
  412. if (current == &thread)
  413. load_task_register(s_redirection.selector);
  414. }
  415. Process* Scheduler::colonel()
  416. {
  417. return s_colonel_process;
  418. }
  419. void Scheduler::initialize()
  420. {
  421. s_redirection.selector = gdt_alloc_entry();
  422. initialize_redirection();
  423. s_colonel_process = Process::create_kernel_process("colonel", nullptr);
  424. // Make sure the colonel uses a smallish time slice.
  425. s_colonel_process->set_priority(Process::IdlePriority);
  426. load_task_register(s_redirection.selector);
  427. }
  428. void Scheduler::timer_tick(RegisterDump& regs)
  429. {
  430. if (!current)
  431. return;
  432. ++g_uptime;
  433. if (s_beep_timeout && g_uptime > s_beep_timeout) {
  434. PCSpeaker::tone_off();
  435. s_beep_timeout = 0;
  436. }
  437. if (current->tick())
  438. return;
  439. current->tss().gs = regs.gs;
  440. current->tss().fs = regs.fs;
  441. current->tss().es = regs.es;
  442. current->tss().ds = regs.ds;
  443. current->tss().edi = regs.edi;
  444. current->tss().esi = regs.esi;
  445. current->tss().ebp = regs.ebp;
  446. current->tss().ebx = regs.ebx;
  447. current->tss().edx = regs.edx;
  448. current->tss().ecx = regs.ecx;
  449. current->tss().eax = regs.eax;
  450. current->tss().eip = regs.eip;
  451. current->tss().cs = regs.cs;
  452. current->tss().eflags = regs.eflags;
  453. // Compute process stack pointer.
  454. // Add 12 for CS, EIP, EFLAGS (interrupt mechanic)
  455. current->tss().esp = regs.esp + 12;
  456. current->tss().ss = regs.ss;
  457. if ((current->tss().cs & 3) != 0) {
  458. current->tss().ss = regs.ss_if_crossRing;
  459. current->tss().esp = regs.esp_if_crossRing;
  460. }
  461. if (!pick_next())
  462. return;
  463. prepare_for_iret_to_new_process();
  464. // Set the NT (nested task) flag.
  465. asm(
  466. "pushf\n"
  467. "orl $0x00004000, (%esp)\n"
  468. "popf\n");
  469. }