linux-kernel - Re: [PATCHv2 bpf 3/3] bpf: Force cookies array to follow symbols sorting

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Wed, 8 Jun 2022 08:40:23 -0400
From:   Steven Rostedt <rostedt@...dmis.org>
To:     Jiri Olsa <olsajiri@...il.com>
Cc:     Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        Andrii Nakryiko <andrii@...nel.org>,
        Network Development <netdev@...r.kernel.org>,
        bpf <bpf@...r.kernel.org>, lkml <linux-kernel@...r.kernel.org>,
        Martin KaFai Lau <kafai@...com>,
        Song Liu <songliubraving@...com>, Yonghong Song <yhs@...com>,
        John Fastabend <john.fastabend@...il.com>,
        KP Singh <kpsingh@...omium.org>,
        Masami Hiramatsu <mhiramat@...nel.org>
Subject: Re: [PATCHv2 bpf 3/3] bpf: Force cookies array to follow symbols
 sorting

On Wed, 8 Jun 2022 11:57:48 +0200
Jiri Olsa <olsajiri@...il.com> wrote:

> Steven,
> is there a reason to show '__ftrace_invalid_address___*' symbols in
> available_filter_functions? it seems more like debug message to me
> 

Yes, because set_ftrace_filter may be set by index. That is, if schedule is
the 43,245th entry in available_filter_functions, then you can do:

  # echo 43245 > set_ftrace_filter
  # cat set_ftrace_filter
  schedule

That index must match the array index of the entries in the function list
internally. The reason for this is that entering a name is an O(n)
operation, where n is the number of functions in
available_filter_functions. If you want to enable half of those functions,
then it takes O(n^2) to do so.

I first implemented this trick to help with bisecting bad functions. That
is, every so often a function that should be annotated with notrace, isn't
and if it gets traced it cause the machine to reboot. To bisect this, I
would enable half the functions at a time and enable tracing to see if it
reboots or not, and if it does, I know that one of the half I enabled is
the culprit, if not, it's in the other half. It would take over 5 minutes
to enable half the functions. Where as the number trick took one second,
not only was it O(1) per function, but it did not need to do kallsym
lookups either. It simply enabled the function at the index.

Later, libtracefs (used by trace-cmd and others) would allow regex(3)
enabling of functions. That is, it would search available_filter_functions
in user space, match them via normal regex, create an index of the
functions to know where they are, and then write in those numbers to enable
them. It's much faster than writing in strings.

My original fix was to simply ignore those functions, but then it would
make the index no longer match what got set. I noticed this while writing
my slides for Kernel Recipes, and then fixed it.

The commit you mention above even states this:

      __ftrace_invalid_address___<invalid-offset>

    (showing the offset that caused it to be invalid).

    This is required for tools that use libtracefs (like trace-cmd does) that
    scan the available_filter_functions and enable set_ftrace_filter and
    set_ftrace_notrace using indexes of the function listed in the file (this
    is a speedup, as enabling thousands of files via names is an O(n^2)
    operation and can take minutes to complete, where the indexing takes less
    than a second).

In other words, having a placeholder is required to keep from breaking user
space.

-- Steve