ref: 9cb54e7e5f803ce37dd4689b3820f8ca6167e1b2
parent: d8beb18b0119dc7b8a0175dc434badf225d2f390
author: cinap_lenrek <cinap_lenrek@felloff.net>
date: Sat Apr 4 12:04:27 EDT 2020
kernel: add portable memory map code (port/memmap.c) This is a generic memory map for physical addresses. Entries can be added with memmapadd() giving a range and a type. Ranges can be allocated and freed from the map. The code automatically resolves overlapping ranges by type priority.
--- /dev/null
+++ b/sys/src/9/port/memmap.c
@@ -1,0 +1,271 @@
+#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, ulong type)
+{+ Mapent *i, *e;
+
+ 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;
+ }
+ if(addr - i->addr + size > i->size)
+ goto Fail;
+Alloc:
+ 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);
+}
--- a/sys/src/9/port/portfns.h
+++ b/sys/src/9/port/portfns.h
@@ -168,6 +168,12 @@
void* mallocalign(ulong, ulong, long, ulong);
void mallocsummary(void);
Block* mem2bl(uchar*, int);
+void memmapdump(void);
+uvlong memmapnext(uvlong, ulong);
+uvlong memmapsize(uvlong, uvlong);
+void memmapadd(uvlong, uvlong, ulong);
+uvlong memmapalloc(uvlong, uvlong, uvlong, ulong);
+void memmapfree(uvlong, uvlong, ulong);
ulong mcountseg(Segment*);
void mfreeseg(Segment*, uintptr, ulong);
void microdelay(int);
--
⑨