* Slub Allocator: Why get_order(size * MAX_OBJS_PER_PAGE) - 1 in function slab_order()?
@ 2011-11-22 20:40 zhihua che
2011-11-23 2:53 ` David Rientjes
0 siblings, 1 reply; 6+ messages in thread
From: zhihua che @ 2011-11-22 20:40 UTC (permalink / raw)
To: linux-kernel
Hi, everyone,
I'm reading the kernel codes about slub allocator and I come
across a confusion. Precisely, I'm reading the initialization of the
slub allocator, kmem_cache_init(), and I find it needs call
calculate_sizes() to determine the order of a kmem_cache, given the
size of the object. In turn, it calls the get_order() to get a
possible order. The problem is, in the start of this function, why it
looks like this:
if (order_objects(min_order, size, reserved) > MAX_OBJS_PER_PAGE)
return get_order(size * MAX_OBJS_PER_PAGE) - 1;
I don't know why it subtracts one from the order returned by
get_order().
because as far as I know, get_order() returns the order the
slab requires to reserve size * MAX_OBJS_PER_PAGE memory. If it
subtracts 1 from the order returned by get_order(), the slab can't
store MAX_OBJS_PER_PAGE objects at all, instead it can only store half
of the MAX_OBJS_PER_PAGE objects.
Could you correct me if I think in a wrong way.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Slub Allocator: Why get_order(size * MAX_OBJS_PER_PAGE) - 1 in function slab_order()?
2011-11-22 20:40 Slub Allocator: Why get_order(size * MAX_OBJS_PER_PAGE) - 1 in function slab_order()? zhihua che
@ 2011-11-23 2:53 ` David Rientjes
[not found] ` <CABexPfEte8U5pVBJ=LvRKMY5=oW7F2vRjw_d9893Yy8W88hfDg@mail.gmail.com>
0 siblings, 1 reply; 6+ messages in thread
From: David Rientjes @ 2011-11-23 2:53 UTC (permalink / raw)
To: zhihua che; +Cc: Christoph Lameter, Pekka Enberg, linux-kernel
On Wed, 23 Nov 2011, zhihua che wrote:
> Hi, everyone,
> I'm reading the kernel codes about slub allocator and I come
> across a confusion. Precisely, I'm reading the initialization of the
> slub allocator, kmem_cache_init(), and I find it needs call
> calculate_sizes() to determine the order of a kmem_cache, given the
> size of the object. In turn, it calls the get_order() to get a
> possible order. The problem is, in the start of this function, why it
> looks like this:
>
> if (order_objects(min_order, size, reserved) > MAX_OBJS_PER_PAGE)
> return get_order(size * MAX_OBJS_PER_PAGE) - 1;
>
> I don't know why it subtracts one from the order returned by
> get_order().
> because as far as I know, get_order() returns the order the
> slab requires to reserve size * MAX_OBJS_PER_PAGE memory. If it
> subtracts 1 from the order returned by get_order(), the slab can't
> store MAX_OBJS_PER_PAGE objects at all, instead it can only store half
> of the MAX_OBJS_PER_PAGE objects.
> Could you correct me if I think in a wrong way.
I agree it looks confusing, but it's correct. SLUB can only store
MAX_OBJS_PER_PAGE because of limitations in struct page (see the comments
in include/linux/mm_types.h). So if the order will yield a page that
could fit _more_ than MAX_OBJS_PER_PAGE, we need to reduce the order by a
factor of 1.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Fwd: Slub Allocator: Why get_order(size * MAX_OBJS_PER_PAGE) - 1 in function slab_order()?
[not found] ` <CABexPfEte8U5pVBJ=LvRKMY5=oW7F2vRjw_d9893Yy8W88hfDg@mail.gmail.com>
@ 2011-11-23 6:59 ` zhihua che
2011-11-23 23:06 ` David Rientjes
0 siblings, 1 reply; 6+ messages in thread
From: zhihua che @ 2011-11-23 6:59 UTC (permalink / raw)
To: linux-kernel
---------- Forwarded message ----------
From: zhihua che <zhihua.che@gmail.com>
Date: 2011/11/23
Subject: Re: Slub Allocator: Why get_order(size * MAX_OBJS_PER_PAGE) -
1 in function slab_order()?
To: David Rientjes <rientjes@google.com>
I know what you mean, that is, a slab can only store no more than
MAX_OBJS_PER_PAGE, actually 0x7FFF, objects.
But get_order(size * MAX_OBJS_PER_PAGE) already returns the order
which reserves no_more_than size * MAX_OBJS_PER_PAGE memory. Right?
So I think there is no need to subtract one.
2011/11/23 David Rientjes <rientjes@google.com>:
> On Wed, 23 Nov 2011, zhihua che wrote:
>
>> Hi, everyone,
>> I'm reading the kernel codes about slub allocator and I come
>> across a confusion. Precisely, I'm reading the initialization of the
>> slub allocator, kmem_cache_init(), and I find it needs call
>> calculate_sizes() to determine the order of a kmem_cache, given the
>> size of the object. In turn, it calls the get_order() to get a
>> possible order. The problem is, in the start of this function, why it
>> looks like this:
>>
>> if (order_objects(min_order, size, reserved) > MAX_OBJS_PER_PAGE)
>> return get_order(size * MAX_OBJS_PER_PAGE) - 1;
>>
>> I don't know why it subtracts one from the order returned by
>> get_order().
>> because as far as I know, get_order() returns the order the
>> slab requires to reserve size * MAX_OBJS_PER_PAGE memory. If it
>> subtracts 1 from the order returned by get_order(), the slab can't
>> store MAX_OBJS_PER_PAGE objects at all, instead it can only store half
>> of the MAX_OBJS_PER_PAGE objects.
>> Could you correct me if I think in a wrong way.
>
> I agree it looks confusing, but it's correct. SLUB can only store
> MAX_OBJS_PER_PAGE because of limitations in struct page (see the comments
> in include/linux/mm_types.h). So if the order will yield a page that
> could fit _more_ than MAX_OBJS_PER_PAGE, we need to reduce the order by a
> factor of 1.
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Fwd: Slub Allocator: Why get_order(size * MAX_OBJS_PER_PAGE) - 1 in function slab_order()?
2011-11-23 6:59 ` Fwd: " zhihua che
@ 2011-11-23 23:06 ` David Rientjes
[not found] ` <CABexPfFFiNf8gj9EHnnWABmcK_wCiRkhxQObUnr0_oY2Dkp+JA@mail.gmail.com>
0 siblings, 1 reply; 6+ messages in thread
From: David Rientjes @ 2011-11-23 23:06 UTC (permalink / raw)
To: zhihua che; +Cc: Christoph Lameter, Pekka Enberg, linux-kernel
[-- Attachment #1: Type: TEXT/PLAIN, Size: 968 bytes --]
On Wed, 23 Nov 2011, zhihua che wrote:
> I know what you mean, that is, a slab can only store no more than
> MAX_OBJS_PER_PAGE, actually 0x7FFF, objects.
>
> But get_order(size * MAX_OBJS_PER_PAGE) already returns the order
> which reserves no_more_than size * MAX_OBJS_PER_PAGE memory. Right?
>
Yes, but it reserves too much memory if the conditional is true.
> So I think there is no need to subtract one.
>
If we didn't subtract one, then the order of a slab page would allow for
_more_ than MAX_OBJS_PER_PAGE to be allocated and that's not allowed
because of the restrictions in struct page.
Consider a page size of 4K and an object size of 8 bytes.
get_order(8 * 32767) would be 6, so that's a 4K * 2^6 = 256K slab page
without the subtraction and could allocate (256K * 1024 / 8) = 32768 which
is greater than MAX_OBJS_PER_PAGE and not allowed.
So we subtract one so the compound slab page is guaranteed to allocate
less than MAX_OBJS_PER_PAGE.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Slub Allocator: Why get_order(size * MAX_OBJS_PER_PAGE) - 1 in function slab_order()?
[not found] ` <CABexPfFFiNf8gj9EHnnWABmcK_wCiRkhxQObUnr0_oY2Dkp+JA@mail.gmail.com>
@ 2011-11-24 4:44 ` zhihua che
2011-11-24 4:55 ` zhihua che
0 siblings, 1 reply; 6+ messages in thread
From: zhihua che @ 2011-11-24 4:44 UTC (permalink / raw)
To: linux-kernel
2011/11/24 David Rientjes <rientjes@google.com>:
> On Wed, 23 Nov 2011, zhihua che wrote:
>
>> I know what you mean, that is, a slab can only store no more than
>> MAX_OBJS_PER_PAGE, actually 0x7FFF, objects.
>>
>> But get_order(size * MAX_OBJS_PER_PAGE) already returns the order
>> which reserves no_more_than size * MAX_OBJS_PER_PAGE memory. Right?
>>
>
> Yes, but it reserves too much memory if the conditional is true.
>
>> So I think there is no need to subtract one.
>>
>
> If we didn't subtract one, then the order of a slab page would allow for
> _more_ than MAX_OBJS_PER_PAGE to be allocated and that's not allowed
> because of the restrictions in struct page.
>
> Consider a page size of 4K and an object size of 8 bytes.
> get_order(8 * 32767) would be 6, so that's a 4K * 2^6 = 256K slab page
> without the subtraction and could allocate (256K * 1024 / 8) = 32768 which
> is greater than MAX_OBJS_PER_PAGE and not allowed.
>
> So we subtract one so the compound slab page is guaranteed to allocate
> less than MAX_OBJS_PER_PAGE.
Oh, sorry to bother you ... I guess I calculated a wrong result. I
repeat your and my example carefully and you're right.
Thanks very much for your patience :)
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Slub Allocator: Why get_order(size * MAX_OBJS_PER_PAGE) - 1 in function slab_order()?
2011-11-24 4:44 ` zhihua che
@ 2011-11-24 4:55 ` zhihua che
0 siblings, 0 replies; 6+ messages in thread
From: zhihua che @ 2011-11-24 4:55 UTC (permalink / raw)
To: linux-kernel
2011/11/24 zhihua che <zhihua.che@gmail.com>:
> 2011/11/24 David Rientjes <rientjes@google.com>:
>> On Wed, 23 Nov 2011, zhihua che wrote:
>>
>>> I know what you mean, that is, a slab can only store no more than
>>> MAX_OBJS_PER_PAGE, actually 0x7FFF, objects.
>>>
>>> But get_order(size * MAX_OBJS_PER_PAGE) already returns the order
>>> which reserves no_more_than size * MAX_OBJS_PER_PAGE memory. Right?
>>>
>>
>> Yes, but it reserves too much memory if the conditional is true.
>>
>>> So I think there is no need to subtract one.
>>>
>>
>> If we didn't subtract one, then the order of a slab page would allow for
>> _more_ than MAX_OBJS_PER_PAGE to be allocated and that's not allowed
>> because of the restrictions in struct page.
>>
>> Consider a page size of 4K and an object size of 8 bytes.
>> get_order(8 * 32767) would be 6, so that's a 4K * 2^6 = 256K slab page
>> without the subtraction and could allocate (256K * 1024 / 8) = 32768 which
>> is greater than MAX_OBJS_PER_PAGE and not allowed.
>>
>> So we subtract one so the compound slab page is guaranteed to allocate
>> less than MAX_OBJS_PER_PAGE.
>
> Oh, sorry to bother you ... I guess I calculated a wrong result. I
> repeat your and my example carefully and you're right.
>
> Thanks very much for your patience :)
>
I guess I find what I'm wrong with. I pick a 0x8000 instead of 0x7FFF
as my example, because I though it's convenient.
But the 0x8000, as a power of two, turned out to be a proper order 7,
which can store 0x8000 objects without subtracting one.
Whatever, I made a stupid mistake.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2011-11-24 4:55 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-11-22 20:40 Slub Allocator: Why get_order(size * MAX_OBJS_PER_PAGE) - 1 in function slab_order()? zhihua che
2011-11-23 2:53 ` David Rientjes
[not found] ` <CABexPfEte8U5pVBJ=LvRKMY5=oW7F2vRjw_d9893Yy8W88hfDg@mail.gmail.com>
2011-11-23 6:59 ` Fwd: " zhihua che
2011-11-23 23:06 ` David Rientjes
[not found] ` <CABexPfFFiNf8gj9EHnnWABmcK_wCiRkhxQObUnr0_oY2Dkp+JA@mail.gmail.com>
2011-11-24 4:44 ` zhihua che
2011-11-24 4:55 ` zhihua che
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).