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