Bjoern's Dissertation Code with Priority Donationwip-splitting-omlp-jerickso

17 files changed, 374 insertions, 1 deletions

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index cea0cd9a316f..5181ed3a211a 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -2142,3 +2142,11 @@ source "crypto/Kconfig"
 source "arch/x86/kvm/Kconfig"
 
 source "lib/Kconfig"
+
+config ARCH_HAS_FEATHER_TRACE
+        def_bool y
+
+config ARCH_HAS_SEND_PULL_TIMERS
+        def_bool y
+
+source "litmus/Kconfig"
diff --git a/arch/x86/include/asm/entry_arch.h b/arch/x86/include/asm/entry_arch.h
index 8e8ec663a98f..5d07dea2ebb8 100644
--- a/arch/x86/include/asm/entry_arch.h
+++ b/arch/x86/include/asm/entry_arch.h
@@ -13,6 +13,7 @@
 BUILD_INTERRUPT(reschedule_interrupt,RESCHEDULE_VECTOR)
 BUILD_INTERRUPT(call_function_interrupt,CALL_FUNCTION_VECTOR)
 BUILD_INTERRUPT(call_function_single_interrupt,CALL_FUNCTION_SINGLE_VECTOR)
+BUILD_INTERRUPT(pull_timers_interrupt,PULL_TIMERS_VECTOR)
 BUILD_INTERRUPT(irq_move_cleanup_interrupt,IRQ_MOVE_CLEANUP_VECTOR)
 BUILD_INTERRUPT(reboot_interrupt,REBOOT_VECTOR)
 
diff --git a/arch/x86/include/asm/feather_trace.h b/arch/x86/include/asm/feather_trace.h
new file mode 100644
index 000000000000..4fd31633405d
--- /dev/null
+++ b/arch/x86/include/asm/feather_trace.h
@@ -0,0 +1,17 @@
+#ifndef _ARCH_FEATHER_TRACE_H
+#define _ARCH_FEATHER_TRACE_H
+
+#include <asm/msr.h>
+
+static inline unsigned long long ft_timestamp(void)
+{
+        return __native_read_tsc();
+}
+
+#ifdef CONFIG_X86_32
+#include "feather_trace_32.h"
+#else
+#include "feather_trace_64.h"
+#endif
+
+#endif
diff --git a/arch/x86/include/asm/feather_trace_32.h b/arch/x86/include/asm/feather_trace_32.h
new file mode 100644
index 000000000000..70202f90f169
--- /dev/null
+++ b/arch/x86/include/asm/feather_trace_32.h
@@ -0,0 +1,79 @@
+/* Do not directly include this file. Include feather_trace.h instead */
+
+#define feather_callback __attribute__((regparm(0)))
+
+/*
+ * make the compiler reload any register that is not saved in
+ * a cdecl function call
+ */
+#define CLOBBER_LIST "memory", "cc", "eax", "ecx", "edx"
+
+#define ft_event(id, callback)                                  \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " call " #callback "                          \n\t" \
+            ".section __event_table, \"aw\"               \n\t" \
+            ".long " #id  ", 0, 1b, 2f                    \n\t" \
+            ".previous                                    \n\t" \
+            "2:                                           \n\t" \
+        : : : CLOBBER_LIST)
+
+#define ft_event0(id, callback)                                 \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " subl $4, %%esp                              \n\t" \
+            " movl $" #id  ", (%%esp)                     \n\t" \
+            " call " #callback "                          \n\t" \
+            " addl $4, %%esp                              \n\t" \
+            ".section __event_table, \"aw\"               \n\t" \
+            ".long " #id  ", 0, 1b, 2f                    \n\t" \
+            ".previous                                    \n\t" \
+            "2:                                           \n\t" \
+        : :  : CLOBBER_LIST)
+
+#define ft_event1(id, callback, param)                          \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " subl $8, %%esp                              \n\t" \
+            " movl %0, 4(%%esp)                           \n\t" \
+            " movl $" #id  ", (%%esp)                     \n\t" \
+            " call " #callback "                          \n\t" \
+            " addl $8, %%esp                              \n\t" \
+            ".section __event_table, \"aw\"               \n\t" \
+            ".long " #id  ", 0, 1b, 2f                    \n\t" \
+            ".previous                                    \n\t" \
+            "2:                                           \n\t" \
+        : : "r" (param)  : CLOBBER_LIST)
+
+#define ft_event2(id, callback, param, param2)                  \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " subl $12, %%esp                             \n\t" \
+            " movl %1, 8(%%esp)                           \n\t" \
+            " movl %0, 4(%%esp)                           \n\t" \
+            " movl $" #id  ", (%%esp)                     \n\t" \
+            " call " #callback "                          \n\t" \
+            " addl $12, %%esp                             \n\t" \
+            ".section __event_table, \"aw\"               \n\t" \
+            ".long " #id  ", 0, 1b, 2f                    \n\t" \
+            ".previous                                    \n\t" \
+            "2:                                           \n\t" \
+        : : "r" (param), "r" (param2)  : CLOBBER_LIST)
+
+
+#define ft_event3(id, callback, p, p2, p3)                      \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " subl $16, %%esp                             \n\t" \
+            " movl %2, 12(%%esp)                          \n\t" \
+            " movl %1, 8(%%esp)                           \n\t" \
+            " movl %0, 4(%%esp)                           \n\t" \
+            " movl $" #id  ", (%%esp)                     \n\t" \
+            " call " #callback "                          \n\t" \
+            " addl $16, %%esp                             \n\t" \
+            ".section __event_table, \"aw\"               \n\t" \
+            ".long " #id  ", 0, 1b, 2f                    \n\t" \
+            ".previous                                    \n\t" \
+            "2:                                           \n\t" \
+        : : "r" (p), "r" (p2), "r" (p3)  : CLOBBER_LIST)
+
diff --git a/arch/x86/include/asm/feather_trace_64.h b/arch/x86/include/asm/feather_trace_64.h
new file mode 100644
index 000000000000..54ac2aeb3a28
--- /dev/null
+++ b/arch/x86/include/asm/feather_trace_64.h
@@ -0,0 +1,67 @@
+/* Do not directly include this file. Include feather_trace.h instead */
+
+/* regparm is the default on x86_64 */
+#define feather_callback
+
+# define _EVENT_TABLE(id,from,to) \
+            ".section __event_table, \"aw\"\n\t" \
+            ".balign 8\n\t" \
+            ".quad " #id  ", 0, " #from ", " #to " \n\t" \
+            ".previous \n\t"
+
+/*
+ * x86_64 callee only owns rbp, rbx, r12 -> r15
+ * the called can freely modify the others
+ */
+#define CLOBBER_LIST    "memory", "cc", "rdi", "rsi", "rdx", "rcx", \
+                        "r8", "r9", "r10", "r11", "rax"
+
+#define ft_event(id, callback)                                  \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " call " #callback "                          \n\t" \
+            _EVENT_TABLE(id,1b,2f) \
+            "2:                                           \n\t" \
+        : : : CLOBBER_LIST)
+
+#define ft_event0(id, callback)                                 \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " movq $" #id ", %%rdi                        \n\t" \
+            " call " #callback "                          \n\t" \
+            _EVENT_TABLE(id,1b,2f) \
+            "2:                                           \n\t" \
+        : :  : CLOBBER_LIST)
+
+#define ft_event1(id, callback, param)                          \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " movq %0, %%rsi                              \n\t" \
+            " movq $" #id ", %%rdi                        \n\t" \
+            " call " #callback "                          \n\t" \
+            _EVENT_TABLE(id,1b,2f) \
+            "2:                                           \n\t" \
+        : : "r" (param)  : CLOBBER_LIST)
+
+#define ft_event2(id, callback, param, param2)                  \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " movq %1, %%rdx                              \n\t" \
+            " movq %0, %%rsi                              \n\t" \
+            " movq $" #id ", %%rdi                        \n\t" \
+            " call " #callback "                          \n\t" \
+            _EVENT_TABLE(id,1b,2f) \
+            "2:                                           \n\t" \
+        : : "r" (param), "r" (param2)  : CLOBBER_LIST)
+
+#define ft_event3(id, callback, p, p2, p3)                      \
+        __asm__ __volatile__(                                   \
+            "1: jmp 2f                                    \n\t" \
+            " movq %2, %%rcx                              \n\t" \
+            " movq %1, %%rdx                              \n\t" \
+            " movq %0, %%rsi                              \n\t" \
+            " movq $" #id ", %%rdi                        \n\t" \
+            " call " #callback "                          \n\t" \
+            _EVENT_TABLE(id,1b,2f) \
+            "2:                                           \n\t" \
+        : : "r" (p), "r" (p2), "r" (p3)  : CLOBBER_LIST)
diff --git a/arch/x86/include/asm/hw_irq.h b/arch/x86/include/asm/hw_irq.h
index 46c0fe05f230..c17411503f28 100644
--- a/arch/x86/include/asm/hw_irq.h
+++ b/arch/x86/include/asm/hw_irq.h
@@ -53,6 +53,8 @@ extern void threshold_interrupt(void);
 extern void call_function_interrupt(void);
 extern void call_function_single_interrupt(void);
 
+extern void pull_timers_interrupt(void);
+
 /* IOAPIC */
 #define IO_APIC_IRQ(x) (((x) >= NR_IRQS_LEGACY) || ((1<<(x)) & io_apic_irqs))
 extern unsigned long io_apic_irqs;
@@ -122,6 +124,7 @@ extern asmlinkage void smp_irq_move_cleanup_interrupt(void);
 extern void smp_reschedule_interrupt(struct pt_regs *);
 extern void smp_call_function_interrupt(struct pt_regs *);
 extern void smp_call_function_single_interrupt(struct pt_regs *);
+extern void smp_pull_timers_interrupt(struct pt_regs *);
 #ifdef CONFIG_X86_32
 extern void smp_invalidate_interrupt(struct pt_regs *);
 #else
diff --git a/arch/x86/include/asm/irq_vectors.h b/arch/x86/include/asm/irq_vectors.h
index e2ca30092557..6143ebeeebfa 100644
--- a/arch/x86/include/asm/irq_vectors.h
+++ b/arch/x86/include/asm/irq_vectors.h
@@ -109,6 +109,11 @@
 #define LOCAL_TIMER_VECTOR              0xef
 
 /*
+ * LITMUS^RT pull timers IRQ vector
+ */
+#define PULL_TIMERS_VECTOR              0xee
+
+/*
  * Generic system vector for platform specific use
  */
 #define X86_PLATFORM_IPI_VECTOR         0xed
diff --git a/arch/x86/include/asm/processor.h b/arch/x86/include/asm/processor.h
index 325b7bdbebaa..ebaa04a8d3af 100644
--- a/arch/x86/include/asm/processor.h
+++ b/arch/x86/include/asm/processor.h
@@ -169,6 +169,10 @@ extern void print_cpu_info(struct cpuinfo_x86 *);
 extern void init_scattered_cpuid_features(struct cpuinfo_x86 *c);
 extern unsigned int init_intel_cacheinfo(struct cpuinfo_x86 *c);
 extern unsigned short num_cache_leaves;
+#ifdef CONFIG_SYSFS
+extern int get_shared_cpu_map(cpumask_var_t mask,
+                               unsigned int cpu, int index);
+#endif
 
 extern void detect_extended_topology(struct cpuinfo_x86 *c);
 extern void detect_ht(struct cpuinfo_x86 *c);
diff --git a/arch/x86/include/asm/unistd_32.h b/arch/x86/include/asm/unistd_32.h
index b766a5e8ba0e..b7ba19acd3f8 100644
--- a/arch/x86/include/asm/unistd_32.h
+++ b/arch/x86/include/asm/unistd_32.h
@@ -347,9 +347,13 @@
 #define __NR_fanotify_mark      339
 #define __NR_prlimit64          340
 
+#define __NR_LITMUS             341
+
+#include "litmus/unistd_32.h"
+
 #ifdef __KERNEL__
 
-#define NR_syscalls 341
+#define NR_syscalls 341 + NR_litmus_syscalls
 
 #define __ARCH_WANT_IPC_PARSE_VERSION
 #define __ARCH_WANT_OLD_READDIR
diff --git a/arch/x86/include/asm/unistd_64.h b/arch/x86/include/asm/unistd_64.h
index 363e9b8a715b..332bf3c9c84c 100644
--- a/arch/x86/include/asm/unistd_64.h
+++ b/arch/x86/include/asm/unistd_64.h
@@ -670,6 +670,10 @@ __SYSCALL(__NR_fanotify_mark, sys_fanotify_mark)
 #define __NR_prlimit64                          302
 __SYSCALL(__NR_prlimit64, sys_prlimit64)
 
+#define __NR_LITMUS                             303
+
+#include "litmus/unistd_64.h"
+
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR
 #define __ARCH_WANT_OLD_STAT
diff --git a/arch/x86/kernel/Makefile b/arch/x86/kernel/Makefile
index fedf32a8c3ec..6890dbb9ac15 100644
--- a/arch/x86/kernel/Makefile
+++ b/arch/x86/kernel/Makefile
@@ -118,6 +118,8 @@ obj-$(CONFIG_X86_CHECK_BIOS_CORRUPTION) += check.o
 
 obj-$(CONFIG_SWIOTLB)                   += pci-swiotlb.o
 
+obj-$(CONFIG_FEATHER_TRACE)     += ft_event.o
+
 ###
 # 64 bit specific files
 ifeq ($(CONFIG_X86_64),y)
diff --git a/arch/x86/kernel/cpu/intel_cacheinfo.c b/arch/x86/kernel/cpu/intel_cacheinfo.c
index 898c2f4eab88..3fec7d9bfd62 100644
--- a/arch/x86/kernel/cpu/intel_cacheinfo.c
+++ b/arch/x86/kernel/cpu/intel_cacheinfo.c
@@ -758,6 +758,23 @@ unsigned int __cpuinit init_intel_cacheinfo(struct cpuinfo_x86 *c)
 static DEFINE_PER_CPU(struct _cpuid4_info *, ici_cpuid4_info);
 #define CPUID4_INFO_IDX(x, y)   (&((per_cpu(ici_cpuid4_info, x))[y]))
 
+/* returns CPUs that share the index cache with cpu */
+int get_shared_cpu_map(cpumask_var_t mask, unsigned int cpu, int index)
+{
+        int ret = 0;
+        struct _cpuid4_info *this_leaf;
+
+        if (index >= num_cache_leaves) {
+                index = num_cache_leaves - 1;
+                ret = index;
+        }
+
+        this_leaf = CPUID4_INFO_IDX(cpu,index);
+        cpumask_copy(mask, to_cpumask(this_leaf->shared_cpu_map));
+
+        return ret;
+}
+
 #ifdef CONFIG_SMP
 static void __cpuinit cache_shared_cpu_map_setup(unsigned int cpu, int index)
 {
diff --git a/arch/x86/kernel/entry_64.S b/arch/x86/kernel/entry_64.S
index 17be5ec7cbba..115e8951e8c8 100644
--- a/arch/x86/kernel/entry_64.S
+++ b/arch/x86/kernel/entry_64.S
@@ -1016,6 +1016,8 @@ apicinterrupt CALL_FUNCTION_VECTOR \
         call_function_interrupt smp_call_function_interrupt
 apicinterrupt RESCHEDULE_VECTOR \
         reschedule_interrupt smp_reschedule_interrupt
+apicinterrupt PULL_TIMERS_VECTOR \
+        pull_timers_interrupt smp_pull_timers_interrupt
 #endif
 
 apicinterrupt ERROR_APIC_VECTOR \
diff --git a/arch/x86/kernel/ft_event.c b/arch/x86/kernel/ft_event.c
new file mode 100644
index 000000000000..37cc33252713
--- /dev/null
+++ b/arch/x86/kernel/ft_event.c
@@ -0,0 +1,118 @@
+#include <linux/types.h>
+
+#include <litmus/feather_trace.h>
+
+/* the feather trace management functions assume
+ * exclusive access to the event table
+ */
+
+#ifndef CONFIG_DEBUG_RODATA
+
+#define BYTE_JUMP      0xeb
+#define BYTE_JUMP_LEN  0x02
+
+/* for each event, there is an entry in the event table */
+struct trace_event {
+        long    id;
+        long    count;
+        long    start_addr;
+        long    end_addr;
+};
+
+extern struct trace_event  __start___event_table[];
+extern struct trace_event  __stop___event_table[];
+
+/* Workaround: if no events are defined, then the event_table section does not
+ * exist and the above references cause linker errors. This could probably be
+ * fixed by adjusting the linker script, but it is easier to maintain for us if
+ * we simply create a dummy symbol in the event table section.
+ */
+int __event_table_dummy[0] __attribute__ ((section("__event_table")));
+
+int ft_enable_event(unsigned long id)
+{
+        struct trace_event* te = __start___event_table;
+        int count = 0;
+        char* delta;
+        unsigned char* instr;
+
+        while (te < __stop___event_table) {
+                if (te->id == id && ++te->count == 1) {
+                        instr  = (unsigned char*) te->start_addr;
+                        /* make sure we don't clobber something wrong */
+                        if (*instr == BYTE_JUMP) {
+                                delta  = (((unsigned char*) te->start_addr) + 1);
+                                *delta = 0;
+                        }
+                }
+                if (te->id == id)
+                        count++;
+                te++;
+        }
+
+        printk(KERN_DEBUG "ft_enable_event: enabled %d events\n", count);
+        return count;
+}
+
+int ft_disable_event(unsigned long id)
+{
+        struct trace_event* te = __start___event_table;
+        int count = 0;
+        char* delta;
+        unsigned char* instr;
+
+        while (te < __stop___event_table) {
+                if (te->id == id && --te->count == 0) {
+                        instr  = (unsigned char*) te->start_addr;
+                        if (*instr == BYTE_JUMP) {
+                                delta  = (((unsigned char*) te->start_addr) + 1);
+                                *delta = te->end_addr - te->start_addr -
+                                        BYTE_JUMP_LEN;
+                        }
+                }
+                if (te->id == id)
+                        count++;
+                te++;
+        }
+
+        printk(KERN_DEBUG "ft_disable_event: disabled %d events\n", count);
+        return count;
+}
+
+int ft_disable_all_events(void)
+{
+        struct trace_event* te = __start___event_table;
+        int count = 0;
+        char* delta;
+        unsigned char* instr;
+
+        while (te < __stop___event_table) {
+                if (te->count) {
+                        instr  = (unsigned char*) te->start_addr;
+                        if (*instr == BYTE_JUMP) {
+                                delta  = (((unsigned char*) te->start_addr)
+                                          + 1);
+                                *delta = te->end_addr - te->start_addr -
+                                        BYTE_JUMP_LEN;
+                                te->count = 0;
+                                count++;
+                        }
+                }
+                te++;
+        }
+        return count;
+}
+
+int ft_is_event_enabled(unsigned long id)
+{
+        struct trace_event* te = __start___event_table;
+
+        while (te < __stop___event_table) {
+                if (te->id == id)
+                        return te->count;
+                te++;
+        }
+        return 0;
+}
+
+#endif
diff --git a/arch/x86/kernel/irqinit.c b/arch/x86/kernel/irqinit.c
index 990ae7cfc578..9772b1a0f9a4 100644
--- a/arch/x86/kernel/irqinit.c
+++ b/arch/x86/kernel/irqinit.c
@@ -189,6 +189,9 @@ static void __init smp_intr_init(void)
         alloc_intr_gate(CALL_FUNCTION_SINGLE_VECTOR,
                         call_function_single_interrupt);
 
+        /* IPI for hrtimer pulling on remote cpus */
+        alloc_intr_gate(PULL_TIMERS_VECTOR, pull_timers_interrupt);
+
         /* Low priority IPI to cleanup after moving an irq */
         set_intr_gate(IRQ_MOVE_CLEANUP_VECTOR, irq_move_cleanup_interrupt);
         set_bit(IRQ_MOVE_CLEANUP_VECTOR, used_vectors);
diff --git a/arch/x86/kernel/smp.c b/arch/x86/kernel/smp.c
index d801210945d6..74cca6014c0e 100644
--- a/arch/x86/kernel/smp.c
+++ b/arch/x86/kernel/smp.c
@@ -23,6 +23,10 @@
 #include <linux/cpu.h>
 #include <linux/gfp.h>
 
+#include <litmus/preempt.h>
+#include <litmus/debug_trace.h>
+#include <litmus/trace.h>
+
 #include <asm/mtrr.h>
 #include <asm/tlbflush.h>
 #include <asm/mmu_context.h>
@@ -118,6 +122,7 @@ static void native_smp_send_reschedule(int cpu)
                 WARN_ON(1);
                 return;
         }
+        TS_SEND_RESCHED_START(cpu);
         apic->send_IPI_mask(cpumask_of(cpu), RESCHEDULE_VECTOR);
 }
 
@@ -147,6 +152,16 @@ void native_send_call_func_ipi(const struct cpumask *mask)
         free_cpumask_var(allbutself);
 }
 
+/* trigger timers on remote cpu */
+void smp_send_pull_timers(int cpu)
+{
+        if (unlikely(cpu_is_offline(cpu))) {
+                WARN_ON(1);
+                return;
+        }
+        apic->send_IPI_mask(cpumask_of(cpu), PULL_TIMERS_VECTOR);
+}
+
 /*
  * this function calls the 'stop' function on all other CPUs in the system.
  */
@@ -198,7 +213,10 @@ static void native_smp_send_stop(void)
 void smp_reschedule_interrupt(struct pt_regs *regs)
 {
         ack_APIC_irq();
+        /* LITMUS^RT: this IPI might need to trigger the sched state machine. */
+        sched_state_ipi();
         inc_irq_stat(irq_resched_count);
+        TS_SEND_RESCHED_END;
         /*
          * KVM uses this interrupt to force a cpu out of guest mode
          */
@@ -222,6 +240,15 @@ void smp_call_function_single_interrupt(struct pt_regs *regs)
         irq_exit();
 }
 
+extern void hrtimer_pull(void);
+
+void smp_pull_timers_interrupt(struct pt_regs *regs)
+{
+        ack_APIC_irq();
+        TRACE("pull timer interrupt\n");
+        hrtimer_pull();
+}
+
 struct smp_ops smp_ops = {
         .smp_prepare_boot_cpu   = native_smp_prepare_boot_cpu,
         .smp_prepare_cpus       = native_smp_prepare_cpus,
diff --git a/arch/x86/kernel/syscall_table_32.S b/arch/x86/kernel/syscall_table_32.S
index b35786dc9b8f..37702905f658 100644
--- a/arch/x86/kernel/syscall_table_32.S
+++ b/arch/x86/kernel/syscall_table_32.S
@@ -340,3 +340,15 @@ ENTRY(sys_call_table)
         .long sys_fanotify_init
         .long sys_fanotify_mark
         .long sys_prlimit64             /* 340 */
+        .long sys_set_rt_task_param     /* LITMUS^RT 341 */
+        .long sys_get_rt_task_param
+        .long sys_complete_job
+        .long sys_od_open
+        .long sys_od_close
+        .long sys_litmus_lock
+        .long sys_litmus_unlock
+        .long sys_query_job_no
+        .long sys_wait_for_job_release
+        .long sys_wait_for_ts_release
+        .long sys_release_ts
+        .long sys_null_call