#include "lib9.h"#include "logfs.h"#include "local.h"#include "fcall.h" typedef struct PathEnt {	ulong path;		long block;} PathEnt; typedef struct GenInfo {	long start;	long end;	int gaps;} GenInfo; static intdataorder(ulong p1, ulong p2){	int o;	o = dataseqof(p1) - dataseqof(p2);	if(o != 0)		return o;	return copygenof(p1) - copygenof(p2);} static intlogorder(ulong p1, ulong p2){	int o;	o = loggenof(p1) - loggenof(p2);	if(o != 0)		return o;	o = logseqof(p1) - logseqof(p2);	if(o != 0)		return o;	return copygenof(p1) - copygenof(p2);} static voidinsert(PathEnt *pathmap, long entries, ulong path, long block, int (*order)(ulong p1, ulong p2)){	long i;	for(i = 0; i < entries; i++)		if((*order)(path, pathmap[i].path) < 0)			break;	memmove(&pathmap[i + 1], &pathmap[i], (entries - i) * sizeof(PathEnt));	pathmap[i].path = path;	pathmap[i].block = block;} static voidpopulate(LogSegment *seg, int gen, long unsweptblockindex, long curblockindex, PathEnt *pathent){	long i;	seg->gen = gen;	seg->unsweptblockindex = unsweptblockindex;	seg->curblockindex = curblockindex;	for(i = unsweptblockindex; i <= curblockindex; i++) {//		print("populate %d: %d\n", i, pathent[i - unsweptblockindex].block);		seg->blockmap[i] = pathent->block;		pathent++;	}} static intdataduplicate(PathEnt *p1, PathEnt *p2){	return dataseqof(p2->path) == dataseqof(p1->path)		&& copygenof(p2->path) == copygensucc(copygenof(p1->path));} static char *eliminateduplicates(LogfsServer *server, char *name, PathEnt *map, long *entriesp){	long i;	long k = *entriesp;	for(i = 0; i < k;) {		PathEnt *prev = &map[i - 1];		PathEnt *this = &map[i];		if(i > 0 && dataduplicate(prev, this)) {			print("%s duplicate detected\n", name);			if(i + 1 < k && dataduplicate(this, &map[i + 1]))				return "three or more copies of same block";			/*			 * check that the copy generations are in order			 */			if(copygensucc(copygenof(this->path)) == copygenof(prev->path)) {				PathEnt m;				/*				 * previous entry is newer, so swap				 */				m = *this;				*this = *prev;				*prev = m;			}			else if(copygensucc(copygenof(prev->path)) != copygenof(this->path))				return "duplicate blocks but copy generations not sequential";			/* erase and format previous block */			logfsbootfettleblock(server->lb, prev->block, LogfsTnone, ~0, nil);			/*			 * remove entry from table			 */			memmove(prev, this, sizeof(PathEnt) * (k - i));			k--;			continue;		}		i++;	}	*entriesp = k;	return nil;} char *logfsscan(LogfsServer *server){	LogfsLowLevel *ll = server->ll;	long b;	long i;	long logfound = 0;	long datafound = 0;	PathEnt *logpathmap, *datapathmap;	GenInfo geninfo[1 << L2LogSweeps];	int gensfound, lastgenfound;	int g0, g1;	char *errmsg;//print("logfsscan %ld blocks\n", server->ll->blocks);	logpathmap = logfsrealloc(nil, sizeof(PathEnt) * server->ll->blocks);	datapathmap = logfsrealloc(nil, sizeof(PathEnt) * server->ll->blocks);	if(logpathmap == nil || datapathmap == nil)		return Enomem;	for(b = 0; b < ll->blocks; b++) {		short tag = (*ll->getblocktag)(ll, b);		ulong path = (*ll->getblockpath)(ll, b);//print("scan: %ld: %d %ld\n", b, tag, path);		switch(tag) {		case LogfsTlog:			insert(logpathmap, logfound++, path, b, logorder);			break;		case LogfsTdata:			insert(datapathmap, datafound++, path, b, dataorder);			break;		}	}	if(server->trace > 1) {		for(i = 0; i < logfound; i++)			print("log gen %lud seq %lud copygen %lud block %ld\n",				loggenof(logpathmap[i].path), logseqof(logpathmap[i].path), copygenof(datapathmap[i].path), logpathmap[i].block);		for(i = 0; i < datafound; i++)			print("data seq %lud copygen %lud block %ld\n",				dataseqof(datapathmap[i].path), copygenof(datapathmap[i].path), datapathmap[i].block);	}	/*	 * sort out data first	 */	errmsg = eliminateduplicates(server, "data", datapathmap, &datafound);	if(errmsg)		goto fail;	/*	 * data blocks guaranteed to be ordered	 */	if(datafound)		server->ndatablocks = dataseqof(datapathmap[datafound - 1].path) + 1;	else		server->ndatablocks = 0;	for(i = 0; i < server->ndatablocks; i++)		server->datablock[i].block = -1;	for(i = 0; i < datafound; i++) {		long j;		j = dataseqof(datapathmap[i].path);		server->datablock[j].path = datapathmap[i].path;		server->datablock[j].block = datapathmap[i].block;		/*		 * mark pages as free and dirty, which indicates they cannot be used	 	*/		server->datablock[j].dirty = server->datablock[j].free = logfsdatapagemask(1 << ll->l2pagesperblock, 0);	}	/*	 * find how many generations are present, and whether there are any gaps	 */	errmsg = eliminateduplicates(server, "log", logpathmap, &logfound);	if(errmsg)		goto fail;	gensfound = 0;	lastgenfound = -1;	for(i = 0; i < nelem(geninfo); i++)		geninfo[i].start = -1;	for(i = 0; i < logfound; i++) {		int gen;		gen = loggenof(logpathmap[i].path);		if(geninfo[gen].start < 0) {			if(lastgenfound >= 0)				geninfo[lastgenfound].end = i;			geninfo[gen].start = i;			lastgenfound = gen;			geninfo[gen].gaps = 0;			gensfound++;		}		else if(!geninfo[lastgenfound].gaps && logseqof(logpathmap[i - 1].path) + 1 != logseqof(logpathmap[i].path)) {			geninfo[lastgenfound].gaps = 1;			print("generation %d has gaps (%lud, %lud)\n", lastgenfound,				logseqof(logpathmap[i - 1].path), logseqof(logpathmap[i].path));		}	}	if(lastgenfound >= 0)		geninfo[lastgenfound].end = i;	if(server->trace > 1) {		for(i = 0; i < nelem(geninfo); i++)			print("geninfo: %ld: start %ld end %ld gaps %d\n", i, geninfo[i].start, geninfo[i].end, geninfo[i].gaps);	}	switch(gensfound) {	case 0:		/* active log - empty */		break;	case 1:		/*		 * one log, active		 */		for(g0 = 0; g0 < nelem(geninfo); g0++)			if(geninfo[g0].start >= 0)				break;		if(geninfo[g0].gaps || geninfo[g0].start != 0) {			errmsg = "missing log blocks";			goto fail;		}		populate(server->activelog, g0, 0, geninfo[g0].end - geninfo[g0].start - 1, logpathmap + geninfo[g0].start);		break;	case 2:		/*		 * two logs, active, swept		 */		g0 = -1;		for(g1 = 0; g1 < nelem(geninfo); g1++)			if(geninfo[g1].start >= 0) {				if(g0 < 0)					g0 = g1;				else 					break;			}		if(geninfo[g0].gaps || geninfo[g1].gaps) {			errmsg = "missing log blocks";			goto fail;		}		if(g0 == loggensucc(g1)) {			int tmp = g0;			g0 = g1;			g1 = tmp;		}		else if(g1 != loggensucc(g0)) {			errmsg = "nonsequential generations in log";			goto fail;		}		if(logseqof(logpathmap[geninfo[g1].start].path) != 0) {			errmsg = "swept log does not start at 0";			goto fail;		}		if(logseqof(logpathmap[geninfo[g0].start].path) == logseqof(logpathmap[geninfo[g1].end - 1].path)) {			/*			 * duplicate block			 * as the log never gets bigger, information from active[n] is either entirely in swept[n],			 * or split between swept[n-1] and swept[n]. we can safely remove swept[n]. this might			 * leave some duplication between swept[n - 1] and active[n], but this is always true			 * for a partially swept log			 */			logfsbootfettleblock(server->lb, logpathmap[geninfo[g1].end - 1].block, LogfsTnone, ~0, nil);			geninfo[g1].end--;		}		if(logseqof(logpathmap[geninfo[g0].start].path) < logseqof(logpathmap[geninfo[g1].end - 1].path)) {			errmsg = "active log overlaps end of swept log";			goto fail;		}		populate(server->activelog, g0, logseqof(logpathmap[geninfo[g0].start].path),			logseqof(logpathmap[geninfo[g0].end - 1].path), logpathmap + geninfo[g0].start);		if(server->sweptlog == nil) {			errmsg = logfslogsegmentnew(server, g1, &server->sweptlog);			if(errmsg)				goto fail;		}		populate(server->sweptlog, g1, logseqof(logpathmap[geninfo[g1].start].path),			logseqof(logpathmap[geninfo[g1].end - 1].path), logpathmap + geninfo[g1].start);		break;	default:			errmsg = "more than two generations in log";		goto fail;	}	goto ok;fail:	logfslogsegmentfree(&server->sweptlog);ok:	logfsfreemem(logpathmap);	logfsfreemem(datapathmap);	return errmsg;}