source: mainline/kernel/generic/include/mm/as.h@ 7be8d4d

Last change on this file since 7be8d4d was 7be8d4d, checked in by Jiri Svoboda <jiri@…>, 7 years ago

Replace B+tree with ordered dict. for used space

Replace the use of B+tree with ordered dictionary for used space,
adding a little bit more abstraction around used space tracking.
This allows performing TLB shootdown while shrinking an area
in a single sequence. A generic used_space_remove() is no longer
needed.
  • Property mode set to 100644
File size: 10.5 KB
Line 
1/*
2 * Copyright (c) 2010 Jakub Jermar
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup kernel_generic_mm
30 * @{
31 */
32/** @file
33 */
34
35#ifndef KERN_AS_H_
36#define KERN_AS_H_
37
38#include <typedefs.h>
39#include <abi/mm/as.h>
40#include <arch/mm/page.h>
41#include <arch/mm/as.h>
42#include <arch/mm/asid.h>
43#include <arch/istate.h>
44#include <synch/spinlock.h>
45#include <synch/mutex.h>
46#include <adt/list.h>
47#include <adt/odict.h>
48#include <lib/elf.h>
49#include <arch.h>
50#include <lib/refcount.h>
51
52#define AS CURRENT->as
53
54/**
55 * Defined to be true if user address space and kernel address space shadow each
56 * other.
57 *
58 */
59#define KERNEL_ADDRESS_SPACE_SHADOWED KERNEL_ADDRESS_SPACE_SHADOWED_ARCH
60
61#define KERNEL_ADDRESS_SPACE_START KERNEL_ADDRESS_SPACE_START_ARCH
62#define KERNEL_ADDRESS_SPACE_END KERNEL_ADDRESS_SPACE_END_ARCH
63#define USER_ADDRESS_SPACE_START USER_ADDRESS_SPACE_START_ARCH
64#define USER_ADDRESS_SPACE_END USER_ADDRESS_SPACE_END_ARCH
65
66/** Kernel address space. */
67#define FLAG_AS_KERNEL (1 << 0)
68
69/* Address space area attributes. */
70#define AS_AREA_ATTR_NONE 0
71#define AS_AREA_ATTR_PARTIAL 1 /**< Not fully initialized area. */
72
73/** The page fault was resolved by as_page_fault(). */
74#define AS_PF_OK 0
75
76/** The page fault was caused by memcpy_from_uspace() or memcpy_to_uspace(). */
77#define AS_PF_DEFER 1
78
79/** The page fault was not resolved by as_page_fault(). */
80#define AS_PF_FAULT 2
81
82/** The page fault was not resolved by as_page_fault(). Non-verbose version. */
83#define AS_PF_SILENT 3
84
85/** Address space structure.
86 *
87 * as_t contains the list of as_areas of userspace accessible
88 * pages for one or more tasks. Ranges of kernel memory pages are not
89 * supposed to figure in the list as they are shared by all tasks and
90 * set up during system initialization.
91 *
92 */
93typedef struct as {
94 /** Protected by asidlock. */
95 link_t inactive_as_with_asid_link;
96
97 /**
98 * Number of processors on which this
99 * address space is active. Protected by
100 * asidlock.
101 */
102 size_t cpu_refcount;
103
104 /** Address space identifier.
105 *
106 * Constant on architectures that do not
107 * support ASIDs. Protected by asidlock.
108 *
109 */
110 asid_t asid;
111
112 /** Number of references (i.e. tasks that reference this as). */
113 atomic_refcount_t refcount;
114
115 mutex_t lock;
116
117 /** Address space areas in this address space by base address.
118 *
119 * Members are of type as_area_t.
120 */
121 odict_t as_areas;
122
123 /** Non-generic content. */
124 as_genarch_t genarch;
125
126 /** Architecture specific content. */
127 as_arch_t arch;
128} as_t;
129
130typedef struct {
131 pte_t *(*page_table_create)(unsigned int);
132 void (*page_table_destroy)(pte_t *);
133 void (*page_table_lock)(as_t *, bool);
134 void (*page_table_unlock)(as_t *, bool);
135 bool (*page_table_locked)(as_t *);
136} as_operations_t;
137
138/** Single anonymous page mapping. */
139typedef struct {
140 /** Containing pagemap structure */
141 struct as_pagemap *pagemap;
142 /** Link to @c shinfo->pagemap ordered dictionary */
143 odlink_t lpagemap;
144 /** Virtual address */
145 uintptr_t vaddr;
146 /** Physical frame address */
147 uintptr_t frame;
148} as_page_mapping_t;
149
150/** Map of anonymous pages in a shared area. */
151typedef struct as_pagemap {
152 /**
153 * Dictionary ordered by virtual address. Members are of type
154 * as_page_mapping_t
155 */
156 odict_t map;
157} as_pagemap_t;
158
159/** Used space interval */
160typedef struct {
161 /** Containing used_space structure */
162 struct used_space *used_space;
163 /** Link to @c used_space->ivals */
164 odlink_t lused_space;
165 /** First page address */
166 uintptr_t page;
167 /** Count of pages */
168 size_t count;
169} used_space_ival_t;
170
171/** Map of used space in an address space area */
172typedef struct used_space {
173 /**
174 * Dictionary of intervals by start address.
175 * Members are of type @c used_space_ival_t.
176 */
177 odict_t ivals;
178 /** Total number of used pages. */
179 size_t pages;
180} used_space_t;
181
182/**
183 * This structure contains information associated with the shared address space
184 * area.
185 *
186 */
187typedef struct {
188 /** This lock must be acquired only when the as_area lock is held. */
189 mutex_t lock;
190 /** This structure can be deallocated if refcount drops to 0. */
191 size_t refcount;
192 /** True if the area has been ever shared. */
193 bool shared;
194
195 /** Complete map of anonymous pages of the shared area. */
196 as_pagemap_t pagemap;
197
198 /** Address space area backend. */
199 struct mem_backend *backend;
200 /** Address space area shared data. */
201 void *backend_shared_data;
202} share_info_t;
203
204/** Page fault access type. */
205typedef enum {
206 PF_ACCESS_READ,
207 PF_ACCESS_WRITE,
208 PF_ACCESS_EXEC,
209 PF_ACCESS_UNKNOWN
210} pf_access_t;
211
212struct mem_backend;
213
214/** Backend data stored in address space area. */
215typedef union mem_backend_data {
216 /* anon_backend members */
217 struct {
218 };
219
220 /** elf_backend members */
221 struct {
222 uintptr_t elf_base;
223 elf_header_t *elf;
224 elf_segment_header_t *segment;
225 };
226
227 /** phys_backend members */
228 struct {
229 uintptr_t base;
230 size_t frames;
231 bool anonymous;
232 };
233
234 /** user_backend members */
235 struct {
236 as_area_pager_info_t pager_info;
237 };
238
239} mem_backend_data_t;
240
241/** Address space area structure.
242 *
243 * Each as_area_t structure describes one contiguous area of virtual memory.
244 *
245 */
246typedef struct {
247 mutex_t lock;
248
249 /** Containing address space. */
250 as_t *as;
251
252 /** Link to @c as->as_areas */
253 odlink_t las_areas;
254
255 /** Memory flags. */
256 unsigned int flags;
257
258 /** Address space area attributes. */
259 unsigned int attributes;
260
261 /** Number of pages in the area. */
262 size_t pages;
263
264 /** Base address of this area. */
265 uintptr_t base;
266
267 /** Map of used space. */
268 used_space_t used_space;
269
270 /**
271 * If the address space area is shared. this is
272 * a reference to the share info structure.
273 */
274 share_info_t *sh_info;
275
276 /** Memory backend backing this address space area. */
277 struct mem_backend *backend;
278
279 /** Data to be used by the backend. */
280 mem_backend_data_t backend_data;
281} as_area_t;
282
283/** Address space area backend structure. */
284typedef struct mem_backend {
285 bool (*create)(as_area_t *);
286 bool (*resize)(as_area_t *, size_t);
287 void (*share)(as_area_t *);
288 void (*destroy)(as_area_t *);
289
290 bool (*is_resizable)(as_area_t *);
291 bool (*is_shareable)(as_area_t *);
292
293 int (*page_fault)(as_area_t *, uintptr_t, pf_access_t);
294 void (*frame_free)(as_area_t *, uintptr_t, uintptr_t);
295
296 bool (*create_shared_data)(as_area_t *);
297 void (*destroy_shared_data)(void *);
298} mem_backend_t;
299
300extern as_t *AS_KERNEL;
301
302extern as_operations_t *as_operations;
303extern list_t inactive_as_with_asid_list;
304
305extern void as_init(void);
306
307extern as_t *as_create(unsigned int);
308extern void as_hold(as_t *);
309extern void as_release(as_t *);
310extern void as_switch(as_t *, as_t *);
311extern int as_page_fault(uintptr_t, pf_access_t, istate_t *);
312
313extern as_area_t *as_area_create(as_t *, unsigned int, size_t, unsigned int,
314 mem_backend_t *, mem_backend_data_t *, uintptr_t *, uintptr_t);
315extern errno_t as_area_destroy(as_t *, uintptr_t);
316extern errno_t as_area_resize(as_t *, uintptr_t, size_t, unsigned int);
317extern errno_t as_area_share(as_t *, uintptr_t, size_t, as_t *, unsigned int,
318 uintptr_t *, uintptr_t);
319extern errno_t as_area_change_flags(as_t *, unsigned int, uintptr_t);
320extern as_area_t *as_area_first(as_t *);
321extern as_area_t *as_area_next(as_area_t *);
322
323extern void as_pagemap_initialize(as_pagemap_t *);
324extern void as_pagemap_finalize(as_pagemap_t *);
325extern as_page_mapping_t *as_pagemap_first(as_pagemap_t *);
326extern as_page_mapping_t *as_pagemap_next(as_page_mapping_t *);
327extern errno_t as_pagemap_find(as_pagemap_t *, uintptr_t, uintptr_t *);
328extern void as_pagemap_insert(as_pagemap_t *, uintptr_t, uintptr_t);
329extern void as_pagemap_remove(as_page_mapping_t *);
330
331extern unsigned int as_area_get_flags(as_area_t *);
332extern bool as_area_check_access(as_area_t *, pf_access_t);
333extern size_t as_area_get_size(uintptr_t);
334extern used_space_ival_t *used_space_first(used_space_t *);
335extern used_space_ival_t *used_space_next(used_space_ival_t *);
336extern used_space_ival_t *used_space_find_gteq(used_space_t *, uintptr_t);
337extern bool used_space_insert(used_space_t *, uintptr_t, size_t);
338
339/* Interface to be implemented by architectures. */
340
341#ifndef as_constructor_arch
342extern errno_t as_constructor_arch(as_t *, unsigned int);
343#endif /* !def as_constructor_arch */
344
345#ifndef as_destructor_arch
346extern int as_destructor_arch(as_t *);
347#endif /* !def as_destructor_arch */
348
349#ifndef as_create_arch
350extern errno_t as_create_arch(as_t *, unsigned int);
351#endif /* !def as_create_arch */
352
353#ifndef as_install_arch
354extern void as_install_arch(as_t *);
355#endif /* !def as_install_arch */
356
357#ifndef as_deinstall_arch
358extern void as_deinstall_arch(as_t *);
359#endif /* !def as_deinstall_arch */
360
361/* Backend declarations and functions. */
362extern mem_backend_t anon_backend;
363extern mem_backend_t elf_backend;
364extern mem_backend_t phys_backend;
365extern mem_backend_t user_backend;
366
367/* Address space area related syscalls. */
368extern sysarg_t sys_as_area_create(uintptr_t, size_t, unsigned int, uintptr_t,
369 as_area_pager_info_t *);
370extern sys_errno_t sys_as_area_resize(uintptr_t, size_t, unsigned int);
371extern sys_errno_t sys_as_area_change_flags(uintptr_t, unsigned int);
372extern sys_errno_t sys_as_area_get_info(uintptr_t, as_area_info_t *);
373extern sys_errno_t sys_as_area_destroy(uintptr_t);
374
375/* Introspection functions. */
376extern as_area_info_t *as_get_area_info(as_t *, size_t *);
377extern void as_print(as_t *);
378
379#endif
380
381/** @}
382 */
Note: See TracBrowser for help on using the repository browser.