ceph/src/pmdk/src/tools/pmreorder/reorderengines.py

   1 # SPDX-License-Identifier: BSD-3-Clause
   2 # Copyright 2018, Intel Corporation
   3
   4
   5 from itertools import combinations
   6 from itertools import permutations
   7 from itertools import islice
   8 from itertools import chain
   9 from random import sample
  10 from functools import partial
  11 from reorderexceptions import NotSupportedOperationException
  12 import collections
  13
  14
  15 class FullReorderEngine:
  16     def __init__(self):
  17         self.test_on_barrier = True
  18     """
  19     Realizes a full reordering of stores within a given list.
  20     Example:
  21         input: (a, b, c)
  22         output:
  23                ()
  24                ('a',)
  25                ('b',)
  26                ('c',)
  27                ('a', 'b')
  28                ('a', 'c')
  29                ('b', 'a')
  30                ('b', 'c')
  31                ('c', 'a')
  32                ('c', 'b')
  33                ('a', 'b', 'c')
  34                ('a', 'c', 'b')
  35                ('b', 'a', 'c')
  36                ('b', 'c', 'a')
  37                ('c', 'a', 'b')
  38                ('c', 'b', 'a')
  39     """
  40     def generate_sequence(self, store_list):
  41         """
  42         Generates all possible combinations of all possible lengths,
  43         based on the operations in the list.
  44
  45         :param store_list: The list of stores to be reordered.
  46         :type store_list: list of :class:`memoryoperations.Store`
  47         :return: Yields all combinations of stores.
  48         :rtype: iterable
  49         """
  50         for length in range(0, len(store_list) + 1):
  51             for permutation in permutations(store_list, length):
  52                 yield permutation
  53
  54
  55 class AccumulativeReorderEngine:
  56     def __init__(self):
  57         self.test_on_barrier = True
  58     """
  59     Realizes an accumulative reorder of stores within a given list.
  60     Example:
  61         input: (a, b, c)
  62         output:
  63                ()
  64                ('a')
  65                ('a', 'b')
  66                ('a', 'b', 'c')
  67     """
  68     def generate_sequence(self, store_list):
  69         """
  70         Generates all accumulative lists,
  71         based on the operations in the store list.
  72
  73         :param store_list: The list of stores to be reordered.
  74         :type store_list: list of :class:`memoryoperations.Store`
  75         :return: Yields all accumulative combinations of stores.
  76         :rtype: iterable
  77         """
  78
  79         for i in range(0, len(store_list) + 1):
  80             out_list = [store_list[i] for i in range(0, i)]
  81             yield out_list
  82
  83
  84 class AccumulativeReverseReorderEngine:
  85     def __init__(self):
  86         self.test_on_barrier = True
  87     """
  88     Realizes an accumulative reorder of stores
  89     within a given list in reverse order.
  90     Example:
  91         input: (a, b, c)
  92         output:
  93                ()
  94                ('c')
  95                ('c', 'b')
  96                ('c', 'b', 'a')
  97     """
  98     def generate_sequence(self, store_list):
  99         """
 100         Reverse all elements order and
 101         generates all accumulative lists.
 102
 103         :param store_list: The list of stores to be reordered.
 104         :type store_list: list of :class:`memoryoperations.Store`
 105         :return: Yields all accumulative combinations of stores.
 106         :rtype: iterable
 107         """
 108         store_list = list(reversed(store_list))
 109         for i in range(len(store_list) + 1):
 110             yield [store_list[j] for j in range(i)]
 111
 112
 113 class SlicePartialReorderEngine:
 114     """
 115     Generates a slice of the full reordering of stores within a given list.
 116     Example:
 117         input: (a, b, c), start = 2, stop = None, step = 2
 118         output:
 119                ('b')
 120                ('a', 'b')
 121                ('b', 'c')
 122     """
 123     def __init__(self, start, stop, step=1):
 124         """
 125         Initializes the generator with the provided parameters.
 126
 127         :param start: Number of preceding elements to be skipped.
 128         :param stop: The element at which the slice is to stop.
 129         :param step: How many values are skipped between successive calls.
 130         """
 131         self._start = start
 132         self._stop = stop
 133         self._step = step
 134         self.test_on_barrier = True
 135
 136     def generate_sequence(self, store_list):
 137         """
 138         This generator yields a slice of all possible combinations.
 139
 140         The result may be a set of combinations of different lengths,
 141         depending on the slice parameters provided at object creation.
 142
 143         :param store_list: The list of stores to be reordered.
 144         :type store_list: list of :class:`memoryoperations.Store`
 145         :return: Yields a slice of all combinations of stores.
 146         :rtype: iterable
 147         """
 148         for sl in islice(chain(*map(lambda x: combinations(store_list, x),
 149                          range(0, len(store_list) + 1))),
 150                          self._start, self._stop, self._step):
 151             yield sl
 152
 153
 154 class FilterPartialReorderEngine:
 155     """
 156     Generates a filtered set of the combinations
 157     without duplication of stores within a given list.
 158     Example:
 159         input: (a, b, c), filter = filter_min_elem, kwarg1 = 2
 160         output:
 161                (a, b)
 162                (a, c)
 163                (b, c)
 164                (a, b, c)
 165
 166         input: (a, b, c), filter = filter_max_elem, kwarg1 = 2
 167         output:
 168                ()
 169                (a)
 170                (b)
 171                (c)
 172                (a, b)
 173                (a, c)
 174                (b, c)
 175
 176         input: (a, b, c), filter = filter_between_elem, kwarg1 = 2, kwarg2 = 2
 177         output:
 178                (a, b)
 179                (a, c)
 180                (b, c)
 181     """
 182     def __init__(self, func, **kwargs):
 183         """
 184         Initializes the generator with the provided parameters.
 185
 186         :param func: The filter function.
 187         :param **kwargs: Arguments to the filter function.
 188         """
 189         self._filter = func
 190         self._filter_kwargs = kwargs
 191         self.test_on_barrier = True
 192
 193     @staticmethod
 194     def filter_min_elem(store_list, **kwargs):
 195         """
 196         Filter stores list if number of element is less than kwarg1
 197         """
 198         if (len(store_list) < kwargs["kwarg1"]):
 199             return False
 200         return True
 201
 202     @staticmethod
 203     def filter_max_elem(store_list, **kwargs):
 204         """
 205         Filter stores list if number of element is greater than kwarg1.
 206         """
 207         if (len(store_list) > kwargs["kwarg1"]):
 208             return False
 209         return True
 210
 211     @staticmethod
 212     def filter_between_elem(store_list, **kwargs):
 213         """
 214         Filter stores list if number of element is
 215         greater or equal kwarg1 and less or equal kwarg2.
 216         """
 217         store_len = len(store_list)
 218         if (store_len >= kwargs["kwarg1"] and store_len <= kwargs["kwarg2"]):
 219             return True
 220         return False
 221
 222     def generate_sequence(self, store_list):
 223         """
 224         This generator yields a filtered set of combinations.
 225
 226         :param store_list: The list of stores to be reordered.
 227         :type store_list: list of :class:`memoryoperations.Store`
 228         :return: Yields a filtered set of combinations.
 229         :rtype: iterable
 230         """
 231         filter_fun = getattr(self, self._filter, None)
 232         for elem in filter(
 233                        partial(filter_fun, **self._filter_kwargs), chain(
 234                            *map(lambda x: combinations(store_list, x), range(
 235                                0, len(store_list) + 1)))):
 236             yield elem
 237
 238
 239 class RandomPartialReorderEngine:
 240     """
 241     Generates a random sequence of combinations of stores.
 242     Example:
 243         input: (a, b, c), max_seq = 3
 244         output:
 245                ('b', 'c')
 246                ('b',)
 247                ('a', 'b', 'c')
 248     """
 249     def __init__(self, max_seq=3):
 250         """
 251         Initializes the generator with the provided parameters.
 252
 253         :param max_seq: The number of combinations to be generated.
 254         """
 255         self.test_on_barrier = True
 256         self._max_seq = max_seq
 257
 258     def generate_sequence(self, store_list):
 259         """
 260         This generator yields a random sequence of combinations.
 261         Number of combinations without replacement has to be limited to
 262         1000 because of exponential growth of elements.
 263         Example:
 264             for 10 element from 80 -> 1646492110120 combinations
 265             for 20 element from 80 -> 3.5353161422122E+18 combinations
 266             for 40 element from 80 -> 1.0750720873334E+23 combinations
 267         :param store_list: The list of stores to be reordered.
 268         :type store_list: list of :class:`memoryoperations.Store`
 269         :return: Yields a random sequence of combinations.
 270         :rtype: iterable
 271         """
 272         population = list(chain(*map(
 273                           lambda x: islice(combinations(store_list, x), 1000),
 274                           range(0, len(store_list) + 1))))
 275         population_size = len(population)
 276         for elem in sample(population, self._max_seq if self._max_seq <=
 277                            population_size else population_size):
 278             yield elem
 279
 280
 281 class NoReorderEngine:
 282     def __init__(self):
 283         self.test_on_barrier = True
 284     """
 285     A NULL reorder engine.
 286     Example:
 287         input: (a, b, c)
 288         output: (a, b, c)
 289     """
 290     def generate_sequence(self, store_list):
 291         """
 292         This generator does not modify the provided store list.
 293
 294         :param store_list: The list of stores to be reordered.
 295         :type store_list: The list of :class:`memoryoperations.Store`
 296         :return: The unmodified list of stores.
 297         :rtype: iterable
 298         """
 299         return [store_list]
 300
 301
 302 class NoCheckerEngine:
 303     def __init__(self):
 304         self.test_on_barrier = False
 305     """
 306     A NULL reorder engine.
 307     Example:
 308         input: (a, b, c)
 309         output: (a, b, c)
 310     """
 311     def generate_sequence(self, store_list):
 312         """
 313         This generator does not modify the provided store list
 314         and does not do the check.
 315
 316         :param store_list: The list of stores to be reordered.
 317         :type store_list: The list of :class:`memoryoperations.Store`
 318         :return: The unmodified list of stores.
 319         :rtype: iterable
 320         """
 321         return [store_list]
 322
 323
 324 def get_engine(engine):
 325     if engine in engines:
 326         reorder_engine = engines[engine]()
 327     else:
 328         raise NotSupportedOperationException(
 329                   "Not supported reorder engine: {}"
 330                   .format(engine))
 331
 332     return reorder_engine
 333
 334
 335 engines = collections.OrderedDict([
 336            ('NoReorderNoCheck', NoCheckerEngine),
 337            ('ReorderFull', FullReorderEngine),
 338            ('NoReorderDoCheck', NoReorderEngine),
 339            ('ReorderAccumulative', AccumulativeReorderEngine),
 340            ('ReorderReverseAccumulative', AccumulativeReverseReorderEngine),
 341            ('ReorderPartial', RandomPartialReorderEngine)])