user-level malloc (untested)

nit in sbrk
indirect block
fix dup to share fd struct

10 files changed, 210 insertions, 52 deletions

diff --git a/Makefile b/Makefile
index a40289f..4a890a9 100644
--- a/Makefile
+++ b/Makefile
@@ -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)
diff --git a/defs.h b/defs.h
index b8b7b84..cb5175d 100644
--- a/defs.h
+++ b/defs.h
@@ -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);
diff --git a/fs.c b/fs.c
index ed62970..6a1c1d0 100644
--- a/fs.c
+++ b/fs.c
@@ -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;
diff --git a/fs.h b/fs.h
index 2112c25..de81e81 100644
--- a/fs.h
+++ b/fs.h
@@ -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
diff --git a/mkfs.c b/mkfs.c
index 15870d9..2d84610 100644
--- a/mkfs.c
+++ b/mkfs.c
@@ -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;
diff --git a/proc.c b/proc.c
index 7382add..b65bb70 100644
--- a/proc.c
+++ b/proc.c
@@ -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. 
diff --git a/syscall.c b/syscall.c
index 39c6821..39cd107 100644
--- a/syscall.c
+++ b/syscall.c
@@ -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;
+  }
+}
diff --git a/user.h b/user.h
index cc82ccf..b5ea91d 100644
--- a/user.h
+++ b/user.h
@@ -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 *);
diff --git a/userfs.c b/userfs.c
index d1cd49e..54bc334 100644
--- a/userfs.c
+++ b/userfs.c
@@ -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");