blob: 9952948403bbeb4212c84a82c6a7ad5627678c7a [file] [log] [blame]
#include <alloc.h>
#include <dri/ata_pio/ata_pio.h>
#include <dri/fs/ext2/ext2.h>
#include <io.h>
#include <kint.h>
#include <log.h>
#define F(f,t) [EXT2_S_##f >> 12] = EXT2_FT_##t,
const uchar ext2_s_to_ft[] =
{
0,
F(IFSOCK, SOCK)
F(IFLINK, SYMLINK)
F(IFREG, REGULAR_FILE)
F(IFBLK, BLKDEV)
F(IFDIR, DIR)
F(IFCHR, CHRDEV)
F(IFIFO, FIFO)
};
#undef F
void ext2_read_block(struct ext2_superblock *sb, void *buffer, uint block)
{
uint block_size = ext2_block_size(sb) / 512;
uint block_start = block_size * block;
ata_pio_read_sectors(buffer, block_start, block_size);
}
void ext2_write_block(struct ext2_superblock *sb, void *buffer, uint block)
{
uint block_size = ext2_block_size(sb) / 512;
uint block_start = block_size * block;
ata_pio_write_sectors(block_start, block_size, buffer);
}
struct ext2_superblock ext2_read_superblock()
{
uchar buffer[512 * 2];
ata_pio_read_sectors(buffer, 2, 2);
struct ext2_superblock *sb = (void *)(buffer);
return *sb;
}
uint ext2_num_block_groups(struct ext2_superblock *sb)
{
// This is a mildly janky way of rounding up
uint a = IDIV_CEIL(sb->total_blocks, sb->blocks_per_block_group);
uint b = IDIV_CEIL(sb->total_inodes, sb->inodes_per_block_group);
if (a == b)
{
return a;
}
else
{
kprintf(ERROR "EXT2 cannot find number of block groups, %d and %d "
"should equal.\n",
a, b);
kpanic("Corrupted filesystem");
}
}
void ext2_write_bgd(struct ext2_superblock *sb, uint block_group,
struct ext2_block_group_descriptor *d)
{
ext2_load_or_write_bgd(sb, block_group, d, true);
}
struct ext2_block_group_descriptor ext2_load_bgd(
struct ext2_superblock *sb, uint block_group)
{
struct ext2_block_group_descriptor bgd;
ext2_load_or_write_bgd(sb, block_group, &bgd, false);
return bgd;
}
void ext2_load_or_write_bgd(struct ext2_superblock *sb,
uint block_group,
struct ext2_block_group_descriptor *d,
bool set)
{
/**
* The BGDT (not to be confused with the GDT) is located the block after the
* superblock. On any block size EXCEPT 1024 (the minimum, remember that the
* block size is specified by X where 1024 << X is the real size) this is
* the second block (0-indexed, so 1). On 1024 this is the third block.
*/
uint bgdt_block = 1;
uint block_size = ext2_block_size(sb);
if (block_size == 1024)
bgdt_block = 2;
const uint bgd_size = sizeof(struct ext2_block_group_descriptor);
// Disk page that the BGD is on relative to the initial FILE SYSTEM block
uint hd_page = block_group / (512 / bgd_size);
// The offset from the beginning of that page the BGD is at
uint bgd_offset = block_group % (512 / bgd_size);
struct ext2_block_group_descriptor descriptors[512 / bgd_size];
kassert(sizeof(descriptors) == 512, "Wrong BGD size");
uint lba = (block_size / 512) * bgdt_block + hd_page;
ata_pio_read_sectors(descriptors, lba, 1);
if (set)
{
descriptors[bgd_offset] = *d;
ata_pio_write_sectors(lba, 1, (ushort *)descriptors);
}
else
{
*d = descriptors[bgd_offset];
}
}
static bool print_entry(uint inode, const char *name, uint l, void *sb)
{
kprintf("%d\t %s\n", inode, name);
return true;
struct ext2_inode in;
if (ext2_find_inode(sb, inode, &in))
{
if ((in.mode & EXT2_F_TYPE) == EXT2_S_IFREG)
{
char buffer[65];
uint read = ext2_read_inode(sb, &in, buffer, 64);
buffer[read] = 0;
kprintf("contents: %d\n'%s'\n", read, buffer);
}
}
return true;
}
void ext2_mount(struct fs_node *where)
{
UNUSED(where)
struct ext2_superblock sb = ext2_read_superblock();
kprintf(DEBUG "EXT2 magic = 0x%x\n", sb.signature);
// Read the root inode 2
struct ext2_inode root;
if (ext2_find_inode(&sb, 2, &root))
{
kprintf(OKAY "Found root inode 2 (size=0x%x, num_blocks=0x%x)\n",
root.size, root.num_blocks);
// kprintf(DEBUG "Root.mode = 0x%x\n", root.mode & 0xf000);
kassert((root.mode & 0xf000) == EXT2_S_IFDIR,
"Root (inode 2) is not a directory.");
char *name = "hello-hl.txt";
kprintf(INFO "Creating hard link %s -> hello.txt\n", name);
ext2_hard_link(&sb, &root, name, strlen(name), 12);
kprintf("ls /\n");
kprintf("inode\t name\n");
kprintf("--------------------\n");
ext2_dir_ls(&sb, &root, print_entry, &sb);
}
else
{
kprintf(WARN "Failed to find root inode 2\n");
}
kprintf(INFO "First free inode is %d\n", ext2_first_free_inode(&sb));
}
bool ext2_valid_filesystem()
{
struct ext2_superblock sb = ext2_read_superblock();
kprintf(DEBUG "superblock signature is %d (0x%x)\n", sb.signature,
sb.signature);
return sb.signature == EXT2_SIGNATURE;
}
void ext2_write_superblock(struct ext2_superblock *sb)
{
ushort *wp = (ushort *)sb;
ata_pio_write_sectors(2, 2, wp);
}
void ext2_corrupt_superblock_for_fun()
{
struct ext2_superblock sb = ext2_read_superblock();
sb.signature = 0xDEAD;
ext2_write_superblock(&sb);
}
bool ext2_get_or_set_inode(struct ext2_superblock *sb, uint number,
struct ext2_inode *inode, bool set)
{
if (number == 0)
return false;
uint block_group = (number - 1) / sb->inodes_per_block_group;
uint local_index = (number - 1) % sb->inodes_per_block_group;
// Load this from the block group descriptor table
struct ext2_block_group_descriptor descriptor =
ext2_load_bgd(sb, block_group);
// We need to figure out what FS block the inode is on, we know how many
// inodes there are total in this BGD and the number per page, so this is
// simple.
const uint block_size = ext2_block_size(sb);
const uint inodes_per_block =
block_size / sizeof(struct ext2_inode);
uint inode_block = local_index / inodes_per_block;
uint inode_index = local_index % inodes_per_block;
struct ext2_inode inodes[block_size / sizeof(struct ext2_inode)];
const uint fs_block = descriptor.inode_table_start_block +
inode_block;
ext2_read_block(sb, inodes, fs_block);
if (set)
{
inodes[inode_index] = *inode;
ext2_write_block(sb, inodes, fs_block);
}
else
{
*inode = inodes[inode_index];
}
return true;
}
bool ext2_find_inode(struct ext2_superblock *sb, uint number,
struct ext2_inode *inode)
{
return ext2_get_or_set_inode(sb, number, inode, false);
}
bool ext2_set_inode(struct ext2_superblock *sb, uint number,
struct ext2_inode *inode)
{
return ext2_get_or_set_inode(sb, number, inode, true);
}
bool ext2_dir_ls(struct ext2_superblock *sb, struct ext2_inode *dir,
bool (*cb)(uint inode, const char *name, uint name_len,
void *data),
void *data)
{
if ((dir->mode & 0xf000) != EXT2_S_IFDIR)
return false;
for (uint i = 0; i < dir->num_blocks; i++)
{
uchar buffer[ext2_block_size(sb)];
ext2_read_inode_block(sb, dir, buffer, i);
struct ext2_dirent *ent = (void *)buffer;
// While there are files in this block
while ((uint)ent < (uint)(buffer + ext2_block_size(sb)))
{
if (ent->inode == 0)
return true;
if (cb)
{
char name[256];
uint name_len = MIN(ent->name_len, 255);
memcpy(name, ent->name, name_len);
name[name_len] = '\0';
if (!cb(ent->inode, name, name_len, data))
return true;
}
ent = (void *)(((uint)(void *)ent) + ent->rec_len);
}
// We ran out of files in this block, continue to the next one. This
// works because files cannot span blocks
}
return true;
}
static void ext2_show_dirent(struct ext2_dirent *ent)
{
char name[ent->name_len + 1];
memcpy(name, ent->name, ent->name_len);
name[ent->name_len] = '\0';
kprintf(DEBUG "<ent ft=%p, i=%d, s=%s, l=%d>\n", ent->file_type, ent->inode,
ent->name, ent->rec_len);
}
bool ext2_hard_link(struct ext2_superblock *sb, struct ext2_inode *dir,
char *name, uint name_len, uint inode)
{
struct ext2_inode in;
if (!ext2_dir_contains(sb, dir, name, name_len) &&
ext2_find_inode(sb, inode, &in))
{
if ((dir->mode & 0xf000) != EXT2_S_IFDIR)
{
return false;
}
// Increment the reference count to this inode
in.links_count++;
ext2_set_inode(sb, inode, &in);
// Insert it into the directory
uchar type = EXT2_S_TO_FT(in.mode);
ext2_insert_into_dir(sb, dir, name, name_len, inode, type);
return true;
}
else
{
return false;
}
}
void ext2_insert_into_dir(struct ext2_superblock *sb, struct ext2_inode *dir,
char *name, uint name_len, uint inode, uchar type)
{
name_len = MIN(name_len, 255);
const uint min_size = PAD(name_len + sizeof(struct ext2_dirent));
const uint block_size = ext2_block_size(sb);
if ((dir->mode & 0xf000) != EXT2_S_IFDIR)
return;
uchar buffer[block_size];
uint i; // block #
for (i = 0; i < dir->num_blocks; i++)
{
ext2_read_inode_block(sb, dir, buffer, i);
struct ext2_dirent *ent = (void *)buffer;
// While there are files in this block
while ((uint)ent < (uint)(buffer + block_size))
{
// kprintf(" %d@%db,%d-%d", ent->inode, i, (uint)ent - (uint)buffer,
// ent->rec_len);
if (ent->inode == 0)
{
// This is the last item, just insert it at the end
// TODO: check this actually fits!
// TODO: if we are in a new block, actually create it!
ent->rec_len = min_size;
ent->name_len = name_len;
memcpy(ent->name, name, name_len);
ent->inode = inode;
ent->file_type = type;
kprintf(DEBUG
"Inserted into dir (appending) at block=%d, b=%p \n",
i, (uint)ent - (uint)buffer);
goto finish;
}
uint this_min_size =
PAD(ent->name_len + sizeof(struct ext2_dirent));
uint available_size = ent->rec_len - this_min_size;
// kprintf(",%d=%d/%d", ent->name_len, this_min_size,
// available_size);
if (available_size >= min_size)
{
// We can fit this in here
struct ext2_dirent *inserting =
(void *)(((uint)(void *)ent) + this_min_size);
ent->rec_len = this_min_size;
inserting->rec_len = available_size;
inserting->name_len = name_len;
inserting->inode = inode;
inserting->file_type = type;
memcpy(inserting->name, name, name_len);
kprintf(DEBUG
"Inserted into dir (splicing) at block=%d, b=%p \n",
i, (uint)inserting - (uint)buffer);
// Done!
goto finish;
}
ent = (void *)(((uint)(void *)ent) + ent->rec_len);
}
// We ran out of files in this block, continue to the next one. This
// works because files cannot span blocks
}
kprintf("\n");
kprintf(WARN "Failed to insert!\n");
finish:
kprintf("\n");
ext2_write_inode_block(sb, dir, buffer, i);
kprintf(DEBUG "[insert] writing inode block %d\n", i);
}
ssize_t ext2_read_inode(struct ext2_superblock *sb, struct ext2_inode *inode,
void *buffer, ssize_t size)
{
const uint block_size = ext2_block_size(sb);
char transfer[block_size];
uint fsize = MIN(inode->size, size);
uint i;
// Transfer full blocks straight to the output buffer
for (i = 0; i < fsize / block_size; i++)
{
ext2_read_inode_block(sb, inode, buffer + i * block_size, i);
}
// If we have part of a block left over read it here first, then transfer
// what we need
if (i * block_size < fsize)
{
uint remainder = fsize % block_size;
ext2_read_inode_block(sb, inode, transfer, i);
memcpy(buffer + i * block_size, transfer, remainder);
}
return fsize;
}
static uint ext2_compute_absolute_block(struct ext2_superblock *sb,
struct ext2_inode *inode, uint block)
{
if (block >= 12)
{
kprintf(ERROR
"Sorry, EXT2 can only access the first 12 (direct) blocks "
"of an inode for now. Indirect look-up will be added later\n");
kpanic("Invalid inode block");
}
return block;
}
bool ext2_read_inode_block(struct ext2_superblock *sb, struct ext2_inode *inode,
void *buffer, uint block)
{
block = ext2_compute_absolute_block(sb, inode, block);
uint block_address = inode->blocks[block];
ext2_read_block(sb, buffer, block_address);
return true;
}
bool ext2_write_inode_block(struct ext2_superblock *sb, struct ext2_inode *dir,
void *buffer, uint block)
{
block = ext2_compute_absolute_block(sb, dir, block);
uint block_address = dir->blocks[block];
kprintf(DEBUG "Writing size=%d, inode block %p, b=%d\n",
ext2_block_size(sb), block_address * ext2_block_size(sb), block);
ext2_write_block(sb, buffer, block_address);
return true;
}
static const uint ext2_bitmap_block(struct ext2_superblock *sb,
uint *bitmap_block, uint *index)
{
const uint block_size = ext2_block_size(sb);
while (*index > block_size)
{
*index -= block_size;
*bitmap_block += 1;
}
return block_size;
}
bool ext2_check_in_bitmap(struct ext2_superblock *sb, uint bitmap_block,
uint index)
{
const uint block_size = ext2_bitmap_block(sb, &bitmap_block, &index);
uint byte = index / 8;
uint bit = index % 8;
uchar buffer[block_size];
ext2_read_block(sb, buffer, bitmap_block);
return !!(buffer[byte] & (1 << bit));
}
void ext2_set_in_bitmap(struct ext2_superblock *sb, uint bitmap_block,
uint index, bool value)
{
const uint block_size = ext2_bitmap_block(sb, &bitmap_block, &index);
uint byte = index / 8;
uint bit = index % 8;
uchar buffer[block_size];
ext2_read_block(sb, buffer, bitmap_block);
uchar target_bit = 1 << bit;
buffer[byte] =
value ? (buffer[byte] | target_bit) : (buffer[byte] | ~target_bit);
ext2_write_block(sb, buffer, bitmap_block);
}
uint ext2_first_zero_bit(struct ext2_superblock *sb, uint bitmap_block,
uint num_blocks, uint start_at)
{
uint block_size = ext2_block_size(sb);
for (uint block = bitmap_block; block < bitmap_block + num_blocks; block++)
{
// dword-array for performance
uint buffer[block_size / 4];
ext2_read_block(sb, buffer, block);
// If this is the first block start at start_at, otherwise 0
for (int i = 0; i < block_size / 4; i++)
{
// The bitwise negative will be non-zero if there are zero bits in
// the original.
if (~buffer[i])
{
// 4 bytes * 8 bits * i dwords
uint index =
(4 * 8 * i) + (block - bitmap_block) * 8 * block_size;
// __builtin_ffs gives us 1+the index of the least-significant 1
// bit. Since we take the bitwise inverse this is actuall the
// least significant 0 bit. This is a GCC intrinsic. This works
// particularly well on little-endian systems where the least
// significant bit happens to also correspond to the first bit
// in the dword bitset.
//
// ________ ________ ________ ________
// ^ this is the LSB ^
// | this is the MSB
//
// This means that the LSB is also the first bit in the bitset.
uint trailing = __builtin_ffs(~buffer[i]) - 1;
return trailing + index;
}
}
}
return -1;
}
uint ext2_first_free_inode(struct ext2_superblock *sb)
{
uint num_block_groups = ext2_num_block_groups(sb);
kprintf(INFO "%d block groups\n", num_block_groups);
for (int bg_num = 0; bg_num < num_block_groups; bg_num++)
{
struct ext2_block_group_descriptor bgd =
ext2_load_bgd(sb, 0);
const uint block_size = ext2_block_size(sb);
// + 1 because we need to round up (ie 1025 for 1024 size blocks will
// yield 1, should 2)
uint bitset_blocks = (sb->inodes_per_block_group / 8) / block_size + 1;
// inodes start at 1
uint inode =
ext2_first_zero_bit(sb, bgd.inode_bitmap, bitset_blocks, 12) + 1;
// This will overflow back to zero if no inode was found
if (inode)
return inode;
}
return 0;
}
// ^
// | this and | this are awfully similar, should refactor
// v
uint ext2_first_free_block(struct ext2_superblock *sb)
{
uint num_block_groups = ext2_num_block_groups(sb);
for (int bg_num = 0; bg_num < num_block_groups; bg_num++)
{
struct ext2_block_group_descriptor bgd =
ext2_load_bgd(sb, 0);
const uint block_size = ext2_block_size(sb);
// + 1 because we need to round up (ie 1025 for 1024 size blocks will
// yield 1, should 2)
uint bitset_blocks = (sb->blocks_per_block_group / 8) / block_size + 1;
// inodes start at 1
uint block_no =
ext2_first_zero_bit(sb, bgd.block_bitmap, bitset_blocks, 0);
// This will overflow back to zero if no inode was found
if (block_no != 0xffffffff)
return block_no;
}
return 0;
}
struct ext2_dir_contains_data
{
char *name;
uint len;
bool found;
};
static bool ext2_dir_contains_cb(uint inode, const char *name,
uint name_len,
struct ext2_dir_contains_data *d)
{
if (strncmp((char *)name, d->name, MIN(name_len, d->len)) == 0)
{
d->found = true;
return false;
}
return true;
}
bool ext2_dir_contains(struct ext2_superblock *sb, struct ext2_inode *dir,
char *name, uint len)
{
if ((dir->mode & EXT2_F_TYPE) != EXT2_S_IFDIR)
{
return false;
}
struct ext2_dir_contains_data d =
{
.name = name,
.len = len,
.found = false,
};
ext2_dir_ls(sb, dir, ext2_dir_contains_cb, &d);
return d.found;
}
struct ext2_dir_find_data
{
char *name;
uint len;
uint inode;
};
bool ext2_dir_find_cb(uint inode, const char *name, uint len,
struct ext2_dir_find_data *d)
{
if (strncmp((char *)name, d->name, MIN(len, d->len)) == 0)
{
d->inode = inode;
return false;
}
return true;
}
uint ext2_dir_find(struct ext2_superblock *sb, struct ext2_inode *dir,
char *name, uint name_len)
{
if ((dir->mode & EXT2_F_TYPE) != EXT2_S_IFDIR)
{
return false;
}
struct ext2_dir_find_data d =
{
.name = name,
.len = name_len,
.inode = 0,
};
ext2_dir_ls(sb, dir, ext2_dir_find_cb, &d);
return d.inode;
}
uint ext2_alloc_new_block(struct ext2_superblock *sb,
uint block_group)
{
struct ext2_block_group_descriptor bgd =
ext2_load_bgd(sb, block_group);
if (bgd.unallocated_blocks == 0)
// TODO: handle out of blocks
return ext2_alloc_new_block(sb, block_group + 1);
// We can safely pass ~0 here as long as the FS is well formed
// because we know there is at least 1 free block
uint block = ext2_first_zero_bit(sb, bgd.block_bitmap, ~0, 0);
ext2_set_in_bitmap(sb, bgd.block_bitmap, block, true);
bgd.unallocated_blocks--;
ext2_write_bgd(sb, block_group, &bgd);
return block;
}