Subversion Repositories HelenOS

Rev

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

Rev Author Line No. Line
684 jermar 1
/*
2
 * Copyright (C) 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
 
29
#include <genarch/mm/page_ht.h>
30
#include <mm/page.h>
792 jermar 31
#include <arch/mm/page.h>
684 jermar 32
#include <mm/frame.h>
699 jermar 33
#include <mm/heap.h>
755 jermar 34
#include <mm/as.h>
687 jermar 35
#include <arch/mm/asid.h>
684 jermar 36
#include <arch/types.h>
37
#include <typedefs.h>
38
#include <arch/asm.h>
746 jermar 39
#include <synch/spinlock.h>
40
#include <arch.h>
699 jermar 41
#include <debug.h>
756 jermar 42
#include <memstr.h>
792 jermar 43
#include <adt/hash_table.h>
684 jermar 44
 
792 jermar 45
static index_t hash(__native key[]);
46
static bool compare(__native key[], count_t keys, link_t *item);
47
static void remove_callback(link_t *item);
48
 
49
static void ht_mapping_insert(as_t *as, __address page, __address frame, int flags);
50
static pte_t *ht_mapping_find(as_t *as, __address page);
51
 
746 jermar 52
/**
756 jermar 53
 * This lock protects the page hash table.
746 jermar 54
 */
55
SPINLOCK_INITIALIZE(page_ht_lock);
56
 
57
/**
792 jermar 58
 * Page hash table.
746 jermar 59
 * The page hash table may be accessed only when page_ht_lock is held.
60
 */
792 jermar 61
hash_table_t page_ht;
746 jermar 62
 
792 jermar 63
/** Hash table operations for page hash table. */
64
hash_table_operations_t ht_operations = {
65
    .hash = hash,
66
    .compare = compare,
67
    .remove_callback = remove_callback
68
};
684 jermar 69
 
793 jermar 70
/** Page mapping operations for page hash table architectures. */
71
page_mapping_operations_t ht_mapping_operations = {
684 jermar 72
    .mapping_insert = ht_mapping_insert,
757 jermar 73
    .mapping_find = ht_mapping_find
684 jermar 74
};
75
 
792 jermar 76
/** Compute page hash table index.
77
 *
78
 * @param key Array of two keys (i.e. page and address space).
79
 *
80
 * @return Index into page hash table.
81
 */
82
index_t hash(__native key[])
83
{
84
    as_t *as = (as_t *) key[KEY_AS];
85
    __address page = (__address) key[KEY_PAGE];
86
    index_t index;
87
 
88
    /*
89
     * Virtual page addresses have roughly the same probability
90
     * of occurring. Least significant bits of VPN compose the
91
     * hash index.
92
     */
93
    index = ((page >> PAGE_WIDTH) & (PAGE_HT_ENTRIES-1));
94
 
95
    /*
96
     * Address space structures are likely to be allocated from
97
     * similar addresses. Least significant bits compose the
98
     * hash index.
99
     */
100
    index |= ((__native) as) & (PAGE_HT_ENTRIES-1);
101
 
102
    return index;
103
}
104
 
105
/** Compare page hash table item with page and/or address space.
106
 *
107
 * @param key Array of one or two keys (i.e. page and/or address space).
108
 * @param keys Number of keys passed.
109
 * @param item Item to compare the keys with.
110
 *
111
 * @return true on match, false otherwise.
112
 */
113
bool compare(__native key[], count_t keys, link_t *item)
114
{
115
    pte_t *t;
116
 
117
    ASSERT(item);
118
    ASSERT((keys > 0) && (keys <= PAGE_HT_KEYS));
119
 
120
    /*
121
     * Convert item to PTE.
122
     */
793 jermar 123
    t = hash_table_get_instance(item, pte_t, link);
792 jermar 124
 
125
    if (keys == PAGE_HT_KEYS) {
126
        return (key[KEY_AS] == (__address) t->as) && (key[KEY_PAGE] == t->page);
127
    } else {
128
        return (key[KEY_AS] == (__address) t->as);
129
    }
130
}
131
 
132
/** Callback on page hash table item removal.
133
 *
134
 * @param item Page hash table item being removed.
135
 */
136
void remove_callback(link_t *item)
137
{
138
    pte_t *t;
139
 
140
    ASSERT(item);
141
 
142
    /*
143
     * Convert item to PTE.
144
     */
793 jermar 145
    t = hash_table_get_instance(item, pte_t, link);
792 jermar 146
 
147
    free(t);
148
}
149
 
684 jermar 150
/** Map page to frame using page hash table.
151
 *
152
 * Map virtual address 'page' to physical address 'frame'
756 jermar 153
 * using 'flags'.
684 jermar 154
 *
756 jermar 155
 * The address space must be locked and interruptsmust be disabled.
156
 *
157
 * @param as Address space to which page belongs.
684 jermar 158
 * @param page Virtual address of the page to be mapped.
159
 * @param frame Physical address of memory frame to which the mapping is done.
160
 * @param flags Flags to be used for mapping.
161
 */
756 jermar 162
void ht_mapping_insert(as_t *as, __address page, __address frame, int flags)
684 jermar 163
{
792 jermar 164
    pte_t *t;
746 jermar 165
    ipl_t ipl;
792 jermar 166
    __native key[2] = { (__address) as, page };
699 jermar 167
 
746 jermar 168
    ipl = interrupts_disable();
169
    spinlock_lock(&page_ht_lock);
755 jermar 170
 
792 jermar 171
    if (!hash_table_find(&page_ht, key)) {
172
        t = (pte_t *) malloc(sizeof(pte_t));
173
        ASSERT(t != NULL);
746 jermar 174
 
792 jermar 175
        hash_table_insert(&page_ht, key, &t->link);
699 jermar 176
    }
746 jermar 177
 
178
    spinlock_unlock(&page_ht_lock);
179
    interrupts_restore(ipl);
684 jermar 180
}
181
 
182
/** Find mapping for virtual page in page hash table.
183
 *
184
 * Find mapping for virtual page.
185
 *
756 jermar 186
 * The address space must be locked and interrupts must be disabled.
746 jermar 187
 *
756 jermar 188
 * @param as Address space to wich page belongs.
684 jermar 189
 * @param page Virtual page.
190
 *
699 jermar 191
 * @return NULL if there is no such mapping; requested mapping otherwise.
684 jermar 192
 */
756 jermar 193
pte_t *ht_mapping_find(as_t *as, __address page)
684 jermar 194
{
792 jermar 195
    link_t *hlp;
196
    pte_t *t = NULL;
197
    __native key[2] = { (__address) as, page };
699 jermar 198
 
746 jermar 199
    spinlock_lock(&page_ht_lock);
792 jermar 200
 
201
    hlp = hash_table_find(&page_ht, key);
202
    if (hlp)
793 jermar 203
        t = hash_table_get_instance(hlp, pte_t, link);
792 jermar 204
 
746 jermar 205
    spinlock_unlock(&page_ht_lock);
206
    return t;
207
}