aboutsummaryrefslogtreecommitdiffstats
path: root/include/litmus
diff options
context:
space:
mode:
authorBjoern Brandenburg <bbb@mpi-sws.org>2015-08-09 07:18:48 -0400
committerBjoern Brandenburg <bbb@mpi-sws.org>2017-05-26 17:12:28 -0400
commit3baa55c19ffb567aa48568fa69dd17ad6f70d31d (patch)
tree7e79fd398705929f2db40ba239895cc60762f61f /include/litmus
parentcbe61859a233702ed8e6723b3b133d1f2ae1ae2c (diff)
Add LITMUS^RT core implementation
This patch adds the core of LITMUS^RT: - library functionality (heaps, rt_domain, prioritization, etc.) - budget enforcement logic - job management - system call backends - virtual devices (control page, etc.) - scheduler plugin API (and dummy plugin) This code compiles, but is not yet integrated with the rest of Linux. Squashed changes: LITMUS^RT Core: add get_current_budget() system call Allow userspace to figure out the used-up and remaining budget of a task. Adds deadline field to control page and updates it when setting up jobs for release. Adds control page deadline offset ftdev: respect O_NONBLOCK flag in ftdev_read() Don't block if userspace wants to go on doing something else. Export job release time and job sequence number in ctrl page Add alternate complete_job() default implementation Let jobs sleep like regular Linux tasks by suspending and waking them with a one-shot timer. Plugins can opt into using this implementation instead of the classic complete_job() implementation (or custom implementations). Fix RCU locking in sys_get_rt_task_param() sys_get_rt_task_param() is rarely used and apparently attracted some bitrot. Free before setting NULL to prevent memory leak Add hrtimer_start_on() support This patch replaces the previous implementation of hrtimer_start_on() by now using smp_call_function_single_async() to arm hrtimers on remote CPUs. Expose LITMUS^RT system calls via control page ioctl() Rationale: make LITMUS^RT ops available in a way that does not create merge conflicts each time we rebase LITMUS^RT on top of a new kernel version. This also helps with portability to different architectures, as we no longer need to patch each architecture's syscall table. Pick non-zero syscall ID start range To avoid interfering with Linux's magic reserved IOCTL numbers Don't preempt before time check in sleep_until_next_release() Avoid preempting jobs that are about to go to sleep soon anyway. LITMUS^RT proc: fix wrong memset() TRACE(): add TRACE_WARN_ON() helper Useful to replace BUG_ON() and WARN_ON() with a non-fatal TRACE()-based equivalent. Add void* plugin_state pointer to task_struct LITMUS^RT: split task admission into two functions Plugin interface: add fork_task() callback LITMUS^RT: Enable plugins to permit RT tasks to fork one-shot complete_job(): set completed flag This could race with a SIGSTOP or some other forced suspension, but we'll let plugins handle this, should they actually care. FP: add list-based ready queue LITMUS^RT core: add should_wait_for_stack() callback Allow plugins to give up when waiting for a stack to become available. LITMUS^RT core: add next_became_invalid() callback LITMUS^RT core: add post-migration validation callback LITMUS^RT core: be more careful when pull-migrating tasks Close more race windows and give plugins a chance to validate tasks after they have been migrated. Add KConfig options for timer latency warnings Add reservation creation API to plugin interface & syscalls LITMUS^RT syscall: expose sys_reservation_create() via ioctl() Add reservation configuration types to rt_param.h Add basic generic reservation-based scheduling infrastructure Switch to aligned quanta by default. For first-time users, aligned quanta is likely what's expected. LITMUS^RT core: keep track of time of last suspension This information is needed to insert ST_COMPLETION records for sporadic tasks. add fields for clock_nanosleep() support Need to communicate the intended wake-up time to the plugin wake-up handler. LITMUS^RT core: add generic handler for sporadic job arrivals In particular, check if a job arrival is triggered from a clock_nanosleep() call. add litmus->task_change_params() callback to plugin interface Will be used by adaptive C-EDF. Call litmus->task_change_params() from sys_set_rt_task_param() Move trace point definition to litmus/litmus.c If !CONFIG_SCHED_TASK_TRACE, but CONFIG_SCHED_LITMUS_TRACEPOINT, then we still need to define the tracepoint structures. This patch should be integrated with the earlier sched_task_trace.c patches during one of the next major rebasing efforts. LITMUS^RT scheduling class: mark enqueued task as present Remove unistd_*.h rebase fix: update to new hrtimer API The new API is actually nicer and cleaner. rebase fix: call lockdep_unpin_lock(&rq->lock, cookie) The LITMUS^RT scheduling class should also do the LOCKDEP dance. LITMUS^RT core: break out non-preemptive flag defs Not every file including litmus.h needs to know this. LITMUS^RT core: don't include debug_trace.h in litmus.h Including debug_trace.h introduces the TRACE() macro, which causes symbol clashes in some (rather obscure) drivers. LITMUS^RT core: add litmus_preemption_in_progress flags Used to communicate that a preemption is in progress. Set by the scheduler; read by the plugins. LITMUS^RT core: revise is_current_running() macro
Diffstat (limited to 'include/litmus')
-rw-r--r--include/litmus/affinity.h52
-rw-r--r--include/litmus/bheap.h77
-rw-r--r--include/litmus/binheap.h205
-rw-r--r--include/litmus/budget.h38
-rw-r--r--include/litmus/ceiling.h36
-rw-r--r--include/litmus/clustered.h46
-rw-r--r--include/litmus/ctrlpage.h105
-rw-r--r--include/litmus/debug_trace.h5
-rw-r--r--include/litmus/edf_common.h25
-rw-r--r--include/litmus/fdso.h78
-rw-r--r--include/litmus/fp_common.h183
-rw-r--r--include/litmus/fpmath.h147
-rw-r--r--include/litmus/jobs.h13
-rw-r--r--include/litmus/litmus.h163
-rw-r--r--include/litmus/litmus_proc.h63
-rw-r--r--include/litmus/locking.h28
-rw-r--r--include/litmus/np.h121
-rw-r--r--include/litmus/preempt.h188
-rw-r--r--include/litmus/reservations/alloc.h15
-rw-r--r--include/litmus/reservations/budget-notifier.h50
-rw-r--r--include/litmus/reservations/polling.h19
-rw-r--r--include/litmus/reservations/reservation.h224
-rw-r--r--include/litmus/reservations/table-driven.h23
-rw-r--r--include/litmus/rt_domain.h182
-rw-r--r--include/litmus/rt_param.h105
-rw-r--r--include/litmus/sched_plugin.h180
-rw-r--r--include/litmus/srp.h28
-rw-r--r--include/litmus/wait.h57
28 files changed, 2403 insertions, 53 deletions
diff --git a/include/litmus/affinity.h b/include/litmus/affinity.h
new file mode 100644
index 000000000000..4d7c618c8175
--- /dev/null
+++ b/include/litmus/affinity.h
@@ -0,0 +1,52 @@
1#ifndef __LITMUS_AFFINITY_H
2#define __LITMUS_AFFINITY_H
3
4#include <linux/cpumask.h>
5
6/* Works like:
7void get_nearest_available_cpu(
8 cpu_entry_t **nearest,
9 cpu_entry_t *start,
10 cpu_entry_t *entries,
11 int release_master,
12 cpumask_var_t cpus_to_test)
13
14Set release_master = NO_CPU for no Release Master.
15
16We use a macro here to exploit the fact that C-EDF and G-EDF
17have similar structures for their cpu_entry_t structs, even though
18they do not share a common base-struct. The macro allows us to
19avoid code duplication.
20
21 */
22#define get_nearest_available_cpu(nearest, start, entries, release_master, cpus_to_test) \
23{ \
24 (nearest) = NULL; \
25 if (!(start)->linked && likely((start)->cpu != (release_master))) { \
26 (nearest) = (start); \
27 } else { \
28 int __cpu; \
29 \
30 /* FIXME: get rid of the iteration with a bitmask + AND */ \
31 for_each_cpu(__cpu, cpus_to_test) { \
32 if (likely(__cpu != release_master)) { \
33 cpu_entry_t *__entry = &per_cpu((entries), __cpu); \
34 if (cpus_share_cache((start)->cpu, __entry->cpu) \
35 && !__entry->linked) { \
36 (nearest) = __entry; \
37 break; \
38 } \
39 } \
40 } \
41 } \
42 \
43 if ((nearest)) { \
44 TRACE("P%d is closest available CPU to P%d\n", \
45 (nearest)->cpu, (start)->cpu); \
46 } else { \
47 TRACE("Could not find an available CPU close to P%d\n", \
48 (start)->cpu); \
49 } \
50}
51
52#endif
diff --git a/include/litmus/bheap.h b/include/litmus/bheap.h
new file mode 100644
index 000000000000..cf4864a498d8
--- /dev/null
+++ b/include/litmus/bheap.h
@@ -0,0 +1,77 @@
1/* bheaps.h -- Binomial Heaps
2 *
3 * (c) 2008, 2009 Bjoern Brandenburg
4 */
5
6#ifndef BHEAP_H
7#define BHEAP_H
8
9#define NOT_IN_HEAP UINT_MAX
10
11struct bheap_node {
12 struct bheap_node* parent;
13 struct bheap_node* next;
14 struct bheap_node* child;
15
16 unsigned int degree;
17 void* value;
18 struct bheap_node** ref;
19};
20
21struct bheap {
22 struct bheap_node* head;
23 /* We cache the minimum of the heap.
24 * This speeds up repeated peek operations.
25 */
26 struct bheap_node* min;
27};
28
29typedef int (*bheap_prio_t)(struct bheap_node* a, struct bheap_node* b);
30
31void bheap_init(struct bheap* heap);
32void bheap_node_init(struct bheap_node** ref_to_bheap_node_ptr, void* value);
33
34static inline int bheap_node_in_heap(struct bheap_node* h)
35{
36 return h->degree != NOT_IN_HEAP;
37}
38
39static inline int bheap_empty(struct bheap* heap)
40{
41 return heap->head == NULL && heap->min == NULL;
42}
43
44/* insert (and reinitialize) a node into the heap */
45void bheap_insert(bheap_prio_t higher_prio,
46 struct bheap* heap,
47 struct bheap_node* node);
48
49/* merge addition into target */
50void bheap_union(bheap_prio_t higher_prio,
51 struct bheap* target,
52 struct bheap* addition);
53
54struct bheap_node* bheap_peek(bheap_prio_t higher_prio,
55 struct bheap* heap);
56
57struct bheap_node* bheap_take(bheap_prio_t higher_prio,
58 struct bheap* heap);
59
60void bheap_uncache_min(bheap_prio_t higher_prio, struct bheap* heap);
61int bheap_decrease(bheap_prio_t higher_prio, struct bheap_node* node);
62
63void bheap_delete(bheap_prio_t higher_prio,
64 struct bheap* heap,
65 struct bheap_node* node);
66
67/* allocate from memcache */
68struct bheap_node* bheap_node_alloc(int gfp_flags);
69void bheap_node_free(struct bheap_node* hn);
70
71/* allocate a heap node for value and insert into the heap */
72int bheap_add(bheap_prio_t higher_prio, struct bheap* heap,
73 void* value, int gfp_flags);
74
75void* bheap_take_del(bheap_prio_t higher_prio,
76 struct bheap* heap);
77#endif
diff --git a/include/litmus/binheap.h b/include/litmus/binheap.h
new file mode 100644
index 000000000000..1cf364701da8
--- /dev/null
+++ b/include/litmus/binheap.h
@@ -0,0 +1,205 @@
1#ifndef LITMUS_BINARY_HEAP_H
2#define LITMUS_BINARY_HEAP_H
3
4#include <linux/kernel.h>
5
6/**
7 * Simple binary heap with add, arbitrary delete, delete_root, and top
8 * operations.
9 *
10 * Style meant to conform with list.h.
11 *
12 * Motivation: Linux's prio_heap.h is of fixed size. Litmus's binomial
13 * heap may be overkill (and perhaps not general enough) for some applications.
14 *
15 * Note: In order to make node swaps fast, a node inserted with a data pointer
16 * may not always hold said data pointer. This is similar to the binomial heap
17 * implementation. This does make node deletion tricky since we have to
18 * (1) locate the node that holds the data pointer to delete, and (2) the
19 * node that was originally inserted with said data pointer. These have to be
20 * coalesced into a single node before removal (see usage of
21 * __binheap_safe_swap()). We have to track node references to accomplish this.
22 */
23
24struct binheap_node {
25 void *data;
26 struct binheap_node *parent;
27 struct binheap_node *left;
28 struct binheap_node *right;
29
30 /* pointer to binheap_node that holds *data for which this binheap_node
31 * was originally inserted. (*data "owns" this node)
32 */
33 struct binheap_node *ref;
34 struct binheap_node **ref_ptr;
35};
36
37/**
38 * Signature of compator function. Assumed 'less-than' (min-heap).
39 * Pass in 'greater-than' for max-heap.
40 *
41 * TODO: Consider macro-based implementation that allows comparator to be
42 * inlined (similar to Linux red/black tree) for greater efficiency.
43 */
44typedef int (*binheap_order_t)(struct binheap_node *a,
45 struct binheap_node *b);
46
47
48struct binheap {
49 struct binheap_node *root;
50
51 /* pointer to node to take next inserted child */
52 struct binheap_node *next;
53
54 /* pointer to last node in complete binary tree */
55 struct binheap_node *last;
56
57 /* comparator function pointer */
58 binheap_order_t compare;
59};
60
61
62/* Initialized heap nodes not in a heap have parent
63 * set to BINHEAP_POISON.
64 */
65#define BINHEAP_POISON ((void*)(0xdeadbeef))
66
67
68/**
69 * binheap_entry - get the struct for this heap node.
70 * Only valid when called upon heap nodes other than the root handle.
71 * @ptr: the heap node.
72 * @type: the type of struct pointed to by binheap_node::data.
73 * @member: unused.
74 */
75#define binheap_entry(ptr, type, member) \
76((type *)((ptr)->data))
77
78/**
79 * binheap_node_container - get the struct that contains this node.
80 * Only valid when called upon heap nodes other than the root handle.
81 * @ptr: the heap node.
82 * @type: the type of struct the node is embedded in.
83 * @member: the name of the binheap_struct within the (type) struct.
84 */
85#define binheap_node_container(ptr, type, member) \
86container_of((ptr), type, member)
87
88/**
89 * binheap_top_entry - get the struct for the node at the top of the heap.
90 * Only valid when called upon the heap handle node.
91 * @ptr: the special heap-handle node.
92 * @type: the type of the struct the head is embedded in.
93 * @member: the name of the binheap_struct within the (type) struct.
94 */
95#define binheap_top_entry(ptr, type, member) \
96binheap_entry((ptr)->root, type, member)
97
98/**
99 * binheap_delete_root - remove the root element from the heap.
100 * @handle: handle to the heap.
101 * @type: the type of the struct the head is embedded in.
102 * @member: the name of the binheap_struct within the (type) struct.
103 */
104#define binheap_delete_root(handle, type, member) \
105__binheap_delete_root((handle), &((type *)((handle)->root->data))->member)
106
107/**
108 * binheap_delete - remove an arbitrary element from the heap.
109 * @to_delete: pointer to node to be removed.
110 * @handle: handle to the heap.
111 */
112#define binheap_delete(to_delete, handle) \
113__binheap_delete((to_delete), (handle))
114
115/**
116 * binheap_add - insert an element to the heap
117 * new_node: node to add.
118 * @handle: handle to the heap.
119 * @type: the type of the struct the head is embedded in.
120 * @member: the name of the binheap_struct within the (type) struct.
121 */
122#define binheap_add(new_node, handle, type, member) \
123__binheap_add((new_node), (handle), container_of((new_node), type, member))
124
125/**
126 * binheap_decrease - re-eval the position of a node (based upon its
127 * original data pointer).
128 * @handle: handle to the heap.
129 * @orig_node: node that was associated with the data pointer
130 * (whose value has changed) when said pointer was
131 * added to the heap.
132 */
133#define binheap_decrease(orig_node, handle) \
134__binheap_decrease((orig_node), (handle))
135
136#define BINHEAP_NODE_INIT() { NULL, BINHEAP_POISON, NULL, NULL , NULL, NULL}
137
138#define BINHEAP_NODE(name) \
139 struct binheap_node name = BINHEAP_NODE_INIT()
140
141
142static inline void INIT_BINHEAP_NODE(struct binheap_node *n)
143{
144 n->data = NULL;
145 n->parent = BINHEAP_POISON;
146 n->left = NULL;
147 n->right = NULL;
148 n->ref = NULL;
149 n->ref_ptr = NULL;
150}
151
152static inline void INIT_BINHEAP_HANDLE(struct binheap *handle,
153 binheap_order_t compare)
154{
155 handle->root = NULL;
156 handle->next = NULL;
157 handle->last = NULL;
158 handle->compare = compare;
159}
160
161/* Returns true if binheap is empty. */
162static inline int binheap_empty(struct binheap *handle)
163{
164 return(handle->root == NULL);
165}
166
167/* Returns true if binheap node is in a heap. */
168static inline int binheap_is_in_heap(struct binheap_node *node)
169{
170 return (node->parent != BINHEAP_POISON);
171}
172
173/* Returns true if binheap node is in given heap. */
174int binheap_is_in_this_heap(struct binheap_node *node, struct binheap* heap);
175
176/* Add a node to a heap */
177void __binheap_add(struct binheap_node *new_node,
178 struct binheap *handle,
179 void *data);
180
181/**
182 * Removes the root node from the heap. The node is removed after coalescing
183 * the binheap_node with its original data pointer at the root of the tree.
184 *
185 * The 'last' node in the tree is then swapped up to the root and bubbled
186 * down.
187 */
188void __binheap_delete_root(struct binheap *handle,
189 struct binheap_node *container);
190
191/**
192 * Delete an arbitrary node. Bubble node to delete up to the root,
193 * and then delete to root.
194 */
195void __binheap_delete(struct binheap_node *node_to_delete,
196 struct binheap *handle);
197
198/**
199 * Bubble up a node whose pointer has decreased in value.
200 */
201void __binheap_decrease(struct binheap_node *orig_node,
202 struct binheap *handle);
203
204
205#endif
diff --git a/include/litmus/budget.h b/include/litmus/budget.h
new file mode 100644
index 000000000000..60eb814fc82b
--- /dev/null
+++ b/include/litmus/budget.h
@@ -0,0 +1,38 @@
1#ifndef _LITMUS_BUDGET_H_
2#define _LITMUS_BUDGET_H_
3
4/* Update the per-processor enforcement timer (arm/reproram/cancel) for
5 * the next task. */
6void update_enforcement_timer(struct task_struct* t);
7
8inline static int budget_exhausted(struct task_struct* t)
9{
10 return get_exec_time(t) >= get_exec_cost(t);
11}
12
13inline static lt_t budget_remaining(struct task_struct* t)
14{
15 if (!budget_exhausted(t))
16 return get_exec_cost(t) - get_exec_time(t);
17 else
18 /* avoid overflow */
19 return 0;
20}
21
22#define budget_enforced(t) (tsk_rt(t)->task_params.budget_policy != NO_ENFORCEMENT)
23
24#define budget_precisely_enforced(t) (tsk_rt(t)->task_params.budget_policy \
25 == PRECISE_ENFORCEMENT)
26
27static inline int requeue_preempted_job(struct task_struct* t)
28{
29 /* Add task to ready queue only if not subject to budget enforcement or
30 * if the job has budget remaining. t may be NULL.
31 */
32 return t && !is_completed(t) &&
33 (!budget_exhausted(t) || !budget_enforced(t));
34}
35
36void litmus_current_budget(lt_t *used_so_far, lt_t *remaining);
37
38#endif
diff --git a/include/litmus/ceiling.h b/include/litmus/ceiling.h
new file mode 100644
index 000000000000..f3d3889315f7
--- /dev/null
+++ b/include/litmus/ceiling.h
@@ -0,0 +1,36 @@
1#ifndef _LITMUS_CEILING_H_
2#define _LITMUS_CEILING_H_
3
4#ifdef CONFIG_LITMUS_LOCKING
5
6void __srp_ceiling_block(struct task_struct *cur);
7
8DECLARE_PER_CPU(int, srp_objects_in_use);
9
10/* assumes preemptions off */
11void srp_ceiling_block(void)
12{
13 struct task_struct *tsk = current;
14
15 /* Only applies to real-time tasks. */
16 if (!is_realtime(tsk))
17 return;
18
19 /* Bail out early if there aren't any SRP resources around. */
20 if (likely(!raw_cpu_read(srp_objects_in_use)))
21 return;
22
23 /* Avoid recursive ceiling blocking. */
24 if (unlikely(tsk->rt_param.srp_non_recurse))
25 return;
26
27 /* must take slow path */
28 __srp_ceiling_block(tsk);
29}
30
31#else
32#define srp_ceiling_block() /* nothing */
33#endif
34
35
36#endif \ No newline at end of file
diff --git a/include/litmus/clustered.h b/include/litmus/clustered.h
new file mode 100644
index 000000000000..fc7f0f87966e
--- /dev/null
+++ b/include/litmus/clustered.h
@@ -0,0 +1,46 @@
1#ifndef CLUSTERED_H
2#define CLUSTERED_H
3
4/* Which cache level should be used to group CPUs into clusters?
5 * GLOBAL_CLUSTER means that all CPUs form a single cluster (just like under
6 * global scheduling).
7 */
8enum cache_level {
9 GLOBAL_CLUSTER = 0,
10 L1_CLUSTER = 1,
11 L2_CLUSTER = 2,
12 L3_CLUSTER = 3
13};
14
15int parse_cache_level(const char *str, enum cache_level *level);
16const char* cache_level_name(enum cache_level level);
17
18/* expose a cache level in a /proc dir */
19struct proc_dir_entry* create_cluster_file(struct proc_dir_entry* parent,
20 enum cache_level* level);
21
22
23
24struct scheduling_cluster {
25 unsigned int id;
26 /* list of CPUs that are part of this cluster */
27 struct list_head cpus;
28};
29
30struct cluster_cpu {
31 unsigned int id; /* which CPU is this? */
32 struct list_head cluster_list; /* List of the CPUs in this cluster. */
33 struct scheduling_cluster* cluster; /* The cluster that this CPU belongs to. */
34};
35
36int get_cluster_size(enum cache_level level);
37
38int assign_cpus_to_clusters(enum cache_level level,
39 struct scheduling_cluster* clusters[],
40 unsigned int num_clusters,
41 struct cluster_cpu* cpus[],
42 unsigned int num_cpus);
43
44int get_shared_cpu_map(cpumask_var_t mask, unsigned int cpu, unsigned int index);
45
46#endif
diff --git a/include/litmus/ctrlpage.h b/include/litmus/ctrlpage.h
new file mode 100644
index 000000000000..f7b03e1aedd6
--- /dev/null
+++ b/include/litmus/ctrlpage.h
@@ -0,0 +1,105 @@
1#ifndef _LITMUS_CTRLPAGE_H_
2#define _LITMUS_CTRLPAGE_H_
3
4#include <litmus/rt_param.h>
5
6union np_flag {
7 uint32_t raw;
8 struct {
9 /* Is the task currently in a non-preemptive section? */
10 uint32_t flag:31;
11 /* Should the task call into the scheduler? */
12 uint32_t preempt:1;
13 } np;
14};
15
16/* The definition of the data that is shared between the kernel and real-time
17 * tasks via a shared page (see litmus/ctrldev.c).
18 *
19 * WARNING: User space can write to this, so don't trust
20 * the correctness of the fields!
21 *
22 * This servees two purposes: to enable efficient signaling
23 * of non-preemptive sections (user->kernel) and
24 * delayed preemptions (kernel->user), and to export
25 * some real-time relevant statistics such as preemption and
26 * migration data to user space. We can't use a device to export
27 * statistics because we want to avoid system call overhead when
28 * determining preemption/migration overheads).
29 */
30struct control_page {
31 /* This flag is used by userspace to communicate non-preempive
32 * sections. */
33 volatile __attribute__ ((aligned (8))) union np_flag sched;
34
35 /* Incremented by the kernel each time an IRQ is handled. */
36 volatile __attribute__ ((aligned (8))) uint64_t irq_count;
37
38 /* Locking overhead tracing: userspace records here the time stamp
39 * and IRQ counter prior to starting the system call. */
40 uint64_t ts_syscall_start; /* Feather-Trace cycles */
41 uint64_t irq_syscall_start; /* Snapshot of irq_count when the syscall
42 * started. */
43
44 lt_t deadline; /* Deadline for the currently executing job */
45 lt_t release; /* Release time of current job */
46 uint64_t job_index; /* Job sequence number of current job */
47
48 /* to be extended */
49};
50
51/* Expected offsets within the control page. */
52
53#define LITMUS_CP_OFFSET_SCHED 0
54#define LITMUS_CP_OFFSET_IRQ_COUNT 8
55#define LITMUS_CP_OFFSET_TS_SC_START 16
56#define LITMUS_CP_OFFSET_IRQ_SC_START 24
57#define LITMUS_CP_OFFSET_DEADLINE 32
58#define LITMUS_CP_OFFSET_RELEASE 40
59#define LITMUS_CP_OFFSET_JOB_INDEX 48
60
61/* System call emulation via ioctl() */
62
63typedef enum {
64 LRT_null_call = 2006,
65 LRT_set_rt_task_param,
66 LRT_get_rt_task_param,
67 LRT_reservation_create,
68 LRT_complete_job,
69 LRT_od_open,
70 LRT_od_close,
71 LRT_litmus_lock,
72 LRT_litmus_unlock,
73 LRT_wait_for_job_release,
74 LRT_wait_for_ts_release,
75 LRT_release_ts,
76 LRT_get_current_budget,
77} litmus_syscall_id_t;
78
79union litmus_syscall_args {
80 struct {
81 pid_t pid;
82 struct rt_task __user *param;
83 } get_set_task_param;
84
85 struct {
86 uint32_t type;
87 void __user *config;
88 } reservation_create;
89
90 struct {
91 uint32_t fd;
92 uint32_t obj_type;
93 uint32_t obj_id;
94 void __user *config;
95 } od_open;
96
97 struct {
98 lt_t __user *expended;
99 lt_t __user *remaining;
100 } get_current_budget;
101};
102
103
104#endif
105
diff --git a/include/litmus/debug_trace.h b/include/litmus/debug_trace.h
index 1266ac6a760c..a760631d4fca 100644
--- a/include/litmus/debug_trace.h
+++ b/include/litmus/debug_trace.h
@@ -37,4 +37,9 @@ extern atomic_t __log_seq_no;
37#define TRACE_CUR(fmt, args...) \ 37#define TRACE_CUR(fmt, args...) \
38 TRACE_TASK(current, fmt, ## args) 38 TRACE_TASK(current, fmt, ## args)
39 39
40#define TRACE_WARN_ON(cond) \
41 if (unlikely(cond)) \
42 TRACE("WARNING: '%s' [%s@%s:%d]\n", \
43 #cond, __FUNCTION__, __FILE__, __LINE__)
44
40#endif 45#endif
diff --git a/include/litmus/edf_common.h b/include/litmus/edf_common.h
new file mode 100644
index 000000000000..bbaf22ea7f12
--- /dev/null
+++ b/include/litmus/edf_common.h
@@ -0,0 +1,25 @@
1/*
2 * EDF common data structures and utility functions shared by all EDF
3 * based scheduler plugins
4 */
5
6/* CLEANUP: Add comments and make it less messy.
7 *
8 */
9
10#ifndef __UNC_EDF_COMMON_H__
11#define __UNC_EDF_COMMON_H__
12
13#include <litmus/rt_domain.h>
14
15void edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
16 release_jobs_t release);
17
18int edf_higher_prio(struct task_struct* first,
19 struct task_struct* second);
20
21int edf_ready_order(struct bheap_node* a, struct bheap_node* b);
22
23int edf_preemption_needed(rt_domain_t* rt, struct task_struct *t);
24
25#endif
diff --git a/include/litmus/fdso.h b/include/litmus/fdso.h
new file mode 100644
index 000000000000..fd9b30dbfb34
--- /dev/null
+++ b/include/litmus/fdso.h
@@ -0,0 +1,78 @@
1/* fdso.h - file descriptor attached shared objects
2 *
3 * (c) 2007 B. Brandenburg, LITMUS^RT project
4 */
5
6#ifndef _LINUX_FDSO_H_
7#define _LINUX_FDSO_H_
8
9#include <linux/list.h>
10#include <asm/atomic.h>
11
12#include <linux/fs.h>
13#include <linux/slab.h>
14
15#define MAX_OBJECT_DESCRIPTORS 85
16
17typedef enum {
18 MIN_OBJ_TYPE = 0,
19
20 FMLP_SEM = 0,
21 SRP_SEM = 1,
22
23 MPCP_SEM = 2,
24 MPCP_VS_SEM = 3,
25 DPCP_SEM = 4,
26 PCP_SEM = 5,
27
28 DFLP_SEM = 6,
29
30 MAX_OBJ_TYPE = 6
31} obj_type_t;
32
33struct inode_obj_id {
34 struct list_head list;
35 atomic_t count;
36 struct inode* inode;
37
38 obj_type_t type;
39 void* obj;
40 unsigned int id;
41};
42
43struct fdso_ops;
44
45struct od_table_entry {
46 unsigned int used;
47
48 struct inode_obj_id* obj;
49 const struct fdso_ops* class;
50};
51
52struct fdso_ops {
53 int (*create)(void** obj_ref, obj_type_t type, void* __user);
54 void (*destroy)(obj_type_t type, void*);
55 int (*open) (struct od_table_entry*, void* __user);
56 int (*close) (struct od_table_entry*);
57};
58
59/* translate a userspace supplied od into the raw table entry
60 * returns NULL if od is invalid
61 */
62struct od_table_entry* get_entry_for_od(int od);
63
64/* translate a userspace supplied od into the associated object
65 * returns NULL if od is invalid
66 */
67static inline void* od_lookup(int od, obj_type_t type)
68{
69 struct od_table_entry* e = get_entry_for_od(od);
70 return e && e->obj->type == type ? e->obj->obj : NULL;
71}
72
73#define lookup_fmlp_sem(od)((struct pi_semaphore*) od_lookup(od, FMLP_SEM))
74#define lookup_srp_sem(od) ((struct srp_semaphore*) od_lookup(od, SRP_SEM))
75#define lookup_ics(od) ((struct ics*) od_lookup(od, ICS_ID))
76
77
78#endif
diff --git a/include/litmus/fp_common.h b/include/litmus/fp_common.h
new file mode 100644
index 000000000000..71c0d0142fc4
--- /dev/null
+++ b/include/litmus/fp_common.h
@@ -0,0 +1,183 @@
1/* Fixed-priority scheduler support.
2 */
3
4#ifndef __FP_COMMON_H__
5#define __FP_COMMON_H__
6
7#include <litmus/rt_domain.h>
8
9#include <asm/bitops.h>
10
11
12void fp_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
13 release_jobs_t release);
14
15int fp_higher_prio(struct task_struct* first,
16 struct task_struct* second);
17
18int fp_ready_order(struct bheap_node* a, struct bheap_node* b);
19
20#define FP_PRIO_BIT_WORDS (LITMUS_MAX_PRIORITY / BITS_PER_LONG)
21
22#if (LITMUS_MAX_PRIORITY % BITS_PER_LONG)
23#error LITMUS_MAX_PRIORITY must be a multiple of BITS_PER_LONG
24#endif
25
26/* bitmask-inexed priority queue */
27struct fp_prio_queue {
28 unsigned long bitmask[FP_PRIO_BIT_WORDS];
29 struct bheap queue[LITMUS_MAX_PRIORITY];
30};
31
32void fp_prio_queue_init(struct fp_prio_queue* q);
33
34static inline void fpq_set(struct fp_prio_queue* q, unsigned int index)
35{
36 unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
37 __set_bit(index % BITS_PER_LONG, word);
38}
39
40static inline void fpq_clear(struct fp_prio_queue* q, unsigned int index)
41{
42 unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
43 __clear_bit(index % BITS_PER_LONG, word);
44}
45
46static inline unsigned int fpq_find(struct fp_prio_queue* q)
47{
48 int i;
49
50 /* loop optimizer should unroll this */
51 for (i = 0; i < FP_PRIO_BIT_WORDS; i++)
52 if (q->bitmask[i])
53 return __ffs(q->bitmask[i]) + i * BITS_PER_LONG;
54
55 return LITMUS_MAX_PRIORITY; /* nothing found */
56}
57
58static inline void fp_prio_add(struct fp_prio_queue* q, struct task_struct* t, unsigned int index)
59{
60 BUG_ON(index >= LITMUS_MAX_PRIORITY);
61 BUG_ON(bheap_node_in_heap(tsk_rt(t)->heap_node));
62
63 fpq_set(q, index);
64 bheap_insert(fp_ready_order, &q->queue[index], tsk_rt(t)->heap_node);
65}
66
67static inline void fp_prio_remove(struct fp_prio_queue* q, struct task_struct* t, unsigned int index)
68{
69 BUG_ON(!is_queued(t));
70
71 bheap_delete(fp_ready_order, &q->queue[index], tsk_rt(t)->heap_node);
72 if (likely(bheap_empty(&q->queue[index])))
73 fpq_clear(q, index);
74}
75
76static inline struct task_struct* fp_prio_peek(struct fp_prio_queue* q)
77{
78 unsigned int idx = fpq_find(q);
79 struct bheap_node* hn;
80
81 if (idx < LITMUS_MAX_PRIORITY) {
82 hn = bheap_peek(fp_ready_order, &q->queue[idx]);
83 return bheap2task(hn);
84 } else
85 return NULL;
86}
87
88static inline struct task_struct* fp_prio_take(struct fp_prio_queue* q)
89{
90 unsigned int idx = fpq_find(q);
91 struct bheap_node* hn;
92
93 if (idx < LITMUS_MAX_PRIORITY) {
94 hn = bheap_take(fp_ready_order, &q->queue[idx]);
95 if (likely(bheap_empty(&q->queue[idx])))
96 fpq_clear(q, idx);
97 return bheap2task(hn);
98 } else
99 return NULL;
100}
101
102int fp_preemption_needed(struct fp_prio_queue* q, struct task_struct *t);
103
104
105/* ******* list-based version ******** */
106
107/* bitmask-inexed priority queue */
108struct fp_ready_list {
109 unsigned long bitmask[FP_PRIO_BIT_WORDS];
110 struct list_head queue[LITMUS_MAX_PRIORITY];
111};
112
113void fp_ready_list_init(struct fp_ready_list* q);
114
115static inline void fp_rl_set(struct fp_ready_list* q, unsigned int index)
116{
117 unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
118 __set_bit(index % BITS_PER_LONG, word);
119}
120
121static inline void fp_rl_clear(struct fp_ready_list* q, unsigned int index)
122{
123 unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
124 __clear_bit(index % BITS_PER_LONG, word);
125}
126
127static inline unsigned int fp_rl_find(struct fp_ready_list* q)
128{
129 int i;
130
131 /* loop optimizer should unroll this */
132 for (i = 0; i < FP_PRIO_BIT_WORDS; i++)
133 if (q->bitmask[i])
134 return __ffs(q->bitmask[i]) + i * BITS_PER_LONG;
135
136 return LITMUS_MAX_PRIORITY; /* nothing found */
137}
138
139static inline void fp_ready_list_add(
140 struct fp_ready_list* q, struct list_head* lh, unsigned int index)
141{
142 BUG_ON(index >= LITMUS_MAX_PRIORITY);
143 BUG_ON(in_list(lh));
144
145 fp_rl_set(q, index);
146 list_add_tail(lh, &q->queue[index]);
147}
148
149static inline void fp_ready_list_remove(
150 struct fp_ready_list* q, struct list_head* lh, unsigned int index)
151{
152 BUG_ON(!in_list(lh));
153
154 list_del(lh);
155 if (likely(list_empty(q->queue + index)))
156 fp_rl_clear(q, index);
157}
158
159static inline struct list_head* fp_ready_list_peek(struct fp_ready_list* q)
160{
161 unsigned int idx = fp_rl_find(q);
162
163 if (idx < LITMUS_MAX_PRIORITY) {
164 return q->queue[idx].next;
165 } else
166 return NULL;
167}
168
169static inline struct list_head* fp_ready_list_take(struct fp_ready_list* q)
170{
171 unsigned int idx = fp_rl_find(q);
172 struct list_head* lh;
173
174 if (idx < LITMUS_MAX_PRIORITY) {
175 lh = q->queue[idx].next;
176 fp_ready_list_remove(q, lh, idx);
177 return lh;
178 } else
179 return NULL;
180}
181
182
183#endif
diff --git a/include/litmus/fpmath.h b/include/litmus/fpmath.h
new file mode 100644
index 000000000000..642de98542c8
--- /dev/null
+++ b/include/litmus/fpmath.h
@@ -0,0 +1,147 @@
1#ifndef __FP_MATH_H__
2#define __FP_MATH_H__
3
4#include <linux/math64.h>
5
6#ifndef __KERNEL__
7#include <stdint.h>
8#define abs(x) (((x) < 0) ? -(x) : x)
9#endif
10
11// Use 64-bit because we want to track things at the nanosecond scale.
12// This can lead to very large numbers.
13typedef int64_t fpbuf_t;
14typedef struct
15{
16 fpbuf_t val;
17} fp_t;
18
19#define FP_SHIFT 10
20#define ROUND_BIT (FP_SHIFT - 1)
21
22#define _fp(x) ((fp_t) {x})
23
24#ifdef __KERNEL__
25static const fp_t LITMUS_FP_ZERO = {.val = 0};
26static const fp_t LITMUS_FP_ONE = {.val = (1 << FP_SHIFT)};
27#endif
28
29static inline fp_t FP(fpbuf_t x)
30{
31 return _fp(((fpbuf_t) x) << FP_SHIFT);
32}
33
34/* divide two integers to obtain a fixed point value */
35static inline fp_t _frac(fpbuf_t a, fpbuf_t b)
36{
37 return _fp(div64_s64(FP(a).val, (b)));
38}
39
40static inline fpbuf_t _point(fp_t x)
41{
42 return (x.val % (1 << FP_SHIFT));
43
44}
45
46#define fp2str(x) x.val
47/*(x.val >> FP_SHIFT), (x.val % (1 << FP_SHIFT)) */
48#define _FP_ "%ld/1024"
49
50static inline fpbuf_t _floor(fp_t x)
51{
52 return x.val >> FP_SHIFT;
53}
54
55/* FIXME: negative rounding */
56static inline fpbuf_t _round(fp_t x)
57{
58 return _floor(x) + ((x.val >> ROUND_BIT) & 1);
59}
60
61/* multiply two fixed point values */
62static inline fp_t _mul(fp_t a, fp_t b)
63{
64 return _fp((a.val * b.val) >> FP_SHIFT);
65}
66
67static inline fp_t _div(fp_t a, fp_t b)
68{
69#if !defined(__KERNEL__) && !defined(unlikely)
70#define unlikely(x) (x)
71#define DO_UNDEF_UNLIKELY
72#endif
73 /* try not to overflow */
74 if (unlikely( a.val > (2l << ((sizeof(fpbuf_t)*8) - FP_SHIFT)) ))
75 return _fp((a.val / b.val) << FP_SHIFT);
76 else
77 return _fp((a.val << FP_SHIFT) / b.val);
78#ifdef DO_UNDEF_UNLIKELY
79#undef unlikely
80#undef DO_UNDEF_UNLIKELY
81#endif
82}
83
84static inline fp_t _add(fp_t a, fp_t b)
85{
86 return _fp(a.val + b.val);
87}
88
89static inline fp_t _sub(fp_t a, fp_t b)
90{
91 return _fp(a.val - b.val);
92}
93
94static inline fp_t _neg(fp_t x)
95{
96 return _fp(-x.val);
97}
98
99static inline fp_t _abs(fp_t x)
100{
101 return _fp(abs(x.val));
102}
103
104/* works the same as casting float/double to integer */
105static inline fpbuf_t _fp_to_integer(fp_t x)
106{
107 return _floor(_abs(x)) * ((x.val > 0) ? 1 : -1);
108}
109
110static inline fp_t _integer_to_fp(fpbuf_t x)
111{
112 return _frac(x,1);
113}
114
115static inline int _leq(fp_t a, fp_t b)
116{
117 return a.val <= b.val;
118}
119
120static inline int _geq(fp_t a, fp_t b)
121{
122 return a.val >= b.val;
123}
124
125static inline int _lt(fp_t a, fp_t b)
126{
127 return a.val < b.val;
128}
129
130static inline int _gt(fp_t a, fp_t b)
131{
132 return a.val > b.val;
133}
134
135static inline int _eq(fp_t a, fp_t b)
136{
137 return a.val == b.val;
138}
139
140static inline fp_t _max(fp_t a, fp_t b)
141{
142 if (a.val < b.val)
143 return b;
144 else
145 return a;
146}
147#endif
diff --git a/include/litmus/jobs.h b/include/litmus/jobs.h
new file mode 100644
index 000000000000..7033393148df
--- /dev/null
+++ b/include/litmus/jobs.h
@@ -0,0 +1,13 @@
1#ifndef __LITMUS_JOBS_H__
2#define __LITMUS_JOBS_H__
3
4void prepare_for_next_period(struct task_struct *t);
5void release_at(struct task_struct *t, lt_t start);
6
7void inferred_sporadic_job_release_at(struct task_struct *t, lt_t when);
8
9long default_wait_for_release_at(lt_t release_time);
10long complete_job(void);
11long complete_job_oneshot(void);
12
13#endif
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index c87863c9b231..f550367ddd4b 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -6,7 +6,50 @@
6#ifndef _LINUX_LITMUS_H_ 6#ifndef _LINUX_LITMUS_H_
7#define _LINUX_LITMUS_H_ 7#define _LINUX_LITMUS_H_
8 8
9#include <litmus/ctrlpage.h>
10
11#ifdef CONFIG_RELEASE_MASTER
12extern atomic_t release_master_cpu;
13#endif
14
15/* in_list - is a given list_head queued on some list?
16 */
17static inline int in_list(struct list_head* list)
18{
19 return !( /* case 1: deleted */
20 (list->next == LIST_POISON1 &&
21 list->prev == LIST_POISON2)
22 ||
23 /* case 2: initialized */
24 (list->next == list &&
25 list->prev == list)
26 );
27}
28
29struct task_struct* __waitqueue_remove_first(wait_queue_head_t *wq);
30
31#define NO_CPU 0xffffffff
32
33void litmus_fork(struct task_struct *tsk);
34void litmus_exec(void);
35/* clean up real-time state of a task */
36void litmus_clear_state(struct task_struct *dead_tsk);
37void exit_litmus(struct task_struct *dead_tsk);
38
39/* Prevent the plugin from being switched-out from underneath a code
40 * path. Might sleep, so may be called only from non-atomic context. */
41void litmus_plugin_switch_disable(void);
42void litmus_plugin_switch_enable(void);
43
44long litmus_admit_task(struct task_struct *tsk);
45void litmus_exit_task(struct task_struct *tsk);
46void litmus_dealloc(struct task_struct *tsk);
47void litmus_do_exit(struct task_struct *tsk);
48int litmus_be_migrate_to(int cpu);
49
9#define is_realtime(t) ((t)->policy == SCHED_LITMUS) 50#define is_realtime(t) ((t)->policy == SCHED_LITMUS)
51#define rt_transition_pending(t) \
52 ((t)->rt_param.transition_pending)
10 53
11#define tsk_rt(t) (&(t)->rt_param) 54#define tsk_rt(t) (&(t)->rt_param)
12 55
@@ -28,6 +71,7 @@
28#define get_partition(t) (tsk_rt(t)->task_params.cpu) 71#define get_partition(t) (tsk_rt(t)->task_params.cpu)
29#define get_priority(t) (tsk_rt(t)->task_params.priority) 72#define get_priority(t) (tsk_rt(t)->task_params.priority)
30#define get_class(t) (tsk_rt(t)->task_params.cls) 73#define get_class(t) (tsk_rt(t)->task_params.cls)
74#define get_release_policy(t) (tsk_rt(t)->task_params.release_policy)
31 75
32/* job_param macros */ 76/* job_param macros */
33#define get_exec_time(t) (tsk_rt(t)->job_params.exec_time) 77#define get_exec_time(t) (tsk_rt(t)->job_params.exec_time)
@@ -35,6 +79,15 @@
35#define get_release(t) (tsk_rt(t)->job_params.release) 79#define get_release(t) (tsk_rt(t)->job_params.release)
36#define get_lateness(t) (tsk_rt(t)->job_params.lateness) 80#define get_lateness(t) (tsk_rt(t)->job_params.lateness)
37 81
82/* release policy macros */
83#define is_periodic(t) (get_release_policy(t) == TASK_PERIODIC)
84#define is_sporadic(t) (get_release_policy(t) == TASK_SPORADIC)
85#ifdef CONFIG_ALLOW_EARLY_RELEASE
86#define is_early_releasing(t) (get_release_policy(t) == TASK_EARLY)
87#else
88#define is_early_releasing(t) (0)
89#endif
90
38#define is_hrt(t) \ 91#define is_hrt(t) \
39 (tsk_rt(t)->task_params.cls == RT_CLASS_HARD) 92 (tsk_rt(t)->task_params.cls == RT_CLASS_HARD)
40#define is_srt(t) \ 93#define is_srt(t) \
@@ -48,6 +101,67 @@ static inline lt_t litmus_clock(void)
48 return ktime_to_ns(ktime_get()); 101 return ktime_to_ns(ktime_get());
49} 102}
50 103
104/* A macro to convert from nanoseconds to ktime_t. */
105#define ns_to_ktime(t) ktime_add_ns(ktime_set(0, 0), t)
106
107#define is_released(t, now) \
108 (lt_before_eq(get_release(t), now))
109#define is_tardy(t, now) \
110 (lt_before_eq(tsk_rt(t)->job_params.deadline, now))
111
112/* real-time comparison macros */
113#define earlier_deadline(a, b) (lt_before(\
114 (a)->rt_param.job_params.deadline,\
115 (b)->rt_param.job_params.deadline))
116#define earlier_release(a, b) (lt_before(\
117 (a)->rt_param.job_params.release,\
118 (b)->rt_param.job_params.release))
119
120void preempt_if_preemptable(struct task_struct* t, int on_cpu);
121
122#define bheap2task(hn) ((struct task_struct*) hn->value)
123
124static inline int is_present(struct task_struct* t)
125{
126 return t && tsk_rt(t)->present;
127}
128
129static inline int is_completed(struct task_struct* t)
130{
131 return t && tsk_rt(t)->completed;
132}
133
134
135/* Used to convert ns-specified execution costs and periods into
136 * integral quanta equivalents.
137 */
138#define LITMUS_QUANTUM_LENGTH_NS (CONFIG_LITMUS_QUANTUM_LENGTH_US * 1000ULL)
139
140/* make the unit explicit */
141typedef unsigned long quanta_t;
142
143enum round {
144 FLOOR,
145 CEIL
146};
147
148static inline quanta_t time2quanta(lt_t time, enum round round)
149{
150 s64 quantum_length = LITMUS_QUANTUM_LENGTH_NS;
151
152 if (do_div(time, quantum_length) && round == CEIL)
153 time++;
154 return (quanta_t) time;
155}
156
157static inline lt_t quanta2time(quanta_t quanta)
158{
159 return quanta * LITMUS_QUANTUM_LENGTH_NS;
160}
161
162/* By how much is cpu staggered behind CPU 0? */
163u64 cpu_stagger_offset(int cpu);
164
51static inline struct control_page* get_control_page(struct task_struct *t) 165static inline struct control_page* get_control_page(struct task_struct *t)
52{ 166{
53 return tsk_rt(t)->ctrl_page; 167 return tsk_rt(t)->ctrl_page;
@@ -58,4 +172,53 @@ static inline int has_control_page(struct task_struct* t)
58 return tsk_rt(t)->ctrl_page != NULL; 172 return tsk_rt(t)->ctrl_page != NULL;
59} 173}
60 174
175
176#ifdef CONFIG_SCHED_OVERHEAD_TRACE
177
178#define TS_SYSCALL_IN_START \
179 if (has_control_page(current)) { \
180 __TS_SYSCALL_IN_START(&get_control_page(current)->ts_syscall_start); \
181 }
182
183#define TS_SYSCALL_IN_END \
184 if (has_control_page(current)) { \
185 unsigned long flags; \
186 uint64_t irqs; \
187 local_irq_save(flags); \
188 irqs = get_control_page(current)->irq_count - \
189 get_control_page(current)->irq_syscall_start; \
190 __TS_SYSCALL_IN_END(&irqs); \
191 local_irq_restore(flags); \
192 }
193
194#else
195
196#define TS_SYSCALL_IN_START
197#define TS_SYSCALL_IN_END
198
199#endif
200
201#ifdef CONFIG_SMP
202
203/*
204 * struct hrtimer_start_on_info - timer info on remote cpu
205 * @timer: timer to be triggered on remote cpu
206 * @time: time event
207 * @mode: timer mode
208 * @csd: smp_call_function parameter to call hrtimer_pull on remote cpu
209 */
210struct hrtimer_start_on_info {
211 struct hrtimer *timer;
212 ktime_t time;
213 enum hrtimer_mode mode;
214 struct call_single_data csd;
215};
216
217void hrtimer_pull(void *csd_info);
218extern void hrtimer_start_on(int cpu, struct hrtimer_start_on_info *info,
219 struct hrtimer *timer, ktime_t time,
220 const enum hrtimer_mode mode);
221
222#endif
223
61#endif 224#endif
diff --git a/include/litmus/litmus_proc.h b/include/litmus/litmus_proc.h
new file mode 100644
index 000000000000..a5db24c03ec0
--- /dev/null
+++ b/include/litmus/litmus_proc.h
@@ -0,0 +1,63 @@
1#include <litmus/sched_plugin.h>
2#include <linux/proc_fs.h>
3
4int __init init_litmus_proc(void);
5void exit_litmus_proc(void);
6
7struct cd_mapping
8{
9 int id;
10 cpumask_var_t mask;
11 struct proc_dir_entry *proc_file;
12};
13
14struct domain_proc_info
15{
16 int num_cpus;
17 int num_domains;
18
19 struct cd_mapping *cpu_to_domains;
20 struct cd_mapping *domain_to_cpus;
21};
22
23/*
24 * On success, returns 0 and sets the pointer to the location of the new
25 * proc dir entry, otherwise returns an error code and sets pde to NULL.
26 */
27long make_plugin_proc_dir(struct sched_plugin* plugin,
28 struct proc_dir_entry** pde);
29
30/*
31 * Plugins should deallocate all child proc directory entries before
32 * calling this, to avoid memory leaks.
33 */
34void remove_plugin_proc_dir(struct sched_plugin* plugin);
35
36/*
37 * Setup the CPU <-> sched domain mappings in proc
38 */
39long activate_domain_proc(struct domain_proc_info* map);
40
41/*
42 * Remove the CPU <-> sched domain mappings from proc
43 */
44long deactivate_domain_proc(void);
45
46/*
47 * Alloc memory for the mapping
48 * Note: Does not set up proc files. Use make_sched_domain_maps for that.
49 */
50long init_domain_proc_info(struct domain_proc_info* map,
51 int num_cpus, int num_domains);
52
53/*
54 * Free memory of the mapping
55 * Note: Does not clean up proc files. Use deactivate_domain_proc for that.
56 */
57void destroy_domain_proc_info(struct domain_proc_info* map);
58
59/* Copy at most size-1 bytes from ubuf into kbuf, null-terminate buf, and
60 * remove a '\n' if present. Returns the number of bytes that were read or
61 * -EFAULT. */
62int copy_and_chomp(char *kbuf, unsigned long ksize,
63 __user const char* ubuf, unsigned long ulength);
diff --git a/include/litmus/locking.h b/include/litmus/locking.h
new file mode 100644
index 000000000000..4d7b870cb443
--- /dev/null
+++ b/include/litmus/locking.h
@@ -0,0 +1,28 @@
1#ifndef LITMUS_LOCKING_H
2#define LITMUS_LOCKING_H
3
4struct litmus_lock_ops;
5
6/* Generic base struct for LITMUS^RT userspace semaphores.
7 * This structure should be embedded in protocol-specific semaphores.
8 */
9struct litmus_lock {
10 struct litmus_lock_ops *ops;
11 int type;
12};
13
14struct litmus_lock_ops {
15 /* Current task tries to obtain / drop a reference to a lock.
16 * Optional methods, allowed by default. */
17 int (*open)(struct litmus_lock*, void* __user);
18 int (*close)(struct litmus_lock*);
19
20 /* Current tries to lock/unlock this lock (mandatory methods). */
21 int (*lock)(struct litmus_lock*);
22 int (*unlock)(struct litmus_lock*);
23
24 /* The lock is no longer being referenced (mandatory method). */
25 void (*deallocate)(struct litmus_lock*);
26};
27
28#endif
diff --git a/include/litmus/np.h b/include/litmus/np.h
new file mode 100644
index 000000000000..dbe2b695f74a
--- /dev/null
+++ b/include/litmus/np.h
@@ -0,0 +1,121 @@
1#ifndef _LITMUS_NP_H_
2#define _LITMUS_NP_H_
3
4/* Definitions related to non-preemptive sections signaled via the control
5 * page
6 */
7
8#ifdef CONFIG_NP_SECTION
9
10static inline int is_kernel_np(struct task_struct *t)
11{
12 return tsk_rt(t)->kernel_np;
13}
14
15static inline int is_user_np(struct task_struct *t)
16{
17 return tsk_rt(t)->ctrl_page ? tsk_rt(t)->ctrl_page->sched.np.flag : 0;
18}
19
20static inline void request_exit_np(struct task_struct *t)
21{
22 if (is_user_np(t)) {
23 /* Set the flag that tells user space to call
24 * into the kernel at the end of a critical section. */
25 if (likely(tsk_rt(t)->ctrl_page)) {
26 TRACE_TASK(t, "setting delayed_preemption flag\n");
27 tsk_rt(t)->ctrl_page->sched.np.preempt = 1;
28 }
29 }
30}
31
32static inline void make_np(struct task_struct *t)
33{
34 tsk_rt(t)->kernel_np++;
35}
36
37/* Caller should check if preemption is necessary when
38 * the function return 0.
39 */
40static inline int take_np(struct task_struct *t)
41{
42 return --tsk_rt(t)->kernel_np;
43}
44
45/* returns 0 if remote CPU needs an IPI to preempt, 1 if no IPI is required */
46static inline int request_exit_np_atomic(struct task_struct *t)
47{
48 union np_flag old, new;
49
50 if (tsk_rt(t)->ctrl_page) {
51 old.raw = tsk_rt(t)->ctrl_page->sched.raw;
52 if (old.np.flag == 0) {
53 /* no longer non-preemptive */
54 return 0;
55 } else if (old.np.preempt) {
56 /* already set, nothing for us to do */
57 return 1;
58 } else {
59 /* non preemptive and flag not set */
60 new.raw = old.raw;
61 new.np.preempt = 1;
62 /* if we get old back, then we atomically set the flag */
63 return cmpxchg(&tsk_rt(t)->ctrl_page->sched.raw, old.raw, new.raw) == old.raw;
64 /* If we raced with a concurrent change, then so be
65 * it. Deliver it by IPI. We don't want an unbounded
66 * retry loop here since tasks might exploit that to
67 * keep the kernel busy indefinitely. */
68 }
69 } else
70 return 0;
71}
72
73#else
74
75static inline int is_kernel_np(struct task_struct* t)
76{
77 return 0;
78}
79
80static inline int is_user_np(struct task_struct* t)
81{
82 return 0;
83}
84
85static inline void request_exit_np(struct task_struct *t)
86{
87 /* request_exit_np() shouldn't be called if !CONFIG_NP_SECTION */
88 BUG();
89}
90
91static inline int request_exit_np_atomic(struct task_struct *t)
92{
93 return 0;
94}
95
96#endif
97
98static inline void clear_exit_np(struct task_struct *t)
99{
100 if (likely(tsk_rt(t)->ctrl_page))
101 tsk_rt(t)->ctrl_page->sched.np.preempt = 0;
102}
103
104static inline int is_np(struct task_struct *t)
105{
106#ifdef CONFIG_SCHED_DEBUG_TRACE
107 int kernel, user;
108 kernel = is_kernel_np(t);
109 user = is_user_np(t);
110 if (kernel || user)
111 TRACE_TASK(t, " is non-preemptive: kernel=%d user=%d\n",
112
113 kernel, user);
114 return kernel || user;
115#else
116 return unlikely(is_kernel_np(t) || is_user_np(t));
117#endif
118}
119
120#endif
121
diff --git a/include/litmus/preempt.h b/include/litmus/preempt.h
new file mode 100644
index 000000000000..8f8bb635cb21
--- /dev/null
+++ b/include/litmus/preempt.h
@@ -0,0 +1,188 @@
1#ifndef LITMUS_PREEMPT_H
2#define LITMUS_PREEMPT_H
3
4#include <linux/types.h>
5#include <linux/cache.h>
6#include <linux/percpu.h>
7#include <asm/atomic.h>
8
9#include <litmus/debug_trace.h>
10
11DECLARE_PER_CPU(bool, litmus_preemption_in_progress);
12
13/* is_current_running() is legacy macro (and a hack) that is used to make
14 * the plugin logic, which still stems from the 2.6.20 era, work with current
15 * kernels.
16 *
17 * It used to honor the flag in the preempt_count variable that was
18 * set when scheduling is in progress. This doesn't exist anymore in recent
19 * Linux versions. Instead, Linux has moved to passing a 'preempt' flag to
20 * __schedule(). In particular, Linux ignores prev->state != TASK_RUNNING and
21 * does *not* process self-suspensions if an interrupt (i.e., a preemption)
22 * races with a task that is about to call schedule() anyway.
23 *
24 * The value of the 'preempt' flag in __schedule() is crucial
25 * information for some of the LITMUS^RT plugins, which must re-add
26 * soon-to-block tasks to the ready queue if the rest of the system doesn't
27 * process the preemption yet. Unfortunately, the flag is not passed to
28 * pick_next_task(). Hence, as a hack, we communicate it out of band via the
29 * global, per-core variable litmus_preemption_in_progress, which is set by
30 * the scheduler in __schedule() and read by the plugins via the
31 * is_current_running() macro.
32 */
33#define is_current_running() \
34 ((current)->state == TASK_RUNNING || \
35 this_cpu_read(litmus_preemption_in_progress))
36
37DECLARE_PER_CPU_SHARED_ALIGNED(atomic_t, resched_state);
38
39#ifdef CONFIG_PREEMPT_STATE_TRACE
40const char* sched_state_name(int s);
41#define TRACE_STATE(fmt, args...) TRACE("SCHED_STATE " fmt, args)
42#else
43#define TRACE_STATE(fmt, args...) /* ignore */
44#endif
45
46#define VERIFY_SCHED_STATE(x) \
47 do { int __s = get_sched_state(); \
48 if ((__s & (x)) == 0) \
49 TRACE_STATE("INVALID s=0x%x (%s) not " \
50 "in 0x%x (%s) [%s]\n", \
51 __s, sched_state_name(__s), \
52 (x), #x, __FUNCTION__); \
53 } while (0);
54
55#define TRACE_SCHED_STATE_CHANGE(x, y, cpu) \
56 TRACE_STATE("[P%d] 0x%x (%s) -> 0x%x (%s)\n", \
57 cpu, (x), sched_state_name(x), \
58 (y), sched_state_name(y))
59
60
61typedef enum scheduling_state {
62 TASK_SCHEDULED = (1 << 0), /* The currently scheduled task is the one that
63 * should be scheduled, and the processor does not
64 * plan to invoke schedule(). */
65 SHOULD_SCHEDULE = (1 << 1), /* A remote processor has determined that the
66 * processor should reschedule, but this has not
67 * been communicated yet (IPI still pending). */
68 WILL_SCHEDULE = (1 << 2), /* The processor has noticed that it has to
69 * reschedule and will do so shortly. */
70 TASK_PICKED = (1 << 3), /* The processor is currently executing schedule(),
71 * has selected a new task to schedule, but has not
72 * yet performed the actual context switch. */
73 PICKED_WRONG_TASK = (1 << 4), /* The processor has not yet performed the context
74 * switch, but a remote processor has already
75 * determined that a higher-priority task became
76 * eligible after the task was picked. */
77} sched_state_t;
78
79static inline sched_state_t get_sched_state_on(int cpu)
80{
81 return atomic_read(&per_cpu(resched_state, cpu));
82}
83
84static inline sched_state_t get_sched_state(void)
85{
86 return atomic_read(this_cpu_ptr(&resched_state));
87}
88
89static inline int is_in_sched_state(int possible_states)
90{
91 return get_sched_state() & possible_states;
92}
93
94static inline int cpu_is_in_sched_state(int cpu, int possible_states)
95{
96 return get_sched_state_on(cpu) & possible_states;
97}
98
99static inline void set_sched_state(sched_state_t s)
100{
101 TRACE_SCHED_STATE_CHANGE(get_sched_state(), s, smp_processor_id());
102 atomic_set(this_cpu_ptr(&resched_state), s);
103}
104
105static inline int sched_state_transition(sched_state_t from, sched_state_t to)
106{
107 sched_state_t old_state;
108
109 old_state = atomic_cmpxchg(this_cpu_ptr(&resched_state), from, to);
110 if (old_state == from) {
111 TRACE_SCHED_STATE_CHANGE(from, to, smp_processor_id());
112 return 1;
113 } else
114 return 0;
115}
116
117static inline int sched_state_transition_on(int cpu,
118 sched_state_t from,
119 sched_state_t to)
120{
121 sched_state_t old_state;
122
123 old_state = atomic_cmpxchg(&per_cpu(resched_state, cpu), from, to);
124 if (old_state == from) {
125 TRACE_SCHED_STATE_CHANGE(from, to, cpu);
126 return 1;
127 } else
128 return 0;
129}
130
131/* Plugins must call this function after they have decided which job to
132 * schedule next. IMPORTANT: this function must be called while still holding
133 * the lock that is used to serialize scheduling decisions.
134 *
135 * (Ideally, we would like to use runqueue locks for this purpose, but that
136 * would lead to deadlocks with the migration code.)
137 */
138static inline void sched_state_task_picked(void)
139{
140 VERIFY_SCHED_STATE(WILL_SCHEDULE);
141
142 /* WILL_SCHEDULE has only a local tansition => simple store is ok */
143 set_sched_state(TASK_PICKED);
144}
145
146static inline void sched_state_entered_schedule(void)
147{
148 /* Update state for the case that we entered schedule() not due to
149 * set_tsk_need_resched() */
150 set_sched_state(WILL_SCHEDULE);
151}
152
153/* Called by schedule() to check if the scheduling decision is still valid
154 * after a context switch. Returns 1 if the CPU needs to reschdule. */
155static inline int sched_state_validate_switch(void)
156{
157 int decision_ok = 0;
158
159 VERIFY_SCHED_STATE(PICKED_WRONG_TASK | TASK_PICKED | WILL_SCHEDULE);
160
161 if (is_in_sched_state(TASK_PICKED)) {
162 /* Might be good; let's try to transition out of this
163 * state. This must be done atomically since remote processors
164 * may try to change the state, too. */
165 decision_ok = sched_state_transition(TASK_PICKED, TASK_SCHEDULED);
166 }
167
168 if (!decision_ok)
169 TRACE_STATE("validation failed (%s)\n",
170 sched_state_name(get_sched_state()));
171
172 return !decision_ok;
173}
174
175/* State transition events. See litmus/preempt.c for details. */
176void sched_state_will_schedule(struct task_struct* tsk);
177void sched_state_ipi(void);
178/* Cause a CPU (remote or local) to reschedule. */
179void litmus_reschedule(int cpu);
180void litmus_reschedule_local(void);
181
182#ifdef CONFIG_DEBUG_KERNEL
183void sched_state_plugin_check(void);
184#else
185#define sched_state_plugin_check() /* no check */
186#endif
187
188#endif
diff --git a/include/litmus/reservations/alloc.h b/include/litmus/reservations/alloc.h
new file mode 100644
index 000000000000..b3471288c9f1
--- /dev/null
+++ b/include/litmus/reservations/alloc.h
@@ -0,0 +1,15 @@
1#ifndef LITMUS_RESERVATIONS_ALLOC_H
2#define LITMUS_RESERVATIONS_ALLOC_H
3
4#include <litmus/reservations/reservation.h>
5
6long alloc_polling_reservation(
7 int res_type,
8 struct reservation_config *config,
9 struct reservation **_res);
10
11long alloc_table_driven_reservation(
12 struct reservation_config *config,
13 struct reservation **_res);
14
15#endif \ No newline at end of file
diff --git a/include/litmus/reservations/budget-notifier.h b/include/litmus/reservations/budget-notifier.h
new file mode 100644
index 000000000000..d831fa9d5153
--- /dev/null
+++ b/include/litmus/reservations/budget-notifier.h
@@ -0,0 +1,50 @@
1#ifndef LITMUS_BUDGET_NOTIFIER_H
2#define LITMUS_BUDGET_NOTIFIER_H
3
4#include <linux/list.h>
5#include <linux/spinlock.h>
6
7struct budget_notifier;
8
9typedef void (*budget_callback_t) (
10 struct budget_notifier *bn
11);
12
13struct budget_notifier {
14 struct list_head list;
15 budget_callback_t budget_exhausted;
16 budget_callback_t budget_replenished;
17};
18
19struct budget_notifier_list {
20 struct list_head list;
21 raw_spinlock_t lock;
22};
23
24void budget_notifier_list_init(struct budget_notifier_list* bnl);
25
26static inline void budget_notifier_add(
27 struct budget_notifier_list *bnl,
28 struct budget_notifier *bn)
29{
30 unsigned long flags;
31
32 raw_spin_lock_irqsave(&bnl->lock, flags);
33 list_add(&bn->list, &bnl->list);
34 raw_spin_unlock_irqrestore(&bnl->lock, flags);
35}
36
37static inline void budget_notifier_remove(
38 struct budget_notifier_list *bnl,
39 struct budget_notifier *bn)
40{
41 unsigned long flags;
42
43 raw_spin_lock_irqsave(&bnl->lock, flags);
44 list_del(&bn->list);
45 raw_spin_unlock_irqrestore(&bnl->lock, flags);
46}
47
48void budget_notifiers_fire(struct budget_notifier_list *bnl, bool replenished);
49
50#endif
diff --git a/include/litmus/reservations/polling.h b/include/litmus/reservations/polling.h
new file mode 100644
index 000000000000..230e12b1088a
--- /dev/null
+++ b/include/litmus/reservations/polling.h
@@ -0,0 +1,19 @@
1#ifndef LITMUS_POLLING_RESERVATIONS_H
2#define LITMUS_POLLING_RESERVATIONS_H
3
4#include <litmus/reservations/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
19#endif
diff --git a/include/litmus/reservations/reservation.h b/include/litmus/reservations/reservation.h
new file mode 100644
index 000000000000..1752dac4e698
--- /dev/null
+++ b/include/litmus/reservations/reservation.h
@@ -0,0 +1,224 @@
1#ifndef LITMUS_RESERVATION_H
2#define LITMUS_RESERVATION_H
3
4#include <linux/list.h>
5#include <linux/hrtimer.h>
6
7#include <litmus/debug_trace.h>
8#include <litmus/reservations/budget-notifier.h>
9
10struct reservation_client;
11struct reservation_environment;
12struct reservation;
13
14typedef enum {
15 /* reservation has no clients, is not consuming budget */
16 RESERVATION_INACTIVE = 0,
17
18 /* reservation has clients, consumes budget when scheduled */
19 RESERVATION_ACTIVE,
20
21 /* reservation has no clients, but may be consuming budget */
22 RESERVATION_ACTIVE_IDLE,
23
24 /* Reservation has no budget and waits for
25 * replenishment. May or may not have clients. */
26 RESERVATION_DEPLETED,
27} reservation_state_t;
28
29
30/* ************************************************************************** */
31
32/* Select which task to dispatch. If NULL is returned, it means there is nothing
33 * to schedule right now and background work can be scheduled. */
34typedef struct task_struct * (*dispatch_t) (
35 struct reservation_client *client
36);
37
38/* Something that can be managed in a reservation and that can yield
39 * a process for dispatching. Contains a pointer to the reservation
40 * to which it "belongs". */
41struct reservation_client {
42 struct list_head list;
43 struct reservation* reservation;
44 dispatch_t dispatch;
45};
46
47
48/* ************************************************************************** */
49
50/* Called by reservations to request state change. */
51typedef void (*reservation_change_state_t) (
52 struct reservation_environment* env,
53 struct reservation *res,
54 reservation_state_t new_state
55);
56
57/* Called by reservations to request replenishment while not DEPLETED.
58 * Useful for soft reservations that remain ACTIVE with lower priority. */
59typedef void (*request_replenishment_t)(
60 struct reservation_environment* env,
61 struct reservation *res
62);
63
64/* The framework within wich reservations operate. */
65struct reservation_environment {
66 lt_t time_zero;
67 lt_t current_time;
68
69 /* services invoked by reservations */
70 reservation_change_state_t change_state;
71 request_replenishment_t request_replenishment;
72};
73
74/* ************************************************************************** */
75
76/* A new client is added or an existing client resumes. */
77typedef void (*client_arrives_t) (
78 struct reservation *reservation,
79 struct reservation_client *client
80);
81
82/* A client suspends or terminates. */
83typedef void (*client_departs_t) (
84 struct reservation *reservation,
85 struct reservation_client *client,
86 int did_signal_job_completion
87);
88
89/* A previously requested replenishment has occurred. */
90typedef void (*on_replenishment_timer_t) (
91 struct reservation *reservation
92);
93
94/* Update the reservation's budget to reflect execution or idling. */
95typedef void (*drain_budget_t) (
96 struct reservation *reservation,
97 lt_t how_much
98);
99
100/* Select a ready task from one of the clients for scheduling. */
101typedef struct task_struct* (*dispatch_client_t) (
102 struct reservation *reservation,
103 lt_t *time_slice /* May be used to force rescheduling after
104 some amount of time. 0 => no limit */
105);
106
107/* Destructor: called before scheduler is deactivated. */
108typedef void (*shutdown_t)(struct reservation *reservation);
109
110struct reservation_ops {
111 dispatch_client_t dispatch_client;
112
113 client_arrives_t client_arrives;
114 client_departs_t client_departs;
115
116 on_replenishment_timer_t replenish;
117 drain_budget_t drain_budget;
118
119 shutdown_t shutdown;
120};
121
122#define RESERVATION_BACKGROUND_PRIORITY ULLONG_MAX
123
124struct reservation {
125 /* used to queue in environment */
126 struct list_head list;
127 struct list_head replenish_list;
128
129 reservation_state_t state;
130 unsigned int id;
131 unsigned int kind;
132
133 /* exact meaning defined by impl. */
134 lt_t priority;
135 lt_t cur_budget;
136 lt_t next_replenishment;
137
138 /* budget stats */
139 lt_t budget_consumed; /* how much budget consumed in this allocation cycle? */
140 lt_t budget_consumed_total;
141
142 /* list of registered budget callbacks */
143 struct budget_notifier_list budget_notifiers;
144
145 /* for memory reclamation purposes */
146 struct list_head all_list;
147
148 /* interaction with framework */
149 struct reservation_environment *env;
150 struct reservation_ops *ops;
151
152 struct list_head clients;
153};
154
155void reservation_init(struct reservation *res);
156
157/* Default implementations */
158
159/* simply select the first client in the list, set *for_at_most to zero */
160struct task_struct* default_dispatch_client(
161 struct reservation *res,
162 lt_t *for_at_most
163);
164
165/* drain budget at linear rate, enter DEPLETED state when budget used up */
166void common_drain_budget(struct reservation *res, lt_t how_much);
167
168/* "connector" reservation client to hook up tasks with reservations */
169struct task_client {
170 struct reservation_client client;
171 struct task_struct *task;
172};
173
174void task_client_init(struct task_client *tc, struct task_struct *task,
175 struct reservation *reservation);
176
177#define SUP_RESCHEDULE_NOW (0)
178#define SUP_NO_SCHEDULER_UPDATE (ULLONG_MAX)
179
180/* A simple uniprocessor (SUP) flat (i.e., non-hierarchical) reservation
181 * environment.
182 */
183struct sup_reservation_environment {
184 struct reservation_environment env;
185
186 /* ordered by priority */
187 struct list_head active_reservations;
188
189 /* ordered by next_replenishment */
190 struct list_head depleted_reservations;
191
192 /* unordered */
193 struct list_head inactive_reservations;
194
195 /* list of all reservations */
196 struct list_head all_reservations;
197
198 /* - SUP_RESCHEDULE_NOW means call sup_dispatch() now
199 * - SUP_NO_SCHEDULER_UPDATE means nothing to do
200 * any other value means program a timer for the given time
201 */
202 lt_t next_scheduler_update;
203 /* set to true if a call to sup_dispatch() is imminent */
204 bool will_schedule;
205};
206
207/* Contract:
208 * - before calling into sup_ code, or any reservation methods,
209 * update the time with sup_update_time(); and
210 * - after calling into sup_ code, or any reservation methods,
211 * check next_scheduler_update and program timer or trigger
212 * scheduler invocation accordingly.
213 */
214
215void sup_init(struct sup_reservation_environment* sup_env);
216void sup_add_new_reservation(struct sup_reservation_environment* sup_env,
217 struct reservation* new_res);
218void sup_update_time(struct sup_reservation_environment* sup_env, lt_t now);
219struct task_struct* sup_dispatch(struct sup_reservation_environment* sup_env);
220
221struct reservation* sup_find_by_id(struct sup_reservation_environment* sup_env,
222 unsigned int id);
223
224#endif
diff --git a/include/litmus/reservations/table-driven.h b/include/litmus/reservations/table-driven.h
new file mode 100644
index 000000000000..b6302a2f200d
--- /dev/null
+++ b/include/litmus/reservations/table-driven.h
@@ -0,0 +1,23 @@
1#ifndef LITMUS_RESERVATIONS_TABLE_DRIVEN_H
2#define LITMUS_RESERVATIONS_TABLE_DRIVEN_H
3
4#include <litmus/reservations/reservation.h>
5
6struct table_driven_reservation {
7 /* extend basic reservation */
8 struct reservation res;
9
10 lt_t major_cycle;
11 unsigned int next_interval;
12 unsigned int num_intervals;
13 struct lt_interval *intervals;
14
15 /* info about current scheduling slot */
16 struct lt_interval cur_interval;
17 lt_t major_cycle_start;
18};
19
20void table_driven_reservation_init(struct table_driven_reservation *tdres,
21 lt_t major_cycle, struct lt_interval *intervals, unsigned int num_intervals);
22
23#endif
diff --git a/include/litmus/rt_domain.h b/include/litmus/rt_domain.h
new file mode 100644
index 000000000000..ac249292e866
--- /dev/null
+++ b/include/litmus/rt_domain.h
@@ -0,0 +1,182 @@
1/* CLEANUP: Add comments and make it less messy.
2 *
3 */
4
5#ifndef __UNC_RT_DOMAIN_H__
6#define __UNC_RT_DOMAIN_H__
7
8#include <litmus/bheap.h>
9
10#define RELEASE_QUEUE_SLOTS 127 /* prime */
11
12struct _rt_domain;
13
14typedef int (*check_resched_needed_t)(struct _rt_domain *rt);
15typedef void (*release_jobs_t)(struct _rt_domain *rt, struct bheap* tasks);
16
17struct release_queue {
18 /* each slot maintains a list of release heaps sorted
19 * by release time */
20 struct list_head slot[RELEASE_QUEUE_SLOTS];
21};
22
23typedef struct _rt_domain {
24 /* runnable rt tasks are in here */
25 raw_spinlock_t ready_lock;
26 struct bheap ready_queue;
27
28 /* real-time tasks waiting for release are in here */
29 raw_spinlock_t release_lock;
30 struct release_queue release_queue;
31
32#ifdef CONFIG_RELEASE_MASTER
33 int release_master;
34#endif
35
36 /* for moving tasks to the release queue */
37 raw_spinlock_t tobe_lock;
38 struct list_head tobe_released;
39
40 /* how do we check if we need to kick another CPU? */
41 check_resched_needed_t check_resched;
42
43 /* how do we release jobs? */
44 release_jobs_t release_jobs;
45
46 /* how are tasks ordered in the ready queue? */
47 bheap_prio_t order;
48} rt_domain_t;
49
50struct release_heap {
51 /* list_head for per-time-slot list */
52 struct list_head list;
53 lt_t release_time;
54 /* all tasks to be released at release_time */
55 struct bheap heap;
56 /* used to trigger the release */
57 struct hrtimer timer;
58
59#ifdef CONFIG_RELEASE_MASTER
60 /* used to delegate releases */
61 struct hrtimer_start_on_info info;
62#endif
63 /* required for the timer callback */
64 rt_domain_t* dom;
65};
66
67
68static inline struct task_struct* __next_ready(rt_domain_t* rt)
69{
70 struct bheap_node *hn = bheap_peek(rt->order, &rt->ready_queue);
71 if (hn)
72 return bheap2task(hn);
73 else
74 return NULL;
75}
76
77void rt_domain_init(rt_domain_t *rt, bheap_prio_t order,
78 check_resched_needed_t check,
79 release_jobs_t relase);
80
81void __add_ready(rt_domain_t* rt, struct task_struct *new);
82void __merge_ready(rt_domain_t* rt, struct bheap *tasks);
83void __add_release(rt_domain_t* rt, struct task_struct *task);
84
85static inline struct task_struct* __take_ready(rt_domain_t* rt)
86{
87 struct bheap_node* hn = bheap_take(rt->order, &rt->ready_queue);
88 if (hn)
89 return bheap2task(hn);
90 else
91 return NULL;
92}
93
94static inline struct task_struct* __peek_ready(rt_domain_t* rt)
95{
96 struct bheap_node* hn = bheap_peek(rt->order, &rt->ready_queue);
97 if (hn)
98 return bheap2task(hn);
99 else
100 return NULL;
101}
102
103static inline int is_queued(struct task_struct *t)
104{
105 BUG_ON(!tsk_rt(t)->heap_node);
106 return bheap_node_in_heap(tsk_rt(t)->heap_node);
107}
108
109static inline void remove(rt_domain_t* rt, struct task_struct *t)
110{
111 bheap_delete(rt->order, &rt->ready_queue, tsk_rt(t)->heap_node);
112}
113
114static inline void add_ready(rt_domain_t* rt, struct task_struct *new)
115{
116 unsigned long flags;
117 /* first we need the write lock for rt_ready_queue */
118 raw_spin_lock_irqsave(&rt->ready_lock, flags);
119 __add_ready(rt, new);
120 raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
121}
122
123static inline void merge_ready(rt_domain_t* rt, struct bheap* tasks)
124{
125 unsigned long flags;
126 raw_spin_lock_irqsave(&rt->ready_lock, flags);
127 __merge_ready(rt, tasks);
128 raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
129}
130
131static inline struct task_struct* take_ready(rt_domain_t* rt)
132{
133 unsigned long flags;
134 struct task_struct* ret;
135 /* first we need the write lock for rt_ready_queue */
136 raw_spin_lock_irqsave(&rt->ready_lock, flags);
137 ret = __take_ready(rt);
138 raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
139 return ret;
140}
141
142
143static inline void add_release(rt_domain_t* rt, struct task_struct *task)
144{
145 unsigned long flags;
146 raw_spin_lock_irqsave(&rt->tobe_lock, flags);
147 __add_release(rt, task);
148 raw_spin_unlock_irqrestore(&rt->tobe_lock, flags);
149}
150
151#ifdef CONFIG_RELEASE_MASTER
152void __add_release_on(rt_domain_t* rt, struct task_struct *task,
153 int target_cpu);
154
155static inline void add_release_on(rt_domain_t* rt,
156 struct task_struct *task,
157 int target_cpu)
158{
159 unsigned long flags;
160 raw_spin_lock_irqsave(&rt->tobe_lock, flags);
161 __add_release_on(rt, task, target_cpu);
162 raw_spin_unlock_irqrestore(&rt->tobe_lock, flags);
163}
164#endif
165
166static inline int __jobs_pending(rt_domain_t* rt)
167{
168 return !bheap_empty(&rt->ready_queue);
169}
170
171static inline int jobs_pending(rt_domain_t* rt)
172{
173 unsigned long flags;
174 int ret;
175 /* first we need the write lock for rt_ready_queue */
176 raw_spin_lock_irqsave(&rt->ready_lock, flags);
177 ret = !bheap_empty(&rt->ready_queue);
178 raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
179 return ret;
180}
181
182#endif
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 8c7869f46bfb..9b291343714f 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -62,6 +62,7 @@ typedef enum {
62#define LITMUS_MAX_PRIORITY 512 62#define LITMUS_MAX_PRIORITY 512
63#define LITMUS_HIGHEST_PRIORITY 1 63#define LITMUS_HIGHEST_PRIORITY 1
64#define LITMUS_LOWEST_PRIORITY (LITMUS_MAX_PRIORITY - 1) 64#define LITMUS_LOWEST_PRIORITY (LITMUS_MAX_PRIORITY - 1)
65#define LITMUS_NO_PRIORITY UINT_MAX
65 66
66/* Provide generic comparison macros for userspace, 67/* Provide generic comparison macros for userspace,
67 * in case that we change this later. */ 68 * in case that we change this later. */
@@ -71,6 +72,46 @@ typedef enum {
71 ((p) >= LITMUS_HIGHEST_PRIORITY && \ 72 ((p) >= LITMUS_HIGHEST_PRIORITY && \
72 (p) <= LITMUS_LOWEST_PRIORITY) 73 (p) <= LITMUS_LOWEST_PRIORITY)
73 74
75/* reservation support */
76
77typedef enum {
78 PERIODIC_POLLING = 10,
79 SPORADIC_POLLING,
80 TABLE_DRIVEN,
81} reservation_type_t;
82
83struct lt_interval {
84 lt_t start;
85 lt_t end;
86};
87
88#ifndef __KERNEL__
89#define __user
90#endif
91
92struct reservation_config {
93 unsigned int id;
94 lt_t priority;
95 int cpu;
96
97 union {
98 struct {
99 lt_t period;
100 lt_t budget;
101 lt_t relative_deadline;
102 lt_t offset;
103 } polling_params;
104
105 struct {
106 lt_t major_cycle_length;
107 unsigned int num_intervals;
108 struct lt_interval __user *intervals;
109 } table_driven_params;
110 };
111};
112
113/* regular sporadic task support */
114
74struct rt_task { 115struct rt_task {
75 lt_t exec_cost; 116 lt_t exec_cost;
76 lt_t period; 117 lt_t period;
@@ -83,54 +124,6 @@ struct rt_task {
83 release_policy_t release_policy; 124 release_policy_t release_policy;
84}; 125};
85 126
86union np_flag {
87 uint64_t raw;
88 struct {
89 /* Is the task currently in a non-preemptive section? */
90 uint64_t flag:31;
91 /* Should the task call into the scheduler? */
92 uint64_t preempt:1;
93 } np;
94};
95
96/* The definition of the data that is shared between the kernel and real-time
97 * tasks via a shared page (see litmus/ctrldev.c).
98 *
99 * WARNING: User space can write to this, so don't trust
100 * the correctness of the fields!
101 *
102 * This servees two purposes: to enable efficient signaling
103 * of non-preemptive sections (user->kernel) and
104 * delayed preemptions (kernel->user), and to export
105 * some real-time relevant statistics such as preemption and
106 * migration data to user space. We can't use a device to export
107 * statistics because we want to avoid system call overhead when
108 * determining preemption/migration overheads).
109 */
110struct control_page {
111 /* This flag is used by userspace to communicate non-preempive
112 * sections. */
113 volatile union np_flag sched;
114
115 volatile uint64_t irq_count; /* Incremented by the kernel each time an IRQ is
116 * handled. */
117
118 /* Locking overhead tracing: userspace records here the time stamp
119 * and IRQ counter prior to starting the system call. */
120 uint64_t ts_syscall_start; /* Feather-Trace cycles */
121 uint64_t irq_syscall_start; /* Snapshot of irq_count when the syscall
122 * started. */
123
124 /* to be extended */
125};
126
127/* Expected offsets within the control page. */
128
129#define LITMUS_CP_OFFSET_SCHED 0
130#define LITMUS_CP_OFFSET_IRQ_COUNT 8
131#define LITMUS_CP_OFFSET_TS_SC_START 16
132#define LITMUS_CP_OFFSET_IRQ_SC_START 24
133
134/* don't export internal data structures to user space (liblitmus) */ 127/* don't export internal data structures to user space (liblitmus) */
135#ifdef __KERNEL__ 128#ifdef __KERNEL__
136 129
@@ -177,9 +170,6 @@ struct pfair_param;
177 * be explicitly set up before the task set is launched. 170 * be explicitly set up before the task set is launched.
178 */ 171 */
179struct rt_param { 172struct rt_param {
180 /* Generic flags available for plugin-internal use. */
181 unsigned int flags:8;
182
183 /* do we need to check for srp blocking? */ 173 /* do we need to check for srp blocking? */
184 unsigned int srp_non_recurse:1; 174 unsigned int srp_non_recurse:1;
185 175
@@ -207,13 +197,19 @@ struct rt_param {
207 /* timing parameters */ 197 /* timing parameters */
208 struct rt_job job_params; 198 struct rt_job job_params;
209 199
200
201 /* Special handling for periodic tasks executing
202 * clock_nanosleep(CLOCK_MONOTONIC, ...).
203 */
204 lt_t nanosleep_wakeup;
205 unsigned int doing_abs_nanosleep:1;
206
210 /* Should the next job be released at some time other than 207 /* Should the next job be released at some time other than
211 * just period time units after the last release? 208 * just period time units after the last release?
212 */ 209 */
213 unsigned int sporadic_release:1; 210 unsigned int sporadic_release:1;
214 lt_t sporadic_release_time; 211 lt_t sporadic_release_time;
215 212
216
217 /* task representing the current "inherited" task 213 /* task representing the current "inherited" task
218 * priority, assigned by inherit_priority and 214 * priority, assigned by inherit_priority and
219 * return priority in the scheduler plugins. 215 * return priority in the scheduler plugins.
@@ -255,7 +251,10 @@ struct rt_param {
255 volatile int linked_on; 251 volatile int linked_on;
256 252
257 /* PFAIR/PD^2 state. Allocated on demand. */ 253 /* PFAIR/PD^2 state. Allocated on demand. */
258 struct pfair_param* pfair; 254 union {
255 void *plugin_state;
256 struct pfair_param *pfair;
257 };
259 258
260 /* Fields saved before BE->RT transition. 259 /* Fields saved before BE->RT transition.
261 */ 260 */
diff --git a/include/litmus/sched_plugin.h b/include/litmus/sched_plugin.h
new file mode 100644
index 000000000000..0923f26b745a
--- /dev/null
+++ b/include/litmus/sched_plugin.h
@@ -0,0 +1,180 @@
1/*
2 * Definition of the scheduler plugin interface.
3 *
4 */
5#ifndef _LINUX_SCHED_PLUGIN_H_
6#define _LINUX_SCHED_PLUGIN_H_
7
8#include <linux/sched.h>
9
10#ifdef CONFIG_LITMUS_LOCKING
11#include <litmus/locking.h>
12#endif
13
14/************************ setup/tear down ********************/
15
16typedef long (*activate_plugin_t) (void);
17typedef long (*deactivate_plugin_t) (void);
18
19struct domain_proc_info;
20typedef long (*get_domain_proc_info_t) (struct domain_proc_info **info);
21
22
23/********************* scheduler invocation ******************/
24/* The main scheduling function, called to select the next task to dispatch. */
25typedef struct task_struct* (*schedule_t)(struct task_struct * prev);
26/* Clean up after the task switch has occured.
27 * This function is called after every (even non-rt) task switch.
28 */
29typedef void (*finish_switch_t)(struct task_struct *prev);
30
31
32/* When waiting for the stack of the task selected by the plugin
33 * to become available, this callback is invoked to give the
34 * plugin a chance to cancel the wait. If the plugin returns false,
35 * the scheduler is invoked again. */
36typedef bool (*should_wait_for_stack_t)(struct task_struct *next);
37
38/* After a pull migration (which involves dropping scheduler locks),
39 * the plugin is given the chance to validate that the task is still
40 * the right one. If the plugin returns false, the scheduler
41 * will be invoked again. */
42typedef bool (*post_migration_validate_t)(struct task_struct *next);
43
44/* After dropping the lock to facilitate a pull migration, the task
45 * state may have changed. In this case, the core notifies the plugin
46 * with this callback and then invokes the scheduler again. */
47typedef void (*next_became_invalid_t)(struct task_struct *next);
48
49/********************* task state changes ********************/
50
51/* Called to setup a new real-time task.
52 * Release the first job, enqueue, etc.
53 * Task may already be running.
54 */
55typedef void (*task_new_t) (struct task_struct *task,
56 int on_rq,
57 int running);
58
59/* Called when userspace seeks to set new task parameters for a task
60 * that is already in real-time mode (i.e., is_realtime(task)).
61 */
62typedef long (*task_change_params_t) (struct task_struct *task,
63 struct rt_task *new_params);
64
65/* Called to re-introduce a task after blocking.
66 * Can potentially be called multiple times.
67 */
68typedef void (*task_wake_up_t) (struct task_struct *task);
69/* called to notify the plugin of a blocking real-time task
70 * it will only be called for real-time tasks and before schedule is called */
71typedef void (*task_block_t) (struct task_struct *task);
72/* Called when a real-time task exits or changes to a different scheduling
73 * class.
74 * Free any allocated resources
75 */
76typedef void (*task_exit_t) (struct task_struct *);
77
78/* task_exit() is called with interrupts disabled and runqueue locks held, and
79 * thus and cannot block or spin. task_cleanup() is called sometime later
80 * without any locks being held.
81 */
82typedef void (*task_cleanup_t) (struct task_struct *);
83
84#ifdef CONFIG_LITMUS_LOCKING
85/* Called when the current task attempts to create a new lock of a given
86 * protocol type. */
87typedef long (*allocate_lock_t) (struct litmus_lock **lock, int type,
88 void* __user config);
89#endif
90
91
92/********************* sys call backends ********************/
93/* This function causes the caller to sleep until the next release */
94typedef long (*complete_job_t) (void);
95
96typedef long (*admit_task_t)(struct task_struct* tsk);
97
98/* return false to indicate that the plugin does not support forking */
99typedef bool (*fork_task_t)(struct task_struct* tsk);
100
101typedef long (*wait_for_release_at_t)(lt_t release_time);
102
103/* Informs the plugin when a synchronous release takes place. */
104typedef void (*synchronous_release_at_t)(lt_t time_zero);
105
106/* How much budget has the current task consumed so far, and how much
107 * has it left? The default implementation ties into the per-task
108 * budget enforcement code. Plugins can override this to report
109 * reservation-specific values. */
110typedef void (*current_budget_t)(lt_t *used_so_far, lt_t *remaining);
111
112/* Reservation creation/removal backends. Meaning of reservation_type and
113 * reservation_id are entirely plugin-specific. */
114typedef long (*reservation_create_t)(int reservation_type, void* __user config);
115typedef long (*reservation_destroy_t)(unsigned int reservation_id, int cpu);
116
117/************************ misc routines ***********************/
118
119
120struct sched_plugin {
121 struct list_head list;
122 /* basic info */
123 char *plugin_name;
124
125 /* setup */
126 activate_plugin_t activate_plugin;
127 deactivate_plugin_t deactivate_plugin;
128 get_domain_proc_info_t get_domain_proc_info;
129
130 /* scheduler invocation */
131 schedule_t schedule;
132 finish_switch_t finish_switch;
133
134 /* control over pull migrations */
135 should_wait_for_stack_t should_wait_for_stack;
136 next_became_invalid_t next_became_invalid;
137 post_migration_validate_t post_migration_validate;
138
139 /* syscall backend */
140 complete_job_t complete_job;
141 wait_for_release_at_t wait_for_release_at;
142 synchronous_release_at_t synchronous_release_at;
143
144 /* task state changes */
145 admit_task_t admit_task;
146 fork_task_t fork_task;
147
148 task_new_t task_new;
149 task_wake_up_t task_wake_up;
150 task_block_t task_block;
151
152 /* optional: support task parameter changes at runtime */
153 task_change_params_t task_change_params;
154
155 task_exit_t task_exit;
156 task_cleanup_t task_cleanup;
157
158 current_budget_t current_budget;
159
160 /* Reservation support */
161 reservation_create_t reservation_create;
162 reservation_destroy_t reservation_destroy;
163
164#ifdef CONFIG_LITMUS_LOCKING
165 /* locking protocols */
166 allocate_lock_t allocate_lock;
167#endif
168} __attribute__ ((__aligned__(SMP_CACHE_BYTES)));
169
170
171extern struct sched_plugin *litmus;
172
173int register_sched_plugin(struct sched_plugin* plugin);
174struct sched_plugin* find_sched_plugin(const char* name);
175void print_sched_plugins(struct seq_file *m);
176
177
178extern struct sched_plugin linux_sched_plugin;
179
180#endif
diff --git a/include/litmus/srp.h b/include/litmus/srp.h
new file mode 100644
index 000000000000..c9a4552b2bf3
--- /dev/null
+++ b/include/litmus/srp.h
@@ -0,0 +1,28 @@
1#ifndef LITMUS_SRP_H
2#define LITMUS_SRP_H
3
4struct srp_semaphore;
5
6struct srp_priority {
7 struct list_head list;
8 unsigned int priority;
9 pid_t pid;
10};
11#define list2prio(l) list_entry(l, struct srp_priority, list)
12
13/* struct for uniprocessor SRP "semaphore" */
14struct srp_semaphore {
15 struct litmus_lock litmus_lock;
16 struct srp_priority ceiling;
17 struct task_struct* owner;
18 int cpu; /* cpu associated with this "semaphore" and resource */
19};
20
21/* map a task to its SRP preemption level priority */
22typedef unsigned int (*srp_prioritization_t)(struct task_struct* t);
23/* Must be updated by each plugin that uses SRP.*/
24extern srp_prioritization_t get_srp_prio;
25
26struct srp_semaphore* allocate_srp_semaphore(void);
27
28#endif
diff --git a/include/litmus/wait.h b/include/litmus/wait.h
new file mode 100644
index 000000000000..ce1347c355f8
--- /dev/null
+++ b/include/litmus/wait.h
@@ -0,0 +1,57 @@
1#ifndef _LITMUS_WAIT_H_
2#define _LITMUS_WAIT_H_
3
4struct task_struct* __waitqueue_remove_first(wait_queue_head_t *wq);
5
6/* wrap regular wait_queue_t head */
7struct __prio_wait_queue {
8 wait_queue_t wq;
9
10 /* some priority point */
11 lt_t priority;
12 /* break ties in priority by lower tie_breaker */
13 unsigned int tie_breaker;
14};
15
16typedef struct __prio_wait_queue prio_wait_queue_t;
17
18static inline void init_prio_waitqueue_entry(prio_wait_queue_t *pwq,
19 struct task_struct* t,
20 lt_t priority)
21{
22 init_waitqueue_entry(&pwq->wq, t);
23 pwq->priority = priority;
24 pwq->tie_breaker = 0;
25}
26
27static inline void init_prio_waitqueue_entry_tie(prio_wait_queue_t *pwq,
28 struct task_struct* t,
29 lt_t priority,
30 unsigned int tie_breaker)
31{
32 init_waitqueue_entry(&pwq->wq, t);
33 pwq->priority = priority;
34 pwq->tie_breaker = tie_breaker;
35}
36
37unsigned int __add_wait_queue_prio_exclusive(
38 wait_queue_head_t* head,
39 prio_wait_queue_t *new);
40
41static inline unsigned int add_wait_queue_prio_exclusive(
42 wait_queue_head_t* head,
43 prio_wait_queue_t *new)
44{
45 unsigned long flags;
46 unsigned int passed;
47
48 spin_lock_irqsave(&head->lock, flags);
49 passed = __add_wait_queue_prio_exclusive(head, new);
50
51 spin_unlock_irqrestore(&head->lock, flags);
52
53 return passed;
54}
55
56
57#endif
generated by cgit v1.2.2 (git 2.25.0) at 2026-02-23 05:14:29 -0500