/* btrfs.c - B-tree file system. */ /* * GRUB -- GRand Unified Bootloader * Copyright (C) 2010,2011,2012,2013 Free Software Foundation, Inc. * * GRUB is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * GRUB is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with GRUB. If not, see . */ /* * Tell zstd to expose functions that aren't part of the stable API, which * aren't safe to use when linking against a dynamic library. We vendor in a * specific zstd version, so we know what we're getting. We need these unstable * functions to provide our own allocator, which uses grub_malloc(), to zstd. */ #define ZSTD_STATIC_LINKING_ONLY #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include GRUB_MOD_LICENSE ("GPLv3+"); #define GRUB_BTRFS_SIGNATURE "_BHRfS_M" /* From http://www.oberhumer.com/opensource/lzo/lzofaq.php * LZO will expand incompressible data by a little amount. I still haven't * computed the exact values, but I suggest using these formulas for * a worst-case expansion calculation: * * output_block_size = input_block_size + (input_block_size / 16) + 64 + 3 * */ #define GRUB_BTRFS_LZO_BLOCK_SIZE 4096 #define GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE (GRUB_BTRFS_LZO_BLOCK_SIZE + \ (GRUB_BTRFS_LZO_BLOCK_SIZE / 16) + 64 + 3) #define ZSTD_BTRFS_MAX_WINDOWLOG 17 #define ZSTD_BTRFS_MAX_INPUT (1 << ZSTD_BTRFS_MAX_WINDOWLOG) typedef grub_uint8_t grub_btrfs_checksum_t[0x20]; typedef grub_uint16_t grub_btrfs_uuid_t[8]; struct grub_btrfs_device { grub_uint64_t device_id; grub_uint64_t size; grub_uint8_t dummy[0x62 - 0x10]; } GRUB_PACKED; struct grub_btrfs_superblock { grub_btrfs_checksum_t checksum; grub_btrfs_uuid_t uuid; grub_uint8_t dummy[0x10]; grub_uint8_t signature[sizeof (GRUB_BTRFS_SIGNATURE) - 1]; grub_uint64_t generation; grub_uint64_t root_tree; grub_uint64_t chunk_tree; grub_uint8_t dummy2[0x20]; grub_uint64_t root_dir_objectid; grub_uint8_t dummy3[0x41]; struct grub_btrfs_device this_device; char label[0x100]; grub_uint8_t dummy4[0x100]; grub_uint8_t bootstrap_mapping[0x800]; } GRUB_PACKED; struct btrfs_header { grub_btrfs_checksum_t checksum; grub_btrfs_uuid_t uuid; grub_uint64_t bytenr; grub_uint8_t dummy[0x28]; grub_uint32_t nitems; grub_uint8_t level; } GRUB_PACKED; struct grub_btrfs_device_desc { grub_device_t dev; grub_uint64_t id; }; struct grub_btrfs_data { struct grub_btrfs_superblock sblock; grub_uint64_t tree; grub_uint64_t inode; struct grub_btrfs_device_desc *devices_attached; unsigned n_devices_attached; unsigned n_devices_allocated; /* Cached extent data. */ grub_uint64_t extstart; grub_uint64_t extend; grub_uint64_t extino; grub_uint64_t exttree; grub_size_t extsize; struct grub_btrfs_extent_data *extent; }; struct grub_btrfs_chunk_item { grub_uint64_t size; grub_uint64_t dummy; grub_uint64_t stripe_length; grub_uint64_t type; #define GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE 0x07 #define GRUB_BTRFS_CHUNK_TYPE_SINGLE 0x00 #define GRUB_BTRFS_CHUNK_TYPE_RAID0 0x08 #define GRUB_BTRFS_CHUNK_TYPE_RAID1 0x10 #define GRUB_BTRFS_CHUNK_TYPE_DUPLICATED 0x20 #define GRUB_BTRFS_CHUNK_TYPE_RAID10 0x40 #define GRUB_BTRFS_CHUNK_TYPE_RAID5 0x80 #define GRUB_BTRFS_CHUNK_TYPE_RAID6 0x100 #define GRUB_BTRFS_CHUNK_TYPE_RAID1C3 0x200 #define GRUB_BTRFS_CHUNK_TYPE_RAID1C4 0x400 grub_uint8_t dummy2[0xc]; grub_uint16_t nstripes; grub_uint16_t nsubstripes; } GRUB_PACKED; struct grub_btrfs_chunk_stripe { grub_uint64_t device_id; grub_uint64_t offset; grub_btrfs_uuid_t device_uuid; } GRUB_PACKED; struct grub_btrfs_leaf_node { struct grub_btrfs_key key; grub_uint32_t offset; grub_uint32_t size; } GRUB_PACKED; struct grub_btrfs_internal_node { struct grub_btrfs_key key; grub_uint64_t addr; grub_uint64_t dummy; } GRUB_PACKED; struct grub_btrfs_dir_item { struct grub_btrfs_key key; grub_uint8_t dummy[8]; grub_uint16_t m; grub_uint16_t n; #define GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR 1 #define GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY 2 #define GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK 7 grub_uint8_t type; char name[0]; } GRUB_PACKED; struct grub_btrfs_leaf_descriptor { unsigned depth; unsigned allocated; struct { grub_disk_addr_t addr; unsigned iter; unsigned maxiter; int leaf; } *data; }; struct grub_btrfs_time { grub_int64_t sec; grub_uint32_t nanosec; } GRUB_PACKED; struct grub_btrfs_inode { grub_uint8_t dummy1[0x10]; grub_uint64_t size; grub_uint8_t dummy2[0x70]; struct grub_btrfs_time mtime; } GRUB_PACKED; struct grub_btrfs_extent_data { grub_uint64_t dummy; grub_uint64_t size; grub_uint8_t compression; grub_uint8_t encryption; grub_uint16_t encoding; grub_uint8_t type; union { char inl[0]; struct { grub_uint64_t laddr; grub_uint64_t compressed_size; grub_uint64_t offset; grub_uint64_t filled; }; }; } GRUB_PACKED; #define GRUB_BTRFS_EXTENT_INLINE 0 #define GRUB_BTRFS_EXTENT_REGULAR 1 #define GRUB_BTRFS_COMPRESSION_NONE 0 #define GRUB_BTRFS_COMPRESSION_ZLIB 1 #define GRUB_BTRFS_COMPRESSION_LZO 2 #define GRUB_BTRFS_COMPRESSION_ZSTD 3 #define GRUB_BTRFS_OBJECT_ID_CHUNK 0x100 static grub_disk_addr_t superblock_sectors[] = { 64 * 2, 64 * 1024 * 2, 256 * 1048576 * 2, 1048576ULL * 1048576ULL * 2 }; static grub_err_t grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr, void *buf, grub_size_t size, int recursion_depth); static grub_err_t read_sblock (grub_disk_t disk, struct grub_btrfs_superblock *sb) { struct grub_btrfs_superblock sblock; unsigned i; grub_err_t err = GRUB_ERR_NONE; for (i = 0; i < ARRAY_SIZE (superblock_sectors); i++) { /* Don't try additional superblocks beyond device size. */ if (i && (grub_le_to_cpu64 (sblock.this_device.size) >> GRUB_DISK_SECTOR_BITS) <= superblock_sectors[i]) break; err = grub_disk_read (disk, superblock_sectors[i], 0, sizeof (sblock), &sblock); if (err == GRUB_ERR_OUT_OF_RANGE) break; if (grub_memcmp ((char *) sblock.signature, GRUB_BTRFS_SIGNATURE, sizeof (GRUB_BTRFS_SIGNATURE) - 1) != 0) break; if (i == 0 || grub_le_to_cpu64 (sblock.generation) > grub_le_to_cpu64 (sb->generation)) grub_memcpy (sb, &sblock, sizeof (sblock)); } if ((err == GRUB_ERR_OUT_OF_RANGE || !err) && i == 0) return grub_error (GRUB_ERR_BAD_FS, "not a Btrfs filesystem"); if (err == GRUB_ERR_OUT_OF_RANGE) grub_errno = err = GRUB_ERR_NONE; return err; } static int key_cmp (const struct grub_btrfs_key *a, const struct grub_btrfs_key *b) { if (grub_le_to_cpu64 (a->object_id) < grub_le_to_cpu64 (b->object_id)) return -1; if (grub_le_to_cpu64 (a->object_id) > grub_le_to_cpu64 (b->object_id)) return +1; if (a->type < b->type) return -1; if (a->type > b->type) return +1; if (grub_le_to_cpu64 (a->offset) < grub_le_to_cpu64 (b->offset)) return -1; if (grub_le_to_cpu64 (a->offset) > grub_le_to_cpu64 (b->offset)) return +1; return 0; } static void free_iterator (struct grub_btrfs_leaf_descriptor *desc) { grub_free (desc->data); } static grub_err_t check_btrfs_header (struct grub_btrfs_data *data, struct btrfs_header *header, grub_disk_addr_t addr) { if (grub_le_to_cpu64 (header->bytenr) != addr) { grub_dprintf ("btrfs", "btrfs_header.bytenr is not equal node addr\n"); return grub_error (GRUB_ERR_BAD_FS, "header bytenr is not equal node addr"); } if (grub_memcmp (data->sblock.uuid, header->uuid, sizeof(grub_btrfs_uuid_t))) { grub_dprintf ("btrfs", "btrfs_header.uuid doesn't match sblock uuid\n"); return grub_error (GRUB_ERR_BAD_FS, "header uuid doesn't match sblock uuid"); } return GRUB_ERR_NONE; } static grub_err_t save_ref (struct grub_btrfs_leaf_descriptor *desc, grub_disk_addr_t addr, unsigned i, unsigned m, int l) { desc->depth++; if (desc->allocated < desc->depth) { void *newdata; grub_size_t sz; if (grub_mul (desc->allocated, 2, &desc->allocated) || grub_mul (desc->allocated, sizeof (desc->data[0]), &sz)) return GRUB_ERR_OUT_OF_RANGE; newdata = grub_realloc (desc->data, sz); if (!newdata) return grub_errno; desc->data = newdata; } desc->data[desc->depth - 1].addr = addr; desc->data[desc->depth - 1].iter = i; desc->data[desc->depth - 1].maxiter = m; desc->data[desc->depth - 1].leaf = l; return GRUB_ERR_NONE; } static int next (struct grub_btrfs_data *data, struct grub_btrfs_leaf_descriptor *desc, grub_disk_addr_t * outaddr, grub_size_t * outsize, struct grub_btrfs_key *key_out) { grub_err_t err; struct grub_btrfs_leaf_node leaf; for (; desc->depth > 0; desc->depth--) { desc->data[desc->depth - 1].iter++; if (desc->data[desc->depth - 1].iter < desc->data[desc->depth - 1].maxiter) break; } if (desc->depth == 0) return 0; while (!desc->data[desc->depth - 1].leaf) { struct grub_btrfs_internal_node node; struct btrfs_header head; err = grub_btrfs_read_logical (data, desc->data[desc->depth - 1].iter * sizeof (node) + sizeof (struct btrfs_header) + desc->data[desc->depth - 1].addr, &node, sizeof (node), 0); if (err) return -err; err = grub_btrfs_read_logical (data, grub_le_to_cpu64 (node.addr), &head, sizeof (head), 0); if (err) return -err; check_btrfs_header (data, &head, grub_le_to_cpu64 (node.addr)); save_ref (desc, grub_le_to_cpu64 (node.addr), 0, grub_le_to_cpu32 (head.nitems), !head.level); } err = grub_btrfs_read_logical (data, desc->data[desc->depth - 1].iter * sizeof (leaf) + sizeof (struct btrfs_header) + desc->data[desc->depth - 1].addr, &leaf, sizeof (leaf), 0); if (err) return -err; *outsize = grub_le_to_cpu32 (leaf.size); *outaddr = desc->data[desc->depth - 1].addr + sizeof (struct btrfs_header) + grub_le_to_cpu32 (leaf.offset); *key_out = leaf.key; return 1; } static grub_err_t lower_bound (struct grub_btrfs_data *data, const struct grub_btrfs_key *key_in, struct grub_btrfs_key *key_out, grub_uint64_t root, grub_disk_addr_t *outaddr, grub_size_t *outsize, struct grub_btrfs_leaf_descriptor *desc, int recursion_depth) { grub_disk_addr_t addr = grub_le_to_cpu64 (root); int depth = -1; if (desc) { desc->allocated = 16; desc->depth = 0; desc->data = grub_calloc (desc->allocated, sizeof (desc->data[0])); if (!desc->data) return grub_errno; } /* > 2 would work as well but be robust and allow a bit more just in case. */ if (recursion_depth > 10) return grub_error (GRUB_ERR_BAD_FS, "too deep btrfs virtual nesting"); grub_dprintf ("btrfs", "retrieving %" PRIxGRUB_UINT64_T " %x %" PRIxGRUB_UINT64_T "\n", key_in->object_id, key_in->type, key_in->offset); while (1) { grub_err_t err; struct btrfs_header head; reiter: depth++; /* FIXME: preread few nodes into buffer. */ err = grub_btrfs_read_logical (data, addr, &head, sizeof (head), recursion_depth + 1); if (err) return err; check_btrfs_header (data, &head, addr); addr += sizeof (head); if (head.level) { unsigned i; struct grub_btrfs_internal_node node, node_last; int have_last = 0; grub_memset (&node_last, 0, sizeof (node_last)); for (i = 0; i < grub_le_to_cpu32 (head.nitems); i++) { err = grub_btrfs_read_logical (data, addr + i * sizeof (node), &node, sizeof (node), recursion_depth + 1); if (err) return err; grub_dprintf ("btrfs", "internal node (depth %d) %" PRIxGRUB_UINT64_T " %x %" PRIxGRUB_UINT64_T "\n", depth, node.key.object_id, node.key.type, node.key.offset); if (key_cmp (&node.key, key_in) == 0) { err = GRUB_ERR_NONE; if (desc) err = save_ref (desc, addr - sizeof (head), i, grub_le_to_cpu32 (head.nitems), 0); if (err) return err; addr = grub_le_to_cpu64 (node.addr); goto reiter; } if (key_cmp (&node.key, key_in) > 0) break; node_last = node; have_last = 1; } if (have_last) { err = GRUB_ERR_NONE; if (desc) err = save_ref (desc, addr - sizeof (head), i - 1, grub_le_to_cpu32 (head.nitems), 0); if (err) return err; addr = grub_le_to_cpu64 (node_last.addr); goto reiter; } *outsize = 0; *outaddr = 0; grub_memset (key_out, 0, sizeof (*key_out)); if (desc) return save_ref (desc, addr - sizeof (head), -1, grub_le_to_cpu32 (head.nitems), 0); return GRUB_ERR_NONE; } { unsigned i; struct grub_btrfs_leaf_node leaf, leaf_last; int have_last = 0; for (i = 0; i < grub_le_to_cpu32 (head.nitems); i++) { err = grub_btrfs_read_logical (data, addr + i * sizeof (leaf), &leaf, sizeof (leaf), recursion_depth + 1); if (err) return err; grub_dprintf ("btrfs", "leaf (depth %d) %" PRIxGRUB_UINT64_T " %x %" PRIxGRUB_UINT64_T "\n", depth, leaf.key.object_id, leaf.key.type, leaf.key.offset); if (key_cmp (&leaf.key, key_in) == 0) { grub_memcpy (key_out, &leaf.key, sizeof (*key_out)); *outsize = grub_le_to_cpu32 (leaf.size); *outaddr = addr + grub_le_to_cpu32 (leaf.offset); if (desc) return save_ref (desc, addr - sizeof (head), i, grub_le_to_cpu32 (head.nitems), 1); return GRUB_ERR_NONE; } if (key_cmp (&leaf.key, key_in) > 0) break; have_last = 1; leaf_last = leaf; } if (have_last) { grub_memcpy (key_out, &leaf_last.key, sizeof (*key_out)); *outsize = grub_le_to_cpu32 (leaf_last.size); *outaddr = addr + grub_le_to_cpu32 (leaf_last.offset); if (desc) return save_ref (desc, addr - sizeof (head), i - 1, grub_le_to_cpu32 (head.nitems), 1); return GRUB_ERR_NONE; } *outsize = 0; *outaddr = 0; grub_memset (key_out, 0, sizeof (*key_out)); if (desc) return save_ref (desc, addr - sizeof (head), -1, grub_le_to_cpu32 (head.nitems), 1); return GRUB_ERR_NONE; } } } /* Context for find_device. */ struct find_device_ctx { struct grub_btrfs_data *data; grub_uint64_t id; grub_device_t dev_found; }; /* Helper for find_device. */ static int find_device_iter (const char *name, void *data) { struct find_device_ctx *ctx = data; grub_device_t dev; grub_err_t err; struct grub_btrfs_superblock sb; dev = grub_device_open (name); if (!dev) return 0; if (!dev->disk) { grub_device_close (dev); return 0; } err = read_sblock (dev->disk, &sb); if (err == GRUB_ERR_BAD_FS) { grub_device_close (dev); grub_errno = GRUB_ERR_NONE; return 0; } if (err) { grub_device_close (dev); grub_print_error (); return 0; } if (grub_memcmp (ctx->data->sblock.uuid, sb.uuid, sizeof (sb.uuid)) != 0 || sb.this_device.device_id != ctx->id) { grub_device_close (dev); return 0; } ctx->dev_found = dev; return 1; } static grub_device_t find_device (struct grub_btrfs_data *data, grub_uint64_t id) { struct find_device_ctx ctx = { .data = data, .id = id, .dev_found = NULL }; unsigned i; for (i = 0; i < data->n_devices_attached; i++) if (id == data->devices_attached[i].id) return data->devices_attached[i].dev; grub_device_iterate (find_device_iter, &ctx); data->n_devices_attached++; if (data->n_devices_attached > data->n_devices_allocated) { void *tmp; grub_size_t sz; if (grub_mul (data->n_devices_attached, 2, &data->n_devices_allocated) || grub_add (data->n_devices_allocated, 1, &data->n_devices_allocated) || grub_mul (data->n_devices_allocated, sizeof (data->devices_attached[0]), &sz)) goto fail; data->devices_attached = grub_realloc (tmp = data->devices_attached, sz); if (!data->devices_attached) { data->devices_attached = tmp; fail: if (ctx.dev_found) grub_device_close (ctx.dev_found); return NULL; } } data->devices_attached[data->n_devices_attached - 1].id = id; data->devices_attached[data->n_devices_attached - 1].dev = ctx.dev_found; return ctx.dev_found; } static grub_err_t btrfs_read_from_chunk (struct grub_btrfs_data *data, struct grub_btrfs_chunk_item *chunk, grub_uint64_t stripen, grub_uint64_t stripe_offset, int redundancy, grub_uint64_t csize, void *buf) { struct grub_btrfs_chunk_stripe *stripe; grub_disk_addr_t paddr; grub_device_t dev; grub_err_t err; stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1); /* Right now the redundancy handling is easy. With RAID5-like it will be more difficult. */ stripe += stripen + redundancy; paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset; grub_dprintf ("btrfs", "stripe %" PRIxGRUB_UINT64_T " maps to 0x%" PRIxGRUB_UINT64_T "\n" "reading paddr 0x%" PRIxGRUB_UINT64_T "\n", stripen, stripe->offset, paddr); dev = find_device (data, stripe->device_id); if (!dev) { grub_dprintf ("btrfs", "couldn't find a necessary member device " "of multi-device filesystem\n"); grub_errno = GRUB_ERR_NONE; return GRUB_ERR_READ_ERROR; } err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS, paddr & (GRUB_DISK_SECTOR_SIZE - 1), csize, buf); return err; } struct raid56_buffer { void *buf; int data_is_valid; }; static void rebuild_raid5 (char *dest, struct raid56_buffer *buffers, grub_uint64_t nstripes, grub_uint64_t csize) { grub_uint64_t i; int first; for(i = 0; buffers[i].data_is_valid && i < nstripes; i++); if (i == nstripes) { grub_dprintf ("btrfs", "called rebuild_raid5(), but all disks are OK\n"); return; } grub_dprintf ("btrfs", "rebuilding RAID 5 stripe #%" PRIuGRUB_UINT64_T "\n", i); for (i = 0, first = 1; i < nstripes; i++) { if (!buffers[i].data_is_valid) continue; if (first) { grub_memcpy(dest, buffers[i].buf, csize); first = 0; } else grub_crypto_xor (dest, dest, buffers[i].buf, csize); } } static grub_err_t raid6_recover_read_buffer (void *data, int disk_nr, grub_uint64_t addr __attribute__ ((unused)), void *dest, grub_size_t size) { struct raid56_buffer *buffers = data; if (!buffers[disk_nr].data_is_valid) return grub_errno = GRUB_ERR_READ_ERROR; grub_memcpy(dest, buffers[disk_nr].buf, size); return grub_errno = GRUB_ERR_NONE; } static void rebuild_raid6 (struct raid56_buffer *buffers, grub_uint64_t nstripes, grub_uint64_t csize, grub_uint64_t parities_pos, void *dest, grub_uint64_t stripen) { grub_raid6_recover_gen (buffers, nstripes, stripen, parities_pos, dest, 0, csize, 0, raid6_recover_read_buffer); } static grub_err_t raid56_read_retry (struct grub_btrfs_data *data, struct grub_btrfs_chunk_item *chunk, grub_uint64_t stripe_offset, grub_uint64_t stripen, grub_uint64_t csize, void *buf, grub_uint64_t parities_pos) { struct raid56_buffer *buffers; grub_uint64_t nstripes = grub_le_to_cpu16 (chunk->nstripes); grub_uint64_t chunk_type = grub_le_to_cpu64 (chunk->type); grub_err_t ret = GRUB_ERR_OUT_OF_MEMORY; grub_uint64_t i, failed_devices; buffers = grub_calloc (nstripes, sizeof (*buffers)); if (!buffers) goto cleanup; for (i = 0; i < nstripes; i++) { buffers[i].buf = grub_zalloc (csize); if (!buffers[i].buf) goto cleanup; } for (failed_devices = 0, i = 0; i < nstripes; i++) { struct grub_btrfs_chunk_stripe *stripe; grub_disk_addr_t paddr; grub_device_t dev; grub_err_t err; /* * The struct grub_btrfs_chunk_stripe array lives * behind struct grub_btrfs_chunk_item. */ stripe = (struct grub_btrfs_chunk_stripe *) (chunk + 1) + i; paddr = grub_le_to_cpu64 (stripe->offset) + stripe_offset; grub_dprintf ("btrfs", "reading paddr %" PRIxGRUB_UINT64_T " from stripe ID %" PRIxGRUB_UINT64_T "\n", paddr, stripe->device_id); dev = find_device (data, stripe->device_id); if (!dev) { grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " FAILED (dev ID %" PRIxGRUB_UINT64_T ")\n", i, stripe->device_id); failed_devices++; continue; } err = grub_disk_read (dev->disk, paddr >> GRUB_DISK_SECTOR_BITS, paddr & (GRUB_DISK_SECTOR_SIZE - 1), csize, buffers[i].buf); if (err == GRUB_ERR_NONE) { buffers[i].data_is_valid = 1; grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " OK (dev ID %" PRIxGRUB_UINT64_T ")\n", i, stripe->device_id); } else { grub_dprintf ("btrfs", "stripe %" PRIuGRUB_UINT64_T " READ FAILED (dev ID %" PRIxGRUB_UINT64_T ")\n", i, stripe->device_id); failed_devices++; } } if (failed_devices > 1 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5)) { grub_dprintf ("btrfs", "not enough disks for RAID 5: total %" PRIuGRUB_UINT64_T ", missing %" PRIuGRUB_UINT64_T "\n", nstripes, failed_devices); ret = GRUB_ERR_READ_ERROR; goto cleanup; } else if (failed_devices > 2 && (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID6)) { grub_dprintf ("btrfs", "not enough disks for RAID 6: total %" PRIuGRUB_UINT64_T ", missing %" PRIuGRUB_UINT64_T "\n", nstripes, failed_devices); ret = GRUB_ERR_READ_ERROR; goto cleanup; } else grub_dprintf ("btrfs", "enough disks for RAID 5: total %" PRIuGRUB_UINT64_T ", missing %" PRIuGRUB_UINT64_T "\n", nstripes, failed_devices); /* We have enough disks. So, rebuild the data. */ if (chunk_type & GRUB_BTRFS_CHUNK_TYPE_RAID5) rebuild_raid5 (buf, buffers, nstripes, csize); else rebuild_raid6 (buffers, nstripes, csize, parities_pos, buf, stripen); ret = GRUB_ERR_NONE; cleanup: if (buffers) for (i = 0; i < nstripes; i++) grub_free (buffers[i].buf); grub_free (buffers); return ret; } static grub_err_t grub_btrfs_read_logical (struct grub_btrfs_data *data, grub_disk_addr_t addr, void *buf, grub_size_t size, int recursion_depth) { while (size > 0) { grub_uint8_t *ptr; struct grub_btrfs_key *key; struct grub_btrfs_chunk_item *chunk; grub_uint64_t csize; grub_err_t err = 0; struct grub_btrfs_key key_out; int challoc = 0; struct grub_btrfs_key key_in; grub_size_t chsize; grub_disk_addr_t chaddr; grub_dprintf ("btrfs", "searching for laddr %" PRIxGRUB_UINT64_T "\n", addr); for (ptr = data->sblock.bootstrap_mapping; ptr < data->sblock.bootstrap_mapping + sizeof (data->sblock.bootstrap_mapping) - sizeof (struct grub_btrfs_key);) { key = (struct grub_btrfs_key *) ptr; if (key->type != GRUB_BTRFS_ITEM_TYPE_CHUNK) break; chunk = (struct grub_btrfs_chunk_item *) (key + 1); grub_dprintf ("btrfs", "%" PRIxGRUB_UINT64_T " %" PRIxGRUB_UINT64_T " \n", grub_le_to_cpu64 (key->offset), grub_le_to_cpu64 (chunk->size)); if (grub_le_to_cpu64 (key->offset) <= addr && addr < grub_le_to_cpu64 (key->offset) + grub_le_to_cpu64 (chunk->size)) goto chunk_found; ptr += sizeof (*key) + sizeof (*chunk) + sizeof (struct grub_btrfs_chunk_stripe) * grub_le_to_cpu16 (chunk->nstripes); } key_in.object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_OBJECT_ID_CHUNK); key_in.type = GRUB_BTRFS_ITEM_TYPE_CHUNK; key_in.offset = grub_cpu_to_le64 (addr); err = lower_bound (data, &key_in, &key_out, data->sblock.chunk_tree, &chaddr, &chsize, NULL, recursion_depth); if (err) return err; key = &key_out; if (key->type != GRUB_BTRFS_ITEM_TYPE_CHUNK || !(grub_le_to_cpu64 (key->offset) <= addr)) return grub_error (GRUB_ERR_BAD_FS, "couldn't find the chunk descriptor"); chunk = grub_malloc (chsize); if (!chunk) return grub_errno; challoc = 1; err = grub_btrfs_read_logical (data, chaddr, chunk, chsize, recursion_depth); if (err) { grub_free (chunk); return err; } chunk_found: { grub_uint64_t stripen; grub_uint64_t stripe_offset; grub_uint64_t off = addr - grub_le_to_cpu64 (key->offset); grub_uint64_t chunk_stripe_length; grub_uint16_t nstripes; unsigned redundancy = 1; unsigned i, j; int is_raid56; grub_uint64_t parities_pos = 0; is_raid56 = !!(grub_le_to_cpu64 (chunk->type) & (GRUB_BTRFS_CHUNK_TYPE_RAID5 | GRUB_BTRFS_CHUNK_TYPE_RAID6)); if (grub_le_to_cpu64 (chunk->size) <= off) { grub_dprintf ("btrfs", "no chunk\n"); return grub_error (GRUB_ERR_BAD_FS, "couldn't find the chunk descriptor"); } nstripes = grub_le_to_cpu16 (chunk->nstripes) ? : 1; chunk_stripe_length = grub_le_to_cpu64 (chunk->stripe_length) ? : 512; grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T "+0x%" PRIxGRUB_UINT64_T " (%d stripes (%d substripes) of %" PRIxGRUB_UINT64_T ")\n", grub_le_to_cpu64 (key->offset), grub_le_to_cpu64 (chunk->size), nstripes, grub_le_to_cpu16 (chunk->nsubstripes), chunk_stripe_length); switch (grub_le_to_cpu64 (chunk->type) & ~GRUB_BTRFS_CHUNK_TYPE_BITS_DONTCARE) { case GRUB_BTRFS_CHUNK_TYPE_SINGLE: { grub_uint64_t stripe_length; grub_dprintf ("btrfs", "single\n"); stripe_length = grub_divmod64 (grub_le_to_cpu64 (chunk->size), nstripes, NULL); if (stripe_length == 0) stripe_length = 512; stripen = grub_divmod64 (off, stripe_length, &stripe_offset); csize = (stripen + 1) * stripe_length - off; break; } case GRUB_BTRFS_CHUNK_TYPE_RAID1C4: redundancy++; /* fall through */ case GRUB_BTRFS_CHUNK_TYPE_RAID1C3: redundancy++; /* fall through */ case GRUB_BTRFS_CHUNK_TYPE_DUPLICATED: case GRUB_BTRFS_CHUNK_TYPE_RAID1: { grub_dprintf ("btrfs", "RAID1 (copies: %d)\n", ++redundancy); stripen = 0; stripe_offset = off; csize = grub_le_to_cpu64 (chunk->size) - off; break; } case GRUB_BTRFS_CHUNK_TYPE_RAID0: { grub_uint64_t middle, high; grub_uint64_t low; grub_dprintf ("btrfs", "RAID0\n"); middle = grub_divmod64 (off, chunk_stripe_length, &low); high = grub_divmod64 (middle, nstripes, &stripen); stripe_offset = low + chunk_stripe_length * high; csize = chunk_stripe_length - low; break; } case GRUB_BTRFS_CHUNK_TYPE_RAID10: { grub_uint64_t middle, high; grub_uint64_t low; grub_uint16_t nsubstripes; nsubstripes = grub_le_to_cpu16 (chunk->nsubstripes) ? : 1; middle = grub_divmod64 (off, chunk_stripe_length, &low); high = grub_divmod64 (middle, nstripes / nsubstripes ? : 1, &stripen); stripen *= nsubstripes; redundancy = nsubstripes; stripe_offset = low + chunk_stripe_length * high; csize = chunk_stripe_length - low; break; } case GRUB_BTRFS_CHUNK_TYPE_RAID5: case GRUB_BTRFS_CHUNK_TYPE_RAID6: { grub_uint64_t nparities, stripe_nr, high, low; redundancy = 1; /* no redundancy for now */ if (grub_le_to_cpu64 (chunk->type) & GRUB_BTRFS_CHUNK_TYPE_RAID5) { grub_dprintf ("btrfs", "RAID5\n"); nparities = 1; } else { grub_dprintf ("btrfs", "RAID6\n"); nparities = 2; } /* * RAID 6 layout consists of several stripes spread over * the disks, e.g.: * * Disk_0 Disk_1 Disk_2 Disk_3 * A0 B0 P0 Q0 * Q1 A1 B1 P1 * P2 Q2 A2 B2 * * Note: placement of the parities depend on row number. * * Pay attention that the btrfs terminology may differ from * terminology used in other RAID implementations, e.g. LVM, * dm or md. The main difference is that btrfs calls contiguous * block of data on a given disk, e.g. A0, stripe instead of chunk. * * The variables listed below have following meaning: * - stripe_nr is the stripe number excluding the parities * (A0 = 0, B0 = 1, A1 = 2, B1 = 3, etc.), * - high is the row number (0 for A0...Q0, 1 for Q1...P1, etc.), * - stripen is the disk number in a row (0 for A0, Q1, P2, * 1 for B0, A1, Q2, etc.), * - off is the logical address to read, * - chunk_stripe_length is the size of a stripe (typically 64 KiB), * - nstripes is the number of disks in a row, * - low is the offset of the data inside a stripe, * - stripe_offset is the data offset in an array, * - csize is the "potential" data to read; it will be reduced * to size if the latter is smaller, * - nparities is the number of parities (1 for RAID 5, 2 for * RAID 6); used only in RAID 5/6 code. */ stripe_nr = grub_divmod64 (off, chunk_stripe_length, &low); /* * stripen is computed without the parities * (0 for A0, A1, A2, 1 for B0, B1, B2, etc.). */ if (nparities >= nstripes) return grub_error (GRUB_ERR_BAD_FS, "invalid RAID5/6: nparities >= nstripes"); high = grub_divmod64 (stripe_nr, nstripes - nparities, &stripen); /* * The stripes are spread over the disks. Every each row their * positions are shifted by 1 place. So, the real disks number * change. Hence, we have to take into account current row number * modulo nstripes (0 for A0, 1 for A1, 2 for A2, etc.). */ grub_divmod64 (high + stripen, nstripes, &stripen); /* * parities_pos is equal to ((high - nparities) % nstripes) * (see the diagram above). However, (high - nparities) can * be negative, e.g. when high == 0, leading to an incorrect * results. (high + nstripes - nparities) is always positive and * modulo nstripes is equal to ((high - nparities) % nstripes). */ grub_divmod64 (high + nstripes - nparities, nstripes, &parities_pos); stripe_offset = chunk_stripe_length * high + low; csize = chunk_stripe_length - low; break; } default: grub_dprintf ("btrfs", "unsupported RAID\n"); return grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET, "unsupported RAID flags %" PRIxGRUB_UINT64_T, grub_le_to_cpu64 (chunk->type)); } if (csize == 0) return grub_error (GRUB_ERR_BUG, "couldn't find the chunk descriptor"); if (csize > (grub_uint64_t) size) csize = size; for (j = 0; j < 2; j++) { grub_dprintf ("btrfs", "chunk 0x%" PRIxGRUB_UINT64_T "+0x%" PRIxGRUB_UINT64_T " (%d stripes (%d substripes) of %" PRIxGRUB_UINT64_T ")\n", grub_le_to_cpu64 (key->offset), grub_le_to_cpu64 (chunk->size), grub_le_to_cpu16 (chunk->nstripes), grub_le_to_cpu16 (chunk->nsubstripes), grub_le_to_cpu64 (chunk->stripe_length)); grub_dprintf ("btrfs", "reading laddr 0x%" PRIxGRUB_UINT64_T "\n", addr); if (is_raid56) { err = btrfs_read_from_chunk (data, chunk, stripen, stripe_offset, 0, /* no mirror */ csize, buf); grub_errno = GRUB_ERR_NONE; if (err) err = raid56_read_retry (data, chunk, stripe_offset, stripen, csize, buf, parities_pos); } else for (i = 0; i < redundancy; i++) { err = btrfs_read_from_chunk (data, chunk, stripen, stripe_offset, i, /* redundancy */ csize, buf); if (!err) break; grub_errno = GRUB_ERR_NONE; } if (!err) break; } if (err) return grub_errno = err; } size -= csize; buf = (grub_uint8_t *) buf + csize; addr += csize; if (challoc) grub_free (chunk); } return GRUB_ERR_NONE; } static struct grub_btrfs_data * grub_btrfs_mount (grub_device_t dev) { struct grub_btrfs_data *data; grub_err_t err; if (!dev->disk) { grub_error (GRUB_ERR_BAD_FS, "not BtrFS"); return NULL; } data = grub_zalloc (sizeof (*data)); if (!data) return NULL; err = read_sblock (dev->disk, &data->sblock); if (err) { grub_free (data); return NULL; } data->n_devices_allocated = 16; data->devices_attached = grub_malloc (sizeof (data->devices_attached[0]) * data->n_devices_allocated); if (!data->devices_attached) { grub_free (data); return NULL; } data->n_devices_attached = 1; data->devices_attached[0].dev = dev; data->devices_attached[0].id = data->sblock.this_device.device_id; return data; } static void grub_btrfs_unmount (struct grub_btrfs_data *data) { unsigned i; /* The device 0 is closed one layer upper. */ for (i = 1; i < data->n_devices_attached; i++) if (data->devices_attached[i].dev) grub_device_close (data->devices_attached[i].dev); grub_free (data->devices_attached); grub_free (data->extent); grub_free (data); } static grub_err_t grub_btrfs_read_inode (struct grub_btrfs_data *data, struct grub_btrfs_inode *inode, grub_uint64_t num, grub_uint64_t tree) { struct grub_btrfs_key key_in, key_out; grub_disk_addr_t elemaddr; grub_size_t elemsize; grub_err_t err; key_in.object_id = num; key_in.type = GRUB_BTRFS_ITEM_TYPE_INODE_ITEM; key_in.offset = 0; err = lower_bound (data, &key_in, &key_out, tree, &elemaddr, &elemsize, NULL, 0); if (err) return err; if (num != key_out.object_id || key_out.type != GRUB_BTRFS_ITEM_TYPE_INODE_ITEM) return grub_error (GRUB_ERR_BAD_FS, "inode not found"); return grub_btrfs_read_logical (data, elemaddr, inode, sizeof (*inode), 0); } static void *grub_zstd_malloc (void *state __attribute__((unused)), size_t size) { return grub_malloc (size); } static void grub_zstd_free (void *state __attribute__((unused)), void *address) { return grub_free (address); } static ZSTD_customMem grub_zstd_allocator (void) { ZSTD_customMem allocator; allocator.customAlloc = &grub_zstd_malloc; allocator.customFree = &grub_zstd_free; allocator.opaque = NULL; return allocator; } static grub_ssize_t grub_btrfs_zstd_decompress (char *ibuf, grub_size_t isize, grub_off_t off, char *obuf, grub_size_t osize) { void *allocated = NULL; char *otmpbuf = obuf; grub_size_t otmpsize = osize; ZSTD_DCtx *dctx = NULL; grub_size_t zstd_ret; grub_ssize_t ret = -1; /* * Zstd will fail if it can't fit the entire output in the destination * buffer, so if osize isn't large enough, allocate a temporary buffer. */ if (otmpsize < ZSTD_BTRFS_MAX_INPUT) { allocated = grub_malloc (ZSTD_BTRFS_MAX_INPUT); if (!allocated) { grub_error (GRUB_ERR_OUT_OF_MEMORY, "failed allocate a zstd buffer"); goto err; } otmpbuf = (char *) allocated; otmpsize = ZSTD_BTRFS_MAX_INPUT; } /* Create the ZSTD_DCtx. */ dctx = ZSTD_createDCtx_advanced (grub_zstd_allocator ()); if (!dctx) { /* ZSTD_createDCtx_advanced() only fails if it is out of memory. */ grub_error (GRUB_ERR_OUT_OF_MEMORY, "failed to create a zstd context"); goto err; } /* * Get the real input size, there may be junk at the * end of the frame. */ isize = ZSTD_findFrameCompressedSize (ibuf, isize); if (ZSTD_isError (isize)) { grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "zstd data corrupted"); goto err; } /* Decompress and check for errors. */ zstd_ret = ZSTD_decompressDCtx (dctx, otmpbuf, otmpsize, ibuf, isize); if (ZSTD_isError (zstd_ret)) { grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "zstd data corrupted"); goto err; } /* * Move the requested data into the obuf. obuf may be equal * to otmpbuf, which is why grub_memmove() is required. */ grub_memmove (obuf, otmpbuf + off, osize); ret = osize; err: grub_free (allocated); ZSTD_freeDCtx (dctx); return ret; } static grub_ssize_t grub_btrfs_lzo_decompress(char *ibuf, grub_size_t isize, grub_off_t off, char *obuf, grub_size_t osize) { grub_uint32_t total_size, cblock_size; grub_size_t ret = 0; char *ibuf0 = ibuf; total_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf)); ibuf += sizeof (total_size); if (isize < total_size) return -1; /* Jump forward to first block with requested data. */ while (off >= GRUB_BTRFS_LZO_BLOCK_SIZE) { /* Don't let following uint32_t cross the page boundary. */ if (((ibuf - ibuf0) & 0xffc) == 0xffc) ibuf = ((ibuf - ibuf0 + 3) & ~3) + ibuf0; cblock_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf)); ibuf += sizeof (cblock_size); if (cblock_size > GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE) return -1; off -= GRUB_BTRFS_LZO_BLOCK_SIZE; ibuf += cblock_size; } while (osize > 0) { lzo_uint usize = GRUB_BTRFS_LZO_BLOCK_SIZE; /* Don't let following uint32_t cross the page boundary. */ if (((ibuf - ibuf0) & 0xffc) == 0xffc) ibuf = ((ibuf - ibuf0 + 3) & ~3) + ibuf0; cblock_size = grub_le_to_cpu32 (grub_get_unaligned32 (ibuf)); ibuf += sizeof (cblock_size); if (cblock_size > GRUB_BTRFS_LZO_BLOCK_MAX_CSIZE) return -1; /* Block partially filled with requested data. */ if (off > 0 || osize < GRUB_BTRFS_LZO_BLOCK_SIZE) { grub_size_t to_copy = GRUB_BTRFS_LZO_BLOCK_SIZE - off; grub_uint8_t *buf; if (to_copy > osize) to_copy = osize; buf = grub_malloc (GRUB_BTRFS_LZO_BLOCK_SIZE); if (!buf) return -1; if (lzo1x_decompress_safe ((lzo_bytep)ibuf, cblock_size, buf, &usize, NULL) != LZO_E_OK) { grub_free (buf); return -1; } if (to_copy > usize) to_copy = usize; grub_memcpy(obuf, buf + off, to_copy); osize -= to_copy; ret += to_copy; obuf += to_copy; ibuf += cblock_size; off = 0; grub_free (buf); continue; } /* Decompress whole block directly to output buffer. */ if (lzo1x_decompress_safe ((lzo_bytep)ibuf, cblock_size, (lzo_bytep)obuf, &usize, NULL) != LZO_E_OK) return -1; osize -= usize; ret += usize; obuf += usize; ibuf += cblock_size; } return ret; } static grub_ssize_t grub_btrfs_extent_read (struct grub_btrfs_data *data, grub_uint64_t ino, grub_uint64_t tree, grub_off_t pos0, char *buf, grub_size_t len) { grub_off_t pos = pos0; while (len) { grub_size_t csize; grub_err_t err; grub_off_t extoff; if (!data->extent || data->extstart > pos || data->extino != ino || data->exttree != tree || data->extend <= pos) { struct grub_btrfs_key key_in, key_out; grub_disk_addr_t elemaddr; grub_size_t elemsize; grub_free (data->extent); key_in.object_id = ino; key_in.type = GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM; key_in.offset = grub_cpu_to_le64 (pos); err = lower_bound (data, &key_in, &key_out, tree, &elemaddr, &elemsize, NULL, 0); if (err) return -1; if (key_out.object_id != ino || key_out.type != GRUB_BTRFS_ITEM_TYPE_EXTENT_ITEM) { grub_error (GRUB_ERR_BAD_FS, "extent not found"); return -1; } if ((grub_ssize_t) elemsize < ((char *) &data->extent->inl - (char *) data->extent)) { grub_error (GRUB_ERR_BAD_FS, "extent descriptor is too short"); return -1; } data->extstart = grub_le_to_cpu64 (key_out.offset); data->extsize = elemsize; data->extent = grub_malloc (elemsize); data->extino = ino; data->exttree = tree; if (!data->extent) return grub_errno; err = grub_btrfs_read_logical (data, elemaddr, data->extent, elemsize, 0); if (err) return err; data->extend = data->extstart + grub_le_to_cpu64 (data->extent->size); if (data->extent->type == GRUB_BTRFS_EXTENT_REGULAR && (char *) data->extent + elemsize >= (char *) &data->extent->filled + sizeof (data->extent->filled)) data->extend = data->extstart + grub_le_to_cpu64 (data->extent->filled); grub_dprintf ("btrfs", "regular extent 0x%" PRIxGRUB_UINT64_T "+0x%" PRIxGRUB_UINT64_T "\n", grub_le_to_cpu64 (key_out.offset), grub_le_to_cpu64 (data->extent->size)); if (data->extend <= pos) { grub_error (GRUB_ERR_BAD_FS, "extent not found"); return -1; } } csize = data->extend - pos; extoff = pos - data->extstart; if (csize > len) csize = len; if (data->extent->encryption) { grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET, "encryption not supported"); return -1; } if (data->extent->compression != GRUB_BTRFS_COMPRESSION_NONE && data->extent->compression != GRUB_BTRFS_COMPRESSION_ZLIB && data->extent->compression != GRUB_BTRFS_COMPRESSION_LZO && data->extent->compression != GRUB_BTRFS_COMPRESSION_ZSTD) { grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET, "compression type 0x%x not supported", data->extent->compression); return -1; } if (data->extent->encoding) { grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET, "encoding not supported"); return -1; } switch (data->extent->type) { case GRUB_BTRFS_EXTENT_INLINE: if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZLIB) { if (grub_zlib_decompress (data->extent->inl, data->extsize - ((grub_uint8_t *) data->extent->inl - (grub_uint8_t *) data->extent), extoff, buf, csize) != (grub_ssize_t) csize) { if (!grub_errno) grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "premature end of compressed"); return -1; } } else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_LZO) { if (grub_btrfs_lzo_decompress(data->extent->inl, data->extsize - ((grub_uint8_t *) data->extent->inl - (grub_uint8_t *) data->extent), extoff, buf, csize) != (grub_ssize_t) csize) return -1; } else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZSTD) { if (grub_btrfs_zstd_decompress (data->extent->inl, data->extsize - ((grub_uint8_t *) data->extent->inl - (grub_uint8_t *) data->extent), extoff, buf, csize) != (grub_ssize_t) csize) return -1; } else grub_memcpy (buf, data->extent->inl + extoff, csize); break; case GRUB_BTRFS_EXTENT_REGULAR: if (!data->extent->laddr) { grub_memset (buf, 0, csize); break; } if (data->extent->compression != GRUB_BTRFS_COMPRESSION_NONE) { char *tmp; grub_uint64_t zsize; grub_ssize_t ret; zsize = grub_le_to_cpu64 (data->extent->compressed_size); tmp = grub_malloc (zsize); if (!tmp) return -1; err = grub_btrfs_read_logical (data, grub_le_to_cpu64 (data->extent->laddr), tmp, zsize, 0); if (err) { grub_free (tmp); return -1; } if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZLIB) ret = grub_zlib_decompress (tmp, zsize, extoff + grub_le_to_cpu64 (data->extent->offset), buf, csize); else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_LZO) ret = grub_btrfs_lzo_decompress (tmp, zsize, extoff + grub_le_to_cpu64 (data->extent->offset), buf, csize); else if (data->extent->compression == GRUB_BTRFS_COMPRESSION_ZSTD) ret = grub_btrfs_zstd_decompress (tmp, zsize, extoff + grub_le_to_cpu64 (data->extent->offset), buf, csize); else ret = -1; grub_free (tmp); if (ret != (grub_ssize_t) csize) { if (!grub_errno) grub_error (GRUB_ERR_BAD_COMPRESSED_DATA, "premature end of compressed"); return -1; } break; } err = grub_btrfs_read_logical (data, grub_le_to_cpu64 (data->extent->laddr) + grub_le_to_cpu64 (data->extent->offset) + extoff, buf, csize, 0); if (err) return -1; break; default: grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET, "unsupported extent type 0x%x", data->extent->type); return -1; } buf += csize; pos += csize; len -= csize; } return pos - pos0; } static grub_err_t get_root (struct grub_btrfs_data *data, struct grub_btrfs_key *key, grub_uint64_t *tree, grub_uint8_t *type) { grub_err_t err; grub_disk_addr_t elemaddr; grub_size_t elemsize; struct grub_btrfs_key key_out, key_in; struct grub_btrfs_root_item ri; key_in.object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_ROOT_VOL_OBJECTID); key_in.offset = 0; key_in.type = GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM; err = lower_bound (data, &key_in, &key_out, data->sblock.root_tree, &elemaddr, &elemsize, NULL, 0); if (err) return err; if (key_in.object_id != key_out.object_id || key_in.type != key_out.type || key_in.offset != key_out.offset) return grub_error (GRUB_ERR_BAD_FS, "no root"); err = grub_btrfs_read_logical (data, elemaddr, &ri, sizeof (ri), 0); if (err) return err; key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM; key->offset = 0; key->object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_OBJECT_ID_CHUNK); *tree = ri.tree; *type = GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY; return GRUB_ERR_NONE; } static grub_err_t find_path (struct grub_btrfs_data *data, const char *path, struct grub_btrfs_key *key, grub_uint64_t *tree, grub_uint8_t *type) { const char *slash = path; grub_err_t err; grub_disk_addr_t elemaddr; grub_size_t elemsize; grub_size_t allocated = 0; struct grub_btrfs_dir_item *direl = NULL; struct grub_btrfs_key key_out; const char *ctoken; grub_size_t ctokenlen; char *path_alloc = NULL; char *origpath = NULL; unsigned symlinks_max = 32; err = get_root (data, key, tree, type); if (err) return err; origpath = grub_strdup (path); if (!origpath) return grub_errno; while (1) { while (path[0] == '/') path++; if (!path[0]) break; slash = grub_strchr (path, '/'); if (!slash) slash = path + grub_strlen (path); ctoken = path; ctokenlen = slash - path; if (*type != GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY) { grub_free (path_alloc); grub_free (origpath); return grub_error (GRUB_ERR_BAD_FILE_TYPE, N_("not a directory")); } if (ctokenlen == 1 && ctoken[0] == '.') { path = slash; continue; } if (ctokenlen == 2 && ctoken[0] == '.' && ctoken[1] == '.') { key->type = GRUB_BTRFS_ITEM_TYPE_INODE_REF; key->offset = -1; err = lower_bound (data, key, &key_out, *tree, &elemaddr, &elemsize, NULL, 0); if (err) { grub_free (direl); grub_free (path_alloc); grub_free (origpath); return err; } if (key_out.type != key->type || key->object_id != key_out.object_id) { grub_free (direl); grub_free (path_alloc); err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath); grub_free (origpath); return err; } *type = GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY; key->object_id = key_out.offset; path = slash; continue; } key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM; key->offset = grub_cpu_to_le64 (~grub_getcrc32c (1, ctoken, ctokenlen)); err = lower_bound (data, key, &key_out, *tree, &elemaddr, &elemsize, NULL, 0); if (err) { grub_free (direl); grub_free (path_alloc); grub_free (origpath); return err; } if (key_cmp (key, &key_out) != 0) { grub_free (direl); grub_free (path_alloc); err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath); grub_free (origpath); return err; } struct grub_btrfs_dir_item *cdirel; if (elemsize > allocated) { allocated = 2 * elemsize; grub_free (direl); direl = grub_malloc (allocated + 1); if (!direl) { grub_free (path_alloc); grub_free (origpath); return grub_errno; } } err = grub_btrfs_read_logical (data, elemaddr, direl, elemsize, 0); if (err) { grub_free (direl); grub_free (path_alloc); grub_free (origpath); return err; } for (cdirel = direl; (grub_uint8_t *) cdirel - (grub_uint8_t *) direl < (grub_ssize_t) elemsize; cdirel = (void *) ((grub_uint8_t *) (direl + 1) + grub_le_to_cpu16 (cdirel->n) + grub_le_to_cpu16 (cdirel->m))) { if (ctokenlen == grub_le_to_cpu16 (cdirel->n) && grub_memcmp (cdirel->name, ctoken, ctokenlen) == 0) break; } if ((grub_uint8_t *) cdirel - (grub_uint8_t *) direl >= (grub_ssize_t) elemsize) { grub_free (direl); grub_free (path_alloc); err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath); grub_free (origpath); return err; } path = slash; if (cdirel->type == GRUB_BTRFS_DIR_ITEM_TYPE_SYMLINK) { struct grub_btrfs_inode inode; char *tmp; if (--symlinks_max == 0) { grub_free (direl); grub_free (path_alloc); grub_free (origpath); return grub_error (GRUB_ERR_SYMLINK_LOOP, N_("too deep nesting of symlinks")); } err = grub_btrfs_read_inode (data, &inode, cdirel->key.object_id, *tree); if (err) { grub_free (direl); grub_free (path_alloc); grub_free (origpath); return err; } tmp = grub_malloc (grub_le_to_cpu64 (inode.size) + grub_strlen (path) + 1); if (!tmp) { grub_free (direl); grub_free (path_alloc); grub_free (origpath); return grub_errno; } if (grub_btrfs_extent_read (data, cdirel->key.object_id, *tree, 0, tmp, grub_le_to_cpu64 (inode.size)) != (grub_ssize_t) grub_le_to_cpu64 (inode.size)) { grub_free (direl); grub_free (path_alloc); grub_free (origpath); grub_free (tmp); return grub_errno; } grub_memcpy (tmp + grub_le_to_cpu64 (inode.size), path, grub_strlen (path) + 1); grub_free (path_alloc); path = path_alloc = tmp; if (path[0] == '/') { err = get_root (data, key, tree, type); if (err) return err; } continue; } *type = cdirel->type; switch (cdirel->key.type) { case GRUB_BTRFS_ITEM_TYPE_ROOT_ITEM: { struct grub_btrfs_root_item ri; err = lower_bound (data, &cdirel->key, &key_out, data->sblock.root_tree, &elemaddr, &elemsize, NULL, 0); if (err) { grub_free (direl); grub_free (path_alloc); grub_free (origpath); return err; } if (cdirel->key.object_id != key_out.object_id || cdirel->key.type != key_out.type) { grub_free (direl); grub_free (path_alloc); err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath); grub_free (origpath); return err; } err = grub_btrfs_read_logical (data, elemaddr, &ri, sizeof (ri), 0); if (err) { grub_free (direl); grub_free (path_alloc); grub_free (origpath); return err; } key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM; key->offset = 0; key->object_id = grub_cpu_to_le64_compile_time (GRUB_BTRFS_OBJECT_ID_CHUNK); *tree = ri.tree; break; } case GRUB_BTRFS_ITEM_TYPE_INODE_ITEM: if (*slash && *type == GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR) { grub_free (direl); grub_free (path_alloc); err = grub_error (GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"), origpath); grub_free (origpath); return err; } *key = cdirel->key; if (*type == GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY) key->type = GRUB_BTRFS_ITEM_TYPE_DIR_ITEM; break; default: grub_free (path_alloc); grub_free (origpath); grub_free (direl); return grub_error (GRUB_ERR_BAD_FS, "unrecognised object type 0x%x", cdirel->key.type); } } grub_free (direl); grub_free (origpath); grub_free (path_alloc); return GRUB_ERR_NONE; } static grub_err_t grub_btrfs_dir (grub_device_t device, const char *path, grub_fs_dir_hook_t hook, void *hook_data) { struct grub_btrfs_data *data = grub_btrfs_mount (device); struct grub_btrfs_key key_in, key_out; grub_err_t err; grub_disk_addr_t elemaddr; grub_size_t elemsize; grub_size_t allocated = 0; struct grub_btrfs_dir_item *direl = NULL; struct grub_btrfs_leaf_descriptor desc; int r = 0; grub_uint64_t tree; grub_uint8_t type; if (!data) return grub_errno; err = find_path (data, path, &key_in, &tree, &type); if (err) { grub_btrfs_unmount (data); return err; } if (type != GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY) { grub_btrfs_unmount (data); return grub_error (GRUB_ERR_BAD_FILE_TYPE, N_("not a directory")); } err = lower_bound (data, &key_in, &key_out, tree, &elemaddr, &elemsize, &desc, 0); if (err) { grub_btrfs_unmount (data); return err; } if (key_out.type != GRUB_BTRFS_ITEM_TYPE_DIR_ITEM || key_out.object_id != key_in.object_id) { r = next (data, &desc, &elemaddr, &elemsize, &key_out); if (r <= 0) goto out; } do { struct grub_btrfs_dir_item *cdirel; if (key_out.type != GRUB_BTRFS_ITEM_TYPE_DIR_ITEM || key_out.object_id != key_in.object_id) { r = 0; break; } if (elemsize > allocated) { allocated = 2 * elemsize; grub_free (direl); direl = grub_malloc (allocated + 1); if (!direl) { r = -grub_errno; break; } } err = grub_btrfs_read_logical (data, elemaddr, direl, elemsize, 0); if (err) { r = -err; break; } for (cdirel = direl; (grub_uint8_t *) cdirel - (grub_uint8_t *) direl < (grub_ssize_t) elemsize; cdirel = (void *) ((grub_uint8_t *) (direl + 1) + grub_le_to_cpu16 (cdirel->n) + grub_le_to_cpu16 (cdirel->m))) { char c; struct grub_btrfs_inode inode; struct grub_dirhook_info info; err = grub_btrfs_read_inode (data, &inode, cdirel->key.object_id, tree); grub_memset (&info, 0, sizeof (info)); if (err) grub_errno = GRUB_ERR_NONE; else { info.mtime = grub_le_to_cpu64 (inode.mtime.sec); info.mtimeset = 1; } c = cdirel->name[grub_le_to_cpu16 (cdirel->n)]; cdirel->name[grub_le_to_cpu16 (cdirel->n)] = 0; info.dir = (cdirel->type == GRUB_BTRFS_DIR_ITEM_TYPE_DIRECTORY); if (hook (cdirel->name, &info, hook_data)) goto out; cdirel->name[grub_le_to_cpu16 (cdirel->n)] = c; } r = next (data, &desc, &elemaddr, &elemsize, &key_out); } while (r > 0); out: grub_free (direl); free_iterator (&desc); grub_btrfs_unmount (data); return -r; } static grub_err_t grub_btrfs_open (struct grub_file *file, const char *name) { struct grub_btrfs_data *data = grub_btrfs_mount (file->device); grub_err_t err; struct grub_btrfs_inode inode; grub_uint8_t type; struct grub_btrfs_key key_in; if (!data) return grub_errno; err = find_path (data, name, &key_in, &data->tree, &type); if (err) { grub_btrfs_unmount (data); return err; } if (type != GRUB_BTRFS_DIR_ITEM_TYPE_REGULAR) { grub_btrfs_unmount (data); return grub_error (GRUB_ERR_BAD_FILE_TYPE, N_("not a regular file")); } data->inode = key_in.object_id; err = grub_btrfs_read_inode (data, &inode, data->inode, data->tree); if (err) { grub_btrfs_unmount (data); return err; } file->data = data; file->size = grub_le_to_cpu64 (inode.size); return err; } static grub_err_t grub_btrfs_close (grub_file_t file) { grub_btrfs_unmount (file->data); return GRUB_ERR_NONE; } static grub_ssize_t grub_btrfs_read (grub_file_t file, char *buf, grub_size_t len) { struct grub_btrfs_data *data = file->data; return grub_btrfs_extent_read (data, data->inode, data->tree, file->offset, buf, len); } static grub_err_t grub_btrfs_uuid (grub_device_t device, char **uuid) { struct grub_btrfs_data *data; *uuid = NULL; data = grub_btrfs_mount (device); if (!data) return grub_errno; *uuid = grub_xasprintf ("%04x%04x-%04x-%04x-%04x-%04x%04x%04x", grub_be_to_cpu16 (data->sblock.uuid[0]), grub_be_to_cpu16 (data->sblock.uuid[1]), grub_be_to_cpu16 (data->sblock.uuid[2]), grub_be_to_cpu16 (data->sblock.uuid[3]), grub_be_to_cpu16 (data->sblock.uuid[4]), grub_be_to_cpu16 (data->sblock.uuid[5]), grub_be_to_cpu16 (data->sblock.uuid[6]), grub_be_to_cpu16 (data->sblock.uuid[7])); grub_btrfs_unmount (data); return grub_errno; } static grub_err_t grub_btrfs_label (grub_device_t device, char **label) { struct grub_btrfs_data *data; *label = NULL; data = grub_btrfs_mount (device); if (!data) return grub_errno; *label = grub_strndup (data->sblock.label, sizeof (data->sblock.label)); grub_btrfs_unmount (data); return grub_errno; } #ifdef GRUB_UTIL static grub_err_t grub_btrfs_embed (grub_device_t device __attribute__ ((unused)), unsigned int *nsectors, unsigned int max_nsectors, grub_embed_type_t embed_type, grub_disk_addr_t **sectors) { unsigned i; if (embed_type != GRUB_EMBED_PCBIOS) return grub_error (GRUB_ERR_NOT_IMPLEMENTED_YET, "BtrFS currently supports only PC-BIOS embedding"); if (64 * 2 - 1 < *nsectors) return grub_error (GRUB_ERR_OUT_OF_RANGE, N_("your core.img is unusually large. " "It won't fit in the embedding area")); *nsectors = 64 * 2 - 1; if (*nsectors > max_nsectors) *nsectors = max_nsectors; *sectors = grub_calloc (*nsectors, sizeof (**sectors)); if (!*sectors) return grub_errno; for (i = 0; i < *nsectors; i++) (*sectors)[i] = i + 1; return GRUB_ERR_NONE; } #endif static struct grub_fs grub_btrfs_fs = { .name = "btrfs", .fs_dir = grub_btrfs_dir, .fs_open = grub_btrfs_open, .fs_read = grub_btrfs_read, .fs_close = grub_btrfs_close, .fs_uuid = grub_btrfs_uuid, .fs_label = grub_btrfs_label, #ifdef GRUB_UTIL .fs_embed = grub_btrfs_embed, .reserved_first_sector = 1, .blocklist_install = 0, #endif }; GRUB_MOD_INIT (btrfs) { grub_fs_register (&grub_btrfs_fs); } GRUB_MOD_FINI (btrfs) { grub_fs_unregister (&grub_btrfs_fs); }