From 264faa6f381b1972327f830e3fca5ddd5881ff92 Mon Sep 17 00:00:00 2001 From: "Richard W.M. Jones" Date: Thu, 1 Jan 1970 00:00:00 +0000 Subject: [PATCH] Added bitmap structure. Run ownership tests for sample block device. --- diskzip/.depend | 9 +++- diskzip/diskzip.ml | 26 ++++++++++- diskzip/diskzip_bitmap.ml | 108 +++++++++++++++++++++++++++++++++++++++++++++ diskzip/diskzip_bitmap.mli | 54 +++++++++++++++++++++++ lib/diskimage.ml | 6 +-- lib/diskimage.mli | 2 +- 6 files changed, 198 insertions(+), 7 deletions(-) create mode 100644 diskzip/diskzip_bitmap.ml create mode 100644 diskzip/diskzip_bitmap.mli diff --git a/diskzip/.depend b/diskzip/.depend index b225123..ca02968 100644 --- a/diskzip/.depend +++ b/diskzip/.depend @@ -1,2 +1,7 @@ -diskzip.cmo: diskzip_gettext.cmo ../lib/diskimage.cmi -diskzip.cmx: diskzip_gettext.cmx ../lib/diskimage.cmx +diskzip_bitmap.cmi: ../lib/int63.cmi +diskzip_bitmap.cmo: ../lib/int63.cmi diskzip_bitmap.cmi +diskzip_bitmap.cmx: ../lib/int63.cmx diskzip_bitmap.cmi +diskzip.cmo: ../lib/int63.cmi diskzip_gettext.cmo diskzip_bitmap.cmi \ + ../lib/diskimage.cmi +diskzip.cmx: ../lib/int63.cmx diskzip_gettext.cmx diskzip_bitmap.cmx \ + ../lib/diskimage.cmx diff --git a/diskzip/diskzip.ml b/diskzip/diskzip.ml index 3de7f63..7e2969a 100644 --- a/diskzip/diskzip.ml +++ b/diskzip/diskzip.ml @@ -20,7 +20,9 @@ open Unix open Printf +open Int63.Operators open Diskzip_gettext.Gettext +module Bitmap = Diskzip_bitmap type output = File of string | Dir of string type extcompress = BZip2 | GZip | External of string @@ -151,7 +153,29 @@ and go_compress extcompress images = let ownership = Diskimage.create_ownership machine in (* Create ownership bitmap for each disk. *) - + List.iter ( + fun { Diskimage.d_name = name; d_dev = disk } -> + let blocksize = disk#blocksize in + let size = disk#size in (* Size in bytes. *) + let nr_blocks = size /^ blocksize in (* Number of disk sectors. *) + + if !Diskimage.debug then + eprintf "Creating bitmap for %s (%s sectors) ...\n%!" + disk#name (Int63.to_string nr_blocks); + + (* Create an empty bitmap, one bit per sector. *) + let bitmap = Bitmap.create nr_blocks in + + (* Get the lookup function for this disk. *) + let lookup = Diskimage.get_owners_lookup machine ownership disk in + + (* Lookup each sector. *) + Bitmap.iter_set ( + fun blk _ -> + let owners = lookup blk in + false + ) bitmap + ) machine.Diskimage.m_disks; (* Redirect output through external pipe if asked. *) (match extcompress with diff --git a/diskzip/diskzip_bitmap.ml b/diskzip/diskzip_bitmap.ml new file mode 100644 index 0000000..982c46f --- /dev/null +++ b/diskzip/diskzip_bitmap.ml @@ -0,0 +1,108 @@ +(* 'diskzip' command for intelligently compressing disk images. + (C) Copyright 2007 Richard W.M. Jones, Red Hat Inc. + http://libvirt.org/ + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + *) + +open Int63.Operators + +type t = int63 * string array + +(* NB: Sys.max_string_length is by no means a 'round' number. *) +let maxlen = Int63.of_int Sys.max_string_length + +let create size = + (* Get the size in bytes & round up. *) + let sizebytes = (size +^ ~^7) >^> 3 in + + let n = Int63.to_int (sizebytes /^ maxlen) in + let overflow = Int63.to_int (sizebytes %^ maxlen) in + let zerochar = Char.chr 0 in + let array = + if overflow <> 0 then + Array.init (n+1) + (function + | i when i = n -> String.make overflow zerochar + | _ -> String.make Sys.max_string_length zerochar) + else + Array.init n (fun _ -> String.make Sys.max_string_length zerochar) in + size, array + +let mask7 = ~^7 + +let set (size, t) offset = + if offset < Int63.zero || offset >= size then invalid_arg "bitmap"; + let offset_bytes, offset_bits = + offset >^> 3, + Int63.to_int (offset &^ mask7) in + let offset_strs, offset_in_str = + Int63.to_int (offset_bytes /^ maxlen), + Int63.to_int (offset_bytes %^ maxlen) in + let c = Char.code t.(offset_strs).[offset_in_str] in + t.(offset_strs).[offset_in_str] <- Char.chr (c lor (1 lsl offset_bits)) + +let clear (size, t) offset = + if offset < Int63.zero || offset >= size then invalid_arg "bitmap"; + let offset_bytes, offset_bits = + offset >^> 3, + Int63.to_int (offset &^ mask7) in + let offset_strs, offset_in_str = + Int63.to_int (offset_bytes /^ maxlen), + Int63.to_int (offset_bytes %^ maxlen) in + let c = Char.code t.(offset_strs).[offset_in_str] in + t.(offset_strs).[offset_in_str] <- + Char.chr (c land (lnot (1 lsl offset_bits))) + +let get (size, t) offset = + if offset < Int63.zero || offset >= size then invalid_arg "bitmap"; + let offset_bytes, offset_bits = + offset >^> 3, + Int63.to_int (offset &^ mask7) in + let offset_strs, offset_in_str = + Int63.to_int (offset_bytes /^ maxlen), + Int63.to_int (offset_bytes %^ maxlen) in + let c = Char.code t.(offset_strs).[offset_in_str] in + c land (1 lsl offset_bits) <> 0 + +let set_bool t offset v = + (if v then set else clear) t offset + +let set_int t offset v = + (if v <> 0 then set else clear) t offset + +let iter_set f (size, t) = + let n = ref Int63.zero in + Array.iter ( + fun str -> + let m = ref 0x80 in + for i = 0 to String.length str - 1 do + let c = Char.code str.[i] in + for j = 0 to 7 do + let n' = !n in + if n' < size then ( + let b = c land !m <> 0 in + let b = f n' b in + str.[i] <- Char.chr (if b then c lor !m else c land lnot !m) + ); + n := Int63.succ n'; + m := !m lsr 1 + done + done + ) t + +let iter f t = + let f i b = f i b; b in + iter_set f t diff --git a/diskzip/diskzip_bitmap.mli b/diskzip/diskzip_bitmap.mli new file mode 100644 index 0000000..85821fd --- /dev/null +++ b/diskzip/diskzip_bitmap.mli @@ -0,0 +1,54 @@ +(* 'diskzip' command for intelligently compressing disk images. + (C) Copyright 2007 Richard W.M. Jones, Red Hat Inc. + http://libvirt.org/ + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +*) + +(** + Unlimited-length fixed-size bitmap type. + + The only reason we need this is because strings are limited to 16 + MBytes on 32 bit platforms (which would limit the size of a disk + image we could process to around 64 GB, assuming 512 byte sectors). + This module hides multiple strings on 32 bit, or a single long + string on 64 bit but is very efficient in either case. + + Also it uses the 'int63' type which makes arithmetic convenient. +*) + +type t + +val create : Int63.t -> t + (** Create a bitmap of the given length in bits. *) + +val set : t -> Int63.t -> unit + +val clear : t -> Int63.t -> unit + +val set_bool : t -> Int63.t -> bool -> unit + +val set_int : t -> Int63.t -> int -> unit + (** Treats the integer as a C-like boolean. *) + +val get : t -> Int63.t -> bool + +val iter : (Int63.t -> bool -> unit) -> t -> unit + (** [iter f bitmap] iterates over the bitmap, calling [f] for each bit. *) + +val iter_set : (Int63.t -> bool -> bool) -> t -> unit + (** [iter_set f bitmap] iterates over the bitmap, calling [f] for each + bit. The return value of [f] is used to set or clear the bit + in the bitmap. *) diff --git a/lib/diskimage.ml b/lib/diskimage.ml index 697cb76..42e02dc 100644 --- a/lib/diskimage.ml +++ b/lib/diskimage.ml @@ -301,7 +301,7 @@ let print_binary_tree leaf_printer node_printer tree = eprintf "/* Use 'dot -Tpng foo.dot > foo.png' to convert to a png file. */\n"; eprintf "digraph G {\n"; print tree; - eprintf "}\n"; + eprintf "}\n%!"; type owner = [ `Filesystem of filesystem @@ -661,9 +661,9 @@ let create_ownership machine = (* Return the ownership structure. *) ownership -let get_owners_lookup machine ownership disk = +let get_owners_lookup machine ownership (disk : block_device) = (* Get the correct tree. *) - let tree = List.assoc disk ownership in + let tree = List.assoc (disk :> device) ownership in fun offset -> let rec query = function diff --git a/lib/diskimage.mli b/lib/diskimage.mli index 8cdd7a9..5d2a420 100644 --- a/lib/diskimage.mli +++ b/lib/diskimage.mli @@ -308,7 +308,7 @@ type owner = | `Partitions of partitions | `PhysicalVolume of pv ] -val get_owners_lookup : machine -> ownership -> device -> +val get_owners_lookup : machine -> ownership -> block_device -> (Int63.t -> (owner * Int63.t) list) (** [get_owners_lookup machine disk] returns a specialized function for looking up owners (filesystems, etc.) -- 1.8.3.1