1/*-
  2 * SPDX-License-Identifier: BSD-3-Clause
  3 *
  4 * Copyright (c) 2003 Peter Wemm.
  5 * All rights reserved.
  6 *
  7 * This code is derived from software contributed to Berkeley by
  8 * the Systems Programming Group of the University of Utah Computer
  9 * Science Department and William Jolitz of UUNET Technologies Inc.
 10 *
 11 * Redistribution and use in source and binary forms, with or without
 12 * modification, are permitted provided that the following conditions
 13 * are met:
 14 * 1. Redistributions of source code must retain the above copyright
 15 *    notice, this list of conditions and the following disclaimer.
 16 * 2. Redistributions in binary form must reproduce the above copyright
 17 *    notice, this list of conditions and the following disclaimer in the
 18 *    documentation and/or other materials provided with the distribution.
 19 * 3. Neither the name of the University nor the names of its contributors
 20 *    may be used to endorse or promote products derived from this software
 21 *    without specific prior written permission.
 22 *
 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 26 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 33 * SUCH DAMAGE.
 34 */
 35
 36#ifndef __SYS__PV_ENTRY_H__
 37#define	__SYS__PV_ENTRY_H__
 38
 39#include <sys/param.h>
 40
 41struct pmap;
 42
 43/*
 44 * For each vm_page_t, there is a list of all currently valid virtual
 45 * mappings of that page.  An entry is a pv_entry_t, the list is pv_list.
 46 */
 47typedef struct pv_entry {
 48	vm_offset_t	pv_va;		/* virtual address for mapping */
 49	TAILQ_ENTRY(pv_entry)	pv_next;
 50} *pv_entry_t;
 51
 52/*
 53 * pv_entries are allocated in chunks per-process.  This avoids the
 54 * need to track per-pmap assignments.  Each chunk is the size of a
 55 * single page.
 56 *
 57 * Chunks store a bitmap in pc_map[] to track which entries in the
 58 * bitmap are free (1) or used (0).  PC_FREEL is the value of the last
 59 * entry in the pc_map[] array when a chunk is completely free.  PC_FREEN
 60 * is the value of all the other entries in the pc_map[] array when a
 61 * chunk is completely free.
 62 */
 63#if PAGE_SIZE == 4 * 1024
 64#ifdef __LP64__
 65#define	_NPCPV	168
 66#define	_NPAD	0
 67#else
 68#define	_NPCPV	336
 69#define	_NPAD	0
 70#endif
 71#elif PAGE_SIZE == 16 * 1024
 72#ifdef __LP64__
 73#define	_NPCPV	677
 74#define	_NPAD	1
 75#endif
 76#endif
 77
 78#ifndef _NPCPV
 79#error Unsupported page size
 80#endif
 81
 82/* Support clang < 14 */
 83#ifndef __LONG_WIDTH__
 84#define	__LONG_WIDTH__	(__CHAR_BIT__ * __SIZEOF_LONG__)
 85#endif
 86
 87#define	_NPCM		howmany(_NPCPV, __LONG_WIDTH__)
 88#define	PC_FREEN	~0ul
 89#define	PC_FREEL	((1ul << (_NPCPV % __LONG_WIDTH__)) - 1)
 90
 91#define	PV_CHUNK_HEADER							\
 92	struct pmap		*pc_pmap;				\
 93	TAILQ_ENTRY(pv_chunk)	pc_list;				\
 94	unsigned long		pc_map[_NPCM];	/* bitmap; 1 = free */	\
 95	TAILQ_ENTRY(pv_chunk)	pc_lru;
 96
 97struct pv_chunk_header {
 98	PV_CHUNK_HEADER
 99};
100
101struct pv_chunk {
102	PV_CHUNK_HEADER
103	struct pv_entry		pc_pventry[_NPCPV];
104	unsigned long		pc_pad[_NPAD];
105};
106
107_Static_assert(sizeof(struct pv_chunk) == PAGE_SIZE,
108    "PV entry chunk size mismatch");
109
110#ifdef _KERNEL
111static __inline bool
112pc_is_full(struct pv_chunk *pc)
113{
114	for (u_int i = 0; i < _NPCM; i++) {
115		if (pc->pc_map[i] != 0)
116			return (false);
117	}
118	return (true);
119}
120
121static __inline bool
122pc_is_free(struct pv_chunk *pc)
123{
124	for (u_int i = 0; i < _NPCM - 1; i++) {
125		if (pc->pc_map[i] != PC_FREEN)
126			return (false);
127	}
128	return (pc->pc_map[_NPCM - 1] == PC_FREEL);
129}
130
131static __inline struct pv_chunk *
132pv_to_chunk(pv_entry_t pv)
133{
134	return ((struct pv_chunk *)((uintptr_t)pv & ~(uintptr_t)PAGE_MASK));
135}
136
137#define PV_PMAP(pv) (pv_to_chunk(pv)->pc_pmap)
138#endif
139
140#endif /* !__SYS__PV_ENTRY_H__ */