From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from firstgate.proxmox.com (firstgate.proxmox.com [212.224.123.68]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by lists.proxmox.com (Postfix) with ESMTPS id BFB006536F for ; Wed, 22 Jul 2020 16:42:28 +0200 (CEST) Received: from firstgate.proxmox.com (localhost [127.0.0.1]) by firstgate.proxmox.com (Proxmox) with ESMTP id ADF5821C1F for ; Wed, 22 Jul 2020 16:41:58 +0200 (CEST) Received: from proxmox-new.maurer-it.com (proxmox-new.maurer-it.com [212.186.127.180]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by firstgate.proxmox.com (Proxmox) with ESMTPS id 54E2C21C13 for ; Wed, 22 Jul 2020 16:41:57 +0200 (CEST) Received: from proxmox-new.maurer-it.com (localhost.localdomain [127.0.0.1]) by proxmox-new.maurer-it.com (Proxmox) with ESMTP id 1B105431A8 for ; Wed, 22 Jul 2020 16:41:57 +0200 (CEST) To: Proxmox Backup Server development discussion , Stefan Reiter References: <20200722135625.23653-1-s.reiter@proxmox.com> <20200722135625.23653-2-s.reiter@proxmox.com> <05152997-427c-2cb9-014d-068c74935434@proxmox.com> <33d25d9d-5f17-3064-7a84-1e908f439a9d@proxmox.com> From: Thomas Lamprecht Message-ID: Date: Wed, 22 Jul 2020 16:41:56 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:79.0) Gecko/20100101 Thunderbird/79.0 MIME-Version: 1.0 In-Reply-To: <33d25d9d-5f17-3064-7a84-1e908f439a9d@proxmox.com> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: quoted-printable X-SPAM-LEVEL: Spam detection results: 0 AWL 0.008 Adjusted score from AWL reputation of From: address KAM_DMARC_STATUS 0.01 Test Rule for DKIM or SPF Failure with Strict Alignment NICE_REPLY_A -0.001 Looks like a legit reply (A) RCVD_IN_DNSWL_MED -2.3 Sender listed at https://www.dnswl.org/, medium trust SPF_HELO_NONE 0.001 SPF: HELO does not publish an SPF Record SPF_PASS -0.001 SPF: sender matches SPF record URIBL_BLOCKED 0.001 ADMINISTRATOR NOTICE: The query to URIBL was blocked. See http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block for more information. [index.rs] Subject: Re: [pbs-devel] [PATCH v2 backup 1/5] add and implement chunk_from_offset for IndexFile X-BeenThere: pbs-devel@lists.proxmox.com X-Mailman-Version: 2.1.29 Precedence: list List-Id: Proxmox Backup Server development discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 22 Jul 2020 14:42:28 -0000 On 22.07.20 16:24, Stefan Reiter wrote: > On 7/22/20 4:16 PM, Thomas Lamprecht wrote: >> On 22.07.20 15:56, Stefan Reiter wrote: >>> Necessary for byte-wise seeking through chunks in an index. >>> >>> Signed-off-by: Stefan Reiter >>> --- >>> =C2=A0 src/backup/dynamic_index.rs | 18 ++++++++++++++++++ >>> =C2=A0 src/backup/fixed_index.rs=C2=A0=C2=A0 | 11 +++++++++++ >>> =C2=A0 src/backup/index.rs=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0 |=C2=A0 3 +++ >>> =C2=A0 3 files changed, 32 insertions(+) >>> >>> diff --git a/src/backup/dynamic_index.rs b/src/backup/dynamic_index.r= s >>> index 4907fe1f..887b7cf3 100644 >>> --- a/src/backup/dynamic_index.rs >>> +++ b/src/backup/dynamic_index.rs >>> @@ -216,6 +216,24 @@ impl IndexFile for DynamicIndexReader { >>> =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 digest: self.index[pos].digest.clone(), >>> =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 fn chunk_from_offset(&self, offset: u64) -> Optio= n<(usize, u64)> { >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 let end_idx =3D self.inde= x.len() - 1; >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 let end =3D self.chunk_en= d(end_idx); >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 let found_idx =3D self.bi= nary_search(0, 0, end_idx, end, offset); >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 let found_idx =3D match f= ound_idx { >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 O= k(i) =3D> i, >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 E= rr(_) =3D> return None >>> +=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 let found_start =3D if fo= und_idx =3D=3D 0 { >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 0= >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 } else { >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 s= elf.chunk_end(found_idx - 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 Some((found_idx, offset -= found_start)) >>> +=C2=A0=C2=A0=C2=A0 } >>> =C2=A0 } >>> =C2=A0 =C2=A0 struct CachedChunk { >>> diff --git a/src/backup/fixed_index.rs b/src/backup/fixed_index.rs >>> index 73d0dad0..b7e785d6 100644 >>> --- a/src/backup/fixed_index.rs >>> +++ b/src/backup/fixed_index.rs >>> @@ -219,6 +219,17 @@ impl IndexFile for FixedIndexReader { >>> =C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 (csum, = chunk_end) >>> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 } >>> + >>> +=C2=A0=C2=A0=C2=A0 fn chunk_from_offset(&self, offset: u64) -> Optio= n<(usize, u64)> { >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 if offset >=3D self.size = { >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 r= eturn None; >>> +=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 Some(( >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 (= offset / self.chunk_size as u64) as usize, >>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 o= ffset % self.chunk_size as u64 >> >> modulo is really slow, but isn't chunk_size always a 2^x and thus we c= an >> do the same here as we do in other places: >> >> offset & (self.chunk_size - 1) >> >=20 > I found it more readable this way and I don't think it's hot-path enoug= h to make a real difference in performance. then why not add a comment instead? This is some orders of magnitude slow= er, not just 2 or 3% ... >=20 > But I don't mind, could even replace the div as well. Maybe an assert!(= chunk_size.is_power_of_two()) might be good somewhere though. Yeah, somewhere in an initial entry point to such code an assert wouldn't= hurt. >=20 >>> +=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 pub struct FixedIndexWriter { >>> diff --git a/src/backup/index.rs b/src/backup/index.rs >>> index efdf3b54..2eab8524 100644 >>> --- a/src/backup/index.rs >>> +++ b/src/backup/index.rs >>> @@ -22,6 +22,9 @@ pub trait IndexFile { >>> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 fn index_bytes(&self) -> u64; >>> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 fn chunk_info(&self, pos: usize) -> Op= tion; >>> =C2=A0 +=C2=A0=C2=A0=C2=A0 /// Get the chunk index and the relative o= ffset within it for a byte offset >>> +=C2=A0=C2=A0=C2=A0 fn chunk_from_offset(&self, offset: u64) -> Optio= n<(usize, u64)>; >>> + >>> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 /// Compute index checksum and size >>> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 fn compute_csum(&self) -> ([u8; 32], u= 64); >>> =C2=A0 >>