#include "filesys/inode.h"
-#include <bitmap.h>
#include <list.h>
#include <debug.h>
-#include <stdio.h>
+#include <round.h>
+#include <string.h>
#include "filesys/filesys.h"
+#include "filesys/free-map.h"
#include "threads/malloc.h"
-/* Number of direct sector pointers in an inode. */
-#define DIRECT_CNT ((DISK_SECTOR_SIZE - sizeof (off_t) - sizeof (size_t)) \
- / sizeof (disk_sector_t))
+/* Identifies an inode. */
+#define INODE_MAGIC 0x494e4f44
/* On-disk inode.
- It is exactly DISK_SECTOR_SIZE bytes long. */
+ Must be exactly DISK_SECTOR_SIZE bytes long. */
struct inode_disk
{
+ disk_sector_t start; /* First data sector. */
off_t length; /* File size in bytes. */
- size_t sector_cnt; /* File size in sectors. */
- disk_sector_t sectors[DIRECT_CNT]; /* Sectors allocated for file. */
+ unsigned magic; /* Magic number. */
+ uint32_t unused[125]; /* Not used. */
};
+/* Returns the number of sectors to allocate for an inode SIZE
+ bytes long. */
+static inline size_t
+bytes_to_sectors (off_t size)
+{
+ return DIV_ROUND_UP (size, DISK_SECTOR_SIZE);
+}
+
/* In-memory inode. */
struct inode
{
- list_elem elem; /* Element in inode list. */
+ struct list_elem elem; /* Element in inode list. */
disk_sector_t sector; /* Sector number of disk location. */
int open_cnt; /* Number of openers. */
bool removed; /* True if deleted, false otherwise. */
- struct inode_disk data; /* On-disk data. */
+ int deny_write_cnt; /* 0: writes ok, >0: deny writes. */
+ struct inode_disk data; /* Inode content. */
};
+/* Returns the disk sector that contains byte offset POS within
+ INODE.
+ Returns -1 if INODE does not contain data for a byte at offset
+ POS. */
+static disk_sector_t
+byte_to_sector (const struct inode *inode, off_t pos)
+{
+ ASSERT (inode != NULL);
+ if (pos < inode->data.length)
+ return inode->data.start + pos / DISK_SECTOR_SIZE;
+ else
+ return -1;
+}
+
/* List of open inodes, so that opening a single inode twice
returns the same `struct inode'. */
-struct list open_inodes;
-
-static struct inode *alloc_inode (disk_sector_t);
+static struct list open_inodes;
/* Initializes the inode module. */
void
list_init (&open_inodes);
}
-/* Allocates sectors from bitmap B for the content of a file
- whose size is LENGTH bytes, and returns a new `struct inode'
- properly initialized for the file.
- It is the caller's responsible to write the inode to disk with
- inode_commit(), as well as the bitmap.
- If memory or disk allocation fails, returns a null pointer,
- leaving bitmap B is unchanged. */
-struct inode *
-inode_create (struct bitmap *b, disk_sector_t sector, off_t length)
+/* Initializes an inode with LENGTH bytes of data and
+ writes the new inode to sector SECTOR on the file system
+ disk.
+ Returns true if successful.
+ Returns false if memory or disk allocation fails. */
+bool
+inode_create (disk_sector_t sector, off_t length)
{
- struct inode *idx;
- size_t sector_cnt;
+ struct inode_disk *disk_inode = NULL;
+ bool success = false;
- ASSERT (b != NULL);
ASSERT (length >= 0);
- /* Calculate number of sectors to allocate for file data. */
- sector_cnt = (length / DISK_SECTOR_SIZE) + (length % DISK_SECTOR_SIZE > 0);
- if (sector_cnt > DIRECT_CNT)
- return NULL;
-
- /* Allocate inode. */
- idx = alloc_inode (sector);
- if (idx == NULL)
- return NULL;
-
- /* Allocate disk sectors. */
- idx->data.length = length;
- while (idx->data.sector_cnt < sector_cnt)
- {
- size_t sector = bitmap_find_and_set (b);
- if (sector == BITMAP_ERROR)
- goto error;
-
- idx->data.sectors[idx->data.sector_cnt++] = sector;
- }
+ /* If this assertion fails, the inode structure is not exactly
+ one sector in size, and you should fix that. */
+ ASSERT (sizeof *disk_inode == DISK_SECTOR_SIZE);
- /* Zero out the file contents. */
- if (sector_cnt > 0)
+ disk_inode = calloc (1, sizeof *disk_inode);
+ if (disk_inode != NULL)
{
- void *zero_sector;
- size_t i;
-
- zero_sector = calloc (1, DISK_SECTOR_SIZE);
- if (zero_sector == NULL)
- goto error;
- for (i = 0; i < sector_cnt; i++)
- disk_write (filesys_disk, idx->data.sectors[i], zero_sector);
- free (zero_sector);
+ size_t sectors = bytes_to_sectors (length);
+ disk_inode->length = length;
+ disk_inode->magic = INODE_MAGIC;
+ if (free_map_allocate (sectors, &disk_inode->start))
+ {
+ disk_write (filesys_disk, sector, disk_inode);
+ if (sectors > 0)
+ {
+ static char zeros[DISK_SECTOR_SIZE];
+ size_t i;
+
+ for (i = 0; i < sectors; i++)
+ disk_write (filesys_disk, disk_inode->start + i, zeros);
+ }
+ success = true;
+ }
+ free (disk_inode);
}
-
- return idx;
-
- error:
- inode_remove (idx);
- inode_close (idx);
- return NULL;
+ return success;
}
/* Reads an inode from SECTOR
struct inode *
inode_open (disk_sector_t sector)
{
- list_elem *e;
- struct inode *idx;
+ struct list_elem *e;
+ struct inode *inode;
/* Check whether this inode is already open. */
for (e = list_begin (&open_inodes); e != list_end (&open_inodes);
e = list_next (e))
{
- idx = list_entry (e, struct inode, elem);
- if (idx->sector == sector)
+ inode = list_entry (e, struct inode, elem);
+ if (inode->sector == sector)
{
- idx->open_cnt++;
- return idx;
+ inode_reopen (inode);
+ return inode;
}
}
- /* Allocate inode. */
- idx = alloc_inode (sector);
- if (idx == NULL)
+ /* Allocate memory. */
+ inode = malloc (sizeof *inode);
+ if (inode == NULL)
return NULL;
- /* Read from disk. */
- ASSERT (sizeof idx->data == DISK_SECTOR_SIZE);
- disk_read (filesys_disk, sector, &idx->data);
+ /* Initialize. */
+ list_push_front (&open_inodes, &inode->elem);
+ inode->sector = sector;
+ inode->open_cnt = 1;
+ inode->deny_write_cnt = 0;
+ inode->removed = false;
+ disk_read (filesys_disk, inode->sector, &inode->data);
+ return inode;
+}
- return idx;
+/* Reopens and returns INODE. */
+struct inode *
+inode_reopen (struct inode *inode)
+{
+ if (inode != NULL)
+ inode->open_cnt++;
+ return inode;
+}
+
+/* Returns INODE's inode number. */
+disk_sector_t
+inode_get_inumber (const struct inode *inode)
+{
+ return inode->sector;
}
-/* Closes inode IDX and writes it to disk.
- If this was the last reference to IDX, frees its memory.
- If IDX was also a removed inode, frees its blocks. */
+/* Closes INODE and writes it to disk.
+ If this was the last reference to INODE, frees its memory.
+ If INODE was also a removed inode, frees its blocks. */
void
-inode_close (struct inode *idx)
+inode_close (struct inode *inode)
{
- if (idx == NULL)
+ /* Ignore null pointer. */
+ if (inode == NULL)
return;
- if (--idx->open_cnt == 0)
+ /* Release resources if this was the last opener. */
+ if (--inode->open_cnt == 0)
{
- if (idx->removed)
+ /* Remove from inode list and release lock. */
+ list_remove (&inode->elem);
+
+ /* Deallocate blocks if removed. */
+ if (inode->removed)
{
- struct bitmap *free_map;
- size_t i;
-
- free_map = bitmap_create (disk_size (filesys_disk));
- if (free_map != NULL)
- {
- bitmap_read (free_map, free_map_file);
-
- bitmap_reset (free_map, idx->sector);
- for (i = 0; i < idx->data.sector_cnt; i++)
- bitmap_reset (free_map, idx->data.sectors[i]);
-
- bitmap_write (free_map, free_map_file);
- bitmap_destroy (free_map);
- }
- else
- printf ("inode_close(): can't free blocks");
+ free_map_release (inode->sector, 1);
+ free_map_release (inode->data.start,
+ bytes_to_sectors (inode->data.length));
}
- list_remove (&idx->elem);
- free (idx);
- }
-}
-/* Writes IDX to disk. */
-void
-inode_commit (const struct inode *idx)
-{
- ASSERT (idx != NULL);
- ASSERT (sizeof idx->data == DISK_SECTOR_SIZE);
- disk_write (filesys_disk, idx->sector, &idx->data);
+ free (inode);
+ }
}
-/* Marks IDX to be deleted when it is closed by the last caller who
+/* Marks INODE to be deleted when it is closed by the last caller who
has it open. */
void
-inode_remove (struct inode *idx)
+inode_remove (struct inode *inode)
{
- ASSERT (idx != NULL);
- idx->removed = true;
+ ASSERT (inode != NULL);
+ inode->removed = true;
}
-/* Returns the disk sector that contains byte offset POS within
- the file with inode IDX.
- Returns -1 if IDX does not contain data for a byte at offset
- POS. */
-disk_sector_t
-inode_byte_to_sector (const struct inode *idx, off_t pos)
+/* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
+ Returns the number of bytes actually read, which may be less
+ than SIZE if an error occurs or end of file is reached. */
+off_t
+inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset)
{
- size_t i;
+ uint8_t *buffer = buffer_;
+ off_t bytes_read = 0;
+ uint8_t *bounce = NULL;
+
+ while (size > 0)
+ {
+ /* Disk sector to read, starting byte offset within sector. */
+ disk_sector_t sector_idx = byte_to_sector (inode, offset);
+ int sector_ofs = offset % DISK_SECTOR_SIZE;
- ASSERT (idx != NULL);
+ /* Bytes left in inode, bytes left in sector, lesser of the two. */
+ off_t inode_left = inode_length (inode) - offset;
+ int sector_left = DISK_SECTOR_SIZE - sector_ofs;
+ int min_left = inode_left < sector_left ? inode_left : sector_left;
+
+ /* Number of bytes to actually copy out of this sector. */
+ int chunk_size = size < min_left ? size : min_left;
+ if (chunk_size <= 0)
+ break;
+
+ if (sector_ofs == 0 && chunk_size == DISK_SECTOR_SIZE)
+ {
+ /* Read full sector directly into caller's buffer. */
+ disk_read (filesys_disk, sector_idx, buffer + bytes_read);
+ }
+ else
+ {
+ /* Read sector into bounce buffer, then partially copy
+ into caller's buffer. */
+ if (bounce == NULL)
+ {
+ bounce = malloc (DISK_SECTOR_SIZE);
+ if (bounce == NULL)
+ break;
+ }
+ disk_read (filesys_disk, sector_idx, bounce);
+ memcpy (buffer + bytes_read, bounce + sector_ofs, chunk_size);
+ }
+
+ /* Advance. */
+ size -= chunk_size;
+ offset += chunk_size;
+ bytes_read += chunk_size;
+ }
+ free (bounce);
- i = pos / DISK_SECTOR_SIZE;
- return i < idx->data.sector_cnt ? idx->data.sectors[i] : (disk_sector_t) -1;
+ return bytes_read;
}
-/* Returns the length, in bytes, of the file with inode IDX. */
+/* Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
+ Returns the number of bytes actually written, which may be
+ less than SIZE if end of file is reached or an error occurs.
+ (Normally a write at end of file would extend the inode, but
+ growth is not yet implemented.) */
off_t
-inode_length (const struct inode *idx)
+inode_write_at (struct inode *inode, const void *buffer_, off_t size,
+ off_t offset)
{
- ASSERT (idx != NULL);
- return idx->data.length;
-}
+ const uint8_t *buffer = buffer_;
+ off_t bytes_written = 0;
+ uint8_t *bounce = NULL;
-/* Prints a representation of IDX to the system console. */
-void
-inode_print (const struct inode *idx)
-{
- size_t i;
-
- printf ("Inode %"PRDSNu": %"PRDSNu" bytes, %zd sectors (",
- idx->sector, idx->data.length, idx->data.sector_cnt);
-
- /* This loop could be unsafe for large idx->data.sector_cnt, can
- you see why? */
- for (i = 0; i < idx->data.sector_cnt; i++)
+ if (inode->deny_write_cnt)
+ return 0;
+
+ while (size > 0)
{
- if (i != 0)
- printf (", ");
- printf ("%"PRDSNu, idx->data.sectors[i]);
+ /* Sector to write, starting byte offset within sector. */
+ disk_sector_t sector_idx = byte_to_sector (inode, offset);
+ int sector_ofs = offset % DISK_SECTOR_SIZE;
+
+ /* Bytes left in inode, bytes left in sector, lesser of the two. */
+ off_t inode_left = inode_length (inode) - offset;
+ int sector_left = DISK_SECTOR_SIZE - sector_ofs;
+ int min_left = inode_left < sector_left ? inode_left : sector_left;
+
+ /* Number of bytes to actually write into this sector. */
+ int chunk_size = size < min_left ? size : min_left;
+ if (chunk_size <= 0)
+ break;
+
+ if (sector_ofs == 0 && chunk_size == DISK_SECTOR_SIZE)
+ {
+ /* Write full sector directly to disk. */
+ disk_write (filesys_disk, sector_idx, buffer + bytes_written);
+ }
+ else
+ {
+ /* We need a bounce buffer. */
+ if (bounce == NULL)
+ {
+ bounce = malloc (DISK_SECTOR_SIZE);
+ if (bounce == NULL)
+ break;
+ }
+
+ /* If the sector contains data before or after the chunk
+ we're writing, then we need to read in the sector
+ first. Otherwise we start with a sector of all zeros. */
+ if (sector_ofs > 0 || chunk_size < sector_left)
+ disk_read (filesys_disk, sector_idx, bounce);
+ else
+ memset (bounce, 0, DISK_SECTOR_SIZE);
+ memcpy (bounce + sector_ofs, buffer + bytes_written, chunk_size);
+ disk_write (filesys_disk, sector_idx, bounce);
+ }
+
+ /* Advance. */
+ size -= chunk_size;
+ offset += chunk_size;
+ bytes_written += chunk_size;
}
- printf (")\n");
+ free (bounce);
+
+ return bytes_written;
}
-\f
-/* Returns a newly allocated and initialized inode. */
-static struct inode *
-alloc_inode (disk_sector_t sector)
+
+/* Disables writes to INODE.
+ May be called at most once per inode opener. */
+void
+inode_deny_write (struct inode *inode)
{
- /* Allocate memory. */
- struct inode *idx = calloc (1, sizeof *idx);
- if (idx == NULL)
- return NULL;
+ inode->deny_write_cnt++;
+ ASSERT (inode->deny_write_cnt <= inode->open_cnt);
+}
- /* Initialize. */
- list_push_front (&open_inodes, &idx->elem);
- idx->sector = sector;
- idx->open_cnt = 1;
- idx->removed = false;
+/* Re-enables writes to INODE.
+ Must be called once by each inode opener who has called
+ inode_deny_write() on the inode, before closing the inode. */
+void
+inode_allow_write (struct inode *inode)
+{
+ ASSERT (inode->deny_write_cnt > 0);
+ ASSERT (inode->deny_write_cnt <= inode->open_cnt);
+ inode->deny_write_cnt--;
+}
- return idx;
+/* Returns the length, in bytes, of INODE's data. */
+off_t
+inode_length (const struct inode *inode)
+{
+ return inode->data.length;
}