[RFC] [PATCH] UBI: refine wear leveling logic

[RFC] [PATCH] UBI: refine wear leveling logic

[Alexander Schmidt]

Hi,

This patch addresses the handling of blocks that are put by the user
while they are moved by the wear leveling thread. The schedule_erase
function is now called by put_peb() itself instead of notifying the wear
leveling thread.

Comments are welcome...

Signed-off-by: Alexander Schmidt <alexs@linux.vnet.ibm.com>
---
 drivers/mtd/ubi/ubi.h |    2 -
 drivers/mtd/ubi/wl.c  |   77 ++++++++------------------------------------------
 2 files changed, 13 insertions(+), 66 deletions(-)

--- dedekind-ubi-2.6.orig/drivers/mtd/ubi/ubi.h
+++ dedekind-ubi-2.6/drivers/mtd/ubi/ubi.h
@@ -316,8 +316,6 @@ struct ubi_device {
 	unsigned long long abs_ec;
 	struct ubi_wl_entry *move_from;
 	struct ubi_wl_entry *move_to;
-	int move_from_put;
-	int move_to_put;
 	struct list_head works;
 	int works_count;
 	struct task_struct *bgt_thread;
--- dedekind-ubi-2.6.orig/drivers/mtd/ubi/wl.c
+++ dedekind-ubi-2.6/drivers/mtd/ubi/wl.c
@@ -793,7 +793,7 @@ static int schedule_erase(struct ubi_dev
 static int wear_leveling_worker(struct ubi_device *ubi, struct ubi_work *wrk,
 				int cancel)
 {
-	int err, put = 0;
+	int err;
 	struct ubi_wl_entry *e1, *e2;
 	struct ubi_vid_hdr *vid_hdr;
 
@@ -864,7 +864,6 @@ static int wear_leveling_worker(struct u
 
 	free_tree_del(ubi, e2);
 	ubi_assert(!ubi->move_from && !ubi->move_to);
-	ubi_assert(!ubi->move_to_put && !ubi->move_from_put);
 	ubi->move_from = e1;
 	ubi->move_to = e2;
 	spin_unlock(&ubi->wl_lock);
@@ -907,28 +906,11 @@ static int wear_leveling_worker(struct u
 
 	ubi_free_vid_hdr(ubi, vid_hdr);
 	spin_lock(&ubi->wl_lock);
-	if (unlikely(!ubi->move_to_put))
-		used_tree_add(ubi, e2);
-	else
-		put = 1;
+	used_tree_add(ubi, e2);
 	ubi->move_from = ubi->move_to = NULL;
-	ubi->move_from_put = ubi->move_to_put = 0;
 	ubi->wl_scheduled = 0;
 	spin_unlock(&ubi->wl_lock);
 
-	if (unlikely(put)) {
-		/*
-		 * Well, the target PEB was put meanwhile, schedule it for
-		 * erasure.
-		 */
-		dbg_wl("PEB %d was put meanwhile, erase", e2->pnum);
-		err = schedule_erase(ubi, e2, 0);
-		if (unlikely(err)) {
-			kmem_cache_free(wl_entries_slab, e2);
-			ubi_ro_mode(ubi);
-		}
-	}
-
 	err = schedule_erase(ubi, e1, 0);
 	if (unlikely(err)) {
 		kmem_cache_free(wl_entries_slab, e1);
@@ -950,27 +932,10 @@ error:
 	ubi_free_vid_hdr(ubi, vid_hdr);
 	spin_lock(&ubi->wl_lock);
 	ubi->wl_scheduled = 0;
-	if (ubi->move_from_put)
-		put = 1;
-	else
-		used_tree_add(ubi, e1);
+	used_tree_add(ubi, e1);
 	ubi->move_from = ubi->move_to = NULL;
-	ubi->move_from_put = ubi->move_to_put = 0;
 	spin_unlock(&ubi->wl_lock);
 
-	if (put) {
-		/*
-		 * Well, the target PEB was put meanwhile, schedule it for
-		 * erasure.
-		 */
-		dbg_wl("PEB %d was put meanwhile, erase", e1->pnum);
-		err = schedule_erase(ubi, e1, 0);
-		if (unlikely(err)) {
-			kmem_cache_free(wl_entries_slab, e1);
-			ubi_ro_mode(ubi);
-		}
-	}
-
 	err = schedule_erase(ubi, e2, 0);
 	if (unlikely(err)) {
 		kmem_cache_free(wl_entries_slab, e2);
@@ -1183,34 +1148,18 @@ int ubi_wl_put_peb(struct ubi_device *ub
 	if (unlikely(e == ubi->move_from)) {
 		/*
 		 * User is putting the physical eraseblock which was selected to
-		 * be moved. It will be scheduled for erasure in the
-		 * wear-leveling worker.
-		 */
-		dbg_wl("PEB %d is being moved", pnum);
-		ubi_assert(!ubi->move_from_put);
-		ubi->move_from_put = 1;
-		spin_unlock(&ubi->wl_lock);
-		return 0;
-	} else if (unlikely(e == ubi->move_to)) {
-		/*
-		 * User is putting the physical eraseblock which was selected
-		 * as the target the data is moved to. It may happen if the EBA
-		 * unit already re-mapped the LEB but the WL unit did has not
-		 * put the PEB to the "used" tree.
+		 * be moved. Schedule the destination block for erasure.
 		 */
-		dbg_wl("PEB %d is the target of data moving", pnum);
-		ubi_assert(!ubi->move_to_put);
-		ubi->move_to_put = 1;
-		spin_unlock(&ubi->wl_lock);
-		return 0;
-	} else {
-		if (in_wl_tree(e, &ubi->used))
-			used_tree_del(ubi, e);
-		else if (unlikely(in_wl_tree(e, &ubi->scrub)))
-			scrub_tree_del(ubi, e);
-		else
-			prot_tree_del(ubi, e->pnum);
+		dbg_wl("PEB %d is being moved");
+		e = ubi->move_to;
 	}
+
+	if (in_wl_tree(e, &ubi->used))
+		used_tree_del(ubi, e);
+	else if (unlikely(in_wl_tree(e, &ubi->scrub)))
+		scrub_tree_del(ubi, e);
+	else if (!in_wl_tree(e, &ubi->free))
+		prot_tree_del(ubi, e->pnum);
 	spin_unlock(&ubi->wl_lock);
 
 	err = schedule_erase(ubi, e, torture);

Re: [RFC] [PATCH] UBI: refine wear leveling logic

[Artem Bityutskiy]

Hi Alexander,

On Wed, 2007-03-28 at 15:47 +0200, Alexander Schmidt wrote:
> This patch addresses the handling of blocks that are put by the user
> while they are moved by the wear leveling thread. The schedule_erase
> function is now called by put_peb() itself instead of notifying the wear
> leveling thread.

May I ask you for more explanation why you think your code is correct?

> +
> +	if (in_wl_tree(e, &ubi->used))
> +		used_tree_del(ubi, e);
> +	else if (unlikely(in_wl_tree(e, &ubi->scrub)))
> +		scrub_tree_del(ubi, e);
> +	else if (!in_wl_tree(e, &ubi->free))
> +		prot_tree_del(ubi, e->pnum);
>  	spin_unlock(&ubi->wl_lock);
>  
>  	err = schedule_erase(ubi, e, torture);

Fine, you schedule this eraseblock for erasure. At the same time the the
WL worker moves data in there. The copy_leb() function will notice that
the LEB is unmapped, and won't do copy. Then the WL worker will insert
the eraseblock to a tree. At the same time the erase worker will insert
the same wl_entry to the free tree. One of the trees will be screwed-up.

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

Re: [RFC] [PATCH] UBI: refine wear leveling logic

[Alexander Schmidt]

Hi Artem,

On Thursday 29 March 2007, Artem Bityutskiy wrote:
> May I ask you for more explanation why you think your code is correct?

While writing this i assumed that erase and WL procedures are performed
sequentially (either by the background thread or, if the bgt is disabled,
by the produce_free_peb() function). Thank to your comment below I now
realised that erase/wl procedures could happen concurrently if the free
tree is empty and there are pending works (this is the only way that
could lead to your error scenario, right?).

If so then i propose to make get_peb() wait until the bgt produces a free
peb and not mix synchronous/asynchronous operations, as this would make
the code easier, IMO.

Regards,
Alex
> 
> > +
> > +	if (in_wl_tree(e, &ubi->used))
> > +		used_tree_del(ubi, e);
> > +	else if (unlikely(in_wl_tree(e, &ubi->scrub)))
> > +		scrub_tree_del(ubi, e);
> > +	else if (!in_wl_tree(e, &ubi->free))
> > +		prot_tree_del(ubi, e->pnum);
> >  	spin_unlock(&ubi->wl_lock);
> >  
> >  	err = schedule_erase(ubi, e, torture);
> 
> Fine, you schedule this eraseblock for erasure. At the same time the the
> WL worker moves data in there. The copy_leb() function will notice that
> the LEB is unmapped, and won't do copy. Then the WL worker will insert
> the eraseblock to a tree. At the same time the erase worker will insert
> the same wl_entry to the free tree. One of the trees will be screwed-up.
> 
> -- 
> Best regards,
> Artem Bityutskiy (Битюцкий Артём)
> 
> 

Re: [RFC] [PATCH] UBI: refine wear leveling logic

[Artem Bityutskiy]

Alexander Schmidt wrote:
> While writing this i assumed that erase and WL procedures are performed
> sequentially (either by the background thread or, if the bgt is disabled,
> by the produce_free_peb() function). Thank to your comment below I now
> realised that erase/wl procedures could happen concurrently if the free
> tree is empty and there are pending works (this is the only way that
> could lead to your error scenario, right?).

Yes, kind of.

> If so then i propose to make get_peb() wait until the bgt produces a free
> peb and not mix synchronous/asynchronous operations, as this would make
> the code easier, IMO.

It already does this AFAIK.

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

Re: [RFC] [PATCH] UBI: refine wear leveling logic

[Alexander Schmidt]

On Friday 30 March 2007, Artem Bityutskiy wrote:
> > If so then i propose to make get_peb() wait until the bgt produces a free
> > peb and not mix synchronous/asynchronous operations, as this would make
> > the code easier, IMO.
> 
> It already does this AFAIK.

In the current code, wl_get_peb() calls produce_free_peb() if the
free tree is empty and thereby performs a synchronous work (even if the
bgt is enabled). This is what I meant with "mixing" sync/async.

So I think making the user thread wait for the wl thread to free a peb
(e.g. by sleeping while waiting for a semaphore) could lead to a better
performance as the wl thread will likely finish its work before the user
thread has performed a whole work.

Regards,
Alex

Re: [RFC] [PATCH] UBI: refine wear leveling logic

[Artem Bityutskiy]

On Fri, 2007-03-30 at 16:40 +0200, Alexander Schmidt wrote:
> In the current code, wl_get_peb() calls produce_free_peb() if the
> free tree is empty and thereby performs a synchronous work (even if the
> bgt is enabled). This is what I meant with "mixing" sync/async.

OK, what's wring with this? We do not have eraseblocks, we produce them
synchronously.

We cannot rely on the thread - what if it was killed or its priority is
too low, but the requesting task needs eraseblocks ASAP.

> So I think making the user thread wait for the wl thread to free a peb
> (e.g. by sleeping while waiting for a semaphore) could lead to a better
> performance as the wl thread will likely finish its work before the user
> thread has performed a whole work.

Not necessarily. The current approach is safer.

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