[PATCH 0/6] md: Remove the hash tables from raid0.

[PATCH 0/6] md: Remove the hash tables from raid0.

[Andre Noll]

As mentioned by Neil, the raid0 hash table code does probably not
add any value. Moreover, it contains some rather strange sector_t
manipulations which are needed to setup and maintain the table.

This patch series against Neil's for-next tree as of yesterday removes
the hash table from the raid0 code.

Patch #1 replaces the hash table lookup by a simple function that
loops over all strip zones to find the zone that holds a given sector.
This change allows to get rid of the hash table itself (patch #2)
and of related fields of struct raid0_private_data (patch #3).

Patch #4 makes raid0 return a proper error code rather than -ENOMEM
in case the array could not be started for reasons other than memory
shortage.

The remaining two patches are simple cleanups that further simplify
the raid0 code a bit.

The patched kernel has been tested with a smallish raid0 array
consisting of five devices of varying sizes (created and filled with
contents by an unpatched kernel) and seems to work just fine. It
passes the raid0 tests of the mdadm test suite.

Please consider for inclusion.

 drivers/md/raid0.c |  150 ++++++++++++++--------------------------------------
 drivers/md/raid0.h |    4 --
 2 files changed, 39 insertions(+), 115 deletions(-)

Thanks
Andre

[PATCH 1/6] md: raid0: Replace hash table lookup by looping over all strip_zones.

[Andre Noll]

The number of strip_zones of a raid0 array is bounded by the number of
drives in the array and is in fact much smaller for typical setups. For
example, any raid0 array containing identical disks will have only
a single strip_zone.

Therefore, the hash tables which are used for quickly finding the
strip_zone that holds a particular sector are of questionable value
and add quite a bit of unnecessary complexity.

This patch replaces the hash table lookup by equivalent code which
simply loops over all strip zones to find the zone that holds the
given sector.

Subsequent cleanup patches will remove the hash table structure.

Signed-off-by: Andre Noll <maan@systemlinux.org>

 drivers/md/raid0.c |   32 +++++++++++++++++++-------------
 1 files changed, 19 insertions(+), 13 deletions(-)
-- 
1.5.4.3

[PATCH 2/6] md: raid0: Remove hash table.

[Andre Noll]

The raid0 hash table has become unused due to the changes in the
previous patch. This patch removes the hash table allocation and
setup code and kills the hash_table field of struct raid0_private_data.

Signed-off-by: Andre Noll <maan@systemlinux.org>

 drivers/md/raid0.c |   12 ------------
 drivers/md/raid0.h |    1 -
 2 files changed, 0 insertions(+), 13 deletions(-)
-- 
1.5.4.3

[PATCH 3/6] md: raid0: Remove hash spacing and sector shift.

[Andre Noll]

The "sector_shift" and "spacing" fields of struct raid0_private_data
were only used for the hash table lookups. So the removal of the
hash table allows get rid of these fields as well which simplifies
create_strip_zones() and raid0_run() quite a bit.

Signed-off-by: Andre Noll <maan@systemlinux.org>

 drivers/md/raid0.c |   63 +---------------------------------------------------
 drivers/md/raid0.h |    3 --
 2 files changed, 1 insertions(+), 65 deletions(-)
-- 
1.5.4.3

[PATCH 4/6] md: raid0: Make raid0_run() return a proper error code.

[Andre Noll]

Currently raid0_run() always returns -ENOMEM on errors. This is
incorrect as running the array might fail for other reasons, for
example because not all component devices were available.

This patch changes create_strip_zones() so that it returns a proper
error code (either -ENOMEM or -EINVAL) rather than 1 on errors and
makes raid0_run(), its single caller, return that value instead
of -ENOMEM.

Signed-off-by: Andre Noll <maan@systemlinux.org>

 drivers/md/raid0.c |   17 +++++++++--------
 1 files changed, 9 insertions(+), 8 deletions(-)
-- 
1.5.4.3

[PATCH 5/6] md: raid0: Kfree() strip_zone and devlist in create_strip_zones().

[Andre Noll]

It's cleaner to kfree() these in the same function where they are
allocated. This allows to simplify raid0_run() a bit which will be
done in the next patch.

Signed-off-by: Andre Noll <maan@systemlinux.org>

 drivers/md/raid0.c |   12 ++++++------
 1 files changed, 6 insertions(+), 6 deletions(-)
-- 
1.5.4.3

[PATCH 6/6] md: raid0: Simplify raid0_run().

[Andre Noll]

Get rid of the local variable "conf" and of an unnecessary cast.

Signed-off-by: Andre Noll <maan@systemlinux.org>

 drivers/md/raid0.c |   20 +++++++-------------
 1 files changed, 7 insertions(+), 13 deletions(-)
-- 
1.5.4.3

Re: [PATCH 0/6] md: Remove the hash tables from raid0.

[raz ben yehuda]

where are the patches ?

On Thu, 2009-05-14 at 11:30 +0200, Andre Noll wrote:
> As mentioned by Neil, the raid0 hash table code does probably not
> add any value. Moreover, it contains some rather strange sector_t
> manipulations which are needed to setup and maintain the table.
> 
> This patch series against Neil's for-next tree as of yesterday removes
> the hash table from the raid0 code.
> 
> Patch #1 replaces the hash table lookup by a simple function that
> loops over all strip zones to find the zone that holds a given sector.
> This change allows to get rid of the hash table itself (patch #2)
> and of related fields of struct raid0_private_data (patch #3).
> 
> Patch #4 makes raid0 return a proper error code rather than -ENOMEM
> in case the array could not be started for reasons other than memory
> shortage.
> 
> The remaining two patches are simple cleanups that further simplify
> the raid0 code a bit.
> 
> The patched kernel has been tested with a smallish raid0 array
> consisting of five devices of varying sizes (created and filled with
> contents by an unpatched kernel) and seems to work just fine. It
> passes the raid0 tests of the mdadm test suite.
> 
> Please consider for inclusion.
> 
>  drivers/md/raid0.c |  150 ++++++++++++++--------------------------------------
>  drivers/md/raid0.h |    4 --
>  2 files changed, 39 insertions(+), 115 deletions(-)
> 
> Thanks
> Andre

[PATCH 0/6] md: Remove the hash tables from raid0 V2 -- Introduction.

[Andre Noll]

As mentioned by Neil, the raid0 hash table does probably not add
any value and contains some rather strange code that manipulates the
various sector counts needed to maintain this table.

This patch series against Neil's for-next tree as of yesterday removes
the hash table from the raid0 code.

Patch #1 replaces the hash table lookup by a simple function that
loops over all strip zones to find the zone that holds a given sector.
This change allows to get rid of the hash table itself (patch #2)
and of related fields of struct raid0_private_data (patch #3).

Patch #4 makes raid0 return a proper error code rather than -ENOMEM
in case the array could not be started for reasons different from
memory shortage.

Patch #5 cleans up the allocation of the buffers for the raid0
configuration.

Patch #6 fixes a memory leak that happens when a raid0 array is
shut down.

The patched kernel has been tested with a smallish raid0 array
consisting of five devices of different sizes (created with an
unpatched kernel) and seems to work just fine. Moreover, it passes
the raid0 tests of the mdadm test suite.

Differences to the first version of the patch set:

	- According to the discussion on linux-raid, ->zone_start has
	been renamed to ->zone_end with the obvious semantic change.

	- Patch #5 and #6 of the old patch set have been combined
	and the allocation/freeing of the raid0 configuration has
	been moved from raid0_run() to create_strip_zones().

	- Patch #6 is new.

 drivers/md/raid0.c |  174 +++++++++++++---------------------------------------
 drivers/md/raid0.h |    6 +--
 2 files changed, 45 insertions(+), 135 deletions(-)

[PATCH 1/6] md: raid0: Replace hash table lookup by looping over all strip_zones.

[Andre Noll]

The number of strip_zones of a raid0 array is bounded by the number of
drives in the array and is in fact much smaller for typical setups. For
example, any raid0 array containing identical disks will have only
a single strip_zone.

Therefore, the hash tables which are used for quickly finding the
strip_zone that holds a particular sector are of questionable value
and add quite a bit of unnecessary complexity.

This patch replaces the hash table lookup by equivalent code which
simply loops over all strip zones to find the zone that holds the
given sector.

In order to make this loop as fast as possible, the zone->start field
of struct strip_zone has been renamed to zone_end, and it now stores
the beginning of the next zone in sectors. This allows to save one
addition in the loop.

Subsequent cleanup patches will remove the hash table structure.

Signed-off-by: Andre Noll <maan@systemlinux.org>
---
 drivers/md/raid0.c |   40 ++++++++++++++++++++--------------------
 drivers/md/raid0.h |    2 +-
 2 files changed, 21 insertions(+), 21 deletions(-)

diff --git a/drivers/md/raid0.c b/drivers/md/raid0.c
index c08d755..f3a35c8 100644
--- a/drivers/md/raid0.c
+++ b/drivers/md/raid0.c
@@ -52,7 +52,6 @@ static int raid0_congested(void *data, int bits)
 	return ret;
 }
 
-
 static int create_strip_zones (mddev_t *mddev)
 {
 	int i, c, j;
@@ -158,7 +157,7 @@ static int create_strip_zones (mddev_t *mddev)
 	}
 	zone->nb_dev = cnt;
 	zone->sectors = smallest->sectors * cnt;
-	zone->zone_start = 0;
+	zone->zone_end = zone->sectors;
 
 	current_start = smallest->sectors;
 	curr_zone_start = zone->sectors;
@@ -198,14 +197,13 @@ static int create_strip_zones (mddev_t *mddev)
 		printk(KERN_INFO "raid0: zone->nb_dev: %d, sectors: %llu\n",
 			zone->nb_dev, (unsigned long long)zone->sectors);
 
-		zone->zone_start = curr_zone_start;
+		zone->zone_end = curr_zone_start + zone->sectors;
 		curr_zone_start += zone->sectors;
 
 		current_start = smallest->sectors;
 		printk(KERN_INFO "raid0: current zone start: %llu\n",
 			(unsigned long long)current_start);
 	}
-
 	/* Now find appropriate hash spacing.
 	 * We want a number which causes most hash entries to cover
 	 * at most two strips, but the hash table must be at most
@@ -398,6 +396,19 @@ static int raid0_stop (mddev_t *mddev)
 	return 0;
 }
 
+/* Find the zone which holds a particular offset */
+static struct strip_zone *find_zone(struct raid0_private_data *conf,
+		sector_t sector)
+{
+	int i;
+	struct strip_zone *z = conf->strip_zone;
+
+	for (i = 0; i < conf->nr_strip_zones; i++)
+		if (sector < z[i].zone_end)
+			return z + i;
+	BUG();
+}
+
 static int raid0_make_request (struct request_queue *q, struct bio *bio)
 {
 	mddev_t *mddev = q->queuedata;
@@ -443,22 +454,11 @@ static int raid0_make_request (struct request_queue *q, struct bio *bio)
 		bio_pair_release(bp);
 		return 0;
 	}
- 
-
-	{
-		sector_t x = sector >> conf->sector_shift;
-		sector_div(x, (u32)conf->spacing);
-		zone = conf->hash_table[x];
-	}
-
-	while (sector >= zone->zone_start + zone->sectors)
-		zone++;
-
+	zone = find_zone(conf, sector);
 	sect_in_chunk = bio->bi_sector & (chunk_sects - 1);
-
-
 	{
-		sector_t x = (sector - zone->zone_start) >> chunksect_bits;
+		sector_t x = (zone->sectors + sector - zone->zone_end)
+				>> chunksect_bits;
 
 		sector_div(x, zone->nb_dev);
 		chunk = x;
@@ -503,8 +503,8 @@ static void raid0_status (struct seq_file *seq, mddev_t *mddev)
 			seq_printf(seq, "%s/", bdevname(
 				conf->strip_zone[j].dev[k]->bdev,b));
 
-		seq_printf(seq, "] zs=%d ds=%d s=%d\n",
-				conf->strip_zone[j].zone_start,
+		seq_printf(seq, "] ze=%d ds=%d s=%d\n",
+				conf->strip_zone[j].zone_end,
 				conf->strip_zone[j].dev_start,
 				conf->strip_zone[j].sectors);
 	}
diff --git a/drivers/md/raid0.h b/drivers/md/raid0.h
index 824b12e..556666f 100644
--- a/drivers/md/raid0.h
+++ b/drivers/md/raid0.h
@@ -3,7 +3,7 @@
 
 struct strip_zone
 {
-	sector_t zone_start;	/* Zone offset in md_dev (in sectors) */
+	sector_t zone_end;	/* Start of the next zone (in sectors) */
 	sector_t dev_start;	/* Zone offset in real dev (in sectors) */
 	sector_t sectors;	/* Zone size in sectors */
 	int nb_dev;		/* # of devices attached to the zone */
-- 
1.5.4.3