microsoft / mimalloc

mimalloc is a compact general purpose allocator with excellent performance.
MIT License
9.74k stars 791 forks source link

Block sizes for huge pages seem inconsistent #868

Closed Zoxc closed 3 months ago

Zoxc commented 3 months ago

Block sizes for huge pages (xblock_size) seem inconsistent. MI_HUGE_OBJ_SIZE_MAX is used as the max block size on creation, otherwise the smaller real value is used. However checking for huge pages compares the block size to MI_LARGE_OBJ_SIZE_MAX + word size, a different value. When freeing a huge page, mi_page_queue_of can return the wrong queue for huge pages when the block size is below or equal to MI_LARGE_OBJ_SIZE_MAX.

daanx commented 3 months ago

Hi @zoxc -- thanks for bringing this up; I think it is not a bug but nevertheless I agree the naming and use is inconsistent. In particular, the name MI_HUGE_BLOCK_SIZE is confusing as it is just a large value used in xblock_size to signify that we need to calculate the block size from the segment size (for very large allocations). But it is orthogonal to the block actually being huge as > MI_LARGE_OBJ_SIZE_MAX. And as you saw, the MI_BIN_HUGE can contain either huge or large blocks. This really need to be fixed/clarified.

I will go through and rename some of these and add further comments, and check for possible bugs in particular for blocksizes around MI_LARGE_OBJ_SIZE_MAX (on first glance it looks actually ok though) Thanks!

Zoxc commented 3 months ago

The specific case I'm worried about is when creating a huge page for an allocation with small size and high alignment.

When allocating it will use unconditionally use MI_HUGE_OBJ_SIZE_MAX to pick the queue to use, but when freeing using mi_page_queue_of it will instead use page->xblock_size which will result in a different queue.

I'm also kind of wondering why MI_HUGE_OBJ_SIZE_MAX isn't 0 or -1 if it just represents an unknown block size?

daanx commented 3 months ago

Ah I see. Just to clarify, you mean MI_HUGE_BLOCK_SIZE instead of MI_HUGE_OBJ_SIZE_MAX. (since dev-slice uses a different value for MI_HUGE_BLOCK_SIZE (I should make this consistent as well)).

Hmm, I think you are right but I need to look into it in more detail. I consider it a bug but I think it actually works as it is because such special huge allocation with a small size but large alignment will always consist of a single block in a single page and thus it will be in the BIN_FULL queue when it is freed which is checked for in mi_page_queue_of. So, I think it actually works, but still, it would be better to maintain a stronger invariant. I need to think about this a bit more.

There is no special reason I think to not use ~0 (as it is unsigned) -- maybe 0 is used already for uninitialized pages.

btw. nice you try to rewrite this in Rust !

daanx commented 3 months ago

Thanks for the feedback; I made various improvements including an is_huge field in the page to ensure the correct page queue is used.