[ats_vtd,v1,20/24] atc: generic ATC that can be used by PCIe devices that support SVM

diff --git a/tests/unit/meson.build b/tests/unit/meson.build
index 228a21d03c..5c9a6fe9f4 100644
--- a/tests/unit/meson.build
+++ b/tests/unit/meson.build
@@ -52,6 +52,7 @@  tests = {
   'test-interval-tree': [],
   'test-xs-node': [qom],
   'test-virtio-dmabuf': [meson.project_source_root() / 'hw/display/virtio-dmabuf.c'],
+  'test-atc': []
 }
 
 if have_system or have_tools
diff --git a/tests/unit/test-atc.c b/tests/unit/test-atc.c
new file mode 100644
index 0000000000..60fa60924a
--- /dev/null
+++ b/tests/unit/test-atc.c
@@ -0,0 +1,502 @@ 
+/*
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "util/atc.h"
+
+static inline bool tlb_entry_equal(IOMMUTLBEntry *e1, IOMMUTLBEntry *e2)
+{
+    if (!e1 || !e2) {
+        return !e1 && !e2;
+    }
+    return e1->iova == e2->iova &&
+            e1->addr_mask == e2->addr_mask &&
+            e1->pasid == e2->pasid &&
+            e1->perm == e2->perm &&
+            e1->target_as == e2->target_as &&
+            e1->translated_addr == e2->translated_addr;
+}
+
+static void assert_lookup_equals(ATC *atc, IOMMUTLBEntry *target,
+                                 uint32_t pasid, hwaddr iova)
+{
+    IOMMUTLBEntry *result;
+    result = atc_lookup(atc, pasid, iova);
+    g_assert(tlb_entry_equal(result, target));
+}
+
+static void check_creation(uint64_t page_size, uint8_t address_width,
+                           uint8_t levels, uint8_t level_offset,
+                           bool should_work) {
+    ATC *atc = atc_new(page_size, address_width);
+    if (atc) {
+        if (atc->levels != levels || atc->level_offset != level_offset) {
+            g_assert(false); /* ATC created but invalid configuration : fail */
+        }
+        atc_destroy(atc);
+        g_assert(should_work);
+    } else {
+        g_assert(!should_work);
+    }
+}
+
+static void test_creation_parameters(void)
+{
+    check_creation(8, 39, 3, 9, false);
+    check_creation(4095, 39, 3, 9, false);
+    check_creation(4097, 39, 3, 9, false);
+    check_creation(8192, 48, 0, 0, false);
+
+    check_creation(4096, 38, 0, 0, false);
+    check_creation(4096, 39, 3, 9, true);
+    check_creation(4096, 40, 0, 0, false);
+    check_creation(4096, 47, 0, 0, false);
+    check_creation(4096, 48, 4, 9, true);
+    check_creation(4096, 49, 0, 0, false);
+    check_creation(4096, 56, 0, 0, false);
+    check_creation(4096, 57, 5, 9, true);
+    check_creation(4096, 58, 0, 0, false);
+
+    check_creation(16384, 35, 0, 0, false);
+    check_creation(16384, 36, 2, 11, true);
+    check_creation(16384, 37, 0, 0, false);
+    check_creation(16384, 46, 0, 0, false);
+    check_creation(16384, 47, 3, 11, true);
+    check_creation(16384, 48, 0, 0, false);
+    check_creation(16384, 57, 0, 0, false);
+    check_creation(16384, 58, 4, 11, true);
+    check_creation(16384, 59, 0, 0, false);
+}
+
+static void test_single_entry(void)
+{
+    IOMMUTLBEntry entry = {
+        .iova = 0x123456789000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = 5,
+        .perm = IOMMU_RW,
+        .translated_addr = 0xdeadbeefULL,
+    };
+
+    ATC *atc = atc_new(4096, 48);
+    g_assert(atc);
+
+    assert_lookup_equals(atc, NULL, entry.pasid,
+                         entry.iova + (entry.addr_mask / 2));
+
+    atc_create_address_space_cache(atc, entry.pasid);
+    g_assert(atc_update(atc, &entry) == 0);
+
+    assert_lookup_equals(atc, NULL, entry.pasid + 1,
+                         entry.iova + (entry.addr_mask / 2));
+    assert_lookup_equals(atc, &entry, entry.pasid,
+                         entry.iova + (entry.addr_mask / 2));
+
+    atc_destroy(atc);
+}
+
+static void test_page_boundaries(void)
+{
+    static const uint32_t pasid = 5;
+    static const hwaddr page_size = 4096;
+
+    /* 2 consecutive entries */
+    IOMMUTLBEntry e1 = {
+        .iova = 0x123456789000ULL,
+        .addr_mask = page_size - 1,
+        .pasid = pasid,
+        .perm = IOMMU_RW,
+        .translated_addr = 0xdeadbeefULL,
+    };
+    IOMMUTLBEntry e2 = {
+        .iova = e1.iova + page_size,
+        .addr_mask = page_size - 1,
+        .pasid = pasid,
+        .perm = IOMMU_RW,
+        .translated_addr = 0x900df00dULL,
+    };
+
+    ATC *atc = atc_new(page_size, 48);
+
+    atc_create_address_space_cache(atc, e1.pasid);
+    /* creating the address space twice should not be a problem */
+    atc_create_address_space_cache(atc, e1.pasid);
+
+    atc_update(atc, &e1);
+    atc_update(atc, &e2);
+
+    assert_lookup_equals(atc, NULL, e1.pasid, e1.iova - 1);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova + e1.addr_mask);
+    g_assert((e1.iova + e1.addr_mask + 1) == e2.iova);
+    assert_lookup_equals(atc, &e2, e2.pasid, e2.iova);
+    assert_lookup_equals(atc, &e2, e2.pasid, e2.iova + e2.addr_mask);
+    assert_lookup_equals(atc, NULL, e2.pasid, e2.iova + e2.addr_mask + 1);
+
+    assert_lookup_equals(atc, NULL, e1.pasid + 10, e1.iova);
+    assert_lookup_equals(atc, NULL, e2.pasid + 10, e2.iova);
+    atc_destroy(atc);
+}
+
+static void test_huge_page(void)
+{
+    static const uint32_t pasid = 5;
+    static const hwaddr page_size = 4096;
+    IOMMUTLBEntry e1 = {
+        .iova = 0x123456600000ULL,
+        .addr_mask = 0x1fffffULL,
+        .pasid = pasid,
+        .perm = IOMMU_RW,
+        .translated_addr = 0xdeadbeefULL,
+    };
+    hwaddr addr;
+
+    ATC *atc = atc_new(page_size, 48);
+
+    atc_create_address_space_cache(atc, e1.pasid);
+    atc_update(atc, &e1);
+
+    for (addr = e1.iova; addr <= e1.iova + e1.addr_mask; addr += page_size) {
+        assert_lookup_equals(atc, &e1, e1.pasid, addr);
+    }
+    /* addr is now out of the huge page */
+    assert_lookup_equals(atc, NULL, e1.pasid, addr);
+    atc_destroy(atc);
+}
+
+static void test_pasid(void)
+{
+    hwaddr addr = 0xaaaaaaaaa000ULL;
+    IOMMUTLBEntry e1 = {
+        .iova = addr,
+        .addr_mask = 0xfffULL,
+        .pasid = 8,
+        .perm = IOMMU_RW,
+        .translated_addr = 0xdeadbeefULL,
+    };
+    IOMMUTLBEntry e2 = {
+        .iova = addr,
+        .addr_mask = 0xfffULL,
+        .pasid = 2,
+        .perm = IOMMU_RW,
+        .translated_addr = 0xb001ULL,
+    };
+    uint16_t i;
+
+    ATC *atc = atc_new(4096, 48);
+
+    atc_create_address_space_cache(atc, e1.pasid);
+    atc_create_address_space_cache(atc, e2.pasid);
+    atc_update(atc, &e1);
+    atc_update(atc, &e2);
+
+    for (i = 0; i <= MAX(e1.pasid, e2.pasid) + 1; ++i) {
+        if (i == e1.pasid || i == e2.pasid) {
+            continue;
+        }
+        assert_lookup_equals(atc, NULL, i, addr);
+    }
+    assert_lookup_equals(atc, &e1, e1.pasid, addr);
+    assert_lookup_equals(atc, &e1, e1.pasid, addr);
+    atc_destroy(atc);
+}
+
+static void test_large_address(void)
+{
+    IOMMUTLBEntry e1 = {
+        .iova = 0xaaaaaaaaa000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = 8,
+        .perm = IOMMU_RW,
+        .translated_addr = 0x5eeeeeedULL,
+    };
+    IOMMUTLBEntry e2 = {
+        .iova = 0x1f00baaaaabf000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = e1.pasid,
+        .perm = IOMMU_RW,
+        .translated_addr = 0xdeadbeefULL,
+    };
+
+    ATC *atc = atc_new(4096, 57);
+
+    atc_create_address_space_cache(atc, e1.pasid);
+    atc_update(atc, &e1);
+    atc_update(atc, &e2);
+
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, &e2, e2.pasid, e2.iova);
+    atc_destroy(atc);
+}
+
+static void test_bigger_page(void)
+{
+    IOMMUTLBEntry e1 = {
+        .iova = 0xaabbccdde000ULL,
+        .addr_mask = 0x1fffULL,
+        .pasid = 1,
+        .perm = IOMMU_RW,
+        .translated_addr = 0x5eeeeeedULL,
+    };
+    hwaddr i;
+
+    ATC *atc = atc_new(8192, 43);
+
+    atc_create_address_space_cache(atc, e1.pasid);
+    atc_update(atc, &e1);
+
+    i = e1.iova & (~e1.addr_mask);
+    assert_lookup_equals(atc, NULL, e1.pasid, i - 1);
+    while (i <= e1.iova + e1.addr_mask) {
+        assert_lookup_equals(atc, &e1, e1.pasid, i);
+        ++i;
+    }
+    assert_lookup_equals(atc, NULL, e1.pasid, i);
+    atc_destroy(atc);
+}
+
+static void test_unknown_pasid(void)
+{
+    IOMMUTLBEntry e1 = {
+        .iova = 0xaabbccfff000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = 1,
+        .perm = IOMMU_RW,
+        .translated_addr = 0x5eeeeeedULL,
+    };
+
+    ATC *atc = atc_new(4096, 48);
+    g_assert(atc_update(atc, &e1) != 0);
+    assert_lookup_equals(atc, NULL, e1.pasid, e1.iova);
+}
+
+static void test_invalidation(void)
+{
+    static uint64_t page_size = 4096;
+    IOMMUTLBEntry e1 = {
+        .iova = 0xaabbccddf000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = 1,
+        .perm = IOMMU_RW,
+        .translated_addr = 0x5eeeeeedULL,
+    };
+    IOMMUTLBEntry e2 = {
+        .iova = 0xffe00000ULL,
+        .addr_mask = 0x1fffffULL,
+        .pasid = 1,
+        .perm = IOMMU_RW,
+        .translated_addr = 0xb000001ULL,
+    };
+    IOMMUTLBEntry e3;
+
+    ATC *atc = atc_new(page_size , 48);
+    atc_create_address_space_cache(atc, e1.pasid);
+
+    atc_update(atc, &e1);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    atc_invalidate(atc, &e1);
+    assert_lookup_equals(atc, NULL, e1.pasid, e1.iova);
+
+    atc_update(atc, &e1);
+    atc_update(atc, &e2);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, &e2, e2.pasid, e2.iova);
+    atc_invalidate(atc, &e2);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, NULL, e2.pasid, e2.iova);
+
+    /* invalidate a huge page by invalidating a small region */
+    for (hwaddr addr = e2.iova; addr <= (e2.iova + e2.addr_mask);
+         addr += page_size) {
+        atc_update(atc, &e2);
+        assert_lookup_equals(atc, &e2, e2.pasid, e2.iova);
+        e3 = (IOMMUTLBEntry){
+            .iova = addr,
+            .addr_mask = page_size - 1,
+            .pasid = e2.pasid,
+            .perm = IOMMU_RW,
+            .translated_addr = 0,
+        };
+        atc_invalidate(atc, &e3);
+        assert_lookup_equals(atc, NULL, e2.pasid, e2.iova);
+    }
+}
+
+static void test_delete_address_space_cache(void)
+{
+    static uint64_t page_size = 4096;
+    IOMMUTLBEntry e1 = {
+        .iova = 0xaabbccddf000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = 1,
+        .perm = IOMMU_RW,
+        .translated_addr = 0x5eeeeeedULL,
+    };
+    IOMMUTLBEntry e2 = {
+        .iova = e1.iova,
+        .addr_mask = 0xfffULL,
+        .pasid = 2,
+        .perm = IOMMU_RW,
+        .translated_addr = 0x5eeeeeedULL,
+    };
+
+    ATC *atc = atc_new(page_size , 48);
+    atc_create_address_space_cache(atc, e1.pasid);
+
+    atc_update(atc, &e1);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    atc_invalidate(atc, &e2); /* unkown pasid : is a nop*/
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+
+    atc_create_address_space_cache(atc, e2.pasid);
+    atc_update(atc, &e2);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, &e2, e2.pasid, e2.iova);
+    atc_invalidate(atc, &e1);
+    /* e1 has been removed but e2 is still there */
+    assert_lookup_equals(atc, NULL, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, &e2, e2.pasid, e2.iova);
+
+    atc_update(atc, &e1);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, &e2, e2.pasid, e2.iova);
+
+    atc_delete_address_space_cache(atc, e2.pasid);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, NULL, e2.pasid, e2.iova);
+}
+
+static void test_invalidate_entire_address_space(void)
+{
+    static uint64_t page_size = 4096;
+    IOMMUTLBEntry e1 = {
+        .iova = 0x1000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = 1,
+        .perm = IOMMU_RW,
+        .translated_addr = 0x5eedULL,
+    };
+    IOMMUTLBEntry e2 = {
+        .iova = 0xfffffffff000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = 1,
+        .perm = IOMMU_RW,
+        .translated_addr = 0xbeefULL,
+    };
+    IOMMUTLBEntry e3 = {
+        .iova = 0,
+        .addr_mask = 0xffffffffffffffffULL,
+        .pasid = 1,
+        .perm = IOMMU_RW,
+        .translated_addr = 0,
+    };
+
+    ATC *atc = atc_new(page_size , 48);
+    atc_create_address_space_cache(atc, e1.pasid);
+
+    atc_update(atc, &e1);
+    atc_update(atc, &e2);
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, &e2, e2.pasid, e2.iova);
+    atc_invalidate(atc, &e3);
+    /* e1 has been removed but e2 is still there */
+    assert_lookup_equals(atc, NULL, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, NULL, e2.pasid, e2.iova);
+
+    atc_destroy(atc);
+}
+
+static void test_reset(void)
+{
+    static uint64_t page_size = 4096;
+    IOMMUTLBEntry e1 = {
+        .iova = 0x1000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = 1,
+        .perm = IOMMU_RW,
+        .translated_addr = 0x5eedULL,
+    };
+    IOMMUTLBEntry e2 = {
+        .iova = 0xfffffffff000ULL,
+        .addr_mask = 0xfffULL,
+        .pasid = 2,
+        .perm = IOMMU_RW,
+        .translated_addr = 0xbeefULL,
+    };
+
+    ATC *atc = atc_new(page_size , 48);
+    atc_create_address_space_cache(atc, e1.pasid);
+    atc_create_address_space_cache(atc, e2.pasid);
+    atc_update(atc, &e1);
+    atc_update(atc, &e2);
+
+    assert_lookup_equals(atc, &e1, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, &e2, e2.pasid, e2.iova);
+
+    atc_reset(atc);
+
+    assert_lookup_equals(atc, NULL, e1.pasid, e1.iova);
+    assert_lookup_equals(atc, NULL, e2.pasid, e2.iova);
+}
+
+static void test_get_max_number_of_pages(void)
+{
+    static uint64_t page_size = 4096;
+    hwaddr base = 0xc0fee000; /* aligned */
+    ATC *atc = atc_new(page_size , 48);
+    g_assert(atc_get_max_number_of_pages(atc, base, page_size / 2) == 1);
+    g_assert(atc_get_max_number_of_pages(atc, base, page_size) == 1);
+    g_assert(atc_get_max_number_of_pages(atc, base, page_size + 1) == 2);
+
+    g_assert(atc_get_max_number_of_pages(atc, base + 10, 1) == 1);
+    g_assert(atc_get_max_number_of_pages(atc, base + 10, page_size - 10) == 1);
+    g_assert(atc_get_max_number_of_pages(atc, base + 10,
+                                         page_size - 10 + 1) == 2);
+    g_assert(atc_get_max_number_of_pages(atc, base + 10,
+                                         page_size - 10 + 2) == 2);
+
+    g_assert(atc_get_max_number_of_pages(atc, base + page_size - 1, 1) == 1);
+    g_assert(atc_get_max_number_of_pages(atc, base + page_size - 1, 2) == 2);
+    g_assert(atc_get_max_number_of_pages(atc, base + page_size - 1, 3) == 2);
+
+    g_assert(atc_get_max_number_of_pages(atc, base + 10, page_size * 20) == 21);
+    g_assert(atc_get_max_number_of_pages(atc, base + 10,
+                                         (page_size * 20) + (page_size - 10))
+                                          == 21);
+    g_assert(atc_get_max_number_of_pages(atc, base + 10,
+                                         (page_size * 20) +
+                                         (page_size - 10 + 1)) == 22);
+}
+
+int main(int argc, char **argv)
+{
+    g_test_init(&argc, &argv, NULL);
+    g_test_add_func("/atc/test_creation_parameters", test_creation_parameters);
+    g_test_add_func("/atc/test_single_entry", test_single_entry);
+    g_test_add_func("/atc/test_page_boundaries", test_page_boundaries);
+    g_test_add_func("/atc/test_huge_page", test_huge_page);
+    g_test_add_func("/atc/test_pasid", test_pasid);
+    g_test_add_func("/atc/test_large_address", test_large_address);
+    g_test_add_func("/atc/test_bigger_page", test_bigger_page);
+    g_test_add_func("/atc/test_unknown_pasid", test_unknown_pasid);
+    g_test_add_func("/atc/test_invalidation", test_invalidation);
+    g_test_add_func("/atc/test_delete_address_space_cache",
+                    test_delete_address_space_cache);
+    g_test_add_func("/atc/test_invalidate_entire_address_space",
+                    test_invalidate_entire_address_space);
+    g_test_add_func("/atc/test_reset", test_reset);
+    g_test_add_func("/atc/test_get_max_number_of_pages",
+                    test_get_max_number_of_pages);
+    return g_test_run();
+}
diff --git a/util/atc.c b/util/atc.c
new file mode 100644
index 0000000000..3332d7e2b8
--- /dev/null
+++ b/util/atc.c
@@ -0,0 +1,211 @@ 
+/*
+ * QEMU emulation of an ATC
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "util/atc.h"
+
+
+#define PAGE_TABLE_ENTRY_SIZE 8
+
+/* a pasid is hashed using the identity function */
+static guint atc_pasid_key_hash(gconstpointer v)
+{
+    return (guint)(uintptr_t)v; /* pasid */
+}
+
+/* pasid equality */
+static gboolean atc_pasid_key_equal(gconstpointer v1, gconstpointer v2)
+{
+    return v1 == v2;
+}
+
+/* Hash function for IOTLB entries */
+static guint atc_addr_key_hash(gconstpointer v)
+{
+    hwaddr addr = (hwaddr)v;
+    return (guint)((addr >> 32) ^ (addr & 0xffffffffU));
+}
+
+/* Equality test for IOTLB entries */
+static gboolean atc_addr_key_equal(gconstpointer v1, gconstpointer v2)
+{
+    return (hwaddr)v1 == (hwaddr)v2;
+}
+
+static void atc_address_space_free(void *as)
+{
+    g_hash_table_unref(as);
+}
+
+/* return log2(val), or UINT8_MAX if val is not a power of 2 */
+static uint8_t ilog2(uint64_t val)
+{
+    uint8_t result = 0;
+    while (val != 1) {
+        if (val & 1) {
+            return UINT8_MAX;
+        }
+
+        val >>= 1;
+        result += 1;
+    }
+    return result;
+}
+
+ATC *atc_new(uint64_t page_size, uint8_t address_width)
+{
+    ATC *atc;
+    uint8_t log_page_size = ilog2(page_size);
+    /* number of bits each used to store all the intermediate indexes */
+    uint64_t addr_lookup_indexes_size;
+
+    if (log_page_size == UINT8_MAX) {
+        return NULL;
+    }
+    /*
+     * We only support page table entries of 8 (PAGE_TABLE_ENTRY_SIZE) bytes
+     * log2(page_size / 8) = log2(page_size) - 3
+     * is the level offset
+     */
+    if (log_page_size <= 3) {
+       return NULL;
+    }
+
+    atc = g_new0(ATC, 1);
+    atc->address_spaces = g_hash_table_new_full(atc_pasid_key_hash,
+                                                atc_pasid_key_equal,
+                                                NULL, atc_address_space_free);
+    atc->level_offset = log_page_size - 3;
+    /* at this point, we know that page_size is a power of 2 */
+    atc->min_addr_mask = page_size - 1;
+    addr_lookup_indexes_size = address_width - log_page_size;
+    if ((addr_lookup_indexes_size % atc->level_offset) != 0) {
+        goto error;
+    }
+    atc->levels = addr_lookup_indexes_size / atc->level_offset;
+    atc->page_size = page_size;
+    return atc;
+
+error:
+    g_free(atc);
+    return NULL;
+}
+
+static inline GHashTable *atc_get_address_space_cache(ATC *atc, uint32_t pasid)
+{
+    return g_hash_table_lookup(atc->address_spaces,
+                               (gconstpointer)(uintptr_t)pasid);
+}
+
+void atc_create_address_space_cache(ATC *atc, uint32_t pasid)
+{
+    GHashTable *as_cache;
+
+    as_cache = atc_get_address_space_cache(atc, pasid);
+    if (!as_cache) {
+        as_cache = g_hash_table_new_full(atc_addr_key_hash,
+                                         atc_addr_key_equal,
+                                         NULL, g_free);
+        g_hash_table_replace(atc->address_spaces,
+                             (gpointer)(uintptr_t)pasid, as_cache);
+    }
+}
+
+void atc_delete_address_space_cache(ATC *atc, uint32_t pasid)
+{
+    g_hash_table_remove(atc->address_spaces, (gpointer)(uintptr_t)pasid);
+}
+
+int atc_update(ATC *atc, IOMMUTLBEntry *entry)
+{
+    IOMMUTLBEntry *value;
+    GHashTable *as_cache = atc_get_address_space_cache(atc, entry->pasid);
+    if (!as_cache) {
+        return -ENODEV;
+    }
+    value = g_memdup2(entry, sizeof(*value));
+    g_hash_table_replace(as_cache, (gpointer)(entry->iova), value);
+    return 0;
+}
+
+IOMMUTLBEntry *atc_lookup(ATC *atc, uint32_t pasid, hwaddr addr)
+{
+    IOMMUTLBEntry *entry;
+    hwaddr mask = atc->min_addr_mask;
+    hwaddr key = addr & (~mask);
+    GHashTable *as_cache = atc_get_address_space_cache(atc, pasid);
+
+    if (!as_cache) {
+        return NULL;
+    }
+
+    /*
+     * Iterate over the possible page sizes and try to find a hit
+    */
+    for (uint8_t level = 0; level < atc->levels; ++level) {
+        entry = g_hash_table_lookup(as_cache, (gconstpointer)key);
+        if (entry) {
+            return entry;
+        }
+        mask = (mask << atc->level_offset) | ((1 << atc->level_offset) - 1);
+        key = addr & (~mask);
+    }
+
+    return NULL;
+}
+
+static gboolean atc_invalidate_entry_predicate(gpointer key, gpointer value,
+                                               gpointer user_data)
+{
+    IOMMUTLBEntry *entry = (IOMMUTLBEntry *)value;
+    IOMMUTLBEntry *target = (IOMMUTLBEntry *)user_data;
+    hwaddr target_mask = ~target->addr_mask;
+    hwaddr entry_mask = ~entry->addr_mask;
+    return ((target->iova & target_mask) == (entry->iova & target_mask)) ||
+           ((target->iova & entry_mask) == (entry->iova & entry_mask));
+}
+
+void atc_invalidate(ATC *atc, IOMMUTLBEntry *entry)
+{
+    GHashTable *as_cache = atc_get_address_space_cache(atc, entry->pasid);
+    if (!as_cache) {
+        return;
+    }
+    g_hash_table_foreach_remove(as_cache,
+                                atc_invalidate_entry_predicate,
+                                entry);
+}
+
+void atc_destroy(ATC *atc)
+{
+    g_hash_table_unref(atc->address_spaces);
+}
+
+size_t atc_get_max_number_of_pages(ATC *atc, hwaddr addr, size_t length)
+{
+    hwaddr page_mask = ~(atc->min_addr_mask);
+    size_t result = (length / atc->page_size);
+    if ((((addr & page_mask) + length - 1) & page_mask) !=
+        ((addr + length - 1) & page_mask)) {
+        result += 1;
+    }
+    return result + (length % atc->page_size != 0 ? 1 : 0);
+}
+
+void atc_reset(ATC *atc)
+{
+    g_hash_table_remove_all(atc->address_spaces);
+}
diff --git a/util/atc.h b/util/atc.h
new file mode 100644
index 0000000000..8be95f5cca
--- /dev/null
+++ b/util/atc.h
@@ -0,0 +1,117 @@ 
+/*
+ * QEMU emulation of an ATC
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef UTIL_ATC_H
+#define UTIL_ATC_H
+
+#include "qemu/osdep.h"
+#include "exec/memory.h"
+
+typedef struct ATC {
+    GHashTable *address_spaces; /* Key : pasid, value : GHashTable */
+    hwaddr min_addr_mask;
+    uint64_t page_size;
+    uint8_t levels;
+    uint8_t level_offset;
+} ATC;
+
+/*
+ * atc_new: Create an ATC.
+ *
+ * Return an ATC or NULL if the creation failed
+ *
+ * @page_size: #PCIDevice doing the memory access
+ * @address_width: width of the virtual addresses used by the IOMMU (in bits)
+ */
+ATC *atc_new(uint64_t page_size, uint8_t address_width);
+
+/*
+ * atc_update: Insert or update an entry in the cache
+ *
+ * Return 0 if the operation succeeds, a negative error code otherwise
+ *
+ * The insertion will fail if the address space associated with this pasid
+ * has not been created with atc_create_address_space_cache
+ *
+ * @atc: the ATC to update
+ * @entry: the tlb entry to insert into the cache
+ */
+int atc_update(ATC *atc, IOMMUTLBEntry *entry);
+
+/*
+ * atc_create_address_space_cache: delare a new address space
+ * identified by a PASID
+ *
+ * @atc: the ATC to update
+ * @pasid: the pasid of the address space to be created
+ */
+void atc_create_address_space_cache(ATC *atc, uint32_t pasid);
+
+/*
+ * atc_delete_address_space_cache: delete an address space
+ * identified by a PASID
+ *
+ * @atc: the ATC to update
+ * @pasid: the pasid of the address space to be deleted
+ */
+void atc_delete_address_space_cache(ATC *atc, uint32_t pasid);
+
+/*
+ * atc_lookup: query the cache in a given address space
+ *
+ * @atc: the ATC to query
+ * @pasid: the pasid of the address space to query
+ * @addr: the virtual address to translate
+ */
+IOMMUTLBEntry *atc_lookup(ATC *atc, uint32_t pasid, hwaddr addr);
+
+/*
+ * atc_invalidate: invalidate an entry in the cache
+ *
+ * @atc: the ATC to update
+ * @entry: the entry to invalidate
+ */
+void atc_invalidate(ATC *atc, IOMMUTLBEntry *entry);
+
+/*
+ * atc_destroy: delete an ATC
+ *
+ * @atc: the cache to be deleted
+ */
+void atc_destroy(ATC *atc);
+
+/*
+ * atc_get_max_number_of_pages: get the number of pages a memory operation
+ * will access if all the pages concerned have the minimum size.
+ *
+ * This function can be used to determine the size of the result array to be
+ * allocated when issuing an ATS request.
+ *
+ * @atc: the cache
+ * @addr: start address
+ * @length: number of bytes accessed from addr
+ */
+size_t atc_get_max_number_of_pages(ATC *atc, hwaddr addr, size_t length);
+
+/*
+ * atc_reset: invalidates all the entries stored in the ATC
+ *
+ * @atc: the cache
+ */
+void atc_reset(ATC *atc);
+
+#endif
diff --git a/util/meson.build b/util/meson.build
index 0ef9886be0..a2e0e9e5d7 100644
--- a/util/meson.build
+++ b/util/meson.build
@@ -94,6 +94,7 @@  if have_block
   util_ss.add(files('hbitmap.c'))
   util_ss.add(files('hexdump.c'))
   util_ss.add(files('iova-tree.c'))
+  util_ss.add(files('atc.c'))
   util_ss.add(files('iov.c', 'uri.c'))
   util_ss.add(files('nvdimm-utils.c'))
   util_ss.add(files('block-helpers.c'))