Subversion Repositories HelenOS-historic

Compare Revisions

Ignore whitespace Rev 1146 → Rev 1147

/kernel/trunk/generic/include/adt/btree.h
83,5 → 83,8
extern void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node);
extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node);
 
extern btree_node_t *btree_node_left_sibling(btree_t *t, btree_node_t *node);
extern btree_node_t *btree_node_right_sibling(btree_t *t, btree_node_t *node);
 
extern void btree_print(btree_t *t);
#endif
/kernel/trunk/generic/include/mm/as.h
36,6 → 36,7
#include <typedefs.h>
#include <synch/spinlock.h>
#include <adt/list.h>
#include <adt/btree.h>
 
/** Defined to be true if user address space and kernel address space shadow each other. */
#define KERNEL_ADDRESS_SPACE_SHADOWED KERNEL_ADDRESS_SPACE_SHADOWED_ARCH
63,7 → 64,6
*/
struct as_area {
SPINLOCK_DECLARE(lock);
link_t link;
int flags;
count_t pages; /**< Size of this area in multiples of PAGE_SIZE. */
__address base; /**< Base address of this area. */
85,7 → 85,8
/** Number of processors on wich is this address space active. */
count_t refcount;
 
link_t as_area_head;
/** B+-tree of address space areas. */
btree_t as_area_btree;
 
/** Page table pointer. Constant on architectures that use global page hash table. */
pte_t *page_table;
/kernel/trunk/generic/src/adt/btree.c
340,6 → 340,38
return NULL;
}
 
/** Return pointer to B-tree node's left sibling.
*
* @param t B-tree.
* @param node Node whose left sibling will be returned.
*
* @return Left sibling of the node or NULL if the node does not have the left sibling.
*/
btree_node_t *btree_node_left_sibling(btree_t *t, btree_node_t *node)
{
ASSERT(LEAF_NODE(node));
if (node->leaf_link.prev != &t->leaf_head)
return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
else
return NULL;
}
 
/** Return pointer to B-tree node's right sibling.
*
* @param t B-tree.
* @param node Node whose right sibling will be returned.
*
* @return Right sibling of the node or NULL if the node does not have the right sibling.
*/
btree_node_t *btree_node_right_sibling(btree_t *t, btree_node_t *node)
{
ASSERT(LEAF_NODE(node));
if (node->leaf_link.next != &t->leaf_head)
return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
else
return NULL;
}
 
/** Initialize B-tree node.
*
* @param node B-tree node.
/kernel/trunk/generic/src/mm/as.c
48,6 → 48,7
#include <synch/spinlock.h>
#include <config.h>
#include <adt/list.h>
#include <adt/btree.h>
#include <panic.h>
#include <arch/asm.h>
#include <debug.h>
94,7 → 95,7
as = (as_t *) malloc(sizeof(as_t), 0);
link_initialize(&as->inactive_as_with_asid_link);
spinlock_initialize(&as->lock, "as_lock");
list_initialize(&as->as_area_head);
btree_create(&as->as_area_btree);
if (flags & FLAG_AS_KERNEL)
as->asid = ASID_KERNEL;
153,12 → 154,11
 
spinlock_initialize(&a->lock, "as_area_lock");
link_initialize(&a->link);
a->flags = flags;
a->pages = SIZE2FRAMES(size);
a->base = base;
list_append(&a->link, &as->as_area_head);
btree_insert(&as->as_area_btree, base, (void *) a, NULL);
 
spinlock_unlock(&as->lock);
interrupts_restore(ipl);
445,18 → 445,12
}
 
pages = SIZE2FRAMES((address - area->base) + size);
if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
spinlock_unlock(&area->lock);
spinlock_unlock(&as->lock);
interrupts_restore(ipl);
return (__address) -1;
}
 
if (pages < area->pages) {
int i;
 
/*
* Shrinking the area.
* No need to check for overlaps.
*/
for (i = pages; i < area->pages; i++) {
pte_t *pte;
486,6 → 480,17
tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages);
tlb_shootdown_finalize();
} else {
/*
* Growing the area.
* Check for overlaps with other address space areas.
*/
if (!check_area_conflicts(as, address, pages * PAGE_SIZE, area)) {
spinlock_unlock(&area->lock);
spinlock_unlock(&as->lock);
interrupts_restore(ipl);
return (__address) -1;
}
}
 
area->pages = pages;
508,16 → 513,43
*/
as_area_t *find_area_and_lock(as_t *as, __address va)
{
link_t *cur;
as_area_t *a;
btree_node_t *leaf, *lnode;
int i;
for (cur = as->as_area_head.next; cur != &as->as_area_head; cur = cur->next) {
a = list_get_instance(cur, as_area_t, link);
a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
if (a) {
/* va is the base address of an address space area */
spinlock_lock(&a->lock);
return a;
}
/*
* Search the leaf node and the righmost record of its left sibling
* to find out whether this is a miss or va belongs to an address
* space area found there.
*/
/* First, search the leaf node itself. */
for (i = 0; i < leaf->keys; i++) {
a = (as_area_t *) leaf->value[i];
spinlock_lock(&a->lock);
if ((a->base <= va) && (va < a->base + a->pages * PAGE_SIZE)) {
return a;
}
spinlock_unlock(&a->lock);
}
 
if ((va >= a->base) && (va < a->base + a->pages * PAGE_SIZE))
/*
* Second, locate the left sibling and test its last record.
* Because of its position in the B+-tree, it must have base < va.
*/
if ((lnode = btree_node_left_sibling(&as->as_area_btree, leaf))) {
a = (as_area_t *) lnode->value[lnode->keys - 1];
spinlock_lock(&a->lock);
if (va < a->base + a->pages * PAGE_SIZE) {
return a;
}
spinlock_unlock(&a->lock);
}
 
537,8 → 569,9
*/
bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area)
{
link_t *cur;
as_area_t *a;
btree_node_t *leaf, *node;
int i;
/*
* We don't want any area to have conflicts with NULL page.
546,24 → 579,52
if (overlaps(va, size, NULL, PAGE_SIZE))
return false;
for (cur = as->as_area_head.next; cur != &as->as_area_head; cur = cur->next) {
__address a_start;
size_t a_size;
/*
* The leaf node is found in O(log n), where n is proportional to
* the number of address space areas belonging to as.
* The check for conflicts is then attempted on the rightmost
* record in the left sibling, the leftmost record in the right
* sibling and all records in the leaf node itself.
*/
a = list_get_instance(cur, as_area_t, link);
if ((a = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf))) {
if (a != avoid_area)
return false;
}
/* First, check the two border cases. */
if ((node = btree_node_left_sibling(&as->as_area_btree, leaf))) {
a = (as_area_t *) node->value[node->keys - 1];
spinlock_lock(&a->lock);
if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
spinlock_unlock(&a->lock);
return false;
}
spinlock_unlock(&a->lock);
}
if ((node = btree_node_right_sibling(&as->as_area_btree, leaf))) {
a = (as_area_t *) node->value[0];
spinlock_lock(&a->lock);
if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
spinlock_unlock(&a->lock);
return false;
}
spinlock_unlock(&a->lock);
}
/* Second, check the leaf node. */
for (i = 0; i < leaf->keys; i++) {
a = (as_area_t *) leaf->value[i];
if (a == avoid_area)
continue;
spinlock_lock(&a->lock);
 
a_start = a->base;
a_size = a->pages * PAGE_SIZE;
 
if (overlaps(va, size, a->base, a->pages * PAGE_SIZE)) {
spinlock_unlock(&a->lock);
return false;
}
spinlock_unlock(&a->lock);
 
if (overlaps(va, size, a_start, a_size))
return false;
 
}
 
/*