LDB: Patch for fixing counter variables

tridge at samba.org tridge at samba.org
Mon Nov 9 22:54:17 MST 2009


Hi Matthias,

 > That is, the boundary condition needs to be *way* below 2^31 (can we
 > really allocate that many elements?), and raising it to 2^32 just seems
 > to change the rollover point.  

Andrew is right about that, we can't ever allocate anything like that
number of elements in ldb. For a start, we limit talloc allocations to
256M, plus lots of the internal algorithms in ldb would start to fail.

There are a few things that are O(N^2) in ldb. If N approaches 2^31,
then N^2 will be 2^62. Think how long it will take to process that :-)

Changing to unsigned counters isn't wrong, but it does need to be done
very carefully, and I don't see it gaining us anything.

Matthias, would you mind if I suggested a more worthwhile project
related to ldb and 'for' loops? 

A really worthwhile project would be to find the places that are
O(N^2) or larger and find a way to fix them. To do that you might like
to start by finding all for loop nesting, or loops that call functions
that loop.

To give you an example, consider the code in ltdb_modify_internal()
which checks to see that we don't have a multi-valued attribute with
the same attribute twice (look near line 691 of
lib/ldb/ldb_tdb/ldb_tdb.c). Now think about what happens when we
modify an index record, which may have thousands of @IDX entries
(eg. the objectclass=user index, or a one-level index).

Adding 10k users will call this function 10k times on that
record. After adding N users, each call of that function will cost
O(N^2), as it checks all elements being stored with all previous
elements. So that means adding 10k users will cost O(N^3). So it will
cost about 10^12 memcmp() calls (the calls are in
ldb_val_equal_exact()). Each memcmp compares on average about 10^2
bytes, so in total we memcmp() about 10^14 bytes. A modern CPU can
compare cached memory at a rate of about 4*10^9 bytes/s, so those
memcmp() calls are costing us about 25000 seconds (ie. about 6 hours).

The reason I'm suggesting this is you are concerned about large lists
of elements in ldb. If you plug N=2^31 into the above, then you'll see
that to add that number of users in the current ldb would cost about
2^95 time. The earth (and probably the universe!) would be well and
truly dead by the time we'd added that number of users.

The fix is to develop hashing, binary search and sort functions that
will allow ldb to scale to large sizes. That fix is much more
important than going from 2^31 to 2^32. In the example above, if we
used a qsort() of the elements then checked for duplicates by checking
neighboring elements then the total cost of that part of the code
would drop from 10^14 to about 10^10. So instead of taking 6 hours for
those few lines of code to run it would take about 2 seconds.

There are lots of examples like this in Samba4 (and probably in Samba3
too!), and there is an especially large concentration of them in
ldb. We rarely test for real scalability, and that means that the
developers aren't thinking in terms of big-O calculations when they
write the code.

If you can help us fix that, then maybe someday we can actually think
about approaching 2^31 elements. Then signed/unsigned for the loop
counters will matter :-)

Cheers, Tridge

PS: All numbers in the above are very rough of course - but try adding
a few thousand users with a profiler running and you'll see what I
mean


More information about the samba-technical mailing list