Changeset cefb126 in mainline for kernel/generic/src

Timestamp:

2010-07-02T14:19:30Z (15 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

89c57b6

Parents:

fe7abd0 (diff), e3ee9b9 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge mainline changes.

Location:

kernel/generic/src

Files:

• adt/btree.c (modified) (22 diffs)
• console/cmd.c (modified) (7 diffs)
• console/console.c (modified) (1 diff)
• cpu/cpu.c (modified) (3 diffs)
• debug/debug.c (moved) (moved from kernel/test/synch/rwlock2.c ) (2 diffs)
• debug/panic.c (moved) (moved from uspace/lib/c/include/limits.h ) (3 diffs)
• debug/stacktrace.c (modified) (2 diffs)
• debug/symtab.c (modified) (3 diffs)
• interrupt/interrupt.c (modified) (3 diffs)
• ipc/sysipc.c (modified) (1 diff)
• lib/sort.c (modified) (2 diffs)
• main/kinit.c (modified) (3 diffs)
• main/main.c (modified) (15 diffs)
• mm/as.c (modified) (45 diffs)
• mm/frame.c (modified) (3 diffs)
• mm/page.c (modified) (4 diffs)
• mm/slab.c (modified) (2 diffs)
• mm/tlb.c (modified) (3 diffs)
• proc/program.c (modified) (1 diff)
• proc/scheduler.c (modified) (3 diffs)
• proc/the.c (modified) (2 diffs)
• proc/thread.c (modified) (4 diffs)
• smp/ipi.c (modified) (2 diffs)
• synch/futex.c (modified) (13 diffs)
• synch/rwlock.c (deleted)
• sysinfo/stats.c (modified) (1 diff)
• time/clock.c (modified) (4 diffs)

kernel/generic/src/adt/btree.c

@@ -33 +33 @@
 /**
  * @file
- * @brief       B+tree implementation.
+ * @brief B+tree implementation.
  *
  * This file implements B+tree type and operations.
@@ -54 +54 @@
 #include <print.h>
 
-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 +103 @@
  *
  * @param t B-tree.
+ *
  */
 void btree_create(btree_t *t)
@@ -103 +113 @@
 }
 
-/** 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 +128 @@
                 }
         }
+        
         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 +579 @@
                  * 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 +598 @@
                          * 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 +783 @@
                         node_remove_key_and_rsubtree(node, key);
                 }
+                
                 return;
         }
@@ -271 +798 @@
         if (node->keys > FILL_FACTOR) {
                 size_t i;
-
+                
                 /*
                  * The key can be immediatelly removed.
@@ -280 +807 @@
                  */
                 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 +826 @@
                 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 +837 @@
 }
 
+/** 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 +876 @@
          */
         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 +892 @@
                         void *val;
                         size_t i;
-                
+                        
                         /*
                          * Now if the key is smaller than cur->key[i]
@@ -347 +902 @@
                                         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 +933 @@
 /** 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 +952 @@
 /** 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 +969 @@
 }
 
-/** 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 +979 @@
         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 +1003 @@
                         depth = node->depth;
                 }
-
+                
                 printf("(");
+                
                 for (i = 0; i < node->keys; i++) {
                         printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
@@ -976 +1012 @@
                         }
                 }
-                if (node->depth && node->subtree[i]) {
+                
+                if (node->depth && node->subtree[i])
                         list_append(&node->subtree[i]->bfs_link, &head);
-                }
+                
                 printf(")");
         }
+        
         printf("\n");
         
@@ -990 +1028 @@
                 
                 ASSERT(node);
-
+                
                 printf("(");
+                
                 for (i = 0; i < node->keys; i++)
                         printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
+                
                 printf(")");
         }
+        
         printf("\n");
 }

kernel/generic/src/console/cmd.c

@@ -108 +108 @@
 
 #ifdef CONFIG_TEST
-static int cmd_tests(cmd_arg_t *argv);
-static cmd_info_t tests_info = {
-        .name = "tests",
-        .description = "Print available kernel tests.",
-        .func = cmd_tests,
-        .argc = 0
-};
-
 static char test_buf[MAX_CMDLINE + 1];
 static int cmd_test(cmd_arg_t *argv);
 static cmd_arg_t test_argv[] = {
         {
-                .type = ARG_TYPE_STRING,
+                .type = ARG_TYPE_STRING_OPTIONAL,
                 .buffer = test_buf,
                 .len = sizeof(test_buf)
@@ -127 +119 @@
 static cmd_info_t test_info = {
         .name = "test",
-        .description = "Run kernel test.",
+        .description = "Print list of kernel tests or run a test.",
         .func = cmd_test,
         .argc = 1,
@@ -509 +501 @@
         &zone_info,
 #ifdef CONFIG_TEST
-        &tests_info,
         &test_info,
         &bench_info,
@@ -1066 +1057 @@
 
 #ifdef CONFIG_TEST
-/** Command for printing kernel tests list.
- *
- * @param argv Ignored.
- *
- * return Always 1.
- */
-int cmd_tests(cmd_arg_t *argv)
-{
-        size_t len = 0;
-        test_t *test;
-        for (test = tests; test->name != NULL; test++) {
-                if (str_length(test->name) > len)
-                        len = str_length(test->name);
-        }
-        
-        for (test = tests; test->name != NULL; test++)
-                printf("%-*s %s%s\n", len, test->name, test->desc, (test->safe ? "" : " (unsafe)"));
-        
-        printf("%-*s Run all safe tests\n", len, "*");
-        return 1;
-}
-
 static bool run_test(const test_t *test)
 {
@@ -1193 +1162 @@
 }
 
-/** Command for returning kernel tests
+static void list_tests(void)
+{
+        size_t len = 0;
+        test_t *test;
+        
+        for (test = tests; test->name != NULL; test++) {
+                if (str_length(test->name) > len)
+                        len = str_length(test->name);
+        }
+        
+        for (test = tests; test->name != NULL; test++)
+                printf("%-*s %s%s\n", len, test->name, test->desc, (test->safe ? "" : " (unsafe)"));
+        
+        printf("%-*s Run all safe tests\n", len, "*");
+}
+
+/** Command for listing and running kernel tests
  *
  * @param argv Argument vector.
  *
  * return Always 1.
+ *
  */
 int cmd_test(cmd_arg_t *argv)
@@ -1211 +1197 @@
                         }
                 }
-        } else {
+        } else if (str_cmp((char *) argv->buffer, "") != 0) {
                 bool fnd = false;
                 
@@ -1224 +1210 @@
                 if (!fnd)
                         printf("Unknown test\n");
-        }
+        } else
+                list_tests();
         
         return 1;

kernel/generic/src/console/console.c

@@ -294 +294 @@
                 stdout->op->write(stdout, ch, silent);
         else {
-                /* The character is just in the kernel log */
+                /*
+                 * No standard output routine defined yet.
+                 * The character is still stored in the kernel log
+                 * for possible future output.
+                 *
+                 * The early_putchar() function is used to output
+                 * the character for low-level debugging purposes.
+                 * Note that the early_putc() function might be
+                 * a no-op on certain hardware configurations.
+                 *
+                 */
+                early_putchar(ch);
+                
                 if (klog_stored < klog_len)
                         klog_stored++;

kernel/generic/src/cpu/cpu.c

@@ -49 +49 @@
 #include <print.h>
 #include <sysinfo/sysinfo.h>
+#include <arch/cycle.h>
 
 cpu_t *cpus;
@@ -94 +95 @@
         CPU->tlb_active = true;
         
+        CPU->idle = false;
+        CPU->last_cycle = get_cycle();
+        CPU->idle_cycles = 0;
+        CPU->busy_cycles = 0;
+        
         cpu_identify();
         cpu_arch_init();
@@ -113 +119 @@
 /** @}
  */
-

kernel/generic/src/debug/debug.c

@@ -1 +1 @@
 /*
- * Copyright (c) 2001-2004 Jakub Jermar
+ * Copyright (c) 2010 Martin Decky
  * All rights reserved.
  *
@@ -27 +27 @@
  */
 
-#include <test.h>
-#include <arch.h>
-#include <atomic.h>
+/** @addtogroup genericdebug
+ * @{
+ */
+
+/**
+ * @file
+ * @brief Kernel instrumentation functions.
+ */
+
+#ifdef CONFIG_TRACE
+
+#include <debug.h>
+#include <symtab.h>
+#include <errno.h>
 #include <print.h>
-#include <proc/thread.h>
 
-#include <synch/rwlock.h>
-
-#define READERS  50
-#define WRITERS  50
-
-static rwlock_t rwlock;
-
-static void writer(void *arg)
+void __cyg_profile_func_enter(void *fn, void *call_site)
 {
-        TPRINTF("Trying to lock rwlock for writing....\n");
+        const char *fn_sym = symtab_fmt_name_lookup((uintptr_t) fn);
         
-        rwlock_write_lock(&rwlock);
-        rwlock_write_unlock(&rwlock);
+        const char *call_site_sym;
+        uintptr_t call_site_off;
         
-        TPRINTF("Trying to lock rwlock for reading....\n");
-        
-        rwlock_read_lock(&rwlock);
-        rwlock_read_unlock(&rwlock);
+        if (symtab_name_lookup((uintptr_t) call_site, &call_site_sym,
+            &call_site_off) == EOK)
+                printf("%s+%" PRIp "->%s\n", call_site_sym, call_site_off,
+                    fn_sym);
+        else
+                printf("->%s\n", fn_sym);
 }
 
-const char *test_rwlock2(void)
+void __cyg_profile_func_exit(void *fn, void *call_site)
 {
-        thread_t *thrd;
+        const char *fn_sym = symtab_fmt_name_lookup((uintptr_t) fn);
         
-        rwlock_initialize(&rwlock);
+        const char *call_site_sym;
+        uintptr_t call_site_off;
         
-        rwlock_read_lock(&rwlock);
-        rwlock_read_lock(&rwlock);
-        rwlock_read_lock(&rwlock);
-        rwlock_read_lock(&rwlock);
-        
-        thrd = thread_create(writer, NULL, TASK, 0, "writer", false);
-        if (thrd)
-                thread_ready(thrd);
+        if (symtab_name_lookup((uintptr_t) call_site, &call_site_sym,
+            &call_site_off) == EOK)
+                printf("%s+%" PRIp "<-%s\n", call_site_sym, call_site_off,
+                    fn_sym);
         else
-                return "Could not create thread";
-        
-        thread_sleep(1);
-        
-        rwlock_read_unlock(&rwlock);
-        rwlock_read_unlock(&rwlock);
-        rwlock_read_unlock(&rwlock);
-        rwlock_read_unlock(&rwlock);
-        
-        thread_join(thrd);
-        thread_detach(thrd);
-        
-        return NULL;
+                printf("<-%s\n", fn_sym);
 }
+
+#endif /* CONFIG_TRACE */
+
+/** @}
+ */

kernel/generic/src/debug/panic.c

@@ -1 +1 @@
 /*
- * Copyright (c) 2006 Josef Cejka
+ * Copyright (c) 2010 Jakub Jermar
  * All rights reserved.
  *
@@ -27 +27 @@
  */
 
-/** @addtogroup libc
+/** @addtogroup genericdebug
  * @{
  */
@@ -33 +33 @@
  */
 
-#ifndef LIBC_LIMITS_H_
-#define LIBC_LIMITS_H_
+#include <panic.h>
+#include <print.h>
+#include <stacktrace.h>
+#include <func.h>
+#include <typedefs.h>
+#include <mm/as.h>
+#include <stdarg.h>
+#include <interrupt.h>
 
-#include <stdint.h>
-#include <libarch/limits.h>
+void panic_common(panic_category_t cat, istate_t *istate, int access,
+    uintptr_t address, const char *fmt, ...)
+{
+        va_list args;
 
-/* char */
-#define SCHAR_MIN MIN_INT8
-#define SCHAR_MAX MAX_INT8
-#define UCHAR_MIN MIN_UINT8
-#define UCHAR_MAX MAX_UINT8
+        silent = false;
 
-#ifdef __CHAR_UNSIGNED__
-        #define CHAR_MIN UCHAR_MIN
-        #define CHAR_MAX UCHAR_MAX
-#else
-        #define CHAR_MIN SCHAR_MIN
-        #define CHAR_MAX SCHAR_MAX
-#endif
+        printf("\nKERNEL PANIC ");
+        if (CPU)
+                printf("ON cpu%d ", CPU->id);
+        printf("DUE TO ");
 
-/* short int */
-#define SHRT_MIN MIN_INT16
-#define SHRT_MAX MAX_INT16
-#define USHRT_MIN MIN_UINT16
-#define USHRT_MAX MAX_UINT16
+        va_start(args, fmt);
+        if (cat == PANIC_ASSERT) {
+                printf("A FAILED ASSERTION:\n");
+                vprintf(fmt, args);
+                printf("\n");
+        } else if (cat == PANIC_BADTRAP) {
+                printf("BAD TRAP %ld.\n", address);
+        } else if (cat == PANIC_MEMTRAP) {
+                printf("A BAD MEMORY ACCESS WHILE ");
+                if (access == PF_ACCESS_READ)
+                        printf("LOADING FROM");
+                else if (access == PF_ACCESS_WRITE)
+                        printf("STORING TO");
+                else if (access == PF_ACCESS_EXEC)
+                        printf("BRANCHING TO");
+                else
+                        printf("REFERENCING");
+                printf(" ADDRESS %p.\n", address); 
+        } else {
+                printf("THE FOLLOWING REASON:\n");
+                vprintf(fmt, args);
+        }
+        va_end(args);
 
-/* int */
-#define INT_MIN MIN_INT32
-#define INT_MAX MAX_INT32
-#define UINT_MIN MIN_UINT32
-#define UINT_MAX MAX_UINT32
+        printf("\n");
 
-/* long long int */
-#define LLONG_MIN MIN_INT64
-#define LLONG_MAX MAX_INT64
-#define ULLONG_MIN MIN_UINT64
-#define ULLONG_MAX MAX_UINT64
+        if (istate) {
+                istate_decode(istate);
+                printf("\n");
+        }
 
-/* off64_t */
-#define OFF64_MIN MIN_INT64
-#define OFF64_MAX MAX_INT64
-
-/* aoff64_t */
-#define AOFF64_MIN MIN_UINT64
-#define AOFF64_MAX MAX_UINT64
-
-#endif
+        stack_trace();
+        halt();
+}
 
 /** @}

kernel/generic/src/debug/stacktrace.c

@@ -37 +37 @@
 #include <typedefs.h>
 #include <symtab.h>
+#include <print.h>
 
 #define STACK_FRAMES_MAX        20
@@ -51 +52 @@
                     ops->symbol_resolve(pc, &symbol, &offset)) {
                         if (offset)
-                                printf("%p: %s+%p()\n", fp, symbol, offset);
+                                printf("%p: %s+%" PRIp "()\n", fp, symbol, offset);
                         else
                                 printf("%p: %s()\n", fp, symbol);

kernel/generic/src/debug/symtab.c

@@ -46 +46 @@
 /** Get name of a symbol that seems most likely to correspond to address.
  *
- * @param addr          Address.
- * @param name          Place to store pointer to the symbol name.
- * @param offset        Place to store offset from the symbol address.
+ * @param addr   Address.
+ * @param name   Place to store pointer to the symbol name.
+ * @param offset Place to store offset from the symbol address.
  *
  * @return Zero on success or negative error code, ENOENT if not found,
@@ -83 +83 @@
 /** Lookup symbol by address and format for display.
  *
- * Returns name of closest corresponding symbol, "Not found" if none exists
- * or "N/A" if no symbol information is available.
+ * Returns name of closest corresponding symbol,
+ * "unknown" if none exists and "N/A" if no symbol
+ * information is available.
  *
  * @param addr Address.
@@ -101 +102 @@
                 return name;
         case ENOENT:
-                return "Not found";
+                return "unknown";
         default:
                 return "N/A";

kernel/generic/src/interrupt/interrupt.c

@@ -99 +99 @@
 void exc_dispatch(unsigned int n, istate_t *istate)
 {
+        ASSERT(CPU);
+        
 #if (IVT_ITEMS > 0)
         ASSERT(n < IVT_ITEMS);
@@ -110 +112 @@
         }
         
+        /* Account CPU usage if it has waked up from sleep */
+        irq_spinlock_lock(&CPU->lock, false);
+        if (CPU->idle) {
+                uint64_t now = get_cycle();
+                CPU->idle_cycles += now - CPU->last_cycle;
+                CPU->last_cycle = now;
+                CPU->idle = false;
+        }
+        irq_spinlock_unlock(&CPU->lock, false);
+        
         uint64_t begin_cycle = get_cycle();
         
@@ -131 +143 @@
         uint64_t end_cycle = get_cycle();
         
+        irq_spinlock_lock(&exctbl_lock, false);
         exc_table[n].cycles += end_cycle - begin_cycle;
         exc_table[n].count++;
+        irq_spinlock_unlock(&exctbl_lock, false);
         
         /* Do not charge THREAD for exception cycles */

kernel/generic/src/ipc/sysipc.c

@@ -1150 +1150 @@
                 return (unative_t) rc;
         
-        LOG("sys_ipc_connect_kbox(%" PRIu64 ")\n", taskid_arg.value);
+        LOG("sys_ipc_connect_kbox(%" PRIu64 ")", taskid_arg.value);
         
         return ipc_connect_kbox(taskid_arg.value);

kernel/generic/src/lib/sort.c

@@ -27 +27 @@
  */
 
-/** @addtogroup generic 
+/** @addtogroup generic
  * @{
  */
@@ -33 +33 @@
 /**
  * @file
- * @brief       Sorting functions.
+ * @brief Sorting functions.
  *
  * This files contains functions implementing several sorting
- * algorithms (e.g. quick sort and bubble sort).
- */
- 
+ * algorithms (e.g. quick sort and gnome sort).
+ *
+ */
+
 #include <mm/slab.h>
 #include <memstr.h>
 #include <sort.h>
-#include <panic.h>
-
-#define EBUFSIZE        32
-
-void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot);
-void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);
-
-/** Quicksort wrapper
- *
- * This is only a wrapper that takes care of memory allocations for storing
- * the pivot and temporary elements for generic quicksort algorithm.
- * 
- * This function _can_ sleep
- *
- * @param data Pointer to data to be sorted.
- * @param n Number of elements to be sorted.
- * @param e_size Size of one element.
- * @param cmp Comparator function.
- * 
- */
-void qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
-{
-        uint8_t buf_tmp[EBUFSIZE];
-        uint8_t buf_pivot[EBUFSIZE];
-        void * tmp = buf_tmp;
-        void * pivot = buf_pivot;
-
-        if (e_size > EBUFSIZE) {
-                pivot = (void *) malloc(e_size, 0);
-                tmp = (void *) malloc(e_size, 0);
+
+/** Immediate buffer size.
+ *
+ * For small buffer sizes avoid doing malloc()
+ * and use the stack.
+ *
+ */
+#define IBUF_SIZE  32
+
+/** Array accessor.
+ *
+ */
+#define INDEX(buf, i, elem_size)  ((buf) + (i) * (elem_size))
+
+/** Gnome sort
+ *
+ * Apply generic gnome sort algorithm on supplied data,
+ * using pre-allocated buffer.
+ *
+ * @param data      Pointer to data to be sorted.
+ * @param cnt       Number of elements to be sorted.
+ * @param elem_size Size of one element.
+ * @param cmp       Comparator function.
+ * @param arg       3rd argument passed to cmp.
+ * @param slot      Pointer to scratch memory buffer
+ *                  elem_size bytes long.
+ *
+ */
+static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
+    void *arg, void *slot)
+{
+        size_t i = 0;
+        
+        while (i < cnt) {
+                if ((i > 0) &&
+                    (cmp(INDEX(data, i, elem_size),
+                    INDEX(data, i - 1, elem_size), arg) == -1)) {
+                        memcpy(slot, INDEX(data, i, elem_size), elem_size);
+                        memcpy(INDEX(data, i, elem_size), INDEX(data, i - 1, elem_size),
+                            elem_size);
+                        memcpy(INDEX(data, i - 1, elem_size), slot, elem_size);
+                        i--;
+                } else
+                        i++;
         }
-
-        _qsort(data, n, e_size, cmp, tmp, pivot);
-        
-        if (e_size > EBUFSIZE) {
-                free(tmp);
-                free(pivot);
-        }
 }
 
 /** Quicksort
  *
- * Apply generic quicksort algorithm on supplied data, using pre-allocated buffers.
- * 
- * @param data Pointer to data to be sorted.
- * @param n Number of elements to be sorted.
- * @param e_size Size of one element.
- * @param cmp Comparator function.
- * @param tmp Pointer to scratch memory buffer e_size bytes long.
- * @param pivot Pointer to scratch memory buffer e_size bytes long.
- * 
- */
-void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot)
-{
-        if (n > 4) {
-                unsigned int i = 0, j = n - 1;
-
-                memcpy(pivot, data, e_size);
-
-                while (1) {
-                        while ((cmp(data + i * e_size, pivot) < 0) && (i < n))
+ * Apply generic quicksort algorithm on supplied data,
+ * using pre-allocated buffers.
+ *
+ * @param data      Pointer to data to be sorted.
+ * @param cnt       Number of elements to be sorted.
+ * @param elem_size Size of one element.
+ * @param cmp       Comparator function.
+ * @param arg       3rd argument passed to cmp.
+ * @param slot      Pointer to scratch memory buffer
+ *                  elem_size bytes long.
+ * @param pivot     Pointer to scratch memory buffer
+ *                  elem_size bytes long.
+ *
+ */
+static void _qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
+    void *arg, void *slot, void *pivot)
+{
+        if (cnt > 4) {
+                size_t i = 0;
+                size_t j = cnt - 1;
+                
+                memcpy(pivot, data, elem_size);
+                
+                while (true) {
+                        while ((cmp(INDEX(data, i, elem_size), pivot, arg) < 0) && (i < cnt))
                                 i++;
-                        while ((cmp(data + j * e_size, pivot) >= 0) && (j > 0))
+                        
+                        while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0))
                                 j--;
                         
                         if (i < j) {
-                                memcpy(tmp, data + i * e_size, e_size);
-                                memcpy(data + i * e_size, data + j * e_size, e_size);
-                                memcpy(data + j * e_size, tmp, e_size);
-                        } else {
+                                memcpy(slot, INDEX(data, i, elem_size), elem_size);
+                                memcpy(INDEX(data, i, elem_size), INDEX(data, j, elem_size),
+                                    elem_size);
+                                memcpy(INDEX(data, j, elem_size), slot, elem_size);
+                        } else
                                 break;
-                        }
                 }
-
-                _qsort(data, j + 1, e_size, cmp, tmp, pivot);
-                _qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp, tmp, pivot);
+                
+                _qsort(data, j + 1, elem_size, cmp, arg, slot, pivot);
+                _qsort(INDEX(data, j + 1, elem_size), cnt - j - 1, elem_size,
+                    cmp, arg, slot, pivot);
+        } else
+                _gsort(data, cnt, elem_size, cmp, arg, slot);
+}
+
+/** Gnome sort wrapper
+ *
+ * This is only a wrapper that takes care of memory
+ * allocations for storing the slot element for generic
+ * gnome sort algorithm.
+ *
+ * This function can sleep.
+ *
+ * @param data      Pointer to data to be sorted.
+ * @param cnt       Number of elements to be sorted.
+ * @param elem_size Size of one element.
+ * @param cmp       Comparator function.
+ * @param arg       3rd argument passed to cmp.
+ *
+ * @return True if sorting succeeded.
+ *
+ */
+bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
+{
+        uint8_t ibuf_slot[IBUF_SIZE];
+        void *slot;
+        
+        if (elem_size > IBUF_SIZE) {
+                slot = (void *) malloc(elem_size, 0);
+                if (!slot)
+                        return false;
+        } else
+                slot = (void *) ibuf_slot;
+        
+        _gsort(data, cnt, elem_size, cmp, arg, slot);
+        
+        if (elem_size > IBUF_SIZE)
+                free(slot);
+        
+        return true;
+}
+
+/** Quicksort wrapper
+ *
+ * This is only a wrapper that takes care of memory
+ * allocations for storing the pivot and temporary elements
+ * for generic quicksort algorithm.
+ *
+ * This function can sleep.
+ *
+ * @param data      Pointer to data to be sorted.
+ * @param cnt       Number of elements to be sorted.
+ * @param elem_size Size of one element.
+ * @param cmp       Comparator function.
+ * @param arg       3rd argument passed to cmp.
+ *
+ * @return True if sorting succeeded.
+ *
+ */
+bool qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
+{
+        uint8_t ibuf_slot[IBUF_SIZE];
+        uint8_t ibuf_pivot[IBUF_SIZE];
+        void *slot;
+        void *pivot;
+        
+        if (elem_size > IBUF_SIZE) {
+                slot = (void *) malloc(elem_size, 0);
+                if (!slot)
+                        return false;
+                
+                pivot = (void *) malloc(elem_size, 0);
+                if (!pivot) {
+                        free(slot);
+                        return false;
+                }
         } else {
-                _bubblesort(data, n, e_size, cmp, tmp);
+                slot = (void *) ibuf_slot;
+                pivot = (void *) ibuf_pivot;
         }
-}
-
-/** Bubblesort wrapper
- *
- * This is only a wrapper that takes care of memory allocation for storing
- * the slot element for generic bubblesort algorithm.
- * 
- * @param data Pointer to data to be sorted.
- * @param n Number of elements to be sorted.
- * @param e_size Size of one element.
- * @param cmp Comparator function.
- * 
- */
-void bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
-{
-        uint8_t buf_slot[EBUFSIZE];
-        void * slot = buf_slot;
-        
-        if (e_size > EBUFSIZE) {
-                slot = (void *) malloc(e_size, 0);
-        }
-
-        _bubblesort(data, n, e_size, cmp, slot);
-        
-        if (e_size > EBUFSIZE) {
+        
+        _qsort(data, cnt, elem_size, cmp, arg, slot, pivot);
+        
+        if (elem_size > IBUF_SIZE) {
+                free(pivot);
                 free(slot);
         }
-}
-
-/** Bubblesort
- *
- * Apply generic bubblesort algorithm on supplied data, using pre-allocated buffer.
- * 
- * @param data Pointer to data to be sorted.
- * @param n Number of elements to be sorted.
- * @param e_size Size of one element.
- * @param cmp Comparator function.
- * @param slot Pointer to scratch memory buffer e_size bytes long.
- * 
- */
-void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)
-{
-        bool done = false;
-        void * p;
-
-        while (!done) {
-                done = true;
-                for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
-                        if (cmp(p, p + e_size) == 1) {
-                                memcpy(slot, p, e_size);
-                                memcpy(p, p + e_size, e_size);
-                                memcpy(p + e_size, slot, e_size);
-                                done = false;
-                        }
-                }
-        }
-
-}
-
-/*
- * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
- */
-int int_cmp(void * a, void * b)
-{
-        return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
-}
-
-int uint8_t_cmp(void * a, void * b)
-{
-        return (* (uint8_t *) a > * (uint8_t *)b) ? 1 : (*(uint8_t *)a < * (uint8_t *)b) ? -1 : 0;
-}
-
-int uint16_t_cmp(void * a, void * b)
-{
-        return (* (uint16_t *) a > * (uint16_t *)b) ? 1 : (*(uint16_t *)a < * (uint16_t *)b) ? -1 : 0;
-}
-
-int uint32_t_cmp(void * a, void * b)
-{
-        return (* (uint32_t *) a > * (uint32_t *)b) ? 1 : (*(uint32_t *)a < * (uint32_t *)b) ? -1 : 0;
+        
+        return true;
 }
 

kernel/generic/src/main/kinit.c

@@ -107 +107 @@
         if (config.cpu_count > 1) {
                 waitq_initialize(&ap_completion_wq);
+                
                 /*
                  * Create the kmp thread and wait for its completion.
@@ -124 +125 @@
                 thread_join(thread);
                 thread_detach(thread);
-        }
-        
-        if (config.cpu_count > 1) {
+                
+                /*
+                 * For each CPU, create its load balancing thread.
+                 */
                 size_t i;
                 
-                /*
-                 * For each CPU, create its load balancing thread.
-                 */
                 for (i = 0; i < config.cpu_count; i++) {
                         thread = thread_create(kcpulb, NULL, TASK, THREAD_FLAG_WIRED, "kcpulb", true);
@@ -181 +180 @@
                 if (init.tasks[i].addr % FRAME_SIZE) {
                         printf("init[%" PRIs "].addr is not frame aligned\n", i);
+                        programs[i].task = NULL;
                         continue;
                 }

kernel/generic/src/main/main.c

@@ -104 +104 @@
 
 /** Lowest safe stack virtual address. */
-uintptr_t stack_safe = 0;               
+uintptr_t stack_safe = 0;
 
 /*
@@ -113 +113 @@
  */
 static void main_bsp_separated_stack(void);
+
 #ifdef CONFIG_SMP
 static void main_ap_separated_stack(void);
 #endif
 
-#define CONFIG_STACK_SIZE       ((1 << STACK_FRAMES) * STACK_SIZE)
+#define CONFIG_STACK_SIZE  ((1 << STACK_FRAMES) * STACK_SIZE)
 
 /** Main kernel routine for bootstrap CPU.
@@ -130 +131 @@
  *
  */
-void main_bsp(void)
+void __attribute__((no_instrument_function)) main_bsp(void)
 {
         config.cpu_count = 1;
@@ -151 +152 @@
                             init.tasks[i].size, config.stack_size);
         }
-
+        
         /* Avoid placing stack on top of boot allocations. */
         if (ballocs.size) {
@@ -170 +171 @@
 }
 
-
 /** Main kernel routine for bootstrap CPU using new stack.
  *
@@ -176 +176 @@
  *
  */
-void main_bsp_separated_stack(void) 
+void main_bsp_separated_stack(void)
 {
         /* Keep this the first thing. */
@@ -183 +183 @@
         version_print();
         
-        LOG("\nconfig.base=%#" PRIp " config.kernel_size=%" PRIs
-            "\nconfig.stack_base=%#" PRIp " config.stack_size=%" PRIs,
+        LOG("\nconfig.base=%p config.kernel_size=%" PRIs
+            "\nconfig.stack_base=%p config.stack_size=%" PRIs,
             config.base, config.kernel_size, config.stack_base,
             config.stack_size);
@@ -194 +194 @@
          * commands.
          */
-        LOG_EXEC(kconsole_init());
+        kconsole_init();
 #endif
         
@@ -201 +201 @@
          * starts adding its own handlers
          */
-        LOG_EXEC(exc_init());
+        exc_init();
         
         /*
          * Memory management subsystems initialization.
          */
-        LOG_EXEC(arch_pre_mm_init());
-        LOG_EXEC(frame_init());
+        arch_pre_mm_init();
+        frame_init();
         
         /* Initialize at least 1 memory segment big enough for slab to work. */
-        LOG_EXEC(slab_cache_init());
-        LOG_EXEC(sysinfo_init());
-        LOG_EXEC(btree_init());
-        LOG_EXEC(as_init());
-        LOG_EXEC(page_init());
-        LOG_EXEC(tlb_init());
-        LOG_EXEC(ddi_init());
-        LOG_EXEC(tasklet_init());
-        LOG_EXEC(arch_post_mm_init());
-        LOG_EXEC(arch_pre_smp_init());
-        LOG_EXEC(smp_init());
+        slab_cache_init();
+        sysinfo_init();
+        btree_init();
+        as_init();
+        page_init();
+        tlb_init();
+        ddi_init();
+        tasklet_init();
+        arch_post_mm_init();
+        arch_pre_smp_init();
+        smp_init();
         
         /* Slab must be initialized after we know the number of processors. */
-        LOG_EXEC(slab_enable_cpucache());
+        slab_enable_cpucache();
         
         printf("Detected %" PRIs " CPU(s), %" PRIu64" MiB free memory\n",
             config.cpu_count, SIZE2MB(zones_total_size()));
-
-        LOG_EXEC(cpu_init());
-        
-        LOG_EXEC(calibrate_delay_loop());
-        LOG_EXEC(clock_counter_init());
-        LOG_EXEC(timeout_init());
-        LOG_EXEC(scheduler_init());
-        LOG_EXEC(task_init());
-        LOG_EXEC(thread_init());
-        LOG_EXEC(futex_init());
+        
+        cpu_init();
+        
+        calibrate_delay_loop();
+        clock_counter_init();
+        timeout_init();
+        scheduler_init();
+        task_init();
+        thread_init();
+        futex_init();
         
         if (init.cnt > 0) {
                 size_t i;
                 for (i = 0; i < init.cnt; i++)
-                        LOG("init[%" PRIs "].addr=%#" PRIp ", init[%" PRIs
-                            "].size=%#" PRIs, i, init.tasks[i].addr, i,
+                        LOG("init[%" PRIs "].addr=%p, init[%" PRIs
+                            "].size=%" PRIs, i, init.tasks[i].addr, i,
                             init.tasks[i].size);
         } else
                 printf("No init binaries found.\n");
         
-        LOG_EXEC(ipc_init());
-        LOG_EXEC(event_init());
-        LOG_EXEC(klog_init());
-        LOG_EXEC(stats_init());
+        ipc_init();
+        event_init();
+        klog_init();
+        stats_init();
         
         /*
@@ -266 +266 @@
         if (!kinit_thread)
                 panic("Cannot create kinit thread.");
-        LOG_EXEC(thread_ready(kinit_thread));
+        thread_ready(kinit_thread);
         
         /*
@@ -276 +276 @@
 }
 
-
 #ifdef CONFIG_SMP
+
 /** Main kernel routine for application CPUs.
  *
@@ -296 +296 @@
          */
         config.cpu_active++;
-
+        
         /*
          * The THE structure is well defined because ctx.sp is used as stack.
@@ -311 +311 @@
         calibrate_delay_loop();
         arch_post_cpu_init();
-
+        
         the_copy(THE, (the_t *) CPU->stack);
-
+        
         /*
          * If we woke kmp up before we left the kernel stack, we could
@@ -326 +326 @@
 }
 
-
 /** Main kernel routine for application CPUs using new stack.
  *
@@ -338 +337 @@
          */
         timeout_init();
-
+        
         waitq_wakeup(&ap_completion_wq, WAKEUP_FIRST);
         scheduler();
         /* not reached */
 }
+
 #endif /* CONFIG_SMP */
 

kernel/generic/src/mm/as.c

@@ -116 +116 @@
 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)
 {
@@ -239 +234 @@
         
         spinlock_unlock(&asidlock);
+        interrupts_restore(ipl);
+
         
         /*
@@ -266 +263 @@
 #endif
         
-        interrupts_restore(ipl);
-        
         slab_free(as_slab, as);
 }
@@ -296 +291 @@
         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;
 }
 
@@ -327 +422 @@
                 return NULL;
         
-        ipl_t ipl = interrupts_disable();
         mutex_lock(&as->lock);
         
         if (!check_area_conflicts(as, base, size, NULL)) {
                 mutex_unlock(&as->lock);
-                interrupts_restore(ipl);
                 return NULL;
         }
@@ -357 +450 @@
         
         mutex_unlock(&as->lock);
-        interrupts_restore(ipl);
         
         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;
 }
 
@@ -376 +530 @@
 int as_area_resize(as_t *as, uintptr_t address, size_t size, unsigned int flags)
 {
-        ipl_t ipl = interrupts_disable();
         mutex_lock(&as->lock);
         
@@ -386 +539 @@
         if (!area) {
                 mutex_unlock(&as->lock);
-                interrupts_restore(ipl);
                 return ENOENT;
         }
@@ -398 +550 @@
                 mutex_unlock(&area->lock);
                 mutex_unlock(&as->lock);
-                interrupts_restore(ipl);
                 return ENOTSUP;
         }
@@ -410 +561 @@
                 mutex_unlock(&area->lock);
                 mutex_unlock(&as->lock);
-                interrupts_restore(ipl);
                 return ENOTSUP;
         }
@@ -422 +572 @@
                 mutex_unlock(&area->lock);
                 mutex_unlock(&as->lock);
-                interrupts_restore(ipl);
                 return EPERM;
         }
@@ -441 +590 @@
                  *
                  */
-                tlb_shootdown_start(TLB_INVL_PAGES, as->asid, area->base +
-                    pages * PAGE_SIZE, area->pages - pages);
+                ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES, as->asid,
+                    area->base + pages * PAGE_SIZE, area->pages - pages);
                 
                 /*
@@ -536 +685 @@
                 as_invalidate_translation_cache(as, area->base +
                     pages * PAGE_SIZE, area->pages - pages);
-                tlb_shootdown_finalize();
+                tlb_shootdown_finalize(ipl);
                 
                 page_table_unlock(as, false);
@@ -549 +698 @@
                         mutex_unlock(&area->lock);
                         mutex_unlock(&as->lock);
-                        interrupts_restore(ipl);
                         return EADDRNOTAVAIL;
                 }
@@ -558 +706 @@
         mutex_unlock(&area->lock);
         mutex_unlock(&as->lock);
-        interrupts_restore(ipl);
         
         return 0;
+}
+
+/** 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);
+        }
 }
 
@@ -573 +761 @@
 int as_area_destroy(as_t *as, uintptr_t address)
 {
-        ipl_t ipl = interrupts_disable();
         mutex_lock(&as->lock);
         
@@ -579 +766 @@
         if (!area) {
                 mutex_unlock(&as->lock);
-                interrupts_restore(ipl);
                 return ENOENT;
         }
@@ -590 +776 @@
          * Start TLB shootdown sequence.
          */
-        tlb_shootdown_start(TLB_INVL_PAGES, as->asid, area->base, area->pages);
+        ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES, as->asid, area->base,
+            area->pages);
         
         /*
@@ -637 +824 @@
          */
         as_invalidate_translation_cache(as, area->base, area->pages);
-        tlb_shootdown_finalize();
+        tlb_shootdown_finalize(ipl);
         
         page_table_unlock(as, false);
@@ -659 +846 @@
         
         mutex_unlock(&as->lock);
-        interrupts_restore(ipl);
         return 0;
 }
@@ -690 +876 @@
     as_t *dst_as, uintptr_t dst_base, unsigned int dst_flags_mask)
 {
-        ipl_t ipl = interrupts_disable();
         mutex_lock(&src_as->lock);
         as_area_t *src_area = find_area_and_lock(src_as, src_base);
@@ -699 +884 @@
                  */
                 mutex_unlock(&src_as->lock);
-                interrupts_restore(ipl);
                 return ENOENT;
         }
@@ -711 +895 @@
                 mutex_unlock(&src_area->lock);
                 mutex_unlock(&src_as->lock);
-                interrupts_restore(ipl);
                 return ENOTSUP;
         }
@@ -728 +911 @@
                 mutex_unlock(&src_area->lock);
                 mutex_unlock(&src_as->lock);
-                interrupts_restore(ipl);
                 return EPERM;
         }
@@ -777 +959 @@
                 sh_info_remove_reference(sh_info);
                 
-                interrupts_restore(ipl);
                 return ENOMEM;
         }
@@ -794 +975 @@
         mutex_unlock(&dst_as->lock);
         
-        interrupts_restore(ipl);
-        
         return 0;
 }
@@ -816 +995 @@
         };
 
-        ASSERT(interrupts_disabled());
         ASSERT(mutex_locked(&area->lock));
         
@@ -823 +1001 @@
         
         return true;
+}
+
+/** 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;
 }
 
@@ -844 +1048 @@
         unsigned int page_flags = area_flags_to_page_flags(flags);
         
-        ipl_t ipl = interrupts_disable();
         mutex_lock(&as->lock);
         
@@ -850 +1053 @@
         if (!area) {
                 mutex_unlock(&as->lock);
-                interrupts_restore(ipl);
                 return ENOENT;
         }
@@ -859 +1061 @@
                 mutex_unlock(&area->lock);
                 mutex_unlock(&as->lock);
-                interrupts_restore(ipl);
                 return ENOTSUP;
         }
@@ -889 +1090 @@
          *
          */
-        tlb_shootdown_start(TLB_INVL_PAGES, as->asid, area->base, area->pages);
+        ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES, as->asid, area->base,
+            area->pages);
         
         /*
@@ -936 +1138 @@
          */
         as_invalidate_translation_cache(as, area->base, area->pages);
-        tlb_shootdown_finalize();
+        tlb_shootdown_finalize(ipl);
         
         page_table_unlock(as, false);
@@ -978 +1180 @@
         mutex_unlock(&area->lock);
         mutex_unlock(&as->lock);
-        interrupts_restore(ipl);
         
         return 0;
@@ -1184 +1385 @@
 }
 
-/** 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.
@@ -1219 +1396 @@
 unsigned int as_area_get_flags(as_area_t *area)
 {
-        ASSERT(interrupts_disabled());
         ASSERT(mutex_locked(&area->lock));
 
@@ -1296 +1472 @@
 /** 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)
@@ -1309 +1485 @@
 }
 
-
-/** 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(interrupts_disabled());
-        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(interrupts_disabled());
-        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;
-}
-
 /** Return size of the address space area with given base.
  *
@@ -1486 +1497 @@
         size_t size;
         
-        ipl_t ipl = interrupts_disable();
         page_table_lock(AS, true);
         as_area_t *src_area = find_area_and_lock(AS, base);
@@ -1497 +1507 @@
         
         page_table_unlock(AS, true);
-        interrupts_restore(ipl);
         return size;
 }
@@ -1988 +1997 @@
 }
 
-/** 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.
@@ -2070 +2038 @@
 void as_get_area_info(as_t *as, as_area_info_t **obuf, size_t *osize)
 {
-        ipl_t ipl = interrupts_disable();
         mutex_lock(&as->lock);
         
@@ -2114 +2081 @@
         
         mutex_unlock(&as->lock);
-        interrupts_restore(ipl);
         
         *obuf = info;
@@ -2127 +2093 @@
 void as_print(as_t *as)
 {
-        ipl_t ipl = interrupts_disable();
         mutex_lock(&as->lock);
         
@@ -2150 +2115 @@
         
         mutex_unlock(&as->lock);
-        interrupts_restore(ipl);
 }
 

kernel/generic/src/mm/frame.c

@@ -1234 +1234 @@
 {
 #ifdef __32_BITS__
-        printf("#  base address frames       flags    free frames  busy frames\n");
-        printf("-- ------------ ------------ -------- ------------ ------------\n");
+        printf("[nr] [base addr] [frames    ] [flags ] [free frames ] [busy frames ]\n");
 #endif
 
 #ifdef __64_BITS__
-        printf("#  base address          frames      flags    free frames  busy frames\n");
-        printf("-- -------------------- ------------ -------- ------------ ------------\n");
+        printf("[nr] [base address    ] [frames    ] [flags ] [free frames ] [busy frames ]\n");
 #endif
         
@@ -1273 +1271 @@
                 bool available = zone_flags_available(flags);
                 
-                printf("%-2" PRIs, i);
+                printf("%-4" PRIs, i);
                 
 #ifdef __32_BITS__
-                printf("   %10p", base);
+                printf("  %10p", base);
 #endif
                 
 #ifdef __64_BITS__
-                printf("   %18p", base);
+                printf(" %18p", base);
 #endif
                 
@@ -1289 +1287 @@
                 
                 if (available)
-                        printf("%12" PRIs " %12" PRIs,
+                        printf("%14" PRIs " %14" PRIs,
                             free_count, busy_count);
                 

kernel/generic/src/mm/page.c

@@ -38 +38 @@
  * 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.
  *
  */
@@ -118 +118 @@
     unsigned int flags)
 {
-        ASSERT(interrupts_disabled());
         ASSERT(page_table_locked(as));
         
@@ -142 +141 @@
 void page_mapping_remove(as_t *as, uintptr_t page)
 {
-        ASSERT(interrupts_disabled());
         ASSERT(page_table_locked(as));
         
@@ -167 +165 @@
 pte_t *page_mapping_find(as_t *as, uintptr_t page)
 {
-        ASSERT(interrupts_disabled());
         ASSERT(page_table_locked(as));
         

kernel/generic/src/mm/slab.c

@@ -829 +829 @@
 void slab_print_list(void)
 {
-        printf("slab name        size     pages  obj/pg   slabs  cached allocated"
-            " ctl\n");
-        printf("---------------- -------- ------ -------- ------ ------ ---------"
-            " ---\n");
+        printf("[slab name       ] [size  ] [pages ] [obj/pg] [slabs ]"
+            " [cached] [alloc ] [ctl]\n");
         
         size_t skip = 0;
@@ -887 +885 @@
                 irq_spinlock_unlock(&slab_cache_lock, true);
                 
-                printf("%-16s %8" PRIs " %6u %8" PRIs " %6ld %6ld %9ld %-3s\n",
+                printf("%-18s %8" PRIs " %8u %8" PRIs " %8ld %8ld %8ld %-5s\n",
                     name, size, (1 << order), objects, allocated_slabs,
                     cached_objs, allocated_objs,

kernel/generic/src/mm/tlb.c

@@ -73 +73 @@
  * to all other processors.
  *
- * This function must be called with interrupts disabled.
- *
- * @param type Type describing scope of shootdown.
- * @param asid Address space, if required by type.
- * @param page Virtual page address, if required by type.
+ * @param type  Type describing scope of shootdown.
+ * @param asid  Address space, if required by type.
+ * @param page  Virtual page address, if required by type.
  * @param count Number of pages, if required by type.
  *
+ * @return The interrupt priority level as it existed prior to this call.
+ *
  */
-void tlb_shootdown_start(tlb_invalidate_type_t type, asid_t asid,
+ipl_t tlb_shootdown_start(tlb_invalidate_type_t type, asid_t asid,
     uintptr_t page, size_t count)
 {
+        ipl_t ipl = interrupts_disable();
         CPU->tlb_active = false;
         irq_spinlock_lock(&tlblock, false);
@@ -89 +90 @@
         size_t i;
         for (i = 0; i < config.cpu_count; i++) {
-                cpu_t *cpu;
-                
                 if (i == CPU->id)
                         continue;
                 
-                cpu = &cpus[i];
+                cpu_t *cpu = &cpus[i];
+                
                 irq_spinlock_lock(&cpu->lock, false);
                 if (cpu->tlb_messages_count == TLB_MESSAGE_QUEUE_LEN) {
@@ -122 +122 @@
         
 busy_wait:
-        for (i = 0; i < config.cpu_count; i++)
+        for (i = 0; i < config.cpu_count; i++) {
                 if (cpus[i].tlb_active)
                         goto busy_wait;
+        }
+        
+        return ipl;
 }
 
 /** Finish TLB shootdown sequence.
  *
+ * @param ipl Previous interrupt priority level.
+ *
  */
-void tlb_shootdown_finalize(void)
+void tlb_shootdown_finalize(ipl_t ipl)
 {
         irq_spinlock_unlock(&tlblock, false);
         CPU->tlb_active = true;
+        interrupts_restore(ipl);
 }
 

kernel/generic/src/proc/program.c

@@ -145 +145 @@
                 
                 program_loader = image_addr;
-                LOG("Registered program loader at 0x%" PRIp "\n",
+                LOG("Registered program loader at 0x%" PRIp,
                     image_addr);
                 

kernel/generic/src/proc/scheduler.c

@@ -193 +193 @@
                  * This improves energy saving and hyperthreading.
                  */
-                
-                 /* Mark CPU as it was idle this clock tick */
                 irq_spinlock_lock(&CPU->lock, false);
                 CPU->idle = true;
                 irq_spinlock_unlock(&CPU->lock, false);
-                
                 interrupts_enable();
+                
                 /*
                  * An interrupt might occur right now and wake up a thread.
@@ -386 +384 @@
         as_t *old_as = AS;
         
-        ASSERT(!THREAD || irq_spinlock_locked(&THREAD->lock));
+        ASSERT((!THREAD) || (irq_spinlock_locked(&THREAD->lock)));
         ASSERT(CPU != NULL);
         
@@ -457 +455 @@
                         irq_spinlock_unlock(&THREAD->sleep_queue->lock, false);
                         
-                        /*
-                         * Check for possible requests for out-of-context
-                         * invocation.
-                         *
-                         */
-                        if (THREAD->call_me) {
-                                THREAD->call_me(THREAD->call_me_with);
-                                THREAD->call_me = NULL;
-                                THREAD->call_me_with = NULL;
-                        }
-                        
                         irq_spinlock_unlock(&THREAD->lock, false);
-                        
                         break;
                 

kernel/generic/src/proc/the.c

@@ -33 +33 @@
 /**
  * @file
- * @brief       THE structure functions.
+ * @brief THE structure functions.
  *
  * This file contains functions to manage the THE structure.
@@ -43 +43 @@
 
 #include <arch.h>
-
 
 /** Initialize THE structure

kernel/generic/src/proc/thread.c

@@ -48 +48 @@
 #include <synch/spinlock.h>
 #include <synch/waitq.h>
-#include <synch/rwlock.h>
 #include <cpu.h>
 #include <str.h>
@@ -329 +328 @@
         thread->flags = flags;
         thread->state = Entering;
-        thread->call_me = NULL;
-        thread->call_me_with = NULL;
         
         timeout_initialize(&thread->sleep_timeout);
@@ -343 +340 @@
         thread->detached = false;
         waitq_initialize(&thread->join_wq);
-        
-        thread->rwlock_holder_type = RWLOCK_NONE;
         
         thread->task = task;
@@ -583 +578 @@
         
         (void) waitq_sleep_timeout(&wq, usec, SYNCH_FLAGS_NON_BLOCKING);
-}
-
-/** Register thread out-of-context invocation
- *
- * Register a function and its argument to be executed
- * on next context switch to the current thread. Must
- * be called with interrupts disabled.
- *
- * @param call_me      Out-of-context function.
- * @param call_me_with Out-of-context function argument.
- *
- */
-void thread_register_call_me(void (* call_me)(void *), void *call_me_with)
-{
-        irq_spinlock_lock(&THREAD->lock, false);
-        THREAD->call_me = call_me;
-        THREAD->call_me_with = call_me_with;
-        irq_spinlock_unlock(&THREAD->lock, false);
 }
 

kernel/generic/src/smp/ipi.c

@@ -47 +47 @@
  * @param ipi Message to broadcast.
  *
- * @bug The decision whether to actually send the IPI must be based
- *      on a different criterion. The current version has
- *      problems when some of the detected CPUs are marked
- *      disabled in machine configuration.
  */
 void ipi_broadcast(int ipi)
@@ -60 +56 @@
          */
         
-        if ((config.cpu_active > 1) && (config.cpu_active == config.cpu_count))
+        if (config.cpu_count > 1)
                 ipi_broadcast_arch(ipi);
 }

kernel/generic/src/synch/futex.c

@@ -37 +37 @@
 
 #include <synch/futex.h>
-#include <synch/rwlock.h>
+#include <synch/mutex.h>
 #include <synch/spinlock.h>
 #include <synch/synch.h>
@@ -65 +65 @@
 
 /**
- * Read-write lock protecting global futex hash table.
+ * Mutex protecting global futex hash table.
  * It is also used to serialize access to all futex_t structures.
  * Must be acquired before the task futex B+tree lock.
  */
-static rwlock_t futex_ht_lock;
+static mutex_t futex_ht_lock;
 
 /** Futex hash table. */
@@ -84 +84 @@
 void futex_init(void)
 {
-        rwlock_initialize(&futex_ht_lock);
+        mutex_initialize(&futex_ht_lock, MUTEX_PASSIVE);
         hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
 }
@@ -113 +113 @@
         uintptr_t paddr;
         pte_t *t;
-        ipl_t ipl;
         int rc;
         
-        ipl = interrupts_disable();
-
         /*
          * Find physical address of futex counter.
@@ -125 +122 @@
         if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
                 page_table_unlock(AS, true);
-                interrupts_restore(ipl);
                 return (unative_t) ENOENT;
         }
@@ -131 +127 @@
         page_table_unlock(AS, true);
         
-        interrupts_restore(ipl);        
-
         futex = futex_find(paddr);
 
@@ -156 +150 @@
         uintptr_t paddr;
         pte_t *t;
-        ipl_t ipl;
-        
-        ipl = interrupts_disable();
         
         /*
@@ -167 +158 @@
         if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) {
                 page_table_unlock(AS, true);
-                interrupts_restore(ipl);
                 return (unative_t) ENOENT;
         }
@@ -173 +163 @@
         page_table_unlock(AS, true);
         
-        interrupts_restore(ipl);
-
         futex = futex_find(paddr);
                 
@@ -200 +188 @@
          * or allocate new one if it does not exist already.
          */
-        rwlock_read_lock(&futex_ht_lock);
+        mutex_lock(&futex_ht_lock);
         item = hash_table_find(&futex_ht, &paddr);
         if (item) {
@@ -212 +200 @@
                         /*
                          * The futex is new to the current task.
-                         * However, we only have read access.
-                         * Gain write access and try again.
+                         * Upgrade its reference count and put it to the
+                         * current task's B+tree of known futexes.
                          */
-                        mutex_unlock(&TASK->futexes_lock);
-                        goto gain_write_access;
+                        futex->refcount++;
+                        btree_insert(&TASK->futexes, paddr, futex, leaf);
                 }
                 mutex_unlock(&TASK->futexes_lock);
-
-                rwlock_read_unlock(&futex_ht_lock);
         } else {
-gain_write_access:
+                futex = (futex_t *) malloc(sizeof(futex_t), 0);
+                futex_initialize(futex);
+                futex->paddr = paddr;
+                hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
+                        
                 /*
-                 * Upgrade to writer is not currently supported,
-                 * therefore, it is necessary to release the read lock
-                 * and reacquire it as a writer.
+                 * This is the first task referencing the futex.
+                 * It can be directly inserted into its
+                 * B+tree of known futexes.
                  */
-                rwlock_read_unlock(&futex_ht_lock);
-
-                rwlock_write_lock(&futex_ht_lock);
-                /*
-                 * Avoid possible race condition by searching
-                 * the hash table once again with write access.
-                 */
-                item = hash_table_find(&futex_ht, &paddr);
-                if (item) {
-                        futex = hash_table_get_instance(item, futex_t, ht_link);
-                        
-                        /*
-                         * See if this futex is known to the current task.
-                         */
-                        mutex_lock(&TASK->futexes_lock);
-                        if (!btree_search(&TASK->futexes, paddr, &leaf)) {
-                                /*
-                                 * The futex is new to the current task.
-                                 * Upgrade its reference count and put it to the
-                                 * current task's B+tree of known futexes.
-                                 */
-                                futex->refcount++;
-                                btree_insert(&TASK->futexes, paddr, futex,
-                                    leaf);
-                        }
-                        mutex_unlock(&TASK->futexes_lock);
-        
-                        rwlock_write_unlock(&futex_ht_lock);
-                } else {
-                        futex = (futex_t *) malloc(sizeof(futex_t), 0);
-                        futex_initialize(futex);
-                        futex->paddr = paddr;
-                        hash_table_insert(&futex_ht, &paddr, &futex->ht_link);
-                        
-                        /*
-                         * This is the first task referencing the futex.
-                         * It can be directly inserted into its
-                         * B+tree of known futexes.
-                         */
-                        mutex_lock(&TASK->futexes_lock);
-                        btree_insert(&TASK->futexes, paddr, futex, NULL);
-                        mutex_unlock(&TASK->futexes_lock);
-                        
-                        rwlock_write_unlock(&futex_ht_lock);
-                }
+                mutex_lock(&TASK->futexes_lock);
+                btree_insert(&TASK->futexes, paddr, futex, NULL);
+                mutex_unlock(&TASK->futexes_lock);
+                
         }
+        mutex_unlock(&futex_ht_lock);
         
         return futex;
@@ -324 +274 @@
         link_t *cur;
         
-        rwlock_write_lock(&futex_ht_lock);
+        mutex_lock(&futex_ht_lock);
         mutex_lock(&TASK->futexes_lock);
 
@@ -344 +294 @@
         
         mutex_unlock(&TASK->futexes_lock);
-        rwlock_write_unlock(&futex_ht_lock);
+        mutex_unlock(&futex_ht_lock);
 }
 

kernel/generic/src/sysinfo/stats.c

@@ -124 +124 @@
                 stats_cpus[i].active = cpus[i].active;
                 stats_cpus[i].frequency_mhz = cpus[i].frequency_mhz;
-                stats_cpus[i].busy_ticks = cpus[i].busy_ticks;
-                stats_cpus[i].idle_ticks = cpus[i].idle_ticks;
+                stats_cpus[i].busy_cycles = cpus[i].busy_cycles;
+                stats_cpus[i].idle_cycles = cpus[i].idle_cycles;
                 
                 irq_spinlock_unlock(&cpus[i].lock, true);

kernel/generic/src/time/clock.c

@@ -57 +57 @@
 #include <mm/frame.h>
 #include <ddi/ddi.h>
+#include <arch/cycle.h>
 
 /* Pointer to variable with uptime */
@@ -125 +126 @@
 }
 
+static void cpu_update_accounting(void)
+{
+        irq_spinlock_lock(&CPU->lock, false);
+        uint64_t now = get_cycle();
+        CPU->busy_cycles += now - CPU->last_cycle;
+        CPU->last_cycle = now;
+        irq_spinlock_unlock(&CPU->lock, false);
+}
+
 /** Clock routine
  *
@@ -136 +146 @@
         size_t missed_clock_ticks = CPU->missed_clock_ticks;
         
-        /* Account lost ticks to CPU usage */
-        if (CPU->idle)
-                CPU->idle_ticks += missed_clock_ticks + 1;
-        else
-                CPU->busy_ticks += missed_clock_ticks + 1;
-        
-        CPU->idle = false;
+        /* Account CPU usage */
+        cpu_update_accounting();
         
         /*
@@ -151 +156 @@
         size_t i;
         for (i = 0; i <= missed_clock_ticks; i++) {
+                /* Update counters and accounting */
                 clock_update_counters();
+                cpu_update_accounting();
+                
                 irq_spinlock_lock(&CPU->timeoutlock, false);