From 7f2def9e6dbaad36f40fc916d940834809106ce9 Mon Sep 17 00:00:00 2001 From: Alasdair Kergon Date: Wed, 11 May 2005 15:02:49 +0000 Subject: [PATCH] Remove lists of free PV segments. Simplify pv_maps code and remove slow bitset algorithm. --- WHATS_NEW | 4 +- lib/format1/import-export.c | 1 - lib/format_pool/import_export.c | 1 - lib/format_text/import_vsn1.c | 1 - lib/metadata/lv_manip.c | 7 +- lib/metadata/metadata.c | 11 +- lib/metadata/metadata.h | 3 - lib/metadata/pv_alloc.h | 3 +- lib/metadata/pv_manip.c | 43 +---- lib/metadata/pv_map.c | 277 ++++++++++---------------------- lib/metadata/pv_map.h | 14 +- tools/toollib.c | 1 - 12 files changed, 107 insertions(+), 259 deletions(-) diff --git a/WHATS_NEW b/WHATS_NEW index df688e613..495c3ef6f 100644 --- a/WHATS_NEW +++ b/WHATS_NEW @@ -1,6 +1,8 @@ Version 2.01.11 - ============================== - Redhatify the clvmd rhel4 initscript + Remove lists of free PV segments. + Simplify pv_maps code and remove slow bitset algorithm. + Red-Hat-ify the clvmd rhel4 initscript. %Zu->%zu Fix loopfiles alias alloc & mem debugging. Un-inline dbg_strdup. diff --git a/lib/format1/import-export.c b/lib/format1/import-export.c index ca487a1c5..2e38104af 100644 --- a/lib/format1/import-export.c +++ b/lib/format1/import-export.c @@ -91,7 +91,6 @@ int import_pv(struct pool *mem, struct device *dev, list_init(&pv->tags); list_init(&pv->segments); - list_init(&pv->free_segments); if (!alloc_pv_segment_whole_pv(mem, pv)) { stack; diff --git a/lib/format_pool/import_export.c b/lib/format_pool/import_export.c index 79e8279b2..dd3152661 100644 --- a/lib/format_pool/import_export.c +++ b/lib/format_pool/import_export.c @@ -184,7 +184,6 @@ int import_pool_pv(const struct format_type *fmt, struct pool *mem, list_init(&pv->tags); list_init(&pv->segments); - list_init(&pv->free_segments); if (!alloc_pv_segment_whole_pv(mem, pv)) { stack; diff --git a/lib/format_text/import_vsn1.c b/lib/format_text/import_vsn1.c index 498f4d7a8..ec130594f 100644 --- a/lib/format_text/import_vsn1.c +++ b/lib/format_text/import_vsn1.c @@ -192,7 +192,6 @@ static int _read_pv(struct format_instance *fid, struct pool *mem, list_init(&pv->tags); list_init(&pv->segments); - list_init(&pv->free_segments); /* Optional tags */ if ((cn = find_config_node(pvn, "tags")) && diff --git a/lib/metadata/lv_manip.c b/lib/metadata/lv_manip.c index 01798c3d7..f4a5cb822 100644 --- a/lib/metadata/lv_manip.c +++ b/lib/metadata/lv_manip.c @@ -160,8 +160,7 @@ static int _alloc_parallel_area(struct logical_volume *lv, uint32_t area_count, for (s = 0; s < area_count; s++) { struct pv_area *pva = areas[s]; - if (!set_lv_segment_area_pv(seg, s, pva->map->pvl->pv, - pva->start)) { + if (!set_lv_segment_area_pv(seg, s, pva->map->pv, pva->start)) { stack; return 0; } @@ -288,7 +287,7 @@ static int _alloc_linear_area(struct logical_volume *lv, uint32_t *ix, return 0; } - if (!set_lv_segment_area_pv(seg, 0, map->pvl->pv, pva->start)) { + if (!set_lv_segment_area_pv(seg, 0, map->pv, pva->start)) { stack; return 0; } @@ -323,7 +322,7 @@ static int _alloc_mirrored_area(struct logical_volume *lv, uint32_t *ix, /* FIXME Remove AREA_PV restriction here? */ if (!set_lv_segment_area_pv(seg, 0, mirrored_pv, mirrored_pe) || - !set_lv_segment_area_pv(seg, 1, map->pvl->pv, pva->start)) { + !set_lv_segment_area_pv(seg, 1, map->pv, pva->start)) { stack; return 0; } diff --git a/lib/metadata/metadata.c b/lib/metadata/metadata.c index 14e62582d..2ee881531 100644 --- a/lib/metadata/metadata.c +++ b/lib/metadata/metadata.c @@ -127,7 +127,7 @@ static int _copy_pv(struct physical_volume *pv_to, } if (!peg_dup(pv_to->fmt->cmd->mem, &pv_to->segments, - &pv_to->free_segments, &pv_from->segments)) { + &pv_from->segments)) { stack; return 0; } @@ -380,8 +380,11 @@ int vg_change_pesize(struct cmd_context *cmd, struct volume_group *vg, return 0; } - /* foreach PV Segment */ - list_iterate_items(pvseg, &pv->free_segments) { + /* foreach free PV Segment */ + list_iterate_items(pvseg, &pv->segments) { + if (pvseg->lvseg) + continue; + if (!_recalc_extents(&pvseg->pe, dev_name(pv->dev), " PV segment start", old_size, new_size)) { @@ -542,7 +545,6 @@ struct physical_volume *pv_create(const struct format_type *fmt, list_init(&pv->tags); list_init(&pv->segments); - list_init(&pv->free_segments); if (!fmt->ops->pv_setup(fmt, pe_start, existing_extent_count, existing_extent_size, @@ -1202,7 +1204,6 @@ struct physical_volume *pv_read(struct cmd_context *cmd, const char *pv_name, list_init(&pv->tags); list_init(&pv->segments); - list_init(&pv->free_segments); /* FIXME Move more common code up here */ if (!(info->fmt->ops->pv_read(info->fmt, pv_name, pv, mdas))) { diff --git a/lib/metadata/metadata.h b/lib/metadata/metadata.h index 3004452cf..a6f90248d 100644 --- a/lib/metadata/metadata.h +++ b/lib/metadata/metadata.h @@ -109,8 +109,6 @@ struct pv_segment { struct lv_segment *lvseg; /* NULL if free space */ uint32_t lv_area; /* Index to area in LV segment */ - - struct list freelist; /* Member of pv->free_segments */ }; struct physical_volume { @@ -129,7 +127,6 @@ struct physical_volume { uint32_t pe_alloc_count; struct list segments; /* Ordered pv_segments covering complete PV */ - struct list free_segments; /* Free pv_segments for this PV */ struct list tags; }; diff --git a/lib/metadata/pv_alloc.h b/lib/metadata/pv_alloc.h index 655f2238e..ff2b76a4c 100644 --- a/lib/metadata/pv_alloc.h +++ b/lib/metadata/pv_alloc.h @@ -16,8 +16,7 @@ #include "pool.h" int alloc_pv_segment_whole_pv(struct pool *mem, struct physical_volume *pv); -int peg_dup(struct pool *mem, struct list *peg_new, struct list *peg_free_new, - struct list *peg_old); +int peg_dup(struct pool *mem, struct list *peg_new, struct list *peg_old); struct pv_segment *assign_peg_to_lvseg(struct physical_volume *pv, uint32_t pe, uint32_t area_len, struct lv_segment *seg, diff --git a/lib/metadata/pv_manip.c b/lib/metadata/pv_manip.c index 0758f743c..fb2c94ab5 100644 --- a/lib/metadata/pv_manip.c +++ b/lib/metadata/pv_manip.c @@ -39,7 +39,6 @@ static struct pv_segment *_alloc_pv_segment(struct pool *mem, peg->lv_area = lv_area; list_init(&peg->list); - list_init(&peg->freelist); return peg; } @@ -58,18 +57,15 @@ int alloc_pv_segment_whole_pv(struct pool *mem, struct physical_volume *pv) } list_add(&pv->segments, &peg->list); - list_add(&pv->free_segments, &peg->freelist); return 1; } -int peg_dup(struct pool *mem, struct list *peg_new, struct list *peg_free_new, - struct list *peg_old) +int peg_dup(struct pool *mem, struct list *peg_new, struct list *peg_old) { struct pv_segment *peg, *pego; list_init(peg_new); - list_init(peg_free_new); list_iterate_items(pego, peg_old) { if (!(peg = _alloc_pv_segment(mem, pego->pv, pego->pe, @@ -79,8 +75,6 @@ int peg_dup(struct pool *mem, struct list *peg_new, struct list *peg_free_new, return 0; } list_add(peg_new, &peg->list); - if (!peg->lvseg) - list_add(peg_free_new, &peg->freelist); } return 1; @@ -105,7 +99,6 @@ static int _pv_split_segment(struct physical_volume *pv, struct pv_segment *peg, peg->len = peg->len - peg_new->len; list_add_h(&peg->list, &peg_new->list); - list_add_h(&pv->free_segments, &peg_new->freelist); return 1; } @@ -160,9 +153,6 @@ struct pv_segment *assign_peg_to_lvseg(struct physical_volume *pv, peg->lvseg = seg; peg->lv_area = area_num; - list_del(&peg->freelist); - list_init(&peg->freelist); - return peg; } @@ -173,7 +163,6 @@ int release_pv_segment(struct pv_segment *peg, uint32_t new_area_len) peg->lv_area = 0; /* FIXME merge free space */ - list_add(&peg->pv->free_segments, &peg->freelist); return 1; } @@ -194,9 +183,6 @@ void merge_pv_segments(struct pv_segment *peg1, struct pv_segment *peg2) peg1->len += peg2->len; list_del(&peg2->list); - - if (!list_empty(&peg2->freelist)) - list_del(&peg2->freelist); } /* @@ -208,7 +194,6 @@ int check_pv_segments(struct volume_group *vg) struct pv_list *pvl; struct pv_segment *peg; unsigned s, segno; - int free_count, free_total, free_size; uint32_t start_pe; int ret = 1; @@ -216,12 +201,8 @@ int check_pv_segments(struct volume_group *vg) pv = pvl->pv; segno = 0; start_pe = 0; - free_total = 0; - - free_count = list_size(&pv->free_segments); list_iterate_items(peg, &pv->segments) { - free_size = list_size(&peg->freelist); s = peg->lv_area; /* FIXME Remove this next line eventually */ @@ -250,31 +231,9 @@ int check_pv_segments(struct volume_group *vg) peg->lvseg->area_len); ret = 0; } - if (free_size) { - log_debug("Segment is on free list!"); - ret = 0; - } - } else { - free_total++; - if (!free_size) { - log_debug("Seg missing from free list"); - ret = 0; - } - if (free_size != free_count) { - log_debug("Seg free size inconsistent: " - "%u != %u", free_size, - free_count); - ret = 0; - } } start_pe += peg->len; } - - if (free_count != free_total) { - log_debug("Free list inconsistent: %u != %u", - free_count, free_total); - ret = 0; - } } return ret; diff --git a/lib/metadata/pv_map.c b/lib/metadata/pv_map.c index 2bfbaa144..77a69fb42 100644 --- a/lib/metadata/pv_map.c +++ b/lib/metadata/pv_map.c @@ -16,213 +16,107 @@ #include "lib.h" #include "pv_map.h" #include "hash.h" - -static int _create_maps(struct pool *mem, struct list *pvs, struct list *maps) -{ - struct list *tmp; - struct pv_map *pvm; - struct pv_list *pvl; - - list_iterate(tmp, pvs) { - pvl = list_item(tmp, struct pv_list); - - if (!(pvl->pv->status & ALLOCATABLE_PV)) - continue; - - if (!(pvm = pool_zalloc(mem, sizeof(*pvm)))) { - stack; - return 0; - } - - pvm->pvl = pvl; - if (!(pvm->allocated_extents = - bitset_create(mem, pvl->pv->pe_count))) { - stack; - return 0; - } - - list_init(&pvm->areas); - list_add(maps, &pvm->list); - } - - return 1; -} - -static int _set_allocd(struct hash_table *hash, - struct physical_volume *pv, uint32_t pe) -{ - struct pv_map *pvm; - - if (!(pvm = (struct pv_map *) hash_lookup(hash, dev_name(pv->dev)))) { - /* - * it doesn't matter that this fails, it just - * means this part of the lv is on a pv that - * we're not interested in allocating to. - */ - return 1; - } - - /* sanity check */ - if (bit(pvm->allocated_extents, pe)) { - log_error("Physical extent %d of %s referenced by more than " - "one logical volume", pe, dev_name(pv->dev)); - return 0; - } - - bit_set(pvm->allocated_extents, pe); - return 1; -} - -static int _fill_bitsets(struct volume_group *vg, struct list *maps) -{ - struct list *lvh, *pvmh, *segh; - struct logical_volume *lv; - struct pv_map *pvm; - uint32_t s, pe; - struct hash_table *hash; - struct lv_segment *seg; - int r = 0; - - if (!(hash = hash_create(128))) { - log_err("Couldn't create hash table for pv maps."); - return 0; - } - - /* populate the hash table */ - list_iterate(pvmh, maps) { - pvm = list_item(pvmh, struct pv_map); - if (!hash_insert(hash, dev_name(pvm->pvl->pv->dev), pvm)) { - stack; - goto out; - } - } - - /* iterate through all the lv's setting bit's for used pe's */ - list_iterate(lvh, &vg->lvs) { - lv = list_item(lvh, struct lv_list)->lv; - - list_iterate(segh, &lv->segments) { - seg = list_item(segh, struct lv_segment); - - for (s = 0u; s < seg->area_count; s++) { - for (pe = 0u; pe < seg->area_len; pe++) { - if (seg->area[s].type != AREA_PV) - continue; - if (!_set_allocd(hash, - seg->area[s].u.pv.pvseg->pv, - seg->area[s].u.pv.pvseg->pe - + pe)) { - stack; - goto out; - } - } - } - } - } - r = 1; - - out: - hash_destroy(hash); - return r; -} +#include "pv_alloc.h" /* - * Areas are maintained in size order. + * Areas are maintained in size order, largest first. */ static void _insert_area(struct list *head, struct pv_area *a) { - struct list *pvah; - struct pv_area *pva = NULL; - - if (list_empty(head)) { - list_add(head, &a->list); - return; - } - - list_iterate(pvah, head) { - pva = list_item(pvah, struct pv_area); + struct pv_area *pva; - if (pva->count < a->count) + list_iterate_items(pva, head) { + if (a->count > pva->count) break; } - list_add_h(&pva->list, &a->list); + list_add(&pva->list, &a->list); } static int _create_single_area(struct pool *mem, struct pv_map *pvm, - uint32_t end, uint32_t *extent) + uint32_t start, uint32_t length) { - uint32_t e = *extent, b; struct pv_area *pva; - while (e <= end && bit(pvm->allocated_extents, e)) - e++; - - if (e > end) { - *extent = e; - return 1; - } - - b = e++; - - while (e <= end && !bit(pvm->allocated_extents, e)) - e++; - if (!(pva = pool_zalloc(mem, sizeof(*pva)))) { stack; return 0; } log_debug("Allowing allocation on %s start PE %" PRIu32 " length %" - PRIu32, dev_name(pvm->pvl->pv->dev), b, e - b); + PRIu32, dev_name(pvm->pv->dev), start, length); pva->map = pvm; - pva->start = b; - pva->count = e - b; + pva->start = start; + pva->count = length; _insert_area(&pvm->areas, pva); - *extent = e; return 1; } -static int _create_areas(struct pool *mem, struct pv_map *pvm, uint32_t start, - uint32_t count) +static int _create_alloc_areas_for_pv(struct pool *mem, struct pv_map *pvm, + uint32_t start, uint32_t count) { - uint32_t pe, end; + struct pv_segment *peg; + uint32_t pe, end, area_len; + /* Only select extents from start to end inclusive */ end = start + count - 1; - if (end > pvm->pvl->pv->pe_count - 1) - end = pvm->pvl->pv->pe_count - 1; + if (end > pvm->pv->pe_count - 1) + end = pvm->pv->pe_count - 1; pe = start; - while (pe <= end) - if (!_create_single_area(mem, pvm, end, &pe)) { + + /* Walk through complete ordered list of device segments */ + list_iterate_items(peg, &pvm->pv->segments) { + /* pe holds the next extent we want to check */ + + /* Beyond the range we're interested in? */ + if (pe > end) + break; + + /* Skip if we haven't reached the first seg we want yet */ + if (pe > peg->pe + peg->len - 1) + continue; + + /* Free? */ + if (peg->lvseg) + goto next; + + /* How much of this peg do we need? */ + area_len = (end >= peg->pe + peg->len - 1) ? + peg->len - (pe - peg->pe) : end - pe + 1; + + if (!_create_single_area(mem, pvm, pe, area_len)) { stack; return 0; } + next: + pe = peg->pe + peg->len; + } + return 1; } -static int _create_allocatable_areas(struct pool *mem, struct pv_map *pvm) +static int _create_all_areas_for_pv(struct pool *mem, struct pv_map *pvm, + struct list *pe_ranges) { - struct list *alloc_areas, *aah; struct pe_range *aa; - alloc_areas = pvm->pvl->pe_ranges; + if (!pe_ranges) { + /* Use whole PV */ + if (!_create_alloc_areas_for_pv(mem, pvm, UINT32_C(0), + pvm->pv->pe_count)) { + stack; + return 0; + } - if (alloc_areas) { - list_iterate(aah, alloc_areas) { - aa = list_item(aah, struct pe_range); - if (!_create_areas(mem, pvm, aa->start, aa->count)) { - stack; - return 0; - } + return 1; + } - } - } else { - /* Use whole PV */ - if (!_create_areas(mem, pvm, UINT32_C(0), - pvm->pvl->pv->pe_count)) { + list_iterate_items(aa, pe_ranges) { + if (!_create_alloc_areas_for_pv(mem, pvm, aa->start, + aa->count)) { stack; return 0; } @@ -231,16 +125,26 @@ static int _create_allocatable_areas(struct pool *mem, struct pv_map *pvm) return 1; } -static int _create_all_areas(struct pool *mem, struct list *maps, - struct list *pvs) +static int _create_maps(struct pool *mem, struct list *pvs, struct list *pvms) { - struct list *tmp; struct pv_map *pvm; + struct pv_list *pvl; + + list_iterate_items(pvl, pvs) { + if (!(pvl->pv->status & ALLOCATABLE_PV)) + continue; + + if (!(pvm = pool_zalloc(mem, sizeof(*pvm)))) { + stack; + return 0; + } - list_iterate(tmp, maps) { - pvm = list_item(tmp, struct pv_map); + pvm->pv = pvl->pv; - if (!_create_allocatable_areas(mem, pvm)) { + list_init(&pvm->areas); + list_add(pvms, &pvm->list); + + if (!_create_all_areas_for_pv(mem, pvm, pvl->pe_ranges)) { stack; return 0; } @@ -249,40 +153,29 @@ static int _create_all_areas(struct pool *mem, struct list *maps, return 1; } +/* + * Create list of PV areas available for this particular allocation + */ struct list *create_pv_maps(struct pool *mem, struct volume_group *vg, - struct list *pvs) + struct list *allocatable_pvs) { - struct list *maps = pool_zalloc(mem, sizeof(*maps)); + struct list *pvms; - if (!maps) { - stack; + if (!(pvms = pool_zalloc(mem, sizeof(*pvms)))) { + log_error("create_pv_maps alloc failed"); return NULL; } - list_init(maps); + list_init(pvms); - if (!_create_maps(mem, pvs, maps)) { + if (!_create_maps(mem, allocatable_pvs, pvms)) { log_error("Couldn't create physical volume maps in %s", vg->name); - goto bad; - } - - if (!_fill_bitsets(vg, maps)) { - log_error("Couldn't fill extent allocation bitmaps in %s", - vg->name); - goto bad; - } - - if (!_create_all_areas(mem, maps, pvs)) { - log_error("Couldn't create area maps in %s", vg->name); - goto bad; + pool_free(mem, pvms); + return NULL; } - return maps; - - bad: - pool_free(mem, maps); - return NULL; + return pvms; } void consume_pv_area(struct pv_area *pva, uint32_t to_go) diff --git a/lib/metadata/pv_map.h b/lib/metadata/pv_map.h index 0da796c7f..7aa2b2944 100644 --- a/lib/metadata/pv_map.h +++ b/lib/metadata/pv_map.h @@ -33,19 +33,21 @@ struct pv_area { uint32_t start; uint32_t count; - struct list list; + struct list list; /* pv_map.areas */ }; struct pv_map { - struct pv_list *pvl; - bitset_t allocated_extents; - struct list areas; + struct physical_volume *pv; + struct list areas; /* struct pv_areas */ struct list list; }; -struct list *create_pv_maps(struct pool *mem, - struct volume_group *vg, struct list *pvs); +/* + * Find intersection between available_pvs and free space in VG + */ +struct list *create_pv_maps(struct pool *mem, struct volume_group *vg, + struct list *allocatable_pvs); void consume_pv_area(struct pv_area *area, uint32_t to_go); diff --git a/tools/toollib.c b/tools/toollib.c index cb6ddc256..8882c72e8 100644 --- a/tools/toollib.c +++ b/tools/toollib.c @@ -498,7 +498,6 @@ static int _process_all_devs(struct cmd_context *cmd, void *handle, memset(&pv_dummy, 0, sizeof(pv_dummy)); list_init(&pv_dummy.tags); list_init(&pv_dummy.segments); - list_init(&pv_dummy.free_segments); pv_dummy.dev = dev; pv_dummy.fmt = NULL; pv = &pv_dummy; -- 2.43.5