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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAEH94Liftb9zhTt=5TFUOay=aAQ+MA6YXsQWWt0Kn+F8U2MJNg@mail.gmail.com>
Date:	Thu, 27 Sep 2012 14:23:16 +0800
From:	Zhi Yong Wu <zwu.kernel@...il.com>
To:	Dave Chinner <david@...morbit.com>
Cc:	linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org,
	linux-btrfs@...r.kernel.org, linux-ext4@...r.kernel.org,
	linuxram@...ux.vnet.ibm.com, viro@...iv.linux.org.uk,
	cmm@...ibm.com, tytso@....edu, marco.stornelli@...il.com,
	stroetmann@...olinux.com, diegocg@...il.com, chris@...muel.org,
	Zhi Yong Wu <wuzhy@...ux.vnet.ibm.com>
Subject: Re: [RFC v2 05/10] vfs: introduce one hash table

On Thu, Sep 27, 2012 at 11:43 AM, Dave Chinner <david@...morbit.com> wrote:
> On Sun, Sep 23, 2012 at 08:56:30PM +0800, zwu.kernel@...il.com wrote:
>> From: Zhi Yong Wu <wuzhy@...ux.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
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@...morbit.com



-- 
Regards,

Zhi Yong Wu
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html