2 * Copyright (c) 1989, 1992, 1993
3 * The Regents of the University of California. All rights reserved.
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.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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
34 #include <sys/cdefs.h>
35 __FBSDID("$FreeBSD$");
37 #include <sys/param.h>
38 #include <sys/fnv_hash.h>
43 #include <sys/linker.h>
64 #include "kvm_private.h"
67 * Routines private to libkvm.
70 /* from src/lib/libc/gen/nlist.c */
71 int __fdnlist(int, struct nlist *);
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).
80 _kvm_err(kvm_t *kd, const char *program, const char *fmt, ...)
85 if (program != NULL) {
86 (void)fprintf(stderr, "%s: ", program);
87 (void)vfprintf(stderr, fmt, ap);
88 (void)fputc('\n', stderr);
90 (void)vsnprintf(kd->errbuf,
91 sizeof(kd->errbuf), fmt, ap);
97 _kvm_syserr(kvm_t *kd, const char *program, const char *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));
108 char *cp = kd->errbuf;
110 (void)vsnprintf(cp, sizeof(kd->errbuf), fmt, ap);
112 (void)snprintf(&cp[n], sizeof(kd->errbuf) - n, ": %s",
119 _kvm_malloc(kvm_t *kd, size_t n)
123 if ((p = calloc(n, sizeof(char))) == NULL)
124 _kvm_err(kd, kd->program, "can't allocate %zu bytes: %s",
130 _kvm_probe_elf_kernel(kvm_t *kd, int class, int machine)
133 return (kd->nlehdr.e_ident[EI_CLASS] == class &&
134 kd->nlehdr.e_type == ET_EXEC &&
135 kd->nlehdr.e_machine == machine);
139 _kvm_is_minidump(kvm_t *kd)
145 if (pread(kd->pmfd, &minihdr, 8, 0) == 8 &&
146 memcmp(&minihdr, "minidump", 8) == 0)
152 * The powerpc backend has a hack to strip a leading kerneldump
153 * header from the core before treating it as an ELF header.
155 * We can add that here if we can get a change to libelf to support
156 * an initial offset into the file. Alternatively we could patch
157 * savecore to extract cores from a regular file instead.
160 _kvm_read_core_phdrs(kvm_t *kd, size_t *phnump, GElf_Phdr **phdrp)
167 elf = elf_begin(kd->pmfd, ELF_C_READ, NULL);
169 _kvm_err(kd, kd->program, "%s", elf_errmsg(0));
172 if (elf_kind(elf) != ELF_K_ELF) {
173 _kvm_err(kd, kd->program, "invalid core");
176 if (gelf_getclass(elf) != kd->nlehdr.e_ident[EI_CLASS]) {
177 _kvm_err(kd, kd->program, "invalid core");
180 if (gelf_getehdr(elf, &ehdr) == NULL) {
181 _kvm_err(kd, kd->program, "%s", elf_errmsg(0));
184 if (ehdr.e_type != ET_CORE) {
185 _kvm_err(kd, kd->program, "invalid core");
188 if (ehdr.e_machine != kd->nlehdr.e_machine) {
189 _kvm_err(kd, kd->program, "invalid core");
193 if (elf_getphdrnum(elf, &phnum) == -1) {
194 _kvm_err(kd, kd->program, "%s", elf_errmsg(0));
198 phdr = calloc(phnum, sizeof(*phdr));
200 _kvm_err(kd, kd->program, "failed to allocate phdrs");
204 for (i = 0; i < phnum; i++) {
205 if (gelf_getphdr(elf, i, &phdr[i]) == NULL) {
207 _kvm_err(kd, kd->program, "%s", elf_errmsg(0));
222 * Transform v such that only bits [bit0, bitN) may be set. Generates a
223 * bitmask covering the number of bits, then shifts so +bit0+ is the first.
226 bitmask_range(uint64_t v, uint64_t bit0, uint64_t bitN)
228 if (bit0 == 0 && bitN == BITS_IN(v))
231 return (v & (((1ULL << (bitN - bit0)) - 1ULL) << bit0));
235 * Returns the number of bits in a given byte array range starting at a
236 * given base, from bit0 to bitN. bit0 may be non-zero in the case of
237 * counting backwards from bitN.
240 popcount_bytes(uint64_t *addr, uint32_t bit0, uint32_t bitN)
242 uint32_t res = bitN - bit0;
246 /* Align to 64-bit boundary on the left side if needed. */
247 if ((bit0 % BITS_IN(*addr)) != 0) {
248 bound = MIN(bitN, roundup2(bit0, BITS_IN(*addr)));
249 count += __bitcount64(bitmask_range(*addr, bit0, bound));
250 res -= (bound - bit0);
255 bound = MIN(res, BITS_IN(*addr));
256 count += __bitcount64(bitmask_range(*addr, 0, bound));
265 _kvm_pmap_get(kvm_t *kd, u_long idx, size_t len)
267 uintptr_t off = idx * len;
269 if ((off_t)off >= kd->pt_sparse_off)
271 return (void *)((uintptr_t)kd->page_map + off);
275 _kvm_map_get(kvm_t *kd, u_long pa, unsigned int page_size)
280 off = _kvm_pt_find(kd, pa, page_size);
284 addr = (uintptr_t)kd->page_map + off;
285 if (off >= kd->pt_sparse_off)
286 addr = (uintptr_t)kd->sparse_map + (off - kd->pt_sparse_off);
291 _kvm_pt_init(kvm_t *kd, size_t map_len, off_t map_off, off_t sparse_off,
292 int page_size, int word_size)
295 uint32_t *popcount_bin;
296 int bin_popcounts = 0;
297 uint64_t pc_bins, res;
301 * Map the bitmap specified by the arguments.
303 kd->pt_map = _kvm_malloc(kd, map_len);
304 if (kd->pt_map == NULL) {
305 _kvm_err(kd, kd->program, "cannot allocate %zu bytes for bitmap",
309 rd = pread(kd->pmfd, kd->pt_map, map_len, map_off);
310 if (rd < 0 || rd != (ssize_t)map_len) {
311 _kvm_err(kd, kd->program, "cannot read %zu bytes for bitmap",
315 kd->pt_map_size = map_len;
318 * Generate a popcount cache for every POPCOUNT_BITS in the bitmap,
319 * so lookups only have to calculate the number of bits set between
320 * a cache point and their bit. This reduces lookups to O(1),
321 * without significantly increasing memory requirements.
323 * Round up the number of bins so that 'upper half' lookups work for
324 * the final bin, if needed. The first popcount is 0, since no bits
325 * precede bit 0, so add 1 for that also. Without this, extra work
326 * would be needed to handle the first PTEs in _kvm_pt_find().
330 pc_bins = 1 + (res * NBBY + POPCOUNT_BITS / 2) / POPCOUNT_BITS;
331 kd->pt_popcounts = calloc(pc_bins, sizeof(uint32_t));
332 if (kd->pt_popcounts == NULL) {
333 _kvm_err(kd, kd->program, "cannot allocate popcount bins");
337 for (popcount_bin = &kd->pt_popcounts[1]; res > 0;
338 addr++, res -= sizeof(*addr)) {
339 *popcount_bin += popcount_bytes(addr, 0,
340 MIN(res * NBBY, BITS_IN(*addr)));
341 if (++bin_popcounts == POPCOUNTS_IN(*addr)) {
343 *popcount_bin = *(popcount_bin - 1);
348 assert(pc_bins * sizeof(*popcount_bin) ==
349 ((uintptr_t)popcount_bin - (uintptr_t)kd->pt_popcounts));
351 kd->pt_sparse_off = sparse_off;
352 kd->pt_sparse_size = (uint64_t)*popcount_bin * page_size;
353 kd->pt_page_size = page_size;
354 kd->pt_word_size = word_size;
357 * Map the sparse page array. This is useful for performing point
358 * lookups of specific pages, e.g. for kvm_walk_pages. Generally,
359 * this is much larger than is reasonable to read in up front, so
360 * mmap it in instead.
362 kd->sparse_map = mmap(NULL, kd->pt_sparse_size, PROT_READ,
363 MAP_PRIVATE, kd->pmfd, kd->pt_sparse_off);
364 if (kd->sparse_map == MAP_FAILED) {
365 _kvm_err(kd, kd->program, "cannot map %" PRIu64
366 " bytes from fd %d offset %jd for sparse map: %s",
367 kd->pt_sparse_size, kd->pmfd,
368 (intmax_t)kd->pt_sparse_off, strerror(errno));
375 _kvm_pmap_init(kvm_t *kd, uint32_t pmap_size, off_t pmap_off)
377 ssize_t exp_len = pmap_size;
379 kd->page_map_size = pmap_size;
380 kd->page_map_off = pmap_off;
381 kd->page_map = _kvm_malloc(kd, pmap_size);
382 if (kd->page_map == NULL) {
383 _kvm_err(kd, kd->program, "cannot allocate %u bytes "
384 "for page map", pmap_size);
387 if (pread(kd->pmfd, kd->page_map, pmap_size, pmap_off) != exp_len) {
388 _kvm_err(kd, kd->program, "cannot read %d bytes from "
389 "offset %jd for page map", pmap_size, (intmax_t)pmap_off);
396 * Find the offset for the given physical page address; returns -1 otherwise.
398 * A page's offset is represented by the sparse page base offset plus the
399 * number of bits set before its bit multiplied by page size. This means
400 * that if a page exists in the dump, it's necessary to know how many pages
401 * in the dump precede it. Reduce this O(n) counting to O(1) by caching the
402 * number of bits set at POPCOUNT_BITS intervals.
404 * Then to find the number of pages before the requested address, simply
405 * index into the cache and count the number of bits set between that cache
406 * bin and the page's bit. Halve the number of bytes that have to be
407 * checked by also counting down from the next higher bin if it's closer.
410 _kvm_pt_find(kvm_t *kd, uint64_t pa, unsigned int page_size)
412 uint64_t *bitmap = kd->pt_map;
413 uint64_t pte_bit_id = pa / page_size;
414 uint64_t pte_u64 = pte_bit_id / BITS_IN(*bitmap);
415 uint64_t popcount_id = pte_bit_id / POPCOUNT_BITS;
416 uint64_t pte_mask = 1ULL << (pte_bit_id % BITS_IN(*bitmap));
420 /* Check whether the page address requested is in the dump. */
421 if (pte_bit_id >= (kd->pt_map_size * NBBY) ||
422 (bitmap[pte_u64] & pte_mask) == 0)
426 * Add/sub popcounts from the bitmap until the PTE's bit is reached.
427 * For bits that are in the upper half between the calculated
428 * popcount id and the next one, use the next one and subtract to
429 * minimize the number of popcounts required.
431 if ((pte_bit_id % POPCOUNT_BITS) < (POPCOUNT_BITS / 2)) {
432 count = kd->pt_popcounts[popcount_id] + popcount_bytes(
433 bitmap + popcount_id * POPCOUNTS_IN(*bitmap),
434 0, pte_bit_id - popcount_id * POPCOUNT_BITS);
437 * Counting in reverse is trickier, since we must avoid
438 * reading from bytes that are not in range, and invert.
440 uint64_t pte_u64_bit_off = pte_u64 * BITS_IN(*bitmap);
443 bitN = MIN(popcount_id * POPCOUNT_BITS,
444 kd->pt_map_size * BITS_IN(uint8_t));
445 count = kd->pt_popcounts[popcount_id] - popcount_bytes(
447 pte_bit_id - pte_u64_bit_off, bitN - pte_u64_bit_off);
451 * This can only happen if the core is truncated. Treat these
452 * entries as if they don't exist, since their backing doesn't.
454 if (count >= (kd->pt_sparse_size / page_size))
457 return (kd->pt_sparse_off + (uint64_t)count * page_size);
461 kvm_fdnlist(kvm_t *kd, struct kvm_nlist *list)
466 if (kd->resolve_symbol == NULL) {
470 for (count = 0; list[count].n_name != NULL &&
471 list[count].n_name[0] != '\0'; count++)
473 nl = calloc(count + 1, sizeof(*nl));
474 for (i = 0; i < count; i++)
475 nl[i].n_name = list[i].n_name;
476 nfail = __fdnlist(kd->nlfd, nl);
477 for (i = 0; i < count; i++) {
478 list[i].n_type = nl[i].n_type;
479 list[i].n_value = nl[i].n_value;
486 while (list->n_name != NULL && list->n_name[0] != '\0') {
487 error = kd->resolve_symbol(list->n_name, &addr);
493 list->n_value = addr;
494 list->n_type = N_DATA | N_EXT;
502 * Walk the list of unresolved symbols, generate a new list and prefix the
503 * symbol names, try again, and merge back what we could resolve.
506 kvm_fdnlist_prefix(kvm_t *kd, struct kvm_nlist *nl, int missing,
507 const char *prefix, kvaddr_t (*validate_fn)(kvm_t *, kvaddr_t))
509 struct kvm_nlist *n, *np, *p;
513 int slen, unresolved;
516 * Calculate the space we need to malloc for nlist and names.
517 * We are going to store the name twice for later lookups: once
518 * with the prefix and once the unmodified name delmited by \0.
522 for (p = nl; p->n_name && p->n_name[0]; ++p) {
523 if (p->n_type != N_UNDF)
525 len += sizeof(struct kvm_nlist) + strlen(prefix) +
526 2 * (strlen(p->n_name) + 1);
531 /* Add space for the terminating nlist entry. */
532 len += sizeof(struct kvm_nlist);
535 /* Alloc one chunk for (nlist, [names]) and setup pointers. */
536 n = np = malloc(len);
540 cp = ce = (char *)np;
541 cp += unresolved * sizeof(struct kvm_nlist);
544 /* Generate shortened nlist with special prefix. */
546 for (p = nl; p->n_name && p->n_name[0]; ++p) {
547 if (p->n_type != N_UNDF)
550 /* Save the new\0orig. name so we can later match it again. */
551 slen = snprintf(cp, ce - cp, "%s%s%c%s", prefix,
552 (prefix[0] != '\0' && p->n_name[0] == '_') ?
553 (p->n_name + 1) : p->n_name, '\0', p->n_name);
554 if (slen < 0 || slen >= ce - cp)
562 /* Do lookup on the reduced list. */
564 unresolved = kvm_fdnlist(kd, np);
566 /* Check if we could resolve further symbols and update the list. */
567 if (unresolved >= 0 && unresolved < missing) {
568 /* Find the first freshly resolved entry. */
569 for (; np->n_name && np->n_name[0]; np++)
570 if (np->n_type != N_UNDF)
573 * The lists are both in the same order,
574 * so we can walk them in parallel.
576 for (p = nl; np->n_name && np->n_name[0] &&
577 p->n_name && p->n_name[0]; ++p) {
578 if (p->n_type != N_UNDF)
580 /* Skip expanded name and compare to orig. one. */
581 ccp = np->n_name + strlen(np->n_name) + 1;
582 if (strcmp(ccp, p->n_name) != 0)
584 /* Update nlist with new, translated results. */
585 p->n_type = np->n_type;
587 p->n_value = (*validate_fn)(kd, np->n_value);
589 p->n_value = np->n_value;
591 /* Find next freshly resolved entry. */
592 for (np++; np->n_name && np->n_name[0]; np++)
593 if (np->n_type != N_UNDF)
597 /* We could assert missing = unresolved here. */
604 _kvm_nlist(kvm_t *kd, struct kvm_nlist *nl, int initialize)
608 struct kld_sym_lookup lookup;
610 const char *prefix = "";
611 char symname[1024]; /* XXX-BZ symbol name length limit? */
612 int tried_vnet, tried_dpcpu;
615 * If we can't use the kld symbol lookup, revert to the
619 error = kvm_fdnlist(kd, nl);
620 if (error <= 0) /* Hard error or success. */
623 if (_kvm_vnet_initialized(kd, initialize))
624 error = kvm_fdnlist_prefix(kd, nl, error,
625 VNET_SYMPREFIX, _kvm_vnet_validaddr);
627 if (error > 0 && _kvm_dpcpu_initialized(kd, initialize))
628 error = kvm_fdnlist_prefix(kd, nl, error,
629 DPCPU_SYMPREFIX, _kvm_dpcpu_validaddr);
635 * We can use the kld lookup syscall. Go through each nlist entry
636 * and look it up with a kldsym(2) syscall.
642 for (p = nl; p->n_name && p->n_name[0]; ++p) {
643 if (p->n_type != N_UNDF)
646 lookup.version = sizeof(lookup);
650 error = snprintf(symname, sizeof(symname), "%s%s", prefix,
651 (prefix[0] != '\0' && p->n_name[0] == '_') ?
652 (p->n_name + 1) : p->n_name);
653 if (error < 0 || error >= (int)sizeof(symname))
655 lookup.symname = symname;
656 if (lookup.symname[0] == '_')
659 if (kldsym(0, KLDSYM_LOOKUP, &lookup) != -1) {
661 if (_kvm_vnet_initialized(kd, initialize) &&
662 strcmp(prefix, VNET_SYMPREFIX) == 0)
664 _kvm_vnet_validaddr(kd, lookup.symvalue);
665 else if (_kvm_dpcpu_initialized(kd, initialize) &&
666 strcmp(prefix, DPCPU_SYMPREFIX) == 0)
668 _kvm_dpcpu_validaddr(kd, lookup.symvalue);
670 p->n_value = lookup.symvalue;
677 * Check the number of entries that weren't found. If they exist,
678 * try again with a prefix for virtualized or DPCPU symbol names.
680 error = ((p - nl) - nvalid);
681 if (error && _kvm_vnet_initialized(kd, initialize) && !tried_vnet) {
683 prefix = VNET_SYMPREFIX;
686 if (error && _kvm_dpcpu_initialized(kd, initialize) && !tried_dpcpu) {
688 prefix = DPCPU_SYMPREFIX;
693 * Return the number of entries that weren't found. If they exist,
694 * also fill internal error buffer.
696 error = ((p - nl) - nvalid);
698 _kvm_syserr(kd, kd->program, "kvm_nlist");
703 _kvm_bitmap_init(struct kvm_bitmap *bm, u_long bitmapsize, u_long *idx)
707 bm->map = calloc(bitmapsize, sizeof *bm->map);
710 bm->size = bitmapsize;
715 _kvm_bitmap_set(struct kvm_bitmap *bm, u_long pa, unsigned int page_size)
717 u_long bm_index = pa / page_size;
718 uint8_t *byte = &bm->map[bm_index / 8];
720 *byte |= (1UL << (bm_index % 8));
724 _kvm_bitmap_next(struct kvm_bitmap *bm, u_long *idx)
726 u_long first_invalid = bm->size * CHAR_BIT;
728 if (*idx == ULONG_MAX)
733 /* Find the next valid idx. */
734 for (; *idx < first_invalid; (*idx)++) {
735 unsigned int mask = *idx % CHAR_BIT;
736 if ((bm->map[*idx * CHAR_BIT] & mask) == 0)
740 return (*idx < first_invalid);
744 _kvm_bitmap_deinit(struct kvm_bitmap *bm)
751 _kvm_visit_cb(kvm_t *kd, kvm_walk_pages_cb_t *cb, void *arg, u_long pa,
752 u_long kmap_vaddr, u_long dmap_vaddr, vm_prot_t prot, size_t len,
753 unsigned int page_size)
755 unsigned int pgsz = page_size ? page_size : len;
756 struct kvm_page p = {
757 .version = LIBKVM_WALK_PAGES_VERSION,
759 .kmap_vaddr = kmap_vaddr,
760 .dmap_vaddr = dmap_vaddr,
762 .offset = _kvm_pt_find(kd, pa, pgsz),