kern

annotate src/fs.c @ 96:07fe6a614185

find changesets by author, revision, files, or words in the commit message
filesystem
author John Tsiombikas <nuclear@member.fsf.org>
date Thu, 15 Dec 2011 04:39:00 +0200
parents ec62cbe00b55
children 8717eb590727
rev   line source
nuclear@96 1 /* This code is used by the kernel AND by userspace filesystem-related tools. */
nuclear@88 2 #include <stdio.h>
nuclear@89 3 #include <stdlib.h>
nuclear@94 4 #include <string.h>
nuclear@90 5 #include <errno.h>
nuclear@94 6 #include <assert.h>
nuclear@88 7 #include "fs.h"
nuclear@93 8 #include "bdev.h"
nuclear@96 9 #include "kdef.h"
nuclear@96 10
nuclear@96 11 /* number of inodes in a block */
nuclear@96 12 #define BLK_INODES (BLKSZ / sizeof(struct inode))
nuclear@96 13 /* number of directory entries in a block */
nuclear@96 14 #define BLK_DIRENT (BLKSZ / sizeof(struct dir_entry))
nuclear@96 15
nuclear@96 16 #define BLKBITS (BLKSZ * 8)
nuclear@90 17
nuclear@95 18 #define BM_IDX(x) ((x) / 32)
nuclear@95 19 #define BM_BIT(x) ((x) & 0x1f)
nuclear@95 20
nuclear@95 21 #define BM_ISFREE(bm, x) (((bm)[BM_IDX(x)] & (1 << BM_BIT(x))) == 0)
nuclear@95 22 #define BM_SET(bm, x) ((bm)[BM_IDX(x)] |= (1 << BM_BIT(x)))
nuclear@95 23 #define BM_CLR(bm, x) ((bm)[BM_IDX(x)] &= ~(1 << BM_BIT(x)))
nuclear@95 24
nuclear@89 25
nuclear@96 26 static struct inode *newdir(struct filesys *fs, struct inode *parent);
nuclear@96 27 static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name);
nuclear@94 28 static int read_superblock(struct filesys *fs);
nuclear@94 29 static int write_superblock(struct filesys *fs);
nuclear@94 30 static int get_inode(struct filesys *fs, int ino, struct inode *inode);
nuclear@94 31 static int put_inode(struct filesys *fs, struct inode *inode);
nuclear@96 32 static int find_free(uint32_t *bm, int sz);
nuclear@96 33 static int alloc_inode(struct filesys *fs);
nuclear@96 34 static void free_inode(struct filesys *fs, int ino);
nuclear@96 35 static int alloc_block(struct filesys *fs);
nuclear@96 36 static void free_block(struct filesys *fs, int ino);
nuclear@96 37 static int file_block(struct filesys *fs, struct inode *node, int boffs);
nuclear@90 38
nuclear@93 39 int openfs(struct filesys *fs, dev_t dev)
nuclear@93 40 {
nuclear@93 41 int res;
nuclear@93 42 struct block_device *bdev;
nuclear@94 43
nuclear@94 44 assert(BLKSZ % sizeof(struct inode) == 0);
nuclear@89 45
nuclear@93 46 if(!(bdev = blk_open(dev))) {
nuclear@93 47 return -ENOENT;
nuclear@90 48 }
nuclear@94 49 fs->bdev = bdev;
nuclear@90 50
nuclear@93 51 /* read the superblock */
nuclear@94 52 if(!(fs->sb = malloc(BLKSZ))) {
nuclear@96 53 blk_close(bdev);
nuclear@96 54 return -ENOMEM;
nuclear@93 55 }
nuclear@94 56 if((res = read_superblock(fs)) != 0) {
nuclear@96 57 blk_close(bdev);
nuclear@96 58 return res;
nuclear@93 59 }
nuclear@90 60
nuclear@96 61 return 0;
nuclear@96 62 }
nuclear@93 63
nuclear@96 64 int mkfs(struct filesys *fs, dev_t dev)
nuclear@96 65 {
nuclear@96 66 struct filesys *fs;
nuclear@96 67 struct superblock *sb;
nuclear@96 68 struct block_device *bdev;
nuclear@96 69 int i, bcount;
nuclear@96 70
nuclear@96 71 if(!(bdev = blk_open(dev))) {
nuclear@96 72 return -1;
nuclear@96 73 }
nuclear@96 74 fs->bdev = bdev;
nuclear@96 75
nuclear@96 76 if(!(sb = malloc(BLKSZ))) {
nuclear@96 77 blk_close(bdev);
nuclear@96 78 return -1;
nuclear@96 79 }
nuclear@96 80 fs->sb = sb;
nuclear@96 81
nuclear@96 82 /* populate the superblock */
nuclear@96 83 sb->magic = MAGIC;
nuclear@96 84 sb->ver = FS_VER;
nuclear@96 85 sb->blksize = BLKSZ;
nuclear@96 86
nuclear@96 87 sb->num_blocks = bdev->size;
nuclear@96 88 sb->num_inodes = sb->num_blocks / 4;
nuclear@96 89
nuclear@96 90 /* inode bitmap just after the superblock */
nuclear@96 91 sb->ibm_start = 2;
nuclear@96 92 sb->ibm_count = (sb->num_inodes + BLKBITS - 1) / BLKBITS;
nuclear@96 93 /* also allocate and initialize in-memory inode bitmap */
nuclear@96 94 sb->ibm = malloc(sb->ibm_count * BLKSZ);
nuclear@96 95 assert(sb->ibm);
nuclear@96 96 memset(sb->ibm, 0, sb->ibm_count * BLKSZ);
nuclear@96 97
nuclear@96 98 /* XXX mark inode 0 as used always */
nuclear@96 99 BM_SET(sb->ibm, 0);
nuclear@96 100
nuclear@96 101 /* block bitmap just after the inode bitmap */
nuclear@96 102 sb->bm_start = sb->ibm_start + sb->ibm_count;
nuclear@96 103 sb->bm_count = (sb->num_blocks + BLKBITS - 1) / BLKBITS;
nuclear@96 104 /* also allocate and initialize in-memory block bitmap */
nuclear@96 105 sb->bm = malloc(sb->bm_count * BLKSZ);
nuclear@96 106 assert(sb->bm);
nuclear@96 107 memset(sb->bm, 0, sb->bm_count * BLKSZ);
nuclear@96 108
nuclear@96 109 /* inode table, just after the block bitmap */
nuclear@96 110 sb->itbl_start = sb->bm_start + sb->bm_count;
nuclear@96 111 sb->itbl_count = (sb->num_inodes * sizeof(struct inode) + BLKSZ - 1) / BLKSZ;
nuclear@96 112
nuclear@96 113 /* mark all used blocks as used */
nuclear@96 114 bcount = sb->itbl_start + sb->itbl_count;
nuclear@96 115 memset(sb->bm, 0xff, bcount / 8);
nuclear@96 116 for(i=0; i<bcount % 8; i++) {
nuclear@96 117 int bit = bcount / 8 + i;
nuclear@96 118 BM_SET(sb->bm, bit);
nuclear@96 119 }
nuclear@96 120
nuclear@96 121 /* create the root directory */
nuclear@96 122 sb->root = newdir(fs, 0);
nuclear@96 123 sb->root_ino = sb->root->ino;
nuclear@90 124 }
nuclear@88 125
nuclear@96 126 static struct inode *newdir(struct filesys *fs, struct inode *parent)
nuclear@96 127 {
nuclear@96 128 struct inode *dirnode;
nuclear@96 129
nuclear@96 130 /* allocate and initialize inode */
nuclear@96 131 if(!(dirnode = malloc(sizeof *dirnode))) {
nuclear@96 132 return 0;
nuclear@96 133 }
nuclear@96 134 memset(dirnode, 0, sizeof *dirnode);
nuclear@96 135
nuclear@96 136 if((dirnode->ino = alloc_inode(fs)) == -1) {
nuclear@96 137 printf("failed to allocate inode for a new directory\n");
nuclear@96 138 free(dirnode);
nuclear@96 139 return 0;
nuclear@96 140 }
nuclear@96 141 dirnode->mode = S_IFDIR;
nuclear@96 142
nuclear@96 143 /* add . and .. links */
nuclear@96 144 addlink(fs, dirnode, dirnode, ".");
nuclear@96 145 addlink(fs, dirnode, parent ? parent : dirnode, "..");
nuclear@96 146
nuclear@96 147 /* and write the inode to disk */
nuclear@96 148 put_inode(fs, dirnode);
nuclear@96 149 return dirnode;
nuclear@96 150 }
nuclear@96 151
nuclear@96 152 static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name)
nuclear@96 153 {
nuclear@96 154 struct dir_entry ent, *data;
nuclear@96 155 int boffs, bidx, len;
nuclear@96 156
nuclear@96 157 if(!(target->mode & S_IFDIR)) {
nuclear@96 158 return -ENOTDIR;
nuclear@96 159 }
nuclear@96 160 if(node->mode & S_IFDIR) {
nuclear@96 161 return -EPERM;
nuclear@96 162 }
nuclear@96 163 /* TODO check that the link does not already exist (EEXIST) */
nuclear@96 164
nuclear@96 165 if((len = strlen(name)) > MAX_FNAME) {
nuclear@96 166 return -ENAMETOOLONG;
nuclear@96 167 }
nuclear@96 168 ent->ino = node->ino;
nuclear@96 169 memcpy(newent->name, name, len + 1);
nuclear@96 170
nuclear@96 171 /* find a place to put it */
nuclear@96 172 if(!(data = malloc(BLKSZ))) {
nuclear@96 173 return -ENOMEM;
nuclear@96 174 }
nuclear@96 175
nuclear@96 176 boffs = 0;
nuclear@96 177 while((bidx = file_block(fs, target, boffs)) > 0) {
nuclear@96 178 /* read the block, and search for an empty entry */
nuclear@96 179 blk_read(fs->bdev, bidx, 1, data);
nuclear@96 180
nuclear@96 181 /* for all directory entries in this block... */
nuclear@96 182 for(i=0; i<BLK_DIRENT; i++) {
nuclear@96 183 if(data[i].ino == 0) {
nuclear@96 184 /* found empty */
nuclear@96 185 memcpy(data + i, &ent, sizeof ent);
nuclear@96 186 goto success;
nuclear@96 187 }
nuclear@96 188 }
nuclear@96 189 boffs++;
nuclear@96 190 }
nuclear@96 191
nuclear@96 192 /* didn't find any free entries amongst our blocks, allocate a new one */
nuclear@96 193 if(!(bidx = alloc_file_block(fs, target, boffs))) {
nuclear@96 194 free(data);
nuclear@96 195 return -ENOSPC;
nuclear@96 196 }
nuclear@96 197 /* zero-fill the new block and add the first entry */
nuclear@96 198 memset(data, 0, BLKSZ);
nuclear@96 199 *data = ent;
nuclear@96 200
nuclear@96 201 success:
nuclear@96 202 /* write to disk */
nuclear@96 203 blk_write(fs->bdev, bidx, 1, data);
nuclear@96 204 node->nlink++; /* increase reference count */
nuclear@96 205
nuclear@96 206 free(data);
nuclear@96 207 return 0;
nuclear@96 208 }
nuclear@96 209
nuclear@96 210
nuclear@94 211 static int read_superblock(struct filesys *fs)
nuclear@88 212 {
nuclear@94 213 struct superblock *sb = fs->sb;
nuclear@94 214
nuclear@93 215 /* read superblock and verify */
nuclear@94 216 if(blk_read(fs->bdev, 1, 1, sb) == -1) {
nuclear@93 217 printf("failed to read superblock\n");
nuclear@93 218 return -EIO;
nuclear@93 219 }
nuclear@93 220 if(sb->magic != MAGIC) {
nuclear@93 221 printf("invalid magic\n");
nuclear@93 222 return -EINVAL;
nuclear@93 223 }
nuclear@93 224 if(sb->ver > FS_VER) {
nuclear@93 225 printf("invalid version: %d\n", sb->ver);
nuclear@93 226 return -EINVAL;
nuclear@93 227 }
nuclear@93 228 if(sb->blksize != BLKSZ) {
nuclear@93 229 printf("invalid block size: %d\n", sb->blksize);
nuclear@93 230 return -EINVAL;
nuclear@93 231 }
nuclear@89 232
nuclear@93 233 /* allocate and populate in-memory bitmaps */
nuclear@93 234 if(!(sb->ibm = malloc(sb->ibm_count * sb->blksize))) {
nuclear@93 235 return -ENOMEM;
nuclear@88 236 }
nuclear@94 237 if(blk_read(fs->bdev, sb->ibm_start, sb->ibm_count, sb->ibm) == -1) {
nuclear@93 238 printf("failed to read inode bitmap\n");
nuclear@93 239 free(sb->ibm);
nuclear@93 240 return -EIO;
nuclear@93 241 }
nuclear@93 242 if(!(sb->bm = malloc(sb->bm_count * sb->blksize))) {
nuclear@93 243 free(sb->ibm);
nuclear@93 244 return -ENOMEM;
nuclear@93 245 }
nuclear@94 246 if(blk_read(fs->bdev, sb->bm_start, sb->bm_count, sb->bm) == -1) {
nuclear@93 247 printf("failed to read block bitmap\n");
nuclear@93 248 free(sb->ibm);
nuclear@93 249 free(sb->bm);
nuclear@93 250 return -EIO;
nuclear@93 251 }
nuclear@93 252
nuclear@94 253 /* read the root inode */
nuclear@94 254 if(!(sb->root = malloc(sizeof *sb->root))) {
nuclear@94 255 free(sb->ibm);
nuclear@94 256 free(sb->bm);
nuclear@94 257 return -ENOMEM;
nuclear@94 258 }
nuclear@94 259 if(get_inode(fs, sb->root_ino, sb->root) == -1) {
nuclear@94 260 printf("failed to read root inode\n");
nuclear@94 261 return -1;
nuclear@94 262 }
nuclear@94 263
nuclear@93 264 return 0;
nuclear@88 265 }
nuclear@94 266
nuclear@94 267 static int write_superblock(struct filesys *fs)
nuclear@94 268 {
nuclear@94 269 struct superblock *sb = fs->sb;
nuclear@94 270
nuclear@94 271 /* write back any changes in the root inode */
nuclear@94 272 if(put_inode(fs, sb->root) == -1) {
nuclear@94 273 return -1;
nuclear@94 274 }
nuclear@94 275 /* write back the block bitmap */
nuclear@94 276 if(blk_write(fs->bdev, sb->bm_start, sb->bm_count, sb->bm) == -1) {
nuclear@94 277 return -1;
nuclear@94 278 }
nuclear@94 279 /* write back the inode bitmap */
nuclear@94 280 if(blk_write(fs->bdev, sb->ibm_start, sb->ibm_count, sb->ibm) == -1) {
nuclear@94 281 return -1;
nuclear@94 282 }
nuclear@96 283 /* write the superblock itself */
nuclear@96 284 if(blk_write(fs->bdev, 1, 1, sb) == -1) {
nuclear@96 285 return -1;
nuclear@96 286 }
nuclear@94 287 return 0;
nuclear@94 288 }
nuclear@94 289
nuclear@94 290 /* copy the requested inode from the disk, into the buffer passed in the last arg */
nuclear@94 291 static int get_inode(struct filesys *fs, int ino, struct inode *inode)
nuclear@94 292 {
nuclear@94 293 struct inode *buf = malloc(BLKSZ);
nuclear@94 294 assert(buf);
nuclear@94 295
nuclear@94 296 if(blk_read(fs->bdev, fs->sb->itbl_start + ino / BLK_INODES, 1, buf) == -1) {
nuclear@94 297 free(buf);
nuclear@94 298 return -1;
nuclear@94 299 }
nuclear@94 300 memcpy(inode, buf + ino % BLK_INODES, sizeof *inode);
nuclear@94 301 free(buf);
nuclear@94 302 return 0;
nuclear@94 303 }
nuclear@94 304
nuclear@94 305 /* write the inode to the disk */
nuclear@94 306 static int put_inode(struct filesys *fs, struct inode *inode)
nuclear@94 307 {
nuclear@94 308 struct inode *buf = malloc(BLKSZ);
nuclear@94 309 assert(buf);
nuclear@94 310
nuclear@94 311 if(blk_read(fs->bdev, fs->sb->itbl_start + inode->ino / BLK_INODES, 1, buf) == -1) {
nuclear@94 312 free(buf);
nuclear@94 313 return -1;
nuclear@94 314 }
nuclear@94 315 memcpy(buf + inode->ino % BLK_INODES, inode, sizeof *inode);
nuclear@94 316
nuclear@94 317 if(blk_write(fs->bdev, fs->sb->itbl_start + inode->ino / BLK_INODES, 1, buf) == -1) {
nuclear@94 318 free(buf);
nuclear@94 319 return -1;
nuclear@94 320 }
nuclear@94 321 free(buf);
nuclear@94 322 return 0;
nuclear@94 323 }
nuclear@95 324
nuclear@96 325 /* find a free element in the bitmap and return its number */
nuclear@96 326 static int find_free(uint32_t *bm, int nbits)
nuclear@95 327 {
nuclear@96 328 int i, j, nwords = nbits / 32;
nuclear@96 329 uint32_t ent = 0;
nuclear@95 330
nuclear@96 331 for(i=0; i<=nwords; i++) {
nuclear@95 332 if(bm[i] != 0xffffffff) {
nuclear@95 333 for(j=0; j<32; j++) {
nuclear@95 334 if(BM_ISFREE(bm, ent)) {
nuclear@95 335 return ent;
nuclear@95 336 }
nuclear@96 337 ent++;
nuclear@95 338 }
nuclear@95 339
nuclear@95 340 panic("shouldn't happen (in find_free:fs.c)");
nuclear@96 341 } else {
nuclear@96 342 ent += 32;
nuclear@95 343 }
nuclear@95 344 }
nuclear@95 345
nuclear@95 346 return -1;
nuclear@95 347 }
nuclear@95 348
nuclear@95 349 static int alloc_inode(struct filesys *fs)
nuclear@95 350 {
nuclear@95 351 int ino;
nuclear@95 352
nuclear@96 353 if((ino = find_free(fs->sb->ibm, fs->sb->num_inodes)) == -1) {
nuclear@95 354 return -1;
nuclear@95 355 }
nuclear@96 356 BM_SET(fs->sb->ibm, ino);
nuclear@95 357 return 0;
nuclear@95 358 }
nuclear@96 359
nuclear@96 360 static void free_inode(struct filesys *fs, int ino)
nuclear@96 361 {
nuclear@96 362 BM_CLR(fs->sb->ibm, ino);
nuclear@96 363 }
nuclear@96 364
nuclear@96 365 static int alloc_block(struct filesys *fs)
nuclear@96 366 {
nuclear@96 367 int ino;
nuclear@96 368
nuclear@96 369 if((ino = find_free(fs->sb->bm, fs->sb->num_blocks)) == -1) {
nuclear@96 370 return -1;
nuclear@96 371 }
nuclear@96 372 BM_SET(fs->sb->bm, ino);
nuclear@96 373 return 0;
nuclear@96 374 }
nuclear@96 375
nuclear@96 376 static void free_block(struct filesys *fs, int ino)
nuclear@96 377 {
nuclear@96 378 BM_CLR(fs->sb->bm, ino);
nuclear@96 379 }
nuclear@96 380
nuclear@96 381 #define BLK_BLKID (BLKSZ / sizeof(blkid))
nuclear@96 382 #define MAX_IND (NDIRBLK + BLK_BLKID)
nuclear@96 383 #define MAX_DIND (MAX_IND + BLK_BLKID * BLK_BLKID)
nuclear@96 384
nuclear@96 385 static int file_block(struct filesys *fs, struct inode *node, int boffs)
nuclear@96 386 {
nuclear@96 387 int res, idx;
nuclear@96 388 blkid *barr;
nuclear@96 389
nuclear@96 390 /* is it a direct block ? */
nuclear@96 391 if(boffs < NDIRBLK) {
nuclear@96 392 return node->blk[boffs];
nuclear@96 393 }
nuclear@96 394
nuclear@96 395 barr = malloc(BLKSZ);
nuclear@96 396 assert(barr);
nuclear@96 397
nuclear@96 398 /* is it an indirect block ? */
nuclear@96 399 if(boffs < MAX_IND) {
nuclear@96 400 if(!node->ind) {
nuclear@96 401 res = 0;
nuclear@96 402 goto end;
nuclear@96 403 }
nuclear@96 404 blk_read(fs->bdev, node->ind, 1, barr);
nuclear@96 405 res = barr[boffs - NDIRBLK];
nuclear@96 406 goto end;
nuclear@96 407 }
nuclear@96 408
nuclear@96 409 /* is it a double-indirect block ? */
nuclear@96 410 if(boffs < MAX_DIND) {
nuclear@96 411 /* first read the dind block and find the index of the ind block */
nuclear@96 412 if(!node->dind) {
nuclear@96 413 res = 0;
nuclear@96 414 goto end;
nuclear@96 415 }
nuclear@96 416 blk_read(fd->bdev, node->dind, 1, barr);
nuclear@96 417 idx = (boffs - MAX_IND) / BLK_BLKID;
nuclear@96 418
nuclear@96 419 /* then read the ind block and find the index of the block */
nuclear@96 420 if(!barr[idx]) {
nuclear@96 421 res = 0;
nuclear@96 422 goto end;
nuclear@96 423 }
nuclear@96 424 blk_read(fd->bdev, barr[idx], 1, barr);
nuclear@96 425 res = barr[(boffs - MAX_IND) % BLK_BLKID];
nuclear@96 426 }
nuclear@96 427
nuclear@96 428 end:
nuclear@96 429 free(barr);
nuclear@96 430 return res;
nuclear@96 431 }