os-lists.cpp

Go to the documentation of this file.

/*
 * This file is part of the µOS++ distribution.
 *   (https://github.com/micro-os-plus)
 * Copyright (c) 2016 Liviu Ionescu.
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom
 * the Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */

#include <cmsis-plus/rtos/os.h>

#include <cmsis-plus/diag/trace.h>

namespace os
{
  namespace rtos
  {
    namespace internal
    {
      // ======================================================================

      void
      thread_children_list::link (thread& thread)
      {
        // Add thread intrusive node at the end of the list.
        insert_after (thread.child_links_,
                      const_cast<utils::static_double_list_links*> (tail ()));
      }

      // ======================================================================

      void
      ready_threads_list::link (waiting_thread_node& node)
      {
        if (head_.prev () == nullptr)
          {
            // If this is the first time, initialise the list to empty.
            clear ();
          }

        thread::priority_t prio = node.thread_->priority ();

        waiting_thread_node* after =
            static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (tail ()));

        if (empty ())
          {
            // Insert at the end of the list.
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("ready %s() empty +%u\n", __func__, prio);
#endif
          }
        else if (prio <= after->thread_->priority ())
          {
            // Insert at the end of the list.
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("ready %s() back %u +%u \n", __func__,
                           after->thread_->priority (), prio);
#endif
          }
        else if (prio > head ()->thread_->priority ())
          {
            // Insert at the beginning of the list.
            after =
                static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (&head_));
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("ready %s() front +%u %u \n", __func__, prio,
                           head ()->thread_->priority ());
#endif
          }
        else
          {
            // Insert in the middle of the list.
            // The loop is guaranteed to terminate, and not hit the head.
            // The weight is relatively small, priority() is not heavy.
            while (prio > after->thread_->priority ())
              {
                after =
                    static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (after->prev ()));
              }
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("ready %s() middle %u +%u \n", __func__,
                           after->thread_->priority (), prio);
#endif
          }

        insert_after (node, after);

        node.thread_->state_ = thread::state::ready;
      }

      thread*
      ready_threads_list::unlink_head (void)
      {
        assert (!empty ());

        thread* th = head ()->thread_;

#if defined(OS_TRACE_RTOS_LISTS)
        trace::printf ("ready %s() %p %s\n", __func__, th, th->name ());
#endif

        const_cast<waiting_thread_node*> (head ())->unlink ();

        assert (th != nullptr);

        // Unlinking is immediately followed by a context switch,
        // so in order to guarantee that the thread is marked as
        // running, it is saver to do it here.

        th->state_ = thread::state::running;
        return th;
      }

      // ======================================================================

      void
      waiting_threads_list::link (waiting_thread_node& node)
      {
        thread::priority_t prio = node.thread_->priority ();

        waiting_thread_node* after =
            static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (tail ()));

        if (empty ())
          {
            // Insert at the end of the list.
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("wait %s() empty +%u\n", __func__, prio);
#endif
          }
        else if (prio <= after->thread_->priority ())
          {
            // Insert at the end of the list.
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("wait %s() back %u +%u \n", __func__,
                           after->thread_->priority (), prio);
#endif
          }
        else if (prio > head ()->thread_->priority ())
          {
            // Insert at the beginning of the list.
            after =
                static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (&head_));
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("wait %s() front +%u %u \n", __func__, prio,
                           head ()->thread_->priority ());
#endif
          }
        else
          {
            // Insert in the middle of the list.
            // The loop is guaranteed to terminate, and not hit the head.
            // The weight is relatively small, priority() is not heavy.
            while (prio > after->thread_->priority ())
              {
                after =
                    static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (after->prev ()));
              }
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("wait %s() middle %u +%u \n", __func__,
                           after->thread_->priority (), prio);
#endif
          }

        insert_after (node, after);
      }

      bool
      waiting_threads_list::resume_one (void)
      {
        thread* th;
          {
            // ----- Enter critical section -----------------------------------
            interrupts::critical_section ics;

            // If the list is empty, silently return.
            if (empty ())
              {
                return false;
              }

            // The top priority is to remove the entry from the list
            // so that subsequent wakeups to address different threads.
            th = head ()->thread_;
            const_cast<waiting_thread_node*> (head ())->unlink ();
            // ----- Exit critical section ------------------------------------
          }
        assert (th != nullptr);

        thread::state_t state = th->state ();
        if (state != thread::state::destroyed)
          {
            th->resume ();
          }
        else
          {
#if defined(OS_TRACE_RTOS_LISTS)
            trace::printf ("%s() gone \n", __func__);
#endif
          }

        return true;
      }

      void
      waiting_threads_list::resume_all (void)
      {
        while (resume_one ())
          ;
      }

      // ======================================================================

      timestamp_node::timestamp_node (clock::timestamp_t ts) :
          timestamp (ts)
      {
#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
        trace::printf ("%s() %p \n", __func__, this);
#endif
      }

      timestamp_node::~timestamp_node ()
      {
#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
        trace::printf ("%s() %p \n", __func__, this);
#endif
      }

      // ======================================================================

      timeout_thread_node::timeout_thread_node (clock::timestamp_t ts,
                                                rtos::thread& th) :
          timestamp_node
            { ts }, //
          thread (th)
      {
#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
        trace::printf ("%s() %p \n", __func__, this);
#endif
      }

      timeout_thread_node::~timeout_thread_node ()
      {
#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
        trace::printf ("%s() %p \n", __func__, this);
#endif
      }

      // Must be called in a critical section.
      void
      timeout_thread_node::action (void)
      {
        rtos::thread* th = &this->thread;
        this->unlink ();

        thread::state_t state = th->state ();
        if (state != thread::state::destroyed)
          {
            th->resume ();
          }
      }

      // ======================================================================

#if !defined(OS_USE_RTOS_PORT_TIMER)

      timer_node::timer_node (clock::timestamp_t ts, timer& tm) :
          timestamp_node
            { ts }, //
          tmr (tm)
      {
#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
        trace::printf ("%s() %p \n", __func__, this);
#endif
      }

      timer_node::~timer_node ()
      {
#if defined(OS_TRACE_RTOS_LISTS_CONSTRUCT)
        trace::printf ("%s() %p \n", __func__, this);
#endif
      }

      void
      timer_node::action (void)
      {
        this->unlink ();
        tmr.internal_interrupt_service_routine ();
      }

#endif

      // ======================================================================

      void
      clock_timestamps_list::link (timestamp_node& node)
      {
        clock::timestamp_t timestamp = node.timestamp;

        timeout_thread_node* after =
            static_cast<timeout_thread_node*> (const_cast<utils::static_double_list_links *> (tail ()));

        if (empty ())
          {
            // Insert at the end of the list.
#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
            trace::printf ("clock %s() empty +%u\n", __func__,
                static_cast<uint32_t> (timestamp));
#endif
          }
        else if (timestamp >= after->timestamp)
          {
            // Insert at the end of the list.
#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
            trace::printf ("clock %s() back %u +%u\n", __func__,
                static_cast<uint32_t> (after->timestamp),
                static_cast<uint32_t> (timestamp));
#endif
          }
        else if (timestamp < head ()->timestamp)
          {
            // Insert at the beginning of the list
            // and update the new head.
            after =
                static_cast<timeout_thread_node*> (const_cast<utils::static_double_list_links *> (&head_));
#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
            trace::printf ("clock %s() front +%u %u\n", __func__,
                static_cast<uint32_t> (timestamp),
                static_cast<uint32_t> (head ()->timestamp));
#endif
          }
        else
          {
            // Insert in the middle of the list.
            // The loop is guaranteed to terminate.
            while (timestamp < after->timestamp)
              {
                after =
                    static_cast<timeout_thread_node*> (const_cast<utils::static_double_list_links *> (after->prev ()));
              }
#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
            trace::printf ("clock %s() middle %u +%u\n", __func__,
                static_cast<uint32_t> (after->timestamp),
                static_cast<uint32_t> (timestamp));
#endif
          }

        insert_after (node, after);
      }

      void
      clock_timestamps_list::check_timestamp (clock::timestamp_t now)
      {
        if (head_.next () == nullptr)
          {
            // This happens before the constructors are executed.
            return;
          }

        // Multiple threads can wait for the same time stamp, so
        // iterate until a node with future time stamp is identified.
        for (;;)
          {
            // ----- Enter critical section -----------------------------------
            interrupts::critical_section ics;

            if (empty ())
              {
                break;
              }
            clock::timestamp_t head_ts = head ()->timestamp;
            if (now >= head_ts)
              {
#if defined(OS_TRACE_RTOS_LISTS_CLOCKS)
                trace::printf ("%s() %u \n", __func__,
                    static_cast<uint32_t> (sysclock.now ()));
#endif
                const_cast<timestamp_node*> (head ())->action ();
              }
            else
              {
                break;
              }
            // ----- Exit critical section ------------------------------------
          }
      }

      // ======================================================================

      void
      terminated_threads_list::link (waiting_thread_node& node)
      {
        if (head_.prev () == nullptr)
          {
            // If this is the first time, initialise the list to empty.
            clear ();
          }

        waiting_thread_node* after =
            static_cast<waiting_thread_node*> (const_cast<utils::static_double_list_links *> (tail ()));

#if defined(OS_TRACE_RTOS_THREAD)
        trace::printf ("terminated %s() %p %s\n", __func__, &node.thread_,
                       node.thread_->name ());
#endif

        node.thread_->state_ = thread::state::terminated;

        insert_after (node, after);
      }

    // ------------------------------------------------------------------------
    } /* namespace internal */
  } /* namespace rtos */
} /* namespace os */