Index: kernel/generic/src/adt/btree.c =================================================================== --- kernel/generic/src/adt/btree.c (revision b5382d4f551b38012fe4db27dd79c095f5e09706) +++ kernel/generic/src/adt/btree.c (revision cefb126edea34b0dd89c1d23a3945eba732448c8) @@ -33,5 +33,5 @@ /** * @file - * @brief B+tree implementation. + * @brief B+tree implementation. * * This file implements B+tree type and operations. @@ -54,39 +54,48 @@ #include -static void btree_destroy_subtree(btree_node_t *root); -static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node); -static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node); -static void node_initialize(btree_node_t *node); -static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree); -static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree); -static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key); -static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key); -static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median); -static btree_node_t *node_combine(btree_node_t *node); -static size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right); -static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx); -static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx); -static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree); -static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree); -static bool try_rotation_from_left(btree_node_t *rnode); -static bool try_rotation_from_right(btree_node_t *lnode); - -#define ROOT_NODE(n) (!(n)->parent) -#define INDEX_NODE(n) ((n)->subtree[0] != NULL) -#define LEAF_NODE(n) ((n)->subtree[0] == NULL) - -#define FILL_FACTOR ((BTREE_M-1)/2) - -#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2) -#define MEDIAN_HIGH_INDEX(n) ((n)->keys/2) -#define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]); -#define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]); - static slab_cache_t *btree_node_slab; + +#define ROOT_NODE(n) (!(n)->parent) +#define INDEX_NODE(n) ((n)->subtree[0] != NULL) +#define LEAF_NODE(n) ((n)->subtree[0] == NULL) + +#define FILL_FACTOR ((BTREE_M - 1) / 2) + +#define MEDIAN_LOW_INDEX(n) (((n)->keys-1) / 2) +#define MEDIAN_HIGH_INDEX(n) ((n)->keys / 2) +#define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]); +#define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]); /** Initialize B-trees. */ void btree_init(void) { - btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); + btree_node_slab = slab_cache_create("btree_node_slab", + sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); +} + +/** Initialize B-tree node. + * + * @param node B-tree node. + * + */ +static void node_initialize(btree_node_t *node) +{ + unsigned int i; + + node->keys = 0; + + /* Clean also space for the extra key. */ + for (i = 0; i < BTREE_MAX_KEYS + 1; i++) { + node->key[i] = 0; + node->value[i] = NULL; + node->subtree[i] = NULL; + } + + node->subtree[i] = NULL; + node->parent = NULL; + + link_initialize(&node->leaf_link); + link_initialize(&node->bfs_link); + node->depth = 0; } @@ -94,4 +103,5 @@ * * @param t B-tree. + * */ void btree_create(btree_t *t) @@ -103,41 +113,13 @@ } -/** Destroy empty B-tree. */ -void btree_destroy(btree_t *t) -{ - btree_destroy_subtree(t->root); -} - -/** Insert key-value pair into B-tree. - * - * @param t B-tree. - * @param key Key to be inserted. - * @param value Value to be inserted. - * @param leaf_node Leaf node where the insertion should begin. - */ -void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node) -{ - btree_node_t *lnode; - - ASSERT(value); - - lnode = leaf_node; - if (!lnode) { - if (btree_search(t, key, &lnode)) { - panic("B-tree %p already contains key %" PRIu64 ".", t, key); - } - } - - _btree_insert(t, key, value, NULL, lnode); -} - /** Destroy subtree rooted in a node. * * @param root Root of the subtree. - */ -void btree_destroy_subtree(btree_node_t *root) + * + */ +static void btree_destroy_subtree(btree_node_t *root) { size_t i; - + if (root->keys) { for (i = 0; i < root->keys + 1; i++) { @@ -146,16 +128,430 @@ } } + slab_free(btree_node_slab, root); } +/** Destroy empty B-tree. */ +void btree_destroy(btree_t *t) +{ + btree_destroy_subtree(t->root); +} + +/** Insert key-value-rsubtree triplet into B-tree node. + * + * It is actually possible to have more keys than BTREE_MAX_KEYS. + * This feature is used during splitting the node when the + * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation + * also makes use of this feature. + * + * @param node B-tree node into wich the new key is to be inserted. + * @param key The key to be inserted. + * @param value Pointer to value to be inserted. + * @param rsubtree Pointer to the right subtree. + * + */ +static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, + void *value, btree_node_t *rsubtree) +{ + size_t i; + + for (i = 0; i < node->keys; i++) { + if (key < node->key[i]) { + size_t j; + + for (j = node->keys; j > i; j--) { + node->key[j] = node->key[j - 1]; + node->value[j] = node->value[j - 1]; + node->subtree[j + 1] = node->subtree[j]; + } + + break; + } + } + + node->key[i] = key; + node->value[i] = value; + node->subtree[i + 1] = rsubtree; + node->keys++; +} + +/** Find key by its left or right subtree. + * + * @param node B-tree node. + * @param subtree Left or right subtree of a key found in node. + * @param right If true, subtree is a right subtree. If false, + * subtree is a left subtree. + * + * @return Index of the key associated with the subtree. + * + */ +static size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, + bool right) +{ + size_t i; + + for (i = 0; i < node->keys + 1; i++) { + if (subtree == node->subtree[i]) + return i - (int) (right != false); + } + + panic("Node %p does not contain subtree %p.", node, subtree); +} + +/** Remove key and its left subtree pointer from B-tree node. + * + * Remove the key and eliminate gaps in node->key array. + * Note that the value pointer and the left subtree pointer + * is removed from the node as well. + * + * @param node B-tree node. + * @param key Key to be removed. + * + */ +static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key) +{ + size_t i; + size_t j; + + for (i = 0; i < node->keys; i++) { + if (key == node->key[i]) { + for (j = i + 1; j < node->keys; j++) { + node->key[j - 1] = node->key[j]; + node->value[j - 1] = node->value[j]; + node->subtree[j - 1] = node->subtree[j]; + } + + node->subtree[j - 1] = node->subtree[j]; + node->keys--; + + return; + } + } + + panic("Node %p does not contain key %" PRIu64 ".", node, key); +} + +/** Remove key and its right subtree pointer from B-tree node. + * + * Remove the key and eliminate gaps in node->key array. + * Note that the value pointer and the right subtree pointer + * is removed from the node as well. + * + * @param node B-tree node. + * @param key Key to be removed. + * + */ +static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key) +{ + size_t i, j; + + for (i = 0; i < node->keys; i++) { + if (key == node->key[i]) { + for (j = i + 1; j < node->keys; j++) { + node->key[j - 1] = node->key[j]; + node->value[j - 1] = node->value[j]; + node->subtree[j] = node->subtree[j + 1]; + } + + node->keys--; + return; + } + } + + panic("Node %p does not contain key %" PRIu64 ".", node, key); +} + +/** Insert key-value-lsubtree triplet into B-tree node. + * + * It is actually possible to have more keys than BTREE_MAX_KEYS. + * This feature is used during insert by right rotation. + * + * @param node B-tree node into wich the new key is to be inserted. + * @param key The key to be inserted. + * @param value Pointer to value to be inserted. + * @param lsubtree Pointer to the left subtree. + * + */ +static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, + void *value, btree_node_t *lsubtree) +{ + size_t i; + + for (i = 0; i < node->keys; i++) { + if (key < node->key[i]) { + size_t j; + + for (j = node->keys; j > i; j--) { + node->key[j] = node->key[j - 1]; + node->value[j] = node->value[j - 1]; + node->subtree[j + 1] = node->subtree[j]; + } + + node->subtree[j + 1] = node->subtree[j]; + break; + } + } + + node->key[i] = key; + node->value[i] = value; + node->subtree[i] = lsubtree; + + node->keys++; +} + +/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling. + * + * The biggest key and its value and right subtree is rotated + * from the left node to the right. If the node is an index node, + * than the parent node key belonging to the left node takes part + * in the rotation. + * + * @param lnode Left sibling. + * @param rnode Right sibling. + * @param idx Index of the parent node key that is taking part + * in the rotation. + * + */ +static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx) +{ + btree_key_t key = lnode->key[lnode->keys - 1]; + + if (LEAF_NODE(lnode)) { + void *value = lnode->value[lnode->keys - 1]; + + node_remove_key_and_rsubtree(lnode, key); + node_insert_key_and_lsubtree(rnode, key, value, NULL); + lnode->parent->key[idx] = key; + } else { + btree_node_t *rsubtree = lnode->subtree[lnode->keys]; + + node_remove_key_and_rsubtree(lnode, key); + node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree); + lnode->parent->key[idx] = key; + + /* Fix parent link of the reconnected right subtree. */ + rsubtree->parent = rnode; + } +} + +/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling. + * + * The smallest key and its value and left subtree is rotated + * from the right node to the left. If the node is an index node, + * than the parent node key belonging to the right node takes part + * in the rotation. + * + * @param lnode Left sibling. + * @param rnode Right sibling. + * @param idx Index of the parent node key that is taking part + * in the rotation. + * + */ +static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx) +{ + btree_key_t key = rnode->key[0]; + + if (LEAF_NODE(rnode)) { + void *value = rnode->value[0]; + + node_remove_key_and_lsubtree(rnode, key); + node_insert_key_and_rsubtree(lnode, key, value, NULL); + rnode->parent->key[idx] = rnode->key[0]; + } else { + btree_node_t *lsubtree = rnode->subtree[0]; + + node_remove_key_and_lsubtree(rnode, key); + node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree); + rnode->parent->key[idx] = key; + + /* Fix parent link of the reconnected left subtree. */ + lsubtree->parent = lnode; + } +} + +/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done. + * + * Left sibling of the node (if it exists) is checked for free space. + * If there is free space, the key is inserted and the smallest key of + * the node is moved there. The index node which is the parent of both + * nodes is fixed. + * + * @param node B-tree node. + * @param inskey Key to be inserted. + * @param insvalue Value to be inserted. + * @param rsubtree Right subtree of inskey. + * + * @return True if the rotation was performed, false otherwise. + * + */ +static bool try_insert_by_rotation_to_left(btree_node_t *node, + btree_key_t inskey, void *insvalue, btree_node_t *rsubtree) +{ + size_t idx; + btree_node_t *lnode; + + /* + * If this is root node, the rotation can not be done. + */ + if (ROOT_NODE(node)) + return false; + + idx = find_key_by_subtree(node->parent, node, true); + if ((int) idx == -1) { + /* + * If this node is the leftmost subtree of its parent, + * the rotation can not be done. + */ + return false; + } + + lnode = node->parent->subtree[idx]; + if (lnode->keys < BTREE_MAX_KEYS) { + /* + * The rotaion can be done. The left sibling has free space. + */ + node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree); + rotate_from_right(lnode, node, idx); + return true; + } + + return false; +} + +/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done. + * + * Right sibling of the node (if it exists) is checked for free space. + * If there is free space, the key is inserted and the biggest key of + * the node is moved there. The index node which is the parent of both + * nodes is fixed. + * + * @param node B-tree node. + * @param inskey Key to be inserted. + * @param insvalue Value to be inserted. + * @param rsubtree Right subtree of inskey. + * + * @return True if the rotation was performed, false otherwise. + * + */ +static bool try_insert_by_rotation_to_right(btree_node_t *node, + btree_key_t inskey, void *insvalue, btree_node_t *rsubtree) +{ + size_t idx; + btree_node_t *rnode; + + /* + * If this is root node, the rotation can not be done. + */ + if (ROOT_NODE(node)) + return false; + + idx = find_key_by_subtree(node->parent, node, false); + if (idx == node->parent->keys) { + /* + * If this node is the rightmost subtree of its parent, + * the rotation can not be done. + */ + return false; + } + + rnode = node->parent->subtree[idx + 1]; + if (rnode->keys < BTREE_MAX_KEYS) { + /* + * The rotaion can be done. The right sibling has free space. + */ + node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree); + rotate_from_left(node, rnode, idx); + return true; + } + + return false; +} + +/** Split full B-tree node and insert new key-value-right-subtree triplet. + * + * This function will split a node and return a pointer to a newly created + * node containing keys greater than or equal to the greater of medians + * (or median) of the old keys and the newly added key. It will also write + * the median key to a memory address supplied by the caller. + * + * If the node being split is an index node, the median will not be + * included in the new node. If the node is a leaf node, + * the median will be copied there. + * + * @param node B-tree node wich is going to be split. + * @param key The key to be inserted. + * @param value Pointer to the value to be inserted. + * @param rsubtree Pointer to the right subtree of the key being added. + * @param median Address in memory, where the median key will be stored. + * + * @return Newly created right sibling of node. + * + */ +static btree_node_t *node_split(btree_node_t *node, btree_key_t key, + void *value, btree_node_t *rsubtree, btree_key_t *median) +{ + btree_node_t *rnode; + size_t i; + size_t j; + + ASSERT(median); + ASSERT(node->keys == BTREE_MAX_KEYS); + + /* + * Use the extra space to store the extra node. + */ + node_insert_key_and_rsubtree(node, key, value, rsubtree); + + /* + * Compute median of keys. + */ + *median = MEDIAN_HIGH(node); + + /* + * Allocate and initialize new right sibling. + */ + rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0); + node_initialize(rnode); + rnode->parent = node->parent; + rnode->depth = node->depth; + + /* + * Copy big keys, values and subtree pointers to the new right sibling. + * If this is an index node, do not copy the median. + */ + i = (size_t) INDEX_NODE(node); + for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) { + rnode->key[j] = node->key[i]; + rnode->value[j] = node->value[i]; + rnode->subtree[j] = node->subtree[i]; + + /* + * Fix parent links in subtrees. + */ + if (rnode->subtree[j]) + rnode->subtree[j]->parent = rnode; + } + + rnode->subtree[j] = node->subtree[i]; + if (rnode->subtree[j]) + rnode->subtree[j]->parent = rnode; + + rnode->keys = j; /* Set number of keys of the new node. */ + node->keys /= 2; /* Shrink the old node. */ + + return rnode; +} + /** Recursively insert into B-tree. * - * @param t B-tree. - * @param key Key to be inserted. - * @param value Value to be inserted. + * @param t B-tree. + * @param key Key to be inserted. + * @param value Value to be inserted. * @param rsubtree Right subtree of the inserted key. - * @param node Start inserting into this node. - */ -void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node) + * @param node Start inserting into this node. + * + */ +static void _btree_insert(btree_t *t, btree_key_t key, void *value, + btree_node_t *rsubtree, btree_node_t *node) { if (node->keys < BTREE_MAX_KEYS) { @@ -183,7 +579,7 @@ * bigger keys (i.e. the new node) into its parent. */ - + rnode = node_split(node, key, value, rsubtree, &median); - + if (LEAF_NODE(node)) { list_prepend(&rnode->leaf_link, &node->leaf_link); @@ -202,44 +598,174 @@ * Left-hand side subtree will be the old root (i.e. node). * Right-hand side subtree will be rnode. - */ + */ t->root->subtree[0] = node; - + t->root->depth = node->depth + 1; } _btree_insert(t, median, NULL, rnode, node->parent); - } - -} - -/** Remove B-tree node. - * - * @param t B-tree. - * @param key Key to be removed from the B-tree along with its associated value. - * @param leaf_node If not NULL, pointer to the leaf node where the key is found. - */ -void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node) + } +} + +/** Insert key-value pair into B-tree. + * + * @param t B-tree. + * @param key Key to be inserted. + * @param value Value to be inserted. + * @param leaf_node Leaf node where the insertion should begin. + * + */ +void btree_insert(btree_t *t, btree_key_t key, void *value, + btree_node_t *leaf_node) { btree_node_t *lnode; + + ASSERT(value); lnode = leaf_node; if (!lnode) { - if (!btree_search(t, key, &lnode)) { - panic("B-tree %p does not contain key %" PRIu64 ".", t, key); - } - } - - _btree_remove(t, key, lnode); + if (btree_search(t, key, &lnode)) + panic("B-tree %p already contains key %" PRIu64 ".", t, key); + } + + _btree_insert(t, key, value, NULL, lnode); +} + +/** Rotate in a key from the left sibling or from the index node, if this operation can be done. + * + * @param rnode Node into which to add key from its left sibling + * or from the index node. + * + * @return True if the rotation was performed, false otherwise. + * + */ +static bool try_rotation_from_left(btree_node_t *rnode) +{ + size_t idx; + btree_node_t *lnode; + + /* + * If this is root node, the rotation can not be done. + */ + if (ROOT_NODE(rnode)) + return false; + + idx = find_key_by_subtree(rnode->parent, rnode, true); + if ((int) idx == -1) { + /* + * If this node is the leftmost subtree of its parent, + * the rotation can not be done. + */ + return false; + } + + lnode = rnode->parent->subtree[idx]; + if (lnode->keys > FILL_FACTOR) { + rotate_from_left(lnode, rnode, idx); + return true; + } + + return false; +} + +/** Rotate in a key from the right sibling or from the index node, if this operation can be done. + * + * @param lnode Node into which to add key from its right sibling + * or from the index node. + * + * @return True if the rotation was performed, false otherwise. + * + */ +static bool try_rotation_from_right(btree_node_t *lnode) +{ + size_t idx; + btree_node_t *rnode; + + /* + * If this is root node, the rotation can not be done. + */ + if (ROOT_NODE(lnode)) + return false; + + idx = find_key_by_subtree(lnode->parent, lnode, false); + if (idx == lnode->parent->keys) { + /* + * If this node is the rightmost subtree of its parent, + * the rotation can not be done. + */ + return false; + } + + rnode = lnode->parent->subtree[idx + 1]; + if (rnode->keys > FILL_FACTOR) { + rotate_from_right(lnode, rnode, idx); + return true; + } + + return false; +} + +/** Combine node with any of its siblings. + * + * The siblings are required to be below the fill factor. + * + * @param node Node to combine with one of its siblings. + * + * @return Pointer to the rightmost of the two nodes. + * + */ +static btree_node_t *node_combine(btree_node_t *node) +{ + size_t idx; + btree_node_t *rnode; + size_t i; + + ASSERT(!ROOT_NODE(node)); + + idx = find_key_by_subtree(node->parent, node, false); + if (idx == node->parent->keys) { + /* + * Rightmost subtree of its parent, combine with the left sibling. + */ + idx--; + rnode = node; + node = node->parent->subtree[idx]; + } else + rnode = node->parent->subtree[idx + 1]; + + /* Index nodes need to insert parent node key in between left and right node. */ + if (INDEX_NODE(node)) + node->key[node->keys++] = node->parent->key[idx]; + + /* Copy the key-value-subtree triplets from the right node. */ + for (i = 0; i < rnode->keys; i++) { + node->key[node->keys + i] = rnode->key[i]; + node->value[node->keys + i] = rnode->value[i]; + + if (INDEX_NODE(node)) { + node->subtree[node->keys + i] = rnode->subtree[i]; + rnode->subtree[i]->parent = node; + } + } + + if (INDEX_NODE(node)) { + node->subtree[node->keys + i] = rnode->subtree[i]; + rnode->subtree[i]->parent = node; + } + + node->keys += rnode->keys; + return rnode; } /** Recursively remove B-tree node. * - * @param t B-tree. - * @param key Key to be removed from the B-tree along with its associated value. + * @param t B-tree. + * @param key Key to be removed from the B-tree along with its associated value. * @param node Node where the key being removed resides. - */ -void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node) + * + */ +static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node) { if (ROOT_NODE(node)) { - if (node->keys == 1 && node->subtree[0]) { + if ((node->keys == 1) && (node->subtree[0])) { /* * Free the current root and set new root. @@ -257,4 +783,5 @@ node_remove_key_and_rsubtree(node, key); } + return; } @@ -271,5 +798,5 @@ if (node->keys > FILL_FACTOR) { size_t i; - + /* * The key can be immediatelly removed. @@ -280,13 +807,14 @@ */ node_remove_key_and_rsubtree(node, key); + for (i = 0; i < node->parent->keys; i++) { if (node->parent->key[i] == key) node->parent->key[i] = node->key[0]; } - } else { size_t idx; - btree_node_t *rnode, *parent; - + btree_node_t *rnode; + btree_node_t *parent; + /* * The node is below the fill factor as well as its left and right sibling. @@ -298,6 +826,8 @@ node_remove_key_and_rsubtree(node, key); rnode = node_combine(node); + if (LEAF_NODE(rnode)) list_remove(&rnode->leaf_link); + idx = find_key_by_subtree(parent, rnode, true); ASSERT((int) idx != -1); @@ -307,11 +837,34 @@ } +/** Remove B-tree node. + * + * @param t B-tree. + * @param key Key to be removed from the B-tree along + * with its associated value. + * @param leaf_node If not NULL, pointer to the leaf node where + * the key is found. + * + */ +void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node) +{ + btree_node_t *lnode; + + lnode = leaf_node; + if (!lnode) { + if (!btree_search(t, key, &lnode)) + panic("B-tree %p does not contain key %" PRIu64 ".", t, key); + } + + _btree_remove(t, key, lnode); +} + /** Search key in a B-tree. * - * @param t B-tree. - * @param key Key to be searched. + * @param t B-tree. + * @param key Key to be searched. * @param leaf_node Address where to put pointer to visited leaf node. * * @return Pointer to value or NULL if there is no such key. + * */ void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node) @@ -323,6 +876,8 @@ */ for (cur = t->root; cur; cur = next) { - - /* Last iteration will set this with proper leaf node address. */ + /* + * Last iteration will set this with proper + * leaf node address. + */ *leaf_node = cur; @@ -337,5 +892,5 @@ void *val; size_t i; - + /* * Now if the key is smaller than cur->key[i] @@ -347,26 +902,29 @@ next = cur->subtree[i]; val = cur->value[i - 1]; - + if (LEAF_NODE(cur)) return key == cur->key[i - 1] ? val : NULL; - + goto descend; - } + } } /* - * Last possibility is that the key is in the rightmost subtree. + * Last possibility is that the key is + * in the rightmost subtree. */ next = cur->subtree[i]; val = cur->value[i - 1]; + if (LEAF_NODE(cur)) return key == cur->key[i - 1] ? val : NULL; } descend: - ; - } - + ; + } + /* - * The key was not found in the *leaf_node and is smaller than any of its keys. + * The key was not found in the *leaf_node and + * is smaller than any of its keys. */ return NULL; @@ -375,12 +933,15 @@ /** Return pointer to B-tree leaf node's left neighbour. * - * @param t B-tree. + * @param t B-tree. * @param node Node whose left neighbour will be returned. * - * @return Left neighbour of the node or NULL if the node does not have the left neighbour. + * @return Left neighbour of the node or NULL if the node + * does not have the left neighbour. + * */ btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node) { ASSERT(LEAF_NODE(node)); + if (node->leaf_link.prev != &t->leaf_head) return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link); @@ -391,12 +952,15 @@ /** Return pointer to B-tree leaf node's right neighbour. * - * @param t B-tree. + * @param t B-tree. * @param node Node whose right neighbour will be returned. * - * @return Right neighbour of the node or NULL if the node does not have the right neighbour. + * @return Right neighbour of the node or NULL if the node + * does not have the right neighbour. + * */ btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node) { ASSERT(LEAF_NODE(node)); + if (node->leaf_link.next != &t->leaf_head) return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link); @@ -405,537 +969,8 @@ } -/** Initialize B-tree node. - * - * @param node B-tree node. - */ -void node_initialize(btree_node_t *node) -{ - int i; - - node->keys = 0; - - /* Clean also space for the extra key. */ - for (i = 0; i < BTREE_MAX_KEYS + 1; i++) { - node->key[i] = 0; - node->value[i] = NULL; - node->subtree[i] = NULL; - } - node->subtree[i] = NULL; - - node->parent = NULL; - - link_initialize(&node->leaf_link); - - link_initialize(&node->bfs_link); - node->depth = 0; -} - -/** Insert key-value-lsubtree triplet into B-tree node. - * - * It is actually possible to have more keys than BTREE_MAX_KEYS. - * This feature is used during insert by right rotation. - * - * @param node B-tree node into wich the new key is to be inserted. - * @param key The key to be inserted. - * @param value Pointer to value to be inserted. - * @param lsubtree Pointer to the left subtree. - */ -void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree) -{ - size_t i; - - for (i = 0; i < node->keys; i++) { - if (key < node->key[i]) { - size_t j; - - for (j = node->keys; j > i; j--) { - node->key[j] = node->key[j - 1]; - node->value[j] = node->value[j - 1]; - node->subtree[j + 1] = node->subtree[j]; - } - node->subtree[j + 1] = node->subtree[j]; - break; - } - } - node->key[i] = key; - node->value[i] = value; - node->subtree[i] = lsubtree; - - node->keys++; -} - -/** Insert key-value-rsubtree triplet into B-tree node. - * - * It is actually possible to have more keys than BTREE_MAX_KEYS. - * This feature is used during splitting the node when the - * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation - * also makes use of this feature. - * - * @param node B-tree node into wich the new key is to be inserted. - * @param key The key to be inserted. - * @param value Pointer to value to be inserted. - * @param rsubtree Pointer to the right subtree. - */ -void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree) -{ - size_t i; - - for (i = 0; i < node->keys; i++) { - if (key < node->key[i]) { - size_t j; - - for (j = node->keys; j > i; j--) { - node->key[j] = node->key[j - 1]; - node->value[j] = node->value[j - 1]; - node->subtree[j + 1] = node->subtree[j]; - } - break; - } - } - node->key[i] = key; - node->value[i] = value; - node->subtree[i + 1] = rsubtree; - - node->keys++; -} - -/** Remove key and its left subtree pointer from B-tree node. - * - * Remove the key and eliminate gaps in node->key array. - * Note that the value pointer and the left subtree pointer - * is removed from the node as well. - * - * @param node B-tree node. - * @param key Key to be removed. - */ -void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key) -{ - size_t i, j; - - for (i = 0; i < node->keys; i++) { - if (key == node->key[i]) { - for (j = i + 1; j < node->keys; j++) { - node->key[j - 1] = node->key[j]; - node->value[j - 1] = node->value[j]; - node->subtree[j - 1] = node->subtree[j]; - } - node->subtree[j - 1] = node->subtree[j]; - node->keys--; - return; - } - } - panic("Node %p does not contain key %" PRIu64 ".", node, key); -} - -/** Remove key and its right subtree pointer from B-tree node. - * - * Remove the key and eliminate gaps in node->key array. - * Note that the value pointer and the right subtree pointer - * is removed from the node as well. - * - * @param node B-tree node. - * @param key Key to be removed. - */ -void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key) -{ - size_t i, j; - - for (i = 0; i < node->keys; i++) { - if (key == node->key[i]) { - for (j = i + 1; j < node->keys; j++) { - node->key[j - 1] = node->key[j]; - node->value[j - 1] = node->value[j]; - node->subtree[j] = node->subtree[j + 1]; - } - node->keys--; - return; - } - } - panic("Node %p does not contain key %" PRIu64 ".", node, key); -} - -/** Split full B-tree node and insert new key-value-right-subtree triplet. - * - * This function will split a node and return a pointer to a newly created - * node containing keys greater than or equal to the greater of medians - * (or median) of the old keys and the newly added key. It will also write - * the median key to a memory address supplied by the caller. - * - * If the node being split is an index node, the median will not be - * included in the new node. If the node is a leaf node, - * the median will be copied there. - * - * @param node B-tree node wich is going to be split. - * @param key The key to be inserted. - * @param value Pointer to the value to be inserted. - * @param rsubtree Pointer to the right subtree of the key being added. - * @param median Address in memory, where the median key will be stored. - * - * @return Newly created right sibling of node. - */ -btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median) -{ - btree_node_t *rnode; - size_t i, j; - - ASSERT(median); - ASSERT(node->keys == BTREE_MAX_KEYS); - - /* - * Use the extra space to store the extra node. - */ - node_insert_key_and_rsubtree(node, key, value, rsubtree); - - /* - * Compute median of keys. - */ - *median = MEDIAN_HIGH(node); - - /* - * Allocate and initialize new right sibling. - */ - rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0); - node_initialize(rnode); - rnode->parent = node->parent; - rnode->depth = node->depth; - - /* - * Copy big keys, values and subtree pointers to the new right sibling. - * If this is an index node, do not copy the median. - */ - i = (size_t) INDEX_NODE(node); - for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) { - rnode->key[j] = node->key[i]; - rnode->value[j] = node->value[i]; - rnode->subtree[j] = node->subtree[i]; - - /* - * Fix parent links in subtrees. - */ - if (rnode->subtree[j]) - rnode->subtree[j]->parent = rnode; - - } - rnode->subtree[j] = node->subtree[i]; - if (rnode->subtree[j]) - rnode->subtree[j]->parent = rnode; - - rnode->keys = j; /* Set number of keys of the new node. */ - node->keys /= 2; /* Shrink the old node. */ - - return rnode; -} - -/** Combine node with any of its siblings. - * - * The siblings are required to be below the fill factor. - * - * @param node Node to combine with one of its siblings. - * - * @return Pointer to the rightmost of the two nodes. - */ -btree_node_t *node_combine(btree_node_t *node) -{ - size_t idx; - btree_node_t *rnode; - size_t i; - - ASSERT(!ROOT_NODE(node)); - - idx = find_key_by_subtree(node->parent, node, false); - if (idx == node->parent->keys) { - /* - * Rightmost subtree of its parent, combine with the left sibling. - */ - idx--; - rnode = node; - node = node->parent->subtree[idx]; - } else { - rnode = node->parent->subtree[idx + 1]; - } - - /* Index nodes need to insert parent node key in between left and right node. */ - if (INDEX_NODE(node)) - node->key[node->keys++] = node->parent->key[idx]; - - /* Copy the key-value-subtree triplets from the right node. */ - for (i = 0; i < rnode->keys; i++) { - node->key[node->keys + i] = rnode->key[i]; - node->value[node->keys + i] = rnode->value[i]; - if (INDEX_NODE(node)) { - node->subtree[node->keys + i] = rnode->subtree[i]; - rnode->subtree[i]->parent = node; - } - } - if (INDEX_NODE(node)) { - node->subtree[node->keys + i] = rnode->subtree[i]; - rnode->subtree[i]->parent = node; - } - - node->keys += rnode->keys; - - return rnode; -} - -/** Find key by its left or right subtree. - * - * @param node B-tree node. - * @param subtree Left or right subtree of a key found in node. - * @param right If true, subtree is a right subtree. If false, subtree is a left subtree. - * - * @return Index of the key associated with the subtree. - */ -size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right) -{ - size_t i; - - for (i = 0; i < node->keys + 1; i++) { - if (subtree == node->subtree[i]) - return i - (int) (right != false); - } - panic("Node %p does not contain subtree %p.", node, subtree); -} - -/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling. - * - * The biggest key and its value and right subtree is rotated from the left node - * to the right. If the node is an index node, than the parent node key belonging to - * the left node takes part in the rotation. - * - * @param lnode Left sibling. - * @param rnode Right sibling. - * @param idx Index of the parent node key that is taking part in the rotation. - */ -void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx) -{ - btree_key_t key; - - key = lnode->key[lnode->keys - 1]; - - if (LEAF_NODE(lnode)) { - void *value; - - value = lnode->value[lnode->keys - 1]; - node_remove_key_and_rsubtree(lnode, key); - node_insert_key_and_lsubtree(rnode, key, value, NULL); - lnode->parent->key[idx] = key; - } else { - btree_node_t *rsubtree; - - rsubtree = lnode->subtree[lnode->keys]; - node_remove_key_and_rsubtree(lnode, key); - node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree); - lnode->parent->key[idx] = key; - - /* Fix parent link of the reconnected right subtree. */ - rsubtree->parent = rnode; - } - -} - -/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling. - * - * The smallest key and its value and left subtree is rotated from the right node - * to the left. If the node is an index node, than the parent node key belonging to - * the right node takes part in the rotation. - * - * @param lnode Left sibling. - * @param rnode Right sibling. - * @param idx Index of the parent node key that is taking part in the rotation. - */ -void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx) -{ - btree_key_t key; - - key = rnode->key[0]; - - if (LEAF_NODE(rnode)) { - void *value; - - value = rnode->value[0]; - node_remove_key_and_lsubtree(rnode, key); - node_insert_key_and_rsubtree(lnode, key, value, NULL); - rnode->parent->key[idx] = rnode->key[0]; - } else { - btree_node_t *lsubtree; - - lsubtree = rnode->subtree[0]; - node_remove_key_and_lsubtree(rnode, key); - node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree); - rnode->parent->key[idx] = key; - - /* Fix parent link of the reconnected left subtree. */ - lsubtree->parent = lnode; - } - -} - -/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done. - * - * Left sibling of the node (if it exists) is checked for free space. - * If there is free space, the key is inserted and the smallest key of - * the node is moved there. The index node which is the parent of both - * nodes is fixed. - * - * @param node B-tree node. - * @param inskey Key to be inserted. - * @param insvalue Value to be inserted. - * @param rsubtree Right subtree of inskey. - * - * @return True if the rotation was performed, false otherwise. - */ -bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree) -{ - size_t idx; - btree_node_t *lnode; - - /* - * If this is root node, the rotation can not be done. - */ - if (ROOT_NODE(node)) - return false; - - idx = find_key_by_subtree(node->parent, node, true); - if ((int) idx == -1) { - /* - * If this node is the leftmost subtree of its parent, - * the rotation can not be done. - */ - return false; - } - - lnode = node->parent->subtree[idx]; - if (lnode->keys < BTREE_MAX_KEYS) { - /* - * The rotaion can be done. The left sibling has free space. - */ - node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree); - rotate_from_right(lnode, node, idx); - return true; - } - - return false; -} - -/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done. - * - * Right sibling of the node (if it exists) is checked for free space. - * If there is free space, the key is inserted and the biggest key of - * the node is moved there. The index node which is the parent of both - * nodes is fixed. - * - * @param node B-tree node. - * @param inskey Key to be inserted. - * @param insvalue Value to be inserted. - * @param rsubtree Right subtree of inskey. - * - * @return True if the rotation was performed, false otherwise. - */ -bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree) -{ - size_t idx; - btree_node_t *rnode; - - /* - * If this is root node, the rotation can not be done. - */ - if (ROOT_NODE(node)) - return false; - - idx = find_key_by_subtree(node->parent, node, false); - if (idx == node->parent->keys) { - /* - * If this node is the rightmost subtree of its parent, - * the rotation can not be done. - */ - return false; - } - - rnode = node->parent->subtree[idx + 1]; - if (rnode->keys < BTREE_MAX_KEYS) { - /* - * The rotaion can be done. The right sibling has free space. - */ - node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree); - rotate_from_left(node, rnode, idx); - return true; - } - - return false; -} - -/** Rotate in a key from the left sibling or from the index node, if this operation can be done. - * - * @param rnode Node into which to add key from its left sibling or from the index node. - * - * @return True if the rotation was performed, false otherwise. - */ -bool try_rotation_from_left(btree_node_t *rnode) -{ - size_t idx; - btree_node_t *lnode; - - /* - * If this is root node, the rotation can not be done. - */ - if (ROOT_NODE(rnode)) - return false; - - idx = find_key_by_subtree(rnode->parent, rnode, true); - if ((int) idx == -1) { - /* - * If this node is the leftmost subtree of its parent, - * the rotation can not be done. - */ - return false; - } - - lnode = rnode->parent->subtree[idx]; - if (lnode->keys > FILL_FACTOR) { - rotate_from_left(lnode, rnode, idx); - return true; - } - - return false; -} - -/** Rotate in a key from the right sibling or from the index node, if this operation can be done. - * - * @param lnode Node into which to add key from its right sibling or from the index node. - * - * @return True if the rotation was performed, false otherwise. - */ -bool try_rotation_from_right(btree_node_t *lnode) -{ - size_t idx; - btree_node_t *rnode; - - /* - * If this is root node, the rotation can not be done. - */ - if (ROOT_NODE(lnode)) - return false; - - idx = find_key_by_subtree(lnode->parent, lnode, false); - if (idx == lnode->parent->keys) { - /* - * If this node is the rightmost subtree of its parent, - * the rotation can not be done. - */ - return false; - } - - rnode = lnode->parent->subtree[idx + 1]; - if (rnode->keys > FILL_FACTOR) { - rotate_from_right(lnode, rnode, idx); - return true; - } - - return false; -} - /** Print B-tree. * * @param t Print out B-tree. + * */ void btree_print(btree_t *t) @@ -944,13 +979,13 @@ int depth = t->root->depth; link_t head, *cur; - + printf("Printing B-tree:\n"); list_initialize(&head); list_append(&t->root->bfs_link, &head); - + /* * Use BFS search to print out the tree. * Levels are distinguished from one another by node->depth. - */ + */ while (!list_empty(&head)) { link_t *hlp; @@ -968,6 +1003,7 @@ depth = node->depth; } - + printf("("); + for (i = 0; i < node->keys; i++) { printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : ""); @@ -976,9 +1012,11 @@ } } - if (node->depth && node->subtree[i]) { + + if (node->depth && node->subtree[i]) list_append(&node->subtree[i]->bfs_link, &head); - } + printf(")"); } + printf("\n"); @@ -990,10 +1028,13 @@ ASSERT(node); - + printf("("); + for (i = 0; i < node->keys; i++) printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : ""); + printf(")"); } + printf("\n"); } Index: kernel/generic/src/cpu/cpu.c =================================================================== --- kernel/generic/src/cpu/cpu.c (revision b5382d4f551b38012fe4db27dd79c095f5e09706) +++ kernel/generic/src/cpu/cpu.c (revision cefb126edea34b0dd89c1d23a3945eba732448c8) @@ -119,3 +119,2 @@ /** @} */ - Index: kernel/generic/src/mm/as.c =================================================================== --- kernel/generic/src/mm/as.c (revision b5382d4f551b38012fe4db27dd79c095f5e09706) +++ kernel/generic/src/mm/as.c (revision cefb126edea34b0dd89c1d23a3945eba732448c8) @@ -116,9 +116,4 @@ as_t *AS_KERNEL = NULL; -static unsigned int area_flags_to_page_flags(unsigned int); -static as_area_t *find_area_and_lock(as_t *, uintptr_t); -static bool check_area_conflicts(as_t *, uintptr_t, size_t, as_area_t *); -static void sh_info_remove_reference(share_info_t *); - static int as_constructor(void *obj, unsigned int flags) { @@ -296,4 +291,104 @@ if (atomic_predec(&as->refcount) == 0) as_destroy(as); +} + +/** Check area conflicts with other areas. + * + * @param as Address space. + * @param va Starting virtual address of the area being tested. + * @param size Size of the area being tested. + * @param avoid_area Do not touch this area. + * + * @return True if there is no conflict, false otherwise. + * + */ +static bool check_area_conflicts(as_t *as, uintptr_t va, size_t size, + as_area_t *avoid_area) +{ + ASSERT(mutex_locked(&as->lock)); + + /* + * We don't want any area to have conflicts with NULL page. + * + */ + if (overlaps(va, size, NULL, PAGE_SIZE)) + return false; + + /* + * The leaf node is found in O(log n), where n is proportional to + * the number of address space areas belonging to as. + * The check for conflicts is then attempted on the rightmost + * record in the left neighbour, the leftmost record in the right + * neighbour and all records in the leaf node itself. + * + */ + btree_node_t *leaf; + as_area_t *area = + (as_area_t *) btree_search(&as->as_area_btree, va, &leaf); + if (area) { + if (area != avoid_area) + return false; + } + + /* First, check the two border cases. */ + btree_node_t *node = + btree_leaf_node_left_neighbour(&as->as_area_btree, leaf); + if (node) { + area = (as_area_t *) node->value[node->keys - 1]; + + mutex_lock(&area->lock); + + if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) { + mutex_unlock(&area->lock); + return false; + } + + mutex_unlock(&area->lock); + } + + node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf); + if (node) { + area = (as_area_t *) node->value[0]; + + mutex_lock(&area->lock); + + if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) { + mutex_unlock(&area->lock); + return false; + } + + mutex_unlock(&area->lock); + } + + /* Second, check the leaf node. */ + btree_key_t i; + for (i = 0; i < leaf->keys; i++) { + area = (as_area_t *) leaf->value[i]; + + if (area == avoid_area) + continue; + + mutex_lock(&area->lock); + + if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) { + mutex_unlock(&area->lock); + return false; + } + + mutex_unlock(&area->lock); + } + + /* + * So far, the area does not conflict with other areas. + * Check if it doesn't conflict with kernel address space. + * + */ + if (!KERNEL_ADDRESS_SPACE_SHADOWED) { + return !overlaps(va, size, + KERNEL_ADDRESS_SPACE_START, + KERNEL_ADDRESS_SPACE_END - KERNEL_ADDRESS_SPACE_START); + } + + return true; } @@ -357,4 +452,66 @@ return area; +} + +/** Find address space area and lock it. + * + * @param as Address space. + * @param va Virtual address. + * + * @return Locked address space area containing va on success or + * NULL on failure. + * + */ +static as_area_t *find_area_and_lock(as_t *as, uintptr_t va) +{ + ASSERT(mutex_locked(&as->lock)); + + btree_node_t *leaf; + as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf); + if (area) { + /* va is the base address of an address space area */ + mutex_lock(&area->lock); + return area; + } + + /* + * Search the leaf node and the righmost record of its left neighbour + * to find out whether this is a miss or va belongs to an address + * space area found there. + * + */ + + /* First, search the leaf node itself. */ + btree_key_t i; + + for (i = 0; i < leaf->keys; i++) { + area = (as_area_t *) leaf->value[i]; + + mutex_lock(&area->lock); + + if ((area->base <= va) && (va < area->base + area->pages * PAGE_SIZE)) + return area; + + mutex_unlock(&area->lock); + } + + /* + * Second, locate the left neighbour and test its last record. + * Because of its position in the B+tree, it must have base < va. + * + */ + btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf); + if (lnode) { + area = (as_area_t *) lnode->value[lnode->keys - 1]; + + mutex_lock(&area->lock); + + if (va < area->base + area->pages * PAGE_SIZE) + return area; + + mutex_unlock(&area->lock); + } + + return NULL; } @@ -553,4 +710,45 @@ } +/** Remove reference to address space area share info. + * + * If the reference count drops to 0, the sh_info is deallocated. + * + * @param sh_info Pointer to address space area share info. + * + */ +static void sh_info_remove_reference(share_info_t *sh_info) +{ + bool dealloc = false; + + mutex_lock(&sh_info->lock); + ASSERT(sh_info->refcount); + + if (--sh_info->refcount == 0) { + dealloc = true; + link_t *cur; + + /* + * Now walk carefully the pagemap B+tree and free/remove + * reference from all frames found there. + */ + for (cur = sh_info->pagemap.leaf_head.next; + cur != &sh_info->pagemap.leaf_head; cur = cur->next) { + btree_node_t *node + = list_get_instance(cur, btree_node_t, leaf_link); + btree_key_t i; + + for (i = 0; i < node->keys; i++) + frame_free((uintptr_t) node->value[i]); + } + + } + mutex_unlock(&sh_info->lock); + + if (dealloc) { + btree_destroy(&sh_info->pagemap); + free(sh_info); + } +} + /** Destroy address space area. * @@ -805,4 +1003,30 @@ } +/** Convert address space area flags to page flags. + * + * @param aflags Flags of some address space area. + * + * @return Flags to be passed to page_mapping_insert(). + * + */ +static unsigned int area_flags_to_page_flags(unsigned int aflags) +{ + unsigned int flags = PAGE_USER | PAGE_PRESENT; + + if (aflags & AS_AREA_READ) + flags |= PAGE_READ; + + if (aflags & AS_AREA_WRITE) + flags |= PAGE_WRITE; + + if (aflags & AS_AREA_EXEC) + flags |= PAGE_EXEC; + + if (aflags & AS_AREA_CACHEABLE) + flags |= PAGE_CACHEABLE; + + return flags; +} + /** Change adress space area flags. * @@ -1161,29 +1385,5 @@ } -/** Convert address space area flags to page flags. - * - * @param aflags Flags of some address space area. - * - * @return Flags to be passed to page_mapping_insert(). - * - */ -unsigned int area_flags_to_page_flags(unsigned int aflags) -{ - unsigned int flags = PAGE_USER | PAGE_PRESENT; - - if (aflags & AS_AREA_READ) - flags |= PAGE_READ; - - if (aflags & AS_AREA_WRITE) - flags |= PAGE_WRITE; - - if (aflags & AS_AREA_EXEC) - flags |= PAGE_EXEC; - - if (aflags & AS_AREA_CACHEABLE) - flags |= PAGE_CACHEABLE; - - return flags; -} + /** Compute flags for virtual address translation subsytem. @@ -1272,8 +1472,8 @@ /** Test whether page tables are locked. * - * @param as Address space where the page tables belong. - * - * @return True if the page tables belonging to the address soace - * are locked, otherwise false. + * @param as Address space where the page tables belong. + * + * @return True if the page tables belonging to the address soace + * are locked, otherwise false. */ bool page_table_locked(as_t *as) @@ -1283,167 +1483,4 @@ return as_operations->page_table_locked(as); -} - - -/** Find address space area and lock it. - * - * @param as Address space. - * @param va Virtual address. - * - * @return Locked address space area containing va on success or - * NULL on failure. - * - */ -as_area_t *find_area_and_lock(as_t *as, uintptr_t va) -{ - ASSERT(mutex_locked(&as->lock)); - - btree_node_t *leaf; - as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf); - if (area) { - /* va is the base address of an address space area */ - mutex_lock(&area->lock); - return area; - } - - /* - * Search the leaf node and the righmost record of its left neighbour - * to find out whether this is a miss or va belongs to an address - * space area found there. - * - */ - - /* First, search the leaf node itself. */ - btree_key_t i; - - for (i = 0; i < leaf->keys; i++) { - area = (as_area_t *) leaf->value[i]; - - mutex_lock(&area->lock); - - if ((area->base <= va) && (va < area->base + area->pages * PAGE_SIZE)) - return area; - - mutex_unlock(&area->lock); - } - - /* - * Second, locate the left neighbour and test its last record. - * Because of its position in the B+tree, it must have base < va. - * - */ - btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf); - if (lnode) { - area = (as_area_t *) lnode->value[lnode->keys - 1]; - - mutex_lock(&area->lock); - - if (va < area->base + area->pages * PAGE_SIZE) - return area; - - mutex_unlock(&area->lock); - } - - return NULL; -} - -/** Check area conflicts with other areas. - * - * @param as Address space. - * @param va Starting virtual address of the area being tested. - * @param size Size of the area being tested. - * @param avoid_area Do not touch this area. - * - * @return True if there is no conflict, false otherwise. - * - */ -bool check_area_conflicts(as_t *as, uintptr_t va, size_t size, - as_area_t *avoid_area) -{ - ASSERT(mutex_locked(&as->lock)); - - /* - * We don't want any area to have conflicts with NULL page. - * - */ - if (overlaps(va, size, NULL, PAGE_SIZE)) - return false; - - /* - * The leaf node is found in O(log n), where n is proportional to - * the number of address space areas belonging to as. - * The check for conflicts is then attempted on the rightmost - * record in the left neighbour, the leftmost record in the right - * neighbour and all records in the leaf node itself. - * - */ - btree_node_t *leaf; - as_area_t *area = - (as_area_t *) btree_search(&as->as_area_btree, va, &leaf); - if (area) { - if (area != avoid_area) - return false; - } - - /* First, check the two border cases. */ - btree_node_t *node = - btree_leaf_node_left_neighbour(&as->as_area_btree, leaf); - if (node) { - area = (as_area_t *) node->value[node->keys - 1]; - - mutex_lock(&area->lock); - - if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) { - mutex_unlock(&area->lock); - return false; - } - - mutex_unlock(&area->lock); - } - - node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf); - if (node) { - area = (as_area_t *) node->value[0]; - - mutex_lock(&area->lock); - - if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) { - mutex_unlock(&area->lock); - return false; - } - - mutex_unlock(&area->lock); - } - - /* Second, check the leaf node. */ - btree_key_t i; - for (i = 0; i < leaf->keys; i++) { - area = (as_area_t *) leaf->value[i]; - - if (area == avoid_area) - continue; - - mutex_lock(&area->lock); - - if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) { - mutex_unlock(&area->lock); - return false; - } - - mutex_unlock(&area->lock); - } - - /* - * So far, the area does not conflict with other areas. - * Check if it doesn't conflict with kernel address space. - * - */ - if (!KERNEL_ADDRESS_SPACE_SHADOWED) { - return !overlaps(va, size, - KERNEL_ADDRESS_SPACE_START, - KERNEL_ADDRESS_SPACE_END - KERNEL_ADDRESS_SPACE_START); - } - - return true; } @@ -1960,45 +1997,4 @@ } -/** Remove reference to address space area share info. - * - * If the reference count drops to 0, the sh_info is deallocated. - * - * @param sh_info Pointer to address space area share info. - * - */ -void sh_info_remove_reference(share_info_t *sh_info) -{ - bool dealloc = false; - - mutex_lock(&sh_info->lock); - ASSERT(sh_info->refcount); - - if (--sh_info->refcount == 0) { - dealloc = true; - link_t *cur; - - /* - * Now walk carefully the pagemap B+tree and free/remove - * reference from all frames found there. - */ - for (cur = sh_info->pagemap.leaf_head.next; - cur != &sh_info->pagemap.leaf_head; cur = cur->next) { - btree_node_t *node - = list_get_instance(cur, btree_node_t, leaf_link); - btree_key_t i; - - for (i = 0; i < node->keys; i++) - frame_free((uintptr_t) node->value[i]); - } - - } - mutex_unlock(&sh_info->lock); - - if (dealloc) { - btree_destroy(&sh_info->pagemap); - free(sh_info); - } -} - /* * Address space related syscalls. Index: kernel/generic/src/mm/page.c =================================================================== --- kernel/generic/src/mm/page.c (revision b5382d4f551b38012fe4db27dd79c095f5e09706) +++ kernel/generic/src/mm/page.c (revision cefb126edea34b0dd89c1d23a3945eba732448c8) @@ -38,5 +38,5 @@ * mappings between virtual addresses and physical addresses. * Functions here are mere wrappers that call the real implementation. - * They however, define the single interface. + * They however, define the single interface. * */ Index: kernel/generic/src/proc/the.c =================================================================== --- kernel/generic/src/proc/the.c (revision b5382d4f551b38012fe4db27dd79c095f5e09706) +++ kernel/generic/src/proc/the.c (revision cefb126edea34b0dd89c1d23a3945eba732448c8) @@ -33,5 +33,5 @@ /** * @file - * @brief THE structure functions. + * @brief THE structure functions. * * This file contains functions to manage the THE structure. @@ -43,5 +43,4 @@ #include - /** Initialize THE structure