[Pkg-shadow-devel] Bug#526749: passwd: Infinite loop when reaching 60000 users

[Sylvain Beucler]

On Sun, May 03, 2009 at 11:55:05AM +0200, Nicolas François wrote:
> On Sun, May 03, 2009 at 11:21:04AM +0200, beuc at beuc.net wrote:
> > 
> > As far as I can see, when looking for the next available user id, useradd does:
> > - take max user id + 1
> > - if id > 60000 then start from 1000 and search for gaps
> > - repeat
> > 
> > So if all user ids from 1000 to 60000 are taken, useradd is in an infinite loop.
> > Admittedly not a common case, but I guess it needs to return an error in that case.
> 
> I don't think there is any infinite loop.
> 
> I had some reports about being very slow with LDAP systems under some
> conditions (a bug in the ldap nss was mentioned at that time).
> 
> Here is the code with the loops in useradd (in libmisc/find_new_ids.c):
> 
> 	setpwent ();
> 	pw_rewind ();
> 	while (   ((pwd = getpwent ()) != NULL)
> 	       || ((pwd = pw_next ()) != NULL)) {
> 		if ((pwd->pw_uid >= user_id) && (pwd->pw_uid <= uid_max)) {
> 			user_id = pwd->pw_uid + 1;
> 		}
> 	}
> 
> At some time, getpwent will return NULL. Unfortunately, the above
> mentioned LDAP bug caused getpwent to loop back to the beginning.
> So there could be (LDAP users) * (local users) at most loops here.
> 
> Without this bug, it is only (LDAP users) + (local users).
> 
> Then, there is another loop, which starts from uid_min up to at most
> uid_max.
> 
> 		for (user_id = uid_min; user_id < uid_max; user_id++) {
> 			/* local, no need for xgetpwuid */
> 			if (   (getpwuid (user_id) == NULL)
> 			    && (pw_locate_uid (user_id) == NULL)) {
> 				break;
> 			}
> 		}
> 
> So the two loops are finite.
> 
> 
> What were the symptoms you experienced?

I don't have anything related to LDAP here.

I added users >> /etc/passwd through:
#include <stdio.h>
int main(void)
{
  for (int i = 1001; i < 60000; i++)
    printf("t%d:x:%d:%d::/home/t%d:/bin/sh\n", i, i, i, i);
}

'useradd t60000' worked fine, a bit slow but under 2 seconds.
'useradd t60001' didn't finish within 30 seconds.

-- 
Sylvain