On Tue, May 05, 2020 at 09:20:39AM -0700, Darrick J. Wong wrote: > On Tue, May 05, 2020 at 09:55:51AM -0400, Brian Foster wrote: > > On Mon, Apr 13, 2020 at 12:46:00PM -0700, Darrick J. Wong wrote: > > > From: Darrick J. Wong <darrick.wong@xxxxxxxxxx> > > > > > > Dave and I had a short discussion about whether or not xattr trees > > > needed to have the same free space tracking that directories have, and > > > a comparison of how each of the two metadata types interact with > > > dabtrees resulted. I've reworked this a bit to make it flow better as a > > > book chapter, so here we go. > > > > > > Original-mail: https://lore.kernel.org/linux-xfs/20200404085203.1908-1-chandanrlinux@xxxxxxxxx/T/#mdd12ad06cf5d635772cc38946fc5b22e349e136f > > > Originally-from: Dave Chinner <david@xxxxxxxxxxxxx> > > > Signed-off-by: Darrick J. Wong <darrick.wong@xxxxxxxxxx> > > > --- > > > v2: various fixes suggested by Dave; reflow the paragraphs about > > > directories to describe the relations between dabtree and dirents only once; > > > don't talk about an unnamed "we". > > > --- > > > .../extended_attributes.asciidoc | 55 ++++++++++++++++++++ > > > 1 file changed, 55 insertions(+) > > > > > > diff --git a/design/XFS_Filesystem_Structure/extended_attributes.asciidoc b/design/XFS_Filesystem_Structure/extended_attributes.asciidoc > > > index 99f7b35..b7a6007 100644 > > > --- a/design/XFS_Filesystem_Structure/extended_attributes.asciidoc > > > +++ b/design/XFS_Filesystem_Structure/extended_attributes.asciidoc > > > @@ -910,3 +910,58 @@ Log sequence number of the last write to this block. > > > > > > Filesystems formatted prior to v5 do not have this header in the remote block. > > > Value data begins immediately at offset zero. > > > + > > > +== Key Differences Between Directories and Extended Attributes > > > + > > > +Though directories and extended attributes can take advantage of the same > > > +variable length record btree structures (i.e. the dabtree) to map name hashes > > > +to directory entry records (dirent records) or extended attribute records, > > > +there are major differences in the ways that each of those users embed the > > > +btree within the information that they are storing. The directory dabtree leaf > > > +nodes contain mappings between a name hash and the location of a dirent record > > > +inside the directory entry segment. Extended attributes, on the other hand, > > > +store attribute records directly in the leaf nodes of the dabtree. > > Hmm, both you and Bill are right; maybe I don't want to have a > three-sentence paragraph where the first sentence constitutes 60% of the > words in that paragraph. :) I like this a lot better, thanks! Reviewed-by: Bill O'Donnell <billodo@xxxxxxxxxx> > > "Directories and extended attributes share the function of mapping names > to information, but the differences in the functionality requirements > applied to each type of structure influence their respective internal > formats. Directories map variable length names to iterable directory > entry records (dirent records), whereas extended attributes map variable > length names to non-iterable attribute records. Both structures can > take advantage of variable length record btree structures (i.e the > dabtree) to map name hashes, but there are major differences in the way > each type of structure integrate the dabtree index within the > information being stored. The directory dabtree leaf nodes contain > mappings between a name hash and the location of a dirent record inside > the directory entry segment. Extended attributes, on the other hand, > store attribute records directly in the leaf nodes of the dabtree." > > How about that instead? > > --D > > > > + > > > > Does the above mean to say "there are major differences in the ways each > > of these users embed information in the btree" as opposed to "embed the > > btree within the information?" The latter wording confuses me a bit, > > otherwise the rest looks good to me: > > > > Reviewed-by: Brian Foster <bfoster@xxxxxxxxxx> > > > > > +When XFS adds or removes an attribute record in any dabtree, it splits or > > > +merges leaf nodes of the tree based on where the name hash index determines a > > > +record needs to be inserted into or removed. In the attribute dabtree, XFS > > > +splits or merges sparse leaf nodes of the dabtree as a side effect of inserting > > > +or removing attribute records. > > > + > > > +Directories, however, are subject to stricter constraints. The userspace > > > +readdir/seekdir/telldir directory cookie API places a requirement on the > > > +directory structure that dirent record cookie cannot change for the life of the > > > +dirent record. XFS uses the dirent record's logical offset into the directory > > > +data segment as the cookie, and hence the dirent record cannot change location. > > > +Therefore, XFS cannot store dirent records in the leaf nodes of the dabtree > > > +because the offset into the tree would change as other entries are inserted and > > > +removed. > > > + > > > +Dirent records are therefore stored within directory data blocks, all of which > > > +are mapped in the first directory segment. The directory dabtree is mapped > > > +into the second directory segment. Therefore, directory blocks require > > > +external free space tracking because they are not part of the dabtree itself. > > > +Because the dabtree only stores pointers to dirent records in the first data > > > +segment, there is no need to leave holes in the dabtree itself. The dabtree > > > +splits or merges leaf nodes as required as pointers to the directory data > > > +segment are added or removed, and needs no free space tracking. > > > + > > > +When XFS adds a dirent record, it needs to find the best-fitting free space in > > > +the directory data segment to turn into the new record. This requires a free > > > +space index for the directory data segment. The free space index is held in > > > +the third directory segment. Once XFS has used the free space index to find > > > +the block with that best free space, it modifies the directory data block and > > > +updates the dabtree to point the name hash at the new record. When XFS removes > > > +dirent records, it leaves hole in the data segment so that the rest of the > > > +entries do not move, and removes the corresponding dabtree name hash mapping. > > > + > > > +Note that for small directories, XFS collapses the name hash mappings and > > > +the free space information into the directory data blocks to save space. > > > + > > > +In summary, the requirement for a free space map in the directory structure > > > +results from storing the dirent records externally to the dabtree. Attribute > > > +records are stored directly in the dabtree leaf nodes of the dabtree (except > > > +for remote attribute values which can be anywhere in the attr fork address > > > +space) and do not need external free space tracking to determine where to best > > > +insert them. As a result, extended attributes exhibit nearly perfect scaling > > > +until the computer runs out of memory. > > > > > >
