From 220bc631f92890d09d7473eb62e80966faaefc4d Mon Sep 17 00:00:00 2001
From: comex
Date: Sun, 1 Mar 2015 13:26:58 -0500
Subject: make jump-dis use a vec as a stack, rather than a hacky queue

---
 Makefile       |  4 ++--
 lib/cbit/vec.h |  9 +++++++++
 lib/jump-dis.c | 35 +++++++++--------------------------
 3 files changed, 20 insertions(+), 28 deletions(-)

diff --git a/Makefile b/Makefile
index 7d25c61..2d9e671 100644
--- a/Makefile
+++ b/Makefile
@@ -126,8 +126,8 @@ $(eval $(call define_test,td-simple-i386,td-simple,$(CC) -std=c11 -DHDR='"x86/di
 $(eval $(call define_test,td-simple-x86-64,td-simple,$(CC) -std=c11 -DHDR='"x86/dis-main.inc.h"' -Dxdis=dis -DFORCE_TARGET_x86_64))
 $(eval $(call define_test,dis-arm,dis,$(CC) -std=c11 -DFORCE_TARGET_arm))
 $(eval $(call define_test,dis-arm64,dis,$(CC) -std=c11 -DFORCE_TARGET_arm64))
-$(eval $(call define_test,jump-dis-arm,jump-dis,$(CC) -std=c11 -DFORCE_TARGET_arm -O0))
-$(eval $(call define_test,jump-dis-arm64,jump-dis,$(CC) -std=c11 -DFORCE_TARGET_arm64 -O0))
+$(eval $(call define_test,jump-dis-arm,jump-dis,$(CC) -std=c11 -DFORCE_TARGET_arm -O0 out/cbit/vec.o))
+$(eval $(call define_test,jump-dis-arm64,jump-dis,$(CC) -std=c11 -DFORCE_TARGET_arm64 -O0 out/cbit/vec.o))
 $(eval $(call define_test,transform-dis-arm,transform-dis,$(CC) -std=c11 -DFORCE_TARGET_arm -O0))
 $(eval $(call define_test,transform-dis-arm64,transform-dis,$(CC) -std=c11 -DFORCE_TARGET_arm64 -O0))
 $(eval $(call define_test,transform-dis-i386,transform-dis,$(CC) -std=c11 -DFORCE_TARGET_i386 -O0))
diff --git a/lib/cbit/vec.h b/lib/cbit/vec.h
index 87e4c28..2889ac1 100644
--- a/lib/cbit/vec.h
+++ b/lib/cbit/vec.h
@@ -70,6 +70,15 @@ void vec_realloc_internal_as_necessary(struct vec_internal *vi,
       *vec_appendp_##name(v) = val; \
    } \
    UNUSED_STATIC_INLINE \
+   VEC_TY(name) vec_pop_##name(struct vec_##name *v) { \
+      size_t i = v->length - 1; \
+      VEC_TY(name) ret = v->els[i]; \
+      if (i - 1 < v->capacity / 3) \
+         vec_realloc_internal_as_necessary(&v->vi, i - 1, sizeof(v->els[0])); \
+      v->length = i; \
+      return ret; \
+   } \
+   UNUSED_STATIC_INLINE \
    void vec_concat_##name(struct vec_##name *v1, const struct vec_##name *v2) { \
       size_t l1 = v1->length, l2 = v2->length; \
       vec_resize_##name(v1, safe_add(l1, l2)); \
diff --git a/lib/jump-dis.c b/lib/jump-dis.c
index e1a7d48..e740874 100644
--- a/lib/jump-dis.c
+++ b/lib/jump-dis.c
@@ -1,3 +1,4 @@
+#include "cbit/vec.h"
 #include "substitute-internal.h"
 #ifdef TARGET_DIS_SUPPORTED
 #define DIS_MAY_MODIFY 0
@@ -18,6 +19,8 @@ enum {
     JUMP_ANALYSIS_MAX_SIZE = JUMP_ANALYSIS_MAX_INSNS * MIN_INSN_SIZE,
 };
 
+DECL_VEC(uint_tptr, uint_tptr);
+
 struct jump_dis_ctx {
     /* outputs */
     bool bad_insn;
@@ -29,12 +32,8 @@ struct jump_dis_ctx {
     uint_tptr pc_patch_end;
 
     uint8_t seen_mask[JUMP_ANALYSIS_MAX_INSNS / 8];
-    /* queue of instructions to visit */
-    uint_tptr *queue;
-    size_t queue_write_off;
-    size_t queue_read_off;
-    size_t queue_size;
-    size_t queue_count;
+    /* queue of instructions to visit (well, stack) */
+    VEC_STORAGE_CAPA(uint_tptr, 10) queue;
 
     struct arch_dis_ctx arch;
 };
@@ -60,21 +59,7 @@ static void jump_dis_add_to_queue(struct jump_dis_ctx *ctx, uint_tptr pc) {
     }
     ctx->seen_mask[diff / 8] |= 1 << (diff % 8);
 
-    if (ctx->queue_write_off == ctx->queue_read_off && (ctx->queue_count || !ctx->queue_size)) {
-        size_t new_size = ctx->queue_size * 2 + 5;
-        ctx->queue = realloc(ctx->queue, new_size * sizeof(*ctx->queue));
-        if (!ctx->queue)
-            substitute_panic("%s: out of memory\n", __func__);
-        size_t new_read_off = new_size - (ctx->queue_size - ctx->queue_read_off);
-        memmove(ctx->queue + new_read_off,
-                ctx->queue + ctx->queue_read_off,
-                (ctx->queue_size - ctx->queue_read_off) * sizeof(*ctx->queue));
-        ctx->queue_read_off = new_read_off % new_size;
-        ctx->queue_size = new_size;
-    }
-    ctx->queue[ctx->queue_write_off] = pc;
-    ctx->queue_write_off = (ctx->queue_write_off + 1) % ctx->queue_size;
-    ctx->queue_count++;
+    vec_append_uint_tptr(&ctx->queue.v, pc);
 }
 
 static INLINE UNUSED
@@ -157,16 +142,14 @@ bool jump_dis_main(void *code_ptr, uint_tptr pc_patch_start, uint_tptr pc_patch_
             jump_dis_add_to_queue(&ctx, ctx.base.pc + ctx.base.op_size);
 
         /* get next address */
-        if (ctx.queue_read_off == ctx.queue_write_off)
+        if (!ctx.queue.v.length)
             break;
-        ctx.base.pc = ctx.queue[ctx.queue_read_off];
-        ctx.queue_read_off = (ctx.queue_read_off + 1) % ctx.queue_size;
-        ctx.queue_count--;
+        ctx.base.pc = vec_pop_uint_tptr(&ctx.queue.v);
     }
     /* no bad instructions! */
     ret = false;
 fail:
-    free(ctx.queue);
+    vec_free_storage(&ctx.queue.v);
     return ret;
 }
 
-- 
cgit v1.2.3