Re: [PATCH 08/14] xfs: document btree bulk loading

["Darrick J. Wong" <djwong@kernel.org>]

On Thu, Feb 16, 2023 at 03:46:02PM +0000, Allison Henderson wrote:

<snip to the relevant parts>

> > > > +Writing the New Tree
> > > > +````````````````````
> > > > +
> > > > +This part is pretty simple -- the btree builder
> > > > (``xfs_btree_bulkload``) claims
> > > > +a block from the reserved list, writes the new btree block
> > > > header,
> > > > fills the
> > > > +rest of the block with records, and adds the new leaf block to a
> > > > list of
> > > > +written blocks.
> > > > +Sibling pointers are set every time a new block is added to the
> > > > level.
> > > > +When it finishes writing the record leaf blocks, it moves on to
> > > > the
> > > > node
> > > > +blocks.
> > > > +To fill a node block, it walks each block in the next level down
> > > > in
> > > > the tree
> > > > +to compute the relevant keys and write them into the parent
> > > > node.
> > > > +When it reaches the root level, it is ready to commit the new
> > > > btree!
> > > I think most of this is as straight forward as it can be, but it's
> > > a
> > > lot visualizing too, which makes me wonder if it would benefit from
> > > an
> > > simple illustration if possible.
> > > 
> > > On a side note: In a prior team I discovered power points, while a
> > > lot
> > > work, were also really effective for quickly moving a crowd of
> > > people
> > > through connected graph navigation/manipulations.  Because each one
> > > of
> > > these steps was another slide that illustrated how the structure
> > > evolved through the updates.  I realize that's not something that
> > > fits
> > > in the scheme of a document like this, but maybe something
> > > supplemental
> > > to add later.  While it was a time eater, i noticed a lot of
> > > confused
> > > expressions just seemed to shake loose, so sometimes it was worth
> > > it.
> > 
> > That was ... surprisingly less bad than I feared it would be to cut
> > and
> > paste unicode linedraw characters and arrows.
> > 
> >           ┌─────────┐
> >           │root     │
> >           │PP       │
> >           └─────────┘
> >           ↙         ↘
> >       ┌────┐       ┌────┐
> >       │node│──────→│node│
> >       │PP  │←──────│PP  │
> >       └────┘       └────┘
> >       ↙   ↘         ↙   ↘
> >   ┌────┐ ┌────┐ ┌────┐ ┌────┐
> >   │leaf│→│leaf│→│leaf│→│leaf│
> >   │RRR │←│RRR │←│RRR │←│RRR │
> >   └────┘ └────┘ └────┘ └────┘
> > 
> > (Does someone have a program that does this?)
> I think Catherine mentioned she had used PlantUML for the larp diagram,
> though for something this simple I think this is fine

<nod>

> > I really like your version!  Can I tweak it a bit?
> > 
> > - Until the reverse mapping btree runs out of records:
> > 
> >   - Retrieve the next record from the btree and put it in a bag.
> > 
> >   - Collect all records with the same starting block from the btree
> > and
> >     put them in the bag.
> > 
> >   - While the bag isn't empty:
> > 
> >     - Among the mappings in the bag, compute the lowest block number
> >       where the reference count changes.
> >       This position will be either the starting block number of the
> > next
> >       unprocessed reverse mapping or the next block after the
> > shortest
> >       mapping in the bag.
> > 
> >     - Remove all mappings from the bag that end at this position.
> > 
> >     - Collect all reverse mappings that start at this position from
> > the
> >       btree and put them in the bag.
> > 
> >     - If the size of the bag changed and is greater than one, create
> > a
> >       new refcount record associating the block number range that we
> >       just walked to the size of the bag.
> > 
> > 
> Sure, that looks fine to me

Ok, will commit.

> > > Branch link?  Looks like maybe it's missing.  In fact this logic
> > > looks
> > > like it might have been cut off?
> > 
> > OH, heh.  I forgot that we already merged the AGFL repair code.
> > 
> > "See `fs/xfs/scrub/agheader_repair.c
> > <
> > https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tre
> > e/fs/xfs/scrub/agheader_repair.c>`_
> > for more details."
> > 
> > > In any case, maybe give some thought to the highlight link
> > > suggestions.
> > 
> > Er... how do those work?  In principle I like them, but none of your
> > links actually highlighted anything here.  Could you send the link
> > over
> > IRC so that urldefense crapola won't destroy it, please?
> > 
> > --D
> So I think the last we talked about these, we realized they're a chrome
> only format.  That's a shame, I think they really help people to
> quickly navigate the code in question.  Otherwise I'm pretty much just
> poking through the branches looking for code that resembles the
> description.

Yep.  Back in 2020, Google was pushing a "link to text fragment"
proposal wherein they'd add some secret sauce to URL anchors:

#:~:text=[prefix-,]textStart[,textEnd][,-suffix]

Which would inspire web browsers to highlight all instances of "text" in
a document and autoscroll to the first occurrence.  They've since
integrated this into Chrome and persuaded Safari to pick it up, but
there are serious problems with this hack.

https://wicg.github.io/scroll-to-text-fragment/

The first and biggest problem is that none of the prefix characters here
":~:text=" are invalid characters for a url anchor, nor are they ever
invalid for an <a name> tag.  This is valid html:

<a name="dork:~:text=farts">cow</a>

And this is valid link to that html anchor:

file:///tmp/a.html#dork:~:text=farts

Web browsers that are unaware of this extension (Firefox, lynx, w3m,
etc.) will not know to ignore everything starting with ":~:" when
navigating, so they will actually try to find an anchor matching that
name.  That's why it didn't work for me but worked fine for Allison.

This is even worse if the document also contains:

<a name="dork">frogs</a>

Because now the url "file:///tmp/a.html#dork:~:text=farts" jumps to
"cow" on Chrome, and "frogs" on Firefox.

Embrace and extend [with proprietary bullsh*t].  Thanks Google.

> I also poked around and found there was a firefox plugin that does the
> same (link to text fragment addon).  Though it doesn't look like the
> links generated are compatible between the browsers.

No, they are not.

> Maybe something to consider if we have a lot of chrome or ff users.  I
> think if they help facilitate more discussion they're better than
> nothing at least during review.

I'll comb through these documents and add some suggestions of where to
navigate, e.g.

"For more details, see the function xrep_reap."

Simple and readable by anyone, albeit without the convenient mechanical
links.

For more fun reading, apparently terminals support now escape sequences
to inject url links too:
https://github.com/Alhadis/OSC8-Adoption

--D

> > 
> > > Allison
> > > 
>