Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

209 lines (189 sloc) 6.481 kb
/*
* mm/prio_tree.c - priority search tree for mapping->i_mmap
*
* Copyright (C) 2004, Rajesh Venkatasubramanian <vrajesh@umich.edu>
*
* This file is released under the GPL v2.
*
* Based on the radix priority search tree proposed by Edward M. McCreight
* SIAM Journal of Computing, vol. 14, no.2, pages 257-276, May 1985
*
* 02Feb2004 Initial version
*/
#include <linux/mm.h>
#include <linux/prio_tree.h>
#include <linux/prefetch.h>
/*
* See lib/prio_tree.c for details on the general radix priority search tree
* code.
*/
/*
* The following #defines are mirrored from lib/prio_tree.c. They're only used
* for debugging, and should be removed (along with the debugging code using
* them) when switching also VMAs to the regular prio_tree code.
*/
#define RADIX_INDEX(vma) ((vma)->vm_pgoff)
#define VMA_SIZE(vma) (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT)
/* avoid overflow */
#define HEAP_INDEX(vma) ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1))
/*
* Radix priority search tree for address_space->i_mmap
*
* For each vma that map a unique set of file pages i.e., unique [radix_index,
* heap_index] value, we have a corresponding priority search tree node. If
* multiple vmas have identical [radix_index, heap_index] value, then one of
* them is used as a tree node and others are stored in a vm_set list. The tree
* node points to the first vma (head) of the list using vm_set.head.
*
* prio_tree_root
* |
* A vm_set.head
* / \ /
* L R -> H-I-J-K-M-N-O-P-Q-S
* ^ ^ <-- vm_set.list -->
* tree nodes
*
* We need some way to identify whether a vma is a tree node, head of a vm_set
* list, or just a member of a vm_set list. We cannot use vm_flags to store
* such information. The reason is, in the above figure, it is possible that
* vm_flags' of R and H are covered by the different mmap_sems. When R is
* removed under R->mmap_sem, H replaces R as a tree node. Since we do not hold
* H->mmap_sem, we cannot use H->vm_flags for marking that H is a tree node now.
* That's why some trick involving shared.vm_set.parent is used for identifying
* tree nodes and list head nodes.
*
* vma radix priority search tree node rules:
*
* vma->shared.vm_set.parent != NULL ==> a tree node
* vma->shared.vm_set.head != NULL ==> list of others mapping same range
* vma->shared.vm_set.head == NULL ==> no others map the same range
*
* vma->shared.vm_set.parent == NULL
* vma->shared.vm_set.head != NULL ==> list head of vmas mapping same range
* vma->shared.vm_set.head == NULL ==> a list node
*/
/*
* Add a new vma known to map the same set of pages as the old vma:
* useful for fork's dup_mmap as well as vma_prio_tree_insert below.
* Note that it just happens to work correctly on i_mmap_nonlinear too.
*/
void vma_prio_tree_add(struct vm_area_struct *vma, struct vm_area_struct *old)
{
/* Leave these BUG_ONs till prio_tree patch stabilizes */
BUG_ON(RADIX_INDEX(vma) != RADIX_INDEX(old));
BUG_ON(HEAP_INDEX(vma) != HEAP_INDEX(old));
vma->shared.vm_set.head = NULL;
vma->shared.vm_set.parent = NULL;
if (!old->shared.vm_set.parent)
list_add(&vma->shared.vm_set.list,
&old->shared.vm_set.list);
else if (old->shared.vm_set.head)
list_add_tail(&vma->shared.vm_set.list,
&old->shared.vm_set.head->shared.vm_set.list);
else {
INIT_LIST_HEAD(&vma->shared.vm_set.list);
vma->shared.vm_set.head = old;
old->shared.vm_set.head = vma;
}
}
void vma_prio_tree_insert(struct vm_area_struct *vma,
struct prio_tree_root *root)
{
struct prio_tree_node *ptr;
struct vm_area_struct *old;
vma->shared.vm_set.head = NULL;
ptr = raw_prio_tree_insert(root, &vma->shared.prio_tree_node);
if (ptr != (struct prio_tree_node *) &vma->shared.prio_tree_node) {
old = prio_tree_entry(ptr, struct vm_area_struct,
shared.prio_tree_node);
vma_prio_tree_add(vma, old);
}
}
void vma_prio_tree_remove(struct vm_area_struct *vma,
struct prio_tree_root *root)
{
struct vm_area_struct *node, *head, *new_head;
if (!vma->shared.vm_set.head) {
if (!vma->shared.vm_set.parent)
list_del_init(&vma->shared.vm_set.list);
else
raw_prio_tree_remove(root, &vma->shared.prio_tree_node);
} else {
/* Leave this BUG_ON till prio_tree patch stabilizes */
BUG_ON(vma->shared.vm_set.head->shared.vm_set.head != vma);
if (vma->shared.vm_set.parent) {
head = vma->shared.vm_set.head;
if (!list_empty(&head->shared.vm_set.list)) {
new_head = list_entry(
head->shared.vm_set.list.next,
struct vm_area_struct,
shared.vm_set.list);
list_del_init(&head->shared.vm_set.list);
} else
new_head = NULL;
raw_prio_tree_replace(root, &vma->shared.prio_tree_node,
&head->shared.prio_tree_node);
head->shared.vm_set.head = new_head;
if (new_head)
new_head->shared.vm_set.head = head;
} else {
node = vma->shared.vm_set.head;
if (!list_empty(&vma->shared.vm_set.list)) {
new_head = list_entry(
vma->shared.vm_set.list.next,
struct vm_area_struct,
shared.vm_set.list);
list_del_init(&vma->shared.vm_set.list);
node->shared.vm_set.head = new_head;
new_head->shared.vm_set.head = node;
} else
node->shared.vm_set.head = NULL;
}
}
}
/*
* Helper function to enumerate vmas that map a given file page or a set of
* contiguous file pages. The function returns vmas that at least map a single
* page in the given range of contiguous file pages.
*/
struct vm_area_struct *vma_prio_tree_next(struct vm_area_struct *vma,
struct prio_tree_iter *iter)
{
struct prio_tree_node *ptr;
struct vm_area_struct *next;
if (!vma) {
/*
* First call is with NULL vma
*/
ptr = prio_tree_next(iter);
if (ptr) {
next = prio_tree_entry(ptr, struct vm_area_struct,
shared.prio_tree_node);
prefetch(next->shared.vm_set.head);
return next;
} else
return NULL;
}
if (vma->shared.vm_set.parent) {
if (vma->shared.vm_set.head) {
next = vma->shared.vm_set.head;
prefetch(next->shared.vm_set.list.next);
return next;
}
} else {
next = list_entry(vma->shared.vm_set.list.next,
struct vm_area_struct, shared.vm_set.list);
if (!next->shared.vm_set.head) {
prefetch(next->shared.vm_set.list.next);
return next;
}
}
ptr = prio_tree_next(iter);
if (ptr) {
next = prio_tree_entry(ptr, struct vm_area_struct,
shared.prio_tree_node);
prefetch(next->shared.vm_set.head);
return next;
} else
return NULL;
}
Jump to Line
Something went wrong with that request. Please try again.