1/*
2 * Copyright (c) 2012, ETH Zurich.
3 * All rights reserved.
4 *
5 * This file is distributed under the terms in the attached LICENSE file.
6 * If you do not find this file, copies can be found by writing to:
7 * ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
8 */
9
10#ifndef LIBMDB_MDB_TREE_H
11#define LIBMDB_MDB_TREE_H
12
13#include <sys/cdefs.h>
14
15#include <errors/errno.h>
16#include <barrelfish/types.h>
17#include <mdb/types.h>
18
19__BEGIN_DECLS
20
21struct capability;
22struct cte;
23
24#define mdb_invariants(f) \
25    /* All checked invariants hold*/\
26    f(MDB_INVARIANT_OK) \
27    /* A node with level > 0 must have both children*/\
28    f(MDB_INVARIANT_BOTHCHILDREN) \
29    /* The level of a node's left child must be lt the node's level*/\
30    f(MDB_INVARIANT_LEFT_LEVEL_LESS) \
31    /* The level of a node's right child must be leq the node's level*/\
32    f(MDB_INVARIANT_RIGHT_LEVEL_LEQ) \
33    /* The level of a node's right grandchildren must bt lt the node's level*/\
34    f(MDB_INVARIANT_RIGHTRIGHT_LEVEL_LESS) \
35    f(MDB_INVARIANT_RIGHTLEFT_LEVEL_LESS) \
36    /* The node's "end" value must be the maximum of the subtree's ends*/\
37    f(MDB_INVARIANT_END_IS_MAX) \
38    /* The left child of a node must be earlier in the ordering*/\
39    f(MDB_INVARIANT_LEFT_SMALLER) \
40    /* The right child of a node must be later in the ordering*/\
41    f(MDB_INVARIANT_RIGHT_GREATER)
42
43#define f_enum(x) x,
44enum mdb_invariant {
45    mdb_invariants(f_enum)
46};
47#undef f_enum
48
49#define f_str(x) #x,
50static const char *mdb_invariant_str[] = { mdb_invariants(f_str) };
51#undef f_str
52
53#undef mdb_invariants
54
55static inline const char *mdb_invariant_to_str(enum mdb_invariant i)
56{
57    return mdb_invariant_str[i];
58}
59
60enum {
61    // No cap was found covering the specified region
62    MDB_RANGE_NOT_FOUND = 0,
63    // A cap was found covering at least the entire specified region
64    MDB_RANGE_FOUND_SURROUNDING = 1,
65    // A cap was found that is inside the specified region
66    MDB_RANGE_FOUND_INNER = 2,
67    // A cap was found that overlaps with one of the specified region's ends
68    MDB_RANGE_FOUND_PARTIAL = 3,
69};
70
71#if IN_KERNEL
72// kcb defined else-where
73struct kcb;
74#else
75// create mini kcb that can be used to set root node in user space mdb
76struct kcb {
77    lvaddr_t mdb_root;
78};
79#endif
80
81// Restore mdb state by passing in the address of the root node
82// requires: mdb not initialized
83// ensures: mdb_check_invariants() && mdb_is_sane()
84errval_t mdb_init(struct kcb *k);
85
86// Print the specified subtree
87void mdb_dump(struct cte *cte, int indent);
88// Print the complete tree
89void mdb_dump_all_the_things(void);
90// Check that the invariants hold. The return value indicates the first issue
91// that was encountered.
92int mdb_check_invariants(void);
93
94// Insert a cap into the tree. An error (MDB_DUPLICATE_ENTRY) is returned iff
95// the cap is already present in the tree.
96errval_t mdb_insert(struct cte *new_node);
97// Remove a cap from the tree. An error (MDB_ENTRY_NOTFOUND) is returned iff
98// the cap is not present in the tree.
99errval_t mdb_remove(struct cte *node);
100
101struct cte *mdb_predecessor(struct cte *current);
102struct cte *mdb_successor(struct cte *current);
103
104// Find a cap in the tree that compares equal to the given cap. Returns NULL if
105// no such cap is found.
106struct cte *mdb_find_equal(struct capability *cap);
107// Find the greatest cap in the tree that is earlier in the ordering. Returns
108// NULL if no matching cap is found.
109// @param equal_ok If true, will return a copy of the passed cap if it is
110//        present.
111struct cte *mdb_find_less(struct capability *cap, bool equal_ok);
112// Find the smallest cap in the tree that is later in the ordering. Returns
113// NULL if no matching cap is found.
114// @param equal_ok If true, will return a copy of the passed cap if it is
115//        present.
116struct cte *mdb_find_greater(struct capability *cap, bool equal_ok);
117
118// Find a cap in the given range.
119// @param root indicates which type tree root to search through (usually
120//        `get_type_root(ObjType_PhysAddr)`).
121// @param max_result Indicates the maximum outcome (not found, surrounding...)
122//        for which a cap should be returned. If an result is found that is
123//        greater than max_result, this function returns immediately with the
124//        given result and NULL cte. The semantics/uses for individual
125//        max_result values are thus:
126//        - MDB_RANGE_NOT_FOUND: A simple test whether the given region is
127//          covered by a cap.
128//        - MDB_RANGE_FOUND_SURROUNDING: Can be used to check if a region can
129//          be retyped.
130//        - MDB_RANGE_FOUND_INNER: Useful for iterating through *immediate*
131//          descendants.
132errval_t mdb_find_range(mdb_root_t root, genpaddr_t address, gensize_t size,
133                        int max_result, struct cte **ret_node, int *result);
134
135errval_t mdb_find_cap_for_address(genpaddr_t address, struct cte **ret_node);
136
137bool mdb_reachable(struct cte *cte);
138
139/**
140 * Call-back function for tree traversals.
141 * @param cte The current tree entry.
142 * @param data User provided data pointer.
143 */
144typedef errval_t (*mdb_tree_traversal_fn)(struct cte *cte, void *data);
145
146enum mdb_tree_traversal_order {
147    MDB_TRAVERSAL_ORDER_ASCENDING, ///< Traverse the tree in ascending order
148    MDB_TRAVERSAL_ORDER_DESCENDING ///< Traverse the tree in descending order
149};
150
151/**
152 * Traverse the mdb tree using some order with a call-back function and
153 * user-provided data. This function starts at the root of the tree.
154 * @param order The order to traverse the tree in.
155 * @param cb The call-back to execute for every node in the tree.
156 * @parm data User-provided data pointer.
157 */
158errval_t mdb_traverse(enum mdb_tree_traversal_order order, mdb_tree_traversal_fn cb, void *data);
159
160/**
161 * Traverse an mdb sub tree using some order with a call-back function and
162 * user-provided data.
163 * @param cte The subtree to traverse. The call-back will be executed on this node.
164 * @param order The order to traverse the tree in.
165 * @param cb The call-back to execute for every node in the tree.
166 * @parm data User-provided data pointer.
167 */
168errval_t mdb_traverse_subtree(struct cte *cte, enum mdb_tree_traversal_order order, mdb_tree_traversal_fn cb, void *data);
169
170__END_DECLS
171
172#endif // LIBMDB_MDB_TREE_H
173