mkfs.simplefs

[Habbit]

Hey guys! I've started a new thread instead of asking on the SFS one because this is not about the SFS specification itself, but about my implementation.

I'm currently writing the linux mkfs.simplefs program (for Windozers: the format utility for simplefs), but I think I need a bit of imaginative thinking: I'm looking for an algorithm to determine the initial size of the index area.

Currently I've got a linear progression: 10 entries per megabyte. That means an 1.38 MiB floppy would start with 14 unused entries (896 bytes), while a 200 GiB HD would initially have 2048000 entries (125 MiB). That would yield a relatively constant starting index area size % - about 0,06% of the disk.

However, I reckon this is an ineffective approach: with it, floppies will almost surely need expanding their index area, while hard drives (or flash cards) will probably be wasting index area space. Thus, I am thinking about sub-linear progressions, but... should I use sqtr? log2? log10? ln? I am really puzzled... ???

If anyone has an idea, the constraints I work on are:

• The initial index area (which contains 64-byte entries, one or more per file depending on the file name length) must not span more than 0.25% of the drive)
• For floppies and other sizes near 1 MiB, the algorithm should not give less than 20 or 25 entries
• For a 200 GiB drive, the algorithm should not give more than 50k entries, or about 3 MiB of index area
• If possible, I'd prefer a "smooth" mathematical expression to a "chunked" algorithm or looking up into a table

Thank you all for your help

Edit: oho, i slipped one too many zero in the 200gib max entry count

[Pype.Clicker]

iirc, it is possible to extend the index area, right ? so do we actually need a smart algorithm at format-time ? why couldn't i use a 4GB SFS-DVD to store 20 avi chunks ? a 512MB SFS-USB to store 20 mp3s ...

I don't see the advantage of preparing more space for the index just because the disk is larger.

[Habbit]

Well, the index area can certainly be extended, but I think it is best if it initially has a size that allows it to manage what would be a decent amount of files, relative to the volume size.

Oh, and I didn't mention that mksimplefs does have an option for this matter: it allows the user either to select the actual number of index area entries, so if you know you'll be storing a few large files you would write something like [tt]mksimplefs /dev/hdc1 --indexentries=25[/tt] for your USB pendrive.
Another possibility - I'm not so sure about including this one - would be something like an --optimizeforfiles=[small|medium|large] switch that should affect the output of the index area size algorithm, scaling it by orders of magnitude.

[killedbydeath]

I invented a very simple algorithm to do this
entries=((sizeofdrive_inbytes)/1024) /64)*100

it gives aprox 4 MiB(327680000 entries) index for a 200 GiB drive
and 2,25 KiB index for a floppy (2304 entries) ok it's not 3MiB like you requested but you also remove some entries

Best Regards

[Habbit]

I invented a very simple algorithm to do this
entries=((sizeofdrive_inbytes)/1024) /64)*100

it gives aprox 4 MiB(327680000 entries) index for a 200 GiB drive
and 2,25 KiB index for a floppy (2304 entries) ok it's not 3MiB like you requested but you also remove some entries

Best Regards

Er... applying your formula gives me 2250 entries for a 1.38 MiB floppy, which, at 64 (index area) bytes per entry, gives 144 KiB, more than 10%. Too much, unless you meant "index area size=((sizeofdrive...", in which case the length matches.

However, the result for the 200 hard drive is indeed 327 680 000. If that meant entries, which I hope it doesn't, at 64 bytes each, the index area would be 20 GB. If that meant bytes (a 312 MiB index area), that would be able to fit about 5 million entries, instead of the five hundred thousand that I wanted.

That's why I said I needed a sub-linear progression: no matter what multipliers or divisors you choose, if you use only * and / you're making a linear progression, that is, one that will increase at the same rate always: y = m*x, which in geom represents a straight line. What I want is something on the lines of y = root_m(x) or y = log(x). That kind of formulae grow at an ever diminishing rate, which is what I want. However, since my Maths are not their best right ATM, I can't "tune" the formula myself - or, better, I'm completely lost - and I'm definitely not going to ask my sadistic professor about his.

[Habbit]

Well, I found a suitable algorithm.

Logarithms progressed far too slowly, so I started tinkering with roots: I wanted a root index between 2.5 and 3 (cubic root), but I couldn't quite find the right one: either little floppies had too many index area entries, or big hard disks had too litle. So I decided, after checking my Maths book, for a variable-index root.

For anything lower than 1 MiB, the root index is 3.5. After 1 MiB, the index decreases slowly towards 3 at 1 MiB, and then towards 2.6 at 256 MiB, remaining constant after then.

The actual formula is indexAreaEntries=floor(pow(volumeSize, 1/rootIndex))

The results are quite satisfactory, as the table shows. In it, the formula is applied to some floppies (360, 720 and 1440 KiB), an arbitraty quantity of 10 MiB, a 256 MiB ramdisk/pen drive, and some hard drives, both current (60 and 200 _decimal_ GB) and future (1 TB and 1 PB):
[tt]
Vol. size (MiB)    Idx. entries#   Idx. area size   % of volume
---------------    -------------   --------------   -----------
0.351562 MiB       39 ent          2496 bytes       0.677083%
0.703125 MiB       47 ent          3008 bytes       0.407986%
1.40625 MiB       59 ent          3776 bytes       0.256076%
10.0002 MiB       219 ent         14016 bytes       0.133664%
256.001 MiB       1745 ent       111680 bytes      0.041604%
57220.5 MiB       13978 ent       894592 bytes      0.00149099%
190735 MiB         22210 ent       1421440 bytes    0.00071072%
953674 MiB         41246 ent       2639744 bytes    0.000263974%
9.53674e+08 MiB    587802 ent      37619328 bytes    3.76193e-06%
[/tt]

The actual code is:

Code: Select all

static double initialIndexAreaEntries_rootIndex(uint64_t volumeSize)
{
   static const uint32_t TWO_TO_TWENTY_I = 1048576;
   static const double TWO_TO_TWENTY_F = 1048576.0;
   if (volumeSize < TWO_TO_TWENTY_I)
      return 3.5;
   else if (volumeSize < (10 * TWO_TO_TWENTY_I))
      return 3.55555555555556 + (-0.5 * volumeSize)/(9.0 * TWO_TO_TWENTY_F);
   else if (volumeSize < (256 * TWO_TO_TWENTY_I))
      return 3.01626016260163 + (-0.4 * volumeSize)/(246.0 * TWO_TO_TWENTY_F);
   else return 2.6;
}

static uint64_t initialIndexAreaEntries(uint64_t volumeSize)
{
   double rootIndex = initialIndexAreaEntries_rootIndex(volumeSize);
   return uint64_t(floor(pow(volumeSize, 1.0/rootIndex)));
}

And yes, I'm both quite crazy and have plenty of time to waste... ;D

[Brendan]

Hi,

The original plan was for simple/unoptimized code to begin with:

Code: Select all

index_area_size = block_size / (64 * 2)   (rounded up to nearest block)
data_area_size = 0

And then change these fields in the super-block each time a new block is needed for the index area, each time more space is needed in the data area, or each time compaction reduces the amount of used space in either area (such that the "free area" between the data area and index area is always as large as possible).

For example:

Code: Select all

uint64 allocate_new_data_blocks(uint64 blocks_needed) {
    if(data_area_end - index_area_start < blocks_needed) {
        do_compaction();
        if(data_area_end - index_area_start < blocks_needed) return NO_SPACE;
    }
    starting_block = data_area_end;
    data_area_end += blocks_needed;
    update_super_block();
    return starting_block;
}



uint64 get_free_index_entry(int blocks_needed) {
    uint64 i;

    i = current_number_of_index_entries;
    do {
        i--;
        if( check_if_entry_unused(i) == FOUND) return i;
    } while (i > 0);

    if(data_area_end - index_area_start == 0) {
        do_compaction();
        if(data_area_end - index_area_start == 0) return NO_SPACE;
    }
    i = index_area_start;
    fill_index_area_block_with_unused(i);
    index_area_start--;
    update_super_block();
    return entries_per_block - 1;
}

Of course this is the simplest possible method, which is guaranteed to perform badly....

For more complex code, and default value will either be "less than perfect" (for e.g. no way to tell if the user is going to store a single huge file or lots of tiny files) or it won't matter (one tiny file on a huge drive). Therefore I'd use something simple like "index_area_size = total_size >> 3". The sizes of these areas can be adjusted later if necessary...


Cheers,

Brendan

[Combuster]

The other alternative is (what my formatsfs does right now) is to set index area to only 128 bytes, and the data area to 0, leaving a lot of free space in between. This saves a lot of time when formatting (only first and last block have to be written) and file data and indices can be added easily: you grow the data area upward and the index area downward, as well as not having to read several MBs if you attempt to list the root of a new partition (which would require the entire index to be loaded on the first run, which is NOT fun if you just formatted a tape or the like)

And since changing the index size just means changing 4 bytes in the superblock, i think the laziness will most definately pay off.
At least its Pype.Clicker.Optimized ;D

Well, all methods have its advantages and disadvantages - we should run a benchmark somewhere to see which one of mkfs.brendan or mkfs.habbit or mkfs.combuster scores best, although a lot of people here just would want to see it work...

[Habbit]

Well, I assume a compaction is a long process, especially in floppies. With such a strange variable-root-index crazyness, I want to move some optimization into the format/mkfs program, so that, while the index area created is not too big (0.7% in the worst case, a 360 KiB 5.25" floppy), it is enough for most uses - thus avoiding compactions to expand the index area. Oh, and by the way, with my crazy algorithm, even a 60 GB disk has less than 1 MiB of index area.

But you are right: most people here (and wherever) won't care if their mkfs just divides by 8, performs a complex variable-index root or consults an astrological table to see where in the sky Arrakis is: they just want their disk formatted