From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.3 required=3.0 tests=BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 78897C07E9B for ; Mon, 5 Jul 2021 04:36:17 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5D048613CB for ; Mon, 5 Jul 2021 04:36:17 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229495AbhGEEiw (ORCPT ); Mon, 5 Jul 2021 00:38:52 -0400 Received: from wtarreau.pck.nerim.net ([62.212.114.60]:57221 "EHLO 1wt.eu" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229447AbhGEEiv (ORCPT ); Mon, 5 Jul 2021 00:38:51 -0400 Received: (from willy@localhost) by pcw.home.local (8.15.2/8.15.2/Submit) id 1654ZWv9030978; Mon, 5 Jul 2021 06:35:32 +0200 Date: Mon, 5 Jul 2021 06:35:32 +0200 From: Willy Tarreau To: Gary Guo Cc: Matthew Wilcox , ojeda@kernel.org, Linus Torvalds , Greg Kroah-Hartman , rust-for-linux@vger.kernel.org, linux-kbuild@vger.kernel.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, Alex Gaynor , Geoffrey Thomas , Finn Behrens , Adam Bratschi-Kaye , Wedson Almeida Filho Subject: Re: [PATCH 01/17] kallsyms: support big kernel symbols (2-byte lengths) Message-ID: <20210705043532.GA30964@1wt.eu> References: <20210704202756.29107-1-ojeda@kernel.org> <20210704202756.29107-2-ojeda@kernel.org> <20210704222043.000026b3@garyguo.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20210704222043.000026b3@garyguo.net> User-Agent: Mutt/1.10.1 (2018-07-13) Precedence: bulk List-ID: X-Mailing-List: rust-for-linux@vger.kernel.org On Sun, Jul 04, 2021 at 10:20:43PM +0100, Gary Guo wrote: > On Sun, 4 Jul 2021 22:04:49 +0100 > Matthew Wilcox wrote: > > > On Sun, Jul 04, 2021 at 10:27:40PM +0200, ojeda@kernel.org wrote: > > > From: Miguel Ojeda > > > > > > Rust symbols can become quite long due to namespacing introduced > > > by modules, types, traits, generics, etc. > > > > > > Increasing to 255 is not enough in some cases, and therefore > > > we need to introduce 2-byte lengths to the symbol table. We call > > > these "big" symbols. > > > > > > In order to avoid increasing all lengths to 2 bytes (since most > > > of them only require 1 byte, including many Rust ones), we use > > > length zero to mark "big" symbols in the table. > > > > What happened to my suggestion from last time of encoding symbols < > > 128 as 0-127 and symbols larger than that as (data[0] - 128) * 256 + > > data[1]) ? > > Yeah, I agree ULEB128 or similar encoding scheme would be better than > using 0 as an escape byte. If ULEB128 is used and we restrict number of > bytes to 2, it will encode numbers up to 2**14 instead of 2**16 like the > current scheme, but that should be sufficient anyway. Actually plenty of variants of such encodings exist. You can split the first byte on 192 to keep 6 upper bits, 224 for 5, 240 for 4, etc. It all depends how long the maximum string is expected to be and how often we expect to see large strings. For example when splitting around 240, all sizes from 0 to 239 take one byte, and sizes from 240 to 4335 take two bytes. But if strings >128 are already extremely rare we don't really care about the extra byte needed to encode them. Willy