Skip to contentSkip to conversation

md: Remove the hash tables from raid0 V2 -- Introduction.

PATCH In review Andre Noll 2 participants 8 messages May 15, 2009 – May 16, 2009 MD RAID

lore
Share & tools
lore

Andre Noll

author
#0 lore raw

cover md: Remove the hash tables from raid0 V2 -- Introduction.

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(-)
author
#1 lore raw

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

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.

---
 drivers/md/raid0.c |   40 ++++++++++++++++++++--------------------
 drivers/md/raid0.h |    2 +-
 2 files changed, 21 insertions(+), 21 deletions(-)
drivers/md/raid0.c +20 -20
index c08d755..f3a35c8 100644
@@ -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);
 	}
drivers/md/raid0.h +1 -1
index 824b12e..556666f 100644
@@ -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 */
Signature · 1 line
1.5.4.3
author
#2 lore raw

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

In reply to 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.

---
 drivers/md/raid0.c |   12 ------------
 drivers/md/raid0.h |    1 -
 2 files changed, 0 insertions(+), 13 deletions(-)
drivers/md/raid0.c +0 -12
index f3a35c8..d550396 100644
@@ -328,22 +328,14 @@ static int raid0_run (mddev_t *mddev)
 		nb_zone = s + round;
 	}
 	printk(KERN_INFO "raid0 : nb_zone is %d.\n", nb_zone);
-
-	printk(KERN_INFO "raid0 : Allocating %zu bytes for hash.\n",
-				nb_zone*sizeof(struct strip_zone*));
-	conf->hash_table = kmalloc (sizeof (struct strip_zone *)*nb_zone, GFP_KERNEL);
-	if (!conf->hash_table)
-		goto out_free_conf;
 	sectors = conf->strip_zone[cur].sectors;
 
-	conf->hash_table[0] = conf->strip_zone + cur;
 	for (i=1; i< nb_zone; i++) {
 		while (sectors <= conf->spacing) {
 			cur++;
 			sectors += conf->strip_zone[cur].sectors;
 		}
 		sectors -= conf->spacing;
-		conf->hash_table[i] = conf->strip_zone + cur;
 	}
 	if (conf->sector_shift) {
 		conf->spacing >>= conf->sector_shift;
@@ -386,8 +378,6 @@ static int raid0_stop (mddev_t *mddev)
 	raid0_conf_t *conf = mddev_to_conf(mddev);
 
 	blk_sync_queue(mddev->queue); /* the unplug fn references 'conf'*/
-	kfree(conf->hash_table);
-	conf->hash_table = NULL;
 	kfree(conf->strip_zone);
 	conf->strip_zone = NULL;
 	kfree(conf);
@@ -496,8 +486,6 @@ static void raid0_status (struct seq_file *seq, mddev_t *mddev)
 	h = 0;
 	for (j = 0; j < conf->nr_strip_zones; j++) {
 		seq_printf(seq, "      z%d", j);
-		if (conf->hash_table[h] == conf->strip_zone+j)
-			seq_printf(seq, "(h%d)", h++);
 		seq_printf(seq, "=[");
 		for (k = 0; k < conf->strip_zone[j].nb_dev; k++)
 			seq_printf(seq, "%s/", bdevname(
drivers/md/raid0.h +0 -1
index 556666f..a14630a 100644
@@ -12,7 +12,6 @@ struct strip_zone
 
 struct raid0_private_data
 {
-	struct strip_zone **hash_table; /* Table of indexes into strip_zone */
 	struct strip_zone *strip_zone;
 	mdk_rdev_t **devlist; /* lists of rdevs, pointed to by strip_zone->dev */
 	int nr_strip_zones;
Signature · 1 line
1.5.4.3
author
#3 lore raw

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

In reply to 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.

---
 drivers/md/raid0.c |   63 +---------------------------------------------------
 drivers/md/raid0.h |    3 --
 2 files changed, 1 insertions(+), 65 deletions(-)
drivers/md/raid0.c +1 -62
index d550396..4b207ab 100644
@@ -56,7 +56,6 @@ static int create_strip_zones (mddev_t *mddev)
 {
 	int i, c, j;
 	sector_t current_start, curr_zone_start;
-	sector_t min_spacing;
 	raid0_conf_t *conf = mddev_to_conf(mddev);
 	mdk_rdev_t *smallest, *rdev1, *rdev2, *rdev;
 	struct strip_zone *zone;
@@ -204,28 +203,7 @@ static int create_strip_zones (mddev_t *mddev)
 		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
-	 * 1 PAGE.  We choose the smallest strip, or contiguous collection
-	 * of strips, that has big enough size.  We never consider the last
-	 * strip though as it's size has no bearing on the efficacy of the hash
-	 * table.
-	 */
-	conf->spacing = curr_zone_start;
-	min_spacing = curr_zone_start;
-	sector_div(min_spacing, PAGE_SIZE/sizeof(struct strip_zone*));
-	for (i=0; i < conf->nr_strip_zones-1; i++) {
-		sector_t s = 0;
-		for (j = i; j < conf->nr_strip_zones - 1 &&
-				s < min_spacing; j++)
-			s += conf->strip_zone[j].sectors;
-		if (s >= min_spacing && s < conf->spacing)
-			conf->spacing = s;
-	}
-
 	mddev->queue->unplug_fn = raid0_unplug;
-
 	mddev->queue->backing_dev_info.congested_fn = raid0_congested;
 	mddev->queue->backing_dev_info.congested_data = mddev;
 
@@ -275,10 +253,8 @@ static sector_t raid0_size(mddev_t *mddev, sector_t sectors, int raid_disks)
 	return array_sectors;
 }
 
-static int raid0_run (mddev_t *mddev)
+static int raid0_run(mddev_t *mddev)
 {
-	unsigned  cur=0, i=0, nb_zone;
-	s64 sectors;
 	raid0_conf_t *conf;
 
 	if (mddev->chunk_size == 0) {
@@ -308,43 +284,6 @@ static int raid0_run (mddev_t *mddev)
 
 	printk(KERN_INFO "raid0 : md_size is %llu sectors.\n",
 		(unsigned long long)mddev->array_sectors);
-	printk(KERN_INFO "raid0 : conf->spacing is %llu sectors.\n",
-		(unsigned long long)conf->spacing);
-	{
-		sector_t s = raid0_size(mddev, 0, 0);
-		sector_t space = conf->spacing;
-		int round;
-		conf->sector_shift = 0;
-		if (sizeof(sector_t) > sizeof(u32)) {
-			/*shift down space and s so that sector_div will work */
-			while (space > (sector_t) (~(u32)0)) {
-				s >>= 1;
-				space >>= 1;
-				s += 1; /* force round-up */
-				conf->sector_shift++;
-			}
-		}
-		round = sector_div(s, (u32)space) ? 1 : 0;
-		nb_zone = s + round;
-	}
-	printk(KERN_INFO "raid0 : nb_zone is %d.\n", nb_zone);
-	sectors = conf->strip_zone[cur].sectors;
-
-	for (i=1; i< nb_zone; i++) {
-		while (sectors <= conf->spacing) {
-			cur++;
-			sectors += conf->strip_zone[cur].sectors;
-		}
-		sectors -= conf->spacing;
-	}
-	if (conf->sector_shift) {
-		conf->spacing >>= conf->sector_shift;
-		/* round spacing up so when we divide by it, we
-		 * err on the side of too-low, which is safest
-		 */
-		conf->spacing++;
-	}
-
 	/* calculate the max read-ahead size.
 	 * For read-ahead of large files to be effective, we need to
 	 * readahead at least twice a whole stripe. i.e. number of devices
drivers/md/raid0.h +0 -3
index a14630a..dbcf1da 100644
@@ -15,9 +15,6 @@ struct raid0_private_data
 	struct strip_zone *strip_zone;
 	mdk_rdev_t **devlist; /* lists of rdevs, pointed to by strip_zone->dev */
 	int nr_strip_zones;
-
-	sector_t spacing;
-	int sector_shift; /* shift this before divide by spacing */
 };
 
 typedef struct raid0_private_data raid0_conf_t;
Signature · 1 line
1.5.4.3
author
#4 lore raw

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

In reply to 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.

---
 drivers/md/raid0.c |   17 +++++++++--------
 1 files changed, 9 insertions(+), 8 deletions(-)
drivers/md/raid0.c +9 -8
index 4b207ab..7f89843 100644
@@ -105,12 +105,12 @@ static int create_strip_zones (mddev_t *mddev)
 	conf->strip_zone = kzalloc(sizeof(struct strip_zone)*
 				conf->nr_strip_zones, GFP_KERNEL);
 	if (!conf->strip_zone)
-		return 1;
+		return -ENOMEM;
 	conf->devlist = kzalloc(sizeof(mdk_rdev_t*)*
 				conf->nr_strip_zones*mddev->raid_disks,
 				GFP_KERNEL);
 	if (!conf->devlist)
-		return 1;
+		return -ENOMEM;
 
 	/* The first zone must contain all devices, so here we check that
 	 * there is a proper alignment of slots to devices and find them all
@@ -209,8 +209,8 @@ static int create_strip_zones (mddev_t *mddev)
 
 	printk(KERN_INFO "raid0: done.\n");
 	return 0;
- abort:
-	return 1;
+abort:
+	return -EINVAL;
 }
 
 /**
@@ -256,6 +256,7 @@ static sector_t raid0_size(mddev_t *mddev, sector_t sectors, int raid_disks)
 static int raid0_run(mddev_t *mddev)
 {
 	raid0_conf_t *conf;
+	int ret;
 
 	if (mddev->chunk_size == 0) {
 		printk(KERN_ERR "md/raid0: non-zero chunk size required.\n");
@@ -271,12 +272,13 @@ static int raid0_run(mddev_t *mddev)
 
 	conf = kmalloc(sizeof (raid0_conf_t), GFP_KERNEL);
 	if (!conf)
-		goto out;
+		return -ENOMEM;
 	mddev->private = (void *)conf;
  
 	conf->strip_zone = NULL;
 	conf->devlist = NULL;
-	if (create_strip_zones (mddev)) 
+	ret = create_strip_zones(mddev);
+	if (ret < 0)
 		goto out_free_conf;
 
 	/* calculate array device size */
@@ -308,8 +310,7 @@ out_free_conf:
 	kfree(conf->devlist);
 	kfree(conf);
 	mddev->private = NULL;
-out:
-	return -ENOMEM;
+	return ret;
 }
 
 static int raid0_stop (mddev_t *mddev)
Signature · 1 line
1.5.4.3
author
#5 lore raw

PATCH 5/6 md: raid0: Allocate all buffers for the raid0 configuration in one function.

In reply to Andre Noll

Currently the raid0 configuration is allocated in raid0_run() while the buffers for the strip_zone and the dev_list arrays are allocated in create_strip_zones(). On errors, all three buffers are freed in raid0_run().

It's easier and more readable to do the allocation and cleanup within a single function. So move that code into create_strip_zones().

---
 drivers/md/raid0.c |   47 +++++++++++++++++------------------------------
 1 files changed, 17 insertions(+), 30 deletions(-)
drivers/md/raid0.c +17 -30
index 7f89843..74689ad 100644
@@ -52,21 +52,18 @@ static int raid0_congested(void *data, int bits)
 	return ret;
 }
 
-static int create_strip_zones (mddev_t *mddev)
+static int create_strip_zones(mddev_t *mddev)
 {
-	int i, c, j;
+	int i, c, j, err;
 	sector_t current_start, curr_zone_start;
-	raid0_conf_t *conf = mddev_to_conf(mddev);
 	mdk_rdev_t *smallest, *rdev1, *rdev2, *rdev;
 	struct strip_zone *zone;
 	int cnt;
 	char b[BDEVNAME_SIZE];
- 
-	/*
-	 * The number of 'same size groups'
-	 */
-	conf->nr_strip_zones = 0;
- 
+	raid0_conf_t *conf = kzalloc(sizeof(*conf), GFP_KERNEL);
+
+	if (!conf)
+		return -ENOMEM;
 	list_for_each_entry(rdev1, &mddev->disks, same_set) {
 		printk(KERN_INFO "raid0: looking at %s\n",
 			bdevname(rdev1->bdev,b));
@@ -101,16 +98,16 @@ static int create_strip_zones (mddev_t *mddev)
 		}
 	}
 	printk(KERN_INFO "raid0: FINAL %d zones\n", conf->nr_strip_zones);
-
+	err = -ENOMEM;
 	conf->strip_zone = kzalloc(sizeof(struct strip_zone)*
 				conf->nr_strip_zones, GFP_KERNEL);
 	if (!conf->strip_zone)
-		return -ENOMEM;
+		goto abort;
 	conf->devlist = kzalloc(sizeof(mdk_rdev_t*)*
 				conf->nr_strip_zones*mddev->raid_disks,
 				GFP_KERNEL);
 	if (!conf->devlist)
-		return -ENOMEM;
+		goto abort;
 
 	/* The first zone must contain all devices, so here we check that
 	 * there is a proper alignment of slots to devices and find them all
@@ -119,6 +116,7 @@ static int create_strip_zones (mddev_t *mddev)
 	cnt = 0;
 	smallest = NULL;
 	zone->dev = conf->devlist;
+	err = -EINVAL;
 	list_for_each_entry(rdev1, &mddev->disks, same_set) {
 		int j = rdev1->raid_disk;
 
@@ -208,9 +206,14 @@ static int create_strip_zones (mddev_t *mddev)
 	mddev->queue->backing_dev_info.congested_data = mddev;
 
 	printk(KERN_INFO "raid0: done.\n");
+	mddev->private = conf;
 	return 0;
 abort:
-	return -EINVAL;
+	kfree(conf->strip_zone);
+	kfree(conf->devlist);
+	kfree(conf);
+	mddev->private = NULL;
+	return err;
 }
 
 /**
@@ -255,7 +258,6 @@ static sector_t raid0_size(mddev_t *mddev, sector_t sectors, int raid_disks)
 
 static int raid0_run(mddev_t *mddev)
 {
-	raid0_conf_t *conf;
 	int ret;
 
 	if (mddev->chunk_size == 0) {
@@ -270,16 +272,9 @@ static int raid0_run(mddev_t *mddev)
 	blk_queue_segment_boundary(mddev->queue, (mddev->chunk_size>>1) - 1);
 	mddev->queue->queue_lock = &mddev->queue->__queue_lock;
 
-	conf = kmalloc(sizeof (raid0_conf_t), GFP_KERNEL);
-	if (!conf)
-		return -ENOMEM;
-	mddev->private = (void *)conf;
- 
-	conf->strip_zone = NULL;
-	conf->devlist = NULL;
 	ret = create_strip_zones(mddev);
 	if (ret < 0)
-		goto out_free_conf;
+		return ret;
 
 	/* calculate array device size */
 	md_set_array_sectors(mddev, raid0_size(mddev, 0, 0));
@@ -301,16 +296,8 @@ static int raid0_run(mddev_t *mddev)
 			mddev->queue->backing_dev_info.ra_pages = 2* stripe;
 	}
 
-
 	blk_queue_merge_bvec(mddev->queue, raid0_mergeable_bvec);
 	return 0;
-
-out_free_conf:
-	kfree(conf->strip_zone);
-	kfree(conf->devlist);
-	kfree(conf);
-	mddev->private = NULL;
-	return ret;
 }
 
 static int raid0_stop (mddev_t *mddev)
Signature · 1 line
1.5.4.3
author
#6 lore raw

PATCH 6/6 md: raid0: Fix a memory leak when stopping a raid0 array.

In reply to Andre Noll

raid0_stop() removes all references to the raid0 configuration but misses to free the ->devlist buffer.

This patch closes this leak, removes a pointless initialization and fixes a coding style issue in raid0_stop().

---
 drivers/md/raid0.c |    5 ++---
 1 files changed, 2 insertions(+), 3 deletions(-)
drivers/md/raid0.c +2 -3
index 74689ad..0305061 100644
@@ -300,16 +300,15 @@ static int raid0_run(mddev_t *mddev)
 	return 0;
 }
 
-static int raid0_stop (mddev_t *mddev)
+static int raid0_stop(mddev_t *mddev)
 {
 	raid0_conf_t *conf = mddev_to_conf(mddev);
 
 	blk_sync_queue(mddev->queue); /* the unplug fn references 'conf'*/
 	kfree(conf->strip_zone);
-	conf->strip_zone = NULL;
+	kfree(conf->devlist);
 	kfree(conf);
 	mddev->private = NULL;
-
 	return 0;
 }
 
Signature · 1 line
1.5.4.3
#7 lore raw
In reply to Andre Noll
Quoted 6 lines · On Friday May 15, [email protected] wrote:

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.

Thanks.
All applied, and pushed out to
git://neil.brown.name/md for-next

I've added a couple more patches to remove a couple of fields from struct strip_zone. I'll post them shortly for comment.

And thanks for finding the memory leak!

NeilBrown