[FFmpeg-devel] lavf/mov: fix hang while seek on a kind of fragmented mp4.

Binary searching would hang if the fragment items do NOT have timestamp for the specified stream.

For example, a fmp4 consists of separated 'moof' boxes for each track, and separated 'sidx' for each segment, but no 'mfra' box.
Then every fragment item only have the timestamp for one of its tracks.

Signed-off-by: Charles Liu <liuchh83@gmail.com>
---
 libavformat/mov.c | 21 +++++++++------------
 1 file changed, 9 insertions(+), 12 deletions(-)

On Sat, 2 Feb 2019, Charles Liu wrote:

> Binary searching would hang if the fragment items do NOT have timestamp for the specified stream.
>
> For example, a fmp4 consists of separated 'moof' boxes for each track, and separated 'sidx' for each segment, but no 'mfra' box.
> Then every fragment item only have the timestamp for one of its tracks.

I don't see why you are changing the search to be linear. Is it possible 
the some of the stream fragmens have NOPTS_VALUE but other don't? In this 
case you should keep the binary search and only fall back to linear search 
if binary search finds an AV_NOPTS_VALUE. See similar code in function 
mxf_absolute_bodysid_offset of libavformat/mxfdec.c.

On the other hand, if either all stream segments have AV_NOPTS_VALUE, or 
none of them do, then why don't you simply break out of the loop with error?

Thanks,
Marton


>
> Signed-off-by: Charles Liu <liuchh83@gmail.com>
> ---
> libavformat/mov.c | 21 +++++++++------------
> 1 file changed, 9 insertions(+), 12 deletions(-)
>
> diff --git a/libavformat/mov.c b/libavformat/mov.c
> index 9b9739f788..ce1130ad07 100644
> --- a/libavformat/mov.c
> +++ b/libavformat/mov.c
> @@ -1266,9 +1266,8 @@ static int64_t get_frag_time(MOVFragmentIndex *frag_index,
> static int search_frag_timestamp(MOVFragmentIndex *frag_index,
>                                  AVStream *st, int64_t timestamp)
> {
> -    int a, b, m;
>     int64_t frag_time;
> -    int id = -1;
> +    int i, frag = 0, id = -1;
>
>     if (st) {
>         // If the stream is referenced by any sidx, limit the search
> @@ -1278,20 +1277,18 @@ static int search_frag_timestamp(MOVFragmentIndex *frag_index,
>             id = st->id;
>     }
> 
> -    a = -1;
> -    b = frag_index->nb_items;
> -
> -    while (b - a > 1) {
> -        m = (a + b) >> 1;
> -        frag_time = get_frag_time(frag_index, m, id);
> +    for (i = 0; i < frag_index->nb_items; i++) {
> +        frag_time = get_frag_time(frag_index, i, id);
>         if (frag_time != AV_NOPTS_VALUE) {
> -            if (frag_time >= timestamp)
> -                b = m;
>             if (frag_time <= timestamp)
> -                a = m;
> +                frag = i;
> +            else {
> +                break;
> +            }
>         }
>     }
> -    return a;
> +
> +    return frag;
> }
> 
> static int update_frag_index(MOVContext *c, int64_t offset)
> -- 
> 2.20.1
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel

Hi Marton,


Thanks for your replay.


The case I met is shown in attached pictures. Each 'moof' only contain one
track's data. So the reference id of the first 'sidx' box is 1. The the
reference id of the second 'sidx' box is 2.

Then we read below segment info in mp4 demuxer:

|MOVFragmentIndex

|----MOVFragmentIndexItem[0]

|--------MOVFragmentStreamInfo[0] {sidx_pts=20000}

|--------MOVFragmentStreamInfo[1] {sidx_pts=AV_NOPTS_VALUE}

|----MOVFragmentIndexItem[1]

|--------MOVFragmentStreamInfo[0] {sidx_pts=AV_NOPTS_VALUE}

|--------MOVFragmentStreamInfo[1] {sidx_pts=0}

|...

If you seek a point to this file, you can NOT exit the while statement in
search_frag_timestamp().

You can easily create the test clip: ffmpeg -i INPUT_VIDEO -c copy
-movflags dash+frag_keyframe+skip_trailer+separate_moof out.mp4

[image: sidx0.png]
[image: sidx1.png]

On the other hand, you are right. I should only fall back to linear
searching if needed. It is more efficient.
I'll send the patch again.

Thanks and Regards,
Charles Liu

Marton Balint <cus@passwd.hu> 于2019年2月3日周日 上午12:03写道：

>
>
> On Sat, 2 Feb 2019, Charles Liu wrote:
>
> > Binary searching would hang if the fragment items do NOT have timestamp
> for the specified stream.
> >
> > For example, a fmp4 consists of separated 'moof' boxes for each track,
> and separated 'sidx' for each segment, but no 'mfra' box.
> > Then every fragment item only have the timestamp for one of its tracks.
>
> I don't see why you are changing the search to be linear. Is it possible
> the some of the stream fragmens have NOPTS_VALUE but other don't? In this
> case you should keep the binary search and only fall back to linear search
> if binary search finds an AV_NOPTS_VALUE. See similar code in function
> mxf_absolute_bodysid_offset of libavformat/mxfdec.c.
>
> On the other hand, if either all stream segments have AV_NOPTS_VALUE, or
> none of them do, then why don't you simply break out of the loop with
> error?
>
> Thanks,
> Marton
>
>
> >
> > Signed-off-by: Charles Liu <liuchh83@gmail.com>
> > ---
> > libavformat/mov.c | 21 +++++++++------------
> > 1 file changed, 9 insertions(+), 12 deletions(-)
> >
> > diff --git a/libavformat/mov.c b/libavformat/mov.c
> > index 9b9739f788..ce1130ad07 100644
> > --- a/libavformat/mov.c
> > +++ b/libavformat/mov.c
> > @@ -1266,9 +1266,8 @@ static int64_t get_frag_time(MOVFragmentIndex
> *frag_index,
> > static int search_frag_timestamp(MOVFragmentIndex *frag_index,
> >                                  AVStream *st, int64_t timestamp)
> > {
> > -    int a, b, m;
> >     int64_t frag_time;
> > -    int id = -1;
> > +    int i, frag = 0, id = -1;
> >
> >     if (st) {
> >         // If the stream is referenced by any sidx, limit the search
> > @@ -1278,20 +1277,18 @@ static int
> search_frag_timestamp(MOVFragmentIndex *frag_index,
> >             id = st->id;
> >     }
> >
> > -    a = -1;
> > -    b = frag_index->nb_items;
> > -
> > -    while (b - a > 1) {
> > -        m = (a + b) >> 1;
> > -        frag_time = get_frag_time(frag_index, m, id);
> > +    for (i = 0; i < frag_index->nb_items; i++) {
> > +        frag_time = get_frag_time(frag_index, i, id);
> >         if (frag_time != AV_NOPTS_VALUE) {
> > -            if (frag_time >= timestamp)
> > -                b = m;
> >             if (frag_time <= timestamp)
> > -                a = m;
> > +                frag = i;
> > +            else {
> > +                break;
> > +            }
> >         }
> >     }
> > -    return a;
> > +
> > +    return frag;
> > }
> >
> > static int update_frag_index(MOVContext *c, int64_t offset)
> > --
> > 2.20.1
> >
> > _______________________________________________
> > ffmpeg-devel mailing list
> > ffmpeg-devel@ffmpeg.org
> > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>

On Sat, Feb 02, 2019 at 05:03:25PM +0100, Marton Balint wrote:
> 
> 
> On Sat, 2 Feb 2019, Charles Liu wrote:
> 
> >Binary searching would hang if the fragment items do NOT have timestamp for the specified stream.
> >
> >For example, a fmp4 consists of separated 'moof' boxes for each track, and separated 'sidx' for each segment, but no 'mfra' box.
> >Then every fragment item only have the timestamp for one of its tracks.
> 
> I don't see why you are changing the search to be linear. Is it possible the
> some of the stream fragmens have NOPTS_VALUE but other don't? In this case
> you should keep the binary search and only fall back to linear search if
> binary search finds an AV_NOPTS_VALUE. See similar code in function
> mxf_absolute_bodysid_offset of libavformat/mxfdec.c.

The point of binary searching is to achieve O(log n) time
if there is any linear search this is no longer achieved.
So its not ideal to have any AV_NOPTS_VALUE in the array that is
searched. It would be better if the unknown entries are not in the
array that is used for the search or if their value is monotonized
once for all searches
that being ideal at least ...

Thanks

[...]

On Mon, 4 Feb 2019, Michael Niedermayer wrote:

> On Sat, Feb 02, 2019 at 05:03:25PM +0100, Marton Balint wrote:
>>
>>
>> On Sat, 2 Feb 2019, Charles Liu wrote:
>>
>>> Binary searching would hang if the fragment items do NOT have timestamp for the specified stream.
>>>
>>> For example, a fmp4 consists of separated 'moof' boxes for each track, and separated 'sidx' for each segment, but no 'mfra' box.
>>> Then every fragment item only have the timestamp for one of its tracks.
>>
>> I don't see why you are changing the search to be linear. Is it possible the
>> some of the stream fragmens have NOPTS_VALUE but other don't? In this case
>> you should keep the binary search and only fall back to linear search if
>> binary search finds an AV_NOPTS_VALUE. See similar code in function
>> mxf_absolute_bodysid_offset of libavformat/mxfdec.c.
>
> The point of binary searching is to achieve O(log n) time
> if there is any linear search this is no longer achieved.
> So its not ideal to have any AV_NOPTS_VALUE in the array that is
> searched. It would be better if the unknown entries are not in the
> array that is used for the search or if their value is monotonized
> once for all searches
> that being ideal at least ...

Yeah that is true, but that would require maintaining a different array 
with pts-es, and getting/updating fragment pts-es are complicated as is.

Considering that this fixes a hang, I'd rather see the last version of the 
patch applied than wait for a more complicated, yet faster implementation.

Regards,
Marton

I also think it would be better if we store pts-es in different lists for
each track. However, it does NOT match the original design of data
structures. Several boxes will be affected. So I am trying to commit this
patch to discuss with maintainers.

At present, I prefer the last version patch(fall back to linear searching
only if needed). I could research more later.


Thanks and Regards,

Charles Liu

Marton Balint <cus@passwd.hu> 于2019年2月5日周二 上午4:42写道：

>
>
> On Mon, 4 Feb 2019, Michael Niedermayer wrote:
>
> > On Sat, Feb 02, 2019 at 05:03:25PM +0100, Marton Balint wrote:
> >>
> >>
> >> On Sat, 2 Feb 2019, Charles Liu wrote:
> >>
> >>> Binary searching would hang if the fragment items do NOT have
> timestamp for the specified stream.
> >>>
> >>> For example, a fmp4 consists of separated 'moof' boxes for each track,
> and separated 'sidx' for each segment, but no 'mfra' box.
> >>> Then every fragment item only have the timestamp for one of its tracks.
> >>
> >> I don't see why you are changing the search to be linear. Is it
> possible the
> >> some of the stream fragmens have NOPTS_VALUE but other don't? In this
> case
> >> you should keep the binary search and only fall back to linear search if
> >> binary search finds an AV_NOPTS_VALUE. See similar code in function
> >> mxf_absolute_bodysid_offset of libavformat/mxfdec.c.
> >
> > The point of binary searching is to achieve O(log n) time
> > if there is any linear search this is no longer achieved.
> > So its not ideal to have any AV_NOPTS_VALUE in the array that is
> > searched. It would be better if the unknown entries are not in the
> > array that is used for the search or if their value is monotonized
> > once for all searches
> > that being ideal at least ...
>
> Yeah that is true, but that would require maintaining a different array
> with pts-es, and getting/updating fragment pts-es are complicated as is.
>
> Considering that this fixes a hang, I'd rather see the last version of the
> patch applied than wait for a more complicated, yet faster implementation.
>
> Regards,
> Marton
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>