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 */
xf_sched_put(xf_sched_t * sched,xf_task_t * t,u32 ts)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 */
xf_sched_get(xf_sched_t * sched)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!) */
xf_sched_cancel(xf_sched_t * sched,xf_task_t * t)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 */
xf_sched_init(xf_sched_t * sched)150 void xf_sched_init(xf_sched_t *sched)
151 {
152 rb_init((rb_tree_t *)sched);
153 }
154