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