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