FS#12409 - problems with buflib_compact()
Opened by Boris Gjenero (dreamlayers) - Sunday, 27 November 2011, 01:29 GMT
Last edited by Boris Gjenero (dreamlayers) - Monday, 05 December 2011, 17:41 GMT
There seem to be several problems in r31061 buflib_compact() in firmware/buflib.c. I just created one tracker entry because this all involves just one function and a solution may address multiple issues.
The first problem I observed means a block ending at ctx->alloc_end may be lost:
When a block ends at ctx->alloc_end and only the hole filling strategy is used. Free blocks add to shift, and that is the proper amount for changing ctx->alloc_end. The change is made at the end of the function, via "ctx->alloc_end += shift". However, after a block is moved successfully to fill a hole, this code is executed:
if (ctx->alloc_end == next_block)
ctx->alloc_end = block;
As a result, at the end of the function, ctx->alloc_end points to the start of the last block.
It seems like other things can go wrong in the interaction between hole filling and moving by shift.
A failed attempt to move the allocation by shift will reset shift to 0, but the possibility remains that other blocks after the unmovable block can be moved into free space at first_free. Those moves won't increase shift. As a result, ctx->alloc_end may end up wrong, and blocks moved by shift won't be moved as much as possible. Perhaps the two lines I pasted above try to fix ctx->alloc_end in this situation, but they're not always the right solution.
A successful move by shift doesn't update first_free. That shouldn't lead to a crash and it just means buflib_compact() won't compact the buffer as much as possible. There are two possibilities:
If the block was shifted to start at first_free, then first_free->val is now positive and the hole filling code won't run anymore.
If the block was shifted into another hole, then free space may remain at first_free, and blocks may be moved into it.
In either case, any free space after a shifted block is only usable for shifting the next block, and unmovable blocks result in holes which won't be filled by moving other blocks into them.
Monday, 05 December 2011, 17:41 GMT
Reason for closing: Fixed
Additional comments about closing: Fixed by Thomas Martitz (kugel.) in r31101. Thanks!