code: 9ferno

ref: 876f68cfab0905e1ab21be625fabd3c49a819075
dir: /os/port/memmap.c/

#include "u.h"
#include "../port/lib.h"
#include "mem.h"
#include "dat.h"
#include "fns.h"

enum {
	Allocated	= 1UL<<31,
};

typedef struct Mapent Mapent;
struct Mapent
{
	ulong	type;
	uvlong	addr;
	uvlong	size;
};

static struct {
	Lock;
	int	n;
	int	m;
	Mapent	a[256];
} mapalloc;

static void
dump1(Mapent *e)
{
	print("%.16llux-%.16llux %lux\n", e->addr, e->addr + e->size, e->type);
}

static int
insert(uvlong addr, uvlong size, ulong type)
{
	Mapent *e;

	if(size == 0 || addr == -1 || addr + size-1 < addr)
		return 0;

	if(mapalloc.n+mapalloc.m >= nelem(mapalloc.a))
		return 0;

	e = &mapalloc.a[mapalloc.n + mapalloc.m++];
	e->type = type;
	e->addr = addr;
	e->size = size;

	return 1;
}

static Mapent*
lookup(uvlong addr)
{
	Mapent *i, *e;

	if(addr == -1)
		return nil;
	for(i = mapalloc.a, e = i + mapalloc.n; i < e; i++){
		if(i->addr > addr)
			break;
		if(addr - i->addr < i->size)
			return i;
	}
	return nil;
}

static int
compare(void *a, void *b)
{
	Mapent *ma = a, *mb = b;

	if(ma->addr < mb->addr)
		return -1;
	if(ma->addr > mb->addr)
		return 1;

	if(ma->type < mb->type)
		return -1;
	if(ma->type > mb->type)
		return 1;

	return 0;
}

static void
sort(void)
{
	Mapent *d, *i, *j, *e;

Again:
	if(mapalloc.m == 0)
		return;
	mapalloc.n += mapalloc.m;
	mapalloc.m = 0;

	qsort(mapalloc.a, mapalloc.n, sizeof(*e), compare);

	d = i = mapalloc.a;
	e = i + mapalloc.n;
	while(i < e){
		if(i->size == 0)
			goto Skip;
		for(j = i+1; j < e; j++){
			if(j->size == 0)
				continue;
			if(j->addr - i->addr >= i->size)
				break;
			if(j->type <= i->type){
				if(j->addr - i->addr + j->size <= i->size)
					j->size = 0;
				else {
					j->size -= i->addr + i->size - j->addr;
					j->addr = i->addr + i->size;
				}
				continue;
			}
			if(j->addr - i->addr + j->size < i->size)
				if(!insert(j->addr + j->size, i->size - (j->addr + j->size - i->addr), i->type))
					continue;
			i->size = j->addr - i->addr;
			if(i->size == 0)
				goto Skip;
		}
		if(d > mapalloc.a){
			j = d-1;
			if(i->addr - j->addr == j->size && i->type == j->type){
				j->size += i->size;
				i->size = 0;
				goto Skip;
			}
		}
		memmove(d, i, sizeof(*i));
		d++;
	Skip:
		i++;
	}
	if(mapalloc.m > 0)
		memmove(d, e, mapalloc.m*sizeof(*e));
	mapalloc.n = d - mapalloc.a;
	goto Again;
}

void
memmapdump(void)
{
	int i;

	lock(&mapalloc);
	sort();
	for(i = 0; i < mapalloc.n; i++)
		dump1(&mapalloc.a[i]);
	unlock(&mapalloc);
}

uvlong
memmapnext(uvlong addr, ulong type)
{
	Mapent *i, *e;

	lock(&mapalloc);
	sort();
	for(i = mapalloc.a, e = i+mapalloc.n; i < e; i++){
		if(((i->type ^ type) & ~Allocated) == 0
		&& (addr == -1 || i->addr > addr)){
			addr = i->addr;
			unlock(&mapalloc);
			return addr;
		}
	}
	unlock(&mapalloc);
	return -1;
}

uvlong
memmapsize(uvlong addr, uvlong align)
{
	Mapent *i;
	uvlong size;

	size = 0;
	lock(&mapalloc);
	sort();
	if((i = lookup(addr)) != nil){
		if(align){
			addr += align-1;
			addr &= ~(align-1);
		}
		if(addr - i->addr < i->size)
			size = i->size - (addr - i->addr);
	}
	unlock(&mapalloc);
	return size;
}

void
memmapadd(uvlong addr, uvlong size, ulong type)
{
	type &= ~Allocated;
	lock(&mapalloc);
	if(insert(addr, size, type)){
		if(mapalloc.n+mapalloc.m >= nelem(mapalloc.a)-1){
			sort();
		}
	}
	unlock(&mapalloc);
}

uvlong
memmapalloc(uvlong addr, uvlong size, uvlong align, u32 type)
{
	Mapent *i, *e;

	print("memmapalloc addr 0x%p size 0x%zx %zd align 0x%zx type 0x%x\n",
		addr, size, size, align, type);
	type &= ~Allocated;
	lock(&mapalloc);
	sort();
	if(addr != -1){
		i = lookup(addr);
		if(i == nil || i->type != type)
			goto Fail;
		if(align){
			addr += align-1;
			addr &= ~(align-1);
			if(addr - i->addr >= i->size)
				goto Fail;
		}
		print("memmapalloc addr 0x%p i->addr 0x%p size 0x%zx %zd i->size 0x%zx %zd\n",
			addr, i->addr, size, size, i->size, i->size);
		if(addr - i->addr + size > i->size)
			goto Fail;
Alloc:
		print("memmapalloc insert addr 0x%p size 0x%zx %zd\n", addr, size, size);
		if(size > 0 && !insert(addr, size, type|Allocated))
			goto Fail;
		unlock(&mapalloc);
		return addr;
	}
	e = mapalloc.a + mapalloc.n;
	for(i = mapalloc.a; i < e; i++){
		if(i->type != type)
			continue;
		addr = i->addr;
		if(align){
			addr += align-1;
			addr &= ~(align-1);
			if(addr - i->addr >= i->size)
				continue;
		}
		if(addr - i->addr + size <= i->size)
			goto Alloc;
	}
Fail:
	unlock(&mapalloc);
	return -1;
}

void
memmapfree(uvlong addr, uvlong size, ulong type)
{
	Mapent *i;

	lock(&mapalloc);
	sort();
	i = lookup(addr);
	if(i == nil
	|| i->type != (type|Allocated)
	|| addr - i->addr + size > i->size){
		unlock(&mapalloc);
		return;
	}
	if(i->addr < addr)
		insert(i->addr, addr - i->addr, i->type);
	if(addr - i->addr + size < i->size)
		insert(addr+size, addr - i->addr + i->size - size, i->type);
	i->type &= ~Allocated;
	unlock(&mapalloc);
}