libparted/fs/r/hfs/advfs.c

   1 /*
   2     libparted - a library for manipulating disk partitions
   3     Copyright (C) 2004-2005, 2007, 2009-2012 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.h"
  37
  38 #include "advfs.h"
  39
  40 /* - if a < b, 0 if a == b, + if a > b */
  41 /* Comparaison is done in the following order : */
  42 /* CNID, then fork type, then start block */
  43 /* Note that HFS implementation in linux has a bug */
  44 /* in this function */
  45 static int
  46 hfs_extent_key_cmp(HfsPrivateGenericKey* a, HfsPrivateGenericKey* b)
  47 {
  48         HfsExtentKey* key1 = (HfsExtentKey*) a;
  49         HfsExtentKey* key2 = (HfsExtentKey*) b;
  50
  51         /* do NOT use a substraction, because */
  52         /* 0xFFFFFFFF - 1 = 0xFFFFFFFE so this */
  53         /* would return -2, despite the fact */
  54         /* 0xFFFFFFFF > 1 !!! (this is the 2.4 bug) */
  55         if (key1->file_ID != key2->file_ID)
  56                 return PED_BE32_TO_CPU(key1->file_ID) <
  57                        PED_BE32_TO_CPU(key2->file_ID) ?
  58                                 -1 : +1;
  59
  60         if (key1->type != key2->type)
  61                 return (int)(key1->type - key2->type);
  62
  63         if (key1->start == key2->start)
  64                 return 0;
  65         /* the whole thing wont work with 16 bits ints */
  66         /* anyway */
  67         return (int)( PED_BE16_TO_CPU(key1->start) -
  68                       PED_BE16_TO_CPU(key2->start) );
  69 }
  70
  71 /* do a B-Tree lookup */
  72 /* read the first record immediatly inferior or egal to the given key */
  73 /* return 0 on error */
  74 /* record_out _must_ be large enough to receive record_size bytes */
  75 /* WARNING : the compare function called only handle Extents BTree */
  76 /*           so modify this function if you want to do lookup in */
  77 /*           other BTrees has well */
  78 int
  79 hfs_btree_search (HfsPrivateFile* b_tree_file, HfsPrivateGenericKey* key,
  80                   void *record_out, unsigned int record_size,
  81                   HfsCPrivateLeafRec* record_ref)
  82 {
  83         uint8_t                 node[PED_SECTOR_SIZE_DEFAULT];
  84         HfsHeaderRecord*        header;
  85         HfsNodeDescriptor*      desc = (HfsNodeDescriptor*) node;
  86         HfsPrivateGenericKey*   record_key = NULL;
  87         unsigned int            node_number, record_number;
  88         int                     i;
  89
  90         /* Read the header node */
  91         if (!hfs_file_read_sector(b_tree_file, node, 0))
  92                 return 0;
  93         header = ((HfsHeaderRecord*) (node + PED_BE16_TO_CPU(*((uint16_t *)
  94                                                 (node+(PED_SECTOR_SIZE_DEFAULT-2))))));
  95
  96         /* Get the node number of the root */
  97         node_number = PED_BE32_TO_CPU(header->root_node);
  98         if (!node_number)
  99                 return 0;
 100
 101         /* Read the root node */
 102         if (!hfs_file_read_sector(b_tree_file, node, node_number))
 103                 return 0;
 104
 105         /* Follow the white rabbit */
 106         while (1) {
 107                 record_number = PED_BE16_TO_CPU (desc->rec_nb);
 108                 for (i = record_number; i; i--) {
 109                         record_key = (HfsPrivateGenericKey*)
 110                                 (node + PED_BE16_TO_CPU(*((uint16_t *)
 111                                             (node+(PED_SECTOR_SIZE_DEFAULT - 2*i)))));
 112                         /* check for obvious error in FS */
 113                         if (((uint8_t*)record_key - node < HFS_FIRST_REC)
 114                             || ((uint8_t*)record_key - node
 115                                 >= PED_SECTOR_SIZE_DEFAULT
 116                                    - 2 * (signed)(record_number+1))) {
 117                                 ped_exception_throw (
 118                                         PED_EXCEPTION_ERROR,
 119                                         PED_EXCEPTION_CANCEL,
 120                                         _("The file system contains errors."));
 121                                 return 0;
 122                         }
 123                         if (hfs_extent_key_cmp(record_key, key) <= 0)
 124                                 break;
 125                 }
 126                 if (!i) return 0;
 127                 if (desc->type == HFS_IDX_NODE) {
 128                         unsigned int    skip;
 129
 130                         skip = (1 + record_key->key_length + 1) & ~1;
 131                         node_number = PED_BE32_TO_CPU (*((uint32_t *)
 132                                         (((uint8_t *) record_key) + skip)));
 133                         if (!hfs_file_read_sector(b_tree_file, node,
 134                                                   node_number))
 135                                 return 0;
 136                 } else
 137                         break;
 138         }
 139
 140         /* copy the result if needed */
 141         if (record_size)
 142                 memcpy (record_out, record_key, record_size);
 143
 144         /* send record reference if needed */
 145         if (record_ref) {
 146                 record_ref->node_size = 1;      /* in sectors */
 147                 record_ref->node_number = node_number;
 148                 record_ref->record_pos = (uint8_t*)record_key - node;
 149                 record_ref->record_number = i;
 150         }
 151
 152         /* success */
 153         return 1;
 154 }
 155
 156 /* free the bad blocks linked list */
 157 void
 158 hfs_free_bad_blocks_list(HfsPrivateLinkExtent* first)
 159 {
 160         HfsPrivateLinkExtent*   next;
 161
 162         while (first) {
 163                 next = first->next;
 164                 free (first);
 165                 first = next;
 166         }
 167 }
 168
 169 /* This function reads bad blocks extents in the extents file
 170    and store it in f.s. specific data of fs */
 171 int
 172 hfs_read_bad_blocks (const PedFileSystem *fs)
 173 {
 174         HfsPrivateFSData*       priv_data = (HfsPrivateFSData*)
 175                                                 fs->type_specific;
 176
 177         if (priv_data->bad_blocks_loaded)
 178                 return 1;
 179
 180         {
 181         uint8_t                 record[sizeof (HfsExtentKey)
 182                                                + sizeof (HfsExtDataRec)];
 183         HfsExtentKey            search;
 184         HfsExtentKey*           ret_key = (HfsExtentKey*) record;
 185         HfsExtDescriptor*       ret_cache = (HfsExtDescriptor*)
 186                                              (record + sizeof (HfsExtentKey));
 187         unsigned int            block, last_start, first_pass = 1;
 188
 189         search.key_length = sizeof (HfsExtentKey) - 1;
 190         search.type = HFS_DATA_FORK;
 191         search.file_ID = PED_CPU_TO_BE32 (HFS_BAD_BLOCK_ID);
 192
 193         last_start = -1; block = 0;
 194         while (1) {
 195                 int i;
 196
 197                 search.start = PED_CPU_TO_BE16 (block);
 198                 if (!hfs_btree_search (priv_data->extent_file,
 199                                        (HfsPrivateGenericKey*) &search,
 200                                        record, sizeof (record), NULL)
 201                     || ret_key->file_ID != search.file_ID
 202                     || ret_key->type != search.type) {
 203                         if (first_pass)
 204                                 break;
 205                         else
 206                                 goto errbb;
 207                 }
 208                 if (PED_BE16_TO_CPU (ret_key->start) == last_start)
 209                     break;
 210
 211                 last_start = PED_BE16_TO_CPU (ret_key->start);
 212                 for (i = 0; i < HFS_EXT_NB; i++) {
 213                         if (ret_cache[i].block_count) {
 214                                 HfsPrivateLinkExtent*   new_xt =
 215                                    (HfsPrivateLinkExtent*) ped_malloc (
 216                                         sizeof (HfsPrivateLinkExtent));
 217                                 if (!new_xt)
 218                                         goto errbb;
 219                                 new_xt->next = priv_data->bad_blocks_xtent_list;
 220                                 memcpy(&(new_xt->extent), ret_cache+i,
 221                                         sizeof (HfsExtDescriptor));
 222                                 priv_data->bad_blocks_xtent_list = new_xt;
 223                                 priv_data->bad_blocks_xtent_nb++;
 224                                 block += PED_BE16_TO_CPU (
 225                                                 ret_cache[i].block_count);
 226                         }
 227                 }
 228                 first_pass = 0;
 229         }
 230
 231         priv_data->bad_blocks_loaded = 1;
 232         return 1;}
 233
 234 errbb:  hfs_free_bad_blocks_list(priv_data->bad_blocks_xtent_list);
 235         priv_data->bad_blocks_xtent_list=NULL;
 236         priv_data->bad_blocks_xtent_nb=0;
 237         return 0;
 238 }
 239
 240 /* This function check if fblock is a bad block */
 241 int
 242 hfs_is_bad_block (const PedFileSystem *fs, unsigned int fblock)
 243 {
 244         HfsPrivateFSData*       priv_data = (HfsPrivateFSData*)
 245                                                 fs->type_specific;
 246         HfsPrivateLinkExtent*   walk;
 247
 248         for (walk = priv_data->bad_blocks_xtent_list; walk; walk = walk->next) {
 249                 /* Won't compile without the strange cast ! gcc bug ? */
 250                 /* or maybe C subtilties... */
 251                 if ((fblock >= PED_BE16_TO_CPU (walk->extent.start_block)) &&
 252                     (fblock <  (unsigned int) (PED_BE16_TO_CPU (
 253                                                     walk->extent.start_block)
 254                                                + PED_BE16_TO_CPU (
 255                                                     walk->extent.block_count))))
 256                         return 1;
 257         }
 258
 259         return 0;
 260 }
 261
 262 /* This function returns the first sector of the last free block of an
 263    HFS volume we can get after a hfs_pack_free_space_from_block call */
 264 /* On error this function returns 0 */
 265 PedSector
 266 hfs_get_empty_end (const PedFileSystem *fs)
 267 {
 268         HfsPrivateFSData*       priv_data = (HfsPrivateFSData*)
 269                                                 fs->type_specific;
 270         HfsMasterDirectoryBlock* mdb = priv_data->mdb;
 271         unsigned int            block, last_bad, end_free_blocks;
 272
 273         /* find the next block to the last bad block of the volume */
 274         if (!hfs_read_bad_blocks (fs))
 275                 return 0;
 276
 277         HfsPrivateLinkExtent*   l;
 278         last_bad = 0;
 279         for (l = priv_data->bad_blocks_xtent_list; l; l = l->next) {
 280                 if ((unsigned int) PED_BE16_TO_CPU (l->extent.start_block)
 281                     + PED_BE16_TO_CPU (l->extent.block_count) > last_bad)
 282                         last_bad = PED_BE16_TO_CPU (l->extent.start_block)
 283                                    + PED_BE16_TO_CPU (l->extent.block_count);
 284         }
 285
 286         /* Count the free blocks from last_bad to the end of the volume */
 287         end_free_blocks = 0;
 288         for (block = last_bad;
 289              block < PED_BE16_TO_CPU (mdb->total_blocks);
 290              block++) {
 291                 if (!TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
 292                         end_free_blocks++;
 293         }
 294
 295         /* Calculate the block that will by the first free at the
 296            end of the volume */
 297         block = PED_BE16_TO_CPU (mdb->total_blocks) - end_free_blocks;
 298
 299         return (PedSector) PED_BE16_TO_CPU (mdb->start_block)
 300                 + (PedSector) block * (PED_BE32_TO_CPU (mdb->block_size)
 301                                        / PED_SECTOR_SIZE_DEFAULT);
 302 }
 303
 304 /* return the block which should be used to pack data to have at
 305    least free fblock blocks at the end of the volume */
 306 unsigned int
 307 hfs_find_start_pack (const PedFileSystem *fs, unsigned int fblock)
 308 {
 309         HfsPrivateFSData*       priv_data = (HfsPrivateFSData*)
 310                                                 fs->type_specific;
 311         unsigned int            block;
 312
 313         for (block = PED_BE16_TO_CPU (priv_data->mdb->total_blocks) - 1;
 314              block && fblock;
 315              block--) {
 316                 if (!TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
 317                         fblock--;
 318         }
 319
 320         while (block && !TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
 321                 block--;
 322         if (TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
 323                 block++;
 324
 325         return block;
 326 }
 327
 328 #endif /* !DISCOVER_ONLY */