URL https://opencores.org/ocsvn/test_project/test_project/trunk

Subversion Repositories test_project

[/] [test_project/] [trunk/] [linux_sd_driver/] [mm/] [prio_tree.c] - Blame information for rev 62

Details | Compare with Previous | View Log


/*
 * 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>
 
/*
 * 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;
}

Browse

Tools

Subversion Repositories test_project

[/] [test_project/] [trunk/] [linux_sd_driver/] [mm/] [prio_tree.c] - Blame information for rev 62

Line No.	Rev	Author	Line
1	62	marcus.erl	`/*`
2			`* mm/prio_tree.c - priority search tree for mapping->i_mmap`
3			`*`
4			`* Copyright (C) 2004, Rajesh Venkatasubramanian <vrajesh@umich.edu>`
5			`*`
6			`* This file is released under the GPL v2.`
7			`*`
8			`* Based on the radix priority search tree proposed by Edward M. McCreight`
9			`* SIAM Journal of Computing, vol. 14, no.2, pages 257-276, May 1985`
10			`*`
11			`* 02Feb2004 Initial version`
12			`*/`
13
14			`#include <linux/mm.h>`
15			`#include <linux/prio_tree.h>`
16
17			`/*`
18			`* See lib/prio_tree.c for details on the general radix priority search tree`
19			`* code.`
20			`*/`
21
22			`/*`
23			`* The following #defines are mirrored from lib/prio_tree.c. They're only used`
24			`* for debugging, and should be removed (along with the debugging code using`
25			`* them) when switching also VMAs to the regular prio_tree code.`
26			`*/`
27
28			`#define RADIX_INDEX(vma) ((vma)->vm_pgoff)`
29			`#define VMA_SIZE(vma) (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT)`
30			`/* avoid overflow */`
31			`#define HEAP_INDEX(vma) ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1))`
32
33			`/*`
34			`* Radix priority search tree for address_space->i_mmap`
35			`*`
36			`* For each vma that map a unique set of file pages i.e., unique [radix_index,`
37			`* heap_index] value, we have a corresponding priority search tree node. If`
38			`* multiple vmas have identical [radix_index, heap_index] value, then one of`
39			`* them is used as a tree node and others are stored in a vm_set list. The tree`
40			`* node points to the first vma (head) of the list using vm_set.head.`
41			`*`
42			`* prio_tree_root`
43			`* \|`
44			`* A vm_set.head`
45			`* / \ /`
46			`* L R -> H-I-J-K-M-N-O-P-Q-S`
47			`* ^ ^ <-- vm_set.list -->`
48			`* tree nodes`
49			`*`
50			`* We need some way to identify whether a vma is a tree node, head of a vm_set`
51			`* list, or just a member of a vm_set list. We cannot use vm_flags to store`
52			`* such information. The reason is, in the above figure, it is possible that`
53			`* vm_flags' of R and H are covered by the different mmap_sems. When R is`
54			`* removed under R->mmap_sem, H replaces R as a tree node. Since we do not hold`
55			`* H->mmap_sem, we cannot use H->vm_flags for marking that H is a tree node now.`
56			`* That's why some trick involving shared.vm_set.parent is used for identifying`
57			`* tree nodes and list head nodes.`
58			`*`
59			`* vma radix priority search tree node rules:`
60			`*`
61			`* vma->shared.vm_set.parent != NULL ==> a tree node`
62			`* vma->shared.vm_set.head != NULL ==> list of others mapping same range`
63			`* vma->shared.vm_set.head == NULL ==> no others map the same range`
64			`*`
65			`* vma->shared.vm_set.parent == NULL`
66			`* vma->shared.vm_set.head != NULL ==> list head of vmas mapping same range`
67			`* vma->shared.vm_set.head == NULL ==> a list node`
68			`*/`
69
70			`/*`
71			`* Add a new vma known to map the same set of pages as the old vma:`
72			`* useful for fork's dup_mmap as well as vma_prio_tree_insert below.`
73			`* Note that it just happens to work correctly on i_mmap_nonlinear too.`
74			`*/`
75			`void vma_prio_tree_add(struct vm_area_struct vma, struct vm_area_struct old)`
76			`{`
77			`/* Leave these BUG_ONs till prio_tree patch stabilizes */`
78			`BUG_ON(RADIX_INDEX(vma) != RADIX_INDEX(old));`
79			`BUG_ON(HEAP_INDEX(vma) != HEAP_INDEX(old));`
80
81			`vma->shared.vm_set.head = NULL;`
82			`vma->shared.vm_set.parent = NULL;`
83
84			`if (!old->shared.vm_set.parent)`
85			`list_add(&vma->shared.vm_set.list,`
86			`&old->shared.vm_set.list);`
87			`else if (old->shared.vm_set.head)`
88			`list_add_tail(&vma->shared.vm_set.list,`
89			`&old->shared.vm_set.head->shared.vm_set.list);`
90			`else {`
91			`INIT_LIST_HEAD(&vma->shared.vm_set.list);`
92			`vma->shared.vm_set.head = old;`
93			`old->shared.vm_set.head = vma;`
94			`}`
95			`}`
96
97			`void vma_prio_tree_insert(struct vm_area_struct *vma,`
98			`struct prio_tree_root *root)`
99			`{`
100			`struct prio_tree_node *ptr;`
101			`struct vm_area_struct *old;`
102
103			`vma->shared.vm_set.head = NULL;`
104
105			`ptr = raw_prio_tree_insert(root, &vma->shared.prio_tree_node);`
106			`if (ptr != (struct prio_tree_node *) &vma->shared.prio_tree_node) {`
107			`old = prio_tree_entry(ptr, struct vm_area_struct,`
108			`shared.prio_tree_node);`
109			`vma_prio_tree_add(vma, old);`
110			`}`
111			`}`
112
113			`void vma_prio_tree_remove(struct vm_area_struct *vma,`
114			`struct prio_tree_root *root)`
115			`{`
116			`struct vm_area_struct node, head, *new_head;`
117
118			`if (!vma->shared.vm_set.head) {`
119			`if (!vma->shared.vm_set.parent)`
120			`list_del_init(&vma->shared.vm_set.list);`
121			`else`
122			`raw_prio_tree_remove(root, &vma->shared.prio_tree_node);`
123			`} else {`
124			`/* Leave this BUG_ON till prio_tree patch stabilizes */`
125			`BUG_ON(vma->shared.vm_set.head->shared.vm_set.head != vma);`
126			`if (vma->shared.vm_set.parent) {`
127			`head = vma->shared.vm_set.head;`
128			`if (!list_empty(&head->shared.vm_set.list)) {`
129			`new_head = list_entry(`
130			`head->shared.vm_set.list.next,`
131			`struct vm_area_struct,`
132			`shared.vm_set.list);`
133			`list_del_init(&head->shared.vm_set.list);`
134			`} else`
135			`new_head = NULL;`
136
137			`raw_prio_tree_replace(root, &vma->shared.prio_tree_node,`
138			`&head->shared.prio_tree_node);`
139			`head->shared.vm_set.head = new_head;`
140			`if (new_head)`
141			`new_head->shared.vm_set.head = head;`
142
143			`} else {`
144			`node = vma->shared.vm_set.head;`
145			`if (!list_empty(&vma->shared.vm_set.list)) {`
146			`new_head = list_entry(`
147			`vma->shared.vm_set.list.next,`
148			`struct vm_area_struct,`
149			`shared.vm_set.list);`
150			`list_del_init(&vma->shared.vm_set.list);`
151			`node->shared.vm_set.head = new_head;`
152			`new_head->shared.vm_set.head = node;`
153			`} else`
154			`node->shared.vm_set.head = NULL;`
155			`}`
156			`}`
157			`}`
158
159			`/*`
160			`* Helper function to enumerate vmas that map a given file page or a set of`
161			`* contiguous file pages. The function returns vmas that at least map a single`
162			`* page in the given range of contiguous file pages.`
163			`*/`
164			`struct vm_area_struct vma_prio_tree_next(struct vm_area_struct vma,`
165			`struct prio_tree_iter *iter)`
166			`{`
167			`struct prio_tree_node *ptr;`
168			`struct vm_area_struct *next;`
169
170			`if (!vma) {`
171			`/*`
172			`* First call is with NULL vma`
173			`*/`
174			`ptr = prio_tree_next(iter);`
175			`if (ptr) {`
176			`next = prio_tree_entry(ptr, struct vm_area_struct,`
177			`shared.prio_tree_node);`
178			`prefetch(next->shared.vm_set.head);`
179			`return next;`
180			`} else`
181			`return NULL;`
182			`}`
183
184			`if (vma->shared.vm_set.parent) {`
185			`if (vma->shared.vm_set.head) {`
186			`next = vma->shared.vm_set.head;`
187			`prefetch(next->shared.vm_set.list.next);`
188			`return next;`
189			`}`
190			`} else {`
191			`next = list_entry(vma->shared.vm_set.list.next,`
192			`struct vm_area_struct, shared.vm_set.list);`
193			`if (!next->shared.vm_set.head) {`
194			`prefetch(next->shared.vm_set.list.next);`
195			`return next;`
196			`}`
197			`}`
198
199			`ptr = prio_tree_next(iter);`
200			`if (ptr) {`
201			`next = prio_tree_entry(ptr, struct vm_area_struct,`
202			`shared.prio_tree_node);`
203			`prefetch(next->shared.vm_set.head);`
204			`return next;`
205			`} else`
206			`return NULL;`
207			`}`