* Fwd: Update: btrfs patch for grub2 with annotations
@ 2010-08-11 12:35 Surbhi Palande
0 siblings, 0 replies; only message in thread
From: Surbhi Palande @ 2010-08-11 12:35 UTC (permalink / raw)
To: Chris Mason, Robbie Williamson, Colin Watson, grub-devel,
Peter Anvin
[-- Attachment #1: Type: text/plain, Size: 4114 bytes --]
Hi Chris,
I was wondering if you had a chance to look at the btrfs patch and if it
could be accepted with a GPLv2+ license at least?
Thanks a lot!
Warm Regards,
Surbhi.
P/S: I have copy pasted the original message sent to grub-devel@gnu.org
at the end of this email.
-------- Original Message --------
Subject: btrfs patch for grub2 with annotations
Date: Wed, 14 Jul 2010 22:15:51 +0300
From: Surbhi Palande <surbhi.palande@canonical.com>
Reply-To: surbhi.palande@canonical.com
Organization: Canonical
To: chris.mason@oracle.com
Hi Chris,
As discussed on the #btrfs, I am sending you the btrfs patches for
grub2. I have also attached a btrfs-annotation.txt with a list of
functions and description of whether they are different or based on some
other implementation.
If the code based on syslinux
(http://www.kernel.org/pub/linux/utils/boot/syslinux/syslinux-4.01.tar.bz2)
cannot be accepted under GPLv2+, then I will rewrite that code either
entirely or base it on the patch in grub-legacy.
I however do hope that this code can at least passed off as GPLv2+.
Thanks a lot!
Warm Regards,
Surbhi.
-------- Original Message Copy Pasted here --------
Subject: btrfs support for grub2
Date: Wed, 5 Jul 2010
From: Surbhi Palande <surbhi.palande@canonical.com>
Reply-To: surbhi.palande@canonical.com
Organization: Canonical
To: grub-devel@gnu.org
Hi All,
I am attaching two patches along with this email for enabling btrfs
support in grub2. Please note that the licensing for this patch needs to
be sorted out as grub-2 is at GPL-v3 and btrfs support in the linux
kernel is at GPL-v2.
I have referred to the btrfs code in the kernel, btrfs-tools, sys-linux
and legacy grub. I have used some code from sys-linux's btrfs support
(written by Alek Du). As agreed in #btrfs irc, I am sending this email
to Chris Mason to find out whether the code in the patch can be passed
under GPLv3.
The patch provides btrfs support for the following:
1) single device.
2) subvolumes.
I have tested this patch using grub-fstest (using subcommands-ls, hex
and crc). *I have not yet tested it by booting through the btrfs partition*
This is the first version of the patch and I have listed a few changes
that could be made:
1) change the storage identifiers to the grub compliant ones.
2) linkcount for symbolic links needs better handling
I have a decompression support for btrfs-grub2 in an almost ready state.
I will send that patch after these patches are sorted out.
Please do let me know your comments. I will be glad to incorporate the
changes inorder to get btrfs support into grub-2.
Thanks for your time!
Warm Regards,
Surbhi.
P/S:
Following is a brief procedure with some eg. of how one can test these
patches in qemu:
1) used an image created with "dd" as a hdb for qemu:
kvm -hda ubuntu.img -hdb btrfs.img -m 512 -net nic,macaddr='DE:AD:BE:EF::'
-net tap
This is detected as /dev/sdb in qemu.
2) Booted through qemu and then did: fdisk -l /dev/sdb, created a partition
table in /dev/sdb
4) Used mkfs.btrfs -A <byte_num> to create a filesystem at a byte
reflected by
the "start" field of the output of fdisk -ul
and then mounted this btrfs img/partition using mount -o offset=<byte-num>.
Populated the fs.
5) compiled grub-2 with this patch
6) tested using this command:
a) grub-fstest /dev/sdb ls '(loop0,1)/' etc.
Subvolumes can be created as follows:
1) mount -t btrfs /dev/sdb /mnt/btrfs
2) btrfsctl -S subvol1 /mnt
3) mount -t btrfs -o subvol=subvol1 /dev/sdb /mnt/btrfs_subvol
4) create some files, dir, links on /mnt/btrfs_subvol
Now you can check the contents of the subvolume by using
./grub_fstest /dev/sdb ls '(loop0,1)/subvol1/'
surbhi (2):
config support for btrfs
btrfs support for grub-2
conf/common.rmk | 40 +-
conf/i386-pc.rmk | 4 +-
conf/sparc64-ieee1275.rmk | 5 +-
fs/btrfs.c | 1434
+++++++++++++++++++++++++++++++++++++++++++++
fs/btrfs.h | 385 ++++++++++++
5 files changed, 1843 insertions(+), 25 deletions(-)
create mode 100644 fs/btrfs.c
create mode 100644 fs/btrfs.h
[-- Attachment #2: btrfs-annotation.txt --]
[-- Type: text/plain, Size: 1809 bytes --]
code from btrfs-tools/sys-linux (which happens to be same/very similar to each other)
1) btrfs_sb_offset() - same as btrfs-tools::btrfs_sb_offset()
2) bin_search() - same as generic_bin_search() in btrfs-tools (or bin_search() in btrfs patch for grub-legacy)
3) btrfs_chunk_item_size() - same as btrfs-tools::btrfs_chunk_item_size()
4) btrfs_read_sys_chunk_array() - based on btrfs-tools::btrfs_read_sys_array() - (single device support), except that insert_map() is used to keep the mappings in an array instead of inserting in tree.
5) btrfs_read_chunk_tree() - based on btrfs-tools::btrfs_read_chunk_tree() (single device support), except that insert_map() is used to keep the mappings in an array instead of inserting in tree.
code from syslinux:
1) logical_physical()
2) btrfs_comp_keys_type()
4) search_tree()
5) next_leaf()
6) insert_map()
from the linux kernel:
1) btrfs_name_hash() - same as linux-2.6::btrfs_name_hash()
2) btrfs_comp_keys() - same as linux-2.6::btrfs_comp_cpu_keys()
what is different:
1) btrfs_get_fs_tree() - name is same as in syslinux, but the implementation is different
2) cache implementation()
3) btrfs_init_fs()
4) get_component()
5) btrfs_match_dir_item_name()
6) read_extent()
7) read_file_inr()
8) change_fs_root()
9) get_ino_cache()
10) get_parent()
11) insert_new_cache_item()
12) stripped_len()
13) search_path()
14) follow_link()
15) get_resolved_inum()
16) search_comp()
17) init_file()
18) grub_btrfs_open()
19) get_item_key()
20) grub_btrfs_read()
21) get_dirent_info()
22) btrfs_print_dir_item_names()
23) read_dir()
24) grub_btrfs_dir()
25) grub_btrfs_close()
26) grub_btrfs_label()
27) grub_btrfs_uuid()
28) grub_btrfs_mtime()
* Every function that starts with grub is grub dependent. Every other function could be used by other boot loaders as well.
[-- Attachment #3: 0001-config-support-for-btrfs.patch --]
[-- Type: text/x-patch, Size: 8350 bytes --]
From b45ad1339b7a35b5e13ed1911bef1d97444f4d85 Mon Sep 17 00:00:00 2001
Message-Id: <b45ad1339b7a35b5e13ed1911bef1d97444f4d85.1278336083.git.Surbhi.Palande@canonical.com>
In-Reply-To: <cover.1278336083.git.Surbhi.Palande@canonical.com>
References: <cover.1278336083.git.Surbhi.Palande@canonical.com>
From: surbhi <csurbhi@gmail.com>
Date: Mon, 5 Jul 2010 15:21:58 +0300
Subject: [PATCH 1/2] config support for btrfs
Signed-off-by: surbhi <Surbhi.Palande@canonical.com>
---
conf/common.rmk | 40 ++++++++++++++++++++--------------------
conf/i386-pc.rmk | 4 ++--
conf/sparc64-ieee1275.rmk | 5 ++---
3 files changed, 24 insertions(+), 25 deletions(-)
diff --git a/conf/common.rmk b/conf/common.rmk
index 1af14f7..f4532f4 100644
--- a/conf/common.rmk
+++ b/conf/common.rmk
@@ -33,7 +33,7 @@ grub_probe_SOURCES = gnulib/progname.c util/grub-probe.c \
fs/hfsplus.c fs/iso9660.c fs/udf.c fs/jfs.c fs/minix.c \
fs/nilfs2.c fs/ntfs.c fs/ntfscomp.c fs/reiserfs.c \
fs/sfs.c fs/ufs.c fs/ufs2.c fs/xfs.c fs/afs.c \
- fs/afs_be.c fs/befs.c fs/befs_be.c fs/tar.c \
+ fs/afs_be.c fs/befs.c fs/befs_be.c fs/tar.c fs/btrfs.c \
\
partmap/msdos.c partmap/bsdlabel.c partmap/apple.c \
partmap/sun.c partmap/sunpc.c partmap/gpt.c \
@@ -57,7 +57,7 @@ grub_fstest_SOURCES = gnulib/progname.c util/grub-fstest.c kern/emu/hostfs.c \
fs/hfsplus.c fs/iso9660.c fs/udf.c fs/jfs.c fs/minix.c \
fs/nilfs2.c fs/ntfs.c fs/ntfscomp.c fs/reiserfs.c fs/sfs.c \
fs/ufs.c fs/ufs2.c fs/xfs.c fs/afs.c fs/afs_be.c fs/befs.c \
- fs/befs_be.c fs/tar.c \
+ fs/befs_be.c fs/tar.c fs/btrfs.c \
\
kern/partition.c partmap/msdos.c partmap/bsdlabel.c \
partmap/apple.c partmap/sun.c partmap/sunpc.c partmap/gpt.c \
@@ -69,8 +69,7 @@ grub_fstest_SOURCES = gnulib/progname.c util/grub-fstest.c kern/emu/hostfs.c \
# For grub-mkfont.
ifeq ($(enable_grub_mkfont), yes)
bin_UTILITIES += grub-mkfont
-grub_mkfont_SOURCES = gnulib/progname.c util/grub-mkfont.c util/misc.c \
- unidata.c kern/emu/misc.c
+grub_mkfont_SOURCES = gnulib/progname.c util/grub-mkfont.c util/misc.c kern/emu/misc.c
grub_mkfont_CFLAGS = $(freetype_cflags)
grub_mkfont_LDFLAGS = $(freetype_libs)
endif
@@ -96,7 +95,6 @@ grub_script_check_SOURCES = gnulib/progname.c gnulib/getdelim.c gnulib/getline.c
kern/misc.c kern/env.c grub_script.tab.c \
grub_script.yy.c
grub_script_check_CFLAGS = $(GNULIB_UTIL_CFLAGS)
-grub_script_check_DEPENDENCIES = grub_script.tab.h
MOSTLYCLEANFILES += symlist.c kernel_syms.lst
DEFSYMFILES += kernel_syms.lst
@@ -207,9 +205,6 @@ grub-mkconfig_SCRIPTS = 00_header 30_os-prober 40_custom 41_custom
ifneq (, $(host_kernel))
grub-mkconfig_SCRIPTS += 10_$(host_kernel)
endif
-ifeq (linux, $(host_kernel))
-grub-mkconfig_SCRIPTS += 20_linux_xen
-endif
CLEANFILES += $(grub-mkconfig_SCRIPTS)
@@ -233,7 +228,7 @@ CLEANFILES += grub-reboot
pkglib_MODULES += fshelp.mod fat.mod ufs1.mod ufs2.mod ext2.mod ntfs.mod \
ntfscomp.mod minix.mod hfs.mod jfs.mod iso9660.mod xfs.mod \
affs.mod sfs.mod hfsplus.mod reiserfs.mod cpio.mod tar.mod \
- udf.mod afs.mod afs_be.mod befs.mod befs_be.mod
+ udf.mod afs.mod afs_be.mod befs.mod befs_be.mod btrfs.mod
# For fshelp.mod.
fshelp_mod_SOURCES = fs/fshelp.c
@@ -356,6 +351,12 @@ befs_be_mod_SOURCES = fs/befs_be.c
befs_be_mod_CFLAGS = $(COMMON_CFLAGS)
befs_be_mod_LDFLAGS = $(COMMON_LDFLAGS)
+# For btrfs.mod.
+btrfs_mod_SOURCES = fs/btrfs.c
+btrfs_mod_CFLAGS = $(COMMON_CFLAGS)
+btrfs_mod_CFLAGS += -fno-strict-aliasing
+btrfs_mod_LDFLAGS = $(COMMON_LDFLAGS)
+
# Partition maps.
pkglib_MODULES += part_amiga.mod
@@ -442,7 +443,7 @@ scsi_mod_LDFLAGS = $(COMMON_LDFLAGS)
pkglib_MODULES += minicmd.mod extcmd.mod hello.mod \
ls.mod cmp.mod cat.mod help.mod search.mod loopback.mod \
configfile.mod echo.mod \
- test.mod blocklist.mod hexdump.mod \
+ terminfo.mod test.mod blocklist.mod hexdump.mod \
read.mod sleep.mod loadenv.mod crc.mod parttool.mod \
msdospart.mod memrw.mod normal.mod \
gptsync.mod true.mod probe.mod password.mod \
@@ -491,8 +492,7 @@ gfxmenu_mod_SOURCES = \
gfxmenu/gui_progress_bar.c \
gfxmenu/gui_util.c \
gfxmenu/gui_string_util.c \
- gfxmenu/named_colors.c \
- gfxmenu/font.c
+ gfxmenu/named_colors.c
gfxmenu_mod_CFLAGS = $(COMMON_CFLAGS)
gfxmenu_mod_LDFLAGS = $(COMMON_LDFLAGS)
@@ -568,13 +568,10 @@ configfile_mod_SOURCES = commands/configfile.c
configfile_mod_CFLAGS = $(COMMON_CFLAGS)
configfile_mod_LDFLAGS = $(COMMON_LDFLAGS)
-ifneq ($(platform), ieee1275)
# For terminfo.mod.
-pkglib_MODULES += terminfo.mod
terminfo_mod_SOURCES = term/terminfo.c term/tparm.c
terminfo_mod_CFLAGS = $(COMMON_CFLAGS)
terminfo_mod_LDFLAGS = $(COMMON_LDFLAGS)
-endif
# For blocklist.mod.
blocklist_mod_SOURCES = commands/blocklist.c
@@ -627,15 +624,12 @@ keystatus_mod_CFLAGS = $(COMMON_CFLAGS)
keystatus_mod_LDFLAGS = $(COMMON_LDFLAGS)
# For normal.mod.
-ifneq (, $(FONT_SOURCE))
-normal/charset.c_DEPENDENCIES = widthspec.h
-endif
normal_mod_SOURCES = normal/main.c normal/cmdline.c normal/dyncmd.c \
normal/auth.c normal/autofs.c \
normal/color.c normal/completion.c normal/datetime.c normal/menu.c \
- normal/menu_entry.c normal/menu_text.c normal/charset.c \
+ normal/menu_entry.c normal/menu_text.c \
normal/misc.c normal/crypto.c normal/term.c normal/context.c \
- script/main.c script/script.c script/execute.c unidata.c \
+ script/main.c script/script.c script/execute.c \
script/function.c script/lexer.c grub_script.tab.c grub_script.yy.c
normal_mod_CFLAGS = $(COMMON_CFLAGS) $(POSIX_CFLAGS) -Wno-error
normal_mod_LDFLAGS = $(COMMON_LDFLAGS)
@@ -709,6 +703,7 @@ png_mod_SOURCES = video/readers/png.c
png_mod_CFLAGS = $(COMMON_CFLAGS)
png_mod_LDFLAGS = $(COMMON_LDFLAGS)
+
# Misc.
pkglib_MODULES += gzio.mod elf.mod
@@ -762,6 +757,11 @@ setjmp_mod_SOURCES = lib/$(target_cpu)/setjmp.S
setjmp_mod_ASFLAGS = $(COMMON_ASFLAGS)
setjmp_mod_LDFLAGS = $(COMMON_LDFLAGS)
+pkglib_MODULES += charset.mod
+charset_mod_SOURCES = lib/charset.c
+charset_mod_CFLAGS = $(COMMON_CFLAGS)
+charset_mod_LDFLAGS = $(COMMON_LDFLAGS)
+
pkglib_MODULES += regexp.mod
regexp_mod_SOURCES = gnulib/regex.c commands/regexp.c
regexp_mod_CFLAGS = $(COMMON_CFLAGS) $(GNULIB_CFLAGS)
diff --git a/conf/i386-pc.rmk b/conf/i386-pc.rmk
index 96058e8..aca59a4 100644
--- a/conf/i386-pc.rmk
+++ b/conf/i386-pc.rmk
@@ -73,7 +73,7 @@ grub_setup_SOURCES = gnulib/progname.c util/i386/pc/grub-setup.c \
fs/hfsplus.c fs/iso9660.c fs/udf.c fs/jfs.c fs/minix.c \
fs/nilfs2.c fs/ntfs.c fs/ntfscomp.c fs/reiserfs.c \
fs/sfs.c fs/ufs.c fs/ufs2.c fs/xfs.c fs/afs.c \
- fs/afs_be.c fs/befs.c fs/befs_be.c fs/tar.c \
+ fs/afs_be.c fs/befs.c fs/befs_be.c fs/tar.c fs/btrfs.c \
\
partmap/msdos.c partmap/bsdlabel.c partmap/sunpc.c \
partmap/gpt.c \
@@ -147,7 +147,7 @@ linux_mod_CFLAGS = $(COMMON_CFLAGS)
linux_mod_LDFLAGS = $(COMMON_LDFLAGS)
pkglib_MODULES += xnu.mod
-xnu_mod_SOURCES = loader/xnu_resume.c loader/i386/xnu.c \
+xnu_mod_SOURCES = loader/xnu_resume.c loader/i386/xnu.c loader/i386/pc/xnu.c \
loader/macho32.c loader/macho64.c loader/macho.c loader/xnu.c
xnu_mod_CFLAGS = $(COMMON_CFLAGS)
xnu_mod_LDFLAGS = $(COMMON_LDFLAGS)
diff --git a/conf/sparc64-ieee1275.rmk b/conf/sparc64-ieee1275.rmk
index cb6b070..0c7e29e 100644
--- a/conf/sparc64-ieee1275.rmk
+++ b/conf/sparc64-ieee1275.rmk
@@ -31,8 +31,7 @@ kernel_img_SOURCES = kern/sparc64/ieee1275/crt0.S kern/ieee1275/cmain.c \
kern/sparc64/ieee1275/init.c \
kern/ieee1275/mmap.c \
term/ieee1275/ofconsole.c \
- kern/ieee1275/openfw.c term/terminfo.c term/tparm.c \
- disk/ieee1275/ofdisk.c \
+ kern/ieee1275/openfw.c disk/ieee1275/ofdisk.c \
kern/parser.c kern/partition.c kern/env.c kern/$(target_cpu)/dl.c \
kern/generic/millisleep.c kern/time.c \
symlist.c kern/$(target_cpu)/cache.S
@@ -57,7 +56,7 @@ grub_setup_SOURCES = util/sparc64/ieee1275/grub-setup.c \
fs/hfsplus.c fs/iso9660.c fs/udf.c fs/jfs.c fs/minix.c \
fs/nilfs2.c fs/ntfs.c fs/ntfscomp.c fs/reiserfs.c \
fs/sfs.c fs/ufs.c fs/ufs2.c fs/xfs.c fs/afs.c \
- fs/afs_be.c fs/befs.c fs/befs_be.c fs/tar.c \
+ fs/afs_be.c fs/befs.c fs/befs_be.c fs/tar.c fs/btrfs.c \
\
partmap/amiga.c partmap/apple.c partmap/msdos.c \
partmap/bsdlabel.c partmap/sun.c partmap/acorn.c \
--
1.7.0.4
[-- Attachment #4: 0002-btrfs-support-for-grub-2.patch --]
[-- Type: text/x-patch, Size: 63088 bytes --]
From 39b8bbd853911fa0ea91265744b19779c24128b8 Mon Sep 17 00:00:00 2001
Message-Id: <39b8bbd853911fa0ea91265744b19779c24128b8.1278336083.git.Surbhi.Palande@canonical.com>
In-Reply-To: <cover.1278336083.git.Surbhi.Palande@canonical.com>
References: <cover.1278336083.git.Surbhi.Palande@canonical.com>
From: surbhi <csurbhi@gmail.com>
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 <Surbhi.Palande@canonical.com>
---
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: Surbhi.Palande@canonical.com
+ * 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
^ permalink raw reply related [flat|nested] only message in thread
only message in thread, other threads:[~2010-08-11 12:36 UTC | newest]
Thread overview: (only message) (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2010-08-11 12:35 Fwd: Update: btrfs patch for grub2 with annotations Surbhi Palande
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.