tree 68c838d25ae198abe0a80108a1fffbce56bb1520
parent 5db745a2836fd480d6be1b7cf388b0aad6b786ad
author Lukas Czerner <lczerner@redhat.com> 1324186173 -0500
committer Theodore Ts'o <tytso@mit.edu> 1324188760 -0500

libext2fs: add a bitmap implementation using rbtree's

For a long time we had a bitarray backend for storing filesystem
metadata bitmaps, however today this approach might hit its limits with
todays huge data storage devices, because of its memory utilization.

Bitarrays stores bitmaps as ..well, as bitmaps. But this is in most
cases highly unefficient because we need to allocate memory even for the
big parts of bitmaps we will never use, resulting in high memory
utilization especially for huge filesystem, when bitmaps might occupy
gigabytes of space.

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.

I have done some limited benchmarking and it shows that rbtree backend
consumes approx 65% less memory that bitarray on 312GB filesystem aged
with Impression (default config). This number may grow significantly
with the filesystem size, but also it may be a lot lower (even negative)
if the inodes are very fragmented (need more benchmarking).

This commit itself does not enable the use of rbtree backend.

[ Simplified the code by avoiding unneeded memory allocation and
  deallocation of del_ext.  In addition, fixed a bug discovered by the
  tst_bitmaps tests: rb_unamrk_bmap() must return true if the bit was
  previously set in bitmap, and zero otherwise -- tytso ]

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>