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