ext2fs: Multi-block allocator with extent tree support and allocation lifecycle state machine

[pfg]

Summary

The idea was to have an allocator that uses better the locality information and would be better suited for extents and it ended being similar to what linux calls a multiblock allocator in a paper from 2005.
I have never seem the code and I doubt the specific implementation has any similarity.

Implement ext2_alloc_run() — a multi-block physical allocator that
reserves a contiguous physical block run and returns it via a
context-based state machine:

ALLOCATED -> MAPPED -> PUBLISHED -> ROLLED_BACK

ext2_alloc_run() enforces the reserved-block policy using struct
ucred *cred (NOCRED panics under INVARIANTS). Callers include
ext2_alloc() and ext4_new_blocks() for block allocation.

ext4_ext_split() uses scalar ext2_rollback_unpublished() for metadata
block cleanup (no context arrays). ext4_ext_insert_extent() handles
MAPPED -> PUBLISHED state transitions with the context on extent
insertion success.

The allocation context tracks only essential state:

• physical run (start + length)
• lifecycle state (4 values)
• accounting_applied (needed for ALLOCATED -> ROLLED_BACK)

Note 1: I used poolside/laguna-s-2.1:free AI to help the implementation of this algorithm,
It was instructed specifically NOT to take code from linux. Plus I had to review an fix it several times.
Note 2: I have a WIP implementation of softupdates on top of it.

Test Plan

I tested this with fsx : no failures.
I ran dbench with 8 clients and the results are marginally better, not too
impressive, but perhaps it had something to do that I did in a ZVOL,
which is the only thing based on a spinning disk here.
It is also likely this helps with fragmentation: ext3/4 has turned off reallocblk.

Oldalloc:
Throughput 3850.7 MB/sec 8 clients 8 procs max_latency=26.015 ms

Newalloc:
Throughput 3932.79 MB/sec 8 clients 8 procs max_latency=26.057 ms (with reallocblks)

[fsu]

I can see, that ext2_alloc_run() is called each time with request to allocate only single block.
On "inderects" side it could be seen from code:

• ext2_alloc.c:140
• ext2_balloc.c:335

On "extents" side. I placed the traces, tried different tests, including fsx with different op sizes, and I can see the only single block allocation requests for ext2_alloc_run().
To be honest, I do not exactly remember, why the only one block requested on each request.

So, it is needed to find test cases, when ext2_alloc_run() will be called for multiple blocks, or modify code to have it.

Also, I can see that, you tried to implement error handling in the ext2_extents.c, like the errors checks for ext4_ext_dirty().
It is good thing, because we does not have error handling here at all. But my opinion is, that we need to implement it firstly, and then it could be switched to this commit/rollback logic for multi-block allocation.

Some more: uma_zalloc warnings in the dmesg:
uma_zalloc_debug: zone "g_bio" with the following non-sleepable locks held:
exclusive sleep mutex EXT2FS (EXT2FS Lock) r = 0 (0xfffff801b37fdab8) locked @ /usr/src/sys/fs/ext2fs/ext2_alloc.c:494
stack backtrace:
#0 0xffffffff80cc43bc at witness_debugger+0x6c
#1 0xffffffff80cc5cbc at witness_warn+0x4bc
#2 0xffffffff8103d1ff at uma_zalloc_debug+0x3f
#3 0xffffffff8103cd47 at uma_zalloc_arg+0x27
#4 0xffffffff80b71d6d at g_vfs_strategy+0xcd
#5 0xffffffff80d25056 at bufwrite+0x246
#6 0xffffffff82a389ab at ext2_update+0x21b
#7 0xffffffff82a343e0 at ext4_ext_get_blocks+0x350
#8 0xffffffff82a2e4fa at ext2_balloc+0x14a
#9 0xffffffff82a3f675 at ext2_write+0x1f5
#10 0xffffffff812b355e at VOP_WRITE_APV+0xbe
#11 0xffffffff80d7cbca at vn_write+0x2ca
#12 0xffffffff80d746de at vn_io_fault+0x1ee
#13 0xffffffff80ccab02 at dofilewrite+0x82
#14 0xffffffff80cca3f2 at sys_write+0x132
#15 0xffffffff811d93dc at amd64_syscall+0x17c
#16 0xffffffff811a679b at fast_syscall_common+0xf8
Sleeping on "biowr" with the following non-sleepable locks held:
exclusive sleep mutex EXT2FS (EXT2FS Lock) r = 0 (0xfffff801b37fdab8) locked @ /usr/src/sys/fs/ext2fs/ext2_alloc.c:494
stack backtrace:
#0 0xffffffff80cc43bc at witness_debugger+0x6c
#1 0xffffffff80cc5cbc at witness_warn+0x4bc
#2 0xffffffff80c52393 at _sleep+0x63
#3 0xffffffff80d27e14 at bufwait+0xc4
#4 0xffffffff80d25064 at bufwrite+0x254
#5 0xffffffff82a389ab at ext2_update+0x21b
#6 0xffffffff82a343e0 at ext4_ext_get_blocks+0x350
#7 0xffffffff82a2e4fa at ext2_balloc+0x14a
#8 0xffffffff82a3f675 at ext2_write+0x1f5
#9 0xffffffff812b355e at VOP_WRITE_APV+0xbe
#10 0xffffffff80d7cbca at vn_write+0x2ca
#11 0xffffffff80d746de at vn_io_fault+0x1ee
#12 0xffffffff80ccab02 at dofilewrite+0x82
#13 0xffffffff80cca3f2 at sys_write+0x132
#14 0xffffffff811d93dc at amd64_syscall+0x17c
#15 0xffffffff811a679b at fast_syscall_common+0xf8

[pfg]

The AI concurred with your analysis. This patch gives better performance,

[pfg]

There is a new AI engine (Space Bunny) and after some request to simplify the comments and minor cleanups it came up with this:

"On the last open item — multi-block allocation. ext2_write caps xfersize at e2fs_fsize - blkoffset, so ext2_balloc can never see more than one block; that is stock FreeBSD behaviour, and changing it would mean allocating blocks the call cannot install. The real hook is VOP_REALLOCBLKS: the traditional path already allocates runs there, but ext2_reallocblks bails on IN_E4EXTENTS (ext2_alloc.c:626), so extent files only ever get one block at a time. Closing that means an ext4_reallocblks that inserts a multi-block extent instead of rewriting indirect pointers, through the ALLOCATED → MAPPED → PUBLISHED state machine. That is the one item I'd want your call on before writing, since it mutates the extent tree in the most delicate code in the module"

So it comes up to having to redo the reallocblk code (which this patch does but does not yet enable). I do have to focus on the allocator before looking again at softupdates which remains the desired next feature.

[pfg]

This just has some compilation cleanups.
I now have updated patches for softupdates+journaling on top of this.

[pfg]

I passed this through fsx, but more testing would be great.

[pho]

In D59866#1389549, @pfg wrote:

I passed this through fsx, but more testing would be great.

I ran stress2 tests for two hours without seeing any issues.
LGTM.

[pfg]

I went ahead and re-enabled reallocblk in my setup and it still works reliably with fsx.
The question is now who can commit this: I gave back my commit bit back more that a year a go :-/.