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

[Dave Chinner]

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
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
structure to point to the frequency data to track this....

> 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?

Cheers,

Dave.
-- 
Dave Chinner
david@xxxxxxxxxxxxx
--
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/