Public Domain (Or zlib, take your pick!) implementation of a simple file system. No support for file or directories (YET), but structure is there.

simple_fs.py

#!/usr/bin/env python3
"""
Description:
Virtual file system implementation.
Currently supports blocks, block chaining, and block bitmaps.
No support for files and directories, but the structure is there.
Publishing this as-is right now in case I never get around to finishing it.
Check back for updates.

Flaws:
* Infinite loop can be encountered by a corrupted file system causing
  block pointers to point in circles. Should check to make sure it isn't
  revisiting a previously visited block.
* Could use some optimization where marked.

Notes:
* Block size should be a power of 2 for optimiziation reasons.

LICENSE:
ZLib or Unlicense, take your pick.

Option 1:
------------------------------------ ZLIB --------------------------------------
Copyright (c) 2022 Kyler "Félix" Eastridge
This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
1. The origin of this software must not be misrepresented; you must not
   claim that you wrote the original software. If you use this software
   in a product, an acknowledgment in the product documentation would be
   appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
   misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
--------------------------------------------------------------------------------

Option 2:
--------------------------------- UNLICENSE ------------------------------------
This is free and unencumbered software released into the public domain.

Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.

In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

For more information, please refer to <http://unlicense.org/>
--------------------------------------------------------------------------------

"""
import struct

FSMagic = bytes.fromhex("48af7cd3-f4ea-abed-5362-956ecb7219d9".replace("-", ""))

"""
header {
    char[16] magic; //UUID
    uint16 version_major; //Structure change
    uint16 version_minor; //New feature
    uint16 blocksize; //Typically 1024
    uint64 bitmappointer; //Abs Offset to bitmap
    uint64 rootpointer; //Abs Offset to root
    char[] padding; //Pad until header is the length of blocksize
}
"""
sFSHeader = struct.Struct(">16s H H H Q Q")

"""
block {
    //Related data
    uint32 prevblock; //If 0, start
    uint32 nextblock; //If 0, end
    node[blocksize - 4 - 4] data;
}
"""
sFSBlock = struct.Struct(">I I")

"""
node {
    uint8 type;
    char[] data;
}
"""
sFSNode = struct.Struct(">B")

"""
string {
    uint8 namelen;
    char[namelen] name;
}
"""
sFSStringLen = struct.Struct(">B")

"""
permissionsdata {
    uint16 owner;
    uint16 group;
    uint16 permissions;
}
"""
sFSPermissions = struct.Struct(">H H H")

"""
bitmap {
    uint32 blockcount;
    char[ceil(blockcount / 8)] data; //1 = in use, 0 = free
}
"""
sFSBitmapLen = struct.Struct(">I")

"""
directory {
    string name;
    permissionsdata permissions;
    uint32 childcount;
    uint32[childcount] children;
}
"""

sFSDirChildLen = struct.Struct(">I")
sFSDirChild = struct.Struct(">I")

"""
file {
    string name;
    permissionsdata permissions;
    uint32 parent;
    uint64 datalen;
    char[datalen] data;
}
"""
sFSFile = struct.Struct(">I Q")

NODE_TYPE_NULL = 0
NODE_TYPE_BITMAP = 1
NODE_TYPE_DIRECTORY = 2
NODE_TYPE_FILE = 3

class VFSException(Exception):
    pass

class VFS:
    def __init__(self, handle, init = False, defaultBlockSize = 1024):
        #Store the handle
        self.handle = handle
        
        #Store our index in case we are part of a subfile
        self.indexOffset = self.handle.tell()
        
        #Init defaults
        self.bitmappointer = 0
        self.rootpointer = 0
        self.bitmap = bytearray()
        self.lastFreeBlock = 0
        
        #Create FS if needed
        if init:
            self.blocksize = defaultBlockSize
            #Initialize the header
            self.write(sFSHeader.pack(
                FSMagic, #Magic
                0, #Version major
                0, #Version minor
                self.blocksize, #Block
                1, #Bitmap pointer
                2, #Root pointer
            ))
            
            self.write(bytes(self.blocksize - sFSHeader.size))
            
            #Reserve the first 3 blocks(Header, Bitmap, Root dir)
            self.bitmap = bytearray([0b111])
            
            #Create empty bitmap data
            self.writeBlock(1, 0, 0,
                sFSNode.pack(NODE_TYPE_BITMAP) \
                + sFSBitmapLen.pack(1) \
                + self.bitmap
            )
            self.bitmappointer = 1
            
            #Tell the bitmap to write it's self
            self.writeBitmap()
            
            
            #self.mkdir("")
        
        #Load it otherwise
        else:
            header = self.read(sFSHeader.size)
            if len(header) != sFSHeader.size:
                raise VFSException("VFS corrupted. Invalid header length.")
            
            magic, vmajor, vminor, blocksize, bitmappointer, rootpointer \
                 = sFSHeader.unpack(header)
            
            if magic != bytes(FSMagic):
                raise VFSException("VFS corrupted. Invalid magic.")
            
            #TODO: Handle versions
            self.blocksize = blocksize
            self.bitmappointer = bitmappointer
            self.rootpointer = rootpointer
            self.loadBitmap()
    
    #Base block IO
    def readBlock(self, bnum):
        self.seek(bnum * self.blocksize) #TODO: Optimize with bitwise
        
        return sFSBlock.unpack(self.read(sFSBlock.size)), \
               self.read(self.blocksize - sFSBlock.size)
    
    def updateBlock(self, bnum, prev, next):
        self.seek(bnum * self.blocksize) #TODO: Optimize with bitwise
        
        self.write(sFSBlock.pack(prev, next))
    
    def writeBlock(self, bnum, prev, next, data):
        self.seek(bnum * self.blocksize) #TODO: Optimize with bitwise
        
        if len(data) > self.blocksize - sFSBlock.size:
            raise VFSException("writeBlock cannot write more than blocksize!")
        
        self.write(sFSBlock.pack(prev, next))
        self.write(data)
        rem = self.blocksize - sFSBlock.size - len(data)
        if rem > 0:
            self.write(bytes(rem))
    
    def getFreeBlock(self):
        if (self.lastFreeBlock >> 3) > len(self.bitmap):
            self.lastFreeBlock = 0
        
        for i in range(self.lastFreeBlock >> 3, len(self.bitmap)):
            if self.bitmap[i] != 255:
                for b in range(8):
                    if (self.bitmap[i] >> i) & 1 == 0:
                        return (i << 3) + b
        
        #If we didn't return, we need more blocks
        self.bitmap.append(0)
        
        #Increment our free block cache
        self.lastFreeBlock = (len(self.bitmap) << 3) + 1
        
        #Return first entry on the newest bitmap entry
        return len(self.bitmap) << 3
    
    def freeBlock(self, block):
        #If it isn't even freeable, don't bother
        if (block >> 3) > len(self.bitmap):
            return
        
        i = block >> 3
        #This basically selects the (block % 7)th bit of bitmap[i]
        self.bitmap[i] = self.bitmap[i] & ~(1 << (block & 7))
    
    #Whole block IO
    def readBlocks(self, bnum):
        #BNum is converted in readBlock
        result = b""
        pointers, result = self.readBlock(bnum)
        if pointers[0] != 0:
            #TODO: Seek to first block instead?
            raise VFSException("readBlocks expected starting block!")
        
        #Read until we reach end of block
        #WARNING: This is suseptible to infinite looping
        while pointers[1] != 0:
            pointers, data = self.readBlock(bnum)
            result += data
        
        return result
    
    def writeBlocks(self, data):
        chunksize = self.blocksize - sFSBlock.size
        prevprevblock = 0
        prevblock = 0
        for i in range(0, len(data), chunksize):
            thisblock = self.getFreeBlock()
            self.writeBlock(thisblock, prevblock, 0, data)
            if prevblock != 0:
                self.updateBlock(prevblock, prevprevblock, thisblock)
                prevprevblock = prevblock
            prevblock = thisblock
    
    #Bitmaps
    def writeBitmap(self):
        #Erase existing bitmap
        pointers, result = self.readBlock(self.bitmappointer)
        self.freeBlock(self.bitmappointer)
        while pointers[1] != 0:
            self.freeBlock(pointers[1])
            pointers, result = self.readBlock(pointers[1])
        
        #Write new bitmap to bytes
        bitmapdata = bytes(self.bitmap)
        
        #This is ceil(len(self.bitmap) / 8) but faster
        bcount = (len(self.bitmap) >> 3) + 1
        
        bitmapdata = sFSNode.pack(NODE_TYPE_BITMAP) \
                   + sFSBitmapLen.pack(bcount) \
                   + bitmapdata
        
        self.writeBlocks(bitmapdata)
    
    def loadBitmap(self):
        data = self.readBlocks(self.bitmappointer)
        if data[0] != NODE_TYPE_BITMAP:
            raise VFSException("Tried to load non-bitmap node as bitmap!")
        
        l, = sFSBitmapLen.unpack_from(data, 1)
        
        self.bitmapdata = bytearray(data[1+sFSBitmapLen.size:l*8])
    
    #Helper functions
    def seek(self, offset, whence = 0):
        #Override our index position
        if whence == 0:
            offset = self.indexOffset + offset
        
        return self.handle.seek(offset)
    
    def read(self, size):
        return self.handle.read(size)
    
    def write(self, data):
        return self.handle.write(data)

if __name__ == "__main__":
    import io
    handle = io.BytesIO()
    #Open a FS on handle, create it, and make the blocksize 64 bytes
    #Real world we want larger block size, 64 bytes is for ease of testing.
    vfs = VFS(handle, True, 64)
    vfs.loadBitmap()
    handle.seek(0)
    print(handle.read())