On Mon, Jul 11, 2016 at 7:22 AM, Dave Chinner <david@xxxxxxxxxxxxx> wrote:
> [please don't top post]
>
> On Fri, Jul 08, 2016 at 01:48:43PM +0800, Kaho Ng wrote:
>> On Fri, Jul 8, 2016 at 6:28 AM, Dave Chinner <david@xxxxxxxxxxxxx> wrote:
>> > On Thu, Jul 07, 2016 at 07:01:35PM +0800, Kaho Ng wrote:
>> >> I am trying to investigate how freelist allocator in xfs interacts
>> >> with freespace B+Tree allocator.
>> >> First I prepared a patch
>> >> <https://gist.github.com/22ffca35929e67c08759b057779b7566> on
>> >> linux-source/fs/xfs/libxfs/xfs_alloc.c to print debugging messages
>> >> (The kernel version used is linux-3.10.0-327.22.2.el7).
>> > ......
>> >> When reading the log output
>> >> <https://gist.github.com/890076405e1c13c0a952a579e25e6afe> , I
>> >> realised that there is no B+Tree split
>> >> triggered by xfs_alloc_fix_freelist() when calling xfs_free_extent().
>> >> Isn't B+Tree split possible in by-size B+Tree even when truncating a
>> >> longer freespace record to shorter one? But what I found in the log is
>> >> only a few tree shrinks... And when reading the source code of
>> >> freespace allocator I found that a B+Tree growth in this case is
>> >> impossible at least...
>> >
>> > args->isfl doesn't mean what you think it means.
>> >
>> > args->isfl is only set when moving blocks from the freespace btree
>> > to the AGFL, which only occurs when a previous operation allocated a
>> > new freespace btree block and depleted the current freelist. i.e.
>> > "AG Free List" != "AG freespace btree" - they are different
>> > structures on disk...
>> >
>> > And when you consider that a freelist refill can only remove records
>> > from the the freespace btree, it's should be clear that a btree
>> > split won't occur during a freelist refill...
>>
>> Hmm, wouldn't xfs_alloc_ag_vextent_size() first remove the free extent
>> record, and insert a new extent record into the freespace by-size
>> btree if the found free extent record is longer than args->maxlen?
>
> Good, you went and looked to verify what I said(*). Indeed, when
> you read xfs_alloc_fixup_trees() where the two trees are modified
> after an extent has been selected for allocation:
>
> ...
> * Delete the entry from the by-size btree.
> ...
> * Add new by-size btree entry(s).
> ...
> * Fix up the by-block btree entry(s)
>
> It's pretty clear what the answer is. IOWs, yes, you're correct - we
> only ever modify or delete records from the by-bno freespace tree,
> but the by-size tree does do a delete and insert and so can
> split.(**)
>
> So, while it is possible for a split to occur, you still didn't see
> one in your test. That's because a split is rather unlikely in your
> scenario because once we have a large enough freespace btree records
> stored for a split to occur, we almost always have exact matches in
> the by-count tree for freelist fills and so record deletes are the
> usual operationon the by-count tree.
>
> And even if we are doing a by-count insert, the chances the target
> block for the insert is full is quite small, as are the chances the
> target block for the insert is different to the block the original
> record was deleted from (consider ordering, what record index the
> initial lookup returns and that freelist fills usually only require
> a block or two to be allocated).
>
> Cheers,
>
> Dave.
>
> (*) That was what my answer was aimed at getting you to do as I get
> a lot of timewasters asking me via direct email to answer their
> homework questions for them. Anyone who is trying to understand the
> basics of the freespace btrees should have realised the by-count
> tree needs a delete/insert operation pair if we modify the length of
> a freespace record.
>
> (**) The lesson here is this: trust what people say, but always
> verify it when you can. e.g. I now know you'll look at the
> code to try to understand answers you are given, so my time
> answering your questions is not going to be wasted.
>
> --
> Dave Chinner
> david@xxxxxxxxxxxxx
Thanks for the detailed explaination!
Just wonders why we prefer failing the request of refilling freelist
with XFS_WANT_CORRUPTED_RETURN(mp, i == 1) in some rare case, rather
than returning NULLAGBLOCK and allowing the loop in
xfs_alloc_ag_vextent_size() to try xfs_alloc_ag_vextent_small()... In
such corner case there will always be a lot of small extents at the
front of the by-count tree, and any truncation changes to the first
entry in the tree will not result in tree splits and triggering
assertion failure.
|