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