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 } 320