--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/DebugWorker/memory.c	Tue Jan 18 19:54:28 2022 +0900
@@ -0,0 +1,379 @@
+/*
+
+    memory fragment management library
+
+    Shinji Kono (2006)
+
+    usage:
+
+    MemoryPtr db = 0;
+    add_memory(address,length,&db);
+
+	memory pattern is copyied and stored in a binary tree in db.
+	All patterns are shared.
+
+    memory pattern database (binary tree by pattern)
+
+
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "memory.h"
+#include "crc32.h"
+#include <string.h>
+
+#define MEMORY_REPORT 1
+
+#if MEMORY_REPORT
+int    memory_header;
+int    memcmp_count;
+int    memory_body;
+int    restore_count;
+int    restore_size;
+int    range_count;
+int    range_size;
+#endif
+
+extern void die_exit(char *);
+
+void
+die_exit(char *msg)
+{
+    fprintf(stderr,"%s\n",msg);
+    exit(1);
+}
+
+// static MemoryPtr memory_root;
+
+
+/*
+
+    make memory fragment as a part of the program state
+
+ */
+
+MemoryPtr
+create_memory(void *adr, int length)
+{
+    MemoryPtr m = (MemoryPtr)malloc(sizeof(Memory));
+    if (!m) die_exit("Cann't alloc memory list.");
+    m->left = m->right = 0;
+    m->length = length;
+    m->adr = m->body = adr;
+#if MEMORY_REPORT
+    memory_header++;
+#endif
+    return m;
+}
+
+/*
+
+    Compute hash value of a memory fragment
+
+ */
+
+unsigned
+compute_memory_hash1(MemoryPtr m,unsigned hash)
+{
+    return Get_CRC((unsigned char *)m->adr,m->length, hash);
+}
+
+void
+free_memory(MemoryPtr m)
+{
+    m->left = m->right = 0;
+    m->adr = m->body = 0;
+    free(m);
+}
+
+/*
+
+   Compare memory contents ( doesn't care about its address )
+
+ */
+
+int
+cmp_content(MemoryPtr a,MemoryPtr b)
+{
+    if (a->length != b->length) {
+      if (a->length > b->length) {
+        return 1;
+      } else {
+        return -1;
+      }
+    }
+    if (a->hash == b->hash) {
+#if MEMORY_REPORT
+      memcmp_count ++;
+#endif
+      return memcmp(a->body,b->body,a->length);
+    } else if (a->hash > b->hash) {
+        return 1;
+    } else {
+        return -1;
+    }
+}
+
+/*
+
+   Compare entire memory contents ( doesn't care about its address )
+
+ */
+
+static int
+cmp_memory1(MemoryPtr a,MemoryPtr b)
+{
+    int r;
+    if ((r=cmp_content(a,b))) return r;
+
+    if (a->adr==b->adr) {
+      return 0;
+    }
+    return (a->adr > b->adr) ? 1 : -1;
+}
+
+int
+cmp_memory(MemoryPtr a,MemoryPtr b)
+{
+    int r;
+    while(1) {
+      if ((r=cmp_memory1(a,b))) return r;
+      if (a->left && b->left) {
+          if ((r=cmp_memory(a->left,b->left))) return r;
+      } else if (a->left || b->left) {
+          return (a->left > b->left)? 1 : -1;
+      }
+      if (a->right && b->right) {
+          a = a->right; b = b->right;
+          // recursive loop
+      } else if (a->right || b->right) {
+          return (a->right > b->right)? 1 : -1;
+      } else {
+          return 0;  // singleton
+      }
+    }
+}
+
+/*
+    Make a copy of real memory fragments
+ */
+
+MemoryPtr
+copy_memory1(MemoryPtr m)
+{
+    MemoryPtr new = create_memory(m->adr,m->length);
+    void *p = (void *)malloc(m->length);
+    if (!p) {
+      die_exit("can't alloc memory body");
+      return 0;
+    }
+#if MEMORY_REPORT
+    memory_body += m->length;
+#endif
+    memcpy(p,m->adr,m->length);
+    m->body = new->body = p;     // abondon original memory pattern
+    new->hash = m->hash;
+    return new;
+}
+
+MemoryPtr
+copy_memory(MemoryPtr m, MemoryPtr *db)
+{
+    MemoryPtr new, out;
+    if (!m) return m;
+    new = create_memory(m->adr,m->length);
+    new->hash = m->hash;
+    // look up is necessary to share its memory pattern
+    memory_lookup(new, db, copy_memory1, &out);
+    if (m->left)  new->left = copy_memory(m->left, db);
+    if (m->right) new->right = copy_memory(m->right, db);
+    return new;
+}
+
+/*
+    restore copied memory save to the original addresses
+ */
+
+void
+restore_memory(MemoryPtr m)
+{
+    while (m) {
+      memcpy(m->adr,m->body,m->length);
+#if MEMORY_REPORT
+      restore_count ++;
+      restore_size += m->length;
+#endif
+      if (m->left)  restore_memory(m->left);
+      m = m->right;
+    }
+}
+
+
+/*
+    get hash for all memeory fragments
+	initial value of hash should be zero
+ */
+
+unsigned
+get_memory_hash(MemoryPtr m, unsigned hash)
+{
+    if (!m) return hash;
+    if (m->left)  hash = get_memory_hash(m->left, hash);
+    m->hash = compute_memory_hash1(m, 0xffffffff);        // for each memory segment
+    hash =  Get_CRC((unsigned char *)&m->hash,sizeof(m->hash), hash);  // for entire chain
+    if (m->right) hash = get_memory_hash(m->right, hash);
+    return hash;
+}
+
+/*
+    add modified memory fragments to the pattern database
+ */
+
+MemoryPtr
+add_memory(void *ptr,int length, MemoryPtr *parent)
+{
+    Memory m, *out;
+    m.adr = m.body = ptr;
+    m.length = length;
+    m.left = m.right = 0;
+    m.hash = compute_memory_hash1(&m, 0xffffffff);
+    memory_lookup(&m, parent, copy_memory1, &out);
+    return out;
+}
+
+int
+memory_lookup(MemoryPtr m, MemoryPtr *parent,
+		    MemoryPtr (*new_memory)(MemoryPtr), MemoryPtr *out)
+{
+    MemoryPtr db;
+    int r;
+
+    while(1) {
+        db = *parent;
+        if (!db) {
+	    /* not found */
+          if (new_memory && out) {
+              db = new_memory(m);
+              db->left = db->right = 0;
+              *out = *parent = db;
+          }
+          return 0;
+        }
+        if(!(r = cmp_memory1(m,db))) {
+            /* bingo */
+          if (out) {
+            *out = db;
+          }
+          return 1;
+        } else if (r>0) {
+            parent = &db->left;
+        } else if (r<0) {
+            parent = &db->right;
+        }
+    }
+    /* !NOT REACHED */
+}
+
+/*
+    memory range list management for state registration
+	this list points the real memory
+ */
+
+MemoryPtr
+add_memory_range(void *ptr,int length, MemoryPtr *parent)
+{
+    Memory m, *out;
+    m.adr = ptr;
+    m.length = length;
+    m.left = m.right = 0;
+
+    memory_range_lookup(&m, parent, &out);
+    return out;
+}
+
+static int
+cmp_range(MemoryPtr a,MemoryPtr b)
+{
+    if (a->adr==b->adr) {
+      if (a->length != b->length)
+        die_exit("memory range inconsitency");
+      return 0;
+    }
+    return (a->adr > b->adr) ? 1 : -1;
+}
+
+int
+memory_range_lookup(MemoryPtr m, MemoryPtr *parent, MemoryPtr *out)
+{
+    MemoryPtr db;
+    int r;
+
+    while(1) {
+        db = *parent;
+        if (!db) {
+	    /* not found */
+          if (out) {
+            db = create_memory(m->adr, m->length);
+            *out = *parent = db;
+          }
+#if MEMORY_REPORT
+        range_count++;
+        range_size+=m->length;
+#endif
+        return 0;
+      }
+      if(!(r = cmp_range(m,db))) {
+            /* bingo (actually an error) */
+        if (out) {
+          *out = db;
+        }
+        return 1;
+      } else if (r>0) {
+        parent = &db->left;
+      } else if (r<0) {
+            parent = &db->right;
+      }
+  }
+    /* !NOT REACHED */
+}
+
+/*
+    dump memory
+ */
+
+void
+dump_memory(MemoryPtr m)
+{
+    while (m) {
+      // printf("\n%p : ",m->adr);
+      unsigned char *p = (unsigned char *)m->adr;
+      for(int i=0; i<m->length ;i++) {
+          printf("%02x",p[i]);
+          if ((i+1)%4==0) putchar(' ');
+      }
+      if (m->left)  dump_memory(m->left);
+      m = m->right;
+    }
+}
+
+
+/*
+ */
+
+void
+memory_usage()
+{
+#if MEMORY_REPORT
+    printf("	memory_header %d\n",memory_header);
+    printf("	memcmp_count %d\n",memcmp_count);
+    printf("	memory_body %d\n",memory_body);
+    printf("	restore_count %d\n",restore_count);
+    printf("	restore_size %d\n",restore_size);
+    printf("	range_count %d\n",range_count);
+    printf("	range_size %d\n",range_size);
+#endif
+}
+
+
+/* end */