Logo Search packages:      
Sourcecode: parted version File versions

disk_dos.c

/*
    libparted - a library for manipulating disk partitions
    Copyright (C) 1999, 2000, 2001, 2004 Free Software Foundation, Inc.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include "config.h"

#include <sys/time.h>
#include <parted/parted.h>
#include <parted/debug.h>
#include <parted/endian.h>
#include <string.h>

#if ENABLE_NLS
#  include <libintl.h>
#  define _(String) dgettext (PACKAGE, String)
#else
#  define _(String) (String)
#endif /* ENABLE_NLS */

/* this MBR boot code is loaded into 0000:7c00 by the BIOS.  See mbr.s for
 * the source, and how to build it
 */

static char MBR_BOOT_CODE[] = {
      0xfa, 0xb8, 0x00, 0x10, 0x8e, 0xd0, 0xbc, 0x00,
      0xb0, 0xb8, 0x00, 0x00, 0x8e, 0xd8, 0x8e, 0xc0,
      0xfb, 0xbe, 0x00, 0x7c, 0xbf, 0x00, 0x06, 0xb9,
      0x00, 0x02, 0xf3, 0xa4, 0xea, 0x21, 0x06, 0x00,
      0x00, 0xbe, 0xbe, 0x07, 0x38, 0x04, 0x75, 0x0b,
      0x83, 0xc6, 0x10, 0x81, 0xfe, 0xfe, 0x07, 0x75,
      0xf3, 0xeb, 0x16, 0xb4, 0x02, 0xb0, 0x01, 0xbb,
      0x00, 0x7c, 0xb2, 0x80, 0x8a, 0x74, 0x01, 0x8b,
      0x4c, 0x02, 0xcd, 0x13, 0xea, 0x00, 0x7c, 0x00,
      0x00, 0xeb, 0xfe
};

#define MSDOS_MAGIC           0xAA55
#define PARTITION_MAGIC_MAGIC 0xf6f6

#define PARTITION_EMPTY       0x00
#define PARTITION_FAT12       0x01
#define PARTITION_FAT16_SM    0x04
#define PARTITION_EXT         0x05
#define PARTITION_FAT16       0x06
#define PARTITION_NTFS        0x07
#define PARTITION_HPFS        0x07
#define PARTITION_FAT32       0x0b
#define PARTITION_FAT32_LBA   0x0c
#define PARTITION_FAT16_LBA   0x0e
#define PARTITION_EXT_LBA     0x0f

#define PART_FLAG_HIDDEN      0x10  /* Valid for FAT/NTFS only */
#define PARTITION_FAT12_H     (PARTITION_FAT12  | PART_FLAG_HIDDEN)
#define PARTITION_FAT16_SM_H  (PARTITION_FAT16_SM     | PART_FLAG_HIDDEN)
#define PARTITION_EXT_H       (PARTITION_EXT          | PART_FLAG_HIDDEN)
#define PARTITION_FAT16_H     (PARTITION_FAT16  | PART_FLAG_HIDDEN)
#define PARTITION_NTFS_H      (PARTITION_NTFS         | PART_FLAG_HIDDEN)
#define PARTITION_FAT32_H     (PARTITION_FAT32  | PART_FLAG_HIDDEN)
#define PARTITION_FAT32_LBA_H (PARTITION_FAT32_LBA    | PART_FLAG_HIDDEN)
#define PARTITION_FAT16_LBA_H (PARTITION_FAT16_LBA    | PART_FLAG_HIDDEN)

#define PARTITION_LDM         0x42

#define PARTITION_COMPAQ_DIAG 0x12
#define PARTITION_LINUX_SWAP  0x82
#define PARTITION_LINUX       0x83
#define PARTITION_LINUX_EXT   0x85
#define PARTITION_LINUX_LVM   0x8e
#define PARTITION_SUN_UFS     0xbf
#define PARTITION_DELL_DIAG   0xde
#define PARTITION_GPT         0xee
#define PARTITION_PALO        0xf0
#define PARTITION_PREP        0x41
#define PARTITION_LINUX_RAID  0xfd
#define PARTITION_LINUX_LVM_OLD 0xfe

/* This constant contains the maximum cylinder number that can be represented
 * in (C,H,S) notation.  Higher cylinder numbers are reserved for
 * "too big" indicators (in which case only LBA addressing can be used).
 *    Some partition tables in the wild indicate this number is 1021.
 * (i.e. 1022 is sometimes used to indicate "use LBA").
 */
#define MAX_CHS_CYLINDER      1021

typedef struct _DosRawPartition           DosRawPartition;
typedef struct _DosRawTable         DosRawTable;

/* note: lots of bit-bashing here, thus, you shouldn't look inside it.
 * Use chs_to_sector() and sector_to_chs() instead.
 */
typedef struct {
      uint8_t           head;
      uint8_t           sector;
      uint8_t           cylinder;
} __attribute__((packed)) RawCHS;

/* ripped from Linux source */
struct _DosRawPartition {
        uint8_t         boot_ind;   /* 00:  0x80 - active */
      RawCHS            chs_start;  /* 01: */
      uint8_t           type;       /* 04: partition type */
      RawCHS            chs_end;    /* 05: */
      uint32_t    start;            /* 08: starting sector counting from 0 */
      uint32_t    length;           /* 0c: nr of sectors in partition */
} __attribute__((packed));

struct _DosRawTable {
      char              boot_code [440];
      uint32_t                mbr_signature;    /* really a unique ID */
      uint16_t                Unknown;
      DosRawPartition         partitions [4];
      uint16_t          magic;
} __attribute__((packed));

/* OrigState is information we want to preserve about the partition for
 * dealing with CHS issues
 */
typedef struct {
      PedGeometry geom;
      DosRawPartition   raw_part;
      PedSector   lba_offset; /* needed for computing start/end for
                               * logical partitions */
} OrigState;

typedef struct {
      unsigned char     system;
      int         boot;
      int         hidden;
      int         raid;
      int         lvm;
      int         lba;
      int         palo;
      int         prep;
      OrigState*  orig;             /* used for CHS stuff */
} DosPartitionData;

static PedDiskType msdos_disk_type;

static int
msdos_probe (PedDevice *dev)
{
      PedDiskType*      disk_type;
      DosRawTable part_table;
      int         i;

      PED_ASSERT (dev != NULL, return 0);

      if (!ped_device_read (dev, &part_table, 0, 1))
            return 0;

      /* check magic */
      if (PED_LE16_TO_CPU (part_table.magic) != MSDOS_MAGIC)
            return 0;

      /* if this is a FAT fs, fail here.  Note that the Smart Boot Manager
       * Loader (SBML) signature indicates a partition table, not a file
       * system.
       */
      if ((!strncmp (part_table.boot_code + 0x36, "FAT", 3)
          && strncmp (part_table.boot_code + 0x40, "SBML", 4) != 0)
          || !strncmp (part_table.boot_code + 0x52, "FAT", 3))
            return 0;

      /* If this is a GPT disk, fail here */
      for (i = 0; i < 4; i++) {
            if (part_table.partitions[i].type == PARTITION_GPT)
                  return 0;
      }

#ifdef ENABLE_PC98
      /* HACK: it's impossible to tell PC98 and msdos disk labels apart.
       * Someone made the signatures the same (very clever).  Since
       * PC98 has some idiosyncracies with it's boot-loader, it's detection
       * is more reliable */
      disk_type = ped_disk_type_get ("pc98");
      if (disk_type && disk_type->ops->probe (dev))
            return 0;
#endif /* ENABLE_PC98 */

      return 1;
}

static PedDisk*
msdos_alloc (PedDevice* dev)
{
      PedDisk* disk;
      PED_ASSERT (dev != NULL, return NULL);

      disk = _ped_disk_alloc (dev, &msdos_disk_type);
      if (disk)
            disk->disk_specific = NULL;
      return disk;
}

static PedDisk*
msdos_duplicate (const PedDisk* disk)
{
      PedDisk*    new_disk;
       
      new_disk = ped_disk_new_fresh (disk->dev, &msdos_disk_type);
      if (!new_disk)
            return NULL;
      new_disk->disk_specific = NULL;
      return new_disk;
}

static void
msdos_free (PedDisk* disk)
{
      PED_ASSERT (disk != NULL, return);

      _ped_disk_free (disk);
}

#ifndef DISCOVER_ONLY
static int
msdos_clobber (PedDevice* dev)
{
      DosRawTable       table;

      PED_ASSERT (dev != NULL, return 0);
      PED_ASSERT (msdos_probe (dev), return 0);

      if (!ped_device_read (dev, &table, 0, 1))
            return 0;
      table.magic = 0;
      return ped_device_write (dev, (void*) &table, 0, 1);
}
#endif /* !DISCOVER_ONLY */

static int
chs_get_cylinder (const RawCHS* chs)
{
      return chs->cylinder + ((chs->sector >> 6) << 8);
}

static int
chs_get_head (const RawCHS* chs)
{
      return chs->head;
}

/* counts from 0 */
static int
chs_get_sector (const RawCHS* chs)
{
      return (chs->sector & 0x3f) - 1;
}

static PedSector
chs_to_sector (PedDevice* dev, const PedCHSGeometry *bios_geom,
             const RawCHS* chs)
{
      PedSector   c;          /* not measured in sectors, but need */
      PedSector   h;          /* lots of bits */
      PedSector   s;

      PED_ASSERT (bios_geom != NULL, return 0);
      PED_ASSERT (chs != NULL, return 0);

      c = chs_get_cylinder (chs);
      h = chs_get_head (chs);
      s = chs_get_sector (chs);

      if (c > MAX_CHS_CYLINDER)           /* MAGIC: C/H/S is irrelevant */
            return 0;
      if (s < 0)
            return 0;
      return ((c * bios_geom->heads + h) * bios_geom->sectors + s)
            * (dev->sector_size / 512);
}

static void
sector_to_chs (PedDevice* dev, const PedCHSGeometry* bios_geom,
             PedSector sector, RawCHS* chs)
{
      PedSector   real_c, real_h, real_s;

      PED_ASSERT (dev != NULL, return);
      PED_ASSERT (chs != NULL, return);
      
      if (!bios_geom)
            bios_geom = &dev->bios_geom;

      sector /= (dev->sector_size / 512);

      real_c = sector / (bios_geom->heads * bios_geom->sectors);
      real_h = (sector / bios_geom->sectors) % bios_geom->heads;
      real_s = sector % bios_geom->sectors;

      if (real_c > MAX_CHS_CYLINDER) {
            real_c = 1023;
            real_h = bios_geom->heads - 1;
            real_s = bios_geom->sectors - 1;
      }

      chs->cylinder = real_c % 0x100;
      chs->head = real_h;
      chs->sector = real_s + 1 + (real_c >> 8 << 6);
}

static PedSector
legacy_start (PedDisk* disk, const PedCHSGeometry* bios_geom,
            const DosRawPartition* raw_part)
{
      PED_ASSERT (disk != NULL, return 0);
      PED_ASSERT (raw_part != NULL, return 0);

      return chs_to_sector (disk->dev, bios_geom, &raw_part->chs_start);
}

static PedSector
legacy_end (PedDisk* disk, const PedCHSGeometry* bios_geom,
          const DosRawPartition* raw_part)
{
      PED_ASSERT (disk != NULL, return 0);
      PED_ASSERT (raw_part != NULL, return 0);

      return chs_to_sector (disk->dev, bios_geom, &raw_part->chs_end);
}

static PedSector
linear_start (const PedDisk* disk, const DosRawPartition* raw_part,
            PedSector offset)
{
      PED_ASSERT (disk != NULL, return 0);
      PED_ASSERT (raw_part != NULL, return 0);

      return offset
             + PED_LE32_TO_CPU (raw_part->start)
                        * (disk->dev->sector_size / 512);
}

static PedSector
linear_end (const PedDisk* disk, const DosRawPartition* raw_part,
          PedSector offset)
{
      PED_ASSERT (disk != NULL, return 0);
      PED_ASSERT (raw_part != NULL, return 0);

      return linear_start (disk, raw_part, offset)
             + (PED_LE32_TO_CPU (raw_part->length) - 1)
                        * (disk->dev->sector_size / 512);
}

#ifndef DISCOVER_ONLY
static int
partition_check_bios_geometry (PedPartition* part, PedCHSGeometry* bios_geom)
{
      PedSector         leg_start, leg_end;
      DosPartitionData* dos_data;
      PedDisk*          disk;

      PED_ASSERT (part != NULL, return 0);
      PED_ASSERT (part->disk != NULL, return 0);
      PED_ASSERT (part->disk_specific != NULL, return 0);
      dos_data = part->disk_specific;

      if (!dos_data->orig)
            return 1;

      disk = part->disk;
      leg_start = legacy_start (disk, bios_geom, &dos_data->orig->raw_part);
      leg_end = legacy_end (disk, bios_geom, &dos_data->orig->raw_part);

      if (leg_start && leg_start != dos_data->orig->geom.start)
            return 0;
      if (leg_end && leg_end != dos_data->orig->geom.end)
            return 0;
      return 1;
}

static int
disk_check_bios_geometry (PedDisk* disk, PedCHSGeometry* bios_geom)
{
      PedPartition* part = NULL;

      PED_ASSERT (disk != NULL, return 0);

      while ((part = ped_disk_next_partition (disk, part))) {
            if (ped_partition_is_active (part)) {
                  if (!partition_check_bios_geometry (part, bios_geom))
                        return 0;
            }
      }

      return 1;
}

static int
probe_filesystem_for_geom (const PedPartition* part, PedCHSGeometry* bios_geom)
{
      const char* ms_types[] = {"ntfs", "fat16", "fat32", NULL};
      int i;
      int found;
      unsigned char buf[PED_SECTOR_SIZE];
      int sectors;
      int heads;

      PED_ASSERT (part != NULL, return 0);
      PED_ASSERT (part->disk != NULL, return 0);
      PED_ASSERT (bios_geom != NULL, return 0);

      if (!part->fs_type)
            return 0;

      found = 0;
      for (i = 0; ms_types[i]; i++) {
            if (!strcmp(ms_types[i], part->fs_type->name))
                  found = 1;
      }
      if (!found)
            return 0;

      if (!ped_geometry_read(&part->geom, buf, 0, 1))
            return 0;

      /* shared by the start of all Microsoft file systems */
      sectors = buf[0x18] + (buf[0x19] << 8);
      heads = buf[0x1a] + (buf[0x1b] << 8);

      if (sectors < 1 || sectors > 63)
            return 0;
      if (heads > 255 || heads < 1)
            return 0;

      bios_geom->sectors = sectors;
      bios_geom->heads = heads;
      bios_geom->cylinders = part->disk->dev->length / (sectors * heads);
      return 1;
}

/* This function attempts to infer the BIOS CHS geometry of the hard disk
 * from the CHS + LBA information contained in the partition table from
 * a single partition's entry.
 *
 * This involves some maths.  Let (c,h,s,a) be the starting cylinder,
 * starting head, starting sector and LBA start address of the partition.
 * Likewise, (C,H,S,A) the end addresses.  Using both of these pieces
 * of information, we want to deduce cyl_sectors and head_sectors which
 * are the sizes of a single cylinder and a single head, respectively.
 *
 * The relationships are:
 * c*cyl_sectors + h * head_sectors + s = a
 * C*cyl_sectors + H * head_sectors + S = A
 *
 * We can rewrite this in matrix form:
 *
 * [ c h ] [ cyl_sectors  ]  =  [ s - a ]  =  [ a_ ]
 * [ C H ] [ head_sectors ]     [ S - A ]     [ A_ ]
 * 
 * (s - a is abbreviated to a_to simplify the notation.)
 * 
 * Solving these equations requires following the row reduction algorithm.  We
 * need to be careful about a few things though:
 *    - the equations might be linearly dependent, in which case there
 *    are many solutions.
 *    - the equations might be inconsistent, in which case there
 *    are no solutions.  (Inconsistent partition table entry!)
 *    - there might be zeros, so we need to be careful about applying
 *    the algorithm.  We know, however, that C > 0.
 */
static int
probe_partition_for_geom (PedPartition* part, PedCHSGeometry* bios_geom)
{
      DosPartitionData* dos_data;
      RawCHS* start_chs;
      RawCHS* end_chs;
      PedSector c, h, s, a, a_;     /* start */
      PedSector C, H, S, A, A_;     /* end */
      PedSector cyl_size, head_size;
      PedSector cylinders, heads, sectors;

      PED_ASSERT (part != NULL, return 0);
      PED_ASSERT (part->disk_specific != NULL, return 0);
      PED_ASSERT (bios_geom != NULL, return 0);

      dos_data = part->disk_specific;

      if (!dos_data->orig)
            return 0;

      start_chs = &dos_data->orig->raw_part.chs_start;
      c = chs_get_cylinder (start_chs);
      h = chs_get_head (start_chs);
      s = chs_get_sector (start_chs);
      a = dos_data->orig->geom.start;
      a_ = a - s;

      end_chs = &dos_data->orig->raw_part.chs_end;
      C = chs_get_cylinder (end_chs);
      H = chs_get_head (end_chs);
      S = chs_get_sector (end_chs);
      A = dos_data->orig->geom.end;
      A_ = A - S;

      if (h < 0 || H < 0 || h > 254 || H > 254)
            return 0;
      if (c > C)
            return 0;

      /* If no geometry is feasible, then don't even bother.
       * Useful for eliminating assertions for broken partition
       * tables generated by Norton Ghost et al.
       */
      if (A > (C+1) * 255 * 63)
            return 0;

      /* Not enough information.  In theory, we can do better.  Should we? */
      if (C > MAX_CHS_CYLINDER)
            return 0;
      if (C == 0)
            return 0;

      /* STEP ONE: find cyl_size */
      if (h == 0 && c > 0) {
            /* If the matrix looks like this, then it's easy!
             * [ c 0 ]
             * [ C H ]
             */
            cyl_size = a_ / c;
      } else if (h > 0) {
            /* if h > 0, we can do R2 -> R2 - H/h R1 to get:
             *
             * [ c h ] = [ a_ ]
             * [ X 0 ] = [ Y ]
             *
             * Then, cyl_size = Y / X
             *
             * However, if H/h isn't an integer, this isn't going
             * to work out nicely, so the partition table must
             * be inconsistent.
             */
            if (H % h != 0)
                  return 0;
            if (C == H/h * c)
                  return 0;
            cyl_size = (A_ - H/h * a_) / (C - H/h * c);
      } else {
            /* h == 0 && c == 0: not enough information */
            return 0;
      }

      PED_ASSERT (cyl_size > 0, return 0);
      PED_ASSERT (cyl_size <= 255 * 63, return 0);

      /* STEP TWO: find head_size */
      if (h > 0) {
            head_size = (a_ - c * cyl_size) / h;
      } else if (H > 0) {
            head_size = (A_ - C * cyl_size) / H;
      } else {
            /* not enough information */
            return 0;
      }

      PED_ASSERT (head_size > 0, return 0);
      PED_ASSERT (head_size <= 63, return 0);

      cylinders = part->disk->dev->length / cyl_size;
      heads = cyl_size / head_size;
      sectors = head_size;

      PED_ASSERT (heads > 0, return 0);
      PED_ASSERT (heads < 256, return 0);

      PED_ASSERT (sectors > 0, return 0);
      PED_ASSERT (sectors <= 63, return 0);

      PED_ASSERT ((c * heads + h) * sectors + s == a, return 0);
      PED_ASSERT ((C * heads + H) * sectors + S == A, return 0);

      bios_geom->cylinders = cylinders;
      bios_geom->heads = heads;
      bios_geom->sectors = sectors;

      return 1;
}

static void
partition_probe_bios_geometry (PedPartition* part, PedCHSGeometry* bios_geom)
{
      PED_ASSERT (part != NULL, return);
      PED_ASSERT (part->disk != NULL, return);
      PED_ASSERT (bios_geom != NULL, return);

      if (ped_partition_is_active (part)) {
            if (probe_partition_for_geom (part, bios_geom))
                  return;
            if (part->type & PED_PARTITION_EXTENDED) {
                  if (probe_filesystem_for_geom (part, bios_geom))
                        return;
            }
      }
      if (part->type & PED_PARTITION_LOGICAL) {
            PedPartition* ext_part;
            ext_part = ped_disk_extended_partition (part->disk);
            PED_ASSERT (ext_part != NULL, return);
            partition_probe_bios_geometry (ext_part, bios_geom);
      } else {
            *bios_geom = part->disk->dev->bios_geom;
      }
}

static void
disk_probe_bios_geometry (PedDisk* disk, PedCHSGeometry* bios_geom)
{
      PedPartition*     part;

      /* first look at the boot partition */
      part = NULL;
      while ((part = ped_disk_next_partition (disk, part))) {
            if (!ped_partition_is_active (part))
                  continue;
            if (ped_partition_get_flag (part, PED_PARTITION_BOOT)) {
                  if (probe_filesystem_for_geom (part, bios_geom))
                        return;
                  if (probe_partition_for_geom (part, bios_geom))
                        return;
            }
      }

      /* that didn't work... try all partition table entries */
      part = NULL;
      while ((part = ped_disk_next_partition (disk, part))) {
            if (ped_partition_is_active (part)) {
                  if (probe_partition_for_geom (part, bios_geom))
                        return;
            }
      }

      /* that didn't work... look at all file systems */
      part = NULL;
      while ((part = ped_disk_next_partition (disk, part))) {
            if (ped_partition_is_active (part)) {
                  if (probe_filesystem_for_geom (part, bios_geom))
                        return;
            }
      }
}
#endif /* !DISCOVER_ONLY */

static int
raw_part_is_extended (const DosRawPartition* raw_part)
{
      PED_ASSERT (raw_part != NULL, return 0);

      switch (raw_part->type) {
      case PARTITION_EXT:
      case PARTITION_EXT_LBA:
      case PARTITION_LINUX_EXT:
            return 1;

      default:
            return 0;
      }

      return 0;
}

static int
raw_part_is_hidden (const DosRawPartition* raw_part)
{
      PED_ASSERT (raw_part != NULL, return 0);

      switch (raw_part->type) {
      case PARTITION_FAT12_H:
      case PARTITION_FAT16_SM_H:
      case PARTITION_FAT16_H:
      case PARTITION_FAT32_H:
      case PARTITION_NTFS_H:
      case PARTITION_FAT32_LBA_H:
      case PARTITION_FAT16_LBA_H:
            return 1;

      default:
            return 0;
      }

      return 0;
}

static int
raw_part_is_lba (const DosRawPartition* raw_part)
{
      PED_ASSERT (raw_part != NULL, return 0);

      switch (raw_part->type) {
      case PARTITION_FAT32_LBA:
      case PARTITION_FAT16_LBA:
      case PARTITION_EXT_LBA:
      case PARTITION_FAT32_LBA_H:
      case PARTITION_FAT16_LBA_H:
            return 1;

      default:
            return 0;
      }

      return 0;
}

PedPartition*
raw_part_parse (PedDisk* disk, const DosRawPartition* raw_part,
              PedSector lba_offset, PedPartitionType type)
{
      PedPartition* part;
      DosPartitionData* dos_data;

      PED_ASSERT (disk != NULL, return NULL);
      PED_ASSERT (raw_part != NULL, return NULL);

      part = ped_partition_new (
            disk, type, NULL,
            linear_start (disk, raw_part, lba_offset),
            linear_end (disk, raw_part, lba_offset));
      if (!part)
            return NULL;
      dos_data = part->disk_specific;
      dos_data->system = raw_part->type;
      dos_data->boot = raw_part->boot_ind != 0;
      dos_data->hidden = raw_part_is_hidden (raw_part);
      dos_data->raid = raw_part->type == PARTITION_LINUX_RAID;
      dos_data->lvm = raw_part->type == PARTITION_LINUX_LVM_OLD
                  || raw_part->type == PARTITION_LINUX_LVM;
      dos_data->lba = raw_part_is_lba (raw_part);
      dos_data->palo = raw_part->type == PARTITION_PALO;
      dos_data->prep = raw_part->type == PARTITION_PREP;
      dos_data->orig = ped_malloc (sizeof (OrigState));
      if (!dos_data->orig) {
            ped_partition_destroy (part);
            return NULL;
      }
      dos_data->orig->geom = part->geom;
      dos_data->orig->raw_part = *raw_part;
      dos_data->orig->lba_offset = lba_offset;
      return part;
}

static int
read_table (PedDisk* disk, PedSector sector, int is_extended_table)
{
      int               i;
      DosRawTable       table;
      DosRawPartition*  raw_part;
      PedPartition*           part;
      PedPartitionType  type;
      PedSector         lba_offset;
      PedConstraint*          constraint_exact;

      PED_ASSERT (disk != NULL, return 0);
      PED_ASSERT (disk->dev != NULL, return 0);

      if (!ped_device_read (disk->dev, (void*) &table, sector, 1))
            goto error;

      /* weird: empty extended partitions are filled with 0xf6 by PM */
      if (is_extended_table
          && PED_LE16_TO_CPU (table.magic) == PARTITION_MAGIC_MAGIC)
            return 1;

#ifndef DISCOVER_ONLY
      if (PED_LE16_TO_CPU (table.magic) != MSDOS_MAGIC) {
            if (ped_exception_throw (
                  PED_EXCEPTION_ERROR, PED_EXCEPTION_IGNORE_CANCEL,
                  _("Invalid partition table on %s - wrong signature %x"),
                  disk->dev->path,
                  PED_LE16_TO_CPU (table.magic))
                        != PED_EXCEPTION_IGNORE)
                  goto error;
            return 1;
      }
#endif

      /* parse the partitions from this table */
      for (i = 0; i < 4; i++) {
            raw_part = &table.partitions [i];
            if (raw_part->type == PARTITION_EMPTY || !raw_part->length)
                  continue;

            /* process nested extended partitions after normal logical
             * partitions, to make sure we get the order right.
             */
            if (is_extended_table && raw_part_is_extended (raw_part))
                  continue;   

            lba_offset = is_extended_table ? sector : 0;

            if (linear_start (disk, raw_part, lba_offset) == sector) {
                  if (ped_exception_throw (
                        PED_EXCEPTION_ERROR,
                        PED_EXCEPTION_IGNORE_CANCEL,
                        _("Invalid partition table - recursive "
                        "partition on %s."),
                        disk->dev->path)
                              != PED_EXCEPTION_IGNORE)
                        goto error;
                  continue;   /* avoid infinite recursion */
            }

            if (is_extended_table)
                  type = PED_PARTITION_LOGICAL;
            else if (raw_part_is_extended (raw_part))
                  type = PED_PARTITION_EXTENDED;
            else
                  type = PED_PARTITION_NORMAL;

            part = raw_part_parse (disk, raw_part, lba_offset, type);
            if (!part)
                  goto error;
            if (!is_extended_table)
                  part->num = i + 1;
            if (type != PED_PARTITION_EXTENDED)
                  part->fs_type = ped_file_system_probe (&part->geom);

            constraint_exact = ped_constraint_exact (&part->geom);
            if (!ped_disk_add_partition (disk, part, constraint_exact))
                  goto error;
            ped_constraint_destroy (constraint_exact);

            /* non-nested extended partition */
            if (part->type == PED_PARTITION_EXTENDED) {
                  if (!read_table (disk, part->geom.start, 1))
                        goto error;
            }
      }

      if (is_extended_table) {
            /* process the nested extended partitions */
            for (i = 0; i < 4; i++) {
                  PedSector part_start;

                  raw_part = &table.partitions [i];
                  if (!raw_part_is_extended (raw_part))
                        continue;

                  lba_offset = ped_disk_extended_partition
                              (disk)->geom.start;
                  part_start = linear_start (disk, raw_part, lba_offset);
                  if (part_start == sector) {
                        /* recursive table - already threw an
                         * exception above.
                         */
                        continue;
                  }
                  if (!read_table (disk, part_start, 1))
                        goto error;
            }
      }

      return 1;

error:
      ped_disk_delete_all (disk);
      return 0;
}

static int
msdos_read (PedDisk* disk)
{
      PED_ASSERT (disk != NULL, return 0);
      PED_ASSERT (disk->dev != NULL, return 0);

      ped_disk_delete_all (disk);
      if (!read_table (disk, 0, 0))
            return 0;

#ifndef DISCOVER_ONLY
      /* try to figure out the correct BIOS CHS values */
      if (!disk_check_bios_geometry (disk, &disk->dev->bios_geom)) {
            PedCHSGeometry bios_geom = disk->dev->bios_geom;
            disk_probe_bios_geometry (disk, &bios_geom);

            /* if the geometry was wrong, then we should reread, to
             * make sure the metadata is allocated in the right places.
             */
            if (disk->dev->bios_geom.cylinders != bios_geom.cylinders
                || disk->dev->bios_geom.heads != bios_geom.heads
                || disk->dev->bios_geom.sectors != bios_geom.sectors) {
                  disk->dev->bios_geom = bios_geom;
                  return msdos_read (disk);
            }
      }
#endif

      return 1;
}

#ifndef DISCOVER_ONLY
static int
fill_raw_part (DosRawPartition* raw_part, PedPartition* part, PedSector offset)
{
      DosPartitionData* dos_data;
      PedCHSGeometry          bios_geom;

      PED_ASSERT (raw_part != NULL, return 0);
      PED_ASSERT (part != NULL, return 0);

      partition_probe_bios_geometry (part, &bios_geom);

      dos_data = part->disk_specific;

      raw_part->boot_ind = 0x80 * dos_data->boot;
      raw_part->type = dos_data->system;
      raw_part->start = PED_CPU_TO_LE32 ((part->geom.start - offset)
                        / (part->disk->dev->sector_size / 512));
      raw_part->length = PED_CPU_TO_LE32 (part->geom.length
                        / (part->disk->dev->sector_size / 512));

      sector_to_chs (part->disk->dev, &bios_geom, part->geom.start,
                   &raw_part->chs_start);
      sector_to_chs (part->disk->dev, &bios_geom, part->geom.end,
                   &raw_part->chs_end);

      if (dos_data->orig) {
            DosRawPartition* orig_raw_part = &dos_data->orig->raw_part;
            if (dos_data->orig->geom.start == part->geom.start)
                  raw_part->chs_start = orig_raw_part->chs_start;
            if (dos_data->orig->geom.end == part->geom.end)
                  raw_part->chs_end = orig_raw_part->chs_end;
      }

      return 1;
}

static int
fill_ext_raw_part_geom (DosRawPartition* raw_part, PedCHSGeometry* bios_geom,
                  PedGeometry* geom, PedSector offset)
{
      PED_ASSERT (raw_part != NULL, return 0);
      PED_ASSERT (geom != NULL, return 0);
      PED_ASSERT (geom->dev != NULL, return 0);

      raw_part->boot_ind = 0;
      raw_part->type = PARTITION_EXT;
      raw_part->start = PED_CPU_TO_LE32 ((geom->start - offset)
                        / (geom->dev->sector_size / 512));
      raw_part->length = PED_CPU_TO_LE32 (geom->length
                        / (geom->dev->sector_size / 512));

      sector_to_chs (geom->dev, bios_geom, geom->start, &raw_part->chs_start);
      sector_to_chs (geom->dev, bios_geom, geom->start + geom->length - 1,
                   &raw_part->chs_end);

      return 1;
}

static int
write_ext_table (PedDisk* disk, PedSector sector, PedPartition* logical)
{
      DosRawTable       table;
      PedPartition*           part;
      PedSector         lba_offset;

      PED_ASSERT (disk != NULL, return 0);
      PED_ASSERT (ped_disk_extended_partition (disk) != NULL, return 0);
      PED_ASSERT (logical != NULL, return 0);

      lba_offset = ped_disk_extended_partition (disk)->geom.start;

      memset (&table, 0, sizeof (DosRawTable));
      table.magic = PED_CPU_TO_LE16 (MSDOS_MAGIC);

      if (!fill_raw_part (&table.partitions[0], logical, sector))
            return 0;

      part = ped_disk_get_partition (disk, logical->num + 1);
      if (part) {
            PedGeometry*            geom;
            PedCHSGeometry          bios_geom;

            geom = ped_geometry_new (disk->dev, part->prev->geom.start,
                        part->geom.end - part->prev->geom.start + 1);
            if (!geom)
                  return 0;
            partition_probe_bios_geometry (part, &bios_geom);
            fill_ext_raw_part_geom (&table.partitions[1], &bios_geom,
                                geom, lba_offset);
            ped_geometry_destroy (geom);

            if (!write_ext_table (disk, part->prev->geom.start, part))
                  return 0;
      }

      return ped_device_write (disk->dev, (void*) &table, sector, 1);
}

static int
write_empty_table (PedDisk* disk, PedSector sector)
{
      DosRawTable       table;

      PED_ASSERT (disk != NULL, return 0);

      memset (&table, 0, sizeof (DosRawTable));
      table.magic = PED_CPU_TO_LE16 (MSDOS_MAGIC);

      return ped_device_write (disk->dev, (void*) &table, sector, 1);
}

/* Find the first logical partition, and write the partition table for it.
 */
static int
write_extended_partitions (PedDisk* disk)
{
      PedPartition*           ext_part;
      PedPartition*           part;
      PedCHSGeometry          bios_geom;

      PED_ASSERT (disk != NULL, return 0);

      ext_part = ped_disk_extended_partition (disk);
      partition_probe_bios_geometry (ext_part, &bios_geom);
      part = ped_disk_get_partition (disk, 5);
      if (part)
            return write_ext_table (disk, ext_part->geom.start, part);
      else
            return write_empty_table (disk, ext_part->geom.start);
}

static inline uint32_t generate_random_id()
{
      struct timeval tv;
      int rc;
      rc = gettimeofday(&tv, NULL);
      if (rc == -1)
            return 0;
      return (uint32_t)(tv.tv_usec & 0xFFFFFFFFUL);
}

static int
msdos_write (PedDisk* disk)
{
      DosRawTable       table;
      PedPartition*           part;
      int               i;

      PED_ASSERT (disk != NULL, return 0);
      PED_ASSERT (disk->dev != NULL, return 0);

      ped_device_read (disk->dev, &table, 0, 1);

      if (!table.boot_code[0]) {
            memset (table.boot_code, 0, 512);
            memcpy (table.boot_code, MBR_BOOT_CODE, sizeof (MBR_BOOT_CODE));
      }

      /* If there is no unique identifier, generate a random one */
      if (!table.mbr_signature)
            table.mbr_signature = generate_random_id();

      memset (table.partitions, 0, sizeof (DosRawPartition) * 4);
      table.magic = PED_CPU_TO_LE16 (MSDOS_MAGIC);

      for (i=1; i<=4; i++) {
            part = ped_disk_get_partition (disk, i);
            if (!part)
                  continue;

            if (!fill_raw_part (&table.partitions [i - 1], part, 0))
                  return 0;

            if (part->type == PED_PARTITION_EXTENDED) {
                  if (!write_extended_partitions (disk))
                        return 0;
            }
      }

      if (!ped_device_write (disk->dev, (void*) &table, 0, 1))
            return 0;
      return ped_device_sync (disk->dev);
}
#endif /* !DISCOVER_ONLY */

static PedPartition*
msdos_partition_new (const PedDisk* disk, PedPartitionType part_type,
                 const PedFileSystemType* fs_type,
                 PedSector start, PedSector end)
{
      PedPartition*           part;
      DosPartitionData* dos_data;

      part = _ped_partition_alloc (disk, part_type, fs_type, start, end);
      if (!part)
            goto error;

      if (ped_partition_is_active (part)) {
            part->disk_specific
                        = dos_data = ped_malloc (sizeof (DosPartitionData));
            if (!dos_data)
                  goto error_free_part;
            dos_data->orig = NULL;
            dos_data->system = PARTITION_LINUX;
            dos_data->hidden = 0;
            dos_data->boot = 0;
            dos_data->raid = 0;
            dos_data->lvm = 0;
            dos_data->lba = 0;
            dos_data->palo = 0;
            dos_data->prep = 0;
      } else {
            part->disk_specific = NULL;
      }
      return part;

error_free_dos_data:
      ped_free (dos_data);
error_free_part:
      ped_free (part);
error:
      return 0;
}

static PedPartition*
msdos_partition_duplicate (const PedPartition* part)
{
      PedPartition*           new_part;
      DosPartitionData* new_dos_data;
      DosPartitionData* old_dos_data;

      new_part = ped_partition_new (part->disk, part->type, part->fs_type,
                              part->geom.start, part->geom.end);
      if (!new_part)
            return NULL;
      new_part->num = part->num;

      old_dos_data = (DosPartitionData*) part->disk_specific;
      new_dos_data = (DosPartitionData*) new_part->disk_specific;
      new_dos_data->system = old_dos_data->system;
      new_dos_data->boot = old_dos_data->boot;
      new_dos_data->hidden = old_dos_data->hidden;
      new_dos_data->raid = old_dos_data->raid;
      new_dos_data->lvm = old_dos_data->lvm;
      new_dos_data->lba = old_dos_data->lba;
      new_dos_data->palo = old_dos_data->palo;
      new_dos_data->prep = old_dos_data->prep;

      if (old_dos_data->orig) {
            new_dos_data->orig = ped_malloc (sizeof (OrigState));
            if (!new_dos_data->orig) {
                  ped_partition_destroy (new_part);
                  return NULL;
            }
            new_dos_data->orig->geom = old_dos_data->orig->geom;
            new_dos_data->orig->raw_part = old_dos_data->orig->raw_part;
            new_dos_data->orig->lba_offset = old_dos_data->orig->lba_offset;
      }
      return new_part;
}

static void
msdos_partition_destroy (PedPartition* part)
{
      PED_ASSERT (part != NULL, return);

      if (ped_partition_is_active (part))
            ped_free (part->disk_specific);
      ped_free (part);
}

static int
msdos_partition_set_system (PedPartition* part,
                      const PedFileSystemType* fs_type)
{
      DosPartitionData* dos_data = part->disk_specific;

      part->fs_type = fs_type;

      if (dos_data->hidden
                && fs_type
                && strncmp (fs_type->name, "fat", 3) != 0
                && strcmp (fs_type->name, "ntfs") != 0)
            dos_data->hidden = 0;

      if (part->type & PED_PARTITION_EXTENDED) {
            dos_data->raid = 0;
            dos_data->lvm = 0;
            dos_data->palo = 0;
            dos_data->prep = 0;
            if (dos_data->lba)
                  dos_data->system = PARTITION_EXT_LBA;
            else
                  dos_data->system = PARTITION_EXT;
            return 1;
      }

      if (dos_data->lvm) {
            dos_data->system = PARTITION_LINUX_LVM;
            return 1;
      }
      if (dos_data->raid) {
            dos_data->system = PARTITION_LINUX_RAID;
            return 1;
      }
      if (dos_data->palo) {
            dos_data->system = PARTITION_PALO;
            return 1;
      }
      if (dos_data->prep) {
            dos_data->system = PARTITION_PREP;
            return 1;
      }

      if (!fs_type)
            dos_data->system = PARTITION_LINUX;
      else if (!strcmp (fs_type->name, "fat16")) {
            dos_data->system = dos_data->lba
                           ? PARTITION_FAT16_LBA : PARTITION_FAT16;
            dos_data->system |= dos_data->hidden ? PART_FLAG_HIDDEN : 0;
      } else if (!strcmp (fs_type->name, "fat32")) {
            dos_data->system = dos_data->lba
                           ? PARTITION_FAT32_LBA : PARTITION_FAT32;
            dos_data->system |= dos_data->hidden ? PART_FLAG_HIDDEN : 0;
      } else if (!strcmp (fs_type->name, "ntfs")
               || !strcmp (fs_type->name, "hpfs")) {
            dos_data->system = PARTITION_NTFS;
            dos_data->system |= dos_data->hidden ? PART_FLAG_HIDDEN : 0;
      } else if (!strcmp (fs_type->name, "sun-ufs"))
            dos_data->system = PARTITION_SUN_UFS;
      else if (!strcmp (fs_type->name, "linux-swap"))
            dos_data->system = PARTITION_LINUX_SWAP;
      else
            dos_data->system = PARTITION_LINUX;

      return 1;
}

static int
msdos_partition_set_flag (PedPartition* part, PedPartitionFlag flag, int state)
{
      PedDisk*                disk;
      PedPartition*                 walk;
      DosPartitionData*       dos_data;

      PED_ASSERT (part != NULL, return 0);
      PED_ASSERT (part->disk_specific != NULL, return 0);
      PED_ASSERT (part->disk != NULL, return 0);

      dos_data = part->disk_specific;
      disk = part->disk;

      switch (flag) {
      case PED_PARTITION_HIDDEN:
            if (part->type == PED_PARTITION_EXTENDED) {
                  ped_exception_throw (
                        PED_EXCEPTION_ERROR,
                        PED_EXCEPTION_CANCEL,
                        "Extended partitions can not be hidden on "
                        "msdos disk labels.");
                  return 0;
            }
            dos_data->hidden = state;
            return ped_partition_set_system (part, part->fs_type);

      case PED_PARTITION_BOOT:
            dos_data->boot = state;
            if (!state)
                  return 1;

            walk = ped_disk_next_partition (disk, NULL);
            for (; walk; walk = ped_disk_next_partition (disk, walk)) {
                  if (walk == part || !ped_partition_is_active (walk))
                        continue;
                  msdos_partition_set_flag (walk, PED_PARTITION_BOOT, 0);
            }
            return 1;

      case PED_PARTITION_RAID:
            if (state) {
                  dos_data->hidden = 0;
                  dos_data->lvm = 0;
                  dos_data->palo = 0;
                  dos_data->prep = 0;
            }
            dos_data->raid = state;
            return ped_partition_set_system (part, part->fs_type);

      case PED_PARTITION_LVM:
            if (state) {
                  dos_data->hidden = 0;
                  dos_data->raid = 0;
                  dos_data->palo = 0;
                  dos_data->prep = 0;
            }
            dos_data->lvm = state;
            return ped_partition_set_system (part, part->fs_type);

      case PED_PARTITION_LBA:
            dos_data->lba = state;
            return ped_partition_set_system (part, part->fs_type);

      case PED_PARTITION_PALO:
            if (state) {
                  dos_data->hidden = 0;
                  dos_data->raid = 0;
                  dos_data->lvm = 0;
            }
            dos_data->palo = state;
            return ped_partition_set_system (part, part->fs_type);

      case PED_PARTITION_PREP:
            if (state) {
                  dos_data->hidden = 0;
                  dos_data->raid = 0;
                  dos_data->lvm = 0;
            }
            dos_data->prep = state;
            return ped_partition_set_system (part, part->fs_type);

      default:
            return 0;
      }
}

static int
msdos_partition_get_flag (const PedPartition* part, PedPartitionFlag flag)
{
      DosPartitionData* dos_data;

      PED_ASSERT (part != NULL, return 0);
      PED_ASSERT (part->disk_specific != NULL, return 0);

      dos_data = part->disk_specific;
      switch (flag) {
      case PED_PARTITION_HIDDEN:
            return dos_data->hidden;

      case PED_PARTITION_BOOT:
            return dos_data->boot;

      case PED_PARTITION_RAID:
            return dos_data->raid;

      case PED_PARTITION_LVM:
            return dos_data->lvm;

      case PED_PARTITION_LBA:
            return dos_data->lba;

      case PED_PARTITION_PALO:
            return dos_data->palo;

      case PED_PARTITION_PREP:
            return dos_data->prep;

      default:
            return 0;
      }
}

static int
msdos_partition_is_flag_available (const PedPartition* part,
                           PedPartitionFlag flag)
{
      switch (flag) {
      case PED_PARTITION_HIDDEN:
      case PED_PARTITION_BOOT:
      case PED_PARTITION_RAID:
      case PED_PARTITION_LVM:
      case PED_PARTITION_LBA:
      case PED_PARTITION_PALO:
      case PED_PARTITION_PREP:
            return 1;

      default:
            return 0;
      }
}

static PedGeometry*
_try_constraint (PedPartition* part, const PedConstraint* external,
             PedConstraint* internal)
{
      PedConstraint*          intersection;
      PedGeometry*            solution;

      intersection = ped_constraint_intersect (external, internal);
      ped_constraint_destroy (internal);
      if (!intersection)
            return NULL;

      solution = ped_constraint_solve_nearest (intersection, &part->geom);
      ped_constraint_destroy (intersection);
      return solution;
}

static PedGeometry*
_best_solution (const PedPartition* part, const PedCHSGeometry* bios_geom,
            PedGeometry* a, PedGeometry* b)
{
      PedDevice*  dev = part->disk->dev;
      PedSector   cyl_size = bios_geom->heads * bios_geom->sectors;
      int         a_cylinder;
      int         b_cylinder;

      if (!a)
            return b;
      if (!b)
            return a;

      a_cylinder = a->start / cyl_size;
      b_cylinder = b->start / cyl_size;

      if (a_cylinder == b_cylinder) {
            if ( (a->start / bios_geom->sectors) % bios_geom->heads
                    < (b->start / bios_geom->sectors) % bios_geom->heads)
                        goto choose_a;
            else
                  goto choose_b;
      } else {
            PedSector   a_delta;
            PedSector   b_delta;

            a_delta = abs (part->geom.start - a->start);
            b_delta = abs (part->geom.start - b->start);

            if (a_delta < b_delta)
                  goto choose_a;
            else
                  goto choose_b;
      }

      return NULL;      /* never get here! */

choose_a:
      ped_geometry_destroy (b);
      return a;

choose_b:
      ped_geometry_destroy (a);
      return b;
}

/* This constraint is for "normal" primary partitions, that start at the
 * beginning of a cylinder, and end at the end of a cylinder.
 *    Note: you can't start a partition at the beginning of the 1st
 * cylinder, because that's where the partition table is!  There are different
 * rules for that - see the _primary_start_constraint.
 */
static PedConstraint*
_primary_constraint (PedDisk* disk, const PedCHSGeometry* bios_geom,
                 PedGeometry* min_geom)
{
      PedDevice*  dev = disk->dev;
      PedSector   cylinder_size = bios_geom->sectors * bios_geom->heads;
      PedAlignment      start_align;
      PedAlignment      end_align;
      PedGeometry start_geom;
      PedGeometry end_geom;

      if (!ped_alignment_init (&start_align, 0, cylinder_size))
            return NULL;
      if (!ped_alignment_init (&end_align, -1, cylinder_size))
            return NULL;

      if (min_geom) {
            if (min_geom->start < cylinder_size)
                  return NULL;
            if (!ped_geometry_init (&start_geom, dev, cylinder_size,
                                    min_geom->start + 1 - cylinder_size))
                  return NULL;
            if (!ped_geometry_init (&end_geom, dev, min_geom->end,
                                    dev->length - min_geom->end))
                  return NULL;
      } else {
            if (!ped_geometry_init (&start_geom, dev, cylinder_size,
                                    dev->length - cylinder_size))
                  return NULL;
            if (!ped_geometry_init (&end_geom, dev, 0, dev->length))
                  return NULL;
      }

      return ped_constraint_new (&start_align, &end_align, &start_geom,
                           &end_geom, 1, dev->length);
}

/* This constraint is for partitions starting on the first cylinder.  They
 * must start on the 2nd head of the 1st cylinder.
 */
static PedConstraint*
_primary_start_constraint (PedDisk* disk, const PedCHSGeometry* bios_geom,
                     PedGeometry* min_geom)
{
      PedDevice*  dev = disk->dev;
      PedSector   cylinder_size = bios_geom->sectors * bios_geom->heads;
      PedAlignment      start_align;
      PedAlignment      end_align;
      PedGeometry start_geom;
      PedGeometry end_geom;

      if (!ped_alignment_init (&start_align, bios_geom->sectors, 0))
            return NULL;
      if (!ped_alignment_init (&end_align, -1, cylinder_size))
            return NULL;
      if (min_geom) {
            if (!ped_geometry_init (&start_geom, dev,
                              bios_geom->sectors, 1))
                  return NULL;
            if (!ped_geometry_init (&end_geom, dev, min_geom->end,
                                    dev->length - min_geom->end))
                  return NULL;
      } else {
            if (!ped_geometry_init (&start_geom, dev, bios_geom->sectors,
                              dev->length - bios_geom->sectors))
                  return NULL;
            if (!ped_geometry_init (&end_geom, dev, 0, dev->length))
                  return NULL;
      }

      return ped_constraint_new (&start_align, &end_align, &start_geom,
                           &end_geom, 1, dev->length);
}

/* constraints for logical partitions:
 *    - start_offset is the offset in the start alignment.  "normally",
 * this is bios_geom->sectors.  exceptions: MINOR > 5 at the beginning of the
 * extended partition, or MINOR == 5 in the middle of the extended partition
 *    - is_start_part == 1 if the constraint is for the first cylinder of
 * the extended partition, or == 0 if the constraint is for the second cylinder
 * onwards of the extended partition.
 */
static PedConstraint*
_logical_constraint (PedDisk* disk, const PedCHSGeometry* bios_geom,
                 PedSector start_offset, int is_start_part)
{
      PedPartition*     ext_part = ped_disk_extended_partition (disk);
      PedDevice*  dev = disk->dev;
      PedSector   cylinder_size = bios_geom->sectors * bios_geom->heads;
      PedAlignment      start_align;
      PedAlignment      end_align;
      PedGeometry max_geom;

      PED_ASSERT (ext_part != NULL, return NULL);

      if (!ped_alignment_init (&start_align, start_offset, cylinder_size))
            return NULL;
      if (!ped_alignment_init (&end_align, -1, cylinder_size))
            return NULL;
      if (is_start_part) {
            if (!ped_geometry_init (&max_geom, dev,
                              ext_part->geom.start,
                              ext_part->geom.length))
                  return NULL;
      } else {
            PedSector   min_start;
            PedSector   max_length;

            min_start = ped_round_up_to (ext_part->geom.start + 1,
                                   cylinder_size);
            max_length = ext_part->geom.end - min_start + 1;
            if (min_start >= ext_part->geom.end)
                  return NULL;

            if (!ped_geometry_init (&max_geom, dev, min_start, max_length))
                  return NULL;
      }

      return ped_constraint_new (&start_align, &end_align, &max_geom,
                                 &max_geom, 1, dev->length);
}

/* returns the minimum geometry for the extended partition, given that the
 * extended partition must contain:
 *   * all logical partitions
 *   * all partition tables for all logical partitions (except the first)
 *   * the extended partition table
 */
static PedGeometry*
_get_min_extended_part_geom (const PedPartition* ext_part,
                       const PedCHSGeometry* bios_geom)
{
      PedDisk*          disk = ext_part->disk;
      PedSector         head_size = bios_geom ? bios_geom->sectors : 1;
      PedPartition*           walk;
      PedGeometry*            min_geom;

      walk = ped_disk_get_partition (disk, 5);
      if (!walk)
            return NULL;

      min_geom = ped_geometry_duplicate (&walk->geom);
      ped_geometry_set_start (min_geom, walk->geom.start - 1 * head_size);

      for (walk = ext_part->part_list; walk; walk = walk->next) {
            if (!ped_partition_is_active (walk) || walk->num == 5)
                  continue;
            if (walk->geom.start < min_geom->start)
                  ped_geometry_set_start (min_geom,
                              walk->geom.start - 2 * head_size);
            if (walk->geom.end > min_geom->end)
                  ped_geometry_set_end (min_geom, walk->geom.end);
      }

      return min_geom;
}

static int
_align_primary (PedPartition* part, const PedCHSGeometry* bios_geom,
            const PedConstraint* constraint)
{
      PedDisk*    disk = part->disk;
      PedDevice*  dev = disk->dev;
      PedGeometry*      min_geom = NULL;
      PedGeometry*      solution = NULL;

      if (part->type == PED_PARTITION_EXTENDED)
            min_geom = _get_min_extended_part_geom (part, bios_geom);

      solution = _best_solution (part, bios_geom, solution,
                  _try_constraint (part, constraint,
                               _primary_start_constraint (disk,
                                     bios_geom, min_geom)));
      solution = _best_solution (part, bios_geom, solution,
                  _try_constraint (part, constraint,
                               _primary_constraint (disk, bios_geom,
                                     min_geom)));

      if (min_geom)
            ped_geometry_destroy (min_geom);

      if (solution) {
            ped_geometry_set (&part->geom, solution->start,
                          solution->length);
            ped_geometry_destroy (solution);
            return 1;
      }

      return 0;
}

static int
_logical_min_start_head (PedPartition* part, const PedCHSGeometry* bios_geom,
                   PedPartition* ext_part, int is_start_ext_part)
{
      PedDevice*  dev = part->disk->dev;
      PedSector   cylinder_size = bios_geom->sectors * bios_geom->heads;
      PedSector   base_head;

      if (is_start_ext_part)
            base_head = 1 + (ext_part->geom.start % cylinder_size)
                              / bios_geom->sectors;
      else
            base_head = 0;

      if (part->num == 5)
            return base_head + 0;
      else
            return base_head + 1;
}

static int
_align_logical (PedPartition* part, const PedCHSGeometry* bios_geom,
            const PedConstraint* constraint)
{
      PedDisk*    disk = part->disk;
      PedDevice*  dev = disk->dev;
      PedPartition*     ext_part = ped_disk_extended_partition (disk);
      PedSector   cyl_size = bios_geom->sectors * bios_geom->heads;
      PedSector   start_base;
      int         head;
      PedGeometry*      solution = NULL;

      PED_ASSERT (ext_part != NULL, return 0);

      start_base = ped_round_down_to (part->geom.start, cyl_size);

      for (head = _logical_min_start_head (part, bios_geom, ext_part, 0);
           head < PED_MIN (5, bios_geom->heads); head++) {
            PedConstraint*    disk_constraint;
            PedSector   start = start_base + head * bios_geom->sectors;

            if (head >= _logical_min_start_head (part, bios_geom,
                                         ext_part, 1))
                  disk_constraint =
                        _logical_constraint (disk, bios_geom, start, 1);
            else
                  disk_constraint =
                        _logical_constraint (disk, bios_geom, start, 0);

            solution = _best_solution (part, bios_geom, solution,
                        _try_constraint (part, constraint,
                                     disk_constraint));
      }

      if (solution) {
            ped_geometry_set (&part->geom, solution->start,
                          solution->length);
            ped_geometry_destroy (solution);
            return 1;
      }

      return 0;
}

static int
_align (PedPartition* part, const PedCHSGeometry* bios_geom,
      const PedConstraint* constraint)
{
      if (part->type == PED_PARTITION_LOGICAL)
            return _align_logical (part, bios_geom, constraint);
      else
            return _align_primary (part, bios_geom, constraint);
}

static PedConstraint*
_no_geom_constraint (PedDisk* disk, PedSector start, PedSector end)
{
      PedGeometry  max;

      ped_geometry_init (&max, disk->dev, start, end - start + 1);
      return ped_constraint_new_from_max (&max);
}

static PedConstraint*
_no_geom_extended_constraint (PedPartition* part)
{
      PedDevice*  dev = part->disk->dev;
      PedGeometry*      min = _get_min_extended_part_geom (part, NULL);
      PedGeometry start_range;
      PedGeometry end_range;
      PedConstraint*    constraint;

      if (min) {
            ped_geometry_init (&start_range, dev, 1, min->start);
            ped_geometry_init (&end_range, dev, min->end,
                           dev->length - min->end);
            ped_geometry_destroy (min);
      } else {
            ped_geometry_init (&start_range, dev, 1, dev->length - 1);
            ped_geometry_init (&end_range, dev, 1, dev->length - 1);
      }
      constraint = ped_constraint_new (ped_alignment_any, ped_alignment_any,
                  &start_range, &end_range, 1, dev->length);
      return constraint;
}

static int
_align_primary_no_geom (PedPartition* part, const PedConstraint* constraint)
{
      PedDisk*    disk = part->disk;
      PedGeometry*      solution;

      if (part->type == PED_PARTITION_EXTENDED) {
            solution = _try_constraint (part, constraint,
                        _no_geom_extended_constraint (part));
      } else {
            solution = _try_constraint (part, constraint,
                        _no_geom_constraint (disk, 1,
                                         disk->dev->length - 1));
      }

      if (solution) {
            ped_geometry_set (&part->geom, solution->start,
                          solution->length);
            ped_geometry_destroy (solution);
            return 1;
      }
      return 0;
}

static PedSector
_calc_min_logical_start (PedPartition* part)
{
      PedDisk*    disk = part->disk;
      PedPartition*     ext_part = ped_disk_extended_partition (disk);
      PedPartition*     walk;

      for (walk = ext_part->part_list; walk && walk != part;
           walk = walk->next) {
            if (walk->geom.end > part->geom.start) {
                  if (walk->prev)
                        return walk->prev->geom.end + 2;
                  break;
            }
      }

      if (part->num == 5)
            return ext_part->geom.start + 1;
      else
            return ext_part->geom.start + 2;
}

static int
_align_logical_no_geom (PedPartition* part, const PedConstraint* constraint)
{
      PedDisk*    disk = part->disk;
      PedPartition*     ext_part = ped_disk_extended_partition (disk);
      PedSector   min_start = _calc_min_logical_start (part);
      PedGeometry*      solution;

      solution = _try_constraint (part, constraint,
                  _no_geom_constraint (disk, min_start,
                                   ext_part->geom.end));

      if (solution) {
            ped_geometry_set (&part->geom, solution->start,
                          solution->length);
            ped_geometry_destroy (solution);
            return 1;
      }
      return 0;
}

static int
_align_no_geom (PedPartition* part, const PedConstraint* constraint)
{
      if (part->type == PED_PARTITION_LOGICAL)
            return _align_logical_no_geom (part, constraint);
      else
            return _align_primary_no_geom (part, constraint);
}

static int
msdos_partition_align (PedPartition* part, const PedConstraint* constraint)
{
      PedCHSGeometry    bios_geom;
      DosPartitionData* dos_data;

      PED_ASSERT (part != NULL, return 0);
      PED_ASSERT (part->disk_specific != NULL, return 0);

      dos_data = part->disk_specific;
      if (dos_data->system == PARTITION_LDM && dos_data->orig) {
            PedGeometry *orig_geom = &dos_data->orig->geom;

            if (ped_geometry_test_equal (&part->geom, orig_geom)
                && ped_constraint_is_solution (constraint, &part->geom))
                  return 1;

            ped_geometry_set (&part->geom, orig_geom->start,
                          orig_geom->length);
            ped_exception_throw (
                  PED_EXCEPTION_ERROR,
                  PED_EXCEPTION_CANCEL,
                  _("Parted can't resize partitions managed by "
                    "Windows Dynamic Disk."));
            return 0;
      }

      partition_probe_bios_geometry (part, &bios_geom);

      if (_align (part, &bios_geom, constraint))
            return 1;
      if (_align_no_geom (part, constraint))
            return 1;
 
#ifndef DISCOVER_ONLY
      ped_exception_throw (
            PED_EXCEPTION_ERROR,
            PED_EXCEPTION_CANCEL,
            _("Unable to satisfy all constraints on the partition."));
#endif
      return 0;
}

static int
add_metadata_part (PedDisk* disk, PedPartitionType type, PedSector start,
               PedSector end)
{
      PedPartition*           new_part;

      PED_ASSERT (disk != NULL, return 0);

      new_part = ped_partition_new (disk, type | PED_PARTITION_METADATA, NULL,
                              start, end);
      if (!new_part)
            goto error;
      if (!ped_disk_add_partition (disk, new_part, NULL))
            goto error_destroy_new_part;

      return 1;

error_destroy_new_part:
      ped_partition_destroy (new_part);
error:
      return 0;
}

/* There are a few objectives here:
 *    - avoid having lots of "free space" partitions lying around, to confuse
 * the front end.
 *    - ensure that there's enough room to put in the extended partition
 * tables, etc.
 */
static int
add_logical_part_metadata (PedDisk* disk, PedPartition* log_part)
{
      PedPartition*     ext_part = ped_disk_extended_partition (disk);
      PedPartition*     prev = log_part->prev;
      PedDevice*  dev = disk->dev;
      PedCHSGeometry    bios_geom;
      PedSector   cyl_size;
      PedSector   metadata_start;
      PedSector   metadata_end;
      PedSector   metadata_length;

      partition_probe_bios_geometry (ext_part, &bios_geom);
      cyl_size = bios_geom.sectors * bios_geom.heads;

      /* if there's metadata shortly before the partition (on the same
       * cylinder), then make this new metadata partition touch the end of
       * the other.  No point having 63 bytes (or whatever) of free space
       * partition - just confuses front-ends, etc.
       *    Otherwise, start the metadata at the start of the cylinder
       */

      metadata_end = log_part->geom.start - 1;
      metadata_start = ped_round_down_to (metadata_end, cyl_size);
      if (prev)
            metadata_start = PED_MAX (metadata_start, prev->geom.end + 1);
      else
            metadata_start = PED_MAX (metadata_start,
                                ext_part->geom.start + 1);
      metadata_length = metadata_end - metadata_start + 1;

      /* partition 5 doesn't need to have any metadata */
      if (log_part->num == 5 && metadata_length < bios_geom.sectors)
            return 1;

      PED_ASSERT (metadata_length > 0, return 0);

      return add_metadata_part (disk, PED_PARTITION_LOGICAL,
                          metadata_start, metadata_end);
}

static PedPartition*
get_last_part (PedDisk* disk)
{
      PedPartition* first_part = disk->part_list;
      PedPartition* walk;

      if (!first_part)
            return NULL;
      for (walk = first_part; walk->next; walk = walk->next);
      return walk;
}

/* Adds metadata placeholder partitions to cover the partition table (and
 * "free" space after it that often has bootloader stuff), and the last
 * incomplete cylinder at the end of the disk.
 *    Parted has to be mindful of the uncertainty of dev->bios_geom.
 * It therefore makes sure this metadata doesn't overlap with partitions.
 */
static int
add_startend_metadata (PedDisk* disk)
{
      PedDevice* dev = disk->dev;
      PedSector cyl_size = dev->bios_geom.sectors * dev->bios_geom.heads;
      PedPartition* first_part = disk->part_list;
      PedPartition* last_part = get_last_part (disk);
      PedSector start, end;

      if (!first_part)
            return 1;

      start = 0;
      end = PED_MIN (dev->bios_geom.sectors - 1, first_part->geom.start - 1);
      if (!add_metadata_part (disk, PED_PARTITION_NORMAL, start, end))
            return 0;

      start = PED_MAX (last_part->geom.end + 1,
                   ped_round_down_to (dev->length, cyl_size));
      end = dev->length - 1;
      if (start < end) {
            if (!add_metadata_part (disk, PED_PARTITION_NORMAL, start, end))
                  return 0;
      }

      return 1;
}

static int
msdos_alloc_metadata (PedDisk* disk)
{
      PedPartition*           ext_part;

      PED_ASSERT (disk != NULL, return 0);
      PED_ASSERT (disk->dev != NULL, return 0);

      if (!add_startend_metadata (disk))
            return 0;

      ext_part = ped_disk_extended_partition (disk);
      if (ext_part) {
            int         i;
            PedSector   start, end;
            PedCHSGeometry    bios_geom;
            
            for (i=5; 1; i++) {
                  PedPartition* log_part;
                  log_part = ped_disk_get_partition (disk, i);
                  if (!log_part)
                        break;
                  if (!add_logical_part_metadata (disk, log_part))
                        return 0;
            }

            partition_probe_bios_geometry (ext_part, &bios_geom);
            start = ext_part->geom.start;
            end = start + bios_geom.sectors - 1;
            if (ext_part->part_list)
                  end = PED_MIN (end,
                               ext_part->part_list->geom.start - 1);
            if (!add_metadata_part (disk, PED_PARTITION_LOGICAL,
                              start, end))
                  return 0;
      }

      return 1;
}

static int
next_primary (PedDisk* disk)
{
      int   i;
      for (i=1; i<=4; i++) {
            if (!ped_disk_get_partition (disk, i))
                  return i;
      }
      return 0;
}

static int
next_logical (PedDisk* disk)
{
      int   i;
      for (i=5; 1; i++) {
            if (!ped_disk_get_partition (disk, i))
                  return i;
      }
}

static int
msdos_partition_enumerate (PedPartition* part)
{
      PED_ASSERT (part != NULL, return 0);
      PED_ASSERT (part->disk != NULL, return 0);

      /* don't re-number a primary partition */
      if (part->num != -1 && part->num <= 4)
            return 1;

      part->num = -1;

      if (part->type & PED_PARTITION_LOGICAL)
            part->num = next_logical (part->disk);
      else
            part->num = next_primary (part->disk);

      return 1;
}

static int
msdos_get_max_primary_partition_count (const PedDisk* disk)
{
      return 4;
}

static PedDiskOps msdos_disk_ops = {
      probe:                  msdos_probe,
#ifndef DISCOVER_ONLY
      clobber:          msdos_clobber,
#else
      clobber:          NULL,
#endif
      alloc:                  msdos_alloc,
      duplicate:        msdos_duplicate,
      free:             msdos_free,
      read:             msdos_read,
#ifndef DISCOVER_ONLY
      write:                  msdos_write,
#else
      write:                  NULL,
#endif

      partition_new:          msdos_partition_new,
      partition_duplicate:    msdos_partition_duplicate,
      partition_destroy:      msdos_partition_destroy,
      partition_set_system:   msdos_partition_set_system,
      partition_set_flag:     msdos_partition_set_flag,
      partition_get_flag:     msdos_partition_get_flag,
      partition_is_flag_available:  msdos_partition_is_flag_available,
      partition_set_name:     NULL,
      partition_get_name:     NULL,
      partition_align:  msdos_partition_align,
      partition_enumerate:    msdos_partition_enumerate,

      alloc_metadata:         msdos_alloc_metadata,
      get_max_primary_partition_count:
                        msdos_get_max_primary_partition_count
};

static PedDiskType msdos_disk_type = {
      next:       NULL,
      name:       "msdos",
      ops:        &msdos_disk_ops,
      features:   PED_DISK_TYPE_EXTENDED
};

void
ped_disk_msdos_init ()
{
      PED_ASSERT (sizeof (DosRawPartition) == 16, return);
      PED_ASSERT (sizeof (DosRawTable) == 512, return);

      ped_register_disk_type (&msdos_disk_type);
}

void
ped_disk_msdos_done ()
{
      ped_unregister_disk_type (&msdos_disk_type);
}


Generated by  Doxygen 1.6.0   Back to index