[pbs-devel] [PATCH RFC proxmox/proxmox-backup] restore files from pxar sparsely

[pbs-devel] [PATCH RFC proxmox/proxmox-backup] restore files from pxar sparsely

[Dominik Csapak]

to be able to restore containers with big sparse files

ideally(?) we would save hole information directly in the pxar archive
and not even use zero chunks, so that we can have smaller
pxar archives, and accurately restore sparse files like they were before

for now, restore all files sparsely

proxmox:

Dominik Csapak (2):
  add tools/zero: add fast zero comparison code
  proxmox: add sparse_copy(_async) to tools::io

 proxmox/src/tools/io/mod.rs |  62 ++++++++++
 proxmox/src/tools/mod.rs    |   1 +
 proxmox/src/tools/zero.rs   | 233 ++++++++++++++++++++++++++++++++++++
 3 files changed, 296 insertions(+)
 create mode 100644 proxmox/src/tools/zero.rs

proxmox-backup:

Dominik Csapak (1):
  pxar/extrac: if possible create files sparesly

 src/pxar/extract.rs | 32 ++++++++++++++++++++++++++------
 1 file changed, 26 insertions(+), 6 deletions(-)

-- 
2.20.1

[pbs-devel] [PATCH proxmox 1/2] add tools/zero: add fast zero comparison code

[Dominik Csapak]

that can make use of see/avx instructions where available

this is mostly a direct translation of qemu's util/bufferiszero.c

this is originally from Wolfgang Bumiller

Signed-off-by: Dominik Csapak <d.csapak@proxmox.com>
---
 proxmox/src/tools/mod.rs  |   1 +
 proxmox/src/tools/zero.rs | 233 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 234 insertions(+)
 create mode 100644 proxmox/src/tools/zero.rs

diff --git a/proxmox/src/tools/mod.rs b/proxmox/src/tools/mod.rs
index ff3a720..49418a4 100644
--- a/proxmox/src/tools/mod.rs
+++ b/proxmox/src/tools/mod.rs
@@ -20,6 +20,7 @@ pub mod serde;
 pub mod time;
 pub mod uuid;
 pub mod vec;
+pub mod zero;
 
 #[cfg(feature = "websocket")]
 pub mod websocket;
diff --git a/proxmox/src/tools/zero.rs b/proxmox/src/tools/zero.rs
new file mode 100644
index 0000000..7493262
--- /dev/null
+++ b/proxmox/src/tools/zero.rs
@@ -0,0 +1,233 @@
+#[cfg(test)]
+mod test {
+    use std::mem;
+
+    pub(super) fn do_zero_test(func: fn(&[u8]) -> bool, short: bool) {
+        let mut buf: [u8; 512] = unsafe { mem::zeroed() };
+        assert_eq!(func(&buf), true);
+        for i in 0..buf.len() {
+            buf[i] = 1;
+            assert_eq!(func(&buf), false);
+            buf[i] = 0;
+        }
+        if short {
+            for i in 0..8 {
+                assert_eq!(func(&buf[0..i+1]), true);
+                buf[i] = 1;
+                assert_eq!(func(&buf[0..i+1]), false);
+                buf[i] = 0;
+            }
+        }
+    }
+}
+
+//#[cfg(all(target_arch = "x86_64", target_feature = "sse4"))]
+#[cfg(target_arch = "x86_64")]
+mod x86_64 {
+    use std::arch::x86_64::*;
+
+    const BIT_OSXSAVE: u32 = 1<<27;
+    const BIT_SSE2:    u32 = 1<<26;
+    const BIT_SSE4_1:  u32 = 1<<19;
+    const BIT_AVX:     u32 = 1<<28;
+    const BIT_AVX2:    u32 = 1<< 5;
+
+    // Direct translation of buffer_zero_sse2() of qemu's util/bufferiszero.c
+    fn buffer_is_zero_sse2(buf_slice: &[u8]) -> bool {
+        unsafe {
+            let len = buf_slice.len();
+            let buf = buf_slice.as_ptr() as *const u8;
+            let mut t = _mm_loadu_si128(buf as *const __m128i);
+            let mut p = ((buf as usize + 5*16) & !0xf) as *const __m128i;
+            let e = ((buf as usize + len) & !0xf) as *const __m128i;
+            let zero: __m128i = _mm_setzero_si128();
+            while p <= e {
+                _mm_prefetch(p as *const i8, _MM_HINT_T0);
+                t = _mm_cmpeq_epi8(t, zero);
+                if _mm_movemask_epi8(t) != 0xFFFF {
+                    return false;
+                }
+                t = *p.offset(-4);
+                t = _mm_or_si128(t, *p.offset(-3));
+                t = _mm_or_si128(t, *p.offset(-2));
+                t = _mm_or_si128(t, *p.offset(-1));
+                p = p.offset(4);
+            }
+            t = _mm_or_si128(t, *e.offset(-3));
+            t = _mm_or_si128(t, *e.offset(-2));
+            t = _mm_or_si128(t, *e.offset(-1));
+            t = _mm_or_si128(t, _mm_loadu_si128(
+                buf.add(len-16) as *const __m128i));
+            return _mm_movemask_epi8(_mm_cmpeq_epi8(t, zero)) == 0xFFFF;
+        }
+    }
+    #[test]
+    fn test_sse2() {
+        super::test::do_zero_test(buffer_is_zero_sse2, false);
+    }
+
+    // Direct translation of buffer_zero_sse4() of qemu's util/bufferiszero.c
+    fn buffer_is_zero_sse4_1(buf_slice: &[u8]) -> bool {
+        unsafe {
+            let len = buf_slice.len();
+            let buf = buf_slice.as_ptr() as *const u8;
+            let mut t = _mm_loadu_si128(buf as *const __m128i);
+            let mut p = ((buf as usize + 5*16) & !0xf) as *const __m128i;
+            let e = ((buf as usize + len) & !0xf) as *const __m128i;
+            while p <= e {
+                _mm_prefetch(p as *const i8, _MM_HINT_T0);
+                if _mm_testz_si128(t, t) == 0 {
+                    return false;
+                }
+                t = *p.offset(-4);
+                t = _mm_or_si128(t, *p.offset(-3));
+                t = _mm_or_si128(t, *p.offset(-2));
+                t = _mm_or_si128(t, *p.offset(-1));
+                p = p.offset(4);
+            }
+            t = _mm_or_si128(t, *e.offset(-3));
+            t = _mm_or_si128(t, *e.offset(-2));
+            t = _mm_or_si128(t, *e.offset(-1));
+            t = _mm_or_si128(t, _mm_loadu_si128(
+                buf.add(len-16) as *const __m128i));
+            return _mm_testz_si128(t, t) != 0;
+        }
+    }
+    #[test]
+    fn test_sse4_1() {
+        super::test::do_zero_test(buffer_is_zero_sse4_1, false);
+    }
+
+    // Direct translation of buffer_zero_avx2() of qemu's util/bufferiszero.c
+    fn buffer_is_zero_avx2(buf_slice: &[u8]) -> bool {
+        unsafe {
+            let len = buf_slice.len();
+            let buf = buf_slice.as_ptr() as *const u8;
+            let mut t = _mm256_loadu_si256(buf as *const __m256i);
+            let mut p = ((buf as usize + 5*32) & !0x1f) as *const __m256i;
+            let e = ((buf as usize + len) & !0x1f) as *const __m256i;
+            if p <= e {
+                // loop over 32 byte aligned blocks of 128
+                while p <= e {
+                    _mm_prefetch(p as *const i8, _MM_HINT_T0);
+                    if _mm256_testz_si256(t, t) == 0 {
+                        return false;
+                    }
+                    t = *p.offset(-4);
+                    t = _mm256_or_si256(t, *p.offset(-3));
+                    t = _mm256_or_si256(t, *p.offset(-2));
+                    t = _mm256_or_si256(t, *p.offset(-1));
+                    p = p.offset(4);
+                }
+                t = _mm256_or_si256(t, _mm256_loadu_si256(buf.add(len - 4*32) as *const __m256i));
+                t = _mm256_or_si256(t, _mm256_loadu_si256(buf.add(len - 3*32) as *const __m256i));
+            } else {
+                t = _mm256_or_si256(t, _mm256_loadu_si256(
+                    buf.add(32) as *const __m256i));
+                if len > 128 {
+                    t = _mm256_or_si256(t, _mm256_loadu_si256(buf.add(len - 4*32) as *const __m256i));
+                    t = _mm256_or_si256(t, _mm256_loadu_si256(buf.add(len - 3*32) as *const __m256i));
+                }
+            }
+            t = _mm256_or_si256(t, _mm256_loadu_si256(buf.add(len - 2*32) as *const __m256i));
+            t = _mm256_or_si256(t, _mm256_loadu_si256(buf.add(len - 1*32) as *const __m256i));
+            return _mm256_testz_si256(t, t) != 0;
+        }
+    }
+    #[test]
+    fn test_avx2() {
+        super::test::do_zero_test(buffer_is_zero_avx2, false);
+    }
+
+    // From qemu's (util/bufferiszero.c) init_cpuid_cache() + init_accel()
+    pub(super) fn init() {
+        unsafe {
+            let (max, _) = __get_cpuid_max(0);
+            if max >= 1 {
+                let id = __cpuid(1);
+                let avx_bits = BIT_OSXSAVE | BIT_AVX;
+                if (id.ecx & avx_bits) == avx_bits && max >= 7 {
+                    let bv = _xgetbv(0);
+                    let id70 = __cpuid_count(7, 0);
+                    if (bv & 6) == 6 && (id70.ebx & BIT_AVX2) == BIT_AVX2 {
+                        super::BUFFER_IS_ZERO_FUNC = buffer_is_zero_avx2;
+                        return;
+                    }
+                }
+
+                if (id.ecx & BIT_SSE4_1) == BIT_SSE4_1 {
+                    super::BUFFER_IS_ZERO_FUNC = buffer_is_zero_sse4_1;
+                    return;
+                }
+                if (id.edx & BIT_SSE2) == BIT_SSE2 {
+                    super::BUFFER_IS_ZERO_FUNC = buffer_is_zero_sse2;
+                    return
+                }
+            }
+            super::BUFFER_IS_ZERO_FUNC = super::buffer_is_zero_compat;
+        }
+    }
+}
+
+fn buffer_is_zero_compat(buf: &[u8]) -> bool{
+    let len = buf.len();
+    if len < 8 {
+        return buf.iter().fold(0, |a, x| a|x) == 0;
+    }
+
+    unsafe {
+        let mut ptr = buf.as_ptr() as *const u64;
+        let end = ((buf.as_ptr() as usize + len) & !7) as *const u64;
+        let mut t = ptr.read_unaligned();
+        ptr = ((ptr as usize + 8) & !7) as *const u64;
+        while ptr.add(8) <= end {
+            // XXX: add a prefetch_read_data() once it's stable...
+            if t != 0 {
+                return false;
+            }
+
+            t = *ptr | *ptr.add(1) | *ptr.add(2) | *ptr.add(3)
+              | *ptr.add(4) | *ptr.add(5) | *ptr.add(6) | *ptr.add(7);
+            ptr = ptr.add(8);
+        }
+        while ptr < end {
+            t |= *ptr;
+            ptr = ptr.add(1);
+        }
+        t |= end.offset(-1).read_unaligned();
+        return t == 0;
+    }
+}
+
+#[test]
+fn test_zero_compat() {
+    test::do_zero_test(buffer_is_zero_compat, true);
+}
+
+static BUF_IS_ZERO_GUARD: ::std::sync::Once = ::std::sync::Once::new();
+pub(self) static mut BUFFER_IS_ZERO_FUNC: fn(&[u8]) -> bool
+    = first_buffer_is_zero;
+
+fn first_buffer_is_zero(buf: &[u8]) -> bool {
+    BUF_IS_ZERO_GUARD.call_once(|| {
+        if cfg!(target_arch = "x86_64") {
+            x86_64::init();
+        }
+    });
+    return unsafe { BUFFER_IS_ZERO_FUNC(buf) };
+}
+
+pub fn buffer_is_zero(buf: &[u8]) -> bool {
+    if buf.len() == 0 {
+        return false;
+    }
+    if buf.len() < 64 {
+        return buffer_is_zero_compat(buf);
+    }
+    return unsafe { BUFFER_IS_ZERO_FUNC(buf) };
+}
+
+#[test]
+fn test_initialization() {
+    test::do_zero_test(buffer_is_zero, false);
+}
-- 
2.20.1

[pbs-devel] [PATCH proxmox 2/2] proxmox: add sparse_copy(_async) to tools::io

[Dominik Csapak]

this is able to seek the target instead of writing zeroes, which
generates sparse files where supported

it does not guarantee that all zero bytes are skipped, only when the
buffer after a read solely consists of zeroes

Signed-off-by: Dominik Csapak <d.csapak@proxmox.com>
---
 proxmox/src/tools/io/mod.rs | 62 +++++++++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)

diff --git a/proxmox/src/tools/io/mod.rs b/proxmox/src/tools/io/mod.rs
index 2e92ebb..53f767c 100644
--- a/proxmox/src/tools/io/mod.rs
+++ b/proxmox/src/tools/io/mod.rs
@@ -3,8 +3,70 @@
 //! The [`ReadExt`] trait provides additional operations for handling byte buffers for types
 //! implementing [`Read`](std::io::Read).
 
+use std::io::{self, Read, Write, Seek, SeekFrom, ErrorKind};
+
 mod read;
 pub use read::*;
 
 mod write;
 pub use write::*;
+
+/// copy similar to io::copy, but seeks the target when encountering
+/// zero bytes instead of writing them
+pub fn sparse_copy<R: Read + ?Sized, W: Write + Seek + ?Sized>(
+    reader: &mut R,
+    writer: &mut W,
+) -> Result<u64, io::Error> {
+    let mut buf = crate::tools::byte_buffer::ByteBuffer::new();
+    let mut written = 0;
+    loop {
+        let len = match buf.read_from(reader) {
+            Ok(0) => return Ok(written),
+            Ok(len) => len,
+            Err(ref e) if e.kind() == ErrorKind::Interrupted => continue,
+            Err(e) => return Err(e),
+        };
+
+        if crate::tools::zero::buffer_is_zero(&buf[..]) {
+            writer.seek(SeekFrom::Current(len as i64))?;
+        } else {
+            writer.write_all(&buf[..])?;
+        }
+        buf.clear();
+        written += len as u64;
+    }
+}
+
+#[cfg(feature = "tokio")]
+use tokio::io::{AsyncReadExt, AsyncWriteExt, AsyncSeekExt};
+
+#[cfg(feature = "tokio")]
+/// copy similar to tokio::io::copy, but seeks the target when encountering
+/// zero bytes instead of writing them
+pub async fn sparse_copy_async<R, W>(
+    reader: &mut R,
+    writer: &mut W,
+) -> Result<u64, io::Error>
+where
+    R: AsyncReadExt + Unpin,
+    W: AsyncWriteExt + AsyncSeekExt + Unpin,
+{
+    let mut buf = crate::tools::byte_buffer::ByteBuffer::new();
+    let mut written = 0;
+    loop {
+        let len = match buf.read_from_async(reader).await {
+            Ok(0) => return Ok(written),
+            Ok(len) => len,
+            Err(ref e) if e.kind() == ErrorKind::Interrupted => continue,
+            Err(e) => return Err(e),
+        };
+
+        if crate::tools::zero::buffer_is_zero(&buf[..]) {
+            writer.seek(SeekFrom::Current(len as i64)).await?;
+        } else {
+            writer.write_all(&buf[..]).await?;
+        }
+        buf.clear();
+        written += len as u64;
+    }
+}
-- 
2.20.1

[pbs-devel] [PATCH proxmox-backup 1/1] pxar/extrac: if possible create files sparesly

[Dominik Csapak]

instead of filling them with zeroes

this fixes an issue where we could not restore a container with large
sparse files in the backup (e.g. a 10GiB sparse file in a container
with a 8GiB disk)

Signed-off-by: Dominik Csapak <d.csapak@proxmox.com>
---
 src/pxar/extract.rs | 32 ++++++++++++++++++++++++++------
 1 file changed, 26 insertions(+), 6 deletions(-)

diff --git a/src/pxar/extract.rs b/src/pxar/extract.rs
index ed238a2c..dd084ead 100644
--- a/src/pxar/extract.rs
+++ b/src/pxar/extract.rs
@@ -18,7 +18,10 @@ use pxar::format::Device;
 use pxar::Metadata;
 
 use proxmox::c_result;
-use proxmox::tools::fs::{create_path, CreateOptions};
+use proxmox::tools::{
+    fs::{create_path, CreateOptions},
+    io::{sparse_copy, sparse_copy_async}
+};
 
 use crate::pxar::dir_stack::PxarDirStack;
 use crate::pxar::metadata;
@@ -392,6 +395,11 @@ impl Extractor {
             )
         };
 
+        let copy_sparse = match nix::unistd::ftruncate(file.as_raw_fd(), size as i64) {
+            Ok(_) => true,
+            Err(_) => false,
+        };
+
         metadata::apply_initial_flags(
             self.feature_flags,
             metadata,
@@ -399,8 +407,12 @@ impl Extractor {
             &mut self.on_error,
         )?;
 
-        let extracted = io::copy(&mut *contents, &mut file)
-            .map_err(|err| format_err!("failed to copy file contents: {}", err))?;
+        let extracted = if copy_sparse {
+            sparse_copy(&mut *contents, &mut file)
+        } else {
+            io::copy(&mut *contents, &mut file)
+        }.map_err(|err| format_err!("failed to copy file contents: {}", err))?;
+
         if size != extracted {
             bail!("extracted {} bytes of a file of {} bytes", extracted, size);
         }
@@ -434,6 +446,11 @@ impl Extractor {
             )
         });
 
+        let copy_sparse = match nix::unistd::ftruncate(file.as_raw_fd(), size as i64) {
+            Ok(_) => true,
+            Err(_) => false,
+        };
+
         metadata::apply_initial_flags(
             self.feature_flags,
             metadata,
@@ -441,9 +458,12 @@ impl Extractor {
             &mut self.on_error,
         )?;
 
-        let extracted = tokio::io::copy(&mut *contents, &mut file)
-            .await
-            .map_err(|err| format_err!("failed to copy file contents: {}", err))?;
+        let extracted = if copy_sparse {
+            sparse_copy_async(&mut *contents, &mut file).await
+        } else {
+            tokio::io::copy(&mut *contents, &mut file).await
+        }.map_err(|err| format_err!("failed to copy file contents: {}", err))?;
+
         if size != extracted {
             bail!("extracted {} bytes of a file of {} bytes", extracted, size);
         }
-- 
2.20.1

Re: [pbs-devel] [PATCH proxmox 1/2] add tools/zero: add fast zero comparison code

[Thomas Lamprecht]

On 11.12.20 13:08, Dominik Csapak wrote:
> that can make use of see/avx instructions where available
> 

maybe some performance numbers can help to argue why we should add
that, maybe directly as small benchmark binary so different CPUs
could be compared?

> this is mostly a direct translation of qemu's util/bufferiszero.c
> 
> this is originally from Wolfgang Bumiller

FYI, you could use the

Originally-by: Wolfgang Bumiller <w.bumiller@proxmox.com>

git trailer for that, I saw it a few times used in other projects (e.g.,
kernel)

Re: [pbs-devel] [PATCH proxmox 1/2] add tools/zero: add fast zero comparison code

[Wolfgang Bumiller]

Some testing & internal talk led to the decision to exclude this patch.

apart from being incomplete (some alignment issues aren't handled),
rustc itself is very capable of producing fast SSE code for this, if you
know *how*:

Assuming an `fn is_zero(buf: &[u8]) -> bool`:

a) `buf.contains(&0)`

    compiles to a naive loop, slow

b) `buf.iter().fold(0, |a, b| a | b) == 0`

    produces fast SSE code loading 128 bytes at a time (sort of) into
    xmm registers, (pretty much the code from this commit, but better),

    however, this doesn't stop at the first non-zero

c) ```
   buf
       .chunks(128)
       .map(|aa| aa.iter().fold(0, |a, b| a|b) != 0)
       .any(|a| a)
   ```

    A compromise suggested by Fabian G.
    Much like case (b), the inner loop loads 128 bytes directly via sse
    instructions, but we also have the outer chunks to stop early

On Mon, Dec 14, 2020 at 09:38:49AM +0100, Thomas Lamprecht wrote:
> On 11.12.20 13:08, Dominik Csapak wrote:
> > that can make use of see/avx instructions where available
> > 
> 
> maybe some performance numbers can help to argue why we should add
> that, maybe directly as small benchmark binary so different CPUs
> could be compared?
> 
> > this is mostly a direct translation of qemu's util/bufferiszero.c
> > 
> > this is originally from Wolfgang Bumiller
> 
> FYI, you could use the
> 
> Originally-by: Wolfgang Bumiller <w.bumiller@proxmox.com>
> 
> git trailer for that, I saw it a few times used in other projects (e.g.,
> kernel)