lib/libdisk/chunk.c

   1 /*
   2  * ----------------------------------------------------------------------------
   3  * "THE BEER-WARE LICENSE" (Revision 42):
   4  * <phk@FreeBSD.org> wrote this file.  As long as you retain this notice you
   5  * can do whatever you want with this stuff. If we meet some day, and you think
   6  * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
   7  * ----------------------------------------------------------------------------
   8  */
   9
  10 #include <sys/cdefs.h>
  11 __FBSDID("$FreeBSD$");
  12
  13 #include <sys/types.h>
  14 #include <sys/stdint.h>
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <unistd.h>
  18 #include <string.h>
  19 #include <err.h>
  20 #include "libdisk.h"
  21
  22 struct chunk *
  23 New_Chunk(void)
  24 {
  25         struct chunk *c;
  26
  27         c = malloc(sizeof *c);
  28         if (c != NULL)
  29                 memset(c, 0, sizeof *c);
  30         return (c);
  31 }
  32
  33 /* Is c2 completely inside c1 ? */
  34
  35 static int
  36 Chunk_Inside(const struct chunk *c1, const struct chunk *c2)
  37 {
  38         /* if c1 ends before c2 do */
  39         if (c1->end < c2->end)
  40                 return 0;
  41         /* if c1 starts after c2 do */
  42         if (c1->offset > c2->offset)
  43                 return 0;
  44         return 1;
  45 }
  46
  47 static struct chunk *
  48 Find_Mother_Chunk(struct chunk *chunks, daddr_t offset, daddr_t end,
  49                   chunk_e type)
  50 {
  51         struct chunk *c1, *c2, ct;
  52
  53         ct.offset = offset;
  54         ct.end = end;
  55         switch (type) {
  56         case whole:
  57                 if (Chunk_Inside(chunks, &ct))
  58                         return chunks;
  59         case extended:
  60                 for (c1 = chunks->part; c1; c1 = c1->next) {
  61                         if (c1->type != type)
  62                                 continue;
  63                         if (Chunk_Inside(c1, &ct))
  64                                 return c1;
  65                 }
  66                 return 0;
  67         case freebsd:
  68                 for (c1 = chunks->part; c1; c1 = c1->next) {
  69                         if (c1->type == type)
  70                                 if (Chunk_Inside(c1, &ct))
  71                                         return c1;
  72                         if (c1->type != extended)
  73                                 continue;
  74                         for (c2 = c1->part; c2; c2 = c2->next)
  75                                 if (c2->type == type && Chunk_Inside(c2, &ct))
  76                                         return c2;
  77                 }
  78                 return 0;
  79 #ifdef __powerpc__
  80         case apple:
  81                 for (c1 = chunks->part; c1; c1 = c1->next) {
  82                         if (c1->type == type)
  83                                 if (Chunk_Inside(c1, &ct))
  84                                         return c1;
  85                 }
  86                 return 0;
  87 #endif
  88         default:
  89                 warn("Unsupported mother type in Find_Mother_Chunk");
  90                 return 0;
  91         }
  92 }
  93
  94 void
  95 Free_Chunk(struct chunk *c1)
  96 {
  97         if(c1 == NULL)
  98                 return;
  99         if(c1->private_data && c1->private_free)
 100                 (*c1->private_free)(c1->private_data);
 101         if(c1->part != NULL)
 102                 Free_Chunk(c1->part);
 103         if(c1->next != NULL)
 104                 Free_Chunk(c1->next);
 105         if (c1->name != NULL)
 106                 free(c1->name);
 107         if (c1->sname != NULL)
 108                 free(c1->sname);
 109         free(c1);
 110 }
 111
 112 struct chunk *
 113 Clone_Chunk(const struct chunk *c1)
 114 {
 115         struct chunk *c2;
 116
 117         if(!c1)
 118                 return NULL;
 119         c2 = New_Chunk();
 120         if (c2 == NULL)
 121                 return NULL;
 122         *c2 = *c1;
 123         if (c1->private_data && c1->private_clone)
 124                 c2->private_data = c2->private_clone(c2->private_data);
 125         c2->name = strdup(c2->name);
 126         if (c2->sname != NULL)
 127                 c2->sname = strdup(c2->sname);
 128         c2->next = Clone_Chunk(c2->next);
 129         c2->part = Clone_Chunk(c2->part);
 130         return c2;
 131 }
 132
 133 int
 134 Insert_Chunk(struct chunk *c2, daddr_t offset, daddr_t size, const char *name,
 135         chunk_e type, int subtype, u_long flags, const char *sname)
 136 {
 137         struct chunk *ct,*cs;
 138
 139         /* We will only insert into empty spaces */
 140         if (c2->type != unused)
 141                 return __LINE__;
 142
 143         ct = New_Chunk();
 144         if (ct == NULL)
 145                 return __LINE__;
 146         ct->disk = c2->disk;
 147         ct->offset = offset;
 148         ct->size = size;
 149         ct->end = offset + size - 1;
 150         ct->type = type;
 151         if (sname != NULL)
 152                 ct->sname = strdup(sname);
 153         ct->name = strdup(name);
 154         ct->subtype = subtype;
 155         ct->flags = flags;
 156
 157         if (!Chunk_Inside(c2, ct)) {
 158                 Free_Chunk(ct);
 159                 return __LINE__;
 160         }
 161
 162         if ((type == freebsd || type == extended || type == apple)) {
 163                 cs = New_Chunk();
 164                 if (cs == NULL)
 165                         return __LINE__;
 166                 cs->disk = c2->disk;
 167                 cs->offset = offset;
 168                 cs->size = size;
 169                 cs->end = offset + size - 1;
 170                 cs->type = unused;
 171                 if (sname != NULL)
 172                         cs->sname = strdup(sname);
 173                 cs->name = strdup("-");
 174                 ct->part = cs;
 175         }
 176
 177         /* Make a new chunk for any trailing unused space */
 178         if (c2->end > ct->end) {
 179                 cs = New_Chunk();
 180                 if (cs == NULL)
 181                          return __LINE__;
 182                 *cs = *c2;
 183                 cs->disk = c2->disk;
 184                 cs->offset = ct->end + 1;
 185                 cs->size = c2->end - ct->end;
 186                 if (c2->sname != NULL)
 187                         cs->sname = strdup(c2->sname);
 188                 if (c2->name)
 189                         cs->name = strdup(c2->name);
 190                 c2->next = cs;
 191                 c2->size -= c2->end - ct->end;
 192                 c2->end = ct->end;
 193         }
 194         /* If no leading unused space just occupy the old chunk */
 195         if (c2->offset == ct->offset) {
 196                 c2->sname = ct->sname;
 197                 c2->name = ct->name;
 198                 c2->type = ct->type;
 199                 c2->part = ct->part;
 200                 c2->subtype = ct->subtype;
 201                 c2->flags = ct->flags;
 202                 ct->sname = NULL;
 203                 ct->name = NULL;
 204                 ct->part = 0;
 205                 Free_Chunk(ct);
 206                 return 0;
 207         }
 208         /* else insert new chunk and adjust old one */
 209         c2->end = ct->offset - 1;
 210         c2->size -= ct->size;
 211         ct->next = c2->next;
 212         c2->next = ct;
 213         return 0;
 214 }
 215
 216 int
 217 Add_Chunk(struct disk *d, daddr_t offset, daddr_t size, const char *name,
 218           chunk_e type, int subtype, u_long flags, const char *sname)
 219 {
 220         struct chunk *c1, *c2, ct;
 221         daddr_t end = offset + size - 1;
 222         ct.offset = offset;
 223         ct.end = end;
 224         ct.size = size;
 225
 226         if (type == whole) {
 227                 d->chunks = c1 = New_Chunk();
 228                 if (c1 == NULL)
 229                         return __LINE__;
 230                 c2 = c1->part = New_Chunk();
 231                 if (c2 == NULL)
 232                          return __LINE__;
 233                 c2->disk = c1->disk = d;
 234                 c2->offset = c1->offset = offset;
 235                 c2->size = c1->size = size;
 236                 c2->end = c1->end = end;
 237                 c1->sname = strdup(sname);
 238                 c2->sname = strdup("-");
 239                 c1->name = strdup(name);
 240                 c2->name = strdup("-");
 241                 c1->type = type;
 242                 c2->type = unused;
 243                 c1->flags = flags;
 244                 c1->subtype = subtype;
 245                 return 0;
 246         }
 247
 248         c1 = 0;
 249         /* PLATFORM POLICY BEGIN ------------------------------------- */
 250         switch(platform) {
 251         case p_i386:
 252         case p_amd64:
 253                 switch (type) {
 254                 case fat:
 255                 case gpt:
 256                 case mbr:
 257                 case extended:
 258                 case freebsd:
 259                         c1 = Find_Mother_Chunk(d->chunks, offset, end, whole);
 260                         break;
 261                 case part:
 262                         c1 = Find_Mother_Chunk(d->chunks, offset, end, freebsd);
 263                         break;
 264                 default:
 265                         return(-1);
 266                 }
 267                 break;
 268         case p_ia64:
 269                 switch (type) {
 270                 case freebsd:
 271                         subtype = 0xa5;
 272                         /* FALL THROUGH */
 273                 case fat:
 274                 case efi:
 275                 case mbr:
 276                         c1 = Find_Mother_Chunk(d->chunks, offset, end, whole);
 277                         break;
 278                 case part:
 279                         c1 = Find_Mother_Chunk(d->chunks, offset, end,
 280                             freebsd);
 281                         if (!c1)
 282                                 c1 = Find_Mother_Chunk(d->chunks, offset, end,
 283                                     whole);
 284                         break;
 285                 default:
 286                         return (-1);
 287                 }
 288                 break;
 289         case p_pc98:
 290                 switch (type) {
 291                 case fat:
 292                 case pc98:
 293                 case freebsd:
 294                         c1 = Find_Mother_Chunk(d->chunks, offset, end, whole);
 295                         break;
 296                 case part:
 297                         c1 = Find_Mother_Chunk(d->chunks, offset, end, freebsd);
 298                         break;
 299                 default:
 300                         return(-1);
 301                 }
 302                 break;
 303         case p_sparc64:
 304         case p_alpha:
 305                 switch (type) {
 306                 case freebsd:
 307                         c1 = Find_Mother_Chunk(d->chunks, offset, end, whole);
 308                         break;
 309                 case part:
 310                         c1 = Find_Mother_Chunk(d->chunks, offset, end, freebsd);
 311                         break;
 312                 default:
 313                         return(-1);
 314                 }
 315                 break;
 316         case p_ppc:
 317                 switch (type) {
 318                 case apple:
 319                         c1 = Find_Mother_Chunk(d->chunks, offset, end, whole);
 320                         break;
 321                 case part:
 322                         c1 = Find_Mother_Chunk(d->chunks, offset, end, apple);
 323                         break;
 324                 default:
 325                         return (-1);
 326                 }
 327                 break;
 328         default:
 329                 return (-1);
 330         }
 331         /* PLATFORM POLICY END ---------------------------------------- */
 332
 333         if(!c1)
 334                 return __LINE__;
 335         for(c2 = c1->part; c2; c2 = c2->next) {
 336                 if (c2->type != unused)
 337                         continue;
 338                 if(!Chunk_Inside(c2, &ct))
 339                         continue;
 340 /* PLATFORM POLICY BEGIN ------------------------------------- */
 341                 if (platform == p_sparc64) {
 342                         offset = Prev_Cyl_Aligned(d, offset);
 343                         size = Next_Cyl_Aligned(d, size);
 344                 } else if (platform == p_i386 || platform == p_pc98 ||
 345                     platform == p_amd64) {
 346                         if (type != freebsd)
 347                                 break;
 348                         if (!(flags & CHUNK_ALIGN))
 349                                 break;
 350                         if (offset == d->chunks->offset &&
 351                             end == d->chunks->end)
 352                                 break;
 353
 354                         /* Round down to prev cylinder */
 355                         offset = Prev_Cyl_Aligned(d,offset);
 356                         /* Stay inside the parent */
 357                         if (offset < c2->offset)
 358                                 offset = c2->offset;
 359                         /* Round up to next cylinder */
 360                         offset = Next_Cyl_Aligned(d, offset);
 361                         /* Keep one track clear in front of parent */
 362                         if (offset == c1->offset)
 363                                 offset = Next_Track_Aligned(d, offset + 1);
 364                         /* Work on the (end+1) */
 365                         size += offset;
 366                         /* Round up to cylinder */
 367                         size = Next_Cyl_Aligned(d, size);
 368                         /* Stay inside parent */
 369                         if ((size-1) > c2->end)
 370                                 size = c2->end + 1;
 371                         /* Round down to cylinder */
 372                         size = Prev_Cyl_Aligned(d, size);
 373
 374                         /* Convert back to size */
 375                         size -= offset;
 376                 }
 377                 break;
 378
 379 /* PLATFORM POLICY END ------------------------------------- */
 380         }
 381         if (c2 == NULL)
 382                 return (__LINE__);
 383         return Insert_Chunk(c2, offset, size, name, type, subtype, flags,
 384                             sname);
 385 }
 386
 387 char *
 388 ShowChunkFlags(struct chunk *c)
 389 {
 390         static char ret[10];
 391         int i = 0;
 392
 393         if (c->flags & CHUNK_ACTIVE)
 394                 ret[i++] = 'A';
 395         if (c->flags & CHUNK_ALIGN)
 396                 ret[i++] = '=';
 397         if (c->flags & CHUNK_IS_ROOT)
 398                 ret[i++] = 'R';
 399         ret[i++] = '\0';
 400
 401         return ret;
 402 }
 403
 404 static void
 405 Print_Chunk(struct chunk *c1, int offset)
 406 {
 407         int i;
 408
 409         if (!c1)
 410                 return;
 411         for (i = 0; i < offset - 2; i++)
 412                 putchar(' ');
 413         for (; i < offset; i++)
 414                 putchar('-');
 415         putchar('>');
 416         for (; i < 10; i++)
 417                 putchar(' ');
 418 #ifndef __ia64__
 419         printf("%p ", c1);
 420 #endif
 421         printf("%8jd %8jd %8jd %-8s %-16s %-8s 0x%02x %s",
 422             (intmax_t)c1->offset, (intmax_t)c1->size, (intmax_t)c1->end,
 423             c1->name, c1->sname, chunk_name(c1->type), c1->subtype,
 424             ShowChunkFlags(c1));
 425         putchar('\n');
 426         Print_Chunk(c1->part, offset + 2);
 427         Print_Chunk(c1->next, offset);
 428 }
 429
 430 void
 431 Debug_Chunk(struct chunk *c1)
 432 {
 433
 434         Print_Chunk(c1, 2);
 435 }
 436
 437 int
 438 Delete_Chunk(struct disk *d, struct chunk *c)
 439 {
 440
 441         return (Delete_Chunk2(d, c, 0));
 442 }
 443
 444 int
 445 Delete_Chunk2(struct disk *d, struct chunk *c, int rflags)
 446 {
 447         struct chunk *c1, *c2, *c3;
 448         daddr_t offset = c->offset;
 449
 450         switch (c->type) {
 451         case whole:
 452         case unused:
 453                 return 1;
 454         case extended:
 455                 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, whole);
 456                 break;
 457         case part:
 458                 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, freebsd);
 459 #ifdef __ia64__
 460                 if (c1 == NULL)
 461                         c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end,
 462                             whole);
 463 #endif
 464 #ifdef __powerpc__
 465                 if (c1 == NULL)
 466                         c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end,
 467                             apple);
 468 #endif
 469                 break;
 470         default:
 471                 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, extended);
 472                 if (c1 == NULL)
 473                         c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end,
 474                             whole);
 475                 break;
 476         }
 477         if (c1 == NULL)
 478                 return 1;
 479         for (c2 = c1->part; c2; c2 = c2->next) {
 480                 if (c2 == c) {
 481                         c2->type = unused;
 482                         c2->subtype = 0;
 483                         c2->flags = 0;
 484                         if (c2->sname != NULL)
 485                                 free(c2->sname);
 486                         c2->sname = strdup("-");
 487                         free(c2->name);
 488                         c2->name = strdup("-");
 489                         Free_Chunk(c2->part);
 490                         c2->part =0;
 491                         goto scan;
 492                 }
 493         }
 494         return 1;
 495 scan:
 496         /*
 497          * Collapse multiple unused elements together, and attempt
 498          * to extend the previous chunk into the freed chunk.
 499          *
 500          * We only extend non-unused elements which are marked
 501          * for newfs (we can't extend working filesystems), and
 502          * only if we are called with DELCHUNK_RECOVER.
 503          */
 504         for (c2 = c1->part; c2; c2 = c2->next) {
 505                 if (c2->type != unused) {
 506                         if (c2->offset + c2->size != offset ||
 507                             (rflags & DELCHUNK_RECOVER) == 0 ||
 508                             (c2->flags & CHUNK_NEWFS) == 0) {
 509                                 continue;
 510                         }
 511                         /* else extend into free area */
 512                 }
 513                 if (!c2->next)
 514                         continue;
 515                 if (c2->next->type != unused)
 516                         continue;
 517                 c3 = c2->next;
 518                 c2->size += c3->size;
 519                 c2->end = c3->end;
 520                 c2->next = c3->next;
 521                 c3->next = 0;
 522                 Free_Chunk(c3);
 523                 goto scan;
 524         }
 525         Fixup_Names(d);
 526         return 0;
 527 }
 528
 529 #if 0
 530 int
 531 Collapse_Chunk(struct disk *d, struct chunk *c1)
 532 {
 533         struct chunk *c2, *c3;
 534
 535         if (c1->next && Collapse_Chunk(d, c1->next))
 536                 return 1;
 537
 538         if (c1->type == unused && c1->next && c1->next->type == unused) {
 539                 c3 = c1->next;
 540                 c1->size += c3->size;
 541                 c1->end = c3->end;
 542                 c1->next = c3->next;
 543                 c3->next = 0;
 544                 Free_Chunk(c3);
 545                 return 1;
 546         }
 547         c3 = c1->part;
 548         if (!c3)
 549                 return 0;
 550         if (Collapse_Chunk(d, c1->part))
 551                 return 1;
 552
 553         if (c1->type == whole)
 554                 return 0;
 555
 556         if (c3->type == unused && c3->size == c1->size) {
 557                 Delete_Chunk(d, c1);
 558                 return 1;
 559         }
 560         if (c3->type == unused) {
 561                 c2 = New_Chunk();
 562                 if (c2 == NULL)
 563                         barfout(1, "malloc failed");
 564                 *c2 = *c1;
 565                 c1->next = c2;
 566                 c1->disk = d;
 567                 c1->sname = strdup("-");
 568                 c1->name = strdup("-");
 569                 c1->part = 0;
 570                 c1->type = unused;
 571                 c1->flags = 0;
 572                 c1->subtype = 0;
 573                 c1->size = c3->size;
 574                 c1->end = c3->end;
 575                 c2->offset += c1->size;
 576                 c2->size -= c1->size;
 577                 c2->part = c3->next;
 578                 c3->next = 0;
 579                 Free_Chunk(c3);
 580                 return 1;
 581         }
 582         for (c2 = c3; c2->next; c2 = c2->next)
 583                 c3 = c2;
 584         if (c2 && c2->type == unused) {
 585                 c3->next = 0;
 586                 c2->next = c1->next;
 587                 c1->next = c2;
 588                 c1->size -= c2->size;
 589                 c1->end -= c2->size;
 590                 return 1;
 591         }
 592
 593         return 0;
 594 }
 595 #endif