From 85bd74dbbe2fd72f095c454a52e5094412002a31 Mon Sep 17 00:00:00 2001 From: Liu Aleaxander Date: Mon, 31 May 2010 03:17:15 +0800 Subject: [PATCH] dir stuff and part of fs-write stuff added Signed-off-by: Liu Aleaxander --- Makefile | 11 +++-- balloc.c | 2 +- cache.c | 126 ++++++++++++++++++++++++++++++++++++++++++++++++ cache.h | 22 +++++++++ dir.c | 164 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ dirent.h | 28 +++++++++++ inode.c | 131 +++++++++++++++++++++++++++++++++++++++++++------- tfs.h | 12 +++++ 8 files changed, 475 insertions(+), 21 deletions(-) create mode 100644 cache.c create mode 100644 cache.h create mode 100644 dir.c create mode 100644 dirent.h diff --git a/Makefile b/Makefile index 52e7e14..79cc1b5 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,4 @@ -all: mktfs balloc inode ialloc +all: mktfs inode mktfs: mktfs.c utils.c tfs.h gcc -g -o mktfs mktfs.c utils.c @@ -9,12 +9,15 @@ balloc: balloc.c utils.c super.c tfs.h ialloc: ialloc.c utils.c super.c tfs.h gcc -g -o ialloc ialloc.c utils.c super.c -inode: inode.c utils.c super.c tfs.h - gcc -g -o inode inode.c utils.c super.c ialloc.c +inode: inode.c utils.c super.c cache.c balloc.c dir.c tfs.h + gcc -g -o inode inode.c utils.c super.c ialloc.c cache.c dir.c balloc.c + +dir: dir.c utils.c super.c cache.c balloc.c tfs.h cache.h dirent.h + gcc -g -o dir dir.c cache.c utils.c super.c balloc.c mkfs: qemu-img create tfs.img 1M ./mktfs tfs.img clean: - rm -f mktfs balloc ialloc inode *.o + rm -f mktfs balloc ialloc inode dir *.o diff --git a/balloc.c b/balloc.c index 903a790..9dbac75 100644 --- a/balloc.c +++ b/balloc.c @@ -46,7 +46,7 @@ int tfs_alloc_block(struct tfs_sb_info *sbi, uint32_t block) return block; } -#if 1 /* the deubg part */ +#if 0 /* the deubg part */ #include int main(int argc, char *argv[]) { diff --git a/cache.c b/cache.c new file mode 100644 index 0000000..32a940a --- /dev/null +++ b/cache.c @@ -0,0 +1,126 @@ +/* + * A simple LRU cache implemention. Even the fstk is a user-space program, + * but we really do need a cache algorithm to make fstk more effective. + * + * This file is from Syslinux_project/core/cache.c. This file can + * be redistributed under the terms of the GNU Public License. + */ + +#include +#include + +#include "tfs.h" +#include "cache.h" + + +/* The cache data, we just make it be 32K, and it's enough for us */ +#define CACHE_SIZE (32 << 10) + +static char cache_data[CACHE_SIZE]; + +#define MAX_CACHE_ENTRIES 64 /* assume we have a block size as 512 */ +static struct cache_struct cache_head; +static struct cache_struct cache[MAX_CACHE_ENTRIES]; +static int cache_entries = 0; + +/* + * Initialize the cache data structres + */ +void cache_init(struct tfs_sb_info *sbi) +{ + struct cache_struct *prev, *cur; + char *data = cache_data; + int i; + + cache_entries = CACHE_SIZE >> sbi->s_block_shift; + if (cache_entries > MAX_CACHE_ENTRIES) + cache_entries = MAX_CACHE_ENTRIES; + + cache_head.prev = &cache[cache_entries-1]; + cache_head.prev->next = &cache_head; + prev = &cache_head; + + for (i = 0; i < cache_entries; i++) { + cur = &cache[i]; + cur->block = 0; + cur->prev = prev; + prev->next = cur; + cur->data = data; + cur->outdate = 0; + data += sbi->s_block_size; + prev = cur++; + } +} + + +/* + * Check for a particular BLOCK in the block cache, + * and if it is already there, just do nothing and return; + * otherwise load it and updata the relative cache + * structre with data pointer. + */ +struct cache_struct* get_cache_block(struct tfs_sb_info *sbi, uint32_t block) +{ + struct cache_struct *head = &cache_head; + struct cache_struct *last = head->prev; + /* let's find it from the end, 'cause the endest is the freshest */ + struct cache_struct *cs = head->prev; + int i; + + if (!block) { + printf("ERR: we got a ZERO block number that's not we want!\n"); + return NULL; + } + + /* it's aleardy the freshest, so nothing we need do , just return it */ + if (cs->block == block && !cs->outdate) + goto out; + + for (i = 0; i < cache_entries; i ++) { + if (cs->block == block) + break; + else + cs = cs->prev; + } + + /* missed, so we need to load it */ + if (i == cache_entries) { + /* store it at the head of real cache */ + cs = head->next; + cs->block = block; + tfs_bread(sbi, block, cs->data); + } else if (cs->outdate) { + tfs_bread(sbi, block, cs->data); + } + + /* remove cs from current position in list */ + cs->prev->next = cs->next; + cs->next->prev = cs->prev; + + /* add to just before head node */ + last->next = cs; + cs->prev = last; + head->prev = cs; + cs->next = head; +out: + return cs; +} + + +/** + * Just print the sector, and according the LRU algorithm, + * Left most value is the most least secotr, and Right most + * value is the most Recent sector. I see it's a Left Right Used + * (LRU) algorithm; Just kidding:) + */ +void print_cache(void) +{ + int i = 0; + struct cache_struct *cs = &cache_head; + for (; i < cache_entries; i++) { + cs = cs->next; + printf("%d(%p) ", cs->block, cs->data); + } + + printf("\n"); +} diff --git a/cache.h b/cache.h new file mode 100644 index 0000000..8739ed4 --- /dev/null +++ b/cache.h @@ -0,0 +1,22 @@ +#ifndef CACHE_H +#define CACHE_H + +#include + +/* The cache structure */ +struct cache_struct { + uint32_t block; + struct cache_struct *prev; + struct cache_struct *next; + void *data; + int outdate; +}; + + +/* functions */ +void cache_init(struct tfs_sb_info *); +struct cache_struct *get_cache_block(struct tfs_sb_info *, uint32_t); +void print_cache(void); + + +#endif /* cache.h */ diff --git a/dir.c b/dir.c new file mode 100644 index 0000000..f608c7f --- /dev/null +++ b/dir.c @@ -0,0 +1,164 @@ +#include +#include +#include + +#include "tfs.h" +#include "cache.h" +#include "dirent.h" + +/* + * NOTE! unlike strncmp, ext2_match_entry returns 1 for success, 0 for failure. + * + * len <= EXT2_NAME_LEN and de != NULL are guaranteed by caller. + */ +static inline int tfs_match_entry (const char * const name, + struct tfs_dir_entry * de) +{ + if (!de->d_inode) + return 0; + return !strncmp(name, de->d_name, strlen(name)); +} + +struct tfs_dir_entry * tfs_find_entry(struct tfs_sb_info *sbi, + const char *dname, + struct inode *inode) +{ + uint32_t block; + int i = 0; + int index = 0; + struct tfs_dir_entry *de; + struct cache_struct *cs; + + block = inode->i_data[index++]; + return NULL; + cs = get_cache_block(sbi, block); + de = (struct tfs_dir_entry *)cs->data; + + while(i < (int)inode->i_size) { + if ((char *)de >= (char *)cs->data + sbi->s_block_size) { + if ((block = inode->i_data[index++]) < sbi->s_data_area) + return NULL; + cs = get_cache_block(sbi, block); + de = (struct tfs_dir_entry *)cs->data; + } + if (tfs_match_entry(dname, de)) + return de; + + de++; + } + + return NULL; +} + +int tfs_add_entry(struct tfs_sb_info *sbi, struct inode *dir, const char *name, int inr, int * dirty) +{ + uint32_t block; + int i = 0, index = 0; + struct cache_struct *cs; + struct tfs_dir_entry *de; + + if (strlen(name) > TFS_NAME_LEN) { + printf("ERROR: file name too long!\n"); + return -1; + } + + if (!(block = dir->i_data[index++])) + return -1; + cs = get_cache_block(sbi, block); + de = (struct tfs_dir_entry *)cs->data; + while (i <= (int)dir->i_size) { + if ((void *)de >= cs->data + sbi->s_block_size) { + if (!(block = dir->i_data[index++])) + break; + cs = get_cache_block(sbi, block); + de = (struct tfs_dir_entry *)cs->data; + } + if (!de->d_inode) + break; + i += sizeof(struct tfs_dir_entry); + } + + *dirty = 0; + + /* allocate a new block to hold the new entry */ + if (!block) { + block = tfs_alloc_block(sbi, sbi->s_data_area); + dir->i_data[index] = block; + if (block == -1) { + printf("ERROR: allocate new block failed, out of space!\n"); + return -1; + } + cs = get_cache_block(sbi, block); + de = (struct tfs_dir_entry *)cs->data; + memset(cs->data, 0, sbi->s_block_size); + /* + * tell the cache system to update the cache block + * in the next time read + */ + cs->outdate = 1; + + /* + * This will go through the next if sentence, since if we + * allocated a new entry, then 'i >= dir->i_size' would + * be true. + */ + } + + if (i >= dir->i_size) { + /* Add a new entry at last */ + dir->i_size += sizeof(struct tfs_dir_entry); + + /* tell the caller to update this inode */ + *dirty = 1; + } + + /* + * Else, we find a unused hole, this usually happens when user + * removes a file or directory, so we can just fill up + * the hole, and do not need allocate more space. + */ + de->d_inode = inr; + memcpy(de->d_name, name, strlen(name)); + + /* write the entry back to disk */ + tfs_bwrite(sbi, block, cs->data); + + return 0; +} + + + +/* read one directry entry at a time */ +static struct dirent * tfs_readdir(struct tfs_sb_info *sbi, struct inode *inode, uint32_t offset) +{ + struct dirent *dirent; + struct tfs_dir_entry *de; + struct cache_struct *cs; + int index = offset >> sbi->s_block_shift; + uint32_t block; + + if (!(block = inode->i_data[index])) + return NULL; + cs = get_cache_block(sbi, block); + de = (struct tfs_dir_entry *)(cs->data + (offset & (sbi->s_block_size- 1))); + + if (!(dirent = malloc(sizeof(*dirent)))) { + printf("malloc dirent structure in tfs_readdir error!\n"); + return NULL; + } + memset(dirent, 0, sizeof(*dirent)); + dirent->d_ino = de->d_inode; + dirent->d_off = offset; + dirent->d_reclen = sizeof(struct tfs_dir_entry); + dirent->d_type = 0; + memcpy(dirent->d_name, de->d_name, TFS_NAME_LEN); + + return dirent; + +} + +#if 0 /* the debug part */ +int main(int argc, char *argv[]) +{ +} +#endif diff --git a/dirent.h b/dirent.h new file mode 100644 index 0000000..b1e02ba --- /dev/null +++ b/dirent.h @@ -0,0 +1,28 @@ +#ifndef DIRENT_H +#define DIRENT_H + +#include + +struct dirent { + uint32_t d_ino; + uint32_t d_off; + uint16_t d_reclen; + uint16_t d_type; + char d_name[256]; +}; + +/* + +typedef struct { + struct file *dd_dir; +} DIR; + +extern DIR *this_dir; + +DIR * fstk_opendir(struct fstk *, char *); +struct dirent * fstk_readdir(DIR *); +void fstk_closedir(DIR *); + +*/ + +#endif /* dirent.h */ diff --git a/inode.c b/inode.c index 1c8407c..5214c13 100644 --- a/inode.c +++ b/inode.c @@ -3,6 +3,7 @@ #include #include "tfs.h" +#include "cache.h" #define current_time 0 @@ -91,7 +92,8 @@ struct inode * tfs_new_inode(struct tfs_sb_info *sbi, int mode) static void tfs_fill_inode(struct inode *inode, struct tfs_inode *tinode) { - inode->i_mode = get_mode(tinode->i_mode); + //inode->i_mode = get_mode(tinode->i_mode); + inode->i_mode = tinode->i_mode; inode->i_size = tinode->i_size; inode->i_atime = tinode->i_atime; inode->i_ctime = tinode->i_ctime; @@ -105,21 +107,15 @@ static void tfs_fill_inode(struct inode *inode, struct tfs_inode *tinode) static int tfs_read_inode(struct tfs_sb_info *sbi, struct tfs_inode *tinode, int inr) { uint32_t inode_block; - char *buf = malloc(sbi->s_block_size); + struct cache_struct *cs; - if (!buf) { - printf("malloc buf for tfs_read_inode error!\n"); - return -1; - } - inode_block = sbi->s_inode_table + (inr - 1) / TFS_INODES_PER_BLOCK(sbi); - if (tfs_bread(sbi, inode_block, buf)) { - free(buf); + cs = get_cache_block(sbi, inode_block); + if (!cs) return -1; - } - memcpy(tinode, buf + (inr - 1) % TFS_INODES_PER_BLOCK(sbi), sizeof(*tinode)); - free(buf); + memcpy(tinode, cs->data + ((inr - 1) % TFS_INODES_PER_BLOCK(sbi)) * sizeof(*tinode), sizeof(*tinode)); + return 0; } @@ -158,8 +154,36 @@ static struct inode *tfs_iget(struct tfs_sb_info * sbi, char *dname, struct inod return tfs_iget_by_inr(sbi, de->d_inode); } +static void *tfs_write_inode(struct tfs_inode *tinode, struct inode *inode) +{ + tinode->i_mode = inode->i_mode; + tinode->i_size = inode->i_size; + tinode->i_atime = inode->i_atime; + tinode->i_ctime = inode->i_ctime; + tinode->i_mtime = inode->i_mtime; + tinode->i_dtime = inode->i_dtime; + tinode->i_flags = inode->i_flags; + + memcpy(tinode->i_block, inode->i_data, TFS_N_BLOCKS * sizeof(uint32_t *)); + tinode->i_reserved[0] = 0; + +} +static void *tfs_iwrite(struct tfs_sb_info *sbi, struct inode *inode) +{ + struct cache_struct *cs; + struct tfs_inode *tinode; + uint32_t inode_block; + + inode_block = sbi->s_inode_table + (inode->i_ino - 1) / TFS_INODES_PER_BLOCK(sbi); + cs = get_cache_block(sbi, inode_block); + tinode = (struct tfs_inode *)cs->data + ((inode->i_ino - 1) % TFS_INODES_PER_BLOCK(sbi)); + tfs_write_inode(tinode, inode); + tfs_bwrite(sbi, inode_block, cs->data); + cs->outdate = 1; +} + -struct inode * namei(struct tfs_sb_info *sbi, const char *name) +struct inode * namei(struct tfs_sb_info *sbi, const char *name, uint32_t flag) { struct inode *inode; struct inode *parent; @@ -178,9 +202,18 @@ struct inode * namei(struct tfs_sb_info *sbi, const char *name) while (*name) { p = part; - while (*name && *name != '/') + while (*name && *name != '/') { + if (p >= part + TFS_NAME_LEN) { + printf("ERROR: file name to long!\n"); + return NULL; + } *p++ = *name++; + } *p = '\0'; + while (*name && *name == '/') + name++; + if (!*name && (flag & LOOKUP_PARENT)) + return parent; inode = tfs_iget(sbi, part, parent); if (!inode) return NULL; @@ -189,13 +222,79 @@ struct inode * namei(struct tfs_sb_info *sbi, const char *name) parent = inode; if (!*name) break; - while (*name == '/') - name++; } return inode; } +static char *__strrchr(const char *s, int c) +{ + const char *end = s + strlen(s) - 1; + while (*end != c && end >= s) + end--; + if (end < s) + return NULL; + return end; +} + +static char *get_base_name(const char *path_org) +{ + char *p; + char *path = strdup(path_org); + + p = strrchr(path, '/'); + if (!p) + return NULL; + /* the /linux/hello/ case */ + if (*(p + 1) == 0) { + *p = 0; + p--; + while (*p != '/' && p >= path) { + *p = 0; + p--; + } + if (p < path) + return NULL; + } + + return p; +} + +struct inode * tfs_mknod(struct tfs_sb_info *sbi, const char *path, int mode) +{ + struct inode *dir; + struct inode *inode; + const char *filename = get_base_name(path); + struct tfs_dir_entry *de; + int dirty = 0; + + dir = namei(sbi, filename, LOOKUP_PARENT); + if (!dir) { + printf("ERROR: path not exist!\n"); + return NULL; + } + + if (de = tfs_find_entry(sbi, filename, dir)) { + printf("ERROR: %s exist!\n", path); + return NULL; + } + + inode = tfs_new_inode(sbi, mode); + if (!inode) + return NULL; + inode->i_mtime = inode->i_atime = current_time; + tfs_iwrite(sbi, inode); + + if (tfs_add_entry(sbi, dir, filename, inode->i_ino, &dirty) == -1) { + TFS_DEBUG("trying to add a new entry: %s faild!\n", filename); + return NULL; + } + if (dirty) + tfs_iwrite(sbi, dir); + + return inode; +} + #if 0 /* the debug part */ int main(int argc, char *argv[]) diff --git a/tfs.h b/tfs.h index 1fdbf0e..1b170d5 100644 --- a/tfs.h +++ b/tfs.h @@ -7,6 +7,9 @@ #define TFS_FILE 0x1 #define TFS_DIR 0x2 +/* namei: path lookup flags */ +#define LOOKUP_PARENT 0x1 + /* just support I_FILE and I_DIR only currently */ enum tfs_inode_mode { I_FILE, I_DIR, I_UNKNOWN }; @@ -126,4 +129,13 @@ struct tfs_sb_info * tfs_mount_by_fsname(const char *); int tfs_free_inode(struct tfs_sb_info *, int); int tfs_alloc_inode(struct tfs_sb_info *, int); +/* balloc.c */ +int tfs_alloc_block(struct tfs_sb_info *, uint32_t); +int tfs_free_block(struct tfs_sb_info *, uint32_t); + + +/* dir.c */ +struct tfs_dir_entry *tfs_find_entry(struct tfs_sb_info *, const char *, struct inode *); +int tfs_add_entry(struct tfs_sb_info *, struct inode *, const char *, int , int *); + #endif /* tfs.h */ -- 2.11.4.GIT