[apple/hfs.git] / tests / hfs_extents_test.c

/*
 * Copyright (c) 2014-2015 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The 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, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

#include "hfs_extents_test.h"
#include "../core/hfs_extents.h"

typedef struct extent_group {
	LIST_ENTRY(extent_group) chain;
	uint32_t start_block;
	HFSPlusExtentRecord extents;
	bool deleted;
} extent_group_t;

int32_t BTDeleteRecord(filefork_t    *ff,
					   BTreeIterator *iterator)
{
	(void)ff;

	assert(!iterator->group->deleted);

	LIST_REMOVE(iterator->group, chain);

	iterator->group->deleted = true;

	return 0;
}

errno_t hfs_ext_iter_next_group(struct hfs_ext_iter *iter)
{
	off_t offset = (iter->bt_iter.key.startBlock + iter->group_block_count) * 4096;

	errno_t ret = hfs_ext_find(iter->vp, offset, iter);

	if (ret)
		return ret;

	if (iter->bt_iter.key.startBlock != offset / 4096)
		return ESTALE;

	return 0;
}

errno_t hfs_ext_iter_update(hfs_ext_iter_t *iter,
							HFSPlusExtentDescriptor *extents,
							int count,
							HFSPlusExtentRecord cat_extents)
{
	if (count % kHFSPlusExtentDensity) {
		// Zero out last group
		int to_zero = kHFSPlusExtentDensity - (count % 8);
		bzero(&extents[count], to_zero * sizeof(*extents));
		count += to_zero;
	}

	extent_group_t *group = NULL;

	if (!iter->bt_iter.key.startBlock) {
		memcpy(cat_extents, extents, sizeof(HFSPlusExtentRecord));
		group = LIST_FIRST(&iter->vp->ffork->groups);
		hfs_ext_copy_rec(extents, group->extents);

		iter->bt_iter.key.startBlock += hfs_total_blocks(extents, 8);

		count -= 8;
		extents += 8;
	} else {
		extent_group_t *next;
		LIST_FOREACH(next, &iter->vp->ffork->groups, chain) {
			if (iter->bt_iter.key.startBlock < next->start_block)
				break;
			group = next;
		}
	}

	iter->bt_iter.group = NULL;

	while (count > 0) {
		extent_group_t *new_group = malloc(sizeof(*new_group));
		hfs_ext_copy_rec(extents, new_group->extents);
		new_group->start_block = iter->bt_iter.key.startBlock;
		new_group->deleted = false;

		if (group) {
			LIST_INSERT_AFTER(group, new_group, chain);
		} else
			LIST_INSERT_HEAD(&iter->vp->ffork->groups, new_group, chain);
		group = new_group;

		iter->bt_iter.key.startBlock += hfs_total_blocks(extents, 8);

		count -= 8;
		extents += 8;
	}

	return 0;
}

errno_t hfs_ext_find(vnode_t vp, off_t offset, hfs_ext_iter_t *iter)
{
	(void)vp;
	const uint32_t block = (uint32_t)(offset / 4096);

	iter->vp = vp;
	extent_group_t *next, *group = NULL;
	LIST_FOREACH(next, &vp->ffork->groups, chain) {
		if (block < next->start_block)
			break;
		group = next;
	}

	if (!group)
		return ENOENT;

	iter->file_block = iter->bt_iter.key.startBlock = group->start_block;
	iter->bt_iter.group = group;

	for (iter->ndx = 0; iter->ndx < 8; ++iter->ndx) {
		HFSPlusExtentDescriptor *ext = &group->extents[iter->ndx];
		if (iter->file_block + ext->blockCount > block) {
			hfs_ext_copy_rec(group->extents, iter->group);
			return hfs_ext_iter_check_group(iter);
		}
		iter->file_block += ext->blockCount;
	}

	return ENOENT;
}

void dump_extents(struct extent_groups *groups)
{
	extent_group_t *group;
	int i = 0;

	LIST_FOREACH(group, groups, chain) {
		for (int j = 0; j < 8; ++j) {
			HFSPlusExtentDescriptor *ext = &group->extents[j];
			if (!ext->blockCount) {
				// Make sure all the reset are NULL
				if (LIST_NEXT(group, chain))
					goto keep_going;

				for (int k = j; k < 8; ++k) {
					if (group->extents[k].startBlock
						|| group->extents[k].blockCount) {
						goto keep_going;
					}
				}

				break;
			}

		keep_going:

			printf("%s{ %u, %u }", (i == 0 ? "" : i % 4 == 0 ? ",\n" : ", "),
				   ext->startBlock, ext->blockCount);
			++i;
		}
	}
	printf("\n");
}

void check_extents(unsigned line, vnode_t vnode,
				   const HFSPlusExtentDescriptor *extents, int count)
{
	uint32_t block = 0;
	extent_group_t *group;
	LIST_FOREACH(group, &vnode->ffork->groups, chain) {
		if (group->start_block != block)
			goto bad;
		int cnt = MIN(count, 8);
		if (memcmp(group->extents, extents, cnt * sizeof(*extents)))
			goto bad;
		while (cnt < 8) {
			if (group->extents[cnt].startBlock || group->extents[cnt].blockCount)
				goto bad;
			++cnt;
		}
		if ((count -= 8) <= 0)
			break;
		block += hfs_total_blocks(extents, 8);
		extents += 8;
	}

	if (LIST_NEXT(group, chain))
		goto bad;

	return;

bad:

	printf("hfs_extents_test:%u: error: unexpected extents:\n", line);
	dump_extents(&vnode->ffork->groups);
	exit(1);
}

int main(void)
{
	cnode_t cnode = {};
	hfsmount_t mount = {
		.blockSize = 4096,
		.hfs_extents_cp = &cnode,
	};
	filefork_t ffork = {
		.ff_blocks			= 200,
		.ff_unallocblocks	= 100,
		.groups = LIST_HEAD_INITIALIZER(ffork.groups),
	};
	struct vnode vnode = {
		.ffork = &ffork,
		.mount = &mount,
		.is_rsrc = false,
		.cnode = &cnode,
	};

	extent_group_t group = {
		.extents = { { 100, 100 } },
	};

	LIST_INSERT_HEAD(&ffork.groups, &group, chain);

	HFSPlusExtentRecord cat_extents;

#define E(...)			(HFSPlusExtentDescriptor[]) { __VA_ARGS__ }
#define lengthof(x)		(sizeof(x) / sizeof(*x))

#define CHECK_EXTENTS(...)										\
	do {														\
		HFSPlusExtentDescriptor extents_[] = __VA_ARGS__;		\
		check_extents(__LINE__, &vnode, extents_,				\
					  lengthof(extents_));						\
	} while (0)

#define CHECK_REPLACE(file_block, repl, expected)								\
	do {																		\
		HFSPlusExtentDescriptor repl_[] = repl;									\
		hfs_ext_replace(&mount, &vnode, file_block, repl_,						\
						lengthof(repl_), cat_extents);							\
		CHECK_EXTENTS(expected);												\
	} while (0)
	
	CHECK_REPLACE(10, E({ 200, 10 }),
				  E({ 100, 10 }, { 200, 10 }, { 120, 80 }));

	CHECK_REPLACE(5, E({ 300, 10 }),
				  E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 120, 80 }));

	CHECK_REPLACE(20, E({ 400, 1 }),
				  E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
					{ 121, 79 }));

	CHECK_REPLACE(21, E({ 402, 1 }),
				  E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
					{ 402, 1 }, { 122, 78 }));
	
	CHECK_REPLACE(22, E({ 404, 1 }),
				  E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
					{ 402, 1 }, { 404, 1 }, { 123, 77 }));

	CHECK_REPLACE(23, E({ 406, 1 }),
				  E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
					{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 124, 76 }));

	CHECK_REPLACE(24, E({ 408, 1 }),
				  E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
					{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
					{ 125, 75 }));

	/*
	 * OK, now we won't see any padding until we get the number of extents
	 * over 32.  So let's get to that point now.
	 */

	for (int i = 25, j = 500; i < 25 + 24; ++i, j += 2) {
		hfs_ext_replace(&mount, &vnode, i, E({ j, 1 }),
						1, cat_extents);
	}

	CHECK_EXTENTS(E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
					{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
					{ 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
					{ 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
					{ 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
					{ 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
					{ 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
					{ 540, 1 }, { 542, 1 }, { 544, 1 }, { 546, 1 },
					{ 149, 51 }));

	/*
	 * So if we replace an extent in the first group, we should see it pad using
	 * the 205 extent and some of the 300 extent.
	 */

	CHECK_REPLACE(2, E({ 600, 1 }),
				  E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
					{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
					{ 207, 1 }, { 208, 1 }, { 209, 1 }, { 400, 1 },
					{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
					{ 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
					{ 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
					{ 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
					{ 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
					{ 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
					{ 540, 1 }, { 542, 1 }, { 544, 1 }, { 546, 1 },
					{ 149, 51 }));

	/*
	 * Now try and test the case where it fails to pad and is forced to move
	 * to the next group.  First, merge the 544 and 546 extents to reduce
	 * the number of extents by 1.
	 */

	CHECK_REPLACE(47, E({ 700, 2 }),
				  E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
					{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
					{ 207, 1 }, { 208, 1 }, { 209, 1 }, { 400, 1 },
					{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
					{ 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
					{ 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
					{ 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
					{ 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
					{ 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
					{ 540, 1 }, { 542, 1 }, { 700, 2 }, { 149, 51 }));

	// Now force 207-209 to be merged

	CHECK_REPLACE(21, E({ 800, 1 }),
				  E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
					{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
					{ 207, 3 }, { 400, 1 }, { 800, 1 }, { 404, 1 },
					{ 406, 1 }, { 408, 1 }, { 500, 1 }, { 502, 1 },
					{ 504, 1 }, { 506, 1 }, { 508, 1 }, { 510, 1 },
					{ 512, 1 }, { 514, 1 }, { 516, 1 }, { 518, 1 },
					{ 520, 1 }, { 522, 1 }, { 524, 1 }, { 526, 1 },
					{ 528, 1 }, { 530, 1 }, { 532, 1 }, { 534, 1 },
					{ 536, 1 }, { 538, 1 }, { 540, 1 }, { 542, 1 },
					{ 700, 2 }, { 149, 51 }));

	// Now let's push the last extent into a new group

	CHECK_REPLACE(50, E({ 800, 1 }),
				  E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
					{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
					{ 207, 3 }, { 400, 1 }, { 800, 1 }, { 404, 1 },
					{ 406, 1 }, { 408, 1 }, { 500, 1 }, { 502, 1 },
					{ 504, 1 }, { 506, 1 }, { 508, 1 }, { 510, 1 },
					{ 512, 1 }, { 514, 1 }, { 516, 1 }, { 518, 1 },
					{ 520, 1 }, { 522, 1 }, { 524, 1 }, { 526, 1 },
					{ 528, 1 }, { 530, 1 }, { 532, 1 }, { 534, 1 },
					{ 536, 1 }, { 538, 1 }, { 540, 1 }, { 542, 1 },
					{ 700, 2 }, { 149, 1 }, { 800, 1 }, { 151, 49 }));

	CHECK_REPLACE(52, E({ 802, 1 }),
				  E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
					{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
					{ 207, 3 }, { 400, 1 }, { 800, 1 }, { 404, 1 },
					{ 406, 1 }, { 408, 1 }, { 500, 1 }, { 502, 1 },
					{ 504, 1 }, { 506, 1 }, { 508, 1 }, { 510, 1 },
					{ 512, 1 }, { 514, 1 }, { 516, 1 }, { 518, 1 },
					{ 520, 1 }, { 522, 1 }, { 524, 1 }, { 526, 1 },
					{ 528, 1 }, { 530, 1 }, { 532, 1 }, { 534, 1 },
					{ 536, 1 }, { 538, 1 }, { 540, 1 }, { 542, 1 },
					{ 700, 2 }, { 149, 1 }, { 800, 1 }, { 151, 1 },
					{ 802, 1 }, { 153, 47 }));

	/*
	 * And now if we split the 207 extent, it will fail to pad within the
	 * 32 extents and so it will be forced to pull in more extents.
	 */

	CHECK_REPLACE(18, E({ 900, 1 }),
				  E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
					{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
					{ 207, 1 }, { 900, 1 }, { 209, 1 }, { 400, 1 },
					{ 800, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
					{ 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
					{ 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
					{ 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
					{ 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
					{ 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
					{ 540, 1 }, { 542, 1 }, { 700, 2 }, { 149, 1 },
					{ 800, 1 }, { 151, 1 }, { 802, 1 }, { 153, 47 }));

	// Some tests covering replacing the beginning and end

	CHECK_REPLACE(0, E({ 100, 100 }), E({ 100, 100 }));
	CHECK_REPLACE(10, E({ 200, 90 }), E({ 100, 10 }, { 200, 90 }));
	CHECK_REPLACE(0, E({ 300, 10 }), E({ 300, 10 }, { 200, 90 }));

	// Test replacing with multiple extents
	CHECK_REPLACE(5, E({ 400, 1 }, { 400, 2 }),
				  E({ 300, 5 }, { 400, 1 }, { 400, 2 }, { 308, 2 }, { 200, 90 }));

	/*
	 * Test an unlikely case where we have lots of extents that could
	 * be coalesced.  When replacing extents here, we can't coalesce
	 * all of them because we will not be able to roll back.
	 */

	// First, set things up
	hfs_ext_iter_t iter;

	assert(!hfs_ext_find(&vnode, 0, &iter));

	for (int i = 0; i < 32768; i += 8) {
		HFSPlusExtentRecord r = { { i, 1 }, { i + 1, 1 }, { i + 2, 1 }, { i + 3, 1 }, 
								  { i + 4, 1 }, { i + 5, 1 }, { i + 6, 1 }, { i + 7, 1 } };

		hfs_ext_iter_update(&iter, r, 8, cat_extents);
	}

	ffork.ff_blocks = 32768;
	ffork.ff_unallocblocks = 0;

	/*
	 * Now we have 32768 extents that could be coalesced.  Check the
	 * following succeeds.
	 */
	assert(!hfs_ext_replace(&mount, &vnode, 0, 
							E({ 1, 8 }), 1, cat_extents));

	printf("[PASSED] hfs_extents_test\n");

	return 0;
}
Commit	Line	Data
558d2836 A	1	/*
	2	* Copyright (c) 2014-2015 Apple Inc. All rights reserved.
	3	*
	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
	14	*
	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
	25	*
	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
	27	*/
	28
	29	#include "hfs_extents_test.h"
	30	#include "../core/hfs_extents.h"
	31
	32	typedef struct extent_group {
	33	LIST_ENTRY(extent_group) chain;
	34	uint32_t start_block;
	35	HFSPlusExtentRecord extents;
	36	bool deleted;
	37	} extent_group_t;
	38
	39	int32_t BTDeleteRecord(filefork_t *ff,
	40	BTreeIterator *iterator)
	41	{
	42	(void)ff;
	43
	44	assert(!iterator->group->deleted);
	45
	46	LIST_REMOVE(iterator->group, chain);
	47
	48	iterator->group->deleted = true;
	49
	50	return 0;
	51	}
	52
	53	errno_t hfs_ext_iter_next_group(struct hfs_ext_iter *iter)
	54	{
	55	off_t offset = (iter->bt_iter.key.startBlock + iter->group_block_count) * 4096;
	56
	57	errno_t ret = hfs_ext_find(iter->vp, offset, iter);
	58
	59	if (ret)
	60	return ret;
	61
	62	if (iter->bt_iter.key.startBlock != offset / 4096)
	63	return ESTALE;
	64
65	return 0;
66	}
67
68	errno_t hfs_ext_iter_update(hfs_ext_iter_t *iter,
69	HFSPlusExtentDescriptor *extents,
70	int count,
71	HFSPlusExtentRecord cat_extents)
72	{
73	if (count % kHFSPlusExtentDensity) {
74	// Zero out last group
75	int to_zero = kHFSPlusExtentDensity - (count % 8);
76	bzero(&extents[count], to_zero * sizeof(*extents));
77	count += to_zero;
78	}
79
80	extent_group_t *group = NULL;
81
82	if (!iter->bt_iter.key.startBlock) {
83	memcpy(cat_extents, extents, sizeof(HFSPlusExtentRecord));
84	group = LIST_FIRST(&iter->vp->ffork->groups);
85	hfs_ext_copy_rec(extents, group->extents);
86
87	iter->bt_iter.key.startBlock += hfs_total_blocks(extents, 8);
88
89	count -= 8;
90	extents += 8;
91	} else {
92	extent_group_t *next;
93	LIST_FOREACH(next, &iter->vp->ffork->groups, chain) {
94	if (iter->bt_iter.key.startBlock < next->start_block)
95	break;
96	group = next;
97	}
98	}
99
100	iter->bt_iter.group = NULL;
101
102	while (count > 0) {
103	extent_group_t new_group = malloc(sizeof(new_group));
104	hfs_ext_copy_rec(extents, new_group->extents);
105	new_group->start_block = iter->bt_iter.key.startBlock;
106	new_group->deleted = false;
107
108	if (group) {
109	LIST_INSERT_AFTER(group, new_group, chain);
110	} else
111	LIST_INSERT_HEAD(&iter->vp->ffork->groups, new_group, chain);
112	group = new_group;
113
114	iter->bt_iter.key.startBlock += hfs_total_blocks(extents, 8);
115
116	count -= 8;
117	extents += 8;
118	}
119
120	return 0;
121	}
122
123	errno_t hfs_ext_find(vnode_t vp, off_t offset, hfs_ext_iter_t *iter)
124	{
125	(void)vp;
126	const uint32_t block = (uint32_t)(offset / 4096);
127
128	iter->vp = vp;
129	extent_group_t next, group = NULL;
130	LIST_FOREACH(next, &vp->ffork->groups, chain) {
131	if (block < next->start_block)
132	break;
133	group = next;
134	}
135
136	if (!group)
137	return ENOENT;
138
139	iter->file_block = iter->bt_iter.key.startBlock = group->start_block;
140	iter->bt_iter.group = group;
141
142	for (iter->ndx = 0; iter->ndx < 8; ++iter->ndx) {
143	HFSPlusExtentDescriptor *ext = &group->extents[iter->ndx];
144	if (iter->file_block + ext->blockCount > block) {
145	hfs_ext_copy_rec(group->extents, iter->group);
146	return hfs_ext_iter_check_group(iter);
147	}
148	iter->file_block += ext->blockCount;
149	}
150
151	return ENOENT;
152	}
153
154	void dump_extents(struct extent_groups *groups)
155	{
156	extent_group_t *group;
157	int i = 0;
158
159	LIST_FOREACH(group, groups, chain) {
160	for (int j = 0; j < 8; ++j) {
161	HFSPlusExtentDescriptor *ext = &group->extents[j];
162	if (!ext->blockCount) {
163	// Make sure all the reset are NULL
164	if (LIST_NEXT(group, chain))
165	goto keep_going;
166
167	for (int k = j; k < 8; ++k) {
168	if (group->extents[k].startBlock
169	\|\| group->extents[k].blockCount) {
170	goto keep_going;
171	}
172	}
173
174	break;
175	}
176
177	keep_going:
178
179	printf("%s{ %u, %u }", (i == 0 ? "" : i % 4 == 0 ? ",\n" : ", "),
180	ext->startBlock, ext->blockCount);
181	++i;
182	}
183	}
184	printf("\n");
185	}
186
187	void check_extents(unsigned line, vnode_t vnode,
188	const HFSPlusExtentDescriptor *extents, int count)
189	{
190	uint32_t block = 0;
191	extent_group_t *group;
192	LIST_FOREACH(group, &vnode->ffork->groups, chain) {
193	if (group->start_block != block)
194	goto bad;
195	int cnt = MIN(count, 8);
196	if (memcmp(group->extents, extents, cnt * sizeof(*extents)))
197	goto bad;
198	while (cnt < 8) {
199	if (group->extents[cnt].startBlock \|\| group->extents[cnt].blockCount)
200	goto bad;
201	++cnt;
202	}
203	if ((count -= 8) <= 0)
204	break;
205	block += hfs_total_blocks(extents, 8);
206	extents += 8;
207	}
208
209	if (LIST_NEXT(group, chain))
210	goto bad;
211
212	return;
213
214	bad:
215
216	printf("hfs_extents_test:%u: error: unexpected extents:\n", line);
217	dump_extents(&vnode->ffork->groups);
218	exit(1);
219	}
220
221	int main(void)
222	{
223	cnode_t cnode = {};
224	hfsmount_t mount = {
225	.blockSize = 4096,
226	.hfs_extents_cp = &cnode,
227	};
228	filefork_t ffork = {
229	.ff_blocks = 200,
230	.ff_unallocblocks = 100,
231	.groups = LIST_HEAD_INITIALIZER(ffork.groups),
232	};
233	struct vnode vnode = {
234	.ffork = &ffork,
235	.mount = &mount,
236	.is_rsrc = false,
237	.cnode = &cnode,
238	};
239
240	extent_group_t group = {
241	.extents = { { 100, 100 } },
242	};
243
244	LIST_INSERT_HEAD(&ffork.groups, &group, chain);
245
246	HFSPlusExtentRecord cat_extents;
247
248	#define E(...) (HFSPlusExtentDescriptor[]) { __VA_ARGS__ }
249	#define lengthof(x) (sizeof(x) / sizeof(*x))
250
251	#define CHECK_EXTENTS(...) \
252	do { \
253	HFSPlusExtentDescriptor extents_[] = __VA_ARGS__; \
254	check_extents(__LINE__, &vnode, extents_, \
255	lengthof(extents_)); \
256	} while (0)
257
258	#define CHECK_REPLACE(file_block, repl, expected) \
259	do { \
260	HFSPlusExtentDescriptor repl_[] = repl; \
261	hfs_ext_replace(&mount, &vnode, file_block, repl_, \
262	lengthof(repl_), cat_extents); \
263	CHECK_EXTENTS(expected); \
264	} while (0)
265
266	CHECK_REPLACE(10, E({ 200, 10 }),
267	E({ 100, 10 }, { 200, 10 }, { 120, 80 }));
268
269	CHECK_REPLACE(5, E({ 300, 10 }),
270	E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 120, 80 }));
271
272	CHECK_REPLACE(20, E({ 400, 1 }),
273	E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
274	{ 121, 79 }));
275
276	CHECK_REPLACE(21, E({ 402, 1 }),
277	E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
278	{ 402, 1 }, { 122, 78 }));
279
280	CHECK_REPLACE(22, E({ 404, 1 }),
281	E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
282	{ 402, 1 }, { 404, 1 }, { 123, 77 }));
283
284	CHECK_REPLACE(23, E({ 406, 1 }),
285	E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
286	{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 124, 76 }));
287
288	CHECK_REPLACE(24, E({ 408, 1 }),
289	E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
290	{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
291	{ 125, 75 }));
292
293	/*
294	* OK, now we won't see any padding until we get the number of extents
295	* over 32. So let's get to that point now.
296	*/
297
298	for (int i = 25, j = 500; i < 25 + 24; ++i, j += 2) {
299	hfs_ext_replace(&mount, &vnode, i, E({ j, 1 }),
300	1, cat_extents);
301	}
302
303	CHECK_EXTENTS(E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
304	{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
305	{ 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
306	{ 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
307	{ 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
308	{ 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
309	{ 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
310	{ 540, 1 }, { 542, 1 }, { 544, 1 }, { 546, 1 },
311	{ 149, 51 }));
312
313	/*
314	* So if we replace an extent in the first group, we should see it pad using
315	* the 205 extent and some of the 300 extent.
316	*/
317
318	CHECK_REPLACE(2, E({ 600, 1 }),
319	E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
320	{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
321	{ 207, 1 }, { 208, 1 }, { 209, 1 }, { 400, 1 },
322	{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
323	{ 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
324	{ 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
325	{ 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
326	{ 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
327	{ 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
328	{ 540, 1 }, { 542, 1 }, { 544, 1 }, { 546, 1 },
329	{ 149, 51 }));
330
331	/*
332	* Now try and test the case where it fails to pad and is forced to move
333	* to the next group. First, merge the 544 and 546 extents to reduce
334	* the number of extents by 1.
335	*/
336
337	CHECK_REPLACE(47, E({ 700, 2 }),
338	E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
339	{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
340	{ 207, 1 }, { 208, 1 }, { 209, 1 }, { 400, 1 },
341	{ 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
342	{ 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
343	{ 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
344	{ 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
345	{ 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
346	{ 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
347	{ 540, 1 }, { 542, 1 }, { 700, 2 }, { 149, 51 }));
348
349	// Now force 207-209 to be merged
350
351	CHECK_REPLACE(21, E({ 800, 1 }),
352	E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
353	{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
354	{ 207, 3 }, { 400, 1 }, { 800, 1 }, { 404, 1 },
355	{ 406, 1 }, { 408, 1 }, { 500, 1 }, { 502, 1 },
356	{ 504, 1 }, { 506, 1 }, { 508, 1 }, { 510, 1 },
357	{ 512, 1 }, { 514, 1 }, { 516, 1 }, { 518, 1 },
358	{ 520, 1 }, { 522, 1 }, { 524, 1 }, { 526, 1 },
359	{ 528, 1 }, { 530, 1 }, { 532, 1 }, { 534, 1 },
360	{ 536, 1 }, { 538, 1 }, { 540, 1 }, { 542, 1 },
361	{ 700, 2 }, { 149, 51 }));
362
363	// Now let's push the last extent into a new group
364
365	CHECK_REPLACE(50, E({ 800, 1 }),
366	E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
367	{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
368	{ 207, 3 }, { 400, 1 }, { 800, 1 }, { 404, 1 },
369	{ 406, 1 }, { 408, 1 }, { 500, 1 }, { 502, 1 },
370	{ 504, 1 }, { 506, 1 }, { 508, 1 }, { 510, 1 },
371	{ 512, 1 }, { 514, 1 }, { 516, 1 }, { 518, 1 },
372	{ 520, 1 }, { 522, 1 }, { 524, 1 }, { 526, 1 },
373	{ 528, 1 }, { 530, 1 }, { 532, 1 }, { 534, 1 },
374	{ 536, 1 }, { 538, 1 }, { 540, 1 }, { 542, 1 },
375	{ 700, 2 }, { 149, 1 }, { 800, 1 }, { 151, 49 }));
376
377	CHECK_REPLACE(52, E({ 802, 1 }),
378	E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
379	{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
380	{ 207, 3 }, { 400, 1 }, { 800, 1 }, { 404, 1 },
381	{ 406, 1 }, { 408, 1 }, { 500, 1 }, { 502, 1 },
382	{ 504, 1 }, { 506, 1 }, { 508, 1 }, { 510, 1 },
383	{ 512, 1 }, { 514, 1 }, { 516, 1 }, { 518, 1 },
384	{ 520, 1 }, { 522, 1 }, { 524, 1 }, { 526, 1 },
385	{ 528, 1 }, { 530, 1 }, { 532, 1 }, { 534, 1 },
386	{ 536, 1 }, { 538, 1 }, { 540, 1 }, { 542, 1 },
387	{ 700, 2 }, { 149, 1 }, { 800, 1 }, { 151, 1 },
388	{ 802, 1 }, { 153, 47 }));
389
390	/*
391	* And now if we split the 207 extent, it will fail to pad within the
392	* 32 extents and so it will be forced to pull in more extents.
393	*/
394
395	CHECK_REPLACE(18, E({ 900, 1 }),
396	E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
397	{ 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
398	{ 207, 1 }, { 900, 1 }, { 209, 1 }, { 400, 1 },
399	{ 800, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
400	{ 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
401	{ 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
402	{ 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
403	{ 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
404	{ 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
405	{ 540, 1 }, { 542, 1 }, { 700, 2 }, { 149, 1 },
406	{ 800, 1 }, { 151, 1 }, { 802, 1 }, { 153, 47 }));
407
408	// Some tests covering replacing the beginning and end
409
410	CHECK_REPLACE(0, E({ 100, 100 }), E({ 100, 100 }));
411	CHECK_REPLACE(10, E({ 200, 90 }), E({ 100, 10 }, { 200, 90 }));
412	CHECK_REPLACE(0, E({ 300, 10 }), E({ 300, 10 }, { 200, 90 }));
413
414	// Test replacing with multiple extents
415	CHECK_REPLACE(5, E({ 400, 1 }, { 400, 2 }),
416	E({ 300, 5 }, { 400, 1 }, { 400, 2 }, { 308, 2 }, { 200, 90 }));
417
418	/*
419	* Test an unlikely case where we have lots of extents that could
420	* be coalesced. When replacing extents here, we can't coalesce
421	* all of them because we will not be able to roll back.
422	*/
423
424	// First, set things up
425	hfs_ext_iter_t iter;
426
427	assert(!hfs_ext_find(&vnode, 0, &iter));
428
429	for (int i = 0; i < 32768; i += 8) {
430	HFSPlusExtentRecord r = { { i, 1 }, { i + 1, 1 }, { i + 2, 1 }, { i + 3, 1 },
431	{ i + 4, 1 }, { i + 5, 1 }, { i + 6, 1 }, { i + 7, 1 } };
432
433	hfs_ext_iter_update(&iter, r, 8, cat_extents);
434	}
435
436	ffork.ff_blocks = 32768;
437	ffork.ff_unallocblocks = 0;
438
439	/*
440	* Now we have 32768 extents that could be coalesced. Check the
441	* following succeeds.
442	*/
443	assert(!hfs_ext_replace(&mount, &vnode, 0,
444	E({ 1, 8 }), 1, cat_extents));
445
446	printf("[PASSED] hfs_extents_test\n");
447
448	return 0;
449	}