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 int iova_tree_remove(IOVATree *tree, const 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     return IOVA_OK;
 176 }
 177
 178 /**
 179  * Try to find an unallocated IOVA range between prev and this elements.
 180  *
 181  * @args: Arguments to allocation
 182  *
 183  * Cases:
 184  *
 185  * (1) !prev, !this: No entries allocated, always succeed
 186  *
 187  * (2) !prev, this: We're iterating at the 1st element.
 188  *
 189  * (3) prev, !this: We're iterating at the last element.
 190  *
 191  * (4) prev, this: this is the most common case, we'll try to find a hole
 192  * between "prev" and "this" mapping.
 193  *
 194  * Note that this function assumes the last valid iova is HWADDR_MAX, but it
 195  * searches linearly so it's easy to discard the result if it's not the case.
 196  */
 197 static void iova_tree_alloc_map_in_hole(struct IOVATreeAllocArgs *args)
 198 {
 199     const DMAMap *prev = args->prev, *this = args->this;
 200     uint64_t hole_start, hole_last;
 201
 202     if (this && this->iova + this->size < args->iova_begin) {
 203         return;
 204     }
 205
 206     hole_start = MAX(prev ? prev->iova + prev->size + 1 : 0, args->iova_begin);
 207     hole_last = this ? this->iova : HWADDR_MAX;
 208
 209     if (hole_last - hole_start > args->new_size) {
 210         args->iova_result = hole_start;
 211         args->iova_found = true;
 212     }
 213 }
 214
 215 /**
 216  * Foreach dma node in the tree, compare if there is a hole with its previous
 217  * node (or minimum iova address allowed) and the node.
 218  *
 219  * @key: Node iterating
 220  * @value: Node iterating
 221  * @pargs: Struct to communicate with the outside world
 222  *
 223  * Return: false to keep iterating, true if needs break.
 224  */
 225 static gboolean iova_tree_alloc_traverse(gpointer key, gpointer value,
 226                                          gpointer pargs)
 227 {
 228     struct IOVATreeAllocArgs *args = pargs;
 229     DMAMap *node = value;
 230
 231     assert(key == value);
 232
 233     iova_tree_alloc_args_iterate(args, node);
 234     iova_tree_alloc_map_in_hole(args);
 235     return args->iova_found;
 236 }
 237
 238 int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
 239                         hwaddr iova_last)
 240 {
 241     struct IOVATreeAllocArgs args = {
 242         .new_size = map->size,
 243         .iova_begin = iova_begin,
 244     };
 245
 246     if (unlikely(iova_last < iova_begin)) {
 247         return IOVA_ERR_INVALID;
 248     }
 249
 250     /*
 251      * Find a valid hole for the mapping
 252      *
 253      * Assuming low iova_begin, so no need to do a binary search to
 254      * locate the first node.
 255      *
 256      * TODO: Replace all this with g_tree_node_first/next/last when available
 257      * (from glib since 2.68). To do it with g_tree_foreach complicates the
 258      * code a lot.
 259      *
 260      */
 261     g_tree_foreach(tree->tree, iova_tree_alloc_traverse, &args);
 262     if (!args.iova_found) {
 263         /*
 264          * Either tree is empty or the last hole is still not checked.
 265          * g_tree_foreach does not compare (last, iova_last] range, so we check
 266          * it here.
 267          */
 268         iova_tree_alloc_args_iterate(&args, NULL);
 269         iova_tree_alloc_map_in_hole(&args);
 270     }
 271
 272     if (!args.iova_found || args.iova_result + map->size > iova_last) {
 273         return IOVA_ERR_NOMEM;
 274     }
 275
 276     map->iova = args.iova_result;
 277     return iova_tree_insert(tree, map);
 278 }
 279
 280 void iova_tree_destroy(IOVATree *tree)
 281 {
 282     g_tree_destroy(tree->tree);
 283     g_free(tree);
 284 }