[bug report] f2fs: off by one in garbage collection functions

[bug report] f2fs: off by one in garbage collection functions

[Dan Carpenter]

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

Re: [bug report] f2fs: off by one in garbage collection functions

[Jaegeuk Kim]

[-- Attachment #1: Type: text/plain, Size: 1450 bytes --]

Hi,

2013-01-18 (금), 16:29 +0300, Dan Carpenter:
> 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.

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.

-- 
Jaegeuk Kim
Samsung

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]