| git.druid.rocks | index | druid520 | kaboom | src/ | fs/ | kfs.nsc |
src/fs/kfs.nsc
/*
* kfs: hand-rolled flat filesystem, not fat12/fat32, not a port of
* tape-kernel's ffs (clean-room, feature-inherited-not-copied per the
* license split -- tape-kernel is gplv3, this is fmc).
*
* every on-disk field is a full 8-byte word, deliberately: unlike
* gdt/idt entries (whose byte layout is dictated by the cpu) this
* format is entirely kaboom's own invention, so there was no reason
* to fight nsc's pointer model (*p is always a full 8-byte load/store,
* no byte/halfword deref, no struct byte-packing) when word-aligning
* every field sidesteps the whole problem instead.
*
* layout (block = 512 bytes, one ata sector):
* block 0 : superblock
* block 1..N : inode table (one inode per block, one inode's
* own block wholly its own -- no packing, no
* sub-block offset math)
* block N+1..M : root directory data (flat, no subdirectories yet)
* block M+1..end : file data blocks
*
* inode (512 bytes = 64 words = one whole block): type, perm, size,
* 56 direct block ptrs (offsets 24..471), 1 single-indirect block ptr
* (offset 472), 4 double-indirect block ptrs (offsets 480..511) -- see
* kfs_block_tier for the exact block-index -> pointer mapping every
* consumer shares, and kfs_write_file's own note for the indirect
* formats. 56 direct + 64 via the single-indirect block + 4*64*64 via
* the double-indirect blocks = 16504 blocks * 512 bytes = 8450048-byte
* (~8.06mib) max file size. same pattern as everything else in this
* kernel (ship the real minimal version, extend when it's proven
* necessary rather than before): this cap was raised three times as a
* flat bump (64-byte/5-direct-block, then 128-byte/13-direct-block,
* then 512-byte/61-direct-block) as kaboom's own coreutils outgrew it,
* then once via single indirection (60 direct + 64 = 63488 bytes),
* and now via double indirection, done the moment something real (the
* 160512-byte raw kernel blob as an inspection file) needed more than
* that. past this, a triple-indirect level is the known follow-up.
*
* permissions: bitmask, r=1 w=2 x=4 (rwx=7), same scheme for files
* and directories both -- genuinely enforced (kfs_check_perm), not
* just stored: for a file, r gates opening it for reading (fd.nsc's
* fd_open) and x gates running it (exec.nsc's sys_exec, including a
* shebang script's own interpreter re-exec); for a directory, r gates
* listing it (kfs_dir_list/kfs_dir_list_path), w gates creating or
* removing an entry within it (kfs_create/kfs_mkdir/kfs_rm/kfs_rmdir,
* all via kfs_resolve_parent's own parent_inode_out), and x gates
* traversing through it at all (every intermediate component of any
* path, plus the final directory kfs_cd is actually moving into).
* unconditional, with no owner/group/other split and no chmod gate of
* its own to check against first: there's exactly one user here, so
* the stored bitmask is simply the whole answer, every time.
*/
i32 ata_read_sector(u32 lba, ptr buf);
i32 ata_write_sector(u32 lba, ptr buf);
/* forward declaration -- kfs_check_perm is defined much further down
* (right where it's most at home, next to kfs_chmod), but permission
* enforcement needed it available from kfs_dir_list onward, near the
* top of this file. */
i32 kfs_check_perm(i32 inode_num, u64 bit);
/* forward declaration -- kfs_rm lives down with kfs_rmdir, but
* kfs_save uses it to undo its own kfs_create when the write fails. */
i32 kfs_rm(ptr name, u64 name_len);
/* forward declaration -- kfs_is_virt_dir lives next to kfs_file_size,
* but kfs_create/kfs_mkdir (defined earlier) need it too. */
i32 kfs_is_virt_dir(u64 dir_lba);
/* the reason the most recent failing kfs/fd/exec call actually
* failed -- 0 (unknown/not-permission: doesn't exist, already
* exists, not empty, ...) or 1 (EPERM, set only by kfs_check_perm).
* every public entry point resets this to 0 at its own start; see
* kfs_check_perm's own comment for the full reasoning. idt.nsc's
* sys_doerror reads this to log a real reason, not just "failed", to
* the kernel log. */
global i32 kaboom_errno;
global u64 kfs_magic; /* "kaboomfs" as 8 bytes, little-endian */
global u64 kfs_total_blocks;
global u64 kfs_inode_table_lba;
global u64 kfs_inode_count;
global u64 kfs_root_dir_lba;
global u64 kfs_cwd_dir_lba; /* data block lba of the CURRENT directory */
global i32 kfs_cwd_inode; /* inode number of the current directory */
global i8 kfs_cwd_path[256]; /* printable path, tracked alongside cwd_dir_lba
* rather than reconstructed from parent
* pointers -- no parent pointer exists (see
* the note on kfs_cd for why), so this is the
* only record of "how did we get here". */
global u64 kfs_data_start_lba;
global u64 kfs_root_inode;
global u64 kfs_bin_dir_lba; /* /bin's own data block lba, resolved once
* at mount time -- sys_exec's fallback
* lookup for "found in cwd? no? try /bin"
* (a real, minimal $PATH), see kfs_mount. */
global u64 kfs_proc_dir_lba; /* /proc's own data block lba, resolved the
* same way as kfs_bin_dir_lba -- virtfs.nsc's
* dispatch checks a name's PARENT against
* this (and kfs_int_dir_lba) to decide if a
* file's content should come from a live
* generator instead of real disk blocks. */
global u64 kfs_int_dir_lba; /* /int's own data block lba -- see kfs_proc_dir_lba. */
/* kfs.h-equivalent constants -- nsc has no #include/#define-for-others
* mechanism, so every file that needs these just repeats the literal
* with a comment, same as the vector numbers in idt.nsc/kbd.nsc. */
/* KFS_MAGIC = 0x7366_6d6f_6f62_616b ("kaboomfs" bytes, LE) */
/* KFS_TYPE_FREE = 0, KFS_TYPE_FILE = 1, KFS_TYPE_DIR = 2 */
/* KFS_INODES_PER_BLOCK = 1 (one whole 512-byte block per inode) */
/* KFS_DIRENT_SIZE = 32 (8-byte inode num + 24-byte name) */
/* KFS_DIRENTS_PER_BLOCK = 16 (512 / 32) */
/* KFS_LBA_BASE = 1025 (real disk lba of kfs's own block 0) */
/* kfs's own block numbering (superblock at "block 0", exactly as it
* always has been) is completely unaffected by this -- every existing
* kfs_* function still computes the same lba it always did. this is
* the one place that number becomes a REAL disk lba: the bios
* bootloader ("dynamite", src/boot/dynamite.s) occupies real lba 0,
* and the raw kernel blob it loads occupies real lba 1-1024, so
* kfs's own "block 0" actually lives at real lba 1025. mk/disk.pl's
* put_block applies this identical offset when it lays out the
* initial disk image -- the two have to agree exactly, or kfs_mount
* looks for its own superblock at the wrong real sector and fails
* outright. */
void
kfs_read_block(u64 lba, ptr buf)
{
ata_read_sector((u32)(lba + (u64)1025), buf);
}
void
kfs_write_block(u64 lba, ptr buf)
{
ata_write_sector((u32)(lba + (u64)1025), buf);
}
/* reads inode n into a caller-supplied 512-byte buffer. one inode is
* one whole block now, so this is just a direct block read -- no
* sub-block offset, no read-modify-write of a shared block. */
global void
kfs_read_inode(u64 n, ptr inode_buf)
{
kfs_read_block(kfs_inode_table_lba + n, inode_buf);
}
/* same story: the inode's own block belongs to it alone, so writing
* it is a plain overwrite, not a read-patch-write of a block shared
* with other inodes. */
global void
kfs_write_inode(u64 n, ptr inode_buf)
{
kfs_write_block(kfs_inode_table_lba + n, inode_buf);
}
/* formats a fresh disk: writes the superblock, zeroes the inode
* table, marks inode 0 as the root directory (empty), zeroes the root
* directory's first data block. total_blocks/inode_count are chosen
* by the caller based on the real disk size -- kfs itself has no way
* to probe that yet (needs an ata identify call this driver doesn't
* do), so this is deliberately explicit rather than guessed. */
global void
kfs_mkfs(u64 total_blocks, u64 inode_count)
{
i8 zero[512];
i8 inode[512];
u64 i;
ptr p;
kfs_magic = (u64)0x73666d6f6f62616b; /* "kaboomfs" bytes, little-endian */
kfs_total_blocks = total_blocks;
kfs_inode_table_lba = (u64)1;
kfs_inode_count = inode_count;
kfs_root_dir_lba = kfs_inode_table_lba + inode_count;
kfs_data_start_lba = kfs_root_dir_lba + (u64)1;
kfs_root_inode = (u64)0;
kfs_next_free_block = kfs_data_start_lba;
kfs_next_free_inode = (u64)1; /* inode 0 is the root directory */
kfs_cwd_dir_lba = kfs_root_dir_lba;
kfs_cwd_inode = 0;
kfs_cwd_path[0] = (i8)47; /* '/' */
kfs_cwd_path[1] = 0;
kfs_bin_dir_lba = kfs_root_dir_lba; /* no /bin yet on a fresh format */
kfs_proc_dir_lba = kfs_root_dir_lba; /* no /proc yet on a fresh format */
kfs_int_dir_lba = kfs_root_dir_lba; /* no /int yet on a fresh format */
i = 0;
while(i < (u64)512)
{
zero[i] = 0;
i = i + 1;
}
/* superblock */
p = &zero[0];
*p = (i64)kfs_magic;
*(p + 8) = (i64)kfs_total_blocks;
*(p + 16) = (i64)kfs_inode_table_lba;
*(p + 24) = (i64)kfs_inode_count;
*(p + 32) = (i64)kfs_root_dir_lba;
*(p + 40) = (i64)kfs_data_start_lba;
*(p + 48) = (i64)kfs_root_inode;
kfs_write_block((u64)0, &zero[0]);
/* zero every inode table block -- zero[] must be re-zeroed first:
* it still holds the superblock's own fields from just above, and
* writing THAT to every inode block would leave every inode's own
* type field (offset 0 of its now-whole-block inode, since inodes
* stopped being packed several-per-block) reading back as the
* superblock magic's low bytes instead of a genuine 0 -- a real
* bug that was harmless by pure coincidence under the old packed
* inode layout (a packed inode's own type field landed past the
* 56 bytes of real superblock content that block ever held) and
* only started actually mattering once inodes became whole
* blocks. found by kfs_create failing outright on every inode
* past inode 0 once this format changed. */
i = 0;
while(i < (u64)512)
{
zero[i] = 0;
i = i + 1;
}
i = 0;
while(i < inode_count)
{
kfs_write_block((u64)1 + i, &zero[0]);
i = i + 1;
}
/* root directory inode: type=dir, perm=rwx (7), size=0 */
i = 0;
while(i < (u64)512)
{
inode[i] = 0;
i = i + 1;
}
p = &inode[0];
*p = (i64)2; /* KFS_TYPE_DIR */
*(p + 8) = (i64)7; /* rwx */
*(p + 16) = (i64)0; /* size */
*(p + 24) = (i64)kfs_root_dir_lba; /* direct block 0 */
kfs_write_inode(kfs_root_inode, &inode[0]);
/* the root directory's data block: every slot's inode-number
* field must start as the ~0 "empty" sentinel, NOT zero -- inode 0
* is the root directory itself, a genuinely valid inode number, so
* a zeroed slot looks exactly like an occupied slot pointing at
* inode 0 rather than an empty one. kfs_dir_add would never find a
* free slot in a freshly formatted, completely empty directory
* without this -- caught by kfs_create failing outright on the
* very first file ever created on a fresh disk. */
i = 0;
while(i < (u64)16)
{
p = &zero[0] + i * (u64)32;
*p = (i64)(~(u64)0);
i = i + (u64)1;
}
kfs_write_block(kfs_root_dir_lba, &zero[0]);
}
/* computes exactly where in a file's block-pointer structure logical
* block b lives, returning the tier (0 = one of the 56 direct pointers,
* 1 = via the single-indirect pointer, 2 = via one of the 4
* double-indirect pointers) and writing out whichever of dp_out/slot_out/
* l2_out that tier actually needs -- unused out-params for a given tier
* are left untouched, callers only ever read the ones that tier's own
* branch needs:
* - tier 0: *slot_out = which of the 56 direct pointers (0..55).
* - tier 1: *slot_out = index into the single-indirect block (0..63).
* - tier 2: *dp_out = which of the 4 double-indirect pointers (0..3),
* *slot_out = index into that pointer's first-level block (0..63),
* *l2_out = index into the resulting second-level block (0..63).
* one double-indirect pointer reaches 64*64 = 4096 blocks (2mib); 56
* direct + 64 single-indirect + 4*4096 double-indirect = 16504 blocks =
* 8450048 bytes, the new FORMAT ceiling (a real, known follow-up past
* THIS would be a third indirection level or more double-indirect
* pointers -- same "extend when something actually needs it" pattern as
* every earlier size bump here, most recently single indirection
* itself). not the same as what's actually reachable today: a single
* open file is capped by fs_colosseum (4mib, fd_buf_need/alloc.nsc), a
* fresh default disk image only has ~1.5mib free (mk/disk.pl's own
* 2mib floor, minus everything already baked in), and one boot's total
* budget for large reads is bounded by the heap's own 12mib remainder
* after fs_colosseum's carve-out, since arena_alloc never frees (alloc.nsc)
* -- each raiseable independently, same "extend when something needs
* it" pattern, not attempted here since nothing needs it yet. this is
* the single place the tier arithmetic itself is computed --
* kfs_write_file, kfs_read_file, and kfs_scan_allocators all call this
* instead of separately re-deriving it, so the three can never silently
* drift out of agreement with each other. defined up here, ahead of
* kfs_scan_allocators (its first caller in this file), rather than
* next to kfs_write_file. mk/disk.pl's build-time inode writer must mirror this
* same arithmetic in perl (it cannot call nsc) -- the two must stay
* byte-identical for any file size. */
i32
kfs_block_tier(u64 b, ptr dp_out, ptr slot_out, ptr l2_out)
{
u64 d;
if(b < (u64)56)
{
*slot_out = (i64)b;
return 0;
}
if(b < (u64)120)
{
*slot_out = (i64)(b - (u64)56);
return 1;
}
d = b - (u64)120;
*dp_out = (i64)(d / (u64)4096);
*slot_out = (i64)((d % (u64)4096) / (u64)64);
*l2_out = (i64)(d % (u64)64);
return 2;
}
/* scans the whole inode table, setting kfs_next_free_inode/
* kfs_next_free_block past everything already genuinely in use --
* the real fix for kfs_mount's own former "known real limitation"
* (see the removed comment this replaced): a disk built by
* disk.img.def, not freshly kfs_mkfs'd, already has real inodes and
* data blocks allocated (every directory, every baked-in binary)
* that kfs_mount used to know nothing about, so resetting both
* allocators to their bare "fresh format" minimums
* meant the very first mkdir/save after boot handed out and
* overwrote a block or inode something else was already using --
* found for real the moment a richer, pre-populated disk (the plan9-
* flavored directory tree) made that collision happen on the very
* first mkdir instead of needing several. */
void
kfs_scan_allocators(void)
{
i8 inode[512];
u64 n;
i64 type;
u64 size;
u64 nblocks;
u64 b;
u64 lba;
kfs_next_free_inode = (u64)1;
kfs_next_free_block = kfs_data_start_lba;
n = 0;
while(n < kfs_inode_count)
{
kfs_read_inode(n, &inode[0]);
type = *(&inode[0]);
if(type != (i64)0)
{
if(n + (u64)1 > kfs_next_free_inode)
{
kfs_next_free_inode = n + (u64)1;
}
if(type == (i64)2)
{
/* a directory's data is a CHAIN of blocks, not just
* the single one its own direct slot points at (see
* kfs_dir_next_block's own note on why) -- this used
* to stop at the first block, which was correct back
* when a directory really was only ever one block,
* but left every later chain block invisible to this
* scan once chaining shipped: a directory that had
* genuinely grown a second block (/bin already has,
* see kfs_dir_next_block) could have that live block
* handed right back out by the bump allocator on the
* next mkdir/save after a remount. */
i8 dirblock[512];
u64 chain_lba;
u64 chain_next;
i32 chain_done;
chain_lba = (u64)*(&inode[0] + 24);
chain_done = 0;
while(chain_done == 0)
{
if(chain_lba + (u64)1 > kfs_next_free_block)
{
kfs_next_free_block = chain_lba + (u64)1;
}
kfs_read_block(chain_lba, &dirblock[0]);
chain_next = kfs_dir_next_block(&dirblock[0]);
if(chain_next == ~(u64)0)
{
chain_done = 1;
}
else
{
chain_lba = chain_next;
}
}
}
else
{
/* a file: walk every block exactly the way kfs_read_file
* does (same kfs_block_tier, same lazily-loaded single-
* indirect/l1/l2 buffers), bumping kfs_next_free_block
* past every data block AND every pointer block itself
* (the single-indirect block, each first-level double-
* indirect block, each second-level block) -- missing
* any one of those would let the bump allocator hand a
* live block of a large file straight back out after a
* remount. */
i8 sind[512];
i8 l1[512];
i8 l2[512];
i32 have_sind;
i32 have_l1;
i32 have_l2;
u64 cur_dp;
u64 cur_l1;
u64 sind_lba;
u64 l1_lba;
u64 l2_lba;
i32 tier;
u64 dp;
u64 slot;
u64 l2idx;
size = (u64)*(&inode[0] + 16);
nblocks = (size + (u64)511) / (u64)512;
if(nblocks == (u64)0)
{
nblocks = (u64)1;
}
have_sind = 0;
have_l1 = 0;
have_l2 = 0;
cur_dp = ~(u64)0;
cur_l1 = ~(u64)0;
b = 0;
while(b < nblocks)
{
tier = kfs_block_tier(b, &dp, &slot, &l2idx);
if(tier == 0)
{
lba = (u64)*(&inode[0] + 24 + slot * (u64)8);
}
else if(tier == 1)
{
if(have_sind == 0)
{
sind_lba = (u64)*(&inode[0] + 472);
if(sind_lba + (u64)1 > kfs_next_free_block)
{
kfs_next_free_block = sind_lba + (u64)1;
}
kfs_read_block(sind_lba, &sind[0]);
have_sind = 1;
}
lba = (u64)*(&sind[0] + slot * (u64)8);
}
else
{
if(have_l1 == 0 || cur_dp != dp)
{
l1_lba = (u64)*(&inode[0] + 480 + dp * (u64)8);
if(l1_lba + (u64)1 > kfs_next_free_block)
{
kfs_next_free_block = l1_lba + (u64)1;
}
kfs_read_block(l1_lba, &l1[0]);
cur_dp = dp;
have_l1 = 1;
have_l2 = 0; /* old l2 belonged to the previous l1 */
}
if(have_l2 == 0 || cur_l1 != slot)
{
l2_lba = (u64)*(&l1[0] + slot * (u64)8);
if(l2_lba + (u64)1 > kfs_next_free_block)
{
kfs_next_free_block = l2_lba + (u64)1;
}
kfs_read_block(l2_lba, &l2[0]);
cur_l1 = slot;
have_l2 = 1;
}
lba = (u64)*(&l2[0] + l2idx * (u64)8);
}
if(lba + (u64)1 > kfs_next_free_block)
{
kfs_next_free_block = lba + (u64)1;
}
b = b + (u64)1;
}
}
}
n = n + (u64)1;
}
}
global i32
kfs_mount(void)
{
i8 block[512];
ptr p;
kfs_read_block((u64)0, &block[0]);
p = &block[0];
kfs_magic = (u64)*p;
if(kfs_magic != (u64)0x73666d6f6f62616b)
{
return 0;
}
kfs_total_blocks = (u64)*(p + 8);
kfs_inode_table_lba = (u64)*(p + 16);
kfs_inode_count = (u64)*(p + 24);
kfs_root_dir_lba = (u64)*(p + 32);
kfs_data_start_lba = (u64)*(p + 40);
kfs_root_inode = (u64)*(p + 48);
kfs_scan_allocators();
kfs_cwd_dir_lba = kfs_root_dir_lba;
kfs_cwd_inode = 0;
kfs_cwd_path[0] = (i8)47; /* '/' */
kfs_cwd_path[1] = 0;
/* resolve /bin once, up front, rather than on every exec: sys_exec's
* fallback lookup (cwd first, then kfs_bin_dir_lba) needs this
* whether or not the caller ever cd's anywhere -- kfs_dir_find_in
* against kfs_root_dir_lba directly, not kfs_dir_find, so this
* doesn't depend on (or disturb) cwd having just been set above.
* no /bin on this disk at all (an old image, or one built before
* disk.img.def started creating it) falls back to root, the same
* as kfs_mkfs's own default -- name lookups just never fall
* through to a second, redundant check of the same directory. */
{
i32 bin_inode;
i8 bin_inode_buf[512];
bin_inode = kfs_dir_find_in(kfs_root_dir_lba, "bin", (u64)3);
if(bin_inode >= 0)
{
kfs_read_inode((u64)bin_inode, &bin_inode_buf[0]);
kfs_bin_dir_lba = (u64)*(&bin_inode_buf[0] + 24);
}
else
{
kfs_bin_dir_lba = kfs_root_dir_lba;
}
}
/* same pattern again for /proc and /int -- virtfs_read (virtfs.nsc)
* needs both resolved once up front so it can recognize "a name's
* PARENT is one of these two" without re-walking from root on every
* single open(). falls back to root the same way kfs_bin_dir_lba
* does, for an old disk image built before disk.pl started creating
* these two directories. */
{
i32 proc_inode;
i8 proc_inode_buf[512];
proc_inode = kfs_dir_find_in(kfs_root_dir_lba, "proc", (u64)4);
if(proc_inode >= 0)
{
kfs_read_inode((u64)proc_inode, &proc_inode_buf[0]);
kfs_proc_dir_lba = (u64)*(&proc_inode_buf[0] + 24);
}
else
{
kfs_proc_dir_lba = kfs_root_dir_lba;
}
}
{
i32 int_inode;
i8 int_inode_buf[512];
int_inode = kfs_dir_find_in(kfs_root_dir_lba, "int", (u64)3);
if(int_inode >= 0)
{
kfs_read_inode((u64)int_inode, &int_inode_buf[0]);
kfs_int_dir_lba = (u64)*(&int_inode_buf[0] + 24);
}
else
{
kfs_int_dir_lba = kfs_root_dir_lba;
}
}
return 1;
}
global u64 kfs_next_free_block;
global u64 kfs_next_free_inode;
/* fills buf (caller-owned, room for 4 u64s = 32 bytes) with
* total_blocks, blocks_used, inode_count, inodes_used -- for info.
* buf is word-aligned by construction (a fresh caller-side u64[4] or
* equivalent), so these are plain aligned 8-byte stores, no
* packed-word read-modify-write needed (unlike the byte-at-a-time
* helpers elsewhere in this file). */
global void
kfs_info(ptr buf)
{
ptr p;
p = buf;
*p = (i64)kfs_total_blocks;
*(p + 8) = (i64)(kfs_next_free_block - kfs_data_start_lba);
*(p + 16) = (i64)kfs_inode_count;
*(p + 24) = (i64)kfs_next_free_inode;
}
/* reads one byte at an arbitrary offset from a raw ptr -- *p is
* always a full 8-byte load, so this does an (unaligned, fine on
* x86) 8-byte load starting exactly at base+index and keeps only the
* low byte. same technique vga_puts/serial_puts already use for
* walking a string one byte at a time, generalized to an arbitrary
* offset instead of always starting at 0. */
u8
ptr_byte_at(ptr base, u64 index)
{
ptr p;
u64 word;
p = base + index;
word = (u64)*p;
return (u8)(word & (u64)0xff);
}
/* ptr_byte_at's write counterpart -- nsc's `*p` is always a full
* 8-byte load/store (see mem.nsc's own note on this, userspace's
* mem_byte_set being the exact same technique), so a single-byte
* write has to read the containing aligned word, replace just the
* target byte, and write the whole word back. only kfs_join_path
* needs this today (writing through a caller-given ptr, not a local
* i8 array it can index directly by bracket) -- everywhere else in
* this file already builds its output into a typed i8[] local. */
void
ptr_byte_set(ptr base, u64 index, u8 val)
{
u64 wordoff;
u64 byteoff;
u64 word;
wordoff = index & ~(u64)7;
byteoff = index & (u64)7;
word = (u64)*(base + wordoff);
word = word & ~((u64)0xff << (byteoff * (u64)8));
word = word | ((u64)val << (byteoff * (u64)8));
*(base + wordoff) = (i64)word;
}
/* true if the first name_len bytes at name match the (up to 24-byte,
* null-padded) name field stored at dirblock[dirent_off+8 .. +31]. */
i32
kfs_name_matches(ptr name, u64 name_len, ptr dirblock, u64 dirent_off)
{
u64 i;
u8 a;
u8 b;
if(name_len > (u64)23)
{
return 0;
}
i = 0;
while(i < name_len)
{
a = ptr_byte_at(name, i);
b = ptr_byte_at(dirblock, dirent_off + (u64)8 + i);
if(a != b)
{
return 0;
}
i = i + 1;
}
/* the byte right after the matched prefix must be the null
* terminator, or "ab" would wrongly match a stored "abc". */
b = ptr_byte_at(dirblock, dirent_off + (u64)8 + name_len);
if(b != (u8)0)
{
return 0;
}
return 1;
}
/* returns the inode number for name in the root directory, or -1 if
* not found. flat namespace only -- no subdirectories yet. */
/* NOTE on inode_num = (u64)block[off]: this reads exactly ONE byte
* (block is a real array, block[off] is genuinely one byte), sign
* extended to u64 by the cast -- it is NOT reading the full 8-byte
* word a dirent's inode-number field nominally is. this is correct,
* not a truncation bug, because both sides agree: kfs_dir_add writes
* the same single low byte (block[slot] = (i8)inode_num, see there),
* and the empty-slot sentinel (~0, written as a genuine 8-byte word
* via *ptr in kfs_mkfs) reads back correctly here purely because its
* low byte (0xff) sign-extends to exactly ~(u64)0 too -- a real but
* fragile coincidence, not a coincidence-free design. effectively
* caps inode numbers this dirent format can address at 0-127, not
* 0-255: the same sign extension that makes 0xff read back as ~0 also
* makes every stored byte 0x80-0xfe read back negative, which every
* caller treats as "not found". kfs_inode_count (currently far below
* 128) never approaches that; widening the field would be an on-disk
* format change, not a fix. */
/* a directory is a CHAIN of these 512-byte blocks, not just one:
* slots 0-14 (offsets 0..448) are real dirents (up to 15 per block,
* one less than before), slot 15 (offset 480) is never a real dirent
* -- its full 8-byte word (not the fragile single-low-byte trick
* real dirents use) is either ~0 (no next block yet) or the lba of
* the next block in the chain. every dir_*_in function below walks
* this chain instead of assuming one block is all a directory ever
* needs.
*
* chosen over growing a directory's INODE to hold multiple direct
* block pointers (the way a FILE's inode already does) specifically
* because it needed zero changes to kfs_mkfs, mk/disk.pl's own block
* format, kfs_cwd_dir_lba/kfs_bin_dir_lba (both still just "a
* directory's lba", not "a directory's inode number"), or any
* existing caller: a freshly formatted block's slot 15 is ALREADY
* the ~0 sentinel every slot starts as, so "no next block yet" was
* already true of every directory block that existed before this
* chaining existed at all -- only kfs_dir_find_in/kfs_dir_list_in/
* kfs_dir_add_in/kfs_dir_remove_in (below) needed to actually change.
*
* found necessary for real: /bin outgrew 16 entries (17 coreutils)
* the moment a few more coreutils were added, and "mkdir: directory
* (lba N) full" -- disk.img.def's own guard for the single-block
* case -- fired for real, not hypothetically. */
u64
kfs_dir_next_block(ptr block)
{
return (u64)*(block + 480);
}
void
kfs_dir_set_next_block(ptr block, u64 lba)
{
*(block + 480) = (i64)lba;
}
/* same lookup, in an explicitly-named directory rather than always
* the cwd -- kfs_dir_find (below) is the cwd-only case every existing
* caller (cd, ls, mkdir, rm, ...) still uses, kept as its own function
* so none of them need to know this more general form exists. sys_exec
* uses this one directly to fall back to kfs_bin_dir_lba when a name
* isn't found in the cwd, without disturbing kfs_cwd_dir_lba at all. */
global i32
kfs_dir_find_in(u64 dir_lba, ptr name, u64 name_len)
{
i8 block[512];
u64 i;
u64 off;
u64 inode_num;
u64 lba;
u64 next;
lba = dir_lba;
while(1)
{
kfs_read_block(lba, &block[0]);
i = 0;
while(i < (u64)15)
{
off = i * (u64)32;
inode_num = (u64)block[off];
if(inode_num != ~(u64)0)
{
if(kfs_name_matches(name, name_len, &block[0], off) == 1)
{
return (i32)inode_num;
}
}
i = i + 1;
}
next = kfs_dir_next_block(&block[0]);
if(next == ~(u64)0)
{
return -1;
}
lba = next;
}
return -1;
}
global i32
kfs_dir_find(ptr name, u64 name_len)
{
return kfs_dir_find_in(kfs_cwd_dir_lba, name, name_len);
}
/* fills names_out (caller-owned, room for max*24 bytes) with up to
* max occupied entries' names, each a 24-byte null-padded slot -- for
* ls. walks the FULL block chain (see the note above kfs_dir_next_
* block), not just one block, stopping early once max entries have
* been written. names_out is a ptr parameter, not a real array, so
* filling it is the same packed-word read-modify-write technique as
* every other byte-at-a-time write through a bare ptr in this kernel;
* 24 is already a multiple of 8, so no partial-word tail to worry
* about between one entry's name and the next. */
global i32
kfs_dir_list_in(u64 dir_lba, ptr names_out, i32 max)
{
i8 block[512];
i32 count;
u64 i;
u64 off;
u64 inode_num;
u64 j;
u64 word;
u64 wordoff;
u64 byteoff;
u8 ch;
ptr dst;
u64 lba;
u64 next;
count = 0;
lba = dir_lba;
while(1)
{
kfs_read_block(lba, &block[0]);
i = 0;
while(i < (u64)15)
{
off = i * (u64)32;
inode_num = (u64)block[off];
if(inode_num != ~(u64)0)
{
if(count < max)
{
j = 0;
while(j < (u64)24)
{
ch = (u8)block[off + (u64)8 + j];
wordoff = j & ~(u64)7;
byteoff = j & (u64)7;
dst = names_out + (u64)count * (u64)24 + wordoff;
word = (u64)*dst;
word = word & ~((u64)0xff << (byteoff * (u64)8));
word = word | ((u64)ch << (byteoff * (u64)8));
*dst = (i64)word;
j = j + (u64)1;
}
count = count + 1;
}
}
i = i + (u64)1;
}
if(count >= max)
{
return count;
}
next = kfs_dir_next_block(&block[0]);
if(next == ~(u64)0)
{
return count;
}
lba = next;
}
return count;
}
global i32
kfs_dir_list(ptr names_out, i32 max)
{
kaboom_errno = 0;
if(kfs_check_perm(kfs_cwd_inode, (u64)1) == 0)
{
return -1; /* no read permission on cwd -- can't list it */
}
return kfs_dir_list_in(kfs_cwd_dir_lba, names_out, max);
}
/* builds "<prefix>/<name>\0" into out (capacity out_cap), returning
* the resulting length (not counting the null) or -1 if it wouldn't
* fit. a small, generic path-join, not specific to /bin at all --
* pulled out so sys_exec's $PATH fallback (exec.nsc) can turn a bare
* name found only via kfs_bin_dir_lba into a real, independently-
* resolvable path by asking for kfs_bin_dir_name/"/bin" once, instead
* of hand-spelling the same 5 ascii bytes out itself. anything else
* that ever needs "dir + name" joined into one path (a future search
* path with more than one entry, say) can reuse this instead of
* growing its own copy. */
global i32
kfs_join_path(ptr out, u64 out_cap, ptr prefix, u64 prefix_len, ptr name, u64 name_len)
{
u64 total;
u64 i;
total = prefix_len + (u64)1 + name_len;
if(total + (u64)1 > out_cap)
{
return -1;
}
i = 0;
while(i < prefix_len)
{
ptr_byte_set(out, i, ptr_byte_at(prefix, i));
i = i + (u64)1;
}
ptr_byte_set(out, prefix_len, (u8)47); /* '/' */
i = 0;
while(i < name_len)
{
ptr_byte_set(out, prefix_len + (u64)1 + i, ptr_byte_at(name, i));
i = i + (u64)1;
}
ptr_byte_set(out, total, (u8)0);
return (i32)total;
}
/* walks a real path -- "name" (relative to cwd, kfs_dir_find's own
* always-supported shape), "a/b/c" (relative, multi-component), or
* "/a/b/c" (absolute, starts at root) -- one directory at a time via
* kfs_dir_find_in, returning the final component's inode number or
* -1. every intermediate component must already exist and be a
* directory; the final component can be anything (a file is exactly
* what cat/open want to find at the end of a path). a bare name with
* no '/' at all resolves against cwd exactly like kfs_dir_find always
* did -- this fully replaces it for anything that might receive a
* real path, not just a bare name.
*
* added because "cat /doc/INTRO.doc" and "ls doc" (a bare relative
* name naming a subdirectory, not a file) had no way to work at all
* before this: kfs_dir_find/kfs_dir_find_in only ever look inside ONE
* given directory, never walk into a subdirectory themselves. */
global i32
kfs_resolve(ptr path, u64 path_len)
{
u64 dir_lba;
u64 i;
u64 seg_start;
i32 inode;
i8 inode_buf[512];
i64 type;
kaboom_errno = 0;
if(path_len == (u64)0)
{
return -1;
}
dir_lba = kfs_cwd_dir_lba;
i = 0;
if(ptr_byte_at(path, (u64)0) == (u8)47)
{
dir_lba = kfs_root_dir_lba;
i = 1;
if(path_len == (u64)1)
{
return (i32)kfs_root_inode; /* path was exactly "/" */
}
}
inode = -1;
seg_start = i;
while(i <= path_len)
{
if(i == path_len || ptr_byte_at(path, i) == (u8)47)
{
if(i > seg_start)
{
inode = kfs_dir_find_in(dir_lba, path + seg_start, i - seg_start);
if(inode < 0)
{
return -1;
}
if(i < path_len)
{
/* more components follow -- this one has to be a
* directory to descend into, and needs x (real
* unix's own "traverse" bit) to be resolved
* through at all. */
kfs_read_inode((u64)inode, &inode_buf[0]);
type = *(&inode_buf[0]);
if(type != (i64)2)
{
return -1;
}
if(kfs_check_perm(inode, (u64)4) == 0)
{
return -1;
}
dir_lba = (u64)*(&inode_buf[0] + 24);
}
}
seg_start = i + (u64)1;
}
i = i + (u64)1;
}
return inode;
}
/* splits path into its PARENT directory's lba+inode and the byte
* offset where the final path component starts within path -- for
* mkdir/create/rm/rmdir/save, which all need to operate a dirent
* into/out of the parent named by everything before the last '/',
* not the final component's own (possibly not-yet-existing, for
* create/mkdir) inode. "foo" (no slash) resolves its parent to cwd,
* offset 0 -- the exact bare-name case every caller already handled,
* unaffected by this existing at all. every intermediate component
* must exist, be a directory, and have x permission (needed to
* traverse through it at all), same as kfs_resolve. writes through
* parent_lba_out/parent_inode_out/base_off_out (real 8-byte word
* stores -- the caller passes the address of its own u64/i32 locals,
* not a bare-ptr byte buffer, so no packed-word technique is needed
* here). returns 1 on success, 0 if any intermediate component fails
* to resolve.
*
* parent_inode_out (added alongside real permission enforcement) is
* what lets a caller check the parent DIRECTORY's own write bit
* before adding/removing an entry within it -- parent_lba_out alone
* (the directory's DATA block) has no way back to its own inode
* number, which is what kfs_check_perm actually needs.
*
* added for "rm /doc/x" and friends: without this, a path argument
* to rm/rmdir/mkdir/chmod/ed's save was compared as one literal
* (and always-failing, since it contains '/') name against cwd's own
* dirents instead of actually looking inside /doc for x. */
global i32
kfs_resolve_parent(ptr path, u64 path_len, ptr parent_lba_out, ptr parent_inode_out, ptr base_off_out)
{
u64 dir_lba;
i32 dir_inode;
u64 i;
u64 seg_start;
i32 inode;
i8 inode_buf[512];
i64 type;
kaboom_errno = 0;
if(path_len == (u64)0)
{
return 0;
}
dir_lba = kfs_cwd_dir_lba;
dir_inode = kfs_cwd_inode;
i = 0;
if(ptr_byte_at(path, (u64)0) == (u8)47)
{
dir_lba = kfs_root_dir_lba;
dir_inode = (i32)kfs_root_inode;
i = 1;
}
seg_start = i;
while(i < path_len)
{
if(ptr_byte_at(path, i) == (u8)47)
{
if(i > seg_start)
{
inode = kfs_dir_find_in(dir_lba, path + seg_start, i - seg_start);
if(inode < 0)
{
return 0;
}
kfs_read_inode((u64)inode, &inode_buf[0]);
type = *(&inode_buf[0]);
if(type != (i64)2)
{
return 0;
}
if(kfs_check_perm(inode, (u64)4) == 0)
{
return 0;
}
dir_lba = (u64)*(&inode_buf[0] + 24);
dir_inode = inode;
}
seg_start = i + (u64)1;
}
i = i + (u64)1;
}
*parent_lba_out = (i64)dir_lba;
*parent_inode_out = (i64)dir_inode;
*base_off_out = (i64)seg_start;
return 1;
}
/* resolves path and returns its inode's type (1=file, 2=dir), or -1
* if it doesn't exist -- for ls to decide whether an argument names
* something to list into or just print by itself. */
global i64
kfs_stat(ptr path, u64 path_len)
{
i32 n;
i8 inode[512];
n = kfs_resolve(path, path_len);
if(n < 0)
{
return -1;
}
kfs_read_inode((u64)n, &inode[0]);
return *(&inode[0]);
}
/* kfs_dir_list_in, but given a path instead of an already-known lba
* -- resolves path, confirms it's a directory, then lists it. -1 if
* path doesn't resolve or isn't a directory. */
global i32
kfs_dir_list_path(ptr path, u64 path_len, ptr names_out, i32 max)
{
i32 n;
i8 inode[512];
i64 type;
u64 dir_lba;
n = kfs_resolve(path, path_len);
if(n < 0)
{
return -1;
}
kfs_read_inode((u64)n, &inode[0]);
type = *(&inode[0]);
if(type != (i64)2)
{
return -1;
}
if(kfs_check_perm(n, (u64)1) == 0)
{
return -1; /* no read permission -- can't list it */
}
dir_lba = (u64)*(&inode[0] + 24);
return kfs_dir_list_in(dir_lba, names_out, max);
}
/* true if inode_num's own stored permission includes bit (r=1 w=2
* x=4) -- the one real check every enforcement point below shares.
* no user/group/other split to check against (see this file's own
* top comment on the permission scheme): there's exactly one user,
* so the stored bitmask is the whole answer, unconditionally.
*
* this is also the ONE place that ever sets kaboom_errno = 1 (EPERM)
* -- every public entry point below resets it to 0 at its own start
* (see e.g. kfs_resolve), so by the time any of them returns failure,
* kaboom_errno correctly says whether THIS call's failure was a
* permission problem specifically, or something else (not found, a
* directory that isn't empty, ...) that just leaves it at 0. idt.nsc's
* sys_doerror reads it to decide what to actually write to the kernel
* log -- centralizing the enforcement/logging split here, instead of
* every caller separately guessing why something failed. */
global i32
kfs_check_perm(i32 inode_num, u64 bit)
{
i8 inode_buf[512];
u64 perm;
kfs_read_inode((u64)inode_num, &inode_buf[0]);
perm = (u64)*(&inode_buf[0] + 8);
if((perm & bit) != (u64)0)
{
return 1;
}
kaboom_errno = 1;
return 0;
}
/* changes name's permission bits (r=1 w=2 x=4) -- name can be a bare
* name or a real path, via kfs_resolve -- for chmod. returns 1 on
* success, 0 if name doesn't exist. unconditional, no permission
* check of its own: there's no owner/root concept to gate chmod
* behind (see kfs_check_perm's own note) -- the one user here can
* always chmod anything. */
global i32
kfs_chmod(ptr name, u64 name_len, u64 perm)
{
i8 inode[512];
i32 n;
n = kfs_resolve(name, name_len);
if(n < 0)
{
return 0;
}
kfs_read_inode((u64)n, &inode[0]);
*(&inode[0] + 8) = (i64)perm;
kfs_write_inode((u64)n, &inode[0]);
return 1;
}
/* reads back name's permission bits (r=1 w=2 x=4, the same bitmask
* chmod writes) -- for a userspace `perms` command to actually show
* what chmod set, since nothing before this ever needed to read a
* perm bit back out, only check one (kfs_check_perm) or overwrite one
* (kfs_chmod). returns -1 if name doesn't resolve, matching kfs_stat's
* own -1-on-not-found convention; unconditional otherwise, same "no
* owner/root concept" reasoning as kfs_chmod -- reading a perm bit
* back needs no permission of its own either. */
global i32
kfs_getperm(ptr name, u64 name_len)
{
i8 inode[512];
i32 n;
n = kfs_resolve(name, name_len);
if(n < 0)
{
return -1;
}
kfs_read_inode((u64)n, &inode[0]);
return (i32)*(&inode[0] + 8);
}
/* adds name -> inode_num to dir_lba's entry list, walking the full
* block chain (see the note above kfs_dir_next_block) for a free
* slot before bump-allocating and linking a fresh block onto the end
* of the chain -- a directory only ever grows by one block at a
* time, exactly when its current last block is genuinely full,
* mirroring the same "allocate lazily, only when actually needed"
* shape kfs_write_file's indirect block already uses. returns 1 on
* success, 0 if name is empty or longer than the 23 bytes a dirent's
* name field holds (callers reject both before getting here -- see
* kfs_create -- this is the last line of defense, not the check), or
* if the chain needs a new block and none is left below
* kfs_total_blocks. nothing is written in either failure case.
* kfs_dir_add (below) is the cwd-only case every existing caller used
* before path resolution existed; generalized the same way
* kfs_dir_find/kfs_dir_list already were, so kfs_create/kfs_mkdir/
* kfs_save can add a dirent into a resolved PARENT directory instead
* of always cwd (see kfs_resolve_parent) -- "rm /doc/x" needs to
* remove x's dirent from /doc, not from whatever the caller's cwd
* happens to be. */
i32
kfs_dir_add_in(u64 dir_lba, ptr name, u64 name_len, u64 inode_num)
{
i8 block[512];
u64 i;
u64 off;
u64 slot;
u64 stored;
u8 ch;
u64 lba;
u64 next;
u64 new_lba;
/* a dirent's name field is 24 bytes including the null, so 23 is
* the most it can hold. this used to truncate a longer name and
* then write the null at the untruncated length, past the end of
* the name field: into the next dirent, into the chain's own
* next-block word at offset 480, or off the end of block[]. */
if(name_len == (u64)0 || name_len > (u64)23)
{
return 0;
}
lba = dir_lba;
while(1)
{
kfs_read_block(lba, &block[0]);
slot = ~(u64)0;
i = 0;
while(i < (u64)15)
{
off = i * (u64)32;
stored = (u64)block[off];
if(stored == ~(u64)0)
{
slot = off;
i = (u64)15;
}
i = i + 1;
}
if(slot != ~(u64)0)
{
block[slot] = (i8)inode_num;
i = (u64)1;
while(i < (u64)8)
{
block[slot + i] = 0;
i = i + 1;
}
i = 0;
while(i < name_len)
{
ch = ptr_byte_at(name, i);
block[slot + (u64)8 + i] = (i8)ch;
i = i + 1;
}
block[slot + (u64)8 + name_len] = 0;
kfs_write_block(lba, &block[0]);
return 1;
}
next = kfs_dir_next_block(&block[0]);
if(next != ~(u64)0)
{
lba = next;
}
else
{
/* this block (the last in the chain) is genuinely full --
* allocate a new one, link it on, and retry there. same
* bounds check as kfs_write_file: a block past the image's
* real end would be linked in, its write would silently go
* nowhere, and the next walk would re-read stale buffer
* content whose next-block word points right back at it --
* an endless loop in every chain walker. refuse before
* touching anything instead. */
if(kfs_next_free_block + (u64)1 > kfs_total_blocks)
{
return 0;
}
new_lba = kfs_next_free_block;
kfs_next_free_block = kfs_next_free_block + (u64)1;
kfs_dir_set_next_block(&block[0], new_lba);
kfs_write_block(lba, &block[0]);
i = 0;
while(i < (u64)512)
{
block[i] = 0;
i = i + 1;
}
i = 0;
while(i < (u64)16)
{
*(&block[0] + i * (u64)32) = (i64)(~(u64)0);
i = i + (u64)1;
}
kfs_write_block(new_lba, &block[0]);
lba = new_lba;
}
}
return 0;
}
i32
kfs_dir_add(ptr name, u64 name_len, u64 inode_num)
{
return kfs_dir_add_in(kfs_cwd_dir_lba, name, name_len, inode_num);
}
i32
kfs_find_free_inode(void)
{
i8 inode[512];
i64 type;
u64 n;
n = kfs_next_free_inode;
while(n < kfs_inode_count)
{
kfs_read_inode(n, &inode[0]);
type = *(&inode[0]);
if(type == (i64)0)
{
return (i32)n;
}
n = n + (u64)1;
}
return -1;
}
/* creates a new, empty file with the given name (a bare name, or a
* real path -- "doc/x"/"/doc/x" create x inside doc, via
* kfs_resolve_parent) and rwx permission bitmask (r=1 w=2 x=4).
* returns the new inode number, or -1 if the name already exists, no
* inodes are free, the directory is full, or an intermediate path
* component doesn't resolve. */
global i32
kfs_create(ptr name, u64 name_len, u64 perm)
{
i8 inode[512];
i32 n;
u64 i;
ptr p;
u64 parent_lba;
i32 parent_inode;
u64 base_off;
ptr base_name;
u64 base_len;
if(kfs_resolve_parent(name, name_len, &parent_lba, &parent_inode, &base_off) == 0)
{
return -1;
}
if(kfs_check_perm(parent_inode, (u64)2) == 0)
{
return -1; /* no write permission on the parent directory */
}
if(kfs_is_virt_dir(parent_lba) == 1)
{
return -1; /* /proc or /int -- see kfs_is_virt_dir */
}
base_name = name + base_off;
base_len = name_len - base_off;
/* a dirent holds at most 23 name bytes (see kfs_dir_add_in), and
* an empty base name ("x/", or "/" itself) would make a nameless
* dirent. refuse both before touching anything: a long name used
* to reach kfs_dir_add_in and corrupt the directory block, and
* since kfs_name_matches never finds a name over 23 bytes, every
* retry added another corrupt entry. */
if(base_len == (u64)0 || base_len > (u64)23)
{
return -1;
}
if(kfs_dir_find_in(parent_lba, base_name, base_len) >= 0)
{
return -1; /* already exists */
}
n = kfs_find_free_inode();
if(n < 0)
{
return -1;
}
i = 0;
while(i < (u64)512)
{
inode[i] = 0;
i = i + 1;
}
p = &inode[0];
*p = (i64)1; /* KFS_TYPE_FILE */
*(p + 8) = (i64)perm;
*(p + 16) = (i64)0; /* size */
kfs_write_inode((u64)n, &inode[0]);
if(kfs_dir_add_in(parent_lba, base_name, base_len, (u64)n) == 0)
{
/* no room for the dirent (disk full) -- free the inode again
* rather than leave it typed but unreachable. */
*p = (i64)0;
*(p + 8) = (i64)0;
kfs_write_inode((u64)n, &inode[0]);
return -1;
}
kfs_next_free_inode = (u64)n + (u64)1;
return n;
}
/* finds name -- a bare name or a real path, via kfs_resolve/
* kfs_create's own kfs_resolve_parent -- creating it (rw perm) if it
* doesn't exist yet, and overwrites its entire content with data/len
* -- the "write a whole file" a real program (ed) needs, which
* nothing before it did (cat/ls/echo/klogs are all read-only). kept
* as one call rather than open+write+close: kfs's whole-file-cached
* fd layer (fd.nsc) has no write-back path yet, and this doesn't
* need one either -- a save is "replace the whole file", not a
* partial/seeked write. returns 1 on success, 0 on failure (no free
* inode, directory full, an intermediate path component doesn't
* resolve, the data's too big -- see kfs_write_file -- or name
* already exists as something other than a plain file).
*
* that last check matters: kfs_write_file overwrites whatever inode
* it's given, directory or not, so saving onto an existing directory
* used to replace the directory's dirent blocks with the file's bytes
* -- every entry in it gone, the leftover bytes parsed as garbage
* dirents. `mv file dir`/`cp file dir` (the natural unix "into this
* directory" typo) did exactly that, and `cp x /` would have done it
* to root. refused cleanly now, the same way a missing write
* permission is.
*
* a failed write must also leave nothing behind when name didn't exist
* before: kfs_create makes the inode and dirent first, so when
* kfs_write_file then refuses (disk full, or too big) the fresh entry
* is removed again with kfs_rm, leaving the directory exactly as it
* was. before this, a disk-full `mv a b` left an empty b behind, and
* the natural next command, `mv b a`, read that 0-byte b and
* overwrote the real a with it. an EXISTING file needs no undo:
* kfs_write_file refuses before touching the inode or allocating
* anything, so its old content is still there. */
global i32
kfs_save(ptr name, u64 name_len, ptr data, u64 len)
{
i32 n;
i32 created;
i8 inode[512];
created = 0;
n = kfs_resolve(name, name_len);
if(n < 0)
{
/* rw (3, r=1 w=2), matching real unix touch/save semantics --
* a plain file isn't executable by default there either. a
* script written with ed and run directly (see exec.nsc's own
* shebang handling) needs an explicit chmod +x before it will
* run, same as a real shell -- this WAS "7" (rwx) specifically
* to avoid that step, but that made every plain data file
* default to executable too, which is the wrong direction to
* default in. explicit chmod is the correct place for this,
* not a save-time default. */
n = kfs_create(name, name_len, (u64)3);
if(n < 0)
{
return 0;
}
created = 1;
}
else
{
kfs_read_inode((u64)n, &inode[0]);
if(*(&inode[0]) != (i64)1)
{
return 0; /* exists, but isn't a plain file (KFS_TYPE_FILE) */
}
if(kfs_check_perm(n, (u64)2) == 0)
{
return 0; /* exists, but no write permission */
}
}
if(kfs_write_file(n, data, len) == 1)
{
return 1;
}
if(created == 1)
{
kfs_rm(name, name_len); /* undo the create -- see above */
}
return 0;
}
/* writes data (len bytes, <= 8450048) as the entire contents of inode n,
* overwriting whatever was there. returns 1 on success, 0 if len is too
* big or the blocks it needs won't fit below kfs_total_blocks.
*
* three tiers, exactly as kfs_block_tier computes them: 56 direct block
* pointers (offsets 24..471), 1 single-indirect pointer (offset 472,
* unchanged shape from before double indirection existed: one 512-byte
* block of 64 more direct pointers), and 4 double-indirect pointers
* (offsets 480/488/496/504 -- each -> a first-level block of 64
* pointers -> each of those -> a second-level block of 64 more direct
* pointers). every pointer block is allocated lazily, only once a file
* actually reaches the tier that needs it, so a small file's on-disk
* footprint is exactly what it always was: its data blocks and nothing
* else.
*
* buffers are flushed lazily, in step with b's own monotonic increase:
* at most one single-indirect buffer, one "current" first-level
* double-indirect buffer, and one "current" second-level buffer are ever
* live in memory at once, each written to disk (and its own lba recorded
* in its parent) the moment b moves past the last block it can hold --
* never all up-to-256 possible second-level blocks at once, which would
* be 128kib of buffers on a single shared 64kib stack. */
global i32
kfs_write_file(i32 n, ptr data, u64 len)
{
i8 inode[512];
i8 block[512];
i8 sind[512];
i8 l1[512];
i8 l2[512];
i32 have_sind;
i32 have_l1;
i32 have_l2;
u64 sind_lba;
u64 l1_lba;
u64 l2_lba;
u64 cur_dp;
u64 cur_l1;
u64 nblocks;
u64 b;
u64 remaining;
u64 chunk;
u64 i;
u64 lba;
i32 tier;
u64 dp;
u64 slot;
u64 l2idx;
u64 need;
ptr p;
if(len > (u64)8450048)
{
return 0;
}
nblocks = (len + (u64)511) / (u64)512;
if(nblocks == (u64)0)
{
nblocks = (u64)1; /* even an empty file owns one block */
}
/* refuse up front, before touching the inode or allocating a single
* block, if this write can't fit on the real disk: every block it's
* about to allocate -- the data blocks, plus the pointer blocks the
* tiers above lazily allocate (1 single-indirect block past 56 data
* blocks; past 120, one l1 block per started 4096 and one l2 block
* per started 64 of the blocks beyond 120) -- has to land below
* kfs_total_blocks (the disk's real physical size, see mk/disk.pl).
* without this, a write past the image's real end "succeeded" with
* its data silently never landing anywhere. same clean return-0 as
* the len check above, and kfs_next_free_block is left untouched. */
need = nblocks;
if(nblocks > (u64)56)
{
need = need + (u64)1;
}
if(nblocks > (u64)120)
{
need = need + (nblocks - (u64)120 + (u64)4095) / (u64)4096;
need = need + (nblocks - (u64)120 + (u64)63) / (u64)64;
}
if(kfs_next_free_block > kfs_total_blocks || need > kfs_total_blocks - kfs_next_free_block)
{
return 0;
}
kfs_read_inode((u64)n, &inode[0]);
p = &inode[0];
have_sind = 0;
have_l1 = 0;
have_l2 = 0;
cur_dp = ~(u64)0;
cur_l1 = ~(u64)0;
b = 0;
remaining = len;
while(b < nblocks)
{
lba = kfs_next_free_block;
kfs_next_free_block = kfs_next_free_block + (u64)1;
tier = kfs_block_tier(b, &dp, &slot, &l2idx);
if(tier == 0)
{
*(p + (u64)24 + slot * (u64)8) = (i64)lba;
}
else if(tier == 1)
{
if(have_sind == 0)
{
sind_lba = kfs_next_free_block;
kfs_next_free_block = kfs_next_free_block + (u64)1;
i = 0;
while(i < (u64)512)
{
sind[i] = 0;
i = i + 1;
}
have_sind = 1;
}
*(&sind[0] + slot * (u64)8) = (i64)lba;
}
else
{
/* b only ever increases, so once dp or slot (l1 index) within
* the same dp changes, whatever buffer we're moving away from
* is permanently done and must be flushed before its buffer
* is reused -- l2 first (more nested, and its own lba has to
* land in the l1 it belongs to BEFORE that l1 is flushed),
* then l1 if the double-indirect pointer itself changed too. */
if(have_l2 == 1)
{
if(cur_dp != dp || cur_l1 != slot)
{
kfs_write_block(l2_lba, &l2[0]);
*(&l1[0] + cur_l1 * (u64)8) = (i64)l2_lba;
have_l2 = 0;
}
}
if(have_l1 == 1)
{
if(cur_dp != dp)
{
kfs_write_block(l1_lba, &l1[0]);
*(p + (u64)480 + cur_dp * (u64)8) = (i64)l1_lba;
have_l1 = 0;
}
}
if(have_l1 == 0)
{
cur_dp = dp;
l1_lba = kfs_next_free_block;
kfs_next_free_block = kfs_next_free_block + (u64)1;
i = 0;
while(i < (u64)512)
{
l1[i] = 0;
i = i + 1;
}
have_l1 = 1;
}
if(have_l2 == 0)
{
cur_l1 = slot;
l2_lba = kfs_next_free_block;
kfs_next_free_block = kfs_next_free_block + (u64)1;
i = 0;
while(i < (u64)512)
{
l2[i] = 0;
i = i + 1;
}
have_l2 = 1;
}
*(&l2[0] + l2idx * (u64)8) = (i64)lba;
}
i = 0;
while(i < (u64)512)
{
block[i] = 0;
i = i + 1;
}
chunk = remaining;
if(chunk > (u64)512)
{
chunk = (u64)512;
}
i = 0;
while(i < chunk)
{
block[i] = (i8)ptr_byte_at(data, b * (u64)512 + i);
i = i + 1;
}
kfs_write_block(lba, &block[0]);
remaining = remaining - chunk;
b = b + (u64)1;
}
/* flush whatever pointer blocks are still live -- l2 before l1, for
* the same parent-records-child's-lba-first reason as above. */
if(have_sind == 1)
{
*(p + (u64)472) = (i64)sind_lba;
kfs_write_block(sind_lba, &sind[0]);
}
if(have_l2 == 1)
{
kfs_write_block(l2_lba, &l2[0]);
*(&l1[0] + cur_l1 * (u64)8) = (i64)l2_lba;
}
if(have_l1 == 1)
{
kfs_write_block(l1_lba, &l1[0]);
*(p + (u64)480 + cur_dp * (u64)8) = (i64)l1_lba;
}
*(p + 16) = (i64)len;
kfs_write_inode((u64)n, &inode[0]);
return 1;
}
/* reads inode n's full contents into buf. buf must have room for
* kfs_file_size(n) rounded UP to the next multiple of 8: *ptr is
* always a full 8-byte store (no single-byte write through a raw ptr
* exists in this language), so the tail end of a file whose size
* isn't a multiple of 8 writes up to 7 bytes of harmless padding past
* the logical end -- real bytes read from the same on-disk block
* (never uninitialized memory), just not meaningful file content.
* returns the number of logically meaningful bytes (kfs_file_size).
*
* mirrors kfs_write_file's own lazy single-indirect/l1/l2 buffer
* handling, but read-only: nothing is allocated here, only whatever's
* already on disk is walked, via the same kfs_block_tier every other
* consumer uses. */
global u64
kfs_read_file(i32 n, ptr buf)
{
i8 inode[512];
i8 block[512];
i8 sind[512];
i8 l1[512];
i8 l2[512];
i32 have_sind;
i32 have_l1;
i32 have_l2;
u64 cur_dp;
u64 cur_l1;
u64 size;
u64 nblocks;
u64 b;
u64 remaining;
u64 chunk;
u64 i;
u64 lba;
i32 tier;
u64 dp;
u64 slot;
u64 l2idx;
ptr p;
ptr dst;
kfs_read_inode((u64)n, &inode[0]);
p = &inode[0];
size = (u64)*(p + 16);
nblocks = (size + (u64)511) / (u64)512;
dst = buf;
have_sind = 0;
have_l1 = 0;
have_l2 = 0;
cur_dp = ~(u64)0;
cur_l1 = ~(u64)0;
b = 0;
remaining = size;
while(b < nblocks)
{
tier = kfs_block_tier(b, &dp, &slot, &l2idx);
if(tier == 0)
{
lba = (u64)*(p + (u64)24 + slot * (u64)8);
}
else if(tier == 1)
{
if(have_sind == 0)
{
kfs_read_block((u64)*(p + (u64)472), &sind[0]);
have_sind = 1;
}
lba = (u64)*(&sind[0] + slot * (u64)8);
}
else
{
if(have_l1 == 0 || cur_dp != dp)
{
kfs_read_block((u64)*(p + (u64)480 + dp * (u64)8), &l1[0]);
cur_dp = dp;
have_l1 = 1;
have_l2 = 0; /* old l2 belonged to the previous l1 -- force
* a reload below, don't reuse it. */
}
if(have_l2 == 0 || cur_l1 != slot)
{
kfs_read_block((u64)*(&l1[0] + slot * (u64)8), &l2[0]);
cur_l1 = slot;
have_l2 = 1;
}
lba = (u64)*(&l2[0] + l2idx * (u64)8);
}
kfs_read_block(lba, &block[0]);
chunk = remaining;
if(chunk > (u64)512)
{
chunk = (u64)512;
}
/* build 8-byte groups from the block array (byte-indexable,
* being a real array) and store each as one full word through
* dst (a bare ptr -- no byte-granular store exists). chunk is
* only ever < 512 on the last block of a file (every earlier
* block reads the full 512), so the only place this can write
* a few bytes past the logical chunk boundary is the very
* last write of the whole function, with no subsequent write
* to collide with. */
i = 0;
while(i < chunk)
{
u64 word;
u64 k;
word = 0;
k = 0;
while(k < (u64)8)
{
word = word | ((u64)(u8)block[i + k] << (k * (u64)8));
k = k + (u64)1;
}
*(dst + i) = (i64)word;
i = i + (u64)8;
}
dst = dst + chunk;
remaining = remaining - chunk;
b = b + (u64)1;
}
return size;
}
global u64
kfs_file_size(i32 n)
{
i8 inode[512];
kfs_read_inode((u64)n, &inode[0]);
return (u64)*(&inode[0] + 16);
}
/* inode n's type (KFS_TYPE_FILE = 1, KFS_TYPE_DIR = 2) -- kfs_stat's
* answer for an inode number already in hand instead of a path, same
* shape as kfs_file_size. fd_open (fd.nsc) uses it to refuse opening
* anything that isn't a plain file. */
global i64
kfs_inode_type(i32 n)
{
i8 inode[512];
kfs_read_inode((u64)n, &inode[0]);
return *(&inode[0]);
}
/* true if dir_lba is /proc's or /int's own data block -- the same
* "is this name's PARENT a virtual directory" recognition virtfs_read
* (virtfs.nsc) uses, including its guard against an old disk image
* where kfs_mount fell both back to root. every entry in a virtual
* directory is a placeholder virtfs depends on finding on disk, so
* kfs_rm/kfs_rmdir refuse to remove one and kfs_create/kfs_mkdir
* refuse to add one: `rm /proc/ps` used to delete the placeholder
* for good (surviving reboot, ps then saying "/proc/ps not found"),
* and a stray file created in there could never be removed again. */
i32
kfs_is_virt_dir(u64 dir_lba)
{
if(dir_lba == kfs_proc_dir_lba && kfs_proc_dir_lba != kfs_root_dir_lba)
{
return 1;
}
if(dir_lba == kfs_int_dir_lba && kfs_int_dir_lba != kfs_root_dir_lba)
{
return 1;
}
return 0;
}
/* creates a new, empty directory with the given name (a bare name or
* a real path, via kfs_resolve_parent -- same as kfs_create) and rwx
* permission bitmask. same shape as kfs_create, plus allocating and
* initializing the new directory's own (empty) data block -- a
* directory's "data" is just its own dirent list, same 16-slot
* single-block format as the root directory has always used. returns
* the new inode number, or -1 if the name already exists, no
* inodes/blocks are free, the parent directory is full, or an
* intermediate path component doesn't resolve. */
global i32
kfs_mkdir(ptr name, u64 name_len, u64 perm)
{
i8 inode[512];
i8 zero[512];
i32 n;
u64 lba;
u64 i;
ptr p;
u64 parent_lba;
i32 parent_inode;
u64 base_off;
ptr base_name;
u64 base_len;
if(kfs_resolve_parent(name, name_len, &parent_lba, &parent_inode, &base_off) == 0)
{
return -1;
}
if(kfs_check_perm(parent_inode, (u64)2) == 0)
{
return -1; /* no write permission on the parent directory */
}
if(kfs_is_virt_dir(parent_lba) == 1)
{
return -1; /* /proc or /int -- see kfs_is_virt_dir */
}
base_name = name + base_off;
base_len = name_len - base_off;
/* same empty/over-23-byte name refusal as kfs_create, same reason. */
if(base_len == (u64)0 || base_len > (u64)23)
{
return -1;
}
if(kfs_dir_find_in(parent_lba, base_name, base_len) >= 0)
{
return -1;
}
n = kfs_find_free_inode();
if(n < 0)
{
return -1;
}
/* the new directory's own data block has to land below
* kfs_total_blocks, same check as kfs_write_file -- otherwise its
* write goes nowhere and the directory reads back as stale garbage. */
if(kfs_next_free_block + (u64)1 > kfs_total_blocks)
{
return -1;
}
lba = kfs_next_free_block;
kfs_next_free_block = kfs_next_free_block + (u64)1;
i = 0;
while(i < (u64)512)
{
zero[i] = 0;
i = i + 1;
}
i = 0;
while(i < (u64)16)
{
p = &zero[0] + i * (u64)32;
*p = (i64)(~(u64)0);
i = i + (u64)1;
}
kfs_write_block(lba, &zero[0]);
i = 0;
while(i < (u64)512)
{
inode[i] = 0;
i = i + 1;
}
p = &inode[0];
*p = (i64)2; /* KFS_TYPE_DIR */
*(p + 8) = (i64)perm;
*(p + 16) = (i64)0;
*(p + 24) = (i64)lba;
kfs_write_inode((u64)n, &inode[0]);
if(kfs_dir_add_in(parent_lba, base_name, base_len, (u64)n) == 0)
{
/* the parent had no room for the dirent (disk full) -- free
* the inode again, and hand back the data block too: a failed
* kfs_dir_add_in allocates nothing, so lba is still the last
* block handed out. */
*p = (i64)0;
*(p + 8) = (i64)0;
*(p + 24) = (i64)0;
kfs_write_inode((u64)n, &inode[0]);
kfs_next_free_block = lba;
return -1;
}
kfs_next_free_inode = (u64)n + (u64)1;
return n;
}
/* changes the current directory. only two shapes are supported: "/"
* (back to root) and a bare name naming a direct child of the
* current directory -- no multi-component paths ("a/b"), no ".."
* (would need a parent pointer, which no inode stores -- a real,
* known follow-up). returns 1 on success, 0 if name isn't found or
* isn't a directory. */
global i32
kfs_cd(ptr name, u64 name_len)
{
i8 inode_buf[512];
i32 n;
i64 type;
u64 lba;
u64 eff_len;
u64 i;
u64 j;
u8 ch;
if(name_len == (u64)1 && ptr_byte_at(name, (u64)0) == (u8)47)
{
kaboom_errno = 0;
if(kfs_check_perm(0, (u64)4) == 0)
{
return 0; /* no x permission on root -- can't traverse into it */
}
kfs_cwd_dir_lba = kfs_root_dir_lba;
kfs_cwd_inode = 0;
kfs_cwd_path[0] = (i8)47;
kfs_cwd_path[1] = 0;
return 1;
}
/* kfs_resolve, not kfs_dir_find: kfs_dir_find only ever looks
* inside the cwd itself, so it can never make sense of a leading
* '/' (an absolute path) or a trailing '/' -- "cd /usr" was
* literally searching the cwd for an entry named "/usr" (slash
* included) and "cd /usr/" for one named "/usr/", neither of
* which any real dirent is ever named. kfs_resolve already walks
* a real absolute/relative/multi-component path one directory at
* a time (see its own comment) and already tolerates a trailing
* '/' correctly (an empty final path component is simply a no-op
* once the walk gets there). */
n = kfs_resolve(name, name_len);
if(n < 0)
{
return 0;
}
kfs_read_inode((u64)n, &inode_buf[0]);
type = *(&inode_buf[0]);
if(type != (i64)2)
{
return 0; /* not a directory */
}
if(kfs_check_perm(n, (u64)4) == 0)
{
return 0; /* no x permission -- can't traverse into it */
}
lba = (u64)*(&inode_buf[0] + 24);
kfs_cwd_dir_lba = lba;
kfs_cwd_inode = n;
/* canonicalize for kfs_cwd_path's own bookkeeping: drop a single
* trailing '/' (kfs_resolve above already tolerated one, but pwd
* shouldn't show one -- "cd /usr/" and "cd /usr" should both
* leave pwd saying "/usr"). the name_len==1 bare "/" case is
* handled separately above and never reaches here. */
eff_len = name_len;
if(eff_len > (u64)1 && ptr_byte_at(name, eff_len - (u64)1) == (u8)47)
{
eff_len = eff_len - (u64)1;
}
if(ptr_byte_at(name, (u64)0) == (u8)47)
{
/* absolute path: REPLACES the whole cwd path -- appending (the
* relative-path branch below) would be wrong here, "cd /usr"
* from cwd "/doc" must leave pwd saying "/usr", not
* "/doc/usr". */
i = 0;
while(i < eff_len && i < (u64)255)
{
ch = ptr_byte_at(name, i);
kfs_cwd_path[i] = (i8)ch;
i = i + (u64)1;
}
kfs_cwd_path[i] = 0;
}
else
{
/* relative -- a bare child name or a relative multi-component
* path ("a/b") both just append onto the existing cwd path,
* same as always: find the current length, then only insert a
* separator if cwd isn't the bare root ("/" itself already
* ends in the separator "/name" needs). */
i = 0;
while(kfs_cwd_path[i] != (i8)0)
{
i = i + (u64)1;
}
if(i > (u64)1)
{
kfs_cwd_path[i] = (i8)47; /* '/' */
i = i + (u64)1;
}
j = 0;
while(j < eff_len && i + j < (u64)255)
{
ch = ptr_byte_at(name, j);
kfs_cwd_path[i + j] = (i8)ch;
j = j + (u64)1;
}
kfs_cwd_path[i + j] = 0;
}
return 1;
}
/* copies the current directory's printable path into buf (a bare ptr,
* so byte-at-a-time is the usual packed-word read-modify-write).
* returns the path length. */
global u64
kfs_pwd(ptr buf)
{
u64 n;
u64 i;
u64 word;
u64 wordoff;
u64 byteoff;
ptr dst;
n = 0;
while(kfs_cwd_path[n] != (i8)0)
{
n = n + (u64)1;
}
dst = buf;
i = 0;
while(i < n)
{
wordoff = i & ~(u64)7;
byteoff = i & (u64)7;
word = (u64)*(dst + wordoff);
word = word & ~((u64)0xff << (byteoff * (u64)8));
word = word | ((u64)(u8)kfs_cwd_path[i] << (byteoff * (u64)8));
*(dst + wordoff) = (i64)word;
i = i + (u64)1;
}
return n;
}
/* clears the dirent slot matching name in dir_lba, walking the full
* block chain (see the note above kfs_dir_next_block). returns 1 if
* a matching entry was found and cleared, 0 otherwise. generalized
* the same way kfs_dir_add was, for the same path-resolution reason. */
i32
kfs_dir_remove_i