lib/libkvm/kvm_private.c

   1 /*-
   2  * Copyright (c) 1989, 1992, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software developed by the Computer Systems
   6  * Engineering group at Lawrence Berkeley Laboratory under DARPA contract
   7  * BG 91-66 and contributed to Berkeley.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  * 3. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 #include <sys/param.h>
  35 #include <sys/fnv_hash.h>
  36
  37 #define _WANT_VNET
  38
  39 #include <sys/user.h>
  40 #include <sys/linker.h>
  41 #include <sys/pcpu.h>
  42 #include <sys/stat.h>
  43 #include <sys/mman.h>
  44
  45 #include <stdbool.h>
  46 #include <net/vnet.h>
  47
  48 #include <assert.h>
  49 #include <fcntl.h>
  50 #include <vm/vm.h>
  51 #include <kvm.h>
  52 #include <limits.h>
  53 #include <paths.h>
  54 #include <stdint.h>
  55 #include <stdio.h>
  56 #include <stdlib.h>
  57 #include <string.h>
  58 #include <unistd.h>
  59 #include <stdarg.h>
  60 #include <inttypes.h>
  61
  62 #include "kvm_private.h"
  63
  64 /*
  65  * Routines private to libkvm.
  66  */
  67
  68 /* from src/lib/libc/gen/nlist.c */
  69 int __fdnlist(int, struct nlist *);
  70
  71 /*
  72  * Report an error using printf style arguments.  "program" is kd->program
  73  * on hard errors, and 0 on soft errors, so that under sun error emulation,
  74  * only hard errors are printed out (otherwise, programs like gdb will
  75  * generate tons of error messages when trying to access bogus pointers).
  76  */
  77 void
  78 _kvm_err(kvm_t *kd, const char *program, const char *fmt, ...)
  79 {
  80         va_list ap;
  81
  82         va_start(ap, fmt);
  83         if (program != NULL) {
  84                 (void)fprintf(stderr, "%s: ", program);
  85                 (void)vfprintf(stderr, fmt, ap);
  86                 (void)fputc('\n', stderr);
  87         } else
  88                 (void)vsnprintf(kd->errbuf,
  89                     sizeof(kd->errbuf), fmt, ap);
  90
  91         va_end(ap);
  92 }
  93
  94 void
  95 _kvm_syserr(kvm_t *kd, const char *program, const char *fmt, ...)
  96 {
  97         va_list ap;
  98         int n;
  99
 100         va_start(ap, fmt);
 101         if (program != NULL) {
 102                 (void)fprintf(stderr, "%s: ", program);
 103                 (void)vfprintf(stderr, fmt, ap);
 104                 (void)fprintf(stderr, ": %s\n", strerror(errno));
 105         } else {
 106                 char *cp = kd->errbuf;
 107
 108                 (void)vsnprintf(cp, sizeof(kd->errbuf), fmt, ap);
 109                 n = strlen(cp);
 110                 (void)snprintf(&cp[n], sizeof(kd->errbuf) - n, ": %s",
 111                     strerror(errno));
 112         }
 113         va_end(ap);
 114 }
 115
 116 void *
 117 _kvm_malloc(kvm_t *kd, size_t n)
 118 {
 119         void *p;
 120
 121         if ((p = calloc(n, sizeof(char))) == NULL)
 122                 _kvm_err(kd, kd->program, "can't allocate %zu bytes: %s",
 123                          n, strerror(errno));
 124         return (p);
 125 }
 126
 127 int
 128 _kvm_probe_elf_kernel(kvm_t *kd, int class, int machine)
 129 {
 130
 131         return (kd->nlehdr.e_ident[EI_CLASS] == class &&
 132             ((machine == EM_PPC || machine == EM_PPC64) ?
 133              kd->nlehdr.e_type == ET_DYN : kd->nlehdr.e_type == ET_EXEC) &&
 134             kd->nlehdr.e_machine == machine);
 135 }
 136
 137 int
 138 _kvm_is_minidump(kvm_t *kd)
 139 {
 140         char minihdr[8];
 141
 142         if (kd->rawdump)
 143                 return (0);
 144         if (pread(kd->pmfd, &minihdr, 8, 0) == 8 &&
 145             memcmp(&minihdr, "minidump", 8) == 0)
 146                 return (1);
 147         return (0);
 148 }
 149
 150 /*
 151  * The powerpc backend has a hack to strip a leading kerneldump
 152  * header from the core before treating it as an ELF header.
 153  *
 154  * We can add that here if we can get a change to libelf to support
 155  * an initial offset into the file.  Alternatively we could patch
 156  * savecore to extract cores from a regular file instead.
 157  */
 158 int
 159 _kvm_read_core_phdrs(kvm_t *kd, size_t *phnump, GElf_Phdr **phdrp)
 160 {
 161         GElf_Ehdr ehdr;
 162         GElf_Phdr *phdr;
 163         Elf *elf;
 164         size_t i, phnum;
 165
 166         elf = elf_begin(kd->pmfd, ELF_C_READ, NULL);
 167         if (elf == NULL) {
 168                 _kvm_err(kd, kd->program, "%s", elf_errmsg(0));
 169                 return (-1);
 170         }
 171         if (elf_kind(elf) != ELF_K_ELF) {
 172                 _kvm_err(kd, kd->program, "invalid core");
 173                 goto bad;
 174         }
 175         if (gelf_getclass(elf) != kd->nlehdr.e_ident[EI_CLASS]) {
 176                 _kvm_err(kd, kd->program, "invalid core");
 177                 goto bad;
 178         }
 179         if (gelf_getehdr(elf, &ehdr) == NULL) {
 180                 _kvm_err(kd, kd->program, "%s", elf_errmsg(0));
 181                 goto bad;
 182         }
 183         if (ehdr.e_type != ET_CORE) {
 184                 _kvm_err(kd, kd->program, "invalid core");
 185                 goto bad;
 186         }
 187         if (ehdr.e_machine != kd->nlehdr.e_machine) {
 188                 _kvm_err(kd, kd->program, "invalid core");
 189                 goto bad;
 190         }
 191
 192         if (elf_getphdrnum(elf, &phnum) == -1) {
 193                 _kvm_err(kd, kd->program, "%s", elf_errmsg(0));
 194                 goto bad;
 195         }
 196
 197         phdr = calloc(phnum, sizeof(*phdr));
 198         if (phdr == NULL) {
 199                 _kvm_err(kd, kd->program, "failed to allocate phdrs");
 200                 goto bad;
 201         }
 202
 203         for (i = 0; i < phnum; i++) {
 204                 if (gelf_getphdr(elf, i, &phdr[i]) == NULL) {
 205                         free(phdr);
 206                         _kvm_err(kd, kd->program, "%s", elf_errmsg(0));
 207                         goto bad;
 208                 }
 209         }
 210         elf_end(elf);
 211         *phnump = phnum;
 212         *phdrp = phdr;
 213         return (0);
 214
 215 bad:
 216         elf_end(elf);
 217         return (-1);
 218 }
 219
 220 /*
 221  * Transform v such that only bits [bit0, bitN) may be set.  Generates a
 222  * bitmask covering the number of bits, then shifts so +bit0+ is the first.
 223  */
 224 static uint64_t
 225 bitmask_range(uint64_t v, uint64_t bit0, uint64_t bitN)
 226 {
 227         if (bit0 == 0 && bitN == BITS_IN(v))
 228                 return (v);
 229
 230         return (v & (((1ULL << (bitN - bit0)) - 1ULL) << bit0));
 231 }
 232
 233 /*
 234  * Returns the number of bits in a given byte array range starting at a
 235  * given base, from bit0 to bitN.  bit0 may be non-zero in the case of
 236  * counting backwards from bitN.
 237  */
 238 static uint64_t
 239 popcount_bytes(uint64_t *addr, uint32_t bit0, uint32_t bitN)
 240 {
 241         uint32_t res = bitN - bit0;
 242         uint64_t count = 0;
 243         uint32_t bound;
 244
 245         /* Align to 64-bit boundary on the left side if needed. */
 246         if ((bit0 % BITS_IN(*addr)) != 0) {
 247                 bound = MIN(bitN, roundup2(bit0, BITS_IN(*addr)));
 248                 count += __bitcount64(bitmask_range(*addr, bit0, bound));
 249                 res -= (bound - bit0);
 250                 addr++;
 251         }
 252
 253         while (res > 0) {
 254                 bound = MIN(res, BITS_IN(*addr));
 255                 count += __bitcount64(bitmask_range(*addr, 0, bound));
 256                 res -= bound;
 257                 addr++;
 258         }
 259
 260         return (count);
 261 }
 262
 263 void *
 264 _kvm_pmap_get(kvm_t *kd, u_long idx, size_t len)
 265 {
 266         uintptr_t off = idx * len;
 267
 268         if ((off_t)off >= kd->pt_sparse_off)
 269                 return (NULL);
 270         return (void *)((uintptr_t)kd->page_map + off);
 271 }
 272
 273 void *
 274 _kvm_map_get(kvm_t *kd, u_long pa, unsigned int page_size)
 275 {
 276         off_t off;
 277         uintptr_t addr;
 278
 279         off = _kvm_pt_find(kd, pa, page_size);
 280         if (off == -1)
 281                 return NULL;
 282
 283         addr = (uintptr_t)kd->page_map + off;
 284         if (off >= kd->pt_sparse_off)
 285                 addr = (uintptr_t)kd->sparse_map + (off - kd->pt_sparse_off);
 286         return (void *)addr;
 287 }
 288
 289 int
 290 _kvm_pt_init(kvm_t *kd, size_t dump_avail_size, off_t dump_avail_off,
 291     size_t map_len, off_t map_off, off_t sparse_off, int page_size)
 292 {
 293         uint64_t *addr;
 294         uint32_t *popcount_bin;
 295         int bin_popcounts = 0;
 296         uint64_t pc_bins, res;
 297         ssize_t rd;
 298
 299         kd->dump_avail_size = dump_avail_size;
 300         if (dump_avail_size > 0) {
 301                 kd->dump_avail = mmap(NULL, kd->dump_avail_size, PROT_READ,
 302                     MAP_PRIVATE, kd->pmfd, dump_avail_off);
 303         } else {
 304                 /*
 305                  * Older version minidumps don't provide dump_avail[],
 306                  * so the bitmap is fully populated from 0 to
 307                  * last_pa. Create an implied dump_avail that
 308                  * expresses this.
 309                  */
 310                 kd->dump_avail = calloc(4, sizeof(uint64_t));
 311                 kd->dump_avail[1] = _kvm64toh(kd, map_len * 8 * page_size);
 312         }
 313
 314         /*
 315          * Map the bitmap specified by the arguments.
 316          */
 317         kd->pt_map = _kvm_malloc(kd, map_len);
 318         if (kd->pt_map == NULL) {
 319                 _kvm_err(kd, kd->program, "cannot allocate %zu bytes for bitmap",
 320                     map_len);
 321                 return (-1);
 322         }
 323         rd = pread(kd->pmfd, kd->pt_map, map_len, map_off);
 324         if (rd < 0 || rd != (ssize_t)map_len) {
 325                 _kvm_err(kd, kd->program, "cannot read %zu bytes for bitmap",
 326                     map_len);
 327                 return (-1);
 328         }
 329         kd->pt_map_size = map_len;
 330
 331         /*
 332          * Generate a popcount cache for every POPCOUNT_BITS in the bitmap,
 333          * so lookups only have to calculate the number of bits set between
 334          * a cache point and their bit.  This reduces lookups to O(1),
 335          * without significantly increasing memory requirements.
 336          *
 337          * Round up the number of bins so that 'upper half' lookups work for
 338          * the final bin, if needed.  The first popcount is 0, since no bits
 339          * precede bit 0, so add 1 for that also.  Without this, extra work
 340          * would be needed to handle the first PTEs in _kvm_pt_find().
 341          */
 342         addr = kd->pt_map;
 343         res = map_len;
 344         pc_bins = 1 + (res * NBBY + POPCOUNT_BITS / 2) / POPCOUNT_BITS;
 345         kd->pt_popcounts = calloc(pc_bins, sizeof(uint32_t));
 346         if (kd->pt_popcounts == NULL) {
 347                 _kvm_err(kd, kd->program, "cannot allocate popcount bins");
 348                 return (-1);
 349         }
 350
 351         for (popcount_bin = &kd->pt_popcounts[1]; res > 0;
 352             addr++, res -= sizeof(*addr)) {
 353                 *popcount_bin += popcount_bytes(addr, 0,
 354                     MIN(res * NBBY, BITS_IN(*addr)));
 355                 if (++bin_popcounts == POPCOUNTS_IN(*addr)) {
 356                         popcount_bin++;
 357                         *popcount_bin = *(popcount_bin - 1);
 358                         bin_popcounts = 0;
 359                 }
 360         }
 361
 362         assert(pc_bins * sizeof(*popcount_bin) ==
 363             ((uintptr_t)popcount_bin - (uintptr_t)kd->pt_popcounts));
 364
 365         kd->pt_sparse_off = sparse_off;
 366         kd->pt_sparse_size = (uint64_t)*popcount_bin * page_size;
 367         kd->pt_page_size = page_size;
 368
 369         /*
 370          * Map the sparse page array.  This is useful for performing point
 371          * lookups of specific pages, e.g. for kvm_walk_pages.  Generally,
 372          * this is much larger than is reasonable to read in up front, so
 373          * mmap it in instead.
 374          */
 375         kd->sparse_map = mmap(NULL, kd->pt_sparse_size, PROT_READ,
 376             MAP_PRIVATE, kd->pmfd, kd->pt_sparse_off);
 377         if (kd->sparse_map == MAP_FAILED) {
 378                 _kvm_err(kd, kd->program, "cannot map %" PRIu64
 379                     " bytes from fd %d offset %jd for sparse map: %s",
 380                     kd->pt_sparse_size, kd->pmfd,
 381                     (intmax_t)kd->pt_sparse_off, strerror(errno));
 382                 return (-1);
 383         }
 384         return (0);
 385 }
 386
 387 int
 388 _kvm_pmap_init(kvm_t *kd, uint32_t pmap_size, off_t pmap_off)
 389 {
 390         ssize_t exp_len = pmap_size;
 391
 392         kd->page_map_size = pmap_size;
 393         kd->page_map_off = pmap_off;
 394         kd->page_map = _kvm_malloc(kd, pmap_size);
 395         if (kd->page_map == NULL) {
 396                 _kvm_err(kd, kd->program, "cannot allocate %u bytes "
 397                     "for page map", pmap_size);
 398                 return (-1);
 399         }
 400         if (pread(kd->pmfd, kd->page_map, pmap_size, pmap_off) != exp_len) {
 401                 _kvm_err(kd, kd->program, "cannot read %d bytes from "
 402                     "offset %jd for page map", pmap_size, (intmax_t)pmap_off);
 403                 return (-1);
 404         }
 405         return (0);
 406 }
 407
 408 static inline uint64_t
 409 dump_avail_n(kvm_t *kd, long i)
 410 {
 411         return (_kvm64toh(kd, kd->dump_avail[i]));
 412 }
 413
 414 uint64_t
 415 _kvm_pa_bit_id(kvm_t *kd, uint64_t pa, unsigned int page_size)
 416 {
 417         uint64_t adj;
 418         long i;
 419
 420         adj = 0;
 421         for (i = 0; dump_avail_n(kd, i + 1) != 0; i += 2) {
 422                 if (pa >= dump_avail_n(kd, i + 1)) {
 423                         adj += howmany(dump_avail_n(kd, i + 1), page_size) -
 424                             dump_avail_n(kd, i) / page_size;
 425                 } else {
 426                         return (pa / page_size -
 427                             dump_avail_n(kd, i) / page_size + adj);
 428                 }
 429         }
 430         return (_KVM_BIT_ID_INVALID);
 431 }
 432
 433 uint64_t
 434 _kvm_bit_id_pa(kvm_t *kd, uint64_t bit_id, unsigned int page_size)
 435 {
 436         uint64_t sz;
 437         long i;
 438
 439         for (i = 0; dump_avail_n(kd, i + 1) != 0; i += 2) {
 440                 sz = howmany(dump_avail_n(kd, i + 1), page_size) -
 441                     dump_avail_n(kd, i) / page_size;
 442                 if (bit_id < sz) {
 443                         return (rounddown2(dump_avail_n(kd, i), page_size) +
 444                             bit_id * page_size);
 445                 }
 446                 bit_id -= sz;
 447         }
 448         return (_KVM_PA_INVALID);
 449 }
 450
 451 /*
 452  * Find the offset for the given physical page address; returns -1 otherwise.
 453  *
 454  * A page's offset is represented by the sparse page base offset plus the
 455  * number of bits set before its bit multiplied by page size.  This means
 456  * that if a page exists in the dump, it's necessary to know how many pages
 457  * in the dump precede it.  Reduce this O(n) counting to O(1) by caching the
 458  * number of bits set at POPCOUNT_BITS intervals.
 459  *
 460  * Then to find the number of pages before the requested address, simply
 461  * index into the cache and count the number of bits set between that cache
 462  * bin and the page's bit.  Halve the number of bytes that have to be
 463  * checked by also counting down from the next higher bin if it's closer.
 464  */
 465 off_t
 466 _kvm_pt_find(kvm_t *kd, uint64_t pa, unsigned int page_size)
 467 {
 468         uint64_t *bitmap = kd->pt_map;
 469         uint64_t pte_bit_id = _kvm_pa_bit_id(kd, pa, page_size);
 470         uint64_t pte_u64 = pte_bit_id / BITS_IN(*bitmap);
 471         uint64_t popcount_id = pte_bit_id / POPCOUNT_BITS;
 472         uint64_t pte_mask = 1ULL << (pte_bit_id % BITS_IN(*bitmap));
 473         uint64_t bitN;
 474         uint32_t count;
 475
 476         /* Check whether the page address requested is in the dump. */
 477         if (pte_bit_id == _KVM_BIT_ID_INVALID ||
 478             pte_bit_id >= (kd->pt_map_size * NBBY) ||
 479             (bitmap[pte_u64] & pte_mask) == 0)
 480                 return (-1);
 481
 482         /*
 483          * Add/sub popcounts from the bitmap until the PTE's bit is reached.
 484          * For bits that are in the upper half between the calculated
 485          * popcount id and the next one, use the next one and subtract to
 486          * minimize the number of popcounts required.
 487          */
 488         if ((pte_bit_id % POPCOUNT_BITS) < (POPCOUNT_BITS / 2)) {
 489                 count = kd->pt_popcounts[popcount_id] + popcount_bytes(
 490                     bitmap + popcount_id * POPCOUNTS_IN(*bitmap),
 491                     0, pte_bit_id - popcount_id * POPCOUNT_BITS);
 492         } else {
 493                 /*
 494                  * Counting in reverse is trickier, since we must avoid
 495                  * reading from bytes that are not in range, and invert.
 496                  */
 497                 uint64_t pte_u64_bit_off = pte_u64 * BITS_IN(*bitmap);
 498
 499                 popcount_id++;
 500                 bitN = MIN(popcount_id * POPCOUNT_BITS,
 501                     kd->pt_map_size * BITS_IN(uint8_t));
 502                 count = kd->pt_popcounts[popcount_id] - popcount_bytes(
 503                     bitmap + pte_u64,
 504                     pte_bit_id - pte_u64_bit_off, bitN - pte_u64_bit_off);
 505         }
 506
 507         /*
 508          * This can only happen if the core is truncated.  Treat these
 509          * entries as if they don't exist, since their backing doesn't.
 510          */
 511         if (count >= (kd->pt_sparse_size / page_size))
 512                 return (-1);
 513
 514         return (kd->pt_sparse_off + (uint64_t)count * page_size);
 515 }
 516
 517 static int
 518 kvm_fdnlist(kvm_t *kd, struct kvm_nlist *list)
 519 {
 520         kvaddr_t addr;
 521         int error, nfail;
 522
 523         if (kd->resolve_symbol == NULL) {
 524                 struct nlist *nl;
 525                 int count, i;
 526
 527                 for (count = 0; list[count].n_name != NULL &&
 528                      list[count].n_name[0] != '\0'; count++)
 529                         ;
 530                 nl = calloc(count + 1, sizeof(*nl));
 531                 for (i = 0; i < count; i++)
 532                         nl[i].n_name = list[i].n_name;
 533                 nfail = __fdnlist(kd->nlfd, nl);
 534                 for (i = 0; i < count; i++) {
 535                         list[i].n_type = nl[i].n_type;
 536                         list[i].n_value = nl[i].n_value;
 537                 }
 538                 free(nl);
 539                 return (nfail);
 540         }
 541
 542         nfail = 0;
 543         while (list->n_name != NULL && list->n_name[0] != '\0') {
 544                 error = kd->resolve_symbol(list->n_name, &addr);
 545                 if (error != 0) {
 546                         nfail++;
 547                         list->n_value = 0;
 548                         list->n_type = 0;
 549                 } else {
 550                         list->n_value = addr;
 551                         list->n_type = N_DATA | N_EXT;
 552                 }
 553                 list++;
 554         }
 555         return (nfail);
 556 }
 557
 558 /*
 559  * Walk the list of unresolved symbols, generate a new list and prefix the
 560  * symbol names, try again, and merge back what we could resolve.
 561  */
 562 static int
 563 kvm_fdnlist_prefix(kvm_t *kd, struct kvm_nlist *nl, int missing,
 564     const char *prefix, kvaddr_t (*validate_fn)(kvm_t *, kvaddr_t))
 565 {
 566         struct kvm_nlist *n, *np, *p;
 567         char *cp, *ce;
 568         const char *ccp;
 569         size_t len;
 570         int slen, unresolved;
 571
 572         /*
 573          * Calculate the space we need to malloc for nlist and names.
 574          * We are going to store the name twice for later lookups: once
 575          * with the prefix and once the unmodified name delmited by \0.
 576          */
 577         len = 0;
 578         unresolved = 0;
 579         for (p = nl; p->n_name && p->n_name[0]; ++p) {
 580                 if (p->n_type != N_UNDF)
 581                         continue;
 582                 len += sizeof(struct kvm_nlist) + strlen(prefix) +
 583                     2 * (strlen(p->n_name) + 1);
 584                 unresolved++;
 585         }
 586         if (unresolved == 0)
 587                 return (unresolved);
 588         /* Add space for the terminating nlist entry. */
 589         len += sizeof(struct kvm_nlist);
 590         unresolved++;
 591
 592         /* Alloc one chunk for (nlist, [names]) and setup pointers. */
 593         n = np = malloc(len);
 594         bzero(n, len);
 595         if (n == NULL)
 596                 return (missing);
 597         cp = ce = (char *)np;
 598         cp += unresolved * sizeof(struct kvm_nlist);
 599         ce += len;
 600
 601         /* Generate shortened nlist with special prefix. */
 602         unresolved = 0;
 603         for (p = nl; p->n_name && p->n_name[0]; ++p) {
 604                 if (p->n_type != N_UNDF)
 605                         continue;
 606                 *np = *p;
 607                 /* Save the new\0orig. name so we can later match it again. */
 608                 slen = snprintf(cp, ce - cp, "%s%s%c%s", prefix,
 609                     (prefix[0] != '\0' && p->n_name[0] == '_') ?
 610                         (p->n_name + 1) : p->n_name, '\0', p->n_name);
 611                 if (slen < 0 || slen >= ce - cp)
 612                         continue;
 613                 np->n_name = cp;
 614                 cp += slen + 1;
 615                 np++;
 616                 unresolved++;
 617         }
 618
 619         /* Do lookup on the reduced list. */
 620         np = n;
 621         unresolved = kvm_fdnlist(kd, np);
 622
 623         /* Check if we could resolve further symbols and update the list. */
 624         if (unresolved >= 0 && unresolved < missing) {
 625                 /* Find the first freshly resolved entry. */
 626                 for (; np->n_name && np->n_name[0]; np++)
 627                         if (np->n_type != N_UNDF)
 628                                 break;
 629                 /*
 630                  * The lists are both in the same order,
 631                  * so we can walk them in parallel.
 632                  */
 633                 for (p = nl; np->n_name && np->n_name[0] &&
 634                     p->n_name && p->n_name[0]; ++p) {
 635                         if (p->n_type != N_UNDF)
 636                                 continue;
 637                         /* Skip expanded name and compare to orig. one. */
 638                         ccp = np->n_name + strlen(np->n_name) + 1;
 639                         if (strcmp(ccp, p->n_name) != 0)
 640                                 continue;
 641                         /* Update nlist with new, translated results. */
 642                         p->n_type = np->n_type;
 643                         if (validate_fn)
 644                                 p->n_value = (*validate_fn)(kd, np->n_value);
 645                         else
 646                                 p->n_value = np->n_value;
 647                         missing--;
 648                         /* Find next freshly resolved entry. */
 649                         for (np++; np->n_name && np->n_name[0]; np++)
 650                                 if (np->n_type != N_UNDF)
 651                                         break;
 652                 }
 653         }
 654         /* We could assert missing = unresolved here. */
 655
 656         free(n);
 657         return (unresolved);
 658 }
 659
 660 int
 661 _kvm_nlist(kvm_t *kd, struct kvm_nlist *nl, int initialize)
 662 {
 663         struct kvm_nlist *p;
 664         int nvalid;
 665         struct kld_sym_lookup lookup;
 666         int error;
 667         const char *prefix = "";
 668         char symname[1024]; /* XXX-BZ symbol name length limit? */
 669         int tried_vnet, tried_dpcpu;
 670
 671         /*
 672          * If we can't use the kld symbol lookup, revert to the
 673          * slow library call.
 674          */
 675         if (!ISALIVE(kd)) {
 676                 error = kvm_fdnlist(kd, nl);
 677                 if (error <= 0)                 /* Hard error or success. */
 678                         return (error);
 679
 680                 if (_kvm_vnet_initialized(kd, initialize))
 681                         error = kvm_fdnlist_prefix(kd, nl, error,
 682                             VNET_SYMPREFIX, _kvm_vnet_validaddr);
 683
 684                 if (error > 0 && _kvm_dpcpu_initialized(kd, initialize))
 685                         error = kvm_fdnlist_prefix(kd, nl, error,
 686                             DPCPU_SYMPREFIX, _kvm_dpcpu_validaddr);
 687
 688                 return (error);
 689         }
 690
 691         /*
 692          * We can use the kld lookup syscall.  Go through each nlist entry
 693          * and look it up with a kldsym(2) syscall.
 694          */
 695         nvalid = 0;
 696         tried_vnet = 0;
 697         tried_dpcpu = 0;
 698 again:
 699         for (p = nl; p->n_name && p->n_name[0]; ++p) {
 700                 if (p->n_type != N_UNDF)
 701                         continue;
 702
 703                 lookup.version = sizeof(lookup);
 704                 lookup.symvalue = 0;
 705                 lookup.symsize = 0;
 706
 707                 error = snprintf(symname, sizeof(symname), "%s%s", prefix,
 708                     (prefix[0] != '\0' && p->n_name[0] == '_') ?
 709                         (p->n_name + 1) : p->n_name);
 710                 if (error < 0 || error >= (int)sizeof(symname))
 711                         continue;
 712                 lookup.symname = symname;
 713                 if (lookup.symname[0] == '_')
 714                         lookup.symname++;
 715
 716                 if (kldsym(0, KLDSYM_LOOKUP, &lookup) != -1) {
 717                         p->n_type = N_TEXT;
 718                         if (_kvm_vnet_initialized(kd, initialize) &&
 719                             strcmp(prefix, VNET_SYMPREFIX) == 0)
 720                                 p->n_value =
 721                                     _kvm_vnet_validaddr(kd, lookup.symvalue);
 722                         else if (_kvm_dpcpu_initialized(kd, initialize) &&
 723                             strcmp(prefix, DPCPU_SYMPREFIX) == 0)
 724                                 p->n_value =
 725                                     _kvm_dpcpu_validaddr(kd, lookup.symvalue);
 726                         else
 727                                 p->n_value = lookup.symvalue;
 728                         ++nvalid;
 729                         /* lookup.symsize */
 730                 }
 731         }
 732
 733         /*
 734          * Check the number of entries that weren't found. If they exist,
 735          * try again with a prefix for virtualized or DPCPU symbol names.
 736          */
 737         error = ((p - nl) - nvalid);
 738         if (error && _kvm_vnet_initialized(kd, initialize) && !tried_vnet) {
 739                 tried_vnet = 1;
 740                 prefix = VNET_SYMPREFIX;
 741                 goto again;
 742         }
 743         if (error && _kvm_dpcpu_initialized(kd, initialize) && !tried_dpcpu) {
 744                 tried_dpcpu = 1;
 745                 prefix = DPCPU_SYMPREFIX;
 746                 goto again;
 747         }
 748
 749         /*
 750          * Return the number of entries that weren't found. If they exist,
 751          * also fill internal error buffer.
 752          */
 753         error = ((p - nl) - nvalid);
 754         if (error)
 755                 _kvm_syserr(kd, kd->program, "kvm_nlist");
 756         return (error);
 757 }
 758
 759 int
 760 _kvm_bitmap_init(struct kvm_bitmap *bm, u_long bitmapsize, u_long *idx)
 761 {
 762
 763         *idx = ULONG_MAX;
 764         bm->map = calloc(bitmapsize, sizeof *bm->map);
 765         if (bm->map == NULL)
 766                 return (0);
 767         bm->size = bitmapsize;
 768         return (1);
 769 }
 770
 771 void
 772 _kvm_bitmap_set(struct kvm_bitmap *bm, u_long bm_index)
 773 {
 774         uint8_t *byte = &bm->map[bm_index / 8];
 775
 776         if (bm_index / 8 < bm->size)
 777                 *byte |= (1UL << (bm_index % 8));
 778 }
 779
 780 int
 781 _kvm_bitmap_next(struct kvm_bitmap *bm, u_long *idx)
 782 {
 783         u_long first_invalid = bm->size * CHAR_BIT;
 784
 785         if (*idx == ULONG_MAX)
 786                 *idx = 0;
 787         else
 788                 (*idx)++;
 789
 790         /* Find the next valid idx. */
 791         for (; *idx < first_invalid; (*idx)++) {
 792                 unsigned int mask = 1U << (*idx % CHAR_BIT);
 793                 if ((bm->map[*idx / CHAR_BIT] & mask) != 0)
 794                         break;
 795         }
 796
 797         return (*idx < first_invalid);
 798 }
 799
 800 void
 801 _kvm_bitmap_deinit(struct kvm_bitmap *bm)
 802 {
 803
 804         free(bm->map);
 805 }
 806
 807 int
 808 _kvm_visit_cb(kvm_t *kd, kvm_walk_pages_cb_t *cb, void *arg, u_long pa,
 809     u_long kmap_vaddr, u_long dmap_vaddr, vm_prot_t prot, size_t len,
 810     unsigned int page_size)
 811 {
 812         unsigned int pgsz = page_size ? page_size : len;
 813         struct kvm_page p = {
 814                 .kp_version = LIBKVM_WALK_PAGES_VERSION,
 815                 .kp_paddr = pa,
 816                 .kp_kmap_vaddr = kmap_vaddr,
 817                 .kp_dmap_vaddr = dmap_vaddr,
 818                 .kp_prot = prot,
 819                 .kp_offset = _kvm_pt_find(kd, pa, pgsz),
 820                 .kp_len = len,
 821         };
 822
 823         return cb(&p, arg);
 824 }