]> git.saurik.com Git - apple/hfs.git/blob - CopyHFSMeta/ScanExtents.c
hfs-285.tar.gz
[apple/hfs.git] / CopyHFSMeta / ScanExtents.c
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 */
26 static unsigned int
27 FindBlock(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 */
51 static int
52 GetNode(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 */
129 static unsigned int
130 ScanNode(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__
183 int
184 ScanExtents(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
268 done:
269 if (nodePtr)
270 free(nodePtr);
271 return retval;
272
273 }