From e1e5cfb926e886b8fc3126429d045b8ba305fe50 Mon Sep 17 00:00:00 2001 From: "Richard W.M. Jones" Date: Thu, 1 Jan 1970 00:00:00 +0000 Subject: [PATCH] Added #contiguous method to make block mapping more efficient, and renamed #mapblock -> #map_block for consistency. --- lib/diskimage.mli | 30 +++++++++++++++++++++++------- lib/diskimage_lvm2.ml | 29 +++++++++++++++++++++++------ lib/diskimage_utils.ml | 27 +++++++++++++++++---------- lib/diskimage_utils.mli | 12 ++++++++---- 4 files changed, 71 insertions(+), 27 deletions(-) diff --git a/lib/diskimage.mli b/lib/diskimage.mli index 9247551..b926193 100644 --- a/lib/diskimage.mli +++ b/lib/diskimage.mli @@ -34,6 +34,7 @@ class virtual device : object method virtual name : string (** Return some printable name for the device. *) + method virtual size : Int63.t (** Return the size of the device in bytes. @@ -44,15 +45,16 @@ class virtual device : (** [read offset len] reads len bytes starting at offset. Note: A default implementation is provided for [read], - but it is fairly inefficient because it uses {!mapblock} to + but it is fairly inefficient because it uses {!map_block} to map each block in the request. *) method read_bitstring : Int63.t -> Int63.t -> Bitmatch.bitstring (** [read_bitstring] is the same as [read] but returns a pa_bitmatch-style bitstring. *) + method virtual blocksize : Int63.t (** [blocksize] returns the natural block size of the device. *) - method virtual mapblock : Int63.t -> (device * Int63.t) list - (** [mapblock] describes how a block in this device is + method virtual map_block : Int63.t -> (device * Int63.t) list + (** [map_block] describes how a block in this device is mapped down to any underlying device(s). Returns [[]] (empty list) if there is no underlying @@ -62,13 +64,24 @@ class virtual device : Normally the returned list has length 1, but in cases such as mirroring you can have the same block mapped to several underlying devices. *) + + method virtual contiguous : Int63.t -> Int63.t + (** [contiguous offset] returns the number of contiguous + {i bytes} starting at byte [offset] on this device, + before (eg.) end of device or some discontinuity in + the mapping table occurs. + + This method and {!map_block} allow callers to determine how + high level blocks map to low level disk images efficiently + (complex striping and interleaving patterns can make the + process much less efficient however). *) end (** A virtual (or physical!) device, encapsulating any translation that has to be done to access the device. eg. For partitions there is a simple offset, but for LVM you may need complicated table lookups. - + Note this very rare use of OOP in OCaml! *) @@ -79,7 +92,8 @@ class block_device : string -> Int63.t -> method read : Int63.t -> Int63.t -> string method read_bitstring : Int63.t -> Int63.t -> Bitmatch.bitstring method blocksize : Int63.t - method mapblock : Int63.t -> (device * Int63.t) list + method map_block : Int63.t -> (device * Int63.t) list + method contiguous : Int63.t -> Int63.t method close : unit -> unit (** Close the device, freeing up the file descriptor. *) end @@ -96,7 +110,8 @@ class offset_device : string -> Int63.t -> Int63.t -> Int63.t -> device -> method read : Int63.t -> Int63.t -> string method read_bitstring : Int63.t -> Int63.t -> Bitmatch.bitstring method blocksize : Int63.t - method mapblock : Int63.t -> (device * Int63.t) list + method map_block : Int63.t -> (device * Int63.t) list + method contiguous : Int63.t -> Int63.t end (** A concrete device which maps a linear part of an underlying device. @@ -115,7 +130,8 @@ class blocksize_overlay : Int63.t -> device -> method read : Int63.t -> Int63.t -> string method read_bitstring : Int63.t -> Int63.t -> Bitmatch.bitstring method blocksize : Int63.t - method mapblock : Int63.t -> (device * Int63.t) list + method contiguous : Int63.t -> Int63.t + method map_block : Int63.t -> (device * Int63.t) list end (** Change the blocksize of an existing device. *) diff --git a/lib/diskimage_lvm2.ml b/lib/diskimage_lvm2.ml index ea127cb..4432e90 100644 --- a/lib/diskimage_lvm2.ml +++ b/lib/diskimage_lvm2.ml @@ -64,22 +64,39 @@ object (self) *) method blocksize = extent_size - (* Map block (extent) i to the underlying device. *) - method mapblock i = + method private map i = if i < ~^0 || i >= size_in_extents then invalid_arg "linear_map_device: read outside device"; let rec loop = function | [] -> - [] + None | (start_extent, end_extent, dev, pvoffset) :: rest -> - if start_extent <= i && i < end_extent then - [dev, (pvoffset +^ i) *^ extent_size] - else + if start_extent <= i && i < end_extent then ( + let dev_offset = (pvoffset +^ i) *^ extent_size in + Some (start_extent, end_extent, dev, dev_offset, pvoffset) + ) else loop rest in loop segments + (* Map block (extent) i to the underlying device. *) + method map_block i = + match self#map i with + | Some (_, _, dev, dev_offset, _) -> [dev, dev_offset] + | None -> [] + + (* Continguous span. *) + method contiguous offset = + let offset_in_extents = offset /^ extent_size in + + (* Get the segment that this offset lies in. *) + match self#map offset_in_extents with + | Some (_, end_extent, dev, dev_offset, _) -> + (* Contiguous bytes up to the end of this extent. *) + end_extent *^ extent_size -^ offset + | None -> ~^0 + (* NB. Use the superclass #read method. *) end diff --git a/lib/diskimage_utils.ml b/lib/diskimage_utils.ml index 4ad508d..80a7e3a 100644 --- a/lib/diskimage_utils.ml +++ b/lib/diskimage_utils.ml @@ -29,7 +29,8 @@ object (self) method virtual size : int63 method virtual name : string method virtual blocksize : int63 - method virtual mapblock : int63 -> (device * int63) list + method virtual map_block : int63 -> (device * int63) list + method virtual contiguous : Int63.t -> Int63.t (* Block-based read. Inefficient so normally overridden in subclasses. *) method read offset len = @@ -51,7 +52,7 @@ object (self) let not_mapped_error () = invalid_arg "device: read: block not mapped" in (* Copy the first block (partial). *) - (match self#mapblock first_blk with + (match self#map_block first_blk with | [] -> not_mapped_error () | (dev, base) :: _ -> let len = @@ -63,7 +64,7 @@ object (self) (* Copy the middle blocks. *) let rec loop blk = if blk < last_blk then ( - (match self#mapblock blk with + (match self#map_block blk with | [] -> not_mapped_error () | (dev, base) :: _ -> let str = dev#read ~^0 self#blocksize in @@ -76,7 +77,7 @@ object (self) (* Copy the last block (partial). *) if first_blk < last_blk then ( - match self#mapblock last_blk with + match self#map_block last_blk with | [] -> not_mapped_error () | (dev, base) :: _ -> let len = (offset +^ len) -^ last_blk *^ blocksize in @@ -109,7 +110,9 @@ object (self) method size = size method name = filename method blocksize = blocksize - method mapblock _ = [] + method map_block _ = [] + method contiguous offset = + size -^ offset method close () = close fd end @@ -128,7 +131,9 @@ object ); dev#read (start+^offset) len method blocksize = blocksize - method mapblock i = [dev, i *^ blocksize +^ start] + method map_block i = [dev, i *^ blocksize +^ start] + method contiguous offset = + size -^ offset end (* A device with just a modified block size. *) @@ -137,11 +142,12 @@ object inherit device method name = dev#name method size = dev#size - method read offset len = dev#read offset len + method read = dev#read method blocksize = new_blocksize - method mapblock new_blk = + method map_block new_blk = let orig_blk = new_blk *^ new_blocksize /^ dev#blocksize in - dev#mapblock orig_blk + dev#map_block orig_blk + method contiguous offset = dev#size -^ offset end (* The null device. Any attempt to read generates an error. *) @@ -152,7 +158,8 @@ object method size = ~^0 method name = "null" method blocksize = ~^1 - method mapblock _ = assert false + method map_block _ = assert false + method contiguous _ = ~^0 end type machine = { diff --git a/lib/diskimage_utils.mli b/lib/diskimage_utils.mli index 5e91520..641483d 100644 --- a/lib/diskimage_utils.mli +++ b/lib/diskimage_utils.mli @@ -29,7 +29,8 @@ class virtual device : method read : Int63.t -> Int63.t -> string method read_bitstring : Int63.t -> Int63.t -> Bitmatch.bitstring method virtual blocksize : Int63.t - method virtual mapblock : Int63.t -> (device * Int63.t) list + method virtual map_block : Int63.t -> (device * Int63.t) list + method virtual contiguous : Int63.t -> Int63.t end class block_device : string -> Int63.t -> @@ -39,7 +40,8 @@ class block_device : string -> Int63.t -> method read : Int63.t -> Int63.t -> string method read_bitstring : Int63.t -> Int63.t -> Bitmatch.bitstring method blocksize : Int63.t - method mapblock : Int63.t -> (device * Int63.t) list + method map_block : Int63.t -> (device * Int63.t) list + method contiguous : Int63.t -> Int63.t method close : unit -> unit end @@ -50,7 +52,8 @@ class offset_device : string -> Int63.t -> Int63.t -> Int63.t -> device -> method read : Int63.t -> Int63.t -> string method read_bitstring : Int63.t -> Int63.t -> Bitmatch.bitstring method blocksize : Int63.t - method mapblock : Int63.t -> (device * Int63.t) list + method map_block : Int63.t -> (device * Int63.t) list + method contiguous : Int63.t -> Int63.t end class blocksize_overlay : Int63.t -> device -> @@ -60,7 +63,8 @@ class blocksize_overlay : Int63.t -> device -> method read : Int63.t -> Int63.t -> string method read_bitstring : Int63.t -> Int63.t -> Bitmatch.bitstring method blocksize : Int63.t - method mapblock : Int63.t -> (device * Int63.t) list + method map_block : Int63.t -> (device * Int63.t) list + method contiguous : Int63.t -> Int63.t end val null_device : device -- 1.8.3.1