X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/disorder/blobdiff_plain/91c9324af56bd50592e818fd4763e6cdcea68857..ddf0e06b99c52ed416f19432be45b71238d0b877:/server/choose.c diff --git a/server/choose.c b/server/choose.c index f22bf6f..f1d06b8 100644 --- a/server/choose.c +++ b/server/choose.c @@ -1,6 +1,7 @@ /* * 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 * it under the terms of the GNU General Public License as published by @@ -25,34 +26,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 "disorder-server.h" + +#define BASE_WEIGHT 90000 static DB_TXN *global_tid; @@ -83,29 +59,28 @@ static void help(void) { 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; static char **required_tags; static char **prohibited_tags; +static int queue_contains(const struct queue_entry *head, + const char *track) { + const struct queue_entry *q; + + for(q = head->next; q != head; q = q->next) + if(!strcmp(q->track, track)) + return 1; + return 0; +} + /** @brief Compute the weight of a track * @param track Track name (UTF-8) * @param data Track data @@ -119,7 +94,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) */ @@ -140,11 +115,15 @@ 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 + 8 * 3600) /* TODO configurable */ + if(now < last + config->replay_min) return 0; } + /* Reject tracks currently in the queue or in the recent list */ + if(queue_contains(&qhead, track) + || queue_contains(&phead, track)) + return 0; + /* We'll need tags for a number of things */ track_tags = parsetags(kvp_get(prefs, "tags")); @@ -156,61 +135,129 @@ static unsigned long compute_weight(const char *track, if(*required_tags && !tag_intersection(track_tags, required_tags)) return 0; - return 90000; -} + /* Use the configured weight if available */ + if((s = kvp_get(prefs, "weight"))) { + long n; + errno = 0; -/** @brief Called for each track */ -static int collect_tracks_callback(const char *track, - struct kvp *data, - struct kvp *prefs, - void attribute((unused)) *u, - DB_TXN attribute((unused)) *tid) { - const unsigned long weight = compute_weight(track, data, prefs); + n = strtol(s, 0, 10); + if((errno == 0 || errno == ERANGE) && n >= 0) + return n; + } - if(weight) { - struct weighted_track *const t = xmalloc(sizeof *t); + /* Bias up tracks that were recently added */ + if((s = kvp_get(data, "_noticed"))) { + const time_t noticed = atoll(s); - t->next = tracks; - t->track = track; - t->weight = weight; - tracks = t; - total_weight += weight; - ++ntracks; + 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 0; + + return BASE_WEIGHT; } /** @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; + unsigned char buf[(sizeof(unsigned long long) * CHAR_BIT + 7)/8], m; + unsigned long long t, r, slop; + int i, nby, nbi; - 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; + 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 Pick a track at random and write it to stdout */ -static void pick_track(void) { - long long w; - struct weighted_track *t; +/** @brief Called for each track */ +static int collect_tracks_callback(const char *track, + struct kvp *data, + struct kvp *prefs, + void attribute((unused)) *u, + DB_TXN attribute((unused)) *tid) { + unsigned long weight = compute_weight(track, data, prefs); - w = pick_weight(total_weight); - t = tracks; - while(t && w >= t->weight) { - w -= t->weight; - t = t->next; + /* 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) { + total_weight += weight; + if (pick_weight(total_weight) < weight) + winning = track; } - if(!t) - fatal(0, "ran out of tracks but %lld weighting left", w); - xprintf("%s", t->track); + ntracks++; + return 0; } int main(int argc, char **argv) { @@ -237,6 +284,9 @@ int main(int argc, char **argv) { log_default = &log_syslog; } if(config_read(0)) fatal(0, "cannot read configuration"); + /* Find out current queue/recent list */ + queue_read(); + recent_read(); /* Generate the candidate track list */ trackdb_init(TRACKDB_NO_RECOVER); trackdb_open(TRACKDB_NO_UPGRADE|TRACKDB_READ_ONLY); @@ -252,11 +302,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; }