· 5 years ago · Jul 27, 2020, 11:14 PM
1/*
2
3 MyFS: a tiny file-system written for educational purposes
4
5 MyFS is
6
7 Copyright 2018-20 by
8
9 University of Alaska Anchorage, College of Engineering.
10
11 Contributors: Christoph Lauter
12 ... and
13 ...
14
15 and based on
16
17 FUSE: Filesystem in Userspace
18 Copyright (C) 2001-2007 Miklos Szeredi <miklos@szeredi.hu>
19
20 This program can be distributed under the terms of the GNU GPL.
21 See the file COPYING.
22
23 gcc -Wall myfs.c implementation.c `pkg-config fuse --cflags --libs` -o myfs
24
25*/
26
27#include <stddef.h>
28#include <sys/stat.h>
29#include <sys/statvfs.h>
30#include <stdint.h>
31#include <string.h>
32#include <time.h>
33#include <stdlib.h>
34#include <sys/types.h>
35#include <unistd.h>
36#include <fcntl.h>
37#include <errno.h>
38#include <stdio.h>
39
40
41/* The filesystem you implement must support all the 13 operations
42 stubbed out below. There need not be support for access rights,
43 links, symbolic links. There needs to be support for access and
44 modification times and information for statfs.
45
46 The filesystem must run in memory, using the memory of size
47 fssize pointed to by fsptr. The memory comes from mmap and
48 is backed with a file if a backup-file is indicated. When
49 the filesystem is unmounted, the memory is written back to
50 that backup-file. When the filesystem is mounted again from
51 the backup-file, the same memory appears at the newly mapped
52 in virtual address. The filesystem datastructures hence must not
53 store any pointer directly to the memory pointed to by fsptr; it
54 must rather store offsets from the beginning of the memory region.
55
56 When a filesystem is mounted for the first time, the whole memory
57 region of size fssize pointed to by fsptr reads as zero-bytes. When
58 a backup-file is used and the filesystem is mounted again, certain
59 parts of the memory, which have previously been written, may read
60 as non-zero bytes. The size of the memory region is at least 2048
61 bytes.
62
63 CAUTION:
64
65 * You MUST NOT use any global variables in your program for reasons
66 due to the way FUSE is designed.
67
68 You can find ways to store a structure containing all "global" data
69 at the start of the memory region representing the filesystem.
70
71 * You MUST NOT store (the value of) pointers into the memory region
72 that represents the filesystem. Pointers are virtual memory
73 addresses and these addresses are ephemeral. Everything will seem
74 okay UNTIL you remount the filesystem again.
75
76 You may store offsets/indices (of type size_t) into the
77 filesystem. These offsets/indices are like pointers: instead of
78 storing the pointer, you store how far it is away from the start of
79 the memory region. You may want to define a type for your offsets
80 and to write two functions that can convert from pointers to
81 offsets and vice versa.
82
83 * You may use any function out of libc for your filesystem,
84 including (but not limited to) malloc, calloc, free, strdup,
85 strlen, strncpy, strchr, strrchr, memset, memcpy. However, your
86 filesystem MUST NOT depend on memory outside of the filesystem
87 memory region. Only this part of the virtual memory address space
88 gets saved into the backup-file. As a matter of course, your FUSE
89 process, which implements the filesystem, MUST NOT leak memory: be
90 careful in particular not to leak tiny amounts of memory that
91 accumulate over time. In a working setup, a FUSE process is
92 supposed to run for a long time!
93
94 It is possible to check for memory leaks by running the FUSE
95 process inside valgrind:
96
97 valgrind --leak-check=full ./myfs --backupfile=test.myfs ~/fuse-mnt/ -f
98
99 However, the analysis of the leak indications displayed by valgrind
100 is difficult as libfuse contains some small memory leaks (which do
101 not accumulate over time). We cannot (easily) fix these memory
102 leaks inside libfuse.
103
104 * Avoid putting debug messages into the code. You may use fprintf
105 for debugging purposes but they should all go away in the final
106 version of the code. Using gdb is more professional, though.
107
108 * You MUST NOT fail with exit(1) in case of an error. All the
109 functions you have to implement have ways to indicate failure
110 cases. Use these, mapping your internal errors intelligently onto
111 the POSIX error conditions.
112
113 * And of course: your code MUST NOT SEGFAULT!
114
115 It is reasonable to proceed in the following order:
116
117 (1) Design and implement a mechanism that initializes a filesystem
118 whenever the memory space is fresh. That mechanism can be
119 implemented in the form of a filesystem handle into which the
120 filesystem raw memory pointer and sizes are translated.
121 Check that the filesystem does not get reinitialized at mount
122 time if you initialized it once and unmounted it but that all
123 pieces of information (in the handle) get read back correctly
124 from the backup-file.
125
126 (2) Design and implement functions to find and allocate free memory
127 regions inside the filesystem memory space. There need to be
128 functions to free these regions again, too. Any "global" variable
129 goes into the handle structure the mechanism designed at step (1)
130 provides.
131
132 (3) Carefully design a data structure able to represent all the
133 pieces of information that are needed for files and
134 (sub-)directories. You need to store the location of the
135 root directory in a "global" variable that, again, goes into the
136 handle designed at step (1).
137
138 (4) Write __myfs_getattr_implem and debug it thoroughly, as best as
139 you can with a filesystem that is reduced to one
140 function. Writing this function will make you write helper
141 functions to traverse paths, following the appropriate
142 subdirectories inside the file system. Strive for modularity for
143 these filesystem traversal functions.
144
145 (5) Design and implement __myfs_readdir_implem. You cannot test it
146 besides by listing your root directory with ls -la and looking
147 at the date of last access/modification of the directory (.).
148 Be sure to understand the signature of that function and use
149 caution not to provoke segfaults nor to leak memory.
150
151 (6) Design and implement __myfs_mknod_implem. You can now touch files
152 with
153
154 touch foo
155
156 and check that they start to exist (with the appropriate
157 access/modification times) with ls -la.
158
159 (7) Design and implement __myfs_mkdir_implem. Test as above.
160
161 (8) Design and implement __myfs_truncate_implem. You can now
162 create files filled with zeros:
163
164 truncate -s 1024 foo
165
166 (9) Design and implement __myfs_statfs_implem. Test by running
167 df before and after the truncation of a file to various lengths.
168 The free "disk" space must change accordingly.
169
170 (10) Design, implement and test __myfs_utimens_implem. You can now
171 touch files at different dates (in the past, in the future).
172
173 (11) Design and implement __myfs_open_implem. The function can
174 only be tested once __myfs_read_implem and __myfs_write_implem are
175 implemented.
176
177 (12) Design, implement and test __myfs_read_implem and
178 __myfs_write_implem. You can now write to files and read the data
179 back:
180
181 echo "Hello world" > foo
182 echo "Hallo ihr da" >> foo
183 cat foo
184
185 Be sure to test the case when you unmount and remount the
186 filesystem: the files must still be there, contain the same
187 information and have the same access and/or modification
188 times.
189
190 (13) Design, implement and test __myfs_unlink_implem. You can now
191 remove files.
192
193 (14) Design, implement and test __myfs_unlink_implem. You can now
194 remove directories.
195
196 (15) Design, implement and test __myfs_rename_implem. This function
197 is extremely complicated to implement. Be sure to cover all
198 cases that are documented in man 2 rename. The case when the
199 new path exists already is really hard to implement. Be sure to
200 never leave the filessystem in a bad state! Test thoroughly
201 using mv on (filled and empty) directories and files onto
202 inexistant and already existing directories and files.
203
204 (16) Design, implement and test any function that your instructor
205 might have left out from this list. There are 13 functions
206 __myfs_XXX_implem you have to write.
207
208 (17) Go over all functions again, testing them one-by-one, trying
209 to exercise all special conditions (error conditions): set
210 breakpoints in gdb and use a sequence of bash commands inside
211 your mounted filesystem to trigger these special cases. Be
212 sure to cover all funny cases that arise when the filesystem
213 is full but files are supposed to get written to or truncated
214 to longer length. There must not be any segfault; the user
215 space program using your filesystem just has to report an
216 error. Also be sure to unmount and remount your filesystem,
217 in order to be sure that it contents do not change by
218 unmounting and remounting. Try to mount two of your
219 filesystems at different places and copy and move (rename!)
220 (heavy) files (your favorite movie or song, an image of a cat
221 etc.) from one mount-point to the other. None of the two FUSE
222 processes must provoke errors. Find ways to test the case
223 when files have holes as the process that wrote them seeked
224 beyond the end of the file several times. Your filesystem must
225 support these operations at least by making the holes explicit
226 zeros (use dd to test this aspect).
227
228 (18) Run some heavy testing: copy your favorite movie into your
229 filesystem and try to watch it out of the filesystem.
230
231*/
232
233/* Helper types and functions */
234typedef enum{
235 Empty,
236 File,
237 Directory,
238 Stockpile,
239} blockTypes;
240
241typedef uint32_t offset_t;
242
243typedef struct FS_header_t {
244 offset_t freeblock_tail; // points to the tail block of the linked list of available freeblock numbers (stored in blocks)
245 // int freeblock_count; // might need later
246 _Bool is_setup;
247 int total_blocks;
248 struct timespec tempTime;
249 int root_dir;
250} FS_header_t;
251
252#define TRUE 1
253#define FALSE 0
254#define BLOCK_SIZE 4096
255#define CHAR_LIMIT_INCLUDE_NULL 256
256#define START_OFFSET sizeof(FS_header_t)
257#define PATH_SEPARATOR ("/")
258
259typedef struct entry_t {
260 char file_name[CHAR_LIMIT_INCLUDE_NULL];
261 int block_num;
262} entry_t;
263
264typedef struct block_t {
265 int block_num;
266 blockTypes content_type;
267 size_t bytes_occupied;
268} block_t;
269
270typedef struct file_t {
271 int next_block;
272 struct timespec atim;
273 struct timespec mtim;
274} file_t;
275
276typedef struct directory_t {
277 int next_block;
278 struct timespec atim;
279 struct timespec mtim;
280 int entry_count;
281 int furthest_index;
282 // entries written under it (up to 15)
283} directory_t;
284
285// a linked list of blocks holding a stack of empty block numbers
286typedef struct freeblock_t {
287 int next_block;
288 int prev_block;
289 int freeblock_count;
290} freeblock_t;
291
292#define FREE_BLOCK_NUMBERS_PER_BLOCK (BLOCK_SIZE - sizeof(block_t) - sizeof(freeblock_t))/sizeof(int)
293#define ENTRIES_PER_BLOCK (BLOCK_SIZE-sizeof(block_t)-sizeof(directory_t))/sizeof(entry_t)
294
295// typedef struct file_header_t {
296//
297// } file_header_t;
298//
299// typedef struct block_header_t {
300//
301// } block_header_t;
302
303/* YOUR HELPER FUNCTIONS GO HERE */
304// FS_header_t* initialize_FS(void* fsptr, size_t fssize) {
305// return (FS_header_t*) fsptr;
306// }
307// start_fs()
308// get_free_block()
309// return_free_block()
310// typedef struct freeblock {
311//
312// }
313
314
315
316
317// block goes from 0 to total_blocks-1
318block_t* retrieve_block(void *fsptr, int n) {
319 offset_t offset = n*BLOCK_SIZE;
320 block_t *block = (block_t*) (fsptr+START_OFFSET+offset);
321 //sizeof(block_t)
322 return block;
323}
324
325// initializes each block with its block number, needed for pointing to next/prev, (could also give them number in retrieve block function if takes too long)
326int initialize_blocks(FS_header_t *handle) {
327 for (int i=0; i<handle->total_blocks; i++) {
328 block_t *block = retrieve_block((void*)handle, i);
329 block->block_num = i;
330 block->bytes_occupied = sizeof(block_t);
331 }
332 return 0;
333}
334
335freeblock_t* get_stockpile_header(block_t*);
336int* get_stockpile_num_array(block_t*);
337
338
339// returns pointer under the block header
340void* __get_header(block_t* block) {
341 void *ptr = (void*)block;
342 return ptr+sizeof(block_t);
343}
344
345file_t* get_file_header(block_t *file_block) {
346 if (file_block->content_type != File) {
347 fprintf(stderr, "file_block is not a file block\n");
348 return NULL;
349 }
350 return (file_t*)__get_header(file_block);
351}
352
353void* get_file_content(block_t *file_block) {
354 if (file_block->content_type != File) {
355 fprintf(stderr, "file_block is not a file block\n");
356 return NULL;
357 }
358 return ((void*)file_block)+sizeof(file_t)+sizeof(block_t);
359}
360
361directory_t* get_directory_header(block_t *dir_block) {
362 if (dir_block->content_type != Directory) {
363 fprintf(stderr, "dir_block is not a directory block\n");
364 return NULL;
365 }
366 return (directory_t*)__get_header(dir_block);
367}
368
369entry_t* get_directory_entries(block_t *dir_block) {
370 if (dir_block->content_type != Directory) {
371 fprintf(stderr, "dir_block is not a directory block\n");
372 return NULL;
373 }
374 return (entry_t*)(((void*)dir_block)+sizeof(directory_t)+sizeof(block_t));
375}
376
377freeblock_t* get_stockpile_header(block_t *stockpile_block) {
378 if (stockpile_block->content_type != Stockpile) {
379 fprintf(stderr, "stockpile_block is not a stockpile block\n");
380 return NULL;
381 }
382 return (freeblock_t*)__get_header(stockpile_block);
383}
384
385int* get_stockpile_num_array(block_t *stockpile_block) {
386 if (stockpile_block->content_type != Stockpile) {
387 fprintf(stderr, "stockpile_block is not a stockpile block\n");
388 return NULL;
389 }
390 return (int*)(((void*)stockpile_block)+sizeof(freeblock_t)+sizeof(block_t));
391}
392
393// only called by setup_filesystem
394// initializes the root directory
395// store_file(int startingBlock)
396struct timespec get_time(FS_header_t* globals) {
397 // are we allowed to use the stack or no?
398 // get deleted after moving out of stack
399 clock_gettime(CLOCK_REALTIME, &(globals->tempTime));
400 return globals->tempTime;
401}
402
403int set_dir_time(directory_t *header, _Bool has_been_modified) {
404 struct timespec temp_time;
405 clock_gettime(CLOCK_REALTIME, &(temp_time));
406 header->atim = temp_time;
407 if (has_been_modified) {
408 header->mtim = temp_time;
409 }
410 return 0;
411}
412
413int set_file_time(file_t *header, _Bool has_been_modified) {
414 struct timespec temp_time;
415 clock_gettime(CLOCK_REALTIME, &(temp_time));
416 header->atim = temp_time;
417 if (has_been_modified) {
418 header->mtim = temp_time;
419 }
420 return 0;
421}
422
423int set_block_time(block_t *block, _Bool has_been_modified) {
424 int return_value;
425 if (block->content_type == Directory) {
426 return_value = set_dir_time(get_directory_header(block), has_been_modified);
427 } else if (block->content_type == File) {
428 return_value = set_file_time(get_file_header(block), has_been_modified);
429 }
430 return return_value;
431}
432
433block_t* clean_block(FS_header_t *handle, block_t *block) {
434 if (block->content_type == Empty) {
435 fprintf(stderr, "block is already clean\n");
436 return NULL;
437 }
438 else if (block->content_type == File){
439 /*STUB*/
440 }
441 else if (block->content_type == Directory){
442 /*STUB*/
443 }
444 else if (block->content_type == Stockpile){
445 freeblock_t *header = get_stockpile_header(block);
446 // make sure stockpile is tail end of linked list;
447 if (header->prev_block == -1 || header->next_block != -1) {
448 fprintf(stderr, "only tail end of stockpile block may be deleted\n");
449 return NULL;
450 }
451 // make sure there are no entries
452 if (header->freeblock_count > 0) {
453 fprintf(stderr, "must store no freeblocks to format\n");
454 return NULL;
455 }
456 // make sure it is pointed to by handle / if block num is accurate
457 if (handle->freeblock_tail != block->block_num) {
458 fprintf(stderr, "handle->freeblock_tail is not storing this block's number\n");
459 return NULL;
460 }
461 // finally do stuff
462 // make previous block's next to -1
463 block_t* prev_block = retrieve_block((void*)handle, header->prev_block);
464 freeblock_t* prev_block_header = get_stockpile_header(prev_block);
465 prev_block_header->next_block = -1;
466
467 // make handle->tail point to prev block
468 handle->freeblock_tail = header->prev_block;
469
470 //format block
471 char *zeroes = (char*)header;
472 for (int i=0; i<BLOCK_SIZE-sizeof(block_t); i++) {
473 zeroes[i] = 0;
474 }
475
476 // convert block type to Empty
477 block->content_type = Empty;
478
479 // put size to initial
480 block->bytes_occupied = sizeof(block_t);
481
482 return block;
483 }
484 fprintf(stderr, "invalid block content type\n");
485 return NULL;
486}
487
488block_t* get_stockpile_block(void *fsptr, int block_num) {
489 block_t *empty_block = retrieve_block(fsptr, block_num);
490 // error if block specified is not empty
491 if (empty_block->content_type != Empty || empty_block->bytes_occupied > sizeof(block_t)) {
492 fprintf(stderr, "ERROR: cannot convert non-empty block\n");
493 return NULL;
494 }
495 // initialize default stockpile values
496 empty_block->content_type = Stockpile;
497
498 freeblock_t *freeblock_header = (freeblock_t*)(((void*)empty_block)+sizeof(block_t));
499 freeblock_header->next_block = -1;
500 freeblock_header->prev_block = -1;
501 empty_block->bytes_occupied = sizeof(block_t)+sizeof(freeblock_t);
502
503 return empty_block;
504}
505
506// internal function to push the number into the stockpile block, does not check if full or if it will fit
507int __push_free_block_num(block_t *stockpile_block, int block_num) {
508 freeblock_t *header = (freeblock_t*)(((void*)stockpile_block)+sizeof(block_t));
509 int *numbers = (int*)(((void*)header)+sizeof(freeblock_t));
510
511 int count = header->freeblock_count;
512 numbers[count] = block_num;
513 stockpile_block->bytes_occupied += sizeof(int);
514 header->freeblock_count++;
515 return 0;
516}
517
518// used to push the cleared block back on the stack for others to use
519int push_free_block_num(FS_header_t *handle, int block_num) {
520 _Bool is_empty = retrieve_block((void*)handle, block_num)->content_type == Empty;
521 if (!is_empty) {
522 fprintf(stderr, "block_num describes non-empty block\n");
523 return -1;
524 }
525
526 block_t* stockpile = retrieve_block((void*)handle, handle->freeblock_tail);
527
528 _Bool array_is_full = BLOCK_SIZE-stockpile->bytes_occupied < sizeof(int);
529 if (array_is_full) {
530 block_t* new_stockpile = get_stockpile_block((void*)handle, block_num);
531 freeblock_t* new_header = get_stockpile_header(new_stockpile);
532 new_header->prev_block = handle->freeblock_tail;
533 handle->freeblock_tail = block_num;
534 }
535 else {
536 __push_free_block_num(stockpile, block_num);
537 }
538 return 0;
539}
540
541int pop_free_block_num(FS_header_t *handle) {
542 // if there is no freeblocks in the stockpile, empty stockpile and offer it as freeblock, change handle tail to prev block
543 if (handle->freeblock_tail == -1) {
544 fprintf(stderr, "ERROR: Out of space\n");
545 return -1;
546 }
547 block_t* stockpile = retrieve_block((void*)handle, handle->freeblock_tail);
548 freeblock_t* header = get_stockpile_header(stockpile);
549 int* array = get_stockpile_num_array(stockpile);
550
551 int last_element = header->freeblock_count-1;
552 if (header->freeblock_count > 0) {
553 int block_num = array[last_element];
554 // delete the remnants
555 array[last_element] = 0;
556 header->freeblock_count--;
557 return block_num;
558 } else if (header->freeblock_count == 0){
559 // convert block into free block
560 block_t* cleared_block = clean_block(handle, stockpile);
561 return cleared_block->block_num;
562 } else {
563 fprintf(stderr, "ERROR: freeblock count is off\n");
564 return -1;
565 }
566 return 0;
567}
568
569int setup_free_blocks(FS_header_t *handle, int starting_block) {
570 block_t *stockpile_block = get_stockpile_block((void*)handle, starting_block);
571 freeblock_t *header = (freeblock_t*)(((void*)stockpile_block)+sizeof(block_t));
572
573 _Bool has_enough_space = 1;
574 // goes from n-2 to 0, uinitialized points to 0 (reserved for root directory "/")
575 for (int i=handle->total_blocks-2; i>=0; i--) {
576 has_enough_space = BLOCK_SIZE - stockpile_block->bytes_occupied >= 4;
577 if (has_enough_space) {
578 __push_free_block_num(stockpile_block, i);
579 } else {
580 // append to linked list, update handle->tail
581 int prev_num = stockpile_block->block_num;
582 header->next_block = i;
583 handle->freeblock_tail = i;
584 stockpile_block = get_stockpile_block((void*)handle, i);
585 header = get_stockpile_header(stockpile_block);
586 header->prev_block = prev_num;
587 }
588 }
589 return 0;
590}
591
592block_t* get_free_block(FS_header_t *handle) {
593 return retrieve_block((void*)handle, pop_free_block_num(handle));
594}
595
596int find_empty_entry(block_t *dir_block) {
597 // assume push and pop for now
598 directory_t *dir_header = get_directory_header(dir_block);
599 entry_t *dir_entries = get_directory_entries(dir_block);
600 int search_this_many = dir_header->entry_count+1;
601 for (int i = 0; i<search_this_many; i++) {
602 if (strncmp(dir_entries[i].file_name,"\0\0\0\0\0",5)) {
603 return i;
604 }
605 }
606 return -1;
607}
608
609block_t* get_file_block(FS_header_t *handle) {
610 // creates an inode referring to all the files as well as the file_t
611 block_t *file_block = get_free_block(handle);
612 file_block->content_type = File;
613 file_t *file_header = get_file_header(file_block);
614
615 // set the time
616 set_file_time(file_header, TRUE);
617
618 return file_block;
619}
620
621block_t* get_dir_block(FS_header_t *handle) {
622 block_t *dir_block = get_free_block(handle);
623 dir_block->content_type = Directory;
624 directory_t *dir_header = get_directory_header(dir_block);
625 dir_header->next_block = -1;
626 dir_header->entry_count = 0;
627
628 // set the time
629 set_dir_time(dir_header, TRUE);
630
631 return dir_block;
632}
633
634int __update_furthest_index(int furthest, entry_t *entries) {
635 for (int i = furthest-1; i>=0; i--) {
636 if (strncmp(entries[i].file_name, "\0", 1) != 0) {
637 return i;
638 }
639 }
640 return 0;
641}
642
643int __clear_entry(entry_t *entries, int i) {
644 // only have to clear to the first null
645 entries[i].block_num = 0;
646 char *fill_null = (char*)(&entries[i]);
647 for (int i=0; i<CHAR_LIMIT_INCLUDE_NULL; i++) {
648 if (fill_null[i] == '\0') {
649 break;
650 }
651 fill_null[i] = '\0';
652 }
653 return 0;
654}
655
656// removes file/ directory entry from directory entry array
657int __remove_entry(block_t *dir_block, int block_num) {
658 directory_t *dir_header = get_directory_header(dir_block);
659 entry_t *dir_entries = get_directory_entries(dir_block);
660 // find if there's any entries not in use
661 for (int i=0; i<=dir_header->furthest_index; i++) {
662 if (strncmp(dir_entries[i].file_name, "\0", 1) != 0) {
663 if (dir_entries[i].block_num == block_num) {
664 __clear_entry(dir_entries, i);
665 dir_header->entry_count--;
666 dir_block->bytes_occupied -= sizeof(entry_t);
667 if (i >= dir_header->furthest_index-1) {
668 dir_header->furthest_index -= 1; // __update_furthest_index(dir_header->furthest_index, dir_entries);
669 }
670 set_dir_time(dir_header, TRUE);
671 return 0;
672 }
673 }
674 }
675 return -1;
676}
677
678// inserts the file/directory content into the directory's entry array
679int __insert_entry(block_t *dir_block, char *name, int block_num) {
680 directory_t *dir_header = get_directory_header(dir_block);
681 entry_t *dir_entries = get_directory_entries(dir_block);
682 // check if there's space
683 _Bool has_space = BLOCK_SIZE - dir_block->bytes_occupied > sizeof(int);
684 if (!has_space) {
685 // todo: add new page to directory
686 fprintf(stderr, "directory is out of space!\n");
687 return -1;
688 }
689 // find if there's any entries not in use
690 for (int i=0; i<=dir_header->furthest_index; i++) {
691 if (strncmp(dir_entries[i].file_name, "\0", 1) == 0) {
692 // add entry HERE
693 strcpy(dir_entries[i].file_name, name);
694 dir_entries[i].block_num = block_num;
695 dir_header->entry_count++;
696 if (i >= dir_header->furthest_index-1) {
697 dir_header->furthest_index = i+1;
698 }
699 dir_block->bytes_occupied += sizeof(entry_t);
700 // modify time
701 set_dir_time(dir_header, TRUE);
702 return 0;
703 }
704 }
705 return -1;
706}
707
708int new_entry(block_t *parent, block_t *content_block, char *name) {
709 // check if parent is directory_t
710 if (parent->content_type != Directory) {
711 fprintf(stderr, "parent must be a directory\n");
712 return -1;
713 }
714 if (!(content_block->content_type == File || content_block->content_type == Directory)) {
715 fprintf(stderr, "can only insert new directories and files\n");
716 return -1;
717 }
718 return __insert_entry(parent, name, content_block->block_num);
719}
720
721int remove_entry(block_t *parent, block_t *content_block) {
722 // check if parent is directory_t
723 if (parent->content_type != Directory) {
724 fprintf(stderr, "parent must be a directory\n");
725 return -1;
726 }
727 if (!(content_block->content_type == File || content_block->content_type == Directory)) {
728 fprintf(stderr, "can only remove directories and files\n");
729 return -1;
730 }
731 if (content_block->content_type == Directory) {
732 directory_t *temp_header = get_directory_header(content_block);
733 if (temp_header->entry_count > 0) {
734 fprintf(stderr, "directory must be empty\n");
735 return -1;
736 }
737 }
738 return __remove_entry(parent, content_block->block_num);
739}
740
741// int create_directory(FS_header_t *handle, block_t *parent) {
742// block_t *dir_block = get_dir_block(handle);
743// block_t
744// }
745
746// int create_file(FS_header_t *handle, block_t *dir_block, const char *name) {
747// // check if dir_block is directory_t
748// directory_t *dir_header = get_directory_header(dir_block);
749// entry_t *dir_entries = get_directory_entries(dir_block);
750//
751// int count = dir_header->entry_count;
752// strcpy(dir_entries[count].file_name, name);
753// int file_start = get_file_block(handle)->block_num;
754// dir_entries[count].block_num = file_start;
755// dir_header->entry_count++;
756// return 0;
757// }
758
759int create_root_directory(FS_header_t *handle) {
760 block_t *dir_block = get_dir_block(handle);
761 handle->root_dir = dir_block->block_num;
762 return 0;
763}
764
765// allocates blocks for filesystem and sets up the globals_handle
766int setup_filesystem(FS_header_t *handle, size_t fssize, int *errnoptr) {
767 size_t total_storage_bytes = fssize - START_OFFSET;
768 int total_blocks = total_storage_bytes/BLOCK_SIZE;
769 handle->total_blocks = total_blocks;
770 handle->is_setup = TRUE;
771 handle->freeblock_tail = START_OFFSET;
772 // setup up freeblock system (stockpiles grow from the bottom up)
773 initialize_blocks(handle);
774 setup_free_blocks(handle, total_blocks-1);
775 // setup the root directory
776 create_root_directory(handle);
777 // add entry to directory
778 return 0;
779}
780
781
782
783
784size_t str_len(char *str) {
785 size_t length = 0;
786 for (char *c = str; *c; c++) {
787 length++;
788 }
789 return length;
790}
791
792_Bool is_dir(block_t *block) {
793 if (block->content_type == Directory) {
794 return 1;
795 }
796 return 0;
797}
798
799int search_directory(block_t *dir_block, char* file_name) {
800 directory_t *dir_header;
801 entry_t *dir_entries;
802
803 if (!is_dir(dir_block)) {
804 fprintf(stderr, "cannot search into non directory block\n");
805 return -1;
806 }
807
808 dir_header = get_directory_header(dir_block);
809 dir_entries = get_directory_entries(dir_block);
810 // assumes push and pop directories for now
811 int count = dir_header->entry_count;
812 for (int i = 0; i < count; i++) {
813 if (strncmp(dir_entries[i].file_name,"\0", 1) != 0) {
814 if (strcmp(dir_entries[i].file_name, file_name) == 0) {
815 return dir_entries[i].block_num;
816 }
817 }
818 }
819 return -1;
820}
821
822block_t* find_root (FS_header_t *handle) {
823 return retrieve_block((void*)handle, handle->root_dir);
824}
825
826block_t* resolve_path(FS_header_t *handle, const char *path) {
827 // working dir support?
828 // if path begins with /
829 char *temp,*found;
830 block_t *root_dir = find_root(handle);
831 block_t *prev_dir;
832 int result;
833
834 if (strncmp(path, PATH_SEPARATOR, 1) != 0) {
835 fprintf(stderr, "path must start with /\n");
836 return NULL;
837 }
838
839 if (strcmp(path, PATH_SEPARATOR)==0) {
840 return root_dir;
841 }
842
843 temp = strdup(path);
844 prev_dir = root_dir;
845 while ((found = strsep(&temp, PATH_SEPARATOR)) != NULL ) {
846 if ((result=search_directory(prev_dir, found)) != -1) {
847 prev_dir = retrieve_block((void*)handle, result);
848 }
849 }
850 free(temp);
851 return prev_dir;
852 // split path into tokens / / /
853 // get index of each / token
854 // read between the slashes
855 // find /, find root, find dir, find file.txt
856}
857
858void test_program(FS_header_t *handle, size_t fssize, int *errnoptr) {
859 block_t *root = get_dir_block(handle);
860 block_t *dir = get_dir_block(handle);
861 block_t *file = get_file_block(handle);
862 block_t *file2 = get_file_block(handle);
863
864 new_entry(find_root(handle), root, "root");
865 new_entry(root, dir, "dir");
866 new_entry(dir, file, "file.txt");
867 new_entry(dir, file2, "file2.txt");
868
869 block_t *result_block = resolve_path(handle, "/root/dir/file.txt");
870
871 remove_entry(dir, result_block);
872 remove_entry(root, dir);
873 remove_entry(dir, file2);
874 block_t *new = get_dir_block(handle);
875 new_entry(dir, new, "new");
876 remove_entry(dir, file);
877 remove_entry(root, dir);
878
879 block_t *text = get_file_block(handle);
880 new_entry(new, text, "text.txt");
881}
882
883FS_header_t* get_handle(void *fsptr, size_t fssize, int *errnoptr) {
884 // write some stuff at 0
885 FS_header_t *handle = (FS_header_t *) fsptr;
886 if (!handle->is_setup) {
887 setup_filesystem(handle, fssize, errnoptr);
888 }
889 // get a block, cast it into a file struct, write a long string into the file, read the string
890 // test_program(handle, fssize, errnoptr);
891 return handle;
892
893}
894
895
896
897
898
899/* End of helper functions */
900
901/* Implemegetnts an emulation of the stat system call on the filesystem
902 of size fssize pointed to by fsptr.
903
904 If path can be followed and describes a file or directory
905 that exists and is accessable, the access information is
906 put into stbuf.
907
908 On success, 0 is returned. On failure, -1 is returned and
909 the appropriate error code is put into *errnoptr.
910
911 man 2 stat documents all possible error codes and gives more detail
912 on what fields of stbuf need to be filled in. Essentially, only the
913 following fields need to be supported:
914
915 st_uid the value passed in argument
916 st_gid the value passed in argument
917 st_mode (as fixed values S_IFDIR | 0755 for directories,
918 S_IFREG | 0755 for files)
919 st_nlink (as many as there are subdirectories (not files) for directories
920 (including . and ..),
921 1 for files)
922 st_size (supported only for files, where it is the real file size)
923 st_atim
924 st_mtim
925
926*/
927int __myfs_getattr_implem(void *fsptr, size_t fssize, int *errnoptr,
928 uid_t uid, gid_t gid,
929 const char *path, struct stat *stbuf) {
930 // get the handle / table of everything
931 FS_header_t* handle = get_handle(fsptr, fssize, errnoptr);
932 block_t* block = resolve_path(handle, path);
933 // flush buffer
934 memset(stbuf, 0, sizeof(struct stat));
935
936 stbuf->st_uid = uid;
937 stbuf->st_gid = gid;
938 if (block->content_type == Directory) {
939 directory_t *dir_header = get_directory_header(block);
940 stbuf->st_mode = S_IFDIR | 0755;
941 stbuf->st_nlink = get_directory_header(block)->entry_count+2; //+2 counts . and ..
942 stbuf->st_atim = dir_header->atim;
943 stbuf->st_mtim = dir_header->mtim;
944 }
945 else if (block->content_type == File) {
946 file_t *file_header = get_file_header(block);
947 stbuf->st_mode = S_IFREG | 0755;
948 stbuf->st_nlink = 1;
949 stbuf->st_size = block->bytes_occupied;
950 stbuf->st_atim = file_header->atim;
951 stbuf->st_mtim = file_header->mtim;
952 }
953
954 // figure out if it's a directory or file
955 //struct timespec currTime; // this variable is on the stack so is that ok?
956 //clock_gettime(CLOCK_REALTIME, &currTime);
957 return 0;
958}
959
960/* Implements an emulation of the readdir system call on the filesystem
961 of size fssize pointed to by fsptr.
962
963 If path can be followed and describes a directory that exists and
964 is accessable, the names of the subdirectories and files
965 contained in that directory are output into *namesptr. The . and ..
966 directories must not be included in that listing.
967
968 If it needs to output file and subdirectory names, the function
969 starts by allocating (with calloc) an array of pointers to
970 characters of the right size (n entries for n names). Sets
971 *namesptr to that pointer. It then goes over all entries
972 in that array and allocates, for each of them an array of
973 characters of the right size (to hold the i-th name, together
974 with the appropriate '\0' terminator). It puts the pointer
975 into that i-th array entry and fills the allocated array
976 of characters with the appropriate name. The calling function
977 will call free on each of the entries of *namesptr and
978 on *namesptr.
979
980 The function returns the number of names that have been
981 put into namesptr.
982
983 If no name needs to be reported because the directory does
984 not contain any file or subdirectory besides . and .., 0 is
985 returned and no allocation takes place.
986
987 On failure, -1 is returned and the *errnoptr is set to
988 the appropriate error code.
989
990 The error codes are documented in man 2 readdir.
991
992 In the case memory allocation with malloc/calloc fails, failure is
993 indicated by returning -1 and setting *errnoptr to EINVAL.
994
995*/
996int __myfs_readdir_implem(void *fsptr, size_t fssize, int *errnoptr,
997 const char *path, char ***namesptr) {
998 /* STUB */
999 return -1;
1000}
1001
1002/* Implements an emulation of the mknod system call for regular files
1003 on the filesystem of size fssize pointed to by fsptr.
1004
1005 This function is called only for the creation of regular files.
1006
1007 If a file gets created, it is of size zero and has default
1008 ownership and mode bits.
1009
1010 The call creates the file indicated by path.
1011
1012 On success, 0 is returned.
1013
1014 On failure, -1 is returned and *errnoptr is set appropriately.
1015
1016 The error codes are documented in man 2 mknod.
1017
1018*/
1019int __myfs_mknod_implem(void *fsptr, size_t fssize, int *errnoptr,
1020 const char *path) {
1021 /* STUB */
1022 return -1;
1023}
1024
1025/* Implements an emulation of the unlink system call for regular files
1026 on the filesystem of size fssize pointed to by fsptr.
1027
1028 This function is called only for the deletion of regular files.
1029
1030 On success, 0 is returned.
1031
1032 On failure, -1 is returned and *errnoptr is set appropriately.
1033
1034 The error codes are documented in man 2 unlink.
1035
1036*/
1037int __myfs_unlink_implem(void *fsptr, size_t fssize, int *errnoptr,
1038 const char *path) {
1039 /* STUB */
1040 return -1;
1041}
1042
1043/* Implements an emulation of the rmdir system call on the filesystem
1044 of size fssize pointed to by fsptr.
1045
1046 The call deletes the directory indicated by path.
1047
1048 On success, 0 is returned.
1049
1050 On failure, -1 is returned and *errnoptr is set appropriately.
1051
1052 The function call must fail when the directory indicated by path is
1053 not empty (if there are files or subdirectories other than . and ..).
1054
1055 The error codes are documented in man 2 rmdir.
1056
1057*/
1058int __myfs_rmdir_implem(void *fsptr, size_t fssize, int *errnoptr,
1059 const char *path) {
1060 /* STUB */
1061 return -1;
1062}
1063
1064/* Implements an emulation of the mkdir system call on the filesystem
1065 of size fssize pointed to by fsptr.
1066
1067 The call creates the directory indicated by path.
1068
1069 On success, 0 is returned.
1070
1071 On failure, -1 is returned and *errnoptr is set appropriately.
1072
1073 The error codes are documented in man 2 mkdir.
1074
1075*/
1076int __myfs_mkdir_implem(void *fsptr, size_t fssize, int *errnoptr,
1077 const char *path) {
1078 /* STUB */
1079 return -1;
1080}
1081
1082/* Implements an emulation of the rename system call on the filesystem
1083 of size fssize pointed to by fsptr.
1084
1085 The call moves the file or directory indicated by from to to.
1086
1087 On success, 0 is returned.
1088
1089 On failure, -1 is returned and *errnoptr is set appropriately.
1090
1091 Caution: the function does more than what is hinted to by its name.
1092 In cases the from and to paths differ, the file is moved out of
1093 the from path and added to the to path.
1094
1095 The error codes are documented in man 2 rename.
1096
1097*/
1098int __myfs_rename_implem(void *fsptr, size_t fssize, int *errnoptr,
1099 const char *from, const char *to) {
1100 /* STUB */
1101 return -1;
1102}
1103
1104/* Implements an emulation of the truncate system call on the filesystem
1105 of size fssize pointed to by fsptr.
1106
1107 The call changes the size of the file indicated by path to offset
1108 bytes.
1109
1110 When the file becomes smaller due to the call, the extending bytes are
1111 removed. When it becomes larger, zeros are appended.
1112
1113 On success, 0 is returned.
1114
1115 On failure, -1 is returned and *errnoptr is set appropriately.
1116
1117 The error codes are documented in man 2 truncate.
1118
1119*/
1120int __myfs_truncate_implem(void *fsptr, size_t fssize, int *errnoptr,
1121 const char *path, off_t offset) {
1122 /* STUB */
1123 return -1;
1124}
1125
1126/* Implements an emulation of the open system call on the filesystem
1127 of size fssize pointed to by fsptr, without actually performing the opening
1128 of the file (no file descriptor is returned).
1129
1130 The call just checks if the file (or directory) indicated by path
1131 can be accessed, i.e. if the path can be followed to an existing
1132 object for which the access rights are granted.
1133
1134 On success, 0 is returned.
1135
1136 On failure, -1 is returned and *errnoptr is set appropriately.
1137
1138 The two only interesting error codes are
1139
1140 * EFAULT: the filesystem is in a bad state, we can't do anything
1141
1142 * ENOENT: the file that we are supposed to open doesn't exist (or a
1143 subpath).
1144
1145 It is possible to restrict ourselves to only these two error
1146 conditions. It is also possible to implement more detailed error
1147 condition answers.
1148
1149 The error codes are documented in man 2 open.
1150
1151*/
1152int __myfs_open_implem(void *fsptr, size_t fssize, int *errnoptr,
1153 const char *path) {
1154 /* STUB */
1155 return -1;
1156}
1157
1158/* Implements an emulation of the read system call on the filesystem
1159 of size fssize pointed to by fsptr.
1160
1161 The call copies up to size bytes from the file indicated by
1162 path into the buffer, starting to read at offset. See the man page
1163 for read for the details when offset is beyond the end of the file etc.
1164
1165 On success, the appropriate number of bytes read into the buffer is
1166 returned. The value zero is returned on an end-of-file condition.
1167
1168 On failure, -1 is returned and *errnoptr is set appropriately.
1169
1170 The error codes are documented in man 2 read.
1171
1172*/
1173int __myfs_read_implem(void *fsptr, size_t fssize, int *errnoptr,
1174 const char *path, char *buf, size_t size, off_t offset) {
1175 /* STUB */
1176 return -1;
1177}
1178
1179/* Implements an emulation of the write system call on the filesystem
1180 of size fssize pointed to by fsptr.
1181
1182 The call copies up to size bytes to the file indicated by
1183 path into the buffer, starting to write at offset. See the man page
1184 for write for the details when offset is beyond the end of the file etc.
1185
1186 On success, the appropriate number of bytes written into the file is
1187 returned. The value zero is returned on an end-of-file condition.
1188
1189 On failure, -1 is returned and *errnoptr is set appropriately.
1190
1191 The error codes are documented in man 2 write.
1192
1193*/
1194int __myfs_write_implem(void *fsptr, size_t fssize, int *errnoptr,
1195 const char *path, const char *buf, size_t size, off_t offset) {
1196 /* STUB */
1197 return -1;
1198}
1199
1200/* Implements an emulation of the utimensat system call on the filesystem
1201 of size fssize pointed to by fsptr.
1202
1203 The call changes the access and modification times of the file
1204 or directory indicated by path to the values in ts.
1205
1206 On success, 0 is returned.
1207
1208 On failure, -1 is returned and *errnoptr is set appropriately.
1209
1210 The error codes are documented in man 2 utimensat.
1211
1212*/
1213int __myfs_utimens_implem(void *fsptr, size_t fssize, int *errnoptr,
1214 const char *path, const struct timespec ts[2]) {
1215 /* STUB */
1216 return -1;
1217}
1218
1219/* Implements an emulation of the statfs system call on the filesystem
1220 of size fssize pointed to by fsptr.
1221
1222 The call gets information of the filesystem usage and puts in
1223 into stbuf.
1224
1225 On success, 0 is returned.
1226
1227 On failure, -1 is returned and *errnoptr is set appropriately.
1228
1229 The error codes are documented in man 2 statfs.
1230
1231 Essentially, only the following fields of struct statvfs need to be
1232 supported:
1233
1234 f_bsize fill with what you call a block (typically 1024 bytes)
1235 f_blocks fill with the total number of blocks in the filesystem
1236 f_bfree fill with the free number of blocks in the filesystem
1237 f_bavail fill with same value as f_bfree
1238 f_namemax fill with your maximum file/directory name, if your
1239 filesystem has such a maximum
1240
1241*/
1242int __myfs_statfs_implem(void *fsptr, size_t fssize, int *errnoptr,
1243 struct statvfs* stbuf) {
1244 /* STUB */
1245 return -1;
1246}
1247