From b88c1d90e1d65d62f5438686bdb386652c3d7d40 Mon Sep 17 00:00:00 2001 From: Liav A Date: Fri, 24 Feb 2023 20:23:38 +0200 Subject: Kernel: Move TimerQueue code to the Time subdirectory --- Kernel/CMakeLists.txt | 2 +- Kernel/Graphics/VMWare/Console.h | 2 +- Kernel/Graphics/VirtIOGPU/Console.h | 2 +- Kernel/Syscalls/alarm.cpp | 2 +- Kernel/Tasks/Process.cpp | 2 +- Kernel/Tasks/Thread.cpp | 2 +- Kernel/Time/TimeManagement.cpp | 2 +- Kernel/Time/TimerQueue.cpp | 232 ++++++++++++++++++++++++++++++++++++ Kernel/Time/TimerQueue.h | 126 ++++++++++++++++++++ Kernel/TimerQueue.cpp | 232 ------------------------------------ Kernel/TimerQueue.h | 126 -------------------- 11 files changed, 365 insertions(+), 365 deletions(-) create mode 100644 Kernel/Time/TimerQueue.cpp create mode 100644 Kernel/Time/TimerQueue.h delete mode 100644 Kernel/TimerQueue.cpp delete mode 100644 Kernel/TimerQueue.h diff --git a/Kernel/CMakeLists.txt b/Kernel/CMakeLists.txt index a8c6c691bd..405a0d863a 100644 --- a/Kernel/CMakeLists.txt +++ b/Kernel/CMakeLists.txt @@ -358,7 +358,7 @@ set(KERNEL_SOURCES Tasks/WaitQueue.cpp Tasks/WorkQueue.cpp Time/TimeManagement.cpp - TimerQueue.cpp + Time/TimerQueue.cpp ) if ("${SERENITY_ARCH}" STREQUAL "x86_64") diff --git a/Kernel/Graphics/VMWare/Console.h b/Kernel/Graphics/VMWare/Console.h index 0624e427bb..cb4e3d44df 100644 --- a/Kernel/Graphics/VMWare/Console.h +++ b/Kernel/Graphics/VMWare/Console.h @@ -8,7 +8,7 @@ #include #include -#include +#include namespace Kernel { diff --git a/Kernel/Graphics/VirtIOGPU/Console.h b/Kernel/Graphics/VirtIOGPU/Console.h index 744a640d89..d1a994aaef 100644 --- a/Kernel/Graphics/VirtIOGPU/Console.h +++ b/Kernel/Graphics/VirtIOGPU/Console.h @@ -8,7 +8,7 @@ #include #include -#include +#include namespace Kernel::Graphics::VirtIOGPU { diff --git a/Kernel/Syscalls/alarm.cpp b/Kernel/Syscalls/alarm.cpp index fdd77f2d53..db0b1e6192 100644 --- a/Kernel/Syscalls/alarm.cpp +++ b/Kernel/Syscalls/alarm.cpp @@ -6,7 +6,7 @@ #include #include -#include +#include namespace Kernel { diff --git a/Kernel/Tasks/Process.cpp b/Kernel/Tasks/Process.cpp index bcfef1d571..7b8f348221 100644 --- a/Kernel/Tasks/Process.cpp +++ b/Kernel/Tasks/Process.cpp @@ -39,7 +39,7 @@ #include #include #include -#include +#include namespace Kernel { diff --git a/Kernel/Tasks/Thread.cpp b/Kernel/Tasks/Thread.cpp index d42a4df45c..d0cbc22e3c 100644 --- a/Kernel/Tasks/Thread.cpp +++ b/Kernel/Tasks/Thread.cpp @@ -27,7 +27,7 @@ #include #include #include -#include +#include #include namespace Kernel { diff --git a/Kernel/Time/TimeManagement.cpp b/Kernel/Time/TimeManagement.cpp index 5d672af49f..23d66b971c 100644 --- a/Kernel/Time/TimeManagement.cpp +++ b/Kernel/Time/TimeManagement.cpp @@ -31,7 +31,7 @@ #include #include #include -#include +#include namespace Kernel { diff --git a/Kernel/Time/TimerQueue.cpp b/Kernel/Time/TimerQueue.cpp new file mode 100644 index 0000000000..89546b0c07 --- /dev/null +++ b/Kernel/Time/TimerQueue.cpp @@ -0,0 +1,232 @@ +/* + * Copyright (c) 2018-2020, Andreas Kling + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#include +#include +#include +#include +#include +#include + +namespace Kernel { + +static Singleton s_the; +static Spinlock g_timerqueue_lock {}; + +Duration Timer::remaining() const +{ + return m_remaining; +} + +Duration Timer::now(bool is_firing) const +{ + // NOTE: If is_firing is true then TimePrecision::Precise isn't really useful here. + // We already have a quite precise time stamp because we just updated the time in the + // interrupt handler. In those cases, just use coarse timestamps. + auto clock_id = m_clock_id; + if (is_firing) { + switch (clock_id) { + case CLOCK_MONOTONIC: + clock_id = CLOCK_MONOTONIC_COARSE; + break; + case CLOCK_MONOTONIC_RAW: + // TODO: use a special CLOCK_MONOTONIC_RAW_COARSE like mechanism here + break; + case CLOCK_REALTIME: + clock_id = CLOCK_REALTIME_COARSE; + break; + default: + break; + } + } + return TimeManagement::the().current_time(clock_id); +} + +TimerQueue& TimerQueue::the() +{ + return *s_the; +} + +UNMAP_AFTER_INIT TimerQueue::TimerQueue() +{ + m_ticks_per_second = TimeManagement::the().ticks_per_second(); +} + +bool TimerQueue::add_timer_without_id(NonnullRefPtr timer, clockid_t clock_id, Duration const& deadline, Function&& callback) +{ + if (deadline <= TimeManagement::the().current_time(clock_id)) + return false; + + // Because timer handlers can execute on any processor and there is + // a race between executing a timer handler and cancel_timer() this + // *must* be a RefPtr. Otherwise, calling cancel_timer() could + // inadvertently cancel another timer that has been created between + // returning from the timer handler and a call to cancel_timer(). + timer->setup(clock_id, deadline, move(callback)); + + SpinlockLocker lock(g_timerqueue_lock); + timer->m_id = 0; // Don't generate a timer id + add_timer_locked(move(timer)); + return true; +} + +TimerId TimerQueue::add_timer(NonnullRefPtr&& timer) +{ + SpinlockLocker lock(g_timerqueue_lock); + + timer->m_id = ++m_timer_id_count; + VERIFY(timer->m_id != 0); // wrapped + auto id = timer->m_id; + add_timer_locked(move(timer)); + return id; +} + +void TimerQueue::add_timer_locked(NonnullRefPtr timer) +{ + Duration timer_expiration = timer->m_expires; + + timer->clear_cancelled(); + timer->clear_callback_finished(); + timer->set_in_use(); + + auto& queue = queue_for_timer(*timer); + if (queue.list.is_empty()) { + queue.list.append(timer.leak_ref()); + queue.next_timer_due = timer_expiration; + } else { + Timer* following_timer = nullptr; + for (auto& t : queue.list) { + if (t.m_expires > timer_expiration) { + following_timer = &t; + break; + } + } + if (following_timer) { + bool next_timer_needs_update = queue.list.first() == following_timer; + queue.list.insert_before(*following_timer, timer.leak_ref()); + if (next_timer_needs_update) + queue.next_timer_due = timer_expiration; + } else { + queue.list.append(timer.leak_ref()); + } + } +} + +bool TimerQueue::cancel_timer(Timer& timer, bool* was_in_use) +{ + bool in_use = timer.is_in_use(); + if (was_in_use) + *was_in_use = in_use; + + // If the timer isn't in use, the cancellation is a no-op. + if (!in_use) { + VERIFY(!timer.m_list_node.is_in_list()); + return false; + } + + bool did_already_run = timer.set_cancelled(); + auto& timer_queue = queue_for_timer(timer); + if (!did_already_run) { + timer.clear_in_use(); + + SpinlockLocker lock(g_timerqueue_lock); + if (timer_queue.list.contains(timer)) { + // The timer has not fired, remove it + VERIFY(timer.ref_count() > 1); + remove_timer_locked(timer_queue, timer); + return true; + } + + // The timer was queued to execute but hasn't had a chance + // to run. In this case, it should still be in m_timers_executing + // and we don't need to spin. It still holds a reference + // that will be dropped when it does get a chance to run, + // but since we called set_cancelled it will only drop its reference + VERIFY(m_timers_executing.contains(timer)); + m_timers_executing.remove(timer); + return true; + } + + // At this point the deferred call is queued and is being executed + // on another processor. We need to wait until it's complete! + while (!timer.is_callback_finished()) + Processor::wait_check(); + + return false; +} + +void TimerQueue::remove_timer_locked(Queue& queue, Timer& timer) +{ + bool was_next_timer = (queue.list.first() == &timer); + queue.list.remove(timer); + auto now = timer.now(false); + if (timer.m_expires > now) + timer.m_remaining = timer.m_expires - now; + + if (was_next_timer) + update_next_timer_due(queue); + // Whenever we remove a timer that was still queued (but hasn't been + // fired) we added a reference to it. So, when removing it from the + // queue we need to drop that reference. + timer.unref(); +} + +void TimerQueue::fire() +{ + SpinlockLocker lock(g_timerqueue_lock); + + auto fire_timers = [&](Queue& queue) { + auto* timer = queue.list.first(); + VERIFY(timer); + VERIFY(queue.next_timer_due == timer->m_expires); + + while (timer && timer->now(true) > timer->m_expires) { + queue.list.remove(*timer); + + m_timers_executing.append(*timer); + + update_next_timer_due(queue); + + lock.unlock(); + + // Defer executing the timer outside of the irq handler + Processor::deferred_call_queue([this, timer]() { + // Check if we were cancelled in between being triggered + // by the timer irq handler and now. If so, just drop + // our reference and don't execute the callback. + if (!timer->set_cancelled()) { + timer->m_callback(); + SpinlockLocker lock(g_timerqueue_lock); + m_timers_executing.remove(*timer); + } + timer->clear_in_use(); + timer->set_callback_finished(); + // Drop the reference we added when queueing the timer + timer->unref(); + }); + + lock.lock(); + timer = queue.list.first(); + } + }; + + if (!m_timer_queue_monotonic.list.is_empty()) + fire_timers(m_timer_queue_monotonic); + if (!m_timer_queue_realtime.list.is_empty()) + fire_timers(m_timer_queue_realtime); +} + +void TimerQueue::update_next_timer_due(Queue& queue) +{ + VERIFY(g_timerqueue_lock.is_locked()); + + if (auto* next_timer = queue.list.first()) + queue.next_timer_due = next_timer->m_expires; + else + queue.next_timer_due = {}; +} + +} diff --git a/Kernel/Time/TimerQueue.h b/Kernel/Time/TimerQueue.h new file mode 100644 index 0000000000..7258c33eca --- /dev/null +++ b/Kernel/Time/TimerQueue.h @@ -0,0 +1,126 @@ +/* + * Copyright (c) 2018-2020, Andreas Kling + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#pragma once + +#include +#include +#include +#include +#include +#include +#include + +namespace Kernel { + +AK_TYPEDEF_DISTINCT_ORDERED_ID(u64, TimerId); + +class Timer final : public AtomicRefCounted { + friend class TimerQueue; + +public: + void setup(clockid_t clock_id, Duration expires, Function&& callback) + { + VERIFY(!is_queued()); + m_clock_id = clock_id; + m_expires = expires; + m_callback = move(callback); + } + + ~Timer() + { + VERIFY(!is_queued()); + } + + Duration remaining() const; + +private: + TimerId m_id; + clockid_t m_clock_id; + Duration m_expires; + Duration m_remaining {}; + Function m_callback; + Atomic m_cancelled { false }; + Atomic m_callback_finished { false }; + Atomic m_in_use { false }; + + bool operator<(Timer const& rhs) const + { + return m_expires < rhs.m_expires; + } + bool operator>(Timer const& rhs) const + { + return m_expires > rhs.m_expires; + } + bool operator==(Timer const& rhs) const + { + return m_id == rhs.m_id; + } + + void clear_cancelled() { return m_cancelled.store(false, AK::memory_order_release); } + bool set_cancelled() { return m_cancelled.exchange(true, AK::memory_order_acq_rel); } + + bool is_in_use() { return m_in_use.load(AK::memory_order_acquire); }; + void set_in_use() { m_in_use.store(true, AK::memory_order_release); } + void clear_in_use() { return m_in_use.store(false, AK::memory_order_release); } + + bool is_callback_finished() const { return m_callback_finished.load(AK::memory_order_acquire); } + void clear_callback_finished() { m_callback_finished.store(false, AK::memory_order_release); } + void set_callback_finished() { m_callback_finished.store(true, AK::memory_order_release); } + + Duration now(bool) const; + + bool is_queued() const { return m_list_node.is_in_list(); } + +public: + IntrusiveListNode m_list_node; + using List = IntrusiveList<&Timer::m_list_node>; +}; + +class TimerQueue { + friend class Timer; + +public: + TimerQueue(); + static TimerQueue& the(); + + TimerId add_timer(NonnullRefPtr&&); + bool add_timer_without_id(NonnullRefPtr, clockid_t, Duration const&, Function&&); + bool cancel_timer(Timer& timer, bool* was_in_use = nullptr); + void fire(); + +private: + struct Queue { + Timer::List list; + Duration next_timer_due {}; + }; + void remove_timer_locked(Queue&, Timer&); + void update_next_timer_due(Queue&); + void add_timer_locked(NonnullRefPtr); + + Queue& queue_for_timer(Timer& timer) + { + switch (timer.m_clock_id) { + case CLOCK_MONOTONIC: + case CLOCK_MONOTONIC_COARSE: + case CLOCK_MONOTONIC_RAW: + return m_timer_queue_monotonic; + case CLOCK_REALTIME: + case CLOCK_REALTIME_COARSE: + return m_timer_queue_realtime; + default: + VERIFY_NOT_REACHED(); + } + } + + u64 m_timer_id_count { 0 }; + u64 m_ticks_per_second { 0 }; + Queue m_timer_queue_monotonic; + Queue m_timer_queue_realtime; + Timer::List m_timers_executing; +}; + +} diff --git a/Kernel/TimerQueue.cpp b/Kernel/TimerQueue.cpp deleted file mode 100644 index 7e4f8cbe41..0000000000 --- a/Kernel/TimerQueue.cpp +++ /dev/null @@ -1,232 +0,0 @@ -/* - * Copyright (c) 2018-2020, Andreas Kling - * - * SPDX-License-Identifier: BSD-2-Clause - */ - -#include -#include -#include -#include -#include -#include - -namespace Kernel { - -static Singleton s_the; -static Spinlock g_timerqueue_lock {}; - -Duration Timer::remaining() const -{ - return m_remaining; -} - -Duration Timer::now(bool is_firing) const -{ - // NOTE: If is_firing is true then TimePrecision::Precise isn't really useful here. - // We already have a quite precise time stamp because we just updated the time in the - // interrupt handler. In those cases, just use coarse timestamps. - auto clock_id = m_clock_id; - if (is_firing) { - switch (clock_id) { - case CLOCK_MONOTONIC: - clock_id = CLOCK_MONOTONIC_COARSE; - break; - case CLOCK_MONOTONIC_RAW: - // TODO: use a special CLOCK_MONOTONIC_RAW_COARSE like mechanism here - break; - case CLOCK_REALTIME: - clock_id = CLOCK_REALTIME_COARSE; - break; - default: - break; - } - } - return TimeManagement::the().current_time(clock_id); -} - -TimerQueue& TimerQueue::the() -{ - return *s_the; -} - -UNMAP_AFTER_INIT TimerQueue::TimerQueue() -{ - m_ticks_per_second = TimeManagement::the().ticks_per_second(); -} - -bool TimerQueue::add_timer_without_id(NonnullRefPtr timer, clockid_t clock_id, Duration const& deadline, Function&& callback) -{ - if (deadline <= TimeManagement::the().current_time(clock_id)) - return false; - - // Because timer handlers can execute on any processor and there is - // a race between executing a timer handler and cancel_timer() this - // *must* be a RefPtr. Otherwise, calling cancel_timer() could - // inadvertently cancel another timer that has been created between - // returning from the timer handler and a call to cancel_timer(). - timer->setup(clock_id, deadline, move(callback)); - - SpinlockLocker lock(g_timerqueue_lock); - timer->m_id = 0; // Don't generate a timer id - add_timer_locked(move(timer)); - return true; -} - -TimerId TimerQueue::add_timer(NonnullRefPtr&& timer) -{ - SpinlockLocker lock(g_timerqueue_lock); - - timer->m_id = ++m_timer_id_count; - VERIFY(timer->m_id != 0); // wrapped - auto id = timer->m_id; - add_timer_locked(move(timer)); - return id; -} - -void TimerQueue::add_timer_locked(NonnullRefPtr timer) -{ - Duration timer_expiration = timer->m_expires; - - timer->clear_cancelled(); - timer->clear_callback_finished(); - timer->set_in_use(); - - auto& queue = queue_for_timer(*timer); - if (queue.list.is_empty()) { - queue.list.append(timer.leak_ref()); - queue.next_timer_due = timer_expiration; - } else { - Timer* following_timer = nullptr; - for (auto& t : queue.list) { - if (t.m_expires > timer_expiration) { - following_timer = &t; - break; - } - } - if (following_timer) { - bool next_timer_needs_update = queue.list.first() == following_timer; - queue.list.insert_before(*following_timer, timer.leak_ref()); - if (next_timer_needs_update) - queue.next_timer_due = timer_expiration; - } else { - queue.list.append(timer.leak_ref()); - } - } -} - -bool TimerQueue::cancel_timer(Timer& timer, bool* was_in_use) -{ - bool in_use = timer.is_in_use(); - if (was_in_use) - *was_in_use = in_use; - - // If the timer isn't in use, the cancellation is a no-op. - if (!in_use) { - VERIFY(!timer.m_list_node.is_in_list()); - return false; - } - - bool did_already_run = timer.set_cancelled(); - auto& timer_queue = queue_for_timer(timer); - if (!did_already_run) { - timer.clear_in_use(); - - SpinlockLocker lock(g_timerqueue_lock); - if (timer_queue.list.contains(timer)) { - // The timer has not fired, remove it - VERIFY(timer.ref_count() > 1); - remove_timer_locked(timer_queue, timer); - return true; - } - - // The timer was queued to execute but hasn't had a chance - // to run. In this case, it should still be in m_timers_executing - // and we don't need to spin. It still holds a reference - // that will be dropped when it does get a chance to run, - // but since we called set_cancelled it will only drop its reference - VERIFY(m_timers_executing.contains(timer)); - m_timers_executing.remove(timer); - return true; - } - - // At this point the deferred call is queued and is being executed - // on another processor. We need to wait until it's complete! - while (!timer.is_callback_finished()) - Processor::wait_check(); - - return false; -} - -void TimerQueue::remove_timer_locked(Queue& queue, Timer& timer) -{ - bool was_next_timer = (queue.list.first() == &timer); - queue.list.remove(timer); - auto now = timer.now(false); - if (timer.m_expires > now) - timer.m_remaining = timer.m_expires - now; - - if (was_next_timer) - update_next_timer_due(queue); - // Whenever we remove a timer that was still queued (but hasn't been - // fired) we added a reference to it. So, when removing it from the - // queue we need to drop that reference. - timer.unref(); -} - -void TimerQueue::fire() -{ - SpinlockLocker lock(g_timerqueue_lock); - - auto fire_timers = [&](Queue& queue) { - auto* timer = queue.list.first(); - VERIFY(timer); - VERIFY(queue.next_timer_due == timer->m_expires); - - while (timer && timer->now(true) > timer->m_expires) { - queue.list.remove(*timer); - - m_timers_executing.append(*timer); - - update_next_timer_due(queue); - - lock.unlock(); - - // Defer executing the timer outside of the irq handler - Processor::deferred_call_queue([this, timer]() { - // Check if we were cancelled in between being triggered - // by the timer irq handler and now. If so, just drop - // our reference and don't execute the callback. - if (!timer->set_cancelled()) { - timer->m_callback(); - SpinlockLocker lock(g_timerqueue_lock); - m_timers_executing.remove(*timer); - } - timer->clear_in_use(); - timer->set_callback_finished(); - // Drop the reference we added when queueing the timer - timer->unref(); - }); - - lock.lock(); - timer = queue.list.first(); - } - }; - - if (!m_timer_queue_monotonic.list.is_empty()) - fire_timers(m_timer_queue_monotonic); - if (!m_timer_queue_realtime.list.is_empty()) - fire_timers(m_timer_queue_realtime); -} - -void TimerQueue::update_next_timer_due(Queue& queue) -{ - VERIFY(g_timerqueue_lock.is_locked()); - - if (auto* next_timer = queue.list.first()) - queue.next_timer_due = next_timer->m_expires; - else - queue.next_timer_due = {}; -} - -} diff --git a/Kernel/TimerQueue.h b/Kernel/TimerQueue.h deleted file mode 100644 index 7258c33eca..0000000000 --- a/Kernel/TimerQueue.h +++ /dev/null @@ -1,126 +0,0 @@ -/* - * Copyright (c) 2018-2020, Andreas Kling - * - * SPDX-License-Identifier: BSD-2-Clause - */ - -#pragma once - -#include -#include -#include -#include -#include -#include -#include - -namespace Kernel { - -AK_TYPEDEF_DISTINCT_ORDERED_ID(u64, TimerId); - -class Timer final : public AtomicRefCounted { - friend class TimerQueue; - -public: - void setup(clockid_t clock_id, Duration expires, Function&& callback) - { - VERIFY(!is_queued()); - m_clock_id = clock_id; - m_expires = expires; - m_callback = move(callback); - } - - ~Timer() - { - VERIFY(!is_queued()); - } - - Duration remaining() const; - -private: - TimerId m_id; - clockid_t m_clock_id; - Duration m_expires; - Duration m_remaining {}; - Function m_callback; - Atomic m_cancelled { false }; - Atomic m_callback_finished { false }; - Atomic m_in_use { false }; - - bool operator<(Timer const& rhs) const - { - return m_expires < rhs.m_expires; - } - bool operator>(Timer const& rhs) const - { - return m_expires > rhs.m_expires; - } - bool operator==(Timer const& rhs) const - { - return m_id == rhs.m_id; - } - - void clear_cancelled() { return m_cancelled.store(false, AK::memory_order_release); } - bool set_cancelled() { return m_cancelled.exchange(true, AK::memory_order_acq_rel); } - - bool is_in_use() { return m_in_use.load(AK::memory_order_acquire); }; - void set_in_use() { m_in_use.store(true, AK::memory_order_release); } - void clear_in_use() { return m_in_use.store(false, AK::memory_order_release); } - - bool is_callback_finished() const { return m_callback_finished.load(AK::memory_order_acquire); } - void clear_callback_finished() { m_callback_finished.store(false, AK::memory_order_release); } - void set_callback_finished() { m_callback_finished.store(true, AK::memory_order_release); } - - Duration now(bool) const; - - bool is_queued() const { return m_list_node.is_in_list(); } - -public: - IntrusiveListNode m_list_node; - using List = IntrusiveList<&Timer::m_list_node>; -}; - -class TimerQueue { - friend class Timer; - -public: - TimerQueue(); - static TimerQueue& the(); - - TimerId add_timer(NonnullRefPtr&&); - bool add_timer_without_id(NonnullRefPtr, clockid_t, Duration const&, Function&&); - bool cancel_timer(Timer& timer, bool* was_in_use = nullptr); - void fire(); - -private: - struct Queue { - Timer::List list; - Duration next_timer_due {}; - }; - void remove_timer_locked(Queue&, Timer&); - void update_next_timer_due(Queue&); - void add_timer_locked(NonnullRefPtr); - - Queue& queue_for_timer(Timer& timer) - { - switch (timer.m_clock_id) { - case CLOCK_MONOTONIC: - case CLOCK_MONOTONIC_COARSE: - case CLOCK_MONOTONIC_RAW: - return m_timer_queue_monotonic; - case CLOCK_REALTIME: - case CLOCK_REALTIME_COARSE: - return m_timer_queue_realtime; - default: - VERIFY_NOT_REACHED(); - } - } - - u64 m_timer_id_count { 0 }; - u64 m_ticks_per_second { 0 }; - Queue m_timer_queue_monotonic; - Queue m_timer_queue_realtime; - Timer::List m_timers_executing; -}; - -} -- cgit v1.2.3