ext4: fix rbtree traversal bug in ext4_mb_use_preallocated
Linux
Affected versions
| Product | Affected | Fixed in |
|---|---|---|
| Linux Linux |
| No fix yet |
| Linux Linux |
|
|
Linux
| Product | Affected | Fixed in |
|---|---|---|
| Linux Linux |
| No fix yet |
| Linux Linux |
|
|
In the Linux kernel, the following vulnerability has been resolved:
ext4: fix rbtree traversal bug in ext4_mb_use_preallocated
During allocations, while looking for preallocations(PA) in the per inode rbtree, we can't do a direct traversal of the tree because ext4_mb_discard_group_preallocation() can paralelly mark the pa deleted and that can cause direct traversal to skip some entries. This was leading to a BUG_ON() being hit [1] when we missed a PA that could satisfy our request and ultimately tried to create a new PA that would overlap with the missed one.
To makes sure we handle that case while still keeping the performance of the rbtree, we make use of the fact that the only pa that could possibly overlap the original goal start is the one that satisfies the below conditions:
1. It must have it's logical start immediately to the left of (ie less than) original logical start.
2. It must not be deleted
To find this pa we use the following traversal method:
1. Descend into the rbtree normally to find the immediate neighboring PA. Here we keep descending irrespective of if the PA is deleted or if it overlaps with our request etc. The goal is to find an immediately adjacent PA.
From the CVE record · Linux
A bug in ext4 preallocation tree traversal can miss an existing allocation during concurrent preallocation discard, causing a kernel BUG_ON() during allocation. The input does not specify whether an attacker can trigger this remotely or locally, or whether authentication or user interaction is required.
Engineers running Linux kernels with ext4 should check their versions; affected versions are not specified.