Re: [RFC PATCH 6/6] x86/jump_label,x86/alternatives: Batch jump label transformations

[Daniel Bristot de Oliveira]

On 10/10/18 10:17 PM, Steven Rostedt wrote:
> On Mon,  8 Oct 2018 14:53:05 +0200
> Daniel Bristot de Oliveira <bristot@xxxxxxxxxx> wrote:
> 
>> diff --git a/arch/x86/include/asm/jump_label.h b/arch/x86/include/asm/jump_label.h
>> index 8c0de4282659..d61c476046fe 100644
>> --- a/arch/x86/include/asm/jump_label.h
>> +++ b/arch/x86/include/asm/jump_label.h
>> @@ -15,6 +15,8 @@
>>  #error asm/jump_label.h included on a non-jump-label kernel
>>  #endif
>>  
>> +#define HAVE_JUMP_LABEL_BATCH
>> +
>>  #define JUMP_LABEL_NOP_SIZE 5
>>  
>>  #ifdef CONFIG_X86_64
>> diff --git a/arch/x86/include/asm/text-patching.h b/arch/x86/include/asm/text-patching.h
>> index e85ff65c43c3..a28230f09d72 100644
>> --- a/arch/x86/include/asm/text-patching.h
>> +++ b/arch/x86/include/asm/text-patching.h
>> @@ -18,6 +18,14 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
>>  #define __parainstructions_end	NULL
>>  #endif
>>  
>> +struct text_to_poke {
>> +	struct list_head list;
>> +	void *opcode;
>> +	void *addr;
>> +	void *handler;
>> +	size_t len;
>> +};
>> +
>>  extern void *text_poke_early(void *addr, const void *opcode, size_t len);
>>  
>>  /*
>> @@ -37,6 +45,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
>>  extern void *text_poke(void *addr, const void *opcode, size_t len);
>>  extern int poke_int3_handler(struct pt_regs *regs);
>>  extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
>> +extern void text_poke_bp_list(struct list_head *entry_list);
>>  extern int after_bootmem;
>>  
>>  #endif /* _ASM_X86_TEXT_PATCHING_H */
>> diff --git a/arch/x86/kernel/alternative.c b/arch/x86/kernel/alternative.c
>> index a4c83cb49cd0..3bd502ea4c53 100644
>> --- a/arch/x86/kernel/alternative.c
>> +++ b/arch/x86/kernel/alternative.c
>> @@ -735,9 +735,12 @@ static void do_sync_core(void *info)
>>  
>>  static bool bp_patching_in_progress;
>>  static void *bp_int3_handler, *bp_int3_addr;
>> +struct list_head *bp_list;
>>  
>>  int poke_int3_handler(struct pt_regs *regs)
>>  {
>> +	void *ip;
>> +	struct text_to_poke *tp;
>>  	/*
>>  	 * Having observed our INT3 instruction, we now must observe
>>  	 * bp_patching_in_progress.
>> @@ -753,21 +756,38 @@ int poke_int3_handler(struct pt_regs *regs)
>>  	if (likely(!bp_patching_in_progress))
>>  		return 0;
>>  
>> -	if (user_mode(regs) || regs->ip != (unsigned long)bp_int3_addr)
>> +	if (user_mode(regs))
>>  		return 0;
>>  
>> -	/* set up the specified breakpoint handler */
>> -	regs->ip = (unsigned long) bp_int3_handler;
>> +	/*
>> +	 * Single poke.
>> +	 */
>> +	if (bp_int3_addr) {
>> +		if (regs->ip == (unsigned long) bp_int3_addr) {
>> +			regs->ip = (unsigned long) bp_int3_handler;
>> +			return 1;
>> +		}
>> +		return 0;
>> +	}
>>  
>> -	return 1;
>> +	/*
>> +	 * Batch mode.
>> +	 */
>> +	ip = (void *) regs->ip - sizeof(unsigned char);
>> +	list_for_each_entry(tp, bp_list, list) {
>> +		if (ip == tp->addr) {
>> +			/* set up the specified breakpoint handler */
>> +			regs->ip = (unsigned long) tp->handler;
> 
> I hate this loop. Makes hitting the static branch (which is probably in
> a fast path, otherwise why use static branches?), do a O(n) loop of
> batch updates. You may not have that many, but why not optimize it?
> 
> Can we make an array of the handlers, in sorted order, then we simply
> do a binary search for the ip involved? Turning this from O(n) to
> O(log2(n)).
> 
> As Jason mentioned. If you set aside a page for processing batches up
> to PAGE / (sizeof tp) then you can also make it sorted and replace the
> iteration with a loop.

Hi Steven!

I am convinced! I am working in the v2 now, that will:

Split the batch mode into two patches (Jason)
Use an aside page rather than allocating memory (Jason)
Use a sorted vector of keys with binary search in the int3 handler (Steven)

I will also do some performance tests in the int3 handler (peterz on IRC).

Thanks!

-- Daniel