8 files changed, 235 insertions, 213 deletions

diff --git a/lib/libkvm/kvm.c b/lib/libkvm/kvm.c
index 504c7ba9b5d6..26fdbe750c84 100644
--- a/lib/libkvm/kvm.c
+++ b/lib/libkvm/kvm.c
@@ -283,6 +283,8 @@ kvm_close(kvm_t *kd)
 		free((void *) kd->argspc);
 	if (kd->argv != 0)
 		free((void *)kd->argv);
+	if (kd->pt_map != NULL)
+		free(kd->pt_map);
 	free((void *)kd);
 
 	return (0);
diff --git a/lib/libkvm/kvm_minidump_aarch64.c b/lib/libkvm/kvm_minidump_aarch64.c
index d5c5197307fe..ffe27bdd527d 100644
--- a/lib/libkvm/kvm_minidump_aarch64.c
+++ b/lib/libkvm/kvm_minidump_aarch64.c
@@ -50,7 +50,6 @@ __FBSDID("$FreeBSD$");
 
 struct vmstate {
 	struct minidumphdr hdr;
-	struct hpt hpt;
 	uint64_t *page_map;
 };
 
@@ -67,7 +66,6 @@ _aarch64_minidump_freevtop(kvm_t *kd)
 {
 	struct vmstate *vm = kd->vmst;
 
-	_kvm_hpt_free(&vm->hpt);
 	free(vm->page_map);
 	free(vm);
 	kd->vmst = NULL;
@@ -77,8 +75,7 @@ static int
 _aarch64_minidump_initvtop(kvm_t *kd)
 {
 	struct vmstate *vmst;
-	uint64_t *bitmap;
-	off_t off;
+	off_t off, sparse_off;
 
 	vmst = _kvm_malloc(kd, sizeof(*vmst));
 	if (vmst == NULL) {
@@ -114,19 +111,12 @@ _aarch64_minidump_initvtop(kvm_t *kd)
 	/* Skip header and msgbuf */
 	off = AARCH64_PAGE_SIZE + aarch64_round_page(vmst->hdr.msgbufsize);
 
-	bitmap = _kvm_malloc(kd, vmst->hdr.bitmapsize);
-	if (bitmap == NULL) {
-		_kvm_err(kd, kd->program,
-		    "cannot allocate %d bytes for bitmap",
-		    vmst->hdr.bitmapsize);
-		return (-1);
-	}
-	if (pread(kd->pmfd, bitmap, vmst->hdr.bitmapsize, off) !=
-	    (ssize_t)vmst->hdr.bitmapsize) {
-		_kvm_err(kd, kd->program,
-		    "cannot read %d bytes for page bitmap",
-		    vmst->hdr.bitmapsize);
-		free(bitmap);
+	/* build physical address lookup table for sparse pages */
+	sparse_off = off + aarch64_round_page(vmst->hdr.bitmapsize) +
+	    aarch64_round_page(vmst->hdr.pmapsize);
+	if (_kvm_pt_init(kd, vmst->hdr.bitmapsize, off, sparse_off,
+	    AARCH64_PAGE_SIZE, sizeof(uint64_t)) == -1) {
+		_kvm_err(kd, kd->program, "cannot load core bitmap");
 		return (-1);
 	}
 	off += aarch64_round_page(vmst->hdr.bitmapsize);
@@ -136,7 +126,6 @@ _aarch64_minidump_initvtop(kvm_t *kd)
 		_kvm_err(kd, kd->program,
 		    "cannot allocate %d bytes for page_map",
 		    vmst->hdr.pmapsize);
-		free(bitmap);
 		return (-1);
 	}
 	/* This is the end of the dump, savecore may have truncated it. */
@@ -149,15 +138,9 @@ _aarch64_minidump_initvtop(kvm_t *kd)
 	    AARCH64_PAGE_SIZE) {
 		_kvm_err(kd, kd->program, "cannot read %d bytes for page_map",
 		    vmst->hdr.pmapsize);
-		free(bitmap);
 		return (-1);
 	}
-	off += vmst->hdr.pmapsize;
-
-	/* build physical address hash table for sparse pages */
-	_kvm_hpt_init(kd, &vmst->hpt, bitmap, vmst->hdr.bitmapsize, off,
-	    AARCH64_PAGE_SIZE, sizeof(*bitmap));
-	free(bitmap);
+	off += aarch64_round_page(vmst->hdr.pmapsize);
 
 	return (0);
 }
@@ -178,7 +161,7 @@ _aarch64_minidump_vatop(kvm_t *kd, kvaddr_t va, off_t *pa)
 	if (va >= vm->hdr.dmapbase && va < vm->hdr.dmapend) {
 		a = (va - vm->hdr.dmapbase + vm->hdr.dmapphys) &
 		    ~AARCH64_PAGE_MASK;
-		ofs = _kvm_hpt_find(&vm->hpt, a);
+		ofs = _kvm_pt_find(kd, a);
 		if (ofs == -1) {
 			_kvm_err(kd, kd->program, "_aarch64_minidump_vatop: "
 			    "direct map address 0x%jx not in minidump",
@@ -198,7 +181,7 @@ _aarch64_minidump_vatop(kvm_t *kd, kvaddr_t va, off_t *pa)
 			goto invalid;
 		}
 		a = l3 & ~AARCH64_ATTR_MASK;
-		ofs = _kvm_hpt_find(&vm->hpt, a);
+		ofs = _kvm_pt_find(kd, a);
 		if (ofs == -1) {
 			_kvm_err(kd, kd->program, "_aarch64_minidump_vatop: "
 			    "physical address 0x%jx not in minidump",
diff --git a/lib/libkvm/kvm_minidump_amd64.c b/lib/libkvm/kvm_minidump_amd64.c
index 3df7a62461f0..21bb5d4774b2 100644
--- a/lib/libkvm/kvm_minidump_amd64.c
+++ b/lib/libkvm/kvm_minidump_amd64.c
@@ -49,7 +49,6 @@ __FBSDID("$FreeBSD$");
 
 struct vmstate {
 	struct minidumphdr hdr;
-	struct hpt hpt;
 	amd64_pte_t *page_map;
 };
 
@@ -66,9 +65,7 @@ _amd64_minidump_freevtop(kvm_t *kd)
 {
 	struct vmstate *vm = kd->vmst;
 
-	_kvm_hpt_free(&vm->hpt);
-	if (vm->page_map)
-		free(vm->page_map);
+	free(vm->page_map);
 	free(vm);
 	kd->vmst = NULL;
 }
@@ -77,8 +74,7 @@ static int
 _amd64_minidump_initvtop(kvm_t *kd)
 {
 	struct vmstate *vmst;
-	uint64_t *bitmap;
-	off_t off;
+	off_t off, sparse_off;
 
 	vmst = _kvm_malloc(kd, sizeof(*vmst));
 	if (vmst == NULL) {
@@ -116,37 +112,28 @@ _amd64_minidump_initvtop(kvm_t *kd)
 	/* Skip header and msgbuf */
 	off = AMD64_PAGE_SIZE + amd64_round_page(vmst->hdr.msgbufsize);
 
-	bitmap = _kvm_malloc(kd, vmst->hdr.bitmapsize);
-	if (bitmap == NULL) {
-		_kvm_err(kd, kd->program, "cannot allocate %d bytes for bitmap", vmst->hdr.bitmapsize);
-		return (-1);
-	}
-	if (pread(kd->pmfd, bitmap, vmst->hdr.bitmapsize, off) !=
-	    (ssize_t)vmst->hdr.bitmapsize) {
-		_kvm_err(kd, kd->program, "cannot read %d bytes for page bitmap", vmst->hdr.bitmapsize);
-		free(bitmap);
+	sparse_off = off + amd64_round_page(vmst->hdr.bitmapsize) +
+	    amd64_round_page(vmst->hdr.pmapsize);
+	if (_kvm_pt_init(kd, vmst->hdr.bitmapsize, off, sparse_off,
+	    AMD64_PAGE_SIZE, sizeof(uint64_t)) == -1) {
+		_kvm_err(kd, kd->program, "cannot load core bitmap");
 		return (-1);
 	}
 	off += amd64_round_page(vmst->hdr.bitmapsize);
 
 	vmst->page_map = _kvm_malloc(kd, vmst->hdr.pmapsize);
 	if (vmst->page_map == NULL) {
-		_kvm_err(kd, kd->program, "cannot allocate %d bytes for page_map", vmst->hdr.pmapsize);
-		free(bitmap);
+		_kvm_err(kd, kd->program, "cannot allocate %d bytes for page_map",
+		    vmst->hdr.pmapsize);
 		return (-1);
 	}
 	if (pread(kd->pmfd, vmst->page_map, vmst->hdr.pmapsize, off) !=
 	    (ssize_t)vmst->hdr.pmapsize) {
-		_kvm_err(kd, kd->program, "cannot read %d bytes for page_map", vmst->hdr.pmapsize);
-		free(bitmap);
+		_kvm_err(kd, kd->program, "cannot read %d bytes for page_map",
+		    vmst->hdr.pmapsize);
 		return (-1);
 	}
-	off += vmst->hdr.pmapsize;
-
-	/* build physical address hash table for sparse pages */
-	_kvm_hpt_init(kd, &vmst->hpt, bitmap, vmst->hdr.bitmapsize, off,
-	    AMD64_PAGE_SIZE, sizeof(*bitmap));
-	free(bitmap);
+	off += amd64_round_page(vmst->hdr.pmapsize);
 
 	return (0);
 }
@@ -175,7 +162,7 @@ _amd64_minidump_vatop_v1(kvm_t *kd, kvaddr_t va, off_t *pa)
 			goto invalid;
 		}
 		a = pte & AMD64_PG_FRAME;
-		ofs = _kvm_hpt_find(&vm->hpt, a);
+		ofs = _kvm_pt_find(kd, a);
 		if (ofs == -1) {
 			_kvm_err(kd, kd->program,
 	    "_amd64_minidump_vatop_v1: physical address 0x%jx not in minidump",
@@ -186,7 +173,7 @@ _amd64_minidump_vatop_v1(kvm_t *kd, kvaddr_t va, off_t *pa)
 		return (AMD64_PAGE_SIZE - offset);
 	} else if (va >= vm->hdr.dmapbase && va < vm->hdr.dmapend) {
 		a = (va - vm->hdr.dmapbase) & ~AMD64_PAGE_MASK;
-		ofs = _kvm_hpt_find(&vm->hpt, a);
+		ofs = _kvm_pt_find(kd, a);
 		if (ofs == -1) {
 			_kvm_err(kd, kd->program,
     "_amd64_minidump_vatop_v1: direct map address 0x%jx not in minidump",
@@ -235,20 +222,20 @@ _amd64_minidump_vatop(kvm_t *kd, kvaddr_t va, off_t *pa)
 		}
 		if ((pde & AMD64_PG_PS) == 0) {
 			a = pde & AMD64_PG_FRAME;
-			ofs = _kvm_hpt_find(&vm->hpt, a);
+			/* TODO: Just read the single PTE */
+			ofs = _kvm_pt_find(kd, a);
 			if (ofs == -1) {
 				_kvm_err(kd, kd->program,
-	    "_amd64_minidump_vatop: pt physical address 0x%jx not in minidump",
+				    "cannot find page table entry for %ju",
 				    (uintmax_t)a);
 				goto invalid;
 			}
-			/* TODO: Just read the single PTE */
 			if (pread(kd->pmfd, &pt, AMD64_PAGE_SIZE, ofs) !=
 			    AMD64_PAGE_SIZE) {
 				_kvm_err(kd, kd->program,
-				    "cannot read %d bytes for page table",
-				    AMD64_PAGE_SIZE);
-				return (-1);
+				    "cannot read page table entry for %ju",
+				    (uintmax_t)a);
+				goto invalid;
 			}
 			pteindex = (va >> AMD64_PAGE_SHIFT) &
 			    (AMD64_NPTEPG - 1);
@@ -263,7 +250,7 @@ _amd64_minidump_vatop(kvm_t *kd, kvaddr_t va, off_t *pa)
 			a = pde & AMD64_PG_PS_FRAME;
 			a += (va & AMD64_PDRMASK) ^ offset;
 		}
-		ofs = _kvm_hpt_find(&vm->hpt, a);
+		ofs = _kvm_pt_find(kd, a);
 		if (ofs == -1) {
 			_kvm_err(kd, kd->program,
 	    "_amd64_minidump_vatop: physical address 0x%jx not in minidump",
@@ -274,7 +261,7 @@ _amd64_minidump_vatop(kvm_t *kd, kvaddr_t va, off_t *pa)
 		return (AMD64_PAGE_SIZE - offset);
 	} else if (va >= vm->hdr.dmapbase && va < vm->hdr.dmapend) {
 		a = (va - vm->hdr.dmapbase) & ~AMD64_PAGE_MASK;
-		ofs = _kvm_hpt_find(&vm->hpt, a);
+		ofs = _kvm_pt_find(kd, a);
 		if (ofs == -1) {
 			_kvm_err(kd, kd->program,
 	    "_amd64_minidump_vatop: direct map address 0x%jx not in minidump",
diff --git a/lib/libkvm/kvm_minidump_arm.c b/lib/libkvm/kvm_minidump_arm.c
index f24a3eea1f3e..53ca3f02fa73 100644
--- a/lib/libkvm/kvm_minidump_arm.c
+++ b/lib/libkvm/kvm_minidump_arm.c
@@ -51,7 +51,6 @@ __FBSDID("$FreeBSD$");
 
 struct vmstate {
 	struct		minidumphdr hdr;
-	struct		hpt hpt;
 	void		*ptemap;
 	unsigned char	ei_data;
 };
@@ -69,9 +68,7 @@ _arm_minidump_freevtop(kvm_t *kd)
 {
 	struct vmstate *vm = kd->vmst;
 
-	_kvm_hpt_free(&vm->hpt);
-	if (vm->ptemap)
-		free(vm->ptemap);
+	free(vm->ptemap);
 	free(vm);
 	kd->vmst = NULL;
 }
@@ -80,8 +77,7 @@ static int
 _arm_minidump_initvtop(kvm_t *kd)
 {
 	struct vmstate *vmst;
-	uint32_t *bitmap;
-	off_t off;
+	off_t off, sparse_off;
 
 	vmst = _kvm_malloc(kd, sizeof(*vmst));
 	if (vmst == NULL) {
@@ -122,18 +118,11 @@ _arm_minidump_initvtop(kvm_t *kd)
 	/* Skip header and msgbuf */
 	off = ARM_PAGE_SIZE + arm_round_page(vmst->hdr.msgbufsize);
 
-	bitmap = _kvm_malloc(kd, vmst->hdr.bitmapsize);
-	if (bitmap == NULL) {
-		_kvm_err(kd, kd->program, "cannot allocate %d bytes for "
-		    "bitmap", vmst->hdr.bitmapsize);
-		return (-1);
-	}
-
-	if (pread(kd->pmfd, bitmap, vmst->hdr.bitmapsize, off) !=
-	    (ssize_t)vmst->hdr.bitmapsize) {
-		_kvm_err(kd, kd->program, "cannot read %d bytes for page bitmap",
-		    vmst->hdr.bitmapsize);
-		free(bitmap);
+	sparse_off = off + arm_round_page(vmst->hdr.bitmapsize) +
+	    arm_round_page(vmst->hdr.ptesize);
+	if (_kvm_pt_init(kd, vmst->hdr.bitmapsize, off, sparse_off,
+	    ARM_PAGE_SIZE, sizeof(uint32_t)) == -1) {
+		_kvm_err(kd, kd->program, "cannot load core bitmap");
 		return (-1);
 	}
 	off += arm_round_page(vmst->hdr.bitmapsize);
@@ -142,7 +131,6 @@ _arm_minidump_initvtop(kvm_t *kd)
 	if (vmst->ptemap == NULL) {
 		_kvm_err(kd, kd->program, "cannot allocate %d bytes for "
 		    "ptemap", vmst->hdr.ptesize);
-		free(bitmap);
 		return (-1);
 	}
 
@@ -150,16 +138,9 @@ _arm_minidump_initvtop(kvm_t *kd)
 	    (ssize_t)vmst->hdr.ptesize) {
 		_kvm_err(kd, kd->program, "cannot read %d bytes for ptemap",
 		    vmst->hdr.ptesize);
-		free(bitmap);
 		return (-1);
 	}
-
-	off += vmst->hdr.ptesize;
-
-	/* Build physical address hash table for sparse pages */
-	_kvm_hpt_init(kd, &vmst->hpt, bitmap, vmst->hdr.bitmapsize, off,
-	    ARM_PAGE_SIZE, sizeof(*bitmap));
-	free(bitmap);
+	off += arm_round_page(vmst->hdr.ptesize);
 
 	return (0);
 }
@@ -209,7 +190,7 @@ _arm_minidump_kvatop(kvm_t *kd, kvaddr_t va, off_t *pa)
 			a = pte & ARM_L2_S_FRAME;
 		}
 
-		ofs = _kvm_hpt_find(&vm->hpt, a);
+		ofs = _kvm_pt_find(kd, a);
 		if (ofs == -1) {
 			_kvm_err(kd, kd->program, "_arm_minidump_kvatop: "
 			    "physical address 0x%jx not in minidump",
diff --git a/lib/libkvm/kvm_minidump_i386.c b/lib/libkvm/kvm_minidump_i386.c
index a154adf91a5f..c8fc38eb45bc 100644
--- a/lib/libkvm/kvm_minidump_i386.c
+++ b/lib/libkvm/kvm_minidump_i386.c
@@ -49,7 +49,6 @@ __FBSDID("$FreeBSD$");
 
 struct vmstate {
 	struct minidumphdr hdr;
-	struct hpt hpt;
 	void *ptemap;
 };
 
@@ -66,9 +65,7 @@ _i386_minidump_freevtop(kvm_t *kd)
 {
 	struct vmstate *vm = kd->vmst;
 
-	_kvm_hpt_free(&vm->hpt);
-	if (vm->ptemap)
-		free(vm->ptemap);
+	free(vm->ptemap);
 	free(vm);
 	kd->vmst = NULL;
 }
@@ -77,8 +74,7 @@ static int
 _i386_minidump_initvtop(kvm_t *kd)
 {
 	struct vmstate *vmst;
-	uint32_t *bitmap;
-	off_t off;
+	off_t off, sparse_off;
 
 	vmst = _kvm_malloc(kd, sizeof(*vmst));
 	if (vmst == NULL) {
@@ -110,15 +106,11 @@ _i386_minidump_initvtop(kvm_t *kd)
 	/* Skip header and msgbuf */
 	off = I386_PAGE_SIZE + i386_round_page(vmst->hdr.msgbufsize);
 
-	bitmap = _kvm_malloc(kd, vmst->hdr.bitmapsize);
-	if (bitmap == NULL) {
-		_kvm_err(kd, kd->program, "cannot allocate %d bytes for bitmap", vmst->hdr.bitmapsize);
-		return (-1);
-	}
-	if (pread(kd->pmfd, bitmap, vmst->hdr.bitmapsize, off) !=
-	    (ssize_t)vmst->hdr.bitmapsize) {
-		_kvm_err(kd, kd->program, "cannot read %d bytes for page bitmap", vmst->hdr.bitmapsize);
-		free(bitmap);
+	sparse_off = off + i386_round_page(vmst->hdr.bitmapsize) +
+	    i386_round_page(vmst->hdr.ptesize);
+	if (_kvm_pt_init(kd, vmst->hdr.bitmapsize, off, sparse_off,
+	    I386_PAGE_SIZE, sizeof(uint32_t)) == -1) {
+		_kvm_err(kd, kd->program, "cannot load core bitmap");
 		return (-1);
 	}
 	off += i386_round_page(vmst->hdr.bitmapsize);
@@ -126,21 +118,14 @@ _i386_minidump_initvtop(kvm_t *kd)
 	vmst->ptemap = _kvm_malloc(kd, vmst->hdr.ptesize);
 	if (vmst->ptemap == NULL) {
 		_kvm_err(kd, kd->program, "cannot allocate %d bytes for ptemap", vmst->hdr.ptesize);
-		free(bitmap);
 		return (-1);
 	}
 	if (pread(kd->pmfd, vmst->ptemap, vmst->hdr.ptesize, off) !=
 	    (ssize_t)vmst->hdr.ptesize) {
 		_kvm_err(kd, kd->program, "cannot read %d bytes for ptemap", vmst->hdr.ptesize);
-		free(bitmap);
 		return (-1);
 	}
-	off += vmst->hdr.ptesize;
-
-	/* build physical address hash table for sparse pages */
-	_kvm_hpt_init(kd, &vmst->hpt, bitmap, vmst->hdr.bitmapsize, off,
-	    I386_PAGE_SIZE, sizeof(*bitmap));
-	free(bitmap);
+	off += i386_round_page(vmst->hdr.ptesize);
 
 	return (0);
 }
@@ -171,7 +156,7 @@ _i386_minidump_vatop_pae(kvm_t *kd, kvaddr_t va, off_t *pa)
 			goto invalid;
 		}
 		a = pte & I386_PG_FRAME_PAE;
-		ofs = _kvm_hpt_find(&vm->hpt, a);
+		ofs = _kvm_pt_find(kd, a);
 		if (ofs == -1) {
 			_kvm_err(kd, kd->program,
 	    "_i386_minidump_vatop_pae: physical address 0x%jx not in minidump",
@@ -218,7 +203,7 @@ _i386_minidump_vatop(kvm_t *kd, kvaddr_t va, off_t *pa)
 			goto invalid;
 		}
 		a = pte & I386_PG_FRAME;
-		ofs = _kvm_hpt_find(&vm->hpt, a);
+		ofs = _kvm_pt_find(kd, a);
 		if (ofs == -1) {
 			_kvm_err(kd, kd->program,
 	    "_i386_minidump_vatop: physical address 0x%jx not in minidump",
diff --git a/lib/libkvm/kvm_minidump_mips.c b/lib/libkvm/kvm_minidump_mips.c
index bec6426e1682..77d1892df3a2 100644
--- a/lib/libkvm/kvm_minidump_mips.c
+++ b/lib/libkvm/kvm_minidump_mips.c
@@ -52,7 +52,6 @@ __FBSDID("$FreeBSD$");
 
 struct vmstate {
 	struct		minidumphdr hdr;
-	struct		hpt hpt;
 	void		*ptemap;
 	int		pte_size;
 };
@@ -74,9 +73,7 @@ _mips_minidump_freevtop(kvm_t *kd)
 {
 	struct vmstate *vm = kd->vmst;
 
-	_kvm_hpt_free(&vm->hpt);
-	if (vm->ptemap)
-		free(vm->ptemap);
+	free(vm->ptemap);
 	free(vm);
 	kd->vmst = NULL;
 }
@@ -85,8 +82,7 @@ static int
 _mips_minidump_initvtop(kvm_t *kd)
 {
 	struct vmstate *vmst;
-	uint32_t *bitmap;
-	off_t off;
+	off_t off, sparse_off;
 
 	vmst = _kvm_malloc(kd, sizeof(*vmst));
 	if (vmst == NULL) {
@@ -129,18 +125,11 @@ _mips_minidump_initvtop(kvm_t *kd)
 	/* Skip header and msgbuf */
 	off = MIPS_PAGE_SIZE + mips_round_page(vmst->hdr.msgbufsize);
 
-	bitmap = _kvm_malloc(kd, vmst->hdr.bitmapsize);
-	if (bitmap == NULL) {
-		_kvm_err(kd, kd->program, "cannot allocate %d bytes for "
-		    "bitmap", vmst->hdr.bitmapsize);
-		return (-1);
-	}
-
-	if (pread(kd->pmfd, bitmap, vmst->hdr.bitmapsize, off) !=
-	    (ssize_t)vmst->hdr.bitmapsize) {
-		_kvm_err(kd, kd->program, "cannot read %d bytes for page bitmap",
-		    vmst->hdr.bitmapsize);
-		free(bitmap);
+	sparse_off = off + mips_round_page(vmst->hdr.bitmapsize) +
+	    mips_round_page(vmst->hdr.ptesize);
+	if (_kvm_pt_init(kd, vmst->hdr.bitmapsize, off, sparse_off,
+	    MIPS_PAGE_SIZE, sizeof(uint32_t)) == -1) {
+		_kvm_err(kd, kd->program, "cannot load core bitmap");
 		return (-1);
 	}
 	off += mips_round_page(vmst->hdr.bitmapsize);
@@ -149,7 +138,6 @@ _mips_minidump_initvtop(kvm_t *kd)
 	if (vmst->ptemap == NULL) {
 		_kvm_err(kd, kd->program, "cannot allocate %d bytes for "
 		    "ptemap", vmst->hdr.ptesize);
-		free(bitmap);
 		return (-1);
 	}
 
@@ -157,16 +145,9 @@ _mips_minidump_initvtop(kvm_t *kd)
 	    (ssize_t)vmst->hdr.ptesize) {
 		_kvm_err(kd, kd->program, "cannot read %d bytes for ptemap",
 		    vmst->hdr.ptesize);
-		free(bitmap);
 		return (-1);
 	}
-
-	off += vmst->hdr.ptesize;
-
-	/* Build physical address hash table for sparse pages */
-	_kvm_hpt_init(kd, &vmst->hpt, bitmap, vmst->hdr.bitmapsize, off,
-	    MIPS_PAGE_SIZE, sizeof(*bitmap));
-	free(bitmap);
+	off += mips_round_page(vmst->hdr.ptesize);
 
 	return (0);
 }
@@ -243,7 +224,7 @@ _mips_minidump_kvatop(kvm_t *kd, kvaddr_t va, off_t *pa)
 	}
 
 found:
-	ofs = _kvm_hpt_find(&vm->hpt, a);
+	ofs = _kvm_pt_find(kd, a);
 	if (ofs == -1) {
 		_kvm_err(kd, kd->program, "_mips_minidump_kvatop: physical "
 		    "address 0x%jx not in minidump", (uintmax_t)a);
diff --git a/lib/libkvm/kvm_private.c b/lib/libkvm/kvm_private.c
index 940a5a92eaa7..f790757adbf0 100644
--- a/lib/libkvm/kvm_private.c
+++ b/lib/libkvm/kvm_private.c
@@ -46,6 +46,7 @@ __FBSDID("$FreeBSD$");
 
 #include <net/vnet.h>
 
+#include <assert.h>
 #include <fcntl.h>
 #include <kvm.h>
 #include <limits.h>
@@ -213,73 +214,178 @@ bad:
 	return (-1);
 }
 
-static void
-_kvm_hpt_insert(struct hpt *hpt, uint64_t pa, off_t off)
+/*
+ * Transform v such that only bits [bit0, bitN) may be set.  Generates a
+ * bitmask covering the number of bits, then shifts so +bit0+ is the first.
+ */
+static uint64_t
+bitmask_range(uint64_t v, uint64_t bit0, uint64_t bitN)
 {
-	struct hpte *hpte;
-	uint32_t fnv = FNV1_32_INIT;
-
-	fnv = fnv_32_buf(&pa, sizeof(pa), fnv);
-	fnv &= (HPT_SIZE - 1);
-	hpte = malloc(sizeof(*hpte));
-	hpte->pa = pa;
-	hpte->off = off;
-	hpte->next = hpt->hpt_head[fnv];
-	hpt->hpt_head[fnv] = hpte;
+	if (bit0 == 0 && bitN == BITS_IN(v))
+		return (v);
+
+	return (v & (((1ULL << (bitN - bit0)) - 1ULL) << bit0));
 }
 
-void
-_kvm_hpt_init(kvm_t *kd, struct hpt *hpt, void *base, size_t len, off_t off,
-    int page_size, int word_size)
+/*
+ * Returns the number of bits in a given byte array range starting at a
+ * given base, from bit0 to bitN.  bit0 may be non-zero in the case of
+ * counting backwards from bitN.
+ */
+static uint64_t
+popcount_bytes(uint64_t *addr, uint32_t bit0, uint32_t bitN)
 {
-	uint64_t bits, idx, pa;
-	uint64_t *base64;
-	uint32_t *base32;
-
-	base64 = base;
-	base32 = base;
-	for (idx = 0; idx < len / word_size; idx++) {
-		if (word_size == sizeof(uint64_t))
-			bits = _kvm64toh(kd, base64[idx]);
-		else
-			bits = _kvm32toh(kd, base32[idx]);
-		pa = idx * word_size * NBBY * page_size;
-		for (; bits != 0; bits >>= 1, pa += page_size) {
-			if ((bits & 1) == 0)
-				continue;
-			_kvm_hpt_insert(hpt, pa, off);
-			off += page_size;
-		}
+	uint32_t res = bitN - bit0;
+	uint64_t count = 0;
+	uint32_t bound;
+
+	/* Align to 64-bit boundary on the left side if needed. */
+	if ((bit0 % BITS_IN(*addr)) != 0) {
+		bound = MIN(bitN, roundup2(bit0, BITS_IN(*addr)));
+		count += __bitcount64(bitmask_range(*addr, bit0, bound));
+		res -= (bound - bit0);
+		addr++;
+	}
+
+	while (res > 0) {
+		bound = MIN(res, BITS_IN(*addr));
+		count += __bitcount64(bitmask_range(*addr, 0, bound));
+		res -= bound;
+		addr++;
 	}
+
+	return (count);
 }
 
-off_t
-_kvm_hpt_find(struct hpt *hpt, uint64_t pa)
+int
+_kvm_pt_init(kvm_t *kd, size_t map_len, off_t map_off, off_t sparse_off,
+    int page_size, int word_size)
 {
-	struct hpte *hpte;
-	uint32_t fnv = FNV1_32_INIT;
-
-	fnv = fnv_32_buf(&pa, sizeof(pa), fnv);
-	fnv &= (HPT_SIZE - 1);
-	for (hpte = hpt->hpt_head[fnv]; hpte != NULL; hpte = hpte->next) {
-		if (pa == hpte->pa)
-			return (hpte->off);
+	uint64_t *addr;
+	uint32_t *popcount_bin;
+	int bin_popcounts = 0;
+	uint64_t pc_bins, res;
+	ssize_t rd;
+
+	/*
+	 * Map the bitmap specified by the arguments.
+	 */
+	kd->pt_map = _kvm_malloc(kd, map_len);
+	if (kd->pt_map == NULL) {
+		_kvm_err(kd, kd->program, "cannot allocate %zu bytes for bitmap",
+		    map_len);
+		return (-1);
 	}
-	return (-1);
+	rd = pread(kd->pmfd, kd->pt_map, map_len, map_off);
+	if (rd < 0 || rd != (ssize_t)map_len) {
+		_kvm_err(kd, kd->program, "cannot read %zu bytes for bitmap",
+		    map_len);
+		return (-1);
+	}
+	kd->pt_map_size = map_len;
+
+	/*
+	 * Generate a popcount cache for every POPCOUNT_BITS in the bitmap,
+	 * so lookups only have to calculate the number of bits set between
+	 * a cache point and their bit.  This reduces lookups to O(1),
+	 * without significantly increasing memory requirements.
+	 *
+	 * Round up the number of bins so that 'upper half' lookups work for
+	 * the final bin, if needed.  The first popcount is 0, since no bits
+	 * precede bit 0, so add 1 for that also.  Without this, extra work
+	 * would be needed to handle the first PTEs in _kvm_pt_find().
+	 */
+	addr = kd->pt_map;
+	res = map_len;
+	pc_bins = 1 + (res * NBBY + POPCOUNT_BITS / 2) / POPCOUNT_BITS;
+	kd->pt_popcounts = calloc(pc_bins, sizeof(uint32_t));
+	if (kd->pt_popcounts == NULL)
+		return (-1);
+
+	for (popcount_bin = &kd->pt_popcounts[1]; res > 0;
+	    addr++, res -= sizeof(*addr)) {
+		*popcount_bin += popcount_bytes(addr, 0,
+		    MIN(res * NBBY, BITS_IN(*addr)));
+		if (++bin_popcounts == POPCOUNTS_IN(*addr)) {
+			popcount_bin++;
+			*popcount_bin = *(popcount_bin - 1);
+			bin_popcounts = 0;
+		}
+	}
+
+	assert(pc_bins * sizeof(*popcount_bin) ==
+	    ((uintptr_t)popcount_bin - (uintptr_t)kd->pt_popcounts));
+
+	kd->pt_sparse_off = sparse_off;
+	kd->pt_sparse_size = (uint64_t)*popcount_bin * PAGE_SIZE;
+	kd->pt_page_size = page_size;
+	kd->pt_word_size = word_size;
+	return (0);
 }
 
-void
-_kvm_hpt_free(struct hpt *hpt)
+/*
+ * Find the offset for the given physical page address; returns -1 otherwise.
+ *
+ * A page's offset is represented by the sparse page base offset plus the
+ * number of bits set before its bit multiplied by PAGE_SIZE.  This means
+ * that if a page exists in the dump, it's necessary to know how many pages
+ * in the dump precede it.  Reduce this O(n) counting to O(1) by caching the
+ * number of bits set at POPCOUNT_BITS intervals.
+ *
+ * Then to find the number of pages before the requested address, simply
+ * index into the cache and count the number of bits set between that cache
+ * bin and the page's bit.  Halve the number of bytes that have to be
+ * checked by also counting down from the next higher bin if it's closer.
+ */
+off_t
+_kvm_pt_find(kvm_t *kd, uint64_t pa)
 {
-	struct hpte *hpte, *next;
-	int i;
+	uint64_t *bitmap = kd->pt_map;
+	uint64_t pte_bit_id = pa / PAGE_SIZE;
+	uint64_t pte_u64 = pte_bit_id / BITS_IN(*bitmap);
+	uint64_t popcount_id = pte_bit_id / POPCOUNT_BITS;
+	uint64_t pte_mask = 1ULL << (pte_bit_id % BITS_IN(*bitmap));
+	uint64_t bitN;
+	uint32_t count;
+
+	/* Check whether the page address requested is in the dump. */
+	if (pte_bit_id >= (kd->pt_map_size * NBBY) ||
+	    (bitmap[pte_u64] & pte_mask) == 0)
+		return (-1);
 
-	for (i = 0; i < HPT_SIZE; i++) {
-		for (hpte = hpt->hpt_head[i]; hpte != NULL; hpte = next) {
-			next = hpte->next;
-			free(hpte);
-		}
+	/*
+	 * Add/sub popcounts from the bitmap until the PTE's bit is reached.
+	 * For bits that are in the upper half between the calculated
+	 * popcount id and the next one, use the next one and subtract to
+	 * minimize the number of popcounts required.
+	 */
+	if ((pte_bit_id % POPCOUNT_BITS) < (POPCOUNT_BITS / 2)) {
+		count = kd->pt_popcounts[popcount_id] + popcount_bytes(
+		    bitmap + popcount_id * POPCOUNTS_IN(*bitmap),
+		    0, pte_bit_id - popcount_id * POPCOUNT_BITS);
+	} else {
+		/*
+		 * Counting in reverse is trickier, since we must avoid
+		 * reading from bytes that are not in range, and invert.
+		 */
+		uint64_t pte_u64_bit_off = pte_u64 * BITS_IN(*bitmap);
+
+		popcount_id++;
+		bitN = MIN(popcount_id * POPCOUNT_BITS,
+		    kd->pt_map_size * BITS_IN(uint8_t));
+		count = kd->pt_popcounts[popcount_id] - popcount_bytes(
+		    bitmap + pte_u64,
+		    pte_bit_id - pte_u64_bit_off, bitN - pte_u64_bit_off);
 	}
+
+	/*
+	 * This can only happen if the core is truncated.  Treat these
+	 * entries as if they don't exist, since their backing doesn't.
+	 */
+	if (count >= (kd->pt_sparse_size / PAGE_SIZE))
+		return (-1);
+
+	return (kd->pt_sparse_off + (uint64_t)count * PAGE_SIZE);
 }
 
 static int
diff --git a/lib/libkvm/kvm_private.h b/lib/libkvm/kvm_private.h
index 78b48458cd6f..814a06f63b99 100644
--- a/lib/libkvm/kvm_private.h
+++ b/lib/libkvm/kvm_private.h
@@ -97,23 +97,21 @@ struct __kvm {
 	uintptr_t	*dpcpu_off;	/* base array, indexed by CPU ID */
 	u_int		dpcpu_curcpu;	/* CPU we're currently working with */
 	kvaddr_t	dpcpu_curoff;	/* dpcpu base of current CPU */
-};
 
-/*
- * Page table hash used by minidump backends to map physical addresses
- * to file offsets.
- */
-struct hpte {
-	struct hpte	*next;
-	uint64_t	pa;
-	off_t		off;
+	/* Page table lookup structures. */
+	uint64_t	*pt_map;
+	size_t		pt_map_size;
+	off_t		pt_sparse_off;
+	uint64_t	pt_sparse_size;
+	uint32_t	*pt_popcounts;
+	unsigned int	pt_page_size;
+	unsigned int	pt_word_size;
 };
 
-#define HPT_SIZE 1024
-
-struct hpt {
-	struct hpte	*hpt_head[HPT_SIZE];
-};
+/* Page table lookup constants. */
+#define POPCOUNT_BITS	1024
+#define BITS_IN(v)	(sizeof(v) * NBBY)
+#define POPCOUNTS_IN(v)	(POPCOUNT_BITS / BITS_IN(v))
 
 /*
  * Functions used internally by kvm, but across kvm modules.
@@ -154,6 +152,5 @@ kvaddr_t _kvm_dpcpu_validaddr(kvm_t *, kvaddr_t);
 int	 _kvm_probe_elf_kernel(kvm_t *, int, int);
 int	 _kvm_is_minidump(kvm_t *);
 int	 _kvm_read_core_phdrs(kvm_t *, size_t *, GElf_Phdr **);
-void	 _kvm_hpt_init(kvm_t *, struct hpt *, void *, size_t, off_t, int, int);
-off_t	 _kvm_hpt_find(struct hpt *, uint64_t);
-void	 _kvm_hpt_free(struct hpt *);
+int	 _kvm_pt_init(kvm_t *, size_t, off_t, off_t, int, int);
+off_t	 _kvm_pt_find(kvm_t *, uint64_t);