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