1 /* vmlog - high-speed logging for free VMs */
2 /* Copyright (C) 2006 Edwin Steiner <edwin.steiner@gmx.net> */
4 /* This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
32 #define VMLOGDIFF_RINGBUF_SIZE 1024*1024
33 #define VMLOGDIFF_PREFETCH 256
37 #define LOG(args) printf args
42 typedef struct vmlogdiff_removed vmlogdiff_removed;
44 struct vmlogdiff_removed {
56 char *g_cleanedfname[2] = { "vmlogdiff.A.clean", "vmlogdiff.B.clean" };
57 char *g_removedfname[2] = { "vmlogdiff.A.removed", "vmlogdiff.B.removed" };
61 char *g_indentation = " ";
62 vmlog_seq_t g_context_available = 0;
63 vmlog_seq_t g_context_requested = 0;
65 vmlog_string_entry *g_idxmap;
67 vmlogdiff_removed *g_removedmap[2];
68 vmlogdiff_removed *g_removedptr[2];
69 vmlogdiff_removed *g_removedend[2];
72 vmlog_seq_t g_showseq[2] = { 0 };
76 vmlog_ringbuf *g_ringbuf[2] = { NULL };
77 vmlog_ringbuf *g_ringbuf_back[2] = { NULL };
78 vmlog_ringbuf *g_ringbuf_show[2] = { NULL };
79 vmlog_ringbuf *g_ringbuf_orig[2] = { NULL };
82 "Usage: vmlogdiff [options] prefix fileA fileB\n"
85 " -h display this help message\n"
86 " -v verbose messages to stderr\n"
89 /* global variables for diff algorithm */
92 vmlog_seq_t *g_Vforw_buf = NULL;
93 vmlog_seq_t *g_Vback_buf = NULL;
94 vmlog_seq_t *g_Vforw = NULL;
95 vmlog_seq_t *g_Vback = NULL;
99 char *g_index_used = NULL;
101 static void compare(vmlog_seq_t xstart,vmlog_seq_t ystart,vmlog_seq_t xend,vmlog_seq_t yend);
103 static void diff_alloc(int maxD)
108 VMLOG_FREE_ARRAY(vmlog_seq_t,g_Vsize,g_Vforw_buf);
109 VMLOG_FREE_ARRAY(vmlog_seq_t,g_Vsize,g_Vback_buf);
113 g_Vsize = 2 * g_maxD + 1;
115 g_Vforw_buf = VMLOG_NEW_ARRAY(vmlog_seq_t,g_Vsize);
116 g_Vback_buf = VMLOG_NEW_ARRAY(vmlog_seq_t,g_Vsize);
118 g_Vforw = g_Vforw_buf + g_maxD;
119 g_Vback = g_Vback_buf + g_maxD;
122 void parse_command_line(int argc,char **argv)
127 r = getopt(argc,argv,"hv");
132 vmlog_die_usage(usage,0);
139 vmlog_die_usage(usage,1);
143 if (argc - optind < 3)
144 vmlog_die_usage(usage,1);
146 opt_prefix = argv[optind++];
147 opt_fname[0] = argv[optind++];
148 opt_fname[1] = argv[optind++];
151 static void fprint_string(FILE *file,int index)
154 vmlog_string_entry *strent;
157 strent = g_idxmap + index;
158 str = g_strmap + strent->ofs;
160 buf = VMLOG_NEW_ARRAY(char,strent->len+1);
162 memcpy(buf,str,strent->len);
163 buf[strent->len] = 0;
167 VMLOG_FREE_ARRAY(char,strent->len+1,buf);
170 static void dump_log_entry(vmlog_log_entry *logent,int depth)
173 fprintf(stdout,"%d",depth);
180 for (i=0; i<depth; ++i)
181 fputs(g_indentation,stdout);
183 switch(logent->tag) {
184 case VMLOG_TAG_ENTER: fputs("enter ",stdout); break;
185 case VMLOG_TAG_LEAVE: fputs("leave ",stdout); break;
186 case VMLOG_TAG_THROW: fputs("throw ",stdout); break;
187 case VMLOG_TAG_CATCH: fputs("catch ",stdout); break;
188 case VMLOG_TAG_UNWND: fputs("unwnd ",stdout); break;
190 fprint_string(stdout,logent->index);
194 static void show_context(void)
197 vmlog_log_entry *logent;
200 if (g_context_available > 2*opt_context) {
201 skipped = g_context_available - 2*opt_context;
202 printf("@@ " VMLOG_SEQ_FMT " common entr%s skipped @@\n",skipped,(skipped > 1) ? "ies" : "y");
203 g_context_available = opt_context;
207 if (len > g_context_available) {
208 len = g_context_available;
214 vmlog_ringbuf_seek(g_ringbuf_show[0],g_ringbuf_show[0]->seq - len);
215 while (len-- && (logent = vmlog_ringbuf_next(g_ringbuf_show[0],VMLOGDIFF_PREFETCH))) {
217 dump_log_entry(logent,0);
218 g_context_available--;
222 static void handle_unmatchable(int which,vmlogdiff_removed *rm)
225 vmlog_log_entry *logent;
227 LOG(("unmatchable, only in %d: ofs=%lld len=%lld\n",which,rm->start,rm->len));
233 vmlog_ringbuf_seek(g_ringbuf_orig[which],rm->start);
234 for (i=0; i<rm->len; ++i) {
235 logent = vmlog_ringbuf_next(g_ringbuf_orig[which],1 /* XXX */);
236 fputc((which) ? '+' : '-',stdout);
237 dump_log_entry(logent,0);
240 g_context_requested = opt_context;
241 g_context_available = 0;
244 static void handle_common(vmlog_seq_t xstart,vmlog_seq_t ystart,vmlog_seq_t len)
248 vmlog_log_entry *logent;
250 LOG(("common: x=%lld y=%lld len=%lld\n",xstart,ystart,len));
252 vmlog_ringbuf_seek(g_ringbuf_show[0],xstart);
253 for (i=0; i<len; ++i) {
254 for (j=0; j<2; ++j) {
255 if (g_removedptr[j] < g_removedend[j] && g_showseq[j] == g_removedptr[j]->start) {
256 handle_unmatchable(j,g_removedptr[j]);
257 g_showseq[j] += g_removedptr[j]->len;
262 logent = vmlog_ringbuf_next(g_ringbuf_show[0],VMLOGDIFF_PREFETCH);
263 if (g_context_requested) {
265 dump_log_entry(logent,0);
266 g_context_requested--;
267 assert(!g_context_available);
270 g_context_available++;
278 static void handle_only_in(int which,vmlog_seq_t start,vmlog_seq_t len)
281 vmlog_log_entry *logent;
283 LOG(("only in %d: ofs=%lld len=%lld\n",which,start,len));
289 vmlog_ringbuf_seek(g_ringbuf_show[which],start);
290 for (i=0; i<len; ++i) {
291 if (g_removedptr[which] < g_removedend[which] && g_showseq[which] == g_removedptr[which]->start) {
292 handle_unmatchable(which,g_removedptr[which]);
293 g_showseq[which] += g_removedptr[which]->len;
294 g_removedptr[which]++;
296 logent = vmlog_ringbuf_next(g_ringbuf_show[which],1 /* XXX */);
297 fputc((which) ? '+' : '-',stdout);
298 dump_log_entry(logent,0);
303 g_context_requested = opt_context;
304 g_context_available = 0;
307 static vmlog_seq_t match_forward(vmlog_seq_t x,vmlog_seq_t y,vmlog_seq_t xend,vmlog_seq_t yend)
309 vmlog_log_entry *enta;
310 vmlog_log_entry *entb;
313 if (x >= xend || y >= yend)
317 vmlog_ringbuf_seek(g_ringbuf[0],x);
318 vmlog_ringbuf_seek(g_ringbuf[1],y);
321 enta = vmlog_ringbuf_next(g_ringbuf[0],VMLOGDIFF_PREFETCH);
322 entb = vmlog_ringbuf_next(g_ringbuf[1],VMLOGDIFF_PREFETCH);
323 assert(enta && entb);
325 if (enta->index != entb->index || enta->tag != entb->tag)
328 /* a diagonal edge in the edit graph */
331 } while (x < xend && y < yend);
336 static vmlog_seq_t match_backward(vmlog_seq_t xstart,vmlog_seq_t ystart,vmlog_seq_t x,vmlog_seq_t y)
338 vmlog_log_entry *enta;
339 vmlog_log_entry *entb;
342 if (x <= xstart || y <= ystart)
346 vmlog_ringbuf_seek(g_ringbuf_back[0],x);
347 vmlog_ringbuf_seek(g_ringbuf_back[1],y);
350 enta = vmlog_ringbuf_prev(g_ringbuf_back[0],VMLOGDIFF_PREFETCH);
351 entb = vmlog_ringbuf_prev(g_ringbuf_back[1],VMLOGDIFF_PREFETCH);
352 assert(enta && entb);
354 if (enta->index != entb->index || enta->tag != entb->tag)
357 /* a diagonal edge in the edit graph */
360 } while (x > xstart && y > ystart);
365 /* pre-condition: X and Y differ at both ends */
367 static void find_middle_snake(vmlog_seq_t xstart,vmlog_seq_t ystart,vmlog_seq_t xend,vmlog_seq_t yend)
373 vmlog_seq_t rdiagofs;
376 vmlog_seq_t snakex,snakey;
377 vmlog_seq_t snakestartx = 0;
378 vmlog_seq_t snakestarty = 0;
379 vmlog_seq_t snakelen = 0;
381 vmlog_seq_t best_forward;
382 vmlog_seq_t best_backward;
384 LOG(("find_middle_snake(%lld,%lld,%lld,%lld)\n",
385 xstart,ystart,xend,yend));
387 diagofs = ystart - xstart;
388 rdiagofs = yend - xend;
390 Delta = diagofs - rdiagofs;
392 /* fake vertical edge (0,-1) -> (0,0) ending on 0-diagonal */
395 /* fake vertical edge (N,M+1) -> (N,M) ending on 0-reverse-diagonal */
399 best_backward = xend;
401 for (D=0; D <= g_maxD; ++D) {
404 if (opt_verbose && D && (D % 1000 == 0))
405 fprintf(stderr,"%d. (" VMLOG_SEQ_FMT_W ":" VMLOG_SEQ_FMT_W " entries, " VMLOG_SEQ_FMT_W " left) D = %d\n",
406 g_level,xend-xstart,yend-ystart,best_backward - best_forward,D);
408 for (k = -D; k <= D; k += 2) {
409 LOG((" k = %d, forward\n",k));
411 /* we take a (D-1)-path that ends on a */
412 /* neighbouring diagonal and extend it with a */
413 /* vertical or horizontal edge (whichever takes */
416 if (k == -D || (k != +D && g_Vforw[k-1] < g_Vforw[k+1])) {
417 /* vertical edge from diagonal k+1 down to k */
421 /* horizontal edge from diagonal k-1 right to k */
422 x = g_Vforw[k-1] + 1;
425 /* calculate y using the k-diagonal equation */
429 /* append the trailing snake to the D-path */
434 match = match_forward(x,y,xend,yend);
439 LOG(("match from (%lld,%lld) to (%lld,%lld)\n",
440 snakex,snakey,x-1,y-1));
445 snakestartx = (xstart + xend) / 2;;
446 snakestarty = snakestartx;
447 if (snakestarty < ystart)
448 snakestarty = ystart;
449 else if (snakestarty > yend)
452 goto found_middle_snake;
455 /* this is the furthest reaching D-path on the k-diagonal */
458 if (x > best_forward)
461 LOG(("\tlongest %d-path on %d-diagonal ends at x=%lld\n",
464 /* check overlap with furthest reaching reverse D-1 path */
466 if ((Delta & 1) && k - Delta >= -(D-1) && k - Delta <= +(D-1)) {
467 if (x >= g_Vback[k - Delta]) {
468 LOG(("length of SES is %d\n",2*D - 1));
471 snakestartx = snakex;
472 snakestarty = snakey;
473 snakelen = x - snakex;
474 goto found_middle_snake;
479 for (k = -D; k <= +D; k += 2) {
481 LOG((" k = %d, backward\n",k));
483 /* we take a reverse (D-1)-path that ends on a */
484 /* neighbouring diagonal and extend it with a */
485 /* vertical or horizontal edge (whichever takes */
488 if (k == +D || (k != -D && g_Vback[k-1] < g_Vback[k+1])) {
489 /* vertical edge from reverse diagonal k-1 up to k */
493 /* horizontal edge from reverse diagonal k+1 left to k */
494 x = g_Vback[k+1] - 1;
497 /* calculate y using the k-reverse-diagonal equation */
499 y = x - k + rdiagofs;
501 /* append the trailing snake to the D-path */
505 match = match_backward(xstart,ystart,x,y);
510 LOG(("match from (%lld,%lld) to (%lld,%lld)\n",
511 x,y,snakex-1,snakey-1));
513 /* this is the furthest reaching reverse D-path on the k-diagonal */
516 if (x < best_backward)
519 LOG(("\tlongest reverse %d-path on %d-diagonal ends at x=%lld\n",
522 /* check overlap with forward reaching D path */
524 if (!(Delta & 1) && k + Delta >= -D && k + Delta <= +D) {
525 if (x <= g_Vforw[k + Delta]) {
526 LOG(("length of SES is %d\n",2*D));
531 snakelen = snakex - x;
532 goto found_middle_snake;
538 vmlog_die("length of shortest editing script is > %d\n",g_maxD);
541 if (opt_verbose && g_level == 0) {
542 fprintf(stderr,"shortest editing script D = %d\n",resultD);
547 compare(xstart,ystart,snakestartx,snakestarty);
549 LOG(("middle snake: x=%lld y=%lld len=%lld\n",
550 snakestartx,snakestarty,snakelen));
553 handle_common(snakestartx,snakestarty,snakelen);
556 compare(snakestartx + snakelen,snakestarty + snakelen,xend,yend);
560 vmlog_seq_t lendiff = (yend - ystart) - (xend - xstart);
562 LOG(("snakestartx=%lld snakestarty=%lld snakelen=%lld\n",
563 snakestartx,snakestarty,snakelen));
564 assert(snakelen == 0);
568 handle_only_in(1,ystart,lendiff);
571 handle_only_in(0,xstart,-lendiff);
576 static void compare(vmlog_seq_t xstart,vmlog_seq_t ystart,vmlog_seq_t xend,vmlog_seq_t yend)
580 vmlog_seq_t xdiffend;
581 vmlog_seq_t ydiffend;
583 LOG(("compare(%lld,%lld,%lld,%lld)\n",
584 xstart,ystart,xend,yend));
586 /* process and strip common prefix */
588 prefix = match_forward(xstart,ystart,xend,yend);
589 if (opt_verbose && g_level == 0) {
590 fprintf(stderr,"common prefix = " VMLOG_SEQ_FMT "\n",prefix);
593 handle_common(xstart,ystart,prefix);
598 /* strip common suffix */
600 suffix = match_backward(xstart,ystart,xend,yend);
601 if (opt_verbose && g_level == 0) {
602 fprintf(stderr,"common suffix = " VMLOG_SEQ_FMT "\n",suffix);
604 xdiffend = xend - suffix;
605 ydiffend = yend - suffix;
608 /* handle differences */
610 if (xstart < xdiffend || ystart < ydiffend) {
611 if (xstart == xdiffend) {
612 handle_only_in(1,ystart,ydiffend - ystart);
614 else if (ystart == ydiffend) {
615 handle_only_in(0,xstart,xdiffend - xstart);
618 find_middle_snake(xstart,ystart,xdiffend,ydiffend);
622 /* process common suffix */
625 handle_common(xdiffend,ydiffend,suffix);
629 static void unmatchable_entries(void)
631 vmlog_log_entry *logent;
638 vmlogdiff_removed removed;
640 VMLOG_XZNEW_ARRAY(g_index_used,char,g_nstrings);
642 for (i=0; i<2; ++i) {
645 vmlog_ringbuf_seek(g_ringbuf[i],0);
646 while ((logent = vmlog_ringbuf_next(g_ringbuf[i],VMLOGDIFF_PREFETCH))) {
647 g_index_used[logent->index] |= mark;
651 for (i=0; i<2; ++i) {
652 vmlog_file_open(&cleaned,g_cleanedfname[i],vmlogTruncateAppend);
653 vmlog_file_open(&seqs,g_removedfname[i],vmlogTruncateAppend);
655 vmlog_ringbuf_seek(g_ringbuf[i],0);
660 while ((logent = vmlog_ringbuf_next(g_ringbuf[i],VMLOGDIFF_PREFETCH))) {
661 if (g_index_used[logent->index] == 3) {
662 vmlog_file_append(&cleaned,logent,sizeof(vmlog_log_entry));
664 vmlog_file_append(&seqs,&removed,sizeof(vmlogdiff_removed));
666 removed.start = seq + 1;
675 vmlog_file_append(&seqs,&removed,sizeof(vmlogdiff_removed));
677 vmlog_file_close(&seqs);
678 vmlog_file_close(&cleaned);
681 fprintf(stderr,"removed " VMLOG_SEQ_FMT " unmatchable entries from %s\n",
682 count,g_ringbuf[i]->file.fname);
684 g_removedmap[i] = vmlog_file_mmap(g_removedfname[i],&(g_removedlen[i]));
685 g_nremoved[i] = g_removedlen[i] / sizeof(vmlogdiff_removed);
686 g_removedptr[i] = g_removedmap[i];
687 g_removedend[i] = g_removedmap[i] + g_nremoved[i];
691 static void diff_logs(void)
695 for (i=0; i<2; ++i) {
696 g_ringbuf[i] = vmlog_ringbuf_new(opt_fname[i],VMLOGDIFF_RINGBUF_SIZE);
699 unmatchable_entries();
702 for (i=0; i<2; ++i) {
703 g_ringbuf_orig[i] = g_ringbuf[i];
704 g_ringbuf[i] = vmlog_ringbuf_new(g_cleanedfname[i],VMLOGDIFF_RINGBUF_SIZE);
705 g_ringbuf_back[i] = vmlog_ringbuf_new(g_cleanedfname[i],VMLOGDIFF_RINGBUF_SIZE);
706 g_ringbuf_show[i] = vmlog_ringbuf_new(g_cleanedfname[i],VMLOGDIFF_RINGBUF_SIZE);
709 g_n[0] = g_ringbuf[0]->file.size / sizeof(vmlog_log_entry);
710 g_n[1] = g_ringbuf[1]->file.size / sizeof(vmlog_log_entry);
712 compare(0,0,g_n[0],g_n[1]);
715 int main(int argc,char **argv)
718 vmlog_set_progname(argv[0]);
719 parse_command_line(argc,argv);
721 g_idxfname = vmlog_concat3(opt_prefix,"",".idx",NULL);
722 g_strfname = vmlog_concat3(opt_prefix,"",".str",NULL);
724 g_idxmap = (vmlog_string_entry *) vmlog_file_mmap(g_idxfname,&g_idxlen);
725 g_nstrings = g_idxlen / sizeof(vmlog_string_entry);
726 g_strmap = (char *) vmlog_file_mmap(g_strfname,&g_strlen);
730 vmlog_ringbuf_free(g_ringbuf[0]);
731 vmlog_ringbuf_free(g_ringbuf[1]);
734 vmlog_file_munmap(g_strmap,g_strlen);
735 vmlog_file_munmap(g_idxmap,g_idxlen);
736 vmlog_file_munmap(g_removedmap[0],g_removedlen[0]);
737 vmlog_file_munmap(g_removedmap[1],g_removedlen[1]);
742 /* vim: noet ts=8 sw=8