stk_strategy_pthreshold.h

Go to the documentation of this file.

/*
 * SuperTinyKernel(TM) RTOS: Lightweight High-Performance Deterministic C++ RTOS for Embedded Systems.
 *
 * Source: https://github.com/SuperTinyKernel-RTOS
 *
 * Copyright (c) 2022-2026 Neutron Code Limited <stk@neutroncode.com>. All Rights Reserved.
 * License: MIT License, see LICENSE for a full text.
 */
 
#ifndef STK_STRATEGY_PTHRESHOLD_H_
#define STK_STRATEGY_PTHRESHOLD_H_

 
#include "stk_common.h"
 
namespace stk {

template <uint8_t MAX_PRIORITIES, bool TIMESLICE = false>
class SwitchStrategyPreemptionThreshold final : public ITaskSwitchStrategy
{
public:
    enum EConfig
    {
        WEIGHT_API               = 1, 
        SLEEP_EVENT_API          = 1, 
        DEADLINE_MISSED_API      = 0, 
        PRIORITY_INHERITANCE_API = 1, 
        NOSLEEP_YIELD_API        = 1, 
        TIMESLICE_API            = (TIMESLICE ? 1 : 0) 
    };

    static constexpr Weight MakeWeight(uint8_t priority, uint8_t threshold)
    {
        return static_cast<Weight>((static_cast<Weight>(priority) << 8) | static_cast<Weight>(threshold));
    }

    static constexpr Weight FromThreadX(uint8_t tx_priority, uint8_t tx_threshold)
    {
        return MakeWeight(static_cast<uint8_t>((MAX_PRIORITIES - 1U) - tx_priority),
                          static_cast<uint8_t>((MAX_PRIORITIES - 1U) - tx_threshold));
    }

    explicit SwitchStrategyPreemptionThreshold() : m_tasks(), m_sleep(), m_ready_bitmap(0U), m_held_bitmap(0U), m_advance_bitmap(0U), m_running(nullptr), m_prev(), m_held()
    {
        STK_STATIC_ASSERT_DESC(MAX_PRIORITIES <= 32U, "MAX_PRIORITIES exceeds 32-bit bitmap width");
    }

    STK_VIRT_DTOR ~SwitchStrategyPreemptionThreshold() = default;

    void AddTask(IKernelTask *task) override
    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(task->GetHead() == nullptr);
        STK_ASSERT(GetTaskPriority(task) < MAX_PRIORITIES);
        STK_ASSERT(GetRawThreshold(task) < MAX_PRIORITIES);
        STK_ASSERT(GetRawThreshold(task) >= GetTaskPriority(task));
 
        const Priority prio = GetTaskPriority(task);
        const bool is_tail = (m_prev[prio] == m_tasks[prio].GetLast());
 
        AddActive(task);
 
        // non-sticky mode: if the cursor is on the tail, move it to the new task so that the next
        // GetNext() returns the head instead of the new task (the new task waits for its turn),
        // sticky mode (TIMESLICE): the cursor stays on the running task and the new task is
        // appended behind it, the CPU is not taken over until the rotation is requested
        if (is_tail && !TIMESLICE)
        {
            m_prev[prio] = task;
        }
    }

    void RemoveTask(IKernelTask *task) override
    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(GetSize() != 0U);
        STK_ASSERT((task->GetHead() == &m_tasks[GetTaskPriority(task)]) || (task->GetHead() == &m_sleep));
 
        if (task->GetHead() == &m_sleep)
        {
            m_sleep.Unlink(task);
        }
        else
        {
            RemoveActive(task, GetTaskPriority(task));
        }
    }

    IKernelTask *GetNext() override
    {
        IKernelTask *next = nullptr;
 
        if (m_ready_bitmap != 0U)
        {
            const Priority hi = GetHighestReadyPriority(m_ready_bitmap);
 
            if (m_held_bitmap != 0U)
            {
                IKernelTask *const holder = m_held[GetHighestReadyPriority(m_held_bitmap)];
                STK_ASSERT(holder != nullptr);
 
                if (hi <= GetTaskThreshold(holder))
                {
                    next = holder;
                }
            }
 
            if (next == nullptr)
            {
                bool advance = true;
 
                if __stk_constexpr_cpp17 (TIMESLICE)
                {
                    // sticky: the cursor moves only when a rotation was requested for this level
                    advance = ((m_advance_bitmap & (1U << hi)) != 0U);
                    m_advance_bitmap &= ~(1U << hi);
                }
 
                if (advance)
                {
                    next = (*m_prev[hi]->GetNext());
                    m_prev[hi] = next;
                }
                else
                {
                    next = m_prev[hi];
                }
 
                if (GetTaskThreshold(next) > hi)
                {
                    m_held[hi] = next;
                    m_held_bitmap |= (1U << hi);
                }
            }
        }
 
        m_running = next;
 
        return next;
    }

    IKernelTask *GetFirst() override
    {
        STK_ASSERT(GetSize() != 0U);
 
        IKernelTask *first_task = nullptr;
 
        if (m_ready_bitmap == 0U)
        {
            first_task = (*m_sleep.GetFirst());
        }
        else
        {
            first_task = (*m_tasks[GetHighestReadyPriority(m_ready_bitmap)].GetFirst());
        }
 
        return first_task;
    }

    size_t GetSize() const override
    {
        size_t total = m_sleep.GetSize();
        for (Priority i = 0U; i < MAX_PRIORITIES; ++i)
        {
            total += m_tasks[i].GetSize();
        }
 
        return total;
    }

    void OnTaskSleep(IKernelTask *task) override
    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(task->IsSleeping());
        STK_ASSERT(task->GetHead() == &m_tasks[GetTaskPriority(task)]);
 
        RemoveActive(task, GetTaskPriority(task));
        m_sleep.LinkBack(task);
    }

    void OnTaskWake(IKernelTask *task) override
    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(!task->IsSleeping());
        STK_ASSERT(task->GetHead() == &m_sleep);
 
        m_sleep.Unlink(task);
        AddActive(task);
    }

    void OnTaskWeightChange(IKernelTask *task, Weight old_weight) override
    {
        const Priority old_prio = DecodePriority(old_weight);
        const Priority new_prio = GetTaskPriority(task);
 
        STK_ASSERT(new_prio < MAX_PRIORITIES);
        STK_ASSERT(old_prio < MAX_PRIORITIES);
 
        if (task->GetHead() != &m_sleep)
        {
            STK_ASSERT(task->GetHead() == &m_tasks[old_prio]);
 
            if (old_prio == new_prio)
            {
                // threshold-only change (IKernelService::SetWeight): no relinking needed
                UpdateHold(task, new_prio);
            }
            else
            {
                const bool was_held = (m_held[old_prio] == task);
 
                RemoveActive(task, old_prio);
                AddActive(task);
 
                // migrate the hold to the new level if the task still has a protected band
                // and the level's (single) hold slot is free
                if (was_held && (GetTaskThreshold(task) > new_prio) && (m_held[new_prio] == nullptr))
                {
                    m_held[new_prio] = task;
                    m_held_bitmap |= (1U << new_prio);
                }
            }
        }
    }

    bool OnTaskYield(IKernelTask *task) override
    {
        STK_ASSERT(task != nullptr);
 
        bool handled = false;
        const Priority prio = GetTaskPriority(task);
 
        if ((prio < MAX_PRIORITIES) && (task->GetHead() == &m_tasks[prio]))
        {
            if (m_held[prio] == task)
            {
                m_held[prio] = nullptr;
                m_held_bitmap &= ~(1U << prio);
            }
 
            m_prev[prio] = task;
            handled      = true;
 
            if __stk_constexpr_cpp17 (TIMESLICE)
            {
                m_advance_bitmap |= (1U << prio);
            }
        }
 
        return handled;
    }

    bool OnTaskTimeSlice(IKernelTask *task) override
    {
        bool rotated = false;
 
        if __stk_constexpr_cpp17 (TIMESLICE)
        {
            STK_ASSERT(task != nullptr);
 
            const Priority prio = GetTaskPriority(task);
 
            // rotation requires a same-priority peer: a lone task simply continues (with a fresh slice
            // reloaded by the kernel), no rotation request is left pending for the level
            if ((prio < MAX_PRIORITIES) && (task->GetHead() == &m_tasks[prio]) && (m_held[prio] != task) &&
                (m_tasks[prio].GetSize() > 1U))
            {
                m_prev[prio] = task;
                rotated      = true;
 
                m_advance_bitmap |= (1U << prio);
            }
        }
 
        return rotated;
    }

    static uint8_t ChangeThreshold(IKernelService &service, TId tid, uint8_t priority, uint8_t threshold)
    {
        STK_ASSERT(priority < MAX_PRIORITIES);
        STK_ASSERT((threshold >= priority) && (threshold < MAX_PRIORITIES));
 
        return DecodeThreshold(service.SetWeight(tid, MakeWeight(priority, threshold)));
    }
 
protected:
    typedef uint8_t Priority;
 
    void AddActive(IKernelTask *task)
    {
        const Priority prio = GetTaskPriority(task);
 
        m_tasks[prio].LinkBack(task);
 
        if (m_tasks[prio].GetSize() == 1U)
        {
            m_prev[prio] = task;
            m_ready_bitmap |= (1U << prio);
        }
    }
 
    void RemoveActive(IKernelTask *task, const Priority prio)
    {
        IKernelTask *const next = (*task->GetNext());
 
        m_tasks[prio].Unlink(task);
 
        if (m_running == task)
        {
            m_running = nullptr;
        }
 
        // release preemption-threshold hold
        if (m_held[prio] == task)
        {
            m_held[prio] = nullptr;
            m_held_bitmap &= ~(1U << prio);
        }
 
        if (next == task)
        {
            m_prev[prio] = nullptr;
            m_ready_bitmap &= ~(1U << prio);
 
            if __stk_constexpr_cpp17 (TIMESLICE)
            {
                m_advance_bitmap &= ~(1U << prio);
            }
        }
        else if (m_prev[prio] == task)
        {
            // cursor was on the removed task: step back so GetNext() returns its successor;
            // otherwise leave the rotation untouched
            m_prev[prio] = (*next->GetPrev());
 
            if __stk_constexpr_cpp17 (TIMESLICE)
            {
                // sticky mode: the successor must run next
                m_advance_bitmap |= (1U << prio);
            }
        }
    }

    void UpdateHold(IKernelTask *task, const Priority prio)
    {
        if (GetTaskThreshold(task) > prio)
        {
            if ((task == m_running) && (m_held[prio] == nullptr))
            {
                m_held[prio] = task;
                m_held_bitmap |= (1U << prio);
            }
        }
        else if (m_held[prio] == task)
        {
            m_held[prio] = nullptr;
            m_held_bitmap &= ~(1U << prio);
        }
        else
        {
            // nothing to update
        }
    }
 
    static __stk_forceinline Priority DecodePriority(Weight weight)
    {
        return static_cast<Priority>((static_cast<uint32_t>(weight) >> 8) & 0xFFU);
    }
 
    static __stk_forceinline Priority GetTaskPriority(IKernelTask *task)
    {
        return DecodePriority(task->GetWeight());
    }
 
    static __stk_forceinline Priority DecodeThreshold(Weight weight)
    {
        return static_cast<Priority>(static_cast<uint32_t>(weight) & 0xFFU);
    }

    static __stk_forceinline Priority GetRawThreshold(IKernelTask *task)
    {
        return DecodeThreshold(task->GetBaseWeight());
    }

    static __stk_forceinline Priority GetTaskThreshold(IKernelTask *task)
    {
        const Priority prio = GetTaskPriority(task);
        const Priority thr  = GetRawThreshold(task);
 
        return (thr > prio ? thr : prio);
    }
 
    static __stk_forceinline Priority GetHighestReadyPriority(uint32_t bitmap)
    {
        return static_cast<Priority>(31U - CountLeadingZeros(bitmap));
    }
 
private:
    STK_NONCOPYABLE_CLASS(SwitchStrategyPreemptionThreshold);
 
    IKernelTask::ListHeadType m_tasks[MAX_PRIORITIES]; 
    IKernelTask::ListHeadType m_sleep;                 
    uint32_t                  m_ready_bitmap;          
    uint32_t                  m_held_bitmap;           
    uint32_t                  m_advance_bitmap;        
    IKernelTask              *m_running;               
    IKernelTask              *m_prev[MAX_PRIORITIES];  
    IKernelTask              *m_held[MAX_PRIORITIES];  
};

typedef SwitchStrategyPreemptionThreshold<32> SwitchStrategyPT32;

typedef SwitchStrategyPreemptionThreshold<32, true> SwitchStrategyPT32_TS;
 
} // namespace stk
 
#endif /* STK_STRATEGY_PTHRESHOLD_H_ */