realloc

[Al Bowers]

Al Bowers wrote:




No, not really, the pointer to s2 may become invalid by the realloc call if
s2 == s1 and s1 != realloc(s1, new_size).

I see. Function realloc may possibly move the allocated space
thus making s2 becoming invalid in cases of "self-concatenation"
or partial "self-concatenation".

memmove(tmp+sz1,s2,sz2+1);

Standard C provides function memmove which is similiar to memcpy
but eliminates the overlap problem.

ptrdiff_t d0 = s1 - *pS0;

if ((pTmp = realloc (pTmp, l0 + l1))) {
if (0 <= d0 && (size_t)d0 <= l0) {
--l1;
memcpy (pTmp + l0, pTmp + d0, l1);
pTmp[l0 + l1] = '\000';


I think, this will solve the failure for partial "self-concatenation"

But the function will still exhibit UB with the statement:
ptrdiff_t d0 = s1 - *pS0;
for d0 to be valid, both pointers need to point to elements
of the same array object or one element just past the array
object. This would be the case only for
"self-concatenation" and partial "self-concatenation".
The cases in which *pS0 and s1 are not both pointing to
elements of the same array object, as described above,
will make the use of d0 UB.

 

[CBFalconer]

.... snip ...

I assume you are referring to the overlap hazard involving function
memcpy. If one is to write the function cat to protect against the
overlapUB, you should do more than check for the case of
"self-concatenation". You should prevent all possible cases of
overlap UB, ie. (cat(&s,s+1) where strlen of s is greater than 1.

In strlcpy/strlcat as commonly defined:

size_t strlcpy(char *dst, const char *src, size_t sz);
size_t strlcat(char *dst, const char *src, size_t sz);

the use of sz will normally allow protection against such an
anomaly as issuing:

res = strlcat(dst, strchr(dst, 'X'), maxcapacity);

(which is another justification for my treating NULL as an empty
src string in my implementation of those functions, found at:
<http://cbfalconer.home.att.net/download/>

However, in general would the restrict qualifier afford
protection? I am envisioning something like:

char *s2, s1[SIZE] = "some nonsense";

s2 = strchr(s1, 'n');
... obscurative code ...
if ((strlen(s1) + strlen(s2)) < SIZE) cat(s1, s2)

where cat is the unprotected against length:

char *cat(restrict char *dst, const char *src);

and an inner loop of the form

while (*dst++ = *src++) continue;

will have a few problems terminating. Again, does restrict avoid
this call? Should it? Or should it simply mean "don't do that".

 

[Michael Knaup]

However, in general would the restrict qualifier afford

protection? I am envisioning something like:

char *s2, s1[SIZE] = "some nonsense";

s2 = strchr(s1, 'n');
... obscurative code ...
if ((strlen(s1) + strlen(s2)) < SIZE) cat(s1, s2)

The function cat concatenatiats two "heap" strings allocated by malloc or
realloc. You cannot usage cat with an static array as you did. So there is
no real need for an size information as long as s1 and s2 are (0
terminatet) C strings.

The problem occurs if you do the following with cat

cat (&string, string [+ n]) /* n <= strlen(string) */

Cause of a reallocation (using realloc on string) in cat. The second
argument may become invalid. A solution for this Problem might be the
following code but im not 100% sure if the test for overlapping is valid

char* StrConcat (char ** pS0, const char * const s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
register size_t l0 = (pTmp ? strlen (pTmp) : 0u);
register size_t l1 = strlen (s1);

if ((pTmp = realloc (pTmp, l0 + l1 + 1u))) {
/* Check if s1 is part of *pS0 */
if (*pS0 + l0 == s1 + l1) {
ptrdiff_t d0 = s1 - *pS0;
memcpy (pTmp + l0, pTmp + d0, l1);
} else {
memcpy (pTmp + l0, s1, l1);
}
pTmp[l0 + l1] = '\000';
*pS0 = pTmp;
}

}

return pTmp;
}

 

[Al Bowers]

However, in general would the restrict qualifier afford

protection? I am envisioning something like:

char *s2, s1[SIZE] = "some nonsense";

s2 = strchr(s1, 'n');
... obscurative code ...
if ((strlen(s1) + strlen(s2)) < SIZE) cat(s1, s2)

The function cat concatenatiats two "heap" strings allocated by malloc or
realloc. You cannot usage cat with an static array as you did. So there is
no real need for an size information as long as s1 and s2 are (0
terminatet) C strings.

The problem occurs if you do the following with cat

cat (&string, string [+ n]) /* n <= strlen(string) */

Cause of a reallocation (using realloc on string) in cat. The second
argument may become invalid. A solution for this Problem might be the
following code but im not 100% sure if the test for overlapping is valid

char* StrConcat (char ** pS0, const char * const s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
register size_t l0 = (pTmp ? strlen (pTmp) : 0u);
register size_t l1 = strlen (s1);

if ((pTmp = realloc (pTmp, l0 + l1 + 1u))) {
/* Check if s1 is part of *pS0 */
if (*pS0 + l0 == s1 + l1) {
ptrdiff_t d0 = s1 - *pS0;

I'll mention this again. Isn' t this UB?

From the Standard 6.5.6.9
"When two pointers are subtracted, both shall point to elements
of the same array object, or one past the last element of the
array object; the result is the difference of the subscripts of
the two array elements".

It is quite likely that s1 and *pS0 will NOT be pointers to
elements of the same array object.

memcpy (pTmp + l0, pTmp + d0, l1);
} else {
memcpy (pTmp + l0, s1, l1);
}
pTmp[l0 + l1] = '\000';
*pS0 = pTmp;
}

}

return pTmp;
}

 

[Michael Knaup]

However, in general would the restrict qualifier afford

protection? I am envisioning something like:

char *s2, s1[SIZE] = "some nonsense";

s2 = strchr(s1, 'n');
... obscurative code ...
if ((strlen(s1) + strlen(s2)) < SIZE) cat(s1, s2)

The function cat concatenatiats two "heap" strings allocated by malloc or
realloc. You cannot usage cat with an static array as you did. So there
is no real need for an size information as long as s1 and s2 are (0
terminatet) C strings.

The problem occurs if you do the following with cat

cat (&string, string [+ n]) /* n <= strlen(string) */

Cause of a reallocation (using realloc on string) in cat. The second
argument may become invalid. A solution for this Problem might be the
following code but im not 100% sure if the test for overlapping is valid

char* StrConcat (char ** pS0, const char * const s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
register size_t l0 = (pTmp ? strlen (pTmp) : 0u);
register size_t l1 = strlen (s1);

if ((pTmp = realloc (pTmp, l0 + l1 + 1u))) {
/* Check if s1 is part of *pS0 */
if (*pS0 + l0 == s1 + l1) {
ptrdiff_t d0 = s1 - *pS0;

I'll mention this again. Isn' t this UB?

From the Standard 6.5.6.9
"When two pointers are subtracted, both shall point to elements
of the same array object, or one past the last element of the
array object; the result is the difference of the subscripts of
the two array elements".

It is quite likely that s1 and *pS0 will NOT be pointers to
elements of the same array object.

I'm not sure but, I think that
*pS0 + l0 == *s1 + l1
is only true when they both point to the same object and in this case
d0 = s1 - *pS0
is valid.

memcpy (pTmp + l0, pTmp + d0, l1);
} else {
memcpy (pTmp + l0, s1, l1);
}
pTmp[l0 + l1] = '\000';
*pS0 = pTmp;
}

}

return pTmp;
}

 

[Al Bowers]

Al Bowers wrote:

However, in general would the restrict qualifier afford


protection? I am envisioning something like:

char *s2, s1[SIZE] = "some nonsense";

s2 = strchr(s1, 'n');
... obscurative code ...
if ((strlen(s1) + strlen(s2)) < SIZE) cat(s1, s2)


The function cat concatenatiats two "heap" strings allocated by malloc or
realloc. You cannot usage cat with an static array as you did. So there
is no real need for an size information as long as s1 and s2 are (0
terminatet) C strings.

The problem occurs if you do the following with cat

cat (&string, string [+ n]) /* n <= strlen(string) */

Cause of a reallocation (using realloc on string) in cat. The second
argument may become invalid. A solution for this Problem might be the
following code but im not 100% sure if the test for overlapping is valid

char* StrConcat (char ** pS0, const char * const s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
register size_t l0 = (pTmp ? strlen (pTmp) : 0u);
register size_t l1 = strlen (s1);

if ((pTmp = realloc (pTmp, l0 + l1 + 1u))) {
/* Check if s1 is part of *pS0 */
if (*pS0 + l0 == s1 + l1) {
ptrdiff_t d0 = s1 - *pS0;

I'll mention this again. Isn' t this UB?

From the Standard 6.5.6.9
"When two pointers are subtracted, both shall point to elements
of the same array object, or one past the last element of the
array object; the result is the difference of the subscripts of
the two array elements".

It is quite likely that s1 and *pS0 will NOT be pointers to
elements of the same array object.

I'm not sure but, I think that
*pS0 + l0 == *s1 + l1
is only true when they both point to the same object and in this case
d0 = s1 - *pS0
is valid.

After posting, I saw what you have made a change. I tried
to cancel the post.

I do have one area of concern and would like for you to look
at and possiby respond.

The expression *pS0 +10 appears to me to be UB when
*pS0 is a null pointer. From looking at the flow it seems
possible that *pS0 can have the NULL value.

The Standard says:
1. When an expression that has integer type is added to
or subtracted from a pointer, the result has the type of
the pointer operand.

2. If both the pointer operand and the result point to elements
of the same array object, or one past the last element of the
array object, the evaluation shall not produce an overflow;
otherwise, the behavior is undefined.

So the expression (*pS0 + l0) will yield a char *type.
And, if *pS0 is a null pointer(value is NULL), then the result,
a char *type, would not be pointing to a defined array type as
pS0 will not be pointing to a defined array type.

Because of this I would change the if statement to:

if(*pS0 && (*pS0 + l0 == s1 + l1))

memcpy (pTmp + l0, pTmp + d0, l1);
} else {
memcpy (pTmp + l0, s1, l1);
}
pTmp[l0 + l1] = '\000';
*pS0 = pTmp;
}

}

return pTmp;
}

 

[Michael Knaup]

Al Bowers wrote:

if(*pS0 && (*pS0 + l0 == s1 + l1))

Yes you are right, this must be added, thanks ;-).

 

[Al Bowers]

Al Bowers wrote:

However, in general would the restrict qualifier afford


protection? I am envisioning something like:

char *s2, s1[SIZE] = "some nonsense";

s2 = strchr(s1, 'n');
... obscurative code ...
if ((strlen(s1) + strlen(s2)) < SIZE) cat(s1, s2)


The function cat concatenatiats two "heap" strings allocated by malloc or
realloc. You cannot usage cat with an static array as you did. So there
is no real need for an size information as long as s1 and s2 are (0
terminatet) C strings.

The problem occurs if you do the following with cat

cat (&string, string [+ n]) /* n <= strlen(string) */

Cause of a reallocation (using realloc on string) in cat. The second
argument may become invalid. A solution for this Problem might be the
following code but im not 100% sure if the test for overlapping is valid

char* StrConcat (char ** pS0, const char * const s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
register size_t l0 = (pTmp ? strlen (pTmp) : 0u);
register size_t l1 = strlen (s1);

if ((pTmp = realloc (pTmp, l0 + l1 + 1u))) {
/* Check if s1 is part of *pS0 */
if (*pS0 + l0 == s1 + l1) {
ptrdiff_t d0 = s1 - *pS0;

I'll mention this again. Isn' t this UB?

From the Standard 6.5.6.9
"When two pointers are subtracted, both shall point to elements
of the same array object, or one past the last element of the
array object; the result is the difference of the subscripts of
the two array elements".

It is quite likely that s1 and *pS0 will NOT be pointers to
elements of the same array object.

I'm not sure but, I think that
*pS0 + l0 == *s1 + l1
is only true when they both point to the same object and in this case
d0 = s1 - *pS0
is valid.

I had a concern that *pS0 might have value NULL in expression
*pS0 + l0. But, I see that it can't so the code looks fine to me.

memcpy (pTmp + l0, pTmp + d0, l1);
} else {
memcpy (pTmp + l0, s1, l1);
}
pTmp[l0 + l1] = '\000';
*pS0 = pTmp;
}

}

return pTmp;
}

 

[Michael Knaup]

I had a concern that *pS0 might have value NULL in expression
*pS0 + l0. But, I see that it can't so the code looks fine to me.

Sorry, that i've to say that *pS0 == NULL is true if you call Concat
in this way

char *string = NULL

Concat(&string, "ho");

So you were right with your concern.

 

[Flash Gordon]

However, in general would the restrict qualifier afford

protection? I am envisioning something like:

char *s2, s1[SIZE] = "some nonsense";

s2 = strchr(s1, 'n');
... obscurative code ...
if ((strlen(s1) + strlen(s2)) < SIZE) cat(s1, s2)

The function cat concatenatiats two "heap" strings allocated by malloc or
realloc. You cannot usage cat with an static array as you did. So there is
no real need for an size information as long as s1 and s2 are (0
terminatet) C strings.

The problem occurs if you do the following with cat

cat (&string, string [+ n]) /* n <= strlen(string) */

Cause of a reallocation (using realloc on string) in cat. The second
argument may become invalid. A solution for this Problem might be the
following code but im not 100% sure if the test for overlapping is valid

char* StrConcat (char ** pS0, const char * const s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
register size_t l0 = (pTmp ? strlen (pTmp) : 0u);
register size_t l1 = strlen (s1);

Using names l0 and l1 is a horrible thing to do since they look too much
like 10 and 11.

if ((pTmp = realloc (pTmp, l0 + l1 + 1u))) {
/* Check if s1 is part of *pS0 */
if (*pS0 + l0 == s1 + l1) {

If the realloc moves the block then evaluating a pointer in to where is
used to be (i.e. *pS0) invokes undefined behaviour. So you need to do
this check before the realloc.

ptrdiff_t d0 = s1 - *pS0;

Again, if the block has been moved by the realloc you are evaluating an
invalid pointer invoking undefined behaviour. So you need to work this
out before the realloc.

memcpy (pTmp + l0, pTmp + d0, l1);
} else {
memcpy (pTmp + l0, s1, l1);
}
pTmp[l0 + l1] = '\000';
*pS0 = pTmp;
}

}

return pTmp;
}

How about:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stddef.h>

char* StrConcat (char **pS0, const char *s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
ptrdiff_t offset;
size_t len0 = (pTmp ? strlen(pTmp) : 0);
size_t len1 = strlen(s1);
int overlapping = 0;

/* Check if s1 is part of *pS0 */
if (pTmp + len0 == s1 + len1) {
overlapping = 1;
offset = s1 - pTmp;
}

if ((pTmp = realloc(pTmp, len0 + len1 + 1))) {
if (overlapping)
s1 = pTmp + offset;
memcpy(pTmp + len0, s1, len1);
pTmp[len0 + len1] = '\0';
*pS0 = pTmp;
}

}

return pTmp;
}

int main(void)
{
char *tmp;
char *s = NULL;
tmp = StrConcat(&s,"oh");
printf("%s\n",tmp);
s = StrConcat(&tmp,"haha");
printf("%s\n",s);
return 0;
}

 

[CBFalconer]

However, in general would the restrict qualifier afford
protection? I am envisioning something like:

char *s2, s1[SIZE] = "some nonsense";

s2 = strchr(s1, 'n');
... obscurative code ...
if ((strlen(s1) + strlen(s2)) < SIZE) cat(s1, s2)

The function cat concatenatiats two "heap" strings allocated by
malloc or realloc. You cannot usage cat with an static array as
you did. So there is no real need for an size information as long
as s1 and s2 are (0 terminatet) C strings.

I gave the prototype for the cat I was discussing as:

char *cat(restrict char *dst, const char *src);

which in no way restricts the strings to be in memory allocated by
malloc etc. There is no way, in standard C, to so restrict
parameters, and any code that requires it is a bomb waiting to
explode. It is so silly a practice that I never conceived anyone
would write code requiring it.

 

[Al Bowers]

Michael Knaup wrote:

The function cat concatenatiats two "heap" strings allocated by malloc or
realloc. You cannot usage cat with an static array as you did. So
there is
no real need for an size information as long as s1 and s2 are (0
terminatet) C strings.

The problem occurs if you do the following with cat
cat (&string, string [+ n]) /* n <= strlen(string) */

Cause of a reallocation (using realloc on string) in cat. The second
argument may become invalid. A solution for this Problem might be the
following code but im not 100% sure if the test for overlapping is valid

char* StrConcat (char ** pS0, const char * const s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
register size_t l0 = (pTmp ? strlen (pTmp) : 0u);
register size_t l1 = strlen (s1);
if ((pTmp = realloc (pTmp, l0 + l1 + 1u))) {
/* Check if s1 is part of *pS0 */
if (*pS0 + l0 == s1 + l1) {

If the realloc moves the block then evaluating a pointer in to where is
used to be (i.e. *pS0) invokes undefined behaviour. So you need to do
this check before the realloc.

Yes, this appears to be UB.

ptrdiff_t d0 = s1 - *pS0;

Again, if the block has been moved by the realloc you are evaluating an
invalid pointer invoking undefined behaviour. So you need to work this
out before the realloc.

memcpy (pTmp + l0, pTmp + d0, l1);
} else {
memcpy (pTmp + l0, s1, l1);
}
pTmp[l0 + l1] = '\000';
*pS0 = pTmp;
}

}

return pTmp;
}

How about:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stddef.h>

char* StrConcat (char **pS0, const char *s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
ptrdiff_t offset;
size_t len0 = (pTmp ? strlen(pTmp) : 0);
size_t len1 = strlen(s1);
int overlapping = 0;

/* Check if s1 is part of *pS0 */
if (pTmp + len0 == s1 + len1) {

(pTmp + len0) has the look of undefined behavior. The flow
of the code seems to indicate that it is possible for tTmp
to have the value of NULL. The additition of len0 to pTmp,
a type char * result, does not appear valid if pTmp
is a null pointer.
Perhaps, to make it safe, use:
if(pTmp && (pTmp + len0 == s1 + len1))

overlapping = 1;
offset = s1 - pTmp;
}

if ((pTmp = realloc(pTmp, len0 + len1 + 1))) {
if (overlapping)
s1 = pTmp + offset;
memcpy(pTmp + len0, s1, len1);
pTmp[len0 + len1] = '\0';
*pS0 = pTmp;
}

}

return pTmp;
}

int main(void)
{
char *tmp;
char *s = NULL;
tmp = StrConcat(&s,"oh");
printf("%s\n",tmp);
s = StrConcat(&tmp,"haha");
printf("%s\n",s);
return 0;
}

 

[Chris Torek]

I gave the prototype for the cat I was discussing as:
char *cat(restrict char *dst, const char *src);

Just an aside (as I think this whole thread is a bit silly ),
but assuming this is the C99 "restrict", you want to have it
occur elsewhere in the type:

char *cat(char *restrict dst, const char *src);

or more likely:

char *cat(char *restrict dst, const char *restrict src);

which matches the C99 strcpy() and strcat() prototypes.

Note that "restrict" is a constraint on the person using the
function: compilers need not, and in general cannot, check whether
the restriction is satisified by any given call.

 

[Flash Gordon]

Michael Knaup wrote:

The function cat concatenatiats two "heap" strings allocated by
malloc or
realloc. You cannot usage cat with an static array as you did. So
there is
no real need for an size information as long as s1 and s2 are (0
terminatet) C strings.

The problem occurs if you do the following with cat
cat (&string, string [+ n]) /* n <= strlen(string) */

Cause of a reallocation (using realloc on string) in cat. The second
argument may become invalid. A solution for this Problem might be the
following code but im not 100% sure if the test for overlapping is valid

char* StrConcat (char ** pS0, const char * const s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
register size_t l0 = (pTmp ? strlen (pTmp) : 0u);
register size_t l1 = strlen (s1);
if ((pTmp = realloc (pTmp, l0 + l1 + 1u))) {
/* Check if s1 is part of *pS0 */
if (*pS0 + l0 == s1 + l1) {

If the realloc moves the block then evaluating a pointer in to where
is used to be (i.e. *pS0) invokes undefined behaviour. So you need to
do this check before the realloc.

Yes, this appears to be UB.

ptrdiff_t d0 = s1 - *pS0;

Again, if the block has been moved by the realloc you are evaluating
an invalid pointer invoking undefined behaviour. So you need to work
this out before the realloc.

memcpy (pTmp + l0, pTmp + d0, l1);
} else {
memcpy (pTmp + l0, s1, l1);
}
pTmp[l0 + l1] = '\000';
*pS0 = pTmp;
}

}

return pTmp;
}

How about:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stddef.h>

char* StrConcat (char **pS0, const char *s1)
{
char *pTmp = (pS0 ? *pS0 : (pS0 = &pTmp, NULL));

if (s1) {
ptrdiff_t offset;
size_t len0 = (pTmp ? strlen(pTmp) : 0); ^^^^^^^^^^^^^^^^^^^^^^^
size_t len1 = strlen(s1);
int overlapping = 0;

/* Check if s1 is part of *pS0 */
if (pTmp + len0 == s1 + len1) {

(pTmp + len0) has the look of undefined behavior. The flow
of the code seems to indicate that it is possible for tTmp
to have the value of NULL. The additition of len0 to pTmp,
a type char * result, does not appear valid if pTmp
is a null pointer.

If pTmp is NULL then len0 is 0. Is it legal to add 0 to a NULL pointer?

Perhaps, to make it safe, use:
if(pTmp && (pTmp + len0 == s1 + len1))

Yes, that is definitely safe.

<snip>

 

[CBFalconer]

Just an aside (as I think this whole thread is a bit silly ),
but assuming this is the C99 "restrict", you want to have it
occur elsewhere in the type:

char *cat(char *restrict dst, const char *src);

or more likely:

char *cat(char *restrict dst, const char *restrict src);

which matches the C99 strcpy() and strcat() prototypes.

Note that "restrict" is a constraint on the person using the
function: compilers need not, and in general cannot, check
whether the restriction is satisified by any given call.

Am I correct if I say the restrict simply warns the user that this
function makes some assumptions about the pointer(s) it is
receiving, and that it is very likely to go howling off into the
boondocks if those assumptions are not met? I.e. it has no more
real effect than a notation in the function documentation.

 

[Keith Thompson]

Am I correct if I say the restrict simply warns the user that this
function makes some assumptions about the pointer(s) it is
receiving, and that it is very likely to go howling off into the
boondocks if those assumptions are not met? I.e. it has no more
real effect than a notation in the function documentation.

As I understand it, "restrict" causes certain things to become
undefined behavior that would not have been undefined behavior in the
absence of the "restrict". In other words, it gives the compiler
permission to perform optimizations based on the assumption that those
things will not occur. It then becomes the programmer's
responsibility to ensure that the compiler's assumptions are not
violated. (A conforming compiler could simply ignore "restrict".)

 

[Richard Bos]

However, in general would the restrict qualifier afford

protection? I am envisioning something like:

char *s2, s1[SIZE] = "some nonsense";

s2 = strchr(s1, 'n');
... obscurative code ...
if ((strlen(s1) + strlen(s2)) < SIZE) cat(s1, s2)

The function cat concatenatiats two "heap" strings allocated by malloc or
realloc.

Well... the first string must be allocated (or a null pointer), since it
is realloc()ed. The second string can come from anywhere, as long as
it's a correct string.

Richard