// Allocate a page to hold the disk block
int
map_block(uint32_t blockno)
{
	if (block_is_mapped(blockno))
		return 0;
	return sys_page_alloc(0, diskaddr(blockno), PTE_U|PTE_P|PTE_W);
}

// Set *blk to point at the filebno'th block in file 'f'.
// Allocate the block if it doesn't yet exist.
// Returns 0 on success, < 0 on error.
int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{
	int r;
	uint32_t diskbno;

	// Read in the block, leaving the pointer in *blk.
	// Hint: Use file_map_block and read_block.
	// LAB 5: Your code here.
	r = file_map_block(f, filebno, &diskbno, 1);
	if (r)
		return r;

	// If the block is already mapped we return it
	// instead of reading the block from disk again.
	// XXX: I'm not sure whether this is the right
	// thing to do, however, looks like lab5 says
	// to do that (p. 7).
	if (block_is_mapped(diskbno)) {
		if (blk)
			*blk = diskaddr(diskbno);
		return 0;
	}

	return read_block(diskbno, blk);
}

// Make sure a particular disk block is loaded into memory.
// Returns 0 on success, or a negative error code on error.
// 
// If blk != 0, set *blk to the address of the block in memory.
//
// Hint: Use diskaddr, map_block, and ide_read.
static int
read_block(uint32_t blockno, char **blk)
{
	int r;
	char *addr;

	if (super && blockno >= super->s_nblocks)
		panic("reading non-existent block %08x\n", blockno);

	if (bitmap && block_is_free(blockno))
		panic("reading free block %08x\n", blockno);

	// LAB 5: Your code here.
	addr = diskaddr(blockno);
	if (block_is_mapped(blockno)) {
		goto succeeded;
	}

	// now that the block is not in memory, allocate memory and read it in.
	if ((r = map_block(blockno)) < 0)
		return r;
	if ((r = ide_read(blockno * BLKSECTS, addr, BLKSECTS)) < 0)
		return r;

succeeded:
	if (blk)
		*blk = addr;
	return 0;
}

// Flush the contents and metadata of file f out to disk.
// Loop over all the blocks in file.
// Translate the file block number into a disk block number
// and then check whether that disk block is dirty.  If so, write it out.
void
file_flush(struct File *f)
{
	int i;
	uint32_t *pdiskbno;

	for (i = 0; i < (f->f_size + BLKSIZE - 1) / BLKSIZE; i++) {
		if (file_block_walk(f, i, &pdiskbno, 0) < 0 ||
		    pdiskbno == NULL || *pdiskbno == 0)
			continue;
		flush_block(diskaddr(*pdiskbno));
	}
	flush_block(f);
	if (f->f_indirect)
		flush_block(diskaddr(f->f_indirect));
}

int
fs_rmdir(const char *path)
{
	struct inode *dir;
	struct dirent *dent;
	uint32_t nblock, i, j;
	char *blk;
	int r;

	if ((r = inode_open(path, &dir)) < 0)
		return r;
	if (dir == diskaddr(super->s_root))
		return -EPERM;
	if (!S_ISDIR(dir->i_mode))
		return -ENOTDIR;

	nblock = dir->i_size / BLKSIZE;
	for (i = 0; i < nblock; i++) {
		if ((r = inode_get_block(dir, i, &blk)) < 0)
			return r;
		dent = (struct dirent *)blk;
		for (j = 0; j < BLKDIRENTS; ++j)
			if (dent[j].d_name[0] != '\0')
				return -ENOTEMPTY;
	}
	return inode_unlink(path);
}

// Make sure a particular disk block is loaded into memory.
// Returns 0 on success, or a negative error code on error.
// 
// If blk != 0, set *blk to the address of the block in memory.
//
// Hint: Use diskaddr, map_block, and ide_read.
static int
read_block(uint32_t blockno, char **blk)
{
	int r;
	char *addr;

	if (super && blockno >= super->s_nblocks)
		panic("reading non-existent block %08x\n", blockno);

	if (bitmap && block_is_free(blockno))
		panic("reading free block %08x\n", blockno);
	
	addr = diskaddr(blockno);
    if(!block_is_mapped(blockno)){
        if((r = map_block(blockno)) < 0)
            return r;
        r = ide_read(blockno*BLKSECTS, (void *)addr, BLKSECTS);
        if(r < 0)
            return r;
    }
    if(blk)
        *blk = addr;
	
	return 0;
}

// Set *blk to the address in memory where the filebno'th
// block of file 'f' would be mapped.
//
// Returns 0 on success, < 0 on error.  Errors are:
//	-E_NO_DISK if a block needed to be allocated but the disk is full.
//	-E_INVAL if filebno is out of range.
//
// Hint: Use file_block_walk and alloc_block.
int
file_get_block(struct File *f, uint32_t filebno, char **blk)
{
       // code for lab 5- M.G
       //      panic("file_get_block not implemented");

    uint32_t *ppdiskbno;
    uint32_t new_block_no;

    int return_value;    

    if ((return_value = file_block_walk(f, filebno, &ppdiskbno,true)) < 0)
    {
        return return_value;
    }    

    if (!*ppdiskbno)
    {
		if ((new_block_no = alloc_block()) < 0)
        {
			return -E_NO_DISK;
        }
	    *ppdiskbno = new_block_no;
    }   
    
    *blk = diskaddr(*ppdiskbno);

    return 0;
}

// Read and validate the file system bitmap.
//
// Read all the bitmap blocks into memory.
// Set the "bitmap" pointer to point at the beginning of the first
// bitmap block.
// 
// Check that all reserved blocks -- 0, 1, and the bitmap blocks themselves --
// are all marked as in-use
// (for each block i, assert(!block_is_free(i))).
//
// Hint: Assume that the superblock has already been loaded into
// memory (in variable 'super').  Check out super->s_nblocks.
void
read_bitmap(void)
{
	int r;
	uint32_t i;

	// Read the bitmap into memory.
	// The bitmap consists of one or more blocks.  A single bitmap block
	// contains the in-use bits for BLKBITSIZE blocks.  There are
	// super->s_nblocks blocks in the disk altogether.
	// Set 'bitmap' to point to the first address in the bitmap.
	// Hint: Use read_block.

	// LAB 5: Your code here.
	// bitmap blocks start at block 2.
	for (i = 0; i < (super->s_nblocks - 1) / BLKBITSIZE + 1; i++) {
		if ((r = read_block(i + 2, NULL)) < 0)
			panic("read_block for bitmap %d failed: %e.\n", i, r);
	}
	bitmap = (uint32_t *) diskaddr(2);

	// Make sure the reserved and root blocks are marked in-use.
	assert(!block_is_free(0));
	assert(!block_is_free(1));
	assert(bitmap);

	// Make sure that the bitmap blocks are marked in-use.
	// LAB 5: Your code here.
	for (i = 0; i < super->s_nblocks / BLKBITSIZE; i++)
		assert(!block_is_free(i + 2));
	cprintf("read_bitmap is good\n");
}

static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{
	if (filebno >= NDIRECT + NINDIRECT) {
		return -E_INVAL;
	}
	uint32_t nblock = f->f_size / BLKSIZE;
	if (filebno > nblock) {
		return -E_NOT_FOUND;
	}
	if (filebno < NDIRECT) {
		*ppdiskbno = &f->f_direct[filebno];
		return 0;
	}
	else {
		if(!f->f_indirect) {
			return -E_NOT_FOUND;
		}
		uint32_t* index = (uint32_t*)diskaddr(f->f_indirect);
		*ppdiskbno = &index[filebno - NDIRECT] ;
	}
	return 0;
    // LAB 5: Your code here.
	// panic("file_block_walk not implemented");
}

// Make sure a particular disk block is loaded into memory.
// Returns 0 on success, or a negative error code on error.
// 
// If blk != 0, set *blk to the address of the block in memory.
//
// Hint: Use diskaddr, map_block, and ide_read.
static int
read_block(uint32_t blockno, char **blk)
{
	int r;
	char *addr;

	if (super && blockno >= super->s_nblocks)
		panic("reading non-existent block %08x\n", blockno);

	if (bitmap && block_is_free(blockno))
		panic("reading free block %08x\n", blockno);

	// LAB 5: Your code here.
	r = map_block(blockno);
	if (r)
		return r;

	addr = diskaddr(blockno);
	r = ide_read(blockno * BLKSECTS, addr, BLKSECTS);
	if (r)
		return r;

	if (blk)
		*blk = addr;

	return sys_page_map(0, addr, 0, addr, vpt[VPN(addr)] & PTE_USER);
}

// Sync the entire file system.  A big hammer.
void
fs_sync(void)
{
	int i;
	for (i = 1; i < super->s_nblocks; i++)
		flush_block(diskaddr(i));
}

// Make sure a particular disk block is loaded into memory.
// Returns 0 on success, or a negative error code on error.
// 
// If blk != 0, set *blk to the address of the block in memory.
//
// Hint: Use diskaddr, map_block, and ide_read.
static int
read_block(uint32_t blockno, char **blk)
{
	int r;
	char *addr;

	if (super && blockno >= super->s_nblocks)
		panic("reading non-existent block %08x\n", blockno);

	if (bitmap && block_is_free(blockno))
		panic("reading free block %08x\n", blockno);

	// LAB 5: Your code here.
	addr = diskaddr(blockno);
	int error = map_block(blockno);
	if(error<0) return error;

	int secno = blockno*BLKSECTS;
	error = ide_read(secno, addr, (size_t)BLKSECTS);
	if(error) return error;

	if(blk) *blk = addr;
	// panic("read_block not implemented");

	return 0;
}

// Copy the current contents of the block out to disk.
// Then clear the PTE_D bit using sys_page_map.
// Hint: Use ide_write.
// Hint: Use the PTE_USER constant when calling sys_page_map.
void
write_block(uint32_t blockno)
{
	char *addr;
	if (!block_is_mapped(blockno))
		panic("write unmapped block %08x", blockno);
	
	// Write the disk block and clear PTE_D.
	// LAB 5: Your code here.

	// We will use the VM hardware to keep track of whether a 
	// disk block has been modified since it was last read from 
	// or written to disk. To see whether a block needs writing, 
	// we can just look to see if the PTE_D "dirty" bit is set 
	// in the vpt entry.
	addr = diskaddr(blockno);
	if(!va_is_dirty(addr)) return;

	
	int error;
	int secno = blockno*BLKSECTS;
	error = ide_write(secno, addr, BLKSECTS);
	if(error<0) panic("write block error on writing");

	int env_id = sys_getenvid();
	error = sys_page_map(env_id, addr, 
		env_id, addr, ((PTE_U|PTE_P|PTE_W) & ~PTE_D));
	if(error<0) panic("write block error on clearing PTE_D");



	// panic("write_block not implemented");
}

// Search the bitmap for a free block and allocate it.  When you
// allocate a block, immediately flush the changed bitmap block
// to disk.
//
// Return block number allocated on success,
// -E_NO_DISK if we are out of blocks.
//
// Hint: use free_block as an example for manipulating the bitmap.
int
alloc_block(void)
{
	// The bitmap consists of one or more blocks.  A single bitmap block
	// contains the in-use bits for BLKBITSIZE blocks.  There are
	// super->s_nblocks blocks in the disk altogether.

	// code for lab 5 -M.G
    //	panic("alloc_block not implemented");

    uint32_t i,j;
    for (i = 0; i < super->s_nblocks/32; i++)
    {
    	for (j = 0; j < 32; j++) 
        {
    	    uint32_t mark_bit = (1 << j);
    	    if (bitmap[i] & mark_bit) 
            {
        		bitmap[i] &= ~mark_bit;
        		flush_block(diskaddr((i * 32 | j)/BLKBITSIZE + 2));
        		return (i * 32) | j;
    	    }
	    }
    }
    return -E_NO_DISK;
}

// Find the disk block number slot for the 'filebno'th block in file 'f'.
// Set '*ppdiskbno' to point to that slot.
// The slot will be one of the f->f_direct[] entries,
// or an entry in the indirect block.
// When 'alloc' is set, this function will allocate an indirect block
// if necessary.
//
// Returns:
//	0 on success (but note that *ppdiskbno might equal 0).
//	-E_NOT_FOUND if the function needed to allocate an indirect block, but
//		alloc was 0.
//	-E_NO_DISK if there's no space on the disk for an indirect block.
//	-E_INVAL if filebno is out of range (it's >= NDIRECT + NINDIRECT).
//
// Analogy: This is like pgdir_walk for files.  
// Hint: Don't forget to clear any block you allocate.
static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{
	// LAB 5: Your code here.
	//panic("file_block_walk not implemented");
	int result;

	if(filebno >= NDIRECT+NINDIRECT)
	{
		return -E_INVAL;
	}
	
	if(filebno < NDIRECT) 
	{
		if(ppdiskbno)
		{
			*ppdiskbno=(f->f_direct+filebno);
		}

		return 0;
	}

	if(!f->f_indirect && !alloc)
	{
		return -E_NOT_FOUND;
	}

	if(!f->f_indirect) 
	{
		if((result=alloc_block()) < 0)
		{
			return -E_NO_DISK;
		}

		f->f_indirect=result;
				
		memset(diskaddr(result), 0, BLKSIZE);
		flush_block(diskaddr(result));
	}
					
	if(ppdiskbno)
	{
		*ppdiskbno=(uint32_t *)diskaddr(f->f_indirect)+filebno-NDIRECT;
	}
			
	return 0;
}

// Find the disk block number slot for the 'filebno'th block in file 'f'.
// Set '*ppdiskbno' to point to that slot.
// The slot will be one of the f->f_direct[] entries,
// or an entry in the indirect block.
// When 'alloc' is set, this function will allocate an indirect block
// if necessary.
//
// Returns:
//	0 on success (but note that *ppdiskbno might equal 0).
//	-E_NOT_FOUND if the function needed to allocate an indirect block, but
//		alloc was 0.
//	-E_NO_DISK if there's no space on the disk for an indirect block.
//	-E_INVAL if filebno is out of range (it's >= NDIRECT + NINDIRECT).
//
// Analogy: This is like pgdir_walk for files.
// Hint: Don't forget to clear any block you allocate.
static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{	
	// Lab 5 ex 4
	// LAB 5: Your code here.
	if(!f || !ppdiskbno)
		return -E_INVAL;
	int new_block;
	void *blk_addr;
	uint32_t * index;
	if(filebno >= (NDIRECT + NINDIRECT))
		return -E_INVAL;

	if(filebno < 10)
	{
		*ppdiskbno = &(f->f_direct[filebno]);
		return 0;
	}
	else
	{
		filebno -= 10;
		if(f->f_indirect)
		{
			blk_addr = diskaddr((uint64_t)(f->f_indirect));
			index = (uint32_t *) blk_addr;
		        *ppdiskbno = (index + filebno); 	
			return 0;
		}
		else
		{
			if(alloc == 0)
				return -E_NOT_FOUND;
			new_block = alloc_block();
			if(new_block == -E_NO_DISK)
				return -E_NO_DISK;
			f->f_indirect = (uint32_t)new_block;
			blk_addr = diskaddr((uint64_t)(f->f_indirect));
                        index = (uint32_t *) blk_addr;
                        *ppdiskbno = (index + filebno);
			return 0;			
		}	
	}
	
	//panic("file_block_walk not implemented");
}

void
bc_init(void)
{
	struct Super super;
	set_pgfault_handler(bc_pgfault);

	// cache the super block by reading it once
	memmove(&super, diskaddr(1), sizeof super);
}

static void print_block_list()
{
       cprintf("\n");
       cprintf("==============block usage list==============\n");
       int i;
       for (i=0; i<MAXBLK; ++i)
               if (plist[i].valid)
                    cprintf("+block at %x, used %d times, last used at time %d\n", diskaddr(i), plist[i].count, plist[i].tstamp);
       cprintf("++++++++++++++++++end list++++++++++++++++++\n");
}

// Initialize the file system
void
fs_init(void)
{
	static_assert(sizeof(struct File) == 256);

       // Find a JOS disk.  Use the second IDE disk (number 1) if availabl
       if (ide_probe_disk1())
               ide_set_disk(1);
       else
               ide_set_disk(0);
	bc_init();

	// Set "super" to point to the super block.
	super = diskaddr(1);
	check_super();

	// Set "bitmap" to the beginning of the first bitmap block.
	bitmap = diskaddr(2);
	check_bitmap();
}

// Find the disk block number slot for the 'filebno'th block in file 'f'.
// Set '*ppdiskbno' to point to that slot.
// The slot will be one of the f->f_direct[] entries,
// or an entry in the indirect block.
// When 'alloc' is set, this function will allocate an indirect block
// if necessary.
//
// Returns:
//	0 on success (but note that *ppdiskbno might equal 0).
//	-E_NOT_FOUND if the function needed to allocate an indirect block, but
//		alloc was 0.
//	-E_NO_DISK if there's no space on the disk for an indirect block.
//	-E_INVAL if filebno is out of range (it's >= NDIRECT + NINDIRECT).
//
// Analogy: This is like pgdir_walk for files.
// Hint: Don't forget to clear any block you allocate.
static int
file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc)
{
       // code for lab 5-M.G
        //       panic("file_block_walk not implemented");

   	uint32_t new_block_no;

	if (filebno < NDIRECT) 
    {
		*ppdiskbno = &f->f_direct[filebno];
	}
    else if (filebno < (NDIRECT + NINDIRECT)) 
    {
		if (!f->f_indirect) 
        { 
			if (alloc == false)
            {
                return -E_NOT_FOUND;
            }
            else
            {        
            
			    if ((new_block_no = alloc_block()) < 0)
			    {
                	return -E_NO_DISK;
                }
            
			f->f_indirect = new_block_no;
			memset(diskaddr(new_block_no), 0, BLKSIZE);
            }
		} 
		*ppdiskbno = &((uintptr_t *) diskaddr(f->f_indirect))[filebno - NDIRECT];
	} 
    else 
    {
		return -E_INVAL;
    }

	return 0;
}