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