Change method for the mmap free bloc search for a faster one

1 files changed, 134 insertions, 86 deletions

diff --git a/src/custommem.c b/src/custommem.c
index ddfe86b2..da38fb4d 100644
--- a/src/custommem.c
+++ b/src/custommem.c
@@ -54,6 +54,13 @@ static uint8_t *volatile memprot[1<<20];    // x86_64 mem is 48bits, page is 12b
 static uint8_t memprot_default[MEMPROT_SIZE];
 static int inited = 0;
 
+typedef struct mapmem_s {
+    uintptr_t begin, end;
+    struct mapmem_s *prev, *next;
+} mapmem_t;
+
+static mapmem_t *mapmem = NULL;
+
 typedef struct blocklist_s {
     void*               block;
     size_t              maxfree;
@@ -824,6 +831,102 @@ void unprotectDB(uintptr_t addr, size_t size)
     }
     pthread_mutex_unlock(&mutex_prot);
 }
+void addMapMem(uintptr_t begin, uintptr_t end)
+{
+    // granularity is 0x10000, like on x86_64
+    begin &=~0xffff;
+    end = (end&~0xffff)+0xffff; // full granulirity
+    // sanitize values
+    if(end==0xffff) return;
+    if(!begin) begin = 0x1000;
+    // find attach point (cannot be the 1st one by construction)
+    mapmem_t* m = mapmem;
+    while(m->next && m->next->begin<begin) {
+        m = m->next;
+    }
+    // attach at the end of m
+    if(m->end>end) {
+        return; // included... nothing to do
+    }
+    if(m->end+1>=begin) {
+        m->end = end;   // enlarge block
+        return;
+    }
+    mapmem_t* newm = (mapmem_t*)calloc(1, sizeof(mapmem_t));
+    newm->prev = m;
+    newm->next = m->next;
+    newm->begin = begin;
+    newm->end = end;
+    m->next = newm;
+    while(newm->next && newm->next->begin<newm->end) {
+        // fuse with next
+        if(newm->next->end>newm->end)
+            newm->end = newm->next->end;
+        mapmem_t* tmp = newm->next;
+        newm->next = tmp->next;
+        tmp->prev = newm;
+        free(tmp);
+    }
+    // all done!
+}
+void removeMapMem(uintptr_t begin, uintptr_t end)
+{
+    // granularity is 0x10000, like on x86_64
+    begin &=~0xffff;
+    end = (end&~0xffff)+0xffff; // full granulirity
+    // sanitize values
+    if(end==0xffff) return;
+    if(!begin) begin = 0x1000;
+    mapmem_t* m = mapmem;
+    while(begin<end) {
+        // find attach point (cannot be the 1st one by construction)
+        while(m && m->end<begin) {
+            m = m->next;
+        }
+        if(!m) {
+            return;
+        }
+        if(m->begin<end)
+            return; // block is not there
+        else if(m->begin <= begin) {
+            if(m->end>end) {
+                // whole zone to free if now free, nothing more to do, bye
+                m->begin = end + 1;
+                return;
+            } else {
+                begin = m->end + 1;
+                mapmem_t* tmp = m;
+                m = m->next;
+                m->prev = tmp->prev;
+                tmp->prev->next = m;
+                free(tmp);
+            }
+        } else {
+            if(m->end>end) {
+                // split the block!
+                mapmem_t* newm = (mapmem_t*)calloc(1, sizeof(mapmem_t));
+                newm->begin = end+1;
+                newm->end = m->end;
+                m->end = begin - 1;
+                newm->next = m->next;
+                newm->prev = m;
+                m->next = newm;
+            } else if(m->end == end) {
+                m->end = begin - 1;
+                return;
+            } else {
+                //free the block
+                begin = m->end + 1;
+                mapmem_t* tmp = m;
+                m = m->next;
+                tmp->prev->next = m;
+                if(m)
+                    m->prev = tmp->prev;
+                free(tmp);
+            }
+        }
+    }
+}
 
 int isprotectedDB(uintptr_t addr, size_t size)
 {
@@ -852,6 +955,7 @@ int isprotectedDB(uintptr_t addr, size_t size)
 void updateProtection(uintptr_t addr, size_t size, uint32_t prot)
 {
     dynarec_log(LOG_DEBUG, "updateProtection %p:%p 0x%x\n", (void*)addr, (void*)(addr+size-1), prot);
+    addMapMem(addr, addr+size);
     uintptr_t idx = (addr>>MEMPROT_SHIFT);
     uintptr_t end = ((addr+size-1)>>MEMPROT_SHIFT);
     if(end>=(1LL<<(48-MEMPROT_SHIFT)))
@@ -881,6 +985,7 @@ void updateProtection(uintptr_t addr, size_t size, uint32_t prot)
 
 void setProtection(uintptr_t addr, size_t size, uint32_t prot)
 {
+    addMapMem(addr, addr+size);
     uintptr_t idx = (addr>>MEMPROT_SHIFT);
     uintptr_t end = ((addr+size-1)>>MEMPROT_SHIFT);
     if(end>=(1LL<<(48-MEMPROT_SHIFT)))
@@ -907,6 +1012,7 @@ void setProtection(uintptr_t addr, size_t size, uint32_t prot)
 void allocProtection(uintptr_t addr, size_t size, uint32_t prot)
 {
     dynarec_log(LOG_DEBUG, "allocProtection %p:%p 0x%x\n", (void*)addr, (void*)(addr+size-1), prot);
+    addMapMem(addr, addr+size);
     uintptr_t idx = (addr>>MEMPROT_SHIFT);
     uintptr_t end = ((addr+size-1LL)>>MEMPROT_SHIFT);
     if(end>=(1LL<<(48-MEMPROT_SHIFT)))
@@ -972,6 +1078,7 @@ static int blockempty(uint8_t* mem)
 void freeProtection(uintptr_t addr, size_t size)
 {
     dynarec_log(LOG_DEBUG, "freeProtection %p:%p\n", (void*)addr, (void*)(addr+size-1));
+    removeMapMem(addr, addr+size);
     uintptr_t idx = (addr>>MEMPROT_SHIFT);
     uintptr_t end = ((addr+size-1LL)>>MEMPROT_SHIFT);
     if(end>=(1LL<<(48-MEMPROT_SHIFT)))
@@ -1018,107 +1125,38 @@ uint32_t getProtection(uintptr_t addr)
     return ret;
 }
 
-#define LOWEST (void*)0x20000
-static uintptr_t nextFree(uintptr_t addr, uintptr_t increment)
-{
-    if(addr>=(1LL<<48))
-        return 0;
-    do {
-        uintptr_t idx = (addr>>MEMPROT_SHIFT);
-        if(memprot[idx>>16]==memprot_default) {
-            return addr;
-        }
-        for (uintptr_t i=(idx&0xffff); i<MEMPROT_SIZE; ++i)
-            if(!memprot[idx>>16][i]) {
-                return ((idx>>16)<<(16+12))+(i<<MEMPROT_SHIFT);
-            }
-        addr += increment?increment:(1LL<<(16+12));
-        addr &= ~((1LL<<(16+12)-1LL));
-    } while(1);
-}
-static uintptr_t maxFree(uintptr_t addr, uintptr_t sz)
-{
-    if(addr>=(1LL<<48))
-        return 0;
-    uintptr_t mfree = 0;
-    do {
-        uintptr_t idx = (addr>>MEMPROT_SHIFT);
-        if(memprot[idx>>16]==memprot_default) {
-            mfree+=(1LL<<(16+12));
-            if(mfree>sz) {
-                return addr;
-            }
-        } else {
-            for (uintptr_t i=(idx&0xffffLL); i<MEMPROT_SIZE; ++i)
-                if(!memprot[idx>>16][i]) {
-                    mfree+=(1<<MEMPROT_SHIFT);
-                } else
-                    return mfree;
-        }
-        addr += (1LL<<(12+16));
-        addr &= ~((1LL<<(12+16))-1LL);
-    } while(1);
-}
+#define LOWEST (void*)0x10000
 void* find32bitBlock(size_t size)
 {
     return findBlockNearHint(LOWEST, size);
 }
 void* find47bitBlock(size_t size)
 {
-    // slow iterative search... Would need something better one day
-    uintptr_t addr = 0x100000000LL;
-    do {
-        addr = nextFree(addr, 0x10000);
-        uintptr_t sz = maxFree(addr, size);
-        if(sz>=size) {
-            return (void*)addr;
-        }
-        addr += sz;
-    } while(addr<0x800000000000LL);
-    // search in 32bits as a backup
-    addr = (uintptr_t)LOWEST;
-    do {
-        addr = nextFree(addr, 0x10000);
-        uintptr_t sz = maxFree(addr, size);
-        if(sz>=size) {
-            return (void*)addr;
-        }
-        addr += sz;
-    } while(addr<0x100000000LL);
-    printf_log(LOG_DEBUG, "Warning: cannot find a 0x%zx block in 47bits address space\n", size);
-    return NULL;
+    void* ret = find47bitBlockNearHint((void*)0x100000000LL, size);
+    if(!ret)
+        ret = find32bitBlock(size);
+    return ret;
 }
 void* find47bitBlockNearHint(void* hint, size_t size)
 {
-    // slow iterative search... Would need something better one day
-    uintptr_t addr = (uintptr_t)(hint?hint:LOWEST);
-    do {
-        addr = nextFree(addr, 0x10000);
-        uintptr_t sz = maxFree(addr, size);
-        if(sz>=size) {
-            return (void*)addr;
-        }
-        addr += sz;
-    } while(addr<0x800000000000LL);
-    printf_log(LOG_DEBUG, "Warning: cannot find a 0x%zx block in 32bits address space\n", size);
+    mapmem_t* m = mapmem;
+    while(m && m->end<0x800000000000LL) {
+        if((m->end>(uintptr_t)hint) && (!m->next || (m->next->begin-(m->end+1)>=size)))
+            return (void*)(m->end + 1);
+        m = m->next;
+    }
     return NULL;
 }
 void* findBlockNearHint(void* hint, size_t size)
 {
-    // slow iterative search... Would need something better one day
-    uintptr_t addr = (uintptr_t)(hint?hint:LOWEST);
-    do {
-        addr = nextFree(addr, 0x10000);
-        uintptr_t sz = maxFree(addr, size);
-        if(sz>=size) {
-            return (void*)addr;
-        }
-        addr += sz;
-    } while(addr<0x100000000LL);
-    printf_log(LOG_NONE, "Warning: cannot find a 0x%zx block in 32bits address space\n", size);
+    mapmem_t* m = mapmem;
+    while(m && m->end<0x100000000LL) {
+        if((m->end>(uintptr_t)hint) && (!m->next || (m->next->begin-(m->end+1)>=size)))
+            return (void*)(m->end + 1);
+        m = m->next;
+    }
     return NULL;
 }
-#undef LOWEST
 
 int unlockCustommemMutex()
 {
@@ -1183,6 +1221,11 @@ void init_custommem_helper(box64context_t* ctx)
         }
 #endif
     pthread_atfork(NULL, NULL, atfork_child_custommem);
+    // init mapmem list
+    mapmem = (mapmem_t*)calloc(1, sizeof(mapmem_t));
+    mapmem->begin = 0x0;
+    mapmem->end = (uintptr_t)LOWEST - 1;
+    loadProtectionFromMap();
 }
 
 void fini_custommem_helper(box64context_t *ctx)
@@ -1260,4 +1303,9 @@ void fini_custommem_helper(box64context_t *ctx)
     free(p_blocks);
     pthread_mutex_destroy(&mutex_prot);
     pthread_mutex_destroy(&mutex_blocks);
+    while(mapmem) {
+        mapmem_t *tmp = mapmem;
+        mapmem = mapmem->next;
+        free(tmp);
+    }
 }