?

Log in

No account? Create an account
C Pointer Comparison Gotcha - Shlomif's Technical Posts Community — LiveJournal [entries|archive|friends|userinfo]
Shlomif's Technical Posts Community

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| Shlomi Fish's Homepage Main Journal Homesite Blog Planet Linux-IL Amir Aharoni in Unicode open dot dot dot ]

C Pointer Comparison Gotcha [Dec. 29th, 2010|08:52 am]
Shlomif's Technical Posts Community

shlomif_tech

[shlomif]
[Tags|, , , , ]
[Current Location |Home]
[Current Music |Men at Work - Land Down Under]

Some days ago I integrated a new BSD-licensed balanced binary tree, based on the red-black tree of kazlib into Freecell Solver (fc-solve) and ported two of its collections to it. I've written a comparator function for it and asked my IRC pal Amadiro to test the new fc-solve with some memory optimisations on one of his University's HPC machines which he had access to. However, it crashed pretty quickly.

I was able to reproduce a similar crash on my x86-64 laptop, and tried to investigate it. Then it hit me, because the comparator callback was this:

extern int fc_solve_compare_lru_cache_keys(
    const void * void_a, const void * void_b, void * context
)
{
#define GET_PARAM(p) ((unsigned long) \
    ((const fcs_cache_key_info_t *)(p))->val_ptr)
    return GET_PARAM(void_a) - GET_PARAM(void_b);
}

Do you see the problem? Subtracting two unsigned longs will always yield a non-negative value, which will yield the comparison void. I considered several alternatives to this including using longs instead of unsigned longs (which will still be a problems on platforms where long is less than the pointer size), or subtracting const char * (which may overflow the int return) and eventually opted for the safest version of:

typedef const char * fcs_lru_side_t;

extern int fc_solve_compare_lru_cache_keys(
    const void * void_a, const void * void_b, void * context
)
{
#define GET_PARAM(p) ((fcs_lru_side_t) \
    (((const fcs_cache_key_info_t *)(p))->val_ptr))
    fcs_lru_side_t a, b;

    a = GET_PARAM(void_a);
    b = GET_PARAM(void_b);

    return ((a > b) ? 1 : (a < b) ? (-1) : 0);
#undef GET_PARAM
}

This way I'm sure that the comparison works correctly, and indeed after that Freecell Solver ran fine on the HPC machine, and would have appeared to scale to up to 600 million positions within 64 GigaBytes instead of the previous 400 million positions.

If you're a sucker for pretty graphs, you may wish to inspect the OpenDocument spreadsheet (.ods) of the memory consumption of the solver, though the data is quite estimative.

Update: corrected the second comparison in the corrected example after a copy-paste-and-HTMLisation-error (thanks to Lev).

LinkReply

Comments:
From: (Anonymous)
2010-12-29 10:42 am (UTC)

I think you have the sign reversed in the return statement

Shouldn't the second comparison be: a < b?
return ((a > b) ? 1 : (a < b) ? (-1) : 0);

I hope it's just a copy paste error.

-- Lev
(Reply) (Thread)
[User Picture]From: shlomif
2010-12-30 10:11 am (UTC)

Re: I think you have the sign reversed in the return statement

Hi Lev,

yes, it should be that - thanks for noticing that and reporting that. And it was only an HTMLisation error where I used the wrong HTML escape for the second sign.

Thanks again.
(Reply) (Parent) (Thread)
From: (Anonymous)
2010-12-29 09:38 pm (UTC)

Why throw away pointers?

Why do you need to cast away the pointers in the first place? You can do math on pointers and comparisons on pointers. Just compare the pointers themselves, and let the compiler worry about the size and the signedness.

You don't need to cast them to a char* pointer either.
(Reply) (Thread)
From: (Anonymous)
2011-01-02 02:13 pm (UTC)

Re: Why throw away pointers?

My thoughts also. "void" casts are always dangerous...

Or are the void casts required for the sake of cross-platform flexibility?

Thanks for a good reminder about pointers!

Regards,
Martin
(Reply) (Parent) (Thread)
[User Picture]From: shlomif
2011-01-10 10:52 am (UTC)

Re: Why throw away pointers?


Read the GET_PARAM(...) macro carefully. I'm not comparing void_a and void_b themselves - I'm comparing their val_ptr members. I guess I can avoid casting them as char *, but the type is in a different place.

(Reply) (Parent) (Thread)
From: (Anonymous)
2011-01-18 11:54 am (UTC)

Use ptrdiff_t

Use ptrdiff_t to hold difference between to pointer of the same type:

The <stddef.h> header shall define the following types:

ptrdiff_t
Signed integer type of the result of subtracting two pointers.


And never cast a pointer to long. Use intptr_t or uintptr_t from <stdint.h>

Integer types capable of holding object pointers

The following type designates a signed integer type with the property
that any valid pointer to void can be converted to this type, then
converted back to a pointer to void, and the result will compare equal
to the original pointer: intptr_t

The following type designates an unsigned integer type with the property
that any valid pointer to void can be converted to this type, then
converted back to a pointer to void, and the result will compare equal
to the original pointer: uintptr_t


--
Yann Droneaud
(Reply) (Thread)