| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Fri, 18 Jun 2010 10:03:13 +0200 From: Christian Stroetmann <stroetmann@...olab.com> To: Mat <jackdachef@...il.com>, linux-btrfs@...r.kernel.org, linux-fsdevel@...r.kernel.org, Linux Kernel Mailing List <linux-kernel@...r.kernel.org> Subject: Re: Unbound(?) internal fragmentation in Btrfs Aloha Mat: > On Thu, Jun 3, 2010 at 4:58 PM, Edward Shishkin<edward@...hat.com> wrote: > >> Hello everyone. >> >> I was asked to review/evaluate Btrfs for using in enterprise >> systems and the below are my first impressions (linux-2.6.33). >> >> The first test I have made was filling an empty 659M (/dev/sdb2) >> btrfs partition (mounted to /mnt) with 2K files: >> >> # for i in $(seq 1000000); \ >> do dd if=/dev/zero of=/mnt/file_$i bs=2048 count=1; done >> (terminated after getting "No space left on device" reports). >> >> # ls /mnt | wc -l >> 59480 >> >> So, I got the "dirty" utilization 59480*2048 / (659*1024*1024) = 0.17, >> and the first obvious question is "hey, where are other 83% of my >> disk space???" I looked at the btrfs storage tree (fs_tree) and was >> shocked with the situation on the leaf level. The Appendix B shows >> 5 adjacent btrfs leafs, which have the same parent. >> >> For example, look at the leaf 29425664: "items 1 free space 3892" >> (of 4096!!). Note, that this "free" space (3892) is _dead_: any >> attempts to write to the file system will result in "No space left >> on device". >> >> Internal fragmentation (see Appendix A) of those 5 leafs is >> (1572+3892+1901+3666+1675)/4096*5 = 0.62. This is even worse then >> ext4 and xfs: The last ones in this example will show fragmentation >> near zero with blocksize<= 2K. Even with 4K blocksize they will >> show better utilization 0.50 (against 0.38 in btrfs)! >> >> I have a small question for btrfs developers: Why do you folks put >> "inline extents", xattr, etc items of variable size to the B-tree >> in spite of the fact that B-tree is a data structure NOT for variable >> sized records? This disadvantage of B-trees was widely discussed. >> For example, maestro D. Knuth warned about this issue long time >> ago (see Appendix C). >> >> It is a well known fact that internal fragmentation of classic Bayer's >> B-trees is restricted by the value 0.50 (see Appendix C). However it >> takes place only if your tree contains records of the _same_ length >> (for example, extent pointers). Once you put to your B-tree records >> of variable length (restricted only by leaf size, like btrfs "inline >> extents"), your tree LOSES this boundary. Moreover, even worse: >> it is clear, that in this case utilization of B-tree scales as zero(!). >> That said, for every small E and for every amount of data N we >> can construct a consistent B-tree, which contains data N and has >> utilization worse then E. I.e. from the standpoint of utilization >> such trees can be completely degenerated. >> >> That said, the very important property of B-trees, which guarantees >> non-zero utilization, has been lost, and I don't see in Btrfs code any >> substitution for this property. In other words, where is a formal >> guarantee that all disk space of our users won't be eaten by internal >> fragmentation? I consider such guarantee as a *necessary* condition >> for putting a file system to production. >> >> Any technical comments are welcome. >> >> Thanks, >> Edward. >> >> >> Appendix A. >> ----------- >> Glossary >> >> 1. Utilization of data and(or) metadata storage. >> >> The fraction A/B, where >> A is total size in bytes of stored data and(or) metadata. >> B = N * S, where >> N is number of blocks occupied by stored data and(or) metadata. >> S is block size in bytes. >> >> 2. Internal fragmentation of data and(or) metadata storage. >> >> difference (1 - U), where U is utilization. >> >> >> Appendix B. >> ----------- >> a "period" in the dump of the fs_tree (btrfs-debug-tree /dev/sdb2) >> >> ... >> >> leaf 29982720 items 4 free space 1572 generation 8 owner 5 >> fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956 >> chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6 >> item 0 key (319 XATTR_ITEM 3817753667) itemoff 3917 itemsize 78 >> location key (0 UNKNOWN 0) type 8 >> namelen 16 datalen 32 name: security.selinux >> item 1 key (319 EXTENT_DATA 0) itemoff 1848 itemsize 2069 >> inline extent data size 2048 ram 2048 compress 0 >> item 2 key (320 INODE_ITEM 0) itemoff 1688 itemsize 160 >> inode generation 8 size 2048 block group 29360128 mode 100644 >> links 1 >> item 3 key (320 INODE_REF 256) itemoff 1672 itemsize 16 >> inode ref index 65 namelen 6 name: file64 >> leaf 29425664 items 1 free space 3892 generation 8 owner 5 >> fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956 >> chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6 >> item 0 key (320 XATTR_ITEM 3817753667) itemoff 3917 itemsize 78 >> location key (0 UNKNOWN 0) type 8 >> namelen 16 datalen 32 name: security.selinux >> leaf 29990912 items 1 free space 1901 generation 8 owner 5 >> fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956 >> chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6 >> item 0 key (320 EXTENT_DATA 0) itemoff 1926 itemsize 2069 >> inline extent data size 2048 ram 2048 compress 0 >> leaf 29986816 items 3 free space 3666 generation 8 owner 5 >> fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956 >> chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6 >> item 0 key (321 INODE_ITEM 0) itemoff 3835 itemsize 160 >> inode generation 8 size 2048 block group 29360128 mode 100644 >> links 1 >> item 1 key (321 INODE_REF 256) itemoff 3819 itemsize 16 >> inode ref index 66 namelen 6 name: file65 >> item 2 key (321 XATTR_ITEM 3817753667) itemoff 3741 itemsize 78 >> location key (0 UNKNOWN 0) type 8 >> namelen 16 datalen 32 name: security.selinux >> leaf 29995008 items 3 free space 1675 generation 8 owner 5 >> fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956 >> chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6 >> item 0 key (321 EXTENT_DATA 0) itemoff 1926 itemsize 2069 >> inline extent data size 2048 ram 2048 compress 0 >> item 1 key (322 INODE_ITEM 0) itemoff 1766 itemsize 160 >> inode generation 8 size 2048 block group 29360128 mode 100644 >> links 1 >> item 2 key (322 INODE_REF 256) itemoff 1750 itemsize 16 >> inode ref index 67 namelen 6 name: file66 >> ... >> >> Appendix C. >> ----------- >> >> D.E. Knuth, The Art of Computer Programming, vol. 3 (Sorting and Searching), >> Addison-Wesley, Reading, MA, 1973. >> >> -- >> Edward O. Shishkin >> Principal Software Engineer >> Red Hat Czech >> >> -- >> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in >> the body of a message to majordomo@...r.kernel.org >> More majordomo info at http://vger.kernel.org/majordomo-info.html >> >> > Hi to all, > > First of let me say: Btrfs really has matured a lot in the last months > and this is thanks to you guys (the developers !) > > More and more people are making it their dedicated filesystem (MeeGo) > or an option (Ubuntu, Fedora) > > So thank you very very much for your on-going efforts on making this > more and more a viable (and usable !) alternative/competition to zfs > :) > > The problems Edward mentioned sound like some very important points > (issues ?) to investigate > > I find it somewhat surprising that none of you guys commented on his mail > Me too. > I'm in no way a developer (in fact a power-user) but would > nevertheless be interested in your opinions on this matter - > especially Chris' > > Thanks ! > > Mat > > With all the best Christian Stroetmann -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists