* 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
[parent not found: <CABexPfEte8U5pVBJ=LvRKMY5=oW7F2vRjw_d9893Yy8W88hfDg@mail.gmail.com>]
* 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
[parent not found: <CABexPfFFiNf8gj9EHnnWABmcK_wCiRkhxQObUnr0_oY2Dkp+JA@mail.gmail.com>]
* 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).