1 /*
2 	Supports HFS Plus and HFSX file systems with or without an HFS
3 	wrapper.
4 
5 	Apple technical note 1150 documents the file system:
6 	
7 	http://developer.apple.com/technotes/tn/tn1150.html
8 	
9 	Briefly an hfs file system comprises a volume header, an
10 	optional journal, and a set of forks.
11 	
12 	Most fs metadata resides in forks including a block allocation
13 	bitmap, a tree storing extents (q.v.) for forks and bad disk
14 	blocks, and a tree storing catalog (file and directory)
15 	information.
16 
17 	An extent comprises a starting block number and block count.
18 	The fs maintains a list of k*NEXTENTS extents for each fork.
19 	These are used to map fork block numbers to disk block
20 	numbers.  A fork's initial extents are in its catalog record
21 	or (for fs forks) the volume header.  The rest are in the
22 	extents tree.
23 
24 	Fs trees are layed out (in a fork) as an array of fixed-size
25 	nodes.  A node comprises a header, a sorted list of
26 	variable-size records, and trailing record offsets.  The
27 	records in interior nodes map keys to (child) node numbers.
28 	The records in leaf nodes map keys to data.  The nodes at each
29 	level in a tree are also sorted via (sibling) node numbers
30 	stored in each node header.
31 */
32 
33 typedef struct Extent Extent;
34 typedef struct Fork Fork;
35 typedef struct Inode Inode;
36 typedef struct Tree Tree;
37 typedef struct Node Node;
38 typedef struct Treeref Treeref;
39 typedef struct Key Key;
40 typedef struct Extentkey Extentkey;
41 typedef struct Name Name;
42 typedef struct Catalogkey Catalogkey;
43 typedef struct Hfs Hfs;
44 
45 enum
46 {
47 	Hfssig = 0x4244,
48 	Hfsplussig = 0x482B,
49 	Hfsxsig = 0x4858,
50  	Hfsplusmagic = (Hfsplussig<<16)|4,
51  	Hfsxmagic = (Hfsxsig<<16)|5,
52 
53 	NAMELEN = 255,
54 	UTFNAMELEN = NAMELEN*UTFmax,
55 	
56 	NEXTENTS = 8,
57 	
58 	Dfork = 0, Rfork = 255,
59 	
60 	/* fixed cnids */
61 	RootpId = 1, RootId, ExtentsId, CatalogId,
62 	BadblockId, AllocId, MinuserId = 16,
63 
64 	/* size of a few structures on disk */
65 	Extentlen = 8,		/* Extent */
66 	Ndlen = 14,		/* Node */
67 	Folderlen = 88, Filelen = 248,		/* Inode */
68 	Adlen = 82,		/* Apple double header */
69 		Fioff = 50,
70 	Filen = 32,		/* Finder info */
71 
72 	/* values in Node.type */
73 	LeafNode = -1, IndexNode, HeaderNode, MapNode,
74 	
75 	/* catalog record types */
76 	Folder = 1, File, FolderThread, FileThread,
77 
78 	/* permissions in Inode.mode */
79 	IEXEC = 00100,
80 	IWRITE = 0200,
81 	IREAD = 0400,
82 	ISTXT = 01000,
83 	ISGID = 02000,
84 	ISUID = 04000,
85 
86 	/* type in Inode.mode */
87 	IFMT = 0170000,
88 	IFIFO = 0010000,
89 	IFCHR = 0020000,
90 	IFDIR = 0040000,
91 	IFBLK = 0060000,
92 	IFREG = 0100000,
93 	IFLNK = 0120000,
94 	IFSOCK = 0140000,
95 	IFWHT = 0160000,
96 };
97 
98 struct Extent
99 {
100 	u32int	start;		/* first block in extent */
101 	u32int	count;		/* number of blocks in extent */
102 };
103 
104 struct Fork
105 {
106 	u32int	cnid;		/* catalog node id (in memory only) */
107 	int	type;		/* Dfork or Rfork (in memory only) */
108 	u64int	size;		/* size in bytes */
109 	u32int	nblocks;
110 	Extent	extent[NEXTENTS];		/* initial extents */
111 };
112 
113 /*
114  * In-core catalog record for a file or folder.
115  */
116 struct Inode
117 {
118 	u32int	cnid;
119 	u64int	fileid;		/* in memory only */
120 	u32int	mtime;		/* modification */
121 	u32int	ctime;		/* attribute modification */
122 	u32int	atime;		/* access */
123 	u32int	nlink;		/* in memory only */
124 	u32int	uid;
125 	u32int	gid;
126 	int	mode;
127 	u32int	special;
128 	union{
129 		u32int	nentries;		/* directories */
130 		struct{		/* files */
131 			Fork	dfork;
132 			Fork	rfork;
133 			uchar	info[Filen];
134 
135 			/* in memory only */
136 			int	nhdr;		/* 0 or Adlen */
137 			Fork	*fork;		/* dfork or rfork */
138 		} f;
139 	} u;
140 };
141 
142 struct Tree
143 {
144 	int	nodesize;		/* node size in bytes */
145 	u32int	nnodes;		/* number of nodes in tree */
146 	u32int	root;		/* node number of the tree's root */
147 	int	height;
148 	int	maxkeylen;		/* maximum key size in bytes */
149 	int	indexkeylen;		/* 0 or length of index node keys */
150 	int	sensitive;		/* are key strings case sensitive */
151 	Hfs	*fs;
152 	Fork	*fork;
153 };
154 
155 struct Node
156 {
157 	int	type;		/* type of this node */
158 	u32int	next;		/* next related node or 0 */
159 	int	nrec;		/* number of records in this node */
160 };
161 
162 struct Treeref
163 {
164 	Tree	*tree;
165 	u32int	cnid;		/* tree->fork->cnid, for debugging prints */
166 	
167 	Block	*block;		/* a node in the tree */
168 	u32int	nno;
169 	Node	node;
170 	
171 	int	rno;		/* a record in the node */
172 	int	klen;
173 	uchar	*key;	
174 	int	dlen;
175 	uchar	*data;
176 };
177 
178 struct Key
179 {
180 	int	(*_cmp)(uchar *k, int len, int *order, Key *key);
181 	void	*priv;
182 };
183 
184 struct Extentkey
185 {
186 	u32int	cnid;
187 	int	type;
188 	u32int	bno;
189 };
190 
191 struct Name
192 {
193 	int	len;
194 	Rune	name[NAMELEN];		/* only len runes on disk */
195 };
196 
197 struct Catalogkey
198 {
199 	u32int	parent;
200 	union{
201 		Name	name;
202 		uchar	*b;		/* not yet decoded */
203 	} u;
204 };
205 
206 struct Hfs
207 {
208 	u32int	blocksize;
209 	u32int	nblock;
210 	u32int	nfree;		/* for debugging */
211 	int	hasbadblocks;
212 	Fork	alloc;		/* block allocation bitmap */
213 	Fork	extentsfork;
214 	Fork	catalogfork;
215 	Tree	extents;		/* Extentkey -> Extent[NEXTENT] */
216 	Tree	catalog;		/* Catalogkey -> Catalogkey + Inode */
217 	u32int	hlinkparent;		/* 0 or cnid */
218 	Disk	*disk;
219 	Fsys	*fsys;
220 };