Mercurial > hg > CbC > old > DPP

comparison memory.c @ 0:d4bc23cb728b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS (CVS_DB/member/atsuki/cbc/DPP)
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Wed, 16 Dec 2015 15:16:11 +0900
parents
children 190dadd8405b
comparison
equal deleted inserted replaced
-1:000000000000 0:d4bc23cb728b
1 /*
2
3 memory fragment management library
4
5 Shinji Kono (2006)
6
7 usage:
8
9 MemoryPtr db = 0;
10 add_memory(address,length,&db);
11
12 memory pattern is copyied and stored in a binary tree in db.
13 All patterns are shared.
14
15 memory pattern database (binary tree by pattern)
16
17
18 */
19
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include "memory.h"
23 #include "crc32.h"
24 #include <string.h>
25
26 #define MEMORY_REPORT 1
27
28 #if MEMORY_REPORT
29 int memory_header;
30 int memcmp_count;
31 int memory_body;
32 int restore_count;
33 int restore_size;
34 int range_count;
35 int range_size;
36 #endif
37
38 extern void die_exit(char *);
39
40 void
41 die_exit(char *msg)
42 {
43 fprintf(stderr,"%s\n",msg);
44 exit(1);
45 }
46
47 // static MemoryPtr memory_root;
48
49
50 /*
51
52 make memory fragment as a part of the program state
53
54 */
55
56 MemoryPtr
57 create_memory(void *adr, int length)
58 {
59 MemoryPtr m = (MemoryPtr)malloc(sizeof(Memory));
60 if (!m) die_exit("Cann't alloc memory list.");
61 m->left = m->right = 0;
62 m->length = length;
63 m->adr = m->body = adr;
64 #if MEMORY_REPORT
65 memory_header++;
66 #endif
67 return m;
68 }
69
70 /*
71
72 Compute hash value of a memory fragment
73
74 */
75
76 void
77 compute_memory_hash1(MemoryPtr m)
78 {
79 m->hash = Get_CRC((unsigned char *)m->adr,m->length);
80 }
81
82 void
83 free_memory(MemoryPtr m)
84 {
85 m->left = m->right = 0;
86 m->adr = m->body = 0;
87 free(m);
88 }
89
90 /*
91
92 Compare memory contents ( doesn't care about its address )
93
94 */
95
96 int
97 cmp_content(MemoryPtr a,MemoryPtr b)
98 {
99 if (a->length != b->length) {
100 if (a->length > b->length) {
101 return 1;
102 } else {
103 return -1;
104 }
105 }
106 if (a->hash == b->hash) {
107 #if MEMORY_REPORT
108 memcmp_count ++;
109 #endif
110 return memcmp(a->body,b->body,a->length);
111 } else if (a->hash > b->hash) {
112 return 1;
113 } else {
114 return -1;
115 }
116 }
117
118 /*
119
120 Compare entire memory contents ( doesn't care about its address )
121
122 */
123
124 static int
125 cmp_memory1(MemoryPtr a,MemoryPtr b)
126 {
127 int r;
128 if ((r=cmp_content(a,b))) return r;
129
130 if (a->adr==b->adr) {
131 return 0;
132 }
133 return (a->adr > b->adr) ? 1 : -1;
134 }
135
136 int
137 cmp_memory(MemoryPtr a,MemoryPtr b)
138 {
139 int r;
140 while(1) {
141 if ((r=cmp_memory1(a,b))) return r;
142 if (a->left && b->left) {
143 if ((r=cmp_memory(a->left,b->left))) return r;
144 } else if (a->left || b->left) {
145 return (a->left > b->left)? 1 : -1;
146 }
147 if (a->right && b->right) {
148 a = a->right; b = b->right;
149 // recursive loop
150 } else if (a->right || b->right) {
151 return (a->right > b->right)? 1 : -1;
152 } else {
153 return 0; // singleton
154 }
155 }
156 }
157
158 /*
159 Make a copy of real memory fragments
160 */
161
162 MemoryPtr
163 copy_memory1(MemoryPtr m)
164 {
165 MemoryPtr new = create_memory(m->adr,m->length);
166 void *p = (void *)malloc(m->length);
167 if (!p) {
168 die_exit("can't alloc memory body");
169 return 0;
170 }
171 #if MEMORY_REPORT
172 memory_body += m->length;
173 #endif
174 memcpy(p,m->adr,m->length);
175 m->body = new->body = p; // abondon original memory pattern
176 new->hash = m->hash;
177 return new;
178 }
179
180 MemoryPtr
181 copy_memory(MemoryPtr m, MemoryPtr *db)
182 {
183 MemoryPtr new, out;
184 if (!m) return m;
185 new = create_memory(m->adr,m->length);
186 new->hash = m->hash;
187 // look up is necessary to share its memory pattern
188 memory_lookup(new, db, copy_memory1, &out);
189 if (m->left) new->left = copy_memory(m->left, db);
190 if (m->right) new->right = copy_memory(m->right, db);
191 return new;
192 }
193
194 /*
195 restore copied memory save to the original addresses
196 */
197
198 void
199 restore_memory(MemoryPtr m)
200 {
201 while (m) {
202 memcpy(m->adr,m->body,m->length);
203 #if MEMORY_REPORT
204 restore_count ++;
205 restore_size += m->length;
206 #endif
207 if (m->left) restore_memory(m->left);
208 m = m->right;
209 }
210 }
211
212
213 /*
214 get hash for all memeory fragments
215 initial value of hash should be zero
216 */
217
218 int
219 get_memory_hash(MemoryPtr m, int hash)
220 {
221 if (!m) return hash;
222 compute_memory_hash1(m);
223 if (m->left) hash = get_memory_hash(m->left, hash);
224 if (m->right) return get_memory_hash(m->right, hash);
225 return m->hash | hash;
226 }
227
228 /*
229 add modified memory fragments to the pattern database
230 */
231
232 MemoryPtr
233 add_memory(void *ptr,int length, MemoryPtr *parent)
234 {
235 Memory m, *out;
236 m.adr = m.body = ptr;
237 m.length = length;
238 m.left = m.right = 0;
239 compute_memory_hash1(&m);
240
241 memory_lookup(&m, parent, copy_memory1, &out);
242 return out;
243 }
244
245 int
246 memory_lookup(MemoryPtr m, MemoryPtr *parent,
247 MemoryPtr (*new_memory)(MemoryPtr), MemoryPtr *out)
248 {
249 MemoryPtr db;
250 int r;
251
252 while(1) {
253 db = *parent;
254 if (!db) {
255 /* not found */
256 if (new_memory && out) {
257 db = new_memory(m);
258 db->left = db->right = 0;
259 *out = *parent = db;
260 }
261 return 0;
262 }
263 if(!(r = cmp_memory1(m,db))) {
264 /* bingo */
265 if (out) {
266 *out = db;
267 }
268 return 1;
269 } else if (r>0) {
270 parent = &db->left;
271 } else if (r<0) {
272 parent = &db->right;
273 }
274 }
275 /* !NOT REACHED */
276 }
277
278 /*
279 memory range list management for state registration
280 this list points the real memory
281 */
282
283 MemoryPtr
284 add_memory_range(void *ptr,int length, MemoryPtr *parent)
285 {
286 Memory m, *out;
287 m.adr = ptr;
288 m.length = length;
289 m.left = m.right = 0;
290
291 memory_range_lookup(&m, parent, &out);
292 return out;
293 }
294
295 static int
296 cmp_range(MemoryPtr a,MemoryPtr b)
297 {
298 if (a->adr==b->adr) {
299 if (a->length != b->length)
300 die_exit("memory range inconsitency");
301 return 0;
302 }
303 return (a->adr > b->adr) ? 1 : -1;
304 }
305
306 int
307 memory_range_lookup(MemoryPtr m, MemoryPtr *parent, MemoryPtr *out)
308 {
309 MemoryPtr db;
310 int r;
311
312 while(1) {
313 db = *parent;
314 if (!db) {
315 /* not found */
316 if (out) {
317 db = create_memory(m->adr, m->length);
318 *out = *parent = db;
319 }
320 #if MEMORY_REPORT
321 range_count++;
322 range_size+=m->length;
323 #endif
324 return 0;
325 }
326 if(!(r = cmp_range(m,db))) {
327 /* bingo (actually an error) */
328 if (out) {
329 *out = db;
330 }
331 return 1;
332 } else if (r>0) {
333 parent = &db->left;
334 } else if (r<0) {
335 parent = &db->right;
336 }
337 }
338 /* !NOT REACHED */
339 }
340
341 /*
342 */
343
344 void
345 memory_usage()
346 {
347 #if MEMORY_REPORT
348 printf(" memory_header %d\n",memory_header);
349 printf(" memcmp_count %d\n",memcmp_count);
350 printf(" memory_body %d\n",memory_body);
351 printf(" restore_count %d\n",restore_count);
352 printf(" restore_size %d\n",restore_size);
353 printf(" range_count %d\n",range_count);
354 printf(" range_size %d\n",range_size);
355 #endif
356 }
357
358
359 /* end */