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