Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752000Ab0G0WBY (ORCPT ); Tue, 27 Jul 2010 18:01:24 -0400 Received: from mail-vw0-f46.google.com ([209.85.212.46]:54180 "EHLO mail-vw0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751396Ab0G0WBU (ORCPT ); Tue, 27 Jul 2010 18:01:20 -0400 DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:to:cc:subject:date:message-id:x-mailer:in-reply-to:references; b=OyU8jpv7WaUpavgb9yADgMDWktX8NCqCrq/zo3ixYB2CnD6uoThn/idgZT6jhvniwg SWp9E1hsnxi4ZG0P/lEhFZXJALGsB/vQmwCO+43hzTs2UbUEwZ/qLOFxCfKo7GxuOrdy SF6BTwQQPuuc5pZR/ykPhLCeS6536qNo2NMf0= From: bchociej@gmail.com To: chris.mason@oracle.com, linux-btrfs@vger.kernel.org Cc: linux-fsdevel@vger.kernel.org, cmm@us.ibm.com, bcchocie@us.ibm.com, mrlupfer@us.ibm.com, crscott@us.ibm.com, linux-kernel@vger.kernel.org Subject: [RFC PATCH 1/5] Btrfs: Add experimental hot data hash list index Date: Tue, 27 Jul 2010 17:00:19 -0500 Message-Id: <1280268023-18408-2-git-send-email-bchociej@gmail.com> X-Mailer: git-send-email 1.7.0.4 In-Reply-To: <1280268023-18408-1-git-send-email-bchociej@gmail.com> References: <1280268023-18408-1-git-send-email-bchociej@gmail.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 7426 Lines: 238 From: Ben Chociej Adds a hash table structure to efficiently lookup the data temperature of a file. Also adds a function to calculate that temperature based on some metrics kept in custom frequency data structs. Signed-off-by: Ben Chociej Signed-off-by: Matt Lupfer Signed-off-by: Conor Scott Reviewed-by: Mingming Cao Reviewed-by: Steve French --- fs/btrfs/hotdata_hash.c | 111 +++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/hotdata_hash.h | 89 +++++++++++++++++++++++++++++++++++++ 2 files changed, 200 insertions(+), 0 deletions(-) create mode 100644 fs/btrfs/hotdata_hash.c create mode 100644 fs/btrfs/hotdata_hash.h diff --git a/fs/btrfs/hotdata_hash.c b/fs/btrfs/hotdata_hash.c new file mode 100644 index 0000000..a0de853 --- /dev/null +++ b/fs/btrfs/hotdata_hash.c @@ -0,0 +1,111 @@ +#include +#include +#include +#include +#include "hotdata_map.h" +#include "hotdata_hash.h" +#include "async-thread.h" +#include "ctree.h" + +/* set thread to update temperatures every 5 minutes */ +#define HEAT_UPDATE_DELAY (HZ * 60 * 5) + +struct heat_hashlist_node *alloc_heat_hashlist_node(gfp_t mask) +{ + struct heat_hashlist_node *node; + + node = kmalloc(sizeof(struct heat_hashlist_node), mask); + if (!node || IS_ERR(node)) + return node; + INIT_HLIST_NODE(&node->hashnode); + node->freq_data = NULL; + node->hlist = NULL; + + return node; +} + +void free_heat_hashlists(struct btrfs_root *root) +{ + int i; + + /* Free node/range heat hash lists */ + for (i = 0; i < HEAT_HASH_SIZE; i++) { + struct hlist_node *pos = NULL, *pos2 = NULL; + struct heat_hashlist_node *heatnode = NULL; + + hlist_for_each_safe(pos, pos2, + &root->heat_inode_hl[i].hashhead) { + heatnode = hlist_entry(pos, struct heat_hashlist_node, + hashnode); + hlist_del(pos); + kfree(heatnode); + } + + hlist_for_each_safe(pos, pos2, + &root->heat_range_hl[i].hashhead) { + heatnode = hlist_entry(pos, struct heat_hashlist_node, + hashnode); + hlist_del(pos); + kfree(heatnode); + } + } +} + +/* + * Function that converts btrfs_freq_data structs to integer temperature + * values, determined by some constants in .h. + * + * This is not very calibrated, though we've gotten it in the ballpark. + */ +int btrfs_get_temp(struct btrfs_freq_data *fdata) +{ + u32 result = 0; + + struct timespec ckt = current_kernel_time(); + u64 cur_time = timespec_to_ns(&ckt); + + u32 nrr_heat = fdata->nr_reads << NRR_MULTIPLIER_POWER; + u32 nrw_heat = fdata->nr_writes << NRW_MULTIPLIER_POWER; + + u64 ltr_heat = (cur_time - timespec_to_ns(&fdata->last_read_time)) + >> LTR_DIVIDER_POWER; + u64 ltw_heat = (cur_time - timespec_to_ns(&fdata->last_write_time)) + >> LTW_DIVIDER_POWER; + + u64 avr_heat = (((u64) -1) - fdata->avg_delta_reads) + >> AVR_DIVIDER_POWER; + u64 avw_heat = (((u64) -1) - fdata->avg_delta_writes) + >> AVR_DIVIDER_POWER; + + if (ltr_heat >= ((u64) 1 << 32)) + ltr_heat = 0; + else + ltr_heat = ((u64) 1 << 32) - ltr_heat; + /* ltr_heat is now guaranteed to be u32 safe */ + + if (ltw_heat >= ((u64) 1 << 32)) + ltw_heat = 0; + else + ltw_heat = ((u64) 1 << 32) - ltw_heat; + /* ltw_heat is now guaranteed to be u32 safe */ + + if (avr_heat >= ((u64) 1 << 32)) + avr_heat = (u32) -1; + /* avr_heat is now guaranteed to be u32 safe */ + + if (avw_heat >= ((u64) 1 << 32)) + avr_heat = (u32) -1; + /* avw_heat is now guaranteed to be u32 safe */ + + nrr_heat = nrr_heat >> (3 - NRR_COEFF_POWER); + nrw_heat = nrw_heat >> (3 - NRW_COEFF_POWER); + ltr_heat = ltr_heat >> (3 - LTR_COEFF_POWER); + ltw_heat = ltw_heat >> (3 - LTW_COEFF_POWER); + avr_heat = avr_heat >> (3 - AVR_COEFF_POWER); + avw_heat = avw_heat >> (3 - AVW_COEFF_POWER); + + result = nrr_heat + nrw_heat + (u32) ltr_heat + + (u32) ltw_heat + (u32) avr_heat + (u32) avw_heat; + + return result >> (32 - HEAT_HASH_BITS); +} diff --git a/fs/btrfs/hotdata_hash.h b/fs/btrfs/hotdata_hash.h new file mode 100644 index 0000000..46bf61e --- /dev/null +++ b/fs/btrfs/hotdata_hash.h @@ -0,0 +1,89 @@ +#ifndef __HOTDATAHASH__ +#define __HOTDATAHASH__ + +#include +#include + +#define HEAT_HASH_BITS 8 +#define HEAT_HASH_SIZE (1 << HEAT_HASH_BITS) +#define HEAT_HASH_MASK (HEAT_HASH_SIZE - 1) +#define HEAT_MIN_VALUE 0 +#define HEAT_MAX_VALUE (HEAT_HASH_SIZE - 1) +#define HEAT_HOT_MIN (HEAT_HASH_SIZE - 50) + +/* + * The following comments explain what exactly comprises a unit of heat. + * + * Each of six values of heat are calculated and combined in order to form an + * overall temperature for the data: + * + * NRR - number of reads since mount + * NRW - number of writes since mount + * LTR - time elapsed since last read (ns) + * LTW - time elapsed since last write (ns) + * AVR - average delta between recent reads (ns) + * AVW - average delta between recent writes (ns) + * + * These values are divided (right-shifted) according to the *_DIVIDER_POWER + * values defined below to bring the numbers into a reasonable range. You can + * modify these values to fit your needs. However, each heat unit is a u32 and + * thus maxes out at 2^32 - 1. Therefore, you must choose your dividers quite + * carefully or else they could max out or be stuck at zero quite easily. + * + * (E.g., if you chose AVR_DIVIDER_POWER = 0, nothing less than 4s of atime + * delta would bring the temperature above zero, ever.) + * + * Finally, each value is added to the overall temperature between 0 and 8 + * times, depending on its *_COEFF_POWER value. Note that the coefficients are + * also actually implemented with shifts, so take care to treat these values + * as powers of 2. (I.e., 0 means we'll add it to the temp once; 1 = 2x, etc.) + */ + +#define NRR_MULTIPLIER_POWER 23 +#define NRR_COEFF_POWER 0 +#define NRW_MULTIPLIER_POWER 23 +#define NRW_COEFF_POWER 0 +#define LTR_DIVIDER_POWER 30 +#define LTR_COEFF_POWER 1 +#define LTW_DIVIDER_POWER 30 +#define LTW_COEFF_POWER 1 +#define AVR_DIVIDER_POWER 40 +#define AVR_COEFF_POWER 0 +#define AVW_DIVIDER_POWER 40 +#define AVW_COEFF_POWER 0 + +/* TODO a kmem cache for entry structs */ + +struct btrfs_root; + +/* Hash list heads for heat hash table */ +struct heat_hashlist_entry { + struct hlist_head hashhead; + rwlock_t rwlock; + u32 temperature; +}; + +/* Nodes stored in each hash list of hash table */ +struct heat_hashlist_node { + struct hlist_node hashnode; + struct btrfs_freq_data *freq_data; + struct heat_hashlist_entry *hlist; +}; + +struct heat_hashlist_node *alloc_heat_hashlist_node(gfp_t mask); +void free_heat_hashlists(struct btrfs_root *root); + +/* + * Returns a value from 0 to HEAT_MAX_VALUE indicating the temperature of the + * file (and consequently its bucket number in hashlist) + */ +int btrfs_get_temp(struct btrfs_freq_data *fdata); + +/* + * recalculates temperatures for inode or range + * and moves around in heat hash table based on temp + */ +void btrfs_update_heat_index(struct btrfs_freq_data *fdata, + struct btrfs_root *root); + +#endif /* __HOTDATAHASH__ */ -- 1.7.1 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/