Add basic generic reservation-based scheduling infrastructure

7 files changed, 1091 insertions, 0 deletions

diff --git a/litmus/Makefile b/litmus/Makefile
index 7970cd55e7fd..c969ce59db67 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -30,3 +30,5 @@ obj-$(CONFIG_FEATHER_TRACE) += ft_event.o ftdev.o
 obj-$(CONFIG_SCHED_TASK_TRACE) += sched_task_trace.o
 obj-$(CONFIG_SCHED_DEBUG_TRACE) += sched_trace.o
 obj-$(CONFIG_SCHED_OVERHEAD_TRACE) += trace.o
+
+obj-y += reservations/
diff --git a/litmus/reservations/Makefile b/litmus/reservations/Makefile
new file mode 100644
index 000000000000..517fc2ff8a76
--- /dev/null
+++ b/litmus/reservations/Makefile
@@ -0,0 +1,3 @@
+obj-y += core.o budget-notifier.o alloc.o
+obj-y += polling.o
+obj-y += table-driven.o
diff --git a/litmus/reservations/alloc.c b/litmus/reservations/alloc.c
new file mode 100644
index 000000000000..1f93f223f504
--- /dev/null
+++ b/litmus/reservations/alloc.c
@@ -0,0 +1,143 @@
+#include <linux/slab.h>
+#include <asm/uaccess.h>
+
+#include <litmus/rt_param.h>
+
+#include <litmus/reservations/alloc.h>
+#include <litmus/reservations/polling.h>
+#include <litmus/reservations/table-driven.h>
+
+
+long alloc_polling_reservation(
+        int res_type,
+        struct reservation_config *config,
+        struct reservation **_res)
+{
+        struct polling_reservation *pres;
+        int use_edf  = config->priority == LITMUS_NO_PRIORITY;
+        int periodic =  res_type == PERIODIC_POLLING;
+
+        if (config->polling_params.budget >
+            config->polling_params.period) {
+                printk(KERN_ERR "invalid polling reservation (%u): "
+                       "budget > period\n", config->id);
+                return -EINVAL;
+        }
+        if (config->polling_params.budget >
+            config->polling_params.relative_deadline
+            && config->polling_params.relative_deadline) {
+                printk(KERN_ERR "invalid polling reservation (%u): "
+                       "budget > deadline\n", config->id);
+                return -EINVAL;
+        }
+        if (config->polling_params.offset >
+            config->polling_params.period) {
+                printk(KERN_ERR "invalid polling reservation (%u): "
+                       "offset > period\n", config->id);
+                return -EINVAL;
+        }
+
+        /* XXX: would be nice to use a core-local allocation. */
+        pres = kzalloc(sizeof(*pres), GFP_KERNEL);
+        if (!pres)
+                return -ENOMEM;
+
+        polling_reservation_init(pres, use_edf, periodic,
+                config->polling_params.budget,
+                config->polling_params.period,
+                config->polling_params.relative_deadline,
+                config->polling_params.offset);
+        pres->res.id = config->id;
+        if (!use_edf)
+                pres->res.priority = config->priority;
+
+        *_res = &pres->res;
+        return 0;
+}
+
+
+#define MAX_INTERVALS 1024
+
+long alloc_table_driven_reservation(
+        struct reservation_config *config,
+        struct reservation **_res)
+{
+        struct table_driven_reservation *td_res = NULL;
+        struct lt_interval *slots = NULL;
+        size_t slots_size;
+        unsigned int i, num_slots;
+        long err = -EINVAL;
+        void *mem;
+
+        if (!config->table_driven_params.num_intervals) {
+                printk(KERN_ERR "invalid table-driven reservation (%u): "
+                       "no intervals\n", config->id);
+                return -EINVAL;
+        }
+
+        if (config->table_driven_params.num_intervals > MAX_INTERVALS) {
+                printk(KERN_ERR "invalid table-driven reservation (%u): "
+                       "too many intervals (max: %d)\n", config->id, MAX_INTERVALS);
+                return -EINVAL;
+        }
+
+        num_slots = config->table_driven_params.num_intervals;
+        slots_size = sizeof(slots[0]) * num_slots;
+
+        mem = kzalloc(sizeof(*td_res) + slots_size, GFP_KERNEL);
+        if (!mem) {
+                return -ENOMEM;
+        } else {
+                slots  = mem + sizeof(*td_res);
+                td_res = mem;
+                err = copy_from_user(slots,
+                        config->table_driven_params.intervals, slots_size);
+        }
+
+        if (!err) {
+                /* sanity checks */
+                for (i = 0; !err && i < num_slots; i++)
+                        if (slots[i].end <= slots[i].start) {
+                                printk(KERN_ERR
+                                       "invalid table-driven reservation (%u): "
+                                       "invalid interval %u => [%llu, %llu]\n",
+                                       config->id, i,
+                                       slots[i].start, slots[i].end);
+                                err = -EINVAL;
+                        }
+
+                for (i = 0; !err && i + 1 < num_slots; i++)
+                        if (slots[i + 1].start <= slots[i].end) {
+                                printk(KERN_ERR
+                                       "invalid table-driven reservation (%u): "
+                                       "overlapping intervals %u, %u\n",
+                                       config->id, i, i + 1);
+                                err = -EINVAL;
+                        }
+
+                if (slots[num_slots - 1].end >
+                        config->table_driven_params.major_cycle_length) {
+                        printk(KERN_ERR
+                                "invalid table-driven reservation (%u): last "
+                                "interval ends past major cycle %llu > %llu\n",
+                                config->id,
+                                slots[num_slots - 1].end,
+                                config->table_driven_params.major_cycle_length);
+                        err = -EINVAL;
+                }
+        }
+
+        if (err) {
+                kfree(td_res);
+        } else {
+                table_driven_reservation_init(td_res,
+                        config->table_driven_params.major_cycle_length,
+                        slots, num_slots);
+                td_res->res.id = config->id;
+                td_res->res.priority = config->priority;
+                *_res = &td_res->res;
+        }
+
+        return err;
+}
+
diff --git a/litmus/reservations/budget-notifier.c b/litmus/reservations/budget-notifier.c
new file mode 100644
index 000000000000..0b0f42687882
--- /dev/null
+++ b/litmus/reservations/budget-notifier.c
@@ -0,0 +1,26 @@
+#include <litmus/reservations/budget-notifier.h>
+
+void budget_notifier_list_init(struct budget_notifier_list* bnl)
+{
+        INIT_LIST_HEAD(&bnl->list);
+        raw_spin_lock_init(&bnl->lock);
+}
+
+void budget_notifiers_fire(struct budget_notifier_list *bnl, bool replenished)
+{
+        struct budget_notifier *bn, *next;
+
+        unsigned long flags;
+
+        raw_spin_lock_irqsave(&bnl->lock, flags);
+
+        list_for_each_entry_safe(bn, next, &bnl->list, list) {
+                if (replenished)
+                        bn->budget_replenished(bn);
+                else
+                        bn->budget_exhausted(bn);
+        }
+
+        raw_spin_unlock_irqrestore(&bnl->lock, flags);
+}
+
diff --git a/litmus/reservations/core.c b/litmus/reservations/core.c
new file mode 100644
index 000000000000..cf55ca8ffd3c
--- /dev/null
+++ b/litmus/reservations/core.c
@@ -0,0 +1,392 @@
+#include <linux/sched.h>
+
+#include <litmus/litmus.h>
+#include <litmus/reservations/reservation.h>
+
+void reservation_init(struct reservation *res)
+{
+        memset(res, 0, sizeof(*res));
+        res->state = RESERVATION_INACTIVE;
+        INIT_LIST_HEAD(&res->clients);
+        INIT_LIST_HEAD(&res->replenish_list);
+        budget_notifier_list_init(&res->budget_notifiers);
+}
+
+struct task_struct* default_dispatch_client(
+        struct reservation *res,
+        lt_t *for_at_most)
+{
+        struct reservation_client *client, *next;
+        struct task_struct* tsk;
+
+        BUG_ON(res->state != RESERVATION_ACTIVE);
+        *for_at_most = 0;
+
+        list_for_each_entry_safe(client, next, &res->clients, list) {
+                tsk = client->dispatch(client);
+                if (likely(tsk)) {
+                        /* Primitive form of round-robin scheduling:
+                         * make sure we alternate between multiple clients
+                         * with at least the granularity of the replenishment
+                         * period. Reservations that need more fine-grained
+                         * or more predictable alternation between threads
+                         * within a reservation should provide a custom
+                         * dispatch function. */
+                        list_del(&client->list);
+                        /* move to back of list */
+                        list_add_tail(&client->list, &res->clients);
+                        return tsk;
+                }
+        }
+        return NULL;
+}
+
+void common_drain_budget(
+        struct reservation *res,
+        lt_t how_much)
+{
+        if (how_much >= res->cur_budget)
+                res->cur_budget = 0;
+        else
+                res->cur_budget -= how_much;
+
+        res->budget_consumed += how_much;
+        res->budget_consumed_total += how_much;
+
+        switch (res->state) {
+                case RESERVATION_DEPLETED:
+                case RESERVATION_INACTIVE:
+                        BUG();
+                        break;
+
+                case RESERVATION_ACTIVE_IDLE:
+                case RESERVATION_ACTIVE:
+                        if (!res->cur_budget) {
+                                res->env->change_state(res->env, res,
+                                        RESERVATION_DEPLETED);
+                        } /* else: stay in current state */
+                        break;
+        }
+}
+
+static struct task_struct * task_client_dispatch(struct reservation_client *client)
+{
+        struct task_client *tc = container_of(client, struct task_client, client);
+        return tc->task;
+}
+
+void task_client_init(struct task_client *tc, struct task_struct *tsk,
+        struct reservation *res)
+{
+        memset(&tc->client, 0, sizeof(tc->client));
+        tc->client.dispatch = task_client_dispatch;
+        tc->client.reservation = res;
+        tc->task = tsk;
+}
+
+static void sup_scheduler_update_at(
+        struct sup_reservation_environment* sup_env,
+        lt_t when)
+{
+        if (sup_env->next_scheduler_update > when)
+                sup_env->next_scheduler_update = when;
+}
+
+static void sup_scheduler_update_after(
+        struct sup_reservation_environment* sup_env,
+        lt_t timeout)
+{
+        sup_scheduler_update_at(sup_env, sup_env->env.current_time + timeout);
+}
+
+static int _sup_queue_depleted(
+        struct sup_reservation_environment* sup_env,
+        struct reservation *res)
+{
+        struct list_head *pos;
+        struct reservation *queued;
+        int passed_earlier = 0;
+
+        BUG_ON(in_list(&res->replenish_list));
+
+        list_for_each(pos, &sup_env->depleted_reservations) {
+                queued = list_entry(pos, struct reservation, replenish_list);
+                if (queued->next_replenishment > res->next_replenishment) {
+                        list_add(&res->replenish_list, pos->prev);
+                        return passed_earlier;
+                } else
+                        passed_earlier = 1;
+        }
+
+        list_add_tail(&res->replenish_list, &sup_env->depleted_reservations);
+
+        return passed_earlier;
+}
+
+static void sup_queue_depleted(
+        struct sup_reservation_environment* sup_env,
+        struct reservation *res)
+{
+        int passed_earlier = _sup_queue_depleted(sup_env, res);
+
+        /* check for updated replenishment time */
+        if (!passed_earlier)
+                sup_scheduler_update_at(sup_env, res->next_replenishment);
+}
+
+static int _sup_queue_active(
+        struct sup_reservation_environment* sup_env,
+        struct reservation *res)
+{
+        struct list_head *pos;
+        struct reservation *queued;
+        int passed_active = 0;
+
+        if (likely(res->priority != RESERVATION_BACKGROUND_PRIORITY)) {
+                /* enqueue in order of priority */
+                list_for_each(pos, &sup_env->active_reservations) {
+                        queued = list_entry(pos, struct reservation, list);
+                        if (queued->priority > res->priority) {
+                                list_add(&res->list, pos->prev);
+                                return passed_active;
+                        } else if (queued->state == RESERVATION_ACTIVE)
+                                passed_active = 1;
+                }
+        } else {
+                /* don't preempt unless the list happens to be empty */
+                passed_active = !list_empty(&sup_env->active_reservations);
+        }
+        /* Either a background reservation, or we fell off the end of the list.
+         * In both cases, just add the reservation to the end of the list of
+         * active reservations. */
+        list_add_tail(&res->list, &sup_env->active_reservations);
+        return passed_active;
+}
+
+static void sup_queue_active(
+        struct sup_reservation_environment* sup_env,
+        struct reservation *res)
+{
+        int passed_active = _sup_queue_active(sup_env, res);
+
+        /* check for possible preemption */
+        if (res->state == RESERVATION_ACTIVE && !passed_active)
+                sup_env->next_scheduler_update = SUP_RESCHEDULE_NOW;
+        else if (res == list_first_entry(&sup_env->active_reservations,
+                                         struct reservation, list)) {
+                /* First reservation is draining budget => make sure
+                 * the scheduler is called to notice when the reservation
+                 * budget has been drained completely. */
+                sup_scheduler_update_after(sup_env, res->cur_budget);
+        }
+}
+
+static void sup_queue_reservation(
+        struct sup_reservation_environment* sup_env,
+        struct reservation *res)
+{
+        switch (res->state) {
+                case RESERVATION_INACTIVE:
+                        list_add(&res->list, &sup_env->inactive_reservations);
+                        break;
+
+                case RESERVATION_DEPLETED:
+                        sup_queue_depleted(sup_env, res);
+                        break;
+
+                case RESERVATION_ACTIVE_IDLE:
+                case RESERVATION_ACTIVE:
+                        sup_queue_active(sup_env, res);
+                        break;
+        }
+}
+
+void sup_add_new_reservation(
+        struct sup_reservation_environment* sup_env,
+        struct reservation* new_res)
+{
+        new_res->env = &sup_env->env;
+        list_add(&new_res->all_list, &sup_env->all_reservations);
+        sup_queue_reservation(sup_env, new_res);
+}
+
+struct reservation* sup_find_by_id(struct sup_reservation_environment* sup_env,
+        unsigned int id)
+{
+        struct reservation *res;
+
+        list_for_each_entry(res, &sup_env->all_reservations, all_list) {
+                if (res->id == id)
+                        return res;
+        }
+
+        return NULL;
+}
+
+static void sup_charge_budget(
+        struct sup_reservation_environment* sup_env,
+        lt_t delta)
+{
+        struct reservation *res;
+
+        /* charge the highest-priority ACTIVE or ACTIVE_IDLE reservation */
+
+        res = list_first_entry_or_null(
+                &sup_env->active_reservations, struct reservation, list);
+
+        if (res) {
+                TRACE("R%d: charging at %llu for %llu execution, budget before: %llu\n",
+                        res->id, res->env->current_time, delta, res->cur_budget);
+                res->ops->drain_budget(res, delta);
+                TRACE("R%d: budget now: %llu, priority: %llu\n",
+                        res->id, res->cur_budget, res->priority);
+        }
+
+        /* check when the next budget expires */
+
+        res = list_first_entry_or_null(
+                &sup_env->active_reservations, struct reservation, list);
+
+        if (res) {
+                /* make sure scheduler is invoked when this reservation expires
+                 * its remaining budget */
+                TRACE("requesting scheduler update for reservation %u "
+                        "in %llu nanoseconds\n",
+                        res->id, res->cur_budget);
+                sup_scheduler_update_after(sup_env, res->cur_budget);
+        }
+}
+
+static void sup_replenish_budgets(struct sup_reservation_environment* sup_env)
+{
+        struct list_head *pos, *next;
+        struct reservation *res;
+
+        list_for_each_safe(pos, next, &sup_env->depleted_reservations) {
+                res = list_entry(pos, struct reservation, replenish_list);
+                if (res->next_replenishment <= sup_env->env.current_time) {
+                        TRACE("R%d: replenishing budget at %llu, "
+                              "priority: %llu\n",
+                                res->id, res->env->current_time, res->priority);
+                        res->ops->replenish(res);
+                } else {
+                        /* list is ordered by increasing depletion times */
+                        break;
+                }
+        }
+
+        /* request a scheduler update at the next replenishment instant */
+        res = list_first_entry_or_null(&sup_env->depleted_reservations,
+                struct reservation, replenish_list);
+        if (res)
+                sup_scheduler_update_at(sup_env, res->next_replenishment);
+}
+
+void sup_update_time(
+        struct sup_reservation_environment* sup_env,
+        lt_t now)
+{
+        lt_t delta;
+
+        /* If the time didn't advance, there is nothing to do.
+         * This check makes it safe to call sup_advance_time() potentially
+         * multiple times (e.g., via different code paths. */
+        if (!list_empty(&sup_env->active_reservations))
+                TRACE("(sup_update_time) now: %llu, current_time: %llu\n", now,
+                        sup_env->env.current_time);
+        if (unlikely(now <= sup_env->env.current_time))
+                return;
+
+        delta = now - sup_env->env.current_time;
+        sup_env->env.current_time = now;
+
+        /* check if future updates are required */
+        if (sup_env->next_scheduler_update <= sup_env->env.current_time)
+                sup_env->next_scheduler_update = SUP_NO_SCHEDULER_UPDATE;
+
+        /* deplete budgets by passage of time */
+        sup_charge_budget(sup_env, delta);
+
+        /* check if any budgets were replenished */
+        sup_replenish_budgets(sup_env);
+}
+
+struct task_struct* sup_dispatch(struct sup_reservation_environment* sup_env)
+{
+        struct reservation *res, *next;
+        struct task_struct *tsk = NULL;
+        lt_t time_slice;
+
+        list_for_each_entry_safe(res, next, &sup_env->active_reservations, list) {
+                if (res->state == RESERVATION_ACTIVE) {
+                        tsk = res->ops->dispatch_client(res, &time_slice);
+                        if (likely(tsk)) {
+                                if (time_slice)
+                                    sup_scheduler_update_after(sup_env, time_slice);
+                                sup_scheduler_update_after(sup_env, res->cur_budget);
+                                return tsk;
+                        }
+                }
+        }
+
+        return NULL;
+}
+
+static void sup_res_change_state(
+        struct reservation_environment* env,
+        struct reservation *res,
+        reservation_state_t new_state)
+{
+        struct sup_reservation_environment* sup_env;
+
+        sup_env = container_of(env, struct sup_reservation_environment, env);
+
+        TRACE("reservation R%d state %d->%d at %llu\n",
+                res->id, res->state, new_state, env->current_time);
+
+        if (new_state == RESERVATION_DEPLETED
+            && (res->state == RESERVATION_ACTIVE ||
+                res->state == RESERVATION_ACTIVE_IDLE)) {
+                budget_notifiers_fire(&res->budget_notifiers, false);
+        } else if (res->state == RESERVATION_DEPLETED
+                   && new_state == RESERVATION_ACTIVE) {
+                budget_notifiers_fire(&res->budget_notifiers, true);
+        }
+
+        /* dequeue prior to re-queuing */
+        if (res->state == RESERVATION_DEPLETED)
+                list_del(&res->replenish_list);
+        else
+                list_del(&res->list);
+
+        /* check if we need to reschedule because we lost an active reservation */
+        if (res->state == RESERVATION_ACTIVE && !sup_env->will_schedule)
+                sup_env->next_scheduler_update = SUP_RESCHEDULE_NOW;
+        res->state = new_state;
+        sup_queue_reservation(sup_env, res);
+}
+
+static void sup_request_replenishment(
+        struct reservation_environment* env,
+        struct reservation *res)
+{
+        struct sup_reservation_environment* sup_env;
+
+        sup_env = container_of(env, struct sup_reservation_environment, env);
+        sup_queue_depleted(sup_env, res);
+}
+
+void sup_init(struct sup_reservation_environment* sup_env)
+{
+        memset(sup_env, 0, sizeof(*sup_env));
+
+        INIT_LIST_HEAD(&sup_env->all_reservations);
+        INIT_LIST_HEAD(&sup_env->active_reservations);
+        INIT_LIST_HEAD(&sup_env->depleted_reservations);
+        INIT_LIST_HEAD(&sup_env->inactive_reservations);
+
+        sup_env->env.change_state = sup_res_change_state;
+        sup_env->env.request_replenishment = sup_request_replenishment;
+
+        sup_env->next_scheduler_update = SUP_NO_SCHEDULER_UPDATE;
+}
diff --git a/litmus/reservations/polling.c b/litmus/reservations/polling.c
new file mode 100644
index 000000000000..63e0bed566e8
--- /dev/null
+++ b/litmus/reservations/polling.c
@@ -0,0 +1,256 @@
+#include <linux/sched.h>
+
+#include <litmus/litmus.h>
+#include <litmus/reservations/reservation.h>
+#include <litmus/reservations/polling.h>
+
+
+static void periodic_polling_client_arrives(
+        struct reservation* res,
+        struct reservation_client *client
+)
+{
+        struct polling_reservation *pres =
+                container_of(res, struct polling_reservation, res);
+        lt_t instances, tmp;
+
+        list_add_tail(&client->list, &res->clients);
+
+        switch (res->state) {
+                case RESERVATION_INACTIVE:
+                        /* Figure out next replenishment time. */
+                        tmp = res->env->current_time - res->env->time_zero;
+                        instances =  div64_u64(tmp, pres->period);
+                        res->next_replenishment =
+                                (instances + 1) * pres->period + pres->offset;
+
+                        TRACE("pol-res: activate tmp=%llu instances=%llu period=%llu nextrp=%llu cur=%llu\n",
+                                tmp, instances, pres->period, res->next_replenishment,
+                                res->env->current_time);
+
+                        res->env->change_state(res->env, res,
+                                RESERVATION_DEPLETED);
+                        break;
+
+                case RESERVATION_ACTIVE:
+                case RESERVATION_DEPLETED:
+                        /* do nothing */
+                        break;
+
+                case RESERVATION_ACTIVE_IDLE:
+                        res->env->change_state(res->env, res,
+                                RESERVATION_ACTIVE);
+                        break;
+        }
+}
+
+
+static void periodic_polling_client_departs(
+        struct reservation *res,
+        struct reservation_client *client,
+        int did_signal_job_completion
+)
+{
+        list_del(&client->list);
+
+        switch (res->state) {
+                case RESERVATION_INACTIVE:
+                case RESERVATION_ACTIVE_IDLE:
+                        BUG(); /* INACTIVE or IDLE <=> no client */
+                        break;
+
+                case RESERVATION_ACTIVE:
+                        if (list_empty(&res->clients)) {
+                                res->env->change_state(res->env, res,
+                                                RESERVATION_ACTIVE_IDLE);
+                        } /* else: nothing to do, more clients ready */
+                        break;
+
+                case RESERVATION_DEPLETED:
+                        /* do nothing */
+                        break;
+        }
+}
+
+static void periodic_polling_on_replenishment(
+        struct reservation *res
+)
+{
+        struct polling_reservation *pres =
+                container_of(res, struct polling_reservation, res);
+
+        /* replenish budget */
+        res->cur_budget = pres->max_budget;
+        res->next_replenishment += pres->period;
+        res->budget_consumed = 0;
+
+        switch (res->state) {
+                case RESERVATION_DEPLETED:
+                case RESERVATION_INACTIVE:
+                case RESERVATION_ACTIVE_IDLE:
+                        if (list_empty(&res->clients))
+                                /* no clients => poll again later */
+                                res->env->change_state(res->env, res,
+                                        RESERVATION_INACTIVE);
+                        else
+                                /* we have clients & budget => ACTIVE */
+                                res->env->change_state(res->env, res,
+                                        RESERVATION_ACTIVE);
+                        break;
+
+                case RESERVATION_ACTIVE:
+                        /* Replenished while active => tardy? In any case,
+                         * go ahead and stay active. */
+                        break;
+        }
+}
+
+static void periodic_polling_on_replenishment_edf(
+        struct reservation *res
+)
+{
+        struct polling_reservation *pres =
+                container_of(res, struct polling_reservation, res);
+
+        /* update current priority */
+        res->priority = res->next_replenishment + pres->deadline;
+
+        /* do common updates */
+        periodic_polling_on_replenishment(res);
+}
+
+static struct reservation_ops periodic_polling_ops_fp = {
+        .dispatch_client = default_dispatch_client,
+        .client_arrives = periodic_polling_client_arrives,
+        .client_departs = periodic_polling_client_departs,
+        .replenish = periodic_polling_on_replenishment,
+        .drain_budget = common_drain_budget,
+};
+
+static struct reservation_ops periodic_polling_ops_edf = {
+        .dispatch_client = default_dispatch_client,
+        .client_arrives = periodic_polling_client_arrives,
+        .client_departs = periodic_polling_client_departs,
+        .replenish = periodic_polling_on_replenishment_edf,
+        .drain_budget = common_drain_budget,
+};
+
+
+
+
+static void sporadic_polling_client_arrives_fp(
+        struct reservation* res,
+        struct reservation_client *client
+)
+{
+        struct polling_reservation *pres =
+                container_of(res, struct polling_reservation, res);
+
+        list_add_tail(&client->list, &res->clients);
+
+        switch (res->state) {
+                case RESERVATION_INACTIVE:
+                        /* Replenish now. */
+                        res->cur_budget = pres->max_budget;
+                        res->next_replenishment =
+                                res->env->current_time + pres->period;
+
+                        res->env->change_state(res->env, res,
+                                RESERVATION_ACTIVE);
+                        break;
+
+                case RESERVATION_ACTIVE:
+                case RESERVATION_DEPLETED:
+                        /* do nothing */
+                        break;
+
+                case RESERVATION_ACTIVE_IDLE:
+                        res->env->change_state(res->env, res,
+                                RESERVATION_ACTIVE);
+                        break;
+        }
+}
+
+static void sporadic_polling_client_arrives_edf(
+        struct reservation* res,
+        struct reservation_client *client
+)
+{
+        struct polling_reservation *pres =
+                container_of(res, struct polling_reservation, res);
+
+        list_add_tail(&client->list, &res->clients);
+
+        switch (res->state) {
+                case RESERVATION_INACTIVE:
+                        /* Replenish now. */
+                        res->cur_budget = pres->max_budget;
+                        res->next_replenishment =
+                                res->env->current_time + pres->period;
+                        res->priority =
+                                res->env->current_time + pres->deadline;
+
+                        res->env->change_state(res->env, res,
+                                RESERVATION_ACTIVE);
+                        break;
+
+                case RESERVATION_ACTIVE:
+                case RESERVATION_DEPLETED:
+                        /* do nothing */
+                        break;
+
+                case RESERVATION_ACTIVE_IDLE:
+                        res->env->change_state(res->env, res,
+                                RESERVATION_ACTIVE);
+                        break;
+        }
+}
+
+static struct reservation_ops sporadic_polling_ops_fp = {
+        .dispatch_client = default_dispatch_client,
+        .client_arrives = sporadic_polling_client_arrives_fp,
+        .client_departs = periodic_polling_client_departs,
+        .replenish = periodic_polling_on_replenishment,
+        .drain_budget = common_drain_budget,
+};
+
+static struct reservation_ops sporadic_polling_ops_edf = {
+        .dispatch_client = default_dispatch_client,
+        .client_arrives = sporadic_polling_client_arrives_edf,
+        .client_departs = periodic_polling_client_departs,
+        .replenish = periodic_polling_on_replenishment_edf,
+        .drain_budget = common_drain_budget,
+};
+
+void polling_reservation_init(
+        struct polling_reservation *pres,
+        int use_edf_prio,
+        int use_periodic_polling,
+        lt_t budget, lt_t period, lt_t deadline, lt_t offset
+)
+{
+        if (!deadline)
+                deadline = period;
+        BUG_ON(budget > period);
+        BUG_ON(budget > deadline);
+        BUG_ON(offset >= period);
+
+        reservation_init(&pres->res);
+        pres->max_budget = budget;
+        pres->period = period;
+        pres->deadline = deadline;
+        pres->offset = offset;
+        if (use_periodic_polling) {
+                pres->res.kind = PERIODIC_POLLING;
+                if (use_edf_prio)
+                        pres->res.ops = &periodic_polling_ops_edf;
+                else
+                        pres->res.ops = &periodic_polling_ops_fp;
+        } else {
+                pres->res.kind = SPORADIC_POLLING;
+                if (use_edf_prio)
+                        pres->res.ops = &sporadic_polling_ops_edf;
+                else
+                        pres->res.ops = &sporadic_polling_ops_fp;
+        }
+}
diff --git a/litmus/reservations/table-driven.c b/litmus/reservations/table-driven.c
new file mode 100644
index 000000000000..e4debcb5d4d2
--- /dev/null
+++ b/litmus/reservations/table-driven.c
@@ -0,0 +1,269 @@
+#include <linux/sched.h>
+
+#include <litmus/litmus.h>
+#include <litmus/reservations/reservation.h>
+#include <litmus/reservations/table-driven.h>
+
+static lt_t td_cur_major_cycle_start(struct table_driven_reservation *tdres)
+{
+        lt_t x, tmp;
+
+        tmp = tdres->res.env->current_time - tdres->res.env->time_zero;
+        x = div64_u64(tmp, tdres->major_cycle);
+        x *= tdres->major_cycle;
+        return x;
+}
+
+
+static lt_t td_next_major_cycle_start(struct table_driven_reservation *tdres)
+{
+        lt_t x, tmp;
+
+        tmp = tdres->res.env->current_time - tdres->res.env->time_zero;
+        x = div64_u64(tmp, tdres->major_cycle) + 1;
+        x *= tdres->major_cycle;
+        return x;
+}
+
+static void td_client_arrives(
+        struct reservation* res,
+        struct reservation_client *client
+)
+{
+        struct table_driven_reservation *tdres =
+                container_of(res, struct table_driven_reservation, res);
+
+        list_add_tail(&client->list, &res->clients);
+
+        switch (res->state) {
+                case RESERVATION_INACTIVE:
+                        /* Figure out first replenishment time. */
+                        tdres->major_cycle_start = td_next_major_cycle_start(tdres);
+                        res->next_replenishment  = tdres->major_cycle_start;
+                        res->next_replenishment += tdres->intervals[0].start;
+                        tdres->next_interval = 0;
+
+                        res->env->change_state(res->env, res,
+                                RESERVATION_DEPLETED);
+                        break;
+
+                case RESERVATION_ACTIVE:
+                case RESERVATION_DEPLETED:
+                        /* do nothing */
+                        break;
+
+                case RESERVATION_ACTIVE_IDLE:
+                        res->env->change_state(res->env, res,
+                                RESERVATION_ACTIVE);
+                        break;
+        }
+}
+
+static void td_client_departs(
+        struct reservation *res,
+        struct reservation_client *client,
+        int did_signal_job_completion
+)
+{
+        list_del(&client->list);
+
+        switch (res->state) {
+                case RESERVATION_INACTIVE:
+                case RESERVATION_ACTIVE_IDLE:
+                        BUG(); /* INACTIVE or IDLE <=> no client */
+                        break;
+
+                case RESERVATION_ACTIVE:
+                        if (list_empty(&res->clients)) {
+                                res->env->change_state(res->env, res,
+                                                RESERVATION_ACTIVE_IDLE);
+                        } /* else: nothing to do, more clients ready */
+                        break;
+
+                case RESERVATION_DEPLETED:
+                        /* do nothing */
+                        break;
+        }
+}
+
+static lt_t td_time_remaining_until_end(struct table_driven_reservation *tdres)
+{
+        lt_t now = tdres->res.env->current_time;
+        lt_t end = tdres->cur_interval.end;
+        TRACE("td_remaining(%u): start=%llu now=%llu end=%llu state=%d\n",
+                tdres->res.id,
+                tdres->cur_interval.start,
+                now, end,
+                tdres->res.state);
+        if (now >=  end)
+                return 0;
+        else
+                return end - now;
+}
+
+static void td_replenish(
+        struct reservation *res)
+{
+        struct table_driven_reservation *tdres =
+                container_of(res, struct table_driven_reservation, res);
+
+        TRACE("td_replenish(%u): expected_replenishment=%llu\n", res->id,
+                res->next_replenishment);
+
+        /* figure out current interval */
+        tdres->cur_interval.start = tdres->major_cycle_start +
+                tdres->intervals[tdres->next_interval].start;
+        tdres->cur_interval.end =  tdres->major_cycle_start +
+                tdres->intervals[tdres->next_interval].end;
+        TRACE("major_cycle_start=%llu => [%llu, %llu]\n",
+                tdres->major_cycle_start,
+                tdres->cur_interval.start,
+                tdres->cur_interval.end);
+
+        /* reset budget */
+        res->cur_budget = td_time_remaining_until_end(tdres);
+        res->budget_consumed = 0;
+        TRACE("td_replenish(%u): %s budget=%llu\n", res->id,
+                res->cur_budget ? "" : "WARNING", res->cur_budget);
+
+        /* prepare next slot */
+        tdres->next_interval = (tdres->next_interval + 1) % tdres->num_intervals;
+        if (!tdres->next_interval)
+                /* wrap to next major cycle */
+                tdres->major_cycle_start += tdres->major_cycle;
+
+        /* determine next time this reservation becomes eligible to execute */
+        res->next_replenishment  = tdres->major_cycle_start;
+        res->next_replenishment += tdres->intervals[tdres->next_interval].start;
+        TRACE("td_replenish(%u): next_replenishment=%llu\n", res->id,
+                res->next_replenishment);
+
+
+        switch (res->state) {
+                case RESERVATION_DEPLETED:
+                case RESERVATION_ACTIVE:
+                case RESERVATION_ACTIVE_IDLE:
+                        if (list_empty(&res->clients))
+                                res->env->change_state(res->env, res,
+                                        RESERVATION_ACTIVE_IDLE);
+                        else
+                                /* we have clients & budget => ACTIVE */
+                                res->env->change_state(res->env, res,
+                                        RESERVATION_ACTIVE);
+                        break;
+
+                case RESERVATION_INACTIVE:
+                        BUG();
+                        break;
+        }
+}
+
+static void td_drain_budget(
+                struct reservation *res,
+                lt_t how_much)
+{
+        struct table_driven_reservation *tdres =
+                container_of(res, struct table_driven_reservation, res);
+
+        res->budget_consumed += how_much;
+        res->budget_consumed_total += how_much;
+
+        /* Table-driven scheduling: instead of tracking the budget, we compute
+         * how much time is left in this allocation interval. */
+
+        /* sanity check: we should never try to drain from future slots */
+        BUG_ON(tdres->cur_interval.start > res->env->current_time);
+
+        switch (res->state) {
+                case RESERVATION_DEPLETED:
+                case RESERVATION_INACTIVE:
+                        BUG();
+                        break;
+
+                case RESERVATION_ACTIVE_IDLE:
+                case RESERVATION_ACTIVE:
+                        res->cur_budget = td_time_remaining_until_end(tdres);
+                        TRACE("td_drain_budget(%u): drained to budget=%llu\n",
+                                res->id, res->cur_budget);
+                        if (!res->cur_budget) {
+                                res->env->change_state(res->env, res,
+                                        RESERVATION_DEPLETED);
+                        } else {
+                                /* sanity check budget calculation */
+                                BUG_ON(res->env->current_time >= tdres->cur_interval.end);
+                                BUG_ON(res->env->current_time < tdres->cur_interval.start);
+                        }
+
+                        break;
+        }
+}
+
+static struct task_struct* td_dispatch_client(
+        struct reservation *res,
+        lt_t *for_at_most)
+{
+        struct task_struct *t;
+        struct table_driven_reservation *tdres =
+                container_of(res, struct table_driven_reservation, res);
+
+        /* usual logic for selecting a client */
+        t = default_dispatch_client(res, for_at_most);
+
+        TRACE_TASK(t, "td_dispatch_client(%u): selected, budget=%llu\n",
+                res->id, res->cur_budget);
+
+        /* check how much budget we have left in this time slot */
+        res->cur_budget = td_time_remaining_until_end(tdres);
+
+        TRACE_TASK(t, "td_dispatch_client(%u): updated to budget=%llu next=%d\n",
+                res->id, res->cur_budget, tdres->next_interval);
+
+        if (unlikely(!res->cur_budget)) {
+                /* Unlikely case: if we ran out of budget, the user configured
+                 * a broken scheduling table (overlapping table slots).
+                 * Not much we can do about this, but we can't dispatch a job
+                 * now without causing overload. So let's register this reservation
+                 * as depleted and wait for the next allocation. */
+                TRACE("td_dispatch_client(%u): budget unexpectedly depleted "
+                        "(check scheduling table for unintended overlap)\n",
+                        res->id);
+                res->env->change_state(res->env, res,
+                        RESERVATION_DEPLETED);
+                return NULL;
+        } else
+                return t;
+}
+
+static struct reservation_ops td_ops = {
+        .dispatch_client = td_dispatch_client,
+        .client_arrives = td_client_arrives,
+        .client_departs = td_client_departs,
+        .replenish = td_replenish,
+        .drain_budget = td_drain_budget,
+};
+
+void table_driven_reservation_init(
+        struct table_driven_reservation *tdres,
+        lt_t major_cycle,
+        struct lt_interval *intervals,
+        unsigned int num_intervals)
+{
+        unsigned int i;
+
+        /* sanity checking */
+        BUG_ON(!num_intervals);
+        for (i = 0; i < num_intervals; i++)
+                BUG_ON(intervals[i].end <= intervals[i].start);
+        for (i = 0; i + 1 < num_intervals; i++)
+                BUG_ON(intervals[i + 1].start <= intervals[i].end);
+        BUG_ON(intervals[num_intervals - 1].end > major_cycle);
+
+        reservation_init(&tdres->res);
+        tdres->res.kind = TABLE_DRIVEN;
+        tdres->major_cycle = major_cycle;
+        tdres->intervals = intervals;
+        tdres->cur_interval.start = 0;
+        tdres->cur_interval.end   = 0;
+        tdres->num_intervals = num_intervals;
+        tdres->res.ops = &td_ops;
+}