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