Ext2 vs UFS getlbns

[Bruce Evans]

On Fri, 11 Jun 2004, Brian Bergstrand wrote:

> On Jun 11, 2004, at 1:14 PM, Bruce Evans wrote:
>
> > On Fri, 11 Jun 2004, Brian Bergstrand wrote:
> >
> >> I just noticed something in ext2_getlbns() (ext2_bmap.c, v1.57) vs.
> >> ufs_getlbns() (ufs_bmap.c, v1.60)
> >>
> >> ...
> >>
> >> Notice that blockcnt is changed AFTER offset/metalbn in Ext2 and
> >> BEFORE
> >> those in UFS.
> >>
> >> Was this change in Ext2 done on purpose for some reason? It makes a
> >> difference in calculating in_off and metalbn for some block #'s.
> >
> > This is to fix overflow in the calculation of block numbers for triple
> > indirect blocks.  ffs used to do this, and ext2_getlbns() was a copy
> > ..
> >
> > This difference shouldn't affect in_off or metalbn for any reachable
> > block number (32 bit ones in ext2fs).  There is another variable
> > ...
>
> The reason that I originally asked, is because I'm seeing different
> offsets and metalbns for relatively small block #'s in the OS X port.
> The OS X code is derived from FreeBSD 5.x and ext2_getlbns() has not
> changed
>
> For instance, on a 1KB block FS (which therefore has 256 block entries
> per indirect block) I see the following with the original algo.:
>
> Write 21 bytes at offset 0:
> lbn = 0
> indir not set because this falls in the direct block range
>
> Write 21 bytes at offset 12288:
> lbn=12
> {{
>      in_lbn = -12,
>      in_off = 0,
>      in_exists = 0
>    }, {
>      in_lbn = -12,
>      in_off = 0,
>      in_exists = 0
>    }, {
> ....
>
> Write 21 bytes at offset 4194304
> lbn=4096
> {{
>      in_lbn = -269,
>      in_off = 1,
>      in_exists = 0
>    }, {
>      in_lbn = -269,
>      in_off = 14,
>      in_exists = 0
>    }, {
>      in_lbn = -3852,
>      in_off = 244,
>      in_exists = 0
>    }, {
> ...

This seems to be correct.  E.g., the first 14 blocks pointed to by the
second indirect block are full and point to 256 data blocks.  The 15th
block pointed to by the second indirect block points to 244 data blocks
(4096 = 12 + 256 + 14 * 256 + 244).

> But, if I move the blockcnt cal to where UFS has it I get:
>
> Write 21 bytes at offset 0: same
>
> Write 21 bytes at offset 12288: same
>
> Write 21 bytes at offset 4194304
> lbn=4096
> {{
>      in_lbn = -269,
>      in_off = 1,
>      in_exists = 0
>    }, {
>      in_lbn = -269,
>      in_off = 244,
>      in_exists = 0
>    }, {
>      in_lbn = -512,
>      in_off = 0,
>      in_exists = 0
>    }, {
>    ...

This seems to be incorrect.  It doesn't have the magic number 14, and
I can't see how the magic number of -512 can be relevant.

>
> Notice how indir[1].off, indir[2].off and indir[2].in_lbn are different
> from the first run (with the current ext2 algo). The same thing happens
> with 8MB and 16MB offset writes too.
>
> Any ideas why this happens?
>
> Here's my simplified test case to simulate what happens on a 1KB block
> FS:

I merged the current version of ufs_getblns() into your test and got the
same results as with the current ext2_lbns().

%%%
diff -c2 z.c~ z.c
*** z.c~	Sat Jun 12 23:29:43 2004
--- z.c	Sun Jun 13 00:25:36 2004
***************
*** 23,36 ****

  int
! ext2_getlbns(vp, bn, ap, nump)
! 	struct vnode *vp;
! 	int32_t bn;
! 	struct indir *ap;
! 	int *nump;
  {
! 	long blockcnt, metalbn, realbn;
  	struct ext2mount *ump;
  	int i, numlevels, off;
- 	int64_t qblockcnt;

  	//ump = VFSTOEXT2(vp->v_mount);
--- 23,31 ----

  int
! ext2_getlbns(struct vnode *vp, int64_t bn, struct indir *ap, int *nump)
  {
! 	int64_t blockcnt, metalbn, realbn;
  	struct ext2mount *ump;
  	int i, numlevels, off;

  	//ump = VFSTOEXT2(vp->v_mount);
***************
*** 44,49 ****
  	numlevels = 0;
  	realbn = bn;
! 	if ((long)bn < 0)
! 		bn = -(long)bn;

  	/* The first NDADDR blocks are direct blocks. */
--- 39,44 ----
  	numlevels = 0;
  	realbn = bn;
! 	if (bn < 0)
! 		bn = -bn;

  	/* The first NDADDR blocks are direct blocks. */
***************
*** 60,72 ****
  		if (i == 0)
  			return (EFBIG);
! 		/*
! 		 * Use int64_t's here to avoid overflow for triple indirect
! 		 * blocks when longs have 32 bits and the block size is more
! 		 * than 4K.
! 		 */
! 		qblockcnt = (int64_t)blockcnt * MNINDIR(ump);
! 		if (bn < qblockcnt)
  			break;
- 		blockcnt = qblockcnt;
  	}

--- 55,61 ----
  		if (i == 0)
  			return (EFBIG);
! 		blockcnt *= MNINDIR(ump);
! 		if (bn < blockcnt)
  			break;
  	}

***************
*** 92,95 ****
--- 81,85 ----
  			break;

+ 		blockcnt /= MNINDIR(ump);
  		//blockcnt /= MNINDIR(ump);
  		off = (bn / blockcnt) % MNINDIR(ump);
***************
*** 102,106 ****

  		metalbn -= -1 + off * blockcnt;
- 		blockcnt /= MNINDIR(ump);
  	}
  	if (nump)
--- 92,95 ----
%%%

This patch was adapted from "cvs diff -c1 -r 1.51 -r 1.60 ufs_bmap.c".

Bruce