lib/libdisk/chunk.c

   1 /*
   2  * ----------------------------------------------------------------------------
   3  * "THE BEER-WARE LICENSE" (Revision 42):
   4  * <phk@login.dknet.dk> 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  * $FreeBSD: src/lib/libdisk/chunk.c,v 1.21.2.6 2002/01/07 07:53:29 dillon Exp $
  10  * $DragonFly: src/lib/libdisk/Attic/chunk.c,v 1.2 2003/06/17 04:26:49 dillon Exp $
  11  *
  12  */
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <unistd.h>
  17 #include <string.h>
  18 #include <sys/types.h>
  19 #include <err.h>
  20 #include "libdisk.h"
  21
  22 #define new_chunk() memset(malloc(sizeof(struct chunk)), 0, sizeof(struct chunk))
  23
  24 /* Is c2 completely inside c1 ? */
  25
  26 static int
  27 Chunk_Inside(struct chunk *c1, struct chunk *c2)
  28 {
  29         /* if c1 ends before c2 do */
  30         if (c1->end < c2->end)
  31                 return 0;
  32         /* if c1 starts after c2 do */
  33         if (c1->offset > c2->offset)
  34                 return 0;
  35         return 1;
  36 }
  37
  38 struct chunk *
  39 Find_Mother_Chunk(struct chunk *chunks, u_long offset, u_long end, chunk_e type)
  40 {
  41         struct chunk *c1,*c2,ct;
  42
  43         ct.offset = offset;
  44         ct.end = end;
  45         switch (type) {
  46                 case whole:
  47                         if (Chunk_Inside(chunks, &ct))
  48                                 return chunks;
  49 #ifndef PC98
  50                 case extended:
  51                         for(c1 = chunks->part; c1; c1 = c1->next) {
  52                                 if (c1->type != type)
  53                                         continue;
  54                                 if (Chunk_Inside(c1, &ct))
  55                                         return c1;
  56                         }
  57                         return 0;
  58 #endif
  59                 case freebsd:
  60                         for(c1 = chunks->part; c1; c1 = c1->next) {
  61                                 if (c1->type == type)
  62                                         if (Chunk_Inside(c1, &ct))
  63                                                 return c1;
  64                                 if (c1->type != extended)
  65                                         continue;
  66                                 for(c2 = c1->part; c2; c2 = c2->next)
  67                                         if (c2->type == type
  68                                             && Chunk_Inside(c2, &ct))
  69                                                 return c2;
  70                         }
  71                         return 0;
  72                 default:
  73                         warn("Unsupported mother type in Find_Mother_Chunk");
  74                         return 0;
  75         }
  76 }
  77
  78 void
  79 Free_Chunk(struct chunk *c1)
  80 {
  81         if(!c1) return;
  82         if(c1->private_data && c1->private_free)
  83                 (*c1->private_free)(c1->private_data);
  84         if(c1->part)
  85                 Free_Chunk(c1->part);
  86         if(c1->next)
  87                 Free_Chunk(c1->next);
  88         free(c1->name);
  89 #ifdef PC98
  90         free(c1->sname);
  91 #endif
  92         free(c1);
  93 }
  94
  95 struct chunk *
  96 Clone_Chunk(struct chunk *c1)
  97 {
  98         struct chunk *c2;
  99
 100         if(!c1)
 101                 return 0;
 102         c2 = new_chunk();
 103         if (!c2) return NULL;
 104         *c2 = *c1;
 105         if (c1->private_data && c1->private_clone)
 106                 c2->private_data = c2->private_clone(c2->private_data);
 107         c2->name = strdup(c2->name);
 108 #ifdef PC98
 109         c2->sname = strdup(c2->sname);
 110 #endif
 111         c2->next = Clone_Chunk(c2->next);
 112         c2->part = Clone_Chunk(c2->part);
 113         return c2;
 114 }
 115
 116 int
 117 #ifdef PC98
 118 Insert_Chunk(struct chunk *c2, u_long offset, u_long size, const char *name,
 119         chunk_e type, int subtype, u_long flags, const char *sname)
 120 #else
 121 Insert_Chunk(struct chunk *c2, u_long offset, u_long size, const char *name,
 122         chunk_e type, int subtype, u_long flags)
 123 #endif
 124 {
 125         struct chunk *ct,*cs;
 126
 127         /* We will only insert into empty spaces */
 128         if (c2->type != unused)
 129                 return __LINE__;
 130
 131         ct = new_chunk();
 132         if (!ct) return __LINE__;
 133         memset(ct, 0, sizeof *ct);
 134         ct->disk = c2->disk;
 135         ct->offset = offset;
 136         ct->size = size;
 137         ct->end = offset + size - 1;
 138         ct->type = type;
 139 #ifdef PC98
 140         ct->sname = strdup(sname);
 141 #endif
 142         ct->name = strdup(name);
 143         ct->subtype = subtype;
 144         ct->flags = flags;
 145
 146         if (!Chunk_Inside(c2, ct)) {
 147                 Free_Chunk(ct);
 148                 return __LINE__;
 149         }
 150
 151         if(type==freebsd || type==extended) {
 152                 cs = new_chunk();
 153                 if (!cs) return __LINE__;
 154                 memset(cs, 0, sizeof *cs);
 155                 cs->disk = c2->disk;
 156                 cs->offset = offset;
 157                 cs->size = size;
 158                 cs->end = offset + size - 1;
 159                 cs->type = unused;
 160 #ifdef PC98
 161                 cs->sname = strdup(sname);
 162 #endif
 163                 cs->name = strdup("-");
 164                 ct->part = cs;
 165         }
 166
 167         /* Make a new chunk for any trailing unused space */
 168         if (c2->end > ct->end) {
 169                 cs = new_chunk();
 170                 if (!cs) return __LINE__;
 171                 *cs = *c2;
 172                 cs->disk = c2->disk;
 173                 cs->offset = ct->end + 1;
 174                 cs->size = c2->end - ct->end;
 175 #ifdef PC98
 176                 if(c2->sname)
 177                         cs->sname = strdup(c2->sname);
 178 #endif
 179                 if(c2->name)
 180                         cs->name = strdup(c2->name);
 181                 c2->next = cs;
 182                 c2->size -= c2->end - ct->end;
 183                 c2->end = ct->end;
 184         }
 185         /* If no leading unused space just occupy the old chunk */
 186         if (c2->offset == ct->offset) {
 187 #ifdef PC98
 188                 c2->sname = ct->sname;
 189 #endif
 190                 c2->name = ct->name;
 191                 c2->type = ct->type;
 192                 c2->part = ct->part;
 193                 c2->subtype = ct->subtype;
 194                 c2->flags = ct->flags;
 195 #ifdef PC98
 196                 ct->sname = 0;
 197 #endif
 198                 ct->name = 0;
 199                 ct->part = 0;
 200                 Free_Chunk(ct);
 201                 return 0;
 202         }
 203         /* else insert new chunk and adjust old one */
 204         c2->end = ct->offset - 1;
 205         c2->size -= ct->size;
 206         ct->next = c2->next;
 207         c2->next = ct;
 208         return 0;
 209 }
 210
 211 int
 212 #ifdef PC98
 213 Add_Chunk(struct disk *d, long offset, u_long size, const char *name,
 214         chunk_e type, int subtype, u_long flags, const char *sname)
 215 #else
 216 Add_Chunk(struct disk *d, long offset, u_long size, const char *name,
 217         chunk_e type, int subtype, u_long flags)
 218 #endif
 219 {
 220         struct chunk *c1,*c2,ct;
 221         u_long 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) return __LINE__;
 229                 memset(c1, 0, sizeof *c1);
 230                 c2 = c1->part = new_chunk();
 231                 if (!c2) return __LINE__;
 232                 memset(c2,0,sizeof *c2);
 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 #ifdef PC98
 238                 c1->sname = strdup(sname);
 239                 c2->sname = strdup("-");
 240 #endif
 241                 c1->name = strdup(name);
 242                 c2->name = strdup("-");
 243                 c1->type = type;
 244                 c2->type = unused;
 245                 c1->flags = flags;
 246                 c1->subtype = subtype;
 247                 return 0;
 248         }
 249         if (type == freebsd)
 250 #ifdef PC98
 251                 subtype = 0xc494;
 252 #else
 253                 subtype = 0xa5;
 254 #endif
 255         c1 = 0;
 256 #ifndef PC98
 257         if(!c1 && (type == freebsd || type == fat || type == unknown))
 258                 c1 = Find_Mother_Chunk(d->chunks, offset, end, extended);
 259 #endif
 260         if(!c1 && (type == freebsd || type == fat || type == unknown))
 261                 c1 = Find_Mother_Chunk(d->chunks, offset, end, whole);
 262 #ifndef PC98
 263         if(!c1 && type == extended)
 264                 c1 = Find_Mother_Chunk(d->chunks, offset, end, whole);
 265 #endif
 266         if(!c1 && type == part)
 267                 c1 = Find_Mother_Chunk(d->chunks, offset, end, freebsd);
 268         if(!c1)
 269                 return __LINE__;
 270         for(c2 = c1->part; c2; c2 = c2->next) {
 271                 if (c2->type != unused)
 272                         continue;
 273                 if(Chunk_Inside(c2, &ct)) {
 274                         if (type != freebsd)
 275                                 goto doit;
 276                         if (!(flags & CHUNK_ALIGN))
 277                                 goto doit;
 278                         if (offset == d->chunks->offset
 279                            && end == d->chunks->end)
 280                                 goto doit;
 281
 282                         /* Round down to prev cylinder */
 283                         offset = Prev_Cyl_Aligned(d,offset);
 284                         /* Stay inside the parent */
 285                         if (offset < c2->offset)
 286                                 offset = c2->offset;
 287                         /* Round up to next cylinder */
 288                         offset = Next_Cyl_Aligned(d, offset);
 289                         /* Keep one track clear in front of parent */
 290                         if (offset == c1->offset)
 291                                 offset = Next_Track_Aligned(d, offset + 1);
 292
 293                         /* Work on the (end+1) */
 294                         size += offset;
 295                         /* Round up to cylinder */
 296                         size = Next_Cyl_Aligned(d, size);
 297                         /* Stay inside parent */
 298                         if ((size-1) > c2->end)
 299                                 size = c2->end + 1;
 300                         /* Round down to cylinder */
 301                         size = Prev_Cyl_Aligned(d, size);
 302
 303                         /* Convert back to size */
 304                         size -= offset;
 305
 306                     doit:
 307 #ifdef PC98
 308                         return Insert_Chunk(c2, offset, size, name,
 309                                 type, subtype, flags, sname);
 310 #else
 311                         return Insert_Chunk(c2, offset, size, name,
 312                                 type, subtype, flags);
 313 #endif
 314                 }
 315         }
 316         return __LINE__;
 317 }
 318
 319 char *
 320 ShowChunkFlags(struct chunk *c)
 321 {
 322         static char ret[10];
 323
 324         int i=0;
 325         if (c->flags & CHUNK_BSD_COMPAT)        ret[i++] = 'C';
 326         if (c->flags & CHUNK_ACTIVE)            ret[i++] = 'A';
 327         if (c->flags & CHUNK_ALIGN)             ret[i++] = '=';
 328         if (c->flags & CHUNK_IS_ROOT)           ret[i++] = 'R';
 329         ret[i++] = '\0';
 330         return ret;
 331 }
 332
 333 void
 334 Print_Chunk(struct chunk *c1,int offset)
 335 {
 336         int i;
 337         if(!c1) return;
 338         for(i = 0; i < offset - 2; i++) putchar(' ');
 339         for(; i < offset; i++) putchar('-');
 340         putchar('>');
 341         for(; i < 10; i++) putchar(' ');
 342 #ifdef PC98
 343         printf("%p %8ld %8lu %8lu %-8s %-16s %-8s 0x%02x %s",
 344                 c1, c1->offset, c1->size, c1->end, c1->name, c1->sname,
 345 #else
 346         printf("%p %8ld %8lu %8lu %-8s %-8s 0x%02x %s",
 347                 c1, c1->offset, c1->size, c1->end, c1->name,
 348 #endif
 349                 chunk_n[c1->type], c1->subtype,
 350                 ShowChunkFlags(c1));
 351         putchar('\n');
 352         Print_Chunk(c1->part, offset + 2);
 353         Print_Chunk(c1->next, offset);
 354 }
 355
 356 void
 357 Debug_Chunk(struct chunk *c1)
 358 {
 359         Print_Chunk(c1,2);
 360 }
 361
 362 int
 363 Delete_Chunk(struct disk *d, struct chunk *c)
 364 {
 365     return(Delete_Chunk2(d, c, 0));
 366 }
 367
 368 int
 369 Delete_Chunk2(struct disk *d, struct chunk *c, int rflags)
 370 {
 371         struct chunk *c1=0, *c2, *c3;
 372         chunk_e type = c->type;
 373         long offset = c->offset;
 374
 375         if(type == whole)
 376                 return 1;
 377 #ifndef PC98
 378         if(!c1 && (type == freebsd || type == fat || type == unknown))
 379                 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, extended);
 380 #endif
 381         if(!c1 && (type == freebsd || type == fat || type == unknown))
 382                 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, whole);
 383 #ifndef PC98
 384         if(!c1 && type == extended)
 385                 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, whole);
 386 #endif
 387         if(!c1 && type == part)
 388                 c1 = Find_Mother_Chunk(d->chunks, c->offset, c->end, freebsd);
 389         if(!c1)
 390                 return 1;
 391         for(c2 = c1->part; c2; c2 = c2->next) {
 392                 if (c2 == c) {
 393                         c2->type = unused;
 394                         c2->subtype = 0;
 395                         c2->flags = 0;
 396 #ifdef PC98
 397                         free(c2->sname);
 398                         c2->sname = strdup("-");
 399 #endif
 400                         free(c2->name);
 401                         c2->name = strdup("-");
 402                         Free_Chunk(c2->part);
 403                         c2->part =0;
 404                         goto scan;
 405                 }
 406         }
 407         return 1;
 408     scan:
 409         /*
 410          * Collapse multiple unused elements together, and attempt
 411          * to extend the previous chunk into the freed chunk.
 412          *
 413          * We only extend non-unused elements which are marked
 414          * for newfs (we can't extend working filesystems), and
 415          * only if we are called with DELCHUNK_RECOVER.
 416          */
 417         for(c2 = c1->part; c2; c2 = c2->next) {
 418                 if (c2->type != unused) {
 419                         if (c2->offset + c2->size != offset ||
 420                             (rflags & DELCHUNK_RECOVER) == 0 ||
 421                             (c2->flags & CHUNK_NEWFS) == 0) {
 422                                 continue;
 423                         }
 424                         /* else extend into free area */
 425                 }
 426                 if (!c2->next)
 427                         continue;
 428                 if (c2->next->type != unused)
 429                         continue;
 430                 c3 = c2->next;
 431                 c2->size += c3->size;
 432                 c2->end = c3->end;
 433                 c2->next = c3->next;
 434                 c3->next = 0;
 435                 Free_Chunk(c3);
 436                 goto scan;
 437         }
 438         Fixup_Names(d);
 439         return 0;
 440 }
 441
 442 #if 0
 443 int
 444 Collapse_Chunk(struct disk *d, struct chunk *c1)
 445 {
 446         struct chunk *c2, *c3;
 447
 448         if(c1->next && Collapse_Chunk(d, c1->next))
 449                 return 1;
 450
 451         if(c1->type == unused && c1->next && c1->next->type == unused) {
 452                 c3 = c1->next;
 453                 c1->size += c3->size;
 454                 c1->end = c3->end;
 455                 c1->next = c3->next;
 456                 c3->next = 0;
 457                 Free_Chunk(c3);
 458                 return 1;
 459         }
 460         c3 = c1->part;
 461         if(!c3)
 462                 return 0;
 463         if (Collapse_Chunk(d, c1->part))
 464                 return 1;
 465
 466         if (c1->type == whole)
 467                 return 0;
 468
 469         if(c3->type == unused && c3->size == c1->size) {
 470                 Delete_Chunk(d, c1);
 471                 return 1;
 472         }
 473         if(c3->type == unused) {
 474                 c2 = new_chunk();
 475                 if (!c2) barfout(1, "malloc failed");
 476                 *c2 = *c1;
 477                 c1->next = c2;
 478                 c1->disk = d;
 479 #ifdef PC98
 480                 c1->sname = strdup("-");
 481 #endif
 482                 c1->name = strdup("-");
 483                 c1->part = 0;
 484                 c1->type = unused;
 485                 c1->flags = 0;
 486                 c1->subtype = 0;
 487                 c1->size = c3->size;
 488                 c1->end = c3->end;
 489                 c2->offset += c1->size;
 490                 c2->size -= c1->size;
 491                 c2->part = c3->next;
 492                 c3->next = 0;
 493                 Free_Chunk(c3);
 494                 return 1;
 495         }
 496         for(c2=c3;c2->next;c2 = c2->next)
 497                 c3 = c2;
 498         if (c2 && c2->type == unused) {
 499                 c3->next = 0;
 500                 c2->next = c1->next;
 501                 c1->next = c2;
 502                 c1->size -= c2->size;
 503                 c1->end -= c2->size;
 504                 return 1;
 505         }
 506
 507         return 0;
 508 }
 509 #endif