ref: e9887eaf83eea7d530704ab3f1caab08b35af404
parent: bb9df261cba0e42df6178850d7479dd162d742d6
author: 9ferno <gophone2015@gmail.com>
date: Sat Oct 22 05:35:55 EDT 2022
more updates to the documentation
--- a/docs/mafs.ms
+++ b/docs/mafs.ms
@@ -19,7 +19,7 @@
.sp
Mafs is a user space file system to provide system stability and security. It is based on kfs.
.sp
-As a goal of this document is to build up technical expertise, it gratuitously uses the actual commands and C data structure definitions to convey information.
+As this document aims to also provide working knowledge, it gratuitously uses the actual commands and the relevant C data structure definitions to convey information.
.sp
.ft B
Workflow
@@ -121,10 +121,10 @@
Tind2, /* list of Tind1 blocks */
Tind3, /* list of Tind2 blocks */
Tind4, /* list of Tind3 blocks */
- Tind5, /* list of Tind4 blocks */
+ Tind5, /* list of Tind4 blocks, maximum file size 26 TiB */
};
.sp
-A Span is stored to the disk with a Tag.
+A block is stored to the disk with a Tag.
.br
struct Tag
{@@ -136,7 +136,7 @@
};
.fi
.sp
-Every file or directory is represented on the disk by a directory entry (Dentry). Every directory entry uses a block (Tag.type = Tdentry) and is uniquely identifiable by a Qid.
+Every file or directory is represented on the disk by a directory entry (Dentry). A directory entry uses a block (Tag.type = Tdentry) and is uniquely identifiable by a Qid.
.sp
Mafs does not store the last access time of a file or directory.
.sp
@@ -144,8 +144,8 @@
.nf
enum {Rawblocksize= 512, /* real block size */
- Ndblock = 32, /* number of direct blocks in a Dentry */
- Niblock = 6, /* max depth of indirect blocks */
+ Ndblock = 32,/* number of direct blocks in a Dentry */
+ Niblock = 6, /* max depth of indirect blocks */
};
struct Qid9p1
{@@ -215,7 +215,14 @@
max size 57731387018*Blocksize = 28981156283036 bytes = 26 TiB
.fi
.sp
-reli is the relative index within a directory entry. A zero reli is first data block in the directory entry and a reli of 1 is the second data block of the directory entry.
+.sp
+.ne 20
+.sp
+On an empty mafs filesystem mounted at /n/mafs, the disk contents added by the below commands are:
+.nf
+mkdir /n/mafs/dir1
+echo test > /n/mafs/dir1/file1
+.fi
.PS
right
bigboxht = boxht
@@ -222,7 +229,7 @@
fieldht = 0.35*boxht
{down
- { Bound: box height 15*bigboxht width 3.3*boxwid }+ { Bound: box height 10*bigboxht width 3.3*boxwid }move 0.1i
box height fieldht invis "Tdentry 1 64"
box height fieldht invis "qid.version 0"
@@ -235,36 +242,22 @@
box height fieldht invis "uid 10006"
box height fieldht invis "gid -1"
box height fieldht invis "muid 10006"
- box height fieldht invis "direct spans"
- box height fieldht invis " 0 19 1"
- box height fieldht invis " 1 0 0"
- box height fieldht invis " 2 0 0"
- box height fieldht invis " 3 0 0"
- box height fieldht invis " 4 0 0"
- box height fieldht invis " 5 0 0"
- box height fieldht invis " 6 0 0"
- box height fieldht invis " 7 0 0"
- box height fieldht invis " 8 0 0"
- box height fieldht invis " 9 0 0"
- box height fieldht invis " 10 0 0"
- box height fieldht invis " 11 0 0"
- box height fieldht invis " 12 0 0"
- box height fieldht invis " 13 0 0"
- box height fieldht invis " 14 0 0"
- box height fieldht invis " 15 0 0"
- box height fieldht invis " 16 0 0"
- box height fieldht invis " 17 0 0"
- box height fieldht invis " 18 0 0"
- box height fieldht invis " 19 0 0"
- box height fieldht invis " 20 0 0"
- box height fieldht invis " 21 0 0"
- box height fieldht invis " 22 0 0"
- box height fieldht invis " 23 0 0"
+ box height fieldht invis "direct blocks"
+ box height fieldht invis " 0 19"
+ box height fieldht invis " 1 0"
+ box height fieldht invis " 2 0"
+ box height fieldht invis "."
+ box height fieldht invis "."
+ box height fieldht invis "."
+ box height fieldht invis " 30 0"
+ box height fieldht invis " 31 0"
box height fieldht invis "indirect blocks"
box height fieldht invis " 0 0"
box height fieldht invis " 1 0"
box height fieldht invis " 2 0"
box height fieldht invis " 3 0"
+ box height fieldht invis " 4 0"
+ box height fieldht invis " 5 0"
box height fieldht invis "name dir1"
"Block 18 contents: /dir1 Dentry" at Bound.nw + 0,0.1i ljust
"Representation of a file in a directory: /dir1/file1" ljust at Bound.n + 0,0.3i
@@ -272,7 +265,7 @@
move 4*boxwid
{down
- { Bound: box height 15*bigboxht width 3.3*boxwid }+ { Bound: box height 10*bigboxht width 3.3*boxwid }move 0.1i
box height fieldht invis "Tdentry 1 65"
box height fieldht invis "qid.version 0"
@@ -285,40 +278,33 @@
box height fieldht invis "uid 10006"
box height fieldht invis "gid -1"
box height fieldht invis "muid 10006"
- box height fieldht invis "direct spans"
- box height fieldht invis " 0 20 1"; {"content is in Block 20" at last box.e + 1i,0 ljust}- box height fieldht invis " 1 0 0"
- box height fieldht invis " 2 0 0"
- box height fieldht invis " 3 0 0"
- box height fieldht invis " 4 0 0"
- box height fieldht invis " 5 0 0"
- box height fieldht invis " 6 0 0"
- box height fieldht invis " 7 0 0"
- box height fieldht invis " 8 0 0"
- box height fieldht invis " 9 0 0"
- box height fieldht invis " 10 0 0"
- box height fieldht invis " 11 0 0"
- box height fieldht invis " 12 0 0"
- box height fieldht invis " 13 0 0"
- box height fieldht invis " 14 0 0"
- box height fieldht invis " 15 0 0"
- box height fieldht invis " 16 0 0"
- box height fieldht invis " 17 0 0"
- box height fieldht invis " 18 0 0"
- box height fieldht invis " 19 0 0"
- box height fieldht invis " 20 0 0"
- box height fieldht invis " 21 0 0"
- box height fieldht invis " 22 0 0"
- box height fieldht invis " 23 0 0"
+ box height fieldht invis "direct blocks"
+ box height fieldht invis " 0 20"; {"content is in Block 20" at last box.e + 1i,0 ljust}+ box height fieldht invis " 1 0"
+ box height fieldht invis " 2 0"
+ box height fieldht invis "."
+ box height fieldht invis "."
+ box height fieldht invis "."
+ box height fieldht invis " 30 0"
+ box height fieldht invis " 31 0"
box height fieldht invis "indirect blocks"
box height fieldht invis " 0 0"
box height fieldht invis " 1 0"
box height fieldht invis " 2 0"
box height fieldht invis " 3 0"
+ box height fieldht invis " 4 0"
+ box height fieldht invis " 5 0"
box height fieldht invis "name file1"
"Block 19 contents: file1 Dentry" at Bound.nw + 0,0.1i ljust
}
.PE
+.sp
+Contents of block 20 are:
+.nf
+disk/block tests/test.1/disk 20 | xd -c
+0000000 T d a t a 6 5 \n t e s t \n
+000000e
+.fi
.PS
right
Start: {@@ -336,17 +322,17 @@
box height fieldht invis "uid 10006"
box height fieldht invis "gid -1"
box height fieldht invis "muid 10006"
- box height fieldht invis "direct spans"
- box height fieldht invis " 0 22 1"
- box height fieldht invis " 1 24 1"
+ box height fieldht invis "direct blocks"
+ box height fieldht invis " 0 22"
+ box height fieldht invis " 1 24"
box height fieldht invis "."
box height fieldht invis "."
box height fieldht invis "."
- box height fieldht invis " 23 0 0"
+ box height fieldht invis " 31 0"
box height fieldht invis "indirect blocks"
box height fieldht invis " 0 0"
box height fieldht invis "."
- box height fieldht invis " 3 0"
+ box height fieldht invis " 5 0"
box height fieldht invis "name dir2"
"Block 21 contents: /dir2 Dentry" at Bound.nw + 0,0.1i ljust
"Representation of two files in a directory (/dir2/file1 and /dir2/file2)" ljust at Bound.nw + 0.2,0.3i
@@ -367,17 +353,17 @@
box height fieldht invis "uid 10006"
box height fieldht invis "gid -1"
box height fieldht invis "muid 10006"
- box height fieldht invis "direct spans"
- box height fieldht invis " 0 23 1"
- box height fieldht invis " 1 0 0"
+ box height fieldht invis "direct blocks"
+ box height fieldht invis " 0 23"
+ box height fieldht invis " 1 0"
box height fieldht invis "."
box height fieldht invis "."
box height fieldht invis "."
- box height fieldht invis " 23 0 0"
+ box height fieldht invis " 31 0"
box height fieldht invis "indirect blocks"
box height fieldht invis " 0 0"
box height fieldht invis "."
- box height fieldht invis " 3 0"
+ box height fieldht invis " 5 0"
box height fieldht invis "name file1"
"Block 22 contents: file1 Dentry" at Bound.nw + 0,0.1i ljust
}
@@ -398,21 +384,74 @@
box height fieldht invis "uid 10006"
box height fieldht invis "gid -1"
box height fieldht invis "muid 10006"
- box height fieldht invis "direct spans"
- box height fieldht invis " 0 25 1"
- box height fieldht invis " 1 0 0"
+ box height fieldht invis "direct blocks"
+ box height fieldht invis " 0 25"
+ box height fieldht invis " 1 0"
box height fieldht invis "."
box height fieldht invis "."
box height fieldht invis "."
- box height fieldht invis " 23 0 0"
+ box height fieldht invis " 31 0"
box height fieldht invis "indirect blocks"
box height fieldht invis " 0 0"
box height fieldht invis "."
- box height fieldht invis " 3 0"
+ box height fieldht invis " 5 0"
box height fieldht invis "name file2"
"Block 24 contents: file2 Dentry" at Bound.nw + 0,0.1i ljust
}
.PE
+.sp
+iblocks[0] has the block number of a Tind0 block. A Tind0 block has a list of Tdata block numbers for files and Tdentry block numbers for directories.
+.sp
+iblocks[1] contains the block number of a Tind1 block. A Tind1 block has a list of block numbers of Tind0 blocks.
+.sp
+Similarly, for other iblocks[n] entries, iblocks[n] contains the block number of a Tind\fIn\fR block. A Tind\fIn\fR block has a list of block numbers of Tind\fI(n-1)\fR blocks.
+.sp
+.sp
+Relative index
+.sp
+The zero'th relative index in a directory entry is the first data block. The next relative index is the second data block of the directory entry, and so on.
+.sp
+tests/chkreli.rc tests the translation of a relative index(reli) to an actual disk block number.
+.sp
+To find the actual block number where the first block (zero'th as zero indexed) of a file is stored:
+.nf
+tests/6.reli 0 # command, below is the output of this command
+reli 0
+dblock[0]
+.fi
+.sp
+To find the actual block number where the second block of a file is stored:
+.nf
+tests/6.reli 1
+reli 1
+dblock[1]
+.fi
+.sp
+And so on, for the 32nd and 33rd blocks of a file:
+.nf
+tests/6.reli 31
+reli 31
+dblock[31]
+
+tests/6.reli 32
+reli 32
+iblock[0]
+Tind0 reli 0 is at [0]
+.fi
+.sp
+This is how the last block of a 26 TiB file would be stored:
+.nf
+tests/6.reli 57731387017
+reli 57731387017
+iblock[5]
+Tind5 reli 56800235583 is at [61]
+Tind4 reli 916132831 is at [61]
+Tind3 reli 14776335 is at [61]
+Tind2 reli 238327 is at [61]
+Tind1 reli 3843 is at [61]
+Tind0 reli 61 is at [61]
+.fi
+.sp
.PS
right
Start: {@@ -430,7 +469,7 @@
box height fieldht invis "uid 10006"
box height fieldht invis "gid -1"
box height fieldht invis "muid 10006"
- box height fieldht invis "direct spans"
+ box height fieldht invis "direct blocks"
box height fieldht invis " 0 28 2048"
box height fieldht invis " 1 2076 1969"
box height fieldht invis " 2 0 0"
@@ -467,7 +506,7 @@
box height fieldht invis "uid 10006"
box height fieldht invis "gid -1"
box height fieldht invis "muid 10006"
- box height fieldht invis "direct spans"
+ box height fieldht invis "direct blocks"
box height fieldht invis " 0 8123 2048"
box height fieldht invis " 1 10171 2048"
box height fieldht invis " 2 12219 2048"
@@ -523,36 +562,8 @@
}
.PE
.sp
-kfs and cwfs use blocks but with a size of 8192 bytes. Hence, they store multiple directory entries (Dentry) per block. They use slot numbers to identify a particular directory entry in a block of directory entries.
+The Tag.dirty flag is set while a block is being written. This helps identify dirty blocks after a crash.
.sp
-iblocks[0] contains the block number of a Tind0 Span(1 block). A Tind0 Span is a list of Span identifiers with the block numbers of Tdata Span's for files and Tdentry Span's for directories.
-.sp
-iblocks[1] contains the block number of a Tind1 Span(1 block). A Tind1 Span is a list of block numbers of Tind0 blocks.
-.sp
-Similarly, for other iblocks[n] entries, iblocks[n] contains the block number of a Tind\fIn\fR Span(1 block). A Tind\fIn\fR Span is a list of block numbers of Tind\fI(n-1)\fR blocks.
-.sp
-The Tag.dirty flag is set while a Span is being written. This helps identify dirty Span's after a crash.
-.sp
-To increase read and write throughput, all Tdata allocations will be Span's (Block number + len). The maximum Span length is 1MB (Maxspanlen blocks). Only the last span can be less than 1MB size.
-.sp
-A directory entry once assigned is not given up until the parent directory is removed. It is zero'ed if the directory entry is removed. It is reused by the next directory entry created under that parent directory. This removes the need for garbage collection of directory entries on removals and also avoids zero block numbers in the middle of a directory. A zero block number while traversing a directory's dspanids or iblocks represents the end of directory or file contents. When a directory is removed, the parent will have a directory entry with a tag of Tdentry and Qpnone and the rest of the contents set to zero.
-.sp
-A directory's size is always zero.
-.sp
-A file's data blocks are identified by a tag of Tdata and Qid.path. A block number of zero represents the end of the file's contents. If a file is truncated, the data and indirect blocks are given up and the dentry.dspanids[0] = (Spanid){0,0}.-.sp
-The directory entry is locked with a read-write lock (RWlock) for any file operations. This ensures synchronization across multiple processes updating the same file.
-.sp
-Why is the Span's len stored in the directory entry when the same information can be obtained from the block's Tag.len?
-.br
-.in 3n
-.ti 0
-1. This avoids an extra read call for the Tag.len before getting the contents from the disk. Instead, we can read the contents with one read call as we know the number of blocks to read. Also, it works as a cross-checking mechanism if the Tag gets overwritten.
-.br
-.ti 0
-2. Code is simpler when we store the length of the Span in the directory entry.
-.in 0
-.sp
.TS
box;
c s s s
@@ -616,18 +627,28 @@
Mafs needs atleast Nminblocks=17 blocks (8.5 KB). The middle block number is Nminblocks + ((nblocks - Nminblocks)/2), where nblocks = total number of blocks.
.fi
.sp
+A directory entry once assigned is not given up until the parent directory is removed. It is zero'ed if the directory entry is removed. It is reused by the next directory entry created under that parent directory. This removes the need for garbage collection of directory entries on removals and also avoids zero block numbers in the middle of a directory. A zero block number while traversing a directory's dspanids or iblocks represents the end of directory or file contents. When a directory is removed, the parent will have a directory entry with a tag of Tdentry and Qpnone and the rest of the contents set to zero.
.sp
+A directory's size is always zero.
+.sp
+A file's data blocks are identified by a tag of Tdata and Qid.path. A block number of zero represents the end of the file's contents. If a file is truncated, the data and indirect blocks are given up and the dentry.dblocks[0] = 0.
+.sp
+The directory entry is locked with a read-write lock (RWlock) for any file operations. This ensures synchronization across multiple processes updating the same file.
+.sp
+kfs and cwfs use 8192 byte blocks. Hence, they store multiple directory entries (Dentry) per block. They use slot numbers to identify a particular directory entry in a block of directory entries. Mafs avoids that be using 512 byte blocks thus having only one directory entry per block. This avoids locking up other sibling directory entries on access.
+.sp
+.sp
.ft B
-Buffer cache - Hash buckets with circular linked list of Iobuf's for collisions.
+Buffer cache - Hash buckets with a circular linked list of Iobuf's for collisions.
.ft R
.sp
-An Iobuf is used to represent a Span in memory. An Iobuf is unique to a Span. All disk interaction, except for free block management, happens through an Iobuf. We read Span's from the disk into an Iobuf. To update Span's on the disk, we write to an Iobuf, which, in-turn gets written to the disk.
+An Iobuf is used to represent a block in memory. An Iobuf is unique to a block. All disk interaction, except for free block management, happens through an Iobuf. We read a block from the disk into an Iobuf. To update a block on the disk, we write to an Iobuf, which, in-turn gets written to the disk.
.sp
-getbuf() and putbuf() are used to manage Iobuf's. The contents of an Iobuf is not touched unless it is locked between getbuf() and putbuf() calls.
+getbuf(), putbuf() and putbuffree() are used to manage Iobuf's. The contents of an Iobuf is not touched unless it is locked between getbuf(), putbuf() and putbuffree() calls.
.sp
-allocblocks() allocates free blocks into an Iobuf.
+allocblock() allocates free blocks into an Iobuf.
.sp
-freeblocks() erases the Iobuf and returns the blocks to the free block management routines.
+freeblock() erases the Iobuf and returns the block to the free block management routines.
.sp
Iobuf's are organized into a list of hash buckets to speed up access.
.sp
@@ -642,7 +663,6 @@
Ref;
RWLock;
u64 blkno; /* block number on the disk, primary key */
- u16 len; /* number of blocks of data xiobuf points to */
Iobuf *fore; /* for lru */
Iobuf *back; /* for lru */
union{@@ -649,7 +669,8 @@
u8 *xiobuf; /* "real" buffer pointer */
Content *io; /* cast'able to contents */
}
- int flags;
+ u32 dirties;
+ u8 tofree;
};
.fi
.sp
@@ -690,13 +711,65 @@
.PE
.sp
The size of the buffer cache is approximately: number of hash buckets * collisions per hash bucket * Maximum Span size. By default, the approximate size of the buffer cache = Nbuckets * Ncollisions * Maxspansize = 256 * 10 * 1MB = 2.56GB. The -h parameter can be used to change the number of hash buckets.
-.\" .sp
-.\" What is the need for Iobuf.Ref?
-.\" I have two threads that are writing to the same file. The file's directory entry is in block 18.
.sp
+Iobuf.Ref is used to avoid locking up the hash bucket when a process is waiting for a lock on an Iobuf in that hash bucket.
.sp
+Iobuf.Ref ensures that an Iobuf is not stolen before another process can get to wlock()'ing it after letting go of the lock on the hash bucket. We cannot hold the lock on the hash bucket until we wlock() the iobuf as that blocks other processes from using the hash bucket. This could also result in a deadlock. For example, the directory entry is block 18, which hashes to a hash index of 7. A writer() locked the directory entry iobuf and wants to add a data block 84 to the directory entry. Block 84 hashes to the same hash index of 7. Another process wanting to access the directory entry is waiting for a lock on that io buffer. While doing so, it has locked the hash bucket. Now, this has caused a deadlock between both these processes. The first process cannot proceed until it can lock the hash bucket holding block 84 and is still holding the lock on the directory entry in block 18. The second process cannot lock block 18 and is holding the lock on the hash bucket.
+.nf
+ for locking a buffer:
+ qlock(hash bucket); incref(buffer); qunlock(hash bucket);
+ wlock(buffer); decref(buffer);
+
+ for stealing an unused buffer:
+ qlock(hash bucket);
+ find a buffer with ref == 0 and wlock()'able.
+ qunlock(hash bucket);
+
+ for unlocking a buffer:
+ wunlock(buffer);
+.fi
+.sp
+.sp
.ne 4
.ft B
+Asynchronous writes
+.ft R
+.sp
+The blocks to be written to a disk are stored to a linked list represented by:
+.nf
+typedef struct Dirties Dirties;
+typedef struct Wbuf Wbuf;
+
+struct Dirties
+{+ QLock lck;
+ Wbuf *head, *tail;
+ s32 n;
+ Rendez isempty;
+} drts = {0};+
+struct Wbuf
+{+ u64 blkno; /* block number on the disk, primary key */
+ u16 len; /* number of blocks of data xiobuf points to */
+ Wbuf *prev, *next;
+ Iobuf *iobuf;
+ union{+ u8 payload; /* "real" contents */
+ Content io; /* cast'able to contents */
+ };
+};
+.fi
+.sp
+A writer process takes the blocks from the Dirties linked list on a FIFO (first-in-first-out) basis and writes them to the disk. putbuf() adds blocks to the end of this linked list.
+.sp
+The dirty blocks not yet written to the disk remain in the buffer cache and cannot be stolen when a need for new Iobuf's arises.
+.sp
+Free'd blocks are not written to the disk to avoid writing blanks to a disk.
+.sp
+.sp
+.ne 4
+.ft B
Free blocks - Extents
.ft R
.sp
@@ -706,6 +779,7 @@
.sp
A tag of Tfree and Qpnone represents a free block. If a directory entry is removed, the parent will have a zero'ed out child directory entry (Qid.path = 0) and a tag of Tdentry and Qpnone.
.sp
+.ne 14
Algorithm to allocate blocks from Extents:
.in 3n
.br
@@ -1032,8 +1106,9 @@
iobuf.c routines on Iobuf's. The bkp() routines operate on Iobuf's. 5
extents.[ch] routines to manage the free blocks. 6
ctl.c /adm/ctl operations.
-tag.c routines to convert from a relative index in a directory entry to a tag.
+tag.c routines to manage a relative index (reli) in a directory entry.
blk.c routines to show blocks.
+writer.c disk writer routines.
console.c obsolete. /adm/ctl is the console.
.TE
.ta 5n 10n 15n 20n 25n 30n 35n 40n 45n 50n 55n 60n 65n 70n 75n 80n
@@ -1151,7 +1226,7 @@
A Tind3 unit points to 192200 data spans (201534000800 bytes)
block points to 11916400 data spans
sizeof(Dentry1) 326 Namelen 174
-maxsize direct spans max 24
+maxsize direct blocks max 24
maxsize Tind0 50 max 74
maxsize Tind1 3100 max 3174
maxsize Tind2 192200 max 195374
@@ -1168,16 +1243,22 @@
Tests
.ft R
.sp
-tests/regress.rc: Regression tests.
+.TS
+box;
+c l
+l a .
+Program Description
+_
+tests/regress.rc All regression tests
+tests/chkextents.rc Unit tests on extents
+tests/chkreli.rc Unit tests on relative index lookups
+_
+tests/6.offsets Write file using different offsets to test mafswrite()
+tests/6.sizes Show the effects of the different parameters
+tests/6.testextents Test extents.[ch] state changes
+tests/6.reli Translate relative index to block number on a disk
+.TE
.sp
-tests/6.offsets: Write file using different offsets to test mafswrite().
-.sp
-tests/6.sizes: Show the effects of the different parameters.
-.sp
-tests/chkextents.rc: Unit tests on extents.
-.sp
-tests/6.testextents: Test extents.[ch] state changes.
-.sp
The below disk state tests:
.in 3n
.br
@@ -1252,7 +1333,14 @@
Limitations
.ft R
.sp
-As we use packed structs to store data to the disk, a disk with mafs is not be portable to a machine using a different endian system.
+As we use packed structs to store data to the disk, a disk with mafs is not portable to a machine using a different endian system.
+.sp
+.sp
+.ft B
+Source
+.ft R
+.sp
+http://git.9front.org/plan9front/mafs/HEAD/info.html
.sp
.sp
.ft B
binary files a/docs/mafs.pdf b/docs/mafs.pdf differ