hfsplus.c 29.2 KB
Newer Older
1 2 3
/* hfsplus.c - HFS+ Filesystem.  */
/*
 *  GRUB  --  GRand Unified Bootloader
4
 *  Copyright (C) 2005,2006,2007,2008,2009  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 10
 *  (at your option) any later version.
 *
11
 *  GRUB is distributed in the hope that it will be useful,
12 13 14 15 16
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  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 21
/* HFS+ is documented at http://developer.apple.com/technotes/tn/tn1150.html */

22
#define grub_fshelp_node grub_hfsplus_file 
23 24 25 26 27 28 29 30
#include <grub/err.h>
#include <grub/file.h>
#include <grub/mm.h>
#include <grub/misc.h>
#include <grub/disk.h>
#include <grub/dl.h>
#include <grub/types.h>
#include <grub/fshelp.h>
31
#include <grub/hfs.h>
32
#include <grub/charset.h>
33
#include <grub/hfsplus.h>
34

35 36
GRUB_MOD_LICENSE ("GPLv3+");

37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
/* The type of node.  */
enum grub_hfsplus_btnode_type
  {
    GRUB_HFSPLUS_BTNODE_TYPE_LEAF = -1,
    GRUB_HFSPLUS_BTNODE_TYPE_INDEX = 0,
    GRUB_HFSPLUS_BTNODE_TYPE_HEADER = 1,
    GRUB_HFSPLUS_BTNODE_TYPE_MAP = 2,
  };

/* The header of a HFS+ B+ Tree.  */
struct grub_hfsplus_btheader
{
  grub_uint16_t depth;
  grub_uint32_t root;
  grub_uint32_t leaf_records;
  grub_uint32_t first_leaf_node;
  grub_uint32_t last_leaf_node;
  grub_uint16_t nodesize;
  grub_uint16_t keysize;
56 57 58 59 60 61 62
  grub_uint32_t total_nodes;
  grub_uint32_t free_nodes;
  grub_uint16_t reserved1;
  grub_uint32_t clump_size;  /* ignored */
  grub_uint8_t btree_type;
  grub_uint8_t key_compare;
  grub_uint32_t attributes;
63
} GRUB_PACKED;
64 65 66 67 68

struct grub_hfsplus_catfile
{
  grub_uint16_t type;
  grub_uint16_t flags;
69
  grub_uint32_t parentid; /* Thread only.  */
70
  grub_uint32_t fileid;
71 72 73
  grub_uint8_t unused1[4];
  grub_uint32_t mtime;
  grub_uint8_t unused2[22];
74
  grub_uint16_t mode;
75
  grub_uint8_t unused3[44];
76 77
  struct grub_hfsplus_forkdata data;
  struct grub_hfsplus_forkdata resource;
78
} GRUB_PACKED;
79 80 81 82 83 84 85 86

/* Filetype information as used in inodes.  */
#define GRUB_HFSPLUS_FILEMODE_MASK	0170000
#define GRUB_HFSPLUS_FILEMODE_REG	0100000
#define GRUB_HFSPLUS_FILEMODE_DIRECTORY	0040000
#define GRUB_HFSPLUS_FILEMODE_SYMLINK	0120000

/* Some pre-defined file IDs.  */
87 88 89 90 91 92 93
enum
  {
    GRUB_HFSPLUS_FILEID_ROOTDIR = 2,
    GRUB_HFSPLUS_FILEID_OVERFLOW = 3,
    GRUB_HFSPLUS_FILEID_CATALOG	= 4,
    GRUB_HFSPLUS_FILEID_ATTR	= 8
  };
94 95 96 97 98 99 100 101 102

enum grub_hfsplus_filetype
  {
    GRUB_HFSPLUS_FILETYPE_DIR = 1,
    GRUB_HFSPLUS_FILETYPE_REG = 2,
    GRUB_HFSPLUS_FILETYPE_DIR_THREAD = 3,
    GRUB_HFSPLUS_FILETYPE_REG_THREAD = 4
  };

103 104 105
#define GRUB_HFSPLUSX_BINARYCOMPARE	0xBC
#define GRUB_HFSPLUSX_CASEFOLDING	0xCF

106 107 108
static grub_dl_t my_mod;


109

110 111 112 113 114
grub_err_t (*grub_hfsplus_open_compressed) (struct grub_fshelp_node *node);
grub_ssize_t (*grub_hfsplus_read_compressed) (struct grub_hfsplus_file *node,
					      grub_off_t pos,
					      grub_size_t len,
					      char *buf);
115

116 117
/* Find the extent that points to FILEBLOCK.  If it is not in one of
   the 8 extents described by EXTENT, return -1.  In that case set
118
   FILEBLOCK to the next block.  */
119
static grub_disk_addr_t
120
grub_hfsplus_find_block (struct grub_hfsplus_extent *extent,
121
			 grub_disk_addr_t *fileblock)
122 123
{
  int i;
124
  grub_disk_addr_t blksleft = *fileblock;
125 126 127 128 129 130 131 132 133

  /* First lookup the file in the given extents.  */
  for (i = 0; i < 8; i++)
    {
      if (blksleft < grub_be_to_cpu32 (extent[i].count))
	return grub_be_to_cpu32 (extent[i].start) + blksleft;
      blksleft -= grub_be_to_cpu32 (extent[i].count);
    }

134
  *fileblock = blksleft;
135
  return 0xffffffffffffffffULL;
136 137 138 139 140 141 142
}

static int grub_hfsplus_cmp_extkey (struct grub_hfsplus_key *keya,
				    struct grub_hfsplus_key_internal *keyb);

/* Search for the block FILEBLOCK inside the file NODE.  Return the
   blocknumber of this block on disk.  */
143 144
static grub_disk_addr_t
grub_hfsplus_read_block (grub_fshelp_node_t node, grub_disk_addr_t fileblock)
145 146
{
  struct grub_hfsplus_btnode *nnode = 0;
147
  grub_disk_addr_t blksleft = fileblock;
148 149
  struct grub_hfsplus_extent *extents = node->compressed 
    ? &node->resource_extents[0] : &node->extents[0];
150 151 152

  while (1)
    {
153
      struct grub_hfsplus_extkey *key;
154
      struct grub_hfsplus_key_internal extoverflow;
155 156
      grub_disk_addr_t blk;
      grub_off_t ptr;
157 158

      /* Try to find this block in the current set of extents.  */
159
      blk = grub_hfsplus_find_block (extents, &blksleft);
160 161

      /* The previous iteration of this loop allocated memory.  The
162
	 code above used this memory, it can be freed now.  */
163 164
      grub_free (nnode);
      nnode = 0;
165

166
      if (blk != 0xffffffffffffffffULL)
167
	return blk;
168 169 170 171 172

      /* For the extent overflow file, extra extents can't be found in
	 the extent overflow file.  If this happens, you found a
	 bug...  */
      if (node->fileid == GRUB_HFSPLUS_FILEID_OVERFLOW)
173 174 175 176 177
	{
	  grub_error (GRUB_ERR_READ_ERROR,
		      "extra extents found in an extend overflow file");
	  break;
	}
178 179

      /* Set up the key to look for in the extent overflow file.  */
180
      extoverflow.extkey.fileid = node->fileid;
181
      extoverflow.extkey.type = 0;
182
      extoverflow.extkey.start = fileblock - blksleft;
183
      extoverflow.extkey.type = node->compressed ? 0xff : 0;
184
      if (grub_hfsplus_btree_search (&node->data->extoverflow_tree,
185
				     &extoverflow,
186 187
				     grub_hfsplus_cmp_extkey, &nnode, &ptr)
	  || !nnode)
188 189 190 191 192 193
	{
	  grub_error (GRUB_ERR_READ_ERROR,
		      "no block found for the file id 0x%x and the block offset 0x%x",
		      node->fileid, fileblock);
	  break;
	}
194

195 196 197 198
      /* The extent overflow file has 8 extents right after the key.  */
      key = (struct grub_hfsplus_extkey *)
	grub_hfsplus_btree_recptr (&node->data->extoverflow_tree, nnode, ptr);
      extents = (struct grub_hfsplus_extent *) (key + 1);
199 200

      /* The block wasn't found.  Perhaps the next iteration will find
201
	 it.  The last block we found is stored in BLKSLEFT now.  */
202 203
    }

204
  grub_free (nnode);
205 206 207 208 209 210 211 212

  /* Too bad, you lose.  */
  return -1;
}


/* Read LEN bytes from the file described by DATA starting with byte
   POS.  Return the amount of read bytes in READ.  */
213
grub_ssize_t
214
grub_hfsplus_read_file (grub_fshelp_node_t node,
215
			grub_disk_read_hook_t read_hook, void *read_hook_data,
216
			grub_off_t pos, grub_size_t len, char *buf)
217
{
218 219
  return grub_fshelp_read_file (node->data->disk, node,
				read_hook, read_hook_data,
220 221
				pos, len, buf, grub_hfsplus_read_block,
				node->size,
222 223
				node->data->log2blksize - GRUB_DISK_SECTOR_BITS,
				node->data->embedded_offset);
224 225 226 227 228 229 230 231
}

static struct grub_hfsplus_data *
grub_hfsplus_mount (grub_disk_t disk)
{
  struct grub_hfsplus_data *data;
  struct grub_hfsplus_btheader header;
  struct grub_hfsplus_btnode node;
232
  grub_uint16_t magic;
233 234 235 236
  union {
    struct grub_hfs_sblock hfs;
    struct grub_hfsplus_volheader hfsplus;
  } volheader;
237 238 239 240 241 242 243 244

  data = grub_malloc (sizeof (*data));
  if (!data)
    return 0;

  data->disk = disk;

  /* Read the bootblock.  */
245
  grub_disk_read (disk, GRUB_HFSPLUS_SBLOCK, 0, sizeof (volheader),
246
		  &volheader);
247 248 249
  if (grub_errno)
    goto fail;

250 251 252
  data->embedded_offset = 0;
  if (grub_be_to_cpu16 (volheader.hfs.magic) == GRUB_HFS_MAGIC)
    {
253 254 255
      grub_disk_addr_t extent_start;
      grub_disk_addr_t ablk_size;
      grub_disk_addr_t ablk_start;
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272

      /* See if there's an embedded HFS+ filesystem.  */
      if (grub_be_to_cpu16 (volheader.hfs.embed_sig) != GRUB_HFSPLUS_MAGIC)
	{
	  grub_error (GRUB_ERR_BAD_FS, "not a HFS+ filesystem");
	  goto fail;
	}

      /* Calculate the offset needed to translate HFS+ sector numbers.  */
      extent_start = grub_be_to_cpu16 (volheader.hfs.embed_extent.first_block);
      ablk_size = grub_be_to_cpu32 (volheader.hfs.blksz);
      ablk_start = grub_be_to_cpu16 (volheader.hfs.first_block);
      data->embedded_offset = (ablk_start
			       + extent_start
			       * (ablk_size >> GRUB_DISK_SECTOR_BITS));

      grub_disk_read (disk, data->embedded_offset + GRUB_HFSPLUS_SBLOCK, 0,
273
		      sizeof (volheader), &volheader);
274 275 276 277 278
      if (grub_errno)
	goto fail;
    }

  /* Make sure this is an HFS+ filesystem.  XXX: Do we really support
279
     HFX?  */
280
  magic = grub_be_to_cpu16 (volheader.hfsplus.magic);
281 282 283 284
  if (((magic != GRUB_HFSPLUS_MAGIC) && (magic != GRUB_HFSPLUSX_MAGIC))
      || volheader.hfsplus.blksize == 0
      || ((volheader.hfsplus.blksize & (volheader.hfsplus.blksize - 1)) != 0)
      || grub_be_to_cpu32 (volheader.hfsplus.blksize) < GRUB_DISK_SECTOR_SIZE)
285 286 287 288 289
    {
      grub_error (GRUB_ERR_BAD_FS, "not a HFS+ filesystem");
      goto fail;
    }

290
  grub_memcpy (&data->volheader, &volheader.hfsplus,
291
	       sizeof (volheader.hfsplus));
292

293 294 295
  for (data->log2blksize = 0;
       (1U << data->log2blksize) < grub_be_to_cpu32 (data->volheader.blksize);
       data->log2blksize++);
296 297 298 299

  /* Make a new node for the catalog tree.  */
  data->catalog_tree.file.data = data;
  data->catalog_tree.file.fileid = GRUB_HFSPLUS_FILEID_CATALOG;
300
  data->catalog_tree.file.compressed = 0;
301 302 303
  grub_memcpy (&data->catalog_tree.file.extents,
	       data->volheader.catalog_file.extents,
	       sizeof data->volheader.catalog_file.extents);
304
  data->catalog_tree.file.size =
305 306
    grub_be_to_cpu64 (data->volheader.catalog_file.size);

307 308 309 310 311 312 313 314 315 316
  data->attr_tree.file.data = data;
  data->attr_tree.file.fileid = GRUB_HFSPLUS_FILEID_ATTR;
  grub_memcpy (&data->attr_tree.file.extents,
	       data->volheader.attr_file.extents,
	       sizeof data->volheader.attr_file.extents);

  data->attr_tree.file.size =
    grub_be_to_cpu64 (data->volheader.attr_file.size);
  data->attr_tree.file.compressed = 0;

317 318 319
  /* Make a new node for the extent overflow file.  */
  data->extoverflow_tree.file.data = data;
  data->extoverflow_tree.file.fileid = GRUB_HFSPLUS_FILEID_OVERFLOW;
320
  data->extoverflow_tree.file.compressed = 0;
321 322 323 324
  grub_memcpy (&data->extoverflow_tree.file.extents,
	       data->volheader.extents_file.extents,
	       sizeof data->volheader.catalog_file.extents);

325
  data->extoverflow_tree.file.size =
326 327 328
    grub_be_to_cpu64 (data->volheader.extents_file.size);

  /* Read the essential information about the trees.  */
329
  if (grub_hfsplus_read_file (&data->catalog_tree.file, 0, 0,
330 331
			      sizeof (struct grub_hfsplus_btnode),
			      sizeof (header), (char *) &header) <= 0)
332 333 334 335
    goto fail;

  data->catalog_tree.root = grub_be_to_cpu32 (header.root);
  data->catalog_tree.nodesize = grub_be_to_cpu16 (header.nodesize);
336 337
  data->case_sensitive = ((magic == GRUB_HFSPLUSX_MAGIC) &&
			  (header.key_compare == GRUB_HFSPLUSX_BINARYCOMPARE));
338

339 340 341
  if (data->catalog_tree.nodesize < 2)
    goto fail;

342
  if (grub_hfsplus_read_file (&data->extoverflow_tree.file, 0, 0,
343 344
			      sizeof (struct grub_hfsplus_btnode),
			      sizeof (header), (char *) &header) <= 0)
345 346 347 348
    goto fail;

  data->extoverflow_tree.root = grub_be_to_cpu32 (header.root);

349
  if (grub_hfsplus_read_file (&data->extoverflow_tree.file, 0, 0, 0,
350
			      sizeof (node), (char *) &node) <= 0)
351 352 353 354 355
    goto fail;

  data->extoverflow_tree.root = grub_be_to_cpu32 (header.root);
  data->extoverflow_tree.nodesize = grub_be_to_cpu16 (header.nodesize);

356 357 358
  if (data->extoverflow_tree.nodesize < 2)
    goto fail;

359 360 361 362 363 364 365 366 367 368 369 370 371 372
  if (grub_hfsplus_read_file (&data->attr_tree.file, 0, 0,
			      sizeof (struct grub_hfsplus_btnode),
			      sizeof (header), (char *) &header) <= 0)
    {
      grub_errno = 0;
      data->attr_tree.root = 0;
      data->attr_tree.nodesize = 0;
    }
  else
    {
      data->attr_tree.root = grub_be_to_cpu32 (header.root);
      data->attr_tree.nodesize = grub_be_to_cpu16 (header.nodesize);
    }

373 374 375 376 377 378
  data->dirroot.data = data;
  data->dirroot.fileid = GRUB_HFSPLUS_FILEID_ROOTDIR;

  return data;

 fail:
379 380

  if (grub_errno == GRUB_ERR_OUT_OF_RANGE)
381
    grub_error (GRUB_ERR_BAD_FS, "not a HFS+ filesystem");
382

383 384 385 386 387 388 389 390 391 392 393 394 395
  grub_free (data);
  return 0;
}

/* Compare the on disk catalog key KEYA with the catalog key we are
   looking for (KEYB).  */
static int
grub_hfsplus_cmp_catkey (struct grub_hfsplus_key *keya,
			 struct grub_hfsplus_key_internal *keyb)
{
  struct grub_hfsplus_catkey *catkey_a = &keya->catkey;
  struct grub_hfsplus_catkey_internal *catkey_b = &keyb->catkey;
  int diff;
396
  grub_size_t len;
397

398 399 400 401 402 403
  /* Safe unsigned comparison */
  grub_uint32_t aparent = grub_be_to_cpu32 (catkey_a->parent);
  if (aparent > catkey_b->parent)
    return 1;
  if (aparent < catkey_b->parent)
    return -1;
404

405 406 407
  len = grub_be_to_cpu16 (catkey_a->namelen);
  if (len > catkey_b->namelen)
    len = catkey_b->namelen;
408 409
  /* Since it's big-endian memcmp gives the same result as manually comparing
     uint16_t but may be faster.  */
410
  diff = grub_memcmp (catkey_a->name, catkey_b->name,
411
		      len * sizeof (catkey_a->name[0]));
412 413
  if (diff == 0)
    diff = grub_be_to_cpu16 (catkey_a->namelen) - catkey_b->namelen;
414 415 416 417

  return diff;
}

418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436
/* Compare the on disk catalog key KEYA with the catalog key we are
   looking for (KEYB).  */
static int
grub_hfsplus_cmp_catkey_id (struct grub_hfsplus_key *keya,
			 struct grub_hfsplus_key_internal *keyb)
{
  struct grub_hfsplus_catkey *catkey_a = &keya->catkey;
  struct grub_hfsplus_catkey_internal *catkey_b = &keyb->catkey;

  /* Safe unsigned comparison */
  grub_uint32_t aparent = grub_be_to_cpu32 (catkey_a->parent);
  if (aparent > catkey_b->parent)
    return 1;
  if (aparent < catkey_b->parent)
    return -1;

  return 0;
}

437 438 439 440 441 442 443 444
/* Compare the on disk extent overflow key KEYA with the extent
   overflow key we are looking for (KEYB).  */
static int
grub_hfsplus_cmp_extkey (struct grub_hfsplus_key *keya,
			 struct grub_hfsplus_key_internal *keyb)
{
  struct grub_hfsplus_extkey *extkey_a = &keya->extkey;
  struct grub_hfsplus_extkey_internal *extkey_b = &keyb->extkey;
445 446 447 448 449 450 451 452
  grub_uint32_t akey;

  /* Safe unsigned comparison */
  akey = grub_be_to_cpu32 (extkey_a->fileid);
  if (akey > extkey_b->fileid)
    return 1;
  if (akey < extkey_b->fileid)
    return -1;
453 454 455 456 457

  if (extkey_a->type > extkey_b->type)
    return 1;
  if (extkey_a->type < extkey_b->type)
    return -1;
458 459 460 461 462 463

  if (extkey_a->type > extkey_b->type)
    return +1;

  if (extkey_a->type < extkey_b->type)
    return -1;
464 465 466 467 468 469 470
  
  akey = grub_be_to_cpu32 (extkey_a->start);
  if (akey > extkey_b->start)
    return 1;
  if (akey < extkey_b->start)
    return -1;
  return 0;
471 472 473 474 475 476 477 478 479 480 481 482
}

static char *
grub_hfsplus_read_symlink (grub_fshelp_node_t node)
{
  char *symlink;
  grub_ssize_t numread;

  symlink = grub_malloc (node->size + 1);
  if (!symlink)
    return 0;

483
  numread = grub_hfsplus_read_file (node, 0, 0, 0, node->size, symlink);
484 485 486 487 488 489 490 491 492 493
  if (numread != (grub_ssize_t) node->size)
    {
      grub_free (symlink);
      return 0;
    }
  symlink[node->size] = '\0';

  return symlink;
}

494
static int
495 496
grub_hfsplus_btree_iterate_node (struct grub_hfsplus_btree *btree,
				 struct grub_hfsplus_btnode *first_node,
497
				 grub_disk_addr_t first_rec,
498 499
				 int (*hook) (void *record, void *hook_arg),
				 void *hook_arg)
500
{
501
  grub_disk_addr_t rec;
502 503
  grub_uint64_t saved_node = -1;
  grub_uint64_t node_count = 0;
504 505 506 507 508 509 510 511

  for (;;)
    {
      char *cnode = (char *) first_node;

      /* Iterate over all records in this node.  */
      for (rec = first_rec; rec < grub_be_to_cpu16 (first_node->count); rec++)
	{
512
	  if (hook (grub_hfsplus_btree_recptr (btree, first_node, rec), hook_arg))
513 514 515 516 517 518
	    return 1;
	}

      if (! first_node->next)
	break;

519 520 521 522 523 524 525 526 527
      if (node_count && first_node->next == saved_node)
	{
	  grub_error (GRUB_ERR_BAD_FS, "HFS+ btree loop");
	  return 0;
	}
      if (!(node_count & (node_count - 1)))
	saved_node = first_node->next;
      node_count++;

528
      if (grub_hfsplus_read_file (&btree->file, 0, 0,
529 530
				  (((grub_disk_addr_t)
				    grub_be_to_cpu32 (first_node->next))
531 532
				   * btree->nodesize),
				  btree->nodesize, cnode) <= 0)
533 534 535 536 537 538 539 540 541 542 543 544
	return 1;

      /* Don't skip any record in the next iteration.  */
      first_rec = 0;
    }

  return 0;
}

/* Lookup the node described by KEY in the B+ Tree BTREE.  Compare
   keys using the function COMPARE_KEYS.  When a match is found,
   return the node in MATCHNODE and a pointer to the data in this node
545
   in KEYOFFSET.  MATCHNODE should be freed by the caller.  */
546
grub_err_t
547 548 549 550
grub_hfsplus_btree_search (struct grub_hfsplus_btree *btree,
			   struct grub_hfsplus_key_internal *key,
			   int (*compare_keys) (struct grub_hfsplus_key *keya,
						struct grub_hfsplus_key_internal *keyb),
551 552
			   struct grub_hfsplus_btnode **matchnode, 
			   grub_off_t *keyoffset)
553 554 555 556
{
  grub_uint64_t currnode;
  char *node;
  struct grub_hfsplus_btnode *nodedesc;
557
  grub_disk_addr_t rec;
558 559
  grub_uint64_t save_node;
  grub_uint64_t node_count = 0;
560

561 562 563 564 565 566
  if (!btree->nodesize)
    {
      *matchnode = 0;
      return 0;
    }

567 568 569 570 571
  node = grub_malloc (btree->nodesize);
  if (! node)
    return grub_errno;

  currnode = btree->root;
572
  save_node = currnode - 1;
573 574 575 576
  while (1)
    {
      int match = 0;

577 578 579 580 581 582 583 584 585
      if (save_node == currnode)
	{
	  grub_free (node);
	  return grub_error (GRUB_ERR_BAD_FS, "HFS+ btree loop");
	}
      if (!(node_count & (node_count - 1)))
	save_node = currnode;
      node_count++;

586
      /* Read a node.  */
587
      if (grub_hfsplus_read_file (&btree->file, 0, 0,
588 589
				  (grub_disk_addr_t) currnode
				  * (grub_disk_addr_t) btree->nodesize,
590
				  btree->nodesize, (char *) node) <= 0)
591 592
	{
	  grub_free (node);
593
	  return grub_error (GRUB_ERR_BAD_FS, "couldn't read i-node");
594 595 596 597 598 599 600 601
	}

      nodedesc = (struct grub_hfsplus_btnode *) node;

      /* Find the record in this tree.  */
      for (rec = 0; rec < grub_be_to_cpu16 (nodedesc->count); rec++)
	{
	  struct grub_hfsplus_key *currkey;
602 603
	  currkey = grub_hfsplus_btree_recptr (btree, nodedesc, rec);

604 605 606 607 608 609 610 611 612 613 614 615 616 617
	  /* The action that has to be taken depend on the type of
	     record.  */
	  if (nodedesc->type == GRUB_HFSPLUS_BTNODE_TYPE_LEAF
	      && compare_keys (currkey, key) == 0)
	    {
	      /* An exact match was found!  */

	      *matchnode = nodedesc;
	      *keyoffset = rec;

	      return 0;
	    }
	  else if (nodedesc->type == GRUB_HFSPLUS_BTNODE_TYPE_INDEX)
	    {
618
	      void *pointer;
619

620
	      /* The place where the key could have been found didn't
621 622 623 624 625 626 627 628 629
		 contain the key.  This means that the previous match
		 is the one that should be followed.  */
	      if (compare_keys (currkey, key) > 0)
		break;

	      /* Mark the last key which is lower or equal to the key
		 that we are looking for.  The last match that is
		 found will be used to locate the child which can
		 contain the record.  */
630 631 632 633
	      pointer = ((char *) currkey
			 + grub_be_to_cpu16 (currkey->keylen)
			 + 2);
	      currnode = grub_be_to_cpu32 (grub_get_unaligned32 (pointer));
634 635 636 637
	      match = 1;
	    }
	}

638
      /* No match is found, no record with this key exists in the
639 640 641 642 643
	 tree.  */
      if (! match)
	{
	  *matchnode = 0;
	  grub_free (node);
644
	  return 0;
645 646 647 648
	}
    }
}

649 650 651 652 653 654 655 656
struct list_nodes_ctx
{
  int ret;
  grub_fshelp_node_t dir;
  grub_fshelp_iterate_dir_hook_t hook;
  void *hook_data;
};

657
static int
658
list_nodes (void *record, void *hook_arg)
659
{
660 661 662 663 664 665 666
  struct grub_hfsplus_catkey *catkey;
  char *filename;
  int i;
  struct grub_fshelp_node *node;
  struct grub_hfsplus_catfile *fileinfo;
  enum grub_fshelp_filetype type = GRUB_FSHELP_UNKNOWN;
  struct list_nodes_ctx *ctx = hook_arg;
667

668 669 670 671 672 673 674 675 676 677 678 679 680 681
  catkey = (struct grub_hfsplus_catkey *) record;

  fileinfo =
    (struct grub_hfsplus_catfile *) ((char *) record
				     + grub_be_to_cpu16 (catkey->keylen)
				     + 2 + (grub_be_to_cpu16(catkey->keylen)
					    % 2));

  /* Stop iterating when the last directory entry is found.  */
  if (grub_be_to_cpu32 (catkey->parent) != ctx->dir->fileid)
    return 1;

  /* Determine the type of the node that is found.  */
  switch (fileinfo->type)
682
    {
683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703
    case grub_cpu_to_be16_compile_time (GRUB_HFSPLUS_FILETYPE_REG):
      {
	int mode = (grub_be_to_cpu16 (fileinfo->mode)
		    & GRUB_HFSPLUS_FILEMODE_MASK);

	if (mode == GRUB_HFSPLUS_FILEMODE_REG)
	  type = GRUB_FSHELP_REG;
	else if (mode == GRUB_HFSPLUS_FILEMODE_SYMLINK)
	  type = GRUB_FSHELP_SYMLINK;
	else
	  type = GRUB_FSHELP_UNKNOWN;
	break;
      }
    case grub_cpu_to_be16_compile_time (GRUB_HFSPLUS_FILETYPE_DIR):
      type = GRUB_FSHELP_DIR;
      break;
    case grub_cpu_to_be16_compile_time (GRUB_HFSPLUS_FILETYPE_DIR_THREAD):
      if (ctx->dir->fileid == 2)
	return 0;
      node = grub_malloc (sizeof (*node));
      if (!node)
704
	return 1;
705 706 707 708
      node->data = ctx->dir->data;
      node->mtime = 0;
      node->size = 0;
      node->fileid = grub_be_to_cpu32 (fileinfo->parentid);
709

710 711 712
      ctx->ret = ctx->hook ("..", GRUB_FSHELP_DIR, node, ctx->hook_data);
      return ctx->ret;
    }
713

714 715
  if (type == GRUB_FSHELP_UNKNOWN)
    return 0;
716

717 718 719 720
  filename = grub_malloc (grub_be_to_cpu16 (catkey->namelen)
			  * GRUB_MAX_UTF8_PER_UTF16 + 1);
  if (! filename)
    return 0;
721

722 723 724 725
  /* Make sure the byte order of the UTF16 string is correct.  */
  for (i = 0; i < grub_be_to_cpu16 (catkey->namelen); i++)
    {
      catkey->name[i] = grub_be_to_cpu16 (catkey->name[i]);
726

727 728
      if (catkey->name[i] == '/')
	catkey->name[i] = ':';
729

730 731
      /* If the name is obviously invalid, skip this node.  */
      if (catkey->name[i] == 0)
732 733 734 735
	{
	  grub_free (filename);
	  return 0;
	}
736
    }
737

738 739
  *grub_utf16_to_utf8 ((grub_uint8_t *) filename, catkey->name,
		       grub_be_to_cpu16 (catkey->namelen)) = '\0';
740

741 742 743 744 745 746 747
  /* Restore the byte order to what it was previously.  */
  for (i = 0; i < grub_be_to_cpu16 (catkey->namelen); i++)
    {
      if (catkey->name[i] == ':')
	catkey->name[i] = '/';
      catkey->name[i] = grub_be_to_cpu16 (catkey->name[i]);
    }
748

749 750 751
  /* hfs+ is case insensitive.  */
  if (! ctx->dir->data->case_sensitive)
    type |= GRUB_FSHELP_CASE_INSENSITIVE;
752

753 754 755 756
  /* A valid node is found; setup the node and call the
     callback function.  */
  node = grub_malloc (sizeof (*node));
  if (!node)
757 758 759 760
    {
      grub_free (filename);
      return 1;
    }
761
  node->data = ctx->dir->data;
762 763 764
  node->compressed = 0;
  node->cbuf = 0;
  node->compress_index = 0;
765

766 767
  grub_memcpy (node->extents, fileinfo->data.extents,
	       sizeof (node->extents));
768 769
  grub_memcpy (node->resource_extents, fileinfo->resource.extents,
	       sizeof (node->resource_extents));
770 771
  node->mtime = grub_be_to_cpu32 (fileinfo->mtime) - 2082844800;
  node->size = grub_be_to_cpu64 (fileinfo->data.size);
772
  node->resource_size = grub_be_to_cpu64 (fileinfo->resource.size);
773
  node->fileid = grub_be_to_cpu32 (fileinfo->fileid);
774

775
  ctx->ret = ctx->hook (filename, type, node, ctx->hook_data);
776

777
  grub_free (filename);
778

779 780
  return ctx->ret;
}
781

782 783 784 785 786 787 788 789 790 791 792
static int
grub_hfsplus_iterate_dir (grub_fshelp_node_t dir,
			  grub_fshelp_iterate_dir_hook_t hook, void *hook_data)
{
  struct list_nodes_ctx ctx =
  {
    .ret = 0,
    .dir = dir,
    .hook = hook,
    .hook_data = hook_data
  };
793 794

  struct grub_hfsplus_key_internal intern;
795 796
  struct grub_hfsplus_btnode *node = NULL;
  grub_disk_addr_t ptr = 0;
797

798 799 800 801 802 803
  {
    struct grub_fshelp_node *fsnode;
    fsnode = grub_malloc (sizeof (*fsnode));
    if (!fsnode)
      return 1;
    *fsnode = *dir;
804
    if (hook (".", GRUB_FSHELP_DIR, fsnode, hook_data))
805 806 807
      return 1;
  }

808 809
  /* Create a key that points to the first entry in the directory.  */
  intern.catkey.parent = dir->fileid;
810 811
  intern.catkey.name = 0;
  intern.catkey.namelen = 0;
812 813 814

  /* First lookup the first entry.  */
  if (grub_hfsplus_btree_search (&dir->data->catalog_tree, &intern,
815 816
				 grub_hfsplus_cmp_catkey, &node, &ptr)
      || !node)
817 818 819
    return 0;

  /* Iterate over all entries in this directory.  */
820
  grub_hfsplus_btree_iterate_node (&dir->data->catalog_tree, node, ptr,
821
				   list_nodes, &ctx);
822 823 824

  grub_free (node);

825
  return ctx.ret;
826 827 828 829 830 831 832 833
}

/* Open a file named NAME and initialize FILE.  */
static grub_err_t
grub_hfsplus_open (struct grub_file *file, const char *name)
{
  struct grub_hfsplus_data *data;
  struct grub_fshelp_node *fdiro = 0;
834

835
  grub_dl_ref (my_mod);
836

837 838 839 840 841 842 843 844 845 846
  data = grub_hfsplus_mount (file->device->disk);
  if (!data)
    goto fail;

  grub_fshelp_find_file (name, &data->dirroot, &fdiro,
			 grub_hfsplus_iterate_dir,
			 grub_hfsplus_read_symlink, GRUB_FSHELP_REG);
  if (grub_errno)
    goto fail;

847 848 849 850 851 852 853 854
  if (grub_hfsplus_open_compressed)
    {
      grub_err_t err;
      err = grub_hfsplus_open_compressed (fdiro);
      if (err)
	goto fail;
    }

855 856 857 858 859 860 861 862 863 864 865 866 867
  file->size = fdiro->size;
  data->opened_file = *fdiro;
  grub_free (fdiro);

  file->data = data;
  file->offset = 0;

  return 0;

 fail:
  if (data && fdiro != &data->dirroot)
    grub_free (fdiro);
  grub_free (data);
868

869 870 871 872 873 874 875 876 877
  grub_dl_unref (my_mod);

  return grub_errno;
}


static grub_err_t
grub_hfsplus_close (grub_file_t file)
{
878 879 880 881 882 883 884
  struct grub_hfsplus_data *data =
    (struct grub_hfsplus_data *) file->data;

  grub_free (data->opened_file.cbuf);
  grub_free (data->opened_file.compress_index);

  grub_free (data);
885 886 887 888 889 890 891 892

  grub_dl_unref (my_mod);

  return GRUB_ERR_NONE;
}

/* Read LEN bytes data from FILE into BUF.  */
static grub_ssize_t
893
grub_hfsplus_read (grub_file_t file, char *buf, grub_size_t len)
894
{
895
  struct grub_hfsplus_data *data =
896 897
    (struct grub_hfsplus_data *) file->data;

898 899
  data->opened_file.file = file;

900 901 902 903
  if (grub_hfsplus_read_compressed && data->opened_file.compressed)
    return grub_hfsplus_read_compressed (&data->opened_file,
					 file->offset, len, buf);

904 905 906
  return grub_hfsplus_read_file (&data->opened_file,
				 file->read_hook, file->read_hook_data,
				 file->offset, len, buf);
907 908
}

909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928
/* Context for grub_hfsplus_dir.  */
struct grub_hfsplus_dir_ctx
{
  grub_fs_dir_hook_t hook;
  void *hook_data;
};

/* Helper for grub_hfsplus_dir.  */
static int
grub_hfsplus_dir_iter (const char *filename,
		       enum grub_fshelp_filetype filetype,
		       grub_fshelp_node_t node, void *data)
{
  struct grub_hfsplus_dir_ctx *ctx = data;
  struct grub_dirhook_info info;

  grub_memset (&info, 0, sizeof (info));
  info.dir = ((filetype & GRUB_FSHELP_TYPE_MASK) == GRUB_FSHELP_DIR);
  info.mtimeset = 1;
  info.mtime = node->mtime;
929 930
  info.inodeset = 1;
  info.inode = node->fileid;
931 932 933 934 935
  info.case_insensitive = !! (filetype & GRUB_FSHELP_CASE_INSENSITIVE);
  grub_free (node);
  return ctx->hook (filename, &info, ctx->hook_data);
}

936
static grub_err_t
937
grub_hfsplus_dir (grub_device_t device, const char *path,
938
		  grub_fs_dir_hook_t hook, void *hook_data)
939
{
940
  struct grub_hfsplus_dir_ctx ctx = { hook, hook_data };
941 942
  struct grub_hfsplus_data *data = 0;
  struct grub_fshelp_node *fdiro = 0;
943

944
  grub_dl_ref (my_mod);
945

946 947 948 949 950 951 952 953 954 955 956 957
  data = grub_hfsplus_mount (device->disk);
  if (!data)
    goto fail;

  /* Find the directory that should be opened.  */
  grub_fshelp_find_file (path, &data->dirroot, &fdiro,
			 grub_hfsplus_iterate_dir,
			 grub_hfsplus_read_symlink, GRUB_FSHELP_DIR);
  if (grub_errno)
    goto fail;

  /* Iterate over all entries in this directory.  */
958
  grub_hfsplus_iterate_dir (fdiro, grub_hfsplus_dir_iter, &ctx);
959

960 961 962 963 964 965 966 967 968 969 970 971
 fail:
  if (data && fdiro != &data->dirroot)
    grub_free (fdiro);
  grub_free (data);

  grub_dl_unref (my_mod);

  return grub_errno;
}


static grub_err_t
972
grub_hfsplus_label (grub_device_t device, char **label)
973
{
974 975 976 977 978
  struct grub_hfsplus_data *data;
  grub_disk_t disk = device->disk;
  struct grub_hfsplus_catkey *catkey;
  int i, label_len;
  struct grub_hfsplus_key_internal intern;
979 980
  struct grub_hfsplus_btnode *node = NULL;
  grub_disk_addr_t ptr = 0;
981 982 983 984 985 986 987 988 989

  *label = 0;

  data = grub_hfsplus_mount (disk);
  if (!data)
    return grub_errno;

  /* Create a key that points to the label.  */
  intern.catkey.parent = 1;
990 991
  intern.catkey.name = 0;
  intern.catkey.namelen = 0;
992 993 994

  /* First lookup the first entry.  */
  if (grub_hfsplus_btree_search (&data->catalog_tree, &intern,
995 996
				 grub_hfsplus_cmp_catkey_id, &node, &ptr)
      || !node)
997 998 999 1000 1001 1002
    {
      grub_free (data);
      return 0;
    }

  catkey = (struct grub_hfsplus_catkey *)
1003
    grub_hfsplus_btree_recptr (&data->catalog_tree, node, ptr);
1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014

  label_len = grub_be_to_cpu16 (catkey->namelen);
  for (i = 0; i < label_len; i++)
    {
      catkey->name[i] = grub_be_to_cpu16 (catkey->name[i]);

      /* If the name is obviously invalid, skip this node.  */
      if (catkey->name[i] == 0)
	return 0;
    }

1015
  *label = grub_malloc (label_len * GRUB_MAX_UTF8_PER_UTF16 + 1);
1016 1017 1018
  if (! *label)
    return grub_errno;

1019 1020
  *grub_utf16_to_utf8 ((grub_uint8_t *) (*label), catkey->name,
		       label_len) = '\0';
1021 1022 1023 1024 1025

  grub_free (node);
  grub_free (data);

  return GRUB_ERR_NONE;
1026 1027
}

1028
/* Get mtime.  */
1029
static grub_err_t
1030 1031 1032 1033 1034 1035 1036 1037 1038 1039
grub_hfsplus_mtime (grub_device_t device, grub_int32_t *tm)
{
  struct grub_hfsplus_data *data;
  grub_disk_t disk = device->disk;

  grub_dl_ref (my_mod);

  data = grub_hfsplus_mount (disk);
  if (!data)
    *tm = 0;
1040
  else
1041 1042 1043 1044 1045 1046 1047 1048 1049 1050
    *tm = grub_be_to_cpu32 (data->volheader.utime) - 2082844800;

  grub_dl_unref (my_mod);

  grub_free (data);

  return grub_errno;

}

1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061
static grub_err_t
grub_hfsplus_uuid (grub_device_t device, char **uuid)
{
  struct grub_hfsplus_data *data;
  grub_disk_t disk = device->disk;

  grub_dl_ref (my_mod);

  data = grub_hfsplus_mount (disk);
  if (data)
    {
1062
      *uuid = grub_xasprintf ("%016llx",
1063 1064
			     (unsigned long long)
			     grub_be_to_cpu64 (data->volheader.num_serial));
1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075
    }
  else
    *uuid = NULL;

  grub_dl_unref (my_mod);

  grub_free (data);

  return grub_errno;
}

1076

1077 1078 1079 1080 1081 1082 1083 1084 1085

static struct grub_fs grub_hfsplus_fs =
  {
    .name = "hfsplus",
    .dir = grub_hfsplus_dir,
    .open = grub_hfsplus_open,
    .read = grub_hfsplus_read,
    .close = grub_hfsplus_close,
    .label = grub_hfsplus_label,
1086
    .mtime = grub_hfsplus_mtime,
1087
    .uuid = grub_hfsplus_uuid,
1088 1089
#ifdef GRUB_UTIL
    .reserved_first_sector = 1,
1090
    .blocklist_install = 1,
1091
#endif
1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104
    .next = 0
  };

GRUB_MOD_INIT(hfsplus)
{
  grub_fs_register (&grub_hfsplus_fs);
  my_mod = mod;
}

GRUB_MOD_FINI(hfsplus)
{
  grub_fs_unregister (&grub_hfsplus_fs);
}