libstand/dosfs: cache FAT32 in 128 Kb blocks to save loader memory

[Mikhail.Kupchik_gmail.com]

Summary

Current implementation of dosfs in libstand reads full File Allocation Table to the RAM in the initialization code. In the extreme case of FAT32 filesystem, this structure will take up to 256-1024 Mb of loader memory, depending on the cluster size.

Proposed patch reduces libstands/dosfs memory requirements to 128 Kb for all variants of dosfs filesystem. For FAT12 and FAT16 filesystems, File Allocation Table is cached in full, as before. For FAT32, File Allocation Table is broken into the equal blocks of 128 Kilobytes (32768 entries), and only current block is cached.

In my measurements, I could not find any performance degradation caused by this patch. FAT32 cache misses occur with ~ 1/10000 probability, so this patch doesn't hurt performance much, but allows to save significant amount of memory in the loader environment. Additionally, loader time is saved by avoiding loading of non-relevant 128K-blocks from the File Allocation Table on disk.

Because per-filesystem context is now small, global FAT cache (for all instances of dosfs filesystem) is replaced by local per-instance cache.

[tsoome]

I'm sorry it took so long till I got to this one, some cstyle issues need attention.

I did also test with illumos port and loading smartos - as it has huge boot archive, it will put up nice stress on loading; the load time seems to be about the same - 35-37 seconds on 2 tests on USB2, 31 seconds on USB3 (corsair 64GB usb3 stick). Of course the spinner will add some ~5 seconds there. Also browsing and reading efi system partition from loader.efi is working as expected, so apart from cstyle, I am happy.

lib/libstand/dosfs.c

164

cstyle: opening { should be on the same line with if. Same below.

165

Also note it is good to fit in 80 chars.

194

This is not your change, but can you remove if there - our free() does check for NULL.

204

space after return.

210

space after return.

770

cstyle: { should be with if.

[Mikhail.Kupchik_gmail.com]

cstyle issues were fixed.

Also error handing at line 190 was rewritten to avoid free-without-malloc, and to reduce branching.

[tsoome]

lib/libstand/dosfs.c

165

There is another problem - normally the indentation is tab and continuation is 4 spaces, however this file is older one and built by different logic - with all cases 4 position (replaced by tabs if needed). So in this case, the tab + 4 spaces is probably the thing you need. We do not align to first function argument. hint: man style ;)

[Mikhail.Kupchik_gmail.com]

indentation fixed at line 165

[tsoome]

seems ok for me:)

[allanjude]

Approved By: allanjude

[tsoome]

Actually hold the horses a bit, I have incoming comments from illumos review and we can get this even better:)

[rm_fingolfin.org]

lib/libstand/dosfs.c

192

I was reviewing this on illumos with tsoome and noticed a problem with the free() logic here. He asked I relay this here. In general, if we're freeing something that's not from the function we allocate it, we need to think twice. It turns out that dos_mount() is only called by dos_open(). And while dos_open() does free fs (somewhat confusingly), none of the other functions that dos_open() calls do free fs, and thus we can have memory leaks in those error cases. I think this will be more straightforward if you don't try and free fs here at all and instead deal with its memory lifetime consistently in dos_open().

[Mikhail.Kupchik_gmail.com]

Freeing of DOS_FS structure was moved from dos_mount() to dos_open(), where allocation happens. Also error handling in dos_open() was improved, resource leaks fixed.

[tsoome]

Ah, right, there is an problem now with viewing the changes - if you just upload the diff, there is not enough context for phabricator to work with. arcanist does post automatically, diff needs some command line option to provide the whole file, I can not recall it off hand..

[Mikhail.Kupchik_gmail.com]

I've read this comment:
https://www.illumos.org/rb/r/403/#comment1770

Concerns about overflow in fatoff() macro in the context of fatget() function seems legit to me. It can happen for FAT32 only. Actually FAT32 entries are 28-bit, per Microsoft specification upper 4 bits should be zeroed out (when reading) and preserved (when writing).

I will make an update for fatget() function to check for overflow on entry and to zero-out upper 4 bits on exit.

[Mikhail.Kupchik_gmail.com]

Added overflow prevention to fatget() function, submitted whole file diff.

[tsoome]

lib/libstand/dosfs.c

758

u_char *p_entry;

762

no parens needed

[Mikhail.Kupchik_gmail.com]

fixed these two style issues

[tsoome]

In D9547#207910, @Mikhail.Kupchik_gmail.com wrote:

fixed these two style issues

:) thanks,

In D9547#207910, @Mikhail.Kupchik_gmail.com wrote:

fixed these two style issues

BTW: What is the current status of this work? I think it is important enough fix to finalize it properly and get it integrated:)

[Mikhail.Kupchik_gmail.com]

What is the current status of this work?

I think it's ready. It works in my environment. All feedback from reviews (here and on Illumos) was taken into account and integrated into this patch. Coding style issues were fixed.

[tsoome]

In D9547#213027, @Mikhail.Kupchik_gmail.com wrote:

What is the current status of this work?

I think it's ready. It works in my environment. All feedback from reviews (here and on Illumos) was taken into account and integrated into this patch. Coding style issues were fixed.

I just did add an small nit, see https://www.illumos.org/rb/r/403/diff/2-3/ just to be sure we wont get partial reads (which may happen with IO errors).

Note I did try to get a bit more order with u_int versus size_t use, but I did not want to walk too deep into this rabbit hole..

[Mikhail.Kupchik_gmail.com]

I just did add an small nit, see https://www.illumos.org/rb/r/403/diff/2-3/ just to be sure we wont get partial reads (which may happen with IO errors).

OK, I've integrated your changes to this patch. (I've initially dismissed this remark because I thought that device strategy routine would return some error code for short reads if called with rsize = NULL, turns out it doesn't).

There were a few small changes to your diff: cast to size_t at line 161; also ioget() shouldn't always discard error code returned by device strategy routine, ioget() should substitute EIO only for short reads when zero error code is returned from device strategy routine.

[tsoome]

LGTM.

[Mikhail.Kupchik_gmail.com]

Fix for a typo in comment: "read read" -> "read"

[tsoome]

good catch:)