pointer cast UB?

[Serve Lau]

Some of you may be aware of the "bucket technique" to create linked lists or
any data structure in C in a general way. I was wondering if there's any UB
involved in the following snippet, especially newsym/freesym functions and
when the returned pointer is used in between



typedef struct BUCKET {

struct fs_BUCKET *Next;

struct fs_BUCKET **Prev;

} BUCKET;

typedef struct DATA_LIST {

size_t Size;

BUCKET *First;

} DATA_LIST;

void *newsym(size_t Size) {

BUCKET *p = malloc(Size + sizeof *p);

return p ? p + 1 : NULL;

}

void freesym(void *p) {

free((BUCKET *)p - 1);

}

 

[Harald van =?UTF-8?B?RMSzaw==?=]

Some of you may be aware of the "bucket technique" to create linked lists
or any data structure in C in a general way. I was wondering if there's
any UB involved in the following snippet, especially newsym/freesym
functions and when the returned pointer is used in between



typedef struct BUCKET {

struct fs_BUCKET *Next;

struct fs_BUCKET **Prev;

} BUCKET;

typedef struct DATA_LIST {

size_t Size;

BUCKET *First;

} DATA_LIST;

void *newsym(size_t Size) {

BUCKET *p = malloc(Size + sizeof *p);

return p ? p + 1 : NULL;

}

void freesym(void *p) {

free((BUCKET *)p - 1);

}

There is no guarantee that the result of newsym is properly aligned for any
structure, and mostly any type, other than struct BUCKET itself.

 

[Flash Gordon]

Serve Lau wrote, On 06/07/07 17:38:

Some of you may be aware of the "bucket technique" to create linked lists or
any data structure in C in a general way. I was wondering if there's any UB
involved in the following snippet, especially newsym/freesym functions and
when the returned pointer is used in between

typedef struct BUCKET {
struct fs_BUCKET *Next;
struct fs_BUCKET **Prev;
} BUCKET;

typedef struct DATA_LIST {
size_t Size;
BUCKET *First;
} DATA_LIST;

void *newsym(size_t Size) {
BUCKET *p = malloc(Size + sizeof *p);
return p ? p + 1 : NULL;
}

void freesym(void *p) {
free((BUCKET *)p - 1);

If passed a null pointer this invokes UB. Try:
if (p) free((BUCKET)p - 1);

}

There is no UB directly in the snippet you provide, but there could be
UB in the code using it. Specifically, there is no guarantee that p+1 is
correctly aligned for anything other than a BUCKET.

I'm also assuming the real code will initialise the "hidden" pointers
before they are used.

 

[Serve Lau]

If passed a null pointer this invokes UB. Try:
if (p) free((BUCKET)p - 1);

so this will be UB then?

typedef struct
{
int x;
} SomeStruct;

SomeStruct *s = newsym(sizeof *s);

if (s)
s->x = 10;

freesym(s);

 

[Flash Gordon]

Serve Lau wrote, On 06/07/07 21:52:

so this will be UB then?

typedef struct
{
int x;
} SomeStruct;

SomeStruct *s = newsym(sizeof *s);

if (s)
s->x = 10;

This will be UB *if* the malloc succeeded AND s is not correctly
aligned. If s is correctly aligned you are fine. Of course, there is no
way to ensure that s is correctly aligned.

freesym(s);

Without my fix this is UB if malloc failed (or rather the UB will occur
within freesym) but with my fix this is fine.

 

[Eric Sosman]

Serve Lau wrote On 07/06/07 16:52,:

so this will be UB then?

typedef struct
{
int x;
} SomeStruct;

SomeStruct *s = newsym(sizeof *s);

if (s)
s->x = 10;

freesym(s);

Yes, or "potentially." If SomeStruct requires
stricter alignment than BUCKET, the value returned
by newsym will not satisfy that stricter requirement.
What happens next is anyone's guess: You might get
trouble on assigning the bad value to s, you might
have no trouble until trying to use s->x, the access
to s->x might appear to work all right but end up
corrupting the data in the BUCKET before it, the
code might even work but run inexplicably slowly ...
Or, of course, demons might fly out of your nose.

The "traditional" way to get around this issue is
to use a union of a lot of types that are likely to
have comparatively strict alignment requirements:

union align {
BUCKET bucket;
int i;
long l;
long long ll;
double d;
long double ld;
void *vp;
void (*fp)(void);
};

.... and then you allocate space for a `union align'
just before the "payload," and use the BUCKET that's
inside that union. The problem is that you cannot
enumerate all possible types (the C programmer can
invent new ones), so you cannot be 100% sure the
union's alignment is truly the strictest of all.
Also, on a system with relatively weak alignment
requirements this approach may use more memory than
is really needed.

 

[Frodo Baggins]

Some of you may be aware of the "bucket technique" to create linked lists or
any data structure in C in a general way. I was wondering if there's any UB
involved in the following snippet, especially newsym/freesym functions and
when the returned pointer is used in between

typedef struct BUCKET {

struct fs_BUCKET *Next;

struct fs_BUCKET **Prev;

} BUCKET;

typedef struct DATA_LIST {

size_t Size;

BUCKET *First;

} DATA_LIST;

void *newsym(size_t Size) {

BUCKET *p = malloc(Size + sizeof *p);

return p ? p + 1 : NULL;

}

void freesym(void *p) {

free((BUCKET *)p - 1);

}

Any reason why BUCKET.Next is a struct fs_Bucket * whereas BUCKET.Prev
is a struct fs_Bucket ** ?

Regards,
Frodo B

 

[Serve Lau]

Any reason why BUCKET.Next is a struct fs_Bucket * whereas BUCKET.Prev
is a struct fs_Bucket ** ?

Regards,
Frodo B

The reason is I removed distracting company coding standard thingies and I
forgot those

 

[Serve Lau]

Serve Lau wrote On 07/06/07 16:52,:
The "traditional" way to get around this issue is
to use a union of a lot of types that are likely to
have comparatively strict alignment requirements:

... and then you allocate space for a `union align'
just before the "payload," and use the BUCKET that's
inside that union. The problem is that you cannot
enumerate all possible types (the C programmer can
invent new ones), so you cannot be 100% sure the
union's alignment is truly the strictest of all.
Also, on a system with relatively weak alignment
requirements this approach may use more memory than
is really needed.

Think I can be sure enough. Thanks for the advice!

 

[Serve Lau]

union align {
BUCKET bucket;
int i;
long l;
long long ll;
double d;
long double ld;
void *vp;
void (*fp)(void);
};

So when having the align struct all I have to do is change the newsym and
freesym functions into the union? The rest can keep the BUCKET pointers?
void *newsym(size_t Size)

{

union align *sym = malloc(Size + sizeof *sym);

return sym ? &sym->Bucket + 1 : NULL;

}

void freesym(void *sym)

{

if (sym != NULL)

free((union align*)sym - 1);

}

 

[Eric Sosman]

So when having the align struct all I have to do is change the newsym and
freesym functions into the union? The rest can keep the BUCKET pointers?
void *newsym(size_t Size)

{

union align *sym = malloc(Size + sizeof *sym);

return sym ? &sym->Bucket + 1 : NULL;

No, this is wrong. Return `sym + 1', pointing past
the entire union. `&sym->bucket + 1' might point somewhere
in the middle of the union, leaving you with the same
alignment problem you had to begin with.

}

void freesym(void *sym)

{

if (sym != NULL)

free((union align*)sym - 1);

This is right.

Once again: The whole scheme rests on the uncertain
assumption that no type requires stricter alignment than
`union align'; there is no portable way to check that
assumption.