#if HFS_EXTENTS_TEST
#include "hfs_extents_test.h"
#include "hfs_extents.h"
#else
#include "hfs_extents.h"
static uint32_t hfs_total_blocks(const HFSPlusExtentDescriptor *ext, int count);
static errno_t hfs_ext_iter_next_group(struct hfs_ext_iter *iter);
static errno_t hfs_ext_iter_update(struct hfs_ext_iter *iter,
HFSPlusExtentDescriptor *extents,
int count,
HFSPlusExtentRecord cat_extents);
static errno_t hfs_ext_iter_check_group(hfs_ext_iter_t *iter);
#endif
#define CHECK(x, var, goto_label) \
do { \
var = (x); \
if (var) { \
printf("%s:%u error: %d\n", __func__, __LINE__, var); \
goto goto_label; \
} \
} while (0)
#define min(a,b) \
({ typeof (a) _a = (a); typeof (b) _b = (b); _a < _b ? _a : _b; })
static __attribute__((pure))
const HFSPlusExtentKey *hfs_ext_iter_key(const hfs_ext_iter_t *iter)
{
return (const HFSPlusExtentKey *)&iter->bt_iter.key;
}
static __attribute__((pure))
HFSPlusExtentKey *hfs_ext_iter_key_mut(hfs_ext_iter_t *iter)
{
return (HFSPlusExtentKey *)&iter->bt_iter.key;
}
uint32_t hfs_total_blocks(const HFSPlusExtentDescriptor *extents, int count)
{
uint32_t block_count = 0;
for (int i = 0; i < count; ++i)
block_count += extents[i].blockCount;
return block_count;
}
errno_t hfs_ext_iter_check_group(hfs_ext_iter_t *iter)
{
filefork_t *ff = VTOF(iter->vp);
const HFSPlusExtentKey *key = hfs_ext_iter_key(iter);
uint32_t count = 0;
int i;
for (i = 0; i < kHFSPlusExtentDensity; ++i) {
if (!iter->group[i].blockCount)
break;
count += iter->group[i].blockCount;
}
if (i < kHFSPlusExtentDensity) {
iter->last_in_fork = true;
if (key->startBlock + count != ff_allocblocks(ff))
goto bad;
for (++i; i < kHFSPlusExtentDensity; ++i) {
if (iter->group[i].blockCount)
goto bad;
}
} else {
if (key->startBlock + count > ff_allocblocks(ff))
goto bad;
iter->last_in_fork = (key->startBlock + count == ff_allocblocks(ff));
}
iter->group_block_count = count;
return 0;
bad:
#if DEBUG
printf("hfs_ext_iter_check_group: bad group; start: %u, total blocks: %u\n",
key->startBlock, ff_allocblocks(ff));
for (int j = 0; j < kHFSPlusExtentDensity; ++j) {
printf("%s<%u, %u>", j ? ", " : "",
iter->group[j].startBlock, iter->group[j].blockCount);
}
printf("\n");
#endif
return ESTALE;
}
static void hfs_ext_iter_copy(const hfs_ext_iter_t *src, hfs_ext_iter_t *dst)
{
dst->vp = src->vp;
memcpy(&dst->bt_iter.key, &src->bt_iter.key, sizeof(HFSPlusExtentKey));
dst->file_block = src->file_block;
dst->ndx = src->ndx;
dst->bt_iter.hint = src->bt_iter.hint;
dst->bt_iter.version = 0;
dst->bt_iter.reserved = 0;
dst->bt_iter.hitCount = 0;
dst->bt_iter.maxLeafRecs = 0;
}
bool hfs_ext_iter_is_catalog_extents(hfs_ext_iter_t *iter)
{
return hfs_ext_iter_key(iter)->startBlock == 0;
}
#if !HFS_EXTENTS_TEST
errno_t hfs_ext_find(vnode_t vp, off_t offset, hfs_ext_iter_t *iter)
{
errno_t ret;
hfsmount_t *hfsmp = VTOHFS(vp);
iter->vp = vp;
uint32_t end_block, index;
HFSPlusExtentKey *key = hfs_ext_iter_key_mut(iter);
filefork_t *ff = VTOF(vp);
CHECK(SearchExtentFile(hfsmp, ff, offset,
key, iter->group, &index,
&iter->bt_iter.hint.nodeNum, &end_block), ret, exit);
iter->ndx = index;
iter->file_block = end_block - iter->group[index].blockCount;
if (!key->keyLength) {
key->keyLength = kHFSPlusExtentKeyMaximumLength;
key->forkType = (VNODE_IS_RSRC(iter->vp)
? kHFSResourceForkType : kHFSDataForkType);
key->pad = 0;
key->fileID = VTOC(iter->vp)->c_fileid;
key->startBlock = 0;
}
CHECK(hfs_ext_iter_check_group(iter), ret, exit);
ret = 0;
exit:
return MacToVFSError(ret);
}
static uint32_t hfs_ext_iter_next_group_block(const hfs_ext_iter_t *iter)
{
const HFSPlusExtentKey *key = hfs_ext_iter_key(iter);
return key->startBlock + iter->group_block_count;
}
static errno_t hfs_ext_iter_next_group(hfs_ext_iter_t *iter)
{
errno_t ret;
hfsmount_t *hfsmp = VTOHFS(iter->vp);
filefork_t * const tree = hfsmp->hfs_extents_cp->c_datafork;
HFSPlusExtentKey *key = hfs_ext_iter_key_mut(iter);
const bool catalog_extents = hfs_ext_iter_is_catalog_extents(iter);
const uint32_t next_block = hfs_ext_iter_next_group_block(iter);
FSBufferDescriptor fbd = {
.bufferAddress = &iter->group,
.itemCount = 1,
.itemSize = sizeof(iter->group)
};
if (catalog_extents) {
key->startBlock = next_block;
CHECK(BTSearchRecord(tree, &iter->bt_iter, &fbd, NULL,
&iter->bt_iter), ret, exit);
} else {
const uint32_t file_id = key->fileID;
const uint8_t fork_type = key->forkType;
CHECK(BTIterateRecord(tree, kBTreeNextRecord, &iter->bt_iter,
&fbd, NULL), ret, exit);
if (key->fileID != file_id
|| key->forkType != fork_type
|| key->startBlock != next_block) {
ret = ESTALE;
goto exit;
}
}
iter->file_block = key->startBlock;
iter->ndx = 0;
CHECK(hfs_ext_iter_check_group(iter), ret, exit);
ret = 0;
exit:
return MacToVFSError(ret);
}
errno_t hfs_ext_iter_update(hfs_ext_iter_t *iter,
HFSPlusExtentDescriptor *extents,
int count,
HFSPlusExtentRecord cat_extents)
{
errno_t ret;
hfsmount_t *hfsmp = VTOHFS(iter->vp);
cnode_t *cp = VTOC(iter->vp);
HFSPlusExtentKey *key = hfs_ext_iter_key_mut(iter);
int ndx = 0;
if (!extents)
extents = iter->group;
if (count % kHFSPlusExtentDensity) {
bzero(&extents[count], (kHFSPlusExtentDensity
- (count % 8)) * sizeof(*extents));
}
if (hfs_ext_iter_is_catalog_extents(iter)) {
if (cat_extents)
hfs_ext_copy_rec(extents, cat_extents);
struct cat_fork fork;
hfs_fork_copy(&fork, &VTOF(iter->vp)->ff_data, extents);
hfs_prepare_fork_for_update(VTOF(iter->vp), &fork, &fork, hfsmp->blockSize);
bool is_rsrc = VNODE_IS_RSRC(iter->vp);
CHECK(cat_update(hfsmp, &cp->c_desc, &cp->c_attr,
is_rsrc ? NULL : &fork,
is_rsrc ? &fork : NULL), ret, exit);
key->startBlock = hfs_total_blocks(extents, kHFSPlusExtentDensity);
ndx += 8;
}
for (; ndx < count; ndx += 8) {
filefork_t * const tree = hfsmp->hfs_extents_cp->c_datafork;
FSBufferDescriptor fbd = {
.bufferAddress = &extents[ndx],
.itemCount = 1,
.itemSize = sizeof(HFSPlusExtentRecord)
};
CHECK(BTInsertRecord(tree, &iter->bt_iter, &fbd,
sizeof(HFSPlusExtentRecord)), ret, exit);
key->startBlock += hfs_total_blocks(&extents[ndx], kHFSPlusExtentDensity);
}
ret = 0;
exit:
return ret;
}
#endif // !HFS_EXTENTS_TEST
static void push_ext(HFSPlusExtentDescriptor *extents, int *count,
const HFSPlusExtentDescriptor *ext)
{
if (!ext->blockCount)
return;
if (*count && hfs_ext_end(&extents[*count - 1]) == ext->startBlock)
extents[*count - 1].blockCount += ext->blockCount;
else
extents[(*count)++] = *ext;
}
errno_t hfs_ext_replace(hfsmount_t *hfsmp, vnode_t vp,
uint32_t file_block,
const HFSPlusExtentDescriptor *repl,
int repl_count,
HFSPlusExtentRecord catalog_extents)
{
errno_t ret;
filefork_t * const tree = hfsmp->hfs_extents_cp->c_datafork;
hfs_ext_iter_t *iter_in = NULL, *iter_out;
HFSPlusExtentDescriptor *extents = NULL;
HFSPlusExtentDescriptor *roll_back_extents = NULL;
int roll_back_count = 0;
const uint32_t end_file_block = file_block + hfs_total_blocks(repl, repl_count);
filefork_t *ff = VTOF(vp);
catalog_extents[0].blockCount = 0;
if (end_file_block > ff_allocblocks(ff)) {
ret = EINVAL;
goto exit;
}
MALLOC(iter_in, hfs_ext_iter_t *, sizeof(*iter_in) * 2, M_TEMP, M_WAITOK);
iter_out = iter_in + 1;
HFSPlusExtentKey *key_in = hfs_ext_iter_key_mut(iter_in);
off_t offset = hfs_blk_to_bytes(file_block, hfsmp->blockSize);
if (offset > 0)
--offset;
CHECK(hfs_ext_find(vp, offset, iter_in), ret, exit);
const uint32_t start_group_block = key_in->startBlock;
const int max_roll_back_extents = 128 * 1024 / sizeof(HFSPlusExtentDescriptor);
MALLOC(roll_back_extents, HFSPlusExtentDescriptor *, 128 * 1024, M_TEMP, M_WAITOK);
iter_in->ndx = 0;
hfs_ext_iter_copy(iter_in, iter_out);
const int buffered_extents = roundup(3 * kHFSPlusExtentDensity + repl_count,
kHFSPlusExtentDensity);
MALLOC(extents, HFSPlusExtentDescriptor *,
sizeof(*extents) * buffered_extents, M_TEMP, M_WAITOK);
int count = 0;
uint32_t block = start_group_block;
for (;;) {
if (!iter_in->ndx) {
hfs_ext_copy_rec(iter_in->group, &roll_back_extents[roll_back_count]);
roll_back_count += kHFSPlusExtentDensity;
if (!hfs_ext_iter_is_catalog_extents(iter_in)) {
CHECK(BTDeleteRecord(tree, &iter_in->bt_iter), ret, exit);
}
}
HFSPlusExtentDescriptor *ext = &iter_in->group[iter_in->ndx];
if (!ext->blockCount) {
goto finish;
}
if (block + ext->blockCount <= file_block || block >= end_file_block) {
push_ext(extents, &count, ext);
} else {
HFSPlusExtentDescriptor dealloc_ext = *ext;
if (block <= file_block) {
uint32_t trimmed_len = file_block - block;
if (trimmed_len) {
push_ext(extents, &count,
&(HFSPlusExtentDescriptor){ ext->startBlock,
trimmed_len });
dealloc_ext.startBlock += trimmed_len;
dealloc_ext.blockCount -= trimmed_len;
}
for (int i = 0; i < repl_count; ++i)
push_ext(extents, &count, &repl[i]);
}
if (block + ext->blockCount > end_file_block) {
uint32_t overlap = end_file_block - block;
push_ext(extents, &count,
&(HFSPlusExtentDescriptor){ ext->startBlock + overlap,
ext->blockCount - overlap });
dealloc_ext.blockCount = (ext->startBlock + overlap
- dealloc_ext.startBlock);
}
CHECK(BlockDeallocate(hfsmp, dealloc_ext.startBlock,
dealloc_ext.blockCount, 0), ret, exit);
}
block += ext->blockCount;
if (++iter_in->ndx >= kHFSPlusExtentDensity) {
if (block >= end_file_block) {
if (iter_in->last_in_fork || !(count % kHFSPlusExtentDensity)) {
goto finish;
}
if (count + kHFSPlusExtentDensity > buffered_extents
|| (roll_back_count
+ kHFSPlusExtentDensity > max_roll_back_extents)) {
break;
}
}
CHECK(hfs_ext_iter_next_group(iter_in), ret, exit);
}
}
int stop_at = 0;
for (;;) {
int in = count - 1;
count = roundup(count, kHFSPlusExtentDensity);
int out = count - 1;
do {
if (out <= in) {
goto finish;
}
extents[out].blockCount = 1;
extents[out].startBlock = (extents[in].startBlock
+ extents[in].blockCount - 1);
--out;
} while (--extents[in].blockCount || --in >= stop_at);
if (roll_back_count + kHFSPlusExtentDensity > max_roll_back_extents) {
ret = ENOSPC;
goto exit;
}
++out;
memmove(&extents[stop_at], &extents[out],
(count - out) * sizeof(*extents));
count -= out - stop_at;
CHECK(hfs_ext_iter_next_group(iter_in), ret, exit);
hfs_ext_copy_rec(iter_in->group, &roll_back_extents[roll_back_count]);
roll_back_count += kHFSPlusExtentDensity;
CHECK(BTDeleteRecord(tree, &iter_in->bt_iter), ret, exit);
if (iter_in->last_in_fork) {
int old_count = count;
count = 0;
for (int i = 0; i < old_count; ++i)
push_ext(extents, &count, &extents[i]);
const int flush_count = buffered_extents - kHFSPlusExtentDensity;
if (count > flush_count) {
CHECK(hfs_ext_iter_update(iter_out, extents,
flush_count, catalog_extents), ret, exit);
memmove(&extents[0], &extents[flush_count],
(count - flush_count) * sizeof(*extents));
count -= flush_count;
}
for (int i = 0; i < kHFSPlusExtentDensity; ++i) {
HFSPlusExtentDescriptor *ext = &iter_in->group[i];
if (!ext->blockCount)
break;
push_ext(extents, &count, ext);
}
goto finish;
}
if (count > buffered_extents - kHFSPlusExtentDensity) {
CHECK(hfs_ext_iter_update(iter_out, extents,
kHFSPlusExtentDensity,
catalog_extents), ret, exit);
memmove(&extents[0], &extents[kHFSPlusExtentDensity],
(count - kHFSPlusExtentDensity) * sizeof(*extents));
count -= kHFSPlusExtentDensity;
}
stop_at = count;
hfs_ext_copy_rec(iter_in->group, &extents[count]);
count += kHFSPlusExtentDensity;
}
finish:
CHECK(hfs_ext_iter_update(iter_out, extents, count,
catalog_extents), ret, exit);
CHECK(BTFlushPath(hfsmp->hfs_catalog_cp->c_datafork), ret, exit);
CHECK(BTFlushPath(hfsmp->hfs_extents_cp->c_datafork), ret, exit);
exit:
if (ret && roll_back_count) {
#define RB_FAILED \
do { \
printf("hfs_ext_replace:%u: roll back failed\n", __LINE__); \
hfs_mark_inconsistent(hfsmp, HFS_ROLLBACK_FAILED); \
goto roll_back_failed; \
} while (0)
HFSPlusExtentKey *key_out = hfs_ext_iter_key_mut(iter_out);
key_in->startBlock = start_group_block;
if (!key_in->startBlock && key_out->startBlock > key_in->startBlock) {
key_in->startBlock += hfs_total_blocks(catalog_extents,
kHFSPlusExtentDensity);
}
if (key_out->startBlock > key_in->startBlock) {
FSBufferDescriptor fbd = {
.bufferAddress = &iter_in->group,
.itemCount = 1,
.itemSize = sizeof(iter_in->group)
};
if (BTSearchRecord(tree, &iter_in->bt_iter, &fbd, NULL,
&iter_in->bt_iter)) {
RB_FAILED;
}
for (;;) {
if (BTDeleteRecord(tree, &iter_in->bt_iter))
RB_FAILED;
key_in->startBlock += hfs_total_blocks(iter_in->group,
kHFSPlusExtentDensity);
if (key_in->startBlock >= key_out->startBlock)
break;
if (BTSearchRecord(tree, &iter_in->bt_iter, &fbd, NULL,
&iter_in->bt_iter)) {
RB_FAILED;
}
}
}
key_out->startBlock = start_group_block;
if (hfs_ext_iter_update(iter_out, roll_back_extents, roll_back_count,
catalog_extents)) {
RB_FAILED;
}
const uint32_t end_block = min(block, end_file_block);
block = start_group_block;
for (int i = 0; i < roll_back_count && block < end_block; ++i) {
HFSPlusExtentDescriptor *ext = &roll_back_extents[i];
if (block + ext->blockCount <= file_block)
continue;
HFSPlusExtentDescriptor alloc_ext = *ext;
if (block <= file_block) {
uint32_t trimmed_len = file_block - block;
alloc_ext.startBlock += trimmed_len;
alloc_ext.blockCount -= trimmed_len;
}
if (block + ext->blockCount > end_file_block) {
uint32_t overlap = end_file_block - block;
alloc_ext.blockCount = (ext->startBlock + overlap
- alloc_ext.startBlock);
}
if (hfs_block_alloc(hfsmp, &alloc_ext, HFS_ALLOC_ROLL_BACK, NULL))
RB_FAILED;
block += ext->blockCount;
}
if (BTFlushPath(hfsmp->hfs_catalog_cp->c_datafork)
|| BTFlushPath(hfsmp->hfs_extents_cp->c_datafork)) {
RB_FAILED;
}
}
roll_back_failed:
FREE(iter_in, M_TEMP);
FREE(extents, M_TEMP);
FREE(roll_back_extents, M_TEMP);
return MacToVFSError(ret);
}