linux-kernel - Re: [PATCH 2.6.28 1/2] memory: improve find

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 for Android: free password hash cracker in your pocket

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

Date:	Thu, 22 Jan 2009 17:22:39 +0000 (GMT)
From:	Hugh Dickins <hugh@...itas.com>
To:	Daniel Lowengrub <lowdanie@...il.com>
cc:	linux-kernel@...r.kernel.org, linux-mm@...ck.org
Subject: Re: [PATCH 2.6.28 1/2] memory: improve find_vma

On Thu, 22 Jan 2009, Daniel Lowengrub wrote:
> The goal of this patch is to improve the efficiency of the find_vma
> function in mm/mmap.c. The function first checks whether the vma
> stored in the cache is the one it's looking for. Currently, it's
> possible for the cache to be correct and still get rejected because
> the function checks whether the given address is inside the vma in the
> cache, not whether the cached vma is the smallest one that's bigger
> than the address.  To solve this problem I turned the list of vma's
> into a doubly linked list, and using that list made a function that
> can check if a given vma is the one that find_vma is looking for.
> This gives a greater number of cache hits than the standerd method.
> The doubly linked list can be used to optimize other parts of the
> memory management as well.  I'll implement some of those possibilities
> in the next patch.
> Signed-off-by: Daniel Lowengrub <lowdanie@...il.com>

Do you have some performance figures to support this patch?
Some of the lmbench tests may be appropriate.

The thing is, expanding vm_area_struct to include another pointer
will have its own cost, which may well outweigh the efficiency
(in one particular case) which you're adding.  Expanding mm_struct
for this would be much more palatable, but I don't think that flies.

And it seems a little greedy to require both an rbtree and a doubly
linked list for working our way around the vmas.

I suspect that originally your enhancement would only have hit when
extending the stack: which I guess isn't enough to justify the cost.
But it could well be that unmapped area handling has grown more
complex down the years, and you get some hits now from that.

You mention using the doubly linked list to optimize some other parts
of mm too: I guess those interfaces where we have to pass around prev
would be simplified, are you thinking of those, or something else?

(I don't think we need unmap_vmas to go backwards!)

Hugh
--
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/