fs/ubifs/shrinker.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * This file is part of UBIFS.
   4  *
   5  * Copyright (C) 2006-2008 Nokia Corporation.
   6  *
   7  * Authors: Artem Bityutskiy (Битюцкий Артём)
   8  *          Adrian Hunter
   9  */
  10
  11 /*
  12  * This file implements UBIFS shrinker which evicts clean znodes from the TNC
  13  * tree when Linux VM needs more RAM.
  14  *
  15  * We do not implement any LRU lists to find oldest znodes to free because it
  16  * would add additional overhead to the file system fast paths. So the shrinker
  17  * just walks the TNC tree when searching for znodes to free.
  18  *
  19  * If the root of a TNC sub-tree is clean and old enough, then the children are
  20  * also clean and old enough. So the shrinker walks the TNC in level order and
  21  * dumps entire sub-trees.
  22  *
  23  * The age of znodes is just the time-stamp when they were last looked at.
  24  * The current shrinker first tries to evict old znodes, then young ones.
  25  *
  26  * Since the shrinker is global, it has to protect against races with FS
  27  * un-mounts, which is done by the 'ubifs_infos_lock' and 'c->umount_mutex'.
  28  */
  29
  30 #include "ubifs.h"
  31
  32 /* List of all UBIFS file-system instances */
  33 LIST_HEAD(ubifs_infos);
  34
  35 /*
  36  * We number each shrinker run and record the number on the ubifs_info structure
  37  * so that we can easily work out which ubifs_info structures have already been
  38  * done by the current run.
  39  */
  40 static unsigned int shrinker_run_no;
  41
  42 /* Protects 'ubifs_infos' list */
  43 DEFINE_SPINLOCK(ubifs_infos_lock);
  44
  45 /* Global clean znode counter (for all mounted UBIFS instances) */
  46 atomic_long_t ubifs_clean_zn_cnt;
  47
  48 /**
  49  * shrink_tnc - shrink TNC tree.
  50  * @c: UBIFS file-system description object
  51  * @nr: number of znodes to free
  52  * @age: the age of znodes to free
  53  * @contention: if any contention, this is set to %1
  54  *
  55  * This function traverses TNC tree and frees clean znodes. It does not free
  56  * clean znodes which younger then @age. Returns number of freed znodes.
  57  */
  58 static int shrink_tnc(struct ubifs_info *c, int nr, int age, int *contention)
  59 {
  60         int total_freed = 0;
  61         struct ubifs_znode *znode, *zprev;
  62         time64_t time = ktime_get_seconds();
  63
  64         ubifs_assert(c, mutex_is_locked(&c->umount_mutex));
  65         ubifs_assert(c, mutex_is_locked(&c->tnc_mutex));
  66
  67         if (!c->zroot.znode || atomic_long_read(&c->clean_zn_cnt) == 0)
  68                 return 0;
  69
  70         /*
  71          * Traverse the TNC tree in levelorder manner, so that it is possible
  72          * to destroy large sub-trees. Indeed, if a znode is old, then all its
  73          * children are older or of the same age.
  74          *
  75          * Note, we are holding 'c->tnc_mutex', so we do not have to lock the
  76          * 'c->space_lock' when _reading_ 'c->clean_zn_cnt', because it is
  77          * changed only when the 'c->tnc_mutex' is held.
  78          */
  79         zprev = NULL;
  80         znode = ubifs_tnc_levelorder_next(c, c->zroot.znode, NULL);
  81         while (znode && total_freed < nr &&
  82                atomic_long_read(&c->clean_zn_cnt) > 0) {
  83                 int freed;
  84
  85                 /*
  86                  * If the znode is clean, but it is in the 'c->cnext' list, this
  87                  * means that this znode has just been written to flash as a
  88                  * part of commit and was marked clean. They will be removed
  89                  * from the list at end commit. We cannot change the list,
  90                  * because it is not protected by any mutex (design decision to
  91                  * make commit really independent and parallel to main I/O). So
  92                  * we just skip these znodes.
  93                  *
  94                  * Note, the 'clean_zn_cnt' counters are not updated until
  95                  * after the commit, so the UBIFS shrinker does not report
  96                  * the znodes which are in the 'c->cnext' list as freeable.
  97                  *
  98                  * Also note, if the root of a sub-tree is not in 'c->cnext',
  99                  * then the whole sub-tree is not in 'c->cnext' as well, so it
 100                  * is safe to dump whole sub-tree.
 101                  */
 102
 103                 if (znode->cnext) {
 104                         /*
 105                          * Very soon these znodes will be removed from the list
 106                          * and become freeable.
 107                          */
 108                         *contention = 1;
 109                 } else if (!ubifs_zn_dirty(znode) &&
 110                            abs(time - znode->time) >= age) {
 111                         if (znode->parent)
 112                                 znode->parent->zbranch[znode->iip].znode = NULL;
 113                         else
 114                                 c->zroot.znode = NULL;
 115
 116                         freed = ubifs_destroy_tnc_subtree(c, znode);
 117                         atomic_long_sub(freed, &ubifs_clean_zn_cnt);
 118                         atomic_long_sub(freed, &c->clean_zn_cnt);
 119                         total_freed += freed;
 120                         znode = zprev;
 121                 }
 122
 123                 if (unlikely(!c->zroot.znode))
 124                         break;
 125
 126                 zprev = znode;
 127                 znode = ubifs_tnc_levelorder_next(c, c->zroot.znode, znode);
 128                 cond_resched();
 129         }
 130
 131         return total_freed;
 132 }
 133
 134 /**
 135  * shrink_tnc_trees - shrink UBIFS TNC trees.
 136  * @nr: number of znodes to free
 137  * @age: the age of znodes to free
 138  * @contention: if any contention, this is set to %1
 139  *
 140  * This function walks the list of mounted UBIFS file-systems and frees clean
 141  * znodes which are older than @age, until at least @nr znodes are freed.
 142  * Returns the number of freed znodes.
 143  */
 144 static int shrink_tnc_trees(int nr, int age, int *contention)
 145 {
 146         struct ubifs_info *c;
 147         struct list_head *p;
 148         unsigned int run_no;
 149         int freed = 0;
 150
 151         spin_lock(&ubifs_infos_lock);
 152         do {
 153                 run_no = ++shrinker_run_no;
 154         } while (run_no == 0);
 155         /* Iterate over all mounted UBIFS file-systems and try to shrink them */
 156         p = ubifs_infos.next;
 157         while (p != &ubifs_infos) {
 158                 c = list_entry(p, struct ubifs_info, infos_list);
 159                 /*
 160                  * We move the ones we do to the end of the list, so we stop
 161                  * when we see one we have already done.
 162                  */
 163                 if (c->shrinker_run_no == run_no)
 164                         break;
 165                 if (!mutex_trylock(&c->umount_mutex)) {
 166                         /* Some un-mount is in progress, try next FS */
 167                         *contention = 1;
 168                         p = p->next;
 169                         continue;
 170                 }
 171                 /*
 172                  * We're holding 'c->umount_mutex', so the file-system won't go
 173                  * away.
 174                  */
 175                 if (!mutex_trylock(&c->tnc_mutex)) {
 176                         mutex_unlock(&c->umount_mutex);
 177                         *contention = 1;
 178                         p = p->next;
 179                         continue;
 180                 }
 181                 spin_unlock(&ubifs_infos_lock);
 182                 /*
 183                  * OK, now we have TNC locked, the file-system cannot go away -
 184                  * it is safe to reap the cache.
 185                  */
 186                 c->shrinker_run_no = run_no;
 187                 freed += shrink_tnc(c, nr, age, contention);
 188                 mutex_unlock(&c->tnc_mutex);
 189                 spin_lock(&ubifs_infos_lock);
 190                 /* Get the next list element before we move this one */
 191                 p = p->next;
 192                 /*
 193                  * Move this one to the end of the list to provide some
 194                  * fairness.
 195                  */
 196                 list_move_tail(&c->infos_list, &ubifs_infos);
 197                 mutex_unlock(&c->umount_mutex);
 198                 if (freed >= nr)
 199                         break;
 200         }
 201         spin_unlock(&ubifs_infos_lock);
 202         return freed;
 203 }
 204
 205 /**
 206  * kick_a_thread - kick a background thread to start commit.
 207  *
 208  * This function kicks a background thread to start background commit. Returns
 209  * %-1 if a thread was kicked or there is another reason to assume the memory
 210  * will soon be freed or become freeable. If there are no dirty znodes, returns
 211  * %0.
 212  */
 213 static int kick_a_thread(void)
 214 {
 215         int i;
 216         struct ubifs_info *c;
 217
 218         /*
 219          * Iterate over all mounted UBIFS file-systems and find out if there is
 220          * already an ongoing commit operation there. If no, then iterate for
 221          * the second time and initiate background commit.
 222          */
 223         spin_lock(&ubifs_infos_lock);
 224         for (i = 0; i < 2; i++) {
 225                 list_for_each_entry(c, &ubifs_infos, infos_list) {
 226                         long dirty_zn_cnt;
 227
 228                         if (!mutex_trylock(&c->umount_mutex)) {
 229                                 /*
 230                                  * Some un-mount is in progress, it will
 231                                  * certainly free memory, so just return.
 232                                  */
 233                                 spin_unlock(&ubifs_infos_lock);
 234                                 return -1;
 235                         }
 236
 237                         dirty_zn_cnt = atomic_long_read(&c->dirty_zn_cnt);
 238
 239                         if (!dirty_zn_cnt || c->cmt_state == COMMIT_BROKEN ||
 240                             c->ro_mount || c->ro_error) {
 241                                 mutex_unlock(&c->umount_mutex);
 242                                 continue;
 243                         }
 244
 245                         if (c->cmt_state != COMMIT_RESTING) {
 246                                 spin_unlock(&ubifs_infos_lock);
 247                                 mutex_unlock(&c->umount_mutex);
 248                                 return -1;
 249                         }
 250
 251                         if (i == 1) {
 252                                 list_move_tail(&c->infos_list, &ubifs_infos);
 253                                 spin_unlock(&ubifs_infos_lock);
 254
 255                                 ubifs_request_bg_commit(c);
 256                                 mutex_unlock(&c->umount_mutex);
 257                                 return -1;
 258                         }
 259                         mutex_unlock(&c->umount_mutex);
 260                 }
 261         }
 262         spin_unlock(&ubifs_infos_lock);
 263
 264         return 0;
 265 }
 266
 267 unsigned long ubifs_shrink_count(struct shrinker *shrink,
 268                                  struct shrink_control *sc)
 269 {
 270         long clean_zn_cnt = atomic_long_read(&ubifs_clean_zn_cnt);
 271
 272         /*
 273          * Due to the way UBIFS updates the clean znode counter it may
 274          * temporarily be negative.
 275          */
 276         return clean_zn_cnt >= 0 ? clean_zn_cnt : 1;
 277 }
 278
 279 unsigned long ubifs_shrink_scan(struct shrinker *shrink,
 280                                 struct shrink_control *sc)
 281 {
 282         unsigned long nr = sc->nr_to_scan;
 283         int contention = 0;
 284         unsigned long freed;
 285         long clean_zn_cnt = atomic_long_read(&ubifs_clean_zn_cnt);
 286
 287         if (!clean_zn_cnt) {
 288                 /*
 289                  * No clean znodes, nothing to reap. All we can do in this case
 290                  * is to kick background threads to start commit, which will
 291                  * probably make clean znodes which, in turn, will be freeable.
 292                  * And we return -1 which means will make VM call us again
 293                  * later.
 294                  */
 295                 dbg_tnc("no clean znodes, kick a thread");
 296                 return kick_a_thread();
 297         }
 298
 299         freed = shrink_tnc_trees(nr, OLD_ZNODE_AGE, &contention);
 300         if (freed >= nr)
 301                 goto out;
 302
 303         dbg_tnc("not enough old znodes, try to free young ones");
 304         freed += shrink_tnc_trees(nr - freed, YOUNG_ZNODE_AGE, &contention);
 305         if (freed >= nr)
 306                 goto out;
 307
 308         dbg_tnc("not enough young znodes, free all");
 309         freed += shrink_tnc_trees(nr - freed, 0, &contention);
 310
 311         if (!freed && contention) {
 312                 dbg_tnc("freed nothing, but contention");
 313                 return SHRINK_STOP;
 314         }
 315
 316 out:
 317         dbg_tnc("%lu znodes were freed, requested %lu", freed, nr);
 318         return freed;
 319 }