Add hrtimer_start_on() support

This patch adds hrtimer_start_on(), which allows arming timers on
remote CPUs.  This is needed to avoided timer interrupts on "shielded"
CPUs and is also useful for implementing semi-partitioned schedulers.

11 files changed, 191 insertions, 1 deletions

diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
index ce948d46a1b3..d3bfc3a4e56a 100644
--- a/arch/arm/Kconfig
+++ b/arch/arm/Kconfig
@@ -2123,5 +2123,8 @@ source "arch/arm/kvm/Kconfig"
 config ARCH_HAS_FEATHER_TRACE
         def_bool n
 
+config ARCH_HAS_SEND_PULL_TIMERS
+        def_bool n
+
 source "litmus/Kconfig"
 
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 6331227b4686..f9c9a4d70b24 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -2598,4 +2598,7 @@ 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 dc5fa661465f..e657219d7964 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_INTERRUPT3(irq_move_cleanup_interrupt, IRQ_MOVE_CLEANUP_VECTOR,
                  smp_irq_move_cleanup_interrupt)
 BUILD_INTERRUPT3(reboot_interrupt, REBOOT_VECTOR, smp_reboot_interrupt)
diff --git a/arch/x86/include/asm/hw_irq.h b/arch/x86/include/asm/hw_irq.h
index e9571ddabc4f..3e860d1f9416 100644
--- a/arch/x86/include/asm/hw_irq.h
+++ b/arch/x86/include/asm/hw_irq.h
@@ -77,6 +77,8 @@ extern asmlinkage void threshold_interrupt(void);
 extern asmlinkage void call_function_interrupt(void);
 extern asmlinkage void call_function_single_interrupt(void);
 
+extern asmlinkage void pull_timers_interrupt(void);
+
 #ifdef CONFIG_TRACING
 /* Interrupt handlers registered during init_IRQ */
 extern void trace_apic_timer_interrupt(void);
@@ -89,6 +91,7 @@ extern void trace_reschedule_interrupt(void);
 extern void trace_threshold_interrupt(void);
 extern void trace_call_function_interrupt(void);
 extern void trace_call_function_single_interrupt(void);
+extern void trace_pull_timers_interrupt(void);
 #define trace_irq_move_cleanup_interrupt  irq_move_cleanup_interrupt
 #define trace_reboot_interrupt  reboot_interrupt
 #define trace_kvm_posted_intr_ipi kvm_posted_intr_ipi
@@ -179,6 +182,7 @@ extern __visible void smp_reschedule_interrupt(struct pt_regs *);
 extern __visible void smp_call_function_interrupt(struct pt_regs *);
 extern __visible void smp_call_function_single_interrupt(struct pt_regs *);
 extern __visible void smp_invalidate_interrupt(struct pt_regs *);
+extern __visible void smp_pull_timers_interrupt(struct pt_regs *);
 #endif
 
 extern char irq_entries_start[];
diff --git a/arch/x86/include/asm/irq_vectors.h b/arch/x86/include/asm/irq_vectors.h
index 666c89ec4bd7..82545836e1a1 100644
--- a/arch/x86/include/asm/irq_vectors.h
+++ b/arch/x86/include/asm/irq_vectors.h
@@ -124,6 +124,12 @@
  */
 #define LOCAL_TIMER_VECTOR              0xef
 
+/*
+ * LITMUS^RT pull timers IRQ vector.
+ * Make sure it's not used by Linux.
+ */
+#define PULL_TIMERS_VECTOR              0xdf
+
 #define NR_VECTORS                       256
 
 #ifdef CONFIG_X86_LOCAL_APIC
diff --git a/arch/x86/kernel/entry_64.S b/arch/x86/kernel/entry_64.S
index 02c2eff7478d..d810f5fea04f 100644
--- a/arch/x86/kernel/entry_64.S
+++ b/arch/x86/kernel/entry_64.S
@@ -947,6 +947,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/irqinit.c b/arch/x86/kernel/irqinit.c
index cd10a6437264..834496ed9536 100644
--- a/arch/x86/kernel/irqinit.c
+++ b/arch/x86/kernel/irqinit.c
@@ -115,6 +115,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 be8e1bde07aa..7ce9fb210d55 100644
--- a/arch/x86/kernel/smp.c
+++ b/arch/x86/kernel/smp.c
@@ -24,6 +24,8 @@
 #include <linux/cpu.h>
 #include <linux/gfp.h>
 
+#include <litmus/debug_trace.h>
+
 #include <asm/mtrr.h>
 #include <asm/tlbflush.h>
 #include <asm/mmu_context.h>
@@ -164,6 +166,16 @@ static int smp_stop_nmi_callback(unsigned int val, struct pt_regs *regs)
         return NMI_HANDLED;
 }
 
+/* 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.
  */
@@ -216,7 +228,7 @@ static void native_stop_other_cpus(int wait)
                 while (num_online_cpus() > 1 && (wait || timeout--))
                         udelay(1);
         }
-        
+
         /* if the REBOOT_VECTOR didn't work, try with the NMI */
         if ((num_online_cpus() > 1) && (!smp_no_nmi_ipi))  {
                 if (register_nmi_handler(NMI_LOCAL, smp_stop_nmi_callback,
@@ -341,6 +353,30 @@ static int __init nonmi_ipi_setup(char *str)
 
 __setup("nonmi_ipi", nonmi_ipi_setup);
 
+extern void hrtimer_pull(void);
+
+static inline void __smp_pull_timers_interrupt(void)
+{
+        TRACE("pull timer interrupt\n");
+        hrtimer_pull();
+}
+
+__visible void smp_pull_timers_interrupt(struct pt_regs *regs)
+{
+        smp_entering_irq();
+        __smp_pull_timers_interrupt();
+        exiting_irq();
+}
+
+__visible void smp_trace_pull_timers_interrupt(struct pt_regs *regs)
+{
+        smp_entering_irq();
+        trace_call_function_single_entry(PULL_TIMERS_VECTOR);
+        __smp_pull_timers_interrupt();
+        trace_call_function_single_exit(PULL_TIMERS_VECTOR);
+        exiting_irq();
+}
+
 struct smp_ops smp_ops = {
         .smp_prepare_boot_cpu   = native_smp_prepare_boot_cpu,
         .smp_prepare_cpus       = native_smp_prepare_cpus,
diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h
index 05f6df1fdf5b..d1be5d2cb8fc 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -178,6 +178,7 @@ enum  hrtimer_base_type {
  * @nr_hangs:           Total number of hrtimer interrupt hangs
  * @max_hang_time:      Maximum time spent in hrtimer_interrupt
  * @clock_base:         array of clock bases for this cpu
+ * @to_pull:            LITMUS^RT list of timers to be pulled on this cpu
  */
 struct hrtimer_cpu_base {
         raw_spinlock_t                  lock;
@@ -195,8 +196,32 @@ struct hrtimer_cpu_base {
         ktime_t                         max_hang_time;
 #endif
         struct hrtimer_clock_base       clock_base[HRTIMER_MAX_CLOCK_BASES];
+        struct list_head                to_pull;
 };
 
+#ifdef CONFIG_ARCH_HAS_SEND_PULL_TIMERS
+
+#define HRTIMER_START_ON_INACTIVE       0
+#define HRTIMER_START_ON_QUEUED         1
+
+/*
+ * struct hrtimer_start_on_info - save timer info on remote cpu
+ * @list:       list of hrtimer_start_on_info on remote cpu (to_pull)
+ * @timer:      timer to be triggered on remote cpu
+ * @time:       time event
+ * @mode:       timer mode
+ * @state:      activity flag
+ */
+struct hrtimer_start_on_info {
+        struct list_head        list;
+        struct hrtimer          *timer;
+        ktime_t                 time;
+        enum hrtimer_mode       mode;
+        atomic_t                state;
+};
+
+#endif
+
 static inline void hrtimer_set_expires(struct hrtimer *timer, ktime_t time)
 {
         timer->node.expires = time;
@@ -362,6 +387,13 @@ __hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim,
                          unsigned long delta_ns,
                          const enum hrtimer_mode mode, int wakeup);
 
+#ifdef CONFIG_ARCH_HAS_SEND_PULL_TIMERS
+extern void hrtimer_start_on_info_init(struct hrtimer_start_on_info *info);
+extern int hrtimer_start_on(int cpu, struct hrtimer_start_on_info *info,
+                        struct hrtimer *timer, ktime_t time,
+                        const enum hrtimer_mode mode);
+#endif
+
 extern int hrtimer_cancel(struct hrtimer *timer);
 extern int hrtimer_try_to_cancel(struct hrtimer *timer);
 
diff --git a/include/linux/smp.h b/include/linux/smp.h
index c4414074bd88..dfc63fe33a63 100644
--- a/include/linux/smp.h
+++ b/include/linux/smp.h
@@ -103,6 +103,11 @@ void kick_all_cpus_sync(void);
 void wake_up_all_idle_cpus(void);
 
 /*
+ * sends a 'pull timer' event to a remote CPU
+ */
+extern void smp_send_pull_timers(int cpu);
+
+/*
  * Generic and arch helpers
  */
 void __init call_function_init(void);
diff --git a/kernel/time/hrtimer.c b/kernel/time/hrtimer.c
index 93ef7190bdea..22f9156f19d2 100644
--- a/kernel/time/hrtimer.c
+++ b/kernel/time/hrtimer.c
@@ -50,6 +50,8 @@
 #include <linux/timer.h>
 #include <linux/freezer.h>
 
+#include <litmus/debug_trace.h>
+
 #include <asm/uaccess.h>
 
 #include <trace/events/timer.h>
@@ -1045,6 +1047,98 @@ hrtimer_start(struct hrtimer *timer, ktime_t tim, const enum hrtimer_mode mode)
 }
 EXPORT_SYMBOL_GPL(hrtimer_start);
 
+#if defined(CONFIG_ARCH_HAS_SEND_PULL_TIMERS) && defined(CONFIG_SMP)
+
+/**
+ * hrtimer_start_on_info_init - Initialize hrtimer_start_on_info
+ */
+void hrtimer_start_on_info_init(struct hrtimer_start_on_info *info)
+{
+        memset(info, 0, sizeof(struct hrtimer_start_on_info));
+        atomic_set(&info->state, HRTIMER_START_ON_INACTIVE);
+}
+
+/**
+ *  hrtimer_pull - PULL_TIMERS_VECTOR callback on remote cpu
+ */
+void hrtimer_pull(void)
+{
+        struct hrtimer_cpu_base *base = this_cpu_ptr(&hrtimer_bases);
+        struct hrtimer_start_on_info *info;
+        struct list_head *pos, *safe, list;
+
+        raw_spin_lock(&base->lock);
+        list_replace_init(&base->to_pull, &list);
+        raw_spin_unlock(&base->lock);
+
+        list_for_each_safe(pos, safe, &list) {
+                info = list_entry(pos, struct hrtimer_start_on_info, list);
+                TRACE("pulled timer 0x%x\n", info->timer);
+                list_del(pos);
+                hrtimer_start(info->timer, info->time, info->mode);
+        }
+}
+
+/**
+ *  hrtimer_start_on - trigger timer arming on remote cpu
+ *  @cpu:       remote cpu
+ *  @info:      save timer information for enqueuing on remote cpu
+ *  @timer:     timer to be pulled
+ *  @time:      expire time
+ *  @mode:      timer mode
+ */
+int hrtimer_start_on(int cpu, struct hrtimer_start_on_info* info,
+                struct hrtimer *timer, ktime_t time,
+                const enum hrtimer_mode mode)
+{
+        unsigned long flags;
+        struct hrtimer_cpu_base* base;
+        int in_use = 0, was_empty;
+
+        /* serialize access to info through the timer base */
+        lock_hrtimer_base(timer, &flags);
+
+        in_use = (atomic_read(&info->state) != HRTIMER_START_ON_INACTIVE);
+        if (!in_use) {
+                INIT_LIST_HEAD(&info->list);
+                info->timer = timer;
+                info->time  = time;
+                info->mode  = mode;
+                /* mark as in use */
+                atomic_set(&info->state, HRTIMER_START_ON_QUEUED);
+        }
+
+        unlock_hrtimer_base(timer, &flags);
+
+        if (!in_use) {
+                /* initiate pull  */
+                preempt_disable();
+                if (cpu == smp_processor_id()) {
+                        /* start timer locally; we may get called
+                         * with rq->lock held, do not wake up anything
+                         */
+                        TRACE("hrtimer_start_on: starting on local CPU\n");
+                        __hrtimer_start_range_ns(info->timer, info->time,
+                                                 0, info->mode, 0);
+                } else {
+                        TRACE("hrtimer_start_on: pulling to remote CPU\n");
+                        base = &per_cpu(hrtimer_bases, cpu);
+                        raw_spin_lock_irqsave(&base->lock, flags);
+                        was_empty = list_empty(&base->to_pull);
+                        list_add(&info->list, &base->to_pull);
+                        raw_spin_unlock_irqrestore(&base->lock, flags);
+                        if (was_empty)
+                                /* only send IPI if other no else
+                                 * has done so already
+                                 */
+                                smp_send_pull_timers(cpu);
+                }
+                preempt_enable();
+        }
+        return in_use;
+}
+
+#endif
 
 /**
  * hrtimer_try_to_cancel - try to deactivate a timer
@@ -1626,6 +1720,7 @@ static void init_hrtimers_cpu(int cpu)
 
         cpu_base->cpu = cpu;
         hrtimer_init_hres(cpu_base);
+        INIT_LIST_HEAD(&cpu_base->to_pull);
 }
 
 #ifdef CONFIG_HOTPLUG_CPU