Blob


1 #include <fuse_opt.h>
2 #include <libgen.h>
3 #include <unistd.h>
4 #include <string.h>
5 #include <stdlib.h>
6 #include <stdio.h>
7 #include <errno.h>
8 #include <fuse.h>
9 #include <err.h>
10 #include "sufs.h"
12 #define MIN(a, b) ((a) < (b) ? (a) : (b))
13 #define MAX(a, b) ((a) > (b) ? (a) : (b))
15 enum {
16 KEY_VERSION,
17 KEY_HELP,
18 };
20 static const struct fuse_opt opts[] = {
21 FUSE_OPT_KEY("-V", KEY_VERSION),
22 FUSE_OPT_KEY("-h", KEY_HELP),
23 FUSE_OPT_END
24 };
25 static struct sufs_superblock sb;
26 static char *buffer, *dbuffer;
27 static int fd;
29 static void write_inode (uint64_t, const struct sufs_inode *);
30 static struct sufs_inode read_inode (uint64_t ino);
32 void read_block (uint64_t b, char *d)
33 {
34 printf ("read_block(%zu);\n", (size_t)b);
35 if (lseek (fd, b * sb.bsize, SEEK_SET) < 0)
36 err (1, "read_block(): lseek()");
37 if (read (fd, d, sb.bsize) != sb.bsize)
38 err (1, "read_block(): read()");
39 }
41 void write_block (uint64_t b, const char *d)
42 {
43 printf ("write_block(%zu);\n", (size_t)b);
44 if (lseek (fd, b * sb.bsize, SEEK_SET) < 0)
45 err (1, "write_block(): lseek()");
46 if (write (fd, d, sb.bsize) != sb.bsize)
47 err (1, "write_block(): read()");
48 }
50 static uint64_t alloc_bitmap (uint64_t begin, uint64_t len)
51 {
52 uint8_t *p;
54 for (uint64_t i = 0; i < len; i += sb.bsize) {
55 read_block (begin + i, buffer);
56 for (uint32_t j = 0; j < MIN (len, sb.bsize); ++j) {
57 p = buffer + j;
58 if (*p == 0)
59 continue;
61 for (unsigned k = 0; k < 8; ++k) {
62 uint8_t mask = 1 << k;
63 if ((*p & mask) == mask) {
64 printf ("i=%zu, j=%u, k=%u\n", (size_t)i, j, k);
65 *p &= ~mask;
66 write_block (begin + i, buffer);
67 return (i + j) * 8 + k;
68 }
69 }
70 }
71 }
73 return -1;
74 }
76 static void free_bitmap (uint64_t begin, uint64_t idx)
77 {
78 uint64_t blkno;
79 unsigned off, bit;
81 blkno = begin + idx / (8 * sb.bsize);
82 off = (idx / 8) % sb.bsize;
83 bit = idx % 8;
85 printf ("free_bitmap(%zu, %zu, %zu, %u, %u);\n", (size_t)begin, (size_t)idx, (size_t)blkno, off, bit);
87 read_block (blkno, buffer);
88 ((uint8_t *)buffer)[off] |= 1 << bit;
89 write_block (blkno, buffer);
90 }
92 static uint64_t alloc_inode (void)
93 {
94 uint64_t ino = alloc_bitmap (sb.ibmoff, sb.nino);
96 printf ("alloc_inode(): %zu\n", (size_t)ino);
98 return ino;
99 }
101 static void free_dblock (uint64_t blkno)
103 free_bitmap (sb.dbmoff, blkno - sb.doff);
106 static void free_inode (uint64_t ino)
108 struct sufs_inode in;
110 printf ("free_inode(%zu);\n", (size_t)ino);
112 in = read_inode (ino);
114 --in.nlink;
116 if (in.nlink != 0) {
117 write_inode (ino, &in);
118 return;
121 for (uint64_t i = 0; i < MIN (in.blocks, SUFS_NDIRECT); ++i) {
122 free_dblock (in.direct[i]);
125 if (in.blocks >= SUFS_NDIRECT)
126 errx (1, "free_inode(): TODO: indirect blocks");
128 free_bitmap (sb.ibmoff, ino);
131 static uint64_t alloc_dblock (void)
133 uint64_t b = alloc_bitmap (sb.dbmoff, sb.ndata) + sb.doff;
134 memset (buffer, 0, sb.bsize);
135 write_block (b, buffer);
136 printf ("alloc_dblock(): %zu\n", (size_t)b);
137 return b;
140 uint64_t resolve_inode_block (const struct sufs_inode *in, uint64_t blkno)
142 const size_t pbp = sb.bsize / sizeof (uint64_t);
143 volatile uint64_t *tmp = (volatile uint64_t *)buffer;
144 uint64_t i;
146 if (blkno < SUFS_NDIRECT) {
147 return in->direct[blkno];
148 } else if (blkno < (SUFS_NDIRECT + pbp)) {
149 read_block (in->indir[0], buffer);
150 return tmp[blkno - SUFS_NDIRECT];
151 } else if (blkno < (SUFS_NDIRECT + pbp * pbp)) {
152 read_block (in->indir[1], buffer);
153 i = blkno - SUFS_NDIRECT - pbp;
154 read_block (tmp[i / pbp], buffer);
155 return tmp[i % pbp];
156 } else if (blkno < (SUFS_NDIRECT + pbp * pbp * pbp)) {
157 read_block (in->indir[2], buffer);
158 i = blkno - SUFS_NDIRECT - pbp * pbp;
159 read_block (tmp[i / pbp / pbp], buffer);
160 read_block (tmp[i / pbp % pbp], buffer);
161 return tmp[i % pbp];
162 } else {
163 errx (1, "resolve_inode_block(): inode out of range");
167 void free_block (uint64_t block)
169 if (block == 0)
170 return;
172 errx (1, "free_block(): TODO");
175 void map_inode (uint64_t ino, struct sufs_inode *in, uint64_t blkno, uint64_t block)
177 const size_t pbp = sb.bsize / sizeof (uint64_t);
178 volatile uint64_t *tmp = (volatile uint64_t *)buffer;
179 uint64_t i;
181 printf ("map_inode(%zu, %zu, %zu);\n", (size_t)ino, (size_t)blkno, (size_t)block);
183 if (blkno < SUFS_NDIRECT) {
184 free_block (in->direct[blkno]);
185 in->direct[blkno] = block;
186 } else if (blkno < (SUFS_NDIRECT + pbp)) {
187 if (in->indir[0] == 0) {
188 in->indir[0] = alloc_dblock ();
189 write_inode (ino, in);
191 read_block (in->indir[0], buffer);
192 tmp[blkno - SUFS_NDIRECT] = block;
193 write_block (in->indir[0], buffer);
194 } else if (blkno < (SUFS_NDIRECT + pbp * pbp)) {
195 if (in->indir[1] == 0) {
196 in->indir[1] = alloc_dblock ();
197 write_inode (ino, in);
199 read_block (in->indir[1], buffer);
200 i = blkno - SUFS_NDIRECT - pbp;
201 if (tmp[i / pbp] == 0) {
202 tmp[i / pbp] = alloc_dblock ();
203 write_block (in->indir[1], buffer);
205 read_block (tmp[i / pbp], buffer);
206 tmp[i % pbp] = block;
207 write_block (tmp[i % pbp], buffer);
208 } else if (blkno < (SUFS_NDIRECT + pbp * pbp * pbp)) {
209 if (in->indir[2] == 0) {
210 in->indir[2] = alloc_dblock ();
211 write_inode (ino, in);
214 read_block (in->indir[2], buffer);
215 i = blkno - SUFS_NDIRECT - pbp * pbp;
216 if (tmp[i / pbp / pbp] == 0) {
217 tmp[i / pbp / pbp] = alloc_dblock ();
218 write_block (in->indir[2], buffer);
221 read_block (tmp[i / pbp / pbp], buffer);
223 if (tmp[i / pbp % pbp] == 0) {
224 tmp[i / pbp % pbp] = alloc_dblock ();
225 write_block (tmp[i / pbp / pbp], buffer);
227 read_block (tmp[i / pbp % pbp], buffer);
228 tmp[i % pbp] = block;
229 write_block (tmp[i / pbp % pbp], buffer);
230 } else {
231 errx (1, "resolve_inode_block(): inode out of range");
235 void read_block_inode (const struct sufs_inode *in, uint64_t blkno, char *buf)
237 uint64_t b;
239 b = resolve_inode_block (in, blkno);
240 if (b != 0) {
241 read_block (b, buf);
242 } else {
243 memset (buf, 0, sb.bsize);
247 void write_block_inode (uint64_t ino, struct sufs_inode *in, uint64_t blkno, const char *buf)
249 uint64_t b;
251 b = resolve_inode_block (in, blkno);
252 if (b == 0) {
253 b = alloc_dblock ();
254 map_inode (ino, in, blkno, b);
255 ++in->blocks;
256 write_inode (ino, in);
258 write_block (b, buf);
261 static struct sufs_inode read_inode (uint64_t ino)
263 struct sufs_inode in;
264 printf ("read_inode(%zu);\n", (size_t)ino);
265 read_block (sufs_iblk (sb, ino), buffer);
266 memcpy (&in, buffer + sufs_ioff (sb, ino), sizeof (in));
267 return in;
270 static void write_inode (uint64_t ino, const struct sufs_inode *in)
272 printf ("write_inode(%zu);\n", (size_t)ino);
273 read_block (sufs_iblk (sb, ino), buffer);
274 memcpy (buffer + sufs_ioff (sb, ino), in, sizeof (*in));
275 write_block (sufs_iblk (sb, ino), buffer);
278 static uint64_t searchdir (uint64_t ino, const char *name)
280 struct sufs_dirent *ent;
281 struct sufs_inode in;
282 uint64_t i;
283 size_t n, len;
285 printf ("searchdir(%zu, %s);\n", (size_t)ino, name);
287 len = strlen (name);
289 in = read_inode (ino);
290 if ((in.mode & S_IFMT) != S_IFDIR) {
291 errno = ENOTDIR;
292 return 0;
295 for (i = 0; i < in.blocks; ++i) {
296 read_block_inode (&in, i, buffer);
298 for (n = 0; n < sb.bsize; n += ent->size) {
299 ent = (struct sufs_dirent *)(buffer + n);
301 if (ent->ino == 0)
302 break;
304 if (ent->len != len)
305 continue;
307 if (memcmp (name, ent->name, len) == 0)
308 return ent->ino;
312 errno = ENOENT;
313 return 0;
316 static uint64_t lookup2 (char *path)
318 uint64_t parent;
319 char *name, *slash;
320 size_t len;
322 // remove trailing slashes
323 len = strlen (path);
324 while (len > 0 && path[len - 1] == '/')
325 --len;
326 path[len] = '\0';
328 if (len == 0 || strcmp (path, "/") == 0)
329 return SUFS_INO_ROOT;
331 // split path at '/'
332 slash = strrchr (path, '/');
333 if (slash == NULL)
334 errx (1, "lookup2(): failed to split path");
335 *slash = '\0';
336 name = slash + 1;
338 // find parent inode
339 parent = lookup2 (path);
340 if (parent == 0) {
341 return 0;
344 return searchdir (parent, name);
347 static uint64_t lookup (const char *path)
349 uint64_t ino;
350 char *buf;
352 printf ("lookup(\"%s\");\n", path);
354 if (*path != '/') {
355 errno = EINVAL;
356 return 0;
359 buf = strdup (path);
360 ino = lookup2 (buf);
362 free (buf);
363 return ino;
366 int sufs_getattr (const char *path, struct stat *st)
368 struct sufs_inode in;
369 uint64_t ino;
371 printf ("getattr(\"%s\");\n", path);
373 ino = lookup (path);
374 if (ino == 0)
375 return -errno;
377 in = read_inode (ino);
379 st->st_ino = ino;
380 st->st_mode = in.mode;
381 printf ("mode = %o\n", (unsigned)in.mode);
382 st->st_nlink = in.nlink;
383 st->st_uid = in.uid;
384 st->st_gid = in.gid;
385 st->st_atime = in.atime;
386 st->st_mtime = in.mtime;
387 st->st_ctime = in.ctime;
388 st->st_size = in.size;
389 st->st_blocks = in.blocks;
390 st->st_blksize = sb.bsize;
391 return 0;
394 int sufs_open (const char *path, struct fuse_file_info *ffi)
396 uint64_t ino;
398 ino = lookup (path);
399 return ino > 0 ? 0 : -errno;
402 int sufs_read (const char *path, char *buf, size_t size, off_t off, struct fuse_file_info *ffi)
404 struct sufs_inode in;
405 uint64_t ino;
407 printf ("read(\"%s\", %zu, %zu);\n", path, (size_t)off, size);
409 ino = lookup (path);
410 if (ino == 0)
411 return -errno;
413 in = read_inode (ino);
415 if (off > in.size)
416 return 0;
418 if ((off + size) >= sb.bsize)
419 size = sb.bsize - off;
421 if ((off + size) >= in.size)
422 size = in.size - off;
424 read_block_inode (&in, off / sb.bsize, dbuffer);
425 memcpy (buf, dbuffer + off % sb.bsize, size);
427 return size;
430 int sufs_write (const char *path, const char *buf, size_t size, off_t off, struct fuse_file_info *ffi)
432 struct sufs_inode in;
433 uint64_t ino;
435 printf ("write(\"%s\", %zu, %zu);\n", path, size, (size_t)off);
437 ino = lookup (path);
438 if (ino == 0)
439 return -errno;
441 in = read_inode (ino);
443 if ((off + size) >= sb.bsize)
444 size = sb.bsize - off;
446 memcpy (dbuffer + off % sb.bsize, buf, size);
447 write_block_inode (ino, &in, off / sb.bsize, dbuffer);
449 if (off + size >= in.size)
450 in.size = off + size;
452 write_inode (ino, &in);
454 return size;
457 int sufs_readdir (const char *path, void *data, fuse_fill_dir_t filler, off_t off, struct fuse_file_info *ffi)
459 char name[256];
460 struct sufs_dirent *ent;
461 struct sufs_inode in;
462 uint64_t ino;
463 size_t len;
465 if (off != 0)
466 return 0;
468 ino = lookup (path);
469 if (ino == 0)
470 return -errno;
472 in = read_inode (ino);
474 for (uint64_t i = 0; i < in.blocks; ++i) {
475 read_block_inode (&in, i, buffer);
476 for (uint32_t j = 0; j < sb.bsize; j += ent->size) {
477 ent = (struct sufs_dirent *)(buffer + j);
478 if (ent->size == 0)
479 break;
480 len = ent->len;
481 memcpy (name, ent->name, len);
482 name[len] = '\0';
483 filler (data, name, NULL, 0);
488 return 0;
491 int sufs_chown (const char *path, uid_t uid, gid_t gid)
493 struct sufs_inode in;
494 uint64_t ino;
496 printf ("chown(\"%s\", %u, %u);\n", path, (unsigned)uid, (unsigned)gid);
498 ino = lookup (path);
499 if (ino == 0)
500 return -errno;
502 in = read_inode (ino);
504 if (uid != -1)
505 in.uid = uid;
507 if (gid != -1)
508 in.gid = gid;
510 write_inode (ino, &in);
512 return 0;
515 int sufs_chmod (const char *path, mode_t mode)
517 struct sufs_inode in;
518 uint64_t ino;
520 ino = lookup (path);
521 if (ino == 0)
522 return -errno;
524 in = read_inode (ino);
526 in.mode &= ~07777;
527 in.mode |= mode & 07777;
529 write_inode (ino, &in);
531 return 0;
535 static int add_to_dir (uint64_t pino, struct sufs_inode *pin, const char *name, uint64_t ino)
537 struct sufs_dirent *ent, *new;
538 uint16_t rem;
539 uint64_t i, off;
540 size_t len;
542 printf ("add_to_dir(\"%s\", %zu);\n", name, (size_t)ino);
544 len = strlen (name);
545 if (len > 255) {
546 errno = -E2BIG;
547 return -1;
550 for (i = 0; i < pin->blocks; ++i) {
551 read_block_inode (pin, i, buffer);
552 for (uint64_t j = 0; j < sb.bsize; j += ent->size) {
553 ent = (struct sufs_dirent *)(buffer + j);
554 if (ent->size == 0)
555 break;
557 printf ("ent = { ino: %zu, len: %zu, size: %zu, name: \"%*s\" }\n",
558 (size_t)ent->ino, (size_t)ent->len, (size_t)ent->size, (int)ent->len, ent->name);
560 rem = ent->size - ent->len - sizeof (struct sufs_dirent);
562 printf ("rem = %zu\n", (size_t)rem);
564 if (rem < (sizeof (struct sufs_dirent) + len + 8))
565 continue;
567 off = j + sizeof (struct sufs_dirent) + len;
568 off = (off + 7) & ~7;
569 printf ("j = %zu, off = %zu\n", (size_t)j, (size_t)off);
571 new = (struct sufs_dirent *)(buffer + off);
572 new->ino = ino;
573 new->size = rem;
574 new->len = len;
575 memcpy (new->name, name, len);
576 ent->size = off - j;
578 write_block_inode (pino, pin, i, buffer);
579 return 0;
583 errx (1, "add_to_dir(): TODO: allocating new directory blocks");
586 static int find_parent (const char *path, struct sufs_inode *parent)
588 uint64_t ino;
589 char *ppath, *tmp;
591 tmp = strdup (path);
592 ppath = dirname (tmp);
593 ino = lookup (ppath);
594 free (tmp);
595 if (ino == 0)
596 return -1;
598 *parent = read_inode (ino);
599 return (parent->mode & S_IFMT) == S_IFDIR ? 0 : -1;
602 int sufs_mknod (const char *path, mode_t mode, dev_t dev)
604 struct fuse_context *ctx;
605 struct sufs_inode pin, in;
606 uint64_t pino, ino;
607 char *name, *ppath, *tmp;
609 printf ("mknod(\"%s\", %o, %u);\n", path, (unsigned)mode, (unsigned)dev);
611 tmp = strdup (path);
612 ppath = dirname (tmp);
613 pino = lookup (ppath);
614 if (pino == 0)
615 return -errno;
617 pin = read_inode (pino);
618 if ((pin.mode & S_IFMT) != S_IFDIR)
619 return -ENOTDIR;
621 ino = alloc_inode ();
623 ctx = fuse_get_context ();
624 memset (&in, 0, sizeof (in));
625 in.mode = mode;
626 in.nlink = 1;
627 in.uid = ctx->uid;
628 in.gid = pin.gid;
629 in.atime = time (NULL);
630 in.mtime = time (NULL);
631 in.ctime = time (NULL);
633 write_inode (ino, &in);
635 tmp = strdup (path);
636 name = basename (tmp);
637 add_to_dir (pino, &pin, name, ino);
638 return 0;
641 int sufs_create (const char *path, mode_t mode, struct fuse_file_info *ffi)
643 return sufs_mknod (path, mode, 0);
646 int sufs_release (const char *path, struct fuse_file_info *ffi)
648 return 0;
651 int sufs_unlink (const char *path)
653 struct sufs_inode parent, in;
654 const char *name;
655 size_t len;
656 char *tmp;
658 printf ("unlink(\"%s\");\n", path);
660 if (find_parent (path, &parent) != 0)
661 return -errno;
663 tmp = strdup (path);
664 name = basename (tmp);
665 len = strlen (name);
667 for (uint64_t i = 0; i < parent.blocks; ++i) {
668 struct sufs_dirent *ent, *prent;
669 uint64_t blkno, ino;
670 uint32_t prev;
672 blkno = resolve_inode_block (&parent, i);
673 if (blkno == 0)
674 continue;
675 read_block (blkno, buffer);
677 for (uint32_t j = 0, prev = -1; j < sb.bsize; prev = j, j += ent->size) {
678 ent = (struct sufs_dirent *)(buffer + j);
679 ino = ent->ino;
681 if (ino == 0 || len != ent->len)
682 continue;
684 if (memcmp (name, ent->name, len) != 0)
685 continue;
687 if (prev != -1) {
688 prent = (struct sufs_dirent *)(buffer + prev);
689 prent->size += ent->size;
690 } else if (ent->size == sb.bsize) {
691 ent->ino = 0;
692 } else {
693 errx (1, "sufs_unlink(): TODO: removing the first dirent in a block");
696 write_block (blkno, buffer);
697 free_inode (ent->ino);
698 free (tmp);
699 return 0;
704 free (tmp);
705 return -ENOENT;
708 int sufs_utime (const char *path, struct utimbuf *t)
710 struct sufs_inode in;
711 uint64_t ino;
713 ino = lookup (path);
714 if (ino == 0)
715 return -errno;
717 in = read_inode (ino);
718 in.atime = t->actime;
719 in.mtime = t->modtime;
720 write_inode (ino, &in);
721 return 0;
724 struct fuse_operations fsops = {
725 .getattr = sufs_getattr,
726 .open = sufs_open,
727 .read = sufs_read,
728 .write = sufs_write,
729 .readdir = sufs_readdir,
730 .chown = sufs_chown,
731 .chmod = sufs_chmod,
732 .mknod = sufs_mknod,
733 .create = sufs_create,
734 .release = sufs_release,
735 .unlink = sufs_unlink,
736 .utime = sufs_utime,
737 };
739 int opt_parse (void *data, const char *arg, int key, struct fuse_args *outargs)
741 switch (key) {
742 case KEY_VERSION:
743 fputs ("fuse_sufs v0\n", stderr);
744 fuse_opt_add_arg (outargs, "--version");
745 fuse_main (outargs->argc, outargs->argv, &fsops, NULL);
746 exit (0);
747 break;
748 case KEY_HELP:
749 fputs ("usage: fuse_sufs file mountpoint\n", stderr);
750 fuse_opt_add_arg (outargs, "-h");
751 fuse_main (outargs->argc, outargs->argv, &fsops, NULL);
752 exit (1);
753 break;
755 return 1;
758 int main (int argc, char *argv[])
760 struct fuse_args args = FUSE_ARGS_INIT (argc, argv);
761 fuse_opt_parse (&args, NULL, opts, opt_parse);
763 fd = open ("test.img", O_RDWR);
765 if (fd < 0)
766 err (1, "open()");
768 read (fd, &sb, sizeof (sb));
770 if (sb.magic != SUFS_MAGIC) {
771 lseek (fd, SUFS_BOOTSIZE, SEEK_SET);
772 read (fd, &sb, sizeof (sb));
774 if (sb.magic != SUFS_MAGIC)
775 errx (1, "invalid magic");
778 buffer = malloc (sb.bsize);
779 dbuffer = malloc (sb.bsize);
781 return fuse_main (argc, argv, &fsops, NULL);