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: Sat, 19 Jun 2010 00:04:06 +0200 From: Edward Shishkin <edward@...hat.com> To: Chris Mason <chris.mason@...cle.com>, Edward Shishkin <edward@...hat.com>, Jamie Lokier <jamie@...reable.org>, Edward Shishkin <edward.shishkin@...il.com>, Mat <jackdachef@...il.com>, LKML <linux-kernel@...r.kernel.org>, linux-fsdevel@...r.kernel.org, Ric Wheeler <rwheeler@...hat.com>, Andrew Morton <akpm@...ux-foundation.org>, Linus Torvalds <torvalds@...ux-foundation.org>, The development of BTRFS <linux-btrfs@...r.kernel.org> Subject: Balancing leaves when walking from top to down (was Btrfs:...) Chris Mason wrote: > On Fri, Jun 18, 2010 at 09:29:40PM +0200, Edward Shishkin wrote: > >> Jamie Lokier wrote: >> >>> Edward Shishkin wrote: >>> >>>> If you decide to base your file system on some algorithms then please >>>> use the original ones from proper academic papers. DO NOT modify the >>>> algorithms in solitude: this is very fragile thing! All such >>>> modifications must be reviewed by specialists in the theory of >>>> algorithms. Such review can be done in various scientific magazines of >>>> proper level. >>>> >>>> Personally I don't see any way to improve the situation with Btrfs >>>> except full redesigning the last one. If you want to base your file >>>> system on the paper of Ohad Rodeh, then please, use *exactly* the >>>> Bayer's B-trees that he refers to. That said, make sure that all >>>> records you put to the tree has equal length and all non-root nodes of >>>> your tree are at least half filled. >>>> >>> First, thanks Edward for identifying a specific problem with the >>> current btrfs implementation. >>> >> Hello Jamie. >> >> >>> I've studied modified B-trees quite a lot and know enough to be sure >>> that they are quite robust when you modify them in all sorts of ways. >>> >> Which property is robust? >> >> >>> Moreover, you are incorrect to say there's an intrinsic algorithmic >>> problem with variable-length records. It is not true; if Knuth said >>> so, Knuth was mistaken. >>> >> I didn't say about intrinsic algorithmic problems :) >> I just repeat (after Knuth et al) that B-trees with variable-length >> records don't >> have any sane boundary for internal fragmentation. The common idea >> is that if we >> don't want Btrfs to be in infinite development stage, then we should >> choose some >> *sane* strategy (for example the paper of Ohad Rodeh) and strictly >> adhere this in >> future. >> > > Again, other than the inline file data, what exactly do you believe > needs to change? 1. getting rid of inline extents; 2. new formats for directory and xattr items to not look like a train, which is able to occupy the whole leaf; 3. make sure we do pro-active balancing like it is described in the paper. Sorry, I don't see other ways for now.. > Top down balancing vs balancing on insertion doesn't > impact our ability to maintain full leaves. The current code is clearly > choosing not to merge two leaves that it should have merged, which is > just a plain old bug. > How are you going to balance leaves when walking from top to down? Suppose 1) and 2) above are not satisfied and having arrived to the leaf level we see a number of items of variable length. What will we do to keep leaves full? Could you please provide a sketch of the algorithm? Thanks! -- Edward O. Shishkin Principal Software Engineer Red Hat Czech -- 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