PureFS: Difference between revisions

From OSDev.wiki
Jump to navigation Jump to search
[unchecked revision][unchecked revision]
Content added Content deleted
VisualWikitext
(Added some information)
 
 
(22 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{In Progress}}
{{Filesystems}}
{{Filesystems}}
'''Note: if you find a grammatical error in the article, please correct it (the author does not know English well, so there may be errors).'''<br/>
PureFS is a simple disk file system designed to quickly read information and data from files and directories.<br>
PureFS is a disk file system designed to simplify the interaction between the operating system and disks.
Due to its structure, it is possible to use a second file system on the disk, you just need to create a 3rd or 4th entry for PureFS in the MBR partition table('''SystemID = 0x15''').


== PureFS 1.1.0 ==
== PureFS V1.2.0 ==
Better than the [https://wiki.osdev.org/index.php?title=PureFS&oldid=28856 previous version] in terms of speed, but a bit more complicated.<br/>
There are only 4 structures:
PureFS V1.2.0 has a total of 6 main structures:
* PureFsHeader
#PureFsHeader
* PureFsPartitionHeader
#PureFsVolumeHeader
* PureFsFile
#PureFsFileMap
* PureFsData
#PureFsDataMap
'''Note: all values ​​must be written in Little-Endian format!'''
#PureFsFileTable
#PureFsDataTable


Advantages(+):
#Easy to implement.
#Easy to understand.
#Supports nested directories.
#Maximum available 2^64 - 1 sectors.

Disadvantages(-):
#It can be journalable, provided that the OS takes care of this task itself.
#The maximum length of the file name is 255 characters.
#The maximum number of volumes is 40.
#Does not support Unicode names.
#Takes up a lot of space.

== Example Of Disk Space Allocation ==
Note: sector #1 is not the first sector on the disk, but the first sector of PureFS.<br/>
Partition with a single volume:
{| class="wikitable"
|-
! Sector #
! Structure
|-
| 1
| PureFS header
|-
| 2
| PureFS volume header
|-
| 3
| PureFS file map
|-
| 3+blocks/map
| PureFS data map
|-
| 3+blocks/map*2
| PureFS file table
|-
| 3+blocks/map*2+32*blocks/map
| PureFS data table
|}

== Structures ==
=== PureFsHeader ===
=== PureFsHeader ===
Contains information about file system.
Contains information about the file system.<br/>
{| {{wikitable}}
{| class="wikitable"
|-
|-
! Offset
! Offset
! Size
! Size
! Type
! Name
! Name
! Value/Description
! Value
|-
|-
| 0x00
| 0x00
| 0x08
| 0x08
| char[8]
| Signature
| Signature
| `'''->PureFS'''`
| `->PureFS`
|-
|-
| 0x08
| 0x08
| 0x04
| 0x04
| u32
| Version
| Version
| Version number as a hex value (for ex.: 1.1.0 = 0x010100)
| PureFS version number(1.2.0 = 0x010200)
|-
|-
| 0x0C
| 0x0C
| 0x08
| 0x08
| u64
| FirstPartition
| NumVolumes
| Offset to first partition (in sectors)
| Number of PureFS volumes
|-
|-
| 0x14
| 0x14
| 0x08
| 0x01
| u8
| NumPartitions
| Number of PureFS partitions
|-
| 0x1C
| 0x08
| Checksum
| Checksum
| With a byte-by-byte sum of all fields above it should give 0
| Complements byte sum of fields above to 0
|-
|-
| 0x1D
| 0x15
| 0x1E3
| 0x0B
| u8[11]
| Reserved
| Reserved
| Reserved for future use
| Reserved for future use
|-
|-
| 0x20
| 0x28*0x0C
| PureFsVolumePtr[40]
| Volumes
| Pointers to PureFS volumes
|}
|}


PureFsVolumePtr:
=== PureFsPartitionHeader ===
{| class="wikitable"
Contains information about partition.
{| {{wikitable}}
|-
|-
! Offset
! Offset
! Size
! Size
! Type
! Name
! Name
! Value/Description
! Value
|-
|-
| 0x00
| 0x00
| 0x40
| 0x08
| u64
| Offset
| Offset to PureFS volume (in sectors)
|-
| 0x08
| 0x04
| u32
| NameHash
| Murmur v3 32-bit volume name hash<br />
|}

=== PureFsVolumeHeader ===
Contains information about the PureFS volume.<br/>
{| class="wikitable"
|-
! Offset
! Size
! Type
! Name
! Value
|-
| 0x00
| 0x37+0x01
| char[55+1]
| Name
| Name
| PureFS volume name (zero-terminated)
| Name of the partition
|-
|-
| 0x40
| 0x38
| 0x08
| 0x08
| u64
| Attributes
| Attributes
| Partition attributes
| PureFS volume attributes
|-
| 0x40
| 0x08
| u64
| BlocksPerMap
| Maximum number of blocks(sectors) per map(FileMap/DataMap)
|-
|-
| 0x48
| 0x48
| 0x08
| 0x08
| u64
| NumBlocks
| NumFiles
| Maximum number of blocks(sectors) in partition
| Current number of files
|-
|-
| 0x50
| 0x50
| 0x08
| 0x08
| u64
| NumFiles
| NumData
| Current number of files in partition
| Current number of data blocks(sectors)
|-
|-
| 0x58
| 0x58
| 0x08
| 0x1A8
| u8[424]
| FirstFile
| Reserved
| Offset to first file block (in sectors)
| Reserved for future use
|}

Attributes:
*'''BOOTABLE'''(0x01) - marks that there is a program (OS kernel, for example) on the partition that bootloader should load.
*'''READABLE'''(0x02)
*'''WRITEABLE'''(0x04)

=== PureFsFileMap ===
Consists of PureFsVolumeHeader::BlocksPerMap sectors. There are 32 PureFsFileMapEntry entries in each sector.<br/>
PureFsFileMapEntry:
{| class="wikitable"
|-
|-
! Offset
| 0x60
! Size
| 0x08
! Type
| LastFile
! Name
| Offset to last file block (in sectors)
! Value
|-
|-
| 0x68
| 0x00
| 0x08
| 0x08
| u64
| FirstData
| FileIndex
| Offset to first data block (in sectors)
| PureFsFile block(sector) index in the file table
|-
|-
| 0x70
| 0x08
| 0x08
| 0x04
| LastData
| u32
| Offset to last data block (in sectors)
| PathHash<br />
| Murmur v3 32-bit hash of file path on partition ('''without partition name!''')
|-
|-
| 0x78
| 0x0C
| 0x04
| u32
| ParentHash
| Murmur v3 32-bit hash of the path to the parent directory on the partition ('''without partition name!''')
|}

=== PureFsDataMap ===
Consists of PureFsVolumeHeader::BlocksPerMap sectors. There are 32 PureFsDataMapEntry entries in each sector.<br/>
PureFsDataMapEntry:
{| class="wikitable"
|-
! Offset
! Size
! Type
! Name
! Value
|-
| 0x00
| 0x08
| 0x08
| u64
| NextPartition
| FileIndex
| Offset to next partition (in sectors)
| PureFsData block(sector) index in the data table
|-
|-
| 0x80
| 0x08
| 0x180
| 0x08
| u8[8]
| Reserved
| Reserved
| Reserved for future use
| Reserved for future use
|-
|}
|}

'''Attributes:'''
=== PureFsFileTable ===
* '''SYSTEM'''(0x01) - partition required for the file system to function
Contains PureFsFile blocks.<br/>
* '''BOOTABLE'''(0x02) - the partition contains a program that can be loaded by the bootloader
PureFsFile:
* '''HIDDEN'''(0x04)
{| class="wikitable"
* '''READONLY'''(0x08)
* '''WRITEONLY'''(0x10)
'''NextPartition:''' if this is the last partition, this field is 0
=== PureFsFile ===
Contains information about file.
{| {{wikitable}}
|-
|-
! Offset
! Offset
! Size
! Size
! Type
! Name
! Name
! Value/Description
! Value
|-
|-
| 0x00
| 0x00
| 0x100
| 0x100
| char[255+1]
| Name
| Name
| File name (ASCII)
| File name (ASCII) (zero-terminated)
|-
|-
| 0x100
| 0x100
| 0x08
| 0x08
| u64
| Size
| Original file size
|-
| 0x108
| 0x04
| u32
| Attributes
| Attributes
| File attributes
| File attributes
|-
|-
| 0x108
| 0x10C
| 0x08
| 0x08
| u64
| NumBlocks
| ParentIndex
| Number of data blocks(`PureFsData`) of the file
| Index of the PureFsFile block(sector) of the parent directory in the file table
|-
|-
| 0x110
| 0x114
| 0x08
| 0x08
| u64
| OriginalSize
| DataIndex
| Original file data size
| Index of the PureFsData block(sector) in the data table
|-
| 0x118
| 0x08
| FirstBlock
| Offset to first data block(`PureFsData`) (in sectors)
|-
| 0x120
| 0x04
| PathHash
| Murmur3 32-bit hash of the file path on the partition
|-
| 0x124
| 0x04
| ParentHash
| Murmur3 32-bit hash of the path to the file's parent directory
|-
|-
| 0x128
| 0x11C
| 0xD8
| 0xE4
| u8[228]
| Reserved
| Reserved
| Reserved for future use
| Reserved for future use
|-
|}
|}
'''Attributes:'''
* '''SYSTEM'''(0x01) - file required for the file system to function
* '''EXECUTABLE'''(0x02) - it is possible to run the file as a program
* '''HIDDEN'''(0x04)
* '''READONLY'''(0x08)
* '''WRITEONLY'''(0x10)
* '''DIRECTORY'''(0x20) - marks that it is a directory and not a file
'''OriginalSize:''' if the file is empty or it is a directory, it is equal to 0<br>
'''FirstBlock:''' if the file is empty or it is a directory, it is equal to 0


Attributes:
=== PureFsData ===
*'''EXECUTABLE'''(0x01) - marks the file as a program that can be executed by the OS.
Contains one of the file's data parts.
*'''READABLE'''(0x02)
{| {{wikitable}}
*'''WRITEABLE'''(0x04)

=== PureFsDataTable ===
Contains PureFsData blocks.<br/>
PureFsData:
{| class="wikitable"
|-
|-
! Offset
! Offset
! Size
! Size
! Type
! Name
! Name
! Value/Description
! Value
|-
|-
| 0x00
| 0x00
| 0x1F8
| 0x1F8
| u8[504]
| Data
| Data
| One of the file data parts
| Part of the file data
|-
|-
| 0x1F8
| 0x1F8
| 0x08
| 0x08
| u64
| NextData
| NextIndex
| Offset to next data block(`PureFsData`) (in sectors)
| Index of the next data block(sector) (0 if last)
|-
|}
|}
'''NextData:''' if this is the last block of data, this field is 0

== Implementation of some functions ==
purefs.h:
<source lang="c">#pragma once
#ifndef PUREFS_H
#define PUREFS_H

#include <stdint.h>
#include <string.h>

typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;

#pragma pack(push, 1)
#define PUREFS_SIGNATURE "->PureFS"
#define PUREFS_V1_1_0 0x010100
#define PUREFS_SYSID 0x15
#define PUREFS_MURMUR3_SEED 0x4E53544B
typedef struct _PureFsHeader {
i8 Signature[8];
u32 Version;
u64 FirstPartition;
u64 NumPartitions;
u8 Checksum;
u8 Reserved[0x1E3];
} PureFsHeader;

#define PUREFS_PARTITION_ATR_SYSTEM 0x01
#define PUREFS_PARTITION_ATR_BOOTABLE 0x02
#define PUREFS_PARTITION_ATR_HIDDEN 0x04
#define PUREFS_PARTITION_ATR_READONLY 0x08
#define PUREFS_PARTITION_ATR_WRITEONLY 0x10
typedef struct _PureFsPartitionHeader {
i8 Name[64];
u64 Attributes;
u64 NumBlocks;
u64 NumFiles;
u64 FirstFile;
u64 LastFile;
u64 FirstData;
u64 LastData;
u64 NextPartition;
u8 Reserved[0x180];
} PureFsPartitionHeader;

#define PUREFS_FILE_ATR_SYSTEM 0x01
#define PUREFS_FILE_ATR_EXECUTABLE 0x02
#define PUREFS_FILE_ATR_HIDDEN 0x04
#define PUREFS_FILE_ATR_READONLY 0x08
#define PUREFS_FILE_ATR_WRITEONLY 0x10
#define PUREFS_FILE_ATR_DIRECTORY 0x20
typedef struct _PureFsFile {
i8 Name[256];
u64 Attributes;
u64 NumBlocks;
u64 OriginalSize;
u64 FirstBlock;
u32 PathHash;
u32 ParentHash;
u8 Reserved[0xD8];
} PureFsFile;

typedef struct _PureFsData {
u8 Data[504];
u64 NextData;
} PureFsData;
#pragma pack(pop)

extern size_t ReadSector(void *disk, u64 lba, u8 *buf);
extern u32 murmur3_32(u8 *key, size_t len, u32 seed);

size_t PureFsCheckHeader(PureFsHeader *h);
size_t PureFsReadHeader(void *disk, PureFsHeader *h);
size_t PureFsReadPartitionHeader(void *disk, const char *name, PureFsHeader *fsh, PureFsPartitionHeader *ph);
size_t PureFsReadFile(void *disk, const char *path, PureFsHeader *h, PureFsFile *buf1, u8 *buf2);
#endif
</source>

purefs.c:
<source lang="c">
#include <purefs.h>

// Returns: 0 - invalid PureFS header, 1 - valid
size_t PureFsCheckHeader(PureFsHeader *h) {
u8 csum;
u8 i;

if (!strcmp(h->Signature, PUREFS_SIGNATURE) || h->Version != PUREFS_V1_1_0) return 0;

csum = 0;
for (i = 0; i < 0x1D; ++i) csum == ((u8*)h)[i];
return !csum;
}

// Returns LBA of the sector with PureFsHeader or 0
size_t PureFsReadHeader(void *disk, PureFsHeader *h) {
u8 MBR[512];
size_t off;
size_t i;
u64 lba;

if (!h || !ReadSector(disk, 0, &MBR[0])) return 0;

// Finding a PureFS entry in the MBR partition table
lba = 0;
off = 440 + 4 + 2;
for (i = 0; i < 4; ++i) {
// We check that the partition is active and its ID is PureFS(0x15)
if (*((u8*)off) & 0x80 && *((u8*)(off + 4)) == PUREFS_SYSID) {
lba = (u64)*((u32*)(off + 8));
if (lba) break;
}
}

if (!lba || !ReadSector(disk, lba, h) || !PureFsCheckHeader(h)) return 0;
return lba;
}

// Returns LBA of the sector with PureFsPartitionHeader or 0
size_t PureFsReadPartitionHeader(void *disk, const char *name, PureFsHeader *fsh, PureFsPartitionHeader *ph) {
u64 lba;

if (!fsh->FirstPartition || !fsh->NumPartitions) return 0;

lba = (u64)fsh->FirstPartition;
do {
if (!ReadSector(disk, lba, ph)) continue;
if (!strcmp(ph->Name, name)) return lba;

lba = ph->NextPartition;
} while (ph->NextPartition);

return 0;
}

// Returns LBA of the sector with PureFsFile or 0
size_t PureFsReadFile(void *disk, const char *path, PureFsHeader *h, PureFsFile *buf1, u8 *buf2) {
PureFsPartitionHeader ph;
char *separator;
char tmp[512];
PureFsFile f;
size_t found;
size_t len;
u32 hash;
u64 lba;
u64 i;
u64 j;

if (!h || !h->FirstPartition || !h->NumPartitions) return 0;

// Get file path hash
hash = murmur3_32(path, strlen(path), PUREFS_MURMUR3_SEED);
while (*path == '/') ++path;
separator = strchr(path, '/');
if (!separator) return 0;

len = (size_t)separator - (size_t)path;
memcpy(tmp, path, len);
tmp[len] = 0;

// Looking for a partition by name
found = 0;
lba = (u64)h->FirstPartition;
do {
if (!ReadSector(disk, lba, &ph)) continue;
if (!strcmp(ph.Name, tmp)) {
found = 1;
break;
}

lba = ph.NextPartition;
} while (ph.NextPartition);

if (!found || !ph.NumBlocks || !ph.NumFiles || !ph.FirstFile) return 0;

// Looking for file
found = 0;
lba += ph.FirstFile;
for (i = 0; i < ph.NumFiles; ++i) {
if (!ReadSector(disk, lba, &f)) continue;

if (f.PathHash == hash) {
found = 1;
break;
}

++lba;
}

if (!found) return 0;

// Copy PureFsFile and read data as needed
if (buf1) memcpy(buf1, &f, sizeof(PureFsFile));
if (f.FirstBlock && buf2) {
len = f.OriginalSize;
j = lba + f.FirstBlock;
for (i = 0; i < f.NumBlocks - 1; ++i) {
if (!ReadSector(disk, j, tmp) || !((PureFsData*)tmp)->NextData) return 0;


== FAQ ==
memcpy(buf2, tmp, 504);
*How are directories stored? - Directories are the same as files, except that the PUREFS_FILE_ATR_DIRECTORY bit is set in PureFsFile::Attributes, and the data blocks(sectors) (PureFsData) contain the indexes of the files they contain.
buf2 = (u8*)((size_t)buf2 + 504);
*How are symbolic links stored? - Symbolic links differ from regular files only in that they have no data blocks, and the PureFsFile::DataIndex field contains the index of the file/directory in the PureFsFileTable table.
len -= 504;
*How are hash collisions handled? - For this purpose, the PathHash and ParentHash fields are provided in the PureFsFileMapEntry structure to minimize the risk of finding the wrong file. When the OS reads the PureFsFile structure, it must check that the file name matches the file being searched for.
++j;
}


== See Also ==
if (!ReadSector(disk, j, tmp)) return 0;
[https://wiki.osdev.org/index.php?title=PureFS&oldid=28856 PureFS V1.1.0]<br/>
memcpy(buf2, tmp, len);
[https://en.wikipedia.org/wiki/MurmurHash#Algorithm Murmur v3 32-bit hash]
}


return lba;
}
</source>
== See also ==
[https://en.wikipedia.org/wiki/MurmurHash#Algorithm murmur hash v3]
[[Category:Filesystems]]
[[Category:Filesystems]]

Latest revision as of 15:13, 29 May 2024

This page is a work in progress.
This page may thus be incomplete. Its content may be changed in the near future.
Filesystems
Virtual Filesystems

VFS

Disk Filesystems
CD/DVD Filesystems
Network Filesystems
Flash Filesystems

Note: if you find a grammatical error in the article, please correct it (the author does not know English well, so there may be errors).
PureFS is a disk file system designed to simplify the interaction between the operating system and disks.

PureFS V1.2.0

Better than the previous version in terms of speed, but a bit more complicated.
PureFS V1.2.0 has a total of 6 main structures:

  1. PureFsHeader
  2. PureFsVolumeHeader
  3. PureFsFileMap
  4. PureFsDataMap
  5. PureFsFileTable
  6. PureFsDataTable

Advantages(+):

  1. Easy to implement.
  2. Easy to understand.
  3. Supports nested directories.
  4. Maximum available 2^64 - 1 sectors.

Disadvantages(-):

  1. It can be journalable, provided that the OS takes care of this task itself.
  2. The maximum length of the file name is 255 characters.
  3. The maximum number of volumes is 40.
  4. Does not support Unicode names.
  5. Takes up a lot of space.

Example Of Disk Space Allocation

Note: sector #1 is not the first sector on the disk, but the first sector of PureFS.
Partition with a single volume:

Sector # Structure
1 PureFS header
2 PureFS volume header
3 PureFS file map
3+blocks/map PureFS data map
3+blocks/map*2 PureFS file table
3+blocks/map*2+32*blocks/map PureFS data table

Structures

PureFsHeader

Contains information about the file system.

Offset Size Type Name Value
0x00 0x08 char[8] Signature `->PureFS`
0x08 0x04 u32 Version PureFS version number(1.2.0 = 0x010200)
0x0C 0x08 u64 NumVolumes Number of PureFS volumes
0x14 0x01 u8 Checksum Complements byte sum of fields above to 0
0x15 0x0B u8[11] Reserved Reserved for future use
0x20 0x28*0x0C PureFsVolumePtr[40] Volumes Pointers to PureFS volumes

PureFsVolumePtr:

Offset Size Type Name Value
0x00 0x08 u64 Offset Offset to PureFS volume (in sectors)
0x08 0x04 u32 NameHash Murmur v3 32-bit volume name hash

PureFsVolumeHeader

Contains information about the PureFS volume.

Offset Size Type Name Value
0x00 0x37+0x01 char[55+1] Name PureFS volume name (zero-terminated)
0x38 0x08 u64 Attributes PureFS volume attributes
0x40 0x08 u64 BlocksPerMap Maximum number of blocks(sectors) per map(FileMap/DataMap)
0x48 0x08 u64 NumFiles Current number of files
0x50 0x08 u64 NumData Current number of data blocks(sectors)
0x58 0x1A8 u8[424] Reserved Reserved for future use

Attributes:

  • BOOTABLE(0x01) - marks that there is a program (OS kernel, for example) on the partition that bootloader should load.
  • READABLE(0x02)
  • WRITEABLE(0x04)

PureFsFileMap

Consists of PureFsVolumeHeader::BlocksPerMap sectors. There are 32 PureFsFileMapEntry entries in each sector.
PureFsFileMapEntry:

Offset Size Type Name Value
0x00 0x08 u64 FileIndex PureFsFile block(sector) index in the file table
0x08 0x04 u32 PathHash
 Murmur v3 32-bit hash of file path on partition (without partition name!)
0x0C 0x04 u32 ParentHash Murmur v3 32-bit hash of the path to the parent directory on the partition (without partition name!)

PureFsDataMap

Consists of PureFsVolumeHeader::BlocksPerMap sectors. There are 32 PureFsDataMapEntry entries in each sector.
PureFsDataMapEntry:

Offset Size Type Name Value
0x00 0x08 u64 FileIndex PureFsData block(sector) index in the data table
0x08 0x08 u8[8] Reserved Reserved for future use

PureFsFileTable

Contains PureFsFile blocks.
PureFsFile:

Offset Size Type Name Value
0x00 0x100 char[255+1] Name File name (ASCII) (zero-terminated)
0x100 0x08 u64 Size Original file size
0x108 0x04 u32 Attributes File attributes
0x10C 0x08 u64 ParentIndex Index of the PureFsFile block(sector) of the parent directory in the file table
0x114 0x08 u64 DataIndex Index of the PureFsData block(sector) in the data table
0x11C 0xE4 u8[228] Reserved Reserved for future use

Attributes:

  • EXECUTABLE(0x01) - marks the file as a program that can be executed by the OS.
  • READABLE(0x02)
  • WRITEABLE(0x04)

PureFsDataTable

Contains PureFsData blocks.
PureFsData:

Offset Size Type Name Value
0x00 0x1F8 u8[504] Data Part of the file data
0x1F8 0x08 u64 NextIndex Index of the next data block(sector) (0 if last)

FAQ

  • How are directories stored? - Directories are the same as files, except that the PUREFS_FILE_ATR_DIRECTORY bit is set in PureFsFile::Attributes, and the data blocks(sectors) (PureFsData) contain the indexes of the files they contain.
  • How are symbolic links stored? - Symbolic links differ from regular files only in that they have no data blocks, and the PureFsFile::DataIndex field contains the index of the file/directory in the PureFsFileTable table.
  • How are hash collisions handled? - For this purpose, the PathHash and ParentHash fields are provided in the PureFsFileMapEntry structure to minimize the risk of finding the wrong file. When the OS reads the PureFsFile structure, it must check that the file name matches the file being searched for.

See Also

PureFS V1.1.0
Murmur v3 32-bit hash

Retrieved from "https://osdev.wiki/wiki/PureFS?oldid=24996"