code: mafs

ref: b5d191e8cfa4fac05a02ea309df2541a2652ff23
dir: /extents.c/

View raw version
#include <u.h>
#include <libc.h>
#include "dat.h"
#include "fns.h"
#include "extents.h"

/*
 * Extents are used to manage memory space and disk space. The space is
 * is split into units of the same size.
 *
 * All space is split into a sequence of units. Each such sequence of units
 * is called an Extent. The data structure Extents is used to contain this
 * information. Space is added to the Extents using bfree() and allocated
 * using balloc(). When freed, adjacent extents are coalesced to create a
 * large extent, if they are continuous.
 */

void	showextent(int fd, char *pre, Extent *e);

s64
belongs(Extent *e, u64 start, u64 len)
{
	if(e == nil)
		sysfatal("belongs: e == nil");
	if(start+len == e->start || start == e->start+e->len)
		return 0;
	if(start >= e->start && start <= e->start+e->len)
		panic("belongs: inconsistent"
				" e->start %llud e->len %llud"
				" start %llud len %llud\n",
				e->start, e->len, start, len);
	return start+len-e->start;
}

Extent *
searchlrus(Extents *es, u64 blkno, u64 len, s64 *closest)
{
	Extent *e, *eclosest;
	s64 howclose;

	if(es->lru == nil)
		panic("searchlrus: should not happen");;

	eclosest = e = es->lru;
	*closest = belongs(e, blkno, len);
	if(closest == 0)
		return es->lru;
	for(e = e->next; e != es->lru; e = e->next){
		howclose = belongs(e, blkno, len);
		if(abs(howclose) < abs(*closest)){
			eclosest = e;
			*closest = howclose;
		}
	}
	return eclosest;
}

void
removefromlrus(Extents *es, Extent *e)
{
	Extent *z, *a;

	if(e == nil || es == nil)
		return;

	/* only entry in the lru linked list */
	if(e->prev == e->next){
		e->prev = e->next = es->lru = nil;
		es->nlru = 0;
		return;
	}

	/* z e a => z a */
	z = e->prev;
	a = e->next;

	z->next = a;
	a->prev = z;
	es->nlru--;

	if(es->lru == e)
		es->lru = a;
}

void
intolrus(Extents *es, Extent *e)
{
	Extent *y, *z;

	if(e == nil || es == nil)
		return;

	if(e->prev != nil)
		removefromlrus(es, e);

	if(es->lru == nil){
		es->lru = e->prev = e->next = e;
	}else if(es->nlru >= Nlru){
		/*
			y z lru
				to
			y e lru
			then make e the lru
		 */
		z = es->lru->prev;
		y = z->prev;
		z->prev = z->next = nil;

		e->prev = y;
		y->next = e;

		e->next = es->lru;
		es->lru->prev = e;
	}else{
		/*
			z lru
				to
			z e lru
			then make e the lru
		 */
		z = es->lru->prev;
		z->next = e;
		e->prev = z;
		e->next = es->lru;
		es->lru->prev = e;
		es->nlru++;
	}
	es->lru = e;
}

Extent *
lowest(Extents *es)
{
	Extent *e;

	if(es == nil || es->lru == nil || es->head == nil)
		return nil;
	for(e = es->head; e!= nil && e->low != nil; e=e->low)
		;
	return e;
}

Extent *
highest(Extents *es)
{
	Extent *e;

	if(es == nil || es->lru == nil)
		return nil;
	for(e = es->lru; e!=nil && e->high != nil; e=e->high)
		;
	return e;
}

Extent *
addextent(Extents *es, Extent *e, u64 start, u64 len)
{
	Extent *c;

	c = emalloc(sizeof(Extent));
	c->start = start;
	c->len = len;
	es->n++;
	if(chatty9p > 7)
		print("	+%llud %llud %llud\n", start, start+len-1, len);

	if(start < e->start){
		/* e->low e =>
			e->low c e
		  */
		if(e->low == nil)
			es->head = c;
		else
			e->low->high = c;
		c->low = e->low;
		e->low = c;
		c->high = e;
		intolrus(es, c);
		return c;
	}
	if(start > e->start){
		/* e e->high =>
			e c e->high
		  */
		if(e->high != nil)
			e->high->low = c;
		c->high = e->high;
		e->high = c;
		c->low = e;
		intolrus(es, c);
		return c;
	}
	print("addextent: should not be here e->start"
			" %llud .. %llud start %llud len %llud\n",
			e->start, e->start+e->len-1, start, len);
	abort();
	return nil;
}

/*
	in d e f g
		e = e+f
	becomes d e g
 */
Extent *
mergenext(Extents *es, Extent *e)
{
	Extent *f, *g;

	if(e == nil)
		return e;

	/* at the highest extent */
	if(e->high == nil)
		return e;
	if(e->start + e->len == e->high->start){
		f = e->high;
		if(f != nil)
			g = f->high;
		else
			g = nil;
		/* skipping f */
		e->len += f->len;
		if(g != nil)
			g->low = e;
		e->high = g;

		removefromlrus(es, f);
		free(f);
		es->n--;
		intolrus(es, e);
		return e;
	}
	return e;
}

/*
	in c d e f
		d = d+e
	becomes c d f
 */
Extent *
mergeprevious(Extents *es, Extent *e)
{
	Extent *d, *f;

	if(e == nil)
		return e;

	/* at the lowest extent */
	if(e->low == nil)
		return e;
	if(e->low->start+e->low->len == e->start){
		d = e->low;
		f = e->high;
		/* skipping e */
		if(d != nil){
			d->len += e->len;
			d->high = f;
		}
		if(f != nil)
			f->low = d;

		removefromlrus(es, e);
		free(e);
		es->n--;
		intolrus(es, d);
		return d;
	}
	return e;
}

Extent *
increment(Extents *es, Extent *e, u64 start, u64 len)
{
	if(e == nil)
		return e;
	intolrus(es, e);
	if(start+len == e->start){
		e->start = start;
		e->len += len;
		return mergeprevious(es, e);
	}
	if(start == e->start+e->len){
		e->len += len;
		return mergenext(es, e);
	}
	print("increment: should not be here"
		" e->start %llud .. %llud start %llud len %llud\n",
		e->start, e->start+e->len-1, start, len);
	abort();
	return e;
}

/*
print("between e->prev %llud .. %llud and e %llud .. %llud\n",
	 e->prev->start, e->prev->start+e->prev->n-1,
	 e->start, e->start+e->len-1);
 */
Extent *
doadd(Extents *es, u64 start, u64 len)
{
	s64 dir;
	Extent *e, *eprev;

	if(es == nil)
		panic("add es == nil");
	if(es->lru == nil){
		e = emalloc(sizeof(Extent));
		e->low = e->high = nil;
		e->start = start;
		e->len = len;
		es->lru = es->head = e->prev = e->next = e;
		es->n = 1;
		return e;
	}

	/* using the previously used extent */
	eprev = e = searchlrus(es, start, len, &dir);
	if(e == nil)
		panic("doadd: e == nil");
	if(chatty9p > 7){
		print(" 	belongs(e %llud %llud %llud %p %p start %llud %llud %llud) %lld\n",
				 e->start, e->start+e->len-1, e->len, e->low, e->high,
				 start, start+len-1, len, dir);
	}
	if(dir < 0){
		while((dir = belongs(e, start, len)) < 0){
			eprev = e;
			e = e->low;
			if(e == nil)
				break;
		}
		if(chatty9p > 7){
			print(" 	belongs(e %llud %llud %llud %p %p start %llud %llud %llud) %lld\n",
					 e->start, e->start+e->len-1, e->len, e->low, e->high,
					 start, start+len-1, len, dir);
		}
		/* e->low e eprev */
		if(dir == 0)
			return increment(es, e, start, len);
		if(e == nil)
			/* at the lowest extent, add below or above */
			return addextent(es, eprev, start, len);

		/* dir(e) > 0, hence, e < start < eprev */
		return addextent(es, eprev, start, len);
	}else if(dir > 0){
		while((dir = belongs(e, start, len)) > 0){
			eprev = e;
			e = e->high;
			if(e == nil)
				break;
		}
		if(chatty9p > 7){
			print(" 	belongs(e %llud %llud %llud start %llud %llud %llud) %lld\n",
				 e->start, e->start+e->len-1, e->len, start, start+len-1, len, dir);
		}
		/* eprev e e->high */
		if(dir == 0)
			return increment(es, e, start, len);
		if(e == nil)
			/* at the highest extent, add below or above */
			return addextent(es, eprev, start, len);

		/* dir(e) < 0, hence, eprev < start < e */
		return addextent(es, eprev, start, len);
	}

	/* dir == 0 */
	return increment(es, e, start, len);
}

Extent *
add(Extents *es, u64 start, u64 len)
{
	Extent *e;

	if(chatty9p > 7){
		showextents(2, "		before\n", es);
		fprint(2, " +%llud %llud\n", start, len);
	}
	e = doadd(es, start, len);
	es->lru = e;
	if(chatty9p > 7)
		showextents(2, "		after\n", es);
	return e;
}

static u64
pluck(Extents *es, Extent *e)
{
	Extent *dlow, *fhigh;
	u64 start;

	if(es == nil || e == nil || es->lru == nil)
		panic("pluck(): should not happen");

	/* if e is the only entry in es */
	if(e->low == nil && e->high == nil){
		es->head = nil;
		es->n = 0;
		start = e->start;
		removefromlrus(es, e);
		free(e);
		return start;
	}

	/* there are atleast 2 elements in the list */
	/* d e f => d f */
	dlow = e->low;
	fhigh = e->high;
	removefromlrus(es, e);

	/* d e nil => d nil */
	if(fhigh == nil){
		dlow->high = nil;
		intolrus(es, dlow);
		es->n--;
	}

	/* nil e f => nil f */
	if(dlow == nil){
		fhigh->low = nil;
		es->head = fhigh;
		intolrus(es, fhigh);
		es->n--;
	}

	if(dlow != nil && fhigh != nil){
		dlow->high = fhigh;
		fhigh->low = dlow;
		intolrus(es, fhigh);
		es->n--;
	}
	start = e->start;
	free(e);
	return start;
}

u64
slice(Extents *es, Extent *e, u64 len)
{
	u64 oldstart, oldlen;

	if(es == nil || e == nil || es->lru == nil || len == 0 || e->len <= len)
		panic("pluck(): should not happen");
	oldlen = e->len;
	oldstart = pluck(es, e);
	add(es, oldstart+len, oldlen - len);
	return oldstart;
}

/* allocate n blocks and return that block number */
u64
balloc(Extents *es, u64 n)
{
	Extent *e;
	u64 start;
	// char msg[64];

	if(es == nil)
		panic("balloc: es == nil");
	start = 0;
	qlock(&es->lck);
	if(es->n == 0)
		rsleep(&es->isempty);
/*	if(chatty9p > 7){
		snprint(msg, 64, "balloc() %llud blocks:\n", n);
		showextents(2, msg, es);
	}*/

	for(e = lowest(es); e != nil && e->len < n; e = e->high)
		;
	if(e == nil){
		// snprint(msg, 64, "balloc() %llud blocks:\n", n);
		// showextents(fd, msg, es);
		panic("balloc: out of free blocks");
	}
	else if(e->len == n)
		start = pluck(es, e);
	else /* found something bigger */
		start = slice(es, e, n);

	qunlock(&es->lck);
	return start;
}

/* reallocate n blocks to nnew blocks and return that block number
   It is upto the caller to copy the contents and bfree() the old
   block number if the returned block number <> old block number.
   Not providing brealloc() as we would need access to the contents
   to copy stuff over.
 */

/* free n blocks allocated at block number */
void
bfree(Extents *es, u64 start, u64 len)
{
	if(es == nil)
		panic("bfree: es == nil");
	qlock(&es->lck);
	add(es, start, len);
	if(es->n == 1)
		rwakeup(&es->isempty);
	qunlock(&es->lck);
}

/* count the total number of free blocks */
u64
nfrees(Extents *es)
{
	u64 n = 0;
	Extent *e;

	if(es == nil)
		panic("nfrees: es == nil");
	qlock(&es->lck);
	for(e = lowest(es); e != nil; e = e->high){
		n += e->len;
	}
	qunlock(&es->lck);
	return n;
}

/* string length when the extents are written as a string */
s32
sizeofextents(Extents *es)
{
	u64 n, used;
	s8 tmp[128];
	Extent *e;

	qlock(&es->lck);
	used = 0;
	for(e = lowest(es); e != nil; e = e->high){
		n = snprint(tmp, 128, "%llud %llud %llud\n",
						e->start, e->start+e->len-1, e->len);
		if(n == 128)
			panic("saveextents(): increase tmp size");
		used += n;
	}
	// keep it locked?
	qunlock(&es->lck);
	return used;
}
/* write to *buf return the length written */
s32
saveextents(Extents *es, s8 *buf, u32 nbuf)
{
	u64 n, used;
	s8 tmp[128];
	Extent *e;
	s32 ret;

	qlock(&es->lck);
	used = 0;
	for(e = lowest(es); e != nil; e = e->high){
		n = snprint(tmp, 128, "%llud %llud %llud\n",
						e->start, e->start+e->len-1, e->len);
		if(n == 128)
			panic("saveextents(): increase tmp size");
		if(used+n > nbuf){
			ret = -1;	/* increase buf size */
			goto end;
		}
		snprint(buf+used, nbuf-used, "%s", tmp);
		used += n;
	}
	ret = used;
	// keep it locked?
end:
	qunlock(&es->lck);
	return ret;
}

/* load the extents from buf of length nbuf */
/* make this be called multiple times to add more extents - not needed now */
/* assumes that the input is in ascending order of block numbers */
s32
loadextents(Extents *es, s8 *buf, u32 nbuf)
{
	s8 *p, *ep;
	u64 start, end, nblocks;

	p = buf;
	if(es->lru != nil || es->n != 0){
		panic("extents already loaded.\n"
			"	TODO make loadextents() be called multiple times\n");
	}
	while(*p != 0 && p-buf < nbuf){
		start = strtoull(p, &ep, 10);
		if(p == ep)
			panic("could not read");

		p = ep;
		p += 1; /* skip over the space */
		end = strtoull(p, &ep, 10);
		if(p == ep)
			panic("could not read");

		p = ep;
		p += 1; /* skip over the space */
		nblocks = strtoull(p, &ep, 10);
		if(p == ep)
			panic("could not read");
		if(end-start+1 != nblocks)
			panic("loadextents does not match up: start %llud end %llud nblocks %llud",
					start, end, nblocks);

		p = ep;
		p++; /* to skip over the new line */
		bfree(es, start, nblocks);
	}
	return es->n;
}

void
showextent(int fd, char *pre, Extent *e)
{
	fprint(fd, "%s	low %8#p	e %8#p %llud %llud	high %8#p",
			pre, e->low, e, e->start, e->len, e->high);
}

void
showextents(int fd, char *msg, Extents *es)
{
	Extent *e;

	fprint(fd, "%s", msg);
	for(e = lowest(es); e != nil; e = e->high){
		fprint(fd, "%llud %llud %llud", e->start, e->start+e->len-1, e->len);
//		showextent(fd, "	", e);
		fprint(fd, "\n");
	}
}

void
showblocknos(int fd, Extents *es)
{
	Extent *e;
	u64 i;

	for(e = lowest(es); e != nil; e = e->high)
		for(i = e->start; i<e->start+e->len; i++)
			fprint(fd, "%llud\n", i);
}

void *
emalloc(u32 sz)
{
	void *v;

	if((v = mallocz(sz, 1)) == nil)
		sysfatal("emalloc: %r");

	setmalloctag(v, getcallerpc(&sz));
	return v;
}

s8 *
estrdup(s8 *s)
{
	s8 *p;

	p = strdup(s);
	if(p == nil)
		sysfatal("estrdup: %r");
	setmalloctag(p, getcallerpc(&s));
	return p;
}

s8
find(Extents *es, u64 bno)
{
	Extent *e;

	if(es == nil || es->lru == nil)
		return 0;
	for(e = lowest(es); e != nil; e=e->high){
		if(e->start == bno)
			return 1;
		if(e->start < bno && bno < e->start+e->len)
			return 1;
	}
	return 0;
}

void
initextents(Extents *es)
{
	es->isempty.l = &es->lck;
}

/* obsolete */
Extent *
doadd_recursive(Extents *es, u64 start, u64 len)
{
	s64 dir;
	Extent *e;

	if(es == nil)
		panic("add es == nil");
	if(es->lru == nil){
		e = emalloc(sizeof(Extent));
		e->low = e->high = nil;
		e->start = start;
		e->len = len;
		es->lru = es->head = e;
		es->n = 1;
		return e;
	}

	/* using the previously used extent */
	e = es->lru;
	dir = belongs(es->lru, start, len);
	if(chatty9p > 7){
		print(" 	belongs(e %llud %llud start %llud .. %llud) %lld\n",
			 e->start, e->start+e->len-1, start, start+len-1, dir);
	}
	if(dir == 0)
		return increment(es, e, start, len);
	else if(dir < 0){
		if(e->low == nil)
			/* at the lowest extent, add a prev */
			return addextent(es, e, start, len);
		else if(e->low->start+e->low->len == start)
			/* belongs in the ->low extent */
			return increment(es, e->low, start, len);
		else if(e->low->start+e->low->len < start)
			/* between the e->low and e */
			return addextent(es, e->low, start, len);
		else{
			/* search from e->low */
			es->lru = e->low;
			return doadd(es, start, len);
		}
	}else if(dir > 0){
		if(e->high == nil)
			/* at the highest extent, add the next */
			return addextent(es, e, start, len);
		else if(start+len == e->high->start)
			/* belongs in the ->high extent */
			return increment(es, e->high, start, len);
		else if(start+len < e->high->start)
			/* between e and e->high */
			return addextent(es, e, start, len);
		else{
			es->lru = e->high;
			/* search from e->high */
			return doadd(es, start, len);
		}
	}
	/* dir == 0 */
	sysfatal("add: should not be here"
		 " e->start %llud .. %llud start %llud len %llud\n",
		  e->start, e->start+e->len-1, start, len);
	return e;
}