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 	/* some systems have these defined */
79 	#undef IEXEC
80 	#undef IWRITE
81 	#undef IREAD
82 	#undef ISVTX
83 	#undef ISGID
84 	#undef ISUID
85 	#undef IFMT
86 	#undef IFIFO
87 	#undef IFCHR
88 	#undef IFDIR
89 	#undef IFBLK
90 	#undef IFREG
91 	#undef IFLNK
92 	#undef IFSOCK
93 	#undef IFWHT
94 
95 	#define IEXEC	HFS_IEXEC
96 	#define IWRITE	HFS_IWRITE
97 	#define IREAD	HFS_IREAD
98 	#define ISVTX	HFS_ISVTX
99 	#define ISGID	HFS_ISGID
100 	#define ISUID	HFS_ISUID
101 	#define IFMT	HFS_IFMT
102 	#define IFIFO	HFS_IFIFO
103 	#define IFCHR	HFS_IFCHR
104 	#define IFDIR	HFS_IFDIR
105 	#define IFBLK	HFS_IFBLK
106 	#define IFREG	HFS_IFREG
107 	#define IFLNK	HFS_IFLNK
108 	#define IFSOCK	HFS_IFSOCK
109 	#define IFWHT	HFS_IFWHT
110 
111 	/* permissions in Inode.mode */
112 	IEXEC = 00100,
113 	IWRITE = 0200,
114 	IREAD = 0400,
115 	ISTXT = 01000,
116 	ISGID = 02000,
117 	ISUID = 04000,
118 
119 	/* type in Inode.mode */
120 	IFMT = 0170000,
121 	IFIFO = 0010000,
122 	IFCHR = 0020000,
123 	IFDIR = 0040000,
124 	IFBLK = 0060000,
125 	IFREG = 0100000,
126 	IFLNK = 0120000,
127 	IFSOCK = 0140000,
128 	IFWHT = 0160000,
129 };
130 
131 struct Extent
132 {
133 	u32int	start;		/* first block in extent */
134 	u32int	count;		/* number of blocks in extent */
135 };
136 
137 struct Fork
138 {
139 	u32int	cnid;		/* catalog node id (in memory only) */
140 	int	type;		/* Dfork or Rfork (in memory only) */
141 	u64int	size;		/* size in bytes */
142 	u32int	nblocks;
143 	Extent	extent[NEXTENTS];		/* initial extents */
144 };
145 
146 /*
147  * In-core catalog record for a file or folder.
148  */
149 struct Inode
150 {
151 	u32int	cnid;
152 	u64int	fileid;		/* in memory only */
153 	u32int	mtime;		/* modification */
154 	u32int	ctime;		/* attribute modification */
155 	u32int	atime;		/* access */
156 	u32int	nlink;		/* in memory only */
157 	u32int	uid;
158 	u32int	gid;
159 	int	mode;
160 	u32int	special;
161 	union{
162 		u32int	nentries;		/* directories */
163 		struct{		/* files */
164 			Fork	dfork;
165 			Fork	rfork;
166 			uchar	info[Filen];
167 
168 			/* in memory only */
169 			int	nhdr;		/* 0 or Adlen */
170 			Fork	*fork;		/* dfork or rfork */
171 		} f;
172 	} u;
173 };
174 
175 struct Tree
176 {
177 	int	nodesize;		/* node size in bytes */
178 	u32int	nnodes;		/* number of nodes in tree */
179 	u32int	root;		/* node number of the tree's root */
180 	int	height;
181 	int	maxkeylen;		/* maximum key size in bytes */
182 	int	indexkeylen;		/* 0 or length of index node keys */
183 	int	sensitive;		/* are key strings case sensitive */
184 	Hfs	*fs;
185 	Fork	*fork;
186 };
187 
188 struct Node
189 {
190 	int	type;		/* type of this node */
191 	u32int	next;		/* next related node or 0 */
192 	int	nrec;		/* number of records in this node */
193 };
194 
195 struct Treeref
196 {
197 	Tree	*tree;
198 	u32int	cnid;		/* tree->fork->cnid, for debugging prints */
199 
200 	Block	*block;		/* a node in the tree */
201 	u32int	nno;
202 	Node	node;
203 
204 	int	rno;		/* a record in the node */
205 	int	klen;
206 	uchar	*key;
207 	int	dlen;
208 	uchar	*data;
209 };
210 
211 struct Key
212 {
213 	int	(*_cmp)(uchar *k, int len, int *order, Key *key);
214 	void	*priv;
215 };
216 
217 struct Extentkey
218 {
219 	u32int	cnid;
220 	int	type;
221 	u32int	bno;
222 };
223 
224 struct Name
225 {
226 	int	len;
227 	Rune	name[NAMELEN];		/* only len runes on disk */
228 };
229 
230 struct Catalogkey
231 {
232 	u32int	parent;
233 	union{
234 		Name	name;
235 		uchar	*b;		/* not yet decoded */
236 	} u;
237 };
238 
239 struct Hfs
240 {
241 	u32int	blocksize;
242 	u32int	nblock;
243 	u32int	nfree;		/* for debugging */
244 	int	hasbadblocks;
245 	Fork	alloc;		/* block allocation bitmap */
246 	Fork	extentsfork;
247 	Fork	catalogfork;
248 	Tree	extents;		/* Extentkey -> Extent[NEXTENT] */
249 	Tree	catalog;		/* Catalogkey -> Catalogkey + Inode */
250 	u32int	hlinkparent;		/* 0 or cnid */
251 	Disk	*disk;
252 	Fsys	*fsys;
253 };