diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | defs.h | 2 | ||||
| -rw-r--r-- | fs.c | 86 | ||||
| -rw-r--r-- | fs.h | 8 | ||||
| -rw-r--r-- | mkfs.c | 32 | ||||
| -rw-r--r-- | proc.c | 9 | ||||
| -rw-r--r-- | syscall.c | 24 | ||||
| -rw-r--r-- | umalloc.c | 90 | ||||
| -rw-r--r-- | user.h | 3 | ||||
| -rw-r--r-- | userfs.c | 6 |
10 files changed, 210 insertions, 52 deletions
@@ -57,7 +57,7 @@ kernel : $(OBJS) bootother.S init vectors.S : vectors.pl perl vectors.pl > vectors.S -ULIB = ulib.o usys.o printf.o +ULIB = ulib.o usys.o printf.o umalloc.o user1 : user1.o $(ULIB) $(LD) -N -e main -Ttext 0 -o user1 user1.o $(ULIB) @@ -16,7 +16,7 @@ struct jmpbuf; void setupsegs(struct proc *); struct proc * copyproc(struct proc*); struct spinlock; -int growproc(int); +char *growproc(int); void sleep(void *, struct spinlock *); void wakeup(void *); void scheduler(void); @@ -231,24 +231,46 @@ uint bmap(struct inode *ip, uint bn) { unsigned x; + uint *a; + struct buf *inbp; - if(bn >= NDIRECT) + if(bn >= MAXFILE) panic("bmap 1"); - x = ip->addrs[bn]; - if(x == 0) - panic("bmap 2"); + if (bn < NDIRECT) { + x = ip->addrs[bn]; + if (x == 0) + panic("bmap 2"); + } else { + cprintf("indirect block read\n"); + inbp = bread(ip->dev, INDIRECT); + a = (uint *) inbp->data; + x = a[bn - NDIRECT]; + brelse(inbp); + if (x == 0) + panic("bmap 3"); + } return x; } void iunlink(struct inode *ip) { - int i; + int i, j; // free inode, its blocks, and remove dir entry - for (i = 0; i < NDIRECT; i++) { + for (i = 0; i < NADDRS; i++) { if (ip->addrs[i] != 0) { - bfree(ip->dev, ip->addrs[i]); + if (i == INDIRECT) { + for (j = 0; j < NINDIRECT; j++) { + uint *a = (uint *) (ip->addrs[i]); + if (a[j] != 0) { + bfree(ip->dev, a[j]); + a[j] = 0; + } + } + } + else + bfree(ip->dev, ip->addrs[i]); ip->addrs[i] = 0; } } @@ -333,30 +355,62 @@ readi(struct inode *ip, char *dst, uint off, uint n) } int +newblock(struct inode *ip, uint lbn) +{ + struct buf *inbp; + uint *inaddrs; + uint b; + + if (lbn < NDIRECT) { + if (ip->addrs[lbn] == 0) { + b = balloc(ip->dev); + if (b <= 0) return -1; + ip->addrs[lbn] = b; + } + } else { + cprintf("newblock: use indirect block\n"); + if (ip->addrs[INDIRECT] == 0) { + cprintf("newblock: allocate indirect block\n"); + b = balloc(ip->dev); + if (b <= 0) return -1; + ip->addrs[INDIRECT] = b; + } + inbp = bread(ip->dev, bmap(ip, INDIRECT)); + inaddrs = (uint *) inbp->data; + if (inaddrs[lbn - NDIRECT] == 0) { + b = balloc(ip->dev); + if (b <= 0) return -1; + inaddrs[lbn - NDIRECT] = b; + bwrite(inbp, INDIRECT); + } + brelse(inbp); + } + return 0; +} + +int writei(struct inode *ip, char *addr, uint off, uint n) { if (ip->type == T_DEV) { if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].d_write) return -1; return devsw[ip->major].d_write (ip->minor, addr, n); - } else if (ip->type == T_FILE || ip->type == T_DIR) { // XXX dir here too? + } else if (ip->type == T_FILE || ip->type == T_DIR) { struct buf *bp; int r = 0; int m; int lbn; - uint b; while (r < n) { lbn = off / BSIZE; - if (lbn >= NDIRECT) return r; - if (ip->addrs[lbn] == 0) { - b = balloc(ip->dev); - if (b <= 0) return r; - ip->addrs[lbn] = b; + if (lbn >= MAXFILE) return r; + if (newblock(ip, lbn) < 0) { + cprintf("newblock failed\n"); + return r; } m = min(BSIZE - off % BSIZE, n-r); - bp = bread(ip->dev, bmap(ip, off / BSIZE)); + bp = bread(ip->dev, bmap(ip, lbn)); memmove (bp->data + off % BSIZE, addr, m); - bwrite (bp, bmap(ip, off/BSIZE)); + bwrite (bp, bmap(ip, lbn)); brelse (bp); r += m; off += m; @@ -9,7 +9,11 @@ struct superblock{ uint ninodes; }; -#define NDIRECT 13 +#define NADDRS NDIRECT+1 +#define NDIRECT 12 +#define INDIRECT 12 +#define NINDIRECT (BSIZE / sizeof(uint)) +#define MAXFILE (NDIRECT + NINDIRECT) struct dinode { short type; @@ -17,7 +21,7 @@ struct dinode { short minor; short nlink; uint size; - uint addrs[NDIRECT]; + uint addrs[NADDRS]; }; #define T_DIR 1 @@ -106,6 +106,7 @@ main(int argc, char *argv[]) for(i = 2; i < argc; i++){ assert(index(argv[i], '/') == 0); + if((fd = open(argv[i], 0)) < 0){ perror(argv[i]); exit(1); @@ -234,21 +235,40 @@ iappend(uint inum, void *xp, int n) 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 < NDIRECT); - if(din.addrs[fbn] == 0) { - din.addrs[fbn] = xint(freeblock++); - usedblocks++; + 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[INDIRECT]) == 0) { + printf("allocate indirect block\n"); + din.addrs[INDIRECT] = xint(freeblock++); + usedblocks++; + } + printf("read indirect block\n"); + rsect(xint(din.addrs[INDIRECT]), (char *) indirect); + if (indirect[fbn - NDIRECT] == 0) { + indirect[fbn - NDIRECT] = xint(freeblock++); + usedblocks++; + wsect(INDIRECT, (char *) indirect); + } + x = xint(indirect[fbn-NDIRECT]); } n1 = min(n, (fbn + 1) * 512 - off); - rsect(xint(din.addrs[fbn]), buf); + rsect(x, buf); bcopy(p, buf + off - (fbn * 512), n1); - wsect(xint(din.addrs[fbn]), buf); + wsect(x, buf); n -= n1; off += n1; p += n1; @@ -138,22 +138,23 @@ copyproc(struct proc* p) return np; } -int +char * growproc(int n) { struct proc *cp = curproc[cpu()]; char *newmem, *oldmem; newmem = kalloc(cp->sz + n); - if(newmem == 0) return -1; + if(newmem == 0) return (char *) -1; memmove(newmem, cp->mem, cp->sz); memset(newmem + cp->sz, 0, n); oldmem = cp->mem; cp->mem = newmem; kfree(oldmem, cp->sz); cp->sz += n; - cprintf("growproc: added %d bytes\n", n); - return 0; + cprintf("growproc: added %d bytes starting at address 0x%x\n", n, + newmem + cp->sz - n); + return newmem + cp->sz - n; } // Per-CPU process scheduler. @@ -404,7 +404,6 @@ sys_dup(void) { struct proc *cp = curproc[cpu()]; uint fd, ufd1; - struct fd *fd1; if(fetcharg(0, &fd) < 0) return -1; @@ -414,25 +413,11 @@ sys_dup(void) return -1; if (cp->fds[fd]->type != FD_PIPE && cp->fds[fd]->type != FD_FILE) return -1; - - if ((fd1 = fd_alloc()) == 0) { - return -1; - } if ((ufd1 = fd_ualloc()) < 0) { - fd_close(fd1); return -1; } - cp->fds[ufd1] = fd1; - fd1->type = cp->fds[fd]->type; - fd1->readable = cp->fds[fd]->readable; - fd1->writeable = cp->fds[fd]->writeable; - if (cp->fds[fd]->type == FD_FILE) { - fd1->ip = cp->fds[fd]->ip; - iincref(fd1->ip); - } else if (cp->fds[fd]->type == FD_PIPE) { - fd1->pipe = cp->fds[fd]->pipe; - } - fd1->off = cp->fds[fd]->off; + cp->fds[ufd1] = cp->fds[fd]; + fd_incref(cp->fds[ufd1]); return ufd1; } @@ -462,14 +447,15 @@ sys_getpid(void) int sys_sbrk(void) { - int r, n; + char *r; + int n; struct proc *cp = curproc[cpu()]; if(fetcharg(0, &n) < 0) return -1; r = growproc(n); setupsegs(cp); - return r; + return (int) r; } int diff --git a/umalloc.c b/umalloc.c new file mode 100644 index 0000000..c0fc4ca --- /dev/null +++ b/umalloc.c @@ -0,0 +1,90 @@ +#include "types.h" +#include "stat.h" +#include "user.h" +#include "param.h" + +// Memory allocator by Kernighan and Ritchie, The C programming Language, +// 2nd ed. Section 8.7. + +typedef long Align; + +union header { + struct { + union header *ptr; + uint size; + } s; + Align x; +}; + +typedef union header Header; + +static Header base; +static Header *freep = 0; + +void +free(void *ap) +{ + Header *bp, *p; + + bp = (Header *) ap - 1; + for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) + if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) + break; + if (bp + bp->s.size == p->s.ptr) { + bp->s.size += p->s.ptr->s.size; + bp->s.ptr = p->s.ptr->s.ptr; + } else + bp->s.ptr = p->s.ptr; + if (p + p->s.size == bp) { + p->s.size += bp->s.size; + p->s.ptr = bp->s.ptr; + } else + p->s.ptr = bp; + freep = p; +} + +static Header * +morecore(uint nu) +{ + char *cp; + Header *up; + + if (nu < PAGE) + nu = PAGE; + cp = sbrk(nu * sizeof(Header)); + if (cp == (char *) -1) + return 0; + up = (Header *) cp; + up->s.size = nu; + free((void *)(up + 1)); + return freep; +} + +void * +malloc(uint nbytes) +{ + Header *p, *prevp; + uint nunits; + + nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1; + if ((prevp = freep) == 0) { + base.s.ptr = freep = prevp = &base; + base.s.size = 0; + } + for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) { + if (p->s.size >= nunits) { + if (p->s.size == nunits) + prevp->s.ptr = p->s.ptr; + else { + p->s.size -= nunits; + p += p->s.size; + p->s.size = nunits; + } + freep = prevp; + return (void *) (p + 1); + } + if (p == freep) + if ((p = morecore(nunits)) == 0) + return 0; + } +} @@ -19,6 +19,7 @@ int mkdir(char *); int chdir(char *); int dup(int); int getpid(); +char *sbrk(int); int stat(char *, struct stat *stat); int puts(char*); @@ -29,3 +30,5 @@ void printf(int fd, char *fmt, ...); char *gets(char *, int max); unsigned int strlen(char *); void * memset(void *dst, int c, unsigned int n); +void *mallic(uint); +void free(void *); @@ -21,7 +21,7 @@ main(void) printf(stdout, "userfs is running\n"); if (sbrk(4096) < 0) { - printf(stdout, "sbrk failed\n"); + printf(stdout, "sbrk failed\n"); } fd = open("echo", 0); @@ -46,10 +46,10 @@ main(void) } for (i = 0; i < 100; i++) { if (write (fd, "aaaaaaaaaa", 10) != 10) { - printf(stdout, "error: write new file failed\n"); + printf(stdout, "error: write aa %d new file failed\n", i); } if (write (fd, "bbbbbbbbbb", 10) != 10) { - printf(stdout, "error: write new file failed\n"); + printf(stdout, "error: write bb %d new file failed\n", i); } } printf(stdout, "writes done\n"); |