Subversion Repositories HelenOS-historic

Rev

Rev 1483 | Rev 1544 | Go to most recent revision | Only display areas with differences | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

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