Tested/Fixed IKGLP heurs. OS WORK FINALLY DONE!

5 files changed, 132 insertions, 63 deletions

diff --git a/include/litmus/ikglp_lock.h b/include/litmus/ikglp_lock.h
index dd4f14e4eaff..eb017d48410a 100644
--- a/include/litmus/ikglp_lock.h
+++ b/include/litmus/ikglp_lock.h
@@ -120,7 +120,7 @@ struct ikglp_affinity_ops
         struct fifo_queue* (*advise_enqueue)(struct ikglp_affinity* aff, struct task_struct* t);        // select FIFO
         ikglp_wait_state_t* (*advise_steal)(struct ikglp_affinity* aff, struct fifo_queue* dst);        // select steal from FIFO
         ikglp_donee_heap_node_t* (*advise_donee_selection)(struct ikglp_affinity* aff, struct task_struct* t);  // select a donee
-        ikglp_wait_state_t* (*advise_doner_to_fq)(struct ikglp_affinity* aff, struct fifo_queue* dst);  // select a donor to move to PQ
+        ikglp_wait_state_t* (*advise_donor_to_fq)(struct ikglp_affinity* aff, struct fifo_queue* dst);  // select a donor to move to PQ
 
         void (*notify_enqueue)(struct ikglp_affinity* aff, struct fifo_queue* fq, struct task_struct* t);       // fifo enqueue
         void (*notify_dequeue)(struct ikglp_affinity* aff, struct fifo_queue* fq, struct task_struct* t);       // fifo dequeue
diff --git a/include/litmus/sched_plugin.h b/include/litmus/sched_plugin.h
index f0b464207e14..24a6858b4b0b 100644
--- a/include/litmus/sched_plugin.h
+++ b/include/litmus/sched_plugin.h
@@ -63,6 +63,7 @@ typedef void (*task_exit_t)    (struct task_struct *);
 typedef long (*allocate_lock_t) (struct litmus_lock **lock, int type,
                                  void* __user config);
 
+struct affinity_observer;
 typedef long (*allocate_affinity_observer_t) (
                                                                 struct affinity_observer **aff_obs, int type,
                                                                 void* __user config);
diff --git a/litmus/fdso.c b/litmus/fdso.c
index 0fc74be7f5ee..18fc61b6414a 100644
--- a/litmus/fdso.c
+++ b/litmus/fdso.c
@@ -20,7 +20,9 @@
 
 extern struct fdso_ops generic_lock_ops;
 
+#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
 extern struct fdso_ops generic_affinity_ops;
+#endif
 
 static const struct fdso_ops* fdso_ops[] = {
         &generic_lock_ops, /* FMLP_SEM */
@@ -28,10 +30,12 @@ static const struct fdso_ops* fdso_ops[] = {
         &generic_lock_ops, /* RSM_MUTEX */
         &generic_lock_ops, /* IKGLP_SEM */
         &generic_lock_ops, /* KFMLP_SEM */
+#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
         &generic_affinity_ops, /* IKGLP_SIMPLE_GPU_AFF_OBS */
         &generic_affinity_ops, /* IKGLP_GPU_AFF_OBS */
         &generic_affinity_ops, /* KFMLP_SIMPLE_GPU_AFF_OBS */
         &generic_affinity_ops, /* KFMLP_GPU_AFF_OBS */
+#endif
 };
 
 static int fdso_create(void** obj_ref, obj_type_t type, void* __user config)
diff --git a/litmus/ikglp_lock.c b/litmus/ikglp_lock.c
index 1a5d674b26a5..b7e23029b849 100644
--- a/litmus/ikglp_lock.c
+++ b/litmus/ikglp_lock.c
@@ -660,7 +660,7 @@ static void __ikglp_enqueue_on_fq(struct ikglp_semaphore *sem,
                 ikglp_add_donees(sem, fq, t, donee_heap_node);
         }
 
-        if(likely(sem->shortest_fifo_queue == fq)) {
+        if(sem->shortest_fifo_queue == fq) {
                 sem->shortest_fifo_queue = ikglp_find_shortest(sem, fq);
         }
 
@@ -912,7 +912,7 @@ int ikglp_lock(struct litmus_lock* l)
 
         if(fq->count == 0) {
                 // take available resource
-                //replica = ikglp_get_idx(sem, fq);
+                replica = ikglp_get_idx(sem, fq);
 
                 ikglp_get_immediate(t, fq, sem, flags);  // unlocks sem->lock
 
@@ -964,7 +964,7 @@ int ikglp_lock(struct litmus_lock* l)
                 fq = ikglp_get_queue(sem, t);
                 BUG_ON(!fq);
 
-                //replica = ikglp_get_idx(sem, fq);
+                replica = ikglp_get_idx(sem, fq);
         }
 
         TRACE_CUR("Acquired lock %d, queue %d\n",
@@ -976,7 +976,7 @@ int ikglp_lock(struct litmus_lock* l)
         }
 #endif
 
-        return ikglp_get_idx(sem, fq);
+        return replica;
 }
 
 static void ikglp_move_donor_to_fq(struct ikglp_semaphore *sem,
@@ -1184,15 +1184,7 @@ int ikglp_unlock(struct litmus_lock* l)
         unsigned long flags = 0, real_flags;
 
         int err = 0;
-
-
-        fq = ikglp_get_queue(sem, t);  // returns NULL if 't' is not owner.
-
-        if (!fq) {
-                err = -EINVAL;
-                goto out;
-        }
-
+        
 #ifdef CONFIG_LITMUS_DGL_SUPPORT
         dgl_lock = litmus->get_dgl_spinlock(t);
 #endif
@@ -1201,6 +1193,14 @@ int ikglp_unlock(struct litmus_lock* l)
         lock_global_irqsave(dgl_lock, flags);  // TODO: Push this deeper
         lock_fine_irqsave(&sem->lock, flags);
 
+        
+        fq = ikglp_get_queue(sem, t);  // returns NULL if 't' is not owner.
+        
+        if (!fq) {
+                err = -EINVAL;
+                goto out;
+        }       
+        
         TRACE_TASK(t, "Freeing replica %d.\n", ikglp_get_idx(sem, fq));
 
 
@@ -1223,7 +1223,7 @@ int ikglp_unlock(struct litmus_lock* l)
 
         // Move the next request into the FQ and update heaps as needed.
         // We defer re-evaluation of priorities to later in the function.
-        if(fq->donee_heap_node.donor_info) {  // move my doner to FQ
+        if(fq->donee_heap_node.donor_info) {  // move my donor to FQ
                 ikglp_wait_state_t *donor_info = fq->donee_heap_node.donor_info;
 
                 new_on_fq = donor_info->task;
@@ -1240,7 +1240,7 @@ int ikglp_unlock(struct litmus_lock* l)
                 // Select a donor
 #ifdef CONFIG_LITMUS_AFFINITY_LOCKING
                 other_donor_info = (sem->aff_obs) ?
-                        sem->aff_obs->ops->advise_doner_to_fq(sem->aff_obs, fq) :
+                        sem->aff_obs->ops->advise_donor_to_fq(sem->aff_obs, fq) :
                         binheap_top_entry(&sem->donors, ikglp_wait_state_t, node);
 #else
                 other_donor_info = binheap_top_entry(&sem->donors, ikglp_wait_state_t, node);
@@ -1784,7 +1784,7 @@ static struct affinity_observer* ikglp_aff_obs_new(struct affinity_observer_ops*
         ikglp_aff->nr_simult = aff_args.nr_simult_users;
         ikglp_aff->nr_rsrc = sem->nr_replicas / ikglp_aff->nr_simult;
 
-        memset(ikglp_aff->nr_cur_users_on_rsrc, 0, sizeof(int)*(sem->nr_replicas / ikglp_aff->nr_rsrc));
+        memset(ikglp_aff->nr_cur_users_on_rsrc, 0, sizeof(int)*(ikglp_aff->nr_rsrc));
 
         for(i = 0; i < sem->nr_replicas; ++i) {
                 ikglp_aff->q_info[i].q = &sem->fifo_queues[i];
@@ -1882,37 +1882,42 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
                           min_len);
 
         for(i = 0; i < sem->nr_replicas; ++i) {
-                if((&aff->q_info[i] != shortest) &&
-                   (aff->q_info[i].q->count < sem->max_fifo_len)) {
+                if(&aff->q_info[i] != shortest) {
+                        if(aff->q_info[i].q->count < sem->max_fifo_len) {
 
-                        lt_t est_len =
-                                aff->q_info[i].estimated_len +
-                                get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu,
+                                lt_t est_len =
+                                        aff->q_info[i].estimated_len +
+                                        get_gpu_estimate(t,
+                                                                gpu_migration_distance(tsk_rt(t)->last_gpu,
                                                                                                         replica_to_gpu(aff, i)));
 
-                        // queue is smaller, or they're equal and the other has a smaller number
-                        // of total users.
-                        //
-                        // tie-break on the shortest number of simult users.  this only kicks in
-                        // when there are more than 1 empty queues.
-                        if((est_len < min_len) ||
-                           ((est_len == min_len) && (*(aff->q_info[i].nr_cur_users) < min_nr_users))) {
-                                shortest = &aff->q_info[i];
-                                min_len = est_len;
-                                min_nr_users = *(aff->q_info[i].nr_cur_users);
-                        }
+                // queue is smaller, or they're equal and the other has a smaller number
+                // of total users.
+                //
+                // tie-break on the shortest number of simult users.  this only kicks in
+                // when there are more than 1 empty queues.
+                                if((shortest->q->count >= sem->max_fifo_len) || /* 'shortest' is full and i-th queue is not */
+                                   (est_len < min_len) ||                                               /* i-th queue has shortest length */
+                                   ((est_len == min_len) &&                                             /* equal lengths, but one has fewer over-all users */
+                                        (*(aff->q_info[i].nr_cur_users) < min_nr_users))) {
+                                           
+                                        shortest = &aff->q_info[i];
+                                        min_len = est_len;
+                                        min_nr_users = *(aff->q_info[i].nr_cur_users);
+                                }
 
-                        TRACE_CUR("cs is %llu on queue %d (count = %d): est len = %llu\n",
-                                          get_gpu_estimate(t,
-                                                        gpu_migration_distance(tsk_rt(t)->last_gpu,
-                                                                                                   replica_to_gpu(aff, i))),
-                                          ikglp_get_idx(sem, aff->q_info[i].q),
-                                          aff->q_info[i].q->count,
-                                          est_len);
-                }
-                else {
-                        TRACE_CUR("queue %d is too long.  ineligible for enqueue.\n",
-                                          ikglp_get_idx(sem, aff->q_info[i].q));
+                                TRACE_CUR("cs is %llu on queue %d (count = %d): est len = %llu\n",
+                                                  get_gpu_estimate(t,
+                                                                gpu_migration_distance(tsk_rt(t)->last_gpu,
+                                                                                                           replica_to_gpu(aff, i))),
+                                                  ikglp_get_idx(sem, aff->q_info[i].q),
+                                                  aff->q_info[i].q->count,
+                                                  est_len);
+                        }
+                        else {
+                                TRACE_CUR("queue %d is too long.  ineligible for enqueue.\n",
+                                                  ikglp_get_idx(sem, aff->q_info[i].q));
+                        }
                 }
         }
         
@@ -1959,8 +1964,16 @@ static ikglp_donee_heap_node_t* pick_donee(struct ikglp_affinity* aff,
         ikglp_donee_heap_node_t *donee_node;
         struct task_struct *mth_highest = ikglp_mth_highest(sem);
         
+        lt_t now = litmus_clock();
+        
+//      TRACE_CUR("fq %d: mth_highest: %s/%d, deadline = %d: (donor) = ??? ",
+//                        ikglp_get_idx(sem, fq),
+//                        mth_highest->comm, mth_highest->pid,
+//                        (int)get_deadline(mth_highest) - now);                          
+        
         if(fq->owner &&
-           fq->donee_heap_node.donor_info != NULL &&
+           fq->donee_heap_node.donor_info == NULL &&
+           mth_highest != fq->owner && 
            litmus->__compare(mth_highest, BASE, fq->owner, BASE)) {
                 donee = fq->owner;
                 donee_node = &(fq->donee_heap_node);
@@ -1976,6 +1989,20 @@ static ikglp_donee_heap_node_t* pick_donee(struct ikglp_affinity* aff,
         else if(waitqueue_active(&fq->wait)) {
                 struct list_head        *pos;
                 
+                
+//              TRACE_CUR("fq %d: owner: %s/%d, deadline = %d: (donor) = %s/%d "
+//                                "(mth_highest != fq->owner) = %d "
+//                                "(mth_highest > fq->owner) = %d\n",
+//                                ikglp_get_idx(sem, fq),
+//                                (fq->owner) ? fq->owner->comm : "nil",
+//                                (fq->owner) ? fq->owner->pid : -1,
+//                                (fq->owner) ? (int)get_deadline(fq->owner) - now : -999,
+//                                (fq->donee_heap_node.donor_info) ? fq->donee_heap_node.donor_info->task->comm : "nil",
+//                                (fq->donee_heap_node.donor_info) ? fq->donee_heap_node.donor_info->task->pid : -1,
+//                                (mth_highest != fq->owner),
+//                                (litmus->__compare(mth_highest, BASE, fq->owner, BASE)));
+                
+                
                 *dist_from_head = 1;
                 
                 // iterating from the start of the queue is nice since this means
@@ -1983,7 +2010,22 @@ static ikglp_donee_heap_node_t* pick_donee(struct ikglp_affinity* aff,
                 list_for_each(pos, &fq->wait.task_list) {
                         wait_queue_t *fq_wait = list_entry(pos, wait_queue_t, task_list);
                         ikglp_wait_state_t *wait = container_of(fq_wait, ikglp_wait_state_t, fq_node);
+                        
+//                      TRACE_CUR("fq %d: waiter %d: %s/%d, deadline = %d (donor) = %s/%d "
+//                                        "(mth_highest != wait->task) = %d "
+//                                        "(mth_highest > wait->task) = %d\n",
+//                                        ikglp_get_idx(sem, fq),
+//                                        dist_from_head,
+//                                        wait->task->comm, wait->task->pid,
+//                                        (int)get_deadline(wait->task) - now,
+//                                        (wait->donee_heap_node.donor_info) ? wait->donee_heap_node.donor_info->task->comm : "nil",
+//                                        (wait->donee_heap_node.donor_info) ? wait->donee_heap_node.donor_info->task->pid : -1,
+//                                        (mth_highest != wait->task),
+//                                        (litmus->__compare(mth_highest, BASE, wait->task, BASE)));                    
+                        
+                        
                         if(!has_donor(fq_wait) &&
+                           mth_highest != wait->task &&
                            litmus->__compare(mth_highest, BASE, wait->task, BASE)) {
                                 donee = (struct task_struct*) fq_wait->private;
                                 donee_node = &wait->donee_heap_node;
@@ -1997,8 +2039,6 @@ static ikglp_donee_heap_node_t* pick_donee(struct ikglp_affinity* aff,
                         }
                         ++(*dist_from_head);
                 }
-                
-                WARN_ON(1);
         }
         
         donee = NULL;
@@ -2120,16 +2160,17 @@ ikglp_donee_heap_node_t* gpu_ikglp_advise_donee_selection(
         default_donee->donor_info = default_donee_donor_info;
 
         if(!donee_node) {
+                donee_node = default_donee;             
+                
                 TRACE_CUR("Could not find a donee. We have to steal one.\n");
                 WARN_ON(default_donee->donor_info == NULL);
-                
-                donee_node = default_donee;
         }
         
 out:
         
-        TRACE_CUR("Selected donee %s/%d from GPU %d for %s/%d with affinity for GPU %d\n",
+        TRACE_CUR("Selected donee %s/%d on fq %d (GPU %d) for %s/%d with affinity for GPU %d\n",
                           donee_node->task->comm, donee_node->task->pid,
+                          ikglp_get_idx(sem, donee_node->fq),
                           replica_to_gpu(aff, ikglp_get_idx(sem, donee_node->fq)),
                           donor->comm, donor->pid, tsk_rt(donor)->last_gpu);
 
@@ -2149,6 +2190,11 @@ static void __find_closest_donor(int target_gpu,
         int this_dist =
                 gpu_migration_distance(target_gpu, tsk_rt(this_donor->task)->last_gpu);
         
+//      TRACE_CUR("%s/%d: dist from target = %d\n",
+//                        this_donor->task->comm,
+//                        this_donor->task->pid,
+//                        this_dist);
+        
         if(this_dist < *cur_dist) {
                 // take this donor
                 *cur_dist = this_dist;
@@ -2169,7 +2215,7 @@ static void __find_closest_donor(int target_gpu,
     if(donor_node->right) __find_closest_donor(target_gpu, donor_node->right, cur_closest, cur_dist);
 }
 
-ikglp_wait_state_t* gpu_ikglp_advise_doner_to_fq(struct ikglp_affinity* aff, struct fifo_queue* fq)
+ikglp_wait_state_t* gpu_ikglp_advise_donor_to_fq(struct ikglp_affinity* aff, struct fifo_queue* fq)
 {
         // Huristic strategy: Find donor with the closest affinity to fq.
         // Tie-break on priority.
@@ -2188,11 +2234,14 @@ ikglp_wait_state_t* gpu_ikglp_advise_doner_to_fq(struct ikglp_affinity* aff, str
         
         __find_closest_donor(gpu, sem->donors.root, &donor, &distance);
         
-        TRACE_CUR("Selected %s/%d as donor (distance = %d) "
-                          "(non-aff wanted %s/%d)\n",
+        TRACE_CUR("Selected donor %s/%d (distance = %d) to move to fq %d "
+                          "(non-aff wanted %s/%d). differs = %d\n",
                           donor->task->comm, donor->task->pid,
                           distance,
-                          default_donor->task->comm, default_donor->task->pid);
+                          ikglp_get_idx(sem, fq),
+                          default_donor->task->comm, default_donor->task->pid,
+                          (donor->task != default_donor->task)
+                          );
         
         return(donor);
 }
@@ -2265,7 +2314,9 @@ void gpu_ikglp_notify_dequeue(struct ikglp_affinity* aff, struct fifo_queue* fq,
         //      }
 }
 
-void gpu_ikglp_notify_acquired(struct ikglp_affinity* aff, struct fifo_queue* fq, struct task_struct* t)
+void gpu_ikglp_notify_acquired(struct ikglp_affinity* aff,
+                                                           struct fifo_queue* fq,
+                                                           struct task_struct* t)
 {
         struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
         int replica = ikglp_get_idx(sem, fq);
@@ -2286,7 +2337,9 @@ void gpu_ikglp_notify_acquired(struct ikglp_affinity* aff, struct fifo_queue* fq
         start_gpu_tracker(t);
 }
 
-void gpu_ikglp_notify_freed(struct ikglp_affinity* aff, struct fifo_queue* fq, struct task_struct* t)
+void gpu_ikglp_notify_freed(struct ikglp_affinity* aff,
+                                                        struct fifo_queue* fq,
+                                                        struct task_struct* t)
 {
         struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
         int replica = ikglp_get_idx(sem, fq);
@@ -2307,7 +2360,8 @@ void gpu_ikglp_notify_freed(struct ikglp_affinity* aff, struct fifo_queue* fq, s
         // update estimates
         update_gpu_estimate(t, get_gpu_time(t));
 
-        TRACE_CUR("%s/%d freed gpu %d.  actual time was %llu.  estimated was %llu.  diff is %d\n",
+        TRACE_CUR("%s/%d freed gpu %d.  actual time was %llu.  "
+                          "estimated was %llu.  diff is %d\n",
                           t->comm, t->pid, gpu,
                           get_gpu_time(t),
                           est_time,
@@ -2319,7 +2373,7 @@ struct ikglp_affinity_ops gpu_ikglp_affinity =
         .advise_enqueue = gpu_ikglp_advise_enqueue,
         .advise_steal = gpu_ikglp_advise_steal,
         .advise_donee_selection = gpu_ikglp_advise_donee_selection,
-        .advise_doner_to_fq = gpu_ikglp_advise_doner_to_fq,
+        .advise_donor_to_fq = gpu_ikglp_advise_donor_to_fq,
 
         .notify_enqueue = gpu_ikglp_notify_enqueue,
         .notify_dequeue = gpu_ikglp_notify_dequeue,
@@ -2408,7 +2462,7 @@ ikglp_donee_heap_node_t* simple_gpu_ikglp_advise_donee_selection(struct ikglp_af
         return(donee);
 }
 
-ikglp_wait_state_t* simple_gpu_ikglp_advise_doner_to_fq(struct ikglp_affinity* aff, struct fifo_queue* fq)
+ikglp_wait_state_t* simple_gpu_ikglp_advise_donor_to_fq(struct ikglp_affinity* aff, struct fifo_queue* fq)
 {
         struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
         ikglp_wait_state_t* donor = binheap_top_entry(&sem->donors, ikglp_wait_state_t, node);
@@ -2457,7 +2511,7 @@ struct ikglp_affinity_ops simple_gpu_ikglp_affinity =
         .advise_enqueue = simple_gpu_ikglp_advise_enqueue,
         .advise_steal = simple_gpu_ikglp_advise_steal,
         .advise_donee_selection = simple_gpu_ikglp_advise_donee_selection,
-        .advise_doner_to_fq = simple_gpu_ikglp_advise_doner_to_fq,
+        .advise_donor_to_fq = simple_gpu_ikglp_advise_donor_to_fq,
 
         .notify_enqueue = simple_gpu_ikglp_notify_enqueue,
         .notify_dequeue = simple_gpu_ikglp_notify_dequeue,
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index 422ad0395099..f2c5f180e819 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -1703,6 +1703,13 @@ static struct affinity_observer_ops gsnedf_kfmlp_affinity_ops = {
         .deallocate = kfmlp_aff_obs_free,
 };
 
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+static struct affinity_observer_ops gsnedf_ikglp_affinity_ops = {
+        .close = ikglp_aff_obs_close,
+        .deallocate = ikglp_aff_obs_free,
+};
+#endif
+
 static long gsnedf_allocate_affinity_observer(
                                                                 struct affinity_observer **aff_obs,
                                                                 int type,
@@ -1720,9 +1727,12 @@ static long gsnedf_allocate_affinity_observer(
                         *aff_obs = kfmlp_gpu_aff_obs_new(&gsnedf_kfmlp_affinity_ops, args);
                         break;
 #ifdef CONFIG_LITMUS_NESTED_LOCKING
-//              case IKGLP_GPU_AFF_OBS:
-//                      *aff_obs = gsnedf_new_ikglp_aff(arg);
-//                      break;
+                case IKGLP_SIMPLE_GPU_AFF_OBS:
+                        *aff_obs = ikglp_simple_gpu_aff_obs_new(&gsnedf_ikglp_affinity_ops, args);
+                        break;
+                case IKGLP_GPU_AFF_OBS:
+                        *aff_obs = ikglp_gpu_aff_obs_new(&gsnedf_ikglp_affinity_ops, args);
+                        break;
 #endif
                 default:
                         err = -ENXIO;