diff options
author | Glenn Elliott <gelliott@cs.unc.edu> | 2012-04-25 17:31:08 -0400 |
---|---|---|
committer | Glenn Elliott <gelliott@cs.unc.edu> | 2012-04-25 17:31:08 -0400 |
commit | 58f04ff13ac7128609ee468eb317c71817474a84 (patch) | |
tree | 6d443d96d0745e54fedc1ff0673e0f3f1cddc49f | |
parent | 4aabc4a7f68aae11c79b39fa65a9c54d3f3451e7 (diff) |
Port rtss12 features to C-EDF (untested)
-rw-r--r-- | include/litmus/ikglp_lock.h | 2 | ||||
-rw-r--r-- | include/litmus/rt_param.h | 1 | ||||
-rw-r--r-- | litmus/ikglp_lock.c | 457 | ||||
-rw-r--r-- | litmus/locking.c | 6 | ||||
-rw-r--r-- | litmus/sched_cedf.c | 1095 | ||||
-rw-r--r-- | litmus/sched_gsn_edf.c | 37 |
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 | ||
143 | static inline struct ikglp_affinity* ikglp_aff_obs_from_aff_obs(struct affinity_observer* aff_obs) | 145 | static 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 | |||
15 | int ikglp_max_heap_base_priority_order(struct binheap_node *a, | 18 | int 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 | |||
878 | int ikglp_lock(struct litmus_lock* l) | 883 | int 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 | ||
975 | acquired: | ||
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 | |||
982 | static void ikglp_move_donor_to_fq(struct ikglp_semaphore *sem, | 1092 | static 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 | |||
2113 | static 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 | |||
2150 | out: | ||
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 | |||
1939 | ikglp_wait_state_t* gpu_ikglp_advise_steal(struct ikglp_affinity* aff, | 2162 | ikglp_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 | |||
2197 | out: | ||
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 |
108 | struct tasklet_head | 117 | struct 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 */ | ||
157 | static int num_clusters; | ||
158 | /* we do not support cluster of different sizes */ | ||
159 | static unsigned int cluster_size; | ||
160 | |||
161 | static int clusters_allocated = 0; | ||
162 | |||
163 | #ifdef CONFIG_LITMUS_DGL_SUPPORT | ||
164 | static 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 | ||
467 | static 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 | |||
489 | static void do_lit_tasklets(cedf_domain_t* cluster, struct task_struct* sched_task) | 497 | static 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 | |||
543 | static 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 | |||
562 | static void __add_pai_tasklet(struct tasklet_struct* tasklet, cedf_domain_t* cluster) | 554 | static 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 | ||
618 | static int enqueue_pai_tasklet(struct tasklet_struct* tasklet) | 610 | static 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 | |||
630 | static 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 | ||
716 | static 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 | ||
985 | static long cedf_admit_task(struct task_struct* tsk) | 1024 | static 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 | ||
997 | static void __set_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh) | 1041 | |
1042 | /* called with IRQs off */ | ||
1043 | static 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 */ |
1065 | static void set_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh) | 1128 | static 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 */ |
1088 | static void __clear_priority_inheritance(struct task_struct* t) | 1161 | static 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 */ | 1215 | static void decrease_priority_inheritance(struct task_struct* t, |
1134 | static 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 */ |
1147 | static void set_priority_inheritance_klitirqd(struct task_struct* klitirqd, | 1253 | static 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 */ |
1180 | static void clear_priority_inheritance_klitirqd(struct task_struct* klitirqd, | 1289 | static 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 */ | ||
1215 | struct 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 | |||
1223 | struct 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 | |||
1234 | static 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 | ||
1239 | static inline int kfmlp_get_idx(struct kfmlp_semaphore* sem, | ||
1240 | struct kfmlp_queue* queue) | ||
1241 | { | ||
1242 | return (queue - &sem->queues[0]); | ||
1243 | } | ||
1244 | 1309 | ||
1245 | static 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 */ | ||
1256 | static 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 | ||
1273 | static 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. | |
1297 | static struct task_struct* kfmlp_remove_hp_waiter(struct kfmlp_semaphore* sem) | 1320 | (2) The lock 'to_unlock' is held. |
1321 | */ | ||
1322 | static 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 | ||
1392 | int 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 | */ | ||
1363 | static 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 | ||
1473 | int 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", | 1398 | static 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; | 1414 | static 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 */ | 1421 | static 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 | |||
1572 | out: | ||
1573 | spin_unlock_irqrestore(&sem->lock, flags); | ||
1574 | 1431 | ||
1575 | return err; | 1432 | static 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 | ||
1578 | int 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) | 1445 | static 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 | ||
1600 | void cedf_kfmlp_free(struct litmus_lock* l) | 1457 | static 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 | ||
1607 | static 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 | ||
1614 | static struct litmus_lock* cedf_new_kfmlp(void* __user arg, int* ret_code) | 1463 | /* **** lock constructor **** */ |
1464 | |||
1465 | static 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) | 1495 | UNSUPPORTED_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 | ||
1503 | static 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 |
1509 | static 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 | ||
1672 | static long cedf_allocate_lock(struct litmus_lock **lock, int type, | 1515 | static 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 | ||
1551 | UNSUPPORTED_AFF_OBS: | ||
1552 | return err; | ||
1553 | } | ||
1554 | #endif | ||
1692 | 1555 | ||
1693 | 1556 | ||
1694 | 1557 | ||
1695 | /* total number of cluster */ | ||
1696 | static int num_clusters; | ||
1697 | /* we do not support cluster of different sizes */ | ||
1698 | static unsigned int cluster_size; | ||
1699 | 1558 | ||
1700 | #ifdef VERBOSE_INIT | 1559 | #ifdef VERBOSE_INIT |
1701 | static void print_cluster_topology(cpumask_var_t mask, int cpu) | 1560 | static 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 | ||
1713 | static int clusters_allocated = 0; | ||
1714 | |||
1715 | static void cleanup_cedf(void) | 1572 | static 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) | |||
445 | static void __do_lit_tasklet(struct tasklet_struct* tasklet, unsigned long flushed) | 436 | static 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 */ |
1131 | static void increase_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh) | 1129 | static 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, | |||
1217 | static void decrease_priority_inheritance(struct task_struct* t, | 1214 | static 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; |