Re: [RFC v2 05/10] vfs: introduce one hash table

[Zhi Yong Wu]

On Thu, Sep 27, 2012 at 2:57 PM, Dave Chinner <david@xxxxxxxxxxxxx> wrote:
> On Thu, Sep 27, 2012 at 02:23:16PM +0800, Zhi Yong Wu wrote:
>> On Thu, Sep 27, 2012 at 11:43 AM, Dave Chinner <david@xxxxxxxxxxxxx> wrote:
>> > On Sun, Sep 23, 2012 at 08:56:30PM +0800, zwu.kernel@xxxxxxxxx wrote:
>> >> From: Zhi Yong Wu <wuzhy@xxxxxxxxxxxxxxxxxx>
>> >>
>> >>   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
>> Correct.
>> >
>> > 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-->....
>> Great, can we put them in hot_tracking.txt in Documentation?
>> >
>> >
>> > 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.
>> How will you know if one hot_inode_item should be moved between lists
>> when its freq data is changed?
>
> Record the current temperature in the frequency data, and if it
I know how to do it, thanks.
> changes, change the list it is on.
>
>> > 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.
>> OK.
>> >
>> > 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?
>> In hot_hash_calc_temperature(), you can see that one hot_inode or
>> hot_range's freq data will be distilled into one temperature value,
>> then it will be inserted to the heat map based on its temperature.
>> When the file corresponding to the inode or range got hotter or cold,
>> its location will be changed in the heat map based on its new
>> temperature in hot_hash_update_hash_table().
>
> Yes, but a hot_inode_item or hot_range_item can only have one
> location in the heat map, right? So it doesn't need external
Yes.
> structure to point to the frequency data to track this....
OK.
>
>> And the user will retrieve those freq data and temperature info via
>> debugfs or ioctl interfaces.
>
> Right - but that data is only extracted after an initial
> hot_inode_tree lookup - The heat map itself is never directly used
> for lookups. If it's not used for lookups based on temperature, why
> is it needed?
You mean we don't need hot_inode_tree? You know, after those hook
functions collect the freq data for inode, they will store those raw
info in hot_inode_tree. One private kthread will iterate this tree to
distill those raw freq data into one temperatue value in [0 ~ 255],
then link the corresponding hot_inode_item in heat map.

>
> Cheers,
>
> Dave.
> --
> Dave Chinner
> david@xxxxxxxxxxxxx



-- 
Regards,

Zhi Yong Wu
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/