?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Upgraded GRUB2 to 2.00 release.
[AROS.git] / arch / all-pc / boot / grub2-aros / grub-core / fs / btrfs.c
bloba993f0747b0ce1472b5edd71c1a14f4b714530d4
1 /* btrfs.c - B-tree file system. */
2 /*
3 * GRUB -- GRand Unified Bootloader
4 * Copyright (C) 2010 Free Software Foundation, Inc.
5 *
6 * GRUB is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * GRUB is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with GRUB. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <grub/err.h>
21 #include <grub/file.h>
22 #include <grub/mm.h>
23 #include <grub/misc.h>
24 #include <grub/disk.h>
25 #include <grub/dl.h>
26 #include <grub/types.h>
27 #include <grub/lib/crc.h>
28 #include <grub/deflate.h>
29 #include <minilzo.h>
30 #include <grub/i18n.h>
31
32 GRUB_MOD_LICENSE ("GPLv3+");
33
34 #define GRUB_BTRFS_SIGNATURE "_BHRfS_M"
35
36 /* From http://www.oberhumer.com/opensource/lzo/lzofaq.php
37 * LZO will expand incompressible data by a little amount. I still haven't
38 * computed the exact values, but I suggest using these formulas for
39 * a worst-case expansion calculation:
40 *
41 * output_block_size = input_block_size + (input_block_size / 16) + 64 + 3
42 * */
43 #define GRUB_BTRFS_LZO_BLOCK_SIZE 4096
44 #define GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE (GRUB_BTRFS_LZO_BLOCK_SIZE + \
45 (GRUB_BTRFS_LZO_BLOCK_SIZE / 16) + 64 + 3)
46
47 typedef grub_uint8_t grub_btrfs_checksum_t[0x20];
48 typedef grub_uint16_t grub_btrfs_uuid_t[8];
49
50 struct grub_btrfs_device
51 {
52 grub_uint64_t device_id;
53 grub_uint64_t size;
54 grub_uint8_t dummy[0x62 - 0x10];
55 } __attribute__ ((packed));
56
57 struct grub_btrfs_superblock
58 {
59 grub_btrfs_checksum_t checksum;
60 grub_btrfs_uuid_t uuid;
61 grub_uint8_t dummy[0x10];
62 grub_uint8_t signature[sizeof (GRUB_BTRFS_SIGNATURE) - 1];
63 grub_uint64_t generation;
64 grub_uint64_t root_tree;
65 grub_uint64_t chunk_tree;
66 grub_uint8_t dummy2[0x20];
67 grub_uint64_t root_dir_objectid;
68 grub_uint8_t dummy3[0x41];
69 struct grub_btrfs_device this_device;
70 char label[0x100];
71 grub_uint8_t dummy4[0x100];
72 grub_uint8_t bootstrap_mapping[0x800];
73 } __attribute__ ((packed));
74
75 struct btrfs_header
76 {
77 grub_btrfs_checksum_t checksum;
78 grub_btrfs_uuid_t uuid;
79 grub_uint8_t dummy[0x30];
80 grub_uint32_t nitems;
81 grub_uint8_t level;
82 } __attribute__ ((packed));
83
84 struct grub_btrfs_device_desc
85 {
86 grub_device_t dev;
87 grub_uint64_t id;
88 };
89
90 struct grub_btrfs_data
91 {
92 struct grub_btrfs_superblock sblock;
93 grub_uint64_t tree;
94 grub_uint64_t inode;
95
96 struct grub_btrfs_device_desc *devices_attached;
97 unsigned n_devices_attached;
98 unsigned n_devices_allocated;
99
100 /* Cached extent data. */
101 grub_uint64_t extstart;
102 grub_uint64_t extend;
103 grub_uint64_t extino;
104 grub_uint64_t exttree;
105 grub_size_t extsize;
106 struct grub_btrfs_extent_data *extent;
107 };
108
109 enum
110 {
111 GRUB_BTRFS_ITEM_TYPE_INODE_ITEM = 0x01,
112 GRUB_BTRFS_ITEM_TYPE_INODE_REF = 0x0c,
113 GRUB_BTRFS_ITEM_TYPE_DIR_ITEM = 0x54,
114 GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM = 0x6c,
115 GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM = 0x84,
116 GRUB_BTRFS_ITEM_TYPE_DEVICE = 0xd8,
117 GRUB_BTRFS_ITEM_TYPE_CHUNK = 0xe4
118 };
119
120 struct grub_btrfs_key
121 {
122 grub_uint64_t object_id;
123 grub_uint8_t type;
124 grub_uint64_t offset;
125 } __attribute__ ((packed));
126
127 struct grub_btrfs_chunk_item
128 {
129 grub_uint64_t size;
130 grub_uint64_t dummy;
131 grub_uint64_t stripe_length;
132 grub_uint64_t type;
133 #define GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE 0x07
134 #define GRUB_BTRFS_CHUNK_TYPE_SINGLE 0x00
135 #define GRUB_BTRFS_CHUNK_TYPE_RAID0 0x08
136 #define GRUB_BTRFS_CHUNK_TYPE_RAID1 0x10
137 #define GRUB_BTRFS_CHUNK_TYPE_DUPLICATED 0x20
138 #define GRUB_BTRFS_CHUNK_TYPE_RAID10 0x40
139 grub_uint8_t dummy2[0xc];
140 grub_uint16_t nstripes;
141 grub_uint16_t nsubstripes;
142 } __attribute__ ((packed));
143
144 struct grub_btrfs_chunk_stripe
145 {
146 grub_uint64_t device_id;
147 grub_uint64_t offset;
148 grub_btrfs_uuid_t device_uuid;
149 } __attribute__ ((packed));
150
151 struct grub_btrfs_leaf_node
152 {
153 struct grub_btrfs_key key;
154 grub_uint32_t offset;
155 grub_uint32_t size;
156 } __attribute__ ((packed));
157
158 struct grub_btrfs_internal_node
159 {
160 struct grub_btrfs_key key;
161 grub_uint64_t addr;
162 grub_uint64_t dummy;
163 } __attribute__ ((packed));
164
165 struct grub_btrfs_dir_item
166 {
167 struct grub_btrfs_key key;
168 grub_uint8_t dummy[8];
169 grub_uint16_t m;
170 grub_uint16_t n;
171 #define GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR 1
172 #define GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY 2
173 #define GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK 7
174 grub_uint8_t type;
175 char name[0];
176 } __attribute__ ((packed));
177
178 struct grub_btrfs_leaf_descriptor
179 {
180 unsigned depth;
181 unsigned allocated;
182 struct
183 {
184 grub_disk_addr_t addr;
185 unsigned iter;
186 unsigned maxiter;
187 int leaf;
188 } *data;
189 };
190
191 struct grub_btrfs_root_item
192 {
193 grub_uint8_t dummy[0xb0];
194 grub_uint64_t tree;
195 grub_uint64_t inode;
196 };
197
198 struct grub_btrfs_time
199 {
200 grub_int64_t sec;
201 grub_uint32_t nanosec;
202 } __attribute__ ((aligned (4)));
203
204 struct grub_btrfs_inode
205 {
206 grub_uint8_t dummy1[0x10];
207 grub_uint64_t size;
208 grub_uint8_t dummy2[0x70];
209 struct grub_btrfs_time mtime;
210 } __attribute__ ((packed));
211
212 struct grub_btrfs_extent_data
213 {
214 grub_uint64_t dummy;
215 grub_uint64_t size;
216 grub_uint8_t compression;
217 grub_uint8_t encryption;
218 grub_uint16_t encoding;
219 grub_uint8_t type;
220 union
221 {
222 char inl[0];
223 struct
224 {
225 grub_uint64_t laddr;
226 grub_uint64_t compressed_size;
227 grub_uint64_t offset;
228 grub_uint64_t filled;
229 };
230 };
231 } __attribute__ ((packed));
232
233 #define GRUB_BTRFS_EXTENT_INLINE 0
234 #define GRUB_BTRFS_EXTENT_REGULAR 1
235
236 #define GRUB_BTRFS_COMPRESSION_NONE 0
237 #define GRUB_BTRFS_COMPRESSION_ZLIB 1
238 #define GRUB_BTRFS_COMPRESSION_LZO 2
239
240 #define GRUB_BTRFS_OBJECT_ID_CHUNK 0x100
241
242 static grub_disk_addr_t superblock_sectors[] = { 64 * 2, 64 * 1024 * 2,
243 256 * 1048576 * 2, 1048576ULL * 1048576ULL * 2
244 };
245
246 static grub_err_t
247 grub_btrfs_read_logical (struct grub_btrfs_data *data,
248 grub_disk_addr_t addr, void *buf, grub_size_t size,
249 int recursion_depth);
250
251 static grub_err_t
252 read_sblock (grub_disk_t disk, struct grub_btrfs_superblock *sb)
253 {
254 unsigned i;
255 grub_err_t err = GRUB_ERR_NONE;
256 for (i = 0; i < ARRAY_SIZE (superblock_sectors); i++)
257 {
258 struct grub_btrfs_superblock sblock;
259 /* Don't try additional superblocks beyond device size. */
260 if (i && (grub_le_to_cpu64 (sblock.this_device.size)
261 >> GRUB_DISK_SECTOR_BITS) <= superblock_sectors[i])
262 break;
263 err = grub_disk_read (disk, superblock_sectors[i], 0,
264 sizeof (sblock), &sblock);
265 if (err == GRUB_ERR_OUT_OF_RANGE)
266 break;
267
268 if (grub_memcmp ((char *) sblock.signature, GRUB_BTRFS_SIGNATURE,
269 sizeof (GRUB_BTRFS_SIGNATURE) - 1) != 0)
270 break;
271 if (i == 0 || grub_le_to_cpu64 (sblock.generation)
272 > grub_le_to_cpu64 (sb->generation))
273 grub_memcpy (sb, &sblock, sizeof (sblock));
274 }
275
276 if ((err == GRUB_ERR_OUT_OF_RANGE || !err) && i == 0)
277 return grub_error (GRUB_ERR_BAD_FS, "not a Btrfs filesystem");
278
279 if (err == GRUB_ERR_OUT_OF_RANGE)
280 grub_errno = err = GRUB_ERR_NONE;
281
282 return err;
283 }
284
285 static int
286 key_cmp (const struct grub_btrfs_key *a, const struct grub_btrfs_key *b)
287 {
288 if (grub_le_to_cpu64 (a->object_id) < grub_le_to_cpu64 (b->object_id))
289 return -1;
290 if (grub_le_to_cpu64 (a->object_id) > grub_le_to_cpu64 (b->object_id))
291 return +1;
292
293 if (a->type < b->type)
294 return -1;
295 if (a->type > b->type)
296 return +1;
297
298 if (grub_le_to_cpu64 (a->offset) < grub_le_to_cpu64 (b->offset))
299 return -1;
300 if (grub_le_to_cpu64 (a->offset) > grub_le_to_cpu64 (b->offset))
301 return +1;
302 return 0;
303 }
304
305 static void
306 free_iterator (struct grub_btrfs_leaf_descriptor *desc)
307 {
308 grub_free (desc->data);
309 }
310
311 static grub_err_t
312 save_ref (struct grub_btrfs_leaf_descriptor *desc,
313 grub_disk_addr_t addr, unsigned i, unsigned m, int l)
314 {
315 desc->depth++;
316 if (desc->allocated < desc->depth)
317 {
318 void *newdata;
319 desc->allocated *= 2;
320 newdata = grub_realloc (desc->data, sizeof (desc->data[0])
321 * desc->allocated);
322 if (!newdata)
323 return grub_errno;
324 desc->data = newdata;
325 }
326 desc->data[desc->depth - 1].addr = addr;
327 desc->data[desc->depth - 1].iter = i;
328 desc->data[desc->depth - 1].maxiter = m;
329 desc->data[desc->depth - 1].leaf = l;
330 return GRUB_ERR_NONE;
331 }
332
333 static int
334 next (struct grub_btrfs_data *data,
335 struct grub_btrfs_leaf_descriptor *desc,
336 grub_disk_addr_t * outaddr, grub_size_t * outsize,
337 struct grub_btrfs_key *key_out)
338 {
339 grub_err_t err;
340 struct grub_btrfs_leaf_node leaf;
341
342 for (; desc->depth > 0; desc->depth--)
343 {
344 desc->data[desc->depth - 1].iter++;
345 if (desc->data[desc->depth - 1].iter
346 < desc->data[desc->depth - 1].maxiter)
347 break;
348 }
349 if (desc->depth == 0)
350 return 0;
351 while (!desc->data[desc->depth - 1].leaf)
352 {
353 struct grub_btrfs_internal_node node;
354 struct btrfs_header head;
355
356 err = grub_btrfs_read_logical (data, desc->data[desc->depth - 1].iter
357 * sizeof (node)
358 + sizeof (struct btrfs_header)
359 + desc->data[desc->depth - 1].addr,
360 &node, sizeof (node), 0);
361 if (err)
362 return -err;
363
364 err = grub_btrfs_read_logical (data, grub_le_to_cpu64 (node.addr),
365 &head, sizeof (head), 0);
366 if (err)
367 return -err;
368
369 save_ref (desc, grub_le_to_cpu64 (node.addr), 0,
370 grub_le_to_cpu32 (head.nitems), !head.level);
371 }
372 err = grub_btrfs_read_logical (data, desc->data[desc->depth - 1].iter
373 * sizeof (leaf)
374 + sizeof (struct btrfs_header)
375 + desc->data[desc->depth - 1].addr, &leaf,
376 sizeof (leaf), 0);
377 if (err)
378 return -err;
379 *outsize = grub_le_to_cpu32 (leaf.size);
380 *outaddr = desc->data[desc->depth - 1].addr + sizeof (struct btrfs_header)
381 + grub_le_to_cpu32 (leaf.offset);
382 *key_out = leaf.key;
383 return 1;
384 }
385
386 static grub_err_t
387 lower_bound (struct grub_btrfs_data *data,
388 const struct grub_btrfs_key *key_in,
389 struct grub_btrfs_key *key_out,
390 grub_uint64_t root,
391 grub_disk_addr_t *outaddr, grub_size_t *outsize,
392 struct grub_btrfs_leaf_descriptor *desc,
393 int recursion_depth)
394 {
395 grub_disk_addr_t addr = grub_le_to_cpu64 (root);
396 int depth = -1;
397
398 if (desc)
399 {
400 desc->allocated = 16;
401 desc->depth = 0;
402 desc->data = grub_malloc (sizeof (desc->data[0]) * desc->allocated);
403 if (!desc->data)
404 return grub_errno;
405 }
406
407 /* > 2 would work as well but be robust and allow a bit more just in case.
408 */
409 if (recursion_depth > 10)
410 return grub_error (GRUB_ERR_BAD_FS, "too deep btrfs virtual nesting");
411
412 grub_dprintf ("btrfs",
413 "retrieving %" PRIxGRUB_UINT64_T
414 " %x %" PRIxGRUB_UINT64_T "\n",
415 key_in->object_id, key_in->type, key_in->offset);
416
417 while (1)
418 {
419 grub_err_t err;
420 struct btrfs_header head;
421
422 reiter:
423 depth++;
424 /* FIXME: preread few nodes into buffer. */
425 err = grub_btrfs_read_logical (data, addr, &head, sizeof (head),
426 recursion_depth + 1);
427 if (err)
428 return err;
429 addr += sizeof (head);
430 if (head.level)
431 {
432 unsigned i;
433 struct grub_btrfs_internal_node node, node_last;
434 int have_last = 0;
435 grub_memset (&node_last, 0, sizeof (node_last));
436 for (i = 0; i < grub_le_to_cpu32 (head.nitems); i++)
437 {
438 err = grub_btrfs_read_logical (data, addr + i * sizeof (node),
439 &node, sizeof (node),
440 recursion_depth + 1);
441 if (err)
442 return err;
443
444 grub_dprintf ("btrfs",
445 "internal node (depth %d) %" PRIxGRUB_UINT64_T
446 " %x %" PRIxGRUB_UINT64_T "\n", depth,
447 node.key.object_id, node.key.type,
448 node.key.offset);
449
450 if (key_cmp (&node.key, key_in) == 0)
451 {
452 err = GRUB_ERR_NONE;
453 if (desc)
454 err = save_ref (desc, addr - sizeof (head), i,
455 grub_le_to_cpu32 (head.nitems), 0);
456 if (err)
457 return err;
458 addr = grub_le_to_cpu64 (node.addr);
459 goto reiter;
460 }
461 if (key_cmp (&node.key, key_in) > 0)
462 break;
463 node_last = node;
464 have_last = 1;
465 }
466 if (have_last)
467 {
468 err = GRUB_ERR_NONE;
469 if (desc)
470 err = save_ref (desc, addr - sizeof (head), i - 1,
471 grub_le_to_cpu32 (head.nitems), 0);
472 if (err)
473 return err;
474 addr = grub_le_to_cpu64 (node_last.addr);
475 goto reiter;
476 }
477 *outsize = 0;
478 *outaddr = 0;
479 grub_memset (key_out, 0, sizeof (*key_out));
480 if (desc)
481 return save_ref (desc, addr - sizeof (head), -1,
482 grub_le_to_cpu32 (head.nitems), 0);
483 return GRUB_ERR_NONE;
484 }
485 {
486 unsigned i;
487 struct grub_btrfs_leaf_node leaf, leaf_last;
488 int have_last = 0;
489 for (i = 0; i < grub_le_to_cpu32 (head.nitems); i++)
490 {
491 err = grub_btrfs_read_logical (data, addr + i * sizeof (leaf),
492 &leaf, sizeof (leaf),
493 recursion_depth + 1);
494 if (err)
495 return err;
496
497 grub_dprintf ("btrfs",
498 "leaf (depth %d) %" PRIxGRUB_UINT64_T
499 " %x %" PRIxGRUB_UINT64_T "\n", depth,
500 leaf.key.object_id, leaf.key.type, leaf.key.offset);
501
502 if (key_cmp (&leaf.key, key_in) == 0)
503 {
504 grub_memcpy (key_out, &leaf.key, sizeof (*key_out));
505 *outsize = grub_le_to_cpu32 (leaf.size);
506 *outaddr = addr + grub_le_to_cpu32 (leaf.offset);
507 if (desc)
508 return save_ref (desc, addr - sizeof (head), i,
509 grub_le_to_cpu32 (head.nitems), 1);
510 return GRUB_ERR_NONE;
511 }
512
513 if (key_cmp (&leaf.key, key_in) > 0)
514 break;
515
516 have_last = 1;
517 leaf_last = leaf;
518 }
519
520 if (have_last)
521 {
522 grub_memcpy (key_out, &leaf_last.key, sizeof (*key_out));
523 *outsize = grub_le_to_cpu32 (leaf_last.size);
524 *outaddr = addr + grub_le_to_cpu32 (leaf_last.offset);
525 if (desc)
526 return save_ref (desc, addr - sizeof (head), i - 1,
527 grub_le_to_cpu32 (head.nitems), 1);
528 return GRUB_ERR_NONE;
529 }
530 *outsize = 0;
531 *outaddr = 0;
532 grub_memset (key_out, 0, sizeof (*key_out));
533 if (desc)
534 return save_ref (desc, addr - sizeof (head), -1,
535 grub_le_to_cpu32 (head.nitems), 1);
536 return GRUB_ERR_NONE;
537 }
538 }
539 }
540
541 static grub_device_t
542 find_device (struct grub_btrfs_data *data, grub_uint64_t id, int do_rescan)
543 {
544 grub_device_t dev_found = NULL;
545 auto int hook (const char *name);
546 int hook (const char *name)
547 {
548 grub_device_t dev;
549 grub_err_t err;
550 struct grub_btrfs_superblock sb;
551 dev = grub_device_open (name);
552 if (!dev)
553 return 0;
554 if (!dev->disk)
555 {
556 grub_device_close (dev);
557 return 0;
558 }
559 err = read_sblock (dev->disk, &sb);
560 if (err == GRUB_ERR_BAD_FS)
561 {
562 grub_device_close (dev);
563 grub_errno = GRUB_ERR_NONE;
564 return 0;
565 }
566 if (err)
567 {
568 grub_device_close (dev);
569 grub_print_error ();
570 return 0;
571 }
572 if (grub_memcmp (data->sblock.uuid, sb.uuid, sizeof (sb.uuid)) != 0
573 || sb.this_device.device_id != id)
574 {
575 grub_device_close (dev);
576 return 0;
577 }
578
579 dev_found = dev;
580 return 1;
581 }
582
583 unsigned i;
584
585 for (i = 0; i < data->n_devices_attached; i++)
586 if (id == data->devices_attached[i].id)
587 return data->devices_attached[i].dev;
588 if (do_rescan)
589 grub_device_iterate (hook);
590 if (!dev_found)
591 {
592 grub_error (GRUB_ERR_BAD_FS,
593 N_("couldn't find a necessary member device "
594 "of multi-device filesystem"));
595 return NULL;
596 }
597 data->n_devices_attached++;
598 if (data->n_devices_attached > data->n_devices_allocated)
599 {
600 void *tmp;
601 data->n_devices_allocated = 2 * data->n_devices_attached + 1;
602 data->devices_attached
603 = grub_realloc (tmp = data->devices_attached,
604 data->n_devices_allocated
605 * sizeof (data->devices_attached[0]));
606 if (!data->devices_attached)
607 {
608 grub_device_close (dev_found);
609 data->devices_attached = tmp;
610 return NULL;
611 }
612 }
613 data->devices_attached[data->n_devices_attached - 1].id = id;
614 data->devices_attached[data->n_devices_attached - 1].dev = dev_found;
615 return dev_found;
616 }
617
618 static grub_err_t
619 grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr,
620 void *buf, grub_size_t size, int recursion_depth)
621 {
622 while (size > 0)
623 {
624 grub_uint8_t *ptr;
625 struct grub_btrfs_key *key;
626 struct grub_btrfs_chunk_item *chunk;
627 grub_uint64_t csize;
628 grub_err_t err = 0;
629 struct grub_btrfs_key key_out;
630 int challoc = 0;
631 grub_device_t dev;
632 struct grub_btrfs_key key_in;
633 grub_size_t chsize;
634 grub_disk_addr_t chaddr;
635
636 grub_dprintf ("btrfs", "searching for laddr %" PRIxGRUB_UINT64_T "\n",
637 addr);
638 for (ptr = data->sblock.bootstrap_mapping;
639 ptr < data->sblock.bootstrap_mapping
640 + sizeof (data->sblock.bootstrap_mapping)
641 - sizeof (struct grub_btrfs_key);)
642 {
643 key = (struct grub_btrfs_key *) ptr;
644 if (key->type != GRUB_BTRFS_ITEM_TYPE_CHUNK)
645 break;
646 chunk = (struct grub_btrfs_chunk_item *) (key + 1);
647 grub_dprintf ("btrfs",
648 "%" PRIxGRUB_UINT64_T " %" PRIxGRUB_UINT64_T " \n",
649 grub_le_to_cpu64 (key->offset),
650 grub_le_to_cpu64 (chunk->size));
651 if (grub_le_to_cpu64 (key->offset) <= addr
652 && addr < grub_le_to_cpu64 (key->offset)
653 + grub_le_to_cpu64 (chunk->size))
654 goto chunk_found;
655 ptr += sizeof (*key) + sizeof (*chunk)
656 + sizeof (struct grub_btrfs_chunk_stripe)
657 * grub_le_to_cpu16 (chunk->nstripes);
658 }
659
660 key_in.object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_OBJECT_ID_CHUNK);
661 key_in.type = GRUB_BTRFS_ITEM_TYPE_CHUNK;
662 key_in.offset = grub_cpu_to_le64 (addr);
663 err = lower_bound (data, &key_in, &key_out,
664 data->sblock.chunk_tree,
665 &chaddr, &chsize, NULL, recursion_depth);
666 if (err)
667 return err;
668 key = &key_out;
669 if (key->type != GRUB_BTRFS_ITEM_TYPE_CHUNK
670 || !(grub_le_to_cpu64 (key->offset) <= addr))
671 return grub_error (GRUB_ERR_BAD_FS,
672 "couldn't find the chunk descriptor");
673
674 chunk = grub_malloc (chsize);
675 if (!chunk)
676 return grub_errno;
677
678 challoc = 1;
679 err = grub_btrfs_read_logical (data, chaddr, chunk, chsize,
680 recursion_depth);
681 if (err)
682 {
683 grub_free (chunk);
684 return err;
685 }
686
687 chunk_found:
688 {
689 grub_uint64_t stripen;
690 grub_uint64_t stripe_offset;
691 grub_uint64_t off = addr - grub_le_to_cpu64 (key->offset);
692 unsigned redundancy = 1;
693 unsigned i, j;
694
695 if (grub_le_to_cpu64 (chunk->size) <= off)
696 {
697 grub_dprintf ("btrfs", "no chunk\n");
698 return grub_error (GRUB_ERR_BAD_FS,
699 "couldn't find the chunk descriptor");
700 }
701
702 grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
703 "+0x%" PRIxGRUB_UINT64_T
704 " (%d stripes (%d substripes) of %"
705 PRIxGRUB_UINT64_T ")\n",
706 grub_le_to_cpu64 (key->offset),
707 grub_le_to_cpu64 (chunk->size),
708 grub_le_to_cpu16 (chunk->nstripes),
709 grub_le_to_cpu16 (chunk->nsubstripes),
710 grub_le_to_cpu64 (chunk->stripe_length));
711
712 switch (grub_le_to_cpu64 (chunk->type)
713 & ~GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE)
714 {
715 case GRUB_BTRFS_CHUNK_TYPE_SINGLE:
716 {
717 grub_uint64_t stripe_length;
718 grub_dprintf ("btrfs", "single\n");
719 stripe_length = grub_divmod64 (grub_le_to_cpu64 (chunk->size),
720 grub_le_to_cpu16 (chunk->nstripes),
721 NULL);
722 stripen = grub_divmod64 (off, stripe_length, &stripe_offset);
723 csize = (stripen + 1) * stripe_length - off;
724 break;
725 }
726 case GRUB_BTRFS_CHUNK_TYPE_DUPLICATED:
727 case GRUB_BTRFS_CHUNK_TYPE_RAID1:
728 {
729 grub_dprintf ("btrfs", "RAID1\n");
730 stripen = 0;
731 stripe_offset = off;
732 csize = grub_le_to_cpu64 (chunk->size) - off;
733 redundancy = 2;
734 break;
735 }
736 case GRUB_BTRFS_CHUNK_TYPE_RAID0:
737 {
738 grub_uint64_t middle, high;
739 grub_uint64_t low;
740 grub_dprintf ("btrfs", "RAID0\n");
741 middle = grub_divmod64 (off,
742 grub_le_to_cpu64 (chunk->stripe_length),
743 &low);
744
745 high = grub_divmod64 (middle, grub_le_to_cpu16 (chunk->nstripes),
746 &stripen);
747 stripe_offset =
748 low + grub_le_to_cpu64 (chunk->stripe_length) * high;
749 csize = grub_le_to_cpu64 (chunk->stripe_length) - low;
750 break;
751 }
752 case GRUB_BTRFS_CHUNK_TYPE_RAID10:
753 {
754 grub_uint64_t middle, high;
755 grub_uint64_t low;
756 middle = grub_divmod64 (off,
757 grub_le_to_cpu64 (chunk->stripe_length),
758 &low);
759
760 high = grub_divmod64 (middle,
761 grub_le_to_cpu16 (chunk->nstripes)
762 / grub_le_to_cpu16 (chunk->nsubstripes),
763 &stripen);
764 stripen *= grub_le_to_cpu16 (chunk->nsubstripes);
765 redundancy = grub_le_to_cpu16 (chunk->nsubstripes);
766 stripe_offset = low + grub_le_to_cpu64 (chunk->stripe_length)
767 * high;
768 csize = grub_le_to_cpu64 (chunk->stripe_length) - low;
769 break;
770 }
771 default:
772 grub_dprintf ("btrfs", "unsupported RAID\n");
773 return grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
774 "unsupported RAID flags %" PRIxGRUB_UINT64_T,
775 grub_le_to_cpu64 (chunk->type));
776 }
777 if (csize == 0)
778 return grub_error (GRUB_ERR_BUG,
779 "couldn't find the chunk descriptor");
780 if (csize > (grub_uint64_t) size)
781 csize = size;
782
783 for (j = 0; j < 2; j++)
784 {
785 for (i = 0; i < redundancy; i++)
786 {
787 struct grub_btrfs_chunk_stripe *stripe;
788 grub_disk_addr_t paddr;
789
790 stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1);
791 /* Right now the redundancy handling is easy.
792 With RAID5-like it will be more difficult. */
793 stripe += stripen + i;
794
795 paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset;
796
797 grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
798 "+0x%" PRIxGRUB_UINT64_T
799 " (%d stripes (%d substripes) of %"
800 PRIxGRUB_UINT64_T ") stripe %" PRIxGRUB_UINT64_T
801 " maps to 0x%" PRIxGRUB_UINT64_T "\n",
802 grub_le_to_cpu64 (key->offset),
803 grub_le_to_cpu64 (chunk->size),
804 grub_le_to_cpu16 (chunk->nstripes),
805 grub_le_to_cpu16 (chunk->nsubstripes),
806 grub_le_to_cpu64 (chunk->stripe_length),
807 stripen, stripe->offset);
808 grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T
809 " for laddr 0x%" PRIxGRUB_UINT64_T "\n", paddr,
810 addr);
811
812 dev = find_device (data, stripe->device_id, j);
813 if (!dev)
814 {
815 err = grub_errno;
816 grub_errno = GRUB_ERR_NONE;
817 continue;
818 }
819
820 err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS,
821 paddr & (GRUB_DISK_SECTOR_SIZE - 1),
822 csize, buf);
823 if (!err)
824 break;
825 grub_errno = GRUB_ERR_NONE;
826 }
827 if (i != redundancy)
828 break;
829 }
830 if (err)
831 return grub_errno = err;
832 }
833 size -= csize;
834 buf = (grub_uint8_t *) buf + csize;
835 addr += csize;
836 if (challoc)
837 grub_free (chunk);
838 }
839 return GRUB_ERR_NONE;
840 }
841
842 static struct grub_btrfs_data *
843 grub_btrfs_mount (grub_device_t dev)
844 {
845 struct grub_btrfs_data *data;
846 grub_err_t err;
847
848 if (!dev->disk)
849 {
850 grub_error (GRUB_ERR_BAD_FS, "not BtrFS");
851 return NULL;
852 }
853
854 data = grub_zalloc (sizeof (*data));
855 if (!data)
856 return NULL;
857
858 err = read_sblock (dev->disk, &data->sblock);
859 if (err)
860 {
861 grub_free (data);
862 return NULL;
863 }
864
865 data->n_devices_allocated = 16;
866 data->devices_attached = grub_malloc (sizeof (data->devices_attached[0])
867 * data->n_devices_allocated);
868 if (!data->devices_attached)
869 {
870 grub_free (data);
871 return NULL;
872 }
873 data->n_devices_attached = 1;
874 data->devices_attached[0].dev = dev;
875 data->devices_attached[0].id = data->sblock.this_device.device_id;
876
877 return data;
878 }
879
880 static void
881 grub_btrfs_unmount (struct grub_btrfs_data *data)
882 {
883 unsigned i;
884 /* The device 0 is closed one layer upper. */
885 for (i = 1; i < data->n_devices_attached; i++)
886 grub_device_close (data->devices_attached[i].dev);
887 grub_free (data->devices_attached);
888 grub_free (data->extent);
889 grub_free (data);
890 }
891
892 static grub_err_t
893 grub_btrfs_read_inode (struct grub_btrfs_data *data,
894 struct grub_btrfs_inode *inode, grub_uint64_t num,
895 grub_uint64_t tree)
896 {
897 struct grub_btrfs_key key_in, key_out;
898 grub_disk_addr_t elemaddr;
899 grub_size_t elemsize;
900 grub_err_t err;
901
902 key_in.object_id = num;
903 key_in.type = GRUB_BTRFS_ITEM_TYPE_INODE_ITEM;
904 key_in.offset = 0;
905
906 err = lower_bound (data, &key_in, &key_out, tree, &elemaddr, &elemsize, NULL,
907 0);
908 if (err)
909 return err;
910 if (num != key_out.object_id
911 || key_out.type != GRUB_BTRFS_ITEM_TYPE_INODE_ITEM)
912 return grub_error (GRUB_ERR_BAD_FS, "inode not found");
913
914 return grub_btrfs_read_logical (data, elemaddr, inode, sizeof (*inode), 0);
915 }
916
917 static grub_ssize_t
918 grub_btrfs_lzo_decompress(char *ibuf, grub_size_t isize, grub_off_t off,
919 char *obuf, grub_size_t osize)
920 {
921 grub_uint32_t total_size, cblock_size;
922 grub_size_t ret = 0;
923 unsigned char buf[GRUB_BTRFS_LZO_BLOCK_SIZE];
924 char *ibuf0 = ibuf;
925
926 total_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf));
927 ibuf += sizeof (total_size);
928
929 if (isize < total_size)
930 return -1;
931
932 /* Jump forward to first block with requested data. */
933 while (off >= GRUB_BTRFS_LZO_BLOCK_SIZE)
934 {
935 /* Don't let following uint32_t cross the page boundary. */
936 if (((ibuf - ibuf0) & 0xffc) == 0xffc)
937 ibuf = ((ibuf - ibuf0 + 3) & ~3) + ibuf0;
938
939 cblock_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf));
940 ibuf += sizeof (cblock_size);
941
942 if (cblock_size > GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE)
943 return -1;
944
945 off -= GRUB_BTRFS_LZO_BLOCK_SIZE;
946 ibuf += cblock_size;
947 }
948
949 while (osize > 0)
950 {
951 lzo_uint usize = GRUB_BTRFS_LZO_BLOCK_SIZE;
952
953 /* Don't let following uint32_t cross the page boundary. */
954 if (((ibuf - ibuf0) & 0xffc) == 0xffc)
955 ibuf = ((ibuf - ibuf0 + 3) & ~3) + ibuf0;
956
957 cblock_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf));
958 ibuf += sizeof (cblock_size);
959
960 if (cblock_size > GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE)
961 return -1;
962
963 /* Block partially filled with requested data. */
964 if (off > 0 || osize < GRUB_BTRFS_LZO_BLOCK_SIZE)
965 {
966 grub_size_t to_copy = GRUB_BTRFS_LZO_BLOCK_SIZE - off;
967
968 if (to_copy > osize)
969 to_copy = osize;
970
971 if (lzo1x_decompress_safe ((lzo_bytep)ibuf, cblock_size, buf, &usize,
972 NULL) != LZO_E_OK)
973 return -1;
974
975 if (to_copy > usize)
976 to_copy = usize;
977 grub_memcpy(obuf, buf + off, to_copy);
978
979 osize -= to_copy;
980 ret += to_copy;
981 obuf += to_copy;
982 ibuf += cblock_size;
983 off = 0;
984 continue;
985 }
986
987 /* Decompress whole block directly to output buffer. */
988 if (lzo1x_decompress_safe ((lzo_bytep)ibuf, cblock_size, (lzo_bytep)obuf,
989 &usize, NULL) != LZO_E_OK)
990 return -1;
991
992 osize -= usize;
993 ret += usize;
994 obuf += usize;
995 ibuf += cblock_size;
996 }
997
998 return ret;
999 }
1000
1001 static grub_ssize_t
1002 grub_btrfs_extent_read (struct grub_btrfs_data *data,
1003 grub_uint64_t ino, grub_uint64_t tree,
1004 grub_off_t pos0, char *buf, grub_size_t len)
1005 {
1006 grub_off_t pos = pos0;
1007 while (len)
1008 {
1009 grub_size_t csize;
1010 grub_err_t err;
1011 grub_off_t extoff;
1012 if (!data->extent || data->extstart > pos || data->extino != ino
1013 || data->exttree != tree || data->extend <= pos)
1014 {
1015 struct grub_btrfs_key key_in, key_out;
1016 grub_disk_addr_t elemaddr;
1017 grub_size_t elemsize;
1018
1019 grub_free (data->extent);
1020 key_in.object_id = ino;
1021 key_in.type = GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM;
1022 key_in.offset = grub_cpu_to_le64 (pos);
1023 err = lower_bound (data, &key_in, &key_out, tree,
1024 &elemaddr, &elemsize, NULL, 0);
1025 if (err)
1026 return -1;
1027 if (key_out.object_id != ino
1028 || key_out.type != GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM)
1029 {
1030 grub_error (GRUB_ERR_BAD_FS, "extent not found");
1031 return -1;
1032 }
1033 if ((grub_ssize_t) elemsize < ((char *) &data->extent->inl
1034 - (char *) data->extent))
1035 {
1036 grub_error (GRUB_ERR_BAD_FS, "extent descriptor is too short");
1037 return -1;
1038 }
1039 data->extstart = grub_le_to_cpu64 (key_out.offset);
1040 data->extsize = elemsize;
1041 data->extent = grub_malloc (elemsize);
1042 data->extino = ino;
1043 data->exttree = tree;
1044 if (!data->extent)
1045 return grub_errno;
1046
1047 err = grub_btrfs_read_logical (data, elemaddr, data->extent,
1048 elemsize, 0);
1049 if (err)
1050 return err;
1051
1052 data->extend = data->extstart + grub_le_to_cpu64 (data->extent->size);
1053 if (data->extent->type == GRUB_BTRFS_EXTENT_REGULAR
1054 && (char *) &data->extent + elemsize
1055 >= (char *) &data->extent->filled + sizeof (data->extent->filled))
1056 data->extend =
1057 data->extstart + grub_le_to_cpu64 (data->extent->filled);
1058
1059 grub_dprintf ("btrfs", "regular extent 0x%" PRIxGRUB_UINT64_T "+0x%"
1060 PRIxGRUB_UINT64_T "\n",
1061 grub_le_to_cpu64 (key_out.offset),
1062 grub_le_to_cpu64 (data->extent->size));
1063 if (data->extend <= pos)
1064 {
1065 grub_error (GRUB_ERR_BAD_FS, "extent not found");
1066 return -1;
1067 }
1068 }
1069 csize = data->extend - pos;
1070 extoff = pos - data->extstart;
1071 if (csize > len)
1072 csize = len;
1073
1074 if (data->extent->encryption)
1075 {
1076 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
1077 "encryption not supported");
1078 return -1;
1079 }
1080
1081 if (data->extent->compression != GRUB_BTRFS_COMPRESSION_NONE
1082 && data->extent->compression != GRUB_BTRFS_COMPRESSION_ZLIB
1083 && data->extent->compression != GRUB_BTRFS_COMPRESSION_LZO)
1084 {
1085 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
1086 "compression type 0x%x not supported",
1087 data->extent->compression);
1088 return -1;
1089 }
1090
1091 if (data->extent->encoding)
1092 {
1093 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET, "encoding not supported");
1094 return -1;
1095 }
1096
1097 switch (data->extent->type)
1098 {
1099 case GRUB_BTRFS_EXTENT_INLINE:
1100 if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZLIB)
1101 {
1102 if (grub_zlib_decompress (data->extent->inl, data->extsize -
1103 ((grub_uint8_t *) data->extent->inl
1104 - (grub_uint8_t *) data->extent),
1105 extoff, buf, csize)
1106 != (grub_ssize_t) csize)
1107 return -1;
1108 }
1109 else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_LZO)
1110 {
1111 if (grub_btrfs_lzo_decompress(data->extent->inl, data->extsize -
1112 ((grub_uint8_t *) data->extent->inl
1113 - (grub_uint8_t *) data->extent),
1114 extoff, buf, csize)
1115 != (grub_ssize_t) csize)
1116 return -1;
1117 }
1118 else
1119 grub_memcpy (buf, data->extent->inl + extoff, csize);
1120 break;
1121 case GRUB_BTRFS_EXTENT_REGULAR:
1122 if (!data->extent->laddr)
1123 {
1124 grub_memset (buf, 0, csize);
1125 break;
1126 }
1127
1128 if (data->extent->compression != GRUB_BTRFS_COMPRESSION_NONE)
1129 {
1130 char *tmp;
1131 grub_uint64_t zsize;
1132 grub_ssize_t ret;
1133
1134 zsize = grub_le_to_cpu64 (data->extent->compressed_size);
1135 tmp = grub_malloc (zsize);
1136 if (!tmp)
1137 return -1;
1138 err = grub_btrfs_read_logical (data,
1139 grub_le_to_cpu64 (data->extent->laddr),
1140 tmp, zsize, 0);
1141 if (err)
1142 {
1143 grub_free (tmp);
1144 return -1;
1145 }
1146
1147 if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZLIB)
1148 ret = grub_zlib_decompress (tmp, zsize, extoff
1149 + grub_le_to_cpu64 (data->extent->offset),
1150 buf, csize);
1151 else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_LZO)
1152 ret = grub_btrfs_lzo_decompress (tmp, zsize, extoff
1153 + grub_le_to_cpu64 (data->extent->offset),
1154 buf, csize);
1155 else
1156 ret = -1;
1157
1158 grub_free (tmp);
1159
1160 if (ret != (grub_ssize_t) csize)
1161 return -1;
1162
1163 break;
1164 }
1165 err = grub_btrfs_read_logical (data,
1166 grub_le_to_cpu64 (data->extent->laddr)
1167 + grub_le_to_cpu64 (data->extent->offset)
1168 + extoff, buf, csize, 0);
1169 if (err)
1170 return -1;
1171 break;
1172 default:
1173 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
1174 "unsupported extent type 0x%x", data->extent->type);
1175 return -1;
1176 }
1177 buf += csize;
1178 pos += csize;
1179 len -= csize;
1180 }
1181 return pos - pos0;
1182 }
1183
1184 static grub_err_t
1185 find_path (struct grub_btrfs_data *data,
1186 const char *path, struct grub_btrfs_key *key,
1187 grub_uint64_t *tree, grub_uint8_t *type)
1188 {
1189 const char *slash = path;
1190 grub_err_t err;
1191 grub_disk_addr_t elemaddr;
1192 grub_size_t elemsize;
1193 grub_size_t allocated = 0;
1194 struct grub_btrfs_dir_item *direl = NULL;
1195 struct grub_btrfs_key key_out;
1196 int skip_default;
1197 const char *ctoken;
1198 grub_size_t ctokenlen;
1199 char *path_alloc = NULL;
1200 char *origpath = NULL;
1201 unsigned symlinks_max = 32;
1202
1203 *type = GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY;
1204 *tree = data->sblock.root_tree;
1205 key->object_id = data->sblock.root_dir_objectid;
1206 key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM;
1207 key->offset = 0;
1208 skip_default = 1;
1209 origpath = grub_strdup (path);
1210 if (!origpath)
1211 return grub_errno;
1212
1213 while (1)
1214 {
1215 if (!skip_default)
1216 {
1217 while (path[0] == '/')
1218 path++;
1219 if (!path[0])
1220 break;
1221 slash = grub_strchr (path, '/');
1222 if (!slash)
1223 slash = path + grub_strlen (path);
1224 ctoken = path;
1225 ctokenlen = slash - path;
1226 }
1227 else
1228 {
1229 ctoken = "default";
1230 ctokenlen = sizeof ("default") - 1;
1231 }
1232
1233 if (*type != GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY)
1234 {
1235 grub_free (path_alloc);
1236 grub_free (origpath);
1237 return grub_error (GRUB_ERR_BAD_FILE_TYPE, N_("not a directory"));
1238 }
1239
1240 if (ctokenlen == 1 && ctoken[0] == '.')
1241 {
1242 if (!skip_default)
1243 path = slash;
1244 skip_default = 0;
1245 continue;
1246 }
1247 if (ctokenlen == 2 && ctoken[0] == '.' && ctoken[1] == '.')
1248 {
1249 key->type = GRUB_BTRFS_ITEM_TYPE_INODE_REF;
1250 key->offset = -1;
1251
1252 err = lower_bound (data, key, &key_out, *tree, &elemaddr, &elemsize,
1253 NULL, 0);
1254 if (err)
1255 {
1256 grub_free (direl);
1257 grub_free (path_alloc);
1258 grub_free (origpath);
1259 return err;
1260 }
1261
1262 if (key_out.type != key->type
1263 || key->object_id != key_out.object_id)
1264 {
1265 grub_free (direl);
1266 grub_free (path_alloc);
1267 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1268 grub_free (origpath);
1269 return err;
1270 }
1271
1272 *type = GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY;
1273 key->object_id = key_out.offset;
1274
1275 if (!skip_default)
1276 path = slash;
1277 skip_default = 0;
1278
1279 continue;
1280 }
1281
1282 key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM;
1283 key->offset = grub_cpu_to_le64 (~grub_getcrc32c (1, ctoken, ctokenlen));
1284
1285 err = lower_bound (data, key, &key_out, *tree, &elemaddr, &elemsize,
1286 NULL, 0);
1287 if (err)
1288 {
1289 grub_free (direl);
1290 grub_free (path_alloc);
1291 grub_free (origpath);
1292 return err;
1293 }
1294 if (key_cmp (key, &key_out) != 0)
1295 {
1296 grub_free (direl);
1297 grub_free (path_alloc);
1298 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1299 grub_free (origpath);
1300 return err;
1301 }
1302
1303 struct grub_btrfs_dir_item *cdirel;
1304 if (elemsize > allocated)
1305 {
1306 allocated = 2 * elemsize;
1307 grub_free (direl);
1308 direl = grub_malloc (allocated + 1);
1309 if (!direl)
1310 {
1311 grub_free (path_alloc);
1312 grub_free (origpath);
1313 return grub_errno;
1314 }
1315 }
1316
1317 err = grub_btrfs_read_logical (data, elemaddr, direl, elemsize, 0);
1318 if (err)
1319 {
1320 grub_free (direl);
1321 grub_free (path_alloc);
1322 grub_free (origpath);
1323 return err;
1324 }
1325
1326 for (cdirel = direl;
1327 (grub_uint8_t *) cdirel - (grub_uint8_t *) direl
1328 < (grub_ssize_t) elemsize;
1329 cdirel = (void *) ((grub_uint8_t *) (direl + 1)
1330 + grub_le_to_cpu16 (cdirel->n)
1331 + grub_le_to_cpu16 (cdirel->m)))
1332 {
1333 if (ctokenlen == grub_le_to_cpu16 (cdirel->n)
1334 && grub_memcmp (cdirel->name, ctoken, ctokenlen) == 0)
1335 break;
1336 }
1337 if ((grub_uint8_t *) cdirel - (grub_uint8_t *) direl
1338 >= (grub_ssize_t) elemsize)
1339 {
1340 grub_free (direl);
1341 grub_free (path_alloc);
1342 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1343 grub_free (origpath);
1344 return err;
1345 }
1346
1347 if (!skip_default)
1348 path = slash;
1349 skip_default = 0;
1350 if (cdirel->type == GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK)
1351 {
1352 struct grub_btrfs_inode inode;
1353 char *tmp;
1354 if (--symlinks_max == 0)
1355 {
1356 grub_free (direl);
1357 grub_free (path_alloc);
1358 grub_free (origpath);
1359 return grub_error (GRUB_ERR_SYMLINK_LOOP,
1360 N_("too deep nesting of symlinks"));
1361 }
1362
1363 err = grub_btrfs_read_inode (data, &inode,
1364 cdirel->key.object_id, *tree);
1365 if (err)
1366 {
1367 grub_free (direl);
1368 grub_free (path_alloc);
1369 grub_free (origpath);
1370 return err;
1371 }
1372 tmp = grub_malloc (grub_le_to_cpu64 (inode.size)
1373 + grub_strlen (path) + 1);
1374 if (!tmp)
1375 {
1376 grub_free (direl);
1377 grub_free (path_alloc);
1378 grub_free (origpath);
1379 return grub_errno;
1380 }
1381
1382 if (grub_btrfs_extent_read (data, cdirel->key.object_id,
1383 *tree, 0, tmp,
1384 grub_le_to_cpu64 (inode.size))
1385 != (grub_ssize_t) grub_le_to_cpu64 (inode.size))
1386 {
1387 grub_free (direl);
1388 grub_free (path_alloc);
1389 grub_free (origpath);
1390 grub_free (tmp);
1391 return grub_errno;
1392 }
1393 grub_memcpy (tmp + grub_le_to_cpu64 (inode.size), path,
1394 grub_strlen (path) + 1);
1395 grub_free (path_alloc);
1396 path = path_alloc = tmp;
1397 if (path[0] == '/')
1398 {
1399 *type = GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY;
1400 *tree = data->sblock.root_tree;
1401 key->object_id = data->sblock.root_dir_objectid;
1402 key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM;
1403 key->offset = 0;
1404 skip_default = 1;
1405 }
1406 continue;
1407 }
1408 *type = cdirel->type;
1409
1410 switch (cdirel->key.type)
1411 {
1412 case GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM:
1413 {
1414 struct grub_btrfs_root_item ri;
1415 err = lower_bound (data, &cdirel->key, &key_out,
1416 data->sblock.root_tree,
1417 &elemaddr, &elemsize, NULL, 0);
1418 if (err)
1419 {
1420 grub_free (direl);
1421 grub_free (path_alloc);
1422 grub_free (origpath);
1423 return err;
1424 }
1425 if (cdirel->key.object_id != key_out.object_id
1426 || cdirel->key.type != key_out.type)
1427 {
1428 grub_free (direl);
1429 grub_free (path_alloc);
1430 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1431 grub_free (origpath);
1432 return err;
1433 }
1434 err = grub_btrfs_read_logical (data, elemaddr, &ri,
1435 sizeof (ri), 0);
1436 if (err)
1437 {
1438 grub_free (direl);
1439 grub_free (path_alloc);
1440 grub_free (origpath);
1441 return err;
1442 }
1443 key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM;
1444 key->offset = 0;
1445 key->object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_OBJECT_ID_CHUNK);
1446 *tree = ri.tree;
1447 break;
1448 }
1449 case GRUB_BTRFS_ITEM_TYPE_INODE_ITEM:
1450 if (*slash && *type == GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR)
1451 {
1452 grub_free (direl);
1453 grub_free (path_alloc);
1454 err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath);
1455 grub_free (origpath);
1456 return err;
1457 }
1458 *key = cdirel->key;
1459 if (*type == GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY)
1460 key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM;
1461 break;
1462 default:
1463 grub_free (path_alloc);
1464 grub_free (origpath);
1465 grub_free (direl);
1466 return grub_error (GRUB_ERR_BAD_FS, "unrecognised object type 0x%x",
1467 cdirel->key.type);
1468 }
1469 }
1470
1471 grub_free (direl);
1472 grub_free (origpath);
1473 grub_free (path_alloc);
1474 return GRUB_ERR_NONE;
1475 }
1476
1477 static grub_err_t
1478 grub_btrfs_dir (grub_device_t device, const char *path,
1479 int (*hook) (const char *filename,
1480 const struct grub_dirhook_info *info))
1481 {
1482 struct grub_btrfs_data *data = grub_btrfs_mount (device);
1483 struct grub_btrfs_key key_in, key_out;
1484 grub_err_t err;
1485 grub_disk_addr_t elemaddr;
1486 grub_size_t elemsize;
1487 grub_size_t allocated = 0;
1488 struct grub_btrfs_dir_item *direl = NULL;
1489 struct grub_btrfs_leaf_descriptor desc;
1490 int r = 0;
1491 grub_uint64_t tree;
1492 grub_uint8_t type;
1493
1494 if (!data)
1495 return grub_errno;
1496
1497 err = find_path (data, path, &key_in, &tree, &type);
1498 if (err)
1499 {
1500 grub_btrfs_unmount (data);
1501 return err;
1502 }
1503 if (type != GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY)
1504 {
1505 grub_btrfs_unmount (data);
1506 return grub_error (GRUB_ERR_BAD_FILE_TYPE, N_("not a directory"));
1507 }
1508
1509 err = lower_bound (data, &key_in, &key_out, tree,
1510 &elemaddr, &elemsize, &desc, 0);
1511 if (err)
1512 {
1513 grub_btrfs_unmount (data);
1514 return err;
1515 }
1516 if (key_out.type != GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
1517 || key_out.object_id != key_in.object_id)
1518 {
1519 r = next (data, &desc, &elemaddr, &elemsize, &key_out);
1520 if (r <= 0)
1521 goto out;
1522 }
1523 do
1524 {
1525 struct grub_btrfs_dir_item *cdirel;
1526 if (key_out.type != GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
1527 || key_out.object_id != key_in.object_id)
1528 {
1529 r = 0;
1530 break;
1531 }
1532 if (elemsize > allocated)
1533 {
1534 allocated = 2 * elemsize;
1535 grub_free (direl);
1536 direl = grub_malloc (allocated + 1);
1537 if (!direl)
1538 {
1539 r = -grub_errno;
1540 break;
1541 }
1542 }
1543
1544 err = grub_btrfs_read_logical (data, elemaddr, direl, elemsize, 0);
1545 if (err)
1546 {
1547 r = -err;
1548 break;
1549 }
1550
1551 for (cdirel = direl;
1552 (grub_uint8_t *) cdirel - (grub_uint8_t *) direl
1553 < (grub_ssize_t) elemsize;
1554 cdirel = (void *) ((grub_uint8_t *) (direl + 1)
1555 + grub_le_to_cpu16 (cdirel->n)
1556 + grub_le_to_cpu16 (cdirel->m)))
1557 {
1558 char c;
1559 struct grub_btrfs_inode inode;
1560 struct grub_dirhook_info info;
1561 err = grub_btrfs_read_inode (data, &inode, cdirel->key.object_id,
1562 tree);
1563 grub_memset (&info, 0, sizeof (info));
1564 if (err)
1565 grub_errno = GRUB_ERR_NONE;
1566 else
1567 {
1568 info.mtime = grub_le_to_cpu64 (inode.mtime.sec);
1569 info.mtimeset = 1;
1570 }
1571 c = cdirel->name[grub_le_to_cpu16 (cdirel->n)];
1572 cdirel->name[grub_le_to_cpu16 (cdirel->n)] = 0;
1573 info.dir = (cdirel->type == GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY);
1574 if (hook (cdirel->name, &info))
1575 goto out;
1576 cdirel->name[grub_le_to_cpu16 (cdirel->n)] = c;
1577 }
1578 r = next (data, &desc, &elemaddr, &elemsize, &key_out);
1579 }
1580 while (r > 0);
1581
1582 out:
1583 grub_free (direl);
1584
1585 free_iterator (&desc);
1586 grub_btrfs_unmount (data);
1587
1588 return -r;
1589 }
1590
1591 static grub_err_t
1592 grub_btrfs_open (struct grub_file *file, const char *name)
1593 {
1594 struct grub_btrfs_data *data = grub_btrfs_mount (file->device);
1595 grub_err_t err;
1596 struct grub_btrfs_inode inode;
1597 grub_uint8_t type;
1598 struct grub_btrfs_key key_in;
1599
1600 if (!data)
1601 return grub_errno;
1602
1603 err = find_path (data, name, &key_in, &data->tree, &type);
1604 if (err)
1605 {
1606 grub_btrfs_unmount (data);
1607 return err;
1608 }
1609 if (type != GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR)
1610 {
1611 grub_btrfs_unmount (data);
1612 return grub_error (GRUB_ERR_BAD_FILE_TYPE, N_("not a regular file"));
1613 }
1614
1615 data->inode = key_in.object_id;
1616 err = grub_btrfs_read_inode (data, &inode, data->inode, data->tree);
1617 if (err)
1618 {
1619 grub_btrfs_unmount (data);
1620 return err;
1621 }
1622
1623 file->data = data;
1624 file->size = grub_le_to_cpu64 (inode.size);
1625
1626 return err;
1627 }
1628
1629 static grub_err_t
1630 grub_btrfs_close (grub_file_t file)
1631 {
1632 grub_btrfs_unmount (file->data);
1633
1634 return GRUB_ERR_NONE;
1635 }
1636
1637 static grub_ssize_t
1638 grub_btrfs_read (grub_file_t file, char *buf, grub_size_t len)
1639 {
1640 struct grub_btrfs_data *data = file->data;
1641
1642 return grub_btrfs_extent_read (data, data->inode,
1643 data->tree, file->offset, buf, len);
1644 }
1645
1646 static grub_err_t
1647 grub_btrfs_uuid (grub_device_t device, char **uuid)
1648 {
1649 struct grub_btrfs_data *data;
1650
1651 *uuid = NULL;
1652
1653 data = grub_btrfs_mount (device);
1654 if (!data)
1655 return grub_errno;
1656
1657 *uuid = grub_xasprintf ("%04x%04x-%04x-%04x-%04x-%04x%04x%04x",
1658 grub_be_to_cpu16 (data->sblock.uuid[0]),
1659 grub_be_to_cpu16 (data->sblock.uuid[1]),
1660 grub_be_to_cpu16 (data->sblock.uuid[2]),
1661 grub_be_to_cpu16 (data->sblock.uuid[3]),
1662 grub_be_to_cpu16 (data->sblock.uuid[4]),
1663 grub_be_to_cpu16 (data->sblock.uuid[5]),
1664 grub_be_to_cpu16 (data->sblock.uuid[6]),
1665 grub_be_to_cpu16 (data->sblock.uuid[7]));
1666
1667 grub_btrfs_unmount (data);
1668
1669 return grub_errno;
1670 }
1671
1672 static grub_err_t
1673 grub_btrfs_label (grub_device_t device, char **label)
1674 {
1675 struct grub_btrfs_data *data;
1676
1677 *label = NULL;
1678
1679 data = grub_btrfs_mount (device);
1680 if (!data)
1681 return grub_errno;
1682
1683 *label = grub_strndup (data->sblock.label, sizeof (data->sblock.label));
1684
1685 grub_btrfs_unmount (data);
1686
1687 return grub_errno;
1688 }
1689
1690 #ifdef GRUB_UTIL
1691 static grub_err_t
1692 grub_btrfs_embed (grub_device_t device __attribute__ ((unused)),
1693 unsigned int *nsectors,
1694 unsigned int max_nsectors,
1695 grub_embed_type_t embed_type,
1696 grub_disk_addr_t **sectors)
1697 {
1698 unsigned i;
1699
1700 if (embed_type != GRUB_EMBED_PCBIOS)
1701 return grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET,
1702 "BtrFS currently supports only PC-BIOS embedding");
1703
1704 if (64 * 2 - 1 < *nsectors)
1705 return grub_error (GRUB_ERR_OUT_OF_RANGE,
1706 N_("your core.img is unusually large. "
1707 "It won't fit in the embedding area"));
1708
1709 *nsectors = 64 * 2 - 1;
1710 if (*nsectors > max_nsectors)
1711 *nsectors = max_nsectors;
1712 *sectors = grub_malloc (*nsectors * sizeof (**sectors));
1713 if (!*sectors)
1714 return grub_errno;
1715 for (i = 0; i < *nsectors; i++)
1716 (*sectors)[i] = i + 1;
1717
1718 return GRUB_ERR_NONE;
1719 }
1720 #endif
1721
1722 static struct grub_fs grub_btrfs_fs = {
1723 .name = "btrfs",
1724 .dir = grub_btrfs_dir,
1725 .open = grub_btrfs_open,
1726 .read = grub_btrfs_read,
1727 .close = grub_btrfs_close,
1728 .uuid = grub_btrfs_uuid,
1729 .label = grub_btrfs_label,
1730 #ifdef GRUB_UTIL
1731 .embed = grub_btrfs_embed,
1732 .reserved_first_sector = 1,
1733 .blocklist_install = 0,
1734 #endif
1735 };
1736
1737 GRUB_MOD_INIT (btrfs)
1738 {
1739 grub_fs_register (&grub_btrfs_fs);
1740 }
1741
1742 GRUB_MOD_FINI (btrfs)
1743 {
1744 grub_fs_unregister (&grub_btrfs_fs);
1745 }
Mirror of AROS' svn.