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 /* A node descriptor. This is the header of every node. */
55 } __attribute__ ((packed
));
57 /* The head of the B*-Tree. */
58 struct grub_hfs_treeheader
60 grub_uint16_t tree_depth
;
61 /* The number of the first node. */
62 grub_uint32_t root_node
;
64 grub_uint32_t first_leaf
;
65 grub_uint32_t last_leaf
;
66 grub_uint16_t node_size
;
67 grub_uint16_t key_size
;
69 grub_uint32_t free_nodes
;
70 grub_uint8_t unused
[76];
71 } __attribute__ ((packed
));
73 /* The state of a mounted HFS filesystem. */
76 struct grub_hfs_sblock sblock
;
78 grub_hfs_datarecord_t extents
;
90 /* The key as used on disk in a catalog tree. This is used to lookup
91 file/directory nodes by parent directory ID and filename. */
92 struct grub_hfs_catalog_key
95 grub_uint32_t parent_dir
;
97 /* Filename length. */
101 grub_uint8_t str
[31];
102 } __attribute__ ((packed
));
104 /* The key as used on disk in a extent overflow tree. Using this key
105 the extents can be looked up using a fileid and logical start block
107 struct grub_hfs_extent_key
109 /* The kind of fork. This is used to store meta information like
110 icons, attributes, etc. We will only use the datafork, which is
112 grub_uint8_t forktype
;
113 grub_uint32_t fileid
;
114 grub_uint16_t first_block
;
115 } __attribute__ ((packed
));
117 /* A dirrect record. This is used to find out the directory ID. */
118 struct grub_hfs_dirrec
120 /* For a directory, type == 1. */
122 grub_uint8_t unused
[5];
124 } __attribute__ ((packed
));
126 /* Information about a file. */
127 struct grub_hfs_filerec
129 /* For a file, type == 2. */
131 grub_uint8_t unused
[19];
132 grub_uint32_t fileid
;
133 grub_uint8_t unused2
[2];
135 grub_uint8_t unused3
[44];
137 /* The first 3 extents of the file. The other extents can be found
138 in the extent overflow file. */
139 grub_hfs_datarecord_t extents
;
140 } __attribute__ ((packed
));
142 /* A record descriptor, both key and data, used to pass to call back
144 struct grub_hfs_record
153 static grub_dl_t my_mod
;
156 static int grub_hfs_find_node (struct grub_hfs_data
*, char *,
157 grub_uint32_t
, int, char *, int);
159 /* Find block BLOCK of the file FILE in the mounted UFS filesystem
160 DATA. The first 3 extents are described by DAT. If cache is set,
161 using caching to improve non-random reads. */
163 grub_hfs_block (struct grub_hfs_data
*data
, grub_hfs_datarecord_t dat
,
164 int file
, int block
, int cache
)
166 grub_hfs_datarecord_t dr
;
168 struct grub_hfs_extent_key key
;
171 static int cache_file
= 0;
172 static int cache_pos
= 0;
173 static grub_hfs_datarecord_t cache_dr
;
175 grub_memcpy (dr
, dat
, sizeof (dr
));
178 key
.fileid
= grub_cpu_to_be32 (file
);
180 if (cache
&& cache_file
== file
&& block
> cache_pos
)
183 key
.first_block
= grub_cpu_to_be16 (pos
);
184 grub_memcpy (dr
, cache_dr
, sizeof (cache_dr
));
191 /* Try all 3 extents. */
192 for (i
= 0; i
< 3; i
++)
194 /* Check if the block is stored in this extent. */
195 if (grub_be_to_cpu16 (dr
[i
].count
) + pos
> block
)
197 int first
= grub_be_to_cpu16 (dr
[i
].first_block
);
199 /* If the cache is enabled, store the current position
205 grub_memcpy (cache_dr
, dr
, sizeof (cache_dr
));
208 return (grub_be_to_cpu16 (data
->sblock
.first_block
)
209 + (first
+ block
- pos
) * GRUB_HFS_BLKS
);
212 /* Try the next extent. */
213 pos
+= grub_be_to_cpu16 (dr
[i
].count
);
216 /* Lookup the block in the extent overflow file. */
217 key
.first_block
= grub_cpu_to_be16 (pos
);
219 grub_hfs_find_node (data
, (char *) &key
, data
->ext_root
,
220 1, (char *) &dr
, sizeof (dr
));
227 /* Read LEN bytes from the file described by DATA starting with byte
228 POS. Return the amount of read bytes in READ. */
230 grub_hfs_read_file (struct grub_hfs_data
*data
,
231 void NESTED_FUNC_ATTR (*read_hook
) (grub_disk_addr_t sector
,
232 unsigned offset
, unsigned length
),
233 int pos
, grub_size_t len
, char *buf
)
238 /* Adjust len so it we can't read past the end of the file. */
239 if (len
> grub_le_to_cpu32 (data
->size
))
240 len
= grub_le_to_cpu32 (data
->size
);
242 blockcnt
= ((len
+ pos
)
243 + data
->blksz
- 1) / data
->blksz
;
245 for (i
= pos
/ data
->blksz
; i
< blockcnt
; i
++)
248 int blockoff
= pos
% data
->blksz
;
249 int blockend
= data
->blksz
;
253 blknr
= grub_hfs_block (data
, data
->extents
, data
->fileid
, i
, 1);
258 if (i
== blockcnt
- 1)
260 blockend
= (len
+ pos
) % data
->blksz
;
262 /* The last portion is exactly EXT2_BLOCK_SIZE (data). */
264 blockend
= data
->blksz
;
268 if (i
== pos
/ data
->blksz
)
270 skipfirst
= blockoff
;
271 blockend
-= skipfirst
;
274 /* If the block number is 0 this block is not stored on disk but
275 is zero filled instead. */
278 data
->disk
->read_hook
= read_hook
;
279 grub_disk_read (data
->disk
, blknr
, skipfirst
,
281 data
->disk
->read_hook
= 0;
286 buf
+= data
->blksz
- skipfirst
;
293 /* Mount the filesystem on the disk DISK. */
294 static struct grub_hfs_data
*
295 grub_hfs_mount (grub_disk_t disk
)
297 struct grub_hfs_data
*data
;
298 struct grub_hfs_catalog_key key
;
299 struct grub_hfs_dirrec dir
;
304 struct grub_hfs_node node
;
305 struct grub_hfs_treeheader head
;
308 data
= grub_malloc (sizeof (struct grub_hfs_data
));
312 /* Read the superblock. */
313 if (grub_disk_read (disk
, GRUB_HFS_SBLOCK
, 0,
314 sizeof (struct grub_hfs_sblock
), (char *) &data
->sblock
))
317 /* Check if this is a HFS filesystem. */
318 if (grub_be_to_cpu16 (data
->sblock
.magic
) != GRUB_HFS_MAGIC
)
320 grub_error (GRUB_ERR_BAD_FS
, "not an HFS filesystem");
324 /* Check if this is an embedded HFS+ filesystem. */
325 if (grub_be_to_cpu16 (data
->sblock
.embed_sig
) == GRUB_HFS_EMBED_HFSPLUS_SIG
)
327 grub_error (GRUB_ERR_BAD_FS
, "embedded HFS+ filesystem");
331 data
->blksz
= grub_be_to_cpu32 (data
->sblock
.blksz
);
334 /* Lookup the root node of the extent overflow tree. */
335 first_block
= ((grub_be_to_cpu16 (data
->sblock
.extent_recs
[0].first_block
)
337 + grub_be_to_cpu16 (data
->sblock
.first_block
));
339 if (grub_disk_read (data
->disk
, first_block
, 0,
340 sizeof (treehead
), (char *) &treehead
))
342 data
->ext_root
= grub_be_to_cpu32 (treehead
.head
.root_node
);
343 data
->ext_size
= grub_be_to_cpu16 (treehead
.head
.node_size
);
345 /* Lookup the root node of the catalog tree. */
346 first_block
= ((grub_be_to_cpu16 (data
->sblock
.catalog_recs
[0].first_block
)
348 + 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
->cat_root
= grub_be_to_cpu32 (treehead
.head
.root_node
);
353 data
->cat_size
= grub_be_to_cpu16 (treehead
.head
.node_size
);
355 /* Lookup the root directory node in the catalog tree using the
357 key
.parent_dir
= grub_cpu_to_be32 (1);
358 key
.strlen
= data
->sblock
.volname
[0];
359 grub_strcpy ((char *) key
.str
, (char *) (data
->sblock
.volname
+ 1));
361 if (grub_hfs_find_node (data
, (char *) &key
, data
->cat_root
,
362 0, (char *) &dir
, sizeof (dir
)) == 0)
364 grub_error (GRUB_ERR_BAD_FS
, "can not find the hfs root directory");
371 data
->rootdir
= grub_be_to_cpu32 (dir
.dirid
);
377 if (grub_errno
== GRUB_ERR_OUT_OF_RANGE
)
378 grub_error (GRUB_ERR_BAD_FS
, "not a hfs filesystem");
384 /* Compare the K1 and K2 catalog file keys. */
386 grub_hfs_cmp_catkeys (struct grub_hfs_catalog_key
*k1
,
387 struct grub_hfs_catalog_key
*k2
)
389 int cmp
= (grub_be_to_cpu32 (k1
->parent_dir
)
390 - grub_be_to_cpu32 (k2
->parent_dir
));
395 cmp
= grub_strncasecmp ((char *) (k1
->str
), (char *) (k2
->str
), k1
->strlen
);
397 /* This is required because the compared strings are not of equal
399 if (cmp
== 0 && k1
->strlen
< k2
->strlen
)
405 /* Compare the K1 and K2 extent overflow file keys. */
407 grub_hfs_cmp_extkeys (struct grub_hfs_extent_key
*k1
,
408 struct grub_hfs_extent_key
*k2
)
410 int cmp
= k1
->forktype
- k2
->forktype
;
412 cmp
= grub_be_to_cpu32 (k1
->fileid
) - grub_be_to_cpu32 (k2
->fileid
);
414 cmp
= (grub_be_to_cpu16 (k1
->first_block
)
415 - grub_be_to_cpu16 (k2
->first_block
));
420 /* Iterate the records in the node with index IDX in the mounted HFS
421 filesystem DATA. This node holds data of the type TYPE (0 =
422 catalog node, 1 = extent overflow node). If this is set, continue
423 iterating to the next node. For every records, call NODE_HOOK. */
425 grub_hfs_iterate_records (struct grub_hfs_data
*data
, int type
, int idx
,
426 int this, int (*node_hook
) (struct grub_hfs_node
*hnd
,
427 struct grub_hfs_record
*))
429 int nodesize
= type
== 0 ? data
->cat_size
: data
->ext_size
;
433 struct grub_hfs_node node
;
434 char rawnode
[nodesize
];
435 grub_uint16_t offsets
[nodesize
/ 2];
441 struct grub_hfs_extent
*dat
;
444 dat
= (struct grub_hfs_extent
*) (type
== 0
445 ? (&data
->sblock
.catalog_recs
)
446 : (&data
->sblock
.extent_recs
));
448 /* Read the node into memory. */
449 blk
= grub_hfs_block (data
, dat
,
450 0, idx
/ (data
->blksz
/ nodesize
), 0);
451 blk
+= (idx
% (data
->blksz
/ nodesize
));
455 if (grub_disk_read (data
->disk
, blk
, 0,
456 sizeof (node
), (char *) &node
))
459 /* Iterate over all records in this node. */
460 for (i
= 0; i
< grub_be_to_cpu16 (node
.node
.reccnt
); i
++)
462 int pos
= (nodesize
>> 1) - 1 - i
;
467 } __attribute__ ((packed
)) *pnt
;
468 pnt
= (struct pointer
*) (grub_be_to_cpu16 (node
.offsets
[pos
])
471 struct grub_hfs_record rec
=
475 &pnt
->key
+ pnt
->keylen
+(pnt
->keylen
+ 1) % 2,
476 nodesize
- grub_be_to_cpu16 (node
.offsets
[pos
])
480 if (node_hook (&node
.node
, &rec
))
484 if (idx
% (data
->blksz
/ nodesize
) == 0)
485 idx
= grub_be_to_cpu32 (node
.node
.next
);
488 } while (idx
&& this);
494 /* Lookup a record in the mounted filesystem DATA using the key KEY.
495 The index of the node on top of the tree is IDX. The tree is of
496 the type TYPE (0 = catalog node, 1 = extent overflow node). Return
497 the data in DATAR with a maximum length of DATALEN. */
499 grub_hfs_find_node (struct grub_hfs_data
*data
, char *key
,
500 grub_uint32_t idx
, int type
, char *datar
, int datalen
)
505 auto int node_found (struct grub_hfs_node
*, struct grub_hfs_record
*);
507 int node_found (struct grub_hfs_node
*hnd
, struct grub_hfs_record
*rec
)
512 cmp
= grub_hfs_cmp_catkeys (rec
->key
, (void *) key
);
514 cmp
= grub_hfs_cmp_extkeys (rec
->key
, (void *) key
);
516 /* If the key is smaller or equal to the currect node, mark the
517 entry. In case of a non-leaf mode it will be used to lookup
518 the rest of the tree. */
521 grub_uint32_t
*node
= (grub_uint32_t
*) rec
->data
;
522 found
= grub_be_to_cpu32 (*node
);
524 else /* The key can not be found in the tree. */
527 /* Check if this node is a leaf node. */
528 if (hnd
->type
== GRUB_HFS_NODE_LEAF
)
535 grub_memcpy (datar
, rec
->data
,
536 rec
->datalen
< datalen
? rec
->datalen
: datalen
);
544 if (grub_hfs_iterate_records (data
, type
, idx
, 0, node_found
))
553 return grub_hfs_find_node (data
, key
, found
, type
, datar
, datalen
);
557 /* Iterate over the directory with the id DIR. The tree is searched
558 starting with the node ROOT_IDX. For every entry in this directory
561 grub_hfs_iterate_dir (struct grub_hfs_data
*data
, grub_uint32_t root_idx
,
562 unsigned int dir
, int (*hook
) (struct grub_hfs_record
*))
568 /* The lowest key possible with DIR as root directory. */
569 struct grub_hfs_catalog_key key
= {0, grub_cpu_to_be32 (dir
), 0, ""};
571 auto int node_found (struct grub_hfs_node
*, struct grub_hfs_record
*);
572 auto int it_dir (struct grub_hfs_node
* __attribute ((unused
)),
573 struct grub_hfs_record
*);
576 int node_found (struct grub_hfs_node
*hnd
, struct grub_hfs_record
*rec
)
578 struct grub_hfs_catalog_key
*ckey
= rec
->key
;
580 if (grub_hfs_cmp_catkeys (rec
->key
, (void *) &key
) <= 0)
581 found
= grub_be_to_cpu32 (*(grub_uint32_t
*) rec
->data
);
583 if (hnd
->type
== 0xFF && ckey
->strlen
> 0)
586 next
= grub_be_to_cpu32 (hnd
->next
);
588 /* An entry was found. */
589 if (grub_be_to_cpu32 (ckey
->parent_dir
) == dir
)
596 int it_dir (struct grub_hfs_node
*hnd
__attribute ((unused
)),
597 struct grub_hfs_record
*rec
)
599 struct grub_hfs_catalog_key
*ckey
= rec
->key
;
600 struct grub_hfs_catalog_key
*origkey
= &key
;
602 /* Stop when the entries do not match anymore. */
603 if (grub_be_to_cpu32 (ckey
->parent_dir
)
604 != grub_be_to_cpu32 ((origkey
)->parent_dir
))
610 if (grub_hfs_iterate_records (data
, 0, root_idx
, 0, node_found
))
616 /* If there was a matching record in this leaf node, continue the
617 iteration until the last record was found. */
620 grub_hfs_iterate_records (data
, 0, next
, 1, it_dir
);
624 return grub_hfs_iterate_dir (data
, found
, dir
, hook
);
628 /* Find a file or directory with the pathname PATH in the filesystem
629 DATA. Return the file record in RETDATA when it is non-zero.
630 Return the directory number in RETINODE when it is non-zero. */
632 grub_hfs_find_dir (struct grub_hfs_data
*data
, const char *path
,
633 struct grub_hfs_filerec
*retdata
, int *retinode
)
635 int inode
= data
->rootdir
;
638 struct grub_hfs_filerec frec
;
639 struct grub_hfs_dirrec
*dir
= (struct grub_hfs_dirrec
*) &frec
;
640 frec
.type
= GRUB_HFS_FILETYPE_DIR
;
644 grub_error (GRUB_ERR_BAD_FILENAME
, "bad filename");
648 origpath
= grub_strdup (path
);
655 while (path
&& grub_strlen (path
))
657 if (frec
.type
!= GRUB_HFS_FILETYPE_DIR
)
659 grub_error (GRUB_ERR_BAD_FILE_TYPE
, "not a directory");
663 /* Isolate a part of the path. */
664 next
= grub_strchr (path
, '/');
671 struct grub_hfs_catalog_key key
;
673 key
.parent_dir
= grub_cpu_to_be32 (inode
);
674 key
.strlen
= grub_strlen (path
);
675 grub_strcpy ((char *) (key
.str
), path
);
677 /* Lookup this node. */
678 if (! grub_hfs_find_node (data
, (char *) &key
, data
->cat_root
,
679 0, (char *) &frec
, sizeof (frec
)))
681 grub_error (GRUB_ERR_FILE_NOT_FOUND
, "file not found");
688 inode
= grub_be_to_cpu32 (dir
->dirid
);
693 grub_memcpy (retdata
, &frec
, sizeof (frec
));
699 grub_free (origpath
);
706 grub_hfs_dir (grub_device_t device
, const char *path
,
707 int (*hook
) (const char *filename
, int dir
))
711 auto int dir_hook (struct grub_hfs_record
*rec
);
713 int dir_hook (struct grub_hfs_record
*rec
)
715 char fname
[32] = { 0 };
716 char *filetype
= rec
->data
;
717 struct grub_hfs_catalog_key
*ckey
= rec
->key
;
719 grub_strncpy (fname
, (char *) (ckey
->str
), ckey
->strlen
);
721 if (*filetype
== GRUB_HFS_FILETYPE_DIR
)
722 return hook (fname
, 1);
723 else if (*filetype
== GRUB_HFS_FILETYPE_FILE
)
724 return hook (fname
, 0);
728 struct grub_hfs_data
*data
;
729 struct grub_hfs_filerec frec
;
732 grub_dl_ref (my_mod
);
735 data
= grub_hfs_mount (device
->disk
);
739 /* First the directory ID for the directory. */
740 if (grub_hfs_find_dir (data
, path
, &frec
, &inode
))
743 if (frec
.type
!= GRUB_HFS_FILETYPE_DIR
)
745 grub_error (GRUB_ERR_BAD_FILE_TYPE
, "not a directory");
749 grub_hfs_iterate_dir (data
, data
->cat_root
, inode
, dir_hook
);
755 grub_dl_unref (my_mod
);
762 /* Open a file named NAME and initialize FILE. */
764 grub_hfs_open (struct grub_file
*file
, const char *name
)
766 struct grub_hfs_data
*data
;
767 struct grub_hfs_filerec frec
;
770 grub_dl_ref (my_mod
);
773 data
= grub_hfs_mount (file
->device
->disk
);
775 if (grub_hfs_find_dir (data
, name
, &frec
, 0))
779 grub_dl_unref (my_mod
);
784 if (frec
.type
!= GRUB_HFS_FILETYPE_FILE
)
787 grub_error (GRUB_ERR_BAD_FILE_TYPE
, "not a file");
789 grub_dl_unref (my_mod
);
794 grub_memcpy (data
->extents
, frec
.extents
, sizeof (grub_hfs_datarecord_t
));
795 file
->size
= grub_be_to_cpu32 (frec
.size
);
796 data
->size
= grub_be_to_cpu32 (frec
.size
);
797 data
->fileid
= grub_be_to_cpu32 (frec
.fileid
);
806 grub_hfs_read (grub_file_t file
, char *buf
, grub_size_t len
)
808 struct grub_hfs_data
*data
=
809 (struct grub_hfs_data
*) file
->data
;
811 return grub_hfs_read_file (data
, file
->read_hook
, file
->offset
, len
, buf
);
816 grub_hfs_close (grub_file_t file
)
818 grub_free (file
->data
);
821 grub_dl_unref (my_mod
);
829 grub_hfs_label (grub_device_t device
, char **label
)
831 struct grub_hfs_data
*data
;
833 data
= grub_hfs_mount (device
->disk
);
836 *label
= grub_strndup ((char *) (data
->sblock
.volname
+ 1),
837 *data
->sblock
.volname
);
847 static struct grub_fs grub_hfs_fs
=
851 .open
= grub_hfs_open
,
852 .read
= grub_hfs_read
,
853 .close
= grub_hfs_close
,
854 .label
= grub_hfs_label
,
860 grub_fs_register (&grub_hfs_fs
);
868 grub_fs_unregister (&grub_hfs_fs
);