Skip to contentSkip to conversation

Parallelize BTF type info generating of pahole

PATCH In review Kui-Feng Lee 3 participants 6 messages Jan 20, 2022 BPF

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index 7a5b16ff393e..b61cadd55127 100644
@@ -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
index 7c34739afdce..de6d4dbfce97 100644
@@ -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
index 52d162d67456..de152f9b64cf 100644
@@ -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
index f3a51cb2fe74..f3eeaaca4cdf 100644
@@ -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
index 2b5ba1bf6745..8b1d6f1c96cb 100644
@@ -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
index 5485622e639b..314915b774f4 100644
@@ -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
#2 lore raw

PATCH 2/2 pahole: Use per-thread btf instances to avoid mutex locking.

In reply to 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.

---
 btf_encoder.c |   5 +++
 btf_encoder.h |   2 +
 pahole.c      | 117 +++++++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 119 insertions(+), 5 deletions(-)
btf_encoder.c +5 -0
index 9d015f304e92..96a6c1d5fba0 100644
@@ -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
index f133b0d7674d..e141ec2e677d 100644
@@ -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
#3 lore raw

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.

---

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
index 9d015f304e92..96a6c1d5fba0 100644

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
index f133b0d7674d..e141ec2e677d 100644
@@ -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
index f3eeaaca4cdf..56bd7dc4e62e 100644
@@ -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

#4 lore raw
In reply to Kui-Feng Lee

+cc [email protected]

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

#5 lore raw
Quoted 43 lines · Andrii Nakryiko

+cc [email protected]

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
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