`On Mon, 2012-06-18 at 18:05 -0400, Rik van Riel wrote:> +       /* Find the left-most free area of sufficient size. */Just because there's nothing better than writing it yourself.. I triedwriting something that does the above. The below is the result, itdoesn't use your uncle functions and is clearly limited to twotraversals and thus trivially still O(log n). [ although I think with abit of effort you can prove the same for your version ].---static inline struct vm_area_struct *vma_of(struct rb_node *node){        return container_of(node, struct vm_area_struct, vm_rb);}static inline unsigned long max_gap_of(struct rb_node *node){        return vma_of(node)->free_gap;}static unsigned long gap_of(struct rb_node *node){        struct vm_area_struct *vma = vma_of(node);        if (!vma->vm_prev)                return vma->vm_start;        return vma->vm_start - vma->vm_prev->vm_end;}static bool node_better(struct rb_node *node, struct rb_node *best){        if (!best)                return true;        return vma_of(node)->vm_start < vma_of(best)->vm_start;}unsigned long find_leftmost_gap(struct mm_struct *mm, unsigned long len){        struct rb_node *node = mm->mm_rb.rb_node, *best = NULL, *tree = NULL;        /*         * Do a search for TASK_UNMAPPED_BASE + len, all nodes right of this         * boundary should be considered. Path nodes are immediate candidates,         * their right sub-tree is stored for later consideration in case         * the immediate path doesn't yield a suitable node.         */        while (node) {                if (vma_of(node)->vm_start - len >= TASK_UNMAPPED_BASE) {                        /*                         * If our node has a big enough hole, track it.                         */                        if (gap_of(node) > len && node_better(node, best))                                best = node;                        /*                         * In case we flunk out on the path nodes, keep track                          * of the right sub-trees which have big enough holes.                         */                        if (node->rb_right && max_gap_of(node-rb_right) >= len &&                            node_better(node->rb_right, tree))                                tree = node->rb_right;                        node = node->rb_left;                        continue;                }                node = node->rb_right;        }        if (best)                return vma_of(best)->vm_start - len;        /*         * Our stored subtree must be entirely right of TASK_UNMAPPED_BASE + len         * so do a simple search for leftmost hole of appropriate size.         */        while (tree) {                if (gap_of(tree) >= len && node_better(tree, best))                        best = tree;                if (tree->rb_left && max_gap_of(tree->rb_left) >= len) {                        tree = tree->rb_left;                        continue;                }                tree = tree->rb_right;        }        if (best)                return vma_of(best)->vm_start - len;        /*         * Ok, so no path node, nor right sub-tree had a properly sized hole         * we could use, use the rightmost address in the tree.         */        node = mm->mm_rb.rb_node;        while (node && node->rb_right)                node = node->rb_right;        return max(vma_of(node)->vm_end, TASK_UNMAPPED_BASE);}`