aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjoern Brandenburg <bbb@mpi-sws.org>2014-06-14 06:42:30 -0400
committerNamhoon Kim <namhoonk@cs.unc.edu>2014-11-03 21:58:03 -0500
commita88daa29933e6c2b1b3b4d616450a35137e59723 (patch)
tree3eff9f6fff8c76725026c7eb70206ceed7fa6420
parent1d65b6286a0f6c13495eefbb41bd1cac3d420cc3 (diff)
Add basic generic reservation-based scheduling infrastructure
Diffstat
-rw-r--r--include/litmus/polling_reservations.h37
-rw-r--r--include/litmus/reservation.h189
-rw-r--r--litmus/Makefile2
-rw-r--r--litmus/polling_reservations.c436
-rw-r--r--litmus/reservation.c298
5 files changed, 962 insertions, 0 deletions
diff --git a/include/litmus/polling_reservations.h b/include/litmus/polling_reservations.h
new file mode 100644
index 000000000000..9958a92b8aeb
--- /dev/null
+++ b/include/litmus/polling_reservations.h
@@ -0,0 +1,37 @@
1#ifndef LITMUS_POLLING_RESERVATIONS_H
2#define LITMUS_POLLING_RESERVATIONS_H
3
4#include <litmus/reservation.h>
5
6struct polling_reservation {
7 /* extend basic reservation */
8 struct reservation res;
9
10 lt_t max_budget;
11 lt_t period;
12 lt_t deadline;
13 lt_t offset;
14};
15
16void polling_reservation_init(struct polling_reservation *pres, int use_edf_prio,
17 int use_periodic_polling, lt_t budget, lt_t period, lt_t deadline, lt_t offset);
18
19struct lt_interval {
20 lt_t start;
21 lt_t end;
22};
23
24struct table_driven_reservation {
25 /* extend basic reservation */
26 struct reservation res;
27
28 lt_t major_cycle;
29 unsigned int next_interval;
30 unsigned int num_intervals;
31 struct lt_interval *intervals;
32};
33
34void table_driven_reservation_init(struct table_driven_reservation *tdres,
35 lt_t major_cycle, struct lt_interval *intervals, unsigned int num_intervals);
36
37#endif
diff --git a/include/litmus/reservation.h b/include/litmus/reservation.h
new file mode 100644
index 000000000000..d8d6ce37dc47
--- /dev/null
+++ b/include/litmus/reservation.h
@@ -0,0 +1,189 @@
1#ifndef LITMUS_RESERVATION_H
2#define LITMUS_RESERVATION_H
3
4#include <linux/list.h>
5#include <linux/hrtimer.h>
6
7struct reservation_client;
8struct reservation_environment;
9struct reservation;
10
11typedef enum {
12 /* reservation has no clients, is not consuming budget */
13 RESERVATION_INACTIVE = 0,
14
15 /* reservation has clients, consumes budget when scheduled */
16 RESERVATION_ACTIVE,
17
18 /* reservation has no clients, but may be consuming budget */
19 RESERVATION_ACTIVE_IDLE,
20
21 /* Reservation has no budget and waits for
22 * replenishment. May or may not have clients. */
23 RESERVATION_DEPLETED,
24} reservation_state_t;
25
26
27/* ************************************************************************** */
28
29/* Select which task to dispatch. If NULL is returned, it means there is nothing
30 * to schedule right now and background work can be scheduled. */
31typedef struct task_struct * (*dispatch_t) (
32 struct reservation_client *client
33);
34
35/* Something that can be managed in a reservation and that can yield
36 * a process for dispatching. */
37struct reservation_client {
38 struct list_head list;
39 dispatch_t dispatch;
40};
41
42
43/* ************************************************************************** */
44
45/* Called by reservations to request state change. */
46typedef void (*reservation_change_state_t) (
47 struct reservation_environment* env,
48 struct reservation *res,
49 reservation_state_t new_state
50);
51
52/* The framework within wich reservations operate. */
53struct reservation_environment {
54 lt_t time_zero;
55 lt_t current_time;
56
57 /* services invoked by reservations */
58 reservation_change_state_t change_state;
59};
60
61
62/* ************************************************************************** */
63
64/* A new client is added or an existing client resumes. */
65typedef void (*client_arrives_t) (
66 struct reservation *reservation,
67 struct reservation_client *client
68);
69
70/* A client suspends or terminates. */
71typedef void (*client_departs_t) (
72 struct reservation *reservation,
73 struct reservation_client *client,
74 int did_signal_job_completion
75);
76
77/* A previously requested replenishment has occurred. */
78typedef void (*on_replenishment_timer_t) (
79 struct reservation *reservation
80);
81
82/* Update the reservation's budget to reflect execution or idling. */
83typedef void (*drain_budget_t) (
84 struct reservation *reservation,
85 lt_t how_much
86);
87
88/* Select a ready task from one of the clients for scheduling. */
89typedef struct task_struct* (*dispatch_client_t) (
90 struct reservation *reservation,
91 lt_t *time_slice /* May be used to force rescheduling after
92 some amount of time. 0 => no limit */
93);
94
95
96struct reservation_ops {
97 dispatch_client_t dispatch_client;
98
99 client_arrives_t client_arrives;
100 client_departs_t client_departs;
101
102 on_replenishment_timer_t replenish;
103 drain_budget_t drain_budget;
104};
105
106struct reservation {
107 /* used to queue in environment */
108 struct list_head list;
109
110 reservation_state_t state;
111 unsigned int id;
112
113 /* exact meaning defined by impl. */
114 lt_t priority;
115 lt_t cur_budget;
116 lt_t next_replenishment;
117
118 /* interaction with framework */
119 struct reservation_environment *env;
120 struct reservation_ops *ops;
121
122 struct list_head clients;
123};
124
125void reservation_init(struct reservation *res);
126
127/* Default implementations */
128
129/* simply select the first client in the list, set *for_at_most to zero */
130struct task_struct* default_dispatch_client(
131 struct reservation *res,
132 lt_t *for_at_most
133);
134
135/* "connector" reservation client to hook up tasks with reservations */
136struct task_client {
137 struct reservation_client client;
138 struct reservation* reservation;
139 struct task_struct *task;
140};
141
142void task_client_init(struct task_client *tc, struct task_struct *task,
143 struct reservation *reservation);
144
145#define SUP_RESCHEDULE_NOW (0)
146#define SUP_NO_SCHEDULER_UPDATE (ULLONG_MAX)
147
148/* A simple uniprocessor (SUP) flat (i.e., non-hierarchical) reservation
149 * environment.
150 */
151struct sup_reservation_environment {
152 struct reservation_environment env;
153
154 /* ordered by priority */
155 struct list_head active_reservations;
156
157 /* ordered by next_replenishment */
158 struct list_head depleted_reservations;
159
160 /* unordered */
161 struct list_head inactive_reservations;
162
163 /* - SUP_RESCHEDULE_NOW means call sup_dispatch() now
164 * - SUP_NO_SCHEDULER_UPDATE means nothing to do
165 * any other value means program a timer for the given time
166 */
167 lt_t next_scheduler_update;
168 /* set to true if a call to sup_dispatch() is imminent */
169 bool will_schedule;
170};
171
172/* Contract:
173 * - before calling into sup_ code, or any reservation methods,
174 * update the time with sup_update_time(); and
175 * - after calling into sup_ code, or any reservation methods,
176 * check next_scheduler_update and program timer or trigger
177 * scheduler invocation accordingly.
178 */
179
180void sup_init(struct sup_reservation_environment* sup_env);
181void sup_add_new_reservation(struct sup_reservation_environment* sup_env,
182 struct reservation* new_res);
183void sup_update_time(struct sup_reservation_environment* sup_env, lt_t now);
184struct task_struct* sup_dispatch(struct sup_reservation_environment* sup_env);
185
186struct reservation* sup_find_by_id(struct sup_reservation_environment* sup_env,
187 unsigned int id);
188
189#endif
diff --git a/litmus/Makefile b/litmus/Makefile
index 84b173a57b7d..e3439c88e1b1 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -32,3 +32,5 @@ obj-$(CONFIG_FEATHER_TRACE) += ft_event.o ftdev.o
32obj-$(CONFIG_SCHED_TASK_TRACE) += sched_task_trace.o 32obj-$(CONFIG_SCHED_TASK_TRACE) += sched_task_trace.o
33obj-$(CONFIG_SCHED_DEBUG_TRACE) += sched_trace.o 33obj-$(CONFIG_SCHED_DEBUG_TRACE) += sched_trace.o
34obj-$(CONFIG_SCHED_OVERHEAD_TRACE) += trace.o 34obj-$(CONFIG_SCHED_OVERHEAD_TRACE) += trace.o
35
36obj-y += reservation.o polling_reservations.o
diff --git a/litmus/polling_reservations.c b/litmus/polling_reservations.c
new file mode 100644
index 000000000000..08034c3556e4
--- /dev/null
+++ b/litmus/polling_reservations.c
@@ -0,0 +1,436 @@
1#include <linux/sched.h>
2
3#include <litmus/litmus.h>
4#include <litmus/reservation.h>
5#include <litmus/polling_reservations.h>
6
7
8static void periodic_polling_client_arrives(
9 struct reservation* res,
10 struct reservation_client *client
11)
12{
13 struct polling_reservation *pres =
14 container_of(res, struct polling_reservation, res);
15 lt_t instances, tmp;
16
17 list_add_tail(&client->list, &res->clients);
18
19 switch (res->state) {
20 case RESERVATION_INACTIVE:
21 /* Figure out next replenishment time. */
22 tmp = res->env->current_time - res->env->time_zero;
23 instances = div64_u64(tmp, pres->period);
24 res->next_replenishment =
25 (instances + 1) * pres->period + pres->offset;
26
27 TRACE("pol-res: activate tmp=%llu instances=%llu period=%llu nextrp=%llu cur=%llu\n",
28 tmp, instances, pres->period, res->next_replenishment,
29 res->env->current_time);
30
31 res->env->change_state(res->env, res,
32 RESERVATION_DEPLETED);
33 break;
34
35 case RESERVATION_ACTIVE:
36 case RESERVATION_DEPLETED:
37 /* do nothing */
38 break;
39
40 case RESERVATION_ACTIVE_IDLE:
41 res->env->change_state(res->env, res,
42 RESERVATION_ACTIVE);
43 break;
44 }
45}
46
47
48static void periodic_polling_client_departs(
49 struct reservation *res,
50 struct reservation_client *client,
51 int did_signal_job_completion
52)
53{
54 list_del(&client->list);
55
56 switch (res->state) {
57 case RESERVATION_INACTIVE:
58 case RESERVATION_ACTIVE_IDLE:
59 BUG(); /* INACTIVE or IDLE <=> no client */
60 break;
61
62 case RESERVATION_ACTIVE:
63 if (list_empty(&res->clients)) {
64 res->env->change_state(res->env, res,
65 did_signal_job_completion ?
66 RESERVATION_DEPLETED :
67 RESERVATION_ACTIVE_IDLE);
68 } /* else: nothing to do, more clients ready */
69 break;
70
71 case RESERVATION_DEPLETED:
72 /* do nothing */
73 break;
74 }
75}
76
77static void periodic_polling_on_replenishment(
78 struct reservation *res
79)
80{
81 struct polling_reservation *pres =
82 container_of(res, struct polling_reservation, res);
83
84 /* replenish budget */
85 res->cur_budget = pres->max_budget;
86 res->next_replenishment += pres->period;
87
88 switch (res->state) {
89 case RESERVATION_DEPLETED:
90 case RESERVATION_INACTIVE:
91 case RESERVATION_ACTIVE_IDLE:
92 if (list_empty(&res->clients))
93 /* no clients => poll again later */
94 res->env->change_state(res->env, res,
95 RESERVATION_INACTIVE);
96 else
97 /* we have clients & budget => ACTIVE */
98 res->env->change_state(res->env, res,
99 RESERVATION_ACTIVE);
100 break;
101
102 case RESERVATION_ACTIVE:
103 /* Replenished while active => tardy? In any case,
104 * go ahead and stay active. */
105 break;
106 }
107}
108
109static void periodic_polling_on_replenishment_edf(
110 struct reservation *res
111)
112{
113 struct polling_reservation *pres =
114 container_of(res, struct polling_reservation, res);
115
116 /* update current priority */
117 res->priority = res->next_replenishment + pres->deadline;
118
119 /* do common updates */
120 periodic_polling_on_replenishment(res);
121}
122
123static void common_drain_budget(
124 struct reservation *res,
125 lt_t how_much)
126{
127 if (how_much >= res->cur_budget)
128 res->cur_budget = 0;
129 else
130 res->cur_budget -= how_much;
131
132 switch (res->state) {
133 case RESERVATION_DEPLETED:
134 case RESERVATION_INACTIVE:
135 BUG();
136 break;
137
138 case RESERVATION_ACTIVE_IDLE:
139 case RESERVATION_ACTIVE:
140 if (!res->cur_budget) {
141 res->env->change_state(res->env, res,
142 RESERVATION_DEPLETED);
143 } /* else: stay in current state */
144 break;
145 }
146}
147
148static struct reservation_ops periodic_polling_ops_fp = {
149 .dispatch_client = default_dispatch_client,
150 .client_arrives = periodic_polling_client_arrives,
151 .client_departs = periodic_polling_client_departs,
152 .replenish = periodic_polling_on_replenishment,
153 .drain_budget = common_drain_budget,
154};
155
156static struct reservation_ops periodic_polling_ops_edf = {
157 .dispatch_client = default_dispatch_client,
158 .client_arrives = periodic_polling_client_arrives,
159 .client_departs = periodic_polling_client_departs,
160 .replenish = periodic_polling_on_replenishment_edf,
161 .drain_budget = common_drain_budget,
162};
163
164
165
166
167static void sporadic_polling_client_arrives_fp(
168 struct reservation* res,
169 struct reservation_client *client
170)
171{
172 struct polling_reservation *pres =
173 container_of(res, struct polling_reservation, res);
174
175 list_add_tail(&client->list, &res->clients);
176
177 switch (res->state) {
178 case RESERVATION_INACTIVE:
179 /* Replenish now. */
180 res->cur_budget = pres->max_budget;
181 res->next_replenishment =
182 res->env->current_time + pres->period;
183
184 res->env->change_state(res->env, res,
185 RESERVATION_ACTIVE);
186 break;
187
188 case RESERVATION_ACTIVE:
189 case RESERVATION_DEPLETED:
190 /* do nothing */
191 break;
192
193 case RESERVATION_ACTIVE_IDLE:
194 res->env->change_state(res->env, res,
195 RESERVATION_ACTIVE);
196 break;
197 }
198}
199
200static void sporadic_polling_client_arrives_edf(
201 struct reservation* res,
202 struct reservation_client *client
203)
204{
205 struct polling_reservation *pres =
206 container_of(res, struct polling_reservation, res);
207
208 list_add_tail(&client->list, &res->clients);
209
210 switch (res->state) {
211 case RESERVATION_INACTIVE:
212 /* Replenish now. */
213 res->cur_budget = pres->max_budget;
214 res->next_replenishment =
215 res->env->current_time + pres->period;
216 res->priority =
217 res->env->current_time + pres->deadline;
218
219 res->env->change_state(res->env, res,
220 RESERVATION_ACTIVE);
221 break;
222
223 case RESERVATION_ACTIVE:
224 case RESERVATION_DEPLETED:
225 /* do nothing */
226 break;
227
228 case RESERVATION_ACTIVE_IDLE:
229 res->env->change_state(res->env, res,
230 RESERVATION_ACTIVE);
231 break;
232 }
233}
234
235static struct reservation_ops sporadic_polling_ops_fp = {
236 .dispatch_client = default_dispatch_client,
237 .client_arrives = sporadic_polling_client_arrives_fp,
238 .client_departs = periodic_polling_client_departs,
239 .replenish = periodic_polling_on_replenishment,
240 .drain_budget = common_drain_budget,
241};
242
243static struct reservation_ops sporadic_polling_ops_edf = {
244 .dispatch_client = default_dispatch_client,
245 .client_arrives = sporadic_polling_client_arrives_edf,
246 .client_departs = periodic_polling_client_departs,
247 .replenish = periodic_polling_on_replenishment_edf,
248 .drain_budget = common_drain_budget,
249};
250
251void polling_reservation_init(
252 struct polling_reservation *pres,
253 int use_edf_prio,
254 int use_periodic_polling,
255 lt_t budget, lt_t period, lt_t deadline, lt_t offset
256)
257{
258 if (!deadline)
259 deadline = period;
260 BUG_ON(budget > period);
261 BUG_ON(budget > deadline);
262 BUG_ON(offset >= period);
263
264 reservation_init(&pres->res);
265 pres->max_budget = budget;
266 pres->period = period;
267 pres->deadline = deadline;
268 pres->offset = offset;
269 if (use_periodic_polling) {
270 if (use_edf_prio)
271 pres->res.ops = &periodic_polling_ops_edf;
272 else
273 pres->res.ops = &periodic_polling_ops_fp;
274 } else {
275 if (use_edf_prio)
276 pres->res.ops = &sporadic_polling_ops_edf;
277 else
278 pres->res.ops = &sporadic_polling_ops_fp;
279 }
280}
281
282
283static lt_t td_cur_major_cycle_start(struct table_driven_reservation *tdres)
284{
285 lt_t x, tmp;
286
287 tmp = tdres->res.env->current_time - tdres->res.env->time_zero;
288 x = div64_u64(tmp, tdres->major_cycle);
289 x *= tdres->major_cycle;
290 return x;
291}
292
293
294static lt_t td_next_major_cycle_start(struct table_driven_reservation *tdres)
295{
296 lt_t x, tmp;
297
298 tmp = tdres->res.env->current_time - tdres->res.env->time_zero;
299 x = div64_u64(tmp, tdres->major_cycle) + 1;
300 x *= tdres->major_cycle;
301 return x;
302}
303
304static void td_client_arrives(
305 struct reservation* res,
306 struct reservation_client *client
307)
308{
309 struct table_driven_reservation *tdres =
310 container_of(res, struct table_driven_reservation, res);
311
312 list_add_tail(&client->list, &res->clients);
313
314 switch (res->state) {
315 case RESERVATION_INACTIVE:
316 /* Figure out first replenishment time. */
317 res->next_replenishment = td_next_major_cycle_start(tdres);
318 res->next_replenishment += tdres->intervals[0].start;
319 tdres->next_interval = 0;
320
321 res->env->change_state(res->env, res,
322 RESERVATION_DEPLETED);
323 break;
324
325 case RESERVATION_ACTIVE:
326 case RESERVATION_DEPLETED:
327 /* do nothing */
328 break;
329
330 case RESERVATION_ACTIVE_IDLE:
331 res->env->change_state(res->env, res,
332 RESERVATION_ACTIVE);
333 break;
334 }
335}
336
337static void td_client_departs(
338 struct reservation *res,
339 struct reservation_client *client,
340 int did_signal_job_completion
341)
342{
343 list_del(&client->list);
344
345 switch (res->state) {
346 case RESERVATION_INACTIVE:
347 case RESERVATION_ACTIVE_IDLE:
348 BUG(); /* INACTIVE or IDLE <=> no client */
349 break;
350
351 case RESERVATION_ACTIVE:
352 if (list_empty(&res->clients)) {
353 res->env->change_state(res->env, res,
354 RESERVATION_ACTIVE_IDLE);
355 } /* else: nothing to do, more clients ready */
356 break;
357
358 case RESERVATION_DEPLETED:
359 /* do nothing */
360 break;
361 }
362}
363
364static lt_t td_interval_length(struct lt_interval *ival)
365{
366 return ival->end - ival->start;
367}
368
369static void td_replenish(
370 struct reservation *res
371)
372{
373 struct table_driven_reservation *tdres =
374 container_of(res, struct table_driven_reservation, res);
375
376 /* replenish budget */
377 res->cur_budget = td_interval_length(tdres->intervals + tdres->next_interval);
378
379 tdres->next_interval = (tdres->next_interval + 1) % tdres->num_intervals;
380 if (tdres->next_interval)
381 res->next_replenishment = td_cur_major_cycle_start(tdres);
382 else
383 /* wrap to next major cycle */
384 res->next_replenishment = td_next_major_cycle_start(tdres);
385 res->next_replenishment += tdres->intervals[tdres->next_interval].start;
386
387
388 switch (res->state) {
389 case RESERVATION_DEPLETED:
390 case RESERVATION_ACTIVE:
391 case RESERVATION_ACTIVE_IDLE:
392 if (list_empty(&res->clients))
393 res->env->change_state(res->env, res,
394 RESERVATION_ACTIVE_IDLE);
395 else
396 /* we have clients & budget => ACTIVE */
397 res->env->change_state(res->env, res,
398 RESERVATION_ACTIVE);
399 break;
400
401 case RESERVATION_INACTIVE:
402 BUG();
403 break;
404 }
405}
406
407static struct reservation_ops td_ops = {
408 .dispatch_client = default_dispatch_client,
409 .client_arrives = td_client_arrives,
410 .client_departs = td_client_departs,
411 .replenish = td_replenish,
412 .drain_budget = common_drain_budget,
413};
414
415void table_driven_reservation_init(
416 struct table_driven_reservation *tdres,
417 lt_t major_cycle,
418 struct lt_interval *intervals,
419 unsigned int num_intervals)
420{
421 unsigned int i;
422
423 /* sanity checking */
424 BUG_ON(!num_intervals);
425 for (i = 0; i < num_intervals; i++)
426 BUG_ON(intervals[i].end <= intervals[i].start);
427 for (i = 0; i + 1 < num_intervals; i++)
428 BUG_ON(intervals[i + 1].start <= intervals[i].end);
429 BUG_ON(intervals[num_intervals - 1].end > major_cycle);
430
431 reservation_init(&tdres->res);
432 tdres->major_cycle = major_cycle;
433 tdres->intervals = intervals;
434 tdres->num_intervals = num_intervals;
435 tdres->res.ops = &td_ops;
436}
diff --git a/litmus/reservation.c b/litmus/reservation.c
new file mode 100644
index 000000000000..bc32b2ecace4
--- /dev/null
+++ b/litmus/reservation.c
@@ -0,0 +1,298 @@
1#include <linux/sched.h>
2
3#include <litmus/litmus.h>
4#include <litmus/reservation.h>
5
6void reservation_init(struct reservation *res)
7{
8 memset(res, sizeof(*res), 0);
9 res->state = RESERVATION_INACTIVE;
10 INIT_LIST_HEAD(&res->clients);
11}
12
13struct task_struct* default_dispatch_client(
14 struct reservation *res,
15 lt_t *for_at_most)
16{
17 struct reservation_client *client, *next;
18 struct task_struct* tsk;
19
20 BUG_ON(res->state != RESERVATION_ACTIVE);
21 *for_at_most = 0;
22
23 list_for_each_entry_safe(client, next, &res->clients, list) {
24 tsk = client->dispatch(client);
25 if (likely(tsk)) {
26 return tsk;
27 }
28 }
29 return NULL;
30}
31
32static struct task_struct * task_client_dispatch(struct reservation_client *client)
33{
34 struct task_client *tc = container_of(client, struct task_client, client);
35 return tc->task;
36}
37
38void task_client_init(struct task_client *tc, struct task_struct *tsk,
39 struct reservation *res)
40{
41 memset(&tc->client, sizeof(tc->client), 0);
42 tc->client.dispatch = task_client_dispatch;
43 tc->task = tsk;
44 tc->reservation = res;
45}
46
47static void sup_scheduler_update_at(
48 struct sup_reservation_environment* sup_env,
49 lt_t when)
50{
51 if (sup_env->next_scheduler_update > when)
52 sup_env->next_scheduler_update = when;
53}
54
55static void sup_scheduler_update_after(
56 struct sup_reservation_environment* sup_env,
57 lt_t timeout)
58{
59 sup_scheduler_update_at(sup_env, sup_env->env.current_time + timeout);
60}
61
62static int _sup_queue_depleted(
63 struct sup_reservation_environment* sup_env,
64 struct reservation *res)
65{
66 struct list_head *pos;
67 struct reservation *queued;
68 int passed_earlier = 0;
69
70 list_for_each(pos, &sup_env->depleted_reservations) {
71 queued = list_entry(pos, struct reservation, list);
72 if (queued->next_replenishment > res->next_replenishment) {
73 list_add(&res->list, pos->prev);
74 return passed_earlier;
75 } else
76 passed_earlier = 1;
77 }
78
79 list_add_tail(&res->list, &sup_env->depleted_reservations);
80
81 return passed_earlier;
82}
83
84static void sup_queue_depleted(
85 struct sup_reservation_environment* sup_env,
86 struct reservation *res)
87{
88 int passed_earlier = _sup_queue_depleted(sup_env, res);
89
90 /* check for updated replenishment time */
91 if (!passed_earlier)
92 sup_scheduler_update_at(sup_env, res->next_replenishment);
93}
94
95static int _sup_queue_active(
96 struct sup_reservation_environment* sup_env,
97 struct reservation *res)
98{
99 struct list_head *pos;
100 struct reservation *queued;
101 int passed_active = 0;
102
103 list_for_each(pos, &sup_env->active_reservations) {
104 queued = list_entry(pos, struct reservation, list);
105 if (queued->priority > res->priority) {
106 list_add(&res->list, pos->prev);
107 return passed_active;
108 } else if (queued->state == RESERVATION_ACTIVE)
109 passed_active = 1;
110 }
111
112 list_add_tail(&res->list, &sup_env->active_reservations);
113 return passed_active;
114}
115
116static void sup_queue_active(
117 struct sup_reservation_environment* sup_env,
118 struct reservation *res)
119{
120 int passed_active = _sup_queue_active(sup_env, res);
121
122 /* check for possible preemption */
123 if (res->state == RESERVATION_ACTIVE && !passed_active)
124 sup_env->next_scheduler_update = SUP_RESCHEDULE_NOW;
125}
126
127
128static void sup_queue_reservation(
129 struct sup_reservation_environment* sup_env,
130 struct reservation *res)
131{
132 switch (res->state) {
133 case RESERVATION_INACTIVE:
134 list_add(&res->list, &sup_env->inactive_reservations);
135 break;
136
137 case RESERVATION_DEPLETED:
138 sup_queue_depleted(sup_env, res);
139 break;
140
141 case RESERVATION_ACTIVE_IDLE:
142 case RESERVATION_ACTIVE:
143 sup_queue_active(sup_env, res);
144 break;
145 }
146}
147
148void sup_add_new_reservation(
149 struct sup_reservation_environment* sup_env,
150 struct reservation* new_res)
151{
152 new_res->env = &sup_env->env;
153 sup_queue_reservation(sup_env, new_res);
154}
155
156struct reservation* sup_find_by_id(struct sup_reservation_environment* sup_env,
157 unsigned int id)
158{
159 struct reservation *res;
160
161 list_for_each_entry(res, &sup_env->active_reservations, list) {
162 if (res->id == id)
163 return res;
164 }
165 list_for_each_entry(res, &sup_env->inactive_reservations, list) {
166 if (res->id == id)
167 return res;
168 }
169 list_for_each_entry(res, &sup_env->depleted_reservations, list) {
170 if (res->id == id)
171 return res;
172 }
173
174 return NULL;
175}
176
177static void sup_charge_budget(
178 struct sup_reservation_environment* sup_env,
179 lt_t delta)
180{
181 struct list_head *pos, *next;
182 struct reservation *res;
183
184 list_for_each_safe(pos, next, &sup_env->active_reservations) {
185 /* charge all ACTIVE_IDLE up to the first ACTIVE reservation */
186 res = list_entry(pos, struct reservation, list);
187 if (res->state == RESERVATION_ACTIVE) {
188 res->ops->drain_budget(res, delta);
189 /* stop at the first ACTIVE reservation */
190 break;
191 } else {
192 BUG_ON(res->state != RESERVATION_ACTIVE_IDLE);
193 res->ops->drain_budget(res, delta);
194 }
195 }
196}
197
198static void sup_replenish_budgets(struct sup_reservation_environment* sup_env)
199{
200 struct list_head *pos, *next;
201 struct reservation *res;
202
203 list_for_each_safe(pos, next, &sup_env->depleted_reservations) {
204 res = list_entry(pos, struct reservation, list);
205 if (res->next_replenishment <= sup_env->env.current_time) {
206 res->ops->replenish(res);
207 } else {
208 /* list is ordered by increasing depletion times */
209 break;
210 }
211 }
212
213 /* request a scheduler update at the next replenishment instant */
214 res = list_first_entry_or_null(&sup_env->depleted_reservations,
215 struct reservation, list);
216 if (res)
217 sup_scheduler_update_at(sup_env, res->next_replenishment);
218}
219
220void sup_update_time(
221 struct sup_reservation_environment* sup_env,
222 lt_t now)
223{
224 lt_t delta;
225
226 /* If the time didn't advance, there is nothing to do.
227 * This check makes it safe to call sup_advance_time() potentially
228 * multiple times (e.g., via different code paths. */
229 if (unlikely(now <= sup_env->env.current_time))
230 return;
231
232 delta = now - sup_env->env.current_time;
233 sup_env->env.current_time = now;
234
235 /* check if future updates are required */
236 if (sup_env->next_scheduler_update <= sup_env->env.current_time)
237 sup_env->next_scheduler_update = SUP_NO_SCHEDULER_UPDATE;
238
239 /* deplete budgets by passage of time */
240 sup_charge_budget(sup_env, delta);
241
242 /* check if any budgets where replenished */
243 sup_replenish_budgets(sup_env);
244}
245
246struct task_struct* sup_dispatch(struct sup_reservation_environment* sup_env)
247{
248 struct reservation *res, *next;
249 struct task_struct *tsk = NULL;
250 lt_t time_slice;
251
252 list_for_each_entry_safe(res, next, &sup_env->active_reservations, list) {
253 if (res->state == RESERVATION_ACTIVE) {
254 tsk = res->ops->dispatch_client(res, &time_slice);
255 if (likely(tsk)) {
256 if (time_slice)
257 sup_scheduler_update_after(sup_env, time_slice);
258 sup_scheduler_update_after(sup_env, res->cur_budget);
259 return tsk;
260 }
261 }
262 }
263
264 return NULL;
265}
266
267static void sup_res_change_state(
268 struct reservation_environment* env,
269 struct reservation *res,
270 reservation_state_t new_state)
271{
272 struct sup_reservation_environment* sup_env;
273
274 sup_env = container_of(env, struct sup_reservation_environment, env);
275
276 TRACE("reservation R%d state %d->%d at %llu\n",
277 res->id, res->state, new_state, env->current_time);
278
279 list_del(&res->list);
280 /* check if we need to reschedule because we lost an active reservation */
281 if (res->state == RESERVATION_ACTIVE && !sup_env->will_schedule)
282 sup_env->next_scheduler_update = SUP_RESCHEDULE_NOW;
283 res->state = new_state;
284 sup_queue_reservation(sup_env, res);
285}
286
287void sup_init(struct sup_reservation_environment* sup_env)
288{
289 memset(sup_env, sizeof(*sup_env), 0);
290
291 INIT_LIST_HEAD(&sup_env->active_reservations);
292 INIT_LIST_HEAD(&sup_env->depleted_reservations);
293 INIT_LIST_HEAD(&sup_env->inactive_reservations);
294
295 sup_env->env.change_state = sup_res_change_state;
296
297 sup_env->next_scheduler_update = SUP_NO_SCHEDULER_UPDATE;
298}
generated by cgit v1.2.2 (git 2.25.0) at 2024-06-02 12:09:27 -0400