linux-kernel - Re: [PATCH 06/30] mm: kmem_alloc

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]

Message-ID: <4890C8BF.4050908@linux-foundation.org>
Date:	Wed, 30 Jul 2008 15:02:07 -0500
From:	Christoph Lameter <cl@...ux-foundation.org>
To:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
CC:	Pekka Enberg <penberg@...helsinki.fi>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	linux-kernel@...r.kernel.org, linux-mm@...ck.org,
	netdev@...r.kernel.org, trond.myklebust@....uio.no,
	Daniel Lezcano <dlezcano@...ibm.com>,
	Neil Brown <neilb@...e.de>
Subject: Re: [PATCH 06/30] mm: kmem_alloc_estimate()

Peter Zijlstra wrote:

>>> +/*
>>> + * Calculate the upper bound of pages requires to sequentially allocate @bytes
>>> + * from kmalloc in an unspecified number of allocations of nonuniform size.
>>> + */
>>> +unsigned kmalloc_estimate_variable(gfp_t flags, size_t bytes)
>>> +{
>>> +	int i;
>>> +	unsigned long pages;
>>> +
>>> +	/*
>>> +	 * multiply by two, in order to account the worst case slack space
>>> +	 * due to the power-of-two allocation sizes.
>>> +	 */
>>> +	pages = DIV_ROUND_UP(2 * bytes, PAGE_SIZE);
>> For bytes > PAGE_SIZE this doesn't look right (for SLUB). We do page
>> allocator pass-through which means that we'll be grabbing high order
>> pages which can be bigger than what 'pages' is here.
> 
> Satisfying allocations from a bucket distribution with power-of-two
> (which page alloc order satisfies) has a worst case slack space of:
> 
> S(x) = 2^n - (2^(n-1)) - 1, n = ceil(log2(x))
> 
> This can be seen for the cases where x = 2^i + 1.

The needed bytes for a kmalloc allocation with size > PAGE_SIZE is

get_order(size) << PAGE_SHIFT bytes.

See kmalloc_large().



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