linux-kernel - Re: [PATCH v1] mm/vmalloc: add a node corresponding to cached_hole

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, 21 Jul 2017 04:39:48 -0700
From:   Matthew Wilcox <willy@...radead.org>
To:     Zhaoyang Huang <huangzhaoyang@...il.com>
Cc:     zhaoyang.huang@...eadtrum.com,
        Andrew Morton <akpm@...ux-foundation.org>,
        Michal Hocko <mhocko@...e.com>, Ingo Molnar <mingo@...nel.org>,
        zijun_hu <zijun_hu@....com>, Vlastimil Babka <vbabka@...e.cz>,
        Thomas Garnier <thgarnie@...gle.com>,
        "Kirill A. Shutemov" <kirill.shutemov@...ux.intel.com>,
        Andrey Ryabinin <aryabinin@...tuozzo.com>, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org, zijun_hu@...o.com
Subject: Re: [PATCH v1] mm/vmalloc: add a node corresponding to
 cached_hole_size

On Fri, Jul 21, 2017 at 06:01:41PM +0800, Zhaoyang Huang wrote:
> we just record the cached_hole_size now, which will be used when
> the criteria meet both of 'free_vmap_cache == NULL' and 'size <
> cached_hole_size'. However, under above scenario, the search will
> start from the rb_root and then find the node which just in front
> of the cached hole.
> 
> free_vmap_cache miss:
>       vmap_area_root
>           /      \
>        _next     U
>         /  (T1)
>  cached_hole_node
>        /
>      ...   (T2)
>       /
>     first
> 
> vmap_area_list->first->......->cached_hole_node->cached_hole_node.list.next
>                   |-------(T3)-------| | <<< cached_hole_size >>> |
> 
> vmap_area_list->......->cached_hole_node->cached_hole_node.list.next
>                                | <<< cached_hole_size >>> |
> 
> The time cost to search the node now is T = T1 + T2 + T3.
> The commit add a cached_hole_node here to record the one just in front of
> the cached_hole_size, which can help to avoid walking the rb tree and
> the list and make the T = 0;

Yes, but does this matter in practice?  Are there any workloads where
this makes a difference?  If so, how much?