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, 176 insertions, 0 deletions

diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
index 4f412167b95d..411536b9c975 100644
--- a/arch/arm/Kconfig
+++ b/arch/arm/Kconfig
@@ -2249,5 +2249,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 171cdc9cc5db..b0695266a4cb 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -2350,4 +2350,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 9bd4ecac72be..3a3c2f1ac1c4 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)
 #endif
diff --git a/arch/x86/include/asm/hw_irq.h b/arch/x86/include/asm/hw_irq.h
index 1da97efad08a..672de9367d27 100644
--- a/arch/x86/include/asm/hw_irq.h
+++ b/arch/x86/include/asm/hw_irq.h
@@ -77,6 +77,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;
@@ -166,6 +168,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 5702d7e3111d..224116be0e22 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
 
 #define FPU_IRQ                           13
diff --git a/arch/x86/kernel/entry_64.S b/arch/x86/kernel/entry_64.S
index 727208941030..a48b3ea137cd 100644
--- a/arch/x86/kernel/entry_64.S
+++ b/arch/x86/kernel/entry_64.S
@@ -1183,6 +1183,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 a2a1fbc594ff..77979d9bd90d 100644
--- a/arch/x86/kernel/irqinit.c
+++ b/arch/x86/kernel/irqinit.c
@@ -145,6 +145,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 48d2b7ded422..a52ef7fd6862 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>
@@ -163,6 +165,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.
  */
@@ -285,6 +297,17 @@ static int __init nonmi_ipi_setup(char *str)
 
 __setup("nonmi_ipi", nonmi_ipi_setup);
 
+extern void hrtimer_pull(void);
+
+void smp_pull_timers_interrupt(struct pt_regs *regs)
+{
+        ack_APIC_irq();
+        irq_enter();
+        TRACE("pull timer interrupt\n");
+        hrtimer_pull();
+        irq_exit();
+}
+
 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 d19a5c2d2270..93def50764dd 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -176,6 +176,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;
@@ -191,8 +192,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;
@@ -366,6 +391,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 c8488763277f..4f78ea77662c 100644
--- a/include/linux/smp.h
+++ b/include/linux/smp.h
@@ -84,6 +84,11 @@ int smp_call_function_any(const struct cpumask *mask,
 void kick_all_cpus_sync(void);
 
 /*
+ * sends a 'pull timer' event to a remote CPU
+ */
+extern void smp_send_pull_timers(int cpu);
+
+/*
  * Generic and arch helpers
  */
 #ifdef CONFIG_USE_GENERIC_SMP_HELPERS
diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index 2288fbdada16..c7f0c79b2cb5 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -48,6 +48,8 @@
 #include <linux/sched/rt.h>
 #include <linux/timer.h>
 
+#include <litmus/debug_trace.h>
+
 #include <asm/uaccess.h>
 
 #include <trace/events/timer.h>
@@ -1064,6 +1066,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 = &__get_cpu_var(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
@@ -1667,6 +1761,7 @@ static void __cpuinit init_hrtimers_cpu(int cpu)
         }
 
         hrtimer_init_hres(cpu_base);
+        INIT_LIST_HEAD(&cpu_base->to_pull);
 }
 
 #ifdef CONFIG_HOTPLUG_CPU