| 1 | |
| 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 |
|
| 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 |
|
| 43 | DEFINE_SPINLOCK(ubifs_infos_lock);
|
| 44 |
|
| 45 |
|
| 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 |
|
| 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 |
|
| 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 |
|
| 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 | }
|