fs/hpfs/hpfs.h

   1 /*
   2  *  linux/fs/hpfs/hpfs.h
   3  *
   4  *  HPFS structures by Chris Smith, 1993
   5  *
   6  *  a little bit modified by Mikulas Patocka, 1998-1999
   7  */
   8
   9 /* The paper
  10
  11      Duncan, Roy
  12      Design goals and implementation of the new High Performance File System
  13      Microsoft Systems Journal  Sept 1989  v4 n5 p1(13)
  14
  15    describes what HPFS looked like when it was new, and it is the source
  16    of most of the information given here.  The rest is conjecture.
  17
  18    For definitive information on the Duncan paper, see it, not this file.
  19    For definitive information on HPFS, ask somebody else -- this is guesswork.
  20    There are certain to be many mistakes. */
  21
  22 /* Notation */
  23
  24 typedef u32 secno;                      /* sector number, partition relative */
  25
  26 typedef secno dnode_secno;              /* sector number of a dnode */
  27 typedef secno fnode_secno;              /* sector number of an fnode */
  28 typedef secno anode_secno;              /* sector number of an anode */
  29
  30 typedef u32 time32_t;           /* 32-bit time_t type */
  31
  32 /* sector 0 */
  33
  34 /* The boot block is very like a FAT boot block, except that the
  35    29h signature byte is 28h instead, and the ID string is "HPFS". */
  36
  37 #define BB_MAGIC 0xaa55
  38
  39 struct hpfs_boot_block
  40 {
  41   u8 jmp[3];
  42   u8 oem_id[8];
  43   u8 bytes_per_sector[2];       /* 512 */
  44   u8 sectors_per_cluster;
  45   u8 n_reserved_sectors[2];
  46   u8 n_fats;
  47   u8 n_rootdir_entries[2];
  48   u8 n_sectors_s[2];
  49   u8 media_byte;
  50   u16 sectors_per_fat;
  51   u16 sectors_per_track;
  52   u16 heads_per_cyl;
  53   u32 n_hidden_sectors;
  54   u32 n_sectors_l;              /* size of partition */
  55   u8 drive_number;
  56   u8 mbz;
  57   u8 sig_28h;                   /* 28h */
  58   u8 vol_serno[4];
  59   u8 vol_label[11];
  60   u8 sig_hpfs[8];               /* "HPFS    " */
  61   u8 pad[448];
  62   u16 magic;                    /* aa55 */
  63 };
  64
  65
  66 /* sector 16 */
  67
  68 /* The super block has the pointer to the root directory. */
  69
  70 #define SB_MAGIC 0xf995e849
  71
  72 struct hpfs_super_block
  73 {
  74   u32 magic;                            /* f995 e849 */
  75   u32 magic1;                           /* fa53 e9c5, more magic? */
  76   u8 version;                           /* version of a filesystem  usually 2 */
  77   u8 funcversion;                       /* functional version - oldest version
  78                                            of filesystem that can understand
  79                                            this disk */
  80   u16 zero;                             /* 0 */
  81   fnode_secno root;                     /* fnode of root directory */
  82   secno n_sectors;                      /* size of filesystem */
  83   u32 n_badblocks;                      /* number of bad blocks */
  84   secno bitmaps;                        /* pointers to free space bit maps */
  85   u32 zero1;                            /* 0 */
  86   secno badblocks;                      /* bad block list */
  87   u32 zero3;                            /* 0 */
  88   time32_t last_chkdsk;                 /* date last checked, 0 if never */
  89   /*u32 zero4;*/                        /* 0 */
  90   time32_t last_optimize;               /* date last optimized, 0 if never */
  91   secno n_dir_band;                     /* number of sectors in dir band */
  92   secno dir_band_start;                 /* first sector in dir band */
  93   secno dir_band_end;                   /* last sector in dir band */
  94   secno dir_band_bitmap;                /* free space map, 1 dnode per bit */
  95   u8 volume_name[32];                   /* not used */
  96   secno user_id_table;                  /* 8 preallocated sectors - user id */
  97   u32 zero6[103];                       /* 0 */
  98 };
  99
 100
 101 /* sector 17 */
 102
 103 /* The spare block has pointers to spare sectors.  */
 104
 105 #define SP_MAGIC 0xf9911849
 106
 107 struct hpfs_spare_block
 108 {
 109   u32 magic;                            /* f991 1849 */
 110   u32 magic1;                           /* fa52 29c5, more magic? */
 111
 112   unsigned dirty: 1;                    /* 0 clean, 1 "improperly stopped" */
 113   unsigned sparedir_used: 1;            /* spare dirblks used */
 114   unsigned hotfixes_used: 1;            /* hotfixes used */
 115   unsigned bad_sector: 1;               /* bad sector, corrupted disk (???) */
 116   unsigned bad_bitmap: 1;               /* bad bitmap */
 117   unsigned fast: 1;                     /* partition was fast formatted */
 118   unsigned old_wrote: 1;                /* old version wrote to partion */
 119   unsigned old_wrote_1: 1;              /* old version wrote to partion (?) */
 120   unsigned install_dasd_limits: 1;      /* HPFS386 flags */
 121   unsigned resynch_dasd_limits: 1;
 122   unsigned dasd_limits_operational: 1;
 123   unsigned multimedia_active: 1;
 124   unsigned dce_acls_active: 1;
 125   unsigned dasd_limits_dirty: 1;
 126   unsigned flag67: 2;
 127   u8 mm_contlgulty;
 128   u8 unused;
 129
 130   secno hotfix_map;                     /* info about remapped bad sectors */
 131   u32 n_spares_used;                    /* number of hotfixes */
 132   u32 n_spares;                         /* number of spares in hotfix map */
 133   u32 n_dnode_spares_free;              /* spare dnodes unused */
 134   u32 n_dnode_spares;                   /* length of spare_dnodes[] list,
 135                                            follows in this block*/
 136   secno code_page_dir;                  /* code page directory block */
 137   u32 n_code_pages;                     /* number of code pages */
 138   u32 super_crc;                        /* on HPFS386 and LAN Server this is
 139                                            checksum of superblock, on normal
 140                                            OS/2 unused */
 141   u32 spare_crc;                        /* on HPFS386 checksum of spareblock */
 142   u32 zero1[15];                        /* unused */
 143   dnode_secno spare_dnodes[100];        /* emergency free dnode list */
 144   u32 zero2[1];                         /* room for more? */
 145 };
 146
 147 /* The bad block list is 4 sectors long.  The first word must be zero,
 148    the remaining words give n_badblocks bad block numbers.
 149    I bet you can see it coming... */
 150
 151 #define BAD_MAGIC 0
 152
 153 /* The hotfix map is 4 sectors long.  It looks like
 154
 155        secno from[n_spares];
 156        secno to[n_spares];
 157
 158    The to[] list is initialized to point to n_spares preallocated empty
 159    sectors.  The from[] list contains the sector numbers of bad blocks
 160    which have been remapped to corresponding sectors in the to[] list.
 161    n_spares_used gives the length of the from[] list. */
 162
 163
 164 /* Sectors 18 and 19 are preallocated and unused.
 165    Maybe they're spares for 16 and 17, but simple substitution fails. */
 166
 167
 168 /* The code page info pointed to by the spare block consists of an index
 169    block and blocks containing uppercasing tables.  I don't know what
 170    these are for (CHKDSK, maybe?) -- OS/2 does not seem to use them
 171    itself.  Linux doesn't use them either. */
 172
 173 /* block pointed to by spareblock->code_page_dir */
 174
 175 #define CP_DIR_MAGIC 0x494521f7
 176
 177 struct code_page_directory
 178 {
 179   u32 magic;                            /* 4945 21f7 */
 180   u32 n_code_pages;                     /* number of pointers following */
 181   u32 zero1[2];
 182   struct {
 183     u16 ix;                             /* index */
 184     u16 code_page_number;               /* code page number */
 185     u32 bounds;                         /* matches corresponding word
 186                                            in data block */
 187     secno code_page_data;               /* sector number of a code_page_data
 188                                            containing c.p. array */
 189     u16 index;                          /* index in c.p. array in that sector*/
 190     u16 unknown;                        /* some unknown value; usually 0;
 191                                            2 in Japanese version */
 192   } array[31];                          /* unknown length */
 193 };
 194
 195 /* blocks pointed to by code_page_directory */
 196
 197 #define CP_DATA_MAGIC 0x894521f7
 198
 199 struct code_page_data
 200 {
 201   u32 magic;                            /* 8945 21f7 */
 202   u32 n_used;                           /* # elements used in c_p_data[] */
 203   u32 bounds[3];                        /* looks a bit like
 204                                              (beg1,end1), (beg2,end2)
 205                                            one byte each */
 206   u16 offs[3];                          /* offsets from start of sector
 207                                            to start of c_p_data[ix] */
 208   struct {
 209     u16 ix;                             /* index */
 210     u16 code_page_number;               /* code page number */
 211     u16 unknown;                        /* the same as in cp directory */
 212     u8 map[128];                        /* upcase table for chars 80..ff */
 213     u16 zero2;
 214   } code_page[3];
 215   u8 incognita[78];
 216 };
 217
 218
 219 /* Free space bitmaps are 4 sectors long, which is 16384 bits.
 220    16384 sectors is 8 meg, and each 8 meg band has a 4-sector bitmap.
 221    Bit order in the maps is little-endian.  0 means taken, 1 means free.
 222
 223    Bit map sectors are marked allocated in the bit maps, and so are sectors
 224    off the end of the partition.
 225
 226    Band 0 is sectors 0-3fff, its map is in sectors 18-1b.
 227    Band 1 is 4000-7fff, its map is in 7ffc-7fff.
 228    Band 2 is 8000-ffff, its map is in 8000-8003.
 229    The remaining bands have maps in their first (even) or last (odd) 4 sectors
 230      -- if the last, partial, band is odd its map is in its last 4 sectors.
 231
 232    The bitmap locations are given in a table pointed to by the super block.
 233    No doubt they aren't constrained to be at 18, 7ffc, 8000, ...; that is
 234    just where they usually are.
 235
 236    The "directory band" is a bunch of sectors preallocated for dnodes.
 237    It has a 4-sector free space bitmap of its own.  Each bit in the map
 238    corresponds to one 4-sector dnode, bit 0 of the map corresponding to
 239    the first 4 sectors of the directory band.  The entire band is marked
 240    allocated in the main bitmap.   The super block gives the locations
 241    of the directory band and its bitmap.  ("band" doesn't mean it is
 242    8 meg long; it isn't.)  */
 243
 244
 245 /* dnode: directory.  4 sectors long */
 246
 247 /* A directory is a tree of dnodes.  The fnode for a directory
 248    contains one pointer, to the root dnode of the tree.  The fnode
 249    never moves, the dnodes do the B-tree thing, splitting and merging
 250    as files are added and removed.  */
 251
 252 #define DNODE_MAGIC   0x77e40aae
 253
 254 struct dnode {
 255   u32 magic;                            /* 77e4 0aae */
 256   u32 first_free;                       /* offset from start of dnode to
 257                                            first free dir entry */
 258   unsigned root_dnode:1;                /* Is it root dnode? */
 259   unsigned increment_me:31;             /* some kind of activity counter?
 260                                            Neither HPFS.IFS nor CHKDSK cares
 261                                            if you change this word */
 262   secno up;                             /* (root dnode) directory's fnode
 263                                            (nonroot) parent dnode */
 264   dnode_secno self;                     /* pointer to this dnode */
 265   u8 dirent[2028];                      /* one or more dirents */
 266 };
 267
 268 struct hpfs_dirent {
 269   u16 length;                   /* offset to next dirent */
 270   unsigned first: 1;                    /* set on phony ^A^A (".") entry */
 271   unsigned has_acl: 1;
 272   unsigned down: 1;                     /* down pointer present (after name) */
 273   unsigned last: 1;                     /* set on phony \377 entry */
 274   unsigned has_ea: 1;                   /* entry has EA */
 275   unsigned has_xtd_perm: 1;             /* has extended perm list (???) */
 276   unsigned has_explicit_acl: 1;
 277   unsigned has_needea: 1;               /* ?? some EA has NEEDEA set
 278                                            I have no idea why this is
 279                                            interesting in a dir entry */
 280   unsigned read_only: 1;                /* dos attrib */
 281   unsigned hidden: 1;                   /* dos attrib */
 282   unsigned system: 1;                   /* dos attrib */
 283   unsigned flag11: 1;                   /* would be volume label dos attrib */
 284   unsigned directory: 1;                /* dos attrib */
 285   unsigned archive: 1;                  /* dos attrib */
 286   unsigned not_8x3: 1;                  /* name is not 8.3 */
 287   unsigned flag15: 1;
 288   fnode_secno fnode;                    /* fnode giving allocation info */
 289   time32_t write_date;                  /* mtime */
 290   u32 file_size;                        /* file length, bytes */
 291   time32_t read_date;                   /* atime */
 292   time32_t creation_date;                       /* ctime */
 293   u32 ea_size;                          /* total EA length, bytes */
 294   unsigned char no_of_acls : 3;         /* number of ACL's */
 295   unsigned char reserver : 5;
 296   u8 ix;                                /* code page index (of filename), see
 297                                            struct code_page_data */
 298   u8 namelen, name[1];                  /* file name */
 299   /* dnode_secno down;    btree down pointer, if present,
 300                           follows name on next word boundary, or maybe it
 301                           precedes next dirent, which is on a word boundary. */
 302 };
 303
 304
 305 /* B+ tree: allocation info in fnodes and anodes */
 306
 307 /* dnodes point to fnodes which are responsible for listing the sectors
 308    assigned to the file.  This is done with trees of (length,address)
 309    pairs.  (Actually triples, of (length, file-address, disk-address)
 310    which can represent holes.  Find out if HPFS does that.)
 311    At any rate, fnodes contain a small tree; if subtrees are needed
 312    they occupy essentially a full block in anodes.  A leaf-level tree node
 313    has 3-word entries giving sector runs, a non-leaf node has 2-word
 314    entries giving subtree pointers.  A flag in the header says which. */
 315
 316 struct bplus_leaf_node
 317 {
 318   u32 file_secno;                       /* first file sector in extent */
 319   u32 length;                           /* length, sectors */
 320   secno disk_secno;                     /* first corresponding disk sector */
 321 };
 322
 323 struct bplus_internal_node
 324 {
 325   u32 file_secno;                       /* subtree maps sectors < this  */
 326   anode_secno down;                     /* pointer to subtree */
 327 };
 328
 329 struct bplus_header
 330 {
 331   unsigned hbff: 1;     /* high bit of first free entry offset */
 332   unsigned flag1: 1;
 333   unsigned flag2: 1;
 334   unsigned flag3: 1;
 335   unsigned flag4: 1;
 336   unsigned fnode_parent: 1;             /* ? we're pointed to by an fnode,
 337                                            the data btree or some ea or the
 338                                            main ea bootage pointer ea_secno */
 339                                         /* also can get set in fnodes, which
 340                                            may be a chkdsk glitch or may mean
 341                                            this bit is irrelevant in fnodes,
 342                                            or this interpretation is all wet */
 343   unsigned binary_search: 1;            /* suggest binary search (unused) */
 344   unsigned internal: 1;                 /* 1 -> (internal) tree of anodes
 345                                            0 -> (leaf) list of extents */
 346   u8 fill[3];
 347   u8 n_free_nodes;                      /* free nodes in following array */
 348   u8 n_used_nodes;                      /* used nodes in following array */
 349   u16 first_free;                       /* offset from start of header to
 350                                            first free node in array */
 351   union {
 352     struct bplus_internal_node internal[0]; /* (internal) 2-word entries giving
 353                                                subtree pointers */
 354     struct bplus_leaf_node external[0];     /* (external) 3-word entries giving
 355                                                sector runs */
 356   } u;
 357 };
 358
 359 /* fnode: root of allocation b+ tree, and EA's */
 360
 361 /* Every file and every directory has one fnode, pointed to by the directory
 362    entry and pointing to the file's sectors or directory's root dnode.  EA's
 363    are also stored here, and there are said to be ACL's somewhere here too. */
 364
 365 #define FNODE_MAGIC 0xf7e40aae
 366
 367 struct fnode
 368 {
 369   u32 magic;                            /* f7e4 0aae */
 370   u32 zero1[2];                         /* read history */
 371   u8 len, name[15];                     /* true length, truncated name */
 372   fnode_secno up;                       /* pointer to file's directory fnode */
 373   secno acl_size_l;
 374   secno acl_secno;
 375   u16 acl_size_s;
 376   u8 acl_anode;
 377   u8 zero2;                             /* history bit count */
 378   u32 ea_size_l;                        /* length of disk-resident ea's */
 379   secno ea_secno;                       /* first sector of disk-resident ea's*/
 380   u16 ea_size_s;                        /* length of fnode-resident ea's */
 381
 382   unsigned flag0: 1;
 383   unsigned ea_anode: 1;                 /* 1 -> ea_secno is an anode */
 384   unsigned flag2: 1;
 385   unsigned flag3: 1;
 386   unsigned flag4: 1;
 387   unsigned flag5: 1;
 388   unsigned flag6: 1;
 389   unsigned flag7: 1;
 390   unsigned dirflag: 1;                  /* 1 -> directory.  first & only extent
 391                                            points to dnode. */
 392   unsigned flag9: 1;
 393   unsigned flag10: 1;
 394   unsigned flag11: 1;
 395   unsigned flag12: 1;
 396   unsigned flag13: 1;
 397   unsigned flag14: 1;
 398   unsigned flag15: 1;
 399
 400   struct bplus_header btree;            /* b+ tree, 8 extents or 12 subtrees */
 401   union {
 402     struct bplus_leaf_node external[8];
 403     struct bplus_internal_node internal[12];
 404   } u;
 405
 406   u32 file_size;                        /* file length, bytes */
 407   u32 n_needea;                         /* number of EA's with NEEDEA set */
 408   u8 user_id[16];                       /* unused */
 409   u16 ea_offs;                          /* offset from start of fnode
 410                                            to first fnode-resident ea */
 411   u8 dasd_limit_treshhold;
 412   u8 dasd_limit_delta;
 413   u32 dasd_limit;
 414   u32 dasd_usage;
 415   u8 ea[316];                           /* zero or more EA's, packed together
 416                                            with no alignment padding.
 417                                            (Do not use this name, get here
 418                                            via fnode + ea_offs. I think.) */
 419 };
 420
 421
 422 /* anode: 99.44% pure allocation tree */
 423
 424 #define ANODE_MAGIC 0x37e40aae
 425
 426 struct anode
 427 {
 428   u32 magic;                            /* 37e4 0aae */
 429   anode_secno self;                     /* pointer to this anode */
 430   secno up;                             /* parent anode or fnode */
 431
 432   struct bplus_header btree;            /* b+tree, 40 extents or 60 subtrees */
 433   union {
 434     struct bplus_leaf_node external[40];
 435     struct bplus_internal_node internal[60];
 436   } u;
 437
 438   u32 fill[3];                          /* unused */
 439 };
 440
 441
 442 /* extended attributes.
 443
 444    A file's EA info is stored as a list of (name,value) pairs.  It is
 445    usually in the fnode, but (if it's large) it is moved to a single
 446    sector run outside the fnode, or to multiple runs with an anode tree
 447    that points to them.
 448
 449    The value of a single EA is stored along with the name, or (if large)
 450    it is moved to a single sector run, or multiple runs pointed to by an
 451    anode tree, pointed to by the value field of the (name,value) pair.
 452
 453    Flags in the EA tell whether the value is immediate, in a single sector
 454    run, or in multiple runs.  Flags in the fnode tell whether the EA list
 455    is immediate, in a single run, or in multiple runs. */
 456
 457 struct extended_attribute
 458 {
 459   unsigned indirect: 1;                 /* 1 -> value gives sector number
 460                                            where real value starts */
 461   unsigned anode: 1;                    /* 1 -> sector is an anode
 462                                            that points to fragmented value */
 463   unsigned flag2: 1;
 464   unsigned flag3: 1;
 465   unsigned flag4: 1;
 466   unsigned flag5: 1;
 467   unsigned flag6: 1;
 468   unsigned needea: 1;                   /* required ea */
 469   u8 namelen;                           /* length of name, bytes */
 470   u16 valuelen;                         /* length of value, bytes */
 471   u8 name[0];
 472   /*
 473     u8 name[namelen];                   ascii attrib name
 474     u8 nul;                             terminating '\0', not counted
 475     u8 value[valuelen];                 value, arbitrary
 476       if this.indirect, valuelen is 8 and the value is
 477         u32 length;                     real length of value, bytes
 478         secno secno;                    sector address where it starts
 479       if this.anode, the above sector number is the root of an anode tree
 480         which points to the value.
 481   */
 482 };
 483
 484 /*
 485    Local Variables:
 486    comment-column: 40
 487    End:
 488 */