| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 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 |  * Authors: Artem Bityutskiy (Битюцкий Артём) | 
 | 20 |  *          Adrian Hunter | 
 | 21 |  */ | 
 | 22 |  | 
 | 23 | /* | 
 | 24 |  * This file is a part of UBIFS journal implementation and contains various | 
 | 25 |  * functions which manipulate the log. The log is a fixed area on the flash | 
 | 26 |  * which does not contain any data but refers to buds. The log is a part of the | 
 | 27 |  * journal. | 
 | 28 |  */ | 
 | 29 |  | 
 | 30 | #include "ubifs.h" | 
 | 31 |  | 
 | 32 | #ifdef CONFIG_UBIFS_FS_DEBUG | 
 | 33 | static int dbg_check_bud_bytes(struct ubifs_info *c); | 
 | 34 | #else | 
 | 35 | #define dbg_check_bud_bytes(c) 0 | 
 | 36 | #endif | 
 | 37 |  | 
 | 38 | /** | 
 | 39 |  * ubifs_search_bud - search bud LEB. | 
 | 40 |  * @c: UBIFS file-system description object | 
 | 41 |  * @lnum: logical eraseblock number to search | 
 | 42 |  * | 
 | 43 |  * This function searches bud LEB @lnum. Returns bud description object in case | 
 | 44 |  * of success and %NULL if there is no bud with this LEB number. | 
 | 45 |  */ | 
 | 46 | struct ubifs_bud *ubifs_search_bud(struct ubifs_info *c, int lnum) | 
 | 47 | { | 
 | 48 | 	struct rb_node *p; | 
 | 49 | 	struct ubifs_bud *bud; | 
 | 50 |  | 
 | 51 | 	spin_lock(&c->buds_lock); | 
 | 52 | 	p = c->buds.rb_node; | 
 | 53 | 	while (p) { | 
 | 54 | 		bud = rb_entry(p, struct ubifs_bud, rb); | 
 | 55 | 		if (lnum < bud->lnum) | 
 | 56 | 			p = p->rb_left; | 
 | 57 | 		else if (lnum > bud->lnum) | 
 | 58 | 			p = p->rb_right; | 
 | 59 | 		else { | 
 | 60 | 			spin_unlock(&c->buds_lock); | 
 | 61 | 			return bud; | 
 | 62 | 		} | 
 | 63 | 	} | 
 | 64 | 	spin_unlock(&c->buds_lock); | 
 | 65 | 	return NULL; | 
 | 66 | } | 
 | 67 |  | 
 | 68 | /** | 
 | 69 |  * ubifs_get_wbuf - get the wbuf associated with a LEB, if there is one. | 
 | 70 |  * @c: UBIFS file-system description object | 
 | 71 |  * @lnum: logical eraseblock number to search | 
 | 72 |  * | 
 | 73 |  * This functions returns the wbuf for @lnum or %NULL if there is not one. | 
 | 74 |  */ | 
 | 75 | struct ubifs_wbuf *ubifs_get_wbuf(struct ubifs_info *c, int lnum) | 
 | 76 | { | 
 | 77 | 	struct rb_node *p; | 
 | 78 | 	struct ubifs_bud *bud; | 
 | 79 | 	int jhead; | 
 | 80 |  | 
 | 81 | 	if (!c->jheads) | 
 | 82 | 		return NULL; | 
 | 83 |  | 
 | 84 | 	spin_lock(&c->buds_lock); | 
 | 85 | 	p = c->buds.rb_node; | 
 | 86 | 	while (p) { | 
 | 87 | 		bud = rb_entry(p, struct ubifs_bud, rb); | 
 | 88 | 		if (lnum < bud->lnum) | 
 | 89 | 			p = p->rb_left; | 
 | 90 | 		else if (lnum > bud->lnum) | 
 | 91 | 			p = p->rb_right; | 
 | 92 | 		else { | 
 | 93 | 			jhead = bud->jhead; | 
 | 94 | 			spin_unlock(&c->buds_lock); | 
 | 95 | 			return &c->jheads[jhead].wbuf; | 
 | 96 | 		} | 
 | 97 | 	} | 
 | 98 | 	spin_unlock(&c->buds_lock); | 
 | 99 | 	return NULL; | 
 | 100 | } | 
 | 101 |  | 
 | 102 | /** | 
 | 103 |  * next_log_lnum - switch to the next log LEB. | 
 | 104 |  * @c: UBIFS file-system description object | 
 | 105 |  * @lnum: current log LEB | 
 | 106 |  */ | 
 | 107 | static inline int next_log_lnum(const struct ubifs_info *c, int lnum) | 
 | 108 | { | 
 | 109 | 	lnum += 1; | 
 | 110 | 	if (lnum > c->log_last) | 
 | 111 | 		lnum = UBIFS_LOG_LNUM; | 
 | 112 |  | 
 | 113 | 	return lnum; | 
 | 114 | } | 
 | 115 |  | 
 | 116 | /** | 
 | 117 |  * empty_log_bytes - calculate amount of empty space in the log. | 
 | 118 |  * @c: UBIFS file-system description object | 
 | 119 |  */ | 
 | 120 | static inline long long empty_log_bytes(const struct ubifs_info *c) | 
 | 121 | { | 
 | 122 | 	long long h, t; | 
 | 123 |  | 
 | 124 | 	h = (long long)c->lhead_lnum * c->leb_size + c->lhead_offs; | 
 | 125 | 	t = (long long)c->ltail_lnum * c->leb_size; | 
 | 126 |  | 
 | 127 | 	if (h >= t) | 
 | 128 | 		return c->log_bytes - h + t; | 
 | 129 | 	else | 
 | 130 | 		return t - h; | 
 | 131 | } | 
 | 132 |  | 
 | 133 | /** | 
 | 134 |  * ubifs_add_bud - add bud LEB to the tree of buds and its journal head list. | 
 | 135 |  * @c: UBIFS file-system description object | 
 | 136 |  * @bud: the bud to add | 
 | 137 |  */ | 
 | 138 | void ubifs_add_bud(struct ubifs_info *c, struct ubifs_bud *bud) | 
 | 139 | { | 
 | 140 | 	struct rb_node **p, *parent = NULL; | 
 | 141 | 	struct ubifs_bud *b; | 
 | 142 | 	struct ubifs_jhead *jhead; | 
 | 143 |  | 
 | 144 | 	spin_lock(&c->buds_lock); | 
 | 145 | 	p = &c->buds.rb_node; | 
 | 146 | 	while (*p) { | 
 | 147 | 		parent = *p; | 
 | 148 | 		b = rb_entry(parent, struct ubifs_bud, rb); | 
 | 149 | 		ubifs_assert(bud->lnum != b->lnum); | 
 | 150 | 		if (bud->lnum < b->lnum) | 
 | 151 | 			p = &(*p)->rb_left; | 
 | 152 | 		else | 
 | 153 | 			p = &(*p)->rb_right; | 
 | 154 | 	} | 
 | 155 |  | 
 | 156 | 	rb_link_node(&bud->rb, parent, p); | 
 | 157 | 	rb_insert_color(&bud->rb, &c->buds); | 
 | 158 | 	if (c->jheads) { | 
 | 159 | 		jhead = &c->jheads[bud->jhead]; | 
 | 160 | 		list_add_tail(&bud->list, &jhead->buds_list); | 
 | 161 | 	} else | 
| Artem Bityutskiy | 2ef1329 | 2010-09-19 18:34:26 +0300 | [diff] [blame] | 162 | 		ubifs_assert(c->replaying && c->ro_mount); | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 163 |  | 
 | 164 | 	/* | 
 | 165 | 	 * Note, although this is a new bud, we anyway account this space now, | 
 | 166 | 	 * before any data has been written to it, because this is about to | 
 | 167 | 	 * guarantee fixed mount time, and this bud will anyway be read and | 
 | 168 | 	 * scanned. | 
 | 169 | 	 */ | 
 | 170 | 	c->bud_bytes += c->leb_size - bud->start; | 
 | 171 |  | 
| Artem Bityutskiy | 77a7ae5 | 2009-09-15 15:03:51 +0300 | [diff] [blame] | 172 | 	dbg_log("LEB %d:%d, jhead %s, bud_bytes %lld", bud->lnum, | 
 | 173 | 		bud->start, dbg_jhead(bud->jhead), c->bud_bytes); | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 174 | 	spin_unlock(&c->buds_lock); | 
 | 175 | } | 
 | 176 |  | 
 | 177 | /** | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 178 |  * ubifs_add_bud_to_log - add a new bud to the log. | 
 | 179 |  * @c: UBIFS file-system description object | 
 | 180 |  * @jhead: journal head the bud belongs to | 
 | 181 |  * @lnum: LEB number of the bud | 
 | 182 |  * @offs: starting offset of the bud | 
 | 183 |  * | 
 | 184 |  * This function writes reference node for the new bud LEB @lnum it to the log, | 
 | 185 |  * and adds it to the buds tress. It also makes sure that log size does not | 
 | 186 |  * exceed the 'c->max_bud_bytes' limit. Returns zero in case of success, | 
 | 187 |  * %-EAGAIN if commit is required, and a negative error codes in case of | 
 | 188 |  * failure. | 
 | 189 |  */ | 
 | 190 | int ubifs_add_bud_to_log(struct ubifs_info *c, int jhead, int lnum, int offs) | 
 | 191 | { | 
 | 192 | 	int err; | 
 | 193 | 	struct ubifs_bud *bud; | 
 | 194 | 	struct ubifs_ref_node *ref; | 
 | 195 |  | 
 | 196 | 	bud = kmalloc(sizeof(struct ubifs_bud), GFP_NOFS); | 
 | 197 | 	if (!bud) | 
 | 198 | 		return -ENOMEM; | 
 | 199 | 	ref = kzalloc(c->ref_node_alsz, GFP_NOFS); | 
 | 200 | 	if (!ref) { | 
 | 201 | 		kfree(bud); | 
 | 202 | 		return -ENOMEM; | 
 | 203 | 	} | 
 | 204 |  | 
 | 205 | 	mutex_lock(&c->log_mutex); | 
| Artem Bityutskiy | 2ef1329 | 2010-09-19 18:34:26 +0300 | [diff] [blame] | 206 | 	ubifs_assert(!c->ro_media && !c->ro_mount); | 
| Artem Bityutskiy | 2680d72 | 2010-09-17 16:44:28 +0300 | [diff] [blame] | 207 | 	if (c->ro_error) { | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 208 | 		err = -EROFS; | 
 | 209 | 		goto out_unlock; | 
 | 210 | 	} | 
 | 211 |  | 
 | 212 | 	/* Make sure we have enough space in the log */ | 
 | 213 | 	if (empty_log_bytes(c) - c->ref_node_alsz < c->min_log_bytes) { | 
 | 214 | 		dbg_log("not enough log space - %lld, required %d", | 
 | 215 | 			empty_log_bytes(c), c->min_log_bytes); | 
 | 216 | 		ubifs_commit_required(c); | 
 | 217 | 		err = -EAGAIN; | 
 | 218 | 		goto out_unlock; | 
 | 219 | 	} | 
 | 220 |  | 
 | 221 | 	/* | 
| Artem Bityutskiy | 7d4e9cc | 2009-03-20 19:11:12 +0200 | [diff] [blame] | 222 | 	 * Make sure the amount of space in buds will not exceed the | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 223 | 	 * 'c->max_bud_bytes' limit, because we want to guarantee mount time | 
 | 224 | 	 * limits. | 
 | 225 | 	 * | 
 | 226 | 	 * It is not necessary to hold @c->buds_lock when reading @c->bud_bytes | 
 | 227 | 	 * because we are holding @c->log_mutex. All @c->bud_bytes take place | 
 | 228 | 	 * when both @c->log_mutex and @c->bud_bytes are locked. | 
 | 229 | 	 */ | 
 | 230 | 	if (c->bud_bytes + c->leb_size - offs > c->max_bud_bytes) { | 
 | 231 | 		dbg_log("bud bytes %lld (%lld max), require commit", | 
 | 232 | 			c->bud_bytes, c->max_bud_bytes); | 
 | 233 | 		ubifs_commit_required(c); | 
 | 234 | 		err = -EAGAIN; | 
 | 235 | 		goto out_unlock; | 
 | 236 | 	} | 
 | 237 |  | 
 | 238 | 	/* | 
 | 239 | 	 * If the journal is full enough - start background commit. Note, it is | 
 | 240 | 	 * OK to read 'c->cmt_state' without spinlock because integer reads | 
 | 241 | 	 * are atomic in the kernel. | 
 | 242 | 	 */ | 
 | 243 | 	if (c->bud_bytes >= c->bg_bud_bytes && | 
 | 244 | 	    c->cmt_state == COMMIT_RESTING) { | 
 | 245 | 		dbg_log("bud bytes %lld (%lld max), initiate BG commit", | 
 | 246 | 			c->bud_bytes, c->max_bud_bytes); | 
 | 247 | 		ubifs_request_bg_commit(c); | 
 | 248 | 	} | 
 | 249 |  | 
 | 250 | 	bud->lnum = lnum; | 
 | 251 | 	bud->start = offs; | 
 | 252 | 	bud->jhead = jhead; | 
 | 253 |  | 
 | 254 | 	ref->ch.node_type = UBIFS_REF_NODE; | 
 | 255 | 	ref->lnum = cpu_to_le32(bud->lnum); | 
 | 256 | 	ref->offs = cpu_to_le32(bud->start); | 
 | 257 | 	ref->jhead = cpu_to_le32(jhead); | 
 | 258 |  | 
 | 259 | 	if (c->lhead_offs > c->leb_size - c->ref_node_alsz) { | 
 | 260 | 		c->lhead_lnum = next_log_lnum(c, c->lhead_lnum); | 
 | 261 | 		c->lhead_offs = 0; | 
 | 262 | 	} | 
 | 263 |  | 
 | 264 | 	if (c->lhead_offs == 0) { | 
 | 265 | 		/* Must ensure next log LEB has been unmapped */ | 
 | 266 | 		err = ubifs_leb_unmap(c, c->lhead_lnum); | 
 | 267 | 		if (err) | 
 | 268 | 			goto out_unlock; | 
 | 269 | 	} | 
 | 270 |  | 
 | 271 | 	if (bud->start == 0) { | 
 | 272 | 		/* | 
 | 273 | 		 * Before writing the LEB reference which refers an empty LEB | 
 | 274 | 		 * to the log, we have to make sure it is mapped, because | 
 | 275 | 		 * otherwise we'd risk to refer an LEB with garbage in case of | 
 | 276 | 		 * an unclean reboot, because the target LEB might have been | 
 | 277 | 		 * unmapped, but not yet physically erased. | 
 | 278 | 		 */ | 
 | 279 | 		err = ubi_leb_map(c->ubi, bud->lnum, UBI_SHORTTERM); | 
 | 280 | 		if (err) | 
 | 281 | 			goto out_unlock; | 
 | 282 | 	} | 
 | 283 |  | 
 | 284 | 	dbg_log("write ref LEB %d:%d", | 
 | 285 | 		c->lhead_lnum, c->lhead_offs); | 
 | 286 | 	err = ubifs_write_node(c, ref, UBIFS_REF_NODE_SZ, c->lhead_lnum, | 
 | 287 | 			       c->lhead_offs, UBI_SHORTTERM); | 
 | 288 | 	if (err) | 
 | 289 | 		goto out_unlock; | 
 | 290 |  | 
 | 291 | 	c->lhead_offs += c->ref_node_alsz; | 
 | 292 |  | 
 | 293 | 	ubifs_add_bud(c, bud); | 
 | 294 |  | 
 | 295 | 	mutex_unlock(&c->log_mutex); | 
 | 296 | 	kfree(ref); | 
 | 297 | 	return 0; | 
 | 298 |  | 
 | 299 | out_unlock: | 
| Adrian Hunter | 2fb42b1 | 2008-07-18 17:56:37 +0300 | [diff] [blame] | 300 | 	if (err != -EAGAIN) | 
 | 301 | 		ubifs_ro_mode(c, err); | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 302 | 	mutex_unlock(&c->log_mutex); | 
 | 303 | 	kfree(ref); | 
 | 304 | 	kfree(bud); | 
 | 305 | 	return err; | 
 | 306 | } | 
 | 307 |  | 
 | 308 | /** | 
 | 309 |  * remove_buds - remove used buds. | 
 | 310 |  * @c: UBIFS file-system description object | 
 | 311 |  * | 
 | 312 |  * This function removes use buds from the buds tree. It does not remove the | 
 | 313 |  * buds which are pointed to by journal heads. | 
 | 314 |  */ | 
 | 315 | static void remove_buds(struct ubifs_info *c) | 
 | 316 | { | 
 | 317 | 	struct rb_node *p; | 
 | 318 |  | 
 | 319 | 	ubifs_assert(list_empty(&c->old_buds)); | 
 | 320 | 	c->cmt_bud_bytes = 0; | 
 | 321 | 	spin_lock(&c->buds_lock); | 
 | 322 | 	p = rb_first(&c->buds); | 
 | 323 | 	while (p) { | 
 | 324 | 		struct rb_node *p1 = p; | 
 | 325 | 		struct ubifs_bud *bud; | 
 | 326 | 		struct ubifs_wbuf *wbuf; | 
 | 327 |  | 
 | 328 | 		p = rb_next(p); | 
 | 329 | 		bud = rb_entry(p1, struct ubifs_bud, rb); | 
 | 330 | 		wbuf = &c->jheads[bud->jhead].wbuf; | 
 | 331 |  | 
 | 332 | 		if (wbuf->lnum == bud->lnum) { | 
 | 333 | 			/* | 
 | 334 | 			 * Do not remove buds which are pointed to by journal | 
 | 335 | 			 * heads (non-closed buds). | 
 | 336 | 			 */ | 
 | 337 | 			c->cmt_bud_bytes += wbuf->offs - bud->start; | 
| Artem Bityutskiy | 77a7ae5 | 2009-09-15 15:03:51 +0300 | [diff] [blame] | 338 | 			dbg_log("preserve %d:%d, jhead %s, bud bytes %d, " | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 339 | 				"cmt_bud_bytes %lld", bud->lnum, bud->start, | 
| Artem Bityutskiy | 77a7ae5 | 2009-09-15 15:03:51 +0300 | [diff] [blame] | 340 | 				dbg_jhead(bud->jhead), wbuf->offs - bud->start, | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 341 | 				c->cmt_bud_bytes); | 
 | 342 | 			bud->start = wbuf->offs; | 
 | 343 | 		} else { | 
 | 344 | 			c->cmt_bud_bytes += c->leb_size - bud->start; | 
| Artem Bityutskiy | 77a7ae5 | 2009-09-15 15:03:51 +0300 | [diff] [blame] | 345 | 			dbg_log("remove %d:%d, jhead %s, bud bytes %d, " | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 346 | 				"cmt_bud_bytes %lld", bud->lnum, bud->start, | 
| Artem Bityutskiy | 77a7ae5 | 2009-09-15 15:03:51 +0300 | [diff] [blame] | 347 | 				dbg_jhead(bud->jhead), c->leb_size - bud->start, | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 348 | 				c->cmt_bud_bytes); | 
 | 349 | 			rb_erase(p1, &c->buds); | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 350 | 			/* | 
 | 351 | 			 * If the commit does not finish, the recovery will need | 
 | 352 | 			 * to replay the journal, in which case the old buds | 
 | 353 | 			 * must be unchanged. Do not release them until post | 
 | 354 | 			 * commit i.e. do not allow them to be garbage | 
 | 355 | 			 * collected. | 
 | 356 | 			 */ | 
| Eric Sesterhenn | ec32816 | 2009-02-13 09:13:11 +0100 | [diff] [blame] | 357 | 			list_move(&bud->list, &c->old_buds); | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 358 | 		} | 
 | 359 | 	} | 
 | 360 | 	spin_unlock(&c->buds_lock); | 
 | 361 | } | 
 | 362 |  | 
 | 363 | /** | 
 | 364 |  * ubifs_log_start_commit - start commit. | 
 | 365 |  * @c: UBIFS file-system description object | 
 | 366 |  * @ltail_lnum: return new log tail LEB number | 
 | 367 |  * | 
 | 368 |  * The commit operation starts with writing "commit start" node to the log and | 
 | 369 |  * reference nodes for all journal heads which will define new journal after | 
 | 370 |  * the commit has been finished. The commit start and reference nodes are | 
 | 371 |  * written in one go to the nearest empty log LEB (hence, when commit is | 
 | 372 |  * finished UBIFS may safely unmap all the previous log LEBs). This function | 
 | 373 |  * returns zero in case of success and a negative error code in case of | 
 | 374 |  * failure. | 
 | 375 |  */ | 
 | 376 | int ubifs_log_start_commit(struct ubifs_info *c, int *ltail_lnum) | 
 | 377 | { | 
 | 378 | 	void *buf; | 
 | 379 | 	struct ubifs_cs_node *cs; | 
 | 380 | 	struct ubifs_ref_node *ref; | 
 | 381 | 	int err, i, max_len, len; | 
 | 382 |  | 
 | 383 | 	err = dbg_check_bud_bytes(c); | 
 | 384 | 	if (err) | 
 | 385 | 		return err; | 
 | 386 |  | 
 | 387 | 	max_len = UBIFS_CS_NODE_SZ + c->jhead_cnt * UBIFS_REF_NODE_SZ; | 
 | 388 | 	max_len = ALIGN(max_len, c->min_io_size); | 
 | 389 | 	buf = cs = kmalloc(max_len, GFP_NOFS); | 
 | 390 | 	if (!buf) | 
 | 391 | 		return -ENOMEM; | 
 | 392 |  | 
 | 393 | 	cs->ch.node_type = UBIFS_CS_NODE; | 
| Artem Bityutskiy | 014eb04 | 2008-07-21 17:14:29 +0300 | [diff] [blame] | 394 | 	cs->cmt_no = cpu_to_le64(c->cmt_no); | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 395 | 	ubifs_prepare_node(c, cs, UBIFS_CS_NODE_SZ, 0); | 
 | 396 |  | 
 | 397 | 	/* | 
 | 398 | 	 * Note, we do not lock 'c->log_mutex' because this is the commit start | 
 | 399 | 	 * phase and we are exclusively using the log. And we do not lock | 
 | 400 | 	 * write-buffer because nobody can write to the file-system at this | 
 | 401 | 	 * phase. | 
 | 402 | 	 */ | 
 | 403 |  | 
 | 404 | 	len = UBIFS_CS_NODE_SZ; | 
 | 405 | 	for (i = 0; i < c->jhead_cnt; i++) { | 
 | 406 | 		int lnum = c->jheads[i].wbuf.lnum; | 
 | 407 | 		int offs = c->jheads[i].wbuf.offs; | 
 | 408 |  | 
 | 409 | 		if (lnum == -1 || offs == c->leb_size) | 
 | 410 | 			continue; | 
 | 411 |  | 
| Artem Bityutskiy | 77a7ae5 | 2009-09-15 15:03:51 +0300 | [diff] [blame] | 412 | 		dbg_log("add ref to LEB %d:%d for jhead %s", | 
 | 413 | 			lnum, offs, dbg_jhead(i)); | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 414 | 		ref = buf + len; | 
 | 415 | 		ref->ch.node_type = UBIFS_REF_NODE; | 
 | 416 | 		ref->lnum = cpu_to_le32(lnum); | 
 | 417 | 		ref->offs = cpu_to_le32(offs); | 
 | 418 | 		ref->jhead = cpu_to_le32(i); | 
 | 419 |  | 
 | 420 | 		ubifs_prepare_node(c, ref, UBIFS_REF_NODE_SZ, 0); | 
 | 421 | 		len += UBIFS_REF_NODE_SZ; | 
 | 422 | 	} | 
 | 423 |  | 
 | 424 | 	ubifs_pad(c, buf + len, ALIGN(len, c->min_io_size) - len); | 
 | 425 |  | 
 | 426 | 	/* Switch to the next log LEB */ | 
 | 427 | 	if (c->lhead_offs) { | 
 | 428 | 		c->lhead_lnum = next_log_lnum(c, c->lhead_lnum); | 
 | 429 | 		c->lhead_offs = 0; | 
 | 430 | 	} | 
 | 431 |  | 
 | 432 | 	if (c->lhead_offs == 0) { | 
 | 433 | 		/* Must ensure next LEB has been unmapped */ | 
 | 434 | 		err = ubifs_leb_unmap(c, c->lhead_lnum); | 
 | 435 | 		if (err) | 
 | 436 | 			goto out; | 
 | 437 | 	} | 
 | 438 |  | 
 | 439 | 	len = ALIGN(len, c->min_io_size); | 
 | 440 | 	dbg_log("writing commit start at LEB %d:0, len %d", c->lhead_lnum, len); | 
 | 441 | 	err = ubifs_leb_write(c, c->lhead_lnum, cs, 0, len, UBI_SHORTTERM); | 
 | 442 | 	if (err) | 
 | 443 | 		goto out; | 
 | 444 |  | 
 | 445 | 	*ltail_lnum = c->lhead_lnum; | 
 | 446 |  | 
 | 447 | 	c->lhead_offs += len; | 
 | 448 | 	if (c->lhead_offs == c->leb_size) { | 
 | 449 | 		c->lhead_lnum = next_log_lnum(c, c->lhead_lnum); | 
 | 450 | 		c->lhead_offs = 0; | 
 | 451 | 	} | 
 | 452 |  | 
 | 453 | 	remove_buds(c); | 
 | 454 |  | 
 | 455 | 	/* | 
 | 456 | 	 * We have started the commit and now users may use the rest of the log | 
 | 457 | 	 * for new writes. | 
 | 458 | 	 */ | 
 | 459 | 	c->min_log_bytes = 0; | 
 | 460 |  | 
 | 461 | out: | 
 | 462 | 	kfree(buf); | 
 | 463 | 	return err; | 
 | 464 | } | 
 | 465 |  | 
 | 466 | /** | 
 | 467 |  * ubifs_log_end_commit - end commit. | 
 | 468 |  * @c: UBIFS file-system description object | 
 | 469 |  * @ltail_lnum: new log tail LEB number | 
 | 470 |  * | 
 | 471 |  * This function is called on when the commit operation was finished. It | 
 | 472 |  * moves log tail to new position and unmaps LEBs which contain obsolete data. | 
 | 473 |  * Returns zero in case of success and a negative error code in case of | 
 | 474 |  * failure. | 
 | 475 |  */ | 
 | 476 | int ubifs_log_end_commit(struct ubifs_info *c, int ltail_lnum) | 
 | 477 | { | 
 | 478 | 	int err; | 
 | 479 |  | 
 | 480 | 	/* | 
 | 481 | 	 * At this phase we have to lock 'c->log_mutex' because UBIFS allows FS | 
 | 482 | 	 * writes during commit. Its only short "commit" start phase when | 
 | 483 | 	 * writers are blocked. | 
 | 484 | 	 */ | 
 | 485 | 	mutex_lock(&c->log_mutex); | 
 | 486 |  | 
 | 487 | 	dbg_log("old tail was LEB %d:0, new tail is LEB %d:0", | 
 | 488 | 		c->ltail_lnum, ltail_lnum); | 
 | 489 |  | 
 | 490 | 	c->ltail_lnum = ltail_lnum; | 
 | 491 | 	/* | 
 | 492 | 	 * The commit is finished and from now on it must be guaranteed that | 
 | 493 | 	 * there is always enough space for the next commit. | 
 | 494 | 	 */ | 
 | 495 | 	c->min_log_bytes = c->leb_size; | 
 | 496 |  | 
 | 497 | 	spin_lock(&c->buds_lock); | 
 | 498 | 	c->bud_bytes -= c->cmt_bud_bytes; | 
 | 499 | 	spin_unlock(&c->buds_lock); | 
 | 500 |  | 
 | 501 | 	err = dbg_check_bud_bytes(c); | 
 | 502 |  | 
 | 503 | 	mutex_unlock(&c->log_mutex); | 
 | 504 | 	return err; | 
 | 505 | } | 
 | 506 |  | 
 | 507 | /** | 
 | 508 |  * ubifs_log_post_commit - things to do after commit is completed. | 
 | 509 |  * @c: UBIFS file-system description object | 
 | 510 |  * @old_ltail_lnum: old log tail LEB number | 
 | 511 |  * | 
 | 512 |  * Release buds only after commit is completed, because they must be unchanged | 
 | 513 |  * if recovery is needed. | 
 | 514 |  * | 
 | 515 |  * Unmap log LEBs only after commit is completed, because they may be needed for | 
 | 516 |  * recovery. | 
 | 517 |  * | 
 | 518 |  * This function returns %0 on success and a negative error code on failure. | 
 | 519 |  */ | 
 | 520 | int ubifs_log_post_commit(struct ubifs_info *c, int old_ltail_lnum) | 
 | 521 | { | 
 | 522 | 	int lnum, err = 0; | 
 | 523 |  | 
 | 524 | 	while (!list_empty(&c->old_buds)) { | 
 | 525 | 		struct ubifs_bud *bud; | 
 | 526 |  | 
 | 527 | 		bud = list_entry(c->old_buds.next, struct ubifs_bud, list); | 
 | 528 | 		err = ubifs_return_leb(c, bud->lnum); | 
 | 529 | 		if (err) | 
 | 530 | 			return err; | 
 | 531 | 		list_del(&bud->list); | 
 | 532 | 		kfree(bud); | 
 | 533 | 	} | 
 | 534 | 	mutex_lock(&c->log_mutex); | 
 | 535 | 	for (lnum = old_ltail_lnum; lnum != c->ltail_lnum; | 
 | 536 | 	     lnum = next_log_lnum(c, lnum)) { | 
 | 537 | 		dbg_log("unmap log LEB %d", lnum); | 
 | 538 | 		err = ubifs_leb_unmap(c, lnum); | 
 | 539 | 		if (err) | 
 | 540 | 			goto out; | 
 | 541 | 	} | 
 | 542 | out: | 
 | 543 | 	mutex_unlock(&c->log_mutex); | 
 | 544 | 	return err; | 
 | 545 | } | 
 | 546 |  | 
 | 547 | /** | 
 | 548 |  * struct done_ref - references that have been done. | 
 | 549 |  * @rb: rb-tree node | 
 | 550 |  * @lnum: LEB number | 
 | 551 |  */ | 
 | 552 | struct done_ref { | 
 | 553 | 	struct rb_node rb; | 
 | 554 | 	int lnum; | 
 | 555 | }; | 
 | 556 |  | 
 | 557 | /** | 
 | 558 |  * done_already - determine if a reference has been done already. | 
 | 559 |  * @done_tree: rb-tree to store references that have been done | 
 | 560 |  * @lnum: LEB number of reference | 
 | 561 |  * | 
 | 562 |  * This function returns %1 if the reference has been done, %0 if not, otherwise | 
 | 563 |  * a negative error code is returned. | 
 | 564 |  */ | 
 | 565 | static int done_already(struct rb_root *done_tree, int lnum) | 
 | 566 | { | 
 | 567 | 	struct rb_node **p = &done_tree->rb_node, *parent = NULL; | 
 | 568 | 	struct done_ref *dr; | 
 | 569 |  | 
 | 570 | 	while (*p) { | 
 | 571 | 		parent = *p; | 
 | 572 | 		dr = rb_entry(parent, struct done_ref, rb); | 
 | 573 | 		if (lnum < dr->lnum) | 
 | 574 | 			p = &(*p)->rb_left; | 
 | 575 | 		else if (lnum > dr->lnum) | 
 | 576 | 			p = &(*p)->rb_right; | 
 | 577 | 		else | 
 | 578 | 			return 1; | 
 | 579 | 	} | 
 | 580 |  | 
 | 581 | 	dr = kzalloc(sizeof(struct done_ref), GFP_NOFS); | 
 | 582 | 	if (!dr) | 
 | 583 | 		return -ENOMEM; | 
 | 584 |  | 
 | 585 | 	dr->lnum = lnum; | 
 | 586 |  | 
 | 587 | 	rb_link_node(&dr->rb, parent, p); | 
 | 588 | 	rb_insert_color(&dr->rb, done_tree); | 
 | 589 |  | 
 | 590 | 	return 0; | 
 | 591 | } | 
 | 592 |  | 
 | 593 | /** | 
 | 594 |  * destroy_done_tree - destroy the done tree. | 
 | 595 |  * @done_tree: done tree to destroy | 
 | 596 |  */ | 
 | 597 | static void destroy_done_tree(struct rb_root *done_tree) | 
 | 598 | { | 
 | 599 | 	struct rb_node *this = done_tree->rb_node; | 
 | 600 | 	struct done_ref *dr; | 
 | 601 |  | 
 | 602 | 	while (this) { | 
 | 603 | 		if (this->rb_left) { | 
 | 604 | 			this = this->rb_left; | 
 | 605 | 			continue; | 
 | 606 | 		} else if (this->rb_right) { | 
 | 607 | 			this = this->rb_right; | 
 | 608 | 			continue; | 
 | 609 | 		} | 
 | 610 | 		dr = rb_entry(this, struct done_ref, rb); | 
 | 611 | 		this = rb_parent(this); | 
 | 612 | 		if (this) { | 
 | 613 | 			if (this->rb_left == &dr->rb) | 
 | 614 | 				this->rb_left = NULL; | 
 | 615 | 			else | 
 | 616 | 				this->rb_right = NULL; | 
 | 617 | 		} | 
 | 618 | 		kfree(dr); | 
 | 619 | 	} | 
 | 620 | } | 
 | 621 |  | 
 | 622 | /** | 
 | 623 |  * add_node - add a node to the consolidated log. | 
 | 624 |  * @c: UBIFS file-system description object | 
 | 625 |  * @buf: buffer to which to add | 
 | 626 |  * @lnum: LEB number to which to write is passed and returned here | 
 | 627 |  * @offs: offset to where to write is passed and returned here | 
 | 628 |  * @node: node to add | 
 | 629 |  * | 
 | 630 |  * This function returns %0 on success and a negative error code on failure. | 
 | 631 |  */ | 
 | 632 | static int add_node(struct ubifs_info *c, void *buf, int *lnum, int *offs, | 
 | 633 | 		    void *node) | 
 | 634 | { | 
 | 635 | 	struct ubifs_ch *ch = node; | 
 | 636 | 	int len = le32_to_cpu(ch->len), remains = c->leb_size - *offs; | 
 | 637 |  | 
 | 638 | 	if (len > remains) { | 
 | 639 | 		int sz = ALIGN(*offs, c->min_io_size), err; | 
 | 640 |  | 
 | 641 | 		ubifs_pad(c, buf + *offs, sz - *offs); | 
 | 642 | 		err = ubifs_leb_change(c, *lnum, buf, sz, UBI_SHORTTERM); | 
 | 643 | 		if (err) | 
 | 644 | 			return err; | 
 | 645 | 		*lnum = next_log_lnum(c, *lnum); | 
 | 646 | 		*offs = 0; | 
 | 647 | 	} | 
 | 648 | 	memcpy(buf + *offs, node, len); | 
 | 649 | 	*offs += ALIGN(len, 8); | 
 | 650 | 	return 0; | 
 | 651 | } | 
 | 652 |  | 
 | 653 | /** | 
 | 654 |  * ubifs_consolidate_log - consolidate the log. | 
 | 655 |  * @c: UBIFS file-system description object | 
 | 656 |  * | 
 | 657 |  * Repeated failed commits could cause the log to be full, but at least 1 LEB is | 
 | 658 |  * needed for commit. This function rewrites the reference nodes in the log | 
 | 659 |  * omitting duplicates, and failed CS nodes, and leaving no gaps. | 
 | 660 |  * | 
 | 661 |  * This function returns %0 on success and a negative error code on failure. | 
 | 662 |  */ | 
 | 663 | int ubifs_consolidate_log(struct ubifs_info *c) | 
 | 664 | { | 
 | 665 | 	struct ubifs_scan_leb *sleb; | 
 | 666 | 	struct ubifs_scan_node *snod; | 
 | 667 | 	struct rb_root done_tree = RB_ROOT; | 
 | 668 | 	int lnum, err, first = 1, write_lnum, offs = 0; | 
 | 669 | 	void *buf; | 
 | 670 |  | 
 | 671 | 	dbg_rcvry("log tail LEB %d, log head LEB %d", c->ltail_lnum, | 
 | 672 | 		  c->lhead_lnum); | 
 | 673 | 	buf = vmalloc(c->leb_size); | 
 | 674 | 	if (!buf) | 
 | 675 | 		return -ENOMEM; | 
 | 676 | 	lnum = c->ltail_lnum; | 
 | 677 | 	write_lnum = lnum; | 
 | 678 | 	while (1) { | 
| Artem Bityutskiy | 348709b | 2009-08-25 15:00:55 +0300 | [diff] [blame] | 679 | 		sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0); | 
| Artem Bityutskiy | 1e51764 | 2008-07-14 19:08:37 +0300 | [diff] [blame] | 680 | 		if (IS_ERR(sleb)) { | 
 | 681 | 			err = PTR_ERR(sleb); | 
 | 682 | 			goto out_free; | 
 | 683 | 		} | 
 | 684 | 		list_for_each_entry(snod, &sleb->nodes, list) { | 
 | 685 | 			switch (snod->type) { | 
 | 686 | 			case UBIFS_REF_NODE: { | 
 | 687 | 				struct ubifs_ref_node *ref = snod->node; | 
 | 688 | 				int ref_lnum = le32_to_cpu(ref->lnum); | 
 | 689 |  | 
 | 690 | 				err = done_already(&done_tree, ref_lnum); | 
 | 691 | 				if (err < 0) | 
 | 692 | 					goto out_scan; | 
 | 693 | 				if (err != 1) { | 
 | 694 | 					err = add_node(c, buf, &write_lnum, | 
 | 695 | 						       &offs, snod->node); | 
 | 696 | 					if (err) | 
 | 697 | 						goto out_scan; | 
 | 698 | 				} | 
 | 699 | 				break; | 
 | 700 | 			} | 
 | 701 | 			case UBIFS_CS_NODE: | 
 | 702 | 				if (!first) | 
 | 703 | 					break; | 
 | 704 | 				err = add_node(c, buf, &write_lnum, &offs, | 
 | 705 | 					       snod->node); | 
 | 706 | 				if (err) | 
 | 707 | 					goto out_scan; | 
 | 708 | 				first = 0; | 
 | 709 | 				break; | 
 | 710 | 			} | 
 | 711 | 		} | 
 | 712 | 		ubifs_scan_destroy(sleb); | 
 | 713 | 		if (lnum == c->lhead_lnum) | 
 | 714 | 			break; | 
 | 715 | 		lnum = next_log_lnum(c, lnum); | 
 | 716 | 	} | 
 | 717 | 	if (offs) { | 
 | 718 | 		int sz = ALIGN(offs, c->min_io_size); | 
 | 719 |  | 
 | 720 | 		ubifs_pad(c, buf + offs, sz - offs); | 
 | 721 | 		err = ubifs_leb_change(c, write_lnum, buf, sz, UBI_SHORTTERM); | 
 | 722 | 		if (err) | 
 | 723 | 			goto out_free; | 
 | 724 | 		offs = ALIGN(offs, c->min_io_size); | 
 | 725 | 	} | 
 | 726 | 	destroy_done_tree(&done_tree); | 
 | 727 | 	vfree(buf); | 
 | 728 | 	if (write_lnum == c->lhead_lnum) { | 
 | 729 | 		ubifs_err("log is too full"); | 
 | 730 | 		return -EINVAL; | 
 | 731 | 	} | 
 | 732 | 	/* Unmap remaining LEBs */ | 
 | 733 | 	lnum = write_lnum; | 
 | 734 | 	do { | 
 | 735 | 		lnum = next_log_lnum(c, lnum); | 
 | 736 | 		err = ubifs_leb_unmap(c, lnum); | 
 | 737 | 		if (err) | 
 | 738 | 			return err; | 
 | 739 | 	} while (lnum != c->lhead_lnum); | 
 | 740 | 	c->lhead_lnum = write_lnum; | 
 | 741 | 	c->lhead_offs = offs; | 
 | 742 | 	dbg_rcvry("new log head at %d:%d", c->lhead_lnum, c->lhead_offs); | 
 | 743 | 	return 0; | 
 | 744 |  | 
 | 745 | out_scan: | 
 | 746 | 	ubifs_scan_destroy(sleb); | 
 | 747 | out_free: | 
 | 748 | 	destroy_done_tree(&done_tree); | 
 | 749 | 	vfree(buf); | 
 | 750 | 	return err; | 
 | 751 | } | 
 | 752 |  | 
 | 753 | #ifdef CONFIG_UBIFS_FS_DEBUG | 
 | 754 |  | 
 | 755 | /** | 
 | 756 |  * dbg_check_bud_bytes - make sure bud bytes calculation are all right. | 
 | 757 |  * @c: UBIFS file-system description object | 
 | 758 |  * | 
 | 759 |  * This function makes sure the amount of flash space used by closed buds | 
 | 760 |  * ('c->bud_bytes' is correct). Returns zero in case of success and %-EINVAL in | 
 | 761 |  * case of failure. | 
 | 762 |  */ | 
 | 763 | static int dbg_check_bud_bytes(struct ubifs_info *c) | 
 | 764 | { | 
 | 765 | 	int i, err = 0; | 
 | 766 | 	struct ubifs_bud *bud; | 
 | 767 | 	long long bud_bytes = 0; | 
 | 768 |  | 
 | 769 | 	if (!(ubifs_chk_flags & UBIFS_CHK_GEN)) | 
 | 770 | 		return 0; | 
 | 771 |  | 
 | 772 | 	spin_lock(&c->buds_lock); | 
 | 773 | 	for (i = 0; i < c->jhead_cnt; i++) | 
 | 774 | 		list_for_each_entry(bud, &c->jheads[i].buds_list, list) | 
 | 775 | 			bud_bytes += c->leb_size - bud->start; | 
 | 776 |  | 
 | 777 | 	if (c->bud_bytes != bud_bytes) { | 
 | 778 | 		ubifs_err("bad bud_bytes %lld, calculated %lld", | 
 | 779 | 			  c->bud_bytes, bud_bytes); | 
 | 780 | 		err = -EINVAL; | 
 | 781 | 	} | 
 | 782 | 	spin_unlock(&c->buds_lock); | 
 | 783 |  | 
 | 784 | 	return err; | 
 | 785 | } | 
 | 786 |  | 
 | 787 | #endif /* CONFIG_UBIFS_FS_DEBUG */ |