On Wed, Aug 30, 2017 at 12:14:03AM -0700, Christoph Hellwig wrote:
> On Wed, Aug 30, 2017 at 07:51:57AM +1000, Dave Chinner wrote:
> > Right, I've looked at btrees, too, but it's more complex than just
> > using an rbtree. I originally looked at using Peter Z's old
> > RCU-aware btree code, but it doesn't hold data in the tree leaves.
> > So that needed significant modification to make work without a
> > memory alloc per extent and that didn't work with original aim of
> > RCU-safe extent lookups. I also looked at that "generic" btree
> > stuff that came from logfs, and after a little while ran away
> > screaming.
>
> I started with the latter, but it's not really looking like it any more:
> there nodes are formatted as a series of u64s instead of all the
> long magic,
Yeah, that was about where I started to run away and look for
something nicer....
> and the data is stored inline - in fact I use a cute
> trick to keep the size down, derived from our "compressed" on disk
> extent format:
>
> Key:
>
> +-------+----------------------------+
> | 00:51 | all 52 bits of startoff |
> | 52:63 | low 12 bits of startblock |
> +-------+----------------------------+
>
> Value
>
> +-------+----------------------------+
> | 00:20 | all 21 bits of length |
> | 21 | unwritten extent bit |
> | 22:63 | high 42 bits of startblock |
> +-------+----------------------------+
>
> So we only need a 64-bit key and a 64-bit value by abusing parts
> of the key to store bits of the startblock.
Neat! :)
> For non-leaf nodes we iterate through the keys only, never touching
> the cache lines for the value. For the leaf nodes we have to touch
> the value anyway because we have to do a range lookup to find the
> exact record.
>
> This works fine so far in an isolated simulator, and now I'm ammending
> it to be a b+tree with pointers to the previous and next node so
> that we can nicely implement our extent iterators instead of doing
> full lookups.
Ok, that sounds exactly what I have been looking towards....
> > The sticking point, IMO, is the extent array index based lookups in
> > all the bmbt code. I've been looking at converting all that to use
> > offset based lookups and a cursor w/ lookup/inc/dec/insert/delete
> > ioperations wrapping xfs_iext_lookup_ext() and friends. This means
> > the modifications are pretty much identical to the on-disk extent
> > btree, so they can be abstracted out into a single extent update
> > interface for both trees. Have you planned/done any cleanup/changes
> > with this code?
>
> I've done various cleanups, but I've not yet consolidated the two.
> Basically step one at the moment is to move everyone to
> xfs_iext_lookup_extent + xfs_iext_get_extent that removes all the
> bad intrusion.
Yup.
> Once we move to the actual b+trees the extnum_t cursor will be replaced
> with a real cursor structure that contains a pointer to the current
> b+tree leaf node, and an index inside that, which will allows us very
> efficient iteration. The xfs_iext_get_extent calls will be replaced
> with more specific xfs_iext_prev_extent, xfs_iext_next_extent calls
> that include the now slightly more complex cursor decrement, increment
> as well as a new xfs_iext_last_extent helper for the last extent
> that we need in a few places.
Ok, that's sounds like it'll fit right in with what I've been
prototyping for the extent code in xfs_bmap.c. I can make that work
with a cursor-based lookup/inc/dec/ins/del API similar to the bmbt
API. I've been looking to abstract the extent manipulations out into
functions that modify both trees like this:
[note: just put template code in to get my thoughts straight, it's
not working code]
+static int
+xfs_bmex_delete(
+ struct xfs_iext_cursor *icur,
+ struct xfs_btree_cursor *cur,
+ int *nextents)
+{
+ int i;
+
+ xfs_iext_remove(bma->ip, bma->idx + 1, 2, state);
+ if (nextents)
+ (*nextents)--;
+ if (!cur)
+ return 0;
+ error = xfs_btree_delete(cur, &i);
+ if (error)
+ return error;
+ XFS_WANT_CORRUPTED_RETURN(cur->bc_mp, i == 1);
+ return 0;
+}
+
+static int
+xfs_bmex_increment(
+ struct xfs_iext_cursor *icur,
+ struct xfs_btree_cursor *cur)
+{
+ int i;
+
+ icur->ep = xfs_iext_get_right_ext(icur->ep);
+ if (!cur)
+ return 0;
+ error = xfs_btree_increment(cur, 0, &i);
+ if (error)
+ return error;
+ XFS_WANT_CORRUPTED_RETURN(cur->bc_mp, i == 1);
+ return 0;
+}
+
+static int
+xfs_bmex_decrement(
+ struct xfs_iext_cursor *icur,
+ struct xfs_btree_cursor *cur)
+{
+ int i;
+
+ icur->ep = xfs_iext_get_left_ext(icur->ep);
+ if (!cur)
+ return 0;
+ error = xfs_btree_decrement(cur, 0, &i);
+ if (error)
+ return error;
+ XFS_WANT_CORRUPTED_RETURN(cur->bc_mp, i == 1);
+ return 0;
+}
And so what you're doing would fit straight into that. I'm
ending up with is extent operations that look like this:
xfs_bmap_add_extent_delay_real()
.....
case BMAP_LEFT_FILLING | BMAP_LEFT_CONTIG |
BMAP_RIGHT_FILLING | BMAP_RIGHT_CONTIG:
/*
* Filling in all of a previously delayed allocation extent.
* The left and right neighbors are both contiguous with new.
*/
+ rval |= XFS_ILOG_CORE;
+
+ /* remove the incore delalloc extent first */
+ error = xfs_bmex_delete(&icur, NULL, nextents);
+ if (error)
+ goto done;
+
+ /*
+ * update incore and bmap extent trees
+ * 1. set cursors to the right extent
+ * 2. remove the right extent
+ * 3. update the left extent to span all 3 extent ranges
+ */
+ error = xfs_bmex_lookup_eq(&icur, bma->cur, RIGHT.br_startoff,
+ RIGHT.br_startblock, RIGHT.br_blockcount, 1);
+ if (error)
+ goto done;
+ error = xfs_bmex_delete(&icur, bma->cur, NULL);
+ if (error)
+ goto done;
+ error = xfs_bmex_decrement(&icur, bma->cur);
+ if (error)
+ goto done;
+ error = xfs_bmex_update(&icur, bma->cur, LEFT.br_startoff,
+ LEFT.br_startblock,
+ LEFT.br_blockcount + PREV.br_blockcount +
+ RIGHT.br_blockcount,
+ LEFT.br_state);
+ if (error)
+ goto done;
break;
....
And I'm starting to see where there are common extent manipulations
being done so there's probably a fair amount of further factoring
that can be done on top of this....
> insert/delete remain very similar to what they do right now, they'll
> get a different cursor type, and the manual xfs_iext_add calls will
> go away. The new xfs_iext_update_extent helper I posted to the list
> yesterday will become a bit more complex, as changing the startoff
> will have to be propagated up the tree.
I've had a quick look at them and pulled it down into my tree for
testing (which had a cpu burning hang on xfs/020 a few minutes ago),
but I'll spend more time grokking them tomorrow.
Cheers,
Dave.
--
Dave Chinner
david@xxxxxxxxxxxxx
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>
