>From 39b8bbd853911fa0ea91265744b19779c24128b8 Mon Sep 17 00:00:00 2001 Message-Id: In-Reply-To: References: From: surbhi Date: Mon, 5 Jul 2010 15:22:28 +0300 Subject: [PATCH 2/2] btrfs support for grub-2 This patch is usable provided the license for this patch resolves to GPLv3. Signed-off-by: Surbhi Palande --- fs/btrfs.c | 1434 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs.h | 385 ++++++++++++++++ 2 files changed, 1819 insertions(+), 0 deletions(-) create mode 100644 fs/btrfs.c create mode 100644 fs/btrfs.h diff --git a/fs/btrfs.c b/fs/btrfs.c new file mode 100644 index 0000000..7725e0a --- /dev/null +++ b/fs/btrfs.c @@ -0,0 +1,1434 @@ +/* btrfs.c - Binary Tree F.S */ +/* + * GRUB -- GRand Unified Bootloader + * Copyright (C) 2003,2004,2005,2007,2008,2009 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. + * This file can be re-distributed and/or modified 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. + * + * You should have received a copy of the GNU General Public License + * along with GRUB. If not, see . + * + * btrfs: Copyright (C) 2007 Oracle. All rights reserved. + * + * btrfs.c -- readonly btrfs support for grub-2 + * author: address@hidden + * License for this file yet needs to be resolved!! + * You cannot use this file as of now. Will be usable only if the file + * can be accepted as GPLv3 + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "btrfs.h" + +#define BTRFS_SUPER_MIRROR_SHIFT 12 + +#define assert(boolean) real_assert (boolean, __FILE__, __LINE__) +static inline void +real_assert (int boolean, const char *file, const int line) +{ + if (! boolean) + grub_printf ("Assertion failed at %s:%d\n", file, line); +} + +#define perror(str) grub_printf("\n ##str %d", grub_errno); + + +static grub_dl_t my_mod; + +#define u32 unsigned int +#define u8 unsigned char +static u32 crc32c_table[256]; +/* + * * Steps through buffer one byte at at time, calculates reflected + * * crc using table. + * */ + + +static inline u32 crc32c_le(u32 crc, const char *data, u32 length) +{ + while (length--) + crc = crc32c_table[(u8)(crc ^ *data++)] ^ (crc >> 8); + + return crc; +} + +static inline void btrfs_init_crc32c(void) +{ + int i, j; + u32 v; + const u32 poly = 0x82F63B78; /* Bit-reflected CRC32C polynomial */ + + for (i = 0; i < 256; i++) { + v = i; + for (j = 0; j < 8; j++) { + v = (v >> 1) ^ ((v & 1) ? poly : 0); + } + crc32c_table[i] = v; + } +} + +struct btrfs_fs_cache fs_cache; + +static void clear_mem(char * ptr, unsigned int size) +{ + unsigned int i; + for(i = 0; i< size; i++) + { + ptr[i] = 0; + } +} + + +static inline u64 btrfs_sb_offset(int mirror) +{ + u64 start = 16 * 1024; + if (mirror) + return start << (BTRFS_SUPER_MIRROR_SHIFT * mirror); + return BTRFS_SUPER_INFO_OFFSET; +} + +/* + * returns 1 if superblock is found and returns 0 otherwise + * + */ +static int btrfs_read_superblock(grub_disk_t disk, struct btrfs_fs_info * fs_info) +{ + int i, ret; + int found = 1; + u64 offset; + unsigned fsid[BTRFS_FSID_SIZE]; + + struct btrfs_super_block sb; + fs_info->sb_transid = 0; + + for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) { + /* + * read from cache if cache is already populated, else + * read from disk + */ + offset = btrfs_sb_offset(i); + if(offset > disk->total_sectors) { + if( found == 1) + grub_errno = GRUB_ERR_OUT_OF_RANGE; + break; + } + ret = grub_disk_read(disk, offset >> SECTOR_BITS, + (offset % (1< fs_info->sb_transid) { + grub_memcpy(&fs_info->sb_copy, &sb, sizeof(sb)); + //grub_printf("\n copied superblock, magic num matches!\n"); + fs_info->sb_transid = sb.generation; + fs_info->sb_mirror = i; + } + } + if (grub_errno == GRUB_ERR_OUT_OF_RANGE) { + if(found == 1) + grub_error (GRUB_ERR_BAD_FS, "not a btrfs filesystem"); + else + grub_errno = GRUB_ERR_NONE; + } + return found; +} + +/* compare function used for bin_search */ +typedef int (*cmp_func)(void *ptr1, void *ptr2); + + +/* simple but useful bin search, used for chunk search and btree search + * you always compare the item stored in the middle + * 0 is a perfect match, 1 indicates slot has the next stored slot number + */ +static int bin_search(void *ptr, int item_size, void *cmp_item, cmp_func func, + int min, int max, int *slot) +{ + int low = min; + int high = max; + int mid; + int ret; + unsigned long offset; + void *item; + + while (low < high) { + mid = (low + high) / 2; + offset = mid * item_size; + + item = (char *) ptr + offset; + ret = func(item, cmp_item); + // ret<0 then item < cmp_item. ret >0 then item > cm_item + if (ret < 0) { + low = mid + 1; + } + else if (ret > 0) { + high = mid; + } + else { + *slot = mid; + return 0; + } + } + // this is the next item which is just bigger than what we are searching. + *slot = low; + return 1; +} + + +static int btrfs_comp_chunk_map(struct btrfs_chunk_map_item *m1, + struct btrfs_chunk_map_item *m2) +{ + if (m1->logical > m2->logical) + return 1; + if (m1->logical < m2->logical) + return -1; + return 0; +} + + + + +/* insert a new chunk mapping item */ +static void insert_map(struct btrfs_chunk_map_item *item, struct btrfs_fs_info * fs_info) +{ + int ret; + int slot; + int i; + struct btrfs_chunk_map * chunk_map = &(fs_info->chunk_map); + + + if (chunk_map->map == NULL) { /* first item */ + chunk_map->map_length = BTRFS_MAX_CHUNK_ENTRIES; + chunk_map->map = (struct btrfs_chunk_map_item *) + grub_malloc(chunk_map->map_length * sizeof(*chunk_map->map)); + chunk_map->map[0] = *item; + chunk_map->cur_length = 1; + return; + } + ret = bin_search(chunk_map->map, sizeof(*item), item, + (cmp_func)btrfs_comp_chunk_map, 0, + chunk_map->cur_length, &slot); + if (ret == 0)/* already in map */ + { + return; + } + if (chunk_map->cur_length == BTRFS_MAX_CHUNK_ENTRIES) { + /* should be impossible */ + return; + } + + for (i = chunk_map->cur_length; i > slot; i--) + chunk_map->map[i] = chunk_map->map[i-1]; + + chunk_map->map[slot] = *item; + chunk_map->cur_length++; + return; +} + +static inline unsigned long btrfs_chunk_item_size(int num_stripes) +{ + assert(num_stripes > 0); + return sizeof(struct btrfs_chunk) + + sizeof(struct btrfs_stripe) * (num_stripes - 1); +} + +static void btrfs_read_sys_chunk_array(struct btrfs_fs_info * fs_info) +{ + struct btrfs_chunk_map_item item; + struct btrfs_disk_key *key; + struct btrfs_chunk *chunk; + int cur; + int ret; + + /* read chunk array in superblock */ + cur = 0; + while (cur < fs_info->sb_copy.sys_chunk_array_size) { + key = (struct btrfs_disk_key *)(fs_info->sb_copy.sys_chunk_array + cur); + cur += sizeof(struct btrfs_disk_key); + chunk = (struct btrfs_chunk *)(fs_info->sb_copy.sys_chunk_array + cur); + if(chunk->num_stripes <= 0) { + grub_errno = GRUB_ERR_BAD_FS; + break; + } + ret = btrfs_chunk_item_size(chunk->num_stripes); + cur = cur + ret; + /* insert to mapping table, ignore multi stripes */ + item.logical = key->offset; + item.length = chunk->length; + item.devid = chunk->stripe.devid; + item.physical = chunk->stripe.offset;/*ignore other stripes */ + insert_map(&item, fs_info); + } +} + + +/* + * * from sys_chunk_array or chunk_tree, we can convert a logical address to + * * a physical address we can not support multi device case yet + * */ +static u64 logical_physical(struct btrfs_chunk_map * chunk_map, u64 logical) +{ + struct btrfs_chunk_map_item item; + int slot, ret; + + item.logical = logical; + ret = bin_search(chunk_map->map, sizeof(*chunk_map->map), &item, + (cmp_func)btrfs_comp_chunk_map, 0, + chunk_map->cur_length, &slot); + if (ret == 0) + slot++; + else if (slot == 0) + return -1; + if (logical >= + chunk_map->map[slot-1].logical + chunk_map->map[slot-1].length) + return -1; + //grub_printf("\n conversion: logical: %llx, physical: %llx ", chunk_map->map[slot-1].logical, chunk_map->map[slot-1].physical); + return chunk_map->map[slot-1].physical + logical - + chunk_map->map[slot-1].logical; +} + +/* if stored item > searched item then return 1, else return -1 or 0 */ +static int btrfs_comp_keys(struct btrfs_disk_key *k1, struct btrfs_disk_key *k2) +{ + if (k1->objectid > k2->objectid) + return 1; + if (k1->objectid < k2->objectid) + return -1; + if (k1->type > k2->type) + return 1; + if (k1->type < k2->type) + return -1; + if (k1->offset > k2->offset) + return 1; + if (k1->offset < k2->offset) + return -1; + return 0; +} + + +/* compare keys but ignore offset, is useful to enumerate all same kind keys + * */ +static int btrfs_comp_keys_type(struct btrfs_disk_key *k1, + struct btrfs_disk_key *k2) +{ + if (k1->objectid > k2->objectid) + return 1; + if (k1->objectid < k2->objectid) + return -1; + if (k1->type > k2->type) + return 1; + if (k1->type < k2->type) + return -1; + return 0; +} + +/* seach tree directly on disk ... */ +static int search_tree(grub_disk_t disk, struct btrfs_fs_info * fs_info, u64 loffset, struct btrfs_disk_key *key, struct btrfs_path *path) +{ + u8 buf[BTRFS_MAX_LEAF_SIZE]; + struct btrfs_header *header = (struct btrfs_header *)buf; + struct btrfs_node *node = (struct btrfs_node *)buf; + struct btrfs_leaf *leaf = (struct btrfs_leaf *)buf; + int slot, ret; + u64 offset; + struct btrfs_super_block sb = fs_info->sb_copy; + + offset = logical_physical(&(fs_info->chunk_map), loffset); + grub_disk_read(disk, offset>>SECTOR_BITS, (offset % (1<level) {/*node*/ + grub_disk_read(disk, (offset + sizeof(*header)) >> SECTOR_BITS, + ((offset + sizeof(*header)) % (1<ptrs[0]); + path->itemsnr[header->level] = header->nritems; + path->offsets[header->level] = loffset; + ret = bin_search(&node->ptrs[0], sizeof(struct btrfs_key_ptr), + key, (cmp_func)btrfs_comp_keys, + path->slots[header->level], header->nritems, &slot); + if (ret && slot > path->slots[header->level]) + slot--; + path->slots[header->level] = slot; + ret = search_tree(disk, fs_info, node->ptrs[slot].blockptr, key, path); + } else {/*leaf*/ + grub_disk_read(disk, (offset + sizeof(*header)) >> SECTOR_BITS, + ((offset + sizeof(*header)) % (1<items); + path->itemsnr[0] = header->nritems; + path->offsets[0] = loffset; + ret = bin_search(&leaf->items[0], sizeof(struct btrfs_item), + key, (cmp_func)btrfs_comp_keys, path->slots[0], + header->nritems, &slot); + if (ret && slot > path->slots[header->level]) + slot--; + path->slots[0] = slot; + path->item = leaf->items[slot]; + if(leaf->items[slot].size > BTRFS_MAX_LEAF_SIZE) { + grub_printf("\n leaf->items[%d].size: %x greater than BTRFS_MAX_LEAF_SIZE \n", slot, leaf->items[slot].size); + return -1; + } + grub_disk_read(disk, (offset + sizeof(*header) + leaf->items[slot].offset) >> SECTOR_BITS, + ((offset + sizeof(*header) + leaf->items[slot].offset) % (1<items[slot].size, (char *)(&path->data)); + } + return ret; +} + +static int get_next_slot(grub_disk_t disk , u64 loffset, struct btrfs_path * path, int slot) +{ + u8 buf[BTRFS_MAX_LEAF_SIZE]; + u64 offset = logical_physical(&fs_cache.fs_info.chunk_map, loffset); + struct btrfs_leaf * leaf = (struct btrfs_leaf *) buf; + offset = offset + sizeof(struct btrfs_header); + + grub_disk_read(disk, offset >> SECTOR_BITS, (offset % (1<items); + offset = offset + leaf->items[slot].offset; + path->item = leaf->items[slot]; + grub_disk_read(disk, offset >> SECTOR_BITS, + (offset % (1<items[slot].size, (char *)(&path->data)); + return 0; +} + +/* return 0 if slot found */ +static int next_slot(grub_disk_t disk, struct btrfs_path *path) +{ + int slot; + if (!path->itemsnr[0]) + return 1; + slot = path->slots[0] + 1; + if (slot >= path->itemsnr[0]) + return 1; + path->slots[0] = slot; + get_next_slot(disk, path->offsets[0], path, path->slots[0]); + return 0; +} + + +/* return 0 if leaf found */ +static int next_leaf(grub_disk_t disk, struct btrfs_fs_info * fs_info, struct btrfs_disk_key *key, struct btrfs_path *path) +{ + int slot; + int level = 1; + + while (level < BTRFS_MAX_LEVEL) { + if (!path->itemsnr[level]) /* no more nodes */ + return 1; + slot = path->slots[level] + 1; + if (slot >= path->itemsnr[level]) { + level++; + continue;; + } + path->slots[level] = slot; + path->slots[level-1] = 0; /* reset low level slots info */ + search_tree(disk, fs_info, path->offsets[level], key, path); + break; + } + if (level == BTRFS_MAX_LEVEL) + return 1; + return 0; +} + + + + +/* read chunk items from chunk_tree and insert them to chunk map + * since you start from key.offset=0, you will pick up every chunk in the + * chunk tree with the key.objectid: BTRFS_FIRST_CHUNK_TREE_OBJECTID and + * key.type: BTRFS_FIRST_CHUNK_TREE_OBJECTID, iff min=0 and max is the last + * element. Or else you will pick every chunk after or including min. + */ +static void btrfs_read_chunk_tree(grub_disk_t disk, struct btrfs_fs_info * fs_info) +{ + struct btrfs_disk_key search_key; + struct btrfs_chunk chunk; + struct btrfs_chunk_map_item item; + struct btrfs_path path; + struct btrfs_super_block sb = fs_info->sb_copy; + + if (!(sb.flags & BTRFS_SUPER_FLAG_METADUMP)) { + if (sb.num_devices > 1) { + grub_printf("warning: only support single device btrfs\n"); + } + /* read chunk from chunk_tree */ + search_key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID; + search_key.type = BTRFS_CHUNK_ITEM_KEY; + search_key.offset = 0; + clear_mem((char *)&path, sizeof(struct btrfs_path)); + search_tree(disk, fs_info, sb.chunk_root, &search_key, &path); + while(1) { + /* insert into the chunk_map every slot in the + * leaf with key.offset >= search_offset and the + * same key.type and key.object_id. + */ + if (btrfs_comp_keys_type(&search_key, &path.item.key)) + break; + grub_memcpy(&chunk, (struct btrfs_chunk *)(path.data), sizeof(struct btrfs_chunk)); + /* insert to mapping table, ignore stripes */ + item.logical = path.item.key.offset; + item.length = chunk.length; + item.devid = chunk.stripe.devid; + item.physical = chunk.stripe.offset; + insert_map(&item, fs_info); + if(next_slot(disk, &path)) + if(next_leaf(disk, fs_info, &search_key, &path)) + break; + } + } +} + +static void btrfs_get_fs_tree(grub_disk_t disk, struct btrfs_fs_info * fs_info) +{ + struct btrfs_disk_key search_key; + struct btrfs_path path; + struct btrfs_root_item tree; + search_key.objectid = BTRFS_FS_TREE_OBJECTID; + search_key.type = BTRFS_ROOT_ITEM_KEY; + search_key.offset = 0; + clear_mem((char *)&path, sizeof(struct btrfs_path)); + search_tree(disk, fs_info, fs_info->sb_copy.root, &search_key, &path); + grub_memcpy(&tree, (struct btrfs_root_item *)path.data, sizeof(struct btrfs_root_item)); + fs_info->fs_root = tree.bytenr; + fs_cache.default_fs_root = tree.bytenr; +} + + +static void free_cache(void) +{ + struct btrfs_cache * cache, * temp1; + cache = &fs_cache.dentry_cache; + temp1 = cache; + while(cache->next) { + temp1 = cache->next; + cache->next = temp1->next; + grub_free(temp1); +//grub_printf("\n freed item from cache with value (comp: %s, ino: %lld, parent_ino:parent_ino: %lld) \n", temp1->path, temp1->inum, temp1->parent_inum); + } + fs_cache.dentry_cache.next = NULL; +} + +static void free_btrfs_cache(void) +{ + // grub_printf("\n freed cache \n"); + free_cache(); + clear_mem((char *)&fs_cache, sizeof(struct btrfs_fs_cache)); +} + +static int init_btrfs_cache(grub_disk_t disk) +{ + // read the latest super block in fs_info.sb + if(btrfs_read_superblock(disk, &fs_cache.fs_info) || (grub_errno != GRUB_ERR_NONE)) { + return -1; + } + if(grub_strncmp((char *)(&(fs_cache.fs_info.sb_copy.magic)), BTRFS_MAGIC, + sizeof(fs_cache.fs_info.sb_copy.magic))!= 0) { + grub_printf("\n This should not happen!"); + grub_errno = GRUB_ERR_BAD_FS; + return grub_errno; + } + btrfs_read_sys_chunk_array(&fs_cache.fs_info); + if(grub_errno == GRUB_ERR_NONE) { + btrfs_read_chunk_tree(disk, &fs_cache.fs_info); + if(grub_errno == GRUB_ERR_NONE) + btrfs_get_fs_tree(disk, &fs_cache.fs_info); + } + if(grub_errno == GRUB_ERR_NONE) + { + //grub_printf("\n fscache is populated! "); + fs_cache.populated=1; + fs_cache.disk_id = disk->id; + btrfs_init_crc32c(); + } else { + clear_mem((char *)&fs_cache, sizeof(struct btrfs_fs_cache)); // clear anything that was written + } + return grub_errno; +} + + + + + +static struct grub_btrfs_data * btrfs_init_fs(grub_disk_t disk) +{ + struct grub_btrfs_data * data; + if((fs_cache.populated == 1) && (fs_cache.disk_id != disk->id)) { + grub_errno = GRUB_ERR_BAD_FS; + return NULL; + } + if(fs_cache.populated == 0) { + if(init_btrfs_cache(disk)) + return NULL; + } + data = grub_zalloc (sizeof (struct grub_btrfs_data)); + if (!data) + return NULL; + data->fs_info = &fs_cache.fs_info; + data->cache = &fs_cache.dentry_cache; + data->disk = disk; + if(fs_cache.fs_info.fs_root != fs_cache.default_fs_root) + fs_cache.fs_info.fs_root = fs_cache.default_fs_root; //set it to the original root for future searches + return data; +} + +static void get_component(const char * str, int *start, int * end) +{ + int i=*start; + while(str[i] == '/') { + i++; + } + if(str[i] == '\0') { + *start = grub_strlen(str) - 1; + *end = (*start) + 1; + return; + } + *start = i; + while(str[i]!= '\0' && str[i] != '/') + i++; + *end = i; + return; +} + +static inline void btrfs_item_key_to_cpu(struct btrfs_disk_key * key, struct btrfs_path * path) +{ + key->type = path->item.key.type; + key->offset = path->item.key.offset; + key->objectid = path->item.key.objectid; +} + +static struct btrfs_dir_item * btrfs_match_dir_item_name(struct btrfs_path * path, char * name, int len) +{ + struct btrfs_dir_item *dir_item; + unsigned long name_ptr; + u32 total_len; + u32 cur = 0; + u32 this_len; + + dir_item = (struct btrfs_dir_item *) path->data; + total_len = path->item.size; + while (cur < total_len) { + this_len = sizeof(*dir_item) + + dir_item->name_len + dir_item->data_len; + name_ptr = (unsigned long)(dir_item + 1); + + if((dir_item->name_len < 0) || (dir_item->name_len > PATH_MAX)) + return NULL; + if(((char *)name_ptr)[dir_item->name_len] != '\0') + ((char *)name_ptr)[dir_item->name_len] = '\0'; + + if (dir_item->name_len == len && + grub_strcmp((char *)name_ptr, name)== 0) { + return dir_item; + } + cur = cur + this_len; + dir_item = (struct btrfs_dir_item *)((char *)dir_item + + this_len); + } + return NULL; +} + + +static inline u64 btrfs_name_hash(const char *name, int len) +{ + return crc32c_le((u32)~1, name, len); +} + +static int read_extent(grub_disk_t disk, struct btrfs_file_extent_item * extent_item, int offset, int disk_len, int mem_len, char * buf) +{ + long long total_len = 0; + //grub_printf("\n extent_item->compression: %d mem_len: %d", extent_item->compression, mem_len); + if(extent_item->compression != 0) { + return -mem_len; + } + while(disk_len > 0) { + // read at max 4K at a time + if(disk_len > 4096) { + disk_len = disk_len - 4096; + grub_disk_read(disk, offset>>SECTOR_BITS, (offset % (1<>SECTOR_BITS, (offset % (1< extent.length, so the next + * extent has to be searched and read. This function reads only 4K data from the disk at + * at a time. This is for now and should/can be changed + */ + +static grub_ssize_t read_file_inr(grub_disk_t disk, struct btrfs_fs_info * fs_info, __le64 inum, __le64 size, char * buf) +{ + struct btrfs_disk_key key; + struct btrfs_path path; + int ret = 0; + struct btrfs_file_extent_item extent_item; + u64 offset, loffset; + u64 disk_len = 0, rem_len = 0; + + + clear_mem((char *)&path, sizeof(struct btrfs_path)); + + key.objectid = inum; + key.type = BTRFS_EXTENT_DATA_KEY; + key.offset = 0; + + rem_len = size; + + while(rem_len > 0) { + if(search_tree(disk, fs_info, fs_info->fs_root, &key, &path)) { + grub_errno = GRUB_ERR_FILE_READ_ERROR; + return(-1); + } + grub_memcpy(&extent_item, (struct btrfs_file_extent_item *) path.data, sizeof(struct btrfs_file_extent_item)); + if (extent_item.type == BTRFS_FILE_EXTENT_INLINE) { + // verify this part + loffset = path.offsets[0] + sizeof(struct btrfs_header) \ + + path.item.offset \ + + (u32)(&(((struct btrfs_file_extent_item *) 0)->disk_bytenr)); + disk_len = path.item.size; + if(disk_len > rem_len) + disk_len = rem_len; + } else { + loffset = extent_item.disk_bytenr; + assert(extent_item.num_bytes == extent_item.disk_num_bytes); + disk_len = extent_item.disk_num_bytes; + if(disk_len > rem_len) + disk_len = rem_len; + } + offset = logical_physical(&(fs_info->chunk_map), loffset); + ret = read_extent(disk, &extent_item, offset, disk_len, rem_len, buf); + if(ret < 0) { + grub_errno = GRUB_ERR_FILE_READ_ERROR; + return -1; + } + rem_len = rem_len - ret; + key.offset = size - rem_len; //offset + rem_len = size + } + return size; +} + +static inline __le64 get_root_inum(void) +{ + return BTRFS_FIRST_FREE_OBJECTID; +} + +static __le64 get_resolved_inum(struct grub_btrfs_data * data, __le64 cwd_inum, __le64 inum, int *lnk_count, struct btrfs_inode_item * inode); + +static __le64 search_comp(struct grub_btrfs_data * data, __le64 dirid, char * name, int name_len); + +static int change_fs_root(grub_disk_t disk, struct btrfs_fs_info * fs_info, char * subvolName) +{ + struct btrfs_disk_key search_key; + struct btrfs_path path; + struct btrfs_root_item tree; + int subvol_ok = -1; + char * name_ptr; + struct btrfs_root_ref *ref; + + search_key.objectid = BTRFS_FS_TREE_OBJECTID; + search_key.type = BTRFS_ROOT_REF_KEY; + search_key.offset = 0; + clear_mem((char *)&path, sizeof(struct btrfs_path)); + + if (search_tree(disk, fs_info, fs_info->sb_copy.root, &search_key, &path)) + next_slot(disk, &path); + while(1) { + if (btrfs_comp_keys_type(&search_key, &path.item.key)) + break; + ref = (struct btrfs_root_ref *)path.data; + name_ptr = (char *) (ref + 1); + if(name_ptr[ref->name_len] != '\0') + name_ptr[ref->name_len] = '\0'; + // grub_printf("\n subvol: %s found! ", (char *) (ref + 1)); + if (!grub_strcmp(name_ptr, subvolName)) { + subvol_ok = 0; + break; + } + if(next_slot(disk, &path)) + if(next_leaf(disk, fs_info, &search_key, &path)) + break; + } + if(subvol_ok == 0) { + search_key.objectid = path.item.key.offset; + search_key.type = BTRFS_ROOT_ITEM_KEY; + search_key.offset = 0; + clear_mem((char *)&path, sizeof(struct btrfs_path)); + if(fs_info->sb_copy.root) { + search_tree(disk, fs_info, fs_info->sb_copy.root, &search_key, &path); + } + else + return -1; //this would be terrible. some coding error + grub_memcpy(&tree, (struct btrfs_root_item *)path.data, sizeof(struct btrfs_root_item)); + fs_info->fs_root = tree.bytenr; + if(grub_errno) + subvol_ok = 0; + } + return subvol_ok; +} + +static __le64 get_ino_cache(char * comp, __le64 parent_ino, u64 fs_root) +{ + struct btrfs_cache * temp = fs_cache.dentry_cache.next; + //grub_printf("\n searching for parent_ino: %lld", parent_ino); + while(temp){ + //grub_printf("\n stored parent_inum: %lld", temp->parent_inum); + if((temp->parent_inum == parent_ino) && (temp->fs_root == fs_root)) { + //grub_printf("\n found parent, about to match comp: %s temp->path: %s " , comp, temp->path); + if(grub_strcmp(temp->path, comp) == 0) { + if(temp->resolved_inum != -1) + return temp->resolved_inum; + else { + grub_printf("\n This should really not happen! inode found, resolved_inum = -1"); + return -1; + } + } + } + temp = temp->next; + } + return 0; +} + + +static __le64 get_parent(__le64 inum, u64 fs_root) +{ + struct btrfs_cache * temp = &fs_cache.dentry_cache; + if(inum == get_root_inum()) + return inum; + while(temp->next) { + temp = temp->next; + if((temp->inum == inum) && (temp->fs_root == fs_root)) + return temp->parent_inum; + } + return -1; +} + +static int insert_new_cache_item(__le64 inum, __le64 resolved_inum, __le64 parent_inum, u64 fs_root, char * comp) +{ + struct btrfs_cache * temp; + int len = grub_strlen(comp); + if(get_parent(inum, fs_root) == parent_inum) //entry found + return 0; + temp = (struct btrfs_cache *) grub_zalloc(sizeof(struct btrfs_cache)); + if(temp == NULL) { + return grub_errno; + } + temp->path = grub_malloc(len + 1); + if(!temp->path) { + return grub_errno; + } + temp->next = fs_cache.dentry_cache.next; + fs_cache.dentry_cache.next = temp; + temp->inum = inum; + grub_strcpy(temp->path, comp); + temp->path[len] = '\0'; + temp->parent_inum = parent_inum; + temp->resolved_inum = resolved_inum; + temp->fs_root = fs_root; + //grub_printf("\n Inserted new item in cache at addr: %lx with value (comp: %s, ino: %lld, parent_ino: %lld) ", (long) temp, comp, ino, parent_inum); + return 0; +} + + + + +static int stripped_len(const char * str) +{ + int len = grub_strlen(str); + while((len > 1) && (str[len-1] == '/')) { + len = len-1; + } + return len; +} + +/* could use grubs parser for this as is used in ext2. but for now shall use this code itself */ + +static __le64 search_path(struct grub_btrfs_data * data, __le64 root_ino, const char * str, int * lnk_count, struct btrfs_inode_item * inode_item) +{ + char * comp; + int start=0, end=0; + int len=stripped_len(str); + __le64 cwd_ino = -1; + __le64 ino = -1; + __le64 resolved_ino = -1; + + + if(len == 1) { + if(grub_strcmp(str, "/") == 0) { + ino = root_ino; + cwd_ino = root_ino; + resolved_ino = get_resolved_inum(data, cwd_ino, ino, lnk_count, inode_item); + return resolved_ino; + } + return -1; + } + + comp = grub_malloc(grub_strlen(str) + 1); + if(!comp) { + perror("\n could not allocate memory to comp because:"); + return -1; + } + + cwd_ino = root_ino; + ino = root_ino; + + while(end < len) { + get_component(str, &start, &end); + grub_strcpy(comp, &str[start]); + comp[end - start] = '\0'; + if(grub_strcmp(comp, ".") == 0) { + ino = cwd_ino; + cwd_ino = get_parent(ino, data->fs_info->fs_root); + if(cwd_ino == -1) { + ino = -1; + break; + } + start = end; + continue; + } else if(grub_strcmp(comp, "..")== 0) { + ino = get_parent(cwd_ino, data->fs_info->fs_root); + cwd_ino = get_parent(ino, data->fs_info->fs_root); + if(cwd_ino == -1) { + ino = -1; + break; + } + start = end; + continue; + } + if((resolved_ino = get_ino_cache(comp, cwd_ino, data->fs_info->fs_root)) > 0) { + cwd_ino = resolved_ino; + grub_printf("\n from cache: resolved_ino: %lld ", resolved_ino); + start = end; + continue; + } + /* searching for component in dir with inode: ino */ + ino = search_comp(data, cwd_ino, comp, end - start); + if(ino < 0) { + ino = -1; + break; + } + /* subvolume related - ret_ino = parent's inode i.e ino, then the dir is a subvolume */ + if (cwd_ino == ino) { + //grub_printf("\n %s is a subvolume ", comp); + change_fs_root(data->disk, data->fs_info, comp); + } + start = end; + /* we will resolve the ino in case its a sym link and also to populate inode_item */ + resolved_ino = get_resolved_inum(data, cwd_ino, ino, lnk_count, inode_item); + if(resolved_ino <= 0) { + ino = -1; + break; + } + insert_new_cache_item(ino, resolved_ino, cwd_ino, data->fs_info->fs_root, comp); + cwd_ino = resolved_ino; + } + + if(ino > 0) { + /* we do this only to fetch the inode_item, incase it was not done + * due to previously fetching inode num from fs_cache.dentry_cache + */ + resolved_ino = get_resolved_inum(data, cwd_ino, ino, lnk_count, inode_item); + } else { + grub_errno = GRUB_ERR_FILE_NOT_FOUND; + } + + grub_free(comp); + return ino; +} + +static u32 follow_link(struct grub_btrfs_data * data, __le64 cwd_inum, __le64 * inum, int * lnk_count, struct btrfs_inode_item * inode) +{ + struct btrfs_disk_key key; + struct btrfs_path path; + struct btrfs_file_extent_item extent_item; + u64 offset, loffset; + u64 len = 0; + char link_buf[PATH_MAX]; + __le64 root_ino = 0; + struct btrfs_fs_info * fs_info = data->fs_info; + + + clear_mem((char *)&path, sizeof(struct btrfs_path)); + + key.objectid = *inum; + key.type = BTRFS_EXTENT_DATA_KEY; + key.offset = 0; + + + if(search_tree(data->disk, fs_info, fs_info->fs_root, &key, &path)) { + grub_errno = GRUB_ERR_FILE_NOT_FOUND; + return(-1); + } + grub_memcpy(&extent_item, (struct btrfs_file_extent_item *)path.data, sizeof(struct btrfs_file_extent_item)); + if (extent_item.type == BTRFS_FILE_EXTENT_INLINE) { + // verify this part + loffset = path.offsets[0] + sizeof(struct btrfs_header) \ + + path.item.offset \ + + (u32)(&(((struct btrfs_file_extent_item *) 0)->disk_bytenr)); + len = inode->size; + } else { + loffset = extent_item.disk_bytenr; + assert(extent_item.num_bytes == extent_item.disk_num_bytes); + len = extent_item.num_bytes; + if(len > inode->size) + len = inode->size; + } + offset = logical_physical(&fs_info->chunk_map, loffset); + assert(len < PATH_MAX); + grub_disk_read(data->disk, offset>>SECTOR_BITS, (offset % (1<fs_info->fs_root); + } + if(root_ino < 0) + return -1; + *inum = search_path(data, root_ino, link_buf, lnk_count, inode); + return 0; +} + +/* returns the inode number. In case of anything other than the symbolic link, + * the inode number is the same as what is passed. But in case of the symbolic + * link the inode number is different than what is passed here. This function + * will return the ultimately resolved inode number of a symbolic link + * eg: path: a/b/c/d; say b->e/f i.e path: a/e/f/c/d i.e c has to be searched + * in f. So inode number of b will be passed to this function. if b is a + * symbolic link, the inode number of f will be returned back as b points to + * e/f ultimately + * On error -1 is returned + * For DIR/REG Files etc, the same inode number is returned + * Input: cwd_inum: inode of the directory in which the items are searched + * inum: inode which we have to resolve incase its a link + * cwd_inum will be used for searching in case the link has a relative + * path + * Note: inode should be allocated memory before this function is called + */ +static __le64 get_resolved_inum(struct grub_btrfs_data * data, __le64 cwd_inum, __le64 inum, int *lnk_count, struct btrfs_inode_item * inode) +{ + struct btrfs_disk_key key; + struct btrfs_path path; + int ret = 0; + struct btrfs_fs_info * fs_info = data->fs_info; + key.objectid = inum; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + clear_mem((char *)&path, sizeof(struct btrfs_path)); + + if(search_tree(data->disk, data->fs_info, fs_info->fs_root, &key, &path)) { + grub_errno = GRUB_ERR_FILE_NOT_FOUND; + return -1; + } + grub_memcpy(inode, (struct btrfs_inode_item *)path.data, sizeof(struct btrfs_inode_item)); + inode->mode = (((inode->mode) & 0170000) >> 12); + if (inode->mode == DT_LNK) { + /* follow the link and return back the new + * object id and the new mode. the link could be a link to a + * file or to a dir + */ + *lnk_count = *lnk_count + 1; + if(*lnk_count >= MAX_LINK_COUNT) { + return -1; + } + ret = follow_link(data, cwd_inum, &inum, lnk_count, inode); + if(ret < 0) { + return ret; + } + assert(inode->mode != DT_LNK); + } + return inum; +} + + + +static __le64 search_comp(struct grub_btrfs_data * data, __le64 dirid, char * name, int name_len) +{ + struct btrfs_disk_key key; + struct btrfs_path path; + struct btrfs_dir_item *di; + + key.objectid = dirid; + key.type = BTRFS_DIR_ITEM_KEY; + key.offset = btrfs_name_hash(name, name_len); + clear_mem((char *)&path, sizeof(struct btrfs_path)); + + if(search_tree(data->disk, data->fs_info, data->fs_info->fs_root, &key, &path)) + return -1; + // walk through the dir + while(1) { + btrfs_item_key_to_cpu(&key, &path); + if (key.objectid != dirid || key.type != BTRFS_DIR_ITEM_KEY) { + break; + } + di = btrfs_match_dir_item_name(&path, name, name_len); + if (di) { + return(di->location.objectid); + } + if(next_slot(data->disk, &path)) + if(next_leaf(data->disk, data->fs_info, &key, &path)) + break; + } + return -1; +} + +static __le64 init_file(struct grub_btrfs_data * data, struct btrfs_inode_item * inode_item, const char * path) +{ + int lnk_count = 0; + __le64 inum; + __le64 root_ino = get_root_inum(); + + inum = search_path(data, root_ino, path, &lnk_count, inode_item); + if(inum < 0) { + return -1; + } + return inum; +} + +/* Open a file named NAME and initialize FILE. */ +static grub_err_t grub_btrfs_open (struct grub_file *file, const char *name) +{ + struct grub_btrfs_data * data = file->data; + __le64 inum; + + grub_dl_ref (my_mod); + + if(file->data == NULL) { + data = btrfs_init_fs(file->device->disk); + if(!data) { + return grub_errno; + } + file->data = data; + } + inum = init_file(data, &data->inode, name); + if(inum < 0) { + return grub_errno; + } + data->ino = inum; + file->size = grub_le_to_cpu64 (data->inode.size); + file->offset = 0; + return 0; +} + +static int get_item_key(struct grub_btrfs_data *data, u64 loffset, int slot, struct btrfs_disk_key * found_key) +{ + u8 buf[BTRFS_MAX_LEAF_SIZE]; + u64 offset = logical_physical(&data->fs_info->chunk_map, loffset); + struct btrfs_leaf * leaf = (struct btrfs_leaf *) buf; + + offset = offset + sizeof(struct btrfs_header); + + grub_disk_read(data->disk, offset >> SECTOR_BITS, (offset % (1<fs_info->sb_copy.leafsize - sizeof(struct btrfs_header), (char *)&leaf->items); + found_key->type = leaf->items[slot].key.type; + found_key->objectid = leaf->items[slot].key.objectid; + found_key->offset = leaf->items[slot].key.offset; + return 0; +} + + + +/* Read LEN bytes data from FILE into BUF. */ +static grub_ssize_t +grub_btrfs_read (grub_file_t file, char *buf, grub_size_t len) +{ + long long ret; + struct grub_btrfs_data *data = (struct grub_btrfs_data *) file->data; + u64 ino = data->ino; + clear_mem(buf, len); + if(len > data->inode.size) { + len = data->inode.size; + } + ret = read_file_inr(data->disk, data->fs_info, ino, len, buf); + if(ret > 0) + file->offset = ret; + return ret; +} + + +static int get_dirent_info(struct grub_btrfs_data * data, __le64 inum, struct grub_dirhook_info * info) +{ + struct btrfs_disk_key key; + struct btrfs_path path; + struct btrfs_inode_item inode; + + key.objectid = inum; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + clear_mem((char *)&path, sizeof(struct btrfs_path)); + + if(search_tree(data->disk, data->fs_info, data->fs_info->fs_root, &key, &path)) { + grub_errno = GRUB_ERR_FILE_NOT_FOUND; + return -1; + } + + inode = *(struct btrfs_inode_item *)path.data; + inode.mode = (inode.mode & 0170000) >> 12; + if(inode.mode == DT_DIR) { + info->dir = 1; + } + + return(0); +} + +static struct btrfs_dir_item * btrfs_print_dir_item_names(struct grub_btrfs_data * data, struct btrfs_path * path, int (*hook) (const char *filename, const struct grub_dirhook_info *info)) +{ + struct btrfs_dir_item *dir_item; + unsigned long name_ptr; + u32 total_len; + u32 cur; + u32 this_len; + struct grub_dirhook_info info; + + info.dir = 0; + info.mtimeset=0; + info.case_insensitive=0; + + assert(path != NULL); + dir_item = (struct btrfs_dir_item *) path->data; + total_len = path->item.size; + this_len = 0; + cur = 0; + + while (cur < total_len) { + dir_item = (struct btrfs_dir_item *)((char *)dir_item + + this_len); + this_len = sizeof(*dir_item) + + dir_item->name_len + dir_item->data_len; + name_ptr = (unsigned long)(dir_item + 1); + cur = cur + this_len; + if(dir_item->name_len <= 0) { + break; + } + if(((char *)name_ptr)[dir_item->name_len] != '\0') + ((char *)name_ptr)[dir_item->name_len] = '\0'; + /* get information about this direntry by searching for the inode*/ + get_dirent_info(data, dir_item->location.objectid, &info); + + hook((char *)name_ptr, &info); + + cur = cur + this_len; + } + return NULL; +} + +static int read_dir(struct grub_btrfs_data * data, __le64 inum, int (*hook) (const char *filename, + const struct grub_dirhook_info *info)) +{ + struct btrfs_disk_key key, found_key; + struct btrfs_path path; + struct btrfs_dir_item * dir_item; + u32 level; + + key.type = BTRFS_DIR_INDEX_KEY; + key.offset = 2; + key.objectid = inum; + + clear_mem((char *)&path, sizeof(struct btrfs_path)); + + if(search_tree(data->disk, data->fs_info, data->fs_info->fs_root, &key, &path)) { + grub_errno = GRUB_ERR_FILE_NOT_FOUND; + return -1; + } + dir_item = (struct btrfs_dir_item *) path.data; + // now we should print the dir items + level = 0; + while(1) { + assert(path.data != NULL); + + dir_item = (struct btrfs_dir_item *) path.data; + assert(dir_item != NULL); + get_item_key(data, path.offsets[0], path.slots[level], &found_key); + if(found_key.type != BTRFS_DIR_INDEX_KEY || found_key.objectid != inum) { + break; + } + btrfs_print_dir_item_names(data, &path, hook); + if(next_slot(data->disk, &path)) + if(next_leaf(data->disk, data->fs_info, &key, &path)) + break; + + } + return 0; +} + +/* Check if the path represents a dir */ +static grub_err_t grub_btrfs_dir(grub_device_t device, const char *path, + int (*hook) (const char *filename, + const struct grub_dirhook_info *info)) +{ + struct grub_btrfs_data * data; + int lnk_count = 0; + __le64 inum; + __le64 root_ino; + + grub_dl_ref (my_mod); + grub_errno = GRUB_ERR_NONE; + + data = btrfs_init_fs(device->disk); + if(!data) { + grub_dl_unref(my_mod); + return grub_errno; + } + + root_ino = get_root_inum(); + inum = search_path(data, root_ino, path, &lnk_count, &data->inode); + if(inum < 0) { + grub_errno = GRUB_ERR_FILE_NOT_FOUND; + } else if (data->inode.mode != DT_DIR) { + grub_errno = GRUB_ERR_BAD_FILE_TYPE; + } + if(!grub_errno) { + read_dir(data, inum, hook); + } + grub_dl_unref (my_mod); + grub_free(data); + return grub_errno; +} + +static grub_err_t grub_btrfs_close (grub_file_t file) +{ + if(file->data) { + grub_free (file->data); + } + grub_dl_unref (my_mod); + return GRUB_ERR_NONE; +} + +/* copy the label from the super block to the char ** label + * assign an address to * label or NULL if error + */ +static grub_err_t +grub_btrfs_label (grub_device_t device, char **label) +{ + struct grub_btrfs_data * data; + + grub_dl_ref (my_mod); + + data = btrfs_init_fs(device->disk); + if(data) { + *label = grub_strndup (data->fs_info->sb_copy.label, BTRFS_LABEL_SIZE); + grub_free(data); + } else { + *label = NULL; + } + grub_dl_unref (my_mod); + return grub_errno; +} + +/* copy the uuid from the super block to the char ** uuid + * assign an address to * uuid or NULL if error + */ +static grub_err_t grub_btrfs_uuid (grub_device_t device, char **uuid) +{ + struct grub_btrfs_data * data; + + grub_dl_ref (my_mod); + + data = btrfs_init_fs(device->disk); + if(data) { + *uuid = grub_strndup ((const char *)data->fs_info->sb_copy.fsid, BTRFS_FSID_SIZE); + grub_free(data); + } else { + *uuid = NULL; + } + grub_dl_unref (my_mod); + + return grub_errno; +} + +/* copy the mtime from the super block to the char ** tm + * assign an address to * tm or NULL if error + */ +static grub_err_t grub_btrfs_mtime (grub_device_t device, grub_int32_t *tm) +{ + *tm = 0; + device = NULL; + return grub_errno; +} + +static struct grub_fs grub_btrfs_fs = +{ + .name = "btrfs", + .dir = grub_btrfs_dir, + .open = grub_btrfs_open, + .read = grub_btrfs_read, + .close = grub_btrfs_close, + .label = grub_btrfs_label, + .uuid = grub_btrfs_uuid, + .mtime = grub_btrfs_mtime, +#ifdef GRUB_UTIL + .reserved_first_sector = 1, +#endif + .next = 0 +}; + +GRUB_MOD_INIT(btrfs) +{ + grub_fs_register (&grub_btrfs_fs); + my_mod = mod; +} + +GRUB_MOD_FINI(btrfs) +{ + free_btrfs_cache(); + grub_fs_unregister (&grub_btrfs_fs); +} + + diff --git a/fs/btrfs.h b/fs/btrfs.h new file mode 100644 index 0000000..d447fb9 --- /dev/null +++ b/fs/btrfs.h @@ -0,0 +1,385 @@ +/* + * Copyright (C) 2007 Oracle. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program 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 this program; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 021110-1307, USA. + */ + +#define BTRFS_MAGIC "_BHRfS_M" +#define le64_to_cpu(x) ((__u64) (x)) +#define BTRFS_MAX_CHUNK_ENTRIES 256 +#define BTRFS_MAX_LEAF_SIZE 4096 +#define BTRFS_MAX_LEVEL 8 +#define BTRFS_UUID_SIZE 16 +#define BTRFS_CSUM_SIZE 32 +#define BTRFS_FSID_SIZE 16 +#define BTRFS_SYSTEM_CHUNK_ARRAY_SIZE 2048 +#define BTRFS_LABEL_SIZE 256 +#define BTRFS_SUPER_MIRROR_MAX 3 +#define BTRFS_SUPER_INFO_OFFSET (64 * 1024) +#define BTRFS_SUPER_FLAG_METADUMP (1ULL << 33) + +#define BTRFS_INODE_ITEM_KEY 1 +#define BTRFS_DIR_ITEM_KEY 84 +#define BTRFS_DIR_INDEX_KEY 96 +#define BTRFS_EXTENT_DATA_KEY 108 +#define BTRFS_ROOT_ITEM_KEY 132 +#define BTRFS_ROOT_REF_KEY 156 +#define BTRFS_CHUNK_ITEM_KEY 228 + + +#define BTRFS_FS_TREE_OBJECTID 5ULL +#define BTRFS_FIRST_FREE_OBJECTID 256ULL +#define BTRFS_FIRST_CHUNK_TREE_OBJECTID 256ULL + +#define BTRFS_FILE_EXTENT_INLINE 0 +#define MAX_LINK_COUNT 5 +#define PATH_MAX 1024 + + +// temporary - copy in the original code from grub somewhere. not done +#define SECTOR_BITS 9 // sector size is 512 bytes which is 2^9 + + + +#define __le64 long long +#define __le32 int +#define __le16 short +#define u8 unsigned char +#define u16 unsigned short +#define u32 unsigned int +#define u64 unsigned long long + + +enum dirent_type { + DT_UNKNOWN = 0, + DT_FIFO = 1, + DT_CHR = 2, + DT_DIR = 4, + DT_BLK = 6, + DT_REG = 8, + DT_LNK = 10, + DT_SOCK = 12, + DT_WHT = 14, +}; + + + +struct extent_buffer{ + u64 start; + u64 dev_bytenr; + u32 len; + char * data; +}; + +struct btrfs_timespec { + __le64 sec; + __le32 nsec; +} __attribute__ ((__packed__)); + + +struct btrfs_inode_item { + /* nfs style generation number */ + __le64 generation; + /* transid that last touched this inode */ + __le64 transid; + u64 size; + __le64 nbytes; + __le64 block_group; + __le32 nlink; + __le32 uid; + __le32 gid; + __le32 mode; + __le64 rdev; + __le64 flags; + + /* modification sequence number for NFS */ + __le64 sequence; + /* + * a little future expansion, for more than this we can + * just grow the inode item and version it + */ + __le64 reserved[4]; + struct btrfs_timespec atime; + struct btrfs_timespec ctime; + struct btrfs_timespec mtime; + struct btrfs_timespec otime; +}__attribute__ ((__packed__)); + +struct btrfs_disk_key { + __le64 objectid; + u8 type; + __le64 offset; +}__attribute__ ((__packed__)); + +struct btrfs_root_item{ + struct btrfs_inode_item inode; + __le64 generation; + __le64 root_dirid; + __le64 bytenr; + __le64 byte_limit; + __le64 bytes_used; + __le64 last_snapshot; + __le64 flags; + __le32 refs; + struct btrfs_disk_key drop_progress; + u8 drop_level; + u8 level; +}__attribute__ ((__packed__)); + +struct btrfs_root{ + struct extent_buffer node; + char data[4096]; + struct btrfs_root_item root_item; + u64 objectid; + + /* data allocations are done in sectorsize units */ + u32 sectorsize; + /* node allocations are done in nodesize units */ + u32 nodesize; + /* leaf allocations are done in leafsize units */ + u32 leafsize; + /* leaf allocations are done in leafsize units */ + u32 stripesize; + + u32 type; +}__attribute__ ((__packed__)); + +/* this represents a divice in a chunk tree */ +struct btrfs_dev_item { + __le64 devid; /* internal device id */ + __le64 total_bytes; /* size of the device */ + __le64 bytes_used; + __le32 io_align; /* optimal io alignment */ + __le32 io_width; /* optimal io width */ + __le32 sector_size; /* minimal io size */ + __le64 type; /* type and info about this device */ + __le64 generation; /* expected generation */ + __le64 start_offset; /* of the partition on a device */ + + /* info for allocation decisions */ + __le32 dev_group; + + u8 seek_speed; /* 0-100 (100 is fastest) */ + u8 bandwidth; /* 0-100 (100 is fastest) */ + + u8 uuid[BTRFS_UUID_SIZE]; /* dev uuid generated by btrfs */ + u8 fsid[BTRFS_UUID_SIZE]; /* uuid of the host FS */ +} __attribute__ ((__packed__)); + + +struct btrfs_super_block{ + u8 csum[BTRFS_CSUM_SIZE]; + /* the first 4 fields must match struct btrfs_header */ + u8 fsid[BTRFS_FSID_SIZE]; /* FS specific uuid */ + u64 bytenr; /* this block number */ + __le64 flags; + + /* allowed to be different from the btrfs_header from here own down */ + __le64 magic; + u64 generation; + __le64 root; + __le64 chunk_root; + __le64 log_root; + + /* this will help find the new super based on the log root */ + __le64 log_root_transid; + __le64 total_bytes; + __le64 bytes_used; + __le64 root_dir_objectid; + __le64 num_devices; + __le32 sectorsize; + __le32 nodesize; + __le32 leafsize; + __le32 stripesize; + __le32 sys_chunk_array_size; + __le64 chunk_root_generation; + __le64 compat_flags; + __le64 compat_ro_flags; + __le64 incompat_flags; + __le16 csum_type; + u8 root_level; + u8 chunk_root_level; + u8 log_root_level; + struct btrfs_dev_item dev_item; + + char label[BTRFS_LABEL_SIZE]; + + /* future expansion */ + __le64 reserved[32]; + u8 sys_chunk_array[BTRFS_SYSTEM_CHUNK_ARRAY_SIZE]; +}__attribute__ ((__packed__)); + + +struct btrfs_stripe { + __le64 devid; + __le64 offset; + u8 dev_uuid[BTRFS_UUID_SIZE]; +} __attribute__ ((__packed__)); + + + +struct btrfs_chunk { + __le64 length; + __le64 owner; + __le64 stripe_len; + __le64 type; + __le32 io_align; + __le32 io_width; + __le32 sector_size; + __le16 num_stripes; + __le16 sub_stripes; + struct btrfs_stripe stripe; +} __attribute__ ((__packed__)); + + +/* store logical offset to physical offset mapping */ +struct btrfs_chunk_map_item { + u64 logical; + u64 length; + u64 devid; + u64 physical; +}__attribute__ ((__packed__)); + +struct btrfs_chunk_map { + struct btrfs_chunk_map_item *map; + u32 map_length; + u32 cur_length; +}__attribute__ ((__packed__)); + + +struct btrfs_fs_info { + u8 fsid[BTRFS_FSID_SIZE]; + struct btrfs_super_block sb_copy; + struct btrfs_root chunk_root; + //stores the logical bytenr of where the fs_root is stored + u64 fs_root; + u64 sb_transid; + int fd; + int sb_mirror; + struct btrfs_chunk_map chunk_map; +}__attribute__ ((__packed__)); + +/* parent_inum for resolving "..", resolved_inum for getting the resolved + * inode given an inode of a symbolic link. path is used for fetching the + * resolved inode given the path instead of the inode num*/ + +struct btrfs_cache { + __le64 inum; + __le64 resolved_inum; + __le64 parent_inum; + u64 fs_root; + char * path; + struct btrfs_cache * next; +}__attribute__((__packed__)); + +/* Information about a "mounted" btrfs filesystem. */ +struct grub_btrfs_data +{ + struct btrfs_fs_info *fs_info; + struct btrfs_inode_item inode; + grub_disk_t disk; //pointer to a disk + u64 ino; + u64 offset; + struct btrfs_cache * cache; +}__attribute__ ((__packed__)); + +struct btrfs_fs_cache +{ + struct btrfs_fs_info fs_info; + struct btrfs_cache dentry_cache; + int populated; + unsigned long disk_id; + u64 default_fs_root; +}__attribute__ ((__packed__)); + +struct btrfs_dir_item { + struct btrfs_disk_key location; + __le64 transid; + __le16 data_len; + __le16 name_len; + u8 type; +} __attribute__ ((__packed__)); + +/* Item header for per-leaf lookup */ +struct btrfs_item { + struct btrfs_disk_key key; + __le32 offset; + __le32 size; +} __attribute__ ((__packed__)); + + +/* remember how we get to a node/leaf */ +struct btrfs_path { + u64 offsets[BTRFS_MAX_LEVEL]; + int itemsnr[BTRFS_MAX_LEVEL]; + int slots[BTRFS_MAX_LEVEL]; + /* remember last slot's item and data */ + struct btrfs_item item; + u8 data[BTRFS_MAX_LEAF_SIZE]; +}__attribute__ ((__packed__)); + +struct btrfs_header { + /* these first four must match the super block */ + u8 csum[BTRFS_CSUM_SIZE]; + u8 fsid[BTRFS_FSID_SIZE]; /* FS specific uuid */ + __le64 bytenr; /* which block this node is supposed to live in */ + __le64 flags; + + /* allowed to be different from the super from here on down */ + u8 chunk_tree_uuid[BTRFS_UUID_SIZE]; + __le64 generation; + __le64 owner; + __le32 nritems; + u8 level; +} __attribute__ ((__packed__)); + +struct btrfs_leaf { + struct btrfs_header header; + struct btrfs_item items[]; +} __attribute__ ((__packed__)); + + +struct btrfs_key_ptr { + struct btrfs_disk_key key; + __le64 blockptr; + __le64 generation; +} __attribute__ ((__packed__)); + +struct btrfs_node { + struct btrfs_header header; + struct btrfs_key_ptr ptrs[]; +} __attribute__ ((__packed__)); + +struct btrfs_file_extent_item { + __le64 generation; + __le64 ram_bytes; + u8 compression; + u8 encryption; + __le16 other_encoding; /* spare for later use */ + u8 type; + u64 disk_bytenr; + __le64 disk_num_bytes; + __le64 offset; + __le64 num_bytes; +} __attribute__ ((__packed__)); + +struct btrfs_root_ref { + __le64 dirid; + __le64 sequence; + __le16 name_len; +} __attribute__ ((__packed__)); + + + -- 1.7.0.4