$date = $myarr[$index][$subindex];
[download]

where $date is a reference to an array of ten integers and ($index, $subindex) is a pair of integers each in range 0..99.

With your data, you cannot assume that $index, $subindex, or the pair ($index, $subindex) are unique. The best solution very much depends on how you need to handle these special cases. I would only be adding to your confusion if I attempted to answer your original question before you clarify this issue.

The use of an array-of-arrays, as the reference above requires, has another problem. The arrays are very sparse. Refering to your data, the entire structure only stores fifteen dates. This is not a serious problem yet, but it would not scale up well if your array size were to increase. We seldom use hashes with integer keys, but it seems to be the perfect solution to this problem.

Hi all,

Thx for replies. I won't have a chance to try the suggestions until later tonight but Bill your point re data structures is right, its a bit of an unusual lot of data (to me anyway) and I have struggled to decide how to approach it.

Its actually the 16kb sectors of a SSD which broke and I retrieved an image of the NANDs from. So I have a 'physical image' of the drive. However the translation table is partially lost and I am searching for patterns. There are around 16 million sectors ($lpn) and each lbn is sometimes present in many places (up to 20000 for a very few examples, usually 2 places). Each sector has associated with it as well as an ID I have figured out is its lba, up to 128 numbers which might indicate its validity (they might point to expired physical locations but I am not sure yet).

So I need to search it for patterns after I load it into some kind of structure. It will take a lot of memory.

I tried at first with hashes but could not get it working and after thinking about it more decided arrays would be more appropriate (although very sparse as you say).

I need 3 levels of storage, logical address ($lpn - unique), physical address ($ppn, once again unique), and inside each $ppn I need 'sub PPNs' lets call them $subppn, I don't know how unique they will be per $ppn, maybe not. Every element will be a 32 bit integer (in fact only uses 24 bits).

So each $lpn owns several $ppns, each of which owns a list of $subppns.

Structurally what this respresents is PPNs are the actual physical location of the sector, LPN is the logical location that I believe is assigned to this PPN, and subppn is a list that each PPN owns of locations I need to analyse to see what pattern emerges in relation to the PPN and LPN. Many PPNs point to a single LPN sometimes.

Then I need to do:

foreach $ppn {
   foreach $ppn {
      # do stuff
   }
}
[download]

So in other words I need to for each $lpn, then for each $ppn, check the list of $subppns against all other $ppns in this $lpn.

I hope that makes sense - I am sitting at a table with 2 screaming kids as I type this and having difficulty describing it. If it does not make sense I will provide a better description later.

I guess ideally looking at my description I would like $structure{hash}{hash}array but I could not get it to work, for similar reasons to the one I have hit above (using scalar as reference etc). Edited to correct mistake when I said PPNs are only unique per LPN - this is not the case now I think about it. Thanks, Pete

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...

To my way of thinking, the requirements to solve this are best met using a Database (eg. SQLITE).

I read the requirements as 3 x one-to-many structures (tables) - and SQL can easily accommodate the queries to find your patterns.

                "From there to here, from here to there, funny things are everywhere." -- Dr. Seuss

It now appears that your problem is much more complicated than your original post implied. I cannot help you because I do not know anything about SSD technology and cannot infer enough from your post. If no one else can help you at this point, your next step should be to find and post a link to documentation for the applicable technology. Then update you example using the exact vocabulary of the reference for function and variable names. Tell us clearly what data you have recovered and what you have to recreate. (Are you even sure that this task is possible?)
Bill

Hi again,

Maybe this rudimentary implementation will help:

use strict;
use warnings;
use feature 'say';

my %data;

for (0..14) {
    my ($lpn, $ppn, $cnt_subppn) = get_ns();
    push @{ $data{$lpn}{$ppn} }, (0..$cnt_subppn);
}

for my $lpn ( sort {$a <=> $b} keys %data ) {
    say "$lpn:";
    for my $ppn ( sort {$a <=> $b} keys %{ $data{$lpn} } ) {
        say "  $ppn:";
        for my $sub_ppn ( sort {$a <=> $b} @{ $data{$lpn}{$ppn} } ) {
            say "    $sub_ppn";
        }
    }
}


sub get_ns {
    return (int(rand(10)), int(rand(10)), int(rand(10)));
}
[download]

Note adds multiple entries for the same "sub_ppn"; you could count instead.

Example output:

0:
  7:
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
2:
  2:
    0
    1
    2
  9:
    0
    1
    2
    3
    4
3:
  5:
    0
    1
    2
    3
  8:
    0
    1
    2
    3
    4
    5
    6
    7
    8
4:
  3:
    0
    1
    2
    3
    4
    5
    6
    7
    8
  7:
    0
    1
  9:
    0
    1
    2
5:
  2:
    0
    1
    2
    3
    4
    5
6:
  8:
    0
    0
    1
    1
    2
    2
    3
    3
    4
    4
    5
    6
    7
    8
    9
  9:
    0
    1
    2
    3
    4
    5
    6
    7
    8
7:
  7:
    0
    1
    2
    3
    4
    5
    6
    7
8:
  4:
    0
    1
    2
    3
    4
    5
    6
9:
  3:
    0
    1
[download]

Hope this helps!



The way forward always starts with a minimal test.

Hi, first off, your life would be easier if you used hashes for nested data.

With

push @{ $myarr[$lpn] }, $ppn;
[download]

Probably changing the above line to

$myarr{$lpn}{$ppn} = ();
[download]

Hope this helps!

1nickt is right: few notes more

push already accept a list: push @{$myarr[$index][$subindex]}, [ @tmp ] has to be push @{$myarr[$index][$subindex]}, @tmp infact i suspect 23 is number of elements in @tmp

Also scalar(@{$myarr[$index]})-1) can be written as $#{$myarr[$index]}

L*

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

Another step, now that we know how big this image is, would be to preserve the index arrays (@PPN, @LPN) on disk using Storable after loading them. Then you can reload them quickly instead of scanning the entire 273GB image just to build up indexes before being able to actually look at anything.

The patterns in the "bank 32" map pages look suspiciously like flags of some type, likely for the preceding 4096 (=128*32) pages, with 8-bit or 16-bit values being possible fits. Is there a correlation between those values and duplicated LPNs? Perhaps only one of the LPNs in a duplicate set pairs with a particular value, suggesting that it is the valid copy? If "bank 32" holds a flag array, it is possible that the same space in other pages does in fact hold LPNs — whatever fragments of the LPN tables happened to be in the controller's memory when those maps were last written. We already know about the quality of the controller firmware, since the drive is dead.

And to everyone else reading this: since that other thread mentions why we are after this data, I do have to hold this up as an example to others of why you should put backups of important things like baby pictures on write-once optical media from a reputable manufacturer; do not use the cheapest bargain-basement garbage you can find. (The last detail is from a different case of data loss: many of Barack Obama's earliest speeches were recorded only by random members of the audience using direct-to-DVD-R camcorders — on cheap media that was found to be unreadable only a few years later after he had been elected President of the United States.) At the very minimum, store at least some backups on "spinning rust" hard disks; the technology is mature and very reliable. Avoid putting all your data in flash.

Learn from peterrowse's misfortune. The standard backup rule is "3-2-1": at least 3 copies, using at least 2 different storage technologies, with 1 off-site. ("Cloud" can be "off-site", but does not count as a storage technology, since you do not know how the data is actually stored, nor does it count as one of the 3 copies, since it can also disappear without warning.)

First re the backup, and woeful lack of it in my case - this is so so true. So much effort could have been avoided if I had. The sad thing is that this is not the first time I have experienced significant data loss due to hard drive failure. In this case although I had previously used backups, I mistakenly thought SSDs were super robust, and had moved a load of new data (these photos mainly, a few thousand of them) from camera SD cards to the SSD while I organised it ready for moving to the backup machine. I then reused the SD cards :-( The 'organising' project took longer than expected due to family illness and I forgot the vulnerable data sitting on the SSD, thinking it 'safe as houses' anyway. Meanwhile the power supply developed a fault. Only then did I discover SSDs pitfalls.

Even so my old backup solution was, I can see now, not good enough. A fire or lightning strike would for instance destroy all my data, but also many other scenarios might. I now have a system which keeps 5 copies distributed over 2 locations several miles apart, using different OSes and formatting systems. One is usually offline. I think I still have holes in the system though and am looking to change a few aspects of it. I use spinning rust now, because it can usually be recovered from, certainly a lot easier than SSD. SSD tech I now realise is a complete nightmare, since a power failure at the wrong time can cause what I have - an extremely difficult, if possible at all, to recover drive.

As for optical media, I am wary of it, having had issues in the past with copies becoming unreadable several years later. Maybe poor quality as you say though. The other problem with it is I have around 3TB of to me very important data, once you figure in the video taken over the last few years, and optical with its small size takes time to use and make several copies of. I like HDDs now because they are very large, and as you say they are extremely mature. Data recovery companies usually have excellent success with them if required, the only severe failure mode is physical damage to the disk and with multiple copies in more than one location the chances of all having physical damage is very low. And they can be tasked to do their job reliably even when I am in periods of life when I am not being reliable!

A second storage technology would be nice but I wonder about the reliability of the higher density stuff. I must admit I didn't know some can hold up to 128GB before looking it up just now, and its something to look into certainly. A few optical backups on some media which can be trusted would be certainly nice to have.

Ill get back to the technical now in another post.

So re the use of Storable, what I currently do, since I have mainly been using C up until now for the lower level stuff like accessing the disk itself, is to use a cut down disk image for holding the data. I'm probably still thinking more in C terms than perl though. So I took all the 16kb LBA blocks (131072 of them), chopped off the last 14kb or so which always contained just 0xFFFFFFFF, and wrote that to a file around 250MB in size. Then I just read it back in when I need it, not always wholly though, I might just scan a few fields using seek and pop them into an array and then seek to disk locations to get the data I need as I process it. Since theres perhaps 40 million values there, whether this approach or storable would be faster I don't know, your opinion would be appreciated. I am running the analysis on an SSD (will I never learn?! Its all backed up:-)) so seek times are short. I've assumed storable uses text to store rather than raw binary and that the overhead of this would be large, but maybe thats a false assumption.

Now as for the bank_32 business. As you say it does look like it does something significant. It doesn't look random enough for things like block write count, and the pattern seems to suggest its mapping something. I should extract those bank_32 fields and take a closer look, and I'll post some of it up here. The fact that they stored the LBAs in such a logical place, with a bitfield showing validity, a physical block start address etc all is very sensible and simple. If this was the style of the coders doing this it seems they would have put that last little bit of data somewhere accessible too. Thats not to say I am crediting them - I think the firmware choking when it sees the bad block area corrupt is poor, but they do seem to have designed the LBA id area fairly well.

Perhaps as you say the bank_32 lpn area stores data relevant to the other banks in this superblock. I can't remember the exact layout of the NANDs and the rules for writing them but the rules are restrictive re order. Maybe bank_32 needs to be the last written out of the superblock. If so it would make sense to write up to date validity data in this zone for the superblock (This is what you are saying I think).

There are 2 other areas which are worthy of thought too. One is the space for LBA 128 in the lba area, IE the last LBA 'slot'. It corresponds to the lba area itself, which is obviously redundant. It is not empty and not FFFFFFFF and it must do something. IIRC there is also another 4 bytes after this which frequently (always?) is a copy of LBA 128. I should poke around with this a bit more to see what its characteristics are.

And then there is of course this second LBA area, since it does not correlate in the way I hoped with the LBAs, what the heck is it. I wonder if I am looking at it wrong - perhaps there is a fixed offset between its numbering and the one I am using for blocks or something. It seems that stripping down the data for some duplicate LBAs and seeing if I can see any patterns manually again might be worth it at this point.