1 /* 2 * This file is part of UBIFS. 3 * 4 * Copyright (C) 2006-2008 Nokia Corporation. 5 * 6 * This program is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 as published by 8 * the Free Software Foundation. 9 * 10 * This program is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 13 * more details. 14 * 15 * You should have received a copy of the GNU General Public License along with 16 * this program; if not, write to the Free Software Foundation, Inc., 51 17 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 18 * 19 * Author: Adrian Hunter 20 */ 21 22 #include "ubifs.h" 23 24 /* 25 * An orphan is an inode number whose inode node has been committed to the index 26 * with a link count of zero. That happens when an open file is deleted 27 * (unlinked) and then a commit is run. In the normal course of events the inode 28 * would be deleted when the file is closed. However in the case of an unclean 29 * unmount, orphans need to be accounted for. After an unclean unmount, the 30 * orphans' inodes must be deleted which means either scanning the entire index 31 * looking for them, or keeping a list on flash somewhere. This unit implements 32 * the latter approach. 33 * 34 * The orphan area is a fixed number of LEBs situated between the LPT area and 35 * the main area. The number of orphan area LEBs is specified when the file 36 * system is created. The minimum number is 1. The size of the orphan area 37 * should be so that it can hold the maximum number of orphans that are expected 38 * to ever exist at one time. 39 * 40 * The number of orphans that can fit in a LEB is: 41 * 42 * (c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64) 43 * 44 * For example: a 15872 byte LEB can fit 1980 orphans so 1 LEB may be enough. 45 * 46 * Orphans are accumulated in a rb-tree. When an inode's link count drops to 47 * zero, the inode number is added to the rb-tree. It is removed from the tree 48 * when the inode is deleted. Any new orphans that are in the orphan tree when 49 * the commit is run, are written to the orphan area in 1 or more orphan nodes. 50 * If the orphan area is full, it is consolidated to make space. There is 51 * always enough space because validation prevents the user from creating more 52 * than the maximum number of orphans allowed. 53 */ 54 55 /** 56 * tot_avail_orphs - calculate total space. 57 * @c: UBIFS file-system description object 58 * 59 * This function returns the number of orphans that can be written in half 60 * the total space. That leaves half the space for adding new orphans. 61 */ 62 static int tot_avail_orphs(struct ubifs_info *c) 63 { 64 int avail_lebs, avail; 65 66 avail_lebs = c->orph_lebs; 67 avail = avail_lebs * 68 ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)); 69 return avail / 2; 70 } 71 72 /** 73 * ubifs_clear_orphans - erase all LEBs used for orphans. 74 * @c: UBIFS file-system description object 75 * 76 * If recovery is not required, then the orphans from the previous session 77 * are not needed. This function locates the LEBs used to record 78 * orphans, and un-maps them. 79 */ 80 int ubifs_clear_orphans(struct ubifs_info *c) 81 { 82 int lnum, err; 83 84 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { 85 err = ubifs_leb_unmap(c, lnum); 86 if (err) 87 return err; 88 } 89 c->ohead_lnum = c->orph_first; 90 c->ohead_offs = 0; 91 return 0; 92 } 93 94 /** 95 * insert_dead_orphan - insert an orphan. 96 * @c: UBIFS file-system description object 97 * @inum: orphan inode number 98 * 99 * This function is a helper to the 'do_kill_orphans()' function. The orphan 100 * must be kept until the next commit, so it is added to the rb-tree and the 101 * deletion list. 102 */ 103 static int insert_dead_orphan(struct ubifs_info *c, ino_t inum) 104 { 105 struct ubifs_orphan *orphan, *o; 106 struct rb_node **p, *parent = NULL; 107 108 orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_KERNEL); 109 if (!orphan) 110 return -ENOMEM; 111 orphan->inum = inum; 112 113 p = &c->orph_tree.rb_node; 114 while (*p) { 115 parent = *p; 116 o = rb_entry(parent, struct ubifs_orphan, rb); 117 if (inum < o->inum) 118 p = &(*p)->rb_left; 119 else if (inum > o->inum) 120 p = &(*p)->rb_right; 121 else { 122 /* Already added - no problem */ 123 kfree(orphan); 124 return 0; 125 } 126 } 127 c->tot_orphans += 1; 128 rb_link_node(&orphan->rb, parent, p); 129 rb_insert_color(&orphan->rb, &c->orph_tree); 130 list_add_tail(&orphan->list, &c->orph_list); 131 orphan->dnext = c->orph_dnext; 132 c->orph_dnext = orphan; 133 dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum, 134 c->new_orphans, c->tot_orphans); 135 return 0; 136 } 137 138 /** 139 * do_kill_orphans - remove orphan inodes from the index. 140 * @c: UBIFS file-system description object 141 * @sleb: scanned LEB 142 * @last_cmt_no: cmt_no of last orphan node read is passed and returned here 143 * @outofdate: whether the LEB is out of date is returned here 144 * @last_flagged: whether the end orphan node is encountered 145 * 146 * This function is a helper to the 'kill_orphans()' function. It goes through 147 * every orphan node in a LEB and for every inode number recorded, removes 148 * all keys for that inode from the TNC. 149 */ 150 static int do_kill_orphans(struct ubifs_info *c, struct ubifs_scan_leb *sleb, 151 unsigned long long *last_cmt_no, int *outofdate, 152 int *last_flagged) 153 { 154 struct ubifs_scan_node *snod; 155 struct ubifs_orph_node *orph; 156 unsigned long long cmt_no; 157 ino_t inum; 158 int i, n, err, first = 1; 159 160 list_for_each_entry(snod, &sleb->nodes, list) { 161 if (snod->type != UBIFS_ORPH_NODE) { 162 ubifs_err("invalid node type %d in orphan area at " 163 "%d:%d", snod->type, sleb->lnum, snod->offs); 164 dbg_dump_node(c, snod->node); 165 return -EINVAL; 166 } 167 168 orph = snod->node; 169 170 /* Check commit number */ 171 cmt_no = le64_to_cpu(orph->cmt_no) & LLONG_MAX; 172 /* 173 * The commit number on the master node may be less, because 174 * of a failed commit. If there are several failed commits in a 175 * row, the commit number written on orphan nodes will continue 176 * to increase (because the commit number is adjusted here) even 177 * though the commit number on the master node stays the same 178 * because the master node has not been re-written. 179 */ 180 if (cmt_no > c->cmt_no) 181 c->cmt_no = cmt_no; 182 if (cmt_no < *last_cmt_no && *last_flagged) { 183 /* 184 * The last orphan node had a higher commit number and 185 * was flagged as the last written for that commit 186 * number. That makes this orphan node, out of date. 187 */ 188 if (!first) { 189 ubifs_err("out of order commit number %llu in " 190 "orphan node at %d:%d", 191 cmt_no, sleb->lnum, snod->offs); 192 dbg_dump_node(c, snod->node); 193 return -EINVAL; 194 } 195 dbg_rcvry("out of date LEB %d", sleb->lnum); 196 *outofdate = 1; 197 return 0; 198 } 199 200 if (first) 201 first = 0; 202 203 n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3; 204 for (i = 0; i < n; i++) { 205 inum = le64_to_cpu(orph->inos[i]); 206 dbg_rcvry("deleting orphaned inode %lu", 207 (unsigned long)inum); 208 err = ubifs_tnc_remove_ino(c, inum); 209 if (err) 210 return err; 211 err = insert_dead_orphan(c, inum); 212 if (err) 213 return err; 214 } 215 216 *last_cmt_no = cmt_no; 217 if (le64_to_cpu(orph->cmt_no) & (1ULL << 63)) { 218 dbg_rcvry("last orph node for commit %llu at %d:%d", 219 cmt_no, sleb->lnum, snod->offs); 220 *last_flagged = 1; 221 } else 222 *last_flagged = 0; 223 } 224 225 return 0; 226 } 227 228 /** 229 * kill_orphans - remove all orphan inodes from the index. 230 * @c: UBIFS file-system description object 231 * 232 * If recovery is required, then orphan inodes recorded during the previous 233 * session (which ended with an unclean unmount) must be deleted from the index. 234 * This is done by updating the TNC, but since the index is not updated until 235 * the next commit, the LEBs where the orphan information is recorded are not 236 * erased until the next commit. 237 */ 238 static int kill_orphans(struct ubifs_info *c) 239 { 240 unsigned long long last_cmt_no = 0; 241 int lnum, err = 0, outofdate = 0, last_flagged = 0; 242 243 c->ohead_lnum = c->orph_first; 244 c->ohead_offs = 0; 245 /* Check no-orphans flag and skip this if no orphans */ 246 if (c->no_orphs) { 247 dbg_rcvry("no orphans"); 248 return 0; 249 } 250 /* 251 * Orph nodes always start at c->orph_first and are written to each 252 * successive LEB in turn. Generally unused LEBs will have been unmapped 253 * but may contain out of date orphan nodes if the unmap didn't go 254 * through. In addition, the last orphan node written for each commit is 255 * marked (top bit of orph->cmt_no is set to 1). It is possible that 256 * there are orphan nodes from the next commit (i.e. the commit did not 257 * complete successfully). In that case, no orphans will have been lost 258 * due to the way that orphans are written, and any orphans added will 259 * be valid orphans anyway and so can be deleted. 260 */ 261 for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { 262 struct ubifs_scan_leb *sleb; 263 264 dbg_rcvry("LEB %d", lnum); 265 sleb = ubifs_scan(c, lnum, 0, c->sbuf); 266 if (IS_ERR(sleb)) { 267 sleb = ubifs_recover_leb(c, lnum, 0, c->sbuf, 0); 268 if (IS_ERR(sleb)) { 269 err = PTR_ERR(sleb); 270 break; 271 } 272 } 273 err = do_kill_orphans(c, sleb, &last_cmt_no, &outofdate, 274 &last_flagged); 275 if (err || outofdate) { 276 ubifs_scan_destroy(sleb); 277 break; 278 } 279 if (sleb->endpt) { 280 c->ohead_lnum = lnum; 281 c->ohead_offs = sleb->endpt; 282 } 283 ubifs_scan_destroy(sleb); 284 } 285 return err; 286 } 287 288 /** 289 * ubifs_mount_orphans - delete orphan inodes and erase LEBs that recorded them. 290 * @c: UBIFS file-system description object 291 * @unclean: indicates recovery from unclean unmount 292 * @read_only: indicates read only mount 293 * 294 * This function is called when mounting to erase orphans from the previous 295 * session. If UBIFS was not unmounted cleanly, then the inodes recorded as 296 * orphans are deleted. 297 */ 298 int ubifs_mount_orphans(struct ubifs_info *c, int unclean, int read_only) 299 { 300 int err = 0; 301 302 c->max_orphans = tot_avail_orphs(c); 303 304 if (!read_only) { 305 c->orph_buf = vmalloc(c->leb_size); 306 if (!c->orph_buf) 307 return -ENOMEM; 308 } 309 310 if (unclean) 311 err = kill_orphans(c); 312 else if (!read_only) 313 err = ubifs_clear_orphans(c); 314 315 return err; 316 } 317