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