src/libsystemd/sd-hwdb/sd-hwdb.c

   1 /***
   2   This file is part of systemd.
   3
   4   Copyright 2012 Kay Sievers <kay@vrfy.org>
   5   Copyright 2008 Alan Jenkins <alan.christopher.jenkins@googlemail.com>
   6   Copyright 2014 Tom Gundersen <teg@jklm.no>
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include <errno.h>
  23 #include <fnmatch.h>
  24 #include <inttypes.h>
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <sys/mman.h>
  29
  30 #include "sd-hwdb.h"
  31
  32 #include "alloc-util.h"
  33 #include "fd-util.h"
  34 #include "hashmap.h"
  35 #include "hwdb-internal.h"
  36 #include "hwdb-util.h"
  37 #include "refcnt.h"
  38 #include "string-util.h"
  39
  40 struct sd_hwdb {
  41         RefCount n_ref;
  42         int refcount;
  43
  44         FILE *f;
  45         struct stat st;
  46         union {
  47                 struct trie_header_f *head;
  48                 const char *map;
  49         };
  50
  51         OrderedHashmap *properties;
  52         Iterator properties_iterator;
  53         bool properties_modified;
  54 };
  55
  56 struct linebuf {
  57         char bytes[LINE_MAX];
  58         size_t size;
  59         size_t len;
  60 };
  61
  62 static void linebuf_init(struct linebuf *buf) {
  63         buf->size = 0;
  64         buf->len = 0;
  65 }
  66
  67 static const char *linebuf_get(struct linebuf *buf) {
  68         if (buf->len + 1 >= sizeof(buf->bytes))
  69                 return NULL;
  70         buf->bytes[buf->len] = '\0';
  71         return buf->bytes;
  72 }
  73
  74 static bool linebuf_add(struct linebuf *buf, const char *s, size_t len) {
  75         if (buf->len + len >= sizeof(buf->bytes))
  76                 return false;
  77         memcpy(buf->bytes + buf->len, s, len);
  78         buf->len += len;
  79         return true;
  80 }
  81
  82 static bool linebuf_add_char(struct linebuf *buf, char c) {
  83         if (buf->len + 1 >= sizeof(buf->bytes))
  84                 return false;
  85         buf->bytes[buf->len++] = c;
  86         return true;
  87 }
  88
  89 static void linebuf_rem(struct linebuf *buf, size_t count) {
  90         assert(buf->len >= count);
  91         buf->len -= count;
  92 }
  93
  94 static void linebuf_rem_char(struct linebuf *buf) {
  95         linebuf_rem(buf, 1);
  96 }
  97
  98 static const struct trie_child_entry_f *trie_node_child(sd_hwdb *hwdb, const struct trie_node_f *node, size_t idx) {
  99         const char *base = (const char *)node;
 100
 101         base += le64toh(hwdb->head->node_size);
 102         base += idx * le64toh(hwdb->head->child_entry_size);
 103         return (const struct trie_child_entry_f *)base;
 104 }
 105
 106 static const struct trie_value_entry_f *trie_node_value(sd_hwdb *hwdb, const struct trie_node_f *node, size_t idx) {
 107         const char *base = (const char *)node;
 108
 109         base += le64toh(hwdb->head->node_size);
 110         base += node->children_count * le64toh(hwdb->head->child_entry_size);
 111         base += idx * le64toh(hwdb->head->value_entry_size);
 112         return (const struct trie_value_entry_f *)base;
 113 }
 114
 115 static const struct trie_node_f *trie_node_from_off(sd_hwdb *hwdb, le64_t off) {
 116         return (const struct trie_node_f *)(hwdb->map + le64toh(off));
 117 }
 118
 119 static const char *trie_string(sd_hwdb *hwdb, le64_t off) {
 120         return hwdb->map + le64toh(off);
 121 }
 122
 123 static int trie_children_cmp_f(const void *v1, const void *v2) {
 124         const struct trie_child_entry_f *n1 = v1;
 125         const struct trie_child_entry_f *n2 = v2;
 126
 127         return n1->c - n2->c;
 128 }
 129
 130 static const struct trie_node_f *node_lookup_f(sd_hwdb *hwdb, const struct trie_node_f *node, uint8_t c) {
 131         struct trie_child_entry_f *child;
 132         struct trie_child_entry_f search;
 133
 134         search.c = c;
 135         child = bsearch(&search, (const char *)node + le64toh(hwdb->head->node_size), node->children_count,
 136                         le64toh(hwdb->head->child_entry_size), trie_children_cmp_f);
 137         if (child)
 138                 return trie_node_from_off(hwdb, child->child_off);
 139         return NULL;
 140 }
 141
 142 static int hwdb_add_property(sd_hwdb *hwdb, const struct trie_value_entry_f *entry) {
 143         const char *key;
 144         int r;
 145
 146         assert(hwdb);
 147
 148         key = trie_string(hwdb, entry->key_off);
 149
 150         /*
 151          * Silently ignore all properties which do not start with a
 152          * space; future extensions might use additional prefixes.
 153          */
 154         if (key[0] != ' ')
 155                 return 0;
 156
 157         key++;
 158
 159         if (le64toh(hwdb->head->value_entry_size) >= sizeof(struct trie_value_entry2_f)) {
 160                 const struct trie_value_entry2_f *old, *entry2;
 161
 162                 entry2 = (const struct trie_value_entry2_f *)entry;
 163                 old = ordered_hashmap_get(hwdb->properties, key);
 164                 if (old) {
 165                         /* On duplicates, we order by filename priority and line-number.
 166                          *
 167                          *
 168                          * v2 of the format had 64 bits for the line number.
 169                          * v3 reuses top 32 bits of line_number to store the priority.
 170                          * We check the top bits — if they are zero we have v2 format.
 171                          * This means that v2 clients will print wrong line numbers with
 172                          * v3 data.
 173                          *
 174                          * For v3 data: we compare the priority (of the source file)
 175                          * and the line number.
 176                          *
 177                          * For v2 data: we rely on the fact that the filenames in the hwdb
 178                          * are added in the order of priority (higher later), because they
 179                          * are *processed* in the order of priority. So we compare the
 180                          * indices to determine which file had higher priority. Comparing
 181                          * the strings alphabetically would be useless, because those are
 182                          * full paths, and e.g. /usr/lib would sort after /etc, even
 183                          * though it has lower priority. This is not reliable because of
 184                          * suffix compression, but should work for the most common case of
 185                          * /usr/lib/udev/hwbd.d and /etc/udev/hwdb.d, and is better than
 186                          * not doing the comparison at all.
 187                          */
 188                         bool lower;
 189
 190                         if (entry2->file_priority == 0)
 191                                 lower = entry2->filename_off < old->filename_off ||
 192                                         (entry2->filename_off == old->filename_off && entry2->line_number < old->line_number);
 193                         else
 194                                 lower = entry2->file_priority < old->file_priority ||
 195                                         (entry2->file_priority == old->file_priority && entry2->line_number < old->line_number);
 196                         if (lower)
 197                                 return 0;
 198                 }
 199         }
 200
 201         r = ordered_hashmap_ensure_allocated(&hwdb->properties, &string_hash_ops);
 202         if (r < 0)
 203                 return r;
 204
 205         r = ordered_hashmap_replace(hwdb->properties, key, (void *)entry);
 206         if (r < 0)
 207                 return r;
 208
 209         hwdb->properties_modified = true;
 210
 211         return 0;
 212 }
 213
 214 static int trie_fnmatch_f(sd_hwdb *hwdb, const struct trie_node_f *node, size_t p,
 215                           struct linebuf *buf, const char *search) {
 216         size_t len;
 217         size_t i;
 218         const char *prefix;
 219         int err;
 220
 221         prefix = trie_string(hwdb, node->prefix_off);
 222         len = strlen(prefix + p);
 223         linebuf_add(buf, prefix + p, len);
 224
 225         for (i = 0; i < node->children_count; i++) {
 226                 const struct trie_child_entry_f *child = trie_node_child(hwdb, node, i);
 227
 228                 linebuf_add_char(buf, child->c);
 229                 err = trie_fnmatch_f(hwdb, trie_node_from_off(hwdb, child->child_off), 0, buf, search);
 230                 if (err < 0)
 231                         return err;
 232                 linebuf_rem_char(buf);
 233         }
 234
 235         if (le64toh(node->values_count) && fnmatch(linebuf_get(buf), search, 0) == 0)
 236                 for (i = 0; i < le64toh(node->values_count); i++) {
 237                         err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, i));
 238                         if (err < 0)
 239                                 return err;
 240                 }
 241
 242         linebuf_rem(buf, len);
 243         return 0;
 244 }
 245
 246 static int trie_search_f(sd_hwdb *hwdb, const char *search) {
 247         struct linebuf buf;
 248         const struct trie_node_f *node;
 249         size_t i = 0;
 250         int err;
 251
 252         linebuf_init(&buf);
 253
 254         node = trie_node_from_off(hwdb, hwdb->head->nodes_root_off);
 255         while (node) {
 256                 const struct trie_node_f *child;
 257                 size_t p = 0;
 258
 259                 if (node->prefix_off) {
 260                         uint8_t c;
 261
 262                         for (; (c = trie_string(hwdb, node->prefix_off)[p]); p++) {
 263                                 if (IN_SET(c, '*', '?', '['))
 264                                         return trie_fnmatch_f(hwdb, node, p, &buf, search + i + p);
 265                                 if (c != search[i + p])
 266                                         return 0;
 267                         }
 268                         i += p;
 269                 }
 270
 271                 child = node_lookup_f(hwdb, node, '*');
 272                 if (child) {
 273                         linebuf_add_char(&buf, '*');
 274                         err = trie_fnmatch_f(hwdb, child, 0, &buf, search + i);
 275                         if (err < 0)
 276                                 return err;
 277                         linebuf_rem_char(&buf);
 278                 }
 279
 280                 child = node_lookup_f(hwdb, node, '?');
 281                 if (child) {
 282                         linebuf_add_char(&buf, '?');
 283                         err = trie_fnmatch_f(hwdb, child, 0, &buf, search + i);
 284                         if (err < 0)
 285                                 return err;
 286                         linebuf_rem_char(&buf);
 287                 }
 288
 289                 child = node_lookup_f(hwdb, node, '[');
 290                 if (child) {
 291                         linebuf_add_char(&buf, '[');
 292                         err = trie_fnmatch_f(hwdb, child, 0, &buf, search + i);
 293                         if (err < 0)
 294                                 return err;
 295                         linebuf_rem_char(&buf);
 296                 }
 297
 298                 if (search[i] == '\0') {
 299                         size_t n;
 300
 301                         for (n = 0; n < le64toh(node->values_count); n++) {
 302                                 err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, n));
 303                                 if (err < 0)
 304                                         return err;
 305                         }
 306                         return 0;
 307                 }
 308
 309                 child = node_lookup_f(hwdb, node, search[i]);
 310                 node = child;
 311                 i++;
 312         }
 313         return 0;
 314 }
 315
 316 static const char hwdb_bin_paths[] =
 317         "/etc/systemd/hwdb/hwdb.bin\0"
 318         "/etc/udev/hwdb.bin\0"
 319         "/usr/lib/systemd/hwdb/hwdb.bin\0"
 320 #if HAVE_SPLIT_USR
 321         "/lib/systemd/hwdb/hwdb.bin\0"
 322 #endif
 323         UDEVLIBEXECDIR "/hwdb.bin\0";
 324
 325 _public_ int sd_hwdb_new(sd_hwdb **ret) {
 326         _cleanup_(sd_hwdb_unrefp) sd_hwdb *hwdb = NULL;
 327         const char *hwdb_bin_path;
 328         const char sig[] = HWDB_SIG;
 329
 330         assert_return(ret, -EINVAL);
 331
 332         hwdb = new0(sd_hwdb, 1);
 333         if (!hwdb)
 334                 return -ENOMEM;
 335
 336         hwdb->n_ref = REFCNT_INIT;
 337
 338         /* find hwdb.bin in hwdb_bin_paths */
 339         NULSTR_FOREACH(hwdb_bin_path, hwdb_bin_paths) {
 340                 hwdb->f = fopen(hwdb_bin_path, "re");
 341                 if (hwdb->f)
 342                         break;
 343                 else if (errno == ENOENT)
 344                         continue;
 345                 else
 346                         return log_debug_errno(errno, "error reading %s: %m", hwdb_bin_path);
 347         }
 348
 349         if (!hwdb->f) {
 350                 log_debug("hwdb.bin does not exist, please run systemd-hwdb update");
 351                 return -ENOENT;
 352         }
 353
 354         if (fstat(fileno(hwdb->f), &hwdb->st) < 0 ||
 355             (size_t)hwdb->st.st_size < offsetof(struct trie_header_f, strings_len) + 8)
 356                 return log_debug_errno(errno, "error reading %s: %m", hwdb_bin_path);
 357
 358         hwdb->map = mmap(0, hwdb->st.st_size, PROT_READ, MAP_SHARED, fileno(hwdb->f), 0);
 359         if (hwdb->map == MAP_FAILED)
 360                 return log_debug_errno(errno, "error mapping %s: %m", hwdb_bin_path);
 361
 362         if (memcmp(hwdb->map, sig, sizeof(hwdb->head->signature)) != 0 ||
 363             (size_t)hwdb->st.st_size != le64toh(hwdb->head->file_size)) {
 364                 log_debug("error recognizing the format of %s", hwdb_bin_path);
 365                 return -EINVAL;
 366         }
 367
 368         log_debug("=== trie on-disk ===");
 369         log_debug("tool version:          %"PRIu64, le64toh(hwdb->head->tool_version));
 370         log_debug("file size:        %8"PRIi64" bytes", hwdb->st.st_size);
 371         log_debug("header size       %8"PRIu64" bytes", le64toh(hwdb->head->header_size));
 372         log_debug("strings           %8"PRIu64" bytes", le64toh(hwdb->head->strings_len));
 373         log_debug("nodes             %8"PRIu64" bytes", le64toh(hwdb->head->nodes_len));
 374
 375         *ret = hwdb;
 376         hwdb = NULL;
 377
 378         return 0;
 379 }
 380
 381 _public_ sd_hwdb *sd_hwdb_ref(sd_hwdb *hwdb) {
 382         assert_return(hwdb, NULL);
 383
 384         assert_se(REFCNT_INC(hwdb->n_ref) >= 2);
 385
 386         return hwdb;
 387 }
 388
 389 _public_ sd_hwdb *sd_hwdb_unref(sd_hwdb *hwdb) {
 390         if (hwdb && REFCNT_DEC(hwdb->n_ref) == 0) {
 391                 if (hwdb->map)
 392                         munmap((void *)hwdb->map, hwdb->st.st_size);
 393                 safe_fclose(hwdb->f);
 394                 ordered_hashmap_free(hwdb->properties);
 395                 free(hwdb);
 396         }
 397
 398         return NULL;
 399 }
 400
 401 bool hwdb_validate(sd_hwdb *hwdb) {
 402         bool found = false;
 403         const char* p;
 404         struct stat st;
 405
 406         if (!hwdb)
 407                 return false;
 408         if (!hwdb->f)
 409                 return false;
 410
 411         /* if hwdb.bin doesn't exist anywhere, we need to update */
 412         NULSTR_FOREACH(p, hwdb_bin_paths) {
 413                 if (stat(p, &st) >= 0) {
 414                         found = true;
 415                         break;
 416                 }
 417         }
 418         if (!found)
 419                 return true;
 420
 421         if (timespec_load(&hwdb->st.st_mtim) != timespec_load(&st.st_mtim))
 422                 return true;
 423         return false;
 424 }
 425
 426 static int properties_prepare(sd_hwdb *hwdb, const char *modalias) {
 427         assert(hwdb);
 428         assert(modalias);
 429
 430         ordered_hashmap_clear(hwdb->properties);
 431         hwdb->properties_modified = true;
 432
 433         return trie_search_f(hwdb, modalias);
 434 }
 435
 436 _public_ int sd_hwdb_get(sd_hwdb *hwdb, const char *modalias, const char *key, const char **_value) {
 437         const struct trie_value_entry_f *entry;
 438         int r;
 439
 440         assert_return(hwdb, -EINVAL);
 441         assert_return(hwdb->f, -EINVAL);
 442         assert_return(modalias, -EINVAL);
 443         assert_return(_value, -EINVAL);
 444
 445         r = properties_prepare(hwdb, modalias);
 446         if (r < 0)
 447                 return r;
 448
 449         entry = ordered_hashmap_get(hwdb->properties, key);
 450         if (!entry)
 451                 return -ENOENT;
 452
 453         *_value = trie_string(hwdb, entry->value_off);
 454
 455         return 0;
 456 }
 457
 458 _public_ int sd_hwdb_seek(sd_hwdb *hwdb, const char *modalias) {
 459         int r;
 460
 461         assert_return(hwdb, -EINVAL);
 462         assert_return(hwdb->f, -EINVAL);
 463         assert_return(modalias, -EINVAL);
 464
 465         r = properties_prepare(hwdb, modalias);
 466         if (r < 0)
 467                 return r;
 468
 469         hwdb->properties_modified = false;
 470         hwdb->properties_iterator = ITERATOR_FIRST;
 471
 472         return 0;
 473 }
 474
 475 _public_ int sd_hwdb_enumerate(sd_hwdb *hwdb, const char **key, const char **value) {
 476         const struct trie_value_entry_f *entry;
 477         const void *k;
 478
 479         assert_return(hwdb, -EINVAL);
 480         assert_return(key, -EINVAL);
 481         assert_return(value, -EINVAL);
 482
 483         if (hwdb->properties_modified)
 484                 return -EAGAIN;
 485
 486         ordered_hashmap_iterate(hwdb->properties, &hwdb->properties_iterator, (void **)&entry, &k);
 487         if (!k)
 488                 return 0;
 489
 490         *key = k;
 491         *value = trie_string(hwdb, entry->value_off);
 492
 493         return 1;
 494 }