why use a very low-efficient method to check all the uncheked inode in garbage_collect_pass

why use a very low-efficient method to check all the uncheked inode in garbage_collect_pass

[zhengjun]

I encountered a problem with my linux system（uses jffs2 file system）
After scan all inode on the flash, a background thread ( garbage_collect_thread) is start。 Before collecting,
it begins with checking crc of all inodes in inode_cache_list. But unluckly the checking work cost all most 3
minutes。It costs the 98% of all cpu resource.
I found that the time is wasted on finding out the valid inode_cache with specified inode id (c->checked_ino)。
checked_ino is counted from zero to c->higest_ino。 
In my system, there are 3000 files,but with higest_ino reached to 27262976。
(Because the old file is replaced by new file, by first delete then copy)。
So the most of time, jffs2_get_inode_cache can not find a valid inode with c->checked_ino。
So the useless search works wastes a lot of time.
why?
why use a increased  index to find each indoe_cache in inode_cache_list， but you never know which index is the valide ino.
The indode_cache_list is a hash table.
why not use a deep-first-search method to get each inode in hash table?
Just remember next valid ino in c->checked_ino.

Now I designed a new search method。 It works much more efficiently.

Could you optimize these code for better work?  Thanks!

jffs2_garbage_collect_pass()
{
   ....
    if( c->unchecked_size )
    {
        ic = jffs2_get_inode_cache_next( c, & c->checked_ino );  // new search method

       if( !ic )
      {
         BUG();
      }
   }
....
}

struct jffs2_inode_cache * jffs2_get_inode_cache_next( struct jffs2_sb_info * c, uint32_t * ino )
{
    struct jffs2_inode_cache * ret;
    uint32_t curIno;
    uint32_t ihash;

    curIno = *ino;
    ihash = curino % 128;

    ret = c->inode_cache_list[ihash];

    while( NULL != ret )
    {
        if( ret->ino >= curInfo )
        {
             goto findinode;
        }
        ret = ret ->next;
    }
    for( ihash = ihash + 1; ihash < 128; ihash ++ )
    {
        if( NULL != ( ret = c->inode_cache_list[ihash] ) )
            goto findinode;
    }
    return NULL;
findinode:
    if( ret->next )
    {
        *ino = ret->next->ino;
    } else
    {
        *ino = ihash + 1;
    }
   return ret;  
}

Re: why use a very low-efficient method to check all the uncheked inode in garbage_collect_pass

[Abhijit Lamsoge]

unsubscribe linux-mtd

On Fri, Jun 28, 2013 at 8:18 PM, zhengjun <zhengun23@126.com> wrote:
> I encountered a problem with my linux system（uses jffs2 file system）
> After scan all inode on the flash, a background thread ( garbage_collect_thread) is start。 Before collecting,
> it begins with checking crc of all inodes in inode_cache_list. But unluckly the checking work cost all most 3
> minutes。It costs the 98% of all cpu resource.
> I found that the time is wasted on finding out the valid inode_cache with specified inode id (c->checked_ino)。
> checked_ino is counted from zero to c->higest_ino。
> In my system, there are 3000 files,but with higest_ino reached to 27262976。
> (Because the old file is replaced by new file, by first delete then copy)。
> So the most of time, jffs2_get_inode_cache can not find a valid inode with c->checked_ino。
> So the useless search works wastes a lot of time.
> why?
> why use a increased  index to find each indoe_cache in inode_cache_list， but you never know which index is the valide ino.
> The indode_cache_list is a hash table.
> why not use a deep-first-search method to get each inode in hash table?
> Just remember next valid ino in c->checked_ino.
>
> Now I designed a new search method。 It works much more efficiently.
>
> Could you optimize these code for better work?  Thanks!
>
> jffs2_garbage_collect_pass()
> {
>    ....
>     if( c->unchecked_size )
>     {
>         ic = jffs2_get_inode_cache_next( c, & c->checked_ino );  // new search method
>
>        if( !ic )
>       {
>          BUG();
>       }
>    }
> ....
> }
>
> struct jffs2_inode_cache * jffs2_get_inode_cache_next( struct jffs2_sb_info * c, uint32_t * ino )
> {
>     struct jffs2_inode_cache * ret;
>     uint32_t curIno;
>     uint32_t ihash;
>
>     curIno = *ino;
>     ihash = curino % 128;
>
>     ret = c->inode_cache_list[ihash];
>
>     while( NULL != ret )
>     {
>         if( ret->ino >= curInfo )
>         {
>              goto findinode;
>         }
>         ret = ret ->next;
>     }
>     for( ihash = ihash + 1; ihash < 128; ihash ++ )
>     {
>         if( NULL != ( ret = c->inode_cache_list[ihash] ) )
>             goto findinode;
>     }
>     return NULL;
> findinode:
>     if( ret->next )
>     {
>         *ino = ret->next->ino;
>     } else
>     {
>         *ino = ihash + 1;
>     }
>    return ret;
> }
>
>
>
> ______________________________________________________
> Linux MTD discussion mailing list
> http://lists.infradead.org/mailman/listinfo/linux-mtd/