Better alternative to strncpy in QEMU.

Better alternative to strncpy in QEMU.

[Chetan]

[-- Attachment #1: Type: text/plain, Size: 2814 bytes --]

Hello All,

This mail is in reference to one of the tasks mentioned in '
*Contribute/BiteSizedTasks*' in QEMU wiki, under '*API conversion*' which
states to introduce a better alternative to strncpy function. I've drafted
and tested below implementation for the same. Before proceeding with any
changes in QEMU code can you all please go through it and suggest
changes/corrections if required.




































































*/* This function is introduced in place of strncpy(), it asserts if
destination * is large enough to fit strlen(source)+1 bytes and guarantees
null termination * in destination string. * * char source[], is expecting a
pointer to the source where data should be copied * from. * * char
destination[], is expecting a pointer to the destination where data
should * be copied to. * * size_t destination_size, is expecting size of
destination. * In case of char[], sizeof() function can be used to find the
size. * In case of char *, provide value which was passed to malloc()
function for * memory allocation. */char *qemu_strncpy(char destination[],
char source[], size_t destination_size){    /* Looping through the array
and copying the characters from     * source to destination.     */    for
(int i = 0; i < strlen(source); i++) {        destination[i] = source[i];
      /* Check if value of i is equal to the second last index         * of
destination array and if condition is true, mark last         * index as
NULL and break from the loop.         */        if (i == (destination_size
- 2)) {            destination[destination_size - 1] = '\0';
break;        }    }    return destination;}/* This function is introduced
in place of strncpy(), it asserts if destination * is large enough to fit
strlen(source) bytes and does not guarantee null * termination in
destination string. * * char source[], is expecting a pointer to the source
where data should be copied * from. * * char destination[], is expecting a
pointer to the destination where data should * be copied to. * * size_t
destination_size, is expecting size of destination. * In case of char[],
sizeof() function can be used to find the size. * In case of char *,
provide value which was passed to malloc() function for * memory
allocation. */char *qemu_strncpy_nonul(char destination[], char source[],
size_t destination_size){    /* Looping through the array and copying the
characters from     * source to destination.     */    for (int i = 0; i <
strlen(source); i++) {        destination[i] = source[i];        /* Check
if value of i is equal to the last index         * of the destination array
and if condition is true,         * break from the loop.         */
if (i == (destination_size - 1)) {            break;        }    }
return destination;} *

Regards,
Chetan P.

[-- Attachment #2: Type: text/html, Size: 3356 bytes --]

Re: Better alternative to strncpy in QEMU.

[Thomas Huth]

On 11/04/2021 15.50, Chetan wrote:
> Hello All,
> 
> This mail is in reference to one of the tasks mentioned in 
> '/Contribute/BiteSizedTasks/' in QEMU wiki, under '/API conversion/' which 
> states to introduce a better alternative to strncpy function.

Looks like this task has been added by Paolo, so I'm adding him to Cc: now.

( 
https://wiki.qemu.org/index.php?title=Contribute/BiteSizedTasks&diff=9130&oldid=9045 
)

> I've drafted 
> and tested below implementation for the same. Before proceeding with any 
> changes in QEMU code can you all please go through it and suggest 
> changes/corrections if required.
> 
> //* This function is introduced in place of strncpy(), it asserts if destination
>   * is large enough to fit strlen(source)+1 bytes and guarantees null 
> termination
>   * in destination string.
>   *
>   * char source[], is expecting a pointer to the source where data should be 
> copied
>   * from.
>   *
>   * char destination[], is expecting a pointer to the destination where data 
> should
>   * be copied to.
>   *
>   * size_t destination_size, is expecting size of destination.
>   * In case of char[], sizeof() function can be used to find the size.
>   * In case of char *, provide value which was passed to malloc() function for
>   * memory allocation.
>   */
> char *qemu_strncpy(char destination[], char source[], size_t destination_size)

Please use "*destination" and "*source" instead of "destination[]" and 
"source[]" here.

> {
>      /* Looping through the array and copying the characters from
>       * source to destination.
>       */
>      for (int i = 0; i < strlen(source); i++) {
>          destination[i] = source[i];
> 
>          /* Check if value of i is equal to the second last index
>           * of destination array and if condition is true, mark last
>           * index as NULL and break from the loop.
>           */
>          if (i == (destination_size - 2)) {
>              destination[destination_size - 1] = '\0';
>              break;
>          }
>      }
>      return destination;
> }

I think this is pretty much the same as g_strlcpy() from the glib:

https://developer.gnome.org/glib/2.66/glib-String-Utility-Functions.html#g-strlcpy

So I guess Paolo had something different in mind when adding this task?

> /* This function is introduced in place of strncpy(), it asserts if destination
>   * is large enough to fit strlen(source) bytes and does not guarantee null
>   * termination in destination string.
>   *
>   * char source[], is expecting a pointer to the source where data should be 
> copied
>   * from.
>   *
>   * char destination[], is expecting a pointer to the destination where data 
> should
>   * be copied to.
>   *
>   * size_t destination_size, is expecting size of destination.
>   * In case of char[], sizeof() function can be used to find the size.
>   * In case of char *, provide value which was passed to malloc() function for
>   * memory allocation.
>   */
> char *qemu_strncpy_nonul(char destination[], char source[], size_t 
> destination_size)
> {
>      /* Looping through the array and copying the characters from
>       * source to destination.
>       */
>      for (int i = 0; i < strlen(source); i++) {
>          destination[i] = source[i];
> 
>          /* Check if value of i is equal to the last index
>           * of the destination array and if condition is true,
>           * break from the loop.
>           */
>          if (i == (destination_size - 1)) {
>              break;
>          }
>      }
>      return destination;
> } /

I'm not sure what's the improvement over strncpy() here? Paolo, could you 
elaborate?
(Note that we also have some functions like strpadcpy() in QEMU already, 
which can be used in similar ways)

  Thomas

Re: Better alternative to strncpy in QEMU.

[Peter Maydell]

On Sun, 11 Apr 2021 at 14:52, Chetan <chetan4windows@gmail.com> wrote:
> char *qemu_strncpy(char destination[], char source[], size_t destination_size)
> {
>     /* Looping through the array and copying the characters from
>      * source to destination.
>      */
>     for (int i = 0; i < strlen(source); i++) {
>         destination[i] = source[i];
>
>         /* Check if value of i is equal to the second last index
>          * of destination array and if condition is true, mark last
>          * index as NULL and break from the loop.
>          */
>         if (i == (destination_size - 2)) {
>             destination[destination_size - 1] = '\0';
>             break;
>         }
>     }
>     return destination;
> }

This implementation is "accidentally quadratic", because it
calls strlen(source) every time through the loop, and thus
copying an N byte string will read N*N bytes of memory. (The
compiler can't pull the "strlen(source)" call up out of the loop
because it can't guarantee that source and destination don't
overlap.)

I think this is a good illustration of why we probably don't want
to roll our own string operation functions if we can avoid it
(ie without having a clear view of why we are improving on either
what libc or glib offer us).

thanks
-- PMM

Re: Better alternative to strncpy in QEMU.

[Chetan]

[-- Attachment #1: Type: text/plain, Size: 2935 bytes --]

Hello All,

> I'm not sure what's the improvement over strncpy() here? Paolo, could you
> elaborate?
> (Note that we also have some functions like strpadcpy() in QEMU already,
> which can be used in similar ways)

Ok Thanks, I'll wait for Paolo to clarify if the functions are needed, if
yes then whether my understanding
is correct. If not, then I'll drop this and pick another one.

> Please use "*destination" and "*source" instead of "destination[]" and
> "source[]" here.

@Thomas Thanks for the input, I'll change it accordingly.

> This implementation is "accidentally quadratic", because it
> calls strlen(source) every time through the loop, and thus
> copying an N byte string will read N*N bytes of memory. (The
> compiler can't pull the "strlen(source)" call up out of the loop
> because it can't guarantee that source and destination don't
> overlap.)

@Peter Thanks for the input, I'll be using a while loop instead, as Bruno
suggested. Also, I will only continue with this task after Paolo's input.

> One other optimization that could be done (but is a bigger headache to
implement correctly) would be to cast the char* into uint64_t* (or
uint32_t* for 32-bit >systems) and copy more bytes at a time. The headache
comes from finding a 0 in this longer variable, but you can probably use a
similar strategy to freebsd's > strlen (
https://github.com/freebsd/freebsd-src/blob/main/lib/libc/string/strlen.c).

@Bruno Thanks I'll check out freebsd code.

Thanks and Regards,
Chetan P.

On Mon, Apr 12, 2021 at 6:50 PM Peter Maydell <peter.maydell@linaro.org>
wrote:

> On Sun, 11 Apr 2021 at 14:52, Chetan <chetan4windows@gmail.com> wrote:
> > char *qemu_strncpy(char destination[], char source[], size_t
> destination_size)
> > {
> >     /* Looping through the array and copying the characters from
> >      * source to destination.
> >      */
> >     for (int i = 0; i < strlen(source); i++) {
> >         destination[i] = source[i];
> >
> >         /* Check if value of i is equal to the second last index
> >          * of destination array and if condition is true, mark last
> >          * index as NULL and break from the loop.
> >          */
> >         if (i == (destination_size - 2)) {
> >             destination[destination_size - 1] = '\0';
> >             break;
> >         }
> >     }
> >     return destination;
> > }
>
> This implementation is "accidentally quadratic", because it
> calls strlen(source) every time through the loop, and thus
> copying an N byte string will read N*N bytes of memory. (The
> compiler can't pull the "strlen(source)" call up out of the loop
> because it can't guarantee that source and destination don't
> overlap.)
>
> I think this is a good illustration of why we probably don't want
> to roll our own string operation functions if we can avoid it
> (ie without having a clear view of why we are improving on either
> what libc or glib offer us).
>
> thanks
> -- PMM
>

[-- Attachment #2: Type: text/html, Size: 4351 bytes --]

Re: Better alternative to strncpy in QEMU.

[Paolo Bonzini]

On 12/04/21 06:51, Thomas Huth wrote:
>>
> 
> I think this is pretty much the same as g_strlcpy() from the glib:
> 
> https://developer.gnome.org/glib/2.66/glib-String-Utility-Functions.html#g-strlcpy 
> 
> So I guess Paolo had something different in mind when adding this task?

Yes, I did.  strncpy is used legitimately when placing data in a 
fixed-size buffer that is written to a socket, to a file or to guest 
memory.  The problem with using g_strlcpy in those cases is that it does 
not write past the first '\0' character, and therefore it can leak host 
data.

What I had in mind was basically strncpy plus an assertion that the last 
copied byte will be set to 0.  It can be written in many ways, for 
example strncpy followed by assert(dest[destlen - 1] == '\0'), or like 
assert(strlen(src) < destlen) followed by strncpy, or of course you 
could write a for loop by hand.

Once you do that, you can split uses of strncpy in two: those where the 
reader expects the last byte to be zero, and those where the reader does 
not.  (I don't expect many cases of the first type, because the reader 
always has to think of how to handle a malicious data stream that does 
not have a zero termination).

As long as you avoid the accidentally quadratic behavior that Peter 
pointed out, any way is fine since performance does not matter on these 
paths.  Making the code nice and readable is more important.

Paolo

RE: Better alternative to strncpy in QEMU.

[Bruno Piazera Larsen]

[-- Attachment #1: Type: text/plain, Size: 1706 bytes --]

Im not sure about what "better version" means, but my guess would be a faster or more reliable version. If that's the case:

>     for (int i = 0; i < strlen(source); i++) {

Since you're going on ebyte at a time, there's no need to know how big the array is. As a stopping condition you could use source[i] != '\0', which is one less pass through the array.

One other optimization that could be done (but is a bigger headache to implement correctly) would be to cast the char* into uint64_t* (or uint32_t* for 32-bit systems) and copy more bytes at a time. The headache comes from finding a 0 in this longer variable, but you can probably use a similar strategy to freebsd's strlen (https://github.com/freebsd/freebsd-src/blob/main/lib/libc/string/strlen.c).

I'm not sure if it would be a real speedup in most cases, since glibc can use this strategy already), but at least we'd have consistent performance in case some system doesn't use it


Bruno Piazera Larsen

Instituto de Pesquisas ELDORADO<http://clickemailmkt.eldorado.org.br/ls/click?upn=UPoxpeIcHnAcbUZyo7TTaswyiVb1TXP3jEbQqiiJKKGsxOn8hBEs5ZsMLQfXkKuKXZ7MVDg0ij9eG8HV4TXI75dBzDiNGLxQ8Xx5PzCVNt6TpGrzBbU-2Biu0o69X5ce-2FW-2FOk1uUipuK0fZnWXJEgbRw-3D-3DJY4T_wWk-2BG6VvNBoa1YzxYjhCdFS9IfANIaBzDSklR1NyyrKOI1wj0P-2BdBFcuO4FnHcsA1MyHu0ly1Yt3oDMp7KKdJPM68iKuI2jiRH5v4B0d8wf3chU3qy5n5iXWnW1QjSaNFHOgELzxaP-2FnesTeBgJ5dFkjH4f279sVQpOtyjw5xAqj34M6pgNRAxVvuXif4IWDcVzXg1FzfYlEfkKzr9vvpA3Hg8kitwMtlU3zwbQUBCgL30fQoJPcRPMGKyOY8RmoAlXNqTJYDYIvqmfnI7KLUvw6vKB5R-2B5q1FJRAzX7H-2BmF0NnDET6jMLuIqtCcVIch>

Departamento Computação Embarcada

Analista de Software Trainee

Aviso Legal - Disclaimer<https://www.eldorado.org.br/disclaimer.html>

[-- Attachment #2: Type: text/html, Size: 4055 bytes --]