Now I need to understand the sweep function and how it handles the run-length compression of free space. Let me trace through the logic carefully.
The sweep function processes a pool. Each block in the pool has a header. The key macros are:
- `POOL_FREE_HEADER(wosize)` = `Make_header(wosize, No_scan_tag, NOT_MARKABLE)` — creates a header for a free block where `wosize` is the number of *additional* contiguous free blocks that follow- `POOL_BLOCK_FREE_HD(hd)` checks if a header indicates a free block
- `Wosize_hd(hd)` extracts the wosize from the header
- `Wosize_hp(p)` extracts the wosize from the header at address p
- `Whsize_hd(hd)` extracts the "header size" = wosize + 1
The critical observation is the loop advancement. There are two `p +=` statements:
Line 644: `p += wh * Wosize_hd(hd);` — this skips the additional free blocks (the "RLE" part)
Line 650: `p += Whsize_hd(hd);` — this advances past the current block (including its header)
Wait, but `Whsize_hd(hd)` for a free block header with `Wosize_hd(hd) = N` would be `N + 1`. So the advance at line 650 for a free block would be `N + 1`, not `wh` (the block size).
Hmm wait, I think I'm confusing things. Let me re-read the header semantics.
For a free block header:
- `Make_header(wosize, No_scan_tag, NOT_MARKABLE)` where `wosize` represents the number of *contiguous free blocks that follow* this one.
So when iterating through blocks:
- Line 644: `p += wh * Wosize_hd(hd);` — skip past the `Wosize_hd(hd)` additional free blocks (each of size `wh`)
- Line 650: `p += Whsize_hd(hd);` — this advances past the current block... but wait, for a free block with `Wosize_hd(hd) = N`, `Whsize_hd(hd) = N + 1`. That doesn't make sense for the block size.
Actually wait, let me re-read the comment at line 643: "add the free blocks following this block, skipping over them". So line 644 skips the additional free blocks.
But then line 650 `p += Whsize_hd(hd);` — for a free block, `Whsize_hd(hd) = Wosize_hd(hd) + 1`. But wait, this is always executed (it's outside the if/else), so for ALL blocks (free or live):
- For a live block: `p += Whsize_hd(hd)` which is `Wosize_hd(hd) + 1` — the actual block size including header. This is correct.
- For a free block: `p += Whsize_hd(hd)` = `Wosize_hd(hd) + 1`
Hmm but that doesn't make sense for a free block. For a free block, the "wosize" in the header is the number of additional contiguous free blocks, not the actual object size. So `Whsize_hd(hd)` for a free block with wosize=3 would be 4, which isn't the actual size of the block.
Wait, I think I'm confusing myself. Let me look again.
For a free block header `POOL_FREE_HEADER(wosize) = Make_header(wosize, No_scan_tag, NOT_MARKABLE)`:
- The wosize field stores the count of contiguous free blocks *after* this one.
But when we process this block in the sweep loop:
1. `p += wh * Wosize_hd(hd);` (line 644) — skips the extra free blocks
2. `p += Whsize_hd(hd);` (line 650) — should advance by the actual block size
But `Whsize_hd(hd) = Wosize_hd(hd) + 1`, which for a free block with wosize=N would be N+1, not `wh`.
This is wrong! The correct advance for the current free block should be `wh` (the sizeclass width), not `Whsize_hd(hd)`.
Actually wait, let me re-read more carefully. After line 644:
- If the block is free with wosize=N, we first skip N * wh positions (the N additional free blocks)
- Then at line 650, we add `Whsize_hd(hd) = N + 1`
Total advance = N * wh + N + 1 = N * (wh + 1) + 1
Hmm, that doesn't seem right either. For a single free block (N=0), the advance would be 1, which is just the header. But blocks are `wh` wide.
Actually wait, I think I'm wrong about what `Whsize_hd` does for free blocks. Let me check.
Actually, for the purpose of this loop, the wosize in the free header is used to encode the count of additional free blocks. So:
- A newly created free block from garbage has `wosize = 0` (no additional free blocks)
- When two adjacent free blocks are merged, the first one's wosize is increased
But the critical issue is: after line 644, `p` is already advanced past all the additional free blocks. So at line 650, we should only advance by `wh` (the size of the current block), not by `Whsize_hd(hd)`.
For a free block with `Wosize_hd(hd) = 0`, `Whsize_hd(hd) = 1`, so the advance at line 650 is 1, not `wh`. This seems wrong!
Wait, but let me look at what happens for a non-free (live) block:
- Line 650: `p += Whsize_hd(hd);` — this is `Wosize_hd(hd) + 1`, which is the correct block size including header.
For a live block, `Whsize_hd(hd)` is the actual block size. Correct.
For a free block with `Wosize_hd(hd) = N`:
- Line 644: `p += wh * N;` — skip N additional free blocks
- Line 650: `p += N + 1;` — but this is wrong! For a free block, the block occupies `wh` words, not `N + 1` words.
Hmm, but actually, wait. `Whsize_hd(hd)` for a live block is also `Wosize_hd(hd) + 1` which is the number of words in the block including the header. The actual word size of the block object is `Wosize_hd(hd)` and the header is 1 word, so total is `Wosize_hd(hd) + 1`.
For a pool, all blocks have size `wh` (the sizeclass width). So `Whsize_hd(hd)` for a live block should equal `wh` (or less due to wastage). So the advance at line 650 for a live block is approximately `wh`.
For a free block with wosize=N:
- The total advance should be `wh * (1 + N)` — one block of size `wh` for the current, plus N blocks of size `wh` for the additional.
- Line 644 gives `wh * N`
- Line 650 gives `N + 1`
- Total: `wh * N + N + 1 = N * (wh + 1) + 1`
For this to equal `wh * (1 + N)`, we need:
`N * (wh + 1) + 1 = wh * (1 + N) = wh + wh * N`
`N * wh + N + 1 = wh + N * wh`
`N + 1 = wh`
This is only true if `wh = N + 1`, which is generally not the case!
So there IS a bug. Let me think about what the correct code should be.
For a free block at position `p` with header indicating `N` additional free blocks:
- The current free block occupies `wh` words (positions `p` to `p + wh - 1`)
- The N additional free blocks occupy `N * wh` words (positions `p + wh` to `p + wh + N * wh - 1`)
- Total: `(1 + N) * wh` words
So the loop should advance `p` by `(1 + N) * wh`:
- Line 644: `p += wh * N` (skip the additional blocks) ✓
- Line 650 should advance by `wh` for the current block.
But line 650 does `p += Whsize_hd(hd)` which is `N + 1` for a free block.
So the bug is that line 650 advances by `N + 1` instead of `wh` for free blocks.
Wait, but let me double-check by looking at pool_allocate and pool_initialize.
In pool_initialize (line 311-332):
```c
p[0] = POOL_FREE_HEADER(pool_blocks-1);
p[1] = 0;
```
So when a pool is initialized, the first block's header has `wosize = pool_blocks - 1`, indicating that there are `pool_blocks - 1` additional free blocks after it. And `p[1] = 0` is the next_obj pointer (no next free block beyond the contiguous ones).
In pool_allocate (line 445-484):
```c
p = r->next_obj;
...
if( Wosize_hp(p) > 0 ) {
next = (value*)(p + wsize_sizeclass[sz]);
*next = POOL_FREE_HEADER(Wosize_hp(p) - 1);
next[1] = p[1];
}
```
So when allocating from a pool, `p` is the next free object. If `Wosize_hp(p) > 0` (there are additional free blocks), the next free block is at `p + wsize_sizeclass[sz]` (= `p + wh`), and its header has `wosize = Wosize_hp(p) - 1`.
This confirms that the run-length encoding uses `wosize` as "number of additional contiguous free blocks after this one", and each block occupies `wh` words.
So in the sweep loop, the bug is at line 650:
```c
p += Whsize_hd(hd);
```
For a live block, `Whsize_hd(hd) = Wosize_hd(hd) + 1` which should equal `wh` (or less due to fragmentation). This is correct.
For a free block with wosize=N, `Whsize_hd(hd) = N + 1`, but the advance should be `wh` (since we already skipped N * wh at line644).
Wait, actually let me re-examine this. For a live block in a pool:
- `Wosize_hd(hd)` is the actual wosize of the block
- `Whsize_hd(hd) = Wosize_hd(hd) + 1` is the header + payload size
- The pool allocates blocks of size `wh = wsize_sizeclass[sz]` words
- So `Whsize_hd(hd) <= wh` (there can be wastage)
For a free block with wosize=N:
- `Whsize_hd(hd) = N + 1`
- But we need to advance by `wh` to get to the next block
So the issue is: for free blocks, line 650 doesn't advance by the right amount. The total advance is:
- Line 644: `wh * N` (for additional free blocks)
- Line 650: `N + 1` (BUGGY — should be `wh`)
- Total: `wh * N + N + 1` instead of `wh * (N + 1) = wh * N + wh`
The correct advance at line 650 should be `wh` for free blocks, not `Whsize_hd(hd)`.
Wait, but hold on. Let me re-read the loop structure more carefully:
```c
do {
header_t hd = ...;
...
if (Has_status_hd(hd, caml_global_heap_state.GARBAGE)) {
// convert garbage to free block *p = POOL_FREE_HEADER(0);
hd = POOL_FREE_HEADER(0);
}
if (POOL_BLOCK_FREE_HD(hd)) {
// free block processing (merging, linking)
...
p += wh * Wosize_hd(hd); // line 644: skip additional free blocks
} else {
// live block release_to_global_pool = 0;
}
p += Whsize_hd(hd); // line 650: advance past current block
} while (p + wh <= end);
```
Hmm, actually wait. For a live block, `Whsize_hd(hd) = Wosize_hd(hd) + 1`. In a pool, the block's actual wosize can be less than or equal to `wh - 1` (since `wh` includes the header). So `Whsize_hd(hd) <= wh`. The advance is correct for live blocks.
For a free block, `Whsize_hd(hd) = N + 1`. This is NOT the block size — it's the RLE count + 1.
So the fix would be: for free blocks, advance by `wh` instead of `Whsize_hd(hd)`.
One way to fix this is to change line 650 from:
```c
p += Whsize_hd(hd);
```
to:
```c
p += wh;
```
Wait, but that would change the behavior for live blocks too. For live blocks, `Whsize_hd(hd)` should equal `wh` (since the pool block size is `wh`), so this should be fine.
Actually no. For live blocks, `Whsize_hd(hd)` may be less than `wh` due to fragmentation. The block's wosize can be smaller than the sizeclass width. So `p += wh` would skip past the end of the block AND the padding, which... actually might be correct since all blocks in a pool are aligned to `wh` word boundaries.
Hmm, but wait. In the pool, every block occupies exactly `wh` words (including header). So the correct advance is always `wh`, regardless of whether the block is free or live.
Actually, let me look at this more carefully. In pool_allocate:
```c
p = r->next_obj;
...
if( Wosize_hp(p) > 0 ) {
next = (value*)(p + wsize_sizeclass[sz]);
```
So the next block is at `p + wh`, confirming that blocks are spaced `wh` apart.
And in `caml_shared_try_alloc`:
```c
sizeclass sz = sizeclass_wsize[whsize];
CAMLassert(wsize_sizeclass[sz] >= whsize);
p = pool_allocate(local, sz);
```
So `wh = wsize_sizeclass[sz]` is the spacing between blocks in the pool, and `whsize = Wosize_wosize(wosize)` is the actual header+payload size. There can be wastage: `wh - whsize` words of padding.
So for the sweep loop, the correct advance should always be `wh` to move from one block to the next. The current code uses `Whsize_hd(hd)` which:
- For live blocks: equals the actual header+payload size, which is <= wh. This would under-advance!
- For free blocks with wosize=N: equals N+1, which is also wrong.
Wait, this means the current code is buggy even for live blocks? Let me think again...
Hmm, actually, I think I may be wrong about `Whsize_hd` for live blocks. In a pool, a live block's header stores the actual wosize. And `Whsize_hd(hd) = Wosize_hd(hd) + 1`. The sizeclass ensures that `wsize_sizeclass[sz] >= whsize`. So `Whsize_hd(hd)` could be less than `wh`.
But if that's the case, then the sweep loop would under-advance for live blocks too, not just free blocks. That would be a pre-existing bug, not something newly introduced by the RLE compression.
Hmm, wait. Let me look at the `calc_pool_stats` function which also iterates over pools:
```cstatic void calc_pool_stats(pool* a, sizeclass sz, struct heap_stats* s)
{
header_t* p = POOL_FIRST_BLOCK(a, sz);
header_t* end = POOL_END(a);
mlsize_t wh = wsize_sizeclass[sz];
while (p + wh <= end) {
header_t hd = (header_t)atomic_load_relaxed((atomic_uintnat*)p);
if (!POOL_BLOCK_FREE_HD(hd)) {
s->pool_live_words += Whsize_hd(hd);
s->pool_frag_words += wh - Whsize_hd(hd);
s->pool_live_blocks++;
} else {
p += wh * Wosize_hd(hd); /* skip contiguous free blocks */
}
p += wh; // <-- advances by wh, not Whsize_hd(hd)!
}
```
This function advances by `wh` at each step, and for free blocks it additionally skips `wh * Wosize_hd(hd)`. This is the correct pattern!
Similarly, `verify_pool`:
```c
while (p + wh <= end) {
header_t hd = Hd_hp(p);
...
if (!POOL_BLOCK_FREE_HD(hd)) {
...
} else {
s->free += wh * (1 + Wosize_hd(hd));
p += Wosize_hd(hd) * wh;
}
p += wh;
}
```
Same pattern — advances by `wh` plus `Wosize_hd(hd) * wh` for free blocks.
And `compact_update_pools`:
```c
while (p + wh <= end) {
if (!POOL_BLOCK_FREE_HP(p)) {
...
} else {
p += wh * Wosize_hp(p);
}
p += wh;
}
```
Same pattern again!
And `pool_finalise`:
```c
while (p + wh <= end) {
header_t hd = ...;
if (!POOL_BLOCK_FREE_HD(hd)) {
...
} else {
p += wh * Wosize_hd(hd);
}
p += wh;
}
```
Same pattern!
So in `pool_sweep`, line 650 should be `p += wh;` not `p += Whsize_hd(hd);`.
This is definitely the bug! The sweep function was modified to use run-length encoding for free space, but the loop advancement was changed to use `Whsize_hd(hd)` (which for a free block gives `Wosize_hd(hd) + 1`) instead of the correct `wh`.
The original code (before the RLE modification) likely had `p += wh;` at line 650 (matching all the other iteration patterns in the file), and the RLE modification incorrectly changed it to `p += Whsize_hd(hd);`.
Let me verify by looking at other iteration patterns more carefully:
`calc_pool_stats`: `p += wh;` with extra `p += wh * Wosize_hd(hd);` for free blocks
`verify_pool`: `p += wh;` with extra `p += Wosize_hd(hd) * wh;` for free blocks
`compact_update_pools`: `p += wh;` with extra `p += wh * Wosize_hp(p);` for free blocks
`pool_finalise`: `p += wh;` with extra `p += wh * Wosize_hd(hd);` for free blocks
`caml_redarken_pool`: `p += wh;` (no RLE handling, just skips one block at a time)
The `pool_sweep` code has:
```c
p += wh * Wosize_hd(hd); // line 644: inside the free block branch
...
p += Whsize_hd(hd); // line 650: always
```
The fix is to change line 650 from `p += Whsize_hd(hd);` to `p += wh;`.
But wait, let me also think about what `Whsize_hd(hd)` would do for a *live* block. For a live block:
- `Wosize_hd(hd)` is the actual object size
- `Whsize_hd(hd) = Wosize_hd(hd) + 1` = total block size including header
- In a pool, blocks are `wh` words apart
- `Whsize_hd(hd) <= wh` (since the sizeclass guarantees at least this much space)
So for live blocks, `p += Whsize_hd(hd)` would advance by less than `wh`, which would mean we'd land in the middle of the padding/wastage area of the current block, not at the start of the next block. This would be buggy too!
But wait, this code must have been working at some point (before the RLE changes)... unless the user's changes introduced this bug.
Actually, let me think about this differently. Maybe before the user's changes, the code didn't have the RLE encoding. Without RLE, there would be no `p += wh * Wosize_hd(hd);` line (line 644). And the `p += Whsize_hd(hd);` at line 650 might have been `p += wh;` originally.
Looking at the code structure, I think the user:
1. Added the RLE compression scheme (using `Wosize` in free headers to count additional contiguous blocks)
2. Added the skip at line 644: `p += wh * Wosize_hd(hd);`
3. But then mistakenly changed line 650 from `p += wh;` to `p += Whsize_hd(hd);`, perhaps thinking that `Whsize_hd` gives the block size including header
The fix is simply to change line650 from `p += Whsize_hd(hd);` to `p += wh;`.
Wait, but I should double-check. Let me look at `Whsize_hd`:
From the OCaml source, `Whsize_hd(hd) = Wosize_hd(hd) + 1`. For a live block with wosize=W, this is W+1 which is the number of words in the block (payload + header). The pool block size is `wh`. So `Whsize_hd(hd)` for a live block is the actual size of the live data, which can be less than `wh` due to fragmentation.
So yes, the correct fix is to change `p += Whsize_hd(hd);` to `p += wh;` at line 650.
Now, wait. Let me also check: what if line 650 was originally `p += wh;` and the user changed it to `p += Whsize_hd(hd);`? That would explain the bug perfectly.
Actually, I realize I should also check what `Wosize_whsize` and `Whsize_wosize` are, to make sure I understand the macros correctly.
Looking at `mlvalues.h` or wherever these are defined... Actually, the standard definitions are:
- `Whsize_wosize(n) = (n) + 1` — word size including header
- `Wosize_whsize(n) = (n) - 1` — object size without header
- `Whsize_hd(hd) = Wosize_hd(hd) + 1` — word size including header from header value
So `Whsize_hd(hd)` for a live block = actual wosize + 1 = actual block size in words. For a pool with sizeclass `wh`, this is <= wh.
OK, I'm quite confident now. The bug is at line 650. It should be `p += wh;` instead of `p += Whsize_hd(hd);`.
Let me also verify there's not a subtle issue with the loop termination condition. The loop condition is `p + wh <= end`. After advancing by `wh`, we check if there's room for another full block. This is consistent.
Let me also look at the `all_used` / `last_free_block` logic to make sure the merge is correct when we fix the advancement.
When we encounter a free block at position `p` with wosize `N`:
- It covers blocks at positions `p, p+wh, p+2*wh, ..., p+N*wh`
- The next free block in the chain (if any) is stored at `p[1]`
When merging with `last_free_block`:
- `last_free_block + (1 + Wosize_hp(last_free_block)) * wh == p`
- This checks if `p` immediately follows the last free block's run
After merging:
- `*last_free_block = POOL_FREE_HEADER(Wosize_hp(last_free_block) + Wosize_hd(hd) + 1);`
- This adds the current block's run length plus 1 (for the current block itself) to the last free block's run length
This looks correct.
After merging, we still need to update `last_free_block[1]` (the next pointer) since the newly freed blocks may have had a next pointer that should be preserved. Wait, actually, in the merge case, we don't update the next pointer. Let me think about this.
If `last_free_block` had its next pointer set to some block X (beyond its run), and the current free block `p` has its next pointer set to Y, after merging, the merged block's next pointer should still be... hmm, actually in the merge case, `p` is immediately after `last_free_block`'s run, so there can't be anything between them. The next pointer of `p` (which is `p[1]`) might point to a further free block. After merging, we should update `last_free_block[1] = p[1]` to preserve the chain.
Wait, but the code doesn't do this in the merge case! It only updates the next pointer in the `else` branch (line 631: `last_free_block[1] = (value)p;`).
Hmm, but actually, let me think about when `p` already has a valid next pointer. For a pre-existing free block, `p[1]` would already be set to the next free block in the chain. For a newly freed block (from garbage), `p[1]` would be whatever was in the first field of the block when it was alive (garbage data).
Actually wait, when a garbage block is converted to free:
```c
*p = POOL_FREE_HEADER(0);
```
The code only sets the header, not `p[1]`. So `p[1]` still contains whatever the live block had in its first field. This is fine because we don't use `p[1]` in the merge case — we only use it in the `else` branch where we set `last_free_block[1] = (value)p`.
But wait, what if `p` was a pre-existing free block (not converted from garbage)? Then `p[1]` already has a valid next pointer. When we merge, we lose this next pointer because we don't update `last_free_block[1]`. But since `p` is immediately after `last_free_block`'s run, they must be contiguous, which means there are no non-free blocks between them. So the chain from `last_free_block` would naturally include `p`'s run after the merge. The only issue would be if `p[1]` points to a free block that's not contiguous with the merged block. In that case, we'd lose the pointer to that distant free block.
Hmm, actually let me think about this more carefully. When we merge:
1. `last_free_block` has wosize K (meaning K additional free blocks after it)
2. `p` has wosize N (meaning N additional free blocks after it)
3. After merge: `last_free_block` gets wosize K + N + 1
The blocks covered by `last_free_block` after merge:
- `last_free_block, last_free_block+wh, ..., last_free_block+(K+N+1)*wh`
The blocks covered by `p` before merge:
- `p, p+wh, ..., p+N*wh`
Since `p = last_free_block + (K+1)*wh`:
- `p+N*wh = last_free_block + (K+1+N)*wh = last_free_block + (K+N+1)*wh` ✓
So the merge correctly covers all blocks.
But what about `p[1]`? If `p` was a pre-existing free block, `p[1]` might point to a free block beyond `p`'s run. After the merge, `last_free_block[1]` still points to whatever it pointed to before. If `p[1]` pointed to a different (further) free block, we'd lose that link.
Wait, but if `p` is a pre-existing free block with wosize N:
- After `p`, there are N additional free blocks
- After those N blocks, the next block might be free or live
- `p[1]` points to the next free block beyond the run
After merging with `last_free_block`, we should set `last_free_block[1] = p[1]` to preserve the chain. But the code doesn't do this.
Hmm, but actually, looking at the sweep more carefully:
When we encounter a pre-existing free block `p` with wosize N:
1. We try to merge with `last_free_block`
2. If merge succeeds, we update `last_free_block`'s wosize but NOT its next pointer
3. Then at line 644, we skip N blocks: `p += wh * N`
4. At line 650, we advance by the block size
After step 2, `last_free_block[1]` still points to whatever it was pointing to before. If `p` had a next pointer (`p[1]`) that pointed to something different, we lose it.
But wait, think about the situation: `last_free_block` was the last free block we saw, and `p` is the next free block that's contiguous with it. Between them, there are no other free blocks (otherwise they would have been merged already). So `last_free_block[1]` was either:
- NULL (no known next free block) — this would be the case for a newly freed block
- Or pointing to `p` (if `last_free_block` was pre-existing and its next pointer was set to `p`)
If `last_free_block[1]` points to `p`, then after merging, we should update it to `p[1]` (the block after `p`'s run). But the code doesn't do this.
Actually, wait. I think the issue is more subtle. In the sweep, we're iterating through blocks sequentially. The "next_obj" pointer in a free block is used by the allocator to find free blocks. During sweep, we're rebuilding these pointers. So the old next pointers in pre-existing free blocks are being overwritten anyway.
Let me re-read the merge code:
```c
if( last_free_block + (1 + Wosize_hp(last_free_block)) * wh == p ) {
/* merge */
*last_free_block = POOL_FREE_HEADER(Wosize_hp(last_free_block)
+ Wosize_hd(hd) + 1);
} else {
/* not contiguous, link them */
last_free_block[1] = (value)p;
last_free_block = p;
}
```
In the merge case, we update the header of `last_free_block` but don't touch `last_free_block[1]`. After merging, `last_free_block[1]` should be the next free pointer. For a pre-existing `last_free_block`, its `[1]` field was already set during a previous iteration. When we merge, the next pointer should still be correct because:
- If `last_free_block[1]` pointed to `p`, we should now update it to `p[1]`
- If `last_free_block[1]` pointed to something else (shouldn't happen if `p` is contiguous), that would be wrongActually, I think the situation where `last_free_block[1]` points to `p` and `p` is contiguous IS the case where we should update `last_free_block[1] = p[1]`. But the code doesn't do this.
Hmm, but let me think about whether this actually causes a problem. After the sweep, the free list is rebuilt. The `a->next_obj` is set to the first free block, and each free block's `[1]` field points to the next non-contiguous free block.
If `last_free_block[1]` still points to `p` after merging, then when the allocator later uses this free list, it would find `p` as the "next" free block, but `p` is now part of the merged block and its header has been... wait, no. The header of `p` hasn't been changed — only the header of `last_free_block` was updated. So `p` still has its old header. When the allocator encounters `p` through the next pointer, it would see it as a free block. But it's in the middle of the merged free block, which is confusing.
Actually, I think the issue is that in the merge case, `last_free_block[1]` needs to be updated to `p[1]`. Let me see if this causes the crash.
Actually, wait. Let me reconsider. Let me look at the case more carefully.
Case 1: `last_free_block` is pre-existing free with wosize K, next pointer set to some block Y.
- `last_free_block[1] = Y`
- We encounter `p` which is contiguous (immediately after `last_free_block`'s run)
- We merge: `last_free_block` gets wosize K + N + 1 (where N is `p`'s wosize)
- `last_free_block[1]` is still `Y`
But `Y` might be a free block that's further away. After the merge, the merged block covers blocks from `last_free_block` to `last_free_block + (K+N+1)*wh`. If `Y` is within this range, it's now part of the merged block and shouldn't be in the next pointer. If `Y` is outside this range, it's fine.
But actually, `Y` can't be within the range because we're scanning blocks sequentially. If `Y` were within the range, we would have encountered it already and merged it. So `Y` is either beyond the range or NULL. In either case, `last_free_block[1] = Y` is correct after the merge.
But wait, `p` might have had its own next pointer (`p[1]`) pointing to a free block `Z`. After the merge, `last_free_block[1]` should point to the next non-contiguous free block. If `Z` is further than `Y`, we'd lose the link to `Z`. If `Y` is further than `Z`, we'd lose the link to `Y`... wait, no, we keep `Y` since `last_free_block[1]` is still `Y`.
Hmm, this is getting complicated. Let me think about whether `p[1]` could have a meaningful value at this point in the sweep.
For a pre-existing free block `p`:
- `p[1]` was set during the previous sweep to point to the next free block
- This could be a block far away from `p`
When we merge `p` into `last_free_block`, we should make `last_free_block[1] = p[1]` to preserve the chain. Otherwise, if `last_free_block[1]` pointed to `p` (which is now part of the merged block), the allocator could try to use `p` as a separate free block.
Actually, I think the key insight is: `last_free_block[1]` was set to `p` in a PREVIOUS iteration of this sweep. So in the current sweep, when we encounter `p` and merge it:
- `last_free_block[1]` currently points to `p`
- After merging, we should update it to `p[1]`
But the code doesn't do this! So `last_free_block[1]` still points to `p`, which is now in the middle of the merged free block. When the allocator encounters `p` through this pointer, it sees a free block that overlaps with the merged block.
OK so there are potentially TWO bugs:
1. Line 650: `p += Whsize_hd(hd)` should be `p += wh`
2. In the merge case, `last_free_block[1]` should be updated to `p[1]`
But wait, I need to think about whether bug #2 actually matters or not. Let me look at what happens during allocation:
```cstatic void* pool_allocate(struct caml_heap_state* local, sizeclass sz) {
p = r->next_obj;
...
if( Wosize_hp(p) > 0 ) {
next = (value*)(p + wsize_sizeclass[sz]);
*next = POOL_FREE_HEADER(Wosize_hp(p) - 1);
next[1] = p[1];
} else {
next = (value*)p[1];
}
r->next_obj = next;
```
When allocating from a free block `p`:
- If `Wosize_hp(p) > 0` (there are additional contiguous free blocks):
- The next free block is at `p + wh`
- Set its header to `POOL_FREE_HEADER(Wosize_hp(p) - 1)`
- Set its next pointer to `p[1]`
- If `Wosize_hp(p) == 0` (no additional contiguous free blocks):
- The next free block is `p[1]`
So if `last_free_block` has `last_free_block[1] = p` where `p` is in the middle of the merged block:
- When allocating from `last_free_block`, if `Wosize > 0`:
- The next block at `last_free_block + wh` has a valid free header (it's part of the merged block)
- Its next pointer is set to `last_free_block[1] = p`
- But `p` might be at `last_free_block + 2*wh` or further, which would be a block in the middle of what should be a contiguous run
This is indeed a bug! The allocator would see `p` as a separate free block when it should be part of the contiguous run.
OK so I've found two bugs, but let me focus on the one that causes the crash. The crash during bootstrapping is likely due to the incorrect loop advancement (bug #1), which would cause the sweep to read garbage headers and corrupt the heap.
Let me now also think about bug #2 more carefully. In the merge case:
```c
*last_free_block = POOL_FREE_HEADER(Wosize_hp(last_free_block) + Wosize_hd(hd) + 1);
```
After this, `last_free_block[1]` still has its old value. If the old value was `p` (set in a previous iteration's `else` branch), then we have a stale pointer. We should set `last_free_block[1] = p[1]` after the merge.
But actually, when was `last_free_block[1]` set to `p`? It was set in the else branch:
```c
} else {
last_free_block[1] = (value)p;
last_free_block = p;
}
```
This sets `last_free_block[1] = (value)p` and then updates `last_free_block = p`. So in the next iteration where we encounter a contiguous free block `p'`:
- `last_free_block` is the previous `p`
- `last_free_block[1]` is... wait, `last_free_block[1]` was not set to `p'` yet. It was set in the else branch of the PREVIOUS iteration.
Let me trace through an example:
- Block A: free (wosize=0)
- Block B: live
- Block C: free (wosize=0)
- Block D: free (wosize=0, contiguous with C)
Iteration 1 (p = A):
- hd = free header with wosize=0
- last_free_block is NULL → set a->next_obj = A, last_free_block = A
- p += 0 (line 644) → p still at A
- p += Whsize_hd(hd) = 0 + 1 =1 → p at A+1
Oh wait, this would be wrong! `p` should advance by `wh` (the sizeclass width), not by 1. With the bug, `p` advances by 1, landing in the middle of block A's payload, not at block B.
So bug #1 is definitely the main issue causing the crash.
Now, regarding bug #2 (not updating `last_free_block[1]` in the merge case):
Let me trace through more carefully with the correct advancement (p += wh):
- Block A: free (wosize=0)
- Block B: live
- Block C: free (wosize=0)
- Block D: free (wosize=0, contiguous with C)
Iteration 1 (p = A):
- hd = free, wosize=0
- last_free_block = NULL → a->next_obj = A, last_free_block = A
- p += wh * 0 = 0 (skip additional free blocks)
- p += wh → p at BIteration 2 (p = B):
- hd = live
- release_to_global_pool = 0
- p += wh → p at C
Iteration 3 (p = C):
- hd = free, wosize=0
- last_free_block = A, A + (1+0)*wh = A + wh = B ≠ C → not contiguous- else: A[1] = C, last_free_block = C
- p += wh * 0 = 0
- p += wh → p at D
Iteration 4 (p = D):
- hd = free, wosize=0
- last_free_block = C, C + (1+0)*wh = C + wh = D → contiguous!
- merge: *C = POOL_FREE_HEADER(0 + 0 + 1) = POOL_FREE_HEADER(1)
- C[1] is NOT updated (stale value from iteration 3 — but C was just set as last_free_block, C[1] was never explicitly set)
Hmm, actually C[1] was never set. C was a pre-existing free block. Its [1] field might have been set during the previous sweep. But in the current sweep, we haven't touched it.
After the merge, C now has wosize=1 (covering C and D). C[1] still has its old value from before. If C[1] was 0 or some stale pointer, the allocator would use it as the next free pointer after consuming C and D. This could be a problem.
But wait, after C and D, we'll continue scanning and might find more free blocks. Let's say block E is free (not contiguous with C+D because there's something in between). In that case:
Iteration 5 (p = E):
- hd = free, wosize=0
- last_free_block = C, C + (1+1)*wh = C + 2*wh = E → contiguous! (if E = C + 2*wh)
Wait, E might not be contiguous. If there's a live block between D and E...
OK, I think the merge logic + next pointer update issue is more subtle. But the main bug causing the crash is #1 (incorrect loop advancement).
Actually, let me reconsider bug #2. In the merge case, after merging D into C:
- C has wosize=1 (covers C and D)
- C[1] has whatever was in C's payload before (stale data)
Later, if we encounter E (not contiguous), we go through the else branch:
- C[1] = E, last_free_block = E
So C[1] gets updated to E. This is correct! The stale C[1] value is overwritten when we encounter the next non-contiguous free block.
But what if C's run extends all the way to the end of the pool? Then C[1] would never be updated and would have stale data. But at the end of the sweep:
```c
if( !all_used ) {
last_free_block[1] = 0;
}
```
This sets the last free block's next pointer to 0. So C[1] = 0, which is correct.
So bug #2 might not actually be a problem! The stale next pointer in the merged block gets overwritten either by a subsequent else branch or by the end-of-pool cleanup.
OK so I'm now fairly confident that the main (and possibly only) bug is at line 650: `p += Whsize_hd(hd)` should be `p += wh`.
Wait, but I should also check: could the merge at line 626-627 be wrong?
```c
*last_free_block = POOL_FREE_HEADER(Wosize_hp(last_free_block) + Wosize_hd(hd) + 1);
```
Let me verify:
- `last_free_block` has wosize K → covers K additional blocks (total K+1 blocks)
- Current block `p` has wosize N → covers N additional blocks (total N+1 blocks)
- They're contiguous, so total blocks = (K+1) + (N+1) = K + N + 2
- New wosize should be total blocks - 1 = K + N + 1
- The formula gives: K + N + 1 ✓
This is correct.
Now let me also verify the merge condition:
```c
last_free_block + (1 + Wosize_hp(last_free_block)) * wh == p
```
- `last_free_block` covers (K+1) blocks starting at `last_free_block`
- The block after the last one in the run is at `last_free_block + (K+1) * wh`
- This should equal `p` for contiguity ✓
This is also correct.
So the fix is simply to change line 650 from `p += Whsize_hd(hd);` to `p += wh;`.
Actually wait, I realize I should double check one more time. Let me look at the `do...while` loop structure:
```c
do {
header_t hd = (header_t)atomic_load_relaxed((atomic_uintnat*)p);
...
if (Has_status_hd(hd, caml_global_heap_state.GARBAGE)) {
*p = POOL_FREE_HEADER(0);
hd = POOL_FREE_HEADER(0);
}
if (POOL_BLOCK_FREE_HD(hd)) {
...
p += wh * Wosize_hd(hd); // skip additional free blocks } else {
...
}
p += Whsize_hd(hd); // advance past current block} while (p + wh <= end);
```
For a free block with wosize N:
- Line 644: `p += wh * N` (skip additional blocks)
- Line 650: `p += N + 1` (BUG: should be `p += wh`)
- Total: `p += wh * N + N + 1`
Correct total should be: `p += wh * (N + 1) = wh * N + wh`
Difference: `(wh * N + N + 1)` vs `(wh * N + wh)` = `(N + 1)` vs `wh`
For most sizeclasses, `wh >= 2` (minimum block size is 2 words: 1 header + 1 payload). So for N=0:
- Current: advance by 1
- Correct: advance by `wh` (at least 2)
This means for a free block with no additional blocks, we only advance by 1 word instead of `wh`. This would cause us to read the payload of the free block as if it were a header, leading to corruption.
For N > 0, the advance is even more wrong: `N + 1` vs `wh * (N + 1)`.
This is clearly the bug. The fix is to change `p += Whsize_hd(hd);` to `p += wh;`.
Actually, hold on. I want to make sure I haven't missed something. Let me check if `Whsize_hd` could equal `wh` for a live block.
For a live block in a pool of sizeclass `sz`:
- `wh = wsize_sizeclass[sz]`
- The block's `wosize` is determined by the allocation: `sizeclass_wsize[whsize] = sz`, where `whsize = Whsize_wosize(wosize)`
- So `whsize <= wh`, meaning `Wosize_hd(hd) + 1 <= wh`, meaning `Whsize_hd(hd) <= wh`
For blocks that perfectly fit the sizeclass (no wastage), `Whsize_hd(hd) == wh`. For blocks with wastage, `Whsize_hd(hd) < wh`.
So for live blocks, `p += Whsize_hd(hd)` would under-advance when there's wastage!
But wait, the pre-existing code (before the RLE changes) must have worked. Let me check what the original code probably looked like. I think the original sweep loop had:
```c
p += wh; // always advance by the block size
```
And the user changed it to:
```c
p += Whsize_hd(hd); // tries to advance by the block's actual size
```
This is wrong for two reasons:
1. For free blocks, `Whsize_hd(hd)` encodes the RLE count, not the block size
2. For live blocks with wastage, `Whsize_hd(hd) < wh`
So the fix is simply `p += wh;`.
Wait, but I also want to check the `do...while` termination condition. The loop runs `while (p + wh <= end)`, meaning it continues as long as there's room for a full block. After the fix, `p` always advances by at least `wh`, so this should be correct.
After the last block, `p` should equal `end`. Let me verify:
- Pool has `pool_blocks` blocks, each of size `wh`
- First block starts at `POOL_FIRST_BLOCK(a, sz)`
- `end = POOL_FIRST_BLOCK(a, sz) + pool_blocks * wh` (wait, not exactly... let me check)
Actually, `end = POOL_END(a) = (header_t*)(a) + POOL_WSIZE`. And `POOL_FIRST_BLOCK(a, sz) = (header_t*)(a) + POOL_SLAB_WOFFSET(sz)`. So:
- `end - POOL_FIRST_BLOCK(a, sz) = POOL_WSIZE - POOL_SLAB_WOFFSET(sz)`
- Number of blocks = `(POOL_WSIZE - POOL_SLAB_WOFFSET(sz)) / wh`
Since blocks are `wh` words apart, and they tile the pool exactly (by the sizeclass design), `p` should equal `end` after iterating through all blocks. So the assertion `CAMLassert(p == end);` should hold.
OK, I'm confident in the fix. Let me also look at the assertion at line 652:
```c
CAMLassert(p == end);
```
With the buggy code, `p` would not equal `end` because the advancement is wrong. This assertion would fire in debug mode. In release mode, the loop would continue past `end` or stop too early, causing the crash.
Alright, the fix is clear: change line650 from `p += Whsize_hd(hd);` to `p += wh;`.