util/iova-tree.c

   1 /*
   2  * IOVA tree implementation based on GTree.
   3  *
   4  * Copyright 2018 Red Hat, Inc.
   5  *
   6  * Authors:
   7  *  Peter Xu <peterx@redhat.com>
   8  *
   9  * This work is licensed under the terms of the GNU GPL, version 2 or later.
  10  */
  11
  12 #include "qemu/osdep.h"
  13 #include "qemu/iova-tree.h"
  14
  15 struct IOVATree {
  16     GTree *tree;
  17 };
  18
  19 /* Args to pass to iova_tree_alloc foreach function. */
  20 struct IOVATreeAllocArgs {
  21     /* Size of the desired allocation */
  22     size_t new_size;
  23
  24     /* The minimum address allowed in the allocation */
  25     hwaddr iova_begin;
  26
  27     /* Map at the left of the hole, can be NULL if "this" is first one */
  28     const DMAMap *prev;
  29
  30     /* Map at the right of the hole, can be NULL if "prev" is the last one */
  31     const DMAMap *this;
  32
  33     /* If found, we fill in the IOVA here */
  34     hwaddr iova_result;
  35
  36     /* Whether have we found a valid IOVA */
  37     bool iova_found;
  38 };
  39
  40 typedef struct IOVATreeFindIOVAArgs {
  41     const DMAMap *needle;
  42     const DMAMap *result;
  43 } IOVATreeFindIOVAArgs;
  44
  45 /**
  46  * Iterate args to the next hole
  47  *
  48  * @args: The alloc arguments
  49  * @next: The next mapping in the tree. Can be NULL to signal the last one
  50  */
  51 static void iova_tree_alloc_args_iterate(struct IOVATreeAllocArgs *args,
  52                                          const DMAMap *next)
  53 {
  54     args->prev = args->this;
  55     args->this = next;
  56 }
  57
  58 static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
  59 {
  60     const DMAMap *m1 = a, *m2 = b;
  61
  62     if (m1->iova > m2->iova + m2->size) {
  63         return 1;
  64     }
  65
  66     if (m1->iova + m1->size < m2->iova) {
  67         return -1;
  68     }
  69
  70     /* Overlapped */
  71     return 0;
  72 }
  73
  74 IOVATree *iova_tree_new(void)
  75 {
  76     IOVATree *iova_tree = g_new0(IOVATree, 1);
  77
  78     /* We don't have values actually, no need to free */
  79     iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL);
  80
  81     return iova_tree;
  82 }
  83
  84 const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map)
  85 {
  86     return g_tree_lookup(tree->tree, map);
  87 }
  88
  89 static gboolean iova_tree_find_address_iterator(gpointer key, gpointer value,
  90                                                 gpointer data)
  91 {
  92     const DMAMap *map = key;
  93     IOVATreeFindIOVAArgs *args = data;
  94     const DMAMap *needle;
  95
  96     g_assert(key == value);
  97
  98     needle = args->needle;
  99     if (map->translated_addr + map->size < needle->translated_addr ||
 100         needle->translated_addr + needle->size < map->translated_addr) {
 101         return false;
 102     }
 103
 104     args->result = map;
 105     return true;
 106 }
 107
 108 const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map)
 109 {
 110     IOVATreeFindIOVAArgs args = {
 111         .needle = map,
 112     };
 113
 114     g_tree_foreach(tree->tree, iova_tree_find_address_iterator, &args);
 115     return args.result;
 116 }
 117
 118 const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova)
 119 {
 120     const DMAMap map = { .iova = iova, .size = 0 };
 121
 122     return iova_tree_find(tree, &map);
 123 }
 124
 125 static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range)
 126 {
 127     /* Key and value are sharing the same range data */
 128     g_tree_insert(gtree, range, range);
 129 }
 130
 131 int iova_tree_insert(IOVATree *tree, const DMAMap *map)
 132 {
 133     DMAMap *new;
 134
 135     if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
 136         return IOVA_ERR_INVALID;
 137     }
 138
 139     /* We don't allow to insert range that overlaps with existings */
 140     if (iova_tree_find(tree, map)) {
 141         return IOVA_ERR_OVERLAP;
 142     }
 143
 144     new = g_new0(DMAMap, 1);
 145     memcpy(new, map, sizeof(*new));
 146     iova_tree_insert_internal(tree->tree, new);
 147
 148     return IOVA_OK;
 149 }
 150
 151 static gboolean iova_tree_traverse(gpointer key, gpointer value,
 152                                 gpointer data)
 153 {
 154     iova_tree_iterator iterator = data;
 155     DMAMap *map = key;
 156
 157     g_assert(key == value);
 158
 159     return iterator(map);
 160 }
 161
 162 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator)
 163 {
 164     g_tree_foreach(tree->tree, iova_tree_traverse, iterator);
 165 }
 166
 167 void iova_tree_remove(IOVATree *tree, DMAMap map)
 168 {
 169     const DMAMap *overlap;
 170
 171     while ((overlap = iova_tree_find(tree, &map))) {
 172         g_tree_remove(tree->tree, overlap);
 173     }
 174 }
 175
 176 /**
 177  * Try to find an unallocated IOVA range between prev and this elements.
 178  *
 179  * @args: Arguments to allocation
 180  *
 181  * Cases:
 182  *
 183  * (1) !prev, !this: No entries allocated, always succeed
 184  *
 185  * (2) !prev, this: We're iterating at the 1st element.
 186  *
 187  * (3) prev, !this: We're iterating at the last element.
 188  *
 189  * (4) prev, this: this is the most common case, we'll try to find a hole
 190  * between "prev" and "this" mapping.
 191  *
 192  * Note that this function assumes the last valid iova is HWADDR_MAX, but it
 193  * searches linearly so it's easy to discard the result if it's not the case.
 194  */
 195 static void iova_tree_alloc_map_in_hole(struct IOVATreeAllocArgs *args)
 196 {
 197     const DMAMap *prev = args->prev, *this = args->this;
 198     uint64_t hole_start, hole_last;
 199
 200     if (this && this->iova + this->size < args->iova_begin) {
 201         return;
 202     }
 203
 204     hole_start = MAX(prev ? prev->iova + prev->size + 1 : 0, args->iova_begin);
 205     hole_last = this ? this->iova : HWADDR_MAX;
 206
 207     if (hole_last - hole_start > args->new_size) {
 208         args->iova_result = hole_start;
 209         args->iova_found = true;
 210     }
 211 }
 212
 213 /**
 214  * Foreach dma node in the tree, compare if there is a hole with its previous
 215  * node (or minimum iova address allowed) and the node.
 216  *
 217  * @key: Node iterating
 218  * @value: Node iterating
 219  * @pargs: Struct to communicate with the outside world
 220  *
 221  * Return: false to keep iterating, true if needs break.
 222  */
 223 static gboolean iova_tree_alloc_traverse(gpointer key, gpointer value,
 224                                          gpointer pargs)
 225 {
 226     struct IOVATreeAllocArgs *args = pargs;
 227     DMAMap *node = value;
 228
 229     assert(key == value);
 230
 231     iova_tree_alloc_args_iterate(args, node);
 232     iova_tree_alloc_map_in_hole(args);
 233     return args->iova_found;
 234 }
 235
 236 int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
 237                         hwaddr iova_last)
 238 {
 239     struct IOVATreeAllocArgs args = {
 240         .new_size = map->size,
 241         .iova_begin = iova_begin,
 242     };
 243
 244     if (unlikely(iova_last < iova_begin)) {
 245         return IOVA_ERR_INVALID;
 246     }
 247
 248     /*
 249      * Find a valid hole for the mapping
 250      *
 251      * Assuming low iova_begin, so no need to do a binary search to
 252      * locate the first node.
 253      *
 254      * TODO: Replace all this with g_tree_node_first/next/last when available
 255      * (from glib since 2.68). To do it with g_tree_foreach complicates the
 256      * code a lot.
 257      *
 258      */
 259     g_tree_foreach(tree->tree, iova_tree_alloc_traverse, &args);
 260     if (!args.iova_found) {
 261         /*
 262          * Either tree is empty or the last hole is still not checked.
 263          * g_tree_foreach does not compare (last, iova_last] range, so we check
 264          * it here.
 265          */
 266         iova_tree_alloc_args_iterate(&args, NULL);
 267         iova_tree_alloc_map_in_hole(&args);
 268     }
 269
 270     if (!args.iova_found || args.iova_result + map->size > iova_last) {
 271         return IOVA_ERR_NOMEM;
 272     }
 273
 274     map->iova = args.iova_result;
 275     return iova_tree_insert(tree, map);
 276 }
 277
 278 void iova_tree_destroy(IOVATree *tree)
 279 {
 280     g_tree_destroy(tree->tree);
 281     g_free(tree);
 282 }