+if (dbdb != NULL)
+ {
+ /* Locate the basic ratelimit block inside the DB data. */
+ HDEBUG(D_acl) debug_printf("ratelimit found key in database\n");
+ dbd = &dbdb->dbd;
+
+ /* Forget the old Bloom filter if it is too old, so that we count each
+ repeating event once per period. We don't simply clear and re-use the old
+ filter because we want its size to change if the limit changes. Note that
+ we keep the dbd pointer for copying the rate into the new data block. */
+
+ if(unique != NULL && tv.tv_sec > dbdb->bloom_epoch + period)
+ {
+ HDEBUG(D_acl) debug_printf("ratelimit discarding old Bloom filter\n");
+ dbdb = NULL;
+ }
+
+ /* Sanity check. */
+
+ if(unique != NULL && dbdb_size < sizeof(*dbdb))
+ {
+ HDEBUG(D_acl) debug_printf("ratelimit discarding undersize Bloom filter\n");
+ dbdb = NULL;
+ }
+ }
+
+/* Allocate a new data block if the database lookup failed
+or the Bloom filter passed its age limit. */
+
+if (dbdb == NULL)
+ {
+ if (unique == NULL)
+ {
+ /* No Bloom filter. This basic ratelimit block is initialized below. */
+ HDEBUG(D_acl) debug_printf("ratelimit creating new rate data block\n");
+ dbdb_size = sizeof(*dbd);
+ dbdb = store_get(dbdb_size);
+ }
+ else
+ {
+ int extra;
+ HDEBUG(D_acl) debug_printf("ratelimit creating new Bloom filter\n");
+
+ /* See the long comment below for an explanation of the magic number 2.
+ The filter has a minimum size in case the rate limit is very small;
+ this is determined by the definition of dbdata_ratelimit_unique. */
+
+ extra = (int)limit * 2 - sizeof(dbdb->bloom);
+ if (extra < 0) extra = 0;
+ dbdb_size = sizeof(*dbdb) + extra;
+ dbdb = store_get(dbdb_size);
+ dbdb->bloom_epoch = tv.tv_sec;
+ dbdb->bloom_size = sizeof(dbdb->bloom) + extra;
+ memset(dbdb->bloom, 0, dbdb->bloom_size);
+
+ /* Preserve any basic ratelimit data (which is our longer-term memory)
+ by copying it from the discarded block. */
+
+ if (dbd != NULL)
+ {
+ dbdb->dbd = *dbd;
+ dbd = &dbdb->dbd;
+ }
+ }
+ }
+
+/* If we are counting unique events, find out if this event is new or not.
+If the client repeats the event during the current period then it should be
+counted. We skip this code in readonly mode for efficiency, because any
+changes to the filter will be discarded and because count is already set to
+zero. */
+
+if (unique != NULL && !readonly)
+ {
+ /* We identify unique events using a Bloom filter. (You can find my
+ notes on Bloom filters at http://fanf.livejournal.com/81696.html)
+ With the per_addr option, an "event" is a recipient address, though the
+ user can use the unique option to define their own events. We only count
+ an event if we have not seen it before.
+
+ We size the filter according to the rate limit, which (in leaky mode)
+ is the limit on the population of the filter. We allow 16 bits of space
+ per entry (see the construction code above) and we set (up to) 8 of them
+ when inserting an element (see the loop below). The probability of a false
+ positive (an event we have not seen before but which we fail to count) is
+
+ size = limit * 16
+ numhash = 8
+ allzero = exp(-numhash * pop / size)
+ = exp(-0.5 * pop / limit)
+ fpr = pow(1 - allzero, numhash)
+
+ For senders at the limit the fpr is 0.06% or 1 in 1700
+ and for senders at half the limit it is 0.0006% or 1 in 170000
+
+ In strict mode the Bloom filter can fill up beyond the normal limit, in
+ which case the false positive rate will rise. This means that the
+ measured rate for very fast senders can bogusly drop off after a while.
+
+ At twice the limit, the fpr is 2.5% or 1 in 40
+ At four times the limit, it is 31% or 1 in 3.2
+
+ It takes ln(pop/limit) periods for an over-limit burst of pop events to
+ decay below the limit, and if this is more than one then the Bloom filter
+ will be discarded before the decay gets that far. The false positive rate
+ at this threshold is 9.3% or 1 in 10.7. */
+
+ BOOL seen;
+ unsigned n, hash, hinc;
+ uschar md5sum[16];
+ md5 md5info;
+
+ /* Instead of using eight independent hash values, we combine two values
+ using the formula h1 + n * h2. This does not harm the Bloom filter's
+ performance, and means the amount of hash we need is independent of the
+ number of bits we set in the filter. */
+
+ md5_start(&md5info);
+ md5_end(&md5info, unique, Ustrlen(unique), md5sum);
+ hash = md5sum[0] | md5sum[1] << 8 | md5sum[2] << 16 | md5sum[3] << 24;
+ hinc = md5sum[4] | md5sum[5] << 8 | md5sum[6] << 16 | md5sum[7] << 24;
+
+ /* Scan the bits corresponding to this event. A zero bit means we have
+ not seen it before. Ensure all bits are set to record this event. */
+
+ HDEBUG(D_acl) debug_printf("ratelimit checking uniqueness of %s\n", unique);
+
+ seen = TRUE;
+ for (n = 0; n < 8; n++, hash += hinc)
+ {
+ int bit = 1 << (hash % 8);
+ int byte = (hash / 8) % dbdb->bloom_size;
+ if ((dbdb->bloom[byte] & bit) == 0)
+ {
+ dbdb->bloom[byte] |= bit;
+ seen = FALSE;
+ }
+ }
+
+ /* If this event has occurred before, do not count it. */
+
+ if (seen)
+ {
+ HDEBUG(D_acl) debug_printf("ratelimit event found in Bloom filter\n");
+ count = 0.0;
+ }
+ else
+ HDEBUG(D_acl) debug_printf("ratelimit event added to Bloom filter\n");
+ }
+
+/* If there was no previous ratelimit data block for this key, initialize
+the new one, otherwise update the block from the database. The initial rate
+is what would be computed by the code below for an infinite interval. */
+
git://git.exim.org / users / heiko / exim.git / commitdiff