Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Tue, 29 Mar 2022 16:16:11 +0200
From:   "Steinar H. Gunderson" <sesse@google.com>
To:     Adrian Hunter <adrian.hunter@intel.com>
Cc:     Peter Zijlstra <peterz@infradead.org>,
        Ingo Molnar <mingo@redhat.com>,
        Arnaldo Carvalho de Melo <acme@kernel.org>,
        Alexander Shishkin <alexander.shishkin@linux.intel.com>,
        Jiri Olsa <jolsa@redhat.com>,
        Namhyung Kim <namhyung@kernel.org>,
        linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH] perf intel-pt: Synthesize cycle events
Message-ID: <YkMUq/qrzEg5Mj1N@google.com>
References: <52903e58-e74c-5ea0-36b4-277ea3610af4@intel.com>
 <YjGdoGy4Z2UUG9S9@google.com>
 <ef780335-7dc6-3a23-54a8-b6fc9c8a2ed3@intel.com>
 <YjHfGrZovk3N/H0f@google.com>
 <371faf0d-f794-4a2e-0a1c-9d454d7c8b12@intel.com>
 <YjhUjotmo+kYvoNP@google.com>
 <ffa56520-09b5-9c5d-7733-6767d2f8e350@intel.com>
 <YjiuoEUL6jH32cBi@google.com>
 <Yjm5stBpRC0g4G8s@google.com>
 <YkL8EpWaeZ1US8t2@google.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <YkL8EpWaeZ1US8t2@google.com>
Precedence: bulk

On Tue, Mar 29, 2022 at 02:31:14PM +0200, Steinar H. Gunderson wrote:
>   int64_t _sort__sym_cmp(struct symbol *sym_l, struct symbol *sym_r)
>   {
>           if (!sym_l || !sym_r)
>                   return cmp_null(sym_l, sym_r);
> 
>           if (sym_l == sym_r)
>                   return 0;
> 
>           if (sym_l->inlined || sym_r->inlined) {
>                   int ret = strcmp(sym_l->name, sym_r->name);
> 
>                   if (ret)
>                           return ret;
>                   if ((sym_l->start <= sym_r->end) && (sym_l->end >= sym_r->start))
>                           return 0;
>           }
> 
>           if (sym_l->start != sym_r->start)
>                   return (int64_t)(sym_r->start - sym_l->start);

Even fixing <= to <, I do get nonsensical results like an inlined
(and very small) destructor taking 50%+ of CPU time, and having a huge
call chain under it. It largely goes away (I'm not sure if it's perfect)
if I remove the entire if (sym_l->inlined || ... branch, but I guess
it's there for a reason.

Thinking about it, I wonder if this code breaks the entire tree
invariant of comparison being transitive. If left _or_ right is inlined,
it compares them by name, but if not, it compares them by address. So
you can have three symbols A, B (inline) and C, where A < B (on name),
B < C (on name) but C < A (on address; assuming C has a lower start
address than A). That doesn't look good to me.

I'm wondering if the right fix would be something like replacing the
entire if with something like

           if (sym_l->inlined && sym_r->inlined &&
	       strcmp(sym_l->name, sym_r->name) == 0) &&
	       <keep [start,end) overlap test here>) {
                   return 0;
	   }

but I'm not sure.

/* Steinar */