This was a very complex task to complete. An even now I am not 100% sure that my solution is correct. The task was is to get a pointer to the the last block of data in an ext2 inode. This means I need to transverse the direct and indirect blocks of the ext2 inode. It took me a solid week and some serious brain segment faults but I think I have my solution. If you are reading this and know a better way, please post a comment.

The first concept was to search from begining to end. But to do this is a serious waste of time and cpu. The second concept was to start from the end and work my way up to the begining, skipping any indirect pointers that were zero. That means if the triple indirect pointer was zero skip it and look at the double indirect pointer. But this was still a waste of cpu cycles. Then I re-found the i_blocks variable in the ext2 inode structure. It states that:

include/linux/ext2_fs.h
   __le32  i_blocks;                /* Blocks count */

Blocks count is the number of blocks that inode is using. So all I would have to do is calculate where that block is. I could not find code that did this within the linux kernel. After a quick glance at the code, I decided to knock it out myself real quick. That was 8 days ago.

Lets start with i_blocks, it really is the number of blocks of size 512, but the block size of the standard installition of my linux is 4096. So the number of blocks (bn) is really i_blocks divided by eight.

bn = i_blocks / 8;

Next we know that the ext2 inode has direct blocks, indirect blocks, double indirect blocks, and triple indirect blocks. They are all contained in the i_block structure.

#define EXT2_NDIR_BLOCKS 12
#define EXT2_IND_BLOCK   EXT2_NDIR_BLOCKS      // 12
#define EXT2_DIND_BLOCK (EXT2_IND_BLOCK + 1)   // 13
#define EXT2_TIND_BLOCK (EXT2_DIND_BLOCK + 1)  // 14
#define EXT2_N_BLOCKS   (EXT2_TIND_BLOCK + 1)  // 15
   __le32  i_block[EXT2_N_BLOCKS];  /* Pointers to blocks */

So from i_block[0] to i_block[11] are the direct blocks, i_block[12] is the indirect block pointer, i_block[13] is the double indirect pointer, and i_block[14] is the triple indirect pointer. What this means that that the block number if greater than 12 is offset by 12 within each indirect section. The indirect block group holds 4096 pointers, the double indirect holds 4096 x 4096 pointers, and the triple indirect holds 4096 x 4096 x 4096 pointers. To normalize the we have to add EXT2_NDIR_BLOCKS plus the previous indirect size as needed to the block number (bn) defined above. Thus we get the normalized block number (nbn).

if (bn < db)                             // direct
   nbn = bn;
else if (bn < 4096 + db)                 // indirect
   nbn = bn – db;
else if (bn < (4096 << 12) + 4096 + db)  // double indirect
   nbn = bn – pagesize – db;
else                                     // triple indirect
   nbn = bn – (4096 << 12) – 4096 – db;

Haveing the normalize block number allows us to calculate the indirect, double indirect, and triple indirect index.

if (bn < db)                              // direct
{
   index = bn;
}
else if (bn < 4096 + db)              // indirect
{
   nbn = bn – db;
   index = nbn;
}
else if (bn < (4096 << 12) + 4096 + db)  // double indirect
{
   nbn = bn – 4096 – db;
   doubleindex = nbn / 4096;
   index = nbn % 4096;
}
else                                      // triple indirect
{
   nbn = bn – (4096 << 12) – 4096 – db;
   tripleindex = nbn / (4096 << 12);
   doubleindex = nbn / 4096;
   index = nbn % 4096;
}

If these indexes calculations are correct then we can pull out the block.

struct buffer_head *bh;
char *lbp;  // Last block pointer

if (bn < db)                              // direct
{
   index = bn;
   bh = sb_bread(sb, e->block[index]);
}
else if (bn < 4096 + db)              // indirect
{
   nbn = bn – db;
   index = nbn;
   bh = sb_bread(sb, e->block[EXT2_IND_BLOCK]);
   bh = sb_bread(sb, ((__u32 *)bh->b_data)[index]));
}
else if (bn < (4096 << 12) + 4096 + db)  // double indirect
{
   nbn = bn – 4096 – db;
   doubleindex = nbn / 4096;
   index = nbn % 4096;
   bh = sb_bread(sb, e->block[EXT2_DIND_BLOCK]);
   bh = sb_bread(sb, ((__u32 *)bh->b_data)[doubleindex]));
   bh = sb_bread(sb, ((__u32 *)bh->b_data)[index]));
}
else                                      // triple indirect
{
   nbn = bn – (4096 << 12) – 4096 – db;
   tripleindex = nbn / (4096 << 12);
   doubleindex = nbn / 4096;
   index = nbn % 4096;
   bh = sb_bread(sb, e->block[EXT2_TIND_BLOCK]);
   bh = sb_bread(sb, ((__u32 *)bh->b_data)[tripleindex]));
   bh = sb_bread(sb, ((__u32 *)bh->b_data)[doubleindex]));
   bh = sb_bread(sb, ((__u32 *)bh->b_data)[index]));
}

lbp = bh->b_data;

Well that is it. I am still checking to see if it works.