lib/diskimage_ntfs.ml

   1 (* 'df' command for virtual domains.
   2    (C) Copyright 2007 Richard W.M. Jones, Red Hat Inc.
   3    http://libvirt.org/
   4
   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.
   9
  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.
  14
  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.
  18
  19    Support for NTFS.
  20 *)
  21
  22 open Unix
  23 open Printf
  24
  25 open Diskimage_impl
  26 open Int63.Operators
  27
  28 (* Private data functions. *)
  29 let attach_private_data, get_private_data =
  30   private_data_functions (fun {fs_cb = {fs_cb_uq = u}} -> u)
  31
  32 let id = "ntfs"
  33
  34 let rec probe dev =
  35   let fs = probe_superblock dev in
  36   fs
  37
  38 and probe_superblock dev =
  39   (* Load the boot sector / superblock. *)
  40   let bits = dev#read_bitstring ~^0 ~^512 in
  41
  42   (* Most of this data comes from ntfsprogs' layout.h header file. *)
  43   bitmatch bits with
  44   | { _ : 24;                           (* Jump to boot up code. *)
  45       "NTFS    " : 64 : string;         (* NTFS OEM ID (magic). *)
  46       bytes_per_sector : 16 : littleendian;
  47       sectors_per_cluster : 8 : littleendian;
  48       _ : 16;                           (* Reserved sectors - unused. *)
  49       _ : 8;                            (* FATs - unused. *)
  50       _ : 16;                           (* Root entries - unused. *)
  51       _ : 16;                           (* Sectors - unused. *)
  52       _ : 8;                            (* Media type, probably 'f8' = HDD *)
  53       _ : 16;                           (* Sectors per FAT - unused. *)
  54       _ : 16;                           (* Sectors per track. *)
  55       _ : 16;                           (* Heads. *)
  56       _ : 32;                           (* Hidden sectors. *)
  57       _ : 32;                           (* Large sectors. *)
  58       _ : 8;                            (* Physical drive, 0 = FDD, 0x80 = HDD*)
  59       _ : 8;                            (* Current head. *)
  60       _ : 8;                            (* Extended boot signature. *)
  61       _ : 8;                            (* Reserved. *)
  62       number_of_sectors : 64 : littleendian;
  63       mft_lcn : 64 : littleendian;      (* MFT location in clusters. *)
  64       mftmirr_lcn : 64 : littleendian;  (* MFT mirror location. *)
  65       clusters_per_mft_record : 8;
  66       _ : 24;
  67       clusters_per_index_record : 8;
  68       _ : 24;
  69       volume_serial_number : 64 : littleendian;
  70       checksum : 32 : littleendian;     (* Boot sector checksum. *)
  71       code : 8 * 426 : bitstring;       (* Boot code. *)
  72       0x55AA : 16 } ->                  (* End of bootsector magic. *)
  73
  74       let blocksize = bytes_per_sector * sectors_per_cluster in
  75
  76       if !debug then
  77         eprintf "%s: NTFS boot sector with blocksize = %d, serial = %Lx\n%!"
  78           dev#name blocksize volume_serial_number;
  79
  80       let blocksize = Int63.of_int blocksize in
  81
  82       (* The blocksize of the filesystem is likely to be quite different
  83        * from that of the underlying device, so create an overlay device
  84        * with the natural filesystem blocksize.
  85        *)
  86       let fs_dev = new blocksize_overlay blocksize dev in
  87
  88       (* Get the location and size of the Master File Table. *)
  89       let mft_lcn = Int63.of_int64 mft_lcn *^ blocksize in
  90       let mft_size = Int63.of_int clusters_per_mft_record *^ blocksize in
  91
  92       let mft = parse_mft dev mft_lcn mft_size in
  93
  94       raise Not_found                   (* XXX *)
  95
  96   | { _ } -> raise Not_found            (* Not an NTFS boot sector. *)
  97
  98 and parse_mft dev mft_lcn mft_size =
  99   (* Read the whole of the MFT (which is an array of MFT records) ... *)
 100   let bits = dev#read_bitstring mft_lcn mft_size in
 101
 102   (* ... and turn the MFT into records. *)
 103   let records = parse_mft_records bits in
 104   records
 105
 106 and parse_mft_records bits =
 107   bitmatch bits with
 108   | { "FILE" : 32 : string;
 109       (* Assume 3 USAs starting at offset 0x30. XXX? *)
 110       0x30 : 16 : littleendian;
 111       0x03 : 16 : littleendian;
 112       _ : 64;                           (* lsn *)
 113       _ : 16;                           (* sequence_number *)
 114       _ : 16;                           (* link_count *)
 115       _ : 16;                           (* attrs_offset *)
 116       _ : 16;                           (* MFT_RECORD_FLAGS *)
 117       bytes_in_use : 32 : littleendian;
 118       record_size : 32 : littleendian;
 119       _ : 64;                           (* base_mft_record *)
 120       _ : 16;                           (* next_attr_instance *)
 121       _ : 16;                           (* reserved *)
 122       _ : 32;                           (* mft_record_number *)
 123       _ : 64;                           (* USN, 3 * USAs -- see above. *)
 124
 125       (* The attributes.  Subtract header size (0x30 bytes)
 126        * and space for the USN/USAs (8 bytes).
 127        *)
 128       attrs : (Int32.to_int record_size - 0x30 - 8)*8 : bitstring;
 129
 130       (* Subsequent MFT records: *)
 131       rest : -1 : bitstring } ->
 132
 133       if !debug then
 134         eprintf "got an MFT record, now parsing attributes ...\n%!";
 135
 136       let attrs = parse_attrs attrs in
 137
 138       parse_mft_records rest            (* loop rest of MFT records *)
 139
 140   (* Just assume that the end of the list of MFT records
 141    * is marked by all zeroes.  This seems to be the
 142    * case, but not sure if it is generally true.
 143    * XXX?
 144    *)
 145   | { 0x00000000_l : 32 } ->
 146       ()
 147
 148   | { _ } -> ()
 149
 150 and parse_attrs attrs =
 151   (* Parse the MFT record attributes. *)
 152   bitmatch attrs with
 153   | { 0xFFFFFFFF_l : 32 : littleendian } -> (* AT_END *)
 154       if !debug then
 155         eprintf "found AT_END, end of attributes\n%!";
 156       ()
 157
 158   | { attr_type : 32 : littleendian;
 159       attr_size : 32 : littleendian;
 160       0 : 8;                         (* means attribute is resident *)
 161       pad : 24*8 - 8 - 64 : bitstring; (* actually meaningful *)
 162       attr : (Int32.to_int attr_size - 24) * 8 : bitstring;
 163       rest : -1 : bitstring } ->
 164
 165       (* XXX let attr = *) parse_resident_attr attr_type attr;
 166       parse_attrs rest
 167
 168   | { attr_type : 32 : littleendian;
 169       attr_size : 32 : littleendian;
 170       1 : 8;                            (* non-resident attribute *)
 171       0 : 8;                            (* name length, assume unnamed *)
 172       _ : 16;                           (* name offset *)
 173       _ : 16;                           (* flags *)
 174       _ : 16;                           (* instance number *)
 175       0L : 64 : littleendian;           (* lowest VCN, assume single extent *)
 176       highest_vcn : 64 : littleendian;  (* size in clusters - 1 *)
 177       0x40 : 16 : littleendian;         (* mapping pairs offset *)
 178       0 : 8;                            (* assume not compressed *)
 179       pad : 40 : bitstring;             (* padding *)
 180       allocated_size : 64 : littleendian; (* allocate size on disk *)
 181       data_size : 64 : littleendian;      (* byte size of the attribute *)
 182       initialized_size : 64 : littleendian;
 183
 184       (* Table of virtual clusters to logical clusters. *)
 185       mapping_pairs : (Int32.to_int attr_size - 0x40) * 8 : bitstring;
 186
 187       rest : -1 : bitstring } ->
 188
 189       (* XXX let attr = *)
 190       parse_nonresident_attr attr_type highest_vcn
 191         allocated_size data_size initialized_size
 192         mapping_pairs;
 193
 194       parse_attrs rest
 195
 196   (* Not matched above, so we don't know how to parse this attribute, but
 197    * there is still enough information to skip to the next one.
 198    *)
 199   | { attr_type : 32 : littleendian;
 200       attr_size : 32 : littleendian;
 201       pad : (Int32.to_int attr_size - 8) * 8 : bitstring;
 202       rest : -1 : bitstring } ->
 203
 204       if !debug then (
 205         eprintf "cannot parse MFT attribute entry\n%!";
 206         Bitmatch.hexdump_bitstring Pervasives.stderr attrs
 207       );
 208
 209       parse_attrs rest
 210
 211   (* Otherwise unparsable & unskippable attribute entry. *)
 212   | { _ } ->
 213       if !debug then
 214         eprintf "corrupt MFT attribute entry\n%!"
 215
 216 and parse_resident_attr attr_type attr =
 217   match attr_type with
 218   | 0x10_l ->                           (* AT_STANDARD_INFORMATION *)
 219       (bitmatch attr with
 220        | { creation_time : 64;
 221            last_data_change_time : 64;
 222            last_mft_change_time : 64;
 223            last_access_time : 64
 224            (* other stuff follows, just ignore it *) } ->
 225            if !debug then
 226              eprintf "creation time: %Lx, last_access_time: %Lx\n"
 227                creation_time last_access_time
 228
 229        | { _ } ->
 230            if !debug then
 231              eprintf "cannot parse AT_STANDARD_INFORMATION\n%!"
 232       );
 233
 234   | 0x30_l ->                           (* AT_FILE_NAME *)
 235       (bitmatch attr with
 236        | { _ : 64;                      (* parent directory ref *)
 237            _ : 64;                      (* creation time *)
 238            _ : 64;                      (* last change time *)
 239            _ : 64;                      (* last MFT change time *)
 240            _ : 64;                      (* last access time *)
 241            allocated_size : 64 : littleendian;
 242            data_size : 64 : littleendian;
 243            _ : 32;
 244            _ : 32;
 245            name_len : 8;
 246            name_type_flags : 8;
 247            name : name_len*16 : string } ->
 248
 249            let name = ucs2_to_utf8 name name_len in
 250            if !debug then
 251              eprintf "filename: %s (size: %Ld bytes)\n" name data_size
 252
 253        | { _ } ->
 254            if !debug then
 255              eprintf "cannot parse AT_FILE_NAME\n%!"
 256       );
 257
 258   | _ ->                                (* unknown attribute - just ignore *)
 259       if !debug then
 260         eprintf "unknown resident attribute %lx\n%!" attr_type
 261
 262 and parse_nonresident_attr attr_type highest_vcn
 263     allocated_size data_size initialized_size
 264     mapping_pairs =
 265   match attr_type with
 266   | 0x80_l ->                           (* AT_DATA, ie. the $Data stream *)
 267       if !debug then (
 268         eprintf "AT_DATA: size = %Ld bytes, highest_vcn = 0x%Lx\n"
 269           data_size highest_vcn;
 270         Bitmatch.hexdump_bitstring Pervasives.stderr mapping_pairs
 271       );
 272
 273       let lowest_vcn = ~^0 (* see assumption above *) in
 274       let runlist = parse_runlist lowest_vcn ~^0 mapping_pairs in
 275       if !debug then (
 276         eprintf "AT_DATA: runlist is:\n";
 277         List.iter (
 278           function
 279           | ((vcn, deltavcn), Some lcn) ->
 280             eprintf "\tVCNs %s..%s -> LCN %s\n"
 281               (Int63.to_string vcn) (Int63.to_string (vcn +^ deltavcn -^ ~^1))
 282               (Int63.to_string lcn)
 283           | ((vcn, deltavcn), None) ->
 284             eprintf "\tVCNs %s..%s -> sparse hole\n"
 285               (Int63.to_string vcn) (Int63.to_string (vcn +^ deltavcn -^ ~^1))
 286         ) runlist
 287       );
 288
 289   | _ ->
 290       if !debug then
 291         eprintf "unknown non-resident attribute %lx\n%!" attr_type
 292
 293 (* mapping_pairs is not straightforward and not documented well.  See
 294  * ntfsprogs libntfs/runlist.c:ntfs_mapping_pairs_decompress
 295  *)
 296 and parse_runlist vcn lcn bits =
 297   bitmatch bits with
 298   | { 0 : 8 } ->                        (* end of table *)
 299       []
 300
 301   | { 0 : 4;
 302       vcnlen : 4;
 303       deltavcn : vcnlen * 8 : littleendian;
 304       rest : -1 : bitstring
 305     } when vcnlen >= 1 && vcnlen <= 4 ->
 306
 307       let deltavcn = Int63.of_int64 deltavcn in
 308
 309       (* This is a sparse file hole. *)
 310       ((vcn, deltavcn), None) ::
 311         parse_runlist (vcn +^ deltavcn) lcn rest
 312
 313   | { (* Really these fields are signed, but we'll just limit it to
 314        * sensible values in the when clause instead.
 315        *)
 316       lcnlen : 4;
 317       vcnlen : 4;
 318       deltavcn : vcnlen * 8 : littleendian;
 319       deltalcn : lcnlen * 8 : littleendian;
 320       rest : -1 : bitstring
 321     } when (vcnlen >= 1 && vcnlen <= 4) && (lcnlen >= 1 || lcnlen <= 4) ->
 322
 323       let deltavcn = Int63.of_int64 deltavcn in
 324       let deltalcn = Int63.of_int64 deltalcn in (* XXX signed *)
 325
 326       let lcn = lcn +^ deltalcn in
 327
 328       eprintf "lcnlen = %d, vcnlen = %d\n" lcnlen vcnlen;
 329
 330       ((vcn, deltavcn), Some lcn) ::
 331         parse_runlist (vcn +^ deltavcn) lcn rest
 332
 333   | { _ } ->
 334       if !debug then (
 335         eprintf "unknown field in the runlist\n%!";
 336         Bitmatch.hexdump_bitstring Pervasives.stderr bits
 337       );
 338       []
 339
 340 (* Poor man's little-endian UCS-2 to UTF-8 conversion.
 341  * XXX Should use Camomile.
 342  *)
 343 and ucs2_to_utf8 name len =
 344   (* Calculate length of final string. *)
 345   let outlen = ref 0 in
 346   let j = ref 0 in
 347   for i = 0 to len-1 do
 348     let j' = !j in
 349     j := j' + 2;
 350     let c0 = Char.code name.[j'] and c1 = Char.code name.[j'+1] in
 351     let c = c0 + c1 * 256 in
 352     if c < 128 then incr outlen
 353     else if c < 0x800 then outlen := !outlen + 2
 354     else outlen := !outlen + 3
 355   done;
 356   let outstr = String.create !outlen in
 357   j := 0; outlen := 0;
 358   for i = 0 to len-1 do
 359     let j' = !j in
 360     j := j' + 2;
 361     let c0 = Char.code name.[j'] and c1 = Char.code name.[j'+1] in
 362     let c = c0 + c1 * 256 in
 363     if c < 128 then (
 364       outstr.[!outlen] <- Char.chr c;
 365       incr outlen
 366     ) else if c < 0x800 then (
 367       outstr.[!outlen] <- Char.chr (0b11000000 lor (c lsr 6));
 368       outstr.[!outlen+1] <- Char.chr (0b10000000 lor (c land 0b00111111));
 369       outlen := !outlen + 2
 370     ) else (
 371       outstr.[!outlen] <- Char.chr (0b11100000 lor (c lsr 12));
 372       outstr.[!outlen+1] <- Char.chr (0b10000000 lor ((c lsr 6) lor 0b00111111));
 373       outstr.[!outlen+2] <- Char.chr (0b10000000 lor (c land 0b00111111));
 374       outlen := !outlen + 3
 375     )
 376   done;
 377   outstr
 378
 379 and offset_is_free _ _ = false
 380
 381 and callbacks =
 382   let i = ref 0 in
 383   fun () -> {
 384     fs_cb_uq = (incr i; !i);
 385     fs_cb_name = id;
 386     fs_cb_printable_name = "Windows NTFS";
 387     fs_cb_offset_is_free = offset_is_free;
 388   }
 389
 390 (* Register the plugin. *)
 391 let () = register_plugin ~filesystem:probe id