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