| Message ID | 20201121172429.18034-1-michael@niedermayer.cc |
|---|---|
| State | Superseded |
| Headers | show |
| Series | [FFmpeg-devel] avformat/utils: Change compute_chapters_end() from O(n²) to O(n log n) | expand |
| Context | Check | Description |
|---|---|---|
| andriy/x86_make | success | Make finished |
| andriy/x86_make_fate | success | Make fate finished |
| andriy/PPC64_make | success | Make finished |
| andriy/PPC64_make_fate | success | Make fate finished |
Nov 21, 2020, 18:24 by michael@niedermayer.cc: > Fixes: Timeout (49sec -> 9sec) > Fixes: 27427/clusterfuzz-testcase-minimized-ffmpeg_dem_FFMETADATA_fuzzer-5140589838073856 > > Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg > Signed-off-by: Michael Niedermayer <michael@niedermayer.cc> > --- > libavformat/utils.c | 43 +++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 43 insertions(+) > > diff --git a/libavformat/utils.c b/libavformat/utils.c > index 503e583ad0..9fac3fc2aa 100644 > --- a/libavformat/utils.c > +++ b/libavformat/utils.c > @@ -3191,15 +3191,58 @@ enum AVCodecID av_codec_get_id(const AVCodecTag *const *tags, unsigned int tag) > return AV_CODEC_ID_NONE; > } > > +static int chapter_start_cmp(const void *p1, const void *p2) > +{ > + AVChapter *ch1 = *(AVChapter**)p1; > + AVChapter *ch2 = *(AVChapter**)p2; > + int delta = av_compare_ts(ch1->start, ch1->time_base, ch2->start, ch2->time_base); > + if (delta) > + return delta; > + return (ch1 > ch2) - (ch1 < ch2); > +} > + > static void compute_chapters_end(AVFormatContext *s) > { > unsigned int i, j; > int64_t max_time = 0; > + int computations = 0; > > if (s->duration > 0 && s->start_time < INT64_MAX - s->duration) > max_time = s->duration + > ((s->start_time == AV_NOPTS_VALUE) ? 0 : s->start_time); > > + for (i = 0; i < s->nb_chapters; i++) > + if (s->chapters[i]->end == AV_NOPTS_VALUE) > + computations ++; > + > + if (computations > 5) { > + AVChapter **timetable = av_malloc(s->nb_chapters * sizeof(*timetable)); > + if (timetable) { > Its a void function, but shouldn't you change it to make it return AVERROR(ENOMEM) and then handle that in the caller? No memory is pretty catastrophic.
On Sat, Nov 21, 2020 at 07:32:31PM +0100, Lynne wrote: > Nov 21, 2020, 18:24 by michael@niedermayer.cc: > > > Fixes: Timeout (49sec -> 9sec) > > Fixes: 27427/clusterfuzz-testcase-minimized-ffmpeg_dem_FFMETADATA_fuzzer-5140589838073856 > > > > Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg > > Signed-off-by: Michael Niedermayer <michael@niedermayer.cc> > > --- > > libavformat/utils.c | 43 +++++++++++++++++++++++++++++++++++++++++++ > > 1 file changed, 43 insertions(+) > > > > diff --git a/libavformat/utils.c b/libavformat/utils.c > > index 503e583ad0..9fac3fc2aa 100644 > > --- a/libavformat/utils.c > > +++ b/libavformat/utils.c > > @@ -3191,15 +3191,58 @@ enum AVCodecID av_codec_get_id(const AVCodecTag *const *tags, unsigned int tag) > > return AV_CODEC_ID_NONE; > > } > > > > +static int chapter_start_cmp(const void *p1, const void *p2) > > +{ > > + AVChapter *ch1 = *(AVChapter**)p1; > > + AVChapter *ch2 = *(AVChapter**)p2; > > + int delta = av_compare_ts(ch1->start, ch1->time_base, ch2->start, ch2->time_base); > > + if (delta) > > + return delta; > > + return (ch1 > ch2) - (ch1 < ch2); > > +} > > + > > static void compute_chapters_end(AVFormatContext *s) > > { > > unsigned int i, j; > > int64_t max_time = 0; > > + int computations = 0; > > > > if (s->duration > 0 && s->start_time < INT64_MAX - s->duration) > > max_time = s->duration + > > ((s->start_time == AV_NOPTS_VALUE) ? 0 : s->start_time); > > > > + for (i = 0; i < s->nb_chapters; i++) > > + if (s->chapters[i]->end == AV_NOPTS_VALUE) > > + computations ++; > > + > > + if (computations > 5) { > > + AVChapter **timetable = av_malloc(s->nb_chapters * sizeof(*timetable)); > > + if (timetable) { > > > > Its a void function, but shouldn't you change it to make it return > AVERROR(ENOMEM) and then handle that in the caller? > No memory is pretty catastrophic. you are probably correct, that fallback isnt worth it, ill drop it and return failure thx [...]
diff --git a/libavformat/utils.c b/libavformat/utils.c index 503e583ad0..9fac3fc2aa 100644 --- a/libavformat/utils.c +++ b/libavformat/utils.c @@ -3191,15 +3191,58 @@ enum AVCodecID av_codec_get_id(const AVCodecTag *const *tags, unsigned int tag) return AV_CODEC_ID_NONE; } +static int chapter_start_cmp(const void *p1, const void *p2) +{ + AVChapter *ch1 = *(AVChapter**)p1; + AVChapter *ch2 = *(AVChapter**)p2; + int delta = av_compare_ts(ch1->start, ch1->time_base, ch2->start, ch2->time_base); + if (delta) + return delta; + return (ch1 > ch2) - (ch1 < ch2); +} + static void compute_chapters_end(AVFormatContext *s) { unsigned int i, j; int64_t max_time = 0; + int computations = 0; if (s->duration > 0 && s->start_time < INT64_MAX - s->duration) max_time = s->duration + ((s->start_time == AV_NOPTS_VALUE) ? 0 : s->start_time); + for (i = 0; i < s->nb_chapters; i++) + if (s->chapters[i]->end == AV_NOPTS_VALUE) + computations ++; + + if (computations > 5) { + AVChapter **timetable = av_malloc(s->nb_chapters * sizeof(*timetable)); + if (timetable) { + for (i = 0; i < s->nb_chapters; i++) + timetable[i] = s->chapters[i]; + qsort(timetable, s->nb_chapters, sizeof(*timetable), chapter_start_cmp); + + for (i = 0; i < s->nb_chapters; i++) + if (timetable[i]->end == AV_NOPTS_VALUE) { + AVChapter *ch = timetable[i]; + int64_t end = max_time ? av_rescale_q(max_time, AV_TIME_BASE_Q, + ch->time_base) + : INT64_MAX; + + if (i + 1 < s->nb_chapters) { + AVChapter *ch1 = timetable[i + 1]; + int64_t next_start = av_rescale_q(ch1->start, ch1->time_base, + ch->time_base); + if (next_start > ch->start && next_start < end) + end = next_start; + } + ch->end = (end == INT64_MAX || end < ch->start) ? ch->start : end; + } + av_free(timetable); + return; + } + } + for (i = 0; i < s->nb_chapters; i++) if (s->chapters[i]->end == AV_NOPTS_VALUE) { AVChapter *ch = s->chapters[i];
Fixes: Timeout (49sec -> 9sec) Fixes: 27427/clusterfuzz-testcase-minimized-ffmpeg_dem_FFMETADATA_fuzzer-5140589838073856 Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg Signed-off-by: Michael Niedermayer <michael@niedermayer.cc> --- libavformat/utils.c | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+)