Handle dependency by VkMemoryDedicatedAllocateInfo

We have a situation that if an image memory is created with
VkMemoryDedicatedAllocateInfo, the following commands that refer to the
same image  must happen in this exact order:

vkCreateImage
vkAllocateMemory (with dedicated image memory)
vkBindImageMemory
vkCreateImageView

Our previous dependency graph implementation uses Vulkan objects as
nodes and does not haven enough granularity to handle this situation.
vkCreateImageView can only be executed after an image is created and
bound to memory. Our previous dependency graph does not have the
notion of "bound to memory". We worked around it by adding
vkBindImageMemory as part of the image initialization steps.

To make sure we can bind image at initialization, we marked image to be
dependent on the memory it bounds to. When adding the new
vkAllocateMemory with dedicated image memory extension into the mix, it
introduced a circular dependency. vkAllocateMemory will say the memory
has dependency on the image. vkBindImageMemory will say the image has
dependency on the memory.

To properly resolve the issue, we will need to record the state of an
Vulkan object, and declare that vkCreateImageView not only depends on an
image, but also requires the image to be bound to memory. We do so by
introducing a "State" enum and use the pair <VkObjectHandle, State> as
the vertex in the deppendency graph. Currently State is an enum with 2
values: CREATED and BOUND_MEMORY. By default, after a VkCreate* command,
an object will be in CREATED state. When calling vkBindImageMemory or
vkBindBufferMemory it will transform the image or buffer into
BOUND_MEMORY state. Then vkCreateImageView will have dependency with
{VkImage, BOUND_MEMORY}.

Then we can create a dependency graph that looks like this:

VkImageView --> {VkImage,BOUND_MEMORY} --> VkMemory
                        |                       |
                        |   ┌-------------------⅃
                        v   v
                       VkImage

No more circular dependency.

Test: GfxstreamEnd2EndVkSnapshotImageTests
Bug: 333447188
Change-Id: Ice45b04292eea151bed18988872e2f34401b7182

5 files changed, 326 insertions, 115 deletions

diff --git a/codegen/vulkan/vulkan-docs-next/scripts/cereal/decodersnapshot.py b/codegen/vulkan/vulkan-docs-next/scripts/cereal/decodersnapshot.py
index 450cf8af..dc708502 100644
--- a/codegen/vulkan/vulkan-docs-next/scripts/cereal/decodersnapshot.py
+++ b/codegen/vulkan/vulkan-docs-next/scripts/cereal/decodersnapshot.py
@@ -9,6 +9,7 @@ from .wrapperdefs import API_PREFIX_UNMARSHAL
 from .wrapperdefs import VULKAN_STREAM_TYPE
 
 from copy import copy
+from dataclasses import dataclass
 
 decoder_snapshot_decl_preamble = """
 
@@ -106,12 +107,25 @@ SNAPSHOT_HANDLE_DEPENDENCIES = [
 
 handleDependenciesDict = dict(SNAPSHOT_HANDLE_DEPENDENCIES)
 
+def extract_deps_vkAllocateMemory(param, access, lenExpr, api, cgen):
+    cgen.stmt("const VkMemoryDedicatedAllocateInfo* dedicatedAllocateInfo = vk_find_struct<VkMemoryDedicatedAllocateInfo>(pAllocateInfo)");
+    cgen.beginIf("dedicatedAllocateInfo");
+    cgen.beginIf("dedicatedAllocateInfo->image")
+    cgen.stmt("mReconstruction.addHandleDependency((const uint64_t*)%s, %s, (uint64_t)(uintptr_t)%s)" % \
+              (access, lenExpr, "unboxed_to_boxed_non_dispatchable_VkImage(dedicatedAllocateInfo->image)"))
+    cgen.endIf()
+    cgen.beginIf("dedicatedAllocateInfo->buffer")
+    cgen.stmt("mReconstruction.addHandleDependency((const uint64_t*)%s, %s, (uint64_t)(uintptr_t)%s)" % \
+              (access, lenExpr, "unboxed_to_boxed_non_dispatchable_VkBuffer(dedicatedAllocateInfo->buffer)"))
+    cgen.endIf()
+    cgen.endIf()
+
 def extract_deps_vkAllocateCommandBuffers(param, access, lenExpr, api, cgen):
     cgen.stmt("mReconstruction.addHandleDependency((const uint64_t*)%s, %s, (uint64_t)(uintptr_t)%s)" % \
               (access, lenExpr, "unboxed_to_boxed_non_dispatchable_VkCommandPool(pAllocateInfo->commandPool)"))
 
 def extract_deps_vkCreateImageView(param, access, lenExpr, api, cgen):
-    cgen.stmt("mReconstruction.addHandleDependency((const uint64_t*)%s, %s, (uint64_t)(uintptr_t)%s)" % \
+    cgen.stmt("mReconstruction.addHandleDependency((const uint64_t*)%s, %s, (uint64_t)(uintptr_t)%s, VkReconstruction::CREATED, VkReconstruction::BOUND_MEMORY)" % \
               (access, lenExpr, "unboxed_to_boxed_non_dispatchable_VkImage(pCreateInfo->image)"))
 
 def extract_deps_vkCreateGraphicsPipelines(param, access, lenExpr, api, cgen):
@@ -131,11 +145,14 @@ def extract_deps_vkCreateFramebuffer(param, access, lenExpr, api, cgen):
     cgen.endFor()
 
 def extract_deps_vkBindImageMemory(param, access, lenExpr, api, cgen):
-    cgen.stmt("mReconstruction.addHandleDependency((const uint64_t*)%s, %s, (uint64_t)(uintptr_t)%s)" % \
+    cgen.stmt("mReconstruction.addHandleDependency((const uint64_t*)%s, %s, (uint64_t)(uintptr_t)%s, VkReconstruction::BOUND_MEMORY)" % \
               (access, lenExpr, "(uint64_t)(uintptr_t)unboxed_to_boxed_non_dispatchable_VkDeviceMemory(memory)"))
+    cgen.stmt("mReconstruction.addHandleDependency((const uint64_t*)%s, %s, (uint64_t)(uintptr_t)((%s)[0]), VkReconstruction::BOUND_MEMORY)" % \
+              (access, lenExpr, access))
 
 specialCaseDependencyExtractors = {
     "vkAllocateCommandBuffers" : extract_deps_vkAllocateCommandBuffers,
+    "vkAllocateMemory" : extract_deps_vkAllocateMemory,
     "vkCreateImageView" : extract_deps_vkCreateImageView,
     "vkCreateGraphicsPipelines" : extract_deps_vkCreateGraphicsPipelines,
     "vkCreateFramebuffer" : extract_deps_vkCreateFramebuffer,
@@ -146,11 +163,14 @@ apiSequences = {
     "vkAllocateMemory" : ["vkAllocateMemory", "vkMapMemoryIntoAddressSpaceGOOGLE"]
 }
 
-# vkBindImageMemory needs to execute before vkCreateImageView
-# Thus we inject it into VkImage creation sequence.
+@dataclass(frozen=True)
+class VkObjectState:
+    vk_object : str
+    state : str = "VkReconstruction::CREATED"
+
 # TODO: add vkBindImageMemory2 into this list
-apiInitializes = {
-    "vkBindImageMemory": ["image"],
+apiChangeState = {
+    "vkBindImageMemory": VkObjectState("image", "VkReconstruction::BOUND_MEMORY"),
 }
 
 apiModifies = {
@@ -162,12 +182,22 @@ delayedDestroys = [
     "vkDestroyShaderModule",
 ]
 
-def is_initialize_operation(api, param):
-    if api.name in apiInitializes:
-        if param.paramName in apiInitializes[api.name]:
+def is_state_change_operation(api, param):
+    if param.isCreatedBy(api):
+        return True
+    if api.name in apiChangeState:
+        if param.paramName == apiChangeState[api.name].vk_object:
             return True
     return False
 
+def get_target_state(api, param):
+    if param.isCreatedBy(api):
+        return "VkReconstruction::CREATED"
+    if api.name in apiChangeState:
+        if param.paramName == apiChangeState[api.name].vk_object:
+            return apiChangeState[api.name].state
+    return None
+
 def is_modify_operation(api, param):
     if api.name in apiModifies:
         if param.paramName in apiModifies[api.name]:
@@ -192,7 +222,7 @@ def emit_impl(typeInfo, api, cgen):
         else:
             access = "(&%s)" % p.paramName
 
-        if p.isCreatedBy(api) or is_initialize_operation(api, p):
+        if is_state_change_operation(api, p):
             if p.isCreatedBy(api):
                 boxed_access = access
             else:
@@ -218,7 +248,7 @@ def emit_impl(typeInfo, api, cgen):
             cgen.stmt("mReconstruction.setApiTrace(apiInfo, OP_%s, snapshotTraceBegin, snapshotTraceBytes)" % api.name)
             if lenAccessGuard is not None:
                 cgen.beginIf(lenAccessGuard)
-            cgen.stmt("mReconstruction.forEachHandleAddApi((const uint64_t*)%s, %s, apiHandle)" % (boxed_access, lenExpr))
+            cgen.stmt(f"mReconstruction.forEachHandleAddApi((const uint64_t*){boxed_access}, {lenExpr}, apiHandle, {get_target_state(api, p)})")
             if p.isCreatedBy(api):
                 cgen.stmt("mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)%s, %s)" % (boxed_access, lenExpr))
             if lenAccessGuard is not None:
diff --git a/common/end2end/GfxstreamEnd2EndVkSnapshotImageTests.cpp b/common/end2end/GfxstreamEnd2EndVkSnapshotImageTests.cpp
index a50e6e49..e81faa59 100644
--- a/common/end2end/GfxstreamEnd2EndVkSnapshotImageTests.cpp
+++ b/common/end2end/GfxstreamEnd2EndVkSnapshotImageTests.cpp
@@ -195,6 +195,73 @@ TEST_P(GfxstreamEnd2EndVkSnapshotImageTest, MultiSampleImage) {
     SnapshotSaveAndLoad();
 }
 
+TEST_P(GfxstreamEnd2EndVkSnapshotImageTest, ImageViewDependencyWithDedicatedMemory) {
+    auto [instance, physicalDevice, device, queue, queueFamilyIndex] =
+        VK_ASSERT(SetUpTypicalVkTestEnvironment());
+
+    const uint32_t width = 32;
+    const uint32_t height = 32;
+
+    const vkhpp::ImageCreateInfo imageCreateInfo = {
+        .pNext = nullptr,
+        .imageType = vkhpp::ImageType::e2D,
+        .extent.width = width,
+        .extent.height = height,
+        .extent.depth = 1,
+        .mipLevels = 1,
+        .arrayLayers = 1,
+        .format = vkhpp::Format::eR8G8B8A8Unorm,
+        .tiling = vkhpp::ImageTiling::eOptimal,
+        .initialLayout = vkhpp::ImageLayout::eUndefined,
+        .usage = vkhpp::ImageUsageFlagBits::eSampled | vkhpp::ImageUsageFlagBits::eTransferDst |
+                 vkhpp::ImageUsageFlagBits::eTransferSrc,
+        .sharingMode = vkhpp::SharingMode::eExclusive,
+        .samples = vkhpp::SampleCountFlagBits::e1,
+    };
+    auto image = device->createImageUnique(imageCreateInfo).value;
+    ASSERT_THAT(image, IsValidHandle());
+
+    vkhpp::MemoryRequirements imageMemoryRequirements{};
+    device->getImageMemoryRequirements(*image, &imageMemoryRequirements);
+
+    const uint32_t imageMemoryIndex = GetMemoryType(physicalDevice, imageMemoryRequirements,
+                                                    vkhpp::MemoryPropertyFlagBits::eDeviceLocal);
+    ASSERT_THAT(imageMemoryIndex, Not(Eq(-1)));
+
+    const vkhpp::MemoryDedicatedAllocateInfo dedicatedAllocateInfo = {
+        .image = *image,
+    };
+
+    const vkhpp::MemoryAllocateInfo imageMemoryAllocateInfo = {
+        .pNext = &dedicatedAllocateInfo,
+        .allocationSize = imageMemoryRequirements.size,
+        .memoryTypeIndex = imageMemoryIndex,
+    };
+
+    auto imageMemory = device->allocateMemoryUnique(imageMemoryAllocateInfo).value;
+    ASSERT_THAT(imageMemory, IsValidHandle());
+
+    ASSERT_THAT(device->bindImageMemory(*image, *imageMemory, 0), IsVkSuccess());
+
+    const vkhpp::ImageViewCreateInfo imageViewCreateInfo = {
+        .image = *image,
+        .viewType = vkhpp::ImageViewType::e2D,
+        .format = vkhpp::Format::eR8G8B8A8Unorm,
+        .subresourceRange =
+            {
+                .aspectMask = vkhpp::ImageAspectFlagBits::eColor,
+                .baseMipLevel = 0,
+                .levelCount = 1,
+                .baseArrayLayer = 0,
+                .layerCount = 1,
+            },
+    };
+    auto imageView = device->createImageViewUnique(imageViewCreateInfo).value;
+    ASSERT_THAT(imageView, IsValidHandle());
+    // Make sure it doesn't crash on load
+    SnapshotSaveAndLoad();
+}
+
 TEST_P(GfxstreamEnd2EndVkSnapshotImageTest, ImageContent) {
     static constexpr int kWidth = 256;
     static constexpr int kHeight = 256;
diff --git a/host/vulkan/VkDecoderSnapshot.cpp b/host/vulkan/VkDecoderSnapshot.cpp
index 0aafe511..0260df9f 100644
--- a/host/vulkan/VkDecoderSnapshot.cpp
+++ b/host/vulkan/VkDecoderSnapshot.cpp
@@ -68,7 +68,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateInstance, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pInstance, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pInstance, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pInstance, 1);
     }
     void vkDestroyInstance(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -95,7 +96,8 @@ class VkDecoderSnapshot::Impl {
                                     snapshotTraceBytes);
         if (pPhysicalDeviceCount) {
             mReconstruction.forEachHandleAddApi((const uint64_t*)pPhysicalDevices,
-                                                (*(pPhysicalDeviceCount)), apiHandle);
+                                                (*(pPhysicalDeviceCount)), apiHandle,
+                                                VkReconstruction::CREATED);
             mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pPhysicalDevices,
                                                     (*(pPhysicalDeviceCount)));
         }
@@ -149,7 +151,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateDevice, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pDevice, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pDevice, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pDevice, 1);
     }
     void vkDestroyDevice(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -194,7 +197,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkGetDeviceQueue, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pQueue, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pQueue, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pQueue, 1);
     }
     void vkQueueSubmit(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -214,11 +218,28 @@ class VkDecoderSnapshot::Impl {
         mReconstruction.addHandles((const uint64_t*)pMemory, 1);
         mReconstruction.addHandleDependency((const uint64_t*)pMemory, 1,
                                             (uint64_t)(uintptr_t)device);
+        const VkMemoryDedicatedAllocateInfo* dedicatedAllocateInfo =
+            vk_find_struct<VkMemoryDedicatedAllocateInfo>(pAllocateInfo);
+        if (dedicatedAllocateInfo) {
+            if (dedicatedAllocateInfo->image) {
+                mReconstruction.addHandleDependency(
+                    (const uint64_t*)pMemory, 1,
+                    (uint64_t)(uintptr_t)unboxed_to_boxed_non_dispatchable_VkImage(
+                        dedicatedAllocateInfo->image));
+            }
+            if (dedicatedAllocateInfo->buffer) {
+                mReconstruction.addHandleDependency(
+                    (const uint64_t*)pMemory, 1,
+                    (uint64_t)(uintptr_t)unboxed_to_boxed_non_dispatchable_VkBuffer(
+                        dedicatedAllocateInfo->buffer));
+            }
+        }
         auto apiHandle = mReconstruction.createApiInfo();
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkAllocateMemory, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pMemory, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pMemory, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pMemory, 1);
     }
     void vkFreeMemory(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -259,12 +280,17 @@ class VkDecoderSnapshot::Impl {
         mReconstruction.addHandleDependency(
             (const uint64_t*)&boxed_VkImage, 1,
             (uint64_t)(uintptr_t)(uint64_t)(uintptr_t)
-                unboxed_to_boxed_non_dispatchable_VkDeviceMemory(memory));
+                unboxed_to_boxed_non_dispatchable_VkDeviceMemory(memory),
+            VkReconstruction::BOUND_MEMORY);
+        mReconstruction.addHandleDependency((const uint64_t*)&boxed_VkImage, 1,
+                                            (uint64_t)(uintptr_t)((&boxed_VkImage)[0]),
+                                            VkReconstruction::BOUND_MEMORY);
         auto apiHandle = mReconstruction.createApiInfo();
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkBindImageMemory, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)&boxed_VkImage, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)&boxed_VkImage, 1, apiHandle,
+                                            VkReconstruction::BOUND_MEMORY);
     }
     void vkGetBufferMemoryRequirements(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
                                        android::base::BumpPool* pool, VkDevice device,
@@ -300,7 +326,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateFence, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pFence, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pFence, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pFence, 1);
     }
     void vkDestroyFence(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -334,7 +361,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateSemaphore, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pSemaphore, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pSemaphore, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pSemaphore, 1);
     }
     void vkDestroySemaphore(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -358,7 +386,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateEvent, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pEvent, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pEvent, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pEvent, 1);
     }
     void vkDestroyEvent(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -391,7 +420,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateQueryPool, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pQueryPool, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pQueryPool, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pQueryPool, 1);
     }
     void vkDestroyQueryPool(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -420,7 +450,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateBuffer, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pBuffer, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pBuffer, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pBuffer, 1);
     }
     void vkDestroyBuffer(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -443,7 +474,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateBufferView, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pView, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pView, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pView, 1);
     }
     void vkDestroyBufferView(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -467,7 +499,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateImage, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pImage, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pImage, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pImage, 1);
     }
     void vkDestroyImage(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -492,12 +525,14 @@ class VkDecoderSnapshot::Impl {
         mReconstruction.addHandleDependency((const uint64_t*)pView, 1, (uint64_t)(uintptr_t)device);
         mReconstruction.addHandleDependency(
             (const uint64_t*)pView, 1,
-            (uint64_t)(uintptr_t)unboxed_to_boxed_non_dispatchable_VkImage(pCreateInfo->image));
+            (uint64_t)(uintptr_t)unboxed_to_boxed_non_dispatchable_VkImage(pCreateInfo->image),
+            VkReconstruction::CREATED, VkReconstruction::BOUND_MEMORY);
         auto apiHandle = mReconstruction.createApiInfo();
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateImageView, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pView, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pView, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pView, 1);
     }
     void vkDestroyImageView(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -522,7 +557,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateShaderModule, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pShaderModule, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pShaderModule, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pShaderModule, 1);
     }
     void vkDestroyShaderModule(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -548,7 +584,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreatePipelineCache, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pPipelineCache, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pPipelineCache, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pPipelineCache, 1);
     }
     void vkDestroyPipelineCache(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -593,7 +630,7 @@ class VkDecoderSnapshot::Impl {
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateGraphicsPipelines, snapshotTraceBegin,
                                     snapshotTraceBytes);
         mReconstruction.forEachHandleAddApi((const uint64_t*)pPipelines, ((createInfoCount)),
-                                            apiHandle);
+                                            apiHandle, VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pPipelines,
                                                 ((createInfoCount)));
     }
@@ -614,7 +651,7 @@ class VkDecoderSnapshot::Impl {
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateComputePipelines, snapshotTraceBegin,
                                     snapshotTraceBytes);
         mReconstruction.forEachHandleAddApi((const uint64_t*)pPipelines, ((createInfoCount)),
-                                            apiHandle);
+                                            apiHandle, VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pPipelines,
                                                 ((createInfoCount)));
     }
@@ -640,7 +677,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreatePipelineLayout, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pPipelineLayout, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pPipelineLayout, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pPipelineLayout, 1);
     }
     void vkDestroyPipelineLayout(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -665,7 +703,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateSampler, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pSampler, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pSampler, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pSampler, 1);
     }
     void vkDestroySampler(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -691,7 +730,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateDescriptorSetLayout, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pSetLayout, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pSetLayout, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pSetLayout, 1);
     }
     void vkDestroyDescriptorSetLayout(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -717,7 +757,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateDescriptorPool, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pDescriptorPool, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pDescriptorPool, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pDescriptorPool, 1);
     }
     void vkDestroyDescriptorPool(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -749,7 +790,8 @@ class VkDecoderSnapshot::Impl {
         mReconstruction.setApiTrace(apiInfo, OP_vkAllocateDescriptorSets, snapshotTraceBegin,
                                     snapshotTraceBytes);
         mReconstruction.forEachHandleAddApi((const uint64_t*)pDescriptorSets,
-                                            pAllocateInfo->descriptorSetCount, apiHandle);
+                                            pAllocateInfo->descriptorSetCount, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pDescriptorSets,
                                                 pAllocateInfo->descriptorSetCount);
     }
@@ -792,7 +834,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateFramebuffer, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pFramebuffer, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pFramebuffer, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pFramebuffer, 1);
     }
     void vkDestroyFramebuffer(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -816,7 +859,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateRenderPass, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pRenderPass, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pRenderPass, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pRenderPass, 1);
     }
     void vkDestroyRenderPass(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -843,7 +887,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateCommandPool, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pCommandPool, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pCommandPool, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pCommandPool, 1);
     }
     void vkDestroyCommandPool(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -874,7 +919,8 @@ class VkDecoderSnapshot::Impl {
         mReconstruction.setApiTrace(apiInfo, OP_vkAllocateCommandBuffers, snapshotTraceBegin,
                                     snapshotTraceBytes);
         mReconstruction.forEachHandleAddApi((const uint64_t*)pCommandBuffers,
-                                            pAllocateInfo->commandBufferCount, apiHandle);
+                                            pAllocateInfo->commandBufferCount, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pCommandBuffers,
                                                 pAllocateInfo->commandBufferCount);
     }
@@ -1159,7 +1205,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkGetDeviceQueue2, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pQueue, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pQueue, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pQueue, 1);
     }
     void vkCreateSamplerYcbcrConversion(const uint8_t* snapshotTraceBegin,
@@ -1178,7 +1225,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateSamplerYcbcrConversion, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pYcbcrConversion, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pYcbcrConversion, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pYcbcrConversion, 1);
     }
     void vkDestroySamplerYcbcrConversion(const uint8_t* snapshotTraceBegin,
@@ -1206,7 +1254,7 @@ class VkDecoderSnapshot::Impl {
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateDescriptorUpdateTemplate,
                                     snapshotTraceBegin, snapshotTraceBytes);
         mReconstruction.forEachHandleAddApi((const uint64_t*)pDescriptorUpdateTemplate, 1,
-                                            apiHandle);
+                                            apiHandle, VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle,
                                                 (const uint64_t*)pDescriptorUpdateTemplate, 1);
     }
@@ -1270,7 +1318,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateRenderPass2, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pRenderPass, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pRenderPass, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pRenderPass, 1);
     }
     void vkCmdBeginRenderPass2(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -1456,7 +1505,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateSwapchainKHR, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pSwapchain, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pSwapchain, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pSwapchain, 1);
     }
     void vkDestroySwapchainKHR(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -1600,7 +1650,7 @@ class VkDecoderSnapshot::Impl {
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateDescriptorUpdateTemplateKHR,
                                     snapshotTraceBegin, snapshotTraceBytes);
         mReconstruction.forEachHandleAddApi((const uint64_t*)pDescriptorUpdateTemplate, 1,
-                                            apiHandle);
+                                            apiHandle, VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle,
                                                 (const uint64_t*)pDescriptorUpdateTemplate, 1);
     }
@@ -1638,7 +1688,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateRenderPass2KHR, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pRenderPass, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pRenderPass, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pRenderPass, 1);
     }
     void vkCmdBeginRenderPass2KHR(const uint8_t* snapshotTraceBegin, size_t snapshotTraceBytes,
@@ -1712,7 +1763,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateSamplerYcbcrConversionKHR,
                                     snapshotTraceBegin, snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pYcbcrConversion, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pYcbcrConversion, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pYcbcrConversion, 1);
     }
     void vkDestroySamplerYcbcrConversionKHR(const uint8_t* snapshotTraceBegin,
@@ -1972,7 +2024,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateDebugUtilsMessengerEXT, snapshotTraceBegin,
                                     snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pMessenger, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pMessenger, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pMessenger, 1);
     }
     void vkDestroyDebugUtilsMessengerEXT(const uint8_t* snapshotTraceBegin,
@@ -2216,7 +2269,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateImageWithRequirementsGOOGLE,
                                     snapshotTraceBegin, snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pImage, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pImage, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pImage, 1);
     }
     void vkCreateBufferWithRequirementsGOOGLE(
@@ -2234,7 +2288,8 @@ class VkDecoderSnapshot::Impl {
         auto apiInfo = mReconstruction.getApiInfo(apiHandle);
         mReconstruction.setApiTrace(apiInfo, OP_vkCreateBufferWithRequirementsGOOGLE,
                                     snapshotTraceBegin, snapshotTraceBytes);
-        mReconstruction.forEachHandleAddApi((const uint64_t*)pBuffer, 1, apiHandle);
+        mReconstruction.forEachHandleAddApi((const uint64_t*)pBuffer, 1, apiHandle,
+                                            VkReconstruction::CREATED);
         mReconstruction.setCreatedHandlesForApi(apiHandle, (const uint64_t*)pBuffer, 1);
     }
     void vkGetMemoryHostAddressInfoGOOGLE(const uint8_t* snapshotTraceBegin,
diff --git a/host/vulkan/VkReconstruction.cpp b/host/vulkan/VkReconstruction.cpp
index 2b148cdc..dc415cf8 100644
--- a/host/vulkan/VkReconstruction.cpp
+++ b/host/vulkan/VkReconstruction.cpp
@@ -39,15 +39,21 @@ namespace vk {
 
 VkReconstruction::VkReconstruction() = default;
 
-std::vector<uint64_t> typeTagSortedHandles(const std::vector<uint64_t>& handles) {
+std::vector<VkReconstruction::HandleWithState> typeTagSortedHandles(
+    const std::vector<VkReconstruction::HandleWithState>& handles) {
     using EntityManagerTypeForHandles = android::base::EntityManager<32, 16, 16, int>;
 
-    std::vector<uint64_t> res = handles;
+    std::vector<VkReconstruction::HandleWithState> res = handles;
 
-    std::sort(res.begin(), res.end(), [](uint64_t lhs, uint64_t rhs) {
-        return EntityManagerTypeForHandles::getHandleType(lhs) <
-               EntityManagerTypeForHandles::getHandleType(rhs);
-    });
+    std::sort(res.begin(), res.end(),
+              [](const VkReconstruction::HandleWithState& lhs,
+                 const VkReconstruction::HandleWithState& rhs) {
+                  if (lhs.second != rhs.second) {
+                      return lhs.second < rhs.second;
+                  }
+                  return EntityManagerTypeForHandles::getHandleType(lhs.first) <
+                         EntityManagerTypeForHandles::getHandleType(rhs.first);
+              });
 
     return res;
 }
@@ -59,27 +65,31 @@ void VkReconstruction::save(android::base::Stream* stream) {
     dump();
 #endif
 
-    std::unordered_map<uint64_t, int> totalParents;
-    std::vector<uint64_t> next;
+    std::unordered_map<HandleWithState, int, HandleWithStateHash> totalParents;
+    std::vector<HandleWithState> next;
 
     mHandleReconstructions.forEachLiveComponent_const(
         [&totalParents, &next](bool live, uint64_t componentHandle, uint64_t entityHandle,
-                               const HandleReconstruction& item) {
-            totalParents[entityHandle] = item.parentHandles.size();
-            if (item.parentHandles.empty()) {
-                next.push_back(entityHandle);
+                               const HandleWithStateReconstruction& item) {
+            for (int state = BEGIN; state < HANDLE_STATE_COUNT; state++) {
+                const auto& parents = item.states[state].parentHandles;
+                HandleWithState handleWithState = {entityHandle, static_cast<HandleState>(state)};
+                totalParents[handleWithState] = parents.size();
+                if (parents.empty()) {
+                    next.push_back(handleWithState);
+                }
             }
         });
 
-    std::vector<std::vector<uint64_t>> handlesByTopoOrder;
+    std::vector<std::vector<HandleWithState>> handlesByTopoOrder;
 
     while (!next.empty()) {
         next = typeTagSortedHandles(next);
         handlesByTopoOrder.push_back(std::move(next));
-        const std::vector<uint64_t>& current = handlesByTopoOrder.back();
-        for (uint64_t handle : current) {
-            auto item = mHandleReconstructions.get(handle);
-            for (auto childHandle : item->childHandles) {
+        const std::vector<HandleWithState>& current = handlesByTopoOrder.back();
+        for (const auto& handle : current) {
+            const auto& item = mHandleReconstructions.get(handle.first)->states[handle.second];
+            for (const auto& childHandle : item.childHandles) {
                 if (--totalParents[childHandle] == 0) {
                     next.push_back(childHandle);
                 }
@@ -91,12 +101,12 @@ void VkReconstruction::save(android::base::Stream* stream) {
     uniqApiRefsByTopoOrder.reserve(handlesByTopoOrder.size() + 1);
     for (const auto& handles : handlesByTopoOrder) {
         std::vector<uint64_t> nextApis;
-        for (uint64_t handle : handles) {
-            auto item = mHandleReconstructions.get(handle);
-            for (uint64_t apiRef : item->apiRefs) {
+        for (const auto& handle : handles) {
+            auto item = mHandleReconstructions.get(handle.first)->states[handle.second];
+            for (uint64_t apiRef : item.apiRefs) {
 #if DEBUG_RECONSTRUCTION
                 auto apiItem = mApiTrace.get(apiRef);
-                DEBUG_RECON("adding handle 0x%lx API 0x%lx op code %d\n", handle, apiRef,
+                DEBUG_RECON("adding handle 0x%lx API 0x%lx op code %d\n", handle.first, apiRef,
                             apiItem->opCode);
 #endif
                 nextApis.push_back(apiRef);
@@ -294,17 +304,20 @@ void VkReconstruction::dump() {
 
     mHandleReconstructions.forEachLiveComponent_const(
         [this](bool live, uint64_t componentHandle, uint64_t entityHandle,
-               const HandleReconstruction& reconstruction) {
+               const HandleWithStateReconstruction& reconstruction) {
             fprintf(stderr, "VkReconstruction::%s: %p handle 0x%llx api refs:\n", __func__, this,
                     (unsigned long long)entityHandle);
-            for (auto apiHandle : reconstruction.apiRefs) {
-                auto apiInfo = mApiTrace.get(apiHandle);
-                const char* apiName = apiInfo ? api_opcode_to_string(apiInfo->opCode) : "unalloced";
-                fprintf(stderr, "VkReconstruction::%s:     0x%llx: %s\n", __func__,
-                        (unsigned long long)apiHandle, apiName);
-                for (auto createdHandle : apiInfo->createdHandles) {
-                    fprintf(stderr, "VkReconstruction::%s:         created 0x%llx\n", __func__,
-                            (unsigned long long)createdHandle);
+            for (const auto& state : reconstruction.states) {
+                for (auto apiHandle : state.apiRefs) {
+                    auto apiInfo = mApiTrace.get(apiHandle);
+                    const char* apiName =
+                        apiInfo ? api_opcode_to_string(apiInfo->opCode) : "unalloced";
+                    fprintf(stderr, "VkReconstruction::%s:     0x%llx: %s\n", __func__,
+                            (unsigned long long)apiHandle, apiName);
+                    for (auto createdHandle : apiInfo->createdHandles) {
+                        fprintf(stderr, "VkReconstruction::%s:         created 0x%llx\n", __func__,
+                                (unsigned long long)createdHandle);
+                    }
                 }
             }
         });
@@ -330,7 +343,7 @@ void VkReconstruction::addHandles(const uint64_t* toAdd, uint32_t count) {
 
     for (uint32_t i = 0; i < count; ++i) {
         DEBUG_RECON("add 0x%llx", (unsigned long long)toAdd[i]);
-        mHandleReconstructions.add(toAdd[i], HandleReconstruction());
+        mHandleReconstructions.add(toAdd[i], HandleWithStateReconstruction());
     }
 }
 
@@ -344,41 +357,63 @@ void VkReconstruction::removeHandles(const uint64_t* toRemove, uint32_t count, b
         // It might delete the parents before children, which will automatically remove
         // the name.
         if (!item) continue;
-
-        if (!recursive && item->childHandles.size()) {
+        // Break circuler references
+        if (item->destroying) continue;
+        item->destroying = true;
+        if (!recursive) {
+            bool couldDestroy = true;
+            for (const auto& state : item->states) {
+                if (!state.childHandles.size()) {
+                    continue;
+                }
+                couldDestroy = false;
+                break;
+            }
             // TODO(b/330769702): perform delayed destroy when all children are destroyed.
-            DEBUG_RECON("delay destroy of 0x%lx, TODO: actually destroy it", toRemove[i]);
-            item->destroyed = true;
+            if (couldDestroy) {
+                forEachHandleDeleteApi(toRemove + i, 1);
+                mHandleReconstructions.remove(toRemove[i]);
+            } else {
+                DEBUG_RECON("delay destroy of 0x%lx, TODO: actually destroy it", toRemove[i]);
+                item->delayed_destroy = true;
+                item->destroying = false;
+            }
             continue;
         }
-        for (uint64_t parentHandle : item->parentHandles) {
-            auto parentItem = mHandleReconstructions.get(parentHandle);
-            if (!parentItem) {
-                continue;
+        for (size_t j = 0; j < item->states.size(); j++) {
+            for (const auto& parentHandle : item->states[j].parentHandles) {
+                auto parentItem = mHandleReconstructions.get(parentHandle.first);
+                if (!parentItem) {
+                    continue;
+                }
+                parentItem->states[parentHandle.second].childHandles.erase(
+                    {toRemove[i], static_cast<HandleState>(j)});
+            }
+            item->states[j].parentHandles.clear();
+            std::vector<uint64_t> childHandles;
+            for (const auto& childHandle : item->states[j].childHandles) {
+                if (childHandle.second == CREATED) {
+                    childHandles.push_back(childHandle.first);
+                }
             }
-            parentItem->childHandles.erase(toRemove[i]);
+            item->states[j].childHandles.clear();
+            removeHandles(childHandles.data(), childHandles.size());
         }
         forEachHandleDeleteApi(toRemove + i, 1);
-        // Keep a local copy because removeHandles will mess up
-        // item->childHandles iterators.
-        std::vector<uint64_t> childHandles(item->childHandles.begin(), item->childHandles.end());
-        removeHandles(childHandles.data(), childHandles.size());
-        item->childHandles.clear();
         mHandleReconstructions.remove(toRemove[i]);
     }
 }
 
 void VkReconstruction::forEachHandleAddApi(const uint64_t* toProcess, uint32_t count,
-                                           uint64_t apiHandle) {
+                                           uint64_t apiHandle, HandleState state) {
     if (!toProcess) return;
 
     for (uint32_t i = 0; i < count; ++i) {
         auto item = mHandleReconstructions.get(toProcess[i]);
-
         if (!item) continue;
 
-        item->apiRefs.push_back(apiHandle);
-        DEBUG_RECON("handle 0x%lx added api 0x%lx", toProcess[i], apiHandle);
+        item->states[state].apiRefs.push_back(apiHandle);
+        DEBUG_RECON("handle 0x%lx state %d added api 0x%lx", toProcess[i], state, apiHandle);
     }
 }
 
@@ -391,12 +426,13 @@ void VkReconstruction::forEachHandleDeleteApi(const uint64_t* toProcess, uint32_
 
         if (!item) continue;
 
-        for (auto handle : item->apiRefs) {
-            destroyApiInfo(handle);
+        for (auto& state : item->states) {
+            for (auto handle : state.apiRefs) {
+                destroyApiInfo(handle);
+            }
+            state.apiRefs.clear();
         }
 
-        item->apiRefs.clear();
-
         auto modifyItem = mHandleModifications.get(toProcess[i]);
 
         if (!modifyItem) continue;
@@ -406,7 +442,8 @@ void VkReconstruction::forEachHandleDeleteApi(const uint64_t* toProcess, uint32_
 }
 
 void VkReconstruction::addHandleDependency(const uint64_t* handles, uint32_t count,
-                                           uint64_t parentHandle) {
+                                           uint64_t parentHandle, HandleState childState,
+                                           HandleState parentState) {
     if (!handles) return;
 
     auto parentItem = mHandleReconstructions.get(parentHandle);
@@ -415,14 +452,18 @@ void VkReconstruction::addHandleDependency(const uint64_t* handles, uint32_t cou
         DEBUG_RECON("WARN: adding null parent item: 0x%lx\n", parentHandle);
         return;
     }
+    auto& parentItemState = parentItem->states[parentState];
 
     for (uint32_t i = 0; i < count; ++i) {
         auto childItem = mHandleReconstructions.get(handles[i]);
         if (!childItem) {
             continue;
         }
-        parentItem->childHandles.insert(handles[i]);
-        childItem->parentHandles.push_back(parentHandle);
+        parentItemState.childHandles.insert({handles[i], static_cast<HandleState>(childState)});
+        childItem->states[childState].parentHandles.push_back(
+            {parentHandle, static_cast<HandleState>(parentState)});
+        DEBUG_RECON("Child handle 0x%lx state %d depends on parent handle 0x%lx state %d",
+                    handles[i], childState, parentHandle, parentState);
     }
 }
 
diff --git a/host/vulkan/VkReconstruction.h b/host/vulkan/VkReconstruction.h
index 328330aa..bb78649d 100644
--- a/host/vulkan/VkReconstruction.h
+++ b/host/vulkan/VkReconstruction.h
@@ -46,15 +46,31 @@ class VkReconstruction {
     using ApiTrace = android::base::EntityManager<32, 16, 16, ApiInfo>;
     using ApiHandle = ApiTrace::EntityHandle;
 
+    enum HandleState { BEGIN = 0, CREATED = 0, BOUND_MEMORY = 1, HANDLE_STATE_COUNT };
+
+    typedef std::pair<uint64_t, HandleState> HandleWithState;
+    struct HandleWithStateHash {
+        inline size_t operator()(const HandleWithState& v) const {
+            std::hash<uint64_t> int_hasher;
+            return int_hasher(v.first) ^ int_hasher(v.second);
+        }
+    };
+
     struct HandleReconstruction {
         std::vector<ApiHandle> apiRefs;
-        std::unordered_set<uint64_t> childHandles;
-        std::vector<uint64_t> parentHandles;
-        bool destroyed = false;
+        std::unordered_set<HandleWithState, HandleWithStateHash> childHandles;
+        std::vector<HandleWithState> parentHandles;
+    };
+
+    struct HandleWithStateReconstruction {
+        std::vector<HandleReconstruction> states =
+            std::vector<HandleReconstruction>(HANDLE_STATE_COUNT);
+        bool delayed_destroy = false;
+        bool destroying = false;
     };
 
-    using HandleReconstructions =
-        android::base::UnpackedComponentManager<32, 16, 16, HandleReconstruction>;
+    using HandleWithStateReconstructions =
+        android::base::UnpackedComponentManager<32, 16, 16, HandleWithStateReconstruction>;
 
     struct HandleModification {
         std::vector<ApiHandle> apiRefs;
@@ -77,10 +93,12 @@ class VkReconstruction {
     void addHandles(const uint64_t* toAdd, uint32_t count);
     void removeHandles(const uint64_t* toRemove, uint32_t count, bool recursive = true);
 
-    void forEachHandleAddApi(const uint64_t* toProcess, uint32_t count, uint64_t apiHandle);
+    void forEachHandleAddApi(const uint64_t* toProcess, uint32_t count, uint64_t apiHandle,
+                             HandleState state = CREATED);
     void forEachHandleDeleteApi(const uint64_t* toProcess, uint32_t count);
 
-    void addHandleDependency(const uint64_t* handles, uint32_t count, uint64_t parentHandle);
+    void addHandleDependency(const uint64_t* handles, uint32_t count, uint64_t parentHandle,
+                             HandleState childState = CREATED, HandleState parentState = CREATED);
 
     void setCreatedHandlesForApi(uint64_t apiHandle, const uint64_t* created, uint32_t count);
 
@@ -113,7 +131,7 @@ class VkReconstruction {
 
     ApiTrace mApiTrace;
 
-    HandleReconstructions mHandleReconstructions;
+    HandleWithStateReconstructions mHandleReconstructions;
     HandleModifications mHandleModifications;
 
     std::vector<uint64_t> mExtraHandlesForNextApi;