Overflow in calculating audio timestamp

Overflow in calculating audio timestamp

[Alan Young]

sound/core/pcm_lib.c:update_audio_tstamp() contains the following 
calculation:

         audio_nsecs = div_u64(audio_frames * 1000000000LL,
                 runtime->rate);

This will result in a 64-bit overflow after 4.4 days at 48000 Hz, or 1.1 
days at 192000.

Are you interested in a patch to improve this?

The same calculation occurs in a couple of other places.

Alan.

Re: Overflow in calculating audio timestamp

[Takashi Sakamoto]

Hi,

Thank you for the report.

On Thu, Feb 02, 2023 at 01:55:24PM +0000, Alan Young wrote:
> sound/core/pcm_lib.c:update_audio_tstamp() contains the following
> calculation:
> 
>         audio_nsecs = div_u64(audio_frames * 1000000000LL,
>                 runtime->rate);
> 
> This will result in a 64-bit overflow after 4.4 days at 48000 Hz, or 1.1
> days at 192000.
> 
> Are you interested in a patch to improve this?
> 
> The same calculation occurs in a couple of other places.

I'm interested in your patch. Would you please post it C.C.ed to the
list and me?  As you noted, we can see the issue in ALSA PCM core and
Intel HDA stuffs at least.

 * sound/core/pcm_lib.c
 * sound/pci/hda/hda_controller.c
 * sound/soc/intel/skylake/skl-pcm.c

I note that 'NSEC_PER_SEC' macro is available once including
'linux/time.h'. It is better to use instead of the literal.
The macro is defined in 'include/vdso/time64.h'.


As another issue, the value of 'audio_frames' comes from the value of
'struct snd_pcm_runtime.hw_ptr_wrap'. In ALSA PCM core, the value is
increased by the size of PCM buffer every time hw_ptr cross the boundary
of PCM buffer, thus multiples of the size is expected. Nevertheless,
there is no check for overflow within 64 bit storage. In my opinion, the
committer had less care of it since user does not practically playback or
capture PCM substream so long. But the additional check is preferable as
long as it does not break the fallback implementation of audio time stamp.


Regards

Takashi Sakamoto

Re: Overflow in calculating audio timestamp

[Alan Young]

On 03/02/2023 00:34, Takashi Sakamoto wrote:
> Hi,
>
> Thank you for the report.
>
> On Thu, Feb 02, 2023 at 01:55:24PM +0000, Alan Young wrote:
>> sound/core/pcm_lib.c:update_audio_tstamp() contains the following
>> calculation:
>>
>>          audio_nsecs = div_u64(audio_frames * 1000000000LL,
>>                  runtime->rate);
>>
>> This will result in a 64-bit overflow after 4.4 days at 48000 Hz, or 1.1
>> days at 192000.
>>
>> Are you interested in a patch to improve this?
>>
>> The same calculation occurs in a couple of other places.
> I'm interested in your patch. Would you please post it C.C.ed to the
> list and me?  As you noted, we can see the issue in ALSA PCM core and
> Intel HDA stuffs at least.
>
>   * sound/core/pcm_lib.c
>   * sound/pci/hda/hda_controller.c
>   * sound/soc/intel/skylake/skl-pcm.c
>
> I note that 'NSEC_PER_SEC' macro is available once including
> 'linux/time.h'. It is better to use instead of the literal.
> The macro is defined in 'include/vdso/time64.h'.
>
>
> As another issue, the value of 'audio_frames' comes from the value of
> 'struct snd_pcm_runtime.hw_ptr_wrap'. In ALSA PCM core, the value is
> increased by the size of PCM buffer every time hw_ptr cross the boundary
> of PCM buffer, thus multiples of the size is expected. Nevertheless,
> there is no check for overflow within 64 bit storage. In my opinion, the
> committer had less care of it since user does not practically playback or
> capture PCM substream so long. But the additional check is preferable as
> long as it does not break the fallback implementation of audio time stamp.


I have not yet finished testing various alternatives. I want to extend 
the overflow by "enough" and also am conscious of the need to keep the 
overhead down.

I actually think, on reflection, that the only case that matters is the 
call from update_audio_tstamp(). The others only deal with codec delays 
which will be small (unless I misunderstand those drivers).

This is what I have so far but I'll submit a proper patch when I have it 
refined.

static u64 snd_pcm_lib_frames_to_nsecs(u64 frames, unsigned int rate)
{
     /*
      *  Avoid 64-bit calculation overflow after:
      *  - 4.8 days @ 44100
      *  - 0.56 days @ 384000
      *  extending these intervals by a factor of 100.
      */
     if (frames < 0xffffffffffffffffLLU / NSEC_PER_SEC)
         return div_u64(frames * NSEC_PER_SEC, rate);

     if (rate % 100 == 0)
         return div_u64(frames * (NSEC_PER_SEC/100), (rate/100));

     /* Fallback: reduce precision to approximately deci-micro-seconds: 1.28e-7 */
     return div_u64(frames * (NSEC_PER_SEC >> 7), rate) << 7;
}

Alan.

Re: Overflow in calculating audio timestamp

[Jaroslav Kysela]

On 03. 02. 23 17:11, Alan Young wrote:
> 
> On 03/02/2023 00:34, Takashi Sakamoto wrote:
>> Hi,
>>
>> Thank you for the report.
>>
>> On Thu, Feb 02, 2023 at 01:55:24PM +0000, Alan Young wrote:
>>> sound/core/pcm_lib.c:update_audio_tstamp() contains the following
>>> calculation:
>>>
>>>           audio_nsecs = div_u64(audio_frames * 1000000000LL,
>>>                   runtime->rate);
>>>
>>> This will result in a 64-bit overflow after 4.4 days at 48000 Hz, or 1.1
>>> days at 192000.
>>>
>>> Are you interested in a patch to improve this?
>>>
>>> The same calculation occurs in a couple of other places.
>> I'm interested in your patch. Would you please post it C.C.ed to the
>> list and me?  As you noted, we can see the issue in ALSA PCM core and
>> Intel HDA stuffs at least.
>>
>>    * sound/core/pcm_lib.c
>>    * sound/pci/hda/hda_controller.c
>>    * sound/soc/intel/skylake/skl-pcm.c
>>
>> I note that 'NSEC_PER_SEC' macro is available once including
>> 'linux/time.h'. It is better to use instead of the literal.
>> The macro is defined in 'include/vdso/time64.h'.
>>
>>
>> As another issue, the value of 'audio_frames' comes from the value of
>> 'struct snd_pcm_runtime.hw_ptr_wrap'. In ALSA PCM core, the value is
>> increased by the size of PCM buffer every time hw_ptr cross the boundary
>> of PCM buffer, thus multiples of the size is expected. Nevertheless,
>> there is no check for overflow within 64 bit storage. In my opinion, the
>> committer had less care of it since user does not practically playback or
>> capture PCM substream so long. But the additional check is preferable as
>> long as it does not break the fallback implementation of audio time stamp.
> 
> 
> I have not yet finished testing various alternatives. I want to extend
> the overflow by "enough" and also am conscious of the need to keep the
> overhead down.
> 
> I actually think, on reflection, that the only case that matters is the
> call from update_audio_tstamp(). The others only deal with codec delays
> which will be small (unless I misunderstand those drivers).
> 
> This is what I have so far but I'll submit a proper patch when I have it
> refined.
> 
> static u64 snd_pcm_lib_frames_to_nsecs(u64 frames, unsigned int rate)
> {
>       /*
>        *  Avoid 64-bit calculation overflow after:
>        *  - 4.8 days @ 44100
>        *  - 0.56 days @ 384000
>        *  extending these intervals by a factor of 100.
>        */
>       if (frames < 0xffffffffffffffffLLU / NSEC_PER_SEC)
>           return div_u64(frames * NSEC_PER_SEC, rate);
> 
>       if (rate % 100 == 0)
>           return div_u64(frames * (NSEC_PER_SEC/100), (rate/100));
> 
>       /* Fallback: reduce precision to approximately deci-micro-seconds: 1.28e-7 */
>       return div_u64(frames * (NSEC_PER_SEC >> 7), rate) << 7;
> }

Thank you for your suggestion, but I think that the *whole* code for 
!get_time_info in update_audio_tstamp() should be recoded. The calling of 
ns_to_timespec64() is not enough to handle the boundary wraps in a decent 
range (tenths years for 24x7 operation) and the bellow code is dangerous for 
32-bit apps / system:

      if (crossed_boundary) {
                 snd_BUG_ON(crossed_boundary != 1);
                 runtime->hw_ptr_wrap += runtime->boundary;
      }

I would probably propose to have just hw_ptr_wrap +1 counter (we can 
reconstruct the frame position back by multiplication and do range check 
later), remove snd_BUG_ON and improve the timespec64 calculation.

The calculation should be split to two parts (tv_sec / tv_nsec):

1) calculate seconds: (frames / rate)
2) calculate the remainder (ns): ((frames % rate) * NSEC_PER_SEC) / rate

With 64-bit integer range, we should go up to (for 384000Hz rate):

2**64 / 384000 / 3600 / 24 / 365 = ~1523287 years

Maybe I did a mistake somewhere. I'm open for comments.

					Jaroslav

-- 
Jaroslav Kysela <perex@perex.cz>
Linux Sound Maintainer; ALSA Project; Red Hat, Inc.

Re: Overflow in calculating audio timestamp

[Pierre-Louis Bossart]

On 2/3/23 12:02, Jaroslav Kysela wrote:
> On 03. 02. 23 17:11, Alan Young wrote:
>>
>> On 03/02/2023 00:34, Takashi Sakamoto wrote:
>>> Hi,
>>>
>>> Thank you for the report.
>>>
>>> On Thu, Feb 02, 2023 at 01:55:24PM +0000, Alan Young wrote:
>>>> sound/core/pcm_lib.c:update_audio_tstamp() contains the following
>>>> calculation:
>>>>
>>>>           audio_nsecs = div_u64(audio_frames * 1000000000LL,
>>>>                   runtime->rate);
>>>>
>>>> This will result in a 64-bit overflow after 4.4 days at 48000 Hz, or
>>>> 1.1
>>>> days at 192000.
>>>>
>>>> Are you interested in a patch to improve this?
>>>>
>>>> The same calculation occurs in a couple of other places.
>>> I'm interested in your patch. Would you please post it C.C.ed to the
>>> list and me?  As you noted, we can see the issue in ALSA PCM core and
>>> Intel HDA stuffs at least.
>>>
>>>    * sound/core/pcm_lib.c
>>>    * sound/pci/hda/hda_controller.c
>>>    * sound/soc/intel/skylake/skl-pcm.c
>>>
>>> I note that 'NSEC_PER_SEC' macro is available once including
>>> 'linux/time.h'. It is better to use instead of the literal.
>>> The macro is defined in 'include/vdso/time64.h'.
>>>
>>>
>>> As another issue, the value of 'audio_frames' comes from the value of
>>> 'struct snd_pcm_runtime.hw_ptr_wrap'. In ALSA PCM core, the value is
>>> increased by the size of PCM buffer every time hw_ptr cross the boundary
>>> of PCM buffer, thus multiples of the size is expected. Nevertheless,
>>> there is no check for overflow within 64 bit storage. In my opinion, the
>>> committer had less care of it since user does not practically
>>> playback or
>>> capture PCM substream so long. But the additional check is preferable as
>>> long as it does not break the fallback implementation of audio time
>>> stamp.
>>
>>
>> I have not yet finished testing various alternatives. I want to extend
>> the overflow by "enough" and also am conscious of the need to keep the
>> overhead down.
>>
>> I actually think, on reflection, that the only case that matters is the
>> call from update_audio_tstamp(). The others only deal with codec delays
>> which will be small (unless I misunderstand those drivers).
>>
>> This is what I have so far but I'll submit a proper patch when I have it
>> refined.
>>
>> static u64 snd_pcm_lib_frames_to_nsecs(u64 frames, unsigned int rate)
>> {
>>       /*
>>        *  Avoid 64-bit calculation overflow after:
>>        *  - 4.8 days @ 44100
>>        *  - 0.56 days @ 384000
>>        *  extending these intervals by a factor of 100.
>>        */
>>       if (frames < 0xffffffffffffffffLLU / NSEC_PER_SEC)
>>           return div_u64(frames * NSEC_PER_SEC, rate);
>>
>>       if (rate % 100 == 0)
>>           return div_u64(frames * (NSEC_PER_SEC/100), (rate/100));
>>
>>       /* Fallback: reduce precision to approximately
>> deci-micro-seconds: 1.28e-7 */
>>       return div_u64(frames * (NSEC_PER_SEC >> 7), rate) << 7;
>> }
> 
> Thank you for your suggestion, but I think that the *whole* code for
> !get_time_info in update_audio_tstamp() should be recoded. The calling
> of ns_to_timespec64() is not enough to handle the boundary wraps in a
> decent range (tenths years for 24x7 operation) and the bellow code is
> dangerous for 32-bit apps / system:
> 
>      if (crossed_boundary) {
>                 snd_BUG_ON(crossed_boundary != 1);
>                 runtime->hw_ptr_wrap += runtime->boundary;
>      }
> 
> I would probably propose to have just hw_ptr_wrap +1 counter (we can
> reconstruct the frame position back by multiplication and do range check
> later), remove snd_BUG_ON and improve the timespec64 calculation.
> 
> The calculation should be split to two parts (tv_sec / tv_nsec):
> 
> 1) calculate seconds: (frames / rate)
> 2) calculate the remainder (ns): ((frames % rate) * NSEC_PER_SEC) / rate
> 
> With 64-bit integer range, we should go up to (for 384000Hz rate):
> 
> 2**64 / 384000 / 3600 / 24 / 365 = ~1523287 years
> 
> Maybe I did a mistake somewhere. I'm open for comments.

I am not following how the boundary comes into play for cases where the
timestamp comes directly from a link counter, and is not related to the
DMA hw_ptr at all.

Re: Overflow in calculating audio timestamp

[Alan Young]

On 04/02/2023 00:54, Pierre-Louis Bossart wrote:
> I am not following how the boundary comes into play for cases where the
> timestamp comes directly from a link counter, and is not related to the
> DMA hw_ptr at all.


I don't think it does. This is all only for the 
SNDRV_PCM_AUDIO_TSTAMP_TYPE_DEFAULT case.

Re: Overflow in calculating audio timestamp

[Alan Young]

On 03/02/2023 18:02, Jaroslav Kysela wrote:
> Thank you for your suggestion, but I think that the *whole* code for 
> !get_time_info in update_audio_tstamp() should be recoded. The calling 
> of ns_to_timespec64() is not enough to handle the boundary wraps in a 
> decent range (tenths years for 24x7 operation) 

Yes, indeed. My ambition was unnecessarily short.


> and the bellow code is dangerous for 32-bit apps / system:
>
>      if (crossed_boundary) {
>                 snd_BUG_ON(crossed_boundary != 1);
>                 runtime->hw_ptr_wrap += runtime->boundary;
>      }
>
I don't understand why?


> I would probably propose to have just hw_ptr_wrap +1 counter (we can 
> reconstruct the frame position back by multiplication and do range 
> check later), 

Would that really help that much? It would extend the total possible 
duration but perhaps ~1523287 years(below) is sufficient.

> remove snd_BUG_ON

Again, why?


> and improve the timespec64 calculation.
>
> The calculation should be split to two parts (tv_sec / tv_nsec):
>
> 1) calculate seconds: (frames / rate)
> 2) calculate the remainder (ns): ((frames % rate) * NSEC_PER_SEC) / rate
>
> With 64-bit integer range, we should go up to (for 384000Hz rate):
>
> 2**64 / 384000 / 3600 / 24 / 365 = ~1523287 years


Yes indeed. How about this?

static inline void snd_pcm_lib_frames_to_timespec64(u64 frames, unsigned int rate, struct timespec64 *audio_tstamp)
{
	u32 remainder;
	audio_tstamp->tv_sec = div_u64_rem(frames, rate, &remainder);
	audio_tstamp->tv_nsec = div_u64(mul_u32_u32(remainder, NSEC_PER_SEC), rate);
}

Alan.

Re: Overflow in calculating audio timestamp

[Jaroslav Kysela]

On 04. 02. 23 10:11, Alan Young wrote:
> 
> On 03/02/2023 18:02, Jaroslav Kysela wrote:
>> Thank you for your suggestion, but I think that the *whole* code for 
>> !get_time_info in update_audio_tstamp() should be recoded. The calling of 
>> ns_to_timespec64() is not enough to handle the boundary wraps in a decent 
>> range (tenths years for 24x7 operation) 
> 
> Yes, indeed. My ambition was unnecessarily short.
> 
> 
>> and the bellow code is dangerous for 32-bit apps / system:
>>
>>      if (crossed_boundary) {
>>                 snd_BUG_ON(crossed_boundary != 1);
>>                 runtime->hw_ptr_wrap += runtime->boundary;
>>      }
>>
> I don't understand why?
 >
>> I would probably propose to have just hw_ptr_wrap +1 counter (we can 
>> reconstruct the frame position back by multiplication and do range check 
>> later), 
> 
> Would that really help that much? It would extend the total possible duration 
> but perhaps ~1523287 years(below) is sufficient.
> 
>> remove snd_BUG_ON
> 
> Again, why?

For 32-bit apps the boundary is near to UINT32_MAX (see recalculate_boundary() 
function). So only one crossing point is not enough to cover a decent time range.

There should be a better check, if the add operation crosses the U64 range for 
snd_BUG_ON. In my eyes, it looks safer to use counter here and do the checks
in the function which uses this value.

>> and improve the timespec64 calculation.
>>
>> The calculation should be split to two parts (tv_sec / tv_nsec):
>>
>> 1) calculate seconds: (frames / rate)
>> 2) calculate the remainder (ns): ((frames % rate) * NSEC_PER_SEC) / rate
>>
>> With 64-bit integer range, we should go up to (for 384000Hz rate):
>>
>> 2**64 / 384000 / 3600 / 24 / 365 = ~1523287 years
> 
> 
> Yes indeed. How about this?
> 
> static inline void snd_pcm_lib_frames_to_timespec64(u64 frames, unsigned int rate, struct timespec64 *audio_tstamp)
> {
> 	u32 remainder;
> 	audio_tstamp->tv_sec = div_u64_rem(frames, rate, &remainder);
> 	audio_tstamp->tv_nsec = div_u64(mul_u32_u32(remainder, NSEC_PER_SEC), rate);

Yes, this looks fine.

					Jaroslav

-- 
Jaroslav Kysela <perex@perex.cz>
Linux Sound Maintainer; ALSA Project; Red Hat, Inc.

Re: Overflow in calculating audio timestamp

[Alan Young]

Hi Jaroslav,

On 04/02/2023 15:40, Jaroslav Kysela wrote:
> For 32-bit apps the boundary is near to UINT32_MAX (see 
> recalculate_boundary() function). So only one crossing point is not 
> enough to cover a decent time range.
>
> There should be a better check, if the add operation crosses the U64 
> range for snd_BUG_ON. In my eyes, it looks safer to use counter here 
> and do the checks
> in the function which uses this value. 


I think you are misunderstanding how crossed_boundary is used. It 
relates to a single call of snd_pcm_update_hw_ptr0(), which should be 
called once per period, or at the very least once per buffer-size. In 
its processing, it may be detected that the boundary has been crossed. 
There are three separate tests that could result in this but only one 
should actually happen during a single call. The snd_BUG_ON() is just to 
detect (report on) a failure in that logic.

None of this restricts the total number of frames that might be 
processed, as a result of multiple boundary crossings.

Changing hw_ptr_wrap to be a boundary-wrap-counter instead of its 
current use as the cumulative number of frames processed at boundary 
wraps would not make any useful difference.

Unless there is something else that I'm missing....

Alan.

Re: Overflow in calculating audio timestamp

[Jaroslav Kysela]

On 06. 02. 23 9:52, Alan Young wrote:
> Hi Jaroslav,
> 
> On 04/02/2023 15:40, Jaroslav Kysela wrote:
>> For 32-bit apps the boundary is near to UINT32_MAX (see
>> recalculate_boundary() function). So only one crossing point is not
>> enough to cover a decent time range.
>>
>> There should be a better check, if the add operation crosses the U64
>> range for snd_BUG_ON. In my eyes, it looks safer to use counter here
>> and do the checks
>> in the function which uses this value.
> 
> 
> I think you are misunderstanding how crossed_boundary is used. It
> relates to a single call of snd_pcm_update_hw_ptr0(), which should be
> called once per period, or at the very least once per buffer-size. In
> its processing, it may be detected that the boundary has been crossed.
> There are three separate tests that could result in this but only one
> should actually happen during a single call. The snd_BUG_ON() is just to
> detect (report on) a failure in that logic.

Oops, the `snd_BUG_ON(crossed_boundary != 1)` check is fine, of course. I 
thought that `if (crossed_boundary)` checks for `if (runtime->hw_ptr_wrap)` 
which has a different meaning. Thank you for your explanation.

> None of this restricts the total number of frames that might be
> processed, as a result of multiple boundary crossings.

Unfortunately, for 64-bit systems, it works only for up to 2 iterations, 
because boundary is nearby LONG_MAX (see snd_pcm_hw_params()).

> Changing hw_ptr_wrap to be a boundary-wrap-counter instead of its
> current use as the cumulative number of frames processed at boundary
> wraps would not make any useful difference.

At least, we should not have a problem even with the 64-bit boundary crossing 
in the hw_ptr0 function. But given the fact, that it's impossible to reach 
this limit, the fix for the timestamp calculation would be sufficient at the 
moment.

And `snd_BUG_ON(runtime->hw_ptr_wrap < runtime->boundary);` check may be 
useful when the hw_ptr_wrap is updated.

			Thanks,
				Jaroslav

-- 
Jaroslav Kysela <perex@perex.cz>
Linux Sound Maintainer; ALSA Project; Red Hat, Inc.

Re: Overflow in calculating audio timestamp

[Pierre-Louis Bossart]

On 2/2/23 07:55, Alan Young wrote:
> sound/core/pcm_lib.c:update_audio_tstamp() contains the following
> calculation:
> 
>         audio_nsecs = div_u64(audio_frames * 1000000000LL,
>                 runtime->rate);
> 
> This will result in a 64-bit overflow after 4.4 days at 48000 Hz, or 1.1
> days at 192000.
> 
> Are you interested in a patch to improve this?
> 
> The same calculation occurs in a couple of other places.

It's clearly unintentional, thanks for reporting this.

I added this in 2012 in

4eeaaeaea1ce ("ALSA: core: add hooks for audio timestamps")

and probably assumed the use of 64-bit was good enough. You just proved
me wrong!