ext2_find_near

ext2_find_near

[Rohit Sharma]

Hi all,

I was going through the function "ext2_find_near" in inode.c and could not
interpret the meaning of the last part of this code :

static ext2_fsblk_t ext2_find_near(struct inode *inode, Indirect *ind)
{
       struct ext2_inode_info *ei = EXT2_I(inode);
       __le32 *start = ind->bh ? (__le32 *) ind->bh->b_data : ei->i_data;
       __le32 *p;
       ext2_fsblk_t bg_start;
       ext2_fsblk_t colour;

       /* Try to find previous block */
      for (p = ind->p - 1; p >= start; p--)
               if (*p)
                       return le32_to_cpu(*p);

       /* No such thing, so let's try location of indirect block */
      if (ind->bh)
               return ind->bh->b_blocknr;

       /*
        * It is going to be refered from inode itself? OK, just put it into
        * the same cylinder group then.
        */

       bg_start = ext2_group_first_block_no(inode->i_sb, ei->i_block_group);

       / * what does the code below do?? why its is using pid of
current process?? */

       colour = (current->pid % 16) *
                       (EXT2_BLOCKS_PER_GROUP(inode->i_sb) / 16);
      return bg_start + colour;
}


What I understand from it is that it has something to do with reducing
the chances of a concurrent allocation -- supposedly from a different
PID.

Can someone just explain a bit on this, what exactly is happening ?

Thanks,
Rohit Sharma.

Re: ext2_find_near

[Theodore Tso]

On Thu, Jul 31, 2008 at 08:17:06PM +0530, Rohit Sharma wrote:
> What I understand from it is that it has something to do with reducing
> the chances of a concurrent allocation -- supposedly from a different
> PID.

Yes, that's exactly it.  To quote from from comment above the function:

 * In the latter case we colour the starting block by the callers PID to
 * prevent it from clashing with concurrent allocations for a different inode
 * in the same block group.

In computer science, the concept of "coloring" is to spread the
allocation across multiple (cpu's, processes, etc.) while
concentrating accesses from a specific CPU, processes, etc., in order
to provide better performance.  You will see references to coloring
pages for virtual memory systems, coloring slabs in slab allocators to
improve better cache utilization, etc.

When people talking using coloring to increase cache utilization, the
goal is to reduce the chances that cache collisions lead to premature
ejection of data from the cache.  In the case of block allocation, the
goal is that if you have two processes writing into the same directory
(for example, if you are compiling a program using "make -j4") that
they don't "collide" and start allocating blocks from the same
starting point, since that might result in an interleaved allocation
for the files.

What is going on here is that code is splitting the block group into
16 zones, and it using the low 4 bits of the process ID (i.e., pid %
16) to determine "zone" in the block group is used as a starting point
for the allocation.

This is a hueristic, and like all hueristics, in some cases it wins,
in other cases it is a lose.  Something like delayed allocation can do
a much better job than this particular hueristic.

					- Ted