From 66916209fa11b050af2f8b4ec184b26adf81d0a9 Mon Sep 17 00:00:00 2001 From: "Richard W.M. Jones" Date: Thu, 1 Jan 1970 00:00:00 +0000 Subject: [PATCH] Ownership using segment tree (not finished). --- lib/diskimage.ml | 191 +++++++++++++++++++++++++++++++++--------------------- lib/diskimage.mli | 6 +- 2 files changed, 122 insertions(+), 75 deletions(-) diff --git a/lib/diskimage.ml b/lib/diskimage.ml index 389358b..c5923cd 100644 --- a/lib/diskimage.ml +++ b/lib/diskimage.ml @@ -30,6 +30,8 @@ include Diskimage_utils *) let disk_block_size = ~^512 +(*----------------------------------------------------------------------*) +(* The plug-ins. *) let partition_types = [ Diskimage_mbr.plugin_id, ("MBR", Diskimage_mbr.probe); @@ -119,6 +121,7 @@ let list_lvs lvm_name devs = let _, _, list_lvs_fn = List.assoc lvm_name lvm_types in list_lvs_fn devs +(*----------------------------------------------------------------------*) (* Create machine description. *) let open_machine name disks = let disks = List.map ( @@ -249,93 +252,129 @@ let scan_machine ({ m_disks = m_disks } as machine) = m_disks = m_disks; m_lv_filesystems = filesystems } +(*----------------------------------------------------------------------*) + +(* We describe the ownership of each part of the disk using a + * segment tree. http://en.wikipedia.org/wiki/Segment_tree + * + * Note that each part can (and usually is) owned multiple times + * (eg. by a filesystem and by the partition that the filesystem + * lies inside). Also, the segment tree is effectively read-only. + * We build it up as a final step given the flat list of segments + * identified by the algorithm in 'iter_over_machine'. + *) + +type ownership = unit + +(* List of owned segments before we build the segment tree. *) +type ownership_list = + (device * (* block_device (disk) *) + int63 * int63 * (* disk offset, size of segment *) + [ `Filesystem of filesystem + | `Partitions of partitions + | `PhysicalVolume of pv ] * (* owner *) + int63 (* owner offset *) + ) list + (* Ownership tables. *) let create_ownership machine = (* Iterate over all the things which can claim ownership of a * disk block (filesystems, partitions, PVs). - * - * A single disk block can be "owned" by several things (eg. it - * could contain an LV filesystem, on a PV, on a partition). *) let rec iter_over_machine - {m_disks = disks; m_lv_filesystems = lv_filesystems} = - List.iter ( - function - | { d_content = (`Filesystem fs as owner) } -> - iter_over_filesystem disks fs owner - | { d_content = (`Partitions parts as owner) } -> - iter_over_partitions disks parts owner - | { d_content = (`PhysicalVolume pv as owner) } -> - iter_over_pv disks pv owner - | { d_content = `Unknown } -> () - ) disks; - List.iter ( - fun (lv, fs) -> - let owner = `Filesystem fs in - iter_over_filesystem disks fs owner - ) lv_filesystems + ({m_disks = disks; m_lv_filesystems = lv_filesystems} as machine) = + + (* No segments to begin with. *) + let ownership = [] in + + (* Iterate over disks. *) + let ownership = + List.fold_left ( + fun ownership -> + function + | { d_content = (`Filesystem fs as owner) } -> + iter_over_filesystem machine ownership fs owner + | { d_content = (`Partitions parts as owner) } -> + iter_over_partitions machine ownership parts owner + | { d_content = (`PhysicalVolume pv as owner) } -> + iter_over_pv machine ownership pv owner + | { d_content = `Unknown } -> ownership + ) ownership disks in + + (* Iterate over LV filesystems. *) + let ownership = + List.fold_left ( + fun ownership (lv, fs) -> + let owner = `Filesystem fs in + iter_over_filesystem machine ownership fs owner + ) ownership lv_filesystems in + + ownership (* Iterate over the blocks in a single filesystem. *) - and iter_over_filesystem disks {fs_dev = dev} owner = - iter_over_device disks dev owner + and iter_over_filesystem machine ownership {fs_dev = dev} owner = + iter_over_device machine ownership dev owner (* Iterate over the blocks in a set of partitions, then * iterate over the contents of the partitions. *) - and iter_over_partitions disks {parts = parts; parts_dev = parts_dev} owner = - iter_over_device disks parts_dev owner; + and iter_over_partitions machine ownership + {parts = parts; parts_dev = parts_dev} owner = + let ownership = iter_over_device machine ownership parts_dev owner in - List.iter ( - function - | { part_content = (`Filesystem fs as owner) } -> - iter_over_filesystem disks fs owner - | { part_content = (`PhysicalVolume pv as owner) } -> - iter_over_pv disks pv owner - | { part_content = `Unknown } -> () - ) parts + let ownership = + List.fold_left ( + fun ownership -> + function + | { part_content = (`Filesystem fs as owner) } -> + iter_over_filesystem machine ownership fs owner + | { part_content = (`PhysicalVolume pv as owner) } -> + iter_over_pv machine ownership pv owner + | { part_content = `Unknown } -> ownership + ) ownership parts in + + ownership (* Iterate over the blocks in a PV. *) - and iter_over_pv disks {pv_dev = dev} owner = - iter_over_device disks dev owner + and iter_over_pv machine ownership {pv_dev = dev} owner = + iter_over_device machine ownership dev owner (* Iterate over the blocks in a device, assigning ownership to 'owner' * * In reality (1): There can be several owners for each block, so we - * incrementally add ownership. The add_ownership function takes - * care of handling overlapping ranges, using an AVL tree. + * incrementally add ownership to the ownership_list (which eventually + * will be turned into a segment tree). * In reality (2): Iterating over blocks would take ages and result * in a very inefficient ownership representation. Instead we look * at minimum contiguous extents. *) - and iter_over_device disks dev owner = + and iter_over_device { m_disks = disks } ownership dev owner = let size = dev#size in + let disks = List.map (fun {d_dev = dev} -> (dev :> device)) disks in - let rec loop offset = + let rec loop ownership offset = if offset < size then ( - let extent = - let devs, extent = get_next_extent disks dev offset in - if devs = [] then - eprintf "warning: no device found under %s\n" - (string_of_owner owner); - List.iter ( - fun (dev, dev_offset) -> - add_ownership dev dev_offset extent owner - ) devs; - extent in - loop (offset +^ extent) + let devs, extent = get_next_extent disks dev offset in + if devs = [] then + eprintf "warning: no device found under %s\n" + (string_of_owner owner); + let ownership = + List.fold_left ( + fun ownership (disk, disk_offset) -> + let elem = disk, disk_offset, extent, owner, offset in + elem :: ownership + ) ownership devs in + loop ownership (offset +^ extent) ) + else ownership in - loop ~^0 + loop ownership ~^0 (* Return the length of the next contiguous region in the device starting * at the given byte offset. Also return the underlying block device(s) * if there is one. *) and get_next_extent disks (dev : device) offset = - let disks = List.map (fun { d_dev = dev } -> (dev :> device)) disks in - map_recursively disks dev offset - - and map_recursively disks dev offset = let this_extent = dev#contiguous offset in (* If this disk is a block_device (a member of the 'disks' list) @@ -360,7 +399,7 @@ let create_ownership machine = let devs = List.map (fun (dev, dev_offset) -> - map_recursively disks dev dev_offset) + get_next_extent disks dev dev_offset) devs in (* Work out the minimum contiguous extent from this offset. *) @@ -380,24 +419,30 @@ let create_ownership machine = "PV:" ^ pv_uuid | `Partitions { parts_plugin_id = parts_plugin_id } -> parts_plugin_id - - and add_ownership dev offset extent owner = - let blocksize = dev#blocksize in - let offset_in_blocks, offset_in_block = - offset /^ blocksize, offset %^ blocksize in - let extent_in_blocks, extent_in_block = - extent /^ blocksize, extent %^ blocksize in - - eprintf "add_ownership: %s %s[%s:%s] %s[%s:%s] %s\n" - dev#name - (Int63.to_string offset) - (Int63.to_string offset_in_blocks) - (Int63.to_string offset_in_block) - (Int63.to_string extent) - (Int63.to_string extent_in_blocks) - (Int63.to_string extent_in_block) - (string_of_owner owner) in - iter_over_machine machine - + let ownership = iter_over_machine machine in + (* If debugging, print the segments that we found. *) + if !debug then ( + let ownership = List.rev ownership in + eprintf "ownership segment list of %s:\n" machine.m_name; + List.iter ( + fun (disk, disk_offset, size, owner, owner_offset) -> + let blocksize = disk#blocksize in + let disk_offset_in_blocks, disk_offset_in_block = + disk_offset /^ blocksize, disk_offset %^ blocksize in + let size_in_blocks, size_in_block = + size /^ blocksize, size %^ blocksize in + + eprintf "%s %s[%s:%s] %s[%s:%s] %s@%s\n" + disk#name + (Int63.to_string disk_offset) + (Int63.to_string disk_offset_in_blocks) + (Int63.to_string disk_offset_in_block) + (Int63.to_string size) + (Int63.to_string size_in_blocks) + (Int63.to_string size_in_block) + (string_of_owner owner) + (Int63.to_string owner_offset) + ) ownership + ) diff --git a/lib/diskimage.mli b/lib/diskimage.mli index 0689a69..2373341 100644 --- a/lib/diskimage.mli +++ b/lib/diskimage.mli @@ -296,9 +296,11 @@ val scan_machine : machine -> machine (** {3 Create ownership tables} *) -val create_ownership : machine -> (*ownership*)unit +type ownership + +val create_ownership : machine -> ownership (** This creates the ownership tables (mapping disk blocks to the - ultimate filesystem, etc., which owns each). + ultimate filesystem, etc., which owns each one). *) (** {2 Debugging} *) -- 1.8.3.1