path: root/litmus/kfmlp_lock.c

#include <linux/slab.h>
#include <linux/uaccess.h>

#include <litmus/trace.h>
#include <litmus/sched_plugin.h>
#include <litmus/fdso.h>

#include <litmus/kfmlp_lock.h>

#if defined(CONFIG_LITMUS_AFFINITY_LOCKING) && defined(CONFIG_LITMUS_NVIDIA)
#include <litmus/gpu_affinity.h>
#include <litmus/nvidia_info.h>
#endif

static inline int kfmlp_get_idx(struct kfmlp_semaphore* sem,
								struct kfmlp_queue* queue)
{
	return (queue - &sem->queues[0]);
}

static inline struct kfmlp_queue* kfmlp_get_queue(struct kfmlp_semaphore* sem,
												  struct task_struct* holder)
{
	int i;
	for(i = 0; i < sem->num_resources; ++i)
		if(sem->queues[i].owner == holder)
			return(&sem->queues[i]);
	return(NULL);
}

/* caller is responsible for locking */
static struct task_struct* kfmlp_find_hp_waiter(struct kfmlp_queue *kqueue,
												struct task_struct *skip)
{
	struct list_head	*pos;
	struct task_struct 	*queued, *found = NULL;
	
	list_for_each(pos, &kqueue->wait.task_list) {
		queued  = (struct task_struct*) list_entry(pos, wait_queue_t,
												   task_list)->private;
		
		/* Compare task prios, find high prio task. */
		//if (queued != skip && edf_higher_prio(queued, found))
		if (queued != skip && litmus->compare(queued, found))
			found = queued;
	}
	return found;
}

static inline struct kfmlp_queue* kfmlp_find_shortest(struct kfmlp_semaphore* sem,
													  struct kfmlp_queue* search_start)
{
	// we start our search at search_start instead of at the beginning of the
	// queue list to load-balance across all resources.
	struct kfmlp_queue* step = search_start;
	struct kfmlp_queue* shortest = sem->shortest_queue;
	
	do
	{
		step = (step+1 != &sem->queues[sem->num_resources]) ?
		step+1 : &sem->queues[0];
		
		if(step->count < shortest->count)
		{
			shortest = step;
			if(step->count == 0)
				break; /* can't get any shorter */
		}
		
	}while(step != search_start);
	
	return(shortest);
}


// TODO: BREAK THIS UP INTO TWO STEPS:
// 1) task to steal (and from what queue)
// 2) update queues
static struct task_struct* kfmlp_select_hp_steal(struct kfmlp_semaphore* sem, wait_queue_t** to_steal, struct kfmlp_queue** to_steal_from)
{
	/* must hold sem->lock */	
	
	int i;
	
	*to_steal = NULL;
	*to_steal_from = NULL;	
	
	for(i = 0; i < sem->num_resources; ++i)
	{
		if( (sem->queues[i].count > 1) &&
		   ((*to_steal_from == NULL) ||
			//(edf_higher_prio(sem->queues[i].hp_waiter, my_queue->hp_waiter))) )
			(litmus->compare(sem->queues[i].hp_waiter, (*to_steal_from)->hp_waiter))) )
		{
			*to_steal_from = &sem->queues[i];
		}
	}
	
	if(*to_steal_from)
	{
		struct list_head *pos;
		list_for_each(pos, &(*to_steal_from)->wait.task_list)
		{
			wait_queue_t *node = list_entry(pos, wait_queue_t, task_list);
			struct task_struct *queued = (struct task_struct*) node->private;
			/* Compare task prios, find high prio task. */
			if (queued == (*to_steal_from)->hp_waiter)
			{
				*to_steal = node;
				
				TRACE_CUR("steal: selected %s/%d from queue %d\n",
						  queued->comm, queued->pid,
						  kfmlp_get_idx(sem, *to_steal_from));
				
				return queued;
			}
		}
	}
	
	return NULL;
}

static void kfmlp_steal_node(struct kfmlp_semaphore *sem,
							 struct kfmlp_queue *dst,
							 wait_queue_t *wait,
							 struct kfmlp_queue *src)
{
	struct task_struct* t = (struct task_struct*) wait->private;
	
	__remove_wait_queue(&src->wait, wait);	
	--(src->count);
	
	if(t == src->hp_waiter) {
		src->hp_waiter = kfmlp_find_hp_waiter(src, NULL);
		
		if(src->owner && tsk_rt(src->owner)->inh_task == t) {
			litmus->decrease_prio(src->owner, src->hp_waiter);
		}
	}
	
	if(sem->shortest_queue->count > src->count) {
		sem->shortest_queue = src;
	}
	
#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
	if(sem->aff_obs) {
		sem->aff_obs->ops->notify_dequeue(sem->aff_obs, src, t);
	}
#endif	
	
	init_waitqueue_entry(wait, t);
	__add_wait_queue_tail_exclusive(&dst->wait, wait);
	++(dst->count);
	
	if(litmus->compare(t, dst->hp_waiter)) {
		dst->hp_waiter = t;
		
		if(dst->owner && litmus->compare(t, dst->owner))
		{
			litmus->increase_prio(dst->owner, t);
		}
	}
	
#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
	if(sem->aff_obs) {
		sem->aff_obs->ops->notify_enqueue(sem->aff_obs, dst, t);
	}
#endif	
}
//// TODO: BREAK THIS UP INTO TWO STEPS:
//// 1) task to steal (and from what queue)
//// 2) update queues
//static struct task_struct* kfmlp_remove_hp_waiter(struct kfmlp_semaphore* sem)
//{
//	/* must hold sem->lock */
//	
//	struct kfmlp_queue *my_queue = NULL;
//	struct task_struct *max_hp = NULL;
//	
//	struct list_head	*pos;
//	struct task_struct 	*queued;
//	int i;
//	
//	for(i = 0; i < sem->num_resources; ++i)
//	{
//		if( (sem->queues[i].count > 1) &&
//		   ((my_queue == NULL) ||
//			//(edf_higher_prio(sem->queues[i].hp_waiter, my_queue->hp_waiter))) )
//			(litmus->compare(sem->queues[i].hp_waiter, my_queue->hp_waiter))) )
//		{
//			my_queue = &sem->queues[i];
//		}
//	}
//	
//	if(my_queue)
//	{		
//		max_hp = my_queue->hp_waiter;
//		
//		BUG_ON(!max_hp);
//		
//		TRACE_CUR("queue %d: stealing %s/%d from queue %d\n",
//				  kfmlp_get_idx(sem, my_queue),
//				  max_hp->comm, max_hp->pid,
//				  kfmlp_get_idx(sem, my_queue));
//		
//		my_queue->hp_waiter = kfmlp_find_hp_waiter(my_queue, max_hp);
//		
//		if(tsk_rt(my_queue->owner)->inh_task == max_hp)
//		{
//			litmus->decrease_prio(my_queue->owner, my_queue->hp_waiter);
//		}
//
//		list_for_each(pos, &my_queue->wait.task_list)
//		{
//			queued  = (struct task_struct*) list_entry(pos, wait_queue_t,
//													   task_list)->private;
//			/* Compare task prios, find high prio task. */
//			if (queued == max_hp)
//			{
//				/*
//				 TRACE_CUR("queue %d: found entry in wait queue.  REMOVING!\n",
//				 kfmlp_get_idx(sem, my_queue));
//				 */
//				__remove_wait_queue(&my_queue->wait,
//									list_entry(pos, wait_queue_t, task_list));
//				break;
//			}
//		}
//		--(my_queue->count);
//		
//#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
//		if(sem->aff_obs) {
//			sem->aff_obs->ops->notify_dequeue(sem->aff_obs, my_queue, max_hp);
//		}		
//#endif		
//	}
//	
//	return(max_hp);
//}

int kfmlp_lock(struct litmus_lock* l)
{
	struct task_struct* t = current;
	struct kfmlp_semaphore *sem = kfmlp_from_lock(l);
	struct kfmlp_queue* my_queue = NULL;
	wait_queue_t wait;
	unsigned long flags;
	
	if (!is_realtime(t))
		return -EPERM;
	
	spin_lock_irqsave(&sem->lock, flags);
	
#ifdef CONFIG_LITMUS_AFFINITY_LOCKING	
	if(sem->aff_obs) {
		my_queue = sem->aff_obs->ops->advise_enqueue(sem->aff_obs, t);
	}
	if(!my_queue) {
		my_queue = sem->shortest_queue;
	}
#else
	my_queue = sem->shortest_queue;
#endif
	
	if (my_queue->owner) {
		/* resource is not free => must suspend and wait */
		TRACE_CUR("queue %d: Resource is not free => must suspend and wait.\n",
				  kfmlp_get_idx(sem, my_queue));
		
		init_waitqueue_entry(&wait, t);
		
		/* FIXME: interruptible would be nice some day */
		set_task_state(t, TASK_UNINTERRUPTIBLE);
		
		__add_wait_queue_tail_exclusive(&my_queue->wait, &wait);
		
		/* check if we need to activate priority inheritance */
		//if (edf_higher_prio(t, my_queue->hp_waiter))
		if (litmus->compare(t, my_queue->hp_waiter))
		{
			my_queue->hp_waiter = t;
			//if (edf_higher_prio(t, my_queue->owner))
			if (litmus->compare(t, my_queue->owner))
			{
				litmus->increase_prio(my_queue->owner, my_queue->hp_waiter);
			}
		}
		
		++(my_queue->count);
		
#ifdef CONFIG_LITMUS_AFFINITY_LOCKING		
		if(my_queue == sem->shortest_queue) {
			sem->shortest_queue = kfmlp_find_shortest(sem, my_queue);
		}
		if(sem->aff_obs) {
			sem->aff_obs->ops->notify_enqueue(sem->aff_obs, my_queue, t);
		}
#else
		sem->shortest_queue = kfmlp_find_shortest(sem, my_queue);
#endif
		
		/* release lock before sleeping */
		spin_unlock_irqrestore(&sem->lock, flags);
		
		/* We depend on the FIFO order.  Thus, we don't need to recheck
		 * when we wake up; we are guaranteed to have the lock since
		 * there is only one wake up per release (or steal).
		 */
		schedule();
		
		
		if(my_queue->owner == t)
		{
			TRACE_CUR("queue %d: acquired through waiting\n",
					  kfmlp_get_idx(sem, my_queue));
		}
		else
		{
			/* this case may happen if our wait entry was stolen
			 between queues. record where we went. */
			my_queue = kfmlp_get_queue(sem, t);
			
			BUG_ON(!my_queue);
			TRACE_CUR("queue %d: acquired through stealing\n",
					  kfmlp_get_idx(sem, my_queue));
		}
	}
	else
	{
		TRACE_CUR("queue %d: acquired immediately\n",
				  kfmlp_get_idx(sem, my_queue));
		
		my_queue->owner = t;
		
		++(my_queue->count);
		
#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
		if(my_queue == sem->shortest_queue) {
			sem->shortest_queue = kfmlp_find_shortest(sem, my_queue);
		}
		if(sem->aff_obs) {
			sem->aff_obs->ops->notify_enqueue(sem->aff_obs, my_queue, t);
			sem->aff_obs->ops->notify_acquired(sem->aff_obs, my_queue, t);
		}
#else
		sem->shortest_queue = kfmlp_find_shortest(sem, my_queue);
#endif
		
		spin_unlock_irqrestore(&sem->lock, flags);
	}
	
	return kfmlp_get_idx(sem, my_queue);
}


int kfmlp_unlock(struct litmus_lock* l)
{
	struct task_struct *t = current, *next;
	struct kfmlp_semaphore *sem = kfmlp_from_lock(l);
	struct kfmlp_queue *my_queue, *to_steal_from;
	unsigned long flags;
	int err = 0;
	
	spin_lock_irqsave(&sem->lock, flags);
	
	my_queue = kfmlp_get_queue(sem, t);
	
	if (!my_queue || my_queue->owner != t) {
		err = -EINVAL;
		goto out;
	}
	
	my_queue->owner = NULL;  // clear ownership
	--(my_queue->count);
	
	if(my_queue->count < sem->shortest_queue->count)
	{
		sem->shortest_queue = my_queue;
	}
	
#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
	if(sem->aff_obs) {
		sem->aff_obs->ops->notify_dequeue(sem->aff_obs, my_queue, t);
		sem->aff_obs->ops->notify_freed(sem->aff_obs, my_queue, t);
	}	
#endif
	
	/* we lose the benefit of priority inheritance (if any) */
	if (tsk_rt(t)->inh_task)
		litmus->decrease_prio(t, NULL);	
	
	
	/* check if there are jobs waiting for this resource */
RETRY:
	next = __waitqueue_remove_first(&my_queue->wait);
	if (next) {
		/* next becomes the resouce holder */
		my_queue->owner = next;
		
#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
		if(sem->aff_obs) {
			sem->aff_obs->ops->notify_acquired(sem->aff_obs, my_queue, next);
		}		
#endif		
		
		TRACE_CUR("queue %d: lock ownership passed to %s/%d\n",
				  kfmlp_get_idx(sem, my_queue), next->comm, next->pid);
		
		/* determine new hp_waiter if necessary */
		if (next == my_queue->hp_waiter) {
			TRACE_TASK(next, "was highest-prio waiter\n");
			my_queue->hp_waiter = kfmlp_find_hp_waiter(my_queue, next);
			if (my_queue->hp_waiter)
				TRACE_TASK(my_queue->hp_waiter, "queue %d: is new highest-prio waiter\n", kfmlp_get_idx(sem, my_queue));
			else
				TRACE("queue %d: no further waiters\n", kfmlp_get_idx(sem, my_queue));
		} else {
			/* Well, if next is not the highest-priority waiter,
			 * then it ought to inherit the highest-priority
			 * waiter's priority. */
			litmus->increase_prio(next, my_queue->hp_waiter);
		}
		
		/* wake up next */
		wake_up_process(next);
	}
	else
	{
		// TODO: put this stealing logic before we attempt to release
		// our resource.  (simplifies code and gets rid of ugly goto RETRY.
		wait_queue_t *wait;
		
		TRACE_CUR("queue %d: looking to steal someone...\n", kfmlp_get_idx(sem, my_queue));

#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
		next = (sem->aff_obs) ?
			sem->aff_obs->ops->advise_steal(sem->aff_obs, &wait, &to_steal_from) :
			kfmlp_select_hp_steal(sem, &wait, &to_steal_from);
#else
		next = kfmlp_select_hp_steal(sem, &wait, &to_steal_from);
#endif
		
		if(next) {
			kfmlp_steal_node(sem, my_queue, wait, to_steal_from);
			
			TRACE_CUR("queued %d: stole %s/%d from queue %d\n",
					  next->comm, next->pid,
					  kfmlp_get_idx(sem, to_steal_from));
			
			goto RETRY;  // will succeed this time.
		}
		else {		
			TRACE_CUR("queue %d: no one to steal.\n", kfmlp_get_idx(sem, my_queue));
		}
	}
	
out:
	spin_unlock_irqrestore(&sem->lock, flags);
	
	return err;
}

int kfmlp_close(struct litmus_lock* l)
{
	struct task_struct *t = current;
	struct kfmlp_semaphore *sem = kfmlp_from_lock(l);
	struct kfmlp_queue *my_queue;
	unsigned long flags;
	
	int owner;
	
	spin_lock_irqsave(&sem->lock, flags);
	
	my_queue = kfmlp_get_queue(sem, t);	
	owner = (my_queue) ? (my_queue->owner == t) : 0;
	
	spin_unlock_irqrestore(&sem->lock, flags);
	
	if (owner)
		kfmlp_unlock(l);
	
	return 0;
}

void kfmlp_free(struct litmus_lock* l)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(l);
	kfree(sem->queues);
	kfree(sem);
}



struct litmus_lock* kfmlp_new(struct litmus_lock_ops* ops, void* __user args)
{
	struct kfmlp_semaphore* sem;
	int num_resources = 0;
	int i;
	
	if(!access_ok(VERIFY_READ, args, sizeof(num_resources)))
	{
		return(NULL);
	}
	if(__copy_from_user(&num_resources, args, sizeof(num_resources)))
	{
		return(NULL);
	}
	if(num_resources < 1)
	{
		return(NULL);		
	}
	
	sem = kmalloc(sizeof(*sem), GFP_KERNEL);
	if(!sem)
	{
		return(NULL);
	}
	
	sem->queues = kmalloc(sizeof(struct kfmlp_queue)*num_resources, GFP_KERNEL);
	if(!sem->queues)
	{
		kfree(sem);
		return(NULL);
	}
	
	sem->litmus_lock.ops = ops;
	spin_lock_init(&sem->lock);
	sem->num_resources = num_resources;
	
	for(i = 0; i < num_resources; ++i)
	{
		sem->queues[i].owner = NULL;
		sem->queues[i].hp_waiter = NULL;
		init_waitqueue_head(&sem->queues[i].wait);
		sem->queues[i].count = 0;
	}
	
	sem->shortest_queue = &sem->queues[0];

	return &sem->litmus_lock;
}




#if defined(CONFIG_LITMUS_AFFINITY_LOCKING) && defined(CONFIG_LITMUS_NVIDIA)

int kfmlp_aff_obs_close(struct affinity_observer* obs)
{
	return 0;
}

void kfmlp_aff_obs_free(struct affinity_observer* obs)
{
	struct kfmlp_affinity *kfmlp_aff = kfmlp_aff_obs_from_aff_obs(obs);
	kfree(kfmlp_aff->q_info);
	kfree(kfmlp_aff);
}

static struct affinity_observer* kfmlp_aff_obs_new(struct affinity_observer_ops* ops,
												   struct kfmlp_affinity_ops* kfmlp_ops,
												   void* __user args)
{
	struct kfmlp_affinity* kfmlp_aff;
	struct kfmlp_gpu_affinity_observer_args aff_args;
	struct kfmlp_semaphore* sem;
	int i;
	unsigned long flags;
	
	if(!access_ok(VERIFY_READ, args, sizeof(aff_args)))
	{
		return(NULL);
	}
	if(__copy_from_user(&aff_args, args, sizeof(aff_args)))
	{
		return(NULL);
	}
	
	sem = (struct kfmlp_semaphore*) get_lock_from_od(aff_args.obs.lock_od);
	
	if(sem->litmus_lock.type != KFMLP_SEM)
	{
		TRACE_CUR("Lock type not supported.  Type = %d\n", sem->litmus_lock.type);
		return(NULL);
	}
	
	kfmlp_aff = kmalloc(sizeof(*kfmlp_aff), GFP_KERNEL);
	if(!kfmlp_aff)
	{
		return(NULL);
	}
	
	kfmlp_aff->q_info = kmalloc(sizeof(struct kfmlp_queue_info)*sem->num_resources, GFP_KERNEL);
	if(!kfmlp_aff->q_info)
	{
		kfree(kfmlp_aff);
		return(NULL);
	}
	
	kfmlp_aff->obs.ops = ops;
	kfmlp_aff->ops = kfmlp_ops;
	kfmlp_aff->offset = aff_args.replica_to_gpu_offset;
	
	for(i = 0; i < sem->num_resources; ++i)
	{
		kfmlp_aff->q_info[i].q = &sem->queues[i];
		kfmlp_aff->q_info[i].estimated_len = 0;
	}
	
	spin_lock_irqsave(&sem->lock, flags);
	sem->aff_obs = kfmlp_aff;
	kfmlp_aff->shortest_queue = &kfmlp_aff->q_info[kfmlp_get_idx(sem, sem->shortest_queue)];
	spin_unlock_irqrestore(&sem->lock, flags);
	
	return &kfmlp_aff->obs;
}




// Smart KFMLP Affinity

static inline struct kfmlp_queue_info* kfmlp_aff_find_shortest(struct kfmlp_affinity* aff)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	struct kfmlp_queue_info *shortest = &aff->q_info[0];
	int i;
	
	for(i = 1; i < sem->num_resources; ++i) {
		if(aff->q_info[i].estimated_len < shortest->estimated_len) {
			shortest = &aff->q_info[i];
		}
	}
	
	return(shortest);
}

struct kfmlp_queue* gpu_kfmlp_advise_enqueue(struct kfmlp_affinity* aff, struct task_struct* t)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	lt_t min_len;
	struct kfmlp_queue_info *shortest;
	struct kfmlp_queue *to_enqueue;
	int i;
	
	// simply pick the shortest queue if, we have no affinity, or we have
	// affinity with the shortest
	if((tsk_rt(t)->last_gpu < 0) ||
	   ((kfmlp_get_idx(sem, aff->shortest_queue->q) + aff->offset) == tsk_rt(t)->last_gpu)) {
		// we have affinity with the shorest queue.  pick it.
		to_enqueue = aff->shortest_queue->q;
		
		TRACE_CUR("special case: no affinity or have affinity with shortest\n");
		
		goto out;
	}
	
	// enqueue where we will have the shortest time to completion
	
	shortest = &aff->q_info[0];
	min_len = shortest->estimated_len + get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu, 0 + aff->offset));
	
	for(i = 1; i < sem->num_resources; ++i) {
		lt_t est_len =
			aff->q_info[i].estimated_len +
			get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu, i + aff->offset));
							 
		if(est_len < min_len) {
			shortest = &aff->q_info[i];
			min_len = est_len;
		}
	}
	to_enqueue = shortest->q;
	
out:
	TRACE_CUR("enqueue on fq %d (non-aff wanted fq %d)\n",
			  kfmlp_get_idx(sem, to_enqueue),
			  kfmlp_get_idx(sem, sem->shortest_queue));	
	
	return to_enqueue;
}

struct task_struct* gpu_kfmlp_advise_steal(struct kfmlp_affinity* aff, wait_queue_t** to_steal, struct kfmlp_queue** to_steal_from)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	
	// For now, just steal from the shortest (by number) queue.
	// TODO: Implement affinity-aware stealing.
	
	return kfmlp_select_hp_steal(sem, to_steal, to_steal_from);
}


void gpu_kfmlp_notify_enqueue(struct kfmlp_affinity* aff, struct kfmlp_queue* fq, struct task_struct* t)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	int replica = kfmlp_get_idx(sem, fq);
	int gpu = aff->offset + replica;
	struct kfmlp_queue_info *info = &aff->q_info[replica];
	lt_t est_time;
	
	if(current == t) {
		tsk_rt(t)->suspend_gpu_tracker_on_block = 1;
	}

	est_time = get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu, gpu));
	info->estimated_len += est_time;
	
	TRACE_CUR("fq %d est len is now %llu\n",
			  kfmlp_get_idx(sem, aff->shortest_queue->q),
			  aff->shortest_queue->estimated_len);
	
	if(aff->shortest_queue == info) {
		// we may no longer be the shortest
		aff->shortest_queue = kfmlp_aff_find_shortest(aff);
		
		TRACE_CUR("shortest queue is fq %d (with %d in queue) has est len %llu\n",
				  kfmlp_get_idx(sem, aff->shortest_queue->q),
				  aff->shortest_queue->q->count,
				  aff->shortest_queue->estimated_len);
	}
}

void gpu_kfmlp_notify_dequeue(struct kfmlp_affinity* aff, struct kfmlp_queue* fq, struct task_struct* t)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	int replica = kfmlp_get_idx(sem, fq);
	int gpu = aff->offset + replica;
	struct kfmlp_queue_info *info = &aff->q_info[replica];
	lt_t est_time = get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu, gpu));
	
	if(est_time > info->estimated_len) {
		WARN_ON(1);
		info->estimated_len = 0;
	}
	else {
		info->estimated_len -= est_time;
	}
	
	TRACE_CUR("fq %d est len is now %llu\n",
			  kfmlp_get_idx(sem, info->q),
			  info->estimated_len);	
	
	// check to see if we're the shortest queue now.
	if((aff->shortest_queue != info) &&
	   (aff->shortest_queue->estimated_len > info->estimated_len)) {
		
		aff->shortest_queue = info;
		
		TRACE_CUR("shortest queue is fq %d (with %d in queue) has est len %llu\n",
				  kfmlp_get_idx(sem, info->q),
				  info->q->count,
				  info->estimated_len);		
	}
}

void gpu_kfmlp_notify_acquired(struct kfmlp_affinity* aff, struct kfmlp_queue* fq, struct task_struct* t)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	int gpu = kfmlp_get_idx(sem, fq) + aff->offset;
	
	tsk_rt(t)->gpu_migration = gpu_migration_distance(tsk_rt(t)->last_gpu, gpu);  // record the type of migration
	
	TRACE_CUR("%s/%d acquired gpu %d.  migration type = %d\n",
			  t->comm, t->pid, gpu, tsk_rt(t)->gpu_migration);
	
	reg_nv_device(gpu, 1);  // register
	
	tsk_rt(t)->suspend_gpu_tracker_on_block = 0;
	reset_gpu_tracker(t);
	start_gpu_tracker(t);
}

void gpu_kfmlp_notify_freed(struct kfmlp_affinity* aff, struct kfmlp_queue* fq, struct task_struct* t)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	int gpu = kfmlp_get_idx(sem, fq) + aff->offset;
	lt_t est_time;
	
	stop_gpu_tracker(t);  // stop the tracker before we do anything else.
	
	est_time = get_gpu_estimate(t, gpu_migration_distance(tsk_rt(t)->last_gpu, gpu));
	
	tsk_rt(t)->last_gpu = gpu;
	reg_nv_device(gpu, 0);	// unregister
	
	// 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",
			  t->comm, t->pid, gpu,
			  get_gpu_time(t),
			  est_time,
			  (long long)get_gpu_time(t) - (long long)est_time);
}

struct kfmlp_affinity_ops gpu_kfmlp_affinity =
{
	.advise_enqueue = gpu_kfmlp_advise_enqueue,
	.advise_steal = gpu_kfmlp_advise_steal,
	.notify_enqueue = gpu_kfmlp_notify_enqueue,
	.notify_dequeue = gpu_kfmlp_notify_dequeue,
	.notify_acquired = gpu_kfmlp_notify_acquired,
	.notify_freed = gpu_kfmlp_notify_freed
};

struct affinity_observer* kfmlp_gpu_aff_obs_new(struct affinity_observer_ops* ops,
											void* __user args)
{
	return kfmlp_aff_obs_new(ops, &gpu_kfmlp_affinity, args);
}








// Simple KFMLP Affinity (standard KFMLP with auto-gpu registration)

struct kfmlp_queue* simple_gpu_kfmlp_advise_enqueue(struct kfmlp_affinity* aff, struct task_struct* t)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	return sem->shortest_queue;
}

struct task_struct* simple_gpu_kfmlp_advise_steal(struct kfmlp_affinity* aff, wait_queue_t** to_steal, struct kfmlp_queue** to_steal_from)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	return kfmlp_select_hp_steal(sem, to_steal, to_steal_from);
}

void simple_gpu_kfmlp_notify_enqueue(struct kfmlp_affinity* aff, struct kfmlp_queue* fq, struct task_struct* t)
{
}

void simple_gpu_kfmlp_notify_dequeue(struct kfmlp_affinity* aff, struct kfmlp_queue* fq, struct task_struct* t)
{
}

void simple_gpu_kfmlp_notify_acquired(struct kfmlp_affinity* aff, struct kfmlp_queue* fq, struct task_struct* t)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	int gpu = kfmlp_get_idx(sem, fq) + aff->offset;
	
	reg_nv_device(gpu, 1);  // register
}

void simple_gpu_kfmlp_notify_freed(struct kfmlp_affinity* aff, struct kfmlp_queue* fq, struct task_struct* t)
{
	struct kfmlp_semaphore *sem = kfmlp_from_lock(aff->obs.lock);
	int gpu = kfmlp_get_idx(sem, fq) + aff->offset;
	
	reg_nv_device(gpu, 0);	// unregister
}

struct kfmlp_affinity_ops simple_gpu_kfmlp_affinity =
{
	.advise_enqueue = simple_gpu_kfmlp_advise_enqueue,
	.advise_steal = simple_gpu_kfmlp_advise_steal,
	.notify_enqueue = simple_gpu_kfmlp_notify_enqueue,
	.notify_dequeue = simple_gpu_kfmlp_notify_dequeue,
	.notify_acquired = simple_gpu_kfmlp_notify_acquired,
	.notify_freed = simple_gpu_kfmlp_notify_freed
};

struct affinity_observer* kfmlp_simple_gpu_aff_obs_new(struct affinity_observer_ops* ops,
												void* __user args)
{
	return kfmlp_aff_obs_new(ops, &simple_gpu_kfmlp_affinity, args);
}

#endif