UBI : Atomic change LEB

UBI : Atomic change LEB

[Brijesh Singh]

I think there is a problem in atomic change LEB.
I was trying to think how ubi will behave when device is full.
Suppose device is full.And
LEBn maps to pebn
           i.e. Ln->pn
If we used automic_change_leb, wear-levelling has no free blocks as
all lebs are mapped to pebs.And no change in LEB is possible to any
LEB.
I think  we will need atleast one extra block at any instance of time
to avoid this situation.
This is similar to block movement situation where we need extra block
for block movement.

Code Snip:
    pnum = ubi_wl_get_peb(ubi, dtype);
>>Asking a new block before unmapping.
>>Wear-levelling has got no block.Logically we should get the block as
far as people are writing to Logical space provided by UBI

    if (pnum < 0) {
        ubi_free_vid_hdr(ubi, vid_hdr);
        leb_write_unlock(ubi, vol_id, lnum);
        return pnum;
    }

    dbg_eba("change LEB %d:%d, PEB %d, write VID hdr to PEB %d",
        vol_id, lnum, vol->eba_tbl[lnum], pnum);

    err = ubi_io_write_vid_hdr(ubi, pnum, vid_hdr);
    if (err) {
        ubi_warn("failed to write VID header to LEB %d:%d, PEB %d",
             vol_id, lnum, pnum);
        goto write_error;
    }

    err = ubi_io_write_data(ubi, buf, pnum, 0, len);
    if (err) {
        ubi_warn("failed to write %d bytes of data to PEB %d",
             len, pnum);
        goto write_error;
    }
>>>> Freeing the block after new is written to provide automicity..

    if (vol->eba_tbl[lnum] >= 0) {
        err = ubi_wl_put_peb(ubi, vol->eba_tbl[lnum], 1);
        if (err) {
            ubi_free_vid_hdr(ubi, vid_hdr);
            leb_write_unlock(ubi, vol_id, lnum);
            return err;
        }
    }

    vol->eba_tbl[lnum] = pnum;
    leb_write_unlock(ubi, vol_id, lnum);
    ubi_free_vid_hdr(ubi, vid_hdr);
    return 0;

Re: UBI : Atomic change LEB

[Artem Bityutskiy]

Hi,

On Thu, 2007-09-13 at 13:32 +0530, Brijesh Singh wrote:
> I think there is a problem in atomic change LEB.
> I was trying to think how ubi will behave when device is full.
> Suppose device is full.And
> LEBn maps to pebn
>            i.e. Ln->pn
> If we used automic_change_leb, wear-levelling has no free blocks as
> all lebs are mapped to pebs.And no change in LEB is possible to any
> LEB.
> I think  we will need atleast one extra block at any instance of time
> to avoid this situation.
> This is similar to block movement situation where we need extra block
> for block movement.

yeah, you are right, thank you! The below patch should fix the problem.
Comments?

>From f02c2e8a10838d80c763f6ccd65398cccd3cfac0 Mon Sep 17 00:00:00 2001
From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Date: Thu, 13 Sep 2007 14:28:14 +0300
Subject: [PATCH] UBI: fix atomic LEB change problems

When the UBI device is nearly full, i.e. all LEBs are mapped, we have
only one spare LEB left - the one we reserved for WL purposes. Well,
I do not count the LEBs which were reserved for bad PEB handling -
suppose NOR flash for simplicity. If an "atomic LEB change operation"
is run, and the WL unit is moving a LEB, we have no spare LEBs to
finish the operation and fail, which is not good. Moreover, if there
are 2 or more simultanious "atomic LEB change" requests, only one of
them has chances to succeed, the other will fail with -ENOSPC. Not
good either.

This patch does 2 things:
1. Reserves one PEB for the "atomic LEB change" operation.
2. Serealize the operations so that only on of them may run
   at a time (by means of a mutex).

Pointed-to-by: Brijesh Singh <brijesh.s.singh@gmail.com>
Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 drivers/mtd/ubi/eba.c |   48 +++++++++++++++++++++++++++++-------------------
 drivers/mtd/ubi/ubi.h |    6 ++++--
 2 files changed, 33 insertions(+), 21 deletions(-)

diff --git a/drivers/mtd/ubi/eba.c b/drivers/mtd/ubi/eba.c
index 81bb6a3..7b7add6 100644
--- a/drivers/mtd/ubi/eba.c
+++ b/drivers/mtd/ubi/eba.c
@@ -46,6 +46,9 @@
 #include <linux/err.h>
 #include "ubi.h"
 
+/* Number of physical eraseblocks reserved for atomic LEB change operation */
+#define EBA_RESERVED_PEBS 1
+
 /**
  * struct ltree_entry - an entry in the lock tree.
  * @rb: links RB-tree nodes
@@ -827,6 +830,9 @@ write_error:
  * data, which has to be aligned. This function guarantees that in case of an
  * unclean reboot the old contents is preserved. Returns zero in case of
  * success and a negative error code in case of failure.
+ *
+ * UBI reserves one LEB for the "atomic LEB change" operation, so only one
+ * LEB change may be done at a time. This is ensured by @ubi->alc_mutex.
  */
 int ubi_eba_atomic_leb_change(struct ubi_device *ubi, int vol_id, int lnum,
 			      const void *buf, int len, int dtype)
@@ -843,11 +849,10 @@ int ubi_eba_atomic_leb_change(struct ubi_device *ubi, int vol_id, int lnum,
 	if (!vid_hdr)
 		return -ENOMEM;
 
+	mutex_lock(&ubi->alc_mutex);
 	err = leb_write_lock(ubi, vol_id, lnum);
-	if (err) {
-		ubi_free_vid_hdr(ubi, vid_hdr);
-		return err;
-	}
+	if (err)
+		goto out_mutex;
 
 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
 	vid_hdr->vol_id = cpu_to_be32(vol_id);
@@ -864,9 +869,8 @@ int ubi_eba_atomic_leb_change(struct ubi_device *ubi, int vol_id, int lnum,
 retry:
 	pnum = ubi_wl_get_peb(ubi, dtype);
 	if (pnum < 0) {
-		ubi_free_vid_hdr(ubi, vid_hdr);
-		leb_write_unlock(ubi, vol_id, lnum);
-		return pnum;
+		err = pnum;
+		goto out_leb_unlock;
 	}
 
 	dbg_eba("change LEB %d:%d, PEB %d, write VID hdr to PEB %d",
@@ -888,17 +892,18 @@ retry:
 
 	if (vol->eba_tbl[lnum] >= 0) {
 		err = ubi_wl_put_peb(ubi, vol->eba_tbl[lnum], 1);
-		if (err) {
-			ubi_free_vid_hdr(ubi, vid_hdr);
-			leb_write_unlock(ubi, vol_id, lnum);
-			return err;
-		}
+		if (err)
+			goto out_leb_unlock;
 	}
 
 	vol->eba_tbl[lnum] = pnum;
+
+out_leb_unlock:
 	leb_write_unlock(ubi, vol_id, lnum);
+out_mutex:
+	mutex_unlock(&ubi->alc_mutex);
 	ubi_free_vid_hdr(ubi, vid_hdr);
-	return 0;
+	return err;
 
 write_error:
 	if (err != -EIO || !ubi->bad_allowed) {
@@ -908,17 +913,13 @@ write_error:
 		 * mode just in case.
 		 */
 		ubi_ro_mode(ubi);
-		leb_write_unlock(ubi, vol_id, lnum);
-		ubi_free_vid_hdr(ubi, vid_hdr);
-		return err;
+		goto out_leb_unlock;
 	}
 
 	err = ubi_wl_put_peb(ubi, pnum, 1);
 	if (err || ++tries > UBI_IO_RETRIES) {
 		ubi_ro_mode(ubi);
-		leb_write_unlock(ubi, vol_id, lnum);
-		ubi_free_vid_hdr(ubi, vid_hdr);
-		return err;
+		goto out_leb_unlock;
 	}
 
 	vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
@@ -1122,6 +1123,7 @@ int ubi_eba_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 	dbg_eba("initialize EBA unit");
 
 	spin_lock_init(&ubi->ltree_lock);
+	mutex_init(&ubi->alc_mutex);
 	ubi->ltree = RB_ROOT;
 
 	if (ubi_devices_cnt == 0) {
@@ -1183,6 +1185,14 @@ int ubi_eba_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
 		ubi->rsvd_pebs  += ubi->beb_rsvd_pebs;
 	}
 
+	if (ubi->avail_pebs < EBA_RESERVED_PEBS) {
+		ubi_err("no enough physical eraseblocks (%d, need %d)",
+			ubi->avail_pebs, EBA_RESERVED_PEBS);
+		goto out_free;
+	}
+	ubi->avail_pebs -= EBA_RESERVED_PEBS;
+	ubi->rsvd_pebs += EBA_RESERVED_PEBS;
+
 	dbg_eba("EBA unit is initialized");
 	return 0;
 
diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index cc01011..5e941a6 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -221,14 +221,15 @@ struct ubi_wl_entry;
  * @vtbl_slots: how many slots are available in the volume table
  * @vtbl_size: size of the volume table in bytes
  * @vtbl: in-RAM volume table copy
+ * @vtbl_mutex: protects on-flash volume table
  *
  * @max_ec: current highest erase counter value
  * @mean_ec: current mean erase counter value
  *
- * global_sqnum: global sequence number
+ * @global_sqnum: global sequence number
  * @ltree_lock: protects the lock tree and @global_sqnum
  * @ltree: the lock tree
- * @vtbl_mutex: protects on-flash volume table
+ * @alc_mutex: serializes "atomic LEB change" operations
  *
  * @used: RB-tree of used physical eraseblocks
  * @free: RB-tree of free physical eraseblocks
@@ -308,6 +309,7 @@ struct ubi_device {
 	unsigned long long global_sqnum;
 	spinlock_t ltree_lock;
 	struct rb_root ltree;
+	struct mutex alc_mutex;
 
 	/* Wear-leveling unit's stuff */
 	struct rb_root used;
-- 
1.5.0.6

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: UBI : Atomic change LEB

[Brijesh Singh]

Thank you Artem.
This seems like a good idea.This will certainly work
.
The only problem I see is
* this will serialize  all the automic changes.If some device supports
multiple writes in parrallel,we are locking it for no reason(We have
reason but hope we can find another option).Also we won't need
serialization when there are lots of spare blocks.

I can't see a better way right now.May be we should think over any
possible twik to solve it.

On 9/13/07, Artem Bityutskiy <dedekind@infradead.org> wrote:
> Hi,
>
> On Thu, 2007-09-13 at 13:32 +0530, Brijesh Singh wrote:
> > I think there is a problem in atomic change LEB.
> > I was trying to think how ubi will behave when device is full.
> > Suppose device is full.And
> > LEBn maps to pebn
> >            i.e. Ln->pn
> > If we used automic_change_leb, wear-levelling has no free blocks as
> > all lebs are mapped to pebs.And no change in LEB is possible to any
> > LEB.
> > I think  we will need atleast one extra block at any instance of time
> > to avoid this situation.
> > This is similar to block movement situation where we need extra block
> > for block movement.
>
> yeah, you are right, thank you! The below patch should fix the problem.
> Comments?
>
> >From f02c2e8a10838d80c763f6ccd65398cccd3cfac0 Mon Sep 17 00:00:00 2001
> From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> Date: Thu, 13 Sep 2007 14:28:14 +0300
> Subject: [PATCH] UBI: fix atomic LEB change problems
>
> When the UBI device is nearly full, i.e. all LEBs are mapped, we have
> only one spare LEB left - the one we reserved for WL purposes. Well,
> I do not count the LEBs which were reserved for bad PEB handling -
> suppose NOR flash for simplicity. If an "atomic LEB change operation"
> is run, and the WL unit is moving a LEB, we have no spare LEBs to
> finish the operation and fail, which is not good. Moreover, if there
> are 2 or more simultanious "atomic LEB change" requests, only one of
> them has chances to succeed, the other will fail with -ENOSPC. Not
> good either.
>
> This patch does 2 things:
> 1. Reserves one PEB for the "atomic LEB change" operation.
> 2. Serealize the operations so that only on of them may run
>    at a time (by means of a mutex).
>
> Pointed-to-by: Brijesh Singh <brijesh.s.singh@gmail.com>
> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> ---
>  drivers/mtd/ubi/eba.c |   48 +++++++++++++++++++++++++++++-------------------
>  drivers/mtd/ubi/ubi.h |    6 ++++--
>  2 files changed, 33 insertions(+), 21 deletions(-)
>
> diff --git a/drivers/mtd/ubi/eba.c b/drivers/mtd/ubi/eba.c
> index 81bb6a3..7b7add6 100644
> --- a/drivers/mtd/ubi/eba.c
> +++ b/drivers/mtd/ubi/eba.c
> @@ -46,6 +46,9 @@
>  #include <linux/err.h>
>  #include "ubi.h"
>
> +/* Number of physical eraseblocks reserved for atomic LEB change operation */
> +#define EBA_RESERVED_PEBS 1
> +
>  /**
>   * struct ltree_entry - an entry in the lock tree.
>   * @rb: links RB-tree nodes
> @@ -827,6 +830,9 @@ write_error:
>   * data, which has to be aligned. This function guarantees that in case of an
>   * unclean reboot the old contents is preserved. Returns zero in case of
>   * success and a negative error code in case of failure.
> + *
> + * UBI reserves one LEB for the "atomic LEB change" operation, so only one
> + * LEB change may be done at a time. This is ensured by @ubi->alc_mutex.
>   */
>  int ubi_eba_atomic_leb_change(struct ubi_device *ubi, int vol_id, int lnum,
>                               const void *buf, int len, int dtype)
> @@ -843,11 +849,10 @@ int ubi_eba_atomic_leb_change(struct ubi_device *ubi, int vol_id, int lnum,
>         if (!vid_hdr)
>                 return -ENOMEM;
>
> +       mutex_lock(&ubi->alc_mutex);
>         err = leb_write_lock(ubi, vol_id, lnum);
> -       if (err) {
> -               ubi_free_vid_hdr(ubi, vid_hdr);
> -               return err;
> -       }
> +       if (err)
> +               goto out_mutex;
>
>         vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
>         vid_hdr->vol_id = cpu_to_be32(vol_id);
> @@ -864,9 +869,8 @@ int ubi_eba_atomic_leb_change(struct ubi_device *ubi, int vol_id, int lnum,
>  retry:
>         pnum = ubi_wl_get_peb(ubi, dtype);
>         if (pnum < 0) {
> -               ubi_free_vid_hdr(ubi, vid_hdr);
> -               leb_write_unlock(ubi, vol_id, lnum);
> -               return pnum;
> +               err = pnum;
> +               goto out_leb_unlock;
>         }
>
>         dbg_eba("change LEB %d:%d, PEB %d, write VID hdr to PEB %d",
> @@ -888,17 +892,18 @@ retry:
>
>         if (vol->eba_tbl[lnum] >= 0) {
>                 err = ubi_wl_put_peb(ubi, vol->eba_tbl[lnum], 1);
> -               if (err) {
> -                       ubi_free_vid_hdr(ubi, vid_hdr);
> -                       leb_write_unlock(ubi, vol_id, lnum);
> -                       return err;
> -               }
> +               if (err)
> +                       goto out_leb_unlock;
>         }
>
>         vol->eba_tbl[lnum] = pnum;
> +
> +out_leb_unlock:
>         leb_write_unlock(ubi, vol_id, lnum);
> +out_mutex:
> +       mutex_unlock(&ubi->alc_mutex);
>         ubi_free_vid_hdr(ubi, vid_hdr);
> -       return 0;
> +       return err;
>
>  write_error:
>         if (err != -EIO || !ubi->bad_allowed) {
> @@ -908,17 +913,13 @@ write_error:
>                  * mode just in case.
>                  */
>                 ubi_ro_mode(ubi);
> -               leb_write_unlock(ubi, vol_id, lnum);
> -               ubi_free_vid_hdr(ubi, vid_hdr);
> -               return err;
> +               goto out_leb_unlock;
>         }
>
>         err = ubi_wl_put_peb(ubi, pnum, 1);
>         if (err || ++tries > UBI_IO_RETRIES) {
>                 ubi_ro_mode(ubi);
> -               leb_write_unlock(ubi, vol_id, lnum);
> -               ubi_free_vid_hdr(ubi, vid_hdr);
> -               return err;
> +               goto out_leb_unlock;
>         }
>
>         vid_hdr->sqnum = cpu_to_be64(next_sqnum(ubi));
> @@ -1122,6 +1123,7 @@ int ubi_eba_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
>         dbg_eba("initialize EBA unit");
>
>         spin_lock_init(&ubi->ltree_lock);
> +       mutex_init(&ubi->alc_mutex);
>         ubi->ltree = RB_ROOT;
>
>         if (ubi_devices_cnt == 0) {
> @@ -1183,6 +1185,14 @@ int ubi_eba_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si)
>                 ubi->rsvd_pebs  += ubi->beb_rsvd_pebs;
>         }
>
> +       if (ubi->avail_pebs < EBA_RESERVED_PEBS) {
> +               ubi_err("no enough physical eraseblocks (%d, need %d)",
> +                       ubi->avail_pebs, EBA_RESERVED_PEBS);
> +               goto out_free;
> +       }
> +       ubi->avail_pebs -= EBA_RESERVED_PEBS;
> +       ubi->rsvd_pebs += EBA_RESERVED_PEBS;
> +
>         dbg_eba("EBA unit is initialized");
>         return 0;
>
> diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
> index cc01011..5e941a6 100644
> --- a/drivers/mtd/ubi/ubi.h
> +++ b/drivers/mtd/ubi/ubi.h
> @@ -221,14 +221,15 @@ struct ubi_wl_entry;
>   * @vtbl_slots: how many slots are available in the volume table
>   * @vtbl_size: size of the volume table in bytes
>   * @vtbl: in-RAM volume table copy
> + * @vtbl_mutex: protects on-flash volume table
>   *
>   * @max_ec: current highest erase counter value
>   * @mean_ec: current mean erase counter value
>   *
> - * global_sqnum: global sequence number
> + * @global_sqnum: global sequence number
>   * @ltree_lock: protects the lock tree and @global_sqnum
>   * @ltree: the lock tree
> - * @vtbl_mutex: protects on-flash volume table
> + * @alc_mutex: serializes "atomic LEB change" operations
>   *
>   * @used: RB-tree of used physical eraseblocks
>   * @free: RB-tree of free physical eraseblocks
> @@ -308,6 +309,7 @@ struct ubi_device {
>         unsigned long long global_sqnum;
>         spinlock_t ltree_lock;
>         struct rb_root ltree;
> +       struct mutex alc_mutex;
>
>         /* Wear-leveling unit's stuff */
>         struct rb_root used;
> --
> 1.5.0.6
>
> --
> Best regards,
> Artem Bityutskiy (Битюцкий Артём)
>
>

Re: UBI : Atomic change LEB

[Artem Bityutskiy]

On Thu, 2007-09-13 at 18:32 +0530, Brijesh Singh wrote:
> Thank you Artem.
> This seems like a good idea.This will certainly work
> .
> The only problem I see is
> * this will serialize  all the automic changes.If some device supports
> multiple writes in parrallel,we are locking it for no reason(We have
> reason but hope we can find another option).Also we won't need
> serialization when there are lots of spare blocks.

Well, this is not a big problem with the existing code base: mtd anyway
locks whole chip when doing I/O, and there are not users of this call
except of UBIFS which will not suffer much.

Also, if this is a problem for someone, we can always reserve N PEBs
for the atomic LEB change operation, and allow N tasks to do this
operation at a time. This is not difficult, we just need to use
something a bit more complex then a mutex.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)

Re: UBI : Atomic change LEB

[Jamie Lokier]

Brijesh Singh wrote:
> Thank you Artem.
> This seems like a good idea.This will certainly work
> .
> The only problem I see is
> * this will serialize  all the automic changes.If some device supports
> multiple writes in parrallel,we are locking it for no reason(We have
> reason but hope we can find another option).Also we won't need
> serialization when there are lots of spare blocks.
> 
> I can't see a better way right now.May be we should think over any
> possible twik to solve it.

Could you use a read-write lock, instead of a mutex?

Lock for "read" (meaning shared) when writing to the MTD device.  Lock
for "write" (meaning exclusive) when erasing.  Then all erases are
serialised, and writes can go in parallel.

Would that solve the locking problems?

If a device can support multiple erases in parallel as well, then
you'd want something more complicated.

-- Jamie

Re: UBI : Atomic change LEB

[Artem Bityutskiy]

On Thu, 2007-09-13 at 15:38 +0100, Jamie Lokier wrote:
> Could you use a read-write lock, instead of a mutex?
> 
> Lock for "read" (meaning shared) when writing to the MTD device.  Lock
> for "write" (meaning exclusive) when erasing.  Then all erases are
> serialised, and writes can go in parallel.
> 
> Would that solve the locking problems?
> 
> If a device can support multiple erases in parallel as well, then
> you'd want something more complicated.

Usual LEB read/write/erase _already_ have per-LEB RW locking which is
actually even too much. We are talking only about LEB atomic change
operation, which is special.

-- 
Best regards,
Artem Bityutskiy (Битюцкий Артём)