Re: BTRFS free space handling still needs more work: Hangs again

[Robert White <rwhite@pobox.com>]

Semi off-topic questions...

On 12/27/2014 08:26 AM, Hugo Mills wrote:
>     This is... badly mistaken, at best. The problem of where to write a
> file into a set of free extents is definitely *not* an NP-hard
> problem. It's a P problem, with an O(n log n) solution, where n is the
> number of free extents in the free space cache. The simple approach:
> fill the first hole with as many bytes as you can, then move on to the
> next hole. More complex: order the free extents by size first. Both of
> these are O(n log n) algorithms, given an efficient general-purpose
> index of free space.

Which algorithm is actually in use?

Is any attempt made to keep subsequent allocations in the same data extent?

All of "best fit", "first fit", and "first encountered" allocation have 
terrible distribution graphs over time.

Without a knod to locality, discontiguous allocation will have 
staggeringly bad after-effects in terms of read-ahead.

>
>     The problem of placing file data isn't a bin-packing problem; it's
> not like allocating RAM (where each allocation must be contiguous).
> The items being placed may be split as much as you like, although
> minimising the amount of splitting is a goal.

How is compression and re-compression handled? If a linear extent is 
compressed to find its on-disk size in bytes, and then there isn't an 
extent large enough to fit it, it has to be cut, then recompressed, then 
searched again right?

How does the system look for the right cut? How iterative can this get? 
Does it always try cutting in half? Does it shave single bytes off the 
end? Does it add one byte at a time till it reaches the size of the 
extent its looking at?

Can you get down to a point where you are placing data in five or ten 
byte chunks somehow? (e.g. what's the smallest chunk you can place? 
clearly if I open a multi-megabyte file and update a single word or byte 
it's not going to land in metadata from my reading of the code.) One 
could easily end up with a couple million free extents of just a few 
bytes each, particularly if largest-first allocation is used.

The degenerate cases here do come straight from the various packing 
problems. You may not be executing any of those packing algorithms but 
once you ignore enough of those issues in the easy cases your free space 
will be a fine pink mist suspended in space. (both an explosion analogy 
and a reference to pink noise 8-) ).

>     I suspect that the performance problems that Martin is seeing may
> indeed be related to free space fragmentation, in that finding and
> creating all of those tiny extents for a huge file is causing
> problems. I believe that btrfs isn't alone in this, but it may well be
> showing the problem to a far greater degree than other FSes. I don't
> have figures to compare, I'm afraid.

>
>> I also don't know what kind of tool you are using, but it might be
>> repeatedly trying and failing to fallocate the file as a single
>> extent or something equally dumb.
>
>     Userspace doesn't as far as I know, get to make that decision. I've
> just read the fallocate(2) man page, and it says nothing at all about
> the contiguity of the extent(s) storage allocated by the call.

Yep, my bad. But as soon as I saw that "fio" was starting two threads, 
one doing random read/write and another doing sequential read/write, 
both on the same file, it set off my "not just creating a file" mindset. 
Given the delayed write into/through the cache normally done by casual 
file io, It seemed likely that fio would be doing something more 
aggressive (like using O_DIRECT or repeated fdatasync() which could get 
very tit-for-tat).

Compare that to a VM in which the guest operating system "knows" it has, 
and has used, its "disk space" internally, and the subsequent async 
activity of the monitor to push that activity out to real storage which 
is usually quite pathological... well you can get into some super 
pernicious behavior over write ordering and infinite retries.

So I was wrong about fallocate per-se, applications can be incredibly 
dumb. For instance a VM might think its _inconceivable_ to get an ENOSPC 
while rewriting data it's just read from a file it "knows" has no holes etc.

Given how lots of code doesn't even check the results of many function 
calls... how many times have you seen code that doesn't look at the 
return value of fwrite() or printf()? Or one that, if it does something 
like if (bytes_written < size) retry_remainder(); So sure I was 
imagining an fallocate() in a loop or something equally dumb. 8-)

>
>     Hugo.
>
> [snip]
>