chiark / gitweb /
Fix a few of the things the Clang static analyzer detects:
[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 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 = xtime(0);
96
97   /* Reject tracks not in any collection (race between edit config and
98    * rescan) */
99   if(!find_track_root(track)) {
100     disorder_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, "")) disorder_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: disorder_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, NULL)) disorder_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     disorder_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     disorder_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(NULL);
305   D(("ntracks=%ld total_weight=%lld", ntracks, total_weight));
306   if(!total_weight)
307     disorder_fatal(0, "no tracks match random choice criteria");
308   if(!winning)
309     disorder_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 */