/**
nkchenz@gmail.com 2006.7.21
fslite

inode 的name长度固定为16字节，0表示字符串结束

紧接inode之后是nentrys个entry
endblock，endblock_offset方便新加项使用

每个block的首部2字节为block索引，指向nextblock，如果为0，则表示结束。

简化编程难度。

*/

#include
#include

/*计数*/
typedef unsigned short int atomic_t;

/*文件偏移*/
typedef unsigned short int loff_t;

/*读写字节数*/
typedef unsigned short int msize_t;

typedef unsigned char spinlock_t;

/*文件系统最小块大小, 为了保证能够存下一个inode，必须>=32*/
#define FSLITE_BLOCKSIZE 32

/*总块数*/
#define FSLITE_TOTAL_BLOCKS 1024 /*32K*/

/* 系统预留空间*/
#define FSLITE_EMERGENCY_BLOCKS 10

/*不算stdin，stdout，stderr，系统最多可以打开的文件数*/
#define FSLITE_MAX_OPENFILES 5
#define FSLITE_MAX_OPENDIRS 5

#define FSLITE_MAGICSTRING_LEN 6
#define FSLITE_MAGICSTRING “fSliTe”

#define FSLITE_SEPARATOR “/”

#define FSLITE_MAX_NAME_LEN 11
#define FSLITE_MAX_PATH_LEN 64

/*superblock中的state*/
#define FSLITE_STATE_R 0×01 //可读
#define FSLITE_STATE_RW 0×02 //可读写
#define FSLITE_STATE_INVALID 0×00 //不可用

#define FSLITE_FILE 0×01
#define FSLITE_DIR 0×02
#define FSLITE_LINK 0×04

/*通用错误代码*/
#define FSLITE_OK 0×0000
#define FSLITE_ERR -1
#define FSLITE_NOMEM 0×0002 /*空间不足*/
#define FSLITE_EOF 0×0003
#define FSLITE_NONEXIST 0×0004 /*文件不存在*/

/* 文件指针位置定义*/
#define FSLITE_SEEK_CUR 1
#define FSLITE_SEEK_END 2
#define FSLITE_SEEK_SET 0

/* fopen mode */
#define FSLITE_FOPEN_R 0×01 //可读
#define FSLITE_FOPEN_RW 0×02 //可读写

/*三个标注描述符*/
#define FSLITE_STDIN 0
#define FSLITE_STDOUT 1
#define FSLITE_STDERR 2

#define FSLITE_SIZEOFINODE sizeof(fslite_inode)
#define FSLITE_SIZEOFENTRY sizeof(atomic_t)

#define FSLITE_NEXTBLOCK(n) ( *(atomic_t *) &fslite_data[n][0] ) // 由block号码获得next指针地址

#define FSLITE_BLOCKADDR(n) ( &fslite_data[n][0] ) //由block号码获取block的地址

#define FSLITE_INODEADDR(n) ( (fslite_inode *) &fslite_data[n][0] ) // 由block号码获得inode指针地址

#define FSLITE_BLOCKNUMBER(p) ( ((atomic_t) (p) – (atomic_t) fslite_data) / FSLITE_BLOCKSIZE )

/* data structure *****************************************************
*/

/* 文件系统信息块superblock
*/
struct fslite_superblock
{
unsigned char magicstring[FSLITE_MAGICSTRING_LEN];
unsigned char version;
unsigned char state;

unsigned short int blocksize;

atomic_t used_blocks; /*总块数*/
atomic_t free_blocks; /*空闲块数*/

atomic_t first_freeblock;

atomic_t root_block; /*文件系统根节点所在块*/

spinlock_t lock;
};

/* 节点块
类型可以为file，dir，link等. 每个inode都位于block的开始
*/
struct fslite_inode
{
atomic_t next;

unsigned char mode;//该节点的权限
unsigned char type;//该节点的类型

atomic_t parentblock;

unsigned short int atime; /* last access time */
unsigned short int mtime; /* last modify time */

msize_t size; //文件的字节数

atomic_t nentry; //目录所含有的子项数

/* end始终指向最后一个子项
** nentry==0时，end为0
*/
atomic_t entry_endblock;

#if FSLITE_BLOCKSIZE > 255
atomic_t entry_endblock_offset;
#else
unsigned char entry_endblock_offset;
#endif

spinlock_t lock;//防止写冲突，防止使用过程中被删除
char name[FSLITE_MAX_NAME_LEN + 1]; //name字符串
};

typedef struct fslite_superblock fslite_superblock;
typedef struct fslite_inode fslite_inode;

/*文件的抽象结构*/
struct fslite_file
{
unsigned short int fd; /*文件描述符 stdin=0 stdout=1 stderr=2*/

unsigned char mode; /*打开方式*/

fslite_inode *inode;
fslite_superblock *sb;

loff_t fp; /*文件指针偏移*/
};

/*目录的抽象结构*/
struct fslite_dir
{
// unsigned short int fd; /*文件描述符 stdin=0 stdout=1 stderr=2*/
// unsigned char mode; /*打开方式*/

fslite_inode *inode;
fslite_superblock *sb;

loff_t dp; /*子项偏移*/
};

typedef struct fslite_file fslite_file;
typedef struct fslite_dir fslite_dir;

/* global declaration *****************************************************
*/

/*全局superblock指针*/
fslite_superblock * sb;
fslite_inode * root;

/* 虚拟ramfs映象 */
unsigned char fslite_data[FSLITE_TOTAL_BLOCKS][FSLITE_BLOCKSIZE];

/*全局打开文件数组*/
fslite_file files[FSLITE_MAX_OPENFILES + 3];
fslite_dir dirs[FSLITE_MAX_OPENDIRS ];
int nopenfiles;
int nopendirs;

/* spinlock **************************************************************
*/
int fslite_spin_lock(spinlock_t * lock)
{
return 0;
}

int fslite_spin_unlock(spinlock_t * lock)
{
return 0;
}

/* block **************************************************************
*/

/* 清零页面n
*/
int fslite_block_zero(atomic_t n)
{
memset(FSLITE_BLOCKADDR(n), 0, FSLITE_BLOCKSIZE);
return FSLITE_OK;
}

/* 从系统空闲列表获得一个空闲块, 不可能返回superblock 0，返回0表示错误
*/
atomic_t fslite_block_get()
{
atomic_t n;

if( sb->free_blocks lock);

n = sb->first_freeblock;
sb->first_freeblock = FSLITE_NEXTBLOCK(n);
sb-> used_blocks ++;
sb -> free_blocks –;

fslite_spin_unlock(&sb->lock);

fslite_block_zero(n);

printf(”block %d used\n”, n);
return n;
}

/* 释放块n
*/
int fslite_block_free(atomic_t n)
{

fslite_spin_lock(&sb->lock);

FSLITE_NEXTBLOCK(n) = sb->first_freeblock;
sb->first_freeblock = n;
//sb->last_freeblock = n;
sb-> used_blocks –;
sb-> free_blocks ++;

fslite_spin_unlock(&sb->lock);

printf(”block %d freed\n”, n);
return FSLITE_OK;
}

/* fs ***************************************************************
*/

/* 初始化文件系统
** superblock, block 号为0， fs的第一块
*/
int fslite_fs_init()
{
atomic_t i;

/* 设置superblock */
sb = (fslite_superblock * )FSLITE_BLOCKADDR(0);

//除了superblock，所有的都放入空闲列表
for(i=1; i magicstring, FSLITE_MAGICSTRING);
sb->version = 1;
sb->state = FSLITE_STATE_RW;
sb->blocksize = FSLITE_BLOCKSIZE;
sb->used_blocks = 0;
sb->free_blocks = FSLITE_TOTAL_BLOCKS – 1;
sb->first_freeblock = 1;

/* 设置rootblock */
sb->root_block = fslite_block_get();

root = FSLITE_INODEADDR( sb->root_block );
root->type = FSLITE_DIR;
root->parentblock = sb->root_block;

root->nentry = 0; // 含有0个子文件目录
strncpy(root->name, FSLITE_SEPARATOR, FSLITE_MAX_NAME_LEN);

printf(”blocks: %d/%d root: %d first_freeblock:%d\n”, sb->used_blocks, sb->free_blocks, sb->root_block, sb->first_freeblock);
printf(”inode size: %d\n”, FSLITE_SIZEOFINODE);

nopenfiles = 3;
nopendirs = 0;
return FSLITE_OK;
}

/* inode ***************************************************************
*/

/* 为node添加入口项 n
**
*/
int fslite_inode_addentry(atomic_t n, fslite_inode *p)
{

atomic_t tmp;

fslite_spin_lock(&p->lock);

if( p->nentry == 0) // 空目录
{
p->entry_endblock_offset = FSLITE_SIZEOFINODE;
p->entry_endblock = FSLITE_BLOCKNUMBER(p);
}else
p->entry_endblock_offset += FSLITE_SIZEOFENTRY;

/* 现在offset指向一个空的entry入口 */
if(p->entry_endblock_offset >= FSLITE_BLOCKSIZE) /*需要一个新block, offset此时应该等于 FSLITE_BLOCKSIZE*/
{
/* 需要一个新的block，只添加了一个entry，可知上一个block刚刚满 */
if((tmp=fslite_block_get()) == 0)
return FSLITE_ERR;

FSLITE_NEXTBLOCK(p->entry_endblock) = tmp;

p->entry_endblock = tmp;
p->entry_endblock_offset = FSLITE_SIZEOFENTRY;
// 新block的头部两个字节是 block索引，跳过
*(atomic_t *)(FSLITE_BLOCKADDR(tmp) + p->entry_endblock_offset) = n;

}else{ //原有block即可存下新加的这个入口
*(atomic_t *)(FSLITE_BLOCKADDR(p->entry_endblock) + p->entry_endblock_offset) = n;
}

p->nentry++;
fslite_spin_unlock(&p->lock);

return FSLITE_OK;
}

/* 获得node的第index个子项的值 */
atomic_t fslite_inode_getentry(atomic_t index, fslite_inode *p)
{

atomic_t nb, child;
unsigned char * start, *end;
int offset;
atomic_t nentry;

if( p->nentry == 0) // 空目录
return FSLITE_ERR;

nb = FSLITE_BLOCKNUMBER(p);
offset = FSLITE_SIZEOFINODE;
nentry = 0;
while(1)
{
start = (unsigned char * ) FSLITE_BLOCKADDR(nb) + offset;
if(nb == p->entry_endblock) // 最后一块
end = (unsigned char * ) FSLITE_BLOCKADDR(nb) + p->entry_endblock_offset;
else
end = (unsigned char * ) FSLITE_BLOCKADDR(nb) + FSLITE_BLOCKSIZE – FSLITE_SIZEOFENTRY;

while(1)
{
child = *(atomic_t*) start;

if(index == nentry)
return child;

nentry++;

// 处理完毕允许start==end，因为此时指向的也是有效元素，需要先进行处理
if(start==end) break;

start += FSLITE_SIZEOFENTRY;
}

// 如果刚刚处理的block是最后一个，则退出
if( nb == p->entry_endblock)
break;

// end指向的是 metablock索引 前的一个有效entry入口，所以要后移FSLITE_SIZEOFENTRY获得metablock索引
nb = FSLITE_NEXTBLOCK(nb);
offset = FSLITE_SIZEOFENTRY;
}

return 0;
}

/* 删除入口项 n
**
*/
int fslite_inode_delentry(atomic_t n, fslite_inode *p)
{

atomic_t nb, child, lastb;
unsigned char * start, *end;
int offset;

char shift;
char *v;

if( p->nentry == 0) // 空目录
return FSLITE_ERR;

fslite_spin_lock(&p->lock);

nb = FSLITE_BLOCKNUMBER(p);
offset = FSLITE_SIZEOFINODE;

shift=0;

lastb = nb;
while(1)
{
start = (unsigned char * ) FSLITE_BLOCKADDR(nb) + offset;
if(nb == p->entry_endblock) // 最后一块
end = (unsigned char * ) FSLITE_BLOCKADDR(nb) + p->entry_endblock_offset;
else
end = (unsigned char * ) FSLITE_BLOCKADDR(nb) + FSLITE_BLOCKSIZE – FSLITE_SIZEOFENTRY;

while(1)
{

child = *(atomic_t*) start;
if(shift)
{
*(atomic_t*)v = child;
v = start; //保存上一个的地址
}

if(child == n)
{
shift = 1;
v = start;
}

// 处理完毕允许start==end，因为此时指向的也是有效元素，需要先进行处理
if(start==end) break;

start += FSLITE_SIZEOFENTRY;
}

// 如果刚刚处理的block是最后一个，则退出
if( nb == p->entry_endblock)
break;

lastb = nb;
// end指向的是 metablock索引 前的一个有效entry入口，所以要后移FSLITE_SIZEOFENTRY获得metablock索引
nb = FSLITE_NEXTBLOCK(lastb);
offset = FSLITE_SIZEOFENTRY;
}

/* 没有找到？*/
if(shift==0)
{
fslite_spin_unlock(&p->lock);
return FSLITE_OK;
}

/* 最后一页只有一项，因此需要将其释放*/
if(p->entry_endblock_offset == FSLITE_SIZEOFENTRY)
{
fslite_block_free(nb);

/* 修改end指针，使其指向上一页的最后一个入口*/
p->entry_endblock_offset = FSLITE_BLOCKSIZE – FSLITE_SIZEOFENTRY;
p->entry_endblock = lastb;
FSLITE_NEXTBLOCK(p->entry_endblock) = 0;
}else
{
*(atomic_t *)(FSLITE_BLOCKADDR(nb) + p->entry_endblock_offset) = 0;
p->entry_endblock_offset -= FSLITE_SIZEOFENTRY;
}

p->nentry–;
fslite_spin_unlock(&p->lock);

return FSLITE_OK;
}

/* 在父目录parent下面创建名字为name的项，类型为type，返回新节点
** 如果parent不是目录，或者空间不够，则返回null
*/
fslite_inode *fslite_inode_createfile(char * name, fslite_inode *parent, unsigned char type)
{

fslite_inode *child;
atomic_t n;

if(parent == NULL || parent->type != FSLITE_DIR)
return NULL;

if(strcmp(name, “”)==0)
return NULL;

if((n=fslite_block_get()) == 0 )
return NULL;

child = FSLITE_INODEADDR(n);
fslite_spin_lock(&child->lock);
child->type=type;
child->parentblock = FSLITE_BLOCKNUMBER(parent);
strncpy(child->name, name, FSLITE_MAX_NAME_LEN);
fslite_spin_unlock(&child->lock);

if( fslite_inode_addentry(n, parent) != FSLITE_OK)
{
fslite_block_free(n);
return NULL;
}

return child;
}

/* 删除节点, 需要在父节点中删除相应入口
**
** 如果目录非空，不可删除
**
** 删除单个文件
**
** 目录删除可以在上层实现
*/
int fslite_inode_deletefile(fslite_inode *p)
{
atomic_t self;

atomic_t n, child, lastb;
int offset;
char *start, *end;

if(p == NULL)
return FSLITE_ERR;

if( p->type == FSLITE_DIR && p->nentry != 0)
return FSLITE_ERR;

self=FSLITE_BLOCKNUMBER(p);
if( p->parentblock == self) // root node can’t del
return FSLITE_ERR;

fslite_spin_lock(&p->lock);

/*释放文件数据占用的页面*/
if( p->type == FSLITE_FILE && p->nentry != 0 )
{
n = self;
lastb = n;
offset = FSLITE_SIZEOFINODE;
while(1)
{
start = (unsigned char * ) FSLITE_BLOCKADDR(n) + offset;
if(n == p->entry_endblock) // 最后一块
end = (unsigned char * ) FSLITE_BLOCKADDR(n) + p->entry_endblock_offset;
else
end = (unsigned char * ) FSLITE_BLOCKADDR(n) + FSLITE_BLOCKSIZE – FSLITE_SIZEOFENTRY;

while(1)
{
child = *(atomic_t*) start;
if(child)
fslite_block_free(child);

if(start==end) break;
start += FSLITE_SIZEOFENTRY;
}

// 如果刚刚处理的block是最后一个，则退出
if( n == p->entry_endblock){
if(n != self) // 不能多次释放同一个block，很危险^_^，那样的话freeblock list会存在回路
fslite_block_free(n);
break;
}

lastb = n;
// end指向的是 metablock索引 前的一个有效entry入口，所以要后移FSLITE_SIZEOFENTRY获得metablock索引
n = FSLITE_NEXTBLOCK(lastb);
offset = FSLITE_SIZEOFENTRY;
if(lastb != self)
fslite_block_free(lastb);
}
}

fslite_spin_unlock(&p->lock);

/* 在父目录中找到此项删除之*/
fslite_inode_delentry(self, FSLITE_INODEADDR(p->parentblock));
fslite_block_free(self);

return FSLITE_OK;
}

/* 从节点p中查找是否含有子项name
** 返回该子项的node指针，否则返回NULL
*/
fslite_inode * fslite_inode_findentry(char *name, fslite_inode *p)
{

atomic_t n;
unsigned char * start, *end;
int offset;

fslite_inode * child;

// 没有考虑 链接 link 的情况
if( p->type != FSLITE_DIR)
return NULL;

if( p->nentry == 0)
return NULL;

n = FSLITE_BLOCKNUMBER(p);
offset = FSLITE_SIZEOFINODE;
while(1)
{
start = (unsigned char * ) FSLITE_BLOCKADDR(n) + offset;
if(n == p->entry_endblock) // 最后一块
end = (unsigned char * ) FSLITE_BLOCKADDR(n) + p->entry_endblock_offset;
else
end = (unsigned char * ) FSLITE_BLOCKADDR(n) + FSLITE_BLOCKSIZE – FSLITE_SIZEOFENTRY;

while(1)
{
child = FSLITE_INODEADDR(*(atomic_t*) start);

/* 这里实现的方法是通过字符串比较，实际上可以先比较name的hash，速度应该更快 */
if(strcmp(child->name, name)==0)
return child;

// 处理完毕允许start==end，因为此时指向的也是有效元素，需要先进行处理
if(start==end) break;

start += FSLITE_SIZEOFENTRY;
}

// 如果刚刚处理的block是最后一个，则退出
if( n == p->entry_endblock)
break;

// end指向的是 metablock索引 前的一个有效entry入口，所以要后移FSLITE_SIZEOFENTRY获得metablock索引
n = FSLITE_NEXTBLOCK(n);
offset = FSLITE_SIZEOFENTRY;
}

return NULL;
}

/* name是相对路径，在节点parent下面查找name是否存在。
** 如果name存在，则返回本文件的对应的节点
** 如果parent不是目录或者是空目录，返回null
** 如果name为空，或者是绝对路径，则返回null
*/
fslite_inode *fslite_inode_findfile_relative(char *name, fslite_inode *parent)
{
char *p, *p1;
fslite_inode * node;
char buf[FSLITE_MAX_NAME_LEN+1];

if(parent == NULL || parent->type != FSLITE_DIR || parent->nentry == 0)
return NULL;

if(strcmp(name, “”)==0)
return NULL;

// 绝对路径
if(strncmp(name, FSLITE_SEPARATOR, strlen(FSLITE_SEPARATOR))==0)
return NULL;

p = name;
node = parent;

while(*p != 0)
{
memset(buf, 0, FSLITE_MAX_NAME_LEN+1);

p1 = strstr(p, FSLITE_SEPARATOR);
if(p1)
{
// 名字过长
if(p1 – p > FSLITE_MAX_NAME_LEN)
return NULL;
strncpy(buf, p, p1 – p);
p = p1 + 1;

}else
{
if(strlen(p) > FSLITE_MAX_NAME_LEN )
return NULL;
strcpy(buf, p);
p += strlen(p); // 将p指到字符串最后，结束循环
}

//printf(”%s\n”, buf);

// 在node下面查找 buf 子项
if((node=fslite_inode_findentry(buf, node)) == NULL)
return NULL;
}

return node;
}

/* fn 是绝对路径
** 如果fn存在，则返回本文件的对应的节点
** 如果fn不是绝对路径，返回null
** 如果fn是 “/”，则返回根节点
*/
fslite_inode *fslite_inode_findfile(char *name)
{
// 不是绝对路径
if(strncmp(name, FSLITE_SEPARATOR, strlen(FSLITE_SEPARATOR)))
return NULL;

if(strcmp(name, FSLITE_SEPARATOR)==0) // ‘/’
return root;

return fslite_inode_findfile_relative(name+1, root);
}

/* inode为一个文件, 从buf中读取，写入blocksize个字节到文件p位置offset处
** 如果不能分配新页面，空间不足，会尽力而为，复制到哪里算哪里
*/
int fslite_inode_write(void *buf, msize_t blocksize, loff_t offset, fslite_inode *p)
{

atomic_t startentry, endentry, n;
int startentry_offset, endentry_offset;

atomic_t ientry;
atomic_t old_nentry;

int windowstart, windowlen;
msize_t remainlen;

unsigned char * start;

if(offset p->size)
return FSLITE_ERR;

// 要写入的位置，第b个entry，块内偏移o
startentry = offset / FSLITE_BLOCKSIZE;
startentry_offset = offset % FSLITE_BLOCKSIZE;

// 写结束位置
endentry = (blocksize + offset) / FSLITE_BLOCKSIZE;
endentry_offset = (blocksize + offset) % FSLITE_BLOCKSIZE;

windowstart = startentry_offset;
windowlen = FSLITE_BLOCKSIZE – windowstart;
remainlen = blocksize;

old_nentry = p->nentry;

/* 特殊一定可以包含于一般之中，普遍地代码是适应的
** 只不过需要处理一下例外的情况，多几个if
*/
for(ientry=startentry; ientry = p->nentry )
{
n = fslite_block_get();
if(n = old_nentry )
p->size += remainlen;

memcpy(start, (unsigned char *)buf + blocksize – remainlen, remainlen);
break;
}
if(ientry >= old_nentry )
p->size += windowlen;

memcpy(start, (unsigned char *)buf + blocksize -remainlen, windowlen);
remainlen -= windowlen;
windowlen = FSLITE_BLOCKSIZE;
windowstart = 0;

}

return FSLITE_OK;
}

/* 从文件p 的位置offset开始读 blocksize大小一块数据到buf中
**
*/
int fslite_inode_read(void *buf, msize_t blocksize, loff_t offset, fslite_inode *p)
{

atomic_t startentry, endentry;
int startentry_offset, endentry_offset;

atomic_t ientry;

int windowstart, windowlen;
msize_t remainlen;

unsigned char * start;

if(offset p->size)
offset = p->size;

startentry = offset / FSLITE_BLOCKSIZE;
startentry_offset = offset % FSLITE_BLOCKSIZE;

endentry = (blocksize + offset) / FSLITE_BLOCKSIZE;
endentry_offset = (blocksize + offset) % FSLITE_BLOCKSIZE;

windowstart = startentry_offset;
windowlen = FSLITE_BLOCKSIZE – windowstart;
remainlen = blocksize;

for(ientry=startentry; ientry = FSLITE_MAX_OPENFILES)
{
printf(”ERR: you can’t open too much file together\n”);
return NULL;
}

// 文件如果不存在，就建立一个，但是父目录应该存在
if(strcmp(mode, “wb+”)==0)
{
sp = strrchr(name, FSLITE_SEPARATOR[0]);
if(sp == name)
p = root;
else
{
//path过长
if(sp -name > FSLITE_MAX_PATH_LEN )
return NULL;

memset(path, 0, FSLITE_MAX_PATH_LEN+1);
strncpy(path, name, sp-name);
printf(”path: %s file: %s\n”, path, sp+1);
p = fslite_inode_findfile(path);
}

if(p==NULL) //上级目录不存在
return NULL;

p = fslite_inode_createfile(sp+1, p, FSLITE_FILE);

if(p==NULL) // 创建失败
return NULL;
}else{
// wb , rb读模式，如果文件不存在则返回
if( (p=fslite_inode_findfile(name)) == NULL)
return NULL;

if(p->type!=FSLITE_FILE)
return NULL;
}

fp= &files[++nopenfiles];
fp->fd = nopenfiles;
fp->sb = sb;
fp->inode = p;

if(strcmp(mode, “rb”)==0)
{
fp->fp = 0;
fp->mode = FSLITE_FOPEN_R;
}
else
{ // wb wb+，写入
fp->fp = p->size;
fp->mode = FSLITE_FOPEN_RW;
}
return fp;
}

/*往fp中写入n个块，每块大小为blocksize*/
msize_t fslite_fwrite(void * buf, msize_t blocksize, msize_t n, fslite_file *fp)
{
int i;

if(fp==NULL)
return 0;

if(fp->mode==FSLITE_FOPEN_R)
return 0;

for(i=0; i fp, fp->inode) != FSLITE_OK)
break;

fp->fp +=blocksize;

}
return i;
}

/*往buf中读入n个块，每块大小为blocksize*/
msize_t fslite_fread(void * buf, msize_t blocksize, msize_t n, fslite_file *fp)
{

int i;

if(fp==NULL)
return 0;

for(i=0; i fp, fp->inode);
if(fp->fp >= fp->inode->size)
{
fp->fp = fp->inode->size;
break;
}
fp->fp +=blocksize;
}
return i;
}

int fslite_rewind(fslite_file *fp)
{
fp->fp = 0;
return FSLITE_OK;
}

int fslite_feof(fslite_file *fp)
{
if(fp->fp >= fp->inode->size)
return 1;
else
return 0;
}

int fslite_fclose(fslite_file *fp)
{
if(nopenfiles > 0)
nopenfiles — ;
return FSLITE_OK;
}

int fslite_fseek(fslite_file *fp, loff_t offset, int where)
{
if(where == FSLITE_SEEK_CUR)
{
fp->fp += offset;
}

if(where == FSLITE_SEEK_SET)
{
fp->fp = offset;
}

if(where == FSLITE_SEEK_END)
{
fp->fp = fp->inode->size + offset;
}

if(fp->fp fp=0;

if(fp->fp > fp->inode->size)
fp->fp=fp->inode->size;

return FSLITE_OK;
}

loff_t fslite_ftell(fslite_file *fp)
{
if(fp==NULL)
return 0;
else
return fp->fp;
}

fslite_dir * fslite_opendir(char *name)
{

fslite_inode *p;
fslite_dir *dp;

// 达到上限
if(nopendirs >= FSLITE_MAX_OPENDIRS)
{
printf(”ERR: you can’t open too much dir together\n”);
return NULL;
}

if( (p=fslite_inode_findfile(name)) == NULL)
return NULL;

if(p->type!=FSLITE_DIR)
return NULL;

dp = &dirs[nopendirs++];
//dp->fd = nopenfiles;
dp->sb = sb;
dp->inode = p;
dp->dp = 0;

return dp;
}

int fslite_closedir(fslite_dir *p)
{
if(nopendirs > 0)
nopendirs — ;
return FSLITE_OK;
}

char *fslite_readdir(fslite_dir *p)
{
fslite_inode *n;
if(p->dp

inode->nentry){
n = FSLITE_INODEADDR(fslite_inode_getentry(p->dp, p->inode));
p->dp++;
return n->name;
}
return NULL;
}

int fslite_rewinddir(fslite_dir *p)
{
p->dp = 0;
return FSLITE_OK;
}

int fslite_mkdir(char *name)
{
fslite_inode *p;
char * sp;
char path[FSLITE_MAX_PATH_LEN+1];

// 不是绝对路径
if(strncmp(name, FSLITE_SEPARATOR, strlen(FSLITE_SEPARATOR)))
return FSLITE_ERR;

sp = strrchr(name, FSLITE_SEPARATOR[0]);
if(sp == name)
p = root;
else
{
//path过长
if(sp -name > FSLITE_MAX_PATH_LEN )
return FSLITE_ERR;

memset(path, 0, FSLITE_MAX_PATH_LEN+1);
strncpy(path, name, sp-name);
printf(”path: %s file: %s\n”, path, sp+1);
p = fslite_inode_findfile(path);
}

if(p==NULL) //上级目录不存在
return FSLITE_ERR;

if(fslite_inode_createfile(sp+1, p, FSLITE_DIR)==NULL)
return FSLITE_ERR;
else
return FSLITE_OK;
}

/* main ***************************************************************
*/

main()
{
FILE *fp;

fslite_inode *p;

fslite_file *f;
fslite_dir *d;

char *n;

char *s=”/test/b/hello/world/this/is/a/what/are/you/doing”;

char *test=”This is the first text of the first file in the first fslite file system\nnkchenz@gmail.com”;

char buf[256];

fslite_fs_init();

fslite_mkdir(”/hello”);

fslite_mkdir(”/hello/1″);
fslite_mkdir(”/hello/2″);
fslite_mkdir(”/hello/3″);

d=fslite_opendir(”/hello”);
while(1)
{
n=fslite_readdir(d);
if(n==NULL) break;
printf(” %s\n”, n);
}
fslite_closedir(d);

if((f=fslite_fopen(”/test”, “wb+”))==NULL)
{
printf(”err\n”);
}
else{
printf(”ok\n”);

fslite_fwrite(test, strlen(test), 1, f);

fslite_fwrite(s, strlen(s), 1, f);

fslite_rewind(f);

fslite_fread(buf, 256, 1, f);

printf(”%s\n”, buf);

if(fslite_feof(f))
printf(”feof\n”);

fslite_fclose(f);

fslite_fdelete(”/test”);

}

/*
if(fslite_inode_createfile(”hello”, root, FSLITE_DIR))
printf(”CREATE: /hello\n”);

if(p=fslite_inode_createfile(”test”, root, FSLITE_FILE))
printf(”CREATE: /test\n”);

if(p2=fslite_inode_createfile(”test2″, root, FSLITE_DIR))
printf(”CREATE: /test2\n”);

if(fslite_inode_deletefile(p)!=FSLITE_OK)
printf(”del err”);
else
printf(”del ok”);

if(fslite_inode_deletefile(p2)!=FSLITE_OK)
printf(”del err”);
else
printf(”del ok”);

p=fslite_inode_findfile(”/hello”);
if(fslite_inode_createfile(”world”, p, FSLITE_DIR))
printf(”CREATE: /hello/world\n”);
*/

s=”/hello”;
if( (p=fslite_inode_findfile(s)) == NULL )
printf(”Not Found: %s \n”, s);
else
printf(”Found: %s \n”, s);

/*测试代码, 将文件系统映象输出到文件*/
fp=fopen(”fslite.img”, “wb+”);
fwrite(fslite_data, FSLITE_TOTAL_BLOCKS * FSLITE_BLOCKSIZE, 1, fp);
fclose(fp);

printf(”blocks: %d/%d root: %d first_freeblock:%d\n”, sb->used_blocks, sb->free_blocks, sb->root_block, sb->first_freeblock);

}

google的picasa相册, 需要先注册一个帐号，然后下载最新的picasa软件，就轻松发布自己机器上的相片了^_^
http://picasaweb.google.com/

我的相册http://picasaweb.google.com/nkchenz/

发布截图

Linux系统， Fedora Core release 4

1 skyeye
下载skyeye
wget http://gro.clinux.org/frs/download.php/1545/skyeye-1.2-RC7-3.tar.bz2

解压
tar jxvf skyeye-1.2-RC7-3.tar.bz2

切换到skyeye-v1目录，如果没有装X，则不编译LCD
make NO_LCD=1

编译完成之后，将skyeye可执行文件cp到路径里面
cp binary/skyeye /bin

2 安装arm交叉编译工具
wget http://uclinux.org/pub/uClinux/arm-elf-tools/arm-elf-tools-20030314.sh
chmod +x arm-elf-tools-20030314.sh
./arm-elf-tools-20030314.sh

3 ucos
下载ucosforskyeye
wget http://gro.clinux.org/frs/download.php/1004/ucosii4skyeye-1.9.3.tar.gz

解压
tar zxvf ucosii4skyeye-1.9.3.tar.gz

切换到目录
cd ucosii4skyeye

修改lib/skyeye_printf.c，添加isdigit函数定义，否则会出错
int isdigit(int c)
{
if( c >= ‘0′ && c <= ‘9′)
return 1;
return 0;
}

然后编译即可
make

完成之后，sample目录即含有可以运行模拟的ucos的映象了。
cd samples/ucos_test
skyeye -e usoc_test.elf
显示了有两个task运行时的ucos

main_entry.c是这个例子的代码

定律一：如果一个年高德劭的杰出科学家说，某件事情是可能的，那他可能是正确的；但如果他说，某件事情是不可能的，那他也许是非常错误的

定律二：要发现某件事情是否可能的界限，唯一的途径是跨越这个界限，从不可能跑到可能中去

定律三：任何非常先进的技术，初看都与魔法无异

从任何实例来看，具体细节是永远无法知道的，即使知道，也由于比人的理解力复杂几百万倍而无法为人所理解。

你的理论是疯狂的——但还没疯狂到不真实的程度
尼尔斯·博尔1885—1962，丹麦物理学家

人生最大的骄傲，就是在成年时实现童年的梦想

2001 space oddesy, 越看越有一种宿命的感觉。上帝是存在，但不是christ。他是一种比人类更加高级的智慧生命，高级到可以控制人的命运以及其他许多不能为人类控制的东西。如果真的有那么一天，又会怎样？不知道能够从它们哪里偷学到多少？

关于Isaac Asimov
你们的科学，这简直是事实的堆砌。由勉强算作理论的东西把它们连在一起。这一切简直太肤浅了，未心值得为它们下功夫。使我感兴趣的倒是你们的小说，人们的欲望和感情的交织和互相影响。—-RB-34

它足够聪明能够犯极其复杂的错误，但不够聪明能帮助我们找出错误所在——机器智能的尴尬

逻辑左移SHL、算术左移指令SAL， 低位补0。逻辑右移SHR 高位补0；SAR算术右移，高位不变，相当于符号位扩展。

带进位的加法器完成多字节加法，带进位的移位器完成多字节移位。

模的运算 a%b  = a - a / b * b，模的符号与被除数的相同

cisc: 一个指令即可以完成很复杂的操作，尽量少的汇编语句完成一件事情是其原则
risc: 许多指令都是单周期的指令，每个指令完成的事情都很简单，都是基本的，常用的指令。这些基本指令的组合起来可以完成很复杂的事情。简单的指令使得电路更简单、利用率更高

有符号乘法运算
4*4，积是8位
         1101
             0011
--------------
      1111 1101
      1111 101
      0000 00
      0000 0 ++++++++减，符号位

对部分积进行符号扩展到乘积的位数，被乘数的最后一位也就是符号位的部分积要减去
A=-A[n-1]*2^(n+1) + A[n-2]*2^(n-2) + ... + A[0]*2^0
A*B

判断是否溢出
无符号数x，y， 如果x+y小于其中之一，肯定溢出
有符号数x，y， 如果x，y均为负数，其和却不为负数，则发生负溢出。若x，y均为正数，其和却为负数，则发生正溢出。

-------------利用循环移位方法计算无符号数除法------------------------
;R00被除数高16位，R02低16位， R04除数不能为0，结果商放R02中，R00为余数
math_div:
       cmp     R04, 0x0
       jz      math_div_over; 除数为0

       cmp    R00,R04
       jnc    over                 ;若高位字大于等于除数，则会溢出
     mov    R5e, 16              ;循环次数

math_div_loop:
       clrb7 flag                  ;清进位标志位
     rcl   R02
       rcl   R00

       jnzb7 flag, math_div_add

       cmp   R00, R04              ;在移出是0的情况下比较是否够减
     jc    math_div_noadd

math_div_add:
       sub   R00, R04;够减，商加1，保存余数
     inc   R02

math_div_noadd:;不够减的情况
     djnz   R5e, math_div_loop   ;循环16次进行求商

     clrb4  flag                 ;清溢出标志位
     jp     math_div_ok
math_div_over:
       setb4  flag                 ;置溢出标志位
math_div_ok:
        ret

;乘法
;R00存放16位被乘数，R02存放16位乘数，R04乘积高16位，R06乘积低16位
math_mul:

	mov R04, 0
	mov R06, 0
	mov R5e, 16
math_mul_loop:
            clrb7 flag
	rcl R06
	rcl R04          

	rcl R02
	jnc math_mul_noadd
            add R06, R00

math_mul_noadd:
            djnz R5e, math_mul_loop

         ret

空间P={p1, p2, ..., pL}
各元素没有公约数GCD(pi, pj)=1, for i!=j

空间的大小 M=p1*p2*...*pL, 表示范围 [0, M)

数X的RNS表示就是 X在空间p上的投影
(x1, x2, ..., xL),  xi= X mod pi

signed RNS 表示范围 (-M/2, M/2]
如果X>0, xi= X mod pi 否则 (M - |x|) mod pi

运算 Z = X @ Y，zi = (xi@yi) mod pi

整数到RNS的转换
X的二进制形式，每一位权值为 2^n, 相对于pi的模为 2^n mod pi，把所有位的模加起来再mod pi，即得该数在pi方向上的投影分量.

X的补码形式，n位为符号位
X=(BnBn-1...B1B0) = -Bn * 2^n + (+, j=0, j=n-1, Bj*2^j)
Xi=X mod pi
  =( Bn*(pi-(2^n mod pi)) + (+, j=0, j=n-1, Bj*(2^j mod pi)) ) mod pi

RNS到整数的转换
中国剩余定理
si = M/pi
ti是si模pi的逆
(si*ti) mod pi =1

X=0
for i=1 to L
	X += si * [ Xi*ti mod pi ]
X= X mod M

难点在于：
大小比较
除法
base extension
scaling， rounding，truncat

使用make menuconfig命令对内核功能进行配置。去掉默认配置中许多不必要的选项，只选择最基本最必需的功能built-in到内核当中，其他功能配置为模块方式，保持基本内核最小，这样，可以极大的缩短内核编译时间，也可以方便以后对配置进行更改。每次只需要重新编译更改的模块即可，而不是对整个内核进行重新编译。

使用make bzImage 快速编译基本内核，将在cpu架构下面生成使用bzip压缩的内核映象如arch/i386/boot/bzImage，这个文件一般被复制到/boot目录，命名为vmlinuz-version文件，作为内核的启动文件。

使用mkinitrd生成初始化文件系统initrd-version.img，在系统的初始阶段提供一些必须的文件。

使用make modules 编译模块，标准内核模块一般放在/lib/modules/version目录下面，使用make modules_install可以把编译完成的内核模块复制到该目录。

编译过程会生成System.map文件，该文件存有内核映象所有符号的入口地址，便于其他程序进行调试之用，一般都复制到boot目录下面。2.5以后的内核提供把内核符号地址编入映象的功能。

启动的时候真正起作用的就是vmlinuz-version, initrd-version.img这两个文件。计算机上电后，启动lilo或者grub，它们知道这两个文件存在什么地方，将其装载到内存当中运行，就可以启动内核了。

data alignment

struct 每个元素都对齐， 整体按照最长元素对齐

例如：

struct animal_struct {
        char dog;             /* 1 byte */
        unsigned long cat;    /* 4 bytes */
        unsigned short pig;   /* 2 bytes */
        char fox;             /* 1 byte */
};
编译为
struct animal_struct {
        char dog;             /* 1 byte */
        u8 __pad0[3];         /* 3 bytes */
        unsigned long cat;    /* 4 bytes */
        unsigned short pig;   /* 2 bytes */
        char fox;             /* 1 byte */
        u8 __pad1;            /* 1 byte */
};

判断endian字节顺序

int x = 1;
if (*(char *)&x == 1)//取x地址的第一个字节
    /* little endian */
else
    /* big endian */

From physics, entropy is a measurement of disorder and randomness in a system
——Shannon entropy

John von Neumann (December 28, 1903February 8, 1957)
game theory, Neumann algebras, and the von Neumann bottleneck.

最后，作者推荐了一本书Expert C Programming。推荐语是：
关于C的一些鲜为人知的细节的深入讨论，Peter非常具有幽默感，整本书废话很多，不过我喜欢。
作者这样说太有意思了哈哈我也喜欢这本书！！！
Peter van der Linden . Expert C Programming. Prentice Hall, 1994. A great discussion on some of the less understood details in C. The author has a wonderful sense of humor and the book is rife with nonsense. I love it.

Threads are regular processes to the kernel that merely share certain resources

如果一个进程访问无效的内存区域, 或者非法访问一个内存区域, 就会引发 segmentation fault而被内核杀死。

kernel thread没有自己的地址空间, 它根据上一个进程的mm, pagetables 来获得内核地址的一些信息。

vm_area_struct 虚拟内存块，范围是 [vm_start, vm_end)，不同块不可以重叠。vmflag: 读写执行权限, 是否可以共享, 增长, 锁, io映射, 顺序, 随机访问, 是否为shm, 是否可swap。

int main(int argc, char *argv[])
{
        return 0;
}

该程序的内存映射
rml@phantasy:~$ pmap 1426
example[1426]
00e80000 (1212 KB)     r-xp (03:01 208530)   /lib/tls/libc-2.3.2.so
00faf000 (12 KB)       rw-p (03:01 208530)   /lib/tls/libc-2.3.2.so
00fb2000 (8 KB)        rw-p (00:00 0)
08048000 (4 KB)        r-xp (03:03 439029)   /home/rml/src/example
08049000 (4 KB)        rw-p (03:03 439029)   /home/rml/src/example
40000000 (84 KB)       r-xp (03:01 80276)    /lib/ld-2.3.2.so
40015000 (4 KB)        rw-p (03:01 80276)    /lib/ld-2.3.2.so
4001e000 (4 KB)        rw-p (00:00 0)
bfffe000 (8 KB)        rwxp (00:00 0)        [ stack ]
mapped: 1340 KB        writable/private: 40 KB     shared: 0 KB

前三行是libc.so的text, data, bss段. 接着是本例的text, data段.然后是动态链接器ld的text, data, bss段, 最后一行为本进程的stack，设备号00:00 0的内存全部被初始化为0。

在一个进程的内存描述符中查找一个特定的地址find_vma()，结果存放于cache之中, 方便下次使用。
if (vma)
mm->mmap_cache = vma;

pcb的mm成员就是该进程的地址空间映射表。

unsigned long do_mmap(struct file *file, unsigned long addr,
unsigned long len, unsigned long prot,
unsigned long flag, unsigned long offset)
内核映射一个新的内存块. 如果该块和已有的块临近且属性相同, 内核执行merge操作。如果file为null, 则成为anonymous mapping，addr指明开始映射的地址。

void * mmap2(void *start,
size_t length,
int prot,
int flags,
int fd,
off_t pgoff)
最后一个偏移量的单位变为page, 可以映射更大的文件

虚拟地址通过三级页表转换为物理地址
page global directory (PGD), 存在于mm之中
page middle directory (PMD)
page table

filesystem 层次化存储数据的地方。 包含文件、目录、相关控制信息。典型操作创建、删除、挂载。一个文件系统可以挂载全局namespace的任何地方。有没有非层次化的文件系统？直接使用数据库做文件系统？superblock 含有整个文件系统的信息。

dirty page回写
使用一个结构 address_space 来存放所有page的缓冲信息。所有的page 读写io都经过page cache, 一个
文件信息先经过vma转换为物理地址page, 然后查看page cache, 然后使用bio模块完成io请求。

pdflush 将dirty page写会磁盘, 当系统内存低于一定限度dirty_background_ratio 的时候回收内存。系统初始化的时候会启动一个定时器, 定时wb_kupdate() 一个pdflush内核线程, 写回过旧的pages。laptop写回模式, 每次超时时全部写回所有dirty页面，而不是频繁的写回。

允许多个pdflush线程存在, 动态生成, 最大8, 最小2. 如果所有的pdflush busy超过1s, 说明io繁忙，就启动一个新线程. 如果一个pdflush 睡眠的时间超过1s, 那么就终止它。这样多个线程就可以同时使多个磁盘保持饱和工作状态，对于磁盘阵列很有利。

I/O scheduler
对io请求进行merge和sort，最小化磁头定位寻道时间，优化整体性能，对于个别请求可能非常不公平。

linus电梯算法: 磁头朝着一个方向移动, 然后向相反方向移动
1 如果请求的sector和队列中的临近, 则合并请求
2 如果队列中有请求超过了一定时间, 则新请求被添加到队列尾部
3 如果可能, 则把请求插入到队列中合适的位置, 保持队列sector的物理顺序
4 否则的话, 添加到尾部

写入操作一般是和程序执行异步的，程序一般不在乎何时真正写入磁盘，但程序往往等待读操作的返回，读操作是同步的。所以，读、写操作应该有不同的相应时间才合理。

deadline io scheduler
超时读操作500ms, 写操作5s. 三个队列, 正常处理sort queue, 对于超时的read, write fifo特殊处理
read fifo
write fifo —–> dispatch queue —> disk
sorted queue

Anticipatory I/O scheduler
同deadline不同之处在于每次处理完读请求之后, 不是立即返回, 而是等待几个微妙在这段时间内, 任何来自临近区域的请求都被立即执行. 超时以后, 继续原来的处理.基于下面的假设: 几个微妙内, 程序有很大机会提交另一次请求.调度器跟踪每个进程的io读写统计信息, 以获得最佳预期

Complete Fair Queuing (CFQ) I/O scheduler 多媒体应用, 总能保证audio、video及时从磁盘读取数据。但对于其他各类应用表现也很好。每个进程一个queue，每个queue按照上述规则进行merge和sort。进程之间round robin调度，每次执行一个进程的4个请求。

Noop I/O scheduler 仅对请求进行merge, 适用于随机存取设备, no seek cost，非机械可随机寻址的磁盘。