5 * Copyright (c) 2013 Tencent, Inc.
7 * This driver base on grub 2.0 btrfs implementation.
10 /* btrfs.c - B-tree file system. */
12 * GRUB -- GRand Unified Bootloader
13 * Copyright (C) 2010 Free Software Foundation, Inc.
15 * GRUB is free software: you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation, either version 3 of the License, or
18 * (at your option) any later version.
20 * GRUB is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
25 * You should have received a copy of the GNU General Public License
26 * along with GRUB. If not, see <http://www.gnu.org/licenses/>.
29 //#define DPRINT(x...) Print(x)
32 #define uint8_t fsw_u8
33 #define uint16_t fsw_u16
34 #define uint32_t fsw_u32
35 #define uint64_t fsw_u64
36 #define int64_t fsw_s64
37 #define int32_t fsw_s32
40 #define DPRINT(x...) /* */
43 /* no single io/element size over 2G */
44 #define fsw_size_t int
45 #define fsw_ssize_t int
46 /* never zip over 2G, 32bit is enough */
47 #define grub_off_t int32_t
48 #define grub_size_t int32_t
49 #define grub_ssize_t int32_t
52 #define MINILZO_CFG_SKIP_LZO_PTR 1
53 #define MINILZO_CFG_SKIP_LZO_UTIL 1
54 #define MINILZO_CFG_SKIP_LZO_STRING 1
55 #define MINILZO_CFG_SKIP_LZO_INIT 1
56 #define MINILZO_CFG_SKIP_LZO1X_DECOMPRESS 1
57 #define MINILZO_CFG_SKIP_LZO1X_1_COMPRESS 1
58 #define MINILZO_CFG_SKIP_LZO_STRING 1
62 #define BTRFS_DEFAULT_BLOCK_SIZE 4096
63 #define BTRFS_INITIAL_BCACHE_SIZE 1024
64 #define GRUB_BTRFS_SIGNATURE "_BHRfS_M"
66 /* From http://www.oberhumer.com/opensource/lzo/lzofaq.php
67 * LZO will expand incompressible data by a little amount. I still haven't
68 * computed the exact values, but I suggest using these formulas for
69 * a worst-case expansion calculation:
71 * output_block_size = input_block_size + (input_block_size / 16) + 64 + 3
73 #define GRUB_BTRFS_LZO_BLOCK_SIZE 4096
74 #define GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE (GRUB_BTRFS_LZO_BLOCK_SIZE + \
75 (GRUB_BTRFS_LZO_BLOCK_SIZE / 16) + 64 + 3)
78 * on disk struct has prefix 'btrfs_', little endian
79 * on memory struct has prefix 'fsw_btrfs_'
81 typedef uint8_t btrfs_checksum_t
[0x20];
82 typedef uint32_t btrfs_uuid_t
[4];
88 uint8_t dummy
[0x62 - 0x10];
89 } __attribute__ ((__packed__
));
91 struct btrfs_superblock
93 btrfs_checksum_t checksum
;
96 uint8_t signature
[sizeof (GRUB_BTRFS_SIGNATURE
) - 1];
100 uint8_t dummy2
[0x10];
101 uint64_t total_bytes
;
103 uint64_t root_dir_objectid
;
104 #define BTRFS_MAX_NUM_DEVICES 0x10000
105 uint64_t num_devices
;
109 uint8_t dummy3
[0x31];
110 struct btrfs_device this_device
;
112 uint8_t dummy4
[0x100];
113 uint8_t bootstrap_mapping
[0x800];
114 } __attribute__ ((__packed__
));
118 btrfs_checksum_t checksum
;
123 } __attribute__ ((__packed__
));
125 struct fsw_btrfs_device_desc
127 struct fsw_volume
* dev
;
131 struct fsw_btrfs_volume
133 struct fsw_volume g
; //!< Generic volume structure
135 /* superblock shadows */
136 uint8_t bootstrap_mapping
[0x800];
138 uint64_t total_bytes
;
142 uint64_t top_tree
; /* top volume tree */
143 unsigned num_devices
;
144 unsigned sectorshift
;
148 struct fsw_btrfs_device_desc
*devices_attached
;
149 unsigned n_devices_attached
;
150 unsigned n_devices_allocated
;
152 /* Cached extent data. */
158 struct btrfs_extent_data
*extent
;
163 GRUB_BTRFS_ITEM_TYPE_INODE_ITEM
= 0x01,
164 GRUB_BTRFS_ITEM_TYPE_INODE_REF
= 0x0c,
165 GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
= 0x54,
166 GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM
= 0x6c,
167 GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM
= 0x84,
168 GRUB_BTRFS_ITEM_TYPE_DEVICE
= 0xd8,
169 GRUB_BTRFS_ITEM_TYPE_CHUNK
= 0xe4
177 } __attribute__ ((__packed__
));
179 struct btrfs_chunk_item
183 uint64_t stripe_length
;
185 #define GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE 0x07
186 #define GRUB_BTRFS_CHUNK_TYPE_SINGLE 0x00
187 #define GRUB_BTRFS_CHUNK_TYPE_RAID0 0x08
188 #define GRUB_BTRFS_CHUNK_TYPE_RAID1 0x10
189 #define GRUB_BTRFS_CHUNK_TYPE_DUPLICATED 0x20
190 #define GRUB_BTRFS_CHUNK_TYPE_RAID10 0x40
193 uint16_t nsubstripes
;
194 } __attribute__ ((__packed__
));
196 struct btrfs_chunk_stripe
200 btrfs_uuid_t device_uuid
;
201 } __attribute__ ((__packed__
));
203 struct btrfs_leaf_node
205 struct btrfs_key key
;
208 } __attribute__ ((__packed__
));
210 struct btrfs_internal_node
212 struct btrfs_key key
;
215 } __attribute__ ((__packed__
));
217 struct btrfs_dir_item
219 struct btrfs_key key
;
223 #define GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR 1
224 #define GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY 2
225 #define GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK 7
228 } __attribute__ ((__packed__
));
230 struct fsw_btrfs_leaf_descriptor
243 struct btrfs_root_item
248 } __attribute__ ((__packed__
));
254 } __attribute__ ((__packed__
));
262 uint64_t block_group
;
272 uint64_t reserved
[4];
273 struct btrfs_time atime
;
274 struct btrfs_time ctime
;
275 struct btrfs_time mtime
;
276 struct btrfs_time otime
;
277 } __attribute__ ((__packed__
));
279 struct fsw_btrfs_dnode
{
280 struct fsw_dnode g
; //!< Generic dnode structure
281 struct btrfs_inode
*raw
; //!< Full raw inode structure
284 struct btrfs_extent_data
298 uint64_t compressed_size
;
303 } __attribute__ ((__packed__
));
305 #define GRUB_BTRFS_EXTENT_INLINE 0
306 #define GRUB_BTRFS_EXTENT_REGULAR 1
308 #define GRUB_BTRFS_COMPRESSION_NONE 0
309 #define GRUB_BTRFS_COMPRESSION_ZLIB 1
310 #define GRUB_BTRFS_COMPRESSION_LZO 2
312 #define GRUB_BTRFS_OBJECT_ID_CHUNK 0x100
314 struct fsw_btrfs_uuid_list
{
315 struct fsw_btrfs_volume
*master
;
316 struct fsw_btrfs_uuid_list
*next
;
319 static int uuid_eq(btrfs_uuid_t u1
, btrfs_uuid_t u2
) {
320 return u1
[0]==u2
[0] && u1
[1]==u2
[1] && u1
[2]==u2
[2] && u1
[3]==u2
[3];
323 static struct fsw_btrfs_uuid_list
*master_uuid_list
= NULL
;
325 static int master_uuid_add(struct fsw_btrfs_volume
*vol
, struct fsw_btrfs_volume
**master_out
) {
326 struct fsw_btrfs_uuid_list
*l
;
328 for (l
= master_uuid_list
; l
; l
=l
->next
)
329 if(uuid_eq(l
->master
->uuid
, vol
->uuid
)) {
331 *master_out
= l
->master
;
335 l
= AllocatePool(sizeof(struct fsw_btrfs_uuid_list
));
337 l
->next
= master_uuid_list
;
338 master_uuid_list
= l
;
342 static void master_uuid_remove(struct fsw_btrfs_volume
*vol
) {
343 struct fsw_btrfs_uuid_list
**lp
;
345 for (lp
= &master_uuid_list
; *lp
; lp
=&(*lp
)->next
)
346 if((*lp
)->master
== vol
) {
347 struct fsw_btrfs_uuid_list
*n
= *lp
;
354 static fsw_status_t
btrfs_set_superblock_info(struct fsw_btrfs_volume
*vol
, struct btrfs_superblock
*sb
)
357 vol
->uuid
[0] = sb
->uuid
[0];
358 vol
->uuid
[1] = sb
->uuid
[1];
359 vol
->uuid
[2] = sb
->uuid
[2];
360 vol
->uuid
[3] = sb
->uuid
[3];
361 vol
->chunk_tree
= sb
->chunk_tree
;
362 vol
->root_tree
= sb
->root_tree
;
363 vol
->total_bytes
= fsw_u64_le_swap(sb
->total_bytes
);
364 vol
->bytes_used
= fsw_u64_le_swap(sb
->bytes_used
);
366 vol
->sectorshift
= 0;
367 vol
->sectorsize
= fsw_u32_le_swap(sb
->sectorsize
);
368 for(i
=9; i
<20; i
++) {
369 if((1UL<<i
) == vol
->sectorsize
) {
370 vol
->sectorshift
= i
;
374 if(fsw_u64_le_swap(sb
->num_devices
) > BTRFS_MAX_NUM_DEVICES
)
375 vol
->num_devices
= BTRFS_MAX_NUM_DEVICES
;
377 vol
->num_devices
= fsw_u64_le_swap(sb
->num_devices
);
378 fsw_memcpy(vol
->bootstrap_mapping
, sb
->bootstrap_mapping
, sizeof(vol
->bootstrap_mapping
));
382 static uint64_t superblock_pos
[4] = {
386 1048576ULL * 1048576ULL / 4
389 static fsw_status_t
fsw_btrfs_read_logical(struct fsw_btrfs_volume
*vol
,
390 uint64_t addr
, void *buf
, fsw_size_t size
, int rdepth
, int cache_level
);
392 static fsw_status_t
btrfs_read_superblock (struct fsw_volume
*vol
, struct btrfs_superblock
*sb_out
)
395 uint64_t total_blocks
= 1024;
396 fsw_status_t err
= FSW_SUCCESS
;
398 fsw_set_blocksize(vol
, BTRFS_DEFAULT_BLOCK_SIZE
, BTRFS_DEFAULT_BLOCK_SIZE
);
399 for (i
= 0; i
< 4; i
++)
402 struct btrfs_superblock
*sb
;
404 /* Don't try additional superblocks beyond device size. */
405 if (total_blocks
<= superblock_pos
[i
])
408 err
= fsw_block_get(vol
, superblock_pos
[i
], 0, (void **)&buffer
);
410 fsw_block_release(vol
, superblock_pos
[i
], buffer
);
414 sb
= (struct btrfs_superblock
*)buffer
;
415 if (!fsw_memeq (sb
->signature
, GRUB_BTRFS_SIGNATURE
,
416 sizeof (GRUB_BTRFS_SIGNATURE
) - 1))
418 fsw_block_release(vol
, superblock_pos
[i
], buffer
);
421 if (i
== 0 || fsw_u64_le_swap (sb
->generation
) > fsw_u64_le_swap (sb_out
->generation
))
423 fsw_memcpy (sb_out
, sb
, sizeof (*sb
));
424 total_blocks
= fsw_u64_le_swap (sb
->this_device
.size
) >> 12;
426 fsw_block_release(vol
, superblock_pos
[i
], buffer
);
429 if ((err
== FSW_UNSUPPORTED
|| !err
) && i
== 0)
430 return FSW_UNSUPPORTED
;
432 if (err
== FSW_UNSUPPORTED
)
436 DPRINT(L
"btrfs: UUID: %08x-%08x-%08x-%08x device id: %d\n",
437 sb_out
->uuid
[0], sb_out
->uuid
[1], sb_out
->uuid
[2], sb_out
->uuid
[3],
438 sb_out
->this_device
.device_id
);
442 static int key_cmp (const struct btrfs_key
*a
, const struct btrfs_key
*b
)
444 if (fsw_u64_le_swap (a
->object_id
) < fsw_u64_le_swap (b
->object_id
))
446 if (fsw_u64_le_swap (a
->object_id
) > fsw_u64_le_swap (b
->object_id
))
449 if (a
->type
< b
->type
)
451 if (a
->type
> b
->type
)
454 if (fsw_u64_le_swap (a
->offset
) < fsw_u64_le_swap (b
->offset
))
456 if (fsw_u64_le_swap (a
->offset
) > fsw_u64_le_swap (b
->offset
))
461 static void free_iterator (struct fsw_btrfs_leaf_descriptor
*desc
)
463 fsw_free (desc
->data
);
466 static fsw_status_t
save_ref (struct fsw_btrfs_leaf_descriptor
*desc
,
467 uint64_t addr
, unsigned i
, unsigned m
, int l
)
470 if (desc
->allocated
< desc
->depth
)
473 int oldsize
= sizeof (desc
->data
[0]) * desc
->allocated
;
474 desc
->allocated
*= 2;
475 newdata
= AllocatePool (sizeof (desc
->data
[0]) * desc
->allocated
);
477 return FSW_OUT_OF_MEMORY
;
478 fsw_memcpy(newdata
, desc
->data
, oldsize
);
479 FreePool(desc
->data
);
480 desc
->data
= newdata
;
482 desc
->data
[desc
->depth
- 1].addr
= addr
;
483 desc
->data
[desc
->depth
- 1].iter
= i
;
484 desc
->data
[desc
->depth
- 1].maxiter
= m
;
485 desc
->data
[desc
->depth
- 1].leaf
= l
;
489 static int next (struct fsw_btrfs_volume
*vol
,
490 struct fsw_btrfs_leaf_descriptor
*desc
,
491 uint64_t * outaddr
, fsw_size_t
* outsize
,
492 struct btrfs_key
*key_out
)
495 struct btrfs_leaf_node leaf
;
497 for (; desc
->depth
> 0; desc
->depth
--)
499 desc
->data
[desc
->depth
- 1].iter
++;
500 if (desc
->data
[desc
->depth
- 1].iter
501 < desc
->data
[desc
->depth
- 1].maxiter
)
504 if (desc
->depth
== 0)
506 while (!desc
->data
[desc
->depth
- 1].leaf
)
508 struct btrfs_internal_node node
;
509 struct btrfs_header head
;
510 fsw_memzero(&node
, sizeof(node
));
512 err
= fsw_btrfs_read_logical (vol
, desc
->data
[desc
->depth
- 1].iter
514 + sizeof (struct btrfs_header
)
515 + desc
->data
[desc
->depth
- 1].addr
,
516 &node
, sizeof (node
), 0, 1);
520 err
= fsw_btrfs_read_logical (vol
, fsw_u64_le_swap (node
.addr
),
521 &head
, sizeof (head
), 0, 1);
525 save_ref (desc
, fsw_u64_le_swap (node
.addr
), 0,
526 fsw_u32_le_swap (head
.nitems
), !head
.level
);
528 err
= fsw_btrfs_read_logical (vol
, desc
->data
[desc
->depth
- 1].iter
530 + sizeof (struct btrfs_header
)
531 + desc
->data
[desc
->depth
- 1].addr
, &leaf
,
532 sizeof (leaf
), 0, 1);
535 *outsize
= fsw_u32_le_swap (leaf
.size
);
536 *outaddr
= desc
->data
[desc
->depth
- 1].addr
+ sizeof (struct btrfs_header
)
537 + fsw_u32_le_swap (leaf
.offset
);
542 #define depth2cache(x) ((x) >= 4 ? 1 : 5-(x))
543 static fsw_status_t
lower_bound (struct fsw_btrfs_volume
*vol
,
544 const struct btrfs_key
*key_in
,
545 struct btrfs_key
*key_out
,
547 uint64_t *outaddr
, fsw_size_t
*outsize
,
548 struct fsw_btrfs_leaf_descriptor
*desc
,
551 uint64_t addr
= fsw_u64_le_swap (root
);
556 desc
->allocated
= 16;
558 desc
->data
= AllocatePool (sizeof (desc
->data
[0]) * desc
->allocated
);
560 return FSW_OUT_OF_MEMORY
;
563 /* > 2 would work as well but be robust and allow a bit more just in case.
566 return FSW_VOLUME_CORRUPTED
;
568 DPRINT (L
"btrfs: retrieving %lx %x %lx\n",
569 key_in
->object_id
, key_in
->type
, key_in
->offset
);
574 struct btrfs_header head
;
575 fsw_memzero(&head
, sizeof(head
));
579 /* FIXME: preread few nodes into buffer. */
580 err
= fsw_btrfs_read_logical (vol
, addr
, &head
, sizeof (head
),
581 rdepth
+ 1, depth2cache(rdepth
));
584 addr
+= sizeof (head
);
588 struct btrfs_internal_node node
, node_last
;
590 fsw_memzero (&node_last
, sizeof (node_last
));
591 for (i
= 0; i
< fsw_u32_le_swap (head
.nitems
); i
++)
593 err
= fsw_btrfs_read_logical (vol
, addr
+ i
* sizeof (node
),
594 &node
, sizeof (node
), rdepth
+ 1, depth2cache(rdepth
));
598 DPRINT (L
"btrfs: internal node (depth %d) %lx %x %lx\n", depth
,
599 node
.key
.object_id
, node
.key
.type
,
602 if (key_cmp (&node
.key
, key_in
) == 0)
606 err
= save_ref (desc
, addr
- sizeof (head
), i
,
607 fsw_u32_le_swap (head
.nitems
), 0);
610 addr
= fsw_u64_le_swap (node
.addr
);
613 if (key_cmp (&node
.key
, key_in
) > 0)
622 err
= save_ref (desc
, addr
- sizeof (head
), i
- 1,
623 fsw_u32_le_swap (head
.nitems
), 0);
626 addr
= fsw_u64_le_swap (node_last
.addr
);
631 fsw_memzero (key_out
, sizeof (*key_out
));
633 return save_ref (desc
, addr
- sizeof (head
), -1,
634 fsw_u32_le_swap (head
.nitems
), 0);
639 struct btrfs_leaf_node leaf
, leaf_last
;
641 for (i
= 0; i
< fsw_u32_le_swap (head
.nitems
); i
++)
643 err
= fsw_btrfs_read_logical (vol
, addr
+ i
* sizeof (leaf
),
644 &leaf
, sizeof (leaf
), rdepth
+ 1, depth2cache(rdepth
));
648 DPRINT (L
"btrfs: leaf (depth %d) %lx %x %lx\n", depth
,
649 leaf
.key
.object_id
, leaf
.key
.type
, leaf
.key
.offset
);
651 if (key_cmp (&leaf
.key
, key_in
) == 0)
653 fsw_memcpy (key_out
, &leaf
.key
, sizeof (*key_out
));
654 *outsize
= fsw_u32_le_swap (leaf
.size
);
655 *outaddr
= addr
+ fsw_u32_le_swap (leaf
.offset
);
657 return save_ref (desc
, addr
- sizeof (head
), i
,
658 fsw_u32_le_swap (head
.nitems
), 1);
662 if (key_cmp (&leaf
.key
, key_in
) > 0)
671 fsw_memcpy (key_out
, &leaf_last
.key
, sizeof (*key_out
));
672 *outsize
= fsw_u32_le_swap (leaf_last
.size
);
673 *outaddr
= addr
+ fsw_u32_le_swap (leaf_last
.offset
);
675 return save_ref (desc
, addr
- sizeof (head
), i
- 1,
676 fsw_u32_le_swap (head
.nitems
), 1);
681 fsw_memzero (key_out
, sizeof (*key_out
));
683 return save_ref (desc
, addr
- sizeof (head
), -1,
684 fsw_u32_le_swap (head
.nitems
), 1);
690 static int btrfs_add_multi_device(struct fsw_btrfs_volume
*master
, struct fsw_volume
*slave
, struct btrfs_superblock
*sb
)
693 for( i
= 0; i
< master
->n_devices_attached
; i
++)
694 if(sb
->this_device
.device_id
== master
->devices_attached
[i
].id
)
695 return FSW_UNSUPPORTED
;
697 slave
= clone_dummy_volume(slave
);
699 return FSW_OUT_OF_MEMORY
;
700 fsw_set_blocksize(slave
, master
->sectorsize
, master
->sectorsize
);
701 slave
->bcache_size
= BTRFS_INITIAL_BCACHE_SIZE
;
703 master
->devices_attached
[i
].id
= sb
->this_device
.device_id
;
704 master
->devices_attached
[i
].dev
= slave
;
705 master
->n_devices_attached
++;
707 DPRINT(L
"Found slave %d\n", sb
->this_device
.device_id
);
711 static int scan_disks_hook(struct fsw_volume
*volg
, struct fsw_volume
*slave
) {
712 struct fsw_btrfs_volume
*vol
= (struct fsw_btrfs_volume
*)volg
;
713 struct btrfs_superblock sb
;
716 if(vol
->n_devices_attached
>= vol
->n_devices_allocated
)
717 return FSW_UNSUPPORTED
;
719 err
= btrfs_read_superblock(slave
, &sb
);
721 return FSW_UNSUPPORTED
;
723 if(!uuid_eq(vol
->uuid
, sb
.uuid
))
724 return FSW_UNSUPPORTED
;
726 return btrfs_add_multi_device(vol
, slave
, &sb
);
729 static struct fsw_volume
*
730 find_device (struct fsw_btrfs_volume
*vol
, uint64_t id
, int do_rescan
) {
734 for (i
= 0; i
< vol
->n_devices_attached
; i
++)
735 if (id
== vol
->devices_attached
[i
].id
)
736 return vol
->devices_attached
[i
].dev
;
737 } while(vol
->n_devices_attached
< vol
->n_devices_allocated
&&
739 scan_disks(scan_disks_hook
, &vol
->g
) > 0);
740 DPRINT(L
"sub device %d not found\n", id
);
744 static fsw_status_t
fsw_btrfs_read_logical (struct fsw_btrfs_volume
*vol
, uint64_t addr
,
745 void *buf
, fsw_size_t size
, int rdepth
, int cache_level
)
750 struct btrfs_key
*key
;
751 struct btrfs_chunk_item
*chunk
;
753 fsw_status_t err
= 0;
754 struct btrfs_key key_out
;
756 struct btrfs_key key_in
;
760 for (ptr
= vol
->bootstrap_mapping
; ptr
< vol
->bootstrap_mapping
+ sizeof (vol
->bootstrap_mapping
) - sizeof (struct btrfs_key
);)
762 key
= (struct btrfs_key
*) ptr
;
763 if (key
->type
!= GRUB_BTRFS_ITEM_TYPE_CHUNK
)
765 chunk
= (struct btrfs_chunk_item
*) (key
+ 1);
766 if (fsw_u64_le_swap (key
->offset
) <= addr
767 && addr
< fsw_u64_le_swap (key
->offset
)
768 + fsw_u64_le_swap (chunk
->size
))
772 ptr
+= sizeof (*key
) + sizeof (*chunk
)
773 + sizeof (struct btrfs_chunk_stripe
)
774 * fsw_u16_le_swap (chunk
->nstripes
);
777 key_in
.object_id
= fsw_u64_le_swap (GRUB_BTRFS_OBJECT_ID_CHUNK
);
778 key_in
.type
= GRUB_BTRFS_ITEM_TYPE_CHUNK
;
779 key_in
.offset
= fsw_u64_le_swap (addr
);
780 err
= lower_bound (vol
, &key_in
, &key_out
, vol
->chunk_tree
, &chaddr
, &chsize
, NULL
, rdepth
);
784 if (key
->type
!= GRUB_BTRFS_ITEM_TYPE_CHUNK
785 || !(fsw_u64_le_swap (key
->offset
) <= addr
))
787 return FSW_VOLUME_CORRUPTED
;
789 // "couldn't find the chunk descriptor");
791 chunk
= AllocatePool (chsize
);
793 return FSW_OUT_OF_MEMORY
;
797 err
= fsw_btrfs_read_logical (vol
, chaddr
, chunk
, chsize
, rdepth
, cache_level
< 5 ? cache_level
+1 : 5);
807 #ifdef __MAKEWITH_GNUEFI
808 #define UINTREM UINTN
811 #define DivU64x32 DivU64x32Remainder
812 #define UINTREM UINT32
815 UINTREM stripe_offset
;
816 uint64_t off
= addr
- fsw_u64_le_swap (key
->offset
);
817 unsigned redundancy
= 1;
820 if (fsw_u64_le_swap (chunk
->size
) <= off
)
822 return FSW_VOLUME_CORRUPTED
;
823 //"couldn't find the chunk descriptor");
826 DPRINT(L
"btrfs chunk 0x%lx+0xlx %d stripes (%d substripes) of %lx\n",
827 fsw_u64_le_swap (key
->offset
),
828 fsw_u64_le_swap (chunk
->size
),
829 fsw_u16_le_swap (chunk
->nstripes
),
830 fsw_u16_le_swap (chunk
->nsubstripes
),
831 fsw_u64_le_swap (chunk
->stripe_length
));
833 /* gnu-efi has no DivU64x64Remainder, limited to DivU64x32 */
834 switch (fsw_u64_le_swap (chunk
->type
)
835 & ~GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE
)
837 case GRUB_BTRFS_CHUNK_TYPE_SINGLE
:
839 uint64_t stripe_length
;
841 stripe_length
= DivU64x32 (fsw_u64_le_swap (chunk
->size
),
842 fsw_u16_le_swap (chunk
->nstripes
), NULL
);
844 if(stripe_length
> 1UL<<30)
845 return FSW_VOLUME_CORRUPTED
;
847 stripen
= DivU64x32 (off
, (uint32_t)stripe_length
, &stripe_offset
);
848 csize
= (stripen
+ 1) * stripe_length
- off
;
849 DPRINT(L
"read_logical %d chunk_found single csize=%d\n", __LINE__
, csize
);
852 case GRUB_BTRFS_CHUNK_TYPE_DUPLICATED
:
853 case GRUB_BTRFS_CHUNK_TYPE_RAID1
:
857 csize
= fsw_u64_le_swap (chunk
->size
) - off
;
859 DPRINT(L
"read_logical %d chunk_found dup/raid1 off=%lx csize=%d\n", __LINE__
, stripe_offset
, csize
);
862 case GRUB_BTRFS_CHUNK_TYPE_RAID0
:
864 uint64_t stripe_length
= fsw_u64_le_swap (chunk
->stripe_length
);
865 uint64_t middle
, high
;
868 if(stripe_length
> 1UL<<30)
869 return FSW_VOLUME_CORRUPTED
;
871 middle
= DivU64x32 (off
, (uint32_t)stripe_length
, &low
);
873 high
= DivU64x32 (middle
, fsw_u16_le_swap (chunk
->nstripes
), &stripen
);
875 low
+ fsw_u64_le_swap (chunk
->stripe_length
) * high
;
876 csize
= fsw_u64_le_swap (chunk
->stripe_length
) - low
;
877 DPRINT(L
"read_logical %d chunk_found raid0 csize=%d\n", __LINE__
, csize
);
880 case GRUB_BTRFS_CHUNK_TYPE_RAID10
:
882 uint64_t stripe_length
= fsw_u64_le_swap (chunk
->stripe_length
);
883 uint64_t middle
, high
;
886 if(stripe_length
> 1UL<<30)
887 return FSW_VOLUME_CORRUPTED
;
889 middle
= DivU64x32 (off
, stripe_length
, &low
);
891 high
= DivU64x32 (middle
,
892 fsw_u16_le_swap (chunk
->nstripes
)
893 / fsw_u16_le_swap (chunk
->nsubstripes
),
895 stripen
*= fsw_u16_le_swap (chunk
->nsubstripes
);
896 redundancy
= fsw_u16_le_swap (chunk
->nsubstripes
);
897 stripe_offset
= low
+ fsw_u64_le_swap (chunk
->stripe_length
)
899 csize
= fsw_u64_le_swap (chunk
->stripe_length
) - low
;
900 DPRINT(L
"read_logical %d chunk_found raid01 csize=%d\n", __LINE__
, csize
);
904 DPRINT (L
"btrfs: unsupported RAID\n");
905 return FSW_UNSUPPORTED
;
908 //"couldn't find the chunk descriptor");
909 return FSW_VOLUME_CORRUPTED
;
911 if (csize
> (uint64_t) size
)
914 for (j
= 0; j
< 2; j
++)
916 for (i
= 0; i
< redundancy
; i
++)
918 struct btrfs_chunk_stripe
*stripe
;
920 struct fsw_volume
*dev
;
922 stripe
= (struct btrfs_chunk_stripe
*) (chunk
+ 1);
923 /* Right now the redundancy handling is easy.
924 With RAID5-like it will be more difficult. */
925 stripe
+= stripen
+ i
;
927 paddr
= fsw_u64_le_swap (stripe
->offset
) + stripe_offset
;
929 DPRINT (L
"btrfs: chunk 0x%lx+0x%lx (%d stripes (%d substripes) of %lx) stripe %lx maps to 0x%lx\n",
930 fsw_u64_le_swap (key
->offset
),
931 fsw_u64_le_swap (chunk
->size
),
932 fsw_u16_le_swap (chunk
->nstripes
),
933 fsw_u16_le_swap (chunk
->nsubstripes
),
934 fsw_u64_le_swap (chunk
->stripe_length
),
935 stripen
, stripe
->offset
);
936 DPRINT (L
"btrfs: reading paddr 0x%lx for laddr 0x%lx\n", paddr
, addr
);
938 dev
= find_device (vol
, stripe
->device_id
, j
);
941 err
= FSW_VOLUME_CORRUPTED
;
945 uint32_t off
= paddr
& (vol
->sectorsize
- 1);
946 paddr
>>= vol
->sectorshift
;
950 err
= fsw_block_get(dev
, paddr
, cache_level
, (void **)&buffer
);
953 int s
= vol
->sectorsize
- off
;
956 fsw_memcpy(buf
+n
, buffer
+off
, s
);
957 fsw_block_release(dev
, paddr
, (void *)buffer
);
963 DPRINT (L
"read logical: err %d csize %d got %d\n",
975 buf
= (uint8_t *) buf
+ csize
;
977 if (challoc
&& chunk
)
983 static fsw_status_t
fsw_btrfs_get_default_root(struct fsw_btrfs_volume
*vol
, uint64_t root_dir_objectid
);
984 static fsw_status_t
fsw_btrfs_volume_mount(struct fsw_volume
*volg
) {
985 struct btrfs_superblock sblock
;
986 struct fsw_btrfs_volume
*vol
= (struct fsw_btrfs_volume
*)volg
;
987 struct fsw_btrfs_volume
*master_out
= NULL
;
993 fsw_memzero((char *)vol
+sizeof(*volg
), sizeof(*vol
)-sizeof(*volg
));
995 err
= btrfs_read_superblock (volg
, &sblock
);
999 btrfs_set_superblock_info(vol
, &sblock
);
1001 if(vol
->sectorshift
== 0)
1002 return FSW_UNSUPPORTED
;
1004 if(vol
->num_devices
>= BTRFS_MAX_NUM_DEVICES
)
1005 return FSW_UNSUPPORTED
;
1007 vol
->is_master
= master_uuid_add(vol
, &master_out
);
1008 /* already mounted via other device */
1009 if(vol
->is_master
== 0) {
1010 #define FAKE_LABEL "btrfs.multi.device"
1011 s
.type
= FSW_STRING_TYPE_UTF8
;
1012 s
.size
= s
.len
= sizeof(FAKE_LABEL
)-1;
1013 s
.data
= FAKE_LABEL
;
1014 err
= fsw_strdup_coerce(&volg
->label
, volg
->host_string_type
, &s
);
1017 btrfs_add_multi_device(master_out
, volg
, &sblock
);
1018 /* create fake root */
1019 return fsw_dnode_create_root_with_tree(volg
, 0, 0, &volg
->root
);
1022 fsw_set_blocksize(volg
, vol
->sectorsize
, vol
->sectorsize
);
1023 vol
->g
.bcache_size
= BTRFS_INITIAL_BCACHE_SIZE
;
1024 vol
->n_devices_allocated
= vol
->num_devices
;
1025 vol
->devices_attached
= AllocatePool (sizeof (vol
->devices_attached
[0])
1026 * vol
->n_devices_allocated
);
1027 if (!vol
->devices_attached
)
1028 return FSW_OUT_OF_MEMORY
;
1030 vol
->n_devices_attached
= 1;
1031 vol
->devices_attached
[0].dev
= volg
;
1032 vol
->devices_attached
[0].id
= sblock
.this_device
.device_id
;
1034 for (i
= 0; i
< 0x100; i
++)
1035 if (sblock
.label
[i
] == 0)
1038 s
.type
= FSW_STRING_TYPE_UTF8
;
1040 s
.data
= sblock
.label
;
1041 err
= fsw_strdup_coerce(&volg
->label
, volg
->host_string_type
, &s
);
1043 FreePool (vol
->devices_attached
);
1044 vol
->devices_attached
= NULL
;
1048 err
= fsw_btrfs_get_default_root(vol
, sblock
.root_dir_objectid
);
1050 DPRINT(L
"root not found\n");
1051 FreePool (vol
->devices_attached
);
1052 vol
->devices_attached
= NULL
;
1059 static void fsw_btrfs_volume_free(struct fsw_volume
*volg
)
1062 struct fsw_btrfs_volume
*vol
= (struct fsw_btrfs_volume
*)volg
;
1068 master_uuid_remove(vol
);
1070 /* The device 0 is closed one layer upper. */
1071 for (i
= 1; i
< vol
->n_devices_attached
; i
++)
1072 fsw_unmount (vol
->devices_attached
[i
].dev
);
1073 if(vol
->devices_attached
)
1074 FreePool (vol
->devices_attached
);
1076 FreePool (vol
->extent
);
1079 static fsw_status_t
fsw_btrfs_volume_stat(struct fsw_volume
*volg
, struct fsw_volume_stat
*sb
)
1081 struct fsw_btrfs_volume
*vol
= (struct fsw_btrfs_volume
*)volg
;
1082 sb
->total_bytes
= vol
->total_bytes
;
1083 sb
->free_bytes
= vol
->bytes_used
;
1087 static fsw_status_t
fsw_btrfs_read_inode (struct fsw_btrfs_volume
*vol
,
1088 struct btrfs_inode
*inode
, uint64_t num
,
1091 struct btrfs_key key_in
, key_out
;
1093 fsw_size_t elemsize
;
1096 key_in
.object_id
= num
;
1097 key_in
.type
= GRUB_BTRFS_ITEM_TYPE_INODE_ITEM
;
1100 err
= lower_bound (vol
, &key_in
, &key_out
, tree
, &elemaddr
, &elemsize
, NULL
, 0);
1103 if (num
!= key_out
.object_id
1104 || key_out
.type
!= GRUB_BTRFS_ITEM_TYPE_INODE_ITEM
)
1105 return FSW_NOT_FOUND
;
1107 return fsw_btrfs_read_logical (vol
, elemaddr
, inode
, sizeof (*inode
), 0, 2);
1110 static fsw_status_t
fsw_btrfs_dnode_fill(struct fsw_volume
*volg
, struct fsw_dnode
*dnog
)
1112 struct fsw_btrfs_volume
*vol
= (struct fsw_btrfs_volume
*)volg
;
1113 struct fsw_btrfs_dnode
*dno
= (struct fsw_btrfs_dnode
*)dnog
;
1117 /* slave device got empty root */
1118 if (!vol
->is_master
) {
1120 dno
->g
.type
= FSW_DNODE_TYPE_DIR
;
1127 dno
->raw
= AllocatePool(sizeof(struct btrfs_inode
));
1128 if(dno
->raw
== NULL
)
1129 return FSW_OUT_OF_MEMORY
;
1131 err
= fsw_btrfs_read_inode(vol
, dno
->raw
, dno
->g
.dnode_id
, dno
->g
.tree_id
);
1138 // get info from the inode
1139 dno
->g
.size
= fsw_u64_le_swap(dno
->raw
->size
);
1140 // TODO: check docs for 64-bit sized files
1141 mode
= fsw_u32_le_swap(dno
->raw
->mode
);
1143 dno
->g
.type
= FSW_DNODE_TYPE_FILE
;
1144 else if (S_ISDIR(mode
))
1145 dno
->g
.type
= FSW_DNODE_TYPE_DIR
;
1146 else if (S_ISLNK(mode
))
1147 dno
->g
.type
= FSW_DNODE_TYPE_SYMLINK
;
1149 dno
->g
.type
= FSW_DNODE_TYPE_SPECIAL
;
1154 static void fsw_btrfs_dnode_free(struct fsw_volume
*volg
, struct fsw_dnode
*dnog
)
1156 struct fsw_btrfs_dnode
*dno
= (struct fsw_btrfs_dnode
*)dnog
;
1161 static fsw_status_t
fsw_btrfs_dnode_stat(struct fsw_volume
*volg
, struct fsw_dnode
*dnog
, struct fsw_dnode_stat
*sb
)
1163 struct fsw_btrfs_dnode
*dno
= (struct fsw_btrfs_dnode
*)dnog
;
1165 /* slave device got empty root */
1166 if(dno
->raw
== NULL
) {
1168 sb
->store_time_posix(sb
, FSW_DNODE_STAT_CTIME
, 0);
1169 sb
->store_time_posix(sb
, FSW_DNODE_STAT_ATIME
, 0);
1170 sb
->store_time_posix(sb
, FSW_DNODE_STAT_MTIME
, 0);
1173 sb
->used_bytes
= fsw_u64_le_swap(dno
->raw
->nbytes
);
1174 sb
->store_time_posix(sb
, FSW_DNODE_STAT_ATIME
,
1175 fsw_u64_le_swap(dno
->raw
->atime
.sec
));
1176 sb
->store_time_posix(sb
, FSW_DNODE_STAT_CTIME
,
1177 fsw_u64_le_swap(dno
->raw
->ctime
.sec
));
1178 sb
->store_time_posix(sb
, FSW_DNODE_STAT_MTIME
,
1179 fsw_u64_le_swap(dno
->raw
->mtime
.sec
));
1180 sb
->store_attr_posix(sb
, fsw_u32_le_swap(dno
->raw
->mode
));
1185 static fsw_ssize_t
grub_btrfs_lzo_decompress(char *ibuf
, fsw_size_t isize
, grub_off_t off
,
1186 char *obuf
, fsw_size_t osize
)
1188 uint32_t total_size
, cblock_size
;
1190 unsigned char buf
[GRUB_BTRFS_LZO_BLOCK_SIZE
];
1193 #define fsw_get_unaligned32(x) (*(uint32_t *)(x))
1194 total_size
= fsw_u32_le_swap (fsw_get_unaligned32(ibuf
));
1195 ibuf
+= sizeof (total_size
);
1197 if (isize
< total_size
)
1200 /* Jump forward to first block with requested data. */
1201 while (off
>= GRUB_BTRFS_LZO_BLOCK_SIZE
)
1203 /* Don't let following uint32_t cross the page boundary. */
1204 if (((ibuf
- ibuf0
) & 0xffc) == 0xffc)
1205 ibuf
= ((ibuf
- ibuf0
+ 3) & ~3) + ibuf0
;
1207 cblock_size
= fsw_u32_le_swap (fsw_get_unaligned32 (ibuf
));
1208 ibuf
+= sizeof (cblock_size
);
1210 if (cblock_size
> GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE
)
1213 off
-= GRUB_BTRFS_LZO_BLOCK_SIZE
;
1214 ibuf
+= cblock_size
;
1219 lzo_uint usize
= GRUB_BTRFS_LZO_BLOCK_SIZE
;
1221 /* Don't let following uint32_t cross the page boundary. */
1222 if (((ibuf
- ibuf0
) & 0xffc) == 0xffc)
1223 ibuf
= ((ibuf
- ibuf0
+ 3) & ~3) + ibuf0
;
1225 cblock_size
= fsw_u32_le_swap (fsw_get_unaligned32 (ibuf
));
1226 ibuf
+= sizeof (cblock_size
);
1228 if (cblock_size
> GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE
)
1231 /* Block partially filled with requested data. */
1232 if (off
> 0 || osize
< GRUB_BTRFS_LZO_BLOCK_SIZE
)
1234 fsw_size_t to_copy
= GRUB_BTRFS_LZO_BLOCK_SIZE
- off
;
1236 if (to_copy
> osize
)
1239 if (lzo1x_decompress_safe ((lzo_bytep
)ibuf
, cblock_size
, (lzo_bytep
)buf
, &usize
, NULL
) != 0)
1242 if (to_copy
> usize
)
1244 fsw_memcpy(obuf
, buf
+ off
, to_copy
);
1249 ibuf
+= cblock_size
;
1254 /* Decompress whole block directly to output buffer. */
1255 if (lzo1x_decompress_safe ((lzo_bytep
)ibuf
, cblock_size
, (lzo_bytep
)obuf
, &usize
, NULL
) != 0)
1261 ibuf
+= cblock_size
;
1267 static fsw_status_t
fsw_btrfs_get_extent(struct fsw_volume
*volg
, struct fsw_dnode
*dnog
,
1268 struct fsw_extent
*extent
)
1270 struct fsw_btrfs_volume
*vol
= (struct fsw_btrfs_volume
*)volg
;
1271 uint64_t ino
= dnog
->dnode_id
;
1272 uint64_t tree
= dnog
->tree_id
;
1273 uint64_t pos0
= extent
->log_start
<< vol
->sectorshift
;
1274 extent
->type
= FSW_EXTENT_TYPE_INVALID
;
1275 extent
->log_count
= 1;
1276 uint64_t pos
= pos0
;
1283 /* slave device got empty root */
1284 if (!vol
->is_master
)
1285 return FSW_NOT_FOUND
;
1287 if (!vol
->extent
|| vol
->extstart
> pos
|| vol
->extino
!= ino
1288 || vol
->exttree
!= tree
|| vol
->extend
<= pos
)
1290 struct btrfs_key key_in
, key_out
;
1292 fsw_size_t elemsize
;
1295 FreePool (vol
->extent
);
1298 key_in
.object_id
= ino
;
1299 key_in
.type
= GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM
;
1300 key_in
.offset
= fsw_u64_le_swap (pos
);
1301 err
= lower_bound (vol
, &key_in
, &key_out
, tree
, &elemaddr
, &elemsize
, NULL
, 0);
1303 return FSW_VOLUME_CORRUPTED
;
1304 if (key_out
.object_id
!= ino
1305 || key_out
.type
!= GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM
)
1307 return FSW_VOLUME_CORRUPTED
;
1309 if ((fsw_ssize_t
) elemsize
< ((char *) &vol
->extent
->inl
1310 - (char *) vol
->extent
))
1312 return FSW_VOLUME_CORRUPTED
;
1314 vol
->extstart
= fsw_u64_le_swap (key_out
.offset
);
1315 vol
->extsize
= elemsize
;
1316 vol
->extent
= AllocatePool (elemsize
);
1318 vol
->exttree
= tree
;
1320 return FSW_OUT_OF_MEMORY
;
1322 err
= fsw_btrfs_read_logical (vol
, elemaddr
, vol
->extent
, elemsize
, 0, 1);
1326 vol
->extend
= vol
->extstart
+ fsw_u64_le_swap (vol
->extent
->size
);
1327 if (vol
->extent
->type
== GRUB_BTRFS_EXTENT_REGULAR
1328 && (char *) &vol
->extent
+ elemsize
1329 >= (char *) &vol
->extent
->filled
+ sizeof (vol
->extent
->filled
))
1331 vol
->extstart
+ fsw_u64_le_swap (vol
->extent
->filled
);
1333 DPRINT (L
"btrfs: %lx +0x%lx\n", fsw_u64_le_swap (key_out
.offset
), fsw_u64_le_swap (vol
->extent
->size
));
1334 if (vol
->extend
<= pos
)
1336 return FSW_VOLUME_CORRUPTED
;
1340 csize
= vol
->extend
- pos
;
1341 extoff
= pos
- vol
->extstart
;
1343 if (vol
->extent
->encryption
||vol
->extent
->encoding
)
1345 return FSW_UNSUPPORTED
;
1348 switch(vol
->extent
->compression
) {
1349 case GRUB_BTRFS_COMPRESSION_LZO
:
1350 case GRUB_BTRFS_COMPRESSION_ZLIB
:
1351 case GRUB_BTRFS_COMPRESSION_NONE
:
1354 return FSW_UNSUPPORTED
;
1357 count
= ( csize
+ vol
->sectorsize
- 1) >> vol
->sectorshift
;
1358 switch (vol
->extent
->type
)
1360 case GRUB_BTRFS_EXTENT_INLINE
:
1361 buf
= AllocatePool( count
<< vol
->sectorshift
);
1363 return FSW_OUT_OF_MEMORY
;
1364 if (vol
->extent
->compression
== GRUB_BTRFS_COMPRESSION_ZLIB
)
1366 if (grub_zlib_decompress (vol
->extent
->inl
, vol
->extsize
-
1367 ((uint8_t *) vol
->extent
->inl
1368 - (uint8_t *) vol
->extent
),
1370 != (fsw_ssize_t
) csize
)
1373 return FSW_VOLUME_CORRUPTED
;
1376 else if (vol
->extent
->compression
== GRUB_BTRFS_COMPRESSION_LZO
)
1378 if (grub_btrfs_lzo_decompress(vol
->extent
->inl
, vol
->extsize
-
1379 ((uint8_t *) vol
->extent
->inl
1380 - (uint8_t *) vol
->extent
),
1382 != (fsw_ssize_t
) csize
)
1385 return -FSW_VOLUME_CORRUPTED
;
1389 fsw_memcpy (buf
, vol
->extent
->inl
+ extoff
, csize
);
1392 case GRUB_BTRFS_EXTENT_REGULAR
:
1393 if (!vol
->extent
->laddr
)
1396 if (vol
->extent
->compression
== GRUB_BTRFS_COMPRESSION_NONE
)
1400 csize
= count
<< vol
->sectorshift
;
1402 buf
= AllocatePool( count
<< vol
->sectorshift
);
1404 return FSW_OUT_OF_MEMORY
;
1405 err
= fsw_btrfs_read_logical (vol
,
1406 fsw_u64_le_swap (vol
->extent
->laddr
)
1407 + fsw_u64_le_swap (vol
->extent
->offset
)
1408 + extoff
, buf
, csize
, 0, 0);
1415 if (vol
->extent
->compression
!= GRUB_BTRFS_COMPRESSION_NONE
)
1421 zsize
= fsw_u64_le_swap (vol
->extent
->compressed_size
);
1422 tmp
= AllocatePool (zsize
);
1424 return -FSW_OUT_OF_MEMORY
;
1425 err
= fsw_btrfs_read_logical (vol
, fsw_u64_le_swap (vol
->extent
->laddr
), tmp
, zsize
, 0, 0);
1429 return -FSW_VOLUME_CORRUPTED
;
1432 buf
= AllocatePool( count
<< vol
->sectorshift
);
1435 return FSW_OUT_OF_MEMORY
;
1438 if (vol
->extent
->compression
== GRUB_BTRFS_COMPRESSION_ZLIB
)
1440 ret
= grub_zlib_decompress (tmp
, zsize
, extoff
1441 + fsw_u64_le_swap (vol
->extent
->offset
),
1444 else if (vol
->extent
->compression
== GRUB_BTRFS_COMPRESSION_LZO
)
1445 ret
= grub_btrfs_lzo_decompress (tmp
, zsize
, extoff
1446 + fsw_u64_le_swap (vol
->extent
->offset
),
1453 if (ret
!= (fsw_ssize_t
) csize
) {
1455 return -FSW_VOLUME_CORRUPTED
;
1462 return -FSW_VOLUME_CORRUPTED
;
1465 extent
->log_count
= count
;
1467 if(csize
< (count
<< vol
->sectorshift
))
1468 fsw_memzero( buf
+ csize
, (count
<< vol
->sectorshift
) - csize
);
1469 extent
->buffer
= buf
;
1470 extent
->type
= FSW_EXTENT_TYPE_BUFFER
;
1472 extent
->buffer
= NULL
;
1473 extent
->type
= FSW_EXTENT_TYPE_SPARSE
;
1478 static fsw_status_t
fsw_btrfs_readlink(struct fsw_volume
*volg
, struct fsw_dnode
*dnog
,
1479 struct fsw_string
*link_target
)
1481 struct fsw_btrfs_volume
*vol
= (struct fsw_btrfs_volume
*)volg
;
1482 struct fsw_btrfs_dnode
*dno
= (struct fsw_btrfs_dnode
*)dnog
;
1484 fsw_status_t status
;
1485 struct fsw_string s
;
1488 if (dno
->g
.size
> FSW_PATH_MAX
)
1489 return FSW_VOLUME_CORRUPTED
;
1491 tmp
= AllocatePool(dno
->g
.size
);
1493 return FSW_OUT_OF_MEMORY
;
1497 struct fsw_extent extent
;
1499 extent
.log_start
= i
;
1500 status
= fsw_btrfs_get_extent(volg
, dnog
, &extent
);
1501 if(status
|| extent
.type
!= FSW_EXTENT_TYPE_BUFFER
) {
1504 FreePool(extent
.buffer
);
1505 return FSW_VOLUME_CORRUPTED
;
1507 size
= extent
.log_count
<< vol
->sectorshift
;
1508 if(size
> (dno
->g
.size
- (i
<<vol
->sectorshift
)))
1509 size
= dno
->g
.size
- (i
<<vol
->sectorshift
);
1510 fsw_memcpy(tmp
+ (i
<<vol
->sectorshift
), extent
.buffer
, size
);
1511 FreePool(extent
.buffer
);
1512 i
+= extent
.log_count
;
1513 } while( (i
<< vol
->sectorshift
) < dno
->g
.size
);
1515 s
.type
= FSW_STRING_TYPE_UTF8
;
1516 s
.size
= s
.len
= (int)dno
->g
.size
;
1518 status
= fsw_strdup_coerce(link_target
, volg
->host_string_type
, &s
);
1524 static fsw_status_t
fsw_btrfs_lookup_dir_item(struct fsw_btrfs_volume
*vol
,
1525 uint64_t tree_id
, uint64_t object_id
,
1526 struct fsw_string
*lookup_name
,
1527 struct btrfs_dir_item
**direl_buf
,
1528 struct btrfs_dir_item
**direl_out
1532 fsw_size_t elemsize
;
1533 fsw_size_t allocated
= 0;
1534 struct btrfs_key key
;
1535 struct btrfs_key key_out
;
1536 struct btrfs_dir_item
*cdirel
;
1541 key
.object_id
= object_id
;
1542 key
.type
= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
;
1543 key
.offset
= fsw_u64_le_swap (~grub_getcrc32c (1, lookup_name
->data
, lookup_name
->size
));
1545 err
= lower_bound (vol
, &key
, &key_out
, tree_id
, &elemaddr
, &elemsize
, NULL
, 0);
1549 if (key_cmp (&key
, &key_out
) != 0)
1550 return FSW_NOT_FOUND
;
1552 if (elemsize
> allocated
)
1554 allocated
= 2 * elemsize
;
1556 FreePool (*direl_buf
);
1557 *direl_buf
= AllocatePool (allocated
+ 1);
1559 return FSW_OUT_OF_MEMORY
;
1562 err
= fsw_btrfs_read_logical (vol
, elemaddr
, *direl_buf
, elemsize
, 0, 1);
1566 for (cdirel
= *direl_buf
;
1567 (uint8_t *) cdirel
- (uint8_t *) *direl_buf
< (fsw_ssize_t
) elemsize
;
1568 cdirel
= (void *) ((uint8_t *) (*direl_buf
+ 1)
1569 + fsw_u16_le_swap (cdirel
->n
)
1570 + fsw_u16_le_swap (cdirel
->m
)))
1572 if (lookup_name
->size
== fsw_u16_le_swap (cdirel
->n
)
1573 && fsw_memeq (cdirel
->name
, lookup_name
->data
, lookup_name
->size
))
1576 if ((uint8_t *) cdirel
- (uint8_t *) *direl_buf
>= (fsw_ssize_t
) elemsize
)
1577 return FSW_NOT_FOUND
;
1579 *direl_out
= cdirel
;
1583 static fsw_status_t
fsw_btrfs_get_root_tree(
1584 struct fsw_btrfs_volume
*vol
,
1585 struct btrfs_key
*key_in
,
1589 struct btrfs_root_item ri
;
1590 struct btrfs_key key_out
;
1592 fsw_size_t elemsize
;
1594 err
= lower_bound (vol
, key_in
, &key_out
, vol
->root_tree
, &elemaddr
, &elemsize
, NULL
, 0);
1598 if (key_in
->object_id
!= key_out
.object_id
|| key_in
->type
!= key_out
.type
)
1599 return FSW_NOT_FOUND
;
1601 err
= fsw_btrfs_read_logical (vol
, elemaddr
, &ri
, sizeof (ri
), 0, 1);
1605 *tree_out
= ri
.tree
;
1609 static fsw_status_t
fsw_btrfs_get_sub_dnode(
1610 struct fsw_btrfs_volume
*vol
,
1611 struct fsw_btrfs_dnode
*dno
,
1612 struct btrfs_dir_item
*cdirel
,
1613 struct fsw_string
*name
,
1614 struct fsw_dnode
**child_dno_out
)
1618 uint64_t tree_id
= dno
->g
.tree_id
;
1621 switch (cdirel
->key
.type
)
1623 case GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM
:
1624 err
= fsw_btrfs_get_root_tree (vol
, &cdirel
->key
, &tree_id
);
1628 child_type
= GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY
;
1629 child_id
= fsw_u64_le_swap(GRUB_BTRFS_OBJECT_ID_CHUNK
);
1631 case GRUB_BTRFS_ITEM_TYPE_INODE_ITEM
:
1632 child_type
= cdirel
->type
;
1633 child_id
= cdirel
->key
.object_id
;
1637 DPRINT (L
"btrfs: unrecognised object type 0x%x", cdirel
->key
.type
);
1638 return FSW_VOLUME_CORRUPTED
;
1641 switch(child_type
) {
1642 case GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR
:
1643 child_type
= FSW_DNODE_TYPE_FILE
;
1645 case GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY
:
1646 child_type
= FSW_DNODE_TYPE_DIR
;
1648 case GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK
:
1649 child_type
= FSW_DNODE_TYPE_SYMLINK
;
1652 child_type
= FSW_DNODE_TYPE_SPECIAL
;
1655 return fsw_dnode_create_with_tree(&dno
->g
, tree_id
, child_id
, child_type
, name
, child_dno_out
);
1658 static fsw_status_t
fsw_btrfs_dir_lookup(struct fsw_volume
*volg
, struct fsw_dnode
*dnog
,
1659 struct fsw_string
*lookup_name
, struct fsw_dnode
**child_dno_out
)
1661 struct fsw_btrfs_volume
*vol
= (struct fsw_btrfs_volume
*)volg
;
1662 struct fsw_btrfs_dnode
*dno
= (struct fsw_btrfs_dnode
*)dnog
;
1664 struct fsw_string s
;
1666 *child_dno_out
= NULL
;
1668 /* slave device got empty root */
1669 if (!vol
->is_master
)
1670 return FSW_NOT_FOUND
;
1672 err
= fsw_strdup_coerce(&s
, FSW_STRING_TYPE_UTF8
, lookup_name
);
1676 /* treat '...' under root as top root */
1677 if(dnog
== volg
->root
&& s
.size
== 3 && ((char *)s
.data
)[0]=='.' && ((char *)s
.data
)[1]=='.' && ((char *)s
.data
)[2]=='.')
1680 if(dnog
->tree_id
== vol
->top_tree
) {
1681 fsw_dnode_retain(dnog
);
1682 *child_dno_out
= dnog
;
1685 return fsw_dnode_create_with_tree(dnog
,
1686 vol
->top_tree
, fsw_u64_le_swap(GRUB_BTRFS_OBJECT_ID_CHUNK
),
1687 FSW_DNODE_TYPE_DIR
, lookup_name
, child_dno_out
);
1689 struct btrfs_dir_item
*direl
=NULL
, *cdirel
;
1690 err
= fsw_btrfs_lookup_dir_item(vol
, dnog
->tree_id
, dnog
->dnode_id
, &s
, &direl
, &cdirel
);
1692 err
= fsw_btrfs_get_sub_dnode(vol
, dno
, cdirel
, lookup_name
, child_dno_out
);
1699 static fsw_status_t
fsw_btrfs_get_default_root(struct fsw_btrfs_volume
*vol
, uint64_t root_dir_objectid
)
1702 struct fsw_string s
;
1703 struct btrfs_dir_item
*direl
=NULL
, *cdirel
;
1704 uint64_t default_tree_id
= 0;
1705 struct btrfs_key top_root_key
;
1707 /* Get to top tree id */
1708 top_root_key
.object_id
= fsw_u64_le_swap(5UL);
1709 top_root_key
.type
= GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM
;
1710 top_root_key
.offset
= -1LL;
1711 err
= fsw_btrfs_get_root_tree (vol
, &top_root_key
, &vol
->top_tree
);
1715 s
.type
= FSW_STRING_TYPE_UTF8
;
1718 err
= fsw_btrfs_lookup_dir_item(vol
, vol
->root_tree
, root_dir_objectid
, &s
, &direl
, &cdirel
);
1720 /* if "default" is failed or invalid, use top tree */
1721 if (err
|| /* failed */
1722 cdirel
->type
!= GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY
|| /* not dir */
1723 cdirel
->key
.type
!= GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM
|| /* not tree */
1724 cdirel
->key
.object_id
== fsw_u64_le_swap(5UL) || /* same as top */
1725 (err
= fsw_btrfs_get_root_tree (vol
, &cdirel
->key
, &default_tree_id
)))
1726 default_tree_id
= vol
->top_tree
;
1729 err
= fsw_dnode_create_root_with_tree(&vol
->g
, default_tree_id
,
1730 fsw_u64_le_swap (GRUB_BTRFS_OBJECT_ID_CHUNK
), &vol
->g
.root
);
1736 static fsw_status_t
fsw_btrfs_dir_read(struct fsw_volume
*volg
, struct fsw_dnode
*dnog
,
1737 struct fsw_shandle
*shand
, struct fsw_dnode
**child_dno_out
)
1739 struct fsw_btrfs_volume
*vol
= (struct fsw_btrfs_volume
*)volg
;
1740 struct fsw_btrfs_dnode
*dno
= (struct fsw_btrfs_dnode
*)dnog
;
1743 struct btrfs_key key_in
, key_out
;
1745 fsw_size_t elemsize
;
1746 fsw_size_t allocated
= 0;
1747 struct btrfs_dir_item
*direl
= NULL
;
1748 struct fsw_btrfs_leaf_descriptor desc
;
1750 uint64_t tree
= dnog
->tree_id
;
1752 /* slave device got empty root */
1753 if (!vol
->is_master
)
1754 return FSW_NOT_FOUND
;
1756 key_in
.object_id
= dnog
->dnode_id
;
1757 key_in
.type
= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
;
1758 key_in
.offset
= shand
->pos
;
1760 if((int64_t)key_in
.offset
== -1LL)
1762 return FSW_NOT_FOUND
;
1765 err
= lower_bound (vol
, &key_in
, &key_out
, tree
, &elemaddr
, &elemsize
, &desc
, 0);
1770 DPRINT(L
"key_in %lx:%x:%lx out %lx:%x:%lx elem %lx+%lx\n",
1771 key_in
.object_id
, key_in
.type
, key_in
.offset
,
1772 key_out
.object_id
, key_out
.type
, key_out
.offset
,
1773 elemaddr
, elemsize
);
1774 if (key_out
.type
!= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
||
1775 key_out
.object_id
!= key_in
.object_id
)
1777 r
= next (vol
, &desc
, &elemaddr
, &elemsize
, &key_out
);
1780 DPRINT(L
"next out %lx:%x:%lx\n",
1781 key_out
.object_id
, key_out
.type
, key_out
.offset
, elemaddr
, elemsize
);
1783 if (key_out
.type
== GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
&&
1784 key_out
.object_id
== key_in
.object_id
&&
1785 fsw_u64_le_swap(key_out
.offset
) <= fsw_u64_le_swap(key_in
.offset
))
1787 r
= next (vol
, &desc
, &elemaddr
, &elemsize
, &key_out
);
1790 DPRINT(L
"next out %lx:%x:%lx\n",
1791 key_out
.object_id
, key_out
.type
, key_out
.offset
, elemaddr
, elemsize
);
1796 struct btrfs_dir_item
*cdirel
;
1797 if (key_out
.type
!= GRUB_BTRFS_ITEM_TYPE_DIR_ITEM
||
1798 key_out
.object_id
!= key_in
.object_id
)
1803 if (elemsize
> allocated
)
1805 allocated
= 2 * elemsize
;
1808 direl
= AllocatePool (allocated
+ 1);
1811 r
= -FSW_OUT_OF_MEMORY
;
1816 err
= fsw_btrfs_read_logical (vol
, elemaddr
, direl
, elemsize
, 0, 1);
1823 for (cdirel
= direl
;
1824 (uint8_t *) cdirel
- (uint8_t *) direl
1825 < (fsw_ssize_t
) elemsize
;
1826 cdirel
= (void *) ((uint8_t *) (direl
+ 1)
1827 + fsw_u16_le_swap (cdirel
->n
)
1828 + fsw_u16_le_swap (cdirel
->m
)))
1830 struct fsw_string s
;
1831 s
.type
= FSW_STRING_TYPE_UTF8
;
1832 s
.size
= s
.len
= fsw_u16_le_swap (cdirel
->n
);
1833 s
.data
= cdirel
->name
;
1834 DPRINT(L
"item key %lx:%x%lx, type %lx, namelen=%lx\n",
1835 cdirel
->key
.object_id
, cdirel
->key
.type
, cdirel
->key
.offset
, cdirel
->type
, s
.size
);
1837 err
= fsw_btrfs_get_sub_dnode(vol
, dno
, cdirel
, &s
, child_dno_out
);
1840 free_iterator (&desc
);
1841 shand
->pos
= key_out
.offset
;
1845 r
= next (vol
, &desc
, &elemaddr
, &elemsize
, &key_out
);
1846 DPRINT(L
"next2 out %lx:%x:%lx\n",
1847 key_out
.object_id
, key_out
.type
, key_out
.offset
, elemaddr
, elemsize
);
1854 free_iterator (&desc
);
1856 r
= r
< 0 ? -r
: FSW_NOT_FOUND
;
1864 struct fsw_fstype_table
FSW_FSTYPE_TABLE_NAME(btrfs
) = {
1865 { FSW_STRING_TYPE_UTF8
, 5, 5, "btrfs" },
1866 sizeof(struct fsw_btrfs_volume
),
1867 sizeof(struct fsw_btrfs_dnode
),
1869 fsw_btrfs_volume_mount
,
1870 fsw_btrfs_volume_free
,
1871 fsw_btrfs_volume_stat
,
1872 fsw_btrfs_dnode_fill
,
1873 fsw_btrfs_dnode_free
,
1874 fsw_btrfs_dnode_stat
,
1875 fsw_btrfs_get_extent
,
1876 fsw_btrfs_dir_lookup
,