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