On Thu, Sep 27, 2012 at 11:43 AM, Dave Chinner [off-list ref] wrote:

On Sun, Sep 23, 2012 at 08:56:30PM +0800, zwu.kernel@gmail.com wrote:

quoted

From: Zhi Yong Wu <redacted>

  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?

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().

And the user will retrieve those freq data and temperature info via
debugfs or ioctl interfaces.

Cheers,

Dave.
--
Dave Chinner
david@fromorbit.com

-- 
Regards,

Zhi Yong Wu