1 /* Copyright (c) 2001, Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4 * Copyright (c) 2007-2021, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6
7 /**
8 * @file pubsub_check.c
9 * @brief Enforce various requirements on a pubsub_builder.
10 **/
11
12 /** @{ */
13 #define PUBSUB_PRIVATE
14 /** @} */
15
16 #include "lib/dispatch/dispatch_naming.h"
17 #include "lib/dispatch/msgtypes.h"
18 #include "lib/pubsub/pubsub_flags.h"
19 #include "lib/pubsub/pubsub_builder_st.h"
20 #include "lib/pubsub/pubsub_build.h"
21
22 #include "lib/container/bitarray.h"
23 #include "lib/container/smartlist.h"
24 #include "lib/log/util_bug.h"
25 #include "lib/malloc/malloc.h"
26 #include "lib/string/compat_string.h"
27
28 #include <string.h>
29
30 static void pubsub_adjmap_add(pubsub_adjmap_t *map,
31 const pubsub_cfg_t *item);
32
33 /**
34 * Helper: construct and return a new pubsub_adjacency_map from <b>cfg</b>.
35 * Return NULL on error.
36 **/
37 static pubsub_adjmap_t *
pubsub_build_adjacency_map(const pubsub_items_t * cfg)38 pubsub_build_adjacency_map(const pubsub_items_t *cfg)
39 {
40 pubsub_adjmap_t *map = tor_malloc_zero(sizeof(*map));
41 const size_t n_subsystems = get_num_subsys_ids();
42 const size_t n_msgs = get_num_message_ids();
43
44 map->n_subsystems = n_subsystems;
45 map->n_msgs = n_msgs;
46
47 map->pub_by_subsys = tor_calloc(n_subsystems, sizeof(smartlist_t*));
48 map->sub_by_subsys = tor_calloc(n_subsystems, sizeof(smartlist_t*));
49 map->pub_by_msg = tor_calloc(n_msgs, sizeof(smartlist_t*));
50 map->sub_by_msg = tor_calloc(n_msgs, sizeof(smartlist_t*));
51
52 SMARTLIST_FOREACH_BEGIN(cfg->items, const pubsub_cfg_t *, item) {
53 pubsub_adjmap_add(map, item);
54 } SMARTLIST_FOREACH_END(item);
55
56 return map;
57 }
58
59 /**
60 * Helper: add a single pubsub_cfg_t to an adjacency map.
61 **/
62 static void
pubsub_adjmap_add(pubsub_adjmap_t * map,const pubsub_cfg_t * item)63 pubsub_adjmap_add(pubsub_adjmap_t *map,
64 const pubsub_cfg_t *item)
65 {
66 smartlist_t **by_subsys;
67 smartlist_t **by_msg;
68
69 tor_assert(item->subsys < map->n_subsystems);
70 tor_assert(item->msg < map->n_msgs);
71
72 if (item->is_publish) {
73 by_subsys = &map->pub_by_subsys[item->subsys];
74 by_msg = &map->pub_by_msg[item->msg];
75 } else {
76 by_subsys = &map->sub_by_subsys[item->subsys];
77 by_msg = &map->sub_by_msg[item->msg];
78 }
79
80 if (! *by_subsys)
81 *by_subsys = smartlist_new();
82 if (! *by_msg)
83 *by_msg = smartlist_new();
84 smartlist_add(*by_subsys, (void*) item);
85 smartlist_add(*by_msg, (void *) item);
86 }
87
88 /**
89 * Release all storage held by m and set m to NULL.
90 **/
91 #define pubsub_adjmap_free(m) \
92 FREE_AND_NULL(pubsub_adjmap_t, pubsub_adjmap_free_, m)
93
94 /**
95 * Free every element of an <b>n</b>-element array of smartlists, then
96 * free the array itself.
97 **/
98 static void
pubsub_adjmap_free_helper(smartlist_t ** lsts,size_t n)99 pubsub_adjmap_free_helper(smartlist_t **lsts, size_t n)
100 {
101 if (!lsts)
102 return;
103
104 for (unsigned i = 0; i < n; ++i) {
105 smartlist_free(lsts[i]);
106 }
107 tor_free(lsts);
108 }
109
110 /**
111 * Release all storage held by <b>map</b>.
112 **/
113 static void
pubsub_adjmap_free_(pubsub_adjmap_t * map)114 pubsub_adjmap_free_(pubsub_adjmap_t *map)
115 {
116 if (!map)
117 return;
118 pubsub_adjmap_free_helper(map->pub_by_subsys, map->n_subsystems);
119 pubsub_adjmap_free_helper(map->sub_by_subsys, map->n_subsystems);
120 pubsub_adjmap_free_helper(map->pub_by_msg, map->n_msgs);
121 pubsub_adjmap_free_helper(map->sub_by_msg, map->n_msgs);
122 tor_free(map);
123 }
124
125 /**
126 * Helper: return the length of <b>sl</b>, or 0 if sl is NULL.
127 **/
128 static int
smartlist_len_opt(const smartlist_t * sl)129 smartlist_len_opt(const smartlist_t *sl)
130 {
131 if (sl)
132 return smartlist_len(sl);
133 else
134 return 0;
135 }
136
137 /** Return a pointer to a statically allocated string encoding the
138 * dispatcher flags in <b>flags</b>. */
139 static const char *
format_flags(unsigned flags)140 format_flags(unsigned flags)
141 {
142 static char buf[32];
143 buf[0] = 0;
144 if (flags & DISP_FLAG_EXCL) {
145 strlcat(buf, " EXCL", sizeof(buf));
146 }
147 if (flags & DISP_FLAG_STUB) {
148 strlcat(buf, " STUB", sizeof(buf));
149 }
150 return buf[0] ? buf+1 : buf;
151 }
152
153 /**
154 * Log a message containing a description of <b>cfg</b> at severity, prefixed
155 * by the string <b>prefix</b>.
156 */
157 static void
pubsub_cfg_dump(const pubsub_cfg_t * cfg,int severity,const char * prefix)158 pubsub_cfg_dump(const pubsub_cfg_t *cfg, int severity, const char *prefix)
159 {
160 tor_assert(prefix);
161
162 tor_log(severity, LD_MESG,
163 "%s%s %s: %s{%s} on %s (%s) <%u %u %u %u %x> [%s:%d]",
164 prefix,
165 get_subsys_id_name(cfg->subsys),
166 cfg->is_publish ? "PUB" : "SUB",
167 get_message_id_name(cfg->msg),
168 get_msg_type_id_name(cfg->type),
169 get_channel_id_name(cfg->channel),
170 format_flags(cfg->flags),
171 cfg->subsys, cfg->msg, cfg->type, cfg->channel, cfg->flags,
172 cfg->added_by_file, cfg->added_by_line);
173 }
174
175 /**
176 * Helper: fill a bitarray <b>out</b> with entries corresponding to the
177 * subsystems listed in <b>items</b>.
178 **/
179 static void
get_message_bitarray(const pubsub_adjmap_t * map,const smartlist_t * items,bitarray_t ** out)180 get_message_bitarray(const pubsub_adjmap_t *map,
181 const smartlist_t *items,
182 bitarray_t **out)
183 {
184 *out = bitarray_init_zero((unsigned)map->n_subsystems);
185 if (! items)
186 return;
187
188 SMARTLIST_FOREACH_BEGIN(items, const pubsub_cfg_t *, cfg) {
189 bitarray_set(*out, cfg->subsys);
190 } SMARTLIST_FOREACH_END(cfg);
191 }
192
193 /**
194 * Helper for lint_message: check that all the pubsub_cfg_t items in the two
195 * respective smartlists obey our local graph topology rules.
196 *
197 * (Right now this is just a matter of "each subsystem only
198 * publishes/subscribes once; no subsystem is a publisher and subscriber for
199 * the same message.")
200 *
201 * Return 0 on success, -1 on failure.
202 **/
203 static int
lint_message_graph(const pubsub_adjmap_t * map,message_id_t msg,const smartlist_t * pub,const smartlist_t * sub)204 lint_message_graph(const pubsub_adjmap_t *map,
205 message_id_t msg,
206 const smartlist_t *pub,
207 const smartlist_t *sub)
208 {
209 bitarray_t *published_by = NULL;
210 bitarray_t *subscribed_by = NULL;
211 bool ok = true;
212
213 get_message_bitarray(map, pub, &published_by);
214 get_message_bitarray(map, sub, &subscribed_by);
215
216 /* Check whether any subsystem is publishing and subscribing the same
217 * message. [??]
218 */
219 for (unsigned i = 0; i < map->n_subsystems; ++i) {
220 if (bitarray_is_set(published_by, i) &&
221 bitarray_is_set(subscribed_by, i)) {
222 log_warn(LD_MESG|LD_BUG,
223 "Message \"%s\" is published and subscribed by the same "
224 "subsystem \"%s\".",
225 get_message_id_name(msg),
226 get_subsys_id_name(i));
227 ok = false;
228 }
229 }
230
231 bitarray_free(published_by);
232 bitarray_free(subscribed_by);
233
234 return ok ? 0 : -1;
235 }
236
237 /**
238 * Helper for lint_message: check that all the pubsub_cfg_t items in the two
239 * respective smartlists have compatible flags, channels, and types.
240 **/
241 static int
lint_message_consistency(message_id_t msg,const smartlist_t * pub,const smartlist_t * sub)242 lint_message_consistency(message_id_t msg,
243 const smartlist_t *pub,
244 const smartlist_t *sub)
245 {
246 if (!smartlist_len_opt(pub) && !smartlist_len_opt(sub))
247 return 0; // LCOV_EXCL_LINE -- this was already checked.
248
249 /* The 'all' list has the publishers and the subscribers. */
250 smartlist_t *all = smartlist_new();
251 if (pub)
252 smartlist_add_all(all, pub);
253 if (sub)
254 smartlist_add_all(all, sub);
255
256 const pubsub_cfg_t *item0 = smartlist_get(all, 0);
257
258 /* Indicates which subsystems we've found publishing/subscribing here. */
259 bool pub_excl = false, sub_excl = false, chan_same = true, type_same = true;
260
261 /* Simple message consistency properties across messages.
262 */
263 SMARTLIST_FOREACH_BEGIN(all, const pubsub_cfg_t *, cfg) {
264 chan_same &= (cfg->channel == item0->channel);
265 type_same &= (cfg->type == item0->type);
266 if (cfg->is_publish)
267 pub_excl |= (cfg->flags & DISP_FLAG_EXCL) != 0;
268 else
269 sub_excl |= (cfg->flags & DISP_FLAG_EXCL) != 0;
270 } SMARTLIST_FOREACH_END(cfg);
271
272 bool ok = true;
273
274 if (! chan_same) {
275 log_warn(LD_MESG|LD_BUG,
276 "Message \"%s\" is associated with multiple inconsistent "
277 "channels.",
278 get_message_id_name(msg));
279 ok = false;
280 }
281 if (! type_same) {
282 log_warn(LD_MESG|LD_BUG,
283 "Message \"%s\" is associated with multiple inconsistent "
284 "message types.",
285 get_message_id_name(msg));
286 ok = false;
287 }
288
289 /* Enforce exclusive-ness for publishers and subscribers that have asked for
290 * it.
291 */
292 if (pub_excl && smartlist_len_opt(pub) > 1) {
293 log_warn(LD_MESG|LD_BUG,
294 "Message \"%s\" has multiple publishers, but at least one is "
295 "marked as exclusive.",
296 get_message_id_name(msg));
297 ok = false;
298 }
299 if (sub_excl && smartlist_len_opt(sub) > 1) {
300 log_warn(LD_MESG|LD_BUG,
301 "Message \"%s\" has multiple subscribers, but at least one is "
302 "marked as exclusive.",
303 get_message_id_name(msg));
304 ok = false;
305 }
306
307 smartlist_free(all);
308
309 return ok ? 0 : -1;
310 }
311
312 /**
313 * Check whether there are any errors or inconsistencies for the message
314 * described by <b>msg</b> in <b>map</b>. If there are problems, log about
315 * them, and return -1. Otherwise return 0.
316 **/
317 static int
lint_message(const pubsub_adjmap_t * map,message_id_t msg)318 lint_message(const pubsub_adjmap_t *map, message_id_t msg)
319 {
320 /* NOTE: Some of the checks in this function are maybe over-zealous, and we
321 * might not want to have them forever. I've marked them with [?] below.
322 */
323 if (BUG(msg >= map->n_msgs))
324 return 0; // LCOV_EXCL_LINE
325
326 const smartlist_t *pub = map->pub_by_msg[msg];
327 const smartlist_t *sub = map->sub_by_msg[msg];
328
329 const size_t n_pub = smartlist_len_opt(pub);
330 const size_t n_sub = smartlist_len_opt(sub);
331
332 if (n_pub == 0 && n_sub == 0) {
333 log_info(LD_MESG, "Nobody is publishing or subscribing to message "
334 "\"%s\".",
335 get_message_id_name(msg));
336 return 0; // No publishers or subscribers: nothing to do.
337 }
338 /* We'll set this to false if there are any problems. */
339 bool ok = true;
340
341 /* First make sure that if there are publishers, there are subscribers. */
342 if (n_pub == 0) {
343 log_warn(LD_MESG|LD_BUG,
344 "Message \"%s\" has subscribers, but no publishers.",
345 get_message_id_name(msg));
346 ok = false;
347 } else if (n_sub == 0) {
348 log_warn(LD_MESG|LD_BUG,
349 "Message \"%s\" has publishers, but no subscribers.",
350 get_message_id_name(msg));
351 ok = false;
352 }
353
354 /* Check the message graph topology. */
355 if (lint_message_graph(map, msg, pub, sub) < 0)
356 ok = false;
357
358 /* Check whether the messages have the same fields set on them. */
359 if (lint_message_consistency(msg, pub, sub) < 0)
360 ok = false;
361
362 if (!ok) {
363 /* There was a problem -- let's log all the publishers and subscribers on
364 * this message */
365 if (pub) {
366 SMARTLIST_FOREACH(pub, pubsub_cfg_t *, cfg,
367 pubsub_cfg_dump(cfg, LOG_WARN, " "));
368 }
369 if (sub) {
370 SMARTLIST_FOREACH(sub, pubsub_cfg_t *, cfg,
371 pubsub_cfg_dump(cfg, LOG_WARN, " "));
372 }
373 }
374
375 return ok ? 0 : -1;
376 }
377
378 /**
379 * Check all the messages in <b>map</b> for consistency. Return 0 on success,
380 * -1 on problems.
381 **/
382 static int
pubsub_adjmap_check(const pubsub_adjmap_t * map)383 pubsub_adjmap_check(const pubsub_adjmap_t *map)
384 {
385 bool all_ok = true;
386 for (unsigned i = 0; i < map->n_msgs; ++i) {
387 if (lint_message(map, i) < 0) {
388 all_ok = false;
389 }
390 }
391 return all_ok ? 0 : -1;
392 }
393
394 /**
395 * Check builder for consistency and various constraints. Return 0 on success,
396 * -1 on failure.
397 **/
398 int
pubsub_builder_check(pubsub_builder_t * builder)399 pubsub_builder_check(pubsub_builder_t *builder)
400 {
401 pubsub_adjmap_t *map = pubsub_build_adjacency_map(builder->items);
402 int rv = -1;
403
404 if (!map)
405 goto err; // should be impossible
406
407 if (pubsub_adjmap_check(map) < 0)
408 goto err;
409
410 rv = 0;
411 err:
412 pubsub_adjmap_free(map);
413 return rv;
414 }
415