@func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
(IDT) to ready it for interrupt handling (@pxref{Interrupt
Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
-handling timer interrupts and keyboard interrupts, respectively. In
+handling timer interrupts and keyboard interrupts, respectively.
+@func{input_init} sets up to merge serial and keyboard input into one
+stream. In
projects 2 and later, we also prepare to handle interrupts caused by
user programs using @func{exception_init} and @func{syscall_init}.
@defmac PGSHIFT
@defmacx PGBITS
-The bit index (0) and number of bits (12) in the offset part of a
+The bit index (0) and number of bits (12) of the offset part of a
virtual address, respectively.
@end defmac
@defmac PGMASK
-A bit mask with value @t{0xfff}, so that the bits in the page offset are
-set to 1 and other bits set to 0.
+A bit mask with the bits in the page offset set to 1, the rest set to 0
+(@t{0xfff}).
@end defmac
@defmac PGSIZE
-The page size in bytes (4096).
+The page size in bytes (4,096).
@end defmac
@deftypefun unsigned pg_ofs (const void *@var{va})
@end deftypefun
Virtual memory in Pintos is divided into two regions: user virtual
-memory and kernel virtual memory. The boundary between them is
-@code{PHYS_BASE}:
+memory and kernel virtual memory (@pxref{Virtual Memory Layout}). The
+boundary between them is @code{PHYS_BASE}:
@defmac PHYS_BASE
Base address of kernel virtual memory. It defaults to @t{0xc0000000} (3
page tables (that is, those for running and suspended processes),
flushing the TLB as necessary.
-User page parameters (@var{upage})to these functions should be user
-virtual addresses. Kernel page parameters (@var{kpage}) should be
-kernel virtual addresses and should have been obtained from the user
-pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why PAL_USER?}).
-
@deftypefun bool pagedir_set_page (uint32_t *@var{pd}, void *@var{upage}, void *@var{kpage}, bool @var{writable})
-Adds to @var{pd} a mapping from page @var{upage} to the frame identified
+Adds to @var{pd} a mapping from user page @var{upage} to the frame identified
by kernel virtual address @var{kpage}. If @var{writable} is true, the
page is mapped read/write; otherwise, it is mapped read-only.
-Page @var{upage} must not already be mapped. If it is, the kernel
-panics.
+User page @var{upage} must not already be mapped in @var{pd}.
+
+Kernel page @var{kpage} should be a kernel virtual address obtained from
+the user pool with @code{palloc_get_page(PAL_USER)} (@pxref{Why
+PAL_USER?}).
Returns true if successful, false on failure. Failure will occur if
additional memory required for the page table cannot be obtained.
@end deftypefun
@deftypefun {void *} pagedir_get_page (uint32_t *@var{pd}, const void *@var{uaddr})
-Looks up the frame mapped to @var{upage} in @var{pd}. Returns the
-kernel virtual address for that frame, if @var{upage} is mapped, or a
+Looks up the frame mapped to @var{uaddr} in @var{pd}. Returns the
+kernel virtual address for that frame, if @var{uaddr} is mapped, or a
null pointer if it is not.
@end deftypefun
-@deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{upage})
-Marks page @var{upage} ``not present'' in @var{pd}. Later accesses to
+@deftypefun void pagedir_clear_page (uint32_t *@var{pd}, void *@var{page})
+Marks @var{page} ``not present'' in @var{pd}. Later accesses to
the page will fault.
-Other bits in the page table for @var{upage} are preserved, permitting
+Other bits in the page table for @var{page} are preserved, permitting
the accessed and dirty bits (see the next section) to be checked.
-If @var{upage} is not mapped, this function has no effect.
+This function has no effect if @var{page} is not mapped.
@end deftypefun
@node Page Table Accessed and Dirty Bits
@defmac PTSHIFT
@defmacx PTBITS
-The bit index (12) and number of bits (10), respectively, in a page table
-index within a virtual address.
+The starting bit index (12) and number of bits (10), respectively, in a
+page table index.
@end defmac
@defmac PTMASK
-A bit mask with the bits in the page table index set to 1 and other bits
-set to 0.
+A bit mask with the bits in the page table index set to 1 and the rest
+set to 0 (@t{0x3ff000}).
@end defmac
@defmac PTSPAN
@defmac PDSHIFT
@defmacx PDBITS
-The bit index (22) and number of bits (10), respectively, in a page
-directory index within a virtual address.
+The starting bit index (22) and number of bits (10), respectively, in a
+page directory index.
@end defmac
@defmac PDMASK
A bit mask with the bits in the page directory index set to 1 and other
-bits set to 0.
+bits set to 0 (@t{0xffc00000}).
@end defmac
@deftypefun uintptr_t pd_no (const void *@var{va})
@deftypefun {void *} pte_get_page (uint32_t @var{pte})
Returns the kernel virtual address for the frame that @var{pte} points
to. The @var{pte} may be present or not-present; if it is not-present
-then the pointer return is only meaningful if the proper bits in the PTE
+then the pointer returned is only meaningful if the address bits in the PTE
actually represent a physical address.
@end deftypefun
@deftypefun {uint32_t *} pde_get_pt (uint32_t @var{pde})
Returns the kernel virtual address for the page table page that
-@var{pde} points to. The @var{pde} must be marked present.
+@var{pde}, which must be marked present, points to.
@end deftypefun
@node Hash Table
@section Hash Table
Pintos provides a hash table data structure in @file{lib/kernel/hash.c}.
-To use it you will need to manually include its header file,
-@file{lib/kernel/hash.h}, with @code{#include <hash.h>}. Intentionally,
-no code provided with Pintos uses the hash table, which means that you
+To use it you will need to include its header file,
+@file{lib/kernel/hash.h}, with @code{#include <hash.h>}.
+No code provided with Pintos uses the hash table, which means that you
are free to use it as is, modify its implementation for your own
purposes, or ignore it, as you wish.
real element type.
@end deftp
-You will often need to obtain a @struct{hash_elem}
-given a real element of the hash table, and vice versa. Given
-a real element of the hash table, obtaining a pointer to its
-@struct{hash_elem} is trivial: take the address of the
-@struct{hash_elem} member. Use the @code{hash_entry()} macro to go the
-other direction.
+You will often need to obtain a @struct{hash_elem} given a real element
+of the hash table, and vice versa. Given a real element of the hash
+table, you may use the @samp{&} operator to obtain a pointer to its
+@struct{hash_elem}. Use the @code{hash_entry()} macro to go the other
+direction.
@deftypefn {Macro} {@var{type} *} hash_entry (struct hash_elem *@var{elem}, @var{type}, @var{member})
Returns a pointer to the structure that @var{elem}, a pointer to a
For example, suppose @code{h} is a @code{struct hash_elem *} variable
that points to a @struct{thread} member (of type @struct{hash_elem})
-named @code{h_elem}. Then, @code{hash_entry (h, struct thread, h_elem)}
+named @code{h_elem}. Then, @code{hash_entry@tie{}(h, struct thread, h_elem)}
yields the address of the @struct{thread} that @code{h} points within.
@end deftypefn
+@xref{Hash Table Example}, for an example.
+
Each hash table element must contain a key, that is, data that
-identifies and distinguishes elements in the hash table. Every element
-in a hash table at a given time must have a unique key. (Elements may
+identifies and distinguishes elements, which must be unique
+among elements in the hash table. (Elements may
also contain non-key data that need not be unique.) While an element is
-in a hash table, its key data must not be changed. For each hash table,
-you must write two functions that act on keys: a hash function and a
-comparison function. These functions must match the following
-prototypes:
+in a hash table, its key data must not be changed. Instead, if need be,
+remove the element from the hash table, modify its key, then reinsert
+the element.
+
+For each hash table, you must write two functions that act on keys: a
+hash function and a comparison function. These functions must match the
+following prototypes:
@deftp {Type} {unsigned hash_hash_func (const struct hash_elem *@var{element}, void *@var{aux})}
Returns a hash of @var{element}'s data, as a value anywhere in the range
@xref{Hash Auxiliary Data}, for an explanation of @var{aux}.
@end deftp
-A few functions that act on hashes accept a pointer to a third kind of
+@xref{Hash Table Example}, for hash and comparison function examples.
+
+A few functions accept a pointer to a third kind of
function as an argument:
@deftp {Type} {void hash_action_func (struct hash_elem *@var{element}, void *@var{aux})}
@node Basic Hash Functions
@subsection Basic Functions
-These functions create and destroy hash tables and obtain basic
-information about their contents.
+These functions create, destroy, and inspect hash tables.
@deftypefun bool hash_init (struct hash *@var{hash}, hash_hash_func *@var{hash_func}, hash_less_func *@var{less_func}, void *@var{aux})
-Initializes @var{hash} as a hash table using @var{hash_func} as hash
+Initializes @var{hash} as a hash table with @var{hash_func} as hash
function, @var{less_func} as comparison function, and @var{aux} as
auxiliary data.
Returns true if successful, false on failure. @func{hash_init} calls
@deftypefun {struct hash_elem *} hash_insert (struct hash *@var{hash}, struct hash_elem *@var{element})
Searches @var{hash} for an element equal to @var{element}. If none is
found, inserts @var{element} into @var{hash} and returns a null pointer.
-If the table already contains an element equal to @var{element}, returns
-the existing element without modifying @var{hash}.
+If the table already contains an element equal to @var{element}, it is
+returned without modifying @var{hash}.
@end deftypefun
@deftypefun {struct hash_elem *} hash_replace (struct hash *@var{hash}, struct hash_elem *@var{element})
equal to @var{element}.
The caller is responsible for deallocating any resources associated with
-the element returned, as appropriate. For example, if the hash table
+the returned element, as appropriate. For example, if the hash table
elements are dynamically allocated using @func{malloc}, then the caller
must @func{free} the element after it is no longer needed.
@end deftypefun
The element passed to the following functions is only used for hashing
and comparison purposes. It is never actually inserted into the hash
-table. Thus, only the key data in the element need be initialized, and
+table. Thus, only key data in the element needs to be initialized, and
other data in the element will not be used. It often makes sense to
declare an instance of the element type as a local variable, initialize
the key data, and then pass the address of its @struct{hash_elem} to
pointer is returned and @var{hash} is unchanged.
The caller is responsible for deallocating any resources associated with
-the element returned, as appropriate. For example, if the hash table
+the returned element, as appropriate. For example, if the hash table
elements are dynamically allocated using @func{malloc}, then the caller
must @func{free} the element after it is no longer needed.
@end deftypefun
scope:
@example
-/* @r{Returns the page containing the given virtual @var{address},
- or a null pointer if no such page exists.} */
+/* @r{Returns the page containing the given virtual @var{address},}
+ @r{or a null pointer if no such page exists.} */
struct page *
page_lookup (const void *address)
@{
it.)
@var{aux} is useful when you have some property of the data in the
-hash table that's both constant and needed for hashing or comparisons,
-but which is not stored in the data items themselves. For example, if
-the items in a hash table contain fixed-length strings, but the items
+hash table is both constant and needed for hashing or comparison,
+but not stored in the data items themselves. For example, if
+the items in a hash table are fixed-length strings, but the items
themselves don't indicate what that fixed length is, you could pass
the length as an @var{aux} parameter.
projects / pintos-anon / blobdiff