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
  33 typedef struct IOVATree IOVATree;
  34 typedef struct DMAMap {
  35     hwaddr iova;
  36     hwaddr translated_addr;
  37     hwaddr size;                /* Inclusive */
  38     IOMMUAccessFlags perm;
  39 } QEMU_PACKED DMAMap;
  40 typedef gboolean (*iova_tree_iterator)(DMAMap *map);
  41
  42 /**
  43  * iova_tree_new:
  44  *
  45  * Create a new iova tree.
  46  *
  47  * Returns: the tree pointer when succeeded, or NULL if error.
  48  */
  49 IOVATree *iova_tree_new(void);
  50
  51 /**
  52  * iova_tree_insert:
  53  *
  54  * @tree: the iova tree to insert
  55  * @map: the mapping to insert
  56  *
  57  * Insert an iova range to the tree.  If there is overlapped
  58  * ranges, IOVA_ERR_OVERLAP will be returned.
  59  *
  60  * Return: 0 if succeeded, or <0 if error.
  61  */
  62 int iova_tree_insert(IOVATree *tree, DMAMap *map);
  63
  64 /**
  65  * iova_tree_remove:
  66  *
  67  * @tree: the iova tree to remove range from
  68  * @map: the map range to remove
  69  *
  70  * Remove mappings from the tree that are covered by the map range
  71  * provided.  The range does not need to be exactly what has inserted,
  72  * all the mappings that are included in the provided range will be
  73  * removed from the tree.  Here map->translated_addr is meaningless.
  74  *
  75  * Return: 0 if succeeded, or <0 if error.
  76  */
  77 int iova_tree_remove(IOVATree *tree, DMAMap *map);
  78
  79 /**
  80  * iova_tree_find:
  81  *
  82  * @tree: the iova tree to search from
  83  * @map: the mapping to search
  84  *
  85  * Search for a mapping in the iova tree that overlaps with the
  86  * mapping range specified.  Only the first found mapping will be
  87  * returned.
  88  *
  89  * Return: DMAMap pointer if found, or NULL if not found.  Note that
  90  * the returned DMAMap pointer is maintained internally.  User should
  91  * only read the content but never modify or free the content.  Also,
  92  * user is responsible to make sure the pointer is valid (say, no
  93  * concurrent deletion in progress).
  94  */
  95 DMAMap *iova_tree_find(IOVATree *tree, DMAMap *map);
  96
  97 /**
  98  * iova_tree_find_address:
  99  *
 100  * @tree: the iova tree to search from
 101  * @iova: the iova address to find
 102  *
 103  * Similar to iova_tree_find(), but it tries to find mapping with
 104  * range iova=iova & size=0.
 105  *
 106  * Return: same as iova_tree_find().
 107  */
 108 DMAMap *iova_tree_find_address(IOVATree *tree, hwaddr iova);
 109
 110 /**
 111  * iova_tree_foreach:
 112  *
 113  * @tree: the iova tree to iterate on
 114  * @iterator: the interator for the mappings, return true to stop
 115  *
 116  * Iterate over the iova tree.
 117  *
 118  * Return: 1 if found any overlap, 0 if not, <0 if error.
 119  */
 120 void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator);
 121
 122 /**
 123  * iova_tree_destroy:
 124  *
 125  * @tree: the iova tree to destroy
 126  *
 127  * Destroy an existing iova tree.
 128  *
 129  * Return: None.
 130  */
 131 void iova_tree_destroy(IOVATree *tree);
 132
 133 #endif