[linux-mm-cc] Queries about Compcache allocator

[Leonidas .]

Hello All,

I am new here, stumbled across Compcache while using VMware player, got
fascinated by the idea, currently going through the documentation part.
Have following questions:

1. xvMalloc is a pool based allocator. Can xvMalloc be used as a
general purpose allocator replacing kmalloc
in case a kernel driver does many smaller but mostly similar sized
allocations? I have gone through the doc
which compares xvMalloc with SLOB and SLUB, I think it fits the bill in case.

2. Does xvMalloc take care of adjusting memory allocations from
appropriate zones depending on the memory
pressure? E.g. allocate from zone high mem only if zone normal is
depleted etc?

3. Out of curiosity, I was trying to compare Jemalloc Linux port and
xvMalloc user port. Jemalloc claims very good
performance in most cases and guarantees very less fragmentation in
heavily multithreaded/multicore environment.
Has it been considered? Any idea why it can/can not be used for
compcache purpose.

-Leo.

[Nitin Gupta]

Hi,

Post by Leonidas .
I am new here, stumbled across Compcache while using VMware player, got
fascinated by the idea, currently going through the documentation part.
1. xvMalloc is a pool based allocator. Can xvMalloc be used as a
general purpose allocator replacing kmalloc
in case a kernel driver does many smaller but mostly similar sized
allocations? I have gone through the doc
which compares xvMalloc with SLOB and SLUB, I think it fits the bill in case.

SLOB is hopeless. Please see this:
http://lkml.indiana.edu/hypermail/linux/kernel/0903.2/01240.html

For SLUB vs xvmalloc, you should consider that xvmalloc is, in its
current state,
not scalable at all while SLUB is much better in this aspect.

Also, xvmalloc was designed to work well under memory pressure (it always
grows pool with single pages etc) while SLUB internally allocates
higher order pages
to reduce fragmentation. This constraint might not be applicable for
your driver, so
cannot be counted as negative point for SLUB.

Lastly, if all the allocation are of (nearly) the same size then SLUB
might be same
as xvmalloc in terms of fragmentation since this is the case SLUB is
designed for.

Post by Leonidas .
2. Does xvMalloc take care of adjusting memory allocations from
appropriate zones depending on the memory
?pressure? E.g. allocate from zone high mem only if zone normal is
depleted etc?

It always requests highmem pages. So, the underlying page allocator
might supply highmem or "normal" page depending on what's available.

Post by Leonidas .
3. Out of curiosity, I was trying to compare Jemalloc Linux port and
xvMalloc user port. Jemalloc claims very good
?performance in most cases and guarantees very less fragmentation in
heavily multithreaded/multicore environment.
?Has it been considered? Any idea why it can/can not be used for
compcache purpose.

Various allocators were considered for compcache (not jemalloc though) but
none of the alternatives could satisfy all the requirements of compcache. Some
of which are:
1- Mem pool must be expanded using 0-order (single) pages since we need
to allocate under memory pressure (its a swap device). Under these conditions,
higher order allocation are almost guaranteed to fail.
1.1 Many allocators result in large fragmentation when this limit
is imposed (including SLUB).
2- We should be able to allocate from "highmem" -- this thing is
applicable only
for 32-bit systems with >1G of RAM (neither SLUB or SLOB allows this).


I have never gone though jemalloc details but if it satisfies above requirements
and also gives low fragmentation under these constraints then it can surely be
used for compcache.


Thanks,
Nitin

[Leonidas .]

Post by Nitin Gupta
Hi,

Post by Leonidas .
I am new here, stumbled across Compcache while using VMware player, got
fascinated by the idea, currently going through the documentation part.
1. xvMalloc is a pool based allocator. Can xvMalloc be used as a
general purpose allocator replacing kmalloc
in case a kernel driver does many smaller but mostly similar sized
allocations? I have gone through the doc
which compares xvMalloc with SLOB and SLUB, I think it fits the bill in case.

http://lkml.indiana.edu/hypermail/linux/kernel/0903.2/01240.html
For SLUB vs xvmalloc, you should consider that xvmalloc is, in its
current state,
not scalable at all while SLUB is much better in this aspect.
Also, xvmalloc was designed to work well under memory pressure (it always
grows pool with single pages etc) while SLUB internally allocates
higher order pages
to reduce fragmentation. This constraint might not be applicable for
your driver, so
cannot be counted as negative point for SLUB.
Lastly, if all the allocation are of (nearly) the same size then SLUB
might be same
as xvmalloc in terms of fragmentation since this is the case SLUB is
designed for.

Post by Leonidas .
2. Does xvMalloc take care of adjusting memory allocations from
appropriate zones depending on the memory
?pressure? E.g. allocate from zone high mem only if zone normal is
depleted etc?

It always requests highmem pages. So, the underlying page allocator
might supply highmem or "normal" page depending on what's available.

Yes, this makes lot of sense.

Post by Nitin Gupta

Post by Leonidas .
3. Out of curiosity, I was trying to compare Jemalloc Linux port and
xvMalloc user port. Jemalloc claims very good
?performance in most cases and guarantees very less fragmentation in
heavily multithreaded/multicore environment.
?Has it been considered? Any idea why it can/can not be used for
compcache purpose.

Various allocators were considered for compcache (not jemalloc though) but
none of the alternatives could satisfy all the requirements of compcache. Some
?1- Mem pool must be expanded using 0-order (single) pages since we need
to allocate under memory pressure (its a swap device). Under these conditions,
higher order allocation are almost guaranteed to fail.
? ? 1.1 Many allocators result in large fragmentation when this limit
is imposed (including SLUB).
?2- We should be able to allocate from "highmem" -- this thing is
applicable only
for 32-bit systems with >1G of RAM (neither SLUB or SLOB allows this).
I have never gone though jemalloc details but if it satisfies above requirements
and also gives low fragmentation under these constraints then it can surely be
used for compcache.
Thanks,
Nitin

I am not sure whether you would be able to have a look at Jemalloc performance
numbers and suitability for the project immediately. In case you have a look and
you find this as a possible candidate please let me know, I would be more than
willing to port it to kernel space.

-Leo.

[John McCabe-Dansted]

Post by Nitin Gupta
I have never gone though jemalloc details but if it satisfies above requirements
and also gives low fragmentation under these constraints then it can surely be
used for compcache.

AFAICT, Out-of-the-box jemalloc would be useless. From the excerpt
below, jemalloc is optimized for allocations less than 512 bytes,
while compcache will often want to allocate ~2k. Under compcache,
jemalloc would essentially act as a power of 2 slab allocator. It
wasn't obvious from skimming the paper whether it would be practical
to modify jemalloc to have "quantum-spaced" allocations up to 4k, and
I didn't check the source code.

http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf
page 5
--

Figure 4 shows the size classes for all allocation sizes.
? ? Category ? Subcategory ? ? ? Size
? ? Small
? ? ? Tiny
? ? ? ? ? ? ? ? ? ?2 ?B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?4 ?B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?8 ?B
? ? ? ? ? ? ? ? ? Quantum-spaced
? 16 ?B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 32 ?B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ?48 ?B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?480 ? B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?496 ? B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?512 ? B
? ? ? ? ? ? ? ? Sub-page
? ? ? ? ? ? ? ?1 ?kB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2 ?kB
? ? Large
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?4 ?kB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 8 ?kB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?16 ?kB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?256 ? kB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?512 ? kB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 ?MB
? ? Huge
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2 ?MB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4 ?MB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 6 ?MB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...
Figure 4: Default size classes, assuming runtime defaults, 4 kB pages
and a 16 byte quantum.
? It would be simpler to have no subcategories for small allocations
by doing away with the quantum-
spaced size classes. However, most applications primarily allocate
objects that are smaller than 512
bytes, and quantum spacing of size classes substantially reduces
average internal fragmentation.

--
John C. McCabe-Dansted

[Leonidas .]

Post by John McCabe-Dansted

Post by Nitin Gupta
I have never gone though jemalloc details but if it satisfies above requirements
and also gives low fragmentation under these constraints then it can surely be
used for compcache.

AFAICT, Out-of-the-box jemalloc would be useless. From the excerpt
below, jemalloc is optimized for allocations less than 512 bytes,
while compcache will often want to allocate ~2k. Under compcache,
jemalloc would essentially act as a power of 2 slab allocator. It
wasn't obvious from skimming the paper whether it would be practical
to modify jemalloc to have "quantum-spaced" allocations up to 4k, and
I didn't check the source code.
http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf
page 5
--
Figure 4 shows the size classes for all allocation sizes.
? ? Category ? Subcategory ? ? ? Size
? ? Small
? ? ? ? ? ? ?? ? ? Tiny
? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?2 ?B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?4 ?B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?8 ?B
? ? ? ? ? ? ? ? ? Quantum-spaced
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 16 ?B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 32 ?B
? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ?48 ?B
? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?480 ? B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?496 ? B
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?512 ? B
?? ? ? ? ? ? ? ? Sub-page
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?1 ?kB
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2 ?kB
? ? Large
? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ?4 ?kB
? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 8 ?kB
? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?16 ?kB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...
? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?256 ? kB
? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?512 ? kB
? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 ?MB
? ? Huge
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2 ?MB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4 ?MB
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 6 ?MB
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...
Figure 4: Default size classes, assuming runtime defaults, 4 kB pages
and a 16 byte quantum.
? It would be simpler to have no subcategories for small allocations
by doing away with the quantum-
spaced size classes. However, most applications primarily allocate
objects that are smaller than 512
bytes, and quantum spacing of size classes substantially reduces
average internal fragmentation.
--
John C. McCabe-Dansted
_______________________________________________
linux-mm-cc mailing list
linux-mm-cc at lists.laptop.org
http://lists.laptop.org/listinfo/linux-mm-cc

Hi,
Sorry for the late response.

Yes, you are right, Jemalloc is optimal for allocation pattern which
involves frequent
small allocations i.e. 512 bytes. So perhaps, this would be ideal for
scenarios which
which require this kind of allocation pattern i.e. may be for embedded
devices, as
per compcache requirement, this might not be ideal in its current form.

-Leo.