Subversion Repositories HelenOS-historic

Rev

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

Rev 1178 Rev 1179
1
/*
1
/*
2
 * Copyright (C) 2001-2006 Jakub Jermar
2
 * Copyright (C) 2001-2006 Jakub Jermar
3
 * All rights reserved.
3
 * All rights reserved.
4
 *
4
 *
5
 * Redistribution and use in source and binary forms, with or without
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
6
 * modification, are permitted provided that the following conditions
7
 * are met:
7
 * are met:
8
 *
8
 *
9
 * - Redistributions of source code must retain the above copyright
9
 * - Redistributions of source code must retain the above copyright
10
 *   notice, this list of conditions and the following disclaimer.
10
 *   notice, this list of conditions and the following disclaimer.
11
 * - Redistributions in binary form must reproduce the above copyright
11
 * - Redistributions in binary form must reproduce the above copyright
12
 *   notice, this list of conditions and the following disclaimer in the
12
 *   notice, this list of conditions and the following disclaimer in the
13
 *   documentation and/or other materials provided with the distribution.
13
 *   documentation and/or other materials provided with the distribution.
14
 * - The name of the author may not be used to endorse or promote products
14
 * - The name of the author may not be used to endorse or promote products
15
 *   derived from this software without specific prior written permission.
15
 *   derived from this software without specific prior written permission.
16
 *
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
27
 */
28
 
28
 
29
/*
29
/*
30
 * This file contains address space manipulation functions.
30
 * This file contains address space manipulation functions.
31
 * Roughly speaking, this is a higher-level client of
31
 * Roughly speaking, this is a higher-level client of
32
 * Virtual Address Translation (VAT) subsystem.
32
 * Virtual Address Translation (VAT) subsystem.
33
 */
33
 */
34
 
34
 
35
#include <mm/as.h>
35
#include <mm/as.h>
36
#include <arch/mm/as.h>
36
#include <arch/mm/as.h>
37
#include <mm/page.h>
37
#include <mm/page.h>
38
#include <mm/frame.h>
38
#include <mm/frame.h>
39
#include <mm/slab.h>
39
#include <mm/slab.h>
40
#include <mm/tlb.h>
40
#include <mm/tlb.h>
41
#include <arch/mm/page.h>
41
#include <arch/mm/page.h>
42
#include <genarch/mm/page_pt.h>
42
#include <genarch/mm/page_pt.h>
43
#include <genarch/mm/page_ht.h>
43
#include <genarch/mm/page_ht.h>
44
#include <mm/asid.h>
44
#include <mm/asid.h>
45
#include <arch/mm/asid.h>
45
#include <arch/mm/asid.h>
46
#include <arch/types.h>
46
#include <arch/types.h>
47
#include <typedefs.h>
47
#include <typedefs.h>
48
#include <synch/spinlock.h>
48
#include <synch/spinlock.h>
49
#include <config.h>
49
#include <config.h>
50
#include <adt/list.h>
50
#include <adt/list.h>
51
#include <adt/btree.h>
51
#include <adt/btree.h>
52
#include <panic.h>
52
#include <panic.h>
53
#include <arch/asm.h>
53
#include <arch/asm.h>
54
#include <debug.h>
54
#include <debug.h>
55
#include <memstr.h>
55
#include <memstr.h>
56
#include <macros.h>
56
#include <macros.h>
57
#include <arch.h>
57
#include <arch.h>
58
#include <print.h>
58
#include <print.h>
59
 
59
 
60
as_operations_t *as_operations = NULL;
60
as_operations_t *as_operations = NULL;
61
 
61
 
62
/** Address space lock. It protects inactive_as_with_asid_head. */
62
/** Address space lock. It protects inactive_as_with_asid_head. */
63
SPINLOCK_INITIALIZE(as_lock);
63
SPINLOCK_INITIALIZE(as_lock);
64
 
64
 
65
/**
65
/**
66
 * This list contains address spaces that are not active on any
66
 * This list contains address spaces that are not active on any
67
 * processor and that have valid ASID.
67
 * processor and that have valid ASID.
68
 */
68
 */
69
LIST_INITIALIZE(inactive_as_with_asid_head);
69
LIST_INITIALIZE(inactive_as_with_asid_head);
70
 
70
 
71
/** Kernel address space. */
71
/** Kernel address space. */
72
as_t *AS_KERNEL = NULL;
72
as_t *AS_KERNEL = NULL;
73
 
73
 
74
static int get_area_flags(as_area_t *a);
74
static int get_area_flags(as_area_t *a);
75
static as_area_t *find_area_and_lock(as_t *as, __address va);
75
static as_area_t *find_area_and_lock(as_t *as, __address va);
76
static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area);
76
static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area);
77
 
77
 
78
/** Initialize address space subsystem. */
78
/** Initialize address space subsystem. */
79
void as_init(void)
79
void as_init(void)
80
{
80
{
81
    as_arch_init();
81
    as_arch_init();
82
    AS_KERNEL = as_create(FLAG_AS_KERNEL);
82
    AS_KERNEL = as_create(FLAG_AS_KERNEL);
83
        if (!AS_KERNEL)
83
        if (!AS_KERNEL)
84
                panic("can't create kernel address space\n");
84
                panic("can't create kernel address space\n");
85
}
85
}
86
 
86
 
87
/** Create address space.
87
/** Create address space.
88
 *
88
 *
89
 * @param flags Flags that influence way in wich the address space is created.
89
 * @param flags Flags that influence way in wich the address space is created.
90
 */
90
 */
91
as_t *as_create(int flags)
91
as_t *as_create(int flags)
92
{
92
{
93
    as_t *as;
93
    as_t *as;
94
 
94
 
95
    as = (as_t *) malloc(sizeof(as_t), 0);
95
    as = (as_t *) malloc(sizeof(as_t), 0);
96
    link_initialize(&as->inactive_as_with_asid_link);
96
    link_initialize(&as->inactive_as_with_asid_link);
97
    spinlock_initialize(&as->lock, "as_lock");
97
    spinlock_initialize(&as->lock, "as_lock");
98
    btree_create(&as->as_area_btree);
98
    btree_create(&as->as_area_btree);
99
   
99
   
100
    if (flags & FLAG_AS_KERNEL)
100
    if (flags & FLAG_AS_KERNEL)
101
        as->asid = ASID_KERNEL;
101
        as->asid = ASID_KERNEL;
102
    else
102
    else
103
        as->asid = ASID_INVALID;
103
        as->asid = ASID_INVALID;
104
   
104
   
105
    as->refcount = 0;
105
    as->refcount = 0;
106
    as->page_table = page_table_create(flags);
106
    as->page_table = page_table_create(flags);
107
 
107
 
108
    return as;
108
    return as;
109
}
109
}
110
 
110
 
111
/** Free Adress space */
111
/** Free Adress space */
112
void as_free(as_t *as)
112
void as_free(as_t *as)
113
{
113
{
114
    ASSERT(as->refcount == 0);
114
    ASSERT(as->refcount == 0);
115
 
115
 
116
    /* TODO: free as_areas and other resources held by as */
116
    /* TODO: free as_areas and other resources held by as */
117
    /* TODO: free page table */
117
    /* TODO: free page table */
118
    free(as);
118
    free(as);
119
}
119
}
120
 
120
 
121
/** Create address space area of common attributes.
121
/** Create address space area of common attributes.
122
 *
122
 *
123
 * The created address space area is added to the target address space.
123
 * The created address space area is added to the target address space.
124
 *
124
 *
125
 * @param as Target address space.
125
 * @param as Target address space.
126
 * @param flags Flags of the area.
126
 * @param flags Flags of the area.
127
 * @param size Size of area.
127
 * @param size Size of area.
128
 * @param base Base address of area.
128
 * @param base Base address of area.
129
 *
129
 *
130
 * @return Address space area on success or NULL on failure.
130
 * @return Address space area on success or NULL on failure.
131
 */
131
 */
132
as_area_t *as_area_create(as_t *as, int flags, size_t size, __address base)
132
as_area_t *as_area_create(as_t *as, int flags, size_t size, __address base)
133
{
133
{
134
    ipl_t ipl;
134
    ipl_t ipl;
135
    as_area_t *a;
135
    as_area_t *a;
136
   
136
   
137
    if (base % PAGE_SIZE)
137
    if (base % PAGE_SIZE)
138
        return NULL;
138
        return NULL;
139
 
139
 
140
    /* Writeable executable areas are not supported. */
140
    /* Writeable executable areas are not supported. */
141
    if ((flags & AS_AREA_EXEC) && (flags & AS_AREA_WRITE))
141
    if ((flags & AS_AREA_EXEC) && (flags & AS_AREA_WRITE))
142
        return NULL;
142
        return NULL;
143
   
143
   
144
    ipl = interrupts_disable();
144
    ipl = interrupts_disable();
145
    spinlock_lock(&as->lock);
145
    spinlock_lock(&as->lock);
146
   
146
   
147
    if (!check_area_conflicts(as, base, size, NULL)) {
147
    if (!check_area_conflicts(as, base, size, NULL)) {
148
        spinlock_unlock(&as->lock);
148
        spinlock_unlock(&as->lock);
149
        interrupts_restore(ipl);
149
        interrupts_restore(ipl);
150
        return NULL;
150
        return NULL;
151
    }
151
    }
152
   
152
   
153
    a = (as_area_t *) malloc(sizeof(as_area_t), 0);
153
    a = (as_area_t *) malloc(sizeof(as_area_t), 0);
154
 
154
 
155
    spinlock_initialize(&a->lock, "as_area_lock");
155
    spinlock_initialize(&a->lock, "as_area_lock");
156
   
156
   
157
    a->flags = flags;
157
    a->flags = flags;
158
    a->pages = SIZE2FRAMES(size);
158
    a->pages = SIZE2FRAMES(size);
159
    a->base = base;
159
    a->base = base;
160
   
160
   
161
    btree_insert(&as->as_area_btree, base, (void *) a, NULL);
161
    btree_insert(&as->as_area_btree, base, (void *) a, NULL);
162
 
162
 
163
    spinlock_unlock(&as->lock);
163
    spinlock_unlock(&as->lock);
164
    interrupts_restore(ipl);
164
    interrupts_restore(ipl);
165
 
165
 
166
    return a;
166
    return a;
167
}
167
}
168
 
168
 
169
/** Initialize mapping for one page of address space.
169
/** Initialize mapping for one page of address space.
170
 *
170
 *
171
 * This functions maps 'page' to 'frame' according
171
 * This functions maps 'page' to 'frame' according
172
 * to attributes of the address space area to
172
 * to attributes of the address space area to
173
 * wich 'page' belongs.
173
 * wich 'page' belongs.
174
 *
174
 *
175
 * @param as Target address space.
175
 * @param as Target address space.
176
 * @param page Virtual page within the area.
176
 * @param page Virtual page within the area.
177
 * @param frame Physical frame to which page will be mapped.
177
 * @param frame Physical frame to which page will be mapped.
178
 */
178
 */
179
void as_set_mapping(as_t *as, __address page, __address frame)
179
void as_set_mapping(as_t *as, __address page, __address frame)
180
{
180
{
181
    as_area_t *area;
181
    as_area_t *area;
182
    ipl_t ipl;
182
    ipl_t ipl;
183
   
183
   
184
    ipl = interrupts_disable();
184
    ipl = interrupts_disable();
185
    page_table_lock(as, true);
185
    page_table_lock(as, true);
186
   
186
   
187
    area = find_area_and_lock(as, page);
187
    area = find_area_and_lock(as, page);
188
    if (!area) {
188
    if (!area) {
189
        panic("page not part of any as_area\n");
189
        panic("page not part of any as_area\n");
190
    }
190
    }
191
 
191
 
192
    page_mapping_insert(as, page, frame, get_area_flags(area));
192
    page_mapping_insert(as, page, frame, get_area_flags(area));
193
   
193
   
194
    spinlock_unlock(&area->lock);
194
    spinlock_unlock(&area->lock);
195
    page_table_unlock(as, true);
195
    page_table_unlock(as, true);
196
    interrupts_restore(ipl);
196
    interrupts_restore(ipl);
197
}
197
}
198
 
198
 
199
/** Handle page fault within the current address space.
199
/** Handle page fault within the current address space.
200
 *
200
 *
201
 * This is the high-level page fault handler.
201
 * This is the high-level page fault handler.
202
 * Interrupts are assumed disabled.
202
 * Interrupts are assumed disabled.
203
 *
203
 *
204
 * @param page Faulting page.
204
 * @param page Faulting page.
205
 *
205
 *
206
 * @return 0 on page fault, 1 on success.
206
 * @return 0 on page fault, 1 on success.
207
 */
207
 */
208
int as_page_fault(__address page)
208
int as_page_fault(__address page)
209
{
209
{
210
    pte_t *pte;
210
    pte_t *pte;
211
    as_area_t *area;
211
    as_area_t *area;
212
    __address frame;
212
    __address frame;
213
   
213
   
214
    ASSERT(AS);
214
    ASSERT(AS);
215
 
215
 
216
    spinlock_lock(&AS->lock);
216
    spinlock_lock(&AS->lock);
217
    area = find_area_and_lock(AS, page);   
217
    area = find_area_and_lock(AS, page);   
218
    if (!area) {
218
    if (!area) {
219
        /*
219
        /*
220
         * No area contained mapping for 'page'.
220
         * No area contained mapping for 'page'.
221
         * Signal page fault to low-level handler.
221
         * Signal page fault to low-level handler.
222
         */
222
         */
223
        spinlock_unlock(&AS->lock);
223
        spinlock_unlock(&AS->lock);
224
        return 0;
224
        return 0;
225
    }
225
    }
226
 
226
 
-
 
227
    ASSERT(!(area->flags & AS_AREA_DEVICE));
-
 
228
 
227
    page_table_lock(AS, false);
229
    page_table_lock(AS, false);
228
   
230
   
229
    /*
231
    /*
230
     * To avoid race condition between two page faults
232
     * To avoid race condition between two page faults
231
     * on the same address, we need to make sure
233
     * on the same address, we need to make sure
232
     * the mapping has not been already inserted.
234
     * the mapping has not been already inserted.
233
     */
235
     */
234
    if ((pte = page_mapping_find(AS, page))) {
236
    if ((pte = page_mapping_find(AS, page))) {
235
        if (PTE_PRESENT(pte)) {
237
        if (PTE_PRESENT(pte)) {
236
            page_table_unlock(AS, false);
238
            page_table_unlock(AS, false);
237
            spinlock_unlock(&area->lock);
239
            spinlock_unlock(&area->lock);
238
            spinlock_unlock(&AS->lock);
240
            spinlock_unlock(&AS->lock);
239
            return 1;
241
            return 1;
240
        }
242
        }
241
    }
243
    }
242
 
244
 
243
    /*
245
    /*
244
     * In general, there can be several reasons that
246
     * In general, there can be several reasons that
245
     * can have caused this fault.
247
     * can have caused this fault.
246
     *
248
     *
247
     * - non-existent mapping: the area is a scratch
249
     * - non-existent mapping: the area is a scratch
248
     *   area (e.g. stack) and so far has not been
250
     *   area (e.g. stack) and so far has not been
249
     *   allocated a frame for the faulting page
251
     *   allocated a frame for the faulting page
250
     *
252
     *
251
     * - non-present mapping: another possibility,
253
     * - non-present mapping: another possibility,
252
     *   currently not implemented, would be frame
254
     *   currently not implemented, would be frame
253
     *   reuse; when this becomes a possibility,
255
     *   reuse; when this becomes a possibility,
254
     *   do not forget to distinguish between
256
     *   do not forget to distinguish between
255
     *   the different causes
257
     *   the different causes
256
     */
258
     */
257
    frame = PFN2ADDR(frame_alloc(ONE_FRAME, 0));
259
    frame = PFN2ADDR(frame_alloc(ONE_FRAME, 0));
258
    memsetb(PA2KA(frame), FRAME_SIZE, 0);
260
    memsetb(PA2KA(frame), FRAME_SIZE, 0);
259
   
261
   
260
    /*
262
    /*
261
     * Map 'page' to 'frame'.
263
     * Map 'page' to 'frame'.
262
     * Note that TLB shootdown is not attempted as only new information is being
264
     * Note that TLB shootdown is not attempted as only new information is being
263
     * inserted into page tables.
265
     * inserted into page tables.
264
     */
266
     */
265
    page_mapping_insert(AS, page, frame, get_area_flags(area));
267
    page_mapping_insert(AS, page, frame, get_area_flags(area));
266
    page_table_unlock(AS, false);
268
    page_table_unlock(AS, false);
267
   
269
   
268
    spinlock_unlock(&area->lock);
270
    spinlock_unlock(&area->lock);
269
    spinlock_unlock(&AS->lock);
271
    spinlock_unlock(&AS->lock);
270
    return 1;
272
    return 1;
271
}
273
}
272
 
274
 
273
/** Switch address spaces.
275
/** Switch address spaces.
274
 *
276
 *
275
 * @param old Old address space or NULL.
277
 * @param old Old address space or NULL.
276
 * @param new New address space.
278
 * @param new New address space.
277
 */
279
 */
278
void as_switch(as_t *old, as_t *new)
280
void as_switch(as_t *old, as_t *new)
279
{
281
{
280
    ipl_t ipl;
282
    ipl_t ipl;
281
    bool needs_asid = false;
283
    bool needs_asid = false;
282
   
284
   
283
    ipl = interrupts_disable();
285
    ipl = interrupts_disable();
284
    spinlock_lock(&as_lock);
286
    spinlock_lock(&as_lock);
285
 
287
 
286
    /*
288
    /*
287
     * First, take care of the old address space.
289
     * First, take care of the old address space.
288
     */
290
     */
289
    if (old) {
291
    if (old) {
290
        spinlock_lock(&old->lock);
292
        spinlock_lock(&old->lock);
291
        ASSERT(old->refcount);
293
        ASSERT(old->refcount);
292
        if((--old->refcount == 0) && (old != AS_KERNEL)) {
294
        if((--old->refcount == 0) && (old != AS_KERNEL)) {
293
            /*
295
            /*
294
             * The old address space is no longer active on
296
             * The old address space is no longer active on
295
             * any processor. It can be appended to the
297
             * any processor. It can be appended to the
296
             * list of inactive address spaces with assigned
298
             * list of inactive address spaces with assigned
297
             * ASID.
299
             * ASID.
298
             */
300
             */
299
             ASSERT(old->asid != ASID_INVALID);
301
             ASSERT(old->asid != ASID_INVALID);
300
             list_append(&old->inactive_as_with_asid_link, &inactive_as_with_asid_head);
302
             list_append(&old->inactive_as_with_asid_link, &inactive_as_with_asid_head);
301
        }
303
        }
302
        spinlock_unlock(&old->lock);
304
        spinlock_unlock(&old->lock);
303
    }
305
    }
304
 
306
 
305
    /*
307
    /*
306
     * Second, prepare the new address space.
308
     * Second, prepare the new address space.
307
     */
309
     */
308
    spinlock_lock(&new->lock);
310
    spinlock_lock(&new->lock);
309
    if ((new->refcount++ == 0) && (new != AS_KERNEL)) {
311
    if ((new->refcount++ == 0) && (new != AS_KERNEL)) {
310
        if (new->asid != ASID_INVALID)
312
        if (new->asid != ASID_INVALID)
311
            list_remove(&new->inactive_as_with_asid_link);
313
            list_remove(&new->inactive_as_with_asid_link);
312
        else
314
        else
313
            needs_asid = true;  /* defer call to asid_get() until new->lock is released */
315
            needs_asid = true;  /* defer call to asid_get() until new->lock is released */
314
    }
316
    }
315
    SET_PTL0_ADDRESS(new->page_table);
317
    SET_PTL0_ADDRESS(new->page_table);
316
    spinlock_unlock(&new->lock);
318
    spinlock_unlock(&new->lock);
317
 
319
 
318
    if (needs_asid) {
320
    if (needs_asid) {
319
        /*
321
        /*
320
         * Allocation of new ASID was deferred
322
         * Allocation of new ASID was deferred
321
         * until now in order to avoid deadlock.
323
         * until now in order to avoid deadlock.
322
         */
324
         */
323
        asid_t asid;
325
        asid_t asid;
324
       
326
       
325
        asid = asid_get();
327
        asid = asid_get();
326
        spinlock_lock(&new->lock);
328
        spinlock_lock(&new->lock);
327
        new->asid = asid;
329
        new->asid = asid;
328
        spinlock_unlock(&new->lock);
330
        spinlock_unlock(&new->lock);
329
    }
331
    }
330
    spinlock_unlock(&as_lock);
332
    spinlock_unlock(&as_lock);
331
    interrupts_restore(ipl);
333
    interrupts_restore(ipl);
332
   
334
   
333
    /*
335
    /*
334
     * Perform architecture-specific steps.
336
     * Perform architecture-specific steps.
335
     * (e.g. write ASID to hardware register etc.)
337
     * (e.g. write ASID to hardware register etc.)
336
     */
338
     */
337
    as_install_arch(new);
339
    as_install_arch(new);
338
   
340
   
339
    AS = new;
341
    AS = new;
340
}
342
}
341
 
343
 
342
/** Compute flags for virtual address translation subsytem.
344
/** Compute flags for virtual address translation subsytem.
343
 *
345
 *
344
 * The address space area must be locked.
346
 * The address space area must be locked.
345
 * Interrupts must be disabled.
347
 * Interrupts must be disabled.
346
 *
348
 *
347
 * @param a Address space area.
349
 * @param a Address space area.
348
 *
350
 *
349
 * @return Flags to be used in page_mapping_insert().
351
 * @return Flags to be used in page_mapping_insert().
350
 */
352
 */
351
int get_area_flags(as_area_t *a)
353
int get_area_flags(as_area_t *a)
352
{
354
{
353
    int flags;
355
    int flags;
354
 
356
 
355
    flags = PAGE_USER | PAGE_PRESENT;
357
    flags = PAGE_USER | PAGE_PRESENT;
356
   
358
   
357
    if (a->flags & AS_AREA_READ)
359
    if (a->flags & AS_AREA_READ)
358
        flags |= PAGE_READ;
360
        flags |= PAGE_READ;
359
       
361
       
360
    if (a->flags & AS_AREA_WRITE)
362
    if (a->flags & AS_AREA_WRITE)
361
        flags |= PAGE_WRITE;
363
        flags |= PAGE_WRITE;
362
   
364
   
363
    if (a->flags & AS_AREA_EXEC)
365
    if (a->flags & AS_AREA_EXEC)
364
        flags |= PAGE_EXEC;
366
        flags |= PAGE_EXEC;
365
   
367
   
366
    if (!(a->flags & AS_AREA_DEVICE))
368
    if (!(a->flags & AS_AREA_DEVICE))
367
        flags |= PAGE_CACHEABLE;
369
        flags |= PAGE_CACHEABLE;
368
       
370
       
369
    return flags;
371
    return flags;
370
}
372
}
371
 
373
 
372
/** Create page table.
374
/** Create page table.
373
 *
375
 *
374
 * Depending on architecture, create either address space
376
 * Depending on architecture, create either address space
375
 * private or global page table.
377
 * private or global page table.
376
 *
378
 *
377
 * @param flags Flags saying whether the page table is for kernel address space.
379
 * @param flags Flags saying whether the page table is for kernel address space.
378
 *
380
 *
379
 * @return First entry of the page table.
381
 * @return First entry of the page table.
380
 */
382
 */
381
pte_t *page_table_create(int flags)
383
pte_t *page_table_create(int flags)
382
{
384
{
383
        ASSERT(as_operations);
385
        ASSERT(as_operations);
384
        ASSERT(as_operations->page_table_create);
386
        ASSERT(as_operations->page_table_create);
385
 
387
 
386
        return as_operations->page_table_create(flags);
388
        return as_operations->page_table_create(flags);
387
}
389
}
388
 
390
 
389
/** Lock page table.
391
/** Lock page table.
390
 *
392
 *
391
 * This function should be called before any page_mapping_insert(),
393
 * This function should be called before any page_mapping_insert(),
392
 * page_mapping_remove() and page_mapping_find().
394
 * page_mapping_remove() and page_mapping_find().
393
 *
395
 *
394
 * Locking order is such that address space areas must be locked
396
 * Locking order is such that address space areas must be locked
395
 * prior to this call. Address space can be locked prior to this
397
 * prior to this call. Address space can be locked prior to this
396
 * call in which case the lock argument is false.
398
 * call in which case the lock argument is false.
397
 *
399
 *
398
 * @param as Address space.
400
 * @param as Address space.
399
 * @param as_locked If false, do not attempt to lock as->lock.
401
 * @param as_locked If false, do not attempt to lock as->lock.
400
 */
402
 */
401
void page_table_lock(as_t *as, bool lock)
403
void page_table_lock(as_t *as, bool lock)
402
{
404
{
403
    ASSERT(as_operations);
405
    ASSERT(as_operations);
404
    ASSERT(as_operations->page_table_lock);
406
    ASSERT(as_operations->page_table_lock);
405
 
407
 
406
    as_operations->page_table_lock(as, lock);
408
    as_operations->page_table_lock(as, lock);
407
}
409
}
408
 
410
 
409
/** Unlock page table.
411
/** Unlock page table.
410
 *
412
 *
411
 * @param as Address space.
413
 * @param as Address space.
412
 * @param as_locked If false, do not attempt to unlock as->lock.
414
 * @param as_locked If false, do not attempt to unlock as->lock.
413
 */
415
 */
414
void page_table_unlock(as_t *as, bool unlock)
416
void page_table_unlock(as_t *as, bool unlock)
415
{
417
{
416
    ASSERT(as_operations);
418
    ASSERT(as_operations);
417
    ASSERT(as_operations->page_table_unlock);
419
    ASSERT(as_operations->page_table_unlock);
418
 
420
 
419
    as_operations->page_table_unlock(as, unlock);
421
    as_operations->page_table_unlock(as, unlock);
420
}
422
}
421
 
423
 
422
/** Find address space area and change it.
424
/** Find address space area and change it.
423
 *
425
 *
424
 * @param as Address space.
426
 * @param as Address space.
425
 * @param address Virtual address belonging to the area to be changed. Must be page-aligned.
427
 * @param address Virtual address belonging to the area to be changed. Must be page-aligned.
426
 * @param size New size of the virtual memory block starting at address.
428
 * @param size New size of the virtual memory block starting at address.
427
 * @param flags Flags influencing the remap operation. Currently unused.
429
 * @param flags Flags influencing the remap operation. Currently unused.
428
 *
430
 *
429
 * @return address on success, (__address) -1 otherwise.
431
 * @return address on success, (__address) -1 otherwise.
430
 */
432
 */
431
__address as_remap(as_t *as, __address address, size_t size, int flags)
433
__address as_remap(as_t *as, __address address, size_t size, int flags)
432
{
434
{
433
    as_area_t *area = NULL;
435
    as_area_t *area = NULL;
434
    ipl_t ipl;
436
    ipl_t ipl;
435
    size_t pages;
437
    size_t pages;
436
   
438
   
437
    ipl = interrupts_disable();
439
    ipl = interrupts_disable();
438
    spinlock_lock(&as->lock);
440
    spinlock_lock(&as->lock);
439
   
441
   
440
    /*
442
    /*
441
     * Locate the area.
443
     * Locate the area.
442
     */
444
     */
443
    area = find_area_and_lock(as, address);
445
    area = find_area_and_lock(as, address);
444
    if (!area) {
446
    if (!area) {
445
        spinlock_unlock(&as->lock);
447
        spinlock_unlock(&as->lock);
-
 
448
        interrupts_restore(ipl);
-
 
449
        return (__address) -1;
-
 
450
    }
-
 
451
 
-
 
452
    if (area->flags & AS_AREA_DEVICE) {
-
 
453
        /*
-
 
454
         * Remapping of address space areas associated
-
 
455
         * with memory mapped devices is not supported.
-
 
456
         */
-
 
457
        spinlock_unlock(&area->lock);
-
 
458
        spinlock_unlock(&as->lock);
446
        interrupts_restore(ipl);
459
        interrupts_restore(ipl);
447
        return (__address) -1;
460
        return (__address) -1;
448
    }
461
    }
449
 
462
 
450
    pages = SIZE2FRAMES((address - area->base) + size);
463
    pages = SIZE2FRAMES((address - area->base) + size);
451
    if (pages < area->pages) {
464
    if (pages < area->pages) {
452
        int i;
465
        int i;
453
 
466
 
454
        /*
467
        /*
455
         * Shrinking the area.
468
         * Shrinking the area.
456
         * No need to check for overlaps.
469
         * No need to check for overlaps.
457
         */
470
         */
458
        for (i = pages; i < area->pages; i++) {
471
        for (i = pages; i < area->pages; i++) {
459
            pte_t *pte;
472
            pte_t *pte;
460
           
473
           
461
            /*
474
            /*
462
             * Releasing physical memory.
475
             * Releasing physical memory.
463
             * This depends on the fact that the memory was allocated using frame_alloc().
476
             * This depends on the fact that the memory was allocated using frame_alloc().
464
             */
477
             */
465
            page_table_lock(as, false);
478
            page_table_lock(as, false);
466
            pte = page_mapping_find(as, area->base + i*PAGE_SIZE);
479
            pte = page_mapping_find(as, area->base + i*PAGE_SIZE);
467
            if (pte && PTE_VALID(pte)) {
480
            if (pte && PTE_VALID(pte)) {
468
                __address frame;
481
                __address frame;
469
 
482
 
470
                ASSERT(PTE_PRESENT(pte));
483
                ASSERT(PTE_PRESENT(pte));
471
                frame = PTE_GET_FRAME(pte);
484
                frame = PTE_GET_FRAME(pte);
472
                page_mapping_remove(as, area->base + i*PAGE_SIZE);
485
                page_mapping_remove(as, area->base + i*PAGE_SIZE);
473
                page_table_unlock(as, false);
486
                page_table_unlock(as, false);
474
 
487
 
475
                frame_free(ADDR2PFN(frame));
488
                frame_free(ADDR2PFN(frame));
476
            } else {
489
            } else {
477
                page_table_unlock(as, false);
490
                page_table_unlock(as, false);
478
            }
491
            }
479
        }
492
        }
480
        /*
493
        /*
481
         * Invalidate TLB's.
494
         * Invalidate TLB's.
482
         */
495
         */
483
        tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
496
        tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
484
        tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
497
        tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
485
        tlb_shootdown_finalize();
498
        tlb_shootdown_finalize();
486
    } else {
499
    } else {
487
        /*
500
        /*
488
         * Growing the area.
501
         * Growing the area.
489
         * Check for overlaps with other address space areas.
502
         * Check for overlaps with other address space areas.
490
         */
503
         */
491
        if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
504
        if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
492
            spinlock_unlock(&area->lock);
505
            spinlock_unlock(&area->lock);
493
            spinlock_unlock(&as->lock);    
506
            spinlock_unlock(&as->lock);    
494
            interrupts_restore(ipl);
507
            interrupts_restore(ipl);
495
            return (__address) -1;
508
            return (__address) -1;
496
        }
509
        }
497
    }
510
    }
498
 
511
 
499
    area->pages = pages;
512
    area->pages = pages;
500
   
513
   
501
    spinlock_unlock(&area->lock);
514
    spinlock_unlock(&area->lock);
502
    spinlock_unlock(&as->lock);
515
    spinlock_unlock(&as->lock);
503
    interrupts_restore(ipl);
516
    interrupts_restore(ipl);
504
 
517
 
505
    return address;
518
    return address;
506
}
519
}
507
 
520
 
508
/** Find address space area and lock it.
521
/** Find address space area and lock it.
509
 *
522
 *
510
 * The address space must be locked and interrupts must be disabled.
523
 * The address space must be locked and interrupts must be disabled.
511
 *
524
 *
512
 * @param as Address space.
525
 * @param as Address space.
513
 * @param va Virtual address.
526
 * @param va Virtual address.
514
 *
527
 *
515
 * @return Locked address space area containing va on success or NULL on failure.
528
 * @return Locked address space area containing va on success or NULL on failure.
516
 */
529
 */
517
as_area_t *find_area_and_lock(as_t *as, __address va)
530
as_area_t *find_area_and_lock(as_t *as, __address va)
518
{
531
{
519
    as_area_t *a;
532
    as_area_t *a;
520
    btree_node_t *leaf, *lnode;
533
    btree_node_t *leaf, *lnode;
521
    int i;
534
    int i;
522
   
535
   
523
    a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
536
    a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
524
    if (a) {
537
    if (a) {
525
        /* va is the base address of an address space area */
538
        /* va is the base address of an address space area */
526
        spinlock_lock(&a->lock);
539
        spinlock_lock(&a->lock);
527
        return a;
540
        return a;
528
    }
541
    }
529
   
542
   
530
    /*
543
    /*
531
     * Search the leaf node and the righmost record of its left neighbour
544
     * Search the leaf node and the righmost record of its left neighbour
532
     * to find out whether this is a miss or va belongs to an address
545
     * to find out whether this is a miss or va belongs to an address
533
     * space area found there.
546
     * space area found there.
534
     */
547
     */
535
   
548
   
536
    /* First, search the leaf node itself. */
549
    /* First, search the leaf node itself. */
537
    for (i = 0; i < leaf->keys; i++) {
550
    for (i = 0; i < leaf->keys; i++) {
538
        a = (as_area_t *) leaf->value[i];
551
        a = (as_area_t *) leaf->value[i];
539
        spinlock_lock(&a->lock);
552
        spinlock_lock(&a->lock);
540
        if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) {
553
        if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) {
541
            return a;
554
            return a;
542
        }
555
        }
543
        spinlock_unlock(&a->lock);
556
        spinlock_unlock(&a->lock);
544
    }
557
    }
545
 
558
 
546
    /*
559
    /*
547
     * Second, locate the left neighbour and test its last record.
560
     * Second, locate the left neighbour and test its last record.
548
     * Because of its position in the B+tree, it must have base < va.
561
     * Because of its position in the B+tree, it must have base < va.
549
     */
562
     */
550
    if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
563
    if ((lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
551
        a = (as_area_t *) lnode->value[lnode->keys - 1];
564
        a = (as_area_t *) lnode->value[lnode->keys - 1];
552
        spinlock_lock(&a->lock);
565
        spinlock_lock(&a->lock);
553
        if (va < a->base + a->pages * PAGE_SIZE) {
566
        if (va < a->base + a->pages * PAGE_SIZE) {
554
            return a;
567
            return a;
555
        }
568
        }
556
        spinlock_unlock(&a->lock);
569
        spinlock_unlock(&a->lock);
557
    }
570
    }
558
 
571
 
559
    return NULL;
572
    return NULL;
560
}
573
}
561
 
574
 
562
/** Check area conflicts with other areas.
575
/** Check area conflicts with other areas.
563
 *
576
 *
564
 * The address space must be locked and interrupts must be disabled.
577
 * The address space must be locked and interrupts must be disabled.
565
 *
578
 *
566
 * @param as Address space.
579
 * @param as Address space.
567
 * @param va Starting virtual address of the area being tested.
580
 * @param va Starting virtual address of the area being tested.
568
 * @param size Size of the area being tested.
581
 * @param size Size of the area being tested.
569
 * @param avoid_area Do not touch this area.
582
 * @param avoid_area Do not touch this area.
570
 *
583
 *
571
 * @return True if there is no conflict, false otherwise.
584
 * @return True if there is no conflict, false otherwise.
572
 */
585
 */
573
bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area)
586
bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area)
574
{
587
{
575
    as_area_t *a;
588
    as_area_t *a;
576
    btree_node_t *leaf, *node;
589
    btree_node_t *leaf, *node;
577
    int i;
590
    int i;
578
   
591
   
579
    /*
592
    /*
580
     * We don't want any area to have conflicts with NULL page.
593
     * We don't want any area to have conflicts with NULL page.
581
     */
594
     */
582
    if (overlaps(va, size, NULL, PAGE_SIZE))
595
    if (overlaps(va, size, NULL, PAGE_SIZE))
583
        return false;
596
        return false;
584
   
597
   
585
    /*
598
    /*
586
     * The leaf node is found in O(log n), where n is proportional to
599
     * The leaf node is found in O(log n), where n is proportional to
587
     * the number of address space areas belonging to as.
600
     * the number of address space areas belonging to as.
588
     * The check for conflicts is then attempted on the rightmost
601
     * The check for conflicts is then attempted on the rightmost
589
     * record in the left neighbour, the leftmost record in the right
602
     * record in the left neighbour, the leftmost record in the right
590
     * neighbour and all records in the leaf node itself.
603
     * neighbour and all records in the leaf node itself.
591
     */
604
     */
592
   
605
   
593
    if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) {
606
    if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) {
594
        if (a != avoid_area)
607
        if (a != avoid_area)
595
            return false;
608
            return false;
596
    }
609
    }
597
   
610
   
598
    /* First, check the two border cases. */
611
    /* First, check the two border cases. */
599
    if ((node = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
612
    if ((node = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf))) {
600
        a = (as_area_t *) node->value[node->keys - 1];
613
        a = (as_area_t *) node->value[node->keys - 1];
601
        spinlock_lock(&a->lock);
614
        spinlock_lock(&a->lock);
602
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
615
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
603
            spinlock_unlock(&a->lock);
616
            spinlock_unlock(&a->lock);
604
            return false;
617
            return false;
605
        }
618
        }
606
        spinlock_unlock(&a->lock);
619
        spinlock_unlock(&a->lock);
607
    }
620
    }
608
    if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) {
621
    if ((node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf))) {
609
        a = (as_area_t *) node->value[0];
622
        a = (as_area_t *) node->value[0];
610
        spinlock_lock(&a->lock);
623
        spinlock_lock(&a->lock);
611
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
624
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
612
            spinlock_unlock(&a->lock);
625
            spinlock_unlock(&a->lock);
613
            return false;
626
            return false;
614
        }
627
        }
615
        spinlock_unlock(&a->lock);
628
        spinlock_unlock(&a->lock);
616
    }
629
    }
617
   
630
   
618
    /* Second, check the leaf node. */
631
    /* Second, check the leaf node. */
619
    for (i = 0; i < leaf->keys; i++) {
632
    for (i = 0; i < leaf->keys; i++) {
620
        a = (as_area_t *) leaf->value[i];
633
        a = (as_area_t *) leaf->value[i];
621
   
634
   
622
        if (a == avoid_area)
635
        if (a == avoid_area)
623
            continue;
636
            continue;
624
   
637
   
625
        spinlock_lock(&a->lock);
638
        spinlock_lock(&a->lock);
626
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
639
        if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
627
            spinlock_unlock(&a->lock);
640
            spinlock_unlock(&a->lock);
628
            return false;
641
            return false;
629
        }
642
        }
630
        spinlock_unlock(&a->lock);
643
        spinlock_unlock(&a->lock);
631
    }
644
    }
632
 
645
 
633
    /*
646
    /*
634
     * So far, the area does not conflict with other areas.
647
     * So far, the area does not conflict with other areas.
635
     * Check if it doesn't conflict with kernel address space.
648
     * Check if it doesn't conflict with kernel address space.
636
     */  
649
     */  
637
    if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
650
    if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
638
        return !overlaps(va, size,
651
        return !overlaps(va, size,
639
            KERNEL_ADDRESS_SPACE_START, KERNEL_ADDRESS_SPACE_END-KERNEL_ADDRESS_SPACE_START);
652
            KERNEL_ADDRESS_SPACE_START, KERNEL_ADDRESS_SPACE_END-KERNEL_ADDRESS_SPACE_START);
640
    }
653
    }
641
 
654
 
642
    return true;
655
    return true;
643
}
656
}
644
 
657