cdnutter
/
iBoot
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
iBoot/lib/fs/hfs/hfs.c

1373 lines
39 KiB
C
Raw Permalink Blame History

/*
* Copyright (C) 2013 Apple Inc. All rights reserved.
* Copyright (C) 2007-2011 Apple Inc. All rights reserved.
* Copyright (c) 2000-2006 Apple Computer, Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* The contents of this file constitute Original Code as defined in and
* are subject to the Apple Public Source License Version 1.1 (the
* "License"). You may not use this file except in compliance with the
* License. Please obtain a copy of the License at
* http://www.apple.com/publicsource and read it before using this file.
*
* This Original Code and all software distributed under the License are
* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
* License for the specific language governing rights and limitations
* under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/
/*
* hfs.c - File System Module for HFS and HFS+.
*
* Copyright (c) 1999-2004 Apple Computer, Inc.
*
* DRI: Josh de Cesare
*/
#include <debug.h>
#include <sys.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <lib/libc.h>
#include <string.h>
#include "hfs.h"
#include "hfs_format.h"
#define HFS_MAXPATHLEN (512)
#define HFS_MAXNAMLEN (255)
#define kBlockSize (0x200)
#define kBlockSizeMax (0x10000)
#define kMDBBaseOffset (2 * kBlockSize)
#define kBTreeCatalog (0)
#define kBTreeExtents (1)
#define kBTreeSize (256)
#define kDirLevelMax (48)
static CICell gCurrentIH;
static off_t gAllocationOffset;
static bool gIsHFSPlus;
static uint32_t gBlockSize;
static uint8_t gBTreeHeaderBuffer[HFS_MAXPATHLEN];
static BTHeaderRec *gBTHeaders[2];
static uint8_t gHFSPlusHeader[kBlockSize];
static HFSPlusVolumeHeader *gHFSPlus =(HFSPlusVolumeHeader*)gHFSPlusHeader;
static uint64_t gVolID;
static char gTempStr[kBTreeSize];
static int ReadFile(void *file, size_t *length, void *base, off_t offset);
static int GetCatalogEntryInfo(void *entry, uint32_t *flags, time_t *time, off_t *size);
static int ResolvePathToCatalogEntry(const char *filePath, uint32_t *flags, void *entry, uint32_t dirID, off_t *dirIndex, time_t *time, off_t *size);
static int GetCatalogEntry(off_t *dirIndex, char *name, size_t nameSize, uint32_t *flags, time_t *time, off_t *size);
static int ReadCatalogEntry(const char *fileName, uint32_t dirID, void *entry, off_t *dirIndex);
static int ReadExtentsEntry(uint32_t fileID, uint32_t startBlock, void *entry);
static int ReadBTreeEntry(uint32_t btree, void *key, uint8_t *entry, off_t *dirIndex);
static int GetBTreeRecord(uint32_t index, uint8_t *nodeBuffer, uint32_t nodeSize, uint8_t **key, uint8_t **data);
static int ReadExtent(uint8_t *extent, uint32_t extentSize, uint32_t extentFile, off_t offset, uint32_t size, void *buffer, bool cache);
static uint32_t GetExtentStart(void *extents, uint32_t index);
static uint32_t GetExtentSize(void *extents, uint32_t index);
static int CompareHFSPlusCatalogKeys(void *key, void *testKey);
static int CompareHFSPlusExtentsKeys(void *key, void *testKey);
static int32_t BinaryUnicodeCompare (uint16_t * str1, uint32_t length1, uint16_t * str2, uint32_t length2);
static int utf_encodestr(const uint16_t *ucsp, unsigned ucslen, uint8_t *utf8p, size_t bufsize);
static void utf_decodestr(const char *utf8p, uint16_t *ucsp, uint16_t *ucslen, uint32_t bufsize);
static void utf_decodestr255(const char *utf8p, struct HFSUniStr255 *ucsstrp);
#if 0
# define HFSdebug(fmt, args...) printf("%s: " fmt "\n", __FUNCTION__ , ##args)
static inline void
DPrintUTF(uint16_t *ucsp, int length)
{
while (length--)
printf("%c", (*(ucsp++) & 0xff00) >> 8);
}
#else
# define HFSdebug(fmt, args...) do { } while(0)
# define DPrintUTF(s, l) do { } while(0)
#endif
static bool
isPowerOf2(uint32_t x)
{
return ((x & (x-1)) == 0);
}
// Sanity-checks some values in the HFS+ header
static bool
ValidateHFSPlusHeader(void)
{
bool valid = true;
uint32_t blockSize = HFSntohl(&gHFSPlus->blockSize);
// check signature field
if ((HFSntohs(&gHFSPlus->signature) != kHFSPlusSigWord) && (HFSntohs(&gHFSPlus->signature) != kHFSXSigWord)) {
dprintf(DEBUG_CRITICAL, "Not HFS+ (signature 0x%04x)\n", HFSntohs(&gHFSPlus->signature));
valid = false;
goto exit;
}
// check blockSize field
if ((blockSize < kBlockSize) || (blockSize > kBlockSizeMax) || (!isPowerOf2(blockSize))) {
dprintf(DEBUG_CRITICAL, "Bad HFS+ blockSize(0x%08x, 0x%x, 0x%x)\n", blockSize, kBlockSize, kBlockSizeMax);
valid = false;
goto exit;
}
exit:
return valid;
}
static int
SanityCheckBTreeHeader(BTHeaderRec *hdr, off_t fileSize)
{
uint16_t nodeSize = HFSntohs(&hdr->nodeSize);
if (!isPowerOf2(nodeSize)) {
HFSdebug("BTree node size is %d, which is not a power of 2\n", nodeSize);
return -1;
}
if (nodeSize < 512) {
HFSdebug("BTree node size is %d, minimum is 512\n", nodeSize);
return -1;
}
if ((fileSize / nodeSize) != HFSntohl(&hdr->totalNodes)) {
HFSdebug("BTree file size indicates %u nodes, header indicates %u\n", (uint32_t)(fileSize / nodeSize), HFSntohl(&hdr->totalNodes));
return -1;
}
return 0;
}
int
HFSInitPartition(CICell ih)
{
uint32_t extentSize, extentFile, nodeSize, btree;
uint32_t result;
void *extent;
if (ih == gCurrentIH)
return 0;
dprintf(DEBUG_INFO, "HFSInitPartition: %p\n", ih);
gAllocationOffset = 0;
gIsHFSPlus = 0;
gBTHeaders[0] = 0;
gBTHeaders[1] = 0;
// Look for the HFSPlus Header
result = HFSBlockRead(ih, gHFSPlusHeader, gAllocationOffset + kMDBBaseOffset, kBlockSize);
if (result != kBlockSize) {
HFSdebug("Error reading HFS+ header");
return -1;
}
// Verify contents of header before continuing
if (!ValidateHFSPlusHeader()) {
gCurrentIH = NULL;
return -1;
}
gIsHFSPlus = 1;
gBlockSize = HFSntohl(&gHFSPlus->blockSize);
HFSdebug("allocation block size %x", gBlockSize);
if (gBlockSize == 0) {
HFSdebug("Volume block size cannot be zero!");
return -1;
}
if (HFSntohl(&gHFSPlus->totalBlocks) == 0) {
HFSdebug("Volume totalBlocks cannot be zero!");
return -1;
}
CacheInit(ih, gBlockSize);
gCurrentIH = ih;
// grab the 64 bit volume ID
memcpy(&gVolID, &gHFSPlus->finderInfo[24], 8);
// Get the Catalog BTree header
btree = kBTreeCatalog;
extent = &gHFSPlus->catalogFile.extents;
extentSize = HFSntohll(&gHFSPlus->catalogFile.logicalSize);
if (extentSize < 512) {
HFSdebug("Catalog btree file is too short, %lld\n", (off_t)extentSize);
return -1;
}
extentFile = kHFSCatalogFileID;
HFSdebug("reading catalog Btree, extent %p extentSize %x, extentFile %d", extent, extentSize, extentFile);
if (ReadExtent(extent, extentSize, extentFile, 0, kBTreeSize, gBTreeHeaderBuffer + btree * kBTreeSize, 0) != kBTreeSize) {
HFSdebug("Cannot read catalog file header node");
return -1;
}
gBTHeaders[btree] = (BTHeaderRec *)(gBTreeHeaderBuffer + btree * kBTreeSize + /*sizeof(BTNodeDescriptor)*/ 14);
HFSdebug("Catalog BTree header: %p", gBTHeaders[btree]);
HFSdebug(" maximum height (usually leaf nodes) %x", HFSntohs(&gBTHeaders[btree]->treeDepth));
HFSdebug(" node number of root node %x", HFSntohl(&gBTHeaders[btree]->rootNode));
HFSdebug(" number of leaf records in all leaf nodes %x", HFSntohl(&gBTHeaders[btree]->leafRecords));
HFSdebug(" node number of first leaf node %x", HFSntohl(&gBTHeaders[btree]->firstLeafNode));
HFSdebug(" node number of last leaf node %x", HFSntohl(&gBTHeaders[btree]->lastLeafNode));
HFSdebug(" size of a node, in bytes %x", HFSntohs(&gBTHeaders[btree]->nodeSize));
HFSdebug(" total number of nodes in tree %x", HFSntohl(&gBTHeaders[btree]->totalNodes));
HFSdebug(" number of unused (free) nodes in tree %x", HFSntohl(&gBTHeaders[btree]->freeNodes));
HFSdebug(" Key string Comparison Type %x", gBTHeaders[btree]->keyCompareType);
HFSdebug(" persistent attributes about the tree %x", HFSntohl(&gBTHeaders[btree]->attributes));
if (SanityCheckBTreeHeader(gBTHeaders[btree], extentSize) == -1) {
return -1;
}
// Get the Extents BTree header
btree = kBTreeExtents;
extent = &gHFSPlus->extentsFile.extents;
extentSize = HFSntohll(&gHFSPlus->extentsFile.logicalSize);
if (extentSize < 512) {
HFSdebug("Extents overflow btree file is too short, %lld\n", (off_t)extentSize);
return -1;
}
extentFile = kHFSExtentsFileID;
if (ReadExtent(extent, extentSize, extentFile, 0, kBTreeSize, gBTreeHeaderBuffer + btree * kBTreeSize, 0) != kBTreeSize) {
HFSdebug("Cannot read extents overflow file header node");
return -1;
}
gBTHeaders[btree] = (BTHeaderRec *)(gBTreeHeaderBuffer + btree * kBTreeSize + /*sizeof(BTNodeDescriptor)*/ 14);
HFSdebug("Extents BTree header:");
HFSdebug(" maximum height (usually leaf nodes) %x", HFSntohs(&gBTHeaders[btree]->treeDepth));
HFSdebug(" node number of root node %x", HFSntohl(&gBTHeaders[btree]->rootNode));
HFSdebug(" number of leaf records in all leaf nodes %x", HFSntohl(&gBTHeaders[btree]->leafRecords));
HFSdebug(" node number of first leaf node %x", HFSntohl(&gBTHeaders[btree]->firstLeafNode));
HFSdebug(" node number of last leaf node %x", HFSntohl(&gBTHeaders[btree]->lastLeafNode));
HFSdebug(" size of a node, in bytes %x", HFSntohs(&gBTHeaders[btree]->nodeSize));
HFSdebug(" total number of nodes in tree %x", HFSntohl(&gBTHeaders[btree]->totalNodes));
HFSdebug(" number of unused (free) nodes in tree %x", HFSntohl(&gBTHeaders[btree]->freeNodes));
HFSdebug(" Key string Comparison Type %x", gBTHeaders[btree]->keyCompareType);
HFSdebug(" persistent attributes about the tree %x", HFSntohl(&gBTHeaders[btree]->attributes));
if (SanityCheckBTreeHeader(gBTHeaders[btree], extentSize) == -1) {
return -1;
}
// If the BTree node size is larger than the block size, reset the cache.
nodeSize = HFSntohs(&gBTHeaders[btree]->nodeSize);
if (nodeSize > gBlockSize)
CacheInit(ih, nodeSize);
return 0;
}
int
HFSDetect(void)
{
if (gCurrentIH == NULL) {
dprintf(DEBUG_CRITICAL, "No current device\n");
return 1;
}
dprintf(DEBUG_INFO, "Filesystem: HFS+\n signature 0x%04x version 0x%04x\n", HFSntohs(&gHFSPlus->signature), HFSntohs(&gHFSPlus->version));
dprintf(DEBUG_INFO, " allocation block size %d bytes\n total block count %d\n volume size %d Mbytes\n",
HFSntohl(&gHFSPlus->blockSize), HFSntohl(&gHFSPlus->totalBlocks),
(int)((long long)HFSntohl(&gHFSPlus->blockSize) * HFSntohl(&gHFSPlus->totalBlocks) / (1024 * 1024)));
dprintf(DEBUG_INFO, " %d files\n %d folders\n", HFSntohl(&gHFSPlus->fileCount), HFSntohl(&gHFSPlus->folderCount));
dprintf(DEBUG_INFO, " created 0x%08x\n modified 0x%08x\n backed up 0x%08x\n checked 0x%08x\n",
HFSntohl(&gHFSPlus->createDate), HFSntohl(&gHFSPlus->modifyDate),
HFSntohl(&gHFSPlus->backupDate), HFSntohl(&gHFSPlus->checkedDate));
dprintf(DEBUG_INFO, " Allocation file\n");
dprintf(DEBUG_INFO, " logical size %d clumpSize %d totalBlocks %d\n",
(int)HFSntohll(&gHFSPlus->allocationFile.logicalSize),
HFSntohl(&gHFSPlus->allocationFile.clumpSize),
HFSntohl(&gHFSPlus->allocationFile.totalBlocks));
dprintf(DEBUG_INFO, " Extents file\n");
dprintf(DEBUG_INFO, " logical size %d clumpSize %d totalBlocks %d\n",
(int)HFSntohll(&gHFSPlus->extentsFile.logicalSize),
HFSntohl(&gHFSPlus->extentsFile.clumpSize),
HFSntohl(&gHFSPlus->extentsFile.totalBlocks));
dprintf(DEBUG_INFO, " Catalog file\n");
dprintf(DEBUG_INFO, " logical size %d clumpSize %d totalBlocks %d\n",
(int)HFSntohll(&gHFSPlus->catalogFile.logicalSize),
HFSntohl(&gHFSPlus->catalogFile.clumpSize),
HFSntohl(&gHFSPlus->catalogFile.totalBlocks));
dprintf(DEBUG_INFO, " Attributes file\n");
dprintf(DEBUG_INFO, " logical size %d clumpSize %d totalBlocks %d\n",
(int)HFSntohll(&gHFSPlus->attributesFile.logicalSize),
HFSntohl(&gHFSPlus->attributesFile.clumpSize),
HFSntohl(&gHFSPlus->attributesFile.totalBlocks));
return 0;
}
int
HFSGetFileInfo(CICell ih, const char *filePath, uint32_t *flags, time_t *time, off_t *size)
{
char *entry;
uint32_t dirID;
int result;
HFSdebug("fs %p path %s", ih, filePath);
entry = (char *)malloc(HFS_MAXPATHLEN);
dirID = kHFSRootFolderID;
result = ResolvePathToCatalogEntry(filePath, flags, entry, dirID, 0, time, size);
free(entry);
return result;
}
int
HFSReadFile(CICell ih, const char *filePath, void *base, off_t offset, size_t length)
{
char *entry;
uint32_t dirID, flags;
int result;
entry = (char *)malloc(HFS_MAXPATHLEN);
dirID = kHFSRootFolderID;
result = ResolvePathToCatalogEntry(filePath, &flags, entry, dirID, 0, NULL, NULL);
if (result != 0) {
dprintf(DEBUG_CRITICAL, "Could not find '%s'\n", filePath);
goto exit;
}
if ((flags & kFileTypeMask) != kFileTypeFlat) {
dprintf(DEBUG_CRITICAL, "'%s' is not a file\n", filePath);
result = -1;
goto exit;
}
result = ReadFile(entry, &length, base, offset);
if (result == 0)
result = length;
exit:
HFSdebug("returning %d\n", result);
free(entry);
return result;
}
int
HFSGetDirEntry(CICell ih, const char *dirPath, off_t *dirIndex, char *name, size_t nameSize, uint32_t *flags, time_t *time, off_t *size)
{
char *entry;
uint32_t dirID, dirFlags;
int ret = 0;
if (*dirIndex == -1)
return -1;
entry = (char *)malloc(HFS_MAXPATHLEN);
dirID = kHFSRootFolderID;
if (*dirIndex == 0) {
ret = ResolvePathToCatalogEntry(dirPath, &dirFlags, entry, dirID, dirIndex, NULL, NULL);
if (ret != 0) {
ret = -1;
goto exit;
}
if (*dirIndex == 0)
*dirIndex = -1;
/* if what we looked up didn't give us the header entry for the directory, bail */
if ((dirFlags & kFileTypeMask) != kFileTypeUnknown) {
dprintf(DEBUG_CRITICAL, "not a directory: '%s' flags %x\n", dirPath, dirFlags);
ret = -1;
goto exit;
}
}
if (GetCatalogEntry(dirIndex, name, nameSize, flags, time, size) != 0) {
ret = -1;
goto exit;
}
/* end of the catalog or end of the directory */
if ((*dirIndex == 0) || ((*flags & kFileTypeMask) == kFileTypeUnknown))
*dirIndex = -1;
exit:
free(entry);
return ret;
}
struct HFSPlusVolumeHeader *
HFSGetVolumeHeader(void)
{
return(gHFSPlus);
}
// Private Functions
static int
ReadFile(void *file, size_t *length_inout, void *base, off_t offset)
{
size_t length;
void *extents;
uint32_t fileID, fileLength;
HFSPlusCatalogFile *hfsPlusFile = file;
int rv;
fileID = HFSntohl(&hfsPlusFile->fileID);
fileLength = HFSntohll(&hfsPlusFile->dataFork.logicalSize);
extents = &hfsPlusFile->dataFork.extents;
length = *length_inout;
// nothing to do if we're asked to read 0 bytes
if (length == 0) {
return 0;
}
// Our parameter is a size_t, but the rest of the library treats
// lengths as uint32_t
if (length > UINT32_MAX) {
dprintf(DEBUG_CRITICAL, "Length is too large.\n");
return -1;
}
if (offset > UINT32_MAX || offset > fileLength || offset < 0) {
dprintf(DEBUG_CRITICAL, "Offset is too large.\n");
return -1;
}
if ((size_t)offset + length < length) {
dprintf(DEBUG_CRITICAL, "Length wraparound.\n");
return -1;
}
if ((offset + length) > fileLength) {
length = fileLength - offset;
}
rv = ReadExtent((uint8_t *)extents, fileLength, fileID,
offset, length, base, 0);
if (rv < 0) {
return -1;
}
*length_inout = rv;
return 0;
}
static int
GetCatalogEntryInfo(void *entry, uint32_t *flags, time_t *time, off_t *size)
{
uint32_t tmpTime = 0;
uint64_t tmpSize = 0;
HFSdebug("fetching information for file type 0x%04x", HFSntohs((uint16_t *)entry));
// Get information about the file.
switch (HFSntohs((uint16_t *)entry)) {
case kHFSFolderRecord :
*flags = kFileTypeDirectory;
tmpTime = HFSntohl((uint32_t *)&((HFSCatalogFolder *)entry)->modifyDate);
break;
case kHFSPlusFolderRecord :
*flags = kFileTypeDirectory |
(HFSntohs(&((HFSPlusCatalogFolder *)entry)->bsdInfo.fileMode) & kPermMask);
tmpTime = HFSntohl(&((HFSPlusCatalogFolder *)entry)->contentModDate);
break;
case kHFSFileRecord :
*flags = kFileTypeFlat;
tmpSize = HFSntohl(&((HFSCatalogFile *)entry)->dataLogicalSize);
tmpTime = HFSntohl(&((HFSCatalogFile *)entry)->modifyDate);
break;
case kHFSPlusFileRecord :
*flags = kFileTypeFlat |
(HFSntohs(&((HFSPlusCatalogFile *)entry)->bsdInfo.fileMode) & kPermMask);
tmpSize = HFSntohll(&((HFSPlusCatalogFile *)entry)->dataFork.logicalSize);
tmpTime = HFSntohl(&((HFSPlusCatalogFile *)entry)->contentModDate);
HFSdebug("file size is %lld", tmpSize);
break;
case kHFSFileThreadRecord :
case kHFSPlusFileThreadRecord :
case kHFSFolderThreadRecord :
case kHFSPlusFolderThreadRecord :
*flags = kFileTypeUnknown;
tmpTime = 0;
break;
default:
return -1;
}
if (time != 0) {
// Convert base time from 1904 to 1970.
*time = tmpTime - 2082844800;
}
if (size != 0)
*size = tmpSize;
return 0;
}
static int
ResolvePathToCatalogEntry(const char *filePath, uint32_t *flags, void *entry, uint32_t dirID, off_t *dirIndex, time_t *time, off_t *size)
{
const char *restPath;
int result;
uint32_t cnt, subFolderID = 0;
static uint32_t recursionCnt = 0;
// Copy the file name to gTempStr
cnt = 0;
result = -1;
if (kDirLevelMax <= recursionCnt++) {
HFSdebug("Too many levels of directories");
goto exit;
}
while ((filePath[cnt] != '/') && (filePath[cnt] != '\0'))
cnt++;
if (cnt >= sizeof(gTempStr)) {
HFSdebug("String too long");
goto exit;
}
strlcpy(gTempStr, filePath, cnt + 1);
// Move restPath to the right place.
if (filePath[cnt] != '\0')
cnt++;
restPath = filePath + cnt;
// gTempStr is a name in the current Dir.
// restPath is the rest of the path if any.
HFSdebug("searching for '%s' with remaining path '%s'", gTempStr, restPath);
result = ReadCatalogEntry(gTempStr, dirID, entry, dirIndex);
if (result < 0) {
HFSdebug("not found");
goto exit;
}
if (dirIndex != 0)
HFSdebug("found at index %llx", *dirIndex);
if (GetCatalogEntryInfo(entry, flags, time, size) < 0) {
HFSdebug("bad catalog entry info");
result = -1;
goto exit;
}
// recursively look up child
if ((*flags & kFileTypeMask) == kFileTypeDirectory) {
subFolderID = HFSntohl(&((HFSPlusCatalogFolder *)entry)->folderID);
HFSdebug("looking up '%s' in '%s'", restPath, gTempStr);
result = ResolvePathToCatalogEntry(restPath, flags, entry, subFolderID, dirIndex, time, size);
if (result != 0) {
result = -1;
goto exit;
}
} else {
// if we weren't on the last element of the path, then
// we should have found a directory
if (*restPath != '\0') {
HFSdebug("expected directory");
result = -1;
goto exit;
}
}
exit:
HFSdebug("returning %d", result);
recursionCnt--;
return result;
}
static int
VerifyCatalogKeyBounds(HFSPlusCatalogKey *key, uint8_t *bufend)
{
int ret = 0;
// Verify key length is contained inside the node
if ((uint8_t *)&key->keyLength + sizeof(key->keyLength) > bufend) {
HFSdebug("keyLength outside of node");
ret = -1;
goto exit;
}
// Verify end of key doesn't overflow past end of node
if ((uint8_t *)key + HFSntohs(&key->keyLength) > bufend) {
HFSdebug("Bad keyLength (ends at %p, bufend %p)", (uint8_t *)key + HFSntohs(&key->keyLength), bufend);
ret = -1;
goto exit;
}
// There are actually two lengths to check, the second one gives the
// number of UCS-2 (16-bit) characters in the name
if ((uint8_t *)&key->nodeName.unicode + HFSntohs(&key->nodeName.length) * 2 > bufend) {
HFSdebug("Bad unicode length");
ret = -1;
goto exit;
}
exit:
return ret;
}
static int
GetCatalogEntry(off_t *dirIndex, char *name, size_t nameSize, uint32_t *flags, time_t *time, off_t *size)
{
uint32_t extentSize, nodeSize, curNode, index;
void *extent;
uint8_t *nodeBuf, *testKey, *entry;
HFSPlusCatalogKey *catalogKey;
BTNodeDescriptor *node;
int result;
int ret = 0;
extent = &gHFSPlus->catalogFile.extents;
extentSize = HFSntohll(&gHFSPlus->catalogFile.logicalSize);
nodeSize = HFSntohs(&gBTHeaders[kBTreeCatalog]->nodeSize);
nodeBuf = malloc(nodeSize);
HFSdebug("got nodeBuf %p", nodeBuf);
node = (BTNodeDescriptor *)nodeBuf;
HFSdebug("dirIndex %p/%lld nodeS5ze %u", dirIndex, *dirIndex, nodeSize);
index = *dirIndex % nodeSize;
curNode = *dirIndex / nodeSize;
HFSdebug("working with index %d curNode %d", index, curNode);
// Read the BTree node and get the record for index.
result = ReadExtent(extent, extentSize, kHFSCatalogFileID, curNode * nodeSize, nodeSize, nodeBuf, 1);
if (result < 0 || (unsigned)result != nodeSize) {
ret = -1;
goto exit;
}
if (GetBTreeRecord(index, nodeBuf, nodeSize, &testKey, &entry) != 0) {
ret = -1;
goto exit;
}
catalogKey = (HFSPlusCatalogKey *)testKey;
// Check for overflow
if (VerifyCatalogKeyBounds(catalogKey, nodeBuf + nodeSize) != 0) {
ret = -1;
goto exit;
}
HFSdebug("got BTnode and index record");
if (GetCatalogEntryInfo(entry, flags, time, size) != 0) {
ret = -1;
goto exit;
}
HFSdebug("got entry info");
// Get the file name.
if (utf_encodestr(catalogKey->nodeName.unicode,
HFSntohs((uint16_t *)&catalogKey->nodeName.length),
(uint8_t *)name, nameSize) <= 0) {
HFSdebug("failed to UTF encode filename");
ret = -1;
goto exit;
}
HFSdebug("got file name");
// Update dirIndex.
index++;
if (index == HFSntohs(&node->numRecords)) {
index = 0;
curNode = HFSntohl(&node->fLink);
}
*dirIndex = curNode * nodeSize + index;
HFSdebug("updated forward sibling index");
exit:
free(nodeBuf);
HFSdebug("returning %d", ret);
return ret;
}
static int
ReadCatalogEntry(const char *fileName, uint32_t dirID, void *entry, off_t *dirIndex)
{
uint32_t length;
HFSPlusCatalogKey *hfsPlusKey;
int ret;
length = strlen(fileName);
if (length > HFS_MAXNAMLEN) {
HFSdebug("length overflowed");
return -1;
}
hfsPlusKey = malloc(sizeof(HFSPlusCatalogKey));
// Make the catalog key.
hfsPlusKey->parentID = dirID;
utf_decodestr255((char *)fileName, &hfsPlusKey->nodeName);
HFSdebug("UTF encoded '%s' from length %d to length %d", fileName, length, (int)hfsPlusKey->nodeName.length * 2);
ret = ReadBTreeEntry(kBTreeCatalog, (char *)hfsPlusKey, entry, dirIndex);
free(hfsPlusKey);
return ret;
}
static int
ReadExtentsEntry(uint32_t fileID, uint32_t startBlock, void *entry)
{
HFSPlusExtentKey hfsPlusKey;
// Make the extents key.
hfsPlusKey.forkType = 0;
hfsPlusKey.fileID = fileID;
hfsPlusKey.startBlock = startBlock;
return ReadBTreeEntry(kBTreeExtents, &hfsPlusKey, entry, 0);
}
static int
ReadBTreeEntry(uint32_t btree, void *key, uint8_t *entry, off_t *dirIndex)
{
uint32_t extentSize;
void *extent;
uint16_t extentFile;
BTHeaderRec *headerRec;
uint8_t *nodeBuf;
BTNodeDescriptor *node;
uint32_t nodeSize, entrySize = 0;
uint32_t curNode, index = 0;
int32_t numRecords, lowerBound, upperBound;
uint8_t *testKey, *recordData;
uint32_t level;
int extentLen;
int result = 0;
int ret = 0;
// Figure out which tree is being looked at.
if (btree == kBTreeCatalog) {
HFSdebug("working with the catalog BTree");
extent = &gHFSPlus->catalogFile.extents;
extentSize = HFSntohll(&gHFSPlus->catalogFile.logicalSize);
extentFile = kHFSCatalogFileID;
} else {
HFSdebug("working with the extents BTree");
extent = &gHFSPlus->extentsFile.extents;
extentSize = HFSntohll(&gHFSPlus->extentsFile.logicalSize);
extentFile = kHFSExtentsFileID;
}
headerRec = gBTHeaders[btree];
ASSERT(headerRec != NULL);
curNode = HFSntohl(&headerRec->rootNode);
level = HFSntohs(&headerRec->treeDepth);
nodeSize = HFSntohs(&headerRec->nodeSize);
nodeBuf = malloc(nodeSize);
node = (BTNodeDescriptor *)nodeBuf;
HFSdebug("btree %d headers %p curNode %x nodeSize %d nodeBuf %p node %p",
btree, headerRec, curNode, nodeSize, nodeBuf, node);
while (1) {
HFSdebug("current node %x", curNode);
// Node 0 is the header node, and is never an index or leaf node.
if (curNode == 0) {
ret = -1;
goto exit;
}
// Read the current node.
extentLen = ReadExtent(extent, extentSize, extentFile, curNode * nodeSize, nodeSize, nodeBuf, 1);
if (extentLen < 0 || (unsigned)extentLen != nodeSize) {
HFSdebug("short result from ReadExtent");
ret = -1;
goto exit;
}
// Make sure the node's height and kind are correct, and numRecords is non-zero.
if (node->height != level) {
HFSdebug("Bad node: height is %d; expected %d", node->height, level);
ret = -1;
goto exit;
}
if (node->kind != (level == 1 ? kBTLeafNode : kBTIndexNode)) {
HFSdebug("Bad node: kind is %d; expected %d", node->kind,
(level == 1 ? kBTLeafNode : kBTIndexNode));
ret = -1;
goto exit;
}
numRecords = HFSntohs(&node->numRecords);
if (numRecords <= 0) {
HFSdebug("Bad node: numRecords must be positive");
ret = -1;
goto exit;
}
// Find the matching key.
lowerBound = 0;
upperBound = numRecords - 1;
HFSdebug("node has %d records", upperBound + 1);
while (lowerBound <= upperBound) {
ASSERT(lowerBound >= 0 && upperBound >= 0);
index = ((uint32_t)lowerBound + (uint32_t)upperBound) / 2;
HFSdebug("current record %d (lower %d upper %d)", index, lowerBound, upperBound);
if(GetBTreeRecord(index, nodeBuf, nodeSize, &testKey, &recordData) != 0) {
HFSdebug("GetBTreeRecord failed");
ret = -1;
goto exit;
}
if (btree == kBTreeCatalog) {
// catalog keys contain two lengths and GetBTreeRecord only validates
// the first one, so check both lengths to be sure
if (VerifyCatalogKeyBounds((HFSPlusCatalogKey *)testKey, nodeBuf + nodeSize) != 0) {
HFSdebug("VerifyCatalogKeyBounds failed");
ret = -1;
goto exit;
}
result = CompareHFSPlusCatalogKeys(key, testKey);
} else {
// Unlike catalog keys, extent keys just have the one length
// and GetBTreeRecord validates that length is in the buffer
result = CompareHFSPlusExtentsKeys(key, testKey);
}
HFSdebug("compare result %d", result);
if (result < 0)
upperBound = index - 1; // search < trial
else if (result > 0)
lowerBound = index + 1; // search > trial
else break; // search = trial
}
HFSdebug("best match %d", index);
if (result < 0) {
index = upperBound;
if(GetBTreeRecord(index, nodeBuf, nodeSize, &testKey, &recordData) != 0) {
ret = -1;
goto exit;
}
}
// Found the closest key... Recurse on it if this is an index node.
if (node->kind == kBTIndexNode) {
HFSdebug("recursing on index node from %p", recordData);
curNode = HFSntohl((uint32_t *)recordData);
} else {
break;
}
--level;
}
// Return error if the file was not found.
if (result != 0) {
HFSdebug("file not found");
ret = -1;
goto exit;
}
if (btree == kBTreeCatalog) {
switch (HFSntohs((uint16_t *)recordData)) {
case kHFSFolderRecord : entrySize = 70; break;
case kHFSFileRecord : entrySize = 102; break;
case kHFSFolderThreadRecord : entrySize = 46; break;
case kHFSFileThreadRecord : entrySize = 46; break;
case kHFSPlusFolderRecord : entrySize = 88; break;
case kHFSPlusFileRecord : entrySize = 248; break;
case kHFSPlusFolderThreadRecord : entrySize = 264; break;
case kHFSPlusFileThreadRecord : entrySize = 264; break;
default:
// we don't know how much to copy, so we have to fail
ret = -1;
goto exit;
}
} else {
entrySize = sizeof(HFSPlusExtentRecord);
}
HFSdebug("entrySize %d", entrySize);
// Check for overflow out of the node
if ((uint8_t *)recordData + entrySize > nodeBuf + nodeSize) {
ret = -1;
goto exit;
}
memcpy(entry, recordData, entrySize);
// Update dirIndex.
if (dirIndex != 0) {
index++;
if (index == HFSntohs(&node->numRecords)) {
index = 0;
curNode = HFSntohl(&node->fLink);
}
*dirIndex = curNode * nodeSize + index;
}
exit:
free(nodeBuf);
return ret;
}
static int
GetBTreeRecord(uint32_t index, uint8_t *nodeBuffer, uint32_t nodeSize, uint8_t **key, uint8_t **data)
{
int ret = 0;
uint32_t keySize;
uint32_t recordOffset;
// check index range
if ((2 * index + 2) < index || (2 * index + 2) > nodeSize) {
HFSdebug("index value (%d) out of range", index);
ret = -1;
goto exit;
}
// List of offsets for each record in the BTree node is at the end of the node,
// in reverse order (highest index is closest to the start of the node)
recordOffset = HFSntohs((uint16_t *)(nodeBuffer + (nodeSize - 2 * index - 2)));
*key = nodeBuffer + recordOffset;
// check key ptr range
if (*key < nodeBuffer || *key > (nodeBuffer + nodeSize - 1)) {
HFSdebug("key ptr (%p) out of range", *key);
ret = -1;
goto exit;
}
keySize = HFSntohs((uint16_t *)*key);
*data = *key + 2 + keySize;
// check data ptr range
if (*data < nodeBuffer || *data > (nodeBuffer + nodeSize - 1)) {
HFSdebug("data ptr (%p) out of range", *data);
ret = -1;
goto exit;
}
HFSdebug("record %d at offset %d (%p) keysize %d data at %p",
index, recordOffset, *key, keySize, *data);
exit:
return ret;
}
static int
ReadExtent(uint8_t *extent, uint32_t extentSize, uint32_t extentFile, off_t offset, uint32_t size, void *buffer, bool cache)
{
uint32_t lastOffset, blockNumber, countedBlocks = 0;
uint32_t nextExtent = 0, sizeRead = 0, readSize;
uint32_t nextExtentBlock, currentExtentBlock = 0;
off_t readOffset;
uint32_t extentDensity, sizeofExtent, currentExtentSize;
uint8_t *currentExtent, *extentBuffer = 0, *bufferPos = buffer;
int result = 0;
if (offset < 0) {
return -1;
}
if (offset >= extentSize) {
HFSdebug("offset too large");
return 0;
}
extentDensity = kHFSPlusExtentDensity;
sizeofExtent = sizeof(HFSPlusExtentDescriptor);
lastOffset = offset + size;
HFSdebug("offset %llx size %x", offset, size);
while (offset < lastOffset) {
blockNumber = offset / gBlockSize;
HFSdebug("file blockNumber %x", blockNumber);
// Find the extent for the offset.
for (; ; nextExtent++) {
HFSdebug("nextExtent %x countedBlocks %x", nextExtent, countedBlocks);
if (nextExtent < extentDensity) {
if ((countedBlocks + GetExtentSize(extent, nextExtent) - 1) < blockNumber) {
HFSdebug("skipping early extent %x blocks", GetExtentSize(extent, nextExtent));
countedBlocks += GetExtentSize(extent, nextExtent);
continue;
}
currentExtent = extent + nextExtent * sizeofExtent;
HFSdebug("found offset %llx in extent %x", offset, nextExtent);
break;
}
if (extentBuffer == 0) {
extentBuffer = malloc(sizeofExtent * extentDensity);
HFSdebug("extent buffer at %p", extentBuffer);
}
nextExtentBlock = nextExtent / extentDensity;
if (currentExtentBlock != nextExtentBlock) {
// Special Case: Extents File cannot have an extents-overflow
if (extentFile == kHFSExtentsFileID) {
panic("Attempt to read overflow extents for the Extents-overflow file");
}
// For all other cases: Read the overflow extent entry for this file from the Extents file
if (ReadExtentsEntry(extentFile, countedBlocks, extentBuffer) != 0) {
result = -1;
goto exit;
}
currentExtentBlock = nextExtentBlock;
}
currentExtentSize = GetExtentSize(extentBuffer, nextExtent % extentDensity);
if ((countedBlocks + currentExtentSize - 1) >= blockNumber) {
currentExtent = extentBuffer + sizeofExtent * (nextExtent % extentDensity);
break;
}
countedBlocks += currentExtentSize;
}
readOffset = ((blockNumber - countedBlocks) * gBlockSize) + (offset % gBlockSize);
readSize = GetExtentSize(currentExtent, 0) * gBlockSize - readOffset;
if (readSize > (size - sizeRead))
readSize = size - sizeRead;
if (readSize == 0)
break;
readOffset += (long long)GetExtentStart(currentExtent, 0) * gBlockSize;
HFSdebug("doing cache read %x/%x", (int)readOffset, readSize);
if (CacheRead(gCurrentIH, bufferPos, gAllocationOffset + readOffset, readSize, cache) != readSize) {
result = -1;
goto exit;
}
sizeRead += readSize;
offset += readSize;
bufferPos += readSize;
}
exit:
if (extentBuffer)
free(extentBuffer);
if (result == 0)
return sizeRead;
else
return result;
}
static uint32_t
GetExtentStart(void *extents, uint32_t index)
{
uint32_t start;
HFSPlusExtentDescriptor *hfsPlusExtents = extents;
start = HFSntohl(&hfsPlusExtents[index].startBlock);
return start;
}
static uint32_t
GetExtentSize(void *extents, uint32_t index)
{
uint32_t size;
HFSPlusExtentDescriptor *hfsPlusExtents = extents;
size = HFSntohl(&hfsPlusExtents[index].blockCount);
return size;
}
/*
* key native endian, testKey FS endian
*/
static int
CompareHFSPlusCatalogKeys(void *key, void *testKey)
{
HFSPlusCatalogKey *searchKey, *trialKey;
uint32_t searchParentID, trialParentID;
int result;
searchKey = key;
trialKey = testKey;
searchParentID = searchKey->parentID;
trialParentID = HFSntohl(&trialKey->parentID);
HFSdebug("SearchParentID %x trialParentID %x", searchParentID, trialParentID);
// parent dirID is unsigned
if (searchParentID > trialParentID)
result = 1;
else if (searchParentID < trialParentID)
result = -1;
else {
#if 0
printf(" search name '");
DPrintUTF(searchKey->nodeName.unicode, searchKey->nodeName.length);
printf("' trial name '");
DPrintUTF(trialKey->nodeName.unicode, HFSntohs(&trialKey->nodeName.length));
printf("'\n");
#endif
// parent dirID's are equal, compare names
if ((searchKey->nodeName.length == 0) || (HFSntohs(&trialKey->nodeName.length) == 0)) {
HFSdebug("search name length %d trial name length %d",
searchKey->nodeName.length, HFSntohs(&trialKey->nodeName.length));
result = searchKey->nodeName.length - HFSntohs(&trialKey->nodeName.length);
} else {
result = BinaryUnicodeCompare(&searchKey->nodeName.unicode[0],
searchKey->nodeName.length,
&trialKey->nodeName.unicode[0],
HFSntohs(&trialKey->nodeName.length));
}
}
return result;
}
/*
* key native endian, testKey FS endian
*/
static int
CompareHFSPlusExtentsKeys(void *key, void *testKey)
{
HFSPlusExtentKey *searchKey, *trialKey;
int result;
searchKey = key;
trialKey = testKey;
// assume searchKey < trialKey
result = -1;
if (searchKey->fileID == HFSntohl(&trialKey->fileID)) {
// FileNum's are equal; compare fork types
if (searchKey->forkType == trialKey->forkType) {
// Fork types are equal; compare allocation block number
if (searchKey->startBlock == HFSntohl(&trialKey->startBlock)) {
// Everything is equal
result = 0;
} else {
// Allocation block numbers differ; determine sign
if (searchKey->startBlock > HFSntohl(&trialKey->startBlock))
result = 1;
}
} else {
// Fork types differ; determine sign
if (searchKey->forkType > trialKey->forkType)
result = 1;
}
} else {
// FileNums differ; determine sign
if (searchKey->fileID > HFSntohl(&trialKey->fileID))
result = 1;
}
return result;
}
//
// BinaryUnicodeCompare - Compare two Unicode strings; produce a relative ordering
// Compared using a 16-bit binary comparison (no case folding)
//
static int32_t
BinaryUnicodeCompare (uint16_t * str1, uint32_t length1, uint16_t * str2, uint32_t length2)
{
register uint16_t c1, c2;
int32_t bestGuess;
uint32_t length;
bestGuess = 0;
if (length1 < length2) {
length = length1;
--bestGuess;
} else if (length1 > length2) {
length = length2;
++bestGuess;
} else {
length = length1;
}
while (length--) {
c1 = HFSntohs(str1++);
c2 = HFSntohs(str2++);
if (c1 > c2)
return (1);
if (c1 < c2)
return (-1);
}
return (bestGuess);
}
/*
* UTF-8 (UCS Transformation Format)
*
* The following subset of UTF-8 is used to encode UCS-2 filenames. It
* requires a maximum of three 3 bytes per UCS-2 character. Only the
* shortest encoding required to represent the significant UCS-2 bits
* is legal.
*
* UTF-8 Multibyte Codes
*
* Bytes Bits UCS-2 Min UCS-2 Max UTF-8 Byte Sequence (binary)
* -------------------------------------------------------------------
* 1 7 0x0000 0x007F 0xxxxxxx
* 2 11 0x0080 0x07FF 110xxxxx 10xxxxxx
* 3 16 0x0800 0xFFFF 1110xxxx 10xxxxxx 10xxxxxx
* -------------------------------------------------------------------
*/
/*
* utf_encodestr - Encodes the UCS-2 (Unicode) string at ucsp into a
* null terminated UTF-8 string at utf8p.
*
* inbufsize is the input buffer length in bytes
* ucslen is the number of UCS-2 input characters (not bytes)
* outbufsize is the size of the output buffer in bytes
*
*/
static int
utf_encodestr(const uint16_t *ucsp, unsigned ucslen, uint8_t *utf8p, size_t outbufsize)
{
uint8_t *bufstart;
uint8_t *bufend;
uint16_t ucs_ch;
if (outbufsize <= 0)
return -1;
bufstart = utf8p;
bufend = utf8p + outbufsize - 1;
while (ucslen-- > 0) {
ucs_ch = HFSntohs(ucsp++);
if (ucs_ch < 0x0080) {
if (utf8p >= bufend) {
HFSdebug("1 byte character past end of buffer");
return -1;
}
if (ucs_ch == '\0')
continue; /* skip over embedded NULLs */
*utf8p++ = ucs_ch;
} else if (ucs_ch < 0x800) {
if ((utf8p + 1) >= bufend) {
HFSdebug("2 byte character past end of buffer");
return -1;
}
*utf8p++ = (ucs_ch >> 6) | 0xc0;
*utf8p++ = (ucs_ch & 0x3f) | 0x80;
} else {
if ((utf8p + 2) >= bufend) {
HFSdebug("3 byte character past end of buffer");
return -1;
}
*utf8p++ = (ucs_ch >> 12) | 0xe0;
*utf8p++ = ((ucs_ch >> 6) & 0x3f) | 0x80;
*utf8p++ = ((ucs_ch) & 0x3f) | 0x80;
}
}
*utf8p = '\0';
return utf8p - bufstart;
}
static void
utf_decodestr255(const char *utf8p, struct HFSUniStr255 *ucsstrp)
{
utf_decodestr(utf8p, ucsstrp->unicode, &ucsstrp->length, sizeof(ucsstrp->unicode));
}
/*
* utf_decodestr - Decodes the null terminated UTF-8 string at
* utf8p into a UCS-2 (Unicode) string at ucsp.
*
* ucslen is the number of UCS-2 output characters (not bytes)
* bufsize is the size of the output buffer in bytes
*/
static void
utf_decodestr(const char *utf8p, uint16_t *ucsp, uint16_t *ucslen, uint32_t bufsize)
{
uint16_t *bufstart;
uint16_t *bufend;
uint16_t ucs_ch;
uint8_t byte;
bufstart = ucsp;
bufend = (uint16_t *)((uint8_t *)ucsp + bufsize);
while ((byte = *utf8p++) != '\0') {
if (ucsp >= bufend)
break;
/* check for ascii */
if (byte < 0x80) {
ucs_ch = byte;
*ucsp++ = HFShtons(ucs_ch);
continue;
}
switch (byte & 0xf0) {
/* 2 byte sequence*/
case 0xc0:
case 0xd0:
/* extract bits 6 - 10 from first byte */
ucs_ch = (byte & 0x1F) << 6;
break;
/* 3 byte sequence*/
case 0xe0:
/* extract bits 12 - 15 from first byte */
ucs_ch = (byte & 0x0F) << 6;
/* extract bits 6 - 11 from second byte */
if (((byte = *utf8p++) & 0xc0) != 0x80)
goto stop;
ucs_ch += (byte & 0x3F);
ucs_ch <<= 6;
break;
default:
goto stop;
}
/* extract bits 0 - 5 from final byte */
if (((byte = *utf8p++) & 0xc0) != 0x80)
goto stop;
ucs_ch += (byte & 0x3F);
*ucsp++ = HFShtons(ucs_ch);
}
stop:
*ucslen = ucsp - bufstart;
}
Reference in New Issue View Git Blame Copy Permalink