Tag Archives: java

Cladograms of virtual machines

Cladograms are diagrams showing the relationships between species and their ancestors. For virtual machines which get cloned and copied, you can also construct simple cladograms, and then use these to construct a tree of backing files to minimize the space used.

The Java program attached was written as a proof-of-concept for an oVirt feature which would automatically infer cladograms (and hence efficient backing files) from a set of virtual machines.

I ran it on a test set consisting of:

  1. An original Windows XP disk image.
  2. The same WinXP disk image as 1, copied and booted once.
  3. The same WinXP disk image as 1, copied, booted and Firefox installed.
  4. A 32 bit Fedora 19 disk image.
  5. A 64 bit Fedora 19 disk image.
  6. An ArchLinux disk image.

The program inferred the following cladogram:

--------------------------- winxp-original
    |    |         |    |
    |    |         |    `---- winxp-copy-1
    |    |         |
    |    |         `----- winxp-copy-2
    |    |
    |    |  ,------ f19rawhidex32
    |     --|
    |       `------ f19rawhidex64
    |
    `-------------- archlinux

The “distance” measured between the Fedora and ArchLinux guests was so large that those are essentially random. But it did very well with the Windows XP guests which were truly derivatives. In fact you could easily modify the program to ignore guests which are unrelated (eg. have a distance measure over, say, 90%).

From the diagram you should be able to see how to build an efficient tree of backing files to minimize disk space requirements.

/* Compare multiple disk images for similarity.
 * By Richard W.M. Jones <rjones@redhat.com>
 * See: https://bugzilla.redhat.com/show_bug.cgi?id=827130#c2
 *
 * Usage:
 *
 *   java Similarity disk.img disk.img [disk.img ...]
 *
 * You need to supply two disk images at a minimum, and usually it's
 * best to supply a lot more.  Any format can be used.
 *
 * Notes on the technique used:
 *
 * (1) We use libguestfs to open each disk image.  This allows us to
 * get at the raw data, in case the disk image is stored in some
 * format like qcow2 or vmdk.  Also you could extend this program so
 * it could understand encrypted disks.
 * http://libguestfs.org/
 * http://libguestfs.org/guestfs-java.3.html
 *
 * (2) For each disk, we split it into 64K blocks and hash each block
 * using SHA-256.  The reason for choosing 64K blocks is that it's the
 * normal cluster size for qcow2, and the block size used by qemu-img
 * etc.  The reason for doing the hashing is so that we can compare
 * the disk images for similarity by holding the complete set of
 * hashes in memory.  The hashing reduces each disk by a factor of
 * 2048, so for example a 10 GB disk image is reduced to a more
 * manageable 5 MB.
 *
 * NB: For speed the hashes are saved in a cache file called
 * 'similarity-cache' in the local directory.  You can just delete
 * this file when done.
 *
 * (3) We then compare each disk image, block by block, and record the
 * difference between each pair of images.
 *
 * Note that we DON'T do advanced Cluster Analysis on the disk images.
 * There's not any point since the rebasing operation used by qemu-img
 * can only handle simple differences at the block level; it cannot,
 * for example, move blocks around or do fuzzy matches.
 * http://en.wikipedia.org/wiki/Cluster_analysis
 *
 * (4) We then output a tree (technically a 'Cladogram') showing a
 * hierarchy of guests, using a simple hierarchical clustering
 * algorithm, where we group the two closest guests, then that group
 * with the next closest guest, and so forth.
 * http://en.wikipedia.org/wiki/Cladogram
 * http://en.wikipedia.org/wiki/Hierarchical_clustering
 */

import java.util.*;
import java.io.*;
import java.security.*;
import com.redhat.et.libguestfs.*;

public class Similarity
{
    static String cache_filename = "similarity-cache";

    static int blocksize = 65536;
    static String hash_algorithm = "SHA-256";
    static int hash_bytes_per_block = 256/8;

    static String[] filenames;

    public static Map<String, ByteArray> read_cache_file ()
        throws Exception
    {
        FileInputStream file = null;

        try {
            file = new FileInputStream (cache_filename);
        }
        catch (Exception e) { }
        if (file == null)
            return new HashMap<String, ByteArray> ();

        ObjectInputStream ois = new ObjectInputStream (file);
        return (HashMap<String, ByteArray>) ois.readObject ();
    }

    public static void write_cache_file (Map<String, ByteArray> cache)
        throws Exception
    {
        FileOutputStream file = new FileOutputStream (cache_filename);
        ObjectOutputStream oos = new ObjectOutputStream (file);
        oos.writeObject (cache);
        oos.close ();
    }

    /* Read the disk image and return all the block hashes
     * concatenated together.
     */
    public static byte[] read_disk_image (String filename)
        throws Exception
    {
        GuestFS g = new GuestFS ();
        g.add_drive_ro (filename);
        g.launch ();

        String dev = "/dev/sda";
        long size = g.blockdev_getsize64 (dev);
        ByteArrayOutputStream os = new ByteArrayOutputStream ();
        long percent, last_percent = -1;

        for (long offset = 0; offset < size-blocksize+1; offset += blocksize) {
            percent = 100 * offset / size;
            if (percent != last_percent) {
                last_percent = percent;
                System.out.print (percent + "%\r");
                System.out.flush ();
            }

            String block = g.pread_device (dev, blocksize, offset);
            MessageDigest md = MessageDigest.getInstance (hash_algorithm);
            os.write (md.digest (block.getBytes ("UTF-8")));
        }

        g.close ();

        return os.toByteArray ();
    }

    // Return number of blocks which are different.
    public static long calculate_distance (byte[] bi, byte[] bj)
    {
        long d = 0;
        ByteArrayInputStream bis = new ByteArrayInputStream (bi);
        ByteArrayInputStream bjs = new ByteArrayInputStream (bj);

        while (bis.available () > 0 || bjs.available () > 0) {
            byte[] bis_block = new byte[hash_bytes_per_block];
            if (bis.available () >= hash_bytes_per_block)
                bis.read (bis_block, 0, hash_bytes_per_block);
            byte[] bjs_block = new byte[hash_bytes_per_block];
            if (bjs.available () >= hash_bytes_per_block)
                bjs.read (bjs_block, 0, hash_bytes_per_block);

            if (! Arrays.equals (bis_block, bjs_block))
                d++;
        }

        return d;
    }

    /* The matrix of distance between disk image i and disk image j. */
    static long[][] matrix;

    public static long min_distance_between_sets (Set<Integer> set1,
                                                  Set<Integer> set2)
    {
        long min_distance = -1;

        Iterator<Integer> i = set1.iterator ();
        while (i.hasNext ()) {
            Integer ii = i.next ();
            Iterator<Integer> j = set2.iterator ();
            while (j.hasNext ()) {
                Integer ji = j.next ();
                long distance = matrix[ii][ji];
                if (min_distance == -1 || distance < min_distance)
                    min_distance = distance;
            }
        }

        return min_distance;
    }

    // Return true if any member of 's' is in 'set'.
    public static boolean is_member_of_set (Set s, Set set)
    {
        Iterator i = s.iterator ();
        while (i.hasNext ()) {
            Object member = i.next ();
            if (set.contains (member))
                return true;
        }
        return false;
    }

    public static Set[] make_cladogram (int level, Set[] sets)
    {
        // Find the minimum distance between any sets.
        long min_distance = min_distance_between_sets (sets[0], sets[1]);

        for (int i = 0; i < sets.length; ++i) {
            for (int j = i+1; j < sets.length; ++j) {
                long distance = min_distance_between_sets (sets[i], sets[j]);
                if (distance < min_distance)
                    min_distance = distance;
            }
        }

        //System.out.println ("min_distance = " + min_distance);

        // For each set that differs from another by exactly the
        // minimum distance, group them together into a single set.
        Set grouped = new HashSet<Integer> ();

        for (int i = 0; i < sets.length; ++i) {
            for (int j = i+1; j < sets.length; ++j) {
                long distance = min_distance_between_sets (sets[i], sets[j]);
                if (distance == min_distance) {
                    grouped.addAll (sets[i]);
                    grouped.addAll (sets[j]);
                }
            }
        }

        List<Set> ret = new ArrayList<Set> ();
        ret.add (grouped);

        // Add the other sets which are not included in 'grouped'.
        for (int i = 0; i < sets.length; ++i) {
            if (! is_member_of_set (sets[i], grouped))
                ret.add (sets[i]);
        }

        System.out.println ("cladogram level " + level + ":");
        Iterator<Set> i = ret.iterator ();
        while (i.hasNext ()) {
            Set<Integer> s = i.next ();
            System.out.print ("[ ");
            Iterator<Integer> j = s.iterator ();
            while (j.hasNext ()) {
                int ii = j.next().intValue();
                String filename = filenames[ii];
                System.out.print (filename + " ");
            }
            System.out.print ("] ");
        }
        System.out.print ("\n");

        return ret.toArray (new HashSet[ret.size()]);
    }

    public static void main (String[] argv)
        throws Exception
    {
        filenames = argv;
        int n = filenames.length;

        if (n < 2)
            throw new Error ("usage: Similarity disk.img disk.img [disk.img ...]");

        // Read the cache file.
        Map<String, ByteArray> cache = read_cache_file ();

        // Read in the disk images and hash them.
        for (int i = 0; i < n; ++i) {
            if (cache.containsKey (filenames[i])) {
                System.out.println ("disk image " + filenames[i] +
                                    " is already in the cache");
            } else {
                System.out.println ("reading disk image: " + filenames[i]);
                byte[] bytes = read_disk_image (filenames[i]);
                ByteArray ba = new ByteArray (bytes);
                cache.put (filenames[i], ba);
            }

            byte[] b = cache.get(filenames[i]).getArray();
            System.out.println (filenames[i] +
                                ": bytes.length = " + b.length +
                                ", blocks = " + b.length / hash_bytes_per_block);
        }

        // Write the cache file.
        write_cache_file (cache);

        // Work out the similarity for each pair of guests.
        // Conveniently we can store this in a matrix where each (i,j)
        // element is the "distance" from filenames[i] to
        // filenames[j].  Distance means the number of blocks which
        // are different.
        matrix = new long[n][n];
        for (int i = 0; i < n; ++i) {
            matrix[i][i] = 0;
            for (int j = 0; j < i; ++j) {
                byte[] bi = cache.get(filenames[i]).getArray();
                byte[] bj = cache.get(filenames[j]).getArray();
                long d = calculate_distance (bi, bj);
                System.out.println ("distance from " +
                                    filenames[i] + " to " +
                                    filenames[j] + " = " + d);
                matrix[i][j] = d;
                matrix[j][i] = d;
            }
        }

        // Construct the cladogram.  The bottom level of this is an
        // array of Sets, with each Set containing just a single
        // guest.  Then we group the Sets together into larger and
        // larger Sets until we have one Set covering everything.
        Set h[] = new Set[n];
        for (int i = 0; i < n; ++i) {
            h[i] = new HashSet<Integer> ();
            h[i].add (new Integer (i));
        }

        int level = 0;
        while (h.length > 1) {
            h = make_cladogram (level, h);
            level++;
        }

        System.out.println ("finished!");
    }
}
/*

   Derby - Class org.apache.derby.iapi.util.ByteArray

   Licensed to the Apache Software Foundation (ASF) under one or more
   contributor license agreements.  See the NOTICE file distributed with
   this work for additional information regarding copyright ownership.
   The ASF licenses this file to you under the Apache License, Version 2.0
   (the "License"); you may not use this file except in compliance with
   the License.  You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.

 */


import java.io.ObjectOutput;
import java.io.ObjectInput;
import java.io.IOException;
import java.io.Serializable;

/**
  ByteArray wraps java byte arrays (byte[]) to allow
  byte arrays to be used as keys in hashtables.

  This is required because the equals function on
  byte[] directly uses reference equality.
  
  This class also allows the trio of array, offset and length
  to be carried around as a single object.
*/
public final class ByteArray implements Serializable
{
    static final long serialVersionUID = 7541513629082952232L;

  private byte[] array;
  private int    offset;
  private int    length;

  /**
    Create an instance of this class that wraps ths given array.
    This class does not make a copy of the array, it just saves
    the reference.
  */
  public ByteArray(byte[] array, int offset, int length) {
    this.array = array;
    this.offset = offset;
    this.length = length;
  }

  public ByteArray(byte[] array) {
    this(array, 0, array.length);
  }

  public ByteArray()
  {
  }

  public void setBytes(byte[] array)
  {
    this.array = array;
    offset = 0;
    length = array.length;
  } 

  public void setBytes(byte[] array, int length)
  {
    this.array = array;
    this.offset = 0;
    this.length = length;
  } 

  public void setBytes(byte[] array, int offset, int length)
  {
    this.array = array;
    this.offset = offset;
    this.length = length;
  } 


  /**
    Value equality for byte arrays.
  */
  public boolean equals(Object other) {
    if (other instanceof ByteArray) {
      ByteArray ob = (ByteArray) other;
      return ByteArray.equals(array, offset, length, ob.array, ob.offset, ob.length);
    }
    return false;
  }



  /**
  */
  public int hashCode() {

    byte[] larray = array;

    int hash = length;
    for (int i = 0; i < length; i++) {
      hash += larray[i + offset];
    }
    return hash;
  }

  public final byte[] getArray() {
    return array;
  }
  public final int getOffset() {
    return offset;
  }

  public final int getLength() {
    return length;
  }
  public final void setLength(int newLength) {
    length = newLength;
  }
  
  /**
   * Read this object from a stream of stored objects.
   *
   * @param in read this.
   *
   * @exception IOException         thrown on error
   */
  public void readExternal( ObjectInput in ) throws IOException
  {
    int len = length = in.readInt();
    offset = 0; 
    array = new byte[len];

    in.readFully(array, 0, len);
  }

  /**
   * Write the byte array out w/o compression
   *
   * @param out write bytes here.
   *
   * @exception IOException   thrown on error
   */
  public void writeExternal(ObjectOutput out) throws IOException
  {
    out.writeInt(length);
    out.write(array, offset, length);
  }

  /**
    Compare two byte arrays using value equality.
    Two byte arrays are equal if their length is
    identical and their contents are identical.
  */
  private static boolean equals(byte[] a, int aOffset, int aLength, byte[] b, int bOffset, int bLength) {

    if (aLength != bLength)
      return false;

    for (int i = 0; i < aLength; i++) {
      if (a[i + aOffset] != b[i + bOffset])
        return false;
    }
    return true;
  }
}
Advertisements

10 Comments

Filed under Uncategorized

New in libguestfs 1.21.3: Java events

In libguestfs 1.21.3 you can now use the libguestfs event API from Java (or JRuby). For example to display progress bars, capture log messages, or do full libvirt authentication.

This effectively completes the Java bindings for libguestfs — as far as I’m aware you can now do anything from Java that you could do from C.

3 Comments

Filed under Uncategorized

Which foreign function interface is the best?

I’ve written libguestfs language bindings for Perl, Python, Ruby, Java, OCaml, PHP, Haskell, Erlang and C#. But which of these is the best? Which is the easiest? What makes this hard? Grubbing around in the internals of a language reveals mistakes made by the language designers, but what are the worst mistakes?

Note: There is source that goes with this. Download libguestfs-1.13.13.tar.gz and look in the respective directories.

The best

It’s going to be a controversial choice, but in my opinion: C#. You just add some simple annotations to your functions and structs, and you can call into shared libraries (or “DllImport”s as Microsoft insisted on calling them) directly. It’s just about as easy as directly calling C and that is no simple achievement considering how the underlying runtime of C# is very different from C.

Example: a C struct:

[StructLayout (LayoutKind.Sequential)]
public class _int_bool {
  int i;
  int b;
}

The worst

There are two languages in the doghouse: Haskell and PHP. PHP first because their method of binding is just very broken. For example, 64 bit types aren’t possible on a 32 bit platform. It requires a very complex autoconf setup. And the quality of their implementation is very poor verging on broken — it makes me wonder if the rest of PHP can be this bad.

Haskell: even though I’m an experienced functional programmer and have done a fair bit of Haskell programming in the past, the FFI is deeply strange and very poorly documented. I simply could not work out how to return anything other than integers from my functions. You end up with bindings that look like this:

write_file h path content size = do
  r <- withCString path $ \path -> withCString content $ \content -> withForeignPtr h (\p -> c_write_file p path content (fromIntegral size))
  if (r == -1)
    then do
      err <- last_error h
      fail err
    else return ()

The middle tier

There’s not a lot to choose between OCaml, Ruby, Java and Erlang. For all of them: you write bindings in C, there’s good documentation, it’s a bit tedious but basically mechanical, and in 3 out of 4 you’re dealing with a reasonable garbage collector so you have to be aware of GC issues.

Erlang is slightly peculiar because the method I chose (out of many possible) is to write an external process that talks to the Erlang over stdin/stdout. But I can’t fault their documentation, and the rest of it is sensible.

Example: Here is a function binding in OCaml, but with mechanical changes this could be Ruby, Java or Erlang too:

CAMLprim value
ocaml_guestfs_add_drive_ro (value gv, value filenamev)
{
  CAMLparam2 (gv, filenamev);
  CAMLlocal1 (rv);

  guestfs_h *g = Guestfs_val (gv);
  if (g == NULL)
    ocaml_guestfs_raise_closed ("add_drive_ro");

  char *filename = guestfs_safe_strdup (g, String_val (filenamev));
  int r;

  caml_enter_blocking_section ();
  r = guestfs_add_drive_ro (g, filename);
  caml_leave_blocking_section ();
  free (filename);
  if (r == -1)
    ocaml_guestfs_raise_error (g, "add_drive_ro");

  rv = Val_unit;
  CAMLreturn (rv);
}

The ugly

Perl: Get reading. You’d better start with perlxs because Perl uses its own language — C with bizarre macros on top so your code looks like this:

SV *
is_config (g)
      guestfs_h *g;
PREINIT:
      int r;
   CODE:
      r = guestfs_is_config (g);
      if (r == -1)
        croak ("%s", guestfs_last_error (g));
      RETVAL = newSViv (r);
 OUTPUT:
      RETVAL

After that, get familiar with perlguts. Perl has only 3 structures and you’ll be using them a lot. There are some brilliant things about Perl which shouldn’t be overlooked, including POD which libguestfs uses to make effortless manual pages.

Python: Best described as half arsed. Rather like the language itself.

Python, Ruby, Erlang: If your language depends on “int”, “long”, “long long” without defining what those mean, and differing based on your C compiler and platform, then you’ve made a big mistake that will unfortunately dog you throughout the runtime, FFIs and the language itself. It’s better either to define them precisely (like Java) or to just use int32 and int64 (like OCaml).

And finally, reference counting (Perl, Python). It’s tremendously easy to make mistakes that are fiendishly difficult to track down. It’s a poor way to do GC and it indicates to me that the language designer didn’t know any better.

18 Comments

Filed under Uncategorized

New libguestfs 1.12: Full Java bindings

In this series of posts I’ll be looking at what’s new in the forthcoming release of libguestfs 1.12.

In previous versions of libguestfs, the Java bindings were incomplete. In 1.12 they now cover all API calls, and we are also providing Java examples which match the other language examples.

As explained here yesterday you can also use these bindings from JRuby.

Leave a comment

Filed under Uncategorized

libguestfs stable 1.8.2, now with better Java bindings

The libguestfs Java bindings were broken for quite a long time. However in the new stable version of libguestfs (1.8.2 — source, Fedora 14 testing package) we have fixed the Java bindings to be almost complete.

The only remaining part which doesn’t work are a handful of functions that have optional arguments — none of these should be necessary for the majority of libguestfs use cases.

Leave a comment

Filed under Uncategorized

libguestfs: Java bindings

New in version 1.0.5 of libguestfs, Java bindings:

public class LVCreate {                                               
    public static void main (String[] argv)                                     
    {                                                                           
        try {                                                                   
            GuestFS g = new GuestFS ();
                                                                                
            RandomAccessFile f = new RandomAccessFile ("test.img", "rw");       
            f.setLength (500 * 1024 * 1024);                                    
            f.close ();                                                         
                                                                                
            g.add_drive ("test.img");
            g.launch ();
            g.wait_ready ();
                                                                                
            g.pvcreate ("/dev/sda");
            g.vgcreate ("VG", new String[] {"/dev/sda"});
            g.lvcreate ("LV1", "VG", 200);
            g.lvcreate ("LV2", "VG", 200);
                                                                                
            String[] lvs = g.lvs ();
            assert lvs[0].equals ("/dev/VG/LV1");                               
            assert lvs[1].equals ("/dev/VG/LV2");                               
                                                                                
            g.sync ();
            g.close ();
        }                                                                       
        catch (Exception exn) {                                                 
            System.err.println (exn);                                           
            System.exit (1);                                                    
        }                                                                       
    }                                                                           
}                                                                               

Leave a comment

Filed under Uncategorized