[FFmpeg-devel,3/4] avformat/flvenc: Use array instead of linked list for index

Submitted by Andreas Rheinhardt on Oct. 25, 2019, 9:11 a.m.

Details

Message ID 20191025091147.5298-2-andreas.rheinhardt@gmail.com
State New
Headers show

Commit Message

Andreas Rheinhardt Oct. 25, 2019, 9:11 a.m.
Using a linked list had very much overhead (the pointer to the next
entry increased the size of the index entry struct from 16 to 24 bytes,
not to mention the overhead of having separate allocations), so it is
better to (re)allocate a continuous array for the index.

Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
---
 libavformat/flvenc.c | 58 +++++++++++++++-----------------------------
 1 file changed, 19 insertions(+), 39 deletions(-)

Comments

Michael Niedermayer Oct. 25, 2019, 8:44 p.m.
On Fri, Oct 25, 2019 at 11:11:46AM +0200, Andreas Rheinhardt wrote:
> Using a linked list had very much overhead (the pointer to the next
> entry increased the size of the index entry struct from 16 to 24 bytes,
> not to mention the overhead of having separate allocations), so it is
> better to (re)allocate a continuous array for the index.
> 
> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
> ---
>  libavformat/flvenc.c | 58 +++++++++++++++-----------------------------
>  1 file changed, 19 insertions(+), 39 deletions(-)
> 
> diff --git a/libavformat/flvenc.c b/libavformat/flvenc.c
> index 0e6c66a5ff..a2bd791c59 100644
> --- a/libavformat/flvenc.c
> +++ b/libavformat/flvenc.c
> @@ -74,7 +74,6 @@ typedef enum {
>  typedef struct FLVFileposition {
>      int64_t keyframe_position;
>      double keyframe_timestamp;
> -    struct FLVFileposition *next;
>  } FLVFileposition;
>  
>  typedef struct FLVContext {
> @@ -108,9 +107,9 @@ typedef struct FLVContext {
>      int acurframeindex;
>      int64_t keyframes_info_offset;
>  
> -    int64_t filepositions_count;
>      FLVFileposition *filepositions;
> -    FLVFileposition *head_filepositions;
> +    size_t filepositions_allocated;
> +    int64_t filepositions_count;
>  
>      AVCodecParameters *audio_par;
>      AVCodecParameters *video_par;
> @@ -549,27 +548,19 @@ static void flv_write_codec_header(AVFormatContext* s, AVCodecParameters* par, i
>  
>  static int flv_append_keyframe_info(AVFormatContext *s, FLVContext *flv, double ts, int64_t pos)
>  {
> -    FLVFileposition *position = av_malloc(sizeof(FLVFileposition));
> -
> -    if (!position) {
> -        av_log(s, AV_LOG_WARNING, "no mem for add keyframe index!\n");
> -        return AVERROR(ENOMEM);
> -    }
> -
> -    position->keyframe_timestamp = ts;
> -    position->keyframe_position = pos;
> -
> -    if (!flv->filepositions_count) {
> -        flv->filepositions = position;
> -        flv->head_filepositions = flv->filepositions;
> -        position->next = NULL;
> -    } else {
> -        flv->filepositions->next = position;
> -        position->next = NULL;
> -        flv->filepositions = flv->filepositions->next;
> +    if (flv->filepositions_count >= flv->filepositions_allocated) {
> +        void *pos = av_realloc_array(flv->filepositions,
> +                                     2 * flv->filepositions_allocated + 1,
> +                                     sizeof(*flv->filepositions));

can the 2* overflow ?
av_fast_realloc() would check for that
i wonder if a av_fast_realloc_array() would make sense

thx

[...]
James Almer Oct. 25, 2019, 8:57 p.m.
On 10/25/2019 5:44 PM, Michael Niedermayer wrote:
> On Fri, Oct 25, 2019 at 11:11:46AM +0200, Andreas Rheinhardt wrote:
>> Using a linked list had very much overhead (the pointer to the next
>> entry increased the size of the index entry struct from 16 to 24 bytes,
>> not to mention the overhead of having separate allocations), so it is
>> better to (re)allocate a continuous array for the index.
>>
>> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
>> ---
>>  libavformat/flvenc.c | 58 +++++++++++++++-----------------------------
>>  1 file changed, 19 insertions(+), 39 deletions(-)
>>
>> diff --git a/libavformat/flvenc.c b/libavformat/flvenc.c
>> index 0e6c66a5ff..a2bd791c59 100644
>> --- a/libavformat/flvenc.c
>> +++ b/libavformat/flvenc.c
>> @@ -74,7 +74,6 @@ typedef enum {
>>  typedef struct FLVFileposition {
>>      int64_t keyframe_position;
>>      double keyframe_timestamp;
>> -    struct FLVFileposition *next;
>>  } FLVFileposition;
>>  
>>  typedef struct FLVContext {
>> @@ -108,9 +107,9 @@ typedef struct FLVContext {
>>      int acurframeindex;
>>      int64_t keyframes_info_offset;
>>  
>> -    int64_t filepositions_count;
>>      FLVFileposition *filepositions;
>> -    FLVFileposition *head_filepositions;
>> +    size_t filepositions_allocated;
>> +    int64_t filepositions_count;
>>  
>>      AVCodecParameters *audio_par;
>>      AVCodecParameters *video_par;
>> @@ -549,27 +548,19 @@ static void flv_write_codec_header(AVFormatContext* s, AVCodecParameters* par, i
>>  
>>  static int flv_append_keyframe_info(AVFormatContext *s, FLVContext *flv, double ts, int64_t pos)
>>  {
>> -    FLVFileposition *position = av_malloc(sizeof(FLVFileposition));
>> -
>> -    if (!position) {
>> -        av_log(s, AV_LOG_WARNING, "no mem for add keyframe index!\n");
>> -        return AVERROR(ENOMEM);
>> -    }
>> -
>> -    position->keyframe_timestamp = ts;
>> -    position->keyframe_position = pos;
>> -
>> -    if (!flv->filepositions_count) {
>> -        flv->filepositions = position;
>> -        flv->head_filepositions = flv->filepositions;
>> -        position->next = NULL;
>> -    } else {
>> -        flv->filepositions->next = position;
>> -        position->next = NULL;
>> -        flv->filepositions = flv->filepositions->next;
>> +    if (flv->filepositions_count >= flv->filepositions_allocated) {
>> +        void *pos = av_realloc_array(flv->filepositions,
>> +                                     2 * flv->filepositions_allocated + 1,
>> +                                     sizeof(*flv->filepositions));
> 
> can the 2* overflow ?
> av_fast_realloc() would check for that
> i wonder if a av_fast_realloc_array() would make sense

av_fast_realloc() doesn't do any overflow check. It only checks that the
min_size argument is below the max allowed alloc size.

But i agree that using it preceded by a sanity check that ensures
something like "flv->filepositions_count + 1 <= INT_MAX /
sizeof(*flv->filepositions)" would be more adequate than
av_realloc_array() with 2*size steps.

> 
> thx
> 
> [...]
> 
> 
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> 
> To unsubscribe, visit link above, or email
> ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
>
Michael Niedermayer Oct. 25, 2019, 9:07 p.m.
On Fri, Oct 25, 2019 at 05:57:44PM -0300, James Almer wrote:
> On 10/25/2019 5:44 PM, Michael Niedermayer wrote:
> > On Fri, Oct 25, 2019 at 11:11:46AM +0200, Andreas Rheinhardt wrote:
> >> Using a linked list had very much overhead (the pointer to the next
> >> entry increased the size of the index entry struct from 16 to 24 bytes,
> >> not to mention the overhead of having separate allocations), so it is
> >> better to (re)allocate a continuous array for the index.
> >>
> >> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
> >> ---
> >>  libavformat/flvenc.c | 58 +++++++++++++++-----------------------------
> >>  1 file changed, 19 insertions(+), 39 deletions(-)
> >>
> >> diff --git a/libavformat/flvenc.c b/libavformat/flvenc.c
> >> index 0e6c66a5ff..a2bd791c59 100644
> >> --- a/libavformat/flvenc.c
> >> +++ b/libavformat/flvenc.c
> >> @@ -74,7 +74,6 @@ typedef enum {
> >>  typedef struct FLVFileposition {
> >>      int64_t keyframe_position;
> >>      double keyframe_timestamp;
> >> -    struct FLVFileposition *next;
> >>  } FLVFileposition;
> >>  
> >>  typedef struct FLVContext {
> >> @@ -108,9 +107,9 @@ typedef struct FLVContext {
> >>      int acurframeindex;
> >>      int64_t keyframes_info_offset;
> >>  
> >> -    int64_t filepositions_count;
> >>      FLVFileposition *filepositions;
> >> -    FLVFileposition *head_filepositions;
> >> +    size_t filepositions_allocated;
> >> +    int64_t filepositions_count;
> >>  
> >>      AVCodecParameters *audio_par;
> >>      AVCodecParameters *video_par;
> >> @@ -549,27 +548,19 @@ static void flv_write_codec_header(AVFormatContext* s, AVCodecParameters* par, i
> >>  
> >>  static int flv_append_keyframe_info(AVFormatContext *s, FLVContext *flv, double ts, int64_t pos)
> >>  {
> >> -    FLVFileposition *position = av_malloc(sizeof(FLVFileposition));
> >> -
> >> -    if (!position) {
> >> -        av_log(s, AV_LOG_WARNING, "no mem for add keyframe index!\n");
> >> -        return AVERROR(ENOMEM);
> >> -    }
> >> -
> >> -    position->keyframe_timestamp = ts;
> >> -    position->keyframe_position = pos;
> >> -
> >> -    if (!flv->filepositions_count) {
> >> -        flv->filepositions = position;
> >> -        flv->head_filepositions = flv->filepositions;
> >> -        position->next = NULL;
> >> -    } else {
> >> -        flv->filepositions->next = position;
> >> -        position->next = NULL;
> >> -        flv->filepositions = flv->filepositions->next;
> >> +    if (flv->filepositions_count >= flv->filepositions_allocated) {
> >> +        void *pos = av_realloc_array(flv->filepositions,
> >> +                                     2 * flv->filepositions_allocated + 1,
> >> +                                     sizeof(*flv->filepositions));
> > 
> > can the 2* overflow ?
> > av_fast_realloc() would check for that
> > i wonder if a av_fast_realloc_array() would make sense
> 
> av_fast_realloc() doesn't do any overflow check. It only checks that the
> min_size argument is below the max allowed alloc size.

it does this:
FFMAX(min_size + min_size / 16 + 32, min_size)

which should check for the overflow. min_size is a unsigned type so overflow
is defined so we can do it and check afterwards.

[...]
Andreas Rheinhardt Oct. 26, 2019, 3:04 a.m.
On Fri, Oct 25, 2019 at 10:44 PM Michael Niedermayer <michael@niedermayer.cc>
wrote:

> On Fri, Oct 25, 2019 at 11:11:46AM +0200, Andreas Rheinhardt wrote:
> > Using a linked list had very much overhead (the pointer to the next
> > entry increased the size of the index entry struct from 16 to 24 bytes,
> > not to mention the overhead of having separate allocations), so it is
> > better to (re)allocate a continuous array for the index.
> >
> > Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
> > ---
> >  libavformat/flvenc.c | 58 +++++++++++++++-----------------------------
> >  1 file changed, 19 insertions(+), 39 deletions(-)
> >
> > diff --git a/libavformat/flvenc.c b/libavformat/flvenc.c
> > index 0e6c66a5ff..a2bd791c59 100644
> > --- a/libavformat/flvenc.c
> > +++ b/libavformat/flvenc.c
> > @@ -74,7 +74,6 @@ typedef enum {
> >  typedef struct FLVFileposition {
> >      int64_t keyframe_position;
> >      double keyframe_timestamp;
> > -    struct FLVFileposition *next;
> >  } FLVFileposition;
> >
> >  typedef struct FLVContext {
> > @@ -108,9 +107,9 @@ typedef struct FLVContext {
> >      int acurframeindex;
> >      int64_t keyframes_info_offset;
> >
> > -    int64_t filepositions_count;
> >      FLVFileposition *filepositions;
> > -    FLVFileposition *head_filepositions;
> > +    size_t filepositions_allocated;
> > +    int64_t filepositions_count;
> >
> >      AVCodecParameters *audio_par;
> >      AVCodecParameters *video_par;
> > @@ -549,27 +548,19 @@ static void
> flv_write_codec_header(AVFormatContext* s, AVCodecParameters* par, i
> >
> >  static int flv_append_keyframe_info(AVFormatContext *s, FLVContext
> *flv, double ts, int64_t pos)
> >  {
> > -    FLVFileposition *position = av_malloc(sizeof(FLVFileposition));
> > -
> > -    if (!position) {
> > -        av_log(s, AV_LOG_WARNING, "no mem for add keyframe index!\n");
> > -        return AVERROR(ENOMEM);
> > -    }
> > -
> > -    position->keyframe_timestamp = ts;
> > -    position->keyframe_position = pos;
> > -
> > -    if (!flv->filepositions_count) {
> > -        flv->filepositions = position;
> > -        flv->head_filepositions = flv->filepositions;
> > -        position->next = NULL;
> > -    } else {
> > -        flv->filepositions->next = position;
> > -        position->next = NULL;
> > -        flv->filepositions = flv->filepositions->next;
> > +    if (flv->filepositions_count >= flv->filepositions_allocated) {
> > +        void *pos = av_realloc_array(flv->filepositions,
> > +                                     2 * flv->filepositions_allocated +
> 1,
> > +                                     sizeof(*flv->filepositions));
>
> can the 2* overflow ?
> av_fast_realloc() would check for that
> i wonder if a av_fast_realloc_array() would make sense
>
>
av_realloc_array checks that the multiplication doesn't overflow (it
actually checks that
the product fits in an int). Given that sizeof(*flv->filepositions) is
bigger than 2, no overflow
can happen in 2 * flv->filepositions_allocated + 1.

- Andreas
Michael Niedermayer Nov. 9, 2019, 5:15 p.m.
On Sat, Oct 26, 2019 at 05:04:20AM +0200, Andreas Rheinhardt wrote:
> On Fri, Oct 25, 2019 at 10:44 PM Michael Niedermayer <michael@niedermayer.cc>
> wrote:
> 
> > On Fri, Oct 25, 2019 at 11:11:46AM +0200, Andreas Rheinhardt wrote:
> > > Using a linked list had very much overhead (the pointer to the next
> > > entry increased the size of the index entry struct from 16 to 24 bytes,
> > > not to mention the overhead of having separate allocations), so it is
> > > better to (re)allocate a continuous array for the index.
> > >
> > > Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
> > > ---
> > >  libavformat/flvenc.c | 58 +++++++++++++++-----------------------------
> > >  1 file changed, 19 insertions(+), 39 deletions(-)
> > >
> > > diff --git a/libavformat/flvenc.c b/libavformat/flvenc.c
> > > index 0e6c66a5ff..a2bd791c59 100644
> > > --- a/libavformat/flvenc.c
> > > +++ b/libavformat/flvenc.c
> > > @@ -74,7 +74,6 @@ typedef enum {
> > >  typedef struct FLVFileposition {
> > >      int64_t keyframe_position;
> > >      double keyframe_timestamp;
> > > -    struct FLVFileposition *next;
> > >  } FLVFileposition;
> > >
> > >  typedef struct FLVContext {
> > > @@ -108,9 +107,9 @@ typedef struct FLVContext {
> > >      int acurframeindex;
> > >      int64_t keyframes_info_offset;
> > >
> > > -    int64_t filepositions_count;
> > >      FLVFileposition *filepositions;
> > > -    FLVFileposition *head_filepositions;
> > > +    size_t filepositions_allocated;
> > > +    int64_t filepositions_count;
> > >
> > >      AVCodecParameters *audio_par;
> > >      AVCodecParameters *video_par;
> > > @@ -549,27 +548,19 @@ static void
> > flv_write_codec_header(AVFormatContext* s, AVCodecParameters* par, i
> > >
> > >  static int flv_append_keyframe_info(AVFormatContext *s, FLVContext
> > *flv, double ts, int64_t pos)
> > >  {
> > > -    FLVFileposition *position = av_malloc(sizeof(FLVFileposition));
> > > -
> > > -    if (!position) {
> > > -        av_log(s, AV_LOG_WARNING, "no mem for add keyframe index!\n");
> > > -        return AVERROR(ENOMEM);
> > > -    }
> > > -
> > > -    position->keyframe_timestamp = ts;
> > > -    position->keyframe_position = pos;
> > > -
> > > -    if (!flv->filepositions_count) {
> > > -        flv->filepositions = position;
> > > -        flv->head_filepositions = flv->filepositions;
> > > -        position->next = NULL;
> > > -    } else {
> > > -        flv->filepositions->next = position;
> > > -        position->next = NULL;
> > > -        flv->filepositions = flv->filepositions->next;
> > > +    if (flv->filepositions_count >= flv->filepositions_allocated) {
> > > +        void *pos = av_realloc_array(flv->filepositions,
> > > +                                     2 * flv->filepositions_allocated +
> > 1,
> > > +                                     sizeof(*flv->filepositions));
> >
> > can the 2* overflow ?
> > av_fast_realloc() would check for that
> > i wonder if a av_fast_realloc_array() would make sense
> >
> >
> av_realloc_array checks that the multiplication doesn't overflow (it
> actually checks that
> the product fits in an int). Given that sizeof(*flv->filepositions) is
> bigger than 2, no overflow
> can happen in 2 * flv->filepositions_allocated + 1.

Iam unsure if that check by the type used in av_realloc_array() is a 
good idea but if you think its ok then please add a comment in the
code explaining this.

Thanks

[...]

Patch hide | download patch | download mbox

diff --git a/libavformat/flvenc.c b/libavformat/flvenc.c
index 0e6c66a5ff..a2bd791c59 100644
--- a/libavformat/flvenc.c
+++ b/libavformat/flvenc.c
@@ -74,7 +74,6 @@  typedef enum {
 typedef struct FLVFileposition {
     int64_t keyframe_position;
     double keyframe_timestamp;
-    struct FLVFileposition *next;
 } FLVFileposition;
 
 typedef struct FLVContext {
@@ -108,9 +107,9 @@  typedef struct FLVContext {
     int acurframeindex;
     int64_t keyframes_info_offset;
 
-    int64_t filepositions_count;
     FLVFileposition *filepositions;
-    FLVFileposition *head_filepositions;
+    size_t filepositions_allocated;
+    int64_t filepositions_count;
 
     AVCodecParameters *audio_par;
     AVCodecParameters *video_par;
@@ -549,27 +548,19 @@  static void flv_write_codec_header(AVFormatContext* s, AVCodecParameters* par, i
 
 static int flv_append_keyframe_info(AVFormatContext *s, FLVContext *flv, double ts, int64_t pos)
 {
-    FLVFileposition *position = av_malloc(sizeof(FLVFileposition));
-
-    if (!position) {
-        av_log(s, AV_LOG_WARNING, "no mem for add keyframe index!\n");
-        return AVERROR(ENOMEM);
-    }
-
-    position->keyframe_timestamp = ts;
-    position->keyframe_position = pos;
-
-    if (!flv->filepositions_count) {
-        flv->filepositions = position;
-        flv->head_filepositions = flv->filepositions;
-        position->next = NULL;
-    } else {
-        flv->filepositions->next = position;
-        position->next = NULL;
-        flv->filepositions = flv->filepositions->next;
+    if (flv->filepositions_count >= flv->filepositions_allocated) {
+        void *pos = av_realloc_array(flv->filepositions,
+                                     2 * flv->filepositions_allocated + 1,
+                                     sizeof(*flv->filepositions));
+        if (!pos) {
+            av_log(s, AV_LOG_WARNING, "No memory for keyframe index\n");
+            return AVERROR(ENOMEM);
+        }
+        flv->filepositions = pos;
+        flv->filepositions_allocated = 2 * flv->filepositions_allocated + 1;
     }
 
-    flv->filepositions_count++;
+    flv->filepositions[flv->filepositions_count++] = (FLVFileposition){ pos, ts };
 
     return 0;
 }
@@ -784,7 +775,7 @@  static int flv_write_trailer(AVFormatContext *s)
     int64_t cur_pos = avio_tell(s->pb);
 
     if (build_keyframes_idx) {
-        FLVFileposition *newflv_posinfo, *p;
+        FLVFileposition *flv_posinfo = flv->filepositions;
 
         avio_seek(pb, flv->videosize_offset, SEEK_SET);
         put_amf_double(pb, flv->videosize);
@@ -809,28 +800,17 @@  static int flv_write_trailer(AVFormatContext *s)
         avio_seek(pb, flv->keyframes_info_offset, SEEK_SET);
         put_amf_string(pb, "filepositions");
         put_amf_dword_array(pb, flv->filepositions_count);
-        for (newflv_posinfo = flv->head_filepositions; newflv_posinfo; newflv_posinfo = newflv_posinfo->next) {
-            put_amf_double(pb, newflv_posinfo->keyframe_position + flv->keyframe_index_size);
+        for (i = 0; i < flv->filepositions_count; i++) {
+            put_amf_double(pb, flv_posinfo[i].keyframe_position + flv->keyframe_index_size);
         }
 
         put_amf_string(pb, "times");
         put_amf_dword_array(pb, flv->filepositions_count);
-        for (newflv_posinfo = flv->head_filepositions; newflv_posinfo; newflv_posinfo = newflv_posinfo->next) {
-            put_amf_double(pb, newflv_posinfo->keyframe_timestamp);
+        for (i = 0; i < flv->filepositions_count; i++) {
+            put_amf_double(pb, flv_posinfo[i].keyframe_timestamp);
         }
 
-        newflv_posinfo = flv->head_filepositions;
-        while (newflv_posinfo) {
-            p = newflv_posinfo->next;
-            if (p) {
-                newflv_posinfo->next = p->next;
-                av_free(p);
-                p = NULL;
-            } else {
-                av_free(newflv_posinfo);
-                newflv_posinfo = NULL;
-            }
-        }
+        av_freep(&flv->filepositions);
 
         put_amf_string(pb, "");
         avio_w8(pb, AMF_END_OF_OBJECT);