Fast cluster allocation in Nextor: reviewers/testers needed!

Paragon (1083)

12-08-2020, 23:04

Hi all! Based on the feedback I received about the future of Nextor I've developed a solution for the painfully slow cluster allocation process (AKA writing to files) in FAT16 drives with little free space. Basically it's the Pencioner's idea of storing the number of the last allocated cluster instead of starting over the search every time, but extended to cover the case of freeing cluster chains (AKA deleting files).

So for now here's a pull request with the code changes for anyone willing to review it: https://github.com/Konamiman/Nextor/pull/68

In a few days (hopefully) I'll publish an alpha of a v2.1.1 including the changes. Messing up with the FAT is not a joke so I'd prefer this change to be thoroughly tested before publishing it in the form of a stable version.

So it's time to wear your reviewer hats, and stay tuned for the time to wear the tester hats!

By sdsnatcher73

Paragon (1095)

13-08-2020, 19:01

I can’t review the code but I wonder about what happens if the partition and as such FAT is modified ‘outside’ Nextor’s view. I mean I take the card/hard drive to a PC and do some modifications. Could this cause issues when the drive is in the MSX again?

By konamiman

Paragon (1083)

14-08-2020, 08:57

The next free cluster number is cached only as long as the card is in its slot in the MSX controller. If you extract the card and insert it again, Nextor will detect that as a card change and will create a new unit descriptor with the next free cluster number reset to its initial value (which is the start of the FAT).

By pgimeno

Master (230)

14-08-2020, 13:46

I left github so I can't comment there, sorry.

I wanted to note that this:

Quote:

The allocation of a cluster chain fails with a "Disk full" error (or with any other error, actually, but "Disk full" will be the most common case). This is a fail safe mechanism: if the algorithm has any flaw and trying to write to the drive causes a "Disk full" error even though there is actually some free space available, the next attempt will succeed.

is actually a necessary step and does not mean the algorithm has a flaw. It's perfectly possible that a cluster chain contains a cluster with a number lower than the first one in the chain.

Consider this scenario:

Entry index: 2   3   4   5   6   7   8   ...
FAT Content: 0   0   0   0   0   0   0   ...

Create file1 with 1 cluster:

Entry index: 2   3   4   5   6   7   8   ...
FAT Content: EOF 0   0   0   0   0   0   ...
Directory pointers:
file1 -> 2

Create file2 with 2 clusters:

Entry index: 2   3   4   5   6   7   8   ...
FAT Content: EOF 4   EOF 0   0   0   0   ...
Directory pointers:
file1 -> 2
file2 -> 3

Delete file1:

Entry index: 2   3   4   5   6   7   8   ...
FAT Content: 0   4   EOF 0   0   0   0   ...
Directory pointers:
file2 -> 3

Extend file2 by 2 clusters:

Entry index: 2   3   4   5   6   7   8   ...
FAT Content: 5   4   2   6   EOF 0   0   ...
Directory pointers:
file2 -> 3

Now file2's chain contains a cluster with a number lower than the first one, therefore when deleting file2, if UD_ACLU is initialized to the first cluster in the chain (cluster 3), there will be a free cluster with a lower value (cluster 2) which must be considered as the disk becomes fuller.

Whether it's worth checking for the lowest cluster in the loop that frees a cluster chain, instead of always taking the first one, I leave up for you to decide. It's not usual that files are extended, which is the only scenario I can imagine where that can happen.

By konamiman

Paragon (1083)

14-08-2020, 14:08

pgimeno wrote:

It's perfectly possible that a cluster chain contains a cluster with a number lower than the first one in the chain.

This is an excellent point that I had completely missed. Indeed, the pointer should be updated to the lowest cluster number freed, not to the start of the freed chain. Many thanks!

I'm so glad that I decided to ask reviews for this before going and implementing it!

By konamiman

Paragon (1083)

23-08-2020, 18:33

And that's it! v2.1.1 alpha with the improved cluster allocation implemented. Please get it and give it a try! (as this is a significant change in how data is written to disk, please backup your data first, or use test data).

By konamiman

Paragon (1083)

30-08-2020, 15:55

Turns out that v2.1.1 alpha 1 had a critical bug. Here's v2.1.1 alpha 2 fixing it for anyone willing to give it a try. Thanks!