f2fs: off by one in garbage collection functions
Subsystems (2)
Hello Jaegeuk Kim,
The patch 7bc0900347e0: "f2fs: add garbage collection functions" from Nov 2, 2012, has an off-by-one bug.
429 block_t start_bidx_of_node(unsigned int node_ofs)
430 {
431 unsigned int indirect_blks = 2 * NIDS_PER_BLOCK + 4;
432 unsigned int bidx;
433
434 if (node_ofs == 0)
435 return 0;
436
437 if (node_ofs <= 2) {
438 bidx = node_ofs - 1;
439 } else if (node_ofs <= indirect_blks) {
440 int dec = (node_ofs - 4) / (NIDS_PER_BLOCK + 1);If node_ofs == 3 here then (node_ofs - 4) is a very high positive number. We divide by 1019 and we get another still very high number but not so high that it is negative when cast as an int.
441 bidx = node_ofs - 2 - dec;
It means that bidx is much higher than intended here (4290752413).
I thought maybe there is an off by one somewhere. Perhaps the 4 should be a 3.
442 } else {
443 int dec = (node_ofs - indirect_blks - 3) / (NIDS_PER_BLOCK + 1);
444 bidx = node_ofs - 5 - dec;
445 }
446 return bidx * ADDRS_PER_BLOCK + ADDRS_PER_INODE;
447 }regards,
dan carpenter
Hi,
2013-01-18 (금), 16:29 +0300, Dan Carpenter:
Quoted 18 lines
Hello Jaegeuk Kim,
The patch
7bc0900347e0: "f2fs: add garbage collection functions" from Nov 2, 2012, has an off-by-one bug.429 block_t start_bidx_of_node(unsigned int node_ofs) 430 { 431 unsigned int indirect_blks = 2 * NIDS_PER_BLOCK + 4; 432 unsigned int bidx; 433 434 if (node_ofs == 0) 435 return 0; 436 437 if (node_ofs <= 2) { 438 bidx = node_ofs - 1; 439 } else if (node_ofs <= indirect_blks) { 440 int dec = (node_ofs - 4) / (NIDS_PER_BLOCK + 1);
Quoted 3 lines
If
node_ofs== 3 here then (node_ofs- 4) is a very high positive number. We divide by 1019 and we get another still very high number but not so high that it is negative when cast as an int.
If the node_ofs is equal to 3, then it's a run-time bug on its caller, gc_data_segment(), not here itself.
In gc_data_segment(),
1. check_dnode(&nofs);
2. start_bidx_of_node(nofs);
Here, it means that we don't care about indirect node pages whose node offsets are 3, 3+1018+1, (3+1018+1)+1018+1, and so on. (Ref. *Index Structure* in Document/filesystems/f2fs.txt) Instead, we just check direct node pages only.
But, anyway, I'd better write comments to make it clear. Thank you for reviewing.
Signature · 2 lines
Jaegeuk Kim Samsung
PATCH 1/1 f2fs: add comments of start_bidx_of_node
The caller of start_bidx_of_node() should give a proper node offsets which point only direct node blocks. Otherwise, it is a caller's bug. This patch adds comments to make it clear.
--- fs/f2fs/gc.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
fs/f2fs/gc.c +5 -1
@@ -424,7 +424,11 @@ next_step: }/* -* Calculate start block index that this node page contains +* Calculate start block index indicating the given node offset. +* Be careful, caller should give this node offset only indicating direct node +* blocks. If any node offsets, which point the other types of node blocks such +* as indirect or double indirect node blocks, are given, it must be a caller's +* bug. */ block_t start_bidx_of_node (unsigned int node_ofs) {
Signature · 1 line
1.8.0.1.250.gb7973fb