include/qemu/iova-tree.h

   1 /*
   2  * An very simplified 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 #ifndef IOVA_TREE_H
  12 #define IOVA_TREE_H
  13
  14 /*
  15  * Currently the iova tree will only allow to keep ranges
  16  * information, and no extra user data is allowed for each element.  A
  17  * benefit is that we can merge adjacent ranges internally within the
  18  * tree.  It can save a lot of memory when the ranges are splitted but
  19  * mostly continuous.
  20  *
  21  * Note that current implementation does not provide any thread
  22  * protections.  Callers of the iova tree should be responsible
  23  * for the thread safety issue.
  24  */
  25
  26 #include "exec/memory.h"
  27 #include "exec/hwaddr.h"
  28
  29 #define  IOVA_OK           (0)
  30 #define  IOVA_ERR_INVALID  (-1) /* Invalid parameters */
  31 #define  IOVA_ERR_OVERLAP  (-2) /* IOVA range overlapped */
  32 #define  IOVA_ERR_NOMEM    (-3) /* Cannot allocate */
  33
  34 typedef struct IOVATree IOVATree;
  35 typedef struct DMAMap {
  36     hwaddr iova;
  37     hwaddr translated_addr;
  38     hwaddr size;                /* Inclusive */
  39     IOMMUAccessFlags perm;
  40 } QEMU_PACKED DMAMap;
  41 typedef gboolean (*iova_tree_iterator)(DMAMap *map);
  42
  43 /**
  44  * iova_tree_new:
  45  *
  46  * Create a new iova tree.
  47  *
  48  * Returns: the tree pointer when succeeded, or NULL if error.
  49  */
  50 IOVATree *iova_tree_new(void);
  51
  52 /**
  53  * iova_tree_insert:
  54  *
  55  * @tree: the iova tree to insert
  56  * @map: the mapping to insert
  57  *
  58  * Insert an iova range to the tree.  If there is overlapped
  59  * ranges, IOVA_ERR_OVERLAP will be returned.
  60  *
  61  * Return: 0 if succeeded, or <0 if error.
  62  */
  63 int iova_tree_insert(IOVATree *tree, const DMAMap *map);
  64
  65 /**
  66  * iova_tree_remove:
  67  *
  68  * @tree: the iova tree to remove range from
  69  * @map: the map range to remove
  70  *
  71  * Remove mappings from the tree that are covered by the map range
  72  * provided.  The range does not need to be exactly what has inserted,
  73  * all the mappings that are included in the provided range will be
  74  * removed from the tree.  Here map->translated_addr is meaningless.
  75  */
  76 void iova_tree_remove(IOVATree *tree, DMAMap map);
  77
  78 /**
  79  * iova_tree_find:
  80  *
  81  * @tree: the iova tree to search from
  82  * @map: the mapping to search
  83  *
  84  * Search for a mapping in the iova tree that iova overlaps with the
  85  * mapping range specified.  Only the first found mapping will be
  86  * returned.
  87  *
  88  * Return: DMAMap pointer if found, or NULL if not found.  Note that
  89  * the returned DMAMap pointer is maintained internally.  User should
  90  * only read the content but never modify or free the content.  Also,
  91  * user is responsible to make sure the pointer is valid (say, no
  92  * concurrent deletion in progress).
  93  */
  94 const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map);
  95
  96 /**
  97  * iova_tree_find_iova:
  98  *
  99  * @tree: the iova tree to search from
 100  * @map: the mapping to search
 101  *
 102  * Search for a mapping in the iova tree that translated_addr overlaps with the
 103  * mapping range specified.  Only the first found mapping will be
 104  * returned.
 105  *
 106  * Return: DMAMap pointer if found, or NULL if not found.  Note that
 107  * the returned DMAMap pointer is maintained internally.  User should
 108  * only read the content but never modify or free the content.  Also,
 109  * user is responsible to make sure the pointer is valid (say, no
 110  * concurrent deletion in progress).
 111  */
 112 const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map);
 113
 114 /**
 115  * iova_tree_find_address:
 116  *
 117  * @tree: the iova tree to search from
 118  * @iova: the iova address to find
 119  *
 120  * Similar to iova_tree_find(), but it tries to find mapping with
 121  * range iova=iova & size=0.
 122  *
 123  * Return: same as iova_tree_find().
 124  */
 125 const DMAMap *iova_tree_find_address(const IOVATree *tree, hwaddr iova);
 126
 127 /**
 128  * iova_tree_foreach:
 129  *
 130  * @tree: the iova tree to iterate on
 131  * @iterator: the interator for the mappings, return true to stop
 132  *
 133  * Iterate over the iova tree.
 134  *
 135  * Return: 1 if found any overlap, 0 if not, <0 if error.
 136  */
 137 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator);
 138
 139 /**
 140  * iova_tree_alloc_map:
 141  *
 142  * @tree: the iova tree to allocate from
 143  * @map: the new map (as translated addr & size) to allocate in the iova region
 144  * @iova_begin: the minimum address of the allocation
 145  * @iova_end: the maximum addressable direction of the allocation
 146  *
 147  * Allocates a new region of a given size, between iova_min and iova_max.
 148  *
 149  * Return: Same as iova_tree_insert, but cannot overlap and can return error if
 150  * iova tree is out of free contiguous range. The caller gets the assigned iova
 151  * in map->iova.
 152  */
 153 int iova_tree_alloc_map(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
 154                         hwaddr iova_end);
 155
 156 /**
 157  * iova_tree_destroy:
 158  *
 159  * @tree: the iova tree to destroy
 160  *
 161  * Destroy an existing iova tree.
 162  *
 163  * Return: None.
 164  */
 165 void iova_tree_destroy(IOVATree *tree);
 166
 167 #endif