Hints for A2

This file may be updated, so check back periodically

Quick Topic Links

• General hints for system calls
• Clarification of Lock Behaviour
• OS/161 crash with no output
• Weird/Garbled Output from sy2
• Testing Your Assignment
• Controlling the Number of Processors
• GDB tips for Synchronization
• _exit
• fork
• Kernel include files
• Proper use of kmalloc and kfree
• Argument passing
• File I/O
• System Call Testing

General

% cd $HOME/cs350-os161/os161-1.99/kern/conf
% ./config ASST2
% cd ../compile/ASST2
% bmake depend
% bmake
% bmake install

Clarification of Lock Behaviour

• lock_release: A lock can not be released by a thread that is not holding the lock. This means that a thread can't release the lock before it acquires the lock and it can not release a lock that is held by another thread.

1. Do not release the lock but do not report an error. This is the least desirable option since a programmer calling lock release in an incorrect way will not be notified of the error.
2. Crash the kernel using panic().
3. Use KASSERT() to test for and catch the error.

OS/161 crash with no output

@cpu20.student[104]% sys161 kernel
sys161: System/161 release 1.13, compiled May 19 2007 21:48:06
sys161: 213925 cycles (88758k, 0u, 125167i)
sys161: 0 irqs 0 exns 0r/0w disk 0r/0w console 0r/0w/1m emufs 0r/0w net
sys161: Elapsed real time: 0.017304 seconds (12.3627 mhz)
sys161: Elapsed virtual time: 0.008557000 seconds (25 mhz)
@cpu20.student[105]% 

It is also true that the kernel creates and uses locks very early in the boot process. Thus, if you start working on locks and you find that the kernel starts failing without producing any output, as shown above, a likely explanation is that your lock code is responsible for an early crash of the kernel. Note that you cannot debug this problem by adding kprintfs to your kernel, because the failure is happening before the kernel can display the output from your kprintf. (In addition, kprintf actually uses a lock, so adding more kprintfs may affect the problem you are trying to debug, or may cause new problems.)

You need to use gdb to help you determine where the problem lies. A good thing to start with is to set breakpoints at your lock functions, and step through them when they are called to ensure that they are behaving as you expect. Another useful idea is to set a breakpoint at the panic function, which the kernel will invoke if an assertion fails.

Weird/Garbled output from sy2

Starting lock test...
thread 0: Mismatch ont thhrteeads rtval2/3:te thMrsismetval1
aTtceehs t faaildoed
n t hreaadttheths2r: rd  eeMitsattahtrdev1 mtathr1t3dtaahhr7le 2hrdc: hea/dar2e :rMte0hd 1o 1ita:t hr Methreed ans4:htvea1add te5t aMlastdht:t  Mhi 2ir11d :hr et7shm1rs:is  maMtMsemr2et1hm1: dai Miis6m
tTaetar9:ththr etsasMiahhreathtch: e:chrv area:ddtsadcera sattaMi otdmm M  i22r madhd eh toaMi1hresa2s 5ce  tt9: M1Mhrrsn namaett:m:haoccd 2aiislem3et6 datahc a  dnhh f3ds8m12a0ae: tcdtrhMtMon   a: m8t a6tcas ct 2ee iciooi a /nud:h:ttMih:dc4sa1oshsnn lMestm  o e12s8 Mh:tvm nmi e3m tv:
nM s0 :h  aa 5ad st1tiattea Titvld
  oMl1:/ tch27McchMesa1:t: oMno tin seome:ihs isml/ evMnis mchu mtnasesstvotannMsai naMmtos ttv atma fsaat  ote l1toenmtctvalM2tslictiuns/si
ctTs athcat2i/vm2lhvsmmanmat tcn cheltc/steased 
uth eotsnt oh s1ehnmatt/o
aTlcveaets vn ott/s ualvctnem1shhlsvma ttevestont1a e s
/Tn otall2enaantc/lhvmtstteut 2n3o /st sl1vhn1
ale2sessmt/n/u ttctt/ua u T
/Tntt
 vnnomfavthevnmlomoeeu Tvfa n
uetveil sau
Tn n tsftaal m
saTTaeeotlm1e
sesmaieliltlseltvsd

Testing Synchronization Primitives

Locks and Condition Variables

Controlling the Number of Processors

You can control the number of processors in the simulated machine by changing the SYS/161 configuration file, sys161.conf. Look for a line like this:

31	mainboard  ramsize=524288  cpus=1

31	mainboard  ramsize=524288  cpus=4

So that you're not constantly editing the configuration file, you can create multiple different configuration files and pass the one you want to the simulator when it starts, using the -c option, e.g,

sys161 -c my-config-file.conf kernel

GDB tips for Synchronization

This is an example gdb session to show what output to expect and how to up up the stack trace to look at a simple variable. This session was produced by Tim Brecht using a previous (older) version of OS/161 (so your code may not look the same). His comments are on the lines that start with "//". Each comment refers to the output that follows it.

This example assumes that there is a .gdbinit file like the one described in the A0 hints.

// Start cs350-gdb.
% cs350-gdb kernel
GNU gdb 6.0
Copyright 2003 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "--host=i686-pc-linux-gnu --target=mips-elf"...
__start () at ../../arch/mips/mips/start.S:24
24         addiu sp, sp, -20
Current language:  auto; currently asm
Breakpoint 1 at 0x80010948: file ../../lib/kprintf.c, line 111.

// Continue execution. This stops and waits for input into os161.
// In the window running sys161 -w kernel after I type something like
// p testbin/program it runs and eventually panics.
(gdb) continue
Continuing.

Breakpoint 1, panic (fmt=0x8002fe6c "Assertion failed: %s, at %s:%d (%s)\n") at ../../lib/kprintf.c:111
111             if (evil==0) {
Current language:  auto; currently c

// I want to find out who called panic and why.
// Where shows the stack trace of who called what and all
// the parameters.
// panic is where we are currently.
// It was called from lock_destroy at line 181 of thread/synch.c
// It was called from proc_entry_init at line 601 of userprog/syscalls.c
// etc.
// proc_entry_init was the function that called lock_destroy.
(gdb) where
#0  panic (fmt=0x8002fe6c "Assertion failed: %s, at %s:%d (%s)\n") at ../../lib/kprintf.c:111
#1  0xffffffff8001740c in lock_destroy (lock=0x800c3e20) at ../../thread/synch.c:181
#2  0xffffffff80022b30 in proc_entry_init (pid=2) at ../../userprog/syscalls.c:601
#3  0xffffffff800258dc in sys_waitpid (pid=2, status=0x7fffff90, options=0, retval=0x800fcf18)
    at ../../userprog/syscalls.c:1367
#4  0xffffffff8000c6b8 in mips_syscall (tf=0x800fcf6c) at ../../arch/mips/mips/syscall.c:145
#5  0xffffffff8000cb68 in mips_trap (tf=0x800fcf6c) at ../../arch/mips/mips/trap.c:134

// Move up the stack.
(gdb) up
#1  0xffffffff8001740c in lock_destroy (lock=0x800c3e20) at ../../thread/synch.c:181
181             assert(lock->held == 0);

// Move up the stack.
(gdb) up
#2  0xffffffff80022b30 in proc_entry_init (pid=2) at ../../userprog/syscalls.c:601
601                     lock_destroy(p->ft_lock);

// Move up the stack.
(gdb) up
#3  0xffffffff800258dc in sys_waitpid (pid=2, status=0x7fffff90, options=0, retval=0x800fcf18)
    at ../../userprog/syscalls.c:1367
1367              proc_entry_init(pid);

// Print out some info about the current thread.
(gdb) print *curthread
$1 = {t_pcb = {pcb_switchstack = 2148519408, pcb_kstack = 2148519936, pcb_ininterrupt = 0, pcb_badfaultfunc = 0,
    pcb_copyjmp = {2148517880, 2147537544, 0, 0, 0, 0, 0, 0, 0, 0, 2148517880}},
  t_name = 0x800d2d00 "ourtests/conc-io", t_sleepaddr = 0x0, t_stack = 0x800fc000 "o?=\021o?=3", t_vmspace = 0x800f7360,
  t_cwd = 0x800d2f40, pid = 1}

// Print out the value of pid as it is inside of userprog/syscalls.c in the
// function sys_waitpid at the time of the call to proc_entry_init.
(gdb) print pid
$2 = 2

// Print out the value of pid in hex.
(gdb) print/x pid
$2 = 0x2

// x/i Examine (x) specified memory location as an instruction (i).
// Print out the instruction located at address 0xffffffff8000c6b8.
// Note that I got this address from the above stack trace.
// It shows you that this is address is 520 bytes inside of mips_syscall.
// This can be really helpful if OS/161 dies and sys161 just prints
// out the epc (which contains the address of the instruction
// that generated the execption.
(gdb) x/i 0xffffffff8000c6b8
0x8000c6b8 :  j       0x8000c6f0 

// x/i Examine (x) specified memory location as an instruction (i).
// Print out the instruction located at address 0xffffffff8001740c.
// Note that I got this address from the above stack trace.
// It shows you that this address is 148 bytes inside of lock_destroy.
(gdb) x/i 0xffffffff8001740c
0x8001740c :  lw      v0,32(s8)


The list command is useful for finding the line of source that contains the faulting instruction (note the *):

Something else that can be done (from a different version of the code)
(gdb) list *0x800197c4
0x800197c4 is in kmain (../../main/main.c:164).
159     kmain(char *arguments)
160     {
161         char *bad_ptr = NULL;
162         boot();
163         
164         *bad_ptr = 0;
165
166         menu(arguments);
167
168         /* Should not get here *

_exit

• The partial implementation of _exit in the base OS/161 does not do anything with the exit status code provided by the the user program. Your complete implementation of _exit should properly handle the exit status code as described in the manual pages for _exit and waitpid.

  Here is something to think about when you do start worrying about those exit status codes: a process's exit status code may be needed long after that process has exited. Where will you keep the code, and when will it be safe to forget it?

fork

• To implement fork, you will need to copy the address space and trap frame from the parent process to use for the child process. When you do this, you need to watch out for potential synchronization problems. Specifically, you will need to make sure that the new thread goes not go to user mode until its address space and trap frame have been set up. In addition, you need to make sure that the parent process does not return to user mode until its address space and trap frame have been copied.

Kernel include files

• If you create a new kernel source (.c) file, you will need to #include one or more kernel header files at the top. The kernel has some requirements about what you must include, and about the order in which things must be included. In particular, the kernel expects that

  #include ‹types.h›
  

  will always come first. For more details and rules about #include, see the comments at the top of kern/include/types.h. Symptoms of failure to observe the these rules include complaints about errors in header files during kernel compilation.
• OS/161 kernel header files follow a convention designed to ensure that headers will not get included twice during any compilation. For example, the kern/include/lib.h includes the following preprocessor code at the top of the file

  #ifndef _LIB_H_
  #define _LIB_H_ 
  

  as well as a corresponding

  #endif /* _LIB_H_ */
  

  at the end of the file. This ensures that lib.h will never be included more than once during a compilation. Every other kernel include file includes similar code, for the same reason. If you add a new header file to your kernel, you should follow a similar convention to ensure that your header will never be included twice. Failure to do so can lead to compilation errors, such as complaints about multiply-defined symbols or variables.

proper use of kmalloc and kfree

• You will need to use kmalloc to dynamically allocate memory for your kernel to use. When that memory is no longer needed, you need to make it available for later reuse by calling kfree. For example:

  kvaddr = kmalloc(size);  /* allocated some memory */
  
  /* do some stuff */
  
  kfree(kvaddr);           /* finished with the memory so free it */
  

• Currently (for Assignment 2) kfree and the calls it relies on to actually free memory don't do anything, so memory will not actually be reused (yet). Assignment 3 often requires completeing the kfree implementation so that memory is actually freed and is available for reuse. This permits multiple programs (or kernel tests) to be executed over and over again without having to reboot the OS.
• So when working on Assignment 2, be sure to use kfree to free memory when it is not longer needed, otherwise you may have to find these memory leaks when implementing Assignment 3.

System Call Testing

• There are many OS/161 applications that you can use to test your kernel. The source code for many of these applications can be found under os161-1.99/user, in the testbin, uw-testbin, bin and sbin directories.

  You build all of the OS/161 application programs when you run bmake in the directory cs350-os161/os161-1.99. When you do this, the application program executable files are copied into subdirectories under cs350-os161/root/.

  Once your OS/161 kernel has booted, you can launch an application program using the p command from the kernel menu. For example, to run the palin program, which is located in testbin, use the following command

  OS/161 kernel [? for menu]: p testbin/palin
  

  As usual, you can pass commands to the kernel on sys161 command line, e.g.,

  sys161 kernel "p testbin/palin"
  



• The amount of memory in the default system is not very large. For some of the test applications, you may wish to increase the amount of memory by modifying the appropriate line in the sys161.conf file. Note that this must be a multiple of the page size (4096). For example:

  # Old/default value
  # 31      busctl  ramsize=524288
  # Changed to 4 MB.
  31      busctl  ramsize=4194304
  

  In particular, you will probably have to do this for applications like forktest, farm and sty.
• To evaluate the kernel you submit for Assignment 2a, we expect to use at least the following test programs, with single-processor and multi-processor configurations:

  uw-testbin/onefork

  this is the simplest test of fork, and also checks the PIDs returned to the parent and child processes

  uw-testbin/pidcheck

  this is also a very simple test that relies on fork and getpid. It can confirm that the child PID that the parent sees is the same as the child PID that the child sees.

  uw-testbin/widefork

  multiple forks, and can also test whether exit status values are being passed properly through _exit to waitpid

  testbin/forktest

  this also performs multiple forks. It relies on proper waitpid synchronization, but not on the exit statuses being returned by waitpid

  If you'd like more details about what these test programs are doing and what kind of output they produce, please just have a look at the programs themselves. The programs are all short, and reviewing them is a good way to ensure that you understand how the system calls work.

Passing Arguments

• To pass arguments (argv) to a user program, you will have to load the arguments into the program's address space. In addition to the argument strings themselves, you have to create the argv array in the user program's address space - argv is an array of pointers to the actual argument strings.


• Whenever you are loading data into an address space, you must ensure that it is properly aligned. Otherwise, the application will cause addressing exceptions when it tries to access the data. 4-byte items, like character pointers, must start at an address that is divisible by 4. So, it would be OK to start your argv array at an address like 0x7fffff08, but your application will run in to alignment problems if argv starts at an address like 0x7fffff09 or 0x7fffff0a, since those addresses are not divisible by 4. Characters are only 1 byte long, so there are no alignment issues. Your argument strings, which are character arrays, can start at any address.

  A related constraint is that the stack pointer should always start at an address that is 8-byte aligned (evenly divisible by 8). This is because the largest data types that require alignment (and which might be pushed onto a stack) are 8 bytes long, e.g., a double-precision floating point value.

• Make sure that you understand how argv and argc are supposed to work before you try implementing argument passing. As an example, consider the testbin/tail application, which expects two arguments. The main() function of tail looks like this:

  int
  main(int argc, char **argv)
  {
  	int file;
  
  	if (argc < 3) {
  		errx(1, "Usage: tail  ");
  	}
  	file = open(argv[1], O_RDONLY);
  	if (file < 0) {
  		err(1, "%s", argv[1]);
  	}
  	tail(file, atoi(argv[2]), argv[1]);
  	close(file);
  	return 0;
  }
  

  argv is a character pointer pointer - it points to an array of character pointers, each of which points to one of the arguments. For example, if the tail program is invoked from the kernel command line like this:

  OS/161 kernel [? for menu]: p testbin/sort foo 100
  

  Then the argv and argc variables should be set up as illustrated in the following illustration:
  
  A detailed description of the expected set up of argv and argc can be found in the man page for the execv system call.

File I/O

• A call like this:

  result = vfs_open("string", mode, &2vn);
  

  is incorrect and should bring a warning from the compiler. The problem is that vfs_open may modify its first argument, but "string" is an unmodifiable literal.

  Since vfs_open may modify its first argument, it is generally a good idea to make a copy of that argument and then pass the copy to vfs_open. For example, if fname points to a string representing the name of the file to be opened, you can use code similar to this:

  char *fname_temp;
  fname_temp = kstrdup(fname);
  result = vfs_open(fname_temp,mode,&vn);
  kfree(fname_temp);
  

• VOP_WRITE, VOP_READ, and other operations on vnodes want a uio structure as a parameter. kern/syscall/loadelf.c contains some useful examples of uio structures being setup and used for vnode operations. The uio structure itself is defined in kern/include/uio.h.

gdb

• gdb is can be very useful for poking around in memory, especially when you are trying to implement argument passing. When you are printing pointer values, you'll probably find it handy to have them displayed in hex, rather than decimal. This is easy to do with gdb. For example, suppose you have a pointer variable called argsarraystart, and you want to know its value. By default, it will print as a decimal number:

  (gdb) print argsarraystart
  $5 = 2147483616
      

  However, you can simply ask gdb to format it as hex:

  (gdb) print /x argsarraystart
  $6 = 0x7fffffe0
      

• you can also use gdb to print the value stored at any memory location that can be mapped by the kernel (based on the current contents of the TLB). For example:

  (gdb) print *(char *)0x7fffffe8
  $17 = 117 'u'
      

  The (char *) in this command tells gdb to treat the address 0x7fffffe8 as a character pointer. The leading * tells gdb to dereference that address and print the value stored there. This is an easy way to see whether things are as you expect them to be in memory. For example, once you have copied arguments into a new address space, you can inspect the address space to see if things are laid out as you expect.