[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 2/2] btrfs support for grub-2
|
From: |
Surbhi Palande |
|
Subject: |
[PATCH 2/2] btrfs support for grub-2 |
|
Date: |
Mon, 5 Jul 2010 16:47:13 +0300 |
From: surbhi <address@hidden>
This patch is usable provided the license for this patch resolves to GPLv3.
Signed-off-by: Surbhi Palande <address@hidden>
---
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 <http://www.gnu.org/licenses/>.
+ *
+ * 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 <grub/err.h>
+#include <grub/file.h>
+#include <grub/mm.h>
+#include <grub/misc.h>
+#include <grub/disk.h>
+#include <grub/dl.h>
+#include <grub/types.h>
+#include <grub/fshelp.h>
+
+#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<<SECTOR_BITS)),
+ sizeof(struct btrfs_super_block), (char *)
&sb);
+ if (grub_errno || ret < 0)
+ break;
+ if (sb.bytenr != offset) {
+ continue;
+ }
+ if(grub_strncmp((char *)(&(sb.magic)), BTRFS_MAGIC,
+ sizeof(sb.magic))) {
+ continue;
+ }
+
+ if(i == 0) {
+ grub_memcpy(fsid, sb.fsid, sizeof(fsid));
+ }
+ else if(grub_memcmp(fsid, sb.fsid, sizeof(sb.fsid)))
+ continue;
+ found = 0;
+ if (sb.generation > 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<<SECTOR_BITS)),
sizeof(*header), (char *)header);
+ if (header->level) {/*node*/
+ grub_disk_read(disk, (offset + sizeof(*header)) >> SECTOR_BITS,
+ ((offset + sizeof(*header)) %
(1<<SECTOR_BITS)),
+ sb.nodesize - sizeof(*header), (char
*)&node->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<<SECTOR_BITS)),
+ sb.leafsize - sizeof(*header), (char
*)&leaf->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<<SECTOR_BITS)),
+ leaf->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<<SECTOR_BITS)),
+
fs_cache.fs_info.sb_copy.leafsize - sizeof(struct btrfs_header),
+ (char *)&leaf->items);
+ offset = offset + leaf->items[slot].offset;
+ path->item = leaf->items[slot];
+ grub_disk_read(disk, offset >> SECTOR_BITS,
+ (offset % (1<<SECTOR_BITS)),
+ leaf->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)), 4096, buf);
+ if(grub_errno)
+ break;
+ offset = offset + 4096;
+ buf = buf + 4096;
+ total_len = total_len + 4096;
+ } else {
+ grub_disk_read(disk, offset>>SECTOR_BITS, (offset %
(1<<SECTOR_BITS)), disk_len, buf);
+ if(grub_errno)
+ break;
+ total_len = total_len + disk_len;
+ buf = buf + disk_len;
+ disk_len = 0;
+ }
+ }
+ if(grub_errno)
+ grub_printf("\n GRUB ERROR while reading ! \n");
+ grub_printf("\n total_len read by read_extent: %lld \n", total_len);
+ return grub_errno ? -1 : total_len;
+}
+
+/* buf is already allocated "size" memory. This function handles all the
following cases
+ * when size < extent.length, size = extent.lenght and size > 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<<SECTOR_BITS)), len, link_buf);
+ link_buf[len] = '\0';
+ /* link_buf contains the path. resolve this and give back the final
+ * inode number back. If the path is absolute then start the search
+ * from the root inode. else the search should be from the current
+ * inode
+ */
+ if(link_buf[0] == '/') {
+ root_ino = get_root_inum();
+ }
+ else {
+ // relative path - need to handle '.' and '..' as special
cases.
+ if((link_buf[0] == '.') && (link_buf[1] != '.'))
+ root_ino = cwd_inum;
+ else
+ root_ino = get_parent(cwd_inum, data->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<<SECTOR_BITS)), data->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
+
+
+//<TODO> 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