From ff210e0441b743890ad85c7335e41894b34a1431 Mon Sep 17 00:00:00 2001 From: Namhoon Kim Date: Wed, 23 Mar 2016 08:20:51 -0400 Subject: MC2 scheduler and partition modules --- include/litmus/cache_proc.h | 5 + include/litmus/litmus.h | 7 + include/litmus/mc2_common.h | 31 + include/litmus/polling_reservations.h | 36 + include/litmus/reservation.h | 256 +++++ include/litmus/rt_param.h | 51 +- include/litmus/sched_plugin.h | 8 + include/litmus/trace.h | 16 +- litmus/Makefile | 5 + litmus/bank_proc.c | 737 +++++++++++++ litmus/cache_proc.c | 257 ++++- litmus/mc2_common.c | 78 ++ litmus/polling_reservations.c | 564 ++++++++++ litmus/reservation.c | 709 +++++++++++++ litmus/sched_mc2.c | 1849 +++++++++++++++++++++++++++++++++ 15 files changed, 4605 insertions(+), 4 deletions(-) create mode 100644 include/litmus/mc2_common.h create mode 100644 include/litmus/polling_reservations.h create mode 100644 include/litmus/reservation.h create mode 100644 litmus/bank_proc.c create mode 100644 litmus/mc2_common.c create mode 100644 litmus/polling_reservations.c create mode 100644 litmus/reservation.c create mode 100644 litmus/sched_mc2.c diff --git a/include/litmus/cache_proc.h b/include/litmus/cache_proc.h index 586224118435..962851da34cc 100644 --- a/include/litmus/cache_proc.h +++ b/include/litmus/cache_proc.h @@ -4,6 +4,11 @@ #ifdef __KERNEL__ void litmus_setup_lockdown(void __iomem*, u32); +void enter_irq_mode(void); +void exit_irq_mode(void); +void flush_cache(int all); + +extern struct page *new_alloc_page_color(unsigned long color); #endif diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h index a6eb534ee0fa..441210c84ed8 100644 --- a/include/litmus/litmus.h +++ b/include/litmus/litmus.h @@ -113,6 +113,13 @@ static inline lt_t litmus_clock(void) ((current)->state == TASK_RUNNING || \ preempt_count() & PREEMPT_ACTIVE) +#define is_running(t) \ + ((t)->state == TASK_RUNNING || \ + task_thread_info(t)->preempt_count & PREEMPT_ACTIVE) + +#define is_blocked(t) \ + (!is_running(t)) + #define is_released(t, now) \ (lt_before_eq(get_release(t), now)) #define is_tardy(t, now) \ diff --git a/include/litmus/mc2_common.h b/include/litmus/mc2_common.h new file mode 100644 index 000000000000..e3c0af28f1b9 --- /dev/null +++ b/include/litmus/mc2_common.h @@ -0,0 +1,31 @@ +/* + * MC^2 common data structures + */ + +#ifndef __UNC_MC2_COMMON_H__ +#define __UNC_MC2_COMMON_H__ + +enum crit_level { + CRIT_LEVEL_A = 0, + CRIT_LEVEL_B = 1, + CRIT_LEVEL_C = 2, + NUM_CRIT_LEVELS = 3, +}; + +struct mc2_task { + enum crit_level crit; + unsigned int res_id; +}; + +#ifdef __KERNEL__ + +#include + +#define tsk_mc2_data(t) (tsk_rt(t)->mc2_data) + +long mc2_task_client_init(struct task_client *tc, struct mc2_task *mc2_param, struct task_struct *tsk, + struct reservation *res); + +#endif /* __KERNEL__ */ + +#endif \ No newline at end of file diff --git a/include/litmus/polling_reservations.h b/include/litmus/polling_reservations.h new file mode 100644 index 000000000000..66c9b1e31f20 --- /dev/null +++ b/include/litmus/polling_reservations.h @@ -0,0 +1,36 @@ +#ifndef LITMUS_POLLING_RESERVATIONS_H +#define LITMUS_POLLING_RESERVATIONS_H + +#include + +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); + +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 diff --git a/include/litmus/reservation.h b/include/litmus/reservation.h new file mode 100644 index 000000000000..7e022b34470f --- /dev/null +++ b/include/litmus/reservation.h @@ -0,0 +1,256 @@ +#ifndef LITMUS_RESERVATION_H +#define LITMUS_RESERVATION_H + +#include +#include + +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 +); + +/* 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; +}; + + +/* ************************************************************************** */ + +/* 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 */ +); + + +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; +}; + +struct reservation { + /* used to queue in environment */ + struct list_head list; + + reservation_state_t state; + unsigned int id; + + /* 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; + + /* interaction with framework */ + struct reservation_environment *env; + struct reservation_ops *ops; + + struct list_head clients; + + /* for global env. */ + int scheduled_on; + int event_added; + /* for blocked by ghost. Do not charge budget when ACTIVE */ + int blocked_by_ghost; + /* ghost_job. If it is clear, do not charge budget when ACTIVE_IDLE */ + int is_ghost; +}; + +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 +); + +/* "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; + + /* - 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_scheduler_update_after(struct sup_reservation_environment* sup_env, + lt_t timeout); +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); + +/* A global multiprocessor reservation environment. */ + +typedef enum { + EVENT_REPLENISH = 0, + EVENT_DRAIN, + EVENT_OTHERS, +} event_type_t; + + +struct next_timer_event { + lt_t next_update; + int timer_armed_on; + unsigned int id; + event_type_t type; + struct list_head list; +}; + +struct gmp_reservation_environment { + raw_spinlock_t lock; + 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; + + /* timer event ordered by next_update */ + struct list_head next_events; + + /* (schedule_now == true) means call gmp_dispatch() now */ + int schedule_now; + /* set to true if a call to gmp_dispatch() is imminent */ + bool will_schedule; +}; + +void gmp_init(struct gmp_reservation_environment* gmp_env); +void gmp_add_new_reservation(struct gmp_reservation_environment* gmp_env, + struct reservation* new_res); +void gmp_add_event_after(struct gmp_reservation_environment* gmp_env, + lt_t timeout, unsigned int id, event_type_t type); +void gmp_print_events(struct gmp_reservation_environment* gmp_env, lt_t now); +int gmp_update_time(struct gmp_reservation_environment* gmp_env, lt_t now); +struct task_struct* gmp_dispatch(struct gmp_reservation_environment* gmp_env); +struct next_timer_event* gmp_find_event_by_id(struct gmp_reservation_environment* gmp_env, unsigned int id); +struct next_timer_event* gmp_find_event_by_time(struct gmp_reservation_environment* gmp_env, lt_t when); +struct reservation* gmp_find_by_id(struct gmp_reservation_environment* gmp_env, + unsigned int id); + +#endif diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h index 7b9a90965c25..998762051a6b 100644 --- a/include/litmus/rt_param.h +++ b/include/litmus/rt_param.h @@ -62,6 +62,7 @@ typedef enum { #define LITMUS_MAX_PRIORITY 512 #define LITMUS_HIGHEST_PRIORITY 1 #define LITMUS_LOWEST_PRIORITY (LITMUS_MAX_PRIORITY - 1) +#define LITMUS_NO_PRIORITY UINT_MAX /* Provide generic comparison macros for userspace, * in case that we change this later. */ @@ -71,6 +72,46 @@ typedef enum { ((p) >= LITMUS_HIGHEST_PRIORITY && \ (p) <= LITMUS_LOWEST_PRIORITY) +/* reservation support */ + +typedef enum { + PERIODIC_POLLING, + SPORADIC_POLLING, + TABLE_DRIVEN, +} reservation_type_t; + +struct lt_interval { + lt_t start; + lt_t end; +}; + +#ifndef __KERNEL__ +#define __user +#endif + +struct reservation_config { + unsigned int id; + lt_t priority; + int cpu; + + union { + struct { + lt_t period; + lt_t budget; + lt_t relative_deadline; + lt_t offset; + } polling_params; + + struct { + lt_t major_cycle_length; + unsigned int num_intervals; + struct lt_interval __user *intervals; + } table_driven_params; + }; +}; + +/* regular sporadic task support */ + struct rt_task { lt_t exec_cost; lt_t period; @@ -165,6 +206,7 @@ struct rt_job { }; struct pfair_param; +struct mc2_task; /* RT task parameters for scheduling extensions * These parameters are inherited during clone and therefore must @@ -246,7 +288,10 @@ struct rt_param { volatile int linked_on; /* PFAIR/PD^2 state. Allocated on demand. */ - struct pfair_param* pfair; + union { + void *plugin_state; + struct pfair_param *pfair; + }; /* Fields saved before BE->RT transition. */ @@ -275,6 +320,10 @@ struct rt_param { /* Pointer to the page shared between userspace and kernel. */ struct control_page * ctrl_page; + + /* Mixed-criticality specific data */ + struct mc2_task* mc2_data; + unsigned long addr_ctrl_page; }; #endif diff --git a/include/litmus/sched_plugin.h b/include/litmus/sched_plugin.h index f36bb3875f58..4c8aaa6b6674 100644 --- a/include/litmus/sched_plugin.h +++ b/include/litmus/sched_plugin.h @@ -83,6 +83,10 @@ typedef void (*synchronous_release_at_t)(lt_t time_zero); * reservation-specific values. */ typedef void (*current_budget_t)(lt_t *used_so_far, lt_t *remaining); +/* Reservation creation/removal backends. Meaning of reservation_type and + * reservation_id are entirely plugin-specific. */ +typedef long (*reservation_create_t)(int reservation_type, void* __user config); +typedef long (*reservation_destroy_t)(unsigned int reservation_id, int cpu); /************************ misc routines ***********************/ @@ -118,6 +122,10 @@ struct sched_plugin { current_budget_t current_budget; + /* Reservation support */ + reservation_create_t reservation_create; + reservation_destroy_t reservation_destroy; + #ifdef CONFIG_LITMUS_LOCKING /* locking protocols */ allocate_lock_t allocate_lock; diff --git a/include/litmus/trace.h b/include/litmus/trace.h index 601787214037..24ca412e1184 100644 --- a/include/litmus/trace.h +++ b/include/litmus/trace.h @@ -118,6 +118,9 @@ feather_callback void save_cpu_task_latency(unsigned long event, unsigned long w #define TS_TICK_START(t) CPU_TTIMESTAMP(110, t) #define TS_TICK_END(t) CPU_TTIMESTAMP(111, t) +#define TS_RELEASE_C_START CPU_DTIMESTAMP(108, TSK_RT) +#define TS_RELEASE_C_END CPU_DTIMESTAMP(109, TSK_RT) + #define TS_QUANTUM_BOUNDARY_START CPU_TIMESTAMP_CUR(112) #define TS_QUANTUM_BOUNDARY_END CPU_TIMESTAMP_CUR(113) @@ -137,6 +140,17 @@ feather_callback void save_cpu_task_latency(unsigned long event, unsigned long w #define TS_SEND_RESCHED_START(c) MSG_TIMESTAMP_SENT(190, c) #define TS_SEND_RESCHED_END MSG_TIMESTAMP_RECEIVED(191) -#define TS_RELEASE_LATENCY(when) CPU_LTIMESTAMP(208, &(when)) +#define TS_ISR_START CPU_TIMESTAMP_CUR(192) +#define TS_ISR_END CPU_TIMESTAMP_CUR(193) + +#define TS_RELEASE_LATENCY(when) CPU_LTIMESTAMP(208, &(when)) +#define TS_RELEASE_LATENCY_A(when) CPU_LTIMESTAMP(209, &(when)) +#define TS_RELEASE_LATENCY_B(when) CPU_LTIMESTAMP(210, &(when)) +#define TS_RELEASE_LATENCY_C(when) CPU_LTIMESTAMP(211, &(when)) + +#define TS_SCHED_A_START CPU_DTIMESTAMP(212, TSK_UNKNOWN) +#define TS_SCHED_A_END(t) CPU_TTIMESTAMP(213, t) +#define TS_SCHED_C_START CPU_DTIMESTAMP(214, TSK_UNKNOWN) +#define TS_SCHED_C_END(t) CPU_TTIMESTAMP(215, t) #endif /* !_SYS_TRACE_H_ */ diff --git a/litmus/Makefile b/litmus/Makefile index f80a3c0d05aa..4a34b4d338a1 100644 --- a/litmus/Makefile +++ b/litmus/Makefile @@ -11,6 +11,7 @@ obj-y = sched_plugin.o litmus.o \ sync.o \ rt_domain.o \ edf_common.o \ + mc2_common.o \ fp_common.o \ fdso.o \ locking.o \ @@ -19,9 +20,13 @@ obj-y = sched_plugin.o litmus.o \ binheap.o \ ctrldev.o \ uncachedev.o \ + reservation.o \ + polling_reservations.o \ sched_gsn_edf.o \ sched_psn_edf.o \ sched_pfp.o \ + sched_mc2.o \ + bank_proc.o \ cache_proc.o obj-$(CONFIG_PLUGIN_CEDF) += sched_cedf.o diff --git a/litmus/bank_proc.c b/litmus/bank_proc.c new file mode 100644 index 000000000000..6103611211ce --- /dev/null +++ b/litmus/bank_proc.c @@ -0,0 +1,737 @@ +/* + * bank_proc.c -- Implementation of the page coloring for cache and bank partition. + * The file will keep a pool of colored pages. Users can require pages with + * specific color or bank number. + * Part of the code is modified from Jonathan Herman's code + */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +#define LITMUS_LOCKDEP_NAME_MAX_LEN 50 + +// This Address Decoding is used in imx6-sabredsd platform +#define BANK_MASK 0x38000000 +#define BANK_SHIFT 27 +#define CACHE_MASK 0x0000f000 +#define CACHE_SHIFT 12 + +#define PAGES_PER_COLOR 1024 +unsigned int NUM_PAGE_LIST; //8*16 + +unsigned int number_banks; +unsigned int number_cachecolors; + +unsigned int set_partition_max = 0x0000ffff; +unsigned int set_partition_min = 0; +unsigned int bank_partition_max = 0x000000ff; +unsigned int bank_partition_min = 0; + +int show_page_pool = 0; +int refill_page_pool = 0; +spinlock_t reclaim_lock; + +unsigned int set_partition[9] = { + 0x00000003, /* Core 0, and Level A*/ + 0x00000003, /* Core 0, and Level B*/ + 0x0000000C, /* Core 1, and Level A*/ + 0x0000000C, /* Core 1, and Level B*/ + 0x00000030, /* Core 2, and Level A*/ + 0x00000030, /* Core 2, and Level B*/ + 0x000000C0, /* Core 3, and Level A*/ + 0x000000C0, /* Core 3, and Level B*/ + 0x0000ff00, /* Level C */ +}; + +unsigned int bank_partition[9] = { + 0x00000010, /* Core 0, and Level A*/ + 0x00000010, /* Core 0, and Level B*/ + 0x00000020, /* Core 1, and Level A*/ + 0x00000020, /* Core 1, and Level B*/ + 0x00000040, /* Core 2, and Level A*/ + 0x00000040, /* Core 2, and Level B*/ + 0x00000080, /* Core 3, and Level A*/ + 0x00000080, /* Core 3, and Level B*/ + 0x0000000c, /* Level C */ +}; + +unsigned int set_index[9] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0 +}; + +unsigned int bank_index[9] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0 +}; + +struct mutex void_lockdown_proc; + + +/* + * Every page list should contain a lock, a list, and a number recording how many pages it store + */ +struct color_group { + spinlock_t lock; + char _lock_name[LITMUS_LOCKDEP_NAME_MAX_LEN]; + struct list_head list; + atomic_t nr_pages; +}; + + +static struct color_group *color_groups; + +/* + * Naive function to count the number of 1's + */ +unsigned int counting_one_set(unsigned int v) +{ +// unsigned int v; // count the number of bits set in v + unsigned int c; // c accumulates the total bits set in v + + for (c = 0; v; v >>= 1) + { + c += v & 1; + } + return c; +} + +unsigned int two_exp(unsigned int e) +{ + unsigned int v = 1; + for (; e>0; e-- ) + { + v=v*2; + } + return v; +} + +unsigned int num_by_bitmask_index(unsigned int bitmask, unsigned int index) +{ + unsigned int pos = 0; + + while(true) + { + if(index ==0 && (bitmask & 1)==1) + { + break; + } + if(index !=0 && (bitmask & 1)==1){ + index--; + } + pos++; + bitmask = bitmask >>1; + + } + return pos; +} + + + +/* Decoding page color, 0~15 */ +static inline unsigned int page_color(struct page *page) +{ + return ((page_to_phys(page)& CACHE_MASK) >> CACHE_SHIFT); +} + +/* Decoding page bank number, 0~7 */ +static inline unsigned int page_bank(struct page *page) +{ + return ((page_to_phys(page)& BANK_MASK) >> BANK_SHIFT); +} + +static inline unsigned int page_list_index(struct page *page) +{ + unsigned int idx; + idx = (page_color(page) + page_bank(page)*(number_cachecolors)); +// printk("address = %lx, ", page_to_phys(page)); +// printk("color(%d), bank(%d), indx = %d\n", page_color(page), page_bank(page), idx); + + return idx; +} + + + +/* + * It is used to determine the smallest number of page lists. + */ +static unsigned long smallest_nr_pages(void) +{ + unsigned long i, min_pages; + struct color_group *cgroup; + cgroup = &color_groups[16*2]; + min_pages =atomic_read(&cgroup->nr_pages); + for (i = 16*2; i < NUM_PAGE_LIST; ++i) { + cgroup = &color_groups[i]; + if (atomic_read(&cgroup->nr_pages) < min_pages) + min_pages = atomic_read(&cgroup->nr_pages); + } + return min_pages; +} + +static void show_nr_pages(void) +{ + unsigned long i; + struct color_group *cgroup; + printk("show nr pages***************************************\n"); + for (i = 0; i < NUM_PAGE_LIST; ++i) { + cgroup = &color_groups[i]; + printk("(%03d) = %03d, ", i, atomic_read(&cgroup->nr_pages)); + if((i % 8) ==7){ + printk("\n"); + } + } +} + +/* + * Add a page to current pool. + */ +void add_page_to_color_list(struct page *page) +{ + const unsigned long color = page_list_index(page); + struct color_group *cgroup = &color_groups[color]; + BUG_ON(in_list(&page->lru) || PageLRU(page)); + BUG_ON(page_count(page) > 1); + spin_lock(&cgroup->lock); + list_add_tail(&page->lru, &cgroup->list); + atomic_inc(&cgroup->nr_pages); + SetPageLRU(page); + spin_unlock(&cgroup->lock); +} + +/* + * Replenish the page pool. + * If the newly allocate page is what we want, it will be pushed to the correct page list + * otherwise, it will be freed. + */ +static int do_add_pages(void) +{ + //printk("LITMUS do add pages\n"); + + struct page *page, *page_tmp; + LIST_HEAD(free_later); + unsigned long color; + int ret = 0; + int i = 0; + int free_counter = 0; + unsigned long counter[128]= {0}; + + //printk("Before refill : \n"); + //show_nr_pages(); + + // until all the page lists contain enough pages + //for (i =0; i<5; i++) { + for (i=0; i< 1024*100;i++) { + //while (smallest_nr_pages() < PAGES_PER_COLOR) { + // printk("smallest = %d\n", smallest_nr_pages()); + page = alloc_page(GFP_HIGHUSER_MOVABLE); + // page = alloc_pages_exact_node(0, GFP_HIGHUSER_MOVABLE, 0); + + if (unlikely(!page)) { + printk(KERN_WARNING "Could not allocate pages.\n"); + ret = -ENOMEM; + goto out; + } + color = page_list_index(page); + counter[color]++; + // printk("page(%d) = color %x, bank %x, [color] =%d \n", color, page_color(page), page_bank(page), atomic_read(&color_groups[color].nr_pages)); + //show_nr_pages(); + if (atomic_read(&color_groups[color].nr_pages) < PAGES_PER_COLOR && color>=32) { + //if ( PAGES_PER_COLOR && color>=16*2) { + add_page_to_color_list(page); + // printk("add page(%d) = color %x, bank %x\n", color, page_color(page), page_bank(page)); + } else{ + // Pages here will be freed later + list_add_tail(&page->lru, &free_later); + free_counter++; + //list_del(&page->lru); + // __free_page(page); + // printk("useless page(%d) = color %x, bank %x\n", color, page_color(page), page_bank(page)); + } + //show_nr_pages(); + /* + if(free_counter >= PAGES_PER_COLOR) + { + printk("free unwanted page list eariler"); + free_counter = 0; + list_for_each_entry_safe(page, page_tmp, &free_later, lru) { + list_del(&page->lru); + __free_page(page); + } + + show_nr_pages(); + } + */ + } +/* printk("page counter = \n"); + for (i=0; i<128; i++) + { + printk("(%03d) = %4d, ", i , counter[i]); + if(i%8 == 7){ + printk("\n"); + } + + } +*/ + //printk("After refill : \n"); + //show_nr_pages(); +#if 1 + // Free the unwanted pages + list_for_each_entry_safe(page, page_tmp, &free_later, lru) { + list_del(&page->lru); + __free_page(page); + } +#endif +out: + return ret; +} + +/* + * Provide pages for replacement according cache color + * This should be the only implementation here + * This function should not be accessed by others directly. + * + */ +static struct page *new_alloc_page_color( unsigned long color) +{ +// printk("allocate new page color = %d\n", color); + struct color_group *cgroup; + struct page *rPage = NULL; + + if( (color <0) || (color)>(number_cachecolors*number_banks -1)) { + TRACE_CUR("Wrong color %lu\n", color); +// printk(KERN_WARNING "Wrong color %lu\n", color); + goto out; + } + + + cgroup = &color_groups[color]; + spin_lock(&cgroup->lock); + if (unlikely(!atomic_read(&cgroup->nr_pages))) { + TRACE_CUR("No free %lu colored pages.\n", color); +// printk(KERN_WARNING "no free %lu colored pages.\n", color); + goto out_unlock; + } + rPage = list_first_entry(&cgroup->list, struct page, lru); + BUG_ON(page_count(rPage) > 1); + //get_page(rPage); + list_del(&rPage->lru); + atomic_dec(&cgroup->nr_pages); + ClearPageLRU(rPage); +out_unlock: + spin_unlock(&cgroup->lock); +out: + if( smallest_nr_pages() == 0) + { + do_add_pages(); + // printk("ERROR(bank_proc.c) = We don't have enough pages in bank_proc.c\n"); + + } + return rPage; +} + +struct page* get_colored_page(unsigned long color) +{ + return new_alloc_page_color(color); +} + +/* + * provide pages for replacement according to + * node = 0 for Level A tasks in Cpu 0 + * node = 1 for Level B tasks in Cpu 0 + * node = 2 for Level A tasks in Cpu 1 + * node = 3 for Level B tasks in Cpu 1 + * node = 4 for Level A tasks in Cpu 2 + * node = 5 for Level B tasks in Cpu 2 + * node = 6 for Level A tasks in Cpu 3 + * node = 7 for Level B tasks in Cpu 3 + * node = 8 for Level C tasks + */ +struct page *new_alloc_page(struct page *page, unsigned long node, int **x) +{ +// printk("allocate new page node = %d\n", node); +// return alloc_pages_exact_node(node, GFP_HIGHUSER_MOVABLE, 0); + struct color_group *cgroup; + struct page *rPage = NULL; + unsigned int color; + + + unsigned int idx = 0; + idx += num_by_bitmask_index(set_partition[node], set_index[node]); + idx += number_cachecolors* num_by_bitmask_index(bank_partition[node], bank_index[node]); + //printk("node = %d, idx = %d\n", node, idx); + + rPage = new_alloc_page_color(idx); + + + set_index[node] = (set_index[node]+1) % counting_one_set(set_partition[node]); + bank_index[node] = (bank_index[node]+1) % counting_one_set(bank_partition[node]); + return rPage; +} + + +/* + * Reclaim pages. + */ +void reclaim_page(struct page *page) +{ + const unsigned long color = page_list_index(page); + unsigned long nr_reclaimed = 0; + spin_lock(&reclaim_lock); + put_page(page); + add_page_to_color_list(page); + + spin_unlock(&reclaim_lock); + printk("Reclaimed page(%d) = color %x, bank %x, [color] =%d \n", color, page_color(page), page_bank(page), atomic_read(&color_groups[color].nr_pages)); +} + + +/* + * Initialize the numbers of banks and cache colors + */ +static int __init init_variables(void) +{ + number_banks = counting_one_set(BANK_MASK); + number_banks = two_exp(number_banks); + + number_cachecolors = counting_one_set(CACHE_MASK); + number_cachecolors = two_exp(number_cachecolors); + NUM_PAGE_LIST = number_banks * number_cachecolors; + printk(KERN_WARNING "number of banks = %d, number of cachecolors=%d\n", number_banks, number_cachecolors); + mutex_init(&void_lockdown_proc); + spin_lock_init(&reclaim_lock); + +} + + +/* + * Initialize the page pool + */ +static int __init init_color_groups(void) +{ + struct color_group *cgroup; + unsigned long i; + int err = 0; + + printk("NUM_PAGE_LIST = %d\n", NUM_PAGE_LIST); + color_groups = kmalloc(NUM_PAGE_LIST *sizeof(struct color_group), GFP_KERNEL); + + if (!color_groups) { + printk(KERN_WARNING "Could not allocate color groups.\n"); + err = -ENOMEM; + }else{ + + for (i = 0; i < NUM_PAGE_LIST; ++i) { + cgroup = &color_groups[i]; + atomic_set(&cgroup->nr_pages, 0); + INIT_LIST_HEAD(&cgroup->list); + spin_lock_init(&cgroup->lock); + } + } + return err; +} + +int set_partition_handler(struct ctl_table *table, int write, void __user *buffer, + size_t *lenp, loff_t *ppos) +{ + int ret = 0, i = 0; + mutex_lock(&void_lockdown_proc); + ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos); + if (ret) + goto out; + if (write) { + printk("New set Partition : \n"); + for(i =0;i <9;i++) + { + set_index[i] = 0; + printk("set[%d] = %x \n", i, set_partition[i]); + } + } +out: + mutex_unlock(&void_lockdown_proc); + return ret; +} + +int bank_partition_handler(struct ctl_table *table, int write, void __user *buffer, + size_t *lenp, loff_t *ppos) +{ + int ret = 0, i = 0; + mutex_lock(&void_lockdown_proc); + ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos); + if (ret) + goto out; + if (write) { + for(i =0;i <9;i++) + { + bank_index[i] = 0; + } + } +out: + mutex_unlock(&void_lockdown_proc); + return ret; +} + +int show_page_pool_handler(struct ctl_table *table, int write, void __user *buffer, + size_t *lenp, loff_t *ppos) +{ + int ret = 0, i = 0; + mutex_lock(&void_lockdown_proc); + ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos); + if (ret) + goto out; + if (write) { + show_nr_pages(); + } +out: + mutex_unlock(&void_lockdown_proc); + return ret; +} + +int refill_page_pool_handler(struct ctl_table *table, int write, void __user *buffer, + size_t *lenp, loff_t *ppos) +{ + int ret = 0, i = 0; + mutex_lock(&void_lockdown_proc); + ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos); + if (ret) + goto out; + if (write) { + do_add_pages(); + } +out: + mutex_unlock(&void_lockdown_proc); + return ret; +} + +static struct ctl_table cache_table[] = +{ + + { + .procname = "C0_LA_set", + .mode = 0666, + .proc_handler = set_partition_handler, + .data = &set_partition[0], + .maxlen = sizeof(set_partition[0]), + .extra1 = &set_partition_min, + .extra2 = &set_partition_max, + }, + { + .procname = "C0_LB_set", + .mode = 0666, + .proc_handler = set_partition_handler, + .data = &set_partition[1], + .maxlen = sizeof(set_partition[1]), + .extra1 = &set_partition_min, + .extra2 = &set_partition_max, + }, + { + .procname = "C1_LA_set", + .mode = 0666, + .proc_handler = set_partition_handler, + .data = &set_partition[2], + .maxlen = sizeof(set_partition[2]), + .extra1 = &set_partition_min, + .extra2 = &set_partition_max, + }, + { + .procname = "C1_LB_set", + .mode = 0666, + .proc_handler = set_partition_handler, + .data = &set_partition[3], + .maxlen = sizeof(set_partition[3]), + .extra1 = &set_partition_min, + .extra2 = &set_partition_max, + }, + { + .procname = "C2_LA_set", + .mode = 0666, + .proc_handler = set_partition_handler, + .data = &set_partition[4], + .maxlen = sizeof(set_partition[4]), + .extra1 = &set_partition_min, + .extra2 = &set_partition_max, + }, + { + .procname = "C2_LB_set", + .mode = 0666, + .proc_handler = set_partition_handler, + .data = &set_partition[5], + .maxlen = sizeof(set_partition[5]), + .extra1 = &set_partition_min, + .extra2 = &set_partition_max, + }, + { + .procname = "C3_LA_set", + .mode = 0666, + .proc_handler = set_partition_handler, + .data = &set_partition[6], + .maxlen = sizeof(set_partition[6]), + .extra1 = &set_partition_min, + .extra2 = &set_partition_max, + }, + { + .procname = "C3_LB_set", + .mode = 0666, + .proc_handler = set_partition_handler, + .data = &set_partition[7], + .maxlen = sizeof(set_partition[7]), + .extra1 = &set_partition_min, + .extra2 = &set_partition_max, + }, + { + .procname = "Call_LC_set", + .mode = 0666, + .proc_handler = set_partition_handler, + .data = &set_partition[8], + .maxlen = sizeof(set_partition[8]), + .extra1 = &set_partition_min, + .extra2 = &set_partition_max, + }, + { + .procname = "C0_LA_bank", + .mode = 0666, + .proc_handler = bank_partition_handler, + .data = &bank_partition[0], + .maxlen = sizeof(set_partition[0]), + .extra1 = &bank_partition_min, + .extra2 = &bank_partition_max, + }, + { + .procname = "C0_LB_bank", + .mode = 0666, + .proc_handler = bank_partition_handler, + .data = &bank_partition[1], + .maxlen = sizeof(set_partition[1]), + .extra1 = &bank_partition_min, + .extra2 = &bank_partition_max, + }, + { + .procname = "C1_LA_bank", + .mode = 0666, + .proc_handler = bank_partition_handler, + .data = &bank_partition[2], + .maxlen = sizeof(set_partition[2]), + .extra1 = &bank_partition_min, + .extra2 = &bank_partition_max, + }, + { + .procname = "C1_LB_bank", + .mode = 0666, + .proc_handler = bank_partition_handler, + .data = &bank_partition[3], + .maxlen = sizeof(set_partition[3]), + .extra1 = &bank_partition_min, + .extra2 = &bank_partition_max, + }, + { + .procname = "C2_LA_bank", + .mode = 0666, + .proc_handler = bank_partition_handler, + .data = &bank_partition[4], + .maxlen = sizeof(set_partition[4]), + .extra1 = &bank_partition_min, + .extra2 = &bank_partition_max, + }, + { + .procname = "C2_LB_bank", + .mode = 0666, + .proc_handler = bank_partition_handler, + .data = &bank_partition[5], + .maxlen = sizeof(set_partition[5]), + .extra1 = &bank_partition_min, + .extra2 = &bank_partition_max, + }, + { + .procname = "C3_LA_bank", + .mode = 0666, + .proc_handler = bank_partition_handler, + .data = &bank_partition[6], + .maxlen = sizeof(set_partition[6]), + .extra1 = &bank_partition_min, + .extra2 = &bank_partition_max, + }, + { + .procname = "C3_LB_bank", + .mode = 0666, + .proc_handler = bank_partition_handler, + .data = &bank_partition[7], + .maxlen = sizeof(set_partition[7]), + .extra1 = &bank_partition_min, + .extra2 = &bank_partition_max, + }, + { + .procname = "Call_LC_bank", + .mode = 0666, + .proc_handler = bank_partition_handler, + .data = &bank_partition[8], + .maxlen = sizeof(set_partition[8]), + .extra1 = &bank_partition_min, + .extra2 = &bank_partition_max, + }, + { + .procname = "show_page_pool", + .mode = 0666, + .proc_handler = show_page_pool_handler, + .data = &show_page_pool, + .maxlen = sizeof(show_page_pool), + }, { + .procname = "refill_page_pool", + .mode = 0666, + .proc_handler = refill_page_pool_handler, + .data = &refill_page_pool, + .maxlen = sizeof(refill_page_pool), + }, + { } +}; + +static struct ctl_table litmus_dir_table[] = { + { + .procname = "litmus", + .mode = 0555, + .child = cache_table, + }, + { } +}; + + +static struct ctl_table_header *litmus_sysctls; + + +/* + * Initialzie this proc + */ +static int __init litmus_color_init(void) +{ + int err=0; + printk("Init bankproc.c\n"); + + init_variables(); + + printk(KERN_INFO "Registering LITMUS^RT proc color sysctl.\n"); + + litmus_sysctls = register_sysctl_table(litmus_dir_table); + if (!litmus_sysctls) { + printk(KERN_WARNING "Could not register LITMUS^RT color sysctl.\n"); + err = -EFAULT; + goto out; + } + + init_color_groups(); + do_add_pages(); + + printk(KERN_INFO "Registering LITMUS^RT color and bank proc.\n"); +out: + return err; +} + +module_init(litmus_color_init); + diff --git a/litmus/cache_proc.c b/litmus/cache_proc.c index f5879f32232a..85d86c02d6e9 100644 --- a/litmus/cache_proc.c +++ b/litmus/cache_proc.c @@ -11,6 +11,7 @@ #include #include #include +#include #include #include @@ -144,6 +145,8 @@ static int l1_prefetch_proc; static int l2_prefetch_hint_proc; static int l2_double_linefill_proc; static int l2_data_prefetch_proc; +static int os_isolation; +static int use_part; u32 lockdown_reg[9] = { 0x00000000, @@ -168,6 +171,7 @@ int lock_all; int nr_lockregs; static raw_spinlock_t cache_lock; static raw_spinlock_t prefetch_lock; +static void ***flusher_pages = NULL; extern void l2c310_flush_all(void); @@ -379,6 +383,79 @@ void cache_lockdown(u32 lock_val, int cpu) //raw_spin_unlock_irqrestore(&cache_lock, flags); } +void do_partition(enum crit_level lv, int cpu) +{ + u32 regs; + unsigned long flags; + + if (lock_all || !use_part) + return; + raw_spin_lock_irqsave(&cache_lock, flags); + switch(lv) { + case CRIT_LEVEL_A: + regs = ~way_partitions[cpu*2]; + regs &= 0x0000ffff; + break; + case CRIT_LEVEL_B: + regs = ~way_partitions[cpu*2+1]; + regs &= 0x0000ffff; + break; + case CRIT_LEVEL_C: + case NUM_CRIT_LEVELS: + regs = ~way_partitions[8]; + regs &= 0x0000ffff; + break; + default: + BUG(); + + } + barrier(); + cache_lockdown(regs, cpu); + barrier(); + + raw_spin_unlock_irqrestore(&cache_lock, flags); + + flush_cache(0); +} + +int use_part_proc_handler(struct ctl_table *table, int write, void __user *buffer, + size_t *lenp, loff_t *ppos) +{ + int ret = 0; + + mutex_lock(&lockdown_proc); + + ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos); + if (ret) + goto out; + + + printk("USE_PART HANDLER = %d\n", use_part); + +out: + mutex_unlock(&lockdown_proc); + return ret; +} + +int os_isolation_proc_handler(struct ctl_table *table, int write, void __user *buffer, + size_t *lenp, loff_t *ppos) +{ + int ret = 0; + + mutex_lock(&lockdown_proc); + + ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos); + if (ret) + goto out; + + + printk("OS_ISOLATION HANDLER = %d\n", os_isolation); + +out: + mutex_unlock(&lockdown_proc); + return ret; +} + int lockdown_reg_handler(struct ctl_table *table, int write, void __user *buffer, size_t *lenp, loff_t *ppos) { @@ -429,6 +506,30 @@ out: return ret; } +void inline enter_irq_mode(void) +{ + int cpu = smp_processor_id(); + + if (os_isolation == 0) + return; + + prev_lockdown_i_reg[cpu] = readl_relaxed(ld_i_reg(cpu)); + prev_lockdown_d_reg[cpu] = readl_relaxed(ld_d_reg(cpu)); + + writel_relaxed(way_partitions[8], ld_i_reg(cpu)); + writel_relaxed(way_partitions[8], ld_d_reg(cpu)); +} + +void inline exit_irq_mode(void) +{ + int cpu = smp_processor_id(); + + if (os_isolation == 0) + return; + writel_relaxed(prev_lockdown_i_reg[cpu], ld_i_reg(cpu)); + writel_relaxed(prev_lockdown_d_reg[cpu], ld_d_reg(cpu)); +} + /* Operate on the Cortex-A9's ACTLR register */ #define ACTLR_L2_PREFETCH_HINT (1 << 1) #define ACTLR_L1_PREFETCH (1 << 2) @@ -683,6 +784,20 @@ static struct ctl_table cache_table[] = .data = &l2_data_prefetch_proc, .maxlen = sizeof(l2_data_prefetch_proc), }, + { + .procname = "os_isolation", + .mode = 0644, + .proc_handler = os_isolation_proc_handler, + .data = &os_isolation, + .maxlen = sizeof(os_isolation), + }, + { + .procname = "use_part", + .mode = 0644, + .proc_handler = use_part_proc_handler, + .data = &use_part, + .maxlen = sizeof(use_part), + }, { .procname = "do_perf_test", .mode = 0644, @@ -838,8 +953,146 @@ extern void v7_flush_kern_cache_all(void); */ void color_flush_page(void *vaddr, size_t size) { - //v7_flush_kern_dcache_area(vaddr, size); - v7_flush_kern_cache_all(); + v7_flush_kern_dcache_area(vaddr, size); + //v7_flush_kern_cache_all(); +} + +extern struct page* get_colored_page(unsigned long color); + +int setup_flusher_array(void) +{ + int color, way, ret = 0; + struct page *page; + + if (flusher_pages != NULL) + goto out; + + flusher_pages = (void***) kmalloc(MAX_NR_WAYS + * sizeof(*flusher_pages), GFP_KERNEL); + if (!flusher_pages) { + printk(KERN_WARNING "No memory for flusher array!\n"); + ret = -EINVAL; + goto out; + } + + for (way = 0; way < MAX_NR_WAYS; way++) { + void **flusher_color_arr; + flusher_color_arr = (void**) kmalloc(sizeof(**flusher_pages) + * MAX_NR_COLORS, GFP_KERNEL); + if (!flusher_color_arr) { + printk(KERN_WARNING "No memory for flusher array!\n"); + ret = -ENOMEM; + goto out_free; + } + + flusher_pages[way] = flusher_color_arr; + + for (color = 0; color < MAX_NR_COLORS; color++) { + int node; + switch (color) { + case 0: + node = 32; + break; + case 1: + node = 33; + break; + case 2: + node = 50; + break; + case 3: + node = 51; + break; + case 4: + node = 68; + break; + case 5: + node = 69; + break; + case 6: + node = 86; + break; + case 7: + node = 87; + break; + case 8: + node = 88; + break; + case 9: + node = 105; + break; + case 10: + node = 106; + break; + case 11: + node = 107; + break; + case 12: + node = 108; + break; + case 13: + node = 125; + break; + case 14: + node = 126; + break; + case 15: + node = 127; + break; + } + page = get_colored_page(node); + if (!page) { + printk(KERN_WARNING "no more colored pages\n"); + ret = -EINVAL; + goto out_free; + } + flusher_pages[way][color] = page_address(page); + if (!flusher_pages[way][color]) { + printk(KERN_WARNING "bad page address\n"); + ret = -EINVAL; + goto out_free; + } + } + } +out: + return ret; +out_free: + for (way = 0; way < MAX_NR_WAYS; way++) { + for (color = 0; color < MAX_NR_COLORS; color++) { + /* not bothering to try and give back colored pages */ + } + kfree(flusher_pages[way]); + } + kfree(flusher_pages); + flusher_pages = NULL; + return ret; +} + +void flush_cache(int all) +{ + int way, color, cpu; + unsigned long flags; + + raw_spin_lock_irqsave(&cache_lock, flags); + cpu = raw_smp_processor_id(); + + prev_lbm_i_reg[cpu] = readl_relaxed(ld_i_reg(cpu)); + prev_lbm_d_reg[cpu] = readl_relaxed(ld_d_reg(cpu)); + for (way=0;way +#include +#include +#include +#include + +#include +#include +#include + +#include + +long mc2_task_client_init(struct task_client *tc, struct mc2_task *mc2_param, struct task_struct *tsk, struct reservation *res) +{ + task_client_init(tc, tsk, res); + if ((mc2_param->crit < CRIT_LEVEL_A) || + (mc2_param->crit > CRIT_LEVEL_C)) + return -EINVAL; + + TRACE_TASK(tsk, "mc2_task_client_init: crit_level = %d\n", mc2_param->crit); + + return 0; +} + +asmlinkage long sys_set_mc2_task_param(pid_t pid, struct mc2_task __user * param) +{ + struct task_struct *target; + int retval = -EINVAL; + struct mc2_task *mp = kzalloc(sizeof(*mp), GFP_KERNEL); + + if (!mp) + return -ENOMEM; + + printk("Setting up mc^2 task parameters for process %d.\n", pid); + + if (pid < 0 || param == 0) { + goto out; + } + if (copy_from_user(mp, param, sizeof(*mp))) { + retval = -EFAULT; + goto out; + } + + /* Task search and manipulation must be protected */ + read_lock_irq(&tasklist_lock); + if (!(target = find_task_by_vpid(pid))) { + retval = -ESRCH; + goto out_unlock; + } + + if (is_realtime(target)) { + /* The task is already a real-time task. + * We cannot not allow parameter changes at this point. + */ + retval = -EBUSY; + goto out_unlock; + } + if (mp->crit < CRIT_LEVEL_A || mp->crit >= NUM_CRIT_LEVELS) { + printk(KERN_INFO "litmus: real-time task %d rejected " + "because of invalid criticality level\n", pid); + goto out_unlock; + } + + //target->rt_param.plugin_state = mp; + target->rt_param.mc2_data = mp; + + retval = 0; +out_unlock: + read_unlock_irq(&tasklist_lock); +out: + return retval; +} \ No newline at end of file diff --git a/litmus/polling_reservations.c b/litmus/polling_reservations.c new file mode 100644 index 000000000000..4a2fee575127 --- /dev/null +++ b/litmus/polling_reservations.c @@ -0,0 +1,564 @@ +#include + +#include +#include +#include + + +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. */ + if (res->env->time_zero == 0) { + tmp = res->env->current_time - res->env->time_zero; + instances = div64_u64(tmp, pres->period); + res->next_replenishment = + (instances + 1) * pres->period + pres->offset; + } + else { + tmp = res->env->current_time - res->env->time_zero; + instances = div64_u64(tmp, pres->period); + res->next_replenishment = res->env->time_zero + instances * pres->period; + } + + TRACE("ENV_TIME_ZERO %llu\n", res->env->time_zero); + TRACE("pol-res: R%d activate tmp=%llu instances=%llu period=%llu nextrp=%llu cur=%llu\n", + res->id, 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->blocked_by_ghost = 0; + 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); + res->cur_budget ? + RESERVATION_ACTIVE_IDLE : + RESERVATION_DEPLETED); +// did_signal_job_completion ? +// RESERVATION_DEPLETED : +// 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; + + TRACE("polling_replenish(%u): next_replenishment=%llu\n", res->id, res->next_replenishment); + 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 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(); + TRACE("!!!!!!!!!!!!!!!STATE ERROR R%d STATE(%d)\n", res->id, res->state); + 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 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; + TRACE_TASK(current, "polling_reservation_init: periodic %d, use_edf %d\n", use_periodic_polling, use_edf_prio); + if (use_periodic_polling) { + if (use_edf_prio) + pres->res.ops = &periodic_polling_ops_edf; + else + pres->res.ops = &periodic_polling_ops_fp; + } else { + if (use_edf_prio) + pres->res.ops = &sporadic_polling_ops_edf; + else + pres->res.ops = &sporadic_polling_ops_fp; + } +} + + +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 */ + //TRACE("TD_DRAIN STATE(%d) [%llu,%llu] %llu ?\n", res->state, tdres->cur_interval.start, tdres->cur_interval.end, res->env->current_time); + //BUG_ON(tdres->cur_interval.start > res->env->current_time); + if (tdres->cur_interval.start > res->env->current_time) + TRACE("TD_DRAIN BUG!!!!!!!!!!\n"); + + switch (res->state) { + case RESERVATION_DEPLETED: + case RESERVATION_INACTIVE: + //BUG(); + TRACE("TD_DRAIN!!!!!!!!! RES_STATE = %d\n", res->state); + 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); + if (res->env->current_time >= tdres->cur_interval.end) + printk(KERN_ALERT "TD_DRAIN_BUDGET WARNING1\n"); + if (res->env->current_time < tdres->cur_interval.start) + printk(KERN_ALERT "TD_DRAIN_BUDGET WARNING2\n"); + } + + 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->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; +} diff --git a/litmus/reservation.c b/litmus/reservation.c new file mode 100644 index 000000000000..07e38cb7d138 --- /dev/null +++ b/litmus/reservation.c @@ -0,0 +1,709 @@ +#include +#include + +#include +#include + +//#define TRACE(fmt, args...) do {} while (false) +//#define TRACE_TASK(fmt, args...) do {} while (false) + +#define BUDGET_ENFORCEMENT_AT_C 0 + +void reservation_init(struct reservation *res) +{ + memset(res, sizeof(*res), 0); + res->state = RESERVATION_INACTIVE; + INIT_LIST_HEAD(&res->clients); +} + +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)) { + return tsk; + } + } + return NULL; +} + +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, sizeof(tc->client), 0); + 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) +{ + //TRACE("SCHEDULER_UPDATE_AT update: %llu > when %llu\n", sup_env->next_scheduler_update, when); + if (sup_env->next_scheduler_update > when) + sup_env->next_scheduler_update = when; +} + +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; + + list_for_each(pos, &sup_env->depleted_reservations) { + queued = list_entry(pos, struct reservation, list); + if (queued->next_replenishment > res->next_replenishment) { + list_add(&res->list, pos->prev); + return passed_earlier; + } else + passed_earlier = 1; + } + + list_add_tail(&res->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; + + 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; + } + + 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 { + /* Active means this 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; + 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->active_reservations, list) { + if (res->id == id) + return res; + } + list_for_each_entry(res, &sup_env->inactive_reservations, list) { + if (res->id == id) + return res; + } + list_for_each_entry(res, &sup_env->depleted_reservations, list) { + if (res->id == id) + return res; + } + + return NULL; +} + +static void sup_charge_budget( + struct sup_reservation_environment* sup_env, + lt_t delta) +{ + struct list_head *pos, *next; + struct reservation *res; + + int encountered_active = 0; + + list_for_each_safe(pos, next, &sup_env->active_reservations) { + /* charge all ACTIVE_IDLE up to the first ACTIVE reservation */ + res = list_entry(pos, struct reservation, list); + if (res->state == RESERVATION_ACTIVE) { + TRACE("sup_charge_budget ACTIVE R%u drain %llu\n", res->id, delta); + if (encountered_active == 0 && res->blocked_by_ghost == 0) { + TRACE("DRAIN !!\n"); + res->ops->drain_budget(res, delta); + encountered_active = 1; + } + } else { + //BUG_ON(res->state != RESERVATION_ACTIVE_IDLE); + TRACE("sup_charge_budget INACTIVE R%u drain %llu\n", res->id, delta); + res->ops->drain_budget(res, delta); + } + if (res->state == RESERVATION_ACTIVE || + res->state == RESERVATION_ACTIVE_IDLE) + { + /* 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); + } + //if (encountered_active == 2) + /* stop at the first ACTIVE reservation */ + // break; + } + //TRACE("finished charging budgets\n"); +} + +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, list); + if (res->next_replenishment <= sup_env->env.current_time) { + res->ops->replenish(res); + } else { + /* list is ordered by increasing depletion times */ + break; + } + } + //TRACE("finished replenishing budgets\n"); + + /* request a scheduler update at the next replenishment instant */ + res = list_first_entry_or_null(&sup_env->depleted_reservations, + struct reservation, 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. */ + //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 */ + //TRACE("CHARGE###\n"); + sup_charge_budget(sup_env, delta); + + /* check if any budgets where replenished */ + //TRACE("REPLENISH###\n"); + 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); + + 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); +} + +void sup_init(struct sup_reservation_environment* sup_env) +{ + memset(sup_env, sizeof(*sup_env), 0); + + 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->next_scheduler_update = SUP_NO_SCHEDULER_UPDATE; +} + +struct reservation* gmp_find_by_id(struct gmp_reservation_environment* gmp_env, + unsigned int id) +{ + struct reservation *res; + + list_for_each_entry(res, &gmp_env->active_reservations, list) { + if (res->id == id) + return res; + } + list_for_each_entry(res, &gmp_env->inactive_reservations, list) { + if (res->id == id) + return res; + } + list_for_each_entry(res, &gmp_env->depleted_reservations, list) { + if (res->id == id) + return res; + } + + return NULL; +} + + +struct next_timer_event* gmp_find_event_by_id(struct gmp_reservation_environment* gmp_env, + unsigned int id) +{ + struct next_timer_event *event; + + list_for_each_entry(event, &gmp_env->next_events, list) { + if (event->id == id) + return event; + } + + return NULL; +} + + +struct next_timer_event* gmp_find_event_by_time(struct gmp_reservation_environment* gmp_env, + lt_t when) +{ + struct next_timer_event *event; + + list_for_each_entry(event, &gmp_env->next_events, list) { + if (event->next_update == when) + return event; + } + + return NULL; +} + +#define TIMER_RESOLUTION 100000L + +static void gmp_add_event( + struct gmp_reservation_environment* gmp_env, + lt_t when, unsigned int id, event_type_t type) +{ + struct next_timer_event *nevent, *queued; + struct list_head *pos; + int found = 0, update = 0; + + //when = div64_u64(when, TIMER_RESOLUTION); + //when *= TIMER_RESOLUTION; +//printk(KERN_ALERT "GMP_ADD id=%d type=%d when=%llu\n", id, type, when); + nevent = gmp_find_event_by_id(gmp_env, id); + + if (nevent) + TRACE("EVENT R%d update prev = %llu, new = %llu\n", nevent->id, nevent->next_update, when); + + if (nevent && nevent->next_update > when) { + list_del(&nevent->list); + update = 1; + + } + + if (!nevent || nevent->type != type || update == 1) { + if (update == 0) + nevent = kzalloc(sizeof(*nevent), GFP_ATOMIC); + BUG_ON(!nevent); + nevent->next_update = when; + nevent->id = id; + nevent->type = type; + nevent->timer_armed_on = NO_CPU; + + list_for_each(pos, &gmp_env->next_events) { + queued = list_entry(pos, struct next_timer_event, list); + if (queued->next_update > nevent->next_update) { + list_add(&nevent->list, pos->prev); + found = 1; + TRACE("NEXT_EVENT id=%d type=%d update=%llu ADDED at before %llu\n", nevent->id, nevent->type, nevent->next_update, queued->next_update); + break; + } + } + + if (!found) { + list_add_tail(&nevent->list, &gmp_env->next_events); + TRACE("NEXT_EVENT id=%d type=%d update=%llu ADDED at TAIL\n", nevent->id, nevent->type, nevent->next_update); + } + } else { + //TRACE("EVENT FOUND id = %d type=%d when=%llu, NEW EVENT type=%d when=%llu\n", nevent->id, nevent->type, nevent->next_update, type, when); +; //printk(KERN_ALERT "EVENT FOUND id = %d type=%d when=%llu, NEW EVENT type=%d when=%llu\n", nevent->id, nevent->type, nevent->next_update, type, when); + } + + TRACE("======START PRINTING EVENT LIST======\n"); + gmp_print_events(gmp_env, litmus_clock()); + TRACE("======FINISH PRINTING EVENT LIST======\n"); +} + +void gmp_add_event_after( + struct gmp_reservation_environment* gmp_env, lt_t timeout, unsigned int id, event_type_t type) +{ + //printk(KERN_ALERT "ADD_EVENT_AFTER id = %d\n", id); + gmp_add_event(gmp_env, gmp_env->env.current_time + timeout, id, type); +} + +static void gmp_queue_depleted( + struct gmp_reservation_environment* gmp_env, + struct reservation *res) +{ + struct list_head *pos; + struct reservation *queued; + int found = 0; + +//printk(KERN_ALERT "R%d request to enqueue depleted_list\n", res->id); + + list_for_each(pos, &gmp_env->depleted_reservations) { + queued = list_entry(pos, struct reservation, list); + if (queued && (queued->next_replenishment > res->next_replenishment)) { +//printk(KERN_ALERT "QUEUED R%d %llu\n", queued->id, queued->next_replenishment); + list_add(&res->list, pos->prev); + found = 1; + break; + } + } + + if (!found) + list_add_tail(&res->list, &gmp_env->depleted_reservations); + + TRACE("R%d queued to depleted_list\n", res->id); +//printk(KERN_ALERT "R%d queued to depleted_list\n", res->id); + gmp_add_event(gmp_env, res->next_replenishment, res->id, EVENT_REPLENISH); +} + +static void gmp_queue_active( + struct gmp_reservation_environment* gmp_env, + struct reservation *res) +{ + struct list_head *pos; + struct reservation *queued; + int check_preempt = 1, found = 0; + + list_for_each(pos, &gmp_env->active_reservations) { + queued = list_entry(pos, struct reservation, list); + if (queued->priority > res->priority) { + list_add(&res->list, pos->prev); + found = 1; + break; + } else if (queued->scheduled_on == NO_CPU) + check_preempt = 0; + } + + if (!found) + list_add_tail(&res->list, &gmp_env->active_reservations); + + /* check for possible preemption */ + if (res->state == RESERVATION_ACTIVE && check_preempt) + gmp_env->schedule_now++; + +#if BUDGET_ENFORCEMENT_AT_C + gmp_add_event_after(gmp_env, res->cur_budget, res->id, EVENT_DRAIN); +#endif + res->event_added = 1; +} + +static void gmp_queue_reservation( + struct gmp_reservation_environment* gmp_env, + struct reservation *res) +{ + +//printk(KERN_ALERT "DEBUG: Passed %s %d %p R%d STATE %d\n",__FUNCTION__,__LINE__, gmp_env, res->id, res->state); + switch (res->state) { + case RESERVATION_INACTIVE: + list_add(&res->list, &gmp_env->inactive_reservations); + break; + + case RESERVATION_DEPLETED: + gmp_queue_depleted(gmp_env, res); + break; + + case RESERVATION_ACTIVE_IDLE: + case RESERVATION_ACTIVE: + gmp_queue_active(gmp_env, res); + break; + } +} + +void gmp_add_new_reservation( + struct gmp_reservation_environment* gmp_env, + struct reservation* new_res) +{ + new_res->env = &gmp_env->env; + gmp_queue_reservation(gmp_env, new_res); +} + +#if BUDGET_ENFORCEMENT_AT_C +static void gmp_charge_budget( + struct gmp_reservation_environment* gmp_env, + lt_t delta) +{ + struct list_head *pos, *next; + struct reservation *res; + + list_for_each_safe(pos, next, &gmp_env->active_reservations) { + int drained = 0; + /* charge all ACTIVE_IDLE up to the first ACTIVE reservation */ + res = list_entry(pos, struct reservation, list); + if (res->state == RESERVATION_ACTIVE) { + TRACE("gmp_charge_budget ACTIVE R%u scheduled_on=%d drain %llu\n", res->id, res->scheduled_on, delta); + if (res->scheduled_on != NO_CPU && res->blocked_by_ghost == 0) { + TRACE("DRAIN !!\n"); + drained = 1; + res->ops->drain_budget(res, delta); + } else { + TRACE("NO DRAIN (not scheduled)!!\n"); + } + } else { + //BUG_ON(res->state != RESERVATION_ACTIVE_IDLE); + if (res->state != RESERVATION_ACTIVE_IDLE) + TRACE("BUG!!!!!!!!!!!! gmp_charge_budget()\n"); + TRACE("gmp_charge_budget INACTIVE R%u drain %llu\n", res->id, delta); + //if (res->is_ghost != NO_CPU) { + TRACE("DRAIN !!\n"); + drained = 1; + res->ops->drain_budget(res, delta); + //} + } + if ((res->state == RESERVATION_ACTIVE || + res->state == RESERVATION_ACTIVE_IDLE) && (drained == 1)) + { + /* make sure scheduler is invoked when this reservation expires + * its remaining budget */ + TRACE("requesting gmp_scheduler update for reservation %u in %llu nanoseconds\n", res->id, res->cur_budget); + gmp_add_event_after(gmp_env, res->cur_budget, res->id, EVENT_DRAIN); + res->event_added = 1; + } + //if (encountered_active == 2) + /* stop at the first ACTIVE reservation */ + // break; + } + //TRACE("finished charging budgets\n"); +} +#else + +static void gmp_charge_budget( + struct gmp_reservation_environment* gmp_env, + lt_t delta) +{ + return; +} + +#endif + +static void gmp_replenish_budgets(struct gmp_reservation_environment* gmp_env) +{ + struct list_head *pos, *next; + struct reservation *res; + + list_for_each_safe(pos, next, &gmp_env->depleted_reservations) { + res = list_entry(pos, struct reservation, list); + if (res->next_replenishment <= gmp_env->env.current_time) { + res->ops->replenish(res); + if (res->is_ghost != NO_CPU) { + TRACE("R%d replenished! scheduled_on=%d\n", res->id, res->scheduled_on); + } + } else { + /* list is ordered by increasing depletion times */ + break; + } + } + //TRACE("finished replenishing budgets\n"); +} + +#define EPSILON 50 + +/* return schedule_now */ +int gmp_update_time( + struct gmp_reservation_environment* gmp_env, + lt_t now) +{ + struct next_timer_event *event, *next; + lt_t delta, ret; + + /* 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. */ + //TRACE("(gmp_update_time) now: %llu, current_time: %llu\n", now, gmp_env->env.current_time); + if (unlikely(now <= gmp_env->env.current_time + EPSILON)) + return 0; + + delta = now - gmp_env->env.current_time; + gmp_env->env.current_time = now; + + + //gmp_print_events(gmp_env, now); + /* deplete budgets by passage of time */ + //TRACE("CHARGE###\n"); + gmp_charge_budget(gmp_env, delta); + + /* check if any budgets where replenished */ + //TRACE("REPLENISH###\n"); + gmp_replenish_budgets(gmp_env); + + + list_for_each_entry_safe(event, next, &gmp_env->next_events, list) { + if (event->next_update < now) { + list_del(&event->list); + //TRACE("EVENT at %llu IS DELETED\n", event->next_update); + kfree(event); + } else { + break; + } + } + + //gmp_print_events(gmp_env, litmus_clock()); + + ret = min(gmp_env->schedule_now, NR_CPUS); + gmp_env->schedule_now = 0; + + return ret; +} + +void gmp_print_events(struct gmp_reservation_environment* gmp_env, lt_t now) +{ + struct next_timer_event *event, *next; + + TRACE("GLOBAL EVENTS now=%llu\n", now); + list_for_each_entry_safe(event, next, &gmp_env->next_events, list) { + TRACE("at %llu type=%d id=%d armed_on=%d\n", event->next_update, event->type, event->id, event->timer_armed_on); + } +} + +static void gmp_res_change_state( + struct reservation_environment* env, + struct reservation *res, + reservation_state_t new_state) +{ + struct gmp_reservation_environment* gmp_env; + + gmp_env = container_of(env, struct gmp_reservation_environment, env); + + TRACE("GMP reservation R%d state %d->%d at %llu\n", + res->id, res->state, new_state, env->current_time); + + list_del(&res->list); + /* check if we need to reschedule because we lost an active reservation */ + if (res->state == RESERVATION_ACTIVE) + gmp_env->schedule_now++; + res->state = new_state; + gmp_queue_reservation(gmp_env, res); +} + +void gmp_init(struct gmp_reservation_environment* gmp_env) +{ + memset(gmp_env, sizeof(*gmp_env), 0); + + INIT_LIST_HEAD(&gmp_env->active_reservations); + INIT_LIST_HEAD(&gmp_env->depleted_reservations); + INIT_LIST_HEAD(&gmp_env->inactive_reservations); + INIT_LIST_HEAD(&gmp_env->next_events); + + gmp_env->env.change_state = gmp_res_change_state; + + gmp_env->schedule_now = 0; + gmp_env->will_schedule = false; + + raw_spin_lock_init(&gmp_env->lock); +} diff --git a/litmus/sched_mc2.c b/litmus/sched_mc2.c new file mode 100644 index 000000000000..0ff27135c825 --- /dev/null +++ b/litmus/sched_mc2.c @@ -0,0 +1,1849 @@ +/* + * litmus/sched_mc2.c + * + * Implementation of the Mixed-Criticality on MultiCore scheduler + * + * Thus plugin implements a scheduling algorithm proposed in + * "Mixed-Criticality Real-Time Scheduling for Multicore System" paper. + */ + +#include +#include +#include + +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +//#define TRACE(fmt, args...) do {} while (false) +//#define TRACE_TASK(fmt, args...) do {} while (false) + +#define BUDGET_ENFORCEMENT_AT_C 0 + +extern void do_partition(enum crit_level lv, int cpu); + +/* _global_env - reservation container for level-C tasks*/ +struct gmp_reservation_environment _global_env; + +/* cpu_entry - keep track of a running task on a cpu + * This state is used to decide the lowest priority cpu + */ +struct cpu_entry { + struct task_struct *scheduled; + lt_t deadline; + int cpu; + enum crit_level lv; + /* if will_schedule is true, this cpu is already selected and + call mc2_schedule() soon. */ + bool will_schedule; +}; + +/* cpu_priority - a global state for choosing the lowest priority CPU */ +struct cpu_priority { + raw_spinlock_t lock; + struct cpu_entry cpu_entries[NR_CPUS]; +}; + +struct cpu_priority _lowest_prio_cpu; + +/* mc2_task_state - a task state structure */ +struct mc2_task_state { + struct task_client res_info; + /* if cpu == -1, this task is a global task (level C) */ + int cpu; + bool has_departed; + struct mc2_task mc2_param; +}; + +/* crit_entry - maintain the logically running job (ghost job) */ +struct crit_entry { + enum crit_level level; + struct task_struct *running; +}; + +/* mc2_cpu_state - maintain the scheduled state and ghost jobs + * timer : timer for partitioned tasks (level A and B) + * g_timer : timer for global tasks (level C) + */ +struct mc2_cpu_state { + raw_spinlock_t lock; + + struct sup_reservation_environment sup_env; + struct hrtimer timer; + + int cpu; + struct task_struct* scheduled; + struct crit_entry crit_entries[NUM_CRIT_LEVELS]; +}; + +static int resched_cpu[NR_CPUS]; +static DEFINE_PER_CPU(struct mc2_cpu_state, mc2_cpu_state); + +#define cpu_state_for(cpu_id) (&per_cpu(mc2_cpu_state, cpu_id)) +#define local_cpu_state() (this_cpu_ptr(&mc2_cpu_state)) + +/* get_mc2_state - get the task's state */ +static struct mc2_task_state* get_mc2_state(struct task_struct *tsk) +{ + struct mc2_task_state* tinfo; + + tinfo = (struct mc2_task_state*)tsk_rt(tsk)->plugin_state; + + if (tinfo) + return tinfo; + else + return NULL; +} + +/* get_task_crit_level - return the criticaility level of a task */ +static enum crit_level get_task_crit_level(struct task_struct *tsk) +{ + struct mc2_task *mp; + + if (!tsk || !is_realtime(tsk)) + return NUM_CRIT_LEVELS; + + mp = tsk_rt(tsk)->mc2_data; + + if (!mp) + return NUM_CRIT_LEVELS; + else + return mp->crit; +} + +/* task_depart - remove a task from its reservation + * If the job has remaining budget, convert it to a ghost job + * and update crit_entries[] + * + * @job_complete indicate whether job completes or not + */ +static void task_departs(struct task_struct *tsk, int job_complete) +{ + struct mc2_task_state* tinfo = get_mc2_state(tsk); + //struct mc2_cpu_state* state = local_cpu_state(); + struct reservation* res = NULL; + struct reservation_client *client = NULL; + + BUG_ON(!is_realtime(tsk)); + + res = tinfo->res_info.client.reservation; + client = &tinfo->res_info.client; + BUG_ON(!res); + BUG_ON(!client); + +/* 9/18/2015 fix start - no ghost job handling, empty remaining budget */ + if (job_complete) { + res->cur_budget = 0; + sched_trace_task_completion(tsk, 0); + } +/* fix end */ + + res->ops->client_departs(res, client, job_complete); + tinfo->has_departed = true; + TRACE_TASK(tsk, "CLIENT DEPART with budget %llu\n", res->cur_budget); +/* 9/18/2015 fix start - no remaining budget + * + if (job_complete && res->cur_budget) { + struct crit_entry* ce; + enum crit_level lv = tinfo->mc2_param.crit; + + ce = &state->crit_entries[lv]; + ce->running = tsk; + res->is_ghost = state->cpu; +#if BUDGET_ENFORCEMENT_AT_C + gmp_add_event_after(&_global_env, res->cur_budget, res->id, EVENT_DRAIN); +#endif + TRACE_TASK(tsk, "BECOME GHOST at %llu\n", litmus_clock()); + } + * fix -end + */ + +} + +/* task_arrive - put a task into its reservation + * If the job was a ghost job, remove it from crit_entries[] + */ +static void task_arrives(struct mc2_cpu_state *state, struct task_struct *tsk) +{ + struct mc2_task_state* tinfo = get_mc2_state(tsk); + struct reservation* res; + struct reservation_client *client; + enum crit_level lv = get_task_crit_level(tsk); + + res = tinfo->res_info.client.reservation; + client = &tinfo->res_info.client; + + tinfo->has_departed = false; + + switch(lv) { + case CRIT_LEVEL_A: + case CRIT_LEVEL_B: + TS_RELEASE_START; + break; + case CRIT_LEVEL_C: + TS_RELEASE_C_START; + break; + default: + break; + } + + res->ops->client_arrives(res, client); + + if (lv != NUM_CRIT_LEVELS) { + struct crit_entry *ce; + ce = &state->crit_entries[lv]; + /* if the currrent task is a ghost job, remove it */ + if (ce->running == tsk) + ce->running = NULL; + } + /* do we need this?? + if (resched_cpu[state->cpu]) + litmus_reschedule(state->cpu); + */ + + switch(lv) { + case CRIT_LEVEL_A: + case CRIT_LEVEL_B: + TS_RELEASE_END; + break; + case CRIT_LEVEL_C: + TS_RELEASE_C_END; + break; + default: + break; + } +} + +/* get_lowest_prio_cpu - return the lowest priority cpu + * This will be used for scheduling level-C tasks. + * If all CPUs are running tasks which has + * higher priority than level C, return NO_CPU. + */ +static int get_lowest_prio_cpu(lt_t priority) +{ + struct cpu_entry *ce; + int cpu, ret = NO_CPU; + lt_t latest_deadline = 0; + + //raw_spin_lock(&_lowest_prio_cpu.lock); + ce = &_lowest_prio_cpu.cpu_entries[local_cpu_state()->cpu]; + if (!ce->will_schedule && !ce->scheduled) { + //raw_spin_unlock(&_lowest_prio_cpu.lock); + TRACE("CPU %d (local) is the lowest!\n", ce->cpu); + return ce->cpu; + } else { + TRACE("Local CPU will_schedule=%d, scheduled=(%s/%d)\n", ce->will_schedule, ce->scheduled ? (ce->scheduled)->comm : "null", ce->scheduled ? (ce->scheduled)->pid : 0); + } + + for_each_online_cpu(cpu) { + ce = &_lowest_prio_cpu.cpu_entries[cpu]; + /* If a CPU will call schedule() in the near future, we don't + return that CPU. */ + TRACE("CPU %d will_schedule=%d, scheduled=(%s/%d:%d)\n", cpu, ce->will_schedule, + ce->scheduled ? (ce->scheduled)->comm : "null", + ce->scheduled ? (ce->scheduled)->pid : 0, + ce->scheduled ? (ce->scheduled)->rt_param.job_params.job_no : 0); + if (!ce->will_schedule) { + if (!ce->scheduled) { + /* Idle cpu, return this. */ + //raw_spin_unlock(&_lowest_prio_cpu.lock); + TRACE("CPU %d is the lowest!\n", ce->cpu); + return ce->cpu; + } else if (ce->lv == CRIT_LEVEL_C && + ce->deadline > latest_deadline) { + latest_deadline = ce->deadline; + ret = ce->cpu; + } + } + } + + //raw_spin_unlock(&_lowest_prio_cpu.lock); + + if (priority >= latest_deadline) + ret = NO_CPU; + + TRACE("CPU %d is the lowest!\n", ret); + + return ret; +} + +/* mc2_update_time - update time for a given criticality level. + * caller must hold a proper lock + * (cpu_state lock or global lock) + */ +/* 9/24/2015 temporally not using +static void mc2_update_time(enum crit_level lv, + struct mc2_cpu_state *state, lt_t time) +{ + int global_schedule_now; + + if (lv < CRIT_LEVEL_C) + sup_update_time(&state->sup_env, time); + else if (lv == CRIT_LEVEL_C) { + global_schedule_now = gmp_update_time(&_global_env, time); + while (global_schedule_now--) { + int cpu = get_lowest_prio_cpu(0); + if (cpu != NO_CPU) { + raw_spin_lock(&_lowest_prio_cpu.lock); + _lowest_prio_cpu.cpu_entries[cpu].will_schedule = true; + raw_spin_unlock(&_lowest_prio_cpu.lock); + TRACE("LOWEST CPU = P%d\n", cpu); + litmus_reschedule(cpu); + } + } + } + else + TRACE("update_time(): Criticality level error!!!!\n"); +} +*/ + +/* NOTE: drops state->lock */ +/* mc2_update_timer_and_unlock - set a timer and g_timer and unlock + * Whenever res_env.current_time is updated, + * we check next_scheduler_update and set + * a timer. + * If there exist a global event which is + * not armed on any CPU and g_timer is not + * active, set a g_timer for that event. + */ +static void mc2_update_timer_and_unlock(struct mc2_cpu_state *state) +{ + int local, cpus; + lt_t update, now; + //enum crit_level lv = get_task_crit_level(state->scheduled); + struct next_timer_event *event, *next; + int reschedule[NR_CPUS]; + + for (cpus = 0; cpussup_env.next_scheduler_update; + now = state->sup_env.env.current_time; + + /* Be sure we're actually running on the right core, + * as pres_update_timer() is also called from pres_task_resume(), + * which might be called on any CPU when a thread resumes. + */ + local = local_cpu_state() == state; + + raw_spin_lock(&_global_env.lock); + + list_for_each_entry_safe(event, next, &_global_env.next_events, list) { + /* If the event time is already passed, we call schedule() on + the lowest priority cpu */ + if (event->next_update >= update) { + break; + } + + if (event->next_update < litmus_clock()) { + if (event->timer_armed_on == NO_CPU) { + struct reservation *res = gmp_find_by_id(&_global_env, event->id); + int cpu = get_lowest_prio_cpu(res?res->priority:0); + TRACE("GLOBAL EVENT PASSED!! poking CPU %d to reschedule\n", cpu); + list_del(&event->list); + kfree(event); + if (cpu != NO_CPU) { + //raw_spin_lock(&_lowest_prio_cpu.lock); + _lowest_prio_cpu.cpu_entries[cpu].will_schedule = true; + //raw_spin_unlock(&_lowest_prio_cpu.lock); + if (cpu == local_cpu_state()->cpu) + litmus_reschedule_local(); + else + reschedule[cpu] = 1; + } + } + } else if (event->next_update < update && (event->timer_armed_on == NO_CPU || event->timer_armed_on == state->cpu)) { + event->timer_armed_on = state->cpu; + update = event->next_update; + break; + } + } + + /* Must drop state lock before calling into hrtimer_start(), which + * may raise a softirq, which in turn may wake ksoftirqd. */ + raw_spin_unlock(&_global_env.lock); + raw_spin_unlock(&state->lock); + + if (update <= now || reschedule[state->cpu]) { + //litmus_reschedule(state->cpu); + raw_spin_lock(&state->lock); + preempt_if_preemptable(state->scheduled, state->cpu); + raw_spin_unlock(&state->lock); + reschedule[state->cpu] = 0; + } else if (likely(local && update != SUP_NO_SCHEDULER_UPDATE)) { + /* Reprogram only if not already set correctly. */ + if (!hrtimer_active(&state->timer) || + ktime_to_ns(hrtimer_get_expires(&state->timer)) != update) { + TRACE("canceling timer...at %llu\n", + ktime_to_ns(hrtimer_get_expires(&state->timer))); + hrtimer_cancel(&state->timer); + TRACE("setting scheduler timer for %llu\n", update); + /* We cannot use hrtimer_start() here because the + * wakeup flag must be set to zero. */ + __hrtimer_start_range_ns(&state->timer, + ns_to_ktime(update), + 0 /* timer coalescing slack */, + HRTIMER_MODE_ABS_PINNED, + 0 /* wakeup */); + } + } else if (unlikely(!local && update != SUP_NO_SCHEDULER_UPDATE)) { + /* Poke remote core only if timer needs to be set earlier than + * it is currently set. + */ + TRACE("mc2_update_timer for remote CPU %d (update=%llu, " + "active:%d, set:%llu)\n", + state->cpu, + update, + hrtimer_active(&state->timer), + ktime_to_ns(hrtimer_get_expires(&state->timer))); + if (!hrtimer_active(&state->timer) || + ktime_to_ns(hrtimer_get_expires(&state->timer)) > update) { + TRACE("poking CPU %d so that it can update its " + "scheduling timer (active:%d, set:%llu)\n", + state->cpu, + hrtimer_active(&state->timer), + ktime_to_ns(hrtimer_get_expires(&state->timer))); + //litmus_reschedule(state->cpu); + raw_spin_lock(&state->lock); + preempt_if_preemptable(state->scheduled, state->cpu); + raw_spin_unlock(&state->lock); + reschedule[state->cpu] = 0; + } + } + for (cpus = 0; cpuslock); + preempt_if_preemptable(remote_state->scheduled, remote_state->cpu); + raw_spin_unlock(&remote_state->lock); + } + } +} + +/* mc2_update_ghost_state - Update crit_entries[] to track ghost jobs + * If the budget of a ghost is exhausted, + * clear is_ghost and reschedule + */ +/* +static lt_t mc2_update_ghost_state(struct mc2_cpu_state *state) +{ + int lv = 0; + struct crit_entry* ce; + struct reservation *res; + struct mc2_task_state *tinfo; + lt_t ret = ULLONG_MAX; + + BUG_ON(!state); + + for (lv = 0; lv < NUM_CRIT_LEVELS; lv++) { + ce = &state->crit_entries[lv]; + if (ce->running != NULL) { +//printk(KERN_ALERT "P%d ce->running : %s/%d\n", state->cpu, ce->running ? (ce->running)->comm : "null", ce->running ? (ce->running)->pid : 0); + tinfo = get_mc2_state(ce->running); + if (!tinfo) + continue; + + res = res_find_by_id(state, tinfo->mc2_param.res_id); + //BUG_ON(!res); + if (!res) { + printk(KERN_ALERT "mc2_update_ghost_state(): R%d not found!\n", tinfo->mc2_param.res_id); + return 0; + } + + TRACE("LV %d running id %d budget %llu\n", + lv, tinfo->mc2_param.res_id, res->cur_budget); + // If the budget is exhausted, clear is_ghost and reschedule + if (!res->cur_budget) { + struct sup_reservation_environment* sup_env = &state->sup_env; + + TRACE("GHOST FINISH id %d at %llu\n", + tinfo->mc2_param.res_id, litmus_clock()); + ce->running = NULL; + res->is_ghost = NO_CPU; + + if (lv < CRIT_LEVEL_C) { + res = list_first_entry_or_null( + &sup_env->active_reservations, + struct reservation, list); + if (res) + litmus_reschedule_local(); + } else if (lv == CRIT_LEVEL_C) { + res = list_first_entry_or_null( + &_global_env.active_reservations, + struct reservation, list); + if (res) + litmus_reschedule(state->cpu); + } + } else { + //TRACE("GHOST NOT FINISH id %d budget %llu\n", res->id, res->cur_budget); + //gmp_add_event_after(&_global_env, res->cur_budget, res->id, EVENT_DRAIN); + if (ret > res->cur_budget) { + ret = res->cur_budget; + } + } + } + } + + return ret; +} +*/ + +/* update_cpu_prio - Update cpu's priority + * When a cpu picks a new task, call this function + * to update cpu priorities. + */ +static void update_cpu_prio(struct mc2_cpu_state *state) +{ + struct cpu_entry *ce = &_lowest_prio_cpu.cpu_entries[state->cpu]; + enum crit_level lv = get_task_crit_level(state->scheduled); + + if (!state->scheduled) { + /* cpu is idle. */ + ce->scheduled = NULL; + ce->deadline = ULLONG_MAX; + ce->lv = NUM_CRIT_LEVELS; + } else if (lv == CRIT_LEVEL_C) { + ce->scheduled = state->scheduled; + ce->deadline = get_deadline(state->scheduled); + ce->lv = lv; + } else if (lv < CRIT_LEVEL_C) { + /* If cpu is running level A or B tasks, it is not eligible + to run level-C tasks */ + ce->scheduled = state->scheduled; + ce->deadline = 0; + ce->lv = lv; + } +}; + +/* on_scheduling_timer - timer event for partitioned tasks + */ +static enum hrtimer_restart on_scheduling_timer(struct hrtimer *timer) +{ + unsigned long flags; + enum hrtimer_restart restart = HRTIMER_NORESTART; + struct mc2_cpu_state *state; + lt_t update, now; + int global_schedule_now; + //lt_t remain_budget; // no ghost jobs + int reschedule[NR_CPUS]; + int cpus; + + for (cpus = 0; cpuscpu != raw_smp_processor_id()); + + TS_ISR_START; + + TRACE("Timer fired at %llu\n", litmus_clock()); + //raw_spin_lock_irqsave(&_global_env.lock, flags); + raw_spin_lock_irqsave(&state->lock, flags); + now = litmus_clock(); + sup_update_time(&state->sup_env, now); + +/* 9/20/2015 fix - no ghost job + remain_budget = mc2_update_ghost_state(state); +*/ + update = state->sup_env.next_scheduler_update; + now = state->sup_env.env.current_time; + +/* 9/20/2015 fix - no ghost job + if (remain_budget != ULLONG_MAX && update > now + remain_budget) { + update = now + remain_budget; + } + + TRACE_CUR("on_scheduling_timer at %llu, upd:%llu (for cpu=%d) g_schedule_now:%d remain_budget:%llu\n", now, update, state->cpu, global_schedule_now, remain_budget); +*/ + + if (update <= now) { + litmus_reschedule_local(); + } else if (update != SUP_NO_SCHEDULER_UPDATE) { + hrtimer_set_expires(timer, ns_to_ktime(update)); + restart = HRTIMER_RESTART; + } + + raw_spin_lock(&_global_env.lock); + global_schedule_now = gmp_update_time(&_global_env, now); + + BUG_ON(global_schedule_now < 0 || global_schedule_now > 4); + + /* Find the lowest cpu, and call reschedule */ + while (global_schedule_now--) { + int cpu = get_lowest_prio_cpu(0); + if (cpu != NO_CPU && _lowest_prio_cpu.cpu_entries[cpu].will_schedule == false) { + //raw_spin_lock(&_lowest_prio_cpu.lock); + _lowest_prio_cpu.cpu_entries[cpu].will_schedule = true; + //raw_spin_unlock(&_lowest_prio_cpu.lock); + TRACE("LOWEST CPU = P%d\n", cpu); + if (cpu == state->cpu && update > now) + litmus_reschedule_local(); + else + reschedule[cpu] = 1; + } + } + raw_spin_unlock(&_global_env.lock); + + raw_spin_unlock_irqrestore(&state->lock, flags); + //raw_spin_unlock_irqrestore(&_global_env.lock, flags); + + TS_ISR_END; + + for (cpus = 0; cpuslock); + preempt_if_preemptable(remote_state->scheduled, remote_state->cpu); + raw_spin_unlock(&remote_state->lock); + } + } + + + return restart; +} + +/* mc2_dispatch - Select the next task to schedule. + */ +struct task_struct* mc2_dispatch(struct sup_reservation_environment* sup_env, struct mc2_cpu_state* state) +{ + struct reservation *res, *next; + struct task_struct *tsk = NULL; + struct crit_entry *ce; + enum crit_level lv; + 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)) { + lv = get_task_crit_level(tsk); + if (lv == NUM_CRIT_LEVELS) { + sup_scheduler_update_after(sup_env, res->cur_budget); + return tsk; + } else { + ce = &state->crit_entries[lv]; + sup_scheduler_update_after(sup_env, res->cur_budget); + res->blocked_by_ghost = 0; + res->is_ghost = NO_CPU; + return tsk; +/* no ghost jobs + if (likely(!ce->running)) { + sup_scheduler_update_after(sup_env, res->cur_budget); + res->blocked_by_ghost = 0; + res->is_ghost = NO_CPU; + return tsk; + } else { + res->blocked_by_ghost = 1; + TRACE_TASK(ce->running, " is GHOST\n"); + } +*/ + } + } + } + } + + return NULL; +} + +struct task_struct* mc2_global_dispatch(struct mc2_cpu_state* state) +{ + struct reservation *res, *next; + struct task_struct *tsk = NULL; + //struct crit_entry *ce; + enum crit_level lv; + lt_t time_slice; + + /* no eligible level A or B tasks exists */ + /* check the ghost job */ + /* + ce = &state->crit_entries[CRIT_LEVEL_C]; + if (ce->running) { + TRACE_TASK(ce->running," is GHOST\n"); + return NULL; + } + */ + list_for_each_entry_safe(res, next, &_global_env.active_reservations, list) { + BUG_ON(!res); + if (res->state == RESERVATION_ACTIVE && res->scheduled_on == NO_CPU) { + tsk = res->ops->dispatch_client(res, &time_slice); + if (likely(tsk)) { + lv = get_task_crit_level(tsk); + if (lv == NUM_CRIT_LEVELS) { +#if BUDGET_ENFORCEMENT_AT_C + gmp_add_event_after(&_global_env, res->cur_budget, res->id, EVENT_DRAIN); +#endif + res->event_added = 1; + res->blocked_by_ghost = 0; + res->is_ghost = NO_CPU; + res->scheduled_on = state->cpu; + return tsk; + } else if (lv == CRIT_LEVEL_C) { + //ce = &state->crit_entries[lv]; + //if (likely(!ce->running)) { +#if BUDGET_ENFORCEMENT_AT_C + gmp_add_event_after(&_global_env, res->cur_budget, res->id, EVENT_DRAIN); +#endif + res->event_added = 1; + res->blocked_by_ghost = 0; + res->is_ghost = NO_CPU; + res->scheduled_on = state->cpu; + return tsk; + //} else { + // res->blocked_by_ghost = 1; + // TRACE_TASK(ce->running, " is GHOST\n"); + // return NULL; + //} + } else { + BUG(); + } + } + } + } + + return NULL; +} + +static inline void pre_schedule(struct task_struct *prev, int cpu) +{ + TS_SCHED_A_START; + TS_SCHED_C_START; + + if (!prev || !is_realtime(prev)) + return; + + do_partition(CRIT_LEVEL_C, cpu); +} + +static inline void post_schedule(struct task_struct *next, int cpu) +{ + enum crit_level lev; + if ((!next) || !is_realtime(next)) + return; + + lev = get_task_crit_level(next); + do_partition(lev, cpu); + + switch(lev) { + case CRIT_LEVEL_A: + case CRIT_LEVEL_B: + TS_SCHED_A_END(next); + break; + case CRIT_LEVEL_C: + TS_SCHED_C_END(next); + break; + default: + break; + } + +} + +/* mc2_schedule - main scheduler function. pick the next task to run + */ +static struct task_struct* mc2_schedule(struct task_struct * prev) +{ + /* next == NULL means "schedule background work". */ + lt_t now; + struct mc2_cpu_state *state = local_cpu_state(); + + pre_schedule(prev, state->cpu); + + /* 9/20/2015 fix + raw_spin_lock(&_global_env.lock); + */ + raw_spin_lock(&state->lock); + + //BUG_ON(state->scheduled && state->scheduled != prev); + //BUG_ON(state->scheduled && !is_realtime(prev)); + if (state->scheduled && state->scheduled != prev) + ; //printk(KERN_ALERT "BUG1!!!!!!!! %s %s\n", state->scheduled ? (state->scheduled)->comm : "null", prev ? (prev)->comm : "null"); + if (state->scheduled && !is_realtime(prev)) + ; //printk(KERN_ALERT "BUG2!!!!!!!! \n"); + + /* update time */ + state->sup_env.will_schedule = true; + + now = litmus_clock(); + sup_update_time(&state->sup_env, now); + /* 9/20/2015 fix + gmp_update_time(&_global_env, now); + */ + /* 9/20/2015 fix + mc2_update_ghost_state(state); + */ + + /* remove task from reservation if it blocks */ + if (is_realtime(prev) && !is_running(prev)) { + if (get_task_crit_level(prev) == CRIT_LEVEL_C) + raw_spin_lock(&_global_env.lock); + task_departs(prev, is_completed(prev)); + if (get_task_crit_level(prev) == CRIT_LEVEL_C) + raw_spin_unlock(&_global_env.lock); + } + + /* figure out what to schedule next */ + state->scheduled = mc2_dispatch(&state->sup_env, state); +/* if (state->scheduled && is_realtime(state->scheduled)) + TRACE_TASK(state->scheduled, "mc2_dispatch picked me!\n"); +*/ + if (!state->scheduled) { + raw_spin_lock(&_global_env.lock); + gmp_update_time(&_global_env, now); + state->scheduled = mc2_global_dispatch(state); + _lowest_prio_cpu.cpu_entries[state->cpu].will_schedule = false; + update_cpu_prio(state); + raw_spin_unlock(&_global_env.lock); + } else { + raw_spin_lock(&_global_env.lock); + _lowest_prio_cpu.cpu_entries[state->cpu].will_schedule = false; + update_cpu_prio(state); + raw_spin_unlock(&_global_env.lock); + } + + //raw_spin_lock(&_lowest_prio_cpu.lock); + //_lowest_prio_cpu.cpu_entries[state->cpu].will_schedule = false; + //update_cpu_prio(state); + //raw_spin_unlock(&_lowest_prio_cpu.lock); + + /* Notify LITMUS^RT core that we've arrived at a scheduling decision. */ + sched_state_task_picked(); + + /* program scheduler timer */ + state->sup_env.will_schedule = false; + + /* NOTE: drops state->lock */ + mc2_update_timer_and_unlock(state); + + if (prev != state->scheduled && is_realtime(prev)) { + struct mc2_task_state* tinfo = get_mc2_state(prev); + struct reservation* res = tinfo->res_info.client.reservation; + TRACE_TASK(prev, "PREV JOB scheduled_on = P%d\n", res->scheduled_on); + res->scheduled_on = NO_CPU; + TRACE_TASK(prev, "descheduled.\n"); + /* if prev is preempted and a global task, find the lowest cpu and reschedule */ + if (tinfo->has_departed == false && get_task_crit_level(prev) == CRIT_LEVEL_C) { + int cpu; + raw_spin_lock(&_global_env.lock); + cpu = get_lowest_prio_cpu(res?res->priority:0); + //TRACE("LEVEL-C TASK PREEMPTED!! poking CPU %d to reschedule\n", cpu); + if (cpu != NO_CPU && _lowest_prio_cpu.cpu_entries[cpu].will_schedule == false) { + //raw_spin_lock(&_lowest_prio_cpu.lock); + _lowest_prio_cpu.cpu_entries[cpu].will_schedule = true; + resched_cpu[cpu] = 1; + //raw_spin_unlock(&_lowest_prio_cpu.lock); + } + raw_spin_unlock(&_global_env.lock); + } + } + if (state->scheduled) { + TRACE_TASK(state->scheduled, "scheduled.\n"); + } + + post_schedule(state->scheduled, state->cpu); + + return state->scheduled; +} + +static void resume_legacy_task_model_updates(struct task_struct *tsk) +{ + lt_t now; + if (is_sporadic(tsk)) { + /* If this sporadic task was gone for a "long" time and woke up past + * its deadline, then give it a new budget by triggering a job + * release. This is purely cosmetic and has no effect on the + * MC2 scheduler. */ + + now = litmus_clock(); + if (is_tardy(tsk, now)) { + //release_at(tsk, now); + //sched_trace_task_release(tsk); + } + } +} + +/* mc2_task_resume - Called when the state of tsk changes back to + * TASK_RUNNING. We need to requeue the task. + */ +static void mc2_task_resume(struct task_struct *tsk) +{ + unsigned long flags; + struct mc2_task_state* tinfo = get_mc2_state(tsk); + struct mc2_cpu_state *state; + + TRACE_TASK(tsk, "thread wakes up at %llu\n", litmus_clock()); + + local_irq_save(flags); + if (tinfo->cpu != -1) + state = cpu_state_for(tinfo->cpu); + else + state = local_cpu_state(); + + /* 9/20/2015 fix + raw_spin_lock(&_global_env.lock); + */ + /* Requeue only if self-suspension was already processed. */ + if (tinfo->has_departed) + { + /* We don't want to consider jobs before synchronous releases */ + if (tsk_rt(tsk)->job_params.job_no > 5) { + switch(get_task_crit_level(tsk)) { + case CRIT_LEVEL_A: + TS_RELEASE_LATENCY_A(get_release(tsk)); + break; + case CRIT_LEVEL_B: + TS_RELEASE_LATENCY_B(get_release(tsk)); + break; + case CRIT_LEVEL_C: + TS_RELEASE_LATENCY_C(get_release(tsk)); + break; + default: + break; + } + } + + raw_spin_lock(&state->lock); + /* Assumption: litmus_clock() is synchronized across cores, + * since we might not actually be executing on tinfo->cpu + * at the moment. */ + if (tinfo->cpu != -1) { + sup_update_time(&state->sup_env, litmus_clock()); + task_arrives(state, tsk); + } else { + raw_spin_lock(&_global_env.lock); + gmp_update_time(&_global_env, litmus_clock()); + task_arrives(state, tsk); + raw_spin_unlock(&_global_env.lock); + } + + /* 9/20/2015 fix + mc2_update_ghost_state(state); + */ + //task_arrives(state, tsk); + /* NOTE: drops state->lock */ + TRACE_TASK(tsk, "mc2_resume()\n"); + mc2_update_timer_and_unlock(state); + } else { + TRACE_TASK(tsk, "resume event ignored, still scheduled\n"); + //raw_spin_unlock(&_global_env.lock); + } + + local_irq_restore(flags); + + //gmp_free_passed_event(); + resume_legacy_task_model_updates(tsk); +} + +/* mc2_complete_job - syscall backend for job completions + */ +static long mc2_complete_job(void) +{ + ktime_t next_release; + long err; + + tsk_rt(current)->completed = 1; + + /* If this the first job instance, we need to reset replenish + time to the next release time */ + if (tsk_rt(current)->sporadic_release) { + struct mc2_cpu_state *state; + struct reservation_environment *env; + struct mc2_task_state *tinfo; + struct reservation *res = NULL; + unsigned long flags; + enum crit_level lv; + + preempt_disable(); + local_irq_save(flags); + + tinfo = get_mc2_state(current); + lv = get_task_crit_level(current); + + if (lv < CRIT_LEVEL_C) { + state = cpu_state_for(tinfo->cpu); + raw_spin_lock(&state->lock); + env = &(state->sup_env.env); + res = sup_find_by_id(&state->sup_env, tinfo->mc2_param.res_id); + env->time_zero = tsk_rt(current)->sporadic_release_time; + } + else if (lv == CRIT_LEVEL_C) { + state = local_cpu_state(); + raw_spin_lock(&state->lock); + raw_spin_lock(&_global_env.lock); + res = gmp_find_by_id(&_global_env, tinfo->mc2_param.res_id); + _global_env.env.time_zero = tsk_rt(current)->sporadic_release_time; + } + else + BUG(); + + /* set next_replenishtime to synchronous release time */ + BUG_ON(!res); + res->next_replenishment = tsk_rt(current)->sporadic_release_time; +/* + if (get_task_crit_level(current) == CRIT_LEVEL_A) { + struct table_driven_reservation *tdres; + tdres = container_of(res, struct table_driven_reservation, res); + tdres->next_interval = 0; + tdres->major_cycle_start = tsk_rt(current)->sporadic_release_time; + res->next_replenishment += tdres->intervals[0].start; + } +*/ + res->cur_budget = 0; + res->env->change_state(res->env, res, RESERVATION_DEPLETED); + + //TRACE_CUR("CHANGE NEXT_REP = %llu NEXT_UPDATE = %llu\n", res->next_replenishment, state->sup_env.next_scheduler_update); + + //if (lv < CRIT_LEVEL_C) +// raw_spin_unlock(&state->lock); + //else + if (lv == CRIT_LEVEL_C) + raw_spin_unlock(&_global_env.lock); + + raw_spin_unlock(&state->lock); + local_irq_restore(flags); + preempt_enable(); + } + + sched_trace_task_completion(current, 0); + /* update the next release time and deadline */ + prepare_for_next_period(current); + sched_trace_task_release(current); + next_release = ns_to_ktime(get_release(current)); + preempt_disable(); + TRACE_CUR("next_release=%llu\n", get_release(current)); + if (get_release(current) > litmus_clock()) { + /* sleep until next_release */ + set_current_state(TASK_INTERRUPTIBLE); + preempt_enable_no_resched(); + err = schedule_hrtimeout(&next_release, HRTIMER_MODE_ABS); + } else { + /* release the next job immediately */ + err = 0; + TRACE_CUR("TARDY: release=%llu now=%llu\n", get_release(current), litmus_clock()); + preempt_enable(); + } + + TRACE_CUR("mc2_complete_job returns at %llu\n", litmus_clock()); + + return err; +} + +/* mc2_admit_task - Setup mc2 task parameters + */ +static long mc2_admit_task(struct task_struct *tsk) +{ + long err = -ESRCH; + unsigned long flags; + struct reservation *res; + struct mc2_cpu_state *state; + struct mc2_task_state *tinfo = kzalloc(sizeof(*tinfo), GFP_ATOMIC); + struct mc2_task *mp = tsk_rt(tsk)->mc2_data; + enum crit_level lv; + + if (!tinfo) + return -ENOMEM; + + if (!mp) { + printk(KERN_ERR "mc2_admit_task: criticality level has not been set\n"); + return err; + } + + lv = mp->crit; + preempt_disable(); + + if (lv < CRIT_LEVEL_C) { + state = cpu_state_for(task_cpu(tsk)); + raw_spin_lock_irqsave(&state->lock, flags); + + res = sup_find_by_id(&state->sup_env, mp->res_id); + + /* found the appropriate reservation */ + if (res) { + TRACE_TASK(tsk, "SUP FOUND RES ID\n"); + tinfo->mc2_param.crit = mp->crit; + tinfo->mc2_param.res_id = mp->res_id; + + /* initial values */ + err = mc2_task_client_init(&tinfo->res_info, &tinfo->mc2_param, tsk, res); + tinfo->cpu = task_cpu(tsk); + tinfo->has_departed = true; + tsk_rt(tsk)->plugin_state = tinfo; + + /* disable LITMUS^RT's per-thread budget enforcement */ + tsk_rt(tsk)->task_params.budget_policy = NO_ENFORCEMENT; + } + + raw_spin_unlock_irqrestore(&state->lock, flags); + } else if (lv == CRIT_LEVEL_C) { + state = local_cpu_state(); + raw_spin_lock_irqsave(&state->lock, flags); + raw_spin_lock(&_global_env.lock); + //state = local_cpu_state(); + + //raw_spin_lock(&state->lock); + + res = gmp_find_by_id(&_global_env, mp->res_id); + + /* found the appropriate reservation (or vCPU) */ + if (res) { + TRACE_TASK(tsk, "GMP FOUND RES ID\n"); + tinfo->mc2_param.crit = mp->crit; + tinfo->mc2_param.res_id = mp->res_id; + + /* initial values */ + err = mc2_task_client_init(&tinfo->res_info, &tinfo->mc2_param, tsk, res); + tinfo->cpu = -1; + tinfo->has_departed = true; + tsk_rt(tsk)->plugin_state = tinfo; + + /* disable LITMUS^RT's per-thread budget enforcement */ + tsk_rt(tsk)->task_params.budget_policy = NO_ENFORCEMENT; + } + + raw_spin_unlock(&_global_env.lock); + raw_spin_unlock_irqrestore(&state->lock, flags); + } + + preempt_enable(); + + if (err) + kfree(tinfo); + + return err; +} + +/* mc2_task_new - A new real-time job is arrived. Release the next job + * at the next reservation replenish time + */ +static void mc2_task_new(struct task_struct *tsk, int on_runqueue, + int is_running) +{ + unsigned long flags; + struct mc2_task_state* tinfo = get_mc2_state(tsk); + struct mc2_cpu_state *state; // = cpu_state_for(tinfo->cpu); + struct reservation *res; + enum crit_level lv = get_task_crit_level(tsk); + lt_t release = 0; + + TRACE_TASK(tsk, "new RT task %llu (on_rq:%d, running:%d)\n", + litmus_clock(), on_runqueue, is_running); + + if (tinfo->cpu == -1) + state = local_cpu_state(); + else + state = cpu_state_for(tinfo->cpu); + + local_irq_save(flags); + + /* acquire the lock protecting the state and disable interrupts */ + //raw_spin_lock(&_global_env.lock); + //raw_spin_lock(&state->lock); + if (is_running) { + state->scheduled = tsk; + /* make sure this task should actually be running */ + litmus_reschedule_local(); + } + + raw_spin_lock(&state->lock); + + if (lv == CRIT_LEVEL_C) { + raw_spin_lock(&_global_env.lock); + res = gmp_find_by_id(&_global_env, tinfo->mc2_param.res_id); + } + else { + res = sup_find_by_id(&state->sup_env, tinfo->mc2_param.res_id); + } + //res = res_find_by_id(state, tinfo->mc2_param.res_id); + release = res->next_replenishment; + + if (on_runqueue || is_running) { + /* Assumption: litmus_clock() is synchronized across cores + * [see comment in pres_task_resume()] */ + if (lv == CRIT_LEVEL_C) { + gmp_update_time(&_global_env, litmus_clock()); + //raw_spin_unlock(&_global_env.lock); + } + else + sup_update_time(&state->sup_env, litmus_clock()); + //mc2_update_time(lv, state, litmus_clock()); + /* 9/20/2015 fix + mc2_update_ghost_state(state); + */ + task_arrives(state, tsk); + if (lv == CRIT_LEVEL_C) + raw_spin_unlock(&_global_env.lock); + /* NOTE: drops state->lock */ + TRACE("mc2_new()\n"); + + mc2_update_timer_and_unlock(state); + } else { + if (lv == CRIT_LEVEL_C) + raw_spin_unlock(&_global_env.lock); + raw_spin_unlock(&state->lock); + //raw_spin_unlock(&_global_env.lock); + } + local_irq_restore(flags); + + if (!release) { + TRACE_TASK(tsk, "mc2_task_new() next_release = %llu\n", release); + //release_at(tsk, release); + } + else + TRACE_TASK(tsk, "mc2_task_new() next_release = NULL\n"); +} + +/* mc2_reservation_destroy - reservation_destroy system call backend + */ +static long mc2_reservation_destroy(unsigned int reservation_id, int cpu) +{ + long ret = -EINVAL; + struct mc2_cpu_state *state; + struct reservation *res = NULL, *next; + struct sup_reservation_environment *sup_env; + int found = 0; + //enum crit_level lv = get_task_crit_level(current); + unsigned long flags; + + if (cpu == -1) { + /* if the reservation is global reservation */ + local_irq_save(flags); + //state = local_cpu_state(); + raw_spin_lock(&_global_env.lock); + //raw_spin_lock(&state->lock); + + list_for_each_entry_safe(res, next, &_global_env.depleted_reservations, list) { + if (res->id == reservation_id) { + list_del(&res->list); + kfree(res); + found = 1; + ret = 0; + } + } + if (!found) { + list_for_each_entry_safe(res, next, &_global_env.inactive_reservations, list) { + if (res->id == reservation_id) { + list_del(&res->list); + kfree(res); + found = 1; + ret = 0; + } + } + } + if (!found) { + list_for_each_entry_safe(res, next, &_global_env.active_reservations, list) { + if (res->id == reservation_id) { + list_del(&res->list); + kfree(res); + found = 1; + ret = 0; + } + } + } + + //raw_spin_unlock(&state->lock); + raw_spin_unlock(&_global_env.lock); + local_irq_restore(flags); + } else { + /* if the reservation is partitioned reservation */ + state = cpu_state_for(cpu); + local_irq_save(flags); + raw_spin_lock(&state->lock); + + // res = sup_find_by_id(&state->sup_env, reservation_id); + sup_env = &state->sup_env; + list_for_each_entry_safe(res, next, &sup_env->depleted_reservations, list) { + if (res->id == reservation_id) { +/* + if (lv == CRIT_LEVEL_A) { + struct table_driven_reservation *tdres; + tdres = container_of(res, struct table_driven_reservation, res); + kfree(tdres->intervals); + } +*/ + list_del(&res->list); + kfree(res); + found = 1; + ret = 0; + } + } + if (!found) { + list_for_each_entry_safe(res, next, &sup_env->inactive_reservations, list) { + if (res->id == reservation_id) { +/* if (lv == CRIT_LEVEL_A) { + struct table_driven_reservation *tdres; + tdres = container_of(res, struct table_driven_reservation, res); + kfree(tdres->intervals); + } +*/ + list_del(&res->list); + kfree(res); + found = 1; + ret = 0; + } + } + } + if (!found) { + list_for_each_entry_safe(res, next, &sup_env->active_reservations, list) { + if (res->id == reservation_id) { +/* if (lv == CRIT_LEVEL_A) { + struct table_driven_reservation *tdres; + tdres = container_of(res, struct table_driven_reservation, res); + kfree(tdres->intervals); + } +*/ + list_del(&res->list); + kfree(res); + found = 1; + ret = 0; + } + } + } + + raw_spin_unlock(&state->lock); + local_irq_restore(flags); + } + + TRACE("Rerservation destroyed ret = %d\n", ret); + return ret; +} + +/* mc2_task_exit - Task became a normal task (not real-time task) + */ +static void mc2_task_exit(struct task_struct *tsk) +{ + unsigned long flags; + struct mc2_task_state* tinfo = get_mc2_state(tsk); + struct mc2_cpu_state *state; + enum crit_level lv = tinfo->mc2_param.crit; + struct crit_entry* ce; + int cpu; + + local_irq_save(flags); + if (tinfo->cpu != -1) + state = cpu_state_for(tinfo->cpu); + else + state = local_cpu_state(); + + raw_spin_lock(&state->lock); + + if (state->scheduled == tsk) + state->scheduled = NULL; + + ce = &state->crit_entries[lv]; + if (ce->running == tsk) + ce->running = NULL; + + /* remove from queues */ + if (is_running(tsk)) { + /* Assumption: litmus_clock() is synchronized across cores + * [see comment in pres_task_resume()] */ + + /* update both global and partitioned */ + if (lv < CRIT_LEVEL_C) { + sup_update_time(&state->sup_env, litmus_clock()); + } + else if (lv == CRIT_LEVEL_C) { + raw_spin_lock(&_global_env.lock); + gmp_update_time(&_global_env, litmus_clock()); + //raw_spin_unlock(&_global_env.lock); + } + /* 9/20/2015 fix + mc2_update_ghost_state(state); + */ + task_departs(tsk, 0); + if (lv == CRIT_LEVEL_C) + raw_spin_unlock(&_global_env.lock); + + /* NOTE: drops state->lock */ + TRACE("mc2_exit()\n"); + + mc2_update_timer_and_unlock(state); + } else { + raw_spin_unlock(&state->lock); + + } + + if (lv == CRIT_LEVEL_C) { + for_each_online_cpu(cpu) { + state = cpu_state_for(cpu); + if (state == local_cpu_state()) + continue; + raw_spin_lock(&state->lock); + + if (state->scheduled == tsk) + state->scheduled = NULL; + + ce = &state->crit_entries[lv]; + if (ce->running == tsk) + ce->running = NULL; + + raw_spin_unlock(&state->lock); + } + } + + local_irq_restore(flags); + + kfree(tsk_rt(tsk)->plugin_state); + tsk_rt(tsk)->plugin_state = NULL; + kfree(tsk_rt(tsk)->mc2_data); + tsk_rt(tsk)->mc2_data = NULL; +} + +/* create_polling_reservation - create a new polling reservation + */ +static long create_polling_reservation( + int res_type, + struct reservation_config *config) +{ + struct mc2_cpu_state *state; + struct reservation* res; + struct polling_reservation *pres; + unsigned long flags; + int use_edf = config->priority == LITMUS_NO_PRIORITY; + int periodic = res_type == PERIODIC_POLLING; + long err = -EINVAL; + + /* sanity checks */ + 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; + } + + /* Allocate before we grab a spin lock. + * Todo: would be nice to use a core-local allocation. + */ + pres = kzalloc(sizeof(*pres), GFP_KERNEL); + if (!pres) + return -ENOMEM; + + if (config->cpu != -1) { + + //raw_spin_lock_irqsave(&_global_env.lock, flags); + state = cpu_state_for(config->cpu); + raw_spin_lock_irqsave(&state->lock, flags); + + res = sup_find_by_id(&state->sup_env, config->id); + if (!res) { + 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; + pres->res.blocked_by_ghost = 0; + pres->res.is_ghost = NO_CPU; + if (!use_edf) + pres->res.priority = config->priority; + sup_add_new_reservation(&state->sup_env, &pres->res); + err = config->id; + } else { + err = -EEXIST; + } + + raw_spin_unlock_irqrestore(&state->lock, flags); + //raw_spin_unlock_irqrestore(&_global_env.lock, flags); + + } else { + raw_spin_lock_irqsave(&_global_env.lock, flags); + + res = gmp_find_by_id(&_global_env, config->id); + if (!res) { + 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; + pres->res.blocked_by_ghost = 0; + pres->res.scheduled_on = NO_CPU; + pres->res.is_ghost = NO_CPU; + if (!use_edf) + pres->res.priority = config->priority; + gmp_add_new_reservation(&_global_env, &pres->res); + err = config->id; + } else { + err = -EEXIST; + } + raw_spin_unlock_irqrestore(&_global_env.lock, flags); + } + + if (err < 0) + kfree(pres); + + return err; +} + +#define MAX_INTERVALS 1024 + +/* create_table_driven_reservation - create a table_driven reservation + */ +static long create_table_driven_reservation( + struct reservation_config *config) +{ + struct mc2_cpu_state *state; + struct reservation* res; + struct table_driven_reservation *td_res = NULL; + struct lt_interval *slots = NULL; + size_t slots_size; + unsigned int i, num_slots; + unsigned long flags; + long err = -EINVAL; + + + 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; + slots = kzalloc(slots_size, GFP_KERNEL); + if (!slots) + return -ENOMEM; + + td_res = kzalloc(sizeof(*td_res), GFP_KERNEL); + if (!td_res) + err = -ENOMEM; + else + 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) { + state = cpu_state_for(config->cpu); + raw_spin_lock_irqsave(&state->lock, flags); + + res = sup_find_by_id(&state->sup_env, config->id); + if (!res) { + 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; + td_res->res.blocked_by_ghost = 0; + sup_add_new_reservation(&state->sup_env, &td_res->res); + err = config->id; + } else { + err = -EEXIST; + } + + raw_spin_unlock_irqrestore(&state->lock, flags); + } + + if (err < 0) { + kfree(slots); + kfree(td_res); + } + + return err; +} + +/* mc2_reservation_create - reservation_create system call backend + */ +static long mc2_reservation_create(int res_type, void* __user _config) +{ + long ret = -EINVAL; + struct reservation_config config; + + TRACE("Attempt to create reservation (%d)\n", res_type); + + if (copy_from_user(&config, _config, sizeof(config))) + return -EFAULT; + + if (config.cpu != -1) { + if (config.cpu < 0 || !cpu_online(config.cpu)) { + printk(KERN_ERR "invalid polling reservation (%u): " + "CPU %d offline\n", config.id, config.cpu); + return -EINVAL; + } + } + + switch (res_type) { + case PERIODIC_POLLING: + case SPORADIC_POLLING: + ret = create_polling_reservation(res_type, &config); + break; + + case TABLE_DRIVEN: + ret = create_table_driven_reservation(&config); + break; + + default: + return -EINVAL; + }; + + return ret; +} + +static struct domain_proc_info mc2_domain_proc_info; + +static long mc2_get_domain_proc_info(struct domain_proc_info **ret) +{ + *ret = &mc2_domain_proc_info; + return 0; +} + +static void mc2_setup_domain_proc(void) +{ + int i, cpu; + int num_rt_cpus = num_online_cpus(); + + struct cd_mapping *cpu_map, *domain_map; + + memset(&mc2_domain_proc_info, sizeof(mc2_domain_proc_info), 0); + init_domain_proc_info(&mc2_domain_proc_info, num_rt_cpus, num_rt_cpus); + mc2_domain_proc_info.num_cpus = num_rt_cpus; + mc2_domain_proc_info.num_domains = num_rt_cpus; + + i = 0; + for_each_online_cpu(cpu) { + cpu_map = &mc2_domain_proc_info.cpu_to_domains[i]; + domain_map = &mc2_domain_proc_info.domain_to_cpus[i]; + + cpu_map->id = cpu; + domain_map->id = i; + cpumask_set_cpu(i, cpu_map->mask); + cpumask_set_cpu(cpu, domain_map->mask); + ++i; + } +} + +static long mc2_activate_plugin(void) +{ + int cpu, lv; + struct mc2_cpu_state *state; + struct cpu_entry *ce; + + gmp_init(&_global_env); + raw_spin_lock_init(&_lowest_prio_cpu.lock); + + for_each_online_cpu(cpu) { + TRACE("Initializing CPU%d...\n", cpu); + + resched_cpu[cpu] = 0; + state = cpu_state_for(cpu); + ce = &_lowest_prio_cpu.cpu_entries[cpu]; + + ce->cpu = cpu; + ce->scheduled = NULL; + ce->deadline = ULLONG_MAX; + ce->lv = NUM_CRIT_LEVELS; + ce->will_schedule = false; + + raw_spin_lock_init(&state->lock); + state->cpu = cpu; + state->scheduled = NULL; + for (lv = 0; lv < NUM_CRIT_LEVELS; lv++) { + struct crit_entry *cr_entry = &state->crit_entries[lv]; + cr_entry->level = lv; + cr_entry->running = NULL; + } + sup_init(&state->sup_env); + + hrtimer_init(&state->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS_PINNED); + state->timer.function = on_scheduling_timer; + } + + mc2_setup_domain_proc(); + + return 0; +} + +static void mc2_finish_switch(struct task_struct *prev) +{ + struct mc2_cpu_state *state = local_cpu_state(); + + state->scheduled = is_realtime(current) ? current : NULL; +} + +static long mc2_deactivate_plugin(void) +{ + int cpu; + struct mc2_cpu_state *state; + struct reservation *res; + struct next_timer_event *event; + struct cpu_entry *ce; + + for_each_online_cpu(cpu) { + state = cpu_state_for(cpu); + raw_spin_lock(&state->lock); + + hrtimer_cancel(&state->timer); + + ce = &_lowest_prio_cpu.cpu_entries[cpu]; + + ce->cpu = cpu; + ce->scheduled = NULL; + ce->deadline = ULLONG_MAX; + ce->lv = NUM_CRIT_LEVELS; + ce->will_schedule = false; + + /* Delete all reservations --- assumes struct reservation + * is prefix of containing struct. */ + + while (!list_empty(&state->sup_env.active_reservations)) { + res = list_first_entry( + &state->sup_env.active_reservations, + struct reservation, list); + list_del(&res->list); + kfree(res); + } + + while (!list_empty(&state->sup_env.inactive_reservations)) { + res = list_first_entry( + &state->sup_env.inactive_reservations, + struct reservation, list); + list_del(&res->list); + kfree(res); + } + + while (!list_empty(&state->sup_env.depleted_reservations)) { + res = list_first_entry( + &state->sup_env.depleted_reservations, + struct reservation, list); + list_del(&res->list); + kfree(res); + } + + raw_spin_unlock(&state->lock); + } + + raw_spin_lock(&_global_env.lock); + + while (!list_empty(&_global_env.active_reservations)) { + res = list_first_entry( + &_global_env.active_reservations, + struct reservation, list); + list_del(&res->list); + kfree(res); + } + + while (!list_empty(&_global_env.inactive_reservations)) { + res = list_first_entry( + &_global_env.inactive_reservations, + struct reservation, list); + list_del(&res->list); + kfree(res); + } + + while (!list_empty(&_global_env.depleted_reservations)) { + res = list_first_entry( + &_global_env.depleted_reservations, + struct reservation, list); + list_del(&res->list); + kfree(res); + } + + while (!list_empty(&_global_env.next_events)) { + event = list_first_entry( + &_global_env.next_events, + struct next_timer_event, list); + list_del(&event->list); + kfree(event); + } + + raw_spin_unlock(&_global_env.lock); + + destroy_domain_proc_info(&mc2_domain_proc_info); + return 0; +} + +static struct sched_plugin mc2_plugin = { + .plugin_name = "MC2", + .schedule = mc2_schedule, + .finish_switch = mc2_finish_switch, + .task_wake_up = mc2_task_resume, + .admit_task = mc2_admit_task, + .task_new = mc2_task_new, + .task_exit = mc2_task_exit, + .complete_job = mc2_complete_job, + .get_domain_proc_info = mc2_get_domain_proc_info, + .activate_plugin = mc2_activate_plugin, + .deactivate_plugin = mc2_deactivate_plugin, + .reservation_create = mc2_reservation_create, + .reservation_destroy = mc2_reservation_destroy, +}; + +static int __init init_mc2(void) +{ + return register_sched_plugin(&mc2_plugin); +} + +module_init(init_mc2); -- cgit v1.2.2