Home | History | Annotate | Download | only in core 
      1 /*******************************************************************************
      2 * Copyright (C) 2018 Cadence Design Systems, Inc.
      3 *
      4 * Permission is hereby granted, free of charge, to any person obtaining
      5 * a copy of this software and associated documentation files (the
      6 * "Software"), to use this Software with Cadence processor cores only and
      7 * not with any other processors and platforms, subject to
      8 * the following conditions:
      9 *
     10 * The above copyright notice and this permission notice shall be included
     11 * in all copies or substantial portions of the Software.
     12 *
     13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
     14 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
     15 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
     16 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
     17 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
     18 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
     19 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
     20 
     21 ******************************************************************************/
     22 
     23 /*******************************************************************************
     24  * xf-sched.c
     25  *
     26  * Non-preemptive earliest-deadline-first scheduler
     27  *
     28  ******************************************************************************/
     29 
     30 #define MODULE_TAG                      SCHED
     31 
     32 /*******************************************************************************
     33  * Includes
     34  ******************************************************************************/
     35 
     36 #include "xf.h"
     37 
     38 /*******************************************************************************
     39  * Tracing configuration
     40  ******************************************************************************/
     41 
     42 TRACE_TAG(DEBUG, 1);
     43 
     44 /*******************************************************************************
     45  * Global functions definitions
     46  ******************************************************************************/
     47 
     48 /* ...place task into scheduler queue */
     49 void xf_sched_put(xf_sched_t *sched, xf_task_t *t, u32 ts)
     50 {
     51     rb_tree_t  *tree = (rb_tree_t *)sched;
     52     rb_node_t  *node = (rb_node_t *)t;
     53     rb_idx_t    p_idx, t_idx;
     54     u32         _ts;
     55 
     56     /* ...set scheduling timestamp */
     57     xf_task_timestamp_set(t, ts);
     58 
     59     /* ...find a place in the tree where the message should be inserted */
     60     for (p_idx = rb_root(tree); p_idx != rb_null(tree); p_idx = t_idx)
     61     {
     62         /* ...get timestamp of the p_idx */
     63         _ts = xf_task_timestamp((xf_task_t *)p_idx);
     64 
     65         /* ...ordering respects FIFO order of messages with same timestamp */
     66         if (xf_timestamp_before(ts, _ts))
     67         {
     68             if ((t_idx = rb_left(tree, p_idx)) == rb_null(tree))
     69             {
     70                 /* ...p_idx is a direct successor of the message */
     71                 rb_set_left(tree, p_idx, node);
     72 
     73                 /* ...adjust head of the tree if needed */
     74                 if (p_idx == rb_cache(tree))    goto insert_head;
     75                 else                            goto insert;
     76             }
     77         }
     78         else
     79         {
     80             if ((t_idx = rb_right(tree, p_idx)) == rb_null(tree))
     81             {
     82                 /* ...p_idx is a direct predeccessor of the message */
     83                 rb_set_right(tree, p_idx, node);
     84 
     85                 goto insert;
     86             }
     87         }
     88     }
     89 
     90 insert_head:
     91     /* ...adjust scheduler head element */
     92     rb_set_cache(tree, node);
     93 
     94 insert:
     95     /* ...insert item and rebalance the tree */
     96     rb_insert(tree, node, p_idx);
     97 
     98     /* ...head cannot be NULL */
     99     BUG(rb_cache(tree) == rb_null(tree), _x("Invalid scheduler state"));
    100 
    101     TRACE(DEBUG, _b("in:  %x:[%p] (ts:%x)"), ts, node, xf_sched_timestamp(sched));
    102 }
    103 
    104 /* ...get first item from the scheduler */
    105 xf_task_t * xf_sched_get(xf_sched_t *sched)
    106 {
    107     rb_tree_t      *tree = (rb_tree_t *)sched;
    108     rb_idx_t        n_idx, t_idx;
    109     u32             ts;
    110 
    111     /* ...head of the tree is cached; replace it with its parent (direct successor) */
    112     if ((n_idx = rb_cache(tree)) == rb_null(tree))
    113     {
    114         /* ...tree is empty; bail out */
    115         return NULL;
    116     }
    117     else
    118     {
    119         /* ...delete current node and rebalance the tree */
    120         t_idx = rb_delete(tree, n_idx), rb_set_cache(tree, t_idx);
    121 
    122         /* ...get task timestamp */
    123         ts = xf_task_timestamp((xf_task_t *)n_idx);
    124 
    125         /* ...advance scheduler timestamp */
    126         xf_sched_timestamp_set(sched, ts);
    127 
    128         TRACE(DEBUG, _b("out: %x:[%p]"), ts, n_idx);
    129 
    130         /* ...return task */
    131         return (xf_task_t *)n_idx;
    132     }
    133 }
    134 
    135 /* ...cancel specified task execution (must be scheduled!) */
    136 void xf_sched_cancel(xf_sched_t *sched, xf_task_t *t)
    137 {
    138     rb_tree_t      *tree = (rb_tree_t *)sched;
    139     rb_idx_t        n_idx = t;
    140     rb_idx_t        t_idx;
    141 
    142     /* ...delete message from tree */
    143     t_idx = rb_delete(tree, n_idx);
    144 
    145     /* ...adjust head if that was the first message */
    146     (n_idx == rb_cache(tree) ? rb_set_cache(tree, t_idx), 1 : 0);
    147 }
    148 
    149 /* ...initialize scheduler data */
    150 void xf_sched_init(xf_sched_t *sched)
    151 {
    152     rb_init((rb_tree_t *)sched);
    153 }
    154