The remaining lines are for addresses below @code{PHYS_BASE}. This
means that they refer to addresses in the user program, not in the
kernel. If you know what user program was running when the kernel
-panicked, you can re-run @command{backtrace} on the user program. You
-need to have compiled the user program with debug symbols enabled for
-this to be useful. Instructions for doing so are included in
-@file{pintos/src/Makefile.userprog}.
-
-In this case, we rerun @command{backtrace} like so (typing the command
-on a single line, of course):
+panicked, you can re-run @command{backtrace} on the user program, like
+so: (typing the command on a single line, of course):
@example
~/cs140/pintos/src/utils/backtrace grow-too-big 0xc0106eff 0xc01102fb
(Use a @samp{0x} prefix to specify an address in hex.)
@end table
-You might notice that @command{gdb} tends to show code being executed
-in an order different from the order in the source. That is, the
-current statement jumps around seemingly randomly. This is due to
-GCC's optimizer, which does tend to reorder code. If it bothers you,
-you can turn off optimization by editing
-@file{pintos/src/Make.config}, removing @option{-O3} from the
-@code{CFLAGS} definition.
-
If you notice other strange behavior while using @command{gdb}, there
are three possibilities. The first is that there is a bug in your
modified Pintos. The second is that there is a bug in Bochs's
@menu
* File System New Code::
* File System Synchronization::
-* Problem 4-1 Large Files::
+* Problem 4-1 Indexed Files::
* Problem 4-2 File Growth::
* Problem 4-3 Subdirectories::
* Problem 4-4 Buffer Cache::
follows the rules above.
@end itemize
-@node Problem 4-1 Large Files
-@section Problem 4-1: Large Files
-
-Modify the file system to allow the maximum size of a file to be as
-large as the disk. You can assume that the disk will not be larger
-than 8 MB. In the basic file system, each file is limited to a file
-size of just under 64 kB. Each file has a header called an index node
-or @dfn{inode} (represented by @struct{inode}) that is a table of
-direct pointers to the disk blocks for that file. Since the inode is
-stored in one disk sector, the maximum size of a file is limited by
-the number of pointers that will fit in one disk sector. Increasing
-the limit to 8 MB will require you to implement doubly-indirect
-blocks.
+@node Problem 4-1 Indexed Files
+@section Problem 4-1: Indexed Files
+
+The basic file system allocates files as a single extent, making it
+vulnerable to external fragmentation. Eliminate this problem by
+modifying the inode structure. In practice, this probably means using
+an index structure with direct, indirect, and doubly indirect blocks.
+(You are welcome to choose a different scheme as long as you explain the
+rationale for it in your design documentation, and as long as it does
+not suffer from external fragmentation.)
+
+You can assume that the disk will not be larger than 8 MB. You must
+support files as large as the disk (minus metadata). Each inode is
+stored in one disk sector, limiting the number of block pointers that it
+can contain. Supporting 8 MB files will require you to implement
+doubly-indirect blocks.
@node Problem 4-2 File Growth
@section Problem 4-2: File Growth
@func{schedule} doesn't exist, which is arguably a @command{gdb} bug.
You can work around this by setting the breakpoint by filename and
line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is
-the line number of the first declaration in @func{schedule}.
-Alternatively you can recompile with optimization turned off, by
-removing @samp{-O3} from the @code{CFLAGS} line in
-@file{Make.config}.} Be sure to keep track of each thread's address
+the line number of the first declaration in @func{schedule}.} Be sure
+to keep track of each thread's address
and state, and what procedures are on the call stack for each thread.
You will notice that when one thread calls @func{switch_threads},
another thread starts running, and the first thing the new thread does
interrupts in your solution by calling @func{intr_disable} or
@func{intr_set_level}, although you may find doing so to be useful
while debugging. Instead, use semaphores, locks and condition
-variables to solve synchronization problems. Hint: read the comments
+variables to solve synchronization problems. Read the tour section on
+synchronization (@pxref{Synchronization}) or the comments
in @file{threads/synch.h} if you're unsure what synchronization
primitives may be used in what situations.
its many limitations. @strong{You should not modify the file system
code for this project}. Proper use of the file system routines now
will make life much easier for project 4, when you improve the file
-system implementation.
+system implementation. Until then, you will have to put up with the
+following limitations:
+
+@itemize @bullet
+@item
+No synchronization. Concurrent accesses will interfere with one
+another, so external synchronization is needed. @xref{Synchronizing
+File Access}, for more details.
+
+@item
+File size is fixed at creation time. Because the root directory is
+represented as a file, the number of files that may be created is also
+limited.
+
+@item
+File data is allocated as a single extent, so that external
+fragmentation can become a serious problem as a file system is used over
+time.
+
+@item
+No subdirectories.
+
+@item
+File names are limited to 14 characters.
+
+@item
+A system crash mid-operation may corrupt the disk in a way
+that cannot be repaired automatically. No `fsck' tool is
+provided in any case.
+@end itemize
+
+However one important feature is included:
+
+@itemize @bullet
+Unix-like semantics for filesys_remove() are implemented.
+That is, if a file is open when it is removed, its blocks
+are not deallocated and it may still be accessed by the
+threads that have it open until the last one closes it. @xref{Removing
+an Open File}, for more information.
+@end itemize
You need to be able to create and format simulated disks. The
@command{pintos} program provides this functionality with its
writing and testing this code before implementing any other system
call functionality.
+@anchor{Synchronizing File Access}
You must make sure that system calls are properly synchronized so that
any number of user processes can make them at once. In particular, it
is not safe to call into the filesystem code provided in the
The disk hasn't yet been formatted (with @samp{pintos run -f}).
@item
-The filename specified is too long. The file system limits file names
+The file name specified is too long. The file system limits file names
to 14 characters. If you're using a command like @samp{pintos put
../../tests/userprog/echo}, that overflows the limit. Use
@samp{pintos put ../../tests/userprog/echo echo} to put the file under
the name @file{echo} instead.
@item
-The file is too big. The file system has a 63 kB limit.
+The file system is full.
+
+@item
+The file system already contains 10 files. (There's a 10-file limit for
+the base Pintos file system.)
+
+@item
+The file system is so fragmented that there's not enough contiguous
+space for your file.
@end itemize
@item
#include "../lib/arc4.h"
#include "../lib/cksum.h"
-#define SIZE (63 * 1024) /* Max file size. */
+/* This is the max file size for an older version of the Pintos
+ file system that had 126 direct blocks each pointing to a
+ single disk sector. We could raise it now. */
+#define SIZE (126 * 512)
+
static char *buf = (char *) 0x10000000;
static struct arc4 *
#endif
#include "../lib/arc4.h"
-#define CHUNK_SIZE (63 * 1024) /* Max file size. */
+/* This is the max file size for an older version of the Pintos
+ file system that had 126 direct blocks each pointing to a
+ single disk sector. We could raise it now. */
+#define CHUNK_SIZE (126 * 512)
#define CHUNK_CNT 8 /* Number of chunks. */
#define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE) /* Buffer size. */
#endif
#include "../lib/arc4.h"
-#define CHUNK_SIZE (63 * 1024) /* Max file size. */
+/* This is the max file size for an older version of the Pintos
+ file system that had 126 direct blocks each pointing to a
+ single disk sector. We could raise it now. */
+#define CHUNK_SIZE (126 * 512)
#define CHUNK_CNT 16 /* Number of chunks. */
#define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE) /* Buffer size. */
CPPFLAGS = -nostdinc -I$(SRCDIR) -I- -I$(SRCDIR)/lib -I$(SRCDIR)/lib/user -I.
# Linker flags.
-# If you want to include debug symbols, comment out the STRIP assignment,
-# or invoke `make' as `make STRIP='.
-# Otherwise debug symbols will be omitted from executables to save space.
-STRIP = -s
-LDFLAGS = -nostdlib -static $(STRIP)
+LDFLAGS = -nostdlib -static
LDLIBS = $(shell $(CC) -print-libgcc-file-name)
# C library sources linked into every test program.
directory is represented as a file, the number of files
that may be created is also limited.
- - No indirect blocks. This limits maximum file size to the
- number of sector pointers that fit in a single inode
- times the size of a sector, or 126 * 512 == 63 kB given
- 32-bit sizes and 512-byte sectors.
+ - File data is allocated as a single extent, so that
+ external fragmentation can become a serious problem as a
+ file system is used over time.
- No subdirectories.
#include <bitmap.h>
#include <list.h>
#include <debug.h>
+#include <round.h>
#include <stdio.h>
#include "filesys/filesys.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))
-
/* On-disk inode.
- It is exactly DISK_SECTOR_SIZE bytes long. */
+ Must be exactly DISK_SECTOR_SIZE bytes long. */
struct inode_disk
{
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. */
+ disk_sector_t first_sector; /* Starting sector. */
+ uint32_t unused[126]; /* Unused padding. */
};
/* In-memory inode. */
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. */
+ sector_cnt = DIV_ROUND_UP (length, DISK_SECTOR_SIZE);
idx->data.length = length;
- while (idx->data.sector_cnt < sector_cnt)
- {
- size_t sector = bitmap_scan_and_flip (b, 0, 1, false);
- if (sector == BITMAP_ERROR)
- goto error;
-
- idx->data.sectors[idx->data.sector_cnt++] = sector;
- }
+ idx->data.first_sector = bitmap_scan_and_flip (b, 0, sector_cnt, false);
+ if (idx->data.first_sector == BITMAP_ERROR)
+ return NULL;
/* Zero out the file contents. */
if (sector_cnt > 0)
{
- void *zero_sector;
- size_t i;
+ static const char zero_sector[DISK_SECTOR_SIZE];
+ disk_sector_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);
+ disk_write (filesys_disk, idx->data.first_sector + i, zero_sector);
}
return idx;
if (idx->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);
+ disk_sector_t start, end;
+ bitmap_read (free_map, free_map_file);
+
+ /* Reset inode sector bit. */
bitmap_reset (free_map, idx->sector);
- for (i = 0; i < idx->data.sector_cnt; i++)
- bitmap_reset (free_map, idx->data.sectors[i]);
+
+ /* Reset inode data sector bits. */
+ start = idx->data.first_sector;
+ end = start + DIV_ROUND_UP (idx->data.length, DISK_SECTOR_SIZE);
+ bitmap_set_multiple (free_map, start, end, false);
bitmap_write (free_map, free_map_file);
bitmap_destroy (free_map);
disk_sector_t
inode_byte_to_sector (const struct inode *idx, off_t pos)
{
- size_t i;
-
ASSERT (idx != NULL);
- i = pos / DISK_SECTOR_SIZE;
- return i < idx->data.sector_cnt ? idx->data.sectors[i] : (disk_sector_t) -1;
+ if (pos < idx->data.length)
+ return idx->data.first_sector + pos / DISK_SECTOR_SIZE;
+ else
+ return (disk_sector_t) -1;
}
/* Returns the length, in bytes, of the file with inode IDX. */
void
inode_print (const struct inode *idx)
{
- size_t i;
-
- printf ("Inode %"PRDSNu": %"PRDSNu" bytes, %zu 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 (i != 0)
- printf (", ");
- printf ("%"PRDSNu, idx->data.sectors[i]);
- }
- printf (")\n");
+ printf ("Inode %"PRDSNu": %"PRDSNu" bytes, "
+ "%zu sectors starting at %"PRDSNu"\n",
+ idx->sector, idx->data.length,
+ (size_t) DIV_ROUND_UP (idx->data.length, DISK_SECTOR_SIZE),
+ idx->data.first_sector);
}
\f
/* Returns a newly allocated and initialized inode. */
projects / pintos-anon / commitdiff