Thanks for the comments, Ted. On Fri, Jan 28, 2011 at 08:53:55PM -0500, Ted Ts'o wrote: > On Fri, Jan 28, 2011 at 03:12:23PM +0100, Petr Uzel wrote: > > > > Sometimes, when there are multiple processes generating time-based > > UUIDs in a loop (each of them using multiple threads), it can happen > > that the socket backlog in uuidd daemon is full and so the connection > > request is refused. uuid_generate_time() then fallbacks to unsafe way of > > generating UUID, which may cause duplicate time-based UUIDs to be > > generated. > > It's probably also a good idea to increase the socket backlog queue > length in uuidd, which is currently set to 5 for no good reason. We > should probably just change that to be SOMAXCONN. > > I don't have a problem with engineering solutions which wait until you > can talk to the uuidd, and returning an error to the processes if it > fails, but it's better not to fail in the first place, and so > increasing the listen backlog parameter would be a good thing to do. I agree; we should try to make libuuid not to fail in the first place. But still, the possibility to report failure to the caller looks as a useful feature to me. > Also, please note that each process only calls out to the uuidd one in > every thousand calls to uuid_generate_time(), so you'd need a pretty > large number of threads before you would be overloading the uuidd are > pretty small, even with the listen backlog set to 5. So I have to ask > --- is this a real or theoretical problem which you are worried about? > Has this actually ever happened in real life? And if so, what were > the circumstances where this happened? Yes, this is a real problem reported by one of our customers. I have a test program[*] that forks several times and later each of the clones generates UUIDs in several threads. The UUIDs are stored in shared segment of memory and after all processes finish, they are checked for duplicates. I use this program to fork 10 processes, each of them runs 10 threads, each thread produces 10 UUIDs. Using these settings, it almost always produces at least one duplicate UUID (sometimes, there are no duplicates, sometimes they are 100 and more). Additional conditions to be able to reproduce the problem: - uuidd must be killed before I run the test (however, it is started by the libuuid and from 'top' I can see it is working) - the test does _not_ fail when ran as regular user (only as root), regardless of whether the daemon is running or not - for testing, I use util-linux-2.19-rc3, installed in VirtualBox (i586) - on my workstation (x86_64) it does _not_ fail The more I'm looking into this, the more confused I am; especially the first two does not make much sense to me yet [*] Unfortunately, I can not post it here right now, because I didn't write it. I'm going to ask the author(s) for permission, and eventually post it later. > I'll also note that the chances of duplicates is relatively small > unless you have a truly vast number of processes that fell back to > generating time-based UID's in a loop. There is a 14 bit clock > sequence number which is picked at random if the threads don't have > access to the clock state counter file (which uuidd would have access > to, as well as processes in the correct group). The birthday paradox > means that the chance of two processes picking the same thread is > approximately 50% when you have 2**13, or 8192 threads all generating > uuid's in a loop. But if you have a few dozen processes generating, > the chances that they will pick duplicate UUID's is actually pretty > remote. > > Also, even if you did fail to contact the uuidd, and had to return a > uuid using a locally generated clock sequence, the next call to > uuid_generate_time() would cause another attempt to contact the uuidd > daemon, and if that succeeded, that thread would be good for another > thousand uuids. So in order to generate a duplicate uuid, not only > would two processes have to win the birthday paranox and pick the same > 14 bit clock sequence, they would both have to get lucky and fail to > contact the uuidd at exactly the same time, such that the 100ns > timestamp used in the time portion of the UUID was the same. Which > again makes me wonder whether this is real or a theoretical problem > that you're worried about. Considering the number of duplicate UUIDs I sometimes get with a relatively small number of processess/threads, it seems there might be some other problem besides the "full backlog" in uuidd. I will look more into the code and report later. In the meantime, any ideas would be very welcome. Thanks, Best regards, Petr -- Petr Uzel IRC: ptr_uzl @ freenode
Attachment:
pgprIz5KDV6oR.pgp
Description: PGP signature
