linux-ext4 - Re: [PATCH 2/2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <40C8AC78-8196-41BE-B1BB-B1FB96D209C7@dilger.ca>
Date:	Mon, 10 Jan 2011 09:43:10 -0700
From:	Andreas Dilger <adilger@...ger.ca>
To:	Lukas Czerner <lczerner@...hat.com>
Cc:	"linux-ext4@...r.kernel.org" <linux-ext4@...r.kernel.org>,
	"tytso@....edu" <tytso@....edu>,
	"sandeen@...hat.com" <sandeen@...hat.com>,
	"kalpak@...geny.com" <kalpak@...geny.com>
Subject: Re: [PATCH 2/2] e2fsprogs: Add rbtree backend for bitmaps, use it instead of bitarrays

Oops, hit send by accident. 

On 2011-01-10, at 8:18, Lukas Czerner <lczerner@...hat.com> wrote:
>> This commit adds another backend to store bitmaps. It is based on
>> rbtrees and it stores just used extents of bitmaps. It means that it can
>> be more memory efficient in most cases and also with a careful use it
>> might be much faster than simple bitarrays.
>> 
>> 
>> @@ -66,7 +66,7 @@ errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs,
>>   if (fs->flags & EXT2_FLAG_64BITS)
>>       return (ext2fs_alloc_generic_bmap(fs,
>>                 EXT2_ET_MAGIC_INODE_BITMAP64,
>> -                  EXT2FS_BMAP64_BITARRAY,
>> +                  EXT2FS_BMAP64_RBTREE,
>>                 start, end, real_end, descr, ret));
> 

It would be really useful to allow runtime selection of bitmap type, ideally separately for block and inode bitmaps. This will allow easier testing of this patch on different filesystems, as well as allow users to select the bitmap the type for performance over space, if they have plenty of memory. 

Perhaps in the future by default e2fsck can select one type based on system memory vs. filesystem size?  That will be important if there continues to be a performance gap between the two types. 

>> +/*
>> 
>> +/*#define DEBUG*/
>> +
>> +#ifdef DEBUG
>> +static void print_tree(struct rb_root *root)

Probably should be DEBUG_RB or similar to allow separate enabling from other debug. 

Cheers, Andreas--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html