[PATCH 0/4] VG Validation updates

[PATCH 0/4] VG Validation updates

[Zdenek Kabelac]

This patchset should address some algorithmic problems
which will become noticable with thousans of LVs.

Using hash tables.
Simplify postorder for all LVs in VG.
Skip some duplicate tests.

The last patch just add pool name to fast pools.
It's IMHO very cheap and adds useful debug info for 
non-debug builds.


Zdenek Kabelac (4):
  Use hash tables for validating names
  Refactor code for _lv_postoder
  Do not check already checked part
  Add pool name to pool-fast as well

 lib/metadata/merge.c    |    3 +
 lib/metadata/metadata.c |  177 +++++++++++++++++++++++++++-------------------
 libdm/mm/pool-fast.c    |    2 +
 libdm/mm/pool.c         |    2 +-
 4 files changed, 110 insertions(+), 74 deletions(-)

-- 
1.7.4.1

[PATCH 1/4] Use hash tables for validating names

[Zdenek Kabelac]

Pick some low handing fruit and accelerate validation loop by
using lvname, lvid, pvid hash tables.
Comparing every name with >1000LVs becomes noticable.

Also merge pvl loop into one cycle now - no need to scan the list twice.

Somewhat unclear is error path behaviour when i.e. dm_hash_insert fails.
I've decided to break the loop in this moment with r=0.

Another noticable change here is - the error message with loop_counter1.
This counter is no longer provided - however the message must have been
misleading anyway.

Signed-off-by: Zdenek Kabelac <zkabelac@redhat.com>
---
 lib/metadata/metadata.c |  138 +++++++++++++++++++++++++++--------------------
 1 files changed, 80 insertions(+), 58 deletions(-)

diff --git a/lib/metadata/metadata.c b/lib/metadata/metadata.c
index ff61cbb..5525e3d 100644
--- a/lib/metadata/metadata.c
+++ b/lib/metadata/metadata.c
@@ -2221,15 +2221,17 @@ static int _lv_validate_references_single(struct logical_volume *lv, void *data)
 
 int vg_validate(struct volume_group *vg)
 {
-	struct pv_list *pvl, *pvl2;
-	struct lv_list *lvl, *lvl2;
+	struct pv_list *pvl;
+	struct lv_list *lvl;
 	struct lv_segment *seg;
 	char uuid[64] __attribute__((aligned(8)));
 	int r = 1;
 	uint32_t hidden_lv_count = 0, lv_count = 0, lv_visible_count = 0;
 	uint32_t pv_count = 0;
 	uint32_t num_snapshots = 0;
-	uint32_t loop_counter1, loop_counter2;
+	struct dm_hash_table *lvname_hash;
+	struct dm_hash_table *lvid_hash;
+	struct dm_hash_table *pvid_hash;
 
 	if (vg->alloc == ALLOC_CLING_BY_TAGS) {
 		log_error(INTERNAL_ERROR "VG %s allocation policy set to invalid cling_by_tags.",
@@ -2238,50 +2240,53 @@ int vg_validate(struct volume_group *vg)
 	}
 
 	/* FIXME Also check there's no data/metadata overlap */
+	if (!(pvid_hash = dm_hash_create(vg->pv_count))) {
+		log_error("Failed to allocate pvid hash.");
+		return 0;
+	}
+
 	dm_list_iterate_items(pvl, &vg->pvs) {
 		if (++pv_count > vg->pv_count) {
 			log_error(INTERNAL_ERROR "PV list corruption detected in VG %s.", vg->name);
 			/* FIXME Dump list structure? */
 			r = 0;
 		}
+
 		if (pvl->pv->vg != vg) {
 			log_error(INTERNAL_ERROR "VG %s PV list entry points "
-				  "to different VG %s", vg->name,
+				  "to different VG %s.", vg->name,
 				  pvl->pv->vg ? pvl->pv->vg->name : "NULL");
 			r = 0;
 		}
-	}
-
-	loop_counter1 = loop_counter2 = 0;
-	/* FIXME Use temp hash table instead? */
-	dm_list_iterate_items(pvl, &vg->pvs) {
-		if (++loop_counter1 > pv_count)
-			break;
-		dm_list_iterate_items(pvl2, &vg->pvs) {
-			if (++loop_counter2 > pv_count)
-				break;
-			if (pvl == pvl2)
-				break;
-			if (id_equal(&pvl->pv->id,
-				     &pvl2->pv->id)) {
-				if (!id_write_format(&pvl->pv->id, uuid,
-						     sizeof(uuid)))
-					 stack;
-				log_error(INTERNAL_ERROR "Duplicate PV id "
-					  "%s detected for %s in %s.",
-					  uuid, pv_dev_name(pvl->pv),
-					  vg->name);
-				r = 0;
-			}
-		}
 
 		if (strcmp(pvl->pv->vg_name, vg->name)) {
 			log_error(INTERNAL_ERROR "VG name for PV %s is corrupted.",
 				  pv_dev_name(pvl->pv));
 			r = 0;
 		}
+
+		if (dm_hash_lookup_binary(pvid_hash, &pvl->pv->id,
+					  sizeof(pvl->pv->id))) {
+			if (!id_write_format(&pvl->pv->id, uuid,
+					     sizeof(uuid)))
+				stack;
+			log_error(INTERNAL_ERROR "Duplicate PV id "
+				  "%s detected for %s in %s.",
+				  uuid, pv_dev_name(pvl->pv),
+				  vg->name);
+			r = 0;
+		}
+
+		if (!dm_hash_insert_binary(pvid_hash, &pvl->pv->id,
+					   sizeof(pvl->pv->id), pvl->pv)) {
+			stack;
+			r = 0;
+			break;
+		}
 	}
 
+	dm_hash_destroy(pvid_hash);
+
 	if (!check_pv_segments(vg)) {
 		log_error(INTERNAL_ERROR "PV segments corrupted in %s.",
 			  vg->name);
@@ -2349,33 +2354,34 @@ int vg_validate(struct volume_group *vg)
 	if (!r)
 		return r;
 
-	loop_counter1 = loop_counter2 = 0;
-	/* FIXME Use temp hash table instead? */
+	if (!(lvname_hash = dm_hash_create(lv_count))) {
+		log_error("Failed to allocate lv_name hash");
+		return 0;
+	}
+
+	if (!(lvid_hash = dm_hash_create(lv_count))) {
+		log_error("Failed to allocate uuid hash");
+		dm_hash_destroy(lvname_hash);
+		return 0;
+	}
+
 	dm_list_iterate_items(lvl, &vg->lvs) {
-		if (++loop_counter1 > lv_count)
-			break;
-		dm_list_iterate_items(lvl2, &vg->lvs) {
-			if (++loop_counter2 > lv_count)
-				break;
-			if (lvl == lvl2)
-				break;
-			if (!strcmp(lvl->lv->name, lvl2->lv->name)) {
-				log_error(INTERNAL_ERROR "Duplicate LV name "
-					  "%s detected in %s.", lvl->lv->name,
-					  vg->name);
-				r = 0;
-			}
-			if (id_equal(&lvl->lv->lvid.id[1],
-				     &lvl2->lv->lvid.id[1])) {
-				if (!id_write_format(&lvl->lv->lvid.id[1], uuid,
-						     sizeof(uuid)))
-					 stack;
-				log_error(INTERNAL_ERROR "Duplicate LV id "
-					  "%s detected for %s and %s in %s.",
-					  uuid, lvl->lv->name, lvl2->lv->name,
-					  vg->name);
-				r = 0;
-			}
+		if (dm_hash_lookup(lvname_hash, lvl->lv->name)) {
+			log_error(INTERNAL_ERROR
+				  "Duplicate LV name %s detected in %s.",
+				  lvl->lv->name, vg->name);
+			r = 0;
+		}
+
+		if (dm_hash_lookup_binary(lvid_hash, lvl->lv->lvid.id,
+					  sizeof(lvl->lv->lvid.id))) {
+			if (!id_write_format(&lvl->lv->lvid.id[1], uuid,
+					     sizeof(uuid)))
+				stack;
+			log_error(INTERNAL_ERROR "Duplicate LV id "
+				  "%s detected for %s in %s.",
+				  uuid, lvl->lv->name, vg->name);
+			r = 0;
 		}
 
 		if (!check_lv_segments(lvl->lv, 1)) {
@@ -2383,8 +2389,24 @@ int vg_validate(struct volume_group *vg)
 				  lvl->lv->name);
 			r = 0;
 		}
+
+		if (!dm_hash_insert(lvname_hash, lvl->lv->name, lvl)) {
+			stack;
+			r = 0;
+			break;
+		}
+
+		if (!dm_hash_insert_binary(lvid_hash, lvl->lv->lvid.id,
+					   sizeof(lvl->lv->lvid.id), lvl->lv)) {
+			stack;
+			r = 0;
+			break;
+		}
 	}
 
+	dm_hash_destroy(lvname_hash);
+	dm_hash_destroy(lvid_hash);
+
 	dm_list_iterate_items(lvl, &vg->lvs) {
 		if (!_lv_postorder(lvl->lv, _lv_validate_references_single, NULL))
 			r = 0;
@@ -2397,14 +2419,14 @@ int vg_validate(struct volume_group *vg)
 			if (seg_is_mirrored(seg)) {
 				if (seg->area_count != 2) {
 					log_error(INTERNAL_ERROR
-						  "Segment %d in %s is not 2-way.",
-						  loop_counter1, lvl->lv->name);
+						  "Segment in %s is not 2-way.",
+						  lvl->lv->name);
 					r = 0;
 				}
 			} else if (seg->area_count != 1) {
 				log_error(INTERNAL_ERROR
-					  "Segment %d in %s has wrong number of areas: %d.",
-					  loop_counter1, lvl->lv->name, seg->area_count);
+					  "Segment in %s has wrong number of areas: %d.",
+					  lvl->lv->name, seg->area_count);
 				r = 0;
 			}
 		}
-- 
1.7.4.1

[PATCH 2/4] Refactor code for _lv_postoder

[Zdenek Kabelac]

Add _lv_postorder_vg() - for calling postorder for every LV from VG.
We use this in 2 places -  vg_mark_partial_lvs and vg_validate
so make it as one function.

Benefit here is - to use only one cleanup code and avoid
potentially duplicate scan of same LVs.

Signed-off-by: Zdenek Kabelac <zkabelac@redhat.com>
---
 lib/metadata/metadata.c |   39 ++++++++++++++++++++++++---------------
 1 files changed, 24 insertions(+), 15 deletions(-)

diff --git a/lib/metadata/metadata.c b/lib/metadata/metadata.c
index 5525e3d..c006b60 100644
--- a/lib/metadata/metadata.c
+++ b/lib/metadata/metadata.c
@@ -2068,6 +2068,25 @@ static int _lv_postorder(struct logical_volume *lv,
 	return r;
 }
 
+static int _lv_postorder_vg(struct volume_group *vg,
+			    int (*fn)(struct logical_volume *lv, void *data),
+			    void *data)
+{
+	struct lv_list *lvl;
+	int r = 1;
+
+	dm_list_iterate_items(lvl, &vg->lvs)
+		if (!_lv_postorder_visit(lvl->lv, fn, data)) {
+			stack;
+			r = 0;
+		}
+
+	dm_list_iterate_items(lvl, &vg->lvs)
+		_lv_postorder_cleanup(lvl->lv, 0);
+
+	return r;
+}
+
 struct _lv_mark_if_partial_baton {
 	int partial;
 };
@@ -2105,11 +2124,6 @@ static int _lv_mark_if_partial_single(struct logical_volume *lv, void *data)
 	return 1;
 }
 
-static int _lv_mark_if_partial(struct logical_volume *lv)
-{
-	return _lv_postorder(lv, _lv_mark_if_partial_single, NULL);
-}
-
 /*
  * Mark LVs with missing PVs using PARTIAL_LV status flag. The flag is
  * propagated transitively, so LVs referencing other LVs are marked
@@ -2117,14 +2131,9 @@ static int _lv_mark_if_partial(struct logical_volume *lv)
  */
 int vg_mark_partial_lvs(struct volume_group *vg)
 {
-	struct logical_volume *lv;
-	struct lv_list *lvl;
+	if (!_lv_postorder_vg(vg, _lv_mark_if_partial_single, NULL))
+		return_0;
 
-	dm_list_iterate_items(lvl, &vg->lvs) {
-		lv = lvl->lv;
-		if (!_lv_mark_if_partial(lv))
-			return_0;
-	}
 	return 1;
 }
 
@@ -2407,9 +2416,9 @@ int vg_validate(struct volume_group *vg)
 	dm_hash_destroy(lvname_hash);
 	dm_hash_destroy(lvid_hash);
 
-	dm_list_iterate_items(lvl, &vg->lvs) {
-		if (!_lv_postorder(lvl->lv, _lv_validate_references_single, NULL))
-			r = 0;
+	if (!_lv_postorder_vg(vg, _lv_validate_references_single, NULL)) {
+		stack;
+		r = 0;
 	}
 
 	dm_list_iterate_items(lvl, &vg->lvs) {
-- 
1.7.4.1

[PATCH 3/4] Do not check already checked part

[Zdenek Kabelac]

check_lv_segments is eithe called once - with 'complete_vg == 0'
or twice in row first with == 0, then with 1.

My assumtion is we do not need to make the same tests for same data
pointers twice - if we already know it's been been OK from the
first pass - that way it's used in vg_validate() and vg_read_internal().

Better idea would be probably to make rather 2 separte functions
there - but for now just skip some large piece of the code.

Signed-off-by: Zdenek Kabelac <zkabelac@redhat.com>
---
 lib/metadata/merge.c |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)

diff --git a/lib/metadata/merge.c b/lib/metadata/merge.c
index 3b8895c..402ee57 100644
--- a/lib/metadata/merge.c
+++ b/lib/metadata/merge.c
@@ -209,6 +209,9 @@ int check_lv_segments(struct logical_volume *lv, int complete_vg)
 		le += seg->len;
 	}
 
+	if (complete_vg)
+		goto out;
+
 	dm_list_iterate_items(sl, &lv->segs_using_this_lv) {
 		seg = sl->seg;
 		seg_found = 0;
-- 
1.7.4.1

[PATCH 4/4] Add pool name to pool-fast as well

[Zdenek Kabelac]

It's fairly cheap to keep this name - and it could
be useful without 'non pool debug code' compilation.

Signed-off-by: Zdenek Kabelac <zkabelac@redhat.com>
---
 libdm/mm/pool-fast.c |    2 ++
 libdm/mm/pool.c      |    2 +-
 2 files changed, 3 insertions(+), 1 deletions(-)

diff --git a/libdm/mm/pool-fast.c b/libdm/mm/pool-fast.c
index ebd982e..377ad99 100644
--- a/libdm/mm/pool-fast.c
+++ b/libdm/mm/pool-fast.c
@@ -28,6 +28,7 @@ struct dm_pool {
 	struct dm_list list;
 	struct chunk *chunk, *spare_chunk;	/* spare_chunk is a one entry free
 						   list to stop 'bobbling' */
+	const char *name;
 	size_t chunk_size;
 	size_t object_len;
 	unsigned object_alignment;
@@ -51,6 +52,7 @@ struct dm_pool *dm_pool_create(const char *name, size_t chunk_hint)
 		return 0;
 	}
 
+	p->name = name;
 	/* round chunk_hint up to the next power of 2 */
 	p->chunk_size = chunk_hint + sizeof(struct chunk);
 	while (new_size < p->chunk_size)
diff --git a/libdm/mm/pool.c b/libdm/mm/pool.c
index 35bfffa..825f7ca 100644
--- a/libdm/mm/pool.c
+++ b/libdm/mm/pool.c
@@ -71,7 +71,7 @@ void dm_pools_check_leaks(void)
 			  p->orig_pool,
 			  p->name, p->stats.bytes);
 #else
-		log_error(" [%p]", p);
+		log_error(" [%p] %s", p, p->name);
 #endif
 	}
 }
-- 
1.7.4.1