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