path: root/litmus/event_group.c

#include <linux/slab.h>
#include <linux/sched.h>
#include <linux/module.h>

#include <litmus/litmus.h>
#include <litmus/trace.h>
#include <litmus/sched_trace.h>
#include <litmus/event_group.h>

#if 1
#define VTRACE(fmt, args...)					\
sched_trace_log_message("%d P%d        [%s@%s:%d]: " fmt,	\
				TRACE_ARGS,  ## args)
#else
#define VTRACE(fmt, args...)
#endif

/*
 * Return event_queue slot for the given time.
 */
static unsigned int time2slot(lt_t time)
{
	return (unsigned int) time2quanta(time, FLOOR) % EVENT_QUEUE_SLOTS;
}

/*
 * Executes events from an event_list in priority order.
 * Events can requeue themselves when they are called.
 */
static enum hrtimer_restart on_timer(struct hrtimer *timer)
{
	unsigned long flags;
	unsigned long num = 0;
	struct event_list *el;
	struct rt_event *e;
	struct list_head *pos, safe, events;

	el = container_of(timer, struct event_list, timer);

	raw_spin_lock_irqsave(&el->group->queue_lock, flags);
	VTRACE("Removing event list 0x%p\n", el);
	list_del_init(&el->queue_node);
	raw_spin_unlock_irqrestore(&el->group->queue_lock, flags);

	/* Empty event list so this event can be requeued */
	VTRACE("Emptying event list 0x%p\n", el);
	list_replace_init(&el->events, &events);

	/* Fire events */
	for (pos = events.next; prefetch(pos->next), pos != &events;) {
		num++;
		e = list_entry(pos, struct rt_event, events_node);
		VTRACE("Dequeueing event 0x%p with prio %d from 0x%p\n",
		      e, e->prio, el);
		list_replace(pos, &safe);
		list_del_init(pos);
		e->function(e);
		pos = safe.next;
	}
	VTRACE("Exhausted %d events from list 0x%p\n", num, el);
	/* sched_trace_action(NULL, num); */
	return HRTIMER_NORESTART;
}

/*
 * Insert event in event-list, respecting priority order.
 */
void insert_event(struct event_list *el, struct rt_event *e)
{
	struct list_head *pos, *last = NULL;
	struct rt_event *queued;
	list_for_each(pos, &el->events) {
		queued = list_entry(pos, struct rt_event, events_node);
		last = pos;
		if (e->prio < queued->prio) {
			VTRACE("Inserting priority %d event 0x%p before %d 0x%p "
			       "in 0x%p, pos 0x%p\n", e->prio, e,
			       queued->prio, &queued->events_node, el, pos);
			BUG_ON(!list_empty(&e->events_node));
			list_add_tail(&e->events_node, pos);
			return;
		}
	}
	VTRACE("Inserting  priority %d event 0x%p at end of 0x%p, last 0x%p\n",
	       e->prio, e, el, last);
	BUG_ON(!list_empty(&e->events_node));
	list_add(&e->events_node, (last) ? last : pos);
}

/*
 * Return event_list for the given event and time. If no event_list
 * is being used yet and use_event_heap is 1, will create the list
 * and return it. Otherwise it will return NULL.
 */
static struct event_list* get_event_list(struct event_group *group,
					 struct rt_event *e,
					 lt_t fire,
					 int use_event_list)
{
	struct list_head* pos;
	struct event_list *el = NULL, *tmp;
	unsigned int slot = time2slot(fire);
	int remaining = 300;

	VTRACE("Getting list for time %llu, event 0x%p\n", fire, e);

	/* Initialize pos for the case that the list is empty */
	pos = group->event_queue[slot].next;
	list_for_each(pos, &group->event_queue[slot]) {
		BUG_ON(remaining-- < 0);
		tmp = list_entry(pos, struct event_list, queue_node);
		if (lt_after_eq(fire, tmp->fire_time) &&
		    lt_before(fire, tmp->fire_time + group->res)) {
			VTRACE("Found match 0x%p at time %llu\n",
			       tmp, tmp->fire_time);
			el = tmp;
			break;
		} else if (lt_before(fire, tmp->fire_time)) {
			/* We need to insert a new node since el is
			 * already in the future
			 */
			VTRACE("Time %llu was before %llu\n",
			       fire, tmp->fire_time);
			break;
		} else {
			VTRACE("Time %llu was after %llu\n",
			       fire, tmp->fire_time + group->res);
		}
	}
	if (!el && use_event_list) {
		/* Use pre-allocated list */
		tmp = e->event_list;
		tmp->fire_time = fire;
		tmp->group = group;
		/* Add to queue */
		VTRACE("Using list 0x%p for priority %d and time %llu\n",
		       tmp, e->prio, fire);
		BUG_ON(!list_empty(&tmp->queue_node));
		list_add(&tmp->queue_node, pos->prev);
		el = tmp;
	}
	return el;
}

/*
 * Prepare a release list for a new set of events.
 */
static void reinit_event_list(struct rt_event *e)
{
	struct event_list *el = e->event_list;
	int ret;
	VTRACE("Reinitting list 0x%p for event 0x%p\n", el, e);
	ret = hrtimer_try_to_cancel(&el->timer);
	BUG_ON(ret == 1);
	if (ret == -1) {
		VTRACE("Timer is running concurrently!\n");
	}
	INIT_LIST_HEAD(&el->events);
	atomic_set(&el->info.state, HRTIMER_START_ON_INACTIVE);
}

/**
 * add_event() - Add timer to event group.
 */
void add_event(struct event_group *group, struct rt_event *e, lt_t fire)
{
	struct event_list *el;
	int in_use;

	VTRACE("Adding event 0x%p with priority %d for time %llu\n",
	       e, e->prio, fire);

	/* A NULL group means use the group of the currently executing CPU  */
	if (NULL == group)
		group = get_event_group_for(NO_CPU);
	/* Saving the group is important for cancellations */
	e->_event_group = group;

	raw_spin_lock(&group->queue_lock);
	el = get_event_list(group, e, fire, 0);
	if (!el) {
		/* Use our own, but drop lock first */
		raw_spin_unlock(&group->queue_lock);
		reinit_event_list(e);
		raw_spin_lock(&group->queue_lock);
		el = get_event_list(group, e, fire, 1);
	}

	/* Add event to sorted list */
	insert_event(el, e);
	raw_spin_unlock(&group->queue_lock);

	/* Arm timer if we are the owner */
	if (el == e->event_list) {
		VTRACE("Arming timer on event 0x%p for %llu\n", e, fire);
		in_use = hrtimer_start_on(group->cpu, &el->info,
					  &el->timer, ns_to_ktime(el->fire_time),
					  HRTIMER_MODE_ABS_PINNED);
		BUG_ON(in_use);
	} else {
		VTRACE("Not my timer @%llu\n", fire);
	}
}

/**
 * cancel_event() - Remove event from the group.
 */
void cancel_event(struct rt_event *e)
{
	struct rt_event *swap;
	struct event_list *tmp;
	struct event_group *group = e->_event_group;

	VTRACE("Canceling event 0x%p with priority %d\n", e, e->prio);
	if (!group) return;

	/* If our event_list contains any events, it is in use */
	raw_spin_lock(&group->queue_lock);
	if (!list_empty(&e->event_list->events)) {
		VTRACE("List 0x%p is not empty\n", e->event_list);

		/* If our event_list contains events, we are the first element
		 * in that list. If there is anyone after us in the list, then
		 * swap our list with theirs to that the event_list can still
		 * trigger the queued events.
		 */
		if (!list_is_singular(&e->event_list->events)) {
			swap = list_entry(e->events_node.next, struct rt_event,
					  events_node);
			VTRACE("Swapping with event 0x%p of priority %d\n",
			       swap, swap->prio);
			tmp = swap->event_list;
			swap->event_list = e->event_list;
			e->event_list = tmp;
		}

		/* Disable the event_list */
		hrtimer_pull_cancel(group->cpu,
				    &e->event_list->timer,
				    &e->event_list->info);
		list_del_init(&e->event_list->queue_node);
	} else {
		VTRACE("List 0x%p is empty\n", e->event_list);
	}
	list_del_init(&e->events_node);
	raw_spin_unlock(&group->queue_lock);
	e->_event_group = NULL;
}

struct kmem_cache *event_list_cache;

struct event_list* event_list_alloc(int gfp_flags)
{
	struct event_list *el = kmem_cache_alloc(event_list_cache, gfp_flags);
	if (el) {
		hrtimer_init(&el->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
		INIT_LIST_HEAD(&el->queue_node);
		el->timer.function = on_timer;
		hrtimer_start_on_info_init(&el->info);
	} else {
		VTRACE("Failed to allocate event list!\n");
		printk(KERN_CRIT "Failed to allocate event list.\n");
		BUG();
	}
	return el;
}

void init_event(struct rt_event *e, int prio, fire_event_t function,
		struct event_list *el)
{
	e->prio = prio;
	e->function = function;
	e->event_list = el;
	e->_event_group = NULL;
	INIT_LIST_HEAD(&e->events_node);
}

/**
 * init_event_group() - Prepare group for events.
 * @group	Group to prepare
 * @res		Timer resolution. Two events of @res distance will be merged
 * @cpu		Cpu on which to fire timers
 */
static void init_event_group(struct event_group *group, lt_t res, int cpu)
{
	int i;
	VTRACE("Creating group with resolution %llu on CPU %d", res, cpu);
	group->res = res;
	group->cpu = cpu;
	for (i = 0; i < EVENT_QUEUE_SLOTS; i++)
		INIT_LIST_HEAD(&group->event_queue[i]);
	raw_spin_lock_init(&group->queue_lock);
}


DEFINE_PER_CPU(struct event_group, _event_groups);

struct event_group *get_event_group_for(const int cpu)
{
	return &per_cpu(_event_groups,
			(NO_CPU == cpu) ? smp_processor_id() : cpu);
}

static int __init _init_event_groups(void)
{
	int cpu;
	printk("Initializing LITMUS^RT event groups.\n");

	for_each_online_cpu(cpu) {
		init_event_group(get_event_group_for(cpu),
				CONFIG_MERGE_TIMERS_WINDOW, cpu);
	}
	return 0;
}

module_init(_init_event_groups);