feat(malloc): add reallocArray(), update realloc() & compact(), tests

- update compact() to adjust top and kill free blocks if poss
thi-ng · Jan 31, 2019 · a55f477 · a55f477
1 parent bf8b28f
commit a55f477
Show file tree

Hide file tree

Showing 3 changed files with 63 additions and 30 deletions.
diff --git a/packages/malloc/src/pool.ts b/packages/malloc/src/pool.ts
@@ -150,8 +150,12 @@ export class MemPool implements
         }
         size = align(size, 8);
         let block = this._used;
+        let blockEnd: number;
+        let newAddr = 0;
         while (block) {
             if (block.addr === addr) {
+                blockEnd = addr + block.size;
+                const isTop = blockEnd >= this.top;
                 // shrink & possibly split existing block
                 if (size <= block.size) {
                     if (this.doSplit) {
@@ -164,29 +168,44 @@ export class MemPool implements
                                 next: null
                             });
                             this.doCompact && this.compact();
+                        } else if (isTop) {
+                            this.top = addr + size;
                         }
+                    } else if (isTop) {
+                        this.top = addr + size;
                     }
-                    return block.addr;
+                    newAddr = addr;
+                    break;
                 }
                 // try to enlarge block if current top
-                const blockEnd = addr + block.size;
-                if (blockEnd >= this.top && addr + size < this.end) {
+                if (isTop && addr + size < this.end) {
                     block.size = size;
                     this.top = addr + size;
-                    return addr;
+                    newAddr = addr;
+                    break;
                 }
                 // fallback to free & malloc
                 this.free(addr);
-                const newAddr = this.malloc(size);
-                // copy old block contents to new addr
-                if (newAddr) {
-                    this.u8.copyWithin(newAddr, addr, blockEnd);
-                }
-                return newAddr;
+                newAddr = this.malloc(size);
+                break;
             }
             block = block.next;
         }
-        return 0;
+        // copy old block contents to new addr
+        if (newAddr && newAddr !== addr) {
+            this.u8.copyWithin(newAddr, addr, blockEnd);
+        }
+        return newAddr;
+    }
+
+    reallocArray(ptr: TypedArray, num: number) {
+        if (ptr.buffer !== this.buf) {
+            return null;
+        }
+        const addr = this.realloc(ptr.byteOffset, num * ptr.BYTES_PER_ELEMENT);
+        return addr ?
+            new (<any>ptr.constructor)(this.buf, addr, num) :
+            null;
     }
 
     free(ptr: number | TypedArray) {
@@ -239,22 +258,23 @@ export class MemPool implements
         let block = this._free;
         let prev: MemBlock;
         let scan: MemBlock;
+        let scanPrev: MemBlock;
         let res = false;
         while (block) {
-            prev = block;
+            scanPrev = block;
             scan = block.next;
-            while (scan && prev.addr + prev.size === scan.addr) {
+            while (scan && scanPrev.addr + scanPrev.size === scan.addr) {
                 // console.log("merge:", scan.addr, scan.size);
-                prev = scan;
+                scanPrev = scan;
                 scan = scan.next;
             }
-            if (prev !== block) {
-                const newSize = prev.addr - block.addr + prev.size;
+            if (scanPrev !== block) {
+                const newSize = scanPrev.addr - block.addr + scanPrev.size;
                 // console.log("merged size:", newSize);
                 block.size = newSize;
-                const next = prev.next;
+                const next = scanPrev.next;
                 let tmp = block.next;
-                while (tmp !== prev.next) {
+                while (tmp !== scanPrev.next) {
                     // console.log("release:", tmp.addr);
                     const tn = tmp.next;
                     tmp.next = null;
@@ -263,6 +283,14 @@ export class MemPool implements
                 block.next = next;
                 res = true;
             }
+            // re-adjust top if poss
+            if (block.addr + block.size >= this.top) {
+                this.top = block.addr;
+                prev ?
+                    (prev.next = block.next) :
+                    (this._free = block.next);
+            }
+            prev = block;
             block = block.next;
         }
         return res;

diff --git a/packages/malloc/src/wrap.ts b/packages/malloc/src/wrap.ts
@@ -15,4 +15,4 @@ const CTORS: IObjectOf<BlockCtor> = {
 
 export const wrap =
     (type: Type, buf: ArrayBuffer, addr: number, num: number) =>
-        CTORS[type](buf, addr, num);
+        CTORS[type](buf, addr, num);
diff --git a/packages/malloc/test/index.ts b/packages/malloc/test/index.ts
@@ -50,8 +50,8 @@ describe("malloc", () => {
         assert(pool.free(b), "free c");
         assert(!pool.free(b), "free b (repeat)");
         stats = pool.stats();
-        assert.equal(stats.top, 8 + 16 + 32 + 24, "top2");
-        assert.deepEqual(stats.free, { count: 1, size: 16 + 32 + 24 });
+        assert.equal(stats.top, 8, "top2");
+        assert.deepEqual(stats.free, { count: 0, size: 0 });
         assert.deepEqual(stats.used, { count: 0, size: 0 });
 
         // alloc & split free block
@@ -90,11 +90,12 @@ describe("malloc", () => {
 
         // non-continous free chain
         assert(pool.free(c), "free c2");
+        assert.equal(stats.top, 80, "top6");
         assert(pool.free(a), "free a3");
         stats = pool.stats();
-        assert.deepEqual(stats.free, { count: 2, size: 16 });
+        assert.deepEqual(stats.free, { count: 1, size: 8 });
         assert.deepEqual(stats.used, { count: 1, size: 64 });
-        assert.equal(stats.top, 88, "top6");
+        assert.equal(stats.top, 80, "top7");
 
         // alloc larger size to force walking free chain
         // and then alloc @ top (reuse block @ 80)
@@ -103,14 +104,15 @@ describe("malloc", () => {
         stats = pool.stats();
         assert.deepEqual(stats.free, { count: 1, size: 8 });
         assert.deepEqual(stats.used, { count: 2, size: 96 });
-        assert.equal(stats.top, 80 + 32, "top7");
+        assert.equal(stats.top, 80 + 32, "top8");
 
         assert(pool.free(a), "free a4");
         assert(pool.free(b), "free b3");
         stats = pool.stats();
-        assert.deepEqual(stats.free, { count: 1, size: 8 + 64 + 32 });
+        assert.deepEqual(stats.free, { count: 0, size: 0 });
         assert.deepEqual(stats.used, { count: 0, size: 0 });
-        assert.equal(stats.top, 8 + 8 + 64 + 32, "top8");
+        assert.equal(stats.available, 256 - 8);
+        assert.equal(stats.top, 8, "top9");
 
         pool.freeAll();
         assert.deepEqual(
@@ -189,8 +191,9 @@ describe("malloc", () => {
         // returned arrays are zeroed
         a = pool.callocAs(Type.U32, 3);
         b = pool.callocAs(Type.U32, 3);
-        assert.deepEqual(a, [0, 0, 0]);
-        assert.deepEqual(b, [0, 0, 0]);
+        const t = [0, 0, 0];
+        assert.deepEqual(a, t);
+        assert.deepEqual(b, t);
     });
 
     it("malloc top", () => {
@@ -207,6 +210,8 @@ describe("malloc", () => {
         pool.free(c);
     });
 
+    it("realloc");
+
     it("no compact", () => {
         pool = new MemPool(0x100, { compact: false });
         pool.malloc(8);
@@ -216,9 +221,9 @@ describe("malloc", () => {
         pool.free(16);
         pool.free(24);
         let p: any = pool;
-        assert.equal(p._free.addr, 24);
+        assert.equal(p._free.addr, 8);
         assert.equal(p._free.next.addr, 16);
-        assert.equal(p._free.next.next.addr, 8);
+        assert.equal(p._free.next.next.addr, 24);
         assert.equal(p._free.next.next.next, null);
     });