sched: IPI only if wakeup causes a context switch

Send an IPI only if we estimate a wakeup to cause a context switch.

Avi Kivity explains:

  We could go much further by estimating whether the wakeup will cause a
  context switch.

  We already have cpu::running_since that tells us how long the current thread
  has been running.  We could also store its vruntime, and a waker can then
  check whether it will preempt the running thread or not.  If not, then just
  skip the IPI.

IPIs are reduced by 59% for one cassandra-stress INSERT run:

Before:

[penberg@server ~]$ sudo perf kvm stat -e kvm:* -p `pidof qemu-system-x86_64`
^C
 Performance counter stats for process id '20319':

         7,049,352 kvm:kvm_entry
                 0 kvm:kvm_hypercall
                 0 kvm:kvm_hv_hypercall
         1,302,778 kvm:kvm_pio
                 0 kvm:kvm_cpuid
         5,098,352 kvm:kvm_apic
         7,049,475 kvm:kvm_exit
         2,467,064 kvm:kvm_inj_virq
                 0 kvm:kvm_inj_exception
                 0 kvm:kvm_page_fault
         2,794,658 kvm:kvm_msr
                 0 kvm:kvm_cr
            22,372 kvm:kvm_pic_set_irq
         2,303,702 kvm:kvm_apic_ipi
         2,431,100 kvm:kvm_apic_accept_irq
         2,458,786 kvm:kvm_eoi
         2,419,966 kvm:kvm_pv_eoi
                 0 kvm:kvm_nested_vmrun
                 0 kvm:kvm_nested_intercepts
                 0 kvm:kvm_nested_vmexit
                 0 kvm:kvm_nested_vmexit_inject
                 0 kvm:kvm_nested_intr_vmexit
                 0 kvm:kvm_invlpga
                 0 kvm:kvm_skinit
            11,186 kvm:kvm_emulate_insn
                 0 kvm:vcpu_match_mmio
                 0 kvm:kvm_update_master_clock
                 0 kvm:kvm_track_tsc
            22,372 kvm:kvm_userspace_exit
            22,372 kvm:kvm_set_irq
            22,372 kvm:kvm_ioapic_set_irq
             3,925 kvm:kvm_msi_set_irq
                 0 kvm:kvm_ack_irq
                 0 kvm:kvm_mmio
            55,881 kvm:kvm_fpu
                 0 kvm:kvm_age_page
                 0 kvm:kvm_try_async_get_page
                 0 kvm:kvm_async_pf_doublefault
                 0 kvm:kvm_async_pf_not_present
                 0 kvm:kvm_async_pf_ready
                 0 kvm:kvm_async_pf_completed

      68.506411994 seconds time elapsed

After:

[penberg@server ~]$ sudo perf kvm stat -e kvm:* -p `pidof qemu-system-x86_64`
^C
 Performance counter stats for process id '14378':

         4,057,973 kvm:kvm_entry
                 0 kvm:kvm_hypercall
                 0 kvm:kvm_hv_hypercall
         1,169,278 kvm:kvm_pio
                 0 kvm:kvm_cpuid
         2,206,428 kvm:kvm_apic
         4,057,973 kvm:kvm_exit
         1,071,588 kvm:kvm_inj_virq
                 0 kvm:kvm_inj_exception
                 0 kvm:kvm_page_fault
         1,273,348 kvm:kvm_msr
                 0 kvm:kvm_cr
            21,534 kvm:kvm_pic_set_irq
           933,088 kvm:kvm_apic_ipi
         1,024,688 kvm:kvm_apic_accept_irq
         1,069,092 kvm:kvm_eoi
         1,054,991 kvm:kvm_pv_eoi
                 0 kvm:kvm_nested_vmrun
                 0 kvm:kvm_nested_intercepts
                 0 kvm:kvm_nested_vmexit
                 0 kvm:kvm_nested_vmexit_inject
                 0 kvm:kvm_nested_intr_vmexit
                 0 kvm:kvm_invlpga
                 0 kvm:kvm_skinit
            10,767 kvm:kvm_emulate_insn
                 0 kvm:vcpu_match_mmio
                 0 kvm:kvm_update_master_clock
                 0 kvm:kvm_track_tsc
            21,534 kvm:kvm_userspace_exit
            21,534 kvm:kvm_set_irq
            21,534 kvm:kvm_ioapic_set_irq
             3,356 kvm:kvm_msi_set_irq
                 0 kvm:kvm_ack_irq
                 0 kvm:kvm_mmio
            74,064 kvm:kvm_fpu
                 0 kvm:kvm_age_page
                 0 kvm:kvm_try_async_get_page
                 0 kvm:kvm_async_pf_doublefault
                 0 kvm:kvm_async_pf_not_present
                 0 kvm:kvm_async_pf_ready
                 0 kvm:kvm_async_pf_completed

      62.192225493 seconds time elapsed

Cassandra READ operations are improved by roughly 10%:

Before:

  [penberg@haswell apache-cassandra-1.2.6]$ ./tools/bin/cassandra-stress -d 192.168.1.89 -o READ
  total,interval_op_rate,interval_key_rate,latency/95th/99th,elapsed_time
  50280,5028,5028,7.6,21.7,160.9,10
  197037,14675,14675,3.0,11.8,63.1,20
  426171,22913,22913,2.3,8.1,52.0,30
  664712,23854,23854,2.2,6.9,39.7,40
  906489,24177,24177,2.1,6.1,39.7,50
  1000000,9351,9351,2.1,5.9,39.7,54
  END
  [penberg@haswell apache-cassandra-1.2.6]$ ./tools/bin/cassandra-stress -d 192.168.1.89 -o READ
  total,interval_op_rate,interval_key_rate,latency/95th/99th,elapsed_time
  229066,22906,22906,2.1,3.2,18.4,10
  460920,23185,23185,2.2,3.1,12.8,20
  690494,22957,22957,2.1,3.1,19.5,30
  947794,25730,25730,2.0,3.0,19.2,40
  1000000,5220,5220,2.0,2.9,19.1,42
  END
  [penberg@haswell apache-cassandra-1.2.6]$ ./tools/bin/cassandra-stress -d 192.168.1.89 -o READ
  total,interval_op_rate,interval_key_rate,latency/95th/99th,elapsed_time
  232108,23210,23210,2.1,3.0,28.5,10
  477234,24512,24512,2.1,2.9,19.4,20
  712239,23500,23500,2.1,3.0,19.1,30
  941734,22949,22949,2.2,3.0,9.9,40
  1000000,5826,5826,2.1,3.0,9.9,43

After:

  [penberg@haswell apache-cassandra-1.2.6]$ ./tools/bin/cassandra-stress -d 192.168.1.89 -o READ
  total,interval_op_rate,interval_key_rate,latency/95th/99th,elapsed_time
  83443,8344,8344,4.8,11.4,135.4,10
  331745,24830,24830,1.8,7.2,61.7,20
  589096,25735,25735,1.7,4.8,61.1,30
  844364,25526,25526,1.8,3.8,23.3,40
  1000000,15563,15563,1.8,3.6,23.3,46
  END
  [penberg@haswell apache-cassandra-1.2.6]$ ./tools/bin/cassandra-stress -d 192.168.1.89 -o READ
  total,interval_op_rate,interval_key_rate,latency/95th/99th,elapsed_time
  254125,25412,25412,1.9,2.6,121.5,10
  498788,24466,24466,1.9,2.6,35.7,20
  784109,28532,28532,1.8,2.5,35.7,30
  1000000,21589,21589,1.8,2.4,35.7,38
  END
  [penberg@haswell apache-cassandra-1.2.6]$ ./tools/bin/cassandra-stress -d 192.168.1.89 -o READ
  total,interval_op_rate,interval_key_rate,latency/95th/99th,elapsed_time
  255483,25548,25548,1.9,2.6,38.6,10
  501079,24559,24559,1.9,2.5,6.2,20
  766858,26577,26577,1.9,2.5,16.2,30
  1000000,23314,23314,1.9,2.5,39.4,39
  END