Index: trunk/src/VBox/Devices/Storage/ParallelsHDDCore.cpp
===================================================================
--- trunk/src/VBox/Devices/Storage/ParallelsHDDCore.cpp	(revision 30862)
+++ trunk/src/VBox/Devices/Storage/ParallelsHDDCore.cpp	(revision 30863)
@@ -567,7 +567,7 @@
     else
     {
-        /** Calculate offset in the real file. */
+        /* Calculate offset in the real file. */
         uSector = uOffset / 512;
-        /** One chunk in the file is always one track big. */
+        /* One chunk in the file is always one track big. */
         iIndexInAllocationTable = (uint32_t)(uSector / pImage->PCHSGeometry.cSectors);
         uSector = uSector % pImage->PCHSGeometry.cSectors;
Index: trunk/src/VBox/Devices/Storage/VBoxHDD.cpp
===================================================================
--- trunk/src/VBox/Devices/Storage/VBoxHDD.cpp	(revision 30862)
+++ trunk/src/VBox/Devices/Storage/VBoxHDD.cpp	(revision 30863)
@@ -711,4 +711,5 @@
     }
 
+    LogFlow(("Allocated root I/O context %#p\n", pIoCtx));
     return pIoCtx;
 }
@@ -736,4 +737,5 @@
     }
 
+    LogFlow(("Allocated child I/O context %#p\n", pIoCtx));
     return pIoCtx;
 }
@@ -776,6 +778,10 @@
 DECLINLINE(void) vdIoCtxFree(PVBOXHDD pDisk, PVDIOCTX pIoCtx)
 {
+    LogFlow(("Freeing I/O context %#p\n", pIoCtx));
     if (pIoCtx->pvAllocation)
         RTMemFree(pIoCtx->pvAllocation);
+#ifdef DEBUG
+    memset(pIoCtx, 0xff, sizeof(VDIOCTX));
+#endif
     RTMemCacheFree(pDisk->hMemCacheIoCtx, pIoCtx);
 }
@@ -845,9 +851,14 @@
     LogFlowFunc(("pIoCtx=%#p\n", pIoCtx));
 
+    RTCritSectEnter(&pDisk->CritSect);
+
     if (   !pIoCtx->cbTransferLeft
         && !pIoCtx->cMetaTransfersPending
         && !pIoCtx->cDataTransfersPending
         && !pIoCtx->pfnIoCtxTransfer)
-        return VINF_VD_ASYNC_IO_FINISHED;
+    {
+        rc = VINF_VD_ASYNC_IO_FINISHED;
+        goto out;
+    }
 
     /*
@@ -858,14 +869,20 @@
         && !pIoCtx->cMetaTransfersPending
         && !pIoCtx->cDataTransfersPending)
-        return VINF_VD_ASYNC_IO_FINISHED;
-
-    /* Don't change anything if there is a metadata transfer pending. */
-    if (pIoCtx->cMetaTransfersPending)
-        return VERR_VD_ASYNC_IO_IN_PROGRESS;
+    {
+        rc = VINF_VD_ASYNC_IO_FINISHED;
+        goto out;
+    }
+
+    /* Don't change anything if there is a metadata transfer pending or we are blocked. */
+    if (   pIoCtx->cMetaTransfersPending
+        || pIoCtx->fBlocked)
+    {
+        rc = VERR_VD_ASYNC_IO_IN_PROGRESS;
+        goto out;
+    }
 
     if (pIoCtx->pfnIoCtxTransfer)
     {
         /* Call the transfer function advancing to the next while there is no error. */
-        RTCritSectEnter(&pDisk->CritSect);
         while (   pIoCtx->pfnIoCtxTransfer
                && RT_SUCCESS(rc))
@@ -881,5 +898,4 @@
             }
         }
-        RTCritSectLeave(&pDisk->CritSect);
     }
 
@@ -904,4 +920,7 @@
             rc = VERR_VD_ASYNC_IO_IN_PROGRESS;
     }
+
+out:
+    RTCritSectLeave(&pDisk->CritSect);
 
     LogFlowFunc(("pIoCtx=%#p rc=%Rrc cbTransferLeft=%u cMetaTransfersPending=%u fComplete=%RTbool\n",
@@ -1554,4 +1573,6 @@
                 LogFlowFunc(("Deferring write pIoCtx=%#p\n", pIoCtx));
 
+                Assert(!pIoCtx->pIoCtxParent && !pIoCtx->fBlocked);
+
                 RTListInit(&pDeferred->NodeDeferred);
                 pDeferred->pIoCtx = pIoCtx;
@@ -1618,5 +1639,12 @@
                 }
                 else
+                {
                     LogFlow(("Child write pending\n"));
+                    pIoCtx->fBlocked = true;
+                    rc = VERR_VD_ASYNC_IO_IN_PROGRESS;
+                    cbWrite -= cbThisWrite;
+                    uOffset += cbThisWrite;
+                    break;
+                }
             }
         }
@@ -1943,4 +1971,5 @@
                 Assert(!pIoCtxParent->pIoCtxParent);
                 Assert(pIoCtx->enmTxDir == VDIOCTXTXDIR_WRITE);
+                Assert(pIoCtxParent->cbTransferLeft >= pIoCtx->Type.Child.cbTransferParent);
                 ASMAtomicSubU32(&pIoCtxParent->cbTransferLeft, pIoCtx->Type.Child.cbTransferParent);
 
@@ -1949,9 +1978,12 @@
 
                 /*
-                 * A completed child write means that we finsihed growing the image.
+                 * A completed child write means that we finished growing the image.
                  * We have to process any pending writes now.
                  */
                 Assert(pDisk->fGrowing);
                 ASMAtomicWriteBool(&pDisk->fGrowing, false);
+
+                /* Unblock the parent */
+                pIoCtxParent->fBlocked = false;
 
                 rc = vdIoCtxProcess(pIoCtxParent);
@@ -1968,8 +2000,8 @@
                 }
 
-                /* Process any pending writes. */
+                /* Process any pending writes if the current request didn't caused another growing. */
                 RTCritSectEnter(&pDisk->CritSect);
 
-                if (!RTListIsEmpty(&pDisk->ListWriteGrowing))
+                if (!RTListIsEmpty(&pDisk->ListWriteGrowing) && !pDisk->fGrowing)
                 {
                     RTLISTNODE ListTmp;
@@ -1996,8 +2028,7 @@
                         RTMemFree(pDeferred);
 
+                        Assert(!pIoCtxWait->pIoCtxParent);
+
                         pIoCtxWait->fBlocked = false;
-
-                        Assert(!pIoCtxWait->pIoCtxParent);
-
                         LogFlowFunc(("Processing waiting I/O context pIoCtxWait=%#p\n", pIoCtxWait));
 
@@ -2052,9 +2083,14 @@
                  pIoStorage, pIoCtx, pfnComplete, pvUser, cbTransfer, rcReq));
 
+    Assert(pIoCtx->cbTransferLeft >= cbTransfer);
     ASMAtomicSubU32(&pIoCtx->cbTransferLeft, cbTransfer);
     ASMAtomicDecU32(&pIoCtx->cDataTransfersPending);
 
     if (pfnComplete)
+    {
+        RTCritSectEnter(&pDisk->CritSect);
         rc = pfnComplete(pIoStorage->pImage->pvBackendData, pIoCtx, pvUser, rcReq);
+        RTCritSectLeave(&pDisk->CritSect);
+    }
 
     if (RT_SUCCESS(rc))
@@ -2074,15 +2110,15 @@
     PVBOXHDD pDisk = pIoStorage->pImage->pDisk;
     RTLISTNODE ListIoCtxWaiting;
-    bool fFlush = VDMETAXFER_TXDIR_GET(pMetaXfer->fFlags) == VDMETAXFER_TXDIR_FLUSH;
+    bool fFlush;
 
     LogFlowFunc(("pIoStorage=%#p pfnComplete=%#p pvUser=%#p pMetaXfer=%#p rcReq=%Rrc\n",
                  pIoStorage, pfnComplete, pvUser, pMetaXfer, rcReq));
 
+    RTCritSectEnter(&pDisk->CritSect);
+    fFlush = VDMETAXFER_TXDIR_GET(pMetaXfer->fFlags) == VDMETAXFER_TXDIR_FLUSH;
     VDMETAXFER_TXDIR_SET(pMetaXfer->fFlags, VDMETAXFER_TXDIR_NONE);
 
     if (!fFlush)
     {
-        RTCritSectEnter(&pDisk->CritSect);
-
         RTListMove(&ListIoCtxWaiting, &pMetaXfer->ListIoCtxWaiting);
 
@@ -2090,4 +2126,5 @@
         {
             /* Remove from the AVL tree. */
+            LogFlow(("Removing meta xfer=%#p\n", pMetaXfer));
             bool fRemoved = RTAvlrFileOffsetRemove(pIoStorage->pTreeMetaXfers, pMetaXfer->Core.Key);
             Assert(fRemoved);
@@ -2099,15 +2136,8 @@
             pMetaXfer->cRefs++;
         }
-
-        RTCritSectLeave(&pDisk->CritSect);
     }
     else
-    {
-        /*
-         *  Flushes don't need the critical section because they are never accessed concurrently
-         * (they also have only one context attached).
-         */
         RTListMove(&ListIoCtxWaiting, &pMetaXfer->ListIoCtxWaiting);
-    }
+    RTCritSectLeave(&pDisk->CritSect);
 
     /* Go through the waiting list and continue the I/O contexts. */
@@ -2124,5 +2154,9 @@
 
         if (pfnComplete)
+        {
+            RTCritSectEnter(&pDisk->CritSect);
             rc = pfnComplete(pIoStorage->pImage->pvBackendData, pIoCtx, pvUser, rcReq);
+            RTCritSectLeave(&pDisk->CritSect);
+        }
 
         LogFlow(("Completion callback for I/O context %#p returned %Rrc\n", pIoCtx, rc));
@@ -2142,7 +2176,8 @@
         RTCritSectEnter(&pDisk->CritSect);
         pMetaXfer->cRefs--;
-        if (!pMetaXfer->cRefs)
+        if (!pMetaXfer->cRefs && RTListIsEmpty(&pMetaXfer->ListIoCtxWaiting))
         {
             /* Remove from the AVL tree. */
+            LogFlow(("Removing meta xfer=%#p\n", pMetaXfer));
             bool fRemoved = RTAvlrFileOffsetRemove(pIoStorage->pTreeMetaXfers, pMetaXfer->Core.Key);
             Assert(fRemoved);
@@ -2430,5 +2465,7 @@
                              uint64_t uOffset, void *pvBuf,
                              size_t cbRead, PVDIOCTX pIoCtx,
-                             PPVDMETAXFER ppMetaXfer)
+                             PPVDMETAXFER ppMetaXfer,
+                             PFNVDXFERCOMPLETED pfnComplete,
+                             void *pvCompleteUser)
 {
     PVDIMAGE pImage = (PVDIMAGE)pvUser;
@@ -2448,4 +2485,10 @@
     if (!pMetaXfer)
     {
+#ifdef RT_STRICT
+        pMetaXfer = (PVDMETAXFER)RTAvlrFileOffsetGetBestFit(pIoStorage->pTreeMetaXfers, uOffset, false /* fAbove */);
+        AssertMsg(!pMetaXfer || (pMetaXfer->Core.Key + pMetaXfer->cbMeta <= uOffset),
+                  ("Overlapping meta transfers!\n"));
+#endif
+
         /* Allocate a new meta transfer. */
         pMetaXfer = vdMetaXferAlloc(pImage, pIoStorage, uOffset, cbRead);
@@ -2453,5 +2496,5 @@
             return VERR_NO_MEMORY;
 
-        pIoTask = vdIoTaskMetaAlloc(pIoStorage, NULL, NULL, pMetaXfer);
+        pIoTask = vdIoTaskMetaAlloc(pIoStorage, pfnComplete, pvCompleteUser, pMetaXfer);
         if (!pIoTask)
         {
@@ -2469,4 +2512,13 @@
                                                              cbRead, pIoTask,
                                                              &pvTask);
+
+        if (RT_SUCCESS(rc) || rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+        {
+            bool fInserted = RTAvlrFileOffsetInsert(pIoStorage->pTreeMetaXfers, &pMetaXfer->Core);
+            Assert(fInserted);
+        }
+        else
+            RTMemFree(pMetaXfer);
+
         if (RT_SUCCESS(rc))
         {
@@ -2474,19 +2526,11 @@
             vdIoTaskFree(pDisk, pIoTask);
         }
-        else if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+        else if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS && !pfnComplete)
             rc = VERR_VD_NOT_ENOUGH_METADATA;
-
-        if (RT_SUCCESS(rc) || rc == VERR_VD_NOT_ENOUGH_METADATA)
-        {
-            bool fInserted = RTAvlrFileOffsetInsert(pIoStorage->pTreeMetaXfers, &pMetaXfer->Core);
-            Assert(fInserted);
-        }
-        else
-            RTMemFree(pMetaXfer);
     }
 
     Assert(VALID_PTR(pMetaXfer) || RT_FAILURE(rc));
 
-    if (RT_SUCCESS(rc) || rc == VERR_VD_NOT_ENOUGH_METADATA)
+    if (RT_SUCCESS(rc) || rc == VERR_VD_NOT_ENOUGH_METADATA || rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
     {
         /* If it is pending add the request to the list. */
@@ -2508,4 +2552,5 @@
             pMetaXfer->cRefs++;
             Assert(pMetaXfer->cbMeta >= cbRead);
+            Assert(pMetaXfer->Core.Key == (RTFOFF)uOffset);
             memcpy(pvBuf, pMetaXfer->abData, cbRead);
             *ppMetaXfer = pMetaXfer;
@@ -2528,4 +2573,5 @@
     PVDIOTASK pIoTask;
     PVDMETAXFER pMetaXfer = NULL;
+    bool fInTree = false;
     void *pvTask = NULL;
 
@@ -2542,53 +2588,68 @@
         if (!pMetaXfer)
             return VERR_NO_MEMORY;
-
-        pIoTask = vdIoTaskMetaAlloc(pIoStorage, pfnComplete, pvCompleteUser, pMetaXfer);
-        if (!pIoTask)
-        {
-            RTMemFree(pMetaXfer);
-            return VERR_NO_MEMORY;
-        }
-
-        memcpy(pMetaXfer->abData, pvBuf, cbWrite);
-        Seg.cbSeg = cbWrite;
-        Seg.pvSeg = pMetaXfer->abData;
-
-        ASMAtomicIncU32(&pIoCtx->cMetaTransfersPending);
-
-        VDMETAXFER_TXDIR_SET(pMetaXfer->fFlags, VDMETAXFER_TXDIR_WRITE);
-        rc = pDisk->pInterfaceAsyncIOCallbacks->pfnWriteAsync(pDisk->pInterfaceAsyncIO->pvUser,
-                                                              pIoStorage->u.pStorage,
-                                                              uOffset, &Seg, 1,
-                                                              cbWrite, pIoTask,
-                                                              &pvTask);
-        if (RT_SUCCESS(rc))
-        {
-            VDMETAXFER_TXDIR_SET(pMetaXfer->fFlags, VDMETAXFER_TXDIR_NONE);
-            ASMAtomicDecU32(&pIoCtx->cMetaTransfersPending);
-            vdIoTaskFree(pDisk, pIoTask);
+    }
+    else
+    {
+        Assert(pMetaXfer->cbMeta >= cbWrite);
+        Assert(pMetaXfer->Core.Key == (RTFOFF)uOffset);
+        fInTree = true;
+    }
+
+    Assert(VDMETAXFER_TXDIR_GET(pMetaXfer->fFlags) == VDMETAXFER_TXDIR_NONE);
+
+    pIoTask = vdIoTaskMetaAlloc(pIoStorage, pfnComplete, pvCompleteUser, pMetaXfer);
+    if (!pIoTask)
+    {
+        RTMemFree(pMetaXfer);
+        return VERR_NO_MEMORY;
+    }
+
+    memcpy(pMetaXfer->abData, pvBuf, cbWrite);
+    Seg.cbSeg = cbWrite;
+    Seg.pvSeg = pMetaXfer->abData;
+
+    ASMAtomicIncU32(&pIoCtx->cMetaTransfersPending);
+
+    VDMETAXFER_TXDIR_SET(pMetaXfer->fFlags, VDMETAXFER_TXDIR_WRITE);
+    rc = pDisk->pInterfaceAsyncIOCallbacks->pfnWriteAsync(pDisk->pInterfaceAsyncIO->pvUser,
+                                                          pIoStorage->u.pStorage,
+                                                          uOffset, &Seg, 1,
+                                                          cbWrite, pIoTask,
+                                                          &pvTask);
+    if (RT_SUCCESS(rc))
+    {
+        VDMETAXFER_TXDIR_SET(pMetaXfer->fFlags, VDMETAXFER_TXDIR_NONE);
+        ASMAtomicDecU32(&pIoCtx->cMetaTransfersPending);
+        vdIoTaskFree(pDisk, pIoTask);
+        if (fInTree && !pMetaXfer->cRefs)
+        {
+            LogFlow(("Removing meta xfer=%#p\n", pMetaXfer));
+            bool fRemoved = RTAvlrFileOffsetRemove(pIoStorage->pTreeMetaXfers, pMetaXfer->Core.Key);
+            AssertMsg(fRemoved, ("Metadata transfer wasn't removed\n"));
             RTMemFree(pMetaXfer);
             pMetaXfer = NULL;
         }
-        else if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
-        {
-            PVDIOCTXDEFERRED pDeferred = (PVDIOCTXDEFERRED)RTMemAllocZ(sizeof(VDIOCTXDEFERRED));
-            AssertPtr(pDeferred);
-
-            RTListInit(&pDeferred->NodeDeferred);
-            pDeferred->pIoCtx = pIoCtx;
-
+    }
+    else if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+    {
+        PVDIOCTXDEFERRED pDeferred = (PVDIOCTXDEFERRED)RTMemAllocZ(sizeof(VDIOCTXDEFERRED));
+        AssertPtr(pDeferred);
+
+        RTListInit(&pDeferred->NodeDeferred);
+        pDeferred->pIoCtx = pIoCtx;
+
+        if (!fInTree)
+        {
             bool fInserted = RTAvlrFileOffsetInsert(pIoStorage->pTreeMetaXfers, &pMetaXfer->Core);
             Assert(fInserted);
-
-            RTListAppend(&pMetaXfer->ListIoCtxWaiting, &pDeferred->NodeDeferred);
-        }
-        else
-        {
-            RTMemFree(pMetaXfer);
-            pMetaXfer = NULL;
-        }
-    }
-
-    Assert(VALID_PTR(pMetaXfer) || RT_SUCCESS(rc) || rc != VERR_VD_ASYNC_IO_IN_PROGRESS);
+        }
+
+        RTListAppend(&pMetaXfer->ListIoCtxWaiting, &pDeferred->NodeDeferred);
+    }
+    else
+    {
+        RTMemFree(pMetaXfer);
+        pMetaXfer = NULL;
+    }
 
     return rc;
@@ -2612,4 +2673,5 @@
     {
         /* Free the meta data entry. */
+        LogFlow(("Removing meta xfer=%#p\n", pMetaXfer));
         bool fRemoved = RTAvlrFileOffsetRemove(pIoStorage->pTreeMetaXfers, pMetaXfer->Core.Key);
         AssertMsg(fRemoved, ("Metadata transfer wasn't removed\n"));
Index: trunk/src/VBox/Devices/Storage/VDIHDDCore.cpp
===================================================================
--- trunk/src/VBox/Devices/Storage/VDIHDDCore.cpp	(revision 30862)
+++ trunk/src/VBox/Devices/Storage/VDIHDDCore.cpp	(revision 30863)
@@ -220,5 +220,5 @@
                                                            pImage->pStorage,
                                                            off, pvBuf, cbRead, pIoCtx,
-                                                           NULL);
+                                                           NULL, NULL, NULL);
 }
 
Index: trunk/src/VBox/Devices/Storage/VHDHDDCore.cpp
===================================================================
--- trunk/src/VBox/Devices/Storage/VHDHDDCore.cpp	(revision 30862)
+++ trunk/src/VBox/Devices/Storage/VHDHDDCore.cpp	(revision 30863)
@@ -2328,5 +2328,6 @@
                                                              pImage->pStorage,
                                                              ((uint64_t)pImage->pBlockAllocationTable[cBlockAllocationTableEntry]) * VHD_SECTOR_SIZE,
-                                                             pImage->pu8Bitmap, pImage->cbDataBlockBitmap, pIoCtx, &pMetaXfer);
+                                                             pImage->pu8Bitmap, pImage->cbDataBlockBitmap, pIoCtx, &pMetaXfer,
+                                                             NULL, NULL);
 
         if (RT_SUCCESS(rc))
@@ -2575,5 +2576,6 @@
                                                                  pImage->pStorage,
                                                                  ((uint64_t)pImage->pBlockAllocationTable[cBlockAllocationTableEntry]) * VHD_SECTOR_SIZE,
-                                                                 pImage->pu8Bitmap, pImage->cbDataBlockBitmap, pIoCtx, &pMetaXfer);
+                                                                 pImage->pu8Bitmap, pImage->cbDataBlockBitmap, pIoCtx, &pMetaXfer,
+                                                                 NULL, NULL);
             if (RT_SUCCESS(rc))
             {
Index: trunk/src/VBox/Devices/Storage/VmdkHDDCore.cpp
===================================================================
--- trunk/src/VBox/Devices/Storage/VmdkHDDCore.cpp	(revision 30862)
+++ trunk/src/VBox/Devices/Storage/VmdkHDDCore.cpp	(revision 30863)
@@ -495,4 +495,28 @@
 } VMDKDEFLATESTATE;
 
+/** Tracks async grain allocation. */
+typedef struct VMDKGRAINALLOCASYNC
+{
+    /** Old size of the extent. Used for rollback after an error. */
+    uint64_t    cbExtentOld;
+    /** Flag whether the allocation failed. */
+    bool        fIoErr;
+    /** Current number of transfers pending.
+     * If reached 0 and there is an error the old state is restored. */
+    unsigned    cIoXfersPending;
+    /** Sector number */
+    uint64_t    uSector;
+    /** Flag whether the grain table needs to be updated. */
+    bool        fGTUpdateNeeded;
+    /** Extent the allocation happens. */
+    PVMDKEXTENT pExtent;
+    /** New size of the extent, required for the grain table update. */
+    uint64_t    cbExtentSize;
+    /** Grain table sector. */
+    uint64_t    uGTSector;
+    /** Backup grain table sector. */
+    uint64_t    uRGTSector;
+} VMDKGRAINALLOCASYNC, *PVMDKGRAINALLOCASYNC;
+
 /*******************************************************************************
  *   Static Variables                                                           *
@@ -520,4 +544,5 @@
 static void vmdkFreeImage(PVMDKIMAGE pImage, bool fDelete);
 
+static int vmdkAllocGrainAsyncComplete(void *pvBackendData, PVDIOCTX pIoCtx, void *pvUser, int rcReq);
 
 /**
@@ -2896,4 +2921,68 @@
 }
 
+/**
+ * Internal: write/update the metadata for a sparse extent - async version.
+ */
+static int vmdkWriteMetaSparseExtentAsync(PVMDKIMAGE pImage, PVMDKEXTENT pExtent,
+                                          uint64_t uOffset, PVDIOCTX pIoCtx)
+{
+    SparseExtentHeader Header;
+
+    memset(&Header, '\0', sizeof(Header));
+    Header.magicNumber = RT_H2LE_U32(VMDK_SPARSE_MAGICNUMBER);
+    Header.version = RT_H2LE_U32(pExtent->uVersion);
+    Header.flags = RT_H2LE_U32(RT_BIT(0));
+    if (pExtent->pRGD)
+        Header.flags |= RT_H2LE_U32(RT_BIT(1));
+    if (pExtent->pImage->uImageFlags & VD_VMDK_IMAGE_FLAGS_STREAM_OPTIMIZED)
+        Header.flags |= RT_H2LE_U32(RT_BIT(16) | RT_BIT(17));
+    Header.capacity = RT_H2LE_U64(pExtent->cSectors);
+    Header.grainSize = RT_H2LE_U64(pExtent->cSectorsPerGrain);
+    Header.descriptorOffset = RT_H2LE_U64(pExtent->uDescriptorSector);
+    Header.descriptorSize = RT_H2LE_U64(pExtent->cDescriptorSectors);
+    Header.numGTEsPerGT = RT_H2LE_U32(pExtent->cGTEntries);
+    if (pExtent->fFooter && uOffset == 0)
+    {
+        if (pExtent->pRGD)
+        {
+            Assert(pExtent->uSectorRGD);
+            Header.rgdOffset = RT_H2LE_U64(VMDK_GD_AT_END);
+            Header.gdOffset = RT_H2LE_U64(VMDK_GD_AT_END);
+        }
+        else
+        {
+            Header.gdOffset = RT_H2LE_U64(VMDK_GD_AT_END);
+        }
+    }
+    else
+    {
+        if (pExtent->pRGD)
+        {
+            Assert(pExtent->uSectorRGD);
+            Header.rgdOffset = RT_H2LE_U64(pExtent->uSectorRGD);
+            Header.gdOffset = RT_H2LE_U64(pExtent->uSectorGD);
+        }
+        else
+        {
+            Header.gdOffset = RT_H2LE_U64(pExtent->uSectorGD);
+        }
+    }
+    Header.overHead = RT_H2LE_U64(pExtent->cOverheadSectors);
+    Header.uncleanShutdown = pExtent->fUncleanShutdown;
+    Header.singleEndLineChar = '\n';
+    Header.nonEndLineChar = ' ';
+    Header.doubleEndLineChar1 = '\r';
+    Header.doubleEndLineChar2 = '\n';
+    Header.compressAlgorithm = RT_H2LE_U16(pExtent->uCompression);
+
+    int rc = pImage->pInterfaceIOCallbacks->pfnWriteMetaAsync(pImage->pInterfaceIO->pvUser,
+                                                              pExtent->pFile->pStorage,
+                                                              uOffset, &Header, sizeof(Header),
+                                                              pIoCtx, NULL, NULL);
+    if (RT_FAILURE(rc) && (rc != VERR_VD_ASYNC_IO_IN_PROGRESS))
+        rc = vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: error writing extent header in '%s'"), pExtent->pszFullname);
+    return rc;
+}
+
 #ifdef VBOX_WITH_VMDK_ESX
 /**
@@ -4397,4 +4486,6 @@
     }
 
+    LogFlowFunc(("uGTSector=%llu\n", uGTSector));
+
     uGTBlock = uSector / (pExtent->cSectorsPerGrain * VMDK_GT_CACHELINE_SIZE);
     uGTHash = vmdkGTCacheHash(pCache, uGTBlock, pExtent->uExtent);
@@ -4408,5 +4499,5 @@
                                                              pExtent->pFile->pStorage,
                                                              VMDK_SECTOR2BYTE(uGTSector) + (uGTBlock % (pExtent->cGTEntries / VMDK_GT_CACHELINE_SIZE)) * sizeof(aGTDataTmp),
-                                                             aGTDataTmp, sizeof(aGTDataTmp), pIoCtx, &pMetaXfer);
+                                                             aGTDataTmp, sizeof(aGTDataTmp), pIoCtx, &pMetaXfer, NULL, NULL);
         if (RT_FAILURE(rc))
             return rc;
@@ -4696,4 +4787,320 @@
     }
 #endif /* VBOX_WITH_VMDK_ESX */
+    return rc;
+}
+
+/**
+ * Internal: Updates the grain table during a async grain allocation.
+ */
+static int vmdkAllocGrainAsyncGTUpdate(PVMDKIMAGE pImage, PVMDKEXTENT pExtent,
+                                       PVMDKGTCACHE pCache, PVDIOCTX pIoCtx,
+                                       PVMDKGRAINALLOCASYNC pGrainAlloc)
+{
+    int rc = VINF_SUCCESS;
+    uint32_t aGTDataTmp[VMDK_GT_CACHELINE_SIZE];
+    uint32_t uGTHash, uGTBlockIndex;
+    uint64_t uGDIndex, uGTSector, uRGTSector, uGTBlock;
+    uint64_t uSector = pGrainAlloc->uSector;
+    PVMDKGTCACHEENTRY pGTCacheEntry;
+
+    LogFlowFunc(("pImage=%#p pExtent=%#p pCache=%#p pIoCtx=%#p pGrainAlloc=%#p\n",
+                 pImage, pExtent, pCache, pIoCtx, pGrainAlloc));
+
+    uGTSector = pGrainAlloc->uGTSector;
+    uRGTSector = pGrainAlloc->uRGTSector;
+    LogFlow(("uGTSector=%llu uRGTSector=%llu\n", uGTSector, uRGTSector));
+
+    /* Update the grain table (and the cache). */
+    uGTBlock = uSector / (pExtent->cSectorsPerGrain * VMDK_GT_CACHELINE_SIZE);
+    uGTHash = vmdkGTCacheHash(pCache, uGTBlock, pExtent->uExtent);
+    pGTCacheEntry = &pCache->aGTCache[uGTHash];
+    if (    pGTCacheEntry->uExtent != pExtent->uExtent
+        ||  pGTCacheEntry->uGTBlock != uGTBlock)
+    {
+        /* Cache miss, fetch data from disk. */
+        LogFlow(("Cache miss, fetch data from disk\n"));
+        PVDMETAXFER pMetaXfer = NULL;
+        rc = pImage->pInterfaceIOCallbacks->pfnReadMetaAsync(pExtent->pImage->pInterfaceIO->pvUser,
+                                                             pExtent->pFile->pStorage,
+                                                             VMDK_SECTOR2BYTE(uGTSector) + (uGTBlock % (pExtent->cGTEntries / VMDK_GT_CACHELINE_SIZE)) * sizeof(aGTDataTmp),
+                                                             aGTDataTmp, sizeof(aGTDataTmp), pIoCtx,
+                                                             &pMetaXfer,
+                                                             vmdkAllocGrainAsyncComplete, pGrainAlloc);
+        if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+        {
+            pGrainAlloc->cIoXfersPending++;
+            pGrainAlloc->fGTUpdateNeeded = true;
+            /* Leave early, we will be called  again after the read completed. */
+            LogFlowFunc(("Metadata read in progress, leaving\n"));
+            return rc;
+        }
+        else if (RT_FAILURE(rc))
+            return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: cannot read allocated grain table entry in '%s'"), pExtent->pszFullname);
+        pImage->pInterfaceIOCallbacks->pfnMetaXferRelease(pExtent->pImage->pInterfaceIO->pvUser, pMetaXfer);
+        pGTCacheEntry->uExtent = pExtent->uExtent;
+        pGTCacheEntry->uGTBlock = uGTBlock;
+        for (unsigned i = 0; i < VMDK_GT_CACHELINE_SIZE; i++)
+            pGTCacheEntry->aGTData[i] = RT_LE2H_U32(aGTDataTmp[i]);
+    }
+    else
+    {
+        /* Cache hit. Convert grain table block back to disk format, otherwise
+         * the code below will write garbage for all but the updated entry. */
+        for (unsigned i = 0; i < VMDK_GT_CACHELINE_SIZE; i++)
+            aGTDataTmp[i] = RT_H2LE_U32(pGTCacheEntry->aGTData[i]);
+    }
+    pGrainAlloc->fGTUpdateNeeded = false;
+    uGTBlockIndex = (uSector / pExtent->cSectorsPerGrain) % VMDK_GT_CACHELINE_SIZE;
+    aGTDataTmp[uGTBlockIndex] = RT_H2LE_U32(VMDK_BYTE2SECTOR(pGrainAlloc->cbExtentSize));
+    pGTCacheEntry->aGTData[uGTBlockIndex] = VMDK_BYTE2SECTOR(pGrainAlloc->cbExtentSize);
+    /* Update grain table on disk. */
+    rc = pImage->pInterfaceIOCallbacks->pfnWriteMetaAsync(pExtent->pImage->pInterfaceIO->pvUser,
+                                                          pExtent->pFile->pStorage,
+                                                          VMDK_SECTOR2BYTE(uGTSector) + (uGTBlock % (pExtent->cGTEntries / VMDK_GT_CACHELINE_SIZE)) * sizeof(aGTDataTmp),
+                                                          aGTDataTmp, sizeof(aGTDataTmp), pIoCtx,
+                                                          vmdkAllocGrainAsyncComplete, pGrainAlloc);
+    if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+        pGrainAlloc->cIoXfersPending++;
+    else if (RT_FAILURE(rc))
+        return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: cannot write updated grain table in '%s'"), pExtent->pszFullname);
+    if (pExtent->pRGD)
+    {
+        /* Update backup grain table on disk. */
+        rc = pImage->pInterfaceIOCallbacks->pfnWriteMetaAsync(pExtent->pImage->pInterfaceIO->pvUser,
+                                                              pExtent->pFile->pStorage,
+                                                              VMDK_SECTOR2BYTE(uRGTSector) + (uGTBlock % (pExtent->cGTEntries / VMDK_GT_CACHELINE_SIZE)) * sizeof(aGTDataTmp),
+                                                              aGTDataTmp, sizeof(aGTDataTmp), pIoCtx,
+                                                              vmdkAllocGrainAsyncComplete, pGrainAlloc);
+        if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+            pGrainAlloc->cIoXfersPending++;
+        else if (RT_FAILURE(rc))
+            return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: cannot write updated backup grain table in '%s'"), pExtent->pszFullname);
+    }
+#ifdef VBOX_WITH_VMDK_ESX
+    if (RT_SUCCESS(rc) && pExtent->enmType == VMDKETYPE_ESX_SPARSE)
+    {
+        pExtent->uFreeSector = uGTSector + VMDK_BYTE2SECTOR(cbWrite);
+        pExtent->fMetaDirty = true;
+    }
+#endif /* VBOX_WITH_VMDK_ESX */
+
+    LogFlowFunc(("leaving rc=%Rrc\n", rc));
+
+    return rc;
+}
+
+/**
+ * Internal - complete the grain allocation by updating disk grain table if required.
+ */
+static int vmdkAllocGrainAsyncComplete(void *pvBackendData, PVDIOCTX pIoCtx, void *pvUser, int rcReq)
+{
+    int rc = VINF_SUCCESS;
+    PVMDKIMAGE pImage = (PVMDKIMAGE)pvBackendData;
+    PVMDKGRAINALLOCASYNC pGrainAlloc = (PVMDKGRAINALLOCASYNC)pvUser;
+    PVMDKEXTENT pExtent = pGrainAlloc->pExtent;
+
+    LogFlowFunc(("pvBackendData=%#p pIoCtx=%#p pvUser=%#p rcReq=%Rrc\n",
+                 pvBackendData, pIoCtx, pvUser, rcReq));
+
+    pGrainAlloc->cIoXfersPending--;
+    if (!pGrainAlloc->cIoXfersPending && pGrainAlloc->fGTUpdateNeeded)
+        rc = vmdkAllocGrainAsyncGTUpdate(pImage, pGrainAlloc->pExtent, pImage->pGTCache,
+                                         pIoCtx, pGrainAlloc);
+
+    if (!pGrainAlloc->cIoXfersPending)
+    {
+        /* Grain allocation completed. */
+        RTMemFree(pGrainAlloc);
+    }
+
+    LogFlowFunc(("Leaving rc=%Rrc\n", rc));
+    return rc;
+}
+
+/**
+ * Internal. Allocates a new grain table (if necessary) - async version.
+ */
+static int vmdkAllocGrainAsync(PVMDKGTCACHE pCache, PVMDKEXTENT pExtent,
+                               PVDIOCTX pIoCtx, uint64_t uSector,
+                               uint64_t cbWrite)
+{
+    uint64_t uGDIndex, uGTSector, uRGTSector, uGTBlock;
+    uint64_t cbExtentSize;
+    uint32_t aGTDataTmp[VMDK_GT_CACHELINE_SIZE];
+    PVMDKGRAINALLOCASYNC pGrainAlloc = NULL;
+    PVMDKIMAGE pImage = pExtent->pImage;
+    int rc;
+
+    LogFlowFunc(("pCache=%#p pExtent=%#p pIoCtx=%#p uSector=%llu cbWrite=%llu\n",
+                 pCache, pExtent, pIoCtx, uSector, cbWrite));
+
+    AssertReturn(!(pExtent->pImage->uImageFlags & VD_VMDK_IMAGE_FLAGS_STREAM_OPTIMIZED), VERR_NOT_SUPPORTED);
+
+    pGrainAlloc = (PVMDKGRAINALLOCASYNC)RTMemAllocZ(sizeof(VMDKGRAINALLOCASYNC));
+    if (!pGrainAlloc)
+        return VERR_NO_MEMORY;
+
+    pGrainAlloc->pExtent = pExtent;
+    pGrainAlloc->uSector = uSector;
+
+    uGDIndex = uSector / pExtent->cSectorsPerGDE;
+    if (uGDIndex >= pExtent->cGDEntries)
+        return VERR_OUT_OF_RANGE;
+    uGTSector = pExtent->pGD[uGDIndex];
+    if (pExtent->pRGD)
+        uRGTSector = pExtent->pRGD[uGDIndex];
+    else
+        uRGTSector = 0; /**< avoid compiler warning */
+    if (!uGTSector)
+    {
+        LogFlow(("Allocating new grain table\n"));
+
+        /* There is no grain table referenced by this grain directory
+         * entry. So there is absolutely no data in this area. Allocate
+         * a new grain table and put the reference to it in the GDs. */
+        rc = vmdkFileGetSize(pExtent->pFile, &cbExtentSize);
+        if (RT_FAILURE(rc))
+            return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: error getting size in '%s'"), pExtent->pszFullname);
+        Assert(!(cbExtentSize % 512));
+
+        pGrainAlloc->cbExtentOld = cbExtentSize;
+
+        cbExtentSize = RT_ALIGN_64(cbExtentSize, 512);
+        uGTSector = VMDK_BYTE2SECTOR(cbExtentSize);
+
+        /* Normally the grain table is preallocated for hosted sparse extents
+         * that support more than 32 bit sector numbers. So this shouldn't
+         * ever happen on a valid extent. */
+        if (uGTSector > UINT32_MAX)
+            return VERR_VD_VMDK_INVALID_HEADER;
+
+        /* Write grain table by writing the required number of grain table
+         * cache chunks. Allocate memory dynamically here or we flood the
+         * metadata cache with very small entries.
+         */
+        size_t cbGTDataTmp = (pExtent->cGTEntries / VMDK_GT_CACHELINE_SIZE) * VMDK_GT_CACHELINE_SIZE * sizeof(uint32_t);
+        uint32_t *paGTDataTmp = (uint32_t *)RTMemTmpAllocZ(cbGTDataTmp);
+
+        if (!paGTDataTmp)
+            return VERR_NO_MEMORY;
+
+        memset(paGTDataTmp, '\0', cbGTDataTmp);
+        rc = pImage->pInterfaceIOCallbacks->pfnWriteMetaAsync(pExtent->pImage->pInterfaceIO->pvUser,
+                                                              pExtent->pFile->pStorage,
+                                                              VMDK_SECTOR2BYTE(uGTSector),
+                                                              paGTDataTmp, cbGTDataTmp, pIoCtx,
+                                                              vmdkAllocGrainAsyncComplete, pGrainAlloc);
+        if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+            pGrainAlloc->cIoXfersPending++;
+        else if (RT_FAILURE(rc))
+        {
+            RTMemTmpFree(paGTDataTmp);
+            return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: cannot write grain table allocation in '%s'"), pExtent->pszFullname);
+        }
+
+        if (pExtent->pRGD)
+        {
+            AssertReturn(!uRGTSector, VERR_VD_VMDK_INVALID_HEADER);
+            rc = vmdkFileGetSize(pExtent->pFile, &cbExtentSize);
+            if (RT_FAILURE(rc))
+                return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: error getting size in '%s'"), pExtent->pszFullname);
+            Assert(!(cbExtentSize % 512));
+            uRGTSector = VMDK_BYTE2SECTOR(cbExtentSize);
+
+            /* Normally the redundant grain table is preallocated for hosted
+             * sparse extents that support more than 32 bit sector numbers. So
+             * this shouldn't ever happen on a valid extent. */
+            if (uRGTSector > UINT32_MAX)
+            {
+                RTMemTmpFree(paGTDataTmp);
+                return VERR_VD_VMDK_INVALID_HEADER;
+            }
+            /* Write backup grain table by writing the required number of grain
+             * table cache chunks. */
+            rc = pImage->pInterfaceIOCallbacks->pfnWriteMetaAsync(pExtent->pImage->pInterfaceIO->pvUser,
+                                                                  pExtent->pFile->pStorage,
+                                                                  VMDK_SECTOR2BYTE(uRGTSector),
+                                                                  paGTDataTmp, cbGTDataTmp, pIoCtx,
+                                                                  vmdkAllocGrainAsyncComplete, pGrainAlloc);
+            if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+                pGrainAlloc->cIoXfersPending++;
+            else if (RT_FAILURE(rc))
+            {
+                RTMemTmpFree(paGTDataTmp);
+                return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: cannot write backup grain table allocation in '%s'"), pExtent->pszFullname);
+            }
+        }
+
+        RTMemTmpFree(paGTDataTmp);
+
+        /* Update the grain directory on disk (doing it before writing the
+         * grain table will result in a garbled extent if the operation is
+         * aborted for some reason. Otherwise the worst that can happen is
+         * some unused sectors in the extent. */
+        uint32_t uGTSectorLE = RT_H2LE_U64(uGTSector);
+        rc = pImage->pInterfaceIOCallbacks->pfnWriteMetaAsync(pExtent->pImage->pInterfaceIO->pvUser,
+                                                              pExtent->pFile->pStorage,
+                                                              VMDK_SECTOR2BYTE(pExtent->uSectorGD) + uGDIndex * sizeof(uGTSectorLE),
+                                                              &uGTSectorLE, sizeof(uGTSectorLE), pIoCtx,
+                                                              vmdkAllocGrainAsyncComplete, pGrainAlloc);
+        if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+            pGrainAlloc->cIoXfersPending++;
+        else if (RT_FAILURE(rc))
+            return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: cannot write grain directory entry in '%s'"), pExtent->pszFullname);
+        if (pExtent->pRGD)
+        {
+            uint32_t uRGTSectorLE = RT_H2LE_U64(uRGTSector);
+            rc = pImage->pInterfaceIOCallbacks->pfnWriteMetaAsync(pExtent->pImage->pInterfaceIO->pvUser,
+                                                                  pExtent->pFile->pStorage,
+                                                                  VMDK_SECTOR2BYTE(pExtent->uSectorRGD) + uGDIndex * sizeof(uGTSectorLE),
+                                                                  &uRGTSectorLE, sizeof(uRGTSectorLE), pIoCtx,
+                                                                  vmdkAllocGrainAsyncComplete, pGrainAlloc);
+            if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+                pGrainAlloc->cIoXfersPending++;
+            else if (RT_FAILURE(rc))
+                return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: cannot write backup grain directory entry in '%s'"), pExtent->pszFullname);
+        }
+
+        /* As the final step update the in-memory copy of the GDs. */
+        pExtent->pGD[uGDIndex] = uGTSector;
+        if (pExtent->pRGD)
+            pExtent->pRGD[uGDIndex] = uRGTSector;
+    }
+
+    LogFlow(("uGTSector=%llu uRGTSector=%llu\n", uGTSector, uRGTSector));
+    pGrainAlloc->uGTSector = uGTSector;
+    pGrainAlloc->uRGTSector = uRGTSector;
+
+    rc = vmdkFileGetSize(pExtent->pFile, &cbExtentSize);
+    if (RT_FAILURE(rc))
+        return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: error getting size in '%s'"), pExtent->pszFullname);
+    Assert(!(cbExtentSize % 512));
+
+    if (!pGrainAlloc->cbExtentOld)
+        pGrainAlloc->cbExtentOld = cbExtentSize;
+
+    pGrainAlloc->cbExtentSize = cbExtentSize;
+
+    /* Write the data. Always a full grain, or we're in big trouble. */
+    rc = pImage->pInterfaceIOCallbacks->pfnWriteUserAsync(pImage->pInterfaceIO->pvUser,
+                                                          pExtent->pFile->pStorage,
+                                                          cbExtentSize,
+                                                          pIoCtx, cbWrite,
+                                                          vmdkAllocGrainAsyncComplete, pGrainAlloc);
+    if (rc == VERR_VD_ASYNC_IO_IN_PROGRESS)
+        pGrainAlloc->cIoXfersPending++;
+    else if (RT_FAILURE(rc))
+        return vmdkError(pExtent->pImage, rc, RT_SRC_POS, N_("VMDK: cannot write allocated data block in '%s'"), pExtent->pszFullname);
+
+    rc = vmdkAllocGrainAsyncGTUpdate(pImage, pExtent, pCache, pIoCtx, pGrainAlloc);
+
+    if (!pGrainAlloc->cIoXfersPending)
+    {
+        /* Grain allocation completed. */
+        RTMemFree(pGrainAlloc);
+    }
+
+    LogFlowFunc(("leaving rc=%Rrc\n", rc));
+
     return rc;
 }
@@ -6067,5 +6474,5 @@
     PVMDKIMAGE pImage = (PVMDKIMAGE)pvBackendData;
 
-#if 1
+#if 1 /** @todo: Remove once the async support is tested throughly */
     bool fAsyncIOSupported = false;
 
@@ -6253,10 +6660,7 @@
                     if (!(fWrite & VD_WRITE_NO_ALLOC))
                     {
-                        AssertMsgFailed(("Implement\n"));
-#if 0
                         /* Allocate GT and find out where to store the grain. */
-                        rc = vmdkAllocGrain(pImage->pGTCache, pExtent,
-                                            uSectorExtentRel, pvBuf, cbWrite);
-#endif
+                        rc = vmdkAllocGrainAsync(pImage->pGTCache, pExtent, pIoCtx,
+                                                 uSectorExtentRel, cbWrite);
                     }
                     else
@@ -6323,6 +6727,18 @@
                 case VMDKETYPE_ESX_SPARSE:
 #endif /* VBOX_WITH_VMDK_ESX */
-                    /** @todo: Fake success for now */
-                    rc = VINF_SUCCESS;
+                    rc = vmdkWriteMetaSparseExtentAsync(pImage, pExtent, 0, pIoCtx);
+                    if (RT_FAILURE(rc) && (rc != VERR_VD_ASYNC_IO_IN_PROGRESS))
+                        goto out;
+                    if (pExtent->fFooter)
+                    {
+                        uint64_t cbSize;
+                        rc = vmdkFileGetSize(pExtent->pFile, &cbSize);
+                        if (RT_FAILURE(rc))
+                            goto out;
+                        cbSize = RT_ALIGN_64(cbSize, 512);
+                        rc = vmdkWriteMetaSparseExtent(pExtent, cbSize - 2*512);
+                        if (RT_FAILURE(rc) && (rc != VERR_VD_ASYNC_IO_IN_PROGRESS))
+                            goto out;
+                    }
                     break;
                 case VMDKETYPE_VMFS:
