• Daniel Bristot de Oliveira's avatar
    x86/alternative: Batch of patch operations · c0213b0a
    Daniel Bristot de Oliveira authored
    
    
    Currently, the patch of an address is done in three steps:
    
    -- Pseudo-code #1 - Current implementation ---
    
            1) add an int3 trap to the address that will be patched
                sync cores (send IPI to all other CPUs)
            2) update all but the first byte of the patched range
                sync cores (send IPI to all other CPUs)
            3) replace the first byte (int3) by the first byte of replacing opcode
                sync cores (send IPI to all other CPUs)
    
    -- Pseudo-code #1 ---
    
    When a static key has more than one entry, these steps are called once for
    each entry. The number of IPIs then is linear with regard to the number 'n' of
    entries of a key: O(n*3), which is O(n).
    
    This algorithm works fine for the update of a single key. But we think
    it is possible to optimize the case in which a static key has more than
    one entry. For instance, the sched_schedstats jump label has 56 entries
    in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in
    which the thread that is enabling the key is _not_ running.
    
    With this patch, rather than receiving a single patch to be processed, a vector
    of patches is passed, enabling the rewrite of the pseudo-code #1 in this
    way:
    
    -- Pseudo-code #2 - This patch  ---
    1)  for each patch in the vector:
            add an int3 trap to the address that will be patched
    
        sync cores (send IPI to all other CPUs)
    
    2)  for each patch in the vector:
            update all but the first byte of the patched range
    
        sync cores (send IPI to all other CPUs)
    
    3)  for each patch in the vector:
            replace the first byte (int3) by the first byte of replacing opcode
    
        sync cores (send IPI to all other CPUs)
    -- Pseudo-code #2 - This patch  ---
    
    Doing the update in this way, the number of IPI becomes O(3) with regard
    to the number of keys, which is O(1).
    
    The batch mode is done with the function text_poke_bp_batch(), that receives
    two arguments: a vector of "struct text_to_poke", and the number of entries
    in the vector.
    
    The vector must be sorted by the addr field of the text_to_poke structure,
    enabling the binary search of a handler in the poke_int3_handler function
    (a fast path).
    
    Signed-off-by: default avatarDaniel Bristot de Oliveira <bristot@redhat.com>
    Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Reviewed-by: default avatarMasami Hiramatsu <mhiramat@kernel.org>
    Cc: Borislav Petkov <bp@alien8.de>
    Cc: Chris von Recklinghausen <crecklin@redhat.com>
    Cc: Clark Williams <williams@redhat.com>
    Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
    Cc: H. Peter Anvin <hpa@zytor.com>
    Cc: Jason Baron <jbaron@akamai.com>
    Cc: Jiri Kosina <jkosina@suse.cz>
    Cc: Josh Poimboeuf <jpoimboe@redhat.com>
    Cc: Linus Torvalds <torvalds@linux-foundation.org>
    Cc: Marcelo Tosatti <mtosatti@redhat.com>
    Cc: Peter Zijlstra <peterz@infradead.org>
    Cc: Scott Wood <swood@redhat.com>
    Cc: Steven Rostedt (VMware) <rostedt@goodmis.org>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Link: https://lkml.kernel.org/r/ca506ed52584c80f64de23f6f55ca288e5d079de.1560325897.git.bristot@redhat.com
    
    
    Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
    c0213b0a