chiark - git - mdw - disorder/blob - server/choose.c

   1 /*
   2  * This file is part of DisOrder
   3  * Copyright (C) 2008 Richard Kettlewell
   4  * Copyright (C) 2008 Mark Wooding
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  19  * USA
  20  */
  21 /** @file choose.c
  22  * @brief Random track chooser
  23  *
  24  * Picks a track at random and writes it to standard output.  If for
  25  * any reason no track can be picked - even a trivial reason like a
  26  * deadlock - it just exits and expects the server to try again.
  27  */
  28
  29 #include "disorder-server.h"
  30
  31 #define BASE_WEIGHT 90000
  32
  33 static DB_TXN *global_tid;
  34
  35 static const struct option options[] = {
  36   { "help", no_argument, 0, 'h' },
  37   { "version", no_argument, 0, 'V' },
  38   { "config", required_argument, 0, 'c' },
  39   { "debug", no_argument, 0, 'd' },
  40   { "no-debug", no_argument, 0, 'D' },
  41   { "syslog", no_argument, 0, 's' },
  42   { "no-syslog", no_argument, 0, 'S' },
  43   { 0, 0, 0, 0 }
  44 };
  45
  46 /* display usage message and terminate */
  47 static void help(void) {
  48   xprintf("Usage:\n"
  49           "  disorder-choose [OPTIONS]\n"
  50           "Options:\n"
  51           "  --help, -h              Display usage message\n"
  52           "  --version, -V           Display version number\n"
  53           "  --config PATH, -c PATH  Set configuration file\n"
  54           "  --debug, -d             Turn on debugging\n"
  55           "  --[no-]syslog           Enable/disable logging to syslog\n"
  56           "\n"
  57           "Track choose for DisOrder.  Not intended to be run\n"
  58           "directly.\n");
  59   xfclose(stdout);
  60   exit(0);
  61 }
  62 /** @brief Sum of all weights */
  63 static unsigned long long total_weight;
  64
  65 /** @brief The winning track */
  66 static const char *winning = 0;
  67
  68 /** @brief Count of tracks */
  69 static long ntracks;
  70
  71 static char **required_tags;
  72 static char **prohibited_tags;
  73
  74 static int queue_contains(const struct queue_entry *head,
  75                           const char *track) {
  76   const struct queue_entry *q;
  77
  78   for(q = head->next; q != head; q = q->next)
  79     if(!strcmp(q->track, track))
  80       return 1;
  81   return 0;
  82 }
  83
  84 /** @brief Compute the weight of a track
  85  * @param track Track name (UTF-8)
  86  * @param data Track data
  87  * @param prefs Track preferences
  88  * @return Track weight (non-negative)
  89  *
  90  * Tracks to be excluded entirely are given a weight of 0.
  91  */
  92 static unsigned long compute_weight(const char *track,
  93                                     struct kvp *data,
  94                                     struct kvp *prefs) {
  95   const char *s;
  96   char **track_tags;
  97   time_t last, now = time(0);
  98
  99   /* Reject tracks not in any collection (race between edit config and
 100    * rescan) */
 101   if(!find_track_root(track)) {
 102     info("found track not in any collection: %s", track);
 103     return 0;
 104   }
 105
 106   /* Reject aliases to avoid giving aliased tracks extra weight */
 107   if(kvp_get(data, "_alias_for"))
 108     return 0;
 109
 110   /* Reject tracks with random play disabled */
 111   if((s = kvp_get(prefs, "pick_at_random"))
 112      && !strcmp(s, "0"))
 113     return 0;
 114
 115   /* Reject tracks played within the last 8 hours */
 116   if((s = kvp_get(prefs, "played_time"))) {
 117     last = atoll(s);
 118     if(now < last + config->replay_min)
 119       return 0;
 120   }
 121
 122   /* Reject tracks currently in the queue or in the recent list */
 123   if(queue_contains(&qhead, track)
 124      || queue_contains(&phead, track))
 125     return 0;
 126
 127   /* We'll need tags for a number of things */
 128   track_tags = parsetags(kvp_get(prefs, "tags"));
 129
 130   /* Reject tracks with prohibited tags */
 131   if(prohibited_tags && tag_intersection(track_tags, prohibited_tags))
 132     return 0;
 133
 134   /* Reject tracks that lack required tags */
 135   if(*required_tags && !tag_intersection(track_tags, required_tags))
 136     return 0;
 137
 138   /* Use the configured weight if available */
 139   if((s = kvp_get(prefs, "weight"))) {
 140     long n;
 141     errno = 0;
 142
 143     n = strtol(s, 0, 10);
 144     if((errno == 0 || errno == ERANGE) && n >= 0)
 145       return n;
 146   }
 147
 148   /* Bias up tracks that were recently added */
 149   if((s = kvp_get(data, "_noticed"))) {
 150     const time_t noticed = atoll(s);
 151
 152     if(noticed + config->new_bias_age < now)
 153       /* Currently we just step up the weight of tracks that are in range.  A
 154        * more sophisticated approach would be to linearly decay from new_bias
 155        * down to BASE_WEIGHT over the course of the new_bias_age interval
 156        * starting when the track is added. */
 157       return config->new_bias;
 158   }
 159
 160   return BASE_WEIGHT;
 161 }
 162
 163 /** @brief Pick a random integer uniformly from [0, limit) */
 164 static unsigned long long pick_weight(unsigned long long limit) {
 165   unsigned char buf[(sizeof(unsigned long long) * CHAR_BIT + 7)/8], m;
 166   unsigned long long t, r, slop;
 167   int i, nby, nbi;
 168
 169   D(("pick_weight: limit = %#016llx", limit));
 170
 171   /* First, decide how many bits of output we actually need; do bytes first
 172    * (they're quicker) and then bits.
 173    *
 174    * To speed this up, we could use a binary search if we knew where to
 175    * start.  (Note that shifting by ULLONG_BITS or more (if such a constant
 176    * existed) is undefined behaviour, so we mustn't do that.)  Figuring out a
 177    * start point involves preprocessor and/or autoconf magic.
 178    */
 179   for (nby = 1, t = (limit - 1) >> 8; t; nby++, t >>= 8)
 180     ;
 181   nbi = (nby - 1) << 3; t = limit >> nbi;
 182   if (t >> 4) { t >>= 4; nbi += 4; }
 183   if (t >> 2) { t >>= 2; nbi += 2; }
 184   if (t >> 1) { t >>= 1; nbi += 1; }
 185   nbi++;
 186   D(("nby = %d; nbi = %d", nby, nbi));
 187
 188   /* Main randomness collection loop.  We read a number of bytes from the
 189    * randomness source, and glue them together into an integer (dropping
 190    * bits off the top byte as necessary).  Call the result r; we have
 191    * 2^{nbi - 1) <= limit < 2^nbi and r < 2^nbi.  If r < limit then we win;
 192    * otherwise we try again.  Given the above bounds, we expect fewer than 2
 193    * iterations.
 194    *
 195    * Unfortunately there are subtleties.  In particular, 2^nbi may in fact be
 196    * zero due to overflow.  So in fact what we do is compute slop = 2^nbi -
 197    * limit > 0; if r < slop then we try again, otherwise r - slop is our
 198    * winner.
 199    */
 200   slop = ((unsigned long long)2 << (nbi - 1)) - limit;
 201   m = nbi & 7 ? (1 << (nbi & 7)) - 1 : 0xff;
 202   D(("slop = %#016llx", slop));
 203   D(("m = 0x%02x", m));
 204
 205   do {
 206     /* Actually get some random data. */
 207     random_get(buf, nby);
 208
 209     /* Clobber the top byte.  */
 210     buf[0] &= m;
 211
 212     /* Turn it into an integer.  */
 213     for (r = 0, i = 0; i < nby; i++)
 214       r = (r << 8) | buf[i];
 215     D(("r = %#016llx", r));
 216   } while (r < slop);
 217
 218   D(("  result=%#016llx", r - slop));
 219   return r - slop;
 220 }
 221
 222 /** @brief Called for each track */
 223 static int collect_tracks_callback(const char *track,
 224                                    struct kvp *data,
 225                                    struct kvp *prefs,
 226                                    void attribute((unused)) *u,
 227                                    DB_TXN attribute((unused)) *tid) {
 228   unsigned long weight = compute_weight(track, data, prefs);
 229
 230   /* Decide whether this is the winning track.
 231    *
 232    * Suppose that we have n things, and thing i, for 0 <= i < n, has weight
 233    * w_i.  Let c_i = w_0 + ... + w_{i-1} be the cumulative weight of the
 234    * things previous to thing i, and let W = c_n = w_0 + ... + w_{i-1} be the
 235    * total weight.  We can clearly choose a random thing with the correct
 236    * weightings by picking a random number r in [0, W) and chooeing thing i
 237    * where c_i <= r < c_i + w_i.  But this involves having an enormous list
 238    * and taking two passes over it (which has bad locality and is ugly).
 239    *
 240    * Here's another way.  Initialize v = -1.  Examine the things in order;
 241    * for thing i, choose a random number r_i in [0, c_i + w_i).  If r_i < w_i
 242    * then set v <- i.
 243    *
 244    * Claim.  For all 0 <= i < n, the above algorithm chooses thing i with
 245    * probability w_i/W.
 246    *
 247    * Proof.  Induction on n.   The claim is clear for n = 1.  Suppose it's
 248    * true for n - 1.  Let L be the event that we choose thing n - 1.  Clearly
 249    * Pr[L] = w_{n-1}/W.  Condition on not-L: then the probabilty that we
 250    * choose thing i, for 0 <= i < n - 1, is w_i/c_{n-1} (induction
 251    * hypothesis); undoing the conditioning gives the desired result.
 252    */
 253   D(("consider %s", track));
 254   if(weight) {
 255     total_weight += weight;
 256     if (pick_weight(total_weight) < weight)
 257       winning = track;
 258   }
 259   ntracks++;
 260   return 0;
 261 }
 262
 263 int main(int argc, char **argv) {
 264   int n, logsyslog = !isatty(2), err;
 265   const char *tags;
 266
 267   set_progname(argv);
 268   mem_init();
 269   if(!setlocale(LC_CTYPE, "")) fatal(errno, "error calling setlocale");
 270   while((n = getopt_long(argc, argv, "hVc:dDSs", options, 0)) >= 0) {
 271     switch(n) {
 272     case 'h': help();
 273     case 'V': version("disorder-choose");
 274     case 'c': configfile = optarg; break;
 275     case 'd': debugging = 1; break;
 276     case 'D': debugging = 0; break;
 277     case 'S': logsyslog = 0; break;
 278     case 's': logsyslog = 1; break;
 279     default: fatal(0, "invalid option");
 280     }
 281   }
 282   if(logsyslog) {
 283     openlog(progname, LOG_PID, LOG_DAEMON);
 284     log_default = &log_syslog;
 285   }
 286   if(config_read(0)) fatal(0, "cannot read configuration");
 287   /* Find out current queue/recent list */
 288   queue_read();
 289   recent_read();
 290   /* Generate the candidate track list */
 291   trackdb_init(TRACKDB_NO_RECOVER);
 292   trackdb_open(TRACKDB_NO_UPGRADE|TRACKDB_READ_ONLY);
 293   global_tid = trackdb_begin_transaction();
 294   if((err = trackdb_get_global_tid("required-tags", global_tid, &tags)))
 295     fatal(0, "error getting required-tags: %s", db_strerror(err));
 296   required_tags = parsetags(tags);
 297   if((err = trackdb_get_global_tid("prohibited-tags", global_tid, &tags)))
 298     fatal(0, "error getting prohibited-tags: %s", db_strerror(err));
 299   prohibited_tags = parsetags(tags);
 300   if(trackdb_scan(0, collect_tracks_callback, 0, global_tid))
 301     exit(1);
 302   trackdb_commit_transaction(global_tid);
 303   trackdb_close();
 304   trackdb_deinit();
 305   D(("ntracks=%ld total_weight=%lld", ntracks, total_weight));
 306   if(!total_weight)
 307     fatal(0, "no tracks match random choice criteria");
 308   if(!winning)
 309     fatal(0, "internal: failed to pick a track");
 310   /* Pick a track */
 311   xprintf("%s", winning);
 312   xfclose(stdout);
 313   return 0;
 314 }
 315
 316 /*
 317 Local Variables:
 318 c-basic-offset:2
 319 comment-column:40
 320 fill-column:79
 321 indent-tabs-mode:nil
 322 End:
 323 */