Обсуждение: Revise the Asserts added to bimapset manipulation functions

On Wed, 27 Dec 2023 at 22:30, Richard Guo <guofenglinux@gmail.com> wrote:
> The Asserts added to bitmapset.c by commits 71a3e8c43b and 7d58f2342b
> contain some duplicates, such as in bms_difference, bms_is_subset,
> bms_subset_compare, bms_int_members and bms_join.  For instance,

I'm just learning of these changes now.   I wonder why that wasn't
done more like:

#ifdef REALLOCATE_BITMAPSETS
static Bitmapset *
bms_clone_and_free(Bitmapset *a)
{
    Bitmapset *c = bms_copy(a);

    bms_free(a);
    return c;
}
#endif

then instead of having to do:

#ifdef REALLOCATE_BITMAPSETS
a = (Bitmapset *) palloc(BITMAPSET_SIZE(tmp->nwords));
memcpy(a, tmp, BITMAPSET_SIZE(tmp->nwords));
pfree(tmp);
#endif

all over the place.  Couldn't we do:

#ifdef REALLOCATE_BITMAPSETS
     return bms_clone_and_free(a);
#else
     return a;
#endif

I think it's best to leave at least that and not hide the behaviour
inside a macro.

It would also be good if REALLOCATE_BITMAPSETS was documented in
bitmapset.c to offer some guidance to people modifying the code so
they know under what circumstances they need to return a copy. There
are no comments that offer any indication of what the intentions are
with this :-(  What's written in pg_config_manual.h isn't going to
help anyone that's modifying bitmapset.c

> While removing those duplicates, I think we can add checks in the new
> Asserts to ensure that Bitmapsets should not contain trailing zero
> words, as the old Asserts did.  That makes the Asserts in the form of:
>
> Assert(a == NULL || (IsA(a, Bitmapset) && a->words[a->nwords - 1] != 0));
>
> I think we can define a new macro for this form and use it to check that
> a Bitmapset is valid.

I think that's an improvement.  I did have a function for this in [1],
but per [2], Tom wasn't a fan.  I likely shouldn't have bothered with
the loop there. It seems fine just to ensure the final word isn't 0.

David

[1] https://postgr.es/m/CAApHDvr5O41MuUjw0DQKqmAnv7QqvmLqXReEd5o4nXTzWp8-%2Bw%40mail.gmail.com
[2] https://postgr.es/m/2686153.1677881312%40sss.pgh.pa.us

On Thu, 28 Dec 2023 at 23:21, David Rowley <dgrowleyml@gmail.com> wrote:
> then instead of having to do:
>
> #ifdef REALLOCATE_BITMAPSETS
> a = (Bitmapset *) palloc(BITMAPSET_SIZE(tmp->nwords));
> memcpy(a, tmp, BITMAPSET_SIZE(tmp->nwords));
> pfree(tmp);
> #endif
>
> all over the place.  Couldn't we do:
>
> #ifdef REALLOCATE_BITMAPSETS
>      return bms_clone_and_free(a);
> #else
>      return a;
> #endif

I looked into this a bit more and I just can't see why the current
code feels like it must do the reallocation in functions such as
bms_del_members().  We don't repalloc the set there, ever, so why do
we need to do it when building with REALLOCATE_BITMAPSETS?  It seems
to me the point of REALLOCATE_BITMAPSETS is to ensure that *if* we
possibly could end up reallocating the set that we *do* reallocate.

There's also a few cases where you could argue that the
REALLOCATE_BITMAPSETS code has introduced bugs.  For example,
bms_del_members(), bms_join() and bms_int_members() are meant to
guarantee that their left input (both inputs in the case of
bms_join()) are recycled. Compiling with REALLOCATE_BITMAPSETS
invalidates that, so it seems about as likely that building with
REALLOCATE_BITMAPSETS could cause bugs rather than find bugs.

I've hacked a bit on this to fix these problems and also added some
documentation to try to offer future people modifying bitmapset.c some
guidance on if they need to care about REALLOCATE_BITMAPSETS.

I also don't think "hangling" is a word. So I've adjusted the comment
in pg_config_manual.h to fix that.

David

On Fri, 29 Dec 2023 at 21:07, Richard Guo <guofenglinux@gmail.com> wrote:
> It seems to me that the former scenario also makes sense in some cases.
> For instance, let's say there are two pointers in two structs, s1->p and
> s2->p, both referencing the same bitmapset.  If we modify the bitmapset
> via s1->p (even if no reallocation could occur), s2 would see different
> content via its pointer 'p'.

That statement simply isn't true.  If there's no reallocation then
both pointers point to the same memory and, therefore have the same
content, not different content.  In the absence of a reallocation,
then the only time s1->p and s2->p could differ is if s1->p became an
empty set as a result of the modification.

>  Sometimes this is just wrong and could
> cause problems.  If we can force a reallocation for every modification
> of the bitmapset, it'd be much easier to find such bugs.

Whether it's intended or unintended, at least it's consistent,
therefore isn't going to behave differently if the number of
bitmapwords in the set changes. All REALLOCATE_BITMAPSETS does for
bms_int_members(), bms_join() and bms_del_members() is change one
consistent behaviour (we never reallocate) into some other consistent
behaviour (we always reallocate).

If we make REALLOCATE_BITMAPSETS work how I propose in my patch then
the reallocation is just limited to cases where the set *could* be
repalloced by a modification.  That change gives us consistent
behaviour as the set is *always* reallocated when it *could* be
reallocated.  Making it consistent to me, seems good as a debug
option. Swapping one consistent behaviour for another (as you propose)
seems pointless and more likely to force us to change code that works
perfectly fine today.

In any case, the comments in bms_int_members(), bms_join() and
bms_del_members() are now only true when REALLOCATE_BITMAPSETS is not
defined. Are you proposing we leave those comments outdated? or do you
propose that we mention that the left inputs are not recycled when
building with REALLOCATE_BITMAPSETS?  In my view, neither of these is
acceptable as often the primary reason to use something like
bms_int_members() over bms_intersect() is exactly because the left
input is recycled.  I don't want people to have to start contorting
code because bms_int_members()'s left input recycling cannot be relied
on.

David

On Fri, 29 Dec 2023 at 23:38, Richard Guo <guofenglinux@gmail.com> wrote:
> After applying this process to the first RestrictInfo, the bitmapset now
> becomes {t2, t3}.  Consequently, the second RestrictInfo also perceives
> {t2, t3} as its required_relids.  As a result, when attempting to remove
> it from the joininfo lists, a problem arises, because it is not in t2's
> joininfo list.

Changing the relids so they reference t2 instead of t1 requires both
bms_add_member() and bms_del_member().  The bms_add_member() will
cause the set to be reallocated with my patch so I don't see why this
case isn't covered.

> Also, here are some review comments for the v2 patch:
>
> * There is no reallocation that happens in bms_add_members(), do we need
> to call bms_copy_and_free() there?

The spec I put in the comment at the top of bitmapset.c says:

> have the code *always* reallocate the bitmapset when the
> * set *could* be reallocated as a result of the modification

Looking at bms_add_members(), it seems to me that the set *could* be
reallocated as a result of the modification, per:

if (a->nwords < b->nwords)
{
    result = bms_copy(b);
    other = a;
}

In my view, that meets the spec I outlined.

> * Do you think we can add Assert(bms_is_valid_set(a)) for bms_free()?

I did briefly have the Assert in bms_free(), but I removed it as I
didn't think it was that useful to validate the set before freeing it.
Certainly, there'd be an argument to do that, but I ended up not
putting it there. I wondered if there could be a case where we do
something like bms_int_members() which results in an empty set and
after checking for and finding the set is now empty, we call
bms_free().  If we did that then we'd Assert fail.  In reality, we use
pfree() instead of bms_free() as we already know the set is not NULL,
so it wouldn't cause a problem for that particular case. I wondered if
there might be another one that I didn't spot, so felt it was best not
to Assert there.

I imagine that if we found some case where the bms_free() Assert
failed, we'd likely just remove it rather than trying to make the set
valid before freeing it.  So it seems pretty pointless if we'd opt to
remove the Assert() at the first sign of trouble.

David

On Tue, 2 Jan 2024 at 20:18, Richard Guo <guofenglinux@gmail.com> wrote:
> I think one purpose of introducing REALLOCATE_BITMAPSETS is to help find
> dangling pointers to Bitmapset's.  From this point of view, I agree that
> we should call bms_copy_and_free() in bms_add_members(), because the
> bitmapset 'a' might be recycled (in-place modified, or pfreed).

I spoke to Andres about this in our weekly meeting and he explained it
in such I way that I now agree that it's useful to repalloc with all
modifications.  I'd previously thought that when the comments mention
that some function "recycle their left input" that you could be
certain that the Bitmapset would be modified in-place, therefore any
other pointers pointing to this set should remain valid.  As Andres
reminded me, that's not the case when the set becomes empty and
there's nothing particularly special about a set becoming empty so
making a clone of the set will help identify any pointers that don't
get updated as a result of the modification.

I've now adjusted the patch to have all modifications to Bitmapsets
return a newly allocated set. There are a few cases missing in master
that need to be fixed (items 6-10 below):

The patch now includes changes for the following:

1. Document what REALLOCATE_BITMAPSETS is for.
2. Provide a reusable function to check a set is valid and use it in
cassert builds and use it to validate sets (Richard)
3. Provide a reusable function to copy a set and pfree the original
and use that instead of duplicating that code all over bitmapset.c
4. Fix Assert duplication (Richard)
5. Make comments in bms_union, bms_intersect, bms_difference clear
that a new set is allocated.  (This has annoyed me for a while)
6. Fix failure to duplicate the set in bms_add_members() when b == NULL.
7. Fix failure to duplicate the set in bms_add_range() when upper < lower
8. Fix failure to duplicate the set in bms_add_range() when the set
has enough words already.
9. Fix failure to duplicate the set in bms_del_members() when b == NULL
10. Fix failure to duplicate the set in bms_join() when a == NULL and
also fix the b == NULL case too
11. Fix hazard in bms_add_members(), bms_int_members(),
bms_del_members() and bms_join(),  where the code added in 7d58f2342
could crash if a == b due to the REALLOCATE_BITMAPSETS code pfreeing
'a'. This happens in knapsack.c:93, although I propose we adjust that
code now that empty sets are always represented as NULL.

David





> According to this criterion, it seems to me that we should also call
> bms_copy_and_free() in bms_join(), since both inputs there might be
> recycled.  But maybe I'm not understanding it correctly.
>
>>
>> > * Do you think we can add Assert(bms_is_valid_set(a)) for bms_free()?
>>
>> I did briefly have the Assert in bms_free(), but I removed it as I
>> didn't think it was that useful to validate the set before freeing it.
>> Certainly, there'd be an argument to do that, but I ended up not
>> putting it there. I wondered if there could be a case where we do
>> something like bms_int_members() which results in an empty set and
>> after checking for and finding the set is now empty, we call
>> bms_free().  If we did that then we'd Assert fail.  In reality, we use
>> pfree() instead of bms_free() as we already know the set is not NULL,
>> so it wouldn't cause a problem for that particular case. I wondered if
>> there might be another one that I didn't spot, so felt it was best not
>> to Assert there.
>>
>> I imagine that if we found some case where the bms_free() Assert
>> failed, we'd likely just remove it rather than trying to make the set
>> valid before freeing it.  So it seems pretty pointless if we'd opt to
>> remove the Assert() at the first sign of trouble.
>
>
> I think I understand your concern.  In some bitmapset manipulation
> functions, like bms_int_members(), the result might be computed as
> empty.  In such cases we need to free the input bitmap.  If we use
> bms_free(), the Assert would fail.
>
> It seems to me that this scenario can only occur within the bitmapset
> manipulation functions.  Outside of bitmapset.c, I think it should be
> quite safe to call bms_free() with this Assert.  So I think it should
> not have problem to have this Assert in bms_free() as long as we are
> careful enough when calling bms_free() inside bitmapset.c.
>
> Thanks
> Richard

On Tue, 16 Jan 2024 at 21:00, Richard Guo <guofenglinux@gmail.com> wrote:
> Thank you so much for all the work you have put into making this patch
> perfect.  I reviewed through the v3 patch and I do not have further
> comments.  I think it's in good shape now.

Thanks for looking again.  I pushed the patch after removing some
comments mentioning "these operations".  I found these not to be very
useful and also misleading.

David