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					AddExtent(vop, start, len);
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 */
182int
183ScanExtents(VolumeObjects_t *vop, int useAltHdr)
184{
185	int retval = -1;
186	ssize_t rv;
187	uint8_t buffer[vop->devp->blockSize];
188	struct RootNode {
189		BTNodeDescriptor desc;
190		BTHeaderRec header;
191	} *headerNode;
192	HFSPlusVolumeHeader *hp;
193	off_t vBlockSize;
194	size_t nodeSize;
195	size_t bufferSize;
196	int blocksPerNode;
197	void *nodePtr = NULL;
198	unsigned int nodeNum = 0;
199
200	hp = useAltHdr ? &vop->vdp->altHeader : & vop->vdp->priHeader;
201	vBlockSize = S32(hp->blockSize);
202
203	rv = GetBlock(vop->devp, S32(hp->extentsFile.extents[0].startBlock) * vBlockSize, buffer);
204	if (rv == -1) {
205		warnx("Cannot get btree header node for extents file for %s header", useAltHdr ? "alternate" : "primary");
206		retval = -1;
207		goto done;
208	}
209	headerNode = (struct RootNode*)buffer;
210
211	if (headerNode->desc.kind != kBTHeaderNode) {
212		warnx("Root node is not a header node (%x)", headerNode->desc.kind);
213		goto done;
214	}
215
216	nodeSize = S16(headerNode->header.nodeSize);
217	/*
218	 * There are three cases here:
219	 * nodeSize == vBlockSize;
220	 * nodeSize > vBlockSize;
221	 * nodeSize < vBlockSize.
222	 * For the first two, everything is easy:  we just need to read in a nodeSize, and that
223	 * contains everything we care about.  For the third case, however, we will
224	 * need to read in an allocation block size, but then have GetNode move memory
225	 * around so the node we want is at the beginning of the buffer.  Note that this
226	 * does mean it is less efficient than it should be.
227	 */
228	if (nodeSize < vBlockSize) {
229		blocksPerNode = 1;	// 1 block will hold multiple nodes
230		bufferSize = vBlockSize;
231	} else {
232		blocksPerNode = nodeSize / vBlockSize;
233		bufferSize = nodeSize;
234	}
235
236	nodePtr = malloc(bufferSize);
237	if (nodePtr == NULL) {
238		warn("cannot allocate buffer for node");
239		goto done;
240	}
241	nodeNum = S32(headerNode->header.firstLeafNode);
242
243	if (debug) printf("first leaf nodenum = %u\n", nodeNum);
244
245	/*
246	 * Iterate through the leaf nodes.
247	 */
248	while (nodeNum != 0) {
249		if (debug) printf("Getting node %u\n", nodeNum);
250
251		/*
252		 * GetNode() puts the node we want into nodePtr;
253		 * we have ensured that the buffer is large enough
254		 * to contain at least one node, or one allocation block,
255		 * whichever is larger.
256		 */
257		rv = GetNode(vop->devp, hp, nodeNum, nodeSize, nodePtr);
258		if (rv == -1) {
259			warnx("Cannot get node %u", nodeNum);
260			retval = -1;
261			goto done;
262		}
263		nodeNum = ScanNode(vop, nodePtr, nodeSize, vBlockSize);
264	}
265	retval = 0;
266
267done:
268	if (nodePtr)
269		free(nodePtr);
270	return retval;
271
272}
273