Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Subject: Re: [PATCH] mm/vmalloc: randomize vmalloc() allocations
To:     David Laight <David.Laight@ACULAB.COM>,
        'Mike Rapoport' <rppt@kernel.org>
Cc:     "linux-hardening@vger.kernel.org" <linux-hardening@vger.kernel.org>,
        "akpm@linux-foundation.org" <akpm@linux-foundation.org>,
        "linux-mm@kvack.org" <linux-mm@kvack.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        Andy Lutomirski <luto@kernel.org>,
        Jann Horn <jannh@google.com>,
        Kees Cook <keescook@chromium.org>,
        Linux API <linux-api@vger.kernel.org>,
        Matthew Wilcox <willy@infradead.org>
References: <20201201214547.9721-1-toiwoton@gmail.com>
 <9d34fb0a-7aba-1e84-6426-006ea7c3d9f5@gmail.com>
 <20201203065801.GH751215@kernel.org>
 <2a672ff3df0c47538ed7d1974c864f0b@AcuMS.aculab.com>
From:   Topi Miettinen <toiwoton@gmail.com>
Message-ID: <3d20f41c-6c8e-755b-33b4-964b5cc5ac71@gmail.com>
Date:   Fri, 4 Dec 2020 12:58:12 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <2a672ff3df0c47538ed7d1974c864f0b@AcuMS.aculab.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

On 4.12.2020 1.15, David Laight wrote:
> From: Mike Rapoport
>> Sent: 03 December 2020 06:58
>>
>> On Wed, Dec 02, 2020 at 08:49:06PM +0200, Topi Miettinen wrote:
>>> On 1.12.2020 23.45, Topi Miettinen wrote:
>>>> Memory mappings inside kernel allocated with vmalloc() are in
>>>> predictable order and packed tightly toward the low addresses. With
>>>> new kernel boot parameter 'randomize_vmalloc=1', the entire area is
>>>> used randomly to make the allocations less predictable and harder to
>>>> guess for attackers.
> 
> Isn't that going to horribly fragment the available address space
> and make even moderate sized allocation requests fail (or sleep).

For 32 bit architecture this is a real issue, but I don't think for 64 
bits it will be a problem. You can't fragment the virtual memory space 
for small allocations because the resulting page tables will not fit in 
RAM for existing or near future systems.

For large allocations (directly mapping entire contents of TB sized NVME 
drives or a special application which needs 1GB huge pages) this could 
be a risk. Maybe this could be solved by reserving some space for them, 
or perhaps in those cases you shouldn't use randomize_vmalloc=1.

The method for reserving the large areas could something like below.

First, consider a simple arrangement of reserving high addresses for 
large allocations and low addresses for smaller allocations. The 
allocator would start searching downwards from high addresses for a free 
large block and upwards from low addresses for small blocks. Also the 
address space would be semi-rigidly divided to priority areas: area 0 
with priority for small allocations, area 1 with equal priority for both 
small and large, and area 2 where small allocations would be placed only 
as a last resort (which probably would never be the case).

The linear way of dividing the allocations would of course be very much 
non-random, so this could be improved with a pseudo-random scrambling 
function to distribute the addresses in memory. A simple example would 
be to randomly choose a value for one bit in the address for large 
allocations (not necessarily the most significant available but also 
large enough to align 1GB/TB sized allocations if needed), or a bit 
pattern across several address bits for non-even distribution.

The addresses would be also fully randomized inside each priority area.

The division would mean some loss of randomization. A simple rigid 
division of 50%/50% for small vs. large allocations would mean a loss of 
one bit but the above methods could help this. Dividing the address 
space less evenly would improve one side at the expense of the other. 
Cracking the scrambling function would reveal the bit(s) used for the 
division.

It would be nice to remove the current rigid division of the kernel 
address space (Documentation/x86/x86_64/mm.rst) and let the allocations 
be placed more randomly in the entire 47 bit address space. Would the 
above priority scheme (perhaps with a rigid priority for certain users) 
be good enough to allow this?

Even better would be to remove the use of highest bit for selecting 
kernel/user addresses but I suppose it would be a lot of work for 
gaining just one extra bit of randomness. There could be other effects 
though (good or bad).

-Topi

> I'm not even sure that you need to use 'best fit' rather than
> 'first fit'.
> 'best fit' is certainly a lot better for a simple linked list
> user space malloc.
> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
>