kern: 07fe6a614185 src/fs.c

kern

view src/fs.c @ 96:07fe6a614185

filesystem

author	John Tsiombikas <nuclear@member.fsf.org>
date	Thu, 15 Dec 2011 04:39:00 +0200
parents	ec62cbe00b55
children	8717eb590727

line source

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

2 #include <stdio.h>

3 #include <stdlib.h>

4 #include <string.h>

5 #include <errno.h>

6 #include <assert.h>

7 #include "fs.h"

8 #include "bdev.h"

9 #include "kdef.h"

11 /* number of inodes in a block */

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

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

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

16 #define BLKBITS (BLKSZ * 8)

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

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

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

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

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

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

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

28 static int read_superblock(struct filesys *fs);

29 static int write_superblock(struct filesys *fs);

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

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

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

33 static int alloc_inode(struct filesys *fs);

34 static void free_inode(struct filesys *fs, int ino);

35 static int alloc_block(struct filesys *fs);

36 static void free_block(struct filesys *fs, int ino);

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

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

40 {

41 int res;

42 struct block_device *bdev;

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

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

47 return -ENOENT;

48 }

49 fs->bdev = bdev;

51 /* read the superblock */

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

53 blk_close(bdev);

54 return -ENOMEM;

55 }

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

57 blk_close(bdev);

58 return res;

59 }

61 return 0;

62 }

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

65 {

66 struct filesys *fs;

67 struct superblock *sb;

68 struct block_device *bdev;

69 int i, bcount;

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

72 return -1;

73 }

74 fs->bdev = bdev;

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

77 blk_close(bdev);

78 return -1;

79 }

80 fs->sb = sb;

82 /* populate the superblock */

83 sb->magic = MAGIC;

84 sb->ver = FS_VER;

85 sb->blksize = BLKSZ;

87 sb->num_blocks = bdev->size;

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

90 /* inode bitmap just after the superblock */

91 sb->ibm_start = 2;

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

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

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

95 assert(sb->ibm);

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

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

99 BM_SET(sb->ibm, 0);

100

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

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

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

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

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

106 assert(sb->bm);

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

108

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

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

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

112

113 /* mark all used blocks as used */

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

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

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

117 int bit = bcount / 8 + i;

118 BM_SET(sb->bm, bit);

119 }

120

121 /* create the root directory */

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

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

124 }

125

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

127 {

128 struct inode *dirnode;

129

130 /* allocate and initialize inode */

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

132 return 0;

133 }

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

135

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

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

138 free(dirnode);

139 return 0;

140 }

141 dirnode->mode = S_IFDIR;

142

143 /* add . and .. links */

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

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

146

147 /* and write the inode to disk */

148 put_inode(fs, dirnode);

149 return dirnode;

150 }

151

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

153 {

154 struct dir_entry ent, *data;

155 int boffs, bidx, len;

156

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

158 return -ENOTDIR;

159 }

160 if(node->mode & S_IFDIR) {

161 return -EPERM;

162 }

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

164

165 if((len = strlen(name)) > MAX_FNAME) {

166 return -ENAMETOOLONG;

167 }

168 ent->ino = node->ino;

169 memcpy(newent->name, name, len + 1);

170

171 /* find a place to put it */

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

173 return -ENOMEM;

174 }

175

176 boffs = 0;

177 while((bidx = file_block(fs, target, boffs)) > 0) {

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

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

180

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

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

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

184 /* found empty */

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

186 goto success;

187 }

188 }

189 boffs++;

190 }

191

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

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

194 free(data);

195 return -ENOSPC;

196 }

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

198 memset(data, 0, BLKSZ);

199 *data = ent;

200

201 success:

202 /* write to disk */

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

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

205

206 free(data);

207 return 0;

208 }

209

210

211 static int read_superblock(struct filesys *fs)

212 {

213 struct superblock *sb = fs->sb;

214

215 /* read superblock and verify */

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

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

218 return -EIO;

219 }

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

221 printf("invalid magic\n");

222 return -EINVAL;

223 }

224 if(sb->ver > FS_VER) {

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

226 return -EINVAL;

227 }

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

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

230 return -EINVAL;

231 }

232

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

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

235 return -ENOMEM;

236 }

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

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

239 free(sb->ibm);

240 return -EIO;

241 }

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

243 free(sb->ibm);

244 return -ENOMEM;

245 }

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

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

248 free(sb->ibm);

249 free(sb->bm);

250 return -EIO;

251 }

252

253 /* read the root inode */

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

255 free(sb->ibm);

256 free(sb->bm);

257 return -ENOMEM;

258 }

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

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

261 return -1;

262 }

263

264 return 0;

265 }

266

267 static int write_superblock(struct filesys *fs)

268 {

269 struct superblock *sb = fs->sb;

270

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

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

273 return -1;

274 }

275 /* write back the block bitmap */

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

277 return -1;

278 }

279 /* write back the inode bitmap */

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

281 return -1;

282 }

283 /* write the superblock itself */

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

285 return -1;

286 }

287 return 0;

288 }

289

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

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

292 {

293 struct inode *buf = malloc(BLKSZ);

294 assert(buf);

295

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

297 free(buf);

298 return -1;

299 }

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

301 free(buf);

302 return 0;

303 }

304

305 /* write the inode to the disk */

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

307 {

308 struct inode *buf = malloc(BLKSZ);

309 assert(buf);

310

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

312 free(buf);

313 return -1;

314 }

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

316

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

318 free(buf);

319 return -1;

320 }

321 free(buf);

322 return 0;

323 }

324

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

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

327 {

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

329 uint32_t ent = 0;

330

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

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

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

334 if(BM_ISFREE(bm, ent)) {

335 return ent;

336 }

337 ent++;

338 }

339

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

341 } else {

342 ent += 32;

343 }

344 }

345

346 return -1;

347 }

348

349 static int alloc_inode(struct filesys *fs)

350 {

351 int ino;

352

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

354 return -1;

355 }

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

357 return 0;

358 }

359

360 static void free_inode(struct filesys *fs, int ino)

361 {

362 BM_CLR(fs->sb->ibm, ino);

363 }

364

365 static int alloc_block(struct filesys *fs)

366 {

367 int ino;

368

369 if((ino = find_free(fs->sb->bm, fs->sb->num_blocks)) == -1) {

370 return -1;

371 }

372 BM_SET(fs->sb->bm, ino);

373 return 0;

374 }

375

376 static void free_block(struct filesys *fs, int ino)

377 {

378 BM_CLR(fs->sb->bm, ino);

379 }

380

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

382 #define MAX_IND (NDIRBLK + BLK_BLKID)

383 #define MAX_DIND (MAX_IND + BLK_BLKID * BLK_BLKID)

384

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

386 {

387 int res, idx;

388 blkid *barr;

389

390 /* is it a direct block ? */

391 if(boffs < NDIRBLK) {

392 return node->blk[boffs];

393 }

394

395 barr = malloc(BLKSZ);

396 assert(barr);

397

398 /* is it an indirect block ? */

399 if(boffs < MAX_IND) {

400 if(!node->ind) {

401 res = 0;

402 goto end;

403 }

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

405 res = barr[boffs - NDIRBLK];

406 goto end;

407 }

408

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

410 if(boffs < MAX_DIND) {

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

412 if(!node->dind) {

413 res = 0;

414 goto end;

415 }

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

417 idx = (boffs - MAX_IND) / BLK_BLKID;

418

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

420 if(!barr[idx]) {

421 res = 0;

422 goto end;

423 }

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

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

426 }

427

428 end:

429 free(barr);

430 return res;

431 }