1 /*
   2     libparted - a library for manipulating disk partitions
   3     Copyright (C) 2000, 2001, 2007 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 
  50 /**
  51  * Initializes a pre-allocated piece of memory to contain a constraint
  52  * with the supplied default values.
  53  *
  54  * \return \c 0 on failure.
  55  */
  56 int
  57 ped_constraint_init (
  58         PedConstraint* constraint,
  59         const PedAlignment* start_align,
  60         const PedAlignment* end_align,
  61         const PedGeometry* start_range,
  62         const PedGeometry* end_range,
  63         PedSector min_size,
  64         PedSector max_size)
  65 {
  66         PED_ASSERT (constraint != NULL, return 0);
  67         PED_ASSERT (start_range != NULL, return 0);
  68         PED_ASSERT (end_range != NULL, return 0);
  69         PED_ASSERT (min_size > 0, return 0);
  70         PED_ASSERT (max_size > 0, return 0);
  71 
  72         constraint->start_align = ped_alignment_duplicate (start_align);
  73         constraint->end_align = ped_alignment_duplicate (end_align);
  74         constraint->start_range = ped_geometry_duplicate (start_range);
  75         constraint->end_range = ped_geometry_duplicate (end_range);
  76         constraint->min_size = min_size;
  77         constraint->max_size = max_size;
  78 
  79         return 1;
  80 }
  81 
  82 /**
  83  * Convenience wrapper for ped_constraint_init().
  84  *
  85  * Allocates a new piece of memory and initializes the constraint.
  86  *
  87  * \return \c NULL on failure.
  88  */
  89 PedConstraint*
  90 ped_constraint_new (
  91         const PedAlignment* start_align,
  92         const PedAlignment* end_align,
  93         const PedGeometry* start_range,
  94         const PedGeometry* end_range,
  95         PedSector min_size,
  96         PedSector max_size)
  97 {
  98         PedConstraint*  constraint;
  99 
 100         constraint = (PedConstraint*) ped_malloc (sizeof (PedConstraint));
 101         if (!constraint)
 102                 goto error;
 103         if (!ped_constraint_init (constraint, start_align, end_align,
 104                                   start_range, end_range, min_size, max_size))
 105                 goto error_free_constraint;
 106         return constraint;
 107 
 108 error_free_constraint:
 109         ped_free (constraint);
 110 error:
 111         return NULL;
 112 }
 113 
 114 /**
 115  * Return a constraint that requires a region to be entirely contained inside
 116  * \p max, and to entirely contain \p min.
 117  *
 118  * \return \c NULL on failure.
 119  */
 120 PedConstraint*
 121 ped_constraint_new_from_min_max (
 122         const PedGeometry* min,
 123         const PedGeometry* max)
 124 {
 125         PedGeometry     start_range;
 126         PedGeometry     end_range;
 127 
 128         PED_ASSERT (min != NULL, return NULL);
 129         PED_ASSERT (max != NULL, return NULL);
 130         PED_ASSERT (ped_geometry_test_inside (max, min), return NULL);
 131 
 132         ped_geometry_init (&start_range, min->dev, max->start,
 133                            min->start - max->start + 1);
 134         ped_geometry_init (&end_range, min->dev, min->end,
 135                            max->end - min->end + 1);
 136 
 137         return ped_constraint_new (
 138                         ped_alignment_any, ped_alignment_any,
 139                         &start_range, &end_range,
 140                         min->length, max->length);
 141 }
 142 
 143 /**
 144  * Return a constraint that requires a region to entirely contain \p min.
 145  *
 146  * \return \c NULL on failure.
 147  */
 148 PedConstraint*
 149 ped_constraint_new_from_min (const PedGeometry* min)
 150 {
 151         PedGeometry     full_dev;
 152 
 153         PED_ASSERT (min != NULL, return NULL);
 154 
 155         ped_geometry_init (&full_dev, min->dev, 0, min->dev->length);
 156         return ped_constraint_new_from_min_max (min, &full_dev);
 157 }
 158 
 159 /**
 160  * Return a constraint that requires a region to be entirely contained inside
 161  * \p max.
 162  *
 163  * \return \c NULL on failure.
 164  */
 165 PedConstraint*
 166 ped_constraint_new_from_max (const PedGeometry* max)
 167 {
 168         PED_ASSERT (max != NULL, return NULL);
 169 
 170         return ped_constraint_new (
 171                         ped_alignment_any, ped_alignment_any,
 172                         max, max, 1, max->length);
 173 }
 174 
 175 /**
 176  * Duplicate a constraint.
 177  *
 178  * \return \c NULL on failure.
 179  */
 180 PedConstraint*
 181 ped_constraint_duplicate (const PedConstraint* constraint)
 182 {
 183         PED_ASSERT (constraint != NULL, return NULL);
 184 
 185         return ped_constraint_new (
 186                 constraint->start_align,
 187                 constraint->end_align,
 188                 constraint->start_range,
 189                 constraint->end_range,
 190                 constraint->min_size,
 191                 constraint->max_size);
 192 }
 193 
 194 /**
 195  * Return a constraint that requires a region to satisfy both \p a and \p b.
 196  *
 197  * Moreover, any region satisfying \p a and \p b will also satisfy the returned
 198  * constraint.
 199  *
 200  * \return \c NULL if no solution could be found (note that \c NULL is a valid
 201  *         PedConstraint).
 202  */
 203 PedConstraint*
 204 ped_constraint_intersect (const PedConstraint* a, const PedConstraint* b)
 205 {
 206         PedAlignment*   start_align;
 207         PedAlignment*   end_align;
 208         PedGeometry*    start_range;
 209         PedGeometry*    end_range;
 210         PedSector       min_size;
 211         PedSector       max_size;
 212         PedConstraint*  constraint;
 213 
 214         if (!a || !b)
 215                 return NULL;
 216 
 217         start_align = ped_alignment_intersect (a->start_align, b->start_align);
 218         if (!start_align)
 219                 goto empty;
 220         end_align = ped_alignment_intersect (a->end_align, b->end_align);
 221         if (!end_align)
 222                 goto empty_destroy_start_align;
 223         start_range = ped_geometry_intersect (a->start_range, b->start_range);
 224         if (!start_range)
 225                 goto empty_destroy_end_align;
 226         end_range = ped_geometry_intersect (a->end_range, b->end_range);
 227         if (!end_range)
 228                 goto empty_destroy_start_range;
 229         min_size = PED_MAX (a->min_size, b->min_size);
 230         max_size = PED_MIN (a->max_size, b->max_size);
 231 
 232         constraint = ped_constraint_new (
 233                         start_align, end_align, start_range, end_range,
 234                         min_size, max_size);
 235         if (!constraint)
 236                 goto empty_destroy_end_range;
 237 
 238         ped_alignment_destroy (start_align);
 239         ped_alignment_destroy (end_align);
 240         ped_geometry_destroy (start_range);
 241         ped_geometry_destroy (end_range);
 242         return constraint;
 243 
 244 empty_destroy_end_range:
 245         ped_geometry_destroy (end_range);
 246 empty_destroy_start_range:
 247         ped_geometry_destroy (start_range);
 248 empty_destroy_end_align:
 249         ped_alignment_destroy (end_align);
 250 empty_destroy_start_align:
 251         ped_alignment_destroy (start_align);
 252 empty:
 253         return NULL;
 254 }
 255 
 256 /**
 257  * Release the memory allocated for a PedConstraint constructed with
 258  * ped_constraint_init().
 259  */
 260 void
 261 ped_constraint_done (PedConstraint* constraint)
 262 {
 263         PED_ASSERT (constraint != NULL, return);
 264 
 265         ped_alignment_destroy (constraint->start_align);
 266         ped_alignment_destroy (constraint->end_align);
 267         ped_geometry_destroy (constraint->start_range);
 268         ped_geometry_destroy (constraint->end_range);
 269 }
 270 
 271 /**
 272  * Release the memory allocated for a PedConstraint constructed with
 273  * ped_constraint_new().
 274  */
 275 void
 276 ped_constraint_destroy (PedConstraint* constraint)
 277 {
 278         if (constraint) {
 279                 ped_constraint_done (constraint);
 280                 ped_free (constraint);
 281         }
 282 }
 283 
 284 /*
 285  * Return the region within which the start must lie
 286  * in order to satisfy a constriant.  It takes into account
 287  * constraint->start_range, constraint->min_size and constraint->max_size.
 288  * All sectors in this range that also satisfy alignment requirements have
 289  * an end, such that the (start, end) satisfy the constraint.
 290  */
 291 static PedGeometry*
 292 _constraint_get_canonical_start_range (const PedConstraint* constraint)
 293 {
 294         PedSector       first_end_soln;
 295         PedSector       last_end_soln;
 296         PedSector       min_start;
 297         PedSector       max_start;
 298         PedGeometry     start_min_max_range;
 299 
 300         if (constraint->min_size > constraint->max_size)
 301                 return NULL;
 302 
 303         first_end_soln = ped_alignment_align_down (
 304                         constraint->end_align, constraint->end_range,
 305                         constraint->end_range->start);
 306         last_end_soln = ped_alignment_align_up (
 307                         constraint->end_align, constraint->end_range,
 308                         constraint->end_range->end);
 309         if (first_end_soln == -1 || last_end_soln == -1
 310             || first_end_soln > last_end_soln
 311             || last_end_soln < constraint->min_size)
 312                 return NULL;
 313 
 314         min_start = first_end_soln - constraint->max_size + 1;
 315         if (min_start < 0)
 316                 min_start = 0;
 317         max_start = last_end_soln - constraint->min_size + 1;
 318         if (max_start < 0)
 319                 return NULL;
 320 
 321         ped_geometry_init (
 322                 &start_min_max_range, constraint->start_range->dev,
 323                 min_start, max_start - min_start + 1);
 324 
 325         return ped_geometry_intersect (&start_min_max_range,
 326                                        constraint->start_range);
 327 }
 328 
 329 /*
 330  * Return the nearest start that will have at least one other end that
 331  * together satisfy the constraint.
 332  */
 333 static PedSector
 334 _constraint_get_nearest_start_soln (const PedConstraint* constraint,
 335                                     PedSector start)
 336 {
 337         PedGeometry*    start_range;
 338         PedSector       result;
 339 
 340         start_range = _constraint_get_canonical_start_range (constraint);
 341         if (!start_range)
 342                 return -1;
 343         result = ped_alignment_align_nearest (
 344                         constraint->start_align, start_range, start);
 345         ped_geometry_destroy (start_range);
 346         return result;
 347 }
 348 
 349 /*
 350  * Given a constraint and a start ("half of the solution"), find the
 351  * range of all possible ends, such that all (start, end) are solutions
 352  * to constraint (subject to additional alignment requirements).
 353  */
 354 static PedGeometry*
 355 _constraint_get_end_range (const PedConstraint* constraint, PedSector start)
 356 {
 357         PedDevice*      dev = constraint->end_range->dev;
 358         PedSector       first_min_max_end;
 359         PedSector       last_min_max_end;
 360         PedGeometry     end_min_max_range;
 361 
 362         if (start + constraint->min_size - 1 > dev->length - 1)
 363                 return NULL;
 364 
 365         first_min_max_end = start + constraint->min_size - 1;
 366         last_min_max_end = start + constraint->max_size - 1;
 367         if (last_min_max_end > dev->length - 1)
 368                 last_min_max_end = dev->length - 1;
 369 
 370         ped_geometry_init (&end_min_max_range, dev,
 371                            first_min_max_end,
 372                            last_min_max_end - first_min_max_end + 1);
 373 
 374         return ped_geometry_intersect (&end_min_max_range,
 375                                        constraint->end_range);
 376 }
 377 
 378 /*
 379  * Given "constraint" and "start", find the end that is nearest to
 380  * "end", such that ("start", the end) together form a solution to
 381  * "constraint".
 382  */
 383 static PedSector
 384 _constraint_get_nearest_end_soln (const PedConstraint* constraint,
 385                                   PedSector start, PedSector end)
 386 {
 387         PedGeometry*    end_range;
 388         PedSector       result;
 389 
 390         end_range = _constraint_get_end_range (constraint, start);
 391         if (!end_range)
 392                 return -1;
 393 
 394         result = ped_alignment_align_nearest (constraint->end_align, end_range,
 395                                               end);
 396         ped_geometry_destroy (end_range);
 397         return result;
 398 }
 399 
 400 /**
 401  * Return the nearest region to \p geom that satisfy a \p constraint.
 402  * 
 403  * Note that "nearest" is somewhat ambiguous.  This function makes
 404  * no guarantees about how this ambiguity is resovled.
 405  *
 406  * \return PedGeometry, or NULL when a \p constrain cannot be satisfied
 407  */
 408 PedGeometry*
 409 ped_constraint_solve_nearest (
 410         const PedConstraint* constraint, const PedGeometry* geom)
 411 {
 412         PedSector       start;
 413         PedSector       end;
 414         PedGeometry*    result;
 415 
 416         if (constraint == NULL)
 417                 return NULL;
 418 
 419         PED_ASSERT (geom != NULL, return NULL);
 420         PED_ASSERT (constraint->start_range->dev == geom->dev, return NULL);
 421 
 422         start = _constraint_get_nearest_start_soln (constraint, geom->start);
 423         if (start == -1)
 424                 return NULL;
 425         end = _constraint_get_nearest_end_soln (constraint, start, geom->end);
 426         if (end == -1)
 427                 return NULL;
 428 
 429         result = ped_geometry_new (geom->dev, start, end - start + 1);
 430         if (!result)
 431                 return NULL;
 432         PED_ASSERT (ped_constraint_is_solution (constraint, result),
 433                     return NULL);
 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, return 0);
 466         PED_ASSERT (geom != NULL, return 0);
 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 
 516         ped_alignment_init (&start_align, geom->start, 0);
 517         ped_alignment_init (&end_align, geom->end, 0);
 518         ped_geometry_init (&start_sector, geom->dev, geom->start, 1);
 519         ped_geometry_init (&end_sector, geom->dev, geom->end, 1);
 520 
 521         return ped_constraint_new (&start_align, &end_align,
 522                                    &start_sector, &end_sector, 1,
 523                                    geom->dev->length);
 524 }
 525 
 526 /**
 527  * @}
 528  */
 529