[RFCv2] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.

[Pratik Shinde]

Hi Gao,

No no. What I am saying is - in the current code (excluding all my changes)
the block lookup will happens in constant time. with only hole list it
won't be O(1) time but rather we have to traverse the holes list. (say in
binary search way).
what I don't understand is - what is the purpose of tracking data extents.
hope you get it.

--Pratik.



On Tue, Dec 24, 2019, 3:35 PM Gao Xiang <gaoxiang25 at huawei.com> wrote:

> Hi Pratik,
>
> On Tue, Dec 24, 2019 at 03:05:53PM +0530, Pratik Shinde wrote:
> > Hello Gao,
> >
> > Thanks for the review.
> > If I understand correctly , you wish to keep track of every extent
> assigned
> > to the file.
> > in case of file without any holes in it, there will single extent
> > representing the entire file.
> >
> > Also, the current block no. lookup happens in constant time. (since we
> only
> > record the start blk no.)
> > If we use extent record for finding given block no. it can't be done in
> > constant time correct ? (maybe in LogN)
>
>
> Could I ask a question?
> In short, how can we use the proposal approach to read random blocks
> in constant time O(1)?
>
> e.g.
>  if you have two holes 2...4  7...10 in a file with 12 blocks.
>
>  if we want to random access block 11, only block number 1,5,6,11 were
>  saved one by one (maybe p1,p2,p3,p4).
>
>  How can we get the physical address (p4) of block 11 directly without
>  scanning the previous holes?
>
> Thanks,
> Gao Xiang
>
>
> >
> > I think I don't fully understand reason for recording extents assigned
> to a
> > file.Since the current design
> > is already time and space optimized & there are no deletions happening.
> > Is it for some future requirement ?
> >
> > --Pratik.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/linux-erofs/attachments/20191224/081102a5/attachment.htm>