Subversion Repositories HelenOS-historic

Rev

Rev 1594 | Rev 1705 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1594 Rev 1702
1 
/*
 1 
/*
2 
 * Copyright (C) 2001-2006 Jakub Jermar
 2 
 * Copyright (C) 2001-2006 Jakub Jermar
3 
 * All rights reserved.
 3 
 * All rights reserved.
4 
 *
 4 
 *
5 
 * Redistribution and use in source and binary forms, with or without
 5 
 * Redistribution and use in source and binary forms, with or without
6 
 * modification, are permitted provided that the following conditions
 6 
 * modification, are permitted provided that the following conditions
7 
 * are met:
 7 
 * are met:
8 
 *
 8 
 *
9 
 * - Redistributions of source code must retain the above copyright
 9 
 * - Redistributions of source code must retain the above copyright
10 
 *   notice, this list of conditions and the following disclaimer.
 10 
 *   notice, this list of conditions and the following disclaimer.
11 
 * - Redistributions in binary form must reproduce the above copyright
 11 
 * - Redistributions in binary form must reproduce the above copyright
12 
 *   notice, this list of conditions and the following disclaimer in the
 12 
 *   notice, this list of conditions and the following disclaimer in the
13 
 *   documentation and/or other materials provided with the distribution.
 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
 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.
 15 
 *   derived from this software without specific prior written permission.
16 
 *
 16 
 *
17 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 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
 18 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 19 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 20 
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 21 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 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
 23 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 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
 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.
 26 
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
 */
 27 
 */
28 
 
 28 
 
- 
 
 29 
 /** @defgroup mm Memory management
- 
 
 30 
  * @ingroup kernel
- 
 
 31 
  * @{
- 
 
 32 
  * @}
- 
 
 33 
  */
- 
 
 34 
 
- 
 
 35 
 /** @addtogroup genericmm generic
- 
 
 36 
  * @ingroup mm
- 
 
 37 
 * @{
- 
 
 38 
 */
- 
 
 39 
 
29 
/**
 40 
/**
30 
 * @file    as.c
 41 
 * @file
31 
 * @brief   Address space related functions.
 42 
 * @brief   Address space related functions.
32 
 *
 43 
 *
33 
 * This file contains address space manipulation functions.
 44 
 * This file contains address space manipulation functions.
34 
 * Roughly speaking, this is a higher-level client of
 45 
 * Roughly speaking, this is a higher-level client of
35 
 * Virtual Address Translation (VAT) subsystem.
 46 
 * Virtual Address Translation (VAT) subsystem.
36 
 *
 47 
 *
37 
 * Functionality provided by this file allows one to
 48 
 * Functionality provided by this file allows one to
38 
 * create address space and create, resize and share
 49 
 * create address space and create, resize and share
39 
 * address space areas.
 50 
 * address space areas.
40 
 *
 51 
 *
41 
 * @see page.c
 52 
 * @see page.c
42 
 *
 53 
 *
43 
 */
 54 
 */
44 
 
 55 
 
45 
#include <mm/as.h>
 56 
#include <mm/as.h>
46 
#include <arch/mm/as.h>
 57 
#include <arch/mm/as.h>
47 
#include <mm/page.h>
 58 
#include <mm/page.h>
48 
#include <mm/frame.h>
 59 
#include <mm/frame.h>
49 
#include <mm/slab.h>
 60 
#include <mm/slab.h>
50 
#include <mm/tlb.h>
 61 
#include <mm/tlb.h>
51 
#include <arch/mm/page.h>
 62 
#include <arch/mm/page.h>
52 
#include <genarch/mm/page_pt.h>
 63 
#include <genarch/mm/page_pt.h>
53 
#include <genarch/mm/page_ht.h>
 64 
#include <genarch/mm/page_ht.h>
54 
#include <mm/asid.h>
 65 
#include <mm/asid.h>
55 
#include <arch/mm/asid.h>
 66 
#include <arch/mm/asid.h>
56 
#include <synch/spinlock.h>
 67 
#include <synch/spinlock.h>
57 
#include <synch/mutex.h>
 68 
#include <synch/mutex.h>
58 
#include <adt/list.h>
 69 
#include <adt/list.h>
59 
#include <adt/btree.h>
 70 
#include <adt/btree.h>
60 
#include <proc/task.h>
 71 
#include <proc/task.h>
61 
#include <proc/thread.h>
 72 
#include <proc/thread.h>
62 
#include <arch/asm.h>
 73 
#include <arch/asm.h>
63 
#include <panic.h>
 74 
#include <panic.h>
64 
#include <debug.h>
 75 
#include <debug.h>
65 
#include <print.h>
 76 
#include <print.h>
66 
#include <memstr.h>
 77 
#include <memstr.h>
67 
#include <macros.h>
 78 
#include <macros.h>
68 
#include <arch.h>
 79 
#include <arch.h>
69 
#include <errno.h>
 80 
#include <errno.h>
70 
#include <config.h>
 81 
#include <config.h>
71 
#include <align.h>
 82 
#include <align.h>
72 
#include <arch/types.h>
 83 
#include <arch/types.h>
73 
#include <typedefs.h>
 84 
#include <typedefs.h>
74 
#include <syscall/copy.h>
 85 
#include <syscall/copy.h>
75 
#include <arch/interrupt.h>
 86 
#include <arch/interrupt.h>
76 
 
 87 
 
77 
as_operations_t *as_operations = NULL;
 88 
as_operations_t *as_operations = NULL;
78 
 
 89 
 
79 
/** This lock protects inactive_as_with_asid_head list. It must be acquired before as_t mutex. */
 90 
/** This lock protects inactive_as_with_asid_head list. It must be acquired before as_t mutex. */
80 
SPINLOCK_INITIALIZE(inactive_as_with_asid_lock);
 91 
SPINLOCK_INITIALIZE(inactive_as_with_asid_lock);
81 
 
 92 
 
82 
/**
 93 
/**
83 
 * This list contains address spaces that are not active on any
 94 
 * This list contains address spaces that are not active on any
84 
 * processor and that have valid ASID.
 95 
 * processor and that have valid ASID.
85 
 */
 96 
 */
86 
LIST_INITIALIZE(inactive_as_with_asid_head);
 97 
LIST_INITIALIZE(inactive_as_with_asid_head);
87 
 
 98 
 
88 
/** Kernel address space. */
 99 
/** Kernel address space. */
89 
as_t *AS_KERNEL = NULL;
 100 
as_t *AS_KERNEL = NULL;
90 
 
 101 
 
91 
static int area_flags_to_page_flags(int aflags);
 102 
static int area_flags_to_page_flags(int aflags);
92 
static as_area_t *find_area_and_lock(as_t *as, __address va);
 103 
static as_area_t *find_area_and_lock(as_t *as, __address va);
93 
static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area);
 104 
static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area);
94 
static void sh_info_remove_reference(share_info_t *sh_info);
 105 
static void sh_info_remove_reference(share_info_t *sh_info);
95 
 
 106 
 
96 
/** Initialize address space subsystem. */
 107 
/** Initialize address space subsystem. */
97 
void as_init(void)
 108 
void as_init(void)
98 
{
 109 
{
99 
    as_arch_init();
 110 
    as_arch_init();
100 
    AS_KERNEL = as_create(FLAG_AS_KERNEL);
 111 
    AS_KERNEL = as_create(FLAG_AS_KERNEL);
101 
    if (!AS_KERNEL)
 112 
    if (!AS_KERNEL)
102 
        panic("can't create kernel address space\n");
 113 
        panic("can't create kernel address space\n");
103 
   
 114 
   
104 
}
 115 
}
105 
 
 116 
 
106 
/** Create address space.
 117 
/** Create address space.
107 
 *
 118 
 *
108 
 * @param flags Flags that influence way in wich the address space is created.
 119 
 * @param flags Flags that influence way in wich the address space is created.
109 
 */
 120 
 */
110 
as_t *as_create(int flags)
 121 
as_t *as_create(int flags)
111 
{
 122 
{
112 
    as_t *as;
 123 
    as_t *as;
113 
 
 124 
 
114 
    as = (as_t *) malloc(sizeof(as_t), 0);
 125 
    as = (as_t *) malloc(sizeof(as_t), 0);
115 
    link_initialize(&as->inactive_as_with_asid_link);
 126 
    link_initialize(&as->inactive_as_with_asid_link);
116 
    mutex_initialize(&as->lock);
 127 
    mutex_initialize(&as->lock);
117 
    btree_create(&as->as_area_btree);
 128 
    btree_create(&as->as_area_btree);
118 
   
 129 
   
119 
    if (flags & FLAG_AS_KERNEL)
 130 
    if (flags & FLAG_AS_KERNEL)
120 
        as->asid = ASID_KERNEL;
 131 
        as->asid = ASID_KERNEL;
121 
    else
 132 
    else
122 
        as->asid = ASID_INVALID;
 133 
        as->asid = ASID_INVALID;
123 
   
 134 
   
124 
    as->refcount = 0;
 135 
    as->refcount = 0;
125 
    as->cpu_refcount = 0;
 136 
    as->cpu_refcount = 0;
126 
    as->page_table = page_table_create(flags);
 137 
    as->page_table = page_table_create(flags);
127 
 
 138 
 
128 
    return as;
 139 
    return as;
129 
}
 140 
}
130 
 
 141 
 
131 
/** Destroy adress space.
 142 
/** Destroy adress space.
132 
 *
 143 
 *
133 
 * When there are no tasks referencing this address space (i.e. its refcount is zero),
 144 
 * When there are no tasks referencing this address space (i.e. its refcount is zero),
134 
 * the address space can be destroyed.
 145 
 * the address space can be destroyed.
135 
 */
 146 
 */
136 
void as_destroy(as_t *as)
 147 
void as_destroy(as_t *as)
137 
{
 148 
{
138 
    ipl_t ipl;
 149 
    ipl_t ipl;
139 
    bool cond;
 150 
    bool cond;
140 
 
 151 
 
141 
    ASSERT(as->refcount == 0);
 152 
    ASSERT(as->refcount == 0);
142 
   
 153 
   
143 
    /*
 154 
    /*
144 
     * Since there is no reference to this area,
 155 
     * Since there is no reference to this area,
145 
     * it is safe not to lock its mutex.
 156 
     * it is safe not to lock its mutex.
146 
     */
 157 
     */
147 
    ipl = interrupts_disable();
 158 
    ipl = interrupts_disable();
148 
    spinlock_lock(&inactive_as_with_asid_lock);
 159 
    spinlock_lock(&inactive_as_with_asid_lock);
149 
    if (as->asid != ASID_INVALID && as != AS_KERNEL) {
 160 
    if (as->asid != ASID_INVALID && as != AS_KERNEL) {
150 
        if (as != AS && as->cpu_refcount == 0)
 161 
        if (as != AS && as->cpu_refcount == 0)
151 
            list_remove(&as->inactive_as_with_asid_link);
 162 
            list_remove(&as->inactive_as_with_asid_link);
152 
        asid_put(as->asid);
 163 
        asid_put(as->asid);
153 
    }
 164 
    }
154 
    spinlock_unlock(&inactive_as_with_asid_lock);
 165 
    spinlock_unlock(&inactive_as_with_asid_lock);
155 
 
 166 
 
156 
    /*
 167 
    /*
157 
     * Destroy address space areas of the address space.
 168 
     * Destroy address space areas of the address space.
158 
     * The B+tee must be walked carefully because it is
 169 
     * The B+tee must be walked carefully because it is
159 
     * also being destroyed.
 170 
     * also being destroyed.
160 
     */
 171 
     */
161 
    for (cond = true; cond; ) {
 172 
    for (cond = true; cond; ) {
162 
        btree_node_t *node;
 173 
        btree_node_t *node;
163 
 
 174 
 
164 
        ASSERT(!list_empty(&as->as_area_btree.leaf_head));
 175 
        ASSERT(!list_empty(&as->as_area_btree.leaf_head));
165 
        node = list_get_instance(as->as_area_btree.leaf_head.next, btree_node_t, leaf_link);
 176 
        node = list_get_instance(as->as_area_btree.leaf_head.next, btree_node_t, leaf_link);
166 
 
 177 
 
167 
        if ((cond = node->keys)) {
 178 
        if ((cond = node->keys)) {
168 
            as_area_destroy(as, node->key[0]);
 179 
            as_area_destroy(as, node->key[0]);
169 
        }
 180 
        }
170 
    }
 181 
    }
171 
 
 182 
 
172 
    btree_destroy(&as->as_area_btree);
 183 
    btree_destroy(&as->as_area_btree);
173 
    page_table_destroy(as->page_table);
 184 
    page_table_destroy(as->page_table);
174 
 
 185 
 
175 
    interrupts_restore(ipl);
 186 
    interrupts_restore(ipl);
176 
   
 187 
   
177 
    free(as);
 188 
    free(as);
178 
}
 189 
}
179 
 
 190 
 
180 
/** Create address space area of common attributes.
 191 
/** Create address space area of common attributes.
181 
 *
 192 
 *
182 
 * The created address space area is added to the target address space.
 193 
 * The created address space area is added to the target address space.
183 
 *
 194 
 *
184 
 * @param as Target address space.
 195 
 * @param as Target address space.
185 
 * @param flags Flags of the area memory.
 196 
 * @param flags Flags of the area memory.
186 
 * @param size Size of area.
 197 
 * @param size Size of area.
187 
 * @param base Base address of area.
 198 
 * @param base Base address of area.
188 
 * @param attrs Attributes of the area.
 199 
 * @param attrs Attributes of the area.
189 
 * @param backend Address space area backend. NULL if no backend is used.
 200 
 * @param backend Address space area backend. NULL if no backend is used.
190 
 * @param backend_data NULL or a pointer to an array holding two void *.
 201 
 * @param backend_data NULL or a pointer to an array holding two void *.
191 
 *
 202 
 *
192 
 * @return Address space area on success or NULL on failure.
 203 
 * @return Address space area on success or NULL on failure.
193 
 */
 204 
 */
194 
as_area_t *as_area_create(as_t *as, int flags, size_t size, __address base, int attrs,
 205 
as_area_t *as_area_create(as_t *as, int flags, size_t size, __address base, int attrs,
195 
           mem_backend_t *backend, mem_backend_data_t *backend_data)
 206 
           mem_backend_t *backend, mem_backend_data_t *backend_data)
196 
{
 207 
{
197 
    ipl_t ipl;
 208 
    ipl_t ipl;
198 
    as_area_t *a;
 209 
    as_area_t *a;
199 
   
 210 
   
200 
    if (base % PAGE_SIZE)
 211 
    if (base % PAGE_SIZE)
201 
        return NULL;
 212 
        return NULL;
202 
 
 213 
 
203 
    if (!size)
 214 
    if (!size)
204 
        return NULL;
 215 
        return NULL;
205 
 
 216 
 
206 
    /* Writeable executable areas are not supported. */
 217 
    /* Writeable executable areas are not supported. */
207 
    if ((flags & AS_AREA_EXEC) && (flags & AS_AREA_WRITE))
 218 
    if ((flags & AS_AREA_EXEC) && (flags & AS_AREA_WRITE))
208 
        return NULL;
 219 
        return NULL;
209 
   
 220 
   
210 
    ipl = interrupts_disable();
 221 
    ipl = interrupts_disable();
211 
    mutex_lock(&as->lock);
 222 
    mutex_lock(&as->lock);
212 
   
 223 
   
213 
    if (!check_area_conflicts(as, base, size, NULL)) {
 224 
    if (!check_area_conflicts(as, base, size, NULL)) {
214 
        mutex_unlock(&as->lock);
 225 
        mutex_unlock(&as->lock);
215 
        interrupts_restore(ipl);
 226 
        interrupts_restore(ipl);
216 
        return NULL;
 227 
        return NULL;
217 
    }
 228 
    }
218 
   
 229 
   
219 
    a = (as_area_t *) malloc(sizeof(as_area_t), 0);
 230 
    a = (as_area_t *) malloc(sizeof(as_area_t), 0);
220 
 
 231 
 
221 
    mutex_initialize(&a->lock);
 232 
    mutex_initialize(&a->lock);
222 
   
 233 
   
223 
    a->as = as;
 234 
    a->as = as;
224 
    a->flags = flags;
 235 
    a->flags = flags;
225 
    a->attributes = attrs;
 236 
    a->attributes = attrs;
226 
    a->pages = SIZE2FRAMES(size);
 237 
    a->pages = SIZE2FRAMES(size);
227 
    a->base = base;
 238 
    a->base = base;
228 
    a->sh_info = NULL;
 239 
    a->sh_info = NULL;
229 
    a->backend = backend;
 240 
    a->backend = backend;
230 
    if (backend_data)
 241 
    if (backend_data)
231 
        a->backend_data = *backend_data;
 242 
        a->backend_data = *backend_data;
232 
    else
 243 
    else
233 
        memsetb((__address) &a->backend_data, sizeof(a->backend_data), 0);
 244 
        memsetb((__address) &a->backend_data, sizeof(a->backend_data), 0);
234 
 
 245 
 
235 
    btree_create(&a->used_space);
 246 
    btree_create(&a->used_space);
236 
   
 247 
   
237 
    btree_insert(&as->as_area_btree, base, (void *) a, NULL);
 248 
    btree_insert(&as->as_area_btree, base, (void *) a, NULL);
238 
 
 249 
 
239 
    mutex_unlock(&as->lock);
 250 
    mutex_unlock(&as->lock);
240 
    interrupts_restore(ipl);
 251 
    interrupts_restore(ipl);
241 
 
 252 
 
242 
    return a;
 253 
    return a;
243 
}
 254 
}
244 
 
 255 
 
245 
/** Find address space area and change it.
 256 
/** Find address space area and change it.
246 
 *
 257 
 *
247 
 * @param as Address space.
 258 
 * @param as Address space.
248 
 * @param address Virtual address belonging to the area to be changed. Must be page-aligned.
 259 
 * @param address Virtual address belonging to the area to be changed. Must be page-aligned.
249 
 * @param size New size of the virtual memory block starting at address.
 260 
 * @param size New size of the virtual memory block starting at address.
250 
 * @param flags Flags influencing the remap operation. Currently unused.
 261 
 * @param flags Flags influencing the remap operation. Currently unused.
251 
 *
 262 
 *
252 
 * @return Zero on success or a value from @ref errno.h otherwise.
 263 
 * @return Zero on success or a value from @ref errno.h otherwise.
253 
 */
 264 
 */
254 
int as_area_resize(as_t *as, __address address, size_t size, int flags)
 265 
int as_area_resize(as_t *as, __address address, size_t size, int flags)
255 
{
 266 
{
256 
    as_area_t *area;
 267 
    as_area_t *area;
257 
    ipl_t ipl;
 268 
    ipl_t ipl;
258 
    size_t pages;
 269 
    size_t pages;
259 
   
 270 
   
260 
    ipl = interrupts_disable();
 271 
    ipl = interrupts_disable();
261 
    mutex_lock(&as->lock);
 272 
    mutex_lock(&as->lock);
262 
   
 273 
   
263 
    /*
 274 
    /*
264 
     * Locate the area.
 275 
     * Locate the area.
265 
     */
 276 
     */
266 
    area = find_area_and_lock(as, address);
 277 
    area = find_area_and_lock(as, address);
267 
    if (!area) {
 278 
    if (!area) {
268 
        mutex_unlock(&as->lock);
 279 
        mutex_unlock(&as->lock);
269 
        interrupts_restore(ipl);
 280 
        interrupts_restore(ipl);
270 
        return ENOENT;
 281 
        return ENOENT;
271 
    }
 282 
    }
272 
 
 283 
 
273 
    if (area->backend == &phys_backend) {
 284 
    if (area->backend == &phys_backend) {
274 
        /*
 285 
        /*
275 
         * Remapping of address space areas associated
 286 
         * Remapping of address space areas associated
276 
         * with memory mapped devices is not supported.
 287 
         * with memory mapped devices is not supported.
277 
         */
 288 
         */
278 
        mutex_unlock(&area->lock);
 289 
        mutex_unlock(&area->lock);
279 
        mutex_unlock(&as->lock);
 290 
        mutex_unlock(&as->lock);
280 
        interrupts_restore(ipl);
 291 
        interrupts_restore(ipl);
281 
        return ENOTSUP;
 292 
        return ENOTSUP;
282 
    }
 293 
    }
283 
    if (area->sh_info) {
 294 
    if (area->sh_info) {
284 
        /*
 295 
        /*
285 
         * Remapping of shared address space areas
 296 
         * Remapping of shared address space areas
286 
         * is not supported.
 297 
         * is not supported.
287 
         */
 298 
         */
288 
        mutex_unlock(&area->lock);
 299 
        mutex_unlock(&area->lock);
289 
        mutex_unlock(&as->lock);
 300 
        mutex_unlock(&as->lock);
290 
        interrupts_restore(ipl);
 301 
        interrupts_restore(ipl);
291 
        return ENOTSUP;
 302 
        return ENOTSUP;
292 
    }
 303 
    }
293 
 
 304 
 
294 
    pages = SIZE2FRAMES((address - area->base) + size);
 305 
    pages = SIZE2FRAMES((address - area->base) + size);
295 
    if (!pages) {
 306 
    if (!pages) {
296 
        /*
 307 
        /*
297 
         * Zero size address space areas are not allowed.
 308 
         * Zero size address space areas are not allowed.
298 
         */
 309 
         */
299 
        mutex_unlock(&area->lock);
 310 
        mutex_unlock(&area->lock);
300 
        mutex_unlock(&as->lock);
 311 
        mutex_unlock(&as->lock);
301 
        interrupts_restore(ipl);
 312 
        interrupts_restore(ipl);
302 
        return EPERM;
 313 
        return EPERM;
303 
    }
 314 
    }
304 
   
 315 
   
305 
    if (pages < area->pages) {
 316 
    if (pages < area->pages) {
306 
        bool cond;
 317 
        bool cond;
307 
        __address start_free = area->base + pages*PAGE_SIZE;
 318 
        __address start_free = area->base + pages*PAGE_SIZE;
308 
 
 319 
 
309 
        /*
 320 
        /*
310 
         * Shrinking the area.
 321 
         * Shrinking the area.
311 
         * No need to check for overlaps.
 322 
         * No need to check for overlaps.
312 
         */
 323 
         */
313 
 
 324 
 
314 
        /*
 325 
        /*
315 
         * Start TLB shootdown sequence.
 326 
         * Start TLB shootdown sequence.
316 
         */
 327 
         */
317 
        tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
 328 
        tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
318 
 
 329 
 
319 
        /*
 330 
        /*
320 
         * Remove frames belonging to used space starting from
 331 
         * Remove frames belonging to used space starting from
321 
         * the highest addresses downwards until an overlap with
 332 
         * the highest addresses downwards until an overlap with
322 
         * the resized address space area is found. Note that this
 333 
         * the resized address space area is found. Note that this
323 
         * is also the right way to remove part of the used_space
 334 
         * is also the right way to remove part of the used_space
324 
         * B+tree leaf list.
 335 
         * B+tree leaf list.
325 
         */    
 336 
         */    
326 
        for (cond = true; cond;) {
 337 
        for (cond = true; cond;) {
327 
            btree_node_t *node;
 338 
            btree_node_t *node;
328 
       
 339 
       
329 
            ASSERT(!list_empty(&area->used_space.leaf_head));
 340 
            ASSERT(!list_empty(&area->used_space.leaf_head));
330 
            node = list_get_instance(area->used_space.leaf_head.prev, btree_node_t, leaf_link);
 341 
            node = list_get_instance(area->used_space.leaf_head.prev, btree_node_t, leaf_link);
331 
            if ((cond = (bool) node->keys)) {
 342 
            if ((cond = (bool) node->keys)) {
332 
                __address b = node->key[node->keys - 1];
 343 
                __address b = node->key[node->keys - 1];
333 
                count_t c = (count_t) node->value[node->keys - 1];
 344 
                count_t c = (count_t) node->value[node->keys - 1];
334 
                int i = 0;
 345 
                int i = 0;
335 
           
 346 
           
336 
                if (overlaps(b, c*PAGE_SIZE, area->base, pages*PAGE_SIZE)) {
 347 
                if (overlaps(b, c*PAGE_SIZE, area->base, pages*PAGE_SIZE)) {
337 
                   
 348 
                   
338 
                    if (b + c*PAGE_SIZE <= start_free) {
 349 
                    if (b + c*PAGE_SIZE <= start_free) {
339 
                        /*
 350 
                        /*
340 
                         * The whole interval fits completely
 351 
                         * The whole interval fits completely
341 
                         * in the resized address space area.
 352 
                         * in the resized address space area.
342 
                         */
 353 
                         */
343 
                        break;
 354 
                        break;
344 
                    }
 355 
                    }
345 
       
 356 
       
346 
                    /*
 357 
                    /*
347 
                     * Part of the interval corresponding to b and c
 358 
                     * Part of the interval corresponding to b and c
348 
                     * overlaps with the resized address space area.
 359 
                     * overlaps with the resized address space area.
349 
                     */
 360 
                     */
350 
       
 361 
       
351 
                    cond = false;   /* we are almost done */
 362 
                    cond = false;   /* we are almost done */
352 
                    i = (start_free - b) >> PAGE_WIDTH;
 363 
                    i = (start_free - b) >> PAGE_WIDTH;
353 
                    if (!used_space_remove(area, start_free, c - i))
 364 
                    if (!used_space_remove(area, start_free, c - i))
354 
                        panic("Could not remove used space.");
 365 
                        panic("Could not remove used space.");
355 
                } else {
 366 
                } else {
356 
                    /*
 367 
                    /*
357 
                     * The interval of used space can be completely removed.
 368 
                     * The interval of used space can be completely removed.
358 
                     */
 369 
                     */
359 
                    if (!used_space_remove(area, b, c))
 370 
                    if (!used_space_remove(area, b, c))
360 
                        panic("Could not remove used space.\n");
 371 
                        panic("Could not remove used space.\n");
361 
                }
 372 
                }
362 
           
 373 
           
363 
                for (; i < c; i++) {
 374 
                for (; i < c; i++) {
364 
                    pte_t *pte;
 375 
                    pte_t *pte;
365 
           
 376 
           
366 
                    page_table_lock(as, false);
 377 
                    page_table_lock(as, false);
367 
                    pte = page_mapping_find(as, b + i*PAGE_SIZE);
 378 
                    pte = page_mapping_find(as, b + i*PAGE_SIZE);
368 
                    ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte));
 379 
                    ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte));
369 
                    if (area->backend && area->backend->frame_free) {
 380 
                    if (area->backend && area->backend->frame_free) {
370 
                        area->backend->frame_free(area,
 381 
                        area->backend->frame_free(area,
371 
                            b + i*PAGE_SIZE, PTE_GET_FRAME(pte));
 382 
                            b + i*PAGE_SIZE, PTE_GET_FRAME(pte));
372 
                    }
 383 
                    }
373 
                    page_mapping_remove(as, b + i*PAGE_SIZE);
 384 
                    page_mapping_remove(as, b + i*PAGE_SIZE);
374 
                    page_table_unlock(as, false);
 385 
                    page_table_unlock(as, false);
375 
                }
 386 
                }
376 
            }
 387 
            }
377 
        }
 388 
        }
378 
 
 389 
 
379 
        /*
 390 
        /*
380 
         * Finish TLB shootdown sequence.
 391 
         * Finish TLB shootdown sequence.
381 
         */
 392 
         */
382 
        tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
 393 
        tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
383 
        tlb_shootdown_finalize();
 394 
        tlb_shootdown_finalize();
384 
    } else {
 395 
    } else {
385 
        /*
 396 
        /*
386 
         * Growing the area.
 397 
         * Growing the area.
387 
         * Check for overlaps with other address space areas.
 398 
         * Check for overlaps with other address space areas.
388 
         */
 399 
         */
389 
        if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
 400 
        if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
390 
            mutex_unlock(&area->lock);
 401 
            mutex_unlock(&area->lock);
391 
            mutex_unlock(&as->lock);       
 402 
            mutex_unlock(&as->lock);       
392 
            interrupts_restore(ipl);
 403 
            interrupts_restore(ipl);
393 
            return EADDRNOTAVAIL;
 404 
            return EADDRNOTAVAIL;
394 
        }
 405 
        }
395 
    }
 406 
    }
396 
 
 407 
 
397 
    area->pages = pages;
 408 
    area->pages = pages;
398 
   
 409 
   
399 
    mutex_unlock(&area->lock);
 410 
    mutex_unlock(&area->lock);
400 
    mutex_unlock(&as->lock);
 411 
    mutex_unlock(&as->lock);
401 
    interrupts_restore(ipl);
 412 
    interrupts_restore(ipl);
402 
 
 413 
 
403 
    return 0;
 414 
    return 0;
404 
}
 415 
}
405 
 
 416 
 
406 
/** Destroy address space area.
 417 
/** Destroy address space area.
407 
 *
 418 
 *
408 
 * @param as Address space.
 419 
 * @param as Address space.
409 
 * @param address Address withing the area to be deleted.
 420 
 * @param address Address withing the area to be deleted.
410 
 *
 421 
 *
411 
 * @return Zero on success or a value from @ref errno.h on failure.
 422 
 * @return Zero on success or a value from @ref errno.h on failure.
412 
 */
 423 
 */
413 
int as_area_destroy(as_t *as, __address address)
 424 
int as_area_destroy(as_t *as, __address address)
414 
{
 425 
{
415 
    as_area_t *area;
 426 
    as_area_t *area;
416 
    __address base;
 427 
    __address base;
417 
    link_t *cur;
 428 
    link_t *cur;
418 
    ipl_t ipl;
 429 
    ipl_t ipl;
419 
 
 430 
 
420 
    ipl = interrupts_disable();
 431 
    ipl = interrupts_disable();
421 
    mutex_lock(&as->lock);
 432 
    mutex_lock(&as->lock);
422 
 
 433 
 
423 
    area = find_area_and_lock(as, address);
 434 
    area = find_area_and_lock(as, address);
424 
    if (!area) {
 435 
    if (!area) {
425 
        mutex_unlock(&as->lock);
 436 
        mutex_unlock(&as->lock);
426 
        interrupts_restore(ipl);
 437 
        interrupts_restore(ipl);
427 
        return ENOENT;
 438 
        return ENOENT;
428 
    }
 439 
    }
429 
 
 440 
 
430 
    base = area->base;
 441 
    base = area->base;
431 
 
 442 
 
432 
    /*
 443 
    /*
433 
     * Start TLB shootdown sequence.
 444 
     * Start TLB shootdown sequence.
434 
     */
 445 
     */
435 
    tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base, area->pages);
 446 
    tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base, area->pages);
436 
 
 447 
 
437 
    /*
 448 
    /*
438 
     * Visit only the pages mapped by used_space B+tree.
 449 
     * Visit only the pages mapped by used_space B+tree.
439 
     */
 450 
     */
440 
    for (cur = area->used_space.leaf_head.next; cur != &area->used_space.leaf_head; cur = cur->next) {
 451 
    for (cur = area->used_space.leaf_head.next; cur != &area->used_space.leaf_head; cur = cur->next) {
441 
        btree_node_t *node;
 452 
        btree_node_t *node;
442 
        int i;
 453 
        int i;
443 
       
 454 
       
444 
        node = list_get_instance(cur, btree_node_t, leaf_link);
 455 
        node = list_get_instance(cur, btree_node_t, leaf_link);
445 
        for (i = 0; i < node->keys; i++) {
 456 
        for (i = 0; i < node->keys; i++) {
446 
            __address b = node->key[i];
 457 
            __address b = node->key[i];
447 
            count_t j;
 458 
            count_t j;
448 
            pte_t *pte;
 459 
            pte_t *pte;
449 
           
 460 
           
450 
            for (j = 0; j < (count_t) node->value[i]; j++) {
 461 
            for (j = 0; j < (count_t) node->value[i]; j++) {
451 
                page_table_lock(as, false);
 462 
                page_table_lock(as, false);
452 
                pte = page_mapping_find(as, b + j*PAGE_SIZE);
 463 
                pte = page_mapping_find(as, b + j*PAGE_SIZE);
453 
                ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte));
 464 
                ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte));
454 
                if (area->backend && area->backend->frame_free) {
 465 
                if (area->backend && area->backend->frame_free) {
455 
                    area->backend->frame_free(area,
 466 
                    area->backend->frame_free(area,
456 
                        b + j*PAGE_SIZE, PTE_GET_FRAME(pte));
 467 
                        b + j*PAGE_SIZE, PTE_GET_FRAME(pte));
457 
                }
 468 
                }
458 
                page_mapping_remove(as, b + j*PAGE_SIZE);
 469 
                page_mapping_remove(as, b + j*PAGE_SIZE);
459 
                page_table_unlock(as, false);
 470 
                page_table_unlock(as, false);
460 
            }
 471 
            }
461 
        }
 472 
        }
462 
    }
 473 
    }
463 
 
 474 
 
464 
    /*
 475 
    /*
465 
     * Finish TLB shootdown sequence.
 476 
     * Finish TLB shootdown sequence.
466 
     */
 477 
     */
467 
    tlb_invalidate_pages(AS->asid, area->base, area->pages);
 478 
    tlb_invalidate_pages(AS->asid, area->base, area->pages);
468 
    tlb_shootdown_finalize();
 479 
    tlb_shootdown_finalize();
469 
   
 480 
   
470 
    btree_destroy(&area->used_space);
 481 
    btree_destroy(&area->used_space);
471 
 
 482 
 
472 
    area->attributes |= AS_AREA_ATTR_PARTIAL;
 483 
    area->attributes |= AS_AREA_ATTR_PARTIAL;
473 
   
 484 
   
474 
    if (area->sh_info)
 485 
    if (area->sh_info)
475 
        sh_info_remove_reference(area->sh_info);
 486 
        sh_info_remove_reference(area->sh_info);
476 
       
 487 
       
477 
    mutex_unlock(&area->lock);
 488 
    mutex_unlock(&area->lock);
478 
 
 489 
 
479 
    /*
 490 
    /*
480 
     * Remove the empty area from address space.
 491 
     * Remove the empty area from address space.
481 
     */
 492 
     */
482 
    btree_remove(&AS->as_area_btree, base, NULL);
 493 
    btree_remove(&AS->as_area_btree, base, NULL);
483 
   
 494 
   
484 
    free(area);
 495 
    free(area);
485 
   
 496 
   
486 
    mutex_unlock(&AS->lock);
 497 
    mutex_unlock(&AS->lock);
487 
    interrupts_restore(ipl);
 498 
    interrupts_restore(ipl);
488 
    return 0;
 499 
    return 0;
489 
}
 500 
}
490 
 
 501 
 
491 
/** Share address space area with another or the same address space.
 502 
/** Share address space area with another or the same address space.
492 
 *
 503 
 *
493 
 * Address space area mapping is shared with a new address space area.
 504 
 * Address space area mapping is shared with a new address space area.
494 
 * If the source address space area has not been shared so far,
 505 
 * If the source address space area has not been shared so far,
495 
 * a new sh_info is created. The new address space area simply gets the
 506 
 * a new sh_info is created. The new address space area simply gets the
496 
 * sh_info of the source area. The process of duplicating the
 507 
 * sh_info of the source area. The process of duplicating the
497 
 * mapping is done through the backend share function.
 508 
 * mapping is done through the backend share function.
498 
 *
 509 
 *
499 
 * @param src_as Pointer to source address space.
 510 
 * @param src_as Pointer to source address space.
500 
 * @param src_base Base address of the source address space area.
 511 
 * @param src_base Base address of the source address space area.
501 
 * @param acc_size Expected size of the source area.
 512 
 * @param acc_size Expected size of the source area.
502 
 * @param dst_as Pointer to destination address space.
 513 
 * @param dst_as Pointer to destination address space.
503 
 * @param dst_base Target base address.
 514 
 * @param dst_base Target base address.
504 
 * @param dst_flags_mask Destination address space area flags mask.
 515 
 * @param dst_flags_mask Destination address space area flags mask.
505 
 *
 516 
 *
506 
 * @return Zero on success or ENOENT if there is no such task or
 517 
 * @return Zero on success or ENOENT if there is no such task or
507 
 *     if there is no such address space area,
 518 
 *     if there is no such address space area,
508 
 *     EPERM if there was a problem in accepting the area or
 519 
 *     EPERM if there was a problem in accepting the area or
509 
 *     ENOMEM if there was a problem in allocating destination
 520 
 *     ENOMEM if there was a problem in allocating destination
510 
 *     address space area. ENOTSUP is returned if an attempt
 521 
 *     address space area. ENOTSUP is returned if an attempt
511 
 *     to share non-anonymous address space area is detected.
 522 
 *     to share non-anonymous address space area is detected.
512 
 */
 523 
 */
513 
int as_area_share(as_t *src_as, __address src_base, size_t acc_size,
 524 
int as_area_share(as_t *src_as, __address src_base, size_t acc_size,
514 
          as_t *dst_as, __address dst_base, int dst_flags_mask)
 525 
          as_t *dst_as, __address dst_base, int dst_flags_mask)
515 
{
 526 
{
516 
    ipl_t ipl;
 527 
    ipl_t ipl;
517 
    int src_flags;
 528 
    int src_flags;
518 
    size_t src_size;
 529 
    size_t src_size;
519 
    as_area_t *src_area, *dst_area;
 530 
    as_area_t *src_area, *dst_area;
520 
    share_info_t *sh_info;
 531 
    share_info_t *sh_info;
521 
    mem_backend_t *src_backend;
 532 
    mem_backend_t *src_backend;
522 
    mem_backend_data_t src_backend_data;
 533 
    mem_backend_data_t src_backend_data;
523 
   
 534 
   
524 
    ipl = interrupts_disable();
 535 
    ipl = interrupts_disable();
525 
    mutex_lock(&src_as->lock);
 536 
    mutex_lock(&src_as->lock);
526 
    src_area = find_area_and_lock(src_as, src_base);
 537 
    src_area = find_area_and_lock(src_as, src_base);
527 
    if (!src_area) {
 538 
    if (!src_area) {
528 
        /*
 539 
        /*
529 
         * Could not find the source address space area.
 540 
         * Could not find the source address space area.
530 
         */
 541 
         */
531 
        mutex_unlock(&src_as->lock);
 542 
        mutex_unlock(&src_as->lock);
532 
        interrupts_restore(ipl);
 543 
        interrupts_restore(ipl);
533 
        return ENOENT;
 544 
        return ENOENT;
534 
    }
 545 
    }
535 
   
 546 
   
536 
    if (!src_area->backend || !src_area->backend->share) {
 547 
    if (!src_area->backend || !src_area->backend->share) {
537 
        /*
 548 
        /*
538 
         * There is now backend or the backend does not
 549 
         * There is now backend or the backend does not
539 
         * know how to share the area.
 550 
         * know how to share the area.
540 
         */
 551 
         */
541 
        mutex_unlock(&src_area->lock);
 552 
        mutex_unlock(&src_area->lock);
542 
        mutex_unlock(&src_as->lock);
 553 
        mutex_unlock(&src_as->lock);
543 
        interrupts_restore(ipl);
 554 
        interrupts_restore(ipl);
544 
        return ENOTSUP;
 555 
        return ENOTSUP;
545 
    }
 556 
    }
546 
   
 557 
   
547 
    src_size = src_area->pages * PAGE_SIZE;
 558 
    src_size = src_area->pages * PAGE_SIZE;
548 
    src_flags = src_area->flags;
 559 
    src_flags = src_area->flags;
549 
    src_backend = src_area->backend;
 560 
    src_backend = src_area->backend;
550 
    src_backend_data = src_area->backend_data;
 561 
    src_backend_data = src_area->backend_data;
551 
 
 562 
 
552 
    /* Share the cacheable flag from the original mapping */
 563 
    /* Share the cacheable flag from the original mapping */
553 
    if (src_flags & AS_AREA_CACHEABLE)
 564 
    if (src_flags & AS_AREA_CACHEABLE)
554 
        dst_flags_mask |= AS_AREA_CACHEABLE;
 565 
        dst_flags_mask |= AS_AREA_CACHEABLE;
555 
 
 566 
 
556 
    if (src_size != acc_size || (src_flags & dst_flags_mask) != dst_flags_mask) {
 567 
    if (src_size != acc_size || (src_flags & dst_flags_mask) != dst_flags_mask) {
557 
        mutex_unlock(&src_area->lock);
 568 
        mutex_unlock(&src_area->lock);
558 
        mutex_unlock(&src_as->lock);
 569 
        mutex_unlock(&src_as->lock);
559 
        interrupts_restore(ipl);
 570 
        interrupts_restore(ipl);
560 
        return EPERM;
 571 
        return EPERM;
561 
    }
 572 
    }
562 
 
 573 
 
563 
    /*
 574 
    /*
564 
     * Now we are committed to sharing the area.
 575 
     * Now we are committed to sharing the area.
565 
     * First prepare the area for sharing.
 576 
     * First prepare the area for sharing.
566 
     * Then it will be safe to unlock it.
 577 
     * Then it will be safe to unlock it.
567 
     */
 578 
     */
568 
    sh_info = src_area->sh_info;
 579 
    sh_info = src_area->sh_info;
569 
    if (!sh_info) {
 580 
    if (!sh_info) {
570 
        sh_info = (share_info_t *) malloc(sizeof(share_info_t), 0);
 581 
        sh_info = (share_info_t *) malloc(sizeof(share_info_t), 0);
571 
        mutex_initialize(&sh_info->lock);
 582 
        mutex_initialize(&sh_info->lock);
572 
        sh_info->refcount = 2;
 583 
        sh_info->refcount = 2;
573 
        btree_create(&sh_info->pagemap);
 584 
        btree_create(&sh_info->pagemap);
574 
        src_area->sh_info = sh_info;
 585 
        src_area->sh_info = sh_info;
575 
    } else {
 586 
    } else {
576 
        mutex_lock(&sh_info->lock);
 587 
        mutex_lock(&sh_info->lock);
577 
        sh_info->refcount++;
 588 
        sh_info->refcount++;
578 
        mutex_unlock(&sh_info->lock);
 589 
        mutex_unlock(&sh_info->lock);
579 
    }
 590 
    }
580 
 
 591 
 
581 
    src_area->backend->share(src_area);
 592 
    src_area->backend->share(src_area);
582 
 
 593 
 
583 
    mutex_unlock(&src_area->lock);
 594 
    mutex_unlock(&src_area->lock);
584 
    mutex_unlock(&src_as->lock);
 595 
    mutex_unlock(&src_as->lock);
585 
 
 596 
 
586 
    /*
 597 
    /*
587 
     * Create copy of the source address space area.
 598 
     * Create copy of the source address space area.
588 
     * The destination area is created with AS_AREA_ATTR_PARTIAL
 599 
     * The destination area is created with AS_AREA_ATTR_PARTIAL
589 
     * attribute set which prevents race condition with
 600 
     * attribute set which prevents race condition with
590 
     * preliminary as_page_fault() calls.
 601 
     * preliminary as_page_fault() calls.
591 
     * The flags of the source area are masked against dst_flags_mask
 602 
     * The flags of the source area are masked against dst_flags_mask
592 
     * to support sharing in less privileged mode.
 603 
     * to support sharing in less privileged mode.
593 
     */
 604 
     */
594 
    dst_area = as_area_create(dst_as, dst_flags_mask, src_size, dst_base,
 605 
    dst_area = as_area_create(dst_as, dst_flags_mask, src_size, dst_base,
595 
                  AS_AREA_ATTR_PARTIAL, src_backend, &src_backend_data);
 606 
                  AS_AREA_ATTR_PARTIAL, src_backend, &src_backend_data);
596 
    if (!dst_area) {
 607 
    if (!dst_area) {
597 
        /*
 608 
        /*
598 
         * Destination address space area could not be created.
 609 
         * Destination address space area could not be created.
599 
         */
 610 
         */
600 
        sh_info_remove_reference(sh_info);
 611 
        sh_info_remove_reference(sh_info);
601 
       
 612 
       
602 
        interrupts_restore(ipl);
 613 
        interrupts_restore(ipl);
603 
        return ENOMEM;
 614 
        return ENOMEM;
604 
    }
 615 
    }
605 
   
 616 
   
606 
    /*
 617 
    /*
607 
     * Now the destination address space area has been
 618 
     * Now the destination address space area has been
608 
     * fully initialized. Clear the AS_AREA_ATTR_PARTIAL
 619 
     * fully initialized. Clear the AS_AREA_ATTR_PARTIAL
609 
     * attribute and set the sh_info.
 620 
     * attribute and set the sh_info.
610 
     */
 621 
     */
611 
    mutex_lock(&dst_area->lock);
 622 
    mutex_lock(&dst_area->lock);
612 
    dst_area->attributes &= ~AS_AREA_ATTR_PARTIAL;
 623 
    dst_area->attributes &= ~AS_AREA_ATTR_PARTIAL;
613 
    dst_area->sh_info = sh_info;
 624 
    dst_area->sh_info = sh_info;
614 
    mutex_unlock(&dst_area->lock);
 625 
    mutex_unlock(&dst_area->lock);
615 
   
 626 
   
616 
    interrupts_restore(ipl);
 627 
    interrupts_restore(ipl);
617 
   
 628 
   
618 
    return 0;
 629 
    return 0;
619 
}
 630 
}
620 
 
 631 
 
621 
/** Check access mode for address space area.
 632 
/** Check access mode for address space area.
622 
 *
 633 
 *
623 
 * The address space area must be locked prior to this call.
 634 
 * The address space area must be locked prior to this call.
624 
 *
 635 
 *
625 
 * @param area Address space area.
 636 
 * @param area Address space area.
626 
 * @param access Access mode.
 637 
 * @param access Access mode.
627 
 *
 638 
 *
628 
 * @return False if access violates area's permissions, true otherwise.
 639 
 * @return False if access violates area's permissions, true otherwise.
629 
 */
 640 
 */
630 
bool as_area_check_access(as_area_t *area, pf_access_t access)
 641 
bool as_area_check_access(as_area_t *area, pf_access_t access)
631 
{
 642 
{
632 
    int flagmap[] = {
 643 
    int flagmap[] = {
633 
        [PF_ACCESS_READ] = AS_AREA_READ,
 644 
        [PF_ACCESS_READ] = AS_AREA_READ,
634 
        [PF_ACCESS_WRITE] = AS_AREA_WRITE,
 645 
        [PF_ACCESS_WRITE] = AS_AREA_WRITE,
635 
        [PF_ACCESS_EXEC] = AS_AREA_EXEC
 646 
        [PF_ACCESS_EXEC] = AS_AREA_EXEC
636 
    };
 647 
    };
637 
 
 648 
 
638 
    if (!(area->flags & flagmap[access]))
 649 
    if (!(area->flags & flagmap[access]))
639 
        return false;
 650 
        return false;
640 
   
 651 
   
641 
    return true;
 652 
    return true;
642 
}
 653 
}
643 
 
 654 
 
644 
/** Handle page fault within the current address space.
 655 
/** Handle page fault within the current address space.
645 
 *
 656 
 *
646 
 * This is the high-level page fault handler. It decides
 657 
 * This is the high-level page fault handler. It decides
647 
 * whether the page fault can be resolved by any backend
 658 
 * whether the page fault can be resolved by any backend
648 
 * and if so, it invokes the backend to resolve the page
 659 
 * and if so, it invokes the backend to resolve the page
649 
 * fault.
 660 
 * fault.
650 
 *
 661 
 *
651 
 * Interrupts are assumed disabled.
 662 
 * Interrupts are assumed disabled.
652 
 *
 663 
 *
653 
 * @param page Faulting page.
 664 
 * @param page Faulting page.
654 
 * @param access Access mode that caused the fault (i.e. read/write/exec).
 665 
 * @param access Access mode that caused the fault (i.e. read/write/exec).
655 
 * @param istate Pointer to interrupted state.
 666 
 * @param istate Pointer to interrupted state.
656 
 *
 667 
 *
657 
 * @return AS_PF_FAULT on page fault, AS_PF_OK on success or AS_PF_DEFER if the
 668 
 * @return AS_PF_FAULT on page fault, AS_PF_OK on success or AS_PF_DEFER if the
658 
 *     fault was caused by copy_to_uspace() or copy_from_uspace().
 669 
 *     fault was caused by copy_to_uspace() or copy_from_uspace().
659 
 */
 670 
 */
660 
int as_page_fault(__address page, pf_access_t access, istate_t *istate)
 671 
int as_page_fault(__address page, pf_access_t access, istate_t *istate)
661 
{
 672 
{
662 
    pte_t *pte;
 673 
    pte_t *pte;
663 
    as_area_t *area;
 674 
    as_area_t *area;
664 
   
 675 
   
665 
    if (!THREAD)
 676 
    if (!THREAD)
666 
        return AS_PF_FAULT;
 677 
        return AS_PF_FAULT;
667 
       
 678 
       
668 
    ASSERT(AS);
 679 
    ASSERT(AS);
669 
 
 680 
 
670 
    mutex_lock(&AS->lock);
 681 
    mutex_lock(&AS->lock);
671 
    area = find_area_and_lock(AS, page);   
 682 
    area = find_area_and_lock(AS, page);   
672 
    if (!area) {
 683 
    if (!area) {
673 
        /*
 684 
        /*
674 
         * No area contained mapping for 'page'.
 685 
         * No area contained mapping for 'page'.
675 
         * Signal page fault to low-level handler.
 686 
         * Signal page fault to low-level handler.
676 
         */
 687 
         */
677 
        mutex_unlock(&AS->lock);
 688 
        mutex_unlock(&AS->lock);
678 
        goto page_fault;
 689 
        goto page_fault;
679 
    }
 690 
    }
680 
 
 691 
 
681 
    if (area->attributes & AS_AREA_ATTR_PARTIAL) {
 692 
    if (area->attributes & AS_AREA_ATTR_PARTIAL) {
682 
        /*
 693 
        /*
683 
         * The address space area is not fully initialized.
 694 
         * The address space area is not fully initialized.
684 
         * Avoid possible race by returning error.
 695 
         * Avoid possible race by returning error.
685 
         */
 696 
         */
686 
        mutex_unlock(&area->lock);
 697 
        mutex_unlock(&area->lock);
687 
        mutex_unlock(&AS->lock);
 698 
        mutex_unlock(&AS->lock);
688 
        goto page_fault;       
 699 
        goto page_fault;       
689 
    }
 700 
    }
690 
 
 701 
 
691 
    if (!area->backend || !area->backend->page_fault) {
 702 
    if (!area->backend || !area->backend->page_fault) {
692 
        /*
 703 
        /*
693 
         * The address space area is not backed by any backend
 704 
         * The address space area is not backed by any backend
694 
         * or the backend cannot handle page faults.
 705 
         * or the backend cannot handle page faults.
695 
         */
 706 
         */
696 
        mutex_unlock(&area->lock);
 707 
        mutex_unlock(&area->lock);
697 
        mutex_unlock(&AS->lock);
 708 
        mutex_unlock(&AS->lock);
698 
        goto page_fault;       
 709 
        goto page_fault;       
699 
    }
 710 
    }
700 
 
 711 
 
701 
    page_table_lock(AS, false);
 712 
    page_table_lock(AS, false);
702 
   
 713 
   
703 
    /*
 714 
    /*
704 
     * To avoid race condition between two page faults
 715 
     * To avoid race condition between two page faults
705 
     * on the same address, we need to make sure
 716 
     * on the same address, we need to make sure
706 
     * the mapping has not been already inserted.
 717 
     * the mapping has not been already inserted.
707 
     */
 718 
     */
708 
    if ((pte = page_mapping_find(AS, page))) {
 719 
    if ((pte = page_mapping_find(AS, page))) {
709 
        if (PTE_PRESENT(pte)) {
 720 
        if (PTE_PRESENT(pte)) {
710 
            if (((access == PF_ACCESS_READ) && PTE_READABLE(pte)) ||
 721 
            if (((access == PF_ACCESS_READ) && PTE_READABLE(pte)) ||
711 
                (access == PF_ACCESS_WRITE && PTE_WRITABLE(pte)) ||
 722 
                (access == PF_ACCESS_WRITE && PTE_WRITABLE(pte)) ||
712 
                (access == PF_ACCESS_EXEC && PTE_EXECUTABLE(pte))) {
 723 
                (access == PF_ACCESS_EXEC && PTE_EXECUTABLE(pte))) {
713 
                page_table_unlock(AS, false);
 724 
                page_table_unlock(AS, false);
714 
                mutex_unlock(&area->lock);
 725 
                mutex_unlock(&area->lock);
715 
                mutex_unlock(&AS->lock);
 726 
                mutex_unlock(&AS->lock);
716 
                return AS_PF_OK;
 727 
                return AS_PF_OK;
717 
            }
 728 
            }
718 
        }
 729 
        }
719 
    }
 730 
    }
720 
   
 731 
   
721 
    /*
 732 
    /*
722 
     * Resort to the backend page fault handler.
 733 
     * Resort to the backend page fault handler.
723 
     */
 734 
     */
724 
    if (area->backend->page_fault(area, page, access) != AS_PF_OK) {
 735 
    if (area->backend->page_fault(area, page, access) != AS_PF_OK) {
725 
        page_table_unlock(AS, false);
 736 
        page_table_unlock(AS, false);
726 
        mutex_unlock(&area->lock);
 737 
        mutex_unlock(&area->lock);
727 
        mutex_unlock(&AS->lock);
 738 
        mutex_unlock(&AS->lock);
728 
        goto page_fault;
 739 
        goto page_fault;
729 
    }
 740 
    }
730 
   
 741 
   
731 
    page_table_unlock(AS, false);
 742 
    page_table_unlock(AS, false);
732 
    mutex_unlock(&area->lock);
 743 
    mutex_unlock(&area->lock);
733 
    mutex_unlock(&AS->lock);
 744 
    mutex_unlock(&AS->lock);
734 
    return AS_PF_OK;
 745 
    return AS_PF_OK;
735 
 
 746 
 
736 
page_fault:
 747 
page_fault:
737 
    if (THREAD->in_copy_from_uspace) {
 748 
    if (THREAD->in_copy_from_uspace) {
738 
        THREAD->in_copy_from_uspace = false;
 749 
        THREAD->in_copy_from_uspace = false;
739 
        istate_set_retaddr(istate, (__address) &memcpy_from_uspace_failover_address);
 750 
        istate_set_retaddr(istate, (__address) &memcpy_from_uspace_failover_address);
740 
    } else if (THREAD->in_copy_to_uspace) {
 751 
    } else if (THREAD->in_copy_to_uspace) {
741 
        THREAD->in_copy_to_uspace = false;
 752 
        THREAD->in_copy_to_uspace = false;
742 
        istate_set_retaddr(istate, (__address) &memcpy_to_uspace_failover_address);
 753 
        istate_set_retaddr(istate, (__address) &memcpy_to_uspace_failover_address);
743 
    } else {
 754 
    } else {
744 
        return AS_PF_FAULT;
 755 
        return AS_PF_FAULT;
745 
    }
 756 
    }
746 
 
 757 
 
747 
    return AS_PF_DEFER;
 758 
    return AS_PF_DEFER;
748 
}
 759 
}
749 
 
 760 
 
750 
/** Switch address spaces.
 761 
/** Switch address spaces.
751 
 *
 762 
 *
752 
 * Note that this function cannot sleep as it is essentially a part of
 763 
 * Note that this function cannot sleep as it is essentially a part of
753 
 * scheduling. Sleeping here would lead to deadlock on wakeup.
 764 
 * scheduling. Sleeping here would lead to deadlock on wakeup.
754 
 *
 765 
 *
755 
 * @param old Old address space or NULL.
 766 
 * @param old Old address space or NULL.
756 
 * @param new New address space.
 767 
 * @param new New address space.
757 
 */
 768 
 */
758 
void as_switch(as_t *old, as_t *new)
 769 
void as_switch(as_t *old, as_t *new)
759 
{
 770 
{
760 
    ipl_t ipl;
 771 
    ipl_t ipl;
761 
    bool needs_asid = false;
 772 
    bool needs_asid = false;
762 
   
 773 
   
763 
    ipl = interrupts_disable();
 774 
    ipl = interrupts_disable();
764 
    spinlock_lock(&inactive_as_with_asid_lock);
 775 
    spinlock_lock(&inactive_as_with_asid_lock);
765 
 
 776 
 
766 
    /*
 777 
    /*
767 
     * First, take care of the old address space.
 778 
     * First, take care of the old address space.
768 
     */
 779 
     */
769 
    if (old) {
 780 
    if (old) {
770 
        mutex_lock_active(&old->lock);
 781 
        mutex_lock_active(&old->lock);
771 
        ASSERT(old->cpu_refcount);
 782 
        ASSERT(old->cpu_refcount);
772 
        if((--old->cpu_refcount == 0) && (old != AS_KERNEL)) {
 783 
        if((--old->cpu_refcount == 0) && (old != AS_KERNEL)) {
773 
            /*
 784 
            /*
774 
             * The old address space is no longer active on
 785 
             * The old address space is no longer active on
775 
             * any processor. It can be appended to the
 786 
             * any processor. It can be appended to the
776 
             * list of inactive address spaces with assigned
 787 
             * list of inactive address spaces with assigned
777 
             * ASID.
 788 
             * ASID.
778 
             */
 789 
             */
779 
             ASSERT(old->asid != ASID_INVALID);
 790 
             ASSERT(old->asid != ASID_INVALID);
780 
             list_append(&old->inactive_as_with_asid_link, &inactive_as_with_asid_head);
 791 
             list_append(&old->inactive_as_with_asid_link, &inactive_as_with_asid_head);
781 
        }
 792 
        }
782 
        mutex_unlock(&old->lock);
 793 
        mutex_unlock(&old->lock);
783 
    }
 794 
    }
784 
 
 795 
 
785 
    /*
 796 
    /*
786 
     * Second, prepare the new address space.
 797 
     * Second, prepare the new address space.
787 
     */
 798 
     */
788 
    mutex_lock_active(&new->lock);
 799 
    mutex_lock_active(&new->lock);
789 
    if ((new->cpu_refcount++ == 0) && (new != AS_KERNEL)) {
 800 
    if ((new->cpu_refcount++ == 0) && (new != AS_KERNEL)) {
790 
        if (new->asid != ASID_INVALID)
 801 
        if (new->asid != ASID_INVALID)
791 
            list_remove(&new->inactive_as_with_asid_link);
 802 
            list_remove(&new->inactive_as_with_asid_link);
792 
        else
 803 
        else
793 
            needs_asid = true;  /* defer call to asid_get() until new->lock is released */
 804 
            needs_asid = true;  /* defer call to asid_get() until new->lock is released */
794 
    }
 805 
    }
795 
    SET_PTL0_ADDRESS(new->page_table);
 806 
    SET_PTL0_ADDRESS(new->page_table);
796 
    mutex_unlock(&new->lock);
 807 
    mutex_unlock(&new->lock);
797 
 
 808 
 
798 
    if (needs_asid) {
 809 
    if (needs_asid) {
799 
        /*
 810 
        /*
800 
         * Allocation of new ASID was deferred
 811 
         * Allocation of new ASID was deferred
801 
         * until now in order to avoid deadlock.
 812 
         * until now in order to avoid deadlock.
802 
         */
 813 
         */
803 
        asid_t asid;
 814 
        asid_t asid;
804 
       
 815 
       
805 
        asid = asid_get();
 816 
        asid = asid_get();
806 
        mutex_lock_active(&new->lock);
 817 
        mutex_lock_active(&new->lock);
807 
        new->asid = asid;
 818 
        new->asid = asid;
808 
        mutex_unlock(&new->lock);
 819 
        mutex_unlock(&new->lock);
809 
    }
 820 
    }
810 
    spinlock_unlock(&inactive_as_with_asid_lock);
 821 
    spinlock_unlock(&inactive_as_with_asid_lock);
811 
    interrupts_restore(ipl);
 822 
    interrupts_restore(ipl);
812 
   
 823 
   
813 
    /*
 824 
    /*
814 
     * Perform architecture-specific steps.
 825 
     * Perform architecture-specific steps.
815 
     * (e.g. write ASID to hardware register etc.)
 826 
     * (e.g. write ASID to hardware register etc.)
816 
     */
 827 
     */
817 
    as_install_arch(new);
 828 
    as_install_arch(new);
818 
   
 829 
   
819 
    AS = new;
 830 
    AS = new;
820 
}
 831 
}
821 
 
 832 
 
822 
/** Convert address space area flags to page flags.
 833 
/** Convert address space area flags to page flags.
823 
 *
 834 
 *
824 
 * @param aflags Flags of some address space area.
 835 
 * @param aflags Flags of some address space area.
825 
 *
 836 
 *
826 
 * @return Flags to be passed to page_mapping_insert().
 837 
 * @return Flags to be passed to page_mapping_insert().
827 
 */
 838 
 */
828 
int area_flags_to_page_flags(int aflags)
 839 
int area_flags_to_page_flags(int aflags)
829 
{
 840 
{
830 
    int flags;
 841 
    int flags;
831 
 
 842 
 
832 
    flags = PAGE_USER | PAGE_PRESENT;
 843 
    flags = PAGE_USER | PAGE_PRESENT;
833 
   
 844 
   
834 
    if (aflags & AS_AREA_READ)
 845 
    if (aflags & AS_AREA_READ)
835 
        flags |= PAGE_READ;
 846 
        flags |= PAGE_READ;
836 
       
 847 
       
837 
    if (aflags & AS_AREA_WRITE)
 848 
    if (aflags & AS_AREA_WRITE)
838 
        flags |= PAGE_WRITE;
 849 
        flags |= PAGE_WRITE;
839 
   
 850 
   
840 
    if (aflags & AS_AREA_EXEC)
 851 
    if (aflags & AS_AREA_EXEC)
841 
        flags |= PAGE_EXEC;
 852 
        flags |= PAGE_EXEC;
842 
   
 853 
   
843 
    if (aflags & AS_AREA_CACHEABLE)
 854 
    if (aflags & AS_AREA_CACHEABLE)
844 
        flags |= PAGE_CACHEABLE;
 855 
        flags |= PAGE_CACHEABLE;
845 
       
 856 
       
846 
    return flags;
 857 
    return flags;
847 
}
 858 
}
848 
 
 859 
 
849 
/** Compute flags for virtual address translation subsytem.
 860 
/** Compute flags for virtual address translation subsytem.
850 
 *
 861 
 *
851 
 * The address space area must be locked.
 862 
 * The address space area must be locked.
852 
 * Interrupts must be disabled.
 863 
 * Interrupts must be disabled.
853 
 *
 864 
 *
854 
 * @param a Address space area.
 865 
 * @param a Address space area.
855 
 *
 866 
 *
856 
 * @return Flags to be used in page_mapping_insert().
 867 
 * @return Flags to be used in page_mapping_insert().
857 
 */
 868 
 */
858 
int as_area_get_flags(as_area_t *a)
 869 
int as_area_get_flags(as_area_t *a)
859 
{
 870 
{
860 
    return area_flags_to_page_flags(a->flags);
 871 
    return area_flags_to_page_flags(a->flags);
861 
}
 872 
}
862 
 
 873 
 
863 
/** Create page table.
 874 
/** Create page table.
864 
 *
 875 
 *
865 
 * Depending on architecture, create either address space
 876 
 * Depending on architecture, create either address space
866 
 * private or global page table.
 877 
 * private or global page table.
867 
 *
 878 
 *
868 
 * @param flags Flags saying whether the page table is for kernel address space.
 879 
 * @param flags Flags saying whether the page table is for kernel address space.
869 
 *
 880 
 *
870 
 * @return First entry of the page table.
 881 
 * @return First entry of the page table.
871 
 */
 882 
 */
872 
pte_t *page_table_create(int flags)
 883 
pte_t *page_table_create(int flags)
873 
{
 884 
{
874 
        ASSERT(as_operations);
 885 
        ASSERT(as_operations);
875 
        ASSERT(as_operations->page_table_create);
 886 
        ASSERT(as_operations->page_table_create);
876 
 
 887 
 
877 
        return as_operations->page_table_create(flags);
 888 
        return as_operations->page_table_create(flags);
878 
}
 889 
}
879 
 
 890 
 
880 
/** Destroy page table.
 891 
/** Destroy page table.
881 
 *
 892 
 *
882 
 * Destroy page table in architecture specific way.
 893 
 * Destroy page table in architecture specific way.
883 
 *
 894 
 *
884 
 * @param page_table Physical address of PTL0.
 895 
 * @param page_table Physical address of PTL0.
885 
 */
 896 
 */
886 
void page_table_destroy(pte_t *page_table)
 897 
void page_table_destroy(pte_t *page_table)
887 
{
 898 
{
888 
        ASSERT(as_operations);
 899 
        ASSERT(as_operations);
889 
        ASSERT(as_operations->page_table_destroy);
 900 
        ASSERT(as_operations->page_table_destroy);
890 
 
 901 
 
891 
        as_operations->page_table_destroy(page_table);
 902 
        as_operations->page_table_destroy(page_table);
892 
}
 903 
}
893 
 
 904 
 
894 
/** Lock page table.
 905 
/** Lock page table.
895 
 *
 906 
 *
896 
 * This function should be called before any page_mapping_insert(),
 907 
 * This function should be called before any page_mapping_insert(),
897 
 * page_mapping_remove() and page_mapping_find().
 908 
 * page_mapping_remove() and page_mapping_find().
898 
 *
 909 
 *
899 
 * Locking order is such that address space areas must be locked
 910 
 * Locking order is such that address space areas must be locked
900 
 * prior to this call. Address space can be locked prior to this
 911 
 * prior to this call. Address space can be locked prior to this
901 
 * call in which case the lock argument is false.
 912 
 * call in which case the lock argument is false.
902 
 *
 913 
 *
903 
 * @param as Address space.
 914 
 * @param as Address space.
904 
 * @param lock If false, do not attempt to lock as->lock.
 915 
 * @param lock If false, do not attempt to lock as->lock.
905 
 */
 916 
 */
906 
void page_table_lock(as_t *as, bool lock)
 917 
void page_table_lock(as_t *as, bool lock)
907 
{
 918 
{
908 
    ASSERT(as_operations);
 919 
    ASSERT(as_operations);
909 
    ASSERT(as_operations->page_table_lock);
 920 
    ASSERT(as_operations->page_table_lock);
910 
 
 921 
 
911 
    as_operations->page_table_lock(as, lock);
 922 
    as_operations->page_table_lock(as, lock);
912 
}
 923 
}
913 
 
 924 
 
914 
/** Unlock page table.
 925 
/** Unlock page table.
915 
 *
 926 
 *
916 
 * @param as Address space.
 927 
 * @param as Address space.
917 
 * @param unlock If false, do not attempt to unlock as->lock.
 928 
 * @param unlock If false, do not attempt to unlock as->lock.
918 
 */
 929 
 */
919 
void page_table_unlock(as_t *as, bool unlock)
 930 
void page_table_unlock(as_t *as, bool unlock)
920 
{
 931 
{
921 
    ASSERT(as_operations);
 932 
    ASSERT(as_operations);
922 
    ASSERT(as_operations->page_table_unlock);
 933 
    ASSERT(as_operations->page_table_unlock);
923 
 
 934 
 
924 
    as_operations->page_table_unlock(as, unlock);
 935 
    as_operations->page_table_unlock(as, unlock);
925 
}
 936 
}
926 
 
 937 
 
927 
 
 938 
 
928 
/** Find address space area and lock it.
 939 
/** Find address space area and lock it.
929 
 *
 940 
 *
930 
 * The address space must be locked and interrupts must be disabled.
 941 
 * The address space must be locked and interrupts must be disabled.
931 
 *
 942 
 *
932 
 * @param as Address space.
 943 
 * @param as Address space.
933 
 * @param va Virtual address.
 944 
 * @param va Virtual address.
934 
 *
 945 
 *
935 
 * @return Locked address space area containing va on success or NULL on failure.
 946 
 * @return Locked address space area containing va on success or NULL on failure.
936 
 */
 947 
 */
937 
as_area_t *find_area_and_lock(as_t *as, __address va)
 948 
as_area_t *find_area_and_lock(as_t *as, __address va)
938 
{
 949 
{
939 
    as_area_t *a;
 950 
    as_area_t *a;
940 
    btree_node_t *leaf, *lnode;
 951 
    btree_node_t *leaf, *lnode;
941 
    int i;
 952 
    int i;
942 
   
 953 
   
943 
    a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
 954 
    a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
944 
    if (a) {
 955 
    if (a) {
945 
        /* va is the base address of an address space area */
 956 
        /* va is the base address of an address space area */
946 
        mutex_lock(&a->lock);
 957 
        mutex_lock(&a->lock);
947 
        return a;
 958 
        return a;
948 
    }
 959 
    }
949 
   
 960 
   
950 
    /*
 961 
    /*
951 
     * Search the leaf node and the righmost record of its left neighbour
 962 
     * Search the leaf node and the righmost record of its left neighbour
952 
     * to find out whether this is a miss or va belongs to an address
 963 
     * to find out whether this is a miss or va belongs to an address
953 
     * space area found there.
 964 
     * space area found there.
954 
     */
 965 
     */
955 
   
 966 
   
956 
    /* First, search the leaf node itself. */
 967 
    /* First, search the leaf node itself. */
957 
    for (i = 0; i < leaf->keys; i++) {
 968 
    for (i = 0; i < leaf->keys; i++) {
958 
        a = (as_area_t *) leaf->value[i];
 969 
        a = (as_area_t *) leaf->value[i];
959 
        mutex_lock(&a->lock);
 970 
        mutex_lock(&a->lock);
960 
        if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) {
 971 
        if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) {
961 
            return a;
 972 
            return a;
962 
        }
 973 
        }
963 
        mutex_unlock(&a->lock);
 974 
        mutex_unlock(&a->lock);
964 
    }
 975 
    }
965 
 
 976 
 
966 
    /*
 977 
    /*
967 
     * Second, locate the left neighbour and test its last record.
 978 
     * Second, locate the left neighbour and test its last record.
968 
     * Because of its position in the B+tree, it must have base < va.
 979 
     * Because of its position in the B+tree, it must have base < va.
969 
     */
 980 
     */
970 
    if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
 981 
    if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
971 
        a = (as_area_t *) lnode->value[lnode->keys - 1];
 982 
        a = (as_area_t *) lnode->value[lnode->keys - 1];
972 
        mutex_lock(&a->lock);
 983 
        mutex_lock(&a->lock);
973 
        if (va < a->base + a->pages * PAGE_SIZE) {
 984 
        if (va < a->base + a->pages * PAGE_SIZE) {
974 
            return a;
 985 
            return a;
975 
        }
 986 
        }
976 
        mutex_unlock(&a->lock);
 987 
        mutex_unlock(&a->lock);
977 
    }
 988 
    }
978 
 
 989 
 
979 
    return NULL;
 990 
    return NULL;
980 
}
 991 
}
981 
 
 992 
 
982 
/** Check area conflicts with other areas.
 993 
/** Check area conflicts with other areas.
983 
 *
 994 
 *
984 
 * The address space must be locked and interrupts must be disabled.
 995 
 * The address space must be locked and interrupts must be disabled.
985 
 *
 996 
 *
986 
 * @param as Address space.
 997 
 * @param as Address space.
987 
 * @param va Starting virtual address of the area being tested.
 998 
 * @param va Starting virtual address of the area being tested.
988 
 * @param size Size of the area being tested.
 999 
 * @param size Size of the area being tested.
989 
 * @param avoid_area Do not touch this area.
 1000 
 * @param avoid_area Do not touch this area.
990 
 *
 1001 
 *
991 
 * @return True if there is no conflict, false otherwise.
 1002 
 * @return True if there is no conflict, false otherwise.
992 
 */
 1003 
 */
993 
bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area)
 1004 
bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area)
994 
{
 1005 
{
995 
    as_area_t *a;
 1006 
    as_area_t *a;
996 
    btree_node_t *leaf, *node;
 1007 
    btree_node_t *leaf, *node;
997 
    int i;
 1008 
    int i;
998 
   
 1009 
   
999 
    /*
 1010 
    /*
1000 
     * We don't want any area to have conflicts with NULL page.
 1011 
     * We don't want any area to have conflicts with NULL page.
1001 
     */
 1012 
     */
1002 
    if (overlaps(va, size, NULL, PAGE_SIZE))
 1013 
    if (overlaps(va, size, NULL, PAGE_SIZE))
1003 
        return false;
 1014 
        return false;
1004 
   
 1015 
   
1005 
    /*
 1016 
    /*
1006 
     * The leaf node is found in O(log n), where n is proportional to
 1017 
     * The leaf node is found in O(log n), where n is proportional to
1007 
     * the number of address space areas belonging to as.
 1018 
     * the number of address space areas belonging to as.
1008 
     * The check for conflicts is then attempted on the rightmost
 1019 
     * The check for conflicts is then attempted on the rightmost
1009 
     * record in the left neighbour, the leftmost record in the right
 1020 
     * record in the left neighbour, the leftmost record in the right
1010 
     * neighbour and all records in the leaf node itself.
 1021 
     * neighbour and all records in the leaf node itself.
1011 
     */
 1022 
     */
1012 
   
 1023 
   
1013 
    if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) {
 1024 
    if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) {
1014 
        if (a != avoid_area)
 1025 
        if (a != avoid_area)
1015 
            return false;
 1026 
            return false;
1016 
    }
 1027 
    }
1017 
   
 1028 
   
1018 
    /* First, check the two border cases. */
 1029 
    /* First, check the two border cases. */
1019 
    if ((node = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
 1030 
    if ((node = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
1020 
        a = (as_area_t *) node->value[node->keys - 1];
 1031 
        a = (as_area_t *) node->value[node->keys - 1];
1021 
        mutex_lock(&a->lock);
 1032 
        mutex_lock(&a->lock);
1022 
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
 1033 
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1023 
            mutex_unlock(&a->lock);
 1034 
            mutex_unlock(&a->lock);
1024 
            return false;
 1035 
            return false;
1025 
        }
 1036 
        }
1026 
        mutex_unlock(&a->lock);
 1037 
        mutex_unlock(&a->lock);
1027 
    }
 1038 
    }
1028 
    if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) {
 1039 
    if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) {
1029 
        a = (as_area_t *) node->value[0];
 1040 
        a = (as_area_t *) node->value[0];
1030 
        mutex_lock(&a->lock);
 1041 
        mutex_lock(&a->lock);
1031 
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
 1042 
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1032 
            mutex_unlock(&a->lock);
 1043 
            mutex_unlock(&a->lock);
1033 
            return false;
 1044 
            return false;
1034 
        }
 1045 
        }
1035 
        mutex_unlock(&a->lock);
 1046 
        mutex_unlock(&a->lock);
1036 
    }
 1047 
    }
1037 
   
 1048 
   
1038 
    /* Second, check the leaf node. */
 1049 
    /* Second, check the leaf node. */
1039 
    for (i = 0; i < leaf->keys; i++) {
 1050 
    for (i = 0; i < leaf->keys; i++) {
1040 
        a = (as_area_t *) leaf->value[i];
 1051 
        a = (as_area_t *) leaf->value[i];
1041 
   
 1052 
   
1042 
        if (a == avoid_area)
 1053 
        if (a == avoid_area)
1043 
            continue;
 1054 
            continue;
1044 
   
 1055 
   
1045 
        mutex_lock(&a->lock);
 1056 
        mutex_lock(&a->lock);
1046 
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
 1057 
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1047 
            mutex_unlock(&a->lock);
 1058 
            mutex_unlock(&a->lock);
1048 
            return false;
 1059 
            return false;
1049 
        }
 1060 
        }
1050 
        mutex_unlock(&a->lock);
 1061 
        mutex_unlock(&a->lock);
1051 
    }
 1062 
    }
1052 
 
 1063 
 
1053 
    /*
 1064 
    /*
1054 
     * So far, the area does not conflict with other areas.
 1065 
     * So far, the area does not conflict with other areas.
1055 
     * Check if it doesn't conflict with kernel address space.
 1066 
     * Check if it doesn't conflict with kernel address space.
1056 
     */  
 1067 
     */  
1057 
    if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
 1068 
    if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
1058 
        return !overlaps(va, size,
 1069 
        return !overlaps(va, size,
1059 
            KERNEL_ADDRESS_SPACE_START, KERNEL_ADDRESS_SPACE_END-KERNEL_ADDRESS_SPACE_START);
 1070 
            KERNEL_ADDRESS_SPACE_START, KERNEL_ADDRESS_SPACE_END-KERNEL_ADDRESS_SPACE_START);
1060 
    }
 1071 
    }
1061 
 
 1072 
 
1062 
    return true;
 1073 
    return true;
1063 
}
 1074 
}
1064 
 
 1075 
 
1065 
/** Return size of the address space area with given base.  */
 1076 
/** Return size of the address space area with given base.  */
1066 
size_t as_get_size(__address base)
 1077 
size_t as_get_size(__address base)
1067 
{
 1078 
{
1068 
    ipl_t ipl;
 1079 
    ipl_t ipl;
1069 
    as_area_t *src_area;
 1080 
    as_area_t *src_area;
1070 
    size_t size;
 1081 
    size_t size;
1071 
 
 1082 
 
1072 
    ipl = interrupts_disable();
 1083 
    ipl = interrupts_disable();
1073 
    src_area = find_area_and_lock(AS, base);
 1084 
    src_area = find_area_and_lock(AS, base);
1074 
    if (src_area){
 1085 
    if (src_area){
1075 
        size = src_area->pages * PAGE_SIZE;
 1086 
        size = src_area->pages * PAGE_SIZE;
1076 
        mutex_unlock(&src_area->lock);
 1087 
        mutex_unlock(&src_area->lock);
1077 
    } else {
 1088 
    } else {
1078 
        size = 0;
 1089 
        size = 0;
1079 
    }
 1090 
    }
1080 
    interrupts_restore(ipl);
 1091 
    interrupts_restore(ipl);
1081 
    return size;
 1092 
    return size;
1082 
}
 1093 
}
1083 
 
 1094 
 
1084 
/** Mark portion of address space area as used.
 1095 
/** Mark portion of address space area as used.
1085 
 *
 1096 
 *
1086 
 * The address space area must be already locked.
 1097 
 * The address space area must be already locked.
1087 
 *
 1098 
 *
1088 
 * @param a Address space area.
 1099 
 * @param a Address space area.
1089 
 * @param page First page to be marked.
 1100 
 * @param page First page to be marked.
1090 
 * @param count Number of page to be marked.
 1101 
 * @param count Number of page to be marked.
1091 
 *
 1102 
 *
1092 
 * @return 0 on failure and 1 on success.
 1103 
 * @return 0 on failure and 1 on success.
1093 
 */
 1104 
 */
1094 
int used_space_insert(as_area_t *a, __address page, count_t count)
 1105 
int used_space_insert(as_area_t *a, __address page, count_t count)
1095 
{
 1106 
{
1096 
    btree_node_t *leaf, *node;
 1107 
    btree_node_t *leaf, *node;
1097 
    count_t pages;
 1108 
    count_t pages;
1098 
    int i;
 1109 
    int i;
1099 
 
 1110 
 
1100 
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
 1111 
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
1101 
    ASSERT(count);
 1112 
    ASSERT(count);
1102 
 
 1113 
 
1103 
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
 1114 
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
1104 
    if (pages) {
 1115 
    if (pages) {
1105 
        /*
 1116 
        /*
1106 
         * We hit the beginning of some used space.
 1117 
         * We hit the beginning of some used space.
1107 
         */
 1118 
         */
1108 
        return 0;
 1119 
        return 0;
1109 
    }
 1120 
    }
1110 
 
 1121 
 
1111 
    if (!leaf->keys) {
 1122 
    if (!leaf->keys) {
1112 
        btree_insert(&a->used_space, page, (void *) count, leaf);
 1123 
        btree_insert(&a->used_space, page, (void *) count, leaf);
1113 
        return 1;
 1124 
        return 1;
1114 
    }
 1125 
    }
1115 
 
 1126 
 
1116 
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
 1127 
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
1117 
    if (node) {
 1128 
    if (node) {
1118 
        __address left_pg = node->key[node->keys - 1], right_pg = leaf->key[0];
 1129 
        __address left_pg = node->key[node->keys - 1], right_pg = leaf->key[0];
1119 
        count_t left_cnt = (count_t) node->value[node->keys - 1], right_cnt = (count_t) leaf->value[0];
 1130 
        count_t left_cnt = (count_t) node->value[node->keys - 1], right_cnt = (count_t) leaf->value[0];
1120 
       
 1131 
       
1121 
        /*
 1132 
        /*
1122 
         * Examine the possibility that the interval fits
 1133 
         * Examine the possibility that the interval fits
1123 
         * somewhere between the rightmost interval of
 1134 
         * somewhere between the rightmost interval of
1124 
         * the left neigbour and the first interval of the leaf.
 1135 
         * the left neigbour and the first interval of the leaf.
1125 
         */
 1136 
         */
1126 
         
 1137 
         
1127 
        if (page >= right_pg) {
 1138 
        if (page >= right_pg) {
1128 
            /* Do nothing. */
 1139 
            /* Do nothing. */
1129 
        } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
 1140 
        } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1130 
            /* The interval intersects with the left interval. */
 1141 
            /* The interval intersects with the left interval. */
1131 
            return 0;
 1142 
            return 0;
1132 
        } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
 1143 
        } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1133 
            /* The interval intersects with the right interval. */
 1144 
            /* The interval intersects with the right interval. */
1134 
            return 0;          
 1145 
            return 0;          
1135 
        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
 1146 
        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
1136 
            /* The interval can be added by merging the two already present intervals. */
 1147 
            /* The interval can be added by merging the two already present intervals. */
1137 
            node->value[node->keys - 1] += count + right_cnt;
 1148 
            node->value[node->keys - 1] += count + right_cnt;
1138 
            btree_remove(&a->used_space, right_pg, leaf);
 1149 
            btree_remove(&a->used_space, right_pg, leaf);
1139 
            return 1;
 1150 
            return 1;
1140 
        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
 1151 
        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
1141 
            /* The interval can be added by simply growing the left interval. */
 1152 
            /* The interval can be added by simply growing the left interval. */
1142 
            node->value[node->keys - 1] += count;
 1153 
            node->value[node->keys - 1] += count;
1143 
            return 1;
 1154 
            return 1;
1144 
        } else if (page + count*PAGE_SIZE == right_pg) {
 1155 
        } else if (page + count*PAGE_SIZE == right_pg) {
1145 
            /*
 1156 
            /*
1146 
             * The interval can be addded by simply moving base of the right
 1157 
             * The interval can be addded by simply moving base of the right
1147 
             * interval down and increasing its size accordingly.
 1158 
             * interval down and increasing its size accordingly.
1148 
             */
 1159 
             */
1149 
            leaf->value[0] += count;
 1160 
            leaf->value[0] += count;
1150 
            leaf->key[0] = page;
 1161 
            leaf->key[0] = page;
1151 
            return 1;
 1162 
            return 1;
1152 
        } else {
 1163 
        } else {
1153 
            /*
 1164 
            /*
1154 
             * The interval is between both neigbouring intervals,
 1165 
             * The interval is between both neigbouring intervals,
1155 
             * but cannot be merged with any of them.
 1166 
             * but cannot be merged with any of them.
1156 
             */
 1167 
             */
1157 
            btree_insert(&a->used_space, page, (void *) count, leaf);
 1168 
            btree_insert(&a->used_space, page, (void *) count, leaf);
1158 
            return 1;
 1169 
            return 1;
1159 
        }
 1170 
        }
1160 
    } else if (page < leaf->key[0]) {
 1171 
    } else if (page < leaf->key[0]) {
1161 
        __address right_pg = leaf->key[0];
 1172 
        __address right_pg = leaf->key[0];
1162 
        count_t right_cnt = (count_t) leaf->value[0];
 1173 
        count_t right_cnt = (count_t) leaf->value[0];
1163 
   
 1174 
   
1164 
        /*
 1175 
        /*
1165 
         * Investigate the border case in which the left neighbour does not
 1176 
         * Investigate the border case in which the left neighbour does not
1166 
         * exist but the interval fits from the left.
 1177 
         * exist but the interval fits from the left.
1167 
         */
 1178 
         */
1168 
         
 1179 
         
1169 
        if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
 1180 
        if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1170 
            /* The interval intersects with the right interval. */
 1181 
            /* The interval intersects with the right interval. */
1171 
            return 0;
 1182 
            return 0;
1172 
        } else if (page + count*PAGE_SIZE == right_pg) {
 1183 
        } else if (page + count*PAGE_SIZE == right_pg) {
1173 
            /*
 1184 
            /*
1174 
             * The interval can be added by moving the base of the right interval down
 1185 
             * The interval can be added by moving the base of the right interval down
1175 
             * and increasing its size accordingly.
 1186 
             * and increasing its size accordingly.
1176 
             */
 1187 
             */
1177 
            leaf->key[0] = page;
 1188 
            leaf->key[0] = page;
1178 
            leaf->value[0] += count;
 1189 
            leaf->value[0] += count;
1179 
            return 1;
 1190 
            return 1;
1180 
        } else {
 1191 
        } else {
1181 
            /*
 1192 
            /*
1182 
             * The interval doesn't adjoin with the right interval.
 1193 
             * The interval doesn't adjoin with the right interval.
1183 
             * It must be added individually.
 1194 
             * It must be added individually.
1184 
             */
 1195 
             */
1185 
            btree_insert(&a->used_space, page, (void *) count, leaf);
 1196 
            btree_insert(&a->used_space, page, (void *) count, leaf);
1186 
            return 1;
 1197 
            return 1;
1187 
        }
 1198 
        }
1188 
    }
 1199 
    }
1189 
 
 1200 
 
1190 
    node = btree_leaf_node_right_neighbour(&a->used_space, leaf);
 1201 
    node = btree_leaf_node_right_neighbour(&a->used_space, leaf);
1191 
    if (node) {
 1202 
    if (node) {
1192 
        __address left_pg = leaf->key[leaf->keys - 1], right_pg = node->key[0];
 1203 
        __address left_pg = leaf->key[leaf->keys - 1], right_pg = node->key[0];
1193 
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1], right_cnt = (count_t) node->value[0];
 1204 
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1], right_cnt = (count_t) node->value[0];
1194 
       
 1205 
       
1195 
        /*
 1206 
        /*
1196 
         * Examine the possibility that the interval fits
 1207 
         * Examine the possibility that the interval fits
1197 
         * somewhere between the leftmost interval of
 1208 
         * somewhere between the leftmost interval of
1198 
         * the right neigbour and the last interval of the leaf.
 1209 
         * the right neigbour and the last interval of the leaf.
1199 
         */
 1210 
         */
1200 
 
 1211 
 
1201 
        if (page < left_pg) {
 1212 
        if (page < left_pg) {
1202 
            /* Do nothing. */
 1213 
            /* Do nothing. */
1203 
        } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
 1214 
        } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1204 
            /* The interval intersects with the left interval. */
 1215 
            /* The interval intersects with the left interval. */
1205 
            return 0;
 1216 
            return 0;
1206 
        } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
 1217 
        } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1207 
            /* The interval intersects with the right interval. */
 1218 
            /* The interval intersects with the right interval. */
1208 
            return 0;          
 1219 
            return 0;          
1209 
        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
 1220 
        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
1210 
            /* The interval can be added by merging the two already present intervals. */
 1221 
            /* The interval can be added by merging the two already present intervals. */
1211 
            leaf->value[leaf->keys - 1] += count + right_cnt;
 1222 
            leaf->value[leaf->keys - 1] += count + right_cnt;
1212 
            btree_remove(&a->used_space, right_pg, node);
 1223 
            btree_remove(&a->used_space, right_pg, node);
1213 
            return 1;
 1224 
            return 1;
1214 
        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
 1225 
        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
1215 
            /* The interval can be added by simply growing the left interval. */
 1226 
            /* The interval can be added by simply growing the left interval. */
1216 
            leaf->value[leaf->keys - 1] +=  count;
 1227 
            leaf->value[leaf->keys - 1] +=  count;
1217 
            return 1;
 1228 
            return 1;
1218 
        } else if (page + count*PAGE_SIZE == right_pg) {
 1229 
        } else if (page + count*PAGE_SIZE == right_pg) {
1219 
            /*
 1230 
            /*
1220 
             * The interval can be addded by simply moving base of the right
 1231 
             * The interval can be addded by simply moving base of the right
1221 
             * interval down and increasing its size accordingly.
 1232 
             * interval down and increasing its size accordingly.
1222 
             */
 1233 
             */
1223 
            node->value[0] += count;
 1234 
            node->value[0] += count;
1224 
            node->key[0] = page;
 1235 
            node->key[0] = page;
1225 
            return 1;
 1236 
            return 1;
1226 
        } else {
 1237 
        } else {
1227 
            /*
 1238 
            /*
1228 
             * The interval is between both neigbouring intervals,
 1239 
             * The interval is between both neigbouring intervals,
1229 
             * but cannot be merged with any of them.
 1240 
             * but cannot be merged with any of them.
1230 
             */
 1241 
             */
1231 
            btree_insert(&a->used_space, page, (void *) count, leaf);
 1242 
            btree_insert(&a->used_space, page, (void *) count, leaf);
1232 
            return 1;
 1243 
            return 1;
1233 
        }
 1244 
        }
1234 
    } else if (page >= leaf->key[leaf->keys - 1]) {
 1245 
    } else if (page >= leaf->key[leaf->keys - 1]) {
1235 
        __address left_pg = leaf->key[leaf->keys - 1];
 1246 
        __address left_pg = leaf->key[leaf->keys - 1];
1236 
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
 1247 
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
1237 
   
 1248 
   
1238 
        /*
 1249 
        /*
1239 
         * Investigate the border case in which the right neighbour does not
 1250 
         * Investigate the border case in which the right neighbour does not
1240 
         * exist but the interval fits from the right.
 1251 
         * exist but the interval fits from the right.
1241 
         */
 1252 
         */
1242 
         
 1253 
         
1243 
        if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
 1254 
        if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1244 
            /* The interval intersects with the left interval. */
 1255 
            /* The interval intersects with the left interval. */
1245 
            return 0;
 1256 
            return 0;
1246 
        } else if (left_pg + left_cnt*PAGE_SIZE == page) {
 1257 
        } else if (left_pg + left_cnt*PAGE_SIZE == page) {
1247 
            /* The interval can be added by growing the left interval. */
 1258 
            /* The interval can be added by growing the left interval. */
1248 
            leaf->value[leaf->keys - 1] += count;
 1259 
            leaf->value[leaf->keys - 1] += count;
1249 
            return 1;
 1260 
            return 1;
1250 
        } else {
 1261 
        } else {
1251 
            /*
 1262 
            /*
1252 
             * The interval doesn't adjoin with the left interval.
 1263 
             * The interval doesn't adjoin with the left interval.
1253 
             * It must be added individually.
 1264 
             * It must be added individually.
1254 
             */
 1265 
             */
1255 
            btree_insert(&a->used_space, page, (void *) count, leaf);
 1266 
            btree_insert(&a->used_space, page, (void *) count, leaf);
1256 
            return 1;
 1267 
            return 1;
1257 
        }
 1268 
        }
1258 
    }
 1269 
    }
1259 
   
 1270 
   
1260 
    /*
 1271 
    /*
1261 
     * Note that if the algorithm made it thus far, the interval can fit only
 1272 
     * Note that if the algorithm made it thus far, the interval can fit only
1262 
     * between two other intervals of the leaf. The two border cases were already
 1273 
     * between two other intervals of the leaf. The two border cases were already
1263 
     * resolved.
 1274 
     * resolved.
1264 
     */
 1275 
     */
1265 
    for (i = 1; i < leaf->keys; i++) {
 1276 
    for (i = 1; i < leaf->keys; i++) {
1266 
        if (page < leaf->key[i]) {
 1277 
        if (page < leaf->key[i]) {
1267 
            __address left_pg = leaf->key[i - 1], right_pg = leaf->key[i];
 1278 
            __address left_pg = leaf->key[i - 1], right_pg = leaf->key[i];
1268 
            count_t left_cnt = (count_t) leaf->value[i - 1], right_cnt = (count_t) leaf->value[i];
 1279 
            count_t left_cnt = (count_t) leaf->value[i - 1], right_cnt = (count_t) leaf->value[i];
1269 
 
 1280 
 
1270 
            /*
 1281 
            /*
1271 
             * The interval fits between left_pg and right_pg.
 1282 
             * The interval fits between left_pg and right_pg.
1272 
             */
 1283 
             */
1273 
 
 1284 
 
1274 
            if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
 1285 
            if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1275 
                /* The interval intersects with the left interval. */
 1286 
                /* The interval intersects with the left interval. */
1276 
                return 0;
 1287 
                return 0;
1277 
            } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
 1288 
            } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1278 
                /* The interval intersects with the right interval. */
 1289 
                /* The interval intersects with the right interval. */
1279 
                return 0;          
 1290 
                return 0;          
1280 
            } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
 1291 
            } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
1281 
                /* The interval can be added by merging the two already present intervals. */
 1292 
                /* The interval can be added by merging the two already present intervals. */
1282 
                leaf->value[i - 1] += count + right_cnt;
 1293 
                leaf->value[i - 1] += count + right_cnt;
1283 
                btree_remove(&a->used_space, right_pg, leaf);
 1294 
                btree_remove(&a->used_space, right_pg, leaf);
1284 
                return 1;
 1295 
                return 1;
1285 
            } else if (page == left_pg + left_cnt*PAGE_SIZE) {
 1296 
            } else if (page == left_pg + left_cnt*PAGE_SIZE) {
1286 
                /* The interval can be added by simply growing the left interval. */
 1297 
                /* The interval can be added by simply growing the left interval. */
1287 
                leaf->value[i - 1] += count;
 1298 
                leaf->value[i - 1] += count;
1288 
                return 1;
 1299 
                return 1;
1289 
            } else if (page + count*PAGE_SIZE == right_pg) {
 1300 
            } else if (page + count*PAGE_SIZE == right_pg) {
1290 
                /*
 1301 
                /*
1291 
                     * The interval can be addded by simply moving base of the right
 1302 
                     * The interval can be addded by simply moving base of the right
1292 
                 * interval down and increasing its size accordingly.
 1303 
                 * interval down and increasing its size accordingly.
1293 
                 */
 1304 
                 */
1294 
                leaf->value[i] += count;
 1305 
                leaf->value[i] += count;
1295 
                leaf->key[i] = page;
 1306 
                leaf->key[i] = page;
1296 
                return 1;
 1307 
                return 1;
1297 
            } else {
 1308 
            } else {
1298 
                /*
 1309 
                /*
1299 
                 * The interval is between both neigbouring intervals,
 1310 
                 * The interval is between both neigbouring intervals,
1300 
                 * but cannot be merged with any of them.
 1311 
                 * but cannot be merged with any of them.
1301 
                 */
 1312 
                 */
1302 
                btree_insert(&a->used_space, page, (void *) count, leaf);
 1313 
                btree_insert(&a->used_space, page, (void *) count, leaf);
1303 
                return 1;
 1314 
                return 1;
1304 
            }
 1315 
            }
1305 
        }
 1316 
        }
1306 
    }
 1317 
    }
1307 
 
 1318 
 
1308 
    panic("Inconsistency detected while adding %d pages of used space at %P.\n", count, page);
 1319 
    panic("Inconsistency detected while adding %d pages of used space at %P.\n", count, page);
1309 
}
 1320 
}
1310 
 
 1321 
 
1311 
/** Mark portion of address space area as unused.
 1322 
/** Mark portion of address space area as unused.
1312 
 *
 1323 
 *
1313 
 * The address space area must be already locked.
 1324 
 * The address space area must be already locked.
1314 
 *
 1325 
 *
1315 
 * @param a Address space area.
 1326 
 * @param a Address space area.
1316 
 * @param page First page to be marked.
 1327 
 * @param page First page to be marked.
1317 
 * @param count Number of page to be marked.
 1328 
 * @param count Number of page to be marked.
1318 
 *
 1329 
 *
1319 
 * @return 0 on failure and 1 on success.
 1330 
 * @return 0 on failure and 1 on success.
1320 
 */
 1331 
 */
1321 
int used_space_remove(as_area_t *a, __address page, count_t count)
 1332 
int used_space_remove(as_area_t *a, __address page, count_t count)
1322 
{
 1333 
{
1323 
    btree_node_t *leaf, *node;
 1334 
    btree_node_t *leaf, *node;
1324 
    count_t pages;
 1335 
    count_t pages;
1325 
    int i;
 1336 
    int i;
1326 
 
 1337 
 
1327 
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
 1338 
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
1328 
    ASSERT(count);
 1339 
    ASSERT(count);
1329 
 
 1340 
 
1330 
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
 1341 
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
1331 
    if (pages) {
 1342 
    if (pages) {
1332 
        /*
 1343 
        /*
1333 
         * We are lucky, page is the beginning of some interval.
 1344 
         * We are lucky, page is the beginning of some interval.
1334 
         */
 1345 
         */
1335 
        if (count > pages) {
 1346 
        if (count > pages) {
1336 
            return 0;
 1347 
            return 0;
1337 
        } else if (count == pages) {
 1348 
        } else if (count == pages) {
1338 
            btree_remove(&a->used_space, page, leaf);
 1349 
            btree_remove(&a->used_space, page, leaf);
1339 
            return 1;
 1350 
            return 1;
1340 
        } else {
 1351 
        } else {
1341 
            /*
 1352 
            /*
1342 
             * Find the respective interval.
 1353 
             * Find the respective interval.
1343 
             * Decrease its size and relocate its start address.
 1354 
             * Decrease its size and relocate its start address.
1344 
             */
 1355 
             */
1345 
            for (i = 0; i < leaf->keys; i++) {
 1356 
            for (i = 0; i < leaf->keys; i++) {
1346 
                if (leaf->key[i] == page) {
 1357 
                if (leaf->key[i] == page) {
1347 
                    leaf->key[i] += count*PAGE_SIZE;
 1358 
                    leaf->key[i] += count*PAGE_SIZE;
1348 
                    leaf->value[i] -= count;
 1359 
                    leaf->value[i] -= count;
1349 
                    return 1;
 1360 
                    return 1;
1350 
                }
 1361 
                }
1351 
            }
 1362 
            }
1352 
            goto error;
 1363 
            goto error;
1353 
        }
 1364 
        }
1354 
    }
 1365 
    }
1355 
 
 1366 
 
1356 
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
 1367 
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
1357 
    if (node && page < leaf->key[0]) {
 1368 
    if (node && page < leaf->key[0]) {
1358 
        __address left_pg = node->key[node->keys - 1];
 1369 
        __address left_pg = node->key[node->keys - 1];
1359 
        count_t left_cnt = (count_t) node->value[node->keys - 1];
 1370 
        count_t left_cnt = (count_t) node->value[node->keys - 1];
1360 
 
 1371 
 
1361 
        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
 1372 
        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
1362 
            if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
 1373 
            if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
1363 
                /*
 1374 
                /*
1364 
                 * The interval is contained in the rightmost interval
 1375 
                 * The interval is contained in the rightmost interval
1365 
                 * of the left neighbour and can be removed by
 1376 
                 * of the left neighbour and can be removed by
1366 
                 * updating the size of the bigger interval.
 1377 
                 * updating the size of the bigger interval.
1367 
                 */
 1378 
                 */
1368 
                node->value[node->keys - 1] -= count;
 1379 
                node->value[node->keys - 1] -= count;
1369 
                return 1;
 1380 
                return 1;
1370 
            } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
 1381 
            } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
1371 
                count_t new_cnt;
 1382 
                count_t new_cnt;
1372 
               
 1383 
               
1373 
                /*
 1384 
                /*
1374 
                 * The interval is contained in the rightmost interval
 1385 
                 * The interval is contained in the rightmost interval
1375 
                 * of the left neighbour but its removal requires
 1386 
                 * of the left neighbour but its removal requires
1376 
                 * both updating the size of the original interval and
 1387 
                 * both updating the size of the original interval and
1377 
                 * also inserting a new interval.
 1388 
                 * also inserting a new interval.
1378 
                 */
 1389 
                 */
1379 
                new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
 1390 
                new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
1380 
                node->value[node->keys - 1] -= count + new_cnt;
 1391 
                node->value[node->keys - 1] -= count + new_cnt;
1381 
                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
 1392 
                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
1382 
                return 1;
 1393 
                return 1;
1383 
            }
 1394 
            }
1384 
        }
 1395 
        }
1385 
        return 0;
 1396 
        return 0;
1386 
    } else if (page < leaf->key[0]) {
 1397 
    } else if (page < leaf->key[0]) {
1387 
        return 0;
 1398 
        return 0;
1388 
    }
 1399 
    }
1389 
   
 1400 
   
1390 
    if (page > leaf->key[leaf->keys - 1]) {
 1401 
    if (page > leaf->key[leaf->keys - 1]) {
1391 
        __address left_pg = leaf->key[leaf->keys - 1];
 1402 
        __address left_pg = leaf->key[leaf->keys - 1];
1392 
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
 1403 
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
1393 
 
 1404 
 
1394 
        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
 1405 
        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
1395 
            if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
 1406 
            if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
1396 
                /*
 1407 
                /*
1397 
                 * The interval is contained in the rightmost interval
 1408 
                 * The interval is contained in the rightmost interval
1398 
                 * of the leaf and can be removed by updating the size
 1409 
                 * of the leaf and can be removed by updating the size
1399 
                 * of the bigger interval.
 1410 
                 * of the bigger interval.
1400 
                 */
 1411 
                 */
1401 
                leaf->value[leaf->keys - 1] -= count;
 1412 
                leaf->value[leaf->keys - 1] -= count;
1402 
                return 1;
 1413 
                return 1;
1403 
            } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
 1414 
            } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
1404 
                count_t new_cnt;
 1415 
                count_t new_cnt;
1405 
               
 1416 
               
1406 
                /*
 1417 
                /*
1407 
                 * The interval is contained in the rightmost interval
 1418 
                 * The interval is contained in the rightmost interval
1408 
                 * of the leaf but its removal requires both updating
 1419 
                 * of the leaf but its removal requires both updating
1409 
                 * the size of the original interval and
 1420 
                 * the size of the original interval and
1410 
                 * also inserting a new interval.
 1421 
                 * also inserting a new interval.
1411 
                 */
 1422 
                 */
1412 
                new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
 1423 
                new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
1413 
                leaf->value[leaf->keys - 1] -= count + new_cnt;
 1424 
                leaf->value[leaf->keys - 1] -= count + new_cnt;
1414 
                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
 1425 
                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
1415 
                return 1;
 1426 
                return 1;
1416 
            }
 1427 
            }
1417 
        }
 1428 
        }
1418 
        return 0;
 1429 
        return 0;
1419 
    }  
 1430 
    }  
1420 
   
 1431 
   
1421 
    /*
 1432 
    /*
1422 
     * The border cases have been already resolved.
 1433 
     * The border cases have been already resolved.
1423 
     * Now the interval can be only between intervals of the leaf.
 1434 
     * Now the interval can be only between intervals of the leaf.
1424 
     */
 1435 
     */
1425 
    for (i = 1; i < leaf->keys - 1; i++) {
 1436 
    for (i = 1; i < leaf->keys - 1; i++) {
1426 
        if (page < leaf->key[i]) {
 1437 
        if (page < leaf->key[i]) {
1427 
            __address left_pg = leaf->key[i - 1];
 1438 
            __address left_pg = leaf->key[i - 1];
1428 
            count_t left_cnt = (count_t) leaf->value[i - 1];
 1439 
            count_t left_cnt = (count_t) leaf->value[i - 1];
1429 
 
 1440 
 
1430 
            /*
 1441 
            /*
1431 
             * Now the interval is between intervals corresponding to (i - 1) and i.
 1442 
             * Now the interval is between intervals corresponding to (i - 1) and i.
1432 
             */
 1443 
             */
1433 
            if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
 1444 
            if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
1434 
                if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
 1445 
                if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
1435 
                    /*
 1446 
                    /*
1436 
                    * The interval is contained in the interval (i - 1)
 1447 
                    * The interval is contained in the interval (i - 1)
1437 
                     * of the leaf and can be removed by updating the size
 1448 
                     * of the leaf and can be removed by updating the size
1438 
                     * of the bigger interval.
 1449 
                     * of the bigger interval.
1439 
                     */
 1450 
                     */
1440 
                    leaf->value[i - 1] -= count;
 1451 
                    leaf->value[i - 1] -= count;
1441 
                    return 1;
 1452 
                    return 1;
1442 
                } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
 1453 
                } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
1443 
                    count_t new_cnt;
 1454 
                    count_t new_cnt;
1444 
               
 1455 
               
1445 
                    /*
 1456 
                    /*
1446 
                     * The interval is contained in the interval (i - 1)
 1457 
                     * The interval is contained in the interval (i - 1)
1447 
                     * of the leaf but its removal requires both updating
 1458 
                     * of the leaf but its removal requires both updating
1448 
                     * the size of the original interval and
 1459 
                     * the size of the original interval and
1449 
                     * also inserting a new interval.
 1460 
                     * also inserting a new interval.
1450 
                     */
 1461 
                     */
1451 
                    new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
 1462 
                    new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
1452 
                    leaf->value[i - 1] -= count + new_cnt;
 1463 
                    leaf->value[i - 1] -= count + new_cnt;
1453 
                    btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
 1464 
                    btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
1454 
                    return 1;
 1465 
                    return 1;
1455 
                }
 1466 
                }
1456 
            }
 1467 
            }
1457 
            return 0;
 1468 
            return 0;
1458 
        }
 1469 
        }
1459 
    }
 1470 
    }
1460 
 
 1471 
 
1461 
error:
 1472 
error:
1462 
    panic("Inconsistency detected while removing %d pages of used space from %P.\n", count, page);
 1473 
    panic("Inconsistency detected while removing %d pages of used space from %P.\n", count, page);
1463 
}
 1474 
}
1464 
 
 1475 
 
1465 
/** Remove reference to address space area share info.
 1476 
/** Remove reference to address space area share info.
1466 
 *
 1477 
 *
1467 
 * If the reference count drops to 0, the sh_info is deallocated.
 1478 
 * If the reference count drops to 0, the sh_info is deallocated.
1468 
 *
 1479 
 *
1469 
 * @param sh_info Pointer to address space area share info.
 1480 
 * @param sh_info Pointer to address space area share info.
1470 
 */
 1481 
 */
1471 
void sh_info_remove_reference(share_info_t *sh_info)
 1482 
void sh_info_remove_reference(share_info_t *sh_info)
1472 
{
 1483 
{
1473 
    bool dealloc = false;
 1484 
    bool dealloc = false;
1474 
 
 1485 
 
1475 
    mutex_lock(&sh_info->lock);
 1486 
    mutex_lock(&sh_info->lock);
1476 
    ASSERT(sh_info->refcount);
 1487 
    ASSERT(sh_info->refcount);
1477 
    if (--sh_info->refcount == 0) {
 1488 
    if (--sh_info->refcount == 0) {
1478 
        dealloc = true;
 1489 
        dealloc = true;
1479 
        link_t *cur;
 1490 
        link_t *cur;
1480 
       
 1491 
       
1481 
        /*
 1492 
        /*
1482 
         * Now walk carefully the pagemap B+tree and free/remove
 1493 
         * Now walk carefully the pagemap B+tree and free/remove
1483 
         * reference from all frames found there.
 1494 
         * reference from all frames found there.
1484 
         */
 1495 
         */
1485 
        for (cur = sh_info->pagemap.leaf_head.next; cur != &sh_info->pagemap.leaf_head; cur = cur->next) {
 1496 
        for (cur = sh_info->pagemap.leaf_head.next; cur != &sh_info->pagemap.leaf_head; cur = cur->next) {
1486 
            btree_node_t *node;
 1497 
            btree_node_t *node;
1487 
            int i;
 1498 
            int i;
1488 
           
 1499 
           
1489 
            node = list_get_instance(cur, btree_node_t, leaf_link);
 1500 
            node = list_get_instance(cur, btree_node_t, leaf_link);
1490 
            for (i = 0; i < node->keys; i++)
 1501 
            for (i = 0; i < node->keys; i++)
1491 
                frame_free(ADDR2PFN((__address) node->value[i]));
 1502 
                frame_free(ADDR2PFN((__address) node->value[i]));
1492 
        }
 1503 
        }
1493 
       
 1504 
       
1494 
    }
 1505 
    }
1495 
    mutex_unlock(&sh_info->lock);
 1506 
    mutex_unlock(&sh_info->lock);
1496 
   
 1507 
   
1497 
    if (dealloc) {
 1508 
    if (dealloc) {
1498 
        btree_destroy(&sh_info->pagemap);
 1509 
        btree_destroy(&sh_info->pagemap);
1499 
        free(sh_info);
 1510 
        free(sh_info);
1500 
    }
 1511 
    }
1501 
}
 1512 
}
1502 
 
 1513 
 
1503 
/*
 1514 
/*
1504 
 * Address space related syscalls.
 1515 
 * Address space related syscalls.
1505 
 */
 1516 
 */
1506 
 
 1517 
 
1507 
/** Wrapper for as_area_create(). */
 1518 
/** Wrapper for as_area_create(). */
1508 
__native sys_as_area_create(__address address, size_t size, int flags)
 1519 
__native sys_as_area_create(__address address, size_t size, int flags)
1509 
{
 1520 
{
1510 
    if (as_area_create(AS, flags | AS_AREA_CACHEABLE, size, address, AS_AREA_ATTR_NONE, &anon_backend, NULL))
 1521 
    if (as_area_create(AS, flags | AS_AREA_CACHEABLE, size, address, AS_AREA_ATTR_NONE, &anon_backend, NULL))
1511 
        return (__native) address;
 1522 
        return (__native) address;
1512 
    else
 1523 
    else
1513 
        return (__native) -1;
 1524 
        return (__native) -1;
1514 
}
 1525 
}
1515 
 
 1526 
 
1516 
/** Wrapper for as_area_resize. */
 1527 
/** Wrapper for as_area_resize. */
1517 
__native sys_as_area_resize(__address address, size_t size, int flags)
 1528 
__native sys_as_area_resize(__address address, size_t size, int flags)
1518 
{
 1529 
{
1519 
    return (__native) as_area_resize(AS, address, size, 0);
 1530 
    return (__native) as_area_resize(AS, address, size, 0);
1520 
}
 1531 
}
1521 
 
 1532 
 
1522 
/** Wrapper for as_area_destroy. */
 1533 
/** Wrapper for as_area_destroy. */
1523 
__native sys_as_area_destroy(__address address)
 1534 
__native sys_as_area_destroy(__address address)
1524 
{
 1535 
{
1525 
    return (__native) as_area_destroy(AS, address);
 1536 
    return (__native) as_area_destroy(AS, address);
1526 
}
 1537 
}
- 
 
 1538 
 
- 
 
 1539 
 /** @}
- 
 
 1540 
 */
- 
 
 1541 
 
1527 
 
 1542