1/*
2 * Copyright (c) 2009 Apple 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#ifndef _VM_VM_MAP_STORE_H
30#define _VM_VM_MAP_STORE_H
31
32#ifndef VM_MAP_STORE_USE_RB
33#define VM_MAP_STORE_USE_RB
34#endif
35
36#include <libkern/tree.h>
37#include <mach/shared_region.h>
38
39struct _vm_map;
40struct vm_map_entry;
41struct vm_map_copy;
42struct vm_map_header;
43
44struct vm_map_store {
45#ifdef VM_MAP_STORE_USE_RB
46 RB_ENTRY(vm_map_store) entry;
47#endif
48};
49
50#ifdef VM_MAP_STORE_USE_RB
51RB_HEAD(rb_head, vm_map_store);
52#endif
53
54/*
55 * Type: vm_map_entry_t [internal use only]
56 *
57 * Description:
58 * A single mapping within an address map.
59 *
60 * Implementation:
61 * Address map entries consist of start and end addresses,
62 * a VM object (or sub map) and offset into that object,
63 * and user-exported inheritance and protection information.
64 * Control information for virtual copy operations is also
65 * stored in the address map entry.
66 *
67 * Note:
68 * vm_map_relocate_early_elem() knows about this layout,
69 * and needs to be kept in sync.
70 */
71struct vm_map_links {
72 struct vm_map_entry *prev; /* previous entry */
73 struct vm_map_entry *next; /* next entry */
74 vm_map_offset_t start; /* start address */
75 vm_map_offset_t end; /* end address */
76};
77
78
79/*
80 * Type: struct vm_map_header
81 *
82 * Description:
83 * Header for a vm_map and a vm_map_copy.
84 *
85 * Note:
86 * vm_map_relocate_early_elem() knows about this layout,
87 * and needs to be kept in sync.
88 */
89struct vm_map_header {
90 struct vm_map_links links; /* first, last, min, max */
91 int nentries; /* Number of entries */
92 uint16_t page_shift; /* page shift */
93 uint16_t entries_pageable : 1; /* are map entries pageable? */
94 uint16_t __padding : 15;
95#ifdef VM_MAP_STORE_USE_RB
96 struct rb_head rb_head_store;
97#endif /* VM_MAP_STORE_USE_RB */
98};
99
100#define VM_MAP_HDR_PAGE_SHIFT(hdr) ((hdr)->page_shift)
101#define VM_MAP_HDR_PAGE_SIZE(hdr) (1 << VM_MAP_HDR_PAGE_SHIFT((hdr)))
102#define VM_MAP_HDR_PAGE_MASK(hdr) (VM_MAP_HDR_PAGE_SIZE((hdr)) - 1)
103
104
105#include <vm/vm_map_store_ll.h>
106#include <vm/vm_map_store_rb.h>
107
108/*
109 * SAVE_HINT_MAP_WRITE:
110 *
111 * Saves the specified entry as the hint for
112 * future lookups. write lock held on map,
113 * so no one else can be writing or looking
114 * until the lock is dropped.
115 */
116#define SAVE_HINT_MAP_WRITE(map, value) \
117 MACRO_BEGIN \
118 (map)->hint = (value); \
119 MACRO_END
120
121#define SAVE_HINT_HOLE_WRITE(map, value) \
122 MACRO_BEGIN \
123 (map)->hole_hint = (value); \
124 MACRO_END
125
126#define SKIP_RB_TREE 0xBAADC0D1
127
128extern void vm_map_store_init(
129 struct vm_map_header *header);
130
131extern bool vm_map_store_lookup_entry(
132 struct _vm_map *map,
133 vm_map_offset_t address,
134 struct vm_map_entry **entryp);
135
136extern void _vm_map_store_entry_link(
137 struct vm_map_header *header,
138 struct vm_map_entry *after_where,
139 struct vm_map_entry *entry);
140
141extern void vm_map_store_entry_link(
142 struct _vm_map *map,
143 struct vm_map_entry *after_where,
144 struct vm_map_entry *entry,
145 vm_map_kernel_flags_t vmk_flags);
146
147extern void _vm_map_store_entry_unlink(
148 struct vm_map_header *header,
149 struct vm_map_entry *entry,
150 bool check_permanent);
151
152extern void vm_map_store_entry_unlink(
153 struct _vm_map *map,
154 struct vm_map_entry *entry,
155 bool check_permanent);
156
157extern void vm_map_store_update_first_free(
158 struct _vm_map *map,
159 struct vm_map_entry *entry,
160 bool new_entry_creation);
161
162extern void vm_map_store_copy_reset(
163 struct vm_map_copy *copy_map,
164 struct vm_map_entry *entry);
165
166#if MACH_ASSERT
167extern bool first_free_is_valid_store(
168 struct _vm_map *map);
169#endif
170
171extern bool vm_map_store_has_RB_support(
172 struct vm_map_header *header);
173
174extern struct vm_map_entry *vm_map_store_find_space(
175 vm_map_t map,
176 vm_map_offset_t hint,
177 vm_map_offset_t limit,
178 bool backwards,
179 vm_map_offset_t guard_offset,
180 vm_map_size_t size,
181 vm_map_offset_t mask,
182 vm_map_offset_t *addr_out);
183
184#endif /* _VM_VM_MAP_STORE_H */
185