kern: 8717eb590727 src/fs.c

kern

view src/fs.c @ 97:8717eb590727

ok stopping with the filesystem to manage to write the article in time

author	John Tsiombikas <nuclear@member.fsf.org>
date	Sat, 17 Dec 2011 14:09:17 +0200
parents	07fe6a614185
children

line source

1 /* This code is used by the kernel AND by userspace filesystem-related tools. */

3 /* XXX convention:

4 * - functions that accept or return a struct inode, do not read/write it to disk

5 * - functions that accept or return an int ino, do read/write it to disk

6 * other kinds of blocks (data, indirect, etc) always hit the disk directly.

7 */

9 #include <stdio.h>

10 #include <stdlib.h>

11 #include <string.h>

12 #include <errno.h>

13 #include <assert.h>

14 #include "fs.h"

15 #include "bdev.h"

16 #include "kdef.h"

18 /* number of inodes in a block */

19 #define BLK_INODES (BLKSZ / sizeof(struct inode))

20 /* number of directory entries in a block */

21 #define BLK_DIRENT (BLKSZ / sizeof(struct dir_entry))

23 #define BLKBITS (BLKSZ * 8)

25 #define BM_IDX(x) ((x) / 32)

26 #define BM_BIT(x) ((x) & 0x1f)

28 #define BM_ISFREE(bm, x) (((bm)[BM_IDX(x)] & (1 << BM_BIT(x))) == 0)

29 #define BM_SET(bm, x) ((bm)[BM_IDX(x)] |= (1 << BM_BIT(x)))

30 #define BM_CLR(bm, x) ((bm)[BM_IDX(x)] &= ~(1 << BM_BIT(x)))

33 static struct inode *newdir(struct filesys *fs, struct inode *parent);

34 static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name);

35 static int read_superblock(struct filesys *fs);

36 static int write_superblock(struct filesys *fs);

37 static int get_inode(struct filesys *fs, int ino, struct inode *inode);

38 static int put_inode(struct filesys *fs, struct inode *inode);

39 static int find_free(uint32_t *bm, int sz);

40 static int alloc_inode(struct filesys *fs);

41 #define free_inode(fs, ino) BM_CLR((fs)->sb->ibm, (ino))

42 static int alloc_block(struct filesys *fs);

43 #define free_block(fs, bno) BM_CLR((fs)->sb->bm, (bno))

44 #define zero_block(fs, bno) \

45 do { \

46 assert(bno > 0); \

47 blk_write((fs)->bdev, (bno), 1, (fs)->zeroblock); \

48 } while(0)

50 static int file_block(struct filesys *fs, struct inode *node, int boffs, int allocate);

51 #define get_file_block(fs, node, boffs) file_block(fs, node, boffs, 0)

52 #define alloc_file_block(fs, node, boffs) file_block(fs, node, boffs, 1)

55 int openfs(struct filesys *fs, dev_t dev)

56 {

57 int res;

58 struct block_device *bdev;

60 assert(BLKSZ % sizeof(struct inode) == 0);

62 if(!(bdev = blk_open(dev))) {

63 return -ENOENT;

64 }

65 fs->bdev = bdev;

67 /* read the superblock */

68 if(!(fs->sb = malloc(BLKSZ))) {

69 blk_close(bdev);

70 return -ENOMEM;

71 }

72 if((res = read_superblock(fs)) != 0) {

73 blk_close(bdev);

74 return res;

75 }

77 /* allocate the zero-block buffer written to zero-out blocks */

78 if(!(fs->zeroblock = malloc(fs->sb->blksize))) {

79 blk_close(bdev);

80 free(fs->sb->ibm);

81 free(fs->sb->bm);

82 free(fs->sb->root);

83 return -ENOMEM;

84 }

85 memset(fs->zeroblock, 0xff, fs->sb->blksize);

87 return 0;

88 }

90 int mkfs(struct filesys *fs, dev_t dev)

91 {

92 struct superblock *sb;

93 struct block_device *bdev;

94 int i, bcount;

96 if(!(bdev = blk_open(dev))) {

97 return -1;

98 }

99 fs->bdev = bdev;

100

101 if(!(sb = malloc(BLKSZ))) {

102 blk_close(bdev);

103 return -1;

104 }

105 fs->sb = sb;

106

107 /* populate the superblock */

108 sb->magic = MAGIC;

109 sb->ver = FS_VER;

110 sb->blksize = BLKSZ;

111

112 sb->num_blocks = bdev->size;

113 sb->num_inodes = sb->num_blocks / 4;

114

115 /* inode bitmap just after the superblock */

116 sb->ibm_start = 2;

117 sb->ibm_count = (sb->num_inodes + BLKBITS - 1) / BLKBITS;

118 /* also allocate and initialize in-memory inode bitmap */

119 sb->ibm = malloc(sb->ibm_count * BLKSZ);

120 assert(sb->ibm);

121 memset(sb->ibm, 0, sb->ibm_count * BLKSZ);

122

123 /* XXX mark inode 0 as used always */

124 BM_SET(sb->ibm, 0);

125

126 /* block bitmap just after the inode bitmap */

127 sb->bm_start = sb->ibm_start + sb->ibm_count;

128 sb->bm_count = (sb->num_blocks + BLKBITS - 1) / BLKBITS;

129 /* also allocate and initialize in-memory block bitmap */

130 sb->bm = malloc(sb->bm_count * BLKSZ);

131 assert(sb->bm);

132 memset(sb->bm, 0, sb->bm_count * BLKSZ);

133

134 /* inode table, just after the block bitmap */

135 sb->itbl_start = sb->bm_start + sb->bm_count;

136 sb->itbl_count = (sb->num_inodes * sizeof(struct inode) + BLKSZ - 1) / BLKSZ;

137

138 /* mark all used blocks as used */

139 bcount = sb->itbl_start + sb->itbl_count;

140 memset(sb->bm, 0xff, bcount / 8);

141 for(i=0; i<bcount % 8; i++) {

142 int bit = bcount / 8 + i;

143 BM_SET(sb->bm, bit);

144 }

145

146 /* create the root directory */

147 sb->root = newdir(fs, 0);

148 sb->root_ino = sb->root->ino;

149 /* and write the inode to disk */

150 put_inode(fs, sb->root);

151

152 return 0;

153 }

154

155 static struct inode *newdir(struct filesys *fs, struct inode *parent)

156 {

157 struct inode *dirnode;

158

159 /* allocate and initialize inode */

160 if(!(dirnode = malloc(sizeof *dirnode))) {

161 return 0;

162 }

163 memset(dirnode, 0, sizeof *dirnode);

164

165 if((dirnode->ino = alloc_inode(fs)) == -1) {

166 printf("failed to allocate inode for a new directory\n");

167 free(dirnode);

168 return 0;

169 }

170 dirnode->mode = S_IFDIR;

171

172 /* add . and .. links */

173 addlink(fs, dirnode, dirnode, ".");

174 addlink(fs, dirnode, parent ? parent : dirnode, "..");

175

176 return dirnode;

177 }

178

179 static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name)

180 {

181 struct dir_entry ent, *data;

182 int i, boffs, bidx, len;

183

184 if(!(target->mode & S_IFDIR)) {

185 return -ENOTDIR;

186 }

187 if(node->mode & S_IFDIR) {

188 return -EPERM;

189 }

190 /* TODO check that the link does not already exist (EEXIST) */

191

192 if((len = strlen(name)) > NAME_MAX) {

193 return -ENAMETOOLONG;

194 }

195 ent.ino = node->ino;

196 memcpy(ent.name, name, len + 1);

197

198 /* find a place to put it */

199 if(!(data = malloc(BLKSZ))) {

200 return -ENOMEM;

201 }

202

203 boffs = 0;

204 while((bidx = get_file_block(fs, target, boffs)) > 0) {

205 /* read the block, and search for an empty entry */

206 blk_read(fs->bdev, bidx, 1, data);

207

208 /* for all directory entries in this block... */

209 for(i=0; i<BLK_DIRENT; i++) {

210 if(data[i].ino == 0) {

211 /* found empty */

212 memcpy(data + i, &ent, sizeof ent);

213 goto success;

214 }

215 }

216 boffs++;

217 }

218

219 /* didn't find any free entries amongst our blocks, allocate a new one */

220 if(!(bidx = alloc_file_block(fs, target, boffs))) {

221 free(data);

222 return -ENOSPC;

223 }

224 /* zero-fill the new block and add the first entry */

225 memset(data, 0, BLKSZ);

226 *data = ent;

227

228 success:

229 /* write to disk */

230 blk_write(fs->bdev, bidx, 1, data);

231 node->nlink++; /* increase reference count */

232

233 free(data);

234 return 0;

235 }

236

237

238 static int read_superblock(struct filesys *fs)

239 {

240 struct superblock *sb = fs->sb;

241

242 /* read superblock and verify */

243 if(blk_read(fs->bdev, 1, 1, sb) == -1) {

244 printf("failed to read superblock\n");

245 return -EIO;

246 }

247 if(sb->magic != MAGIC) {

248 printf("invalid magic\n");

249 return -EINVAL;

250 }

251 if(sb->ver > FS_VER) {

252 printf("invalid version: %d\n", sb->ver);

253 return -EINVAL;

254 }

255 if(sb->blksize != BLKSZ) {

256 printf("invalid block size: %d\n", sb->blksize);

257 return -EINVAL;

258 }

259

260 /* allocate and populate in-memory bitmaps */

261 if(!(sb->ibm = malloc(sb->ibm_count * sb->blksize))) {

262 return -ENOMEM;

263 }

264 if(blk_read(fs->bdev, sb->ibm_start, sb->ibm_count, sb->ibm) == -1) {

265 printf("failed to read inode bitmap\n");

266 free(sb->ibm);

267 return -EIO;

268 }

269 if(!(sb->bm = malloc(sb->bm_count * sb->blksize))) {

270 free(sb->ibm);

271 return -ENOMEM;

272 }

273 if(blk_read(fs->bdev, sb->bm_start, sb->bm_count, sb->bm) == -1) {

274 printf("failed to read block bitmap\n");

275 free(sb->ibm);

276 free(sb->bm);

277 return -EIO;

278 }

279

280 /* read the root inode */

281 if(!(sb->root = malloc(sizeof *sb->root))) {

282 free(sb->ibm);

283 free(sb->bm);

284 return -ENOMEM;

285 }

286 if(get_inode(fs, sb->root_ino, sb->root) == -1) {

287 printf("failed to read root inode\n");

288 return -1;

289 }

290

291 return 0;

292 }

293

294 static int write_superblock(struct filesys *fs)

295 {

296 struct superblock *sb = fs->sb;

297

298 /* write back any changes in the root inode */

299 if(put_inode(fs, sb->root) == -1) {

300 return -1;

301 }

302 /* write back the block bitmap */

303 if(blk_write(fs->bdev, sb->bm_start, sb->bm_count, sb->bm) == -1) {

304 return -1;

305 }

306 /* write back the inode bitmap */

307 if(blk_write(fs->bdev, sb->ibm_start, sb->ibm_count, sb->ibm) == -1) {

308 return -1;

309 }

310 /* write the superblock itself */

311 if(blk_write(fs->bdev, 1, 1, sb) == -1) {

312 return -1;

313 }

314 return 0;

315 }

316

317 /* copy the requested inode from the disk, into the buffer passed in the last arg */

318 static int get_inode(struct filesys *fs, int ino, struct inode *inode)

319 {

320 struct inode *buf = malloc(BLKSZ);

321 assert(buf);

322

323 if(blk_read(fs->bdev, fs->sb->itbl_start + ino / BLK_INODES, 1, buf) == -1) {

324 free(buf);

325 return -1;

326 }

327 memcpy(inode, buf + ino % BLK_INODES, sizeof *inode);

328 free(buf);

329 return 0;

330 }

331

332 /* write the inode to the disk */

333 static int put_inode(struct filesys *fs, struct inode *inode)

334 {

335 struct inode *buf = malloc(BLKSZ);

336 assert(buf);

337

338 if(blk_read(fs->bdev, fs->sb->itbl_start + inode->ino / BLK_INODES, 1, buf) == -1) {

339 free(buf);

340 return -1;

341 }

342 memcpy(buf + inode->ino % BLK_INODES, inode, sizeof *inode);

343

344 if(blk_write(fs->bdev, fs->sb->itbl_start + inode->ino / BLK_INODES, 1, buf) == -1) {

345 free(buf);

346 return -1;

347 }

348 free(buf);

349 return 0;

350 }

351

352 /* find a free element in the bitmap and return its number */

353 static int find_free(uint32_t *bm, int nbits)

354 {

355 int i, j, nwords = nbits / 32;

356 uint32_t ent = 0;

357

358 for(i=0; i<=nwords; i++) {

359 if(bm[i] != 0xffffffff) {

360 for(j=0; j<32; j++) {

361 if(BM_ISFREE(bm, ent)) {

362 return ent;

363 }

364 ent++;

365 }

366

367 panic("shouldn't happen (in find_free:fs.c)");

368 } else {

369 ent += 32;

370 }

371 }

372

373 return -1;

374 }

375

376 static int alloc_inode(struct filesys *fs)

377 {

378 int ino;

379

380 if((ino = find_free(fs->sb->ibm, fs->sb->num_inodes)) == -1) {

381 return -1;

382 }

383 BM_SET(fs->sb->ibm, ino);

384 return 0;

385 }

386

387 static int alloc_block(struct filesys *fs)

388 {

389 int bno;

390

391 if((bno = find_free(fs->sb->bm, fs->sb->num_blocks)) == -1) {

392 return -1;

393 }

394 BM_SET(fs->sb->bm, bno);

395 return 0;

396 }

397

398 #define BLK_BLKID (BLKSZ / sizeof(blkid))

399 #define MAX_IND (NDIRBLK + BLK_BLKID)

400 #define MAX_DIND (MAX_IND + BLK_BLKID * BLK_BLKID)

401

402 static int file_block(struct filesys *fs, struct inode *node, int boffs, int allocate)

403 {

404 int res, idx, node_dirty = 0;

405 blkid *barr;

406

407 /* out of bounds */

408 if(boffs < 0 || boffs >= MAX_DIND) {

409 return 0;

410 }

411

412 /* is it a direct block ? */

413 if(boffs < NDIRBLK) {

414 if(!(res = node->blk[boffs]) && allocate) {

415 res = node->blk[boffs] = alloc_block(fs);

416 if(res) {

417 zero_block(fs, res);

418 /* also write back the modified inode */

419 put_inode(fs, node);

420 }

421 }

422 return res;

423 }

424

425 barr = malloc(fs->sb->blksize);

426 assert(barr);

427

428 /* is it an indirect block ? */

429 if(boffs < MAX_IND) {

430 int ind_dirty = 0;

431

432 if(node->ind) {

433 /* read the indirect block */

434 blk_read(fs->bdev, node->ind, 1, barr);

435 } else {

436 /* does not exist... try to allocate if requested */

437 if(!allocate || !(node->ind = alloc_block(fs))) {

438 res = 0;

439 goto end;

440 }

441

442 /* allocated a block clear the buffer, and invalidate everything */

443 memset(barr, 0, sizeof fs->sb->blksize);

444 node_dirty = 1;

445 ind_dirty = 1;

446 }

447

448 idx = boffs - NDIRBLK;

449

450 if(!(res = barr[idx])) {

451 if(allocate && (res = barr[idx] = alloc_block(fs))) {

452 ind_dirty = 1;

453 }

454 }

455

456 /* write back the indirect block if needed */

457 if(ind_dirty) {

458 blk_write(fs->bdev, node->ind, 1, barr);

459 }

460 goto end;

461 }

462

463 /* TODO check/rewrite this */

464 #if 0

465 /* is it a double-indirect block ? */

466 if(boffs < MAX_DIND) {

467 /* first read the dind block and find the index of the ind block */

468 if(!node->dind) {

469 if(allocate) {

470 /* allocate and zero-out the double indirect block */

471 res = node->dind = alloc_block(fs);

472 if(res) {

473 zero_block(fs, res);

474 }

475 } else {

476 res = 0;

477 goto end;

478 }

479 }

480 blk_read(fd->bdev, node->dind, 1, barr);

481 idx = (boffs - MAX_IND) / BLK_BLKID;

482

483 /* then read the ind block and find the index of the block */

484 if(!barr[idx]) {

485 res = 0;

486 goto end;

487 }

488 blk_read(fd->bdev, barr[idx], 1, barr);

489 res = barr[(boffs - MAX_IND) % BLK_BLKID];

490 }

491 #endif

492

493 end:

494 if(node_dirty) {

495 put_inode(fs, node);

496 }

497 free(barr);

498 return res;

499 }