| 0/0 |
2026/01/28 17:25 |
flow |
patching |
11m
Results: map[KernelCommit:v6.19-rc7 KernelRepo:git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git PatchDescription:jfs: fix array-index-out-of-bounds in dbFindLeaf
Syzkaller reported the following UBSAN failure:
UBSAN: array-index-out-of-bounds in fs/jfs/jfs_dmap.c:2976:16
index 1365 is out of range for type 's8[1365]' (aka 'signed char[1365]')
...
dbFindLeaf+0x308/0x520 fs/jfs/jfs_dmap.c:2976
dbFindCtl+0x267/0x520 fs/jfs/jfs_dmap.c:1717
The function dbFindLeaf() traverses the dmap tree to find a leaf with
sufficient free space. It uses `max_size` (which is 1365 for
CTLTREESIZE) to check bounds for the `dmt_stree` array. However, the
condition `if (x + n > max_size)` allows `x + n` to be equal to
`max_size`, which results in an out-of-bounds access since the valid
indices are 0 to `max_size - 1`.
Fix this by updating the condition to `if (x + n >= max_size)`. PatchDiff:diff --git a/fs/jfs/jfs_dmap.c b/fs/jfs/jfs_dmap.c
index cdfa699cd..18a7dc58f 100644
--- a/fs/jfs/jfs_dmap.c
+++ b/fs/jfs/jfs_dmap.c
@@ -2971,7 +2971,7 @@ static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
/* sufficient free space found. move to the next
* level (or quit if this is the last level).
*/
- if (x + n > max_size)
+ if (x + n >= max_size)
return -ENOSPC;
if (l2nb <= tp->dmt_stree[x + n])
break;
Recipients:[map[Email:jfs-discussion@lists.sourceforge.net Name: To:true] map[Email:linux-kernel@vger.kernel.org Name: To:false] map[Email:shaggy@kernel.org Name:Dave Kleikamp To:true]]]
|
| 1/1 |
2026/01/28 17:25 |
action |
base-commit-picker |
0m
Results: map[KernelCommit:v6.19-rc7 KernelRepo:git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git]
|
| 2/1 |
2026/01/28 17:25 |
action |
kernel-checkouter |
0m
Results: map[KernelSrc:/usr/local/google/home/dvyukov/syzkaller/agent/workdir/cache/src/5452af61ab2e1f5601403fe379188fc9d8a831af]
|
| 3/1 |
2026/01/28 17:25 |
action |
kernel-builder |
0m
Results: map[KernelObj:/usr/local/google/home/dvyukov/syzkaller/agent/workdir/cache/build/53ac19c90e186abedbf71cada4c0776d55521b7f]
|
| 4/1 |
2026/01/28 17:25 |
action |
crash-reproducer |
0m
Results: map[BugTitle:UBSAN: array-index-out-of-bounds in dbFindLeaf CrashReport:------------[ cut here ]------------
UBSAN: array-index-out-of-bounds in /usr/local/google/home/dvyukov/syzkaller/agent/workdir/cache/src/5452af61ab2e1f5601403fe379188fc9d8a831af/fs/jfs/jfs_dmap.c:2976:16
index 1365 is out of range for type 's8[1365]' (aka 'signed char[1365]')
CPU: 0 UID: 0 PID: 6426 Comm: syz-executor354 Not tainted syzkaller #1 PREEMPT_{RT,(full)}
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014
Call Trace:
<TASK>
__dump_stack lib/dump_stack.c:94 [inline]
dump_stack_lvl+0x10e/0x190 lib/dump_stack.c:120
ubsan_epilogue lib/ubsan.c:233 [inline]
__ubsan_handle_out_of_bounds+0x115/0x140 lib/ubsan.c:455
dbFindLeaf+0x308/0x520 fs/jfs/jfs_dmap.c:2976
dbFindCtl+0x267/0x520 fs/jfs/jfs_dmap.c:1717
dbAllocAny fs/jfs/jfs_dmap.c:1527 [inline]
dbAlloc+0x5fd/0xba0 fs/jfs/jfs_dmap.c:878
diNewIAG fs/jfs/jfs_imap.c:2510 [inline]
diAllocExt fs/jfs/jfs_imap.c:1905 [inline]
diAllocAG+0xcf0/0x1db0 fs/jfs/jfs_imap.c:1669
diAlloc+0x1d4/0x1670 fs/jfs/jfs_imap.c:1590
ialloc+0x8c/0x8f0 fs/jfs/jfs_inode.c:56
jfs_mkdir+0x193/0xa70 fs/jfs/namei.c:225
vfs_mkdir+0x530/0x5d0 fs/namei.c:5139
do_mkdirat+0x27a/0x4b0 fs/namei.c:5173
__do_sys_mkdir fs/namei.c:5200 [inline]
__se_sys_mkdir fs/namei.c:5198 [inline]
__x64_sys_mkdir+0x6c/0x80 fs/namei.c:5198
do_syscall_x64 arch/x86/entry/syscall_64.c:63 [inline]
do_syscall_64+0xe8/0xf80 arch/x86/entry/syscall_64.c:94
entry_SYSCALL_64_after_hwframe+0x77/0x7f
RIP: 0033:0x7f31a4a1c897
Code: 1f 40 00 48 89 f2 b9 00 01 00 00 48 89 fe bf 9c ff ff ff e9 7b 37 03 00 66 2e 0f 1f 84 00 00 00 00 00 90 b8 53 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 01 c3 48 c7 c2 d0 ff ff ff f7 d8 64 89 02 b8
RSP: 002b:00007f31a49be038 EFLAGS: 00000246 ORIG_RAX: 0000000000000053
RAX: ffffffffffffffda RBX: 0000200000000200 RCX: 00007f31a4a1c897
RDX: 0000000002b1247d RSI: 00000000000001ff RDI: 00002000000002c0
RBP: 0000000000000000 R08: 00000000000000fc R09: 0000000000000000
R10: 0000000000000008 R11: 0000000000000246 R12: 00002000000002c0
R13: 00007f31a49be0d0 R14: 0000000000000000 R15: 0000000000000000
</TASK>
---[ end trace ]---
]
|
| 5/1 |
2026/01/28 17:25 |
action |
codesearch-prepare |
0m
Results: map[Index:codesearch-index]
|
| 6/1 |
2026/01/28 17:26 |
agent |
debugger |
0m
Model:
Instruction:
You are an experienced Linux kernel developer tasked with debugging a kernel crash root cause.
You need to provide a detailed explanation of the root cause for another developer to be
able to write a fix for the bug based on your explanation.
Your final reply must contain only the explanation.
Prefer calling several tools at the same time to save round-trips.
Prompt:
The crash is:
------------[ cut here ]------------
UBSAN: array-index-out-of-bounds in /usr/local/google/home/dvyukov/syzkaller/agent/workdir/cache/src/5452af61ab2e1f5601403fe379188fc9d8a831af/fs/jfs/jfs_dmap.c:2976:16
index 1365 is out of range for type 's8[1365]' (aka 'signed char[1365]')
CPU: 0 UID: 0 PID: 6426 Comm: syz-executor354 Not tainted syzkaller #1 PREEMPT_{RT,(full)}
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014
Call Trace:
<TASK>
__dump_stack lib/dump_stack.c:94 [inline]
dump_stack_lvl+0x10e/0x190 lib/dump_stack.c:120
ubsan_epilogue lib/ubsan.c:233 [inline]
__ubsan_handle_out_of_bounds+0x115/0x140 lib/ubsan.c:455
dbFindLeaf+0x308/0x520 fs/jfs/jfs_dmap.c:2976
dbFindCtl+0x267/0x520 fs/jfs/jfs_dmap.c:1717
dbAllocAny fs/jfs/jfs_dmap.c:1527 [inline]
dbAlloc+0x5fd/0xba0 fs/jfs/jfs_dmap.c:878
diNewIAG fs/jfs/jfs_imap.c:2510 [inline]
diAllocExt fs/jfs/jfs_imap.c:1905 [inline]
diAllocAG+0xcf0/0x1db0 fs/jfs/jfs_imap.c:1669
diAlloc+0x1d4/0x1670 fs/jfs/jfs_imap.c:1590
ialloc+0x8c/0x8f0 fs/jfs/jfs_inode.c:56
jfs_mkdir+0x193/0xa70 fs/jfs/namei.c:225
vfs_mkdir+0x530/0x5d0 fs/namei.c:5139
do_mkdirat+0x27a/0x4b0 fs/namei.c:5173
__do_sys_mkdir fs/namei.c:5200 [inline]
__se_sys_mkdir fs/namei.c:5198 [inline]
__x64_sys_mkdir+0x6c/0x80 fs/namei.c:5198
do_syscall_x64 arch/x86/entry/syscall_64.c:63 [inline]
do_syscall_64+0xe8/0xf80 arch/x86/entry/syscall_64.c:94
entry_SYSCALL_64_after_hwframe+0x77/0x7f
RIP: 0033:0x7f31a4a1c897
Code: 1f 40 00 48 89 f2 b9 00 01 00 00 48 89 fe bf 9c ff ff ff e9 7b 37 03 00 66 2e 0f 1f 84 00 00 00 00 00 90 b8 53 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 01 c3 48 c7 c2 d0 ff ff ff f7 d8 64 89 02 b8
RSP: 002b:00007f31a49be038 EFLAGS: 00000246 ORIG_RAX: 0000000000000053
RAX: ffffffffffffffda RBX: 0000200000000200 RCX: 00007f31a4a1c897
RDX: 0000000002b1247d RSI: 00000000000001ff RDI: 00002000000002c0
RBP: 0000000000000000 R08: 00000000000000fc R09: 0000000000000000
R10: 0000000000000008 R11: 0000000000000246 R12: 00002000000002c0
R13: 00007f31a49be0d0 R14: 0000000000000000 R15: 0000000000000000
</TASK>
---[ end trace ]---
Reply: The root cause of the crash is an off-by-one error in the bounds check within the `dbFindLeaf` function in `fs/jfs/jfs_dmap.c`.
The function traverses a dmap tree to find a leaf with sufficient free space. The loop calculates the index of the child nodes at the next level using `ti` (and `x` inside the loop):
```c
ti = ((ti + n) << 2) + 1
```
And then it iterates `n` from 0 to 3 to check the 4 children. The code checks if the calculated index `x + n` is within the bounds of the tree array `tp->dmt_stree` (which corresponds to `struct dmapctl::stree` of size 1365 when `is_ctl` is true).
The current bounds check is:
```c
2974: if (x + n > max_size)
2975: return -ENOSPC;
```
When `x + n` is equal to `max_size` (1365), the condition `1365 > 1365` is false, so the check passes. The code then proceeds to access the array:
```c
2976: if (l2nb <= tp->dmt_stree[x + n])
```
Accessing index 1365 of an array of size 1365 is an out-of-bounds access (valid indices are 0 to 1364).
This situation occurs when the filesystem image is corrupted (as in the Syzkaller test case), and the tree height (`dmt_height`) specified in the on-disk metadata is larger than the valid height for the tree size (e.g., > 5 for `dmapctl`), causing the loop to iterate deeper and calculate indices beyond the end of the array.
**Fix**
Change the bounds check to use `>=` instead of `>` to correctly handle the case where the index equals the array size.
```c
--- a/fs/jfs/jfs_dmap.c
+++ b/fs/jfs/jfs_dmap.c
@@ -2974,7 +2974,7 @@ static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
/* sufficient free space found. move to the next
* level (or quit if this is the last level).
*/
- if (x + n > max_size)
+ if (x + n >= max_size)
return -ENOSPC;
if (l2nb <= tp->dmt_stree[x + n])
break;
```
|
| 7/2 |
2026/01/28 17:26 |
llm |
debugger |
0m
Model:
Tokens:
input: 3778
output: 120
thoughts: 253
Thoughts: **Debugging a JFS Array Index Out-of-Bounds Error**
Okay, so I've got a nasty array index out-of-bounds crash in `fs/jfs/jfs_dmap.c` to deal with. Specifically, the error is occurring in `dbFindLeaf` and the message says "index 1365 is out of range for type 's8[1365]'". That's a classic case β trying to access an element *past* the end of the array. The debugger points me to line 2976.
The stack trace gives me the path: `dbFindLeaf` -> `dbFindCtl` -> `dbAllocAny` -> `dbAlloc` -> `diNewIAG` -> `diAllocExt` -> `diAllocAG` -> `diAlloc` -> `ialloc` -> `jfs_mkdir`. So, the problem is ultimately triggered by a `mkdir` operation, which then trickles down through a series of allocation functions, eventually hitting the `dbFindLeaf` function.
The error is clearly in `dbFindLeaf`, accessing index 1365 on an array of size 1365. That means the index is *equal* to the array size, which is, of course, out of bounds. Valid indices are 0 to 1364. My immediate next step is to examine the code around line 2976 in `fs/jfs/jfs_dmap.c`, and see what values are being used to calculate the array index. I suspect there's an off-by-one error somewhere.
|
| 8/2 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeLines:true Name:dbFindLeaf]
Results: map[SourceCode:2924: /*
2925: * NAME: dbFindLeaf()
2926: *
2927: * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2928: * the index of a leaf describing the free blocks if
2929: * sufficient free blocks are found.
2930: *
2931: * the search starts at the top of the dmtree_t tree and
2932: * proceeds down the tree to the leftmost leaf with sufficient
2933: * free space.
2934: *
2935: * PARAMETERS:
2936: * tp - pointer to the tree to be searched.
2937: * l2nb - log2 number of free blocks to search for.
2938: * leafidx - return pointer to be set to the index of the leaf
2939: * describing at least l2nb free blocks if sufficient
2940: * free blocks are found.
2941: * is_ctl - determines if the tree is of type ctl
2942: *
2943: * RETURN VALUES:
2944: * 0 - success
2945: * -ENOSPC - insufficient free blocks.
2946: */
2947: static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
2948: {
2949: int ti, n = 0, k, x = 0;
2950: int max_size, max_idx;
2951:
2952: max_size = is_ctl ? CTLTREESIZE : TREESIZE;
2953: max_idx = is_ctl ? LPERCTL : LPERDMAP;
2954:
2955: /* first check the root of the tree to see if there is
2956: * sufficient free space.
2957: */
2958: if (l2nb > tp->dmt_stree[ROOT])
2959: return -ENOSPC;
2960:
2961: /* sufficient free space available. now search down the tree
2962: * starting at the next level for the leftmost leaf that
2963: * describes sufficient free space.
2964: */
2965: for (k = le32_to_cpu(tp->dmt_height), ti = 1;
2966: k > 0; k--, ti = ((ti + n) << 2) + 1) {
2967: /* search the four nodes at this level, starting from
2968: * the left.
2969: */
2970: for (x = ti, n = 0; n < 4; n++) {
2971: /* sufficient free space found. move to the next
2972: * level (or quit if this is the last level).
2973: */
2974: if (x + n > max_size)
2975: return -ENOSPC;
2976: if (l2nb <= tp->dmt_stree[x + n])
2977: break;
2978: }
2979:
2980: /* better have found something since the higher
2981: * levels of the tree said it was here.
2982: */
2983: assert(n < 4);
2984: }
2985: if (le32_to_cpu(tp->dmt_leafidx) >= max_idx)
2986: return -ENOSPC;
2987:
2988: /* set the return to the leftmost leaf describing sufficient
2989: * free space.
2990: */
2991: *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx);
2992:
2993: return (0);
2994: }
SourceFile:fs/jfs/jfs_dmap.c]
|
| 9/2 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeLines:true Name:dbFindCtl]
Results: map[SourceCode:1653: /*
1654: * NAME: dbFindCtl()
1655: *
1656: * FUNCTION: starting at a specified dmap control page level and block
1657: * number, search down the dmap control levels for a range of
1658: * contiguous free blocks large enough to satisfy an allocation
1659: * request for the specified number of free blocks.
1660: *
1661: * if sufficient contiguous free blocks are found, this routine
1662: * returns the starting block number within a dmap page that
1663: * contains or starts a range of contiqious free blocks that
1664: * is sufficient in size.
1665: *
1666: * PARAMETERS:
1667: * bmp - pointer to bmap descriptor
1668: * level - starting dmap control page level.
1669: * l2nb - log2 number of contiguous free blocks desired.
1670: * *blkno - on entry, starting block number for conducting the search.
1671: * on successful return, the first block within a dmap page
1672: * that contains or starts a range of contiguous free blocks.
1673: *
1674: * RETURN VALUES:
1675: * 0 - success
1676: * -ENOSPC - insufficient disk resources
1677: * -EIO - i/o error
1678: *
1679: * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1680: */
1681: static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno)
1682: {
1683: int rc, leafidx, lev;
1684: s64 b, lblkno;
1685: struct dmapctl *dcp;
1686: int budmin;
1687: struct metapage *mp;
1688:
1689: /* starting at the specified dmap control page level and block
1690: * number, search down the dmap control levels for the starting
1691: * block number of a dmap page that contains or starts off
1692: * sufficient free blocks.
1693: */
1694: for (lev = level, b = *blkno; lev >= 0; lev--) {
1695: /* get the buffer of the dmap control page for the block
1696: * number and level (i.e. L0, L1, L2).
1697: */
1698: lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev);
1699: mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1700: if (mp == NULL)
1701: return -EIO;
1702: dcp = (struct dmapctl *) mp->data;
1703: budmin = dcp->budmin;
1704:
1705: if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
1706: jfs_error(bmp->db_ipbmap->i_sb,
1707: "Corrupt dmapctl page\n");
1708: release_metapage(mp);
1709: return -EIO;
1710: }
1711:
1712: /* search the tree within the dmap control page for
1713: * sufficient free space. if sufficient free space is found,
1714: * dbFindLeaf() returns the index of the leaf at which
1715: * free space was found.
1716: */
1717: rc = dbFindLeaf((dmtree_t *) dcp, l2nb, &leafidx, true);
1718:
1719: /* release the buffer.
1720: */
1721: release_metapage(mp);
1722:
1723: /* space found ?
1724: */
1725: if (rc) {
1726: if (lev != level) {
1727: jfs_error(bmp->db_ipbmap->i_sb,
1728: "dmap inconsistent\n");
1729: return -EIO;
1730: }
1731: return -ENOSPC;
1732: }
1733:
1734: /* adjust the block number to reflect the location within
1735: * the dmap control page (i.e. the leaf) at which free
1736: * space was found.
1737: */
1738: b += (((s64) leafidx) << budmin);
1739:
1740: /* we stop the search at this dmap control page level if
1741: * the number of blocks required is greater than or equal
1742: * to the maximum number of blocks described at the next
1743: * (lower) level.
1744: */
1745: if (l2nb >= budmin)
1746: break;
1747: }
1748:
1749: *blkno = b;
1750: return (0);
1751: }
SourceFile:fs/jfs/jfs_dmap.c]
|
| 10/2 |
2026/01/28 17:26 |
tool |
codesearch-file-index |
0m
Args: map[SourceFile:fs/jfs/jfs_dmap.c]
Results: map[Entities:[map[Kind:function Name:blkstol2] map[Kind:function Name:cntlz] map[Kind:function Name:cnttz] map[Kind:function Name:dbAdjCtl] map[Kind:function Name:dbAdjTree] map[Kind:function Name:dbAlloc] map[Kind:function Name:dbAllocAG] map[Kind:function Name:dbAllocAny] map[Kind:function Name:dbAllocBits] map[Kind:function Name:dbAllocBottomUp] map[Kind:function Name:dbAllocCtl] map[Kind:function Name:dbAllocDmap] map[Kind:function Name:dbAllocDmapBU] map[Kind:function Name:dbAllocDmapLev] map[Kind:function Name:dbAllocNear] map[Kind:function Name:dbAllocNext] map[Kind:function Name:dbBackSplit] map[Kind:function Name:dbDiscardAG] map[Kind:function Name:dbExtend] map[Kind:function Name:dbExtendFS] map[Kind:function Name:dbFinalizeBmap] map[Kind:function Name:dbFindBits] map[Kind:function Name:dbFindCtl] map[Kind:function Name:dbFindLeaf] map[Kind:function Name:dbFree] map[Kind:function Name:dbFreeBits] map[Kind:function Name:dbFreeDmap] map[Kind:function Name:dbGetL2AGSize] map[Kind:function Name:dbInitDmap] map[Kind:function Name:dbInitDmapCtl] map[Kind:function Name:dbInitDmapTree] map[Kind:function Name:dbInitTree] map[Kind:function Name:dbJoin] map[Kind:function Name:dbMapFileSizeToMapSize] map[Kind:function Name:dbMaxBud] map[Kind:function Name:dbMount] map[Kind:function Name:dbNextAG] map[Kind:function Name:dbReAlloc] map[Kind:function Name:dbSplit] map[Kind:function Name:dbSync] map[Kind:function Name:dbUnmount] map[Kind:function Name:dbUpdatePMap] map[Kind:struct Name:range2trim]]]
|
| 11/2 |
2026/01/28 17:26 |
llm |
debugger |
0m
Model:
Tokens:
input: 7803
output: 69
thoughts: 136
Thoughts: **Debugging a JFS Index Out of Bounds Error**
Okay, so I've got an index out of range error, specifically index 1365 exceeding the bounds of an `s8[1365]` array. The error message points me to `fs/jfs/jfs_dmap.c:2976`. Right away, I know I'm dealing with the JFS file system, and this looks like a critical error within the data management layer.
Let's see, line 2976 is inside `dbFindLeaf`, and the problematic line is:
```c
if (l2nb <= tp->dmt_stree[x + n])
```
`tp` is a `dmtree_t *`, and `dmt_stree` seems to be the culprit array. That's my immediate focus now: what's going on with `dmt_stree`? I need to understand its structure, size, and how it's being used within the `dmtree_t` context. I'll check the definition of `dmtree_t` so that I can figure out the array's use and why the index is exceeding the bounds. The root cause is likely an off-by-one or a calculation error that causes the index `x + n` to exceed its expected maximum index (likely 1364 since it's an array of size 1365). Let's see how `x` and `n` are calculated.
|
| 12/2 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.h IncludeLines:true Name:dmtree_t]
Results: map[SourceCode: 172: /*
173: * common definition for dmaptree within dmap and dmapctl
174: */
175: typedef union dmtree {
176: struct dmaptree t1;
177: struct dmapctl t2;
178: } dmtree_t;
SourceFile:fs/jfs/jfs_dmap.h]
|
| 13/2 |
2026/01/28 17:26 |
tool |
codesearch-dir-index |
0m
Args:
Results: map[Files:[acl.c file.c inode.c ioctl.c jfs_acl.h jfs_btree.h jfs_debug.c jfs_debug.h jfs_dinode.h jfs_discard.c jfs_discard.h jfs_dmap.c jfs_dmap.h jfs_dtree.c jfs_dtree.h jfs_extent.c jfs_extent.h jfs_filsys.h jfs_imap.c jfs_imap.h jfs_incore.h jfs_inode.c jfs_inode.h jfs_lock.h jfs_logmgr.c jfs_logmgr.h jfs_metapage.c jfs_metapage.h jfs_mount.c jfs_superblock.h jfs_txnmgr.c jfs_txnmgr.h jfs_types.h jfs_umount.c jfs_unicode.c jfs_unicode.h jfs_xattr.h jfs_xtree.c jfs_xtree.h namei.c resize.c super.c symlink.c xattr.c] Subdirs:<nil>]
|
| 14/2 |
2026/01/28 17:26 |
llm |
debugger |
0m
Model:
Tokens:
input: 8876
output: 115
thoughts: 59
Thoughts: Okay, let's break this down.
**Diving into the DMTree Structure**
Right, so `dmtree_t` is a crucial type, a union, that allows it to hold either a `struct dmaptree` or a `struct dmapctl`. This implies some flexibility in how it's used; probably depends on the current state or function that's being performed. Let's dig into these two structures. I'll need to check `fs/jfs/jfs_dmap.h` to see how `struct dmaptree` and `struct dmapctl` are actually defined. This will illuminate the design and how they interact. Understanding the components of these structures is essential to understanding the design.
|
| 15/2 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.h IncludeLines:true Name:dmaptree]
Results: map[SourceCode: 129: /*
130: * dmap summary tree
131: *
132: * dmaptree must be consistent with dmapctl.
133: */
134: struct dmaptree {
135: __le32 nleafs; /* 4: number of tree leafs */
136: __le32 l2nleafs; /* 4: l2 number of tree leafs */
137: __le32 leafidx; /* 4: index of first tree leaf */
138: __le32 height; /* 4: height of the tree */
139: s8 budmin; /* 1: min l2 tree leaf value to combine */
140: s8 stree[TREESIZE]; /* TREESIZE: tree */
141: u8 pad[2]; /* 2: pad to word boundary */
142: }; /* - 360 - */
SourceFile:fs/jfs/jfs_dmap.h]
|
| 16/2 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.h IncludeLines:true Name:dmapctl]
Results: map[SourceCode: 157: /*
158: * disk map control page per level.
159: *
160: * dmapctl must be consistent with dmaptree.
161: */
162: struct dmapctl {
163: __le32 nleafs; /* 4: number of tree leafs */
164: __le32 l2nleafs; /* 4: l2 number of tree leafs */
165: __le32 leafidx; /* 4: index of the first tree leaf */
166: __le32 height; /* 4: height of tree */
167: s8 budmin; /* 1: minimum l2 tree leaf value */
168: s8 stree[CTLTREESIZE]; /* CTLTREESIZE: dmapctl tree */
169: u8 pad[2714]; /* 2714: pad to 4096 */
170: }; /* - 4096 - */
SourceFile:fs/jfs/jfs_dmap.h]
|
| 17/2 |
2026/01/28 17:26 |
tool |
read-file |
0m
Args: map[File:fs/jfs/jfs_dmap.h]
Results: map[Contents:/* SPDX-License-Identifier: GPL-2.0-or-later */
/*
* Copyright (C) International Business Machines Corp., 2000-2002
*/
#ifndef _H_JFS_DMAP
#define _H_JFS_DMAP
#include "jfs_txnmgr.h"
#define BMAPVERSION 1 /* version number */
#define TREESIZE (256+64+16+4+1) /* size of a dmap tree */
#define LEAFIND (64+16+4+1) /* index of 1st leaf of a dmap tree */
#define LPERDMAP 256 /* num leaves per dmap tree */
#define L2LPERDMAP 8 /* l2 number of leaves per dmap tree */
#define DBWORD 32 /* # of blks covered by a map word */
#define L2DBWORD 5 /* l2 # of blks covered by a mword */
#define BUDMIN L2DBWORD /* max free string in a map word */
#define BPERDMAP (LPERDMAP * DBWORD) /* num of blks per dmap */
#define L2BPERDMAP 13 /* l2 num of blks per dmap */
#define CTLTREESIZE (1024+256+64+16+4+1) /* size of a dmapctl tree */
#define CTLLEAFIND (256+64+16+4+1) /* idx of 1st leaf of a dmapctl tree */
#define LPERCTL 1024 /* num of leaves per dmapctl tree */
#define L2LPERCTL 10 /* l2 num of leaves per dmapctl tree */
#define ROOT 0 /* index of the root of a tree */
#define NOFREE ((s8) -1) /* no blocks free */
#define MAXAG 128 /* max number of allocation groups */
#define L2MAXAG 7 /* l2 max num of AG */
#define L2MINAGSZ 25 /* l2 of minimum AG size in bytes */
#define BMAPBLKNO 0 /* lblkno of bmap within the map */
/*
* maximum l2 number of disk blocks at the various dmapctl levels.
*/
#define L2MAXL0SIZE (L2BPERDMAP + 1 * L2LPERCTL)
#define L2MAXL1SIZE (L2BPERDMAP + 2 * L2LPERCTL)
#define L2MAXL2SIZE (L2BPERDMAP + 3 * L2LPERCTL)
/*
* maximum number of disk blocks at the various dmapctl levels.
*/
#define MAXL0SIZE ((s64)1 << L2MAXL0SIZE)
#define MAXL1SIZE ((s64)1 << L2MAXL1SIZE)
#define MAXL2SIZE ((s64)1 << L2MAXL2SIZE)
#define MAXMAPSIZE MAXL2SIZE /* maximum aggregate map size */
/*
* determine the maximum free string for four (lower level) nodes
* of the tree.
*/
static inline signed char TREEMAX(signed char *cp)
{
signed char tmp1, tmp2;
tmp1 = max(*(cp+2), *(cp+3));
tmp2 = max(*(cp), *(cp+1));
return max(tmp1, tmp2);
}
/*
* convert disk block number to the logical block number of the dmap
* describing the disk block. s is the log2(number of logical blocks per page)
*
* The calculation figures out how many logical pages are in front of the dmap.
* - the number of dmaps preceding it
* - the number of L0 pages preceding its L0 page
* - the number of L1 pages preceding its L1 page
* - 3 is added to account for the L2, L1, and L0 page for this dmap
* - 1 is added to account for the control page of the map.
*/
#define BLKTODMAP(b,s) \
((((b) >> 13) + ((b) >> 23) + ((b) >> 33) + 3 + 1) << (s))
/*
* convert disk block number to the logical block number of the LEVEL 0
* dmapctl describing the disk block. s is the log2(number of logical blocks
* per page)
*
* The calculation figures out how many logical pages are in front of the L0.
* - the number of dmap pages preceding it
* - the number of L0 pages preceding it
* - the number of L1 pages preceding its L1 page
* - 2 is added to account for the L2, and L1 page for this L0
* - 1 is added to account for the control page of the map.
*/
#define BLKTOL0(b,s) \
(((((b) >> 23) << 10) + ((b) >> 23) + ((b) >> 33) + 2 + 1) << (s))
/*
* convert disk block number to the logical block number of the LEVEL 1
* dmapctl describing the disk block. s is the log2(number of logical blocks
* per page)
*
* The calculation figures out how many logical pages are in front of the L1.
* - the number of dmap pages preceding it
* - the number of L0 pages preceding it
* - the number of L1 pages preceding it
* - 1 is added to account for the L2 page
* - 1 is added to account for the control page of the map.
*/
#define BLKTOL1(b,s) \
(((((b) >> 33) << 20) + (((b) >> 33) << 10) + ((b) >> 33) + 1 + 1) << (s))
/*
* convert disk block number to the logical block number of the dmapctl
* at the specified level which describes the disk block.
*/
#define BLKTOCTL(b,s,l) \
(((l) == 2) ? 1 : ((l) == 1) ? BLKTOL1((b),(s)) : BLKTOL0((b),(s)))
/*
* convert aggregate map size to the zero origin dmapctl level of the
* top dmapctl.
*/
#define BMAPSZTOLEV(size) \
(((size) <= MAXL0SIZE) ? 0 : ((size) <= MAXL1SIZE) ? 1 : 2)
/* convert disk block number to allocation group number.
*/
#define BLKTOAG(b,sbi) ((b) >> ((sbi)->bmap->db_agl2size))
/* convert allocation group number to starting disk block
* number.
*/
#define AGTOBLK(a,ip) \
((s64)(a) << (JFS_SBI((ip)->i_sb)->bmap->db_agl2size))
/*
* dmap summary tree
*
* dmaptree must be consistent with dmapctl.
*/
struct dmaptree {
__le32 nleafs; /* 4: number of tree leafs */
__le32 l2nleafs; /* 4: l2 number of tree leafs */
__le32 leafidx; /* 4: index of first tree leaf */
__le32 height; /* 4: height of the tree */
s8 budmin; /* 1: min l2 tree leaf value to combine */
s8 stree[TREESIZE]; /* TREESIZE: tree */
u8 pad[2]; /* 2: pad to word boundary */
}; /* - 360 - */
/*
* dmap page per 8K blocks bitmap
*/
struct dmap {
__le32 nblocks; /* 4: num blks covered by this dmap */
__le32 nfree; /* 4: num of free blks in this dmap */
__le64 start; /* 8: starting blkno for this dmap */
struct dmaptree tree; /* 360: dmap tree */
u8 pad[1672]; /* 1672: pad to 2048 bytes */
__le32 wmap[LPERDMAP]; /* 1024: bits of the working map */
__le32 pmap[LPERDMAP]; /* 1024: bits of the persistent map */
}; /* - 4096 - */
/*
* disk map control page per level.
*
* dmapctl must be consistent with dmaptree.
*/
struct dmapctl {
__le32 nleafs; /* 4: number of tree leafs */
__le32 l2nleafs; /* 4: l2 number of tree leafs */
__le32 leafidx; /* 4: index of the first tree leaf */
__le32 height; /* 4: height of tree */
s8 budmin; /* 1: minimum l2 tree leaf value */
s8 stree[CTLTREESIZE]; /* CTLTREESIZE: dmapctl tree */
u8 pad[2714]; /* 2714: pad to 4096 */
}; /* - 4096 - */
/*
* common definition for dmaptree within dmap and dmapctl
*/
typedef union dmtree {
struct dmaptree t1;
struct dmapctl t2;
} dmtree_t;
/* macros for accessing fields within dmtree */
#define dmt_nleafs t1.nleafs
#define dmt_l2nleafs t1.l2nleafs
#define dmt_leafidx t1.leafidx
#define dmt_height t1.height
#define dmt_budmin t1.budmin
#define dmt_stree t2.stree
/*
* on-disk aggregate disk allocation map descriptor.
*/
struct dbmap_disk {
__le64 dn_mapsize; /* 8: number of blocks in aggregate */
__le64 dn_nfree; /* 8: num free blks in aggregate map */
__le32 dn_l2nbperpage; /* 4: number of blks per page */
__le32 dn_numag; /* 4: total number of ags */
__le32 dn_maxlevel; /* 4: number of active ags */
__le32 dn_maxag; /* 4: max active alloc group number */
__le32 dn_agpref; /* 4: preferred alloc group (hint) */
__le32 dn_aglevel; /* 4: dmapctl level holding the AG */
__le32 dn_agheight; /* 4: height in dmapctl of the AG */
__le32 dn_agwidth; /* 4: width in dmapctl of the AG */
__le32 dn_agstart; /* 4: start tree index at AG height */
__le32 dn_agl2size; /* 4: l2 num of blks per alloc group */
__le64 dn_agfree[MAXAG];/* 8*MAXAG: per AG free count */
__le64 dn_agsize; /* 8: num of blks per alloc group */
s8 dn_maxfreebud; /* 1: max free buddy system */
u8 pad[3007]; /* 3007: pad to 4096 */
}; /* - 4096 - */
struct dbmap {
s64 dn_mapsize; /* number of blocks in aggregate */
s64 dn_nfree; /* num free blks in aggregate map */
int dn_l2nbperpage; /* number of blks per page */
int dn_numag; /* total number of ags */
int dn_maxlevel; /* number of active ags */
int dn_maxag; /* max active alloc group number */
int dn_agpref; /* preferred alloc group (hint) */
int dn_aglevel; /* dmapctl level holding the AG */
int dn_agheight; /* height in dmapctl of the AG */
int dn_agwidth; /* width in dmapctl of the AG */
int dn_agstart; /* start tree index at AG height */
int dn_agl2size; /* l2 num of blks per alloc group */
s64 dn_agfree[MAXAG]; /* per AG free count */
s64 dn_agsize; /* num of blks per alloc group */
signed char dn_maxfreebud; /* max free buddy system */
}; /* - 4096 - */
/*
* in-memory aggregate disk allocation map descriptor.
*/
struct bmap {
struct dbmap db_bmap; /* on-disk aggregate map descriptor */
struct inode *db_ipbmap; /* ptr to aggregate map incore inode */
struct mutex db_bmaplock; /* aggregate map lock */
atomic_t db_active[MAXAG]; /* count of active, open files in AG */
u32 *db_DBmap;
};
/* macros for accessing fields within in-memory aggregate map descriptor */
#define db_mapsize db_bmap.dn_mapsize
#define db_nfree db_bmap.dn_nfree
#define db_agfree db_bmap.dn_agfree
#define db_agsize db_bmap.dn_agsize
#define db_agl2size db_bmap.dn_agl2size
#define db_agwidth db_bmap.dn_agwidth
#define db_agheight db_bmap.dn_agheight
#define db_agstart db_bmap.dn_agstart
#define db_numag db_bmap.dn_numag
#define db_maxlevel db_bmap.dn_maxlevel
#define db_aglevel db_bmap.dn_aglevel
#define db_agpref db_bmap.dn_agpref
#define db_maxag db_bmap.dn_maxag
#define db_maxfreebud db_bmap.dn_maxfreebud
#define db_l2nbperpage db_bmap.dn_l2nbperpage
/*
* macros for various conversions needed by the allocators.
* blkstol2(), cntlz(), and cnttz() are operating system dependent functions.
*/
/* convert number of blocks to log2 number of blocks, rounding up to
* the next log2 value if blocks is not a l2 multiple.
*/
#define BLKSTOL2(d) (blkstol2(d))
/* convert number of leafs to log2 leaf value */
#define NLSTOL2BSZ(n) (31 - cntlz((n)) + BUDMIN)
/* convert leaf index to log2 leaf value */
#define LITOL2BSZ(n,m,b) ((((n) == 0) ? (m) : cnttz((n))) + (b))
/* convert a block number to a dmap control leaf index */
#define BLKTOCTLLEAF(b,m) \
(((b) & (((s64)1 << ((m) + L2LPERCTL)) - 1)) >> (m))
/* convert log2 leaf value to buddy size */
#define BUDSIZE(s,m) (1 << ((s) - (m)))
/*
* external references.
*/
extern int dbMount(struct inode *ipbmap);
extern int dbUnmount(struct inode *ipbmap, int mounterror);
extern int dbFree(struct inode *ipbmap, s64 blkno, s64 nblocks);
extern int dbUpdatePMap(struct inode *ipbmap,
int free, s64 blkno, s64 nblocks, struct tblock * tblk);
extern int dbNextAG(struct inode *ipbmap);
extern int dbAlloc(struct inode *ipbmap, s64 hint, s64 nblocks, s64 * results);
extern int dbReAlloc(struct inode *ipbmap,
s64 blkno, s64 nblocks, s64 addnblocks, s64 * results);
extern int dbSync(struct inode *ipbmap);
extern int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks);
extern int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks);
extern void dbFinalizeBmap(struct inode *ipbmap);
extern s64 dbMapFileSizeToMapSize(struct inode *ipbmap);
extern s64 dbDiscardAG(struct inode *ip, int agno, s64 minlen);
#endif /* _H_JFS_DMAP */
]
|
| 18/2 |
2026/01/28 17:26 |
llm |
debugger |
0m
Model:
Tokens:
input: 14094
output: 47
thoughts: 4678
Thoughts: **Analysis of the Out-of-Bounds Access in `dbFindLeaf`**
Okay, so the crash report indicates an out-of-bounds read within `dbFindLeaf`, specifically accessing `tp->dmt_stree[1365]`. My primary goal is to understand *why* this is happening. The `dmtree_t` union, which points to either a `dmaptree` or a `dmapctl` structure, is the source of the problem. In this case, it's the `dmapctl` structure, which contains the tree data (`stree`) and control information including `height`. The `stree` is an array of `s8` with a size derived from `CTLTREESIZE`, which is calculated to be 1365. This means valid indices range from 0 to 1364. The crash confirms the index 1365 is being accessed.
The core issue lies within `dbFindLeaf`'s loop that descends the tree structure. The function iterates based on the `dmt_height` field within the `dmapctl` structure. The central loop calculates the index for the next level's children using a formula `ti = ((ti + n) << 2) + 1`, which is correct for a 4-way tree traversal, starting with an initial `ti` of 1 to bypass the root node at index 0. However, after the loop, the program updates `ti` in preparation for the next level. The key problem is the bounds check at line 2974: `if (x + n > max_size)`.
The crucial insight here is the tree's structure and valid index boundaries, the code's logic, and the values of `height`. The code checks if the current index `x + n` is *greater than* `max_size` (1365). Given how the `ti` is updated, the code can try to read at position 1365, which is out-of-bounds. However, the condition *only* prevents access *past* the end of the array. The check should really be `>=` instead of `>`.
The bug stems from the fact the `height` value within `dmapctl` is not validated and that the bounds check is *too loose*. If a corrupted or fuzzed filesystem image results in a value of `height` greater than 5, the program will try to descend the tree beyond its limits. During the final iteration of the outer loop, the inner loop calculates a child index of 1365, which then causes the access. The correct fix is to change the comparison operator in the bounds check to `>=`. Furthermore, we should add validation in `dbFindCtl` to make sure the height value is within a reasonable range when reading the `dmapctl` structure.
|
| 19/2 |
2026/01/28 17:26 |
tool |
codesearch-find-references |
0m
Error:
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeSnippetLines:5 Name:dmt_stree]
Results: map[References:<nil> TruncatedOutput:false]
|
| 20/2 |
2026/01/28 17:26 |
llm |
debugger |
0m
Model:
Tokens:
input: 19456
output: 44
thoughts: 54
Thoughts: **Investigating Macro Aliasing and Indexing**
Okay, so I'm looking at this `dmt_stree` thing, and it's hitting me that it's a macro. My gut feeling, based on previous experience, is that the indexing tools I'm using *might* be skipping it when it comes to references, especially if the macro is essentially an alias for a structure field. This could easily happen, and it's a very common gotcha. If it's skipping the macro I won't have the cross reference in my tools.
To confirm this suspicion, I need to hunt down where `stree` is actually *defined* in relation to the file system. Time to go looking. I'll search for `stree` specifically, but my initial hunch is that it'll reside in the `fs/jfs/jfs_dmap.c` file since we're dealing with the JFS file system and "dmap" seems relevant to data mapping. Let's see what we can find.
|
| 21/2 |
2026/01/28 17:26 |
tool |
codesearch-find-references |
0m
Error:
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeSnippetLines:5 Name:stree]
Results: map[References:<nil> TruncatedOutput:false]
|
| 22/2 |
2026/01/28 17:26 |
llm |
debugger |
0m
Model:
Tokens:
input: 19797
output: 49
thoughts: 42
Thoughts: Okay, here's my interpretation of those thoughts, tailored for an expert audience, presented in the first person:
**Navigating Unfamiliar Territory**
Well, that's not quite what I was anticipating. The presence of `stree` as a field within both `struct dmaptree` and `struct dmapctl` is a little surprising. It suggests a potential shared or related responsibility, or perhaps some form of containment or abstraction. Given that these are obviously core data structures related to the dmap subsystem, the relationship warrants further investigation.
I think the most effective way to gain clarity now is to formulate a more targeted search. I'll need to look beyond a general search for `stree`. My instinct is to zero in on the precise context within those structures. Therefore, I should search for `struct dmaptree::stree`. That should provide me with the precise declaration and use sites and, from there, I can analyze the nature of the relationship. I'm keen to understand how `stree` functions within the larger dmap context.
|
| 23/2 |
2026/01/28 17:26 |
tool |
codesearch-find-references |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeSnippetLines:5 Name:struct dmaptree::stree]
Results: map[References:[map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocBits SourceFile:fs/jfs/jfs_dmap.c SourceLine:2148 SourceSnippet:2143: dmtree_t *tp = (dmtree_t *) & dp->tree;
2144: int size;
2145: s8 *leaf;
2146:
2147: /* pick up a pointer to the leaves of the dmap tree */
2148: leaf = dp->tree.stree + LEAFIND;
2149:
2150: /* determine the bit number and word within the dmap of the
2151: * starting block.
2152: */
2153: dbitno = blkno & (BPERDMAP - 1);
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:1854 SourceSnippet:1849: }
1850: dp = (struct dmap *) mp->data;
1851:
1852: /* the dmap better be all free.
1853: */
1854: if (dp->tree.stree[ROOT] != L2BPERDMAP) {
1855: release_metapage(mp);
1856: jfs_error(bmp->db_ipbmap->i_sb,
1857: "the dmap is not all free\n");
1858: rc = -EIO;
1859: goto backout;
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocDmap SourceFile:fs/jfs/jfs_dmap.c SourceLine:2031 SourceSnippet:2026: int rc;
2027:
2028: /* save the current value of the root (i.e. maximum free string)
2029: * of the dmap tree.
2030: */
2031: oldroot = dp->tree.stree[ROOT];
2032:
2033: /* allocate the specified (blocks) bits */
2034: dbAllocBits(bmp, dp, blkno, nblocks);
2035:
2036: /* if the root has not changed, done. */
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocDmap SourceFile:fs/jfs/jfs_dmap.c SourceLine:2037 SourceSnippet:2032:
2033: /* allocate the specified (blocks) bits */
2034: dbAllocBits(bmp, dp, blkno, nblocks);
2035:
2036: /* if the root has not changed, done. */
2037: if (dp->tree.stree[ROOT] == oldroot)
2038: return (0);
2039:
2040: /* root changed. bubble the change up to the dmap control pages.
2041: * if the adjustment of the upper level control pages fails,
2042: * backout the bit allocation (thus making everything consistent).
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocDmap SourceFile:fs/jfs/jfs_dmap.c SourceLine:2044 SourceSnippet:2039:
2040: /* root changed. bubble the change up to the dmap control pages.
2041: * if the adjustment of the upper level control pages fails,
2042: * backout the bit allocation (thus making everything consistent).
2043: */
2044: if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 1, 0)))
2045: dbFreeBits(bmp, dp, blkno, nblocks);
2046:
2047: return (rc);
2048: }
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocDmapBU SourceFile:fs/jfs/jfs_dmap.c SourceLine:3257 SourceSnippet:3252: struct dmaptree *tp = (struct dmaptree *) & dp->tree;
3253:
3254: /* save the current value of the root (i.e. maximum free string)
3255: * of the dmap tree.
3256: */
3257: oldroot = tp->stree[ROOT];
3258:
3259: /* determine the bit number and word within the dmap of the
3260: * starting block.
3261: */
3262: dbitno = blkno & (BPERDMAP - 1);
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocDmapBU SourceFile:fs/jfs/jfs_dmap.c SourceLine:3336 SourceSnippet:3331: bmp->db_nfree -= nblocks;
3332:
3333: BMAP_UNLOCK(bmp);
3334:
3335: /* if the root has not changed, done. */
3336: if (tp->stree[ROOT] == oldroot)
3337: return (0);
3338:
3339: /* root changed. bubble the change up to the dmap control pages.
3340: * if the adjustment of the upper level control pages fails,
3341: * backout the bit allocation (thus making everything consistent).
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocDmapBU SourceFile:fs/jfs/jfs_dmap.c SourceLine:3343 SourceSnippet:3338:
3339: /* root changed. bubble the change up to the dmap control pages.
3340: * if the adjustment of the upper level control pages fails,
3341: * backout the bit allocation (thus making everything consistent).
3342: */
3343: if ((rc = dbAdjCtl(bmp, blkno, tp->stree[ROOT], 1, 0)))
3344: dbFreeBits(bmp, dp, blkno, nblocks);
3345:
3346: return (rc);
3347: }
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocDmapLev SourceFile:fs/jfs/jfs_dmap.c SourceLine:1984 SourceSnippet:1979:
1980: /* if not all bits of the dmap word are free, get the starting
1981: * bit number within the dmap word of the required string of free
1982: * bits and adjust the block number with this value.
1983: */
1984: if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN)
1985: blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb);
1986:
1987: /* allocate the blocks */
1988: if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0)
1989: *results = blkno;
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocNear SourceFile:fs/jfs/jfs_dmap.c SourceLine:1214 SourceSnippet:1209: if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) {
1210: jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n");
1211: return -EIO;
1212: }
1213:
1214: leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1215:
1216: /* determine the word within the dmap that holds the hint
1217: * (i.e. blkno). also, determine the last word in the dmap
1218: * that we'll include in our examination.
1219: */
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocNext SourceFile:fs/jfs/jfs_dmap.c SourceLine:1086 SourceSnippet:1081: return -EIO;
1082: }
1083:
1084: /* pick up a pointer to the leaves of the dmap tree.
1085: */
1086: leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1087:
1088: /* determine the bit number and word within the dmap of the
1089: * starting block.
1090: */
1091: dbitno = blkno & (BPERDMAP - 1);
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbFreeDmap SourceFile:fs/jfs/jfs_dmap.c SourceLine:2086 SourceSnippet:2081: int rc = 0, word;
2082:
2083: /* save the current value of the root (i.e. maximum free string)
2084: * of the dmap tree.
2085: */
2086: oldroot = dp->tree.stree[ROOT];
2087:
2088: /* free the specified (blocks) bits */
2089: rc = dbFreeBits(bmp, dp, blkno, nblocks);
2090:
2091: /* if error or the root has not changed, done. */
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbFreeDmap SourceFile:fs/jfs/jfs_dmap.c SourceLine:2092 SourceSnippet:2087:
2088: /* free the specified (blocks) bits */
2089: rc = dbFreeBits(bmp, dp, blkno, nblocks);
2090:
2091: /* if error or the root has not changed, done. */
2092: if (rc || (dp->tree.stree[ROOT] == oldroot))
2093: return (rc);
2094:
2095: /* root changed. bubble the change up to the dmap control pages.
2096: * if the adjustment of the upper level control pages fails,
2097: * backout the deallocation.
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbFreeDmap SourceFile:fs/jfs/jfs_dmap.c SourceLine:2099 SourceSnippet:2094:
2095: /* root changed. bubble the change up to the dmap control pages.
2096: * if the adjustment of the upper level control pages fails,
2097: * backout the deallocation.
2098: */
2099: if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) {
2100: word = (blkno & (BPERDMAP - 1)) >> L2DBWORD;
2101:
2102: /* as part of backing out the deallocation, we will have
2103: * to back split the dmap tree if the deallocation caused
2104: * the freed blocks to become part of a larger binary buddy
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbFreeDmap SourceFile:fs/jfs/jfs_dmap.c SourceLine:2107 SourceSnippet:2102: /* as part of backing out the deallocation, we will have
2103: * to back split the dmap tree if the deallocation caused
2104: * the freed blocks to become part of a larger binary buddy
2105: * system.
2106: */
2107: if (dp->tree.stree[word] == NOFREE)
2108: dbBackSplit((dmtree_t *)&dp->tree, word, false);
2109:
2110: dbAllocBits(bmp, dp, blkno, nblocks);
2111: }
2112:
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbInitDmapTree SourceFile:fs/jfs/jfs_dmap.c SourceLine:3850 SourceSnippet:3845:
3846: /* init each leaf from corresponding wmap word:
3847: * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3848: * bitmap word are allocated.
3849: */
3850: cp = tp->stree + le32_to_cpu(tp->leafidx);
3851: for (i = 0; i < LPERDMAP; i++)
3852: *cp++ = dbMaxBud((u8 *) & dp->wmap[i]);
3853:
3854: /* build the dmap's binary buddy summary tree */
3855: return (dbInitTree(tp));
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbInitTree SourceFile:fs/jfs/jfs_dmap.c SourceLine:3884 SourceSnippet:3879: {
3880: int l2max, l2free, bsize, nextb, i;
3881: int child, parent, nparent;
3882: s8 *tp, *cp, *cp1;
3883:
3884: tp = dtp->stree;
3885:
3886: /* Determine the maximum free string possible for the leaves */
3887: l2max = le32_to_cpu(dtp->l2nleafs) + dtp->budmin;
3888:
3889: /*
]] TruncatedOutput:false]
|
| 24/2 |
2026/01/28 17:26 |
llm |
debugger |
0m
Model:
Tokens:
input: 24059
output: 49
thoughts: 134
Thoughts: **Analyzing the Structure Tree Access Patterns**
Okay, let's break down these `stree` access patterns. It looks like the codebase uses it in a couple of ways: `dp->tree.stree` and also `tp->stree`, where `tp` is either a `dmtree_t *` or a `struct dmaptree *`. I need to understand how these relate, and what's going on with the different structures.
Now, I was looking at `dbFindLeaf` and noticed a discrepancy. It accesses `tp->dmt_stree`, which, I see, is actually `tp->t2.stree`. The tool missed the connection because my search was too specific, focusing on `struct dmaptree::stree` while `dbFindLeaf` hits `struct dmapctl::stree`. That's a classic search oversight, easy to do when you're jumping around different structures like this.
My next step is to examine how `struct dmapctl::stree` is actually being *used* throughout the code. I need to get a clear picture of its role and how it interacts with the rest of the data structures.
|
| 25/2 |
2026/01/28 17:26 |
tool |
codesearch-find-references |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeSnippetLines:5 Name:struct dmapctl::stree]
Results: map[References:[map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:2503 SourceSnippet:2498: ti = leafno + le32_to_cpu(dcp->leafidx);
2499:
2500: /* save the current leaf value and the current root level (i.e.
2501: * maximum l2 free string described by this dmapctl).
2502: */
2503: oldval = dcp->stree[ti];
2504: oldroot = dcp->stree[ROOT];
2505:
2506: /* check if this is a control page update for an allocation.
2507: * if so, update the leaf to reflect the new leaf value using
2508: * dbSplit(); otherwise (deallocation), use dbJoin() to update
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:2504 SourceSnippet:2499:
2500: /* save the current leaf value and the current root level (i.e.
2501: * maximum l2 free string described by this dmapctl).
2502: */
2503: oldval = dcp->stree[ti];
2504: oldroot = dcp->stree[ROOT];
2505:
2506: /* check if this is a control page update for an allocation.
2507: * if so, update the leaf to reflect the new leaf value using
2508: * dbSplit(); otherwise (deallocation), use dbJoin() to update
2509: * the leaf with the new value. in addition to updating the
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:2531 SourceSnippet:2526: rc = dbBackSplit((dmtree_t *)dcp, leafno, true);
2527: if (rc) {
2528: release_metapage(mp);
2529: return rc;
2530: }
2531: oldval = dcp->stree[ti];
2532: }
2533: dbSplit((dmtree_t *) dcp, leafno, dcp->budmin, newval, true);
2534: } else {
2535: rc = dbJoin((dmtree_t *) dcp, leafno, newval, true);
2536: if (rc) {
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:2549 SourceSnippet:2544: * the current top level (i.e. L0, L1, L2) of the map. if so (i.e.
2545: * root changed and this is not the top level), call this routine
2546: * again (recursion) for the next higher level of the mapping to
2547: * reflect the change in root for the current dmap control page.
2548: */
2549: if (dcp->stree[ROOT] != oldroot) {
2550: /* are we below the top level of the map. if so,
2551: * bubble the root up to the next higher level.
2552: */
2553: if (level < bmp->db_maxlevel) {
2554: /* bubble up the new root of this dmap control page to
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:2558 SourceSnippet:2553: if (level < bmp->db_maxlevel) {
2554: /* bubble up the new root of this dmap control page to
2555: * the next level.
2556: */
2557: if ((rc =
2558: dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc,
2559: level + 1))) {
2560: /* something went wrong in bubbling up the new
2561: * root value, so backout the changes to the
2562: * current dmap control page.
2563: */
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:2574 SourceSnippet:2569: * caused a larger binary buddy system
2570: * to form and we may now be in the
2571: * middle of it. if this is the case,
2572: * back split the buddies.
2573: */
2574: if (dcp->stree[ti] == NOFREE)
2575: dbBackSplit((dmtree_t *)
2576: dcp, leafno, true);
2577: dbSplit((dmtree_t *) dcp, leafno,
2578: dcp->budmin, oldval, true);
2579: }
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:2596 SourceSnippet:2591: assert(level == bmp->db_maxlevel);
2592: if (bmp->db_maxfreebud != oldroot) {
2593: jfs_error(bmp->db_ipbmap->i_sb,
2594: "the maximum free buddy is not the old root\n");
2595: }
2596: bmp->db_maxfreebud = dcp->stree[ROOT];
2597: }
2598: }
2599:
2600: /* write the buffer.
2601: */
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjTree SourceFile:fs/jfs/jfs_dmap.c SourceLine:2881 SourceSnippet:2876: return;
2877:
2878: /* is the current value the same as the old value ? if so,
2879: * there is nothing to do.
2880: */
2881: if (tp->dmt_stree[lp] == newval)
2882: return;
2883:
2884: /* set the new value.
2885: */
2886: tp->dmt_stree[lp] = newval;
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjTree SourceFile:fs/jfs/jfs_dmap.c SourceLine:2886 SourceSnippet:2881: if (tp->dmt_stree[lp] == newval)
2882: return;
2883:
2884: /* set the new value.
2885: */
2886: tp->dmt_stree[lp] = newval;
2887:
2888: /* bubble the new value up the tree as required.
2889: */
2890: for (k = 0; k < le32_to_cpu(tp->dmt_height); k++) {
2891: if (lp == 0)
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjTree SourceFile:fs/jfs/jfs_dmap.c SourceLine:2905 SourceSnippet:2900: */
2901: pp = (lp - 1) >> 2;
2902:
2903: /* determine the maximum of the 4 leaves.
2904: */
2905: max = TREEMAX(&tp->dmt_stree[lp]);
2906:
2907: /* if the maximum of the 4 is the same as the
2908: * parent's value, we're done.
2909: */
2910: if (tp->dmt_stree[pp] == max)
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjTree SourceFile:fs/jfs/jfs_dmap.c SourceLine:2910 SourceSnippet:2905: max = TREEMAX(&tp->dmt_stree[lp]);
2906:
2907: /* if the maximum of the 4 is the same as the
2908: * parent's value, we're done.
2909: */
2910: if (tp->dmt_stree[pp] == max)
2911: break;
2912:
2913: /* parent gets new value.
2914: */
2915: tp->dmt_stree[pp] = max;
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAdjTree SourceFile:fs/jfs/jfs_dmap.c SourceLine:2915 SourceSnippet:2910: if (tp->dmt_stree[pp] == max)
2911: break;
2912:
2913: /* parent gets new value.
2914: */
2915: tp->dmt_stree[pp] = max;
2916:
2917: /* parent becomes leaf for next go-round.
2918: */
2919: lp = pp;
2920: }
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocAG SourceFile:fs/jfs/jfs_dmap.c SourceLine:1407 SourceSnippet:1402: * subtree.
1403: */
1404: for (i = 0; i < bmp->db_agwidth; i++, ti++) {
1405: /* is there sufficient free space ?
1406: */
1407: if (l2nb > dcp->stree[ti])
1408: continue;
1409:
1410: /* sufficient free space found in a subtree. now search down
1411: * the subtree to find the leftmost leaf that describes this
1412: * free space.
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbAllocAG SourceFile:fs/jfs/jfs_dmap.c SourceLine:1416 SourceSnippet:1411: * the subtree to find the leftmost leaf that describes this
1412: * free space.
1413: */
1414: for (k = bmp->db_agheight; k > 0; k--) {
1415: for (n = 0, m = (ti << 2) + 1; n < 4; n++) {
1416: if (l2nb <= dcp->stree[m + n]) {
1417: ti = m + n;
1418: break;
1419: }
1420: }
1421: if (n == 4) {
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbBackSplit SourceFile:fs/jfs/jfs_dmap.c SourceLine:2695 SourceSnippet:2690: */
2691: static int dbBackSplit(dmtree_t *tp, int leafno, bool is_ctl)
2692: {
2693: int budsz, bud, w, bsz, size;
2694: int cursz;
2695: s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2696:
2697: /* leaf should be part (not first part) of a binary
2698: * buddy system.
2699: */
2700: assert(leaf[leafno] == NOFREE);
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbExtendFS SourceFile:fs/jfs/jfs_dmap.c SourceLine:3460 SourceSnippet:3455: }
3456: l2dcp = (struct dmapctl *) l2mp->data;
3457:
3458: /* compute start L1 */
3459: k = blkno >> L2MAXL1SIZE;
3460: l2leaf = l2dcp->stree + CTLLEAFIND + k;
3461: p = BLKTOL1(blkno, sbi->l2nbperpage); /* L1 page */
3462:
3463: /*
3464: * extend each L1 in L2
3465: */
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbExtendFS SourceFile:fs/jfs/jfs_dmap.c SourceLine:3477 SourceSnippet:3472: goto errout;
3473: l1dcp = (struct dmapctl *) l1mp->data;
3474:
3475: /* compute start L0 */
3476: j = (blkno & (MAXL1SIZE - 1)) >> L2MAXL0SIZE;
3477: l1leaf = l1dcp->stree + CTLLEAFIND + j;
3478: p = BLKTOL0(blkno, sbi->l2nbperpage);
3479: j0 = false;
3480: } else {
3481: /* assign/init L1 page */
3482: l1mp = get_metapage(ipbmap, p, PSIZE, 0);
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbExtendFS SourceFile:fs/jfs/jfs_dmap.c SourceLine:3490 SourceSnippet:3485:
3486: l1dcp = (struct dmapctl *) l1mp->data;
3487:
3488: /* compute start L0 */
3489: j = 0;
3490: l1leaf = l1dcp->stree + CTLLEAFIND;
3491: p += nbperpage; /* 1st L0 of L1.k */
3492: }
3493:
3494: /*
3495: * extend each L0 in L1
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbExtendFS SourceFile:fs/jfs/jfs_dmap.c SourceLine:3510 SourceSnippet:3505: l0dcp = (struct dmapctl *) l0mp->data;
3506:
3507: /* compute start dmap */
3508: i = (blkno & (MAXL0SIZE - 1)) >>
3509: L2BPERDMAP;
3510: l0leaf = l0dcp->stree + CTLLEAFIND + i;
3511: p = BLKTODMAP(blkno,
3512: sbi->l2nbperpage);
3513: i0 = false;
3514: } else {
3515: /* assign/init L0 page */
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbExtendFS SourceFile:fs/jfs/jfs_dmap.c SourceLine:3524 SourceSnippet:3519:
3520: l0dcp = (struct dmapctl *) l0mp->data;
3521:
3522: /* compute start dmap */
3523: i = 0;
3524: l0leaf = l0dcp->stree + CTLLEAFIND;
3525: p += nbperpage; /* 1st dmap of L0.j */
3526: }
3527:
3528: /*
3529: * extend each dmap in L0
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbFindLeaf SourceFile:fs/jfs/jfs_dmap.c SourceLine:2958 SourceSnippet:2953: max_idx = is_ctl ? LPERCTL : LPERDMAP;
2954:
2955: /* first check the root of the tree to see if there is
2956: * sufficient free space.
2957: */
2958: if (l2nb > tp->dmt_stree[ROOT])
2959: return -ENOSPC;
2960:
2961: /* sufficient free space available. now search down the tree
2962: * starting at the next level for the leftmost leaf that
2963: * describes sufficient free space.
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbFindLeaf SourceFile:fs/jfs/jfs_dmap.c SourceLine:2976 SourceSnippet:2971: /* sufficient free space found. move to the next
2972: * level (or quit if this is the last level).
2973: */
2974: if (x + n > max_size)
2975: return -ENOSPC;
2976: if (l2nb <= tp->dmt_stree[x + n])
2977: break;
2978: }
2979:
2980: /* better have found something since the higher
2981: * levels of the tree said it was here.
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbInitDmapCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:3968 SourceSnippet:3963: /*
3964: * initialize the leaves of current level that were not covered
3965: * by the specified input block range (i.e. the leaves have no
3966: * low level dmapctl or dmap).
3967: */
3968: cp = &dcp->stree[CTLLEAFIND + i];
3969: for (; i < LPERCTL; i++)
3970: *cp++ = NOFREE;
3971:
3972: /* build the dmap's binary buddy summary tree */
3973: return (dbInitTree((struct dmaptree *) dcp));
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbJoin SourceFile:fs/jfs/jfs_dmap.c SourceLine:2780 SourceSnippet:2775: /* can the new leaf value require a join with other leaves ?
2776: */
2777: if (newval >= tp->dmt_budmin) {
2778: /* pickup a pointer to the leaves of the tree.
2779: */
2780: leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2781:
2782: /* try to join the specified leaf into a large binary
2783: * buddy system. the join proceeds by attempting to join
2784: * the specified leafno with its buddy (leaf) at new value.
2785: * if the join occurs, we attempt to join the left leaf
] map[ReferenceKind:reads ReferencingEntityKind:function ReferencingEntityName:dbSplit SourceFile:fs/jfs/jfs_dmap.c SourceLine:2630 SourceSnippet:2625: */
2626: static void dbSplit(dmtree_t *tp, int leafno, int splitsz, int newval, bool is_ctl)
2627: {
2628: int budsz;
2629: int cursz;
2630: s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2631:
2632: /* check if the leaf needs to be split.
2633: */
2634: if (leaf[leafno] > tp->dmt_budmin) {
2635: /* the split occurs by cutting the buddy system in half
]] TruncatedOutput:false]
|
| 26/2 |
2026/01/28 17:26 |
llm |
debugger |
0m
Model:
Tokens:
input: 30246
output: 625
thoughts: 5518
Thoughts: **Analysis of the `dbFindLeaf` Crash in JFS**
Alright, let's break down this crash I'm seeing. It appears the core issue lies within `dbFindLeaf` in `fs/jfs/jfs_dmap.c`, specifically around line 2976. I'm seeing a bounds check bug. The critical line is:
```c
if (x + n > max_size)
return -ENOSPC;
```
Here's the problem: this check is allowing the code to proceed to access `tp->dmt_stree[x + n]` *when `x + n` is equal to `max_size`*. `max_size` for the `dmapctl` (which appears to be the case here given the stack) is 1365. That means we're trying to access an array element at index 1365 in an array that has valid indices from 0 to 1364. This is a classic off-by-one error.
The crash report confirms that, explicitly stating that "index 1365 is out of range for type 's8[1365]'". This nails the location.
Now, how does this happen? The crash is triggered when `tp->dmt_height` is, let's say, incorrectly large or corrupted on disk. The `dmt_height` variable, coming from a disk-read structure (`dmapctl`), indicates how many levels the tree has. If the height is *too* big, the loop in `dbFindLeaf` runs deeper than it should. The variable `ti` keeps growing, so the index `x + n` eventually becomes `max_size`.
For `dmapctl` (which uses `CTLTREESIZE = 1365`), the root cause is corrupted or an invalid `dmt_height`. If `dmt_height` is, for instance, 6, then, `x + n = 1365` can happen in the loop, resulting in the crash. The `dbFindLeaf` is traversing the tree looking for free space, and the size check is failing.
The fix? Simple. Change the `>` to `>=`:
```c
if (x + n >= max_size)
return -ENOSPC;
```
This change corrects the boundary condition, and now we will correctly check if `x + n` is greater than *or equal to* `max_size`. It prevents accessing `tp->dmt_stree[max_size]` and properly returns -ENOSPC if the index is out of bounds. The code then would return -ENOSPC, indicating an inability to find the leaf, and likely the caller will attempt recovery.
Although the crash is a bounds check, there's another concern: the validation of `dmt_height`. If we don't have proper validation on the `dmt_height` value during the metadata read, we might encounter this corruption/fuzzing. However, fixing the bounds check ensures that it's robust and prevents the crash by returning an error instead.
So, while fixing the bounds check is the most direct and immediate fix, it may be necessary to have further input validation of `dmt_height`, where it's read from disk, in the `dbFindCtl` function, but the primary target is the bounds check in `dbFindLeaf`.
|
| 27/1 |
2026/01/28 17:26 |
action |
kernel-scratch-checkouter |
0m
Results: map[KernelScratchSrc:/usr/local/google/home/dvyukov/syzkaller/agent/workdir/cache/tmp/tmp2559884510]
|
| 28/1 |
2026/01/28 17:26 |
loop |
|
9m
|
| 29/2 |
2026/01/28 17:26 |
iteration |
0 |
9m
|
| 30/3 |
2026/01/28 17:26 |
agent |
patch-generator |
0m
Model:
Instruction:
You are an experienced Linux kernel developer tasked with creating a fix for a kernel bug.
Use the codeedit tool to do code edits.
Note: you will not see your changes when looking at the code using codesearch tools.
Your final reply should contain explanation of what you did in the patch and why.
Prefer calling several tools at the same time to save round-trips.
Prompt:
The crash that corresponds to the bug is:
------------[ cut here ]------------
UBSAN: array-index-out-of-bounds in /usr/local/google/home/dvyukov/syzkaller/agent/workdir/cache/src/5452af61ab2e1f5601403fe379188fc9d8a831af/fs/jfs/jfs_dmap.c:2976:16
index 1365 is out of range for type 's8[1365]' (aka 'signed char[1365]')
CPU: 0 UID: 0 PID: 6426 Comm: syz-executor354 Not tainted syzkaller #1 PREEMPT_{RT,(full)}
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014
Call Trace:
<TASK>
__dump_stack lib/dump_stack.c:94 [inline]
dump_stack_lvl+0x10e/0x190 lib/dump_stack.c:120
ubsan_epilogue lib/ubsan.c:233 [inline]
__ubsan_handle_out_of_bounds+0x115/0x140 lib/ubsan.c:455
dbFindLeaf+0x308/0x520 fs/jfs/jfs_dmap.c:2976
dbFindCtl+0x267/0x520 fs/jfs/jfs_dmap.c:1717
dbAllocAny fs/jfs/jfs_dmap.c:1527 [inline]
dbAlloc+0x5fd/0xba0 fs/jfs/jfs_dmap.c:878
diNewIAG fs/jfs/jfs_imap.c:2510 [inline]
diAllocExt fs/jfs/jfs_imap.c:1905 [inline]
diAllocAG+0xcf0/0x1db0 fs/jfs/jfs_imap.c:1669
diAlloc+0x1d4/0x1670 fs/jfs/jfs_imap.c:1590
ialloc+0x8c/0x8f0 fs/jfs/jfs_inode.c:56
jfs_mkdir+0x193/0xa70 fs/jfs/namei.c:225
vfs_mkdir+0x530/0x5d0 fs/namei.c:5139
do_mkdirat+0x27a/0x4b0 fs/namei.c:5173
__do_sys_mkdir fs/namei.c:5200 [inline]
__se_sys_mkdir fs/namei.c:5198 [inline]
__x64_sys_mkdir+0x6c/0x80 fs/namei.c:5198
do_syscall_x64 arch/x86/entry/syscall_64.c:63 [inline]
do_syscall_64+0xe8/0xf80 arch/x86/entry/syscall_64.c:94
entry_SYSCALL_64_after_hwframe+0x77/0x7f
RIP: 0033:0x7f31a4a1c897
Code: 1f 40 00 48 89 f2 b9 00 01 00 00 48 89 fe bf 9c ff ff ff e9 7b 37 03 00 66 2e 0f 1f 84 00 00 00 00 00 90 b8 53 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 01 c3 48 c7 c2 d0 ff ff ff f7 d8 64 89 02 b8
RSP: 002b:00007f31a49be038 EFLAGS: 00000246 ORIG_RAX: 0000000000000053
RAX: ffffffffffffffda RBX: 0000200000000200 RCX: 00007f31a4a1c897
RDX: 0000000002b1247d RSI: 00000000000001ff RDI: 00002000000002c0
RBP: 0000000000000000 R08: 00000000000000fc R09: 0000000000000000
R10: 0000000000000008 R11: 0000000000000246 R12: 00002000000002c0
R13: 00007f31a49be0d0 R14: 0000000000000000 R15: 0000000000000000
</TASK>
---[ end trace ]---
The explanation of the root cause of the bug is:
The root cause of the crash is an off-by-one error in the bounds check within the `dbFindLeaf` function in `fs/jfs/jfs_dmap.c`.
The function traverses a dmap tree to find a leaf with sufficient free space. The loop calculates the index of the child nodes at the next level using `ti` (and `x` inside the loop):
```c
ti = ((ti + n) << 2) + 1
```
And then it iterates `n` from 0 to 3 to check the 4 children. The code checks if the calculated index `x + n` is within the bounds of the tree array `tp->dmt_stree` (which corresponds to `struct dmapctl::stree` of size 1365 when `is_ctl` is true).
The current bounds check is:
```c
2974: if (x + n > max_size)
2975: return -ENOSPC;
```
When `x + n` is equal to `max_size` (1365), the condition `1365 > 1365` is false, so the check passes. The code then proceeds to access the array:
```c
2976: if (l2nb <= tp->dmt_stree[x + n])
```
Accessing index 1365 of an array of size 1365 is an out-of-bounds access (valid indices are 0 to 1364).
This situation occurs when the filesystem image is corrupted (as in the Syzkaller test case), and the tree height (`dmt_height`) specified in the on-disk metadata is larger than the valid height for the tree size (e.g., > 5 for `dmapctl`), causing the loop to iterate deeper and calculate indices beyond the end of the array.
**Fix**
Change the bounds check to use `>=` instead of `>` to correctly handle the case where the index equals the array size.
```c
--- a/fs/jfs/jfs_dmap.c
+++ b/fs/jfs/jfs_dmap.c
@@ -2974,7 +2974,7 @@ static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
/* sufficient free space found. move to the next
* level (or quit if this is the last level).
*/
- if (x + n > max_size)
+ if (x + n >= max_size)
return -ENOSPC;
if (l2nb <= tp->dmt_stree[x + n])
break;
```
Reply: The bug is an array-index-out-of-bounds access in the `dbFindLeaf` function in `fs/jfs/jfs_dmap.c`.
This function traverses a dmap tree to find a leaf with sufficient free space. It calculates the index of the child nodes at the next level using `ti` (assigned to `x`). The loop iterates `n` from 0 to 3 to check up to 4 children.
The code checks if the calculated index `x + n` is within the bounds of the tree array `tp->dmt_stree`. The size of this array is `CTLTREESIZE` (1365) when `is_ctl` is true, or `TREESIZE` (341) when `is_ctl` is false.
The indices of an array of size `N` range from `0` to `N-1`.
The bounds check was:
```c
if (x + n > max_size)
return -ENOSPC;
```
When `x + n` equals `max_size`, the condition is false, and the code proceeds to access `tp->dmt_stree[x + n]`, which is `tp->dmt_stree[max_size]`. This is an out-of-bounds access (off-by-one).
This happens typically when the filesystem metadata is corrupted, claiming a tree height larger than what fits in the fixed-size array (e.g., height > 5 for `dmapctl`), causing the traversal to go beyond the valid range.
I have applied the fix by changing the condition to `>=` to ensure we return `-ENOSPC` when the index reaches `max_size`.
```c
static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
{
...
for (x = ti, n = 0; n < 4; n++) {
/* sufficient free space found. move to the next
* level (or quit if this is the last level).
*/
if (x + n >= max_size)
return -ENOSPC;
if (l2nb <= tp->dmt_stree[x + n])
break;
}
...
}
```
The change was applied to `fs/jfs/jfs_dmap.c`.
|
| 31/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 4647
output: 44
thoughts: 201
Thoughts: **Fixing a Kernel Bug in `fs/jfs/jfs_dmap.c`**
Alright, let's tackle this. I've got a bug report indicating an array-index-out-of-bounds in the `dbFindLeaf` function within the `fs/jfs/jfs_dmap.c` file of the Linux kernel. Specifically, it looks like a bounds check, `x + n > max_size`, is letting `x + n` equal to `max_size` pass through. This is leading to an access of `tp->dmt_stree[x + n]`, and since `max_size` *is* the array's size, that's definitely out of bounds.
The fix is straightforward, but I need to confirm the context before applying it. I'm thinking the logical fix is to change that '>' to a '>=' in the conditional statement.
First things first: I'll use my tools to locate the file, then verify the function and the line numbers given in the bug report. Iβm thinking line 2976 is the approximate location of the vulnerable code. Iβll use `codesearch-definition-source` to fetch the source code for the `dbFindLeaf` function. This should help me confirm that I've got the correct code, understand the surrounding context, and ensure my proposed fix is actually safe and addresses the root cause correctly.
|
| 32/4 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeLines:true Name:dbFindLeaf]
Results: map[SourceCode:2924: /*
2925: * NAME: dbFindLeaf()
2926: *
2927: * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2928: * the index of a leaf describing the free blocks if
2929: * sufficient free blocks are found.
2930: *
2931: * the search starts at the top of the dmtree_t tree and
2932: * proceeds down the tree to the leftmost leaf with sufficient
2933: * free space.
2934: *
2935: * PARAMETERS:
2936: * tp - pointer to the tree to be searched.
2937: * l2nb - log2 number of free blocks to search for.
2938: * leafidx - return pointer to be set to the index of the leaf
2939: * describing at least l2nb free blocks if sufficient
2940: * free blocks are found.
2941: * is_ctl - determines if the tree is of type ctl
2942: *
2943: * RETURN VALUES:
2944: * 0 - success
2945: * -ENOSPC - insufficient free blocks.
2946: */
2947: static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
2948: {
2949: int ti, n = 0, k, x = 0;
2950: int max_size, max_idx;
2951:
2952: max_size = is_ctl ? CTLTREESIZE : TREESIZE;
2953: max_idx = is_ctl ? LPERCTL : LPERDMAP;
2954:
2955: /* first check the root of the tree to see if there is
2956: * sufficient free space.
2957: */
2958: if (l2nb > tp->dmt_stree[ROOT])
2959: return -ENOSPC;
2960:
2961: /* sufficient free space available. now search down the tree
2962: * starting at the next level for the leftmost leaf that
2963: * describes sufficient free space.
2964: */
2965: for (k = le32_to_cpu(tp->dmt_height), ti = 1;
2966: k > 0; k--, ti = ((ti + n) << 2) + 1) {
2967: /* search the four nodes at this level, starting from
2968: * the left.
2969: */
2970: for (x = ti, n = 0; n < 4; n++) {
2971: /* sufficient free space found. move to the next
2972: * level (or quit if this is the last level).
2973: */
2974: if (x + n > max_size)
2975: return -ENOSPC;
2976: if (l2nb <= tp->dmt_stree[x + n])
2977: break;
2978: }
2979:
2980: /* better have found something since the higher
2981: * levels of the tree said it was here.
2982: */
2983: assert(n < 4);
2984: }
2985: if (le32_to_cpu(tp->dmt_leafidx) >= max_idx)
2986: return -ENOSPC;
2987:
2988: /* set the return to the leftmost leaf describing sufficient
2989: * free space.
2990: */
2991: *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx);
2992:
2993: return (0);
2994: }
SourceFile:fs/jfs/jfs_dmap.c]
|
| 33/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 6330
output: 46
thoughts: 243
Thoughts: **Analyzing the Code's Space Check**
Okay, so the code has flagged a potential out-of-space condition and the offending lines are clearly identifying a capacity issue. Specifically, lines 2974-2977. This snippet seems to be validating if an allocation of size `n` at offset `x` will exceed `max_size`. If it does, we return `-ENOSPC`, which is the correct behavior. The second check on line 2976 is interesting; it looks like we're ensuring some sort of segment size constraint against what's held in the `dmt_stree` array, based on `l2nb`.
`max_size` is initialized with either `CTLTREESIZE` or `TREESIZE`. I'm going to quickly check where these constants are defined. Given this is JFS code and the context, I'd wager they're in `fs/jfs/jfs_dmap.h`, or possibly within the source file itself if they're local to this module. I'll need to look up their definitions to fully understand the space constraints.
And, of course, there's `tp->dmt_stree[x + n]`. I need to recall the structure of `dmtree_t` so I can understand the implications of that array access. Let's make sure I know the size of that array. Understanding the context of `l2nb` is likely important too. Is this related to some kind of block group size or something similar? Gotta double-check that.
|
| 34/4 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeLines:true Name:dmtree_t]
Results: map[SourceCode: 172: /*
173: * common definition for dmaptree within dmap and dmapctl
174: */
175: typedef union dmtree {
176: struct dmaptree t1;
177: struct dmapctl t2;
178: } dmtree_t;
SourceFile:fs/jfs/jfs_dmap.h]
|
| 35/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 7085
output: 45
thoughts: 24
Thoughts: Okay, here's my interpretation of those thoughts, tailored for an expert audience, presented in the first person:
**Analyzing the Core Components**
Alright, a union, thatβs interesting. Letβs dive straight in and focus on what's driving this design choice. I need to understand the relationship between `struct dmaptree` and `struct dmapctl`. My immediate questions are: What are their roles within the system? Are they representing different views of the same underlying data, or are they completely distinct entities that simply share a structural similarity? Is this union a deliberate optimization for memory, or is it about achieving type safety through a shared interface, or perhaps some form of controlled polymorphism? Knowing the rationale behind this will clarify the overall architecture and potential design trade-offs. Let's see how they work together.
|
| 36/4 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Error:
Args: map[ContextFile:fs/jfs/jfs_dmap.h IncludeLines:true Name:struct dmaptree]
Results: map[SourceCode: SourceFile:]
|
| 37/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 7346
output: 44
thoughts: 12
Thoughts: Here's my attempt at summarizing the thought process, tailored for an expert audience:
**Refactoring My Struct Declaration**
Okay, so I'm taking another look at this code snippet, and I'm starting to think I might have been a bit heavy-handed with that `struct` prefix. It's a knee-jerk habit, I admit, a relic from older coding standards, perhaps, or maybe just a desire for absolute clarity. But is it *necessary* here? Honestly, in this specific context, the intent is pretty clear from the field names, and the code around it. The type is already obvious and if it's not you'd refactor to make it that way.
The redundancy of `struct` is becoming apparent, actually. It's cluttering the code and making it slightly less readable. I'm already using other prefixes, could be leading to "prefix-itis". I really need to remember, elegance lies in finding the *right* level of detail, not just piling on conventions. I'm aiming for clarity but this might be pushing that a little too far. It could be making things harder for the next guy to read the code, and maybe even myself down the line.
Ultimately, I want to be concise and direct without compromising readability. Maybe removing the `struct` prefix would actually *enhance* readability here. Time to give it a try.
|
| 38/4 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.h IncludeLines:true Name:dmaptree]
Results: map[SourceCode: 129: /*
130: * dmap summary tree
131: *
132: * dmaptree must be consistent with dmapctl.
133: */
134: struct dmaptree {
135: __le32 nleafs; /* 4: number of tree leafs */
136: __le32 l2nleafs; /* 4: l2 number of tree leafs */
137: __le32 leafidx; /* 4: index of first tree leaf */
138: __le32 height; /* 4: height of the tree */
139: s8 budmin; /* 1: min l2 tree leaf value to combine */
140: s8 stree[TREESIZE]; /* TREESIZE: tree */
141: u8 pad[2]; /* 2: pad to word boundary */
142: }; /* - 360 - */
SourceFile:fs/jfs/jfs_dmap.h]
|
| 39/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 7996
output: 44
thoughts: 6
Thoughts: Okay, here's my summary, in the first person, as if these are my thoughts, keeping in mind I'm an expert in my field:
**Internal Monologue on System Control**
Right, so I'm thinking about system control. Specifically, I need to get to the nuts and bolts of how things are managed. My immediate instinct is to think about the various tools at my disposal. What's the best way to interact with the underlying structure? There has to be a robust, efficient method, the command-line interface is always a good starting place, and it will be interesting to see what can be accomplished. And... *dmapctl*. That's the key.
|
| 40/4 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.h IncludeLines:true Name:dmapctl]
Results: map[SourceCode: 157: /*
158: * disk map control page per level.
159: *
160: * dmapctl must be consistent with dmaptree.
161: */
162: struct dmapctl {
163: __le32 nleafs; /* 4: number of tree leafs */
164: __le32 l2nleafs; /* 4: l2 number of tree leafs */
165: __le32 leafidx; /* 4: index of the first tree leaf */
166: __le32 height; /* 4: height of tree */
167: s8 budmin; /* 1: minimum l2 tree leaf value */
168: s8 stree[CTLTREESIZE]; /* CTLTREESIZE: dmapctl tree */
169: u8 pad[2714]; /* 2714: pad to 4096 */
170: }; /* - 4096 - */
SourceFile:fs/jfs/jfs_dmap.h]
|
| 41/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 8511
output: 27
thoughts: 268
Thoughts: **Analyzing a Potential Out-of-Bounds Array Access**
Okay, let's break this down. My initial thought process is centered around those array accesses, `stree[TREESIZE]` and `stree[CTLTREESIZE]`. In C, as I'm sure you know, arrays start at index 0, and a size `N` array has valid indices from 0 to `N-1`. So, if `max_size` is set to either `TREESIZE` or `CTLTREESIZE`, any attempt to access `stree[max_size]` is an immediate out-of-bounds error.
Looking at the code, specifically the `dbFindLeaf` function, it looks like `max_size` *is* indeed being set to either `TREESIZE` or `CTLTREESIZE`. The conditional check, `x + n > max_size`, is the culprit. Allowing `x + n` to *equal* `max_size` in the conditional means we're trying to access an element past the end of the array. That will lead to crashes and corrupt data.
So, the fix is straightforward: to prevent this out-of-bounds access, changing the greater-than operator (`>`) to a greater-than-or-equal-to operator (`>=`) is the appropriate corrective action. I believe this will fully resolve the vulnerability.
Now, to be absolutely certain I want to verify the `dmtree_t` definition. I'm going to quickly check `fs/jfs/jfs_dmap.h` with the help of `codesearch-definition-source`, though I do recall seeing it in `dmapctl`.
And finally, just to cover all bases, I need to check the definitions of `TREESIZE` and `CTLTREESIZE` to be 100% confident in the context.
|
| 42/4 |
2026/01/28 17:26 |
tool |
read-file |
0m
Args: map[File:fs/jfs/jfs_dmap.h]
Results: map[Contents:/* SPDX-License-Identifier: GPL-2.0-or-later */
/*
* Copyright (C) International Business Machines Corp., 2000-2002
*/
#ifndef _H_JFS_DMAP
#define _H_JFS_DMAP
#include "jfs_txnmgr.h"
#define BMAPVERSION 1 /* version number */
#define TREESIZE (256+64+16+4+1) /* size of a dmap tree */
#define LEAFIND (64+16+4+1) /* index of 1st leaf of a dmap tree */
#define LPERDMAP 256 /* num leaves per dmap tree */
#define L2LPERDMAP 8 /* l2 number of leaves per dmap tree */
#define DBWORD 32 /* # of blks covered by a map word */
#define L2DBWORD 5 /* l2 # of blks covered by a mword */
#define BUDMIN L2DBWORD /* max free string in a map word */
#define BPERDMAP (LPERDMAP * DBWORD) /* num of blks per dmap */
#define L2BPERDMAP 13 /* l2 num of blks per dmap */
#define CTLTREESIZE (1024+256+64+16+4+1) /* size of a dmapctl tree */
#define CTLLEAFIND (256+64+16+4+1) /* idx of 1st leaf of a dmapctl tree */
#define LPERCTL 1024 /* num of leaves per dmapctl tree */
#define L2LPERCTL 10 /* l2 num of leaves per dmapctl tree */
#define ROOT 0 /* index of the root of a tree */
#define NOFREE ((s8) -1) /* no blocks free */
#define MAXAG 128 /* max number of allocation groups */
#define L2MAXAG 7 /* l2 max num of AG */
#define L2MINAGSZ 25 /* l2 of minimum AG size in bytes */
#define BMAPBLKNO 0 /* lblkno of bmap within the map */
/*
* maximum l2 number of disk blocks at the various dmapctl levels.
*/
#define L2MAXL0SIZE (L2BPERDMAP + 1 * L2LPERCTL)
#define L2MAXL1SIZE (L2BPERDMAP + 2 * L2LPERCTL)
#define L2MAXL2SIZE (L2BPERDMAP + 3 * L2LPERCTL)
/*
* maximum number of disk blocks at the various dmapctl levels.
*/
#define MAXL0SIZE ((s64)1 << L2MAXL0SIZE)
#define MAXL1SIZE ((s64)1 << L2MAXL1SIZE)
#define MAXL2SIZE ((s64)1 << L2MAXL2SIZE)
#define MAXMAPSIZE MAXL2SIZE /* maximum aggregate map size */
/*
* determine the maximum free string for four (lower level) nodes
* of the tree.
*/
static inline signed char TREEMAX(signed char *cp)
{
signed char tmp1, tmp2;
tmp1 = max(*(cp+2), *(cp+3));
tmp2 = max(*(cp), *(cp+1));
return max(tmp1, tmp2);
}
/*
* convert disk block number to the logical block number of the dmap
* describing the disk block. s is the log2(number of logical blocks per page)
*
* The calculation figures out how many logical pages are in front of the dmap.
* - the number of dmaps preceding it
* - the number of L0 pages preceding its L0 page
* - the number of L1 pages preceding its L1 page
* - 3 is added to account for the L2, L1, and L0 page for this dmap
* - 1 is added to account for the control page of the map.
*/
#define BLKTODMAP(b,s) \
((((b) >> 13) + ((b) >> 23) + ((b) >> 33) + 3 + 1) << (s))
/*
* convert disk block number to the logical block number of the LEVEL 0
* dmapctl describing the disk block. s is the log2(number of logical blocks
* per page)
*
* The calculation figures out how many logical pages are in front of the L0.
* - the number of dmap pages preceding it
* - the number of L0 pages preceding it
* - the number of L1 pages preceding its L1 page
* - 2 is added to account for the L2, and L1 page for this L0
* - 1 is added to account for the control page of the map.
*/
#define BLKTOL0(b,s) \
(((((b) >> 23) << 10) + ((b) >> 23) + ((b) >> 33) + 2 + 1) << (s))
/*
* convert disk block number to the logical block number of the LEVEL 1
* dmapctl describing the disk block. s is the log2(number of logical blocks
* per page)
*
* The calculation figures out how many logical pages are in front of the L1.
* - the number of dmap pages preceding it
* - the number of L0 pages preceding it
* - the number of L1 pages preceding it
* - 1 is added to account for the L2 page
* - 1 is added to account for the control page of the map.
*/
#define BLKTOL1(b,s) \
(((((b) >> 33) << 20) + (((b) >> 33) << 10) + ((b) >> 33) + 1 + 1) << (s))
/*
* convert disk block number to the logical block number of the dmapctl
* at the specified level which describes the disk block.
*/
#define BLKTOCTL(b,s,l) \
(((l) == 2) ? 1 : ((l) == 1) ? BLKTOL1((b),(s)) : BLKTOL0((b),(s)))
/*
* convert aggregate map size to the zero origin dmapctl level of the
* top dmapctl.
*/
#define BMAPSZTOLEV(size) \
(((size) <= MAXL0SIZE) ? 0 : ((size) <= MAXL1SIZE) ? 1 : 2)
/* convert disk block number to allocation group number.
*/
#define BLKTOAG(b,sbi) ((b) >> ((sbi)->bmap->db_agl2size))
/* convert allocation group number to starting disk block
* number.
*/
#define AGTOBLK(a,ip) \
((s64)(a) << (JFS_SBI((ip)->i_sb)->bmap->db_agl2size))
/*
* dmap summary tree
*
* dmaptree must be consistent with dmapctl.
*/
struct dmaptree {
__le32 nleafs; /* 4: number of tree leafs */
__le32 l2nleafs; /* 4: l2 number of tree leafs */
__le32 leafidx; /* 4: index of first tree leaf */
__le32 height; /* 4: height of the tree */
s8 budmin; /* 1: min l2 tree leaf value to combine */
s8 stree[TREESIZE]; /* TREESIZE: tree */
u8 pad[2]; /* 2: pad to word boundary */
}; /* - 360 - */
/*
* dmap page per 8K blocks bitmap
*/
struct dmap {
__le32 nblocks; /* 4: num blks covered by this dmap */
__le32 nfree; /* 4: num of free blks in this dmap */
__le64 start; /* 8: starting blkno for this dmap */
struct dmaptree tree; /* 360: dmap tree */
u8 pad[1672]; /* 1672: pad to 2048 bytes */
__le32 wmap[LPERDMAP]; /* 1024: bits of the working map */
__le32 pmap[LPERDMAP]; /* 1024: bits of the persistent map */
}; /* - 4096 - */
/*
* disk map control page per level.
*
* dmapctl must be consistent with dmaptree.
*/
struct dmapctl {
__le32 nleafs; /* 4: number of tree leafs */
__le32 l2nleafs; /* 4: l2 number of tree leafs */
__le32 leafidx; /* 4: index of the first tree leaf */
__le32 height; /* 4: height of tree */
s8 budmin; /* 1: minimum l2 tree leaf value */
s8 stree[CTLTREESIZE]; /* CTLTREESIZE: dmapctl tree */
u8 pad[2714]; /* 2714: pad to 4096 */
}; /* - 4096 - */
/*
* common definition for dmaptree within dmap and dmapctl
*/
typedef union dmtree {
struct dmaptree t1;
struct dmapctl t2;
} dmtree_t;
/* macros for accessing fields within dmtree */
#define dmt_nleafs t1.nleafs
#define dmt_l2nleafs t1.l2nleafs
#define dmt_leafidx t1.leafidx
#define dmt_height t1.height
#define dmt_budmin t1.budmin
#define dmt_stree t2.stree
/*
* on-disk aggregate disk allocation map descriptor.
*/
struct dbmap_disk {
__le64 dn_mapsize; /* 8: number of blocks in aggregate */
__le64 dn_nfree; /* 8: num free blks in aggregate map */
__le32 dn_l2nbperpage; /* 4: number of blks per page */
__le32 dn_numag; /* 4: total number of ags */
__le32 dn_maxlevel; /* 4: number of active ags */
__le32 dn_maxag; /* 4: max active alloc group number */
__le32 dn_agpref; /* 4: preferred alloc group (hint) */
__le32 dn_aglevel; /* 4: dmapctl level holding the AG */
__le32 dn_agheight; /* 4: height in dmapctl of the AG */
__le32 dn_agwidth; /* 4: width in dmapctl of the AG */
__le32 dn_agstart; /* 4: start tree index at AG height */
__le32 dn_agl2size; /* 4: l2 num of blks per alloc group */
__le64 dn_agfree[MAXAG];/* 8*MAXAG: per AG free count */
__le64 dn_agsize; /* 8: num of blks per alloc group */
s8 dn_maxfreebud; /* 1: max free buddy system */
u8 pad[3007]; /* 3007: pad to 4096 */
}; /* - 4096 - */
struct dbmap {
s64 dn_mapsize; /* number of blocks in aggregate */
s64 dn_nfree; /* num free blks in aggregate map */
int dn_l2nbperpage; /* number of blks per page */
int dn_numag; /* total number of ags */
int dn_maxlevel; /* number of active ags */
int dn_maxag; /* max active alloc group number */
int dn_agpref; /* preferred alloc group (hint) */
int dn_aglevel; /* dmapctl level holding the AG */
int dn_agheight; /* height in dmapctl of the AG */
int dn_agwidth; /* width in dmapctl of the AG */
int dn_agstart; /* start tree index at AG height */
int dn_agl2size; /* l2 num of blks per alloc group */
s64 dn_agfree[MAXAG]; /* per AG free count */
s64 dn_agsize; /* num of blks per alloc group */
signed char dn_maxfreebud; /* max free buddy system */
}; /* - 4096 - */
/*
* in-memory aggregate disk allocation map descriptor.
*/
struct bmap {
struct dbmap db_bmap; /* on-disk aggregate map descriptor */
struct inode *db_ipbmap; /* ptr to aggregate map incore inode */
struct mutex db_bmaplock; /* aggregate map lock */
atomic_t db_active[MAXAG]; /* count of active, open files in AG */
u32 *db_DBmap;
};
/* macros for accessing fields within in-memory aggregate map descriptor */
#define db_mapsize db_bmap.dn_mapsize
#define db_nfree db_bmap.dn_nfree
#define db_agfree db_bmap.dn_agfree
#define db_agsize db_bmap.dn_agsize
#define db_agl2size db_bmap.dn_agl2size
#define db_agwidth db_bmap.dn_agwidth
#define db_agheight db_bmap.dn_agheight
#define db_agstart db_bmap.dn_agstart
#define db_numag db_bmap.dn_numag
#define db_maxlevel db_bmap.dn_maxlevel
#define db_aglevel db_bmap.dn_aglevel
#define db_agpref db_bmap.dn_agpref
#define db_maxag db_bmap.dn_maxag
#define db_maxfreebud db_bmap.dn_maxfreebud
#define db_l2nbperpage db_bmap.dn_l2nbperpage
/*
* macros for various conversions needed by the allocators.
* blkstol2(), cntlz(), and cnttz() are operating system dependent functions.
*/
/* convert number of blocks to log2 number of blocks, rounding up to
* the next log2 value if blocks is not a l2 multiple.
*/
#define BLKSTOL2(d) (blkstol2(d))
/* convert number of leafs to log2 leaf value */
#define NLSTOL2BSZ(n) (31 - cntlz((n)) + BUDMIN)
/* convert leaf index to log2 leaf value */
#define LITOL2BSZ(n,m,b) ((((n) == 0) ? (m) : cnttz((n))) + (b))
/* convert a block number to a dmap control leaf index */
#define BLKTOCTLLEAF(b,m) \
(((b) & (((s64)1 << ((m) + L2LPERCTL)) - 1)) >> (m))
/* convert log2 leaf value to buddy size */
#define BUDSIZE(s,m) (1 << ((s) - (m)))
/*
* external references.
*/
extern int dbMount(struct inode *ipbmap);
extern int dbUnmount(struct inode *ipbmap, int mounterror);
extern int dbFree(struct inode *ipbmap, s64 blkno, s64 nblocks);
extern int dbUpdatePMap(struct inode *ipbmap,
int free, s64 blkno, s64 nblocks, struct tblock * tblk);
extern int dbNextAG(struct inode *ipbmap);
extern int dbAlloc(struct inode *ipbmap, s64 hint, s64 nblocks, s64 * results);
extern int dbReAlloc(struct inode *ipbmap,
s64 blkno, s64 nblocks, s64 addnblocks, s64 * results);
extern int dbSync(struct inode *ipbmap);
extern int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks);
extern int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks);
extern void dbFinalizeBmap(struct inode *ipbmap);
extern s64 dbMapFileSizeToMapSize(struct inode *ipbmap);
extern s64 dbDiscardAG(struct inode *ip, int agno, s64 minlen);
#endif /* _H_JFS_DMAP */
]
|
| 43/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 13482
output: 77
thoughts: 1387
Thoughts: **Analyzing the `dbFindLeaf` Function and Potential Out-of-Bounds Accesses**
Okay, so I'm looking at this `dbFindLeaf` function and immediately see some potential issues with how it handles the tree structure and array indexing. The core of the problem seems to be the differing sizes of the `stree` array within the `dmaptree` and `dmapctl` structs. The definitions of `TREESIZE` and `CTLTREESIZE` are key here. I see that `dmt_stree` is a macro that always resolves to `t2.stree`, where `t2` is a `dmapctl` struct. The `dmapctl` has `s8 stree[CTLTREESIZE]` and `dmaptree` has `s8 stree[TREESIZE]`. The union `dmtree_t` allows treating the same memory as either a `dmaptree` (`t1`) or a `dmapctl` (`t2`).
The conditional logic based on `is_ctl` determines whether we're working with the `dmaptree` (`t1`) or `dmapctl` (`t2`) parts of the union. If `is_ctl` is false, it's `t1` (dmaptree) and we are meant to be accessing `stree` of size `TREESIZE`. If it's true, we're dealing with `t2` (dmapctl) and access `stree` of size `CTLTREESIZE`.
The function uses `tp->dmt_stree` which, due to the macro, translates to `tp->t2.stree`. This seems fine since the initial layout of the struct is similar for both. Both struct types contain the `stree` array, and they overlap up to `TREESIZE`. So, it's valid as long as the index doesn't go beyond `TREESIZE` when treating it as `t1`. However, if `is_ctl` is false, `max_size` is set to `TREESIZE` which is smaller than `CTLTREESIZE`.
Now, the critical part: the loop check. Line 2974: `if (x + n > max_size)`. Here's where it gets interesting. If `is_ctl` is false, and the `x + n` reaches `TREESIZE`, this condition fails to trigger, because the check is `>`. Therefore, it accesses `t2.stree` at index `TREESIZE`. For `dmaptree` (`t1`), this goes past the valid index, as the `stree` array is only `TREESIZE` in size, and it's followed by `pad[2]`. This means that accessing `stree[TREESIZE]` is accessing `pad[0]`.
If `is_ctl` is true, then `max_size` equals `CTLTREESIZE`. The same loop condition then checks if `x + n` reaches `CTLTREESIZE`. If `x + n` *is equal to* `CTLTREESIZE`, the index is out-of-bounds, since `t2.stree` can only hold indexes up to `CTLTREESIZE -1`. This is confirmed by the UBSAN report, mentioning that index 1365 (which is `CTLTREESIZE`) is out of range for the `s8[1365]` array.
Therefore, the issue is with the strict inequality used in the loop condition, so the fix is evident: Change the `>` to `>=`. This way, we're catching the out-of-bounds access for both the `dmaptree` and `dmapctl` cases. I'm going to change the line in `dbFindLeaf` to: `if (x + n >= max_size)` to prevent this out-of-bounds read and return an error code, which makes the code safer. I'll just apply the change and move on.
|
| 44/4 |
2026/01/28 17:26 |
tool |
codeeditor |
0m
Args: map[CurrentCode: if (x + n > max_size)
return -ENOSPC; NewCode: if (x + n >= max_size)
return -ENOSPC; SourceFile:fs/jfs/jfs_dmap.c]
Results:
|
| 45/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 15836
output: 45
thoughts: 143
Thoughts: **Verification and Expansion of the Fix**
Okay, I've applied the initial fix, that's done. Now, a crucial next step is to ensure this doesn't pop up again in another area of the codebase. Given the nature of the issue, and my understanding of the code's architecture, I need to methodically check for similar instances. It's a risk mitigation strategy.
The stack trace is pointing towards `dbFindCtl` which then calls `dbFindLeaf`. I see both of these functions mentioned so I should really check `dbFindCtl` as well, since that's another function related to the same file. I should take a close look at `dbFindCtl` now; it seems like a likely candidate for containing related, similar logic. This is where I'll expand the initial fix.
|
| 46/4 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeLines:true Name:dbFindCtl]
Results: map[SourceCode:1653: /*
1654: * NAME: dbFindCtl()
1655: *
1656: * FUNCTION: starting at a specified dmap control page level and block
1657: * number, search down the dmap control levels for a range of
1658: * contiguous free blocks large enough to satisfy an allocation
1659: * request for the specified number of free blocks.
1660: *
1661: * if sufficient contiguous free blocks are found, this routine
1662: * returns the starting block number within a dmap page that
1663: * contains or starts a range of contiqious free blocks that
1664: * is sufficient in size.
1665: *
1666: * PARAMETERS:
1667: * bmp - pointer to bmap descriptor
1668: * level - starting dmap control page level.
1669: * l2nb - log2 number of contiguous free blocks desired.
1670: * *blkno - on entry, starting block number for conducting the search.
1671: * on successful return, the first block within a dmap page
1672: * that contains or starts a range of contiguous free blocks.
1673: *
1674: * RETURN VALUES:
1675: * 0 - success
1676: * -ENOSPC - insufficient disk resources
1677: * -EIO - i/o error
1678: *
1679: * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1680: */
1681: static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno)
1682: {
1683: int rc, leafidx, lev;
1684: s64 b, lblkno;
1685: struct dmapctl *dcp;
1686: int budmin;
1687: struct metapage *mp;
1688:
1689: /* starting at the specified dmap control page level and block
1690: * number, search down the dmap control levels for the starting
1691: * block number of a dmap page that contains or starts off
1692: * sufficient free blocks.
1693: */
1694: for (lev = level, b = *blkno; lev >= 0; lev--) {
1695: /* get the buffer of the dmap control page for the block
1696: * number and level (i.e. L0, L1, L2).
1697: */
1698: lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev);
1699: mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1700: if (mp == NULL)
1701: return -EIO;
1702: dcp = (struct dmapctl *) mp->data;
1703: budmin = dcp->budmin;
1704:
1705: if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
1706: jfs_error(bmp->db_ipbmap->i_sb,
1707: "Corrupt dmapctl page\n");
1708: release_metapage(mp);
1709: return -EIO;
1710: }
1711:
1712: /* search the tree within the dmap control page for
1713: * sufficient free space. if sufficient free space is found,
1714: * dbFindLeaf() returns the index of the leaf at which
1715: * free space was found.
1716: */
1717: rc = dbFindLeaf((dmtree_t *) dcp, l2nb, &leafidx, true);
1718:
1719: /* release the buffer.
1720: */
1721: release_metapage(mp);
1722:
1723: /* space found ?
1724: */
1725: if (rc) {
1726: if (lev != level) {
1727: jfs_error(bmp->db_ipbmap->i_sb,
1728: "dmap inconsistent\n");
1729: return -EIO;
1730: }
1731: return -ENOSPC;
1732: }
1733:
1734: /* adjust the block number to reflect the location within
1735: * the dmap control page (i.e. the leaf) at which free
1736: * space was found.
1737: */
1738: b += (((s64) leafidx) << budmin);
1739:
1740: /* we stop the search at this dmap control page level if
1741: * the number of blocks required is greater than or equal
1742: * to the maximum number of blocks described at the next
1743: * (lower) level.
1744: */
1745: if (l2nb >= budmin)
1746: break;
1747: }
1748:
1749: *blkno = b;
1750: return (0);
1751: }
SourceFile:fs/jfs/jfs_dmap.c]
|
| 47/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 17742
output: 21
thoughts: 86
Thoughts: Okay, here's my understanding, considering I'm trying to optimize this:
**Analyzing the `dbFindCtl` and `dbFindLeaf` Interaction**
Right, so `dbFindCtl` β looking at line 1717 β is basically just a wrapper around `dbFindLeaf`. And it's passing `true` for `is_ctl`, which I already suspected. That's good; it simplifies things. The traversal logic, the meat of the operation, is all handled within `dbFindLeaf`. This means whatever fix was implemented in `dbFindLeaf` *should* be sufficient to address the problem along this call path, specifically when `dbFindCtl` is involved.
However, I need to confirm that that's the *only* call path to `dbFindLeaf`. I need to be sure there aren't any other usages of `dbFindLeaf` with potential similar vulnerabilities, otherwise, the fix could be incomplete. Time for a code search for references to `dbFindLeaf`. Let's see what else calls it.
|
| 48/4 |
2026/01/28 17:26 |
tool |
codesearch-find-references |
0m
Args:
Results: map[References:[map[ReferenceKind:calls ReferencingEntityKind:function ReferencingEntityName:dbAllocDmapLev SourceFile:fs/jfs/jfs_dmap.c SourceLine:1969] map[ReferenceKind:calls ReferencingEntityKind:function ReferencingEntityName:dbFindCtl SourceFile:fs/jfs/jfs_dmap.c SourceLine:1717]] TruncatedOutput:false]
|
| 49/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 18205
output: 46
thoughts: 22
Thoughts: Okay, here's my interpretation of those thoughts, crafted with the understanding that I'm speaking to a fellow expert:
**Tracing a Function's Call Chain**
Right, so this function, whatever it is, is also being called from `dbAllocDmapLev`. I need to understand the relationship between these two areas. Let me go back and investigate the usage within `dbAllocDmapLev` to gain further context and a better understanding of how the calling function interacts with this specific component. Understanding this will hopefully illuminate why they are tied together and what kind of dependencies are present. It's a key piece of the puzzle.
|
| 50/4 |
2026/01/28 17:26 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeLines:true Name:dbAllocDmapLev]
Results: map[SourceCode:1929: /*
1930: * NAME: dbAllocDmapLev()
1931: *
1932: * FUNCTION: attempt to allocate a specified number of contiguous blocks
1933: * from a specified dmap.
1934: *
1935: * this routine checks if the contiguous blocks are available.
1936: * if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1937: * returned.
1938: *
1939: * PARAMETERS:
1940: * mp - pointer to bmap descriptor
1941: * dp - pointer to dmap to attempt to allocate blocks from.
1942: * l2nb - log2 number of contiguous block desired.
1943: * nblocks - actual number of contiguous block desired.
1944: * results - on successful return, set to the starting block number
1945: * of the newly allocated range.
1946: *
1947: * RETURN VALUES:
1948: * 0 - success
1949: * -ENOSPC - insufficient disk resources
1950: * -EIO - i/o error
1951: *
1952: * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or
1953: * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
1954: */
1955: static int
1956: dbAllocDmapLev(struct bmap * bmp,
1957: struct dmap * dp, int nblocks, int l2nb, s64 * results)
1958: {
1959: s64 blkno;
1960: int leafidx, rc;
1961:
1962: /* can't be more than a dmaps worth of blocks */
1963: assert(l2nb <= L2BPERDMAP);
1964:
1965: /* search the tree within the dmap page for sufficient
1966: * free space. if sufficient free space is found, dbFindLeaf()
1967: * returns the index of the leaf at which free space was found.
1968: */
1969: if (dbFindLeaf((dmtree_t *) &dp->tree, l2nb, &leafidx, false))
1970: return -ENOSPC;
1971:
1972: if (leafidx < 0)
1973: return -EIO;
1974:
1975: /* determine the block number within the file system corresponding
1976: * to the leaf at which free space was found.
1977: */
1978: blkno = le64_to_cpu(dp->start) + (leafidx << L2DBWORD);
1979:
1980: /* if not all bits of the dmap word are free, get the starting
1981: * bit number within the dmap word of the required string of free
1982: * bits and adjust the block number with this value.
1983: */
1984: if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN)
1985: blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb);
1986:
1987: /* allocate the blocks */
1988: if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0)
1989: *results = blkno;
1990:
1991: return (rc);
1992: }
SourceFile:fs/jfs/jfs_dmap.c]
|
| 51/4 |
2026/01/28 17:26 |
llm |
patch-generator |
0m
Model:
Tokens:
input: 19469
output: 538
thoughts: 1955
Thoughts: **Analysis of the JFS dmap Out-of-Bounds Access Bug and Fix**
Okay, here's the breakdown of this bug and the crucial fix. I've been looking at the `dbFindLeaf` function in `fs/jfs/jfs_dmap.c`, and the core issue is an out-of-bounds read in the `dmt_stree` array within a `dmaptree` structure. The crash is triggered when `dbFindLeaf` is called with a corrupted filesystem image, specifically when the `dmt_height` metadata field indicates a tree height larger than what's valid for the given tree size. This causes the internal loop in `dbFindLeaf` to attempt to access memory beyond the bounds of the `stree` array.
Let's clarify what's going on. The call to `dbFindLeaf` I examined was using `false` for `is_ctl`, and in this case, `max_size` is equivalent to `TREESIZE`, which is the size of the `stree` array. The code iterates through the tree structure based on the tree height and an index `ti` which is manipulated within a loop. The problematic code is:
```c
for (x = ti, n = 0; n < 4; n++) {
if (x + n >= max_size) //This is the key part.
return -ENOSPC;
if (l2nb <= tp->dmt_stree[x + n])
break;
}
```
The original code used a strict `>` (greater than) comparison: `if (x + n > max_size)`. This meant that an access to `stree[max_size]` was *not* prevented. Since the `stree` array has a size of `TREESIZE`, valid indices are 0 to `TREESIZE - 1`. The access to `stree[TREESIZE]` is an out-of-bounds access that results in padding bytes being accessed in the `dmaptree` struct: the array `pad[2]`. While accessing padding might not immediately crash the system (as padding is allocated), it's logically an out-of-bounds read and can potentially lead to unpredictable behavior or security vulnerabilities.
The fix, which has already been applied, changes the comparison to `if (x + n >= max_size)`. This ensures that access to `stree[TREESIZE]` is also prevented. This corrected code is what I observed in the patch:
```c
if (x + n >= max_size)
return -ENOSPC;
```
So, the new code guarantees that the index `x + n` will *never* be equal to or greater than `max_size`.
This out-of-bounds read occurs because the iteration count, determined by `dmt_height`, can be larger than what's appropriate for the tree's actual size. The check within `dbFindLeaf` is designed to be the safety net, the defense against the corruption. The change from `>` to `>=` makes the bounds checking correct and robust against these kinds of filesystem corruptions.
In summary, the bug involved an out-of-bounds read, and the fix ensures it now checks correctly:
1. **The Fix:** The code has been changed in `fs/jfs/jfs_dmap.c` from `if (x + n > max_size)` to `if (x + n >= max_size)` inside the loop within `dbFindLeaf`.
2. **Why it Works:** This prevents an out-of-bounds read by ensuring that any attempt to access the array `tp->dmt_stree` with an index equal to `max_size` (or higher) results in a return with `-ENOSPC` instead. This prevents accessing the pad.
3. **Context:** This situation is triggered when the filesystem metadata is corrupted (e.g., in a Syzkaller test case), and the reported tree height is greater than the valid height for the tree structure. This causes the loop's calculations to go past the end of the `stree` array, and the corrected bounds check prevents it.
|
| 52/3 |
2026/01/28 17:26 |
action |
test-patch |
9m
Results: map[PatchDiff:diff --git a/fs/jfs/jfs_dmap.c b/fs/jfs/jfs_dmap.c
index cdfa699cd..18a7dc58f 100644
--- a/fs/jfs/jfs_dmap.c
+++ b/fs/jfs/jfs_dmap.c
@@ -2971,7 +2971,7 @@ static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
/* sufficient free space found. move to the next
* level (or quit if this is the last level).
*/
- if (x + n > max_size)
+ if (x + n >= max_size)
return -ENOSPC;
if (l2nb <= tp->dmt_stree[x + n])
break;
TestError:]
|
| 53/1 |
2026/01/28 17:36 |
action |
get-maintainers |
0m
Results: map[Recipients:[map[Email:jfs-discussion@lists.sourceforge.net Name: To:true] map[Email:linux-kernel@vger.kernel.org Name: To:false] map[Email:shaggy@kernel.org Name:Dave Kleikamp To:true]]]
|
| 54/1 |
2026/01/28 17:36 |
agent |
description-generator |
0m
Model:
Instruction:
You are an experienced Linux kernel developer tasked with writing a commit description for
a kernel bug fixing commit. The description should start with a one-line summary,
and then include description of the bug being fixed, and how it's fixed by the provided patch.
Your final reply should contain only the text of the commit description.
Phrase the one-line summary so that it is not longer than 72 characters.
The rest of the description must be word-wrapped at 72 characters.
Prefer calling several tools at the same time to save round-trips.
Prompt:
The crash that corresponds to the bug is:
------------[ cut here ]------------
UBSAN: array-index-out-of-bounds in /usr/local/google/home/dvyukov/syzkaller/agent/workdir/cache/src/5452af61ab2e1f5601403fe379188fc9d8a831af/fs/jfs/jfs_dmap.c:2976:16
index 1365 is out of range for type 's8[1365]' (aka 'signed char[1365]')
CPU: 0 UID: 0 PID: 6426 Comm: syz-executor354 Not tainted syzkaller #1 PREEMPT_{RT,(full)}
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014
Call Trace:
<TASK>
__dump_stack lib/dump_stack.c:94 [inline]
dump_stack_lvl+0x10e/0x190 lib/dump_stack.c:120
ubsan_epilogue lib/ubsan.c:233 [inline]
__ubsan_handle_out_of_bounds+0x115/0x140 lib/ubsan.c:455
dbFindLeaf+0x308/0x520 fs/jfs/jfs_dmap.c:2976
dbFindCtl+0x267/0x520 fs/jfs/jfs_dmap.c:1717
dbAllocAny fs/jfs/jfs_dmap.c:1527 [inline]
dbAlloc+0x5fd/0xba0 fs/jfs/jfs_dmap.c:878
diNewIAG fs/jfs/jfs_imap.c:2510 [inline]
diAllocExt fs/jfs/jfs_imap.c:1905 [inline]
diAllocAG+0xcf0/0x1db0 fs/jfs/jfs_imap.c:1669
diAlloc+0x1d4/0x1670 fs/jfs/jfs_imap.c:1590
ialloc+0x8c/0x8f0 fs/jfs/jfs_inode.c:56
jfs_mkdir+0x193/0xa70 fs/jfs/namei.c:225
vfs_mkdir+0x530/0x5d0 fs/namei.c:5139
do_mkdirat+0x27a/0x4b0 fs/namei.c:5173
__do_sys_mkdir fs/namei.c:5200 [inline]
__se_sys_mkdir fs/namei.c:5198 [inline]
__x64_sys_mkdir+0x6c/0x80 fs/namei.c:5198
do_syscall_x64 arch/x86/entry/syscall_64.c:63 [inline]
do_syscall_64+0xe8/0xf80 arch/x86/entry/syscall_64.c:94
entry_SYSCALL_64_after_hwframe+0x77/0x7f
RIP: 0033:0x7f31a4a1c897
Code: 1f 40 00 48 89 f2 b9 00 01 00 00 48 89 fe bf 9c ff ff ff e9 7b 37 03 00 66 2e 0f 1f 84 00 00 00 00 00 90 b8 53 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 01 c3 48 c7 c2 d0 ff ff ff f7 d8 64 89 02 b8
RSP: 002b:00007f31a49be038 EFLAGS: 00000246 ORIG_RAX: 0000000000000053
RAX: ffffffffffffffda RBX: 0000200000000200 RCX: 00007f31a4a1c897
RDX: 0000000002b1247d RSI: 00000000000001ff RDI: 00002000000002c0
RBP: 0000000000000000 R08: 00000000000000fc R09: 0000000000000000
R10: 0000000000000008 R11: 0000000000000246 R12: 00002000000002c0
R13: 00007f31a49be0d0 R14: 0000000000000000 R15: 0000000000000000
</TASK>
---[ end trace ]---
The explanation of the root cause of the bug is:
The root cause of the crash is an off-by-one error in the bounds check within the `dbFindLeaf` function in `fs/jfs/jfs_dmap.c`.
The function traverses a dmap tree to find a leaf with sufficient free space. The loop calculates the index of the child nodes at the next level using `ti` (and `x` inside the loop):
```c
ti = ((ti + n) << 2) + 1
```
And then it iterates `n` from 0 to 3 to check the 4 children. The code checks if the calculated index `x + n` is within the bounds of the tree array `tp->dmt_stree` (which corresponds to `struct dmapctl::stree` of size 1365 when `is_ctl` is true).
The current bounds check is:
```c
2974: if (x + n > max_size)
2975: return -ENOSPC;
```
When `x + n` is equal to `max_size` (1365), the condition `1365 > 1365` is false, so the check passes. The code then proceeds to access the array:
```c
2976: if (l2nb <= tp->dmt_stree[x + n])
```
Accessing index 1365 of an array of size 1365 is an out-of-bounds access (valid indices are 0 to 1364).
This situation occurs when the filesystem image is corrupted (as in the Syzkaller test case), and the tree height (`dmt_height`) specified in the on-disk metadata is larger than the valid height for the tree size (e.g., > 5 for `dmapctl`), causing the loop to iterate deeper and calculate indices beyond the end of the array.
**Fix**
Change the bounds check to use `>=` instead of `>` to correctly handle the case where the index equals the array size.
```c
--- a/fs/jfs/jfs_dmap.c
+++ b/fs/jfs/jfs_dmap.c
@@ -2974,7 +2974,7 @@ static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
/* sufficient free space found. move to the next
* level (or quit if this is the last level).
*/
- if (x + n > max_size)
+ if (x + n >= max_size)
return -ENOSPC;
if (l2nb <= tp->dmt_stree[x + n])
break;
```
The diff of the bug fix is:
diff --git a/fs/jfs/jfs_dmap.c b/fs/jfs/jfs_dmap.c
index cdfa699cd..18a7dc58f 100644
--- a/fs/jfs/jfs_dmap.c
+++ b/fs/jfs/jfs_dmap.c
@@ -2971,7 +2971,7 @@ static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
/* sufficient free space found. move to the next
* level (or quit if this is the last level).
*/
- if (x + n > max_size)
+ if (x + n >= max_size)
return -ENOSPC;
if (l2nb <= tp->dmt_stree[x + n])
break;
Additional description of the patch:
The bug is an array-index-out-of-bounds access in the `dbFindLeaf` function in `fs/jfs/jfs_dmap.c`.
This function traverses a dmap tree to find a leaf with sufficient free space. It calculates the index of the child nodes at the next level using `ti` (assigned to `x`). The loop iterates `n` from 0 to 3 to check up to 4 children.
The code checks if the calculated index `x + n` is within the bounds of the tree array `tp->dmt_stree`. The size of this array is `CTLTREESIZE` (1365) when `is_ctl` is true, or `TREESIZE` (341) when `is_ctl` is false.
The indices of an array of size `N` range from `0` to `N-1`.
The bounds check was:
```c
if (x + n > max_size)
return -ENOSPC;
```
When `x + n` equals `max_size`, the condition is false, and the code proceeds to access `tp->dmt_stree[x + n]`, which is `tp->dmt_stree[max_size]`. This is an out-of-bounds access (off-by-one).
This happens typically when the filesystem metadata is corrupted, claiming a tree height larger than what fits in the fixed-size array (e.g., height > 5 for `dmapctl`), causing the traversal to go beyond the valid range.
I have applied the fix by changing the condition to `>=` to ensure we return `-ENOSPC` when the index reaches `max_size`.
```c
static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
{
...
for (x = ti, n = 0; n < 4; n++) {
/* sufficient free space found. move to the next
* level (or quit if this is the last level).
*/
if (x + n >= max_size)
return -ENOSPC;
if (l2nb <= tp->dmt_stree[x + n])
break;
}
...
}
```
The change was applied to `fs/jfs/jfs_dmap.c`.
Reply: jfs: fix array-index-out-of-bounds in dbFindLeaf
Syzkaller reported the following UBSAN failure:
UBSAN: array-index-out-of-bounds in fs/jfs/jfs_dmap.c:2976:16
index 1365 is out of range for type 's8[1365]' (aka 'signed char[1365]')
...
dbFindLeaf+0x308/0x520 fs/jfs/jfs_dmap.c:2976
dbFindCtl+0x267/0x520 fs/jfs/jfs_dmap.c:1717
The function dbFindLeaf() traverses the dmap tree to find a leaf with
sufficient free space. It uses `max_size` (which is 1365 for
CTLTREESIZE) to check bounds for the `dmt_stree` array. However, the
condition `if (x + n > max_size)` allows `x + n` to be equal to
`max_size`, which results in an out-of-bounds access since the valid
indices are 0 to `max_size - 1`.
Fix this by updating the condition to `if (x + n >= max_size)`.
|
| 55/2 |
2026/01/28 17:36 |
llm |
description-generator |
0m
Model:
Tokens:
input: 5252
output: 44
thoughts: 361
Thoughts: **Analyzing the JFS Kernel Bug Fix**
Okay, so I've got a crash report indicating an out-of-bounds access in the JFS file system, specifically within the `dbFindLeaf` function. The UBSAN complaint points to an index of 1365 exceeding the bounds of an `s8[1365]` array. It's happening in `fs/jfs/jfs_dmap.c` around line 2976. The root cause is pretty clear from the description: the current check `if (x + n > max_size)` allows `x + n` to *equal* `max_size`, which leads to accessing `tp->dmt_stree[x + n]`, effectively going out of bounds when `x + n` is the maximum valid index. So, it looks like an off-by-one error. The fix? Simple β change that `>` to a `>=`.
Before I craft the commit message, I need to verify everything, especially the variable names and the exact code context. I'll fire up the tools and take a look at `fs/jfs/jfs_dmap.c`, focusing on the area around line 2976, and confirm the `dbFindLeaf` function's location.
First, I'll read the file directly. I expect to find `dbFindLeaf` within `fs/jfs/jfs_dmap.c`, and the report suggests I'll find the issue around line 2976.
Once I've got a confirmed understanding of the code, I'll formulate a commit message. A concise summary like "jfs: fix array-index-out-of-bounds in dbFindLeaf" seems right. The description will have to clearly articulate the nature of the off-by-one error, referencing the faulty conditional and the correction.
Now, let's double-check the code.
|
| 56/2 |
2026/01/28 17:36 |
tool |
codesearch-definition-source |
0m
Args: map[ContextFile:fs/jfs/jfs_dmap.c IncludeLines:true Name:dbFindLeaf]
Results: map[SourceCode:2924: /*
2925: * NAME: dbFindLeaf()
2926: *
2927: * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2928: * the index of a leaf describing the free blocks if
2929: * sufficient free blocks are found.
2930: *
2931: * the search starts at the top of the dmtree_t tree and
2932: * proceeds down the tree to the leftmost leaf with sufficient
2933: * free space.
2934: *
2935: * PARAMETERS:
2936: * tp - pointer to the tree to be searched.
2937: * l2nb - log2 number of free blocks to search for.
2938: * leafidx - return pointer to be set to the index of the leaf
2939: * describing at least l2nb free blocks if sufficient
2940: * free blocks are found.
2941: * is_ctl - determines if the tree is of type ctl
2942: *
2943: * RETURN VALUES:
2944: * 0 - success
2945: * -ENOSPC - insufficient free blocks.
2946: */
2947: static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl)
2948: {
2949: int ti, n = 0, k, x = 0;
2950: int max_size, max_idx;
2951:
2952: max_size = is_ctl ? CTLTREESIZE : TREESIZE;
2953: max_idx = is_ctl ? LPERCTL : LPERDMAP;
2954:
2955: /* first check the root of the tree to see if there is
2956: * sufficient free space.
2957: */
2958: if (l2nb > tp->dmt_stree[ROOT])
2959: return -ENOSPC;
2960:
2961: /* sufficient free space available. now search down the tree
2962: * starting at the next level for the leftmost leaf that
2963: * describes sufficient free space.
2964: */
2965: for (k = le32_to_cpu(tp->dmt_height), ti = 1;
2966: k > 0; k--, ti = ((ti + n) << 2) + 1) {
2967: /* search the four nodes at this level, starting from
2968: * the left.
2969: */
2970: for (x = ti, n = 0; n < 4; n++) {
2971: /* sufficient free space found. move to the next
2972: * level (or quit if this is the last level).
2973: */
2974: if (x + n > max_size)
2975: return -ENOSPC;
2976: if (l2nb <= tp->dmt_stree[x + n])
2977: break;
2978: }
2979:
2980: /* better have found something since the higher
2981: * levels of the tree said it was here.
2982: */
2983: assert(n < 4);
2984: }
2985: if (le32_to_cpu(tp->dmt_leafidx) >= max_idx)
2986: return -ENOSPC;
2987:
2988: /* set the return to the leftmost leaf describing sufficient
2989: * free space.
2990: */
2991: *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx);
2992:
2993: return (0);
2994: }
SourceFile:fs/jfs/jfs_dmap.c]
|
| 57/2 |
2026/01/28 17:36 |
llm |
description-generator |
0m
Model:
Tokens:
input: 7204
output: 307
thoughts: 2433
Thoughts: **My Analysis of the Issue**
Okay, here's what I've figured out. The code is definitely showing an array-index-out-of-bounds problem, specifically in `dbFindLeaf`. Line 2974 shows the problem: `if (x + n > max_size)`. And on the next line `tp->dmt_stree[x + n]` is accessed, so `x + n` could be out of bounds. The crash report is clear: "index 1365 is out of range for type 's8[1365]'". `CTLTREESIZE` must be 1365, so when `x + n` reaches that value in the loop, the bounds check fails to prevent access to the invalid index. Valid indices are from 0 up to 1364.
The proposed fix is `if (x + n >= max_size)`, which is exactly what's needed. This will correctly handle the case where `x + n` equals `max_size` and prevent the OOB access. The crash report even specifies that the array is `s8`, which is `signed char`.
I've got the necessary information to write the commit message. The crucial part is the fix in the conditional, and the reasoning is sound.
The crash report confirms that `CTLTREESIZE` is 1365. This is important to note since `max_size` is calculated with a ternary: `max_size = is_ctl ? CTLTREESIZE : TREESIZE;`. Given the crash report, `is_ctl` is true, or has some value associated to the fact the array is of size 1365. I'll need to check the definitions of the `CTLTREESIZE` and `TREESIZE` macros to be 100% sure, but the logic stands regardless of the specific values.
I'm confident in the solution. Here's how I'll present it to conform to the user's requirements:
**Final Reply**
jfs: fix array-index-out-of-bounds in dbFindLeaf
Syzkaller reported the following UBSAN failure:
UBSAN: array-index-out-of-bounds in fs/jfs/jfs_dmap.c:2976:16
index 1365 is out of range for type 's8[1365]' (aka 'signed char[1365]')
...
dbFindLeaf+0x308/0x520 fs/jfs/jfs_dmap.c:2976
dbFindCtl+0x267/0x520 fs/jfs/jfs_dmap.c:1717
The function dbFindLeaf() traverses the dmap tree to find a leaf with
sufficient free space. It uses `max_size` (which is 1365 for
CTLTREESIZE) to check bounds for the `dmt_stree` array. However, the
condition `if (x + n > max_size)` allows `x + n` to be equal to
`max_size`, which results in an out-of-bounds access since the valid
indices are 0 to `max_size - 1`.
Fix this by updating the condition to `if (x + n >= max_size)`.
|