summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorkaashoek <kaashoek>2006-08-09 01:09:36 +0000
committerkaashoek <kaashoek>2006-08-09 01:09:36 +0000
commit241113985f7122c65345885dec02e008601ff7ef (patch)
treea3cfc32c380282f1a4d70e86041b6d6c15c519f4
parent0e84a0ec6e7893dad13dff9a958c5bc987b79c82 (diff)
downloadxv6-labs-241113985f7122c65345885dec02e008601ff7ef.tar.gz
xv6-labs-241113985f7122c65345885dec02e008601ff7ef.tar.bz2
xv6-labs-241113985f7122c65345885dec02e008601ff7ef.zip
block bitmap
balloc
-rw-r--r--fs.c74
-rw-r--r--fs.h17
-rw-r--r--mkfs.c42
3 files changed, 103 insertions, 30 deletions
diff --git a/fs.c b/fs.c
index 6774350..e194f59 100644
--- a/fs.c
+++ b/fs.c
@@ -16,6 +16,43 @@ struct spinlock inode_table_lock = { "inode_table" };
uint rootdev = 1;
+static uint
+balloc(uint dev)
+{
+ int b;
+ struct buf *bp;
+ struct superblock *sb;
+ int bi;
+ int size;
+ int ninodes;
+ uchar m;
+
+ bp = bread(dev, 1);
+ sb = (struct superblock *) bp->data;
+ size = sb->size;
+ ninodes = sb->ninodes;
+
+ for (b = 0; b < size; b++) {
+ if (b % BPB == 0) {
+ brelse(bp);
+ bp = bread(dev, BBLOCK(b, ninodes));
+ }
+ bi = b % BPB;
+ m = 0x1 << (bi % 8);
+ if ((bp->data[bi/8] & m) == 0) { // is block free?
+ break;
+ }
+ }
+ if (b >= size)
+ panic("balloc: out of blocks\n");
+
+ cprintf ("balloc: allocate block %d\n", b);
+ bp->data[bi/8] |= 0x1 << (bi % 8);
+ bwrite (dev, bp, BBLOCK(b, ninodes)); // mark it allocated on disk
+ return b;
+}
+
+
// returns an inode with busy set and incremented reference count.
struct inode *
iget(uint dev, uint inum)
@@ -51,7 +88,7 @@ iget(uint dev, uint inum)
release(&inode_table_lock);
- bp = bread(dev, inum / IPB + 2);
+ bp = bread(dev, IBLOCK(inum));
dip = &((struct dinode *)(bp->data))[inum % IPB];
nip->type = dip->type;
nip->major = dip->major;
@@ -76,12 +113,12 @@ ialloc(uint dev, short type)
struct buf *bp;
bp = bread(dev, 1);
- sb = (struct superblock *) bp;
+ sb = (struct superblock *) bp->data;
ninodes = sb->ninodes;
brelse(bp);
-
+
for (inum = 1; inum < ninodes; inum++) { // loop over inode blocks
- bp = bread(dev, inum / IPB + 2);
+ bp = bread(dev, IBLOCK(inum));
dip = &((struct dinode *)(bp->data))[inum % IPB];
if (dip->type == 0) { // a free inode
break;
@@ -90,13 +127,12 @@ ialloc(uint dev, short type)
}
if (inum >= ninodes) {
- cprintf ("ialloc: no inodes left\n");
- return 0;
+ panic ("ialloc: no inodes left\n");
}
cprintf ("ialloc: %d\n", inum);
dip->type = type;
- bwrite (dev, bp, inum / IPB + 2); // mark it allocated on the disk
+ bwrite (dev, bp, IBLOCK(inum)); // mark it allocated on the disk
brelse(bp);
ip = iget (dev, inum);
return ip;
@@ -108,14 +144,14 @@ iupdate (struct inode *ip)
struct buf *bp;
struct dinode *dip;
- bp = bread(ip->dev, ip->inum / IPB + 2);
+ bp = bread(ip->dev, IBLOCK(ip->inum));
dip = &((struct dinode *)(bp->data))[ip->inum % IPB];
dip->type = ip->type;
dip->major = ip->major;
dip->minor = ip->minor;
dip->nlink = ip->nlink;
dip->size = ip->size;
- bwrite (ip->dev, bp, ip->inum / IPB + 2); // mark it allocated on the disk
+ bwrite (ip->dev, bp, IBLOCK(ip->inum)); // mark it allocated on the disk
brelse(bp);
}
@@ -203,10 +239,10 @@ readi(struct inode *ip, void *xdst, uint off, uint n)
struct buf *bp;
while(n > 0 && off < ip->size){
- bp = bread(ip->dev, bmap(ip, off / 512));
+ bp = bread(ip->dev, bmap(ip, off / BSIZE));
n1 = min(n, ip->size - off);
- n1 = min(n1, 512 - (off % 512));
- memmove(dst, bp->data + (off % 512), n1);
+ n1 = min(n1, BSIZE - (off % BSIZE));
+ memmove(dst, bp->data + (off % BSIZE), n1);
n -= n1;
off += n1;
dst += n1;
@@ -241,10 +277,10 @@ namei(char *path)
return 0;
}
- for(off = 0; off < dp->size; off += 512){
- bp = bread(dp->dev, bmap(dp, off / 512));
+ for(off = 0; off < dp->size; off += BSIZE){
+ bp = bread(dp->dev, bmap(dp, off / BSIZE));
for(ep = (struct dirent *) bp->data;
- ep < (struct dirent *) (bp->data + 512);
+ ep < (struct dirent *) (bp->data + BSIZE);
ep++){
if(ep->inum == 0)
continue;
@@ -288,10 +324,10 @@ mknod(struct inode *dp, char *cp, short type, short major, short minor)
ip->major = major;
ip->minor = minor;
- for(off = 0; off < dp->size; off += 512) {
- bp = bread(dp->dev, bmap(dp, off / 512));
+ for(off = 0; off < dp->size; off += BSIZE) {
+ bp = bread(dp->dev, bmap(dp, off / BSIZE));
for(ep = (struct dirent *) bp->data;
- ep < (struct dirent *) (bp->data + 512);
+ ep < (struct dirent *) (bp->data + BSIZE);
ep++){
if(ep->inum == 0) {
goto found;
@@ -304,7 +340,7 @@ mknod(struct inode *dp, char *cp, short type, short major, short minor)
found:
ep->inum = ip->inum;
for(i = 0; i < DIRSIZ && cp[i]; i++) ep->name[i] = cp[i];
- bwrite (dp->dev, bp, bmap(dp, off/512)); // write directory
+ bwrite (dp->dev, bp, bmap(dp, off/BSIZE)); // write directory
brelse(bp);
iupdate (ip);
return ip;
diff --git a/fs.h b/fs.h
index 48a1c13..cce59fb 100644
--- a/fs.h
+++ b/fs.h
@@ -1,15 +1,16 @@
// on-disk file system format
-// second sector
+#define BSIZE 512 // block size
+
+// sector 1 (2nd sector)
struct superblock{
- int nblocks;
- int ninodes;
+ uint size;
+ uint nblocks;
+ uint ninodes;
};
#define NDIRECT 13
-// inodes start at the third sector
-// and blocks start at (ninodes * sizeof(dinode) + 511) / 512
struct dinode {
short type;
short major;
@@ -23,7 +24,11 @@ struct dinode {
#define T_FILE 2
#define T_DEV 3
-#define IPB (512 / sizeof(struct dinode))
+// sector 0 is unused, sector 1 is superblock, inodes start at sector 2
+#define IPB (BSIZE / sizeof(struct dinode))
+#define IBLOCK(inum) (inum / IPB + 2) // start of inode
+#define BPB (BSIZE*8)
+#define BBLOCK(b,ninodes) (b/BPB + (ninodes/IPB) + 3) // start of bitmap
#define DIRSIZ 14
diff --git a/mkfs.c b/mkfs.c
index 1022adf..fbf78b0 100644
--- a/mkfs.c
+++ b/mkfs.c
@@ -8,15 +8,19 @@
#include "param.h"
#include "fs.h"
-int nblocks = 1009;
+int nblocks = 1008;
int ninodes = 100;
+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 rsect(uint sec, void *buf);
@@ -67,12 +71,20 @@ main(int argc, char *argv[])
exit(1);
}
- sb.nblocks = xint(nblocks); // so whole disk is 1024 sectors
+ sb.size = xint(size);
+ sb.nblocks = xint(nblocks); // so whole disk is size sectors
sb.ninodes = xint(ninodes);
- freeblock = ninodes / IPB + 2;
+ bitblocks = sb.size/(512*8) + 1;
+ usedblocks = ninodes / IPB + 3 + bitblocks;
+ freeblock = usedblocks;
- for(i = 0; i < nblocks + (ninodes / IPB) + 3; i++)
+ printf ("used %d (bit %d ninode %d) free %d total %d\n", usedblocks,
+ bitblocks, ninodes/IPB + 1, freeblock, nblocks+usedblocks);
+
+ assert (nblocks + usedblocks == size);
+
+ for(i = 0; i < nblocks + usedblocks; i++)
wsect(i, zeroes);
wsect(1, &sb);
@@ -110,6 +122,8 @@ main(int argc, char *argv[])
close(fd);
}
+ balloc(usedblocks);
+
exit(0);
}
@@ -186,6 +200,22 @@ ialloc(ushort type)
return inum;
}
+void
+balloc(int used)
+{
+ uchar buf[512];
+ int i;
+
+ printf("balloc: first %d blocks have been allocated\n", used);
+ assert (used < 512);
+ 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 %d\n", ninodes/IPB + 3);
+ wsect(ninodes / IPB + 3, buf);
+}
+
#define min(a, b) ((a) < (b) ? (a) : (b))
void
@@ -202,8 +232,10 @@ iappend(uint inum, void *xp, int n)
while(n > 0){
fbn = off / 512;
assert(fbn < NDIRECT);
- if(din.addrs[fbn] == 0)
+ if(din.addrs[fbn] == 0) {
din.addrs[fbn] = xint(freeblock++);
+ usedblocks++;
+ }
n1 = min(n, (fbn + 1) * 512 - off);
rsect(xint(din.addrs[fbn]), buf);
bcopy(p, buf + off - (fbn * 512), n1);