[FFmpeg-devel,1/2] avutil: Add Simple loop detector

Submitted by Michael Niedermayer on Aug. 8, 2019, 8:36 a.m.

Details

Message ID 20190808083646.18391-1-michael@niedermayer.cc
State New
Headers show

Commit Message

Michael Niedermayer Aug. 8, 2019, 8:36 a.m.
This provides an alternative to retry counters.
Useful if there is no reasonable maximum number of iterations and
no ordering that naturally avoids loops.

Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
 doc/APIchanges            |  3 ++
 libavutil/Makefile        |  1 +
 libavutil/loop_detector.h | 71 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 75 insertions(+)
 create mode 100644 libavutil/loop_detector.h

Comments

Nicolas George Aug. 8, 2019, 9:59 a.m.
Michael Niedermayer (12019-08-08):
> This provides an alternative to retry counters.
> Useful if there is no reasonable maximum number of iterations and
> no ordering that naturally avoids loops.
> 
> Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> ---
>  doc/APIchanges            |  3 ++
>  libavutil/Makefile        |  1 +
>  libavutil/loop_detector.h | 71 +++++++++++++++++++++++++++++++++++++++
>  3 files changed, 75 insertions(+)
>  create mode 100644 libavutil/loop_detector.h
> 
> diff --git a/doc/APIchanges b/doc/APIchanges
> index 6603a8229e..eee4c30ec5 100644
> --- a/doc/APIchanges
> +++ b/doc/APIchanges
> @@ -15,6 +15,9 @@ libavutil:     2017-10-21
>  
>  API changes, most recent first:
>  
> +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
> +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
> +
>  2019-07-27 - xxxxxxxxxx - lavu 56.33.100 - tx.h
>    Add AV_TX_DOUBLE_FFT and AV_TX_DOUBLE_MDCT
>  
> diff --git a/libavutil/Makefile b/libavutil/Makefile
> index 57e6e3d7e8..0b77fa6347 100644
> --- a/libavutil/Makefile
> +++ b/libavutil/Makefile
> @@ -48,6 +48,7 @@ HEADERS = adler32.h                                                     \
>            intreadwrite.h                                                \
>            lfg.h                                                         \
>            log.h                                                         \
> +          loop_detector.h                                               \
>            macros.h                                                      \
>            mathematics.h                                                 \
>            mastering_display_metadata.h                                  \
> diff --git a/libavutil/loop_detector.h b/libavutil/loop_detector.h
> new file mode 100644
> index 0000000000..6f8643495a
> --- /dev/null
> +++ b/libavutil/loop_detector.h
> @@ -0,0 +1,71 @@
> +/*
> + * Copyright (C) 2019 Michael Niedermayer (michael@niedermayer.cc)
> + *
> + * This file is part of FFmpeg
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +
> +/**
> + * @file
> + * Utilties for detecting infinite loops
> + * @author Michael Niedermayer <michael@niedermayer.cc>
> + */
> +
> +#ifndef AVUTIL_LOOP_DETECTOR_H
> +#define AVUTIL_LOOP_DETECTOR_H
> +
> +typedef struct AVSimpleLoopDetector {
> +    uint64_t count;
> +    uint64_t state;
> +} AVSimpleLoopDetector;
> +
> +/**
> + * Checks if the list of states provided by the user fell into a cycle.
> + *

> + * To initialize or reset the detector, the context is simply memset to 0.

I suggest:

#define AV_SIMPLE_LOOP_DETECTOR_INIT {0}

so we can extend it if needs be.

> + * This detector requires only 16bytes of context and minimal computations
> + * per iteration. In exchange for this simplicity it takes a few iterations
> + * into a loop before it is detected.
> + * No deallocation or memory allocation is needed.
> + *
> + * @param c     The context, initialy and to reset, it is simply memset to 0.
> + *              It is only 16bytes so as to be lightweight and not poison any
> + *              data cache.
> + *

> + * @param state The loop state, when this falls into a cycle the detector
> + *              will after a few iterations return 1.
> + *
> + * @param max_iterations
> + *              after this many iterations the detector will return 1 regardless
> + *              of it falling into a cycle.

Even with the code, I do not manage to understand exactly what it means,
in particular what the state is. The example uses a single state, so any
cycle is trivial.

> + *
> + * @return 1 if a loop is detected, 0 otherwise, no errors are possible.
> + *         The code will always return 1 once it returned 1 until its reset.
> + */
> +static inline int av_is_loop(AVSimpleLoopDetector *c, uint64_t state, uint64_t max_iterations)
> +{
> +    if (c->count && c->state == state)
> +        c->count = max_iterations;
> +    if (c->count >= max_iterations)
> +        return 1;
> +    c->count ++;
> +    if (!(c->count & (c->count - 1)))
> +        c->state = state;
> +    return 0;
> +}
> +
> +#endif /* AVUTIL_LOOP_DETECTOR_H */

Regards,
Lynne Aug. 8, 2019, 10:32 a.m.
Aug 8, 2019, 9:36 AM by michael@niedermayer.cc:

> This provides an alternative to retry counters.
> Useful if there is no reasonable maximum number of iterations and
> no ordering that naturally avoids loops.
>

That's very niche and I don't think it belongs to lavu.
Having codec specific code is better.
Nicolas George Aug. 8, 2019, 10:36 a.m.
Lynne (12019-08-08):
> That's very niche and I don't think it belongs to lavu.

That's a single header with no compiled code.

> Having codec specific code is better.

Why? Why risk bug duplication and maintenance burden?

Regards,
Lynne Aug. 8, 2019, 12:29 p.m.
Aug 8, 2019, 11:36 AM by george@nsup.org:

> Lynne (12019-08-08):
>
>> That's very niche and I don't think it belongs to lavu.
>>
>
> That's a single header with no compiled code.
>
>> Having codec specific code is better.
>>
>
> Why? Why risk bug duplication and maintenance burden?
>

Its niche, we have very few places where there's a chance a loop will become infinite. Even then, they're likely all in lavc, and you can just put a non-public header there if there's more than a few. And right now, there's only one.
Plus, its not really common av code, and don't let its name mislead you, its more of a hack.
Nicolas George Aug. 8, 2019, 12:32 p.m.
Lynne (12019-08-08):
> Its niche, we have very few places where there's a chance a loop will
> become infinite. Even then, they're likely all in lavc, and you can
> just put a non-public header there if there's more than a few. And
> right now, there's only one.

You argue that it does not NEED to be in lavu, but not that it SHOULD
note.

> Plus, its not really common av code, and don't let its name mislead
> you, its more of a hack.

I will disregard the insulting subtext of this sentence.

Regards,
Kieran Kunhya Aug. 8, 2019, 2:38 p.m.
>
> You argue that it does not NEED to be in lavu, but not that it SHOULD
> note.
>
> > Plus, its not really common av code, and don't let its name mislead
> > you, its more of a hack.
>
> I will disregard the insulting subtext of this sentence.
>

There is nothing insulting about this sentence. IMO this is a hack, how
come we have not needed such a thing for years?

Kieran
Michael Niedermayer Aug. 9, 2019, 12:12 a.m.
On Thu, Aug 08, 2019 at 03:38:58PM +0100, Kieran Kunhya wrote:
> >
> > You argue that it does not NEED to be in lavu, but not that it SHOULD
> > note.
> >
> > > Plus, its not really common av code, and don't let its name mislead
> > > you, its more of a hack.
> >
> > I will disregard the insulting subtext of this sentence.
> >
> 
> There is nothing insulting about this sentence. IMO this is a hack, how
> come we have not needed such a thing for years?

we didnt "need" the bugfixes because the code was buggy.

The "building block" of a offset or pointer pointing anywhere in a file
is common, that can lead to cycles. Maybe the fuzzers are not good at
creating such constructs out of thin air but i wouldnt use this as
argument that the code isnt containing such bugs

PS: the reason why fuzzers fail to find such loops is likely because 
its not locally convergent. A pointer closing a loop will not run more
iterations as it become closer in value to closing the loop. It doesnt
loop and only in maybe 1 out of 4 billion values will infinite loop and
that only if all surrounding data structures also are valid enough.

Thanks

[...]
Michael Niedermayer Aug. 10, 2019, 9:29 p.m.
On Thu, Aug 08, 2019 at 11:59:12AM +0200, Nicolas George wrote:
> Michael Niedermayer (12019-08-08):
> > This provides an alternative to retry counters.
> > Useful if there is no reasonable maximum number of iterations and
> > no ordering that naturally avoids loops.
> > 
> > Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> > ---
> >  doc/APIchanges            |  3 ++
> >  libavutil/Makefile        |  1 +
> >  libavutil/loop_detector.h | 71 +++++++++++++++++++++++++++++++++++++++
> >  3 files changed, 75 insertions(+)
> >  create mode 100644 libavutil/loop_detector.h
> > 
> > diff --git a/doc/APIchanges b/doc/APIchanges
> > index 6603a8229e..eee4c30ec5 100644
> > --- a/doc/APIchanges
> > +++ b/doc/APIchanges
> > @@ -15,6 +15,9 @@ libavutil:     2017-10-21
> >  
> >  API changes, most recent first:
> >  
> > +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
> > +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
> > +
> >  2019-07-27 - xxxxxxxxxx - lavu 56.33.100 - tx.h
> >    Add AV_TX_DOUBLE_FFT and AV_TX_DOUBLE_MDCT
> >  
> > diff --git a/libavutil/Makefile b/libavutil/Makefile
> > index 57e6e3d7e8..0b77fa6347 100644
> > --- a/libavutil/Makefile
> > +++ b/libavutil/Makefile
> > @@ -48,6 +48,7 @@ HEADERS = adler32.h                                                     \
> >            intreadwrite.h                                                \
> >            lfg.h                                                         \
> >            log.h                                                         \
> > +          loop_detector.h                                               \
> >            macros.h                                                      \
> >            mathematics.h                                                 \
> >            mastering_display_metadata.h                                  \
> > diff --git a/libavutil/loop_detector.h b/libavutil/loop_detector.h
> > new file mode 100644
> > index 0000000000..6f8643495a
> > --- /dev/null
> > +++ b/libavutil/loop_detector.h
> > @@ -0,0 +1,71 @@
> > +/*
> > + * Copyright (C) 2019 Michael Niedermayer (michael@niedermayer.cc)
> > + *
> > + * This file is part of FFmpeg
> > + *
> > + * FFmpeg is free software; you can redistribute it and/or
> > + * modify it under the terms of the GNU Lesser General Public
> > + * License as published by the Free Software Foundation; either
> > + * version 2.1 of the License, or (at your option) any later version.
> > + *
> > + * FFmpeg is distributed in the hope that it will be useful,
> > + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> > + * Lesser General Public License for more details.
> > + *
> > + * You should have received a copy of the GNU Lesser General Public
> > + * License along with FFmpeg; if not, write to the Free Software
> > + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> > + */
> > +
> > +
> > +/**
> > + * @file
> > + * Utilties for detecting infinite loops
> > + * @author Michael Niedermayer <michael@niedermayer.cc>
> > + */
> > +
> > +#ifndef AVUTIL_LOOP_DETECTOR_H
> > +#define AVUTIL_LOOP_DETECTOR_H
> > +
> > +typedef struct AVSimpleLoopDetector {
> > +    uint64_t count;
> > +    uint64_t state;
> > +} AVSimpleLoopDetector;
> > +
> > +/**
> > + * Checks if the list of states provided by the user fell into a cycle.
> > + *
> 
> > + * To initialize or reset the detector, the context is simply memset to 0.
> 
> I suggest:
> 
> #define AV_SIMPLE_LOOP_DETECTOR_INIT {0}
> 
> so we can extend it if needs be.

will change it


> 
> > + * This detector requires only 16bytes of context and minimal computations
> > + * per iteration. In exchange for this simplicity it takes a few iterations
> > + * into a loop before it is detected.
> > + * No deallocation or memory allocation is needed.
> > + *
> > + * @param c     The context, initialy and to reset, it is simply memset to 0.
> > + *              It is only 16bytes so as to be lightweight and not poison any
> > + *              data cache.
> > + *
> 
> > + * @param state The loop state, when this falls into a cycle the detector
> > + *              will after a few iterations return 1.
> > + *
> > + * @param max_iterations
> > + *              after this many iterations the detector will return 1 regardless
> > + *              of it falling into a cycle.
> 
> Even with the code, I do not manage to understand exactly what it means,
> in particular what the state is. The example uses a single state, so any
> cycle is trivial.

the idea is that until the state repeats the return will be 0
when there is a repeat the return may or may not switch to 1
when a final cycle is entered the return will reasonable quickly switch to 1
would this clarify it ? or should i explain this somehow differently 
or maybe the name for the variable isnt optimal ?
in practive it most often will likely be a single variable like a byte offset
in a file but i imagine it could be something more complex like a depth+offset
or tagname+offset or something

thx

[...]
Reimar Döffinger Aug. 11, 2019, 6:30 p.m.
On 08.08.2019, at 10:36, Michael Niedermayer <michael@niedermayer.cc> wrote:

> This provides an alternative to retry counters.
> Useful if there is no reasonable maximum number of iterations and
> no ordering that naturally avoids loops.

Going by the old principle of "an API is not tested until it has at least 3 users"
might it make sense to delay this until we've found and tested it in a few use-cases?
Depending on how much hurry there is to get the bug-fix in.
I assume there is also an actual bug-fix patch somewhere, maybe we should have that
in the same patch series to make it easier to review the actual usage?

> diff --git a/doc/APIchanges b/doc/APIchanges
> index 6603a8229e..eee4c30ec5 100644
> --- a/doc/APIchanges
> +++ b/doc/APIchanges
> @@ -15,6 +15,9 @@ libavutil:     2017-10-21
> 
> API changes, most recent first:
> 
> +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
> +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector

Does is mean it is a public/installed header?
I'd prefer to keep new APIs internal until they are really proven in use if there is no immediate pressure.
Michael Niedermayer Aug. 12, 2019, 7:53 p.m.
On Sun, Aug 11, 2019 at 08:30:51PM +0200, Reimar Döffinger wrote:
> On 08.08.2019, at 10:36, Michael Niedermayer <michael@niedermayer.cc> wrote:
> 
> > This provides an alternative to retry counters.
> > Useful if there is no reasonable maximum number of iterations and
> > no ordering that naturally avoids loops.
> 
> Going by the old principle of "an API is not tested until it has at least 3 users"
> might it make sense to delay this until we've found and tested it in a few use-cases?
> Depending on how much hurry there is to get the bug-fix in.

> I assume there is also an actual bug-fix patch somewhere, maybe we should have that
> in the same patch series to make it easier to review the actual usage?

sure will repost this eventually with 3+ bugfixes.
But wont search for such bugs ATM as ive too many other things to do
so it might take a bit of time before i do


> 
> > diff --git a/doc/APIchanges b/doc/APIchanges
> > index 6603a8229e..eee4c30ec5 100644
> > --- a/doc/APIchanges
> > +++ b/doc/APIchanges
> > @@ -15,6 +15,9 @@ libavutil:     2017-10-21
> > 
> > API changes, most recent first:
> > 
> > +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
> > +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
> 
> Does is mean it is a public/installed header?

that was intended, but it can of course be trivially be kept local if people
prefer when i repost with 3+ dependant fixes 


> I'd prefer to keep new APIs internal until they are really proven in use if there is no immediate pressure.

[...]

thx
Reimar Döffinger Aug. 13, 2019, 1:36 a.m.
On 12.08.2019, at 21:53, Michael Niedermayer <michael@niedermayer.cc> wrote:

> On Sun, Aug 11, 2019 at 08:30:51PM +0200, Reimar Döffinger wrote:
>> On 08.08.2019, at 10:36, Michael Niedermayer <michael@niedermayer.cc> wrote:
>> 
>>> This provides an alternative to retry counters.
>>> Useful if there is no reasonable maximum number of iterations and
>>> no ordering that naturally avoids loops.
>> 
>> Going by the old principle of "an API is not tested until it has at least 3 users"
>> might it make sense to delay this until we've found and tested it in a few use-cases?
>> Depending on how much hurry there is to get the bug-fix in.
> 
>> I assume there is also an actual bug-fix patch somewhere, maybe we should have that
>> in the same patch series to make it easier to review the actual usage?
> 
> sure will repost this eventually with 3+ bugfixes.
> But wont search for such bugs ATM as ive too many other things to do
> so it might take a bit of time before i do

Of course.
Though on re-considering: if it is added as a purely internal API that we can change at any
time and we do not need to think on backwards compatibility (and a comment on the file
that we might want to have and review use-cases before making it public) I would have
no objections.
I realized only being locked-in compatibility-wise had me worried at this point actually.
Lynne Aug. 13, 2019, 10:11 a.m.
Aug 12, 2019, 20:53 by michael@niedermayer.cc:

> On Sun, Aug 11, 2019 at 08:30:51PM +0200, Reimar Döffinger wrote:
>
>> On 08.08.2019, at 10:36, Michael Niedermayer <michael@niedermayer.cc> wrote:
>>
>> > This provides an alternative to retry counters.
>> > Useful if there is no reasonable maximum number of iterations and
>> > no ordering that naturally avoids loops.
>>
>> Going by the old principle of "an API is not tested until it has at least 3 users"
>> might it make sense to delay this until we've found and tested it in a few use-cases?
>> Depending on how much hurry there is to get the bug-fix in.
>>
>> I assume there is also an actual bug-fix patch somewhere, maybe we should have that
>> in the same patch series to make it easier to review the actual usage?
>>
>
> sure will repost this eventually with 3+ bugfixes.
> But wont search for such bugs ATM as ive too many other things to do
> so it might take a bit of time before i do
>
>
>>
>> > diff --git a/doc/APIchanges b/doc/APIchanges
>> > index 6603a8229e..eee4c30ec5 100644
>> > --- a/doc/APIchanges
>> > +++ b/doc/APIchanges
>> > @@ -15,6 +15,9 @@ libavutil:     2017-10-21
>> > 
>> > API changes, most recent first:
>> > 
>> > +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
>> > +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
>>
>> Does is mean it is a public/installed header?
>>
>
> that was intended, but it can of course be trivially be kept local if people
> prefer when i repost with 3+ dependant fixes 
>

You are ignoring 2 developers, and this isn't the first time you're doing this, nor even the second.
I still do no think even with 3 bugfixes this deserves to be in lavu but rather in every library as a non-installed header, at the very most. I still prefer for code to be duplicated for such a small amount of fixes.
Iit could encourage other developers to put this in their code when it isn't needed when a properly written loop would never go infinite.
And, regardless where this code goes, its still as its been pointed out, a hack.
Michael Niedermayer Aug. 14, 2019, 6:29 p.m.
On Tue, Aug 13, 2019 at 12:11:30PM +0200, Lynne wrote:
> Aug 12, 2019, 20:53 by michael@niedermayer.cc:
> 
> > On Sun, Aug 11, 2019 at 08:30:51PM +0200, Reimar Döffinger wrote:
> >
> >> On 08.08.2019, at 10:36, Michael Niedermayer <michael@niedermayer.cc> wrote:
> >>
> >> > This provides an alternative to retry counters.
> >> > Useful if there is no reasonable maximum number of iterations and
> >> > no ordering that naturally avoids loops.
> >>
> >> Going by the old principle of "an API is not tested until it has at least 3 users"
> >> might it make sense to delay this until we've found and tested it in a few use-cases?
> >> Depending on how much hurry there is to get the bug-fix in.
> >>
> >> I assume there is also an actual bug-fix patch somewhere, maybe we should have that
> >> in the same patch series to make it easier to review the actual usage?
> >>
> >
> > sure will repost this eventually with 3+ bugfixes.
> > But wont search for such bugs ATM as ive too many other things to do
> > so it might take a bit of time before i do
> >
> >
> >>
> >> > diff --git a/doc/APIchanges b/doc/APIchanges
> >> > index 6603a8229e..eee4c30ec5 100644
> >> > --- a/doc/APIchanges
> >> > +++ b/doc/APIchanges
> >> > @@ -15,6 +15,9 @@ libavutil:     2017-10-21
> >> > 
> >> > API changes, most recent first:
> >> > 
> >> > +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
> >> > +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
> >>
> >> Does is mean it is a public/installed header?
> >>
> >
> > that was intended, but it can of course be trivially be kept local if people
> > prefer when i repost with 3+ dependant fixes 
> >
> 
> You are ignoring 2 developers, and this isn't the first time you're doing this, nor even the second.
> I still do no think even with 3 bugfixes this deserves to be in lavu but rather in every library as a non-installed header, at the very most. I still prefer for code to be duplicated for such a small amount of fixes.
> Iit could encourage other developers to put this in their code when it isn't needed when a properly written loop would never go infinite.
> And, regardless where this code goes, its still as its been pointed out, a hack.

why are you agressive ?
this is just a patch that is not ready to be applied as reimar asked for 3
dependant bugfixes.
We can discuss where to put the header when theres actual code that can be
commited. discussing it before we can see the whole patchset makes no real
sense.
I mean you complain that something would have been done thats not even
possible ATM given the peoples requests in the review ...

thanks

[...]
Lynne Aug. 14, 2019, 8:46 p.m.
Aug 14, 2019, 19:29 by michael@niedermayer.cc:

> On Tue, Aug 13, 2019 at 12:11:30PM +0200, Lynne wrote:
>
>> Aug 12, 2019, 20:53 by michael@niedermayer.cc:
>>
>> > On Sun, Aug 11, 2019 at 08:30:51PM +0200, Reimar Döffinger wrote:
>> >
>> >> On 08.08.2019, at 10:36, Michael Niedermayer <michael@niedermayer.cc> wrote:
>> >>
>> >> > This provides an alternative to retry counters.
>> >> > Useful if there is no reasonable maximum number of iterations and
>> >> > no ordering that naturally avoids loops.
>> >>
>> >> Going by the old principle of "an API is not tested until it has at least 3 users"
>> >> might it make sense to delay this until we've found and tested it in a few use-cases?
>> >> Depending on how much hurry there is to get the bug-fix in.
>> >>
>> >> I assume there is also an actual bug-fix patch somewhere, maybe we should have that
>> >> in the same patch series to make it easier to review the actual usage?
>> >>
>> >
>> > sure will repost this eventually with 3+ bugfixes.
>> > But wont search for such bugs ATM as ive too many other things to do
>> > so it might take a bit of time before i do
>> >
>> >
>> >>
>> >> > diff --git a/doc/APIchanges b/doc/APIchanges
>> >> > index 6603a8229e..eee4c30ec5 100644
>> >> > --- a/doc/APIchanges
>> >> > +++ b/doc/APIchanges
>> >> > @@ -15,6 +15,9 @@ libavutil:     2017-10-21
>> >> > 
>> >> > API changes, most recent first:
>> >> > 
>> >> > +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
>> >> > +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
>> >>
>> >> Does is mean it is a public/installed header?
>> >>
>> >
>> > that was intended, but it can of course be trivially be kept local if people
>> > prefer when i repost with 3+ dependant fixes 
>> >
>>
>> You are ignoring 2 developers, and this isn't the first time you're doing this, nor even the second.
>> I still do no think even with 3 bugfixes this deserves to be in lavu but rather in every library as a non-installed header, at the very most. I still prefer for code to be duplicated for such a small amount of fixes.
>> Iit could encourage other developers to put this in their code when it isn't needed when a properly written loop would never go infinite.
>> And, regardless where this code goes, its still as its been pointed out, a hack.
>>
>
> why are you agressive ?
>

I can't find a single hint of aggression in my email. I'm being direct and factual.
If you see this as aggression you shouldn't read any specifications or reports, you'll find yourself very offended.



> this is just a patch that is not ready to be applied as reimar asked for 3
> dependant bugfixes.
> We can discuss where to put the header when theres actual code that can be
> commited. discussing it before we can see the whole patchset makes no real
> sense.
> I mean you complain that something would have been done thats not even
> possible ATM given the peoples requests in the review ...
>

I couldn't help but perceive the discussion you were having and your intentions to post another version as ignoring others' opinions.
Nicolas George Aug. 15, 2019, 6:15 p.m.
Lynne (12019-08-14):
> I can't find a single hint of aggression in my email. I'm being direct and factual.
> If you see this as aggression you shouldn't read any specifications or reports, you'll find yourself very offended.

Was this supposed to be not aggressive either?

> I couldn't help but perceive the discussion you were having and your intentions to post another version as ignoring others' opinions.

When some people want X and some people want not-X, somebody has to
decide. That is not ignoring, that is making an arbitration.

Regards,
Lynne Aug. 15, 2019, 8:46 p.m.
Aug 15, 2019, 19:15 by george@nsup.org:

> Lynne (12019-08-14):
>
>> I can't find a single hint of aggression in my email. I'm being direct and factual.
>> If you see this as aggression you shouldn't read any specifications or reports, you'll find yourself very offended.
>>
>
> Was this supposed to be not aggressive either?
>

Yes, as it happens you don't even need to write anything aggressive to be mistaken as such.
Try reading your response in 3 ways: try speaking in a slightly lower monotonic voice, or try acting confused when you speak as if you didn't pay attention, and finally try putting a hard emphasis on on "this" and "not" while speaking quickly.
You'll hear a sarcastic remark, a genuine question, and a rude threat.

Should I tell you off for being aggressive when you could be genuinely confused? Or perhaps am I mistaking your sarcasm for being confused and educating you unnecessarily? Would this reply be considered an educational response, or maybe a sarcastic mockery? The possibilities are all too many
My point being is your own misconceptions color your view of everything, and you only have yourself to blame if you misread someone. And I do believe you're both misreading me, and will continue to do so despite what I've said and would say. Should I take that as a sign of aggression? Perhaps, if after saying twice in a row what my intentions were.
Michael Niedermayer Aug. 16, 2019, 8:35 a.m.
On Wed, Aug 14, 2019 at 10:46:19PM +0200, Lynne wrote:
> Aug 14, 2019, 19:29 by michael@niedermayer.cc:
> 
> > On Tue, Aug 13, 2019 at 12:11:30PM +0200, Lynne wrote:
> >
> >> Aug 12, 2019, 20:53 by michael@niedermayer.cc:
> >>
> >> > On Sun, Aug 11, 2019 at 08:30:51PM +0200, Reimar Döffinger wrote:
> >> >
> >> >> On 08.08.2019, at 10:36, Michael Niedermayer <michael@niedermayer.cc> wrote:
> >> >>
> >> >> > This provides an alternative to retry counters.
> >> >> > Useful if there is no reasonable maximum number of iterations and
> >> >> > no ordering that naturally avoids loops.
> >> >>
> >> >> Going by the old principle of "an API is not tested until it has at least 3 users"
> >> >> might it make sense to delay this until we've found and tested it in a few use-cases?
> >> >> Depending on how much hurry there is to get the bug-fix in.
> >> >>
> >> >> I assume there is also an actual bug-fix patch somewhere, maybe we should have that
> >> >> in the same patch series to make it easier to review the actual usage?
> >> >>
> >> >
> >> > sure will repost this eventually with 3+ bugfixes.
> >> > But wont search for such bugs ATM as ive too many other things to do
> >> > so it might take a bit of time before i do
> >> >
> >> >
> >> >>
> >> >> > diff --git a/doc/APIchanges b/doc/APIchanges
> >> >> > index 6603a8229e..eee4c30ec5 100644
> >> >> > --- a/doc/APIchanges
> >> >> > +++ b/doc/APIchanges
> >> >> > @@ -15,6 +15,9 @@ libavutil:     2017-10-21
> >> >> > 
> >> >> > API changes, most recent first:
> >> >> > 
> >> >> > +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
> >> >> > +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
> >> >>
> >> >> Does is mean it is a public/installed header?
> >> >>
> >> >
> >> > that was intended, but it can of course be trivially be kept local if people
> >> > prefer when i repost with 3+ dependant fixes 
> >> >
> >>
> >> You are ignoring 2 developers, and this isn't the first time you're doing this, nor even the second.
> >> I still do no think even with 3 bugfixes this deserves to be in lavu but rather in every library as a non-installed header, at the very most. I still prefer for code to be duplicated for such a small amount of fixes.
> >> Iit could encourage other developers to put this in their code when it isn't needed when a properly written loop would never go infinite.
> >> And, regardless where this code goes, its still as its been pointed out, a hack.
> >>
> >
> > why are you agressive ?
> >
> 
> I can't find a single hint of aggression in my email. I'm being direct and factual.
> If you see this as aggression you shouldn't read any specifications or reports, you'll find yourself very offended.

What i refered to as agressive is
"You are ignoring 2 developers, and this isn't the first time you're doing this, nor even the second."

Lets look at this claim by claim

"You are ignoring 2 developers" 

I do not, i noted that 2 people dislike this patch and i will eventually post
a new patchset. If that is still disliked by 2 then we need to look at what
the oppinion of the 2 people will be exactly about that new patchset.
The 2 developers have not seen a not yet written patchset only thing really
known is who the author of the patchset will be.


"and this isn't the first time you're doing this, nor even the second."

This is a simple ad hominem attack, we know who you speak of (me) but noone can
know what issues you talk about so noone can verify this or correct or improve
anything.


"its still as its been pointed out, a hack."

If you see some issue in the code you should explain what issue that is and
not just call the code a "hack". Because noone knows what you refer to and
there is nothing that can be done about issues that noone knows what they
refer to.


Another example of aggression from you is (IRC from a few hours ago)

<Lynne> irc logs off? irc logs off.
<Lynne> carl not here? carl not here.
<Lynne> nicolas is an awful person who disagrees with everything and does no work like ever, yet hangs around the ml to be obnoxious
<Lynne> his opinions on asserts should disqualify him from working on any library ever
<durandal_1707> add reimar to that list
<Lynne> I'll remove that assert if I push that patch, just because maybe he'll fuck off then
<durandal_1707> they only work toward covering michael
<Lynne> reimar does, nickolas is just there to misunderstand and be annoying and demanding

just stop these attacks/insults against people.

Thanks

[...]
Paul B Mahol Aug. 16, 2019, 9:31 a.m.
On Fri, Aug 16, 2019 at 10:35 AM Michael Niedermayer <michael@niedermayer.cc>
wrote:

> On Wed, Aug 14, 2019 at 10:46:19PM +0200, Lynne wrote:
> > Aug 14, 2019, 19:29 by michael@niedermayer.cc:
> >
> > > On Tue, Aug 13, 2019 at 12:11:30PM +0200, Lynne wrote:
> > >
> > >> Aug 12, 2019, 20:53 by michael@niedermayer.cc:
> > >>
> > >> > On Sun, Aug 11, 2019 at 08:30:51PM +0200, Reimar Döffinger wrote:
> > >> >
> > >> >> On 08.08.2019, at 10:36, Michael Niedermayer
> <michael@niedermayer.cc> wrote:
> > >> >>
> > >> >> > This provides an alternative to retry counters.
> > >> >> > Useful if there is no reasonable maximum number of iterations and
> > >> >> > no ordering that naturally avoids loops.
> > >> >>
> > >> >> Going by the old principle of "an API is not tested until it has
> at least 3 users"
> > >> >> might it make sense to delay this until we've found and tested it
> in a few use-cases?
> > >> >> Depending on how much hurry there is to get the bug-fix in.
> > >> >>
> > >> >> I assume there is also an actual bug-fix patch somewhere, maybe we
> should have that
> > >> >> in the same patch series to make it easier to review the actual
> usage?
> > >> >>
> > >> >
> > >> > sure will repost this eventually with 3+ bugfixes.
> > >> > But wont search for such bugs ATM as ive too many other things to do
> > >> > so it might take a bit of time before i do
> > >> >
> > >> >
> > >> >>
> > >> >> > diff --git a/doc/APIchanges b/doc/APIchanges
> > >> >> > index 6603a8229e..eee4c30ec5 100644
> > >> >> > --- a/doc/APIchanges
> > >> >> > +++ b/doc/APIchanges
> > >> >> > @@ -15,6 +15,9 @@ libavutil:     2017-10-21
> > >> >> >
> > >> >> > API changes, most recent first:
> > >> >> >
> > >> >> > +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
> > >> >> > +  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
> > >> >>
> > >> >> Does is mean it is a public/installed header?
> > >> >>
> > >> >
> > >> > that was intended, but it can of course be trivially be kept local
> if people
> > >> > prefer when i repost with 3+ dependant fixes
> > >> >
> > >>
> > >> You are ignoring 2 developers, and this isn't the first time you're
> doing this, nor even the second.
> > >> I still do no think even with 3 bugfixes this deserves to be in lavu
> but rather in every library as a non-installed header, at the very most. I
> still prefer for code to be duplicated for such a small amount of fixes.
> > >> Iit could encourage other developers to put this in their code when
> it isn't needed when a properly written loop would never go infinite.
> > >> And, regardless where this code goes, its still as its been pointed
> out, a hack.
> > >>
> > >
> > > why are you agressive ?
> > >
> >
> > I can't find a single hint of aggression in my email. I'm being direct
> and factual.
> > If you see this as aggression you shouldn't read any specifications or
> reports, you'll find yourself very offended.
>
> What i refered to as agressive is
> "You are ignoring 2 developers, and this isn't the first time you're doing
> this, nor even the second."
>
> Lets look at this claim by claim
>
> "You are ignoring 2 developers"
>
> I do not, i noted that 2 people dislike this patch and i will eventually
> post
> a new patchset. If that is still disliked by 2 then we need to look at what
> the oppinion of the 2 people will be exactly about that new patchset.
> The 2 developers have not seen a not yet written patchset only thing really
> known is who the author of the patchset will be.
>
>
> "and this isn't the first time you're doing this, nor even the second."
>
> This is a simple ad hominem attack, we know who you speak of (me) but
> noone can
> know what issues you talk about so noone can verify this or correct or
> improve
> anything.
>
>
> "its still as its been pointed out, a hack."
>
> If you see some issue in the code you should explain what issue that is and
> not just call the code a "hack". Because noone knows what you refer to and
> there is nothing that can be done about issues that noone knows what they
> refer to.
>
>
> Another example of aggression from you is (IRC from a few hours ago)
>
> <Lynne> irc logs off? irc logs off.
> <Lynne> carl not here? carl not here.
> <Lynne> nicolas is an awful person who disagrees with everything and does
> no work like ever, yet hangs around the ml to be obnoxious
> <Lynne> his opinions on asserts should disqualify him from working on any
> library ever
> <durandal_1707> add reimar to that list
> <Lynne> I'll remove that assert if I push that patch, just because maybe
> he'll fuck off then
> <durandal_1707> they only work toward covering michael
> <Lynne> reimar does, nickolas is just there to misunderstand and be
> annoying and demanding
>
> just stop these attacks/insults against people.
>

Not until all mplayer people are not longer part of organization.

You called for it by this behavior.


>
> Thanks
>
> [...]
>
> --
> Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
>
> You can kill me, but you cannot change the truth.
> _______________________________________________
> 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".
Nicolas George Aug. 16, 2019, 11:03 a.m.
Michael Niedermayer (12019-08-16):
> <Lynne> irc logs off? irc logs off.
> <Lynne> carl not here? carl not here.
> <Lynne> nicolas is an awful person who disagrees with everything and does no work like ever, yet hangs around the ml to be obnoxious
> <Lynne> his opinions on asserts should disqualify him from working on any library ever
> <durandal_1707> add reimar to that list
> <Lynne> I'll remove that assert if I push that patch, just because maybe he'll fuck off then
> <durandal_1707> they only work toward covering michael
> <Lynne> reimar does, nickolas is just there to misunderstand and be annoying and demanding
> 
> just stop these attacks/insults against people.

That is not just aggressive, that is outright insulting. It is sad that
some people do not realize how this kind of attitude is hurting the
project and that they should rather try to see the positive that
everybody brings. That is what code of conducts are for, we should start
enforcing one.

Regards,
Paul B Mahol Aug. 16, 2019, 11:10 a.m.
On Fri, Aug 16, 2019 at 1:03 PM Nicolas George <george@nsup.org> wrote:

> Michael Niedermayer (12019-08-16):
> > <Lynne> irc logs off? irc logs off.
> > <Lynne> carl not here? carl not here.
> > <Lynne> nicolas is an awful person who disagrees with everything and
> does no work like ever, yet hangs around the ml to be obnoxious
> > <Lynne> his opinions on asserts should disqualify him from working on
> any library ever
> > <durandal_1707> add reimar to that list
> > <Lynne> I'll remove that assert if I push that patch, just because maybe
> he'll fuck off then
> > <durandal_1707> they only work toward covering michael
> > <Lynne> reimar does, nickolas is just there to misunderstand and be
> annoying and demanding
> >
> > just stop these attacks/insults against people.
>
> That is not just aggressive, that is outright insulting. It is sad that
> some people do not realize how this kind of attitude is hurting the
> project and that they should rather try to see the positive that
> everybody brings. That is what code of conducts are for, we should start
> enforcing one.
>

Go ahead, then none then only mplayer devs doing fuzzing will remain.



>
> Regards,
>
> --
>   Nicolas George
> _______________________________________________
> 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".

Patch hide | download patch | download mbox

diff --git a/doc/APIchanges b/doc/APIchanges
index 6603a8229e..eee4c30ec5 100644
--- a/doc/APIchanges
+++ b/doc/APIchanges
@@ -15,6 +15,9 @@  libavutil:     2017-10-21
 
 API changes, most recent first:
 
+2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h
+  Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector
+
 2019-07-27 - xxxxxxxxxx - lavu 56.33.100 - tx.h
   Add AV_TX_DOUBLE_FFT and AV_TX_DOUBLE_MDCT
 
diff --git a/libavutil/Makefile b/libavutil/Makefile
index 57e6e3d7e8..0b77fa6347 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -48,6 +48,7 @@  HEADERS = adler32.h                                                     \
           intreadwrite.h                                                \
           lfg.h                                                         \
           log.h                                                         \
+          loop_detector.h                                               \
           macros.h                                                      \
           mathematics.h                                                 \
           mastering_display_metadata.h                                  \
diff --git a/libavutil/loop_detector.h b/libavutil/loop_detector.h
new file mode 100644
index 0000000000..6f8643495a
--- /dev/null
+++ b/libavutil/loop_detector.h
@@ -0,0 +1,71 @@ 
+/*
+ * Copyright (C) 2019 Michael Niedermayer (michael@niedermayer.cc)
+ *
+ * This file is part of FFmpeg
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+
+/**
+ * @file
+ * Utilties for detecting infinite loops
+ * @author Michael Niedermayer <michael@niedermayer.cc>
+ */
+
+#ifndef AVUTIL_LOOP_DETECTOR_H
+#define AVUTIL_LOOP_DETECTOR_H
+
+typedef struct AVSimpleLoopDetector {
+    uint64_t count;
+    uint64_t state;
+} AVSimpleLoopDetector;
+
+/**
+ * Checks if the list of states provided by the user fell into a cycle.
+ *
+ * To initialize or reset the detector, the context is simply memset to 0.
+ * This detector requires only 16bytes of context and minimal computations
+ * per iteration. In exchange for this simplicity it takes a few iterations
+ * into a loop before it is detected.
+ * No deallocation or memory allocation is needed.
+ *
+ * @param c     The context, initialy and to reset, it is simply memset to 0.
+ *              It is only 16bytes so as to be lightweight and not poison any
+ *              data cache.
+ *
+ * @param state The loop state, when this falls into a cycle the detector
+ *              will after a few iterations return 1.
+ *
+ * @param max_iterations
+ *              after this many iterations the detector will return 1 regardless
+ *              of it falling into a cycle.
+ *
+ * @return 1 if a loop is detected, 0 otherwise, no errors are possible.
+ *         The code will always return 1 once it returned 1 until its reset.
+ */
+static inline int av_is_loop(AVSimpleLoopDetector *c, uint64_t state, uint64_t max_iterations)
+{
+    if (c->count && c->state == state)
+        c->count = max_iterations;
+    if (c->count >= max_iterations)
+        return 1;
+    c->count ++;
+    if (!(c->count & (c->count - 1)))
+        c->state = state;
+    return 0;
+}
+
+#endif /* AVUTIL_LOOP_DETECTOR_H */