LXR qemu/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
  33typedef struct IOVATree IOVATree;
  34typedef struct DMAMap {
  35    hwaddr iova;
  36    hwaddr translated_addr;
  37    hwaddr size;                /* Inclusive */
  38    IOMMUAccessFlags perm;
  39} QEMU_PACKED DMAMap;
  40typedef 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 */
  49IOVATree *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 */
  62int 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 */
  77int 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 */
  95DMAMap *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 */
 108DMAMap *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 */
 120void 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 */
 131void iova_tree_destroy(IOVATree *tree);
 132
 133#endif
 134