3 * GRUB -- GRand Unified Bootloader
4 * Copyright (C) 2004,2005,2006,2007 Free Software Foundation, Inc.
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.
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.
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/>.
20 /* HFS is documented at
21 http://developer.apple.com/documentation/mac/Files/Files-2.html */
24 #include <grub/file.h>
26 #include <grub/misc.h>
27 #include <grub/disk.h>
29 #include <grub/types.h>
32 #define GRUB_HFS_SBLOCK 2
33 #define GRUB_HFS_EMBED_HFSPLUS_SIG 0x482B
35 #define GRUB_HFS_BLKS (data->blksz >> 9)
37 #define GRUB_HFS_NODE_LEAF 0xFF
39 /* The two supported filesystems a record can have. */
42 GRUB_HFS_FILETYPE_DIR
= 1,
43 GRUB_HFS_FILETYPE_FILE
= 2
46 /* Catalog node ID (CNID). */
47 enum grub_hfs_cnid_type
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,
56 /* A node descriptor. This is the header of every node. */
65 } __attribute__ ((packed
));
67 /* The head of the B*-Tree. */
68 struct grub_hfs_treeheader
70 grub_uint16_t tree_depth
;
71 /* The number of the first node. */
72 grub_uint32_t root_node
;
74 grub_uint32_t first_leaf
;
75 grub_uint32_t last_leaf
;
76 grub_uint16_t node_size
;
77 grub_uint16_t key_size
;
79 grub_uint32_t free_nodes
;
80 grub_uint8_t unused
[76];
81 } __attribute__ ((packed
));
83 /* The state of a mounted HFS filesystem. */
86 struct grub_hfs_sblock sblock
;
88 grub_hfs_datarecord_t extents
;
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
105 grub_uint32_t parent_dir
;
107 /* Filename length. */
111 grub_uint8_t str
[31];
112 } __attribute__ ((packed
));
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
117 struct grub_hfs_extent_key
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
122 grub_uint8_t forktype
;
123 grub_uint32_t fileid
;
124 grub_uint16_t first_block
;
125 } __attribute__ ((packed
));
127 /* A dirrect record. This is used to find out the directory ID. */
128 struct grub_hfs_dirrec
130 /* For a directory, type == 1. */
132 grub_uint8_t unused
[5];
134 } __attribute__ ((packed
));
136 /* Information about a file. */
137 struct grub_hfs_filerec
139 /* For a file, type == 2. */
141 grub_uint8_t unused
[19];
142 grub_uint32_t fileid
;
143 grub_uint8_t unused2
[2];
145 grub_uint8_t unused3
[44];
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
));
152 /* A record descriptor, both key and data, used to pass to call back
154 struct grub_hfs_record
163 static grub_dl_t my_mod
;
166 static int grub_hfs_find_node (struct grub_hfs_data
*, char *,
167 grub_uint32_t
, int, char *, int);
169 /* Find block BLOCK of the file FILE in the mounted UFS filesystem
170 DATA. The first 3 extents are described by DAT. If cache is set,
171 using caching to improve non-random reads. */
173 grub_hfs_block (struct grub_hfs_data
*data
, grub_hfs_datarecord_t dat
,
174 int file
, int block
, int cache
)
176 grub_hfs_datarecord_t dr
;
178 struct grub_hfs_extent_key key
;
181 static int cache_file
= 0;
182 static int cache_pos
= 0;
183 static grub_hfs_datarecord_t cache_dr
;
185 grub_memcpy (dr
, dat
, sizeof (dr
));
188 key
.fileid
= grub_cpu_to_be32 (file
);
190 if (cache
&& cache_file
== file
&& block
> cache_pos
)
193 key
.first_block
= grub_cpu_to_be16 (pos
);
194 grub_memcpy (dr
, cache_dr
, sizeof (cache_dr
));
201 /* Try all 3 extents. */
202 for (i
= 0; i
< 3; i
++)
204 /* Check if the block is stored in this extent. */
205 if (grub_be_to_cpu16 (dr
[i
].count
) + pos
> block
)
207 int first
= grub_be_to_cpu16 (dr
[i
].first_block
);
209 /* If the cache is enabled, store the current position
215 grub_memcpy (cache_dr
, dr
, sizeof (cache_dr
));
218 return (grub_be_to_cpu16 (data
->sblock
.first_block
)
219 + (first
+ block
- pos
) * GRUB_HFS_BLKS
);
222 /* Try the next extent. */
223 pos
+= grub_be_to_cpu16 (dr
[i
].count
);
226 /* Lookup the block in the extent overflow file. */
227 key
.first_block
= grub_cpu_to_be16 (pos
);
229 grub_hfs_find_node (data
, (char *) &key
, data
->ext_root
,
230 1, (char *) &dr
, sizeof (dr
));
237 /* Read LEN bytes from the file described by DATA starting with byte
238 POS. Return the amount of read bytes in READ. */
240 grub_hfs_read_file (struct grub_hfs_data
*data
,
241 void NESTED_FUNC_ATTR (*read_hook
) (grub_disk_addr_t sector
,
242 unsigned offset
, unsigned length
),
243 int pos
, grub_size_t len
, char *buf
)
248 /* Adjust len so it we can't read past the end of the file. */
249 if (len
> grub_le_to_cpu32 (data
->size
))
250 len
= grub_le_to_cpu32 (data
->size
);
252 blockcnt
= ((len
+ pos
)
253 + data
->blksz
- 1) / data
->blksz
;
255 for (i
= pos
/ data
->blksz
; i
< blockcnt
; i
++)
258 int blockoff
= pos
% data
->blksz
;
259 int blockend
= data
->blksz
;
263 blknr
= grub_hfs_block (data
, data
->extents
, data
->fileid
, i
, 1);
268 if (i
== blockcnt
- 1)
270 blockend
= (len
+ pos
) % data
->blksz
;
272 /* The last portion is exactly EXT2_BLOCK_SIZE (data). */
274 blockend
= data
->blksz
;
278 if (i
== pos
/ data
->blksz
)
280 skipfirst
= blockoff
;
281 blockend
-= skipfirst
;
284 /* If the block number is 0 this block is not stored on disk but
285 is zero filled instead. */
288 data
->disk
->read_hook
= read_hook
;
289 grub_disk_read (data
->disk
, blknr
, skipfirst
,
291 data
->disk
->read_hook
= 0;
296 buf
+= data
->blksz
- skipfirst
;
303 /* Mount the filesystem on the disk DISK. */
304 static struct grub_hfs_data
*
305 grub_hfs_mount (grub_disk_t disk
)
307 struct grub_hfs_data
*data
;
308 struct grub_hfs_catalog_key key
;
309 struct grub_hfs_dirrec dir
;
314 struct grub_hfs_node node
;
315 struct grub_hfs_treeheader head
;
318 data
= grub_malloc (sizeof (struct grub_hfs_data
));
322 /* Read the superblock. */
323 if (grub_disk_read (disk
, GRUB_HFS_SBLOCK
, 0,
324 sizeof (struct grub_hfs_sblock
), (char *) &data
->sblock
))
327 /* Check if this is a HFS filesystem. */
328 if (grub_be_to_cpu16 (data
->sblock
.magic
) != GRUB_HFS_MAGIC
)
330 grub_error (GRUB_ERR_BAD_FS
, "not an HFS filesystem");
334 /* Check if this is an embedded HFS+ filesystem. */
335 if (grub_be_to_cpu16 (data
->sblock
.embed_sig
) == GRUB_HFS_EMBED_HFSPLUS_SIG
)
337 grub_error (GRUB_ERR_BAD_FS
, "embedded HFS+ filesystem");
341 data
->blksz
= grub_be_to_cpu32 (data
->sblock
.blksz
);
344 /* Lookup the root node of the extent overflow tree. */
345 first_block
= ((grub_be_to_cpu16 (data
->sblock
.extent_recs
[0].first_block
)
347 + grub_be_to_cpu16 (data
->sblock
.first_block
));
349 if (grub_disk_read (data
->disk
, first_block
, 0,
350 sizeof (treehead
), (char *) &treehead
))
352 data
->ext_root
= grub_be_to_cpu32 (treehead
.head
.root_node
);
353 data
->ext_size
= grub_be_to_cpu16 (treehead
.head
.node_size
);
355 /* Lookup the root node of the catalog tree. */
356 first_block
= ((grub_be_to_cpu16 (data
->sblock
.catalog_recs
[0].first_block
)
358 + grub_be_to_cpu16 (data
->sblock
.first_block
));
359 if (grub_disk_read (data
->disk
, first_block
, 0,
360 sizeof (treehead
), (char *) &treehead
))
362 data
->cat_root
= grub_be_to_cpu32 (treehead
.head
.root_node
);
363 data
->cat_size
= grub_be_to_cpu16 (treehead
.head
.node_size
);
365 /* Lookup the root directory node in the catalog tree using the
367 key
.parent_dir
= grub_cpu_to_be32 (1);
368 key
.strlen
= data
->sblock
.volname
[0];
369 grub_strcpy ((char *) key
.str
, (char *) (data
->sblock
.volname
+ 1));
371 if (grub_hfs_find_node (data
, (char *) &key
, data
->cat_root
,
372 0, (char *) &dir
, sizeof (dir
)) == 0)
374 grub_error (GRUB_ERR_BAD_FS
, "can not find the hfs root directory");
381 data
->rootdir
= grub_be_to_cpu32 (dir
.dirid
);
387 if (grub_errno
== GRUB_ERR_OUT_OF_RANGE
)
388 grub_error (GRUB_ERR_BAD_FS
, "not a hfs filesystem");
394 /* Compare the K1 and K2 catalog file keys. */
396 grub_hfs_cmp_catkeys (struct grub_hfs_catalog_key
*k1
,
397 struct grub_hfs_catalog_key
*k2
)
399 int cmp
= (grub_be_to_cpu32 (k1
->parent_dir
)
400 - grub_be_to_cpu32 (k2
->parent_dir
));
405 cmp
= grub_strncasecmp ((char *) (k1
->str
), (char *) (k2
->str
), k1
->strlen
);
407 /* This is required because the compared strings are not of equal
409 if (cmp
== 0 && k1
->strlen
< k2
->strlen
)
415 /* Compare the K1 and K2 extent overflow file keys. */
417 grub_hfs_cmp_extkeys (struct grub_hfs_extent_key
*k1
,
418 struct grub_hfs_extent_key
*k2
)
420 int cmp
= k1
->forktype
- k2
->forktype
;
422 cmp
= grub_be_to_cpu32 (k1
->fileid
) - grub_be_to_cpu32 (k2
->fileid
);
424 cmp
= (grub_be_to_cpu16 (k1
->first_block
)
425 - grub_be_to_cpu16 (k2
->first_block
));
430 /* Iterate the records in the node with index IDX in the mounted HFS
431 filesystem DATA. This node holds data of the type TYPE (0 =
432 catalog node, 1 = extent overflow node). If this is set, continue
433 iterating to the next node. For every records, call NODE_HOOK. */
435 grub_hfs_iterate_records (struct grub_hfs_data
*data
, int type
, int idx
,
436 int this, int (*node_hook
) (struct grub_hfs_node
*hnd
,
437 struct grub_hfs_record
*))
439 int nodesize
= type
== 0 ? data
->cat_size
: data
->ext_size
;
443 struct grub_hfs_node node
;
444 char rawnode
[nodesize
];
445 grub_uint16_t offsets
[nodesize
/ 2];
451 struct grub_hfs_extent
*dat
;
454 dat
= (struct grub_hfs_extent
*) (type
== 0
455 ? (&data
->sblock
.catalog_recs
)
456 : (&data
->sblock
.extent_recs
));
458 /* Read the node into memory. */
459 blk
= grub_hfs_block (data
, dat
,
460 (type
== 0) ? GRUB_HFS_CNID_CAT
: GRUB_HFS_CNID_EXT
,
461 idx
/ (data
->blksz
/ nodesize
), 0);
462 blk
+= (idx
% (data
->blksz
/ nodesize
));
466 if (grub_disk_read (data
->disk
, blk
, 0,
467 sizeof (node
), (char *) &node
))
470 /* Iterate over all records in this node. */
471 for (i
= 0; i
< grub_be_to_cpu16 (node
.node
.reccnt
); i
++)
473 int pos
= (nodesize
>> 1) - 1 - i
;
478 } __attribute__ ((packed
)) *pnt
;
479 pnt
= (struct pointer
*) (grub_be_to_cpu16 (node
.offsets
[pos
])
482 struct grub_hfs_record rec
=
486 &pnt
->key
+ pnt
->keylen
+(pnt
->keylen
+ 1) % 2,
487 nodesize
- grub_be_to_cpu16 (node
.offsets
[pos
])
491 if (node_hook (&node
.node
, &rec
))
495 idx
= grub_be_to_cpu32 (node
.node
.next
);
496 } while (idx
&& this);
502 /* Lookup a record in the mounted filesystem DATA using the key KEY.
503 The index of the node on top of the tree is IDX. The tree is of
504 the type TYPE (0 = catalog node, 1 = extent overflow node). Return
505 the data in DATAR with a maximum length of DATALEN. */
507 grub_hfs_find_node (struct grub_hfs_data
*data
, char *key
,
508 grub_uint32_t idx
, int type
, char *datar
, int datalen
)
514 auto int node_found (struct grub_hfs_node
*, struct grub_hfs_record
*);
516 int node_found (struct grub_hfs_node
*hnd
, struct grub_hfs_record
*rec
)
521 cmp
= grub_hfs_cmp_catkeys (rec
->key
, (void *) key
);
523 cmp
= grub_hfs_cmp_extkeys (rec
->key
, (void *) key
);
525 /* If the key is smaller or equal to the currect node, mark the
526 entry. In case of a non-leaf mode it will be used to lookup
527 the rest of the tree. */
530 grub_uint32_t
*node
= (grub_uint32_t
*) rec
->data
;
531 found
= grub_be_to_cpu32 (*node
);
533 else /* The key can not be found in the tree. */
536 /* Check if this node is a leaf node. */
537 if (hnd
->type
== GRUB_HFS_NODE_LEAF
)
546 grub_memcpy (datar
, rec
->data
,
547 rec
->datalen
< datalen
? rec
->datalen
: datalen
);
559 if (grub_hfs_iterate_records (data
, type
, idx
, 0, node_found
))
572 /* Iterate over the directory with the id DIR. The tree is searched
573 starting with the node ROOT_IDX. For every entry in this directory
576 grub_hfs_iterate_dir (struct grub_hfs_data
*data
, grub_uint32_t root_idx
,
577 unsigned int dir
, int (*hook
) (struct grub_hfs_record
*))
583 /* The lowest key possible with DIR as root directory. */
584 struct grub_hfs_catalog_key key
= {0, grub_cpu_to_be32 (dir
), 0, ""};
586 auto int node_found (struct grub_hfs_node
*, struct grub_hfs_record
*);
587 auto int it_dir (struct grub_hfs_node
* __attribute ((unused
)),
588 struct grub_hfs_record
*);
591 int node_found (struct grub_hfs_node
*hnd
, struct grub_hfs_record
*rec
)
593 struct grub_hfs_catalog_key
*ckey
= rec
->key
;
595 if (grub_hfs_cmp_catkeys (rec
->key
, (void *) &key
) <= 0)
596 found
= grub_be_to_cpu32 (*(grub_uint32_t
*) rec
->data
);
598 if (hnd
->type
== 0xFF && ckey
->strlen
> 0)
601 next
= grub_be_to_cpu32 (hnd
->next
);
603 /* An entry was found. */
604 if (grub_be_to_cpu32 (ckey
->parent_dir
) == dir
)
611 int it_dir (struct grub_hfs_node
*hnd
__attribute ((unused
)),
612 struct grub_hfs_record
*rec
)
614 struct grub_hfs_catalog_key
*ckey
= rec
->key
;
615 struct grub_hfs_catalog_key
*origkey
= &key
;
617 /* Stop when the entries do not match anymore. */
618 if (grub_be_to_cpu32 (ckey
->parent_dir
)
619 != grub_be_to_cpu32 ((origkey
)->parent_dir
))
629 if (grub_hfs_iterate_records (data
, 0, root_idx
, 0, node_found
))
638 /* If there was a matching record in this leaf node, continue the
639 iteration until the last record was found. */
640 grub_hfs_iterate_records (data
, 0, next
, 1, it_dir
);
645 /* Find a file or directory with the pathname PATH in the filesystem
646 DATA. Return the file record in RETDATA when it is non-zero.
647 Return the directory number in RETINODE when it is non-zero. */
649 grub_hfs_find_dir (struct grub_hfs_data
*data
, const char *path
,
650 struct grub_hfs_filerec
*retdata
, int *retinode
)
652 int inode
= data
->rootdir
;
655 struct grub_hfs_filerec frec
;
656 struct grub_hfs_dirrec
*dir
= (struct grub_hfs_dirrec
*) &frec
;
657 frec
.type
= GRUB_HFS_FILETYPE_DIR
;
661 grub_error (GRUB_ERR_BAD_FILENAME
, "bad filename");
665 origpath
= grub_strdup (path
);
672 while (path
&& grub_strlen (path
))
674 if (frec
.type
!= GRUB_HFS_FILETYPE_DIR
)
676 grub_error (GRUB_ERR_BAD_FILE_TYPE
, "not a directory");
680 /* Isolate a part of the path. */
681 next
= grub_strchr (path
, '/');
688 struct grub_hfs_catalog_key key
;
690 key
.parent_dir
= grub_cpu_to_be32 (inode
);
691 key
.strlen
= grub_strlen (path
);
692 grub_strcpy ((char *) (key
.str
), path
);
694 /* Lookup this node. */
695 if (! grub_hfs_find_node (data
, (char *) &key
, data
->cat_root
,
696 0, (char *) &frec
, sizeof (frec
)))
698 grub_error (GRUB_ERR_FILE_NOT_FOUND
, "file not found");
705 inode
= grub_be_to_cpu32 (dir
->dirid
);
710 grub_memcpy (retdata
, &frec
, sizeof (frec
));
716 grub_free (origpath
);
723 grub_hfs_dir (grub_device_t device
, const char *path
,
724 int (*hook
) (const char *filename
, int dir
))
728 auto int dir_hook (struct grub_hfs_record
*rec
);
730 int dir_hook (struct grub_hfs_record
*rec
)
732 char fname
[32] = { 0 };
733 char *filetype
= rec
->data
;
734 struct grub_hfs_catalog_key
*ckey
= rec
->key
;
736 grub_strncpy (fname
, (char *) (ckey
->str
), ckey
->strlen
);
738 if (*filetype
== GRUB_HFS_FILETYPE_DIR
)
739 return hook (fname
, 1);
740 else if (*filetype
== GRUB_HFS_FILETYPE_FILE
)
741 return hook (fname
, 0);
745 struct grub_hfs_data
*data
;
746 struct grub_hfs_filerec frec
;
749 grub_dl_ref (my_mod
);
752 data
= grub_hfs_mount (device
->disk
);
756 /* First the directory ID for the directory. */
757 if (grub_hfs_find_dir (data
, path
, &frec
, &inode
))
760 if (frec
.type
!= GRUB_HFS_FILETYPE_DIR
)
762 grub_error (GRUB_ERR_BAD_FILE_TYPE
, "not a directory");
766 grub_hfs_iterate_dir (data
, data
->cat_root
, inode
, dir_hook
);
772 grub_dl_unref (my_mod
);
779 /* Open a file named NAME and initialize FILE. */
781 grub_hfs_open (struct grub_file
*file
, const char *name
)
783 struct grub_hfs_data
*data
;
784 struct grub_hfs_filerec frec
;
787 grub_dl_ref (my_mod
);
790 data
= grub_hfs_mount (file
->device
->disk
);
792 if (grub_hfs_find_dir (data
, name
, &frec
, 0))
796 grub_dl_unref (my_mod
);
801 if (frec
.type
!= GRUB_HFS_FILETYPE_FILE
)
804 grub_error (GRUB_ERR_BAD_FILE_TYPE
, "not a file");
806 grub_dl_unref (my_mod
);
811 grub_memcpy (data
->extents
, frec
.extents
, sizeof (grub_hfs_datarecord_t
));
812 file
->size
= grub_be_to_cpu32 (frec
.size
);
813 data
->size
= grub_be_to_cpu32 (frec
.size
);
814 data
->fileid
= grub_be_to_cpu32 (frec
.fileid
);
823 grub_hfs_read (grub_file_t file
, char *buf
, grub_size_t len
)
825 struct grub_hfs_data
*data
=
826 (struct grub_hfs_data
*) file
->data
;
828 return grub_hfs_read_file (data
, file
->read_hook
, file
->offset
, len
, buf
);
833 grub_hfs_close (grub_file_t file
)
835 grub_free (file
->data
);
838 grub_dl_unref (my_mod
);
846 grub_hfs_label (grub_device_t device
, char **label
)
848 struct grub_hfs_data
*data
;
850 data
= grub_hfs_mount (device
->disk
);
853 *label
= grub_strndup ((char *) (data
->sblock
.volname
+ 1),
854 *data
->sblock
.volname
);
864 static struct grub_fs grub_hfs_fs
=
868 .open
= grub_hfs_open
,
869 .read
= grub_hfs_read
,
870 .close
= grub_hfs_close
,
871 .label
= grub_hfs_label
,
877 grub_fs_register (&grub_hfs_fs
);
885 grub_fs_unregister (&grub_hfs_fs
);