linux-kernel - Re: [PATCH bpf-next v2] docs/bpf: Add LRU internals description and graph

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]

Message-ID: <CADa=RyxodgJ+Wa3tiWxTntZoy7eSm_UkuzDBx9tCN=s_QnsDOw@mail.gmail.com>
Date:   Fri, 4 Nov 2022 15:09:32 -0700
From:   Joe Stringer <joe@...valent.com>
To:     Bagas Sanjaya <bagasdotme@...il.com>
Cc:     bpf@...r.kernel.org, linux-doc@...r.kernel.org,
        linux-kernel@...r.kernel.org, ast@...nel.org, corbet@....net,
        martin.lau@...ux.dev
Subject: Re: [PATCH bpf-next v2] docs/bpf: Add LRU internals description and graph

Resending, this time without HTML.

On Fri, Nov 4, 2022 at 2:31 AM Bagas Sanjaya <bagasdotme@...il.com> wrote:
>
> On 11/4/22 03:50, Joe Stringer wrote:
> > +An LRU hashmap type consists of two properties: Firstly, it is a hash map and
> > +hence is indexable by key for constant time lookups. Secondly, when at map
> > +capacity, map updates will trigger eviction of old entries based on the age of
> > +the elements in a set of lists. Each of these properties may be either global
> > +or per-CPU, depending on the map type and flags used to create the map:
> > +
> > +.. flat-table:: Comparison of map properties by map type (x-axis) and flags
> > +   (y-axis)
> > +
> > +   * -
> > +     - ``BPF_MAP_TYPE_LRU_HASH``
> > +     - ``BPF_MAP_TYPE_LRU_PERCPU_HASH``
> > +
> > +   * - ``BPF_NO_COMMON_LRU``
> > +     - Per-CPU LRU, global map
> > +     - Per-CPU LRU, per-cpu map
> > +
> > +   * - ``!BPF_NO_COMMON_LRU``
> > +     - Global LRU, global map
> > +     - Global LRU, per-cpu map
> > +
>
> Shouldn't the table be written in reST table syntax instead?

This table follows the syntax outlined in
https://docs.kernel.org/doc-guide/sphinx.html#list-tables . Is that
document not up to date?
I'm happy to do this, but several of the diagram boxes will reference
terms like rotation, shrinking etc without explaining what they are. I
think it's a net negative to readability if this text is not included
with the diagram. If you think the commit formatting is a bit over the
top, I could maybe just remove the decoration and embed the content
directly in the doc? On my first attempt at sketching this up, it just
felt a bit weird for me to submit that text directly if Martin was the
author of the text. But I could figure something out for that if
that's the preferred approach.

> > +Notably, there are various steps that the update algorithm attempts in order to
> > +enforce the LRU property which have increasing impacts on other CPUs involved
> > +in the operations:
> > +
> > +- Attempt to use CPU-local state to batch operations
> > +- Attempt to fetch free nodes from global lists
> > +- Attempt to pull any node from a global list and remove it from the hashmap
> > +- Attempt to pull any node from any CPU's list and remove it from the hashmap
> > +
>
> Better say "... other CPUs involved in the following operation attempts:"

Will fix, thanks.

> > +Even if an LRU node may be acquired, maps of type ``BPF_MAP_TYPE_LRU_HASH``
> > +may fail to insert the entry into the map if other CPUs are heavily contending
> > +on the global hashmap lock.
> > +
> > +This algorithm is described visually in the following diagram:
> > +
> > +.. kernel-figure::  map_lru_hash_update.dot
> > +   :alt:    Diagram outlining the LRU eviction steps taken during map update
> > +
> > +   LRU hash eviction during map update for ``BPF_MAP_TYPE_LRU_HASH`` and
> > +   variants
> > +
> <snipped>...
> > +
> > +The dot file source for the above diagram is uses internal kernel function
> > +names for the node names in order to make the corresponding logic easier to
> > +find. See ``Documentation/bpf/map_lru_hash_update.dot`` for more details.
>
> Since it references the same figure, just say "See the figure above for more
> details".

The figure is rendered visually in the docs without the corresponding
node names, so developers would need to look at either the dot source
or maybe the SVG source though that's arguably a little less readable.
The suggested phrasing to see the figure doesn't sound very useful to
me since the simple reader's interpretation would be to look directly
at the render rather than the source. This last sentence was intended
as a helpful way for developers to find the path to the corresponding
document, but if you think that is too much detail then I could also
just drop this last sentence. Thoughts?

Cheers,
Joe