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, Universitaetstrasse 6, 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 170errval_t mdb_size(size_t *count); 171 172__END_DECLS 173 174#endif // LIBMDB_MDB_TREE_H 175