| 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
| ||
|
Message-ID: <CAEH94LjijFjKPYKPNr7Qhqa8gHTo5cX1btdNqj7KetDt4g_oYQ@mail.gmail.com> Date: Thu, 27 Sep 2012 15:10:38 +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 2:57 PM, Dave Chinner <david@...morbit.com> 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@...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? > > 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@...morbit.com -- Regards, Zhi Yong Wu -- 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/
Powered by blists - more mailing lists