1 (* Diskimage library for reading disk images.
2 (C) Copyright 2007-2008 Richard W.M. Jones, Red Hat Inc.
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.
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.
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
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.
32 let disk_block_size = ~^512
34 class virtual device =
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
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";
47 let blocksize = self#blocksize in
49 (* Break the request into blocks.
50 * Find the first and last blocks of this request.
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
56 (* Buffer for the result. *)
57 let buf = Buffer.create (Int63.to_int len) in
59 let not_mapped_error () = invalid_arg "device: read: block not mapped" in
61 (* Copy the first block (partial). *)
62 (match self#map_block first_blk with
63 | [] -> not_mapped_error ()
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
71 (* Copy the middle blocks. *)
73 if blk < last_blk then (
74 (match self#map_block blk with
75 | [] -> not_mapped_error ()
77 let str = dev#read ~^0 self#blocksize in
78 Buffer.add_string buf str
83 loop (Int63.succ first_blk);
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 ()
90 let len = (offset +^ len) -^ last_blk *^ blocksize in
91 let str = dev#read ~^0 len in
92 Buffer.add_string buf str
95 assert (Int63.to_int len = Buffer.length buf);
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)
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
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);
118 method name = filename
119 method blocksize = blocksize
120 method map_block _ = []
121 method contiguous offset =
123 method close () = close fd
126 (* A linear offset/size from an underlying device. *)
127 class offset_device name start size blocksize (dev : device) =
132 method read offset len =
133 if offset < ~^0 || len < ~^0 || offset +^ len > size then
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)
139 dev#read (start+^offset) len
140 method blocksize = blocksize
141 method map_block i = [dev, i *^ blocksize +^ start]
142 method contiguous offset =
146 (* A device with just a modified block size. *)
147 class blocksize_overlay new_blocksize (dev : 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
160 (* The null device. Any attempt to read generates an error. *)
161 let null_device : device =
164 method read _ _ = assert false
167 method blocksize = ~^1
168 method map_block _ = assert false
169 method contiguous _ = ~^0
173 m_name : string; (* Machine name. *)
174 m_disks : disk list; (* Machine disks. *)
176 (lv * filesystem) list; (* Machine LV filesystems. *)
179 d_name : string; (* Device name (eg "hda") *)
181 (* About the device itself. *)
182 d_dev : block_device; (* Disk device. *)
183 d_content : disk_content; (* What's on it. *)
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. *)
195 parts_cb : partitioner_callbacks; (* Partitioning scheme. *)
196 parts_dev : device; (* Partitions (whole) device. *)
197 parts : partition list (* Partitions. *)
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. *)
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. *)
212 (* Filesystems (also swap devices). *)
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. *)
228 (* Physical volumes. *)
230 pv_cb : lvm_callbacks; (* The LVM plug-in. *)
231 pv_dev : device; (* Device covering whole PV. *)
232 pv_uuid : string; (* UUID. *)
235 (* Logical volumes. *)
237 lv_dev : device; (* Logical volume device. *)
240 (* Tables of callbacks. *)
241 and partitioner_probe = device -> partitions
243 and partitioner_callbacks = {
245 parts_cb_name : string;
246 parts_cb_offset_is_free : partitions -> Int63.t -> bool;
249 and filesystem_probe = device -> filesystem
251 and filesystem_callbacks = {
254 fs_cb_printable_name : string;
255 fs_cb_offset_is_free : filesystem -> Int63.t -> bool;
258 and lvm_probe = device -> pv
260 and lvm_callbacks = {
262 lvm_cb_name : string;
263 lvm_cb_list_lvs : pv list -> lv list;
264 lvm_cb_offset_is_free : pv -> Int63.t -> bool;
267 let name_of_filesystem { fs_cb = { fs_cb_printable_name = name } } = name
269 (*----------------------------------------------------------------------*)
270 (* Helper functions. *)
272 (* Convert a UUID (containing '-' chars) to canonical form. *)
273 let canonical_uuid uuid =
274 let uuid' = String.make 32 ' ' in
276 for i = 0 to String.length uuid - 1 do
277 if !j >= 32 then invalid_arg "canonical_uuid";
279 if c <> '-' then ( uuid'.[!j] <- c; incr j )
281 if !j <> 32 then invalid_arg "canonical_uuid";
284 (* This version by Isaac Trotts. *)
285 let group_by ?(cmp = Pervasives.compare) ls =
288 (fun acc (day1, x1) ->
291 | (day2, ls2) :: acctl ->
293 then (day1, x1 :: ls2) :: acctl
294 else (day1, [x1]) :: acc)
298 let ls' = List.rev ls' in
299 List.map (fun (x, xs) -> x, List.rev xs) ls'
301 let rec uniq ?(cmp = Pervasives.compare) = function
304 | x :: y :: xs when cmp x y = 0 ->
309 let sort_uniq ?cmp xs =
310 let xs = ExtList.List.sort ?cmp xs in
311 let xs = uniq ?cmp xs in
315 if a < b then a :: range (a+1) b
318 (*----------------------------------------------------------------------*)
321 let partitioners = ref []
322 let filesystems = ref []
325 let register_plugin ?partitioner ?filesystem ?lvm id =
326 (match partitioner with
328 | Some probe -> partitioners := !partitioners @ [id, probe]
330 (match filesystem with
332 | Some probe -> filesystems := !filesystems @ [id, probe]
336 | Some probe -> lvms := !lvms @ [id, probe]
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
344 | (_, probe) :: rest ->
346 with Not_found -> loop rest
348 let r = loop !partitioners in
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
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
363 | (_, probe) :: rest ->
365 with Not_found -> loop rest
367 let r = loop !filesystems in
370 | None -> eprintf "no filesystem found on %s\n%!" dev#name
372 eprintf "found a filesystem on %s:\n" dev#name;
373 eprintf "\t%s\n%!" fs.fs_cb.fs_cb_name
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
382 | (_, probe) :: rest ->
384 with Not_found -> loop rest
386 let r = loop !lvms in
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
395 (* This allows plug-ins to attach their own private data to
396 * the normal plug-in structures (partitions, filesystem, pv, etc.)
398 let private_data_functions get_key =
399 let h = Hashtbl.create 13 in
401 Hashtbl.replace h (get_key struc) data),
403 try Hashtbl.find h (get_key struc)
404 with Not_found -> assert false (* internal error in the plug-in *))
406 (*----------------------------------------------------------------------*)
407 (* Create machine description. *)
408 let open_machine_from_devices name disks =
409 let disks = List.map (
411 { d_name = name; d_dev = dev; d_content = `Unknown }
413 { m_name = name; m_disks = disks; m_lv_filesystems = [] }
415 let open_machine name disks =
416 let disks = List.map (
418 let dev = new block_device path disk_block_size (* XXX *) in
421 open_machine_from_devices name disks
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
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
436 { disk with d_content = `Partitions parts }
438 (* Not partitioned. Does it contain a filesystem? *)
439 let fs = probe_for_filesystem dev in
442 { disk with d_content = `Filesystem fs }
444 (* Not partitioned, no filesystem, is it a PV? *)
445 let pv = probe_for_pv dev in
448 { disk with d_content = `PhysicalVolume pv }
450 disk (* Spare/unknown. *)
453 (* Now we have either detected partitions or a filesystem on each
454 * physical device (or perhaps neither). See what is on those
457 let m_disks = List.map (
459 | ({ d_dev = dev; d_content = `Partitions parts } as disk) ->
462 if p.part_status = Bootable || p.part_status = Nonbootable then (
463 let fs = probe_for_filesystem p.part_dev in
466 { p with part_content = `Filesystem fs }
469 let pv = probe_for_pv p.part_dev in
472 { p with part_content = `PhysicalVolume lvm_name }
474 p (* Spare/unknown. *)
477 let parts = { parts with parts = ps } in
478 { disk with d_content = `Partitions parts }
482 (* LVM filesystem detection
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.
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
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.
495 (* First: LV detection.
496 * Find all physical volumes, can be disks or partitions.
498 let pvs_on_disks = List.filter_map (
500 | { d_content = `PhysicalVolume pv } -> Some pv
503 let pvs_on_partitions = List.map (
505 | { d_content = `Partitions { parts = parts } } ->
508 | { part_content = `PhysicalVolume pv } -> Some pv
513 let lvs = List.concat (pvs_on_disks :: pvs_on_partitions) in
515 (* Second: filesystem on LV detection.
516 * Group the LVs by LVM plug-in ID.
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
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
528 (* lvs is a list of potential LV devices. Now run them through the
529 * probes to see if any contain filesystems.
533 fun ({ lv_dev = dev } as lv) ->
534 match probe_for_filesystem dev with
535 | Some fs -> Some (lv, fs)
541 m_lv_filesystems = filesystems }
543 (*----------------------------------------------------------------------*)
545 (* We describe the ownership of each part of the disk using a
546 * segment tree. http://en.wikipedia.org/wiki/Segment_tree
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'.
555 (* General binary tree type. Data 'a is stored in the leaves and 'b
556 * is stored in the nodes.
558 type ('a,'b) binary_tree =
560 | Node of ('a,'b) binary_tree * 'b * ('a,'b) binary_tree
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. *)
567 let hash = Hashtbl.create 13 in
569 try Hashtbl.find hash node
571 let i = incr i; !i in
572 let label = "n" ^ string_of_int i in
573 Hashtbl.add hash node label;
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);
589 eprintf "/* Use 'dot -Tpng foo.dot > foo.png' to convert to a png file. */\n";
590 eprintf "digraph G {\n";
595 [ `Filesystem of filesystem
596 | `Partitions of partitions
597 | `PhysicalVolume of pv ]
599 (* A segment describes the owner of a range of disk addresses. *)
600 type segment = owner * int63 (* owner, owner offset *)
602 type interval = int63 * int63 (* start point, end point (bytes) *)
604 (* The special segment tree structure that we construct in create_ownership. *)
606 (interval * segment list, interval * segment list) binary_tree
609 (device * (* block_device (disk) *)
610 segment_tree) list (* segment tree for this disk *)
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 *)
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).
625 let rec iter_over_machine
626 ({m_disks = disks; m_lv_filesystems = lv_filesystems} as machine) =
628 (* No segments to begin with. *)
629 let ownership = [] in
631 (* Iterate over disks. *)
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
645 (* Iterate over LV filesystems. *)
648 fun ownership (lv, fs) ->
649 let owner = `Filesystem fs in
650 iter_over_filesystem machine ownership fs owner
651 ) ownership lv_filesystems in
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
659 (* Iterate over the blocks in a set of partitions, then
660 * iterate over the contents of the partitions.
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
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
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
683 (* Iterate over the blocks in a device, assigning ownership to 'owner'
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.
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
696 let rec loop ownership offset =
697 if offset < size then (
698 let devs, extent = get_next_extent disks dev offset in
700 eprintf "warning: no device found under %s\n"
701 (string_of_owner owner);
704 fun ownership (disk, disk_offset) ->
705 let elem = disk, (disk_offset, extent, owner, offset) in
708 loop ownership (offset +^ extent)
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)
718 and get_next_extent disks (dev : device) offset =
719 let this_extent = dev#contiguous offset in
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.
724 if List.memq dev disks then
725 [dev, offset], this_extent
727 let blocksize = dev#blocksize in
728 let block = offset /^ blocksize in
729 let offset_in_block = offset -^ block *^ blocksize in
731 (* Map from this block to the devices one layer down. *)
732 let devs = dev#map_block block in
734 (* Get the real device offsets, adding the offset from start of block. *)
737 (fun (dev, dev_offset) -> dev, dev_offset +^ offset_in_block)
742 (fun (dev, dev_offset) ->
743 get_next_extent disks dev dev_offset)
746 (* Work out the minimum contiguous extent from this offset. *)
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
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 } ->
761 | `Partitions { parts_cb = {parts_cb_name = name} } ->
765 (* Build the list of segments. *)
766 let ownership : ownership_list = iter_over_machine machine in
768 (* Group the segments together by disk. *)
770 let ownership = List.sort ownership in
771 group_by ownership in
773 (* If debugging, print the segments that we found. *)
776 fun (disk, segments) ->
777 eprintf "ownership segment list of %s %s:\n" machine.m_name disk#name;
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
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)
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
805 fun (disk, segments) ->
806 (* Construct the list of distinct endpoints. *)
809 (fun (start, size, _, _) -> [start; start +^ size])
811 let eps = sort_uniq (List.concat eps) in
813 (* Construct the elementary intervals. *)
815 let elints, lastpoint =
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
824 eprintf "elementary intervals for %s (%d in total):\n"
825 disk#name (List.length elints);
827 fun (startpoint, endpoint) ->
829 (Int63.to_string startpoint) (Int63.to_string endpoint)
833 (* Construct the binary tree of elementary intervals. *)
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
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) *)
851 let rec loop = function
854 | xs -> loop (make_layer xs)
859 let leaf_printer (startpoint, endpoint) =
861 (Int63.to_string startpoint) (Int63.to_string endpoint)
863 let node_printer () = "" in
864 print_binary_tree leaf_printer node_printer tree
867 (* Insert the segments into the tree one by one. *)
869 (* For each node/leaf in the tree, add its interval and an
870 * empty list which will be used to store the segments.
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
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));
890 (* "Contained in" operator.
891 * 'a <-< b' iff 'a' is a subinterval of 'b'.
893 * |<----------- b ----------->|
895 let (<-<) (a1, a2) (b1, b2) = b1 <= a1 && a2 <= b2 in
897 (* "Intersects" operator.
898 * 'a /\ b' iff intervals 'a' and 'b' overlap, eg:
900 * |<----------- b ----------->|
902 let ( /\ ) (a1, a2) (b1, b2) = a2 > b1 || b2 > a1 in
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
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)
917 | (Leaf _) as leaf -> leaf
919 (* Else, should we insert into left or right subtrees? *)
920 | Node (left, i, right) ->
922 if seginterval /\ interval_of_node left then
923 insert_segment left segment
927 if seginterval /\ interval_of_node right then
928 insert_segment right segment
931 Node (left, i, right)
933 let tree = List.fold_left insert_segment tree segments in
937 let printer ((sp, ep), segments) =
938 sprintf "[%s-%s] " (Int63.to_string sp) (Int63.to_string ep) ^
940 (List.map (fun (owner,_) -> string_of_owner owner)
943 print_binary_tree printer printer tree
948 (* Return the ownership structure. *)
951 let get_owners_lookup machine ownership (disk : block_device) =
952 (* Get the correct tree. *)
953 let tree = List.assoc (disk :> device) ownership in
956 (* Warning: This 'hot' code was carefully optimized based on
957 * feedback from 'gprof'. Avoid fiddling with it.
959 let rec query = function
960 | Leaf (_, segments) -> segments
962 (* Try to avoid expensive '@' operator if node segments is empty: *)
963 | Node ((Leaf ((_, leftend), _) | Node (_, ((_, leftend), _), _) as left),
967 if offset < leftend then query left else query right in
970 (* ... or a singleton: *)
971 | Node ((Leaf ((_, leftend), _) | Node (_, ((_, leftend), _), _) as left),
975 if offset < leftend then query left else query right in
976 segment :: subsegments
978 (* Normal recursive case: *)
979 | Node ((Leaf ((_, leftend), _) | Node (_, ((_, leftend), _), _) as left),
983 if offset < leftend then query left else query right in
984 segments @ subsegments
986 let owners = query tree in
989 fun (owner, owner_offset) -> (owner, offset -^ owner_offset)
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.
996 let offset_is_free owners =
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