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 "qemu/osdep.h"
  27 #include "exec/memory.h"
  28 #include "exec/hwaddr.h"
  29
  30 #define  IOVA_OK           (0)
  31 #define  IOVA_ERR_INVALID  (-1) /* Invalid parameters */
  32 #define  IOVA_ERR_OVERLAP  (-2) /* IOVA range overlapped */
  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, 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  * Return: 0 if succeeded, or <0 if error.
  77  */
  78 int iova_tree_remove(IOVATree *tree, DMAMap *map);
  79
  80 /**
  81  * iova_tree_find:
  82  *
  83  * @tree: the iova tree to search from
  84  * @map: the mapping to search
  85  *
  86  * Search for a mapping in the iova tree that overlaps with the
  87  * mapping range specified.  Only the first found mapping will be
  88  * returned.
  89  *
  90  * Return: DMAMap pointer if found, or NULL if not found.  Note that
  91  * the returned DMAMap pointer is maintained internally.  User should
  92  * only read the content but never modify or free the content.  Also,
  93  * user is responsible to make sure the pointer is valid (say, no
  94  * concurrent deletion in progress).
  95  */
  96 DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map);
  97
  98 /**
  99  * iova_tree_find_address:
 100  *
 101  * @tree: the iova tree to search from
 102  * @iova: the iova address to find
 103  *
 104  * Similar to iova_tree_find(), but it tries to find mapping with
 105  * range iova=iova & size=0.
 106  *
 107  * Return: same as iova_tree_find().
 108  */
 109 DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova);
 110
 111 /**
 112  * iova_tree_foreach:
 113  *
 114  * @tree: the iova tree to iterate on
 115  * @iterator: the interator for the mappings, return true to stop
 116  *
 117  * Iterate over the iova tree.
 118  *
 119  * Return: 1 if found any overlap, 0 if not, <0 if error.
 120  */
 121 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator);
 122
 123 /**
 124  * iova_tree_destroy:
 125  *
 126  * @tree: the iova tree to destroy
 127  *
 128  * Destroy an existing iova tree.
 129  *
 130  * Return: None.
 131  */
 132 void iova_tree_destroy(IOVATree *tree);
 133
 134 #endif