Re: mgetgroups improvements

[Bruno Haible]

Hi Eric,

> +  /* Reduce the number of duplicates.  On some systems, getgroups
> +     returns the effective gid twice: once as the first element, and
> +     once in its position within the supplementary groups.  On other
> +     systems, getgroups does not return the effective gid at all,
> +     which is why we provide a GID argument.  Meanwhile, the GID
> +     argument, if provided, is typically any member of the
> +     supplementary groups, and not necessarily the effective gid.  So,
> +     the most likely duplicates are the first element with an
> +     arbitrary other element, or pair-wise duplication between the
> +     first and second elements returned by getgroups.  It is possible
> +     that this O(n) pass will not remove all duplicates, but it is not
> +     worth the effort to slow down to an O(n log n) algorithm that
> +     sorts the array in place, nor the extra memory needed for
> +     duplicate removal via an O(n) hash-table.  Hence, this function
> +     is only documented as guaranteeing no pair-wise duplicates,
> +     rather than returning the minimal set.  */
> +  {
> +    gid_t first = *g;
> +    gid_t *next;
> +    gid_t *sentinel = g + ng;
> +
> +    for (next = g + 1; next < sentinel; next++)
> +      {
> +        if (*next == first || *next == *g)
> +          ng--;
> +        else
> +          *++g = *next;
> +      }
> +  }

This code will do an invalid memory access if ng == 0 (which can happen if
gid == (gid_t) -1 and getgroups or getugroups does not find a gid).

Also, the name of the variable 'sentinel' is confusing, precisely because
there is no sentinel [1] at the end of the array. It's just a pointer to the
end of the array.

[1] http://en.wikipedia.org/wiki/Sentinel_value_(programming)

Here's a proposed fix:


2009-12-09  Bruno Haible  <address@hidden>

        * lib/mgetgroups.c (mgetgroups): Don't remove duplicates if there is at
        most one group.

*** lib/mgetgroups.c.orig       2009-12-09 10:26:19.000000000 +0100
--- lib/mgetgroups.c    2009-12-09 10:26:16.000000000 +0100
***************
*** 175,193 ****
       duplicate removal via an O(n) hash-table.  Hence, this function
       is only documented as guaranteeing no pair-wise duplicates,
       rather than returning the minimal set.  */
!   {
!     gid_t first = *g;
!     gid_t *next;
!     gid_t *sentinel = g + ng;
  
!     for (next = g + 1; next < sentinel; next++)
!       {
!         if (*next == first || *next == *g)
!           ng--;
!         else
!           *++g = *next;
!       }
!   }
  
    return ng;
  }
--- 175,194 ----
       duplicate removal via an O(n) hash-table.  Hence, this function
       is only documented as guaranteeing no pair-wise duplicates,
       rather than returning the minimal set.  */
!   if (ng > 1)
!     {
!       gid_t first = *g;
!       gid_t *next;
!       gid_t *groups_end = g + ng;
  
!       for (next = g + 1; next < groups_end; next++)
!         {
!           if (*next == first || *next == *g)
!             ng--;
!           else
!             *++g = *next;
!         }
!     }
  
    return ng;
  }