| 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 <config.h> |
| 30 | #include "types.h" |
| 31 | |
| 32 | #include <getopt.h> |
| 33 | #include <stdio.h> |
| 34 | #include <stdlib.h> |
| 35 | #include <db.h> |
| 36 | #include <locale.h> |
| 37 | #include <errno.h> |
| 38 | #include <sys/types.h> |
| 39 | #include <unistd.h> |
| 40 | #include <pcre.h> |
| 41 | #include <string.h> |
| 42 | #include <fcntl.h> |
| 43 | #include <syslog.h> |
| 44 | #include <time.h> |
| 45 | |
| 46 | #include "configuration.h" |
| 47 | #include "log.h" |
| 48 | #include "defs.h" |
| 49 | #include "mem.h" |
| 50 | #include "kvp.h" |
| 51 | #include "syscalls.h" |
| 52 | #include "printf.h" |
| 53 | #include "trackdb.h" |
| 54 | #include "trackdb-int.h" |
| 55 | #include "version.h" |
| 56 | #include "trackname.h" |
| 57 | #include "queue.h" |
| 58 | #include "server-queue.h" |
| 59 | |
| 60 | static DB_TXN *global_tid; |
| 61 | |
| 62 | static const struct option options[] = { |
| 63 | { "help", no_argument, 0, 'h' }, |
| 64 | { "version", no_argument, 0, 'V' }, |
| 65 | { "config", required_argument, 0, 'c' }, |
| 66 | { "debug", no_argument, 0, 'd' }, |
| 67 | { "no-debug", no_argument, 0, 'D' }, |
| 68 | { "syslog", no_argument, 0, 's' }, |
| 69 | { "no-syslog", no_argument, 0, 'S' }, |
| 70 | { 0, 0, 0, 0 } |
| 71 | }; |
| 72 | |
| 73 | /* display usage message and terminate */ |
| 74 | static void help(void) { |
| 75 | xprintf("Usage:\n" |
| 76 | " disorder-choose [OPTIONS]\n" |
| 77 | "Options:\n" |
| 78 | " --help, -h Display usage message\n" |
| 79 | " --version, -V Display version number\n" |
| 80 | " --config PATH, -c PATH Set configuration file\n" |
| 81 | " --debug, -d Turn on debugging\n" |
| 82 | " --[no-]syslog Enable/disable logging to syslog\n" |
| 83 | "\n" |
| 84 | "Track choose for DisOrder. Not intended to be run\n" |
| 85 | "directly.\n"); |
| 86 | xfclose(stdout); |
| 87 | exit(0); |
| 88 | } |
| 89 | /** @brief Sum of all weights */ |
| 90 | static unsigned long long total_weight; |
| 91 | |
| 92 | /** @brief The winning track */ |
| 93 | static const char *winning = 0; |
| 94 | |
| 95 | /** @brief Count of tracks */ |
| 96 | static long ntracks; |
| 97 | |
| 98 | static char **required_tags; |
| 99 | static char **prohibited_tags; |
| 100 | |
| 101 | static int queue_contains(const struct queue_entry *head, |
| 102 | const char *track) { |
| 103 | const struct queue_entry *q; |
| 104 | |
| 105 | for(q = head->next; q != head; q = q->next) |
| 106 | if(!strcmp(q->track, track)) |
| 107 | return 1; |
| 108 | return 0; |
| 109 | } |
| 110 | |
| 111 | /** @brief Compute the weight of a track |
| 112 | * @param track Track name (UTF-8) |
| 113 | * @param data Track data |
| 114 | * @param prefs Track preferences |
| 115 | * @return Track weight (non-negative) |
| 116 | * |
| 117 | * Tracks to be excluded entirely are given a weight of 0. |
| 118 | */ |
| 119 | static unsigned long compute_weight(const char *track, |
| 120 | struct kvp *data, |
| 121 | struct kvp *prefs) { |
| 122 | const char *s; |
| 123 | char **track_tags; |
| 124 | time_t last, now; |
| 125 | |
| 126 | /* Reject tracks not in any collection (race between edit config and |
| 127 | * rescan) */ |
| 128 | if(!find_track_root(track)) { |
| 129 | info("found track not in any collection: %s", track); |
| 130 | return 0; |
| 131 | } |
| 132 | |
| 133 | /* Reject aliases to avoid giving aliased tracks extra weight */ |
| 134 | if(kvp_get(data, "_alias_for")) |
| 135 | return 0; |
| 136 | |
| 137 | /* Reject tracks with random play disabled */ |
| 138 | if((s = kvp_get(prefs, "pick_at_random")) |
| 139 | && !strcmp(s, "0")) |
| 140 | return 0; |
| 141 | |
| 142 | /* Reject tracks played within the last 8 hours */ |
| 143 | if((s = kvp_get(prefs, "played_time"))) { |
| 144 | last = atoll(s); |
| 145 | now = time(0); |
| 146 | if(now < last + config->replay_min) |
| 147 | return 0; |
| 148 | } |
| 149 | |
| 150 | /* Reject tracks currently in the queue or in the recent list */ |
| 151 | if(queue_contains(&qhead, track) |
| 152 | || queue_contains(&phead, track)) |
| 153 | return 0; |
| 154 | |
| 155 | /* We'll need tags for a number of things */ |
| 156 | track_tags = parsetags(kvp_get(prefs, "tags")); |
| 157 | |
| 158 | /* Reject tracks with prohibited tags */ |
| 159 | if(prohibited_tags && tag_intersection(track_tags, prohibited_tags)) |
| 160 | return 0; |
| 161 | |
| 162 | /* Reject tracks that lack required tags */ |
| 163 | if(*required_tags && !tag_intersection(track_tags, required_tags)) |
| 164 | return 0; |
| 165 | |
| 166 | /* Use the configured weight if available */ |
| 167 | if((s = kvp_get(prefs, "weight"))) { |
| 168 | long n; |
| 169 | errno = 0; |
| 170 | |
| 171 | n = strtol(s, 0, 10); |
| 172 | if((errno == 0 || errno == ERANGE) && n >= 0) |
| 173 | return n; |
| 174 | } |
| 175 | |
| 176 | return 90000; |
| 177 | } |
| 178 | |
| 179 | static unsigned char random_buffer[4096]; |
| 180 | static size_t random_left; |
| 181 | |
| 182 | /** @brief Fill [buf, buf+n) with random bytes */ |
| 183 | static void random_bytes(unsigned char *buf, size_t n) { |
| 184 | while(n > 0) { |
| 185 | if(random_left > 0) { |
| 186 | const size_t this_time = n > random_left ? random_left : n; |
| 187 | |
| 188 | memcpy(buf, random_buffer + random_left - this_time, this_time); |
| 189 | n -= this_time; |
| 190 | random_left -= this_time; |
| 191 | } else { |
| 192 | static int fd = -1; |
| 193 | int r; |
| 194 | |
| 195 | if(fd < 0) { |
| 196 | if((fd = open("/dev/urandom", O_RDONLY)) < 0) |
| 197 | fatal(errno, "opening /dev/urandom"); |
| 198 | } |
| 199 | if((r = read(fd, random_buffer, sizeof random_buffer)) < 0) |
| 200 | fatal(errno, "reading /dev/urandom"); |
| 201 | if((size_t)r < sizeof random_buffer) |
| 202 | fatal(0, "short read from /dev/urandom"); |
| 203 | random_left = sizeof random_buffer; |
| 204 | } |
| 205 | } |
| 206 | } |
| 207 | |
| 208 | /** @brief Pick a random integer uniformly from [0, limit) */ |
| 209 | static unsigned long long pick_weight(unsigned long long limit) { |
| 210 | unsigned char buf[(sizeof(unsigned long long) * CHAR_BIT + 7)/8], m; |
| 211 | unsigned long long t, r, slop; |
| 212 | int i, nby, nbi; |
| 213 | |
| 214 | //info("pick_weight: limit = %llu", limit); |
| 215 | |
| 216 | /* First, decide how many bits of output we actually need; do bytes first |
| 217 | * (they're quicker) and then bits. |
| 218 | * |
| 219 | * To speed this up, we could use a binary search if we knew where to |
| 220 | * start. (Note that shifting by ULLONG_BITS or more (if such a constant |
| 221 | * existed) is undefined behaviour, so we mustn't do that.) Figuring out a |
| 222 | * start point involves preprocessor and/or autoconf magic. |
| 223 | */ |
| 224 | for (nby = 1, t = (limit - 1) >> 8; t; nby++, t >>= 8) |
| 225 | ; |
| 226 | nbi = (nby - 1) << 3; t = limit >> nbi; |
| 227 | if (t >> 4) { t >>= 4; nbi += 4; } |
| 228 | if (t >> 2) { t >>= 2; nbi += 2; } |
| 229 | if (t >> 1) { t >>= 1; nbi += 1; } |
| 230 | nbi++; |
| 231 | //info("nby = %d; nbi = %d", nby, nbi); |
| 232 | |
| 233 | /* Main randomness collection loop. We read a number of bytes from the |
| 234 | * randomness source, and glue them together into an integer (dropping |
| 235 | * bits off the top byte as necessary). Call the result r; we have |
| 236 | * 2^{nbi - 1) <= limit < 2^nbi and r < 2^nbi. If r < limit then we win; |
| 237 | * otherwise we try again. Given the above bounds, we expect fewer than 2 |
| 238 | * iterations. |
| 239 | * |
| 240 | * Unfortunately there are subtleties. In particular, 2^nbi may in fact be |
| 241 | * zero due to overflow. So in fact what we do is compute slop = 2^nbi - |
| 242 | * limit > 0; if r < slop then we try again, otherwise r - slop is our |
| 243 | * winner. |
| 244 | */ |
| 245 | slop = (2 << (nbi - 1)) - limit; |
| 246 | m = nbi & 7 ? (1 << (nbi & 7)) - 1 : 0xff; |
| 247 | //info("slop = %llu", slop); |
| 248 | //info("m = 0x%02x", m); |
| 249 | |
| 250 | do { |
| 251 | /* Actually get some random data. */ |
| 252 | random_bytes(buf, nby); |
| 253 | |
| 254 | /* Clobber the top byte. */ |
| 255 | buf[0] &= m; |
| 256 | |
| 257 | /* Turn it into an integer. */ |
| 258 | for (r = 0, i = 0; i < nby; i++) |
| 259 | r = (r << 8) | buf[i]; |
| 260 | //info("r = %llu", r); |
| 261 | } while (r < slop); |
| 262 | |
| 263 | return r - slop; |
| 264 | } |
| 265 | |
| 266 | /** @brief Called for each track */ |
| 267 | static int collect_tracks_callback(const char *track, |
| 268 | struct kvp *data, |
| 269 | struct kvp *prefs, |
| 270 | void attribute((unused)) *u, |
| 271 | DB_TXN attribute((unused)) *tid) { |
| 272 | unsigned long weight = compute_weight(track, data, prefs); |
| 273 | |
| 274 | /* Decide whether this is the winning track. |
| 275 | * |
| 276 | * Suppose that we have n things, and thing i, for 0 <= i < n, has weight |
| 277 | * w_i. Let c_i = w_0 + ... + w_{i-1} be the cumulative weight of the |
| 278 | * things previous to thing i, and let W = c_n = w_0 + ... + w_{i-1} be the |
| 279 | * total weight. We can clearly choose a random thing with the correct |
| 280 | * weightings by picking a random number r in [0, W) and chooeing thing i |
| 281 | * where c_i <= r < c_i + w_i. But this involves having an enormous list |
| 282 | * and taking two passes over it (which has bad locality and is ugly). |
| 283 | * |
| 284 | * Here's another way. Initialize v = -1. Examine the things in order; |
| 285 | * for thing i, choose a random number r_i in [0, c_i + w_i). If r_i < w_i |
| 286 | * then set v <- i. |
| 287 | * |
| 288 | * Claim. For all 0 <= i < n, the above algorithm chooses thing i with |
| 289 | * probability w_i/W. |
| 290 | * |
| 291 | * Proof. Induction on n. The claim is clear for n = 1. Suppose it's |
| 292 | * true for n - 1. Let L be the event that we choose thing n - 1. Clearly |
| 293 | * Pr[L] = w_{n-1}/W. Condition on not-L: then the probabilty that we |
| 294 | * choose thing i, for 0 <= i < n - 1, is w_i/c_{n-1} (induction |
| 295 | * hypothesis); undoing the conditioning gives the desired result. |
| 296 | */ |
| 297 | if(weight) { |
| 298 | total_weight += weight; |
| 299 | if (pick_weight(total_weight) < weight) |
| 300 | winning = track; |
| 301 | } |
| 302 | ntracks++; |
| 303 | return 0; |
| 304 | } |
| 305 | |
| 306 | int main(int argc, char **argv) { |
| 307 | int n, logsyslog = !isatty(2), err; |
| 308 | const char *tags; |
| 309 | |
| 310 | set_progname(argv); |
| 311 | mem_init(); |
| 312 | if(!setlocale(LC_CTYPE, "")) fatal(errno, "error calling setlocale"); |
| 313 | while((n = getopt_long(argc, argv, "hVc:dDSs", options, 0)) >= 0) { |
| 314 | switch(n) { |
| 315 | case 'h': help(); |
| 316 | case 'V': version("disorder-choose"); |
| 317 | case 'c': configfile = optarg; break; |
| 318 | case 'd': debugging = 1; break; |
| 319 | case 'D': debugging = 0; break; |
| 320 | case 'S': logsyslog = 0; break; |
| 321 | case 's': logsyslog = 1; break; |
| 322 | default: fatal(0, "invalid option"); |
| 323 | } |
| 324 | } |
| 325 | if(logsyslog) { |
| 326 | openlog(progname, LOG_PID, LOG_DAEMON); |
| 327 | log_default = &log_syslog; |
| 328 | } |
| 329 | if(config_read(0)) fatal(0, "cannot read configuration"); |
| 330 | /* Find out current queue/recent list */ |
| 331 | queue_read(); |
| 332 | recent_read(); |
| 333 | /* Generate the candidate track list */ |
| 334 | trackdb_init(TRACKDB_NO_RECOVER); |
| 335 | trackdb_open(TRACKDB_NO_UPGRADE|TRACKDB_READ_ONLY); |
| 336 | global_tid = trackdb_begin_transaction(); |
| 337 | if((err = trackdb_get_global_tid("required-tags", global_tid, &tags))) |
| 338 | fatal(0, "error getting required-tags: %s", db_strerror(err)); |
| 339 | required_tags = parsetags(tags); |
| 340 | if((err = trackdb_get_global_tid("prohibited-tags", global_tid, &tags))) |
| 341 | fatal(0, "error getting prohibited-tags: %s", db_strerror(err)); |
| 342 | prohibited_tags = parsetags(tags); |
| 343 | if(trackdb_scan(0, collect_tracks_callback, 0, global_tid)) |
| 344 | exit(1); |
| 345 | trackdb_commit_transaction(global_tid); |
| 346 | trackdb_close(); |
| 347 | trackdb_deinit(); |
| 348 | //info("ntracks=%ld total_weight=%lld", ntracks, total_weight); |
| 349 | if(!total_weight) |
| 350 | fatal(0, "no tracks match random choice criteria"); |
| 351 | if(!winning) |
| 352 | fatal(0, "internal: failed to pick a track"); |
| 353 | /* Pick a track */ |
| 354 | xprintf("%s", winning); |
| 355 | xfclose(stdout); |
| 356 | return 0; |
| 357 | } |
| 358 | |
| 359 | /* |
| 360 | Local Variables: |
| 361 | c-basic-offset:2 |
| 362 | comment-column:40 |
| 363 | fill-column:79 |
| 364 | indent-tabs-mode:nil |
| 365 | End: |
| 366 | */ |