Parallelize BTF type info generating of pahole
cover Parallelize BTF type info generating of pahole
Creating an instance of btf for each worker thread allows steal-function provided by pahole to add type info on multiple threads without a lock. The main thread merges the results of worker threads to the primary instance.
Copying data from per-thread btf instances to the primary instance is expensive now. However, there is a patch landed at the bpf-next repository. [1] With the patch for bpf-next and this patch, they drop total runtime to 5.4s from 6.0s with "-j4" on my device to generate BTF for Linux.
[1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/commit/?id=d81283d27266
Kui-Feng Lee (2):
dwarf_loader: Prepare and pass per-thread data to worker threads.
pahole: Use per-thread btf instances to avoid mutex locking.
btf_encoder.c | 5 +++ btf_encoder.h | 2 + btf_loader.c | 2 +- ctf_loader.c | 2 +- dwarf_loader.c | 58 ++++++++++++++++++------ dwarves.h | 9 +++- pahole.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++--- pdwtags.c | 3 +- pfunct.c | 4 +- 9 files changed, 180 insertions(+), 25 deletions(-)
Signature · 1 line
2.30.2
PATCH 1/2 dwarf_loader: Prepare and pass per-thread data to worker threads.
Add interfaces to allow users of dwarf_loader to prepare and pass per-thread data to steal-functions running on worker threads.
--- btf_loader.c | 2 +- ctf_loader.c | 2 +- dwarf_loader.c | 58 +++++++++++++++++++++++++++++++++++++++----------- dwarves.h | 9 ++++++-- pahole.c | 3 ++- pdwtags.c | 3 ++- pfunct.c | 4 +++- 7 files changed, 61 insertions(+), 20 deletions(-)
btf_loader.c +1 -1
@@ -624,7 +624,7 @@ static int cus__load_btf(struct cus *cus, struct conf_load *conf, const char *fi* The app stole this cu, possibly deleting it, * so forget about it */ -if (conf && conf->steal && conf->steal (cu, conf)) +if (conf && conf->steal && conf->steal (cu, conf,NULL ))return 0 ;cus__add (cus, cu);
ctf_loader.c +1 -1
@@ -722,7 +722,7 @@ int ctf__load_file(struct cus *cus, struct conf_load *conf,* The app stole this cu, possibly deleting it, * so forget about it */ -if (conf && conf->steal && conf->steal (cu, conf)) +if (conf && conf->steal && conf->steal (cu, conf,NULL ))return 0 ;cus__add (cus, cu);
dwarf_loader.c +45 -13
132 lines not on this page · raw message
dwarves.h +7 -2
@@ -48,8 +48,9 @@ struct conf_fprintf;*/ struct conf_load {enum load_steal_kind (*steal)(struct cu *cu, -struct conf_load *conf); -int (*thread_exit)(void ); +struct conf_load *conf, +void *thr_data); +int (*thread_exit)(struct conf_load *conf,void *thr_data);void *cookie;char *format_path;int nr_jobs;
@@ -70,6 +71,10 @@ struct conf_load {const char *kabi_prefix;struct btf *base_btf;struct conf_fprintf *conf_fprintf; +int (*threads_prepare)(struct conf_load *conf,int nr_threads, +void **thr_data); +int (*threads_collect)(struct conf_load *conf,int nr_threads, +void **thr_data,int error); };/** struct conf_fprintf - hints to the __fprintf routines
pahole.c +2 -1
@@ -2799,7 +2799,8 @@ out:static struct type_instance *header;static enum load_steal_kind pahole_stealer (struct cu *cu, -struct conf_load *conf_load) +struct conf_load *conf_load, +void *thr_data) {int ret =LSK__DELETE ;
pdwtags.c +2 -1
@@ -72,7 +72,8 @@ static int cu__emit_tags(struct cu *cu) }static enum load_steal_kind pdwtags_stealer (struct cu *cu, -struct conf_load *conf_load__maybe_unused ) +struct conf_load *conf_load__maybe_unused , +void *thr_data__maybe_unused ) {cu__emit_tags (cu);return LSK__DELETE ;
pfunct.c +3 -1
@@ -489,7 +489,9 @@ int elf_symtabs__show(char *filenames[])return EXIT_SUCCESS ; } -static enum load_steal_kind pfunct_stealer (struct cu *cu,struct conf_load *conf_load__maybe_unused ) +static enum load_steal_kind pfunct_stealer (struct cu *cu, +struct conf_load *conf_load__maybe_unused , +void *thr_data__maybe_unused ) {if (function_name) {
Signature · 1 line
2.30.2
PATCH 2/2 pahole: Use per-thread btf instances to avoid mutex locking.
In reply to Kui-Feng LeeCreate an instance of btf for each worker thread, and add type info to the local btf instance in the steal-function of pahole without mutex acquiring. Once finished with all worker threads, merge all per-thread btf instances to the primary btf instance.
--- btf_encoder.c | 5 +++ btf_encoder.h | 2 + pahole.c | 117 +++++++++++++++++++++++++++++++++++++++++++++++--- 3 files changed, 119 insertions(+), 5 deletions(-)
btf_encoder.c +5 -0
@@ -1529,3 +1529,8 @@ int btf_encoder__encode_cu(struct btf_encoder *encoder, struct cu *cu) out:return err; } + +struct btf *btf_encoder__get_btf (struct btf_encoder *encoder) +{ +return encoder->btf; +}
btf_encoder.h +2 -0
@@ -29,4 +29,6 @@ struct btf_encoder *btf_encoders__first(struct list_head *encoders);struct btf_encoder *btf_encoders__next (struct btf_encoder *encoder); +struct btf *btf_encoder__get_btf (struct btf_encoder *encoder); +#endif /* _BTF_ENCODER_H_ */
pahole.c +112 -5
153 lines not on this page · raw message
Signature · 1 line
2.30.2
Re: [PATCH dwarves 2/2] pahole: Use per-thread btf instances to avoid mutex locking.
Quoted 8 lines · Kui-Feng Lee
Create an instance of btf for each worker thread, and add type info to the local btf instance in the steal-function of pahole without mutex acquiring. Once finished with all worker threads, merge all per-thread btf instances to the primary btf instance.
Signed-off-by Kui-Feng Lee <[email protected]>---
Just a bunch of nits, I'll relay to Arnaldo to verify the logic is sound
Quoted 10 lines
btf_encoder.c | 5 +++ btf_encoder.h | 2 + pahole.c | 117 +++++++++++++++++++++++++++++++++++++++++++++++--- 3 files changed, 119 insertions(+), 5 deletions(-)btf_encoder.c +0
-0
btf_encoder.c int btf_encoder__encode_cu(struct btf_encoder *encoder, struct cu *cu) · line 1533
Quoted 5 lines
btf_encoder.c +2
-0@@ -1529,3 +1529,8 @@ int btf_encoder__encode_cu(struct btf_encoder *encoder, struct cu *cu) out:return err; } + +struct btf *btf_encoder__get_btf (struct btf_encoder *encoder)
nit: btf_encoder__btf() is how we'd call this in libbpf, not sure which naming convention Arnaldo prefers
Quoted 22 lines
btf_encoder.c +3
-0+{ +return encoder->btf; +}btf_encoder.h +2
-0@@ -29,4 +29,6 @@ struct btf_encoder *btf_encoders__first(struct list_head *encoders);struct btf_encoder *btf_encoders__next (struct btf_encoder *encoder); +struct btf *btf_encoder__get_btf (struct btf_encoder *encoder); +#endif /* _BTF_ENCODER_H_ */ pahole.c +0
-0@@ -2798,6 +2798,73 @@ out:static struct type_instance *header;
pahole.c out: · line 2810
Quoted 10 lines
pahole.c +10
-0+struct thread_data { +struct btf *btf; +struct btf_encoder *encoder; +}; + +static int pahole_threads_prepare (struct conf_load *conf,int nr_threads,void **thr_data) +{ +int i; +struct thread_data *threads = + (struct thread_data *)calloc (sizeof (struct thread_data ), nr_threads);
nit: split variable declaration and initialization, if it's not fitting on a single line? You also don't need casting of calloc() result in C.
pahole.c out: · line 2820
Quoted 10 lines
pahole.c +10
-0+ +for (i =0 ; i < nr_threads; i++) + thr_data[i] = threads + i; + +return 0 ; +} + +static int pahole_thread_exit (struct conf_load *conf,void *thr_data) +{ +struct thread_data *thread = (struct thread_data *)thr_data;
same, casting not needed
pahole.c out: · line 2822
Quoted 2 lines
pahole.c +2
-0+ +if (thread ==NULL )
nit: !thread
pahole.c out: · line 2828
Quoted 6 lines
pahole.c +6
-0+return 0 ; + +/* +* It will call dedup here in the future once we have fixed +* the known performance regression of libbpf. +*/
uhm... it's not a regression, it's BTF dedup algorithm not really supporting partial dedup and subsequent dedup. I'd drop this comment for now, it just adds confusion, IMO.
pahole.c out: · line 2840
Quoted 12 lines
pahole.c +12
-0+ +return 0 ; +} + +static int pahole_threads_collect (struct conf_load *conf,int nr_threads,void **thr_data, +int error) +{ +struct thread_data **threads = (struct thread_data **)thr_data; +int i; +int err =0 ; + +if (error ==0 ) {
reduce nesting:
if (error)
goto out;
pahole.c out: · line 2843
Quoted 3 lines
pahole.c +3
-0+for (i =0 ; i < nr_threads; i++) { +/* +* Merge cotnent of the btf instances of
typo: content
pahole.c out: · line 2849
Quoted 6 lines
pahole.c +6
-0+* worker threads to the btf instance of the +* primary btf_encoder. +*/ +if (!threads[i]->btf || threads[i]->encoder == btf_encoder) +continue ;/* The primary btf_encoder */ + err =btf__add_btf (btf_encoder__get_btf (btf_encoder), threads[i]->btf);
if you do btf__add_btf() in pahole_thread_exit() (under mutex, but that's fine), you can offload some time spent in btf__Add_btf() to worker threads. Have you tried that? I bet you'll get a bit of speed up that way as well.
pahole.c out: · line 2852
Quoted 3 lines
pahole.c +3
-0+if (err <0 ) + goto out; + err =0 ;
move this to after the for loop
Quoted 29 lines
pahole.c +16
-1+btf_encoder__delete (threads[i]->encoder); + threads[i]->encoder =NULL ; + } + } + +out: +for (i =0 ; i < nr_threads; i++) { +if (threads[i]->encoder && threads[i]->encoder != btf_encoder) +btf_encoder__delete (threads[i]->encoder); + } +free (threads[0 ]); + +return err; +} +static enum load_steal_kind pahole_stealer (struct cu *cu,struct conf_load *conf_load,void *thr_data)@@ -2819,8 +2886,8 @@ static enum load_steal_kind pahole_stealer(struct cu *cu,if (btf_encode) {static pthread_mutex_t btf_lock =PTHREAD_MUTEX_INITIALIZER ; +struct btf_encoder *encoder; -pthread_mutex_lock (&btf_lock);/* * FIXME: *
pahole.c static enum load_steal_kind pahole_stealer(struct cu *cu, · line 2898
Quoted 6 lines
pahole.c +1
-2@@ -2828,21 +2895,58 @@ static enum load_steal_kind pahole_stealer(struct cu *cu,* point we'll have cu->elf setup... */ if (!btf_encoder) { - btf_encoder =btf_encoder__new (cu, detached_btf_filename, conf_load->base_btf, skip_encoding_btf_vars, - btf_encode_force, btf_gen_floats, global_verbose); +int new_btf_encoder =0 ;
this is boolean variable, use bool
Quoted 15 lines
pahole.c +15
-0+ +pthread_mutex_lock (&btf_lock); +if (!btf_encoder) { +/* +* btf_encoder is the primary encoder. +* And, it is used by the thread +* create it. +*/ + btf_encoder =btf_encoder__new (cu, detached_btf_filename, + conf_load->base_btf, + skip_encoding_btf_vars, + btf_encode_force, + btf_gen_floats, global_verbose); + new_btf_encoder =1 ; + }
pahole.c static enum load_steal_kind pahole_stealer(struct cu *cu, · line 2923
Quoted 10 lines
pahole.c +6
-0+pthread_mutex_unlock (&btf_lock);if (btf_encoder ==NULL ) { ret =LSK__STOP_LOADING ; goto out_btf; } +if (new_btf_encoder && thr_data) { +struct thread_data *thread = (struct thread_data *)thr_data; + + thread->encoder = btf_encoder; + thread->btf =btf_encoder__get_btf (btf_encoder);
maybe do this initialization right after you created btf_encode above (under lock is fine, there is nothing slow here)
Quoted 44 lines
pahole.c +22
-3+ } } -if (btf_encoder__encode_cu (btf_encoder, cu)) { +if (thr_data) { +struct thread_data *thread = (struct thread_data *)thr_data; + +if (thread->encoder ==NULL ) { + thread->encoder = +btf_encoder__new (cu, detached_btf_filename, +NULL , + skip_encoding_btf_vars, + btf_encode_force, + btf_gen_floats, + global_verbose); + thread->btf =btf_encoder__get_btf (thread->encoder); + } + encoder = thread->encoder; + }else + encoder = btf_encoder; + +if (btf_encoder__encode_cu (encoder, cu)) {fprintf (stderr,"Encountered error while encoding BTF.\n" );exit (1 ); } ret =LSK__DELETE ; out_btf: -pthread_mutex_unlock (&btf_lock);return ret; }#if 0 @@ -3207,6 +3311,9 @@ int main(int argc, char *argv[])memset (tab,' ' ,sizeof (tab) -1 ); conf_load.steal = pahole_stealer; + conf_load.thread_exit = pahole_thread_exit; + conf_load.threads_prepare = pahole_threads_prepare; + conf_load.threads_collect = pahole_threads_collect;// Make 'pahole --header type < file' a shorter form of 'pahole -C type --count 1 < file' if (conf.header_type && !class_name && prettify_input) { --2.30.2
Quoted 11 lines · Kui-Feng Lee
Creating an instance of btf for each worker thread allows steal-function provided by pahole to add type info on multiple threads without a lock. The main thread merges the results of worker threads to the primary instance.
Copying data from per-thread btf instances to the primary instance is expensive now. However, there is a patch landed at the bpf-next repository. [1] With the patch for bpf-next and this patch, they drop total runtime to 5.4s from 6.0s with "-j4" on my device to generate BTF for Linux.
Just a few more data points. I've tried this locally with 40 cores, both with and without the libbpf's btf__add_btf() optimization.
BASELINE NON-PARALLEL
=====================
$ time ./pahole -J ~/linux-build/default/vmlinux ./pahole -J ~/linux-build/default/vmlinux 11.17s user 0.66s system 99% cpu 11.832 total
BASELINE PARALLEL
=================
$ time ./pahole -j40 -J ~/linux-build/default/vmlinux ./pahole -j40 -J ~/linux-build/default/vmlinux 13.85s user 0.75s system 290% cpu 5.023 total
THESE PATCHES WITHOUT LIBBPF SPEED-UP
=====================================
$ time ./pahole -j40 -J ~/linux-build/default/vmlinux ./pahole -j40 -J ~/linux-build/default/vmlinux 25.94s user 1.15s system 685% cpu 3.954 total
THESE PATCHES WITH LATEST LIBBPF SPEED-UP
=========================================
$ time ./pahole -j40 -J ~/linux-build/default/vmlinux ./pahole -j40 -J ~/linux-build/default/vmlinux 27.49s user 1.08s system 858% cpu 3.328 total
So on 40 cores, it's a speed up from 11.8 seconds non-parallel, to 5s parallel without Kui-Feng's changes, to 4s with Kui-Feng's changes, to 3.3s after libbpf update (I did it locally, will sync this to Github today).
4x speed up, not bad!
But parallel mode is not currently enabled in kernel build, let's enable parallel mode and save those seconds during the kernel build!
Quoted 21 lines
[1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/commit/?id=d81283d27266
Kui-Feng Lee (2):
dwarf_loader: Prepare and pass per-thread data to worker threads.
pahole: Use per-thread btf instances to avoid mutex locking.btf_encoder.c | 5 +++ btf_encoder.h | 2 + btf_loader.c | 2 +- ctf_loader.c | 2 +- dwarf_loader.c | 58 ++++++++++++++++++------ dwarves.h | 9 +++- pahole.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++--- pdwtags.c | 3 +- pfunct.c | 4 +- 9 files changed, 180 insertions(+), 25 deletions(-)--
2.30.2
Quoted 43 lines · Andrii Nakryiko
Quoted 11 lines · Kui-Feng Lee
Creating an instance of btf for each worker thread allows steal-function provided by pahole to add type info on multiple threads without a lock. The main thread merges the results of worker threads to the primary instance.
Copying data from per-thread btf instances to the primary instance is expensive now. However, there is a patch landed at the bpf-next repository. [1] With the patch for bpf-next and this patch, they drop total runtime to 5.4s from 6.0s with "-j4" on my device to generate BTF for Linux.
Just a few more data points. I've tried this locally with 40 cores, both with and without the libbpf's
btf__add_btf()optimization.BASELINE NON-PARALLEL
=====================$ time ./pahole -J ~/linux-build/default/vmlinux ./pahole -J ~/linux-build/default/vmlinux 11.17s user 0.66s system 99% cpu 11.832 totalBASELINE PARALLEL
=================$ time ./pahole -j40 -J ~/linux-build/default/vmlinux ./pahole -j40 -J ~/linux-build/default/vmlinux 13.85s user 0.75s system 290% cpu 5.023 totalTHESE PATCHES WITHOUT LIBBPF SPEED-UP
=====================================$ time ./pahole -j40 -J ~/linux-build/default/vmlinux ./pahole -j40 -J ~/linux-build/default/vmlinux 25.94s user 1.15s system 685% cpu 3.954 totalTHESE PATCHES WITH LATEST LIBBPF SPEED-UP
=========================================$ time ./pahole -j40 -J ~/linux-build/default/vmlinux ./pahole -j40 -J ~/linux-build/default/vmlinux 27.49s user 1.08s system 858% cpu 3.328 total
Quoted 6 lines
So on 40 cores, it's a speed up from 11.8 seconds non-parallel, to 5s parallel without Kui-Feng's changes, to 4s with Kui-Feng's changes, to 3.3s after libbpf update (I did it locally, will sync this to Github today).
4x speed up, not bad!
That's indeed excellent! From the limited review I've made so far it looks good, takes advantage of the leg work I did, I'll just break down the patches a bit more, look at the review comments from you and repost, I'll not change the patches, just split them a bit more, tomorrow morning.
- Arnaldo
Quoted 28 lines
But parallel mode is not currently enabled in kernel build, let's enable parallel mode and save those seconds during the kernel build!
Quoted 21 lines
[1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/commit/?id=d81283d27266
Kui-Feng Lee (2):
dwarf_loader: Prepare and pass per-thread data to worker threads.
pahole: Use per-thread btf instances to avoid mutex locking.btf_encoder.c | 5 +++ btf_encoder.h | 2 + btf_loader.c | 2 +- ctf_loader.c | 2 +- dwarf_loader.c | 58 ++++++++++++++++++------ dwarves.h | 9 +++- pahole.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++--- pdwtags.c | 3 +- pfunct.c | 4 +- 9 files changed, 180 insertions(+), 25 deletions(-)--
2.30.2