aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorGlenn Elliott <gelliott@cs.unc.edu>2012-04-25 17:31:08 -0400
committerGlenn Elliott <gelliott@cs.unc.edu>2012-04-25 17:31:08 -0400
commit58f04ff13ac7128609ee468eb317c71817474a84 (patch)
tree6d443d96d0745e54fedc1ff0673e0f3f1cddc49f
parent4aabc4a7f68aae11c79b39fa65a9c54d3f3451e7 (diff)
Port rtss12 features to C-EDF (untested)
Diffstat
-rw-r--r--include/litmus/ikglp_lock.h2
-rw-r--r--include/litmus/rt_param.h1
-rw-r--r--litmus/ikglp_lock.c457
-rw-r--r--litmus/locking.c6
-rw-r--r--litmus/sched_cedf.c1095
-rw-r--r--litmus/sched_gsn_edf.c37
6 files changed, 876 insertions, 722 deletions
diff --git a/include/litmus/ikglp_lock.h b/include/litmus/ikglp_lock.h
index eb017d48410a..af6f15178cb1 100644
--- a/include/litmus/ikglp_lock.h
+++ b/include/litmus/ikglp_lock.h
@@ -74,6 +74,7 @@ struct ikglp_semaphore
74 int m; 74 int m;
75 75
76 int max_fifo_len; // max len of a fifo queue 76 int max_fifo_len; // max len of a fifo queue
77 int nr_in_fifos;
77 78
78 struct binheap_handle top_m; // min heap, base prio 79 struct binheap_handle top_m; // min heap, base prio
79 int top_m_size; // number of nodes in top_m 80 int top_m_size; // number of nodes in top_m
@@ -138,6 +139,7 @@ struct ikglp_affinity
138 int offset; 139 int offset;
139 int nr_simult; 140 int nr_simult;
140 int nr_rsrc; 141 int nr_rsrc;
142 int relax_max_fifo_len;
141}; 143};
142 144
143static inline struct ikglp_affinity* ikglp_aff_obs_from_aff_obs(struct affinity_observer* aff_obs) 145static inline struct ikglp_affinity* ikglp_aff_obs_from_aff_obs(struct affinity_observer* aff_obs)
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index f2f3bfb6a6db..4553521146cc 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -64,6 +64,7 @@ struct gpu_affinity_observer_args
64 struct affinity_observer_args obs; 64 struct affinity_observer_args obs;
65 int replica_to_gpu_offset; 65 int replica_to_gpu_offset;
66 int nr_simult_users; 66 int nr_simult_users;
67 int relaxed_rules;
67}; 68};
68 69
69/* The definition of the data that is shared between the kernel and real-time 70/* The definition of the data that is shared between the kernel and real-time
diff --git a/litmus/ikglp_lock.c b/litmus/ikglp_lock.c
index b95a1def33a3..023443014d4b 100644
--- a/litmus/ikglp_lock.c
+++ b/litmus/ikglp_lock.c
@@ -12,6 +12,9 @@
12 12
13#include <litmus/ikglp_lock.h> 13#include <litmus/ikglp_lock.h>
14 14
15// big signed value.
16#define IKGLP_INVAL_DISTANCE 0x7FFFFFFF
17
15int ikglp_max_heap_base_priority_order(struct binheap_node *a, 18int ikglp_max_heap_base_priority_order(struct binheap_node *a,
16 struct binheap_node *b) 19 struct binheap_node *b)
17{ 20{
@@ -327,7 +330,7 @@ static void ikglp_del_global_list(struct ikglp_semaphore *sem,
327// print_global_list(sem->not_top_m.root, 1); 330// print_global_list(sem->not_top_m.root, 1);
328 } 331 }
329 else { 332 else {
330// TRACE_CUR("%s/%d is in not-top-m\n", t->comm, t->pid); 333 TRACE_CUR("%s/%d is in not-top-m\n", t->comm, t->pid);
331// TRACE_CUR("Not-Top-M Before:\n"); 334// TRACE_CUR("Not-Top-M Before:\n");
332// print_global_list(sem->not_top_m.root, 1); 335// print_global_list(sem->not_top_m.root, 1);
333 336
@@ -430,7 +433,7 @@ static void ikglp_refresh_owners_prio_increase(struct task_struct *t,
430 fq->hp_waiter = t; 433 fq->hp_waiter = t;
431 fq->nest.hp_waiter_eff_prio = effective_priority(fq->hp_waiter); 434 fq->nest.hp_waiter_eff_prio = effective_priority(fq->hp_waiter);
432 435
433 TRACE_TASK(t, "no owner??\n"); 436 TRACE_TASK(t, "no owner.\n");
434 unlock_fine_irqrestore(&sem->lock, flags); 437 unlock_fine_irqrestore(&sem->lock, flags);
435 } 438 }
436 } 439 }
@@ -456,6 +459,8 @@ static void ikglp_refresh_owners_prio_decrease(struct fifo_queue *fq,
456 return; 459 return;
457 } 460 }
458 461
462 TRACE_CUR("ikglp_refresh_owners_prio_decrease\n");
463
459 raw_spin_lock(&tsk_rt(owner)->hp_blocked_tasks_lock); 464 raw_spin_lock(&tsk_rt(owner)->hp_blocked_tasks_lock);
460 465
461 old_max_eff_prio = top_priority(&tsk_rt(owner)->hp_blocked_tasks); 466 old_max_eff_prio = top_priority(&tsk_rt(owner)->hp_blocked_tasks);
@@ -643,6 +648,7 @@ static void __ikglp_enqueue_on_fq(struct ikglp_semaphore *sem,
643 __add_wait_queue_tail_exclusive(&fq->wait, wait); 648 __add_wait_queue_tail_exclusive(&fq->wait, wait);
644 649
645 ++(fq->count); 650 ++(fq->count);
651 ++(sem->nr_in_fifos);
646 652
647 // update global list. 653 // update global list.
648 if(likely(global_heap_node)) { 654 if(likely(global_heap_node)) {
@@ -874,7 +880,6 @@ static void ikglp_enqueue_on_donor(struct ikglp_semaphore *sem,
874// print_donors(sem->donors.root, 1); 880// print_donors(sem->donors.root, 1);
875} 881}
876 882
877
878int ikglp_lock(struct litmus_lock* l) 883int ikglp_lock(struct litmus_lock* l)
879{ 884{
880 struct task_struct* t = current; 885 struct task_struct* t = current;
@@ -901,28 +906,39 @@ int ikglp_lock(struct litmus_lock* l)
901 lock_global_irqsave(dgl_lock, flags); 906 lock_global_irqsave(dgl_lock, flags);
902 lock_fine_irqsave(&sem->lock, flags); 907 lock_fine_irqsave(&sem->lock, flags);
903 908
904 909 if(sem->nr_in_fifos < sem->m) {
910 // enqueue somwhere
905#ifdef CONFIG_LITMUS_AFFINITY_LOCKING 911#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
906 fq = (sem->aff_obs) ? 912 fq = (sem->aff_obs) ?
907 sem->aff_obs->ops->advise_enqueue(sem->aff_obs, t) : 913 sem->aff_obs->ops->advise_enqueue(sem->aff_obs, t) :
908 sem->shortest_fifo_queue; 914 sem->shortest_fifo_queue;
909#else 915#else
910 fq = sem->shortest_fifo_queue; 916 fq = sem->shortest_fifo_queue;
911#endif 917#endif
918 if(fq->count == 0) {
919 // take available resource
920 replica = ikglp_get_idx(sem, fq);
921
922 ikglp_get_immediate(t, fq, sem, flags); // unlocks sem->lock
912 923
913 if(fq->count == 0) { 924 unlock_global_irqrestore(dgl_lock, flags);
914 // take available resource 925 raw_spin_unlock_irqrestore(&sem->real_lock, real_flags);
915 replica = ikglp_get_idx(sem, fq); 926 goto acquired;
927 }
928 else {
929 wait.task = t; // THIS IS CRITICALLY IMPORTANT!!!
916 930
917 ikglp_get_immediate(t, fq, sem, flags); // unlocks sem->lock 931 tsk_rt(t)->blocked_lock = (struct litmus_lock*)sem; // record where we are blocked
932 mb();
918 933
919 unlock_global_irqrestore(dgl_lock, flags); 934 /* FIXME: interruptible would be nice some day */
920 raw_spin_unlock_irqrestore(&sem->real_lock, real_flags); 935 set_task_state(t, TASK_UNINTERRUPTIBLE);
921 }
922 else
923 {
924 // we have to suspend.
925 936
937 ikglp_enqueue_on_fq(sem, fq, &wait, flags); // unlocks sem->lock
938 }
939 }
940 else {
941 // donor!
926 wait.task = t; // THIS IS CRITICALLY IMPORTANT!!! 942 wait.task = t; // THIS IS CRITICALLY IMPORTANT!!!
927 943
928 tsk_rt(t)->blocked_lock = (struct litmus_lock*)sem; // record where we are blocked 944 tsk_rt(t)->blocked_lock = (struct litmus_lock*)sem; // record where we are blocked
@@ -931,42 +947,32 @@ int ikglp_lock(struct litmus_lock* l)
931 /* FIXME: interruptible would be nice some day */ 947 /* FIXME: interruptible would be nice some day */
932 set_task_state(t, TASK_UNINTERRUPTIBLE); 948 set_task_state(t, TASK_UNINTERRUPTIBLE);
933 949
934 if(fq->count < sem->max_fifo_len) { 950 if(litmus->__compare(ikglp_mth_highest(sem), BASE, t, BASE)) {
935 // enqueue on fq 951 // enqueue on PQ
936 ikglp_enqueue_on_fq(sem, fq, &wait, flags); // unlocks sem->lock 952 ikglp_enqueue_on_pq(sem, &wait);
953 unlock_fine_irqrestore(&sem->lock, flags);
937 } 954 }
938 else { 955 else {
939 956 // enqueue as donor
940 TRACE_CUR("IKGLP fifo queues are full (at least they better be).\n"); 957 ikglp_enqueue_on_donor(sem, &wait, flags); // unlocks sem->lock
941
942 // no room in fifos. Go to PQ or donors.
943
944 if(litmus->__compare(ikglp_mth_highest(sem), BASE, t, BASE)) {
945 // enqueue on PQ
946 ikglp_enqueue_on_pq(sem, &wait);
947 unlock_fine_irqrestore(&sem->lock, flags);
948 }
949 else {
950 // enqueue as donor
951 ikglp_enqueue_on_donor(sem, &wait, flags); // unlocks sem->lock
952 }
953 } 958 }
959 }
954 960
955 unlock_global_irqrestore(dgl_lock, flags); 961 unlock_global_irqrestore(dgl_lock, flags);
956 raw_spin_unlock_irqrestore(&sem->real_lock, real_flags); 962 raw_spin_unlock_irqrestore(&sem->real_lock, real_flags);
957 963
958 TS_LOCK_SUSPEND; 964 TS_LOCK_SUSPEND;
959 965
960 schedule(); 966 schedule();
961 967
962 TS_LOCK_RESUME; 968 TS_LOCK_RESUME;
963 969
964 fq = ikglp_get_queue(sem, t); 970 fq = ikglp_get_queue(sem, t);
965 BUG_ON(!fq); 971 BUG_ON(!fq);
966 972
967 replica = ikglp_get_idx(sem, fq); 973 replica = ikglp_get_idx(sem, fq);
968 }
969 974
975acquired:
970 TRACE_CUR("Acquired lock %d, queue %d\n", 976 TRACE_CUR("Acquired lock %d, queue %d\n",
971 l->ident, replica); 977 l->ident, replica);
972 978
@@ -979,6 +985,110 @@ int ikglp_lock(struct litmus_lock* l)
979 return replica; 985 return replica;
980} 986}
981 987
988//int ikglp_lock(struct litmus_lock* l)
989//{
990// struct task_struct* t = current;
991// struct ikglp_semaphore *sem = ikglp_from_lock(l);
992// unsigned long flags = 0, real_flags;
993// struct fifo_queue *fq = NULL;
994// int replica = -EINVAL;
995//
996//#ifdef CONFIG_LITMUS_DGL_SUPPORT
997// raw_spinlock_t *dgl_lock;
998//#endif
999//
1000// ikglp_wait_state_t wait;
1001//
1002// if (!is_realtime(t))
1003// return -EPERM;
1004//
1005//#ifdef CONFIG_LITMUS_DGL_SUPPORT
1006// dgl_lock = litmus->get_dgl_spinlock(t);
1007//#endif
1008//
1009// raw_spin_lock_irqsave(&sem->real_lock, real_flags);
1010//
1011// lock_global_irqsave(dgl_lock, flags);
1012// lock_fine_irqsave(&sem->lock, flags);
1013//
1014//
1015//#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
1016// fq = (sem->aff_obs) ?
1017// sem->aff_obs->ops->advise_enqueue(sem->aff_obs, t) :
1018// sem->shortest_fifo_queue;
1019//#else
1020// fq = sem->shortest_fifo_queue;
1021//#endif
1022//
1023// if(fq->count == 0) {
1024// // take available resource
1025// replica = ikglp_get_idx(sem, fq);
1026//
1027// ikglp_get_immediate(t, fq, sem, flags); // unlocks sem->lock
1028//
1029// unlock_global_irqrestore(dgl_lock, flags);
1030// raw_spin_unlock_irqrestore(&sem->real_lock, real_flags);
1031// }
1032// else
1033// {
1034// // we have to suspend.
1035//
1036// wait.task = t; // THIS IS CRITICALLY IMPORTANT!!!
1037//
1038// tsk_rt(t)->blocked_lock = (struct litmus_lock*)sem; // record where we are blocked
1039// mb();
1040//
1041// /* FIXME: interruptible would be nice some day */
1042// set_task_state(t, TASK_UNINTERRUPTIBLE);
1043//
1044// if(fq->count < sem->max_fifo_len) {
1045// // enqueue on fq
1046// ikglp_enqueue_on_fq(sem, fq, &wait, flags); // unlocks sem->lock
1047// }
1048// else {
1049//
1050// TRACE_CUR("IKGLP fifo queues are full (at least they better be).\n");
1051//
1052// // no room in fifos. Go to PQ or donors.
1053//
1054// if(litmus->__compare(ikglp_mth_highest(sem), BASE, t, BASE)) {
1055// // enqueue on PQ
1056// ikglp_enqueue_on_pq(sem, &wait);
1057// unlock_fine_irqrestore(&sem->lock, flags);
1058// }
1059// else {
1060// // enqueue as donor
1061// ikglp_enqueue_on_donor(sem, &wait, flags); // unlocks sem->lock
1062// }
1063// }
1064//
1065// unlock_global_irqrestore(dgl_lock, flags);
1066// raw_spin_unlock_irqrestore(&sem->real_lock, real_flags);
1067//
1068// TS_LOCK_SUSPEND;
1069//
1070// schedule();
1071//
1072// TS_LOCK_RESUME;
1073//
1074// fq = ikglp_get_queue(sem, t);
1075// BUG_ON(!fq);
1076//
1077// replica = ikglp_get_idx(sem, fq);
1078// }
1079//
1080// TRACE_CUR("Acquired lock %d, queue %d\n",
1081// l->ident, replica);
1082//
1083//#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
1084// if(sem->aff_obs) {
1085// return sem->aff_obs->ops->replica_to_resource(sem->aff_obs, fq);
1086// }
1087//#endif
1088//
1089// return replica;
1090//}
1091
982static void ikglp_move_donor_to_fq(struct ikglp_semaphore *sem, 1092static void ikglp_move_donor_to_fq(struct ikglp_semaphore *sem,
983 struct fifo_queue *fq, 1093 struct fifo_queue *fq,
984 ikglp_wait_state_t *donor_info) 1094 ikglp_wait_state_t *donor_info)
@@ -1092,8 +1202,6 @@ static void ikglp_steal_to_fq(struct ikglp_semaphore *sem,
1092 struct task_struct *t = fq_wait->task; 1202 struct task_struct *t = fq_wait->task;
1093 struct fifo_queue *fq_steal = fq_wait->donee_heap_node.fq; 1203 struct fifo_queue *fq_steal = fq_wait->donee_heap_node.fq;
1094 1204
1095 WARN_ON(t != fq_steal->hp_waiter);
1096
1097 TRACE_CUR("FQ request %s/%d being moved to fq %d\n", 1205 TRACE_CUR("FQ request %s/%d being moved to fq %d\n",
1098 t->comm, 1206 t->comm,
1099 t->pid, 1207 t->pid,
@@ -1111,11 +1219,13 @@ static void ikglp_steal_to_fq(struct ikglp_semaphore *sem,
1111 } 1219 }
1112#endif 1220#endif
1113 1221
1114 fq_steal->hp_waiter = ikglp_find_hp_waiter(fq_steal, NULL); 1222 if(t == fq_steal->hp_waiter) {
1115 TRACE_TASK(t, "New hp_waiter for fq %d is %s/%d!\n", 1223 fq_steal->hp_waiter = ikglp_find_hp_waiter(fq_steal, NULL);
1116 ikglp_get_idx(sem, fq_steal), 1224 TRACE_TASK(t, "New hp_waiter for fq %d is %s/%d!\n",
1117 (fq_steal->hp_waiter) ? fq_steal->hp_waiter->comm : "nil", 1225 ikglp_get_idx(sem, fq_steal),
1118 (fq_steal->hp_waiter) ? fq_steal->hp_waiter->pid : -1); 1226 (fq_steal->hp_waiter) ? fq_steal->hp_waiter->comm : "nil",
1227 (fq_steal->hp_waiter) ? fq_steal->hp_waiter->pid : -1);
1228 }
1119 1229
1120 1230
1121 // Update shortest. 1231 // Update shortest.
@@ -1172,9 +1282,11 @@ int ikglp_unlock(struct litmus_lock* l)
1172 struct task_struct *donee = NULL; 1282 struct task_struct *donee = NULL;
1173 struct task_struct *next = NULL; 1283 struct task_struct *next = NULL;
1174 struct task_struct *new_on_fq = NULL; 1284 struct task_struct *new_on_fq = NULL;
1285 struct fifo_queue *fq_of_new_on_fq = NULL;
1175 1286
1176 ikglp_wait_state_t *other_donor_info = NULL; 1287 ikglp_wait_state_t *other_donor_info = NULL;
1177 struct fifo_queue *to_steal = NULL; 1288 struct fifo_queue *to_steal = NULL;
1289 int need_steal_prio_reeval = 0;
1178 struct fifo_queue *fq; 1290 struct fifo_queue *fq;
1179 1291
1180#ifdef CONFIG_LITMUS_DGL_SUPPORT 1292#ifdef CONFIG_LITMUS_DGL_SUPPORT
@@ -1212,6 +1324,7 @@ int ikglp_unlock(struct litmus_lock* l)
1212 if(fq->count < sem->shortest_fifo_queue->count) { 1324 if(fq->count < sem->shortest_fifo_queue->count) {
1213 sem->shortest_fifo_queue = fq; 1325 sem->shortest_fifo_queue = fq;
1214 } 1326 }
1327 --(sem->nr_in_fifos);
1215 1328
1216#ifdef CONFIG_LITMUS_AFFINITY_LOCKING 1329#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
1217 if(sem->aff_obs) { 1330 if(sem->aff_obs) {
@@ -1227,12 +1340,27 @@ int ikglp_unlock(struct litmus_lock* l)
1227 1340
1228 new_on_fq = donor_info->task; 1341 new_on_fq = donor_info->task;
1229 1342
1230 TRACE_TASK(t, "Moving MY donor (%s/%d) to fq %d.\n",
1231 new_on_fq->comm, new_on_fq->pid,
1232 ikglp_get_idx(sem, fq));
1233 // donor moved to FQ 1343 // donor moved to FQ
1234 donee = t; 1344 donee = t;
1235 ikglp_move_donor_to_fq(sem, fq, donor_info); 1345
1346#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
1347 if(sem->aff_obs && sem->aff_obs->relax_max_fifo_len) {
1348 fq_of_new_on_fq = sem->aff_obs->ops->advise_enqueue(sem->aff_obs, new_on_fq);
1349 }
1350 else {
1351 fq_of_new_on_fq = fq;
1352 }
1353#else
1354 fq_of_new_on_fq = fq;
1355#endif
1356
1357 TRACE_TASK(t, "Moving MY donor (%s/%d) to fq %d (non-aff wanted fq %d).\n",
1358 new_on_fq->comm, new_on_fq->pid,
1359 ikglp_get_idx(sem, fq_of_new_on_fq),
1360 ikglp_get_idx(sem, fq));
1361
1362
1363 ikglp_move_donor_to_fq(sem, fq_of_new_on_fq, donor_info);
1236 } 1364 }
1237 else if(!binheap_empty(&sem->donors)) { // No donor, so move any donor to FQ 1365 else if(!binheap_empty(&sem->donors)) { // No donor, so move any donor to FQ
1238 // move other donor to FQ 1366 // move other donor to FQ
@@ -1252,11 +1380,23 @@ int ikglp_unlock(struct litmus_lock* l)
1252 other_donor_info->donee_info->donor_info = NULL; // clear the cross-link 1380 other_donor_info->donee_info->donor_info = NULL; // clear the cross-link
1253 binheap_decrease(&other_donor_info->donee_info->node, &sem->donees); 1381 binheap_decrease(&other_donor_info->donee_info->node, &sem->donees);
1254 1382
1255 TRACE_TASK(t, "Moving a donor (%s/%d) to fq %d.\n", 1383#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
1384 if(sem->aff_obs && sem->aff_obs->relax_max_fifo_len) {
1385 fq_of_new_on_fq = sem->aff_obs->ops->advise_enqueue(sem->aff_obs, new_on_fq);
1386 }
1387 else {
1388 fq_of_new_on_fq = fq;
1389 }
1390#else
1391 fq_of_new_on_fq = fq;
1392#endif
1393
1394 TRACE_TASK(t, "Moving a donor (%s/%d) to fq %d (non-aff wanted fq %d).\n",
1256 new_on_fq->comm, new_on_fq->pid, 1395 new_on_fq->comm, new_on_fq->pid,
1396 ikglp_get_idx(sem, fq_of_new_on_fq),
1257 ikglp_get_idx(sem, fq)); 1397 ikglp_get_idx(sem, fq));
1258 1398
1259 ikglp_move_donor_to_fq(sem, fq, other_donor_info); 1399 ikglp_move_donor_to_fq(sem, fq_of_new_on_fq, other_donor_info);
1260 } 1400 }
1261 else if(!binheap_empty(&sem->priority_queue)) { // No donors, so move PQ 1401 else if(!binheap_empty(&sem->priority_queue)) { // No donors, so move PQ
1262 ikglp_heap_node_t *pq_node = binheap_top_entry(&sem->priority_queue, 1402 ikglp_heap_node_t *pq_node = binheap_top_entry(&sem->priority_queue,
@@ -1266,11 +1406,23 @@ int ikglp_unlock(struct litmus_lock* l)
1266 1406
1267 new_on_fq = pq_wait->task; 1407 new_on_fq = pq_wait->task;
1268 1408
1269 TRACE_TASK(t, "Moving a pq waiter (%s/%d) to fq %d.\n", 1409#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
1410 if(sem->aff_obs && sem->aff_obs->relax_max_fifo_len) {
1411 fq_of_new_on_fq = sem->aff_obs->ops->advise_enqueue(sem->aff_obs, new_on_fq);
1412 }
1413 else {
1414 fq_of_new_on_fq = fq;
1415 }
1416#else
1417 fq_of_new_on_fq = fq;
1418#endif
1419
1420 TRACE_TASK(t, "Moving a pq waiter (%s/%d) to fq %d (non-aff wanted fq %d).\n",
1270 new_on_fq->comm, new_on_fq->pid, 1421 new_on_fq->comm, new_on_fq->pid,
1422 ikglp_get_idx(sem, fq_of_new_on_fq),
1271 ikglp_get_idx(sem, fq)); 1423 ikglp_get_idx(sem, fq));
1272 1424
1273 ikglp_move_pq_to_fq(sem, fq, pq_wait); 1425 ikglp_move_pq_to_fq(sem, fq_of_new_on_fq, pq_wait);
1274 } 1426 }
1275 else if(fq->count == 0) { // No PQ and this queue is empty, so steal. 1427 else if(fq->count == 0) { // No PQ and this queue is empty, so steal.
1276 ikglp_wait_state_t *fq_wait; 1428 ikglp_wait_state_t *fq_wait;
@@ -1290,6 +1442,8 @@ int ikglp_unlock(struct litmus_lock* l)
1290 to_steal = fq_wait->donee_heap_node.fq; 1442 to_steal = fq_wait->donee_heap_node.fq;
1291 1443
1292 new_on_fq = fq_wait->task; 1444 new_on_fq = fq_wait->task;
1445 fq_of_new_on_fq = fq;
1446 need_steal_prio_reeval = (new_on_fq == to_steal->hp_waiter);
1293 1447
1294 TRACE_TASK(t, "Found %s/%d of fq %d to steal for fq %d...\n", 1448 TRACE_TASK(t, "Found %s/%d of fq %d to steal for fq %d...\n",
1295 new_on_fq->comm, new_on_fq->pid, 1449 new_on_fq->comm, new_on_fq->pid,
@@ -1378,33 +1532,40 @@ int ikglp_unlock(struct litmus_lock* l)
1378 TRACE_TASK(t, "Rechecking priority inheritance of fq %d, triggered by stealing.\n", 1532 TRACE_TASK(t, "Rechecking priority inheritance of fq %d, triggered by stealing.\n",
1379 ikglp_get_idx(sem, to_steal)); 1533 ikglp_get_idx(sem, to_steal));
1380 1534
1381 ikglp_refresh_owners_prio_decrease(to_steal, sem, flags); // unlocks sem->lock. reacquire it. 1535 if(need_steal_prio_reeval) {
1382 lock_fine_irqsave(&sem->lock, flags); // there should be no contention!!!! 1536 ikglp_refresh_owners_prio_decrease(to_steal, sem, flags); // unlocks sem->lock. reacquire it.
1537 lock_fine_irqsave(&sem->lock, flags); // there should be no contention!!!!
1538 }
1383 } 1539 }
1384 1540
1385 // check for new HP waiter. 1541 // check for new HP waiter.
1386 if(new_on_fq) { 1542 if(new_on_fq) {
1387 // fq->owner is null, so just update the hp_waiter without locking. 1543 if(fq == fq_of_new_on_fq) {
1388 1544 // fq->owner is null, so just update the hp_waiter without locking.
1389 if(new_on_fq == fq->hp_waiter) { 1545 if(new_on_fq == fq->hp_waiter) {
1390 TRACE_TASK(t, "new_on_fq is already hp_waiter.\n", 1546 TRACE_TASK(t, "new_on_fq is already hp_waiter.\n",
1391 fq->hp_waiter->comm, fq->hp_waiter->pid);
1392 fq->nest.hp_waiter_eff_prio = effective_priority(fq->hp_waiter); // set this just to be sure...
1393 }
1394 else if(litmus->compare(new_on_fq, fq->hp_waiter)) {
1395 if(fq->hp_waiter)
1396 TRACE_TASK(t, "has higher prio than hp_waiter (%s/%d).\n",
1397 fq->hp_waiter->comm, fq->hp_waiter->pid); 1547 fq->hp_waiter->comm, fq->hp_waiter->pid);
1398 else 1548 fq->nest.hp_waiter_eff_prio = effective_priority(fq->hp_waiter); // set this just to be sure...
1399 TRACE_TASK(t, "has higher prio than hp_waiter (NIL).\n"); 1549 }
1550 else if(litmus->compare(new_on_fq, fq->hp_waiter)) {
1551 if(fq->hp_waiter)
1552 TRACE_TASK(t, "has higher prio than hp_waiter (%s/%d).\n",
1553 fq->hp_waiter->comm, fq->hp_waiter->pid);
1554 else
1555 TRACE_TASK(t, "has higher prio than hp_waiter (NIL).\n");
1400 1556
1401 fq->hp_waiter = new_on_fq; 1557 fq->hp_waiter = new_on_fq;
1402 fq->nest.hp_waiter_eff_prio = effective_priority(fq->hp_waiter); 1558 fq->nest.hp_waiter_eff_prio = effective_priority(fq->hp_waiter);
1403 1559
1404 TRACE_TASK(t, "New hp_waiter for fq %d is %s/%d!\n", 1560 TRACE_TASK(t, "New hp_waiter for fq %d is %s/%d!\n",
1405 ikglp_get_idx(sem, fq), 1561 ikglp_get_idx(sem, fq),
1406 (fq->hp_waiter) ? fq->hp_waiter->comm : "nil", 1562 (fq->hp_waiter) ? fq->hp_waiter->comm : "nil",
1407 (fq->hp_waiter) ? fq->hp_waiter->pid : -1); 1563 (fq->hp_waiter) ? fq->hp_waiter->pid : -1);
1564 }
1565 }
1566 else {
1567 ikglp_refresh_owners_prio_increase(new_on_fq, fq_of_new_on_fq, sem, flags); // unlocks sem->lock. reacquire it.
1568 lock_fine_irqsave(&sem->lock, flags); // there should be no contention!!!!
1408 } 1569 }
1409 } 1570 }
1410 1571
@@ -1608,6 +1769,7 @@ struct litmus_lock* ikglp_new(int m,
1608 sem->nr_replicas = nr_replicas; 1769 sem->nr_replicas = nr_replicas;
1609 sem->m = m; 1770 sem->m = m;
1610 sem->max_fifo_len = (sem->m/nr_replicas) + ((sem->m%nr_replicas) != 0); 1771 sem->max_fifo_len = (sem->m/nr_replicas) + ((sem->m%nr_replicas) != 0);
1772 sem->nr_in_fifos = 0;
1611 1773
1612 TRACE("New IKGLP Sem: m = %d, k = %d, max fifo_len = %d\n", 1774 TRACE("New IKGLP Sem: m = %d, k = %d, max fifo_len = %d\n",
1613 sem->m, 1775 sem->m,
@@ -1782,6 +1944,12 @@ static struct affinity_observer* ikglp_aff_obs_new(struct affinity_observer_ops*
1782 ikglp_aff->offset = aff_args.replica_to_gpu_offset; 1944 ikglp_aff->offset = aff_args.replica_to_gpu_offset;
1783 ikglp_aff->nr_simult = aff_args.nr_simult_users; 1945 ikglp_aff->nr_simult = aff_args.nr_simult_users;
1784 ikglp_aff->nr_rsrc = sem->nr_replicas / ikglp_aff->nr_simult; 1946 ikglp_aff->nr_rsrc = sem->nr_replicas / ikglp_aff->nr_simult;
1947 ikglp_aff->relax_max_fifo_len = (aff_args.relaxed_rules) ? 1 : 0;
1948
1949 TRACE_CUR("GPU affinity_observer: offset = %d, nr_simult = %d, "
1950 "nr_rsrc = %d, relaxed_fifo_len = %d\n",
1951 ikglp_aff->offset, ikglp_aff->nr_simult, ikglp_aff->nr_rsrc,
1952 ikglp_aff->relax_max_fifo_len);
1785 1953
1786 memset(ikglp_aff->nr_cur_users_on_rsrc, 0, sizeof(int)*(ikglp_aff->nr_rsrc)); 1954 memset(ikglp_aff->nr_cur_users_on_rsrc, 0, sizeof(int)*(ikglp_aff->nr_rsrc));
1787 1955
@@ -1851,6 +2019,9 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
1851 int i; 2019 int i;
1852 int affinity_gpu; 2020 int affinity_gpu;
1853 2021
2022 int max_fifo_len = (aff->relax_max_fifo_len) ?
2023 sem->m : sem->max_fifo_len;
2024
1854 // simply pick the shortest queue if, we have no affinity, or we have 2025 // simply pick the shortest queue if, we have no affinity, or we have
1855 // affinity with the shortest 2026 // affinity with the shortest
1856 if(unlikely(tsk_rt(t)->last_gpu < 0)) { 2027 if(unlikely(tsk_rt(t)->last_gpu < 0)) {
@@ -1882,7 +2053,7 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
1882 2053
1883 for(i = 0; i < sem->nr_replicas; ++i) { 2054 for(i = 0; i < sem->nr_replicas; ++i) {
1884 if(&aff->q_info[i] != shortest) { 2055 if(&aff->q_info[i] != shortest) {
1885 if(aff->q_info[i].q->count < sem->max_fifo_len) { 2056 if(aff->q_info[i].q->count < max_fifo_len) {
1886 2057
1887 lt_t est_len = 2058 lt_t est_len =
1888 aff->q_info[i].estimated_len + 2059 aff->q_info[i].estimated_len +
@@ -1895,7 +2066,7 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
1895 // 2066 //
1896 // tie-break on the shortest number of simult users. this only kicks in 2067 // tie-break on the shortest number of simult users. this only kicks in
1897 // when there are more than 1 empty queues. 2068 // when there are more than 1 empty queues.
1898 if((shortest->q->count >= sem->max_fifo_len) || /* 'shortest' is full and i-th queue is not */ 2069 if((shortest->q->count >= max_fifo_len) || /* 'shortest' is full and i-th queue is not */
1899 (est_len < min_len) || /* i-th queue has shortest length */ 2070 (est_len < min_len) || /* i-th queue has shortest length */
1900 ((est_len == min_len) && /* equal lengths, but one has fewer over-all users */ 2071 ((est_len == min_len) && /* equal lengths, but one has fewer over-all users */
1901 (*(aff->q_info[i].nr_cur_users) < min_nr_users))) { 2072 (*(aff->q_info[i].nr_cur_users) < min_nr_users))) {
@@ -1920,7 +2091,7 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
1920 } 2091 }
1921 } 2092 }
1922 2093
1923 if(shortest->q->count >= sem->max_fifo_len) { 2094 if(shortest->q->count >= max_fifo_len) {
1924 TRACE_CUR("selected fq %d is too long, but returning it anyway.\n", 2095 TRACE_CUR("selected fq %d is too long, but returning it anyway.\n",
1925 ikglp_get_idx(sem, shortest->q)); 2096 ikglp_get_idx(sem, shortest->q));
1926 } 2097 }
@@ -1936,15 +2107,120 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
1936 //return(sem->shortest_fifo_queue); 2107 //return(sem->shortest_fifo_queue);
1937} 2108}
1938 2109
2110
2111
2112
2113static ikglp_wait_state_t* pick_steal(struct ikglp_affinity* aff,
2114 int dest_gpu,
2115 struct fifo_queue* fq)
2116{
2117 struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
2118 ikglp_wait_state_t *wait = NULL;
2119 int max_improvement = -(MIG_NONE+1);
2120 int replica = ikglp_get_idx(sem, fq);
2121
2122 if(waitqueue_active(&fq->wait)) {
2123 int this_gpu = replica_to_gpu(aff, replica);
2124 struct list_head *pos;
2125
2126 list_for_each(pos, &fq->wait.task_list) {
2127 wait_queue_t *fq_wait = list_entry(pos, wait_queue_t, task_list);
2128 ikglp_wait_state_t *tmp_wait = container_of(fq_wait, ikglp_wait_state_t, fq_node);
2129
2130 int tmp_improvement =
2131 gpu_migration_distance(this_gpu, tsk_rt(tmp_wait->task)->last_gpu) -
2132 gpu_migration_distance(dest_gpu, tsk_rt(tmp_wait->task)->last_gpu);
2133
2134 if(tmp_improvement > max_improvement) {
2135 wait = tmp_wait;
2136 max_improvement = tmp_improvement;
2137
2138 if(max_improvement >= (MIG_NONE-1)) {
2139 goto out;
2140 }
2141 }
2142 }
2143
2144 BUG_ON(!wait);
2145 }
2146 else {
2147 TRACE_CUR("fq %d is empty!\n", replica);
2148 }
2149
2150out:
2151
2152 TRACE_CUR("Candidate victim from fq %d is %s/%d. aff improvement = %d.\n",
2153 replica,
2154 (wait) ? wait->task->comm : "nil",
2155 (wait) ? wait->task->pid : -1,
2156 max_improvement);
2157
2158 return wait;
2159}
2160
2161
1939ikglp_wait_state_t* gpu_ikglp_advise_steal(struct ikglp_affinity* aff, 2162ikglp_wait_state_t* gpu_ikglp_advise_steal(struct ikglp_affinity* aff,
1940 struct fifo_queue* dst) 2163 struct fifo_queue* dst)
1941{ 2164{
2165 // Huristic strategy: Find task with greatest improvement in affinity.
2166 //
1942 struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock); 2167 struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
2168 ikglp_wait_state_t *to_steal_state = NULL;
2169// ikglp_wait_state_t *default_to_steal_state = ikglp_find_hp_waiter_to_steal(sem);
2170 int max_improvement = -(MIG_NONE+1);
2171 int replica, i;
2172 int dest_gpu;
1943 2173
1944 // For now, just steal highest priority waiter 2174 replica = ikglp_get_idx(sem, dst);
1945 // TODO: Implement affinity-aware stealing. 2175 dest_gpu = replica_to_gpu(aff, replica);
1946 2176
1947 return ikglp_find_hp_waiter_to_steal(sem); 2177 for(i = 0; i < sem->nr_replicas; ++i) {
2178 ikglp_wait_state_t *tmp_to_steal_state =
2179 pick_steal(aff, dest_gpu, &sem->fifo_queues[i]);
2180
2181 if(tmp_to_steal_state) {
2182 int tmp_improvement =
2183 gpu_migration_distance(replica_to_gpu(aff, i), tsk_rt(tmp_to_steal_state->task)->last_gpu) -
2184 gpu_migration_distance(dest_gpu, tsk_rt(tmp_to_steal_state->task)->last_gpu);
2185
2186 if(tmp_improvement > max_improvement) {
2187 to_steal_state = tmp_to_steal_state;
2188 max_improvement = tmp_improvement;
2189
2190 if(max_improvement >= (MIG_NONE-1)) {
2191 goto out;
2192 }
2193 }
2194 }
2195 }
2196
2197out:
2198 if(!to_steal_state) {
2199 TRACE_CUR("Could not find anyone to steal.\n");
2200 }
2201 else {
2202 TRACE_CUR("Selected victim %s/%d on fq %d (GPU %d) for fq %d (GPU %d): improvement = %d\n",
2203 to_steal_state->task->comm, to_steal_state->task->pid,
2204 ikglp_get_idx(sem, to_steal_state->donee_heap_node.fq),
2205 replica_to_gpu(aff, ikglp_get_idx(sem, to_steal_state->donee_heap_node.fq)),
2206 ikglp_get_idx(sem, dst),
2207 dest_gpu,
2208 max_improvement);
2209
2210// TRACE_CUR("Non-aff wanted to select victim %s/%d on fq %d (GPU %d) for fq %d (GPU %d): improvement = %d\n",
2211// default_to_steal_state->task->comm, default_to_steal_state->task->pid,
2212// ikglp_get_idx(sem, default_to_steal_state->donee_heap_node.fq),
2213// replica_to_gpu(aff, ikglp_get_idx(sem, default_to_steal_state->donee_heap_node.fq)),
2214// ikglp_get_idx(sem, dst),
2215// replica_to_gpu(aff, ikglp_get_idx(sem, dst)),
2216//
2217// gpu_migration_distance(
2218// replica_to_gpu(aff, ikglp_get_idx(sem, default_to_steal_state->donee_heap_node.fq)),
2219// tsk_rt(default_to_steal_state->task)->last_gpu) -
2220// gpu_migration_distance(dest_gpu, tsk_rt(default_to_steal_state->task)->last_gpu));
2221 }
2222
2223 return(to_steal_state);
1948} 2224}
1949 2225
1950 2226
@@ -1963,8 +2239,8 @@ static ikglp_donee_heap_node_t* pick_donee(struct ikglp_affinity* aff,
1963 ikglp_donee_heap_node_t *donee_node; 2239 ikglp_donee_heap_node_t *donee_node;
1964 struct task_struct *mth_highest = ikglp_mth_highest(sem); 2240 struct task_struct *mth_highest = ikglp_mth_highest(sem);
1965 2241
1966 lt_t now = litmus_clock(); 2242// lt_t now = litmus_clock();
1967 2243//
1968// TRACE_CUR("fq %d: mth_highest: %s/%d, deadline = %d: (donor) = ??? ", 2244// TRACE_CUR("fq %d: mth_highest: %s/%d, deadline = %d: (donor) = ??? ",
1969// ikglp_get_idx(sem, fq), 2245// ikglp_get_idx(sem, fq),
1970// mth_highest->comm, mth_highest->pid, 2246// mth_highest->comm, mth_highest->pid,
@@ -2042,7 +2318,8 @@ static ikglp_donee_heap_node_t* pick_donee(struct ikglp_affinity* aff,
2042 2318
2043 donee = NULL; 2319 donee = NULL;
2044 donee_node = NULL; 2320 donee_node = NULL;
2045 *dist_from_head = sem->max_fifo_len + 1; 2321 //*dist_from_head = sem->max_fifo_len + 1;
2322 *dist_from_head = IKGLP_INVAL_DISTANCE;
2046 2323
2047 TRACE_CUR("Found no one to be donee in fq %d!\n", ikglp_get_idx(sem, fq)); 2324 TRACE_CUR("Found no one to be donee in fq %d!\n", ikglp_get_idx(sem, fq));
2048 2325
@@ -2113,7 +2390,7 @@ ikglp_donee_heap_node_t* gpu_ikglp_advise_donee_selection(
2113 2390
2114 // only interested in queues that will improve our distance 2391 // only interested in queues that will improve our distance
2115 if(temp_distance < distance || donee_node == NULL) { 2392 if(temp_distance < distance || donee_node == NULL) {
2116 int dist_from_head = sem->max_fifo_len + 1; 2393 int dist_from_head = IKGLP_INVAL_DISTANCE;
2117 2394
2118 TRACE_CUR("searching for donor on GPU %d", i); 2395 TRACE_CUR("searching for donor on GPU %d", i);
2119 2396
@@ -2137,7 +2414,7 @@ ikglp_donee_heap_node_t* gpu_ikglp_advise_donee_selection(
2137 } 2414 }
2138 } 2415 }
2139 2416
2140 if(dist_from_head != sem->max_fifo_len + 1) { 2417 if(dist_from_head != IKGLP_INVAL_DISTANCE) {
2141 TRACE_CUR("found donee %s/%d and is the %d-th waiter.\n", 2418 TRACE_CUR("found donee %s/%d and is the %d-th waiter.\n",
2142 donee_node->task->comm, donee_node->task->pid, 2419 donee_node->task->comm, donee_node->task->pid,
2143 dist_from_head); 2420 dist_from_head);
diff --git a/litmus/locking.c b/litmus/locking.c
index e754b2fa2634..48b548a61f63 100644
--- a/litmus/locking.c
+++ b/litmus/locking.c
@@ -99,7 +99,8 @@ asmlinkage long sys_litmus_lock(int lock_od)
99 entry = get_entry_for_od(lock_od); 99 entry = get_entry_for_od(lock_od);
100 if (entry && is_lock(entry)) { 100 if (entry && is_lock(entry)) {
101 l = get_lock(entry); 101 l = get_lock(entry);
102 TRACE_CUR("attempts to lock 0x%p\n", l); 102 //TRACE_CUR("attempts to lock 0x%p\n", l);
103 TRACE_CUR("attempts to lock %d\n", l->ident);
103 err = l->ops->lock(l); 104 err = l->ops->lock(l);
104 } 105 }
105 106
@@ -121,7 +122,8 @@ asmlinkage long sys_litmus_unlock(int lock_od)
121 entry = get_entry_for_od(lock_od); 122 entry = get_entry_for_od(lock_od);
122 if (entry && is_lock(entry)) { 123 if (entry && is_lock(entry)) {
123 l = get_lock(entry); 124 l = get_lock(entry);
124 TRACE_CUR("attempts to unlock 0x%p\n", l); 125 //TRACE_CUR("attempts to unlock 0x%p\n", l);
126 TRACE_CUR("attempts to unlock %d\n", l->ident);
125 err = l->ops->unlock(l); 127 err = l->ops->unlock(l);
126 } 128 }
127 129
diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c
index 132c44a43564..aa350bb7eabc 100644
--- a/litmus/sched_cedf.c
+++ b/litmus/sched_cedf.c
@@ -30,7 +30,6 @@
30#include <linux/sched.h> 30#include <linux/sched.h>
31#include <linux/slab.h> 31#include <linux/slab.h>
32#include <linux/uaccess.h> 32#include <linux/uaccess.h>
33
34#include <linux/module.h> 33#include <linux/module.h>
35 34
36#include <litmus/litmus.h> 35#include <litmus/litmus.h>
@@ -45,6 +44,15 @@
45#include <litmus/bheap.h> 44#include <litmus/bheap.h>
46#include <litmus/binheap.h> 45#include <litmus/binheap.h>
47 46
47#ifdef CONFIG_LITMUS_LOCKING
48#include <litmus/kfmlp_lock.h>
49#endif
50
51#ifdef CONFIG_LITMUS_NESTED_LOCKING
52#include <litmus/rsm_lock.h>
53#include <litmus/ikglp_lock.h>
54#endif
55
48#ifdef CONFIG_SCHED_CPU_AFFINITY 56#ifdef CONFIG_SCHED_CPU_AFFINITY
49#include <litmus/affinity.h> 57#include <litmus/affinity.h>
50#endif 58#endif
@@ -69,6 +77,10 @@
69#include <litmus/nvidia_info.h> 77#include <litmus/nvidia_info.h>
70#endif 78#endif
71 79
80#if defined(CONFIG_LITMUS_AFFINITY_LOCKING) && defined(CONFIG_LITMUS_NVIDIA)
81#include <litmus/gpu_affinity.h>
82#endif
83
72/* Reference configuration variable. Determines which cache level is used to 84/* Reference configuration variable. Determines which cache level is used to
73 * group CPUs into clusters. GLOBAL_CLUSTER, which is the default, means that 85 * group CPUs into clusters. GLOBAL_CLUSTER, which is the default, means that
74 * all CPUs form a single cluster (just like GSN-EDF). 86 * all CPUs form a single cluster (just like GSN-EDF).
@@ -88,8 +100,6 @@ typedef struct {
88 struct task_struct* linked; /* only RT tasks */ 100 struct task_struct* linked; /* only RT tasks */
89 struct task_struct* scheduled; /* only RT tasks */ 101 struct task_struct* scheduled; /* only RT tasks */
90 atomic_t will_schedule; /* prevent unneeded IPIs */ 102 atomic_t will_schedule; /* prevent unneeded IPIs */
91
92 int in_heap; /* == 0/1: not in / in heap*/
93 struct binheap_node hn; 103 struct binheap_node hn;
94} cpu_entry_t; 104} cpu_entry_t;
95 105
@@ -103,7 +113,6 @@ DEFINE_PER_CPU(cpu_entry_t, cedf_cpu_entries);
103#define test_will_schedule(cpu) \ 113#define test_will_schedule(cpu) \
104 (atomic_read(&per_cpu(cedf_cpu_entries, cpu).will_schedule)) 114 (atomic_read(&per_cpu(cedf_cpu_entries, cpu).will_schedule))
105 115
106
107#ifdef CONFIG_LITMUS_PAI_SOFTIRQD 116#ifdef CONFIG_LITMUS_PAI_SOFTIRQD
108struct tasklet_head 117struct tasklet_head
109{ 118{
@@ -132,6 +141,10 @@ typedef struct clusterdomain {
132#ifdef CONFIG_LITMUS_PAI_SOFTIRQD 141#ifdef CONFIG_LITMUS_PAI_SOFTIRQD
133 struct tasklet_head pending_tasklets; 142 struct tasklet_head pending_tasklets;
134#endif 143#endif
144
145#ifdef CONFIG_LITMUS_DGL_SUPPORT
146 raw_spinlock_t dgl_lock;
147#endif
135} cedf_domain_t; 148} cedf_domain_t;
136 149
137/* a cedf_domain per cluster; allocation is done at init/activation time */ 150/* a cedf_domain per cluster; allocation is done at init/activation time */
@@ -140,6 +153,22 @@ cedf_domain_t *cedf;
140#define remote_cluster(cpu) ((cedf_domain_t *) per_cpu(cedf_cpu_entries, cpu).cluster) 153#define remote_cluster(cpu) ((cedf_domain_t *) per_cpu(cedf_cpu_entries, cpu).cluster)
141#define task_cpu_cluster(task) remote_cluster(get_partition(task)) 154#define task_cpu_cluster(task) remote_cluster(get_partition(task))
142 155
156/* total number of cluster */
157static int num_clusters;
158/* we do not support cluster of different sizes */
159static unsigned int cluster_size;
160
161static int clusters_allocated = 0;
162
163#ifdef CONFIG_LITMUS_DGL_SUPPORT
164static raw_spinlock_t* cedf_get_dgl_spinlock(struct task_struct *t)
165{
166 cedf_domain_t *cluster = task_cpu_cluster(t);
167 return(&cluster->dgl_lock);
168}
169#endif
170
171
143/* Uncomment WANT_ALL_SCHED_EVENTS if you want to see all scheduling 172/* Uncomment WANT_ALL_SCHED_EVENTS if you want to see all scheduling
144 * decisions in the TRACE() log; uncomment VERBOSE_INIT for verbose 173 * decisions in the TRACE() log; uncomment VERBOSE_INIT for verbose
145 * information during the initialization of the plugin (e.g., topology) 174 * information during the initialization of the plugin (e.g., topology)
@@ -165,10 +194,11 @@ static void update_cpu_position(cpu_entry_t *entry)
165{ 194{
166 cedf_domain_t *cluster = entry->cluster; 195 cedf_domain_t *cluster = entry->cluster;
167 196
168 if (likely(entry->in_heap)) 197 if (likely(binheap_is_in_heap(&entry->hn))) {
169 binheap_delete(&entry->hn, &cluster->cpu_heap); 198 binheap_delete(&entry->hn, &cluster->cpu_heap);
199 }
200
170 binheap_add(&entry->hn, &cluster->cpu_heap, cpu_entry_t, hn); 201 binheap_add(&entry->hn, &cluster->cpu_heap, cpu_entry_t, hn);
171 entry->in_heap = 1;
172} 202}
173 203
174/* caller must hold cedf lock */ 204/* caller must hold cedf lock */
@@ -464,28 +494,6 @@ static void __do_lit_tasklet(struct tasklet_struct* tasklet, unsigned long flush
464} 494}
465 495
466 496
467static void flush_tasklets(cedf_domain_t* cluster, struct task_struct* task)
468{
469 // lazy flushing.
470 // just change ownership to NULL and let an idle processor
471 // take care of it. :P
472
473 struct tasklet_struct* step;
474 unsigned long flags;
475
476 raw_spin_lock_irqsave(&cluster->cluster_lock, flags);
477
478 for(step = cluster->pending_tasklets.head; step != NULL; step = step->next) {
479 if(step->owner == task) {
480 TRACE("%s: Found tasklet to flush: %d\n", __FUNCTION__, step->owner->pid);
481 step->owner = NULL;
482 }
483 }
484
485 raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags);
486}
487
488
489static void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* sched_task) 497static void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* sched_task)
490{ 498{
491 int work_to_do = 1; 499 int work_to_do = 1;
@@ -501,24 +509,28 @@ static void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* sched_ta
501 509
502 if(cluster->pending_tasklets.head != NULL) { 510 if(cluster->pending_tasklets.head != NULL) {
503 // remove tasklet at head. 511 // remove tasklet at head.
512 struct tasklet_struct *prev = NULL;
504 tasklet = cluster->pending_tasklets.head; 513 tasklet = cluster->pending_tasklets.head;
505 514
506 if(edf_higher_prio(tasklet->owner, sched_task)) { 515 while(tasklet && edf_higher_prio(sched_task, tasklet->owner)) {
516 prev = tasklet;
517 tasklet = tasklet->next;
518 }
507 519
508 if(NULL == tasklet->next) { 520 // remove the tasklet from the queue
509 // tasklet is at the head, list only has one element 521 if(prev) {
510 TRACE("%s: Tasklet for %d is the last element in tasklet queue.\n", __FUNCTION__, (tasklet->owner) ? tasklet->owner->pid : -1); 522 prev->next = tasklet->next;
511 cluster->pending_tasklets.tail = &(cluster->pending_tasklets.head); 523 if(prev->next == NULL) {
524 TRACE("%s: Tasklet for %d is the last element in tasklet queue.\n", __FUNCTION__, tasklet->owner->pid);
525 cluster->pending_tasklets.tail = &(prev);
512 } 526 }
513
514 // remove the tasklet from the queue
515 cluster->pending_tasklets.head = tasklet->next;
516
517 TRACE("%s: Removed tasklet for %d from tasklet queue.\n", __FUNCTION__, (tasklet->owner) ? tasklet->owner->pid : -1);
518 } 527 }
519 else { 528 else {
520 TRACE("%s: Pending tasklet (%d) does not have priority to run on this CPU (%d).\n", __FUNCTION__, (tasklet->owner) ? tasklet->owner->pid : -1, smp_processor_id()); 529 cluster->pending_tasklets.head = tasklet->next;
521 tasklet = NULL; 530 if(tasklet->next == NULL) {
531 TRACE("%s: Tasklet for %d is the last element in tasklet queue.\n", __FUNCTION__, tasklet->owner->pid);
532 cluster->pending_tasklets.tail = &(cluster->pending_tasklets.head);
533 }
522 } 534 }
523 } 535 }
524 else { 536 else {
@@ -527,8 +539,6 @@ static void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* sched_ta
527 539
528 raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags); 540 raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags);
529 541
530 TS_NV_SCHED_BOTISR_END;
531
532 if(tasklet) { 542 if(tasklet) {
533 __do_lit_tasklet(tasklet, 0ul); 543 __do_lit_tasklet(tasklet, 0ul);
534 tasklet = NULL; 544 tasklet = NULL;
@@ -536,29 +546,11 @@ static void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* sched_ta
536 else { 546 else {
537 work_to_do = 0; 547 work_to_do = 0;
538 } 548 }
539 }
540}
541
542
543static void run_tasklets(struct task_struct* sched_task)
544{
545 cedf_domain_t* cluster;
546 549
547 preempt_disable(); 550 TS_NV_SCHED_BOTISR_END;
548
549 cluster = (is_realtime(sched_task)) ?
550 task_cpu_cluster(sched_task) :
551 remote_cluster(smp_processor_id());
552
553 if(cluster && cluster->pending_tasklets.head != NULL) {
554 TRACE("%s: There are tasklets to process.\n", __FUNCTION__);
555 do_lit_tasklets(cluster, sched_task);
556 } 551 }
557
558 preempt_enable_no_resched();
559} 552}
560 553
561
562static void __add_pai_tasklet(struct tasklet_struct* tasklet, cedf_domain_t* cluster) 554static void __add_pai_tasklet(struct tasklet_struct* tasklet, cedf_domain_t* cluster)
563{ 555{
564 struct tasklet_struct* step; 556 struct tasklet_struct* step;
@@ -595,13 +587,13 @@ static void __add_pai_tasklet(struct tasklet_struct* tasklet, cedf_domain_t* clu
595 TRACE("%s: inserting tasklet for %d between %d and %d.\n", __FUNCTION__, 587 TRACE("%s: inserting tasklet for %d between %d and %d.\n", __FUNCTION__,
596 tasklet->owner->pid, 588 tasklet->owner->pid,
597 (step->owner) ? 589 (step->owner) ?
598 step->owner->pid : 590 step->owner->pid :
599 -1, 591 -1,
600 (step->next) ? 592 (step->next) ?
601 ((step->next->owner) ? 593 ((step->next->owner) ?
602 step->next->owner->pid : 594 step->next->owner->pid :
603 -1) : 595 -1) :
604 -1); 596 -1);
605 597
606 tasklet->next = step->next; 598 tasklet->next = step->next;
607 step->next = tasklet; 599 step->next = tasklet;
@@ -615,7 +607,27 @@ static void __add_pai_tasklet(struct tasklet_struct* tasklet, cedf_domain_t* clu
615 } 607 }
616} 608}
617 609
618static int enqueue_pai_tasklet(struct tasklet_struct* tasklet) 610static void cedf_run_tasklets(struct task_struct* sched_task)
611{
612 cedf_domain_t* cluster;
613
614 preempt_disable();
615
616 cluster = (is_realtime(sched_task)) ?
617 task_cpu_cluster(sched_task) :
618 remote_cluster(smp_processor_id());
619
620 if(cluster && cluster->pending_tasklets.head != NULL) {
621 TRACE("%s: There are tasklets to process.\n", __FUNCTION__);
622 do_lit_tasklets(cluster, sched_task);
623 }
624
625 preempt_enable_no_resched();
626}
627
628
629
630static int cedf_enqueue_pai_tasklet(struct tasklet_struct* tasklet)
619{ 631{
620 cedf_domain_t *cluster = NULL; 632 cedf_domain_t *cluster = NULL;
621 cpu_entry_t *targetCPU = NULL; 633 cpu_entry_t *targetCPU = NULL;
@@ -701,6 +713,25 @@ static int enqueue_pai_tasklet(struct tasklet_struct* tasklet)
701 return(1); // success 713 return(1); // success
702} 714}
703 715
716static void cedf_change_prio_pai_tasklet(struct task_struct *old_prio,
717 struct task_struct *new_prio)
718{
719 struct tasklet_struct* step;
720 unsigned long flags;
721 cedf_domain_t *cluster = task_cpu_cluster(old_prio);
722
723 if(cluster->pending_tasklets.head != NULL) {
724 raw_spin_lock_irqsave(&cluster->cluster_lock, flags);
725 for(step = cluster->pending_tasklets.head; step != NULL; step = step->next) {
726 if(step->owner == old_prio) {
727 TRACE("%s: Found tasklet to change: %d\n", __FUNCTION__, step->owner->pid);
728 step->owner = new_prio;
729 }
730 }
731 raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags);
732 }
733}
734
704#endif // PAI 735#endif // PAI
705 736
706/* Getting schedule() right is a bit tricky. schedule() may not make any 737/* Getting schedule() right is a bit tricky. schedule() may not make any
@@ -779,6 +810,14 @@ static struct task_struct* cedf_schedule(struct task_struct * prev)
779 if (blocks) 810 if (blocks)
780 unlink(entry->scheduled); 811 unlink(entry->scheduled);
781 812
813#if defined(CONFIG_LITMUS_NVIDIA) && defined(CONFIG_LITMUS_AFFINITY_LOCKING)
814 if(exists && is_realtime(entry->scheduled) && tsk_rt(entry->scheduled)->held_gpus) {
815 if(!blocks || tsk_rt(entry->scheduled)->suspend_gpu_tracker_on_block) {
816 stop_gpu_tracker(entry->scheduled);
817 }
818 }
819#endif
820
782 /* Request a sys_exit_np() call if we would like to preempt but cannot. 821 /* Request a sys_exit_np() call if we would like to preempt but cannot.
783 * We need to make sure to update the link structure anyway in case 822 * We need to make sure to update the link structure anyway in case
784 * that we are still linked. Multiple calls to request_exit_np() don't 823 * that we are still linked. Multiple calls to request_exit_np() don't
@@ -930,9 +969,9 @@ static void cedf_task_wake_up(struct task_struct *task)
930 } 969 }
931 } 970 }
932 } 971 }
933#endif 972#else
934
935 set_rt_flags(task, RT_F_RUNNING); // periodic model 973 set_rt_flags(task, RT_F_RUNNING); // periodic model
974#endif
936 975
937 if(tsk_rt(task)->linked_on == NO_CPU) 976 if(tsk_rt(task)->linked_on == NO_CPU)
938 cedf_job_arrival(task); 977 cedf_job_arrival(task);
@@ -964,7 +1003,7 @@ static void cedf_task_exit(struct task_struct * t)
964 cedf_domain_t *cluster = task_cpu_cluster(t); 1003 cedf_domain_t *cluster = task_cpu_cluster(t);
965 1004
966#ifdef CONFIG_LITMUS_PAI_SOFTIRQD 1005#ifdef CONFIG_LITMUS_PAI_SOFTIRQD
967 flush_tasklets(cluster, t); 1006 cedf_change_prio_pai_tasklet(t, NULL);
968#endif 1007#endif
969 1008
970 /* unlink if necessary */ 1009 /* unlink if necessary */
@@ -984,6 +1023,11 @@ static void cedf_task_exit(struct task_struct * t)
984 1023
985static long cedf_admit_task(struct task_struct* tsk) 1024static long cedf_admit_task(struct task_struct* tsk)
986{ 1025{
1026#ifdef CONFIG_LITMUS_NESTED_LOCKING
1027 INIT_BINHEAP_HANDLE(&tsk_rt(tsk)->hp_blocked_tasks,
1028 edf_max_heap_base_priority_order);
1029#endif
1030
987 return task_cpu(tsk) == tsk->rt_param.task_params.cpu ? 0 : -EINVAL; 1031 return task_cpu(tsk) == tsk->rt_param.task_params.cpu ? 0 : -EINVAL;
988} 1032}
989 1033
@@ -994,81 +1038,100 @@ static long cedf_admit_task(struct task_struct* tsk)
994#include <litmus/fdso.h> 1038#include <litmus/fdso.h>
995 1039
996 1040
997static void __set_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh) 1041
1042/* called with IRQs off */
1043static void __increase_priority_inheritance(struct task_struct* t,
1044 struct task_struct* prio_inh)
998{ 1045{
999 int linked_on; 1046 int linked_on;
1000 int check_preempt = 0; 1047 int check_preempt = 0;
1001 1048
1002 cedf_domain_t* cluster = task_cpu_cluster(t); 1049 cedf_domain_t* cluster = task_cpu_cluster(t);
1003 1050
1004 if(prio_inh != NULL) 1051#ifdef CONFIG_LITMUS_NESTED_LOCKING
1005 TRACE_TASK(t, "inherits priority from %s/%d\n", prio_inh->comm, prio_inh->pid); 1052 /* this sanity check allows for weaker locking in protocols */
1006 else 1053 /* TODO (klitirqd): Skip this check if 't' is a proxy thread (???) */
1007 TRACE_TASK(t, "inherits priority from %p\n", prio_inh); 1054 if(__edf_higher_prio(prio_inh, BASE, t, EFFECTIVE)) {
1008 1055#endif
1009 sched_trace_eff_prio_change(t, prio_inh); 1056 TRACE_TASK(t, "inherits priority from %s/%d\n",
1010 1057 prio_inh->comm, prio_inh->pid);
1011 tsk_rt(t)->inh_task = prio_inh; 1058 tsk_rt(t)->inh_task = prio_inh;
1012 1059
1013 linked_on = tsk_rt(t)->linked_on; 1060 linked_on = tsk_rt(t)->linked_on;
1014 1061
1015 /* If it is scheduled, then we need to reorder the CPU heap. */ 1062 /* If it is scheduled, then we need to reorder the CPU heap. */
1016 if (linked_on != NO_CPU) { 1063 if (linked_on != NO_CPU) {
1017 TRACE_TASK(t, "%s: linked on %d\n", 1064 TRACE_TASK(t, "%s: linked on %d\n",
1018 __FUNCTION__, linked_on); 1065 __FUNCTION__, linked_on);
1019 /* Holder is scheduled; need to re-order CPUs. 1066 /* Holder is scheduled; need to re-order CPUs.
1020 * We can't use heap_decrease() here since 1067 * We can't use heap_decrease() here since
1021 * the cpu_heap is ordered in reverse direction, so 1068 * the cpu_heap is ordered in reverse direction, so
1022 * it is actually an increase. */ 1069 * it is actually an increase. */
1023 bheap_delete(cpu_lower_prio, &cluster->cpu_heap, 1070 binheap_delete(&per_cpu(cedf_cpu_entries, linked_on).hn,
1024 per_cpu(cedf_cpu_entries, linked_on).hn); 1071 &cluster->cpu_heap);
1025 bheap_insert(cpu_lower_prio, &cluster->cpu_heap, 1072 binheap_add(&per_cpu(cedf_cpu_entries, linked_on).hn,
1026 per_cpu(cedf_cpu_entries, linked_on).hn); 1073 &cluster->cpu_heap, cpu_entry_t, hn);
1027 } else {
1028 /* holder may be queued: first stop queue changes */
1029 raw_spin_lock(&cluster->domain.release_lock);
1030 if (is_queued(t)) {
1031 TRACE_TASK(t, "%s: is queued\n", __FUNCTION__);
1032
1033 /* We need to update the position of holder in some
1034 * heap. Note that this could be a release heap if we
1035 * budget enforcement is used and this job overran. */
1036 check_preempt = !bheap_decrease(edf_ready_order, tsk_rt(t)->heap_node);
1037 1074
1038 } else { 1075 } else {
1039 /* Nothing to do: if it is not queued and not linked 1076 /* holder may be queued: first stop queue changes */
1040 * then it is either sleeping or currently being moved 1077 raw_spin_lock(&cluster->domain.release_lock);
1041 * by other code (e.g., a timer interrupt handler) that 1078 if (is_queued(t)) {
1042 * will use the correct priority when enqueuing the 1079 TRACE_TASK(t, "%s: is queued\n",
1043 * task. */ 1080 __FUNCTION__);
1044 TRACE_TASK(t, "%s: is NOT queued => Done.\n", __FUNCTION__); 1081 /* We need to update the position of holder in some
1045 } 1082 * heap. Note that this could be a release heap if we
1046 raw_spin_unlock(&cluster->domain.release_lock); 1083 * budget enforcement is used and this job overran. */
1047 1084 check_preempt =
1048 /* If holder was enqueued in a release heap, then the following 1085 !bheap_decrease(edf_ready_order, tsk_rt(t)->heap_node);
1049 * preemption check is pointless, but we can't easily detect 1086 } else {
1050 * that case. If you want to fix this, then consider that 1087 /* Nothing to do: if it is not queued and not linked
1051 * simply adding a state flag requires O(n) time to update when 1088 * then it is either sleeping or currently being moved
1052 * releasing n tasks, which conflicts with the goal to have 1089 * by other code (e.g., a timer interrupt handler) that
1053 * O(log n) merges. */ 1090 * will use the correct priority when enqueuing the
1054 if (check_preempt) { 1091 * task. */
1055 /* heap_decrease() hit the top level of the heap: make 1092 TRACE_TASK(t, "%s: is NOT queued => Done.\n",
1056 * sure preemption checks get the right task, not the 1093 __FUNCTION__);
1057 * potentially stale cache. */ 1094 }
1058 bheap_uncache_min(edf_ready_order, &cluster->domain.ready_queue); 1095 raw_spin_unlock(&cluster->domain.release_lock);
1059 check_for_preemptions(cluster); 1096
1097 /* If holder was enqueued in a release heap, then the following
1098 * preemption check is pointless, but we can't easily detect
1099 * that case. If you want to fix this, then consider that
1100 * simply adding a state flag requires O(n) time to update when
1101 * releasing n tasks, which conflicts with the goal to have
1102 * O(log n) merges. */
1103 if (check_preempt) {
1104 /* heap_decrease() hit the top level of the heap: make
1105 * sure preemption checks get the right task, not the
1106 * potentially stale cache. */
1107 bheap_uncache_min(edf_ready_order,
1108 &cluster->domain.ready_queue);
1109 check_for_preemptions(cluster);
1110 }
1060 } 1111 }
1112#ifdef CONFIG_LITMUS_NESTED_LOCKING
1061 } 1113 }
1114 else {
1115 TRACE_TASK(t, "Spurious invalid priority increase. "
1116 "Inheritance request: %s/%d [eff_prio = %s/%d] to inherit from %s/%d\n"
1117 "Occurance is likely okay: probably due to (hopefully safe) concurrent priority updates.\n",
1118 t->comm, t->pid,
1119 effective_priority(t)->comm, effective_priority(t)->pid,
1120 (prio_inh) ? prio_inh->comm : "nil",
1121 (prio_inh) ? prio_inh->pid : -1);
1122 WARN_ON(!prio_inh);
1123 }
1124#endif
1062} 1125}
1063 1126
1064/* called with IRQs off */ 1127/* called with IRQs off */
1065static void set_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh) 1128static void increase_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh)
1066{ 1129{
1067 cedf_domain_t* cluster = task_cpu_cluster(t); 1130 cedf_domain_t* cluster = task_cpu_cluster(t);
1068 1131
1069 raw_spin_lock(&cluster->cluster_lock); 1132 raw_spin_lock(&cluster->cluster_lock);
1070 1133
1071 __set_priority_inheritance(t, prio_inh); 1134 __increase_priority_inheritance(t, prio_inh);
1072 1135
1073#ifdef CONFIG_LITMUS_SOFTIRQD 1136#ifdef CONFIG_LITMUS_SOFTIRQD
1074 if(tsk_rt(t)->cur_klitirqd != NULL) 1137 if(tsk_rt(t)->cur_klitirqd != NULL)
@@ -1076,75 +1139,118 @@ static void set_priority_inheritance(struct task_struct* t, struct task_struct*
1076 TRACE_TASK(t, "%s/%d inherits a new priority!\n", 1139 TRACE_TASK(t, "%s/%d inherits a new priority!\n",
1077 tsk_rt(t)->cur_klitirqd->comm, tsk_rt(t)->cur_klitirqd->pid); 1140 tsk_rt(t)->cur_klitirqd->comm, tsk_rt(t)->cur_klitirqd->pid);
1078 1141
1079 __set_priority_inheritance(tsk_rt(t)->cur_klitirqd, prio_inh); 1142 __increase_priority_inheritance(tsk_rt(t)->cur_klitirqd, prio_inh);
1080 } 1143 }
1081#endif 1144#endif
1082 1145
1083 raw_spin_unlock(&cluster->cluster_lock); 1146 raw_spin_unlock(&cluster->cluster_lock);
1084}
1085 1147
1148#if defined(CONFIG_LITMUS_PAI_SOFTIRQD) && defined(CONFIG_LITMUS_NVIDIA)
1149 if(tsk_rt(t)->held_gpus) {
1150 int i;
1151 for(i = find_first_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus));
1152 i < NV_DEVICE_NUM;
1153 i = find_next_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus), i+1)) {
1154 pai_check_priority_increase(t, i);
1155 }
1156 }
1157#endif
1158}
1086 1159
1087/* called with IRQs off */ 1160/* called with IRQs off */
1088static void __clear_priority_inheritance(struct task_struct* t) 1161static void __decrease_priority_inheritance(struct task_struct* t,
1162 struct task_struct* prio_inh)
1089{ 1163{
1090 TRACE_TASK(t, "priority restored\n"); 1164#ifdef CONFIG_LITMUS_NESTED_LOCKING
1091 1165 if(__edf_higher_prio(t, EFFECTIVE, prio_inh, BASE)) {
1092 if(tsk_rt(t)->scheduled_on != NO_CPU) 1166#endif
1093 { 1167 /* A job only stops inheriting a priority when it releases a
1094 sched_trace_eff_prio_change(t, NULL); 1168 * resource. Thus we can make the following assumption.*/
1095 1169 if(prio_inh)
1096 tsk_rt(t)->inh_task = NULL; 1170 TRACE_TASK(t, "EFFECTIVE priority decreased to %s/%d\n",
1097 1171 prio_inh->comm, prio_inh->pid);
1098 /* Check if rescheduling is necessary. We can't use heap_decrease() 1172 else
1099 * since the priority was effectively lowered. */ 1173 TRACE_TASK(t, "base priority restored.\n");
1100 unlink(t);
1101 cedf_job_arrival(t);
1102 }
1103 else
1104 {
1105 __set_priority_inheritance(t, NULL);
1106 }
1107
1108#ifdef CONFIG_LITMUS_SOFTIRQD
1109 if(tsk_rt(t)->cur_klitirqd != NULL)
1110 {
1111 TRACE_TASK(t, "%s/%d inheritance set back to owner.\n",
1112 tsk_rt(t)->cur_klitirqd->comm, tsk_rt(t)->cur_klitirqd->pid);
1113 1174
1114 if(tsk_rt(tsk_rt(t)->cur_klitirqd)->scheduled_on != NO_CPU) 1175 tsk_rt(t)->inh_task = prio_inh;
1115 {
1116 sched_trace_eff_prio_change(tsk_rt(t)->cur_klitirqd, t);
1117 1176
1118 tsk_rt(tsk_rt(t)->cur_klitirqd)->inh_task = t; 1177 if(tsk_rt(t)->scheduled_on != NO_CPU) {
1178 TRACE_TASK(t, "is scheduled.\n");
1119 1179
1120 /* Check if rescheduling is necessary. We can't use heap_decrease() 1180 /* Check if rescheduling is necessary. We can't use heap_decrease()
1121 * since the priority was effectively lowered. */ 1181 * since the priority was effectively lowered. */
1122 unlink(tsk_rt(t)->cur_klitirqd); 1182 unlink(t);
1123 cedf_job_arrival(tsk_rt(t)->cur_klitirqd); 1183 cedf_job_arrival(t);
1124 } 1184 }
1125 else 1185 else {
1126 { 1186 cedf_domain_t* cluster = task_cpu_cluster(t);
1127 __set_priority_inheritance(tsk_rt(t)->cur_klitirqd, t); 1187 /* task is queued */
1188 raw_spin_lock(&cluster->domain.release_lock);
1189 if (is_queued(t)) {
1190 TRACE_TASK(t, "is queued.\n");
1191
1192 /* decrease in priority, so we have to re-add to binomial heap */
1193 unlink(t);
1194 cedf_job_arrival(t);
1195 }
1196 else {
1197 TRACE_TASK(t, "is not in scheduler. Probably on wait queue somewhere.\n");
1198 }
1199 raw_spin_unlock(&cluster->domain.release_lock);
1128 } 1200 }
1201#ifdef CONFIG_LITMUS_NESTED_LOCKING
1202 }
1203 else {
1204 TRACE_TASK(t, "Spurious invalid priority decrease. "
1205 "Inheritance request: %s/%d [eff_prio = %s/%d] to inherit from %s/%d\n"
1206 "Occurance is likely okay: probably due to (hopefully safe) concurrent priority updates.\n",
1207 t->comm, t->pid,
1208 effective_priority(t)->comm, effective_priority(t)->pid,
1209 (prio_inh) ? prio_inh->comm : "nil",
1210 (prio_inh) ? prio_inh->pid : -1);
1129 } 1211 }
1130#endif 1212#endif
1131} 1213}
1132 1214
1133/* called with IRQs off */ 1215static void decrease_priority_inheritance(struct task_struct* t,
1134static void clear_priority_inheritance(struct task_struct* t) 1216 struct task_struct* prio_inh)
1135{ 1217{
1136 cedf_domain_t* cluster = task_cpu_cluster(t); 1218 cedf_domain_t* cluster = task_cpu_cluster(t);
1137 1219
1138 raw_spin_lock(&cluster->cluster_lock); 1220 raw_spin_lock(&cluster->cluster_lock);
1139 __clear_priority_inheritance(t); 1221 __decrease_priority_inheritance(t, prio_inh);
1222
1223#ifdef CONFIG_LITMUS_SOFTIRQD
1224 if(tsk_rt(t)->cur_klitirqd != NULL)
1225 {
1226 TRACE_TASK(t, "%s/%d decreases in priority!\n",
1227 tsk_rt(t)->cur_klitirqd->comm, tsk_rt(t)->cur_klitirqd->pid);
1228
1229 __decrease_priority_inheritance(tsk_rt(t)->cur_klitirqd, prio_inh);
1230 }
1231#endif
1232
1140 raw_spin_unlock(&cluster->cluster_lock); 1233 raw_spin_unlock(&cluster->cluster_lock);
1234
1235#if defined(CONFIG_LITMUS_PAI_SOFTIRQD) && defined(CONFIG_LITMUS_NVIDIA)
1236 if(tsk_rt(t)->held_gpus) {
1237 int i;
1238 for(i = find_first_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus));
1239 i < NV_DEVICE_NUM;
1240 i = find_next_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus), i+1)) {
1241 pai_check_priority_decrease(t, i);
1242 }
1243 }
1244#endif
1141} 1245}
1142 1246
1143 1247
1144 1248
1249
1250
1145#ifdef CONFIG_LITMUS_SOFTIRQD 1251#ifdef CONFIG_LITMUS_SOFTIRQD
1146/* called with IRQs off */ 1252/* called with IRQs off */
1147static void set_priority_inheritance_klitirqd(struct task_struct* klitirqd, 1253static void increase_priority_inheritance_klitirqd(struct task_struct* klitirqd,
1148 struct task_struct* old_owner, 1254 struct task_struct* old_owner,
1149 struct task_struct* new_owner) 1255 struct task_struct* new_owner)
1150{ 1256{
@@ -1168,17 +1274,21 @@ static void set_priority_inheritance_klitirqd(struct task_struct* klitirqd,
1168 tsk_rt(new_owner)->cur_klitirqd = klitirqd; 1274 tsk_rt(new_owner)->cur_klitirqd = klitirqd;
1169 } 1275 }
1170 1276
1171 __set_priority_inheritance(klitirqd, 1277 __decrease_priority_inheritance(klitirqd, NULL); // kludge to clear out cur prio.
1172 (tsk_rt(new_owner)->inh_task == NULL) ? 1278
1173 new_owner : 1279 __increase_priority_inheritance(klitirqd,
1174 tsk_rt(new_owner)->inh_task); 1280 (tsk_rt(new_owner)->inh_task == NULL) ?
1281 new_owner :
1282 tsk_rt(new_owner)->inh_task);
1175 1283
1176 raw_spin_unlock(&cluster->cluster_lock); 1284 raw_spin_unlock(&cluster->cluster_lock);
1177} 1285}
1178 1286
1287
1179/* called with IRQs off */ 1288/* called with IRQs off */
1180static void clear_priority_inheritance_klitirqd(struct task_struct* klitirqd, 1289static void decrease_priority_inheritance_klitirqd(struct task_struct* klitirqd,
1181 struct task_struct* old_owner) 1290 struct task_struct* old_owner,
1291 struct task_struct* new_owner)
1182{ 1292{
1183 cedf_domain_t* cluster = task_cpu_cluster(klitirqd); 1293 cedf_domain_t* cluster = task_cpu_cluster(klitirqd);
1184 1294
@@ -1188,514 +1298,263 @@ static void clear_priority_inheritance_klitirqd(struct task_struct* klitirqd,
1188 1298
1189 TRACE_TASK(klitirqd, "priority restored\n"); 1299 TRACE_TASK(klitirqd, "priority restored\n");
1190 1300
1191 if(tsk_rt(klitirqd)->scheduled_on != NO_CPU) 1301 __decrease_priority_inheritance(klitirqd, new_owner);
1192 {
1193 tsk_rt(klitirqd)->inh_task = NULL;
1194
1195 /* Check if rescheduling is necessary. We can't use heap_decrease()
1196 * since the priority was effectively lowered. */
1197 unlink(klitirqd);
1198 cedf_job_arrival(klitirqd);
1199 }
1200 else
1201 {
1202 __set_priority_inheritance(klitirqd, NULL);
1203 }
1204 1302
1205 tsk_rt(old_owner)->cur_klitirqd = NULL; 1303 tsk_rt(old_owner)->cur_klitirqd = NULL;
1206 1304
1207 raw_spin_unlock(&cluster->cluster_lock); 1305 raw_spin_unlock(&cluster->cluster_lock);
1208} 1306}
1209#endif // CONFIG_LITMUS_SOFTIRQD 1307#endif // CONFIG_LITMUS_SOFTIRQD
1210
1211
1212/* ******************** KFMLP support ********************** */
1213
1214/* struct for semaphore with priority inheritance */
1215struct kfmlp_queue
1216{
1217 wait_queue_head_t wait;
1218 struct task_struct* owner;
1219 struct task_struct* hp_waiter;
1220 int count; /* number of waiters + holder */
1221};
1222
1223struct kfmlp_semaphore
1224{
1225 struct litmus_lock litmus_lock;
1226
1227 spinlock_t lock;
1228
1229 int num_resources; /* aka k */
1230 struct kfmlp_queue *queues; /* array */
1231 struct kfmlp_queue *shortest_queue; /* pointer to shortest queue */
1232};
1233
1234static inline struct kfmlp_semaphore* kfmlp_from_lock(struct litmus_lock* lock)
1235{
1236 return container_of(lock, struct kfmlp_semaphore, litmus_lock);
1237}
1238 1308
1239static inline int kfmlp_get_idx(struct kfmlp_semaphore* sem,
1240 struct kfmlp_queue* queue)
1241{
1242 return (queue - &sem->queues[0]);
1243}
1244 1309
1245static inline struct kfmlp_queue* kfmlp_get_queue(struct kfmlp_semaphore* sem,
1246 struct task_struct* holder)
1247{
1248 int i;
1249 for(i = 0; i < sem->num_resources; ++i)
1250 if(sem->queues[i].owner == holder)
1251 return(&sem->queues[i]);
1252 return(NULL);
1253}
1254 1310
1255/* caller is responsible for locking */
1256static struct task_struct* kfmlp_find_hp_waiter(struct kfmlp_queue *kqueue,
1257 struct task_struct *skip)
1258{
1259 struct list_head *pos;
1260 struct task_struct *queued, *found = NULL;
1261 1311
1262 list_for_each(pos, &kqueue->wait.task_list) {
1263 queued = (struct task_struct*) list_entry(pos, wait_queue_t,
1264 task_list)->private;
1265 1312
1266 /* Compare task prios, find high prio task. */
1267 if (queued != skip && edf_higher_prio(queued, found))
1268 found = queued;
1269 }
1270 return found;
1271}
1272 1313
1273static inline struct kfmlp_queue* kfmlp_find_shortest(
1274 struct kfmlp_semaphore* sem,
1275 struct kfmlp_queue* search_start)
1276{
1277 // we start our search at search_start instead of at the beginning of the
1278 // queue list to load-balance across all resources.
1279 struct kfmlp_queue* step = search_start;
1280 struct kfmlp_queue* shortest = sem->shortest_queue;
1281 1314
1282 do 1315#ifdef CONFIG_LITMUS_NESTED_LOCKING
1283 {
1284 step = (step+1 != &sem->queues[sem->num_resources]) ?
1285 step+1 : &sem->queues[0];
1286 if(step->count < shortest->count)
1287 {
1288 shortest = step;
1289 if(step->count == 0)
1290 break; /* can't get any shorter */
1291 }
1292 }while(step != search_start);
1293 1316
1294 return(shortest); 1317/* called with IRQs off */
1295} 1318/* preconditions:
1296 1319 (1) The 'hp_blocked_tasks_lock' of task 't' is held.
1297static struct task_struct* kfmlp_remove_hp_waiter(struct kfmlp_semaphore* sem) 1320 (2) The lock 'to_unlock' is held.
1321 */
1322static void nested_increase_priority_inheritance(struct task_struct* t,
1323 struct task_struct* prio_inh,
1324 raw_spinlock_t *to_unlock,
1325 unsigned long irqflags)
1298{ 1326{
1299 /* must hold sem->lock */ 1327 struct litmus_lock *blocked_lock = tsk_rt(t)->blocked_lock;
1300
1301 struct kfmlp_queue *my_queue = NULL;
1302 struct task_struct *max_hp = NULL;
1303 1328
1304 1329 if(tsk_rt(t)->inh_task != prio_inh) { // shield redundent calls.
1305 struct list_head *pos; 1330 increase_priority_inheritance(t, prio_inh); // increase our prio.
1306 struct task_struct *queued;
1307 int i;
1308
1309 for(i = 0; i < sem->num_resources; ++i)
1310 {
1311 if( (sem->queues[i].count > 1) &&
1312 ((my_queue == NULL) ||
1313 (edf_higher_prio(sem->queues[i].hp_waiter, my_queue->hp_waiter))) )
1314 {
1315 my_queue = &sem->queues[i];
1316 }
1317 } 1331 }
1318 1332
1319 if(my_queue) 1333 raw_spin_unlock(&tsk_rt(t)->hp_blocked_tasks_lock); // unlock the t's heap.
1320 {
1321 cedf_domain_t* cluster;
1322
1323 max_hp = my_queue->hp_waiter;
1324 BUG_ON(!max_hp);
1325
1326 TRACE_CUR("queue %d: stealing %s/%d from queue %d\n",
1327 kfmlp_get_idx(sem, my_queue),
1328 max_hp->comm, max_hp->pid,
1329 kfmlp_get_idx(sem, my_queue));
1330
1331 my_queue->hp_waiter = kfmlp_find_hp_waiter(my_queue, max_hp);
1332
1333 /*
1334 if(my_queue->hp_waiter)
1335 TRACE_CUR("queue %d: new hp_waiter is %s/%d\n",
1336 kfmlp_get_idx(sem, my_queue),
1337 my_queue->hp_waiter->comm,
1338 my_queue->hp_waiter->pid);
1339 else
1340 TRACE_CUR("queue %d: new hp_waiter is %p\n",
1341 kfmlp_get_idx(sem, my_queue), NULL);
1342 */
1343
1344 cluster = task_cpu_cluster(max_hp);
1345 1334
1346 raw_spin_lock(&cluster->cluster_lock);
1347 1335
1348 /* 1336 if(blocked_lock) {
1349 if(my_queue->owner) 1337 if(blocked_lock->ops->propagate_increase_inheritance) {
1350 TRACE_CUR("queue %d: owner is %s/%d\n", 1338 TRACE_TASK(t, "Inheritor is blocked (...perhaps). Checking lock %d.\n",
1351 kfmlp_get_idx(sem, my_queue), 1339 blocked_lock->ident);
1352 my_queue->owner->comm,
1353 my_queue->owner->pid);
1354 else
1355 TRACE_CUR("queue %d: owner is %p\n",
1356 kfmlp_get_idx(sem, my_queue),
1357 NULL);
1358 */
1359 1340
1360 if(tsk_rt(my_queue->owner)->inh_task == max_hp) 1341 // beware: recursion
1361 { 1342 blocked_lock->ops->propagate_increase_inheritance(blocked_lock,
1362 __clear_priority_inheritance(my_queue->owner); 1343 t, to_unlock,
1363 if(my_queue->hp_waiter != NULL) 1344 irqflags);
1364 {
1365 __set_priority_inheritance(my_queue->owner, my_queue->hp_waiter);
1366 }
1367 } 1345 }
1368 raw_spin_unlock(&cluster->cluster_lock); 1346 else {
1369 1347 TRACE_TASK(t, "Inheritor is blocked on lock (%d) that does not support nesting!\n",
1370 list_for_each(pos, &my_queue->wait.task_list) 1348 blocked_lock->ident);
1371 { 1349 unlock_fine_irqrestore(to_unlock, irqflags);
1372 queued = (struct task_struct*) list_entry(pos, wait_queue_t,
1373 task_list)->private;
1374 /* Compare task prios, find high prio task. */
1375 if (queued == max_hp)
1376 {
1377 /*
1378 TRACE_CUR("queue %d: found entry in wait queue. REMOVING!\n",
1379 kfmlp_get_idx(sem, my_queue));
1380 */
1381 __remove_wait_queue(&my_queue->wait,
1382 list_entry(pos, wait_queue_t, task_list));
1383 break;
1384 }
1385 } 1350 }
1386 --(my_queue->count);
1387 } 1351 }
1388 1352 else {
1389 return(max_hp); 1353 TRACE_TASK(t, "is not blocked. No propagation.\n");
1354 unlock_fine_irqrestore(to_unlock, irqflags);
1355 }
1390} 1356}
1391 1357
1392int cedf_kfmlp_lock(struct litmus_lock* l) 1358/* called with IRQs off */
1359/* preconditions:
1360 (1) The 'hp_blocked_tasks_lock' of task 't' is held.
1361 (2) The lock 'to_unlock' is held.
1362 */
1363static void nested_decrease_priority_inheritance(struct task_struct* t,
1364 struct task_struct* prio_inh,
1365 raw_spinlock_t *to_unlock,
1366 unsigned long irqflags)
1393{ 1367{
1394 struct task_struct* t = current; 1368 struct litmus_lock *blocked_lock = tsk_rt(t)->blocked_lock;
1395 struct kfmlp_semaphore *sem = kfmlp_from_lock(l); 1369 decrease_priority_inheritance(t, prio_inh);
1396 struct kfmlp_queue* my_queue;
1397 wait_queue_t wait;
1398 unsigned long flags;
1399
1400 if (!is_realtime(t))
1401 return -EPERM;
1402
1403 spin_lock_irqsave(&sem->lock, flags);
1404
1405 my_queue = sem->shortest_queue;
1406
1407 if (my_queue->owner) {
1408 /* resource is not free => must suspend and wait */
1409 TRACE_CUR("queue %d: Resource is not free => must suspend and wait.\n",
1410 kfmlp_get_idx(sem, my_queue));
1411
1412 init_waitqueue_entry(&wait, t);
1413 1370
1414 /* FIXME: interruptible would be nice some day */ 1371 raw_spin_unlock(&tsk_rt(t)->hp_blocked_tasks_lock); // unlock the t's heap.
1415 set_task_state(t, TASK_UNINTERRUPTIBLE);
1416 1372
1417 __add_wait_queue_tail_exclusive(&my_queue->wait, &wait); 1373 if(blocked_lock) {
1374 if(blocked_lock->ops->propagate_decrease_inheritance) {
1375 TRACE_TASK(t, "Inheritor is blocked (...perhaps). Checking lock %d.\n",
1376 blocked_lock->ident);
1418 1377
1419 /* check if we need to activate priority inheritance */ 1378 // beware: recursion
1420 if (edf_higher_prio(t, my_queue->hp_waiter)) 1379 blocked_lock->ops->propagate_decrease_inheritance(blocked_lock, t,
1421 { 1380 to_unlock,
1422 my_queue->hp_waiter = t; 1381 irqflags);
1423 if (edf_higher_prio(t, my_queue->owner))
1424 {
1425 set_priority_inheritance(my_queue->owner, my_queue->hp_waiter);
1426 }
1427 } 1382 }
1428 1383 else {
1429 ++(my_queue->count); 1384 TRACE_TASK(t, "Inheritor is blocked on lock (%p) that does not support nesting!\n",
1430 sem->shortest_queue = kfmlp_find_shortest(sem, my_queue); 1385 blocked_lock);
1431 1386 unlock_fine_irqrestore(to_unlock, irqflags);
1432 /* release lock before sleeping */
1433 spin_unlock_irqrestore(&sem->lock, flags);
1434
1435 /* We depend on the FIFO order. Thus, we don't need to recheck
1436 * when we wake up; we are guaranteed to have the lock since
1437 * there is only one wake up per release (or steal).
1438 */
1439 schedule();
1440
1441
1442 if(my_queue->owner == t)
1443 {
1444 TRACE_CUR("queue %d: acquired through waiting\n",
1445 kfmlp_get_idx(sem, my_queue));
1446 }
1447 else
1448 {
1449 /* this case may happen if our wait entry was stolen
1450 between queues. record where we went.*/
1451 my_queue = kfmlp_get_queue(sem, t);
1452 BUG_ON(!my_queue);
1453 TRACE_CUR("queue %d: acquired through stealing\n",
1454 kfmlp_get_idx(sem, my_queue));
1455 } 1387 }
1456 } 1388 }
1457 else 1389 else {
1458 { 1390 TRACE_TASK(t, "is not blocked. No propagation.\n");
1459 TRACE_CUR("queue %d: acquired immediately\n", 1391 unlock_fine_irqrestore(to_unlock, irqflags);
1460 kfmlp_get_idx(sem, my_queue));
1461
1462 my_queue->owner = t;
1463
1464 ++(my_queue->count);
1465 sem->shortest_queue = kfmlp_find_shortest(sem, my_queue);
1466
1467 spin_unlock_irqrestore(&sem->lock, flags);
1468 } 1392 }
1469
1470 return kfmlp_get_idx(sem, my_queue);
1471} 1393}
1472 1394
1473int cedf_kfmlp_unlock(struct litmus_lock* l)
1474{
1475 struct task_struct *t = current, *next;
1476 struct kfmlp_semaphore *sem = kfmlp_from_lock(l);
1477 struct kfmlp_queue *my_queue;
1478 unsigned long flags;
1479 int err = 0;
1480
1481 spin_lock_irqsave(&sem->lock, flags);
1482
1483 my_queue = kfmlp_get_queue(sem, t);
1484
1485 if (!my_queue) {
1486 err = -EINVAL;
1487 goto out;
1488 }
1489
1490 /* check if there are jobs waiting for this resource */
1491 next = __waitqueue_remove_first(&my_queue->wait);
1492 if (next) {
1493 /*
1494 TRACE_CUR("queue %d: ASSIGNING %s/%d as owner - next\n",
1495 kfmlp_get_idx(sem, my_queue),
1496 next->comm, next->pid);
1497 */
1498 /* next becomes the resouce holder */
1499 my_queue->owner = next;
1500 1395
1501 --(my_queue->count); 1396/* ******************** RSM MUTEX ********************** */
1502 if(my_queue->count < sem->shortest_queue->count)
1503 {
1504 sem->shortest_queue = my_queue;
1505 }
1506 1397
1507 TRACE_CUR("queue %d: lock ownership passed to %s/%d\n", 1398static struct litmus_lock_ops cedf_rsm_mutex_lock_ops = {
1508 kfmlp_get_idx(sem, my_queue), next->comm, next->pid); 1399 .lock = rsm_mutex_lock,
1509 1400 .unlock = rsm_mutex_unlock,
1510 /* determine new hp_waiter if necessary */ 1401 .close = rsm_mutex_close,
1511 if (next == my_queue->hp_waiter) { 1402 .deallocate = rsm_mutex_free,
1512 TRACE_TASK(next, "was highest-prio waiter\n");
1513 /* next has the highest priority --- it doesn't need to
1514 * inherit. However, we need to make sure that the
1515 * next-highest priority in the queue is reflected in
1516 * hp_waiter. */
1517 my_queue->hp_waiter = kfmlp_find_hp_waiter(my_queue, next);
1518 if (my_queue->hp_waiter)
1519 TRACE_TASK(my_queue->hp_waiter, "queue %d: is new highest-prio waiter\n", kfmlp_get_idx(sem, my_queue));
1520 else
1521 TRACE("queue %d: no further waiters\n", kfmlp_get_idx(sem, my_queue));
1522 } else {
1523 /* Well, if next is not the highest-priority waiter,
1524 * then it ought to inherit the highest-priority
1525 * waiter's priority. */
1526 set_priority_inheritance(next, my_queue->hp_waiter);
1527 }
1528 1403
1529 /* wake up next */ 1404 .propagate_increase_inheritance = rsm_mutex_propagate_increase_inheritance,
1530 wake_up_process(next); 1405 .propagate_decrease_inheritance = rsm_mutex_propagate_decrease_inheritance,
1531 }
1532 else
1533 {
1534 TRACE_CUR("queue %d: looking to steal someone...\n", kfmlp_get_idx(sem, my_queue));
1535 1406
1536 next = kfmlp_remove_hp_waiter(sem); /* returns NULL if nothing to steal */ 1407#ifdef CONFIG_LITMUS_DGL_SUPPORT
1537 1408 .dgl_lock = rsm_mutex_dgl_lock,
1538 /* 1409 .is_owner = rsm_mutex_is_owner,
1539 if(next) 1410 .enable_priority = rsm_mutex_enable_priority,
1540 TRACE_CUR("queue %d: ASSIGNING %s/%d as owner - steal\n", 1411#endif
1541 kfmlp_get_idx(sem, my_queue), 1412};
1542 next->comm, next->pid);
1543 */
1544 1413
1545 my_queue->owner = next; 1414static struct litmus_lock* cedf_new_rsm_mutex(void)
1415{
1416 return rsm_mutex_new(&cedf_rsm_mutex_lock_ops);
1417}
1546 1418
1547 if(next) 1419/* ******************** IKGLP ********************** */
1548 {
1549 TRACE_CUR("queue %d: lock ownership passed to %s/%d (which was stolen)\n",
1550 kfmlp_get_idx(sem, my_queue),
1551 next->comm, next->pid);
1552 1420
1553 /* wake up next */ 1421static struct litmus_lock_ops cedf_ikglp_lock_ops = {
1554 wake_up_process(next); 1422 .lock = ikglp_lock,
1555 } 1423 .unlock = ikglp_unlock,
1556 else 1424 .close = ikglp_close,
1557 { 1425 .deallocate = ikglp_free,
1558 TRACE_CUR("queue %d: no one to steal.\n", kfmlp_get_idx(sem, my_queue));
1559 1426
1560 --(my_queue->count); 1427 // ikglp can only be an outer-most lock.
1561 if(my_queue->count < sem->shortest_queue->count) 1428 .propagate_increase_inheritance = NULL,
1562 { 1429 .propagate_decrease_inheritance = NULL,
1563 sem->shortest_queue = my_queue; 1430};
1564 }
1565 }
1566 }
1567
1568 /* we lose the benefit of priority inheritance (if any) */
1569 if (tsk_rt(t)->inh_task)
1570 clear_priority_inheritance(t);
1571
1572out:
1573 spin_unlock_irqrestore(&sem->lock, flags);
1574 1431
1575 return err; 1432static struct litmus_lock* cedf_new_ikglp(void* __user arg)
1433{
1434 // assumes clusters of uniform size.
1435 return ikglp_new(cluster_size/num_clusters, &cedf_ikglp_lock_ops, arg);
1576} 1436}
1577 1437
1578int cedf_kfmlp_close(struct litmus_lock* l) 1438#endif /* CONFIG_LITMUS_NESTED_LOCKING */
1579{
1580 struct task_struct *t = current;
1581 struct kfmlp_semaphore *sem = kfmlp_from_lock(l);
1582 struct kfmlp_queue *my_queue;
1583 unsigned long flags;
1584 1439
1585 int owner;
1586 1440
1587 spin_lock_irqsave(&sem->lock, flags);
1588 1441
1589 my_queue = kfmlp_get_queue(sem, t);
1590 owner = (my_queue) ? (my_queue->owner == t) : 0;
1591 1442
1592 spin_unlock_irqrestore(&sem->lock, flags); 1443/* ******************** KFMLP support ********************** */
1593 1444
1594 if (owner) 1445static struct litmus_lock_ops cedf_kfmlp_lock_ops = {
1595 cedf_kfmlp_unlock(l); 1446 .lock = kfmlp_lock,
1447 .unlock = kfmlp_unlock,
1448 .close = kfmlp_close,
1449 .deallocate = kfmlp_free,
1450
1451 // kfmlp can only be an outer-most lock.
1452 .propagate_increase_inheritance = NULL,
1453 .propagate_decrease_inheritance = NULL,
1454};
1596 1455
1597 return 0;
1598}
1599 1456
1600void cedf_kfmlp_free(struct litmus_lock* l) 1457static struct litmus_lock* cedf_new_kfmlp(void* __user arg)
1601{ 1458{
1602 struct kfmlp_semaphore *sem = kfmlp_from_lock(l); 1459 return kfmlp_new(&cedf_kfmlp_lock_ops, arg);
1603 kfree(sem->queues);
1604 kfree(sem);
1605} 1460}
1606 1461
1607static struct litmus_lock_ops cedf_kfmlp_lock_ops = {
1608 .close = cedf_kfmlp_close,
1609 .lock = cedf_kfmlp_lock,
1610 .unlock = cedf_kfmlp_unlock,
1611 .deallocate = cedf_kfmlp_free,
1612};
1613 1462
1614static struct litmus_lock* cedf_new_kfmlp(void* __user arg, int* ret_code) 1463/* **** lock constructor **** */
1464
1465static long cedf_allocate_lock(struct litmus_lock **lock, int type,
1466 void* __user args)
1615{ 1467{
1616 struct kfmlp_semaphore* sem; 1468 int err;
1617 int num_resources = 0;
1618 int i;
1619 1469
1620 if(!access_ok(VERIFY_READ, arg, sizeof(num_resources))) 1470 /* GSN-EDF currently only supports the FMLP for global resources. */
1621 { 1471 switch (type) {
1622 *ret_code = -EINVAL; 1472#ifdef CONFIG_LITMUS_NESTED_LOCKING
1623 return(NULL); 1473 case RSM_MUTEX:
1624 } 1474 *lock = cedf_new_rsm_mutex();
1625 if(__copy_from_user(&num_resources, arg, sizeof(num_resources))) 1475 break;
1626 {
1627 *ret_code = -EINVAL;
1628 return(NULL);
1629 }
1630 if(num_resources < 1)
1631 {
1632 *ret_code = -EINVAL;
1633 return(NULL);
1634 }
1635 1476
1636 sem = kmalloc(sizeof(*sem), GFP_KERNEL); 1477 case IKGLP_SEM:
1637 if(!sem) 1478 *lock = cedf_new_ikglp(args);
1638 { 1479 break;
1639 *ret_code = -ENOMEM; 1480#endif
1640 return NULL; 1481 case KFMLP_SEM:
1641 } 1482 *lock = cedf_new_kfmlp(args);
1483 break;
1642 1484
1643 sem->queues = kmalloc(sizeof(struct kfmlp_queue)*num_resources, GFP_KERNEL); 1485 default:
1644 if(!sem->queues) 1486 err = -ENXIO;
1645 { 1487 goto UNSUPPORTED_LOCK;
1646 kfree(sem); 1488 };
1647 *ret_code = -ENOMEM;
1648 return NULL;
1649 }
1650 1489
1651 sem->litmus_lock.ops = &cedf_kfmlp_lock_ops; 1490 if (*lock)
1652 spin_lock_init(&sem->lock); 1491 err = 0;
1653 sem->num_resources = num_resources; 1492 else
1493 err = -ENOMEM;
1654 1494
1655 for(i = 0; i < num_resources; ++i) 1495UNSUPPORTED_LOCK:
1656 { 1496 return err;
1657 sem->queues[i].owner = NULL; 1497}
1658 sem->queues[i].hp_waiter = NULL;
1659 init_waitqueue_head(&sem->queues[i].wait);
1660 sem->queues[i].count = 0;
1661 }
1662 1498
1663 sem->shortest_queue = &sem->queues[0]; 1499#endif // CONFIG_LITMUS_LOCKING
1664 1500
1665 *ret_code = 0;
1666 return &sem->litmus_lock;
1667}
1668 1501
1502#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
1503static struct affinity_observer_ops cedf_kfmlp_affinity_ops = {
1504 .close = kfmlp_aff_obs_close,
1505 .deallocate = kfmlp_aff_obs_free,
1506};
1669 1507
1670/* **** lock constructor **** */ 1508#ifdef CONFIG_LITMUS_NESTED_LOCKING
1509static struct affinity_observer_ops cedf_ikglp_affinity_ops = {
1510 .close = ikglp_aff_obs_close,
1511 .deallocate = ikglp_aff_obs_free,
1512};
1513#endif
1671 1514
1672static long cedf_allocate_lock(struct litmus_lock **lock, int type, 1515static long cedf_allocate_affinity_observer(struct affinity_observer **aff_obs,
1673 void* __user arg) 1516 int type,
1517 void* __user args)
1674{ 1518{
1675 int err = -ENXIO; 1519 int err;
1676 1520
1677 /* C-EDF currently only supports the FMLP for global resources 1521 /* GSN-EDF currently only supports the FMLP for global resources. */
1678 WITHIN a given cluster. DO NOT USE CROSS-CLUSTER! */
1679 switch (type) { 1522 switch (type) {
1680 case KFMLP_SEM: 1523
1681 *lock = cedf_new_kfmlp(arg, &err); 1524 case KFMLP_SIMPLE_GPU_AFF_OBS:
1525 *aff_obs = kfmlp_simple_gpu_aff_obs_new(&cedf_kfmlp_affinity_ops, args);
1682 break; 1526 break;
1683 };
1684 1527
1685 return err; 1528 case KFMLP_GPU_AFF_OBS:
1686} 1529 *aff_obs = kfmlp_gpu_aff_obs_new(&cedf_kfmlp_affinity_ops, args);
1530 break;
1687 1531
1688#endif // CONFIG_LITMUS_LOCKING 1532#ifdef CONFIG_LITMUS_NESTED_LOCKING
1533 case IKGLP_SIMPLE_GPU_AFF_OBS:
1534 *aff_obs = ikglp_simple_gpu_aff_obs_new(&cedf_ikglp_affinity_ops, args);
1535 break;
1689 1536
1537 case IKGLP_GPU_AFF_OBS:
1538 *aff_obs = ikglp_gpu_aff_obs_new(&cedf_ikglp_affinity_ops, args);
1539 break;
1540#endif
1541 default:
1542 err = -ENXIO;
1543 goto UNSUPPORTED_AFF_OBS;
1544 };
1690 1545
1546 if (*aff_obs)
1547 err = 0;
1548 else
1549 err = -ENOMEM;
1691 1550
1551UNSUPPORTED_AFF_OBS:
1552 return err;
1553}
1554#endif
1692 1555
1693 1556
1694 1557
1695/* total number of cluster */
1696static int num_clusters;
1697/* we do not support cluster of different sizes */
1698static unsigned int cluster_size;
1699 1558
1700#ifdef VERBOSE_INIT 1559#ifdef VERBOSE_INIT
1701static void print_cluster_topology(cpumask_var_t mask, int cpu) 1560static void print_cluster_topology(cpumask_var_t mask, int cpu)
@@ -1710,8 +1569,6 @@ static void print_cluster_topology(cpumask_var_t mask, int cpu)
1710} 1569}
1711#endif 1570#endif
1712 1571
1713static int clusters_allocated = 0;
1714
1715static void cleanup_cedf(void) 1572static void cleanup_cedf(void)
1716{ 1573{
1717 int i; 1574 int i;
@@ -1798,6 +1655,10 @@ static long cedf_activate_plugin(void)
1798 /* cycle through cluster and add cpus to them */ 1655 /* cycle through cluster and add cpus to them */
1799 for (i = 0; i < num_clusters; i++) { 1656 for (i = 0; i < num_clusters; i++) {
1800 1657
1658#ifdef CONFIG_LITMUS_DGL_SUPPORT
1659 raw_spin_lock_init(&cedf[i].dgl_lock);
1660#endif
1661
1801 for_each_online_cpu(cpu) { 1662 for_each_online_cpu(cpu) {
1802 /* check if the cpu is already in a cluster */ 1663 /* check if the cpu is already in a cluster */
1803 for (j = 0; j < num_clusters; j++) 1664 for (j = 0; j < num_clusters; j++)
@@ -1830,7 +1691,6 @@ static long cedf_activate_plugin(void)
1830 entry->cluster = &cedf[i]; 1691 entry->cluster = &cedf[i];
1831 1692
1832 INIT_BINHEAP_NODE(&entry->hn); 1693 INIT_BINHEAP_NODE(&entry->hn);
1833 entry->in_heap = 0;
1834 1694
1835 cpu_count++; 1695 cpu_count++;
1836 1696
@@ -1899,18 +1759,31 @@ static struct sched_plugin cedf_plugin __cacheline_aligned_in_smp = {
1899 .task_block = cedf_task_block, 1759 .task_block = cedf_task_block,
1900 .admit_task = cedf_admit_task, 1760 .admit_task = cedf_admit_task,
1901 .activate_plugin = cedf_activate_plugin, 1761 .activate_plugin = cedf_activate_plugin,
1762 .compare = edf_higher_prio,
1902#ifdef CONFIG_LITMUS_LOCKING 1763#ifdef CONFIG_LITMUS_LOCKING
1903 .allocate_lock = cedf_allocate_lock, 1764 .allocate_lock = cedf_allocate_lock,
1904 .set_prio_inh = set_priority_inheritance, 1765 .increase_prio = increase_priority_inheritance,
1905 .clear_prio_inh = clear_priority_inheritance, 1766 .decrease_prio = decrease_priority_inheritance,
1767#endif
1768#ifdef CONFIG_LITMUS_NESTED_LOCKING
1769 .nested_increase_prio = nested_increase_priority_inheritance,
1770 .nested_decrease_prio = nested_decrease_priority_inheritance,
1771 .__compare = __edf_higher_prio,
1772#endif
1773#ifdef CONFIG_LITMUS_DGL_SUPPORT
1774 .get_dgl_spinlock = cedf_get_dgl_spinlock,
1775#endif
1776#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
1777 .allocate_aff_obs = cedf_allocate_affinity_observer,
1906#endif 1778#endif
1907#ifdef CONFIG_LITMUS_SOFTIRQD 1779#ifdef CONFIG_LITMUS_SOFTIRQD
1908 .set_prio_inh_klitirqd = set_priority_inheritance_klitirqd, 1780 .increase_prio_klitirqd = increase_priority_inheritance_klitirqd,
1909 .clear_prio_inh_klitirqd = clear_priority_inheritance_klitirqd, 1781 .decrease_prio_klitirqd = decrease_priority_inheritance_klitirqd,
1910#endif 1782#endif
1911#ifdef CONFIG_LITMUS_PAI_SOFTIRQD 1783#ifdef CONFIG_LITMUS_PAI_SOFTIRQD
1912 .enqueue_pai_tasklet = enqueue_pai_tasklet, 1784 .enqueue_pai_tasklet = cedf_enqueue_pai_tasklet,
1913 .run_tasklets = run_tasklets, 1785 .change_prio_pai_tasklet = cedf_change_prio_pai_tasklet,
1786 .run_tasklets = cedf_run_tasklets,
1914#endif 1787#endif
1915}; 1788};
1916 1789
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index f2c5f180e819..16f532d690cb 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -13,25 +13,22 @@
13#include <linux/sched.h> 13#include <linux/sched.h>
14#include <linux/slab.h> 14#include <linux/slab.h>
15#include <linux/uaccess.h> 15#include <linux/uaccess.h>
16 16#include <linux/module.h>
17
18#ifdef CONFIG_LITMUS_NESTED_LOCKING
19#include <linux/uaccess.h>
20#endif
21 17
22#include <litmus/litmus.h> 18#include <litmus/litmus.h>
23#include <litmus/jobs.h> 19#include <litmus/jobs.h>
24#include <litmus/sched_plugin.h> 20#include <litmus/sched_plugin.h>
25#include <litmus/edf_common.h> 21#include <litmus/edf_common.h>
26#include <litmus/sched_trace.h> 22#include <litmus/sched_trace.h>
27#include <litmus/trace.h>
28 23
29#include <litmus/preempt.h> 24#include <litmus/preempt.h>
30 25
31#include <litmus/bheap.h> 26#include <litmus/bheap.h>
32#include <litmus/binheap.h> 27#include <litmus/binheap.h>
33 28
29#ifdef CONFIG_LITMUS_LOCKING
34#include <litmus/kfmlp_lock.h> 30#include <litmus/kfmlp_lock.h>
31#endif
35 32
36#ifdef CONFIG_LITMUS_NESTED_LOCKING 33#ifdef CONFIG_LITMUS_NESTED_LOCKING
37#include <litmus/rsm_lock.h> 34#include <litmus/rsm_lock.h>
@@ -42,12 +39,6 @@
42#include <litmus/affinity.h> 39#include <litmus/affinity.h>
43#endif 40#endif
44 41
45#include <linux/module.h>
46
47#ifdef CONFIG_SCHED_CPU_AFFINITY
48#include <litmus/affinity.h>
49#endif
50
51#ifdef CONFIG_LITMUS_SOFTIRQD 42#ifdef CONFIG_LITMUS_SOFTIRQD
52#include <litmus/litmus_softirq.h> 43#include <litmus/litmus_softirq.h>
53#endif 44#endif
@@ -445,17 +436,24 @@ static void gsnedf_tick(struct task_struct* t)
445static void __do_lit_tasklet(struct tasklet_struct* tasklet, unsigned long flushed) 436static void __do_lit_tasklet(struct tasklet_struct* tasklet, unsigned long flushed)
446{ 437{
447 if (!atomic_read(&tasklet->count)) { 438 if (!atomic_read(&tasklet->count)) {
448 sched_trace_tasklet_begin(tasklet->owner); 439 if(tasklet->owner) {
440 sched_trace_tasklet_begin(tasklet->owner);
441 }
449 442
450 if (!test_and_clear_bit(TASKLET_STATE_SCHED, &tasklet->state)) 443 if (!test_and_clear_bit(TASKLET_STATE_SCHED, &tasklet->state))
451 { 444 {
452 BUG(); 445 BUG();
453 } 446 }
454 TRACE("%s: Invoking tasklet with owner pid = %d (flushed = %d).\n", __FUNCTION__, tasklet->owner->pid, flushed); 447 TRACE("%s: Invoking tasklet with owner pid = %d (flushed = %d).\n",
448 __FUNCTION__,
449 (tasklet->owner) ? tasklet->owner->pid : -1,
450 (tasklet->owner) ? 0 : 1);
455 tasklet->func(tasklet->data); 451 tasklet->func(tasklet->data);
456 tasklet_unlock(tasklet); 452 tasklet_unlock(tasklet);
457 453
458 sched_trace_tasklet_end(tasklet->owner, flushed); 454 if(tasklet->owner) {
455 sched_trace_tasklet_end(tasklet->owner, flushed);
456 }
459 } 457 }
460 else { 458 else {
461 BUG(); 459 BUG();
@@ -1130,8 +1128,6 @@ static void __increase_priority_inheritance(struct task_struct* t,
1130/* called with IRQs off */ 1128/* called with IRQs off */
1131static void increase_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh) 1129static void increase_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh)
1132{ 1130{
1133 int i = 0;
1134
1135 raw_spin_lock(&gsnedf_lock); 1131 raw_spin_lock(&gsnedf_lock);
1136 1132
1137 __increase_priority_inheritance(t, prio_inh); 1133 __increase_priority_inheritance(t, prio_inh);
@@ -1150,6 +1146,7 @@ static void increase_priority_inheritance(struct task_struct* t, struct task_str
1150 1146
1151#if defined(CONFIG_LITMUS_PAI_SOFTIRQD) && defined(CONFIG_LITMUS_NVIDIA) 1147#if defined(CONFIG_LITMUS_PAI_SOFTIRQD) && defined(CONFIG_LITMUS_NVIDIA)
1152 if(tsk_rt(t)->held_gpus) { 1148 if(tsk_rt(t)->held_gpus) {
1149 int i;
1153 for(i = find_first_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus)); 1150 for(i = find_first_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus));
1154 i < NV_DEVICE_NUM; 1151 i < NV_DEVICE_NUM;
1155 i = find_next_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus), i+1)) { 1152 i = find_next_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus), i+1)) {
@@ -1217,8 +1214,6 @@ static void __decrease_priority_inheritance(struct task_struct* t,
1217static void decrease_priority_inheritance(struct task_struct* t, 1214static void decrease_priority_inheritance(struct task_struct* t,
1218 struct task_struct* prio_inh) 1215 struct task_struct* prio_inh)
1219{ 1216{
1220 int i;
1221
1222 raw_spin_lock(&gsnedf_lock); 1217 raw_spin_lock(&gsnedf_lock);
1223 __decrease_priority_inheritance(t, prio_inh); 1218 __decrease_priority_inheritance(t, prio_inh);
1224 1219
@@ -1236,6 +1231,7 @@ static void decrease_priority_inheritance(struct task_struct* t,
1236 1231
1237#if defined(CONFIG_LITMUS_PAI_SOFTIRQD) && defined(CONFIG_LITMUS_NVIDIA) 1232#if defined(CONFIG_LITMUS_PAI_SOFTIRQD) && defined(CONFIG_LITMUS_NVIDIA)
1238 if(tsk_rt(t)->held_gpus) { 1233 if(tsk_rt(t)->held_gpus) {
1234 int i;
1239 for(i = find_first_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus)); 1235 for(i = find_first_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus));
1240 i < NV_DEVICE_NUM; 1236 i < NV_DEVICE_NUM;
1241 i = find_next_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus), i+1)) { 1237 i = find_next_bit(&tsk_rt(t)->held_gpus, sizeof(tsk_rt(t)->held_gpus), i+1)) {
@@ -1723,13 +1719,16 @@ static long gsnedf_allocate_affinity_observer(
1723 case KFMLP_SIMPLE_GPU_AFF_OBS: 1719 case KFMLP_SIMPLE_GPU_AFF_OBS:
1724 *aff_obs = kfmlp_simple_gpu_aff_obs_new(&gsnedf_kfmlp_affinity_ops, args); 1720 *aff_obs = kfmlp_simple_gpu_aff_obs_new(&gsnedf_kfmlp_affinity_ops, args);
1725 break; 1721 break;
1722
1726 case KFMLP_GPU_AFF_OBS: 1723 case KFMLP_GPU_AFF_OBS:
1727 *aff_obs = kfmlp_gpu_aff_obs_new(&gsnedf_kfmlp_affinity_ops, args); 1724 *aff_obs = kfmlp_gpu_aff_obs_new(&gsnedf_kfmlp_affinity_ops, args);
1728 break; 1725 break;
1726
1729#ifdef CONFIG_LITMUS_NESTED_LOCKING 1727#ifdef CONFIG_LITMUS_NESTED_LOCKING
1730 case IKGLP_SIMPLE_GPU_AFF_OBS: 1728 case IKGLP_SIMPLE_GPU_AFF_OBS:
1731 *aff_obs = ikglp_simple_gpu_aff_obs_new(&gsnedf_ikglp_affinity_ops, args); 1729 *aff_obs = ikglp_simple_gpu_aff_obs_new(&gsnedf_ikglp_affinity_ops, args);
1732 break; 1730 break;
1731
1733 case IKGLP_GPU_AFF_OBS: 1732 case IKGLP_GPU_AFF_OBS:
1734 *aff_obs = ikglp_gpu_aff_obs_new(&gsnedf_ikglp_affinity_ops, args); 1733 *aff_obs = ikglp_gpu_aff_obs_new(&gsnedf_ikglp_affinity_ops, args);
1735 break; 1734 break;
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-21 05:55:49 -0500