delgroup is a wrapper to groupdel which performs additional
validations.  It checks to see whether any other user on the system
has, as its primary group, the group that it is potentially deleting.

It does so with the following code:

    setpwent;
    while ((my $acctname,my $primgrp) = (getpwent)[0,3]) {
        if( $primgrp eq $gr_gid ) {
            fail (7, gtx("`%s' still has `%s' as their primary
group!\n"),$acctname,$group);
        }
    }
    endpwent;

Perl's implementation of getpwent will call getspnam() for each user
to get the shadow password.  On a default system (using /etc/passwd
and /etc/shadow) this means, for each line of /etc/passwd,
perl will open /etc/shadow, scan it until it finds the matching user,
and close the file.  Given adding users adds lines to /etc/passwd and
/etc/shadow, this means the overall I/O complexity for deleting
a group is O(n^2).  On systems with ~100k users this quickly ends up
being hundreds of gigabytes that needs to be read and processed in
order to remove a group; given how often delgroup gets
called from postrm scripts this can make a lot of operations rather expensive.

groupdel performs the same check from C, using getpwent() without
calling the getspnam(), so safety-wise this check is not needed.  The
only thing we gain from it is the opportunity to detect
the error before printing "Removing group ..." and calling groupdel.
groupdel has a return value specifically for this case (it will return
8) in the event we wanted to make any behavior conditional
on this case.

The simplest fix is to simply remove the offending lines of perl
entirely. This will result in a slightly different output being
printed when attempting to remove a group in use, but will otherwise
behave the same, as so:

With current delgroup:

# delgroup root
/usr/sbin/delgroup: `root' still has `root' as their primary group!

If offending code were simply removed:

# delgroup root
Removing group `root' ...
groupdel: cannot remove the primary group of user 'root'
/usr/sbin/delgroup: `/usr/sbin/groupdel root' returned error code 8. Exiting.

The bug was introduced in this commit:
http://anonscm.debian.org/viewvc/adduser/trunk/deluser?r1=233&r2=234&

and it's entirely plausible (I haven't checked) that groupdel didn't
have any check at all at this point in time.  If people believe it's
unacceptable to simply remove the check and rely on groupdel to fail,
this also suggests an alternate approach to fixing this bug -- calling
out to grep via a subshell will be O(n) instead of O(n^2) and should
work fine on systems with much larger numbers of users.

Daniel

Correct, but this bug isn't a product of my normal work.

Yes.

To be honest, I have no idea who has 100k users in their /etc/passwd
file.  A coworker of mine mentioned observing this behavior while
walking to lunch; I didn't follow up with him about what machines he
saw this on, or whether this was even work related.

Given he didn't mention having any other problems with that number of
users on the machine, I think it's a win to correct this sub-optimal
behavior.  There's no reason to do an O(n^2) operation where an O(n)
one will do - especially when we're already doing the O(n) operation
anyway.

Daniel

And given uids went from being 16-bit to 32-bit in 2.4, I think it's
reasonable to expect people to have this many users.

Feel free to benchmark the performance with 64k users, but I suspect
you'll find it to be suboptimal as well.

Here's a debian-devel thread in 1998 where people discuss the
performance problem in perl:

http://lists.debian.org/debian-devel/1998/06/msg00885.html

I don't think this bug is unreasonable.

Daniel

Hi,

I have added a test to benchmark the deletion of groups on a system
with tens of thousands of users, and it is indeed (still) not great.

However, removing the overhead described in this bug (and replacing it
with *nothing*) only yields < 10-15% speed-up.

I would not be opposed to relying on the failure of userdel if it meant
a real boost, but I am tempted to say that this decade-old problem
might be better taken up with the passwd package.

Here is a snippet of the performance test output.  The times for
comparable groups are shown both for delgroup and for groupdel.

ok 2 - populated 10000 groups in 4 seconds (< 120).
ok 3 - command success: /usr/sbin/delgroup --quiet dgpg_3
ok 4 - delgroup dgpg_3 took 8s (< 30).
ok 5 - command success: /usr/sbin/delgroup --quiet dgpg_3333
ok 6 - delgroup dgpg_3333 took 9s (< 30).
ok 7 - command success: /usr/sbin/delgroup --quiet dgpg_6666
ok 8 - delgroup dgpg_6666 took 11s (< 30).
ok 9 - command success: /usr/sbin/delgroup --quiet dgpg_9998
ok 10 - delgroup dgpg_9998 took 13s (< 30).
ok 11 - command success: /usr/sbin/groupdel dgpg_4
ok 12 - groupdel dgpg_4 took 11s (< 30).
ok 13 - command success: /usr/sbin/groupdel dgpg_3334
ok 14 - groupdel dgpg_3334 took 10s (< 30).
ok 15 - command success: /usr/sbin/groupdel dgpg_6667
ok 16 - groupdel dgpg_6667 took 11s (< 30).
ok 17 - command success: /usr/sbin/groupdel dgpg_9999
ok 18 - groupdel dgpg_9999 took 13s (< 30).

Any objections to either moving this bug to passwd, or just wontfix'ing
this?

Cheers,
Matt

No objection from me, I'd just reassign the bug. If we can do something
to speed deletion up while having more pretty code, we should do that
anyway though.

Greetings
Marc

To make the test fast enough to be realistically runnable, I had to
replace even useradd/groupadd with direct writes to /etc/passwd et al.
So.. no prettier code to be had here. :(

We can do as suggested above and remove our own (arguably superfluous)
check, and take the minor performance win.

Dead Shadow Maintainers,

this is a one decade old bug file against adduser, saying that the check
done on group deletion to find out whether there is still a user having
the to-be-deleted group as primary group, takes quite a long time if the
system has many users.

While investigating this, Matt Barry from the adduser team found out
that groupdel in fact suffers from the same issue and that even removing
the offending code from delgroup (relying entirely on the identical
check that groupdel does) only speeds up group deletion by a mere
10-15%.

I am cloning and reassigning the clone to passwd to give you the
possibility of investigating this in groupdel and probably implementing
a more efficient way of doing this check.

Greetings
Marc