lib/diskimage_impl.ml

   1 (* Diskimage library for reading disk images.
   2    (C) Copyright 2007-2008 Richard W.M. Jones, Red Hat Inc.
   3    http://libvirt.org/
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  *)
  19
  20 open ExtList
  21 open Printf
  22 open Unix
  23
  24 open Int63.Operators
  25
  26 let debug = ref false
  27
  28 (* Use as the natural block size for disk images, but really we should
  29  * use the 'blockdev -getbsz' command to find the real block size.
  30  *)
  31 let disk_block_size = ~^512
  32
  33 class virtual device =
  34 object (self)
  35   method virtual size : int63
  36   method virtual name : string
  37   method virtual blocksize : int63
  38   method virtual map_block : int63 -> (device * int63) list
  39   method virtual contiguous : Int63.t -> Int63.t
  40
  41   (* Block-based read.  Inefficient so normally overridden in subclasses. *)
  42   method read offset len =
  43     if offset < ~^0 || len < ~^0 then
  44       invalid_arg "device: read: negative offset or length";
  45
  46     let blocksize = self#blocksize in
  47
  48     (* Break the request into blocks.
  49      * Find the first and last blocks of this request.
  50      *)
  51     let first_blk = offset /^ blocksize in
  52     let offset_in_first_blk = offset -^ first_blk *^ blocksize in
  53     let last_blk = (offset +^ len -^ ~^1) /^ blocksize in
  54
  55     (* Buffer for the result. *)
  56     let buf = Buffer.create (Int63.to_int len) in
  57
  58     let not_mapped_error () = invalid_arg "device: read: block not mapped" in
  59
  60     (* Copy the first block (partial). *)
  61     (match self#map_block first_blk with
  62      | [] -> not_mapped_error ()
  63      | (dev, base) :: _ ->
  64          let len =
  65            min len (blocksize -^ offset_in_first_blk) in
  66          let str = dev#read (base +^ offset_in_first_blk) len in
  67          Buffer.add_string buf str
  68     );
  69
  70     (* Copy the middle blocks. *)
  71     let rec loop blk =
  72       if blk < last_blk then (
  73         (match self#map_block blk with
  74          | [] -> not_mapped_error ()
  75          | (dev, base) :: _ ->
  76              let str = dev#read ~^0 self#blocksize in
  77              Buffer.add_string buf str
  78         );
  79         loop (Int63.succ blk)
  80       )
  81     in
  82     loop (Int63.succ first_blk);
  83
  84     (* Copy the last block (partial). *)
  85     if first_blk < last_blk then (
  86       match self#map_block last_blk with
  87       | [] -> not_mapped_error ()
  88       | (dev, base) :: _ ->
  89           let len = (offset +^ len) -^ last_blk *^ blocksize in
  90           let str = dev#read ~^0 len in
  91           Buffer.add_string buf str
  92     );
  93
  94     assert (Int63.to_int len = Buffer.length buf);
  95     Buffer.contents buf
  96
  97   (* Helper method to read a chunk of data into a bitstring. *)
  98   method read_bitstring offset len =
  99     let str = self#read offset len in
 100     (str, 0, String.length str lsl 3)
 101 end
 102
 103 (* A concrete device which just direct-maps a file or /dev device. *)
 104 class block_device filename blocksize =
 105   let fd = openfile filename [ O_RDONLY ] 0 in
 106   let size = Int63.of_int64 (LargeFile.fstat fd).LargeFile.st_size in
 107 object (self)
 108   inherit device
 109   method read offset len =
 110     let offset = Int63.to_int64 offset in
 111     let len = Int63.to_int len in
 112     ignore (LargeFile.lseek fd offset SEEK_SET);
 113     let str = String.make len '\000' in
 114     ignore (read fd str 0 len);
 115     str
 116   method size = size
 117   method name = filename
 118   method blocksize = blocksize
 119   method map_block _ = []
 120   method contiguous offset =
 121     size -^ offset
 122   method close () = close fd
 123 end
 124
 125 (* A linear offset/size from an underlying device. *)
 126 class offset_device name start size blocksize (dev : device) =
 127 object
 128   inherit device
 129   method name = name
 130   method size = size
 131   method read offset len =
 132     if offset < ~^0 || len < ~^0 || offset +^ len > size then
 133       invalid_arg (
 134         sprintf "%s: tried to read outside device boundaries (%s/%s/%s)"
 135           name (Int63.to_string offset) (Int63.to_string len)
 136           (Int63.to_string size)
 137       );
 138     dev#read (start+^offset) len
 139   method blocksize = blocksize
 140   method map_block i = [dev, i *^ blocksize +^ start]
 141   method contiguous offset =
 142     size -^ offset
 143 end
 144
 145 (* A device with just a modified block size. *)
 146 class blocksize_overlay new_blocksize (dev : device) =
 147 object
 148   inherit device
 149   method name = dev#name
 150   method size = dev#size
 151   method read = dev#read
 152   method blocksize = new_blocksize
 153   method map_block new_blk =
 154     let orig_blk = new_blk *^ new_blocksize /^ dev#blocksize in
 155     dev#map_block orig_blk
 156   method contiguous offset = dev#size -^ offset
 157 end
 158
 159 (* The null device.  Any attempt to read generates an error. *)
 160 let null_device : device =
 161 object
 162   inherit device
 163   method read _ _ = assert false
 164   method size = ~^0
 165   method name = "null"
 166   method blocksize = ~^1
 167   method map_block _ = assert false
 168   method contiguous _ = ~^0
 169 end
 170
 171 type machine = {
 172   m_name : string;                      (* Machine name. *)
 173   m_disks : disk list;                  (* Machine disks. *)
 174   m_lv_filesystems :
 175     (lv * filesystem) list;             (* Machine LV filesystems. *)
 176 }
 177 and disk = {
 178   d_name : string;                      (* Device name (eg "hda") *)
 179
 180   (* About the device itself. *)
 181   d_dev : block_device;                 (* Disk device. *)
 182   d_content : disk_content;             (* What's on it. *)
 183 }
 184 and disk_content =
 185   [ `Unknown                            (* Not probed or unknown. *)
 186   | `Partitions of partitions           (* Contains partitions. *)
 187   | `Filesystem of filesystem           (* Contains a filesystem directly. *)
 188   | `PhysicalVolume of pv               (* Contains an LVM PV. *)
 189   ]
 190
 191 (* Partitions. *)
 192
 193 and partitions = {
 194   parts_cb : partitioner_callbacks;     (* Partitioning scheme. *)
 195   parts_dev : device;                   (* Partitions (whole) device. *)
 196   parts : partition list                (* Partitions. *)
 197 }
 198 and partition = {
 199   part_status : partition_status;       (* Bootable, etc. *)
 200   part_type : int;                      (* Partition filesystem type. *)
 201   part_dev : device;                    (* Partition device. *)
 202   part_content : partition_content;     (* What's on it. *)
 203 }
 204 and partition_status = Bootable | Nonbootable | Malformed | NullEntry
 205 and partition_content =
 206   [ `Unknown                            (* Not probed or unknown. *)
 207   | `Filesystem of filesystem           (* Filesystem. *)
 208   | `PhysicalVolume of pv               (* Contains an LVM PV. *)
 209   ]
 210
 211 (* Filesystems (also swap devices). *)
 212 and filesystem = {
 213   fs_cb : filesystem_callbacks;         (* Filesystem. *)
 214   fs_dev : device;                      (* Device containing the filesystem. *)
 215   fs_blocksize : int63;                 (* Block size (bytes). *)
 216   fs_blocks_total : int63;              (* Total blocks. *)
 217   fs_is_swap : bool;                    (* If swap, following not valid. *)
 218   fs_blocks_reserved : int63;           (* Blocks reserved for super-user. *)
 219   fs_blocks_avail : int63;              (* Blocks free (available). *)
 220   fs_blocks_used : int63;               (* Blocks in use. *)
 221   fs_inodes_total : int63;              (* Total inodes. *)
 222   fs_inodes_reserved : int63;           (* Inodes reserved for super-user. *)
 223   fs_inodes_avail : int63;              (* Inodes free (available). *)
 224   fs_inodes_used : int63;               (* Inodes in use. *)
 225 }
 226
 227 (* Physical volumes. *)
 228 and pv = {
 229   pv_cb : lvm_callbacks;                (* The LVM plug-in. *)
 230   pv_dev : device;                      (* Device covering whole PV. *)
 231   pv_uuid : string;                     (* UUID. *)
 232 }
 233
 234 (* Logical volumes. *)
 235 and lv = {
 236   lv_dev : device;                      (* Logical volume device. *)
 237 }
 238
 239 (* Tables of callbacks. *)
 240 and partitioner_probe = device -> partitions
 241
 242 and partitioner_callbacks = {
 243   parts_cb_uq : int;
 244   parts_cb_name : string;
 245   parts_cb_offset_is_free : partitions -> Int63.t -> bool;
 246 }
 247
 248 and filesystem_probe = device -> filesystem
 249
 250 and filesystem_callbacks = {
 251   fs_cb_uq : int;
 252   fs_cb_name : string;
 253   fs_cb_printable_name : string;
 254   fs_cb_offset_is_free : filesystem -> Int63.t -> bool;
 255 }
 256
 257 and lvm_probe = device -> pv
 258
 259 and lvm_callbacks = {
 260   lvm_cb_uq : int;
 261   lvm_cb_name : string;
 262   lvm_cb_list_lvs : pv list -> lv list;
 263   lvm_cb_offset_is_free : pv -> Int63.t -> bool;
 264 }
 265
 266 let name_of_filesystem { fs_cb = { fs_cb_printable_name = name } } = name
 267
 268 (*----------------------------------------------------------------------*)
 269 (* Helper functions. *)
 270
 271 (* Convert a UUID (containing '-' chars) to canonical form. *)
 272 let canonical_uuid uuid =
 273   let uuid' = String.make 32 ' ' in
 274   let j = ref 0 in
 275   for i = 0 to String.length uuid - 1 do
 276     if !j >= 32 then invalid_arg "canonical_uuid";
 277     let c = uuid.[i] in
 278     if c <> '-' then ( uuid'.[!j] <- c; incr j )
 279   done;
 280   if !j <> 32 then invalid_arg "canonical_uuid";
 281   uuid'
 282
 283 (* This version by Isaac Trotts. *)
 284 let group_by ?(cmp = Pervasives.compare) ls =
 285   let ls' =
 286     List.fold_left
 287       (fun acc (day1, x1) ->
 288          match acc with
 289              [] -> [day1, [x1]]
 290            | (day2, ls2) :: acctl ->
 291                if cmp day1 day2 = 0
 292                then (day1, x1 :: ls2) :: acctl
 293                else (day1, [x1]) :: acc)
 294       []
 295       ls
 296   in
 297   let ls' = List.rev ls' in
 298   List.map (fun (x, xs) -> x, List.rev xs) ls'
 299
 300 let rec uniq ?(cmp = Pervasives.compare) = function
 301   | [] -> []
 302   | [x] -> [x]
 303   | x :: y :: xs when cmp x y = 0 ->
 304       uniq (x :: xs)
 305   | x :: y :: xs ->
 306       x :: uniq (y :: xs)
 307
 308 let sort_uniq ?cmp xs =
 309   let xs = ExtList.List.sort ?cmp xs in
 310   let xs = uniq ?cmp xs in
 311   xs
 312
 313 let rec range a b =
 314   if a < b then a :: range (a+1) b
 315   else []
 316
 317 (*----------------------------------------------------------------------*)
 318 (* The plug-ins. *)
 319
 320 let partitioners = ref []
 321 let filesystems = ref []
 322 let lvms = ref []
 323
 324 let register_plugin ?partitioner ?filesystem ?lvm id =
 325   (match partitioner with
 326    | None -> ()
 327    | Some probe -> partitioners := !partitioners @ [id, probe]
 328   );
 329   (match filesystem with
 330    | None -> ()
 331    | Some probe -> filesystems := !filesystems @ [id, probe]
 332   );
 333   (match lvm with
 334    | None -> ()
 335    | Some probe -> lvms := !lvms @ [id, probe]
 336   )
 337
 338 (* Probe a device for partitions.  Returns [Some parts] or [None]. *)
 339 let probe_for_partitions dev =
 340   if !debug then eprintf "probing for partitions on %s ...\n%!" dev#name;
 341   let rec loop = function
 342     | [] -> None
 343     | (_, probe) :: rest ->
 344         try Some (probe dev)
 345         with Not_found -> loop rest
 346   in
 347   let r = loop !partitioners in
 348   if !debug then (
 349     match r with
 350     | None -> eprintf "no partitions found on %s\n%!" dev#name
 351     | Some { parts_cb = { parts_cb_name = name }; parts = parts } ->
 352         eprintf "found %d %s partitions on %s\n"
 353           (List.length parts) name dev#name
 354   );
 355   r
 356
 357 (* Probe a device for a filesystem.  Returns [Some fs] or [None]. *)
 358 let probe_for_filesystem dev =
 359   if !debug then eprintf "probing for a filesystem on %s ...\n%!" dev#name;
 360   let rec loop = function
 361     | [] -> None
 362     | (_, probe) :: rest ->
 363         try Some (probe dev)
 364         with Not_found -> loop rest
 365   in
 366   let r = loop !filesystems in
 367   if !debug then (
 368     match r with
 369     | None -> eprintf "no filesystem found on %s\n%!" dev#name
 370     | Some fs ->
 371         eprintf "found a filesystem on %s:\n" dev#name;
 372         eprintf "\t%s\n%!" fs.fs_cb.fs_cb_name
 373   );
 374   r
 375
 376 (* Probe a device for a PV.  Returns [Some pv] or [None]. *)
 377 let probe_for_pv dev =
 378   if !debug then eprintf "probing if %s is a PV ...\n%!" dev#name;
 379   let rec loop = function
 380     | [] -> None
 381     | (_, probe) :: rest ->
 382         try Some (probe dev)
 383         with Not_found -> loop rest
 384   in
 385   let r = loop !lvms in
 386   if !debug then (
 387     match r with
 388     | None -> eprintf "no PV found on %s\n%!" dev#name
 389     | Some { pv_cb = { lvm_cb_name = name } } ->
 390         eprintf "%s contains a %s PV\n%!" dev#name name
 391   );
 392   r
 393
 394 (* This allows plug-ins to attach their own private data to
 395  * the normal plug-in structures (partitions, filesystem, pv, etc.)
 396  *)
 397 let private_data_functions get_key =
 398   let h = Hashtbl.create 13 in
 399   (fun struc data ->
 400      Hashtbl.replace h (get_key struc) data),
 401   (fun struc ->
 402      try Hashtbl.find h (get_key struc)
 403      with Not_found -> assert false (* internal error in the plug-in *))
 404
 405 (*----------------------------------------------------------------------*)
 406 (* Create machine description. *)
 407 let open_machine_from_devices name disks =
 408   let disks = List.map (
 409     fun (name, dev) ->
 410       { d_name = name; d_dev = dev; d_content = `Unknown }
 411   ) disks in
 412   { m_name = name; m_disks = disks; m_lv_filesystems = [] }
 413
 414 let open_machine name disks =
 415   let disks = List.map (
 416     fun (name, path) ->
 417       let dev = new block_device path disk_block_size (* XXX *) in
 418       name, dev
 419   ) disks in
 420   open_machine_from_devices name disks
 421
 422 let close_machine { m_disks = m_disks } =
 423   (* Only close the disks, assume all other devices are derived from them. *)
 424   List.iter (fun { d_dev = d_dev } -> d_dev#close ()) m_disks
 425
 426 (* Main scanning function for filesystems. *)
 427 let scan_machine ({ m_disks = m_disks } as machine) =
 428   let m_disks = List.map (
 429     fun ({ d_dev = dev } as disk) ->
 430       let dev = (dev :> device) in
 431       (* See if it is partitioned first. *)
 432       let parts = probe_for_partitions dev in
 433       match parts with
 434       | Some parts ->
 435           { disk with d_content = `Partitions parts }
 436       | None ->
 437           (* Not partitioned.  Does it contain a filesystem? *)
 438           let fs = probe_for_filesystem dev in
 439           match fs with
 440           | Some fs ->
 441               { disk with d_content = `Filesystem fs }
 442           | None ->
 443               (* Not partitioned, no filesystem, is it a PV? *)
 444               let pv = probe_for_pv dev in
 445               match pv with
 446               | Some pv ->
 447                   { disk with d_content = `PhysicalVolume pv }
 448               | None ->
 449                   disk (* Spare/unknown. *)
 450   ) m_disks in
 451
 452   (* Now we have either detected partitions or a filesystem on each
 453    * physical device (or perhaps neither).  See what is on those
 454    * partitions.
 455    *)
 456   let m_disks = List.map (
 457     function
 458     | ({ d_dev = dev; d_content = `Partitions parts } as disk) ->
 459         let ps = List.map (
 460           fun p ->
 461             if p.part_status = Bootable || p.part_status = Nonbootable then (
 462               let fs = probe_for_filesystem p.part_dev in
 463               match fs with
 464               | Some fs ->
 465                   { p with part_content = `Filesystem fs }
 466               | None ->
 467                   (* Is it a PV? *)
 468                   let pv = probe_for_pv p.part_dev in
 469                   match pv with
 470                   | Some lvm_name ->
 471                       { p with part_content = `PhysicalVolume lvm_name }
 472                   | None ->
 473                       p (* Spare/unknown. *)
 474             ) else p
 475         ) parts.parts in
 476         let parts = { parts with parts = ps } in
 477         { disk with d_content = `Partitions parts }
 478     | disk -> disk
 479   ) m_disks in
 480
 481   (* LVM filesystem detection
 482    *
 483    * Look for all disks/partitions which have been identified as PVs
 484    * and pass those back to the respective LVM plugin for LV detection.
 485    *
 486    * (Note - a two-stage process because an LV can be spread over
 487    * several PVs, so we have to detect all PVs belonging to a
 488    * domain first).
 489    *
 490    * XXX To deal with RAID (ie. md devices) we will need to loop
 491    * around here because RAID is like LVM except that they normally
 492    * present as block devices which can be used by LVM.
 493    *)
 494   (* First: LV detection.
 495    * Find all physical volumes, can be disks or partitions.
 496    *)
 497   let pvs_on_disks = List.filter_map (
 498     function
 499     | { d_content = `PhysicalVolume pv } -> Some pv
 500     | _ -> None
 501   ) m_disks in
 502   let pvs_on_partitions = List.map (
 503     function
 504     | { d_content = `Partitions { parts = parts } } ->
 505         List.filter_map (
 506           function
 507           | { part_content = `PhysicalVolume pv } -> Some pv
 508           | _ -> None
 509         ) parts
 510     | _ -> []
 511   ) m_disks in
 512   let lvs = List.concat (pvs_on_disks :: pvs_on_partitions) in
 513
 514   (* Second: filesystem on LV detection.
 515    * Group the LVs by LVM plug-in ID.
 516    *)
 517   let lvs =
 518     List.map (fun ({pv_cb = {lvm_cb_name = name}} as pv) -> name, pv) lvs in
 519   let lvs = List.sort lvs in
 520   let lvs = group_by lvs in
 521
 522   let lvs = List.map (fun (name, pvs) ->
 523                         let pv = List.hd pvs in
 524                         pv.pv_cb.lvm_cb_list_lvs pvs) lvs in
 525   let lvs = List.concat lvs in
 526
 527   (* lvs is a list of potential LV devices.  Now run them through the
 528    * probes to see if any contain filesystems.
 529    *)
 530   let filesystems =
 531     List.filter_map (
 532       fun ({ lv_dev = dev } as lv) ->
 533         match probe_for_filesystem dev with
 534         | Some fs -> Some (lv, fs)
 535         | None -> None
 536     ) lvs in
 537
 538   { machine with
 539       m_disks = m_disks;
 540       m_lv_filesystems = filesystems }
 541
 542 (*----------------------------------------------------------------------*)
 543
 544 (* We describe the ownership of each part of the disk using a
 545  * segment tree. http://en.wikipedia.org/wiki/Segment_tree
 546  *
 547  * Note that each part can (and usually is) owned multiple times
 548  * (eg. by a filesystem and by the partition that the filesystem
 549  * lies inside).  Also, the segment tree is effectively read-only.
 550  * We build it up as a final step given the flat list of segments
 551  * identified by the algorithm in 'iter_over_machine'.
 552  *)
 553
 554 (* General binary tree type.  Data 'a is stored in the leaves and 'b
 555  * is stored in the nodes.
 556  *)
 557 type ('a,'b) binary_tree =
 558   | Leaf of 'a
 559   | Node of ('a,'b) binary_tree * 'b * ('a,'b) binary_tree
 560
 561 (* This prints out the binary tree in graphviz dot format. *)
 562 let print_binary_tree leaf_printer node_printer tree =
 563   (* Assign a unique, fixed label to each node. *)
 564   let label =
 565     let i = ref 0 in
 566     let hash = Hashtbl.create 13 in
 567     fun node ->
 568       try Hashtbl.find hash node
 569       with Not_found ->
 570         let i = incr i; !i in
 571         let label = "n" ^ string_of_int i in
 572         Hashtbl.add hash node label;
 573         label
 574   in
 575   (* Recursively generate the graphviz file. *)
 576   let rec print = function
 577     | (Leaf a as leaf) ->
 578         eprintf "  %s [shape=box, label=\"%s\"];\n"
 579           (label leaf) (leaf_printer a)
 580     | (Node (left,b,right) as node) ->
 581         eprintf "  %s [label=\"%s\"];\n"
 582           (label node) (node_printer b);
 583         eprintf "  %s -> %s [tailport=sw];\n" (label node) (label left);
 584         eprintf "  %s -> %s [tailport=se];\n" (label node) (label right);
 585         print left;
 586         print right;
 587   in
 588   eprintf "/* Use 'dot -Tpng foo.dot > foo.png' to convert to a png file. */\n";
 589   eprintf "digraph G {\n";
 590   print tree;
 591   eprintf "}\n%!";
 592
 593 type owner =
 594     [ `Filesystem of filesystem
 595     | `Partitions of partitions
 596     | `PhysicalVolume of pv ]
 597
 598 (* A segment describes the owner of a range of disk addresses. *)
 599 type segment = owner * int63            (* owner, owner offset *)
 600
 601 type interval = int63 * int63           (* start point, end point (bytes) *)
 602
 603 (* The special segment tree structure that we construct in create_ownership. *)
 604 type segment_tree =
 605     (interval * segment list, interval * segment list) binary_tree
 606
 607 type ownership =
 608     (device *                           (* block_device (disk) *)
 609        segment_tree) list               (* segment tree for this disk *)
 610
 611 (* List of owned segments before we build the segment tree. *)
 612 type ownership_list =
 613     (device *                           (* block_device (disk) *)
 614        (int63 * int63 *                 (* disk offset, size of segment *)
 615           owner * int63                 (* owner, owner offset *)
 616        )
 617     ) list
 618
 619 (* Ownership tables. *)
 620 let create_ownership machine =
 621   (* Iterate over all the things which can claim ownership of a
 622    * disk block (filesystems, partitions, PVs).
 623    *)
 624   let rec iter_over_machine
 625       ({m_disks = disks; m_lv_filesystems = lv_filesystems} as machine) =
 626
 627     (* No segments to begin with. *)
 628     let ownership = [] in
 629
 630     (* Iterate over disks. *)
 631     let ownership =
 632       List.fold_left (
 633         fun ownership ->
 634           function
 635           | { d_content = (`Filesystem fs as owner) } ->
 636               iter_over_filesystem machine ownership fs owner
 637           | { d_content = (`Partitions parts as owner) } ->
 638               iter_over_partitions machine ownership parts owner
 639           | { d_content = (`PhysicalVolume pv as owner) } ->
 640               iter_over_pv machine ownership pv owner
 641           | { d_content = `Unknown } -> ownership
 642       ) ownership disks in
 643
 644     (* Iterate over LV filesystems. *)
 645     let ownership =
 646       List.fold_left (
 647         fun ownership (lv, fs) ->
 648           let owner = `Filesystem fs in
 649           iter_over_filesystem machine ownership fs owner
 650       ) ownership lv_filesystems in
 651
 652     ownership
 653
 654   (* Iterate over the blocks in a single filesystem. *)
 655   and iter_over_filesystem machine ownership {fs_dev = dev} owner =
 656     iter_over_device machine ownership dev owner
 657
 658   (* Iterate over the blocks in a set of partitions, then
 659    * iterate over the contents of the partitions.
 660    *)
 661   and iter_over_partitions machine ownership
 662       {parts = parts; parts_dev = parts_dev} owner =
 663     let ownership = iter_over_device machine ownership parts_dev owner in
 664
 665     let ownership =
 666       List.fold_left (
 667         fun ownership ->
 668           function
 669           | { part_content = (`Filesystem fs as owner) } ->
 670               iter_over_filesystem machine ownership fs owner
 671           | { part_content = (`PhysicalVolume pv as owner) } ->
 672               iter_over_pv machine ownership pv owner
 673           | { part_content = `Unknown } -> ownership
 674       ) ownership parts in
 675
 676     ownership
 677
 678   (* Iterate over the blocks in a PV. *)
 679   and iter_over_pv machine ownership {pv_dev = dev} owner =
 680     iter_over_device machine ownership dev owner
 681
 682   (* Iterate over the blocks in a device, assigning ownership to 'owner'
 683    *
 684    * In reality (1): There can be several owners for each block, so we
 685    * incrementally add ownership to the ownership_list (which eventually
 686    * will be turned into a segment tree).
 687    * In reality (2): Iterating over blocks would take ages and result
 688    * in a very inefficient ownership representation.  Instead we look
 689    * at minimum contiguous extents.
 690    *)
 691   and iter_over_device { m_disks = disks } ownership dev owner =
 692     let size = dev#size in
 693     let disks = List.map (fun {d_dev = dev} -> (dev :> device)) disks in
 694
 695     let rec loop ownership offset =
 696       if offset < size then (
 697         let devs, extent = get_next_extent disks dev offset in
 698         if devs = [] then
 699           eprintf "warning: no device found under %s\n"
 700             (string_of_owner owner);
 701         let ownership =
 702           List.fold_left (
 703             fun ownership (disk, disk_offset) ->
 704               let elem = disk, (disk_offset, extent, owner, offset) in
 705               elem :: ownership
 706           ) ownership devs in
 707         loop ownership (offset +^ extent)
 708       )
 709       else ownership
 710     in
 711     loop ownership ~^0
 712
 713   (* Return the length of the next contiguous region in the device starting
 714    * at the given byte offset.  Also return the underlying block device(s)
 715    * if there is one.
 716    *)
 717   and get_next_extent disks (dev : device) offset =
 718     let this_extent = dev#contiguous offset in
 719
 720     (* If this disk is a block_device (a member of the 'disks' list)
 721      * then we've hit the bottom layer of devices, so just return it.
 722      *)
 723     if List.memq dev disks then
 724       [dev, offset], this_extent
 725     else (
 726       let blocksize = dev#blocksize in
 727       let block = offset /^ blocksize in
 728       let offset_in_block = offset -^ block *^ blocksize in
 729
 730       (* Map from this block to the devices one layer down. *)
 731       let devs = dev#map_block block in
 732
 733       (* Get the real device offsets, adding the offset from start of block. *)
 734       let devs =
 735         List.map
 736           (fun (dev, dev_offset) -> dev, dev_offset +^ offset_in_block)
 737           devs in
 738
 739       let devs =
 740         List.map
 741           (fun (dev, dev_offset) ->
 742              get_next_extent disks dev dev_offset)
 743           devs in
 744
 745       (* Work out the minimum contiguous extent from this offset. *)
 746       let devs, extent =
 747         let extents = List.map snd devs in
 748         let devs = List.concat (List.map fst devs) in
 749         let extent = List.fold_left min this_extent extents in
 750         devs, extent in
 751
 752       devs, extent
 753     )
 754
 755   and string_of_owner = function
 756     | `Filesystem {fs_cb = {fs_cb_name = name}; fs_dev = fs_dev} ->
 757         sprintf "%s(%s)" fs_dev#name name
 758     | `PhysicalVolume { pv_uuid = pv_uuid } ->
 759         "PV:" ^ pv_uuid
 760     | `Partitions { parts_cb = {parts_cb_name = name} } ->
 761         name
 762   in
 763
 764   (* Build the list of segments. *)
 765   let ownership : ownership_list = iter_over_machine machine in
 766
 767   (* Group the segments together by disk. *)
 768   let ownership =
 769     let ownership = List.sort ownership in
 770     group_by ownership in
 771
 772   (* If debugging, print the segments that we found. *)
 773   if !debug then (
 774     List.iter (
 775       fun (disk, segments) ->
 776         eprintf "ownership segment list of %s %s:\n" machine.m_name disk#name;
 777         List.iter (
 778           fun (disk_offset, size, owner, owner_offset) ->
 779             let blocksize = disk#blocksize in
 780             let disk_offset_in_blocks, disk_offset_in_block =
 781               disk_offset /^ blocksize, disk_offset %^ blocksize in
 782             let size_in_blocks, size_in_block =
 783               size /^ blocksize, size %^ blocksize in
 784
 785             eprintf "  %s[%s:%s] %s[%s:%s] %s@%s\n"
 786               (Int63.to_string disk_offset)
 787                 (Int63.to_string disk_offset_in_blocks)
 788                 (Int63.to_string disk_offset_in_block)
 789               (Int63.to_string size)
 790                 (Int63.to_string size_in_blocks)
 791                 (Int63.to_string size_in_block)
 792               (string_of_owner owner)
 793               (Int63.to_string owner_offset)
 794         ) segments
 795     ) ownership
 796   );
 797
 798   (* Build the segment tree from the ownership list (of segments).
 799    * For an explanation of this process see:
 800    * http://en.wikipedia.org/wiki/Segment_tree
 801    *)
 802   let ownership =
 803     List.map (
 804       fun (disk, segments) ->
 805         (* Construct the list of distinct endpoints. *)
 806         let eps =
 807           List.map
 808             (fun (start, size, _, _) -> [start; start +^ size])
 809             segments in
 810         let eps = sort_uniq (List.concat eps) in
 811
 812         (* Construct the elementary intervals. *)
 813         let elints =
 814           let elints, lastpoint =
 815             List.fold_left (
 816               fun (elints, prevpoint) point ->
 817                 ((point, point) :: (prevpoint, point) :: elints), point
 818             ) ([], Int63.min_int) eps in
 819           let elints = (lastpoint, Int63.max_int) :: elints in
 820           List.rev elints in
 821
 822         if !debug then (
 823           eprintf "elementary intervals for %s (%d in total):\n"
 824             disk#name (List.length elints);
 825           List.iter (
 826             fun (startpoint, endpoint) ->
 827               eprintf "  %s %s\n"
 828                 (Int63.to_string startpoint) (Int63.to_string endpoint)
 829           ) elints
 830         );
 831
 832         (* Construct the binary tree of elementary intervals. *)
 833         let tree =
 834           (* Each elementary interval becomes a leaf. *)
 835           let elints = List.map (fun elint -> Leaf elint) elints in
 836           (* Recursively build this into a binary tree. *)
 837           let rec make_layer = function
 838             | [] -> []
 839             | ([_] as x) -> x
 840             (* Turn pairs of leaves at the bottom level into nodes. *)
 841             | (Leaf _ as a) :: (Leaf _ as b) :: xs ->
 842                 let xs = make_layer xs in
 843                 Node (a, (), b) :: xs
 844             (* Turn pairs of nodes at higher levels into nodes. *)
 845             | (Node _ as left) :: ((Node _|Leaf _) as right) :: xs ->
 846                 let xs = make_layer xs in
 847                 Node (left, (), right) :: xs
 848             | Leaf _ :: _ -> assert false (* never happens??? (I think) *)
 849           in
 850           let rec loop = function
 851             | [] -> assert false
 852             | [x] -> x
 853             | xs -> loop (make_layer xs)
 854           in
 855           loop elints in
 856
 857         if !debug then (
 858           let leaf_printer (startpoint, endpoint) =
 859             sprintf "%s-%s"
 860               (Int63.to_string startpoint) (Int63.to_string endpoint)
 861           in
 862           let node_printer () = "" in
 863           print_binary_tree leaf_printer node_printer tree
 864         );
 865
 866         (* Insert the segments into the tree one by one. *)
 867         let tree =
 868           (* For each node/leaf in the tree, add its interval and an
 869            * empty list which will be used to store the segments.
 870            *)
 871           let rec interval_tree = function
 872             | Leaf elint -> Leaf (elint, [])
 873             | Node (left, (), right) ->
 874                 let left = interval_tree left in
 875                 let right = interval_tree right in
 876                 let (leftstart, _) = interval_of_node left in
 877                 let (_, rightend) = interval_of_node right in
 878                 let interval = leftstart, rightend in
 879                 Node (left, (interval, []), right)
 880           and interval_of_node = function
 881             | Leaf (elint, _) -> elint
 882             | Node (_, (interval, _), _) -> interval
 883           in
 884
 885           let tree = interval_tree tree in
 886           (* This should always be true: *)
 887           assert (interval_of_node tree = (Int63.min_int, Int63.max_int));
 888
 889           (* "Contained in" operator.
 890            * 'a <-< b' iff 'a' is a subinterval of 'b'.
 891            *      |<---- a ---->|
 892            * |<----------- b ----------->|
 893            *)
 894           let (<-<) (a1, a2) (b1, b2) = b1 <= a1 && a2 <= b2 in
 895
 896           (* "Intersects" operator.
 897            * 'a /\ b' iff intervals 'a' and 'b' overlap, eg:
 898            *      |<---- a ---->|
 899            *                |<----------- b ----------->|
 900            *)
 901           let ( /\ ) (a1, a2) (b1, b2) = a2 > b1 || b2 > a1 in
 902
 903           let rec insert_segment tree segment =
 904             let start, size, owner, owner_offset = segment in
 905             let seginterval = start, start +^ size in
 906             let seg = owner, owner_offset in
 907
 908             match tree with
 909             (* Test if we should insert into this leaf or node: *)
 910             | Leaf (interval, segs) when interval <-< seginterval ->
 911                 Leaf (interval, seg :: segs)
 912             | Node (left, (interval, segs), right)
 913                 when interval <-< seginterval ->
 914                 Node (left, (interval, seg :: segs), right)
 915
 916             | (Leaf _) as leaf -> leaf
 917
 918             (* Else, should we insert into left or right subtrees? *)
 919             | Node (left, i, right) ->
 920                 let left =
 921                   if seginterval /\ interval_of_node left then
 922                     insert_segment left segment
 923                   else
 924                     left in
 925                 let right =
 926                   if seginterval /\ interval_of_node right then
 927                     insert_segment right segment
 928                   else
 929                     right in
 930                 Node (left, i, right)
 931           in
 932           let tree = List.fold_left insert_segment tree segments in
 933           tree in
 934
 935         if !debug then (
 936           let printer ((sp, ep), segments) =
 937             sprintf "[%s-%s] " (Int63.to_string sp) (Int63.to_string ep) ^
 938               String.concat ";"
 939               (List.map (fun (owner,_) -> string_of_owner owner)
 940                  segments)
 941           in
 942           print_binary_tree printer printer tree
 943         );
 944         (disk, tree)
 945     ) ownership in
 946
 947   (* Return the ownership structure. *)
 948   ownership
 949
 950 let get_owners_lookup machine ownership (disk : block_device) =
 951   (* Get the correct tree. *)
 952   let tree = List.assoc (disk :> device) ownership in
 953
 954   fun offset ->
 955     (* Warning: This 'hot' code was carefully optimized based on
 956      * feedback from 'gprof'.  Avoid fiddling with it.
 957      *)
 958     let rec query = function
 959       | Leaf (_, segments) -> segments
 960
 961       (* Try to avoid expensive '@' operator if node segments is empty: *)
 962       | Node ((Leaf ((_, leftend), _) | Node (_, ((_, leftend), _), _) as left),
 963               (_, []),
 964               right) ->
 965           let subsegments =
 966             if offset < leftend then query left else query right in
 967           subsegments
 968
 969       (* ... or a singleton: *)
 970       | Node ((Leaf ((_, leftend), _) | Node (_, ((_, leftend), _), _) as left),
 971               (_, [segment]),
 972               right) ->
 973           let subsegments =
 974             if offset < leftend then query left else query right in
 975           segment :: subsegments
 976
 977       (* Normal recursive case: *)
 978       | Node ((Leaf ((_, leftend), _) | Node (_, ((_, leftend), _), _) as left),
 979               (_, segments),
 980               right) ->
 981           let subsegments =
 982             if offset < leftend then query left else query right in
 983           segments @ subsegments
 984     in
 985     let owners = query tree in
 986
 987     List.map (
 988       fun (owner, owner_offset) -> (owner, offset -^ owner_offset)
 989     ) owners
 990
 991 (* Find out if a disk offset is free.
 992  * Current algorithm just checks that at least one owner says
 993  * it is free.  We could be smarter about this.
 994  *)
 995 let offset_is_free owners =
 996   List.exists (
 997     function
 998     | `Filesystem fs, offset ->
 999         fs.fs_cb.fs_cb_offset_is_free fs offset
1000     | `Partitions parts, offset ->
1001         parts.parts_cb.parts_cb_offset_is_free parts offset
1002     | `PhysicalVolume pv, offset ->
1003         pv.pv_cb.lvm_cb_offset_is_free pv offset
1004   ) owners