[PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[xiaochuan-xu]

>From e3af46580d374fc5da79212c17ef9f0179299bd0 Mon Sep 17 00:00:00 2001
From: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>
Date: Tue, 9 Dec 2008 19:27:40 +0800
Subject: [PATCH] Adjust severial macros

In order to fulfill the identical function of the currenty
prot RB-tree. *_PROTECTION macros are increased respectively

Signed-off-by: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>
---
 drivers/mtd/ubi/wl.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 0b1e8c7..603435f 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -130,9 +130,9 @@
  * How many erase cycles are short term, unknown, and long term physical
  * eraseblocks protected.
  */
-#define ST_PROTECTION 16
-#define U_PROTECTION  10
-#define LT_PROTECTION 4
+#define ST_PROTECTION 17
+#define U_PROTECTION  11
+#define LT_PROTECTION 5
 
 /* Number of prot lists, must be bigger than 'ST_PROTECTION' */
 #define PROT_LISTS_LEN (ST_PROTECTION+1)
-- 
1.5.3.2


-- 
Yours sincerely
xiaochuan-xu(cqu.edu.cn)

Re: [PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[Artem Bityutskiy]

On Tue, 2008-12-09 at 19:46 +0800, xiaochuan-xu wrote:
> >From e3af46580d374fc5da79212c17ef9f0179299bd0 Mon Sep 17 00:00:00 2001
> From: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>
> Date: Tue, 9 Dec 2008 19:27:40 +0800
> Subject: [PATCH] Adjust severial macros
> 
> In order to fulfill the identical function of the currenty
> prot RB-tree. *_PROTECTION macros are increased respectively
> 
> Signed-off-by: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>
> ---
>  drivers/mtd/ubi/wl.c |    6 +++---
>  1 files changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
> index 0b1e8c7..603435f 100644
> --- a/drivers/mtd/ubi/wl.c
> +++ b/drivers/mtd/ubi/wl.c
> @@ -130,9 +130,9 @@
>   * How many erase cycles are short term, unknown, and long term physical
>   * eraseblocks protected.
>   */
> -#define ST_PROTECTION 16
> -#define U_PROTECTION  10
> -#define LT_PROTECTION 4
> +#define ST_PROTECTION 17
> +#define U_PROTECTION  11
> +#define LT_PROTECTION 5

I doubt these constants make much sense. I would suggest you to get rid
of them and simplify things. Let's have only one constant instead of 3.
This will allow us to implement efficient protection queue which you
will not need to walk at all.

So I'd suggest you to send a separate "preparation" patch which
introduces one constant instead of 3. E.g.,

#define PROTECTION 10

It may be re-named to PROT_LIST_LEN later, probably.

How does this plan sound to you?

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

Re: [PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[xiaochuan-xu]

> > +#define ST_PROTECTION 17
> > +#define U_PROTECTION  11
> > +#define LT_PROTECTION 5
> 
> I doubt these constants make much sense. I would suggest you to get rid
> of them and simplify things. Let's have only one constant instead of 3.


> This will allow us to implement efficient protection queue
>  which you will not need to walk at all.
Sorry, I don't quite follow this meaning.
You mean one protection list (not lists) could filfull the function?

> So I'd suggest you to send a separate "preparation" patch which
> introduces one constant instead of 3. E.g.,
> 
> #define PROTECTION 10
> 
> It may be re-named to PROT_LIST_LEN later, probably.
> 
> How does this plan sound to you?
> 

These three constants are the part of the whole Wear-leveling algorithm,
not only for the protection tree/lists. especially for the GET mothed. 
As far as I could see, Different type data should protect different
'time'. protection 'time' classification makes sense. By means of the
classification, we can implement some more improvement, for instance:

1. UBI_LONGTERM data's PEB may not be protected, but insert into the
USED RB-tree directly, whereas other type data should do.

2. We may split the @dtype into more sub-type. Take the UBI_UNKNOWN as
an example, it seems to have many UBI_UNKNOWN type date in the current
UBI/UBIFS implementation. We may be able to dynamic evaluate the real
type of these UBI_UNKNOWN data in the EBA Sub-system and then GET more
optimal PEB, although this seems to be not so easy.

fundamentally, the question, in my opinion, is not one or three
constants, but how much 'time' corresponding type data should be
protected.

Listen with your suggestion. Thanks.

-- 
Yours sincerely
xiaochuan-xu(cqu.edu.cn)

Re: [PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[Artem Bityutskiy]

On Wed, 2008-12-10 at 12:52 +0800, xiaochuan-xu wrote:
> > This will allow us to implement efficient protection queue
> >  which you will not need to walk at all.
> Sorry, I don't quite follow this meaning.
> You mean one protection list (not lists) could filfull the function?

I was thinking about a pipe-like design. When you want to protect a PEB,
you put it to the head of a pipe. This guarantees that it will go out of
the pipe after N erase cycles, where N is the length of the pipe (e.g.,
10). When any eraseblock is erased, it takes one element from the head
of the pipe.

Thus, you will not need to walk any list when in the erase worker.
You'll need to just take the element from the end of the pipe. Well,
some tricks are needed to guarantee that it always takes N erase cycles
for _any_ element to get out of the protection pipe. And the data
inserting / removing elements should be quick and O(1).

> These three constants are the part of the whole Wear-leveling algorithm,
> not only for the protection tree/lists. especially for the GET mothed. 
> As far as I could see, Different type data should protect different
> 'time'. protection 'time' classification makes sense. By means of the
> classification, we can implement some more improvement, for instance:
> 
> 1. UBI_LONGTERM data's PEB may not be protected, but insert into the
> USED RB-tree directly, whereas other type data should do.

Yes, I guess.

> 2. We may split the @dtype into more sub-type. Take the UBI_UNKNOWN as
> an example, it seems to have many UBI_UNKNOWN type date in the current
> UBI/UBIFS implementation. We may be able to dynamic evaluate the real
> type of these UBI_UNKNOWN data in the EBA Sub-system and then GET more
> optimal PEB, although this seems to be not so easy.

May be, but this is a separate thing.

> fundamentally, the question, in my opinion, is not one or three
> constants, but how much 'time' corresponding type data should be
> protected.

I think it does not matter much and we may use the same constant for
short term and unknown eraseblocks. I do not see much difference between
8 or 16. Does it really matter? We just want to prevent this eraseblock
from being moved for some reasonable "time". And everything depends on
work-load of course. So I think just using the same constant for all PEB
types is reasonable. This will be simpler.

But of course, the best way is to test things.

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

Re: [PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[xiaochuan-xu]

On Wed, 2008-12-10 at 10:44 +0200, Artem Bityutskiy wrote:
> 
> I think it does not matter much and we may use the same constant for
> short term and unknown eraseblocks. I do not see much difference
> between
> 8 or 16. Does it really matter? We just want to prevent this
> eraseblock
> from being moved for some reasonable "time". And everything depends on
> work-load of course. So I think just using the same constant for all
> PEB

My opposite experiment indicates that such unified-protection-time
method seems to be not better than the different-protection-time one in
run time. the system run time fluctuates. 

One major reason, I think, is short term (youngest) PEBs got together in
the protection "queue", when they wear out the protection time and be
flushed to used RB-tree, quantities of wear-leveling worker may trigger
one time. 

> types is reasonable. This will be simpler.
> 
> But of course, the best way is to test things.
-- 
Yours sincerely
xiaochuan-xu(cqu.edu.cn)

Re: [PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[Artem Bityutskiy]

On Wed, 2008-12-10 at 21:11 +0800, xiaochuan-xu wrote:
> On Wed, 2008-12-10 at 10:44 +0200, Artem Bityutskiy wrote:
> > 
> > I think it does not matter much and we may use the same constant for
> > short term and unknown eraseblocks. I do not see much difference
> > between
> > 8 or 16. Does it really matter? We just want to prevent this
> > eraseblock
> > from being moved for some reasonable "time". And everything depends on
> > work-load of course. So I think just using the same constant for all
> > PEB
> 
> My opposite experiment indicates that such unified-protection-time
> method seems to be not better than the different-protection-time one in
> run time. the system run time fluctuates. 

I guess you would have to write a very special test to see any difference.

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

Re: [PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[xiaochuan-xu]

On Mon, 2008-12-15 at 18:00 +0200, Artem Bityutskiy wrote:
> Amended and pushed to ubi-2.6.git tree.
Thanks!

These two sentences should switch in the 'ubi_wl_get_peb()' function:

-	prot_queue_add(ubi, e);
 	dbg_wl("PEB %d EC %d", e->pnum, e->ec);
+	prot_queue_add(ubi, e);

"get" message should print before "add to prot-queue",
which is more descriptive IMO.


>From 83811c383bf70039aae53e1bbc7311899ea4abcd Mon Sep 17 00:00:00 2001
From: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>
Date: Tue, 16 Dec 2008 10:10:20 +0800
Subject: [PATCH] several comments amendment

Signed-off-by: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>
---
 drivers/mtd/ubi/wl.c |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)

diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index d50060f..4fe3f25 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -56,7 +56,7 @@
  * As it was said, for the UBI sub-system all physical eraseblocks are either
  * "free" or "used". Free eraseblock are kept in the @wl->free RB-tree, while
  * used eraseblocks are kept in @wl->used or @wl->scrub RB-trees, or in
- * (temporarily) in the @wl->pq queue.
+ * (temporarily) the @wl->pq queue.
  *
  * When the WL sub-system returns a physical eraseblock, the physical
  * eraseblock is protected from being moved for some "time". For this reason,
@@ -143,7 +143,6 @@
  * struct ubi_work - UBI work description data structure.
  * @list: a link in the list of pending works
  * @func: worker function
- * @priv: private data of the worker function
  * @e: physical eraseblock to erase
  * @torture: if the physical eraseblock has to be tortured
  *
@@ -455,8 +454,8 @@ retry:
 	 * be protected from being moved for some time.
 	 */
 	rb_erase(&e->u.rb, &ubi->free);
-	prot_queue_add(ubi, e);
 	dbg_wl("PEB %d EC %d", e->pnum, e->ec);
+	prot_queue_add(ubi, e);
 	spin_unlock(&ubi->wl_lock);
 	return e->pnum;
 }
@@ -1223,7 +1222,7 @@ int ubi_wl_flush(struct ubi_device *ubi)
 	int err;
 
 	/*
-	 * Erase while the pending works queue is not empty, but not more then
+	 * Erase while the pending works queue is not empty, but not more than
 	 * the number of currently pending works.
 	 */
 	dbg_wl("flush (%d pending works)", ubi->works_count);
-- 
1.5.3.2



-- 
Yours sincerely
xiaochuan-xu(cqu.edu.cn)

Re: [PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[xiaochuan-xu]

>From e43d4e5cbaf1adb3af680a6dec53c142c68014ed Mon Sep 17 00:00:00 2001
From: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>
Date: Tue, 16 Dec 2008 10:44:07 +0800
Subject: [PATCH] delete idle varialbe abs_ec

@wl->abs_ec is useless any more in the Simplify Protection
PEB Queue implementation.

Signed-off-by: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>
---
 drivers/mtd/ubi/ubi.h |    2 --
 drivers/mtd/ubi/wl.c  |    1 -
 2 files changed, 0 insertions(+), 3 deletions(-)

diff --git a/drivers/mtd/ubi/ubi.h b/drivers/mtd/ubi/ubi.h
index a4b921b..4a8ec48 100644
--- a/drivers/mtd/ubi/ubi.h
+++ b/drivers/mtd/ubi/ubi.h
@@ -328,7 +328,6 @@ struct ubi_wl_entry;
  * @wl_scheduled: non-zero if the wear-leveling was scheduled
  * @lookuptbl: a table to quickly find a &struct ubi_wl_entry object for any
  *             physical eraseblock
- * @abs_ec: absolute erase counter
  * @move_from: physical eraseblock from where the data is being moved
  * @move_to: physical eraseblock where the data is being moved to
  * @move_to_put: if the "to" PEB was put
@@ -410,7 +409,6 @@ struct ubi_device {
 	struct rw_semaphore work_sem;
 	int wl_scheduled;
 	struct ubi_wl_entry **lookuptbl;
-	unsigned long long abs_ec;
 	struct ubi_wl_entry *move_from;
 	struct ubi_wl_entry *move_to;
 	int move_to_put;
diff --git a/drivers/mtd/ubi/wl.c b/drivers/mtd/ubi/wl.c
index 4fe3f25..0b5a595 100644
--- a/drivers/mtd/ubi/wl.c
+++ b/drivers/mtd/ubi/wl.c
@@ -982,7 +982,6 @@ static int erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk,
 		kfree(wl_wrk);
 
 		spin_lock(&ubi->wl_lock);
-		ubi->abs_ec += 1;
 		wl_tree_add(e, &ubi->free);
 		spin_unlock(&ubi->wl_lock);
 
-- 
1.5.3.2



On Mon, 2008-12-15 at 18:00 +0200, Artem Bityutskiy wrote:
> Amended and pushed to ubi-2.6.git tree. Please, check.
-- 
Yours sincerely
xiaochuan-xu(cqu.edu.cn)

Re: [PATCH 4/4] UBI WL-Subsys: Improvement in prot tree

[Artem Bityutskiy]

On Tue, 2008-12-16 at 10:48 +0800, xiaochuan-xu wrote:
> >From e43d4e5cbaf1adb3af680a6dec53c142c68014ed Mon Sep 17 00:00:00 2001
> From: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>
> Date: Tue, 16 Dec 2008 10:44:07 +0800
> Subject: [PATCH] delete idle varialbe abs_ec
> 
> @wl->abs_ec is useless any more in the Simplify Protection
> PEB Queue implementation.
> 
> Signed-off-by: Xiaochuan-Xu <xiaochuan-xu@cqu.edu.cn>

Applied, committed using git-commit -a --amend (changed your
original patch in-place).

Thanks.

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