How to resize up beyond reserve?

[aganm]

If this is how to resize up within reserve:

unsigned char *buddy_buf = malloc(buddy_sizeof(4096));
unsigned char *data_buf = malloc(4096);
struct buddy *buddy = buddy_init(buddy_buf, data_buf, 2048);

buddy_resize(buddy, 4096); // Resize is within the limit of the reserve, no problem.

free(buddy_buf);
free(data_buf);

I want to resize up beyond the limit of the reserve, of which I will realloc the reserve appropriately. Something along the lines of:

unsigned char *buddy_buf = malloc(buddy_sizeof(4096));
unsigned char *data_buf = malloc(4096);
struct buddy *buddy = buddy_init(buddy_buf, data_buf, 4096);

// I want to grow my reserve. This pointer could be reallocated by realloc, possibly invalidating the buddy metadata?
data_buf = realloc(data_buf, 8192);

buddy_resize(buddy, 8192); // Resize is outside the limit of the original reserve.

free(buddy_buf);
free(data_buf);

Can this be done?

[spaskalev]

This can be done in both normal and embedded (buddy_init vs buddy_embed) modes but read bellow, there are caveats.

For normal mode you need to realloc both the metadata (buddy_buf) and arena (data_buf) and then call resize. This will work, however if realloc changed the base arena pointer all your allocations, while still valid from the point of the buddy, would have been shifted to a new location.

For embedded mode this works the same and there is a new function added to get the new address of the metadata after resize. The same caveat for existing allocations is valid - if the new base is different then all allocations would also be different!

In general, to avoid issues with moving pointers it is best to initialize the largest arena that you will need. In all modern operating systems just doing malloc will not cause memory use - only when you write to some page it will be actually allocated in physical memory and used.

Then, the buddy by default will try to allocate while minimizing fragmentation and bias to the left - so the actual used space will stay small if you allocations stay small. You can use the buddy_debug functions to print the state of the buddy and see what's allocated and what not.

[aganm]

Thank you!

[aganm]

I thought I had understood everything upon reading your answer, now I'm confused about something.

The original question was about how to resize the buddy allocator beyond the reserve. So I realloc my arena and my metadata. I understand that if realloc returns a new location, all my pointers will be shifted, so I need to patch my buddy_malloced pointers by shifting them by the same amount. But, when growing my arena and my metadata, if realloc returns new pointers, how does the buddy allocator know about these new pointers? The buddy allocator cannot know where these new locations are unless I pass it one way or another. Something is missing, may you point me in the right direction? Do I have to call buddy_init again? Since it's the only function which I can give the new realloced pointers to, but isn't that going to reset my arena? I don't want to lose my previous allocations from the arena. I'm confused.

// Create with initial size of 4096.
unsigned char *buddy_buf = malloc(buddy_sizeof(4096));
unsigned char *data_buf = malloc(4096);
struct buddy *buddy = buddy_init(buddy_buf, data_buf, 4096);

// I want to grow to 8192: "you need to realloc both the metadata (buddy_buf) and arena (data_buf) and then call resize"
buddy_buf = realloc(buddy_buf, buddy_sizeof(8192));  // this could be a new pointer that the buddy is not aware of
data_buf  = realloc(data_buf, data_buf, 8192);      // this could also be a new pointer that the buddy is not aware of

// What will the buddy resize into if it doesn't know the new location of the realloced buffers?
buddy_resize(buddy, 8192);               

// Destroy.
free(buddy_buf);
free(data_buf);

[spaskalev]

You are correct, the allocator will not know the new arena base pointer. Since this is not a common usecase there's not a function to set it but you can set it here

buddy_alloc/buddy_alloc.h

Line 490 in 4e836a6

unsigned char *main;

and provided the metadata is still at the same place it will work.

However, it is best to avoid this solution altogether - the risks are not worth it. Instead, use you OS functions, which provide better memory control than realloc.

Using functions like mmap you can reserve a large amount of virtual memory before that, where on a 64-bit system you have pretty much endless amount of virtual memory and then initialize the buddy at the start of it with a smaller size. You can even use buddy_embed constructors to not deal with the metadata, it will keep it at the end of the arena automatically. Say you need 4 pages (numbers [0-3]) initially but you have reserved 64 pages. Protect the 60 pages and don't write to them. The OS will not allocate physical memory to them.

Then, whenever you want to resize the allocator up unprotect some pages (e.g. pages [4-7] and resize the allocator. The arena will stay in the same place, your pointers will be valid and you will have more memory to use.