chiark / gitweb /
Linux build fix
[disorder] / 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 */