20060303a

1 files changed, 293 insertions, 0 deletions

diff --git a/liblogfs/scan.c b/liblogfs/scan.c
new file mode 100644
index 00000000..5f4d9cf7
--- /dev/null
+++ b/liblogfs/scan.c
@@ -0,0 +1,293 @@
+#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 int
+dataorder(ulong p1, ulong p2)
+{
+	int o;
+	o = dataseqof(p1) - dataseqof(p2);
+	if(o != 0)
+		return o;
+	return copygenof(p1) - copygenof(p2);
+}
+
+static int
+logorder(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 void
+insert(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 void
+populate(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 int
+dataduplicate(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;
+}