VCICache.cpp@ 99739

Last change on this file since 99739 was 99739, checked in by vboxsync, 17 months ago
*: doxygen corrections (mostly about removing @returns from functions returning void).
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 65.8 KB

Rev	Line
[32370]	1	/* $Id: VCICache.cpp 99739 2023-05-11 01:01:08Z vboxsync $ */
	2	/** @file
	3	* VCICacheCore - VirtualBox Cache Image, Core Code.
	4	*/
	5
	6	/*
[98103]	7	* Copyright (C) 2006-2023 Oracle and/or its affiliates.
[32370]	8	*
[96407]	9	* This file is part of VirtualBox base platform packages, as
	10	* available from https://www.virtualbox.org.
	11	*
	12	* This program is free software; you can redistribute it and/or
	13	* modify it under the terms of the GNU General Public License
	14	* as published by the Free Software Foundation, in version 3 of the
	15	* License.
	16	*
	17	* This program is distributed in the hope that it will be useful, but
	18	* WITHOUT ANY WARRANTY; without even the implied warranty of
	19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	20	* General Public License for more details.
	21	*
	22	* You should have received a copy of the GNU General Public License
	23	* along with this program; if not, see <https://www.gnu.org/licenses>.
	24	*
	25	* SPDX-License-Identifier: GPL-3.0-only
[32370]	26	*/
	27
[57358]	28
	29	/*********************************************************************************************************************************
	30	* Header Files *
	31	*********************************************************************************************************************************/
[32370]	32	#define LOG_GROUP LOG_GROUP_VD_RAW /** @todo logging group */
[50988]	33	#include <VBox/vd-cache-backend.h>
[32370]	34	#include <VBox/err.h>
	35
	36	#include <VBox/log.h>
	37	#include <iprt/assert.h>
	38	#include <iprt/alloc.h>
	39	#include <iprt/file.h>
[33481]	40	#include <iprt/asm.h>
[32370]	41
[50988]	42	#include "VDBackends.h"
	43
[32553]	44	/*******************************************************************************
[57372]	45	* On disk data structures *
[32553]	46	*******************************************************************************/
[32370]	47
[32553]	48	/** @note All structures which are written to the disk are written in camel case
	49	* and packed. */
	50
	51	/** Block size used internally, because we cache sectors the smallest unit we
	52	* have to care about is 512 bytes. */
	53	#define VCI_BLOCK_SIZE 512
	54
	55	/** Convert block number/size to byte offset/size. */
	56	#define VCI_BLOCK2BYTE(u) ((uint64_t)(u) << 9)
	57
	58	/** Convert byte offset/size to block number/size. */
	59	#define VCI_BYTE2BLOCK(u) ((u) >> 9)
	60
	61	/**
	62	* The VCI header - at the beginning of the file.
	63	*
	64	* All entries a stored in little endian order.
	65	*/
	66	#pragma pack(1)
	67	typedef struct VciHdr
	68	{
	69	/** The signature to identify a cache image. */
	70	uint32_t u32Signature;
	71	/** Version of the layout of metadata in the cache. */
	72	uint32_t u32Version;
	73	/** Maximum size of the cache file in blocks.
	74	* This includes all metadata. */
	75	uint64_t cBlocksCache;
	76	/** Flag indicating whether the cache was closed cleanly. */
	77	uint8_t fUncleanShutdown;
	78	/** Cache type. */
	79	uint32_t u32CacheType;
	80	/** Offset of the B+-Tree root in the image in blocks. */
	81	uint64_t offTreeRoot;
	82	/** Offset of the block allocation bitmap in blocks. */
	83	uint64_t offBlkMap;
	84	/** Size of the block allocation bitmap in blocks. */
	85	uint32_t cBlkMap;
	86	/** UUID of the image. */
	87	RTUUID uuidImage;
[33540]	88	/** Modification UUID for the cache. */
[32553]	89	RTUUID uuidModification;
	90	/** Reserved for future use. */
	91	uint8_t abReserved[951];
	92	} VciHdr, *PVciHdr;
[33534]	93	#pragma pack()
[32553]	94	AssertCompileSize(VciHdr, 2 * VCI_BLOCK_SIZE);
	95
	96	/** VCI signature to identify a valid image. */
[33745]	97	#define VCI_HDR_SIGNATURE UINT32_C(0x00494356) /* \0ICV */
[32553]	98	/** Current version we support. */
	99	#define VCI_HDR_VERSION UINT32_C(0x00000001)
	100
	101	/** Value for an unclean cache shutdown. */
	102	#define VCI_HDR_UNCLEAN_SHUTDOWN UINT8_C(0x01)
	103	/** Value for a clean cache shutdown. */
	104	#define VCI_HDR_CLEAN_SHUTDOWN UINT8_C(0x00)
	105
	106	/** Cache type: Dynamic image growing to the maximum value. */
	107	#define VCI_HDR_CACHE_TYPE_DYNAMIC UINT32_C(0x00000001)
	108	/** Cache type: Fixed image, space is preallocated. */
	109	#define VCI_HDR_CACHE_TYPE_FIXED UINT32_C(0x00000002)
	110
	111	/**
	112	* On disk representation of an extent describing a range of cached data.
	113	*
	114	* All entries a stored in little endian order.
	115	*/
	116	#pragma pack(1)
	117	typedef struct VciCacheExtent
	118	{
	119	/** Block address of the previous extent in the LRU list. */
	120	uint64_t u64ExtentPrev;
	121	/** Block address of the next extent in the LRU list. */
	122	uint64_t u64ExtentNext;
	123	/** Flags (for compression, encryption etc.) - currently unused and should be always 0. */
	124	uint8_t u8Flags;
	125	/** Reserved */
	126	uint8_t u8Reserved;
	127	/** First block of cached data the extent represents. */
	128	uint64_t u64BlockOffset;
	129	/** Number of blocks the extent represents. */
	130	uint32_t u32Blocks;
	131	/** First block in the image where the data is stored. */
	132	uint64_t u64BlockAddr;
	133	} VciCacheExtent, *PVciCacheExtent;
[33534]	134	#pragma pack()
[32553]	135	AssertCompileSize(VciCacheExtent, 38);
	136
	137	/**
	138	* On disk representation of an internal node.
	139	*
	140	* All entries a stored in little endian order.
	141	*/
	142	#pragma pack(1)
	143	typedef struct VciTreeNodeInternal
	144	{
	145	/** First block of cached data the internal node represents. */
	146	uint64_t u64BlockOffset;
	147	/** Number of blocks the internal node represents. */
	148	uint32_t u32Blocks;
	149	/** Block address in the image where the next node in the tree is stored. */
	150	uint64_t u64ChildAddr;
	151	} VciTreeNodeInternal, *PVciTreeNodeInternal;
[33534]	152	#pragma pack()
[32553]	153	AssertCompileSize(VciTreeNodeInternal, 20);
	154
	155	/**
	156	* On-disk representation of a node in the B+-Tree.
	157	*
	158	* All entries a stored in little endian order.
	159	*/
	160	#pragma pack(1)
	161	typedef struct VciTreeNode
	162	{
	163	/** Type of the node (root, internal, leaf). */
	164	uint8_t u8Type;
	165	/** Data in the node. */
	166	uint8_t au8Data[4095];
	167	} VciTreeNode, *PVciTreeNode;
[33534]	168	#pragma pack()
[32553]	169	AssertCompileSize(VciTreeNode, 8 * VCI_BLOCK_SIZE);
	170
	171	/** Node type: Internal node containing links to other nodes (VciTreeNodeInternal). */
[33522]	172	#define VCI_TREE_NODE_TYPE_INTERNAL UINT8_C(0x01)
[32553]	173	/** Node type: Leaf of the tree (VciCacheExtent). */
[33522]	174	#define VCI_TREE_NODE_TYPE_LEAF UINT8_C(0x02)
[32553]	175
[33481]	176	/** Number of cache extents described by one node. */
[33522]	177	#define VCI_TREE_EXTENTS_PER_NODE ((sizeof(VciTreeNode)-1) / sizeof(VciCacheExtent))
[33481]	178	/** Number of internal nodes managed by one tree node. */
[33522]	179	#define VCI_TREE_INTERNAL_NODES_PER_NODE ((sizeof(VciTreeNode)-1) / sizeof(VciTreeNodeInternal))
[33481]	180
[32553]	181	/**
	182	* VCI block bitmap header.
	183	*
	184	* All entries a stored in little endian order.
	185	*/
	186	#pragma pack(1)
	187	typedef struct VciBlkMap
	188	{
	189	/** Magic of the block bitmap. */
	190	uint32_t u32Magic;
	191	/** Version of the block bitmap. */
	192	uint32_t u32Version;
	193	/** Number of blocks this block map manages. */
	194	uint64_t cBlocks;
	195	/** Number of free blocks. */
	196	uint64_t cBlocksFree;
	197	/** Number of blocks allocated for metadata. */
	198	uint64_t cBlocksAllocMeta;
	199	/** Number of blocks allocated for actual cached data. */
	200	uint64_t cBlocksAllocData;
	201	/** Reserved for future use. */
	202	uint8_t au8Reserved[472];
	203	} VciBlkMap, *PVciBlkMap;
[33534]	204	#pragma pack()
[32553]	205	AssertCompileSize(VciBlkMap, VCI_BLOCK_SIZE);
	206
	207	/** The magic which identifies a block map. */
[33745]	208	#define VCI_BLKMAP_MAGIC UINT32_C(0x4b4c4256) /* KLBV */
[32553]	209	/** Current version. */
	210	#define VCI_BLKMAP_VERSION UINT32_C(0x00000001)
	211
	212	/** Block bitmap entry */
	213	typedef uint8_t VciBlkMapEnt;
	214
[32370]	215
[57358]	216	/*********************************************************************************************************************************
	217	* Constants And Macros, Structures and Typedefs *
	218	*********************************************************************************************************************************/
	219
[32370]	220	/**
[32553]	221	* Block range descriptor.
	222	*/
	223	typedef struct VCIBLKRANGEDESC
	224	{
	225	/** Previous entry in the list. */
	226	struct VCIBLKRANGEDESC *pPrev;
	227	/** Next entry in the list. */
	228	struct VCIBLKRANGEDESC *pNext;
	229	/** Start address of the range. */
	230	uint64_t offAddrStart;
	231	/** Number of blocks in the range. */
	232	uint64_t cBlocks;
	233	/** Flag whether the range is free or allocated. */
	234	bool fFree;
	235	} VCIBLKRANGEDESC, *PVCIBLKRANGEDESC;
	236
	237	/**
	238	* Block map for the cache image - in memory structure.
	239	*/
	240	typedef struct VCIBLKMAP
	241	{
	242	/** Number of blocks the map manages. */
	243	uint64_t cBlocks;
	244	/** Number of blocks allocated for metadata. */
	245	uint64_t cBlocksAllocMeta;
	246	/** Number of blocks allocated for actual cached data. */
	247	uint64_t cBlocksAllocData;
	248	/** Number of free blocks. */
	249	uint64_t cBlocksFree;
	250
	251	/** Pointer to the head of the block range list. */
	252	PVCIBLKRANGEDESC pRangesHead;
	253	/** Pointer to the tail of the block range list. */
	254	PVCIBLKRANGEDESC pRangesTail;
	255
	256	} VCIBLKMAP;
	257	/** Pointer to a block map. */
	258	typedef VCIBLKMAP *PVCIBLKMAP;
	259
	260	/**
[33481]	261	* B+-Tree node header.
	262	*/
	263	typedef struct VCITREENODE
	264	{
	265	/** Type of the node (VCI_TREE_NODE_TYPE_). /
	266	uint8_t u8Type;
	267	/** Block address where the node is stored. */
	268	uint64_t u64BlockAddr;
	269	/** Pointer to the parent. */
	270	struct VCITREENODE *pParent;
	271	} VCITREENODE, *PVCITREENODE;
	272
	273	/**
	274	* B+-Tree node pointer.
	275	*/
	276	typedef struct VCITREENODEPTR
	277	{
	278	/** Flag whether the node is in memory or still on the disk. */
	279	bool fInMemory;
	280	/** Type dependent data. */
	281	union
	282	{
	283	/** Pointer to a in memory node. */
	284	PVCITREENODE pNode;
	285	/** Start block address of the node. */
	286	uint64_t offAddrBlockNode;
	287	} u;
	288	} VCITREENODEPTR, *PVCITREENODEPTR;
	289
	290	/**
	291	* Internal node.
	292	*/
	293	typedef struct VCINODEINTERNAL
	294	{
	295	/** First block of cached data the internal node represents. */
	296	uint64_t u64BlockOffset;
	297	/** Number of blocks the internal node represents. */
	298	uint32_t u32Blocks;
	299	/** Pointer to the child node. */
	300	VCITREENODEPTR PtrChild;
	301	} VCINODEINTERNAL, *PVCINODEINTERNAL;
	302
	303	/**
	304	* A in memory internal B+-tree node.
	305	*/
	306	typedef struct VCITREENODEINT
	307	{
	308	/** Node core. */
	309	VCITREENODE Core;
	310	/** Number of used nodes. */
	311	unsigned cUsedNodes;
	312	/** Array of internal nodes. */
	313	VCINODEINTERNAL aIntNodes[VCI_TREE_INTERNAL_NODES_PER_NODE];
	314	} VCITREENODEINT, *PVCITREENODEINT;
	315
	316	/**
	317	* A in memory cache extent.
	318	*/
	319	typedef struct VCICACHEEXTENT
	320	{
	321	/** First block of cached data the extent represents. */
	322	uint64_t u64BlockOffset;
	323	/** Number of blocks the extent represents. */
	324	uint32_t u32Blocks;
	325	/** First block in the image where the data is stored. */
	326	uint64_t u64BlockAddr;
	327	} VCICACHEEXTENT, *PVCICACHEEXTENT;
	328
	329	/**
	330	* A in memory leaf B+-tree node.
	331	*/
	332	typedef struct VCITREENODELEAF
	333	{
	334	/** Node core. */
[38469]	335	VCITREENODE Core;
	336	/** Next leaf node in the list. */
	337	struct VCITREENODELEAF *pNext;
[33481]	338	/** Number of used nodes. */
[38469]	339	unsigned cUsedNodes;
[33481]	340	/** The extents in the node. */
[38469]	341	VCICACHEEXTENT aExtents[VCI_TREE_EXTENTS_PER_NODE];
[33481]	342	} VCITREENODELEAF, *PVCITREENODELEAF;
	343
	344	/**
[32536]	345	* VCI image data structure.
[32370]	346	*/
	347	typedef struct VCICACHE
	348	{
	349	/** Image name. */
	350	const char *pszFilename;
	351	/** Storage handle. */
	352	PVDIOSTORAGE pStorage;
	353
	354	/** Pointer to the per-disk VD interface list. */
	355	PVDINTERFACE pVDIfsDisk;
	356	/** Pointer to the per-image VD interface list. */
	357	PVDINTERFACE pVDIfsImage;
[38469]	358	/** Error interface. */
	359	PVDINTERFACEERROR pIfError;
	360	/** I/O interface. */
	361	PVDINTERFACEIOINT pIfIo;
[32370]	362
	363	/** Open flags passed by VBoxHD layer. */
	364	unsigned uOpenFlags;
	365	/** Image flags defined during creation or determined during open. */
	366	unsigned uImageFlags;
	367	/** Total size of the image. */
	368	uint64_t cbSize;
	369
[32553]	370	/** Offset of the B+-Tree in the image in bytes. */
	371	uint64_t offTreeRoot;
[33481]	372	/** Pointer to the root node of the B+-Tree. */
	373	PVCITREENODE pRoot;
[32553]	374	/** Offset to the block allocation bitmap in bytes. */
	375	uint64_t offBlksBitmap;
	376	/** Block map. */
	377	PVCIBLKMAP pBlkMap;
[32370]	378	} VCICACHE, *PVCICACHE;
	379
[33481]	380	/** No block free in bitmap error code. */
	381	#define VERR_VCI_NO_BLOCKS_FREE (-65536)
	382
[38469]	383	/** Flags for the block map allocator. */
	384	#define VCIBLKMAP_ALLOC_DATA 0
	385	#define VCIBLKMAP_ALLOC_META RT_BIT(0)
	386	#define VCIBLKMAP_ALLOC_MASK 0x1
	387
[32370]	388
[57358]	389	/*********************************************************************************************************************************
	390	* Static Variables *
	391	*********************************************************************************************************************************/
	392
[32370]	393	/** NULL-terminated array of supported file extensions. */
	394	static const char *const s_apszVciFileExtensions[] =
	395	{
	396	"vci",
	397	NULL
	398	};
	399
	400
[57358]	401	/*********************************************************************************************************************************
	402	* Internal Functions *
	403	*********************************************************************************************************************************/
	404
[32370]	405	/**
[32536]	406	* Internal. Flush image data to disk.
	407	*/
[33481]	408	static int vciFlushImage(PVCICACHE pCache)
[32370]	409	{
[32536]	410	int rc = VINF_SUCCESS;
	411
[33481]	412	if ( pCache->pStorage
	413	&& !(pCache->uOpenFlags & VD_OPEN_FLAGS_READONLY))
[38469]	414	{
	415	rc = vdIfIoIntFileFlushSync(pCache->pIfIo, pCache->pStorage);
	416	}
[32536]	417
	418	return rc;
[32370]	419	}
	420
[32536]	421	/**
[33481]	422	* Internal. Free all allocated space for representing an image except pCache,
[32536]	423	* and optionally delete the image from disk.
	424	*/
[33481]	425	static int vciFreeImage(PVCICACHE pCache, bool fDelete)
[32370]	426	{
[32536]	427	int rc = VINF_SUCCESS;
	428
	429	/* Freeing a never allocated image (e.g. because the open failed) is
	430	* not signalled as an error. After all nothing bad happens. */
[33481]	431	if (pCache)
[32536]	432	{
[33481]	433	if (pCache->pStorage)
[32536]	434	{
	435	/* No point updating the file that is deleted anyway. */
	436	if (!fDelete)
[33481]	437	vciFlushImage(pCache);
[32536]	438
[38469]	439	vdIfIoIntFileClose(pCache->pIfIo, pCache->pStorage);
[33481]	440	pCache->pStorage = NULL;
[32536]	441	}
	442
[33481]	443	if (fDelete && pCache->pszFilename)
[38469]	444	vdIfIoIntFileDelete(pCache->pIfIo, pCache->pszFilename);
[32536]	445	}
	446
	447	LogFlowFunc(("returns %Rrc\n", rc));
	448	return rc;
[32370]	449	}
	450
	451	/**
[32553]	452	* Creates a new block map which can manage the given number of blocks.
	453	*
	454	* The size of the bitmap is aligned to the VCI block size.
	455	*
	456	* @returns VBox status code.
	457	* @param cBlocks The number of blocks the bitmap can manage.
	458	* @param ppBlkMap Where to store the pointer to the block bitmap.
[64272]	459	* @param pcBlkMap Where to store the size of the block bitmap in blocks
[32553]	460	* needed on the disk.
	461	*/
	462	static int vciBlkMapCreate(uint64_t cBlocks, PVCIBLKMAP ppBlkMap, uint32_t pcBlkMap)
	463	{
	464	int rc = VINF_SUCCESS;
	465	uint32_t cbBlkMap = RT_ALIGN_Z(cBlocks / sizeof(VciBlkMapEnt) / 8, VCI_BLOCK_SIZE);
	466	PVCIBLKMAP pBlkMap = (PVCIBLKMAP)RTMemAllocZ(sizeof(VCIBLKMAP));
	467	PVCIBLKRANGEDESC pFree = (PVCIBLKRANGEDESC)RTMemAllocZ(sizeof(VCIBLKRANGEDESC));
	468
	469	LogFlowFunc(("cBlocks=%u ppBlkMap=%#p pcBlkMap=%#p\n", cBlocks, ppBlkMap, pcBlkMap));
	470
[33481]	471	if (pBlkMap && pFree)
[32553]	472	{
	473	pBlkMap->cBlocks = cBlocks;
	474	pBlkMap->cBlocksAllocMeta = 0;
	475	pBlkMap->cBlocksAllocData = 0;
	476	pBlkMap->cBlocksFree = cBlocks;
	477
	478	pFree->pPrev = NULL;
	479	pFree->pNext = NULL;
	480	pFree->offAddrStart = 0;
	481	pFree->cBlocks = cBlocks;
	482	pFree->fFree = true;
	483
	484	pBlkMap->pRangesHead = pFree;
	485	pBlkMap->pRangesTail = pFree;
	486
[33745]	487	Assert(!((cbBlkMap + sizeof(VciBlkMap)) % VCI_BLOCK_SIZE));
[32553]	488	*ppBlkMap = pBlkMap;
[33745]	489	*pcBlkMap = VCI_BYTE2BLOCK(cbBlkMap + sizeof(VciBlkMap));
[32553]	490	}
	491	else
	492	{
	493	if (pBlkMap)
	494	RTMemFree(pBlkMap);
	495	if (pFree)
	496	RTMemFree(pFree);
	497
	498	rc = VERR_NO_MEMORY;
	499	}
	500
	501	LogFlowFunc(("returns rc=%Rrc cBlkMap=%u\n", rc, *pcBlkMap));
	502	return rc;
	503	}
	504
[62873]	505	#if 0 /** @todo unsued vciBlkMapDestroy */
[32553]	506	/**
	507	* Frees a block map.
	508	*
	509	* @param pBlkMap The block bitmap to destroy.
	510	*/
	511	static void vciBlkMapDestroy(PVCIBLKMAP pBlkMap)
	512	{
	513	LogFlowFunc(("pBlkMap=%#p\n", pBlkMap));
	514
	515	PVCIBLKRANGEDESC pRangeCur = pBlkMap->pRangesHead;
	516
	517	while (pRangeCur)
	518	{
	519	PVCIBLKRANGEDESC pTmp = pRangeCur;
	520
	521	RTMemFree(pTmp);
	522
	523	pRangeCur = pRangeCur->pNext;
	524	}
	525
	526	RTMemFree(pBlkMap);
	527
	528	LogFlowFunc(("returns\n"));
	529	}
[62873]	530	#endif
[32553]	531
	532	/**
	533	* Loads the block map from the specified medium and creates all necessary
	534	* in memory structures to manage used and free blocks.
	535	*
	536	* @returns VBox status code.
	537	* @param pStorage Storage handle to read the block bitmap from.
	538	* @param offBlkMap Start of the block bitmap in blocks.
	539	* @param cBlkMap Size of the block bitmap on the disk in blocks.
	540	* @param ppBlkMap Where to store the block bitmap on success.
	541	*/
	542	static int vciBlkMapLoad(PVCICACHE pStorage, uint64_t offBlkMap, uint32_t cBlkMap, PVCIBLKMAP *ppBlkMap)
	543	{
	544	int rc = VINF_SUCCESS;
	545	VciBlkMap BlkMap;
	546
	547	LogFlowFunc(("pStorage=%#p offBlkMap=%llu cBlkMap=%u ppBlkMap=%#p\n",
	548	pStorage, offBlkMap, cBlkMap, ppBlkMap));
	549
	550	if (cBlkMap >= VCI_BYTE2BLOCK(sizeof(VciBlkMap)))
	551	{
	552	cBlkMap -= VCI_BYTE2BLOCK(sizeof(VciBlkMap));
	553
[38469]	554	rc = vdIfIoIntFileReadSync(pStorage->pIfIo, pStorage->pStorage, offBlkMap,
[44233]	555	&BlkMap, VCI_BYTE2BLOCK(sizeof(VciBlkMap)));
[32553]	556	if (RT_SUCCESS(rc))
	557	{
	558	offBlkMap += VCI_BYTE2BLOCK(sizeof(VciBlkMap));
	559
	560	BlkMap.u32Magic = RT_LE2H_U32(BlkMap.u32Magic);
	561	BlkMap.u32Version = RT_LE2H_U32(BlkMap.u32Version);
	562	BlkMap.cBlocks = RT_LE2H_U32(BlkMap.cBlocks);
	563	BlkMap.cBlocksFree = RT_LE2H_U32(BlkMap.cBlocksFree);
	564	BlkMap.cBlocksAllocMeta = RT_LE2H_U32(BlkMap.cBlocksAllocMeta);
	565	BlkMap.cBlocksAllocData = RT_LE2H_U32(BlkMap.cBlocksAllocData);
	566
	567	if ( BlkMap.u32Magic == VCI_BLKMAP_MAGIC
	568	&& BlkMap.u32Version == VCI_BLKMAP_VERSION
	569	&& BlkMap.cBlocks == BlkMap.cBlocksFree + BlkMap.cBlocksAllocMeta + BlkMap.cBlocksAllocData
[33745]	570	&& VCI_BYTE2BLOCK(BlkMap.cBlocks / 8) == cBlkMap)
[32553]	571	{
	572	PVCIBLKMAP pBlkMap = (PVCIBLKMAP)RTMemAllocZ(sizeof(VCIBLKMAP));
	573	if (pBlkMap)
	574	{
	575	pBlkMap->cBlocks = BlkMap.cBlocks;
	576	pBlkMap->cBlocksFree = BlkMap.cBlocksFree;
	577	pBlkMap->cBlocksAllocMeta = BlkMap.cBlocksAllocMeta;
	578	pBlkMap->cBlocksAllocData = BlkMap.cBlocksAllocData;
	579
[33481]	580	/* Load the bitmap and construct the range list. */
	581	PVCIBLKRANGEDESC pRangeCur = (PVCIBLKRANGEDESC)RTMemAllocZ(sizeof(VCIBLKRANGEDESC));
	582
	583	if (pRangeCur)
[32553]	584	{
[33481]	585	uint8_t abBitmapBuffer[16 * _1K];
	586	uint32_t cBlocksRead = 0;
[33745]	587	uint64_t cBlocksLeft = VCI_BYTE2BLOCK(pBlkMap->cBlocks / 8);
[33481]	588
	589	cBlocksRead = RT_MIN(VCI_BYTE2BLOCK(sizeof(abBitmapBuffer)), cBlocksLeft);
[38469]	590	rc = vdIfIoIntFileReadSync(pStorage->pIfIo, pStorage->pStorage,
	591	offBlkMap, abBitmapBuffer,
[44233]	592	cBlocksRead);
[33481]	593
[32553]	594	if (RT_SUCCESS(rc))
	595	{
[33481]	596	pRangeCur->fFree = !(abBitmapBuffer[0] & 0x01);
	597	pRangeCur->offAddrStart = 0;
	598	pRangeCur->cBlocks = 0;
	599	pRangeCur->pNext = NULL;
	600	pRangeCur->pPrev = NULL;
	601	pBlkMap->pRangesHead = pRangeCur;
	602	pBlkMap->pRangesTail = pRangeCur;
[32553]	603	}
[56754]	604	else
	605	RTMemFree(pRangeCur);
[32553]	606
[33481]	607	while ( RT_SUCCESS(rc)
	608	&& cBlocksLeft)
	609	{
[33745]	610	int iBit = 0;
	611	uint32_t cBits = VCI_BLOCK2BYTE(cBlocksRead) * 8;
	612	uint32_t iBitPrev = 0xffffffff;
	613
	614	while (cBits)
[33481]	615	{
	616	if (pRangeCur->fFree)
	617	{
	618	/* Check for the first set bit. */
[33745]	619	iBit = ASMBitNextSet(abBitmapBuffer, cBits, iBitPrev);
[33481]	620	}
	621	else
	622	{
	623	/* Check for the first free bit. */
[33745]	624	iBit = ASMBitNextClear(abBitmapBuffer, cBits, iBitPrev);
[33481]	625	}
	626
	627	if (iBit == -1)
	628	{
	629	/* No change. */
[33745]	630	pRangeCur->cBlocks += cBits;
	631	cBits = 0;
[33481]	632	}
	633	else
	634	{
[33745]	635	Assert((uint32_t)iBit < cBits);
	636	pRangeCur->cBlocks += iBit;
	637
[33481]	638	/* Create a new range descriptor. */
[33745]	639	PVCIBLKRANGEDESC pRangeNew = (PVCIBLKRANGEDESC)RTMemAllocZ(sizeof(VCIBLKRANGEDESC));
	640	if (!pRangeNew)
	641	{
	642	rc = VERR_NO_MEMORY;
	643	break;
	644	}
	645
	646	pRangeNew->fFree = !pRangeCur->fFree;
	647	pRangeNew->offAddrStart = pRangeCur->offAddrStart + pRangeCur->cBlocks;
	648	pRangeNew->cBlocks = 0;
	649	pRangeNew->pPrev = pRangeCur;
	650	pRangeCur->pNext = pRangeNew;
	651	pBlkMap->pRangesTail = pRangeNew;
	652	pRangeCur = pRangeNew;
	653	cBits -= iBit;
	654	iBitPrev = iBit;
[33481]	655	}
	656	}
[33745]	657
[33481]	658	cBlocksLeft -= cBlocksRead;
	659	offBlkMap += cBlocksRead;
	660
[33745]	661	if ( RT_SUCCESS(rc)
	662	&& cBlocksLeft)
[33481]	663	{
	664	/* Read next chunk. */
[33745]	665	cBlocksRead = RT_MIN(VCI_BYTE2BLOCK(sizeof(abBitmapBuffer)), cBlocksLeft);
[38469]	666	rc = vdIfIoIntFileReadSync(pStorage->pIfIo, pStorage->pStorage,
[44233]	667	offBlkMap, abBitmapBuffer, cBlocksRead);
[33481]	668	}
	669	}
[32553]	670	}
	671	else
	672	rc = VERR_NO_MEMORY;
	673
[33481]	674	if (RT_SUCCESS(rc))
	675	{
	676	*ppBlkMap = pBlkMap;
	677	LogFlowFunc(("return success\n"));
	678	return VINF_SUCCESS;
	679	}
[62873]	680
	681	RTMemFree(pBlkMap);
[32553]	682	}
	683	else
	684	rc = VERR_NO_MEMORY;
	685	}
	686	else
	687	rc = VERR_VD_GEN_INVALID_HEADER;
	688	}
[56369]	689	else
[32553]	690	rc = VERR_VD_GEN_INVALID_HEADER;
	691	}
	692	else
	693	rc = VERR_VD_GEN_INVALID_HEADER;
	694
	695	LogFlowFunc(("returns rc=%Rrc\n", rc));
	696	return rc;
	697	}
	698
	699	/**
[33540]	700	* Saves the block map in the cache image. All necessary on disk structures
[32553]	701	* are written.
	702	*
	703	* @returns VBox status code.
	704	* @param pBlkMap The block bitmap to save.
	705	* @param pStorage Where the block bitmap should be written to.
	706	* @param offBlkMap Start of the block bitmap in blocks.
	707	* @param cBlkMap Size of the block bitmap on the disk in blocks.
	708	*/
	709	static int vciBlkMapSave(PVCIBLKMAP pBlkMap, PVCICACHE pStorage, uint64_t offBlkMap, uint32_t cBlkMap)
	710	{
	711	int rc = VINF_SUCCESS;
	712	VciBlkMap BlkMap;
	713
	714	LogFlowFunc(("pBlkMap=%#p pStorage=%#p offBlkMap=%llu cBlkMap=%u\n",
	715	pBlkMap, pStorage, offBlkMap, cBlkMap));
	716
	717	/* Make sure the number of blocks allocated for us match our expectations. */
[33745]	718	if (VCI_BYTE2BLOCK(pBlkMap->cBlocks / 8) + VCI_BYTE2BLOCK(sizeof(VciBlkMap)) == cBlkMap)
[32553]	719	{
	720	/* Setup the header */
	721	memset(&BlkMap, 0, sizeof(VciBlkMap));
	722
	723	BlkMap.u32Magic = RT_H2LE_U32(VCI_BLKMAP_MAGIC);
	724	BlkMap.u32Version = RT_H2LE_U32(VCI_BLKMAP_VERSION);
	725	BlkMap.cBlocks = RT_H2LE_U32(pBlkMap->cBlocks);
	726	BlkMap.cBlocksFree = RT_H2LE_U32(pBlkMap->cBlocksFree);
	727	BlkMap.cBlocksAllocMeta = RT_H2LE_U32(pBlkMap->cBlocksAllocMeta);
	728	BlkMap.cBlocksAllocData = RT_H2LE_U32(pBlkMap->cBlocksAllocData);
	729
[38469]	730	rc = vdIfIoIntFileWriteSync(pStorage->pIfIo, pStorage->pStorage, offBlkMap,
[44233]	731	&BlkMap, VCI_BYTE2BLOCK(sizeof(VciBlkMap)));
[32553]	732	if (RT_SUCCESS(rc))
	733	{
[33481]	734	uint8_t abBitmapBuffer[16*_1K];
	735	unsigned iBit = 0;
	736	PVCIBLKRANGEDESC pCur = pBlkMap->pRangesHead;
	737
[32553]	738	offBlkMap += VCI_BYTE2BLOCK(sizeof(VciBlkMap));
[33481]	739
	740	/* Write the descriptor ranges. */
	741	while (pCur)
	742	{
	743	uint64_t cBlocks = pCur->cBlocks;
	744
	745	while (cBlocks)
	746	{
	747	uint64_t cBlocksMax = RT_MIN(cBlocks, sizeof(abBitmapBuffer) * 8 - iBit);
	748
	749	if (pCur->fFree)
	750	ASMBitClearRange(abBitmapBuffer, iBit, iBit + cBlocksMax);
	751	else
	752	ASMBitSetRange(abBitmapBuffer, iBit, iBit + cBlocksMax);
	753
	754	iBit += cBlocksMax;
	755	cBlocks -= cBlocksMax;
	756
	757	if (iBit == sizeof(abBitmapBuffer) * 8)
	758	{
	759	/* Buffer is full, write to file and reset. */
[38469]	760	rc = vdIfIoIntFileWriteSync(pStorage->pIfIo, pStorage->pStorage,
	761	offBlkMap, abBitmapBuffer,
[44233]	762	VCI_BYTE2BLOCK(sizeof(abBitmapBuffer)));
[33481]	763	if (RT_FAILURE(rc))
	764	break;
	765
	766	offBlkMap += VCI_BYTE2BLOCK(sizeof(abBitmapBuffer));
	767	iBit = 0;
	768	}
	769	}
	770
	771	pCur = pCur->pNext;
	772	}
	773
	774	Assert(iBit % 8 == 0);
	775
	776	if (RT_SUCCESS(rc) && iBit)
[38469]	777	rc = vdIfIoIntFileWriteSync(pStorage->pIfIo, pStorage->pStorage,
[44233]	778	offBlkMap, abBitmapBuffer, VCI_BYTE2BLOCK(iBit / 8));
[32553]	779	}
	780	}
	781	else
[63567]	782	rc = VERR_INTERNAL_ERROR; /** @todo Better error code. */
[32553]	783
	784	LogFlowFunc(("returns rc=%Rrc\n", rc));
	785	return rc;
	786	}
	787
[62873]	788	#if 0 /* unused */
[32553]	789	/**
[33481]	790	* Finds the range block describing the given block address.
	791	*
	792	* @returns Pointer to the block range descriptor or NULL if none could be found.
	793	* @param pBlkMap The block bitmap to search on.
	794	* @param offBlockAddr The block address to search for.
	795	*/
	796	static PVCIBLKRANGEDESC vciBlkMapFindByBlock(PVCIBLKMAP pBlkMap, uint64_t offBlockAddr)
	797	{
	798	PVCIBLKRANGEDESC pBlk = pBlkMap->pRangesHead;
	799
	800	while ( pBlk
	801	&& pBlk->offAddrStart < offBlockAddr)
	802	pBlk = pBlk->pNext;
	803
	804	return pBlk;
	805	}
[62873]	806	#endif
[33481]	807
	808	/**
[32553]	809	* Allocates the given number of blocks in the bitmap and returns the start block address.
	810	*
	811	* @returns VBox status code.
	812	* @param pBlkMap The block bitmap to allocate the blocks from.
	813	* @param cBlocks How many blocks to allocate.
[38469]	814	* @param fFlags Allocation flags, comgination of VCIBLKMAP_ALLOC_*.
[32553]	815	* @param poffBlockAddr Where to store the start address of the allocated region.
	816	*/
[38469]	817	static int vciBlkMapAllocate(PVCIBLKMAP pBlkMap, uint32_t cBlocks, uint32_t fFlags,
	818	uint64_t *poffBlockAddr)
[32553]	819	{
[33481]	820	PVCIBLKRANGEDESC pBestFit = NULL;
	821	PVCIBLKRANGEDESC pCur = NULL;
[32553]	822	int rc = VINF_SUCCESS;
	823
	824	LogFlowFunc(("pBlkMap=%#p cBlocks=%u poffBlockAddr=%#p\n",
	825	pBlkMap, cBlocks, poffBlockAddr));
	826
[33481]	827	pCur = pBlkMap->pRangesHead;
	828
	829	while (pCur)
	830	{
	831	if ( pCur->fFree
	832	&& pCur->cBlocks >= cBlocks)
	833	{
	834	if ( !pBestFit
	835	\|\| pCur->cBlocks < pBestFit->cBlocks)
	836	{
	837	pBestFit = pCur;
	838	/* Stop searching if the size is matching exactly. */
	839	if (pBestFit->cBlocks == cBlocks)
	840	break;
	841	}
	842	}
	843	pCur = pCur->pNext;
	844	}
	845
	846	Assert(!pBestFit \|\| pBestFit->fFree);
	847
	848	if (pBestFit)
	849	{
	850	pBestFit->fFree = false;
	851
	852	if (pBestFit->cBlocks > cBlocks)
	853	{
	854	/* Create a new free block. */
	855	PVCIBLKRANGEDESC pFree = (PVCIBLKRANGEDESC)RTMemAllocZ(sizeof(VCIBLKRANGEDESC));
	856
	857	if (pFree)
	858	{
	859	pFree->fFree = true;
	860	pFree->cBlocks = pBestFit->cBlocks - cBlocks;
[33745]	861	pBestFit->cBlocks -= pFree->cBlocks;
[33481]	862	pFree->offAddrStart = pBestFit->offAddrStart + cBlocks;
	863
	864	/* Link into the list. */
	865	pFree->pNext = pBestFit->pNext;
	866	pBestFit->pNext = pFree;
	867	pFree->pPrev = pBestFit;
	868	if (!pFree->pNext)
	869	pBlkMap->pRangesTail = pFree;
	870
	871	*poffBlockAddr = pBestFit->offAddrStart;
	872	}
	873	else
	874	{
	875	rc = VERR_NO_MEMORY;
	876	pBestFit->fFree = true;
	877	}
	878	}
	879	}
	880	else
	881	rc = VERR_VCI_NO_BLOCKS_FREE;
	882
[38469]	883	if (RT_SUCCESS(rc))
	884	{
	885	if ((fFlags & VCIBLKMAP_ALLOC_MASK) == VCIBLKMAP_ALLOC_DATA)
	886	pBlkMap->cBlocksAllocMeta += cBlocks;
	887	else
	888	pBlkMap->cBlocksAllocData += cBlocks;
	889
	890	pBlkMap->cBlocksFree -= cBlocks;
	891	}
	892
[32553]	893	LogFlowFunc(("returns rc=%Rrc offBlockAddr=%llu\n", rc, *poffBlockAddr));
	894	return rc;
	895	}
	896
[62873]	897	#if 0 /* unused */
[32553]	898	/**
	899	* Try to extend the space of an already allocated block.
	900	*
	901	* @returns VBox status code.
	902	* @param pBlkMap The block bitmap to allocate the blocks from.
	903	* @param cBlocksNew How many blocks the extended block should have.
	904	* @param offBlockAddrOld The start address of the block to reallocate.
	905	* @param poffBlockAddr Where to store the start address of the allocated region.
	906	*/
	907	static int vciBlkMapRealloc(PVCIBLKMAP pBlkMap, uint32_t cBlocksNew, uint64_t offBlockAddrOld,
	908	uint64_t *poffBlockAddr)
	909	{
	910	int rc = VINF_SUCCESS;
	911
	912	LogFlowFunc(("pBlkMap=%#p cBlocksNew=%u offBlockAddrOld=%llu poffBlockAddr=%#p\n",
	913	pBlkMap, cBlocksNew, offBlockAddrOld, poffBlockAddr));
	914
[33481]	915	AssertMsgFailed(("Implement\n"));
[62736]	916	RT_NOREF4(pBlkMap, cBlocksNew, offBlockAddrOld, poffBlockAddr);
[33481]	917
[32553]	918	LogFlowFunc(("returns rc=%Rrc offBlockAddr=%llu\n", rc, *poffBlockAddr));
	919	return rc;
	920	}
[62873]	921	#endif /* unused */
[32553]	922
[62873]	923	#if 0 /* unused */
[32553]	924	/**
	925	* Frees a range of blocks.
	926	*
	927	* @param pBlkMap The block bitmap.
	928	* @param offBlockAddr Address of the first block to free.
	929	* @param cBlocks How many blocks to free.
[38469]	930	* @param fFlags Allocation flags, comgination of VCIBLKMAP_ALLOC_*.
[32553]	931	*/
[38469]	932	static void vciBlkMapFree(PVCIBLKMAP pBlkMap, uint64_t offBlockAddr, uint32_t cBlocks,
	933	uint32_t fFlags)
[32553]	934	{
[33481]	935	PVCIBLKRANGEDESC pBlk;
	936
[32553]	937	LogFlowFunc(("pBlkMap=%#p offBlockAddr=%llu cBlocks=%u\n",
	938	pBlkMap, offBlockAddr, cBlocks));
	939
[33481]	940	while (cBlocks)
	941	{
	942	pBlk = vciBlkMapFindByBlock(pBlkMap, offBlockAddr);
	943	AssertPtr(pBlk);
	944
	945	/* Easy case, the whole block is freed. */
	946	if ( pBlk->offAddrStart == offBlockAddr
	947	&& pBlk->cBlocks <= cBlocks)
	948	{
	949	pBlk->fFree = true;
	950	cBlocks -= pBlk->cBlocks;
	951	offBlockAddr += pBlk->cBlocks;
	952
	953	/* Check if it is possible to merge free blocks. */
	954	if ( pBlk->pPrev
	955	&& pBlk->pPrev->fFree)
	956	{
	957	PVCIBLKRANGEDESC pBlkPrev = pBlk->pPrev;
	958
	959	Assert(pBlkPrev->offAddrStart + pBlkPrev->cBlocks == pBlk->offAddrStart);
	960	pBlkPrev->cBlocks += pBlk->cBlocks;
	961	pBlkPrev->pNext = pBlk->pNext;
	962	if (pBlk->pNext)
	963	pBlk->pNext->pPrev = pBlkPrev;
	964	else
	965	pBlkMap->pRangesTail = pBlkPrev;
	966
	967	RTMemFree(pBlk);
	968	pBlk = pBlkPrev;
	969	}
	970
	971	/* Now the one to the right. */
	972	if ( pBlk->pNext
	973	&& pBlk->pNext->fFree)
	974	{
	975	PVCIBLKRANGEDESC pBlkNext = pBlk->pNext;
	976
	977	Assert(pBlk->offAddrStart + pBlk->cBlocks == pBlkNext->offAddrStart);
	978	pBlk->cBlocks += pBlkNext->cBlocks;
	979	pBlk->pNext = pBlkNext->pNext;
	980	if (pBlkNext->pNext)
	981	pBlkNext->pNext->pPrev = pBlk;
	982	else
	983	pBlkMap->pRangesTail = pBlk;
	984
	985	RTMemFree(pBlkNext);
	986	}
	987	}
	988	else
	989	{
	990	/* The block is intersecting. */
	991	AssertMsgFailed(("TODO\n"));
	992	}
	993	}
	994
[38469]	995	if ((fFlags & VCIBLKMAP_ALLOC_MASK) == VCIBLKMAP_ALLOC_DATA)
	996	pBlkMap->cBlocksAllocMeta -= cBlocks;
	997	else
	998	pBlkMap->cBlocksAllocData -= cBlocks;
	999
	1000	pBlkMap->cBlocksFree += cBlocks;
	1001
[32553]	1002	LogFlowFunc(("returns\n"));
	1003	}
[62873]	1004	#endif /* unused */
[32553]	1005
	1006	/**
[33481]	1007	* Converts a tree node from the image to the in memory structure.
	1008	*
	1009	* @returns Pointer to the in memory tree node.
	1010	* @param offBlockAddrNode Block address of the node.
	1011	* @param pNodeImage Pointer to the image representation of the node.
	1012	*/
	1013	static PVCITREENODE vciTreeNodeImage2Host(uint64_t offBlockAddrNode, PVciTreeNode pNodeImage)
	1014	{
	1015	PVCITREENODE pNode = NULL;
	1016
	1017	if (pNodeImage->u8Type == VCI_TREE_NODE_TYPE_LEAF)
	1018	{
	1019	PVCITREENODELEAF pLeaf = (PVCITREENODELEAF)RTMemAllocZ(sizeof(VCITREENODELEAF));
	1020
	1021	if (pLeaf)
	1022	{
	1023	PVciCacheExtent pExtent = (PVciCacheExtent)&pNodeImage->au8Data[0];
	1024
	1025	pLeaf->Core.u8Type = VCI_TREE_NODE_TYPE_LEAF;
	1026
	1027	for (unsigned idx = 0; idx < RT_ELEMENTS(pLeaf->aExtents); idx++)
	1028	{
	1029	pLeaf->aExtents[idx].u64BlockOffset = RT_LE2H_U64(pExtent->u64BlockOffset);
	1030	pLeaf->aExtents[idx].u32Blocks = RT_LE2H_U32(pExtent->u32Blocks);
	1031	pLeaf->aExtents[idx].u64BlockAddr = RT_LE2H_U64(pExtent->u64BlockAddr);
	1032	pExtent++;
	1033
	1034	if ( pLeaf->aExtents[idx].u32Blocks
	1035	&& pLeaf->aExtents[idx].u64BlockAddr)
	1036	pLeaf->cUsedNodes++;
	1037	}
	1038
	1039	pNode = &pLeaf->Core;
	1040	}
	1041	}
	1042	else if (pNodeImage->u8Type == VCI_TREE_NODE_TYPE_INTERNAL)
	1043	{
	1044	PVCITREENODEINT pInt = (PVCITREENODEINT)RTMemAllocZ(sizeof(VCITREENODEINT));
	1045
	1046	if (pInt)
	1047	{
	1048	PVciTreeNodeInternal pIntImage = (PVciTreeNodeInternal)&pNodeImage->au8Data[0];
	1049
	1050	pInt->Core.u8Type = VCI_TREE_NODE_TYPE_INTERNAL;
	1051
	1052	for (unsigned idx = 0; idx < RT_ELEMENTS(pInt->aIntNodes); idx++)
	1053	{
	1054	pInt->aIntNodes[idx].u64BlockOffset = RT_LE2H_U64(pIntImage->u64BlockOffset);
	1055	pInt->aIntNodes[idx].u32Blocks = RT_LE2H_U32(pIntImage->u32Blocks);
	1056	pInt->aIntNodes[idx].PtrChild.fInMemory = false;
	1057	pInt->aIntNodes[idx].PtrChild.u.offAddrBlockNode = RT_LE2H_U64(pIntImage->u64ChildAddr);
	1058	pIntImage++;
	1059
	1060	if ( pInt->aIntNodes[idx].u32Blocks
	1061	&& pInt->aIntNodes[idx].PtrChild.u.offAddrBlockNode)
	1062	pInt->cUsedNodes++;
	1063	}
	1064
	1065	pNode = &pInt->Core;
	1066	}
	1067	}
	1068	else
	1069	AssertMsgFailed(("Invalid node type %d\n", pNodeImage->u8Type));
	1070
	1071	if (pNode)
	1072	pNode->u64BlockAddr = offBlockAddrNode;
	1073
	1074	return pNode;
	1075	}
	1076
	1077	/**
	1078	* Looks up the cache extent for the given virtual block address.
	1079	*
	1080	* @returns Pointer to the cache extent or NULL if none could be found.
	1081	* @param pCache The cache image instance.
	1082	* @param offBlockOffset The block offset to search for.
[38469]	1083	* @param ppNextBestFit Where to store the pointer to the next best fit
	1084	* cache extent above offBlockOffset if existing. - Optional
	1085	* This is always filled if possible even if the function returns NULL.
[33481]	1086	*/
[38469]	1087	static PVCICACHEEXTENT vciCacheExtentLookup(PVCICACHE pCache, uint64_t offBlockOffset,
	1088	PVCICACHEEXTENT *ppNextBestFit)
[33481]	1089	{
	1090	int rc = VINF_SUCCESS;
	1091	PVCICACHEEXTENT pExtent = NULL;
	1092	PVCITREENODE pNodeCur = pCache->pRoot;
	1093
	1094	while ( RT_SUCCESS(rc)
	1095	&& pNodeCur
	1096	&& pNodeCur->u8Type != VCI_TREE_NODE_TYPE_LEAF)
	1097	{
	1098	PVCITREENODEINT pNodeInt = (PVCITREENODEINT)pNodeCur;
	1099
	1100	Assert(pNodeCur->u8Type == VCI_TREE_NODE_TYPE_INTERNAL);
	1101
	1102	/* Search for the correct internal node. */
	1103	unsigned idxMin = 0;
	1104	unsigned idxMax = pNodeInt->cUsedNodes;
	1105	unsigned idxCur = pNodeInt->cUsedNodes / 2;
	1106
	1107	while (idxMin < idxMax)
	1108	{
	1109	PVCINODEINTERNAL pInt = &pNodeInt->aIntNodes[idxCur];
	1110
	1111	/* Determine the search direction. */
	1112	if (offBlockOffset < pInt->u64BlockOffset)
	1113	{
	1114	/* Search left from the current extent. */
	1115	idxMax = idxCur;
	1116	}
	1117	else if (offBlockOffset >= pInt->u64BlockOffset + pInt->u32Blocks)
	1118	{
	1119	/* Search right from the current extent. */
	1120	idxMin = idxCur;
	1121	}
	1122	else
	1123	{
	1124	/* The block lies in the node, stop searching. */
	1125	if (pInt->PtrChild.fInMemory)
	1126	pNodeCur = pInt->PtrChild.u.pNode;
	1127	else
	1128	{
	1129	PVCITREENODE pNodeNew;
	1130	VciTreeNode NodeTree;
	1131
	1132	/* Read from disk and add to the tree. */
[38469]	1133	rc = vdIfIoIntFileReadSync(pCache->pIfIo, pCache->pStorage,
	1134	VCI_BLOCK2BYTE(pInt->PtrChild.u.offAddrBlockNode),
[44233]	1135	&NodeTree, sizeof(NodeTree));
[33481]	1136	AssertRC(rc);
	1137
	1138	pNodeNew = vciTreeNodeImage2Host(pInt->PtrChild.u.offAddrBlockNode, &NodeTree);
	1139	if (pNodeNew)
	1140	{
	1141	/* Link to the parent. */
	1142	pInt->PtrChild.fInMemory = true;
	1143	pInt->PtrChild.u.pNode = pNodeNew;
	1144	pNodeNew->pParent = pNodeCur;
	1145	pNodeCur = pNodeNew;
	1146	}
	1147	else
	1148	rc = VERR_NO_MEMORY;
	1149	}
	1150	break;
	1151	}
	1152
	1153	idxCur = idxMin + (idxMax - idxMin) / 2;
	1154	}
	1155	}
	1156
	1157	if ( RT_SUCCESS(rc)
	1158	&& pNodeCur)
	1159	{
	1160	PVCITREENODELEAF pLeaf = (PVCITREENODELEAF)pNodeCur;
	1161	Assert(pNodeCur->u8Type == VCI_TREE_NODE_TYPE_LEAF);
	1162
	1163	/* Search the range. */
	1164	unsigned idxMin = 0;
	1165	unsigned idxMax = pLeaf->cUsedNodes;
	1166	unsigned idxCur = pLeaf->cUsedNodes / 2;
	1167
	1168	while (idxMin < idxMax)
	1169	{
	1170	PVCICACHEEXTENT pExtentCur = &pLeaf->aExtents[idxCur];
	1171
	1172	/* Determine the search direction. */
	1173	if (offBlockOffset < pExtentCur->u64BlockOffset)
	1174	{
	1175	/* Search left from the current extent. */
	1176	idxMax = idxCur;
	1177	}
	1178	else if (offBlockOffset >= pExtentCur->u64BlockOffset + pExtentCur->u32Blocks)
	1179	{
	1180	/* Search right from the current extent. */
	1181	idxMin = idxCur;
	1182	}
	1183	else
	1184	{
	1185	/* We found the extent, stop searching. */
	1186	pExtent = pExtentCur;
	1187	break;
	1188	}
	1189
	1190	idxCur = idxMin + (idxMax - idxMin) / 2;
	1191	}
[38469]	1192
	1193	/* Get the next best fit extent if it exists. */
	1194	if (ppNextBestFit)
	1195	{
	1196	if (idxCur < pLeaf->cUsedNodes - 1)
	1197	*ppNextBestFit = &pLeaf->aExtents[idxCur + 1];
	1198	else
	1199	{
	1200	/*
	1201	* Go up the tree and find the best extent
	1202	* in the leftmost tree of the child subtree to the right.
	1203	*/
	1204	PVCITREENODEINT pInt = (PVCITREENODEINT)pLeaf->Core.pParent;
	1205
	1206	while (pInt)
	1207	{
[44412]	1208
[38469]	1209	}
	1210	}
	1211	}
[33481]	1212	}
	1213
	1214	return pExtent;
	1215	}
	1216
	1217	/**
[32370]	1218	* Internal: Open an image, constructing all necessary data structures.
	1219	*/
[33481]	1220	static int vciOpenImage(PVCICACHE pCache, unsigned uOpenFlags)
[32370]	1221	{
[33481]	1222	VciHdr Hdr;
	1223	uint64_t cbFile;
[32370]	1224	int rc;
	1225
[33481]	1226	pCache->uOpenFlags = uOpenFlags;
[32370]	1227
[38469]	1228	pCache->pIfError = VDIfErrorGet(pCache->pVDIfsDisk);
	1229	pCache->pIfIo = VDIfIoIntGet(pCache->pVDIfsImage);
	1230	AssertPtrReturn(pCache->pIfIo, VERR_INVALID_PARAMETER);
[32370]	1231
	1232	/*
	1233	* Open the image.
	1234	*/
[38469]	1235	rc = vdIfIoIntFileOpen(pCache->pIfIo, pCache->pszFilename,
	1236	VDOpenFlagsToFileOpenFlags(uOpenFlags,
	1237	false /* fCreate */),
	1238	&pCache->pStorage);
[32370]	1239	if (RT_FAILURE(rc))
	1240	{
	1241	/* Do NOT signal an appropriate error here, as the VD layer has the
	1242	* choice of retrying the open if it failed. */
	1243	goto out;
	1244	}
	1245
[38469]	1246	rc = vdIfIoIntFileGetSize(pCache->pIfIo, pCache->pStorage, &cbFile);
[33481]	1247	if (RT_FAILURE(rc) \|\| cbFile < sizeof(VciHdr))
	1248	{
	1249	rc = VERR_VD_GEN_INVALID_HEADER;
	1250	goto out;
	1251	}
	1252
[38469]	1253	rc = vdIfIoIntFileReadSync(pCache->pIfIo, pCache->pStorage, 0, &Hdr,
[44233]	1254	VCI_BYTE2BLOCK(sizeof(Hdr)));
[32370]	1255	if (RT_FAILURE(rc))
	1256	{
[33481]	1257	rc = VERR_VD_GEN_INVALID_HEADER;
[32370]	1258	goto out;
	1259	}
	1260
[33481]	1261	Hdr.u32Signature = RT_LE2H_U32(Hdr.u32Signature);
	1262	Hdr.u32Version = RT_LE2H_U32(Hdr.u32Version);
	1263	Hdr.cBlocksCache = RT_LE2H_U64(Hdr.cBlocksCache);
	1264	Hdr.u32CacheType = RT_LE2H_U32(Hdr.u32CacheType);
	1265	Hdr.offTreeRoot = RT_LE2H_U64(Hdr.offTreeRoot);
	1266	Hdr.offBlkMap = RT_LE2H_U64(Hdr.offBlkMap);
[40843]	1267	Hdr.cBlkMap = RT_LE2H_U32(Hdr.cBlkMap);
[33481]	1268
	1269	if ( Hdr.u32Signature == VCI_HDR_SIGNATURE
	1270	&& Hdr.u32Version == VCI_HDR_VERSION)
	1271	{
	1272	pCache->offTreeRoot = Hdr.offTreeRoot;
	1273	pCache->offBlksBitmap = Hdr.offBlkMap;
	1274
	1275	/* Load the block map. */
[33745]	1276	rc = vciBlkMapLoad(pCache, pCache->offBlksBitmap, Hdr.cBlkMap, &pCache->pBlkMap);
[33481]	1277	if (RT_SUCCESS(rc))
	1278	{
	1279	/* Load the first tree node. */
	1280	VciTreeNode RootNode;
	1281
[38469]	1282	rc = vdIfIoIntFileReadSync(pCache->pIfIo, pCache->pStorage,
	1283	pCache->offTreeRoot, &RootNode,
[44233]	1284	VCI_BYTE2BLOCK(sizeof(VciTreeNode)));
[33481]	1285	if (RT_SUCCESS(rc))
	1286	{
	1287	pCache->pRoot = vciTreeNodeImage2Host(pCache->offTreeRoot, &RootNode);
	1288	if (!pCache->pRoot)
	1289	rc = VERR_NO_MEMORY;
	1290	}
	1291	}
	1292	}
	1293	else
	1294	rc = VERR_VD_GEN_INVALID_HEADER;
	1295
[32370]	1296	out:
	1297	if (RT_FAILURE(rc))
[33481]	1298	vciFreeImage(pCache, false);
[32370]	1299	return rc;
	1300	}
	1301
	1302	/**
	1303	* Internal: Create a vci image.
	1304	*/
[33481]	1305	static int vciCreateImage(PVCICACHE pCache, uint64_t cbSize,
[32370]	1306	unsigned uImageFlags, const char *pszComment,
[32536]	1307	unsigned uOpenFlags, PFNVDPROGRESS pfnProgress,
	1308	void *pvUser, unsigned uPercentStart,
	1309	unsigned uPercentSpan)
[32370]	1310	{
[62736]	1311	RT_NOREF1(pszComment);
[32553]	1312	VciHdr Hdr;
	1313	VciTreeNode NodeRoot;
[32370]	1314	int rc;
[32553]	1315	uint64_t cBlocks = cbSize / VCI_BLOCK_SIZE; /* Size of the cache in blocks. */
[32370]	1316
[38469]	1317	pCache->uImageFlags = uImageFlags;
	1318	pCache->uOpenFlags = uOpenFlags & ~VD_OPEN_FLAGS_READONLY;
	1319
	1320	pCache->pIfError = VDIfErrorGet(pCache->pVDIfsDisk);
	1321	pCache->pIfIo = VDIfIoIntGet(pCache->pVDIfsImage);
	1322	AssertPtrReturn(pCache->pIfIo, VERR_INVALID_PARAMETER);
	1323
[32370]	1324	if (uImageFlags & VD_IMAGE_FLAGS_DIFF)
	1325	{
[38469]	1326	rc = vdIfError(pCache->pIfError, VERR_VD_RAW_INVALID_TYPE, RT_SRC_POS, N_("VCI: cannot create diff image '%s'"), pCache->pszFilename);
[32553]	1327	return rc;
[32370]	1328	}
	1329
[32553]	1330	do
[32370]	1331	{
[32553]	1332	/* Create image file. */
[38469]	1333	rc = vdIfIoIntFileOpen(pCache->pIfIo, pCache->pszFilename,
	1334	VDOpenFlagsToFileOpenFlags(uOpenFlags & ~VD_OPEN_FLAGS_READONLY,
	1335	true /* fCreate */),
	1336	&pCache->pStorage);
[32553]	1337	if (RT_FAILURE(rc))
	1338	{
[38469]	1339	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot create image '%s'"), pCache->pszFilename);
[32553]	1340	break;
	1341	}
[32370]	1342
[32553]	1343	/* Allocate block bitmap. */
	1344	uint32_t cBlkMap = 0;
[33481]	1345	rc = vciBlkMapCreate(cBlocks, &pCache->pBlkMap, &cBlkMap);
[32553]	1346	if (RT_FAILURE(rc))
	1347	{
[38469]	1348	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot create block bitmap '%s'"), pCache->pszFilename);
[32553]	1349	break;
	1350	}
[32370]	1351
[32553]	1352	/*
	1353	* Allocate space for the header in the block bitmap.
[32688]	1354	* Because the block map is empty the header has to start at block 0
[32553]	1355	*/
	1356	uint64_t offHdr = 0;
[38469]	1357	rc = vciBlkMapAllocate(pCache->pBlkMap, VCI_BYTE2BLOCK(sizeof(VciHdr)), VCIBLKMAP_ALLOC_META, &offHdr);
[32553]	1358	if (RT_FAILURE(rc))
	1359	{
[38469]	1360	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot allocate space for header in block bitmap '%s'"), pCache->pszFilename);
[32553]	1361	break;
	1362	}
[32370]	1363
[32553]	1364	Assert(offHdr == 0);
[32370]	1365
[32553]	1366	/*
	1367	* Allocate space for the block map itself.
	1368	*/
	1369	uint64_t offBlkMap = 0;
[38469]	1370	rc = vciBlkMapAllocate(pCache->pBlkMap, cBlkMap, VCIBLKMAP_ALLOC_META, &offBlkMap);
[32553]	1371	if (RT_FAILURE(rc))
	1372	{
[38469]	1373	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot allocate space for block map in block map '%s'"), pCache->pszFilename);
[32553]	1374	break;
	1375	}
[32370]	1376
[32553]	1377	/*
	1378	* Allocate space for the tree root node.
	1379	*/
	1380	uint64_t offTreeRoot = 0;
[38469]	1381	rc = vciBlkMapAllocate(pCache->pBlkMap, VCI_BYTE2BLOCK(sizeof(VciTreeNode)), VCIBLKMAP_ALLOC_META, &offTreeRoot);
[32370]	1382	if (RT_FAILURE(rc))
	1383	{
[38469]	1384	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot allocate space for block map in block map '%s'"), pCache->pszFilename);
[32553]	1385	break;
[32370]	1386	}
	1387
[32553]	1388	/*
[33481]	1389	* Allocate the in memory root node.
	1390	*/
	1391	pCache->pRoot = (PVCITREENODE)RTMemAllocZ(sizeof(VCITREENODELEAF));
	1392	if (!pCache->pRoot)
	1393	{
[38469]	1394	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot allocate B+-Tree root pointer '%s'"), pCache->pszFilename);
[33481]	1395	break;
	1396	}
	1397
	1398	pCache->pRoot->u8Type = VCI_TREE_NODE_TYPE_LEAF;
	1399	/* Rest remains 0 as the tree is still empty. */
	1400
	1401	/*
[32553]	1402	* Now that we are here we have all the basic structures and know where to place them in the image.
	1403	* It's time to write it now.
	1404	*/
[32370]	1405
[32553]	1406	/* Setup the header. */
	1407	memset(&Hdr, 0, sizeof(VciHdr));
	1408	Hdr.u32Signature = RT_H2LE_U32(VCI_HDR_SIGNATURE);
	1409	Hdr.u32Version = RT_H2LE_U32(VCI_HDR_VERSION);
	1410	Hdr.cBlocksCache = RT_H2LE_U64(cBlocks);
	1411	Hdr.fUncleanShutdown = VCI_HDR_UNCLEAN_SHUTDOWN;
	1412	Hdr.u32CacheType = uImageFlags & VD_IMAGE_FLAGS_FIXED
	1413	? RT_H2LE_U32(VCI_HDR_CACHE_TYPE_FIXED)
	1414	: RT_H2LE_U32(VCI_HDR_CACHE_TYPE_DYNAMIC);
	1415	Hdr.offTreeRoot = RT_H2LE_U64(offTreeRoot);
	1416	Hdr.offBlkMap = RT_H2LE_U64(offBlkMap);
[40843]	1417	Hdr.cBlkMap = RT_H2LE_U32(cBlkMap);
[32553]	1418
[38469]	1419	rc = vdIfIoIntFileWriteSync(pCache->pIfIo, pCache->pStorage, offHdr, &Hdr,
[44233]	1420	VCI_BYTE2BLOCK(sizeof(VciHdr)));
[32553]	1421	if (RT_FAILURE(rc))
[32370]	1422	{
[38469]	1423	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot write header '%s'"), pCache->pszFilename);
[32553]	1424	break;
[32370]	1425	}
	1426
[33481]	1427	rc = vciBlkMapSave(pCache->pBlkMap, pCache, offBlkMap, cBlkMap);
[32553]	1428	if (RT_FAILURE(rc))
	1429	{
[38469]	1430	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot write block map '%s'"), pCache->pszFilename);
[32553]	1431	break;
	1432	}
[32370]	1433
[32553]	1434	/* Setup the root tree. */
	1435	memset(&NodeRoot, 0, sizeof(VciTreeNode));
[71522]	1436	NodeRoot.u8Type = VCI_TREE_NODE_TYPE_LEAF;
[32370]	1437
[38469]	1438	rc = vdIfIoIntFileWriteSync(pCache->pIfIo, pCache->pStorage, offTreeRoot,
[44233]	1439	&NodeRoot, VCI_BYTE2BLOCK(sizeof(VciTreeNode)));
[32553]	1440	if (RT_FAILURE(rc))
	1441	{
[38469]	1442	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot write root node '%s'"), pCache->pszFilename);
[32553]	1443	break;
	1444	}
[32370]	1445
[33481]	1446	rc = vciFlushImage(pCache);
[32553]	1447	if (RT_FAILURE(rc))
	1448	{
[38469]	1449	rc = vdIfError(pCache->pIfError, rc, RT_SRC_POS, N_("VCI: cannot flush '%s'"), pCache->pszFilename);
[32553]	1450	break;
	1451	}
	1452
[33481]	1453	pCache->cbSize = cbSize;
[32553]	1454
	1455	} while (0);
	1456
[32370]	1457	if (RT_SUCCESS(rc) && pfnProgress)
	1458	pfnProgress(pvUser, uPercentStart + uPercentSpan);
	1459
	1460	if (RT_FAILURE(rc))
[33481]	1461	vciFreeImage(pCache, rc != VERR_ALREADY_EXISTS);
[32370]	1462	return rc;
	1463	}
	1464
	1465	/** @copydoc VDCACHEBACKEND::pfnProbe */
[64272]	1466	static DECLCALLBACK(int) vciProbe(const char *pszFilename, PVDINTERFACE pVDIfsDisk,
[57388]	1467	PVDINTERFACE pVDIfsImage)
[32370]	1468	{
[64272]	1469	RT_NOREF1(pVDIfsDisk);
[33481]	1470	VciHdr Hdr;
[38469]	1471	PVDIOSTORAGE pStorage = NULL;
[33481]	1472	uint64_t cbFile;
[32370]	1473	int rc = VINF_SUCCESS;
	1474
[33481]	1475	LogFlowFunc(("pszFilename=\"%s\"\n", pszFilename));
	1476
[38469]	1477	PVDINTERFACEIOINT pIfIo = VDIfIoIntGet(pVDIfsImage);
	1478	AssertPtrReturn(pIfIo, VERR_INVALID_PARAMETER);
[33481]	1479
[38469]	1480	rc = vdIfIoIntFileOpen(pIfIo, pszFilename,
	1481	VDOpenFlagsToFileOpenFlags(VD_OPEN_FLAGS_READONLY,
	1482	false /* fCreate */),
	1483	&pStorage);
[33481]	1484	if (RT_FAILURE(rc))
	1485	goto out;
	1486
[38469]	1487	rc = vdIfIoIntFileGetSize(pIfIo, pStorage, &cbFile);
[33481]	1488	if (RT_FAILURE(rc) \|\| cbFile < sizeof(VciHdr))
[32370]	1489	{
[33481]	1490	rc = VERR_VD_GEN_INVALID_HEADER;
[32370]	1491	goto out;
	1492	}
	1493
[44233]	1494	rc = vdIfIoIntFileReadSync(pIfIo, pStorage, 0, &Hdr, sizeof(Hdr));
[33481]	1495	if (RT_FAILURE(rc))
	1496	{
	1497	rc = VERR_VD_GEN_INVALID_HEADER;
	1498	goto out;
	1499	}
	1500
	1501	Hdr.u32Signature = RT_LE2H_U32(Hdr.u32Signature);
	1502	Hdr.u32Version = RT_LE2H_U32(Hdr.u32Version);
	1503	Hdr.cBlocksCache = RT_LE2H_U64(Hdr.cBlocksCache);
	1504	Hdr.u32CacheType = RT_LE2H_U32(Hdr.u32CacheType);
	1505	Hdr.offTreeRoot = RT_LE2H_U64(Hdr.offTreeRoot);
	1506	Hdr.offBlkMap = RT_LE2H_U64(Hdr.offBlkMap);
[40843]	1507	Hdr.cBlkMap = RT_LE2H_U32(Hdr.cBlkMap);
[33481]	1508
	1509	if ( Hdr.u32Signature == VCI_HDR_SIGNATURE
	1510	&& Hdr.u32Version == VCI_HDR_VERSION)
	1511	rc = VINF_SUCCESS;
	1512	else
	1513	rc = VERR_VD_GEN_INVALID_HEADER;
	1514
[38469]	1515	out:
	1516	if (pStorage)
	1517	vdIfIoIntFileClose(pIfIo, pStorage);
[33481]	1518
[32370]	1519	LogFlowFunc(("returns %Rrc\n", rc));
	1520	return rc;
	1521	}
	1522
	1523	/** @copydoc VDCACHEBACKEND::pfnOpen */
[57388]	1524	static DECLCALLBACK(int) vciOpen(const char *pszFilename, unsigned uOpenFlags,
	1525	PVDINTERFACE pVDIfsDisk, PVDINTERFACE pVDIfsImage,
	1526	void **ppBackendData)
[32370]	1527	{
[32536]	1528	LogFlowFunc(("pszFilename=\"%s\" uOpenFlags=%#x pVDIfsDisk=%#p pVDIfsImage=%#p ppBackendData=%#p\n", pszFilename, uOpenFlags, pVDIfsDisk, pVDIfsImage, ppBackendData));
[32370]	1529	int rc;
[33481]	1530	PVCICACHE pCache;
[32370]	1531
	1532	/* Check open flags. All valid flags are supported. */
	1533	if (uOpenFlags & ~VD_OPEN_FLAGS_MASK)
	1534	{
	1535	rc = VERR_INVALID_PARAMETER;
	1536	goto out;
	1537	}
	1538
	1539	/* Check remaining arguments. */
[90802]	1540	if ( !RT_VALID_PTR(pszFilename)
[32370]	1541	\|\| !*pszFilename)
	1542	{
	1543	rc = VERR_INVALID_PARAMETER;
	1544	goto out;
	1545	}
	1546
	1547
[33481]	1548	pCache = (PVCICACHE)RTMemAllocZ(sizeof(VCICACHE));
	1549	if (!pCache)
[32370]	1550	{
	1551	rc = VERR_NO_MEMORY;
	1552	goto out;
	1553	}
[33481]	1554	pCache->pszFilename = pszFilename;
	1555	pCache->pStorage = NULL;
	1556	pCache->pVDIfsDisk = pVDIfsDisk;
	1557	pCache->pVDIfsImage = pVDIfsImage;
[32370]	1558
[33481]	1559	rc = vciOpenImage(pCache, uOpenFlags);
[32370]	1560	if (RT_SUCCESS(rc))
[33481]	1561	*ppBackendData = pCache;
[32370]	1562	else
[33481]	1563	RTMemFree(pCache);
[32370]	1564
	1565	out:
[32536]	1566	LogFlowFunc(("returns %Rrc (pBackendData=%#p)\n", rc, *ppBackendData));
[32370]	1567	return rc;
	1568	}
	1569
	1570	/** @copydoc VDCACHEBACKEND::pfnCreate */
[57388]	1571	static DECLCALLBACK(int) vciCreate(const char *pszFilename, uint64_t cbSize,
	1572	unsigned uImageFlags, const char *pszComment,
	1573	PCRTUUID pUuid, unsigned uOpenFlags,
	1574	unsigned uPercentStart, unsigned uPercentSpan,
	1575	PVDINTERFACE pVDIfsDisk, PVDINTERFACE pVDIfsImage,
	1576	PVDINTERFACE pVDIfsOperation, void **ppBackendData)
[32370]	1577	{
[62736]	1578	RT_NOREF1(pUuid);
[32536]	1579	LogFlowFunc(("pszFilename=\"%s\" cbSize=%llu uImageFlags=%#x pszComment=\"%s\" Uuid=%RTuuid uOpenFlags=%#x uPercentStart=%u uPercentSpan=%u pVDIfsDisk=%#p pVDIfsImage=%#p pVDIfsOperation=%#p ppBackendData=%#p",
	1580	pszFilename, cbSize, uImageFlags, pszComment, pUuid, uOpenFlags, uPercentStart, uPercentSpan, pVDIfsDisk, pVDIfsImage, pVDIfsOperation, ppBackendData));
[32370]	1581	int rc;
[33481]	1582	PVCICACHE pCache;
[32370]	1583
	1584	PFNVDPROGRESS pfnProgress = NULL;
	1585	void *pvUser = NULL;
[38469]	1586	PVDINTERFACEPROGRESS pIfProgress = VDIfProgressGet(pVDIfsOperation);
[32370]	1587	if (pIfProgress)
	1588	{
[38469]	1589	pfnProgress = pIfProgress->pfnProgress;
	1590	pvUser = pIfProgress->Core.pvUser;
[32370]	1591	}
	1592
	1593	/* Check open flags. All valid flags are supported. */
	1594	if (uOpenFlags & ~VD_OPEN_FLAGS_MASK)
	1595	{
	1596	rc = VERR_INVALID_PARAMETER;
	1597	goto out;
	1598	}
	1599
	1600	/* Check remaining arguments. */
[90802]	1601	if ( !RT_VALID_PTR(pszFilename)
[32370]	1602	\|\| !*pszFilename)
	1603	{
	1604	rc = VERR_INVALID_PARAMETER;
	1605	goto out;
	1606	}
	1607
[33481]	1608	pCache = (PVCICACHE)RTMemAllocZ(sizeof(VCICACHE));
	1609	if (!pCache)
[32370]	1610	{
	1611	rc = VERR_NO_MEMORY;
	1612	goto out;
	1613	}
[33481]	1614	pCache->pszFilename = pszFilename;
	1615	pCache->pStorage = NULL;
	1616	pCache->pVDIfsDisk = pVDIfsDisk;
	1617	pCache->pVDIfsImage = pVDIfsImage;
[32370]	1618
[33481]	1619	rc = vciCreateImage(pCache, cbSize, uImageFlags, pszComment, uOpenFlags,
[32370]	1620	pfnProgress, pvUser, uPercentStart, uPercentSpan);
	1621	if (RT_SUCCESS(rc))
	1622	{
	1623	/* So far the image is opened in read/write mode. Make sure the
	1624	* image is opened in read-only mode if the caller requested that. */
	1625	if (uOpenFlags & VD_OPEN_FLAGS_READONLY)
	1626	{
[33481]	1627	vciFreeImage(pCache, false);
	1628	rc = vciOpenImage(pCache, uOpenFlags);
[32370]	1629	if (RT_FAILURE(rc))
	1630	{
[33481]	1631	RTMemFree(pCache);
[32370]	1632	goto out;
	1633	}
	1634	}
[33481]	1635	*ppBackendData = pCache;
[32370]	1636	}
	1637	else
[33481]	1638	RTMemFree(pCache);
[32370]	1639
	1640	out:
[32536]	1641	LogFlowFunc(("returns %Rrc (pBackendData=%#p)\n", rc, *ppBackendData));
[32370]	1642	return rc;
	1643	}
	1644
	1645	/** @copydoc VDCACHEBACKEND::pfnClose */
[57388]	1646	static DECLCALLBACK(int) vciClose(void *pBackendData, bool fDelete)
[32370]	1647	{
[32536]	1648	LogFlowFunc(("pBackendData=%#p fDelete=%d\n", pBackendData, fDelete));
[33481]	1649	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32536]	1650	int rc;
[32370]	1651
[33481]	1652	rc = vciFreeImage(pCache, fDelete);
	1653	RTMemFree(pCache);
[32370]	1654
	1655	LogFlowFunc(("returns %Rrc\n", rc));
	1656	return rc;
	1657	}
	1658
	1659	/** @copydoc VDCACHEBACKEND::pfnRead */
[57388]	1660	static DECLCALLBACK(int) vciRead(void *pBackendData, uint64_t uOffset, size_t cbToRead,
	1661	PVDIOCTX pIoCtx, size_t *pcbActuallyRead)
[32370]	1662	{
[44412]	1663	LogFlowFunc(("pBackendData=%#p uOffset=%llu cbToRead=%zu pIoCtx=%#p pcbActuallyRead=%#p\n",
	1664	pBackendData, uOffset, cbToRead, pIoCtx, pcbActuallyRead));
[33481]	1665	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32553]	1666	int rc = VINF_SUCCESS;
[33481]	1667	PVCICACHEEXTENT pExtent;
[38469]	1668	uint64_t cBlocksToRead = VCI_BYTE2BLOCK(cbToRead);
	1669	uint64_t offBlockAddr = VCI_BYTE2BLOCK(uOffset);
[32370]	1670
[33481]	1671	AssertPtr(pCache);
[32370]	1672	Assert(uOffset % 512 == 0);
	1673	Assert(cbToRead % 512 == 0);
	1674
[38469]	1675	pExtent = vciCacheExtentLookup(pCache, offBlockAddr, NULL);
[33481]	1676	if (pExtent)
	1677	{
[38469]	1678	uint64_t offRead = offBlockAddr - pExtent->u64BlockOffset;
	1679	cBlocksToRead = RT_MIN(cBlocksToRead, pExtent->u32Blocks - offRead);
[33481]	1680
[44412]	1681	rc = vdIfIoIntFileReadUser(pCache->pIfIo, pCache->pStorage,
[38469]	1682	pExtent->u64BlockAddr + offRead,
[44412]	1683	pIoCtx, cBlocksToRead);
[33481]	1684	}
	1685	else
	1686	{
	1687	/** @todo Best fit to check whether we have cached data later and set
	1688	* pcbActuallyRead accordingly. */
	1689	rc = VERR_VD_BLOCK_FREE;
	1690	}
	1691
	1692	if (pcbActuallyRead)
[38469]	1693	*pcbActuallyRead = VCI_BLOCK2BYTE(cBlocksToRead);
[33481]	1694
[32370]	1695	LogFlowFunc(("returns %Rrc\n", rc));
	1696	return rc;
	1697	}
	1698
	1699	/** @copydoc VDCACHEBACKEND::pfnWrite */
[57388]	1700	static DECLCALLBACK(int) vciWrite(void *pBackendData, uint64_t uOffset, size_t cbToWrite,
	1701	PVDIOCTX pIoCtx, size_t *pcbWriteProcess)
[32370]	1702	{
[62737]	1703	RT_NOREF5(pBackendData, uOffset, cbToWrite, pIoCtx, pcbWriteProcess);
[44412]	1704	LogFlowFunc(("pBackendData=%#p uOffset=%llu cbToWrite=%zu pIoCtx=%#p pcbWriteProcess=%#p\n",
	1705	pBackendData, uOffset, cbToWrite, pIoCtx, pcbWriteProcess));
[62741]	1706	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32553]	1707	int rc = VINF_SUCCESS;
[38469]	1708	uint64_t cBlocksToWrite = VCI_BYTE2BLOCK(cbToWrite);
[62737]	1709	//uint64_t offBlockAddr = VCI_BYTE2BLOCK(uOffset);
[32370]	1710
[62741]	1711	AssertPtr(pCache); NOREF(pCache);
[32370]	1712	Assert(uOffset % 512 == 0);
	1713	Assert(cbToWrite % 512 == 0);
[38469]	1714	while (cBlocksToWrite)
	1715	{
[44412]	1716
[38469]	1717	}
	1718
[63567]	1719	pcbWriteProcess = cbToWrite; /* @todo Implement. */
[45486]	1720
[32370]	1721	LogFlowFunc(("returns %Rrc\n", rc));
	1722	return rc;
	1723	}
	1724
	1725	/** @copydoc VDCACHEBACKEND::pfnFlush */
[57388]	1726	static DECLCALLBACK(int) vciFlush(void *pBackendData, PVDIOCTX pIoCtx)
[32370]	1727	{
[62737]	1728	RT_NOREF1(pIoCtx);
[32536]	1729	LogFlowFunc(("pBackendData=%#p\n", pBackendData));
[33481]	1730	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1731
[62737]	1732	int rc = vciFlushImage(pCache);
[32370]	1733	LogFlowFunc(("returns %Rrc\n", rc));
	1734	return rc;
	1735	}
	1736
	1737	/** @copydoc VDCACHEBACKEND::pfnGetVersion */
[57388]	1738	static DECLCALLBACK(unsigned) vciGetVersion(void *pBackendData)
[32370]	1739	{
[32536]	1740	LogFlowFunc(("pBackendData=%#p\n", pBackendData));
[33481]	1741	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1742
[33481]	1743	AssertPtr(pCache);
[32370]	1744
[33481]	1745	if (pCache)
[32370]	1746	return 1;
	1747	else
	1748	return 0;
	1749	}
	1750
	1751	/** @copydoc VDCACHEBACKEND::pfnGetSize */
[57388]	1752	static DECLCALLBACK(uint64_t) vciGetSize(void *pBackendData)
[32370]	1753	{
[32536]	1754	LogFlowFunc(("pBackendData=%#p\n", pBackendData));
[33481]	1755	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32536]	1756	uint64_t cb = 0;
[32370]	1757
[33481]	1758	AssertPtr(pCache);
[32370]	1759
[33481]	1760	if (pCache && pCache->pStorage)
	1761	cb = pCache->cbSize;
[32536]	1762
	1763	LogFlowFunc(("returns %llu\n", cb));
	1764	return cb;
[32370]	1765	}
	1766
	1767	/** @copydoc VDCACHEBACKEND::pfnGetFileSize */
[57388]	1768	static DECLCALLBACK(uint64_t) vciGetFileSize(void *pBackendData)
[32370]	1769	{
[32536]	1770	LogFlowFunc(("pBackendData=%#p\n", pBackendData));
[33481]	1771	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1772	uint64_t cb = 0;
	1773
[33481]	1774	AssertPtr(pCache);
[32370]	1775
[33481]	1776	if (pCache)
[32370]	1777	{
	1778	uint64_t cbFile;
[33481]	1779	if (pCache->pStorage)
[32370]	1780	{
[38469]	1781	int rc = vdIfIoIntFileGetSize(pCache->pIfIo, pCache->pStorage, &cbFile);
[32370]	1782	if (RT_SUCCESS(rc))
[32536]	1783	cb = cbFile;
[32370]	1784	}
	1785	}
	1786
	1787	LogFlowFunc(("returns %lld\n", cb));
	1788	return cb;
	1789	}
	1790
	1791	/** @copydoc VDCACHEBACKEND::pfnGetImageFlags */
[57388]	1792	static DECLCALLBACK(unsigned) vciGetImageFlags(void *pBackendData)
[32370]	1793	{
[32536]	1794	LogFlowFunc(("pBackendData=%#p\n", pBackendData));
[33481]	1795	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1796	unsigned uImageFlags;
	1797
[33481]	1798	AssertPtr(pCache);
[32370]	1799
[33481]	1800	if (pCache)
	1801	uImageFlags = pCache->uImageFlags;
[32370]	1802	else
	1803	uImageFlags = 0;
	1804
	1805	LogFlowFunc(("returns %#x\n", uImageFlags));
	1806	return uImageFlags;
	1807	}
	1808
	1809	/** @copydoc VDCACHEBACKEND::pfnGetOpenFlags */
[57388]	1810	static DECLCALLBACK(unsigned) vciGetOpenFlags(void *pBackendData)
[32370]	1811	{
[32536]	1812	LogFlowFunc(("pBackendData=%#p\n", pBackendData));
[33481]	1813	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1814	unsigned uOpenFlags;
	1815
[33481]	1816	AssertPtr(pCache);
[32370]	1817
[33481]	1818	if (pCache)
	1819	uOpenFlags = pCache->uOpenFlags;
[32370]	1820	else
	1821	uOpenFlags = 0;
	1822
	1823	LogFlowFunc(("returns %#x\n", uOpenFlags));
	1824	return uOpenFlags;
	1825	}
	1826
	1827	/** @copydoc VDCACHEBACKEND::pfnSetOpenFlags */
[57388]	1828	static DECLCALLBACK(int) vciSetOpenFlags(void *pBackendData, unsigned uOpenFlags)
[32370]	1829	{
[32536]	1830	LogFlowFunc(("pBackendData=%#p\n uOpenFlags=%#x", pBackendData, uOpenFlags));
[33481]	1831	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1832	int rc;
	1833
	1834	/* Image must be opened and the new flags must be valid. Just readonly and
	1835	* info flags are supported. */
[33481]	1836	if (!pCache \|\| (uOpenFlags & ~(VD_OPEN_FLAGS_READONLY \| VD_OPEN_FLAGS_INFO)))
[32370]	1837	{
	1838	rc = VERR_INVALID_PARAMETER;
	1839	goto out;
	1840	}
	1841
	1842	/* Implement this operation via reopening the image. */
[33481]	1843	rc = vciFreeImage(pCache, false);
[32536]	1844	if (RT_FAILURE(rc))
	1845	goto out;
[33481]	1846	rc = vciOpenImage(pCache, uOpenFlags);
[32370]	1847
	1848	out:
	1849	LogFlowFunc(("returns %Rrc\n", rc));
	1850	return rc;
	1851	}
	1852
	1853	/** @copydoc VDCACHEBACKEND::pfnGetComment */
[57388]	1854	static DECLCALLBACK(int) vciGetComment(void pBackendData, char pszComment,
	1855	size_t cbComment)
[32370]	1856	{
[62737]	1857	RT_NOREF2(pszComment, cbComment);
[32536]	1858	LogFlowFunc(("pBackendData=%#p pszComment=%#p cbComment=%zu\n", pBackendData, pszComment, cbComment));
[33481]	1859	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1860	int rc;
	1861
[33481]	1862	AssertPtr(pCache);
[32370]	1863
[33481]	1864	if (pCache)
[32536]	1865	rc = VERR_NOT_SUPPORTED;
[32370]	1866	else
	1867	rc = VERR_VD_NOT_OPENED;
	1868
	1869	LogFlowFunc(("returns %Rrc comment='%s'\n", rc, pszComment));
	1870	return rc;
	1871	}
	1872
	1873	/** @copydoc VDCACHEBACKEND::pfnSetComment */
[57388]	1874	static DECLCALLBACK(int) vciSetComment(void pBackendData, const char pszComment)
[32370]	1875	{
[62737]	1876	RT_NOREF1(pszComment);
[32536]	1877	LogFlowFunc(("pBackendData=%#p pszComment=\"%s\"\n", pBackendData, pszComment));
[33481]	1878	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1879	int rc;
	1880
[33481]	1881	AssertPtr(pCache);
[32370]	1882
[33524]	1883	if (pCache)
[32370]	1884	{
[33524]	1885	if (pCache->uOpenFlags & VD_OPEN_FLAGS_READONLY)
	1886	rc = VERR_VD_IMAGE_READ_ONLY;
	1887	else
	1888	rc = VERR_NOT_SUPPORTED;
[32370]	1889	}
	1890	else
	1891	rc = VERR_VD_NOT_OPENED;
	1892
	1893	LogFlowFunc(("returns %Rrc\n", rc));
	1894	return rc;
	1895	}
	1896
	1897	/** @copydoc VDCACHEBACKEND::pfnGetUuid */
[57388]	1898	static DECLCALLBACK(int) vciGetUuid(void *pBackendData, PRTUUID pUuid)
[32370]	1899	{
[62737]	1900	RT_NOREF1(pUuid);
[32536]	1901	LogFlowFunc(("pBackendData=%#p pUuid=%#p\n", pBackendData, pUuid));
[33481]	1902	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1903	int rc;
	1904
[33481]	1905	AssertPtr(pCache);
[32370]	1906
[33481]	1907	if (pCache)
[32370]	1908	rc = VERR_NOT_SUPPORTED;
	1909	else
	1910	rc = VERR_VD_NOT_OPENED;
	1911
	1912	LogFlowFunc(("returns %Rrc (%RTuuid)\n", rc, pUuid));
	1913	return rc;
	1914	}
	1915
	1916	/** @copydoc VDCACHEBACKEND::pfnSetUuid */
[57388]	1917	static DECLCALLBACK(int) vciSetUuid(void *pBackendData, PCRTUUID pUuid)
[32370]	1918	{
[62737]	1919	RT_NOREF1(pUuid);
[32536]	1920	LogFlowFunc(("pBackendData=%#p Uuid=%RTuuid\n", pBackendData, pUuid));
[33481]	1921	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1922	int rc;
	1923
	1924	LogFlowFunc(("%RTuuid\n", pUuid));
[33481]	1925	AssertPtr(pCache);
[32370]	1926
[33481]	1927	if (pCache)
[32370]	1928	{
[33481]	1929	if (!(pCache->uOpenFlags & VD_OPEN_FLAGS_READONLY))
[32370]	1930	rc = VERR_NOT_SUPPORTED;
	1931	else
	1932	rc = VERR_VD_IMAGE_READ_ONLY;
	1933	}
	1934	else
	1935	rc = VERR_VD_NOT_OPENED;
	1936
	1937	LogFlowFunc(("returns %Rrc\n", rc));
	1938	return rc;
	1939	}
	1940
	1941	/** @copydoc VDCACHEBACKEND::pfnGetModificationUuid */
[57388]	1942	static DECLCALLBACK(int) vciGetModificationUuid(void *pBackendData, PRTUUID pUuid)
[32370]	1943	{
[62737]	1944	RT_NOREF1(pUuid);
[32536]	1945	LogFlowFunc(("pBackendData=%#p pUuid=%#p\n", pBackendData, pUuid));
[33481]	1946	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1947	int rc;
	1948
[33481]	1949	AssertPtr(pCache);
[32370]	1950
[33481]	1951	if (pCache)
[32370]	1952	rc = VERR_NOT_SUPPORTED;
	1953	else
	1954	rc = VERR_VD_NOT_OPENED;
	1955
	1956	LogFlowFunc(("returns %Rrc (%RTuuid)\n", rc, pUuid));
	1957	return rc;
	1958	}
	1959
	1960	/** @copydoc VDCACHEBACKEND::pfnSetModificationUuid */
[57388]	1961	static DECLCALLBACK(int) vciSetModificationUuid(void *pBackendData, PCRTUUID pUuid)
[32370]	1962	{
[62737]	1963	RT_NOREF1(pUuid);
[32536]	1964	LogFlowFunc(("pBackendData=%#p Uuid=%RTuuid\n", pBackendData, pUuid));
[33481]	1965	PVCICACHE pCache = (PVCICACHE)pBackendData;
[32370]	1966	int rc;
	1967
[33481]	1968	AssertPtr(pCache);
[32370]	1969
[33481]	1970	if (pCache)
[32370]	1971	{
[33481]	1972	if (!(pCache->uOpenFlags & VD_OPEN_FLAGS_READONLY))
[32370]	1973	rc = VERR_NOT_SUPPORTED;
	1974	else
	1975	rc = VERR_VD_IMAGE_READ_ONLY;
	1976	}
	1977	else
	1978	rc = VERR_VD_NOT_OPENED;
	1979
	1980	LogFlowFunc(("returns %Rrc\n", rc));
	1981	return rc;
	1982	}
	1983
	1984	/** @copydoc VDCACHEBACKEND::pfnDump */
[57388]	1985	static DECLCALLBACK(void) vciDump(void *pBackendData)
[32370]	1986	{
[32536]	1987	NOREF(pBackendData);
[32370]	1988	}
	1989
	1990
[50988]	1991	const VDCACHEBACKEND g_VciCacheBackend =
[32370]	1992	{
[63905]	1993	/* u32Version */
	1994	VD_CACHEBACKEND_VERSION,
[32370]	1995	/* pszBackendName */
	1996	"vci",
	1997	/* uBackendCaps */
[33481]	1998	VD_CAP_CREATE_FIXED \| VD_CAP_CREATE_DYNAMIC \| VD_CAP_FILE \| VD_CAP_VFS,
[32370]	1999	/* papszFileExtensions */
	2000	s_apszVciFileExtensions,
	2001	/* paConfigInfo */
	2002	NULL,
	2003	/* pfnProbe */
	2004	vciProbe,
	2005	/* pfnOpen */
	2006	vciOpen,
	2007	/* pfnCreate */
	2008	vciCreate,
	2009	/* pfnClose */
	2010	vciClose,
	2011	/* pfnRead */
	2012	vciRead,
	2013	/* pfnWrite */
	2014	vciWrite,
	2015	/* pfnFlush */
	2016	vciFlush,
[44412]	2017	/* pfnDiscard */
	2018	NULL,
[32370]	2019	/* pfnGetVersion */
	2020	vciGetVersion,
	2021	/* pfnGetSize */
	2022	vciGetSize,
	2023	/* pfnGetFileSize */
	2024	vciGetFileSize,
	2025	/* pfnGetImageFlags */
	2026	vciGetImageFlags,
	2027	/* pfnGetOpenFlags */
	2028	vciGetOpenFlags,
	2029	/* pfnSetOpenFlags */
	2030	vciSetOpenFlags,
	2031	/* pfnGetComment */
	2032	vciGetComment,
	2033	/* pfnSetComment */
	2034	vciSetComment,
	2035	/* pfnGetUuid */
	2036	vciGetUuid,
	2037	/* pfnSetUuid */
	2038	vciSetUuid,
	2039	/* pfnGetModificationUuid */
	2040	vciGetModificationUuid,
	2041	/* pfnSetModificationUuid */
	2042	vciSetModificationUuid,
	2043	/* pfnDump */
	2044	vciDump,
	2045	/* pfnComposeLocation */
	2046	NULL,
	2047	/* pfnComposeName */
[63905]	2048	NULL,
	2049	/* u32VersionEnd */
	2050	VD_CACHEBACKEND_VERSION
[32370]	2051	};
	2052

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/Storage/VCICache.cpp@ 99739

Download in other formats: