libparted/fs/hfs/reloc_plus.c

   1 /*
   2     libparted - a library for manipulating disk partitions
   3     Copyright (C) 2004-2005, 2007, 2009-2011 Free Software Foundation, Inc.
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 3 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 #ifndef DISCOVER_ONLY
  20
  21 #include <config.h>
  22
  23 #include <parted/parted.h>
  24 #include <parted/endian.h>
  25 #include <parted/debug.h>
  26 #include <stdint.h>
  27
  28 #if ENABLE_NLS
  29 #  include <libintl.h>
  30 #  define _(String) dgettext (PACKAGE, String)
  31 #else
  32 #  define _(String) (String)
  33 #endif /* ENABLE_NLS */
  34
  35 #include "hfs.h"
  36 #include "file_plus.h"
  37 #include "advfs_plus.h"
  38 #include "cache.h"
  39 #include "journal.h"
  40
  41 #include "reloc_plus.h"
  42
  43 /* This function moves data of size blocks starting at block *ptr_fblock
  44    to block *ptr_to_fblock */
  45 /* return new start or -1 on failure */
  46 /* -1 is ok because there can only be 2^32-1 blocks, so the max possible
  47    last one is 2^32-2 (and anyway it contains Alternate VH), so
  48    -1 (== 2^32-1[2^32]) never represent a valid block */
  49 static int
  50 hfsplus_effect_move_extent (PedFileSystem *fs, unsigned int *ptr_fblock,
  51                             unsigned int *ptr_to_fblock, unsigned int size)
  52 {
  53         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
  54                                                 fs->type_specific;
  55         unsigned int            i, ok = 0;
  56         unsigned int            next_to_fblock;
  57         unsigned int            start, stop;
  58
  59         PED_ASSERT (hfsp_block != NULL, return -1);
  60         PED_ASSERT (*ptr_to_fblock <= *ptr_fblock, return -1);
  61         /* quiet GCC */
  62         start = stop = 0;
  63
  64 /*
  65         Try to fit the extent AT or _BEFORE_ the wanted place,
  66         or then in the gap between dest and source.
  67         If failed try to fit the extent after source, for 2 pass relocation
  68         The extent is always copied in a non overlapping way
  69 */
  70
  71         /* Backward search */
  72         /* 1 pass relocation AT or BEFORE *ptr_to_fblock */
  73         if (*ptr_to_fblock != *ptr_fblock) {
  74                 start = stop = *ptr_fblock < *ptr_to_fblock+size ?
  75                                *ptr_fblock : *ptr_to_fblock+size;
  76                 while (start && stop-start != size) {
  77                         --start;
  78                         if (TST_BLOC_OCCUPATION(priv_data->alloc_map,start))
  79                                 stop = start;
  80                 }
  81                 ok = (stop-start == size);
  82         }
  83
  84         /* Forward search */
  85         /* 1 pass relocation in the gap merged with 2 pass reloc after source */
  86         if (!ok && *ptr_to_fblock != *ptr_fblock) {
  87                 start = stop = *ptr_to_fblock+1;
  88                 while (stop < PED_BE32_TO_CPU(priv_data->vh->total_blocks)
  89                        && stop-start != size) {
  90                         if (TST_BLOC_OCCUPATION(priv_data->alloc_map,stop))
  91                                 start = stop + 1;
  92                         ++stop;
  93                 }
  94                 ok = (stop-start == size);
  95         }
  96
  97         /* new non overlapping room has been found ? */
  98         if (ok) {
  99                 /* enough room */
 100                 PedSector       abs_sector;
 101                 unsigned int    ai, j, block;
 102                 unsigned int    block_sz = (PED_BE32_TO_CPU (
 103                                         priv_data->vh->block_size)
 104                                         / PED_SECTOR_SIZE_DEFAULT);
 105
 106                 if (stop > *ptr_to_fblock && stop <= *ptr_fblock)
 107                         /* Fit in the gap */
 108                         next_to_fblock = stop;
 109                 else
 110                         /* Before or after the gap */
 111                         next_to_fblock = *ptr_to_fblock;
 112
 113                 /* move blocks */
 114                 for (i = 0; i < size; /*i++*/) {
 115                         j = size - i; j = (j < hfsp_block_count) ?
 116                                            j : hfsp_block_count ;
 117
 118                         abs_sector = (PedSector) (*ptr_fblock + i) * block_sz;
 119                         if (!ped_geometry_read (priv_data->plus_geom,
 120                                                 hfsp_block, abs_sector,
 121                                                 block_sz * j))
 122                                 return -1;
 123
 124                         abs_sector = (PedSector) (start + i) * block_sz;
 125                         if (!ped_geometry_write (priv_data->plus_geom,
 126                                                  hfsp_block, abs_sector,
 127                                                  block_sz * j))
 128                                 return -1;
 129
 130                         for (ai = i+j; i < ai; i++) {
 131                                 /* free source block */
 132                                 block = *ptr_fblock + i;
 133                                 CLR_BLOC_OCCUPATION(priv_data->alloc_map,block);
 134                                 SET_BLOC_OCCUPATION(priv_data->dirty_alloc_map,
 135                                                     block/(PED_SECTOR_SIZE_DEFAULT*8));
 136
 137                                 /* set dest block */
 138                                 block = start + i;
 139                                 SET_BLOC_OCCUPATION(priv_data->alloc_map,block);
 140                                 SET_BLOC_OCCUPATION(priv_data->dirty_alloc_map,
 141                                                     block/(PED_SECTOR_SIZE_DEFAULT*8));
 142                         }
 143                 }
 144                 if (!ped_geometry_sync_fast (priv_data->plus_geom))
 145                         return -1;
 146
 147                 *ptr_fblock += size;
 148                 *ptr_to_fblock = next_to_fblock;
 149         } else {
 150                 if (*ptr_fblock != *ptr_to_fblock)
 151                         /* not enough room */
 152                         ped_exception_throw (PED_EXCEPTION_WARNING,
 153                               PED_EXCEPTION_IGNORE,
 154                               _("An extent has not been relocated."));
 155                 start = *ptr_fblock;
 156                 *ptr_fblock = *ptr_to_fblock = start + size;
 157         }
 158
 159         return start;
 160 }
 161
 162 /* Returns 0 on error */
 163 /*         1 on succes */
 164 int
 165 hfsplus_update_vh (PedFileSystem *fs)
 166 {
 167         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
 168                                                 fs->type_specific;
 169         uint8_t                 node[PED_SECTOR_SIZE_DEFAULT];
 170
 171         if (!ped_geometry_read (priv_data->plus_geom, node, 2, 1))
 172                 return 0;
 173         memcpy (node, priv_data->vh, sizeof (HfsPVolumeHeader));
 174         if (!ped_geometry_write (priv_data->plus_geom, node, 2, 1)
 175             || !ped_geometry_write (priv_data->plus_geom, node,
 176                                  priv_data->plus_geom->length - 2, 1)
 177             || !ped_geometry_sync_fast (priv_data->plus_geom))
 178                 return 0;
 179         return 1;
 180 }
 181
 182 static int
 183 hfsplus_do_move (PedFileSystem* fs, unsigned int *ptr_src,
 184                  unsigned int *ptr_dest, HfsCPrivateCache* cache,
 185                  HfsCPrivateExtent* ref)
 186 {
 187         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
 188                                                 fs->type_specific;
 189         HfsPPrivateFile*        file;
 190         HfsPExtDescriptor*      extent;
 191         HfsCPrivateExtent*      move;
 192         int                     new_start;
 193
 194         new_start = hfsplus_effect_move_extent (fs, ptr_src, ptr_dest,
 195                                                 ref->ext_length);
 196
 197         if (new_start == -1) return -1;
 198
 199         if (ref->ext_start != (unsigned) new_start) {
 200                 switch (ref->where) {
 201                 /************ VH ************/
 202                     case CR_PRIM_CAT :
 203                         priv_data->catalog_file
 204                         ->first[ref->ref_index].start_block =
 205                                 PED_CPU_TO_BE32(new_start);
 206                         goto CR_PRIM;
 207                     case CR_PRIM_EXT :
 208                         priv_data->extents_file
 209                         ->first[ref->ref_index].start_block =
 210                                 PED_CPU_TO_BE32(new_start);
 211                         goto CR_PRIM;
 212                     case CR_PRIM_ATTR :
 213                         priv_data->attributes_file
 214                         ->first[ref->ref_index].start_block =
 215                                 PED_CPU_TO_BE32(new_start);
 216                         goto CR_PRIM;
 217                     case CR_PRIM_ALLOC :
 218                         priv_data->allocation_file
 219                         ->first[ref->ref_index].start_block =
 220                                 PED_CPU_TO_BE32(new_start);
 221                         goto CR_PRIM;
 222                     case CR_PRIM_START :
 223                         /* No startup file opened */
 224                     CR_PRIM :
 225                         extent = ( HfsPExtDescriptor* )
 226                                  ( (uint8_t*)priv_data->vh + ref->ref_offset );
 227                         extent[ref->ref_index].start_block =
 228                                 PED_CPU_TO_BE32(new_start);
 229                         if (!hfsplus_update_vh(fs))
 230                                 return -1;
 231                         break;
 232
 233                 /************** BTREE *************/
 234                     case CR_BTREE_CAT_JIB :
 235                         if (!hfsj_update_jib(fs, new_start))
 236                                 return -1;
 237                         goto BTREE_CAT;
 238
 239                     case CR_BTREE_CAT_JL :
 240                         if (!hfsj_update_jl(fs, new_start))
 241                                 return -1;
 242                         goto BTREE_CAT;
 243
 244                     BTREE_CAT:
 245                     case CR_BTREE_CAT :
 246                         file = priv_data->catalog_file;
 247                         goto CR_BTREE;
 248
 249                     case CR_BTREE_ATTR :
 250                         file = priv_data->attributes_file;
 251                         goto CR_BTREE;
 252
 253                     case CR_BTREE_EXT_ATTR :
 254                         if (priv_data->attributes_file
 255                             ->cache[ref->ref_index].start_block
 256                             == PED_CPU_TO_BE32(ref->ext_start))
 257                                 priv_data->attributes_file
 258                                 ->cache[ref->ref_index].start_block =
 259                                 PED_CPU_TO_BE32(new_start);
 260                         goto CR_BTREE_EXT;
 261                     case CR_BTREE_EXT_CAT :
 262                         if (priv_data->catalog_file
 263                             ->cache[ref->ref_index].start_block
 264                             == PED_CPU_TO_BE32(ref->ext_start))
 265                                 priv_data->catalog_file
 266                                 ->cache[ref->ref_index].start_block =
 267                                 PED_CPU_TO_BE32(new_start);
 268                         goto CR_BTREE_EXT;
 269                     case CR_BTREE_EXT_ALLOC :
 270                         if (priv_data->allocation_file
 271                             ->cache[ref->ref_index].start_block
 272                             == PED_CPU_TO_BE32(ref->ext_start))
 273                                 priv_data->allocation_file
 274                                 ->cache[ref->ref_index].start_block =
 275                                 PED_CPU_TO_BE32(new_start);
 276                         goto CR_BTREE_EXT;
 277                     case CR_BTREE_EXT_START :
 278                         /* No startup file opened */
 279                     CR_BTREE_EXT :
 280                     case CR_BTREE_EXT_0 :
 281                         file = priv_data->extents_file;
 282
 283                     CR_BTREE :
 284                         PED_ASSERT(PED_SECTOR_SIZE_DEFAULT * ref->sect_by_block
 285                                    > ref->ref_offset, return -1 );
 286                         if (!hfsplus_file_read(file, hfsp_block,
 287                                 (PedSector)ref->ref_block * ref->sect_by_block,
 288                                 ref->sect_by_block))
 289                                 return -1;
 290                         extent = ( HfsPExtDescriptor* )
 291                                 ( hfsp_block + ref->ref_offset );
 292                         extent[ref->ref_index].start_block =
 293                                 PED_CPU_TO_BE32(new_start);
 294                         if (!hfsplus_file_write(file, hfsp_block,
 295                                 (PedSector)ref->ref_block * ref->sect_by_block,
 296                                 ref->sect_by_block)
 297                             || !ped_geometry_sync_fast (priv_data->plus_geom))
 298                                 return -1;
 299                         break;
 300
 301                     /********** BUG *********/
 302                     default :
 303                         ped_exception_throw (
 304                                 PED_EXCEPTION_ERROR,
 305                                 PED_EXCEPTION_CANCEL,
 306                                 _("A reference to an extent comes from a place "
 307                                   "it should not.  You should check the file "
 308                                   "system!"));
 309                         return -1;
 310                         break;
 311                 }
 312
 313                 move = hfsc_cache_move_extent(cache, ref->ext_start, new_start);
 314                 if (!move) return -1;
 315                 PED_ASSERT(move == ref, return -1);
 316         }
 317
 318         return new_start;
 319 }
 320
 321 /* save any dirty sector of the allocation bitmap file */
 322 static int
 323 hfsplus_save_allocation(PedFileSystem *fs)
 324 {
 325         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
 326                                                 fs->type_specific;
 327         unsigned int            map_sectors, i, j;
 328         int                     ret = 1;
 329
 330         map_sectors = ( PED_BE32_TO_CPU (priv_data->vh->total_blocks)
 331                         + PED_SECTOR_SIZE_DEFAULT * 8 - 1 ) / (PED_SECTOR_SIZE_DEFAULT * 8);
 332
 333         for (i = 0; i < map_sectors;) {
 334                 for (j = i;
 335                      (TST_BLOC_OCCUPATION(priv_data->dirty_alloc_map,j));
 336                      ++j)
 337                         CLR_BLOC_OCCUPATION(priv_data->dirty_alloc_map,j);
 338                 if (j-i) {
 339                         ret = hfsplus_file_write(priv_data->allocation_file,
 340                                     priv_data->alloc_map + i * PED_SECTOR_SIZE_DEFAULT,
 341                                     i, j-i) && ret;
 342                         i = j;
 343                 } else
 344                         ++i;
 345         }
 346
 347         return ret;
 348 }
 349
 350 /* This function moves an extent starting at block fblock
 351    to block to_fblock if there's enough room */
 352 /* Return 1 if everything was fine */
 353 /* Return -1 if an error occurred */
 354 /* Return 0 if no extent was found */
 355 static int
 356 hfsplus_move_extent_starting_at (PedFileSystem *fs, unsigned int *ptr_fblock,
 357                                  unsigned int *ptr_to_fblock,
 358                                  HfsCPrivateCache* cache)
 359 {
 360         HfsCPrivateExtent*      ref;
 361         unsigned int            old_start, new_start;
 362
 363         ref = hfsc_cache_search_extent(cache, *ptr_fblock);
 364         if (!ref) return 0;
 365
 366         old_start = *ptr_fblock;
 367         new_start = hfsplus_do_move(fs, ptr_fblock, ptr_to_fblock, cache, ref);
 368         if (new_start == (unsigned)-1) return -1;
 369         if (new_start > old_start) {
 370                 new_start = hfsplus_do_move(fs, &new_start, ptr_to_fblock,
 371                                             cache, ref);
 372                 if (new_start == (unsigned)-1 || new_start > old_start)
 373                         return -1;
 374         }
 375
 376         hfsplus_save_allocation(fs);
 377         return 1;
 378 }
 379
 380 static int
 381 hfsplus_cache_from_vh(HfsCPrivateCache* cache, PedFileSystem* fs,
 382                       PedTimer* timer)
 383 {
 384         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
 385                                                 fs->type_specific;
 386         HfsPExtDescriptor*      extent;
 387         unsigned int            j;
 388
 389         extent = priv_data->vh->allocation_file.extents;
 390         for (j = 0; j < HFSP_EXT_NB; ++j) {
 391                 if (!extent[j].block_count) break;
 392                 if (!hfsc_cache_add_extent(
 393                         cache,
 394                         PED_BE32_TO_CPU(extent[j].start_block),
 395                         PED_BE32_TO_CPU(extent[j].block_count),
 396                         0, /* unused for vh */
 397                         ((uint8_t*)extent) - ((uint8_t*)priv_data->vh),
 398                         1, /* load / save 1 sector */
 399                         CR_PRIM_ALLOC,
 400                         j )
 401                    )
 402                         return 0;
 403         }
 404
 405         extent = priv_data->vh->extents_file.extents;
 406         for (j = 0; j < HFSP_EXT_NB; ++j) {
 407                 if (!extent[j].block_count) break;
 408                 if (!hfsc_cache_add_extent(
 409                         cache,
 410                         PED_BE32_TO_CPU(extent[j].start_block),
 411                         PED_BE32_TO_CPU(extent[j].block_count),
 412                         0, /* unused for vh */
 413                         ((uint8_t*)extent) - ((uint8_t*)priv_data->vh),
 414                         1, /* load / save 1 sector */
 415                         CR_PRIM_EXT,
 416                         j )
 417                    )
 418                         return 0;
 419         }
 420
 421         extent = priv_data->vh->catalog_file.extents;
 422         for (j = 0; j < HFSP_EXT_NB; ++j) {
 423                 if (!extent[j].block_count) break;
 424                 if (!hfsc_cache_add_extent(
 425                         cache,
 426                         PED_BE32_TO_CPU(extent[j].start_block),
 427                         PED_BE32_TO_CPU(extent[j].block_count),
 428                         0, /* unused for vh */
 429                         ((uint8_t*)extent) - ((uint8_t*)priv_data->vh),
 430                         1, /* load / save 1 sector */
 431                         CR_PRIM_CAT,
 432                         j )
 433                    )
 434                         return 0;
 435         }
 436
 437         extent = priv_data->vh->attributes_file.extents;
 438         for (j = 0; j < HFSP_EXT_NB; ++j) {
 439                 if (!extent[j].block_count) break;
 440                 if (!hfsc_cache_add_extent(
 441                         cache,
 442                         PED_BE32_TO_CPU(extent[j].start_block),
 443                         PED_BE32_TO_CPU(extent[j].block_count),
 444                         0, /* unused for vh */
 445                         ((uint8_t*)extent) - ((uint8_t*)priv_data->vh),
 446                         1, /* load / save 1 sector */
 447                         CR_PRIM_ATTR,
 448                         j )
 449                    )
 450                         return 0;
 451         }
 452
 453         extent = priv_data->vh->startup_file.extents;
 454         for (j = 0; j < HFSP_EXT_NB; ++j) {
 455                 if (!extent[j].block_count) break;
 456                 if (!hfsc_cache_add_extent(
 457                         cache,
 458                         PED_BE32_TO_CPU(extent[j].start_block),
 459                         PED_BE32_TO_CPU(extent[j].block_count),
 460                         0, /* unused for vh */
 461                         ((uint8_t*)extent) - ((uint8_t*)priv_data->vh),
 462                         1, /* load / save 1 sector */
 463                         CR_PRIM_START,
 464                         j )
 465                    )
 466                         return 0;
 467         }
 468
 469         return 1;
 470 }
 471
 472 static int
 473 hfsplus_cache_from_catalog(HfsCPrivateCache* cache, PedFileSystem* fs,
 474                            PedTimer* timer)
 475 {
 476         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
 477                                                 fs->type_specific;
 478         uint8_t                 node_1[PED_SECTOR_SIZE_DEFAULT];
 479         uint8_t*                node;
 480         HfsPHeaderRecord*       header;
 481         HfsPCatalogKey*         catalog_key;
 482         HfsPCatalog*            catalog_data;
 483         HfsPExtDescriptor*      extent;
 484         unsigned int            leaf_node, record_number;
 485         unsigned int            i, j, size, bsize;
 486         uint32_t                jib = priv_data->jib_start_block,
 487                                 jl  = priv_data->jl_start_block;
 488
 489         if (!priv_data->catalog_file->sect_nb) {
 490                 ped_exception_throw (
 491                         PED_EXCEPTION_INFORMATION,
 492                         PED_EXCEPTION_OK,
 493                         _("This HFS+ volume has no catalog file.  "
 494                           "This is very unusual!"));
 495                 return 1;
 496         }
 497
 498         /* Search the extent starting at *ptr_block in the catalog file */
 499         if (!hfsplus_file_read_sector (priv_data->catalog_file, node_1, 0))
 500                 return 0;
 501         header = (HfsPHeaderRecord*) (node_1 + HFS_FIRST_REC);
 502         leaf_node = PED_BE32_TO_CPU (header->first_leaf_node);
 503         bsize = PED_BE16_TO_CPU (header->node_size);
 504         size = bsize / PED_SECTOR_SIZE_DEFAULT;
 505         PED_ASSERT(size < 256, return 0);
 506
 507         node = (uint8_t*) ped_malloc(bsize);
 508         if (!node) return 0;
 509         HfsPNodeDescriptor *desc = (HfsPNodeDescriptor*) node;
 510
 511         for (; leaf_node; leaf_node = PED_BE32_TO_CPU (desc->next)) {
 512                 if (!hfsplus_file_read (priv_data->catalog_file, node,
 513                                         (PedSector) leaf_node * size, size)) {
 514                         free (node);
 515                         return 0;
 516                 }
 517                 record_number = PED_BE16_TO_CPU (desc->rec_nb);
 518                 for (i = 1; i <= record_number; i++) {
 519                         unsigned int    skip;
 520                         uint8_t         where;
 521
 522                         catalog_key = (HfsPCatalogKey*)
 523                             ( node + PED_BE16_TO_CPU (*((uint16_t *)
 524                                         (node+(bsize - 2*i)))) );
 525                         skip = ( 2 + PED_BE16_TO_CPU (catalog_key->key_length)
 526                                  + 1) & ~1;
 527                         catalog_data = (HfsPCatalog*)
 528                                             (((uint8_t*)catalog_key) + skip);
 529                         /* check for obvious error in FS */
 530                         if (((uint8_t*)catalog_key - node < HFS_FIRST_REC)
 531                             || ((uint8_t*)catalog_data - node
 532                                 >= (signed) bsize
 533                                    - 2 * (signed)(record_number+1))) {
 534                                 ped_exception_throw (
 535                                         PED_EXCEPTION_ERROR,
 536                                         PED_EXCEPTION_CANCEL,
 537                                         _("The file system contains errors."));
 538                                 free (node);
 539                                 return 0;
 540                         }
 541
 542                         if (PED_BE16_TO_CPU(catalog_data->type)!=HFS_CAT_FILE)
 543                                 continue;
 544
 545                         extent = catalog_data->sel.file.data_fork.extents;
 546                         for (j = 0; j < HFSP_EXT_NB; ++j) {
 547                                 if (!extent[j].block_count) break;
 548                                 where = CR_BTREE_CAT;
 549                                 if ( PED_BE32_TO_CPU(extent[j].start_block)
 550                                      == jib ) {
 551                                         jib = 0;
 552                                         where = CR_BTREE_CAT_JIB;
 553                                 } else
 554                                   if ( PED_BE32_TO_CPU(extent[j].start_block)
 555                                        == jl ) {
 556                                         jl = 0;
 557                                         where = CR_BTREE_CAT_JL;
 558                                 }
 559                                 if (!hfsc_cache_add_extent(
 560                                         cache,
 561                                         PED_BE32_TO_CPU(extent[j].start_block),
 562                                         PED_BE32_TO_CPU(extent[j].block_count),
 563                                         leaf_node,
 564                                         (uint8_t*)extent - node,
 565                                         size,
 566                                         where,
 567                                         j )
 568                                    ) {
 569                                         free (node);
 570                                         return 0;
 571                                 }
 572                         }
 573
 574                         extent = catalog_data->sel.file.res_fork.extents;
 575                         for (j = 0; j < HFSP_EXT_NB; ++j) {
 576                                 if (!extent[j].block_count) break;
 577                                 if (!hfsc_cache_add_extent(
 578                                         cache,
 579                                         PED_BE32_TO_CPU(extent[j].start_block),
 580                                         PED_BE32_TO_CPU(extent[j].block_count),
 581                                         leaf_node,
 582                                         (uint8_t*)extent - node,
 583                                         size,
 584                                         CR_BTREE_CAT,
 585                                         j )
 586                                    ) {
 587                                         free (node);
 588                                         return 0;
 589                                 }
 590                         }
 591                 }
 592         }
 593
 594         free (node);
 595         return 1;
 596 }
 597
 598 static int
 599 hfsplus_cache_from_extent(HfsCPrivateCache* cache, PedFileSystem* fs,
 600                           PedTimer* timer)
 601 {
 602         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
 603                                                 fs->type_specific;
 604         uint8_t                 node_1[PED_SECTOR_SIZE_DEFAULT];
 605         uint8_t*                node;
 606         HfsPHeaderRecord*       header;
 607         HfsPExtentKey*          extent_key;
 608         HfsPExtDescriptor*      extent;
 609         unsigned int            leaf_node, record_number;
 610         unsigned int            i, j, size, bsize;
 611
 612         if (!priv_data->extents_file->sect_nb) {
 613                 ped_exception_throw (
 614                         PED_EXCEPTION_INFORMATION,
 615                         PED_EXCEPTION_OK,
 616                         _("This HFS+ volume has no extents overflow "
 617                           "file.  This is quite unusual!"));
 618                 return 1;
 619         }
 620
 621         if (!hfsplus_file_read_sector (priv_data->extents_file, node_1, 0))
 622                 return 0;
 623         header = ((HfsPHeaderRecord*) (node_1 + HFS_FIRST_REC));
 624         leaf_node = PED_BE32_TO_CPU (header->first_leaf_node);
 625         bsize = PED_BE16_TO_CPU (header->node_size);
 626         size = bsize / PED_SECTOR_SIZE_DEFAULT;
 627         PED_ASSERT(size < 256, return 0);
 628
 629         node = (uint8_t*) ped_malloc (bsize);
 630         if (!node) return -1;
 631         HfsPNodeDescriptor *desc = (HfsPNodeDescriptor*) node;
 632
 633         for (; leaf_node; leaf_node = PED_BE32_TO_CPU (desc->next)) {
 634                 if (!hfsplus_file_read (priv_data->extents_file, node,
 635                                         (PedSector) leaf_node * size, size)) {
 636                         free (node);
 637                         return 0;
 638                 }
 639                 record_number = PED_BE16_TO_CPU (desc->rec_nb);
 640                 for (i = 1; i <= record_number; i++) {
 641                         uint8_t where;
 642                         extent_key = (HfsPExtentKey*)
 643                             (node + PED_BE16_TO_CPU(*((uint16_t *)
 644                                             (node+(bsize - 2*i)))));
 645                         extent = (HfsPExtDescriptor*)
 646                             (((uint8_t*)extent_key) + sizeof (HfsPExtentKey));
 647                         /* check for obvious error in FS */
 648                         if (((uint8_t*)extent_key - node < HFS_FIRST_REC)
 649                             || ((uint8_t*)extent - node
 650                                 >= (signed)bsize
 651                                    - 2 * (signed)(record_number+1))) {
 652                                 ped_exception_throw (
 653                                         PED_EXCEPTION_ERROR,
 654                                         PED_EXCEPTION_CANCEL,
 655                                         _("The file system contains errors."));
 656                                 free (node);
 657                                 return -1;
 658                         }
 659
 660                         switch (extent_key->file_ID) {
 661                             case PED_CPU_TO_BE32 (HFS_XTENT_ID) :
 662                                 if (ped_exception_throw (
 663                                         PED_EXCEPTION_WARNING,
 664                                         PED_EXCEPTION_IGNORE_CANCEL,
 665                                         _("The extents overflow file should not"
 666                                         " contain its own extents!  You should "
 667                                         "check the file system."))
 668                                                 != PED_EXCEPTION_IGNORE)
 669                                         return 0;
 670                                 where = CR_BTREE_EXT_EXT;
 671                                 break;
 672                             case PED_CPU_TO_BE32 (HFS_CATALOG_ID) :
 673                                 where = CR_BTREE_EXT_CAT;
 674                                 break;
 675                             case PED_CPU_TO_BE32 (HFSP_ALLOC_ID) :
 676                                 where = CR_BTREE_EXT_ALLOC;
 677                                 break;
 678                             case PED_CPU_TO_BE32 (HFSP_STARTUP_ID) :
 679                                 where = CR_BTREE_EXT_START;
 680                                 break;
 681                             case PED_CPU_TO_BE32 (HFSP_ATTRIB_ID) :
 682                                 where = CR_BTREE_EXT_ATTR;
 683                                 break;
 684                             default :
 685                                 where = CR_BTREE_EXT_0;
 686                                 break;
 687                         }
 688
 689                         for (j = 0; j < HFSP_EXT_NB; ++j) {
 690                                 if (!extent[j].block_count) break;
 691                                 if (!hfsc_cache_add_extent(
 692                                         cache,
 693                                         PED_BE32_TO_CPU(extent[j].start_block),
 694                                         PED_BE32_TO_CPU(extent[j].block_count),
 695                                         leaf_node,
 696                                         (uint8_t*)extent - node,
 697                                         size,
 698                                         where,
 699                                         j )
 700                                    ) {
 701                                         free (node);
 702                                         return 0;
 703                                 }
 704                         }
 705                 }
 706         }
 707
 708         free (node);
 709         return 1;
 710 }
 711
 712 static int
 713 hfsplus_cache_from_attributes(HfsCPrivateCache* cache, PedFileSystem* fs,
 714                               PedTimer* timer)
 715 {
 716         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
 717                                                 fs->type_specific;
 718         uint8_t                 node_1[PED_SECTOR_SIZE_DEFAULT];
 719         uint8_t*                node;
 720         HfsPHeaderRecord*       header;
 721         HfsPPrivateGenericKey*  generic_key;
 722         HfsPForkDataAttr*       fork_ext_data;
 723         HfsPExtDescriptor*      extent;
 724         unsigned int            leaf_node, record_number;
 725         unsigned int            i, j, size, bsize;
 726
 727         /* attributes file is facultative */
 728         if (!priv_data->attributes_file->sect_nb)
 729                 return 1;
 730
 731         /* Search the extent starting at *ptr_block in the catalog file */
 732         if (!hfsplus_file_read_sector (priv_data->attributes_file, node_1, 0))
 733                 return 0;
 734         header = ((HfsPHeaderRecord*) (node_1 + HFS_FIRST_REC));
 735         leaf_node = PED_BE32_TO_CPU (header->first_leaf_node);
 736         bsize = PED_BE16_TO_CPU (header->node_size);
 737         size = bsize / PED_SECTOR_SIZE_DEFAULT;
 738         PED_ASSERT(size < 256, return 0);
 739
 740         node = (uint8_t*) ped_malloc(bsize);
 741         if (!node) return 0;
 742         HfsPNodeDescriptor *desc = (HfsPNodeDescriptor*) node;
 743
 744         for (; leaf_node; leaf_node = PED_BE32_TO_CPU (desc->next)) {
 745                 if (!hfsplus_file_read (priv_data->attributes_file, node,
 746                                         (PedSector) leaf_node * size, size)) {
 747                         free (node);
 748                         return 0;
 749                 }
 750                 record_number = PED_BE16_TO_CPU (desc->rec_nb);
 751                 for (i = 1; i <= record_number; i++) {
 752                         unsigned int    skip;
 753                         generic_key = (HfsPPrivateGenericKey*)
 754                                 (node + PED_BE16_TO_CPU(*((uint16_t *)
 755                                             (node+(bsize - 2*i)))));
 756                         skip = ( 2 + PED_BE16_TO_CPU (generic_key->key_length)
 757                                  + 1 ) & ~1;
 758                         fork_ext_data = (HfsPForkDataAttr*)
 759                                             (((uint8_t*)generic_key) + skip);
 760                         /* check for obvious error in FS */
 761                         if (((uint8_t*)generic_key - node < HFS_FIRST_REC)
 762                             || ((uint8_t*)fork_ext_data - node
 763                                 >= (signed) bsize
 764                                    - 2 * (signed)(record_number+1))) {
 765                                 ped_exception_throw (
 766                                         PED_EXCEPTION_ERROR,
 767                                         PED_EXCEPTION_CANCEL,
 768                                         _("The file system contains errors."));
 769                                 free (node);
 770                                 return 0;
 771                         }
 772
 773                         if (fork_ext_data->record_type
 774                             == PED_CPU_TO_BE32 ( HFSP_ATTR_FORK ) ) {
 775                                 extent = fork_ext_data->fork_res.fork.extents;
 776                                 for (j = 0; j < HFSP_EXT_NB; ++j) {
 777                                         if (!extent[j].block_count) break;
 778                                         if (!hfsc_cache_add_extent(
 779                                                 cache,
 780                                                 PED_BE32_TO_CPU (
 781                                                         extent[j].start_block ),
 782                                                 PED_BE32_TO_CPU (
 783                                                         extent[j].block_count ),
 784                                                 leaf_node,
 785                                                 (uint8_t*)extent-node,
 786                                                 size,
 787                                                 CR_BTREE_ATTR,
 788                                                 j )
 789                                            ) {
 790                                                 free(node);
 791                                                 return 0;
 792                                         }
 793                                 }
 794                         } else if (fork_ext_data->record_type
 795                             == PED_CPU_TO_BE32 ( HFSP_ATTR_EXTENTS ) ) {
 796                                 extent = fork_ext_data->fork_res.extents;
 797                                 for (j = 0; j < HFSP_EXT_NB; ++j) {
 798                                         if (!extent[j].block_count) break;
 799                                         if (!hfsc_cache_add_extent(
 800                                                 cache,
 801                                                 PED_BE32_TO_CPU (
 802                                                         extent[j].start_block ),
 803                                                 PED_BE32_TO_CPU (
 804                                                         extent[j].block_count ),
 805                                                 leaf_node,
 806                                                 (uint8_t*)extent-node,
 807                                                 size,
 808                                                 CR_BTREE_ATTR,
 809                                                 j )
 810                                            ) {
 811                                                 free(node);
 812                                                 return 0;
 813                                         }
 814                                 }
 815                         } else continue;
 816                 }
 817         }
 818
 819         free (node);
 820         return 1;
 821 }
 822
 823 static HfsCPrivateCache*
 824 hfsplus_cache_extents(PedFileSystem* fs, PedTimer* timer)
 825 {
 826         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
 827                                                 fs->type_specific;
 828         HfsCPrivateCache*       ret;
 829         unsigned int            file_number, block_number;
 830
 831         file_number = PED_BE32_TO_CPU(priv_data->vh->file_count);
 832         block_number = PED_BE32_TO_CPU(priv_data->vh->total_blocks);
 833         ret = hfsc_new_cache(block_number, file_number);
 834         if (!ret) return NULL;
 835
 836         if (!hfsplus_cache_from_vh(ret, fs, timer) ||
 837             !hfsplus_cache_from_catalog(ret, fs, timer) ||
 838             !hfsplus_cache_from_extent(ret, fs, timer) ||
 839             !hfsplus_cache_from_attributes(ret, fs, timer)) {
 840                 ped_exception_throw(
 841                         PED_EXCEPTION_ERROR,
 842                         PED_EXCEPTION_CANCEL,
 843                         _("Could not cache the file system in memory."));
 844                 hfsc_delete_cache(ret);
 845                 return NULL;
 846         }
 847
 848         return ret;
 849 }
 850
 851 /* This function moves file's data to compact used and free space,
 852    starting at fblock block */
 853 /* return 0 on error */
 854 int
 855 hfsplus_pack_free_space_from_block (PedFileSystem *fs, unsigned int fblock,
 856                                     PedTimer* timer, unsigned int to_free)
 857 {
 858         PedSector               bytes_buff;
 859         HfsPPrivateFSData*      priv_data = (HfsPPrivateFSData*)
 860                                                 fs->type_specific;
 861         HfsPVolumeHeader*       vh = priv_data->vh;
 862         HfsCPrivateCache*       cache;
 863         unsigned int            to_fblock = fblock;
 864         unsigned int            start = fblock;
 865         unsigned int            divisor = PED_BE32_TO_CPU (vh->total_blocks)
 866                                           + 1 - start - to_free;
 867         int                     ret;
 868
 869         PED_ASSERT (!hfsp_block, return 0);
 870
 871         cache = hfsplus_cache_extents (fs, timer);
 872         if (!cache)
 873                 return 0;
 874
 875         /* Calculate the size of the copy buffer :
 876          * Takes BLOCK_MAX_BUFF HFS blocks, but if > BYTES_MAX_BUFF
 877          * takes the maximum number of HFS blocks so that the buffer
 878          * will remain smaller than or equal to BYTES_MAX_BUFF, with
 879          * a minimum of 1 HFS block */
 880         bytes_buff = PED_BE32_TO_CPU (priv_data->vh->block_size)
 881                      * (PedSector) BLOCK_MAX_BUFF;
 882         if (bytes_buff > BYTES_MAX_BUFF) {
 883                 hfsp_block_count = BYTES_MAX_BUFF
 884                                  / PED_BE32_TO_CPU (priv_data->vh->block_size);
 885                 if (!hfsp_block_count)
 886                         hfsp_block_count = 1;
 887                 bytes_buff = (PedSector) hfsp_block_count
 888                              * PED_BE32_TO_CPU (priv_data->vh->block_size);
 889         } else
 890                 hfsp_block_count = BLOCK_MAX_BUFF;
 891
 892         /* If the cache code requests more space, give it to him */
 893         if (bytes_buff < hfsc_cache_needed_buffer (cache))
 894                 bytes_buff = hfsc_cache_needed_buffer (cache);
 895
 896         hfsp_block = (uint8_t*) ped_malloc (bytes_buff);
 897         if (!hfsp_block)
 898                 goto error_cache;
 899
 900         if (!hfsplus_read_bad_blocks (fs)) {
 901                 ped_exception_throw (
 902                         PED_EXCEPTION_ERROR,
 903                         PED_EXCEPTION_CANCEL,
 904                         _("Bad blocks list could not be loaded."));
 905                 goto error_alloc;
 906         }
 907
 908         while ( fblock < ( priv_data->plus_geom->length - 2 )
 909                          / ( PED_BE32_TO_CPU (vh->block_size)
 910                              / PED_SECTOR_SIZE_DEFAULT ) ) {
 911                 if (TST_BLOC_OCCUPATION (priv_data->alloc_map, fblock)
 912                     && (!hfsplus_is_bad_block (fs, fblock))) {
 913                         if (!(ret = hfsplus_move_extent_starting_at (fs,
 914                                                 &fblock, &to_fblock, cache)))
 915                                 to_fblock = ++fblock;
 916                         else if (ret == -1) {
 917                                 ped_exception_throw (
 918                                         PED_EXCEPTION_ERROR,
 919                                         PED_EXCEPTION_CANCEL,
 920                                         _("An error occurred during extent "
 921                                           "relocation."));
 922                                 goto error_alloc;
 923                         }
 924                 } else {
 925                         fblock++;
 926                 }
 927
 928                 ped_timer_update(timer, (float)(to_fblock - start) / divisor);
 929         }
 930
 931         free (hfsp_block); hfsp_block = NULL; hfsp_block_count = 0;
 932         hfsc_delete_cache (cache);
 933         return 1;
 934
 935 error_alloc:
 936         free (hfsp_block); hfsp_block = NULL; hfsp_block_count = 0;
 937 error_cache:
 938         hfsc_delete_cache (cache);
 939         return 0;
 940 }
 941
 942 #endif /* !DISCOVER_ONLY */