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