commit 382c7f638b76d411c9a1286ef96af0a3307c4229 parent 369cb6557e7b92268ebfdb6508eacee8803605d4 Author: Brian Swetland <swetland@frotz.net> Date: Sat, 28 Dec 2013 05:38:31 -0800 move rest of source code to subdirs, tidy the build a bit kernel source lives in kernel/... user library source lives in ulib/... tools live in tools/... kernel and userspace objects are generated in kobj/... and uobj/... intermediates are generated in out/... contents of the filesystem are generated in fs/... kernel/main.c and kernel/proc.c had to be adjusted due to the out/... path affecting the symbol names for the initcode and entryother blobs tools/mkfs.c is adjusted to allow fs/... prefixes Diffstat:
50 files changed, 1004 insertions(+), 981 deletions(-)
diff --git a/.gitignore b/.gitignore @@ -1,16 +1,13 @@ *~ _* +.*.swp *.o *.d *.asm *.sym *.img vectors.S -bootblock -entryother -initcode -initcode.out -kernel -kernelmemfs mkfs .gdbinit +out +fs diff --git a/Makefile b/Makefile @@ -1,32 +1,32 @@ OBJS = \ - bio.o\ - console.o\ - exec.o\ - file.o\ - fs.o\ - ide.o\ - ioapic.o\ - kalloc.o\ - kbd.o\ - lapic.o\ - log.o\ - main.o\ - mp.o\ - picirq.o\ - pipe.o\ - proc.o\ - spinlock.o\ - string.o\ - swtch.o\ - syscall.o\ - sysfile.o\ - sysproc.o\ - timer.o\ - trapasm.o\ - trap.o\ - uart.o\ - vectors.o\ - vm.o\ + kobj/bio.o\ + kobj/console.o\ + kobj/exec.o\ + kobj/file.o\ + kobj/fs.o\ + kobj/ide.o\ + kobj/ioapic.o\ + kobj/kalloc.o\ + kobj/kbd.o\ + kobj/lapic.o\ + kobj/log.o\ + kobj/main.o\ + kobj/mp.o\ + kobj/picirq.o\ + kobj/pipe.o\ + kobj/proc.o\ + kobj/spinlock.o\ + kobj/string.o\ + kobj/swtch.o\ + kobj/syscall.o\ + kobj/sysfile.o\ + kobj/sysproc.o\ + kobj/timer.o\ + kobj/trapasm.o\ + kobj/trap.o\ + kobj/uart.o\ + kobj/vectors.o\ + kobj/vm.o\ # Cross-compiling (e.g., on Mac OS X) #TOOLPREFIX = i386-jos-elf- @@ -84,40 +84,65 @@ ASFLAGS += -Iinclude $(XFLAGS) # FreeBSD ld wants ``elf_i386_fbsd'' LDFLAGS += -m $(shell $(LD) -V | grep elf_i386 2>/dev/null) -xv6.img: bootblock kernel fs.img +xv6.img: out/bootblock out/kernel.elf fs.img dd if=/dev/zero of=xv6.img count=10000 - dd if=bootblock of=xv6.img conv=notrunc - dd if=kernel of=xv6.img seek=1 conv=notrunc + dd if=out/bootblock of=xv6.img conv=notrunc + dd if=out/kernel.elf of=xv6.img seek=1 conv=notrunc -xv6memfs.img: bootblock kernelmemfs +xv6memfs.img: out/bootblock out/kernelmemfs.elf dd if=/dev/zero of=xv6memfs.img count=10000 - dd if=bootblock of=xv6memfs.img conv=notrunc - dd if=kernelmemfs of=xv6memfs.img seek=1 conv=notrunc - -bootblock: bootasm.S bootmain.c - $(CC) $(CFLAGS) -fno-pic -O -nostdinc -I. -c bootmain.c - $(CC) $(CFLAGS) -fno-pic -nostdinc -I. -c bootasm.S - $(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 -o bootblock.o bootasm.o bootmain.o - $(OBJDUMP) -S bootblock.o > bootblock.asm - $(OBJCOPY) -S -O binary -j .text bootblock.o bootblock - ./sign.pl bootblock - -entryother: entryother.S - $(CC) $(CFLAGS) -fno-pic -nostdinc -I. -c entryother.S - $(LD) $(LDFLAGS) -N -e start -Ttext 0x7000 -o bootblockother.o entryother.o - $(OBJCOPY) -S -O binary -j .text bootblockother.o entryother - $(OBJDUMP) -S bootblockother.o > entryother.asm - -initcode: initcode.S - $(CC) $(CFLAGS) -nostdinc -I. -c initcode.S - $(LD) $(LDFLAGS) -N -e start -Ttext 0 -o initcode.out initcode.o - $(OBJCOPY) -S -O binary initcode.out initcode - $(OBJDUMP) -S initcode.o > initcode.asm - -kernel: $(OBJS) entry.o entryother initcode kernel.ld - $(LD) $(LDFLAGS) -T kernel.ld -o kernel entry.o $(OBJS) -b binary initcode entryother - $(OBJDUMP) -S kernel > kernel.asm - $(OBJDUMP) -t kernel | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > kernel.sym + dd if=out/bootblock of=xv6memfs.img conv=notrunc + dd if=out/kernelmemfs.elf of=xv6memfs.img seek=1 conv=notrunc + +# kernel object files +kobj/%.o: kernel/%.c + @mkdir -p kobj + $(CC) $(CFLAGS) -c -o $@ $< + +kobj/%.o: kernel/%.S + @mkdir -p kobj + $(CC) $(ASFLAGS) -c -o $@ $< + +# userspace object files +uobj/%.o: user/%.c + @mkdir -p uobj + $(CC) $(CFLAGS) -c -o $@ $< + +uobj/%.o: ulib/%.c + @mkdir -p uobj + $(CC) $(CFLAGS) -c -o $@ $< + +uobj/%.o: ulib/%.S + @mkdir -p uobj + $(CC) $(ASFLAGS) -c -o $@ $< + +out/bootblock: kernel/bootasm.S kernel/bootmain.c + @mkdir -p out + $(CC) $(CFLAGS) -fno-pic -O -nostdinc -I. -o out/bootmain.o -c kernel/bootmain.c + $(CC) $(CFLAGS) -fno-pic -nostdinc -I. -o out/bootasm.o -c kernel/bootasm.S + $(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 -o out/bootblock.o out/bootasm.o out/bootmain.o + $(OBJDUMP) -S out/bootblock.o > out/bootblock.asm + $(OBJCOPY) -S -O binary -j .text out/bootblock.o out/bootblock + tools/sign.pl out/bootblock + +out/entryother: kernel/entryother.S + @mkdir -p out + $(CC) $(CFLAGS) -fno-pic -nostdinc -I. -o out/entryother.o -c kernel/entryother.S + $(LD) $(LDFLAGS) -N -e start -Ttext 0x7000 -o out/bootblockother.o out/entryother.o + $(OBJCOPY) -S -O binary -j .text out/bootblockother.o out/entryother + $(OBJDUMP) -S out/bootblockother.o > out/entryother.asm + +out/initcode: kernel/initcode.S + @mkdir -p out + $(CC) $(CFLAGS) -nostdinc -I. -o out/initcode.o -c kernel/initcode.S + $(LD) $(LDFLAGS) -N -e start -Ttext 0 -o out/initcode.out out/initcode.o + $(OBJCOPY) -S -O binary out/initcode.out out/initcode + $(OBJDUMP) -S out/initcode.o > out/initcode.asm + +out/kernel.elf: $(OBJS) kernel/entry.o out/entryother out/initcode kernel/kernel.ld + $(LD) $(LDFLAGS) -T kernel/kernel.ld -o out/kernel.elf kernel/entry.o $(OBJS) -b binary out/initcode out/entryother + $(OBJDUMP) -S out/kernel.elf > out/kernel.asm + $(OBJDUMP) -t out/kernel.elf | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > out/kernel.sym # kernelmemfs is a copy of kernel that maintains the # disk image in memory instead of writing to a disk. @@ -125,73 +150,76 @@ kernel: $(OBJS) entry.o entryother initcode kernel.ld # exploring disk buffering implementations, but it is # great for testing the kernel on real hardware without # needing a scratch disk. -MEMFSOBJS = $(filter-out ide.o,$(OBJS)) memide.o -kernelmemfs: $(MEMFSOBJS) entry.o entryother initcode fs.img - $(LD) $(LDFLAGS) -Ttext 0x100000 -e main -o kernelmemfs entry.o $(MEMFSOBJS) -b binary initcode entryother fs.img - $(OBJDUMP) -S kernelmemfs > kernelmemfs.asm - $(OBJDUMP) -t kernelmemfs | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > kernelmemfs.sym +MEMFSOBJS = $(filter-out kernel/ide.o,$(OBJS)) kernel/memide.o +out/kernelmemfs.elf: $(MEMFSOBJS) kernel/entry.o out/entryother out/initcode fs.img kernel/kernel.ld + $(LD) $(LDFLAGS) -T kernel/kernel.ld -o out/kernelmemfs.elf kernel/entry.o $(MEMFSOBJS) -b binary out/initcode out/entryother fs.img + $(OBJDUMP) -S out/kernelmemfs.elf > kernelmemfs.asm + $(OBJDUMP) -t out/kernelmemfs.elf | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > kernelmemfs.sym tags: $(OBJS) entryother.S _init etags *.S *.c -vectors.S: vectors.pl - perl vectors.pl > vectors.S +kernel/vectors.S: tools/vectors.pl + perl tools/vectors.pl > kernel/vectors.S -ULIB = ulib.o usys.o printf.o umalloc.o +ULIB = uobj/ulib.o uobj/usys.o uobj/printf.o uobj/umalloc.o -_%: user/%.o $(ULIB) +fs/%: uobj/%.o $(ULIB) + @mkdir -p fs out $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $@ $^ - $(OBJDUMP) -S $@ > $*.asm - $(OBJDUMP) -t $@ | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > $*.sym + $(OBJDUMP) -S $@ > out/$*.asm + $(OBJDUMP) -t $@ | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > out/$*.sym -_forktest: user/forktest.o $(ULIB) +fs/forktest: uobj/forktest.o $(ULIB) + @mkdir -p fs # forktest has less library code linked in - needs to be small # in order to be able to max out the proc table. - $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o _forktest user/forktest.o ulib.o usys.o - $(OBJDUMP) -S _forktest > forktest.asm + $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o fs/forktest uobj/forktest.o uobj/ulib.o uobj/usys.o + $(OBJDUMP) -S fs/forktest > out/forktest.asm -mkfs: mkfs.c include/fs.h - gcc -Werror -Wall -o mkfs mkfs.c +out/mkfs: tools/mkfs.c include/fs.h + gcc -Werror -Wall -o out/mkfs tools/mkfs.c # Prevent deletion of intermediate files, e.g. cat.o, after first build, so # that disk image changes after first build are persistent until clean. More # details: # http://www.gnu.org/software/make/manual/html_node/Chained-Rules.html -.PRECIOUS: %.o +.PRECIOUS: uobj/%.o UPROGS=\ - _cat\ - _echo\ - _forktest\ - _grep\ - _init\ - _kill\ - _ln\ - _ls\ - _mkdir\ - _rm\ - _sh\ - _stressfs\ - _usertests\ - _wc\ - _zombie\ - -fs.img: mkfs README $(UPROGS) - ./mkfs fs.img README $(UPROGS) - --include *.d + fs/cat\ + fs/echo\ + fs/forktest\ + fs/grep\ + fs/init\ + fs/kill\ + fs/ln\ + fs/ls\ + fs/mkdir\ + fs/rm\ + fs/sh\ + fs/stressfs\ + fs/usertests\ + fs/wc\ + fs/zombie\ + +fs/README: README + @mkdir -p fs + cp README fs/README + +fs.img: out/mkfs README $(UPROGS) + out/mkfs fs.img README $(UPROGS) + +-include */*.d clean: - rm -f *.tex *.dvi *.idx *.aux *.log *.ind *.ilg \ - *.o *.d *.asm *.sym vectors.S bootblock entryother \ - initcode initcode.out kernel xv6.img fs.img kernelmemfs mkfs \ - .gdbinit \ - $(UPROGS) + rm -rf out fs uobj kobj + rm -f kernel/vectors.S xv6.img xv6memfs.img fs.img .gdbinit # run in emulators bochs : fs.img xv6.img - if [ ! -e .bochsrc ]; then ln -s dot-bochsrc .bochsrc; fi + if [ ! -e .bochsrc ]; then ln -s tools/dot-bochsrc .bochsrc; fi bochs -q # try to generate a unique GDB port diff --git a/bio.c b/kernel/bio.c diff --git a/bootasm.S b/kernel/bootasm.S diff --git a/bootmain.c b/kernel/bootmain.c diff --git a/console.c b/kernel/console.c diff --git a/entry.S b/kernel/entry.S diff --git a/entryother.S b/kernel/entryother.S diff --git a/exec.c b/kernel/exec.c diff --git a/file.c b/kernel/file.c diff --git a/fs.c b/kernel/fs.c diff --git a/ide.c b/kernel/ide.c diff --git a/initcode.S b/kernel/initcode.S diff --git a/ioapic.c b/kernel/ioapic.c diff --git a/kalloc.c b/kernel/kalloc.c diff --git a/kbd.c b/kernel/kbd.c diff --git a/kernel.ld b/kernel/kernel.ld diff --git a/lapic.c b/kernel/lapic.c diff --git a/log.c b/kernel/log.c diff --git a/kernel/main.c b/kernel/main.c @@ -0,0 +1,116 @@ +#include "types.h" +#include "defs.h" +#include "param.h" +#include "memlayout.h" +#include "mmu.h" +#include "proc.h" +#include "x86.h" + +static void startothers(void); +static void mpmain(void) __attribute__((noreturn)); +extern pde_t *kpgdir; +extern char end[]; // first address after kernel loaded from ELF file + +// Bootstrap processor starts running C code here. +// Allocate a real stack and switch to it, first +// doing some setup required for memory allocator to work. +int +main(void) +{ + kinit1(end, P2V(4*1024*1024)); // phys page allocator + kvmalloc(); // kernel page table + mpinit(); // collect info about this machine + lapicinit(); + seginit(); // set up segments + cprintf("\ncpu%d: starting xv6\n\n", cpu->id); + picinit(); // interrupt controller + ioapicinit(); // another interrupt controller + consoleinit(); // I/O devices & their interrupts + uartinit(); // serial port + pinit(); // process table + tvinit(); // trap vectors + binit(); // buffer cache + fileinit(); // file table + iinit(); // inode cache + ideinit(); // disk + if(!ismp) + timerinit(); // uniprocessor timer + startothers(); // start other processors + kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers() + userinit(); // first user process + // Finish setting up this processor in mpmain. + mpmain(); +} + +// Other CPUs jump here from entryother.S. +static void +mpenter(void) +{ + switchkvm(); + seginit(); + lapicinit(); + mpmain(); +} + +// Common CPU setup code. +static void +mpmain(void) +{ + cprintf("cpu%d: starting\n", cpu->id); + idtinit(); // load idt register + xchg(&cpu->started, 1); // tell startothers() we're up + scheduler(); // start running processes +} + +pde_t entrypgdir[]; // For entry.S + +// Start the non-boot (AP) processors. +static void +startothers(void) +{ + extern uchar _binary_out_entryother_start[], _binary_out_entryother_size[]; + uchar *code; + struct cpu *c; + char *stack; + + // Write entry code to unused memory at 0x7000. + // The linker has placed the image of entryother.S in + // _binary_entryother_start. + code = p2v(0x7000); + memmove(code, _binary_out_entryother_start, (uint)_binary_out_entryother_size); + + for(c = cpus; c < cpus+ncpu; c++){ + if(c == cpus+cpunum()) // We've started already. + continue; + + // Tell entryother.S what stack to use, where to enter, and what + // pgdir to use. We cannot use kpgdir yet, because the AP processor + // is running in low memory, so we use entrypgdir for the APs too. + stack = kalloc(); + *(void**)(code-4) = stack + KSTACKSIZE; + *(void**)(code-8) = mpenter; + *(int**)(code-12) = (void *) v2p(entrypgdir); + + lapicstartap(c->id, v2p(code)); + + // wait for cpu to finish mpmain() + while(c->started == 0) + ; + } +} + +// Boot page table used in entry.S and entryother.S. +// Page directories (and page tables), must start on a page boundary, +// hence the "__aligned__" attribute. +// Use PTE_PS in page directory entry to enable 4Mbyte pages. +__attribute__((__aligned__(PGSIZE))) +pde_t entrypgdir[NPDENTRIES] = { + // Map VA's [0, 4MB) to PA's [0, 4MB) + [0] = (0) | PTE_P | PTE_W | PTE_PS, + // Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB) + [KERNBASE>>PDXSHIFT] = (0) | PTE_P | PTE_W | PTE_PS, +}; + +//PAGEBREAK! +// Blank page. + diff --git a/memide.c b/kernel/memide.c diff --git a/mp.c b/kernel/mp.c diff --git a/picirq.c b/kernel/picirq.c diff --git a/pipe.c b/kernel/pipe.c diff --git a/kernel/proc.c b/kernel/proc.c @@ -0,0 +1,459 @@ +#include "types.h" +#include "defs.h" +#include "param.h" +#include "memlayout.h" +#include "mmu.h" +#include "x86.h" +#include "proc.h" +#include "spinlock.h" + +struct { + struct spinlock lock; + struct proc proc[NPROC]; +} ptable; + +static struct proc *initproc; + +int nextpid = 1; +extern void forkret(void); +extern void trapret(void); + +static void wakeup1(void *chan); + +void +pinit(void) +{ + initlock(&ptable.lock, "ptable"); +} + +//PAGEBREAK: 32 +// Look in the process table for an UNUSED proc. +// If found, change state to EMBRYO and initialize +// state required to run in the kernel. +// Otherwise return 0. +static struct proc* +allocproc(void) +{ + struct proc *p; + char *sp; + + acquire(&ptable.lock); + for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) + if(p->state == UNUSED) + goto found; + release(&ptable.lock); + return 0; + +found: + p->state = EMBRYO; + p->pid = nextpid++; + release(&ptable.lock); + + // Allocate kernel stack. + if((p->kstack = kalloc()) == 0){ + p->state = UNUSED; + return 0; + } + sp = p->kstack + KSTACKSIZE; + + // Leave room for trap frame. + sp -= sizeof *p->tf; + p->tf = (struct trapframe*)sp; + + // Set up new context to start executing at forkret, + // which returns to trapret. + sp -= 4; + *(uint*)sp = (uint)trapret; + + sp -= sizeof *p->context; + p->context = (struct context*)sp; + memset(p->context, 0, sizeof *p->context); + p->context->eip = (uint)forkret; + + return p; +} + +//PAGEBREAK: 32 +// Set up first user process. +void +userinit(void) +{ + struct proc *p; + extern char _binary_out_initcode_start[], _binary_out_initcode_size[]; + + p = allocproc(); + initproc = p; + if((p->pgdir = setupkvm()) == 0) + panic("userinit: out of memory?"); + inituvm(p->pgdir, _binary_out_initcode_start, (int)_binary_out_initcode_size); + p->sz = PGSIZE; + memset(p->tf, 0, sizeof(*p->tf)); + p->tf->cs = (SEG_UCODE << 3) | DPL_USER; + p->tf->ds = (SEG_UDATA << 3) | DPL_USER; + p->tf->es = p->tf->ds; + p->tf->ss = p->tf->ds; + p->tf->eflags = FL_IF; + p->tf->esp = PGSIZE; + p->tf->eip = 0; // beginning of initcode.S + + safestrcpy(p->name, "initcode", sizeof(p->name)); + p->cwd = namei("/"); + + p->state = RUNNABLE; +} + +// Grow current process's memory by n bytes. +// Return 0 on success, -1 on failure. +int +growproc(int n) +{ + uint sz; + + sz = proc->sz; + if(n > 0){ + if((sz = allocuvm(proc->pgdir, sz, sz + n)) == 0) + return -1; + } else if(n < 0){ + if((sz = deallocuvm(proc->pgdir, sz, sz + n)) == 0) + return -1; + } + proc->sz = sz; + switchuvm(proc); + return 0; +} + +// Create a new process copying p as the parent. +// Sets up stack to return as if from system call. +// Caller must set state of returned proc to RUNNABLE. +int +fork(void) +{ + int i, pid; + struct proc *np; + + // Allocate process. + if((np = allocproc()) == 0) + return -1; + + // Copy process state from p. + if((np->pgdir = copyuvm(proc->pgdir, proc->sz)) == 0){ + kfree(np->kstack); + np->kstack = 0; + np->state = UNUSED; + return -1; + } + np->sz = proc->sz; + np->parent = proc; + *np->tf = *proc->tf; + + // Clear %eax so that fork returns 0 in the child. + np->tf->eax = 0; + + for(i = 0; i < NOFILE; i++) + if(proc->ofile[i]) + np->ofile[i] = filedup(proc->ofile[i]); + np->cwd = idup(proc->cwd); + + pid = np->pid; + np->state = RUNNABLE; + safestrcpy(np->name, proc->name, sizeof(proc->name)); + return pid; +} + +// Exit the current process. Does not return. +// An exited process remains in the zombie state +// until its parent calls wait() to find out it exited. +void +exit(void) +{ + struct proc *p; + int fd; + + if(proc == initproc) + panic("init exiting"); + + // Close all open files. + for(fd = 0; fd < NOFILE; fd++){ + if(proc->ofile[fd]){ + fileclose(proc->ofile[fd]); + proc->ofile[fd] = 0; + } + } + + iput(proc->cwd); + proc->cwd = 0; + + acquire(&ptable.lock); + + // Parent might be sleeping in wait(). + wakeup1(proc->parent); + + // Pass abandoned children to init. + for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ + if(p->parent == proc){ + p->parent = initproc; + if(p->state == ZOMBIE) + wakeup1(initproc); + } + } + + // Jump into the scheduler, never to return. + proc->state = ZOMBIE; + sched(); + panic("zombie exit"); +} + +// Wait for a child process to exit and return its pid. +// Return -1 if this process has no children. +int +wait(void) +{ + struct proc *p; + int havekids, pid; + + acquire(&ptable.lock); + for(;;){ + // Scan through table looking for zombie children. + havekids = 0; + for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ + if(p->parent != proc) + continue; + havekids = 1; + if(p->state == ZOMBIE){ + // Found one. + pid = p->pid; + kfree(p->kstack); + p->kstack = 0; + freevm(p->pgdir); + p->state = UNUSED; + p->pid = 0; + p->parent = 0; + p->name[0] = 0; + p->killed = 0; + release(&ptable.lock); + return pid; + } + } + + // No point waiting if we don't have any children. + if(!havekids || proc->killed){ + release(&ptable.lock); + return -1; + } + + // Wait for children to exit. (See wakeup1 call in proc_exit.) + sleep(proc, &ptable.lock); //DOC: wait-sleep + } +} + +//PAGEBREAK: 42 +// Per-CPU process scheduler. +// Each CPU calls scheduler() after setting itself up. +// Scheduler never returns. It loops, doing: +// - choose a process to run +// - swtch to start running that process +// - eventually that process transfers control +// via swtch back to the scheduler. +void +scheduler(void) +{ + struct proc *p; + + for(;;){ + // Enable interrupts on this processor. + sti(); + + // Loop over process table looking for process to run. + acquire(&ptable.lock); + for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ + if(p->state != RUNNABLE) + continue; + + // Switch to chosen process. It is the process's job + // to release ptable.lock and then reacquire it + // before jumping back to us. + proc = p; + switchuvm(p); + p->state = RUNNING; + swtch(&cpu->scheduler, proc->context); + switchkvm(); + + // Process is done running for now. + // It should have changed its p->state before coming back. + proc = 0; + } + release(&ptable.lock); + + } +} + +// Enter scheduler. Must hold only ptable.lock +// and have changed proc->state. +void +sched(void) +{ + int intena; + + if(!holding(&ptable.lock)) + panic("sched ptable.lock"); + if(cpu->ncli != 1) + panic("sched locks"); + if(proc->state == RUNNING) + panic("sched running"); + if(readeflags()&FL_IF) + panic("sched interruptible"); + intena = cpu->intena; + swtch(&proc->context, cpu->scheduler); + cpu->intena = intena; +} + +// Give up the CPU for one scheduling round. +void +yield(void) +{ + acquire(&ptable.lock); //DOC: yieldlock + proc->state = RUNNABLE; + sched(); + release(&ptable.lock); +} + +// A fork child's very first scheduling by scheduler() +// will swtch here. "Return" to user space. +void +forkret(void) +{ + static int first = 1; + // Still holding ptable.lock from scheduler. + release(&ptable.lock); + + if (first) { + // Some initialization functions must be run in the context + // of a regular process (e.g., they call sleep), and thus cannot + // be run from main(). + first = 0; + initlog(); + } + + // Return to "caller", actually trapret (see allocproc). +} + +// Atomically release lock and sleep on chan. +// Reacquires lock when awakened. +void +sleep(void *chan, struct spinlock *lk) +{ + if(proc == 0) + panic("sleep"); + + if(lk == 0) + panic("sleep without lk"); + + // Must acquire ptable.lock in order to + // change p->state and then call sched. + // Once we hold ptable.lock, we can be + // guaranteed that we won't miss any wakeup + // (wakeup runs with ptable.lock locked), + // so it's okay to release lk. + if(lk != &ptable.lock){ //DOC: sleeplock0 + acquire(&ptable.lock); //DOC: sleeplock1 + release(lk); + } + + // Go to sleep. + proc->chan = chan; + proc->state = SLEEPING; + sched(); + + // Tidy up. + proc->chan = 0; + + // Reacquire original lock. + if(lk != &ptable.lock){ //DOC: sleeplock2 + release(&ptable.lock); + acquire(lk); + } +} + +//PAGEBREAK! +// Wake up all processes sleeping on chan. +// The ptable lock must be held. +static void +wakeup1(void *chan) +{ + struct proc *p; + + for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) + if(p->state == SLEEPING && p->chan == chan) + p->state = RUNNABLE; +} + +// Wake up all processes sleeping on chan. +void +wakeup(void *chan) +{ + acquire(&ptable.lock); + wakeup1(chan); + release(&ptable.lock); +} + +// Kill the process with the given pid. +// Process won't exit until it returns +// to user space (see trap in trap.c). +int +kill(int pid) +{ + struct proc *p; + + acquire(&ptable.lock); + for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ + if(p->pid == pid){ + p->killed = 1; + // Wake process from sleep if necessary. + if(p->state == SLEEPING) + p->state = RUNNABLE; + release(&ptable.lock); + return 0; + } + } + release(&ptable.lock); + return -1; +} + +//PAGEBREAK: 36 +// Print a process listing to console. For debugging. +// Runs when user types ^P on console. +// No lock to avoid wedging a stuck machine further. +void +procdump(void) +{ + static char *states[] = { + [UNUSED] "unused", + [EMBRYO] "embryo", + [SLEEPING] "sleep ", + [RUNNABLE] "runble", + [RUNNING] "run ", + [ZOMBIE] "zombie" + }; + int i; + struct proc *p; + char *state; + uint pc[10]; + + for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ + if(p->state == UNUSED) + continue; + if(p->state >= 0 && p->state < NELEM(states) && states[p->state]) + state = states[p->state]; + else + state = "???"; + cprintf("%d %s %s", p->pid, state, p->name); + if(p->state == SLEEPING){ + getcallerpcs((uint*)p->context->ebp+2, pc); + for(i=0; i<10 && pc[i] != 0; i++) + cprintf(" %p", pc[i]); + } + cprintf("\n"); + } +} + + diff --git a/spinlock.c b/kernel/spinlock.c diff --git a/string.c b/kernel/string.c diff --git a/swtch.S b/kernel/swtch.S diff --git a/syscall.c b/kernel/syscall.c diff --git a/sysfile.c b/kernel/sysfile.c diff --git a/sysproc.c b/kernel/sysproc.c diff --git a/timer.c b/kernel/timer.c diff --git a/trap.c b/kernel/trap.c diff --git a/trapasm.S b/kernel/trapasm.S diff --git a/uart.c b/kernel/uart.c diff --git a/vm.c b/kernel/vm.c diff --git a/main.c b/main.c @@ -1,116 +0,0 @@ -#include "types.h" -#include "defs.h" -#include "param.h" -#include "memlayout.h" -#include "mmu.h" -#include "proc.h" -#include "x86.h" - -static void startothers(void); -static void mpmain(void) __attribute__((noreturn)); -extern pde_t *kpgdir; -extern char end[]; // first address after kernel loaded from ELF file - -// Bootstrap processor starts running C code here. -// Allocate a real stack and switch to it, first -// doing some setup required for memory allocator to work. -int -main(void) -{ - kinit1(end, P2V(4*1024*1024)); // phys page allocator - kvmalloc(); // kernel page table - mpinit(); // collect info about this machine - lapicinit(); - seginit(); // set up segments - cprintf("\ncpu%d: starting xv6\n\n", cpu->id); - picinit(); // interrupt controller - ioapicinit(); // another interrupt controller - consoleinit(); // I/O devices & their interrupts - uartinit(); // serial port - pinit(); // process table - tvinit(); // trap vectors - binit(); // buffer cache - fileinit(); // file table - iinit(); // inode cache - ideinit(); // disk - if(!ismp) - timerinit(); // uniprocessor timer - startothers(); // start other processors - kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers() - userinit(); // first user process - // Finish setting up this processor in mpmain. - mpmain(); -} - -// Other CPUs jump here from entryother.S. -static void -mpenter(void) -{ - switchkvm(); - seginit(); - lapicinit(); - mpmain(); -} - -// Common CPU setup code. -static void -mpmain(void) -{ - cprintf("cpu%d: starting\n", cpu->id); - idtinit(); // load idt register - xchg(&cpu->started, 1); // tell startothers() we're up - scheduler(); // start running processes -} - -pde_t entrypgdir[]; // For entry.S - -// Start the non-boot (AP) processors. -static void -startothers(void) -{ - extern uchar _binary_entryother_start[], _binary_entryother_size[]; - uchar *code; - struct cpu *c; - char *stack; - - // Write entry code to unused memory at 0x7000. - // The linker has placed the image of entryother.S in - // _binary_entryother_start. - code = p2v(0x7000); - memmove(code, _binary_entryother_start, (uint)_binary_entryother_size); - - for(c = cpus; c < cpus+ncpu; c++){ - if(c == cpus+cpunum()) // We've started already. - continue; - - // Tell entryother.S what stack to use, where to enter, and what - // pgdir to use. We cannot use kpgdir yet, because the AP processor - // is running in low memory, so we use entrypgdir for the APs too. - stack = kalloc(); - *(void**)(code-4) = stack + KSTACKSIZE; - *(void**)(code-8) = mpenter; - *(int**)(code-12) = (void *) v2p(entrypgdir); - - lapicstartap(c->id, v2p(code)); - - // wait for cpu to finish mpmain() - while(c->started == 0) - ; - } -} - -// Boot page table used in entry.S and entryother.S. -// Page directories (and page tables), must start on a page boundary, -// hence the "__aligned__" attribute. -// Use PTE_PS in page directory entry to enable 4Mbyte pages. -__attribute__((__aligned__(PGSIZE))) -pde_t entrypgdir[NPDENTRIES] = { - // Map VA's [0, 4MB) to PA's [0, 4MB) - [0] = (0) | PTE_P | PTE_W | PTE_PS, - // Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB) - [KERNBASE>>PDXSHIFT] = (0) | PTE_P | PTE_W | PTE_PS, -}; - -//PAGEBREAK! -// Blank page. - diff --git a/mkfs.c b/mkfs.c @@ -1,298 +0,0 @@ -#include <stdio.h> -#include <unistd.h> -#include <stdlib.h> -#include <string.h> -#include <fcntl.h> -#include <assert.h> - -#define stat xv6_stat // avoid clash with host struct stat -#include "include/types.h" -#include "include/fs.h" -#include "include/stat.h" -#include "include/param.h" - -#define static_assert(a, b) do { switch (0) case 0: case (a): ; } while (0) - -int nblocks = 985; -int nlog = LOGSIZE; -int ninodes = 200; -int size = 1024; - -int fsfd; -struct superblock sb; -char zeroes[512]; -uint freeblock; -uint usedblocks; -uint bitblocks; -uint freeinode = 1; - -void balloc(int); -void wsect(uint, void*); -void winode(uint, struct dinode*); -void rinode(uint inum, struct dinode *ip); -void rsect(uint sec, void *buf); -uint ialloc(ushort type); -void iappend(uint inum, void *p, int n); - -// convert to intel byte order -ushort -xshort(ushort x) -{ - ushort y; - uchar *a = (uchar*)&y; - a[0] = x; - a[1] = x >> 8; - return y; -} - -uint -xint(uint x) -{ - uint y; - uchar *a = (uchar*)&y; - a[0] = x; - a[1] = x >> 8; - a[2] = x >> 16; - a[3] = x >> 24; - return y; -} - -int -main(int argc, char *argv[]) -{ - int i, cc, fd; - uint rootino, inum, off; - struct dirent de; - char buf[512]; - struct dinode din; - - - static_assert(sizeof(int) == 4, "Integers must be 4 bytes!"); - - if(argc < 2){ - fprintf(stderr, "Usage: mkfs fs.img files...\n"); - exit(1); - } - - assert((512 % sizeof(struct dinode)) == 0); - assert((512 % sizeof(struct dirent)) == 0); - - fsfd = open(argv[1], O_RDWR|O_CREAT|O_TRUNC, 0666); - if(fsfd < 0){ - perror(argv[1]); - exit(1); - } - - sb.size = xint(size); - sb.nblocks = xint(nblocks); // so whole disk is size sectors - sb.ninodes = xint(ninodes); - sb.nlog = xint(nlog); - - bitblocks = size/(512*8) + 1; - usedblocks = ninodes / IPB + 3 + bitblocks; - freeblock = usedblocks; - - printf("used %d (bit %d ninode %zu) free %u log %u total %d\n", usedblocks, - bitblocks, ninodes/IPB + 1, freeblock, nlog, nblocks+usedblocks+nlog); - - assert(nblocks + usedblocks + nlog == size); - - for(i = 0; i < nblocks + usedblocks + nlog; i++) - wsect(i, zeroes); - - memset(buf, 0, sizeof(buf)); - memmove(buf, &sb, sizeof(sb)); - wsect(1, buf); - - rootino = ialloc(T_DIR); - assert(rootino == ROOTINO); - - bzero(&de, sizeof(de)); - de.inum = xshort(rootino); - strcpy(de.name, "."); - iappend(rootino, &de, sizeof(de)); - - bzero(&de, sizeof(de)); - de.inum = xshort(rootino); - strcpy(de.name, ".."); - iappend(rootino, &de, sizeof(de)); - - for(i = 2; i < argc; i++){ - assert(index(argv[i], '/') == 0); - - if((fd = open(argv[i], 0)) < 0){ - perror(argv[i]); - exit(1); - } - - // Skip leading _ in name when writing to file system. - // The binaries are named _rm, _cat, etc. to keep the - // build operating system from trying to execute them - // in place of system binaries like rm and cat. - if(argv[i][0] == '_') - ++argv[i]; - - inum = ialloc(T_FILE); - - bzero(&de, sizeof(de)); - de.inum = xshort(inum); - strncpy(de.name, argv[i], DIRSIZ); - iappend(rootino, &de, sizeof(de)); - - while((cc = read(fd, buf, sizeof(buf))) > 0) - iappend(inum, buf, cc); - - close(fd); - } - - // fix size of root inode dir - rinode(rootino, &din); - off = xint(din.size); - off = ((off/BSIZE) + 1) * BSIZE; - din.size = xint(off); - winode(rootino, &din); - - balloc(usedblocks); - - exit(0); -} - -void -wsect(uint sec, void *buf) -{ - if(lseek(fsfd, sec * 512L, 0) != sec * 512L){ - perror("lseek"); - exit(1); - } - if(write(fsfd, buf, 512) != 512){ - perror("write"); - exit(1); - } -} - -uint -i2b(uint inum) -{ - return (inum / IPB) + 2; -} - -void -winode(uint inum, struct dinode *ip) -{ - char buf[512]; - uint bn; - struct dinode *dip; - - bn = i2b(inum); - rsect(bn, buf); - dip = ((struct dinode*)buf) + (inum % IPB); - *dip = *ip; - wsect(bn, buf); -} - -void -rinode(uint inum, struct dinode *ip) -{ - char buf[512]; - uint bn; - struct dinode *dip; - - bn = i2b(inum); - rsect(bn, buf); - dip = ((struct dinode*)buf) + (inum % IPB); - *ip = *dip; -} - -void -rsect(uint sec, void *buf) -{ - if(lseek(fsfd, sec * 512L, 0) != sec * 512L){ - perror("lseek"); - exit(1); - } - if(read(fsfd, buf, 512) != 512){ - perror("read"); - exit(1); - } -} - -uint -ialloc(ushort type) -{ - uint inum = freeinode++; - struct dinode din; - - bzero(&din, sizeof(din)); - din.type = xshort(type); - din.nlink = xshort(1); - din.size = xint(0); - winode(inum, &din); - return inum; -} - -void -balloc(int used) -{ - uchar buf[512]; - int i; - - printf("balloc: first %d blocks have been allocated\n", used); - assert(used < 512*8); - bzero(buf, 512); - for(i = 0; i < used; i++){ - buf[i/8] = buf[i/8] | (0x1 << (i%8)); - } - printf("balloc: write bitmap block at sector %zu\n", ninodes/IPB + 3); - wsect(ninodes / IPB + 3, buf); -} - -#define min(a, b) ((a) < (b) ? (a) : (b)) - -void -iappend(uint inum, void *xp, int n) -{ - char *p = (char*)xp; - uint fbn, off, n1; - struct dinode din; - char buf[512]; - uint indirect[NINDIRECT]; - uint x; - - rinode(inum, &din); - - off = xint(din.size); - while(n > 0){ - fbn = off / 512; - assert(fbn < MAXFILE); - if(fbn < NDIRECT){ - if(xint(din.addrs[fbn]) == 0){ - din.addrs[fbn] = xint(freeblock++); - usedblocks++; - } - x = xint(din.addrs[fbn]); - } else { - if(xint(din.addrs[NDIRECT]) == 0){ - // printf("allocate indirect block\n"); - din.addrs[NDIRECT] = xint(freeblock++); - usedblocks++; - } - // printf("read indirect block\n"); - rsect(xint(din.addrs[NDIRECT]), (char*)indirect); - if(indirect[fbn - NDIRECT] == 0){ - indirect[fbn - NDIRECT] = xint(freeblock++); - usedblocks++; - wsect(xint(din.addrs[NDIRECT]), (char*)indirect); - } - x = xint(indirect[fbn-NDIRECT]); - } - n1 = min(n, (fbn + 1) * 512 - off); - rsect(x, buf); - bcopy(p, buf + off - (fbn * 512), n1); - wsect(x, buf); - n -= n1; - off += n1; - p += n1; - } - din.size = xint(off); - winode(inum, &din); -} diff --git a/proc.c b/proc.c @@ -1,459 +0,0 @@ -#include "types.h" -#include "defs.h" -#include "param.h" -#include "memlayout.h" -#include "mmu.h" -#include "x86.h" -#include "proc.h" -#include "spinlock.h" - -struct { - struct spinlock lock; - struct proc proc[NPROC]; -} ptable; - -static struct proc *initproc; - -int nextpid = 1; -extern void forkret(void); -extern void trapret(void); - -static void wakeup1(void *chan); - -void -pinit(void) -{ - initlock(&ptable.lock, "ptable"); -} - -//PAGEBREAK: 32 -// Look in the process table for an UNUSED proc. -// If found, change state to EMBRYO and initialize -// state required to run in the kernel. -// Otherwise return 0. -static struct proc* -allocproc(void) -{ - struct proc *p; - char *sp; - - acquire(&ptable.lock); - for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) - if(p->state == UNUSED) - goto found; - release(&ptable.lock); - return 0; - -found: - p->state = EMBRYO; - p->pid = nextpid++; - release(&ptable.lock); - - // Allocate kernel stack. - if((p->kstack = kalloc()) == 0){ - p->state = UNUSED; - return 0; - } - sp = p->kstack + KSTACKSIZE; - - // Leave room for trap frame. - sp -= sizeof *p->tf; - p->tf = (struct trapframe*)sp; - - // Set up new context to start executing at forkret, - // which returns to trapret. - sp -= 4; - *(uint*)sp = (uint)trapret; - - sp -= sizeof *p->context; - p->context = (struct context*)sp; - memset(p->context, 0, sizeof *p->context); - p->context->eip = (uint)forkret; - - return p; -} - -//PAGEBREAK: 32 -// Set up first user process. -void -userinit(void) -{ - struct proc *p; - extern char _binary_initcode_start[], _binary_initcode_size[]; - - p = allocproc(); - initproc = p; - if((p->pgdir = setupkvm()) == 0) - panic("userinit: out of memory?"); - inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size); - p->sz = PGSIZE; - memset(p->tf, 0, sizeof(*p->tf)); - p->tf->cs = (SEG_UCODE << 3) | DPL_USER; - p->tf->ds = (SEG_UDATA << 3) | DPL_USER; - p->tf->es = p->tf->ds; - p->tf->ss = p->tf->ds; - p->tf->eflags = FL_IF; - p->tf->esp = PGSIZE; - p->tf->eip = 0; // beginning of initcode.S - - safestrcpy(p->name, "initcode", sizeof(p->name)); - p->cwd = namei("/"); - - p->state = RUNNABLE; -} - -// Grow current process's memory by n bytes. -// Return 0 on success, -1 on failure. -int -growproc(int n) -{ - uint sz; - - sz = proc->sz; - if(n > 0){ - if((sz = allocuvm(proc->pgdir, sz, sz + n)) == 0) - return -1; - } else if(n < 0){ - if((sz = deallocuvm(proc->pgdir, sz, sz + n)) == 0) - return -1; - } - proc->sz = sz; - switchuvm(proc); - return 0; -} - -// Create a new process copying p as the parent. -// Sets up stack to return as if from system call. -// Caller must set state of returned proc to RUNNABLE. -int -fork(void) -{ - int i, pid; - struct proc *np; - - // Allocate process. - if((np = allocproc()) == 0) - return -1; - - // Copy process state from p. - if((np->pgdir = copyuvm(proc->pgdir, proc->sz)) == 0){ - kfree(np->kstack); - np->kstack = 0; - np->state = UNUSED; - return -1; - } - np->sz = proc->sz; - np->parent = proc; - *np->tf = *proc->tf; - - // Clear %eax so that fork returns 0 in the child. - np->tf->eax = 0; - - for(i = 0; i < NOFILE; i++) - if(proc->ofile[i]) - np->ofile[i] = filedup(proc->ofile[i]); - np->cwd = idup(proc->cwd); - - pid = np->pid; - np->state = RUNNABLE; - safestrcpy(np->name, proc->name, sizeof(proc->name)); - return pid; -} - -// Exit the current process. Does not return. -// An exited process remains in the zombie state -// until its parent calls wait() to find out it exited. -void -exit(void) -{ - struct proc *p; - int fd; - - if(proc == initproc) - panic("init exiting"); - - // Close all open files. - for(fd = 0; fd < NOFILE; fd++){ - if(proc->ofile[fd]){ - fileclose(proc->ofile[fd]); - proc->ofile[fd] = 0; - } - } - - iput(proc->cwd); - proc->cwd = 0; - - acquire(&ptable.lock); - - // Parent might be sleeping in wait(). - wakeup1(proc->parent); - - // Pass abandoned children to init. - for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ - if(p->parent == proc){ - p->parent = initproc; - if(p->state == ZOMBIE) - wakeup1(initproc); - } - } - - // Jump into the scheduler, never to return. - proc->state = ZOMBIE; - sched(); - panic("zombie exit"); -} - -// Wait for a child process to exit and return its pid. -// Return -1 if this process has no children. -int -wait(void) -{ - struct proc *p; - int havekids, pid; - - acquire(&ptable.lock); - for(;;){ - // Scan through table looking for zombie children. - havekids = 0; - for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ - if(p->parent != proc) - continue; - havekids = 1; - if(p->state == ZOMBIE){ - // Found one. - pid = p->pid; - kfree(p->kstack); - p->kstack = 0; - freevm(p->pgdir); - p->state = UNUSED; - p->pid = 0; - p->parent = 0; - p->name[0] = 0; - p->killed = 0; - release(&ptable.lock); - return pid; - } - } - - // No point waiting if we don't have any children. - if(!havekids || proc->killed){ - release(&ptable.lock); - return -1; - } - - // Wait for children to exit. (See wakeup1 call in proc_exit.) - sleep(proc, &ptable.lock); //DOC: wait-sleep - } -} - -//PAGEBREAK: 42 -// Per-CPU process scheduler. -// Each CPU calls scheduler() after setting itself up. -// Scheduler never returns. It loops, doing: -// - choose a process to run -// - swtch to start running that process -// - eventually that process transfers control -// via swtch back to the scheduler. -void -scheduler(void) -{ - struct proc *p; - - for(;;){ - // Enable interrupts on this processor. - sti(); - - // Loop over process table looking for process to run. - acquire(&ptable.lock); - for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ - if(p->state != RUNNABLE) - continue; - - // Switch to chosen process. It is the process's job - // to release ptable.lock and then reacquire it - // before jumping back to us. - proc = p; - switchuvm(p); - p->state = RUNNING; - swtch(&cpu->scheduler, proc->context); - switchkvm(); - - // Process is done running for now. - // It should have changed its p->state before coming back. - proc = 0; - } - release(&ptable.lock); - - } -} - -// Enter scheduler. Must hold only ptable.lock -// and have changed proc->state. -void -sched(void) -{ - int intena; - - if(!holding(&ptable.lock)) - panic("sched ptable.lock"); - if(cpu->ncli != 1) - panic("sched locks"); - if(proc->state == RUNNING) - panic("sched running"); - if(readeflags()&FL_IF) - panic("sched interruptible"); - intena = cpu->intena; - swtch(&proc->context, cpu->scheduler); - cpu->intena = intena; -} - -// Give up the CPU for one scheduling round. -void -yield(void) -{ - acquire(&ptable.lock); //DOC: yieldlock - proc->state = RUNNABLE; - sched(); - release(&ptable.lock); -} - -// A fork child's very first scheduling by scheduler() -// will swtch here. "Return" to user space. -void -forkret(void) -{ - static int first = 1; - // Still holding ptable.lock from scheduler. - release(&ptable.lock); - - if (first) { - // Some initialization functions must be run in the context - // of a regular process (e.g., they call sleep), and thus cannot - // be run from main(). - first = 0; - initlog(); - } - - // Return to "caller", actually trapret (see allocproc). -} - -// Atomically release lock and sleep on chan. -// Reacquires lock when awakened. -void -sleep(void *chan, struct spinlock *lk) -{ - if(proc == 0) - panic("sleep"); - - if(lk == 0) - panic("sleep without lk"); - - // Must acquire ptable.lock in order to - // change p->state and then call sched. - // Once we hold ptable.lock, we can be - // guaranteed that we won't miss any wakeup - // (wakeup runs with ptable.lock locked), - // so it's okay to release lk. - if(lk != &ptable.lock){ //DOC: sleeplock0 - acquire(&ptable.lock); //DOC: sleeplock1 - release(lk); - } - - // Go to sleep. - proc->chan = chan; - proc->state = SLEEPING; - sched(); - - // Tidy up. - proc->chan = 0; - - // Reacquire original lock. - if(lk != &ptable.lock){ //DOC: sleeplock2 - release(&ptable.lock); - acquire(lk); - } -} - -//PAGEBREAK! -// Wake up all processes sleeping on chan. -// The ptable lock must be held. -static void -wakeup1(void *chan) -{ - struct proc *p; - - for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) - if(p->state == SLEEPING && p->chan == chan) - p->state = RUNNABLE; -} - -// Wake up all processes sleeping on chan. -void -wakeup(void *chan) -{ - acquire(&ptable.lock); - wakeup1(chan); - release(&ptable.lock); -} - -// Kill the process with the given pid. -// Process won't exit until it returns -// to user space (see trap in trap.c). -int -kill(int pid) -{ - struct proc *p; - - acquire(&ptable.lock); - for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ - if(p->pid == pid){ - p->killed = 1; - // Wake process from sleep if necessary. - if(p->state == SLEEPING) - p->state = RUNNABLE; - release(&ptable.lock); - return 0; - } - } - release(&ptable.lock); - return -1; -} - -//PAGEBREAK: 36 -// Print a process listing to console. For debugging. -// Runs when user types ^P on console. -// No lock to avoid wedging a stuck machine further. -void -procdump(void) -{ - static char *states[] = { - [UNUSED] "unused", - [EMBRYO] "embryo", - [SLEEPING] "sleep ", - [RUNNABLE] "runble", - [RUNNING] "run ", - [ZOMBIE] "zombie" - }; - int i; - struct proc *p; - char *state; - uint pc[10]; - - for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){ - if(p->state == UNUSED) - continue; - if(p->state >= 0 && p->state < NELEM(states) && states[p->state]) - state = states[p->state]; - else - state = "???"; - cprintf("%d %s %s", p->pid, state, p->name); - if(p->state == SLEEPING){ - getcallerpcs((uint*)p->context->ebp+2, pc); - for(i=0; i<10 && pc[i] != 0; i++) - cprintf(" %p", pc[i]); - } - cprintf("\n"); - } -} - - diff --git a/dot-bochsrc b/tools/dot-bochsrc diff --git a/tools/mkfs.c b/tools/mkfs.c @@ -0,0 +1,296 @@ +#include <stdio.h> +#include <unistd.h> +#include <stdlib.h> +#include <string.h> +#include <fcntl.h> +#include <assert.h> + +#define stat xv6_stat // avoid clash with host struct stat +#include "../include/types.h" +#include "../include/fs.h" +#include "../include/stat.h" +#include "../include/param.h" + +#define static_assert(a, b) do { switch (0) case 0: case (a): ; } while (0) + +int nblocks = 985; +int nlog = LOGSIZE; +int ninodes = 200; +int size = 1024; + +int fsfd; +struct superblock sb; +char zeroes[512]; +uint freeblock; +uint usedblocks; +uint bitblocks; +uint freeinode = 1; + +void balloc(int); +void wsect(uint, void*); +void winode(uint, struct dinode*); +void rinode(uint inum, struct dinode *ip); +void rsect(uint sec, void *buf); +uint ialloc(ushort type); +void iappend(uint inum, void *p, int n); + +// convert to intel byte order +ushort +xshort(ushort x) +{ + ushort y; + uchar *a = (uchar*)&y; + a[0] = x; + a[1] = x >> 8; + return y; +} + +uint +xint(uint x) +{ + uint y; + uchar *a = (uchar*)&y; + a[0] = x; + a[1] = x >> 8; + a[2] = x >> 16; + a[3] = x >> 24; + return y; +} + +int +main(int argc, char *argv[]) +{ + int i, cc, fd; + uint rootino, inum, off; + struct dirent de; + char buf[512]; + struct dinode din; + + + static_assert(sizeof(int) == 4, "Integers must be 4 bytes!"); + + if(argc < 2){ + fprintf(stderr, "Usage: mkfs fs.img files...\n"); + exit(1); + } + + assert((512 % sizeof(struct dinode)) == 0); + assert((512 % sizeof(struct dirent)) == 0); + + fsfd = open(argv[1], O_RDWR|O_CREAT|O_TRUNC, 0666); + if(fsfd < 0){ + perror(argv[1]); + exit(1); + } + + sb.size = xint(size); + sb.nblocks = xint(nblocks); // so whole disk is size sectors + sb.ninodes = xint(ninodes); + sb.nlog = xint(nlog); + + bitblocks = size/(512*8) + 1; + usedblocks = ninodes / IPB + 3 + bitblocks; + freeblock = usedblocks; + + printf("used %d (bit %d ninode %zu) free %u log %u total %d\n", usedblocks, + bitblocks, ninodes/IPB + 1, freeblock, nlog, nblocks+usedblocks+nlog); + + assert(nblocks + usedblocks + nlog == size); + + for(i = 0; i < nblocks + usedblocks + nlog; i++) + wsect(i, zeroes); + + memset(buf, 0, sizeof(buf)); + memmove(buf, &sb, sizeof(sb)); + wsect(1, buf); + + rootino = ialloc(T_DIR); + assert(rootino == ROOTINO); + + bzero(&de, sizeof(de)); + de.inum = xshort(rootino); + strcpy(de.name, "."); + iappend(rootino, &de, sizeof(de)); + + bzero(&de, sizeof(de)); + de.inum = xshort(rootino); + strcpy(de.name, ".."); + iappend(rootino, &de, sizeof(de)); + + for(i = 2; i < argc; i++){ + char *name = argv[i]; + + if (!strncmp(name, "fs/", 3)) + name += 3; + + assert(index(name, '/') == 0); + + if((fd = open(argv[i], 0)) < 0){ + perror(argv[i]); + exit(1); + } + + inum = ialloc(T_FILE); + + bzero(&de, sizeof(de)); + de.inum = xshort(inum); + strncpy(de.name, name, DIRSIZ); + iappend(rootino, &de, sizeof(de)); + + while((cc = read(fd, buf, sizeof(buf))) > 0) + iappend(inum, buf, cc); + + close(fd); + } + + // fix size of root inode dir + rinode(rootino, &din); + off = xint(din.size); + off = ((off/BSIZE) + 1) * BSIZE; + din.size = xint(off); + winode(rootino, &din); + + balloc(usedblocks); + + exit(0); +} + +void +wsect(uint sec, void *buf) +{ + if(lseek(fsfd, sec * 512L, 0) != sec * 512L){ + perror("lseek"); + exit(1); + } + if(write(fsfd, buf, 512) != 512){ + perror("write"); + exit(1); + } +} + +uint +i2b(uint inum) +{ + return (inum / IPB) + 2; +} + +void +winode(uint inum, struct dinode *ip) +{ + char buf[512]; + uint bn; + struct dinode *dip; + + bn = i2b(inum); + rsect(bn, buf); + dip = ((struct dinode*)buf) + (inum % IPB); + *dip = *ip; + wsect(bn, buf); +} + +void +rinode(uint inum, struct dinode *ip) +{ + char buf[512]; + uint bn; + struct dinode *dip; + + bn = i2b(inum); + rsect(bn, buf); + dip = ((struct dinode*)buf) + (inum % IPB); + *ip = *dip; +} + +void +rsect(uint sec, void *buf) +{ + if(lseek(fsfd, sec * 512L, 0) != sec * 512L){ + perror("lseek"); + exit(1); + } + if(read(fsfd, buf, 512) != 512){ + perror("read"); + exit(1); + } +} + +uint +ialloc(ushort type) +{ + uint inum = freeinode++; + struct dinode din; + + bzero(&din, sizeof(din)); + din.type = xshort(type); + din.nlink = xshort(1); + din.size = xint(0); + winode(inum, &din); + return inum; +} + +void +balloc(int used) +{ + uchar buf[512]; + int i; + + printf("balloc: first %d blocks have been allocated\n", used); + assert(used < 512*8); + bzero(buf, 512); + for(i = 0; i < used; i++){ + buf[i/8] = buf[i/8] | (0x1 << (i%8)); + } + printf("balloc: write bitmap block at sector %zu\n", ninodes/IPB + 3); + wsect(ninodes / IPB + 3, buf); +} + +#define min(a, b) ((a) < (b) ? (a) : (b)) + +void +iappend(uint inum, void *xp, int n) +{ + char *p = (char*)xp; + uint fbn, off, n1; + struct dinode din; + char buf[512]; + uint indirect[NINDIRECT]; + uint x; + + rinode(inum, &din); + + off = xint(din.size); + while(n > 0){ + fbn = off / 512; + assert(fbn < MAXFILE); + if(fbn < NDIRECT){ + if(xint(din.addrs[fbn]) == 0){ + din.addrs[fbn] = xint(freeblock++); + usedblocks++; + } + x = xint(din.addrs[fbn]); + } else { + if(xint(din.addrs[NDIRECT]) == 0){ + // printf("allocate indirect block\n"); + din.addrs[NDIRECT] = xint(freeblock++); + usedblocks++; + } + // printf("read indirect block\n"); + rsect(xint(din.addrs[NDIRECT]), (char*)indirect); + if(indirect[fbn - NDIRECT] == 0){ + indirect[fbn - NDIRECT] = xint(freeblock++); + usedblocks++; + wsect(xint(din.addrs[NDIRECT]), (char*)indirect); + } + x = xint(indirect[fbn-NDIRECT]); + } + n1 = min(n, (fbn + 1) * 512 - off); + rsect(x, buf); + bcopy(p, buf + off - (fbn * 512), n1); + wsect(x, buf); + n -= n1; + off += n1; + p += n1; + } + din.size = xint(off); + winode(inum, &din); +} diff --git a/printpcs b/tools/printpcs diff --git a/sign.pl b/tools/sign.pl diff --git a/sleep1.p b/tools/sleep1.p diff --git a/spinp b/tools/spinp diff --git a/vectors.pl b/tools/vectors.pl diff --git a/printf.c b/ulib/printf.c diff --git a/ulib.c b/ulib/ulib.c diff --git a/umalloc.c b/ulib/umalloc.c diff --git a/usys.S b/ulib/usys.S