1/*
2 * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/*
29 * @OSF_COPYRIGHT@
30 */
31/*
32 * Mach Operating System
33 * Copyright (c) 1991,1990,1989 Carnegie Mellon University
34 * All Rights Reserved.
35 *
36 * Permission to use, copy, modify and distribute this software and its
37 * documentation is hereby granted, provided that both the copyright
38 * notice and this permission notice appear in all copies of the
39 * software, derivative works or modified versions, and any portions
40 * thereof, and that both notices appear in supporting documentation.
41 *
42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
43 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
45 *
46 * Carnegie Mellon requests users of this software to return to
47 *
48 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
49 *  School of Computer Science
50 *  Carnegie Mellon University
51 *  Pittsburgh PA 15213-3890
52 *
53 * any improvements or extensions that they make and grant Carnegie Mellon
54 * the rights to redistribute these changes.
55 */
56/*
57 */
58
59/*
60 *	This module maintains information about the presence of
61 *	pages not in memory.  Since an external memory object
62 *	must maintain a complete knowledge of its contents, this
63 *	information takes the form of hints.
64 */
65#include <string.h>	/* for memcpy()/memset() */
66
67#include <mach/boolean.h>
68#include <vm/vm_external.h>
69#include <kern/kalloc.h>
70#include <mach/vm_param.h>
71#include <kern/assert.h>
72
73/*
74 *	The implementation uses bit arrays to record whether
75 *	a page has been written to external storage.  For
76 *	convenience, these bit arrays come in various sizes.
77 *	For example, a map N bytes long can record:
78 *
79 *	  16 bytes =   128 pages = (@ 4KB/page)    512KB
80 *	1024 bytes =  8192 pages = (@ 4KB/page)  32MB
81 *	4096 bytes = 32768 pages = (@ 4KB/page) 128MB
82 *
83 *	For a 32-bit machine with 4KB pages, the largest size
84 *	would be 128KB = 32 pages. Machines with a larger page
85 *	size are more efficient.
86 *
87 *	This subsystem must be very careful about memory allocation,
88 *	since vm_external_create() is almost always called with
89 *	vm_privilege set. The largest map to be allocated must be less
90 *	than or equal to a single page, and the kalloc subsystem must
91 *	never allocate more than a single page in response to a kalloc()
92 *	request. Also, vm_external_destroy() must not take any blocking
93 *	locks, since it is called with a vm_object lock held. This
94 *	implies that kfree() MUST be implemented in terms of zfree()
95 *	NOT kmem_free() for all request sizes that this subsystem uses.
96 *
97 *	For efficiency, this subsystem knows that the kalloc() subsystem
98 *	is implemented in terms of power-of-2 allocation, and that the
99 *	minimum allocation unit is KALLOC_MINSIZE
100 *
101 *	XXXO
102 *	Should consider using existence_map to hold bits directly
103 *	when existence_size <= 4 bytes (i.e., 32 pages).
104 */
105
106#define	SMALL_SIZE	KALLOC_MINSIZE
107#define	LARGE_SIZE	PAGE_SIZE
108
109static vm_object_size_t power_of_2(vm_object_size_t size);
110
111static vm_object_size_t
112power_of_2(vm_object_size_t size)
113{
114	vm_object_size_t power;
115
116	power = 2 * SMALL_SIZE;
117	while (power < size) {
118		power <<= 1;
119	}
120	return(power);
121}
122
123vm_external_map_t
124vm_external_create(
125	vm_object_offset_t	size)
126{
127	vm_object_size_t	bytes;
128	vm_external_map_t	result = VM_EXTERNAL_NULL;
129
130	bytes = stob(size);
131	if (bytes <= SMALL_SIZE) {
132		result = (vm_external_map_t)kalloc(SMALL_SIZE);
133		if (result != NULL) {
134			memset(result, 0, SMALL_SIZE);
135		}
136	} else if (bytes <= LARGE_SIZE) {
137		bytes = power_of_2(bytes);
138
139		assert((vm_size_t) bytes == bytes);
140		result = (vm_external_map_t)kalloc((vm_size_t)bytes);
141		if (result != NULL) {
142			assert((size_t) bytes == bytes);
143			memset(result, 0, (size_t) bytes);
144		}
145	}
146	return(result);
147}
148
149void
150vm_external_destroy(
151	vm_external_map_t	map,
152	vm_object_size_t	size)
153{
154	vm_object_size_t bytes;
155
156	if (map == VM_EXTERNAL_NULL)
157		return;
158
159	bytes = stob(size);
160	if (bytes <= SMALL_SIZE) {
161		bytes = SMALL_SIZE;
162	} else {
163		bytes = power_of_2(bytes);
164	}
165	assert((vm_size_t) bytes == bytes);
166	kfree(map, (vm_size_t) bytes);
167}
168
169/*
170 * Return the number of bytes needed for a vm_external_map given the
171 * size of the object to be mapped, i.e. the size of the map that was
172 * created by vm_external_create.
173 */
174vm_object_size_t
175vm_external_map_size(
176	vm_object_size_t	size)
177{
178	vm_object_size_t	bytes;
179
180	bytes = stob(size);
181	if (bytes != 0) {
182	        if (bytes <= SMALL_SIZE) {
183			bytes = SMALL_SIZE;
184		} else {
185			bytes = power_of_2(bytes);
186		}
187	}
188	return bytes;
189}
190
191void
192vm_external_copy(
193	vm_external_map_t	old_map,
194	vm_object_size_t	old_size,
195	vm_external_map_t	new_map)
196{
197	vm_object_size_t	bytes;
198
199	/*
200	 * Cannot copy non-existent maps
201	 */
202	if ((old_map == VM_EXTERNAL_NULL) || (new_map == VM_EXTERNAL_NULL))
203		return;
204
205	/*
206	 * Copy old map to new
207	 */
208	bytes = stob(old_size);
209	assert((size_t) bytes == bytes);
210	memcpy(new_map, old_map, (size_t) bytes);
211}
212
213boolean_t
214vm_external_within(
215	vm_object_size_t	new_size,
216	vm_object_size_t	old_size)
217{
218	vm_object_size_t 	new_bytes;
219	vm_object_size_t 	old_bytes;
220
221	assert(new_size >= old_size);
222
223	/*
224	 * "old_bytes" is calculated to be the actual amount of space
225	 * allocated for a map of size "old_size".
226	 */
227	old_bytes = stob(old_size);
228	if (old_bytes <= SMALL_SIZE) old_bytes = SMALL_SIZE;
229	else if (old_bytes <= LARGE_SIZE) old_bytes = power_of_2(old_bytes);
230
231	/*
232	 * "new_bytes" is the map size required to map the "new_size" object.
233	 * Since the rounding algorithms are the same, we needn't actually
234	 * round up new_bytes to get the correct answer
235	 */
236	new_bytes = stob(new_size);
237
238	return(new_bytes <= old_bytes);
239}
240
241vm_external_state_t
242_vm_external_state_get(
243	vm_external_map_t	map,
244	vm_object_offset_t	offset)
245{
246	uint64_t		bit, byte;
247
248	assert (map != VM_EXTERNAL_NULL);
249
250	bit = atop_64(offset);
251	byte = bit >> 3;
252	if (map[byte] & (1 << (bit & 07))) {
253		return VM_EXTERNAL_STATE_EXISTS;
254	} else {
255		return VM_EXTERNAL_STATE_ABSENT;
256	}
257}
258
259void
260vm_external_state_set(
261	vm_external_map_t	map,
262	vm_object_offset_t	offset)
263{
264	uint64_t		bit, byte;
265
266	if (map == VM_EXTERNAL_NULL)
267		return;
268
269	bit = atop_64(offset);
270	byte = bit >> 3;
271	map[byte] |= (1 << (bit & 07));
272}
273
274void
275vm_external_state_clr(
276	vm_external_map_t	map,
277	vm_object_offset_t	offset)
278{
279	uint64_t		bit, byte;
280
281	if (map == VM_EXTERNAL_NULL)
282		return;
283
284	bit = atop_64(offset);
285	byte = bit >> 3;
286	map[byte] &= ~(1 << (bit & 07));
287}
288
289void
290vm_external_module_initialize(void)
291{
292}
293