Fossil

Check-in [ef8266b7]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Implementation of a linked list to solve the memory leak described in a TODO in [e2ebb1f5cae8].

This code is slower than having the memory leak, and at the end, it was not a big memory leak. Let's say, 10 byte per revision involved in a file annotate. If a file has 30000 revisions, it may go around 300KB then.

For this leak to be noticeable (as we have a content cache until 50MB), it would mean having above a milion revisions for the file annotated.

So, I keep this in a branch apart, as maybe the leak is worth the faster code. I have not measured the speed difference though.

Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | label_linkedlist
Files: files | file ages | folders
SHA1: ef8266b710505ed189f1d016aff319fabcbd8acf
User & Date: viriketo 2011-09-04 22:14:43
Original Comment: Implementation of a linked list to solve the memory leak described in a TODO in [e2ebb1f5cae8]
Context
2011-09-06
20:30
Documenting the Label structure I introduced. Closed-Leaf check-in: 58a02a2e user: viriketo tags: label_linkedlist
2011-09-04
22:14
Implementation of a linked list to solve the memory leak described in a TODO in [e2ebb1f5cae8].

This code is slower than having the memory leak, and at the end, it was not a big memory leak. Let's say, 10 byte per revision involved in a file annotate. If a file has 30000 revisions, it may go around 300KB then.

For this leak to be noticeable (as we have a content cache until 50MB), it would mean having above a milion revisions for the file annotated.

So, I keep this in a branch apart, as maybe the leak is worth the faster code. I have not measured the speed difference though. check-in: ef8266b7 user: viriketo tags: label_linkedlist

21:39
Reducing the leak of annotate even more.

I wrote a TODO in the file, for a leak still present and relevant for files modified by many versions, but that requires harder work to get right. check-in: e2ebb1f5 user: viriketo tags: annotate_noleak

Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/diff.c.

622
623
624
625
626
627
628







629
630
631
632
633
634
635
636
637
638
639
640
641
642

643
644
645
646
647
648
649
...
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
...
696
697
698
699
700
701
702
703
704









705

706
707
708
709
710
711
712
...
737
738
739
740
741
742
743

744
745







746
747
748
749
750
751
752
753








754
755
756
757
758
759
760
...
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
...
806
807
808
809
810
811
812





813
814
815
816
817
818
819
820

821
822
823
824
825


826
827
828
829
830
831
832
...
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
...
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945







946

*/

/*
** The status of an annotation operation is recorded by an instance
** of the following structure.
*/
typedef struct Annotator Annotator;







struct Annotator {
  DContext c;       /* The diff-engine context */
  struct AnnLine {  /* Lines of the original files... */
    const char *z;       /* The text of the line */
    short int n;         /* Number of bytes (omitting trailing space and \n) */
    short int iLevel;    /* Level at which tag was set */
    const char *zSrc;    /* Tag showing origin of this line */
  } *aOrig;
  int nOrig;        /* Number of elements in aOrig[] */
  int nNoSrc;       /* Number of entries where aOrig[].zSrc==NULL */
  int iLevel;       /* Current level */
  int nVers;        /* Number of versions analyzed */
  char **azVers;    /* Names of versions analyzed */
  Blob toAnnotate;

};

/*
** Initialize the annotation process by specifying the file that is
** to be annotated.  The annotator takes control of the input Blob and
** will release it when it is finished with it.
*/
................................................................................
/*
** The input pParent is the next most recent ancestor of the file
** being annotated.  Do another step of the annotation.  Return true
** if additional annotation is required.  zPName is the tag to insert
** on each line of the file being annotated that was contributed by
** pParent.  Memory to hold zPName is leaked.
*/
static int annotation_step(Annotator *p, Blob *pParent, char *zPName){
  int i, j;
  int lnTo;
  int iPrevLevel;
  int iThisLevel;

  /* Prepare the parent file to be diffed */
  p->c.aFrom = break_into_lines(blob_str(pParent), blob_size(pParent),
................................................................................
  iPrevLevel = p->iLevel;
  p->iLevel++;
  iThisLevel = p->iLevel;
  for(i=lnTo=0; i<p->c.nEdit; i+=3){
    struct AnnLine *x = &p->aOrig[lnTo];
    for(j=0; j<p->c.aEdit[i]; j++, lnTo++, x++){
      if( x->zSrc==0 || x->iLevel==iPrevLevel ){
         /* TODO: handle zPName so we can free labels
          * if they get totally unreferenced in the Annotator */









         x->zSrc = zPName;

         x->iLevel = iThisLevel;
      }
    }
    lnTo += p->c.aEdit[i+2];
  }

  /* Clear out the diff results */
................................................................................
  memset(&x, 0, sizeof(x));
  x.toAnnotate = empty_blob;
  content_get(name_to_rid(g.argv[2]), &x.toAnnotate);
  if( annotation_start(&x) ){
    fossil_fatal("binary file");
  }
  for(i=3; i<g.argc; i++){

    blob_zero(&b);
    content_get(name_to_rid(g.argv[i]), &b);







    if( annotation_step(&x, &b, g.argv[i-1]) ){
      fossil_fatal("binary file");
    }
  }
  for(i=0; i<x.nOrig; i++){
    const char *zSrc = x.aOrig[i].zSrc;
    if( zSrc==0 ) zSrc = g.argv[g.argc-1];
    fossil_print("%10s: %.*s\n", zSrc, x.aOrig[i].n, x.aOrig[i].z);








  }
}

/* Annotation flags */
#define ANN_FILE_VERS  0x001  /* Show file version rather than commit version */

/*
................................................................................
  int mid,             /* Use the version of the file in this check-in */
  int webLabel,        /* Use web-style annotations if true */
  int iLimit,          /* Limit the number of levels if greater than zero */
  int annFlags         /* Flags to alter the annotation */
){
  Blob step = empty_blob;           /* Text of previous revision */
  int rid;             /* Artifact ID of the file being annotated */
  char *zLabel;        /* Label to apply to a line */
  Stmt q;              /* Query returning all ancestor versions */

  /* Initialize the annotation */
  rid = db_int(0, "SELECT fid FROM mlink WHERE mid=%d AND fnid=%d",mid,fnid);
  if( rid==0 ){
    fossil_panic("file #%d is unchanged in manifest #%d", fnid, mid);
  }
................................................................................
    iLimit>0 ? iLimit : 10000000
  );
  while( db_step(&q)==SQLITE_ROW ){
    int pid = db_column_int(&q, 0);
    const char *zUuid = db_column_text(&q, 1);
    const char *zDate = db_column_text(&q, 2);
    const char *zUser = db_column_text(&q, 3);





    if( webLabel ){
      zLabel = mprintf(
          "<a href='%s/info/%s' target='infowindow'>%.10s</a> %s %9.9s", 
          g.zTop, zUuid, zUuid, zDate, zUser
      );
    }else{
      zLabel = mprintf("%.10s %s %9.9s", zUuid, zDate, zUser);
    }

    p->nVers++;
    p->azVers = fossil_realloc(p->azVers, p->nVers*sizeof(p->azVers[0]) );
    p->azVers[p->nVers-1] = zLabel;
    content_get(pid, &step);
    annotation_step(p, &step, zLabel);


    blob_reset(&step);
  }
  db_finalize(&q);
  free(p->c.aTo);
}

/*
................................................................................
  if( P("filevers") ) annFlags |= ANN_FILE_VERS;
  annotate_file(&ann, fnid, mid, g.okHistory, iLimit, annFlags);
  if( P("log") ){
    int i;
    @ <h2>Versions analyzed:</h2>
    @ <ol>
    for(i=0; i<ann.nVers; i++){
      @ <li><tt>%s(ann.azVers[i])</tt></li>
    }
    @ </ol>
    @ <hr>
    @ <h2>Annotation:</h2>
  }
  @ <pre>
  for(i=0; i<ann.nOrig; i++){
    ((char*)ann.aOrig[i].z)[ann.aOrig[i].n] = 0;
    @ %s(ann.aOrig[i].zSrc): %h(ann.aOrig[i].z)
  }
  @ </pre>
  style_footer();
}

/*
** COMMAND: annotate
................................................................................
  if( mid==0 ){
    fossil_panic("unable to find manifest");
  }
  if( fileVers ) annFlags |= ANN_FILE_VERS;
  annotate_file(&ann, fnid, mid, 0, iLimit, annFlags);
  if( showLog ){
    for(i=0; i<ann.nVers; i++){
      printf("version %3d: %s\n", i+1, ann.azVers[i]);
    }
    printf("---------------------------------------------------\n");
  }
  for(i=0; i<ann.nOrig; i++){
    fossil_print("%s: %.*s\n", 
                 ann.aOrig[i].zSrc, ann.aOrig[i].n, ann.aOrig[i].z);
  }
  free(ann.azVers);
  free(ann.aOrig);
  blob_reset(&ann.toAnnotate);







}








>
>
>
>
>
>
>






|





|

>







 







|







 







|
<
>
>
>
>
>
>
>
>
>

>







 







>


>
>
>
>
>
>
>
|




|


>
>
>
>
>
>
>
>







 







<







 







>
>
>
>
>

|




|

>


|

|
>
>







 







|








|







 







|





|




>
>
>
>
>
>
>
|
>
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
...
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
...
704
705
706
707
708
709
710
711

712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
...
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
...
801
802
803
804
805
806
807

808
809
810
811
812
813
814
...
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
...
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
...
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
*/

/*
** The status of an annotation operation is recorded by an instance
** of the following structure.
*/
typedef struct Annotator Annotator;
struct Label
{
    struct Label *prev;
    struct Label *next;
    char *str;
    int nref;
};
struct Annotator {
  DContext c;       /* The diff-engine context */
  struct AnnLine {  /* Lines of the original files... */
    const char *z;       /* The text of the line */
    short int n;         /* Number of bytes (omitting trailing space and \n) */
    short int iLevel;    /* Level at which tag was set */
    struct Label *zSrc;    /* Tag showing origin of this line */
  } *aOrig;
  int nOrig;        /* Number of elements in aOrig[] */
  int nNoSrc;       /* Number of entries where aOrig[].zSrc==NULL */
  int iLevel;       /* Current level */
  int nVers;        /* Number of versions analyzed */
  struct Label **azVers;    /* Names of versions analyzed */
  Blob toAnnotate;
  struct Label *firstLabel;
};

/*
** Initialize the annotation process by specifying the file that is
** to be annotated.  The annotator takes control of the input Blob and
** will release it when it is finished with it.
*/
................................................................................
/*
** The input pParent is the next most recent ancestor of the file
** being annotated.  Do another step of the annotation.  Return true
** if additional annotation is required.  zPName is the tag to insert
** on each line of the file being annotated that was contributed by
** pParent.  Memory to hold zPName is leaked.
*/
static int annotation_step(Annotator *p, Blob *pParent, struct Label *zPName){
  int i, j;
  int lnTo;
  int iPrevLevel;
  int iThisLevel;

  /* Prepare the parent file to be diffed */
  p->c.aFrom = break_into_lines(blob_str(pParent), blob_size(pParent),
................................................................................
  iPrevLevel = p->iLevel;
  p->iLevel++;
  iThisLevel = p->iLevel;
  for(i=lnTo=0; i<p->c.nEdit; i+=3){
    struct AnnLine *x = &p->aOrig[lnTo];
    for(j=0; j<p->c.aEdit[i]; j++, lnTo++, x++){
      if( x->zSrc==0 || x->iLevel==iPrevLevel ){
         if (x->zSrc!=0)

         {
           if(--x->zSrc->nref == 0)
           {
               free(x->zSrc->str);
               x->zSrc->prev->next = x->zSrc->next;
               x->zSrc->next->prev = x->zSrc->prev;
               free(x->zSrc);
           }
         }
         x->zSrc = zPName;
         ++zPName->nref;
         x->iLevel = iThisLevel;
      }
    }
    lnTo += p->c.aEdit[i+2];
  }

  /* Clear out the diff results */
................................................................................
  memset(&x, 0, sizeof(x));
  x.toAnnotate = empty_blob;
  content_get(name_to_rid(g.argv[2]), &x.toAnnotate);
  if( annotation_start(&x) ){
    fossil_fatal("binary file");
  }
  for(i=3; i<g.argc; i++){
    struct Label *l;
    blob_zero(&b);
    content_get(name_to_rid(g.argv[i]), &b);
    l = fossil_malloc(sizeof(*l));
    l->str = g.argv[i-1];
    l->nref = 0;
    l->next = x.firstLabel;
    if (x.firstLabel)
      x.firstLabel->prev = l;
    x.firstLabel = l;
    if( annotation_step(&x, &b, l) ){
      fossil_fatal("binary file");
    }
  }
  for(i=0; i<x.nOrig; i++){
    const char *zSrc = x.aOrig[i].zSrc->str;
    if( zSrc==0 ) zSrc = g.argv[g.argc-1];
    fossil_print("%10s: %.*s\n", zSrc, x.aOrig[i].n, x.aOrig[i].z);
  }
  while(x.firstLabel) {
    struct Label *l;
    l = x.firstLabel->next;
    assert(x.firstLabel->nref > 0);
    free(x.firstLabel->str);
    free(x.firstLabel);
    x.firstLabel = l;
  }
}

/* Annotation flags */
#define ANN_FILE_VERS  0x001  /* Show file version rather than commit version */

/*
................................................................................
  int mid,             /* Use the version of the file in this check-in */
  int webLabel,        /* Use web-style annotations if true */
  int iLimit,          /* Limit the number of levels if greater than zero */
  int annFlags         /* Flags to alter the annotation */
){
  Blob step = empty_blob;           /* Text of previous revision */
  int rid;             /* Artifact ID of the file being annotated */

  Stmt q;              /* Query returning all ancestor versions */

  /* Initialize the annotation */
  rid = db_int(0, "SELECT fid FROM mlink WHERE mid=%d AND fnid=%d",mid,fnid);
  if( rid==0 ){
    fossil_panic("file #%d is unchanged in manifest #%d", fnid, mid);
  }
................................................................................
    iLimit>0 ? iLimit : 10000000
  );
  while( db_step(&q)==SQLITE_ROW ){
    int pid = db_column_int(&q, 0);
    const char *zUuid = db_column_text(&q, 1);
    const char *zDate = db_column_text(&q, 2);
    const char *zUser = db_column_text(&q, 3);
    struct Label *l = fossil_malloc(sizeof(*l));
    l->nref = 0;
    l->next = p->firstLabel;
    if (p->firstLabel)
      p->firstLabel->prev = l;
    if( webLabel ){
      l->str = mprintf(
          "<a href='%s/info/%s' target='infowindow'>%.10s</a> %s %9.9s", 
          g.zTop, zUuid, zUuid, zDate, zUser
      );
    }else{
      l->str = mprintf("%.10s %s %9.9s", zUuid, zDate, zUser);
    }
    p->firstLabel = l;
    p->nVers++;
    p->azVers = fossil_realloc(p->azVers, p->nVers*sizeof(p->azVers[0]) );
    p->azVers[p->nVers-1] = l;
    content_get(pid, &step);
    annotation_step(p, &step, l);
    if (l->nref == 0)
      free(l->str);
    blob_reset(&step);
  }
  db_finalize(&q);
  free(p->c.aTo);
}

/*
................................................................................
  if( P("filevers") ) annFlags |= ANN_FILE_VERS;
  annotate_file(&ann, fnid, mid, g.okHistory, iLimit, annFlags);
  if( P("log") ){
    int i;
    @ <h2>Versions analyzed:</h2>
    @ <ol>
    for(i=0; i<ann.nVers; i++){
      @ <li><tt>%s(ann.azVers[i]->str)</tt></li>
    }
    @ </ol>
    @ <hr>
    @ <h2>Annotation:</h2>
  }
  @ <pre>
  for(i=0; i<ann.nOrig; i++){
    ((char*)ann.aOrig[i].z)[ann.aOrig[i].n] = 0;
    @ %s(ann.aOrig[i].zSrc->str): %h(ann.aOrig[i].z)
  }
  @ </pre>
  style_footer();
}

/*
** COMMAND: annotate
................................................................................
  if( mid==0 ){
    fossil_panic("unable to find manifest");
  }
  if( fileVers ) annFlags |= ANN_FILE_VERS;
  annotate_file(&ann, fnid, mid, 0, iLimit, annFlags);
  if( showLog ){
    for(i=0; i<ann.nVers; i++){
      printf("version %3d: %s\n", i+1, ann.azVers[i]->str);
    }
    printf("---------------------------------------------------\n");
  }
  for(i=0; i<ann.nOrig; i++){
    fossil_print("%s: %.*s\n", 
                 ann.aOrig[i].zSrc->str, ann.aOrig[i].n, ann.aOrig[i].z);
  }
  free(ann.azVers);
  free(ann.aOrig);
  blob_reset(&ann.toAnnotate);
  while(ann.firstLabel) {
    struct Label *l;
    l = ann.firstLabel->next;
    assert(ann.firstLabel->nref > 0);
    free(ann.firstLabel->str);
    free(ann.firstLabel);
    ann.firstLabel = l;
  }
}