PUZZLING MATH PUZZLE

[BigDumbDinosaur]

I’ve been working on the details for my 816NIX filesystem that I have in development. As any experienced programmer knows, 25 percent of the code does the work and the other 75 percent keeps boneheaded user actions from breaking the 25 percent.

Anyhow, I want to make the filesystem generator program as fool-resistant as I can, which includes preventing the user from entering combinations of parameters that can’t work. In the process, I’m stumbling over what would seem to be a simple math problem. So I am looking for some help.

I'm trying to work out how to apportion storage space between data objects (“objects”) and a bitmap that tracks them. Both objects and bitmap are stored in 1024 byte fixed-size blocks. The objects are 128 bytes each, hence 8 can fit in a block. There is a one-for-one correspondence between a bit in the bitmap and an object.

The number of blocks required to store a given number of objects would be:

Code: Select all

OB = OJ ÷ 8 + ((OJ % 8) > 0)

...in which...

• OJ = number of objects
  OB = number of object blocks
  % = modulus operator

Given that there are 8192 bits in a 1024-byte block, the required number of bitmap blocks for a given number of objects would be:

Code: Select all

BB = OJ ÷ r + ((OJ % r) > 0)

...in which...

• BB = number of bitmap blocks
  r = 8192 (bits in a block)

Therefore, storage requirements for a given number of objects would be:

Code: Select all

S = OB + BB

in which:

• S = required blocks

All arithmetic operations are on unsigned integers. Division behaves as INT(OJ / r) would in BASIC. My division function also reports if the remainder is non-zero, which makes it easy to determine if the result of an expression such as (OJ % r) > 0 is true or false.

The puzzle is this: I already know the value of S—it is indirectly determine by the filesystem size entered by the user—and ultimately wish to solve for OJ. Given that an immutable relationship between OJ and BB is defined in the second equation, you'd think this would be straightforward. It isn't...at least for me. Any suggestions?

Thanks!

[BigEd]

I think it might be the case that
OB = OJ ÷ 8 + ((OJ % 8) > 0)
could alternately be written as
OB = (OJ+7) ÷ 8
and similarly for BB. If so, perhaps that makes it easier to rearrange the formula.

[Martin A]

I came up with:

Code: Select all

BB = (OJ div 8192) +1 (if remainder non zero)
OB = (OJ DIV 8) +1 (if remainder non zero)

Worst case remainders are both non zero

AS S = OB + BB replaceing with above gives

S = (OJ div 8192) +1 + (OJ DIV 8) +1

make both divisions 8192 so

S = (OJ div 8192) + (OJ*1024 DIV 8192) +1 +1

That simplifies to:
S = (OJ*1025 DIV 8192) +2

Start re-aranging
S-2 = OJ*1025 DIV 8192 
(S-2)*8192 = OJ *1025

OJ = ((S-2) * 8192) DIV 1025

[BigDumbDinosaur]

BigEd wrote:

I think it might be the case that
OB = OJ ÷ 8 + ((OJ % 8) > 0)
could alternately be written as
OB = (OJ+7) ÷ 8
and similarly for BB. If so, perhaps that makes it easier to rearrange the formula.

Not sure if that would help. I'm going to use your suggestion to work some more on this puzzle.

Using that method, I could probably write:

Code: Select all

S = (OJ + 7) ÷ 8 + (OJ + 8191) ÷ 8192

...which might be easier to rearrange.

Something that has to be kept in mind is that while the relationships can be algebraically expressed, I am doing this in assembly language, which of course has no concept of algebraic precedence. Due to the way in which my division function works, OB = OJ ÷ 8 + ((OJ % 8) > 0) is more efficient than it would seem, as the test for (OJ % 8) > 0 is an automatic step in the division function. Upon return from division, z in SR (status register) is set if (OJ % 8) > 0 is false or cleared if (OJ % 8) > 0 is true. So a sequence such as the following could be used without having to perform a separate addition:

Code: Select all

         intntoa iinodes,s_inpnum,'n'  ;objects —> FACA
         intntob inodldb,s_word,'n'    ;objects per block —> FACB
         intdiv                        ;compute object blocks
         beq .0000020                  ;FACA % FACB == 0
;
         intinca                       ;add a block
;
.0000020 intaton inodblk,s_geonum,'n'  ;FACA —> object blocks

The above is analogous to OB = OJ ÷ 8 + ((OJ % 8) > 0). Incidentally, these arithmetic operations are encoded as macros, since the “raw” assembly language is easy to bollux up—parameters are passed via the stack, which is easy to goof up.

[sark02]

If I understand the problem, you're trying to find the object capacity (OJ) for a filesystem of size S blocks.
I think this works:

Code: Select all

OJ = ((S - 1) - ((S - 1) >> 10)) << 3

Where >> and << are right-shift and left-shift.
In assembly, something like this (untested):

Code: Select all

    S:  .RES 2
    OJ: .RES 2
    P:  .RES 2
    Q:  .RES 2

S_TO_OJ:
    ; P = S - 1
    CLC
    LDA S
    SBC #1
    STA P
    LDA S+1
    SBC #0
    STA P+1

    ; Q = (S-1) >> 10
    LDA P
    LSR A
    LSR A
    STA Q
    LDA #0
    STA Q+1

    ; R = (P - Q) << 3
    SEC
    LDA P
    SBC Q
    STA OJ
    LDA P+1
    SBC Q+1
    STA OJ+1
    LSL OJ
    ROL OJ+1
    LSL OJ
    ROL OJ+1
    LSL OJ
    ROL OJ+1
    RTS

[BigDumbDinosaur]

sark02 wrote:

If I understand the problem, you're trying to find the object capacity (OJ) for a filesystem of size S blocks...

Basically that’s the case. However, not only are there the blocks holding objects, there are blocks containing a bitmap that tracks the objects. Due to the use of 1KB logical blocks, one bitmap block is able to track a maximum of 8192 objects. As disk storage is always read and written in whole blocks, a case where OJ ÷ 8192 results in a remainder requires that an extra bitmap block be used. That is what complicates things.

I tested Ed’s idea in Thoroughbred BASIC with the equation S = INT((OJ + 7) / 8) + INT((OJ + 8191) ÷ 8192). Using a range of values from 0 to 16777216 for OJ, I compared the results of the new equation against the results produced with the method in my original post. The two methods agreed over the full range of OJ.

So the question is now how to rearrange S = (OJ + 7) ÷ 8 + (OJ + 8191) ÷ 8192 to solve for OJ.

[sark02]

BigDumbDinosaur wrote:

As disk storage is always read and written in whole blocks, a case where OJ ÷ 8192 results in a remainder requires that an extra bitmap block be used. That is what complicates things.

Understood. Try my expression: see if it does what you want.

Code: Select all

OJ = ((S - 1) - ((S - 1) >> 10)) << 3

Replace >> 10 with the integer div 1024, and << 3 with mul 8.

[BigDumbDinosaur]

sark02 wrote:

BigDumbDinosaur wrote:

As disk storage is always read and written in whole blocks, a case where OJ ÷ 8192 results in a remainder requires that an extra bitmap block be used. That is what complicates things.

Understood. Try my expression: see if it does what you want.

Code: Select all

OJ = ((S - 1) - ((S - 1) >> 10)) << 3

Replace >> 10 with the integer div 1024, and << 3 with mul 8.

Using your expression with bit shifts, OJ will always be a multiple of 8. Also, the expression will only work with object sizes that are powers of 2. That is not the impediment one might think, since the space needed for OJ objects is used in multiples of 8. Bit shifts/rotates are considerably faster than multiplication and division (moreso with the 65C816, which can shift/rotate 16 bits at a time), so using a filesystem structure that can work with 2^N object sizes would be the way to go. I'm going to give your algorithm a try—the filesystem generator is under development as we speak...so to speak.

By way of explanation, here's what I'm doing.

In the filesystem generator program, the user enters the filesystem’s name, filesystem’s size (FS) in 1KB blocks and number of inodes (NO). For any given value of FS, NO has a maximum, which the user will need to know during input. That maximum is OJ. After the user has entered NO, it will be compared to OJ for range. That is, the expression NO <= OJ must be true.

Once NO passes the smell test, it is used to compute the number of blocks that will be required in the inode array (OB), as well as the number of blocks required for the inode allocation bitmap (BB). Next, the operation DA = FS - (FOH +OB + BB) is carried out, with FOH representing immutable overhead in the filesystem. The difference, DA, is the number of blocks that will be available for the data area of the filesystem.

The data area includes a block allocation bitmap (BAM) and the actual data blocks. As with the inode allocation bitmap, the BAM has a 1:8192 relationship to the objects it tracks, in this case, the data blocks. Since it is desirable to maximize the number of data blocks available for user files, something like DB = (DA - 1) - ((DA - 1) >> 10) would have to be computed, with the available data blocks returned in DB. The expression DA - DB will give the number of BAM (BM) blocks required.

As a final check of filesystem geometry consistency, it will be verified that FOH + BB + BM + OB + DB == FS.

Anyhow, that’s the theory...

[BigDumbDinosaur]

sark02 wrote:

Understood. Try my expression: see if it does what you want.

Code: Select all

OJ = ((S - 1) - ((S - 1) >> 10)) << 3

Replace >> 10 with the integer div 1024, and << 3 with mul 8.

It works, but not reliably when S is not evenly divisible by 8. In such a case, the algorithm overestimates the maximum number of inodes, and in some cases, once blocks have been allocated to inodes and the inode allocation bitmap, there are no blocks left for the data area. This happens whether I use shifts or actual multiplication and division.

So I’m back to using S = ((OJ + 7) ÷ 8) + ((OJ + 8191) ÷ 8192) and solving for OJ.

[sark02]

BigDumbDinosaur wrote:

It works, but not reliably when S is not evenly divisible by 8. In such a case, the algorithm overestimates the maximum number of inodes, and in some cases, once blocks have been allocated to inodes and the inode allocation bitmap, there are no blocks left for the data area.

I ran a python loop over a range of OJ values, calculating S, and then I ran a range of S values, back-calculating OJ and then forward (using that OJ) to S again to make sure the numbers matched. They did, but it looks like there's a gap somewhere.
Oh well, sorry about that. Good luck with the better function.

[BigEd]

Maybe this
S = ((OJ + 7) ÷ 8) + ((OJ + 8191) ÷ 8192)
can be rearranged to
S = ((OJ + 7*1024) ÷ 8192) + ((OJ + 8191) ÷ 8192)
in which case
S = (OJ + 7*1024 + OJ + 8191) ÷ 8192
S = (2*OJ + 15*1024) ÷ 8192
and so
8192*S = (2*OJ + 15*1024)
8192*S - 15*1024 = 2*OJ
whence
OJ = 4096*S - 15*512

But it's quite possible the truncating nature of ÷ is going to scupper that.
Or that I've made some other mistake.

[teamtempest]

I probably don't quite understand the nature of the real problem. Why does the user have to enter anything more than the number of 1K blocks available? From that it should be easy for the system to calculate the maximum possible number of data blocks and then ask the user how many to actually allocate. Shouldn't it? That would make it easy to check if the user entered too large a value.

The minimum number of 1K blocks to create anything would be two. One bitmap block (mostly wasted) and one data block. For 8192 data blocks, 8193 1K blocks are needed. For 8193 data blocks, 8195 1K blocks (two bitmap blocks and 8193 data blocks).

So given N 1K blocks, the maximum number of wholly allocated bitmap blocks W would be:

Code: Select all

W = N/8193 (floored division)

and the number of partially allocated bitmap blocks P would be:

Code: Select all

P = 1 if N%8193 != 0 else 0

So the total number of data blocks D is:

Code: Select all

D = N - W - P

Trying this for a few values of N:

1: D = 1 - 0 - 1 = 0 (minimum two required for one data block)
2: D = 2 - 0 - 1 = 1
3: D = 3 - 0 - 1 = 2

8192: D = 8192 - 0 - 1 = 8191
8193: D = 8193 - 1 - 0 = 8192
8194: D = 8194 - 1 - 1 = 8192 (which is correct, as two more 1K blocks are needed to add one more 1K data block)
8195: D = 8195 - 1 - 1 = 8193

[IamRob]

<corrected>

Does this handle what you need?

For a given number of blocks can handle:
1 block can handle 8192 bitmaps
1 block can handle 8 objects
128x8=1024 blocks is required to handle 8192 objects

for each 128x8=1024 blocks for objects needs 1 block for bitmaps = 1025 blocks total
or put another way
for each 1025 blocks: 1024 blocks are for objects and 1 block is for bitmaps

There are some totals block numbers we can't use. Since at 1025 blocks both the object block and the bitmap block are full, we can't use a block # of 1026. We have to use 1027 since 1 extra block is needed for both a new object block and a new bitmap block

S = 1024 or S = 1025 or S=1027
BB = INT (S / 1027) + 1
OB = S - BB
OJ = OB * 8

S = total # of blocks for both objects and bitmaps
BB = # of blocks required by bitmaps
OB = # of blocks required by objects
OJ = max # of objects that given blocks can hold

[gfoot]

I think teamtempest and IAmRob have the same good approach but both made mistakes in different directions. Either that, or I did! But following their general technique -

Each 1K-block used as a bitmap can track 8192 128-byte data blocks, which themselves require 1024 more 1K-blocks. So a 1025 1K-block unit is "full" and supports 8192 data blocks.

The number of such full units that fit is just S / 1025, rounding down, and they support (S/1025)*8192 data blocks.

Then there are S % 1025 1K-blocks remaining - these can support up to ((S%1025)-1)*8 more data blocks, so long as S%1025 wasn't zero.

So the final answer is then (S/1025)*8192 + (S%1025 > 0 ? ((S%1025)-1)*8 : 0)

Division by 1025 is not pleasant, but I guess you don't need to do this very often!

[BigDumbDinosaur]

teamtempest wrote:

I probably don't quite understand the nature of the real problem. Why does the user have to enter anything more than the number of 1K blocks available? From that it should be easy for the system to calculate the maximum possible number of data blocks and then ask the user how many to actually allocate. Shouldn't it? That would make it easy to check if the user entered too large a value.

In theory, a filesystem-builder program needs to know only one piece of information, which would be the size of the filesystem (1KB blocks in this case). Absent any other inputs, the filesystem builder would compute the values for everything else, with one parameter, typically the number of inodes, being a default from which other parameters are computed. I've yet to encounter a filesystem builder that asks the user for the number of data blocks.

Any blocks in the filesystem that are not spoken for by fixed overhead, the inodes and the inode allocation map (IAM) would be mapped to the data area. That being so, the number of data blocks and the number of blocks in the data block allocation map (BAM) can be computed in the same fashion as calculating inode and IAM blocks.

Quote:

The minimum number of 1K blocks to create anything would be two. One bitmap block (mostly wasted) and one data block. For 8192 data blocks, 8193 1K blocks are needed. For 8193 data blocks, 8195 1K blocks (two bitmap blocks and 8193 data blocks).

That's correct.

In my 816NIX design, I've set the minimum filesystem size at 8201 blocks, since, as you note, at least one block has to be used for the (minimal) data block allocation bitmap—if the bitmap block is there, I might as well use all of it to map data blocks. I have also set the minimum number of inodes to 32 (which results in only 4 bytes being used in the IAM). In a such a filesystem size, block usage would be as follows:

• 3 — immutable overhead
• 4 — inodes (8 per block)
• 1 — IAM
• 8192 — data blocks
• 1 — BAM

In a practical sense, a minimum filesystem would be minimally useful, as it could, at most, store 30 files, assuming no subdirectories were created.

Incidentally, the maximum possible filesystem size in my implementation is 69,216,259 blocks. Such a file system would have 2,097,152 inode blocks (16,777,216 inodes), 2048 IAM blocks, 67,108,864 data blocks and 8192 BAM blocks.