Assume computer has 8 GB Ram

Assume disc has 1 TB storage. (SDD would be same calculations bit with different numbers)


The bitmap method,
   An area of disc is set aside to contain one bit for each block, 1 = in use, 0 = free.

   1 TB = 1,000,000,000,000 bytes (roughly)
        =     2,000,000,000 blocks
       so     2,000,000,000 bits to represent them all
        =       250,000,000 bytes
        =           500,000 blocks

   Half a million blocks out of total 2,000 million set aside for this bitmap, 0.05 % overhead

   Keeping a copy in RAM means setting aside 250,000,000 bytes of RAM, 3.1 % overhead
   Not keeping a copy in RAM means anything up to 500,000 disc accesses to find a free block


The block list method,
   An area of disc is set aside to store the block numbers for each of the free blocks
   2,000,000,000 is just less that 2 to the power of 31, so block numbers fit a 4 byte int

   space required for free block list = 2,000,000,000 ints
                                      = 8,000,000,000 bytes
                                      =    16,000,000 blocks
   
   16 million blocks out of total 2,000 million set aside for this list, 1.25 % overhead

   Keeping a copy in RAM means setting aside 8,000,000,000 bytes of RAM, 100 % overhead!

   But it behaves like a stack, so only need to keep a copy of the top region of the
   stack in memory at any one time, it can be (almost) as small as you want.

   Let's say that we have decided on a very small in-memory portion of the free block
   list, just enough to store 256 block numbers.

   IMPFBL (In-memory portion of free block list) = vec(256)

   Let's say the disc is very nearly half full (actually 999,999,990 blocks in use)
   so first 32,000,000 blocks of the real FBL are empty and the other 32,000,000 blocks 
   contain the addresses of free blocks.

   And let's also say that the free block list occupies blocks 1 to 16,000,000 of
   the disc.

   Then the top of the stack (half empty) will occupy blocks 8,000,000 and 8,000,001
   But the disc isn't quite exactly half full, it is 10 blocks short of half full.
   So block 8,000,000 contains 118 essentially random numbers followed by 10 real
   free block numbers. Block 8,000,001 will contain the full 128 free block numbers.

   The number of used blocks, 999,999,990, needs to be kept in the superblock. From
   that the 8,000,000 (top of stack block number) is easily calculated from that.

   At startup read block 8,000,000 into IMPFBL
              read block 8,000,001 into IMPFBL + 128
   and three more ints are needed:
              IMSP (in memory stack pointer) set to 118
              FBIIMP (first block in in-memory portion) set to 8,000,000
              NFB (number of free blocks) set to 1,000,000,010

   When creating a file, to get a free block:
       if NFB = 0 then
           fail
       if IMSP = 256 (past the end of the in memory portion) then
           // we have used up all the free blocks in the in-memory portion, so
           // the data in the in-memory portion is worthless, just move the
           // window:
           FBIIMP +:= 1
           read block FBIIMP + 1 = 8,000,002 into IMPFBL + 128
           IMSP := 128
       then in both cases (regardless of value of IMSP)
           NFB -:= 1
           BN := FBIIMP ! IMSP
           IMSP +:= 1
           resultis BN
           

   when deleting a file, returning a block to the free list:
       if NFB > 2,000,000,000 then
           something has gone seriously wrong
       if IMSP = 0 (we have filled the in-memory portion with free block numbers) then
           write the 128 words starting at IMPFBL + 128 to block FBIIMP + 1
           FBIMP -:= 1
           IMSP := 127
       then in both cases (regardless of the value of IMSP)
           NFB +:= 1
           IMSP -:= 1
           FBIIMP ! IMSP := the newly freed block number