linux-kernel - 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: <20120927034310.GM15236@dastard>
Date:	Thu, 27 Sep 2012 13:43:10 +1000
From:	Dave Chinner <david@...morbit.com>
To:	zwu.kernel@...il.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 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

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@...morbit.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/