[PATCH LVM2] (0/12) LVM2 allocation rewrites

[PATCH LVM2] (0/12) LVM2 allocation rewrites

[Jun'ichi Nomura]

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.

-- 
Jun'ichi Nomura, NEC Corporation of America

[PATCH LVM2] (1/12) add flattened index to _for_each_pv()

[Jun'ichi Nomura]

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,
-- 
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>

[PATCH LVM2] (2/12) rewrite with struct allocation request

[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,
-- 
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>

[PATCH LVM2] (3/12) remove ix_offset from _find_parallel_space()

[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(-)


-- 
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>

[PATCH LVM2] (4/12) separate constraints checker from _find_parallel_space()

[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,
-- 
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>

[PATCH LVM2] (5/12) allow preference to small area

[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>

[PATCH LVM2] (6/12) move _add_pvs() to the earlier part of the file

[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(-)


-- 
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>

[PATCH LVM2] (7/12) update parallel_areas for on-going allocation

[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,
-- 
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>

[PATCH LVM2] (8/12) 'anywhere' policy implementation

[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,
-- 
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>

[PATCH LVM2] (9/12) lvconvert to use build_parallel_areas_from_lv()

[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,
-- 
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>

[PATCH LVM2] (10/12) calculate free pe counts before allocation attempt

[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,
-- 
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>

[PATCH LVM2] (11/12) extending parallel_area to cover log device

[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,
-- 
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>

[PATCH LVM2] (12/12) sort the allocation requests

[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,
-- 
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>