Get address of deleted logic blocks from Filesystem

Hi all.

Is there a way to get extract the location/address of deleted logic blocks from the filesystem (database)? I am only interested in filesystems currently in use for AmigaOS 4.1.

I can imagine that defragmentation tools can do so as well. But I can't find any detailed information.

The information you want depends on the file system, naturally. What a file system does with "deleted" data is very low level, very private and subject to change with evolution.

In the file systems that I know of, the addresses of deleted data blocks are not saved anywhere, as they are simply returned to the general pool of available data blocks. Most times they are stored in a bitmap (one bit per block), which simply marks each block as "used" or "free". There is no indication of which have been used before or what each block is used *for*.

So, since you can't say where the deleted data was, and since the data blocks it used it may have been reassigned for some other purpose, the question is impossible to answer. The file system still knows while it is deleting the old file (or whatever it was), but once that is finished, there is no longer any information to say where it used to be.

Another problem is that data that has been "deleted" on an SSD no longer exists - the disk firmware actually wipes the data from memory. I don't know of any file systems in Amigaland that invoke the "delete" feature on an SSD, but it will probably happen one day.

@tonyw

I am trying to implement such feature
It is widely known as Trim but each standard has his own name for it.
Therefore am not looking for the deleted data. I want to know which locations have been deleted.
Because the issue is that the SSD doesn't know when data gets deleted. The filesystem knows in its housekeeping but doesn't issue any erase command to the storage medium. So data that is deleted by the filesystem will remain on the SSD until the location is written a next time. But unlike a classic hdd, the location has to be erased first. And this slows down the drive a lot.

With the "trim" function, you tell the SSD which blocks contain no valid data anymore and can be erased in advanced when the drive is idling.

@geennaam

Many years ago, I spent several weeks trying to implement TRIM in our standard device drivers (SiI3112/3512/3114 etc). Like you, I was intending to use the Erase feature on data blocks that were no longer in use, so the file system would "Erase" the blocks with a call to the device driver.

I couldn't get a proper TRIM response from any of the SSDs that I tried, and eventually I gave up. I could have been sending the device the wrong commands or format.

I'm sure you will agree that the Erase feature must be incorporated into the device driver, as only the driver knows whether the device is an SSD or a frisbee. My intention was to get the driver to set some status that a caller could interrogate, so that a file system would know when erasing was possible. It would also be possible to prohibit people from doing a Full Format on an SSD partition.

I did make some measurements of device speed on SSDs and frisbees, and I found that SSD Write transfer speeds were essentially constant, regardless of transfer length (which means that overheads in DMA processing and task switching were considerable). Of course, I was unable to measure the speed of Writes to "deleted" blocks Vs Writes to "occupied" blocks. However, I can say that the overall speed of file system operations is not going to be much improved by ensuring that old blocks are cleared. The speed of SSDs is such that file system operations are not limited by device speed, but by DMA transfers, overheads and housekeeping within the file system (garbage collection, cache maintenance, etc).

So to answer your query - only the file system knows which blocks have been freed and can be deleted. Once they have been freed, the file system does not know any more and there is no means for an outside entity to find out.

@tonyw

TRIM is not the same as erase. In the driver that I am writing at the moment it is called Deallocate. This is different from the erase command because erase is a direct action. Deallocate is simply flagging the blocks that can be deallocated and therefore erased in advance of a future new writes. Deallocation takes place in the background when the controller is not otherwise occupied with direct commands like read, write, erase and flush.

In the end, the driver must issue the TRIM command. But this doesn't have to be an automated action. It can be a manual action once in a while. As a matter of facts, Intel even recommends to make it a manual action only.

I do not know how you've implemented your test, but an erase action takes much longer to complete than a write action. Because of wear-levelling, it takes a long time before you will hit the perfomance penalty. However once you've hit it, the drive slows down a lot. Only TRIM/deallocate can recover such a state.
Even if the filesystem wants to write the same logical block, the wear-leveling protocol will write a different physical block first. Unless all available physical block have been written to.

Controllers that are smart enough understand that if the a logical block has been written twice, the physical block of the first write can be erased. But what complicates matters more is flash page fragmentation. Several logical blocks fit into a flash page. So only when the filesystem overwrites all logical blocks that fit within a physical flash page, the controller can erase the block on its own. But this is only the case with sequential writes. Over time during normal usage, everything gets fragmented. The reason, next to wear, that we don't defrag SSDs anymore is because the very low access times.

If a complete flash page worth of logical blocks contains deleted files. But less than 100% is written with new data, the controller still cannot erase the page. Because it has no way of knowing that the remaining blocks in the page are not valid either.

So implementing TRIM/Deallocate is impossible for the driver without filesystem info. But once the info is available, the device driver can simply have a function that allows for a manual TRIM action with a separate tool.

At least the following steps would be required to add SSD TRIM/erase support:
1. Add an option in the NSDEVTYPE_TRACKDISK standard to get the type of the disk (HD, SSD, etc.), and new TRIM, ERASE (or maybe use NSCMD_ETD_FORMAT64 for it?), etc. commands.
2. Add support for the new SSD commands in the SATA drivers, and while you are at it finally add support for 4k sector HDs (requires updated MediaToolBox, or more likely a new replacement, as well).
3. Update the filesystems to support it.

For FFS and SFS just updated drivers and an external tool for manual TRIM/erase would be possible as well as first step, you can get the unused blocks from the bitmap and simply TRIM/erase all of them. I don't know anything about NGFS.
It would probably be best to do it after defragmenting the partition, in SFS the defragmenter is built into the filesystem and can be executed by such a tool before using TRIM/erase on the unused sectors.

@joerg

It's a long time now since I looked at the problem and I've forgotten most of what I learned. However, your step 1 is fairly easy to do and I think I did it back then (whenever it was). It was step 2 that I couldn't get to work. AFAIR the drive would not accept my TRIM commands and simply returned an error status.

I don't think any change is required to implement 4k sectors *in the driver*, and certainly not in NGFS, which can use 32 kB sectors if the driver specifies such a size in the geometry. MTB is another matter, but is obsolete in any case.

Sure you can read the bitmap to identify all the unused blocks (and I was intending to mark "deleted" data as "unused"), but, as I said, I couldn't get it to work with any of the SSDs that I tried.

@tonyw

Native LBA is relative these days. NVMe drives can support up to 64 different LBA formats. It will report which of the supported LBAs will perform the best based on how the drive has been formatted. My samsung 970 EVO 1TB happens to support only one LBA (512 bytes). It's the OS memory page size that needs to be at least 4k.
I receive a WD BLACK SN770 today. So maybe this modern drive will actually support 4k pages as well.

I am not familiar with filesystems. When can I find this bitmap?
Does NGFS(2) also store this info in a bitmap?

NVME will show the maximum capacity of a namespace and the allocated capacity. I will compare this NVMe allocated value with the actual allocation reported by the filesystem. It should diverge over time without Trim.

@geennaam
Quote:SFS:
The documentation is still available on John's site: https://hjohn.home.xs4all.nl/SFS/bitmap.htm
First you have to read the root block to get the the block size used by the partition, the number of blocks (totalblocks) of the partiton (to calculate how many bitmap blocks are there) and the location of the first bitmap block (bitmapbase).

Before doing any accesses on the blocks of a file system you have to use IDOS->Inhibit(device_name (for example "DH0:"), DOSTRUE) and after you are done IDOS->Inhibit(device_name, DOSFALSE).

@tonyw
Quote:Even if everything else is supported in the drivers it has to return the correct sector size, instead of always 512 bytes like sg2's drivers did for 4k sector HDs.
This is required for MediaToolBox/HDToolBox/... to create correct partitions, with correct sector size and partition starts/ends at sector boundaries. If a driver always returns 512 bytes and the partitions created are wrong because of that two partitions may use the same 4k sector.
4k sector HDs support emulating 512 byte accesses, but of course that's slow, and atomic sector writes, as required by most file systems, may not be guarantied to work either.

Changes in the file systems are only be required to add SSD support (TRIM, etc.), not for 4k sector HDs.

Quote:

Yes it does. Like most other file systems, there is a Root Block that contains all the geometry for the partition. The "Partition Geometry" structure contains the disk addresses of all important structures. Using it, you can determine where the bitmap resides/how many blocks it contains, and from there, which blocks are currently used and unused. It is not public information, and is subject to change at any time without warning, even if nothing is written to the disk (internal housekeeping).