Re: [PATCH v3 09/14] perf kvm: Use histograms list to replace cached list

[Namhyung Kim]

On Tue, Feb 28, 2023 at 3:53 AM Leo Yan <leo.yan@xxxxxxxxxx> wrote:
>
> perf kvm tool defines its own cached list which is managed with RB tree,
> histograms also provide RB tree to manage data entries.  Since now we
> have introduced histograms in the tool, it's not necessary to use the
> self defined list and we can directly use histograms list to manage
> KVM events.
>
> This patch changes to use histograms list to track KVM events, and it
> invokes the common function hists__output_resort_cb() to sort result,
> this also give us flexibility to extend more sorting key words easily.
>
> After histograms list supported, the cached list is redundant so remove
> the relevant code for it.
>
> Signed-off-by: Leo Yan <leo.yan@xxxxxxxxxx>
> Reviewed-by: James Clark <james.clark@xxxxxxx>
> ---
>  tools/perf/builtin-kvm.c   | 186 +++++++++++++++++++------------------
>  tools/perf/util/kvm-stat.h |   7 --
>  2 files changed, 94 insertions(+), 99 deletions(-)
>
> diff --git a/tools/perf/builtin-kvm.c b/tools/perf/builtin-kvm.c
> index da84f5063d4d..32dc697ff707 100644
> --- a/tools/perf/builtin-kvm.c
> +++ b/tools/perf/builtin-kvm.c
> @@ -421,44 +421,37 @@ struct vcpu_event_record {
>         struct kvm_event *last_event;
>  };
>
> -
> -static void init_kvm_event_record(struct perf_kvm_stat *kvm)
> -{
> -       unsigned int i;
> -
> -       for (i = 0; i < EVENTS_CACHE_SIZE; i++)
> -               INIT_LIST_HEAD(&kvm->kvm_events_cache[i]);
> -}
> -
>  #ifdef HAVE_TIMERFD_SUPPORT
> -static void clear_events_cache_stats(struct list_head *kvm_events_cache)
> +static void clear_events_cache_stats(void)
>  {
> -       struct list_head *head;
> +       struct rb_root_cached *root;
> +       struct rb_node *nd;
>         struct kvm_event *event;
> -       unsigned int i;
> -       int j;
> -
> -       for (i = 0; i < EVENTS_CACHE_SIZE; i++) {
> -               head = &kvm_events_cache[i];
> -               list_for_each_entry(event, head, hash_entry) {
> -                       /* reset stats for event */
> -                       event->total.time = 0;
> -                       init_stats(&event->total.stats);
> -
> -                       for (j = 0; j < event->max_vcpu; ++j) {
> -                               event->vcpu[j].time = 0;
> -                               init_stats(&event->vcpu[j].stats);
> -                       }
> +       int i;
> +
> +       if (hists__has(&kvm_hists.hists, need_collapse))
> +               root = &kvm_hists.hists.entries_collapsed;
> +       else
> +               root = kvm_hists.hists.entries_in;
> +
> +       for (nd = rb_first_cached(root); nd; nd = rb_next(nd)) {
> +               struct hist_entry *he;
> +
> +               he = rb_entry(nd, struct hist_entry, rb_node_in);
> +               event = container_of(he, struct kvm_event, he);
> +
> +               /* reset stats for event */
> +               event->total.time = 0;
> +               init_stats(&event->total.stats);
> +
> +               for (i = 0; i < event->max_vcpu; ++i) {
> +                       event->vcpu[i].time = 0;
> +                       init_stats(&event->vcpu[i].stats);
>                 }
>         }
>  }
>  #endif
>
> -static int kvm_events_hash_fn(u64 key)
> -{
> -       return key & (EVENTS_CACHE_SIZE - 1);
> -}
> -
>  static bool kvm_event_expand(struct kvm_event *event, int vcpu_id)
>  {
>         int old_max_vcpu = event->max_vcpu;
> @@ -484,21 +477,51 @@ static bool kvm_event_expand(struct kvm_event *event, int vcpu_id)
>         return true;
>  }
>
> +static void *kvm_he_zalloc(size_t size)
> +{
> +       struct kvm_event *kvm_ev;
> +
> +       kvm_ev = zalloc(size + sizeof(*kvm_ev));
> +       if (!kvm_ev)
> +               return NULL;
> +
> +       return &kvm_ev->he;
> +}
> +
> +static void kvm_he_free(void *he)
> +{
> +       struct kvm_event *kvm_ev;
> +
> +       kvm_ev = container_of(he, struct kvm_event, he);
> +       free(kvm_ev);
> +}
> +
> +static struct hist_entry_ops kvm_ev_entry_ops = {
> +       .new    = kvm_he_zalloc,
> +       .free   = kvm_he_free,
> +};
> +
>  static struct kvm_event *kvm_alloc_init_event(struct perf_kvm_stat *kvm,
>                                               struct event_key *key,
> -                                             struct perf_sample *sample __maybe_unused)
> +                                             struct perf_sample *sample)
>  {
>         struct kvm_event *event;
> +       struct hist_entry *he;
>
> -       event = zalloc(sizeof(*event));
> -       if (!event) {
> -               pr_err("Not enough memory\n");
> +       he = hists__add_entry_ops(&kvm_hists.hists, &kvm_ev_entry_ops,
> +                                 &kvm->al, NULL, NULL, NULL, sample, true);
> +       if (he == NULL) {
> +               pr_err("Failed to allocate hist entry\n");
>                 return NULL;
>         }
>
> +       hists__inc_nr_samples(&kvm_hists.hists, 0);
> +
> +       event = container_of(he, struct kvm_event, he);
>         event->perf_kvm = kvm;
>         event->key = *key;
>         init_stats(&event->total.stats);
> +
>         return event;
>  }
>
> @@ -507,22 +530,26 @@ static struct kvm_event *find_create_kvm_event(struct perf_kvm_stat *kvm,
>                                                struct perf_sample *sample)
>  {
>         struct kvm_event *event;
> -       struct list_head *head;
> +       struct rb_root_cached *root;
> +       struct rb_node *nd;
>
>         BUG_ON(key->key == INVALID_KEY);
>
> -       head = &kvm->kvm_events_cache[kvm_events_hash_fn(key->key)];
> -       list_for_each_entry(event, head, hash_entry) {
> +       if (hists__has(&kvm_hists.hists, need_collapse))
> +               root = &kvm_hists.hists.entries_collapsed;
> +       else
> +               root = kvm_hists.hists.entries_in;
> +
> +       for (nd = rb_first_cached(root); nd; nd = rb_next(nd)) {
> +               struct hist_entry *he = rb_entry(nd, struct hist_entry,
> +                                                rb_node_in);
> +
> +               event = container_of(he, struct kvm_event, he);
>                 if (event->key.key == key->key && event->key.info == key->info)
>                         return event;

This seems inefficient and even unnecessary.  You should find
the event based on the return value of hist_entry__cmp() from
the root and go down.

But I think that's what hists__add_entry_ops() does.  Maybe
you may need to move the init logic (like init_stats) to the
kvm_he_zalloc().

Thanks,
Namhyung


>         }
>
> -       event = kvm_alloc_init_event(kvm, key, sample);
> -       if (!event)
> -               return NULL;
> -
> -       list_add(&event->hash_entry, head);
> -       return event;
> +       return kvm_alloc_init_event(kvm, key, sample);
>  }