X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/disorder/blobdiff_plain/7378b5081fde6f48140327d5c072a8231934f027..e7eb3a2744aa45179daea235800753d3d1955338:/server/choose.c?ds=inline diff --git a/server/choose.c b/server/choose.c index 06c9601..a4bf443 100644 --- a/server/choose.c +++ b/server/choose.c @@ -1,21 +1,20 @@ /* * This file is part of DisOrder * Copyright (C) 2008 Richard Kettlewell + * Copyright (C) 2008 Mark Wooding * - * This program is free software; you can redistribute it and/or modify + * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or + * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - * + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 - * USA + * along with this program. If not, see . */ /** @file choose.c * @brief Random track chooser @@ -25,36 +24,9 @@ * deadlock - it just exits and expects the server to try again. */ -#include -#include "types.h" - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include "configuration.h" -#include "log.h" -#include "defs.h" -#include "mem.h" -#include "kvp.h" -#include "syscalls.h" -#include "printf.h" -#include "trackdb.h" -#include "trackdb-int.h" -#include "version.h" -#include "trackname.h" -#include "queue.h" -#include "server-queue.h" +#include "disorder-server.h" + +#define BASE_WEIGHT 90000 static DB_TXN *global_tid; @@ -80,28 +52,17 @@ static void help(void) { " --debug, -d Turn on debugging\n" " --[no-]syslog Enable/disable logging to syslog\n" "\n" - "Track choose for DisOrder. Not intended to be run\n" + "Track chooser for DisOrder. Not intended to be run\n" "directly.\n"); xfclose(stdout); exit(0); } - -/** @brief Weighted track record */ -struct weighted_track { - /** @brief Next track in the list */ - struct weighted_track *next; - /** @brief Track name */ - const char *track; - /** @brief Weight for this track (always positive) */ - unsigned long weight; -}; - -/** @brief List of tracks with nonzero weight */ -static struct weighted_track *tracks; - /** @brief Sum of all weights */ static unsigned long long total_weight; +/** @brief The winning track */ +static const char *winning = 0; + /** @brief Count of tracks */ static long ntracks; @@ -131,7 +92,7 @@ static unsigned long compute_weight(const char *track, struct kvp *prefs) { const char *s; char **track_tags; - time_t last, now; + time_t last, now = time(0); /* Reject tracks not in any collection (race between edit config and * rescan) */ @@ -152,7 +113,6 @@ static unsigned long compute_weight(const char *track, /* Reject tracks played within the last 8 hours */ if((s = kvp_get(prefs, "played_time"))) { last = atoll(s); - now = time(0); if(now < last + config->replay_min) return 0; } @@ -182,8 +142,79 @@ static unsigned long compute_weight(const char *track, if((errno == 0 || errno == ERANGE) && n >= 0) return n; } + + /* Bias up tracks that were recently added */ + if((s = kvp_get(data, "_noticed"))) { + const time_t noticed = atoll(s); + + if(noticed + config->new_bias_age < now) + /* Currently we just step up the weight of tracks that are in range. A + * more sophisticated approach would be to linearly decay from new_bias + * down to BASE_WEIGHT over the course of the new_bias_age interval + * starting when the track is added. */ + return config->new_bias; + } - return 90000; + return BASE_WEIGHT; +} + +/** @brief Pick a random integer uniformly from [0, limit) */ +static unsigned long long pick_weight(unsigned long long limit) { + unsigned char buf[(sizeof(unsigned long long) * CHAR_BIT + 7)/8], m; + unsigned long long t, r, slop; + int i, nby, nbi; + + D(("pick_weight: limit = %#016llx", limit)); + + /* First, decide how many bits of output we actually need; do bytes first + * (they're quicker) and then bits. + * + * To speed this up, we could use a binary search if we knew where to + * start. (Note that shifting by ULLONG_BITS or more (if such a constant + * existed) is undefined behaviour, so we mustn't do that.) Figuring out a + * start point involves preprocessor and/or autoconf magic. + */ + for (nby = 1, t = (limit - 1) >> 8; t; nby++, t >>= 8) + ; + nbi = (nby - 1) << 3; t = limit >> nbi; + if (t >> 4) { t >>= 4; nbi += 4; } + if (t >> 2) { t >>= 2; nbi += 2; } + if (t >> 1) { t >>= 1; nbi += 1; } + nbi++; + D(("nby = %d; nbi = %d", nby, nbi)); + + /* Main randomness collection loop. We read a number of bytes from the + * randomness source, and glue them together into an integer (dropping + * bits off the top byte as necessary). Call the result r; we have + * 2^{nbi - 1) <= limit < 2^nbi and r < 2^nbi. If r < limit then we win; + * otherwise we try again. Given the above bounds, we expect fewer than 2 + * iterations. + * + * Unfortunately there are subtleties. In particular, 2^nbi may in fact be + * zero due to overflow. So in fact what we do is compute slop = 2^nbi - + * limit > 0; if r < slop then we try again, otherwise r - slop is our + * winner. + */ + slop = ((unsigned long long)2 << (nbi - 1)) - limit; + m = nbi & 7 ? (1 << (nbi & 7)) - 1 : 0xff; + D(("slop = %#016llx", slop)); + D(("m = 0x%02x", m)); + + do { + /* Actually get some random data. */ + random_get(buf, nby); + + /* Clobber the top byte. */ + buf[0] &= m; + + /* Turn it into an integer. */ + for (r = 0, i = 0; i < nby; i++) + r = (r << 8) | buf[i]; + D(("r = %#016llx", r)); + } while (r < slop); + + D((" result=%#016llx", r - slop)); + return r - slop; } /** @brief Called for each track */ @@ -194,56 +225,39 @@ static int collect_tracks_callback(const char *track, DB_TXN attribute((unused)) *tid) { unsigned long weight = compute_weight(track, data, prefs); + /* Decide whether this is the winning track. + * + * Suppose that we have n things, and thing i, for 0 <= i < n, has weight + * w_i. Let c_i = w_0 + ... + w_{i-1} be the cumulative weight of the + * things previous to thing i, and let W = c_n = w_0 + ... + w_{i-1} be the + * total weight. We can clearly choose a random thing with the correct + * weightings by picking a random number r in [0, W) and chooeing thing i + * where c_i <= r < c_i + w_i. But this involves having an enormous list + * and taking two passes over it (which has bad locality and is ugly). + * + * Here's another way. Initialize v = -1. Examine the things in order; + * for thing i, choose a random number r_i in [0, c_i + w_i). If r_i < w_i + * then set v <- i. + * + * Claim. For all 0 <= i < n, the above algorithm chooses thing i with + * probability w_i/W. + * + * Proof. Induction on n. The claim is clear for n = 1. Suppose it's + * true for n - 1. Let L be the event that we choose thing n - 1. Clearly + * Pr[L] = w_{n-1}/W. Condition on not-L: then the probabilty that we + * choose thing i, for 0 <= i < n - 1, is w_i/c_{n-1} (induction + * hypothesis); undoing the conditioning gives the desired result. + */ + D(("consider %s", track)); if(weight) { - struct weighted_track *const t = xmalloc(sizeof *t); - - /* Clamp weight so that we can fit in billions of tracks when we do - * arithmetic in long long */ - if(weight > 0x7fffffff) - weight = 0x7fffffff; - t->next = tracks; - t->track = track; - t->weight = weight; - tracks = t; total_weight += weight; - ++ntracks; + if (pick_weight(total_weight) < weight) + winning = track; } + ntracks++; return 0; } -/** @brief Pick a random integer uniformly from [0, limit) */ -static unsigned long long pick_weight(unsigned long long limit) { - unsigned long long n; - static int fd = -1; - int r; - - if(fd < 0) { - if((fd = open("/dev/urandom", O_RDONLY)) < 0) - fatal(errno, "opening /dev/urandom"); - } - if((r = read(fd, &n, sizeof n)) < 0) - fatal(errno, "reading /dev/urandom"); - if((size_t)r < sizeof n) - fatal(0, "short read from /dev/urandom"); - return n % limit; -} - -/** @brief Pick a track at random and write it to stdout */ -static void pick_track(void) { - long long w; - struct weighted_track *t; - - w = pick_weight(total_weight); - t = tracks; - while(t && w >= t->weight) { - w -= t->weight; - t = t->next; - } - if(!t) - fatal(0, "ran out of tracks but %lld weighting left", w); - xprintf("%s", t->track); -} - int main(int argc, char **argv) { int n, logsyslog = !isatty(2), err; const char *tags; @@ -286,11 +300,13 @@ int main(int argc, char **argv) { trackdb_commit_transaction(global_tid); trackdb_close(); trackdb_deinit(); - //info("ntracks=%ld total_weight=%lld", ntracks, total_weight); + D(("ntracks=%ld total_weight=%lld", ntracks, total_weight)); if(!total_weight) fatal(0, "no tracks match random choice criteria"); + if(!winning) + fatal(0, "internal: failed to pick a track"); /* Pick a track */ - pick_track(); + xprintf("%s", winning); xfclose(stdout); return 0; }