1#include <stdio.h>
2#include <stdlib.h>
3#include <unistd.h>
4#include <err.h>
5#include <errno.h>
6#include <string.h>
7
8#include "hfsmeta.h"
9#include "Data.h"
10
11#ifndef MAX
12# define MAX(a, b) \
13	({ __typeof(a) __a = (a); __typeof(b) __b = (b); __a > __b ? __a : __b; })
14#endif
15
16/*
17 * Functions to scan through the extents overflow file, grabbing
18 * overflow extents for the special files.
19 */
20
21/*
22 * Given an extent record, return the logical block address (in the volume)
23 * for the requested block offset into the file.  It returns 0 if it can't
24 * find it.
25 */
26static unsigned int
27FindBlock(HFSPlusExtentRecord *erp, unsigned int blockNum)
28{
29	unsigned int lba = 0;
30	unsigned int base = 0;
31	HFSPlusExtentDescriptor *ep = &(*erp)[0];
32	int i;
33
34	for (i = 0; i < kHFSPlusExtentDensity; i++) {
35		if (ep->startBlock == 0 || ep->blockCount == 0)
36			break;
37		if ((base + S32(ep->blockCount)) > blockNum) {
38			lba = S32(ep->startBlock) + (blockNum - base);
39			break;
40		}
41		base += S32(ep->blockCount);
42		ep++;
43	}
44	return lba;
45}
46
47/*
48 * Get the given node from the extents-overflow file.  Returns -1 on error, and
49 * 0 on success.
50 */
51static int
52GetNode(DeviceInfo_t *devp, HFSPlusVolumeHeader *hp, int nodeNum, size_t nodeSize, void *nodePtr)
53{
54	int retval = 0;
55	unsigned char *ptr, *endPtr;
56	unsigned int offset;
57	HFSPlusExtentRecord *erp = &hp->extentsFile.extents;
58	size_t bufferSize = MAX(nodeSize, S32(hp->blockSize));
59
60	ptr = nodePtr;
61	endPtr = ptr + bufferSize;
62	/*
63	 * The block number for HFS Plus is guaranteed to be 32 bits.
64	 * But the multiplication could over-flow, so we cast one
65	 * of the variables to off_t, and cast the whole thing back
66	 * to uint32_t.
67	 */
68	offset = (uint32_t)(((off_t)nodeNum * nodeSize) / S32(hp->blockSize));
69
70	/*
71	 * We have two sizes to consider here:  the device blocksize, and the
72	 * buffer size.  The buffer size is the larger of the btree node size
73	 * and the volume allocation block size.
74	 *
75	 * This loop is the case where the device block size is smaller than
76	 * the amount we want to read (in a common case, 8kbyte node size, and
77	 * 512 byte block size).  It reads in a device block, and adds it to
78	 * the buffer; it continues until an error, or until it has gotten
79	 * the amount it needs.
80	 *
81	 * The variable "offset" is in *allocation blocks*, not *bytes*.
82	 */
83	while (ptr < endPtr) {
84		ssize_t rv;
85		off_t lba;
86		unsigned int i;
87
88
89		lba = FindBlock(erp, offset);
90		if (lba == 0) {
91			warnx("Cannot find block %u in extents overflow file", offset);
92			return -1;
93		}
94		lba = lba * S32(hp->blockSize);
95		for (i = 0; i < S32(hp->blockSize) / devp->blockSize; i++) {
96//			printf("Trying to get block %lld\n", lba + i);
97			rv = GetBlock(devp, lba + (i * devp->blockSize), ptr);
98			if (rv == -1) {
99				warnx("Cannot read block %llu in extents overflow file", lba + i);
100				return -1;
101			}
102			ptr += devp->blockSize;
103		}
104		offset++;
105	}
106
107	/*
108	 * Per 13080856:  if the node size is less than the allocation block size, we
109	 * have to deal with having multiple nodes per block.  The code above to read it
110	 * has read in either an allocation block, or a node block, depending on which
111	 * is larger.  If the allocation block is larger, then we have to move the node
112	 * we want to the beginning of the buffer.
113	 */
114	if (nodeSize < bufferSize) {
115		size_t indx = nodeNum % (S32(hp->blockSize) / nodeSize);
116		ptr = nodePtr;
117		memmove(ptr, ptr + (indx * nodeSize), nodeSize);
118	}
119	return retval;
120}
121
122/*
123 * Scan through an extentes overflow node, looking for File ID's less than
124 * the first user file ID.  For each one it finds, it adds the extents to
125 * the volume structure list.  It returns the number of the next node
126 * (which will be 0 when we've hit the end of the list); it also returns 0
127 * when it encounters a CNID larger than the system files'.
128 */
129static unsigned int
130ScanNode(VolumeObjects_t *vop, uint8_t *nodePtr, size_t nodeSize, off_t blockSize)
131{
132	u_int16_t *offsetPtr;
133	BTNodeDescriptor *descp;
134	int indx;
135	int numRecords;
136	HFSPlusExtentKey *keyp;
137	HFSPlusExtentRecord *datap;
138	uint8_t *recp;
139	unsigned int retval;
140
141	descp = (BTNodeDescriptor*)nodePtr;
142
143	if (descp->kind != kBTLeafNode)
144		return 0;
145
146	numRecords = S16(descp->numRecords);
147	offsetPtr = (u_int16_t*)((uint8_t*)nodePtr + nodeSize);
148
149	retval = S32(descp->fLink);
150	for (indx = 1; indx <= numRecords; indx++) {
151		int recOffset = S16(offsetPtr[-indx]);
152		recp = nodePtr + recOffset;
153		if (recp > (nodePtr + nodeSize)) {
154			return -1;	// Corrupt node
155		}
156		keyp = (HFSPlusExtentKey*)recp;
157		datap = (HFSPlusExtentRecord*)(recp + sizeof(HFSPlusExtentKey));
158		if (debug > 1) printf("Node index #%d:  fileID = %u\n", indx, S32(keyp->fileID));
159		if (S32(keyp->fileID) >= kHFSFirstUserCatalogNodeID) {
160			if (debug) printf("Done scanning extents overflow file\n");
161			retval = 0;
162			break;
163		} else {
164			int i;
165			for (i = 0; i < kHFSPlusExtentDensity; i++) {
166				off_t start = S32((*datap)[i].startBlock) * (off_t)blockSize;
167				off_t len = S32((*datap)[i].blockCount) * (off_t)blockSize;
168				if (start && len)
169					AddExtentForFile(vop, start, len, S32(keyp->fileID));
170			}
171		}
172	}
173
174	return retval;
175}
176
177/*
178 * Given a volme structure list, scan through the extents overflow file
179 * looking for system-file extents (those with a CNID < 16).  If useAltHdr
180 * is set, it'll use the extents overflow descriptor in the alternate header.
181 */
182__private_extern__
183int
184ScanExtents(VolumeObjects_t *vop, int useAltHdr)
185{
186	int retval = -1;
187	ssize_t rv;
188	uint8_t buffer[vop->devp->blockSize];
189	struct RootNode {
190		BTNodeDescriptor desc;
191		BTHeaderRec header;
192	} *headerNode;
193	HFSPlusVolumeHeader *hp;
194	off_t vBlockSize;
195	size_t nodeSize;
196	size_t bufferSize;
197	int blocksPerNode;
198	void *nodePtr = NULL;
199	unsigned int nodeNum = 0;
200
201	hp = useAltHdr ? &vop->vdp->altHeader : & vop->vdp->priHeader;
202	vBlockSize = S32(hp->blockSize);
203
204	rv = GetBlock(vop->devp, S32(hp->extentsFile.extents[0].startBlock) * vBlockSize, buffer);
205	if (rv == -1) {
206		warnx("Cannot get btree header node for extents file for %s header", useAltHdr ? "alternate" : "primary");
207		retval = -1;
208		goto done;
209	}
210	headerNode = (struct RootNode*)buffer;
211
212	if (headerNode->desc.kind != kBTHeaderNode) {
213		warnx("Root node is not a header node (%x)", headerNode->desc.kind);
214		goto done;
215	}
216
217	nodeSize = S16(headerNode->header.nodeSize);
218	/*
219	 * There are three cases here:
220	 * nodeSize == vBlockSize;
221	 * nodeSize > vBlockSize;
222	 * nodeSize < vBlockSize.
223	 * For the first two, everything is easy:  we just need to read in a nodeSize, and that
224	 * contains everything we care about.  For the third case, however, we will
225	 * need to read in an allocation block size, but then have GetNode move memory
226	 * around so the node we want is at the beginning of the buffer.  Note that this
227	 * does mean it is less efficient than it should be.
228	 */
229	if (nodeSize < vBlockSize) {
230		blocksPerNode = 1;	// 1 block will hold multiple nodes
231		bufferSize = vBlockSize;
232	} else {
233		blocksPerNode = nodeSize / vBlockSize;
234		bufferSize = nodeSize;
235	}
236
237	nodePtr = malloc(bufferSize);
238	if (nodePtr == NULL) {
239		warn("cannot allocate buffer for node");
240		goto done;
241	}
242	nodeNum = S32(headerNode->header.firstLeafNode);
243
244	if (debug) printf("first leaf nodenum = %u\n", nodeNum);
245
246	/*
247	 * Iterate through the leaf nodes.
248	 */
249	while (nodeNum != 0) {
250		if (debug) printf("Getting node %u\n", nodeNum);
251
252		/*
253		 * GetNode() puts the node we want into nodePtr;
254		 * we have ensured that the buffer is large enough
255		 * to contain at least one node, or one allocation block,
256		 * whichever is larger.
257		 */
258		rv = GetNode(vop->devp, hp, nodeNum, nodeSize, nodePtr);
259		if (rv == -1) {
260			warnx("Cannot get node %u", nodeNum);
261			retval = -1;
262			goto done;
263		}
264		nodeNum = ScanNode(vop, nodePtr, nodeSize, vBlockSize);
265	}
266	retval = 0;
267
268done:
269	if (nodePtr)
270		free(nodePtr);
271	return retval;
272
273}
274