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:   Fri, 24 Sep 2021 22:35:49 +0900
From:   Masami Hiramatsu <mhiramat@kernel.org>
To:     Steven Rostedt <rostedt@goodmis.org>
Cc:     Eugene Syromyatnikov <evgsyr@gmail.com>,
        lkml <linux-kernel@vger.kernel.org>,
        Ingo Molnar <mingo@kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        Masami Hiramatsu <mhiramat@kernel.org>,
        Mathieu Desnoyers <mathieu.desnoyers@efficios.com>,
        linux-trace-devel@vger.kernel.org
Subject: Re: [PATCH 0/2] tracing: Have trace_pid_list be a sparse array
Message-Id: <20210924223549.c41a89befe11534dfd56f01c@kernel.org>
In-Reply-To: <20210924091627.645a8fd3@gandalf.local.home>
References: <20210924033547.939554938@goodmis.org>
        <20210924000717.310b492a@rorschach.local.home>
        <CACGkJdtsHWBstw_Gzb-Dq4Xs_eAW1jsARr5wbh0yE_=NsPA5bw@mail.gmail.com>
        <20210924091627.645a8fd3@gandalf.local.home>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Precedence: bulk

On Fri, 24 Sep 2021 09:16:27 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Fri, 24 Sep 2021 12:51:07 +0200
> Eugene Syromyatnikov <evgsyr@gmail.com> wrote:
> 
> Hi Eugene,
> 
> > Note that there is only one top-level chunk (so its size doesn't
> > matter much), (usually) about one middle-tier chunk (except for some
> > heavy cases, since pids are allocated linearly), and quite some
> > lower-tier bitset leaves.  So I'd optimise towards smaller leaves at
> > the expense of middle-tier (and especially top-tier) chunk size
> > (especially considering the fact that in the kernel, buddy allocator
> > is used), like 12-8-12 or something like that, but I have no factual
> 
> What I really like about my 8 8 14 split I have, it makes everything 2K in
> size on 64 bit machines (1K 1K 2K for 32 bit, but who cares ;-)
> 
>  1 << 8 * 8 bytes = 2K   // top tiers are pointers to lower tiers
>  1 << 14 bits = 2K       // lower tier only cares about bits
> 
> This means they will likely all be allocated in the same slab.
> 
> I'm optimizing the top tiers for size, because they are likely to be empty.
> Why add memory for something that will never be used, and can't be removed.
> Note, the middle and lower tiers can be reused when they go empty, which is
> a likely use case (at least when I test this using hackbench).
> 
> > basis for arguing about specific split.  Also, I cannot resist from
> > noticing that this reminds me an awful lot of XArray and [1].  Maybe,
> > some wrapper around XArray would do?
> > 
> > [1] https://gitlab.com/strace/strace/-/raw/master/src/trie.h
> > 
> 
> I looked into xarray and it appears to be optimized for storing something,
> where as I'm just interested in a sparse bitmask.

I guess he suggested that store the bitmask in xarray. Anyway, both are
OK to me. This is needed for reducing the memory.

Thank you,

> 
> Thanks for the review.
> 
> Note, I'll be posting a v3 soon because I found if I echo 1<<30 into
> set_event_pid, it adds 0 (because it only looks at the bottom 30 bits).
> It should really return -EINVAL.
> 
> -- Steve


-- 
Masami Hiramatsu <mhiramat@kernel.org>