On Wed, Dec 4, 2019, 7:52 AM Gao Xi= ang <gaoxiang25@huawei.com&= gt; wrote:

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 =3D (file_size / bloc= ksize)
> The array basically tracks number of holes before a particular logical= file block.
> e.g blks[i] =3D 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:
>
>=C2=A0 =C2=A0 blkno =3D start_block + (offset >> block_size_shift= ) - (number of
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 holes before block in = which offset falls)
>
> 3) If a read offset falls inside a hole (which can be found using abov= e array). We
>=C2=A0 =C2=A0 fill the user buffer with '\0' on the fly.
>
> through this,block no. lookup would still be performed in constant tim= e.
>
> 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 practic= al.we can use a linkedlist,
> but that will make size of inode variable.

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

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

Thanks,
Gao Xiang

>
> Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com&= gt;
> ---
>=C2=A0 lib/inode.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++= +++++++++++++-
>=C2=A0 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] =3D {
>=C2=A0
>=C2=A0 struct list_head inode_hashtable[NR_INODE_HASHTABLE];
>=C2=A0
> +
> +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) =3D=3D star= t &&=C2=A0 =C2=A0 =C2=A0 =C2=A0 \
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 roundup(end, EROFS_BLKSIZ) =3D=3D end &&=C2= =A0 =C2=A0 =C2=A0 =C2=A0\
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0(end - start) % EROFS_BLKSIZ =3D=3D 0)
> +#define HOLE_BLK=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-1 > +unsigned int erofs_detect_holes(struct erofs_inode *inode, int *blks)=
> +{
> +=C2=A0 =C2=A0 =C2=A0int i, fd, st, en;
> +=C2=A0 =C2=A0 =C2=A0unsigned int nblocks;
> +=C2=A0 =C2=A0 =C2=A0erofs_off_t data, hole, len;
> +
> +=C2=A0 =C2=A0 =C2=A0nblocks =3D inode->i_size / EROFS_BLKSIZ;
> +=C2=A0 =C2=A0 =C2=A0for (i =3D 0; i < nblocks; i++)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0blks[i] =3D 0;
> +=C2=A0 =C2=A0 =C2=A0fd =3D open(inode->i_srcpath, O_RDONLY);
> +=C2=A0 =C2=A0 =C2=A0if (fd < 0) {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return -errno;
> +=C2=A0 =C2=A0 =C2=A0}
> +=C2=A0 =C2=A0 =C2=A0len =3D lseek(fd, 0, SEEK_END);
> +=C2=A0 =C2=A0 =C2=A0if (lseek(fd, 0, SEEK_SET) =3D=3D -1)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return -errno;
> +=C2=A0 =C2=A0 =C2=A0data =3D 0;
> +=C2=A0 =C2=A0 =C2=A0while (data < len) {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0hole =3D lseek(fd, da= ta, SEEK_HOLE);
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (hole =3D=3D len)<= br> > +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0break;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0data =3D lseek(fd, ho= le, SEEK_DATA);
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (data < 0 || ho= le > data) {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0return -EINVAL;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (IS_HOLE(hole, dat= a)) {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0st =3D hole >> S_SHIFT;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0en =3D data >> S_SHIFT;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0nblocks -=3D (en - st);
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0for (i =3D st; i < en; i++)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0blks[i] =3D HOLE_BLK;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
> +=C2=A0 =C2=A0 =C2=A0}
> +=C2=A0 =C2=A0 =C2=A0return nblocks;
> +}
> +
> +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> +=C2=A0 =C2=A0 =C2=A0int i, nholes =3D 0;
> +=C2=A0 =C2=A0 =C2=A0for (i =3D 0; i < nblocks; i++) {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (blks[i] =3D=3D -1= )
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0nholes++;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0else {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0blks[i] =3D nholes;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0if (nholes >=3D (i + 1))
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return -EINVAL;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
> +=C2=A0 =C2=A0 =C2=A0}
> +=C2=A0 =C2=A0 =C2=A0return 0;
> +}
> +
>=C2=A0 void erofs_inode_manager_init(void)
>=C2=A0 {
>=C2=A0 =C2=A0 =C2=A0 =C2=A0unsigned int i;
> @@ -305,6 +360,7 @@ static bool erofs_file_is_compressible(struct erof= s_inode *inode)
>=C2=A0 int erofs_write_file(struct erofs_inode *inode)
>=C2=A0 {
>=C2=A0 =C2=A0 =C2=A0 =C2=A0unsigned int nblocks, i;
> +=C2=A0 =C2=A0 =C2=A0int *blks;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0int ret, fd;
>=C2=A0
>=C2=A0 =C2=A0 =C2=A0 =C2=A0if (!inode->i_size) {
> @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode *inode) >=C2=A0 =C2=A0 =C2=A0 =C2=A0/* fallback to all data uncompressed */
>=C2=A0 =C2=A0 =C2=A0 =C2=A0inode->datalayout =3D EROFS_INODE_FLAT_IN= LINE;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0nblocks =3D inode->i_size / EROFS_BLKSIZ;=
> -
> +=C2=A0 =C2=A0 =C2=A0blks =3D malloc(sizeof(int) * nblocks);
> +=C2=A0 =C2=A0 =C2=A0nblocks =3D erofs_detect_holes(inode, blks);
> +=C2=A0 =C2=A0 =C2=A0if (nblocks < 0)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return nblocks;
> +=C2=A0 =C2=A0 =C2=A0if ((ret =3D erofs_fill_holedata(blks, nblocks)) = !=3D 0) {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return ret;
> +=C2=A0 =C2=A0 =C2=A0}
>=C2=A0 =C2=A0 =C2=A0 =C2=A0ret =3D __allocate_inode_bh_data(inode, nblo= cks);
>=C2=A0 =C2=A0 =C2=A0 =C2=A0if (ret)
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return ret;
> @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode *inode) >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return -errno; >=C2=A0
>=C2=A0 =C2=A0 =C2=A0 =C2=A0for (i =3D 0; i < nblocks; ++i) {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (blks[i] =3D=3D HO= LE_BLK)
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0continue;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0char buf[EROFS_B= LKSIZ];
>=C2=A0
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0ret =3D read(fd,= buf, EROFS_BLKSIZ);
> @@ -962,3 +1026,4 @@ struct erofs_inode *erofs_mkfs_build_tree_from_pa= th(struct erofs_inode *parent,
>=C2=A0 =C2=A0 =C2=A0 =C2=A0return erofs_mkfs_build_tree(inode);
>=C2=A0 }
>=C2=A0
> +
> --
> 2.9.3
>