fs/hfs.c

   1 /* hfs.c - HFS.  */
   2 /*
   3  *  GRUB  --  GRand Unified Bootloader
   4  *  Copyright (C) 2004,2005,2006,2007,2008  Free Software Foundation, Inc.
   5  *
   6  *  GRUB is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  GRUB is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 /* HFS is documented at
  21    http://developer.apple.com/documentation/mac/Files/Files-2.html */
  22
  23 #include <grub/err.h>
  24 #include <grub/file.h>
  25 #include <grub/mm.h>
  26 #include <grub/misc.h>
  27 #include <grub/disk.h>
  28 #include <grub/dl.h>
  29 #include <grub/types.h>
  30 #include <grub/hfs.h>
  31
  32 #define GRUB_HFS_SBLOCK         2
  33 #define GRUB_HFS_EMBED_HFSPLUS_SIG 0x482B
  34
  35 #define GRUB_HFS_BLKS           (data->blksz >> 9)
  36
  37 #define GRUB_HFS_NODE_LEAF      0xFF
  38
  39 /* The two supported filesystems a record can have.  */
  40 enum
  41   {
  42     GRUB_HFS_FILETYPE_DIR = 1,
  43     GRUB_HFS_FILETYPE_FILE = 2
  44   };
  45
  46 /* Catalog node ID (CNID).  */
  47 enum grub_hfs_cnid_type
  48   {
  49     GRUB_HFS_CNID_ROOT_PARENT = 1,
  50     GRUB_HFS_CNID_ROOT = 2,
  51     GRUB_HFS_CNID_EXT = 3,
  52     GRUB_HFS_CNID_CAT = 4,
  53     GRUB_HFS_CNID_BAD = 5
  54   };
  55
  56 /* A node descriptor.  This is the header of every node.  */
  57 struct grub_hfs_node
  58 {
  59   grub_uint32_t next;
  60   grub_uint32_t prev;
  61   grub_uint8_t type;
  62   grub_uint8_t level;
  63   grub_uint16_t reccnt;
  64   grub_uint16_t unused;
  65 } __attribute__ ((packed));
  66
  67 /* The head of the B*-Tree.  */
  68 struct grub_hfs_treeheader
  69 {
  70   grub_uint16_t tree_depth;
  71   /* The number of the first node.  */
  72   grub_uint32_t root_node;
  73   grub_uint32_t leaves;
  74   grub_uint32_t first_leaf;
  75   grub_uint32_t last_leaf;
  76   grub_uint16_t node_size;
  77   grub_uint16_t key_size;
  78   grub_uint32_t nodes;
  79   grub_uint32_t free_nodes;
  80   grub_uint8_t unused[76];
  81 } __attribute__ ((packed));
  82
  83 /* The state of a mounted HFS filesystem.  */
  84 struct grub_hfs_data
  85 {
  86   struct grub_hfs_sblock sblock;
  87   grub_disk_t disk;
  88   grub_hfs_datarecord_t extents;
  89   int fileid;
  90   int size;
  91   int ext_root;
  92   int ext_size;
  93   int cat_root;
  94   int cat_size;
  95   int blksz;
  96   int log2_blksz;
  97   int rootdir;
  98 };
  99
 100 /* The key as used on disk in a catalog tree.  This is used to lookup
 101    file/directory nodes by parent directory ID and filename.  */
 102 struct grub_hfs_catalog_key
 103 {
 104   grub_uint8_t unused;
 105   grub_uint32_t parent_dir;
 106
 107   /* Filename length.  */
 108   grub_uint8_t strlen;
 109
 110   /* Filename.  */
 111   grub_uint8_t str[31];
 112 } __attribute__ ((packed));
 113
 114 /* The key as used on disk in a extent overflow tree.  Using this key
 115    the extents can be looked up using a fileid and logical start block
 116    as index.  */
 117 struct grub_hfs_extent_key
 118 {
 119   /* The kind of fork.  This is used to store meta information like
 120      icons, attributes, etc.  We will only use the datafork, which is
 121      0.  */
 122   grub_uint8_t forktype;
 123   grub_uint32_t fileid;
 124   grub_uint16_t first_block;
 125 } __attribute__ ((packed));
 126
 127 /* A directory record.  This is used to find out the directory ID.  */
 128 struct grub_hfs_dirrec
 129 {
 130   /* For a directory, type == 1.  */
 131   grub_uint8_t type;
 132   grub_uint8_t unused[5];
 133   grub_uint32_t dirid;
 134 } __attribute__ ((packed));
 135
 136 /* Information about a file.  */
 137 struct grub_hfs_filerec
 138 {
 139   /* For a file, type == 2.  */
 140   grub_uint8_t type;
 141   grub_uint8_t unused[19];
 142   grub_uint32_t fileid;
 143   grub_uint8_t unused2[2];
 144   grub_uint32_t size;
 145   grub_uint8_t unused3[44];
 146
 147   /* The first 3 extents of the file.  The other extents can be found
 148      in the extent overflow file.  */
 149   grub_hfs_datarecord_t extents;
 150 } __attribute__ ((packed));
 151
 152 /* A record descriptor, both key and data, used to pass to call back
 153    functions.  */
 154 struct grub_hfs_record
 155 {
 156   void *key;
 157   int keylen;
 158   void *data;
 159   int datalen;
 160 };
 161
 162 static grub_dl_t my_mod;
 163 \f
 164 static int grub_hfs_find_node (struct grub_hfs_data *, char *,
 165                                grub_uint32_t, int, char *, int);
 166
 167 /* Find block BLOCK of the file FILE in the mounted UFS filesystem
 168    DATA.  The first 3 extents are described by DAT.  If cache is set,
 169    using caching to improve non-random reads.  */
 170 static unsigned int
 171 grub_hfs_block (struct grub_hfs_data *data, grub_hfs_datarecord_t dat,
 172                 int file, int block, int cache)
 173 {
 174   grub_hfs_datarecord_t dr;
 175   int pos = 0;
 176   struct grub_hfs_extent_key key;
 177
 178   int tree = 0;
 179   static int cache_file = 0;
 180   static int cache_pos = 0;
 181   static grub_hfs_datarecord_t cache_dr;
 182
 183   grub_memcpy (dr, dat, sizeof (dr));
 184
 185   key.forktype = 0;
 186   key.fileid = grub_cpu_to_be32 (file);
 187
 188   if (cache && cache_file == file  && block > cache_pos)
 189     {
 190       pos = cache_pos;
 191       key.first_block = grub_cpu_to_be16 (pos);
 192       grub_memcpy (dr, cache_dr, sizeof (cache_dr));
 193     }
 194
 195   for (;;)
 196     {
 197       int i;
 198
 199       /* Try all 3 extents.  */
 200       for (i = 0; i < 3; i++)
 201         {
 202           /* Check if the block is stored in this extent.  */
 203           if (grub_be_to_cpu16 (dr[i].count) + pos > block)
 204             {
 205               int first = grub_be_to_cpu16 (dr[i].first_block);
 206
 207               /* If the cache is enabled, store the current position
 208                  in the tree.  */
 209               if (tree && cache)
 210                 {
 211                   cache_file = file;
 212                   cache_pos = pos;
 213                   grub_memcpy (cache_dr, dr, sizeof (cache_dr));
 214                 }
 215
 216               return (grub_be_to_cpu16 (data->sblock.first_block)
 217                       + (first + block - pos) * GRUB_HFS_BLKS);
 218             }
 219
 220           /* Try the next extent.  */
 221           pos += grub_be_to_cpu16 (dr[i].count);
 222         }
 223
 224       /* Lookup the block in the extent overflow file.  */
 225       key.first_block = grub_cpu_to_be16 (pos);
 226       tree = 1;
 227       grub_hfs_find_node (data, (char *) &key, data->ext_root,
 228                           1, (char *) &dr, sizeof (dr));
 229       if (grub_errno)
 230         return 0;
 231     }
 232 }
 233
 234
 235 /* Read LEN bytes from the file described by DATA starting with byte
 236    POS.  Return the amount of read bytes in READ.  */
 237 static grub_ssize_t
 238 grub_hfs_read_file (struct grub_hfs_data *data,
 239                     void NESTED_FUNC_ATTR (*read_hook) (grub_disk_addr_t sector,
 240                                        unsigned offset, unsigned length),
 241                      int pos, grub_size_t len, char *buf)
 242 {
 243   int i;
 244   int blockcnt;
 245
 246   blockcnt = ((len + pos)
 247               + data->blksz - 1) / data->blksz;
 248
 249   for (i = pos / data->blksz; i < blockcnt; i++)
 250     {
 251       int blknr;
 252       int blockoff = pos % data->blksz;
 253       int blockend = data->blksz;
 254
 255       int skipfirst = 0;
 256
 257       blknr = grub_hfs_block (data, data->extents, data->fileid, i, 1);
 258       if (grub_errno)
 259         return -1;
 260
 261       /* Last block.  */
 262       if (i == blockcnt - 1)
 263         {
 264           blockend = (len + pos) % data->blksz;
 265
 266           /* The last portion is exactly EXT2_BLOCK_SIZE (data).  */
 267           if (! blockend)
 268             blockend = data->blksz;
 269         }
 270
 271       /* First block.  */
 272       if (i == pos / data->blksz)
 273         {
 274           skipfirst = blockoff;
 275           blockend -= skipfirst;
 276         }
 277
 278       /* If the block number is 0 this block is not stored on disk but
 279          is zero filled instead.  */
 280       if (blknr)
 281         {
 282           data->disk->read_hook = read_hook;
 283           grub_disk_read (data->disk, blknr, skipfirst,
 284                           blockend, buf);
 285           data->disk->read_hook = 0;
 286           if (grub_errno)
 287             return -1;
 288         }
 289
 290       buf += data->blksz - skipfirst;
 291     }
 292
 293   return len;
 294 }
 295
 296
 297 /* Mount the filesystem on the disk DISK.  */
 298 static struct grub_hfs_data *
 299 grub_hfs_mount (grub_disk_t disk)
 300 {
 301   struct grub_hfs_data *data;
 302   struct grub_hfs_catalog_key key;
 303   struct grub_hfs_dirrec dir;
 304   int first_block;
 305
 306   struct
 307   {
 308     struct grub_hfs_node node;
 309     struct grub_hfs_treeheader head;
 310   } treehead;
 311
 312   data = grub_malloc (sizeof (struct grub_hfs_data));
 313   if (!data)
 314     return 0;
 315
 316   /* Read the superblock.  */
 317   if (grub_disk_read (disk, GRUB_HFS_SBLOCK, 0,
 318                       sizeof (struct grub_hfs_sblock), &data->sblock))
 319     goto fail;
 320
 321   /* Check if this is a HFS filesystem.  */
 322   if (grub_be_to_cpu16 (data->sblock.magic) != GRUB_HFS_MAGIC)
 323     {
 324       grub_error (GRUB_ERR_BAD_FS, "not an HFS filesystem");
 325       goto fail;
 326     }
 327
 328   /* Check if this is an embedded HFS+ filesystem.  */
 329   if (grub_be_to_cpu16 (data->sblock.embed_sig) == GRUB_HFS_EMBED_HFSPLUS_SIG)
 330     {
 331       grub_error (GRUB_ERR_BAD_FS, "embedded HFS+ filesystem");
 332       goto fail;
 333     }
 334
 335   data->blksz = grub_be_to_cpu32 (data->sblock.blksz);
 336   data->disk = disk;
 337
 338   /* Lookup the root node of the extent overflow tree.  */
 339   first_block = ((grub_be_to_cpu16 (data->sblock.extent_recs[0].first_block)
 340                   * GRUB_HFS_BLKS)
 341                  + grub_be_to_cpu16 (data->sblock.first_block));
 342
 343   if (grub_disk_read (data->disk, first_block, 0,
 344                       sizeof (treehead), &treehead))
 345     goto fail;
 346   data->ext_root = grub_be_to_cpu32 (treehead.head.root_node);
 347   data->ext_size = grub_be_to_cpu16 (treehead.head.node_size);
 348
 349   /* Lookup the root node of the catalog tree.  */
 350   first_block = ((grub_be_to_cpu16 (data->sblock.catalog_recs[0].first_block)
 351                   * GRUB_HFS_BLKS)
 352                  + grub_be_to_cpu16 (data->sblock.first_block));
 353   if (grub_disk_read (data->disk, first_block, 0,
 354                       sizeof (treehead), &treehead))
 355     goto fail;
 356   data->cat_root = grub_be_to_cpu32 (treehead.head.root_node);
 357   data->cat_size = grub_be_to_cpu16 (treehead.head.node_size);
 358
 359   /* Lookup the root directory node in the catalog tree using the
 360      volume name.  */
 361   key.parent_dir = grub_cpu_to_be32 (1);
 362   key.strlen = data->sblock.volname[0];
 363   grub_strcpy ((char *) key.str, (char *) (data->sblock.volname + 1));
 364
 365   if (grub_hfs_find_node (data, (char *) &key, data->cat_root,
 366                           0, (char *) &dir, sizeof (dir)) == 0)
 367     {
 368       grub_error (GRUB_ERR_BAD_FS, "can not find the hfs root directory");
 369       goto fail;
 370     }
 371
 372   if (grub_errno)
 373     goto fail;
 374
 375   data->rootdir = grub_be_to_cpu32 (dir.dirid);
 376
 377   return data;
 378  fail:
 379   grub_free (data);
 380
 381   if (grub_errno == GRUB_ERR_OUT_OF_RANGE)
 382     grub_error (GRUB_ERR_BAD_FS, "not a hfs filesystem");
 383
 384   return 0;
 385 }
 386
 387 /* Compare the K1 and K2 catalog file keys using HFS character ordering.  */
 388 static int
 389 grub_hfs_cmp_catkeys (struct grub_hfs_catalog_key *k1,
 390                       struct grub_hfs_catalog_key *k2)
 391 {
 392   /* Taken from hfsutils 3.2.6 and converted to a readable form */
 393   static const unsigned char hfs_charorder[256] = {
 394     [0x00] = 0,
 395     [0x01] = 1,
 396     [0x02] = 2,
 397     [0x03] = 3,
 398     [0x04] = 4,
 399     [0x05] = 5,
 400     [0x06] = 6,
 401     [0x07] = 7,
 402     [0x08] = 8,
 403     [0x09] = 9,
 404     [0x0A] = 10,
 405     [0x0B] = 11,
 406     [0x0C] = 12,
 407     [0x0D] = 13,
 408     [0x0E] = 14,
 409     [0x0F] = 15,
 410     [0x10] = 16,
 411     [0x11] = 17,
 412     [0x12] = 18,
 413     [0x13] = 19,
 414     [0x14] = 20,
 415     [0x15] = 21,
 416     [0x16] = 22,
 417     [0x17] = 23,
 418     [0x18] = 24,
 419     [0x19] = 25,
 420     [0x1A] = 26,
 421     [0x1B] = 27,
 422     [0x1C] = 28,
 423     [0x1D] = 29,
 424     [0x1E] = 30,
 425     [0x1F] = 31,
 426     [' '] = 32,         [0xCA] = 32,
 427     ['!'] = 33,
 428     ['"'] = 34,
 429     [0xD2] = 35,
 430     [0xD3] = 36,
 431     [0xC7] = 37,
 432     [0xC8] = 38,
 433     ['#'] = 39,
 434     ['$'] = 40,
 435     ['%'] = 41,
 436     ['&'] = 42,
 437     ['\''] = 43,
 438     [0xD4] = 44,
 439     [0xD5] = 45,
 440     ['('] = 46,
 441     [')'] = 47,
 442     ['*'] = 48,
 443     ['+'] = 49,
 444     [','] = 50,
 445     ['-'] = 51,
 446     ['.'] = 52,
 447     ['/'] = 53,
 448     ['0'] = 54,
 449     ['1'] = 55,
 450     ['2'] = 56,
 451     ['3'] = 57,
 452     ['4'] = 58,
 453     ['5'] = 59,
 454     ['6'] = 60,
 455     ['7'] = 61,
 456     ['8'] = 62,
 457     ['9'] = 63,
 458     [':'] = 64,
 459     [';'] = 65,
 460     ['<'] = 66,
 461     ['='] = 67,
 462     ['>'] = 68,
 463     ['?'] = 69,
 464     ['@'] = 70,
 465     ['A'] = 71,         ['a'] = 71,
 466     [0x88] = 72,        [0xCB] = 72,
 467     [0x80] = 73,        [0x8A] = 73,
 468     [0x8B] = 74,        [0xCC] = 74,
 469     [0x81] = 75,        [0x8C] = 75,
 470     [0xAE] = 76,        [0xBE] = 76,
 471     ['`'] = 77,
 472     [0x87] = 78,
 473     [0x89] = 79,
 474     [0xBB] = 80,
 475     ['B'] = 81,         ['b'] = 81,
 476     ['C'] = 82,         ['c'] = 82,
 477     [0x82] = 83,        [0x8D] = 83,
 478     ['D'] = 84,         ['d'] = 84,
 479     ['E'] = 85,         ['e'] = 85,
 480     [0x83] = 86,        [0x8E] = 86,
 481     [0x8F] = 87,
 482     [0x90] = 88,
 483     [0x91] = 89,
 484     ['F'] = 90,         ['f'] = 90,
 485     ['G'] = 91,         ['g'] = 91,
 486     ['H'] = 92,         ['h'] = 92,
 487     ['I'] = 93,         ['i'] = 93,
 488     [0x92] = 94,
 489     [0x93] = 95,
 490     [0x94] = 96,
 491     [0x95] = 97,
 492     ['J'] = 98,         ['j'] = 98,
 493     ['K'] = 99,         ['k'] = 99,
 494     ['L'] = 100,        ['l'] = 100,
 495     ['M'] = 101,        ['m'] = 101,
 496     ['N'] = 102,        ['n'] = 102,
 497     [0x84] = 103,       [0x96] = 103,
 498     ['O'] = 104,        ['o'] = 104,
 499     [0x85] = 105,       [0x9A] = 105,
 500     [0x9B] = 106,       [0xCD] = 106,
 501     [0xAF] = 107,       [0xBF] = 107,
 502     [0xCE] = 108,       [0xCF] = 108,
 503     [0x97] = 109,
 504     [0x98] = 110,
 505     [0x99] = 111,
 506     [0xBC] = 112,
 507     ['P'] = 113,        ['p'] = 113,
 508     ['Q'] = 114,        ['q'] = 114,
 509     ['R'] = 115,        ['r'] = 115,
 510     ['S'] = 116,        ['s'] = 116,
 511     [0xA7] = 117,
 512     ['T'] = 118,        ['t'] = 118,
 513     ['U'] = 119,        ['u'] = 119,
 514     [0x86] = 120,       [0x9F] = 120,
 515     [0x9C] = 121,
 516     [0x9D] = 122,
 517     [0x9E] = 123,
 518     ['V'] = 124,        ['v'] = 124,
 519     ['W'] = 125,        ['w'] = 125,
 520     ['X'] = 126,        ['x'] = 126,
 521     ['Y'] = 127,        ['y'] = 127,
 522     [0xD8] = 128,
 523     ['Z'] = 129,        ['z'] = 129,
 524     ['['] = 130,
 525     ['\\'] = 131,
 526     [']'] = 132,
 527     ['^'] = 133,
 528     ['_'] = 134,
 529     ['{'] = 135,
 530     ['|'] = 136,
 531     ['}'] = 137,
 532     ['~'] = 138,
 533     [0x7F] = 139,
 534     [0xA0] = 140,
 535     [0xA1] = 141,
 536     [0xA2] = 142,
 537     [0xA3] = 143,
 538     [0xA4] = 144,
 539     [0xA5] = 145,
 540     [0xA6] = 146,
 541     [0xA8] = 147,
 542     [0xA9] = 148,
 543     [0xAA] = 149,
 544     [0xAB] = 150,
 545     [0xAC] = 151,
 546     [0xAD] = 152,
 547     [0xB0] = 153,
 548     [0xB1] = 154,
 549     [0xB2] = 155,
 550     [0xB3] = 156,
 551     [0xB4] = 157,
 552     [0xB5] = 158,
 553     [0xB6] = 159,
 554     [0xB7] = 160,
 555     [0xB8] = 161,
 556     [0xB9] = 162,
 557     [0xBA] = 163,
 558     [0xBD] = 164,
 559     [0xC0] = 165,
 560     [0xC1] = 166,
 561     [0xC2] = 167,
 562     [0xC3] = 168,
 563     [0xC4] = 169,
 564     [0xC5] = 170,
 565     [0xC6] = 171,
 566     [0xC9] = 172,
 567     [0xD0] = 173,
 568     [0xD1] = 174,
 569     [0xD6] = 175,
 570     [0xD7] = 176,
 571     [0xD9] = 177,
 572     [0xDA] = 178,
 573     [0xDB] = 179,
 574     [0xDC] = 180,
 575     [0xDD] = 181,
 576     [0xDE] = 182,
 577     [0xDF] = 183,
 578     [0xE0] = 184,
 579     [0xE1] = 185,
 580     [0xE2] = 186,
 581     [0xE3] = 187,
 582     [0xE4] = 188,
 583     [0xE5] = 189,
 584     [0xE6] = 190,
 585     [0xE7] = 191,
 586     [0xE8] = 192,
 587     [0xE9] = 193,
 588     [0xEA] = 194,
 589     [0xEB] = 195,
 590     [0xEC] = 196,
 591     [0xED] = 197,
 592     [0xEE] = 198,
 593     [0xEF] = 199,
 594     [0xF0] = 200,
 595     [0xF1] = 201,
 596     [0xF2] = 202,
 597     [0xF3] = 203,
 598     [0xF4] = 204,
 599     [0xF5] = 205,
 600     [0xF6] = 206,
 601     [0xF7] = 207,
 602     [0xF8] = 208,
 603     [0xF9] = 209,
 604     [0xFA] = 210,
 605     [0xFB] = 211,
 606     [0xFC] = 212,
 607     [0xFD] = 213,
 608     [0xFE] = 214,
 609     [0xFF] = 215,
 610   };
 611   int i;
 612   int cmp;
 613   int minlen = (k1->strlen < k2->strlen) ? k1->strlen : k2->strlen;
 614
 615   cmp = (grub_be_to_cpu32 (k1->parent_dir) - grub_be_to_cpu32 (k2->parent_dir));
 616   if (cmp != 0)
 617     return cmp;
 618
 619   for (i = 0; i < minlen; i++)
 620     {
 621       cmp = (hfs_charorder[k1->str[i]] - hfs_charorder[k2->str[i]]);
 622       if (cmp != 0)
 623         return cmp;
 624     }
 625
 626   /* Shorter strings precede long ones.  */
 627   return (k1->strlen - k2->strlen);
 628 }
 629
 630
 631 /* Compare the K1 and K2 extent overflow file keys.  */
 632 static int
 633 grub_hfs_cmp_extkeys (struct grub_hfs_extent_key *k1,
 634                       struct grub_hfs_extent_key *k2)
 635 {
 636   int cmp = k1->forktype - k2->forktype;
 637   if (cmp == 0)
 638     cmp = grub_be_to_cpu32 (k1->fileid) - grub_be_to_cpu32 (k2->fileid);
 639   if (cmp == 0)
 640     cmp = (grub_be_to_cpu16 (k1->first_block)
 641            - grub_be_to_cpu16 (k2->first_block));
 642   return cmp;
 643 }
 644
 645
 646 /* Iterate the records in the node with index IDX in the mounted HFS
 647    filesystem DATA.  This node holds data of the type TYPE (0 =
 648    catalog node, 1 = extent overflow node).  If this is set, continue
 649    iterating to the next node.  For every records, call NODE_HOOK.  */
 650 static grub_err_t
 651 grub_hfs_iterate_records (struct grub_hfs_data *data, int type, int idx,
 652                           int this, int (*node_hook) (struct grub_hfs_node *hnd,
 653                                                       struct grub_hfs_record *))
 654 {
 655   int nodesize = type == 0 ? data->cat_size : data->ext_size;
 656
 657   union
 658   {
 659     struct grub_hfs_node node;
 660     char rawnode[nodesize];
 661     grub_uint16_t offsets[nodesize / 2];
 662   } node;
 663
 664   do
 665     {
 666       int i;
 667       struct grub_hfs_extent *dat;
 668       int blk;
 669
 670       dat = (struct grub_hfs_extent *) (type == 0
 671                                         ? (&data->sblock.catalog_recs)
 672                                         : (&data->sblock.extent_recs));
 673
 674       /* Read the node into memory.  */
 675       blk = grub_hfs_block (data, dat,
 676                             (type == 0) ? GRUB_HFS_CNID_CAT : GRUB_HFS_CNID_EXT,
 677                             idx / (data->blksz / nodesize), 0);
 678       blk += (idx % (data->blksz / nodesize));
 679       if (grub_errno)
 680         return grub_errno;
 681
 682       if (grub_disk_read (data->disk, blk, 0,
 683                           sizeof (node), &node))
 684         return grub_errno;
 685
 686       /* Iterate over all records in this node.  */
 687       for (i = 0; i < grub_be_to_cpu16 (node.node.reccnt); i++)
 688         {
 689           int pos = (nodesize >> 1) - 1 - i;
 690           struct pointer
 691           {
 692             grub_uint8_t keylen;
 693             grub_uint8_t key;
 694           } __attribute__ ((packed)) *pnt;
 695           pnt = (struct pointer *) (grub_be_to_cpu16 (node.offsets[pos])
 696                                     + node.rawnode);
 697
 698           struct grub_hfs_record rec =
 699             {
 700               &pnt->key,
 701               pnt->keylen,
 702               &pnt->key + pnt->keylen +(pnt->keylen + 1) % 2,
 703               nodesize - grub_be_to_cpu16 (node.offsets[pos])
 704               - pnt->keylen - 1
 705             };
 706
 707           if (node_hook (&node.node, &rec))
 708             return 0;
 709         }
 710
 711       idx = grub_be_to_cpu32 (node.node.next);
 712     } while (idx && this);
 713
 714   return 0;
 715 }
 716
 717
 718 /* Lookup a record in the mounted filesystem DATA using the key KEY.
 719    The index of the node on top of the tree is IDX.  The tree is of
 720    the type TYPE (0 = catalog node, 1 = extent overflow node).  Return
 721    the data in DATAR with a maximum length of DATALEN.  */
 722 static int
 723 grub_hfs_find_node (struct grub_hfs_data *data, char *key,
 724                     grub_uint32_t idx, int type, char *datar, int datalen)
 725 {
 726   int found = -1;
 727   int isleaf = 0;
 728   int done = 0;
 729
 730   auto int node_found (struct grub_hfs_node *, struct grub_hfs_record *);
 731
 732   int node_found (struct grub_hfs_node *hnd, struct grub_hfs_record *rec)
 733     {
 734       int cmp = 1;
 735
 736       if (type == 0)
 737         cmp = grub_hfs_cmp_catkeys (rec->key, (void *) key);
 738       else
 739         cmp = grub_hfs_cmp_extkeys (rec->key, (void *) key);
 740
 741       /* If the key is smaller or equal to the current node, mark the
 742          entry.  In case of a non-leaf mode it will be used to lookup
 743          the rest of the tree.  */
 744       if (cmp <= 0)
 745         {
 746           grub_uint32_t *node = (grub_uint32_t *) rec->data;
 747           found = grub_be_to_cpu32 (*node);
 748         }
 749       else /* The key can not be found in the tree. */
 750         return 1;
 751
 752       /* Check if this node is a leaf node.  */
 753       if (hnd->type == GRUB_HFS_NODE_LEAF)
 754         {
 755           isleaf = 1;
 756
 757           /* Found it!!!!  */
 758           if (cmp == 0)
 759             {
 760               done = 1;
 761
 762               grub_memcpy (datar, rec->data,
 763                            rec->datalen < datalen ? rec->datalen : datalen);
 764               return 1;
 765             }
 766         }
 767
 768       return 0;
 769     }
 770
 771   do
 772     {
 773       found = -1;
 774
 775       if (grub_hfs_iterate_records (data, type, idx, 0, node_found))
 776         return 0;
 777
 778       if (found == -1)
 779         return 0;
 780
 781       idx = found;
 782     } while (! isleaf);
 783
 784   return done;
 785 }
 786
 787
 788 /* Iterate over the directory with the id DIR.  The tree is searched
 789    starting with the node ROOT_IDX.  For every entry in this directory
 790    call HOOK.  */
 791 static grub_err_t
 792 grub_hfs_iterate_dir (struct grub_hfs_data *data, grub_uint32_t root_idx,
 793                       unsigned int dir, int (*hook) (struct grub_hfs_record *))
 794 {
 795   int found = -1;
 796   int isleaf = 0;
 797   int next = 0;
 798
 799   /* The lowest key possible with DIR as root directory.  */
 800   struct grub_hfs_catalog_key key = {0, grub_cpu_to_be32 (dir), 0, ""};
 801
 802   auto int node_found (struct grub_hfs_node *, struct grub_hfs_record *);
 803   auto int it_dir (struct grub_hfs_node * __attribute ((unused)),
 804                    struct grub_hfs_record *);
 805
 806
 807   int node_found (struct grub_hfs_node *hnd, struct grub_hfs_record *rec)
 808     {
 809       struct grub_hfs_catalog_key *ckey = rec->key;
 810
 811       if (grub_hfs_cmp_catkeys (rec->key, (void *) &key) <= 0)
 812         found = grub_be_to_cpu32 (*(grub_uint32_t *) rec->data);
 813
 814       if (hnd->type == 0xFF && ckey->strlen > 0)
 815         {
 816           isleaf = 1;
 817           next = grub_be_to_cpu32 (hnd->next);
 818
 819           /* An entry was found.  */
 820           if (grub_be_to_cpu32 (ckey->parent_dir) == dir)
 821             return hook (rec);
 822         }
 823
 824       return 0;
 825     }
 826
 827   int it_dir (struct grub_hfs_node *hnd __attribute ((unused)),
 828               struct grub_hfs_record *rec)
 829     {
 830       struct grub_hfs_catalog_key *ckey = rec->key;
 831       struct grub_hfs_catalog_key *origkey = &key;
 832
 833       /* Stop when the entries do not match anymore.  */
 834       if (grub_be_to_cpu32 (ckey->parent_dir)
 835           != grub_be_to_cpu32 ((origkey)->parent_dir))
 836         return 1;
 837
 838       return hook (rec);
 839     }
 840
 841   do
 842     {
 843       found = -1;
 844
 845       if (grub_hfs_iterate_records (data, 0, root_idx, 0, node_found))
 846         return grub_errno;
 847
 848       if (found == -1)
 849         return 0;
 850
 851       root_idx = found;
 852     } while (! isleaf);
 853
 854   /* If there was a matching record in this leaf node, continue the
 855      iteration until the last record was found.  */
 856   grub_hfs_iterate_records (data, 0, next, 1, it_dir);
 857   return grub_errno;
 858 }
 859
 860
 861 /* Find a file or directory with the pathname PATH in the filesystem
 862    DATA.  Return the file record in RETDATA when it is non-zero.
 863    Return the directory number in RETINODE when it is non-zero.  */
 864 static grub_err_t
 865 grub_hfs_find_dir (struct grub_hfs_data *data, const char *path,
 866                    struct grub_hfs_filerec *retdata, int *retinode)
 867 {
 868   int inode = data->rootdir;
 869   char *next;
 870   char *origpath;
 871   union {
 872     struct grub_hfs_filerec frec;
 873     struct grub_hfs_dirrec dir;
 874   } fdrec;
 875
 876   fdrec.frec.type = GRUB_HFS_FILETYPE_DIR;
 877
 878   if (path[0] != '/')
 879     {
 880       grub_error (GRUB_ERR_BAD_FILENAME, "bad filename");
 881       return 0;
 882     }
 883
 884   origpath = grub_strdup (path);
 885   if (!origpath)
 886     return grub_errno;
 887
 888   path = origpath;
 889   while (*path == '/')
 890     path++;
 891
 892   while (path && grub_strlen (path))
 893     {
 894       if (fdrec.frec.type != GRUB_HFS_FILETYPE_DIR)
 895         {
 896           grub_error (GRUB_ERR_BAD_FILE_TYPE, "not a directory");
 897           goto fail;
 898         }
 899
 900       /* Isolate a part of the path.  */
 901       next = grub_strchr (path, '/');
 902       if (next)
 903         {
 904           while (*next == '/')
 905             *(next++) = '\0';
 906         }
 907
 908       struct grub_hfs_catalog_key key;
 909
 910       key.parent_dir = grub_cpu_to_be32 (inode);
 911       key.strlen = grub_strlen (path);
 912       grub_strcpy ((char *) (key.str), path);
 913
 914       /* Lookup this node.  */
 915       if (! grub_hfs_find_node (data, (char *) &key, data->cat_root,
 916                                 0, (char *) &fdrec.frec, sizeof (fdrec.frec)))
 917         {
 918           grub_error (GRUB_ERR_FILE_NOT_FOUND, "file not found");
 919           goto fail;
 920         }
 921
 922       if (grub_errno)
 923         goto fail;
 924
 925       inode = grub_be_to_cpu32 (fdrec.dir.dirid);
 926       path = next;
 927     }
 928
 929   if (retdata)
 930     grub_memcpy (retdata, &fdrec.frec, sizeof (fdrec.frec));
 931
 932   if (retinode)
 933     *retinode = inode;
 934
 935  fail:
 936   grub_free (origpath);
 937   return grub_errno;
 938 }
 939
 940
 941 \f
 942 static grub_err_t
 943 grub_hfs_dir (grub_device_t device, const char *path,
 944                   int (*hook) (const char *filename,
 945                                const struct grub_dirhook_info *info))
 946 {
 947   int inode;
 948
 949   auto int dir_hook (struct grub_hfs_record *rec);
 950
 951   int dir_hook (struct grub_hfs_record *rec)
 952     {
 953       char fname[32] = { 0 };
 954       char *filetype = rec->data;
 955       struct grub_hfs_catalog_key *ckey = rec->key;
 956       struct grub_dirhook_info info;
 957       grub_memset (&info, 0, sizeof (info));
 958
 959       grub_strncpy (fname, (char *) (ckey->str), ckey->strlen);
 960
 961       if (*filetype == GRUB_HFS_FILETYPE_DIR
 962           || *filetype == GRUB_HFS_FILETYPE_FILE)
 963         {
 964           info.dir = (*filetype == GRUB_HFS_FILETYPE_DIR);
 965           return hook (fname, &info);
 966         }
 967       return 0;
 968     }
 969
 970   struct grub_hfs_data *data;
 971   struct grub_hfs_filerec frec;
 972
 973   grub_dl_ref (my_mod);
 974
 975   data = grub_hfs_mount (device->disk);
 976   if (!data)
 977     goto fail;
 978
 979   /* First the directory ID for the directory.  */
 980   if (grub_hfs_find_dir (data, path, &frec, &inode))
 981     goto fail;
 982
 983   if (frec.type != GRUB_HFS_FILETYPE_DIR)
 984     {
 985       grub_error (GRUB_ERR_BAD_FILE_TYPE, "not a directory");
 986       goto fail;
 987     }
 988
 989   grub_hfs_iterate_dir (data, data->cat_root, inode, dir_hook);
 990
 991  fail:
 992   grub_free (data);
 993
 994   grub_dl_unref (my_mod);
 995
 996   return grub_errno;
 997 }
 998
 999
1000 /* Open a file named NAME and initialize FILE.  */
1001 static grub_err_t
1002 grub_hfs_open (struct grub_file *file, const char *name)
1003 {
1004   struct grub_hfs_data *data;
1005   struct grub_hfs_filerec frec;
1006
1007   grub_dl_ref (my_mod);
1008
1009   data = grub_hfs_mount (file->device->disk);
1010
1011   if (grub_hfs_find_dir (data, name, &frec, 0))
1012     {
1013       grub_free (data);
1014       grub_dl_unref (my_mod);
1015       return grub_errno;
1016     }
1017
1018   if (frec.type != GRUB_HFS_FILETYPE_FILE)
1019     {
1020       grub_free (data);
1021       grub_error (GRUB_ERR_BAD_FILE_TYPE, "not a file");
1022       grub_dl_unref (my_mod);
1023       return grub_errno;
1024     }
1025
1026   grub_memcpy (data->extents, frec.extents, sizeof (grub_hfs_datarecord_t));
1027   file->size = grub_be_to_cpu32 (frec.size);
1028   data->size = grub_be_to_cpu32 (frec.size);
1029   data->fileid = grub_be_to_cpu32 (frec.fileid);
1030   file->offset = 0;
1031
1032   file->data = data;
1033
1034   return 0;
1035 }
1036
1037 static grub_ssize_t
1038 grub_hfs_read (grub_file_t file, char *buf, grub_size_t len)
1039 {
1040   struct grub_hfs_data *data =
1041     (struct grub_hfs_data *) file->data;
1042
1043   return grub_hfs_read_file (data, file->read_hook, file->offset, len, buf);
1044 }
1045
1046
1047 static grub_err_t
1048 grub_hfs_close (grub_file_t file)
1049 {
1050   grub_free (file->data);
1051
1052   grub_dl_unref (my_mod);
1053
1054   return 0;
1055 }
1056
1057
1058 static grub_err_t
1059 grub_hfs_label (grub_device_t device, char **label)
1060 {
1061   struct grub_hfs_data *data;
1062
1063   data = grub_hfs_mount (device->disk);
1064
1065   if (data)
1066     *label = grub_strndup ((char *) (data->sblock.volname + 1),
1067                            *data->sblock.volname);
1068   else
1069     *label = 0;
1070
1071   grub_free (data);
1072   return grub_errno;
1073 }
1074
1075
1076 \f
1077 static struct grub_fs grub_hfs_fs =
1078   {
1079     .name = "hfs",
1080     .dir = grub_hfs_dir,
1081     .open = grub_hfs_open,
1082     .read = grub_hfs_read,
1083     .close = grub_hfs_close,
1084     .label = grub_hfs_label,
1085     .next = 0
1086   };
1087
1088 GRUB_MOD_INIT(hfs)
1089 {
1090   grub_fs_register (&grub_hfs_fs);
1091   my_mod = mod;
1092 }
1093
1094 GRUB_MOD_FINI(hfs)
1095 {
1096   grub_fs_unregister (&grub_hfs_fs);
1097 }