1 /* btrfs.c - B-tree file system. */
3 * GRUB -- GRand Unified Bootloader
4 * Copyright (C) 2010 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/>.
21 #include <grub/file.h>
23 #include <grub/misc.h>
24 #include <grub/disk.h>
26 #include <grub/types.h>
27 #include <grub/lib/crc.h>
28 #include <grub/deflate.h>
30 GRUB_MOD_LICENSE ("GPLv3+");
32 #define GRUB_BTRFS_SIGNATURE "_BHRfS_M"
34 typedef grub_uint8_t grub_btrfs_checksum_t
[0x20];
35 typedef grub_uint16_t grub_btrfs_uuid_t
[8];
37 struct grub_btrfs_device
39 grub_uint64_t device_id
;
40 grub_uint8_t dummy
[0x62 - 8];
41 } __attribute__ ((packed
));
43 struct grub_btrfs_superblock
45 grub_btrfs_checksum_t checksum
;
46 grub_btrfs_uuid_t uuid
;
47 grub_uint8_t dummy
[0x10];
48 grub_uint8_t signature
[sizeof (GRUB_BTRFS_SIGNATURE
) - 1];
49 grub_uint64_t generation
;
50 grub_uint64_t root_tree
;
51 grub_uint64_t chunk_tree
;
52 grub_uint8_t dummy2
[0x20];
53 grub_uint64_t root_dir_objectid
;
54 grub_uint8_t dummy3
[0x41];
55 struct grub_btrfs_device this_device
;
57 grub_uint8_t dummy4
[0x100];
58 grub_uint8_t bootstrap_mapping
[0x800];
59 } __attribute__ ((packed
));
63 grub_btrfs_checksum_t checksum
;
64 grub_btrfs_uuid_t uuid
;
65 grub_uint8_t dummy
[0x30];
68 } __attribute__ ((packed
));
70 struct grub_btrfs_device_desc
76 struct grub_btrfs_data
78 struct grub_btrfs_superblock sblock
;
82 struct grub_btrfs_device_desc
*devices_attached
;
83 unsigned n_devices_attached
;
84 unsigned n_devices_allocated
;
86 /* Cached extent data. */
87 grub_uint64_t extstart
;
90 grub_uint64_t exttree
;
92 struct grub_btrfs_extent_data
*extent
;
97 grub_uint64_t object_id
;
98 #define GRUB_BTRFS_ITEM_TYPE_INODE_ITEM 0x01
99 #define GRUB_BTRFS_ITEM_TYPE_DIR_ITEM 0x54
100 #define GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM 0x6c
101 #define GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM 0x84
102 #define GRUB_BTRFS_ITEM_TYPE_DEVICE 0xd8
103 #define GRUB_BTRFS_ITEM_TYPE_CHUNK 0xe4
105 grub_uint64_t offset
;
106 } __attribute__ ((packed
));
108 struct grub_btrfs_chunk_item
112 grub_uint64_t stripe_length
;
114 #define GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE 0x07
115 #define GRUB_BTRFS_CHUNK_TYPE_SINGLE 0x00
116 #define GRUB_BTRFS_CHUNK_TYPE_RAID0 0x08
117 #define GRUB_BTRFS_CHUNK_TYPE_RAID1 0x10
118 #define GRUB_BTRFS_CHUNK_TYPE_DUPLICATED 0x20
119 #define GRUB_BTRFS_CHUNK_TYPE_RAID10 0x40
120 grub_uint8_t dummy2
[0xc];
121 grub_uint16_t nstripes
;
122 grub_uint16_t nsubstripes
;
123 } __attribute__ ((packed
));
125 struct grub_btrfs_chunk_stripe
127 grub_uint64_t device_id
;
128 grub_uint64_t offset
;
129 grub_btrfs_uuid_t device_uuid
;
130 } __attribute__ ((packed
));
132 struct grub_btrfs_leaf_node
134 struct grub_btrfs_key key
;
135 grub_uint32_t offset
;
137 } __attribute__ ((packed
));
139 struct grub_btrfs_internal_node
141 struct grub_btrfs_key key
;
144 } __attribute__ ((packed
));
146 struct grub_btrfs_dir_item
148 struct grub_btrfs_key key
;
149 grub_uint8_t dummy
[8];
152 #define GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR 1
153 #define GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY 2
154 #define GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK 7
157 } __attribute__ ((packed
));
159 struct grub_btrfs_leaf_descriptor
164 grub_disk_addr_t addr
;
171 struct grub_btrfs_root_item
173 grub_uint8_t dummy
[0xb0];
178 struct grub_btrfs_time
181 grub_uint32_t nanosec
;
182 } __attribute__ ((aligned(4)));
184 struct grub_btrfs_inode
186 grub_uint8_t dummy1
[0x10];
188 grub_uint8_t dummy2
[0x70];
189 struct grub_btrfs_time mtime
;
190 } __attribute__ ((packed
));
192 struct grub_btrfs_extent_data
196 grub_uint8_t compression
;
197 grub_uint8_t encryption
;
198 grub_uint16_t encoding
;
206 grub_uint64_t compressed_size
;
207 grub_uint64_t offset
;
208 grub_uint64_t filled
;
211 } __attribute__ ((packed
));
213 #define GRUB_BTRFS_EXTENT_INLINE 0
214 #define GRUB_BTRFS_EXTENT_REGULAR 1
216 #define GRUB_BTRFS_COMPRESSION_NONE 0
217 #define GRUB_BTRFS_COMPRESSION_ZLIB 1
219 #define GRUB_BTRFS_OBJECT_ID_CHUNK 0x100
221 static grub_disk_addr_t superblock_sectors
[] = { 64 * 2, 64 * 1024 * 2,
223 1048576ULL * 1048576ULL * 2 };
226 grub_btrfs_read_logical (struct grub_btrfs_data
*data
,
227 grub_disk_addr_t addr
, void *buf
, grub_size_t size
);
230 read_sblock (grub_disk_t disk
, struct grub_btrfs_superblock
*sb
)
233 grub_err_t err
= GRUB_ERR_NONE
;
234 for (i
= 0; i
< ARRAY_SIZE (superblock_sectors
); i
++)
236 struct grub_btrfs_superblock sblock
;
237 err
= grub_disk_read (disk
, superblock_sectors
[i
], 0,
238 sizeof (sblock
), &sblock
);
239 if (err
== GRUB_ERR_OUT_OF_RANGE
)
242 if (grub_memcmp ((char *) sblock
.signature
, GRUB_BTRFS_SIGNATURE
,
243 sizeof (GRUB_BTRFS_SIGNATURE
) - 1) != 0)
245 if (i
== 0 || grub_le_to_cpu64 (sblock
.generation
)
246 > grub_le_to_cpu64 (sb
->generation
))
247 grub_memcpy (sb
, &sblock
, sizeof (sblock
));
250 if ((err
== GRUB_ERR_OUT_OF_RANGE
|| !err
) && i
== 0)
251 return grub_error (GRUB_ERR_BAD_FS
, "not a Btrfs filesystem");
253 if (err
== GRUB_ERR_OUT_OF_RANGE
)
254 grub_errno
= err
= GRUB_ERR_NONE
;
260 key_cmp (const struct grub_btrfs_key
*a
, const struct grub_btrfs_key
*b
)
262 if (grub_cpu_to_le64 (a
->object_id
) < grub_cpu_to_le64 (b
->object_id
))
264 if (grub_cpu_to_le64 (a
->object_id
) > grub_cpu_to_le64 (b
->object_id
))
267 if (a
->type
< b
->type
)
269 if (a
->type
> b
->type
)
272 if (grub_cpu_to_le64 (a
->offset
) < grub_cpu_to_le64 (b
->offset
))
274 if (grub_cpu_to_le64 (a
->offset
) > grub_cpu_to_le64 (b
->offset
))
280 free_iterator (struct grub_btrfs_leaf_descriptor
*desc
)
282 grub_free (desc
->data
);
286 save_ref (struct grub_btrfs_leaf_descriptor
*desc
,
287 grub_disk_addr_t addr
, unsigned i
, unsigned m
, int l
)
290 if (desc
->allocated
< desc
->depth
)
293 desc
->allocated
*= 2;
294 newdata
= grub_realloc (desc
->data
, sizeof (desc
->data
[0])
298 desc
->data
= newdata
;
300 desc
->data
[desc
->depth
- 1].addr
= addr
;
301 desc
->data
[desc
->depth
- 1].iter
= i
;
302 desc
->data
[desc
->depth
- 1].maxiter
= m
;
303 desc
->data
[desc
->depth
- 1].leaf
= l
;
304 return GRUB_ERR_NONE
;
308 next (struct grub_btrfs_data
*data
,
309 struct grub_btrfs_leaf_descriptor
*desc
,
310 grub_disk_addr_t
*outaddr
, grub_size_t
*outsize
,
311 struct grub_btrfs_key
*key_out
)
314 struct grub_btrfs_leaf_node leaf
;
316 for (; desc
->depth
> 0; desc
->depth
--)
318 desc
->data
[desc
->depth
- 1].iter
++;
319 if (desc
->data
[desc
->depth
- 1].iter
320 < desc
->data
[desc
->depth
- 1].maxiter
)
323 if (desc
->depth
== 0)
325 while (!desc
->data
[desc
->depth
- 1].leaf
)
327 struct grub_btrfs_internal_node node
;
328 struct btrfs_header head
;
330 err
= grub_btrfs_read_logical (data
, desc
->data
[desc
->depth
- 1].iter
332 + sizeof (struct btrfs_header
)
333 + desc
->data
[desc
->depth
- 1].addr
, &node
,
338 err
= grub_btrfs_read_logical (data
, grub_le_to_cpu64 (node
.addr
), &head
,
343 save_ref (desc
, grub_le_to_cpu64 (node
.addr
), 0,
344 grub_le_to_cpu32 (head
.nitems
), !head
.level
);
346 err
= grub_btrfs_read_logical (data
, desc
->data
[desc
->depth
- 1].iter
348 + sizeof (struct btrfs_header
)
349 + desc
->data
[desc
->depth
- 1].addr
, &leaf
,
353 *outsize
= grub_le_to_cpu32 (leaf
.size
);
354 *outaddr
= desc
->data
[desc
->depth
- 1].addr
+ sizeof (struct btrfs_header
)
355 + grub_le_to_cpu32 (leaf
.offset
);
361 lower_bound (struct grub_btrfs_data
*data
,
362 const struct grub_btrfs_key
*key_in
,
363 struct grub_btrfs_key
*key_out
,
364 grub_disk_addr_t root
,
365 grub_disk_addr_t
*outaddr
, grub_size_t
*outsize
,
366 struct grub_btrfs_leaf_descriptor
*desc
)
368 grub_disk_addr_t addr
= root
;
373 desc
->allocated
= 16;
375 desc
->data
= grub_malloc (sizeof (desc
->data
[0]) * desc
->allocated
);
380 grub_dprintf ("btrfs",
381 "retrieving %" PRIxGRUB_UINT64_T
382 " %x %" PRIxGRUB_UINT64_T
"\n",
383 key_in
->object_id
, key_in
->type
, key_in
->offset
);
388 struct btrfs_header head
;
392 /* FIXME: preread few nodes into buffer. */
393 err
= grub_btrfs_read_logical (data
, addr
, &head
, sizeof (head
));
396 addr
+= sizeof (head
);
400 struct grub_btrfs_internal_node node
, node_last
;
402 grub_memset (&node_last
, 0, sizeof (node_last
));
403 for (i
= 0; i
< grub_le_to_cpu32 (head
.nitems
); i
++)
405 err
= grub_btrfs_read_logical (data
, addr
+ i
* sizeof (node
),
406 &node
, sizeof (node
));
410 grub_dprintf ("btrfs",
411 "internal node (depth %d) %" PRIxGRUB_UINT64_T
412 " %x %" PRIxGRUB_UINT64_T
"\n", depth
,
413 node
.key
.object_id
, node
.key
.type
, node
.key
.offset
);
415 if (key_cmp (&node
.key
, key_in
) == 0)
419 err
= save_ref (desc
, addr
- sizeof (head
), i
,
420 grub_le_to_cpu32 (head
.nitems
), 0);
423 addr
= grub_le_to_cpu64 (node
.addr
);
426 if (key_cmp (&node
.key
, key_in
) > 0)
435 err
= save_ref (desc
, addr
- sizeof (head
), i
- 1,
436 grub_le_to_cpu32 (head
.nitems
), 0);
439 addr
= grub_le_to_cpu64 (node_last
.addr
);
444 grub_memset (key_out
, 0, sizeof (*key_out
));
446 return save_ref (desc
, addr
- sizeof (head
), -1,
447 grub_le_to_cpu32 (head
.nitems
), 0);
448 return GRUB_ERR_NONE
;
452 struct grub_btrfs_leaf_node leaf
, leaf_last
;
454 for (i
= 0; i
< grub_le_to_cpu32 (head
.nitems
); i
++)
456 err
= grub_btrfs_read_logical (data
, addr
+ i
* sizeof (leaf
),
457 &leaf
, sizeof (leaf
));
461 grub_dprintf ("btrfs",
462 "leaf (depth %d) %" PRIxGRUB_UINT64_T
463 " %x %" PRIxGRUB_UINT64_T
"\n", depth
,
464 leaf
.key
.object_id
, leaf
.key
.type
, leaf
.key
.offset
);
466 if (key_cmp (&leaf
.key
, key_in
) == 0)
468 grub_memcpy (key_out
, &leaf
.key
, sizeof(*key_out
));
469 *outsize
= grub_le_to_cpu32 (leaf
.size
);
470 *outaddr
= addr
+ grub_le_to_cpu32 (leaf
.offset
);
472 return save_ref (desc
, addr
- sizeof (head
), i
,
473 grub_le_to_cpu32 (head
.nitems
), 1);
474 return GRUB_ERR_NONE
;
477 if (key_cmp (&leaf
.key
, key_in
) > 0)
486 grub_memcpy (key_out
, &leaf_last
.key
, sizeof(*key_out
));
487 *outsize
= grub_le_to_cpu32 (leaf_last
.size
);
488 *outaddr
= addr
+ grub_le_to_cpu32 (leaf_last
.offset
);
490 return save_ref (desc
, addr
- sizeof (head
), i
- 1,
491 grub_le_to_cpu32 (head
.nitems
), 1);
492 return GRUB_ERR_NONE
;
496 grub_memset (key_out
, 0, sizeof (*key_out
));
498 return save_ref (desc
, addr
- sizeof (head
), -1,
499 grub_le_to_cpu32 (head
.nitems
), 1);
500 return GRUB_ERR_NONE
;
506 find_device (struct grub_btrfs_data
*data
, grub_uint64_t id
,
509 grub_device_t dev_found
= NULL
;
510 auto int hook (const char *name
);
511 int hook (const char *name
)
515 struct grub_btrfs_superblock sb
;
516 dev
= grub_device_open (name
);
521 grub_device_close (dev
);
524 err
= read_sblock (dev
->disk
, &sb
);
525 if (err
== GRUB_ERR_BAD_FS
)
527 grub_device_close (dev
);
528 grub_errno
= GRUB_ERR_NONE
;
533 grub_device_close (dev
);
537 if (grub_memcmp (data
->sblock
.uuid
, sb
.uuid
, sizeof (sb
.uuid
)) != 0
538 || sb
.this_device
.device_id
!= id
)
540 grub_device_close (dev
);
550 for (i
= 0; i
< data
->n_devices_attached
; i
++)
551 if (id
== data
->devices_attached
[i
].id
)
552 return data
->devices_attached
[i
].dev
;
554 grub_device_iterate (hook
);
557 grub_error (GRUB_ERR_BAD_FS
, "couldn't find a member device");
560 data
->n_devices_attached
++;
561 if (data
->n_devices_attached
> data
->n_devices_allocated
)
564 data
->n_devices_allocated
= 2 * data
->n_devices_attached
+ 1;
565 data
->devices_attached
566 = grub_realloc (tmp
= data
->devices_attached
,
567 data
->n_devices_allocated
568 * sizeof (data
->devices_attached
[0]));
569 if (!data
->devices_attached
)
571 grub_device_close (dev_found
);
572 data
->devices_attached
= tmp
;
576 data
->devices_attached
[data
->n_devices_attached
- 1].id
= id
;
577 data
->devices_attached
[data
->n_devices_attached
- 1].dev
= dev_found
;
582 grub_btrfs_read_logical (struct grub_btrfs_data
*data
,
583 grub_disk_addr_t addr
,
584 void *buf
, grub_size_t size
)
589 struct grub_btrfs_key
*key
;
590 struct grub_btrfs_chunk_item
*chunk
;
593 struct grub_btrfs_key key_out
;
596 grub_dprintf ("btrfs", "searching for laddr %" PRIxGRUB_UINT64_T
"\n",
598 for (ptr
= data
->sblock
.bootstrap_mapping
;
599 ptr
< data
->sblock
.bootstrap_mapping
600 + sizeof (data
->sblock
.bootstrap_mapping
)
601 - sizeof (struct grub_btrfs_key
);
604 key
= (struct grub_btrfs_key
*) ptr
;
605 if (key
->type
!= GRUB_BTRFS_ITEM_TYPE_CHUNK
)
607 chunk
= (struct grub_btrfs_chunk_item
*) (key
+ 1);
608 grub_dprintf ("btrfs", "%" PRIxGRUB_UINT64_T
" %" PRIxGRUB_UINT64_T
" \n",
609 grub_le_to_cpu64 (key
->offset
),
610 grub_le_to_cpu64 (chunk
->size
));
611 if (grub_le_to_cpu64 (key
->offset
) <= addr
612 && addr
< grub_le_to_cpu64 (key
->offset
)
613 + grub_le_to_cpu64 (chunk
->size
))
615 ptr
+= sizeof (*key
) + sizeof (*chunk
)
616 + sizeof (struct grub_btrfs_chunk_stripe
)
617 * grub_le_to_cpu16 (chunk
->nstripes
);
619 struct grub_btrfs_key key_in
;
621 grub_disk_addr_t chaddr
;
622 key_in
.object_id
= GRUB_BTRFS_OBJECT_ID_CHUNK
;
623 key_in
.type
= GRUB_BTRFS_ITEM_TYPE_CHUNK
;
624 key_in
.offset
= addr
;
625 err
= lower_bound (data
, &key_in
, &key_out
,
626 grub_le_to_cpu64 (data
->sblock
.chunk_tree
),
627 &chaddr
, &chsize
, NULL
);
631 if (key
->type
!= GRUB_BTRFS_ITEM_TYPE_CHUNK
632 || !(grub_le_to_cpu64 (key
->offset
) <= addr
))
633 return grub_error (GRUB_ERR_BAD_FS
,
634 "couldn't find the chunk descriptor");
636 chunk
= grub_malloc (chsize
);
641 err
= grub_btrfs_read_logical (data
, chaddr
, chunk
, chsize
);
650 grub_uint32_t stripen
;
651 grub_uint64_t stripe_offset
;
652 grub_uint64_t off
= addr
- grub_le_to_cpu64 (key
->offset
);
653 unsigned redundancy
= 1;
656 if (grub_le_to_cpu64 (chunk
->size
) <= off
)
658 grub_dprintf ("btrfs", "no chunk\n");
659 return grub_error (GRUB_ERR_BAD_FS
,
660 "couldn't find the chunk descriptor");
663 grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
664 "+0x%" PRIxGRUB_UINT64_T
665 " (%d stripes (%d substripes) of %"
666 PRIxGRUB_UINT64_T
")\n",
667 grub_le_to_cpu64 (key
->offset
),
668 grub_le_to_cpu64 (chunk
->size
),
669 grub_le_to_cpu16 (chunk
->nstripes
),
670 grub_le_to_cpu16 (chunk
->nsubstripes
),
671 grub_le_to_cpu64 (chunk
->stripe_length
));
673 switch (grub_le_to_cpu64 (chunk
->type
)
674 & ~GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE
)
676 case GRUB_BTRFS_CHUNK_TYPE_SINGLE
:
678 grub_uint64_t stripe_length
;
679 grub_dprintf ("btrfs", "single\n");
680 stripe_length
= grub_divmod64_full (grub_le_to_cpu64 (chunk
->size
),
681 grub_le_to_cpu16 (chunk
->nstripes
),
683 stripen
= grub_divmod64_full (off
, stripe_length
, &stripe_offset
);
684 csize
= (stripen
+ 1) * stripe_length
- off
;
687 case GRUB_BTRFS_CHUNK_TYPE_DUPLICATED
:
688 case GRUB_BTRFS_CHUNK_TYPE_RAID1
:
690 grub_dprintf ("btrfs", "RAID1\n");
693 csize
= grub_le_to_cpu64 (chunk
->size
) - off
;
697 case GRUB_BTRFS_CHUNK_TYPE_RAID0
:
699 grub_uint64_t middle
, high
;
701 grub_dprintf ("btrfs", "RAID0\n");
702 middle
= grub_divmod64 (off
,
703 grub_le_to_cpu64 (chunk
->stripe_length
),
706 high
= grub_divmod64 (middle
, grub_le_to_cpu16 (chunk
->nstripes
),
708 stripe_offset
= low
+ grub_le_to_cpu64 (chunk
->stripe_length
)
710 csize
= grub_le_to_cpu64 (chunk
->stripe_length
) - low
;
713 case GRUB_BTRFS_CHUNK_TYPE_RAID10
:
715 grub_uint64_t middle
, high
;
717 middle
= grub_divmod64 (off
,
718 grub_le_to_cpu64 (chunk
->stripe_length
),
721 high
= grub_divmod64 (middle
,
722 grub_le_to_cpu16 (chunk
->nsubstripes
),
724 stripen
*= grub_le_to_cpu16 (chunk
->nstripes
)
725 / grub_le_to_cpu16 (chunk
->nsubstripes
);
726 redundancy
= grub_le_to_cpu16 (chunk
->nstripes
)
727 / grub_le_to_cpu16 (chunk
->nsubstripes
);
728 stripe_offset
= low
+ grub_le_to_cpu64 (chunk
->stripe_length
)
730 csize
= grub_le_to_cpu64 (chunk
->stripe_length
) - low
;
734 grub_dprintf ("btrfs", "unsupported RAID\n");
735 return grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET
,
736 "unsupported RAID flags %" PRIxGRUB_UINT64_T
,
737 grub_le_to_cpu64 (chunk
->type
));
740 return grub_error (GRUB_ERR_BUG
,
741 "couldn't find the chunk descriptor");
742 if ((grub_size_t
) csize
> size
)
745 for (j
= 0; j
< 2; j
++)
747 for (i
= 0; i
< redundancy
; i
++)
749 struct grub_btrfs_chunk_stripe
*stripe
;
750 grub_disk_addr_t paddr
;
752 stripe
= (struct grub_btrfs_chunk_stripe
*) (chunk
+ 1);
753 /* Right now the redundancy handling is easy.
754 With RAID5-like it will be more difficult. */
755 stripe
+= stripen
+ i
;
757 paddr
= stripe
->offset
+ stripe_offset
;
759 grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T
760 "+0x%" PRIxGRUB_UINT64_T
" (%d stripes (%d substripes) of %"
761 PRIxGRUB_UINT64_T
") stripe %" PRIxGRUB_UINT32_T
762 " maps to 0x%" PRIxGRUB_UINT64_T
"\n",
763 grub_le_to_cpu64 (key
->offset
),
764 grub_le_to_cpu64 (chunk
->size
),
765 grub_le_to_cpu16 (chunk
->nstripes
),
766 grub_le_to_cpu16 (chunk
->nsubstripes
),
767 grub_le_to_cpu64 (chunk
->stripe_length
),
768 stripen
, stripe
->offset
);
769 grub_dprintf ("btrfs", "reading paddr 0x%" PRIxGRUB_UINT64_T
770 " for laddr 0x%" PRIxGRUB_UINT64_T
"\n", paddr
,
773 dev
= find_device (data
, stripe
->device_id
, j
);
777 grub_errno
= GRUB_ERR_NONE
;
781 err
= grub_disk_read (dev
->disk
, paddr
>> GRUB_DISK_SECTOR_BITS
,
782 paddr
& (GRUB_DISK_SECTOR_SIZE
- 1),
786 grub_errno
= GRUB_ERR_NONE
;
792 return grub_errno
= err
;
795 buf
= (grub_uint8_t
*) buf
+ csize
;
800 return GRUB_ERR_NONE
;
803 static struct grub_btrfs_data
*
804 grub_btrfs_mount (grub_device_t dev
)
806 struct grub_btrfs_data
*data
;
811 grub_error (GRUB_ERR_BAD_FS
, "not BtrFS");
815 data
= grub_zalloc (sizeof (*data
));
819 err
= read_sblock (dev
->disk
, &data
->sblock
);
826 data
->n_devices_allocated
= 16;
827 data
->devices_attached
= grub_malloc (sizeof (data
->devices_attached
[0])
828 * data
->n_devices_allocated
);
829 if (!data
->devices_attached
)
834 data
->n_devices_attached
= 1;
835 data
->devices_attached
[0].dev
= dev
;
836 data
->devices_attached
[0].id
= data
->sblock
.this_device
.device_id
;
842 grub_btrfs_unmount (struct grub_btrfs_data
*data
)
845 /* The device 0 is closed one layer upper. */
846 for (i
= 1; i
< data
->n_devices_attached
; i
++)
847 grub_device_close (data
->devices_attached
[i
].dev
);
848 grub_free (data
->devices_attached
);
849 grub_free (data
->extent
);
854 grub_btrfs_read_inode (struct grub_btrfs_data
*data
,
855 struct grub_btrfs_inode
*inode
, grub_uint64_t num
,
858 struct grub_btrfs_key key_in
, key_out
;
859 grub_disk_addr_t elemaddr
;
860 grub_size_t elemsize
;
863 key_in
.object_id
= num
;
864 key_in
.type
= GRUB_BTRFS_ITEM_TYPE_INODE_ITEM
;
867 err
= lower_bound (data
, &key_in
, &key_out
, tree
,
868 &elemaddr
, &elemsize
, NULL
);
871 if (num
!= key_out
.object_id
872 || key_out
.type
!= GRUB_BTRFS_ITEM_TYPE_INODE_ITEM
)
873 return grub_error (GRUB_ERR_BAD_FS
, "inode not found");
875 return grub_btrfs_read_logical (data
, elemaddr
, inode
, sizeof (*inode
));
879 grub_btrfs_extent_read (struct grub_btrfs_data
*data
,
880 grub_uint64_t ino
, grub_uint64_t tree
,
881 grub_off_t pos0
, char *buf
, grub_size_t len
)
883 grub_off_t pos
= pos0
;
889 if (!data
->extent
|| data
->extstart
> pos
|| data
->extino
!= ino
890 || data
->exttree
!= tree
|| data
->extend
<= pos
)
892 struct grub_btrfs_key key_in
, key_out
;
893 grub_disk_addr_t elemaddr
;
894 grub_size_t elemsize
;
896 grub_free (data
->extent
);
897 key_in
.object_id
= ino
;
898 key_in
.type
= GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM
;
899 key_in
.offset
= grub_cpu_to_le64 (pos
);
900 err
= lower_bound (data
, &key_in
, &key_out
, tree
,
901 &elemaddr
, &elemsize
, NULL
);
904 if (key_out
.object_id
!= ino
905 || key_out
.type
!= GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM
)
907 grub_error (GRUB_ERR_BAD_FS
, "extent not found");
910 data
->extstart
= grub_le_to_cpu64 (key_out
.offset
);
911 data
->extsize
= elemsize
;
912 data
->extent
= grub_malloc (elemsize
);
914 data
->exttree
= tree
;
918 err
= grub_btrfs_read_logical (data
, elemaddr
,
919 data
->extent
, elemsize
);
923 data
->extend
= data
->extstart
924 + grub_le_to_cpu64 (data
->extent
->size
);
925 if (data
->extent
->type
== GRUB_BTRFS_EXTENT_REGULAR
926 && (char *) &data
->extent
+ elemsize
927 >= (char *) &data
->extent
->filled
928 + sizeof (data
->extent
->filled
))
929 data
->extend
= data
->extstart
930 + grub_le_to_cpu64 (data
->extent
->filled
);
932 grub_dprintf ("btrfs", "extent 0x%" PRIxGRUB_UINT64_T
"+0x%"
933 PRIxGRUB_UINT64_T
" (0x%"
934 PRIxGRUB_UINT64_T
")\n",
935 grub_le_to_cpu64 (key_out
.offset
),
936 grub_le_to_cpu64 (data
->extent
->size
),
937 grub_le_to_cpu64 (data
->extent
->filled
));
938 if (data
->extend
<= pos
)
940 grub_error (GRUB_ERR_BAD_FS
, "extent not found");
944 csize
= data
->extend
- pos
;
945 extoff
= pos
- data
->extstart
;
949 if (data
->extent
->encryption
)
951 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET
,
952 "encryption not supported");
956 if (data
->extent
->compression
!= GRUB_BTRFS_COMPRESSION_NONE
957 && data
->extent
->compression
!= GRUB_BTRFS_COMPRESSION_ZLIB
)
959 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET
,
960 "compression type 0x%x not supported",
961 data
->extent
->compression
);
965 if (data
->extent
->encoding
)
967 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET
,
968 "encoding not supported");
972 switch (data
->extent
->type
)
974 case GRUB_BTRFS_EXTENT_INLINE
:
975 if (data
->extent
->compression
== GRUB_BTRFS_COMPRESSION_ZLIB
)
977 if (grub_zlib_decompress (data
->extent
->inl
, data
->extsize
-
978 ((grub_uint8_t
*) data
->extent
->inl
979 - (grub_uint8_t
*) data
->extent
),
981 != (grub_ssize_t
) csize
)
985 grub_memcpy (buf
, data
->extent
->inl
+ extoff
, csize
);
987 case GRUB_BTRFS_EXTENT_REGULAR
:
988 if (!data
->extent
->laddr
)
990 grub_memset (buf
, 0, csize
);
993 if (data
->extent
->compression
== GRUB_BTRFS_COMPRESSION_ZLIB
)
997 zsize
= grub_le_to_cpu64 (data
->extent
->compressed_size
);
998 tmp
= grub_malloc (zsize
);
1001 err
= grub_btrfs_read_logical (data
,
1002 grub_le_to_cpu64 (data
->extent
->laddr
),
1009 if (grub_zlib_decompress (tmp
, zsize
, extoff
1010 + grub_le_to_cpu64 (data
->extent
->offset
),
1011 buf
, csize
) != (grub_ssize_t
) csize
)
1019 err
= grub_btrfs_read_logical (data
,
1020 grub_le_to_cpu64 (data
->extent
->laddr
)
1021 + grub_le_to_cpu64 (data
->extent
->offset
)
1028 grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET
,
1029 "unsupported extent type 0x%x", data
->extent
->type
);
1040 find_path (struct grub_btrfs_data
*data
,
1041 const char *path
, struct grub_btrfs_key
*key
,
1042 grub_uint64_t
*tree
, grub_uint8_t
*type
)
1044 const char *slash
= path
;
1046 grub_disk_addr_t elemaddr
;
1047 grub_size_t elemsize
;
1048 grub_size_t allocated
= 0;
1049 struct grub_btrfs_dir_item
*direl
= NULL
;
1050 struct grub_btrfs_key key_out
;
1053 grub_size_t ctokenlen
;
1054 char *path_alloc
= NULL
;
1055 unsigned symlinks_max
= 32;
1057 *type
= GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY
;
1058 *tree
= data
->sblock
.root_tree
;
1059 key
->object_id
= data
->sblock
.root_dir_objectid
;
1060 key
->type
= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
;
1068 while (path
[0] == '/')
1072 slash
= grub_strchr (path
, '/');
1074 slash
= path
+ grub_strlen (path
);
1076 ctokenlen
= slash
- path
;
1081 ctokenlen
= sizeof ("default") - 1;
1084 if (*type
!= GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY
)
1086 grub_free (path_alloc
);
1087 return grub_error (GRUB_ERR_BAD_FILE_TYPE
, "not a directory");
1090 key
->type
= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
;
1091 key
->offset
= grub_cpu_to_le64 (~grub_getcrc32c (1, ctoken
, ctokenlen
));
1093 err
= lower_bound (data
, key
, &key_out
, *tree
,
1094 &elemaddr
, &elemsize
, NULL
);
1098 grub_free (path_alloc
);
1101 if (key_cmp (key
, &key_out
) != 0)
1104 grub_free (path_alloc
);
1105 return grub_error (GRUB_ERR_FILE_NOT_FOUND
, "file not found");
1108 struct grub_btrfs_dir_item
*cdirel
;
1109 if (elemsize
> allocated
)
1111 allocated
= 2 * elemsize
;
1113 direl
= grub_malloc (allocated
+ 1);
1116 grub_free (path_alloc
);
1121 err
= grub_btrfs_read_logical (data
, elemaddr
, direl
, elemsize
);
1125 grub_free (path_alloc
);
1129 for (cdirel
= direl
;
1130 (grub_uint8_t
*) cdirel
- (grub_uint8_t
*) direl
1131 < (grub_ssize_t
) elemsize
;
1132 cdirel
= (void *) ((grub_uint8_t
*) (direl
+ 1)
1133 + grub_le_to_cpu16 (cdirel
->n
)
1134 + grub_le_to_cpu16 (cdirel
->m
)))
1136 if (ctokenlen
== grub_le_to_cpu16 (cdirel
->n
)
1137 && grub_memcmp (cdirel
->name
, ctoken
, ctokenlen
) == 0)
1140 if ((grub_uint8_t
*) cdirel
- (grub_uint8_t
*) direl
1141 >= (grub_ssize_t
) elemsize
)
1144 grub_free (path_alloc
);
1145 return grub_error (GRUB_ERR_FILE_NOT_FOUND
, "file not found");
1151 if (cdirel
->type
== GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK
)
1153 struct grub_btrfs_inode inode
;
1155 if (--symlinks_max
== 0)
1158 grub_free (path_alloc
);
1159 return grub_error (GRUB_ERR_SYMLINK_LOOP
,
1160 "too deep nesting of symlinks");
1163 err
= grub_btrfs_read_inode (data
, &inode
,
1164 cdirel
->key
.object_id
, *tree
);
1168 grub_free (path_alloc
);
1171 tmp
= grub_malloc (grub_le_to_cpu64 (inode
.size
)
1172 + grub_strlen (path
) + 1);
1176 grub_free (path_alloc
);
1180 if (grub_btrfs_extent_read (data
, cdirel
->key
.object_id
,
1182 grub_le_to_cpu64 (inode
.size
))
1183 != (grub_ssize_t
) grub_le_to_cpu64 (inode
.size
))
1186 grub_free (path_alloc
);
1190 grub_memcpy (tmp
+ grub_le_to_cpu64 (inode
.size
), path
,
1191 grub_strlen (path
) + 1);
1192 grub_free (path_alloc
);
1193 path
= path_alloc
= tmp
;
1196 *type
= GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY
;
1197 *tree
= data
->sblock
.root_tree
;
1198 key
->object_id
= data
->sblock
.root_dir_objectid
;
1199 key
->type
= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
;
1205 *type
= cdirel
->type
;
1207 switch (cdirel
->key
.type
)
1209 case GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM
:
1211 struct grub_btrfs_root_item ri
;
1212 err
= lower_bound (data
, &cdirel
->key
, &key_out
,
1213 data
->sblock
.root_tree
,
1214 &elemaddr
, &elemsize
, NULL
);
1218 grub_free (path_alloc
);
1221 if (cdirel
->key
.object_id
!= key_out
.object_id
1222 || cdirel
->key
.type
!= key_out
.type
)
1225 grub_free (path_alloc
);
1226 return grub_error (GRUB_ERR_FILE_NOT_FOUND
, "file not found");
1228 err
= grub_btrfs_read_logical (data
, elemaddr
,
1233 grub_free (path_alloc
);
1236 key
->type
= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
;
1238 key
->object_id
= GRUB_BTRFS_OBJECT_ID_CHUNK
;
1239 *tree
= grub_le_to_cpu64 (ri
.tree
);
1242 case GRUB_BTRFS_ITEM_TYPE_INODE_ITEM
:
1243 if (*slash
&& *type
== GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR
)
1246 grub_free (path_alloc
);
1247 return grub_error (GRUB_ERR_FILE_NOT_FOUND
, "file not found");
1250 if (*type
== GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY
)
1251 key
->type
= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
;
1254 grub_free (path_alloc
);
1256 return grub_error (GRUB_ERR_BAD_FS
, "unrecognised object type 0x%x",
1262 return GRUB_ERR_NONE
;
1266 grub_btrfs_dir (grub_device_t device
, const char *path
,
1267 int (*hook
) (const char *filename
,
1268 const struct grub_dirhook_info
*info
))
1270 struct grub_btrfs_data
*data
= grub_btrfs_mount (device
);
1271 struct grub_btrfs_key key_in
, key_out
;
1273 grub_disk_addr_t elemaddr
;
1274 grub_size_t elemsize
;
1275 grub_size_t allocated
= 0;
1276 struct grub_btrfs_dir_item
*direl
= NULL
;
1277 struct grub_btrfs_leaf_descriptor desc
;
1285 err
= find_path (data
, path
, &key_in
, &tree
, &type
);
1288 if (type
!= GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY
)
1289 return grub_error (GRUB_ERR_BAD_FILE_TYPE
, "not a directory");
1291 err
= lower_bound (data
, &key_in
, &key_out
, tree
,
1292 &elemaddr
, &elemsize
, &desc
);
1295 if (key_out
.type
!= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
1296 || key_out
.object_id
!= key_in
.object_id
)
1298 r
= next (data
, &desc
, &elemaddr
, &elemsize
, &key_out
);
1301 free_iterator (&desc
);
1307 struct grub_btrfs_dir_item
*cdirel
;
1308 if (key_out
.type
!= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
1309 || key_out
.object_id
!= key_in
.object_id
)
1314 if (elemsize
> allocated
)
1316 allocated
= 2 * elemsize
;
1318 direl
= grub_malloc (allocated
+ 1);
1321 free_iterator (&desc
);
1326 err
= grub_btrfs_read_logical (data
, elemaddr
, direl
, elemsize
);
1330 for (cdirel
= direl
;
1331 (grub_uint8_t
*) cdirel
- (grub_uint8_t
*) direl
1332 < (grub_ssize_t
) elemsize
;
1333 cdirel
= (void *) ((grub_uint8_t
*) (direl
+ 1)
1334 + grub_le_to_cpu16 (cdirel
->n
)
1335 + grub_le_to_cpu16 (cdirel
->m
)))
1338 struct grub_btrfs_inode inode
;
1339 struct grub_dirhook_info info
;
1340 err
= grub_btrfs_read_inode (data
, &inode
, cdirel
->key
.object_id
,
1342 grub_memset (&info
, 0, sizeof (info
));
1344 grub_errno
= GRUB_ERR_NONE
;
1347 info
.mtime
= inode
.mtime
.sec
;
1350 c
= cdirel
->name
[grub_le_to_cpu16 (cdirel
->n
)];
1351 cdirel
->name
[grub_le_to_cpu16 (cdirel
->n
)] = 0;
1352 info
.dir
= (cdirel
->type
== GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY
);
1353 if (hook (cdirel
->name
, &info
))
1355 cdirel
->name
[grub_le_to_cpu16 (cdirel
->n
)] = c
;
1357 r
= next (data
, &desc
, &elemaddr
, &elemsize
, &key_out
);
1364 free_iterator (&desc
);
1365 grub_btrfs_unmount (data
);
1371 grub_btrfs_open (struct grub_file
*file
, const char *name
)
1373 struct grub_btrfs_data
*data
= grub_btrfs_mount (file
->device
);
1375 struct grub_btrfs_inode inode
;
1377 struct grub_btrfs_key key_in
;
1382 err
= find_path (data
, name
, &key_in
, &data
->tree
, &type
);
1385 grub_btrfs_unmount (data
);
1388 if (type
!= GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR
)
1390 grub_btrfs_unmount (data
);
1391 return grub_error (GRUB_ERR_BAD_FILE_TYPE
, "not a regular file");
1394 data
->inode
= key_in
.object_id
;
1395 err
= grub_btrfs_read_inode (data
, &inode
, data
->inode
, data
->tree
);
1398 grub_btrfs_unmount (data
);
1403 file
->size
= grub_le_to_cpu64 (inode
.size
);
1409 grub_btrfs_close (grub_file_t file
)
1411 grub_btrfs_unmount (file
->data
);
1413 return GRUB_ERR_NONE
;
1417 grub_btrfs_read (grub_file_t file
, char *buf
, grub_size_t len
)
1419 struct grub_btrfs_data
*data
= file
->data
;
1421 return grub_btrfs_extent_read (data
, data
->inode
,
1422 data
->tree
, file
->offset
, buf
, len
);
1426 grub_btrfs_uuid (grub_device_t device
, char **uuid
)
1428 struct grub_btrfs_data
*data
;
1432 data
= grub_btrfs_mount (device
);
1436 *uuid
= grub_xasprintf ("%04x%04x-%04x-%04x-%04x-%04x%04x%04x",
1437 grub_be_to_cpu16 (data
->sblock
.uuid
[0]),
1438 grub_be_to_cpu16 (data
->sblock
.uuid
[1]),
1439 grub_be_to_cpu16 (data
->sblock
.uuid
[2]),
1440 grub_be_to_cpu16 (data
->sblock
.uuid
[3]),
1441 grub_be_to_cpu16 (data
->sblock
.uuid
[4]),
1442 grub_be_to_cpu16 (data
->sblock
.uuid
[5]),
1443 grub_be_to_cpu16 (data
->sblock
.uuid
[6]),
1444 grub_be_to_cpu16 (data
->sblock
.uuid
[7]));
1446 grub_btrfs_unmount (data
);
1452 grub_btrfs_label (grub_device_t device
, char **label
)
1454 struct grub_btrfs_data
*data
;
1458 data
= grub_btrfs_mount (device
);
1462 *label
= grub_strndup (data
->sblock
.label
, sizeof (data
->sblock
.label
));
1464 grub_btrfs_unmount (data
);
1469 static struct grub_fs grub_btrfs_fs
=
1472 .dir
= grub_btrfs_dir
,
1473 .open
= grub_btrfs_open
,
1474 .read
= grub_btrfs_read
,
1475 .close
= grub_btrfs_close
,
1476 .uuid
= grub_btrfs_uuid
,
1477 .label
= grub_btrfs_label
,
1479 .reserved_first_sector
= 1,
1483 GRUB_MOD_INIT(btrfs
)
1485 grub_fs_register (&grub_btrfs_fs
);
1488 GRUB_MOD_FINI(btrfs
)
1490 grub_fs_unregister (&grub_btrfs_fs
);