libparted/labels/dos.c

   1 /*
   2     libparted - a library for manipulating disk partitions
   3     Copyright (C) 1999-2001, 2004-2005, 2007-2011 Free Software Foundation,
   4     Inc.
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 3 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include <config.h>
  21
  22 #include <sys/time.h>
  23 #include <stdbool.h>
  24 #include <parted/parted.h>
  25 #include <parted/debug.h>
  26 #include <parted/endian.h>
  27
  28 #if ENABLE_NLS
  29 #  include <libintl.h>
  30 #  define _(String) dgettext (PACKAGE, String)
  31 #else
  32 #  define _(String) (String)
  33 #endif /* ENABLE_NLS */
  34
  35 #include "misc.h"
  36 #include "pt-tools.h"
  37
  38 /* this MBR boot code is loaded into 0000:7c00 by the BIOS.  See mbr.s for
  39  * the source, and how to build it
  40  */
  41
  42 static const char MBR_BOOT_CODE[] = {
  43         0xfa, 0xb8, 0x00, 0x10, 0x8e, 0xd0, 0xbc, 0x00,
  44         0xb0, 0xb8, 0x00, 0x00, 0x8e, 0xd8, 0x8e, 0xc0,
  45         0xfb, 0xbe, 0x00, 0x7c, 0xbf, 0x00, 0x06, 0xb9,
  46         0x00, 0x02, 0xf3, 0xa4, 0xea, 0x21, 0x06, 0x00,
  47         0x00, 0xbe, 0xbe, 0x07, 0x38, 0x04, 0x75, 0x0b,
  48         0x83, 0xc6, 0x10, 0x81, 0xfe, 0xfe, 0x07, 0x75,
  49         0xf3, 0xeb, 0x16, 0xb4, 0x02, 0xb0, 0x01, 0xbb,
  50         0x00, 0x7c, 0xb2, 0x80, 0x8a, 0x74, 0x01, 0x8b,
  51         0x4c, 0x02, 0xcd, 0x13, 0xea, 0x00, 0x7c, 0x00,
  52         0x00, 0xeb, 0xfe
  53 };
  54
  55 #define MSDOS_MAGIC             0xAA55
  56 #define PARTITION_MAGIC_MAGIC   0xf6f6
  57
  58 /* The maximum number of DOS primary partitions.  */
  59 #define DOS_N_PRI_PARTITIONS    4
  60
  61 #define PARTITION_EMPTY         0x00
  62 #define PARTITION_FAT12         0x01
  63 #define PARTITION_FAT16_SM      0x04
  64 #define PARTITION_DOS_EXT       0x05
  65 #define PARTITION_FAT16         0x06
  66 #define PARTITION_NTFS          0x07
  67 #define PARTITION_HPFS          0x07
  68 #define PARTITION_FAT32         0x0b
  69 #define PARTITION_FAT32_LBA     0x0c
  70 #define PARTITION_FAT16_LBA     0x0e
  71 #define PARTITION_EXT_LBA       0x0f
  72
  73 #define PART_FLAG_HIDDEN        0x10    /* Valid for FAT/NTFS only */
  74 #define PARTITION_FAT12_H       (PARTITION_FAT12        | PART_FLAG_HIDDEN)
  75 #define PARTITION_FAT16_SM_H    (PARTITION_FAT16_SM     | PART_FLAG_HIDDEN)
  76 #define PARTITION_DOS_EXT_H     (PARTITION_DOS_EXT      | PART_FLAG_HIDDEN)
  77 #define PARTITION_FAT16_H       (PARTITION_FAT16        | PART_FLAG_HIDDEN)
  78 #define PARTITION_NTFS_H        (PARTITION_NTFS         | PART_FLAG_HIDDEN)
  79 #define PARTITION_FAT32_H       (PARTITION_FAT32        | PART_FLAG_HIDDEN)
  80 #define PARTITION_FAT32_LBA_H   (PARTITION_FAT32_LBA    | PART_FLAG_HIDDEN)
  81 #define PARTITION_FAT16_LBA_H   (PARTITION_FAT16_LBA    | PART_FLAG_HIDDEN)
  82
  83 #define PARTITION_COMPAQ_DIAG   0x12
  84 #define PARTITION_MSFT_RECOVERY 0x27
  85 #define PARTITION_LDM           0x42
  86 #define PARTITION_LINUX_SWAP    0x82
  87 #define PARTITION_LINUX         0x83
  88 #define PARTITION_LINUX_EXT     0x85
  89 #define PARTITION_LINUX_LVM     0x8e
  90 #define PARTITION_HFS           0xaf
  91 #define PARTITION_SUN_UFS       0xbf
  92 #define PARTITION_DELL_DIAG     0xde
  93 #define PARTITION_GPT           0xee
  94 #define PARTITION_PALO          0xf0
  95 #define PARTITION_PREP          0x41
  96 #define PARTITION_LINUX_RAID    0xfd
  97 #define PARTITION_LINUX_LVM_OLD 0xfe
  98
  99 /* This constant contains the maximum cylinder number that can be represented
 100  * in (C,H,S) notation.  Higher cylinder numbers are reserved for
 101  * "too big" indicators (in which case only LBA addressing can be used).
 102  *      Some partition tables in the wild indicate this number is 1021.
 103  * (i.e. 1022 is sometimes used to indicate "use LBA").
 104  */
 105 #define MAX_CHS_CYLINDER        1021
 106 #define MAX_TOTAL_PART          16
 107
 108 typedef struct _DosRawPartition         DosRawPartition;
 109 typedef struct _DosRawTable             DosRawTable;
 110
 111 /* note: lots of bit-bashing here, thus, you shouldn't look inside it.
 112  * Use chs_to_sector() and sector_to_chs() instead.
 113  */
 114 typedef struct {
 115         uint8_t         head;
 116         uint8_t         sector;
 117         uint8_t         cylinder;
 118 } __attribute__((packed)) RawCHS;
 119
 120 /* ripped from Linux source */
 121 struct _DosRawPartition {
 122         uint8_t         boot_ind;       /* 00:  0x80 - active */
 123         RawCHS          chs_start;      /* 01: */
 124         uint8_t         type;           /* 04: partition type */
 125         RawCHS          chs_end;        /* 05: */
 126         uint32_t        start;          /* 08: starting sector counting from 0 */
 127         uint32_t        length;         /* 0c: nr of sectors in partition */
 128 } __attribute__((packed));
 129
 130 struct _DosRawTable {
 131         char                    boot_code [440];
 132         uint32_t                mbr_signature;  /* really a unique ID */
 133         uint16_t                Unknown;
 134         DosRawPartition         partitions [DOS_N_PRI_PARTITIONS];
 135         uint16_t                magic;
 136 } __attribute__((packed));
 137
 138 /* OrigState is information we want to preserve about the partition for
 139  * dealing with CHS issues
 140  */
 141 typedef struct {
 142         PedGeometry     geom;
 143         DosRawPartition raw_part;
 144         PedSector       lba_offset;     /* needed for computing start/end for
 145                                          * logical partitions */
 146 } OrigState;
 147
 148 typedef struct {
 149         int             cylinder_alignment;
 150 } DosDiskData;
 151
 152 typedef struct {
 153         unsigned char   system;
 154         int             boot;
 155         int             hidden;
 156         int             raid;
 157         int             lvm;
 158         int             lba;
 159         int             palo;
 160         int             prep;
 161         int             diag;
 162         OrigState*      orig;                   /* used for CHS stuff */
 163 } DosPartitionData;
 164
 165 static PedDiskType msdos_disk_type;
 166
 167 #if 0
 168 From http://www.win.tue.nl/~aeb/linux/fs/fat/fat-1.html
 169
 170 The 2-byte numbers are stored little endian (low order byte first).
 171
 172 Here the FAT12 version, that is also the common part of the FAT12, FAT16 and FAT32 boot sectors. See further below.
 173
 174 Bytes   Content
 175 0-2     Jump to bootstrap (E.g. eb 3c 90; on i86: JMP 003E NOP.
 176         One finds either eb xx 90, or e9 xx xx.
 177         The position of the bootstrap varies.)
 178 3-10    OEM name/version (E.g. "IBM  3.3", "IBM 20.0", "MSDOS5.0", "MSWIN4.0".
 179         Various format utilities leave their own name, like "CH-FOR18".
 180         Sometimes just garbage. Microsoft recommends "MSWIN4.1".)
 181         /* BIOS Parameter Block starts here */
 182 11-12   Number of bytes per sector (512)
 183         Must be one of 512, 1024, 2048, 4096.
 184 13      Number of sectors per cluster (1)
 185         Must be one of 1, 2, 4, 8, 16, 32, 64, 128.
 186         A cluster should have at most 32768 bytes. In rare cases 65536 is OK.
 187 14-15   Number of reserved sectors (1)
 188         FAT12 and FAT16 use 1. FAT32 uses 32.
 189 16      Number of FAT copies (2)
 190 17-18   Number of root directory entries (224)
 191         0 for FAT32. 512 is recommended for FAT16.
 192 19-20   Total number of sectors in the filesystem (2880)
 193         (in case the partition is not FAT32 and smaller than 32 MB)
 194 21      Media descriptor type (f0: 1.4 MB floppy, f8: hard disk; see below)
 195 22-23   Number of sectors per FAT (9)
 196         0 for FAT32.
 197 24-25   Number of sectors per track (12)
 198 26-27   Number of heads (2, for a double-sided diskette)
 199 28-29   Number of hidden sectors (0)
 200         Hidden sectors are sectors preceding the partition.
 201         /* BIOS Parameter Block ends here */
 202 30-509  Bootstrap
 203 510-511 Signature 55 aa
 204 #endif
 205
 206 /* There is a significant risk of misclassifying (as msdos)
 207    a disk that is composed solely of a single FAT partition.
 208    Return false if sector S could not be a valid FAT boot sector.
 209    Otherwise, return true.  */
 210 static bool
 211 maybe_FAT (unsigned char const *s)
 212 {
 213   if (! (s[0] == 0xeb || s[0] == 0xe9))
 214     return false;
 215
 216   unsigned int sector_size = PED_LE16_TO_CPU (*(uint16_t *) (s + 11));
 217   switch (sector_size)
 218     {
 219     case 512:
 220     case 1024:
 221     case 2048:
 222     case 4096:
 223       break;
 224     default:
 225       return false;
 226     }
 227
 228   if (! (s[21] == 0xf0 || s[21] == 0xf8))
 229     return false;
 230
 231   return true;
 232 }
 233
 234 static int
 235 msdos_probe (const PedDevice *dev)
 236 {
 237         PedDiskType*    disk_type;
 238         DosRawTable*    part_table;
 239         int             i;
 240
 241         PED_ASSERT (dev != NULL, return 0);
 242
 243         if (dev->sector_size < sizeof *part_table)
 244                 return 0;
 245
 246         void *label;
 247         if (!ptt_read_sector (dev, 0, &label))
 248                 return 0;
 249
 250         part_table = (DosRawTable *) label;
 251
 252         /* check magic */
 253         if (PED_LE16_TO_CPU (part_table->magic) != MSDOS_MAGIC)
 254                 goto probe_fail;
 255
 256         /* If this is a FAT fs, fail here.  Checking for the FAT signature
 257          * has some false positives; instead, do what the Linux kernel does
 258          * and ensure that each partition has a boot indicator that is
 259          * either 0 or 0x80.
 260          */
 261         unsigned int n_active = 0;
 262         for (i = 0; i < DOS_N_PRI_PARTITIONS; i++) {
 263                 if (part_table->partitions[i].boot_ind == 0x80)
 264                         ++n_active;
 265                 if (part_table->partitions[i].boot_ind != 0
 266                     && part_table->partitions[i].boot_ind != 0x80)
 267                         goto probe_fail;
 268         }
 269
 270         /* If there are no active partitions and this is probably
 271            a FAT file system, do not classify it as msdos.  */
 272         if (n_active == 0 && maybe_FAT (label))
 273           goto probe_fail;
 274
 275         /* If this is a GPT disk, fail here */
 276         for (i = 0; i < DOS_N_PRI_PARTITIONS; i++) {
 277                 if (part_table->partitions[i].type == PARTITION_GPT)
 278                         goto probe_fail;
 279         }
 280
 281         /* If this is an AIX Physical Volume, fail here.  IBMA in EBCDIC */
 282         if (part_table->boot_code[0] == (char) 0xc9 &&
 283             part_table->boot_code[1] == (char) 0xc2 &&
 284             part_table->boot_code[2] == (char) 0xd4 &&
 285             part_table->boot_code[3] == (char) 0xc1)
 286                 goto probe_fail;
 287
 288 #ifdef ENABLE_PC98
 289         /* HACK: it's impossible to tell PC98 and msdos disk labels apart.
 290          * Someone made the signatures the same (very clever).  Since
 291          * PC98 has some idiosyncracies with it's boot-loader, it's detection
 292          * is more reliable */
 293         disk_type = ped_disk_type_get ("pc98");
 294         if (disk_type && disk_type->ops->probe (dev))
 295                 goto probe_fail;
 296 #endif /* ENABLE_PC98 */
 297
 298         free (label);
 299         return 1;
 300
 301  probe_fail:
 302         free (label);
 303         return 0;
 304 }
 305
 306 static PedDisk*
 307 msdos_alloc (const PedDevice* dev)
 308 {
 309         PedDisk* disk;
 310         PED_ASSERT (dev != NULL, return NULL);
 311
 312         disk = _ped_disk_alloc ((PedDevice*)dev, &msdos_disk_type);
 313         if (disk) {
 314                 DosDiskData *disk_specific = ped_malloc(sizeof *disk_specific);
 315                 if (!disk_specific) {
 316                         free (disk);
 317                         return NULL;
 318                 }
 319                 disk_specific->cylinder_alignment = 1;
 320                 disk->disk_specific = disk_specific;
 321         }
 322
 323         return disk;
 324 }
 325
 326 static PedDisk*
 327 msdos_duplicate (const PedDisk* disk)
 328 {
 329         PedDisk*        new_disk;
 330
 331         new_disk = ped_disk_new_fresh (disk->dev, &msdos_disk_type);
 332         if (!new_disk)
 333                 return NULL;
 334
 335         memcpy(new_disk->disk_specific, disk->disk_specific,
 336                sizeof(DosDiskData));
 337
 338         return new_disk;
 339 }
 340
 341 static void
 342 msdos_free (PedDisk* disk)
 343 {
 344         PED_ASSERT (disk != NULL, return);
 345
 346         DosDiskData *disk_specific = disk->disk_specific;
 347         _ped_disk_free (disk);
 348         free(disk_specific);
 349 }
 350
 351 static int
 352 msdos_disk_set_flag (PedDisk *disk, PedDiskFlag flag, int state)
 353 {
 354         DosDiskData *disk_specific = disk->disk_specific;
 355         switch (flag) {
 356         case PED_DISK_CYLINDER_ALIGNMENT:
 357                 disk_specific->cylinder_alignment = !!state;
 358                 return 1;
 359         default:
 360                 return 0;
 361         }
 362 }
 363
 364 static int
 365 msdos_disk_get_flag (const PedDisk *disk, PedDiskFlag flag)
 366 {
 367         DosDiskData *disk_specific = disk->disk_specific;
 368         switch (flag) {
 369         case PED_DISK_CYLINDER_ALIGNMENT:
 370                 return disk_specific->cylinder_alignment;
 371         default:
 372                 return 0;
 373         }
 374 }
 375
 376 static int
 377 msdos_disk_is_flag_available (const PedDisk *disk, PedDiskFlag flag)
 378 {
 379         switch (flag) {
 380         case PED_DISK_CYLINDER_ALIGNMENT:
 381                return 1;
 382         default:
 383                return 0;
 384         }
 385 }
 386
 387 static int
 388 chs_get_cylinder (const RawCHS* chs)
 389 {
 390         return chs->cylinder + ((chs->sector >> 6) << 8);
 391 }
 392
 393 static int
 394 chs_get_head (const RawCHS* chs)
 395 {
 396         return chs->head;
 397 }
 398
 399 /* counts from 0 */
 400 static int
 401 chs_get_sector (const RawCHS* chs)
 402 {
 403         return (chs->sector & 0x3f) - 1;
 404 }
 405
 406 static PedSector
 407 chs_to_sector (const PedDevice* dev, const PedCHSGeometry *bios_geom,
 408                const RawCHS* chs)
 409 {
 410         PedSector       c;              /* not measured in sectors, but need */
 411         PedSector       h;              /* lots of bits */
 412         PedSector       s;
 413
 414         PED_ASSERT (bios_geom != NULL, return 0);
 415         PED_ASSERT (chs != NULL, return 0);
 416
 417         c = chs_get_cylinder (chs);
 418         h = chs_get_head (chs);
 419         s = chs_get_sector (chs);
 420
 421         if (c > MAX_CHS_CYLINDER)               /* MAGIC: C/H/S is irrelevant */
 422                 return 0;
 423         if (s < 0)
 424                 return 0;
 425         return (c * bios_geom->heads + h) * bios_geom->sectors + s;
 426 }
 427
 428 static void
 429 sector_to_chs (const PedDevice* dev, const PedCHSGeometry* bios_geom,
 430                PedSector sector, RawCHS* chs)
 431 {
 432         PedSector       real_c, real_h, real_s;
 433
 434         PED_ASSERT (dev != NULL, return);
 435         PED_ASSERT (chs != NULL, return);
 436
 437         if (!bios_geom)
 438                 bios_geom = &dev->bios_geom;
 439
 440         real_c = sector / (bios_geom->heads * bios_geom->sectors);
 441         real_h = (sector / bios_geom->sectors) % bios_geom->heads;
 442         real_s = sector % bios_geom->sectors;
 443
 444         if (real_c > MAX_CHS_CYLINDER) {
 445                 real_c = 1023;
 446                 real_h = bios_geom->heads - 1;
 447                 real_s = bios_geom->sectors - 1;
 448         }
 449
 450         chs->cylinder = real_c % 0x100;
 451         chs->head = real_h;
 452         chs->sector = real_s + 1 + (real_c >> 8 << 6);
 453 }
 454
 455 static PedSector
 456 legacy_start (const PedDisk* disk, const PedCHSGeometry* bios_geom,
 457               const DosRawPartition* raw_part)
 458 {
 459         PED_ASSERT (disk != NULL, return 0);
 460         PED_ASSERT (raw_part != NULL, return 0);
 461
 462         return chs_to_sector (disk->dev, bios_geom, &raw_part->chs_start);
 463 }
 464
 465 static PedSector
 466 legacy_end (const PedDisk* disk, const PedCHSGeometry* bios_geom,
 467             const DosRawPartition* raw_part)
 468 {
 469         PED_ASSERT (disk != NULL, return 0);
 470         PED_ASSERT (raw_part != NULL, return 0);
 471
 472         return chs_to_sector (disk->dev, bios_geom, &raw_part->chs_end);
 473 }
 474
 475 static PedSector
 476 linear_start (const PedDisk* disk, const DosRawPartition* raw_part,
 477               PedSector offset)
 478 {
 479         PED_ASSERT (disk != NULL, return 0);
 480         PED_ASSERT (raw_part != NULL, return 0);
 481
 482         return offset + PED_LE32_TO_CPU (raw_part->start);
 483 }
 484
 485 static PedSector
 486 linear_end (const PedDisk* disk, const DosRawPartition* raw_part,
 487             PedSector offset)
 488 {
 489         PED_ASSERT (disk != NULL, return 0);
 490         PED_ASSERT (raw_part != NULL, return 0);
 491
 492         return (linear_start (disk, raw_part, offset)
 493                 + (PED_LE32_TO_CPU (raw_part->length) - 1));
 494 }
 495
 496 #ifndef DISCOVER_ONLY
 497 static int
 498 partition_check_bios_geometry (PedPartition* part, PedCHSGeometry* bios_geom)
 499 {
 500         PedSector               leg_start, leg_end;
 501         DosPartitionData*       dos_data;
 502         PedDisk*                disk;
 503
 504         PED_ASSERT (part != NULL, return 0);
 505         PED_ASSERT (part->disk != NULL, return 0);
 506         PED_ASSERT (part->disk_specific != NULL, return 0);
 507         dos_data = part->disk_specific;
 508
 509         if (!dos_data->orig)
 510                 return 1;
 511
 512         disk = part->disk;
 513         leg_start = legacy_start (disk, bios_geom, &dos_data->orig->raw_part);
 514         leg_end = legacy_end (disk, bios_geom, &dos_data->orig->raw_part);
 515
 516         if (leg_start && leg_start != dos_data->orig->geom.start)
 517                 return 0;
 518         if (leg_end && leg_end != dos_data->orig->geom.end)
 519                 return 0;
 520         return 1;
 521 }
 522
 523 static int
 524 disk_check_bios_geometry (const PedDisk* disk, PedCHSGeometry* bios_geom)
 525 {
 526         PedPartition* part = NULL;
 527
 528         PED_ASSERT (disk != NULL, return 0);
 529
 530         while ((part = ped_disk_next_partition (disk, part))) {
 531                 if (ped_partition_is_active (part)) {
 532                         if (!partition_check_bios_geometry (part, bios_geom))
 533                                 return 0;
 534                 }
 535         }
 536
 537         return 1;
 538 }
 539
 540 static int
 541 probe_filesystem_for_geom (const PedPartition* part, PedCHSGeometry* bios_geom)
 542 {
 543         const char* ms_types[] = {"ntfs", "fat16", "fat32", NULL};
 544         int i;
 545         int found;
 546         unsigned char* buf;
 547         int sectors;
 548         int heads;
 549         int res = 0;
 550
 551         PED_ASSERT (bios_geom        != NULL, return 0);
 552         PED_ASSERT (part             != NULL, return 0);
 553         PED_ASSERT (part->disk       != NULL, return 0);
 554         PED_ASSERT (part->disk->dev  != NULL, return 0);
 555         PED_ASSERT (part->disk->dev->sector_size % PED_SECTOR_SIZE_DEFAULT == 0,
 556                     return 0);
 557
 558         buf = ped_malloc (part->disk->dev->sector_size);
 559
 560         if (!buf)
 561                 return 0;
 562
 563         if (!part->fs_type)
 564                 goto end;
 565
 566         found = 0;
 567         for (i = 0; ms_types[i]; i++) {
 568                 if (!strcmp(ms_types[i], part->fs_type->name))
 569                         found = 1;
 570         }
 571         if (!found)
 572                 goto end;
 573
 574         if (!ped_geometry_read(&part->geom, buf, 0, 1))
 575                 goto end;
 576
 577         /* shared by the start of all Microsoft file systems */
 578         sectors = buf[0x18] + (buf[0x19] << 8);
 579         heads = buf[0x1a] + (buf[0x1b] << 8);
 580
 581         if (sectors < 1 || sectors > 63)
 582                 goto end;
 583         if (heads > 255 || heads < 1)
 584                 goto end;
 585
 586         bios_geom->sectors = sectors;
 587         bios_geom->heads = heads;
 588         bios_geom->cylinders = part->disk->dev->length / (sectors * heads);
 589         res = 1;
 590 end:
 591         free(buf);
 592         return res;
 593 }
 594
 595 /* This function attempts to infer the BIOS CHS geometry of the hard disk
 596  * from the CHS + LBA information contained in the partition table from
 597  * a single partition's entry.
 598  *
 599  * This involves some maths.  Let (c,h,s,a) be the starting cylinder,
 600  * starting head, starting sector and LBA start address of the partition.
 601  * Likewise, (C,H,S,A) the end addresses.  Using both of these pieces
 602  * of information, we want to deduce cyl_sectors and head_sectors which
 603  * are the sizes of a single cylinder and a single head, respectively.
 604  *
 605  * The relationships are:
 606  * c*cyl_sectors + h * head_sectors + s = a
 607  * C*cyl_sectors + H * head_sectors + S = A
 608  *
 609  * We can rewrite this in matrix form:
 610  *
 611  * [ c h ] [ cyl_sectors  ]  =  [ s - a ]  =  [ a_ ]
 612  * [ C H ] [ head_sectors ]     [ S - A ]     [ A_ ].
 613  *
 614  * (s - a is abbreviated to a_to simplify the notation.)
 615  *
 616  * This can be abbreviated into augmented matrix form:
 617  *
 618  * [ c h | a_ ]
 619  * [ C H | A_ ].
 620  *
 621  * Solving these equations requires following the row reduction algorithm.  We
 622  * need to be careful about a few things though:
 623  *      - the equations might be linearly dependent, in which case there
 624  *      are many solutions.
 625  *      - the equations might be inconsistent, in which case there
 626  *      are no solutions.  (Inconsistent partition table entry!)
 627  *      - there might be zeros, so we need to be careful about applying
 628  *      the algorithm.  We know, however, that C > 0.
 629  */
 630 static int
 631 probe_partition_for_geom (const PedPartition* part, PedCHSGeometry* bios_geom)
 632 {
 633         DosPartitionData* dos_data;
 634         RawCHS* start_chs;
 635         RawCHS* end_chs;
 636         PedSector c, h, s, a, a_;       /* start */
 637         PedSector C, H, S, A, A_;       /* end */
 638         PedSector dont_overflow, denum;
 639         PedSector cyl_size, head_size;
 640         PedSector cylinders, heads, sectors;
 641
 642         PED_ASSERT (part != NULL, return 0);
 643         PED_ASSERT (part->disk_specific != NULL, return 0);
 644         PED_ASSERT (bios_geom != NULL, return 0);
 645
 646         dos_data = part->disk_specific;
 647
 648         if (!dos_data->orig)
 649                 return 0;
 650
 651         start_chs = &dos_data->orig->raw_part.chs_start;
 652         c = chs_get_cylinder (start_chs);
 653         h = chs_get_head (start_chs);
 654         s = chs_get_sector (start_chs);
 655         a = dos_data->orig->geom.start;
 656         a_ = a - s;
 657
 658         end_chs = &dos_data->orig->raw_part.chs_end;
 659         C = chs_get_cylinder (end_chs);
 660         H = chs_get_head (end_chs);
 661         S = chs_get_sector (end_chs);
 662         A = dos_data->orig->geom.end;
 663         A_ = A - S;
 664
 665         if (h < 0 || H < 0 || h > 254 || H > 254)
 666                 return 0;
 667         if (c > C)
 668                 return 0;
 669
 670         /* If no geometry is feasible, then don't even bother.
 671          * Useful for eliminating assertions for broken partition
 672          * tables generated by Norton Ghost et al.
 673          */
 674         if (A > (C+1) * 255 * 63)
 675                 return 0;
 676
 677         /* Not enough information.  In theory, we can do better.  Should we? */
 678         if (C > MAX_CHS_CYLINDER)
 679                 return 0;
 680         if (C == 0)
 681                 return 0;
 682
 683         /* Calculate the maximum number that can be multiplied by
 684          * any head count without overflowing a PedSector
 685          * 2^8 = 256, 8 bits + 1(sign bit) = 9
 686          */
 687         dont_overflow = 1;
 688         dont_overflow <<= (8*sizeof(dont_overflow)) - 9;
 689         dont_overflow--;
 690
 691         if (a_ > dont_overflow || A_ > dont_overflow)
 692                 return 0;
 693
 694         /* The matrix is solved by :
 695          *
 696          * [ c h | a_]                  R1
 697          * [ C H | A_]                  R2
 698          *
 699          * (cH - Ch) cyl_size = a_H - A_h               H R1 - h R2
 700          * => (if cH - Ch != 0) cyl_size = (a_H - A_h) / (cH - Ch)
 701          *
 702          * (Hc - hC) head_size = A_c - a_C              c R2 - C R1
 703          * => (if cH - Ch != 0) head_size = (A_c - a_C) / (cH - Ch)
 704          *
 705          *   But this calculation of head_size would need
 706          *   not overflowing A_c or a_C
 707          *   So substitution is use instead, to minimize dimension
 708          *   of temporary results :
 709          *
 710          * If h != 0 : head_size = ( a_ - c cyl_size ) / h
 711          * If H != 0 : head_size = ( A_ - C cyl_size ) / H
 712          *
 713          */
 714         denum = c * H - C * h;
 715         if (denum == 0)
 716                 return 0;
 717
 718         cyl_size = (a_*H - A_*h) / denum;
 719         /* Check for non integer result */
 720         if (cyl_size * denum != a_*H - A_*h)
 721                 return 0;
 722
 723         PED_ASSERT (cyl_size > 0, return 0);
 724         PED_ASSERT (cyl_size <= 255 * 63, return 0);
 725
 726         if (h > 0)
 727                 head_size = ( a_ - c * cyl_size ) / h;
 728         else if (H > 0)
 729                 head_size = ( A_ - C * cyl_size ) / H;
 730         else {
 731                 /* should not happen because denum != 0 */
 732                 PED_ASSERT (0, return 0);
 733         }
 734
 735         PED_ASSERT (head_size > 0, return 0);
 736         PED_ASSERT (head_size <= 63, return 0);
 737
 738         cylinders = part->disk->dev->length / cyl_size;
 739         heads = cyl_size / head_size;
 740         sectors = head_size;
 741
 742         PED_ASSERT (heads > 0, return 0);
 743         PED_ASSERT (heads < 256, return 0);
 744
 745         PED_ASSERT (sectors > 0, return 0);
 746         PED_ASSERT (sectors <= 63, return 0);
 747
 748         /* Some broken OEM partitioning program(s) seem to have an out-by-one
 749          * error on the end of partitions.  We should offer to fix the
 750          * partition table...
 751          */
 752         if (((C + 1) * heads + H) * sectors + S == A)
 753                 C++;
 754
 755         PED_ASSERT ((c * heads + h) * sectors + s == a, return 0);
 756         PED_ASSERT ((C * heads + H) * sectors + S == A, return 0);
 757
 758         bios_geom->cylinders = cylinders;
 759         bios_geom->heads = heads;
 760         bios_geom->sectors = sectors;
 761
 762         return 1;
 763 }
 764
 765 static void
 766 partition_probe_bios_geometry (const PedPartition* part,
 767                                PedCHSGeometry* bios_geom)
 768 {
 769         PED_ASSERT (part != NULL, return);
 770         PED_ASSERT (part->disk != NULL, return);
 771         PED_ASSERT (bios_geom != NULL, return);
 772
 773         if (ped_partition_is_active (part)) {
 774                 if (probe_partition_for_geom (part, bios_geom))
 775                         return;
 776                 if (part->type & PED_PARTITION_EXTENDED) {
 777                         if (probe_filesystem_for_geom (part, bios_geom))
 778                                 return;
 779                 }
 780         }
 781         if (part->type & PED_PARTITION_LOGICAL) {
 782                 PedPartition* ext_part;
 783                 ext_part = ped_disk_extended_partition (part->disk);
 784                 PED_ASSERT (ext_part != NULL, return);
 785                 partition_probe_bios_geometry (ext_part, bios_geom);
 786         } else {
 787                 *bios_geom = part->disk->dev->bios_geom;
 788         }
 789 }
 790
 791 static void
 792 disk_probe_bios_geometry (const PedDisk* disk, PedCHSGeometry* bios_geom)
 793 {
 794         PedPartition*   part;
 795
 796         /* first look at the boot partition */
 797         part = NULL;
 798         while ((part = ped_disk_next_partition (disk, part))) {
 799                 if (!ped_partition_is_active (part))
 800                         continue;
 801                 if (ped_partition_get_flag (part, PED_PARTITION_BOOT)) {
 802                         if (probe_filesystem_for_geom (part, bios_geom))
 803                                 return;
 804                         if (probe_partition_for_geom (part, bios_geom))
 805                                 return;
 806                 }
 807         }
 808
 809         /* that didn't work... try all partition table entries */
 810         part = NULL;
 811         while ((part = ped_disk_next_partition (disk, part))) {
 812                 if (ped_partition_is_active (part)) {
 813                         if (probe_partition_for_geom (part, bios_geom))
 814                                 return;
 815                 }
 816         }
 817
 818         /* that didn't work... look at all file systems */
 819         part = NULL;
 820         while ((part = ped_disk_next_partition (disk, part))) {
 821                 if (ped_partition_is_active (part)) {
 822                         if (probe_filesystem_for_geom (part, bios_geom))
 823                                 return;
 824                 }
 825         }
 826 }
 827 #endif /* !DISCOVER_ONLY */
 828
 829 static int
 830 raw_part_is_extended (const DosRawPartition* raw_part)
 831 {
 832         PED_ASSERT (raw_part != NULL, return 0);
 833
 834         switch (raw_part->type) {
 835         case PARTITION_DOS_EXT:
 836         case PARTITION_EXT_LBA:
 837         case PARTITION_LINUX_EXT:
 838                 return 1;
 839
 840         default:
 841                 return 0;
 842         }
 843
 844         return 0;
 845 }
 846
 847 static int
 848 raw_part_is_hidden (const DosRawPartition* raw_part)
 849 {
 850         PED_ASSERT (raw_part != NULL, return 0);
 851
 852         switch (raw_part->type) {
 853         case PARTITION_FAT12_H:
 854         case PARTITION_FAT16_SM_H:
 855         case PARTITION_FAT16_H:
 856         case PARTITION_FAT32_H:
 857         case PARTITION_NTFS_H:
 858         case PARTITION_FAT32_LBA_H:
 859         case PARTITION_FAT16_LBA_H:
 860                 return 1;
 861
 862         default:
 863                 return 0;
 864         }
 865
 866         return 0;
 867 }
 868
 869 static int
 870 raw_part_is_lba (const DosRawPartition* raw_part)
 871 {
 872         PED_ASSERT (raw_part != NULL, return 0);
 873
 874         switch (raw_part->type) {
 875         case PARTITION_FAT32_LBA:
 876         case PARTITION_FAT16_LBA:
 877         case PARTITION_EXT_LBA:
 878         case PARTITION_FAT32_LBA_H:
 879         case PARTITION_FAT16_LBA_H:
 880                 return 1;
 881
 882         default:
 883                 return 0;
 884         }
 885
 886         return 0;
 887 }
 888
 889 static PedPartition*
 890 raw_part_parse (const PedDisk* disk, const DosRawPartition* raw_part,
 891                 PedSector lba_offset, PedPartitionType type)
 892 {
 893         PedPartition* part;
 894         DosPartitionData* dos_data;
 895
 896         PED_ASSERT (disk != NULL, return NULL);
 897         PED_ASSERT (raw_part != NULL, return NULL);
 898
 899         part = ped_partition_new (
 900                 disk, type, NULL,
 901                 linear_start (disk, raw_part, lba_offset),
 902                 linear_end (disk, raw_part, lba_offset));
 903         if (!part)
 904                 return NULL;
 905         dos_data = part->disk_specific;
 906         dos_data->system = raw_part->type;
 907         dos_data->boot = raw_part->boot_ind != 0;
 908         dos_data->diag = raw_part->type == PARTITION_COMPAQ_DIAG ||
 909                          raw_part->type == PARTITION_MSFT_RECOVERY ||
 910                          raw_part->type == PARTITION_DELL_DIAG;
 911         dos_data->hidden = raw_part_is_hidden (raw_part);
 912         dos_data->raid = raw_part->type == PARTITION_LINUX_RAID;
 913         dos_data->lvm = raw_part->type == PARTITION_LINUX_LVM_OLD
 914                         || raw_part->type == PARTITION_LINUX_LVM;
 915         dos_data->lba = raw_part_is_lba (raw_part);
 916         dos_data->palo = raw_part->type == PARTITION_PALO;
 917         dos_data->prep = raw_part->type == PARTITION_PREP;
 918         dos_data->orig = ped_malloc (sizeof (OrigState));
 919         if (!dos_data->orig) {
 920                 ped_partition_destroy (part);
 921                 return NULL;
 922         }
 923         dos_data->orig->geom = part->geom;
 924         dos_data->orig->raw_part = *raw_part;
 925         dos_data->orig->lba_offset = lba_offset;
 926         return part;
 927 }
 928
 929 static int
 930 read_table (PedDisk* disk, PedSector sector, int is_extended_table)
 931 {
 932         int                     i;
 933         DosRawTable*            table;
 934         DosRawPartition*        raw_part;
 935         PedPartition*           part;
 936         PedPartitionType        type;
 937         PedSector               lba_offset;
 938
 939         PED_ASSERT (disk != NULL, return 0);
 940         PED_ASSERT (disk->dev != NULL, return 0);
 941
 942         void *label = NULL;
 943         if (!ptt_read_sector (disk->dev, sector, &label))
 944                 goto error;
 945
 946         table = (DosRawTable *) label;
 947
 948         /* weird: empty extended partitions are filled with 0xf6 by PM */
 949         if (is_extended_table
 950             && PED_LE16_TO_CPU (table->magic) == PARTITION_MAGIC_MAGIC)
 951                 goto read_ok;
 952
 953 #ifndef DISCOVER_ONLY
 954         if (PED_LE16_TO_CPU (table->magic) != MSDOS_MAGIC) {
 955                 if (ped_exception_throw (
 956                         PED_EXCEPTION_ERROR, PED_EXCEPTION_IGNORE_CANCEL,
 957                         _("Invalid partition table on %s "
 958                           "-- wrong signature %x."),
 959                         disk->dev->path,
 960                         PED_LE16_TO_CPU (table->magic))
 961                                 != PED_EXCEPTION_IGNORE)
 962                         goto error;
 963                 goto read_ok;
 964         }
 965 #endif
 966
 967         /* parse the partitions from this table */
 968         for (i = 0; i < DOS_N_PRI_PARTITIONS; i++) {
 969                 raw_part = &table->partitions [i];
 970                 if (raw_part->type == PARTITION_EMPTY || !raw_part->length)
 971                         continue;
 972
 973                 /* process nested extended partitions after normal logical
 974                  * partitions, to make sure we get the order right.
 975                  */
 976                 if (is_extended_table && raw_part_is_extended (raw_part))
 977                         continue;
 978
 979                 lba_offset = is_extended_table ? sector : 0;
 980
 981                 if (linear_start (disk, raw_part, lba_offset) == sector) {
 982                         if (ped_exception_throw (
 983                                 PED_EXCEPTION_ERROR,
 984                                 PED_EXCEPTION_IGNORE_CANCEL,
 985                                 _("Invalid partition table - recursive "
 986                                 "partition on %s."),
 987                                 disk->dev->path)
 988                                         != PED_EXCEPTION_IGNORE)
 989                                 goto error;
 990                         continue;       /* avoid infinite recursion */
 991                 }
 992
 993                 if (is_extended_table)
 994                         type = PED_PARTITION_LOGICAL;
 995                 else if (raw_part_is_extended (raw_part))
 996                         type = PED_PARTITION_EXTENDED;
 997                 else
 998                         type = PED_PARTITION_NORMAL;
 999
1000                 part = raw_part_parse (disk, raw_part, lba_offset, type);
1001                 if (!part)
1002                         goto error;
1003                 if (!is_extended_table)
1004                         part->num = i + 1;
1005                 if (type != PED_PARTITION_EXTENDED)
1006                         part->fs_type = ped_file_system_probe (&part->geom);
1007
1008                 PedConstraint *constraint_exact
1009                   = ped_constraint_exact (&part->geom);
1010                 bool ok = ped_disk_add_partition (disk, part, constraint_exact);
1011                 ped_constraint_destroy (constraint_exact);
1012                 if (!ok)
1013                         goto error;
1014
1015                 /* non-nested extended partition */
1016                 if (part->type == PED_PARTITION_EXTENDED) {
1017                         if (!read_table (disk, part->geom.start, 1))
1018                                 goto error;
1019                 }
1020         }
1021
1022         if (is_extended_table) {
1023                 /* process the nested extended partitions */
1024                 for (i = 0; i < DOS_N_PRI_PARTITIONS; i++) {
1025                         PedSector part_start;
1026
1027                         raw_part = &table->partitions [i];
1028                         if (!raw_part_is_extended (raw_part))
1029                                 continue;
1030
1031                         lba_offset = ped_disk_extended_partition
1032                                         (disk)->geom.start;
1033                         part_start = linear_start (disk, raw_part, lba_offset);
1034                         if (part_start == sector) {
1035                                 /* recursive table - already threw an
1036                                  * exception above.
1037                                  */
1038                                 continue;
1039                         }
1040                         if (!read_table (disk, part_start, 1))
1041                                 goto error;
1042                 }
1043         }
1044
1045 read_ok:
1046         free (label);
1047         return 1;
1048
1049 error:
1050         free (label);
1051         ped_disk_delete_all (disk);
1052         return 0;
1053 }
1054
1055 static int
1056 msdos_read (PedDisk* disk)
1057 {
1058         PED_ASSERT (disk != NULL, return 0);
1059         PED_ASSERT (disk->dev != NULL, return 0);
1060
1061         ped_disk_delete_all (disk);
1062         if (!read_table (disk, 0, 0))
1063                 return 0;
1064
1065 #ifndef DISCOVER_ONLY
1066         /* try to figure out the correct BIOS CHS values */
1067         if (!disk_check_bios_geometry (disk, &disk->dev->bios_geom)) {
1068                 PedCHSGeometry bios_geom = disk->dev->bios_geom;
1069                 disk_probe_bios_geometry (disk, &bios_geom);
1070
1071                 /* if the geometry was wrong, then we should reread, to
1072                  * make sure the metadata is allocated in the right places.
1073                  */
1074                 if (disk->dev->bios_geom.cylinders != bios_geom.cylinders
1075                     || disk->dev->bios_geom.heads != bios_geom.heads
1076                     || disk->dev->bios_geom.sectors != bios_geom.sectors) {
1077                         disk->dev->bios_geom = bios_geom;
1078                         return msdos_read (disk);
1079                 }
1080         }
1081 #endif
1082
1083         return 1;
1084 }
1085
1086 #ifndef DISCOVER_ONLY
1087 static int
1088 fill_raw_part (DosRawPartition* raw_part,
1089                const PedPartition* part, PedSector offset)
1090 {
1091         DosPartitionData*       dos_data;
1092         PedCHSGeometry          bios_geom;
1093
1094         PED_ASSERT (raw_part != NULL, return 0);
1095         PED_ASSERT (part != NULL, return 0);
1096
1097         partition_probe_bios_geometry (part, &bios_geom);
1098
1099         dos_data = part->disk_specific;
1100
1101         raw_part->boot_ind = 0x80 * dos_data->boot;
1102         raw_part->type = dos_data->system;
1103         raw_part->start = PED_CPU_TO_LE32 (part->geom.start - offset);
1104         raw_part->length = PED_CPU_TO_LE32 (part->geom.length);
1105
1106         sector_to_chs (part->disk->dev, &bios_geom, part->geom.start,
1107                        &raw_part->chs_start);
1108         sector_to_chs (part->disk->dev, &bios_geom, part->geom.end,
1109                        &raw_part->chs_end);
1110
1111         if (dos_data->orig) {
1112                 DosRawPartition* orig_raw_part = &dos_data->orig->raw_part;
1113                 if (dos_data->orig->geom.start == part->geom.start)
1114                         raw_part->chs_start = orig_raw_part->chs_start;
1115                 if (dos_data->orig->geom.end == part->geom.end)
1116                         raw_part->chs_end = orig_raw_part->chs_end;
1117         }
1118
1119         return 1;
1120 }
1121
1122 static int
1123 fill_ext_raw_part_geom (DosRawPartition* raw_part,
1124                         const PedCHSGeometry* bios_geom,
1125                         const PedGeometry* geom, PedSector offset)
1126 {
1127         PED_ASSERT (raw_part != NULL, return 0);
1128         PED_ASSERT (geom != NULL, return 0);
1129         PED_ASSERT (geom->dev != NULL, return 0);
1130
1131         raw_part->boot_ind = 0;
1132         raw_part->type = PARTITION_DOS_EXT;
1133         raw_part->start = PED_CPU_TO_LE32 (geom->start - offset);
1134         raw_part->length = PED_CPU_TO_LE32 (geom->length);
1135
1136         sector_to_chs (geom->dev, bios_geom, geom->start, &raw_part->chs_start);
1137         sector_to_chs (geom->dev, bios_geom, geom->start + geom->length - 1,
1138                        &raw_part->chs_end);
1139
1140         return 1;
1141 }
1142
1143 static int
1144 write_ext_table (const PedDisk* disk,
1145                  PedSector sector, const PedPartition* logical)
1146 {
1147         PedPartition*           part;
1148         PedSector               lba_offset;
1149
1150         PED_ASSERT (disk != NULL, return 0);
1151         PED_ASSERT (ped_disk_extended_partition (disk) != NULL, return 0);
1152         PED_ASSERT (logical != NULL, return 0);
1153
1154         lba_offset = ped_disk_extended_partition (disk)->geom.start;
1155
1156         void* s;
1157         if (!ptt_read_sector (disk->dev, sector, &s))
1158                 return 0;
1159
1160         DosRawTable *table = s;
1161         memset(&(table->partitions), 0, sizeof (table->partitions));
1162         table->magic = PED_CPU_TO_LE16 (MSDOS_MAGIC);
1163
1164         int ok = 0;
1165         if (!fill_raw_part (&table->partitions[0], logical, sector))
1166                 goto cleanup;
1167
1168         part = ped_disk_get_partition (disk, logical->num + 1);
1169         if (part) {
1170                 PedGeometry*            geom;
1171                 PedCHSGeometry          bios_geom;
1172
1173                 geom = ped_geometry_new (disk->dev, part->prev->geom.start,
1174                                 part->geom.end - part->prev->geom.start + 1);
1175                 if (!geom)
1176                         goto cleanup;
1177                 partition_probe_bios_geometry (part, &bios_geom);
1178                 fill_ext_raw_part_geom (&table->partitions[1], &bios_geom,
1179                                         geom, lba_offset);
1180                 ped_geometry_destroy (geom);
1181
1182                 if (!write_ext_table (disk, part->prev->geom.start, part))
1183                         goto cleanup;
1184         }
1185
1186         ok = ped_device_write (disk->dev, table, sector, 1);
1187  cleanup:
1188         free (s);
1189         return ok;
1190 }
1191
1192 static int
1193 write_empty_table (const PedDisk* disk, PedSector sector)
1194 {
1195         DosRawTable             table;
1196         void*                   table_sector;
1197
1198         PED_ASSERT (disk != NULL, return 0);
1199
1200         if (ptt_read_sector (disk->dev, sector, &table_sector)) {
1201                 memcpy (&table, table_sector, sizeof (table));
1202                 free(table_sector);
1203         }
1204         memset (&(table.partitions), 0, sizeof (table.partitions));
1205         table.magic = PED_CPU_TO_LE16 (MSDOS_MAGIC);
1206
1207         return ped_device_write (disk->dev, (void*) &table, sector, 1);
1208 }
1209
1210 /* Find the first logical partition, and write the partition table for it.
1211  */
1212 static int
1213 write_extended_partitions (const PedDisk* disk)
1214 {
1215         PedPartition*           ext_part;
1216         PedPartition*           part;
1217         PedCHSGeometry          bios_geom;
1218
1219         PED_ASSERT (disk != NULL, return 0);
1220
1221         ext_part = ped_disk_extended_partition (disk);
1222         partition_probe_bios_geometry (ext_part, &bios_geom);
1223         part = ped_disk_get_partition (disk, 5);
1224         if (part)
1225                 return write_ext_table (disk, ext_part->geom.start, part);
1226         else
1227                 return write_empty_table (disk, ext_part->geom.start);
1228 }
1229
1230 static inline uint32_t generate_random_id (void)
1231 {
1232         struct timeval tv;
1233         int rc;
1234         rc = gettimeofday(&tv, NULL);
1235         if (rc == -1)
1236                 return 0;
1237         return (uint32_t)(tv.tv_usec & 0xFFFFFFFFUL);
1238 }
1239
1240 static int
1241 msdos_write (const PedDisk* disk)
1242 {
1243         PedPartition*           part;
1244         int                     i;
1245
1246         PED_ASSERT (disk != NULL, return 0);
1247         PED_ASSERT (disk->dev != NULL, return 0);
1248
1249         void *s0;
1250         if (!ptt_read_sector (disk->dev, 0, &s0))
1251                 return 0;
1252         DosRawTable *table = (DosRawTable *) s0;
1253
1254         if (!table->boot_code[0]) {
1255                 memset (table->boot_code, 0, 512);
1256                 memcpy (table->boot_code, MBR_BOOT_CODE, sizeof (MBR_BOOT_CODE));
1257         }
1258
1259         /* If there is no unique identifier, generate a random one */
1260         if (!table->mbr_signature)
1261                 table->mbr_signature = generate_random_id();
1262
1263         memset (table->partitions, 0, sizeof (table->partitions));
1264         table->magic = PED_CPU_TO_LE16 (MSDOS_MAGIC);
1265
1266         for (i=1; i<=DOS_N_PRI_PARTITIONS; i++) {
1267                 part = ped_disk_get_partition (disk, i);
1268                 if (!part)
1269                         continue;
1270
1271                 if (!fill_raw_part (&table->partitions [i - 1], part, 0))
1272                         goto write_fail;
1273
1274                 if (part->type == PED_PARTITION_EXTENDED) {
1275                         if (!write_extended_partitions (disk))
1276                                 goto write_fail;
1277                 }
1278         }
1279
1280         int write_ok = ped_device_write (disk->dev, (void*) table, 0, 1);
1281         free (s0);
1282         if (!write_ok)
1283                 return 0;
1284         return ped_device_sync (disk->dev);
1285
1286  write_fail:
1287         free (s0);
1288         return 0;
1289
1290 }
1291 #endif /* !DISCOVER_ONLY */
1292
1293 static PedPartition*
1294 msdos_partition_new (const PedDisk* disk, PedPartitionType part_type,
1295                      const PedFileSystemType* fs_type,
1296                      PedSector start, PedSector end)
1297 {
1298         PedPartition*           part;
1299         DosPartitionData*       dos_data;
1300
1301         part = _ped_partition_alloc (disk, part_type, fs_type, start, end);
1302         if (!part)
1303                 goto error;
1304
1305         if (ped_partition_is_active (part)) {
1306                 part->disk_specific
1307                         = dos_data = ped_malloc (sizeof (DosPartitionData));
1308                 if (!dos_data)
1309                         goto error_free_part;
1310                 dos_data->orig = NULL;
1311                 dos_data->system = PARTITION_LINUX;
1312                 dos_data->hidden = 0;
1313                 dos_data->boot = 0;
1314                 dos_data->diag = 0;
1315                 dos_data->raid = 0;
1316                 dos_data->lvm = 0;
1317                 dos_data->lba = 0;
1318                 dos_data->palo = 0;
1319                 dos_data->prep = 0;
1320         } else {
1321                 part->disk_specific = NULL;
1322         }
1323         return part;
1324
1325 error_free_part:
1326         free (part);
1327 error:
1328         return 0;
1329 }
1330
1331 static PedPartition*
1332 msdos_partition_duplicate (const PedPartition* part)
1333 {
1334         PedPartition*           new_part;
1335         DosPartitionData*       new_dos_data;
1336         DosPartitionData*       old_dos_data;
1337
1338         new_part = ped_partition_new (part->disk, part->type, part->fs_type,
1339                                       part->geom.start, part->geom.end);
1340         if (!new_part)
1341                 return NULL;
1342         new_part->num = part->num;
1343
1344         old_dos_data = (DosPartitionData*) part->disk_specific;
1345         new_dos_data = (DosPartitionData*) new_part->disk_specific;
1346         new_dos_data->system = old_dos_data->system;
1347         new_dos_data->boot = old_dos_data->boot;
1348         new_dos_data->diag = old_dos_data->diag;
1349         new_dos_data->hidden = old_dos_data->hidden;
1350         new_dos_data->raid = old_dos_data->raid;
1351         new_dos_data->lvm = old_dos_data->lvm;
1352         new_dos_data->lba = old_dos_data->lba;
1353         new_dos_data->palo = old_dos_data->palo;
1354         new_dos_data->prep = old_dos_data->prep;
1355
1356         if (old_dos_data->orig) {
1357                 new_dos_data->orig = ped_malloc (sizeof (OrigState));
1358                 if (!new_dos_data->orig) {
1359                         ped_partition_destroy (new_part);
1360                         return NULL;
1361                 }
1362                 new_dos_data->orig->geom = old_dos_data->orig->geom;
1363                 new_dos_data->orig->raw_part = old_dos_data->orig->raw_part;
1364                 new_dos_data->orig->lba_offset = old_dos_data->orig->lba_offset;
1365         }
1366         return new_part;
1367 }
1368
1369 static void
1370 msdos_partition_destroy (PedPartition* part)
1371 {
1372         PED_ASSERT (part != NULL, return);
1373
1374         if (ped_partition_is_active (part)) {
1375                 DosPartitionData* dos_data;
1376                 dos_data = (DosPartitionData*) part->disk_specific;
1377                 free (dos_data->orig);
1378                 free (part->disk_specific);
1379         }
1380         free (part);
1381 }
1382
1383 static int
1384 msdos_partition_set_system (PedPartition* part,
1385                             const PedFileSystemType* fs_type)
1386 {
1387         DosPartitionData* dos_data = part->disk_specific;
1388
1389         part->fs_type = fs_type;
1390
1391         if (dos_data->hidden
1392                     && fs_type
1393                     && strncmp (fs_type->name, "fat", 3) != 0
1394                     && strcmp (fs_type->name, "ntfs") != 0)
1395                 dos_data->hidden = 0;
1396
1397         if (part->type & PED_PARTITION_EXTENDED) {
1398                 dos_data->diag = 0;
1399                 dos_data->raid = 0;
1400                 dos_data->lvm = 0;
1401                 dos_data->palo = 0;
1402                 dos_data->prep = 0;
1403                 if (dos_data->lba)
1404                         dos_data->system = PARTITION_EXT_LBA;
1405                 else
1406                         dos_data->system = PARTITION_DOS_EXT;
1407                 return 1;
1408         }
1409
1410         if (dos_data->diag) {
1411                 /* Don't change the system if it already is a diag type,
1412                    otherwise use Compaq as almost all vendors use that. */
1413                 if (dos_data->system != PARTITION_COMPAQ_DIAG &&
1414                     dos_data->system != PARTITION_MSFT_RECOVERY &&
1415                     dos_data->system != PARTITION_DELL_DIAG)
1416                         dos_data->system = PARTITION_COMPAQ_DIAG;
1417                 return 1;
1418         }
1419         if (dos_data->lvm) {
1420                 dos_data->system = PARTITION_LINUX_LVM;
1421                 return 1;
1422         }
1423         if (dos_data->raid) {
1424                 dos_data->system = PARTITION_LINUX_RAID;
1425                 return 1;
1426         }
1427         if (dos_data->palo) {
1428                 dos_data->system = PARTITION_PALO;
1429                 return 1;
1430         }
1431         if (dos_data->prep) {
1432                 dos_data->system = PARTITION_PREP;
1433                 return 1;
1434         }
1435
1436         if (!fs_type)
1437                 dos_data->system = PARTITION_LINUX;
1438         else if (!strcmp (fs_type->name, "fat16")) {
1439                 dos_data->system = dos_data->lba
1440                                    ? PARTITION_FAT16_LBA : PARTITION_FAT16;
1441                 dos_data->system |= dos_data->hidden ? PART_FLAG_HIDDEN : 0;
1442         } else if (!strcmp (fs_type->name, "fat32")) {
1443                 dos_data->system = dos_data->lba
1444                                    ? PARTITION_FAT32_LBA : PARTITION_FAT32;
1445                 dos_data->system |= dos_data->hidden ? PART_FLAG_HIDDEN : 0;
1446         } else if (!strcmp (fs_type->name, "ntfs")
1447                    || !strcmp (fs_type->name, "hpfs")) {
1448                 dos_data->system = PARTITION_NTFS;
1449                 dos_data->system |= dos_data->hidden ? PART_FLAG_HIDDEN : 0;
1450         } else if (!strcmp (fs_type->name, "hfs")
1451                    || !strcmp (fs_type->name, "hfs+"))
1452                 dos_data->system = PARTITION_HFS;
1453         else if (!strcmp (fs_type->name, "sun-ufs"))
1454                 dos_data->system = PARTITION_SUN_UFS;
1455         else if (is_linux_swap (fs_type->name))
1456                 dos_data->system = PARTITION_LINUX_SWAP;
1457         else
1458                 dos_data->system = PARTITION_LINUX;
1459
1460         return 1;
1461 }
1462
1463 static void
1464 clear_flags (DosPartitionData *dos_data)
1465 {
1466   dos_data->diag = 0;
1467   dos_data->hidden = 0;
1468   dos_data->lvm = 0;
1469   dos_data->palo = 0;
1470   dos_data->prep = 0;
1471   dos_data->raid = 0;
1472 }
1473
1474 static int
1475 msdos_partition_set_flag (PedPartition* part,
1476                           PedPartitionFlag flag, int state)
1477 {
1478         PedDisk*                        disk;
1479         PedPartition*                   walk;
1480         DosPartitionData*               dos_data;
1481
1482         PED_ASSERT (part != NULL, return 0);
1483         PED_ASSERT (part->disk_specific != NULL, return 0);
1484         PED_ASSERT (part->disk != NULL, return 0);
1485
1486         dos_data = part->disk_specific;
1487         disk = part->disk;
1488
1489         switch (flag) {
1490         case PED_PARTITION_HIDDEN:
1491                 if (part->type == PED_PARTITION_EXTENDED) {
1492                         ped_exception_throw (
1493                                 PED_EXCEPTION_ERROR,
1494                                 PED_EXCEPTION_CANCEL,
1495                                 _("Extended partitions cannot be hidden on "
1496                                   "msdos disk labels."));
1497                         return 0;
1498                 }
1499                 dos_data->hidden = state;
1500                 return ped_partition_set_system (part, part->fs_type);
1501
1502         case PED_PARTITION_BOOT:
1503                 dos_data->boot = state;
1504                 if (!state)
1505                         return 1;
1506
1507                 walk = ped_disk_next_partition (disk, NULL);
1508                 for (; walk; walk = ped_disk_next_partition (disk, walk)) {
1509                         if (walk == part || !ped_partition_is_active (walk))
1510                                 continue;
1511                         msdos_partition_set_flag (walk, PED_PARTITION_BOOT, 0);
1512                 }
1513                 return 1;
1514
1515         case PED_PARTITION_DIAG:
1516                 if (state)
1517                         clear_flags (dos_data);
1518                 dos_data->diag = state;
1519                 return ped_partition_set_system (part, part->fs_type);
1520
1521         case PED_PARTITION_RAID:
1522                 if (state)
1523                         clear_flags (dos_data);
1524                 dos_data->raid = state;
1525                 return ped_partition_set_system (part, part->fs_type);
1526
1527         case PED_PARTITION_LVM:
1528                 if (state)
1529                         clear_flags (dos_data);
1530                 dos_data->lvm = state;
1531                 return ped_partition_set_system (part, part->fs_type);
1532
1533         case PED_PARTITION_LBA:
1534                 dos_data->lba = state;
1535                 return ped_partition_set_system (part, part->fs_type);
1536
1537         case PED_PARTITION_PALO:
1538                 if (state)
1539                         clear_flags (dos_data);
1540                 dos_data->palo = state;
1541                 return ped_partition_set_system (part, part->fs_type);
1542
1543         case PED_PARTITION_PREP:
1544                 if (state)
1545                         clear_flags (dos_data);
1546                 dos_data->prep = state;
1547                 return ped_partition_set_system (part, part->fs_type);
1548
1549         default:
1550                 return 0;
1551         }
1552 }
1553
1554 static int
1555 msdos_partition_get_flag (const PedPartition* part, PedPartitionFlag flag)
1556 {
1557         DosPartitionData*       dos_data;
1558
1559         PED_ASSERT (part != NULL, return 0);
1560         PED_ASSERT (part->disk_specific != NULL, return 0);
1561
1562         dos_data = part->disk_specific;
1563         switch (flag) {
1564         case PED_PARTITION_HIDDEN:
1565                 if (part->type == PED_PARTITION_EXTENDED)
1566                         return 0;
1567                 else
1568                         return dos_data->hidden;
1569
1570         case PED_PARTITION_BOOT:
1571                 return dos_data->boot;
1572
1573         case PED_PARTITION_DIAG:
1574                 return dos_data->diag;
1575
1576         case PED_PARTITION_RAID:
1577                 return dos_data->raid;
1578
1579         case PED_PARTITION_LVM:
1580                 return dos_data->lvm;
1581
1582         case PED_PARTITION_LBA:
1583                 return dos_data->lba;
1584
1585         case PED_PARTITION_PALO:
1586                 return dos_data->palo;
1587
1588         case PED_PARTITION_PREP:
1589                 return dos_data->prep;
1590
1591         default:
1592                 return 0;
1593         }
1594 }
1595
1596 static int
1597 msdos_partition_is_flag_available (const PedPartition* part,
1598                                    PedPartitionFlag flag)
1599 {
1600         switch (flag) {
1601         case PED_PARTITION_HIDDEN:
1602                 if (part->type == PED_PARTITION_EXTENDED)
1603                         return 0;
1604                 else
1605                         return 1;
1606
1607         case PED_PARTITION_BOOT:
1608         case PED_PARTITION_RAID:
1609         case PED_PARTITION_LVM:
1610         case PED_PARTITION_LBA:
1611         case PED_PARTITION_PALO:
1612         case PED_PARTITION_PREP:
1613         case PED_PARTITION_DIAG:
1614                 return 1;
1615
1616         default:
1617                 return 0;
1618         }
1619 }
1620
1621 static PedGeometry*
1622 _try_constraint (const PedPartition* part, const PedConstraint* external,
1623                  PedConstraint* internal)
1624 {
1625         PedConstraint*          intersection;
1626         PedGeometry*            solution;
1627
1628         intersection = ped_constraint_intersect (external, internal);
1629         ped_constraint_destroy (internal);
1630         if (!intersection)
1631                 return NULL;
1632
1633         solution = ped_constraint_solve_nearest (intersection, &part->geom);
1634         ped_constraint_destroy (intersection);
1635         return solution;
1636 }
1637
1638 static PedGeometry*
1639 _best_solution (const PedPartition* part, const PedCHSGeometry* bios_geom,
1640                 PedGeometry* a, PedGeometry* b)
1641 {
1642         PedSector       cyl_size = bios_geom->heads * bios_geom->sectors;
1643         int             a_cylinder;
1644         int             b_cylinder;
1645
1646         if (!a)
1647                 return b;
1648         if (!b)
1649                 return a;
1650
1651         a_cylinder = a->start / cyl_size;
1652         b_cylinder = b->start / cyl_size;
1653
1654         if (a_cylinder == b_cylinder) {
1655                 if ( (a->start / bios_geom->sectors) % bios_geom->heads
1656                           < (b->start / bios_geom->sectors) % bios_geom->heads)
1657                         goto choose_a;
1658                 else
1659                         goto choose_b;
1660         } else {
1661                 PedSector       a_delta;
1662                 PedSector       b_delta;
1663
1664                 a_delta = abs (part->geom.start - a->start);
1665                 b_delta = abs (part->geom.start - b->start);
1666
1667                 if (a_delta < b_delta)
1668                         goto choose_a;
1669                 else
1670                         goto choose_b;
1671         }
1672
1673         return NULL;    /* never get here! */
1674
1675 choose_a:
1676         ped_geometry_destroy (b);
1677         return a;
1678
1679 choose_b:
1680         ped_geometry_destroy (a);
1681         return b;
1682 }
1683
1684 /* This constraint is for "normal" primary partitions, that start at the
1685  * beginning of a cylinder, and end at the end of a cylinder.
1686  *      Note: you can't start a partition at the beginning of the 1st
1687  * cylinder, because that's where the partition table is!  There are different
1688  * rules for that - see the _primary_start_constraint.
1689  */
1690 static PedConstraint*
1691 _primary_constraint (const PedDisk* disk, const PedCHSGeometry* bios_geom,
1692                      PedGeometry* min_geom)
1693 {
1694         PedDevice*      dev = disk->dev;
1695         PedSector       cylinder_size = bios_geom->sectors * bios_geom->heads;
1696         PedAlignment    start_align;
1697         PedAlignment    end_align;
1698         PedGeometry     start_geom;
1699         PedGeometry     end_geom;
1700
1701         if (!ped_alignment_init (&start_align, 0, cylinder_size))
1702                 return NULL;
1703         if (!ped_alignment_init (&end_align, -1, cylinder_size))
1704                 return NULL;
1705
1706         if (min_geom) {
1707                 if (min_geom->start < cylinder_size)
1708                         return NULL;
1709                 if (!ped_geometry_init (&start_geom, dev, cylinder_size,
1710                                         min_geom->start + 1 - cylinder_size))
1711                         return NULL;
1712                 if (!ped_geometry_init (&end_geom, dev, min_geom->end,
1713                                         dev->length - min_geom->end))
1714                         return NULL;
1715         } else {
1716                 /* Use cylinder_size as the starting sector number
1717                    when the device is large enough to accommodate that.
1718                    Otherwise, use sector 1.  */
1719                 PedSector start = (cylinder_size < dev->length
1720                                    ? cylinder_size : 1);
1721                 if (!ped_geometry_init (&start_geom, dev, start,
1722                                         dev->length - start))
1723                         return NULL;
1724                 if (!ped_geometry_init (&end_geom, dev, 0, dev->length))
1725                         return NULL;
1726         }
1727
1728         return ped_constraint_new (&start_align, &end_align, &start_geom,
1729                                    &end_geom, 1, dev->length);
1730 }
1731
1732 /* This constraint is for partitions starting on the first cylinder.  They
1733  * must start on the 2nd head of the 1st cylinder.
1734  *
1735  * NOTE: We don't always start on the 2nd head of the 1st cylinder.  Windows
1736  * Vista aligns starting partitions at sector 2048 (0x800) by default.  See:
1737  * http://support.microsoft.com/kb/923332
1738  */
1739 static PedConstraint*
1740 _primary_start_constraint (const PedDisk* disk,
1741                            const PedPartition *part,
1742                            const PedCHSGeometry* bios_geom,
1743                            const PedGeometry* min_geom)
1744 {
1745         PedDevice*      dev = disk->dev;
1746         PedSector       cylinder_size = bios_geom->sectors * bios_geom->heads;
1747         PedAlignment    start_align;
1748         PedAlignment    end_align;
1749         PedGeometry     start_geom;
1750         PedGeometry     end_geom;
1751         PedSector start_pos;
1752
1753         if (part->geom.start == 2048)
1754                 /* check for known Windows Vista (NTFS >= 3.1) alignments */
1755                 /* sector 0x800 == 2048                                   */
1756                 start_pos = 2048;
1757         else
1758                 /* all other primary partitions on a DOS label align to   */
1759                 /* the 2nd head of the first cylinder (0x3F == 63)        */
1760                 start_pos = bios_geom->sectors;
1761
1762         if (!ped_alignment_init (&start_align, start_pos, 0))
1763                 return NULL;
1764         if (!ped_alignment_init (&end_align, -1, cylinder_size))
1765                 return NULL;
1766         if (min_geom) {
1767                 if (!ped_geometry_init (&start_geom, dev, start_pos, 1))
1768                         return NULL;
1769                 if (!ped_geometry_init (&end_geom, dev, min_geom->end,
1770                                         dev->length - min_geom->end))
1771                         return NULL;
1772         } else {
1773                 if (!ped_geometry_init (&start_geom, dev, start_pos,
1774                         dev->length - start_pos))
1775                         return NULL;
1776                 if (!ped_geometry_init (&end_geom, dev, 0, dev->length))
1777                         return NULL;
1778         }
1779
1780         return ped_constraint_new (&start_align, &end_align, &start_geom,
1781                                    &end_geom, 1, dev->length);
1782 }
1783
1784 /* constraints for logical partitions:
1785  *      - start_offset is the offset in the start alignment.  "normally",
1786  * this is bios_geom->sectors.  exceptions: MINOR > 5 at the beginning of the
1787  * extended partition, or MINOR == 5 in the middle of the extended partition
1788  *      - is_start_part == 1 if the constraint is for the first cylinder of
1789  * the extended partition, or == 0 if the constraint is for the second cylinder
1790  * onwards of the extended partition.
1791  */
1792 static PedConstraint*
1793 _logical_constraint (const PedDisk* disk, const PedCHSGeometry* bios_geom,
1794                      PedSector start_offset, int is_start_part)
1795 {
1796         PedPartition*   ext_part = ped_disk_extended_partition (disk);
1797         PedDevice*      dev = disk->dev;
1798         PedSector       cylinder_size = bios_geom->sectors * bios_geom->heads;
1799         PedAlignment    start_align;
1800         PedAlignment    end_align;
1801         PedGeometry     max_geom;
1802
1803         PED_ASSERT (ext_part != NULL, return NULL);
1804
1805         if (!ped_alignment_init (&start_align, start_offset, cylinder_size))
1806                 return NULL;
1807         if (!ped_alignment_init (&end_align, -1, cylinder_size))
1808                 return NULL;
1809         if (is_start_part) {
1810                 if (!ped_geometry_init (&max_geom, dev,
1811                                         ext_part->geom.start,
1812                                         ext_part->geom.length))
1813                         return NULL;
1814         } else {
1815                 PedSector       min_start;
1816                 PedSector       max_length;
1817
1818                 min_start = ped_round_up_to (ext_part->geom.start + 1,
1819                                              cylinder_size);
1820                 max_length = ext_part->geom.end - min_start + 1;
1821                 if (min_start >= ext_part->geom.end)
1822                         return NULL;
1823
1824                 if (!ped_geometry_init (&max_geom, dev, min_start, max_length))
1825                         return NULL;
1826         }
1827
1828         return ped_constraint_new (&start_align, &end_align, &max_geom,
1829                                    &max_geom, 1, dev->length);
1830 }
1831
1832 /* returns the minimum geometry for the extended partition, given that the
1833  * extended partition must contain:
1834  *   * all logical partitions
1835  *   * all partition tables for all logical partitions (except the first)
1836  *   * the extended partition table
1837  */
1838 static PedGeometry*
1839 _get_min_extended_part_geom (const PedPartition* ext_part,
1840                              const PedCHSGeometry* bios_geom)
1841 {
1842         PedDisk*                disk = ext_part->disk;
1843         PedSector               head_size = bios_geom ? bios_geom->sectors : 1;
1844         PedPartition*           walk;
1845         PedGeometry*            min_geom;
1846
1847         walk = ped_disk_get_partition (disk, 5);
1848         if (!walk)
1849                 return NULL;
1850
1851         min_geom = ped_geometry_duplicate (&walk->geom);
1852         if (!min_geom)
1853                 return NULL;
1854         /* We must always allow at least two sectors at the start, to leave
1855          * room for LILO.  See linux/fs/partitions/msdos.c.
1856          */
1857         ped_geometry_set_start (min_geom,
1858                                 walk->geom.start - PED_MAX (1 * head_size, 2));
1859
1860         for (walk = ext_part->part_list; walk; walk = walk->next) {
1861                 if (!ped_partition_is_active (walk) || walk->num == 5)
1862                         continue;
1863                 if (walk->geom.start < min_geom->start)
1864                         ped_geometry_set_start (min_geom,
1865                                         walk->geom.start - 2 * head_size);
1866                 if (walk->geom.end > min_geom->end)
1867                         ped_geometry_set_end (min_geom, walk->geom.end);
1868         }
1869
1870         return min_geom;
1871 }
1872
1873 static int
1874 _align_primary (PedPartition* part, const PedCHSGeometry* bios_geom,
1875                 const PedConstraint* constraint)
1876 {
1877         PedDisk*        disk = part->disk;
1878         PedGeometry*    min_geom = NULL;
1879         PedGeometry*    solution = NULL;
1880
1881         if (part->type == PED_PARTITION_EXTENDED)
1882                 min_geom = _get_min_extended_part_geom (part, bios_geom);
1883
1884         solution = _best_solution (part, bios_geom, solution,
1885                         _try_constraint (part, constraint,
1886                                          _primary_start_constraint (disk, part,
1887                                                  bios_geom, min_geom)));
1888
1889         solution = _best_solution (part, bios_geom, solution,
1890                         _try_constraint (part, constraint,
1891                                 _primary_constraint (disk, bios_geom,
1892                                 min_geom)));
1893
1894         if (min_geom)
1895                 ped_geometry_destroy (min_geom);
1896
1897         if (solution) {
1898                 ped_geometry_set (&part->geom, solution->start,
1899                                   solution->length);
1900                 ped_geometry_destroy (solution);
1901                 return 1;
1902         }
1903
1904         return 0;
1905 }
1906
1907 static int
1908 _logical_min_start_head (const PedPartition* part,
1909                          const PedCHSGeometry* bios_geom,
1910                          const PedPartition* ext_part,
1911                          int is_start_ext_part)
1912 {
1913         PedSector       cylinder_size = bios_geom->sectors * bios_geom->heads;
1914         PedSector       base_head;
1915
1916         if (is_start_ext_part)
1917                 base_head = 1 + (ext_part->geom.start % cylinder_size)
1918                                         / bios_geom->sectors;
1919         else
1920                 base_head = 0;
1921
1922         if (part->num == 5)
1923                 return base_head + 0;
1924         else
1925                 return base_head + 1;
1926 }
1927
1928 /* Shamelessly copied and adapted from _partition_get_overlap_constraint
1929  * (in disk.c)
1930  * This should get rid of the infamous Assertion (metadata_length > 0) failed
1931  * bug for extended msdos disklabels generated by Parted.
1932  * 1) There always is a partition table at the start of ext_part, so we leave
1933  *    a one sector gap there.
1934  * 2)*The partition table of part5 is always at the beginning of the ext_part
1935  *    so there is no need to leave a one sector gap before part5.
1936  *   *There always is a partition table at the beginning of each partition != 5.
1937  * We don't need to worry to much about consistency with
1938  * _partition_get_overlap_constraint because missing it means we are in edge
1939  * cases anyway, and we don't lose anything by just refusing to do the job in
1940  * those cases.
1941  */
1942 static PedConstraint*
1943 _log_meta_overlap_constraint (PedPartition* part, const PedGeometry* geom)
1944 {
1945         PedGeometry     safe_space;
1946         PedSector       min_start;
1947         PedSector       max_end;
1948         PedPartition*   ext_part = ped_disk_extended_partition (part->disk);
1949         PedPartition*   walk;
1950         int             not_5 = (part->num != 5);
1951
1952         PED_ASSERT (ext_part != NULL, return NULL);
1953
1954         walk = ext_part->part_list;
1955
1956         /*                                 1)  2)     */
1957         min_start = ext_part->geom.start + 1 + not_5;
1958         max_end = ext_part->geom.end;
1959
1960         while (walk != NULL             /*      2)                         2) */
1961                 && (   walk->geom.start - (walk->num != 5) < geom->start - not_5
1962                     || walk->geom.start - (walk->num != 5) <= min_start )) {
1963                 if (walk != part && ped_partition_is_active (walk))
1964                         min_start = walk->geom.end + 1 + not_5; /* 2) */
1965                 walk = walk->next;
1966         }
1967
1968         while (walk && (walk == part || !ped_partition_is_active (walk)))
1969                 walk = walk->next;
1970
1971         if (walk)
1972                 max_end = walk->geom.start - 1 - (walk->num != 5); /* 2) */
1973
1974         if (min_start >= max_end)
1975                 return NULL;
1976
1977         ped_geometry_init (&safe_space, part->disk->dev,
1978                            min_start, max_end - min_start + 1);
1979         return ped_constraint_new_from_max (&safe_space);
1980 }
1981
1982 static int
1983 _align_logical (PedPartition* part, const PedCHSGeometry* bios_geom,
1984                 const PedConstraint* constraint)
1985 {
1986         PedDisk*        disk = part->disk;
1987         PedPartition*   ext_part = ped_disk_extended_partition (disk);
1988         PedSector       cyl_size = bios_geom->sectors * bios_geom->heads;
1989         PedSector       start_base;
1990         int             head;
1991         PedGeometry*    solution = NULL;
1992         PedConstraint   *intersect, *log_meta_overlap;
1993
1994         PED_ASSERT (ext_part != NULL, return 0);
1995
1996         log_meta_overlap = _log_meta_overlap_constraint(part, &part->geom);
1997         intersect = ped_constraint_intersect (constraint, log_meta_overlap);
1998         ped_constraint_destroy (log_meta_overlap);
1999         if (!intersect)
2000                 return 0;
2001
2002         start_base = ped_round_down_to (part->geom.start, cyl_size);
2003
2004         for (head = _logical_min_start_head (part, bios_geom, ext_part, 0);
2005              head < PED_MIN (5, bios_geom->heads); head++) {
2006                 PedConstraint*  disk_constraint;
2007                 PedSector       start = start_base + head * bios_geom->sectors;
2008
2009                 if (head >= _logical_min_start_head (part, bios_geom,
2010                                                      ext_part, 1))
2011                         disk_constraint =
2012                                 _logical_constraint (disk, bios_geom, start, 1);
2013                 else
2014                         disk_constraint =
2015                                 _logical_constraint (disk, bios_geom, start, 0);
2016
2017                 solution = _best_solution (part, bios_geom, solution,
2018                                 _try_constraint (part, intersect,
2019                                                  disk_constraint));
2020         }
2021
2022         ped_constraint_destroy (intersect);
2023
2024         if (solution) {
2025                 ped_geometry_set (&part->geom, solution->start,
2026                                   solution->length);
2027                 ped_geometry_destroy (solution);
2028                 return 1;
2029         }
2030
2031         return 0;
2032 }
2033
2034 static int
2035 _align (PedPartition* part, const PedCHSGeometry* bios_geom,
2036         const PedConstraint* constraint)
2037 {
2038         if (part->type == PED_PARTITION_LOGICAL)
2039                 return _align_logical (part, bios_geom, constraint);
2040         else
2041                 return _align_primary (part, bios_geom, constraint);
2042 }
2043
2044 static PedConstraint*
2045 _no_geom_constraint (const PedDisk* disk, PedSector start, PedSector end)
2046 {
2047         PedGeometry      max;
2048
2049         ped_geometry_init (&max, disk->dev, start, end - start + 1);
2050         return ped_constraint_new_from_max (&max);
2051 }
2052
2053 static PedConstraint*
2054 _no_geom_extended_constraint (const PedPartition* part)
2055 {
2056         PedDevice*      dev = part->disk->dev;
2057         PedGeometry*    min = _get_min_extended_part_geom (part, NULL);
2058         PedGeometry     start_range;
2059         PedGeometry     end_range;
2060         PedConstraint*  constraint;
2061
2062         if (min) {
2063                 ped_geometry_init (&start_range, dev, 1, min->start);
2064                 ped_geometry_init (&end_range, dev, min->end,
2065                                    dev->length - min->end);
2066                 ped_geometry_destroy (min);
2067         } else {
2068                 ped_geometry_init (&start_range, dev, 1, dev->length - 1);
2069                 ped_geometry_init (&end_range, dev, 1, dev->length - 1);
2070         }
2071         constraint = ped_constraint_new (ped_alignment_any, ped_alignment_any,
2072                         &start_range, &end_range, 1, dev->length);
2073         return constraint;
2074 }
2075
2076 static int
2077 _align_primary_no_geom (PedPartition* part, const PedConstraint* constraint)
2078 {
2079         PedDisk*        disk = part->disk;
2080         PedGeometry*    solution;
2081
2082         if (part->type == PED_PARTITION_EXTENDED) {
2083                 solution = _try_constraint (part, constraint,
2084                                 _no_geom_extended_constraint (part));
2085         } else {
2086                 solution = _try_constraint (part, constraint,
2087                                 _no_geom_constraint (disk, 1,
2088                                                      disk->dev->length - 1));
2089         }
2090
2091         if (solution) {
2092                 ped_geometry_set (&part->geom, solution->start,
2093                                   solution->length);
2094                 ped_geometry_destroy (solution);
2095                 return 1;
2096         }
2097         return 0;
2098 }
2099
2100 static int
2101 _align_logical_no_geom (PedPartition* part, const PedConstraint* constraint)
2102 {
2103         PedGeometry*    solution;
2104
2105         solution = _try_constraint (part, constraint,
2106                         _log_meta_overlap_constraint (part, &part->geom));
2107
2108         if (solution) {
2109                 ped_geometry_set (&part->geom, solution->start,
2110                                   solution->length);
2111                 ped_geometry_destroy (solution);
2112                 return 1;
2113         }
2114         return 0;
2115 }
2116
2117 static int
2118 _align_no_geom (PedPartition* part, const PedConstraint* constraint)
2119 {
2120         if (part->type == PED_PARTITION_LOGICAL)
2121                 return _align_logical_no_geom (part, constraint);
2122         else
2123                 return _align_primary_no_geom (part, constraint);
2124 }
2125
2126 static int
2127 msdos_partition_align (PedPartition* part, const PedConstraint* constraint)
2128 {
2129         PedCHSGeometry  bios_geom;
2130         DosPartitionData* dos_data;
2131
2132         PED_ASSERT (part != NULL, return 0);
2133         PED_ASSERT (part->disk_specific != NULL, return 0);
2134
2135         dos_data = part->disk_specific;
2136
2137         if (dos_data->system == PARTITION_LDM && dos_data->orig) {
2138                 PedGeometry *orig_geom = &dos_data->orig->geom;
2139
2140                 if (ped_geometry_test_equal (&part->geom, orig_geom)
2141                     && ped_constraint_is_solution (constraint, &part->geom))
2142                         return 1;
2143
2144                 ped_geometry_set (&part->geom, orig_geom->start,
2145                                   orig_geom->length);
2146                 ped_exception_throw (
2147                         PED_EXCEPTION_ERROR,
2148                         PED_EXCEPTION_CANCEL,
2149                         _("Parted can't resize partitions managed by "
2150                           "Windows Dynamic Disk."));
2151                 return 0;
2152         }
2153
2154         partition_probe_bios_geometry (part, &bios_geom);
2155
2156         DosDiskData *disk_specific = part->disk->disk_specific;
2157         if (disk_specific->cylinder_alignment
2158             && _align(part, &bios_geom, constraint))
2159                 return 1;
2160         if (_align_no_geom (part, constraint))
2161                 return 1;
2162
2163 #ifndef DISCOVER_ONLY
2164         ped_exception_throw (
2165                 PED_EXCEPTION_ERROR,
2166                 PED_EXCEPTION_CANCEL,
2167                 _("Unable to satisfy all constraints on the partition."));
2168 #endif
2169         return 0;
2170 }
2171
2172 static int
2173 add_metadata_part (PedDisk* disk, PedPartitionType type, PedSector start,
2174                    PedSector end)
2175 {
2176         PedPartition*           new_part;
2177
2178         PED_ASSERT (disk != NULL, return 0);
2179
2180         new_part = ped_partition_new (disk, type | PED_PARTITION_METADATA, NULL,
2181                                       start, end);
2182         if (!new_part)
2183                 goto error;
2184         if (!ped_disk_add_partition (disk, new_part, NULL))
2185                 goto error_destroy_new_part;
2186
2187         return 1;
2188
2189 error_destroy_new_part:
2190         ped_partition_destroy (new_part);
2191 error:
2192         return 0;
2193 }
2194
2195 /* There are a few objectives here:
2196  *      - avoid having lots of "free space" partitions lying around, to confuse
2197  * the front end.
2198  *      - ensure that there's enough room to put in the extended partition
2199  * tables, etc.
2200  */
2201 static int
2202 add_logical_part_metadata (PedDisk* disk, const PedPartition* log_part)
2203 {
2204         PedPartition*   ext_part = ped_disk_extended_partition (disk);
2205         PedPartition*   prev = log_part->prev;
2206         PedCHSGeometry  bios_geom;
2207         PedSector       cyl_size;
2208         PedSector       metadata_start;
2209         PedSector       metadata_end;
2210         PedSector       metadata_length;
2211
2212         partition_probe_bios_geometry (ext_part, &bios_geom);
2213         cyl_size = bios_geom.sectors * bios_geom.heads;
2214
2215         /* if there's metadata shortly before the partition (on the same
2216          * cylinder), then make this new metadata partition touch the end of
2217          * the other.  No point having 63 bytes (or whatever) of free space
2218          * partition - just confuses front-ends, etc.
2219          *      Otherwise, start the metadata at the start of the cylinder
2220          */
2221
2222         metadata_end = log_part->geom.start - 1;
2223         metadata_start = ped_round_down_to (metadata_end, cyl_size);
2224         if (prev)
2225                 metadata_start = PED_MAX (metadata_start, prev->geom.end + 1);
2226         else
2227                 metadata_start = PED_MAX (metadata_start,
2228                                           ext_part->geom.start + 1);
2229         metadata_length = metadata_end - metadata_start + 1;
2230
2231         /* partition 5 doesn't need to have any metadata */
2232         if (log_part->num == 5 && metadata_length < bios_geom.sectors)
2233                 return 1;
2234
2235         PED_ASSERT (metadata_length > 0, return 0);
2236
2237         return add_metadata_part (disk, PED_PARTITION_LOGICAL,
2238                                   metadata_start, metadata_end);
2239 }
2240
2241 /*
2242  * Find the starting sector number of the first non-free partition,
2243  * set *SECTOR to that value, and return 1.
2244  * If there is no non-free partition, don't modify *SECTOR and return 0.
2245  */
2246 static int
2247 get_start_first_nonfree_part (const PedDisk* disk, PedSector *sector)
2248 {
2249         PedPartition* walk;
2250
2251         // disk->part_list is the first partition on the disk.
2252         if (!disk->part_list)
2253                 return 0;
2254
2255         for (walk = disk->part_list; walk; walk = walk->next) {
2256                 if (walk->type == PED_PARTITION_NORMAL ||
2257                                 walk->type == PED_PARTITION_EXTENDED) {
2258                         *sector = walk->geom.start;
2259                         return 1;
2260                 }
2261         }
2262         return 0;
2263 }
2264
2265 /*
2266  * Find the ending sector number of the last non-free partition,
2267  * set *SECTOR to that value, and return 1.
2268  * If there is no non-free partition, don't modify *SECTOR and return 0.
2269  */
2270 static int
2271 get_end_last_nonfree_part (const PedDisk* disk, PedSector *sector)
2272 {
2273         PedPartition* last_part = NULL;
2274         PedPartition* walk;
2275
2276         // disk->part_list is the first partition on the disk.
2277         if (!disk->part_list)
2278                 return 0;
2279
2280         for (walk = disk->part_list; walk; walk = walk->next) {
2281                 if (walk->type == PED_PARTITION_NORMAL ||
2282                                 walk->type == PED_PARTITION_EXTENDED) {
2283                         last_part = walk;
2284                 }
2285         }
2286
2287         if (!last_part)
2288                 return 0;
2289         else {
2290                 *sector = last_part->geom.end;
2291                 return 1;
2292         }
2293 }
2294
2295 /* Adds metadata placeholder partitions to cover the partition table (and
2296  * "free" space after it that often has bootloader stuff), and the last
2297  * incomplete cylinder at the end of the disk.
2298  *      Parted has to be mindful of the uncertainty of dev->bios_geom.
2299  * It therefore makes sure this metadata doesn't overlap with partitions.
2300  */
2301 static int
2302 add_startend_metadata (PedDisk* disk)
2303 {
2304         PedDevice* dev = disk->dev;
2305         PedSector cyl_size = dev->bios_geom.sectors * dev->bios_geom.heads;
2306         PedSector init_start, init_end, final_start, final_end;
2307
2308         // Ranges for the initial and final metadata partition.
2309         init_start = 0;
2310         if (!get_start_first_nonfree_part(disk, &init_end))
2311                 init_end = dev->bios_geom.sectors - 1;
2312         else
2313                 init_end = PED_MIN (dev->bios_geom.sectors - 1, init_end - 1);
2314
2315         DosDiskData *disk_specific = disk->disk_specific;
2316         if (!disk_specific->cylinder_alignment)
2317                 final_start = dev->length - 1;
2318         else if (!get_end_last_nonfree_part(disk, &final_start))
2319                 final_start = ped_round_down_to (dev->length, cyl_size);
2320         else
2321                 final_start = PED_MAX (final_start + 1,
2322                                 ped_round_down_to (dev->length, cyl_size));
2323         final_end = dev->length - 1;
2324
2325         // Create the metadata partitions.
2326         // init_end <= dev->length for devices that are _real_ small.
2327         if (init_start < init_end &&
2328                         init_end <= dev->length &&
2329                         !add_metadata_part (disk, PED_PARTITION_NORMAL,
2330                                 init_start, init_end))
2331                         return 0;
2332
2333         // init_end < final_start so they dont overlap.  For very small devs.
2334         if (final_start < final_end &&
2335                         init_end < final_start &&
2336                         final_end <= dev->length &&
2337                         !add_metadata_part (disk, PED_PARTITION_NORMAL,
2338                                 final_start, final_end))
2339                         return 0;
2340
2341         return 1;
2342 }
2343
2344 static int
2345 msdos_alloc_metadata (PedDisk* disk)
2346 {
2347         PedPartition*           ext_part;
2348
2349         PED_ASSERT (disk != NULL, return 0);
2350         PED_ASSERT (disk->dev != NULL, return 0);
2351
2352         if (!add_startend_metadata (disk))
2353                 return 0;
2354
2355         ext_part = ped_disk_extended_partition (disk);
2356         if (ext_part) {
2357                 int             i;
2358                 PedSector       start, end;
2359                 PedCHSGeometry  bios_geom;
2360
2361                 for (i=5; 1; i++) {
2362                         PedPartition* log_part;
2363                         log_part = ped_disk_get_partition (disk, i);
2364                         if (!log_part)
2365                                 break;
2366                         if (!add_logical_part_metadata (disk, log_part))
2367                                 return 0;
2368                 }
2369
2370                 partition_probe_bios_geometry (ext_part, &bios_geom);
2371                 start = ext_part->geom.start;
2372                 end = start + bios_geom.sectors - 1;
2373                 if (ext_part->part_list)
2374                         end = PED_MIN (end,
2375                                        ext_part->part_list->geom.start - 1);
2376                 if (!add_metadata_part (disk, PED_PARTITION_LOGICAL,
2377                                         start, end))
2378                         return 0;
2379         }
2380
2381         return 1;
2382 }
2383
2384 static int
2385 next_primary (const PedDisk* disk)
2386 {
2387         int     i;
2388         for (i=1; i<=DOS_N_PRI_PARTITIONS; i++) {
2389                 if (!ped_disk_get_partition (disk, i))
2390                         return i;
2391         }
2392         return 0;
2393 }
2394
2395 static int
2396 next_logical (const PedDisk* disk)
2397 {
2398         int     i;
2399         for (i=5; 1; i++) {
2400                 if (!ped_disk_get_partition (disk, i))
2401                         return i;
2402         }
2403 }
2404
2405 static int
2406 msdos_partition_enumerate (PedPartition* part)
2407 {
2408         PED_ASSERT (part != NULL, return 0);
2409         PED_ASSERT (part->disk != NULL, return 0);
2410
2411         /* don't re-number a primary partition */
2412         if (part->num != -1 && part->num <= DOS_N_PRI_PARTITIONS)
2413                 return 1;
2414
2415         part->num = -1;
2416
2417         if (part->type & PED_PARTITION_LOGICAL)
2418                 part->num = next_logical (part->disk);
2419         else
2420                 part->num = next_primary (part->disk);
2421
2422         return 1;
2423 }
2424
2425 static int
2426 msdos_get_max_primary_partition_count (const PedDisk* disk)
2427 {
2428         return DOS_N_PRI_PARTITIONS;
2429 }
2430
2431 static bool
2432 msdos_get_max_supported_partition_count(const PedDisk* disk, int *max_n)
2433 {
2434         *max_n = MAX_TOTAL_PART;
2435         return true;
2436 }
2437
2438 #include "pt-common.h"
2439 PT_define_limit_functions (msdos)
2440
2441 static PedDiskOps msdos_disk_ops = {
2442         clobber:                NULL,
2443         write:                  NULL_IF_DISCOVER_ONLY (msdos_write),
2444
2445         disk_set_flag:          msdos_disk_set_flag,
2446         disk_get_flag:          msdos_disk_get_flag,
2447         disk_is_flag_available: msdos_disk_is_flag_available,
2448
2449         partition_set_name:     NULL,
2450         partition_get_name:     NULL,
2451
2452   PT_op_function_initializers (msdos)
2453 };
2454
2455 static PedDiskType msdos_disk_type = {
2456         next:           NULL,
2457         name:           "msdos",
2458         ops:            &msdos_disk_ops,
2459         features:       PED_DISK_TYPE_EXTENDED
2460 };
2461
2462 void
2463 ped_disk_msdos_init ()
2464 {
2465         PED_ASSERT (sizeof (DosRawPartition) == 16, return);
2466         PED_ASSERT (sizeof (DosRawTable) == 512, return);
2467
2468         ped_disk_type_register (&msdos_disk_type);
2469 }
2470
2471 void
2472 ped_disk_msdos_done ()
2473 {
2474         ped_disk_type_unregister (&msdos_disk_type);
2475 }