Subversion Repositories HelenOS

Rev

Rev 1423 | Rev 1428 | 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.
459
 * @param dst_base Target base address.
460
 * @param dst_flags_mask Destination address space area flags mask.
1235 jermar 461
 *
1306 jermar 462
 * @return Zero on success or ENOENT if there is no such task or
1235 jermar 463
 *     if there is no such address space area,
464
 *     EPERM if there was a problem in accepting the area or
465
 *     ENOMEM if there was a problem in allocating destination
1413 jermar 466
 *     address space area. ENOTSUP is returned if an attempt
467
 *     to share non-anonymous address space area is detected.
1235 jermar 468
 */
1413 jermar 469
int as_area_share(as_t *src_as, __address src_base, size_t acc_size,
1417 jermar 470
          __address dst_base, int dst_flags_mask)
1235 jermar 471
{
472
    ipl_t ipl;
1239 jermar 473
    int src_flags;
474
    size_t src_size;
475
    as_area_t *src_area, *dst_area;
1413 jermar 476
    share_info_t *sh_info;
1424 jermar 477
    mem_backend_t *src_backend;
478
    mem_backend_data_t src_backend_data;
1329 palkovsky 479
 
1235 jermar 480
    ipl = interrupts_disable();
1380 jermar 481
    mutex_lock(&src_as->lock);
1329 palkovsky 482
    src_area = find_area_and_lock(src_as, src_base);
1239 jermar 483
    if (!src_area) {
1238 jermar 484
        /*
485
         * Could not find the source address space area.
486
         */
1380 jermar 487
        mutex_unlock(&src_as->lock);
1238 jermar 488
        interrupts_restore(ipl);
489
        return ENOENT;
490
    }
1413 jermar 491
 
1424 jermar 492
    if (!src_area->backend || !src_area->backend->share) {
1413 jermar 493
        /*
1424 jermar 494
         * There is now backend or the backend does not
495
         * know how to share the area.
1413 jermar 496
         */
497
        mutex_unlock(&src_area->lock);
498
        mutex_unlock(&src_as->lock);
499
        interrupts_restore(ipl);
500
        return ENOTSUP;
501
    }
502
 
1239 jermar 503
    src_size = src_area->pages * PAGE_SIZE;
504
    src_flags = src_area->flags;
1424 jermar 505
    src_backend = src_area->backend;
506
    src_backend_data = src_area->backend_data;
1413 jermar 507
 
1329 palkovsky 508
    if (src_size != acc_size) {
1413 jermar 509
        mutex_unlock(&src_area->lock);
510
        mutex_unlock(&src_as->lock);
1235 jermar 511
        interrupts_restore(ipl);
512
        return EPERM;
513
    }
1413 jermar 514
 
1235 jermar 515
    /*
1413 jermar 516
     * Now we are committed to sharing the area.
517
     * First prepare the area for sharing.
518
     * Then it will be safe to unlock it.
519
     */
520
    sh_info = src_area->sh_info;
521
    if (!sh_info) {
522
        sh_info = (share_info_t *) malloc(sizeof(share_info_t), 0);
523
        mutex_initialize(&sh_info->lock);
524
        sh_info->refcount = 2;
525
        btree_create(&sh_info->pagemap);
526
        src_area->sh_info = sh_info;
527
    } else {
528
        mutex_lock(&sh_info->lock);
529
        sh_info->refcount++;
530
        mutex_unlock(&sh_info->lock);
531
    }
532
 
1424 jermar 533
    src_area->backend->share(src_area);
1413 jermar 534
 
535
    mutex_unlock(&src_area->lock);
536
    mutex_unlock(&src_as->lock);
537
 
538
    /*
1239 jermar 539
     * Create copy of the source address space area.
540
     * The destination area is created with AS_AREA_ATTR_PARTIAL
541
     * attribute set which prevents race condition with
542
     * preliminary as_page_fault() calls.
1417 jermar 543
     * The flags of the source area are masked against dst_flags_mask
544
     * to support sharing in less privileged mode.
1235 jermar 545
     */
1417 jermar 546
    dst_area = as_area_create(AS, src_flags & dst_flags_mask, src_size, dst_base,
1424 jermar 547
                  AS_AREA_ATTR_PARTIAL, src_backend, &src_backend_data);
1239 jermar 548
    if (!dst_area) {
1235 jermar 549
        /*
550
         * Destination address space area could not be created.
551
         */
1413 jermar 552
        sh_info_remove_reference(sh_info);
553
 
1235 jermar 554
        interrupts_restore(ipl);
555
        return ENOMEM;
556
    }
557
 
558
    /*
1239 jermar 559
     * Now the destination address space area has been
560
     * fully initialized. Clear the AS_AREA_ATTR_PARTIAL
1413 jermar 561
     * attribute and set the sh_info.
1239 jermar 562
     */
1380 jermar 563
    mutex_lock(&dst_area->lock);
1239 jermar 564
    dst_area->attributes &= ~AS_AREA_ATTR_PARTIAL;
1413 jermar 565
    dst_area->sh_info = sh_info;
1380 jermar 566
    mutex_unlock(&dst_area->lock);
1235 jermar 567
 
568
    interrupts_restore(ipl);
569
 
570
    return 0;
571
}
572
 
1423 jermar 573
/** Check access mode for address space area.
574
 *
575
 * The address space area must be locked prior to this call.
576
 *
577
 * @param area Address space area.
578
 * @param access Access mode.
579
 *
580
 * @return False if access violates area's permissions, true otherwise.
581
 */
582
bool as_area_check_access(as_area_t *area, pf_access_t access)
583
{
584
    int flagmap[] = {
585
        [PF_ACCESS_READ] = AS_AREA_READ,
586
        [PF_ACCESS_WRITE] = AS_AREA_WRITE,
587
        [PF_ACCESS_EXEC] = AS_AREA_EXEC
588
    };
589
 
590
    if (!(area->flags & flagmap[access]))
591
        return false;
592
 
593
    return true;
594
}
595
 
703 jermar 596
/** Handle page fault within the current address space.
597
 *
1409 jermar 598
 * This is the high-level page fault handler. It decides
599
 * whether the page fault can be resolved by any backend
600
 * and if so, it invokes the backend to resolve the page
601
 * fault.
602
 *
703 jermar 603
 * Interrupts are assumed disabled.
604
 *
605
 * @param page Faulting page.
1411 jermar 606
 * @param access Access mode that caused the fault (i.e. read/write/exec).
1288 jermar 607
 * @param istate Pointer to interrupted state.
703 jermar 608
 *
1409 jermar 609
 * @return AS_PF_FAULT on page fault, AS_PF_OK on success or AS_PF_DEFER if the
610
 *     fault was caused by copy_to_uspace() or copy_from_uspace().
703 jermar 611
 */
1411 jermar 612
int as_page_fault(__address page, pf_access_t access, istate_t *istate)
703 jermar 613
{
1044 jermar 614
    pte_t *pte;
977 jermar 615
    as_area_t *area;
703 jermar 616
 
1380 jermar 617
    if (!THREAD)
1409 jermar 618
        return AS_PF_FAULT;
1380 jermar 619
 
703 jermar 620
    ASSERT(AS);
1044 jermar 621
 
1380 jermar 622
    mutex_lock(&AS->lock);
977 jermar 623
    area = find_area_and_lock(AS, page);   
703 jermar 624
    if (!area) {
625
        /*
626
         * No area contained mapping for 'page'.
627
         * Signal page fault to low-level handler.
628
         */
1380 jermar 629
        mutex_unlock(&AS->lock);
1288 jermar 630
        goto page_fault;
703 jermar 631
    }
632
 
1239 jermar 633
    if (area->attributes & AS_AREA_ATTR_PARTIAL) {
634
        /*
635
         * The address space area is not fully initialized.
636
         * Avoid possible race by returning error.
637
         */
1380 jermar 638
        mutex_unlock(&area->lock);
639
        mutex_unlock(&AS->lock);
1288 jermar 640
        goto page_fault;       
1239 jermar 641
    }
642
 
1424 jermar 643
    if (!area->backend || !area->backend->page_fault) {
1409 jermar 644
        /*
645
         * The address space area is not backed by any backend
646
         * or the backend cannot handle page faults.
647
         */
648
        mutex_unlock(&area->lock);
649
        mutex_unlock(&AS->lock);
650
        goto page_fault;       
651
    }
1179 jermar 652
 
1044 jermar 653
    page_table_lock(AS, false);
654
 
703 jermar 655
    /*
1044 jermar 656
     * To avoid race condition between two page faults
657
     * on the same address, we need to make sure
658
     * the mapping has not been already inserted.
659
     */
660
    if ((pte = page_mapping_find(AS, page))) {
661
        if (PTE_PRESENT(pte)) {
1423 jermar 662
            if (((access == PF_ACCESS_READ) && PTE_READABLE(pte)) ||
663
                (access == PF_ACCESS_WRITE && PTE_WRITABLE(pte)) ||
664
                (access == PF_ACCESS_EXEC && PTE_EXECUTABLE(pte))) {
665
                page_table_unlock(AS, false);
666
                mutex_unlock(&area->lock);
667
                mutex_unlock(&AS->lock);
668
                return AS_PF_OK;
669
            }
1044 jermar 670
        }
671
    }
1409 jermar 672
 
1044 jermar 673
    /*
1409 jermar 674
     * Resort to the backend page fault handler.
703 jermar 675
     */
1424 jermar 676
    if (area->backend->page_fault(area, page, access) != AS_PF_OK) {
1409 jermar 677
        page_table_unlock(AS, false);
678
        mutex_unlock(&area->lock);
679
        mutex_unlock(&AS->lock);
680
        goto page_fault;
681
    }
703 jermar 682
 
1044 jermar 683
    page_table_unlock(AS, false);
1380 jermar 684
    mutex_unlock(&area->lock);
685
    mutex_unlock(&AS->lock);
1288 jermar 686
    return AS_PF_OK;
687
 
688
page_fault:
689
    if (THREAD->in_copy_from_uspace) {
690
        THREAD->in_copy_from_uspace = false;
691
        istate_set_retaddr(istate, (__address) &memcpy_from_uspace_failover_address);
692
    } else if (THREAD->in_copy_to_uspace) {
693
        THREAD->in_copy_to_uspace = false;
694
        istate_set_retaddr(istate, (__address) &memcpy_to_uspace_failover_address);
695
    } else {
696
        return AS_PF_FAULT;
697
    }
698
 
699
    return AS_PF_DEFER;
703 jermar 700
}
701
 
823 jermar 702
/** Switch address spaces.
703 jermar 703
 *
1380 jermar 704
 * Note that this function cannot sleep as it is essentially a part of
1415 jermar 705
 * scheduling. Sleeping here would lead to deadlock on wakeup.
1380 jermar 706
 *
823 jermar 707
 * @param old Old address space or NULL.
708
 * @param new New address space.
703 jermar 709
 */
823 jermar 710
void as_switch(as_t *old, as_t *new)
703 jermar 711
{
712
    ipl_t ipl;
823 jermar 713
    bool needs_asid = false;
703 jermar 714
 
715
    ipl = interrupts_disable();
1415 jermar 716
    spinlock_lock(&inactive_as_with_asid_lock);
703 jermar 717
 
718
    /*
823 jermar 719
     * First, take care of the old address space.
720
     */
721
    if (old) {
1380 jermar 722
        mutex_lock_active(&old->lock);
1415 jermar 723
        ASSERT(old->cpu_refcount);
724
        if((--old->cpu_refcount == 0) && (old != AS_KERNEL)) {
823 jermar 725
            /*
726
             * The old address space is no longer active on
727
             * any processor. It can be appended to the
728
             * list of inactive address spaces with assigned
729
             * ASID.
730
             */
731
             ASSERT(old->asid != ASID_INVALID);
732
             list_append(&old->inactive_as_with_asid_link, &inactive_as_with_asid_head);
733
        }
1380 jermar 734
        mutex_unlock(&old->lock);
823 jermar 735
    }
736
 
737
    /*
738
     * Second, prepare the new address space.
739
     */
1380 jermar 740
    mutex_lock_active(&new->lock);
1415 jermar 741
    if ((new->cpu_refcount++ == 0) && (new != AS_KERNEL)) {
823 jermar 742
        if (new->asid != ASID_INVALID)
743
            list_remove(&new->inactive_as_with_asid_link);
744
        else
745
            needs_asid = true;  /* defer call to asid_get() until new->lock is released */
746
    }
747
    SET_PTL0_ADDRESS(new->page_table);
1380 jermar 748
    mutex_unlock(&new->lock);
823 jermar 749
 
750
    if (needs_asid) {
751
        /*
752
         * Allocation of new ASID was deferred
753
         * until now in order to avoid deadlock.
754
         */
755
        asid_t asid;
756
 
757
        asid = asid_get();
1380 jermar 758
        mutex_lock_active(&new->lock);
823 jermar 759
        new->asid = asid;
1380 jermar 760
        mutex_unlock(&new->lock);
823 jermar 761
    }
1415 jermar 762
    spinlock_unlock(&inactive_as_with_asid_lock);
823 jermar 763
    interrupts_restore(ipl);
764
 
765
    /*
703 jermar 766
     * Perform architecture-specific steps.
727 jermar 767
     * (e.g. write ASID to hardware register etc.)
703 jermar 768
     */
823 jermar 769
    as_install_arch(new);
703 jermar 770
 
823 jermar 771
    AS = new;
703 jermar 772
}
754 jermar 773
 
1235 jermar 774
/** Convert address space area flags to page flags.
754 jermar 775
 *
1235 jermar 776
 * @param aflags Flags of some address space area.
754 jermar 777
 *
1235 jermar 778
 * @return Flags to be passed to page_mapping_insert().
754 jermar 779
 */
1235 jermar 780
int area_flags_to_page_flags(int aflags)
754 jermar 781
{
782
    int flags;
783
 
1178 jermar 784
    flags = PAGE_USER | PAGE_PRESENT;
754 jermar 785
 
1235 jermar 786
    if (aflags & AS_AREA_READ)
1026 jermar 787
        flags |= PAGE_READ;
788
 
1235 jermar 789
    if (aflags & AS_AREA_WRITE)
1026 jermar 790
        flags |= PAGE_WRITE;
791
 
1235 jermar 792
    if (aflags & AS_AREA_EXEC)
1026 jermar 793
        flags |= PAGE_EXEC;
794
 
1424 jermar 795
    if (aflags & AS_AREA_CACHEABLE)
1178 jermar 796
        flags |= PAGE_CACHEABLE;
797
 
754 jermar 798
    return flags;
799
}
756 jermar 800
 
1235 jermar 801
/** Compute flags for virtual address translation subsytem.
802
 *
803
 * The address space area must be locked.
804
 * Interrupts must be disabled.
805
 *
806
 * @param a Address space area.
807
 *
808
 * @return Flags to be used in page_mapping_insert().
809
 */
1409 jermar 810
int as_area_get_flags(as_area_t *a)
1235 jermar 811
{
812
    return area_flags_to_page_flags(a->flags);
813
}
814
 
756 jermar 815
/** Create page table.
816
 *
817
 * Depending on architecture, create either address space
818
 * private or global page table.
819
 *
820
 * @param flags Flags saying whether the page table is for kernel address space.
821
 *
822
 * @return First entry of the page table.
823
 */
824
pte_t *page_table_create(int flags)
825
{
826
        ASSERT(as_operations);
827
        ASSERT(as_operations->page_table_create);
828
 
829
        return as_operations->page_table_create(flags);
830
}
977 jermar 831
 
1044 jermar 832
/** Lock page table.
833
 *
834
 * This function should be called before any page_mapping_insert(),
835
 * page_mapping_remove() and page_mapping_find().
836
 *
837
 * Locking order is such that address space areas must be locked
838
 * prior to this call. Address space can be locked prior to this
839
 * call in which case the lock argument is false.
840
 *
841
 * @param as Address space.
1248 jermar 842
 * @param lock If false, do not attempt to lock as->lock.
1044 jermar 843
 */
844
void page_table_lock(as_t *as, bool lock)
845
{
846
    ASSERT(as_operations);
847
    ASSERT(as_operations->page_table_lock);
848
 
849
    as_operations->page_table_lock(as, lock);
850
}
851
 
852
/** Unlock page table.
853
 *
854
 * @param as Address space.
1248 jermar 855
 * @param unlock If false, do not attempt to unlock as->lock.
1044 jermar 856
 */
857
void page_table_unlock(as_t *as, bool unlock)
858
{
859
    ASSERT(as_operations);
860
    ASSERT(as_operations->page_table_unlock);
861
 
862
    as_operations->page_table_unlock(as, unlock);
863
}
864
 
977 jermar 865
 
866
/** Find address space area and lock it.
867
 *
868
 * The address space must be locked and interrupts must be disabled.
869
 *
870
 * @param as Address space.
871
 * @param va Virtual address.
872
 *
873
 * @return Locked address space area containing va on success or NULL on failure.
874
 */
875
as_area_t *find_area_and_lock(as_t *as, __address va)
876
{
877
    as_area_t *a;
1147 jermar 878
    btree_node_t *leaf, *lnode;
879
    int i;
977 jermar 880
 
1147 jermar 881
    a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
882
    if (a) {
883
        /* va is the base address of an address space area */
1380 jermar 884
        mutex_lock(&a->lock);
1147 jermar 885
        return a;
886
    }
887
 
888
    /*
1150 jermar 889
     * Search the leaf node and the righmost record of its left neighbour
1147 jermar 890
     * to find out whether this is a miss or va belongs to an address
891
     * space area found there.
892
     */
893
 
894
    /* First, search the leaf node itself. */
895
    for (i = 0; i < leaf->keys; i++) {
896
        a = (as_area_t *) leaf->value[i];
1380 jermar 897
        mutex_lock(&a->lock);
1147 jermar 898
        if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) {
899
            return a;
900
        }
1380 jermar 901
        mutex_unlock(&a->lock);
1147 jermar 902
    }
977 jermar 903
 
1147 jermar 904
    /*
1150 jermar 905
     * Second, locate the left neighbour and test its last record.
1148 jermar 906
     * Because of its position in the B+tree, it must have base < va.
1147 jermar 907
     */
1150 jermar 908
    if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
1147 jermar 909
        a = (as_area_t *) lnode->value[lnode->keys - 1];
1380 jermar 910
        mutex_lock(&a->lock);
1147 jermar 911
        if (va < a->base + a->pages * PAGE_SIZE) {
1048 jermar 912
            return a;
1147 jermar 913
        }
1380 jermar 914
        mutex_unlock(&a->lock);
977 jermar 915
    }
916
 
917
    return NULL;
918
}
1048 jermar 919
 
920
/** Check area conflicts with other areas.
921
 *
922
 * The address space must be locked and interrupts must be disabled.
923
 *
924
 * @param as Address space.
925
 * @param va Starting virtual address of the area being tested.
926
 * @param size Size of the area being tested.
927
 * @param avoid_area Do not touch this area.
928
 *
929
 * @return True if there is no conflict, false otherwise.
930
 */
931
bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area)
932
{
933
    as_area_t *a;
1147 jermar 934
    btree_node_t *leaf, *node;
935
    int i;
1048 jermar 936
 
1070 jermar 937
    /*
938
     * We don't want any area to have conflicts with NULL page.
939
     */
940
    if (overlaps(va, size, NULL, PAGE_SIZE))
941
        return false;
942
 
1147 jermar 943
    /*
944
     * The leaf node is found in O(log n), where n is proportional to
945
     * the number of address space areas belonging to as.
946
     * The check for conflicts is then attempted on the rightmost
1150 jermar 947
     * record in the left neighbour, the leftmost record in the right
948
     * neighbour and all records in the leaf node itself.
1147 jermar 949
     */
1048 jermar 950
 
1147 jermar 951
    if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) {
952
        if (a != avoid_area)
953
            return false;
954
    }
955
 
956
    /* First, check the two border cases. */
1150 jermar 957
    if ((node = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
1147 jermar 958
        a = (as_area_t *) node->value[node->keys - 1];
1380 jermar 959
        mutex_lock(&a->lock);
1147 jermar 960
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1380 jermar 961
            mutex_unlock(&a->lock);
1147 jermar 962
            return false;
963
        }
1380 jermar 964
        mutex_unlock(&a->lock);
1147 jermar 965
    }
1150 jermar 966
    if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) {
1147 jermar 967
        a = (as_area_t *) node->value[0];
1380 jermar 968
        mutex_lock(&a->lock);
1147 jermar 969
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1380 jermar 970
            mutex_unlock(&a->lock);
1147 jermar 971
            return false;
972
        }
1380 jermar 973
        mutex_unlock(&a->lock);
1147 jermar 974
    }
975
 
976
    /* Second, check the leaf node. */
977
    for (i = 0; i < leaf->keys; i++) {
978
        a = (as_area_t *) leaf->value[i];
979
 
1048 jermar 980
        if (a == avoid_area)
981
            continue;
1147 jermar 982
 
1380 jermar 983
        mutex_lock(&a->lock);
1147 jermar 984
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1380 jermar 985
            mutex_unlock(&a->lock);
1147 jermar 986
            return false;
987
        }
1380 jermar 988
        mutex_unlock(&a->lock);
1048 jermar 989
    }
990
 
1070 jermar 991
    /*
992
     * So far, the area does not conflict with other areas.
993
     * Check if it doesn't conflict with kernel address space.
994
     */  
995
    if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
996
        return !overlaps(va, size,
997
            KERNEL_ADDRESS_SPACE_START, KERNEL_ADDRESS_SPACE_END-KERNEL_ADDRESS_SPACE_START);
998
    }
999
 
1048 jermar 1000
    return true;
1001
}
1235 jermar 1002
 
1380 jermar 1003
/** Return size of the address space area with given base.  */
1329 palkovsky 1004
size_t as_get_size(__address base)
1005
{
1006
    ipl_t ipl;
1007
    as_area_t *src_area;
1008
    size_t size;
1009
 
1010
    ipl = interrupts_disable();
1011
    src_area = find_area_and_lock(AS, base);
1012
    if (src_area){
1013
        size = src_area->pages * PAGE_SIZE;
1380 jermar 1014
        mutex_unlock(&src_area->lock);
1329 palkovsky 1015
    } else {
1016
        size = 0;
1017
    }
1018
    interrupts_restore(ipl);
1019
    return size;
1020
}
1021
 
1387 jermar 1022
/** Mark portion of address space area as used.
1023
 *
1024
 * The address space area must be already locked.
1025
 *
1026
 * @param a Address space area.
1027
 * @param page First page to be marked.
1028
 * @param count Number of page to be marked.
1029
 *
1030
 * @return 0 on failure and 1 on success.
1031
 */
1032
int used_space_insert(as_area_t *a, __address page, count_t count)
1033
{
1034
    btree_node_t *leaf, *node;
1035
    count_t pages;
1036
    int i;
1037
 
1038
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
1039
    ASSERT(count);
1040
 
1041
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
1042
    if (pages) {
1043
        /*
1044
         * We hit the beginning of some used space.
1045
         */
1046
        return 0;
1047
    }
1048
 
1049
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
1050
    if (node) {
1051
        __address left_pg = node->key[node->keys - 1], right_pg = leaf->key[0];
1052
        count_t left_cnt = (count_t) node->value[node->keys - 1], right_cnt = (count_t) leaf->value[0];
1053
 
1054
        /*
1055
         * Examine the possibility that the interval fits
1056
         * somewhere between the rightmost interval of
1057
         * the left neigbour and the first interval of the leaf.
1058
         */
1059
 
1060
        if (page >= right_pg) {
1061
            /* Do nothing. */
1062
        } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1063
            /* The interval intersects with the left interval. */
1064
            return 0;
1065
        } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1066
            /* The interval intersects with the right interval. */
1067
            return 0;          
1068
        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
1069
            /* The interval can be added by merging the two already present intervals. */
1403 jermar 1070
            node->value[node->keys - 1] += count + right_cnt;
1387 jermar 1071
            btree_remove(&a->used_space, right_pg, leaf);
1072
            return 1;
1073
        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
1074
            /* The interval can be added by simply growing the left interval. */
1403 jermar 1075
            node->value[node->keys - 1] += count;
1387 jermar 1076
            return 1;
1077
        } else if (page + count*PAGE_SIZE == right_pg) {
1078
            /*
1079
             * The interval can be addded by simply moving base of the right
1080
             * interval down and increasing its size accordingly.
1081
             */
1403 jermar 1082
            leaf->value[0] += count;
1387 jermar 1083
            leaf->key[0] = page;
1084
            return 1;
1085
        } else {
1086
            /*
1087
             * The interval is between both neigbouring intervals,
1088
             * but cannot be merged with any of them.
1089
             */
1090
            btree_insert(&a->used_space, page, (void *) count, leaf);
1091
            return 1;
1092
        }
1093
    } else if (page < leaf->key[0]) {
1094
        __address right_pg = leaf->key[0];
1095
        count_t right_cnt = (count_t) leaf->value[0];
1096
 
1097
        /*
1098
         * Investigate the border case in which the left neighbour does not
1099
         * exist but the interval fits from the left.
1100
         */
1101
 
1102
        if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1103
            /* The interval intersects with the right interval. */
1104
            return 0;
1105
        } else if (page + count*PAGE_SIZE == right_pg) {
1106
            /*
1107
             * The interval can be added by moving the base of the right interval down
1108
             * and increasing its size accordingly.
1109
             */
1110
            leaf->key[0] = page;
1403 jermar 1111
            leaf->value[0] += count;
1387 jermar 1112
            return 1;
1113
        } else {
1114
            /*
1115
             * The interval doesn't adjoin with the right interval.
1116
             * It must be added individually.
1117
             */
1118
            btree_insert(&a->used_space, page, (void *) count, leaf);
1119
            return 1;
1120
        }
1121
    }
1122
 
1123
    node = btree_leaf_node_right_neighbour(&a->used_space, leaf);
1124
    if (node) {
1125
        __address left_pg = leaf->key[leaf->keys - 1], right_pg = node->key[0];
1126
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1], right_cnt = (count_t) node->value[0];
1127
 
1128
        /*
1129
         * Examine the possibility that the interval fits
1130
         * somewhere between the leftmost interval of
1131
         * the right neigbour and the last interval of the leaf.
1132
         */
1133
 
1134
        if (page < left_pg) {
1135
            /* Do nothing. */
1136
        } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1137
            /* The interval intersects with the left interval. */
1138
            return 0;
1139
        } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1140
            /* The interval intersects with the right interval. */
1141
            return 0;          
1142
        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
1143
            /* The interval can be added by merging the two already present intervals. */
1403 jermar 1144
            leaf->value[leaf->keys - 1] += count + right_cnt;
1387 jermar 1145
            btree_remove(&a->used_space, right_pg, node);
1146
            return 1;
1147
        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
1148
            /* The interval can be added by simply growing the left interval. */
1403 jermar 1149
            leaf->value[leaf->keys - 1] +=  count;
1387 jermar 1150
            return 1;
1151
        } else if (page + count*PAGE_SIZE == right_pg) {
1152
            /*
1153
             * The interval can be addded by simply moving base of the right
1154
             * interval down and increasing its size accordingly.
1155
             */
1403 jermar 1156
            node->value[0] += count;
1387 jermar 1157
            node->key[0] = page;
1158
            return 1;
1159
        } else {
1160
            /*
1161
             * The interval is between both neigbouring intervals,
1162
             * but cannot be merged with any of them.
1163
             */
1164
            btree_insert(&a->used_space, page, (void *) count, leaf);
1165
            return 1;
1166
        }
1167
    } else if (page >= leaf->key[leaf->keys - 1]) {
1168
        __address left_pg = leaf->key[leaf->keys - 1];
1169
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
1170
 
1171
        /*
1172
         * Investigate the border case in which the right neighbour does not
1173
         * exist but the interval fits from the right.
1174
         */
1175
 
1176
        if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1403 jermar 1177
            /* The interval intersects with the left interval. */
1387 jermar 1178
            return 0;
1179
        } else if (left_pg + left_cnt*PAGE_SIZE == page) {
1180
            /* The interval can be added by growing the left interval. */
1403 jermar 1181
            leaf->value[leaf->keys - 1] += count;
1387 jermar 1182
            return 1;
1183
        } else {
1184
            /*
1185
             * The interval doesn't adjoin with the left interval.
1186
             * It must be added individually.
1187
             */
1188
            btree_insert(&a->used_space, page, (void *) count, leaf);
1189
            return 1;
1190
        }
1191
    }
1192
 
1193
    /*
1194
     * Note that if the algorithm made it thus far, the interval can fit only
1195
     * between two other intervals of the leaf. The two border cases were already
1196
     * resolved.
1197
     */
1198
    for (i = 1; i < leaf->keys; i++) {
1199
        if (page < leaf->key[i]) {
1200
            __address left_pg = leaf->key[i - 1], right_pg = leaf->key[i];
1201
            count_t left_cnt = (count_t) leaf->value[i - 1], right_cnt = (count_t) leaf->value[i];
1202
 
1203
            /*
1204
             * The interval fits between left_pg and right_pg.
1205
             */
1206
 
1207
            if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1208
                /* The interval intersects with the left interval. */
1209
                return 0;
1210
            } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1211
                /* The interval intersects with the right interval. */
1212
                return 0;          
1213
            } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
1214
                /* The interval can be added by merging the two already present intervals. */
1403 jermar 1215
                leaf->value[i - 1] += count + right_cnt;
1387 jermar 1216
                btree_remove(&a->used_space, right_pg, leaf);
1217
                return 1;
1218
            } else if (page == left_pg + left_cnt*PAGE_SIZE) {
1219
                /* The interval can be added by simply growing the left interval. */
1403 jermar 1220
                leaf->value[i - 1] += count;
1387 jermar 1221
                return 1;
1222
            } else if (page + count*PAGE_SIZE == right_pg) {
1223
                /*
1224
                     * The interval can be addded by simply moving base of the right
1225
                 * interval down and increasing its size accordingly.
1226
                 */
1403 jermar 1227
                leaf->value[i] += count;
1387 jermar 1228
                leaf->key[i] = page;
1229
                return 1;
1230
            } else {
1231
                /*
1232
                 * The interval is between both neigbouring intervals,
1233
                 * but cannot be merged with any of them.
1234
                 */
1235
                btree_insert(&a->used_space, page, (void *) count, leaf);
1236
                return 1;
1237
            }
1238
        }
1239
    }
1240
 
1241
    panic("Inconsistency detected while adding %d pages of used space at %P.\n", count, page);
1242
}
1243
 
1244
/** Mark portion of address space area as unused.
1245
 *
1246
 * The address space area must be already locked.
1247
 *
1248
 * @param a Address space area.
1249
 * @param page First page to be marked.
1250
 * @param count Number of page to be marked.
1251
 *
1252
 * @return 0 on failure and 1 on success.
1253
 */
1254
int used_space_remove(as_area_t *a, __address page, count_t count)
1255
{
1256
    btree_node_t *leaf, *node;
1257
    count_t pages;
1258
    int i;
1259
 
1260
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
1261
    ASSERT(count);
1262
 
1263
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
1264
    if (pages) {
1265
        /*
1266
         * We are lucky, page is the beginning of some interval.
1267
         */
1268
        if (count > pages) {
1269
            return 0;
1270
        } else if (count == pages) {
1271
            btree_remove(&a->used_space, page, leaf);
1403 jermar 1272
            return 1;
1387 jermar 1273
        } else {
1274
            /*
1275
             * Find the respective interval.
1276
             * Decrease its size and relocate its start address.
1277
             */
1278
            for (i = 0; i < leaf->keys; i++) {
1279
                if (leaf->key[i] == page) {
1280
                    leaf->key[i] += count*PAGE_SIZE;
1403 jermar 1281
                    leaf->value[i] -= count;
1387 jermar 1282
                    return 1;
1283
                }
1284
            }
1285
            goto error;
1286
        }
1287
    }
1288
 
1289
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
1290
    if (node && page < leaf->key[0]) {
1291
        __address left_pg = node->key[node->keys - 1];
1292
        count_t left_cnt = (count_t) node->value[node->keys - 1];
1293
 
1294
        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
1295
            if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
1296
                /*
1297
                 * The interval is contained in the rightmost interval
1298
                 * of the left neighbour and can be removed by
1299
                 * updating the size of the bigger interval.
1300
                 */
1403 jermar 1301
                node->value[node->keys - 1] -= count;
1387 jermar 1302
                return 1;
1303
            } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
1403 jermar 1304
                count_t new_cnt;
1387 jermar 1305
 
1306
                /*
1307
                 * The interval is contained in the rightmost interval
1308
                 * of the left neighbour but its removal requires
1309
                 * both updating the size of the original interval and
1310
                 * also inserting a new interval.
1311
                 */
1403 jermar 1312
                new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
1313
                node->value[node->keys - 1] -= count + new_cnt;
1387 jermar 1314
                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
1315
                return 1;
1316
            }
1317
        }
1318
        return 0;
1319
    } else if (page < leaf->key[0]) {
1320
        return 0;
1321
    }
1322
 
1323
    if (page > leaf->key[leaf->keys - 1]) {
1324
        __address left_pg = leaf->key[leaf->keys - 1];
1325
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
1326
 
1327
        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
1328
            if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
1329
                /*
1330
                 * The interval is contained in the rightmost interval
1331
                 * of the leaf and can be removed by updating the size
1332
                 * of the bigger interval.
1333
                 */
1403 jermar 1334
                leaf->value[leaf->keys - 1] -= count;
1387 jermar 1335
                return 1;
1336
            } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
1403 jermar 1337
                count_t new_cnt;
1387 jermar 1338
 
1339
                /*
1340
                 * The interval is contained in the rightmost interval
1341
                 * of the leaf but its removal requires both updating
1342
                 * the size of the original interval and
1343
                 * also inserting a new interval.
1344
                 */
1403 jermar 1345
                new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
1346
                leaf->value[leaf->keys - 1] -= count + new_cnt;
1387 jermar 1347
                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
1348
                return 1;
1349
            }
1350
        }
1351
        return 0;
1352
    }  
1353
 
1354
    /*
1355
     * The border cases have been already resolved.
1356
     * Now the interval can be only between intervals of the leaf.
1357
     */
1358
    for (i = 1; i < leaf->keys - 1; i++) {
1359
        if (page < leaf->key[i]) {
1360
            __address left_pg = leaf->key[i - 1];
1361
            count_t left_cnt = (count_t) leaf->value[i - 1];
1362
 
1363
            /*
1364
             * Now the interval is between intervals corresponding to (i - 1) and i.
1365
             */
1366
            if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
1367
                if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
1368
                    /*
1369
                    * The interval is contained in the interval (i - 1)
1370
                     * of the leaf and can be removed by updating the size
1371
                     * of the bigger interval.
1372
                     */
1403 jermar 1373
                    leaf->value[i - 1] -= count;
1387 jermar 1374
                    return 1;
1375
                } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
1403 jermar 1376
                    count_t new_cnt;
1387 jermar 1377
 
1378
                    /*
1379
                     * The interval is contained in the interval (i - 1)
1380
                     * of the leaf but its removal requires both updating
1381
                     * the size of the original interval and
1382
                     * also inserting a new interval.
1383
                     */
1403 jermar 1384
                    new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
1385
                    leaf->value[i - 1] -= count + new_cnt;
1387 jermar 1386
                    btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
1387
                    return 1;
1388
                }
1389
            }
1390
            return 0;
1391
        }
1392
    }
1393
 
1394
error:
1395
    panic("Inconsistency detected while removing %d pages of used space from %P.\n", count, page);
1396
}
1397
 
1409 jermar 1398
/** Remove reference to address space area share info.
1399
 *
1400
 * If the reference count drops to 0, the sh_info is deallocated.
1401
 *
1402
 * @param sh_info Pointer to address space area share info.
1403
 */
1404
void sh_info_remove_reference(share_info_t *sh_info)
1405
{
1406
    bool dealloc = false;
1407
 
1408
    mutex_lock(&sh_info->lock);
1409
    ASSERT(sh_info->refcount);
1410
    if (--sh_info->refcount == 0) {
1411
        dealloc = true;
1412
        bool cond;
1413
 
1414
        /*
1415
         * Now walk carefully the pagemap B+tree and free/remove
1416
         * reference from all frames found there.
1417
         */
1418
        for (cond = true; cond;) {
1419
            btree_node_t *node;
1420
 
1421
            ASSERT(!list_empty(&sh_info->pagemap.leaf_head));
1422
            node = list_get_instance(sh_info->pagemap.leaf_head.next, btree_node_t, leaf_link);
1423
            if ((cond = node->keys)) {
1424
                frame_free(ADDR2PFN((__address) node->value[0]));
1425
                btree_remove(&sh_info->pagemap, node->key[0], node);
1426
            }
1427
        }
1428
 
1429
    }
1430
    mutex_unlock(&sh_info->lock);
1431
 
1432
    if (dealloc) {
1433
        btree_destroy(&sh_info->pagemap);
1434
        free(sh_info);
1435
    }
1436
}
1437
 
1235 jermar 1438
/*
1439
 * Address space related syscalls.
1440
 */
1441
 
1442
/** Wrapper for as_area_create(). */
1443
__native sys_as_area_create(__address address, size_t size, int flags)
1444
{
1424 jermar 1445
    if (as_area_create(AS, flags | AS_AREA_CACHEABLE, size, address, AS_AREA_ATTR_NONE, &anon_backend, NULL))
1235 jermar 1446
        return (__native) address;
1447
    else
1448
        return (__native) -1;
1449
}
1450
 
1451
/** Wrapper for as_area_resize. */
1452
__native sys_as_area_resize(__address address, size_t size, int flags)
1453
{
1306 jermar 1454
    return (__native) as_area_resize(AS, address, size, 0);
1235 jermar 1455
}
1456
 
1306 jermar 1457
/** Wrapper for as_area_destroy. */
1458
__native sys_as_area_destroy(__address address)
1459
{
1460
    return (__native) as_area_destroy(AS, address);
1461
}