Patch in this message
 Date Fri, 29 Jun 2012 16:46:38 -0700 From Michel Lespinasse <> Subject Re: [PATCH -mm v2 01/11] mm: track free size between VMAs in VMA rbtree
`On Thu, Jun 21, 2012 at 05:57:05PM -0400, Rik van Riel wrote:>  /*> + * largest_free_gap - returns the largest free gap "nearby"> + *> + * This function is called when propagating information on the> + * free spaces between VMAs "up" the VMA rbtree. It returns the> + * largest of:> + *> + * 1. The gap between this VMA and vma->vm_prev.> + * 2. The largest gap below us and to our left in the rbtree.> + * 3. The largest gap below us and to our right in the rbtree.> + */> +static unsigned long largest_free_gap(struct rb_node *node)> +{> +	struct vm_area_struct *vma, *prev, *left = NULL, *right = NULL;> +	unsigned long largest = 0;> +> +	if (node->rb_left)> +		left = rb_to_vma(node->rb_left);> +	if (node->rb_right)> +		right = rb_to_vma(node->rb_right);> +> +	/* Calculate the free gap size between us and the VMA to our left. */> +	vma = rb_to_vma(node);> +	prev = vma->vm_prev;> +> +	if (prev)> +		largest = vma->vm_start - prev->vm_end;> +	else> +		largest = vma->vm_start;> +> +	/* We propagate the largest of our own, or our children's free gaps. */> +	if (left)> +		largest = max(largest, left->free_gap);> +	if (right)> +		largest = max(largest, right->free_gap);> +> +	return largest;> +}I second PeterZ's suggestion of having an helper functionstatic unsigned long free_gap(struct rb_node *node){	struct vm_area_struct *vma = rb_to_vma(node);	unsigned long gap = vma->vm_start;	if (vma->vm_prev)		gap -= vma->vm_prev->vm_end;	return gap;}Which you can then use to simplify the largest_free_gap() implementation.> +/*> + * Use the augmented rbtree code to propagate info on the largest> + * free gap between VMAs up the VMA rbtree.> + */> +static void adjust_free_gap(struct vm_area_struct *vma)> +{> +	rb_augment_erase_end(&vma->vm_rb, vma_rb_augment_cb, NULL);> +}> @@ -398,6 +454,10 @@ void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma,>  {>  	rb_link_node(&vma->vm_rb, rb_parent, rb_link);>  	rb_insert_color(&vma->vm_rb, &mm->mm_rb);> +	adjust_free_gap(vma);> +	/* Propagate the new free gap between next and us up the tree. */> +	if (vma->vm_next)> +		adjust_free_gap(vma->vm_next);>  }So this will work, and may be fine for a first implementation. However,the augmented rbtree support really seems inadequate here. What wewould want is for adjust_free_gap to adjust the node's free_gap aswell as its parents, and *stop* when it reaches a node that alreadyhas the desired free_gap instead of going all the way to the root asit does now. But, to do that we would also need rb_insert_color() toadjust free_gap as needed when doing tree rotations, and it doesn'thave the necessary support there.Basically, I think lib/rbtree.c should provide augmented rbtree supportin the form of (versions of) rb_insert_color() and rb_erase() being able tocallback to adjust the augmented node information around tree rotations,instead of using (conservative, overkill) loops to adjust the augmentednode information after the fact in all places that might have been affectedby such rotations. Doing it after the fact is necessarity overkill becauseit visits O(log N) nodes, while the number of rotations that might haveoccured is only O(1).I'm interested in this stuff, please CC me if you do a v3 :)-- Michel "Walken" LespinasseA program is never fully debugged until the last user dies.`

Last update: 2012-06-30 02:21    [W:0.219 / U:2.880 seconds]