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 
}