Subversion Repositories HelenOS

Rev

Rev 1383 | Rev 1403 | 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
 
1380 jermar 79
/** Address space lock. It protects inactive_as_with_asid_head. Must be acquired before as_t mutex. */
823 jermar 80
SPINLOCK_INITIALIZE(as_lock);
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);
754 jermar 92
static int get_area_flags(as_area_t *a);
977 jermar 93
static as_area_t *find_area_and_lock(as_t *as, __address va);
1048 jermar 94
static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area);
1387 jermar 95
int used_space_insert(as_area_t *a, __address page, count_t count);
96
int used_space_remove(as_area_t *a, __address page, count_t count);
703 jermar 97
 
756 jermar 98
/** Initialize address space subsystem. */
99
void as_init(void)
100
{
101
    as_arch_init();
789 palkovsky 102
    AS_KERNEL = as_create(FLAG_AS_KERNEL);
1383 decky 103
    if (!AS_KERNEL)
104
        panic("can't create kernel address space\n");
105
 
756 jermar 106
}
107
 
757 jermar 108
/** Create address space.
109
 *
110
 * @param flags Flags that influence way in wich the address space is created.
111
 */
756 jermar 112
as_t *as_create(int flags)
703 jermar 113
{
114
    as_t *as;
115
 
822 palkovsky 116
    as = (as_t *) malloc(sizeof(as_t), 0);
823 jermar 117
    link_initialize(&as->inactive_as_with_asid_link);
1380 jermar 118
    mutex_initialize(&as->lock);
1147 jermar 119
    btree_create(&as->as_area_btree);
822 palkovsky 120
 
121
    if (flags & FLAG_AS_KERNEL)
122
        as->asid = ASID_KERNEL;
123
    else
124
        as->asid = ASID_INVALID;
125
 
823 jermar 126
    as->refcount = 0;
822 palkovsky 127
    as->page_table = page_table_create(flags);
703 jermar 128
 
129
    return as;
130
}
131
 
973 palkovsky 132
/** Free Adress space */
133
void as_free(as_t *as)
134
{
135
    ASSERT(as->refcount == 0);
136
 
137
    /* TODO: free as_areas and other resources held by as */
138
    /* TODO: free page table */
139
    free(as);
140
}
141
 
703 jermar 142
/** Create address space area of common attributes.
143
 *
144
 * The created address space area is added to the target address space.
145
 *
146
 * @param as Target address space.
1239 jermar 147
 * @param flags Flags of the area memory.
1048 jermar 148
 * @param size Size of area.
703 jermar 149
 * @param base Base address of area.
1239 jermar 150
 * @param attrs Attributes of the area.
703 jermar 151
 *
152
 * @return Address space area on success or NULL on failure.
153
 */
1239 jermar 154
as_area_t *as_area_create(as_t *as, int flags, size_t size, __address base, int attrs)
703 jermar 155
{
156
    ipl_t ipl;
157
    as_area_t *a;
158
 
159
    if (base % PAGE_SIZE)
1048 jermar 160
        return NULL;
161
 
1233 jermar 162
    if (!size)
163
        return NULL;
164
 
1048 jermar 165
    /* Writeable executable areas are not supported. */
166
    if ((flags & AS_AREA_EXEC) && (flags & AS_AREA_WRITE))
167
        return NULL;
703 jermar 168
 
169
    ipl = interrupts_disable();
1380 jermar 170
    mutex_lock(&as->lock);
703 jermar 171
 
1048 jermar 172
    if (!check_area_conflicts(as, base, size, NULL)) {
1380 jermar 173
        mutex_unlock(&as->lock);
1048 jermar 174
        interrupts_restore(ipl);
175
        return NULL;
176
    }
703 jermar 177
 
822 palkovsky 178
    a = (as_area_t *) malloc(sizeof(as_area_t), 0);
703 jermar 179
 
1380 jermar 180
    mutex_initialize(&a->lock);
822 palkovsky 181
 
1026 jermar 182
    a->flags = flags;
1239 jermar 183
    a->attributes = attrs;
1048 jermar 184
    a->pages = SIZE2FRAMES(size);
822 palkovsky 185
    a->base = base;
1387 jermar 186
    btree_create(&a->used_space);
822 palkovsky 187
 
1147 jermar 188
    btree_insert(&as->as_area_btree, base, (void *) a, NULL);
822 palkovsky 189
 
1380 jermar 190
    mutex_unlock(&as->lock);
703 jermar 191
    interrupts_restore(ipl);
704 jermar 192
 
703 jermar 193
    return a;
194
}
195
 
1235 jermar 196
/** Find address space area and change it.
197
 *
198
 * @param as Address space.
199
 * @param address Virtual address belonging to the area to be changed. Must be page-aligned.
200
 * @param size New size of the virtual memory block starting at address.
201
 * @param flags Flags influencing the remap operation. Currently unused.
202
 *
1306 jermar 203
 * @return Zero on success or a value from @ref errno.h otherwise.
1235 jermar 204
 */
1306 jermar 205
int as_area_resize(as_t *as, __address address, size_t size, int flags)
1235 jermar 206
{
1306 jermar 207
    as_area_t *area;
1235 jermar 208
    ipl_t ipl;
209
    size_t pages;
210
 
211
    ipl = interrupts_disable();
1380 jermar 212
    mutex_lock(&as->lock);
1235 jermar 213
 
214
    /*
215
     * Locate the area.
216
     */
217
    area = find_area_and_lock(as, address);
218
    if (!area) {
1380 jermar 219
        mutex_unlock(&as->lock);
1235 jermar 220
        interrupts_restore(ipl);
1306 jermar 221
        return ENOENT;
1235 jermar 222
    }
223
 
224
    if (area->flags & AS_AREA_DEVICE) {
225
        /*
226
         * Remapping of address space areas associated
227
         * with memory mapped devices is not supported.
228
         */
1380 jermar 229
        mutex_unlock(&area->lock);
230
        mutex_unlock(&as->lock);
1235 jermar 231
        interrupts_restore(ipl);
1306 jermar 232
        return ENOTSUP;
1235 jermar 233
    }
234
 
235
    pages = SIZE2FRAMES((address - area->base) + size);
236
    if (!pages) {
237
        /*
238
         * Zero size address space areas are not allowed.
239
         */
1380 jermar 240
        mutex_unlock(&area->lock);
241
        mutex_unlock(&as->lock);
1235 jermar 242
        interrupts_restore(ipl);
1306 jermar 243
        return EPERM;
1235 jermar 244
    }
245
 
246
    if (pages < area->pages) {
247
        int i;
248
 
249
        /*
250
         * Shrinking the area.
251
         * No need to check for overlaps.
252
         */
253
        for (i = pages; i < area->pages; i++) {
254
            pte_t *pte;
255
 
256
            /*
257
             * Releasing physical memory.
258
             * This depends on the fact that the memory was allocated using frame_alloc().
259
             */
260
            page_table_lock(as, false);
261
            pte = page_mapping_find(as, area->base + i*PAGE_SIZE);
262
            if (pte && PTE_VALID(pte)) {
263
                __address frame;
264
 
265
                ASSERT(PTE_PRESENT(pte));
266
                frame = PTE_GET_FRAME(pte);
267
                page_mapping_remove(as, area->base + i*PAGE_SIZE);
268
                page_table_unlock(as, false);
269
 
270
                frame_free(ADDR2PFN(frame));
271
            } else {
272
                page_table_unlock(as, false);
273
            }
274
        }
275
        /*
276
         * Invalidate TLB's.
277
         */
278
        tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
279
        tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
280
        tlb_shootdown_finalize();
281
    } else {
282
        /*
283
         * Growing the area.
284
         * Check for overlaps with other address space areas.
285
         */
286
        if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
1380 jermar 287
            mutex_unlock(&area->lock);
288
            mutex_unlock(&as->lock);       
1235 jermar 289
            interrupts_restore(ipl);
1306 jermar 290
            return EADDRNOTAVAIL;
1235 jermar 291
        }
292
    }
293
 
294
    area->pages = pages;
295
 
1380 jermar 296
    mutex_unlock(&area->lock);
297
    mutex_unlock(&as->lock);
1235 jermar 298
    interrupts_restore(ipl);
299
 
1306 jermar 300
    return 0;
1235 jermar 301
}
302
 
1306 jermar 303
/** Destroy address space area.
304
 *
305
 * @param as Address space.
306
 * @param address Address withing the area to be deleted.
307
 *
308
 * @return Zero on success or a value from @ref errno.h on failure.
309
 */
310
int as_area_destroy(as_t *as, __address address)
311
{
312
    as_area_t *area;
313
    __address base;
314
    ipl_t ipl;
315
    int i;
316
 
317
    ipl = interrupts_disable();
1380 jermar 318
    mutex_lock(&as->lock);
1306 jermar 319
 
320
    area = find_area_and_lock(as, address);
321
    if (!area) {
1380 jermar 322
        mutex_unlock(&as->lock);
1306 jermar 323
        interrupts_restore(ipl);
324
        return ENOENT;
325
    }
326
 
327
    base = area->base; 
328
    for (i = 0; i < area->pages; i++) {
329
        pte_t *pte;
330
 
331
        /*
332
         * Releasing physical memory.
333
         * Areas mapping memory-mapped devices are treated differently than
334
         * areas backing frame_alloc()'ed memory.
335
         */
336
        page_table_lock(as, false);
337
        pte = page_mapping_find(as, area->base + i*PAGE_SIZE);
338
        if (pte && PTE_VALID(pte)) {
339
            ASSERT(PTE_PRESENT(pte));
340
            page_mapping_remove(as, area->base + i*PAGE_SIZE);
341
            if (area->flags & AS_AREA_DEVICE) {
342
                __address frame;
343
                frame = PTE_GET_FRAME(pte);
344
                frame_free(ADDR2PFN(frame));
345
            }
346
            page_table_unlock(as, false);
347
        } else {
348
            page_table_unlock(as, false);
349
        }
350
    }
351
    /*
352
     * Invalidate TLB's.
353
     */
354
    tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base, area->pages);
355
    tlb_invalidate_pages(AS->asid, area->base, area->pages);
356
    tlb_shootdown_finalize();
357
 
1309 jermar 358
    area->attributes |= AS_AREA_ATTR_PARTIAL;
1380 jermar 359
    mutex_unlock(&area->lock);
1306 jermar 360
 
361
    /*
362
     * Remove the empty area from address space.
363
     */
364
    btree_remove(&AS->as_area_btree, base, NULL);
365
 
1309 jermar 366
    free(area);
367
 
1380 jermar 368
    mutex_unlock(&AS->lock);
1306 jermar 369
    interrupts_restore(ipl);
370
    return 0;
371
}
372
 
1329 palkovsky 373
/** Steal address space area from another task.
1235 jermar 374
 *
1329 palkovsky 375
 * Address space area is stolen from another task
376
 * Moreover, any existing mapping
1235 jermar 377
 * is copied as well, providing thus a mechanism
378
 * for sharing group of pages. The source address
379
 * space area and any associated mapping is preserved.
380
 *
1329 palkovsky 381
 * @param src_task Pointer of source task
1239 jermar 382
 * @param src_base Base address of the source address space area.
1329 palkovsky 383
 * @param acc_size Expected size of the source area
384
 * @param dst_base Target base address
1235 jermar 385
 *
1306 jermar 386
 * @return Zero on success or ENOENT if there is no such task or
1235 jermar 387
 *     if there is no such address space area,
388
 *     EPERM if there was a problem in accepting the area or
389
 *     ENOMEM if there was a problem in allocating destination
390
 *     address space area.
391
 */
1329 palkovsky 392
int as_area_steal(task_t *src_task, __address src_base, size_t acc_size,
393
          __address dst_base)
1235 jermar 394
{
395
    ipl_t ipl;
396
    count_t i;
1329 palkovsky 397
    as_t *src_as;      
1239 jermar 398
    int src_flags;
399
    size_t src_size;
400
    as_area_t *src_area, *dst_area;
1329 palkovsky 401
 
1235 jermar 402
    ipl = interrupts_disable();
1329 palkovsky 403
    spinlock_lock(&src_task->lock);
404
    src_as = src_task->as;
1235 jermar 405
 
1380 jermar 406
    mutex_lock(&src_as->lock);
1329 palkovsky 407
    src_area = find_area_and_lock(src_as, src_base);
1239 jermar 408
    if (!src_area) {
1238 jermar 409
        /*
410
         * Could not find the source address space area.
411
         */
1329 palkovsky 412
        spinlock_unlock(&src_task->lock);
1380 jermar 413
        mutex_unlock(&src_as->lock);
1238 jermar 414
        interrupts_restore(ipl);
415
        return ENOENT;
416
    }
1239 jermar 417
    src_size = src_area->pages * PAGE_SIZE;
418
    src_flags = src_area->flags;
1380 jermar 419
    mutex_unlock(&src_area->lock);
420
    mutex_unlock(&src_as->lock);
1235 jermar 421
 
1329 palkovsky 422
 
423
    if (src_size != acc_size) {
424
        spinlock_unlock(&src_task->lock);
1235 jermar 425
        interrupts_restore(ipl);
426
        return EPERM;
427
    }
428
    /*
1239 jermar 429
     * Create copy of the source address space area.
430
     * The destination area is created with AS_AREA_ATTR_PARTIAL
431
     * attribute set which prevents race condition with
432
     * preliminary as_page_fault() calls.
1235 jermar 433
     */
1329 palkovsky 434
    dst_area = as_area_create(AS, src_flags, src_size, dst_base, AS_AREA_ATTR_PARTIAL);
1239 jermar 435
    if (!dst_area) {
1235 jermar 436
        /*
437
         * Destination address space area could not be created.
438
         */
1329 palkovsky 439
        spinlock_unlock(&src_task->lock);
1235 jermar 440
        interrupts_restore(ipl);
441
        return ENOMEM;
442
    }
443
 
1329 palkovsky 444
    spinlock_unlock(&src_task->lock);
1235 jermar 445
 
446
    /*
447
     * Avoid deadlock by first locking the address space with lower address.
448
     */
1329 palkovsky 449
    if (AS < src_as) {
1380 jermar 450
        mutex_lock(&AS->lock);
451
        mutex_lock(&src_as->lock);
1235 jermar 452
    } else {
1380 jermar 453
        mutex_lock(&AS->lock);
454
        mutex_lock(&src_as->lock);
1235 jermar 455
    }
456
 
1239 jermar 457
    for (i = 0; i < SIZE2FRAMES(src_size); i++) {
1235 jermar 458
        pte_t *pte;
459
        __address frame;
460
 
1329 palkovsky 461
        page_table_lock(src_as, false);
462
        pte = page_mapping_find(src_as, src_base + i*PAGE_SIZE);
1235 jermar 463
        if (pte && PTE_VALID(pte)) {
464
            ASSERT(PTE_PRESENT(pte));
465
            frame = PTE_GET_FRAME(pte);
1239 jermar 466
            if (!(src_flags & AS_AREA_DEVICE))
1236 jermar 467
                frame_reference_add(ADDR2PFN(frame));
1329 palkovsky 468
            page_table_unlock(src_as, false);
1235 jermar 469
        } else {
1329 palkovsky 470
            page_table_unlock(src_as, false);
1235 jermar 471
            continue;
472
        }
473
 
1329 palkovsky 474
        page_table_lock(AS, false);
475
        page_mapping_insert(AS, dst_base + i*PAGE_SIZE, frame, area_flags_to_page_flags(src_flags));
476
        page_table_unlock(AS, false);
1235 jermar 477
    }
1239 jermar 478
 
479
    /*
480
     * Now the destination address space area has been
481
     * fully initialized. Clear the AS_AREA_ATTR_PARTIAL
482
     * attribute.
483
     */
1380 jermar 484
    mutex_lock(&dst_area->lock);
1239 jermar 485
    dst_area->attributes &= ~AS_AREA_ATTR_PARTIAL;
1380 jermar 486
    mutex_unlock(&dst_area->lock);
1235 jermar 487
 
1380 jermar 488
    mutex_unlock(&AS->lock);
489
    mutex_unlock(&src_as->lock);
1235 jermar 490
    interrupts_restore(ipl);
491
 
492
    return 0;
493
}
494
 
754 jermar 495
/** Initialize mapping for one page of address space.
703 jermar 496
 *
754 jermar 497
 * This functions maps 'page' to 'frame' according
498
 * to attributes of the address space area to
499
 * wich 'page' belongs.
703 jermar 500
 *
840 jermar 501
 * @param as Target address space.
754 jermar 502
 * @param page Virtual page within the area.
503
 * @param frame Physical frame to which page will be mapped.
703 jermar 504
 */
754 jermar 505
void as_set_mapping(as_t *as, __address page, __address frame)
703 jermar 506
{
977 jermar 507
    as_area_t *area;
703 jermar 508
    ipl_t ipl;
509
 
510
    ipl = interrupts_disable();
1044 jermar 511
    page_table_lock(as, true);
703 jermar 512
 
977 jermar 513
    area = find_area_and_lock(as, page);
754 jermar 514
    if (!area) {
515
        panic("page not part of any as_area\n");
516
    }
517
 
756 jermar 518
    page_mapping_insert(as, page, frame, get_area_flags(area));
754 jermar 519
 
1380 jermar 520
    mutex_unlock(&area->lock);
1044 jermar 521
    page_table_unlock(as, true);
703 jermar 522
    interrupts_restore(ipl);
523
}
524
 
525
/** Handle page fault within the current address space.
526
 *
527
 * This is the high-level page fault handler.
528
 * Interrupts are assumed disabled.
529
 *
530
 * @param page Faulting page.
1288 jermar 531
 * @param istate Pointer to interrupted state.
703 jermar 532
 *
1288 jermar 533
 * @return 0 on page fault, 1 on success or 2 if the fault was caused by copy_to_uspace() or copy_from_uspace().
703 jermar 534
 */
1288 jermar 535
int as_page_fault(__address page, istate_t *istate)
703 jermar 536
{
1044 jermar 537
    pte_t *pte;
977 jermar 538
    as_area_t *area;
703 jermar 539
    __address frame;
540
 
1380 jermar 541
    if (!THREAD)
542
        return 0;
543
 
703 jermar 544
    ASSERT(AS);
1044 jermar 545
 
1380 jermar 546
    mutex_lock(&AS->lock);
977 jermar 547
    area = find_area_and_lock(AS, page);   
703 jermar 548
    if (!area) {
549
        /*
550
         * No area contained mapping for 'page'.
551
         * Signal page fault to low-level handler.
552
         */
1380 jermar 553
        mutex_unlock(&AS->lock);
1288 jermar 554
        goto page_fault;
703 jermar 555
    }
556
 
1239 jermar 557
    if (area->attributes & AS_AREA_ATTR_PARTIAL) {
558
        /*
559
         * The address space area is not fully initialized.
560
         * Avoid possible race by returning error.
561
         */
1380 jermar 562
        mutex_unlock(&area->lock);
563
        mutex_unlock(&AS->lock);
1288 jermar 564
        goto page_fault;       
1239 jermar 565
    }
566
 
1179 jermar 567
    ASSERT(!(area->flags & AS_AREA_DEVICE));
568
 
1044 jermar 569
    page_table_lock(AS, false);
570
 
703 jermar 571
    /*
1044 jermar 572
     * To avoid race condition between two page faults
573
     * on the same address, we need to make sure
574
     * the mapping has not been already inserted.
575
     */
576
    if ((pte = page_mapping_find(AS, page))) {
577
        if (PTE_PRESENT(pte)) {
578
            page_table_unlock(AS, false);
1380 jermar 579
            mutex_unlock(&area->lock);
580
            mutex_unlock(&AS->lock);
1044 jermar 581
            return 1;
582
        }
583
    }
584
 
585
    /*
754 jermar 586
     * In general, there can be several reasons that
587
     * can have caused this fault.
588
     *
589
     * - non-existent mapping: the area is a scratch
590
     *   area (e.g. stack) and so far has not been
591
     *   allocated a frame for the faulting page
592
     *
593
     * - non-present mapping: another possibility,
594
     *   currently not implemented, would be frame
595
     *   reuse; when this becomes a possibility,
596
     *   do not forget to distinguish between
597
     *   the different causes
703 jermar 598
     */
814 palkovsky 599
    frame = PFN2ADDR(frame_alloc(ONE_FRAME, 0));
754 jermar 600
    memsetb(PA2KA(frame), FRAME_SIZE, 0);
703 jermar 601
 
602
    /*
603
     * Map 'page' to 'frame'.
604
     * Note that TLB shootdown is not attempted as only new information is being
605
     * inserted into page tables.
606
     */
756 jermar 607
    page_mapping_insert(AS, page, frame, get_area_flags(area));
1044 jermar 608
    page_table_unlock(AS, false);
703 jermar 609
 
1380 jermar 610
    mutex_unlock(&area->lock);
611
    mutex_unlock(&AS->lock);
1288 jermar 612
    return AS_PF_OK;
613
 
614
page_fault:
615
    if (!THREAD)
616
        return AS_PF_FAULT;
617
 
618
    if (THREAD->in_copy_from_uspace) {
619
        THREAD->in_copy_from_uspace = false;
620
        istate_set_retaddr(istate, (__address) &memcpy_from_uspace_failover_address);
621
    } else if (THREAD->in_copy_to_uspace) {
622
        THREAD->in_copy_to_uspace = false;
623
        istate_set_retaddr(istate, (__address) &memcpy_to_uspace_failover_address);
624
    } else {
625
        return AS_PF_FAULT;
626
    }
627
 
628
    return AS_PF_DEFER;
703 jermar 629
}
630
 
823 jermar 631
/** Switch address spaces.
703 jermar 632
 *
1380 jermar 633
 * Note that this function cannot sleep as it is essentially a part of
634
 * the scheduling. Sleeping here would lead to deadlock on wakeup.
635
 *
823 jermar 636
 * @param old Old address space or NULL.
637
 * @param new New address space.
703 jermar 638
 */
823 jermar 639
void as_switch(as_t *old, as_t *new)
703 jermar 640
{
641
    ipl_t ipl;
823 jermar 642
    bool needs_asid = false;
703 jermar 643
 
644
    ipl = interrupts_disable();
823 jermar 645
    spinlock_lock(&as_lock);
703 jermar 646
 
647
    /*
823 jermar 648
     * First, take care of the old address space.
649
     */
650
    if (old) {
1380 jermar 651
        mutex_lock_active(&old->lock);
823 jermar 652
        ASSERT(old->refcount);
653
        if((--old->refcount == 0) && (old != AS_KERNEL)) {
654
            /*
655
             * The old address space is no longer active on
656
             * any processor. It can be appended to the
657
             * list of inactive address spaces with assigned
658
             * ASID.
659
             */
660
             ASSERT(old->asid != ASID_INVALID);
661
             list_append(&old->inactive_as_with_asid_link, &inactive_as_with_asid_head);
662
        }
1380 jermar 663
        mutex_unlock(&old->lock);
823 jermar 664
    }
665
 
666
    /*
667
     * Second, prepare the new address space.
668
     */
1380 jermar 669
    mutex_lock_active(&new->lock);
823 jermar 670
    if ((new->refcount++ == 0) && (new != AS_KERNEL)) {
671
        if (new->asid != ASID_INVALID)
672
            list_remove(&new->inactive_as_with_asid_link);
673
        else
674
            needs_asid = true;  /* defer call to asid_get() until new->lock is released */
675
    }
676
    SET_PTL0_ADDRESS(new->page_table);
1380 jermar 677
    mutex_unlock(&new->lock);
823 jermar 678
 
679
    if (needs_asid) {
680
        /*
681
         * Allocation of new ASID was deferred
682
         * until now in order to avoid deadlock.
683
         */
684
        asid_t asid;
685
 
686
        asid = asid_get();
1380 jermar 687
        mutex_lock_active(&new->lock);
823 jermar 688
        new->asid = asid;
1380 jermar 689
        mutex_unlock(&new->lock);
823 jermar 690
    }
691
    spinlock_unlock(&as_lock);
692
    interrupts_restore(ipl);
693
 
694
    /*
703 jermar 695
     * Perform architecture-specific steps.
727 jermar 696
     * (e.g. write ASID to hardware register etc.)
703 jermar 697
     */
823 jermar 698
    as_install_arch(new);
703 jermar 699
 
823 jermar 700
    AS = new;
703 jermar 701
}
754 jermar 702
 
1235 jermar 703
/** Convert address space area flags to page flags.
754 jermar 704
 *
1235 jermar 705
 * @param aflags Flags of some address space area.
754 jermar 706
 *
1235 jermar 707
 * @return Flags to be passed to page_mapping_insert().
754 jermar 708
 */
1235 jermar 709
int area_flags_to_page_flags(int aflags)
754 jermar 710
{
711
    int flags;
712
 
1178 jermar 713
    flags = PAGE_USER | PAGE_PRESENT;
754 jermar 714
 
1235 jermar 715
    if (aflags & AS_AREA_READ)
1026 jermar 716
        flags |= PAGE_READ;
717
 
1235 jermar 718
    if (aflags & AS_AREA_WRITE)
1026 jermar 719
        flags |= PAGE_WRITE;
720
 
1235 jermar 721
    if (aflags & AS_AREA_EXEC)
1026 jermar 722
        flags |= PAGE_EXEC;
723
 
1235 jermar 724
    if (!(aflags & AS_AREA_DEVICE))
1178 jermar 725
        flags |= PAGE_CACHEABLE;
726
 
754 jermar 727
    return flags;
728
}
756 jermar 729
 
1235 jermar 730
/** Compute flags for virtual address translation subsytem.
731
 *
732
 * The address space area must be locked.
733
 * Interrupts must be disabled.
734
 *
735
 * @param a Address space area.
736
 *
737
 * @return Flags to be used in page_mapping_insert().
738
 */
739
int get_area_flags(as_area_t *a)
740
{
741
    return area_flags_to_page_flags(a->flags);
742
}
743
 
756 jermar 744
/** Create page table.
745
 *
746
 * Depending on architecture, create either address space
747
 * private or global page table.
748
 *
749
 * @param flags Flags saying whether the page table is for kernel address space.
750
 *
751
 * @return First entry of the page table.
752
 */
753
pte_t *page_table_create(int flags)
754
{
755
        ASSERT(as_operations);
756
        ASSERT(as_operations->page_table_create);
757
 
758
        return as_operations->page_table_create(flags);
759
}
977 jermar 760
 
1044 jermar 761
/** Lock page table.
762
 *
763
 * This function should be called before any page_mapping_insert(),
764
 * page_mapping_remove() and page_mapping_find().
765
 *
766
 * Locking order is such that address space areas must be locked
767
 * prior to this call. Address space can be locked prior to this
768
 * call in which case the lock argument is false.
769
 *
770
 * @param as Address space.
1248 jermar 771
 * @param lock If false, do not attempt to lock as->lock.
1044 jermar 772
 */
773
void page_table_lock(as_t *as, bool lock)
774
{
775
    ASSERT(as_operations);
776
    ASSERT(as_operations->page_table_lock);
777
 
778
    as_operations->page_table_lock(as, lock);
779
}
780
 
781
/** Unlock page table.
782
 *
783
 * @param as Address space.
1248 jermar 784
 * @param unlock If false, do not attempt to unlock as->lock.
1044 jermar 785
 */
786
void page_table_unlock(as_t *as, bool unlock)
787
{
788
    ASSERT(as_operations);
789
    ASSERT(as_operations->page_table_unlock);
790
 
791
    as_operations->page_table_unlock(as, unlock);
792
}
793
 
977 jermar 794
 
795
/** Find address space area and lock it.
796
 *
797
 * The address space must be locked and interrupts must be disabled.
798
 *
799
 * @param as Address space.
800
 * @param va Virtual address.
801
 *
802
 * @return Locked address space area containing va on success or NULL on failure.
803
 */
804
as_area_t *find_area_and_lock(as_t *as, __address va)
805
{
806
    as_area_t *a;
1147 jermar 807
    btree_node_t *leaf, *lnode;
808
    int i;
977 jermar 809
 
1147 jermar 810
    a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
811
    if (a) {
812
        /* va is the base address of an address space area */
1380 jermar 813
        mutex_lock(&a->lock);
1147 jermar 814
        return a;
815
    }
816
 
817
    /*
1150 jermar 818
     * Search the leaf node and the righmost record of its left neighbour
1147 jermar 819
     * to find out whether this is a miss or va belongs to an address
820
     * space area found there.
821
     */
822
 
823
    /* First, search the leaf node itself. */
824
    for (i = 0; i < leaf->keys; i++) {
825
        a = (as_area_t *) leaf->value[i];
1380 jermar 826
        mutex_lock(&a->lock);
1147 jermar 827
        if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) {
828
            return a;
829
        }
1380 jermar 830
        mutex_unlock(&a->lock);
1147 jermar 831
    }
977 jermar 832
 
1147 jermar 833
    /*
1150 jermar 834
     * Second, locate the left neighbour and test its last record.
1148 jermar 835
     * Because of its position in the B+tree, it must have base < va.
1147 jermar 836
     */
1150 jermar 837
    if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
1147 jermar 838
        a = (as_area_t *) lnode->value[lnode->keys - 1];
1380 jermar 839
        mutex_lock(&a->lock);
1147 jermar 840
        if (va < a->base + a->pages * PAGE_SIZE) {
1048 jermar 841
            return a;
1147 jermar 842
        }
1380 jermar 843
        mutex_unlock(&a->lock);
977 jermar 844
    }
845
 
846
    return NULL;
847
}
1048 jermar 848
 
849
/** Check area conflicts with other areas.
850
 *
851
 * The address space must be locked and interrupts must be disabled.
852
 *
853
 * @param as Address space.
854
 * @param va Starting virtual address of the area being tested.
855
 * @param size Size of the area being tested.
856
 * @param avoid_area Do not touch this area.
857
 *
858
 * @return True if there is no conflict, false otherwise.
859
 */
860
bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area)
861
{
862
    as_area_t *a;
1147 jermar 863
    btree_node_t *leaf, *node;
864
    int i;
1048 jermar 865
 
1070 jermar 866
    /*
867
     * We don't want any area to have conflicts with NULL page.
868
     */
869
    if (overlaps(va, size, NULL, PAGE_SIZE))
870
        return false;
871
 
1147 jermar 872
    /*
873
     * The leaf node is found in O(log n), where n is proportional to
874
     * the number of address space areas belonging to as.
875
     * The check for conflicts is then attempted on the rightmost
1150 jermar 876
     * record in the left neighbour, the leftmost record in the right
877
     * neighbour and all records in the leaf node itself.
1147 jermar 878
     */
1048 jermar 879
 
1147 jermar 880
    if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) {
881
        if (a != avoid_area)
882
            return false;
883
    }
884
 
885
    /* First, check the two border cases. */
1150 jermar 886
    if ((node = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
1147 jermar 887
        a = (as_area_t *) node->value[node->keys - 1];
1380 jermar 888
        mutex_lock(&a->lock);
1147 jermar 889
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1380 jermar 890
            mutex_unlock(&a->lock);
1147 jermar 891
            return false;
892
        }
1380 jermar 893
        mutex_unlock(&a->lock);
1147 jermar 894
    }
1150 jermar 895
    if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) {
1147 jermar 896
        a = (as_area_t *) node->value[0];
1380 jermar 897
        mutex_lock(&a->lock);
1147 jermar 898
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1380 jermar 899
            mutex_unlock(&a->lock);
1147 jermar 900
            return false;
901
        }
1380 jermar 902
        mutex_unlock(&a->lock);
1147 jermar 903
    }
904
 
905
    /* Second, check the leaf node. */
906
    for (i = 0; i < leaf->keys; i++) {
907
        a = (as_area_t *) leaf->value[i];
908
 
1048 jermar 909
        if (a == avoid_area)
910
            continue;
1147 jermar 911
 
1380 jermar 912
        mutex_lock(&a->lock);
1147 jermar 913
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
1380 jermar 914
            mutex_unlock(&a->lock);
1147 jermar 915
            return false;
916
        }
1380 jermar 917
        mutex_unlock(&a->lock);
1048 jermar 918
    }
919
 
1070 jermar 920
    /*
921
     * So far, the area does not conflict with other areas.
922
     * Check if it doesn't conflict with kernel address space.
923
     */  
924
    if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
925
        return !overlaps(va, size,
926
            KERNEL_ADDRESS_SPACE_START, KERNEL_ADDRESS_SPACE_END-KERNEL_ADDRESS_SPACE_START);
927
    }
928
 
1048 jermar 929
    return true;
930
}
1235 jermar 931
 
1380 jermar 932
/** Return size of the address space area with given base.  */
1329 palkovsky 933
size_t as_get_size(__address base)
934
{
935
    ipl_t ipl;
936
    as_area_t *src_area;
937
    size_t size;
938
 
939
    ipl = interrupts_disable();
940
    src_area = find_area_and_lock(AS, base);
941
    if (src_area){
942
        size = src_area->pages * PAGE_SIZE;
1380 jermar 943
        mutex_unlock(&src_area->lock);
1329 palkovsky 944
    } else {
945
        size = 0;
946
    }
947
    interrupts_restore(ipl);
948
    return size;
949
}
950
 
1387 jermar 951
/** Mark portion of address space area as used.
952
 *
953
 * The address space area must be already locked.
954
 *
955
 * @param a Address space area.
956
 * @param page First page to be marked.
957
 * @param count Number of page to be marked.
958
 *
959
 * @return 0 on failure and 1 on success.
960
 */
961
int used_space_insert(as_area_t *a, __address page, count_t count)
962
{
963
    btree_node_t *leaf, *node;
964
    count_t pages;
965
    int i;
966
 
967
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
968
    ASSERT(count);
969
 
970
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
971
    if (pages) {
972
        /*
973
         * We hit the beginning of some used space.
974
         */
975
        return 0;
976
    }
977
 
978
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
979
    if (node) {
980
        __address left_pg = node->key[node->keys - 1], right_pg = leaf->key[0];
981
        count_t left_cnt = (count_t) node->value[node->keys - 1], right_cnt = (count_t) leaf->value[0];
982
 
983
        /*
984
         * Examine the possibility that the interval fits
985
         * somewhere between the rightmost interval of
986
         * the left neigbour and the first interval of the leaf.
987
         */
988
 
989
        if (page >= right_pg) {
990
            /* Do nothing. */
991
        } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
992
            /* The interval intersects with the left interval. */
993
            return 0;
994
        } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
995
            /* The interval intersects with the right interval. */
996
            return 0;          
997
        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
998
            /* The interval can be added by merging the two already present intervals. */
999
            node->value[node->keys - 1] += (count_t) count + right_cnt;
1000
            btree_remove(&a->used_space, right_pg, leaf);
1001
            return 1;
1002
        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
1003
            /* The interval can be added by simply growing the left interval. */
1004
            node->value[node->keys - 1] += (count_t) count;
1005
            return 1;
1006
        } else if (page + count*PAGE_SIZE == right_pg) {
1007
            /*
1008
             * The interval can be addded by simply moving base of the right
1009
             * interval down and increasing its size accordingly.
1010
             */
1011
            leaf->value[0] += (count_t) count;
1012
            leaf->key[0] = page;
1013
            return 1;
1014
        } else {
1015
            /*
1016
             * The interval is between both neigbouring intervals,
1017
             * but cannot be merged with any of them.
1018
             */
1019
            btree_insert(&a->used_space, page, (void *) count, leaf);
1020
            return 1;
1021
        }
1022
    } else if (page < leaf->key[0]) {
1023
        __address right_pg = leaf->key[0];
1024
        count_t right_cnt = (count_t) leaf->value[0];
1025
 
1026
        /*
1027
         * Investigate the border case in which the left neighbour does not
1028
         * exist but the interval fits from the left.
1029
         */
1030
 
1031
        if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1032
            /* The interval intersects with the right interval. */
1033
            return 0;
1034
        } else if (page + count*PAGE_SIZE == right_pg) {
1035
            /*
1036
             * The interval can be added by moving the base of the right interval down
1037
             * and increasing its size accordingly.
1038
             */
1039
            leaf->key[0] = page;
1040
            leaf->value[0] += (count_t) count;
1041
            return 1;
1042
        } else {
1043
            /*
1044
             * The interval doesn't adjoin with the right interval.
1045
             * It must be added individually.
1046
             */
1047
            btree_insert(&a->used_space, page, (void *) count, leaf);
1048
            return 1;
1049
        }
1050
    }
1051
 
1052
    node = btree_leaf_node_right_neighbour(&a->used_space, leaf);
1053
    if (node) {
1054
        __address left_pg = leaf->key[leaf->keys - 1], right_pg = node->key[0];
1055
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1], right_cnt = (count_t) node->value[0];
1056
 
1057
        /*
1058
         * Examine the possibility that the interval fits
1059
         * somewhere between the leftmost interval of
1060
         * the right neigbour and the last interval of the leaf.
1061
         */
1062
 
1063
        if (page < left_pg) {
1064
            /* Do nothing. */
1065
        } else if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1066
            /* The interval intersects with the left interval. */
1067
            return 0;
1068
        } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) {
1069
            /* The interval intersects with the right interval. */
1070
            return 0;          
1071
        } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) {
1072
            /* The interval can be added by merging the two already present intervals. */
1073
            leaf->value[leaf->keys - 1] += (count_t) count + right_cnt;
1074
            btree_remove(&a->used_space, right_pg, node);
1075
            return 1;
1076
        } else if (page == left_pg + left_cnt*PAGE_SIZE) {
1077
            /* The interval can be added by simply growing the left interval. */
1078
            leaf->value[leaf->keys - 1] += (count_t) count;
1079
            return 1;
1080
        } else if (page + count*PAGE_SIZE == right_pg) {
1081
            /*
1082
             * The interval can be addded by simply moving base of the right
1083
             * interval down and increasing its size accordingly.
1084
             */
1085
            node->value[0] += (count_t) count;
1086
            node->key[0] = page;
1087
            return 1;
1088
        } else {
1089
            /*
1090
             * The interval is between both neigbouring intervals,
1091
             * but cannot be merged with any of them.
1092
             */
1093
            btree_insert(&a->used_space, page, (void *) count, leaf);
1094
            return 1;
1095
        }
1096
    } else if (page >= leaf->key[leaf->keys - 1]) {
1097
        __address left_pg = leaf->key[leaf->keys - 1];
1098
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
1099
 
1100
        /*
1101
         * Investigate the border case in which the right neighbour does not
1102
         * exist but the interval fits from the right.
1103
         */
1104
 
1105
        if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) {
1106
            /* The interval intersects with the right interval. */
1107
            return 0;
1108
        } else if (left_pg + left_cnt*PAGE_SIZE == page) {
1109
            /* The interval can be added by growing the left interval. */
1110
            leaf->value[leaf->keys - 1] += (count_t) count;
1111
            return 1;
1112
        } else {
1113
            /*
1114
             * The interval doesn't adjoin with the left interval.
1115
             * It must be added individually.
1116
             */
1117
            btree_insert(&a->used_space, page, (void *) count, leaf);
1118
            return 1;
1119
        }
1120
    }
1121
 
1122
    /*
1123
     * Note that if the algorithm made it thus far, the interval can fit only
1124
     * between two other intervals of the leaf. The two border cases were already
1125
     * resolved.
1126
     */
1127
    for (i = 1; i < leaf->keys; i++) {
1128
        if (page < leaf->key[i]) {
1129
            __address left_pg = leaf->key[i - 1], right_pg = leaf->key[i];
1130
            count_t left_cnt = (count_t) leaf->value[i - 1], right_cnt = (count_t) leaf->value[i];
1131
 
1132
            /*
1133
             * The interval fits between left_pg and right_pg.
1134
             */
1135
 
1136
            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. */
1144
                leaf->value[i - 1] += (count_t) count + right_cnt;
1145
                btree_remove(&a->used_space, right_pg, leaf);
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. */
1149
                leaf->value[i - 1] += (count_t) count;
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
                 */
1156
                leaf->value[i] += (count_t) count;
1157
                leaf->key[i] = 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
        }
1168
    }
1169
 
1170
    panic("Inconsistency detected while adding %d pages of used space at %P.\n", count, page);
1171
}
1172
 
1173
/** Mark portion of address space area as unused.
1174
 *
1175
 * The address space area must be already locked.
1176
 *
1177
 * @param a Address space area.
1178
 * @param page First page to be marked.
1179
 * @param count Number of page to be marked.
1180
 *
1181
 * @return 0 on failure and 1 on success.
1182
 */
1183
int used_space_remove(as_area_t *a, __address page, count_t count)
1184
{
1185
    btree_node_t *leaf, *node;
1186
    count_t pages;
1187
    int i;
1188
 
1189
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
1190
    ASSERT(count);
1191
 
1192
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
1193
    if (pages) {
1194
        /*
1195
         * We are lucky, page is the beginning of some interval.
1196
         */
1197
        if (count > pages) {
1198
            return 0;
1199
        } else if (count == pages) {
1200
            btree_remove(&a->used_space, page, leaf);
1201
        } else {
1202
            /*
1203
             * Find the respective interval.
1204
             * Decrease its size and relocate its start address.
1205
             */
1206
            for (i = 0; i < leaf->keys; i++) {
1207
                if (leaf->key[i] == page) {
1208
                    leaf->key[i] += count*PAGE_SIZE;
1209
                    leaf->value[i] -= (count_t) count;
1210
                    return 1;
1211
                }
1212
            }
1213
            goto error;
1214
        }
1215
    }
1216
 
1217
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
1218
    if (node && page < leaf->key[0]) {
1219
        __address left_pg = node->key[node->keys - 1];
1220
        count_t left_cnt = (count_t) node->value[node->keys - 1];
1221
 
1222
        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
1223
            if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
1224
                /*
1225
                 * The interval is contained in the rightmost interval
1226
                 * of the left neighbour and can be removed by
1227
                 * updating the size of the bigger interval.
1228
                 */
1229
                node->value[node->keys - 1] -= (count_t) count;
1230
                return 1;
1231
            } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
1232
                count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
1233
 
1234
                /*
1235
                 * The interval is contained in the rightmost interval
1236
                 * of the left neighbour but its removal requires
1237
                 * both updating the size of the original interval and
1238
                 * also inserting a new interval.
1239
                 */
1240
                node->value[node->keys - 1] -= (count_t) count + new_cnt;
1241
                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
1242
                return 1;
1243
            }
1244
        }
1245
        return 0;
1246
    } else if (page < leaf->key[0]) {
1247
        return 0;
1248
    }
1249
 
1250
    if (page > leaf->key[leaf->keys - 1]) {
1251
        __address left_pg = leaf->key[leaf->keys - 1];
1252
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
1253
 
1254
        if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
1255
            if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
1256
                /*
1257
                 * The interval is contained in the rightmost interval
1258
                 * of the leaf and can be removed by updating the size
1259
                 * of the bigger interval.
1260
                 */
1261
                leaf->value[leaf->keys - 1] -= (count_t) count;
1262
                return 1;
1263
            } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
1264
                count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
1265
 
1266
                /*
1267
                 * The interval is contained in the rightmost interval
1268
                 * of the leaf but its removal requires both updating
1269
                 * the size of the original interval and
1270
                 * also inserting a new interval.
1271
                 */
1272
                leaf->value[leaf->keys - 1] -= (count_t) count + new_cnt;
1273
                btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
1274
                return 1;
1275
            }
1276
        }
1277
        return 0;
1278
    }  
1279
 
1280
    /*
1281
     * The border cases have been already resolved.
1282
     * Now the interval can be only between intervals of the leaf.
1283
     */
1284
    for (i = 1; i < leaf->keys - 1; i++) {
1285
        if (page < leaf->key[i]) {
1286
            __address left_pg = leaf->key[i - 1];
1287
            count_t left_cnt = (count_t) leaf->value[i - 1];
1288
 
1289
            /*
1290
             * Now the interval is between intervals corresponding to (i - 1) and i.
1291
             */
1292
            if (overlaps(left_pg, left_cnt*PAGE_SIZE, page, count*PAGE_SIZE)) {
1293
                if (page + count*PAGE_SIZE == left_pg + left_cnt*PAGE_SIZE) {
1294
                    /*
1295
                    * The interval is contained in the interval (i - 1)
1296
                     * of the leaf and can be removed by updating the size
1297
                     * of the bigger interval.
1298
                     */
1299
                    leaf->value[i - 1] -= (count_t) count;
1300
                    return 1;
1301
                } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) {
1302
                    count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE);
1303
 
1304
                    /*
1305
                     * The interval is contained in the interval (i - 1)
1306
                     * of the leaf but its removal requires both updating
1307
                     * the size of the original interval and
1308
                     * also inserting a new interval.
1309
                     */
1310
                    leaf->value[i - 1] -= (count_t) count + new_cnt;
1311
                    btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf);
1312
                    return 1;
1313
                }
1314
            }
1315
            return 0;
1316
        }
1317
    }
1318
 
1319
error:
1320
    panic("Inconsistency detected while removing %d pages of used space from %P.\n", count, page);
1321
}
1322
 
1235 jermar 1323
/*
1324
 * Address space related syscalls.
1325
 */
1326
 
1327
/** Wrapper for as_area_create(). */
1328
__native sys_as_area_create(__address address, size_t size, int flags)
1329
{
1239 jermar 1330
    if (as_area_create(AS, flags, size, address, AS_AREA_ATTR_NONE))
1235 jermar 1331
        return (__native) address;
1332
    else
1333
        return (__native) -1;
1334
}
1335
 
1336
/** Wrapper for as_area_resize. */
1337
__native sys_as_area_resize(__address address, size_t size, int flags)
1338
{
1306 jermar 1339
    return (__native) as_area_resize(AS, address, size, 0);
1235 jermar 1340
}
1341
 
1306 jermar 1342
/** Wrapper for as_area_destroy. */
1343
__native sys_as_area_destroy(__address address)
1344
{
1345
    return (__native) as_area_destroy(AS, address);
1346
}