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