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 }