Subversion Repositories HelenOS

Rev

Rev 1424 | Rev 1434 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

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