Add dirty map tracking support

[andreeaflorescu]

Tracking dirty bitmap is needed for features such as snapshot, live migration, or live update.

[andreeaflorescu]

In progress: #125

[bonzini]

I'll sketch my proposed design across a few comments. First, the bitmap implementation itself. It supports any number of producers (via interior mutability) but only a finite number of consumers, so the traits are split between producer and consumer:

// A trait to write to a slice containing bit data
trait BitmapProducer {
  fn set(&self, from: usize, count: usize);
  fn or(&self, from: usize, count: usize, data: &[u64]);
}

// A trait to read a slice containing bit data from an external source
// Keeping it simple for now (KVM has the possibility of doing separate
// get and clear, but that would complicate a bit the GuestAddressSpace parts).
trait BitmapConsumer {
  fn get_and_clear(&mut self, from: usize, data: &mut [u64]);
}

Typically there will be just one consumer (live migration) but there can be more, for example to track dirty pages in the frame buffer. For simplicity, consumers are tracked by index. Giving a meaning to the index is left to the VMM.

// A bitmap that can be set by any number of producers, but only read
// by a fixed number of consumers.  The AtomicBitmap maintains one separate
// bitmap for each consumer.  set() writes to each bitmap, while reading
// goes through an AtomicBitmapConsumer and only accesses one bitmap.
struct AtomicBitmap {
  bitmaps: Vec<Vec<AtomicU64>>,
  // See atomic_refcell crate
  consumers: Vec<AtomicRefCell<AtomicBitmapConsumer>>,
}

struct AtomicBitmapConsumer {
  bitmap: &Vec<AtomicU64>,
}

impl AtomicBitmap {
  pub fn new(size: usize, num_consumers: usize);
  pub fn borrow_consumer_mut(&self, index: usize) -> &mut AtomicBitmapConsumer {
    return consumers[index].borrow_mut();
  }
}

impl BitmapProducer for AtomicBitmap {
  // These two do a fetch_or into the bitmaps with Ordering::Release
  fn set(&self, from: usize, count: usize) { ... }
  fn or(&self, from: usize, count: usize, data: &[u64]) { ... }
}
impl BitmapConsumer for AtomicBitmapConsumer {
  // This does a fetch_and or xchg into the bitmaps, with Ordering::Acquire
  fn get_and_clear(&mut self, from: usize, data: &mut [u64]) { ... }
}

[bonzini]

Now the region. It wraps another region and adds an AtomicBitmap.

struct DirtyTrackedRegion<R: GuestRegion> {
  inner: R,
  dirty_bitmap: AtomicBitmap,
}

impl<R: GuestRegion> DirtyTrackedRegion<R> {
  pub fn new(inner: GuestRegion, num_consumers: usize) {
    return DirtyTrackedRegion {
      inner,
      dirty_bitmap: AtomicBitmap::new(inner.len(), num_consumers);
    }
  }

  pub fn borrow_consumer_mut(&self, index: usize) -> &mut AtomicBitmapConsumer {
    return self.dirty_bitmap.borrow_consumer_mut(index);
  }
}

Implementing BitmapProducer (especially the or method) lets the corresponding GuestAddressSpace interface with KVM:

impl<R: GuestRegion> BitmapProducer for DirtyTrackedRegion<R> {
  fn set(&self, from: usize, count: usize) {
    return self.dirty_bitmap.set(from, count);
  }

  fn or(&self, from: usize, count: usize, data: &[u64]) {
    return self.dirty_bitmap.or(from, count);
  }
}

It should also track each write properly in its Bytes<MemoryRegionAddress> implementation, using BitmapProducer::set.

[bonzini]

Finally here's the GuestAddressSpace. It supports an arbitrary number of BitmapSources (for example KVM and VFIO).

struct DirtyTrackedMemory<R: GuestRegion,
                          Mem: GuestMemory<R = DirtyTrackedRegion<R>>,
                          AS: GuestAddressSpace<M = Mem>> {
  inner: AS,
  sources: Mutex<Vec<Box<dyn BitmapConsumer>>>
}

impl DirtyTrackedMemory<...> GuestAddressSpace for DirtyTrackedMemory<R, Mem, AS> {
  type T = AS::T;
  type M = AS::M;
  fn memory(&self) -> AS::T { return self.inner.memory(); }
}

impl<...> DirtyTrackedMemory<R, Mem, AS> {
  pub fn new(inner: AS, num_sources: usize) {
    return DirtyTrackedRegion {
      inner,
      sources: Mutex::new(Vec::new())
    }
  }

  pub fn get_page_size() {
    // could use page_size crate too
    use libc::{_SC_PAGESIZE, sysconf};
    unsafe { sysconf(_SC_PAGESIZE) as usize }
  }

  pub fn add_source(&self, p: Box<dyn BitmapConsumer>) { ... }
  pub fn remove_source(&self, p: Box<dyn BitmapConsumer>) { ... }

  fn sync_dirty(&self, from: usize, count: usize) {
    // let page_size = self.get_page_size()
    // for each region r
    //   if the region overlaps [from, from+count)
    //     let startbit = ...;
    //     let regionbit = ...;
    //     let nregionbits = ...
    //     let size = (count + 63) / 64;
    //     let vec: Vec<AtomicU64> = Vec::with_capacity(size);
    //     vec.resize_with(size, Default::default);
    //     for each source s
    //       s.get_and_clear(startbit, vec.as_slice())
    //       r.or(regionbit, vec.as_slice())
  }

  pub fn get_and_clear_dirty(&self, index: usize, from: usize, count: usize, data: &mut [u64]) {
    self.sync_dirty(from, count);
    // opposite of sync_dirty: walk all regions, if they overlap
    // borrow the index-th consumer and get_and_clear() into data
  }

  // Later, if we split get_and_clear() into get() and clear(), we could return a RAII guard. The
  // guard would hold the borrowed reference to the AtomicBitmapConsumer, and have
  // a forwading clear() method
}

[alexandruag]

Hi Paolo, thanks for sharing this! Did not have the chance to take an in-depth look yet, but I was wondering if you think #125 is missing something in terms of initial steps in the dirty bitmap tracking direction. I left a comment there to answer your question about tracking at the region level.