Rockbox

Regarding the first problem: If the move was successful, ‘block’ points to free space. That free space is be merged with alloc_end. And since the free space is bigger than block’s size it is also impossible that the new alloc_end and block’s alloc data overlap. But I spot that the code path is also used when there isn’t a hole but move should be done by shift (imagine 10k free space at the buffer start followed by a 5k alloc). This doesnt seem to be a problem, though.

Regarding the second, I think you spotted something. first_free needs to be updated indeed (if (first_free == target_block) first_free = new_free;).

Regarding the first problem, yes, if the move is successful, ‘block’ does point to free space, and yes, that free space is to be merged with alloc_end. Yes, it’s impossible for the new alloc_end and the moved block’s data at its new location to overlap. However, consider how at the bottom of the function, “ctx→alloc_end += shift;”. The alloc_end change in the if, plus the alloc_end change at the end can be too much.

In particular, here is what I observed with http://www.rockbox.org/tracker/task/12403?getfile=24414 . I had one single album in pictureflow in the 5G iPod sim, and I moved back and forth between the cover view and track list. There are two allocations. The first buflib_buffer_out() moves both to the end. The patched buflib_buffer_in() leaves them there and creates a free block in the added area at the start. When the second buflib_buffer_out() calls buflib_compact(), you have the following in the buffer: free, alloc1, alloc2. Both allocations can fit in the large free space. The for loop starts at the free block and sets shift to the size of the free block. Then, alloc1 is moved to the start of the free block, and all is well. Finally, alloc2 is moved, and alloc_end is set to the beginning of alloc2’s old location. Just before the function returns, you have that “ctx→alloc_end += shift;”. The proper amount for moving alloc_end is shift, which equals the size of the free block. If alloc_end was just moved by that amount, it would point right after alloc2. However, the alloc_end move in the if, plus the move at the end result in alloc_end pointing to the start of alloc2.

I agree with “if (first_free == target_block) first_free = new_free;”. I also think that when the shift fails, “if (first_free→val > target_block→val) first_free = target_block;” is a good idea. If the biggest hole is always used for moving, that should allow more blocks to be moved into holes. First fit or smallest fit could be even better, but it would slow down buflib_compact(). I don’t think that’s desirable now.

Here’s a restatement of another problem I tried to explain earlier, with examples.

Suppose you have:
free, alloc1 (unmovable), alloc2 (movable into free), free past alloc_end
Here, the code that moves alloc_end too much in the first problem:
if (ctx→alloc_end == next_block)
ctx→alloc_end = block;
will actually save the situation, setting alloc_end to the former start of alloc2, or just after alloc1:
alloc2 moved, remains of free, alloc1, free past alloc_end

But, suppose you instead have:
free, alloc1 (unmovable), alloc2, alloc3, free past alloc_end
Suppose both alloc2 and alloc3 are movable and fit into free. You end up with
alloc2 moved, alloc3 moved, remains of free, alloc1, alloc2 original, free past alloc_end
Here, shift remains at zero, and alloc_end is only moved via the “if” shown above.

I see. So the problem is that the hole-filling code runs when the shift code should. i thought swapping both paths (so shifting takes precedence) but that has a problem: The hole-filling will stop once there’s free space after something unmovable.

Perhaps that is not as bad as it sounds. I can’t imagine of a simple solution right now.

“I also think that when the shift fails, “if (first_free→val > target_block→val) first_free = target_block;” is a good idea.”

Nah, first_free should point to the first free block only. And I dont think we need to handle other holes than the first one (to keep things simple) even if bigger.

The attached patch should fix both isses I hope.

- I removed setting alloc_end explicitely at all, and instead make sure that shift is correct, fixing another potential bug (if a hole-fill was successful, the new free block wasn’t added to shift, so blocks after this don’t get moved properly).
- Implemented the if (first_free == target_block) first_free = new_free; suggestion.

Note: I added a larger comment. Perhaps even more can be said.
Note2: I explicitely kept hole handling simple, i.e. track only one hole (the first one, only starts tracking another one if the first was filled completely). As holes are hacky and rather rare, I think this should be sufficient.
Note3: I only tested if the patch compiles, not really on target.

Thanks for your very valuable investigation.

   buflib.c.vc.diff (3.7 KiB)

buflib.c.vc.diff looks pretty good. It works well in the sim, even in pictureflow with buflib_buffer_in_no_moving.patch from  FS#12403 . I can’t think of how this could mess up in terms of correctness. I can just think of two efficiency issues:

1) If a block could be either moved or shifted, but is actually unmovable, that results in two failed move_block() calls. I think the first failed move_block() call is enough to assume the block is not movable. This is probably very minor because I don’t expect much code to be executed in block move callbacks. The if statements could be joined together with else (also removing need for continue) if the hole filling code handled failed moves.

2) I suggest a change like this after a failed move:
if (hole == NULL || hole→val > target_block→val)
hole = target_block;
It’s better if hole points to a bigger free area. That means more blocks can fit in it, potentially compacting the buffer more. For example, “big hole, unmovable, small hole, unmovable, only fits in big hole” can only be compacted with that added if. The only advantage of only filling the most recent hole is slightly smaller code size. From a correctness standpoint, it doesn’t matter what hole is being filled, as long as it’s a real hole, with an unmovable block after it.

I like how you cleanly split up the function into hole filling and shifting. That makes it easier to understand and reduces the potential for errors. Thanks for the patch.

RE 1) Okay. Let’s make the continue (the first one, the second one in the patch is unnecessary entirely) unconditionally of the move_block result. I’m not sure I understand how you want to merge them (also wouldnt that break the clean split up you appreciate?). The shift path is taken by default, because finding a hole there actually enables the hole filing strategy.

RE 2) First of all, the example code makes the hole smaller :) Second, I’m not convinced that the filling biggest hole is the best strategy. I’n not even sure what *the* best is without lots of complications. We have to remember the purpose of compaction: Maximize contiguous free space to enable to biggest allocation possible to succeed. This is done by making all blocks contiguous so the free space at the end is maximized. If that’s not possible it’s tried to make them as contiguous as possible by moving blocks across unmovable buffers. This is already a work around and perhaps weak strategy.

With the purpose in mind, it’s even better to have a small hole and a big hole instead of two medium size holes. So always filling the biggest hole is not ideal either.

In my patch it’s not the most recent hole that’s filled. It’s the first found. The next one is only taken if the first one has been filled completely. The case you draw is handled in the patch in the way you propose.
FWIW, the case you draw is really a bad case. If something stuffs lots of unmovable and only little movable allocs to buflib it’s purpose is defeated. So I’d rather not like to think of such cases or try very hard to handle them appropriately.

I’ve attached a patch with your changes plus my changes relating to 1).

Added else statements ensure that if hole filling block_move() fails, shifting will not be attempted on that same block. Continue moves on to the next block when block is free, the block_move() succeeds, or there’s no suitable place for moving the block,

Only a failing move_block() results in execution of the new “if (shift)” at the bottom. The creation of a hole is handled within that if. (The code inside could be reached by a goto if the shift move_block() fails, but I don’t think the unnecessary “if (shift)” in that case is a problem.)

Note that even when moving into a hole, you could still have shift < 0. For example, consider “hole, unmovable block, free block, unmovable block that can fit in hole”. In buflib.c.vc.diff, after the move_block() trying to put the block in the hole fails, a second attempt is made using shift, and finally, that failure is handled. My code avoids the second move_block() attempt and assumes the block is unmovable. Theoretically, the move callback could care about the destination address and only deny moves to some locations, but I don’t expect this in practice. If you disagree, then buflib.c.vc.diff is better.

Regarding 2) I was thinking that buflib_compact() should move alloc_end toward buf_start as much as possible. That is the best strategy for buflib_buffer_out(). I agree that when compacting to allow the biggest possible allocation, filling the biggest hole can be bad.

I don’t know what is the best hole to fill. It’s possible that there’s no fast and optimal algorithm for this. I don’t like just filling the first hole, because then a small hole at the start can disable hole filling. I guess filling the most recently created hole is ok.

buflib.c.vc.diff fills the most recently created hole. Holes are formed when move_block() fails and shift < 0. That always leads to “hole = target_block;”. I retained that behaviour in this patch.

Updating of val at newly formed free space after a successful move now seems unnecessary, because a correct shift value allows this to be handled later. After a hole is formed due to an unmovable block, its val will be initialized properly. At the end, alloc_end will be initialized properly.

It seems the return value may be wrong. Consider these two lines:
bool ret = handle_table_shrink(ctx); (near the start)
return ret || shift; (at the end)
This means the return value is true if and only if the space at the end, between alloc_end and the handles, is increased. It does not consider the possibility that the biggest free space is a hole that has been enlarged, so it’s possible the return value is false, but an allocation which couldn’t succeed before can now succeed. I didn’t address this in my patch.

   buflib_compact-v2.patch (4.6 KiB)

Sorry, but TBH I don’t find your changes are an improvement over my patch. It adds a lot of continues, the separation between hole-filing and move-by-shift is not as clear anymore and I didn’t yet understand why you separated out the second if (shift) block.

I re-attach my patch with few fixes. It avoids the second try to move_block() and fixes your finding about the wrong return value and avoids to update new_free→val as you found it’s unnecessary.

You were right. My patch did indeed the most recent hole. That was unintended. But if you say that’s OK and we both don’t know the best strategy I suggest we just keep that for now (it’s quite academic anyway, as Rockbox doesnt have more than one hole [of course we try to not think about how rockbox uses it too much so buflib can be as generalized as possible]).

RE 2) buflib_buffer_out() is low priority. It’s a strange function anyway in my book. Maximizing the allocatable memory is surely more important isnt it?

I hope we can sort this out soon so solution can perhaps even be shipped in 3.10.

   buflib.c.vc-3.diff (4.4 KiB)

My second if (shift) block was doing the same thing you’re doing with the “movable” variable. Yes, your way looks better.

When the return value is true, it doesn’t mean that the largest block of free space after compacting is larger than the largest block of free space before compacting. In other words, it doesn’t mean that some allocation which couldn’t succeed before can succeed now. That can lead to a pointless attempt to allocate. I guess that’s ok.

Yeah, don’t concern yourself with optimizing this for buflib_buffer_out(). Only pictureflow uses that, and it doesn’t depend on any unique properties of the function. A buflib_compact() followed by a buflib_alloc_maximum() would accomplish the same thing as far as pictureflow is concerned. Also, all allocations in pictureflow are movable, so compacting is easy.

buflib.c.vc-3.diff looks good. Yes, putting this fix in 3.10 is a good idea. However, I hope at least one other person will look at it before it’s committed to the branch. It’s good to be extra-sure about this. I wouldn’t want to introduce instability into 3.10, and even in trunk, bugs in buflib could cause weird issues that are hard to track down.

(BTW. I see a problem with my buflib_compact-v2.patch: I shouldn’t have moved “intptr_t hlen = -hole→val;” after the move_block(). I’m not going to bother creating a fixed version because that patch won’t be used anyways, and buflib.c.vc-3.diff is better)