<div dir="ltr"><span class="im" style="font-size:13px"><div>Hi,</div><div><br></div><div>Good to hear about the progress related to rmap. We'll continue</div><div>working here on our side.</div><div><br></div></span><div style="font-size:13px">As we mentioned previously, we've familiarized ourselves</div><div style="font-size:13px">with the fiemap interface and developed an understanding</div><div style="font-size:13px">of how the ioctl works.</div><div style="font-size:13px"><br></div><div style="font-size:13px">We also went through different discussions on the mailing </div><div style="font-size:13px">list related to fiemap, as well as obtained the latest patches.</div><div style="font-size:13px"><br></div><div style="font-size:13px">While working on the rmap, would it be possible for you to </div><div style="font-size:13px">give us some essential details about the required fiemap </div><div style="font-size:13px">interface, so that we can obtain a clearer understanding of</div><div style="font-size:13px"> what we are required to do.</div><div class="" style="font-size:13px"><div id=":16y" class="" tabindex="0"><img class="" src="https://ssl.gstatic.com/ui/v1/icons/mail/images/cleardot.gif"></div></div><div class="" style="font-size:13px"><span class="im"><div><br></div><div><br></div><div>Regards,</div><div>A-DRS.</div></span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Dec 1, 2014 at 10:01 AM, Dave Chinner <span dir="ltr"><<a href="mailto:david@fromorbit.com" target="_blank">david@fromorbit.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Mon, Dec 01, 2014 at 01:29:47AM +0530, Somdeep Dey wrote:<br>
> Hi,<br>
><br>
> We've now resumed working on the xfs_fsr utility as discussed before, after<br>
> our exams.<br>
><br>
> The first task that we undertook was to use fiemap to get file extent<br>
> mappings and tried to correlate the output with the information obtained<br>
> from xfs_bmap. For this we used the two underlying structures fiemap<br>
> and fiemap_extent. We're now trying to use the available free space mapping<br>
> patches to get free spaces in the file system.<br>
><br>
> We also wanted to ask about the current status of the rmap, as we'll<br>
> be required to define the interfaces that query it, as a key component of<br>
> our<br>
> work.<br>
<br>
</span>The rmap design is slowly being thrashed out. Brian and I had a<br>
discussion about it on IRC a couple of weeks ago (below).<br>
<br>
I'm relatively close to having a proof of concept for single-owner<br>
rmap btrees that works...<br>
<br>
Cheers,<br>
<br>
Dave.<br>
--<br>
Dave Chinner<br>
<a href="mailto:david@fromorbit.com">david@fromorbit.com</a><br>
<br>
>From #xfs on <a href="http://freenode.net" target="_blank">freenode.net</a><br>
<br>
[13/11/14 10:07] <dchinner_> foster: still around?<br>
[13/11/14 10:10] <foster> dchinner_: yep<br>
[13/11/14 10:27] <dchinner_> foster: been prototyping reverse mapping btree code over the past couple of days<br>
[13/11/14 10:28] <dchinner_> couple of interesting issues have come up that need discussion<br>
[13/11/14 10:28] <dchinner_> I think I have solutions to them, but I'm sure there are other ways of solving the problems<br>
[13/11/14 10:28] <dchinner_> basically I want the rmap btree for two purposes<br>
[13/11/14 10:29] <dchinner_> 1) to keep owner information so we can do block-to-owner lookups efficiently<br>
[13/11/14 10:29] <dchinner_> e.g. to identify the files corrupted by bad sectors<br>
[13/11/14 10:29] <dchinner_> found during a media scan<br>
[13/11/14 10:31] <dchinner_> or to provide sufficient redundant information for an online rebuild of a corrupted free space btree<br>
[13/11/14 10:32] <foster> so a btree that maps extents to inodes or something of that nature?<br>
[13/11/14 10:32] <dchinner_> exactly<br>
[13/11/14 10:32] <dchinner_> per-ag btree<br>
[13/11/14 10:32] <dchinner_> that contains { start block, length, owner }<br>
[13/11/14 10:32] <dchinner_> records<br>
[13/11/14 10:32] <foster> ok<br>
[13/11/14 10:33] <dchinner_> that's relatively easy to do<br>
[13/11/14 10:33] <dchinner_> The patches I've written do that.<br>
[13/11/14 10:33] <dchinner_> (not that it does anything other than compile yet)<br>
[13/11/14 10:33] <dchinner_> however, there is a second reason for having a reverse mapping tree<br>
[13/11/14 10:34] <dchinner_> it's for reference counting extents shared between inodes<br>
[13/11/14 10:34] <foster> ah, reflink?<br>
[13/11/14 10:34] <dchinner_> i.e. to implement reflink semantics<br>
[13/11/14 10:34] <dchinner_> *nod*<br>
[13/11/14 10:35] <dchinner_> this doesn't affect how the ramp btree interacts with the rest of the allocation/freeing code<br>
[13/11/14 10:35] <dchinner_> but it does affect the "extent owner" tracking<br>
[13/11/14 10:35] <dchinner_> i.e. we can now have multiple owners of an extent<br>
[13/11/14 10:36] <dchinner_> so that btree record now becomes {stat, len, refcount, owner, owner, .... owner }<br>
[13/11/14 10:36] <foster> yeah<br>
[13/11/14 10:36] <dchinner_> and we can't do that with the generic btree infrastructure because it's all based around fixed length records<br>
[13/11/14 10:38] <dchinner_> I've come up with a way of using fixed length records to implement this variable length shared rmap record<br>
[13/11/14 10:38] <dchinner_> which uses the high bit of the start block number to distinguish between the types of records<br>
[13/11/14 10:39] <dchinner_> and, in some cases, also uses the high bit of the extent length field to hold more information again.<br>
[13/11/14 10:40] <dchinner_> but the issue is that it's quite complicated<br>
[13/11/14 10:40] <dchinner_> and there's some interesting warts around records that span multiple btree blocks<br>
[13/11/14 10:41] <dchinner_> because they've been shared across hundreds of owners<br>
[13/11/14 10:43] <dchinner_> I can't see any obvious way of tracking owner information another way when we have shared extents<br>
[13/11/14 10:44] <dchinner_> it's an 1:N mapping<br>
[13/11/14 10:44] <foster> this information that's encoded in the record indicates the length of the record, or some kind of record chaining method..?<br>
[13/11/14 10:44] <dchinner_> both ;)<br>
[13/11/14 10:45] <foster> heh, ok<br>
[13/11/14 10:45] <dchinner_> the first record becomes { start block, length, refcount, owner records}<br>
[13/11/14 10:45] <dchinner_> and so a shared extent record looks like:<br>
[13/11/14 10:46] <dchinner_> {{ master extent record}, {owner record }, {owner record }, .... {owner record}}<br>
[13/11/14 10:46] <dchinner_> when an owner record is simply {owner #1, owner #2}<br>
[13/11/14 10:47] <dchinner_> so both the master record and the owner record are teh same size (16 bytes)<br>
[13/11/14 10:48] <dchinner_> so you can see how it can be problematic when a btree block only contains owner records<br>
[13/11/14 10:48] <dchinner_> there's no start/len information, and so it's problematic for indexing that block in the higher levels of the btree<br>
[13/11/14 10:49] <dchinner_> as the higher levels need to point to the master records....<br>
[13/11/14 10:49] <foster> I'm missing how the master record refers to the owner record<br>
[13/11/14 10:50] <foster> does it, or it's simply followed by the owner records?<br>
[13/11/14 10:50] <dchinner_> owner records always follow the master record<br>
[13/11/14 10:50] <foster> ok<br>
[13/11/14 10:50] <dchinner_> right<br>
[13/11/14 10:51] <dchinner_> So what I'm wondering is whether you think this is way too complex<br>
[13/11/14 10:51] <dchinner_> or whether we might do better to have some other representation<br>
[13/11/14 10:52] <dchinner_> such as keeping owner records in a different tree<br>
[13/11/14 10:53] <dchinner_> or even not keeping them at all for shared extents<br>
[13/11/14 10:53] <foster> sounds somewhat hairy at first, my first reaction is to think about whether there's some kind of level of indirection<br>
[13/11/14 10:53] <foster> but i obviously haven't thought about this much at all<br>
[13/11/14 10:54] <dchinner_> right, and I'm trying not to expose you to allthe gruesome details of what I've come up with ;)<br>
[13/11/14 10:54] <dchinner_> just enough to describe the problem<br>
[13/11/14 10:54] <foster> understood, i think i get the gist of it<br>
[13/11/14 10:54] <foster> effectively creating first order/second order records within the tree<br>
[13/11/14 10:55] <dchinner_> right<br>
[13/11/14 10:55] <foster> or chaining or whatever the best terminology is ;)<br>
[13/11/14 10:56] <dchinner_> hmmm, which triggers me immediately to think of an interesting btree extension<br>
[13/11/14 10:57] <foster> hmm, a second tree is an interesting thought<br>
[13/11/14 10:57] <foster> or some kind of magic/hidden owner inode that handles shared records<br>
[13/11/14 10:57] <dchinner_> which, at first glance, makes it very similar to the directory btree structure....<br>
[13/11/14 10:59] <dchinner_> need to think about that more....<br>
[13/11/14 11:02] <dchinner_> (basically adding another level below the current leaf level of the btree that only holds owner records)<br>
[13/11/14 11:06] <foster> interesting, though i'm not familiar enough with the on-disk dir structure to reason about off hand<br>
</blockquote></div><br></div>