~darkmuggle-deactivatedaccount/ubuntu/quantal/grub2/fix-872244

« back to all changes in this revision

Viewing changes to fs/hfsplus.c

  • Committer: Bazaar Package Importer
  • Author(s): Otavio Salvador
  • Date: 2006-01-05 15:20:40 UTC
  • mto: (17.3.1 squeeze) (1.9.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 4.
  • Revision ID: james.westby@ubuntu.com-20060105152040-b72i5pq1a82z22yi
Tags: upstream-1.92
ImportĀ upstreamĀ versionĀ 1.92

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
/* hfsplus.c - HFS+ Filesystem.  */
 
2
/*
 
3
 *  GRUB  --  GRand Unified Bootloader
 
4
 *  Copyright (C) 2005  Free Software Foundation, Inc.
 
5
 *
 
6
 *  This program 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 2 of the License, or
 
9
 *  (at your option) any later version.
 
10
 *
 
11
 *  This program 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 this program; if not, write to the Free Software
 
18
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
19
 */
 
20
 
 
21
#include <grub/err.h>
 
22
#include <grub/file.h>
 
23
#include <grub/mm.h>
 
24
#include <grub/misc.h>
 
25
#include <grub/disk.h>
 
26
#include <grub/dl.h>
 
27
#include <grub/types.h>
 
28
#include <grub/fshelp.h>
 
29
 
 
30
/* A HFS+ extent.  */
 
31
struct grub_hfsplus_extent
 
32
{
 
33
  /* The first block of a file on disk.  */
 
34
  grub_uint32_t start;
 
35
  /* The amount of blocks described by this extent.  */
 
36
  grub_uint32_t count;
 
37
} __attribute__ ((packed));
 
38
 
 
39
/* The descriptor of a fork.  */
 
40
struct grub_hfsplus_forkdata
 
41
{
 
42
  grub_uint64_t size;
 
43
  grub_uint32_t clumpsize;
 
44
  grub_uint32_t blocks;
 
45
  struct grub_hfsplus_extent extents[8];
 
46
} __attribute__ ((packed));
 
47
 
 
48
/* The HFS+ Volume Header.  */
 
49
struct grub_hfsplus_volheader
 
50
{
 
51
  grub_uint8_t magic[2];
 
52
  grub_uint16_t version;
 
53
  grub_uint32_t attributes;
 
54
  grub_uint8_t unused[32];
 
55
  grub_uint32_t blksize;
 
56
  grub_uint8_t unused2[68];
 
57
  struct grub_hfsplus_forkdata allocations_file;
 
58
  struct grub_hfsplus_forkdata extents_file;
 
59
  struct grub_hfsplus_forkdata catalog_file;
 
60
  struct grub_hfsplus_forkdata attrib_file;
 
61
  struct grub_hfsplus_forkdata startup_file;
 
62
} __attribute__ ((packed));
 
63
 
 
64
/* The type of node.  */
 
65
enum grub_hfsplus_btnode_type
 
66
  {
 
67
    GRUB_HFSPLUS_BTNODE_TYPE_LEAF = -1,
 
68
    GRUB_HFSPLUS_BTNODE_TYPE_INDEX = 0,
 
69
    GRUB_HFSPLUS_BTNODE_TYPE_HEADER = 1,
 
70
    GRUB_HFSPLUS_BTNODE_TYPE_MAP = 2,
 
71
  };
 
72
 
 
73
struct grub_hfsplus_btnode
 
74
{
 
75
  grub_uint32_t next;
 
76
  grub_uint32_t prev;
 
77
  grub_int8_t type;
 
78
  grub_uint8_t height;
 
79
  grub_uint16_t count;
 
80
  grub_uint16_t unused;
 
81
} __attribute__ ((packed));
 
82
 
 
83
/* The header of a HFS+ B+ Tree.  */
 
84
struct grub_hfsplus_btheader
 
85
{
 
86
  grub_uint16_t depth;
 
87
  grub_uint32_t root;
 
88
  grub_uint32_t leaf_records;
 
89
  grub_uint32_t first_leaf_node;
 
90
  grub_uint32_t last_leaf_node;
 
91
  grub_uint16_t nodesize;
 
92
  grub_uint16_t keysize;
 
93
} __attribute__ ((packed));
 
94
 
 
95
/* The on disk layout of a catalog key.  */
 
96
struct grub_hfsplus_catkey
 
97
{
 
98
  grub_uint16_t keylen;
 
99
  grub_uint32_t parent;
 
100
  grub_uint16_t namelen;
 
101
  grub_uint16_t name[30];
 
102
} __attribute__ ((packed));
 
103
 
 
104
/* The on disk layout of an extent overflow file key.  */
 
105
struct grub_hfsplus_extkey
 
106
{
 
107
  grub_uint16_t keylen;
 
108
  grub_uint8_t type;
 
109
  grub_uint8_t unused;
 
110
  grub_uint32_t fileid;
 
111
  grub_uint32_t start;
 
112
} __attribute__ ((packed));
 
113
 
 
114
struct grub_hfsplus_key
 
115
{
 
116
  union
 
117
  {
 
118
    struct grub_hfsplus_extkey extkey;
 
119
    struct grub_hfsplus_catkey catkey;
 
120
    grub_uint16_t keylen;
 
121
  };
 
122
} __attribute__ ((packed));
 
123
 
 
124
struct grub_hfsplus_catfile
 
125
{
 
126
  grub_uint16_t type;
 
127
  grub_uint16_t flags;
 
128
  grub_uint32_t reserved;
 
129
  grub_uint32_t fileid;
 
130
  grub_uint8_t unused1[30];
 
131
  grub_uint16_t mode;
 
132
  grub_uint8_t unused2[44];
 
133
  struct grub_hfsplus_forkdata data;
 
134
  struct grub_hfsplus_forkdata resource;
 
135
} __attribute__ ((packed));
 
136
 
 
137
/* Filetype information as used in inodes.  */
 
138
#define GRUB_HFSPLUS_FILEMODE_MASK      0170000
 
139
#define GRUB_HFSPLUS_FILEMODE_REG       0100000
 
140
#define GRUB_HFSPLUS_FILEMODE_DIRECTORY 0040000
 
141
#define GRUB_HFSPLUS_FILEMODE_SYMLINK   0120000
 
142
 
 
143
/* Some pre-defined file IDs.  */
 
144
#define GRUB_HFSPLUS_FILEID_ROOTDIR     2
 
145
#define GRUB_HFSPLUS_FILEID_OVERFLOW    3
 
146
#define GRUB_HFSPLUS_FILEID_CATALOG     4
 
147
 
 
148
enum grub_hfsplus_filetype
 
149
  {
 
150
    GRUB_HFSPLUS_FILETYPE_DIR = 1,
 
151
    GRUB_HFSPLUS_FILETYPE_REG = 2,
 
152
    GRUB_HFSPLUS_FILETYPE_DIR_THREAD = 3,
 
153
    GRUB_HFSPLUS_FILETYPE_REG_THREAD = 4
 
154
  };
 
155
 
 
156
/* Internal representation of a catalog key.  */
 
157
struct grub_hfsplus_catkey_internal
 
158
{
 
159
  int parent;
 
160
  char *name;
 
161
};
 
162
 
 
163
/* Internal representation of an extent overflow key.  */
 
164
struct grub_hfsplus_extkey_internal
 
165
{
 
166
  grub_uint32_t fileid;
 
167
  grub_uint32_t start;
 
168
};
 
169
 
 
170
struct grub_hfsplus_key_internal
 
171
{
 
172
  union
 
173
  {
 
174
    struct grub_hfsplus_extkey_internal extkey;
 
175
    struct grub_hfsplus_catkey_internal catkey;
 
176
  };
 
177
};
 
178
 
 
179
 
 
180
 
 
181
struct grub_fshelp_node
 
182
{
 
183
  struct grub_hfsplus_data *data;
 
184
  struct grub_hfsplus_extent extents[8];
 
185
  grub_uint64_t size;
 
186
  grub_uint32_t fileid;
 
187
};
 
188
 
 
189
struct grub_hfsplus_btree
 
190
{
 
191
  grub_uint32_t root;
 
192
  int nodesize;
 
193
 
 
194
  /* Catalog file node.  */
 
195
  struct grub_fshelp_node file;
 
196
};
 
197
 
 
198
/* Information about a "mounted" HFS+ filesystem.  */
 
199
struct grub_hfsplus_data
 
200
{
 
201
  struct grub_hfsplus_volheader volheader;
 
202
  grub_disk_t disk;
 
203
 
 
204
  unsigned int log2blksize;
 
205
 
 
206
  struct grub_hfsplus_btree catalog_tree;
 
207
  struct grub_hfsplus_btree extoverflow_tree;
 
208
 
 
209
  struct grub_fshelp_node dirroot;
 
210
  struct grub_fshelp_node opened_file;
 
211
};
 
212
 
 
213
#ifndef GRUB_UTIL
 
214
static grub_dl_t my_mod;
 
215
#endif
 
216
 
 
217
 
 
218
/* Find the extent that points to FILEBLOCK.  If it is not in one of
 
219
   the 8 extents described by EXTENT, return -1.  In that case set
 
220
   RETRY to the last block that was found in the last extent.  */
 
221
static int
 
222
grub_hfsplus_find_block (struct grub_hfsplus_extent *extent,
 
223
                         int fileblock, int *retry)
 
224
{
 
225
  int i;
 
226
  grub_size_t blksleft = fileblock;
 
227
 
 
228
  /* First lookup the file in the given extents.  */
 
229
  for (i = 0; i < 8; i++)
 
230
    {
 
231
      if (blksleft < grub_be_to_cpu32 (extent[i].count))
 
232
        return grub_be_to_cpu32 (extent[i].start) + blksleft;
 
233
      blksleft -= grub_be_to_cpu32 (extent[i].count);
 
234
    }
 
235
 
 
236
  *retry = fileblock - blksleft;
 
237
  return -1;
 
238
}
 
239
 
 
240
static grub_err_t
 
241
grub_hfsplus_btree_search (struct grub_hfsplus_btree *btree,
 
242
                           struct grub_hfsplus_key_internal *key,
 
243
                           int (*compare_keys) (struct grub_hfsplus_key *keya,
 
244
                                                struct grub_hfsplus_key_internal *keyb),
 
245
                           struct grub_hfsplus_btnode **matchnode, int *keyoffset);
 
246
 
 
247
static int grub_hfsplus_cmp_extkey (struct grub_hfsplus_key *keya,
 
248
                                    struct grub_hfsplus_key_internal *keyb);
 
249
 
 
250
/* Search for the block FILEBLOCK inside the file NODE.  Return the
 
251
   blocknumber of this block on disk.  */
 
252
static int
 
253
grub_hfsplus_read_block (grub_fshelp_node_t node, int fileblock)
 
254
{
 
255
  struct grub_hfsplus_extkey_internal extoverflow;
 
256
  struct grub_hfsplus_extkey *keyfound;
 
257
  int blk;
 
258
  struct grub_hfsplus_btnode *nnode = 0;
 
259
  int ptr;
 
260
  int retry = 0;
 
261
 
 
262
  struct grub_hfsplus_extent *extents = &node->extents[0];
 
263
 
 
264
  while (1)
 
265
    {
 
266
      char *cnode;
 
267
 
 
268
      /* Try to find this block in the current set of extents.  */
 
269
      blk = grub_hfsplus_find_block (extents, fileblock, &retry);
 
270
      if (blk != -1)
 
271
        return blk;
 
272
 
 
273
      /* The previous iteration of this loop allocated memory.  The
 
274
         code above used this memory, it can be free'ed now.  */
 
275
      if (nnode)
 
276
        grub_free (nnode);
 
277
 
 
278
      /* For the extent overflow file, extra extents can't be found in
 
279
         the extent overflow file.  If this happens, you found a
 
280
         bug...  */
 
281
      if (node->fileid == GRUB_HFSPLUS_FILEID_OVERFLOW)
 
282
        return -1;
 
283
 
 
284
      /* Set up the key to look for in the extent overflow file.  */
 
285
      extoverflow.fileid = node->fileid;
 
286
      extoverflow.start = retry;
 
287
 
 
288
      if (grub_hfsplus_btree_search (&node->data->extoverflow_tree,
 
289
                                     (struct grub_hfsplus_key_internal *) &extoverflow,
 
290
                                     grub_hfsplus_cmp_extkey, &nnode, &ptr))
 
291
        return -1;
 
292
 
 
293
      cnode = (char *) nnode;
 
294
 
 
295
      /* The extent overflow file has a 8 extents right after the key.  */
 
296
      keyfound = (struct grub_hfsplus_extkey *) 
 
297
        &cnode[(int) cnode[node->data->extoverflow_tree.nodesize - ptr - 1]];
 
298
      extents = (struct grub_hfsplus_extent *) 
 
299
        ((char *) keyfound + sizeof (struct grub_hfsplus_extkey));
 
300
 
 
301
      /* The block wasn't found.  Perhaps the next iteration will find
 
302
         it.  The last block we found is stored in FILEBLOCK now.  */
 
303
      /* XXX: Multiple iterations for locating the right extent was
 
304
         not tested enough... */
 
305
      fileblock = retry;
 
306
    }
 
307
 
 
308
  if (nnode)
 
309
    grub_free (nnode);
 
310
 
 
311
  /* Too bad, you lose.  */
 
312
  return -1;
 
313
}
 
314
 
 
315
 
 
316
/* Read LEN bytes from the file described by DATA starting with byte
 
317
   POS.  Return the amount of read bytes in READ.  */
 
318
static grub_ssize_t
 
319
grub_hfsplus_read_file (grub_fshelp_node_t node,
 
320
                        void (*read_hook) (unsigned long sector,
 
321
                                           unsigned offset, unsigned length),
 
322
                        int pos, unsigned int len, char *buf)
 
323
{
 
324
  return grub_fshelp_read_file (node->data->disk, node, read_hook,
 
325
                                pos, len, buf, grub_hfsplus_read_block,
 
326
                                node->size,
 
327
                                node->data->log2blksize - GRUB_DISK_SECTOR_BITS);
 
328
}
 
329
 
 
330
static struct grub_hfsplus_data *
 
331
grub_hfsplus_mount (grub_disk_t disk)
 
332
{
 
333
  struct grub_hfsplus_data *data;
 
334
  struct grub_hfsplus_btheader header;
 
335
  struct grub_hfsplus_btnode node;
 
336
 
 
337
  data = grub_malloc (sizeof (*data));
 
338
  if (!data)
 
339
    return 0;
 
340
 
 
341
  data->disk = disk;
 
342
 
 
343
  /* Read the bootblock.  */
 
344
  grub_disk_read (disk, 2, 0, sizeof (struct grub_hfsplus_volheader),
 
345
                  (char *) &data->volheader);
 
346
  if (grub_errno)
 
347
    goto fail;
 
348
 
 
349
  /* Make sure this is an hfs+ filesystem.  XXX: Do we really support
 
350
     HFX?  */
 
351
  if (grub_strncmp (data->volheader.magic, "H+", 2)
 
352
      && grub_strncmp (data->volheader.magic, "HX", 2))
 
353
    {
 
354
      grub_error (GRUB_ERR_BAD_FS, "not a HFS+ filesystem");
 
355
      goto fail;
 
356
    }
 
357
 
 
358
  if (grub_fshelp_log2blksize (grub_be_to_cpu32 (data->volheader.blksize),
 
359
                               &data->log2blksize))
 
360
    goto fail;
 
361
 
 
362
  /* Make a new node for the catalog tree.  */
 
363
  data->catalog_tree.file.data = data;
 
364
  data->catalog_tree.file.fileid = GRUB_HFSPLUS_FILEID_CATALOG;
 
365
  grub_memcpy (&data->catalog_tree.file.extents,
 
366
               data->volheader.catalog_file.extents,
 
367
               sizeof data->volheader.catalog_file.extents);
 
368
  data->catalog_tree.file.size = 
 
369
    grub_be_to_cpu64 (data->volheader.catalog_file.size);
 
370
 
 
371
  /* Make a new node for the extent overflow file.  */
 
372
  data->extoverflow_tree.file.data = data;
 
373
  data->extoverflow_tree.file.fileid = GRUB_HFSPLUS_FILEID_OVERFLOW;
 
374
  grub_memcpy (&data->extoverflow_tree.file.extents,
 
375
               data->volheader.extents_file.extents,
 
376
               sizeof data->volheader.catalog_file.extents);
 
377
 
 
378
  data->extoverflow_tree.file.size = 
 
379
    grub_be_to_cpu64 (data->volheader.extents_file.size);
 
380
 
 
381
  /* Read the essential information about the trees.  */
 
382
  if (! grub_hfsplus_read_file (&data->catalog_tree.file, 0,
 
383
                                sizeof (struct grub_hfsplus_btnode),
 
384
                                sizeof (header), (char *) &header))
 
385
    goto fail;
 
386
 
 
387
  data->catalog_tree.root = grub_be_to_cpu32 (header.root);
 
388
  data->catalog_tree.nodesize = grub_be_to_cpu16 (header.nodesize);
 
389
 
 
390
  if (! grub_hfsplus_read_file (&data->extoverflow_tree.file, 0,
 
391
                                sizeof (struct grub_hfsplus_btnode),
 
392
                                sizeof (header), (char *) &header))
 
393
    goto fail;
 
394
 
 
395
  data->extoverflow_tree.root = grub_be_to_cpu32 (header.root);
 
396
 
 
397
  if (! grub_hfsplus_read_file (&data->extoverflow_tree.file, 0, 0,
 
398
                                sizeof (node), (char *) &node))
 
399
    goto fail;
 
400
 
 
401
  data->extoverflow_tree.root = grub_be_to_cpu32 (header.root);
 
402
  data->extoverflow_tree.nodesize = grub_be_to_cpu16 (header.nodesize);
 
403
 
 
404
  data->dirroot.data = data;
 
405
  data->dirroot.fileid = GRUB_HFSPLUS_FILEID_ROOTDIR;
 
406
 
 
407
  return data;
 
408
 
 
409
 fail:
 
410
  grub_free (data);
 
411
  return 0;
 
412
}
 
413
 
 
414
/* Compare the on disk catalog key KEYA with the catalog key we are
 
415
   looking for (KEYB).  */
 
416
static int
 
417
grub_hfsplus_cmp_catkey (struct grub_hfsplus_key *keya,
 
418
                         struct grub_hfsplus_key_internal *keyb)
 
419
{
 
420
  struct grub_hfsplus_catkey *catkey_a = &keya->catkey;
 
421
  struct grub_hfsplus_catkey_internal *catkey_b = &keyb->catkey;
 
422
  char *filename;
 
423
  int i;
 
424
  int diff;
 
425
  
 
426
  diff = grub_be_to_cpu32 (catkey_a->parent) - catkey_b->parent;
 
427
  if (diff)
 
428
    return diff; 
 
429
 
 
430
  /* Change the filename in keya so the endianess is correct.  */
 
431
  for (i = 0; i < grub_be_to_cpu16 (catkey_a->namelen); i++)
 
432
    catkey_a->name[i] = grub_be_to_cpu16 (catkey_a->name[i]);
 
433
 
 
434
  filename = grub_malloc (grub_be_to_cpu16 (catkey_a->namelen) + 1);
 
435
 
 
436
  if (! grub_utf16_to_utf8 (filename, catkey_a->name,
 
437
                            grub_be_to_cpu16 (catkey_a->namelen)))
 
438
    return -1; /* XXX: This error never occurs, but in case it happens
 
439
                  just skip this entry.  */
 
440
 
 
441
  diff = grub_strncmp (filename, catkey_b->name,
 
442
                       grub_be_to_cpu16 (catkey_a->namelen));
 
443
 
 
444
  grub_free (filename);
 
445
 
 
446
  /* The endianess was changed to host format, change it back to
 
447
     whatever it was.  */
 
448
  for (i = 0; i < grub_be_to_cpu16 (catkey_a->namelen); i++)
 
449
    catkey_a->name[i] = grub_cpu_to_be16 (catkey_a->name[i]);
 
450
  return diff;
 
451
}
 
452
 
 
453
/* Compare the on disk extent overflow key KEYA with the extent
 
454
   overflow key we are looking for (KEYB).  */
 
455
static int
 
456
grub_hfsplus_cmp_extkey (struct grub_hfsplus_key *keya,
 
457
                         struct grub_hfsplus_key_internal *keyb)
 
458
{
 
459
  struct grub_hfsplus_extkey *extkey_a = &keya->extkey;
 
460
  struct grub_hfsplus_extkey_internal *extkey_b = &keyb->extkey;
 
461
  int diff;
 
462
 
 
463
  diff = grub_be_to_cpu32 (extkey_a->fileid) - extkey_b->fileid;
 
464
 
 
465
  if (diff)
 
466
    return diff;
 
467
 
 
468
  diff = grub_be_to_cpu32 (extkey_a->start) - extkey_b->start;
 
469
  return diff;
 
470
}
 
471
 
 
472
/* Return the offset of the record with the index INDEX, in the node
 
473
   NODE which is part of the B+ tree BTREE.  */
 
474
static inline unsigned int
 
475
grub_hfsplus_btree_recoffset (struct grub_hfsplus_btree *btree,
 
476
                           struct grub_hfsplus_btnode *node, int index)
 
477
{
 
478
  char *cnode = (char *) node;
 
479
  grub_uint16_t *recptr;
 
480
  recptr = (grub_uint16_t *) (&cnode[btree->nodesize
 
481
                                     - index * sizeof (grub_uint16_t) - 2]);
 
482
  return grub_be_to_cpu16 (*recptr);
 
483
}
 
484
 
 
485
/* Return a pointer to the record with the index INDEX, in the node
 
486
   NODE which is part of the B+ tree BTREE.  */
 
487
static inline struct grub_hfsplus_key *
 
488
grub_hfsplus_btree_recptr (struct grub_hfsplus_btree *btree,
 
489
                           struct grub_hfsplus_btnode *node, int index)
 
490
{
 
491
  char *cnode = (char *) node;
 
492
  unsigned int offset;
 
493
  offset = grub_hfsplus_btree_recoffset (btree, node, index);
 
494
  return (struct grub_hfsplus_key *) &cnode[offset];
 
495
}
 
496
 
 
497
 
 
498
static char *
 
499
grub_hfsplus_read_symlink (grub_fshelp_node_t node)
 
500
{
 
501
  char *symlink;
 
502
  grub_ssize_t numread;
 
503
 
 
504
  symlink = grub_malloc (node->size + 1);
 
505
  if (!symlink)
 
506
    return 0;
 
507
 
 
508
  numread = grub_hfsplus_read_file (node, 0, 0, node->size, symlink);
 
509
  if (numread != (grub_ssize_t) node->size)
 
510
    {
 
511
      grub_free (symlink);
 
512
      return 0;
 
513
    }
 
514
  symlink[node->size] = '\0';
 
515
 
 
516
  return symlink;
 
517
}
 
518
 
 
519
int
 
520
grub_hfsplus_btree_iterate_node (struct grub_hfsplus_btree *btree,
 
521
                                 struct grub_hfsplus_btnode *first_node,
 
522
                                 int first_rec,
 
523
                                 int (*hook) (void *record))
 
524
{
 
525
  int rec;  
 
526
 
 
527
  for (;;)
 
528
    {
 
529
      char *cnode = (char *) first_node;
 
530
 
 
531
      /* Iterate over all records in this node.  */
 
532
      for (rec = first_rec; rec < grub_be_to_cpu16 (first_node->count); rec++)
 
533
        {
 
534
          if (hook (grub_hfsplus_btree_recptr (btree, first_node, rec)))
 
535
            return 1;
 
536
        }
 
537
 
 
538
      if (! first_node->next)
 
539
        break;
 
540
 
 
541
      if (! grub_hfsplus_read_file (&btree->file, 0,
 
542
                                    (grub_be_to_cpu32 (first_node->next)
 
543
                                     * btree->nodesize),
 
544
                                    btree->nodesize, cnode))
 
545
        return 1;
 
546
 
 
547
      /* Don't skip any record in the next iteration.  */
 
548
      first_rec = 0;
 
549
    }
 
550
 
 
551
  return 0;
 
552
}
 
553
 
 
554
/* Lookup the node described by KEY in the B+ Tree BTREE.  Compare
 
555
   keys using the function COMPARE_KEYS.  When a match is found,
 
556
   return the node in MATCHNODE and a pointer to the data in this node
 
557
   in KEYOFFSET.  MATCHNODE should be free'ed by the caller.  */
 
558
static grub_err_t
 
559
grub_hfsplus_btree_search (struct grub_hfsplus_btree *btree,
 
560
                           struct grub_hfsplus_key_internal *key,
 
561
                           int (*compare_keys) (struct grub_hfsplus_key *keya,
 
562
                                                struct grub_hfsplus_key_internal *keyb),
 
563
                           struct grub_hfsplus_btnode **matchnode, int *keyoffset)
 
564
{
 
565
  grub_uint64_t currnode;
 
566
  char *node;
 
567
  struct grub_hfsplus_btnode *nodedesc;
 
568
  int rec;
 
569
 
 
570
  node = grub_malloc (btree->nodesize);
 
571
  if (! node)
 
572
    return grub_errno;
 
573
 
 
574
  currnode = btree->root;
 
575
  while (1)
 
576
    {
 
577
      int match = 0;
 
578
 
 
579
      /* Read a node.  */
 
580
      if (! grub_hfsplus_read_file (&btree->file, 0,
 
581
                                    (long)currnode * (long)btree->nodesize,
 
582
                                    btree->nodesize, (char *) node))
 
583
        {
 
584
          grub_free (node);
 
585
          return grub_errno;
 
586
        }
 
587
 
 
588
      nodedesc = (struct grub_hfsplus_btnode *) node;
 
589
 
 
590
      /* Find the record in this tree.  */
 
591
      for (rec = 0; rec < grub_be_to_cpu16 (nodedesc->count); rec++)
 
592
        {
 
593
          struct grub_hfsplus_key *currkey;
 
594
          currkey = grub_hfsplus_btree_recptr (btree, nodedesc, rec);
 
595
          
 
596
          /* The action that has to be taken depend on the type of
 
597
             record.  */
 
598
          if (nodedesc->type == GRUB_HFSPLUS_BTNODE_TYPE_LEAF
 
599
              && compare_keys (currkey, key) == 0)
 
600
            {
 
601
              /* An exact match was found!  */
 
602
 
 
603
              *matchnode = nodedesc;
 
604
              *keyoffset = rec;
 
605
 
 
606
              return 0;
 
607
            }
 
608
          else if (nodedesc->type == GRUB_HFSPLUS_BTNODE_TYPE_INDEX)
 
609
            {
 
610
              grub_uint32_t *pointer;
 
611
 
 
612
              /* The place where the key could've been found didn't
 
613
                 contain the key.  This means that the previous match
 
614
                 is the one that should be followed.  */
 
615
              if (compare_keys (currkey, key) > 0)
 
616
                break;
 
617
 
 
618
              /* Mark the last key which is lower or equal to the key
 
619
                 that we are looking for.  The last match that is
 
620
                 found will be used to locate the child which can
 
621
                 contain the record.  */
 
622
              pointer = (grub_uint32_t *) ((char *) currkey
 
623
                                           + grub_be_to_cpu16 (currkey->keylen)
 
624
                                           + 2);
 
625
              currnode = grub_be_to_cpu32 (*pointer);
 
626
              match = 1;
 
627
            }
 
628
        }
 
629
 
 
630
      /* No match was found, no record with this key exists in the
 
631
         tree.  */
 
632
      if (! match)
 
633
        {
 
634
          *matchnode = 0;
 
635
          grub_free (node);
 
636
          return 0;
 
637
        }
 
638
    }
 
639
}
 
640
 
 
641
static int
 
642
grub_hfsplus_iterate_dir (grub_fshelp_node_t dir,
 
643
                          int NESTED_FUNC_ATTR
 
644
                          (*hook) (const char *filename,
 
645
                                   enum grub_fshelp_filetype filetype,
 
646
                                   grub_fshelp_node_t node))
 
647
{
 
648
  auto int list_nodes (void *record);
 
649
  int list_nodes (void *record)
 
650
    {
 
651
      struct grub_hfsplus_catkey *catkey;
 
652
      char *filename;
 
653
      int i;
 
654
      int ret = 0;
 
655
      struct grub_fshelp_node *node;
 
656
      struct grub_hfsplus_catfile *fileinfo;
 
657
      enum grub_fshelp_filetype type = GRUB_FSHELP_UNKNOWN;
 
658
 
 
659
      catkey = (struct grub_hfsplus_catkey *) record;
 
660
 
 
661
      fileinfo = (record + grub_be_to_cpu16 (catkey->keylen)
 
662
                  + 2 + grub_be_to_cpu16(catkey->keylen) % 2);
 
663
 
 
664
      /* Stop iterating when the last directory entry was found.  */
 
665
      if (grub_be_to_cpu32 (catkey->parent) != dir->fileid)
 
666
        return 0;
 
667
 
 
668
      filename = grub_malloc (grub_be_to_cpu16 (catkey->namelen) + 1);
 
669
      if (! filename)
 
670
        return 0;
 
671
 
 
672
      /* Make sure the byte order of the UTF16 string is correct.  */
 
673
      for (i = 0; i < grub_be_to_cpu16 (catkey->namelen); i++)
 
674
        catkey->name[i] = grub_be_to_cpu16 (catkey->name[i]);
 
675
 
 
676
      if (! grub_utf16_to_utf8 (filename, catkey->name,
 
677
                                grub_be_to_cpu16 (catkey->namelen)))
 
678
        {
 
679
          grub_free (filename);
 
680
          return 0;
 
681
        }
 
682
 
 
683
      filename[grub_be_to_cpu16 (catkey->namelen)] = '\0';
 
684
 
 
685
      /* Restore the byte order to what it was previously.  */
 
686
      for (i = 0; i < grub_be_to_cpu16 (catkey->namelen); i++)
 
687
        catkey->name[i] = grub_be_to_cpu16 (catkey->name[i]);
 
688
 
 
689
      /* Determine the type of the node that was found.  */
 
690
      if (grub_be_to_cpu16 (fileinfo->type) == GRUB_HFSPLUS_FILETYPE_REG)
 
691
        {
 
692
          int mode = (grub_be_to_cpu16 (fileinfo->mode)
 
693
                      & GRUB_HFSPLUS_FILEMODE_MASK);
 
694
 
 
695
          if (mode == GRUB_HFSPLUS_FILEMODE_REG)
 
696
            type = GRUB_FSHELP_REG;
 
697
          else if (mode == GRUB_HFSPLUS_FILEMODE_SYMLINK)
 
698
            type = GRUB_FSHELP_SYMLINK;
 
699
          else
 
700
            type = GRUB_FSHELP_UNKNOWN;
 
701
        }
 
702
      else if (grub_be_to_cpu16 (fileinfo->type) == GRUB_HFSPLUS_FILETYPE_DIR)
 
703
        type = GRUB_FSHELP_DIR;
 
704
 
 
705
      /* Only accept valid nodes.  */
 
706
      if (type && grub_strlen (filename) == grub_be_to_cpu16 (catkey->namelen))
 
707
        {
 
708
          /* A valid node was found; setup the node and call the
 
709
             callback function.  */
 
710
          node = grub_malloc (sizeof (*node));
 
711
          node->data = dir->data;
 
712
          
 
713
          grub_memcpy (node->extents, fileinfo->data.extents,
 
714
                       sizeof (*node->extents));
 
715
          node->size = grub_be_to_cpu64 (fileinfo->data.size);
 
716
          node->fileid = grub_be_to_cpu32 (fileinfo->fileid);
 
717
 
 
718
          ret = hook (filename, type, node);
 
719
        }
 
720
 
 
721
      grub_free (filename);
 
722
 
 
723
      return ret;
 
724
    }
 
725
 
 
726
  struct grub_hfsplus_key_internal intern;
 
727
  struct grub_hfsplus_btnode *node;
 
728
  int ptr;
 
729
  int ret;
 
730
 
 
731
  /* Create a key that points to the first entry in the directory.  */
 
732
  intern.catkey.parent = dir->fileid;
 
733
  intern.catkey.name = "";
 
734
 
 
735
  /* First lookup the first entry.  */
 
736
  if (grub_hfsplus_btree_search (&dir->data->catalog_tree, &intern,
 
737
                                 grub_hfsplus_cmp_catkey, &node, &ptr))
 
738
    return 0;
 
739
 
 
740
  /* Iterate over all entries in this directory.  */
 
741
  ret = grub_hfsplus_btree_iterate_node (&dir->data->catalog_tree, node, ptr,
 
742
                                         list_nodes);
 
743
 
 
744
  grub_free (node);
 
745
 
 
746
  return ret;
 
747
}
 
748
 
 
749
/* Open a file named NAME and initialize FILE.  */
 
750
static grub_err_t
 
751
grub_hfsplus_open (struct grub_file *file, const char *name)
 
752
{
 
753
  struct grub_hfsplus_data *data;
 
754
  struct grub_fshelp_node *fdiro = 0;
 
755
  
 
756
#ifndef GRUB_UTIL
 
757
  grub_dl_ref (my_mod);
 
758
#endif
 
759
  
 
760
  data = grub_hfsplus_mount (file->device->disk);
 
761
  if (!data)
 
762
    goto fail;
 
763
 
 
764
  grub_fshelp_find_file (name, &data->dirroot, &fdiro,
 
765
                         grub_hfsplus_iterate_dir,
 
766
                         grub_hfsplus_read_symlink, GRUB_FSHELP_REG);
 
767
  if (grub_errno)
 
768
    goto fail;
 
769
 
 
770
  file->size = fdiro->size;
 
771
  data->opened_file = *fdiro;
 
772
  grub_free (fdiro);
 
773
 
 
774
  file->data = data;
 
775
  file->offset = 0;
 
776
 
 
777
  return 0;
 
778
 
 
779
 fail:
 
780
  if (data && fdiro != &data->dirroot)
 
781
    grub_free (fdiro);
 
782
  grub_free (data);
 
783
  
 
784
#ifndef GRUB_UTIL
 
785
  grub_dl_unref (my_mod);
 
786
#endif
 
787
 
 
788
  return grub_errno;
 
789
}
 
790
 
 
791
 
 
792
static grub_err_t
 
793
grub_hfsplus_close (grub_file_t file)
 
794
{
 
795
  grub_free (file->data);
 
796
 
 
797
#ifndef GRUB_UTIL
 
798
  grub_dl_unref (my_mod);
 
799
#endif
 
800
 
 
801
  return GRUB_ERR_NONE;
 
802
}
 
803
 
 
804
 
 
805
/* Read LEN bytes data from FILE into BUF.  */
 
806
static grub_ssize_t
 
807
grub_hfsplus_read (grub_file_t file, char *buf, grub_ssize_t len)
 
808
{
 
809
  struct grub_hfsplus_data *data = 
 
810
    (struct grub_hfsplus_data *) file->data;
 
811
 
 
812
  int size = grub_hfsplus_read_file (&data->opened_file, file->read_hook,
 
813
                                     file->offset, len, buf);
 
814
 
 
815
  return size;
 
816
}
 
817
 
 
818
 
 
819
static grub_err_t
 
820
grub_hfsplus_dir (grub_device_t device, const char *path, 
 
821
                  int (*hook) (const char *filename, int dir))
 
822
{
 
823
  struct grub_hfsplus_data *data = 0;
 
824
  struct grub_fshelp_node *fdiro = 0;
 
825
  
 
826
  auto int NESTED_FUNC_ATTR iterate (const char *filename,
 
827
                                     enum grub_fshelp_filetype filetype,
 
828
                                     grub_fshelp_node_t node);
 
829
 
 
830
  int NESTED_FUNC_ATTR iterate (const char *filename,
 
831
                                enum grub_fshelp_filetype filetype,
 
832
                                grub_fshelp_node_t node)
 
833
    {
 
834
      grub_free (node);
 
835
      
 
836
      if (filetype == GRUB_FSHELP_DIR)
 
837
        return hook (filename, 1);
 
838
      else 
 
839
        return hook (filename, 0);
 
840
      
 
841
      return 0;
 
842
    }
 
843
 
 
844
#ifndef GRUB_UTIL
 
845
  grub_dl_ref (my_mod);
 
846
#endif
 
847
  
 
848
  data = grub_hfsplus_mount (device->disk);
 
849
  if (!data)
 
850
    goto fail;
 
851
 
 
852
  /* Find the directory that should be opened.  */
 
853
  grub_fshelp_find_file (path, &data->dirroot, &fdiro,
 
854
                         grub_hfsplus_iterate_dir,
 
855
                         grub_hfsplus_read_symlink, GRUB_FSHELP_DIR);
 
856
  if (grub_errno)
 
857
    goto fail;
 
858
 
 
859
  /* Iterate over all entries in this directory.  */
 
860
  grub_hfsplus_iterate_dir (fdiro, iterate);
 
861
  
 
862
 fail:
 
863
  if (data && fdiro != &data->dirroot)
 
864
    grub_free (fdiro);
 
865
  grub_free (data);
 
866
 
 
867
#ifndef GRUB_UTIL
 
868
  grub_dl_unref (my_mod);
 
869
#endif
 
870
 
 
871
  return grub_errno;
 
872
}
 
873
 
 
874
 
 
875
static grub_err_t
 
876
grub_hfsplus_label (grub_device_t device __attribute__((unused))
 
877
                    , char **label __attribute__((unused)))
 
878
{
 
879
  /* XXX: It's not documented how to read a label.  */
 
880
  return grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
 
881
                     "reading the label of a HFS+ "
 
882
                     "partiton is not implemented");
 
883
}
 
884
 
 
885
 
 
886
static struct grub_fs grub_hfsplus_fs =
 
887
  {
 
888
    .name = "hfsplus",
 
889
    .dir = grub_hfsplus_dir,
 
890
    .open = grub_hfsplus_open,
 
891
    .read = grub_hfsplus_read,
 
892
    .close = grub_hfsplus_close,
 
893
    .label = grub_hfsplus_label,
 
894
    .next = 0
 
895
  };
 
896
 
 
897
GRUB_MOD_INIT(hfsplus)
 
898
{
 
899
  grub_fs_register (&grub_hfsplus_fs);
 
900
#ifndef GRUB_UTIL
 
901
  my_mod = mod;
 
902
#endif
 
903
}
 
904
 
 
905
GRUB_MOD_FINI(hfsplus)
 
906
{
 
907
  grub_fs_unregister (&grub_hfsplus_fs);
 
908
}