Re: [pbs-devel] [PATCH v2 backup 1/5] add and implement chunk_from_offset for IndexFile

[Stefan Reiter <s.reiter@proxmox.com>]

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 <s.reiter@proxmox.com>
>> ---
>>   src/backup/dynamic_index.rs | 18 ++++++++++++++++++
>>   src/backup/fixed_index.rs   | 11 +++++++++++
>>   src/backup/index.rs         |  3 +++
>>   3 files changed, 32 insertions(+)
>>
>> diff --git a/src/backup/dynamic_index.rs b/src/backup/dynamic_index.rs
>> index 4907fe1f..887b7cf3 100644
>> --- a/src/backup/dynamic_index.rs
>> +++ b/src/backup/dynamic_index.rs
>> @@ -216,6 +216,24 @@ impl IndexFile for DynamicIndexReader {
>>               digest: self.index[pos].digest.clone(),
>>           })
>>       }
>> +
>> +    fn chunk_from_offset(&self, offset: u64) -> Option<(usize, u64)> {
>> +        let end_idx = self.index.len() - 1;
>> +        let end = self.chunk_end(end_idx);
>> +        let found_idx = self.binary_search(0, 0, end_idx, end, offset);
>> +        let found_idx = match found_idx {
>> +            Ok(i) => i,
>> +            Err(_) => return None
>> +        };
>> +
>> +        let found_start = if found_idx == 0 {
>> +            0
>> +        } else {
>> +            self.chunk_end(found_idx - 1)
>> +        };
>> +
>> +        Some((found_idx, offset - found_start))
>> +    }
>>   }
>>   
>>   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 {
>>   
>>           (csum, chunk_end)
>>       }
>> +
>> +    fn chunk_from_offset(&self, offset: u64) -> Option<(usize, u64)> {
>> +        if offset >= self.size {
>> +            return None;
>> +        }
>> +
>> +        Some((
>> +            (offset / self.chunk_size as u64) as usize,
>> +            offset % self.chunk_size as u64
> 
> modulo is really slow, but isn't chunk_size always a 2^x and thus we can
> do the same here as we do in other places:
> 
> offset & (self.chunk_size - 1)
> 

I found it more readable this way and I don't think it's hot-path enough 
to make a real difference in performance.

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.

>> +        ))
>> +    }
>>   }
>>   
>>   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 {
>>       fn index_bytes(&self) -> u64;
>>       fn chunk_info(&self, pos: usize) -> Option<ChunkReadInfo>;
>>   
>> +    /// Get the chunk index and the relative offset within it for a byte offset
>> +    fn chunk_from_offset(&self, offset: u64) -> Option<(usize, u64)>;
>> +
>>       /// Compute index checksum and size
>>       fn compute_csum(&self) -> ([u8; 32], u64);
>>   
>>
>