*.o
+/fs.bin
/mkfs
+/inode_test.txt
+/inode_test_gen
+/inode_test_run
/pool_test.txt
/pool_test_gen
/pool_test_run
CFLAGS=-g -Wall
-all: pool_test_gen pool_test_run process_test_gen process_test_run ucp mkfs
+all: pool_test_gen pool_test_run process_test_gen process_test_run ucp mkfs \
+inode_test_gen inode_test_run
pool_test_gen: pool_test_gen.o
${CC} ${CFLAGS} -o $@ $^
mkfs: mkfs.o util.o
${CC} ${CFLAGS} -o $@ $^
+inode_test_gen: inode_test_gen.o
+ ${CC} ${CFLAGS} -o $@ $^
+
+inode_test_gen.o: inode_test_gen.c
+
+inode_test_run: inode_test_run.o fuzix_fs.o util.o
+ ${CC} ${CFLAGS} -o $@ $^
+
+inode_test_run.o: inode_test_run.c fuzix_fs.h util.h
+
clean:
- rm -f pool_test_gen pool_test_run process_test_gen process_test_run ucp mkfs *.o
+ rm -f pool_test_gen pool_test_run process_test_gen process_test_run \
+ucp mkfs inode_test_gen inode_test_run *.o
+#include <assert.h> // Nick
#include <stdio.h>
#include <string.h>
#include <time.h>
inoptr root;
struct cinode i_tab[ITABSIZE];
struct filesys fs_tab[1];
-uint16_t bufclock; /* Time-stamp counter for LRU */
+long long/*uint16_t*/ bufclock; /* Time-stamp counter for LRU */
struct blkbuf bufpool[NBUFS];
struct u_data udata;
}
if (fuzix_getmode(ino) == F_REG) {
/* Truncate the file to zero length */
+ udata.u_offset = 0;
f_trunc(ino);
/* Reset any oft pointers */
for (j = 0; j < OFTSIZE; ++j)
ino->c_node.i_size = swizzle32(udata.u_offset);
ino->c_dirty = 1;
}
- return towrite;
+
+ return udata.u_count - towrite; // Nick bugfix
default:
udata.u_error = ENODEV;
m = swizzle16(ino->c_node.i_mode);
if (((m & F_MASK) == F_REG) ||
- ((m & F_MASK) == F_DIR) || ((m & F_MASK) == F_PIPE))
+ ((m & F_MASK) == F_DIR) || ((m & F_MASK) == F_PIPE)) {
+ udata.u_offset = 0;
f_trunc(ino);
+ }
}
/* If the inode was modified, we must write it to disk. */
if (!(ino->c_refs) && ino->c_dirty) {
void f_trunc(inoptr ino)
{
int dev;
+ blkno_t blk;
+ int32_t blocks;
int j;
+ if (udata.u_offset >= ino->c_node.i_size)
+ return;
+
+ ino->c_node.i_size = udata.u_offset;
+ ino->c_dirty = 1;
+
dev = ino->c_dev;
+ blocks = (int32_t)((udata.u_offset + 511) >> 9);
/* First deallocate the double indirect blocks */
- freeblk(dev, swizzle16(ino->c_node.i_addr[19]), 2);
+ blk = swizzle16(ino->c_node.i_addr[19]);
+ if (blocks > 18 + 256) {
+ freeblk_partial2(dev, blk, blocks - (18 + 256));
+ return;
+ }
+ freeblk(dev, blk, 2);
+ ino->c_node.i_addr[19] = 0;
/* Also deallocate the indirect blocks */
- freeblk(dev, swizzle16(ino->c_node.i_addr[18]), 1);
+ blk = swizzle16(ino->c_node.i_addr[18]);
+ if ((int)blocks > 18) {
+ freeblk_partial1(dev, blk, (int)blocks - 18);
+ return;
+ }
+ freeblk(dev, blk, 1);
+ ino->c_node.i_addr[18] = 0;
/* Finally, free the direct blocks */
- for (j = 17; j >= 0; --j)
+ for (j = 17; j >= (int)blocks; --j) {
freeblk(dev, swizzle16(ino->c_node.i_addr[j]), 0);
+ ino->c_node.i_addr[j] = 0;
+ }
+}
- bzero((char *) ino->c_node.i_addr, sizeof(ino->c_node.i_addr));
+/* Companion functions to f_trunc(). */
+void freeblk_partial2(int dev, blkno_t blk, int32_t blocks)
+{
+ blkno_t *buf;
+ int end, j;
- ino->c_dirty = 1;
- ino->c_node.i_size = 0;
+ if (!blk || blocks >= 65536)
+ return;
+
+ buf = (blkno_t *) bread(dev, blk, 0);
+ end = (int)blocks >> 8;
+ for (j = 255; j > end; --j) {
+ freeblk(dev, swizzle16(buf[j]), 1);
+ buf[j] = 0;
+ }
+ freeblk_partial1(dev, swizzle16(buf[j]), (((int)blocks - 1) & 0xff) + 1);
+ bawrite((bufptr) buf);
}
+void freeblk_partial1(int dev, blkno_t blk, int blocks)
+{
+ blkno_t *buf;
+ int j;
+
+ if (!blk || blocks >= 256)
+ return;
+
+ buf = (blkno_t *) bread(dev, blk, 0);
+ for (j = 255; j >= blocks; --j) {
+ freeblk(dev, swizzle16(buf[j]), 0);
+ buf[j] = 0;
+ }
+ bawrite((bufptr) buf);
+}
-/* Companion function to f_trunc(). */
void freeblk(int dev, blkno_t blk, int level)
{
blkno_t *buf;
blk_free(dev, blk);
}
-
-
/* Changes: blk_alloc zeroes block it allocates */
/*
* Bmap defines the structure of file system storage by returning
done:
bp->bf_busy = 1;
+ //printf("bread %d\n", (int)(bp - bufpool));
bp->bf_time = ++bufclock; /* Time stamp it */
return (bp->bf_data);
}
int bfree(bufptr bp, int dirty)
{
+ assert(bp->bf_busy);
+ //printf("bfree %d %d\n", (int)(bp - bufpool), dirty);
/*printf("Releasing block %d (%d)\n", bp->bf_blk, dirty);*/
bp->bf_dirty |= dirty;
bp->bf_busy = 0;
bp = freebuf();
bp->bf_dev = -1;
bp->bf_busy = 1;
+ //printf("tmpbuf %d\n", (int)(bp - bufpool));
bp->bf_time = ++bufclock; /* Time stamp it */
return (bp->bf_data);
}
/* Try to find a non-busy buffer and write out the data if it is dirty */
oldest = NULL;
oldtime = 0;
+ //printf("nonbusy");
for (bp = bufpool; bp < bufpool + NBUFS; ++bp) {
+ //if (!bp->bf_busy)
+ // printf(" %d(%lld)", (int)(bp -bufpool), bufclock - bp->bf_time);
if (bufclock - bp->bf_time >= oldtime && !bp->bf_busy) {
oldest = bp;
oldtime = bufclock - bp->bf_time;
}
}
+ //printf("\n");
ifnot(oldest)
panic("no free buffers");
#define NDEVS 1
#define NBUFS 10
#define OFTSIZE 15
-#define ITABSIZE 20
+#define ITABSIZE 96 //20
#define _NSIG NSIGS
#define NULLINODE ((inoptr)NULL)
#define NULLBLK ((blkno_t)-1)
blkno_t bf_blk;
char bf_dirty;
char bf_busy;
- uint16_t bf_time; /* LRU time stamp */
+ long long/*uint16_t*/ bf_time; /* LRU time stamp */
} blkbuf;
typedef blkbuf *bufptr;
extern inoptr root;
extern struct cinode i_tab[ITABSIZE];
extern struct filesys fs_tab[1];
-extern uint16_t bufclock; /* Time-stamp counter for LRU */
+extern long long/*uint16_t*/ bufclock; /* Time-stamp counter for LRU */
extern struct blkbuf bufpool[NBUFS];
extern struct u_data udata;
void wr_inode(inoptr ino);
int isdevice(inoptr ino);
void f_trunc(inoptr ino);
+void freeblk_partial2(int dev, blkno_t blk, int32_t blocks);
+void freeblk_partial1(int dev, blkno_t blk, int blocks);
void freeblk(int dev, blkno_t blk, int level);
blkno_t bmap(inoptr ip, blkno_t bn, int rwflg);
void validblk(int dev, blkno_t num);
--- /dev/null
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "rassert.h"
+
+#define BLOCK_SIZE 0x200
+#define BLOCK_SIZE_SHIFT 9
+
+#define BLOCK_PTRS 0x100
+#define BLOCK_PTRS_SHIFT 8
+
+int rand_int(int n) {
+ return (int)((long long)rand() * n / (RAND_MAX + 1LL));
+}
+
+int bytes_to_blocks(int size) {
+ size = (size + (BLOCK_SIZE - 1)) >> BLOCK_SIZE_SHIFT;
+ int blocks = size;
+ if (size > 18) {
+ // has indirect blocks
+ size = (size + (BLOCK_PTRS - 1 - 18)) >> BLOCK_PTRS_SHIFT;
+ blocks += size;
+ if (size > 1) {
+ // has double indirect blocks
+ size = (size + (BLOCK_PTRS - 1 - 1)) >> BLOCK_PTRS_SHIFT;
+ rassert(size == 1);
+ blocks += size;
+ }
+ }
+ return blocks;
+}
+
+int main(int argc, char **argv) {
+ if (argc < 5) {
+ printf("usage: %s n_files n_blocks n_events file_size [seed]\n", argv[0]);
+ exit(EXIT_FAILURE);
+ }
+ int n_files = atoi(argv[1]);
+ int n_blocks = atoi(argv[2]);
+ int n_events = atoi(argv[3]);
+ int file_size = atoi(argv[4]);
+ int seed = argc >= 6 ? atoi(argv[5]) : 1;
+
+ int *files = malloc(n_files * sizeof(int));
+ rassert(files);
+ memset(files, -1, n_files * sizeof(int));
+
+ srand(seed);
+ int blocks_used = 0;
+ for (int i = 0; i < n_events; ++i) {
+ int file = rand_int(n_files);
+ int old_size = files[file];
+ if (old_size == -1) {
+ int size = rand_int(file_size * BLOCK_SIZE);
+ int size_blocks = bytes_to_blocks(size);
+ bool success = blocks_used + size_blocks <= n_blocks;
+ printf(
+ "alloc %d %d %s\n",
+ file,
+ size,
+ success ? "true" : "false"
+ );
+ if (success) {
+ files[file] = size;
+ blocks_used += size_blocks;
+ }
+ }
+ else if (rand_int(4)) {
+ int size = rand_int(file_size * BLOCK_SIZE);
+ int size_blocks = bytes_to_blocks(size);
+ int old_size_blocks = bytes_to_blocks(old_size);
+ bool success = blocks_used + size_blocks - old_size_blocks <= n_blocks;
+ printf(
+ "realloc %d %d %d %s\n",
+ file,
+ old_size,
+ size,
+ success ? "true" : "false"
+ );
+ if (success) {
+ files[file] = size;
+ blocks_used += size_blocks - old_size_blocks;
+ }
+ }
+ else {
+ printf("free %d %d\n", file, old_size);
+ files[file] = -1;
+ blocks_used -= bytes_to_blocks(old_size);
+ }
+ }
+
+ return 0;
+}
--- /dev/null
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#define UCP 1
+#include "fuzix_fs.h"
+#include "rassert.h"
+#include "util.h"
+
+#define BLOCK_SIZE 0x200
+#define BLOCK_SIZE_SHIFT 9
+
+#define BLOCK_PTRS 0x100
+#define BLOCK_PTRS_SHIFT 8
+
+#define TRANSFER_SIZE 821 // a prime number somewhat near the block size
+
+int rand_int(int n) {
+ return (int)((long long)rand() * n / (RAND_MAX + 1LL));
+}
+
+bool hash_init(int file, struct cinode *inode, int base, int limit) {
+ int count;
+ for (int ptr = base; (count = limit - ptr) > 0; ptr += count) {
+ if (count > TRANSFER_SIZE)
+ count = TRANSFER_SIZE;
+
+ uint8_t buf[TRANSFER_SIZE];
+ for (int i = 0; i < count; ++i) {
+ long long hash = file * 17 + (ptr + i) * 29;
+ hash = (hash & 0xffffffffLL) + (hash >> 32);
+ hash = (hash & 0xffffLL) + (hash >> 16);
+ hash = (hash & 0xffLL) + (hash >> 8);
+ hash = (hash & 0xffLL) + (hash >> 8);
+ buf[i] = (uint8_t)hash;
+ }
+
+ udata.u_base = (char *)buf;
+ udata.u_count = count;
+ udata.u_offset = ptr;
+ udata.u_error = 0;
+ if (writei(inode) < count || udata.u_error)
+ return false;
+ }
+ rassert((int)inode->c_node.i_size == limit);
+ return true;
+}
+
+void hash_verify(int file, struct cinode *inode, int base, int limit) {
+ int count;
+ for (int ptr = base; (count = limit - ptr) > 0; ptr += count) {
+ if (count > TRANSFER_SIZE)
+ count = TRANSFER_SIZE;
+
+ uint8_t buf[TRANSFER_SIZE];
+ udata.u_base = (char *)buf;
+ udata.u_count = count;
+ udata.u_offset = ptr;
+ udata.u_error = 0;
+ rassert(readi(inode) == count && udata.u_error == 0);
+
+ for (int i = 0; i < count; ++i) {
+ long long hash = file * 17 + (ptr + i) * 29;
+ hash = (hash & 0xffffffffLL) + (hash >> 32);
+ hash = (hash & 0xffffLL) + (hash >> 16);
+ hash = (hash & 0xffLL) + (hash >> 8);
+ hash = (hash & 0xffLL) + (hash >> 8);
+ rassert(buf[i] == (uint8_t)hash);
+ }
+
+ base += count;
+ }
+}
+
+int main(int argc, char **argv) {
+ if (argc < 3) {
+ printf("usage: %s fs_path n_files\n", argv[0]);
+ exit(EXIT_FAILURE);
+ }
+ char *fs_path = argv[1];
+ int n_files = atoi(argv[2]);
+
+ fd_open(fs_path);
+ xfs_init(0);
+ printf("free inodes %d blocks %d\n", fs_tab[0].s_tinode, fs_tab[0].s_tfree);
+
+ struct cinode **files = malloc(n_files * sizeof(struct cinode *));
+ rassert(files);
+ memset(files, 0, n_files * sizeof(struct cinode *));
+
+ while (true) {
+ //printf("free inodes %d blocks %d\n", fs_tab[0].s_tinode, fs_tab[0].s_tfree);
+ char buf[256];
+ switch (scanf("%s", buf)) {
+ case -1:
+ goto done;
+ case 1:
+ break;
+ default:
+ rassert(false);
+ }
+ if (strcmp(buf, "alloc") == 0) {
+ int file, size;
+ rassert(scanf("%d %d %s", &file, &size, buf) == 3);
+ rassert(file >= 0 && file < n_files);
+ rassert(size >= 0);
+ bool success;
+ if (strcmp(buf, "false") == 0)
+ success = false;
+ else if (strcmp(buf, "true") == 0)
+ success = true;
+ else
+ rassert(false);
+ printf(
+ "alloc %d %d %s\n",
+ file,
+ size,
+ success ? "true" : "false"
+ );
+ rassert(files[file] == NULL);
+ bool result;
+ files[file] = i_open(0, 0);
+ if (files[file] == NULL)
+ result = false;
+ else {
+ /* This does not implement BSD style "sticky" groups */
+ files[file]->c_node.i_uid = udata.u_euid;
+ files[file]->c_node.i_gid = udata.u_egid;
+
+ files[file]->c_node.i_mode = F_REG; /* For the time being */
+ files[file]->c_node.i_nlink = 0;
+ files[file]->c_node.i_size = 0;
+ for (int i = 0; i < 20; ++i)
+ files[file]->c_node.i_addr[i] = 0;
+ wr_inode(files[file]);
+
+ if (!hash_init(file, files[file], 0, size)) {
+ result = false;
+ i_deref(files[file]);
+ files[file] = NULL;
+ }
+ else
+ result = true;
+ }
+ printf(
+ "... %s\n",
+ result == success ?
+ "ok" :
+ result ? "succeeded, should fail" : "failed, should succeed"
+ );
+ if (files[file] && !success) {
+ printf("... undo\n");
+ i_deref(files[file]);
+ files[file] = NULL;
+ }
+ }
+ else if (strcmp(buf, "realloc") == 0) {
+ int file, old_size, size;
+ rassert(scanf("%d %d %d %s", &file, &old_size, &size, buf) == 4);
+ rassert(file >= 0 && file < n_files);
+ rassert(old_size >= 0);
+ rassert(size >= 0);
+ bool success;
+ if (strcmp(buf, "false") == 0)
+ success = false;
+ else if (strcmp(buf, "true") == 0)
+ success = true;
+ else
+ rassert(false);
+ printf(
+ "realloc %d %d %d %s\n",
+ file,
+ old_size,
+ size,
+ success ? "true" : "false"
+ );
+ if (files[file] == NULL)
+ printf("... not allocated, ignore\n");
+ else {
+ int actual_old_size = (int)files[file]->c_node.i_size;
+ if (actual_old_size != old_size) {
+ printf(
+ "... old size %d, should be %d\n",
+ actual_old_size,
+ old_size
+ );
+ rassert(actual_old_size <= old_size);
+ }
+ bool result;
+ if (size < actual_old_size) {
+ hash_verify(file, files[file], size, actual_old_size);
+ udata.u_offset = size;
+ f_trunc(files[file]);
+ result = true;
+ }
+ else if (!hash_init(file, files[file], actual_old_size, size)) {
+ udata.u_offset = actual_old_size;
+ f_trunc(files[file]);
+ result = false;
+ }
+ else
+ result = true;
+ printf(
+ "... %s\n",
+ result == success ?
+ "ok" :
+ result ? "succeeded, should fail" : "failed, should succeed"
+ );
+ if (result && !success) {
+ printf("... undo\n");
+ udata.u_offset = actual_old_size;
+ f_trunc(files[file]);
+ }
+ }
+ }
+ else if (strcmp(buf, "free") == 0) {
+ int file, old_size;
+ rassert(scanf("%d %d", &file, &old_size) == 2);
+ rassert(file >= 0 && file < n_files);
+ rassert(old_size >= 0);
+ printf(
+ "free %d %d\n",
+ file,
+ old_size
+ );
+ if (files[file] == NULL)
+ printf("... not allocated, ignore\n");
+ else {
+ int actual_old_size = (int)files[file]->c_node.i_size;
+ if (actual_old_size != old_size) {
+ printf(
+ "... old size %d, should be %d\n",
+ actual_old_size,
+ old_size
+ );
+ rassert(actual_old_size <= old_size);
+ }
+ hash_verify(file, files[file], 0, actual_old_size);
+ i_deref(files[file]);
+ files[file] = NULL;
+ printf("... ok\n");
+ }
+ }
+ else
+ rassert(false);
+ }
+
+done:
+ printf("free inodes %d blocks %d\n", fs_tab[0].s_tinode, fs_tab[0].s_tfree);
+
+ printf("final state:\n");
+ for (int i = 0; i < n_files; ++i) {
+ if (files[i] == NULL)
+ printf("file %d: not allocated\n", i);
+ else {
+ int size = (int)files[i]->c_node.i_size;
+ printf("file %d: size %d\n", i, size);
+ hash_verify(i, files[i], 0, size);
+ i_deref(files[i]);
+ }
+ }
+
+ printf("free inodes %d blocks %d\n", fs_tab[0].s_tinode, fs_tab[0].s_tfree);
+
+ return 0;
+}
--- /dev/null
+#!/bin/sh
+
+echo "generate test script"
+./inode_test_gen 64 16128 16384 4096 >inode_test.txt
+
+echo "run test script"
+rm -f fs.bin
+./mkfs fs.bin 256 16384
+./inode_test_run fs.bin 64 <inode_test.txt
}
}
else {
- printf(
- "free %d %d\n",
- item,
- old_size
- );
+ printf("free %d %d\n", item, old_size);
items[item] = -1;
pool_used -= old_size;
}
+#include <assert.h> // Nick
+#include <stdbool.h> // Nick
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
void panic(char *s)
{
fprintf(stderr, "panic: %s\n", s);
+ assert(false);
exit(1);
}
public / moveable_pool.git / commitdiff