libparted/cs/constraint.c

   1 /*
   2     libparted - a library for manipulating disk partitions
   3     Copyright (C) 2000-2001, 2007, 2009-2011 Free Software Foundation, Inc.
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 3 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 /**
  20  * \addtogroup PedConstraint
  21  *
  22  * \brief Constraint solver interface.
  23  *
  24  * Constraints are used to communicate restrictions on operations Constraints
  25  * are restrictions on the location and alignment of the start and end of a
  26  * partition, and the minimum and maximum size.
  27  *
  28  * Constraints are closed under intersection (for the proof see the source
  29  * code).  For background information see the Chinese Remainder Theorem.
  30  *
  31  * This interface consists of construction constraints, finding the intersection
  32  * of constraints, and finding solutions to constraints.
  33  *
  34  * The constraint solver allows you to specify constraints on where a partition
  35  * or file system (or any PedGeometry) may be placed/resized/etc. For example,
  36  * you might want to make sure that a file system is at least 10 Gb, or that it
  37  * starts at the beginning of new cylinder.
  38  *
  39  * The constraint solver in this file unifies solver in geom.c (which allows you
  40  * to specify constraints on ranges) and natmath.c (which allows you to specify
  41  * alignment constraints).
  42  *
  43  * @{
  44  */
  45
  46 #include <config.h>
  47 #include <parted/parted.h>
  48 #include <parted/debug.h>
  49 #include <assert.h>
  50
  51 /**
  52  * Initializes a pre-allocated piece of memory to contain a constraint
  53  * with the supplied default values.
  54  *
  55  * \return \c 0 on failure.
  56  */
  57 int
  58 ped_constraint_init (
  59         PedConstraint* constraint,
  60         const PedAlignment* start_align,
  61         const PedAlignment* end_align,
  62         const PedGeometry* start_range,
  63         const PedGeometry* end_range,
  64         PedSector min_size,
  65         PedSector max_size)
  66 {
  67         PED_ASSERT (constraint != NULL);
  68         PED_ASSERT (start_range != NULL);
  69         PED_ASSERT (end_range != NULL);
  70         PED_ASSERT (min_size > 0);
  71         PED_ASSERT (max_size > 0);
  72
  73         constraint->start_align = ped_alignment_duplicate (start_align);
  74         constraint->end_align = ped_alignment_duplicate (end_align);
  75         constraint->start_range = ped_geometry_duplicate (start_range);
  76         constraint->end_range = ped_geometry_duplicate (end_range);
  77         constraint->min_size = min_size;
  78         constraint->max_size = max_size;
  79
  80         return 1;
  81 }
  82
  83 /**
  84  * Convenience wrapper for ped_constraint_init().
  85  *
  86  * Allocates a new piece of memory and initializes the constraint.
  87  *
  88  * \return \c NULL on failure.
  89  */
  90 PedConstraint*
  91 ped_constraint_new (
  92         const PedAlignment* start_align,
  93         const PedAlignment* end_align,
  94         const PedGeometry* start_range,
  95         const PedGeometry* end_range,
  96         PedSector min_size,
  97         PedSector max_size)
  98 {
  99         PedConstraint*  constraint;
 100
 101         constraint = (PedConstraint*) ped_malloc (sizeof (PedConstraint));
 102         if (!constraint)
 103                 goto error;
 104         if (!ped_constraint_init (constraint, start_align, end_align,
 105                                   start_range, end_range, min_size, max_size))
 106                 goto error_free_constraint;
 107         return constraint;
 108
 109 error_free_constraint:
 110         free (constraint);
 111 error:
 112         return NULL;
 113 }
 114
 115 /**
 116  * Return a constraint that requires a region to be entirely contained inside
 117  * \p max, and to entirely contain \p min.
 118  *
 119  * \return \c NULL on failure.
 120  */
 121 PedConstraint*
 122 ped_constraint_new_from_min_max (
 123         const PedGeometry* min,
 124         const PedGeometry* max)
 125 {
 126         PedGeometry     start_range;
 127         PedGeometry     end_range;
 128
 129         PED_ASSERT (min != NULL);
 130         PED_ASSERT (max != NULL);
 131         PED_ASSERT (ped_geometry_test_inside (max, min));
 132
 133         ped_geometry_init (&start_range, min->dev, max->start,
 134                            min->start - max->start + 1);
 135         ped_geometry_init (&end_range, min->dev, min->end,
 136                            max->end - min->end + 1);
 137
 138         return ped_constraint_new (
 139                         ped_alignment_any, ped_alignment_any,
 140                         &start_range, &end_range,
 141                         min->length, max->length);
 142 }
 143
 144 /**
 145  * Return a constraint that requires a region to entirely contain \p min.
 146  *
 147  * \return \c NULL on failure.
 148  */
 149 PedConstraint*
 150 ped_constraint_new_from_min (const PedGeometry* min)
 151 {
 152         PedGeometry     full_dev;
 153
 154         PED_ASSERT (min != NULL);
 155
 156         ped_geometry_init (&full_dev, min->dev, 0, min->dev->length);
 157         return ped_constraint_new_from_min_max (min, &full_dev);
 158 }
 159
 160 /**
 161  * Return a constraint that requires a region to be entirely contained inside
 162  * \p max.
 163  *
 164  * \return \c NULL on failure.
 165  */
 166 PedConstraint*
 167 ped_constraint_new_from_max (const PedGeometry* max)
 168 {
 169         PED_ASSERT (max != NULL);
 170
 171         return ped_constraint_new (
 172                         ped_alignment_any, ped_alignment_any,
 173                         max, max, 1, max->length);
 174 }
 175
 176 /**
 177  * Duplicate a constraint.
 178  *
 179  * \return \c NULL on failure.
 180  */
 181 PedConstraint*
 182 ped_constraint_duplicate (const PedConstraint* constraint)
 183 {
 184         PED_ASSERT (constraint != NULL);
 185
 186         return ped_constraint_new (
 187                 constraint->start_align,
 188                 constraint->end_align,
 189                 constraint->start_range,
 190                 constraint->end_range,
 191                 constraint->min_size,
 192                 constraint->max_size);
 193 }
 194
 195 /**
 196  * Return a constraint that requires a region to satisfy both \p a and \p b.
 197  *
 198  * Moreover, any region satisfying \p a and \p b will also satisfy the returned
 199  * constraint.
 200  *
 201  * \return \c NULL if no solution could be found (note that \c NULL is a valid
 202  *         PedConstraint).
 203  */
 204 PedConstraint*
 205 ped_constraint_intersect (const PedConstraint* a, const PedConstraint* b)
 206 {
 207         PedAlignment*   start_align;
 208         PedAlignment*   end_align;
 209         PedGeometry*    start_range;
 210         PedGeometry*    end_range;
 211         PedSector       min_size;
 212         PedSector       max_size;
 213         PedConstraint*  constraint;
 214
 215         if (!a || !b)
 216                 return NULL;
 217
 218         start_align = ped_alignment_intersect (a->start_align, b->start_align);
 219         if (!start_align)
 220                 goto empty;
 221         end_align = ped_alignment_intersect (a->end_align, b->end_align);
 222         if (!end_align)
 223                 goto empty_destroy_start_align;
 224         start_range = ped_geometry_intersect (a->start_range, b->start_range);
 225         if (!start_range)
 226                 goto empty_destroy_end_align;
 227         end_range = ped_geometry_intersect (a->end_range, b->end_range);
 228         if (!end_range)
 229                 goto empty_destroy_start_range;
 230         min_size = PED_MAX (a->min_size, b->min_size);
 231         max_size = PED_MIN (a->max_size, b->max_size);
 232
 233         constraint = ped_constraint_new (
 234                         start_align, end_align, start_range, end_range,
 235                         min_size, max_size);
 236         if (!constraint)
 237                 goto empty_destroy_end_range;
 238
 239         ped_alignment_destroy (start_align);
 240         ped_alignment_destroy (end_align);
 241         ped_geometry_destroy (start_range);
 242         ped_geometry_destroy (end_range);
 243         return constraint;
 244
 245 empty_destroy_end_range:
 246         ped_geometry_destroy (end_range);
 247 empty_destroy_start_range:
 248         ped_geometry_destroy (start_range);
 249 empty_destroy_end_align:
 250         ped_alignment_destroy (end_align);
 251 empty_destroy_start_align:
 252         ped_alignment_destroy (start_align);
 253 empty:
 254         return NULL;
 255 }
 256
 257 /**
 258  * Release the memory allocated for a PedConstraint constructed with
 259  * ped_constraint_init().
 260  */
 261 void
 262 ped_constraint_done (PedConstraint* constraint)
 263 {
 264         PED_ASSERT (constraint != NULL);
 265
 266         ped_alignment_destroy (constraint->start_align);
 267         ped_alignment_destroy (constraint->end_align);
 268         ped_geometry_destroy (constraint->start_range);
 269         ped_geometry_destroy (constraint->end_range);
 270 }
 271
 272 /**
 273  * Release the memory allocated for a PedConstraint constructed with
 274  * ped_constraint_new().
 275  */
 276 void
 277 ped_constraint_destroy (PedConstraint* constraint)
 278 {
 279         if (constraint) {
 280                 ped_constraint_done (constraint);
 281                 free (constraint);
 282         }
 283 }
 284
 285 /*
 286  * Return the region within which the start must lie
 287  * in order to satisfy a constriant.  It takes into account
 288  * constraint->start_range, constraint->min_size and constraint->max_size.
 289  * All sectors in this range that also satisfy alignment requirements have
 290  * an end, such that the (start, end) satisfy the constraint.
 291  */
 292 static PedGeometry*
 293 _constraint_get_canonical_start_range (const PedConstraint* constraint)
 294 {
 295         PedSector       first_end_soln;
 296         PedSector       last_end_soln;
 297         PedSector       min_start;
 298         PedSector       max_start;
 299         PedGeometry     start_min_max_range;
 300
 301         if (constraint->min_size > constraint->max_size)
 302                 return NULL;
 303
 304         first_end_soln = ped_alignment_align_down (
 305                         constraint->end_align, constraint->end_range,
 306                         constraint->end_range->start);
 307         last_end_soln = ped_alignment_align_up (
 308                         constraint->end_align, constraint->end_range,
 309                         constraint->end_range->end);
 310         if (first_end_soln == -1 || last_end_soln == -1
 311             || first_end_soln > last_end_soln
 312             || last_end_soln < constraint->min_size)
 313                 return NULL;
 314
 315         min_start = first_end_soln - constraint->max_size + 1;
 316         if (min_start < 0)
 317                 min_start = 0;
 318         max_start = last_end_soln - constraint->min_size + 1;
 319         if (max_start < 0)
 320                 return NULL;
 321
 322         ped_geometry_init (
 323                 &start_min_max_range, constraint->start_range->dev,
 324                 min_start, max_start - min_start + 1);
 325
 326         return ped_geometry_intersect (&start_min_max_range,
 327                                        constraint->start_range);
 328 }
 329
 330 /*
 331  * Return the nearest start that will have at least one other end that
 332  * together satisfy the constraint.
 333  */
 334 static PedSector
 335 _constraint_get_nearest_start_soln (const PedConstraint* constraint,
 336                                     PedSector start)
 337 {
 338         PedGeometry*    start_range;
 339         PedSector       result;
 340
 341         start_range = _constraint_get_canonical_start_range (constraint);
 342         if (!start_range)
 343                 return -1;
 344         result = ped_alignment_align_nearest (
 345                         constraint->start_align, start_range, start);
 346         ped_geometry_destroy (start_range);
 347         return result;
 348 }
 349
 350 /*
 351  * Given a constraint and a start ("half of the solution"), find the
 352  * range of all possible ends, such that all (start, end) are solutions
 353  * to constraint (subject to additional alignment requirements).
 354  */
 355 static PedGeometry*
 356 _constraint_get_end_range (const PedConstraint* constraint, PedSector start)
 357 {
 358         PedDevice*      dev = constraint->end_range->dev;
 359         PedSector       first_min_max_end;
 360         PedSector       last_min_max_end;
 361         PedGeometry     end_min_max_range;
 362
 363         if (start + constraint->min_size - 1 > dev->length - 1)
 364                 return NULL;
 365
 366         first_min_max_end = start + constraint->min_size - 1;
 367         last_min_max_end = start + constraint->max_size - 1;
 368         if (last_min_max_end > dev->length - 1)
 369                 last_min_max_end = dev->length - 1;
 370
 371         ped_geometry_init (&end_min_max_range, dev,
 372                            first_min_max_end,
 373                            last_min_max_end - first_min_max_end + 1);
 374
 375         return ped_geometry_intersect (&end_min_max_range,
 376                                        constraint->end_range);
 377 }
 378
 379 /*
 380  * Given "constraint" and "start", find the end that is nearest to
 381  * "end", such that ("start", the end) together form a solution to
 382  * "constraint".
 383  */
 384 static PedSector
 385 _constraint_get_nearest_end_soln (const PedConstraint* constraint,
 386                                   PedSector start, PedSector end)
 387 {
 388         PedGeometry*    end_range;
 389         PedSector       result;
 390
 391         end_range = _constraint_get_end_range (constraint, start);
 392         if (!end_range)
 393                 return -1;
 394
 395         result = ped_alignment_align_nearest (constraint->end_align, end_range,
 396                                               end);
 397         ped_geometry_destroy (end_range);
 398         return result;
 399 }
 400
 401 /**
 402  * Return the nearest region to \p geom that satisfy a \p constraint.
 403  *
 404  * Note that "nearest" is somewhat ambiguous.  This function makes
 405  * no guarantees about how this ambiguity is resovled.
 406  *
 407  * \return PedGeometry, or NULL when a \p constrain cannot be satisfied
 408  */
 409 PedGeometry*
 410 ped_constraint_solve_nearest (
 411         const PedConstraint* constraint, const PedGeometry* geom)
 412 {
 413         PedSector       start;
 414         PedSector       end;
 415         PedGeometry*    result;
 416
 417         if (constraint == NULL)
 418                 return NULL;
 419
 420         PED_ASSERT (geom != NULL);
 421         PED_ASSERT (constraint->start_range->dev == geom->dev);
 422
 423         start = _constraint_get_nearest_start_soln (constraint, geom->start);
 424         if (start == -1)
 425                 return NULL;
 426         end = _constraint_get_nearest_end_soln (constraint, start, geom->end);
 427         if (end == -1)
 428                 return NULL;
 429
 430         result = ped_geometry_new (geom->dev, start, end - start + 1);
 431         if (!result)
 432                 return NULL;
 433         PED_ASSERT (ped_constraint_is_solution (constraint, result));
 434         return result;
 435 }
 436
 437 /**
 438  * Find the largest region that satisfies a constraint.
 439  *
 440  * There might be more than one solution.  This function makes no
 441  * guarantees about which solution it will choose in this case.
 442  */
 443 PedGeometry*
 444 ped_constraint_solve_max (const PedConstraint* constraint)
 445 {
 446         PedDevice*      dev;
 447         PedGeometry     full_dev;
 448
 449         if (!constraint)
 450                 return NULL;
 451         dev = constraint->start_range->dev;
 452         ped_geometry_init (&full_dev, dev, 0, dev->length - 1);
 453         return ped_constraint_solve_nearest (constraint, &full_dev);
 454 }
 455
 456 /**
 457  * Check whether \p geom satisfies the given constraint.
 458  *
 459  * \return \c 1 if it does.
 460  **/
 461 int
 462 ped_constraint_is_solution (const PedConstraint* constraint,
 463                             const PedGeometry* geom)
 464 {
 465         PED_ASSERT (constraint != NULL);
 466         PED_ASSERT (geom != NULL);
 467
 468         if (!ped_alignment_is_aligned (constraint->start_align, NULL,
 469                                        geom->start))
 470                 return 0;
 471         if (!ped_alignment_is_aligned (constraint->end_align, NULL, geom->end))
 472                 return 0;
 473         if (!ped_geometry_test_sector_inside (constraint->start_range,
 474                                               geom->start))
 475                 return 0;
 476         if (!ped_geometry_test_sector_inside (constraint->end_range, geom->end))
 477                 return 0;
 478         if (geom->length < constraint->min_size)
 479                 return 0;
 480         if (geom->length > constraint->max_size)
 481                 return 0;
 482         return 1;
 483 }
 484
 485 /**
 486  * Return a constraint that any region on the given device will satisfy.
 487  */
 488 PedConstraint*
 489 ped_constraint_any (const PedDevice* dev)
 490 {
 491         PedGeometry     full_dev;
 492
 493         if (!ped_geometry_init (&full_dev, dev, 0, dev->length))
 494                 return NULL;
 495
 496         return ped_constraint_new (
 497                         ped_alignment_any,
 498                         ped_alignment_any,
 499                         &full_dev,
 500                         &full_dev,
 501                         1,
 502                         dev->length);
 503 }
 504
 505 /**
 506  * Return a constraint that only the given region will satisfy.
 507  */
 508 PedConstraint*
 509 ped_constraint_exact (const PedGeometry* geom)
 510 {
 511         PedAlignment    start_align;
 512         PedAlignment    end_align;
 513         PedGeometry     start_sector;
 514         PedGeometry     end_sector;
 515         int ok;
 516
 517         /* With grain size of 0, it always succeeds.  */
 518         ok = ped_alignment_init (&start_align, geom->start, 0);
 519         assert (ok);
 520         ok = ped_alignment_init (&end_align, geom->end, 0);
 521         assert (ok);
 522
 523         ok = ped_geometry_init (&start_sector, geom->dev, geom->start, 1);
 524         if (!ok)
 525           return NULL;
 526         ok = ped_geometry_init (&end_sector, geom->dev, geom->end, 1);
 527         if (!ok)
 528           return NULL;
 529
 530         return ped_constraint_new (&start_align, &end_align,
 531                                    &start_sector, &end_sector, 1,
 532                                    geom->dev->length);
 533 }
 534
 535 /**
 536  * @}
 537  */