Untested donee selection heuristic for IKGLP.

2 files changed, 216 insertions, 25 deletions

diff --git a/include/litmus/ikglp_lock.h b/include/litmus/ikglp_lock.h
index 3fa23251b539..2558a382446c 100644
--- a/include/litmus/ikglp_lock.h
+++ b/include/litmus/ikglp_lock.h
@@ -119,7 +119,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);        // select steal from FIFO
-        ikglp_donee_heap_node_t* (*advise_donee_selection)(struct ikglp_affinity* aff); // select a donee
+        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
 
         void (*notify_enqueue)(struct ikglp_affinity* aff, struct fifo_queue* fq, struct task_struct* t);       // fifo enqueue
diff --git a/litmus/ikglp_lock.c b/litmus/ikglp_lock.c
index 0e07841b86ba..9ae71422d813 100644
--- a/litmus/ikglp_lock.c
+++ b/litmus/ikglp_lock.c
@@ -742,7 +742,7 @@ static void ikglp_enqueue_on_donor(struct ikglp_semaphore *sem,
         // Select a donee
 #ifdef CONFIG_LITMUS_AFFINITY_LOCKING
         donee_node = (sem->aff_obs) ?
-                sem->aff_obs->ops->advise_donee_selection(sem->aff_obs) :
+                sem->aff_obs->ops->advise_donee_selection(sem->aff_obs, t) :
                 binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node);
 #else
         donee_node = binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node);
@@ -1833,24 +1833,22 @@ static int gpu_replica_to_resource(struct ikglp_affinity* aff,
 struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct task_struct* t)
 {
         // advise_enqueue must be smart as not not break IKGLP rules:
-        //  * Total number of waiters cannot exceed ceil(m/k)*k.
+        //  * No queue can be greater than ceil(m/k) in length.  We may return
+        //    such a queue, but IKGLP will be smart enough as to send requests
+        //    to donors or PQ.
         //  * Cannot let a queue idle if there exist waiting PQ/donors
         //      -- needed to guarantee parallel progress of waiters.
         //
-        // Locking protocol is smart enough to noticed that a queue we return is
-        // full and send new requests to Donors/PQ.
-        //
         // We may be able to relax some of these constraints, but this will have to
         // be carefully evaluated.
+        //
+        // Huristic strategy: Find the shortest queue that is not full.
 
         struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
-
-        /*
-        struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
         lt_t min_len;
         int min_nr_users;
         struct ikglp_queue_info *shortest;
-        struct ikglp_queue *to_enqueue;
+        struct fifo_queue *to_enqueue;
         int i;
         int affinity_gpu;
 
@@ -1877,17 +1875,20 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
         min_len = shortest->estimated_len + get_gpu_estimate(t, MIG_LOCAL);
         min_nr_users = *(shortest->nr_cur_users);
 
-        TRACE_CUR("cs is %llu on queue %d: est len = %llu\n",
+        TRACE_CUR("cs is %llu on queue %d (count = %d): est len = %llu\n",
                           get_gpu_estimate(t, MIG_LOCAL),
                           ikglp_get_idx(sem, shortest->q),
+                          shortest->q->count,
                           min_len);
 
         for(i = 0; i < sem->nr_replicas; ++i) {
-                if(&aff->q_info[i] != shortest) {
+                if((&aff->q_info[i] != shortest) &&
+                   (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, replica_to_gpu(aff, i)));
+                                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.
@@ -1901,21 +1902,34 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
                                 min_nr_users = *(aff->q_info[i].nr_cur_users);
                         }
 
-                        TRACE_CUR("cs is %llu on queue %d: est len = %llu\n",
-                                          get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu, replica_to_gpu(aff, i))),
+                        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));
+                }
+        }
+        
+        if(shortest->q->count >= sem->max_fifo_len) {
+                TRACE_CUR("selected fq %d is too long, but returning it anyway.\n",
+                                  ikglp_get_idx(sem, shortest->q));
         }
 
         to_enqueue = shortest->q;
-        TRACE_CUR("enqueue on fq %d (non-aff wanted fq %d)\n",
+        TRACE_CUR("enqueue on fq %d (count = %d) (non-aff wanted fq %d)\n",
                           ikglp_get_idx(sem, to_enqueue),
-                          ikglp_get_idx(sem, sem->shortest_queue));
+                          to_enqueue->count,
+                          ikglp_get_idx(sem, sem->shortest_fifo_queue));
 
         return to_enqueue;
-         */
-        return(sem->shortest_fifo_queue);
+
+        //return(sem->shortest_fifo_queue);
 }
 
 ikglp_wait_state_t* gpu_ikglp_advise_steal(struct ikglp_affinity* aff)
@@ -1928,12 +1942,189 @@ ikglp_wait_state_t* gpu_ikglp_advise_steal(struct ikglp_affinity* aff)
         return ikglp_find_hp_waiter_to_steal(sem);
 }
 
-ikglp_donee_heap_node_t* gpu_ikglp_advise_donee_selection(struct ikglp_affinity* aff)
+
+static inline int has_donor(wait_queue_t* fq_wait)
+{
+        ikglp_wait_state_t *wait = container_of(fq_wait, ikglp_wait_state_t, fq_node);
+        return(wait->donee_heap_node.donor_info != NULL);
+}
+
+static ikglp_donee_heap_node_t* pick_donee(struct ikglp_affinity* aff,
+                                          struct fifo_queue* fq,
+                                          int* dist_from_head)
 {
-        // TODO: MAKE THIS SMARTER
         struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
-        ikglp_donee_heap_node_t *donee = binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node);
-        return(donee);
+        struct task_struct *donee;
+        ikglp_donee_heap_node_t *donee_node;
+        
+        if(fq->owner && fq->donee_heap_node.donor_info != NULL) {
+                donee = fq->owner;
+                donee_node = &(fq->donee_heap_node);
+                *dist_from_head = 0;
+                
+                BUG_ON(donee != donee_node->task);
+                
+                TRACE_CUR("picked owner of fq %d as donee\n",
+                                  ikglp_get_idx(sem, fq));
+
+                goto out;
+        }
+        else if(waitqueue_active(&fq->wait)) {
+                struct list_head        *pos;
+                
+                *dist_from_head = 1;
+                
+                // iterating from the start of the queue is nice since this means
+                // the donee will be closer to obtaining a resource.
+                list_for_each(pos, &fq->wait.task_list) {
+                        wait_queue_t *fq_wait = list_entry(pos, wait_queue_t, task_list);
+                        if(!has_donor(fq_wait)) {
+                                ikglp_wait_state_t *wait = container_of(fq_wait, ikglp_wait_state_t, fq_node);
+                                donee = (struct task_struct*) fq_wait->private;
+                                donee_node = &wait->donee_heap_node;
+                                
+                                BUG_ON(donee != donee_node->task);
+                                
+                                TRACE_CUR("picked waiter in fq %d as donee\n",
+                                                  ikglp_get_idx(sem, fq));
+                                
+                                goto out;
+                        }
+                        ++(*dist_from_head);
+                }
+                
+                WARN_ON(1);
+        }
+        
+        donee = NULL;
+        donee_node = NULL;
+        *dist_from_head = sem->max_fifo_len + 1;
+        
+        TRACE_CUR("Found no one to be donee in fq %d!\n", ikglp_get_idx(sem, fq));
+        
+out:
+        
+        TRACE_CUR("Candidate donee for fq %d is %s/%d (dist_from_head = %d)\n",
+                          ikglp_get_idx(sem, fq),
+                          (donee) ? (donee)->comm : "nil",
+                          (donee) ? (donee)->pid  : -1,
+                          *dist_from_head);
+        
+        return donee_node;
+}
+
+ikglp_donee_heap_node_t* gpu_ikglp_advise_donee_selection(
+                                                                                        struct ikglp_affinity* aff,
+                                                                                        struct task_struct* donor)
+{
+        // Huristic strategy: Find the highest-priority donee that is waiting on
+        // a queue closest to our affinity.  The donee CANNOT already have a donor
+        // (exception: donee is the lowest-prio task in the donee heap).
+        //
+        // Further strategy: amongst elible donees waiting for the same GPU, pick
+        // the one closest to the head of the FIFO queue (including owners).
+        //
+        struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
+        ikglp_donee_heap_node_t *donee_node;
+        gpu_migration_dist_t distance;
+        int start, i, j;
+        
+        ikglp_donee_heap_node_t *default_donee;
+        ikglp_wait_state_t *default_donee_donor_info;
+        
+        if(tsk_rt(donor)->last_gpu < 0) {
+                // no affinity.  just return the min prio, like standard IKGLP
+                // TODO: Find something closer to the head of the queue??
+                donee_node = binheap_top_entry(&sem->donees,
+                                                                           ikglp_donee_heap_node_t,
+                                                                           node);
+                goto out;
+        }
+        
+        
+        // Temporarily break any donation relation the default donee (the lowest
+        // prio task in the FIFO queues) to make it eligible for selection below.
+        //
+        // NOTE: The original donor relation *must* be restored, even if we select
+        // the default donee throug affinity-aware selection, before returning
+        // from this function so we don't screw up our heap ordering.
+        // The standard IKGLP algorithm will steal the donor relationship if needed.
+        default_donee = binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node); 
+        default_donee_donor_info = default_donee->donor_info;  // back-up donor relation
+        default_donee->donor_info = NULL;  // temporarily break any donor relation.
+        
+        // initialize our search
+        donee_node = NULL;
+        distance = MIG_NONE;
+        
+        // begin search with affinity GPU.
+        start = gpu_to_base_replica(aff, tsk_rt(donor)->last_gpu);
+        i = start;  
+        do {  // "for each gpu" / "for each aff->nr_rsrc"
+                gpu_migration_dist_t temp_distance = gpu_migration_distance(start, i);
+                
+                // only interested in queues that will improve our distance
+                if(temp_distance < distance || donee_node == NULL) {
+                        int dist_from_head = sem->max_fifo_len + 1;
+                        
+                        TRACE_CUR("searching for donor on GPU %d", i);
+                        
+                        // visit each queue and pick a donee.  bail as soon as we find
+                        // one for this class.
+
+                        for(j = 0; j < aff->nr_simult; ++j) {
+                                int temp_dist_from_head;
+                                ikglp_donee_heap_node_t *temp_donee_node;                               
+                                struct fifo_queue *fq;
+                                
+                                fq = &(sem->fifo_queues[i + j*aff->nr_rsrc]);
+                                temp_donee_node = pick_donee(aff, fq, &temp_dist_from_head);
+                                
+                                if(temp_dist_from_head < dist_from_head)
+                                {
+                                        // we check all the FQs for this GPU to spread priorities
+                                        // out across the queues.  does this decrease jitter?
+                                        donee_node = temp_donee_node;
+                                        dist_from_head = temp_dist_from_head;
+                                }
+                        }
+                        
+                        if(dist_from_head != sem->max_fifo_len + 1) {
+                                TRACE_CUR("found donee %s/%d and is the %d-th waiter.\n",
+                                                  donee_node->task->comm, donee_node->task->pid,
+                                                  dist_from_head);
+                        }
+                        else {
+                                TRACE_CUR("found no eligible donors from GPU %d\n", i);
+                        }
+                }
+                else {
+                        TRACE_CUR("skipping GPU %d (distance = %d, best donor "
+                                          "distance = %d)\n", i, temp_distance, distance);
+                }
+                
+                i = (i+1 < aff->nr_rsrc) ? i+1 : 0;  // increment with wrap-around
+        } while (i != start);
+        
+        
+        // restore old donor info state.
+        default_donee->donor_info = default_donee_donor_info;
+
+        if(!donee_node) {
+                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",
+                          donee_node->task->comm, donee_node->task->pid,
+                          replica_to_gpu(aff, ikglp_get_idx(sem, donee_node->fq)),
+                          donor->comm, donor->pid, tsk_rt(donor)->last_gpu);
+
+        return(donee_node);
 }
 
 ikglp_wait_state_t* gpu_ikglp_advise_doner_to_fq(struct ikglp_affinity* aff, struct fifo_queue* fq)
@@ -2147,7 +2338,7 @@ ikglp_wait_state_t* simple_gpu_ikglp_advise_steal(struct ikglp_affinity* aff)
         return ikglp_find_hp_waiter_to_steal(sem);
 }
 
-ikglp_donee_heap_node_t* simple_gpu_ikglp_advise_donee_selection(struct ikglp_affinity* aff)
+ikglp_donee_heap_node_t* simple_gpu_ikglp_advise_donee_selection(struct ikglp_affinity* aff, struct task_struct* donor)
 {
         struct ikglp_semaphore *sem = ikglp_from_lock(aff->obs.lock);
         ikglp_donee_heap_node_t *donee = binheap_top_entry(&sem->donees, ikglp_donee_heap_node_t, node);