Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Date:   Tue, 13 Jul 2021 14:02:10 -0400
From:   Kent Overstreet <kent.overstreet@gmail.com>
To:     Matthew Wilcox <willy@infradead.org>
Cc:     Gary Guo <gary@garyguo.net>,
        Miguel Ojeda <miguel.ojeda.sandonis@gmail.com>,
        Miguel Ojeda <ojeda@kernel.org>,
        Linus Torvalds <torvalds@linux-foundation.org>,
        Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
        rust-for-linux <rust-for-linux@vger.kernel.org>,
        Linux Kbuild mailing list <linux-kbuild@vger.kernel.org>,
        Linux Doc Mailing List <linux-doc@vger.kernel.org>,
        linux-kernel <linux-kernel@vger.kernel.org>,
        Alex Gaynor <alex.gaynor@gmail.com>,
        Geoffrey Thomas <geofft@ldpreload.com>,
        Finn Behrens <me@kloenk.de>,
        Adam Bratschi-Kaye <ark.email@gmail.com>,
        Wedson Almeida Filho <wedsonaf@google.com>
Subject: Re: [PATCH 01/17] kallsyms: support big kernel symbols (2-byte
 lengths)
Message-ID: <YO3VIjpaCSZnNapB@moria.home.lan>
References: <20210704202756.29107-1-ojeda@kernel.org>
 <20210704202756.29107-2-ojeda@kernel.org>
 <YOIicc94zvSjrKfe@casper.infradead.org>
 <CANiq72=eHs870jbmZz8CUEUuN2NOCaKS9-F6-jAb0QXje2x1Eg@mail.gmail.com>
 <YOIpM3iFT5roz69i@casper.infradead.org>
 <20210704232007.0000357e@garyguo.net>
 <YOI5O6/RpaN1P6mM@casper.infradead.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <YOI5O6/RpaN1P6mM@casper.infradead.org>
Precedence: bulk

On Sun, Jul 04, 2021 at 11:42:03PM +0100, Matthew Wilcox wrote:
> On Sun, Jul 04, 2021 at 11:20:07PM +0100, Gary Guo wrote:
> > This is big endian.
> 
> Fundamentally, it doesn't matter whether it's encoded as top-7 +
> bottom-8 or bottom-7 + top-8.  It could just as well be:
> 
>         if (len >= 128) {
>                 len -= 128;
>                 len += *data * 256;
>                 data++;
>         }
> 
> It doesn't matter whether it's compatible with some other encoding.
> This encoding has one producer and one consumer.  As long as they agree,
> it's fine.  If you want to make an argument about extensibiity, then
> I'm going to suggest that wanting a symbol name more than 32kB in size
> is a sign you've done something else very, very wrong.
> 
> At that point, you should probably switch to comparing hashes of the
> symbol instead of the symbol.  Indeed, I think we're already there at
> 300 byte symbols; we should probably SipHash the full, unmangled symbol
> [1].  At 33k symbols in the current kernel, the risk of a collision of
> a 64-bit value is negligible, and almost every kernel symbol is longer
> than 7 bytes (thankfully).

We really should have a better standard varint encoding - open coding varint
encodings in 2021 is offensive, and LEB128 is retarded due to using the high bit
of _every_ byte. Here's the encoding I did for bcachefs, which I nominate for a
standard varint encoding, unless someone knows of a way to do better:

https://evilpiepirate.org/git/bcachefs.git/tree/fs/bcachefs/varint.c