aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNamhoon Kim <namhoonk@ludwig.cs.unc.edu>2013-11-25 17:16:38 -0500
committerNamhoon Kim <namhoonk@ludwig.cs.unc.edu>2013-11-25 17:16:38 -0500
commitd2f58ddbfb1dd4fb1b6ff0bebbd886b1dcf5af34 (patch)
tree962fdfb5344956d341adcfc20508adb14437acbc
parentbcaacec1ca714224807728a63eccb37e3d685cd6 (diff)
First draft of C-FL-splitwip-pgm-split
Diffstat
l---------arch/arm/boot/dts/include/dt-bindings1
-rw-r--r--[l---------]arch/microblaze/boot/dts/system.dts368
-rw-r--r--include/litmus/edf_split_common.h25
-rw-r--r--include/litmus/litmus.h1
-rw-r--r--include/litmus/rt_param.h4
-rw-r--r--litmus/Makefile4
-rw-r--r--litmus/edf_split_common.c171
-rw-r--r--litmus/sched_cfl_split.c1006
8 files changed, 1576 insertions, 4 deletions
diff --git a/arch/arm/boot/dts/include/dt-bindings b/arch/arm/boot/dts/include/dt-bindings
deleted file mode 120000
index 08c00e4972fa..000000000000
--- a/arch/arm/boot/dts/include/dt-bindings
+++ /dev/null
@@ -1 +0,0 @@
1../../../../../include/dt-bindings \ No newline at end of file
diff --git a/arch/microblaze/boot/dts/system.dts b/arch/microblaze/boot/dts/system.dts
index 7cb657892f21..3f85df2b73b3 120000..100644
--- a/arch/microblaze/boot/dts/system.dts
+++ b/arch/microblaze/boot/dts/system.dts
@@ -1 +1,367 @@
1../../platform/generic/system.dts \ No newline at end of file 1/*
2 * Device Tree Generator version: 1.1
3 *
4 * (C) Copyright 2007-2008 Xilinx, Inc.
5 * (C) Copyright 2007-2009 Michal Simek
6 *
7 * Michal SIMEK <monstr@monstr.eu>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License as
11 * published by the Free Software Foundation; either version 2 of
12 * the License, or (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
22 * MA 02111-1307 USA
23 *
24 * CAUTION: This file is automatically generated by libgen.
25 * Version: Xilinx EDK 10.1.03 EDK_K_SP3.6
26 *
27 * XPS project directory: Xilinx-ML505-ll_temac-sgdma-MMU-FDT-edk101
28 */
29
30/dts-v1/;
31/ {
32 #address-cells = <1>;
33 #size-cells = <1>;
34 compatible = "xlnx,microblaze";
35 hard-reset-gpios = <&LEDs_8Bit 2 1>;
36 model = "testing";
37 DDR2_SDRAM: memory@90000000 {
38 device_type = "memory";
39 reg = < 0x90000000 0x10000000 >;
40 } ;
41 aliases {
42 ethernet0 = &Hard_Ethernet_MAC;
43 serial0 = &RS232_Uart_1;
44 } ;
45 chosen {
46 bootargs = "console=ttyUL0,115200 highres=on";
47 linux,stdout-path = "/plb@0/serial@84000000";
48 } ;
49 cpus {
50 #address-cells = <1>;
51 #cpus = <0x1>;
52 #size-cells = <0>;
53 microblaze_0: cpu@0 {
54 clock-frequency = <125000000>;
55 compatible = "xlnx,microblaze-7.10.d";
56 d-cache-baseaddr = <0x90000000>;
57 d-cache-highaddr = <0x9fffffff>;
58 d-cache-line-size = <0x10>;
59 d-cache-size = <0x2000>;
60 device_type = "cpu";
61 i-cache-baseaddr = <0x90000000>;
62 i-cache-highaddr = <0x9fffffff>;
63 i-cache-line-size = <0x10>;
64 i-cache-size = <0x2000>;
65 model = "microblaze,7.10.d";
66 reg = <0>;
67 timebase-frequency = <125000000>;
68 xlnx,addr-tag-bits = <0xf>;
69 xlnx,allow-dcache-wr = <0x1>;
70 xlnx,allow-icache-wr = <0x1>;
71 xlnx,area-optimized = <0x0>;
72 xlnx,cache-byte-size = <0x2000>;
73 xlnx,d-lmb = <0x1>;
74 xlnx,d-opb = <0x0>;
75 xlnx,d-plb = <0x1>;
76 xlnx,data-size = <0x20>;
77 xlnx,dcache-addr-tag = <0xf>;
78 xlnx,dcache-always-used = <0x1>;
79 xlnx,dcache-byte-size = <0x2000>;
80 xlnx,dcache-line-len = <0x4>;
81 xlnx,dcache-use-fsl = <0x1>;
82 xlnx,debug-enabled = <0x1>;
83 xlnx,div-zero-exception = <0x1>;
84 xlnx,dopb-bus-exception = <0x0>;
85 xlnx,dynamic-bus-sizing = <0x1>;
86 xlnx,edge-is-positive = <0x1>;
87 xlnx,family = "virtex5";
88 xlnx,endianness = <0x1>;
89 xlnx,fpu-exception = <0x1>;
90 xlnx,fsl-data-size = <0x20>;
91 xlnx,fsl-exception = <0x0>;
92 xlnx,fsl-links = <0x0>;
93 xlnx,i-lmb = <0x1>;
94 xlnx,i-opb = <0x0>;
95 xlnx,i-plb = <0x1>;
96 xlnx,icache-always-used = <0x1>;
97 xlnx,icache-line-len = <0x4>;
98 xlnx,icache-use-fsl = <0x1>;
99 xlnx,ill-opcode-exception = <0x1>;
100 xlnx,instance = "microblaze_0";
101 xlnx,interconnect = <0x1>;
102 xlnx,interrupt-is-edge = <0x0>;
103 xlnx,iopb-bus-exception = <0x0>;
104 xlnx,mmu-dtlb-size = <0x4>;
105 xlnx,mmu-itlb-size = <0x2>;
106 xlnx,mmu-tlb-access = <0x3>;
107 xlnx,mmu-zones = <0x10>;
108 xlnx,number-of-pc-brk = <0x1>;
109 xlnx,number-of-rd-addr-brk = <0x0>;
110 xlnx,number-of-wr-addr-brk = <0x0>;
111 xlnx,opcode-0x0-illegal = <0x1>;
112 xlnx,pvr = <0x2>;
113 xlnx,pvr-user1 = <0x0>;
114 xlnx,pvr-user2 = <0x0>;
115 xlnx,reset-msr = <0x0>;
116 xlnx,sco = <0x0>;
117 xlnx,unaligned-exceptions = <0x1>;
118 xlnx,use-barrel = <0x1>;
119 xlnx,use-dcache = <0x1>;
120 xlnx,use-div = <0x1>;
121 xlnx,use-ext-brk = <0x1>;
122 xlnx,use-ext-nm-brk = <0x1>;
123 xlnx,use-extended-fsl-instr = <0x0>;
124 xlnx,use-fpu = <0x2>;
125 xlnx,use-hw-mul = <0x2>;
126 xlnx,use-icache = <0x1>;
127 xlnx,use-interrupt = <0x1>;
128 xlnx,use-mmu = <0x3>;
129 xlnx,use-msr-instr = <0x1>;
130 xlnx,use-pcmp-instr = <0x1>;
131 } ;
132 } ;
133 mb_plb: plb@0 {
134 #address-cells = <1>;
135 #size-cells = <1>;
136 compatible = "xlnx,plb-v46-1.03.a", "xlnx,plb-v46-1.00.a", "simple-bus";
137 ranges ;
138 FLASH: flash@a0000000 {
139 bank-width = <2>;
140 compatible = "xlnx,xps-mch-emc-2.00.a", "cfi-flash";
141 reg = < 0xa0000000 0x2000000 >;
142 xlnx,family = "virtex5";
143 xlnx,include-datawidth-matching-0 = <0x1>;
144 xlnx,include-datawidth-matching-1 = <0x0>;
145 xlnx,include-datawidth-matching-2 = <0x0>;
146 xlnx,include-datawidth-matching-3 = <0x0>;
147 xlnx,include-negedge-ioregs = <0x0>;
148 xlnx,include-plb-ipif = <0x1>;
149 xlnx,include-wrbuf = <0x1>;
150 xlnx,max-mem-width = <0x10>;
151 xlnx,mch-native-dwidth = <0x20>;
152 xlnx,mch-plb-clk-period-ps = <0x1f40>;
153 xlnx,mch-splb-awidth = <0x20>;
154 xlnx,mch0-accessbuf-depth = <0x10>;
155 xlnx,mch0-protocol = <0x0>;
156 xlnx,mch0-rddatabuf-depth = <0x10>;
157 xlnx,mch1-accessbuf-depth = <0x10>;
158 xlnx,mch1-protocol = <0x0>;
159 xlnx,mch1-rddatabuf-depth = <0x10>;
160 xlnx,mch2-accessbuf-depth = <0x10>;
161 xlnx,mch2-protocol = <0x0>;
162 xlnx,mch2-rddatabuf-depth = <0x10>;
163 xlnx,mch3-accessbuf-depth = <0x10>;
164 xlnx,mch3-protocol = <0x0>;
165 xlnx,mch3-rddatabuf-depth = <0x10>;
166 xlnx,mem0-width = <0x10>;
167 xlnx,mem1-width = <0x20>;
168 xlnx,mem2-width = <0x20>;
169 xlnx,mem3-width = <0x20>;
170 xlnx,num-banks-mem = <0x1>;
171 xlnx,num-channels = <0x0>;
172 xlnx,priority-mode = <0x0>;
173 xlnx,synch-mem-0 = <0x0>;
174 xlnx,synch-mem-1 = <0x0>;
175 xlnx,synch-mem-2 = <0x0>;
176 xlnx,synch-mem-3 = <0x0>;
177 xlnx,synch-pipedelay-0 = <0x2>;
178 xlnx,synch-pipedelay-1 = <0x2>;
179 xlnx,synch-pipedelay-2 = <0x2>;
180 xlnx,synch-pipedelay-3 = <0x2>;
181 xlnx,tavdv-ps-mem-0 = <0x1adb0>;
182 xlnx,tavdv-ps-mem-1 = <0x3a98>;
183 xlnx,tavdv-ps-mem-2 = <0x3a98>;
184 xlnx,tavdv-ps-mem-3 = <0x3a98>;
185 xlnx,tcedv-ps-mem-0 = <0x1adb0>;
186 xlnx,tcedv-ps-mem-1 = <0x3a98>;
187 xlnx,tcedv-ps-mem-2 = <0x3a98>;
188 xlnx,tcedv-ps-mem-3 = <0x3a98>;
189 xlnx,thzce-ps-mem-0 = <0x88b8>;
190 xlnx,thzce-ps-mem-1 = <0x1b58>;
191 xlnx,thzce-ps-mem-2 = <0x1b58>;
192 xlnx,thzce-ps-mem-3 = <0x1b58>;
193 xlnx,thzoe-ps-mem-0 = <0x1b58>;
194 xlnx,thzoe-ps-mem-1 = <0x1b58>;
195 xlnx,thzoe-ps-mem-2 = <0x1b58>;
196 xlnx,thzoe-ps-mem-3 = <0x1b58>;
197 xlnx,tlzwe-ps-mem-0 = <0x88b8>;
198 xlnx,tlzwe-ps-mem-1 = <0x0>;
199 xlnx,tlzwe-ps-mem-2 = <0x0>;
200 xlnx,tlzwe-ps-mem-3 = <0x0>;
201 xlnx,twc-ps-mem-0 = <0x2af8>;
202 xlnx,twc-ps-mem-1 = <0x3a98>;
203 xlnx,twc-ps-mem-2 = <0x3a98>;
204 xlnx,twc-ps-mem-3 = <0x3a98>;
205 xlnx,twp-ps-mem-0 = <0x11170>;
206 xlnx,twp-ps-mem-1 = <0x2ee0>;
207 xlnx,twp-ps-mem-2 = <0x2ee0>;
208 xlnx,twp-ps-mem-3 = <0x2ee0>;
209 xlnx,xcl0-linesize = <0x4>;
210 xlnx,xcl0-writexfer = <0x1>;
211 xlnx,xcl1-linesize = <0x4>;
212 xlnx,xcl1-writexfer = <0x1>;
213 xlnx,xcl2-linesize = <0x4>;
214 xlnx,xcl2-writexfer = <0x1>;
215 xlnx,xcl3-linesize = <0x4>;
216 xlnx,xcl3-writexfer = <0x1>;
217 } ;
218 Hard_Ethernet_MAC: xps-ll-temac@81c00000 {
219 #address-cells = <1>;
220 #size-cells = <1>;
221 compatible = "xlnx,compound";
222 ranges ;
223 ethernet@81c00000 {
224 compatible = "xlnx,xps-ll-temac-1.01.b", "xlnx,xps-ll-temac-1.00.a";
225 device_type = "network";
226 interrupt-parent = <&xps_intc_0>;
227 interrupts = < 5 2 >;
228 llink-connected = <&PIM3>;
229 local-mac-address = [ 00 0a 35 00 00 00 ];
230 reg = < 0x81c00000 0x40 >;
231 xlnx,bus2core-clk-ratio = <0x1>;
232 xlnx,phy-type = <0x1>;
233 xlnx,phyaddr = <0x1>;
234 xlnx,rxcsum = <0x0>;
235 xlnx,rxfifo = <0x1000>;
236 xlnx,temac-type = <0x0>;
237 xlnx,txcsum = <0x0>;
238 xlnx,txfifo = <0x1000>;
239 } ;
240 } ;
241 IIC_EEPROM: i2c@81600000 {
242 compatible = "xlnx,xps-iic-2.00.a";
243 interrupt-parent = <&xps_intc_0>;
244 interrupts = < 6 2 >;
245 reg = < 0x81600000 0x10000 >;
246 xlnx,clk-freq = <0x7735940>;
247 xlnx,family = "virtex5";
248 xlnx,gpo-width = <0x1>;
249 xlnx,iic-freq = <0x186a0>;
250 xlnx,scl-inertial-delay = <0x0>;
251 xlnx,sda-inertial-delay = <0x0>;
252 xlnx,ten-bit-adr = <0x0>;
253 } ;
254 LEDs_8Bit: gpio@81400000 {
255 compatible = "xlnx,xps-gpio-1.00.a";
256 interrupt-parent = <&xps_intc_0>;
257 interrupts = < 7 2 >;
258 reg = < 0x81400000 0x10000 >;
259 xlnx,all-inputs = <0x0>;
260 xlnx,all-inputs-2 = <0x0>;
261 xlnx,dout-default = <0x0>;
262 xlnx,dout-default-2 = <0x0>;
263 xlnx,family = "virtex5";
264 xlnx,gpio-width = <0x8>;
265 xlnx,interrupt-present = <0x1>;
266 xlnx,is-bidir = <0x1>;
267 xlnx,is-bidir-2 = <0x1>;
268 xlnx,is-dual = <0x0>;
269 xlnx,tri-default = <0xffffffff>;
270 xlnx,tri-default-2 = <0xffffffff>;
271 #gpio-cells = <2>;
272 gpio-controller;
273 } ;
274
275 gpio-leds {
276 compatible = "gpio-leds";
277
278 heartbeat {
279 label = "Heartbeat";
280 gpios = <&LEDs_8Bit 4 1>;
281 linux,default-trigger = "heartbeat";
282 };
283
284 yellow {
285 label = "Yellow";
286 gpios = <&LEDs_8Bit 5 1>;
287 };
288
289 red {
290 label = "Red";
291 gpios = <&LEDs_8Bit 6 1>;
292 };
293
294 green {
295 label = "Green";
296 gpios = <&LEDs_8Bit 7 1>;
297 };
298 } ;
299 RS232_Uart_1: serial@84000000 {
300 clock-frequency = <125000000>;
301 compatible = "xlnx,xps-uartlite-1.00.a";
302 current-speed = <115200>;
303 device_type = "serial";
304 interrupt-parent = <&xps_intc_0>;
305 interrupts = < 8 0 >;
306 port-number = <0>;
307 reg = < 0x84000000 0x10000 >;
308 xlnx,baudrate = <0x1c200>;
309 xlnx,data-bits = <0x8>;
310 xlnx,family = "virtex5";
311 xlnx,odd-parity = <0x0>;
312 xlnx,use-parity = <0x0>;
313 } ;
314 SysACE_CompactFlash: sysace@83600000 {
315 compatible = "xlnx,xps-sysace-1.00.a";
316 interrupt-parent = <&xps_intc_0>;
317 interrupts = < 4 2 >;
318 reg = < 0x83600000 0x10000 >;
319 xlnx,family = "virtex5";
320 xlnx,mem-width = <0x10>;
321 } ;
322 debug_module: debug@84400000 {
323 compatible = "xlnx,mdm-1.00.d";
324 reg = < 0x84400000 0x10000 >;
325 xlnx,family = "virtex5";
326 xlnx,interconnect = <0x1>;
327 xlnx,jtag-chain = <0x2>;
328 xlnx,mb-dbg-ports = <0x1>;
329 xlnx,uart-width = <0x8>;
330 xlnx,use-uart = <0x1>;
331 xlnx,write-fsl-ports = <0x0>;
332 } ;
333 mpmc@90000000 {
334 #address-cells = <1>;
335 #size-cells = <1>;
336 compatible = "xlnx,mpmc-4.02.a";
337 ranges ;
338 PIM3: sdma@84600180 {
339 compatible = "xlnx,ll-dma-1.00.a";
340 interrupt-parent = <&xps_intc_0>;
341 interrupts = < 2 2 1 2 >;
342 reg = < 0x84600180 0x80 >;
343 } ;
344 } ;
345 xps_intc_0: interrupt-controller@81800000 {
346 #interrupt-cells = <0x2>;
347 compatible = "xlnx,xps-intc-1.00.a";
348 interrupt-controller ;
349 reg = < 0x81800000 0x10000 >;
350 xlnx,kind-of-intr = <0x100>;
351 xlnx,num-intr-inputs = <0x9>;
352 } ;
353 xps_timer_1: timer@83c00000 {
354 compatible = "xlnx,xps-timer-1.00.a";
355 interrupt-parent = <&xps_intc_0>;
356 interrupts = < 3 2 >;
357 reg = < 0x83c00000 0x10000 >;
358 xlnx,count-width = <0x20>;
359 xlnx,family = "virtex5";
360 xlnx,gen0-assert = <0x1>;
361 xlnx,gen1-assert = <0x1>;
362 xlnx,one-timer-only = <0x0>;
363 xlnx,trig0-assert = <0x1>;
364 xlnx,trig1-assert = <0x1>;
365 } ;
366 } ;
367} ;
diff --git a/include/litmus/edf_split_common.h b/include/litmus/edf_split_common.h
new file mode 100644
index 000000000000..4e7c0ce23c9d
--- /dev/null
+++ b/include/litmus/edf_split_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_SPLIT_COMMON_H__
11#define __UNC_EDF_SPLIT_COMMON_H__
12
13#include <litmus/rt_domain.h>
14
15void edf_split_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
16 release_jobs_t release);
17
18int edf_split_higher_prio(struct task_struct* first,
19 struct task_struct* second);
20
21int edf_split_ready_order(struct bheap_node* a, struct bheap_node* b);
22
23int edf_split_preemption_needed(rt_domain_t* rt, struct task_struct *t);
24
25#endif
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index e35c38c4c0a2..8bd9ab2258da 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -69,6 +69,7 @@ void litmus_exit_task(struct task_struct *tsk);
69#define get_deadline(t) (tsk_rt(t)->job_params.deadline) 69#define get_deadline(t) (tsk_rt(t)->job_params.deadline)
70#define get_release(t) (tsk_rt(t)->job_params.release) 70#define get_release(t) (tsk_rt(t)->job_params.release)
71#define get_lateness(t) (tsk_rt(t)->job_params.lateness) 71#define get_lateness(t) (tsk_rt(t)->job_params.lateness)
72#define is_in_crit_section(t) (tsk_rt(t)->in_crit_section)
72 73
73/* release policy macros */ 74/* release policy macros */
74#define is_periodic(t) (get_release_policy(t) == TASK_PERIODIC) 75#define is_periodic(t) (get_release_policy(t) == TASK_PERIODIC)
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 138799fbaad7..65798427d5c3 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -76,6 +76,7 @@ struct rt_task {
76 lt_t period; 76 lt_t period;
77 lt_t relative_deadline; 77 lt_t relative_deadline;
78 lt_t phase; 78 lt_t phase;
79 int split;
79 unsigned int cpu; 80 unsigned int cpu;
80 unsigned int priority; 81 unsigned int priority;
81 task_class_t cls; 82 task_class_t cls;
@@ -143,6 +144,8 @@ struct rt_job {
143 lt_t release; 144 lt_t release;
144 /* What is the current deadline? */ 145 /* What is the current deadline? */
145 lt_t deadline; 146 lt_t deadline;
147 /* What is the dealine of the current subjob under splitting? */
148 lt_t subjob_deadline;
146 149
147 /* How much service has this job received so far? */ 150 /* How much service has this job received so far? */
148 lt_t exec_time; 151 lt_t exec_time;
@@ -191,7 +194,6 @@ struct rt_param {
191 unsigned int priority_boosted:1; 194 unsigned int priority_boosted:1;
192 /* If so, when did this start? */ 195 /* If so, when did this start? */
193 lt_t boost_start_time; 196 lt_t boost_start_time;
194
195 /* How many LITMUS^RT locks does the task currently hold/wait for? */ 197 /* How many LITMUS^RT locks does the task currently hold/wait for? */
196 unsigned int num_locks_held; 198 unsigned int num_locks_held;
197 /* How many PCP/SRP locks does the task currently hold/wait for? */ 199 /* How many PCP/SRP locks does the task currently hold/wait for? */
diff --git a/litmus/Makefile b/litmus/Makefile
index 2bddc94a399f..8f3b8b4c3342 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -11,6 +11,7 @@ obj-y = sched_plugin.o litmus.o \
11 sync.o \ 11 sync.o \
12 rt_domain.o \ 12 rt_domain.o \
13 edf_common.o \ 13 edf_common.o \
14 edf_split_common.o \
14 fp_common.o \ 15 fp_common.o \
15 fdso.o \ 16 fdso.o \
16 locking.o \ 17 locking.o \
@@ -21,7 +22,8 @@ obj-y = sched_plugin.o litmus.o \
21 uncachedev.o \ 22 uncachedev.o \
22 sched_gsn_edf.o \ 23 sched_gsn_edf.o \
23 sched_psn_edf.o \ 24 sched_psn_edf.o \
24 sched_pfp.o 25 sched_pfp.o \
26 sched_cfl_split.o
25 27
26obj-$(CONFIG_PLUGIN_CEDF) += sched_cedf.o 28obj-$(CONFIG_PLUGIN_CEDF) += sched_cedf.o
27obj-$(CONFIG_PLUGIN_PFAIR) += sched_pfair.o 29obj-$(CONFIG_PLUGIN_PFAIR) += sched_pfair.o
diff --git a/litmus/edf_split_common.c b/litmus/edf_split_common.c
new file mode 100644
index 000000000000..76b100c9c5b9
--- /dev/null
+++ b/litmus/edf_split_common.c
@@ -0,0 +1,171 @@
1/*
2 * kernel/edf_split_common.c
3 *
4 * Common functions for EDF based scheduler with split jobs.
5 */
6
7#include <linux/percpu.h>
8#include <linux/sched.h>
9#include <linux/list.h>
10
11#include <litmus/litmus.h>
12#include <litmus/sched_plugin.h>
13#include <litmus/sched_trace.h>
14
15#include <litmus/edf_split_common.h>
16
17#ifdef CONFIG_EDF_TIE_BREAK_LATENESS_NORM
18#include <litmus/fpmath.h>
19#endif
20
21#ifdef CONFIG_EDF_TIE_BREAK_HASH
22#include <linux/hash.h>
23static inline long edf_split_hash(struct task_struct *t)
24{
25 /* pid is 32 bits, so normally we would shove that into the
26 * upper 32-bits and and put the job number in the bottom
27 * and hash the 64-bit number with hash_64(). Sadly,
28 * in testing, hash_64() doesn't distribute keys were the
29 * upper bits are close together (as would be the case with
30 * pids) and job numbers are equal (as would be the case with
31 * synchronous task sets with all relative deadlines equal).
32 *
33 * A 2006 Linux patch proposed the following solution
34 * (but for some reason it wasn't accepted...).
35 *
36 * At least this workaround works for 32-bit systems as well.
37 */
38 return hash_32(hash_32((u32)tsk_rt(t)->job_params.job_no, 32) ^ t->pid, 32);
39}
40#endif
41
42/* edf_higher_prio - returns true if first has a higher EDF priority
43 * than second. Deadline ties are broken by PID.
44 *
45 * both first and second may be NULL
46 */
47int edf_split_higher_prio(struct task_struct* first,
48 struct task_struct* second)
49{
50 struct task_struct *first_task = first;
51 struct task_struct *second_task = second;
52
53 /* There is no point in comparing a task to itself. */
54 if (first && first == second) {
55 TRACE_TASK(first,
56 "WARNING: pointless edf priority comparison.\n");
57 return 0;
58 }
59
60
61 /* check for NULL tasks */
62 if (!first || !second)
63 return first && !second;
64
65 if (earlier_deadline(first_task, second_task)) {
66 return 1;
67 }
68 else if (get_deadline(first_task) == get_deadline(second_task)) {
69 /* Need to tie break. All methods must set pid_break to 0/1 if
70 * first_task does not have priority over second_task.
71 */
72 int pid_break;
73
74#if defined(CONFIG_EDF_TIE_BREAK_LATENESS)
75 /* Tie break by lateness. Jobs with greater lateness get
76 * priority. This should spread tardiness across all tasks,
77 * especially in task sets where all tasks have the same
78 * period and relative deadlines.
79 */
80 if (get_lateness(first_task) > get_lateness(second_task)) {
81 return 1;
82 }
83 pid_break = (get_lateness(first_task) == get_lateness(second_task));
84
85
86#elif defined(CONFIG_EDF_TIE_BREAK_LATENESS_NORM)
87 /* Tie break by lateness, normalized by relative deadline. Jobs with
88 * greater normalized lateness get priority.
89 *
90 * Note: Considered using the algebraically equivalent
91 * lateness(first)*relative_deadline(second) >
92 lateness(second)*relative_deadline(first)
93 * to avoid fixed-point math, but values are prone to overflow if inputs
94 * are on the order of several seconds, even in 64-bit.
95 */
96 fp_t fnorm = _frac(get_lateness(first_task),
97 get_rt_relative_deadline(first_task));
98 fp_t snorm = _frac(get_lateness(second_task),
99 get_rt_relative_deadline(second_task));
100 if (_gt(fnorm, snorm)) {
101 return 1;
102 }
103 pid_break = _eq(fnorm, snorm);
104
105#elif defined(CONFIG_EDF_TIE_BREAK_HASH)
106 /* Tie break by comparing hashs of (pid, job#) tuple. There should be
107 * a 50% chance that first_task has a higher priority than second_task.
108 */
109 long fhash = edf_hash(first_task);
110 long shash = edf_hash(second_task);
111 if (fhash < shash) {
112 return 1;
113 }
114 pid_break = (fhash == shash);
115#else
116
117
118 /* CONFIG_EDF_PID_TIE_BREAK */
119 pid_break = 1; // fall through to tie-break by pid;
120#endif
121
122 /* Tie break by pid */
123 if(pid_break) {
124 if (first_task->pid < second_task->pid) {
125 return 1;
126 }
127 else if (first_task->pid == second_task->pid) {
128 /* If the PIDs are the same then the task with the
129 * inherited priority wins.
130 */
131 if (!second->rt_param.inh_task) {
132 return 1;
133 }
134 }
135 }
136 }
137 return 0; /* fall-through. prio(second_task) > prio(first_task) */
138}
139
140int edf_split_ready_order(struct bheap_node* a, struct bheap_node* b)
141{
142 return edf_split_higher_prio(bheap2task(a), bheap2task(b));
143}
144
145void edf_split_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
146 release_jobs_t release)
147{
148 rt_domain_init(rt, edf_split_ready_order, resched, release);
149}
150
151/* need_to_preempt - check whether the task t needs to be preempted
152 * call only with irqs disabled and with ready_lock acquired
153 * THIS DOES NOT TAKE NON-PREEMPTIVE SECTIONS INTO ACCOUNT!
154 */
155int edf_split_preemption_needed(rt_domain_t* rt, struct task_struct *t)
156{
157 /* we need the read lock for edf_ready_queue */
158 /* no need to preempt if there is nothing pending */
159 if (!__jobs_pending(rt))
160 return 0;
161 /* we need to reschedule if t doesn't exist */
162 if (!t)
163 return 1;
164
165 /* NOTE: We cannot check for non-preemptibility since we
166 * don't know what address space we're currently in.
167 */
168
169 /* make sure to get non-rt stuff out of the way */
170 return !is_realtime(t) || edf_split_higher_prio(__next_ready(rt), t);
171}
diff --git a/litmus/sched_cfl_split.c b/litmus/sched_cfl_split.c
new file mode 100644
index 000000000000..37180e82bb4b
--- /dev/null
+++ b/litmus/sched_cfl_split.c
@@ -0,0 +1,1006 @@
1/*
2 * litmus/sched_cfl_split.c
3 *
4 * Implementation of a clustered version of the G-FL scheduling algorithm,
5 * with job splitting.
6 *
7 * This implementation is based on G-FL-split:
8 * - CPUs are clustered around L2 or L3 caches.
9 * - Clusters topology is automatically detected (this is arch dependent
10 * and is working only on x86 at the moment --- and only with modern
11 * cpus that exports cpuid4 information)
12 * - The plugins _does not_ attempt to put tasks in the right cluster i.e.
13 * the programmer needs to be aware of the topology to place tasks
14 * in the desired cluster
15 * - default clustering is around L2 cache (cache index = 2)
16 * supported clusters are: L1 (private cache: pedf), L2, L3, ALL (all
17 * online_cpus are placed in a single cluster).
18 *
19 * For details on functions, take a look at sched_gsn_edf.c
20 *
21 * Currently, we do not support changes in the number of online cpus.
22 * If the num_online_cpus() dynamically changes, the plugin is broken.
23 *
24 * This version uses the simple approach and serializes all scheduling
25 * decisions by the use of a queue lock. This is probably not the
26 * best way to do it, but it should suffice for now.
27 */
28
29#include <linux/spinlock.h>
30#include <linux/percpu.h>
31#include <linux/sched.h>
32#include <linux/slab.h>
33
34#include <linux/module.h>
35
36#include <litmus/litmus.h>
37#include <litmus/budget.h>
38#include <litmus/jobs.h>
39#include <litmus/preempt.h>
40#include <litmus/sched_plugin.h>
41#include <litmus/edf_split_common.h>
42#include <litmus/sched_trace.h>
43
44#include <litmus/clustered.h>
45
46#include <litmus/bheap.h>
47
48#ifdef CONFIG_SCHED_CPU_AFFINITY
49#include <litmus/affinity.h>
50#endif
51
52/* to configure the cluster size */
53#include <litmus/litmus_proc.h>
54#include <linux/uaccess.h>
55
56/* Reference configuration variable. Determines which cache level is used to
57 * group CPUs into clusters. GLOBAL_CLUSTER, which is the default, means that
58 * all CPUs form a single cluster (just like G-FL).
59 */
60static enum cache_level cluster_config = GLOBAL_CLUSTER;
61
62struct clusterdomain;
63
64/* cpu_entry_t - maintain the linked and scheduled state
65 *
66 * A cpu also contains a pointer to the cflsplit_domain_t cluster
67 * that owns it (struct clusterdomain*)
68 */
69typedef struct {
70 int cpu;
71 struct clusterdomain* cluster; /* owning cluster */
72 struct task_struct* linked; /* only RT tasks */
73 struct task_struct* scheduled; /* only RT tasks */
74 atomic_t will_schedule; /* prevent unneeded IPIs */
75 struct bheap_node* hn;
76 struct hrtimer split_timer;
77 int timer_armed;
78} cpu_entry_t;
79
80/* one cpu_entry_t per CPU */
81DEFINE_PER_CPU(cpu_entry_t, cflsplit_cpu_entries);
82
83#define set_will_schedule() \
84 (atomic_set(&__get_cpu_var(cflsplit_cpu_entries).will_schedule, 1))
85#define clear_will_schedule() \
86 (atomic_set(&__get_cpu_var(cflsplit_cpu_entries).will_schedule, 0))
87#define test_will_schedule(cpu) \
88 (atomic_read(&per_cpu(cflsplit_cpu_entries, cpu).will_schedule))
89
90/*
91 * In C-FL-split there is a cflsplit domain _per_ cluster
92 * The number of clusters is dynamically determined accordingly to the
93 * total cpu number and the cluster size
94 */
95typedef struct clusterdomain {
96 /* rt_domain for this cluster */
97 rt_domain_t domain;
98 /* cpus in this cluster */
99 cpu_entry_t* *cpus;
100 /* map of this cluster cpus */
101 cpumask_var_t cpu_map;
102 /* the cpus queue themselves according to priority in here */
103 struct bheap_node *heap_node;
104 struct bheap cpu_heap;
105 /* lock for this cluster */
106#define cluster_lock domain.ready_lock
107} cflsplit_domain_t;
108
109/* a cflsplit_domain per cluster; allocation is done at init/activation time */
110cflsplit_domain_t *cflsplit;
111
112#define remote_cluster(cpu) ((cflsplit_domain_t *) per_cpu(cflsplit_cpu_entries, cpu).cluster)
113#define task_cpu_cluster(task) remote_cluster(get_partition(task))
114
115/* Uncomment WANT_ALL_SCHED_EVENTS if you want to see all scheduling
116 * decisions in the TRACE() log; uncomment VERBOSE_INIT for verbose
117 * information during the initialization of the plugin (e.g., topology)
118#define WANT_ALL_SCHED_EVENTS
119 */
120#define VERBOSE_INIT
121
122inline static int get_slice_num(struct task_struct* t)
123{
124 int basic = ((t->rt_param.job_params.exec_time *
125 t->rt_param.task_params.split) /
126 t->rt_param.task_params.exec_cost) + 1;
127 if (basic <= t->rt_param.task_params.split){
128 return basic;
129 }
130 else{
131 /*Since we don't police budget, just leave where it's at.*/
132 return t->rt_param.task_params.split;
133 }
134}
135
136/* Returns the appropriate subjob deadline.*/
137inline static lt_t get_proper_deadline(struct task_struct* t)
138{
139 unsigned int num_cpus = num_online_cpus();
140 return t->rt_param.job_params.release +
141 ((t->rt_param.task_params.period * get_slice_num(t))
142 / t->rt_param.task_params.split)
143 /* G-FL correction */
144 - (((num_cpus - 1) * t->rt_param.task_params.exec_cost)
145 / (num_cpus * t->rt_param.task_params.split));
146}
147
148/* Tells us if the current deadline is too small.*/
149inline static int needs_deadline_move(struct task_struct* t)
150{
151 BUG_ON(get_proper_deadline(t) < t->rt_param.job_params.subjob_deadline);
152 return get_proper_deadline(t) != tsk_rt(t)->job_params.subjob_deadline;
153}
154
155/*Returns execution time until the next deadline move.
156 * 0 means the task has no more deadline moves
157 */
158inline static lt_t time_to_next_move(struct task_struct* t)
159{
160 if (get_slice_num(t) == t->rt_param.task_params.split){
161 return 0;
162 }
163 /* +1 upper bounds ceiling, since integer division is floor*/
164 return ((get_slice_num(t) * t->rt_param.task_params.exec_cost)
165 / t->rt_param.task_params.split) + 1
166 - t->rt_param.job_params.exec_time;
167}
168
169/* Timer stuff - similar to budget.c. */
170static enum hrtimer_restart on_split_timeout(struct hrtimer *timer)
171{
172 cpu_entry_t* st = container_of(timer,
173 cpu_entry_t,
174 split_timer);
175
176 unsigned long flags;
177
178 local_irq_save(flags);
179 TRACE("split timer fired.\n");
180 st->timer_armed = 0;
181 /* Activate scheduler */
182 litmus_reschedule_local();
183 local_irq_restore(flags);
184
185 return HRTIMER_NORESTART;
186}
187
188static void cancel_split_timer(cpu_entry_t* ce)
189{
190 int ret;
191
192 TRACE("cancelling split time.\n");
193
194 /* Since interrupts are disabled and et->timer_armed is only
195 * modified locally, we do not need any locks.
196 */
197
198 if (ce->timer_armed) {
199 ret = hrtimer_try_to_cancel(&ce->split_timer);
200 /* Should never be inactive. */
201 BUG_ON(ret == 0);
202 /* Should never be running concurrently.*/
203 BUG_ON(ret == -1);
204
205 ce->timer_armed = 0;
206 }
207}
208
209/* assumes called with IRQs off */
210static void arm_split_timer(cpu_entry_t *ce,
211 struct task_struct* t)
212{
213 lt_t when_to_fire;
214 lt_t time_to_move;
215 TRACE_TASK(t, "arming split timer.\n");
216
217 /* __hrtimer_start_range_ns() cancels the timer
218 * anyway, so we don't have to check whether it is still armed */
219
220 /*We won't do any new deadline moves if the budget has been exhausted*/
221 if (likely(!is_np(t) && (time_to_move = time_to_next_move(t)))) {
222 when_to_fire = litmus_clock() + time_to_move;
223 TRACE_TASK(t, "actually arming for %llu into the future\n",
224 time_to_move);
225 __hrtimer_start_range_ns(&ce->split_timer,
226 ns_to_ktime(when_to_fire),
227 0 /* delta */,
228 HRTIMER_MODE_ABS_PINNED,
229 0 /* no wakeup */);
230 ce->timer_armed = 1;
231 }
232}
233
234static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b)
235{
236 cpu_entry_t *a, *b;
237 a = _a->value;
238 b = _b->value;
239 /* Note that a and b are inverted: we want the lowest-priority CPU at
240 * the top of the heap.
241 */
242 return edf_split_higher_prio(b->linked, a->linked);
243}
244
245/* update_cpu_position - Move the cpu entry to the correct place to maintain
246 * order in the cpu queue. Caller must hold cflsplit lock.
247 */
248static void update_cpu_position(cpu_entry_t *entry)
249{
250 cflsplit_domain_t *cluster = entry->cluster;
251
252 if (likely(bheap_node_in_heap(entry->hn)))
253 bheap_delete(cpu_lower_prio,
254 &cluster->cpu_heap,
255 entry->hn);
256
257 bheap_insert(cpu_lower_prio, &cluster->cpu_heap, entry->hn);
258}
259
260/* caller must hold cflsplit lock */
261static cpu_entry_t* lowest_prio_cpu(cflsplit_domain_t *cluster)
262{
263 struct bheap_node* hn;
264 hn = bheap_peek(cpu_lower_prio, &cluster->cpu_heap);
265 return hn->value;
266}
267
268
269/* link_task_to_cpu - Update the link of a CPU.
270 * Handles the case where the to-be-linked task is already
271 * scheduled on a different CPU.
272 */
273static noinline void link_task_to_cpu(struct task_struct* linked,
274 cpu_entry_t *entry)
275{
276 cpu_entry_t *sched;
277 struct task_struct* tmp;
278 int on_cpu;
279
280 BUG_ON(linked && !is_realtime(linked));
281
282 /* Currently linked task is set to be unlinked. */
283 if (entry->linked) {
284 entry->linked->rt_param.linked_on = NO_CPU;
285 }
286
287 /* Link new task to CPU. */
288 if (linked) {
289 /* handle task is already scheduled somewhere! */
290 on_cpu = linked->rt_param.scheduled_on;
291 if (on_cpu != NO_CPU) {
292 sched = &per_cpu(cflsplit_cpu_entries, on_cpu);
293 /* this should only happen if not linked already */
294 BUG_ON(sched->linked == linked);
295
296 /* If we are already scheduled on the CPU to which we
297 * wanted to link, we don't need to do the swap --
298 * we just link ourselves to the CPU and depend on
299 * the caller to get things right.
300 */
301 if (entry != sched) {
302 TRACE_TASK(linked,
303 "already scheduled on %d, updating link.\n",
304 sched->cpu);
305 tmp = sched->linked;
306 linked->rt_param.linked_on = sched->cpu;
307 sched->linked = linked;
308 update_cpu_position(sched);
309 linked = tmp;
310 }
311 }
312 if (linked) /* might be NULL due to swap */
313 linked->rt_param.linked_on = entry->cpu;
314 }
315 entry->linked = linked;
316#ifdef WANT_ALL_SCHED_EVENTS
317 if (linked)
318 TRACE_TASK(linked, "linked to %d.\n", entry->cpu);
319 else
320 TRACE("NULL linked to %d.\n", entry->cpu);
321#endif
322 update_cpu_position(entry);
323}
324
325/* unlink - Make sure a task is not linked any longer to an entry
326 * where it was linked before. Must hold cflsplit_lock.
327 */
328static noinline void unlink(struct task_struct* t)
329{
330 cpu_entry_t *entry;
331
332 if (t->rt_param.linked_on != NO_CPU) {
333 /* unlink */
334 entry = &per_cpu(cflsplit_cpu_entries, t->rt_param.linked_on);
335 t->rt_param.linked_on = NO_CPU;
336 link_task_to_cpu(NULL, entry);
337 } else if (is_queued(t)) {
338 /* This is an interesting situation: t is scheduled,
339 * but was just recently unlinked. It cannot be
340 * linked anywhere else (because then it would have
341 * been relinked to this CPU), thus it must be in some
342 * queue. We must remove it from the list in this
343 * case.
344 *
345 * in C-FL-split case is should be somewhere in the queue for
346 * its domain, therefore and we can get the domain using
347 * task_cpu_cluster
348 */
349 remove(&(task_cpu_cluster(t))->domain, t);
350 }
351}
352
353
354/* preempt - force a CPU to reschedule
355 */
356static void preempt(cpu_entry_t *entry)
357{
358 preempt_if_preemptable(entry->scheduled, entry->cpu);
359}
360
361/* requeue - Put an unlinked task into gsn-edf domain.
362 * Caller must hold cflsplit_lock.
363 */
364static noinline void requeue(struct task_struct* task)
365{
366 cflsplit_domain_t *cluster = task_cpu_cluster(task);
367 BUG_ON(!task);
368 /* sanity check before insertion */
369 BUG_ON(is_queued(task));
370
371 if (is_early_releasing(task) || is_released(task, litmus_clock()))
372 __add_ready(&cluster->domain, task);
373 else {
374 /* it has got to wait */
375 add_release(&cluster->domain, task);
376 }
377}
378
379#ifdef CONFIG_SCHED_CPU_AFFINITY
380static cpu_entry_t* cflsplit_get_nearest_available_cpu(
381 cflsplit_domain_t *cluster, cpu_entry_t *start)
382{
383 cpu_entry_t *affinity;
384
385 get_nearest_available_cpu(affinity, start, cflsplit_cpu_entries,
386#ifdef CONFIG_RELEASE_MASTER
387 cluster->domain.release_master
388#else
389 NO_CPU
390#endif
391 );
392
393 /* make sure CPU is in our cluster */
394 if (affinity && cpu_isset(affinity->cpu, *cluster->cpu_map))
395 return(affinity);
396 else
397 return(NULL);
398}
399#endif
400
401
402/* check for any necessary preemptions */
403static void check_for_preemptions(cflsplit_domain_t *cluster)
404{
405 struct task_struct *task;
406 cpu_entry_t *last;
407
408 for(last = lowest_prio_cpu(cluster);
409 edf_split_preemption_needed(&cluster->domain, last->linked);
410 last = lowest_prio_cpu(cluster)) {
411 /* preemption necessary */
412 task = __take_ready(&cluster->domain);
413 TRACE("check_for_preemptions: attempting to link task %d to %d\n",
414 task->pid, last->cpu);
415#ifdef CONFIG_SCHED_CPU_AFFINITY
416 {
417 cpu_entry_t *affinity =
418 cflsplit_get_nearest_available_cpu(cluster,
419 &per_cpu(cflsplit_cpu_entries, task_cpu(task)));
420 if(affinity)
421 last = affinity;
422 else if(requeue_preempted_job(last->linked))
423 requeue(last->linked);
424 }
425#else
426 if (requeue_preempted_job(last->linked))
427 requeue(last->linked);
428#endif
429 link_task_to_cpu(task, last);
430 preempt(last);
431 }
432}
433
434/* cflsplit_job_arrival: task is either resumed or released */
435static noinline void cflsplit_job_arrival(struct task_struct* task)
436{
437 cflsplit_domain_t *cluster = task_cpu_cluster(task);
438 BUG_ON(!task);
439
440 requeue(task);
441 check_for_preemptions(cluster);
442}
443
444static void cflsplit_release_jobs(rt_domain_t* rt, struct bheap* tasks)
445{
446 cflsplit_domain_t* cluster = container_of(rt, cflsplit_domain_t, domain);
447 unsigned long flags;
448
449 raw_spin_lock_irqsave(&cluster->cluster_lock, flags);
450
451 __merge_ready(&cluster->domain, tasks);
452 check_for_preemptions(cluster);
453
454 raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags);
455}
456
457/* caller holds cflsplit_lock */
458static noinline void job_completion(struct task_struct *t, int forced)
459{
460 BUG_ON(!t);
461
462 sched_trace_task_completion(t, forced);
463
464 TRACE_TASK(t, "job_completion().\n");
465
466 /* set flags */
467 tsk_rt(t)->completed = 0;
468 /* prepare for next period */
469 prepare_for_next_period(t);
470 /* We now also set the subjob deadline to what it should be for
471 * scheduling priority.
472 */
473 t->rt_param.job_params.subjob_deadline = get_proper_deadline(t);
474 if (is_early_releasing(t) || is_released(t, litmus_clock()))
475 sched_trace_task_release(t);
476 /* unlink */
477 unlink(t);
478 /* requeue
479 * But don't requeue a blocking task. */
480 if (is_running(t))
481 cflsplit_job_arrival(t);
482}
483
484static void move_deadline(struct task_struct *t)
485{
486 tsk_rt(t)->job_params.subjob_deadline = get_proper_deadline(t);
487 /* Check if rescheduling needed with lower priority. */
488 unlink(t);
489 cflsplit_job_arrival(t);
490}
491
492/* cflsplit_tick - this function is called for every local timer
493 * interrupt.
494 *
495 * checks whether the current task has expired and checks
496 * whether we need to preempt it if it has not expired
497 */
498static void cflsplit_tick(struct task_struct* t)
499{
500 if (is_realtime(t) && budget_enforced(t) && budget_exhausted(t)) {
501 if (!is_np(t)) {
502 /* np tasks will be preempted when they become
503 * preemptable again
504 */
505 litmus_reschedule_local();
506 set_will_schedule();
507 TRACE("cflsplit_scheduler_tick: "
508 "%d is preemptable "
509 " => FORCE_RESCHED\n", t->pid);
510 } else if (is_user_np(t)) {
511 TRACE("cflsplit_scheduler_tick: "
512 "%d is non-preemptable, "
513 "preemption delayed.\n", t->pid);
514 request_exit_np(t);
515 }
516 }
517}
518
519/* Getting schedule() right is a bit tricky. schedule() may not make any
520 * assumptions on the state of the current task since it may be called for a
521 * number of reasons. The reasons include a scheduler_tick() determined that it
522 * was necessary, because sys_exit_np() was called, because some Linux
523 * subsystem determined so, or even (in the worst case) because there is a bug
524 * hidden somewhere. Thus, we must take extreme care to determine what the
525 * current state is.
526 *
527 * The CPU could currently be scheduling a task (or not), be linked (or not).
528 *
529 * The following assertions for the scheduled task could hold:
530 *
531 * - !is_running(scheduled) // the job blocks
532 * - scheduled->timeslice == 0 // the job completed (forcefully)
533 * - is_completed() // the job completed (by syscall)
534 * - linked != scheduled // we need to reschedule (for any reason)
535 * - is_np(scheduled) // rescheduling must be delayed,
536 * sys_exit_np must be requested
537 *
538 * Any of these can occur together.
539 */
540static struct task_struct* cflsplit_schedule(struct task_struct * prev)
541{
542 cpu_entry_t* entry = &__get_cpu_var(cflsplit_cpu_entries);
543 cflsplit_domain_t *cluster = entry->cluster;
544 int out_of_time, sleep, preempt, np, exists, blocks, needs_move;
545 struct task_struct* next = NULL;
546
547#ifdef CONFIG_RELEASE_MASTER
548 /* Bail out early if we are the release master.
549 * The release master never schedules any real-time tasks.
550 */
551 if (unlikely(cluster->domain.release_master == entry->cpu)) {
552 sched_state_task_picked();
553 return NULL;
554 }
555#endif
556
557 raw_spin_lock(&cluster->cluster_lock);
558 clear_will_schedule();
559
560 /* sanity checking */
561 BUG_ON(entry->scheduled && entry->scheduled != prev);
562 BUG_ON(entry->scheduled && !is_realtime(prev));
563 BUG_ON(is_realtime(prev) && !entry->scheduled);
564
565 /* (0) Determine state */
566 exists = entry->scheduled != NULL;
567 blocks = exists && !is_running(entry->scheduled);
568 out_of_time = exists &&
569 budget_enforced(entry->scheduled) &&
570 budget_exhausted(entry->scheduled);
571 needs_move = exists && needs_deadline_move(entry->scheduled);
572 np = exists && is_np(entry->scheduled);
573 sleep = exists && is_completed(entry->scheduled);
574 preempt = entry->scheduled != entry->linked;
575
576#ifdef WANT_ALL_SCHED_EVENTS
577 TRACE_TASK(prev, "invoked cflsplit_schedule.\n");
578#endif
579
580 if (exists)
581 TRACE_TASK(prev,
582 "blocks:%d out_of_time:%d needs_move: %d np:%d"
583 " sleep:%d preempt:%d state:%d sig:%d\n",
584 blocks, out_of_time, needs_move, np, sleep, preempt,
585 prev->state, signal_pending(prev));
586 if (entry->linked && preempt)
587 TRACE_TASK(prev, "will be preempted by %s/%d\n",
588 entry->linked->comm, entry->linked->pid);
589
590
591 /* If a task blocks we have no choice but to reschedule.
592 */
593 if (blocks)
594 unlink(entry->scheduled);
595
596 /* Request a sys_exit_np() call if we would like to preempt but cannot.
597 * We need to make sure to update the link structure anyway in case
598 * that we are still linked. Multiple calls to request_exit_np() don't
599 * hurt.
600 *
601 * Job deadline moves handled similarly
602 */
603 if (np && (out_of_time || preempt || sleep)) {
604 unlink(entry->scheduled);
605 request_exit_np(entry->scheduled);
606 }
607 else if (np && needs_move) {
608 request_exit_np(entry->scheduled);
609 }
610
611 /* Any task that is preemptable and either exhausts its execution
612 * budget or wants to sleep completes. We may have to reschedule after
613 * this. Don't do a job completion if we block (can't have timers running
614 * for blocked jobs). Preemption go first for the same reason.
615 */
616 if (!np && (out_of_time || sleep) && !blocks)
617 job_completion(entry->scheduled, !sleep);
618 else if (!np && needs_move && !blocks) {
619 move_deadline(entry->scheduled);
620 }
621
622 /* Link pending task if we became unlinked.
623 */
624 if (!entry->linked)
625 link_task_to_cpu(__take_ready(&cluster->domain), entry);
626
627 /* The final scheduling decision. Do we need to switch for some reason?
628 * If linked is different from scheduled, then select linked as next.
629 */
630 if ((!np || blocks) &&
631 entry->linked != entry->scheduled) {
632 /* Schedule a linked job? */
633 if (entry->linked) {
634 entry->linked->rt_param.scheduled_on = entry->cpu;
635 next = entry->linked;
636 }
637 if (entry->scheduled) {
638 /* not gonna be scheduled soon */
639 entry->scheduled->rt_param.scheduled_on = NO_CPU;
640 TRACE_TASK(entry->scheduled, "scheduled_on = NO_CPU\n");
641 }
642 } else
643 /* Only override Linux scheduler if we have a real-time task
644 * scheduled that needs to continue.
645 */
646 if (exists)
647 next = prev;
648
649 sched_state_task_picked();
650 raw_spin_unlock(&cluster->cluster_lock);
651
652 if (next) {
653 arm_split_timer(entry, next);
654 }
655 else if (entry->timer_armed) {
656 cancel_split_timer(entry);
657 }
658
659#ifdef WANT_ALL_SCHED_EVENTS
660 TRACE("cflsplit_lock released, next=0x%p\n", next);
661
662 if (next)
663 TRACE_TASK(next, "scheduled at %llu\n", litmus_clock());
664 else if (exists && !next)
665 TRACE("becomes idle at %llu.\n", litmus_clock());
666#endif
667
668
669 return next;
670}
671
672
673/* _finish_switch - we just finished the switch away from prev
674 */
675static void cflsplit_finish_switch(struct task_struct *prev)
676{
677 cpu_entry_t* entry = &__get_cpu_var(cflsplit_cpu_entries);
678
679 entry->scheduled = is_realtime(current) ? current : NULL;
680#ifdef WANT_ALL_SCHED_EVENTS
681 TRACE_TASK(prev, "switched away from\n");
682#endif
683}
684
685
686static void cflsplit_release_at(struct task_struct *t, lt_t start)
687{
688 release_at(t, start);
689 t->rt_param.job_params.subjob_deadline = get_proper_deadline(t);
690}
691
692
693/* Prepare a task for running in RT mode
694 */
695static void cflsplit_task_new(struct task_struct * t, int on_rq, int is_scheduled)
696{
697 unsigned long flags;
698 cpu_entry_t* entry;
699 cflsplit_domain_t* cluster;
700
701 TRACE("gsn edf: task new %d\n", t->pid);
702
703 /* the cluster doesn't change even if t is scheduled */
704 cluster = task_cpu_cluster(t);
705
706 raw_spin_lock_irqsave(&cluster->cluster_lock, flags);
707
708 /* setup job params */
709 cflsplit_release_at(t, litmus_clock());
710
711 if (is_scheduled) {
712 entry = &per_cpu(cflsplit_cpu_entries, task_cpu(t));
713 BUG_ON(entry->scheduled);
714
715#ifdef CONFIG_RELEASE_MASTER
716 if (entry->cpu != cluster->domain.release_master) {
717#endif
718 entry->scheduled = t;
719 tsk_rt(t)->scheduled_on = task_cpu(t);
720#ifdef CONFIG_RELEASE_MASTER
721 } else {
722 /* do not schedule on release master */
723 preempt(entry); /* force resched */
724 tsk_rt(t)->scheduled_on = NO_CPU;
725 }
726#endif
727 } else {
728 t->rt_param.scheduled_on = NO_CPU;
729 }
730 t->rt_param.linked_on = NO_CPU;
731
732 if (is_running(t))
733 cflsplit_job_arrival(t);
734 raw_spin_unlock_irqrestore(&(cluster->cluster_lock), flags);
735}
736
737static void cflsplit_task_wake_up(struct task_struct *task)
738{
739 unsigned long flags;
740 lt_t now;
741 cflsplit_domain_t *cluster;
742
743 TRACE_TASK(task, "wake_up at %llu\n", litmus_clock());
744
745 cluster = task_cpu_cluster(task);
746
747 raw_spin_lock_irqsave(&cluster->cluster_lock, flags);
748 now = litmus_clock();
749 if (is_sporadic(task) && is_tardy(task, now)) {
750 /* new sporadic release */
751 cflsplit_release_at(task, now);
752 sched_trace_task_release(task);
753 }
754 cflsplit_job_arrival(task);
755 raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags);
756}
757
758static void cflsplit_task_block(struct task_struct *t)
759{
760 unsigned long flags;
761 cflsplit_domain_t *cluster;
762
763 TRACE_TASK(t, "block at %llu\n", litmus_clock());
764
765 cluster = task_cpu_cluster(t);
766
767 /* unlink if necessary */
768 raw_spin_lock_irqsave(&cluster->cluster_lock, flags);
769 unlink(t);
770 raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags);
771
772 BUG_ON(!is_realtime(t));
773}
774
775
776static void cflsplit_task_exit(struct task_struct * t)
777{
778 unsigned long flags;
779 cflsplit_domain_t *cluster = task_cpu_cluster(t);
780
781 /* unlink if necessary */
782 raw_spin_lock_irqsave(&cluster->cluster_lock, flags);
783 unlink(t);
784 if (tsk_rt(t)->scheduled_on != NO_CPU) {
785 cpu_entry_t *cpu;
786 cpu = &per_cpu(cflsplit_cpu_entries, tsk_rt(t)->scheduled_on);
787 cpu->scheduled = NULL;
788 tsk_rt(t)->scheduled_on = NO_CPU;
789 }
790 raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags);
791
792 BUG_ON(!is_realtime(t));
793 TRACE_TASK(t, "RIP\n");
794}
795
796static long cflsplit_admit_task(struct task_struct* tsk)
797{
798 return (remote_cluster(task_cpu(tsk)) == task_cpu_cluster(tsk)) ?
799 0 : -EINVAL;
800}
801
802/* total number of cluster */
803static int num_clusters;
804/* we do not support cluster of different sizes */
805static unsigned int cluster_size;
806
807#ifdef VERBOSE_INIT
808static void print_cluster_topology(cpumask_var_t mask, int cpu)
809{
810 int chk;
811 char buf[255];
812
813 chk = cpulist_scnprintf(buf, 254, mask);
814 buf[chk] = '\0';
815 printk(KERN_INFO "CPU = %d, shared cpu(s) = %s\n", cpu, buf);
816
817}
818#endif
819
820static int clusters_allocated = 0;
821
822static void cleanup_cflsplit(void)
823{
824 int i;
825
826 if (clusters_allocated) {
827 for (i = 0; i < num_clusters; i++) {
828 kfree(cflsplit[i].cpus);
829 kfree(cflsplit[i].heap_node);
830 free_cpumask_var(cflsplit[i].cpu_map);
831 }
832
833 kfree(cflsplit);
834 }
835}
836
837static long cflsplit_activate_plugin(void)
838{
839 int i, j, cpu, ccpu, cpu_count;
840 cpu_entry_t *entry;
841
842 cpumask_var_t mask;
843 int chk = 0;
844
845 /* de-allocate old clusters, if any */
846 cleanup_cflsplit();
847
848 printk(KERN_INFO "C-FL-split: Activate Plugin, cluster configuration = %d\n",
849 cluster_config);
850
851 /* need to get cluster_size first */
852 if(!zalloc_cpumask_var(&mask, GFP_ATOMIC))
853 return -ENOMEM;
854
855 if (unlikely(cluster_config == GLOBAL_CLUSTER)) {
856 cluster_size = num_online_cpus();
857 } else {
858 chk = get_shared_cpu_map(mask, 0, cluster_config);
859 if (chk) {
860 /* if chk != 0 then it is the max allowed index */
861 printk(KERN_INFO "C-FL-split: Cluster configuration = %d "
862 "is not supported on this hardware.\n",
863 cluster_config);
864 /* User should notice that the configuration failed, so
865 * let's bail out. */
866 return -EINVAL;
867 }
868
869 cluster_size = cpumask_weight(mask);
870 }
871
872 if ((num_online_cpus() % cluster_size) != 0) {
873 /* this can't be right, some cpus are left out */
874 printk(KERN_ERR "C-FL-split: Trying to group %d cpus in %d!\n",
875 num_online_cpus(), cluster_size);
876 return -1;
877 }
878
879 num_clusters = num_online_cpus() / cluster_size;
880 printk(KERN_INFO "C-FL-split: %d cluster(s) of size = %d\n",
881 num_clusters, cluster_size);
882
883 /* initialize clusters */
884 cflsplit = kmalloc(num_clusters * sizeof(cflsplit_domain_t), GFP_ATOMIC);
885 for (i = 0; i < num_clusters; i++) {
886
887 cflsplit[i].cpus = kmalloc(cluster_size * sizeof(cpu_entry_t),
888 GFP_ATOMIC);
889 cflsplit[i].heap_node = kmalloc(
890 cluster_size * sizeof(struct bheap_node),
891 GFP_ATOMIC);
892 bheap_init(&(cflsplit[i].cpu_heap));
893 edf_split_domain_init(&(cflsplit[i].domain), NULL,
894 cflsplit_release_jobs);
895
896 if(!zalloc_cpumask_var(&cflsplit[i].cpu_map, GFP_ATOMIC))
897 return -ENOMEM;
898#ifdef CONFIG_RELEASE_MASTER
899 cflsplit[i].domain.release_master = atomic_read(&release_master_cpu);
900#endif
901 }
902
903 /* cycle through cluster and add cpus to them */
904 for (i = 0; i < num_clusters; i++) {
905
906 for_each_online_cpu(cpu) {
907 /* check if the cpu is already in a cluster */
908 for (j = 0; j < num_clusters; j++)
909 if (cpumask_test_cpu(cpu, cflsplit[j].cpu_map))
910 break;
911 /* if it is in a cluster go to next cpu */
912 if (j < num_clusters &&
913 cpumask_test_cpu(cpu, cflsplit[j].cpu_map))
914 continue;
915
916 /* this cpu isn't in any cluster */
917 /* get the shared cpus */
918 if (unlikely(cluster_config == GLOBAL_CLUSTER))
919 cpumask_copy(mask, cpu_online_mask);
920 else
921 get_shared_cpu_map(mask, cpu, cluster_config);
922
923 cpumask_copy(cflsplit[i].cpu_map, mask);
924#ifdef VERBOSE_INIT
925 print_cluster_topology(mask, cpu);
926#endif
927 /* add cpus to current cluster and init cpu_entry_t */
928 cpu_count = 0;
929 for_each_cpu(ccpu, cflsplit[i].cpu_map) {
930
931 entry = &per_cpu(cflsplit_cpu_entries, ccpu);
932 cflsplit[i].cpus[cpu_count] = entry;
933 atomic_set(&entry->will_schedule, 0);
934 entry->cpu = ccpu;
935 entry->cluster = &cflsplit[i];
936 entry->hn = &(cflsplit[i].heap_node[cpu_count]);
937 hrtimer_init(&entry->split_timer,
938 CLOCK_MONOTONIC,
939 HRTIMER_MODE_ABS);
940 entry->split_timer.function = on_split_timeout;
941 bheap_node_init(&entry->hn, entry);
942
943 cpu_count++;
944
945 entry->linked = NULL;
946 entry->scheduled = NULL;
947#ifdef CONFIG_RELEASE_MASTER
948 /* only add CPUs that should schedule jobs */
949 if (entry->cpu != entry->cluster->domain.release_master)
950#endif
951 update_cpu_position(entry);
952 }
953 /* done with this cluster */
954 break;
955 }
956 }
957
958 free_cpumask_var(mask);
959 clusters_allocated = 1;
960 return 0;
961}
962
963/* Plugin object */
964static struct sched_plugin cflsplit_plugin __cacheline_aligned_in_smp = {
965 .plugin_name = "C-FL-split",
966 .finish_switch = cflsplit_finish_switch,
967 .tick = cflsplit_tick,
968 .task_new = cflsplit_task_new,
969 .complete_job = complete_job,
970 .task_exit = cflsplit_task_exit,
971 .schedule = cflsplit_schedule,
972 .release_at = cflsplit_release_at,
973 .task_wake_up = cflsplit_task_wake_up,
974 .task_block = cflsplit_task_block,
975 .admit_task = cflsplit_admit_task,
976 .activate_plugin = cflsplit_activate_plugin,
977};
978
979static struct proc_dir_entry *cluster_file = NULL, *cflsplit_dir = NULL;
980
981static int __init init_cflsplit(void)
982{
983 int err, fs;
984
985 err = register_sched_plugin(&cflsplit_plugin);
986 if (!err) {
987 fs = make_plugin_proc_dir(&cflsplit_plugin, &cflsplit_dir);
988 if (!fs)
989 cluster_file = create_cluster_file(cflsplit_dir, &cluster_config);
990 else
991 printk(KERN_ERR "Could not allocate C-FL-split procfs dir.\n");
992 }
993 return err;
994}
995
996static void clean_cflsplit(void)
997{
998 cleanup_cflsplit();
999 if (cluster_file)
1000 remove_proc_entry("cluster", cflsplit_dir);
1001 if (cflsplit_dir)
1002 remove_plugin_proc_dir(&cflsplit_plugin);
1003}
1004
1005module_init(init_cflsplit);
1006module_exit(clean_cflsplit);
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-21 04:24:20 -0500