linux-kernel - Re: [PATCH -mm v2 01/11] mm: track free size between VMAs in VMA rbtree

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Fri, 22 Jun 2012 12:02:59 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Rik van Riel <riel@...riel.com>
Cc:	linux-mm@...ck.org, akpm@...ux-foundation.org, aarcange@...hat.com,
	minchan@...il.com, kosaki.motohiro@...il.com, andi@...stfloor.org,
	hannes@...xchg.org, mel@....ul.ie, linux-kernel@...r.kernel.org,
	Rik van Riel <riel@...hat.com>
Subject: Re: [PATCH -mm v2 01/11] mm: track free size between VMAs in VMA
 rbtree

On Thu, 2012-06-21 at 17:57 -0400, Rik van Riel wrote:
> +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;
> +} 

If you introduce helpers like:

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;
}

You can write your largest free gap as:

unsigned long largest_gap(struct rb_node *node)
{
	unsigned long gap = gap_of(node);

	if (node->rb_left)
		gap = max(gap, max_gap_of(node->rb_left));
	if (node->rb_right)
		gap = max(gap, max_gap_of(node->rb_right));

	return gap;
}

And as shown, you can re-used those {max_,}gap_of() function in the
lookup function in the next patch.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/