xref: /openbmc/u-boot/drivers/mtd/ubi/eba.c (revision 38041db7)
1 /*
2  * Copyright (c) International Business Machines Corp., 2006
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
12  * the GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Artem Bityutskiy (Битюцкий Артём)
19  */
20 
21 /*
22  * The UBI Eraseblock Association (EBA) unit.
23  *
24  * This unit is responsible for I/O to/from logical eraseblock.
25  *
26  * Although in this implementation the EBA table is fully kept and managed in
27  * RAM, which assumes poor scalability, it might be (partially) maintained on
28  * flash in future implementations.
29  *
30  * The EBA unit implements per-logical eraseblock locking. Before accessing a
31  * logical eraseblock it is locked for reading or writing. The per-logical
32  * eraseblock locking is implemented by means of the lock tree. The lock tree
33  * is an RB-tree which refers all the currently locked logical eraseblocks. The
34  * lock tree elements are &struct ubi_ltree_entry objects. They are indexed by
35  * (@vol_id, @lnum) pairs.
36  *
37  * EBA also maintains the global sequence counter which is incremented each
38  * time a logical eraseblock is mapped to a physical eraseblock and it is
39  * stored in the volume identifier header. This means that each VID header has
40  * a unique sequence number. The sequence number is only increased an we assume
41  * 64 bits is enough to never overflow.
42  */
43 
44 #ifdef UBI_LINUX
45 #include <linux/slab.h>
46 #include <linux/crc32.h>
47 #include <linux/err.h>
48 #endif
49 
50 #include <ubi_uboot.h>
51 #include "ubi.h"
52 
53 /* Number of physical eraseblocks reserved for atomic LEB change operation */
54 #define EBA_RESERVED_PEBS 1
55 
56 /**
57  * next_sqnum - get next sequence number.
58  * @ubi: UBI device description object
59  *
60  * This function returns next sequence number to use, which is just the current
61  * global sequence counter value. It also increases the global sequence
62  * counter.
63  */
64 static unsigned long long next_sqnum(struct ubi_device *ubi)
65 {
66 	unsigned long long sqnum;
67 
68 	spin_lock(&ubi->ltree_lock);
69 	sqnum = ubi->global_sqnum++;
70 	spin_unlock(&ubi->ltree_lock);
71 
72 	return sqnum;
73 }
74 
75 /**
76  * ubi_get_compat - get compatibility flags of a volume.
77  * @ubi: UBI device description object
78  * @vol_id: volume ID
79  *
80  * This function returns compatibility flags for an internal volume. User
81  * volumes have no compatibility flags, so %0 is returned.
82  */
83 static int ubi_get_compat(const struct ubi_device *ubi, int vol_id)
84 {
85 	if (vol_id == UBI_LAYOUT_VOLUME_ID)
86 		return UBI_LAYOUT_VOLUME_COMPAT;
87 	return 0;
88 }
89 
90 /**
91  * ltree_lookup - look up the lock tree.
92  * @ubi: UBI device description object
93  * @vol_id: volume ID
94  * @lnum: logical eraseblock number
95  *
96  * This function returns a pointer to the corresponding &struct ubi_ltree_entry
97  * object if the logical eraseblock is locked and %NULL if it is not.
98  * @ubi->ltree_lock has to be locked.
99  */
100 static struct ubi_ltree_entry *ltree_lookup(struct ubi_device *ubi, int vol_id,
101 					    int lnum)
102 {
103 	struct rb_node *p;
104 
105 	p = ubi->ltree.rb_node;
106 	while (p) {
107 		struct ubi_ltree_entry *le;
108 
109 		le = rb_entry(p, struct ubi_ltree_entry, rb);
110 
111 		if (vol_id < le->vol_id)
112 			p = p->rb_left;
113 		else if (vol_id > le->vol_id)
114 			p = p->rb_right;
115 		else {
116 			if (lnum < le->lnum)
117 				p = p->rb_left;
118 			else if (lnum > le->lnum)
119 				p = p->rb_right;
120 			else
121 				return le;
122 		}
123 	}
124 
125 	return NULL;
126 }
127 
128 /**
129  * ltree_add_entry - add new entry to the lock tree.
130  * @ubi: UBI device description object
131  * @vol_id: volume ID
132  * @lnum: logical eraseblock number
133  *
134  * This function adds new entry for logical eraseblock (@vol_id, @lnum) to the
135  * lock tree. If such entry is already there, its usage counter is increased.
136  * Returns pointer to the lock tree entry or %-ENOMEM if memory allocation
137  * failed.
138  */
139 static struct ubi_ltree_entry *ltree_add_entry(struct ubi_device *ubi,
140 					       int vol_id, int lnum)
141 {
142 	struct ubi_ltree_entry *le, *le1, *le_free;
143 
144 	le = kmalloc(sizeof(struct ubi_ltree_entry), GFP_NOFS);
145 	if (!le)
146 		return ERR_PTR(-ENOMEM);
147 
148 	le->users = 0;
149 	init_rwsem(&le->mutex);
150 	le->vol_id = vol_id;
151 	le->lnum = lnum;
152 
153 	spin_lock(&ubi->ltree_lock);
154 	le1 = ltree_lookup(ubi, vol_id, lnum);
155 
156 	if (le1) {
157 		/*
158 		 * This logical eraseblock is already locked. The newly
159 		 * allocated lock entry is not needed.
160 		 */
161 		le_free = le;
162 		le = le1;
163 	} else {
164 		struct rb_node **p, *parent = NULL;
165 
166 		/*
167 		 * No lock entry, add the newly allocated one to the
168 		 * @ubi->ltree RB-tree.
169 		 */
170 		le_free = NULL;
171 
172 		p = &ubi->ltree.rb_node;
173 		while (*p) {
174 			parent = *p;
175 			le1 = rb_entry(parent, struct ubi_ltree_entry, rb);
176 
177 			if (vol_id < le1->vol_id)
178 				p = &(*p)->rb_left;
179 			else if (vol_id > le1->vol_id)
180 				p = &(*p)->rb_right;
181 			else {
182 				ubi_assert(lnum != le1->lnum);
183 				if (lnum < le1->lnum)
184 					p = &(*p)->rb_left;
185 				else
186 					p = &(*p)->rb_right;
187 			}
188 		}
189 
190 		rb_link_node(&le->rb, parent, p);
191 		rb_insert_color(&le->rb, &ubi->ltree);
192 	}
193 	le->users += 1;
194 	spin_unlock(&ubi->ltree_lock);
195 
196 	if (le_free)
197 		kfree(le_free);
198 
199 	return le;
200 }
201 
202 /**
203  * leb_read_lock - lock logical eraseblock for reading.
204  * @ubi: UBI device description object
205  * @vol_id: volume ID
206  * @lnum: logical eraseblock number
207  *
208  * This function locks a logical eraseblock for reading. Returns zero in case
209  * of success and a negative error code in case of failure.
210  */
211 static int leb_read_lock(struct ubi_device *ubi, int vol_id, int lnum)
212 {
213 	struct ubi_ltree_entry *le;
214 
215 	le = ltree_add_entry(ubi, vol_id, lnum);
216 	if (IS_ERR(le))
217 		return PTR_ERR(le);
218 	down_read(&le->mutex);
219 	return 0;
220 }
221 
222 /**
223  * leb_read_unlock - unlock logical eraseblock.
224  * @ubi: UBI device description object
225  * @vol_id: volume ID
226  * @lnum: logical eraseblock number
227  */
228 static void leb_read_unlock(struct ubi_device *ubi, int vol_id, int lnum)
229 {
230 	int _free = 0;
231 	struct ubi_ltree_entry *le;
232 
233 	spin_lock(&ubi->ltree_lock);
234 	le = ltree_lookup(ubi, vol_id, lnum);
235 	le->users -= 1;
236 	ubi_assert(le->users >= 0);
237 	if (le->users == 0) {
238 		rb_erase(&le->rb, &ubi->ltree);
239 		_free = 1;
240 	}
241 	spin_unlock(&ubi->ltree_lock);
242 
243 	up_read(&le->mutex);
244 	if (_free)
245 		kfree(le);
246 }
247 
248 /**
249  * leb_write_lock - lock logical eraseblock for writing.
250  * @ubi: UBI device description object
251  * @vol_id: volume ID
252  * @lnum: logical eraseblock number
253  *
254  * This function locks a logical eraseblock for writing. Returns zero in case
255  * of success and a negative error code in case of failure.
256  */
257 static int leb_write_lock(struct ubi_device *ubi, int vol_id, int lnum)
258 {
259 	struct ubi_ltree_entry *le;
260 
261 	le = ltree_add_entry(ubi, vol_id, lnum);
262 	if (IS_ERR(le))
263 		return PTR_ERR(le);
264 	down_write(&le->mutex);
265 	return 0;
266 }
267 
268 /**
269  * leb_write_lock - lock logical eraseblock for writing.
270  * @ubi: UBI device description object
271  * @vol_id: volume ID
272  * @lnum: logical eraseblock number
273  *
274  * This function locks a logical eraseblock for writing if there is no
275  * contention and does nothing if there is contention. Returns %0 in case of
276  * success, %1 in case of contention, and and a negative error code in case of
277  * failure.
278  */
279 static int leb_write_trylock(struct ubi_device *ubi, int vol_id, int lnum)
280 {
281 	int _free;
282 	struct ubi_ltree_entry *le;
283 
284 	le = ltree_add_entry(ubi, vol_id, lnum);
285 	if (IS_ERR(le))
286 		return PTR_ERR(le);
287 	if (down_write_trylock(&le->mutex))
288 		return 0;
289 
290 	/* Contention, cancel */
291 	spin_lock(&ubi->ltree_lock);
292 	le->users -= 1;
293 	ubi_assert(le->users >= 0);
294 	if (le->users == 0) {
295 		rb_erase(&le->rb, &ubi->ltree);
296 		_free = 1;
297 	} else
298 		_free = 0;
299 	spin_unlock(&ubi->ltree_lock);
300 	if (_free)
301 		kfree(le);
302 
303 	return 1;
304 }
305 
306 /**
307  * leb_write_unlock - unlock logical eraseblock.
308  * @ubi: UBI device description object
309  * @vol_id: volume ID
310  * @lnum: logical eraseblock number
311  */
312 static void leb_write_unlock(struct ubi_device *ubi, int vol_id, int lnum)
313 {
314 	int _free;
315 	struct ubi_ltree_entry *le;
316 
317 	spin_lock(&ubi->ltree_lock);
318 	le = ltree_lookup(ubi, vol_id, lnum);
319 	le->users -= 1;
320 	ubi_assert(le->users >= 0);
321 	if (le->users == 0) {
322 		rb_erase(&le->rb, &ubi->ltree);
323 		_free = 1;
324 	} else
325 		_free = 0;
326 	spin_unlock(&ubi->ltree_lock);
327 
328 	up_write(&le->mutex);
329 	if (_free)
330 		kfree(le);
331 }
332 
333 /**
334  * ubi_eba_unmap_leb - un-map logical eraseblock.
335  * @ubi: UBI device description object
336  * @vol: volume description object
337  * @lnum: logical eraseblock number
338  *
339  * This function un-maps logical eraseblock @lnum and schedules corresponding
340  * physical eraseblock for erasure. Returns zero in case of success and a
341  * negative error code in case of failure.
342  */
343 int ubi_eba_unmap_leb(struct ubi_device *ubi, struct ubi_volume *vol,
344 		      int lnum)
345 {
346 	int err, pnum, vol_id = vol->vol_id;
347 
348 	if (ubi->ro_mode)
349 		return -EROFS;
350 
351 	err = leb_write_lock(ubi, vol_id, lnum);
352 	if (err)
353 		return err;
354 
355 	pnum = vol->eba_tbl[lnum];
356 	if (pnum < 0)
357 		/* This logical eraseblock is already unmapped */
358 		goto out_unlock;
359 
360 	dbg_eba("erase LEB %d:%d, PEB %d", vol_id, lnum, pnum);
361 
362 	vol->eba_tbl[lnum] = UBI_LEB_UNMAPPED;
363 	err = ubi_wl_put_peb(ubi, pnum, 0);
364 
365 out_unlock:
366 	leb_write_unlock(ubi, vol_id, lnum);
367 	return err;
368 }
369 
370 /**
371  * ubi_eba_read_leb - read data.
372  * @ubi: UBI device description object
373  * @vol: volume description object
374  * @lnum: logical eraseblock number
375  * @buf: buffer to store the read data
376  * @offset: offset from where to read
377  * @len: how many bytes to read
378  * @check: data CRC check flag
379  *
380  * If the logical eraseblock @lnum is unmapped, @buf is filled with 0xFF
381  * bytes. The @check flag only makes sense for static volumes and forces
382  * eraseblock data CRC checking.
383  *
384  * In case of success this function returns zero. In case of a static volume,
385  * if data CRC mismatches - %-EBADMSG is returned. %-EBADMSG may also be
386  * returned for any volume type if an ECC error was detected by the MTD device
387  * driver. Other negative error cored may be returned in case of other errors.
388  */
389 int ubi_eba_read_leb(struct ubi_device *ubi, struct ubi_volume *vol, int lnum,
390 		     void *buf, int offset, int len, int check)
391 {
392 	int err, pnum, scrub = 0, vol_id = vol->vol_id;
393 	struct ubi_vid_hdr *vid_hdr;
394 	uint32_t uninitialized_var(crc);
395 
396 	err = leb_read_lock(ubi, vol_id, lnum);
397 	if (err)
398 		return err;
399 
400 	pnum = vol->eba_tbl[lnum];
401 	if (pnum < 0) {
402 		/*
403 		 * The logical eraseblock is not mapped, fill the whole buffer
404 		 * with 0xFF bytes. The exception is static volumes for which
405 		 * it is an error to read unmapped logical eraseblocks.
406 		 */
407 		dbg_eba("read %d bytes from offset %d of LEB %d:%d (unmapped)",
408 			len, offset, vol_id, lnum);
409 		leb_read_unlock(ubi, vol_id, lnum);
410 		ubi_assert(vol->vol_type != UBI_STATIC_VOLUME);
411 		memset(buf, 0xFF, len);
412 		return 0;
413 	}
414 
415 	dbg_eba("read %d bytes from offset %d of LEB %d:%d, PEB %d",
416 		len, offset, vol_id, lnum, pnum);
417 
418 	if (vol->vol_type == UBI_DYNAMIC_VOLUME)
419 		check = 0;
420 
421 retry:
422 	if (check) {
423 		vid_hdr = ubi_zalloc_vid_hdr(ubi, GFP_NOFS);
424 		if (!vid_hdr) {
425 			err = -ENOMEM;
426 			goto out_unlock;
427 		}
428 
429 		err = ubi_io_read_vid_hdr(ubi, pnum, vid_hdr, 1);
430 		if (err && err != UBI_IO_BITFLIPS) {
431 			if (err > 0) {
432 				/*
433 				 * The header is either absent or corrupted.
434 				 * The former case means there is a bug -
435 				 * switch to read-only mode just in case.
436 				 * The latter case means a real corruption - we
437 				 * may try to recover data. FIXME: but this is
438 				 * not implemented.
439 				 */
440 				if (err == UBI_IO_BAD_VID_HDR) {
441 					ubi_warn("bad VID header at PEB %d, LEB"
442 						 "%d:%d", pnum, vol_id, lnum);
443 					err = -EBADMSG;
444 				} else
445 					ubi_ro_mode(ubi);
446 			}
447 			goto out_free;
448 		} else if (err == UBI_IO_BITFLIPS)
449 			scrub = 1;
450 
451 		ubi_assert(lnum < be32_to_cpu(vid_hdr->used_ebs));
452 		ubi_assert(len == be32_to_cpu(vid_hdr->data_size));
453 
454 		crc = be32_to_cpu(vid_hdr->data_crc);
455 		ubi_free_vid_hdr(ubi, vid_hdr);
456 	}
457 
458 	err = ubi_io_read_data(ubi, buf, pnum, offset, len);
459 	if (err) {
460 		if (err == UBI_IO_BITFLIPS) {
461 			scrub = 1;
462 			err = 0;
463 		} else if (err == -EBADMSG) {
464 			if (vol->vol_type == UBI_DYNAMIC_VOLUME)
465 				goto out_unlock;
466 			scrub = 1;
467 			if (!check) {
468 				ubi_msg("force data checking");
469 				check = 1;
470 				goto retry;
471 			}
472 		} else
473 			goto out_unlock;
474 	}
475 
476 	if (check) {
477 		uint32_t crc1 = crc32(UBI_CRC32_INIT, buf, len);
478 		if (crc1 != crc) {
479 			ubi_warn("CRC error: calculated %#08x, must be %#08x",
480 				 crc1, crc);
481 			err = -EBADMSG;
482 			goto out_unlock;
483 		}
484 	}
485 
486 	if (scrub)
487 		err = ubi_wl_scrub_peb(ubi, pnum);
488 
489 	leb_read_unlock(ubi, vol_id, lnum);
490 	return err;
491 
492 out_free:
493 	ubi_free_vid_hdr(ubi, vid_hdr);
494 out_unlock:
495 	leb_read_unlock(ubi, vol_id, lnum);
496 	return err;
497 }
498 
499 /**
500  * recover_peb - recover from write failure.
501  * @ubi: UBI device description object
502  * @pnum: the physical eraseblock to recover
503  * @vol_id: volume ID
504  * @lnum: logical eraseblock number
505  * @buf: data which was not written because of the write failure
506  * @offset: offset of the failed write
507  * @len: how many bytes should have been written
508  *
509  * This function is called in case of a write failure and moves all good data
510  * from the potentially bad physical eraseblock to a good physical eraseblock.
511  * This function also writes the data which was not written due to the failure.
512  * Returns new physical eraseblock number in case of success, and a negative
513  * error code in case of failure.
514  */
515 static int recover_peb(struct ubi_device *ubi, int pnum, int vol_id, int lnum,
516 		       const void *buf, int offset, int len)
517 {
518 	int err, idx = vol_id2idx(ubi, vol_id), new_pnum, data_size, tries = 0;
519 	struct ubi_volume *vol = ubi->volumes[idx];
520 	struct ubi_vid_hdr *vid_hdr;
521 
522 	vid_hdr = ubi_zalloc_vid_hdr(ubi, GFP_NOFS);
523 	if (!vid_hdr) {
524 		return -ENOMEM;
525 	}
526 
527 	mutex_lock(&ubi->buf_mutex);
528 
529 retry:
530 	new_pnum = ubi_wl_get_peb(ubi, UBI_UNKNOWN);
531 	if (new_pnum < 0) {
532 		mutex_unlock(&ubi->buf_mutex);
533 		ubi_free_vid_hdr(ubi, vid_hdr);
534 		return new_pnum;
535 	}
536 
537 	ubi_msg("recover PEB %d, move data to PEB %d", pnum, new_pnum);
538 
539 	err = ubi_io_read_vid_hdr(ubi, pnum, vid_hdr, 1);
540 	if (err && err != UBI_IO_BITFLIPS) {
541 		if (err > 0)
542 			err = -EIO;
543 		goto out_put;
544 	}
545 
546 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
547 	err = ubi_io_write_vid_hdr(ubi, new_pnum, vid_hdr);
548 	if (err)
549 		goto write_error;
550 
551 	data_size = offset + len;
552 	memset(ubi->peb_buf1 + offset, 0xFF, len);
553 
554 	/* Read everything before the area where the write failure happened */
555 	if (offset > 0) {
556 		err = ubi_io_read_data(ubi, ubi->peb_buf1, pnum, 0, offset);
557 		if (err && err != UBI_IO_BITFLIPS)
558 			goto out_put;
559 	}
560 
561 	memcpy(ubi->peb_buf1 + offset, buf, len);
562 
563 	err = ubi_io_write_data(ubi, ubi->peb_buf1, new_pnum, 0, data_size);
564 	if (err)
565 		goto write_error;
566 
567 	mutex_unlock(&ubi->buf_mutex);
568 	ubi_free_vid_hdr(ubi, vid_hdr);
569 
570 	vol->eba_tbl[lnum] = new_pnum;
571 	ubi_wl_put_peb(ubi, pnum, 1);
572 
573 	ubi_msg("data was successfully recovered");
574 	return 0;
575 
576 out_put:
577 	mutex_unlock(&ubi->buf_mutex);
578 	ubi_wl_put_peb(ubi, new_pnum, 1);
579 	ubi_free_vid_hdr(ubi, vid_hdr);
580 	return err;
581 
582 write_error:
583 	/*
584 	 * Bad luck? This physical eraseblock is bad too? Crud. Let's try to
585 	 * get another one.
586 	 */
587 	ubi_warn("failed to write to PEB %d", new_pnum);
588 	ubi_wl_put_peb(ubi, new_pnum, 1);
589 	if (++tries > UBI_IO_RETRIES) {
590 		mutex_unlock(&ubi->buf_mutex);
591 		ubi_free_vid_hdr(ubi, vid_hdr);
592 		return err;
593 	}
594 	ubi_msg("try again");
595 	goto retry;
596 }
597 
598 /**
599  * ubi_eba_write_leb - write data to dynamic volume.
600  * @ubi: UBI device description object
601  * @vol: volume description object
602  * @lnum: logical eraseblock number
603  * @buf: the data to write
604  * @offset: offset within the logical eraseblock where to write
605  * @len: how many bytes to write
606  * @dtype: data type
607  *
608  * This function writes data to logical eraseblock @lnum of a dynamic volume
609  * @vol. Returns zero in case of success and a negative error code in case
610  * of failure. In case of error, it is possible that something was still
611  * written to the flash media, but may be some garbage.
612  */
613 int ubi_eba_write_leb(struct ubi_device *ubi, struct ubi_volume *vol, int lnum,
614 		      const void *buf, int offset, int len, int dtype)
615 {
616 	int err, pnum, tries = 0, vol_id = vol->vol_id;
617 	struct ubi_vid_hdr *vid_hdr;
618 
619 	if (ubi->ro_mode)
620 		return -EROFS;
621 
622 	err = leb_write_lock(ubi, vol_id, lnum);
623 	if (err)
624 		return err;
625 
626 	pnum = vol->eba_tbl[lnum];
627 	if (pnum >= 0) {
628 		dbg_eba("write %d bytes at offset %d of LEB %d:%d, PEB %d",
629 			len, offset, vol_id, lnum, pnum);
630 
631 		err = ubi_io_write_data(ubi, buf, pnum, offset, len);
632 		if (err) {
633 			ubi_warn("failed to write data to PEB %d", pnum);
634 			if (err == -EIO && ubi->bad_allowed)
635 				err = recover_peb(ubi, pnum, vol_id, lnum, buf,
636 						  offset, len);
637 			if (err)
638 				ubi_ro_mode(ubi);
639 		}
640 		leb_write_unlock(ubi, vol_id, lnum);
641 		return err;
642 	}
643 
644 	/*
645 	 * The logical eraseblock is not mapped. We have to get a free physical
646 	 * eraseblock and write the volume identifier header there first.
647 	 */
648 	vid_hdr = ubi_zalloc_vid_hdr(ubi, GFP_NOFS);
649 	if (!vid_hdr) {
650 		leb_write_unlock(ubi, vol_id, lnum);
651 		return -ENOMEM;
652 	}
653 
654 	vid_hdr->vol_type = UBI_VID_DYNAMIC;
655 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
656 	vid_hdr->vol_id = cpu_to_be32(vol_id);
657 	vid_hdr->lnum = cpu_to_be32(lnum);
658 	vid_hdr->compat = ubi_get_compat(ubi, vol_id);
659 	vid_hdr->data_pad = cpu_to_be32(vol->data_pad);
660 
661 retry:
662 	pnum = ubi_wl_get_peb(ubi, dtype);
663 	if (pnum < 0) {
664 		ubi_free_vid_hdr(ubi, vid_hdr);
665 		leb_write_unlock(ubi, vol_id, lnum);
666 		return pnum;
667 	}
668 
669 	dbg_eba("write VID hdr and %d bytes at offset %d of LEB %d:%d, PEB %d",
670 		len, offset, vol_id, lnum, pnum);
671 
672 	err = ubi_io_write_vid_hdr(ubi, pnum, vid_hdr);
673 	if (err) {
674 		ubi_warn("failed to write VID header to LEB %d:%d, PEB %d",
675 			 vol_id, lnum, pnum);
676 		goto write_error;
677 	}
678 
679 	if (len) {
680 		err = ubi_io_write_data(ubi, buf, pnum, offset, len);
681 		if (err) {
682 			ubi_warn("failed to write %d bytes at offset %d of "
683 				 "LEB %d:%d, PEB %d", len, offset, vol_id,
684 				 lnum, pnum);
685 			goto write_error;
686 		}
687 	}
688 
689 	vol->eba_tbl[lnum] = pnum;
690 
691 	leb_write_unlock(ubi, vol_id, lnum);
692 	ubi_free_vid_hdr(ubi, vid_hdr);
693 	return 0;
694 
695 write_error:
696 	if (err != -EIO || !ubi->bad_allowed) {
697 		ubi_ro_mode(ubi);
698 		leb_write_unlock(ubi, vol_id, lnum);
699 		ubi_free_vid_hdr(ubi, vid_hdr);
700 		return err;
701 	}
702 
703 	/*
704 	 * Fortunately, this is the first write operation to this physical
705 	 * eraseblock, so just put it and request a new one. We assume that if
706 	 * this physical eraseblock went bad, the erase code will handle that.
707 	 */
708 	err = ubi_wl_put_peb(ubi, pnum, 1);
709 	if (err || ++tries > UBI_IO_RETRIES) {
710 		ubi_ro_mode(ubi);
711 		leb_write_unlock(ubi, vol_id, lnum);
712 		ubi_free_vid_hdr(ubi, vid_hdr);
713 		return err;
714 	}
715 
716 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
717 	ubi_msg("try another PEB");
718 	goto retry;
719 }
720 
721 /**
722  * ubi_eba_write_leb_st - write data to static volume.
723  * @ubi: UBI device description object
724  * @vol: volume description object
725  * @lnum: logical eraseblock number
726  * @buf: data to write
727  * @len: how many bytes to write
728  * @dtype: data type
729  * @used_ebs: how many logical eraseblocks will this volume contain
730  *
731  * This function writes data to logical eraseblock @lnum of static volume
732  * @vol. The @used_ebs argument should contain total number of logical
733  * eraseblock in this static volume.
734  *
735  * When writing to the last logical eraseblock, the @len argument doesn't have
736  * to be aligned to the minimal I/O unit size. Instead, it has to be equivalent
737  * to the real data size, although the @buf buffer has to contain the
738  * alignment. In all other cases, @len has to be aligned.
739  *
740  * It is prohibited to write more then once to logical eraseblocks of static
741  * volumes. This function returns zero in case of success and a negative error
742  * code in case of failure.
743  */
744 int ubi_eba_write_leb_st(struct ubi_device *ubi, struct ubi_volume *vol,
745 			 int lnum, const void *buf, int len, int dtype,
746 			 int used_ebs)
747 {
748 	int err, pnum, tries = 0, data_size = len, vol_id = vol->vol_id;
749 	struct ubi_vid_hdr *vid_hdr;
750 	uint32_t crc;
751 
752 	if (ubi->ro_mode)
753 		return -EROFS;
754 
755 	if (lnum == used_ebs - 1)
756 		/* If this is the last LEB @len may be unaligned */
757 		len = ALIGN(data_size, ubi->min_io_size);
758 	else
759 		ubi_assert(!(len & (ubi->min_io_size - 1)));
760 
761 	vid_hdr = ubi_zalloc_vid_hdr(ubi, GFP_NOFS);
762 	if (!vid_hdr)
763 		return -ENOMEM;
764 
765 	err = leb_write_lock(ubi, vol_id, lnum);
766 	if (err) {
767 		ubi_free_vid_hdr(ubi, vid_hdr);
768 		return err;
769 	}
770 
771 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
772 	vid_hdr->vol_id = cpu_to_be32(vol_id);
773 	vid_hdr->lnum = cpu_to_be32(lnum);
774 	vid_hdr->compat = ubi_get_compat(ubi, vol_id);
775 	vid_hdr->data_pad = cpu_to_be32(vol->data_pad);
776 
777 	crc = crc32(UBI_CRC32_INIT, buf, data_size);
778 	vid_hdr->vol_type = UBI_VID_STATIC;
779 	vid_hdr->data_size = cpu_to_be32(data_size);
780 	vid_hdr->used_ebs = cpu_to_be32(used_ebs);
781 	vid_hdr->data_crc = cpu_to_be32(crc);
782 
783 retry:
784 	pnum = ubi_wl_get_peb(ubi, dtype);
785 	if (pnum < 0) {
786 		ubi_free_vid_hdr(ubi, vid_hdr);
787 		leb_write_unlock(ubi, vol_id, lnum);
788 		return pnum;
789 	}
790 
791 	dbg_eba("write VID hdr and %d bytes at LEB %d:%d, PEB %d, used_ebs %d",
792 		len, vol_id, lnum, pnum, used_ebs);
793 
794 	err = ubi_io_write_vid_hdr(ubi, pnum, vid_hdr);
795 	if (err) {
796 		ubi_warn("failed to write VID header to LEB %d:%d, PEB %d",
797 			 vol_id, lnum, pnum);
798 		goto write_error;
799 	}
800 
801 	err = ubi_io_write_data(ubi, buf, pnum, 0, len);
802 	if (err) {
803 		ubi_warn("failed to write %d bytes of data to PEB %d",
804 			 len, pnum);
805 		goto write_error;
806 	}
807 
808 	ubi_assert(vol->eba_tbl[lnum] < 0);
809 	vol->eba_tbl[lnum] = pnum;
810 
811 	leb_write_unlock(ubi, vol_id, lnum);
812 	ubi_free_vid_hdr(ubi, vid_hdr);
813 	return 0;
814 
815 write_error:
816 	if (err != -EIO || !ubi->bad_allowed) {
817 		/*
818 		 * This flash device does not admit of bad eraseblocks or
819 		 * something nasty and unexpected happened. Switch to read-only
820 		 * mode just in case.
821 		 */
822 		ubi_ro_mode(ubi);
823 		leb_write_unlock(ubi, vol_id, lnum);
824 		ubi_free_vid_hdr(ubi, vid_hdr);
825 		return err;
826 	}
827 
828 	err = ubi_wl_put_peb(ubi, pnum, 1);
829 	if (err || ++tries > UBI_IO_RETRIES) {
830 		ubi_ro_mode(ubi);
831 		leb_write_unlock(ubi, vol_id, lnum);
832 		ubi_free_vid_hdr(ubi, vid_hdr);
833 		return err;
834 	}
835 
836 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
837 	ubi_msg("try another PEB");
838 	goto retry;
839 }
840 
841 /*
842  * ubi_eba_atomic_leb_change - change logical eraseblock atomically.
843  * @ubi: UBI device description object
844  * @vol: volume description object
845  * @lnum: logical eraseblock number
846  * @buf: data to write
847  * @len: how many bytes to write
848  * @dtype: data type
849  *
850  * This function changes the contents of a logical eraseblock atomically. @buf
851  * has to contain new logical eraseblock data, and @len - the length of the
852  * data, which has to be aligned. This function guarantees that in case of an
853  * unclean reboot the old contents is preserved. Returns zero in case of
854  * success and a negative error code in case of failure.
855  *
856  * UBI reserves one LEB for the "atomic LEB change" operation, so only one
857  * LEB change may be done at a time. This is ensured by @ubi->alc_mutex.
858  */
859 int ubi_eba_atomic_leb_change(struct ubi_device *ubi, struct ubi_volume *vol,
860 			      int lnum, const void *buf, int len, int dtype)
861 {
862 	int err, pnum, tries = 0, vol_id = vol->vol_id;
863 	struct ubi_vid_hdr *vid_hdr;
864 	uint32_t crc;
865 
866 	if (ubi->ro_mode)
867 		return -EROFS;
868 
869 	if (len == 0) {
870 		/*
871 		 * Special case when data length is zero. In this case the LEB
872 		 * has to be unmapped and mapped somewhere else.
873 		 */
874 		err = ubi_eba_unmap_leb(ubi, vol, lnum);
875 		if (err)
876 			return err;
877 		return ubi_eba_write_leb(ubi, vol, lnum, NULL, 0, 0, dtype);
878 	}
879 
880 	vid_hdr = ubi_zalloc_vid_hdr(ubi, GFP_NOFS);
881 	if (!vid_hdr)
882 		return -ENOMEM;
883 
884 	mutex_lock(&ubi->alc_mutex);
885 	err = leb_write_lock(ubi, vol_id, lnum);
886 	if (err)
887 		goto out_mutex;
888 
889 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
890 	vid_hdr->vol_id = cpu_to_be32(vol_id);
891 	vid_hdr->lnum = cpu_to_be32(lnum);
892 	vid_hdr->compat = ubi_get_compat(ubi, vol_id);
893 	vid_hdr->data_pad = cpu_to_be32(vol->data_pad);
894 
895 	crc = crc32(UBI_CRC32_INIT, buf, len);
896 	vid_hdr->vol_type = UBI_VID_DYNAMIC;
897 	vid_hdr->data_size = cpu_to_be32(len);
898 	vid_hdr->copy_flag = 1;
899 	vid_hdr->data_crc = cpu_to_be32(crc);
900 
901 retry:
902 	pnum = ubi_wl_get_peb(ubi, dtype);
903 	if (pnum < 0) {
904 		err = pnum;
905 		goto out_leb_unlock;
906 	}
907 
908 	dbg_eba("change LEB %d:%d, PEB %d, write VID hdr to PEB %d",
909 		vol_id, lnum, vol->eba_tbl[lnum], pnum);
910 
911 	err = ubi_io_write_vid_hdr(ubi, pnum, vid_hdr);
912 	if (err) {
913 		ubi_warn("failed to write VID header to LEB %d:%d, PEB %d",
914 			 vol_id, lnum, pnum);
915 		goto write_error;
916 	}
917 
918 	err = ubi_io_write_data(ubi, buf, pnum, 0, len);
919 	if (err) {
920 		ubi_warn("failed to write %d bytes of data to PEB %d",
921 			 len, pnum);
922 		goto write_error;
923 	}
924 
925 	if (vol->eba_tbl[lnum] >= 0) {
926 		err = ubi_wl_put_peb(ubi, vol->eba_tbl[lnum], 1);
927 		if (err)
928 			goto out_leb_unlock;
929 	}
930 
931 	vol->eba_tbl[lnum] = pnum;
932 
933 out_leb_unlock:
934 	leb_write_unlock(ubi, vol_id, lnum);
935 out_mutex:
936 	mutex_unlock(&ubi->alc_mutex);
937 	ubi_free_vid_hdr(ubi, vid_hdr);
938 	return err;
939 
940 write_error:
941 	if (err != -EIO || !ubi->bad_allowed) {
942 		/*
943 		 * This flash device does not admit of bad eraseblocks or
944 		 * something nasty and unexpected happened. Switch to read-only
945 		 * mode just in case.
946 		 */
947 		ubi_ro_mode(ubi);
948 		goto out_leb_unlock;
949 	}
950 
951 	err = ubi_wl_put_peb(ubi, pnum, 1);
952 	if (err || ++tries > UBI_IO_RETRIES) {
953 		ubi_ro_mode(ubi);
954 		goto out_leb_unlock;
955 	}
956 
957 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
958 	ubi_msg("try another PEB");
959 	goto retry;
960 }
961 
962 /**
963  * ubi_eba_copy_leb - copy logical eraseblock.
964  * @ubi: UBI device description object
965  * @from: physical eraseblock number from where to copy
966  * @to: physical eraseblock number where to copy
967  * @vid_hdr: VID header of the @from physical eraseblock
968  *
969  * This function copies logical eraseblock from physical eraseblock @from to
970  * physical eraseblock @to. The @vid_hdr buffer may be changed by this
971  * function. Returns:
972  *   o %0  in case of success;
973  *   o %1 if the operation was canceled and should be tried later (e.g.,
974  *     because a bit-flip was detected at the target PEB);
975  *   o %2 if the volume is being deleted and this LEB should not be moved.
976  */
977 int ubi_eba_copy_leb(struct ubi_device *ubi, int from, int to,
978 		     struct ubi_vid_hdr *vid_hdr)
979 {
980 	int err, vol_id, lnum, data_size, aldata_size, idx;
981 	struct ubi_volume *vol;
982 	uint32_t crc;
983 
984 	vol_id = be32_to_cpu(vid_hdr->vol_id);
985 	lnum = be32_to_cpu(vid_hdr->lnum);
986 
987 	dbg_eba("copy LEB %d:%d, PEB %d to PEB %d", vol_id, lnum, from, to);
988 
989 	if (vid_hdr->vol_type == UBI_VID_STATIC) {
990 		data_size = be32_to_cpu(vid_hdr->data_size);
991 		aldata_size = ALIGN(data_size, ubi->min_io_size);
992 	} else
993 		data_size = aldata_size =
994 			    ubi->leb_size - be32_to_cpu(vid_hdr->data_pad);
995 
996 	idx = vol_id2idx(ubi, vol_id);
997 	spin_lock(&ubi->volumes_lock);
998 	/*
999 	 * Note, we may race with volume deletion, which means that the volume
1000 	 * this logical eraseblock belongs to might be being deleted. Since the
1001 	 * volume deletion unmaps all the volume's logical eraseblocks, it will
1002 	 * be locked in 'ubi_wl_put_peb()' and wait for the WL worker to finish.
1003 	 */
1004 	vol = ubi->volumes[idx];
1005 	if (!vol) {
1006 		/* No need to do further work, cancel */
1007 		dbg_eba("volume %d is being removed, cancel", vol_id);
1008 		spin_unlock(&ubi->volumes_lock);
1009 		return 2;
1010 	}
1011 	spin_unlock(&ubi->volumes_lock);
1012 
1013 	/*
1014 	 * We do not want anybody to write to this logical eraseblock while we
1015 	 * are moving it, so lock it.
1016 	 *
1017 	 * Note, we are using non-waiting locking here, because we cannot sleep
1018 	 * on the LEB, since it may cause deadlocks. Indeed, imagine a task is
1019 	 * unmapping the LEB which is mapped to the PEB we are going to move
1020 	 * (@from). This task locks the LEB and goes sleep in the
1021 	 * 'ubi_wl_put_peb()' function on the @ubi->move_mutex. In turn, we are
1022 	 * holding @ubi->move_mutex and go sleep on the LEB lock. So, if the
1023 	 * LEB is already locked, we just do not move it and return %1.
1024 	 */
1025 	err = leb_write_trylock(ubi, vol_id, lnum);
1026 	if (err) {
1027 		dbg_eba("contention on LEB %d:%d, cancel", vol_id, lnum);
1028 		return err;
1029 	}
1030 
1031 	/*
1032 	 * The LEB might have been put meanwhile, and the task which put it is
1033 	 * probably waiting on @ubi->move_mutex. No need to continue the work,
1034 	 * cancel it.
1035 	 */
1036 	if (vol->eba_tbl[lnum] != from) {
1037 		dbg_eba("LEB %d:%d is no longer mapped to PEB %d, mapped to "
1038 			"PEB %d, cancel", vol_id, lnum, from,
1039 			vol->eba_tbl[lnum]);
1040 		err = 1;
1041 		goto out_unlock_leb;
1042 	}
1043 
1044 	/*
1045 	 * OK, now the LEB is locked and we can safely start moving iy. Since
1046 	 * this function utilizes thie @ubi->peb1_buf buffer which is shared
1047 	 * with some other functions, so lock the buffer by taking the
1048 	 * @ubi->buf_mutex.
1049 	 */
1050 	mutex_lock(&ubi->buf_mutex);
1051 	dbg_eba("read %d bytes of data", aldata_size);
1052 	err = ubi_io_read_data(ubi, ubi->peb_buf1, from, 0, aldata_size);
1053 	if (err && err != UBI_IO_BITFLIPS) {
1054 		ubi_warn("error %d while reading data from PEB %d",
1055 			 err, from);
1056 		goto out_unlock_buf;
1057 	}
1058 
1059 	/*
1060 	 * Now we have got to calculate how much data we have to to copy. In
1061 	 * case of a static volume it is fairly easy - the VID header contains
1062 	 * the data size. In case of a dynamic volume it is more difficult - we
1063 	 * have to read the contents, cut 0xFF bytes from the end and copy only
1064 	 * the first part. We must do this to avoid writing 0xFF bytes as it
1065 	 * may have some side-effects. And not only this. It is important not
1066 	 * to include those 0xFFs to CRC because later the they may be filled
1067 	 * by data.
1068 	 */
1069 	if (vid_hdr->vol_type == UBI_VID_DYNAMIC)
1070 		aldata_size = data_size =
1071 			ubi_calc_data_len(ubi, ubi->peb_buf1, data_size);
1072 
1073 	cond_resched();
1074 	crc = crc32(UBI_CRC32_INIT, ubi->peb_buf1, data_size);
1075 	cond_resched();
1076 
1077 	/*
1078 	 * It may turn out to me that the whole @from physical eraseblock
1079 	 * contains only 0xFF bytes. Then we have to only write the VID header
1080 	 * and do not write any data. This also means we should not set
1081 	 * @vid_hdr->copy_flag, @vid_hdr->data_size, and @vid_hdr->data_crc.
1082 	 */
1083 	if (data_size > 0) {
1084 		vid_hdr->copy_flag = 1;
1085 		vid_hdr->data_size = cpu_to_be32(data_size);
1086 		vid_hdr->data_crc = cpu_to_be32(crc);
1087 	}
1088 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
1089 
1090 	err = ubi_io_write_vid_hdr(ubi, to, vid_hdr);
1091 	if (err)
1092 		goto out_unlock_buf;
1093 
1094 	cond_resched();
1095 
1096 	/* Read the VID header back and check if it was written correctly */
1097 	err = ubi_io_read_vid_hdr(ubi, to, vid_hdr, 1);
1098 	if (err) {
1099 		if (err != UBI_IO_BITFLIPS)
1100 			ubi_warn("cannot read VID header back from PEB %d", to);
1101 		else
1102 			err = 1;
1103 		goto out_unlock_buf;
1104 	}
1105 
1106 	if (data_size > 0) {
1107 		err = ubi_io_write_data(ubi, ubi->peb_buf1, to, 0, aldata_size);
1108 		if (err)
1109 			goto out_unlock_buf;
1110 
1111 		cond_resched();
1112 
1113 		/*
1114 		 * We've written the data and are going to read it back to make
1115 		 * sure it was written correctly.
1116 		 */
1117 
1118 		err = ubi_io_read_data(ubi, ubi->peb_buf2, to, 0, aldata_size);
1119 		if (err) {
1120 			if (err != UBI_IO_BITFLIPS)
1121 				ubi_warn("cannot read data back from PEB %d",
1122 					 to);
1123 			else
1124 				err = 1;
1125 			goto out_unlock_buf;
1126 		}
1127 
1128 		cond_resched();
1129 
1130 		if (memcmp(ubi->peb_buf1, ubi->peb_buf2, aldata_size)) {
1131 			ubi_warn("read data back from PEB %d - it is different",
1132 				 to);
1133 			goto out_unlock_buf;
1134 		}
1135 	}
1136 
1137 	ubi_assert(vol->eba_tbl[lnum] == from);
1138 	vol->eba_tbl[lnum] = to;
1139 
1140 out_unlock_buf:
1141 	mutex_unlock(&ubi->buf_mutex);
1142 out_unlock_leb:
1143 	leb_write_unlock(ubi, vol_id, lnum);
1144 	return err;
1145 }
1146 
1147 /**
1148  * ubi_eba_init_scan - initialize the EBA unit using scanning information.
1149  * @ubi: UBI device description object
1150  * @si: scanning information
1151  *
1152  * This function returns zero in case of success and a negative error code in
1153  * case of failure.
1154  */
1155 int ubi_eba_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
1156 {
1157 	int i, j, err, num_volumes;
1158 	struct ubi_scan_volume *sv;
1159 	struct ubi_volume *vol;
1160 	struct ubi_scan_leb *seb;
1161 	struct rb_node *rb;
1162 
1163 	dbg_eba("initialize EBA unit");
1164 
1165 	spin_lock_init(&ubi->ltree_lock);
1166 	mutex_init(&ubi->alc_mutex);
1167 	ubi->ltree = RB_ROOT;
1168 
1169 	ubi->global_sqnum = si->max_sqnum + 1;
1170 	num_volumes = ubi->vtbl_slots + UBI_INT_VOL_COUNT;
1171 
1172 	for (i = 0; i < num_volumes; i++) {
1173 		vol = ubi->volumes[i];
1174 		if (!vol)
1175 			continue;
1176 
1177 		cond_resched();
1178 
1179 		vol->eba_tbl = kmalloc(vol->reserved_pebs * sizeof(int),
1180 				       GFP_KERNEL);
1181 		if (!vol->eba_tbl) {
1182 			err = -ENOMEM;
1183 			goto out_free;
1184 		}
1185 
1186 		for (j = 0; j < vol->reserved_pebs; j++)
1187 			vol->eba_tbl[j] = UBI_LEB_UNMAPPED;
1188 
1189 		sv = ubi_scan_find_sv(si, idx2vol_id(ubi, i));
1190 		if (!sv)
1191 			continue;
1192 
1193 		ubi_rb_for_each_entry(rb, seb, &sv->root, u.rb) {
1194 			if (seb->lnum >= vol->reserved_pebs)
1195 				/*
1196 				 * This may happen in case of an unclean reboot
1197 				 * during re-size.
1198 				 */
1199 				ubi_scan_move_to_list(sv, seb, &si->erase);
1200 			vol->eba_tbl[seb->lnum] = seb->pnum;
1201 		}
1202 	}
1203 
1204 	if (ubi->avail_pebs < EBA_RESERVED_PEBS) {
1205 		ubi_err("no enough physical eraseblocks (%d, need %d)",
1206 			ubi->avail_pebs, EBA_RESERVED_PEBS);
1207 		err = -ENOSPC;
1208 		goto out_free;
1209 	}
1210 	ubi->avail_pebs -= EBA_RESERVED_PEBS;
1211 	ubi->rsvd_pebs += EBA_RESERVED_PEBS;
1212 
1213 	if (ubi->bad_allowed) {
1214 		ubi_calculate_reserved(ubi);
1215 
1216 		if (ubi->avail_pebs < ubi->beb_rsvd_level) {
1217 			/* No enough free physical eraseblocks */
1218 			ubi->beb_rsvd_pebs = ubi->avail_pebs;
1219 			ubi_warn("cannot reserve enough PEBs for bad PEB "
1220 				 "handling, reserved %d, need %d",
1221 				 ubi->beb_rsvd_pebs, ubi->beb_rsvd_level);
1222 		} else
1223 			ubi->beb_rsvd_pebs = ubi->beb_rsvd_level;
1224 
1225 		ubi->avail_pebs -= ubi->beb_rsvd_pebs;
1226 		ubi->rsvd_pebs  += ubi->beb_rsvd_pebs;
1227 	}
1228 
1229 	dbg_eba("EBA unit is initialized");
1230 	return 0;
1231 
1232 out_free:
1233 	for (i = 0; i < num_volumes; i++) {
1234 		if (!ubi->volumes[i])
1235 			continue;
1236 		kfree(ubi->volumes[i]->eba_tbl);
1237 	}
1238 	return err;
1239 }
1240 
1241 /**
1242  * ubi_eba_close - close EBA unit.
1243  * @ubi: UBI device description object
1244  */
1245 void ubi_eba_close(const struct ubi_device *ubi)
1246 {
1247 	int i, num_volumes = ubi->vtbl_slots + UBI_INT_VOL_COUNT;
1248 
1249 	dbg_eba("close EBA unit");
1250 
1251 	for (i = 0; i < num_volumes; i++) {
1252 		if (!ubi->volumes[i])
1253 			continue;
1254 		kfree(ubi->volumes[i]->eba_tbl);
1255 	}
1256 }
1257