Skip to contentSkip to conversation

nilfs2: implement calculation of free inodes count

PATCH Superseded Vyacheslav Dubeyko 4 participants 8 messages May 15, 2013 – May 18, 2013 3 messages not in the archive

Subsystems (2)

v3 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Vyacheslav Dubeyko

author maintainer
#0 lore raw

PATCH v3 1/1 nilfs2: implement calculation of free inodes count

Hi Ryusuke,

This is third version of the patch.

v2->v3
* Trivial BUG_ON checks were removed.
* Whole calculation algorithm was moved into nilfs_palloc_count_max_entries() method.
* Improve error processing in the code.
* The nilfs_palloc_mdt_file_can_grow() method was simplified.
* The nilfs_ifile_count_free_inodes() method was simplified.

v1->v2
* Change __statfs_word on u64 type.
* Rename nilfs_count_free_inodes() into nilfs_ifile_count_free_inodes() method.
* Introduce auxiliary functions: nilfs_palloc_count_max_entries(), nilfs_palloc_count_desc_blocks(), nilfs_palloc_mdt_file_can_grow().
* Rework processing of returned error from nilfs_ifile_count_free_inodes() in nilfs_statfs().

With the best regards,
Vyacheslav Dubeyko.
---
From: Vyacheslav Dubeyko <[email protected]>
Subject: [PATCH v3] nilfs2: implement calculation of free inodes count

Currently, NILFS2 returns 0 as free inodes count (f_ffree) and current used inodes count as total file nodes in file system (f_files):

df -i
Filesystem Inodes IUsed IFree IUse% Mounted on
/dev/loop0 2 2 0 100% /mnt/nilfs2

This patch implements real calculation of free inodes count. First of all, it is calculated total file nodes in file system as (desc_blocks_count * groups_per_desc_block * entries_per_group). Then, it is calculated free inodes count as difference the total file nodes and used inodes count. As a result, we have such output for NILFS2:

df -i
Filesystem Inodes IUsed IFree IUse% Mounted on
/dev/loop0 4194304 2114701 2079603 51% /mnt/nilfs2

---
 fs/nilfs2/alloc.c |   96 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/nilfs2/alloc.h |    2 ++
 fs/nilfs2/ifile.c |   22 ++++++++++++
 fs/nilfs2/ifile.h |    2 +-
 fs/nilfs2/mdt.h   |    2 ++
 fs/nilfs2/super.c |   24 ++++++++++++--
 6 files changed, 145 insertions(+), 3 deletions(-)
fs/nilfs2/alloc.c +96 -0
index eed4d7b..2727713 100644
@@ -80,6 +80,13 @@ int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned entry_size)
 		mi->mi_blocks_per_group + 1;
 		/* Number of blocks per descriptor including the
 		   descriptor block */
+	atomic_set(&mi->mi_desc_blocks_count, 1);
+		/*
+		 * The field mi_desc_blocks_count is used for
+		 * storing knowledge about current count of
+		 * desciptor blocks. Initially, it is initialized
+		 * by one.
+		 */
 	return 0;
 }
 
@@ -398,6 +405,95 @@ nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
 }
 
 /**
+ * nilfs_palloc_count_desc_blocks - count descriptor blocks number
+ * @inode: inode of metadata file using this allocator
+ * @start_desc_blks: known current descriptor blocks count
+ * @desc_blocksp: calculated descriptor blocks number [out]
+ */
+static int nilfs_palloc_count_desc_blocks(struct inode *inode,
+					    unsigned int start_desc_blks,
+					    unsigned int *desc_blocksp)
+{
+	unsigned long ngroups = nilfs_palloc_groups_count(inode);
+	unsigned long groups_per_desc_block =
+			nilfs_palloc_groups_per_desc_block(inode);
+	struct buffer_head *desc_bh;
+	unsigned long group =
+		groups_per_desc_block * (unsigned long)start_desc_blks;
+	unsigned int desc_blocks;
+	int err;
+
+	*desc_blocksp = desc_blocks = start_desc_blks;
+	for (; group < ngroups; group += groups_per_desc_block) {
+		err = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
+		if (err) {
+			if (err == -ENOENT)
+				break;
+			return err;
+		}
+		desc_blocks++;
+		brelse(desc_bh);
+	}
+
+	*desc_blocksp = desc_blocks;
+	return 0;
+}
+
+/**
+ * nilfs_palloc_mdt_file_can_grow - check potential opportunity for
+ *					MDT file growing
+ * @inode: inode of metadata file using this allocator
+ * @desc_blocks: known current descriptor blocks count
+ */
+static inline bool nilfs_palloc_mdt_file_can_grow(struct inode *inode,
+						    unsigned int desc_blocks)
+{
+	return (nilfs_palloc_groups_per_desc_block(inode) * (u64)desc_blocks) <
+			nilfs_palloc_groups_count(inode);
+}
+
+/**
+ * nilfs_palloc_count_max_entries - count max number of entries that can be
+ *					described by descriptor blocks count
+ * @inode: inode of metadata file using this allocator
+ * @nused: current number of used entries
+ * @nmaxp: max number of entries [out]
+ */
+int nilfs_palloc_count_max_entries(struct inode *inode, u64 nused, u64 *nmaxp)
+{
+	unsigned int desc_blocks;
+	u64 entries_per_desc_block, nmax;
+	int err;
+
+	desc_blocks = atomic_read(&NILFS_MDT(inode)->mi_desc_blocks_count);
+	entries_per_desc_block = (u64)nilfs_palloc_entries_per_group(inode) *
+				nilfs_palloc_groups_per_desc_block(inode);
+
+	nmax = entries_per_desc_block * (u64)desc_blocks;
+	if (nused >= nmax) {
+		err = nilfs_palloc_count_desc_blocks(inode, desc_blocks,
+							&desc_blocks);
+		if (unlikely(err))
+			return err;
+
+		nmax = entries_per_desc_block * (u64)desc_blocks;
+		if (nused == nmax &&
+				nilfs_palloc_mdt_file_can_grow(inode,
+								desc_blocks)) {
+			nmax += entries_per_desc_block;
+			++desc_blocks;
+		}
+		atomic_set(&NILFS_MDT(inode)->mi_desc_blocks_count,
+				desc_blocks);
+
+		if (nused > nmax)
+			return -ERANGE;
+	}
+	*nmaxp = nmax;
+	return 0;
+}
+
+/**
  * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object
  * @inode: inode of metadata file using this allocator
  * @req: nilfs_palloc_req structure exchanged for the allocation
fs/nilfs2/alloc.h +2 -0
index fb72381..4bd6451 100644
@@ -48,6 +48,8 @@ int nilfs_palloc_get_entry_block(struct inode *, __u64, int,
 void *nilfs_palloc_block_get_entry(const struct inode *, __u64,
 				   const struct buffer_head *, void *);
 
+int nilfs_palloc_count_max_entries(struct inode *, u64, u64 *);
+
 /**
  * nilfs_palloc_req - persistent allocator request and reply
  * @pr_entry_nr: entry number (vblocknr or inode number)
fs/nilfs2/ifile.c +22 -0
index d8e65bd..d788a59 100644
@@ -160,6 +160,28 @@ int nilfs_ifile_get_inode_block(struct inode *ifile, ino_t ino,
 }
 
 /**
+ * nilfs_ifile_count_free_inodes - calculate free inodes count
+ * @ifile: ifile inode
+ * @nmaxinodes: current maximum of available inodes count [out]
+ * @nfreeinodes: free inodes count [out]
+ */
+int nilfs_ifile_count_free_inodes(struct inode *ifile,
+				    u64 *nmaxinodes, u64 *nfreeinodes)
+{
+	u64 nused;
+	int err;
+
+	*nmaxinodes = 0;
+	*nfreeinodes = 0;
+
+	nused = atomic_read(&NILFS_I(ifile)->i_root->inodes_count);
+	err = nilfs_palloc_count_max_entries(ifile, nused, nmaxinodes);
+	if (likely(!err))
+		*nfreeinodes = *nmaxinodes - nused;
+	return err;
+}
+
+/**
  * nilfs_ifile_read - read or get ifile inode
  * @sb: super block instance
  * @root: root object
fs/nilfs2/ifile.h +1 -1
index 59b6f2b..e9ceb27 100644
@@ -48,7 +48,7 @@ static inline void nilfs_ifile_unmap_inode(struct inode *ifile, ino_t ino,
 int nilfs_ifile_create_inode(struct inode *, ino_t *, struct buffer_head **);
 int nilfs_ifile_delete_inode(struct inode *, ino_t);
 int nilfs_ifile_get_inode_block(struct inode *, ino_t, struct buffer_head **);
-
+int nilfs_ifile_count_free_inodes(struct inode *, u64 *, u64 *);
 int nilfs_ifile_read(struct super_block *sb, struct nilfs_root *root,
 		     size_t inode_size, struct nilfs_inode *raw_inode,
 		     struct inode **inodep);
fs/nilfs2/mdt.h +2 -0
index ab172e8..c01b6fb 100644
@@ -53,6 +53,7 @@ struct nilfs_shadow_map {
  * @mi_shadow: shadow of bmap and page caches
  * @mi_blocks_per_group: number of blocks in a group
  * @mi_blocks_per_desc_block: number of blocks per descriptor block
+ * @mi_desc_blocks_count: number of descriptor blocks
  */
 struct nilfs_mdt_info {
 	struct rw_semaphore	mi_sem;
@@ -64,6 +65,7 @@ struct nilfs_mdt_info {
 	struct nilfs_shadow_map *mi_shadow;
 	unsigned long		mi_blocks_per_group;
 	unsigned long		mi_blocks_per_desc_block;
+	atomic_t		mi_desc_blocks_count;
 };
 
 static inline struct nilfs_mdt_info *NILFS_MDT(const struct inode *inode)
fs/nilfs2/super.c +22 -2
index c7d1f9f..2b908a6 100644
@@ -609,6 +609,7 @@ static int nilfs_statfs(struct dentry *dentry, struct kstatfs *buf)
 	unsigned long overhead;
 	unsigned long nrsvblocks;
 	sector_t nfreeblocks;
+	u64 nmaxinodes, nfreeinodes;
 	int err;
 
 	/*
@@ -633,14 +634,33 @@ static int nilfs_statfs(struct dentry *dentry, struct kstatfs *buf)
 	if (unlikely(err))
 		return err;
 
+	err = nilfs_ifile_count_free_inodes(root->ifile,
+						&nmaxinodes, &nfreeinodes);
+	if (unlikely(err)) {
+		printk(KERN_WARNING
+			"NILFS warning: fail to count free inodes: err %d.\n",
+			err);
+		if (err == -ERANGE) {
+			/*
+			 * If nilfs_palloc_count_max_entries() returns
+			 * -ERANGE error code then we simply treat
+			 * curent inodes count as maximum possible and
+			 * zero as free inodes value.
+			 */
+			nmaxinodes = atomic_read(&root->inodes_count);
+			nfreeinodes = 0;
+		} else
+			return err;
+	}
+
 	buf->f_type = NILFS_SUPER_MAGIC;
 	buf->f_bsize = sb->s_blocksize;
 	buf->f_blocks = blocks - overhead;
 	buf->f_bfree = nfreeblocks;
 	buf->f_bavail = (buf->f_bfree >= nrsvblocks) ?
 		(buf->f_bfree - nrsvblocks) : 0;
-	buf->f_files = atomic_read(&root->inodes_count);
-	buf->f_ffree = 0; /* nilfs_count_free_inodes(sb); */
+	buf->f_files = nmaxinodes;
+	buf->f_ffree = nfreeinodes;
 	buf->f_namelen = NILFS_NAME_LEN;
 	buf->f_fsid.val[0] = (u32)id;
 	buf->f_fsid.val[1] = (u32)(id >> 32);
Signature · 1 line
1.7.9.5
#1 lore raw
Quoted 42 lines · Vyacheslav Dubeyko

Hi Ryusuke,

This is third version of the patch.

v2->v3
* Trivial BUG_ON checks were removed.
* Whole calculation algorithm was moved into nilfs_palloc_count_max_entries() method.
* Improve error processing in the code.
* The nilfs_palloc_mdt_file_can_grow() method was simplified.
* The nilfs_ifile_count_free_inodes() method was simplified.

v1->v2
* Change __statfs_word on u64 type.
* Rename nilfs_count_free_inodes() into nilfs_ifile_count_free_inodes() method.
* Introduce auxiliary functions: nilfs_palloc_count_max_entries(), nilfs_palloc_count_desc_blocks(), nilfs_palloc_mdt_file_can_grow().
* Rework processing of returned error from nilfs_ifile_count_free_inodes() in nilfs_statfs().

With the best regards,
Vyacheslav Dubeyko.
---
From: Vyacheslav Dubeyko <[email protected]>
Subject: [PATCH v3] nilfs2: implement calculation of free inodes count

Currently, NILFS2 returns 0 as free inodes count (f_ffree) and current used inodes count as total file nodes in file system (f_files):

df -i
Filesystem Inodes IUsed IFree IUse% Mounted on
/dev/loop0 2 2 0 100% /mnt/nilfs2

This patch implements real calculation of free inodes count. First of all, it is calculated total file nodes in file system as (desc_blocks_count * groups_per_desc_block * entries_per_group). Then, it is calculated free inodes count as difference the total file nodes and used inodes count. As a result, we have such output for NILFS2:

Quoted 8 lines

df -i
Filesystem Inodes IUsed IFree IUse% Mounted on
/dev/loop0 4194304 2114701 2079603 51% /mnt/nilfs2

This patch still has a potential overflow issue that I pointed out in the previous comment; the patch handles the number of descriptor blocks in 32-bit wide variables without checking its upper limit.

If you won't to add checks for the number of descriptor blocks, I propose you to change the definition of nilfs_palloc_groups_count() instead:

static inline unsigned long nilfs_palloc_groups_count(const struct inode *inode) {
- return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
+ return nilfs_palloc_groups_per_desc_block(inode) << 32;
}

This implies the maximum number of descriptor block is 1 ^ 32.

Because the above diff changes the maximum number of groups, I think it should be inserted as a separate patch.

Thanks,
Ryusuke Konishi

Quoted 259 lines
---
 fs/nilfs2/alloc.c |   96 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/nilfs2/alloc.h |    2 ++
 fs/nilfs2/ifile.c |   22 ++++++++++++
 fs/nilfs2/ifile.h |    2 +-
 fs/nilfs2/mdt.h   |    2 ++
 fs/nilfs2/super.c |   24 ++++++++++++--
 6 files changed, 145 insertions(+), 3 deletions(-)
fs/nilfs2/alloc.c +96 -0
index eed4d7b..2727713 100644
@@ -80,6 +80,13 @@ int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned entry_size)
 		mi->mi_blocks_per_group + 1;
 		/* Number of blocks per descriptor including the
 		   descriptor block */
+	atomic_set(&mi->mi_desc_blocks_count, 1);
+		/*
+		 * The field mi_desc_blocks_count is used for
+		 * storing knowledge about current count of
+		 * desciptor blocks. Initially, it is initialized
+		 * by one.
+		 */
 	return 0;
 }
 
@@ -398,6 +405,95 @@ nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
 }
 
 /**
+ * nilfs_palloc_count_desc_blocks - count descriptor blocks number
+ * @inode: inode of metadata file using this allocator
+ * @start_desc_blks: known current descriptor blocks count
+ * @desc_blocksp: calculated descriptor blocks number [out]
+ */
+static int nilfs_palloc_count_desc_blocks(struct inode *inode,
+					    unsigned int start_desc_blks,
+					    unsigned int *desc_blocksp)
+{
+	unsigned long ngroups = nilfs_palloc_groups_count(inode);
+	unsigned long groups_per_desc_block =
+			nilfs_palloc_groups_per_desc_block(inode);
+	struct buffer_head *desc_bh;
+	unsigned long group =
+		groups_per_desc_block * (unsigned long)start_desc_blks;
+	unsigned int desc_blocks;
+	int err;
+
+	*desc_blocksp = desc_blocks = start_desc_blks;
+	for (; group < ngroups; group += groups_per_desc_block) {
+		err = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
+		if (err) {
+			if (err == -ENOENT)
+				break;
+			return err;
+		}
+		desc_blocks++;
+		brelse(desc_bh);
+	}
+
+	*desc_blocksp = desc_blocks;
+	return 0;
+}
+
+/**
+ * nilfs_palloc_mdt_file_can_grow - check potential opportunity for
+ *					MDT file growing
+ * @inode: inode of metadata file using this allocator
+ * @desc_blocks: known current descriptor blocks count
+ */
+static inline bool nilfs_palloc_mdt_file_can_grow(struct inode *inode,
+						    unsigned int desc_blocks)
+{
+	return (nilfs_palloc_groups_per_desc_block(inode) * (u64)desc_blocks) <
+			nilfs_palloc_groups_count(inode);
+}
+
+/**
+ * nilfs_palloc_count_max_entries - count max number of entries that can be
+ *					described by descriptor blocks count
+ * @inode: inode of metadata file using this allocator
+ * @nused: current number of used entries
+ * @nmaxp: max number of entries [out]
+ */
+int nilfs_palloc_count_max_entries(struct inode *inode, u64 nused, u64 *nmaxp)
+{
+	unsigned int desc_blocks;
+	u64 entries_per_desc_block, nmax;
+	int err;
+
+	desc_blocks = atomic_read(&NILFS_MDT(inode)->mi_desc_blocks_count);
+	entries_per_desc_block = (u64)nilfs_palloc_entries_per_group(inode) *
+				nilfs_palloc_groups_per_desc_block(inode);
+
+	nmax = entries_per_desc_block * (u64)desc_blocks;
+	if (nused >= nmax) {
+		err = nilfs_palloc_count_desc_blocks(inode, desc_blocks,
+							&desc_blocks);
+		if (unlikely(err))
+			return err;
+
+		nmax = entries_per_desc_block * (u64)desc_blocks;
+		if (nused == nmax &&
+				nilfs_palloc_mdt_file_can_grow(inode,
+								desc_blocks)) {
+			nmax += entries_per_desc_block;
+			++desc_blocks;
+		}
+		atomic_set(&NILFS_MDT(inode)->mi_desc_blocks_count,
+				desc_blocks);
+
+		if (nused > nmax)
+			return -ERANGE;
+	}
+	*nmaxp = nmax;
+	return 0;
+}
+
+/**
  * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object
  * @inode: inode of metadata file using this allocator
  * @req: nilfs_palloc_req structure exchanged for the allocation
fs/nilfs2/alloc.h +2 -0
index fb72381..4bd6451 100644
@@ -48,6 +48,8 @@ int nilfs_palloc_get_entry_block(struct inode *, __u64, int,
 void *nilfs_palloc_block_get_entry(const struct inode *, __u64,
 				   const struct buffer_head *, void *);
 
+int nilfs_palloc_count_max_entries(struct inode *, u64, u64 *);
+
 /**
  * nilfs_palloc_req - persistent allocator request and reply
  * @pr_entry_nr: entry number (vblocknr or inode number)
fs/nilfs2/ifile.c +22 -0
index d8e65bd..d788a59 100644
@@ -160,6 +160,28 @@ int nilfs_ifile_get_inode_block(struct inode *ifile, ino_t ino,
 }
 
 /**
+ * nilfs_ifile_count_free_inodes - calculate free inodes count
+ * @ifile: ifile inode
+ * @nmaxinodes: current maximum of available inodes count [out]
+ * @nfreeinodes: free inodes count [out]
+ */
+int nilfs_ifile_count_free_inodes(struct inode *ifile,
+				    u64 *nmaxinodes, u64 *nfreeinodes)
+{
+	u64 nused;
+	int err;
+
+	*nmaxinodes = 0;
+	*nfreeinodes = 0;
+
+	nused = atomic_read(&NILFS_I(ifile)->i_root->inodes_count);
+	err = nilfs_palloc_count_max_entries(ifile, nused, nmaxinodes);
+	if (likely(!err))
+		*nfreeinodes = *nmaxinodes - nused;
+	return err;
+}
+
+/**
  * nilfs_ifile_read - read or get ifile inode
  * @sb: super block instance
  * @root: root object
fs/nilfs2/ifile.h +1 -1
index 59b6f2b..e9ceb27 100644
@@ -48,7 +48,7 @@ static inline void nilfs_ifile_unmap_inode(struct inode *ifile, ino_t ino,
 int nilfs_ifile_create_inode(struct inode *, ino_t *, struct buffer_head **);
 int nilfs_ifile_delete_inode(struct inode *, ino_t);
 int nilfs_ifile_get_inode_block(struct inode *, ino_t, struct buffer_head **);
-
+int nilfs_ifile_count_free_inodes(struct inode *, u64 *, u64 *);
 int nilfs_ifile_read(struct super_block *sb, struct nilfs_root *root,
 		     size_t inode_size, struct nilfs_inode *raw_inode,
 		     struct inode **inodep);
fs/nilfs2/mdt.h +2 -0
index ab172e8..c01b6fb 100644
@@ -53,6 +53,7 @@ struct nilfs_shadow_map {
  * @mi_shadow: shadow of bmap and page caches
  * @mi_blocks_per_group: number of blocks in a group
  * @mi_blocks_per_desc_block: number of blocks per descriptor block
+ * @mi_desc_blocks_count: number of descriptor blocks
  */
 struct nilfs_mdt_info {
 	struct rw_semaphore	mi_sem;
@@ -64,6 +65,7 @@ struct nilfs_mdt_info {
 	struct nilfs_shadow_map *mi_shadow;
 	unsigned long		mi_blocks_per_group;
 	unsigned long		mi_blocks_per_desc_block;
+	atomic_t		mi_desc_blocks_count;
 };
 
 static inline struct nilfs_mdt_info *NILFS_MDT(const struct inode *inode)
fs/nilfs2/super.c +22 -2
index c7d1f9f..2b908a6 100644
@@ -609,6 +609,7 @@ static int nilfs_statfs(struct dentry *dentry, struct kstatfs *buf)
 	unsigned long overhead;
 	unsigned long nrsvblocks;
 	sector_t nfreeblocks;
+	u64 nmaxinodes, nfreeinodes;
 	int err;
 
 	/*
@@ -633,14 +634,33 @@ static int nilfs_statfs(struct dentry *dentry, struct kstatfs *buf)
 	if (unlikely(err))
 		return err;
 
+	err = nilfs_ifile_count_free_inodes(root->ifile,
+						&nmaxinodes, &nfreeinodes);
+	if (unlikely(err)) {
+		printk(KERN_WARNING
+			"NILFS warning: fail to count free inodes: err %d.\n",
+			err);
+		if (err == -ERANGE) {
+			/*
+			 * If nilfs_palloc_count_max_entries() returns
+			 * -ERANGE error code then we simply treat
+			 * curent inodes count as maximum possible and
+			 * zero as free inodes value.
+			 */
+			nmaxinodes = atomic_read(&root->inodes_count);
+			nfreeinodes = 0;
+		} else
+			return err;
+	}
+
 	buf->f_type = NILFS_SUPER_MAGIC;
 	buf->f_bsize = sb->s_blocksize;
 	buf->f_blocks = blocks - overhead;
 	buf->f_bfree = nfreeblocks;
 	buf->f_bavail = (buf->f_bfree >= nrsvblocks) ?
 		(buf->f_bfree - nrsvblocks) : 0;
-	buf->f_files = atomic_read(&root->inodes_count);
-	buf->f_ffree = 0; /* nilfs_count_free_inodes(sb); */
+	buf->f_files = nmaxinodes;
+	buf->f_ffree = nfreeinodes;
 	buf->f_namelen = NILFS_NAME_LEN;
 	buf->f_fsid.val[0] = (u32)id;
 	buf->f_fsid.val[1] = (u32)(id >> 32);
Signature · 8 lines
1.7.9.5



--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

A message that is not in the archive (sent off-list or not yet received): 20130516.024602.67896918.konishi.ryusuke-Zyj7fXuS5i5L9jVzuh4AOg@public.gmane.org

#3 lore raw
Quoted 66 lines · Ryusuke Konishi
Quoted 42 lines · Vyacheslav Dubeyko

Hi Ryusuke,

This is third version of the patch.

v2->v3
* Trivial BUG_ON checks were removed.
* Whole calculation algorithm was moved into nilfs_palloc_count_max_entries() method.
* Improve error processing in the code.
* The nilfs_palloc_mdt_file_can_grow() method was simplified.
* The nilfs_ifile_count_free_inodes() method was simplified.

v1->v2
* Change __statfs_word on u64 type.
* Rename nilfs_count_free_inodes() into nilfs_ifile_count_free_inodes() method.
* Introduce auxiliary functions: nilfs_palloc_count_max_entries(), nilfs_palloc_count_desc_blocks(), nilfs_palloc_mdt_file_can_grow().
* Rework processing of returned error from nilfs_ifile_count_free_inodes() in nilfs_statfs().

With the best regards,
Vyacheslav Dubeyko.
---
From: Vyacheslav Dubeyko <[email protected]>
Subject: [PATCH v3] nilfs2: implement calculation of free inodes count

Currently, NILFS2 returns 0 as free inodes count (f_ffree) and current used inodes count as total file nodes in file system (f_files):

df -i
Filesystem Inodes IUsed IFree IUse% Mounted on
/dev/loop0 2 2 0 100% /mnt/nilfs2

This patch implements real calculation of free inodes count. First of all, it is calculated total file nodes in file system as (desc_blocks_count * groups_per_desc_block * entries_per_group). Then, it is calculated free inodes count as difference the total file nodes and used inodes count. As a result, we have such output for NILFS2:

Quoted 8 lines

df -i
Filesystem Inodes IUsed IFree IUse% Mounted on
/dev/loop0 4194304 2114701 2079603 51% /mnt/nilfs2

This patch still has a potential overflow issue that I pointed out in the previous comment; the patch handles the number of descriptor blocks in 32-bit wide variables without checking its upper limit.

If you won't to add checks for the number of descriptor blocks, I propose you to change the definition of nilfs_palloc_groups_count() instead:

  static inline unsigned long
  nilfs_palloc_groups_count(const struct inode *inode)
  {
(quoted diff) +1 -1
- 	return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
+ 	return nilfs_palloc_groups_per_desc_block(inode) << 32;
  }
Quoted 4 lines

This implies the maximum number of descriptor block is 1 ^ 32.

Because the above diff changes the maximum number of groups, I think it should be inserted as a separate patch.

Oops, sorry, this change can overflow in 32-bit architectures because the type of return value is still unsigned long. That calculation should be revised more carefully.

Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

A message that is not in the archive (sent off-list or not yet received): 20130516.075913.157469255.konishi.ryusuke-Zyj7fXuS5i5L9jVzuh4AOg@public.gmane.org

#5 lore raw

Hi Ryusuke,

On Thu, 2013-05-16 at 07:59 +0900, Ryusuke Konishi wrote:

[snip]

Quoted 8 lines
Quoted 8 lines

This patch still has a potential overflow issue that I pointed out in the previous comment; the patch handles the number of descriptor blocks in 32-bit wide variables without checking its upper limit.

If you won't to add checks for the number of descriptor blocks, I propose you to change the definition of nilfs_palloc_groups_count() instead:

Quoted 7 lines

Review

Quoted 7 lines
  static inline unsigned long
  nilfs_palloc_groups_count(const struct inode *inode)
  {
(quoted diff) +1 -1
- 	return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
+ 	return nilfs_palloc_groups_per_desc_block(inode) << 32;
  }

I think the real reason of problem is in using constants (BITS_PER_LONG for the first case and 32 for the second one). But, anyway, it makes sense to operate by volume size in this calculation. Because namely volume size is the real limitation for calculation of maximum available groups count.

What do you think about using volume size in this calculation?

With the best regards,
Vyacheslav Dubeyko.

Quoted 9 lines
Quoted 4 lines

This implies the maximum number of descriptor block is 1 ^ 32.

Because the above diff changes the maximum number of groups, I think it should be inserted as a separate patch.

Oops, sorry, this change can overflow in 32-bit architectures because the type of return value is still unsigned long. That calculation should be revised more carefully.

Quoted 5 lines

Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in the body of a message to [email protected] 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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

#6 lore raw
Quoted 27 lines · Vyacheslav Dubeyko

Hi Ryusuke,

On Thu, 2013-05-16 at 07:59 +0900, Ryusuke Konishi wrote:

[snip]

Quoted 8 lines
Quoted 8 lines

This patch still has a potential overflow issue that I pointed out in the previous comment; the patch handles the number of descriptor blocks in 32-bit wide variables without checking its upper limit.

If you won't to add checks for the number of descriptor blocks, I propose you to change the definition of nilfs_palloc_groups_count() instead:

Quoted 7 lines

Review

Quoted 7 lines
  static inline unsigned long
  nilfs_palloc_groups_count(const struct inode *inode)
  {
(quoted diff) +1 -1
- 	return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
+ 	return nilfs_palloc_groups_per_desc_block(inode) << 32;
  }

I think the real reason of problem is in using constants (BITS_PER_LONG for the first case and 32 for the second one). But, anyway, it makes sense to operate by volume size in this calculation. Because namely volume size is the real limitation for calculation of maximum available groups count.

Quoted 4 lines

What do you think about using volume size in this calculation?

With the best regards,
Vyacheslav Dubeyko.

I disagree with using volume size because it makes resize logic much harder especially for shrink logic. It requires reconstructing of ifile and DAT meatadata file.

I just want to fix the calculation of the maximum number of groups so that the number of descriptor blocks doesn't overflow both for 64-bit and 32-bit architectures.

Regards,
Ryusuke Konishi

Quoted 20 lines
Quoted 9 lines
Quoted 4 lines

This implies the maximum number of descriptor block is 1 ^ 32.

Because the above diff changes the maximum number of groups, I think it should be inserted as a separate patch.

Oops, sorry, this change can overflow in 32-bit architectures because the type of return value is still unsigned long. That calculation should be revised more carefully.

Quoted 5 lines

Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in the body of a message to [email protected]
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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

A message that is not in the archive (sent off-list or not yet received): 20130517.014452.397311903.konishi.ryusuke-Zyj7fXuS5i5L9jVzuh4AOg@public.gmane.org

#8 lore raw

Hi Ryusuke,

Quoted 33 lines · Ryusuke Konishi
Quoted 27 lines · Vyacheslav Dubeyko

Hi Ryusuke,

On Thu, 2013-05-16 at 07:59 +0900, Ryusuke Konishi wrote:

[snip]

Quoted 8 lines
Quoted 8 lines

This patch still has a potential overflow issue that I pointed out in the previous comment; the patch handles the number of descriptor blocks in 32-bit wide variables without checking its upper limit.

If you won't to add checks for the number of descriptor blocks, I propose you to change the definition of nilfs_palloc_groups_count() instead:

Quoted 7 lines

Review

Quoted 7 lines
  static inline unsigned long
  nilfs_palloc_groups_count(const struct inode *inode)
  {
(quoted diff) +1 -1
- 	return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
+ 	return nilfs_palloc_groups_per_desc_block(inode) << 32;
  }

I think the real reason of problem is in using constants (BITS_PER_LONG for the first case and 32 for the second one). But, anyway, it makes sense to operate by volume size in this calculation. Because namely volume size is the real limitation for calculation of maximum available groups count.

Quoted 4 lines

What do you think about using volume size in this calculation?

With the best regards,
Vyacheslav Dubeyko.

Quoted 8 lines

I disagree with using volume size because it makes resize logic much harder especially for shrink logic. It requires reconstructing of ifile and DAT meatadata file.

I just want to fix the calculation of the maximum number of groups so that the number of descriptor blocks doesn't overflow both for 64-bit and 32-bit architectures.

Ok. I see.

What about such implementation?

static inline unsigned long nilfs_palloc_groups_count(const struct inode *inode) {

#define NILFS_DESC_BLOCKS_MAX UINT_MAX
	return nilfs_palloc_groups_per_desc_block(inode) *
			(unsigned long)NILFS_DESC_BLOCKS_MAX;

#undef NILFS_DESC_BLOCKS_MAX
}

With the best regards,
Vyacheslav Dubeyko.

Quoted 24 lines

Regards,
Ryusuke Konishi

Quoted 20 lines
Quoted 9 lines
Quoted 4 lines

This implies the maximum number of descriptor block is 1 ^ 32.

Because the above diff changes the maximum number of groups, I think it should be inserted as a separate patch.

Oops, sorry, this change can overflow in 32-bit architectures because the type of return value is still unsigned long. That calculation should be revised more carefully.

Quoted 5 lines

Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in the body of a message to [email protected] 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 [email protected] 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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

#9 lore raw
Quoted 49 lines · Vyacheslav Dubeyko

Hi Ryusuke,

Quoted 33 lines · Ryusuke Konishi
Quoted 27 lines · Vyacheslav Dubeyko

Hi Ryusuke,

On Thu, 2013-05-16 at 07:59 +0900, Ryusuke Konishi wrote:

[snip]

Quoted 8 lines
Quoted 8 lines

This patch still has a potential overflow issue that I pointed out in the previous comment; the patch handles the number of descriptor blocks in 32-bit wide variables without checking its upper limit.

If you won't to add checks for the number of descriptor blocks, I propose you to change the definition of nilfs_palloc_groups_count() instead:

Quoted 7 lines

Review

Quoted 7 lines
  static inline unsigned long
  nilfs_palloc_groups_count(const struct inode *inode)
  {
(quoted diff) +1 -1
- 	return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
+ 	return nilfs_palloc_groups_per_desc_block(inode) << 32;
  }

I think the real reason of problem is in using constants (BITS_PER_LONG for the first case and 32 for the second one). But, anyway, it makes sense to operate by volume size in this calculation. Because namely volume size is the real limitation for calculation of maximum available groups count.

Quoted 4 lines

What do you think about using volume size in this calculation?

With the best regards,
Vyacheslav Dubeyko.

Quoted 8 lines

I disagree with using volume size because it makes resize logic much harder especially for shrink logic. It requires reconstructing of ifile and DAT meatadata file.

I just want to fix the calculation of the maximum number of groups so that the number of descriptor blocks doesn't overflow both for 64-bit and 32-bit architectures.

Ok. I see.

What about such implementation?

Quoted 8 lines

static inline unsigned long nilfs_palloc_groups_count(const struct inode *inode) {

#define NILFS_DESC_BLOCKS_MAX UINT_MAX
	return nilfs_palloc_groups_per_desc_block(inode) *
			(unsigned long)NILFS_DESC_BLOCKS_MAX;

#undef NILFS_DESC_BLOCKS_MAX
}

No, the bit width of "unsigned int" and that of "unsigned long" are the same on 32-bit architectures (i.e. 32 bits). This function overflows.

Regards,
Ryusuke Konishi

Quoted 2 lines

With the best regards,
Vyacheslav Dubeyko.

--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

#10 lore raw

Hi Vyacheslav,

I reconsidered upper limit number of each parameter in the persistent object allocator, and reached a conclusion that the current implementation of nilfs_palloc_groups_count function below and other routines are consistent and reasonable.

static inline unsigned long
nilfs_palloc_groups_count(const struct inode *inode)
{
return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
}

The basic idea of the following nilfs_palloc_groups_count() routine is to represent serial number of objects (e.g. inode number, virtual block number) with an unsigned long type.

The entry number is addressed with a group number, which is the upper part of "unsigned long", and per-group offset number at the lower part.

For instance, the entry number consists of 17 bits group number and 15 bit per-group offset number in the case of 32 bit OS and 4kB block format:

MSB LSB
31 15 14 0

  +---------------------+------------------+
  |  Group number       | Per-group offset |
  |                     | number of entry  |
  +---------------------+------------------|
  |  Entry number (e.g. inode number,      |
  |        virtual block number,...)       |
  +----------------------------------------+

Then, number of entries per group, maximum number of groups, and maximum number of descriptor blocks become as follows:

--------------+-----------------+-----------------+----------------
Architecture | 32-bit | 64-bit | Calculation
--------------+-----------------+-----------------+----------------
Block size | 1kB | 4KB | 1kB | 4kB |
--------------+--------+--------+--------+--------+----------------

Number of     |        |        |        |        | Number of
entries per   | 2 ^ 13 | 2 ^ 15 | 2 ^ 13 | 2 ^ 15 | bits per
group (N1)    |        |        |        |        | block
--------------+--------+--------+--------+--------+----------------
Maximum number|        |        |        |        | (Number of ids
of groups (N2)| 2 ^ 19 | 2 ^ 17 | 2 ^ 51 | 2 ^ 49 | with unsigned
              |        |        |        |        | long type) / N1
--------------+--------+--------+--------+--------+----------------
Number of     |        |        |        |        | Number of 
groups per    | 2 ^ 8  | 2 ^ 10 | 2 ^ 8  | 2 ^ 10 | 32-bit counters
descriptor    |        |        |        |        | per block
block (N3)    |        |        |        |        |
--------------+--------+--------+--------+--------+----------------
Maximum number|        |        |        |        |
of descriptor | 2 ^ 11 | 2 ^ 7  | 2 ^ 43 | 2 ^ 39 | N2 / N3
blocks        |        |        |        |        |

--------------+--------+--------+--------+--------+----------------

where the maximum number of descriptor blocks requires "unsigned long" type for 64-bit OS.

So, please use unsigned long type for counters or ids of descriptor blocks in your third patch even if it seems too large to you. It looks simpler than other way of changes.

To avoid using an "unsinged int" type atomic counter for desciptor block calculation, I propose you to replace nilfs_palloc_count_desc_blocks function with the following implementation:

/**
* nilfs_palloc_count_desc_blocks - count descriptor blocks number
* @inode: inode of metadata file using this allocator
* @desc_blocks: descriptor blocks number [out]
*/
static int nilfs_palloc_count_desc_blocks(struct inode *inode,
unsigned long *desc_blocks)

{
	unsigned long blknum;
	int ret;

	ret = nilfs_bmap_last_key(NILFS_I(inode)->i_bmap, &blknum);
	if (likely(!ret))
		*desc_blocks = DIV_ROUND_UP(
			blknum, NILFS_MDT(inode)->mi_blocks_per_desc_block);
	return ret;
}

I believe this will help to simplify your patch.

With regards,
Ryusuke Konishi

Quoted 72 lines · Ryusuke Konishi
Quoted 49 lines · Vyacheslav Dubeyko

Hi Ryusuke,

Quoted 33 lines · Ryusuke Konishi
Quoted 27 lines · Vyacheslav Dubeyko

Hi Ryusuke,

On Thu, 2013-05-16 at 07:59 +0900, Ryusuke Konishi wrote:

[snip]

Quoted 8 lines
Quoted 8 lines

This patch still has a potential overflow issue that I pointed out in the previous comment; the patch handles the number of descriptor blocks in 32-bit wide variables without checking its upper limit.

If you won't to add checks for the number of descriptor blocks, I propose you to change the definition of nilfs_palloc_groups_count() instead:

Quoted 7 lines

Review

Quoted 7 lines
  static inline unsigned long
  nilfs_palloc_groups_count(const struct inode *inode)
  {
(quoted diff) +1 -1
- 	return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
+ 	return nilfs_palloc_groups_per_desc_block(inode) << 32;
  }

I think the real reason of problem is in using constants (BITS_PER_LONG for the first case and 32 for the second one). But, anyway, it makes sense to operate by volume size in this calculation. Because namely volume size is the real limitation for calculation of maximum available groups count.

Quoted 4 lines

What do you think about using volume size in this calculation?

With the best regards,
Vyacheslav Dubeyko.

Quoted 8 lines

I disagree with using volume size because it makes resize logic much harder especially for shrink logic. It requires reconstructing of ifile and DAT meatadata file.

I just want to fix the calculation of the maximum number of groups so that the number of descriptor blocks doesn't overflow both for 64-bit and 32-bit architectures.

Ok. I see.

What about such implementation?

Quoted 8 lines

static inline unsigned long nilfs_palloc_groups_count(const struct inode *inode) {

#define NILFS_DESC_BLOCKS_MAX UINT_MAX
	return nilfs_palloc_groups_per_desc_block(inode) *
			(unsigned long)NILFS_DESC_BLOCKS_MAX;

#undef NILFS_DESC_BLOCKS_MAX
}

No, the bit width of "unsigned int" and that of "unsigned long" are the same on 32-bit architectures (i.e. 32 bits). This function overflows.

Regards,
Ryusuke Konishi

Quoted 2 lines

With the best regards,
Vyacheslav Dubeyko.

--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html