diff --git a/shared/OpenglCodecCommon/goldfish_address_space.cpp b/shared/OpenglCodecCommon/goldfish_address_space.cpp
index 50ea76b..afa6b85 100644
--- a/shared/OpenglCodecCommon/goldfish_address_space.cpp
+++ b/shared/OpenglCodecCommon/goldfish_address_space.cpp
@@ -1,3 +1,18 @@
+// Copyright (C) 2019 The Android Open Source Project
+// Copyright (C) 2019 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
 #if PLATFORM_SDK_VERSION < 26
 #include <cutils/log.h>
 #else
@@ -7,17 +22,71 @@
 #include "goldfish_address_space.h"
 
 #ifdef HOST_BUILD
-GoldfishAddressSpaceBlock::GoldfishAddressSpaceBlock() : m_guest_ptr(NULL) {}
-GoldfishAddressSpaceBlock::~GoldfishAddressSpaceBlock() {}
+
+#include "android/base/SubAllocator.h"
+#include "android/base/memory/LazyInstance.h"
+
+// AddressSpaceHost is a global class for obtaining physical addresses
+// for the host-side build.
+class AddressSpaceHost {
+public:
+    AddressSpaceHost() : mAlloc(0, 16ULL * 1024ULL * 1048576ULL, 4096) { }
+    uint64_t alloc(size_t size) {
+        return (uint64_t)(uintptr_t)mAlloc.alloc(size);
+    }
+    void free(uint64_t addr) {
+        mAlloc.free((void*)(uintptr_t)addr);
+    }
+private:
+    android::base::SubAllocator mAlloc;
+};
+
+static android::base::LazyInstance<AddressSpaceHost> sAddressSpaceHost =
+    LAZY_INSTANCE_INIT;
+
+// It may seem like there should be one allocator per provider,
+// but to properly reflect the guest behavior where there is only one
+// allocator in the system and multiple providers are possible,
+// we need to have a separate global object (sAddressSpaceHost).
+GoldfishAddressSpaceBlockProvider::GoldfishAddressSpaceBlockProvider()
+    : mAlloc(sAddressSpaceHost.ptr()) {}
+
+GoldfishAddressSpaceBlockProvider::~GoldfishAddressSpaceBlockProvider() { }
+
+uint64_t GoldfishAddressSpaceBlockProvider::allocPhys(size_t size) {
+    AddressSpaceHost* hostAlloc = reinterpret_cast<AddressSpaceHost*>(mAlloc);
+    return hostAlloc->alloc(size);
+}
+
+void GoldfishAddressSpaceBlockProvider::freePhys(uint64_t phys) {
+    AddressSpaceHost* hostAlloc = reinterpret_cast<AddressSpaceHost*>(mAlloc);
+    return hostAlloc->free(phys);
+}
+
+GoldfishAddressSpaceBlock::GoldfishAddressSpaceBlock() :
+    m_alloced(false), m_guest_ptr(NULL), m_phys_addr(0), m_provider(NULL) {}
+GoldfishAddressSpaceBlock::~GoldfishAddressSpaceBlock() { destroy(); }
+
+GoldfishAddressSpaceBlock &GoldfishAddressSpaceBlock::operator=(const GoldfishAddressSpaceBlock &rhs)
+{
+    m_guest_ptr = rhs.m_guest_ptr;
+    m_phys_addr = rhs.m_phys_addr;
+    m_provider = rhs.m_provider;
+    return *this;
+}
 
 bool GoldfishAddressSpaceBlock::allocate(GoldfishAddressSpaceBlockProvider *provider, size_t size)
 {
+    destroy();
+    m_phys_addr = provider->allocPhys(size);
+    m_alloced = true;
+    m_provider = provider;
     return true;
 }
 
 uint64_t GoldfishAddressSpaceBlock::physAddr() const
 {
-    return 42;  // some random number, not used
+    return m_phys_addr;
 }
 
 uint64_t GoldfishAddressSpaceBlock::hostAddr() const
@@ -38,7 +107,13 @@
 
 void GoldfishAddressSpaceBlock::destroy()
 {
-    m_guest_ptr = NULL;
+    if (m_alloced) {
+        m_guest_ptr = NULL;
+        if (m_provider) {
+            m_provider->freePhys(m_phys_addr);
+        }
+        m_alloced = false;
+    }
 }
 
 void GoldfishAddressSpaceBlock::replace(GoldfishAddressSpaceBlock *other)
diff --git a/shared/OpenglCodecCommon/goldfish_address_space.h b/shared/OpenglCodecCommon/goldfish_address_space.h
index 752a723..637e20d 100644
--- a/shared/OpenglCodecCommon/goldfish_address_space.h
+++ b/shared/OpenglCodecCommon/goldfish_address_space.h
@@ -21,7 +21,19 @@
 class GoldfishAddressSpaceBlock;
 
 #ifdef HOST_BUILD
-class GoldfishAddressSpaceBlockProvider {};
+class GoldfishAddressSpaceBlockProvider {
+public:
+    GoldfishAddressSpaceBlockProvider();
+    ~GoldfishAddressSpaceBlockProvider();
+
+    uint64_t allocPhys(size_t size);
+    void freePhys(uint64_t phys);
+
+private:
+   void* mAlloc;
+
+   friend class GoldfishAddressSpaceBlock;
+};
 #else
 class GoldfishAddressSpaceBlockProvider {
 public:
@@ -56,7 +68,10 @@
     GoldfishAddressSpaceBlock &operator=(const GoldfishAddressSpaceBlock &);
 
 #ifdef HOST_BUILD
+    bool        m_alloced;
     void     *m_guest_ptr;
+    uint64_t  m_phys_addr;
+    GoldfishAddressSpaceBlockProvider* m_provider;
 #else
 #ifdef __Fuchsia__
     uint32_t  m_vmo;
diff --git a/system/vulkan_enc/HostVisibleMemoryVirtualization.cpp b/system/vulkan_enc/HostVisibleMemoryVirtualization.cpp
index 8e254d0..2780d2a 100644
--- a/system/vulkan_enc/HostVisibleMemoryVirtualization.cpp
+++ b/system/vulkan_enc/HostVisibleMemoryVirtualization.cpp
@@ -272,7 +272,7 @@
              alloc->nonCoherentAtomSize - 1) /
             alloc->nonCoherentAtomSize);
 
-    ALOGD("%s: alloc size %u mapped size %u ncaSize %u\n", __func__,
+    ALOGV("%s: alloc size %u mapped size %u ncaSize %u\n", __func__,
             (unsigned int)pAllocateInfo->allocationSize,
             (unsigned int)mappedSize,
             (unsigned int)alloc->nonCoherentAtomSize);
@@ -296,4 +296,11 @@
     memset(toFree, 0x0, sizeof(SubAlloc));
 }
 
+bool canSubAlloc(android::base::SubAllocator* subAlloc, VkDeviceSize size) {
+    auto ptr = subAlloc->alloc(size);
+    if (!ptr) return false;
+    subAlloc->free(ptr);
+    return true;
+}
+
 } // namespace goldfish_vk
diff --git a/system/vulkan_enc/HostVisibleMemoryVirtualization.h b/system/vulkan_enc/HostVisibleMemoryVirtualization.h
index 4f8651b..ad25353 100644
--- a/system/vulkan_enc/HostVisibleMemoryVirtualization.h
+++ b/system/vulkan_enc/HostVisibleMemoryVirtualization.h
@@ -117,4 +117,5 @@
 
 void subFreeHostMemory(SubAlloc* toFree);
 
+bool canSubAlloc(android::base::SubAllocator* subAlloc, VkDeviceSize size);
 } // namespace goldfish_vk
diff --git a/system/vulkan_enc/ResourceTracker.cpp b/system/vulkan_enc/ResourceTracker.cpp
index 3fecd09..4f928c2 100644
--- a/system/vulkan_enc/ResourceTracker.cpp
+++ b/system/vulkan_enc/ResourceTracker.cpp
@@ -1,4 +1,4 @@
-/// Copyright (C) 2018 The Android Open Source Project
+// Copyright (C) 2018 The Android Open Source Project
 // Copyright (C) 2018 Google Inc.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
@@ -230,11 +230,16 @@
         std::vector<VkPhysicalDevice> physicalDevices;
     };
 
+    using HostMemBlocks = std::vector<HostMemAlloc>;
+    using HostMemBlockIndex = size_t;
+
+#define INVALID_HOST_MEM_BLOCK (-1)
+
     struct VkDevice_Info {
         VkPhysicalDevice physdev;
         VkPhysicalDeviceProperties props;
         VkPhysicalDeviceMemoryProperties memProps;
-        HostMemAlloc hostMemAllocs[VK_MAX_MEMORY_TYPES] = {};
+        std::vector<HostMemBlocks> hostMemBlocks { VK_MAX_MEMORY_TYPES };
         uint32_t apiVersion;
         std::set<std::string> enabledExtensions;
         VkFence fence = VK_NULL_HANDLE;
@@ -1037,7 +1042,9 @@
         VkEncoder* enc = (VkEncoder*)context;
 
         for (uint32_t i = 0; i < VK_MAX_MEMORY_TYPES; ++i) {
-            destroyHostMemAlloc(enc, device, &info.hostMemAllocs[i]);
+            for (auto& block : info.hostMemBlocks[i]) {
+                destroyHostMemAlloc(enc, device, &block);
+            }
         }
 
         if (info.fence != VK_NULL_HANDLE) {
@@ -1286,6 +1293,121 @@
     }
 #endif
 
+    HostMemBlockIndex getOrAllocateHostMemBlockLocked(
+        HostMemBlocks& blocks,
+        const VkMemoryAllocateInfo* pAllocateInfo,
+        VkEncoder* enc,
+        VkDevice device,
+        const VkDevice_Info& deviceInfo) {
+
+        HostMemBlockIndex res = 0;
+        bool found = false;
+
+        while (!found) {
+            for (HostMemBlockIndex i = 0; i < blocks.size(); ++i) {
+                if (blocks[i].initialized &&
+                    blocks[i].initResult == VK_SUCCESS &&
+                    canSubAlloc(
+                        blocks[i].subAlloc,
+                        pAllocateInfo->allocationSize)) {
+                    res = i;
+                    found = true;
+                    return res;
+                }
+            }
+
+            blocks.push_back({});
+
+            auto& hostMemAlloc = blocks.back();
+
+            // Uninitialized block; allocate on host.
+            static constexpr VkDeviceSize oneMb = 1048576;
+            static constexpr VkDeviceSize kDefaultHostMemBlockSize =
+                16 * oneMb; // 16 mb
+            VkDeviceSize roundedUpAllocSize =
+                oneMb * ((pAllocateInfo->allocationSize + oneMb - 1) / oneMb);
+
+            VkDeviceSize virtualHeapSize = VIRTUAL_HOST_VISIBLE_HEAP_SIZE;
+
+            VkDeviceSize blockSizeNeeded =
+                std::max(roundedUpAllocSize,
+                    std::min(virtualHeapSize,
+                             kDefaultHostMemBlockSize));
+
+            VkMemoryAllocateInfo allocInfoForHost = *pAllocateInfo;
+
+            allocInfoForHost.allocationSize = blockSizeNeeded;
+
+            // TODO: Support dedicated/external host visible allocation
+            allocInfoForHost.pNext = nullptr;
+
+            mLock.unlock();
+            VkResult host_res =
+                enc->vkAllocateMemory(
+                    device,
+                    &allocInfoForHost,
+                    nullptr,
+                    &hostMemAlloc.memory);
+            mLock.lock();
+
+            if (host_res != VK_SUCCESS) {
+                ALOGE("Could not allocate backing for virtual host visible memory: %d",
+                      host_res);
+                hostMemAlloc.initialized = true;
+                hostMemAlloc.initResult = host_res;
+                return INVALID_HOST_MEM_BLOCK;
+            }
+
+            auto& hostMemInfo = info_VkDeviceMemory[hostMemAlloc.memory];
+            hostMemInfo.allocationSize = allocInfoForHost.allocationSize;
+            VkDeviceSize nonCoherentAtomSize =
+                deviceInfo.props.limits.nonCoherentAtomSize;
+            hostMemInfo.mappedSize = hostMemInfo.allocationSize;
+            hostMemInfo.memoryTypeIndex =
+                pAllocateInfo->memoryTypeIndex;
+            hostMemAlloc.nonCoherentAtomSize = nonCoherentAtomSize;
+
+            uint64_t directMappedAddr = 0;
+
+            mLock.unlock();
+            VkResult directMapResult =
+                enc->vkMapMemoryIntoAddressSpaceGOOGLE(
+                    device, hostMemAlloc.memory, &directMappedAddr);
+            mLock.lock();
+
+            if (directMapResult != VK_SUCCESS) {
+                hostMemAlloc.initialized = true;
+                hostMemAlloc.initResult = directMapResult;
+                mLock.unlock();
+                enc->vkFreeMemory(device, hostMemAlloc.memory, nullptr);
+                mLock.lock();
+                return INVALID_HOST_MEM_BLOCK;
+            }
+
+            hostMemInfo.mappedPtr =
+                (uint8_t*)(uintptr_t)directMappedAddr;
+            hostMemInfo.virtualHostVisibleBacking = true;
+
+            VkResult hostMemAllocRes =
+                finishHostMemAllocInit(
+                    enc,
+                    device,
+                    pAllocateInfo->memoryTypeIndex,
+                    nonCoherentAtomSize,
+                    hostMemInfo.allocationSize,
+                    hostMemInfo.mappedSize,
+                    hostMemInfo.mappedPtr,
+                    &hostMemAlloc);
+
+            if (hostMemAllocRes != VK_SUCCESS) {
+                return INVALID_HOST_MEM_BLOCK;
+            }
+        }
+
+        // unreacheable, but we need to make Werror happy
+        return INVALID_HOST_MEM_BLOCK;
+    }
+
     VkResult on_vkAllocateMemory(
         void* context,
         VkResult input_result,
@@ -1458,7 +1580,7 @@
         }
 
         if (ahw) {
-            ALOGD("%s: AHBIMPORT", __func__);
+            ALOGD("%s: Import AHardwareBulffer", __func__);
             const native_handle_t *handle =
                 AHardwareBuffer_getNativeHandle(ahw);
             const cb_handle_t* cb_handle =
@@ -1565,78 +1687,25 @@
         if (it == info_VkDevice.end()) return VK_ERROR_DEVICE_LOST;
         auto& deviceInfo = it->second;
 
-        HostMemAlloc* hostMemAlloc =
-            &deviceInfo.hostMemAllocs[finalAllocInfo.memoryTypeIndex];
+        auto& hostMemBlocksForTypeIndex =
+            deviceInfo.hostMemBlocks[finalAllocInfo.memoryTypeIndex];
 
-        if (!hostMemAlloc->initialized) {
-            VkMemoryAllocateInfo allocInfoForHost = finalAllocInfo;
-            allocInfoForHost.allocationSize = VIRTUAL_HOST_VISIBLE_HEAP_SIZE;
-            // TODO: Support dedicated allocation
-            allocInfoForHost.pNext = nullptr;
+        HostMemBlockIndex blockIndex =
+            getOrAllocateHostMemBlockLocked(
+                hostMemBlocksForTypeIndex,
+                &finalAllocInfo,
+                enc,
+                device,
+                deviceInfo);
 
-            lock.unlock();
-            VkResult host_res =
-                enc->vkAllocateMemory(
-                    device,
-                    &allocInfoForHost,
-                    nullptr,
-                    &hostMemAlloc->memory);
-            lock.lock();
-
-            if (host_res != VK_SUCCESS) {
-                ALOGE("Could not allocate backing for virtual host visible memory: %d",
-                      host_res);
-                hostMemAlloc->initialized = true;
-                hostMemAlloc->initResult = host_res;
-                return host_res;
-            }
-
-            auto& hostMemInfo = info_VkDeviceMemory[hostMemAlloc->memory];
-            hostMemInfo.allocationSize = allocInfoForHost.allocationSize;
-            VkDeviceSize nonCoherentAtomSize =
-                deviceInfo.props.limits.nonCoherentAtomSize;
-            hostMemInfo.mappedSize = hostMemInfo.allocationSize;
-            hostMemInfo.memoryTypeIndex =
-                finalAllocInfo.memoryTypeIndex;
-            hostMemAlloc->nonCoherentAtomSize = nonCoherentAtomSize;
-
-            uint64_t directMappedAddr = 0;
-            lock.unlock();
-            VkResult directMapResult =
-                enc->vkMapMemoryIntoAddressSpaceGOOGLE(
-                    device, hostMemAlloc->memory, &directMappedAddr);
-            lock.lock();
-
-            if (directMapResult != VK_SUCCESS) {
-                hostMemAlloc->initialized = true;
-                hostMemAlloc->initResult = directMapResult;
-                return directMapResult;
-            }
-
-            hostMemInfo.mappedPtr =
-                (uint8_t*)(uintptr_t)directMappedAddr;
-            hostMemInfo.virtualHostVisibleBacking = true;
-
-            VkResult hostMemAllocRes =
-                finishHostMemAllocInit(
-                    enc,
-                    device,
-                    finalAllocInfo.memoryTypeIndex,
-                    nonCoherentAtomSize,
-                    hostMemInfo.allocationSize,
-                    hostMemInfo.mappedSize,
-                    hostMemInfo.mappedPtr,
-                    hostMemAlloc);
-
-            if (hostMemAllocRes != VK_SUCCESS) {
-                return hostMemAllocRes;
-            }
+        if (blockIndex == INVALID_HOST_MEM_BLOCK) {
+            return VK_ERROR_OUT_OF_HOST_MEMORY;
         }
 
         VkDeviceMemory_Info virtualMemInfo;
 
         subAllocHostMemory(
-            hostMemAlloc,
+            &hostMemBlocksForTypeIndex[blockIndex],
             &finalAllocInfo,
             &virtualMemInfo.subAlloc);