RE: Problems in GC when using NilFS2 with large segment size

RE: Problems in GC when using NilFS2 with large segment size

[Benixon Dhas]

Thanks for your comments Ryusuke Konishi.

We have tried the second suggestion of reducing the number of segments cleaned in a single pass in the configuration file. Even after this we are seeing the memory issue.
Due to limitations of ShIngled Disks the smallest segment size that we can go with is 128MB. In our case a larger segment size is desirable.

We would like a feature which can limit the amount of kernel memory  that is used for garbage collection. This might make the garbage collector inefficient. But it would make it stable on systems with limited resources.
 We are just beginning to look through the source to understand NilFS2 better. We can experiment by modifying the NilFS2 source. We would welcome any suggestions or pointers that would help us in modifying the source. 

Thanks,
Benixon

-----Original Message-----
From: Ryusuke Konishi [mailto:konishi.ryusuke-Zyj7fXuS5i5L9jVzuh4AOg@public.gmane.org] 
Sent: Monday, September 16, 2013 9:18 AM
To: Benixon Dhas
Subject: Re: Problems in GC when using NilFS2 with large segment size

Hi Benixon,

>Hello Ryusuke Konishi,
>
> I am a senior engineer at Western Digital working on Shingled Disks. 
> Shingled Magnetic Recording(SMR) is a new technology that increase HDD 
> capacity. The capacity increase comes at a cost that the drive must 
> physically write sequentially. We have learned about NilFS and have successfully prototyped our technology with your file system.
>
> We are now looking into some slight modifications with NilFS to fit a 
> new use case. Specifically we're looking into memory usage and cleaner algorithms.
> We tried to use NilFS2 on HDD with large segment size (say 128 MB or greater) and 4kB block size.
> Under light loads everything is working fine. Then we  tried running  
> a workload that writes four files in parallel generating data at the 
> rate of 2MB/second per file and a normal CPU load around 60% on a i5 
> core processor. This is fine as long as the garbage collector (GC) is 
> idle. But when Garbage collector starts on this 750GB NilFS partition we see some warnings due to memory allocations failing in the kernel and after a while the OOM killer is triggered.
>
> We see that the only about 150 MB out of the available 8GB main memory free under loaded conditions.
> The problem stills occurs even when the main memory is freed by dropping caches every 10 seconds.
> We are writing  1 to /proc/sys/vm/drop_caches for dropping the data 
> cache. Also we observe that when GC is running the disk activity is increased about five times the normal.
>
> Is there anything that we can do to solve this problem in your opinion?

The cleaner of NILFS reclaims disk space by repeating one-shot GC.
Every one-shot GC is performed per (nsegments_per_clean) segments, or
(mc_nsegments_per_clean) segments if the ratio of free disk space is less than (min_clean_segments).

The cleaner moves data of in-use blocks to new segments with kernel page cache, so it allocates, for the former case, (segment size) * (nsegments_per_clean) kernel memory bytes at worst, and (segment size) * (mc_nsegments_per_clean) bytes for the latter case.

By default, (nsegments_per_clean) is set to two and (mc_nsegments_per_clean) is set to four.  These parameters are defined in /etc/nilfs_cleanerd.conf.

To minimize memory pressure, I recommend you to tweak GC parameters with taking the above memory allocation model into consideration.
The following workaround may make a difference:

1. Decrease segment size
2. Decrease mc_nsegments_per_clean and nsegments_per_clean 3. Decrease cleaning_interval and mc_cleaning_interval instead of increasing
   segment size or {mc_,}nsegments_per_clean.

In general, using large segment size is not recommended because it consumes large kernel memory at least temporarily.

> Also is linux-nilfs kernel mailing list a better place for such 
> questions or is there any other person who might be able to help?

linux-nilfs mailing list is the best place to discuss such topic.

> Please provide us your suggestions and do let us know if you need any more details.
>
> Thanks,
> Benixon

With regards,
Ryusuke Konishi

--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

RE: Problems in GC when using NilFS2 with large segment size

[Vyacheslav Dubeyko]

Hi Benixon,

On Tue, 2013-09-17 at 18:39 +0000, Benixon Dhas wrote:

Yes, GC of NILFS2 is inefficient now. And GC optimization is the key
direction of NILFS2 optimization at whole, from my viewpoint. But I
suppose that we haven't efficient GC solution for LFS, currently. So,
suggestion of good solution of garbage collection scheme for LFS case is
promising direction, as far as I can judge.

I think that F2FS suggests some interesting approaches of garbage
collection. As you know, there are two classical approaches of GC
policies for the LFS case: (1) threading approach; (2) copying approach.
So, F2FS uses hybrid approach. I assume that it can be useful to be
familiar with F2FS techniques of garbage collection.

I know about efforts of NILFS2 GC optimization [1]. But I dissatisfied
as way of such optimization as code quality. So, I don't think that such
GC optimization is proper way.

If we are talking about shingled drive case then, first of all, it makes
sense to be acquainted with existed patents in this field. As I know,
there are significant number of inventions are suggested by guys from
Hitachi and HGST research centers. There are different suggestions of
using LFS in these patents and considerations about possible GC
overhead.

I think that it need to discuss promising techniques of garbage
collection in NILFS2 more deeply. Moreover, garbage collection
techniques for the case of flash and shingled drive can be different, as
far as I can see. I assume that in the case of shingled drive it makes
sense to use such technique of garbage collection. If you use LFS for
the case of shingled drive then you are using Copy-on-Write (COW)
policy. But, anyway, trying to read or update some sector results in
reading as minimum this sector in a cache. So, if you read not sector
but, for example, segment in a cache then you will have opportunity to
make clean operation in this segment. As a result, your read or update
operation will have addition in the form of copied valid blocks from
cleaned segment. I assume that shingled drive controller should have
support of GC operations in such approach.

> 
> We have tried the second suggestion of reducing the number of segments
> cleaned in a single pass in the configuration file. Even after this we
> are seeing the memory issue.
> Due to limitations of ShIngled Disks the smallest segment size that we
> can go with is 128MB. In our case a larger segment size is desirable.
> 
> We would like a feature which can limit the amount of kernel memory
> that is used for garbage collection. This might make the garbage
> collector inefficient. But it would make it stable on systems with
> limited resources.

By the way, there are probability that you have discovered some issue of
NILFS2 GC. So, if you think so then you need to describe a reproducing
path and what is wrong in GC behavior from your point of view.  

>  We are just beginning to look through the source to understand NilFS2
> better. We can experiment by modifying the NilFS2 source. We would
> welcome any suggestions or pointers that would help us in modifying
> the source. 
> 
NILFS2 has many TODO. So, you are welcome. :)

But if you plan to contribute into NILFS2 project then it makes sense to
distribute tasks. And it is possible to suggest something if you will
choose some TODO.

By the way, I am implementing extended attributes (xattr) support in
NILFS2 right now.

With the best regards,
Vyacheslav Dubeyko.

[1] http://www.mail-archive.com/linux-nilfs-u79uwXL29TY76Z2rM5mHXA@public.gmane.org/msg01739.html


--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Problems in GC when using NilFS2 with large segment size

[Ryusuke Konishi]

On Tue, 17 Sep 2013 18:39:01 +0000, Benixon Dhas wrote:
> Thanks for your comments Ryusuke Konishi.
> 
> We have tried the second suggestion of reducing the number of
> segments cleaned in a single pass in the configuration file. Even
> after this we are seeing the memory issue.

Did you try both mc_nsegments_per_clean and nsegments_per_clean ?

If you are using nilfs-clean command to invoke garbage collector,
try --speed option.

  # nilfs-clean --speed <nsegments-per-clean>[/<cleaning-interval>]

>  Due to limitations of
> ShIngled Disks the smallest segment size that we can go with is
> 128MB. In our case a larger segment size is desirable.

What is the purpose of this usage ?

NILFS allocates or reclaims disk space per segment, but write unit of
NILFS is not segment; NILFS usually appends multiple logs repeatedly
into a segment if I/O data size is smaller than segment size.

You can see this with lssu command:

  $ lssu | grep ad-
                 885  2013-09-18 23:48:48  ad-        1366
                 886  ---------- --:--:--  ad-           0
  ...
  $ lssu | grep ad-
                 885  2013-09-19 00:09:49  ad-        1402
                 886  ---------- --:--:--  ad-           0

Is this fit for your purpose?

If log appending is allowed, it looks like 128MB segment size is
not necessary.

In that case, it seems that we have only to customize GC selection
policy and segment allocation algorithm so that disk write is
sequentially performed per 128MB segment group.

Regards,
Ryusuke Konishi


> We would like a feature which can limit the amount of kernel memory
>  that is used for garbage collection. This might make the garbage
>  collector inefficient. But it would make it stable on systems with
>  limited resources.  We are just beginning to look through the
>  source to understand NilFS2 better. We can experiment by modifying
>  the NilFS2 source. We would welcome any suggestions or pointers
>  that would help us in modifying the source.
> 
> Thanks,
> Benixon
> 
> -----Original Message-----
> From: Ryusuke Konishi [mailto:konishi.ryusuke-Zyj7fXuS5i5L9jVzuh4AOg@public.gmane.org] 
> Sent: Monday, September 16, 2013 9:18 AM
> To: Benixon Dhas
> Subject: Re: Problems in GC when using NilFS2 with large segment size
> 
> Hi Benixon,
> 
>>Hello Ryusuke Konishi,
>>
>> I am a senior engineer at Western Digital working on Shingled Disks. 
>> Shingled Magnetic Recording(SMR) is a new technology that increase HDD 
>> capacity. The capacity increase comes at a cost that the drive must 
>> physically write sequentially. We have learned about NilFS and have successfully prototyped our technology with your file system.
>>
>> We are now looking into some slight modifications with NilFS to fit a 
>> new use case. Specifically we're looking into memory usage and cleaner algorithms.
>> We tried to use NilFS2 on HDD with large segment size (say 128 MB or greater) and 4kB block size.
>> Under light loads everything is working fine. Then we  tried running  
>> a workload that writes four files in parallel generating data at the 
>> rate of 2MB/second per file and a normal CPU load around 60% on a i5 
>> core processor. This is fine as long as the garbage collector (GC) is 
>> idle. But when Garbage collector starts on this 750GB NilFS partition we see some warnings due to memory allocations failing in the kernel and after a while the OOM killer is triggered.
>>
>> We see that the only about 150 MB out of the available 8GB main memory free under loaded conditions.
>> The problem stills occurs even when the main memory is freed by dropping caches every 10 seconds.
>> We are writing  1 to /proc/sys/vm/drop_caches for dropping the data 
>> cache. Also we observe that when GC is running the disk activity is increased about five times the normal.
>>
>> Is there anything that we can do to solve this problem in your opinion?
> 
> The cleaner of NILFS reclaims disk space by repeating one-shot GC.
> Every one-shot GC is performed per (nsegments_per_clean) segments, or
> (mc_nsegments_per_clean) segments if the ratio of free disk space is less than (min_clean_segments).
> 
> The cleaner moves data of in-use blocks to new segments with kernel page cache, so it allocates, for the former case, (segment size) * (nsegments_per_clean) kernel memory bytes at worst, and (segment size) * (mc_nsegments_per_clean) bytes for the latter case.
> 
> By default, (nsegments_per_clean) is set to two and (mc_nsegments_per_clean) is set to four.  These parameters are defined in /etc/nilfs_cleanerd.conf.
> 
> To minimize memory pressure, I recommend you to tweak GC parameters with taking the above memory allocation model into consideration.
> The following workaround may make a difference:
> 
> 1. Decrease segment size
> 2. Decrease mc_nsegments_per_clean and nsegments_per_clean 3. Decrease cleaning_interval and mc_cleaning_interval instead of increasing
>    segment size or {mc_,}nsegments_per_clean.
> 
> In general, using large segment size is not recommended because it consumes large kernel memory at least temporarily.
> 
>> Also is linux-nilfs kernel mailing list a better place for such 
>> questions or is there any other person who might be able to help?
> 
> linux-nilfs mailing list is the best place to discuss such topic.
> 
>> Please provide us your suggestions and do let us know if you need any more details.
>>
>> Thanks,
>> Benixon
> 
> With regards,
> Ryusuke Konishi
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Problems in GC when using NilFS2 with large segment size

[Ryusuke Konishi]

On Wed, 18 Sep 2013 11:36:54 +0400, Vyacheslav Dubeyko wrote:
> By the way, I am implementing extended attributes (xattr) support in
> NILFS2 right now.

Sounds great.

Could you share your implementation idea again before finishing your
patchset?

Is the basic idea same as the following RFC?

[1] http://www.mail-archive.com/linux-nilfs-u79uwXL29TY76Z2rM5mHXA@public.gmane.org/msg01298.html

There are several implementation approaches:

(1) Add one or multiple xattr meta data files to store xattr blocks.
(2) Add xattr btree to each disk inode (this seems to need inode size
    extension).
(3) Use part of inodes to hold xattr data.
(4) Extend btree to make holding mutiple data streams possible.

And we should first evaluate pros and cons of them to minimize rework,
for example, impact on disk format, impact on GC, impact on log
writer, and so forth.

We also have to decide whether we impose limitation on xattr block
size, that is, whether we support mutiple xattr blocks per inode or
only support single xattr block per inode.

The latter restricted implementation often becomes an issue nowadays.

Regards,
Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[RFC] nilfs2: xattrs support implementation idea

[Vyacheslav Dubeyko]

Hi Ryusuke,

On Thu, 2013-09-19 at 01:07 +0900, Ryusuke Konishi wrote:

> Could you share your implementation idea again before finishing your
> patchset?
> 

Yes, sure. It makes sense. Please, see description below.

> Is the basic idea same as the following RFC?
> 
> [1] http://www.mail-archive.com/linux-nilfs-u79uwXL29TY76Z2rM5mHXA@public.gmane.org/msg01298.html
> 

I reworked this suggestion significantly. So, I describe my current
approach and then we will elaborate a compromise solution. :)

So, I have such vision, currently.

There two places of storing xattrs:
(1) inline xattr nodes (xanodes);
(2) xattr file (xafile).

The inline xanode is extention of inode space. The raw (on-disk)
inode has 0x80 (128) bytes in size. Thereby, xanode lives in
extended space of inode. For example, if on-disk inode has 256
bytes then xanode is 128 bytes. The last four bytes of inode
(struct nilfs_inode) stores header of inline xanode.

Inline node structure:

 --------------------------------------------------------------
 |     ****      | HEADER | INLINE KEYS | FREE AREA | ENTRIES |
 --------------------------------------------------------------
 |<------ 128 bytes ----->|                                   |
 |<---------------------  inode  ---------------------------->|

The xanode begins with header that describes important details
about the node at whole. The main area of xanode keeps keys and
entries. Keys begin near after header and its grow towards
entries. The chain of keys is ended by termination marker
("end key") that is simply four bytes zeroed field. Entries
begin from xanode end and its grow from the end towards
"end key".

The xafile is metadata file that, basically, has such structure:

 +0                 +1       +2
+------------------+--------+------------------------------+
+ Group descriptor | Bitmap |       Chain of xanodes       |
+ block            | block  |                              |
+------------------+--------+------------------------------+

Thereby, xafile is simply storage of xanodes that can provide
xanode of some size (1KB, 2 KB or 4 KB) by identification
number (ID).

The xanode of xafile can be two types:
(1) xanode is shared between several inodes (shared xanode);
(2) tree of xanodes is dedicated to one inode (tree xanode).
Every on-disk inode stores ID of xanode (i_xattr). This ID number
is used for getting access to xanode.

If an inode has small number of xattrs with small size then
it will be used a shared xanode. The shared xanode has such
structure:

-------------------------
|         HEADER        |
-------------------------
|  LEAF KEYS (inode 1)  |
-------------------------
|  LEAF KEYS (*******)  |
-------------------------
|  LEAF KEYS (inode N)  |
-------------------------
|                       |
|       FREE AREA       |
|                       |
-------------------------
|    ENTRIES (inode N)  |
-------------------------
|    ENTRIES (*******)  |
-------------------------
|    ENTRIES (inode 1)  |
-------------------------

Otherwise, if an inode has many xattrs or xattrs of significant
size then it will be used xanodes' tree is dedicated to the inode.
The tree xanode has such structure:

----------------
|    HEADER    |
----------------
|  INDEX KEYS  |
----------------
|  LEAF KEYS   |
----------------
|              |
|  FREE AREA   |
|              |
----------------
|    ENTRIES   |
----------------

The tree xanode begins with header. Initially, empty xanode
contains reserved place for 8 index keys. First position keeps
index key that describes xanode itself. It is located leaf keys
after space that is reserved for index keys. Leaf keys grow
towards entries. The chain of keys is ended by termination marker
("end key"). Entries begin from xanode end and its grow from the
end towards "end key".

Thereby, xanode can be a mixture of index keys with [leaf key;
entry] pairs or it can contain only index keys. A xanode can
contain [8 | 16 | 32 |...| and so on] index keys. Firstly, when
inode has only one xanode in a tree then it hasn't any necessity
in index keys. First xanode in tree will keep index keys for
8 xanode are added after first one. Then number of index keys in
first xanode will be increased while first xanode is became
index xanode completely. Thereby, an inode keeps ID number of
first xanode in the tree and reading first xanode gives knowledge
about the next leaf node on the basis of index keys or searching
xattr (if first xanode keeps entries yet). Finally, after
exhausting of first inode by index keys, index keys are stored
in xanodes are described in first xanode, and so on.

/* Magic number of xafile node */
#define NILFS_XANODE_MAGIC              0x5841 /* XA */

/* Xafile node's types */
#define NILFS_INLINE_XANODE_TYPE        0
#define NILFS_SHARED_XANODE_TYPE        1
#define NILFS_TREE_XANODE_TYPE          2

/*
 * struct nilfs_inline_xanode_header - header of inline node
 * @magic: magic number for identification
 * @type: node type
 * @entries: number of entries in node
 * @log_node_size: log2(node size in bytes)
 * @flags: node flags
 */
struct nilfs_inline_xanode_header {
        __le16 magic;
        u8 type : 2;
        u8 entries : 6;
        u8 log_node_size : 4;
        u8 flags : 4;
} __packed;

/*
 * struct nilfs_shared_xanode_header - header of shared xanode
 * @magic: magic number for identification
 * @type: node type
 * @entries_low: low 6 bits of entries number in a node
 * @log_node_size: log2(node size in bytes)
 * @reserved1: reserved field
 * @flags: node flags
 * @entries_high: high 8 bits of entries number in a node
 * @refcount: node's reference count
 * @checksum: CRC32 of node
 * @hash: hash value of all attributes
 * @reserved2: reserved field
 */
struct nilfs_shared_xanode_header {
        __le16 magic;
        u8 type : 2;
        u8 entries_low : 6;
        u8 log_node_size : 4;
        u8 reserved1 : 4;
        u8 flags;
        u8 entries_high;
        __le16 refcount;
        __le32 checksum;
        __le32 hash;
        u8 reserved2[16];
} __packed;

/*
 * struct nilfs_tree_xanode_header - header of dedicated xanode
 * @magic: magic number for identification
 * @type: node type
 * @entries_low: low 6 bits of entries number in a node
 * @log_node_size: log2(node size in bytes)
 * @log_index_keys: log2(index keys max count)
 * @flags: node flags
 * @entries_high: high 8 bits of entries number in a node
 * @height: node height in the tree
 * @index_keys_low: low 4 bits of current index keys count
 * @index_keys_high: high 8 bits of current index keys count
 * @checksum: CRC32 of node
 * @prev: previous node ID number
 * @next: next node ID number
 * @reserved: reserved field
 */
struct nilfs_tree_xanode_header {
        __le16 magic;
        u8 type : 2;
        u8 entries_low : 6;
        u8 log_node_size : 4;
        u8 log_index_keys : 4;
        u8 flags;
        u8 entries_high;
        u8 height : 4;
        u8 index_keys_low : 4;
        u8 index_keys_high;
        __le32 checksum;
        __le64 prev;
        __le64 next;
        __le32 reserved;
} __packed;

/* Xattr key's flags */
#define NILFS_INLINE_NODE_KEY           0
#define NILFS_SHARED_XANODE_KEY         1
#define NILFS_XANODE_INDEX_KEY          2
#define NILFS_XANODE_LEAF_KEY           3

/*
 * struct nilfs_xattr_inline_key - xattr key for inline node
 * @type: key type
 * @flags: key's flags
 * @reserved: reserved field
 * @name_index: attribute name index
 * @name_hash: name hash
 * @entry_offset: entry offset inside the node
 * @entry_size: size of entry in bytes
 */
struct nilfs_xattr_inline_key {
        u8 type : 2;
        u8 flags : 6;
        u8 reserved;
        __le16 name_index;
        __le32 name_hash;
        __le16 entry_offset;
        __le16 entry_size;
} __packed;

/*
 * struct nilfs_xattr_shared_key - xattr key for shared node
 * @type: key type
 * @flags: key's flags
 * @reserved1: reserved field
 * @name_index: attribute name index
 * @name_hash: name hash
 * @entry_offset: entry offset inside the node
 * @entry_size: size of entry in bytes
 * @ino: inode ID
 */
struct nilfs_xattr_shared_key {
        u8 type : 2;
        u8 flags : 6;
        u8 reserved1;
        __le16 name_index;
        __le32 name_hash;
        __le16 entry_offset;
        __le16 entry_size;
        __le64 ino;
} __packed;

/*
 * struct nilfs_xattr_index_key - xattr index key
 * @type: key type
 * @flags: key's flags
 * @reserved1: reserved field
 * @name_index: attribute name index
 * @name_hash: name hash
 * @parent: parent node ID
 * @leaf: leaf node ID
 */
struct nilfs_xattr_index_key {
        u8 type : 2;
        u8 flags : 6;
        u8 reserved1;
        __le16 name_index;
        __le32 name_hash;
        __le64 parent;
        __le64 leaf;
} __packed;

/*
 * struct nilfs_xattr_leaf_key - xattr leaf key
 * @type: key type
 * @flags: key's flags
 * @reserved1: reserved field
 * @name_index: attribute name index
 * @name_hash: name hash
 * @entry_offset: entry offset inside the node
 * @entry_size: size of entry in bytes
 */
struct nilfs_xattr_leaf_key {
        u8 type : 2;
        u8 flags : 6;
        u8 reserved1;
        __le16 name_index;
        __le32 name_hash;
        __le16 entry_offset;
        __le16 entry_size;
} __packed;

/*
 *   Structure of xafile's node entry:
 *
 *   ---------------------------------------------------
 *   | name_len | name[variable_length] | binary value |
 *   ---------------------------------------------------
 *   |<----------------   entry_size  ---------------->|
 *
 *   The xafile's node entry begins with name_len field
 *   that define length of xattr name. Then it follows
 *   name's symbol chain. Entry is ended by xattr value.
 *   The whole entry's size is defined by entry_size
 *   field of the key structure.
 */

/*
 * struct nilfs_xattr_entry - entry of xafile's node
 * @name_len: name length
 * @name: attribute name
 */
struct nilfs_xattr_entry {
        __le16 name_len;
        char name[0];
} __packed;

So, I hope that this portion of information gives whole picture of the
implementation idea.

With the best regards,
Vyacheslav Dubeyko.


--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC] nilfs2: xattrs support implementation idea

[Ryusuke Konishi]

Hi Vyacheslav,
On Thu, 19 Sep 2013 14:47:49 +0400, Vyacheslav Dubeyko wrote:
> Hi Ryusuke,
> 
> On Thu, 2013-09-19 at 01:07 +0900, Ryusuke Konishi wrote:
> 
>> Could you share your implementation idea again before finishing your
>> patchset?
>> 
> 
> Yes, sure. It makes sense. Please, see description below.
> 
>> Is the basic idea same as the following RFC?
>> 
>> [1] http://www.mail-archive.com/linux-nilfs-u79uwXL29TY76Z2rM5mHXA@public.gmane.org/msg01298.html
>> 
> 
> I reworked this suggestion significantly. So, I describe my current
> approach and then we will elaborate a compromise solution. :)
> 
> So, I have such vision, currently.

Thank you for detail explanation.

I read through the design, but tonight I don't have enough time to
comment on it, so I will review it another day.

Before that, I have a request on the use of bit-fields in on-disk
structure definitions.

Please avoid using bit-fields in disk format definitions.  The
allocation of bit-fields depends on both compilers and architectures,
and this may sacrifice disk format compatibility.

Usually we define bit masks and bit shift values in order to write bit
operations for small size integer values.

For example,

struct nilfs_xxx {
        __le16 flags;
        ....
} __packed;

Two bit fields over the above "flags" field are define as below:

#define NILFS_XXX_FLAGS_NAME1_SHIFT    0
#define NILFS_XXX_FLAGS_NAME1_MASK     0x0003  /* a 2-bit-width field */
#define NILFS_XXX_FLAGS_NAME2_SHIFT    2
#define NILFS_XXX_FLAGS_NAME2_MASK     0x001c  /* a 3-bit-width field */
...


Regards,
Ryusuke Konishi


> There two places of storing xattrs:
> (1) inline xattr nodes (xanodes);
> (2) xattr file (xafile).
> 
> The inline xanode is extention of inode space. The raw (on-disk)
> inode has 0x80 (128) bytes in size. Thereby, xanode lives in
> extended space of inode. For example, if on-disk inode has 256
> bytes then xanode is 128 bytes. The last four bytes of inode
> (struct nilfs_inode) stores header of inline xanode.
> 
> Inline node structure:
> 
>  --------------------------------------------------------------
>  |     ****      | HEADER | INLINE KEYS | FREE AREA | ENTRIES |
>  --------------------------------------------------------------
>  |<------ 128 bytes ----->|                                   |
>  |<---------------------  inode  ---------------------------->|
> 
> The xanode begins with header that describes important details
> about the node at whole. The main area of xanode keeps keys and
> entries. Keys begin near after header and its grow towards
> entries. The chain of keys is ended by termination marker
> ("end key") that is simply four bytes zeroed field. Entries
> begin from xanode end and its grow from the end towards
> "end key".
> 
> The xafile is metadata file that, basically, has such structure:
> 
>  +0                 +1       +2
> +------------------+--------+------------------------------+
> + Group descriptor | Bitmap |       Chain of xanodes       |
> + block            | block  |                              |
> +------------------+--------+------------------------------+
> 
> Thereby, xafile is simply storage of xanodes that can provide
> xanode of some size (1KB, 2 KB or 4 KB) by identification
> number (ID).
> 
> The xanode of xafile can be two types:
> (1) xanode is shared between several inodes (shared xanode);
> (2) tree of xanodes is dedicated to one inode (tree xanode).
> Every on-disk inode stores ID of xanode (i_xattr). This ID number
> is used for getting access to xanode.
> 
> If an inode has small number of xattrs with small size then
> it will be used a shared xanode. The shared xanode has such
> structure:
> 
> -------------------------
> |         HEADER        |
> -------------------------
> |  LEAF KEYS (inode 1)  |
> -------------------------
> |  LEAF KEYS (*******)  |
> -------------------------
> |  LEAF KEYS (inode N)  |
> -------------------------
> |                       |
> |       FREE AREA       |
> |                       |
> -------------------------
> |    ENTRIES (inode N)  |
> -------------------------
> |    ENTRIES (*******)  |
> -------------------------
> |    ENTRIES (inode 1)  |
> -------------------------
> 
> Otherwise, if an inode has many xattrs or xattrs of significant
> size then it will be used xanodes' tree is dedicated to the inode.
> The tree xanode has such structure:
> 
> ----------------
> |    HEADER    |
> ----------------
> |  INDEX KEYS  |
> ----------------
> |  LEAF KEYS   |
> ----------------
> |              |
> |  FREE AREA   |
> |              |
> ----------------
> |    ENTRIES   |
> ----------------
> 
> The tree xanode begins with header. Initially, empty xanode
> contains reserved place for 8 index keys. First position keeps
> index key that describes xanode itself. It is located leaf keys
> after space that is reserved for index keys. Leaf keys grow
> towards entries. The chain of keys is ended by termination marker
> ("end key"). Entries begin from xanode end and its grow from the
> end towards "end key".
> 
> Thereby, xanode can be a mixture of index keys with [leaf key;
> entry] pairs or it can contain only index keys. A xanode can
> contain [8 | 16 | 32 |...| and so on] index keys. Firstly, when
> inode has only one xanode in a tree then it hasn't any necessity
> in index keys. First xanode in tree will keep index keys for
> 8 xanode are added after first one. Then number of index keys in
> first xanode will be increased while first xanode is became
> index xanode completely. Thereby, an inode keeps ID number of
> first xanode in the tree and reading first xanode gives knowledge
> about the next leaf node on the basis of index keys or searching
> xattr (if first xanode keeps entries yet). Finally, after
> exhausting of first inode by index keys, index keys are stored
> in xanodes are described in first xanode, and so on.
> 
> /* Magic number of xafile node */
> #define NILFS_XANODE_MAGIC              0x5841 /* XA */
> 
> /* Xafile node's types */
> #define NILFS_INLINE_XANODE_TYPE        0
> #define NILFS_SHARED_XANODE_TYPE        1
> #define NILFS_TREE_XANODE_TYPE          2
> 
> /*
>  * struct nilfs_inline_xanode_header - header of inline node
>  * @magic: magic number for identification
>  * @type: node type
>  * @entries: number of entries in node
>  * @log_node_size: log2(node size in bytes)
>  * @flags: node flags
>  */
> struct nilfs_inline_xanode_header {
>         __le16 magic;
>         u8 type : 2;
>         u8 entries : 6;
>         u8 log_node_size : 4;
>         u8 flags : 4;
> } __packed;
> 
> /*
>  * struct nilfs_shared_xanode_header - header of shared xanode
>  * @magic: magic number for identification
>  * @type: node type
>  * @entries_low: low 6 bits of entries number in a node
>  * @log_node_size: log2(node size in bytes)
>  * @reserved1: reserved field
>  * @flags: node flags
>  * @entries_high: high 8 bits of entries number in a node
>  * @refcount: node's reference count
>  * @checksum: CRC32 of node
>  * @hash: hash value of all attributes
>  * @reserved2: reserved field
>  */
> struct nilfs_shared_xanode_header {
>         __le16 magic;
>         u8 type : 2;
>         u8 entries_low : 6;
>         u8 log_node_size : 4;
>         u8 reserved1 : 4;
>         u8 flags;
>         u8 entries_high;
>         __le16 refcount;
>         __le32 checksum;
>         __le32 hash;
>         u8 reserved2[16];
> } __packed;
> 
> /*
>  * struct nilfs_tree_xanode_header - header of dedicated xanode
>  * @magic: magic number for identification
>  * @type: node type
>  * @entries_low: low 6 bits of entries number in a node
>  * @log_node_size: log2(node size in bytes)
>  * @log_index_keys: log2(index keys max count)
>  * @flags: node flags
>  * @entries_high: high 8 bits of entries number in a node
>  * @height: node height in the tree
>  * @index_keys_low: low 4 bits of current index keys count
>  * @index_keys_high: high 8 bits of current index keys count
>  * @checksum: CRC32 of node
>  * @prev: previous node ID number
>  * @next: next node ID number
>  * @reserved: reserved field
>  */
> struct nilfs_tree_xanode_header {
>         __le16 magic;
>         u8 type : 2;
>         u8 entries_low : 6;
>         u8 log_node_size : 4;
>         u8 log_index_keys : 4;
>         u8 flags;
>         u8 entries_high;
>         u8 height : 4;
>         u8 index_keys_low : 4;
>         u8 index_keys_high;
>         __le32 checksum;
>         __le64 prev;
>         __le64 next;
>         __le32 reserved;
> } __packed;
> 
> /* Xattr key's flags */
> #define NILFS_INLINE_NODE_KEY           0
> #define NILFS_SHARED_XANODE_KEY         1
> #define NILFS_XANODE_INDEX_KEY          2
> #define NILFS_XANODE_LEAF_KEY           3
> 
> /*
>  * struct nilfs_xattr_inline_key - xattr key for inline node
>  * @type: key type
>  * @flags: key's flags
>  * @reserved: reserved field
>  * @name_index: attribute name index
>  * @name_hash: name hash
>  * @entry_offset: entry offset inside the node
>  * @entry_size: size of entry in bytes
>  */
> struct nilfs_xattr_inline_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved;
>         __le16 name_index;
>         __le32 name_hash;
>         __le16 entry_offset;
>         __le16 entry_size;
> } __packed;
> 
> /*
>  * struct nilfs_xattr_shared_key - xattr key for shared node
>  * @type: key type
>  * @flags: key's flags
>  * @reserved1: reserved field
>  * @name_index: attribute name index
>  * @name_hash: name hash
>  * @entry_offset: entry offset inside the node
>  * @entry_size: size of entry in bytes
>  * @ino: inode ID
>  */
> struct nilfs_xattr_shared_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved1;
>         __le16 name_index;
>         __le32 name_hash;
>         __le16 entry_offset;
>         __le16 entry_size;
>         __le64 ino;
> } __packed;
> 
> /*
>  * struct nilfs_xattr_index_key - xattr index key
>  * @type: key type
>  * @flags: key's flags
>  * @reserved1: reserved field
>  * @name_index: attribute name index
>  * @name_hash: name hash
>  * @parent: parent node ID
>  * @leaf: leaf node ID
>  */
> struct nilfs_xattr_index_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved1;
>         __le16 name_index;
>         __le32 name_hash;
>         __le64 parent;
>         __le64 leaf;
> } __packed;
> 
> /*
>  * struct nilfs_xattr_leaf_key - xattr leaf key
>  * @type: key type
>  * @flags: key's flags
>  * @reserved1: reserved field
>  * @name_index: attribute name index
>  * @name_hash: name hash
>  * @entry_offset: entry offset inside the node
>  * @entry_size: size of entry in bytes
>  */
> struct nilfs_xattr_leaf_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved1;
>         __le16 name_index;
>         __le32 name_hash;
>         __le16 entry_offset;
>         __le16 entry_size;
> } __packed;
> 
> /*
>  *   Structure of xafile's node entry:
>  *
>  *   ---------------------------------------------------
>  *   | name_len | name[variable_length] | binary value |
>  *   ---------------------------------------------------
>  *   |<----------------   entry_size  ---------------->|
>  *
>  *   The xafile's node entry begins with name_len field
>  *   that define length of xattr name. Then it follows
>  *   name's symbol chain. Entry is ended by xattr value.
>  *   The whole entry's size is defined by entry_size
>  *   field of the key structure.
>  */
> 
> /*
>  * struct nilfs_xattr_entry - entry of xafile's node
>  * @name_len: name length
>  * @name: attribute name
>  */
> struct nilfs_xattr_entry {
>         __le16 name_len;
>         char name[0];
> } __packed;
> 
> So, I hope that this portion of information gives whole picture of the
> implementation idea.
> 
> With the best regards,
> Vyacheslav Dubeyko.
> 
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC] nilfs2: xattrs support implementation idea

[Ryusuke Konishi]

Hi Vyacheslav,

Here is my additional comments on your xattrs support RFC.

> The xanode of xafile can be two types:
> (1) xanode is shared between several inodes (shared xanode);
> (2) tree of xanodes is dedicated to one inode (tree xanode).
> Every on-disk inode stores ID of xanode (i_xattr). This ID number
> is used for getting access to xanode.

The shared xanode you defined looks to be intended to share a disk
block from several inodes (for efficiency of disk block usage) since
nilfs_xattr_shared_key has a backpointer, an inode number field.

I think you would rather consider sharing the same (small) attribute
content among many inodes because the same attribute set is often
associated to many files or directories widely, such as tree wide or
file system wide.  For this type of block sharing, no inode number is
needed in the attribute payload.

For the tree of xanodes, it seems a bit inefficent because it is
implemented over xafile (meta data file), and this introduces
threefold tree lookups to access the target disk block:

  xanode tree lookup --> xafile btree lookup --> DAT btree lookup

Simple block chaining over xafile may be better for most cases.

I think the tree-over-xafile implementation is a candidate, but please
try considering ideas to replace the the tree based lookup into an
index based access over xafile.

For the inline xattr, I think it should not be mandatory.  It should
be an option for users who wants faster accesses to the extended
attributes and can accept reformat of the file system with 256-bit
size inodes for that purpose.


I will add more detail comments below.


> /*
>  * struct nilfs_inline_xanode_header - header of inline node
>  * @magic: magic number for identification
>  * @type: node type
>  * @entries: number of entries in node
>  * @log_node_size: log2(node size in bytes)

log2(node size in bytes) - 10 ?

4-bit width log_node_size only can represent 0~15 bytes.

>  * @flags: node flags
>  */
> struct nilfs_inline_xanode_header {
>         __le16 magic;

Is this magic field necessary?   The reserved field
at the end of the current disk inode is valuable.

Setting the same magic number to all inodes seems wasteful.

>         u8 type : 2;
>         u8 entries : 6;
>         u8 log_node_size : 4;
>         u8 flags : 4;
> } __packed;


> struct nilfs_tree_xanode_header {
>         __le16 magic;
>         u8 type : 2;
>         u8 entries_low : 6;
>         u8 log_node_size : 4;
>         u8 log_index_keys : 4;
>         u8 flags;
>         u8 entries_high;
>         u8 height : 4;
>         u8 index_keys_low : 4;
>         u8 index_keys_high;
>         __le32 checksum;
>         __le64 prev;
>         __le64 next;
>         __le32 reserved;
> } __packed;

This "prev" and "next" member variables are not aligned to 8-byte
boundary ("prev" has +12 bytes offset and "next" has +20 bytes
offset).

It is preferable to think memory alignment in __packed structures to
avoid memory alignment error or performance penalty some architectures
may suffer.


> /*
>  * struct nilfs_xattr_inline_key - xattr key for inline node
>  * @type: key type
>  * @flags: key's flags
>  * @reserved: reserved field
>  * @name_index: attribute name index
>  * @name_hash: name hash
>  * @entry_offset: entry offset inside the node
>  * @entry_size: size of entry in bytes
>  */
> struct nilfs_xattr_inline_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved;
>         __le16 name_index;
>         __le32 name_hash;
>         __le16 entry_offset;
>         __le16 entry_size;
> } __packed;

For what purpose is the type field used ?

> struct nilfs_xattr_shared_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved1;
>         __le16 name_index;
>         __le32 name_hash;
>         __le16 entry_offset;
>         __le16 entry_size;
>         __le64 ino;
> } __packed;

The "ino" field has +12 bytes offset and is not aligned to 8 byte
boundary.

Again, the type field.  What is the difference between the type field
and the flags field ?

> struct nilfs_xattr_index_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved1;
>         __le16 name_index;
>         __le32 name_hash;
>         __le64 parent;
>         __le64 leaf;
> } __packed;

Why is the "parent" field required ?

The size of this structure is 24 bytes.
It fits in 16 bytes structure if the parent field is eliminable.
Otherwise, you need 8 more pad bytes to align on-disk structures 
to 8 byte boundary.

> struct nilfs_xattr_leaf_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved1;
>         __le16 name_index;
>         __le32 name_hash;
>         __le16 entry_offset;
>         __le16 entry_size;
> } __packed;

This structure also needs pad bytes.

> struct nilfs_xattr_entry {
>         __le16 name_len;
>         char name[0];
> } __packed;

Note that name_len must be aligned properly in the group of the
nilfs_xattr_entry structure even though the name field has a variable
size.

You will need alignment calculation as NILFS_DIR_REC_LEN() macro
provides for directory entries.


With regards,
Ryusuke Konishi


On Thu, 19 Sep 2013 14:47:49 +0400, Vyacheslav Dubeyko wrote:
> I reworked this suggestion significantly. So, I describe my current
> approach and then we will elaborate a compromise solution. :)
> 
> So, I have such vision, currently.
> 
> There two places of storing xattrs:
> (1) inline xattr nodes (xanodes);
> (2) xattr file (xafile).
> 
> The inline xanode is extention of inode space. The raw (on-disk)
> inode has 0x80 (128) bytes in size. Thereby, xanode lives in
> extended space of inode. For example, if on-disk inode has 256
> bytes then xanode is 128 bytes. The last four bytes of inode
> (struct nilfs_inode) stores header of inline xanode.
> 
> Inline node structure:
> 
>  --------------------------------------------------------------
>  |     ****      | HEADER | INLINE KEYS | FREE AREA | ENTRIES |
>  --------------------------------------------------------------
>  |<------ 128 bytes ----->|                                   |
>  |<---------------------  inode  ---------------------------->|
> 
> The xanode begins with header that describes important details
> about the node at whole. The main area of xanode keeps keys and
> entries. Keys begin near after header and its grow towards
> entries. The chain of keys is ended by termination marker
> ("end key") that is simply four bytes zeroed field. Entries
> begin from xanode end and its grow from the end towards
> "end key".
> 
> The xafile is metadata file that, basically, has such structure:
> 
>  +0                 +1       +2
> +------------------+--------+------------------------------+
> + Group descriptor | Bitmap |       Chain of xanodes       |
> + block            | block  |                              |
> +------------------+--------+------------------------------+
> 
> Thereby, xafile is simply storage of xanodes that can provide
> xanode of some size (1KB, 2 KB or 4 KB) by identification
> number (ID).
> 
> The xanode of xafile can be two types:
> (1) xanode is shared between several inodes (shared xanode);
> (2) tree of xanodes is dedicated to one inode (tree xanode).
> Every on-disk inode stores ID of xanode (i_xattr). This ID number
> is used for getting access to xanode.
> 
> If an inode has small number of xattrs with small size then
> it will be used a shared xanode. The shared xanode has such
> structure:
> 
> -------------------------
> |         HEADER        |
> -------------------------
> |  LEAF KEYS (inode 1)  |
> -------------------------
> |  LEAF KEYS (*******)  |
> -------------------------
> |  LEAF KEYS (inode N)  |
> -------------------------
> |                       |
> |       FREE AREA       |
> |                       |
> -------------------------
> |    ENTRIES (inode N)  |
> -------------------------
> |    ENTRIES (*******)  |
> -------------------------
> |    ENTRIES (inode 1)  |
> -------------------------
> 
> Otherwise, if an inode has many xattrs or xattrs of significant
> size then it will be used xanodes' tree is dedicated to the inode.
> The tree xanode has such structure:
> 
> ----------------
> |    HEADER    |
> ----------------
> |  INDEX KEYS  |
> ----------------
> |  LEAF KEYS   |
> ----------------
> |              |
> |  FREE AREA   |
> |              |
> ----------------
> |    ENTRIES   |
> ----------------
> 
> The tree xanode begins with header. Initially, empty xanode
> contains reserved place for 8 index keys. First position keeps
> index key that describes xanode itself. It is located leaf keys
> after space that is reserved for index keys. Leaf keys grow
> towards entries. The chain of keys is ended by termination marker
> ("end key"). Entries begin from xanode end and its grow from the
> end towards "end key".
> 
> Thereby, xanode can be a mixture of index keys with [leaf key;
> entry] pairs or it can contain only index keys. A xanode can
> contain [8 | 16 | 32 |...| and so on] index keys. Firstly, when
> inode has only one xanode in a tree then it hasn't any necessity
> in index keys. First xanode in tree will keep index keys for
> 8 xanode are added after first one. Then number of index keys in
> first xanode will be increased while first xanode is became
> index xanode completely. Thereby, an inode keeps ID number of
> first xanode in the tree and reading first xanode gives knowledge
> about the next leaf node on the basis of index keys or searching
> xattr (if first xanode keeps entries yet). Finally, after
> exhausting of first inode by index keys, index keys are stored
> in xanodes are described in first xanode, and so on.
> 
> /* Magic number of xafile node */
> #define NILFS_XANODE_MAGIC              0x5841 /* XA */
> 
> /* Xafile node's types */
> #define NILFS_INLINE_XANODE_TYPE        0
> #define NILFS_SHARED_XANODE_TYPE        1
> #define NILFS_TREE_XANODE_TYPE          2
> 
> /*
>  * struct nilfs_inline_xanode_header - header of inline node
>  * @magic: magic number for identification
>  * @type: node type
>  * @entries: number of entries in node
>  * @log_node_size: log2(node size in bytes)
>  * @flags: node flags
>  */
> struct nilfs_inline_xanode_header {
>         __le16 magic;
>         u8 type : 2;
>         u8 entries : 6;
>         u8 log_node_size : 4;
>         u8 flags : 4;
> } __packed;
> 
> /*
>  * struct nilfs_shared_xanode_header - header of shared xanode
>  * @magic: magic number for identification
>  * @type: node type
>  * @entries_low: low 6 bits of entries number in a node
>  * @log_node_size: log2(node size in bytes)
>  * @reserved1: reserved field
>  * @flags: node flags
>  * @entries_high: high 8 bits of entries number in a node
>  * @refcount: node's reference count
>  * @checksum: CRC32 of node
>  * @hash: hash value of all attributes
>  * @reserved2: reserved field
>  */
> struct nilfs_shared_xanode_header {
>         __le16 magic;
>         u8 type : 2;
>         u8 entries_low : 6;
>         u8 log_node_size : 4;
>         u8 reserved1 : 4;
>         u8 flags;
>         u8 entries_high;
>         __le16 refcount;
>         __le32 checksum;
>         __le32 hash;
>         u8 reserved2[16];
> } __packed;
> 
> /*
>  * struct nilfs_tree_xanode_header - header of dedicated xanode
>  * @magic: magic number for identification
>  * @type: node type
>  * @entries_low: low 6 bits of entries number in a node
>  * @log_node_size: log2(node size in bytes)
>  * @log_index_keys: log2(index keys max count)
>  * @flags: node flags
>  * @entries_high: high 8 bits of entries number in a node
>  * @height: node height in the tree
>  * @index_keys_low: low 4 bits of current index keys count
>  * @index_keys_high: high 8 bits of current index keys count
>  * @checksum: CRC32 of node
>  * @prev: previous node ID number
>  * @next: next node ID number
>  * @reserved: reserved field
>  */
> struct nilfs_tree_xanode_header {
>         __le16 magic;
>         u8 type : 2;
>         u8 entries_low : 6;
>         u8 log_node_size : 4;
>         u8 log_index_keys : 4;
>         u8 flags;
>         u8 entries_high;
>         u8 height : 4;
>         u8 index_keys_low : 4;
>         u8 index_keys_high;
>         __le32 checksum;
>         __le64 prev;
>         __le64 next;
>         __le32 reserved;
> } __packed;
> 
> /* Xattr key's flags */
> #define NILFS_INLINE_NODE_KEY           0
> #define NILFS_SHARED_XANODE_KEY         1
> #define NILFS_XANODE_INDEX_KEY          2
> #define NILFS_XANODE_LEAF_KEY           3
> 
> /*
>  * struct nilfs_xattr_inline_key - xattr key for inline node
>  * @type: key type
>  * @flags: key's flags
>  * @reserved: reserved field
>  * @name_index: attribute name index
>  * @name_hash: name hash
>  * @entry_offset: entry offset inside the node
>  * @entry_size: size of entry in bytes
>  */
> struct nilfs_xattr_inline_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved;
>         __le16 name_index;
>         __le32 name_hash;
>         __le16 entry_offset;
>         __le16 entry_size;
> } __packed;
> 
> /*
>  * struct nilfs_xattr_shared_key - xattr key for shared node
>  * @type: key type
>  * @flags: key's flags
>  * @reserved1: reserved field
>  * @name_index: attribute name index
>  * @name_hash: name hash
>  * @entry_offset: entry offset inside the node
>  * @entry_size: size of entry in bytes
>  * @ino: inode ID
>  */
> struct nilfs_xattr_shared_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved1;
>         __le16 name_index;
>         __le32 name_hash;
>         __le16 entry_offset;
>         __le16 entry_size;
>         __le64 ino;
> } __packed;
> 
> /*
>  * struct nilfs_xattr_index_key - xattr index key
>  * @type: key type
>  * @flags: key's flags
>  * @reserved1: reserved field
>  * @name_index: attribute name index
>  * @name_hash: name hash
>  * @parent: parent node ID
>  * @leaf: leaf node ID
>  */
> struct nilfs_xattr_index_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved1;
>         __le16 name_index;
>         __le32 name_hash;
>         __le64 parent;
>         __le64 leaf;
> } __packed;
> 
> /*
>  * struct nilfs_xattr_leaf_key - xattr leaf key
>  * @type: key type
>  * @flags: key's flags
>  * @reserved1: reserved field
>  * @name_index: attribute name index
>  * @name_hash: name hash
>  * @entry_offset: entry offset inside the node
>  * @entry_size: size of entry in bytes
>  */
> struct nilfs_xattr_leaf_key {
>         u8 type : 2;
>         u8 flags : 6;
>         u8 reserved1;
>         __le16 name_index;
>         __le32 name_hash;
>         __le16 entry_offset;
>         __le16 entry_size;
> } __packed;
> 
> /*
>  *   Structure of xafile's node entry:
>  *
>  *   ---------------------------------------------------
>  *   | name_len | name[variable_length] | binary value |
>  *   ---------------------------------------------------
>  *   |<----------------   entry_size  ---------------->|
>  *
>  *   The xafile's node entry begins with name_len field
>  *   that define length of xattr name. Then it follows
>  *   name's symbol chain. Entry is ended by xattr value.
>  *   The whole entry's size is defined by entry_size
>  *   field of the key structure.
>  */
> 
> /*
>  * struct nilfs_xattr_entry - entry of xafile's node
>  * @name_len: name length
>  * @name: attribute name
>  */
> struct nilfs_xattr_entry {
>         __le16 name_len;
>         char name[0];
> } __packed;
> 
> So, I hope that this portion of information gives whole picture of the
> implementation idea.
> 
> With the best regards,
> Vyacheslav Dubeyko.
> 
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC] nilfs2: xattrs support implementation idea

[Vyacheslav Dubeyko]

Hi Ryusuke,

On Fri, 2013-09-20 at 03:15 +0900, Ryusuke Konishi wrote:

> 
>Before that, I have a request on the use of bit-fields in on-disk
>structure definitions.
>

Ok. It's reasonable request. I'll take it into account.


On Tue, 2013-09-24 at 00:07 +0900, Ryusuke Konishi wrote:

> The shared xanode you defined looks to be intended to share a disk
> block from several inodes (for efficiency of disk block usage) since
> nilfs_xattr_shared_key has a backpointer, an inode number field.
> 
> I think you would rather consider sharing the same (small) attribute
> content among many inodes because the same attribute set is often
> associated to many files or directories widely, such as tree wide or
> file system wide.  For this type of block sharing, no inode number is
> needed in the attribute payload.
> 

So, maybe I miss something but I don't quite follow your thought about
attribute content sharing between several inodes. What do you mean?

I have such understanding. The xattr is a pair of a name and a binary
stream. So, of course, many inodes have xattrs with the same name. But
does it mean that such xattrs have identical binary streams? I doubt
that identity of xattrs' binary streams is very frequent event. For
example, many inodes can have system.posix_acl_access ACL but content of
binary streams will be different (namely, permitted/denied permissions
set). Moreover, of course, it is possible to use such scheme as sharing
identical xattrs' content between several inodes. But if we need in
independent xattr's content update for some inode then we will need to
use something likewise COW policy. I suppose that it can be complicated
technique.

Yes, I dislike also the necessity to have inode number in the key that
it is used in shared xanode. But inode number is essential for the
shared xanode case. Otherwise, sorting of xattr's keys will be made only
on the basis of hash of the name. As a result, we can't distinguish
xattrs of different inodes because xattrs' keys will be in unsorted
order from the point of inodes number. So, we can't make correctly such
operations as listxattr and removexattr for the shared xanode case.

But I think that shared xanode can be useful technique for the case of
unavailability of inline xanode for old NILFS2 volumes. I suppose, this
technique can be efficient for the case of small xattrs as from
performance as from GC point of view. I think about shared xanode
concept as a temporary storage for inode's xattrs while the count and
size of xattrs are small. It can be inefficient to store inode's xattrs
in shared xanode from some moment of time. If whole size (or count) of
xattrs achieve some threshold then it migrates from shared xanode into
inode's dedicated xanode's tree. Of course, also it needs to take into
consideration the synchronization overhead for the shared xanode case.

> For the tree of xanodes, it seems a bit inefficent because it is
> implemented over xafile (meta data file), and this introduces
> threefold tree lookups to access the target disk block:
> 
>   xanode tree lookup --> xafile btree lookup --> DAT btree lookup
> 
> Simple block chaining over xafile may be better for most cases.
> 
> I think the tree-over-xafile implementation is a candidate, but please
> try considering ideas to replace the the tree based lookup into an
> index based access over xafile.
> 

First of all, in my concept the xafile is aggregate of xanodes. Every
xanode is accessed by index in xafile. So, namely index based access
over xafile is used in my implementation. The xafile as container of
xanodes is important concept from the GC point of view. Data blocks and
xattr blocks have different nature of aging. So, mixture of data and
xattr blocks can be not GC friendly. Access to xanodes by means of index
over xafile is important concept too. Because namely index of xanode in
xafile is stored as xanode number in header and other structures. So,
xafile as metadata file hides problem of translation logical index
(xanode number) into real block number.

About lookup... On-disk inode keeps xattrs by itself in the inline
xanode case. So, we don't need to search an inline xanode in such case.
An inode keeps xanode number (or index of xafile's node) in the case of
shared xanode. It means that we have metadata file lookup overhead only
(xafile btree lookup --> DAT btree lookup). An inode keeps xanode number
of a first xanode of dedicated xanodes' tree. Only this inode possesses
by such dedicated tree. So, dedicated tree will not big in ordinary
case. The dedicated xanodes' tree can be big if an inode will have very
big count of xattrs (or xattrs with big content size). Every xanode has
small reserved space for index keys. But, initially, only first xanode
is used for storing index keys. And reserved space for index keys is
growing in the case of necessity to have more index keys. I suppose that
one index level will be enough for most cases. So, usually, reading of
first xanode will be enough for getting knowledge about all leaf xanodes
in dedicated xanodes' tree.

Yes, (xafile btree lookup --> DAT btree lookup) can be the reason of
overhead. But I think that we need to optimize this overhead for all
use-cases, anyway. Theoretically, it is possible to implement additional
technique. But I think that it makes sense to use existing NILFS2
internal techniques.

> For the inline xattr, I think it should not be mandatory.  It should
> be an option for users who wants faster accesses to the extended
> attributes and can accept reformat of the file system with 256-bit
> size inodes for that purpose.
> 

Yes, sure. Inline xattrs are optional. If a user hasn't opportunity (or
desire) for reformat NILFS2 volume then it will not use inline xattrs
completely.

> > /*
> >  * struct nilfs_inline_xanode_header - header of inline node
> >  * @magic: magic number for identification
> >  * @type: node type
> >  * @entries: number of entries in node
> >  * @log_node_size: log2(node size in bytes)
> 
> log2(node size in bytes) - 10 ?
> 
> 4-bit width log_node_size only can represent 0~15 bytes.
> 

I think that xafile's xanode size can be in range: 1KB (1024) - 32KB
(32768). I suppose that maximum value in 32KB is enough for all cases.
So, it needs 15 bytes for 32KB node size.

> >  * @flags: node flags
> >  */
> > struct nilfs_inline_xanode_header {
> >         __le16 magic;
> 
> Is this magic field necessary?   The reserved field
> at the end of the current disk inode is valuable.
> 
> Setting the same magic number to all inodes seems wasteful.
> 

The magic field is useful for consistency checking. And magic number
keeps for the whole xanode. I don't think that 2-byte value wastes 4KB
xanode, for example. Moreover, I use magic for detecting presence of
inline xanode in extended space of on-disk inode. Of course, we can
leave padding field at the end of on-disk inode untouched. But it needs
to use another way of detecting inline xanode presence. What do you
suggest?

> >         u8 type : 2;
> >         u8 entries : 6;
> >         u8 log_node_size : 4;
> >         u8 flags : 4;
> > } __packed;
> 
> 
> > struct nilfs_tree_xanode_header {
> >         __le16 magic;
> >         u8 type : 2;
> >         u8 entries_low : 6;
> >         u8 log_node_size : 4;
> >         u8 log_index_keys : 4;
> >         u8 flags;
> >         u8 entries_high;
> >         u8 height : 4;
> >         u8 index_keys_low : 4;
> >         u8 index_keys_high;
> >         __le32 checksum;
> >         __le64 prev;
> >         __le64 next;
> >         __le32 reserved;
> > } __packed;
> 
> This "prev" and "next" member variables are not aligned to 8-byte
> boundary ("prev" has +12 bytes offset and "next" has +20 bytes
> offset).
> 
> It is preferable to think memory alignment in __packed structures to
> avoid memory alignment error or performance penalty some architectures
> may suffer.
> 

Ok. I agree. I'll take it into account.

> 
> > /*
> >  * struct nilfs_xattr_inline_key - xattr key for inline node
> >  * @type: key type
> >  * @flags: key's flags
> >  * @reserved: reserved field
> >  * @name_index: attribute name index
> >  * @name_hash: name hash
> >  * @entry_offset: entry offset inside the node
> >  * @entry_size: size of entry in bytes
> >  */
> > struct nilfs_xattr_inline_key {
> >         u8 type : 2;
> >         u8 flags : 6;
> >         u8 reserved;
> >         __le16 name_index;
> >         __le32 name_hash;
> >         __le16 entry_offset;
> >         __le16 entry_size;
> > } __packed;
> 
> For what purpose is the type field used ?

The purpose of "type" field is to distinguish different type of xanode's
headers or keys. Namely, for example, detecting that we have header of
inline xanode, shared xanode or tree xanode.

> 
> > struct nilfs_xattr_shared_key {
> >         u8 type : 2;
> >         u8 flags : 6;
> >         u8 reserved1;
> >         __le16 name_index;
> >         __le32 name_hash;
> >         __le16 entry_offset;
> >         __le16 entry_size;
> >         __le64 ino;
> > } __packed;
> 
> The "ino" field has +12 bytes offset and is not aligned to 8 byte
> boundary.
> 

Ok. Agree.

> Again, the type field.  What is the difference between the type field
> and the flags field ?
> 

The type field is part of flags field. So, it can be extracted from
flags field by means of mask.

> > struct nilfs_xattr_index_key {
> >         u8 type : 2;
> >         u8 flags : 6;
> >         u8 reserved1;
> >         __le16 name_index;
> >         __le32 name_hash;
> >         __le64 parent;
> >         __le64 leaf;
> > } __packed;
> 
> Why is the "parent" field required ?
> 
> The size of this structure is 24 bytes.
> It fits in 16 bytes structure if the parent field is eliminable.
> Otherwise, you need 8 more pad bytes to align on-disk structures 
> to 8 byte boundary.

I need to think over the real necessity of "parent" field. But my
initial intention was to have backpointer on index xanode that describe
this xanode as leaf. But now I doubt that keeps this value in an index
key is a good idea. Maybe, it makes sense to keep this value in xanode's
header in the case of real necessity in "parent" backpointer. So, I need
to reflect about it.

> 
> > struct nilfs_xattr_leaf_key {
> >         u8 type : 2;
> >         u8 flags : 6;
> >         u8 reserved1;
> >         __le16 name_index;
> >         __le32 name_hash;
> >         __le16 entry_offset;
> >         __le16 entry_size;
> > } __packed;
> 
> This structure also needs pad bytes.
> 

Ok.

> > struct nilfs_xattr_entry {
> >         __le16 name_len;
> >         char name[0];
> > } __packed;
> 
> Note that name_len must be aligned properly in the group of the
> nilfs_xattr_entry structure even though the name field has a variable
> size.
> 
> You will need alignment calculation as NILFS_DIR_REC_LEN() macro
> provides for directory entries.
> 

Ok. I'll take it into account.

Thanks,
Vyacheslav Dubeyko.


--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC] nilfs2: xattrs support implementation idea

[Ryusuke Konishi]

On Thu, 26 Sep 2013 18:07:59 +0400, Vyacheslav Dubeyko wrote:
> On Tue, 2013-09-24 at 00:07 +0900, Ryusuke Konishi wrote:
> 
>> The shared xanode you defined looks to be intended to share a disk
>> block from several inodes (for efficiency of disk block usage) since
>> nilfs_xattr_shared_key has a backpointer, an inode number field.
>> 
>> I think you would rather consider sharing the same (small) attribute
>> content among many inodes because the same attribute set is often
>> associated to many files or directories widely, such as tree wide or
>> file system wide.  For this type of block sharing, no inode number is
>> needed in the attribute payload.
>> 
> 
> So, maybe I miss something but I don't quite follow your thought about
> attribute content sharing between several inodes. What do you mean?

I meant allowing multiple inodes to share the same set of extended
attributes which contains same keys and values.  This is what
ext2/ext3/ext4 file systems trying to do.

> I have such understanding. The xattr is a pair of a name and a binary
> stream. So, of course, many inodes have xattrs with the same name. But
> does it mean that such xattrs have identical binary streams? I doubt
> that identity of xattrs' binary streams is very frequent event.

I measured how much xattrs are duplicating by using getfattr command
on my fedora 19 system.


 # getfattr -RPh -e hex -dm '.*' / 2>/dev/null | sed -e '/^\#/d' | awk 'BEGIN{RS="";OFS=""}{$1=$1;print}' | wc -l
 143103

The system has 143103 extended attibutes sets, where sed command is
removing comment line, awk command is joining multiple extended
attributes per file or directory, and wc command is used to count
them.

Then, the number of extended attribute sets was reduced to 441 after I
removed duplicated ones with sort and uniq commands:

 # getfattr -RPh -e hex -dm '.*' / 2>/dev/null | sed -e '/^\#/d' |awk 'BEGIN{RS="";OFS=""}{$1=$1;print}' | sort | uniq | wc -l
 441

Although POSIX ACLs are not handled in this measurement (we can use
getfacl command for similiar purpose), sharing the same extended
attribute content looks to be effective to reduce the on-disk data
size.


I also measured the total size of extended attibutes on the system:

 # getfattr -RPh -dm '.*' / 2>/dev/null | sed -e '/^\#/d' |awk 'BEGIN{RS="";OFS=""}{$1=$1;print}' | wc -c
 6857670

It was using about 6857670 bytes (including both key and values), and
this corresponds to about 1675 4k-blocks.  After I removed duplicating
attribute sets, it was reduced to 27453 bytes (about 7 4k-blocks).

 # getfattr -RPh -dm '.*' / 2>/dev/null | sed -e '/^\#/d' |awk 'BEGIN{RS="";OFS=""}{$1=$1;print}' | sort | uniq | wc -c
 27453

If we can share xanodes effectively, the amount of disk space and
access performance of xattrs will be greatly-improved.

However, it seems that supporting multiple xanode sizes which are
smaller than block size and shared among multiple inodes, is
preferable to achieve that goal.


> For example, many inodes can have system.posix_acl_access ACL but
> content of binary streams will be different (namely,
> permitted/denied permissions set).

Usually, posix ACLs are inherited from a parent directory to its
children, so I guess there are much chance of sharing the same content
of binary streams.

> Moreover, of course, it is
> possible to use such scheme as sharing identical xattrs' content
> between several inodes. But if we need in independent xattr's
> content update for some inode then we will need to use something
> likewise COW policy. I suppose that it can be complicated technique.

I don't think COW policy is difficult.  That is what ext2/ext3/ext4
are doing.  You can use mbcache for that purpose and for finding the
xanode having the same content.


Regards,
Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC] nilfs2: xattrs support implementation idea

[Ryusuke Konishi]

On Thu, 26 Sep 2013 18:07:59 +0400, Vyacheslav Dubeyko wrote:
>> For the tree of xanodes, it seems a bit inefficent because it is
>> implemented over xafile (meta data file), and this introduces
>> threefold tree lookups to access the target disk block:
>> 
>>   xanode tree lookup --> xafile btree lookup --> DAT btree lookup
>> 
>> Simple block chaining over xafile may be better for most cases.
>> 
>> I think the tree-over-xafile implementation is a candidate, but please
>> try considering ideas to replace the the tree based lookup into an
>> index based access over xafile.
>> 
> 
> First of all, in my concept the xafile is aggregate of xanodes. Every
> xanode is accessed by index in xafile. So, namely index based access
> over xafile is used in my implementation.

I said this is "For the tree of xanodes".  You are misunderstanding.
I don't comment on shared xanodes here.

Yes, of course, I know block access over xafile i_xattr can be used
for that index access.  That is what we intended to prepare the
i_xattr field and the reserved extended attribute metadata file
(NILFS_XATTR_INO)

> The xafile as container of xanodes is important concept from the GC
> point of view. Data blocks and xattr blocks have different nature of
> aging. So, mixture of data and xattr blocks can be not GC
> friendly.

Yes, I know.  I don't deny using xafile.  The xafile approach also has
the merit of disk format compatibility.  These are exactly the reason
why original nilfs design is reserving xattr inode number.

> Access to xanodes by means of index over xafile is
> important concept too. Because namely index of xanode in xafile is
> stored as xanode number in header and other structures. So, xafile
> as metadata file hides problem of translation logical index (xanode
> number) into real block number.
> 
> About lookup... On-disk inode keeps xattrs by itself in the inline
> xanode case. So, we don't need to search an inline xanode in such case.
> An inode keeps xanode number (or index of xafile's node) in the case of
> shared xanode. It means that we have metadata file lookup overhead only
> (xafile btree lookup --> DAT btree lookup). An inode keeps xanode number
> of a first xanode of dedicated xanodes' tree. Only this inode possesses
> by such dedicated tree. So, dedicated tree will not big in ordinary
> case.

I am not worrying about lookup of inline xattr or shared xattr.  I
inteded to comment on the tree type xattr.

> The dedicated xanodes' tree can be big if an inode will have very
> big count of xattrs (or xattrs with big content size). Every xanode has
> small reserved space for index keys. But, initially, only first xanode
> is used for storing index keys. And reserved space for index keys is
> growing in the case of necessity to have more index keys. I suppose that
> one index level will be enough for most cases. So, usually, reading of
> first xanode will be enough for getting knowledge about all leaf xanodes
> in dedicated xanodes' tree.

Ok, you are pointing out that the depth of xattr trees is expected to
be small.  That is reasonable.

> Yes, (xafile btree lookup --> DAT btree lookup) can be the reason of
> overhead. But I think that we need to optimize this overhead for all
> use-cases, anyway.

Agreed.


>> For the inline xattr, I think it should not be mandatory.  It should
>> be an option for users who wants faster accesses to the extended
>> attributes and can accept reformat of the file system with 256-bit
>> size inodes for that purpose.
>> 
> 
> Yes, sure. Inline xattrs are optional. If a user hasn't opportunity (or
> desire) for reformat NILFS2 volume then it will not use inline xattrs
> completely.

Okay.

>> > /*
>> >  * struct nilfs_inline_xanode_header - header of inline node
>> >  * @magic: magic number for identification
>> >  * @type: node type
>> >  * @entries: number of entries in node
>> >  * @log_node_size: log2(node size in bytes)
>> 
>> log2(node size in bytes) - 10 ?
>> 
>> 4-bit width log_node_size only can represent 0~15 bytes.
>> 
> 
> I think that xafile's xanode size can be in range: 1KB (1024) - 32KB
> (32768). I suppose that maximum value in 32KB is enough for all cases.
> So, it needs 15 bytes for 32KB node size.

Ok, this is my misunderstanding.

4-bit width log_node_size can represent 2^0 ~ 2^15 bytes (32KB).


>> >  * @flags: node flags
>> >  */
>> > struct nilfs_inline_xanode_header {
>> >         __le16 magic;
>> 
>> Is this magic field necessary?   The reserved field
>> at the end of the current disk inode is valuable.
>> 
>> Setting the same magic number to all inodes seems wasteful.
>> 
> 
> The magic field is useful for consistency checking. And magic number
> keeps for the whole xanode. I don't think that 2-byte value wastes 4KB
> xanode, for example. Moreover, I use magic for detecting presence of
> inline xanode in extended space of on-disk inode. Of course, we can
> leave padding field at the end of on-disk inode untouched. But it needs
> to use another way of detecting inline xanode presence. What do you
> suggest?

I am not denying adding 2-bytes magic number to 4k-bytes blocks on
xafile.

What I am saying is the magic number inserted in nilfs_inode.

i_pad is guaranteed to be zero-filled by mkfs, so you don't have to
add 16-bit magic field; a few bits magic number field is enough for
the inlined xattr header.

You can do the consistency check with the few bit magic number and
whether i_xattr is zero or not. (for compatibility reason, we must
define i_xattr is zero if and only if xattr is not used.)

We agreed that inline xattr should be optional, so, I think moving
nilfs_inline_xanode_header into the extended inode area is a
reasonable option.

Anyway, I want to reserve at least a 16-bit field for inode checksum
functionality.


>> > /*
>> >  * struct nilfs_xattr_inline_key - xattr key for inline node
>> >  * @type: key type
>> >  * @flags: key's flags
>> >  * @reserved: reserved field
>> >  * @name_index: attribute name index
>> >  * @name_hash: name hash
>> >  * @entry_offset: entry offset inside the node
>> >  * @entry_size: size of entry in bytes
>> >  */
>> > struct nilfs_xattr_inline_key {
>> >         u8 type : 2;
>> >         u8 flags : 6;
>> >         u8 reserved;
>> >         __le16 name_index;
>> >         __le32 name_hash;
>> >         __le16 entry_offset;
>> >         __le16 entry_size;
>> > } __packed;
>> 
>> For what purpose is the type field used ?
> 
> The purpose of "type" field is to distinguish different type of xanode's
> headers or keys. Namely, for example, detecting that we have header of
> inline xanode, shared xanode or tree xanode.

That looks to be defined as the purpose of "flags" field.  See the
following definitions:

> /* Xattr key's flags */
> #define NILFS_INLINE_NODE_KEY           0
> #define NILFS_SHARED_XANODE_KEY         1
> #define NILFS_XANODE_INDEX_KEY          2
> #define NILFS_XANODE_LEAF_KEY           3


>> Again, the type field.  What is the difference between the type field
>> and the flags field ?
>> 
> 
> The type field is part of flags field. So, it can be extracted from
> flags field by means of mask.

OK, please reorganize the two fields when you will get rid of
bit-field uses.


>> > struct nilfs_xattr_index_key {
>> >         u8 type : 2;
>> >         u8 flags : 6;
>> >         u8 reserved1;
>> >         __le16 name_index;
>> >         __le32 name_hash;
>> >         __le64 parent;
>> >         __le64 leaf;
>> > } __packed;
>> 
>> Why is the "parent" field required ?
>> 
>> The size of this structure is 24 bytes.
>> It fits in 16 bytes structure if the parent field is eliminable.
>> Otherwise, you need 8 more pad bytes to align on-disk structures 
>> to 8 byte boundary.
> 
> I need to think over the real necessity of "parent" field. But my
> initial intention was to have backpointer on index xanode that describe
> this xanode as leaf.

I know it.  What I was asking about is the necessity of the "parent"
field.

> But now I doubt that keeps this value in an index
> key is a good idea. Maybe, it makes sense to keep this value in xanode's
> header in the case of real necessity in "parent" backpointer. So, I need
> to reflect about it.

Ok, please reconsider it as needed when you proceed implementation.


Regards,
Ryusuke Konishi

--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC] nilfs2: xattrs support implementation idea

[Vyacheslav Dubeyko]

Hi Ryusuke,

On Sun, 2013-09-29 at 00:01 +0900, Ryusuke Konishi wrote:

[snip]
> I measured how much xattrs are duplicating by using getfattr command
> on my fedora 19 system.
> 
> 
>  # getfattr -RPh -e hex -dm '.*' / 2>/dev/null | sed -e '/^\#/d' | awk 'BEGIN{RS="";OFS=""}{$1=$1;print}' | wc -l
>  143103
> 
> The system has 143103 extended attibutes sets, where sed command is
> removing comment line, awk command is joining multiple extended
> attributes per file or directory, and wc command is used to count
> them.
> 
> Then, the number of extended attribute sets was reduced to 441 after I
> removed duplicated ones with sort and uniq commands:
> 
>  # getfattr -RPh -e hex -dm '.*' / 2>/dev/null | sed -e '/^\#/d' |awk 'BEGIN{RS="";OFS=""}{$1=$1;print}' | sort | uniq | wc -l
>  441
> 
> Although POSIX ACLs are not handled in this measurement (we can use
> getfacl command for similiar purpose), sharing the same extended
> attribute content looks to be effective to reduce the on-disk data
> size.
> 
> 
> I also measured the total size of extended attibutes on the system:
> 
>  # getfattr -RPh -dm '.*' / 2>/dev/null | sed -e '/^\#/d' |awk 'BEGIN{RS="";OFS=""}{$1=$1;print}' | wc -c
>  6857670
> 
> It was using about 6857670 bytes (including both key and values), and
> this corresponds to about 1675 4k-blocks.  After I removed duplicating
> attribute sets, it was reduced to 27453 bytes (about 7 4k-blocks).
> 
>  # getfattr -RPh -dm '.*' / 2>/dev/null | sed -e '/^\#/d' |awk 'BEGIN{RS="";OFS=""}{$1=$1;print}' | sort | uniq | wc -c
>  27453
> 
> If we can share xanodes effectively, the amount of disk space and
> access performance of xattrs will be greatly-improved.
> 

Ok. I see now.

So, I have achieved some vision after contemplation about what you said.
Yes, I accept your arguments but, anyway, it needs to be accurate. We
should balance between efficient decreasing the used disk space and
efficient access performance.

First of all, I suppose that sharing xattr between multiple inodes makes
sense only for the case when inode has one xattr. In such case we can as
to decrease used disk space as to access to xattr content efficiently.
Otherwise, if inode has several xattrs then efficiency of accesses to
xattrs will degrade significantly, especially for the case of listxattr
operations. I mean that we will keep shared xattrs ordered on the basis
of hashes and, as a result, trying to access to several shared xattrs of
inode will be ended with potential necessity to read (and modify)
several blocks (potentially, count of blocks may be equal to count of
xattrs). Moreover, for example, on my system I have many inodes that
have one duplicated xattr - "security.selinux".

But if a user has inline xanodes then such xattr will be replicated in
inline xanodes. So, does it make sense to share xattr anyway for the
case of inline xanode presence? What do you think? I suppose that inline
xanode will be more efficient storage but without achieving efficiency
in decreasing used space.

I think that concept of independent shared xanodes should be evolved in
concept of shared xanodes' tree. I assume that I have vision of
efficient structure of shared xanodes' tree. But I need to think through
it more deeply before sharing my vision.

Secondly, I think that it needs to take into account and xattrs' name
duplication. Because even if xattrs have different contents then it can
have identical name very frequently. So, it is possible to have one
names tree for the whole xafile. As a result, we will store fixed size
name hash in the key of xattr instead of name with variable size.
Usually, it is used small number of predetermined xattr names under
Linux and xattr's names tree can be small. Anyway, I suppose that I have
vision of efficient structure of xattr's name tree. The getxattr
operation doesn't need to access xattr's names tree because we can
compute hash for requested name. The setxattr operation is provided by
xattr name also but it will need to check necessity to increase (or
decrease) name reference count. Only listxattr operation needs in
extracting names from xattr's names tree on the basis of known hashes.
However, theoretically, it is possible to be without name's reference
counter if xattr's names tree will not support operation of name
removing from the tree.

So, I have such vision of xafile's concepts, currently:
(1) Single xattr's names tree. The names tree stores and share xattrs'
name between inodes.
(2) Inline xanodes (OPTIONAL). It keeps xattrs in extended part of
inode.
(3) Single tree of shared xanodes. It stores xattrs that are shared
between inodes. Shared xattr is accessible in RO mode only. A xattr can
be shared if an inode has one xattr only. If some inode needs in
independent modification of shared xattr then: (A) modified xattr will
be stored in inode's inline xanode or dedicated tree of xanodes; (B)
reference count of shared xattr will be decremented.
(4) Inode's dedicated tree of xanodes. It keeps inode's xattrs in the
xanodes' tree. 

> However, it seems that supporting multiple xanode sizes which are
> smaller than block size and shared among multiple inodes, is
> preferable to achieve that goal.
> 

Yes, I think that it makes sense. I'll take it into account.

By the way, I will be unavailable be e-mail during one week (maybe two
weeks) because of business trip.

With the best regards,
Vyacheslav Dubeyko.


--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html