Re^3: Adding cols to 3d arrays

I will second NetWallah's suggestion for using a database here — it looks like you probably have too much data to fit in RAM all at once.

That does not necessarily mean SQL; you could store image:offset tuples and have objects that abstract data retrieval from disk as-needed. The big problem that I see is that you are looking at possibly (2²⁴)*(2²⁴) arrays, which are a few hundred bytes each in AV overhead. Do you have 2⁴⁸ ~ 256TiB RAM?

Start by what we actually, no question about it, know: the PPN for each page, which we know because it is the address where we read that page from the NAND array. Further, the PPNs have a contiguous range. So we can make an array of hashes: (see also perldsc)

# array mapping PPN to hash of info key => value
#  element keys:
#   LPN => logical page number stored at this block
#   XPPN => array of unknown numbers found with this block
my @PPN = ();
[download]

We probably have the LPN for each block, but we have no guarantee that LPNs in the image are contiguous, and we already know that many PPNs store different versions of the same LPN. However, LPNs are probably mostly contiguous, so we can still use an array, this time of arrays:

# array mapping LPN to array of PPNs that store copies
#  each element is an array of PPNs
my @LPN = ();
[download]

Loading these arrays should be relatively simple:

use constant NAND_PAGE_SIZE => 16384;  # or whatever...
{
  open IMAGE, '<', $image_file_name or die "$image_file_name: $!";
  local $/ = \NAND_PAGE_SIZE;
  while (<IMAGE>) {
    my $ppn = (tell IMAGE) / NAND_PAGE_SIZE;
    my $lpn = get_LPN($_);
    $PPN[$ppn] = { LPN => $lpn, XPPN => [ get_XPPNs($_) ] };
    push @{$LPN[$lpn]}, $ppn;
  }
  close IMAGE;
}
[download]

Hopefully this helps...

Comment on Re^3: Adding cols to 3d arrays - syntax Select or Download Code

Replies are listed 'Best First'.
Re^4: Adding cols to 3d arrays - syntax by peterrowse (Acolyte) on Sep 20, 2019 at 00:20 UTC
Dear all, Thanks enormously for the interest. Firstly I used your pointers to fix what I was originally trying to do and ran it tonight, which revealed essentially a null hypothesis. Secondly now I have described my problem a bit more any ideas as to how to persue it further are much appreciated, @Jcb. I should add detail since you guys are working with little. The disk, a 256 GB SSD, died and 2 recovery companies who apparently own the best gear in the business for recovering it (PC3000) said they had no luck with it (although I wonder if they were upfront about their equpiment but...). I switched it into 'engineering mode' and was able to communicate with it - running its default barefoot indilinx firmware that does not know anything about the layout and type of the NAND its connected to. Configuring the controller over the SATA bus was possible using the OpenSSD project which was luckily made for this controller and trial and error plus reading of datasheets allowed me to image the drive. The total NAND capacity is significantly larger than the drives as sold size and I can read it all, apart from the 'spare area' which is it seems used for ECC rather than data. ECC and descrambling is performed transparently by the controller once asked to do so. So I have an image around 273 GB in size. In the image are pages 16kb long with text, html etc in them. So the descrambling, join by byte and other complicated stuff is being done by the controller now I have found the correct config to send it. Its just a matter now of putting the 16kb pages (or blocks, terminology uncertain to me) back in order. Structure of the disk is as follows. Erase blocks are 128 * 16kb pages - blocks must be erased in chunks this size. This moulds the drives way of working. Minimum writable size is 16kb and needs to be done in a single operation. So collections of 128 pages are important units in the drive because this is the minimum erase size. It seems that block 128, the last one in each erase 'chunk' (128 * 16kb), contains what is clearly logical block numbers (LBAs). Their range is 0-16M or so in contrast to the 'user data' part of the disk. Looking closely at this last 16kb block it contains a 2 byte number which is the pyhsical block number / 4096, then a 16 byte bit field (lets call it bitfield_1) which I have figured out contains data to mark 16k blocks in this erase size block as invalid (when they have been written more than once in the same erase size block). Then there is 127 LPAs. Then there is another bitfield, call it bitfield_2, we will come back to. Then there is a variable number of 4 byte words again, and they are all in the range of LBAs or PBAs (0-16M), lets call this address_field_2. This is what I am currently investigating today, I feel it must be for something but I can't work out what. Bitfield_2 appears to link to this second collection of addresses - perhaps it marks them valid or not like bitfield_1 does for the LBAs (its bitwise length corresponds to the number of addresses in that appear in this second address area). I modified the stackbd kernel module to allow me to provide a map file to it and map the disk image file I made to a virtual drive according to the addresses in the LBA area. This worked well and I see large files many blocks long now in the mapped virtual drive. However around 4% of the LBAs appear more than once in the LBA area (IE the last 16kb block of each 128*16kb erase block). The duplicated LBAs must be from stale erase size blocks. SSDs move blocks around and do copy on write, meaning they simply leave the old blocks there when the OS modifies them, and copies them with changes to a new location. But they don't delete the old blocks and they can't mark them as stale. Somewhere the disk must be storing info as to which are stale, but I can't find it yet. I have recovered a fair amount of the data on this disk, large files, 10MB photos etc, perhaps 30% of it, showing that I am almost there, but these last 4% of blocks must be important blocks (directories?) that are preventing the full recovery. My first feeling was that there should be a sequence number for each erase size block, permitting ordering of the blocks by when they were written and hence revealing the valid LBAs, but I can't find it, and perhaps if the drive has multiple erase size blocks open at once that method would not work anyway. Alternatively it would perhaps make sense, when copying a logical block to a new location, to use address_field_2 in the new erase zise block to store the physical addresses of the logical block that the new block (written in this erase size block) has superceeded. That was my theory today but I could not find any evidence of it by manually checking data so I wanted to scan the whole disk address data for it. However I can now say there are far too few matches, zero exact matches and too few rough matches to indicate this might be correct. A couple of years ago when I started this I had a thread on hddguru that explained a bit more if anyone wants to take a look https://forum.hddguru.com/viewtopic.php?f=10&t=35428&mobile=mobile The drive was unfortunately formatted HFS+. The translated image I have does not mount, but hfs rescue recovers many files from it. I did wonder if my current approach fails whether I could hack the code to mount to allow it to try different logical->physical mapping during the process of attempting to mound the drive. IE keep track of what LBA it accesses and where it decides to abort and keep retrying different physcial addresses from the list of possible PPNs for each LBN until it succeeds, and continue in that way until it has successfully mounted. Any comments on such an approach would be interesting. Thanks, Pete	[reply]

Replies are listed 'Best First'.

Re^4: Adding cols to 3d arrays - syntax
by peterrowse (Acolyte) on Sep 20, 2019 at 00:20 UTC

Dear all,

Thanks enormously for the interest. Firstly I used your pointers to fix what I was originally trying to do and ran it tonight, which revealed essentially a null hypothesis. Secondly now I have described my problem a bit more any ideas as to how to persue it further are much appreciated, @Jcb.

I should add detail since you guys are working with little. The disk, a 256 GB SSD, died and 2 recovery companies who apparently own the best gear in the business for recovering it (PC3000) said they had no luck with it (although I wonder if they were upfront about their equpiment but...). I switched it into 'engineering mode' and was able to communicate with it - running its default barefoot indilinx firmware that does not know anything about the layout and type of the NAND its connected to. Configuring the controller over the SATA bus was possible using the OpenSSD project which was luckily made for this controller and trial and error plus reading of datasheets allowed me to image the drive.

The total NAND capacity is significantly larger than the drives as sold size and I can read it all, apart from the 'spare area' which is it seems used for ECC rather than data. ECC and descrambling is performed transparently by the controller once asked to do so. So I have an image around 273 GB in size.

In the image are pages 16kb long with text, html etc in them. So the descrambling, join by byte and other complicated stuff is being done by the controller now I have found the correct config to send it. Its just a matter now of putting the 16kb pages (or blocks, terminology uncertain to me) back in order.

Structure of the disk is as follows. Erase blocks are 128 * 16kb pages - blocks must be erased in chunks this size. This moulds the drives way of working. Minimum writable size is 16kb and needs to be done in a single operation. So collections of 128 pages are important units in the drive because this is the minimum erase size.

It seems that block 128, the last one in each erase 'chunk' (128 * 16kb), contains what is clearly logical block numbers (LBAs). Their range is 0-16M or so in contrast to the 'user data' part of the disk. Looking closely at this last 16kb block it contains a 2 byte number which is the pyhsical block number / 4096, then a 16 byte bit field (lets call it bitfield_1) which I have figured out contains data to mark 16k blocks in this erase size block as invalid (when they have been written more than once in the same erase size block). Then there is 127 LPAs. Then there is another bitfield, call it bitfield_2, we will come back to. Then there is a variable number of 4 byte words again, and they are all in the range of LBAs or PBAs (0-16M), lets call this address_field_2. This is what I am currently investigating today, I feel it must be for something but I can't work out what.

Bitfield_2 appears to link to this second collection of addresses - perhaps it marks them valid or not like bitfield_1 does for the LBAs (its bitwise length corresponds to the number of addresses in that appear in this second address area).

I modified the stackbd kernel module to allow me to provide a map file to it and map the disk image file I made to a virtual drive according to the addresses in the LBA area. This worked well and I see large files many blocks long now in the mapped virtual drive. However around 4% of the LBAs appear more than once in the LBA area (IE the last 16kb block of each 128*16kb erase block). The duplicated LBAs must be from stale erase size blocks. SSDs move blocks around and do copy on write, meaning they simply leave the old blocks there when the OS modifies them, and copies them with changes to a new location. But they don't delete the old blocks and they can't mark them as stale. Somewhere the disk must be storing info as to which are stale, but I can't find it yet. I have recovered a fair amount of the data on this disk, large files, 10MB photos etc, perhaps 30% of it, showing that I am almost there, but these last 4% of blocks must be important blocks (directories?) that are preventing the full recovery.

My first feeling was that there should be a sequence number for each erase size block, permitting ordering of the blocks by when they were written and hence revealing the valid LBAs, but I can't find it, and perhaps if the drive has multiple erase size blocks open at once that method would not work anyway.

Alternatively it would perhaps make sense, when copying a logical block to a new location, to use address_field_2 in the new erase zise block to store the physical addresses of the logical block that the new block (written in this erase size block) has superceeded. That was my theory today but I could not find any evidence of it by manually checking data so I wanted to scan the whole disk address data for it. However I can now say there are far too few matches, zero exact matches and too few rough matches to indicate this might be correct.

A couple of years ago when I started this I had a thread on hddguru that explained a bit more if anyone wants to take a look

https://forum.hddguru.com/viewtopic.php?f=10&t=35428&mobile=mobile

The drive was unfortunately formatted HFS+. The translated image I have does not mount, but hfs rescue recovers many files from it. I did wonder if my current approach fails whether I could hack the code to mount to allow it to try different logical->physical mapping during the process of attempting to mound the drive. IE keep track of what LBA it accesses and where it decides to abort and keep retrying different physcial addresses from the list of possible PPNs for each LBN until it succeeds, and continue in that way until it has successfully mounted. Any comments on such an approach would be interesting.

Thanks, Pete

[reply]