Skip to contentSkip to conversation

(0/12) LVM2 allocation rewrites

PATCH New Jun'ichi Nomura 1 participant 13 messages Oct 13, 2006

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 (0/12) LVM2 allocation rewrites

Hi,

This series of patches fix the following things:
- allocate mirror log on the same PV with mimage (--alloc anywhere)
- allocate from any available space (--alloc anywhere)
- correct allocation for converting linear LV to mirror LV to avoid existing LV
- correct allocation for extending mirror LV to avoid existing log LV
- generalize allocation logic to cover more complex allocation requests

Patches are applicable to 2.02.11.
Patches should be applied in this order.
Compilation test is done for all patches.
Simple tests of combination of lvcreate/lvextend/lvconvert and linear/stripe/mirror/snapshot are done for the set of the patches.

What's changed
==============

01.for_each_pv.patch
- _for_each_pv() is extended to maintain global index of flattened lv_segment
- _for_each_pv() accepts the range of indices to which call back function is executed

02.alloc_requests.patch
- added struct allocation_requests and eliminate log device specific elements from struct alloc_handle
- corresponding changes in several functions

03.remove_ix_offset.patch
- shrink the size of temporal array of areas

04.separate_constraints.patch
- move constraints checker out from _find_parallel_space()

05.prefer_small.patch
- allowing preference of small area (e.g. for log device)

06.add_pvs.patch
- move _add_pvs()

07.update_parallel.patch
- updating parallel_areas according to the on-going allocation (_update_parallel_areas and other utility functions)

08.anywhere.patch
- added relax_allocation_requests() to split the allocation request to cover anywhere policy

09.lvconvert.patch
- changed lvconvert to use build_parallel_areas_from_lv()

10.calcfree.patch
- calculate free pe count before trying allocation

11.log_coverage.patch
- reflect the fact that log pv constraints other areas regardless of its range

12.sort_requests.patch
- sort allocation requests to pick up log area first

Background of these changes
===========================

Allow mirror log on the same device as mirror image
---------------------------------------------------

Current code takes the allocation request like this:
<n> areas with size <x> which are either striped or mirrored, plus 1 area with size 1 for mirror log device

Then it tries to allocate <n> + 1 areas from different PVs.

The log device is handled as special case various places. If you would like to allow log on the same device with others but the others are on different PVs each other, you have to add another special case handling of the log device. Like the one posted here last month:
https://www.redhat.com/archives/linux-lvm/2006-September/msg00108.html

In 02.alloc_requests.patch, the allocation request is generalized by struct allocation_request. The allocator will process <x> * <n> request and then 1 * 1 request.

To allocate log device first, 12.sort_requests.patch sorts the allocation requests.

Real 'anywhere' policy implementation
-------------------------------------

Since the current logic picks up the best areas from each PV and matches them with allocation request, it doesn't work well if the number of PVs is smaller than the requested areas.

This is acceptable restriction for normal case: it's not good to allocate mirrors or stripes from same PV.
But for special case like 'anywhere' policy, this restriction should be removed.

As the area list in the PV is sorted by size, it's easy to pick up largest one for each PV.
However, it's takes cost to pick up <n> largest areas from <m> PVs where <m> is smaller than <n>.

Rather than that, in 08.anywhere.patch, it splits the allocation request into the smaller unit where <n> is smaller than <m>.

Allocation constraints
----------------------

The allocation code takes "parallel_areas" list as a constraint. It avoids (a part of) PVs in the list.

However, the list was built only before starting the allocation. So it cannot avoid parallel areas just being allocated. For example, if you do 'lvcreate -m1', newly allocated mirror images should avoid mirror log, or vise versa, but it can't. 07.update_parallel.patch updates the list after every allocation to cope with this situation.

The other problem is that if you do 'lvextend' the mirror LV, newly allocated extents should avoid mirror log.
But it can't because it can't distinguish mirror log in parallel_areas list.
11.log_coverage.patch adds mirror log to the list to cover whole range so that future mirror image allocation can avoid it.

Signature · 1 line
Jun'ichi Nomura, NEC Corporation of America
#1 lore raw

PATCH 1/1 (1/12) add flattened index to _for_each_pv()

This patch adds "flattened index" to _for_each_pv().

o Using this index, you can map the stacked LV segment into the array of PVs.
This is useful for allocation code to find index of areas[] corresponding to the prev_lvseg.

o _for_each_pv() doesn't execute call back function if it's NULL. It's useful if you just need to count the number of PVs. (_count_parallel_areas).

o The patch adds "start_index" and "end_index" to restrict the function call back while maintaining the flattened index.

o Also the patch adds "walk_log_lv" flag instead of reusing !only_single_area_segments as workaround, because it is no longer correct.

$ diffstat -p1 01.for_each_pv.patch
 lib/metadata/lv_manip.c |   76 ++++++++++++++++++++++++++++++++++++---------
 1 file changed, 57 insertions(+), 19 deletions(-)

Thanks,

Signature · 10 lines
Jun'ichi Nomura, NEC Corporation of America


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 01.for_each_pv.patch
Type: text/x-patch
Size: 6128 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/01cbc088/attachment.bin>
#2 lore raw

PATCH 1/1 (2/12) rewrite with struct allocation request

In reply to Jun'ichi Nomura

This patch introduces 'struct allocaction_request' to generalize the allocation request currently embedded in struct alloc_handle.

o The struct is in this form:
struct allocation_request {
uint32_t len; /* requested length of single area */ uint32_t area_count; /* number of areas with same length */
uint32_t multiple; /* LV size is extended with (len * multiple) */
uint32_t allocated; /* allocated length of single area */ int flags;
int index; /* index to alloced_areas[] */
};

For example, if you do 'lvcreate -l3 -m1', the first allocation request would be:

     { len = 3, area_count = 2, multiple = 1, index = 0 }
  and for the 2nd allocation (i.e. log) would be:
     { len = 1, area_count = 1, multiple = 1, index = 2 }

_handle_allocation_requests() will call _find_parallel_space() for each struct allocation_request.

The flags is used to describe preference and also be used later to find out for what purpose the request was.

o _find_parallel_space() is simplified since we don't need to carry around the attempt-wide "*allocated" or "max_parallel" and a lot of division and multiplication.

o lv_add_log_segment() is changed to search alloced_areas for log. It should be easily extended to cope with multiple log allocation.

o Set up of struct allocation_request is done in _alloc_init(). It seems better to do it out side of allocate_extents() and allocate_extents() to take the array of struct allocation_request.

$ diffstat -p1 02.alloc_requests.patch
 lib/metadata/lv_manip.c |  459 ++++++++++++++++++++++++++++++++-------------
 1 file changed, 310 insertions(+), 149 deletions(-)

Thanks,

Signature · 10 lines
Jun'ichi Nomura, NEC Corporation of America


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 02.alloc_requests.patch
Type: text/x-patch
Size: 24365 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/6d5a1bc7/attachment.bin>
#3 lore raw

PATCH 1/1 (3/12) remove ix_offset from _find_parallel_space()

In reply to Jun'ichi Nomura

This patch removes ix_offset and related variables.

o Current code splits areas[] array in 2 parts.
The first part is for contiguous areas and the 2nd part is for sorted-by-length areas.
However, these 2 use are exclusive.
If you are trying contiguous allocation, the 2nd part isn't used. Vice versa.

$ diffstat -p1 03.remove_ix_offset.patch
 lib/metadata/lv_manip.c |   66 ++++++++++++++++++++-------------------------
 1 file changed, 28 insertions(+), 38 deletions(-)
Signature · 9 lines
Jun'ichi Nomura, NEC Corporation of America

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 03.remove_ix_offset.patch
Type: text/x-patch
Size: 4248 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/c74a859b/attachment.bin>
#4 lore raw

PATCH 1/1 (4/12) separate constraints checker from _find_parallel_space()

In reply to Jun'ichi Nomura

This patch moves the parts checking constraints out from _find_parallel_space().

o is_pv_parallel() checks all parallel_areas if the allocation request is ALLOC_AVOID_ALL_PARALLEL. (e.g. for log device)

o Others are just moving location.

$ diffstat -p1 04.separate_constraints.patch
 lib/metadata/lv_manip.c |  147 ++++++++++++++++++++++++++++++++++++--------
 1 file changed, 112 insertions(+), 35 deletions(-)

Thanks,

Signature · 10 lines
Jun'ichi Nomura, NEC Corporation of America


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 04.separate_constraints.patch
Type: text/x-patch
Size: 5039 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/6e879ae9/attachment.bin>
#5 lore raw

PATCH 1/1 (5/12) allow preference to small area

In reply to Jun'ichi Nomura

This patch allows allocation request to prefer small area.

o _comp_area_inv() is used to reverse the areas[] sorting if the allocation request is ALLOC_PREFER_SMALL.

o In _find_parallel_space(), iteration for pv_area didn't work work as commented:
/*
* Put the smallest area of each PV that is at least the
* size we need into areas array. If there isn't one
* that fits completely and we're allowed more than one
* LV segment, then take the largest remaining instead. */
because of the "goto next_pv" at the end.

$ diffstat -p1 05.prefer_small.patch
 lib/metadata/lv_manip.c |   15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)

Thanks,
--
Jun'ichi Nomura, NEC Corporation of America
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 05.prefer_small.patch
Type: text/x-patch
Size: 1204 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/46931535/attachment.bin>

#6 lore raw

PATCH 1/1 (6/12) move _add_pvs() to the earlier part of the file

In reply to Jun'ichi Nomura

This move the location of _add_pvs() for later patches. No funtional change.

$ diffstat -p1 06.add_pvs.patch
 lib/metadata/lv_manip.c |   50 +++++++++++++++++++++++++----------------------- 1 file changed, 27 insertions(+), 23 deletions(-)
Signature · 10 lines
Jun'ichi Nomura, NEC Corporation of America


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 06.add_pvs.patch
Type: text/x-patch
Size: 1773 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/deaaa367/attachment.bin>
#7 lore raw

PATCH 1/1 (7/12) update parallel_areas for on-going allocation

In reply to Jun'ichi Nomura

This patch adds _update_parallel_areas() to update parallel_areas list based on the current allocation.

o For some cases (e.g. lvcreate), ah->parallel_areas weren't initialized. So now, _alloc_init() initialize it if there is none. build_parallel_areas() is allowed to return empty list.

o _update_parallel_areas() and other sub functions are added.
It takes the range and PV then reflects them into existing parallel_areas.

$ diffstat -p1 07.update_parallel.patch
 lib/metadata/lv_manip.c |  150 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 150 insertions(+)

Thanks,

Signature · 10 lines
Jun'ichi Nomura, NEC Corporation of America


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 07.update_parallel.patch
Type: text/x-patch
Size: 4901 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/9561e3ed/attachment.bin>
#8 lore raw

PATCH 1/1 (8/12) 'anywhere' policy implementation

In reply to Jun'ichi Nomura

This patch implements 'anywhere' policy.

o relax_allocation_requests() is added to split the allocation requests into smallest possible pieces so that they can fit into any number of PVs.

o _setup_alloced_segment() needed to be changed because it assumed the list items in ah->alloced_areas[0] can be used as array. It's no longer true.

o dm_pool_free() in relax_allocation_requests() seems to free whole alloc_handle and not usable. I might be using it in wrong way.

$ diffstat -p1 08.anywhere.patch
 lib/metadata/lv_manip.c |  108 +++++++++++++++++++++++++++++++++++++++------
 1 file changed, 89 insertions(+), 19 deletions(-)

Thanks,

Signature · 11 lines
Jun'ichi Nomura, NEC Corporation of America



-------------- next part --------------
A non-text attachment was scrubbed...
Name: 08.anywhere.patch
Type: text/x-patch
Size: 5178 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/91bcc3a3/attachment.bin>
#9 lore raw

PATCH 1/1 (9/12) lvconvert to use build_parallel_areas_from_lv()

In reply to Jun'ichi Nomura

This patch uncomments the use of build_parallel_areas_from_lv() by lvconvert. Based on other patches, it works now.

$ diffstat -p1 09.lvconvert.patch
 tools/lvconvert.c |   13 ++++---------
 1 file changed, 4 insertions(+), 9 deletions(-)

Thanks,

Signature · 8 lines
Jun'ichi Nomura, NEC Corporation of America
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 09.lvconvert.patch
Type: text/x-patch
Size: 991 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/132a36de/attachment.bin>
#10 lore raw

PATCH 1/1 (10/12) calculate free pe counts before allocation attempt

In reply to Jun'ichi Nomura

This patch adds calculation of free pe counts and checks it before doing any allocation attempt.

$ diffstat -p1 10.calcfree.patch
 lib/metadata/lv_manip.c |   30 ++++++++++++++++++++++++++----
 1 file changed, 26 insertions(+), 4 deletions(-)

Thanks,

Signature · 10 lines
Jun'ichi Nomura, NEC Corporation of America


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 10.calcfree.patch
Type: text/x-patch
Size: 1890 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/be275032/attachment.bin>
#11 lore raw

PATCH 1/1 (11/12) extending parallel_area to cover log device

In reply to Jun'ichi Nomura

This patch extends parallel_area to include log device appropriately.

o The log device is considered as covering the whole range of the segment including newly allocated extents.
However, current parallel_areas list is not composed as so.

For example, if you have a mirrored LV with length 10, parallel_areas would say: there are parallel PVs for the extents from 0 to 9.
If you are going to extend the mirrored LV, nothing constraints extents allocated for le 10 or higher.

In this case, the existing log device should be taken as parallel to all extents including le 10 or higher.

o _for_each_pv() is changed to accept flags which controls what type of segments _for_each_pv() walks through.

$ diffstat -p1 11.log_coverage.patch
 lib/metadata/lv_manip.c |   71 +++++++++++++++++++++++++++++++++++++----------- 1 file changed, 56 insertions(+), 15 deletions(-)

Thanks,

Signature · 10 lines
Jun'ichi Nomura, NEC Corporation of America


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 11.log_coverage.patch
Type: text/x-patch
Size: 5820 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/d4739cbb/attachment.bin>
#12 lore raw

PATCH 1/1 (12/12) sort the allocation requests

In reply to Jun'ichi Nomura

This patch adds sorting of allocation requests.

o This patch sorts the allocation request based on its type. Allocation for log device is done before allocation of others.

$ diffstat -p1 12.sort_requests.patch
 lib/metadata/lv_manip.c |   21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

Thanks,

Signature · 10 lines
Jun'ichi Nomura, NEC Corporation of America


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 12.sort_requests.patch
Type: text/x-patch
Size: 1235 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/lvm-devel/attachments/20061013/ad75d725/attachment.bin>