diff options
Diffstat (limited to 'ANDROID_3.4.5/fs/ubifs/shrinker.c')
| -rw-r--r-- | ANDROID_3.4.5/fs/ubifs/shrinker.c | 325 |
1 files changed, 0 insertions, 325 deletions
diff --git a/ANDROID_3.4.5/fs/ubifs/shrinker.c b/ANDROID_3.4.5/fs/ubifs/shrinker.c deleted file mode 100644 index 9e1d0566..00000000 --- a/ANDROID_3.4.5/fs/ubifs/shrinker.c +++ /dev/null @@ -1,325 +0,0 @@ -/* - * This file is part of UBIFS. - * - * Copyright (C) 2006-2008 Nokia Corporation. - * - * This program is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 as published by - * the Free Software Foundation. - * - * 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, write to the Free Software Foundation, Inc., 51 - * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - * - * Authors: Artem Bityutskiy (Битюцкий Артём) - * Adrian Hunter - */ - -/* - * This file implements UBIFS shrinker which evicts clean znodes from the TNC - * tree when Linux VM needs more RAM. - * - * We do not implement any LRU lists to find oldest znodes to free because it - * would add additional overhead to the file system fast paths. So the shrinker - * just walks the TNC tree when searching for znodes to free. - * - * If the root of a TNC sub-tree is clean and old enough, then the children are - * also clean and old enough. So the shrinker walks the TNC in level order and - * dumps entire sub-trees. - * - * The age of znodes is just the time-stamp when they were last looked at. - * The current shrinker first tries to evict old znodes, then young ones. - * - * Since the shrinker is global, it has to protect against races with FS - * un-mounts, which is done by the 'ubifs_infos_lock' and 'c->umount_mutex'. - */ - -#include "ubifs.h" - -/* List of all UBIFS file-system instances */ -LIST_HEAD(ubifs_infos); - -/* - * We number each shrinker run and record the number on the ubifs_info structure - * so that we can easily work out which ubifs_info structures have already been - * done by the current run. - */ -static unsigned int shrinker_run_no; - -/* Protects 'ubifs_infos' list */ -DEFINE_SPINLOCK(ubifs_infos_lock); - -/* Global clean znode counter (for all mounted UBIFS instances) */ -atomic_long_t ubifs_clean_zn_cnt; - -/** - * shrink_tnc - shrink TNC tree. - * @c: UBIFS file-system description object - * @nr: number of znodes to free - * @age: the age of znodes to free - * @contention: if any contention, this is set to %1 - * - * This function traverses TNC tree and frees clean znodes. It does not free - * clean znodes which younger then @age. Returns number of freed znodes. - */ -static int shrink_tnc(struct ubifs_info *c, int nr, int age, int *contention) -{ - int total_freed = 0; - struct ubifs_znode *znode, *zprev; - int time = get_seconds(); - - ubifs_assert(mutex_is_locked(&c->umount_mutex)); - ubifs_assert(mutex_is_locked(&c->tnc_mutex)); - - if (!c->zroot.znode || atomic_long_read(&c->clean_zn_cnt) == 0) - return 0; - - /* - * Traverse the TNC tree in levelorder manner, so that it is possible - * to destroy large sub-trees. Indeed, if a znode is old, then all its - * children are older or of the same age. - * - * Note, we are holding 'c->tnc_mutex', so we do not have to lock the - * 'c->space_lock' when _reading_ 'c->clean_zn_cnt', because it is - * changed only when the 'c->tnc_mutex' is held. - */ - zprev = NULL; - znode = ubifs_tnc_levelorder_next(c->zroot.znode, NULL); - while (znode && total_freed < nr && - atomic_long_read(&c->clean_zn_cnt) > 0) { - int freed; - - /* - * If the znode is clean, but it is in the 'c->cnext' list, this - * means that this znode has just been written to flash as a - * part of commit and was marked clean. They will be removed - * from the list at end commit. We cannot change the list, - * because it is not protected by any mutex (design decision to - * make commit really independent and parallel to main I/O). So - * we just skip these znodes. - * - * Note, the 'clean_zn_cnt' counters are not updated until - * after the commit, so the UBIFS shrinker does not report - * the znodes which are in the 'c->cnext' list as freeable. - * - * Also note, if the root of a sub-tree is not in 'c->cnext', - * then the whole sub-tree is not in 'c->cnext' as well, so it - * is safe to dump whole sub-tree. - */ - - if (znode->cnext) { - /* - * Very soon these znodes will be removed from the list - * and become freeable. - */ - *contention = 1; - } else if (!ubifs_zn_dirty(znode) && - abs(time - znode->time) >= age) { - if (znode->parent) - znode->parent->zbranch[znode->iip].znode = NULL; - else - c->zroot.znode = NULL; - - freed = ubifs_destroy_tnc_subtree(znode); - atomic_long_sub(freed, &ubifs_clean_zn_cnt); - atomic_long_sub(freed, &c->clean_zn_cnt); - ubifs_assert(atomic_long_read(&c->clean_zn_cnt) >= 0); - total_freed += freed; - znode = zprev; - } - - if (unlikely(!c->zroot.znode)) - break; - - zprev = znode; - znode = ubifs_tnc_levelorder_next(c->zroot.znode, znode); - cond_resched(); - } - - return total_freed; -} - -/** - * shrink_tnc_trees - shrink UBIFS TNC trees. - * @nr: number of znodes to free - * @age: the age of znodes to free - * @contention: if any contention, this is set to %1 - * - * This function walks the list of mounted UBIFS file-systems and frees clean - * znodes which are older than @age, until at least @nr znodes are freed. - * Returns the number of freed znodes. - */ -static int shrink_tnc_trees(int nr, int age, int *contention) -{ - struct ubifs_info *c; - struct list_head *p; - unsigned int run_no; - int freed = 0; - - spin_lock(&ubifs_infos_lock); - do { - run_no = ++shrinker_run_no; - } while (run_no == 0); - /* Iterate over all mounted UBIFS file-systems and try to shrink them */ - p = ubifs_infos.next; - while (p != &ubifs_infos) { - c = list_entry(p, struct ubifs_info, infos_list); - /* - * We move the ones we do to the end of the list, so we stop - * when we see one we have already done. - */ - if (c->shrinker_run_no == run_no) - break; - if (!mutex_trylock(&c->umount_mutex)) { - /* Some un-mount is in progress, try next FS */ - *contention = 1; - p = p->next; - continue; - } - /* - * We're holding 'c->umount_mutex', so the file-system won't go - * away. - */ - if (!mutex_trylock(&c->tnc_mutex)) { - mutex_unlock(&c->umount_mutex); - *contention = 1; - p = p->next; - continue; - } - spin_unlock(&ubifs_infos_lock); - /* - * OK, now we have TNC locked, the file-system cannot go away - - * it is safe to reap the cache. - */ - c->shrinker_run_no = run_no; - freed += shrink_tnc(c, nr, age, contention); - mutex_unlock(&c->tnc_mutex); - spin_lock(&ubifs_infos_lock); - /* Get the next list element before we move this one */ - p = p->next; - /* - * Move this one to the end of the list to provide some - * fairness. - */ - list_move_tail(&c->infos_list, &ubifs_infos); - mutex_unlock(&c->umount_mutex); - if (freed >= nr) - break; - } - spin_unlock(&ubifs_infos_lock); - return freed; -} - -/** - * kick_a_thread - kick a background thread to start commit. - * - * This function kicks a background thread to start background commit. Returns - * %-1 if a thread was kicked or there is another reason to assume the memory - * will soon be freed or become freeable. If there are no dirty znodes, returns - * %0. - */ -static int kick_a_thread(void) -{ - int i; - struct ubifs_info *c; - - /* - * Iterate over all mounted UBIFS file-systems and find out if there is - * already an ongoing commit operation there. If no, then iterate for - * the second time and initiate background commit. - */ - spin_lock(&ubifs_infos_lock); - for (i = 0; i < 2; i++) { - list_for_each_entry(c, &ubifs_infos, infos_list) { - long dirty_zn_cnt; - - if (!mutex_trylock(&c->umount_mutex)) { - /* - * Some un-mount is in progress, it will - * certainly free memory, so just return. - */ - spin_unlock(&ubifs_infos_lock); - return -1; - } - - dirty_zn_cnt = atomic_long_read(&c->dirty_zn_cnt); - - if (!dirty_zn_cnt || c->cmt_state == COMMIT_BROKEN || - c->ro_mount || c->ro_error) { - mutex_unlock(&c->umount_mutex); - continue; - } - - if (c->cmt_state != COMMIT_RESTING) { - spin_unlock(&ubifs_infos_lock); - mutex_unlock(&c->umount_mutex); - return -1; - } - - if (i == 1) { - list_move_tail(&c->infos_list, &ubifs_infos); - spin_unlock(&ubifs_infos_lock); - - ubifs_request_bg_commit(c); - mutex_unlock(&c->umount_mutex); - return -1; - } - mutex_unlock(&c->umount_mutex); - } - } - spin_unlock(&ubifs_infos_lock); - - return 0; -} - -int ubifs_shrinker(struct shrinker *shrink, struct shrink_control *sc) -{ - int nr = sc->nr_to_scan; - int freed, contention = 0; - long clean_zn_cnt = atomic_long_read(&ubifs_clean_zn_cnt); - - if (nr == 0) - /* - * Due to the way UBIFS updates the clean znode counter it may - * temporarily be negative. - */ - return clean_zn_cnt >= 0 ? clean_zn_cnt : 1; - - if (!clean_zn_cnt) { - /* - * No clean znodes, nothing to reap. All we can do in this case - * is to kick background threads to start commit, which will - * probably make clean znodes which, in turn, will be freeable. - * And we return -1 which means will make VM call us again - * later. - */ - dbg_tnc("no clean znodes, kick a thread"); - return kick_a_thread(); - } - - freed = shrink_tnc_trees(nr, OLD_ZNODE_AGE, &contention); - if (freed >= nr) - goto out; - - dbg_tnc("not enough old znodes, try to free young ones"); - freed += shrink_tnc_trees(nr - freed, YOUNG_ZNODE_AGE, &contention); - if (freed >= nr) - goto out; - - dbg_tnc("not enough young znodes, free all"); - freed += shrink_tnc_trees(nr - freed, 0, &contention); - - if (!freed && contention) { - dbg_tnc("freed nothing, but contention"); - return -1; - } - -out: - dbg_tnc("%d znodes were freed, requested %d", freed, nr); - return freed; -} |