Re: allocation bitmaps

[Antonio Diaz Diaz]

Hello Florian!

Florian Sedivy wrote:

The necessary knowledge has to be brought by the user, as for
block-lists. After all an allocation bitmap is nothing more than an
alternative representation of a block-list. All the tools needed are
there already, for those who know what they are doing: offset, block size
and size. The only thing missing is "raw bitmap" or "binary" (optionally
little- or big-endian) as an alternative input and output format for
ddrescuelog's block-list.


I have just finished to implement your suggestion. It still needs some 
testing, but it will be present in the next version of ddrescue to be 
released in a week or so.


Ddrescuelog now can convert between mapfiles and bitmaps of blocks (big and 
little endian). The new option '-F, --format' has been added to ddrescuelog. 
It selects the input format for '--create-mapfile', or the output format for 
'--list-blocks' (list, bitmap, bitmap-be, bitmap-le).



Best regards,
Antonio.

Re: allocation bitmaps

[Florian Sedivy]

Hello Antonio! 

> Antonio Diaz Diaz  wrote:
> Hi Florian,
> 
> Florian Sedivy wrote:
>> I propose to concentrate on the raw format, just as those allocation
>> bitmaps are stored on the drive by the respective filesystem
>> specifications. That makes ddrescuelog independent of the possibly
>> proprietary formats some tools would use to store backups of them. More
>> importantly it allows reading or writing those bitmap files with direct
>> disk access tools - like ddrescue.
> 
> Even concentrating on the raw format seems to need a lot of research work. 
> For example, given an image of a partition with a file system of type ext3, 
> what is the command required to read the block bitmap(s) from the image using 
> ddrescue? What is the mapping between file system blocks and drive sectors?
> 
> As time permits, I'll try to investigate this for ext2/3/4 file systems. 
> Concrete data (command used and format of resulting bitmap file) for these or 
> other types are welcome.

I don't think ddrescue or ddrescuelog need to include knowledge about the 
location, mapping or meaning of allocation bitmaps. It also doesn't "know" 
about partition maps, volumes, volume headers, filesystems, the mapping between 
a block-list and drive sectors, how to get a block-list from a filesystem or 
where to use one, etc. 

The necessary knowledge has to be brought by the user, as for block-lists. 
After all an allocation bitmap is nothing more than an alternative 
representation of a block-list. All the tools needed are there already, for 
those who know what they are doing: offset, block size and size. The only thing 
missing is "raw bitmap" or "binary" (optionally little- or big-endian) as an 
alternative input and output format for ddrescuelog's block-list. 

Greetings, 
Florian

Re: allocation bitmaps

[Antonio Diaz Diaz]

Hi Florian,

Florian Sedivy wrote:

I propose to concentrate on the raw format, just as those allocation
bitmaps are stored on the drive by the respective filesystem
specifications. That makes ddrescuelog independent of the possibly
proprietary formats some tools would use to store backups of them. More
importantly it allows reading or writing those bitmap files with direct
disk access tools - like ddrescue.


Even concentrating on the raw format seems to need a lot of research work. 
For example, given an image of a partition with a file system of type ext3, 
what is the command required to read the block bitmap(s) from the image 
using ddrescue? What is the mapping between file system blocks and drive 
sectors?


As time permits, I'll try to investigate this for ext2/3/4 file systems. 
Concrete data (command used and format of resulting bitmap file) for these 
or other types are welcome.


Best regards,
Antonio.

Re: allocation bitmaps

[Bug reports for ddrescue, data recovery tool.]

Hola Antonio!

I propose to concentrate on the raw format, just as those allocation bitmaps 
are stored on the drive by the respective filesystem specifications. That makes 
ddrescuelog independent of the possibly proprietary formats some tools would 
use to store backups of them. More importantly it allows reading or writing 
those bitmap files with direct disk access tools – like ddrescue. 

For now I looked into HFS, HFS+, NTFS, ext2/3 and exFAT. Among these the 
allocation bitmaps are stored on disk as bare bit-arrays with no prologue or 
epilogue. All necessary variables – like the size of allocation clusters 
represented by one bit, and the disk-offset represented by the first bit in the 
bitmap – can be managed with the already available options for mapfiles and 
block-lists in ddrescuelog. The user has to bring some knowledge though, as 
e.g. ext3 has separate allocation bitmaps for each block group. 

The only additional option would have to be the bit-endianness. Because – what 
else – that differs even among the few examples I looked at. While with HFS(+) 
the first allocation cluster is represented by the most significant bit of the 
first byte (big-endian), it seems with all the other filesystems it is the 
least significant bit of the first byte (little-endian). At least there is no 
multi-byte endianness involved as far as I saw. 
So for example 11 (8+3) free blocks followed by a continuous region of 23 
(5+8+8+2) allocated blocks would look like this
HFS(+): 00 1F FF FF C0 00 …
Others: 00 F8 FF FF 03 00 …
While big-endian looks better, little-endian should be more straightforward to 
calculate. 

Some sources I found are: 
Technical Note TN1150: HFS Plus Volume Format #Allocation File 

$Bitmap (6) - File - NTFS Documentation 

Block Bitmap | Ext2 and Ext3 Data Structures 

exFAT Allocation Bitmap - NTFS.com 


Greetings, 
Florian


> Am 29.03.2021 um 16:02 schrieb Antonio Diaz Diaz :
> 
> Hi Florian,
> 
> Florian Sedivy wrote:
>> BTW, Antonio: Some filesystem tools produce or expect a volume bitmap
>> (for used space mostly). Could ddrescuelog get that as an alternative
>> in-/output format in addition to "block list"?
> 
> Sure. Do you know where I may find a specification of the format of such 
> "volume bitmap"?
> 
> Best regards,
> Antonio.