From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.2 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A7267C2D0CF for ; Tue, 24 Dec 2019 10:05:51 +0000 (UTC) Received: from lists.ozlabs.org (lists.ozlabs.org [203.11.71.2]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 6227B2071A for ; Tue, 24 Dec 2019 10:05:51 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 6227B2071A Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=huawei.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=linux-erofs-bounces+linux-erofs=archiver.kernel.org@lists.ozlabs.org Received: from lists.ozlabs.org (lists.ozlabs.org [IPv6:2401:3900:2:1::3]) by lists.ozlabs.org (Postfix) with ESMTP id 47hsL54S7tzDqMr for ; Tue, 24 Dec 2019 21:05:49 +1100 (AEDT) Authentication-Results: lists.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=huawei.com (client-ip=45.249.212.188; helo=huawei.com; envelope-from=gaoxiang25@huawei.com; receiver=) Authentication-Results: lists.ozlabs.org; dmarc=none (p=none dis=none) header.from=huawei.com Received: from huawei.com (szxga02-in.huawei.com [45.249.212.188]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 47hsKz6lMhzDqKr for ; Tue, 24 Dec 2019 21:05:39 +1100 (AEDT) Received: from DGGEMM402-HUB.china.huawei.com (unknown [172.30.72.54]) by Forcepoint Email with ESMTP id 84E48F39276A355A652B for ; Tue, 24 Dec 2019 18:05:28 +0800 (CST) Received: from dggeme762-chm.china.huawei.com (10.3.19.108) by DGGEMM402-HUB.china.huawei.com (10.3.20.210) with Microsoft SMTP Server (TLS) id 14.3.439.0; Tue, 24 Dec 2019 18:05:28 +0800 Received: from architecture4 (10.160.196.180) by dggeme762-chm.china.huawei.com (10.3.19.108) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1713.5; Tue, 24 Dec 2019 18:05:27 +0800 Date: Tue, 24 Dec 2019 18:05:11 +0800 From: Gao Xiang To: Pratik Shinde Subject: Re: [RFCv2] erofs-utils:code for detecting and tracking holes in uncompressed sparse files. Message-ID: <20191224100511.GB164058@architecture4> References: <20191223172938.13189-1-pratikshinde320@gmail.com> <20191224034817.GA164058@architecture4> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.9.4 (2018-02-28) X-Originating-IP: [10.160.196.180] X-ClientProxiedBy: dggeme712-chm.china.huawei.com (10.1.199.108) To dggeme762-chm.china.huawei.com (10.3.19.108) X-CFilter-Loop: Reflected X-BeenThere: linux-erofs@lists.ozlabs.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Development of Linux EROFS file system List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: miaoxie@huawei.com, linux-erofs@lists.ozlabs.org Errors-To: linux-erofs-bounces+linux-erofs=archiver.kernel.org@lists.ozlabs.org Sender: "Linux-erofs" 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.