Linux-EROFS Archive on lore.kernel.org
 help / color / Atom feed
From: Gao Xiang <gaoxiang25@huawei.com>
To: Pratik Shinde <pratikshinde320@gmail.com>
Cc: miaoxie@huawei.com, linux-erofs@lists.ozlabs.org
Subject: Re: [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
Date: Wed, 4 Dec 2019 10:27:35 +0800
Message-ID: <20191204022734.GA60329@architecture4> (raw)
In-Reply-To: <20191203140250.23793-1-pratikshinde320@gmail.com>

Hi Pratik,

I'll give detailed words this weekend if you have more questions
since I'm busying in other stupid intra-company stuffs now...

On Tue, Dec 03, 2019 at 07:32:50PM +0530, Pratik Shinde wrote:
> NOTE: The patch is not fully complete yet, with this patch I just want to
> present rough idea of what I am trying to achieve.
> 
> The patch does following :
> 1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
> 2) Keep track of holes per file.
> 
> In-order to track holes, I used an array of size = (file_size / blocksize)
> The array basically tracks number of holes before a particular logical file block.
> e.g blks[i] = 10 meaning ith block has 10 holes before it.
> If a particular block is a hole we set the index to '-1'.
> 
> how read logic will change:
> 1) currently we simply map read offset to a fs block.
> 2) with holes in place the calculation of block number would be:
> 
>    blkno = start_block + (offset >> block_size_shift) - (number of 
>    							 holes before block in which offset falls)
> 
> 3) If a read offset falls inside a hole (which can be found using above array). We
>    fill the user buffer with '\0' on the fly.
> 
> through this,block no. lookup would still be performed in constant time.
> 
> The biggest problem with this approach is - we have to store the hole tracking
> array for every file to the disk.Which doesn't seems to be practical.we can use a linkedlist,
> but that will make size of inode variable.

"variable-sized inode" isn't a problem here, which can be handled
similar to the case of "compress indexes".

Probably no need to write linked list to the disk but generate linked list
in memory when writing data on the fly, and then transfer to a variable-sized
extent array at the time of writing inode metadata (The order is firstly data
and then metadata in erofs-utils so it looks practical.)

Thanks,
Gao Xiang

> 
> Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
> ---
>  lib/inode.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 66 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/inode.c b/lib/inode.c
> index 0e19b11..af31949 100644
> --- a/lib/inode.c
> +++ b/lib/inode.c
> @@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {
>  
>  struct list_head inode_hashtable[NR_INODE_HASHTABLE];
>  
> +
> +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) == start &&	\
> +		             roundup(end, EROFS_BLKSIZ) == end &&	\
> +			    (end - start) % EROFS_BLKSIZ == 0)
> +#define HOLE_BLK		-1
> +unsigned int erofs_detect_holes(struct erofs_inode *inode, int *blks)
> +{
> +	int i, fd, st, en;
> +	unsigned int nblocks;
> +	erofs_off_t data, hole, len;
> +
> +	nblocks = inode->i_size / EROFS_BLKSIZ;
> +	for (i = 0; i < nblocks; i++)
> +		blks[i] = 0;
> +	fd = open(inode->i_srcpath, O_RDONLY);
> +	if (fd < 0) {
> +		return -errno;
> +	}
> +	len = lseek(fd, 0, SEEK_END);
> +	if (lseek(fd, 0, SEEK_SET) == -1)
> +		return -errno;
> +	data = 0;
> +	while (data < len) {
> +		hole = lseek(fd, data, SEEK_HOLE);
> +		if (hole == len)
> +			break;
> +		data = lseek(fd, hole, SEEK_DATA);
> +		if (data < 0 || hole > data) {
> +			return -EINVAL;
> +		}
> +		if (IS_HOLE(hole, data)) {
> +			st = hole >> S_SHIFT;
> +			en = data >> S_SHIFT;
> +			nblocks -= (en - st);
> +			for (i = st; i < en; i++)
> +				blks[i] = HOLE_BLK;
> +		}
> +	}
> +	return nblocks;
> +}
> +
> +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> +	int i, nholes = 0;
> +	for (i = 0; i < nblocks; i++) {
> +		if (blks[i] == -1)
> +			nholes++;
> +		else {
> +			blks[i] = nholes;
> +			if (nholes >= (i + 1))
> +				return -EINVAL;
> +		}
> +	}
> +	return 0;
> +}
> +
>  void erofs_inode_manager_init(void)
>  {
>  	unsigned int i;
> @@ -305,6 +360,7 @@ static bool erofs_file_is_compressible(struct erofs_inode *inode)
>  int erofs_write_file(struct erofs_inode *inode)
>  {
>  	unsigned int nblocks, i;
> +	int *blks;
>  	int ret, fd;
>  
>  	if (!inode->i_size) {
> @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode *inode)
>  	/* fallback to all data uncompressed */
>  	inode->datalayout = EROFS_INODE_FLAT_INLINE;
>  	nblocks = inode->i_size / EROFS_BLKSIZ;
> -
> +	blks = malloc(sizeof(int) * nblocks);
> +	nblocks = erofs_detect_holes(inode, blks);
> +	if (nblocks < 0)
> +		return nblocks;
> +	if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
> +		return ret;
> +	}
>  	ret = __allocate_inode_bh_data(inode, nblocks);
>  	if (ret)
>  		return ret;
> @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode *inode)
>  		return -errno;
>  
>  	for (i = 0; i < nblocks; ++i) {
> +		if (blks[i] == HOLE_BLK)
> +			continue;
>  		char buf[EROFS_BLKSIZ];
>  
>  		ret = read(fd, buf, EROFS_BLKSIZ);
> @@ -962,3 +1026,4 @@ struct erofs_inode *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
>  	return erofs_mkfs_build_tree(inode);
>  }
>  
> +
> -- 
> 2.9.3
> 

  reply index

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-12-03 14:02 Pratik Shinde
2019-12-04  2:27 ` Gao Xiang [this message]
2019-12-09  7:04   ` Pratik Shinde
2019-12-09  7:18     ` Gao Xiang

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20191204022734.GA60329@architecture4 \
    --to=gaoxiang25@huawei.com \
    --cc=linux-erofs@lists.ozlabs.org \
    --cc=miaoxie@huawei.com \
    --cc=pratikshinde320@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-EROFS Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-erofs/0 linux-erofs/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-erofs linux-erofs/ https://lore.kernel.org/linux-erofs \
		linux-erofs@lists.ozlabs.org linux-erofs@ozlabs.org
	public-inbox-index linux-erofs

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.ozlabs.lists.linux-erofs


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git