SFS Algos

[instance]

Hey,
I'm trying to implement the SFS system. Could some of you point me in direction of some implementations of SFS, since the algo's section is still not there in the draft.

um.... and besides the point a bit, if there are no algo's, Here are a few functions I came up with for SFS:

Code: Select all

#include "../includes/basedef.h"
#include "../includes/hdd.h"
#include "../includes/sfs.h"
extern void printNum(uint32 num);
extern void puts(char* s);
uint32 readInt(struct hddSector* s,int i);
uint32 fs_sizeRB,fs_sizeDA,fs_sizeIA,fs_sizeTot;
void mountDisk(){
	struct hddSector mbr;
	read28(0,1,&mbr);
	
	if(mbr.data[0x1AC]==0x53 && mbr.data[0x1AD]==0x46 && mbr.data[0x1AE]==0x53){
		fs_sizeDA=readInt(&mbr,0x19C);
		fs_sizeIA=readInt(&mbr,0x1A4);
		fs_sizeTot=readInt(&mbr,0x1B0);
		fs_sizeRB=readInt(&mbr,0x1B8);
	}
	else{
		return;
	}
}
int streql(char* s1,char* s2){
	int i;
	for(i=0;s1[i];i++);
	int s1len=i;
	for(i=0;s2[i];i++);
	int s2len=i;
	if(s1len!=s2len) return 0;
	for(i=0;i<s1len;i++){
		if(s1[i]!=s2[i]) return 0;
	}
	return 1;
}
int dirExists(char *s){
	//Check if directory exists
	struct hddSector sect;
	uint32 lbaIndex=fs_sizeTot-fs_sizeIA/512;
	uint32 skipRecords=0;
	if(fs_sizeIA%512) {
		lbaIndex--;
		skipRecords=8-(fs_sizeIA%512)/64;
	}
	uint32 curSector=0;
	int foundDir=0;
	while((lbaIndex+curSector)<fs_sizeTot){
		read28(lbaIndex+curSector,1,&sect);
		//Parse
		char dirname[200]="";
		int i,j=0,conti=0;
		for(i=0;i<8;i++){
			if(curSector==0&&skipRecords){ skipRecords--; continue; }
			if(sect.data[i*64]==0x11){
				for(j=0;j<54;j++){
					dirname[j]=sect.data[j+0x0A+i*64];
					if(dirname[j]==0) break;
				}
				conti=sect.data[1+i*64];
				if(!conti){
					//Check if dir name is correct
					if(streql(s,dirname)){
						foundDir=1;
					}
				}
			}
			else{
				if(conti&&(sect.data[i*64]>=0x20)&&(sect.data[i*64]<=0xFF)){
					//This is a continuation sector
					int k;
					for(k=0;k<64&&j<200;j++,k++){
						dirname[j]=sect.data[k+i*64];
						if(dirname[j]==0) break;
					}
					conti--;
					if(!conti){
						//Check if dir name is correct
						if(streql(s,dirname)){
							foundDir=1;
						}
					}
				}
			}
			if(foundDir) break;
		}
		if(foundDir) break;
		curSector++;
	}
	if(foundDir){
		return 1;
	}
	else{
		return 0;
	}
}
int strFileInDirectory(char *filename,char *dirname){
	int i;
	for(i=0;filename[i];i++);
	i--;
	for(;(filename[i]!='/')&&(i>=0);i--);
	if(i>0) i--;
	int dirlen;
	for(dirlen=0;dirname[dirlen];dirlen++);
	dirlen--;
	if(dirlen!=i) return 0;
	for(;i>=0;i--){
		if(filename[i]!=dirname[i]) return 0;
	}
	return 1;
}
int openDir(char* dirname,struct dirhandle* res){
	if(!dirExists(dirname)) return 0;
	int i;
	for(i=0;dirname[i];i++) res->dirname[i]=dirname[i];
	uint32 lbaIndex=fs_sizeTot-fs_sizeIA/512;
	uint32 skipRecords=0;
	if(fs_sizeIA%512) {
		lbaIndex--;
		skipRecords=8-(fs_sizeIA%512)/64;
	}
	res->curlba=lbaIndex;
	res->record=skipRecords;
}
int getNextDirEntry(char* buf,struct dirhandle* res){
	uint32 lbaIndex=res->curlba;
	int i=res->record;   // Pointing to the record from where to start reading
	int conti=0;
	struct hddSector sect;
	while((lbaIndex)<fs_sizeTot){
		read28(lbaIndex,1,&sect);
		//Parse
		char filename[300];
		int j=0,conti=0;
		for(;i<8;i++){
			if(sect.data[i*64]==0x12){   //Regular file
				for(j=0;j<30;j++){
					filename[j]=sect.data[j+0x22+i*64];
					if(filename[j]==0) break;
				}
				conti=sect.data[1+i*64];
				if(!conti){
					//Check if file is in directory
					if(strFileInDirectory(filename,res->dirname)){
						//Copy
						for(j=0;filename[j];j++) buf[j]=filename[j];
						if(i==7){ res->curlba=lbaIndex+1; res->record=0; }
						else{ res->curlba=lbaIndex; res->record++; }
						return 1;
					}
				}
			}
			else{
				if(conti&&(sect.data[i*64]>=0x20)&&(sect.data[i*64]<=0xFF)){
					//This is a continuation sector (for a file, cause conti is set only for files)
					int k;
					for(k=0;k<64&&j<300;j++,k++){
						filename[j]=sect.data[k+i*64];
						if(filename[j]==0) break;
					}
					conti--;
					if(!conti){
						if(strFileInDirectory(filename,res->dirname)){
							//Copy
							for(j=0;filename[j];j++) buf[j]=filename[j];
							if(i==7){ res->curlba=lbaIndex+1; res->record=0; }
							else{ res->curlba=lbaIndex; res->record++; }
							return 1;
						}
					}
				}
			}
		}
		i=0;
		lbaIndex++;
	}
	return 0; //Did not find any files
}
	
uint32 readInt(struct hddSector* s,int i){
	return MAKEDWORD(MAKEWORD(s->data[i+3],s->data[i+2]),MAKEWORD(s->data[i+1],s->data[i]));
}

Code: Select all

//Usage
        char filename[300];
	struct dirhandle s;
	openDir("sample",&s);
	while(getNextDirEntry(filename,&s)){
		puts("Got a filename: ");
		puts(filename);
		putch('\n');
	}

It definately aint the best way to do it, perhaps pretty much the worst , but it does work, as tested against a SFS created by combuster's vdisk tool.

[gmoney]

goto the osdev wiki page and search sfs and tweak you algos so newbs can use implement of sfs as a base

[Troy Martin]

I personally can't understand what you're saying. Are you telling (or asking) him to go to the wiki's SFS article and tweak his algos for his own use, or to add his algorithms to the SFS article? Because for the second, wiki membership is needed (IIRC you should PM a mod.)

[Combuster]

@Troy Martin: For the umpteenth time, you do not need mod intervention to access the wiki.

As for SFS itself - there a few approaches that you might use:

Finding a file: traverse the index in order.
Reading a file: trivial
Writing a file: initally, put the contents in memory, then append at once to the end of the data area and update the sfs header.
Deleting a file: remove the entry from the index. Move the data area pointer if the file is at the end of the disk

When there's not enough space in the unallocated area: defragment. Find the physical order of files, then move files to the front of the volume until there is a gap large enough to fit your object.

Things just get hideously complicated when dealing with damaged sectors

[Troy Martin]

@Troy Martin: For the umpteenth time, you do not need mod intervention to access the wiki.

I've heard people saying "if you need wiki access quickly, PM a mod" quite a few times. I guess I'll shut up now.

hideously complicated

I thought we were talking about SFS, not ext4

[Combuster]

hideously complicated

I thought we were talking about SFS, not ext4

So you have a simple solution for fitting the most possible data on a drive without fragmentation, which has a number of damaged (reserved) sectors, no?

[gmoney]

I personally can't understand what you're saying. Are you telling (or asking) him to go to the wiki's SFS article and tweak his algos for his own use, or to add his algorithms to the SFS article? Because for the second, wiki membership is needed (IIRC you should PM a mod.)

what i was telling him to do is tweak his algos then add it to an article. and wiki membership isn't needed if he host it on his svn repo or other means

[Troy Martin]

hideously complicated

I thought we were talking about SFS, not ext4

So you have a simple solution for fitting the most possible data on a drive without fragmentation, which has a number of damaged (reserved) sectors, no?

No, I'm just saying, ext4 appears to be fugly at a glance.

[pcmattman]

hideously complicated

No, I'm just saying, ext4 appears to be fugly at a glance.

We're talking about SFS, not ext4. If you want to say ext4 looks hideously complicated, this thread isn't the place.

And yes, it is hideously complicated to keep a disk unfragmented when you have to avoid sectors, because suddenly your files can't be contiguous. I can only think of a best-fit algorithm to stop fragmentation, but to know where that "best fit" is in relation to the dead sector involves a lot of housekeeping and could be quite slow. It also involves hoping there's a couple of small files to fit in the gap

[Troy Martin]

hideously complicated

No, I'm just saying, ext4 appears to be fugly at a glance.

Ahem. I believe there are two words: attemped humour.

[Candy]

hideously complicated

No, I'm just saying, ext4 appears to be fugly at a glance.

We're talking about SFS, not ext4. If you want to say ext4 looks hideously complicated, this thread isn't the place.

And yes, it is hideously complicated to keep a disk unfragmented when you have to avoid sectors, because suddenly your files can't be contiguous. I can only think of a best-fit algorithm to stop fragmentation, but to know where that "best fit" is in relation to the dead sector involves a lot of housekeeping and could be quite slow. It also involves hoping there's a couple of small files to fit in the gap

Simplest I can think of is to pretend it doesn't exist. Just keep a list of all the sector numbers and increment yours until you're past it - effectively, renumber to skip those.

Code: Select all

int getPhysicalIndexOf(int sectorLogicalIndex)
{
   int *skipIndices; // wherever your list of invalids is, 0-terminated
   while (*skipIndices && *skipIndices > sectorLogicalIndex)
      sectorLogicalIndex++;
   return sectorLogicalIndex;
}

Assuming skipIndices is a sorted 0-terminated list this works for the indirection.

Any comments?

[Combuster]

Assuming skipIndices is a sorted 0-terminated list this works for the indirection.

Any comments?

1: it means file are no longer guaranteed to be contiguous, which goes directly against the specs.
2: There's a bug in your code...

[pcmattman]

Simplest I can think of is to pretend it doesn't exist. Just keep a list of all the sector numbers and increment yours until you're past it - effectively, renumber to skip those.

I had the same thought; however in order to avoid fragmentation you need to avoid having a file that would otherwise use that sector in that space. That's why I said a best-fit algorithm could help - you could fit small files in the spaces between bigger files (which would have to be moved to the largest contiguous space where there won't be damaged sectors).

The theory is nice and simple, but in practice you may not have a small file to fit into a gap, or you may not have enough contiguous space for a big file.