Re: allocation bitmaps

[Florian Sedivy]

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 
<https://developer.apple.com/library/archive/technotes/tn/tn1150.html#AllocationFile>
$Bitmap (6) - File - NTFS Documentation 
<https://flatcap.org/linux-ntfs/ntfs/files/bitmap.html>
Block Bitmap | Ext2 and Ext3 Data Structures 
<https://flylib.com/books/en/2.48.1/block_bitmap.html>
exFAT Allocation Bitmap - NTFS.com 
<https://www.ntfs.com/exfat-allocation-bitmap.htm>

Greetings, 
Florian


> Am 29.03.2021 um 16:02 schrieb Antonio Diaz Diaz <antonio@gnu.org>:
> 
> 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.