graphviz generator

graphviz.c

#include <stdio.h>

#include "minifile.h"
#include "minifile_private.h"
#include "minithread.h"
#include "miniheader.h"

/*
node [shape = record,height=.1];
nodei - ith block
Fragmentation structure
Superblock
label = "Magic|size|<root>|num free| num data"
Inode
label = "type|size|<freshptr0>|<freshptr1>|...|<freshptrINODE_SLOTS>|<indirect>"
Datablock_Dir_Dir
label = "type|<freshptr0|...|<freshptrDIRECT_SLOTS>"
Datablock_File_DIR
label = "type|<freshptr0|...|<freshptr(DISK_BLOCK_SIZE - sizeof(struct node_header))>"
Datablock_Indirect
label = "type|...|<freshptrINDIRECT_SLOTS|<indirect>"
*/

FILE* out;
#define myprintf(...) fprintf(out,  __VA_ARGS__);

void edge(int a, int b){
	myprintf("\t\"node%d\":to%d -> \"node%d\";\n", a, b, b);
}

void lto(int to){
	myprintf(" <to%d> %d |", to, to);
}

void lto2(int to, char* name){
	myprintf(" <to%d> %s(%d) |", to, name, to);
}

char* superblockfmt = "\tnode%d [label=\"S%d |%d | %d | <to%d> %d | inodes: %d | data: %d\"];\n\t\"node%d\":to%d -> \"node%d\";\n";
char* inodefmt_prolog = "\tnode%d [label=\"I%d | t%d | s%d |";
char* inodefmt_epilog = " <to%d>ind%d\"];\n";
char* dnodefmt_prolog = "\tnode%d [label=\"D%d | t%d |";
char* dnodefmt_epilog = "\"];\n";

int graphviz(arg_t arg){
	// check out superblock
	superblock_t superblock = NEW_SUPERBLOCK();
	int magic, size, ni, nd, to, i, j;

	myprintf("digraph G {\n\tnode [shape = record,height=.1];\n");
	read_from_disk(0, (char*)superblock);
	magic = uu(superblock->magic);
	size = uu(superblock->size);
	ni = uu(superblock->num_free_inodes);
	nd = uu(superblock->num_free_datablocks);
	to = uu(superblock->root_inode);
	myprintf(superblockfmt, 0, 0, magic, size, to, to, ni, nd, 0, to, to);

	// process inodes first
	for (i=1;i<FIRST_DATA; i++){
		inode_t inode = NEW_INODE();
		int type, size, *ptrs = NEW_PTRS(), indirect;
		read_from_disk(i, (char*)inode);
		type = uu(inode->type);
		size = uu(inode->dir.size);
		unpack_arr((unsigned int*)ptrs, inode->dir.data, INODE_SLOTS);
		indirect = uu(inode->dir.indirect);
		// if free, don't bother
		if (type == I_FREE){
			free(inode);
			free(ptrs);
			continue;
		}
		myprintf(inodefmt_prolog, i, i, type, size);
		for (j=0;j<INODE_SLOTS;j++){
			if (!ptrs[j])
				continue;
			lto(ptrs[j]);
		}
		myprintf(inodefmt_epilog, indirect, indirect);
		for (j=0;j<INODE_SLOTS;j++){
			if (!ptrs[j])
				continue;
			edge(i,ptrs[j]);
		}
		if (indirect){
			edge(i, indirect);
		}
		free(inode);
		free(ptrs);
	}

	// next, do the dnodes
	/*
	Datablock_Dir_Dir
label = "type|<freshptr0|...|<freshptrDIRECT_SLOTS>"
Datablock_File_DIR
label = "type|<freshptr0|...|<freshptr(DISK_BLOCK_SIZE - sizeof(struct node_header))>"
Datablock_Indirect
label = "type|...|<freshptrINDIRECT_SLOTS|<indirect>"
	*/
	for (i=FIRST_DATA; i < disk_size; i++){
		datablock_t d = NEW_DNODE();
		int type, *ptrs = (int*)malloc(sizeof(int)*(INDIRECT_SLOTS+1)), indirect;
		//myprintf("%d ",i);
		j = read_from_disk(i, (char*)d);
		
		type = uu(d->type);
		//myprintf("%x %x\n",ptrs, d->direct_file.data);
		unpack_arr((unsigned int*)ptrs, d->indirect.direct_ptrs, INDIRECT_SLOTS);
		indirect = uu(d->indirect.indirect);
		if (type == D_FREE){
			free(d);
			free(ptrs);
			continue;
		}
		myprintf(dnodefmt_prolog, i, i, type);
		switch(type){
		case D_DIR_DIRECT:
			for (j=0;j<DIRECT_SLOTS;j++){
				if (!uu(d->direct_dir.files[j].ptr))
					continue;
				lto2(uu(d->direct_dir.files[j].ptr), d->direct_dir.files[j].name);
			}
			break;
		case D_FILE_INDIRECT:
		case D_DIR_INDIRECT:
			for (j=0;j<INDIRECT_SLOTS;j++){
				if (!ptrs[j])
					continue;
				lto(ptrs[j]);
			}
			if (indirect)
				lto(indirect);
			break;
		case D_FILE_DIRECT:
			unpack_arr((unsigned int*)ptrs, d->direct_file.data, INDIRECT_SLOTS+1);
			for (j=0;j<=INDIRECT_SLOTS;j++){
				if (!ptrs[j])
					continue;
				myprintf("%0.8x |",ptrs[j]);
				break;
			}
		}
		myprintf(dnodefmt_epilog);

		
		switch(type){
		case D_DIR_DIRECT:
			for (j=0;j<DIRECT_SLOTS;j++){
				if (!uu(d->direct_dir.files[j].ptr))
					continue;
				edge(i,uu(d->direct_dir.files[j].ptr));
			}
			break;
		case D_FILE_INDIRECT:
		case D_DIR_INDIRECT:
			for (j=0;j<INDIRECT_SLOTS;j++){
				if (!ptrs[j])
					continue;
				edge(i,ptrs[j]);
			}
			if (indirect)
				lto(indirect);
			break;
		//case D_FILE_DIRECT:
			//unpack_arr((unsigned int*)ptrs, d->direct_file.data, INDIRECT_SLOTS+1);
			//for (j=0;j<=INDIRECT_SLOTS;j++){
				//if (!ptrs[j])
				//	continue;
				//edge(i,ptrs[j]);
			//}
		}

		free(d);
		free(ptrs);
	}

	myprintf("}");
	fflush(out);
}

int main(int argc, char* argv[]){
	use_existing_disk = 1;
	disk_name = "MINIFILESYSTEM";
	out = stdout;
	if (argc > 1){
		FILE* out_tmp = fopen(argv[1], "w");
		if (out_tmp)
			out = out_tmp;
	}

	minithread_system_initialize(graphviz, NULL);

	return 0;
}

minithread_private.h

#ifndef __MINIFILE_PRIVATE_H__
#define __MINIFILE_PRIVATE_H__

#include "disk.h"
#include "synch.h"
#include "queue.h"
#include "minithread.h"

extern disk_t disk;

#define INODE_SLOTS 500
#define MAGIC 0xcafe

#define INDIRECT_SLOTS_ ((DISK_BLOCK_SIZE - sizeof(struct node_header))/4 - 1)
#define INDIRECT_SLOTS__(n) ((n < INDIRECT_SLOTS_)?n:INDIRECT_SLOTS_)
#define INDIRECT_SLOTS (INDIRECT_SLOTS__(INDIRECT_SLOTS_))
#define DIRECT_SLOTS_ ((DISK_BLOCK_SIZE - sizeof(struct node_header))/sizeof(struct file_desc))
#define DIRECT_SLOTS__(n) ((n < DIRECT_SLOTS_) ? n : DIRECT_SLOTS_)
#define DIRECT_SLOTS (DIRECT_SLOTS__(DIRECT_SLOTS_))

#define FIRST_DATA (disk_size/10 + 1)

#define IS_INODE(block) ((block) < FIRST_DATA && (block) > 0)
#define IS_DNODE(block) ((block) < disk_size && (block) >= FIRST_DATA)

#define NEW_INODE() ((inode_t)malloc(sizeof(struct inode)))
#define NEW_DNODE() ((datablock_t)malloc(sizeof(struct datablock)))
#define NEW_SUPERBLOCK() ((superblock_t)malloc(sizeof(struct superblock)))
#define NEW_PTRS() ((int*)malloc(sizeof(int)*INODE_SLOTS))
#define gptrs(ptrs, inode) (unpack_arr((unsigned int*)ptrs, inode->file.data, INODE_SLOTS))

#define uu(x) unpack_unsigned_int(x)
#define pu(x,y) pack_unsigned_int(x,y)

enum {
	I_FILE, I_DIR, I_FREE
} inode_type;

enum {
	D_FILE_DIRECT, D_FILE_INDIRECT, D_DIR_DIRECT, D_DIR_INDIRECT, D_FREE
} data_type;

typedef struct superblock{
	union{
		struct {
			char magic[4];
			char root_inode[4];
			char size[4];
			// free inodes must be before 10% of all disk blocks
			char free_inode[4];
			// free blocks must start after 10% of all disk blocks
			char free_datablock[4];

			char num_free_inodes[4];
			char num_free_datablocks[4];
		};
		char padding[DISK_BLOCK_SIZE];
	};
} *superblock_t;

struct node_header{
	char type[4];
	//char refs[4];
};

typedef struct inode{
	union{
		struct {
			// either a file, directory, or free
			char type[4];
			//char refs[4];
			union {
				struct {
					char size[4];
					char data[INODE_SLOTS*4];
					char indirect[4];
				} file;
				struct {
					char size[4];
					char data[INODE_SLOTS*4];
					char indirect[4];
				} dir;
				struct {
					// free nodes form a linked list
					char next[4];
				} free;
			};
		};
		char padding[DISK_BLOCK_SIZE];
	};
} *inode_t;

typedef struct file_desc{
	char name[256];
	char ptr[4];
} *file_desc_t;

#define DATASIZE (DISK_BLOCK_SIZE - sizeof(struct node_header))

typedef struct datablock{
	union{
		struct{
			char type[4];
			//char refs[4];
			union{
				struct {
					struct file_desc files[DIRECT_SLOTS];
				} direct_dir;
				struct {
					char data [DATASIZE];
				} direct_file;
				struct {
					char direct_ptrs[INDIRECT_SLOTS*4];
					char indirect[4];
				} indirect;
				struct {
					char next[4];
				} free;
			};
		};
		char padding[DISK_BLOCK_SIZE];
	};
} *datablock_t;

// helper functions to read/write from disk as blocking io
int write_to_disk(int block, char *data);
int read_from_disk(int block, char *data_out);

int minifile_initialize();
void minifile_interrupt_handler(disk_interrupt_arg_t *arg);

char* minithread_directory();
void minithread_set_directory(char*);

typedef struct disk_response{
	int block;
	semaphore_t lock;
	semaphore_t response_available;
	disk_interrupt_arg_t *response;
} *disk_response_t;

extern disk_response_t *responses;
extern semaphore_t *node_locks;
extern semaphore_t metadata_lock;

extern unsigned int *thread_count;
extern semaphore_t* thread_count_locks;

extern queue_t cache_queue;
extern void** minifile_cache;
extern semaphore_t* cache_locks;
extern semaphore_t cache_queue_lock;

char** path_split(char* path);
void free_split(char** split);
char** flatten_splits(int n, ...);
char* join_split(char** split);
char** reduce_split(char** split);

int find_inode_of_split(char** split);
queue_t list_files_of_dir(int block);

int get_inode_of_dir(char* path);
inode_t get_free_inode(int* blockp);
datablock_t get_free_dnode(int* blockp);
void push_free_dnode(int nextblock);
void push_free_inode(int nextblock);

void set_file_desc(file_desc_t desc, char* name, int block);

int set_free_ptr_in_inode(int block, int new_size, int (*f)(int, arg_t), arg_t arg1, void(*format)(datablock_t, arg_t), arg_t arg2);

int cache_set(int block, char* buf);
int cache_get(int block, char* buf);

int get_inode_of_dir_extra(char* path, int* bptr, int* iptr);
int find_inode_of_split_extra(char** split, int* bptr, int* iptr);
char** get_split(char* pwd, char* file, char*** pdotdot, char* ext);
void cleanup_file_inode(int block);

enum{
	R, W, A, RW, WP, AP
}filemode;

int get_filemode(char*);
int get_from_cursor(int cursor, int* indirects);
int write_data_cursor(int block, int cursor, int len, char* data, int* leftover);

void cleanup_dir_inode(int block);
int read_data_cursor(int block, int cursor, int len, char* data, int* pleftover);
int find_inode_of_split_extra2(char** split, int* bptr, int* iptr);
int find_inode_of_split2(char** split);
#endif