lkml.org 
[lkml]   [2012]   [Sep]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [RFC v2 05/10] vfs: introduce one hash table
    On Sun, Sep 23, 2012 at 08:56:30PM +0800, zwu.kernel@gmail.com wrote:
    > From: Zhi Yong Wu <wuzhy@linux.vnet.ibm.com>
    >
    > Adds a hash table structure which contains
    > a lot of hash list and is used to efficiently
    > look up the data temperature of a file or its
    > ranges.
    > In each hash list of hash table, the hash node
    > will keep track of temperature info.

    So, let me see if I've got the relationship straight:

    - sb->s_hot_info.hot_inode_tree indexes hot_inode_items, one per inode

    - hot_inode_item contains access frequency data for that inode

    - hot_inode_item holds a heat hash node to index the access
    frequency data for that inode

    - hot_inode_item.hot_range_tree indexes hot_range_items for that inode

    - hot_range_item contains access frequency data for that range

    - hot_range_item holds a heat hash node to index the access
    frequency data for that range

    - sb->s_hot_info.heat_inode_hl indexes per-inode heat hash nodes

    - sb->s_hot_info.heat_range_hl indexes per-range heat hash nodes

    How about some ascii art? :) Just looking at the hot inode item case
    (the range item case is the same pattern, though), we have:


    heat_inode_hl hot_inode_tree
    | |
    | V
    | +-------hot_inode_item-------+
    +---+ | frequency data |
    | V ^ V
    | ...<--hot_inode_item-->... | ...<--hot_inode_item-->....
    | frequency data | frequency data
    | ^ | ^
    | | | |
    | | | |
    +------>hot_hash_node-->hot_hash_node-->hot_hash_node-->....


    There's no actual data stored in the hot_hash_node, just pointer
    back to the frequency data, a hlist_node and a pointer to the
    hashlist head. IOWs, I agree with Ram that this does not need to
    exist and just embedding a hlist_node inside the hot_inode_item is
    all that is needed. i.e:

    heat_inode_hl hot_inode_tree
    | |
    | V
    | +-------hot_inode_item-------+
    | | frequency data |
    +---+ | hlist_node |
    | V ^ | V
    | ...<--hot_inode_item-->... | | ...<--hot_inode_item-->....
    | frequency data | | frequency data
    +------>hlist_node-----------+ +------->hlist_node--->.....

    There's no need for separate allocations, initialisations, locks and
    reference counting - all that is already in the hot_inode_item. The
    items have the same lifecycle limitations - a hot_hash_node must be
    torn down before the frequency data it points to is freed. Finally,
    there's no difference in how you move it between lists.

    Indeed, calling it a hash is wrong - there's not hashing at all
    - it keeping an array of list where each entry corresponds to a
    specific temperature. It is a *heat map*, not a hash list. i.e.
    inode_heat_map, not heat_inode_hl. HEAT_MAP_SIZE, not HASH_SIZE.

    As it is, there aren't any users of the heat maps that are generated
    in this patch set - it's not even exported to userspace or to
    debugfs, so I'm not sure how it will be used yet. How are these heat
    maps going to be used by filesystems, Zhi?

    Cheers,

    Dave.
    --
    Dave Chinner
    david@fromorbit.com


    \
     
     \ /
      Last update: 2012-09-27 06:21    [W:0.031 / U:60.020 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site