Scheduler.cpp 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673
  1. /*
  2. * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
  3. * All rights reserved.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. *
  8. * 1. Redistributions of source code must retain the above copyright notice, this
  9. * list of conditions and the following disclaimer.
  10. *
  11. * 2. Redistributions in binary form must reproduce the above copyright notice,
  12. * this list of conditions and the following disclaimer in the documentation
  13. * and/or other materials provided with the distribution.
  14. *
  15. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  16. * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18. * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  19. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  21. * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  22. * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  23. * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24. * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25. */
  26. #include <AK/QuickSort.h>
  27. #include <AK/TemporaryChange.h>
  28. #include <Kernel/FileSystem/FileDescription.h>
  29. #include <Kernel/Net/Socket.h>
  30. #include <Kernel/Process.h>
  31. #include <Kernel/Profiling.h>
  32. #include <Kernel/RTC.h>
  33. #include <Kernel/Scheduler.h>
  34. #include <Kernel/Time/TimeManagement.h>
  35. #include <Kernel/TimerQueue.h>
  36. //#define LOG_EVERY_CONTEXT_SWITCH
  37. //#define SCHEDULER_DEBUG
  38. //#define SCHEDULER_RUNNABLE_DEBUG
  39. namespace Kernel {
  40. SchedulerData* g_scheduler_data;
  41. timeval g_timeofday;
  42. RecursiveSpinLock g_scheduler_lock;
  43. void Scheduler::init_thread(Thread& thread)
  44. {
  45. ASSERT(g_scheduler_data);
  46. g_scheduler_data->m_nonrunnable_threads.append(thread);
  47. }
  48. void Scheduler::update_state_for_thread(Thread& thread)
  49. {
  50. ASSERT_INTERRUPTS_DISABLED();
  51. ASSERT(g_scheduler_data);
  52. auto& list = g_scheduler_data->thread_list_for_state(thread.state());
  53. if (list.contains(thread))
  54. return;
  55. list.append(thread);
  56. }
  57. static u32 time_slice_for(const Thread& thread)
  58. {
  59. // One time slice unit == 1ms
  60. if (&thread == Processor::current().idle_thread())
  61. return 1;
  62. return 10;
  63. }
  64. timeval Scheduler::time_since_boot()
  65. {
  66. return { TimeManagement::the().seconds_since_boot(), (suseconds_t)TimeManagement::the().ticks_this_second() * 1000 };
  67. }
  68. Thread* g_finalizer;
  69. WaitQueue* g_finalizer_wait_queue;
  70. Atomic<bool> g_finalizer_has_work{false};
  71. static Process* s_colonel_process;
  72. u64 g_uptime;
  73. Thread::JoinBlocker::JoinBlocker(Thread& joinee, void*& joinee_exit_value)
  74. : m_joinee(joinee)
  75. , m_joinee_exit_value(joinee_exit_value)
  76. {
  77. ASSERT(m_joinee.m_joiner == nullptr);
  78. auto current_thread = Thread::current();
  79. m_joinee.m_joiner = current_thread;
  80. current_thread->m_joinee = &joinee;
  81. }
  82. bool Thread::JoinBlocker::should_unblock(Thread& joiner, time_t, long)
  83. {
  84. return !joiner.m_joinee;
  85. }
  86. Thread::FileDescriptionBlocker::FileDescriptionBlocker(const FileDescription& description)
  87. : m_blocked_description(description)
  88. {
  89. }
  90. const FileDescription& Thread::FileDescriptionBlocker::blocked_description() const
  91. {
  92. return m_blocked_description;
  93. }
  94. Thread::AcceptBlocker::AcceptBlocker(const FileDescription& description)
  95. : FileDescriptionBlocker(description)
  96. {
  97. }
  98. bool Thread::AcceptBlocker::should_unblock(Thread&, time_t, long)
  99. {
  100. auto& socket = *blocked_description().socket();
  101. return socket.can_accept();
  102. }
  103. Thread::ConnectBlocker::ConnectBlocker(const FileDescription& description)
  104. : FileDescriptionBlocker(description)
  105. {
  106. }
  107. bool Thread::ConnectBlocker::should_unblock(Thread&, time_t, long)
  108. {
  109. auto& socket = *blocked_description().socket();
  110. return socket.setup_state() == Socket::SetupState::Completed;
  111. }
  112. Thread::WriteBlocker::WriteBlocker(const FileDescription& description)
  113. : FileDescriptionBlocker(description)
  114. {
  115. if (description.is_socket()) {
  116. auto& socket = *description.socket();
  117. if (socket.has_send_timeout()) {
  118. timeval deadline = Scheduler::time_since_boot();
  119. deadline.tv_sec += socket.send_timeout().tv_sec;
  120. deadline.tv_usec += socket.send_timeout().tv_usec;
  121. deadline.tv_sec += (socket.send_timeout().tv_usec / 1000000) * 1;
  122. deadline.tv_usec %= 1000000;
  123. m_deadline = deadline;
  124. }
  125. }
  126. }
  127. bool Thread::WriteBlocker::should_unblock(Thread&, time_t now_sec, long now_usec)
  128. {
  129. if (m_deadline.has_value()) {
  130. bool timed_out = now_sec > m_deadline.value().tv_sec || (now_sec == m_deadline.value().tv_sec && now_usec >= m_deadline.value().tv_usec);
  131. return timed_out || blocked_description().can_write();
  132. }
  133. return blocked_description().can_write();
  134. }
  135. Thread::ReadBlocker::ReadBlocker(const FileDescription& description)
  136. : FileDescriptionBlocker(description)
  137. {
  138. if (description.is_socket()) {
  139. auto& socket = *description.socket();
  140. if (socket.has_receive_timeout()) {
  141. timeval deadline = Scheduler::time_since_boot();
  142. deadline.tv_sec += socket.receive_timeout().tv_sec;
  143. deadline.tv_usec += socket.receive_timeout().tv_usec;
  144. deadline.tv_sec += (socket.receive_timeout().tv_usec / 1000000) * 1;
  145. deadline.tv_usec %= 1000000;
  146. m_deadline = deadline;
  147. }
  148. }
  149. }
  150. bool Thread::ReadBlocker::should_unblock(Thread&, time_t now_sec, long now_usec)
  151. {
  152. if (m_deadline.has_value()) {
  153. bool timed_out = now_sec > m_deadline.value().tv_sec || (now_sec == m_deadline.value().tv_sec && now_usec >= m_deadline.value().tv_usec);
  154. return timed_out || blocked_description().can_read();
  155. }
  156. return blocked_description().can_read();
  157. }
  158. Thread::ConditionBlocker::ConditionBlocker(const char* state_string, Function<bool()>&& condition)
  159. : m_block_until_condition(move(condition))
  160. , m_state_string(state_string)
  161. {
  162. ASSERT(m_block_until_condition);
  163. }
  164. bool Thread::ConditionBlocker::should_unblock(Thread&, time_t, long)
  165. {
  166. return m_block_until_condition();
  167. }
  168. Thread::SleepBlocker::SleepBlocker(u64 wakeup_time)
  169. : m_wakeup_time(wakeup_time)
  170. {
  171. }
  172. bool Thread::SleepBlocker::should_unblock(Thread&, time_t, long)
  173. {
  174. return m_wakeup_time <= g_uptime;
  175. }
  176. Thread::SelectBlocker::SelectBlocker(const timespec& ts, bool select_has_timeout, const FDVector& read_fds, const FDVector& write_fds, const FDVector& except_fds)
  177. : m_select_timeout(ts)
  178. , m_select_has_timeout(select_has_timeout)
  179. , m_select_read_fds(read_fds)
  180. , m_select_write_fds(write_fds)
  181. , m_select_exceptional_fds(except_fds)
  182. {
  183. }
  184. bool Thread::SelectBlocker::should_unblock(Thread& thread, time_t now_sec, long now_usec)
  185. {
  186. if (m_select_has_timeout) {
  187. if (now_sec > m_select_timeout.tv_sec || (now_sec == m_select_timeout.tv_sec && now_usec * 1000 >= m_select_timeout.tv_nsec))
  188. return true;
  189. }
  190. auto& process = thread.process();
  191. for (int fd : m_select_read_fds) {
  192. if (!process.m_fds[fd])
  193. continue;
  194. if (process.m_fds[fd].description->can_read())
  195. return true;
  196. }
  197. for (int fd : m_select_write_fds) {
  198. if (!process.m_fds[fd])
  199. continue;
  200. if (process.m_fds[fd].description->can_write())
  201. return true;
  202. }
  203. return false;
  204. }
  205. Thread::WaitBlocker::WaitBlocker(int wait_options, pid_t& waitee_pid)
  206. : m_wait_options(wait_options)
  207. , m_waitee_pid(waitee_pid)
  208. {
  209. }
  210. bool Thread::WaitBlocker::should_unblock(Thread& thread, time_t, long)
  211. {
  212. bool should_unblock = m_wait_options & WNOHANG;
  213. if (m_waitee_pid != -1) {
  214. auto* peer = Process::from_pid(m_waitee_pid);
  215. if (!peer)
  216. return true;
  217. }
  218. thread.process().for_each_child([&](Process& child) {
  219. if (m_waitee_pid != -1 && m_waitee_pid != child.pid())
  220. return IterationDecision::Continue;
  221. bool child_exited = child.is_dead();
  222. bool child_stopped = false;
  223. if (child.thread_count()) {
  224. child.for_each_thread([&](auto& child_thread) {
  225. if (child_thread.state() == Thread::State::Stopped && !child_thread.has_pending_signal(SIGCONT)) {
  226. child_stopped = true;
  227. return IterationDecision::Break;
  228. }
  229. return IterationDecision::Continue;
  230. });
  231. }
  232. bool fits_the_spec = ((m_wait_options & WEXITED) && child_exited)
  233. || ((m_wait_options & WSTOPPED) && child_stopped);
  234. if (!fits_the_spec)
  235. return IterationDecision::Continue;
  236. m_waitee_pid = child.pid();
  237. should_unblock = true;
  238. return IterationDecision::Break;
  239. });
  240. return should_unblock;
  241. }
  242. Thread::SemiPermanentBlocker::SemiPermanentBlocker(Reason reason)
  243. : m_reason(reason)
  244. {
  245. }
  246. bool Thread::SemiPermanentBlocker::should_unblock(Thread&, time_t, long)
  247. {
  248. // someone else has to unblock us
  249. return false;
  250. }
  251. // Called by the scheduler on threads that are blocked for some reason.
  252. // Make a decision as to whether to unblock them or not.
  253. void Thread::consider_unblock(time_t now_sec, long now_usec)
  254. {
  255. switch (state()) {
  256. case Thread::Invalid:
  257. case Thread::Runnable:
  258. case Thread::Running:
  259. case Thread::Dead:
  260. case Thread::Stopped:
  261. case Thread::Queued:
  262. case Thread::Dying:
  263. /* don't know, don't care */
  264. return;
  265. case Thread::Blocked:
  266. ASSERT(m_blocker != nullptr);
  267. if (m_blocker->should_unblock(*this, now_sec, now_usec))
  268. unblock();
  269. return;
  270. case Thread::Skip1SchedulerPass:
  271. set_state(Thread::Skip0SchedulerPasses);
  272. return;
  273. case Thread::Skip0SchedulerPasses:
  274. set_state(Thread::Runnable);
  275. return;
  276. }
  277. }
  278. void Scheduler::start()
  279. {
  280. ASSERT_INTERRUPTS_DISABLED();
  281. // We need to acquire our scheduler lock, which will be released
  282. // by the idle thread once control transferred there
  283. g_scheduler_lock.lock();
  284. auto& processor = Processor::current();
  285. ASSERT(processor.is_initialized());
  286. auto& idle_thread = *processor.idle_thread();
  287. ASSERT(processor.current_thread() == &idle_thread);
  288. ASSERT(processor.idle_thread() == &idle_thread);
  289. idle_thread.set_ticks_left(time_slice_for(idle_thread));
  290. idle_thread.did_schedule();
  291. idle_thread.set_initialized(true);
  292. processor.init_context(idle_thread, false);
  293. idle_thread.set_state(Thread::Running);
  294. ASSERT(idle_thread.affinity() == (1u << processor.id()));
  295. processor.initialize_context_switching(idle_thread);
  296. ASSERT_NOT_REACHED();
  297. }
  298. bool Scheduler::pick_next()
  299. {
  300. ASSERT_INTERRUPTS_DISABLED();
  301. auto current_thread = Thread::current();
  302. auto now = time_since_boot();
  303. auto now_sec = now.tv_sec;
  304. auto now_usec = now.tv_usec;
  305. ScopedSpinLock lock(g_scheduler_lock);
  306. // Check and unblock threads whose wait conditions have been met.
  307. Scheduler::for_each_nonrunnable([&](Thread& thread) {
  308. thread.consider_unblock(now_sec, now_usec);
  309. return IterationDecision::Continue;
  310. });
  311. Process::for_each([&](Process& process) {
  312. if (process.is_dead()) {
  313. if (current_thread->process().pid() != process.pid() && (!process.ppid() || !Process::from_pid(process.ppid()))) {
  314. auto name = process.name();
  315. auto pid = process.pid();
  316. auto exit_status = Process::reap(process);
  317. dbg() << "Scheduler[" << Processor::current().id() << "]: Reaped unparented process " << name << "(" << pid << "), exit status: " << exit_status.si_status;
  318. }
  319. return IterationDecision::Continue;
  320. }
  321. if (process.m_alarm_deadline && g_uptime > process.m_alarm_deadline) {
  322. process.m_alarm_deadline = 0;
  323. process.send_signal(SIGALRM, nullptr);
  324. }
  325. return IterationDecision::Continue;
  326. });
  327. // Dispatch any pending signals.
  328. Thread::for_each_living([&](Thread& thread) -> IterationDecision {
  329. if (!thread.has_unmasked_pending_signals())
  330. return IterationDecision::Continue;
  331. // FIXME: It would be nice if the Scheduler didn't have to worry about who is "current"
  332. // For now, avoid dispatching signals to "current" and do it in a scheduling pass
  333. // while some other process is interrupted. Otherwise a mess will be made.
  334. if (&thread == current_thread)
  335. return IterationDecision::Continue;
  336. // We know how to interrupt blocked processes, but if they are just executing
  337. // at some random point in the kernel, let them continue.
  338. // Before returning to userspace from a syscall, we will block a thread if it has any
  339. // pending unmasked signals, allowing it to be dispatched then.
  340. if (thread.in_kernel() && !thread.is_blocked() && !thread.is_stopped())
  341. return IterationDecision::Continue;
  342. // NOTE: dispatch_one_pending_signal() may unblock the process.
  343. bool was_blocked = thread.is_blocked();
  344. if (thread.dispatch_one_pending_signal() == ShouldUnblockThread::No)
  345. return IterationDecision::Continue;
  346. if (was_blocked) {
  347. #ifdef SCHEDULER_DEBUG
  348. dbg() << "Scheduler[" << Processor::current().id() << "]:Unblock " << thread << " due to signal";
  349. #endif
  350. ASSERT(thread.m_blocker != nullptr);
  351. thread.m_blocker->set_interrupted_by_signal();
  352. thread.unblock();
  353. }
  354. return IterationDecision::Continue;
  355. });
  356. #ifdef SCHEDULER_RUNNABLE_DEBUG
  357. dbg() << "Non-runnables:";
  358. Scheduler::for_each_nonrunnable([](Thread& thread) -> IterationDecision {
  359. if (thread.state() == Thread::Queued)
  360. dbg() << " " << String::format("%-12s", thread.state_string()) << " " << thread << " @ " << String::format("%w", thread.tss().cs) << ":" << String::format("%x", thread.tss().eip) << " Reason: " << (thread.wait_reason() ? thread.wait_reason() : "none");
  361. else if (thread.state() == Thread::Dying)
  362. dbg() << " " << String::format("%-12s", thread.state_string()) << " " << thread << " @ " << String::format("%w", thread.tss().cs) << ":" << String::format("%x", thread.tss().eip) << " Finalizable: " << thread.is_finalizable();
  363. return IterationDecision::Continue;
  364. });
  365. dbg() << "Runnables:";
  366. Scheduler::for_each_runnable([](Thread& thread) -> IterationDecision {
  367. dbg() << " " << String::format("%3u", thread.effective_priority()) << "/" << String::format("%2u", thread.priority()) << " " << String::format("%-12s", thread.state_string()) << " " << thread << " @ " << String::format("%w", thread.tss().cs) << ":" << String::format("%x", thread.tss().eip);
  368. return IterationDecision::Continue;
  369. });
  370. #endif
  371. Vector<Thread*, 128> sorted_runnables;
  372. for_each_runnable([&sorted_runnables](auto& thread) {
  373. if ((thread.affinity() & (1u << Processor::current().id())) != 0)
  374. sorted_runnables.append(&thread);
  375. return IterationDecision::Continue;
  376. });
  377. quick_sort(sorted_runnables, [](auto& a, auto& b) { return a->effective_priority() >= b->effective_priority(); });
  378. Thread* thread_to_schedule = nullptr;
  379. for (auto* thread : sorted_runnables) {
  380. if (thread->process().is_being_inspected())
  381. continue;
  382. if (thread->process().exec_tid() && thread->process().exec_tid() != thread->tid())
  383. continue;
  384. ASSERT(thread->state() == Thread::Runnable || thread->state() == Thread::Running);
  385. if (!thread_to_schedule) {
  386. thread->m_extra_priority = 0;
  387. thread_to_schedule = thread;
  388. } else {
  389. thread->m_extra_priority++;
  390. }
  391. }
  392. if (!thread_to_schedule)
  393. thread_to_schedule = Processor::current().idle_thread();
  394. #ifdef SCHEDULER_DEBUG
  395. dbg() << "Scheduler[" << Processor::current().id() << "]: Switch to " << *thread_to_schedule << " @ " << String::format("%04x:%08x", thread_to_schedule->tss().cs, thread_to_schedule->tss().eip);
  396. #endif
  397. return context_switch(thread_to_schedule);
  398. }
  399. bool Scheduler::yield()
  400. {
  401. InterruptDisabler disabler;
  402. auto& proc = Processor::current();
  403. auto current_thread = Thread::current();
  404. #ifdef SCHEDULER_DEBUG
  405. dbg() << "Scheduler[" << proc.id() << "]: yielding thread " << *current_thread << " in_irq: " << proc.in_irq();
  406. #endif
  407. ASSERT(current_thread != nullptr);
  408. if (proc.in_irq() || proc.in_critical()) {
  409. // If we're handling an IRQ we can't switch context, or we're in
  410. // a critical section where we don't want to switch contexts, then
  411. // delay until exiting the trap or critical section
  412. proc.invoke_scheduler_async();
  413. return false;
  414. } else if (!Scheduler::pick_next())
  415. return false;
  416. #ifdef SCHEDULER_DEBUG
  417. dbg() << "Scheduler[" << proc.id() << "]: yield returns to thread " << *current_thread << " in_irq: " << proc.in_irq();
  418. #endif
  419. return true;
  420. }
  421. bool Scheduler::donate_to(Thread* beneficiary, const char* reason)
  422. {
  423. ScopedSpinLock lock(g_scheduler_lock);
  424. auto& proc = Processor::current();
  425. ASSERT(!proc.in_irq());
  426. if (!Thread::is_thread(beneficiary))
  427. return false;
  428. if (proc.in_critical()) {
  429. proc.invoke_scheduler_async();
  430. return false;
  431. }
  432. (void)reason;
  433. unsigned ticks_left = Thread::current()->ticks_left();
  434. if (!beneficiary || beneficiary->state() != Thread::Runnable || ticks_left <= 1)
  435. return Scheduler::yield();
  436. unsigned ticks_to_donate = min(ticks_left - 1, time_slice_for(*beneficiary));
  437. #ifdef SCHEDULER_DEBUG
  438. dbg() << "Scheduler[" << proc.id() << "]: Donating " << ticks_to_donate << " ticks to " << *beneficiary << ", reason=" << reason;
  439. #endif
  440. beneficiary->set_ticks_left(ticks_to_donate);
  441. Scheduler::context_switch(beneficiary);
  442. return false;
  443. }
  444. bool Scheduler::context_switch(Thread* thread)
  445. {
  446. thread->set_ticks_left(time_slice_for(*thread));
  447. thread->did_schedule();
  448. auto from_thread = Thread::current();
  449. if (from_thread == thread)
  450. return false;
  451. if (from_thread) {
  452. // If the last process hasn't blocked (still marked as running),
  453. // mark it as runnable for the next round.
  454. if (from_thread->state() == Thread::Running)
  455. from_thread->set_state(Thread::Runnable);
  456. #ifdef LOG_EVERY_CONTEXT_SWITCH
  457. dbg() << "Scheduler[" << Processor::current().id() << "]: " << *from_thread << " -> " << *thread << " [" << thread->priority() << "] " << String::format("%w", thread->tss().cs) << ":" << String::format("%x", thread->tss().eip);
  458. #endif
  459. }
  460. auto& proc = Processor::current();
  461. if (!thread->is_initialized()) {
  462. proc.init_context(*thread, false);
  463. thread->set_initialized(true);
  464. }
  465. thread->set_state(Thread::Running);
  466. // Mark it as active because we are using this thread. This is similar
  467. // to comparing it with Processor::current_thread, but when there are
  468. // multiple processors there's no easy way to check whether the thread
  469. // is actually still needed. This prevents accidental finalization when
  470. // a thread is no longer in Running state, but running on another core.
  471. thread->set_active(true);
  472. proc.switch_context(from_thread, thread);
  473. // NOTE: from_thread at this point reflects the thread we were
  474. // switched from, and thread reflects Thread::current()
  475. enter_current(*from_thread);
  476. ASSERT(thread == Thread::current());
  477. return true;
  478. }
  479. void Scheduler::enter_current(Thread& prev_thread)
  480. {
  481. ASSERT(g_scheduler_lock.is_locked());
  482. prev_thread.set_active(false);
  483. if (prev_thread.state() == Thread::Dying) {
  484. // If the thread we switched from is marked as dying, then notify
  485. // the finalizer. Note that as soon as we leave the scheduler lock
  486. // the finalizer may free from_thread!
  487. notify_finalizer();
  488. }
  489. }
  490. Process* Scheduler::colonel()
  491. {
  492. return s_colonel_process;
  493. }
  494. void Scheduler::initialize(u32 cpu)
  495. {
  496. static Atomic<u32> s_bsp_is_initialized;
  497. ASSERT(&Processor::current() != nullptr); // sanity check
  498. Thread* idle_thread = nullptr;
  499. if (cpu == 0) {
  500. ASSERT(s_bsp_is_initialized.load(AK::MemoryOrder::memory_order_consume) == 0);
  501. g_scheduler_data = new SchedulerData;
  502. g_finalizer_wait_queue = new WaitQueue;
  503. g_finalizer_has_work.store(false, AK::MemoryOrder::memory_order_release);
  504. s_colonel_process = Process::create_kernel_process(idle_thread, "colonel", idle_loop, 1 << cpu);
  505. ASSERT(s_colonel_process);
  506. ASSERT(idle_thread);
  507. idle_thread->set_priority(THREAD_PRIORITY_MIN);
  508. idle_thread->set_name(String::format("idle thread #%u", cpu));
  509. } else {
  510. // We need to make sure the BSP initialized the global data first
  511. if (s_bsp_is_initialized.load(AK::MemoryOrder::memory_order_consume) == 0) {
  512. #ifdef SCHEDULER_DEBUG
  513. dbg() << "Scheduler[" << cpu << "]: waiting for BSP to initialize...";
  514. #endif
  515. while (s_bsp_is_initialized.load(AK::MemoryOrder::memory_order_consume) == 0) {
  516. }
  517. #ifdef SCHEDULER_DEBUG
  518. dbg() << "Scheduler[" << cpu << "]: initializing now";
  519. #endif
  520. }
  521. ASSERT(s_colonel_process);
  522. idle_thread = s_colonel_process->create_kernel_thread(idle_loop, THREAD_PRIORITY_MIN, String::format("idle thread #%u", cpu), 1 << cpu, false);
  523. ASSERT(idle_thread);
  524. }
  525. Processor::current().set_idle_thread(*idle_thread);
  526. Processor::current().set_current_thread(*idle_thread);
  527. if (cpu == 0)
  528. s_bsp_is_initialized.store(1, AK::MemoryOrder::memory_order_release);
  529. }
  530. void Scheduler::timer_tick(const RegisterState& regs)
  531. {
  532. ASSERT_INTERRUPTS_DISABLED();
  533. ASSERT(Processor::current().in_irq());
  534. auto current_thread = Processor::current().current_thread();
  535. if (!current_thread)
  536. return;
  537. ++g_uptime;
  538. g_timeofday = TimeManagement::now_as_timeval();
  539. if (current_thread->process().is_profiling()) {
  540. SmapDisabler disabler;
  541. auto backtrace = current_thread->raw_backtrace(regs.ebp, regs.eip);
  542. auto& sample = Profiling::next_sample_slot();
  543. sample.pid = current_thread->process().pid();
  544. sample.tid = current_thread->tid();
  545. sample.timestamp = g_uptime;
  546. for (size_t i = 0; i < min(backtrace.size(), Profiling::max_stack_frame_count); ++i) {
  547. sample.frames[i] = backtrace[i];
  548. }
  549. }
  550. TimerQueue::the().fire();
  551. if (current_thread->tick())
  552. return;
  553. ASSERT_INTERRUPTS_DISABLED();
  554. ASSERT(Processor::current().in_irq());
  555. Processor::current().invoke_scheduler_async();
  556. }
  557. void Scheduler::invoke_async()
  558. {
  559. ASSERT_INTERRUPTS_DISABLED();
  560. ASSERT(!Processor::current().in_irq());
  561. pick_next();
  562. }
  563. void Scheduler::notify_finalizer()
  564. {
  565. if (g_finalizer_has_work.exchange(true, AK::MemoryOrder::memory_order_acq_rel) == false)
  566. g_finalizer_wait_queue->wake_all();
  567. }
  568. void Scheduler::idle_loop()
  569. {
  570. dbg() << "Scheduler[" << Processor::current().id() << "]: idle loop running";
  571. ASSERT(are_interrupts_enabled());
  572. for (;;) {
  573. asm("hlt");
  574. yield();
  575. }
  576. }
  577. }