xfsdocs: capture some information about dirs vs. attrs and how they use dabtrees
PATCH v2 1/1 xfsdocs: capture some information about dirs vs. attrs and how they use dabtrees
From: Darrick J. Wong <[email protected]>
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/[email protected]/T/#mdd12ad06cf5d635772cc38946fc5b22e349e136f
Originally-from: Dave Chinner <[email protected]>
---
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(+)
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +55 -0
@@ -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. + +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.
Quoted 11 lines · Darrick J. Wong
From: Darrick J. Wong <[email protected]>
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/[email protected]/T/#mdd12ad06cf5d635772cc38946fc5b22e349e136f
Originally-from: Dave Chinner <[email protected]>Signed-off-by Darrick J. Wong <[email protected]>
ping?
--D
Quoted 71 lines
---
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(+)design/XFS_Filesystem_Structure/extended_attributes.asciidoc +55
-0@@ -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. + +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.
Quoted 8 lines · Darrick J. Wong
From: Darrick J. Wong <[email protected]>
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.
Quoted 8 lines
Original-mail: https://lore.kernel.org/linux-xfs/[email protected]/T/#mdd12ad06cf5d635772cc38946fc5b22e349e136f
Originally-from: Dave Chinner <[email protected]>Signed-off-by Darrick J. Wong <[email protected]>---
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".
---
Looks good to me.
Quoted 67 lines
.../extended_attributes.asciidoc | 55 ++++++++++++++++++++ 1 file changed, 55 insertions(+)design/XFS_Filesystem_Structure/extended_attributes.asciidoc +55
-0@@ -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. + +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.
Quoted 29 lines · Darrick J. Wong
From: Darrick J. Wong <[email protected]>
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/[email protected]/T/#mdd12ad06cf5d635772cc38946fc5b22e349e136f
Originally-from: Dave Chinner <[email protected]>Signed-off-by Darrick J. Wong <[email protected]>---
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(+)design/XFS_Filesystem_Structure/extended_attributes.asciidoc +2
-0@@ -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
design/XFS_Filesystem_Structure/extended_attributes.asciidoc Log sequence number of the last write to this block. · line 924
Quoted 10 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +10
-0+ +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. +
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:
Quoted 44 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +43
-0+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.
Quoted 26 lines · Brian Foster
Quoted 25 lines · Darrick J. Wong
From: Darrick J. Wong <[email protected]>
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/[email protected]/T/#mdd12ad06cf5d635772cc38946fc5b22e349e136f
Originally-from: Dave Chinner <[email protected]>Signed-off-by Darrick J. Wong <[email protected]>---
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(+)design/XFS_Filesystem_Structure/extended_attributes.asciidoc +0
-0@@ -910,3 +910,58 @@ Log sequence number of the last write to this block.
Quoted 13 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc Log sequence number of the last write to this block. · line 923
Quoted 13 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +11
-0Filesystems 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. :)
"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
Quoted 54 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc Log sequence number of the last write to this block. · line 924
Quoted 1 line
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +1
-0+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 <[email protected]>Quoted 44 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +43
-0+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.
Bill O'Donnell
Reviewed-byQuoted 36 lines · Darrick J. Wong
Quoted 35 lines · Brian Foster
Quoted 34 lines · Darrick J. Wong
From: Darrick J. Wong <[email protected]>
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/[email protected]/T/#mdd12ad06cf5d635772cc38946fc5b22e349e136f
Originally-from: Dave Chinner <[email protected]>Signed-off-by Darrick J. Wong <[email protected]>---
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(+)design/XFS_Filesystem_Structure/extended_attributes.asciidoc +7
-0@@ -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
Quoted 8 lines
Quoted 4 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc Log sequence number of the last write to this block. · line 923
Quoted 4 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +4
-0+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!
Quoted 74 lines
"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
Quoted 54 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc Log sequence number of the last write to this block. · line 924
Quoted 1 line
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +1
-0+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 <[email protected]>Quoted 44 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +43
-0+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.
Brian Foster
Reviewed-byQuoted 59 lines · Darrick J. Wong
Quoted 26 lines · Brian Foster
Quoted 25 lines · Darrick J. Wong
From: Darrick J. Wong <[email protected]>
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/[email protected]/T/#mdd12ad06cf5d635772cc38946fc5b22e349e136f
Originally-from: Dave Chinner <[email protected]>Signed-off-by Darrick J. Wong <[email protected]>---
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(+)design/XFS_Filesystem_Structure/extended_attributes.asciidoc +0
-0@@ -910,3 +910,58 @@ Log sequence number of the last write to this block.Quoted 13 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc Log sequence number of the last write to this block. · line 923
Quoted 13 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +11
-0Filesystems 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. :)
"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."
Quoted 2 lines
How about that instead?
That reads much nicer than the original, thanks. I'm still not sure what that "major differences in the way each type of structure integrate the dabtree index within the information being stored" phrasing is supposed to express beyond saying something like "major differences in the way each type of structure use the dabtree," but I'm not going to harp on that...
Quoted 57 lines
--D
Quoted 54 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc Log sequence number of the last write to this block. · line 924
Quoted 1 line
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +1
-0+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 <[email protected]>Quoted 44 lines
design/XFS_Filesystem_Structure/extended_attributes.asciidoc +43
-0+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.