diff options
Diffstat (limited to 'fs/sdfat/amap_smart.c')
| -rw-r--r-- | fs/sdfat/amap_smart.c | 1314 |
1 files changed, 1314 insertions, 0 deletions
diff --git a/fs/sdfat/amap_smart.c b/fs/sdfat/amap_smart.c new file mode 100644 index 000000000000..b556f868d76e --- /dev/null +++ b/fs/sdfat/amap_smart.c @@ -0,0 +1,1314 @@ +/* + * Copyright (C) 2012-2013 Samsung Electronics Co., Ltd. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, see <http://www.gnu.org/licenses/>. + */ + +/************************************************************************/ +/* */ +/* PROJECT : exFAT & FAT12/16/32 File System */ +/* FILE : amap_smart.c */ +/* PURPOSE : FAT32 Smart allocation code for sdFAT */ +/* */ +/*----------------------------------------------------------------------*/ +/* NOTES */ +/* */ +/* */ +/************************************************************************/ + +#include <linux/slab.h> +#include <linux/vmalloc.h> + +#include "sdfat.h" +#include "core.h" +#include "amap_smart.h" + +/* AU list related functions */ +static inline void amap_list_del(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + + /* Will be used to check if the entry is a single entry(selected) */ + entry->prev = NULL; + entry->next = NULL; +} + +static inline int amap_insert_to_list(AU_INFO_T *au, struct slist_head *shead) +{ + struct slist_head *entry = &au->shead; + + ASSERT(!entry->head); + + entry->next = shead->next; + entry->head = shead; + + shead->next = entry; + + return 0; +} + +static inline int amap_remove_from_list(AU_INFO_T *au, struct slist_head *shead) +{ + struct slist_head *entry = &au->shead; + struct slist_head *iter; + + BUG_ON(entry->head != shead); + + iter = shead; + + while (iter->next) { + if (iter->next == entry) { + // iter->next = iter->next->next + iter->next = entry->next; + + entry->next = NULL; + entry->head = NULL; + return 0; + } + iter = iter->next; + } + + BUG_ON("Not reachable"); +} + +/* Full-linear serach => Find AU with max. number of fclu */ +static inline AU_INFO_T *amap_find_hot_au_largest(struct slist_head *shead) +{ + struct slist_head *iter; + uint16_t max_fclu = 0; + AU_INFO_T *entry, *ret = NULL; + + ASSERT(shead->head == shead); /* Singly-list condition */ + ASSERT(shead->next != shead); + + iter = shead->next; + + while (iter) { + entry = list_entry(iter, AU_INFO_T, shead); + + if (entry->free_clusters > max_fclu) { + max_fclu = entry->free_clusters; + ret = entry; + } + + iter = iter->next; + } + + return ret; +} + +/* Find partially used AU with max. number of fclu. + * If there is no partial AU available, pick a clean one + */ +static inline AU_INFO_T *amap_find_hot_au_partial(AMAP_T *amap) +{ + struct slist_head *iter; + uint16_t max_fclu = 0; + AU_INFO_T *entry, *ret = NULL; + + iter = &amap->slist_hot; + ASSERT(iter->head == iter); /* Singly-list condition */ + ASSERT(iter->next != iter); + + iter = iter->next; + + while (iter) { + entry = list_entry(iter, AU_INFO_T, shead); + + if (entry->free_clusters > max_fclu) { + if (entry->free_clusters < amap->clusters_per_au) { + max_fclu = entry->free_clusters; + ret = entry; + } else { + if (!ret) + ret = entry; + } + } + + iter = iter->next; + } + + return ret; +} + + + + +/* + * Size-base AU management functions + */ + +/* + * Add au into cold AU MAP + * au: an isolated (not in a list) AU data structure + */ +int amap_add_cold_au(AMAP_T *amap, AU_INFO_T *au) +{ + FCLU_NODE_T *fclu_node = NULL; + + /* Check if a single entry */ + BUG_ON(au->head.prev); + + /* Ignore if the au is full */ + if (!au->free_clusters) + return 0; + + /* Find entry */ + fclu_node = NODE(au->free_clusters, amap); + + /* Insert to the list */ + list_add_tail(&(au->head), &(fclu_node->head)); + + /* Update fclu_hint (Increase) */ + if (au->free_clusters > amap->fclu_hint) + amap->fclu_hint = au->free_clusters; + + return 0; +} + +/* + * Remove an AU from AU MAP + */ +int amap_remove_cold_au(AMAP_T *amap, AU_INFO_T *au) +{ + struct list_head *prev = au->head.prev; + + /* Single entries are not managed in lists */ + if (!prev) { + BUG_ON(au->free_clusters > 0); + return 0; + } + + /* remove from list */ + amap_list_del(&(au->head)); + + return 0; +} + + +/* "Find" best fit AU + * returns NULL if there is no AU w/ enough free space. + * + * This function doesn't change AU status. + * The caller should call amap_remove_cold_au() if needed. + */ +AU_INFO_T *amap_find_cold_au_bestfit(AMAP_T *amap, uint16_t free_clusters) +{ + AU_INFO_T *au = NULL; + FCLU_NODE_T *fclu_iter; + + if (free_clusters <= 0 || free_clusters > amap->clusters_per_au) { + EMSG("AMAP: amap_find_cold_au_bestfit / unexpected arg. (%d)\n", + free_clusters); + return NULL; + } + + fclu_iter = NODE(free_clusters, amap); + + if (amap->fclu_hint < free_clusters) { + /* There is no AUs with enough free_clusters */ + return NULL; + } + + /* Naive Hash management (++) */ + do { + if (!list_empty(&fclu_iter->head)) { + struct list_head *first = fclu_iter->head.next; + + au = list_entry(first, AU_INFO_T, head); + + break; + } + + fclu_iter++; + } while (fclu_iter < (amap->fclu_nodes + amap->clusters_per_au)); + + + // BUG_ON(au->free_clusters < 0); + BUG_ON(au && (au->free_clusters > amap->clusters_per_au)); + + return au; +} + + +/* "Pop" best fit AU + * + * returns NULL if there is no AU w/ enough free space. + * The returned AU will not be in the list anymore. + */ +AU_INFO_T *amap_pop_cold_au_bestfit(AMAP_T *amap, uint16_t free_clusters) +{ + /* Naive implementation */ + AU_INFO_T *au; + + au = amap_find_cold_au_bestfit(amap, free_clusters); + if (au) + amap_remove_cold_au(amap, au); + + return au; +} + + + +/* Pop the AU with the largest free space + * + * search from 'start_fclu' to 0 + * (target freecluster : -1 for each step) + * start_fclu = 0 means to search from the max. value + */ +AU_INFO_T *amap_pop_cold_au_largest(AMAP_T *amap, uint16_t start_fclu) +{ + AU_INFO_T *au = NULL; + FCLU_NODE_T *fclu_iter; + + if (!start_fclu) + start_fclu = amap->clusters_per_au; + if (start_fclu > amap->clusters_per_au) + start_fclu = amap->clusters_per_au; + + /* Use hint (search start point) */ + if (amap->fclu_hint < start_fclu) + fclu_iter = NODE(amap->fclu_hint, amap); + else + fclu_iter = NODE(start_fclu, amap); + + /* Naive Hash management */ + do { + if (!list_empty(&fclu_iter->head)) { + struct list_head *first = fclu_iter->head.next; + + au = list_entry(first, AU_INFO_T, head); + // BUG_ON((au < amap->entries) || ((amap->entries + amap->n_au) <= au)); + + amap_list_del(first); + + // (Hint) Possible maximum value of free clusters (among cold) + /* if it wasn't the whole search, don't update fclu_hint */ + if (start_fclu == amap->clusters_per_au) + amap->fclu_hint = au->free_clusters; + + break; + } + + fclu_iter--; + } while (amap->fclu_nodes <= fclu_iter); + + return au; +} + + + +/* + * =============================================== + * Allocation Map related functions + * =============================================== + */ + +/* Create AMAP related data structure (mount time) */ +int amap_create(struct super_block *sb, u32 pack_ratio, u32 sect_per_au, u32 hidden_sect) +{ + FS_INFO_T *fsi = &(SDFAT_SB(sb)->fsi); + AMAP_T *amap; + int total_used_clusters; + int n_au_table = 0; + int i, i_clu, i_au; + int i_au_root = -1, i_au_hot_from = INT_MAX; + u32 misaligned_sect = hidden_sect; + u64 tmp; + + BUG_ON(!fsi->bd_opened); + + if (fsi->amap) + return -EEXIST; + + /* Check conditions */ + if (fsi->vol_type != FAT32) { + sdfat_msg(sb, KERN_ERR, "smart allocation is only available " + "with fat32-fs"); + return -ENOTSUPP; + } + + if (fsi->num_sectors < AMAP_MIN_SUPPORT_SECTORS) { + sdfat_msg(sb, KERN_ERR, "smart allocation is only available " + "with sectors above %d", AMAP_MIN_SUPPORT_SECTORS); + return -ENOTSUPP; + } + + /* AU size must be a multiple of clu_size */ + if ((sect_per_au <= 0) || (sect_per_au & (fsi->sect_per_clus - 1))) { + sdfat_msg(sb, KERN_ERR, + "invalid AU size (sect_per_au : %u, " + "sect_per_clus : %u) " + "please re-format for performance.", + sect_per_au, fsi->sect_per_clus); + return -EINVAL; + } + + /* the start sector of this partition must be a multiple of clu_size */ + if (misaligned_sect & (fsi->sect_per_clus - 1)) { + sdfat_msg(sb, KERN_ERR, + "misaligned part (start sect : %u, " + "sect_per_clus : %u) " + "please re-format for performance.", + misaligned_sect, fsi->sect_per_clus); + return -EINVAL; + } + + /* data start sector must be a multiple of clu_size */ + if (fsi->data_start_sector & (fsi->sect_per_clus - 1)) { + sdfat_msg(sb, KERN_ERR, + "misaligned data area (start sect : %llu, " + "sect_per_clus : %u) " + "please re-format for performance.", + fsi->data_start_sector, fsi->sect_per_clus); + return -EINVAL; + } + + misaligned_sect &= (sect_per_au - 1); + + /* Allocate data structrues */ + amap = kzalloc(sizeof(AMAP_T), GFP_NOIO); + if (!amap) + return -ENOMEM; + + amap->sb = sb; + + tmp = fsi->num_sectors + misaligned_sect + sect_per_au - 1; + do_div(tmp, sect_per_au); + amap->n_au = tmp; + amap->n_clean_au = 0; + amap->n_full_au = 0; + + /* Reflect block-partition align first, + * then partition-data_start align + */ + amap->clu_align_bias = (misaligned_sect / fsi->sect_per_clus); + amap->clu_align_bias += (fsi->data_start_sector >> fsi->sect_per_clus_bits) - CLUS_BASE; + amap->clusters_per_au = sect_per_au / fsi->sect_per_clus; + + /* That is, + * the size of cluster is at least 4KB if the size of AU is 4MB + */ + if (amap->clusters_per_au > MAX_CLU_PER_AU) { + sdfat_log_msg(sb, KERN_INFO, + "too many clusters per AU (clus/au:%d > %d).", + amap->clusters_per_au, + MAX_CLU_PER_AU); + } + + /* is it needed? why here? */ + // set_sb_dirty(sb); + + spin_lock_init(&amap->amap_lock); + + amap->option.packing_ratio = pack_ratio; + amap->option.au_size = sect_per_au; + amap->option.au_align_factor = hidden_sect; + + + /* Allocate AU info table */ + n_au_table = (amap->n_au + N_AU_PER_TABLE - 1) / N_AU_PER_TABLE; + amap->au_table = kmalloc(sizeof(AU_INFO_T *) * n_au_table, GFP_NOIO); + if (!amap->au_table) { + sdfat_msg(sb, KERN_ERR, + "failed to alloc amap->au_table\n"); + kfree(amap); + return -ENOMEM; + } + + for (i = 0; i < n_au_table; i++) + amap->au_table[i] = (AU_INFO_T *)get_zeroed_page(GFP_NOIO); + + /* Allocate buckets indexed by # of free clusters */ + amap->fclu_order = get_order(sizeof(FCLU_NODE_T) * amap->clusters_per_au); + + // XXX: amap->clusters_per_au limitation is 512 (w/ 8 byte list_head) + sdfat_log_msg(sb, KERN_INFO, "page orders for AU nodes : %d " + "(clus_per_au : %d, node_size : %lu)", + amap->fclu_order, + amap->clusters_per_au, + (unsigned long)sizeof(FCLU_NODE_T)); + + if (!amap->fclu_order) + amap->fclu_nodes = (FCLU_NODE_T *)get_zeroed_page(GFP_NOIO); + else + amap->fclu_nodes = vzalloc(PAGE_SIZE << amap->fclu_order); + + amap->fclu_hint = amap->clusters_per_au; + + /* Hot AU list, ignored AU list */ + amap->slist_hot.next = NULL; + amap->slist_hot.head = &amap->slist_hot; + amap->total_fclu_hot = 0; + + amap->slist_ignored.next = NULL; + amap->slist_ignored.head = &amap->slist_ignored; + + /* Strategy related vars. */ + amap->cur_cold.au = NULL; + amap->cur_hot.au = NULL; + amap->n_need_packing = 0; + + + /* Build AMAP info */ + total_used_clusters = 0; // Count # of used clusters + + i_au_root = i_AU_of_CLU(amap, fsi->root_dir); + i_au_hot_from = amap->n_au - (SMART_ALLOC_N_HOT_AU - 1); + + for (i = 0; i < amap->clusters_per_au; i++) + INIT_LIST_HEAD(&amap->fclu_nodes[i].head); + + /* + * Thanks to kzalloc() + * amap->entries[i_au].free_clusters = 0; + * amap->entries[i_au].head.prev = NULL; + * amap->entries[i_au].head.next = NULL; + */ + + /* Parse FAT table */ + for (i_clu = CLUS_BASE; i_clu < fsi->num_clusters; i_clu++) { + u32 clu_data; + AU_INFO_T *au; + + if (fat_ent_get(sb, i_clu, &clu_data)) { + sdfat_msg(sb, KERN_ERR, + "failed to read fat entry(%u)\n", i_clu); + goto free_and_eio; + } + + if (IS_CLUS_FREE(clu_data)) { + au = GET_AU(amap, i_AU_of_CLU(amap, i_clu)); + au->free_clusters++; + } else + total_used_clusters++; + } + + /* Build AU list */ + for (i_au = 0; i_au < amap->n_au; i_au++) { + AU_INFO_T *au = GET_AU(amap, i_au); + + au->idx = i_au; + BUG_ON(au->free_clusters > amap->clusters_per_au); + + if (au->free_clusters == amap->clusters_per_au) + amap->n_clean_au++; + else if (au->free_clusters == 0) + amap->n_full_au++; + + /* If hot, insert to the hot list */ + if (i_au >= i_au_hot_from) { + amap_add_hot_au(amap, au); + amap->total_fclu_hot += au->free_clusters; + } else if (i_au != i_au_root || SMART_ALLOC_N_HOT_AU == 0) { + /* Otherwise, insert to the free cluster hash */ + amap_add_cold_au(amap, au); + } + } + + /* Hot list -> (root) -> (last) -> (last - 1) -> ... */ + if (i_au_root >= 0 && SMART_ALLOC_N_HOT_AU > 0) { + amap_add_hot_au(amap, GET_AU(amap, i_au_root)); + amap->total_fclu_hot += GET_AU(amap, i_au_root)->free_clusters; + } + + fsi->amap = amap; + fsi->used_clusters = total_used_clusters; + + sdfat_msg(sb, KERN_INFO, + "AMAP: Smart allocation enabled (opt : %u / %u / %u)", + amap->option.au_size, amap->option.au_align_factor, + amap->option.packing_ratio); + + /* Debug purpose - check */ + //{ + //u32 used_clusters; + //fat_count_used_clusters(sb, &used_clusters) + //ASSERT(used_clusters == total_used_clusters); + //} + + return 0; + + +free_and_eio: + if (amap) { + if (amap->au_table) { + for (i = 0; i < n_au_table; i++) + free_page((unsigned long)amap->au_table[i]); + kfree(amap->au_table); + } + if (amap->fclu_nodes) { + if (!amap->fclu_order) + free_page((unsigned long)amap->fclu_nodes); + else + vfree(amap->fclu_nodes); + } + kfree(amap); + } + return -EIO; +} + + +/* Free AMAP related structure */ +void amap_destroy(struct super_block *sb) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + int n_au_table; + + if (!amap) + return; + + DMSG("%s\n", __func__); + + n_au_table = (amap->n_au + N_AU_PER_TABLE - 1) / N_AU_PER_TABLE; + + if (amap->au_table) { + int i; + + for (i = 0; i < n_au_table; i++) + free_page((unsigned long)amap->au_table[i]); + + kfree(amap->au_table); + } + if (!amap->fclu_order) + free_page((unsigned long)amap->fclu_nodes); + else + vfree(amap->fclu_nodes); + kfree(amap); + SDFAT_SB(sb)->fsi.amap = NULL; +} + + +/* + * Check status of FS + * and change destination if needed to disable AU-aligned alloc. + * (from ALLOC_COLD_ALIGNED to ALLOC_COLD_SEQ) + */ +static inline int amap_update_dest(AMAP_T *amap, int ori_dest) +{ + FS_INFO_T *fsi = &(SDFAT_SB(amap->sb)->fsi); + int n_partial_au, n_partial_freeclus; + + if (ori_dest != ALLOC_COLD_ALIGNED) + return ori_dest; + + /* # of partial AUs and # of clusters in those AUs */ + n_partial_au = amap->n_au - amap->n_clean_au - amap->n_full_au; + n_partial_freeclus = fsi->num_clusters - fsi->used_clusters - + amap->clusters_per_au * amap->n_clean_au; + + /* Status of AUs : Full / Partial / Clean + * If there are many partial (and badly fragmented) AUs, + * the throughput will decrease extremly. + * + * The follow code will treat those worst cases. + */ + + /* XXX: AMAP heuristics */ + if ((amap->n_clean_au * 50 <= amap->n_au) && + (n_partial_freeclus*2) < (n_partial_au*amap->clusters_per_au)) { + /* If clean AUs are fewer than 2% of n_au (80 AUs per 16GB) + * and fragment ratio is more than 2 (AVG free_clusters=half AU) + * + * disable clean-first allocation + * enable VFAT-like sequential allocation + */ + return ALLOC_COLD_SEQ; + } + + return ori_dest; +} + + +#define PACKING_SOFTLIMIT (amap->option.packing_ratio) +#define PACKING_HARDLIMIT (amap->option.packing_ratio * 4) +/* + * Pick a packing AU if needed. + * Otherwise just return NULL + * + * This function includes some heuristics. + */ +static inline AU_INFO_T *amap_get_packing_au(AMAP_T *amap, int dest, int num_to_wb, int *clu_to_skip) +{ + AU_INFO_T *au = NULL; + + if (dest == ALLOC_COLD_PACKING) { + /* ALLOC_COLD_PACKING: + * Packing-first mode for defrag. + * Optimized to save clean AU + * + * 1) best-fit AU + * 2) Smallest AU (w/ minimum free clusters) + */ + if (num_to_wb >= amap->clusters_per_au) + num_to_wb = num_to_wb % amap->clusters_per_au; + + /* 이거 주석처리하면, AU size 딱 맞을때는 clean, 나머지는 작은거부터 */ + if (num_to_wb == 0) + num_to_wb = 1; // Don't use clean AUs + + au = amap_find_cold_au_bestfit(amap, num_to_wb); + if (au && au->free_clusters == amap->clusters_per_au && num_to_wb > 1) { + /* if au is clean then get a new partial one */ + au = amap_find_cold_au_bestfit(amap, 1); + } + + if (au) { + amap->n_need_packing = 0; + amap_remove_cold_au(amap, au); + return au; + } + } + + + /* Heuristic packing: + * This will improve QoS greatly. + * + * Count # of AU_ALIGNED allocation. + * If the number exceeds the specific threshold, + * allocate on a partial AU or generate random I/O. + */ + if ((PACKING_SOFTLIMIT > 0) && + (amap->n_need_packing >= PACKING_SOFTLIMIT) && + (num_to_wb < (int)amap->clusters_per_au)) { + /* Best-fit packing: + * If num_to_wb (expected number to be allocated) is smaller + * than AU_SIZE, find a best-fit AU. + */ + + /* Back margin (heuristics) */ + if (num_to_wb < amap->clusters_per_au / 4) + num_to_wb = amap->clusters_per_au / 4; + + au = amap_find_cold_au_bestfit(amap, num_to_wb); + if (au != NULL) { + amap_remove_cold_au(amap, au); + + MMSG("AMAP: packing (cnt: %d) / softlimit, " + "best-fit (num_to_wb: %d))\n", + amap->n_need_packing, num_to_wb); + + if (au->free_clusters > num_to_wb) { // Best-fit search: if 문 무조건 hit + *clu_to_skip = au->free_clusters - num_to_wb; + /* otherwise don't skip */ + } + amap->n_need_packing = 0; + return au; + } + } + + if ((PACKING_HARDLIMIT) && amap->n_need_packing >= PACKING_HARDLIMIT) { + /* Compulsory SLC flushing: + * If there was no chance to do best-fit packing + * and the # of AU-aligned allocation exceeds HARD threshold, + * then pick a clean AU and generate a compulsory random I/O. + */ + au = amap_pop_cold_au_largest(amap, amap->clusters_per_au); + if (au) { + MMSG("AMAP: packing (cnt: %d) / hard-limit, largest)\n", + amap->n_need_packing); + + if (au->free_clusters >= 96) { + *clu_to_skip = au->free_clusters / 2; + MMSG("AMAP: cluster idx re-position\n"); + } + amap->n_need_packing = 0; + return au; + } + } + + /* Update # of clean AU allocation */ + amap->n_need_packing++; + return NULL; +} + + +/* Pick a target AU: + * This function should be called + * only if there are one or more free clusters in the bdev. + */ +TARGET_AU_T *amap_get_target_au(AMAP_T *amap, int dest, int num_to_wb) +{ + int loop_count = 0; + +retry: + if (++loop_count >= 3) { + /* No space available (or AMAP consistency error) + * This could happen because of the ignored AUs but not likely + * (because the defrag daemon will not work if there is no enough space) + */ + BUG_ON(amap->slist_ignored.next == NULL); + return NULL; + } + + /* Hot clusters (DIR) */ + if (dest == ALLOC_HOT) { + + /* Working hot AU exist? */ + if (amap->cur_hot.au == NULL || amap->cur_hot.au->free_clusters == 0) { + AU_INFO_T *au; + + if (amap->total_fclu_hot == 0) { + /* No more hot AU avaialbe */ + dest = ALLOC_COLD; + + goto retry; + } + + au = amap_find_hot_au_partial(amap); + + BUG_ON(au == NULL); + BUG_ON(au->free_clusters <= 0); + + amap->cur_hot.au = au; + amap->cur_hot.idx = 0; + amap->cur_hot.clu_to_skip = 0; + } + + /* Now allocate on a hot AU */ + return &amap->cur_hot; + } + + /* Cold allocation: + * If amap->cur_cold.au has one or more free cluster(s), + * then just return amap->cur_cold + */ + if ((!amap->cur_cold.au) + || (amap->cur_cold.idx == amap->clusters_per_au) + || (amap->cur_cold.au->free_clusters == 0)) { + + AU_INFO_T *au = NULL; + const AU_INFO_T *old_au = amap->cur_cold.au; + int n_clu_to_skip = 0; + + if (old_au) { + ASSERT(!IS_AU_WORKING(old_au, amap)); + /* must be NOT WORKING AU. + * (only for information gathering) + */ + } + + /* Next target AU is needed: + * There are 3 possible ALLOC options for cold AU + * + * ALLOC_COLD_ALIGNED: Clean AU first, but heuristic packing is ON + * ALLOC_COLD_PACKING: Packing AU first (usually for defrag) + * ALLOC_COLD_SEQ : Sequential AU allocation (VFAT-like) + */ + + /* Experimental: Modify allocation destination if needed (ALIGNED => SEQ) */ + // dest = amap_update_dest(amap, dest); + + if ((dest == ALLOC_COLD_SEQ) && old_au) { + int i_au = old_au->idx + 1; + + while (i_au != old_au->idx) { + au = GET_AU(amap, i_au); + + if ((au->free_clusters > 0) && + !IS_AU_HOT(au, amap) && + !IS_AU_IGNORED(au, amap)) { + MMSG("AMAP: new cold AU(%d) with %d " + "clusters (seq)\n", + au->idx, au->free_clusters); + + amap_remove_cold_au(amap, au); + goto ret_new_cold; + } + i_au++; + if (i_au >= amap->n_au) + i_au = 0; + } + + // no cold AUs are available => Hot allocation + dest = ALLOC_HOT; + goto retry; + } + + + /* + * Check if packing is needed + * (ALLOC_COLD_PACKING is treated by this function) + */ + au = amap_get_packing_au(amap, dest, num_to_wb, &n_clu_to_skip); + if (au) { + MMSG("AMAP: new cold AU(%d) with %d clusters " + "(packing)\n", au->idx, au->free_clusters); + goto ret_new_cold; + } + + /* ALLOC_COLD_ALIGNED */ + /* Check if the adjacent AU is clean */ + if (old_au && ((old_au->idx + 1) < amap->n_au)) { + au = GET_AU(amap, old_au->idx + 1); + if ((au->free_clusters == amap->clusters_per_au) && + !IS_AU_HOT(au, amap) && + !IS_AU_IGNORED(au, amap)) { + MMSG("AMAP: new cold AU(%d) with %d clusters " + "(adjacent)\n", au->idx, au->free_clusters); + amap_remove_cold_au(amap, au); + goto ret_new_cold; + } + } + + /* Clean or largest AU */ + au = amap_pop_cold_au_largest(amap, 0); + if (!au) { + //ASSERT(amap->total_fclu_hot == (fsi->num_clusters - fsi->used_clusters - 2)); + dest = ALLOC_HOT; + goto retry; + } + + MMSG("AMAP: New cold AU (%d) with %d clusters\n", + au->idx, au->free_clusters); + +ret_new_cold: + SET_AU_WORKING(au); + + amap->cur_cold.au = au; + amap->cur_cold.idx = 0; + amap->cur_cold.clu_to_skip = n_clu_to_skip; + } + + return &amap->cur_cold; +} + +/* Put and update target AU */ +void amap_put_target_au(AMAP_T *amap, TARGET_AU_T *cur, unsigned int num_allocated) +{ + /* Update AMAP info vars. */ + if (num_allocated > 0 && + (cur->au->free_clusters + num_allocated) == amap->clusters_per_au) { + /* if the target AU was a clean AU before this allocation ... */ + amap->n_clean_au--; + } + if (num_allocated > 0 && + cur->au->free_clusters == 0) + amap->n_full_au++; + + if (IS_AU_HOT(cur->au, amap)) { + /* Hot AU */ + MMSG("AMAP: hot allocation at AU %d\n", cur->au->idx); + amap->total_fclu_hot -= num_allocated; + + /* Intra-AU round-robin */ + if (cur->idx >= amap->clusters_per_au) + cur->idx = 0; + + /* No more space available */ + if (cur->au->free_clusters == 0) + cur->au = NULL; + + } else { + /* non-hot AU */ + ASSERT(IS_AU_WORKING(cur->au, amap)); + + if (cur->idx >= amap->clusters_per_au || cur->au->free_clusters == 0) { + /* It should be inserted back to AU MAP */ + cur->au->shead.head = NULL; // SET_AU_NOT_WORKING + amap_add_cold_au(amap, cur->au); + + // cur->au = NULL; // This value will be used for the next AU selection + cur->idx = amap->clusters_per_au; // AU closing + } + } + +} + + +/* Reposition target->idx for packing (Heuristics): + * Skip (num_to_skip) free clusters in (cur->au) + */ +static inline int amap_skip_cluster(struct super_block *sb, TARGET_AU_T *cur, int num_to_skip) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + u32 clu, read_clu; + MMSG_VAR(int num_to_skip_orig = num_to_skip); + + if (num_to_skip >= cur->au->free_clusters) { + EMSG("AMAP(%s): skip mis-use. amap_566\n", __func__); + return -EIO; + } + + clu = CLU_of_i_AU(amap, cur->au->idx, cur->idx); + while (num_to_skip > 0) { + if (clu >= CLUS_BASE) { + /* Cf. + * If AMAP's integrity is okay, + * we don't need to check if (clu < fsi->num_clusters) + */ + + if (fat_ent_get(sb, clu, &read_clu)) + return -EIO; + + if (IS_CLUS_FREE(read_clu)) + num_to_skip--; + } + + // Move clu->idx + clu++; + (cur->idx)++; + + if (cur->idx >= amap->clusters_per_au) { + /* End of AU (Not supposed) */ + EMSG("AMAP: Skip - End of AU?! (amap_596)\n"); + cur->idx = 0; + return -EIO; + } + } + + MMSG("AMAP: Skip_clusters (%d skipped => %d, among %d free clus)\n", + num_to_skip_orig, cur->idx, cur->au->free_clusters); + + return 0; +} + + +/* AMAP-based allocation function for FAT32 */ +s32 amap_fat_alloc_cluster(struct super_block *sb, u32 num_alloc, CHAIN_T *p_chain, s32 dest) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + TARGET_AU_T *cur = NULL; + AU_INFO_T *target_au = NULL; /* Allocation target AU */ + s32 ret = -ENOSPC; + u32 last_clu = CLUS_EOF, read_clu; + u32 new_clu, total_cnt; + u32 num_allocated = 0, num_allocated_each = 0; + FS_INFO_T *fsi = &(SDFAT_SB(sb)->fsi); + + BUG_ON(!amap); + BUG_ON(IS_CLUS_EOF(fsi->used_clusters)); + + total_cnt = fsi->num_clusters - CLUS_BASE; + + if (unlikely(total_cnt < fsi->used_clusters)) { + sdfat_fs_error_ratelimit(sb, + "AMAP(%s): invalid used clusters(t:%u,u:%u)\n", + __func__, total_cnt, fsi->used_clusters); + return -EIO; + } + + if (num_alloc > total_cnt - fsi->used_clusters) + return -ENOSPC; + + p_chain->dir = CLUS_EOF; + + set_sb_dirty(sb); + + // spin_lock(&amap->amap_lock); + +retry_alloc: + /* Allocation strategy implemented */ + cur = amap_get_target_au(amap, dest, fsi->reserved_clusters); + if (unlikely(!cur)) { + // There is no available AU (only ignored-AU are left) + sdfat_msg(sb, KERN_ERR, "AMAP Allocator: no avaialble AU."); + goto error; + } + + /* If there are clusters to skip */ + if (cur->clu_to_skip > 0) { + if (amap_skip_cluster(sb, &amap->cur_cold, cur->clu_to_skip)) { + ret = -EIO; + goto error; + } + cur->clu_to_skip = 0; + } + + target_au = cur->au; + + /* + * cur->au : target AU info pointer + * cur->idx : the intra-cluster idx in the AU to start from + */ + BUG_ON(!cur->au); + BUG_ON(!cur->au->free_clusters); + BUG_ON(cur->idx >= amap->clusters_per_au); + + num_allocated_each = 0; + new_clu = CLU_of_i_AU(amap, target_au->idx, cur->idx); + + do { + /* Allocate at the target AU */ + if ((new_clu >= CLUS_BASE) && (new_clu < fsi->num_clusters)) { + if (fat_ent_get(sb, new_clu, &read_clu)) { + // spin_unlock(&amap->amap_lock); + ret = -EIO; + goto error; + } + + if (IS_CLUS_FREE(read_clu)) { + BUG_ON(GET_AU(amap, i_AU_of_CLU(amap, new_clu)) != target_au); + + /* Free cluster found */ + if (fat_ent_set(sb, new_clu, CLUS_EOF)) { + ret = -EIO; + goto error; + } + + num_allocated_each++; + + if (IS_CLUS_EOF(p_chain->dir)) { + p_chain->dir = new_clu; + } else { + if (fat_ent_set(sb, last_clu, new_clu)) { + ret = -EIO; + goto error; + } + } + last_clu = new_clu; + + /* Update au info */ + target_au->free_clusters--; + } + + } + + new_clu++; + (cur->idx)++; + + /* End of the AU */ + if ((cur->idx >= amap->clusters_per_au) || !(target_au->free_clusters)) + break; + } while (num_allocated_each < num_alloc); + + /* Update strategy info */ + amap_put_target_au(amap, cur, num_allocated_each); + + + num_allocated += num_allocated_each; + fsi->used_clusters += num_allocated_each; + num_alloc -= num_allocated_each; + + + if (num_alloc > 0) + goto retry_alloc; + + // spin_unlock(&amap->amap_lock); + return 0; +error: + if (num_allocated) + fsi->fs_func->free_cluster(sb, p_chain, 0); + return ret; +} + + +/* Free cluster for FAT32 (not implemented yet) */ +s32 amap_free_cluster(struct super_block *sb, CHAIN_T *p_chain, s32 do_relse) +{ + return -ENOTSUPP; +} + + +/* + * This is called by fat_free_cluster() + * to update AMAP info. + */ +s32 amap_release_cluster(struct super_block *sb, u32 clu) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + AU_INFO_T *au; + int i_au; + + // spin_lock(&amap->amap_lock); + + /* Update AU info */ + i_au = i_AU_of_CLU(amap, clu); + BUG_ON(i_au >= amap->n_au); + au = GET_AU(amap, i_au); + if (au->free_clusters >= amap->clusters_per_au) { + sdfat_fs_error(sb, "%s, au->free_clusters(%hd) is " + "greater than or equal to amap->clusters_per_au(%hd)", + __func__, au->free_clusters, amap->clusters_per_au); + return -EIO; + } + + if (IS_AU_HOT(au, amap)) { + MMSG("AMAP: Hot cluster freed\n"); + au->free_clusters++; + amap->total_fclu_hot++; + } else if (!IS_AU_WORKING(au, amap) && !IS_AU_IGNORED(au, amap)) { + /* Ordinary AU - update AU tree */ + // Can be optimized by implementing amap_update_au + amap_remove_cold_au(amap, au); + au->free_clusters++; + amap_add_cold_au(amap, au); + } else + au->free_clusters++; + + + /* Update AMAP info */ + if (au->free_clusters == amap->clusters_per_au) + amap->n_clean_au++; + if (au->free_clusters == 1) + amap->n_full_au--; + + // spin_unlock(&amap->amap_lock); + return 0; +} + + +/* + * Check if the cluster is in a working AU + * The caller should hold sb lock. + * This func. should be used only if smart allocation is on + */ +s32 amap_check_working(struct super_block *sb, u32 clu) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + AU_INFO_T *au; + + BUG_ON(!amap); + au = GET_AU(amap, i_AU_of_CLU(amap, clu)); + return IS_AU_WORKING(au, amap); +} + + +/* + * Return the # of free clusters in that AU + */ +s32 amap_get_freeclus(struct super_block *sb, u32 clu) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + AU_INFO_T *au; + + BUG_ON(!amap); + au = GET_AU(amap, i_AU_of_CLU(amap, clu)); + return (s32)au->free_clusters; +} + + +/* + * Add the AU containing 'clu' to the ignored AU list. + * The AU will not be used by the allocator. + * + * XXX: Ignored counter needed + */ +s32 amap_mark_ignore(struct super_block *sb, u32 clu) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + AU_INFO_T *au; + + BUG_ON(!amap); + au = GET_AU(amap, i_AU_of_CLU(amap, clu)); + + if (IS_AU_HOT(au, amap)) { + /* Doesn't work with hot AUs */ + return -EPERM; + } else if (IS_AU_WORKING(au, amap)) { + return -EBUSY; + } + + //BUG_ON(IS_AU_IGNORED(au, amap) && (GET_IGN_CNT(au) == 0)); + if (IS_AU_IGNORED(au, amap)) + return 0; + + amap_remove_cold_au(amap, au); + amap_insert_to_list(au, &amap->slist_ignored); + + BUG_ON(!IS_AU_IGNORED(au, amap)); + + //INC_IGN_CNT(au); + MMSG("AMAP: Mark ignored AU (%d)\n", au->idx); + return 0; +} + + +/* + * This function could be used only on IGNORED AUs. + * The caller should care whether it's ignored or not before using this func. + */ +s32 amap_unmark_ignore(struct super_block *sb, u32 clu) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + AU_INFO_T *au; + + BUG_ON(!amap); + + au = GET_AU(amap, i_AU_of_CLU(amap, clu)); + + BUG_ON(!IS_AU_IGNORED(au, amap)); + // BUG_ON(GET_IGN_CNT(au) == 0); + + amap_remove_from_list(au, &amap->slist_ignored); + amap_add_cold_au(amap, au); + + BUG_ON(IS_AU_IGNORED(au, amap)); + + //DEC_IGN_CNT(au); + + MMSG("AMAP: Unmark ignored AU (%d)\n", au->idx); + + return 0; +} + +/* + * Unmark all ignored AU + * This will return # of unmarked AUs + */ +s32 amap_unmark_ignore_all(struct super_block *sb) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + struct slist_head *entry; + AU_INFO_T *au; + int n = 0; + + BUG_ON(!amap); + entry = amap->slist_ignored.next; + while (entry) { + au = list_entry(entry, AU_INFO_T, shead); + + BUG_ON(au != GET_AU(amap, au->idx)); + BUG_ON(!IS_AU_IGNORED(au, amap)); + + //CLEAR_IGN_CNT(au); + amap_remove_from_list(au, &amap->slist_ignored); + amap_add_cold_au(amap, au); + + MMSG("AMAP: Unmark ignored AU (%d)\n", au->idx); + n++; + + entry = amap->slist_ignored.next; + } + + BUG_ON(amap->slist_ignored.next != NULL); + MMSG("AMAP: unmark_ignore_all, total %d AUs\n", n); + + return n; +} + +/** + * @fn amap_get_au_stat + * @brief report AUs status depending on mode + * @return positive on success, 0 otherwise + * @param sbi super block info + * @param mode TOTAL, CLEAN and FULL + */ +u32 amap_get_au_stat(struct super_block *sb, s32 mode) +{ + AMAP_T *amap = SDFAT_SB(sb)->fsi.amap; + + if (!amap) + return 0; + + if (mode == VOL_AU_STAT_TOTAL) + return amap->n_au; + else if (mode == VOL_AU_STAT_CLEAN) + return amap->n_clean_au; + else if (mode == VOL_AU_STAT_FULL) + return amap->n_full_au; + + return 0; +} + |