Index: uspace/lib/fdisk/src/fdisk.c
===================================================================
--- uspace/lib/fdisk/src/fdisk.c	(revision 6bc542bfcd4de3d747e25cc6e0894f9581445ca1)
+++ uspace/lib/fdisk/src/fdisk.c	(revision 99c23405e687595401687deb42d610a45b2fa761)
@@ -671,5 +671,5 @@
 		if (part->index > nidx)
 			break;
-		nidx = part->index;
+		nidx = part->index + 1;
 		link = list_next(link, &dev->parts_idx);
 	}
Index: uspace/lib/label/include/types/liblabel.h
===================================================================
--- uspace/lib/label/include/types/liblabel.h	(revision 6bc542bfcd4de3d747e25cc6e0894f9581445ca1)
+++ uspace/lib/label/include/types/liblabel.h	(revision 99c23405e687595401687deb42d610a45b2fa761)
@@ -94,4 +94,6 @@
 	/** Number of blocks */
 	aoff64_t nblocks;
+	/** Partition type */
+	uint64_t ptype;
 };
 
@@ -108,4 +110,12 @@
 };
 
+typedef struct {
+	uint64_t ptable_ba[2];
+	size_t esize;
+} label_gpt_t;
+
+typedef struct {
+} label_mbr_t;
+
 /** Label instance */
 struct label {
@@ -114,4 +124,6 @@
 	/** Label type */
 	label_type_t ltype;
+	/** Block device service ID */
+	service_id_t svcid;
 	/** Partitions */
 	list_t parts; /* of label_part_t */
@@ -120,4 +132,12 @@
 	/** Number of blocks that can be allocated */
 	aoff64_t anblocks;
+	/** Number of primary partition entries */
+	int pri_entries;
+	/** Block size */
+	size_t block_size;
+	union {
+		label_gpt_t gpt;
+		label_mbr_t mbr;
+	} lt;
 };
 
Index: uspace/lib/label/src/gpt.c
===================================================================
--- uspace/lib/label/src/gpt.c	(revision 6bc542bfcd4de3d747e25cc6e0894f9581445ca1)
+++ uspace/lib/label/src/gpt.c	(revision 99c23405e687595401687deb42d610a45b2fa761)
@@ -54,5 +54,8 @@
 static int gpt_part_destroy(label_part_t *);
 
+static void gpt_unused_pte(gpt_entry_t *);
+static int gpt_part_to_pte(label_part_t *, gpt_entry_t *);
 static int gpt_pte_to_part(label_t *, gpt_entry_t *, int);
+static int gpt_pte_update(label_t *, gpt_entry_t *, int);
 
 const uint8_t efi_signature[8] = {
@@ -77,5 +80,5 @@
 {
 	label_t *label = NULL;
-	gpt_header_t *gpt_hdr = NULL;
+	gpt_header_t *gpt_hdr[2];
 	gpt_entry_t *eptr;
 	uint8_t *etable = NULL;
@@ -84,10 +87,14 @@
 	uint32_t esize;
 	uint32_t bcnt;
-	uint64_t ba;
+	uint64_t ptba[2];
+	uint64_t h1ba;
 	uint32_t entry;
 	uint64_t ba_min, ba_max;
-	int i;
+	int i, j;
 	int rc;
 
+	gpt_hdr[0] = NULL;
+	gpt_hdr[1] = NULL;
+
 	rc = block_get_bsize(sid, &bsize);
 	if (rc != EOK) {
@@ -101,11 +108,25 @@
 	}
 
-	gpt_hdr = calloc(1, bsize);
-	if (gpt_hdr == NULL) {
+	gpt_hdr[0] = calloc(1, bsize);
+	if (gpt_hdr[0] == NULL) {
 		rc = ENOMEM;
 		goto error;
 	}
 
-	rc = block_read_direct(sid, GPT_HDR_BA, 1, gpt_hdr);
+	gpt_hdr[1] = calloc(1, bsize);
+	if (gpt_hdr[1] == NULL) {
+		rc = ENOMEM;
+		goto error;
+	}
+
+	rc = block_read_direct(sid, GPT_HDR_BA, 1, gpt_hdr[0]);
+	if (rc != EOK) {
+		rc = EIO;
+		goto error;
+	}
+
+	h1ba = uint64_t_le2host(gpt_hdr[0]->alternate_lba);
+
+	rc = block_read_direct(sid, h1ba, 1, gpt_hdr[1]);
 	if (rc != EOK) {
 		rc = EIO;
@@ -119,17 +140,20 @@
 	list_initialize(&label->parts);
 
-	for (i = 0; i < 8; ++i) {
-		if (gpt_hdr->efi_signature[i] != efi_signature[i]) {
-			rc = EINVAL;
-			goto error;
+	for (j = 0; j < 2; j++) {
+		for (i = 0; i < 8; ++i) {
+			if (gpt_hdr[j]->efi_signature[i] != efi_signature[i]) {
+				rc = EINVAL;
+				goto error;
+			}
 		}
 	}
 
-	num_entries = uint32_t_le2host(gpt_hdr->num_entries);
-	esize = uint32_t_le2host(gpt_hdr->entry_size);
+	num_entries = uint32_t_le2host(gpt_hdr[0]->num_entries);
+	esize = uint32_t_le2host(gpt_hdr[0]->entry_size);
 	bcnt = (num_entries + esize - 1) / esize;
-	ba = uint64_t_le2host(gpt_hdr->entry_lba);
-	ba_min = uint64_t_le2host(gpt_hdr->first_usable_lba);
-	ba_max = uint64_t_le2host(gpt_hdr->last_usable_lba);
+	ptba[0] = uint64_t_le2host(gpt_hdr[0]->entry_lba);
+	ptba[1] = uint64_t_le2host(gpt_hdr[1]->entry_lba);
+	ba_min = uint64_t_le2host(gpt_hdr[0]->first_usable_lba);
+	ba_max = uint64_t_le2host(gpt_hdr[0]->last_usable_lba);
 
 	if (num_entries < 1) {
@@ -154,5 +178,5 @@
 	}
 
-	rc = block_read_direct(sid, ba, bcnt, etable);
+	rc = block_read_direct(sid, ptba[0], bcnt, etable);
 	if (rc != EOK) {
 		rc = EIO;
@@ -169,16 +193,27 @@
 	free(etable);
 	etable = NULL;
-	free(gpt_hdr);
-	gpt_hdr = NULL;
+	free(gpt_hdr[0]);
+	gpt_hdr[0] = NULL;
+	free(gpt_hdr[1]);
+	gpt_hdr[1] = NULL;
 
 	label->ops = &gpt_label_ops;
 	label->ltype = lt_gpt;
+	label->svcid = sid;
 	label->ablock0 = ba_min;
 	label->anblocks = ba_max - ba_min + 1;
+	label->pri_entries = num_entries;
+	label->block_size = bsize;
+
+	label->lt.gpt.ptable_ba[0] = ptba[0];
+	label->lt.gpt.ptable_ba[1] = ptba[1];
+	label->lt.gpt.esize = esize;
+
 	*rlabel = label;
 	return EOK;
 error:
 	free(etable);
-	free(gpt_hdr);
+	free(gpt_hdr[0]);
+	free(gpt_hdr[1]);
 	free(label);
 	return rc;
@@ -243,27 +278,90 @@
 {
 	label_part_t *part;
+	gpt_entry_t pte;
+	int rc;
 
 	part = calloc(1, sizeof(label_part_t));
-	if (part == NULL)
-		return ENOMEM;
+	if (part == NULL) {
+		rc = ENOMEM;
+		goto error;
+	}
 
 	/* XXX Verify index, block0, nblocks */
 
+	if (pspec->index < 1 || pspec->index > label->pri_entries) {
+		rc = EINVAL;
+		goto error;
+	}
+
+	/* XXX Check if index is used */
+
+	part->label = label;
 	part->index = pspec->index;
 	part->block0 = pspec->block0;
 	part->nblocks = pspec->nblocks;
-
-	/* XXX Modify partition table */
-
-	part->label = label;
+	part->ptype = pspec->ptype;
+
+	/* Prepare partition table entry */
+	rc = gpt_part_to_pte(part, &pte);
+	if (rc != EOK) {
+		rc = EINVAL;
+		goto error;
+	}
+
+	/* Modify partition tables */
+	rc = gpt_pte_update(label, &pte, pspec->index - 1);
+	if (rc != EOK) {
+		rc = EIO;
+		goto error;
+	}
+
 	list_append(&part->llabel, &label->parts);
 
 	*rpart = part;
 	return EOK;
+error:
+	free(part);
+	return rc;
 }
 
 static int gpt_part_destroy(label_part_t *part)
 {
-	return ENOTSUP;
+	gpt_entry_t pte;
+	int rc;
+
+	/* Prepare unused partition table entry */
+	gpt_unused_pte(&pte);
+
+	/* Modify partition tables */
+	rc = gpt_pte_update(part->label, &pte, part->index - 1);
+	if (rc != EOK)
+		return EIO;
+
+	list_remove(&part->llabel);
+	free(part);
+	return EOK;
+}
+
+static void gpt_unused_pte(gpt_entry_t *pte)
+{
+	memset(pte, 0, sizeof(gpt_entry_t));
+}
+
+static int gpt_part_to_pte(label_part_t *part, gpt_entry_t *pte)
+{
+	uint64_t eblock;
+
+	eblock = part->block0 + part->nblocks - 1;
+	if (eblock < part->block0)
+		return EINVAL;
+
+	memset(pte, 0, sizeof(gpt_entry_t));
+	pte->part_type[0] = 0x12;
+	pte->part_id[0] = 0x34;
+	pte->start_lba = host2uint64_t_le(part->block0);
+	pte->end_lba = host2uint64_t_le(eblock);
+//	pte->attributes
+//	pte->part_name
+	return EOK;
 }
 
@@ -301,4 +399,55 @@
 }
 
+/** Update partition table entry at specified index.
+ *
+ * Replace partition entry at index @a index with the contents of
+ * @a pte.
+ */
+static int gpt_pte_update(label_t *label, gpt_entry_t *pte, int index)
+{
+	size_t pos;
+	size_t offs;
+	uint64_t ba;
+	uint8_t *buf;
+	gpt_entry_t *e;
+	int i;
+	int rc;
+
+	pos = index * label->lt.gpt.esize;
+	offs = pos % label->block_size;
+
+	buf = calloc(1, label->block_size);
+	if (buf == NULL)
+		return ENOMEM;
+
+	/* For both partition tables: read, modify, write */
+	for (i = 0; i < 2; i++) {
+		ba = label->lt.gpt.ptable_ba[i] +
+		    pos / label->block_size;
+
+		rc = block_read_direct(label->svcid, ba, 1, buf);
+		if (rc != EOK) {
+			rc = EIO;
+			goto error;
+		}
+
+		/* Replace single entry */
+		e = (gpt_entry_t *)(&buf[offs]);
+		*e = *pte;
+
+		rc = block_write_direct(label->svcid, ba, 1, buf);
+		if (rc != EOK) {
+			rc = EIO;
+			goto error;
+		}
+	}
+
+	free(buf);
+	return EOK;
+error:
+	free(buf);
+	return rc;
+}
+
 /** @}
  */
Index: uspace/lib/label/src/mbr.c
===================================================================
--- uspace/lib/label/src/mbr.c	(revision 6bc542bfcd4de3d747e25cc6e0894f9581445ca1)
+++ uspace/lib/label/src/mbr.c	(revision 99c23405e687595401687deb42d610a45b2fa761)
@@ -54,5 +54,8 @@
 static int mbr_part_destroy(label_part_t *);
 
+static void mbr_unused_pte(mbr_pte_t *);
+static int mbr_part_to_pte(label_part_t *, mbr_pte_t *);
 static int mbr_pte_to_part(label_t *, mbr_pte_t *, int);
+static int mbr_pte_update(label_t *, mbr_pte_t *, int);
 
 label_ops_t mbr_label_ops = {
@@ -141,4 +144,5 @@
 	label->ablock0 = mbr_ablock0;
 	label->anblocks = nblocks - mbr_ablock0;
+	label->pri_entries = mbr_nprimary;
 	*rlabel = label;
 	return EOK;
@@ -207,4 +211,6 @@
 {
 	label_part_t *part;
+	mbr_pte_t pte;
+	int rc;
 
 	part = calloc(1, sizeof(label_part_t));
@@ -212,17 +218,77 @@
 		return ENOMEM;
 
+	/* XXX Verify index, block0, nblocks */
+
+	if (pspec->index < 1 || pspec->index > label->pri_entries) {
+		rc = EINVAL;
+		goto error;
+	}
+
+	/* XXX Check if index is used */
+
+	part->label = label;
 	part->index = pspec->index;
 	part->block0 = pspec->block0;
 	part->nblocks = pspec->nblocks;
-
-	part->label = label;
+	part->ptype = pspec->ptype;
+
+	rc = mbr_part_to_pte(part, &pte);
+	if (rc != EOK) {
+		rc = EINVAL;
+		goto error;
+	}
+
+	rc = mbr_pte_update(label, &pte, pspec->index - 1);
+	if (rc != EOK) {
+		rc = EIO;
+		goto error;
+	}
+
+	list_append(&part->llabel, &label->parts);
 
 	*rpart = part;
 	return EOK;
+error:
+	free(part);
+	return rc;
 }
 
 static int mbr_part_destroy(label_part_t *part)
 {
-	return ENOTSUP;
+	mbr_pte_t pte;
+	int rc;
+
+	/* Prepare unused partition table entry */
+	mbr_unused_pte(&pte);
+
+	/* Modify partition table */
+	rc = mbr_pte_update(part->label, &pte, part->index - 1);
+	if (rc != EOK)
+		return EIO;
+
+	list_remove(&part->llabel);
+	free(part);
+	return EOK;
+}
+
+static void mbr_unused_pte(mbr_pte_t *pte)
+{
+	memset(pte, 0, sizeof(mbr_pte_t));
+}
+
+static int mbr_part_to_pte(label_part_t *part, mbr_pte_t *pte)
+{
+	if ((part->block0 >> 32) != 0)
+		return EINVAL;
+	if ((part->nblocks >> 32) != 0)
+		return EINVAL;
+	if ((part->ptype >> 8) != 0)
+		return EINVAL;
+
+	memset(pte, 0, sizeof(mbr_pte_t));
+	pte->ptype = part->ptype;
+	pte->first_lba = host2uint32_t_le(part->block0);
+	pte->length = host2uint32_t_le(part->nblocks);
+	return EOK;
 }
 
@@ -260,4 +326,39 @@
 }
 
+/** Update partition table entry at specified index.
+ *
+ * Replace partition entry at index @a index with the contents of
+ * @a pte.
+ */
+static int mbr_pte_update(label_t *label, mbr_pte_t *pte, int index)
+{
+	mbr_br_block_t *br;
+	int rc;
+
+	br = calloc(1, label->block_size);
+	if (br == NULL)
+		return ENOMEM;
+
+	rc = block_read_direct(label->svcid, mbr_ba, 1, br);
+	if (rc != EOK) {
+		rc = EIO;
+		goto error;
+	}
+
+	br->pte[index] = *pte;
+
+	rc = block_write_direct(label->svcid, mbr_ba, 1, br);
+	if (rc != EOK) {
+		rc = EIO;
+		goto error;
+	}
+
+	free(br);
+	return EOK;
+error:
+	free(br);
+	return rc;
+}
+
 /** @}
  */
Index: uspace/srv/bd/vbd/disk.c
===================================================================
--- uspace/srv/bd/vbd/disk.c	(revision 6bc542bfcd4de3d747e25cc6e0894f9581445ca1)
+++ uspace/srv/bd/vbd/disk.c	(revision 99c23405e687595401687deb42d610a45b2fa761)
@@ -112,4 +112,5 @@
 }
 
+/** Add partition to our inventory based on liblabel partition structure */
 static int vbds_part_add(vbds_disk_t *disk, label_part_t *lpart,
     vbds_part_t **rpart)
@@ -119,5 +120,4 @@
 	label_part_info_t lpinfo;
 	char *name;
-	int pno;
 	int rc;
 
@@ -132,6 +132,5 @@
 
 	/* XXX Proper service name */
-	pno = list_count(&disk->parts);
-	rc = asprintf(&name, "%sp%u", disk->svc_name, pno);
+	rc = asprintf(&name, "%sp%u", disk->svc_name, lpart->index);
 	if (rc < 0) {
 		log_msg(LOG_DEFAULT, LVL_ERROR, "Out of memory.");
@@ -166,4 +165,32 @@
 	if (rpart != NULL)
 		*rpart = part;
+	return EOK;
+}
+
+/** Remove partition from our inventory leaving only the underlying liblabel
+ * partition structure.
+ */
+static int vbds_part_remove(vbds_part_t *part, label_part_t **rlpart)
+{
+	label_part_t *lpart;
+	int rc;
+
+	log_msg(LOG_DEFAULT, LVL_NOTE, "vbds_part_remove(%p)", part);
+
+	lpart = part->lpart;
+
+	if (part->open_cnt > 0)
+		return EBUSY;
+
+	rc = loc_service_unregister((service_id_t)part->id);
+	if (rc != EOK)
+		return EIO;
+
+	list_remove(&part->ldisk);
+	list_remove(&part->lparts);
+	free(part);
+
+	if (rlpart != NULL)
+		*rlpart = lpart;
 	return EOK;
 }
@@ -442,4 +469,6 @@
 {
 	vbds_part_t *part;
+	vbds_disk_t *disk;
+	label_part_t *lpart;
 	int rc;
 
@@ -448,11 +477,22 @@
 		return rc;
 
-	rc = label_part_destroy(part->lpart);
-	if (rc != EOK)
-		return rc;
-
-	list_remove(&part->ldisk);
-	list_remove(&part->lparts);
-	free(part);
+	disk = part->disk;
+
+	rc = vbds_part_remove(part, &lpart);
+	if (rc != EOK)
+		return rc;
+
+	rc = label_part_destroy(lpart);
+	if (rc != EOK) {
+		log_msg(LOG_DEFAULT, LVL_ERROR, "Failed deleting partition");
+
+		/* Try rolling back */
+		rc = vbds_part_add(disk, lpart, NULL);
+		if (rc != EOK)
+			log_msg(LOG_DEFAULT, LVL_ERROR, "Failed rolling back.");
+
+		return EIO;
+	}
+
 	return EOK;
 }
