1 (* Diskimage library for reading disk images.
2 (C) Copyright 2007-2008 Richard W.M. Jones, Red Hat Inc.
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.
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.
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.
26 include Diskimage_utils
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.
31 let disk_block_size = ~^512
33 (*----------------------------------------------------------------------*)
35 let partition_types = [
36 Diskimage_mbr.plugin_id,
37 ("MBR", Diskimage_mbr.probe);
40 let filesystem_types = [
41 Diskimage_ext2.plugin_id,
42 ("Linux ext2/3", Diskimage_ext2.probe);
43 Diskimage_linux_swap.plugin_id,
44 ("Linux swap", Diskimage_linux_swap.probe);
45 Diskimage_linux_swsuspend.plugin_id,
46 ("Linux s/w suspend", Diskimage_linux_swsuspend.probe);
50 Diskimage_lvm2.plugin_id,
51 ("Linux LVM2", Diskimage_lvm2.probe, Diskimage_lvm2.list);
54 let name_of_parts id =
55 let name, _ = List.assoc id partition_types in
57 let name_of_filesystem id =
58 let name, _ = List.assoc id filesystem_types in
61 let name, _, _ = List.assoc id lvm_types in
64 (* Probe a device for partitions. Returns [Some parts] or [None]. *)
65 let probe_for_partitions dev =
66 if !debug then eprintf "probing for partitions on %s ...\n%!" dev#name;
67 let rec loop = function
69 | (parts_plugin_id, (_, probe_fn)) :: rest ->
70 try Some (probe_fn dev)
71 with Not_found -> loop rest
73 let r = loop partition_types in
76 | None -> eprintf "no partitions found on %s\n%!" dev#name
77 | Some { parts_plugin_id = name; parts = parts } ->
78 eprintf "found %d %s partitions on %s\n"
79 (List.length parts) name dev#name
83 (* Probe a device for a filesystem. Returns [Some fs] or [None]. *)
84 let probe_for_filesystem dev =
85 if !debug then eprintf "probing for a filesystem on %s ...\n%!" dev#name;
86 let rec loop = function
88 | (fs_name, (_, probe_fn)) :: rest ->
89 try Some (probe_fn dev)
90 with Not_found -> loop rest
92 let r = loop filesystem_types in
95 | None -> eprintf "no filesystem found on %s\n%!" dev#name
97 eprintf "found a filesystem on %s:\n" dev#name;
98 eprintf "\t%s\n%!" fs.fs_plugin_id
102 (* Probe a device for a PV. Returns [Some lvm_name] or [None]. *)
103 let probe_for_pv dev =
104 if !debug then eprintf "probing if %s is a PV ...\n%!" dev#name;
105 let rec loop = function
107 | (lvm_name, (_, probe_fn, _)) :: rest ->
108 try Some (probe_fn lvm_name dev)
109 with Not_found -> loop rest
111 let r = loop lvm_types in
114 | None -> eprintf "no PV found on %s\n%!" dev#name
115 | Some { lvm_plugin_id = name } ->
116 eprintf "%s contains a %s PV\n%!" dev#name name
120 let list_lvs lvm_name devs =
121 let _, _, list_lvs_fn = List.assoc lvm_name lvm_types in
124 (*----------------------------------------------------------------------*)
125 (* Create machine description. *)
126 let open_machine name disks =
127 let disks = List.map (
129 let dev = new block_device path disk_block_size (* XXX *) in
130 { d_name = name; d_dev = dev; d_content = `Unknown }
132 { m_name = name; m_disks = disks; m_lv_filesystems = [] }
134 let close_machine { m_disks = m_disks } =
135 (* Only close the disks, assume all other devices are derived from them. *)
136 List.iter (fun { d_dev = d_dev } -> d_dev#close ()) m_disks
138 (* Main scanning function for filesystems. *)
139 let scan_machine ({ m_disks = m_disks } as machine) =
140 let m_disks = List.map (
141 fun ({ d_dev = dev } as disk) ->
142 let dev = (dev :> device) in
143 (* See if it is partitioned first. *)
144 let parts = probe_for_partitions dev in
147 { disk with d_content = `Partitions parts }
149 (* Not partitioned. Does it contain a filesystem? *)
150 let fs = probe_for_filesystem dev in
153 { disk with d_content = `Filesystem fs }
155 (* Not partitioned, no filesystem, is it a PV? *)
156 let pv = probe_for_pv dev in
159 { disk with d_content = `PhysicalVolume lvm_name }
161 disk (* Spare/unknown. *)
164 (* Now we have either detected partitions or a filesystem on each
165 * physical device (or perhaps neither). See what is on those
168 let m_disks = List.map (
170 | ({ d_dev = dev; d_content = `Partitions parts } as disk) ->
173 if p.part_status = Bootable || p.part_status = Nonbootable then (
174 let fs = probe_for_filesystem p.part_dev in
177 { p with part_content = `Filesystem fs }
180 let pv = probe_for_pv p.part_dev in
183 { p with part_content = `PhysicalVolume lvm_name }
185 p (* Spare/unknown. *)
188 let parts = { parts with parts = ps } in
189 { disk with d_content = `Partitions parts }
193 (* LVM filesystem detection
195 * Look for all disks/partitions which have been identified as PVs
196 * and pass those back to the respective LVM plugin for LV detection.
198 * (Note - a two-stage process because an LV can be spread over
199 * several PVs, so we have to detect all PVs belonging to a
202 * XXX To deal with RAID (ie. md devices) we will need to loop
203 * around here because RAID is like LVM except that they normally
204 * present as block devices which can be used by LVM.
206 (* First: LV detection.
207 * Find all physical volumes, can be disks or partitions.
209 let pvs_on_disks = List.filter_map (
212 d_content = `PhysicalVolume pv } -> Some (pv, (d_dev :> device))
215 let pvs_on_partitions = List.map (
217 | { d_content = `Partitions { parts = parts } } ->
220 | { part_dev = part_dev;
221 part_content = `PhysicalVolume pv } ->
227 let lvs = List.concat (pvs_on_disks :: pvs_on_partitions) in
229 (* Second: filesystem on LV detection.
230 * Group the LVs by plug-in type.
232 let cmp (a,_) (b,_) = compare a b in
233 let lvs = List.sort ~cmp lvs in
234 let lvs = group_by lvs in
237 List.map (fun (pv, devs) -> list_lvs pv.lvm_plugin_id devs) lvs in
238 let lvs = List.concat lvs in
240 (* lvs is a list of potential LV devices. Now run them through the
241 * probes to see if any contain filesystems.
245 fun ({ lv_dev = dev } as lv) ->
246 match probe_for_filesystem dev with
247 | Some fs -> Some (lv, fs)
253 m_lv_filesystems = filesystems }
255 (*----------------------------------------------------------------------*)
257 (* We describe the ownership of each part of the disk using a
258 * segment tree. http://en.wikipedia.org/wiki/Segment_tree
260 * Note that each part can (and usually is) owned multiple times
261 * (eg. by a filesystem and by the partition that the filesystem
262 * lies inside). Also, the segment tree is effectively read-only.
263 * We build it up as a final step given the flat list of segments
264 * identified by the algorithm in 'iter_over_machine'.
267 type ownership = unit
269 (* List of owned segments before we build the segment tree. *)
270 type ownership_list =
271 (device * (* block_device (disk) *)
272 int63 * int63 * (* disk offset, size of segment *)
273 [ `Filesystem of filesystem
274 | `Partitions of partitions
275 | `PhysicalVolume of pv ] * (* owner *)
276 int63 (* owner offset *)
279 (* Ownership tables. *)
280 let create_ownership machine =
281 (* Iterate over all the things which can claim ownership of a
282 * disk block (filesystems, partitions, PVs).
284 let rec iter_over_machine
285 ({m_disks = disks; m_lv_filesystems = lv_filesystems} as machine) =
287 (* No segments to begin with. *)
288 let ownership = [] in
290 (* Iterate over disks. *)
295 | { d_content = (`Filesystem fs as owner) } ->
296 iter_over_filesystem machine ownership fs owner
297 | { d_content = (`Partitions parts as owner) } ->
298 iter_over_partitions machine ownership parts owner
299 | { d_content = (`PhysicalVolume pv as owner) } ->
300 iter_over_pv machine ownership pv owner
301 | { d_content = `Unknown } -> ownership
304 (* Iterate over LV filesystems. *)
307 fun ownership (lv, fs) ->
308 let owner = `Filesystem fs in
309 iter_over_filesystem machine ownership fs owner
310 ) ownership lv_filesystems in
314 (* Iterate over the blocks in a single filesystem. *)
315 and iter_over_filesystem machine ownership {fs_dev = dev} owner =
316 iter_over_device machine ownership dev owner
318 (* Iterate over the blocks in a set of partitions, then
319 * iterate over the contents of the partitions.
321 and iter_over_partitions machine ownership
322 {parts = parts; parts_dev = parts_dev} owner =
323 let ownership = iter_over_device machine ownership parts_dev owner in
329 | { part_content = (`Filesystem fs as owner) } ->
330 iter_over_filesystem machine ownership fs owner
331 | { part_content = (`PhysicalVolume pv as owner) } ->
332 iter_over_pv machine ownership pv owner
333 | { part_content = `Unknown } -> ownership
338 (* Iterate over the blocks in a PV. *)
339 and iter_over_pv machine ownership {pv_dev = dev} owner =
340 iter_over_device machine ownership dev owner
342 (* Iterate over the blocks in a device, assigning ownership to 'owner'
344 * In reality (1): There can be several owners for each block, so we
345 * incrementally add ownership to the ownership_list (which eventually
346 * will be turned into a segment tree).
347 * In reality (2): Iterating over blocks would take ages and result
348 * in a very inefficient ownership representation. Instead we look
349 * at minimum contiguous extents.
351 and iter_over_device { m_disks = disks } ownership dev owner =
352 let size = dev#size in
353 let disks = List.map (fun {d_dev = dev} -> (dev :> device)) disks in
355 let rec loop ownership offset =
356 if offset < size then (
357 let devs, extent = get_next_extent disks dev offset in
359 eprintf "warning: no device found under %s\n"
360 (string_of_owner owner);
363 fun ownership (disk, disk_offset) ->
364 let elem = disk, disk_offset, extent, owner, offset in
367 loop ownership (offset +^ extent)
373 (* Return the length of the next contiguous region in the device starting
374 * at the given byte offset. Also return the underlying block device(s)
377 and get_next_extent disks (dev : device) offset =
378 let this_extent = dev#contiguous offset in
380 (* If this disk is a block_device (a member of the 'disks' list)
381 * then we've hit the bottom layer of devices, so just return it.
383 if List.memq dev disks then
384 [dev, offset], this_extent
386 let blocksize = dev#blocksize in
387 let block = offset /^ blocksize in
388 let offset_in_block = offset -^ block *^ blocksize in
390 (* Map from this block to the devices one layer down. *)
391 let devs = dev#map_block block in
393 (* Get the real device offsets, adding the offset from start of block. *)
396 (fun (dev, dev_offset) -> dev, dev_offset +^ offset_in_block)
401 (fun (dev, dev_offset) ->
402 get_next_extent disks dev dev_offset)
405 (* Work out the minimum contiguous extent from this offset. *)
407 let extents = List.map snd devs in
408 let devs = List.concat (List.map fst devs) in
409 let extent = List.fold_left min this_extent extents in
415 and string_of_owner = function
416 | `Filesystem {fs_plugin_id = fs_plugin_id; fs_dev = fs_dev} ->
417 sprintf "%s(%s)" fs_dev#name fs_plugin_id
418 | `PhysicalVolume { pv_uuid = pv_uuid } ->
420 | `Partitions { parts_plugin_id = parts_plugin_id } ->
423 let ownership = iter_over_machine machine in
425 (* If debugging, print the segments that we found. *)
427 let ownership = List.rev ownership in
428 eprintf "ownership segment list of %s:\n" machine.m_name;
430 fun (disk, disk_offset, size, owner, owner_offset) ->
431 let blocksize = disk#blocksize in
432 let disk_offset_in_blocks, disk_offset_in_block =
433 disk_offset /^ blocksize, disk_offset %^ blocksize in
434 let size_in_blocks, size_in_block =
435 size /^ blocksize, size %^ blocksize in
437 eprintf "%s %s[%s:%s] %s[%s:%s] %s@%s\n"
439 (Int63.to_string disk_offset)
440 (Int63.to_string disk_offset_in_blocks)
441 (Int63.to_string disk_offset_in_block)
442 (Int63.to_string size)
443 (Int63.to_string size_in_blocks)
444 (Int63.to_string size_in_block)
445 (string_of_owner owner)
446 (Int63.to_string owner_offset)