libfdisk/src/table.c

   1
   2 #include "fdiskP.h"
   3
   4 /**
   5  * fdisk_new_table:
   6  *
   7  * The table is a container for struct fdisk_partition entries. The container
   8  * does not have any real connection with label (partition table) and with
   9  * real on-disk data.
  10  *
  11  * Returns: newly allocated table struct.
  12  */
  13 struct fdisk_table *fdisk_new_table(void)
  14 {
  15         struct fdisk_table *tb = NULL;
  16
  17         tb = calloc(1, sizeof(*tb));
  18         if (!tb)
  19                 return NULL;
  20
  21         DBG(TAB, ul_debugobj(tb, "alloc"));
  22         tb->refcount = 1;
  23         INIT_LIST_HEAD(&tb->parts);
  24         return tb;
  25 }
  26
  27 /**
  28  * fdisk_reset_table:
  29  * @tb: tab pointer
  30  *
  31  * Removes all entries (filesystems) from the table. The filesystems with zero
  32  * reference count will be deallocated.
  33  *
  34  * Returns: 0 on success or negative number in case of error.
  35  */
  36 int fdisk_reset_table(struct fdisk_table *tb)
  37 {
  38         if (!tb)
  39                 return -EINVAL;
  40
  41         DBG(TAB, ul_debugobj(tb, "reset"));
  42
  43         while (!list_empty(&tb->parts)) {
  44                 struct fdisk_partition *pa = list_entry(tb->parts.next,
  45                                                   struct fdisk_partition, parts);
  46                 fdisk_table_remove_partition(tb, pa);
  47         }
  48
  49         tb->nents = 0;
  50         return 0;
  51 }
  52
  53 /**
  54  * fdisk_ref_table:
  55  * @tb: table pointer
  56  *
  57  * Incremparts reference counter.
  58  */
  59 void fdisk_ref_table(struct fdisk_table *tb)
  60 {
  61         if (tb)
  62                 tb->refcount++;
  63 }
  64
  65 /**
  66  * fdisk_unref_table:
  67  * @tb: table pointer
  68  *
  69  * De-incremparts reference counter, on zero the @tb is automatically
  70  * deallocated by fdisk_free_table().
  71  */
  72 void fdisk_unref_table(struct fdisk_table *tb)
  73 {
  74         if (!tb)
  75                 return;
  76
  77         tb->refcount--;
  78         if (tb->refcount <= 0) {
  79                 fdisk_reset_table(tb);
  80
  81                 DBG(TAB, ul_debugobj(tb, "free"));
  82                 free(tb);
  83         }
  84 }
  85
  86 /**
  87  * fdisk_table_is_empty:
  88  * @tb: pointer to tab
  89  *
  90  * Returns: 1 if the table is without filesystems, or 0.
  91  */
  92 int fdisk_table_is_empty(struct fdisk_table *tb)
  93 {
  94         assert(tb);
  95         return tb == NULL || list_empty(&tb->parts) ? 1 : 0;
  96 }
  97
  98 /**
  99  * fdisk_table_get_nents:
 100  * @tb: pointer to tab
 101  *
 102  * Returns: number of entries in table.
 103  */
 104 int fdisk_table_get_nents(struct fdisk_table *tb)
 105 {
 106         return tb ? tb->nents : 0;
 107 }
 108
 109 /**
 110  * fdisk_table_next_partition:
 111  * @tb: tab pointer
 112  * @itr: iterator
 113  * @pa: returns the next tab entry
 114  *
 115  * Returns: 0 on success, negative number in case of error or 1 at the end of list.
 116  *
 117  * Example:
 118  * <informalexample>
 119  *   <programlisting>
 120  *      while(fdisk_table_next_partition(tb, itr, &pa) == 0) {
 121  *              ...
 122  *      }
 123  *   </programlisting>
 124  * </informalexample>
 125  */
 126 int fdisk_table_next_partition(
 127                         struct fdisk_table *tb,
 128                         struct fdisk_iter *itr,
 129                         struct fdisk_partition **pa)
 130 {
 131         int rc = 1;
 132
 133         assert(tb);
 134         assert(itr);
 135         assert(pa);
 136
 137         if (!tb || !itr || !pa)
 138                 return -EINVAL;
 139         *pa = NULL;
 140
 141         if (!itr->head)
 142                 FDISK_ITER_INIT(itr, &tb->parts);
 143         if (itr->p != itr->head) {
 144                 FDISK_ITER_ITERATE(itr, *pa, struct fdisk_partition, parts);
 145                 rc = 0;
 146         }
 147
 148         return rc;
 149 }
 150
 151 struct fdisk_partition *fdisk_table_get_partition(
 152                         struct fdisk_table *tb,
 153                         size_t n)
 154 {
 155         struct fdisk_partition *pa = NULL;
 156         struct fdisk_iter itr;
 157
 158         if (!tb)
 159                 return NULL;
 160
 161         fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
 162
 163         while (fdisk_table_next_partition(tb, &itr, &pa) == 0) {
 164                 if (n == 0)
 165                         return pa;
 166                 n--;
 167         }
 168
 169         return NULL;
 170 }
 171
 172 /**
 173  * fdisk_table_add_partition
 174  * @tb: tab pointer
 175  * @pa: new entry
 176  *
 177  * Adds a new entry to table and increment @pa reference counter. Don't forget to
 178  * use fdisk_unref_pa() after fdisk_table_add_partition() if you want to keep
 179  * the @pa referenced by the table only.
 180  *
 181  * Returns: 0 on success or negative number in case of error.
 182  */
 183 int fdisk_table_add_partition(struct fdisk_table *tb, struct fdisk_partition *pa)
 184 {
 185         assert(tb);
 186         assert(pa);
 187
 188         if (!tb || !pa)
 189                 return -EINVAL;
 190
 191         fdisk_ref_partition(pa);
 192         list_add_tail(&pa->parts, &tb->parts);
 193         tb->nents++;
 194
 195         DBG(TAB, ul_debugobj(tb, "add entry %p [start=%ju, end=%ju, size=%ju, %s %s %s]",
 196                         pa, pa->start, pa->end, pa->size,
 197                         fdisk_partition_is_freespace(pa) ? "freespace" : "",
 198                         fdisk_partition_is_nested(pa)    ? "nested"    : "",
 199                         fdisk_partition_is_container(pa) ? "container" : "primary"));
 200         return 0;
 201 }
 202
 203 /* inserts @pa after @poz */
 204 static int table_insert_partition(
 205                         struct fdisk_table *tb,
 206                         struct fdisk_partition *poz,
 207                         struct fdisk_partition *pa)
 208 {
 209         assert(tb);
 210         assert(pa);
 211
 212         fdisk_ref_partition(pa);
 213         if (poz)
 214                 list_add(&pa->parts, &poz->parts);
 215         else
 216                 list_add(&pa->parts, &tb->parts);
 217         tb->nents++;
 218
 219         DBG(TAB, ul_debugobj(tb, "insert entry %p pre=%p [start=%ju, end=%ju, size=%ju, %s %s %s]",
 220                         pa, poz ? poz : NULL, pa->start, pa->end, pa->size,
 221                         fdisk_partition_is_freespace(pa) ? "freespace" : "",
 222                         fdisk_partition_is_nested(pa)    ? "nested"    : "",
 223                         fdisk_partition_is_container(pa) ? "container" : "primary"));
 224         return 0;
 225 }
 226
 227 /**
 228  * fdisk_table_remove_partition
 229  * @tb: tab pointer
 230  * @pa: new entry
 231  *
 232  * Removes the @pa from the table and de-increment reference counter of the @pa. The
 233  * partition with zero reference counter will be deallocated. Don't forget to use
 234  * fdisk_ref_partition() before call fdisk_table_remove_partition() if you want
 235  * to use @pa later.
 236  *
 237  * Returns: 0 on success or negative number in case of error.
 238  */
 239 int fdisk_table_remove_partition(struct fdisk_table *tb, struct fdisk_partition *pa)
 240 {
 241         assert(tb);
 242         assert(pa);
 243
 244         if (!tb || !pa)
 245                 return -EINVAL;
 246
 247         DBG(TAB, ul_debugobj(tb, "remove entry %p", pa));
 248         list_del(&pa->parts);
 249         INIT_LIST_HEAD(&pa->parts);
 250
 251         fdisk_unref_partition(pa);
 252         tb->nents--;
 253
 254         return 0;
 255 }
 256
 257 /**
 258  * fdisk_get_partitions
 259  * @cxt: fdisk context
 260  * @tb: returns table
 261  *
 262  * This function adds partitions from disklabel to @table, it allocates a new
 263  * table if if @table points to NULL.
 264  *
 265  * Returns 0 on success, otherwise, a corresponding error.
 266  */
 267 int fdisk_get_partitions(struct fdisk_context *cxt, struct fdisk_table **tb)
 268 {
 269         size_t i;
 270
 271         if (!cxt || !cxt->label || !tb)
 272                 return -EINVAL;
 273         if (!cxt->label->op->get_part)
 274                 return -ENOSYS;
 275
 276         DBG(CXT, ul_debugobj(cxt, "get table"));
 277
 278         if (!*tb && !(*tb = fdisk_new_table()))
 279                 return -ENOMEM;
 280
 281         for (i = 0; i < cxt->label->nparts_max; i++) {
 282                 struct fdisk_partition *pa = NULL;
 283
 284                 if (fdisk_get_partition(cxt, i, &pa) != 0)
 285                         continue;
 286                 if (fdisk_partition_is_used(pa))
 287                         fdisk_table_add_partition(*tb, pa);
 288                 fdisk_unref_partition(pa);
 289         }
 290
 291         return 0;
 292 }
 293
 294 int fdisk_dump_table(struct fdisk_table *tb, FILE *f)
 295 {
 296         struct fdisk_partition *pa;
 297         struct fdisk_iter itr;
 298         int i = 0;
 299
 300         assert(tb);
 301         assert(f);
 302
 303         fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
 304
 305         fprintf(f, "--table--%p\n", tb);
 306         while (fdisk_table_next_partition(tb, &itr, &pa) == 0) {
 307                 fprintf(f, "%d: ", i++);
 308                 fdisk_dump_partition(pa, f);
 309         }
 310         fputs("-----\n", f);
 311         return 0;
 312 }
 313
 314
 315 typedef int (*fdisk_partcmp_t)(struct fdisk_partition *, struct fdisk_partition *);
 316
 317 static int cmp_parts_wrapper(struct list_head *a, struct list_head *b, void *data)
 318 {
 319         struct fdisk_partition *pa = list_entry(a, struct fdisk_partition, parts),
 320                                *pb = list_entry(b, struct fdisk_partition, parts);
 321
 322         fdisk_partcmp_t cmp = (fdisk_partcmp_t) data;
 323
 324         return cmp(pa, pb);
 325 }
 326
 327 int fdisk_table_sort_partitions(struct fdisk_table *tb,
 328                         int (*cmp)(struct fdisk_partition *,
 329                                    struct fdisk_partition *))
 330 {
 331         if (!tb)
 332                 return -EINVAL;
 333
 334         list_sort(&tb->parts, cmp_parts_wrapper, (void *) cmp);
 335         return 0;
 336 }
 337
 338 /* allocates a new freespace description */
 339 static int new_freespace(struct fdisk_context *cxt,
 340                          uint64_t start,
 341                          uint64_t end,
 342                          struct fdisk_partition *parent,
 343                          struct fdisk_partition **pa)
 344 {
 345         assert(cxt);
 346         assert(pa);
 347
 348         *pa = NULL;
 349
 350         if (start == end)
 351                 return 0;
 352         *pa = fdisk_new_partition();
 353         if (!*pa)
 354                 return -ENOMEM;
 355
 356         (*pa)->freespace = 1;
 357         (*pa)->start = fdisk_align_lba_in_range(cxt, start, start, end);
 358         (*pa)->end = end;
 359         (*pa)->size = (*pa)->end - (*pa)->start + 1ULL;
 360
 361         if (parent)
 362                 (*pa)->parent_partno = parent->partno;
 363         return 0;
 364 }
 365
 366 /* add freespace description to the right place within @tb */
 367 static int table_add_freespace(
 368                         struct fdisk_context *cxt,
 369                         struct fdisk_table *tb,
 370                         uint64_t start,
 371                         uint64_t end,
 372                         struct fdisk_partition *parent)
 373 {
 374         struct fdisk_partition *pa, *x, *real_parent = NULL, *best = NULL;
 375         struct fdisk_iter itr;
 376         int rc = 0;
 377
 378         assert(tb);
 379
 380         rc = new_freespace(cxt, start, end, parent, &pa);
 381         if (rc)
 382                 return -ENOMEM;
 383         if (!pa)
 384                 return 0;
 385         fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
 386         if (parent) {
 387                 while (fdisk_table_next_partition(tb, &itr, &x) == 0) {
 388                         if (x->partno == parent->partno) {
 389                                 real_parent = x;
 390                                 break;
 391                         }
 392                 }
 393                 if (!real_parent) {
 394                         DBG(TAB, ul_debugobj(tb, "not found freespace parent (partno=%zu)",
 395                                         parent->partno));
 396                         fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
 397                 }
 398         }
 399
 400         while (fdisk_table_next_partition(tb, &itr, &x) == 0) {
 401                 if (x->end < pa->start && (!best || best->end < x->end))
 402                         best = x;
 403         }
 404
 405         if (!best && real_parent)
 406                 best = real_parent;
 407         rc = table_insert_partition(tb, best, pa);
 408
 409         fdisk_unref_partition(pa);
 410         return rc;
 411 }
 412
 413 /* analyze @cont(ainer) in @parts and add all detected freespace into @tb, note
 414  * that @parts has to be sorted by partition starts */
 415 static int check_container_freespace(struct fdisk_context *cxt,
 416                                      struct fdisk_table *parts,
 417                                      struct fdisk_table *tb,
 418                                      struct fdisk_partition *cont)
 419 {
 420         struct fdisk_iter itr;
 421         struct fdisk_partition *pa;
 422         uint64_t x, last, grain;
 423         uint64_t lastplusoff;
 424         int rc = 0;
 425
 426         assert(cxt);
 427         assert(parts);
 428         assert(tb);
 429         assert(cont);
 430
 431         last = fdisk_partition_get_start(cont);
 432         grain = cxt->grain > cxt->sector_size ? cxt->grain / cxt->sector_size : 1;
 433         fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
 434
 435         while (fdisk_table_next_partition(parts, &itr, &pa) == 0) {
 436                 if (!pa->used || !fdisk_partition_is_nested(pa))
 437                         continue;
 438
 439                 lastplusoff = last + cxt->first_lba;
 440                 if (pa->start > lastplusoff && pa->start - lastplusoff > grain)
 441                         rc = table_add_freespace(cxt, tb, lastplusoff, pa->start, cont);
 442                 if (rc)
 443                         return rc;
 444                 last = pa->end;
 445         }
 446
 447         /* free-space remaining in extended partition */
 448         x = fdisk_partition_get_start(cont) + fdisk_partition_get_size(cont) - 1;
 449         lastplusoff = last + cxt->first_lba;
 450         if (lastplusoff < x && x - lastplusoff > grain)
 451                 rc = table_add_freespace(cxt, tb, lastplusoff, x, cont);
 452         return rc;
 453 }
 454
 455
 456 /**
 457  * fdisk_get_freespaces
 458  * @cxt: fdisk context
 459  * @tb: returns table
 460  *
 461  * This function adds freespace (described by fdisk_partition) to @table, it
 462  * allocates a new table if the @table points to NULL.
 463  *
 464  * Note that free space smaller than grain (see fdisk_topology_get_grain()) is
 465  * ignored.
 466
 467  * Returns 0 on success, otherwise, a corresponding error.
 468  */
 469 int fdisk_get_freespaces(struct fdisk_context *cxt, struct fdisk_table **tb)
 470 {
 471         int rc = 0;
 472         uint64_t last, grain;
 473         struct fdisk_table *parts = NULL;
 474         struct fdisk_partition *pa;
 475         struct fdisk_iter itr;
 476
 477         DBG(CXT, ul_debugobj(cxt, "get freespace"));
 478
 479         if (!cxt || !cxt->label || !tb)
 480                 return -EINVAL;
 481         if (!*tb && !(*tb = fdisk_new_table()))
 482                 return -ENOMEM;
 483
 484         rc = fdisk_get_partitions(cxt, &parts);
 485         if (rc)
 486                 goto done;
 487         fdisk_table_sort_partitions(parts, fdisk_partition_cmp_start);
 488         fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
 489         last = cxt->first_lba;
 490         grain = cxt->grain > cxt->sector_size ? cxt->grain / cxt->sector_size : 1;
 491
 492         /* analyze gaps between partitions */
 493         while (rc == 0 && fdisk_table_next_partition(parts, &itr, &pa) == 0) {
 494                 if (!pa->used || pa->wholedisk || fdisk_partition_is_nested(pa))
 495                         continue;
 496                 DBG(CXT, ul_debugobj(cxt, "freespace analyze: partno=%zu, start=%ju, end=%ju",
 497                                         pa->partno, pa->start, pa->end));
 498                 if (last + grain <= pa->start) {
 499                         rc = table_add_freespace(cxt, *tb,
 500                                 last + (last > cxt->first_lba ? 1 : 0),
 501                                 pa->start - 1, NULL);
 502                 }
 503                 /* add gaps between logical partitions */
 504                 if (fdisk_partition_is_container(pa))
 505                         rc = check_container_freespace(cxt, parts, *tb, pa);
 506                 last = pa->end;
 507         }
 508
 509         /* add free-space behind last partition to the end of the table (so
 510          * don't use table_add_freespace()) */
 511         if (rc == 0 && last + grain < cxt->total_sectors - 1) {
 512                 rc = new_freespace(cxt,
 513                         last + (last > cxt->first_lba ? 1 : 0),
 514                         cxt->last_lba, NULL, &pa);
 515                 if (pa) {
 516                         fdisk_table_add_partition(*tb, pa);
 517                         fdisk_unref_partition(pa);
 518                 }
 519         }
 520
 521         DBG(LABEL, fdisk_dump_table(*tb, stderr));
 522 done:
 523         fdisk_unref_table(parts);
 524         return rc;
 525 }
 526
 527 /**
 528  * fdisk_table_wrong_order:
 529  * @tb: table
 530  *
 531  * Returns: 1 of the table is not in disk order
 532  */
 533 int fdisk_table_wrong_order(struct fdisk_table *tb)
 534 {
 535         struct fdisk_partition *pa;
 536         struct fdisk_iter itr;
 537         sector_t last = 0;
 538
 539         DBG(TAB, ul_debugobj(tb, "wrong older check"));
 540
 541         fdisk_reset_iter(&itr, FDISK_ITER_FORWARD);
 542         while (tb && fdisk_table_next_partition(tb, &itr, &pa) == 0) {
 543                 if (pa->start < last)
 544                         return 1;
 545                 last = pa->start;
 546         }
 547         return 0;
 548 }