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