CS318 - Pintos
Pintos source browser for JHU CS318 course
inode.c
Go to the documentation of this file.
1 #include "filesys/inode.h"
2 #include <list.h>
3 #include <debug.h>
4 #include <round.h>
5 #include <string.h>
6 #include "filesys/filesys.h"
7 #include "filesys/free-map.h"
8 #include "threads/malloc.h"
9 
10 /** Identifies an inode. */
11 #define INODE_MAGIC 0x494e4f44
12 
13 /** On-disk inode.
14  Must be exactly BLOCK_SECTOR_SIZE bytes long. */
15 struct inode_disk
16  {
17  block_sector_t start; /**< First data sector. */
18  off_t length; /**< File size in bytes. */
19  unsigned magic; /**< Magic number. */
20  uint32_t unused[125]; /**< Not used. */
21  };
22 
23 /** Returns the number of sectors to allocate for an inode SIZE
24  bytes long. */
25 static inline size_t
26 bytes_to_sectors (off_t size)
27 {
28  return DIV_ROUND_UP (size, BLOCK_SECTOR_SIZE);
29 }
30 
31 /** In-memory inode. */
32 struct inode
33  {
34  struct list_elem elem; /**< Element in inode list. */
35  block_sector_t sector; /**< Sector number of disk location. */
36  int open_cnt; /**< Number of openers. */
37  bool removed; /**< True if deleted, false otherwise. */
38  int deny_write_cnt; /**< 0: writes ok, >0: deny writes. */
39  struct inode_disk data; /**< Inode content. */
40  };
41 
42 /** Returns the block device sector that contains byte offset POS
43  within INODE.
44  Returns -1 if INODE does not contain data for a byte at offset
45  POS. */
46 static block_sector_t
47 byte_to_sector (const struct inode *inode, off_t pos)
48 {
49  ASSERT (inode != NULL);
50  if (pos < inode->data.length)
51  return inode->data.start + pos / BLOCK_SECTOR_SIZE;
52  else
53  return -1;
54 }
55 
56 /** List of open inodes, so that opening a single inode twice
57  returns the same `struct inode'. */
58 static struct list open_inodes;
59 
60 /** Initializes the inode module. */
61 void
62 inode_init (void)
63 {
64  list_init (&open_inodes);
65 }
66 
67 /** Initializes an inode with LENGTH bytes of data and
68  writes the new inode to sector SECTOR on the file system
69  device.
70  Returns true if successful.
71  Returns false if memory or disk allocation fails. */
72 bool
73 inode_create (block_sector_t sector, off_t length)
74 {
75  struct inode_disk *disk_inode = NULL;
76  bool success = false;
77 
78  ASSERT (length >= 0);
79 
80  /* If this assertion fails, the inode structure is not exactly
81  one sector in size, and you should fix that. */
82  ASSERT (sizeof *disk_inode == BLOCK_SECTOR_SIZE);
83 
84  disk_inode = calloc (1, sizeof *disk_inode);
85  if (disk_inode != NULL)
86  {
87  size_t sectors = bytes_to_sectors (length);
88  disk_inode->length = length;
89  disk_inode->magic = INODE_MAGIC;
90  if (free_map_allocate (sectors, &disk_inode->start))
91  {
92  block_write (fs_device, sector, disk_inode);
93  if (sectors > 0)
94  {
95  static char zeros[BLOCK_SECTOR_SIZE];
96  size_t i;
97 
98  for (i = 0; i < sectors; i++)
99  block_write (fs_device, disk_inode->start + i, zeros);
100  }
101  success = true;
102  }
103  free (disk_inode);
104  }
105  return success;
106 }
107 
108 /** Reads an inode from SECTOR
109  and returns a `struct inode' that contains it.
110  Returns a null pointer if memory allocation fails. */
111 struct inode *
112 inode_open (block_sector_t sector)
113 {
114  struct list_elem *e;
115  struct inode *inode;
116 
117  /* Check whether this inode is already open. */
118  for (e = list_begin (&open_inodes); e != list_end (&open_inodes);
119  e = list_next (e))
120  {
121  inode = list_entry (e, struct inode, elem);
122  if (inode->sector == sector)
123  {
124  inode_reopen (inode);
125  return inode;
126  }
127  }
128 
129  /* Allocate memory. */
130  inode = malloc (sizeof *inode);
131  if (inode == NULL)
132  return NULL;
133 
134  /* Initialize. */
135  list_push_front (&open_inodes, &inode->elem);
136  inode->sector = sector;
137  inode->open_cnt = 1;
138  inode->deny_write_cnt = 0;
139  inode->removed = false;
140  block_read (fs_device, inode->sector, &inode->data);
141  return inode;
142 }
143 
144 /** Reopens and returns INODE. */
145 struct inode *
146 inode_reopen (struct inode *inode)
147 {
148  if (inode != NULL)
149  inode->open_cnt++;
150  return inode;
151 }
152 
153 /** Returns INODE's inode number. */
154 block_sector_t
155 inode_get_inumber (const struct inode *inode)
156 {
157  return inode->sector;
158 }
159 
160 /** Closes INODE and writes it to disk.
161  If this was the last reference to INODE, frees its memory.
162  If INODE was also a removed inode, frees its blocks. */
163 void
164 inode_close (struct inode *inode)
165 {
166  /* Ignore null pointer. */
167  if (inode == NULL)
168  return;
169 
170  /* Release resources if this was the last opener. */
171  if (--inode->open_cnt == 0)
172  {
173  /* Remove from inode list and release lock. */
174  list_remove (&inode->elem);
175 
176  /* Deallocate blocks if removed. */
177  if (inode->removed)
178  {
179  free_map_release (inode->sector, 1);
180  free_map_release (inode->data.start,
181  bytes_to_sectors (inode->data.length));
182  }
183 
184  free (inode);
185  }
186 }
187 
188 /** Marks INODE to be deleted when it is closed by the last caller who
189  has it open. */
190 void
191 inode_remove (struct inode *inode)
192 {
193  ASSERT (inode != NULL);
194  inode->removed = true;
195 }
196 
197 /** Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
198  Returns the number of bytes actually read, which may be less
199  than SIZE if an error occurs or end of file is reached. */
200 off_t
201 inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset)
202 {
203  uint8_t *buffer = buffer_;
204  off_t bytes_read = 0;
205  uint8_t *bounce = NULL;
206 
207  while (size > 0)
208  {
209  /* Disk sector to read, starting byte offset within sector. */
210  block_sector_t sector_idx = byte_to_sector (inode, offset);
211  int sector_ofs = offset % BLOCK_SECTOR_SIZE;
212 
213  /* Bytes left in inode, bytes left in sector, lesser of the two. */
214  off_t inode_left = inode_length (inode) - offset;
215  int sector_left = BLOCK_SECTOR_SIZE - sector_ofs;
216  int min_left = inode_left < sector_left ? inode_left : sector_left;
217 
218  /* Number of bytes to actually copy out of this sector. */
219  int chunk_size = size < min_left ? size : min_left;
220  if (chunk_size <= 0)
221  break;
222 
223  if (sector_ofs == 0 && chunk_size == BLOCK_SECTOR_SIZE)
224  {
225  /* Read full sector directly into caller's buffer. */
226  block_read (fs_device, sector_idx, buffer + bytes_read);
227  }
228  else
229  {
230  /* Read sector into bounce buffer, then partially copy
231  into caller's buffer. */
232  if (bounce == NULL)
233  {
234  bounce = malloc (BLOCK_SECTOR_SIZE);
235  if (bounce == NULL)
236  break;
237  }
238  block_read (fs_device, sector_idx, bounce);
239  memcpy (buffer + bytes_read, bounce + sector_ofs, chunk_size);
240  }
241 
242  /* Advance. */
243  size -= chunk_size;
244  offset += chunk_size;
245  bytes_read += chunk_size;
246  }
247  free (bounce);
248 
249  return bytes_read;
250 }
251 
252 /** Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
253  Returns the number of bytes actually written, which may be
254  less than SIZE if end of file is reached or an error occurs.
255  (Normally a write at end of file would extend the inode, but
256  growth is not yet implemented.) */
257 off_t
258 inode_write_at (struct inode *inode, const void *buffer_, off_t size,
259  off_t offset)
260 {
261  const uint8_t *buffer = buffer_;
262  off_t bytes_written = 0;
263  uint8_t *bounce = NULL;
264 
265  if (inode->deny_write_cnt)
266  return 0;
267 
268  while (size > 0)
269  {
270  /* Sector to write, starting byte offset within sector. */
271  block_sector_t sector_idx = byte_to_sector (inode, offset);
272  int sector_ofs = offset % BLOCK_SECTOR_SIZE;
273 
274  /* Bytes left in inode, bytes left in sector, lesser of the two. */
275  off_t inode_left = inode_length (inode) - offset;
276  int sector_left = BLOCK_SECTOR_SIZE - sector_ofs;
277  int min_left = inode_left < sector_left ? inode_left : sector_left;
278 
279  /* Number of bytes to actually write into this sector. */
280  int chunk_size = size < min_left ? size : min_left;
281  if (chunk_size <= 0)
282  break;
283 
284  if (sector_ofs == 0 && chunk_size == BLOCK_SECTOR_SIZE)
285  {
286  /* Write full sector directly to disk. */
287  block_write (fs_device, sector_idx, buffer + bytes_written);
288  }
289  else
290  {
291  /* We need a bounce buffer. */
292  if (bounce == NULL)
293  {
294  bounce = malloc (BLOCK_SECTOR_SIZE);
295  if (bounce == NULL)
296  break;
297  }
298 
299  /* If the sector contains data before or after the chunk
300  we're writing, then we need to read in the sector
301  first. Otherwise we start with a sector of all zeros. */
302  if (sector_ofs > 0 || chunk_size < sector_left)
303  block_read (fs_device, sector_idx, bounce);
304  else
305  memset (bounce, 0, BLOCK_SECTOR_SIZE);
306  memcpy (bounce + sector_ofs, buffer + bytes_written, chunk_size);
307  block_write (fs_device, sector_idx, bounce);
308  }
309 
310  /* Advance. */
311  size -= chunk_size;
312  offset += chunk_size;
313  bytes_written += chunk_size;
314  }
315  free (bounce);
316 
317  return bytes_written;
318 }
319 
320 /** Disables writes to INODE.
321  May be called at most once per inode opener. */
322 void
323 inode_deny_write (struct inode *inode)
324 {
325  inode->deny_write_cnt++;
326  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
327 }
328 
329 /** Re-enables writes to INODE.
330  Must be called once by each inode opener who has called
331  inode_deny_write() on the inode, before closing the inode. */
332 void
333 inode_allow_write (struct inode *inode)
334 {
335  ASSERT (inode->deny_write_cnt > 0);
336  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
337  inode->deny_write_cnt--;
338 }
339 
340 /** Returns the length, in bytes, of INODE's data. */
341 off_t
342 inode_length (const struct inode *inode)
343 {
344  return inode->data.length;
345 }
inode::data
struct inode_disk data
Inode content.
Definition: inode.c:39
malloc
void * malloc(size_t size)
Obtains and returns a new block of at least SIZE bytes.
Definition: malloc.c:90
uint8_t
unsigned char uint8_t
Definition: stdint.h:20
list_elem
Doubly linked list.
Definition: list.h:90
inode_remove
void inode_remove(struct inode *inode)
Marks INODE to be deleted when it is closed by the last caller who has it open.
Definition: inode.c:191
list_entry
#define list_entry(LIST_ELEM, STRUCT, MEMBER)
Converts pointer to list element LIST_ELEM into a pointer to the structure that LIST_ELEM is embedded...
Definition: list.h:108
inode_disk::length
off_t length
File size in bytes.
Definition: inode.c:18
NULL
#define NULL
Definition: stddef.h:4
free_map_allocate
bool free_map_allocate(size_t cnt, block_sector_t *sectorp)
Allocates CNT consecutive sectors from the free map and stores the first into *SECTORP.
Definition: free-map.c:28
filesys.h
string.h
list_init
void list_init(struct list *list)
Initializes LIST as an empty list.
Definition: list.c:61
memcpy
void * memcpy(void *dst_, const void *src_, size_t size)
Copies SIZE bytes from SRC to DST, which must not overlap.
Definition: string.c:7
off_t
int32_t off_t
An offset within a file.
Definition: off_t.h:9
inode::open_cnt
int open_cnt
Number of openers.
Definition: inode.c:36
list_next
struct list_elem * list_next(struct list_elem *elem)
Returns the element after ELEM in its list.
Definition: list.c:82
free
void free(void *p)
Frees block P, which must have been previously allocated with malloc(), calloc(), or realloc().
Definition: malloc.c:219
block_sector_t
uint32_t block_sector_t
Index of a block device sector.
Definition: block.h:15
inode_deny_write
void inode_deny_write(struct inode *inode)
Disables writes to INODE.
Definition: inode.c:323
inode::removed
bool removed
True if deleted, false otherwise.
Definition: inode.c:37
list_remove
struct list_elem * list_remove(struct list_elem *elem)
Removes ELEM from its list and returns the element that followed it.
Definition: list.c:249
inode_write_at
off_t inode_write_at(struct inode *inode, const void *buffer_, off_t size, off_t offset)
Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
Definition: inode.c:258
inode::elem
struct list_elem elem
Element in inode list.
Definition: inode.c:34
uint32_t
unsigned int uint32_t
Definition: stdint.h:26
buffer
static struct intq buffer
Stores keys from the keyboard and serial port.
Definition: input.c:7
inode
In-memory inode.
Definition: inode.c:32
free-map.h
inode_create
bool inode_create(block_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 ...
Definition: inode.c:73
inode::sector
block_sector_t sector
Sector number of disk location.
Definition: inode.c:35
malloc.h
round.h
calloc
void * calloc(size_t a, size_t b)
Allocates and return A times B bytes initialized to zeroes.
Definition: malloc.c:159
list_end
struct list_elem * list_end(struct list *list)
Returns LIST's tail.
Definition: list.c:94
list_begin
struct list_elem * list_begin(struct list *list)
Returns the beginning of LIST.
Definition: list.c:72
inode_disk::start
block_sector_t start
First data sector.
Definition: inode.c:17
ASSERT
#define ASSERT(CONDITION)
This is outside the header guard so that debug.h may be included multiple times with different settin...
Definition: debug.h:31
inode_length
off_t inode_length(const struct inode *inode)
Returns the length, in bytes, of INODE's data.
Definition: inode.c:342
inode::deny_write_cnt
int deny_write_cnt
0: writes ok, >0: deny writes.
Definition: inode.c:38
inode_disk
On-disk inode.
Definition: inode.c:15
list_push_front
void list_push_front(struct list *list, struct list_elem *elem)
Inserts ELEM at the beginning of LIST, so that it becomes the front in LIST.
Definition: list.c:209
BLOCK_SECTOR_SIZE
#define BLOCK_SECTOR_SIZE
Size of a block device sector in bytes.
Definition: block.h:11
free_map_release
void free_map_release(block_sector_t sector, size_t cnt)
Makes CNT sectors starting at SECTOR available for use.
Definition: free-map.c:45
inode_get_inumber
block_sector_t inode_get_inumber(const struct inode *inode)
Returns INODE's inode number.
Definition: inode.c:155
inode_open
struct inode * inode_open(block_sector_t sector)
Reads an inode from SECTOR and returns a ‘struct inode’ that contains it.
Definition: inode.c:112
block_read
void block_read(struct block *block, block_sector_t sector, void *buffer)
Reads sector SECTOR from BLOCK into BUFFER, which must have room for BLOCK_SECTOR_SIZE bytes.
Definition: block.c:121
DIV_ROUND_UP
#define DIV_ROUND_UP(X, STEP)
Yields X divided by STEP, rounded up.
Definition: round.h:10
inode_allow_write
void inode_allow_write(struct inode *inode)
Re-enables writes to INODE.
Definition: inode.c:333
inode_init
void inode_init(void)
Initializes the inode module.
Definition: inode.c:62
memset
void * memset(void *dst_, int value, size_t size)
Sets the SIZE bytes in DST to VALUE.
Definition: string.c:279
byte_to_sector
static block_sector_t byte_to_sector(const struct inode *inode, off_t pos)
Returns the block device sector that contains byte offset POS within INODE.
Definition: inode.c:47
fs_device
struct block * fs_device
Partition that contains the file system.
Definition: filesys.c:11
inode_read_at
off_t inode_read_at(struct inode *inode, void *buffer_, off_t size, off_t offset)
Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
Definition: inode.c:201
inode_disk::unused
uint32_t unused[125]
Not used.
Definition: inode.c:20
list.h
inode_disk::magic
unsigned magic
Magic number.
Definition: inode.c:19
open_inodes
static struct list open_inodes
List of open inodes, so that opening a single inode twice returns the same ‘struct inode’.
Definition: inode.c:58
inode_reopen
struct inode * inode_reopen(struct inode *inode)
Reopens and returns INODE.
Definition: inode.c:146
INODE_MAGIC
#define INODE_MAGIC
Identifies an inode.
Definition: inode.c:11
block_write
void block_write(struct block *block, block_sector_t sector, const void *buffer)
Write sector SECTOR to BLOCK from BUFFER, which must contain BLOCK_SECTOR_SIZE bytes.
Definition: block.c:134
bytes_to_sectors
static size_t bytes_to_sectors(off_t size)
Returns the number of sectors to allocate for an inode SIZE bytes long.
Definition: inode.c:26
list
List.
Definition: list.h:97
debug.h
inode_close
void inode_close(struct inode *inode)
Closes INODE and writes it to disk.
Definition: inode.c:164
inode.h
Generated on Thu Aug 22 2019 10:19:15 for CS318 - Pintos by   doxygen 1.8.16