Add LITMUS^RT core implementation

This patch adds the core of LITMUS^RT:

 - library functionality (heaps, rt_domain, prioritization, etc.)
 - budget enforcement logic
 - job management
 - system call backends
 - virtual devices (control page, etc.)
 - scheduler plugin API (and dummy plugin)

This code compiles, but is not yet integrated with the rest of Linux.

Squashed changes:

LITMUS^RT Core: add get_current_budget() system call

Allow userspace to figure out the used-up and remaining budget
of a task.

Adds deadline field to control page and updates it when setting up jobs for release.

Adds control page deadline offset

ftdev: respect O_NONBLOCK flag in ftdev_read()

Don't block if userspace wants to go on doing something else.

Export job release time and job sequence number in ctrl page

Add alternate complete_job() default implementation

Let jobs sleep like regular Linux tasks by suspending and waking them
with a one-shot timer. Plugins can opt into using this implementation
instead of the classic complete_job() implementation (or custom
implementations).

Fix RCU locking in sys_get_rt_task_param()

sys_get_rt_task_param() is rarely used and apparently attracted some
bitrot.

Free before setting NULL to prevent memory leak

Add hrtimer_start_on() support

This patch replaces the previous implementation of hrtimer_start_on() by
now using smp_call_function_single_async() to arm hrtimers on remote
CPUs.

Expose LITMUS^RT system calls via control page ioctl()

Rationale: make LITMUS^RT ops available in a way that does not create
merge conflicts each time we rebase LITMUS^RT on top of a new kernel
version. This also helps with portability to different architectures,
as we no longer need to patch each architecture's syscall table.

Pick non-zero syscall ID start range

To avoid interfering with Linux's magic reserved IOCTL numbers

Don't preempt before time check in sleep_until_next_release()

Avoid preempting jobs that are about to go to sleep soon anyway.

LITMUS^RT proc: fix wrong memset()

TRACE(): add TRACE_WARN_ON() helper

Useful to replace BUG_ON() and WARN_ON() with a non-fatal
TRACE()-based equivalent.

Add void* plugin_state pointer to task_struct

LITMUS^RT: split task admission into two functions

Plugin interface: add fork_task() callback

LITMUS^RT: Enable plugins to permit RT tasks to fork

one-shot complete_job(): set completed flag

This could race with a SIGSTOP or some other forced suspension, but
we'll let plugins handle this, should they actually care.

FP: add list-based ready queue

LITMUS^RT core: add should_wait_for_stack() callback

Allow plugins to give up when waiting for a stack to become available.

LITMUS^RT core: add next_became_invalid() callback

LITMUS^RT core: add post-migration validation callback

LITMUS^RT core: be more careful when pull-migrating tasks

Close more race windows and give plugins a chance to validate
tasks after they have been migrated.

Add KConfig options for timer latency warnings

Add reservation creation API to plugin interface & syscalls

LITMUS^RT syscall: expose sys_reservation_create() via ioctl()

Add reservation configuration types to rt_param.h

Add basic generic reservation-based scheduling infrastructure

Switch to aligned quanta by default.

For first-time users, aligned quanta is likely what's expected.

LITMUS^RT core: keep track of time of last suspension

This information is needed to insert ST_COMPLETION records for
sporadic tasks.

add fields for clock_nanosleep() support

Need to communicate the intended wake-up time to the plugin wake-up handler.

LITMUS^RT core: add generic handler for sporadic job arrivals

In particular, check if a job arrival is triggered from a
clock_nanosleep() call.

add litmus->task_change_params() callback to plugin interface

Will be used by adaptive C-EDF.

Call litmus->task_change_params() from sys_set_rt_task_param()

Move trace point definition to litmus/litmus.c

If !CONFIG_SCHED_TASK_TRACE, but CONFIG_SCHED_LITMUS_TRACEPOINT, then
we still need to define the tracepoint structures.

This patch should be integrated with the earlier sched_task_trace.c
patches during one of the next major rebasing efforts.

LITMUS^RT scheduling class: mark enqueued task as present

Remove unistd_*.h

rebase fix: update to new hrtimer API

The new API is actually nicer and cleaner.

rebase fix: call lockdep_unpin_lock(&rq->lock, cookie)
The LITMUS^RT scheduling class should also do the LOCKDEP dance.

LITMUS^RT core: break out non-preemptive flag defs
Not every file including litmus.h needs to know this.

LITMUS^RT core: don't include debug_trace.h in litmus.h
Including debug_trace.h introduces the TRACE() macro, which causes
symbol clashes in some (rather obscure) drivers.

LITMUS^RT core: add litmus_preemption_in_progress flags
Used to communicate that a preemption is in progress. Set by the
scheduler; read by the plugins.

LITMUS^RT core: revise is_current_running() macro

5 files changed, 331 insertions, 0 deletions

diff --git a/include/litmus/reservations/alloc.h b/include/litmus/reservations/alloc.h
new file mode 100644
index 000000000000..b3471288c9f1
--- /dev/null
+++ b/include/litmus/reservations/alloc.h
@@ -0,0 +1,15 @@
+#ifndef LITMUS_RESERVATIONS_ALLOC_H
+#define LITMUS_RESERVATIONS_ALLOC_H
+
+#include <litmus/reservations/reservation.h>
+
+long alloc_polling_reservation(
+        int res_type,
+        struct reservation_config *config,
+        struct reservation **_res);
+
+long alloc_table_driven_reservation(
+        struct reservation_config *config,
+        struct reservation **_res);
+
+#endif
\ No newline at end of file
diff --git a/include/litmus/reservations/budget-notifier.h b/include/litmus/reservations/budget-notifier.h
new file mode 100644
index 000000000000..d831fa9d5153
--- /dev/null
+++ b/include/litmus/reservations/budget-notifier.h
@@ -0,0 +1,50 @@
+#ifndef LITMUS_BUDGET_NOTIFIER_H
+#define LITMUS_BUDGET_NOTIFIER_H
+
+#include <linux/list.h>
+#include <linux/spinlock.h>
+
+struct budget_notifier;
+
+typedef void (*budget_callback_t)  (
+        struct budget_notifier *bn
+);
+
+struct budget_notifier {
+        struct list_head list;
+        budget_callback_t budget_exhausted;
+        budget_callback_t budget_replenished;
+};
+
+struct budget_notifier_list {
+        struct list_head list;
+        raw_spinlock_t lock;
+};
+
+void budget_notifier_list_init(struct budget_notifier_list* bnl);
+
+static inline void budget_notifier_add(
+        struct budget_notifier_list *bnl,
+        struct budget_notifier *bn)
+{
+        unsigned long flags;
+
+        raw_spin_lock_irqsave(&bnl->lock, flags);
+        list_add(&bn->list, &bnl->list);
+        raw_spin_unlock_irqrestore(&bnl->lock, flags);
+}
+
+static inline void budget_notifier_remove(
+        struct budget_notifier_list *bnl,
+        struct budget_notifier *bn)
+{
+        unsigned long flags;
+
+        raw_spin_lock_irqsave(&bnl->lock, flags);
+        list_del(&bn->list);
+        raw_spin_unlock_irqrestore(&bnl->lock, flags);
+}
+
+void budget_notifiers_fire(struct budget_notifier_list *bnl, bool replenished);
+
+#endif
diff --git a/include/litmus/reservations/polling.h b/include/litmus/reservations/polling.h
new file mode 100644
index 000000000000..230e12b1088a
--- /dev/null
+++ b/include/litmus/reservations/polling.h
@@ -0,0 +1,19 @@
+#ifndef LITMUS_POLLING_RESERVATIONS_H
+#define LITMUS_POLLING_RESERVATIONS_H
+
+#include <litmus/reservations/reservation.h>
+
+struct polling_reservation {
+        /* extend basic reservation */
+        struct reservation res;
+
+        lt_t max_budget;
+        lt_t period;
+        lt_t deadline;
+        lt_t offset;
+};
+
+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);
+
+#endif
diff --git a/include/litmus/reservations/reservation.h b/include/litmus/reservations/reservation.h
new file mode 100644
index 000000000000..1752dac4e698
--- /dev/null
+++ b/include/litmus/reservations/reservation.h
@@ -0,0 +1,224 @@
+#ifndef LITMUS_RESERVATION_H
+#define LITMUS_RESERVATION_H
+
+#include <linux/list.h>
+#include <linux/hrtimer.h>
+
+#include <litmus/debug_trace.h>
+#include <litmus/reservations/budget-notifier.h>
+
+struct reservation_client;
+struct reservation_environment;
+struct reservation;
+
+typedef enum {
+        /* reservation has no clients, is not consuming budget */
+        RESERVATION_INACTIVE = 0,
+
+        /* reservation has clients, consumes budget when scheduled */
+        RESERVATION_ACTIVE,
+
+        /* reservation has no clients, but may be consuming budget */
+        RESERVATION_ACTIVE_IDLE,
+
+        /* Reservation has no budget and waits for
+         * replenishment. May or may not have clients. */
+        RESERVATION_DEPLETED,
+} reservation_state_t;
+
+
+/* ************************************************************************** */
+
+/* Select which task to dispatch. If NULL is returned, it means there is nothing
+ * to schedule right now and background work can be scheduled. */
+typedef struct task_struct * (*dispatch_t)  (
+        struct reservation_client *client
+);
+
+/* Something that can be managed in a reservation and that can yield
+ * a process for dispatching. Contains a pointer to the reservation
+ * to which it "belongs". */
+struct reservation_client {
+        struct list_head list;
+        struct reservation* reservation;
+        dispatch_t dispatch;
+};
+
+
+/* ************************************************************************** */
+
+/* Called by reservations to request state change. */
+typedef void (*reservation_change_state_t)  (
+        struct reservation_environment* env,
+        struct reservation *res,
+        reservation_state_t new_state
+);
+
+/* Called by reservations to request replenishment while not DEPLETED.
+ * Useful for soft reservations that remain ACTIVE with lower priority. */
+typedef void (*request_replenishment_t)(
+        struct reservation_environment* env,
+        struct reservation *res
+);
+
+/* The framework within wich reservations operate. */
+struct reservation_environment {
+        lt_t time_zero;
+        lt_t current_time;
+
+        /* services invoked by reservations */
+        reservation_change_state_t change_state;
+        request_replenishment_t request_replenishment;
+};
+
+/* ************************************************************************** */
+
+/* A new client is added or an existing client resumes. */
+typedef void (*client_arrives_t)  (
+        struct reservation *reservation,
+        struct reservation_client *client
+);
+
+/* A client suspends or terminates. */
+typedef void (*client_departs_t)  (
+        struct reservation *reservation,
+        struct reservation_client *client,
+        int did_signal_job_completion
+);
+
+/* A previously requested replenishment has occurred. */
+typedef void (*on_replenishment_timer_t)  (
+        struct reservation *reservation
+);
+
+/* Update the reservation's budget to reflect execution or idling. */
+typedef void (*drain_budget_t) (
+        struct reservation *reservation,
+        lt_t how_much
+);
+
+/* Select a ready task from one of the clients for scheduling. */
+typedef struct task_struct* (*dispatch_client_t)  (
+        struct reservation *reservation,
+        lt_t *time_slice /* May be used to force rescheduling after
+                            some amount of time. 0 => no limit */
+);
+
+/* Destructor: called before scheduler is deactivated. */
+typedef void (*shutdown_t)(struct reservation *reservation);
+
+struct reservation_ops {
+        dispatch_client_t dispatch_client;
+
+        client_arrives_t client_arrives;
+        client_departs_t client_departs;
+
+        on_replenishment_timer_t replenish;
+        drain_budget_t drain_budget;
+
+        shutdown_t shutdown;
+};
+
+#define RESERVATION_BACKGROUND_PRIORITY ULLONG_MAX
+
+struct reservation {
+        /* used to queue in environment */
+        struct list_head list;
+        struct list_head replenish_list;
+
+        reservation_state_t state;
+        unsigned int id;
+        unsigned int kind;
+
+        /* exact meaning defined by impl. */
+        lt_t priority;
+        lt_t cur_budget;
+        lt_t next_replenishment;
+
+        /* budget stats */
+        lt_t budget_consumed; /* how much budget consumed in this allocation cycle? */
+        lt_t budget_consumed_total;
+
+        /* list of registered budget callbacks */
+        struct budget_notifier_list budget_notifiers;
+
+        /* for memory reclamation purposes */
+        struct list_head all_list;
+
+        /* interaction with framework */
+        struct reservation_environment *env;
+        struct reservation_ops *ops;
+
+        struct list_head clients;
+};
+
+void reservation_init(struct reservation *res);
+
+/* Default implementations */
+
+/* simply select the first client in the list, set *for_at_most to zero */
+struct task_struct* default_dispatch_client(
+        struct reservation *res,
+        lt_t *for_at_most
+);
+
+/* drain budget at linear rate, enter DEPLETED state when budget used up */
+void common_drain_budget(struct reservation *res, lt_t how_much);
+
+/* "connector" reservation client to hook up tasks with reservations */
+struct task_client {
+        struct reservation_client client;
+        struct task_struct *task;
+};
+
+void task_client_init(struct task_client *tc, struct task_struct *task,
+        struct reservation *reservation);
+
+#define SUP_RESCHEDULE_NOW (0)
+#define SUP_NO_SCHEDULER_UPDATE (ULLONG_MAX)
+
+/* A simple uniprocessor (SUP) flat (i.e., non-hierarchical) reservation
+ * environment.
+ */
+struct sup_reservation_environment {
+        struct reservation_environment env;
+
+        /* ordered by priority */
+        struct list_head active_reservations;
+
+        /* ordered by next_replenishment */
+        struct list_head depleted_reservations;
+
+        /* unordered */
+        struct list_head inactive_reservations;
+
+        /* list of all reservations */
+        struct list_head all_reservations;
+
+        /* - SUP_RESCHEDULE_NOW means call sup_dispatch() now
+         * - SUP_NO_SCHEDULER_UPDATE means nothing to do
+         * any other value means program a timer for the given time
+         */
+        lt_t next_scheduler_update;
+        /* set to true if a call to sup_dispatch() is imminent */
+        bool will_schedule;
+};
+
+/* Contract:
+ *  - before calling into sup_ code, or any reservation methods,
+ *    update the time with sup_update_time(); and
+ *  - after calling into sup_ code, or any reservation methods,
+ *    check next_scheduler_update and program timer or trigger
+ *    scheduler invocation accordingly.
+ */
+
+void sup_init(struct sup_reservation_environment* sup_env);
+void sup_add_new_reservation(struct sup_reservation_environment* sup_env,
+        struct reservation* new_res);
+void sup_update_time(struct sup_reservation_environment* sup_env, lt_t now);
+struct task_struct* sup_dispatch(struct sup_reservation_environment* sup_env);
+
+struct reservation* sup_find_by_id(struct sup_reservation_environment* sup_env,
+        unsigned int id);
+
+#endif
diff --git a/include/litmus/reservations/table-driven.h b/include/litmus/reservations/table-driven.h
new file mode 100644
index 000000000000..b6302a2f200d
--- /dev/null
+++ b/include/litmus/reservations/table-driven.h
@@ -0,0 +1,23 @@
+#ifndef LITMUS_RESERVATIONS_TABLE_DRIVEN_H
+#define LITMUS_RESERVATIONS_TABLE_DRIVEN_H
+
+#include <litmus/reservations/reservation.h>
+
+struct table_driven_reservation {
+        /* extend basic reservation */
+        struct reservation res;
+
+        lt_t major_cycle;
+        unsigned int next_interval;
+        unsigned int num_intervals;
+        struct lt_interval *intervals;
+
+        /* info about current scheduling slot */
+        struct lt_interval cur_interval;
+        lt_t major_cycle_start;
+};
+
+void table_driven_reservation_init(struct table_driven_reservation *tdres,
+        lt_t major_cycle, struct lt_interval *intervals, unsigned int num_intervals);
+
+#endif