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 static inline void iova_tree_insert_internal(GTree *gtree, DMAMap *range)
 119 {
 120     /* Key and value are sharing the same range data */
 121     g_tree_insert(gtree, range, range);
 122 }
 123
 124 int iova_tree_insert(IOVATree *tree, const DMAMap *map)
 125 {
 126     DMAMap *new;
 127
 128     if (map->iova + map->size < map->iova || map->perm == IOMMU_NONE) {
 129         return IOVA_ERR_INVALID;
 130     }
 131
 132     /* We don't allow to insert range that overlaps with existings */
 133     if (iova_tree_find(tree, map)) {
 134         return IOVA_ERR_OVERLAP;
 135     }
 136
 137     new = g_new0(DMAMap, 1);
 138     memcpy(new, map, sizeof(*new));
 139     iova_tree_insert_internal(tree->tree, new);
 140
 141     return IOVA_OK;
 142 }
 143
 144 void iova_tree_remove(IOVATree *tree, DMAMap map)
 145 {
 146     const DMAMap *overlap;
 147
 148     while ((overlap = iova_tree_find(tree, &map))) {
 149         g_tree_remove(tree->tree, overlap);
 150     }
 151 }
 152
 153 /**
 154  * Try to find an unallocated IOVA range between prev and this elements.
 155  *
 156  * @args: Arguments to allocation
 157  *
 158  * Cases:
 159  *
 160  * (1) !prev, !this: No entries allocated, always succeed
 161  *
 162  * (2) !prev, this: We're iterating at the 1st element.
 163  *
 164  * (3) prev, !this: We're iterating at the last element.
 165  *
 166  * (4) prev, this: this is the most common case, we'll try to find a hole
 167  * between "prev" and "this" mapping.
 168  *
 169  * Note that this function assumes the last valid iova is HWADDR_MAX, but it
 170  * searches linearly so it's easy to discard the result if it's not the case.
 171  */
 172 static void iova_tree_alloc_map_in_hole(struct IOVATreeAllocArgs *args)
 173 {
 174     const DMAMap *prev = args->prev, *this = args->this;
 175     uint64_t hole_start, hole_last;
 176
 177     if (this && this->iova + this->size < args->iova_begin) {
 178         return;
 179     }
 180
 181     hole_start = MAX(prev ? prev->iova + prev->size + 1 : 0, args->iova_begin);
 182     hole_last = this ? this->iova : HWADDR_MAX;
 183
 184     if (hole_last - hole_start > args->new_size) {
 185         args->iova_result = hole_start;
 186         args->iova_found = true;
 187     }
 188 }
 189
 190 /**
 191  * Foreach dma node in the tree, compare if there is a hole with its previous
 192  * node (or minimum iova address allowed) and the node.
 193  *
 194  * @key: Node iterating
 195  * @value: Node iterating
 196  * @pargs: Struct to communicate with the outside world
 197  *
 198  * Return: false to keep iterating, true if needs break.
 199  */
 200 static gboolean iova_tree_alloc_traverse(gpointer key, gpointer value,
 201                                          gpointer pargs)
 202 {
 203     struct IOVATreeAllocArgs *args = pargs;
 204     DMAMap *node = value;
 205
 206     assert(key == value);
 207
 208     iova_tree_alloc_args_iterate(args, node);
 209     iova_tree_alloc_map_in_hole(args);
 210     return args->iova_found;
 211 }
 212
 213 int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
 214                         hwaddr iova_last)
 215 {
 216     struct IOVATreeAllocArgs args = {
 217         .new_size = map->size,
 218         .iova_begin = iova_begin,
 219     };
 220
 221     if (unlikely(iova_last < iova_begin)) {
 222         return IOVA_ERR_INVALID;
 223     }
 224
 225     /*
 226      * Find a valid hole for the mapping
 227      *
 228      * Assuming low iova_begin, so no need to do a binary search to
 229      * locate the first node.
 230      *
 231      * TODO: Replace all this with g_tree_node_first/next/last when available
 232      * (from glib since 2.68). To do it with g_tree_foreach complicates the
 233      * code a lot.
 234      *
 235      */
 236     g_tree_foreach(tree->tree, iova_tree_alloc_traverse, &args);
 237     if (!args.iova_found) {
 238         /*
 239          * Either tree is empty or the last hole is still not checked.
 240          * g_tree_foreach does not compare (last, iova_last] range, so we check
 241          * it here.
 242          */
 243         iova_tree_alloc_args_iterate(&args, NULL);
 244         iova_tree_alloc_map_in_hole(&args);
 245     }
 246
 247     if (!args.iova_found || args.iova_result + map->size > iova_last) {
 248         return IOVA_ERR_NOMEM;
 249     }
 250
 251     map->iova = args.iova_result;
 252     return iova_tree_insert(tree, map);
 253 }
 254
 255 void iova_tree_destroy(IOVATree *tree)
 256 {
 257     g_tree_destroy(tree->tree);
 258     g_free(tree);
 259 }