diff options
Diffstat (limited to 'Documentation')
| -rw-r--r-- | Documentation/00-INDEX | 2 | ||||
| -rw-r--r-- | Documentation/ABI/obsolete/proc-pid-oom_adj | 22 | ||||
| -rw-r--r-- | Documentation/cgroups/memory.txt | 90 | ||||
| -rw-r--r-- | Documentation/filesystems/proc.txt | 22 | ||||
| -rw-r--r-- | Documentation/memory.txt | 33 | ||||
| -rw-r--r-- | Documentation/prio_tree.txt | 107 | ||||
| -rw-r--r-- | Documentation/rbtree.txt | 209 | ||||
| -rw-r--r-- | Documentation/vm/unevictable-lru.txt | 14 |
8 files changed, 227 insertions, 272 deletions
diff --git a/Documentation/00-INDEX b/Documentation/00-INDEX index 49c051380daf..f54273e2ac97 100644 --- a/Documentation/00-INDEX +++ b/Documentation/00-INDEX @@ -270,8 +270,6 @@ preempt-locking.txt - info on locking under a preemptive kernel. printk-formats.txt - how to get printk format specifiers right -prio_tree.txt - - info on radix-priority-search-tree use for indexing vmas. ramoops.txt - documentation of the ramoops oops/panic logging module. rbtree.txt diff --git a/Documentation/ABI/obsolete/proc-pid-oom_adj b/Documentation/ABI/obsolete/proc-pid-oom_adj deleted file mode 100644 index 9a3cb88ade47..000000000000 --- a/Documentation/ABI/obsolete/proc-pid-oom_adj +++ /dev/null @@ -1,22 +0,0 @@ -What: /proc/<pid>/oom_adj -When: August 2012 -Why: /proc/<pid>/oom_adj allows userspace to influence the oom killer's - badness heuristic used to determine which task to kill when the kernel - is out of memory. - - The badness heuristic has since been rewritten since the introduction of - this tunable such that its meaning is deprecated. The value was - implemented as a bitshift on a score generated by the badness() - function that did not have any precise units of measure. With the - rewrite, the score is given as a proportion of available memory to the - task allocating pages, so using a bitshift which grows the score - exponentially is, thus, impossible to tune with fine granularity. - - A much more powerful interface, /proc/<pid>/oom_score_adj, was - introduced with the oom killer rewrite that allows users to increase or - decrease the badness score linearly. This interface will replace - /proc/<pid>/oom_adj. - - A warning will be emitted to the kernel log if an application uses this - deprecated interface. After it is printed once, future warnings will be - suppressed until the kernel is rebooted. diff --git a/Documentation/cgroups/memory.txt b/Documentation/cgroups/memory.txt index 4372e6b8a353..c07f7b4fb88d 100644 --- a/Documentation/cgroups/memory.txt +++ b/Documentation/cgroups/memory.txt @@ -18,16 +18,16 @@ from the rest of the system. The article on LWN [12] mentions some probable uses of the memory controller. The memory controller can be used to a. Isolate an application or a group of applications - Memory hungry applications can be isolated and limited to a smaller + Memory-hungry applications can be isolated and limited to a smaller amount of memory. -b. Create a cgroup with limited amount of memory, this can be used +b. Create a cgroup with a limited amount of memory; this can be used as a good alternative to booting with mem=XXXX. c. Virtualization solutions can control the amount of memory they want to assign to a virtual machine instance. d. A CD/DVD burner could control the amount of memory used by the rest of the system to ensure that burning does not fail due to lack of available memory. -e. There are several other use cases, find one or use the controller just +e. There are several other use cases; find one or use the controller just for fun (to learn and hack on the VM subsystem). Current Status: linux-2.6.34-mmotm(development version of 2010/April) @@ -38,12 +38,12 @@ Features: - optionally, memory+swap usage can be accounted and limited. - hierarchical accounting - soft limit - - moving(recharging) account at moving a task is selectable. + - moving (recharging) account at moving a task is selectable. - usage threshold notifier - oom-killer disable knob and oom-notifier - Root cgroup has no limit controls. - Kernel memory support is work in progress, and the current version provides + Kernel memory support is a work in progress, and the current version provides basically functionality. (See Section 2.7) Brief summary of control files. @@ -144,9 +144,9 @@ Figure 1 shows the important aspects of the controller 3. Each page has a pointer to the page_cgroup, which in turn knows the cgroup it belongs to -The accounting is done as follows: mem_cgroup_charge() is invoked to setup +The accounting is done as follows: mem_cgroup_charge() is invoked to set up the necessary data structures and check if the cgroup that is being charged -is over its limit. If it is then reclaim is invoked on the cgroup. +is over its limit. If it is, then reclaim is invoked on the cgroup. More details can be found in the reclaim section of this document. If everything goes well, a page meta-data-structure called page_cgroup is updated. page_cgroup has its own LRU on cgroup. @@ -163,13 +163,13 @@ for earlier. A file page will be accounted for as Page Cache when it's inserted into inode (radix-tree). While it's mapped into the page tables of processes, duplicate accounting is carefully avoided. -A RSS page is unaccounted when it's fully unmapped. A PageCache page is +An RSS page is unaccounted when it's fully unmapped. A PageCache page is unaccounted when it's removed from radix-tree. Even if RSS pages are fully unmapped (by kswapd), they may exist as SwapCache in the system until they -are really freed. Such SwapCaches also also accounted. +are really freed. Such SwapCaches are also accounted. A swapped-in page is not accounted until it's mapped. -Note: The kernel does swapin-readahead and read multiple swaps at once. +Note: The kernel does swapin-readahead and reads multiple swaps at once. This means swapped-in pages may contain pages for other tasks than a task causing page fault. So, we avoid accounting at swap-in I/O. @@ -209,7 +209,7 @@ memsw.limit_in_bytes. Example: Assume a system with 4G of swap. A task which allocates 6G of memory (by mistake) under 2G memory limitation will use all swap. In this case, setting memsw.limit_in_bytes=3G will prevent bad use of swap. -By using memsw limit, you can avoid system OOM which can be caused by swap +By using the memsw limit, you can avoid system OOM which can be caused by swap shortage. * why 'memory+swap' rather than swap. @@ -217,7 +217,7 @@ The global LRU(kswapd) can swap out arbitrary pages. Swap-out means to move account from memory to swap...there is no change in usage of memory+swap. In other words, when we want to limit the usage of swap without affecting global LRU, memory+swap limit is better than just limiting swap from -OS point of view. +an OS point of view. * What happens when a cgroup hits memory.memsw.limit_in_bytes When a cgroup hits memory.memsw.limit_in_bytes, it's useless to do swap-out @@ -236,7 +236,7 @@ an OOM routine is invoked to select and kill the bulkiest task in the cgroup. (See 10. OOM Control below.) The reclaim algorithm has not been modified for cgroups, except that -pages that are selected for reclaiming come from the per cgroup LRU +pages that are selected for reclaiming come from the per-cgroup LRU list. NOTE: Reclaim does not work for the root cgroup, since we cannot set any @@ -316,7 +316,7 @@ We can check the usage: # cat /sys/fs/cgroup/memory/0/memory.usage_in_bytes 1216512 -A successful write to this file does not guarantee a successful set of +A successful write to this file does not guarantee a successful setting of this limit to the value written into the file. This can be due to a number of factors, such as rounding up to page boundaries or the total availability of memory on the system. The user is required to re-read @@ -350,7 +350,7 @@ Trying usual test under memory controller is always helpful. 4.1 Troubleshooting Sometimes a user might find that the application under a cgroup is -terminated by OOM killer. There are several causes for this: +terminated by the OOM killer. There are several causes for this: 1. The cgroup limit is too low (just too low to do anything useful) 2. The user is using anonymous memory and swap is turned off or too low @@ -358,7 +358,7 @@ terminated by OOM killer. There are several causes for this: A sync followed by echo 1 > /proc/sys/vm/drop_caches will help get rid of some of the pages cached in the cgroup (page cache pages). -To know what happens, disable OOM_Kill by 10. OOM Control(see below) and +To know what happens, disabling OOM_Kill as per "10. OOM Control" (below) and seeing what happens will be helpful. 4.2 Task migration @@ -399,10 +399,10 @@ About use_hierarchy, see Section 6. Almost all pages tracked by this memory cgroup will be unmapped and freed. Some pages cannot be freed because they are locked or in-use. Such pages are - moved to parent(if use_hierarchy==1) or root (if use_hierarchy==0) and this + moved to parent (if use_hierarchy==1) or root (if use_hierarchy==0) and this cgroup will be empty. - Typical use case of this interface is that calling this before rmdir(). + The typical use case for this interface is before calling rmdir(). Because rmdir() moves all pages to parent, some out-of-use page caches can be moved to the parent. If you want to avoid that, force_empty will be useful. @@ -486,7 +486,7 @@ You can reset failcnt by writing 0 to failcnt file. For efficiency, as other kernel components, memory cgroup uses some optimization to avoid unnecessary cacheline false sharing. usage_in_bytes is affected by the -method and doesn't show 'exact' value of memory(and swap) usage, it's an fuzz +method and doesn't show 'exact' value of memory (and swap) usage, it's a fuzz value for efficient access. (Of course, when necessary, it's synchronized.) If you want to know more exact memory usage, you should use RSS+CACHE(+SWAP) value in memory.stat(see 5.2). @@ -496,8 +496,8 @@ value in memory.stat(see 5.2). This is similar to numa_maps but operates on a per-memcg basis. This is useful for providing visibility into the numa locality information within an memcg since the pages are allowed to be allocated from any physical -node. One of the usecases is evaluating application performance by -combining this information with the application's cpu allocation. +node. One of the use cases is evaluating application performance by +combining this information with the application's CPU allocation. We export "total", "file", "anon" and "unevictable" pages per-node for each memcg. The ouput format of memory.numa_stat is: @@ -561,10 +561,10 @@ are pushed back to their soft limits. If the soft limit of each control group is very high, they are pushed back as much as possible to make sure that one control group does not starve the others of memory. -Please note that soft limits is a best effort feature, it comes with +Please note that soft limits is a best-effort feature; it comes with no guarantees, but it does its best to make sure that when memory is heavily contended for, memory is allocated based on the soft limit -hints/setup. Currently soft limit based reclaim is setup such that +hints/setup. Currently soft limit based reclaim is set up such that it gets invoked from balance_pgdat (kswapd). 7.1 Interface @@ -592,7 +592,7 @@ page tables. 8.1 Interface -This feature is disabled by default. It can be enabled(and disabled again) by +This feature is disabled by default. It can be enabledi (and disabled again) by writing to memory.move_charge_at_immigrate of the destination cgroup. If you want to enable it: @@ -601,8 +601,8 @@ If you want to enable it: Note: Each bits of move_charge_at_immigrate has its own meaning about what type of charges should be moved. See 8.2 for details. -Note: Charges are moved only when you move mm->owner, IOW, a leader of a thread - group. +Note: Charges are moved only when you move mm->owner, in other words, + a leader of a thread group. Note: If we cannot find enough space for the task in the destination cgroup, we try to make space by reclaiming memory. Task migration may fail if we cannot make enough space. @@ -612,25 +612,25 @@ And if you want disable it again: # echo 0 > memory.move_charge_at_immigrate -8.2 Type of charges which can be move +8.2 Type of charges which can be moved -Each bits of move_charge_at_immigrate has its own meaning about what type of -charges should be moved. But in any cases, it must be noted that an account of -a page or a swap can be moved only when it is charged to the task's current(old) -memory cgroup. +Each bit in move_charge_at_immigrate has its own meaning about what type of +charges should be moved. But in any case, it must be noted that an account of +a page or a swap can be moved only when it is charged to the task's current +(old) memory cgroup. bit | what type of charges would be moved ? -----+------------------------------------------------------------------------ - 0 | A charge of an anonymous page(or swap of it) used by the target task. - | You must enable Swap Extension(see 2.4) to enable move of swap charges. + 0 | A charge of an anonymous page (or swap of it) used by the target task. + | You must enable Swap Extension (see 2.4) to enable move of swap charges. -----+------------------------------------------------------------------------ - 1 | A charge of file pages(normal file, tmpfs file(e.g. ipc shared memory) + 1 | A charge of file pages (normal file, tmpfs file (e.g. ipc shared memory) | and swaps of tmpfs file) mmapped by the target task. Unlike the case of - | anonymous pages, file pages(and swaps) in the range mmapped by the task + | anonymous pages, file pages (and swaps) in the range mmapped by the task | will be moved even if the task hasn't done page fault, i.e. they might | not be the task's "RSS", but other task's "RSS" that maps the same file. - | And mapcount of the page is ignored(the page can be moved even if - | page_mapcount(page) > 1). You must enable Swap Extension(see 2.4) to + | And mapcount of the page is ignored (the page can be moved even if + | page_mapcount(page) > 1). You must enable Swap Extension (see 2.4) to | enable move of swap charges. 8.3 TODO @@ -640,11 +640,11 @@ memory cgroup. 9. Memory thresholds -Memory cgroup implements memory thresholds using cgroups notification +Memory cgroup implements memory thresholds using the cgroups notification API (see cgroups.txt). It allows to register multiple memory and memsw thresholds and gets notifications when it crosses. -To register a threshold application need: +To register a threshold, an application must: - create an eventfd using eventfd(2); - open memory.usage_in_bytes or memory.memsw.usage_in_bytes; - write string like "<event_fd> <fd of memory.usage_in_bytes> <threshold>" to @@ -659,24 +659,24 @@ It's applicable for root and non-root cgroup. memory.oom_control file is for OOM notification and other controls. -Memory cgroup implements OOM notifier using cgroup notification +Memory cgroup implements OOM notifier using the cgroup notification API (See cgroups.txt). It allows to register multiple OOM notification delivery and gets notification when OOM happens. -To register a notifier, application need: +To register a notifier, an application must: - create an eventfd using eventfd(2) - open memory.oom_control file - write string like "<event_fd> <fd of memory.oom_control>" to cgroup.event_control -Application will be notified through eventfd when OOM happens. -OOM notification doesn't work for root cgroup. +The application will be notified through eventfd when OOM happens. +OOM notification doesn't work for the root cgroup. -You can disable OOM-killer by writing "1" to memory.oom_control file, as: +You can disable the OOM-killer by writing "1" to memory.oom_control file, as: #echo 1 > memory.oom_control -This operation is only allowed to the top cgroup of sub-hierarchy. +This operation is only allowed to the top cgroup of a sub-hierarchy. If OOM-killer is disabled, tasks under cgroup will hang/sleep in memory cgroup's OOM-waitqueue when they request accountable memory. diff --git a/Documentation/filesystems/proc.txt b/Documentation/filesystems/proc.txt index fb0a6aeb936c..a1793d670cd0 100644 --- a/Documentation/filesystems/proc.txt +++ b/Documentation/filesystems/proc.txt @@ -33,7 +33,7 @@ Table of Contents 2 Modifying System Parameters 3 Per-Process Parameters - 3.1 /proc/<pid>/oom_adj & /proc/<pid>/oom_score_adj - Adjust the oom-killer + 3.1 /proc/<pid>/oom_score_adj - Adjust the oom-killer score 3.2 /proc/<pid>/oom_score - Display current oom-killer score 3.3 /proc/<pid>/io - Display the IO accounting fields @@ -1320,10 +1320,10 @@ of the kernel. CHAPTER 3: PER-PROCESS PARAMETERS ------------------------------------------------------------------------------ -3.1 /proc/<pid>/oom_adj & /proc/<pid>/oom_score_adj- Adjust the oom-killer score +3.1 /proc/<pid>/oom_score_adj- Adjust the oom-killer score -------------------------------------------------------------------------------- -These file can be used to adjust the badness heuristic used to select which +This file can be used to adjust the badness heuristic used to select which process gets killed in out of memory conditions. The badness heuristic assigns a value to each candidate task ranging from 0 @@ -1361,22 +1361,10 @@ same system, cpuset, mempolicy, or memory controller resources to use at least equivalent to discounting 50% of the task's allowed memory from being considered as scoring against the task. -For backwards compatibility with previous kernels, /proc/<pid>/oom_adj may also -be used to tune the badness score. Its acceptable values range from -16 -(OOM_ADJUST_MIN) to +15 (OOM_ADJUST_MAX) and a special value of -17 -(OOM_DISABLE) to disable oom killing entirely for that task. Its value is -scaled linearly with /proc/<pid>/oom_score_adj. - -Writing to /proc/<pid>/oom_score_adj or /proc/<pid>/oom_adj will change the -other with its scaled value. - The value of /proc/<pid>/oom_score_adj may be reduced no lower than the last value set by a CAP_SYS_RESOURCE process. To reduce the value any lower requires CAP_SYS_RESOURCE. -NOTICE: /proc/<pid>/oom_adj is deprecated and will be removed, please see -Documentation/feature-removal-schedule.txt. - Caveat: when a parent task is selected, the oom killer will sacrifice any first generation children with separate address spaces instead, if possible. This avoids servers and important system daemons from being killed and loses the @@ -1387,9 +1375,7 @@ minimal amount of work. ------------------------------------------------------------- This file can be used to check the current score used by the oom-killer is for -any given <pid>. Use it together with /proc/<pid>/oom_adj to tune which -process should be killed in an out-of-memory situation. - +any given <pid>. 3.3 /proc/<pid>/io - Display the IO accounting fields ------------------------------------------------------- diff --git a/Documentation/memory.txt b/Documentation/memory.txt deleted file mode 100644 index 802efe58647c..000000000000 --- a/Documentation/memory.txt +++ /dev/null @@ -1,33 +0,0 @@ -There are several classic problems related to memory on Linux -systems. - - 1) There are some motherboards that will not cache above - a certain quantity of memory. If you have one of these - motherboards, your system will be SLOWER, not faster - as you add more memory. Consider exchanging your - motherboard. - -All of these problems can be addressed with the "mem=XXXM" boot option -(where XXX is the size of RAM to use in megabytes). -It can also tell Linux to use less memory than is actually installed. -If you use "mem=" on a machine with PCI, consider using "memmap=" to avoid -physical address space collisions. - -See the documentation of your boot loader (LILO, grub, loadlin, etc.) about -how to pass options to the kernel. - -There are other memory problems which Linux cannot deal with. Random -corruption of memory is usually a sign of serious hardware trouble. -Try: - - * Reducing memory settings in the BIOS to the most conservative - timings. - - * Adding a cooling fan. - - * Not overclocking your CPU. - - * Having the memory tested in a memory tester or exchanged - with the vendor. Consider testing it with memtest86 yourself. - - * Exchanging your CPU, cache, or motherboard for one that works. diff --git a/Documentation/prio_tree.txt b/Documentation/prio_tree.txt deleted file mode 100644 index 3aa68f9a117b..000000000000 --- a/Documentation/prio_tree.txt +++ /dev/null @@ -1,107 +0,0 @@ -The prio_tree.c code indexes vmas using 3 different indexes: - * heap_index = vm_pgoff + vm_size_in_pages : end_vm_pgoff - * radix_index = vm_pgoff : start_vm_pgoff - * size_index = vm_size_in_pages - -A regular radix-priority-search-tree indexes vmas using only heap_index and -radix_index. The conditions for indexing are: - * ->heap_index >= ->left->heap_index && - ->heap_index >= ->right->heap_index - * if (->heap_index == ->left->heap_index) - then ->radix_index < ->left->radix_index; - * if (->heap_index == ->right->heap_index) - then ->radix_index < ->right->radix_index; - * nodes are hashed to left or right subtree using radix_index - similar to a pure binary radix tree. - -A regular radix-priority-search-tree helps to store and query -intervals (vmas). However, a regular radix-priority-search-tree is only -suitable for storing vmas with different radix indices (vm_pgoff). - -Therefore, the prio_tree.c extends the regular radix-priority-search-tree -to handle many vmas with the same vm_pgoff. Such vmas are handled in -2 different ways: 1) All vmas with the same radix _and_ heap indices are -linked using vm_set.list, 2) if there are many vmas with the same radix -index, but different heap indices and if the regular radix-priority-search -tree cannot index them all, we build an overflow-sub-tree that indexes such -vmas using heap and size indices instead of heap and radix indices. For -example, in the figure below some vmas with vm_pgoff = 0 (zero) are -indexed by regular radix-priority-search-tree whereas others are pushed -into an overflow-subtree. Note that all vmas in an overflow-sub-tree have -the same vm_pgoff (radix_index) and if necessary we build different -overflow-sub-trees to handle each possible radix_index. For example, -in figure we have 3 overflow-sub-trees corresponding to radix indices -0, 2, and 4. - -In the final tree the first few (prio_tree_root->index_bits) levels -are indexed using heap and radix indices whereas the overflow-sub-trees below -those levels (i.e. levels prio_tree_root->index_bits + 1 and higher) are -indexed using heap and size indices. In overflow-sub-trees the size_index -is used for hashing the nodes to appropriate places. - -Now, an example prio_tree: - - vmas are represented [radix_index, size_index, heap_index] - i.e., [start_vm_pgoff, vm_size_in_pages, end_vm_pgoff] - -level prio_tree_root->index_bits = 3 ------ - _ - 0 [0,7,7] | - / \ | - ------------------ ------------ | Regular - / \ | radix priority - 1 [1,6,7] [4,3,7] | search tree - / \ / \ | - ------- ----- ------ ----- | heap-and-radix - / \ / \ | indexed - 2 [0,6,6] [2,5,7] [5,2,7] [6,1,7] | - / \ / \ / \ / \ | - 3 [0,5,5] [1,5,6] [2,4,6] [3,4,7] [4,2,6] [5,1,6] [6,0,6] [7,0,7] | - / / / _ - / / / _ - 4 [0,4,4] [2,3,5] [4,1,5] | - / / / | - 5 [0,3,3] [2,2,4] [4,0,4] | Overflow-sub-trees - / / | - 6 [0,2,2] [2,1,3] | heap-and-size - / / | indexed - 7 [0,1,1] [2,0,2] | - / | - 8 [0,0,0] | - _ - -Note that we use prio_tree_root->index_bits to optimize the height -of the heap-and-radix indexed tree. Since prio_tree_root->index_bits is -set according to the maximum end_vm_pgoff mapped, we are sure that all -bits (in vm_pgoff) above prio_tree_root->index_bits are 0 (zero). Therefore, -we only use the first prio_tree_root->index_bits as radix_index. -Whenever index_bits is increased in prio_tree_expand, we shuffle the tree -to make sure that the first prio_tree_root->index_bits levels of the tree -is indexed properly using heap and radix indices. - -We do not optimize the height of overflow-sub-trees using index_bits. -The reason is: there can be many such overflow-sub-trees and all of -them have to be suffled whenever the index_bits increases. This may involve -walking the whole prio_tree in prio_tree_insert->prio_tree_expand code -path which is not desirable. Hence, we do not optimize the height of the -heap-and-size indexed overflow-sub-trees using prio_tree->index_bits. -Instead the overflow sub-trees are indexed using full BITS_PER_LONG bits -of size_index. This may lead to skewed sub-trees because most of the -higher significant bits of the size_index are likely to be 0 (zero). In -the example above, all 3 overflow-sub-trees are skewed. This may marginally -affect the performance. However, processes rarely map many vmas with the -same start_vm_pgoff but different end_vm_pgoffs. Therefore, we normally -do not require overflow-sub-trees to index all vmas. - -From the above discussion it is clear that the maximum height of -a prio_tree can be prio_tree_root->index_bits + BITS_PER_LONG. -However, in most of the common cases we do not need overflow-sub-trees, -so the tree height in the common cases will be prio_tree_root->index_bits. - -It is fair to mention here that the prio_tree_root->index_bits -is increased on demand, however, the index_bits is not decreased when -vmas are removed from the prio_tree. That's tricky to do. Hence, it's -left as a home work problem. - - diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt index 8d32d85a5234..61b6c48871a0 100644 --- a/Documentation/rbtree.txt +++ b/Documentation/rbtree.txt @@ -193,24 +193,55 @@ Example: Support for Augmented rbtrees ----------------------------- -Augmented rbtree is an rbtree with "some" additional data stored in each node. -This data can be used to augment some new functionality to rbtree. -Augmented rbtree is an optional feature built on top of basic rbtree -infrastructure. An rbtree user who wants this feature will have to call the -augmentation functions with the user provided augmentation callback -when inserting and erasing nodes. - -On insertion, the user must call rb_augment_insert() once the new node is in -place. This will cause the augmentation function callback to be called for -each node between the new node and the root which has been affected by the -insertion. - -When erasing a node, the user must call rb_augment_erase_begin() first to -retrieve the deepest node on the rebalance path. Then, after erasing the -original node, the user must call rb_augment_erase_end() with the deepest -node found earlier. This will cause the augmentation function to be called -for each affected node between the deepest node and the root. - +Augmented rbtree is an rbtree with "some" additional data stored in +each node, where the additional data for node N must be a function of +the contents of all nodes in the subtree rooted at N. This data can +be used to augment some new functionality to rbtree. Augmented rbtree +is an optional feature built on top of basic rbtree infrastructure. +An rbtree user who wants this feature will have to call the augmentation +functions with the user provided augmentation callback when inserting +and erasing nodes. + +C files implementing augmented rbtree manipulation must include +<linux/rbtree_augmented.h> instead of <linus/rbtree.h>. Note that +linux/rbtree_augmented.h exposes some rbtree implementations details +you are not expected to rely on; please stick to the documented APIs +there and do not include <linux/rbtree_augmented.h> from header files +either so as to minimize chances of your users accidentally relying on +such implementation details. + +On insertion, the user must update the augmented information on the path +leading to the inserted node, then call rb_link_node() as usual and +rb_augment_inserted() instead of the usual rb_insert_color() call. +If rb_augment_inserted() rebalances the rbtree, it will callback into +a user provided function to update the augmented information on the +affected subtrees. + +When erasing a node, the user must call rb_erase_augmented() instead of +rb_erase(). rb_erase_augmented() calls back into user provided functions +to updated the augmented information on affected subtrees. + +In both cases, the callbacks are provided through struct rb_augment_callbacks. +3 callbacks must be defined: + +- A propagation callback, which updates the augmented value for a given + node and its ancestors, up to a given stop point (or NULL to update + all the way to the root). + +- A copy callback, which copies the augmented value for a given subtree + to a newly assigned subtree root. + +- A tree rotation callback, which copies the augmented value for a given + subtree to a newly assigned subtree root AND recomputes the augmented + information for the former subtree root. + +The compiled code for rb_erase_augmented() may inline the propagation and +copy callbacks, which results in a large function, so each augmented rbtree +user should have a single rb_erase_augmented() call site in order to limit +compiled code size. + + +Sample usage: Interval tree is an example of augmented rb tree. Reference - "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. @@ -230,26 +261,132 @@ and its immediate children. And this will be used in O(log n) lookup for lowest match (lowest start address among all possible matches) with something like: -find_lowest_match(lo, hi, node) +struct interval_tree_node * +interval_tree_first_match(struct rb_root *root, + unsigned long start, unsigned long last) { - lowest_match = NULL; - while (node) { - if (max_hi(node->left) > lo) { - // Lowest overlap if any must be on left side - node = node->left; - } else if (overlap(lo, hi, node)) { - lowest_match = node; - break; - } else if (lo > node->lo) { - // Lowest overlap if any must be on right side - node = node->right; - } else { - break; + struct interval_tree_node *node; + + if (!root->rb_node) + return NULL; + node = rb_entry(root->rb_node, struct interval_tree_node, rb); + + while (true) { + if (node->rb.rb_left) { + struct interval_tree_node *left = + rb_entry(node->rb.rb_left, + struct interval_tree_node, rb); + if (left->__subtree_last >= start) { + /* + * Some nodes in left subtree satisfy Cond2. + * Iterate to find the leftmost such node N. + * If it also satisfies Cond1, that's the match + * we are looking for. Otherwise, there is no + * matching interval as nodes to the right of N + * can't satisfy Cond1 either. + */ + node = left; + continue; + } } + if (node->start <= last) { /* Cond1 */ + if (node->last >= start) /* Cond2 */ + return node; /* node is leftmost match */ + if (node->rb.rb_right) { + node = rb_entry(node->rb.rb_right, + struct interval_tree_node, rb); + if (node->__subtree_last >= start) + continue; + } + } + return NULL; /* No match */ + } +} + +Insertion/removal are defined using the following augmented callbacks: + +static inline unsigned long +compute_subtree_last(struct interval_tree_node *node) +{ + unsigned long max = node->last, subtree_last; + if (node->rb.rb_left) { + subtree_last = rb_entry(node->rb.rb_left, + struct interval_tree_node, rb)->__subtree_last; + if (max < subtree_last) + max = subtree_last; + } + if (node->rb.rb_right) { + subtree_last = rb_entry(node->rb.rb_right, + struct interval_tree_node, rb)->__subtree_last; + if (max < subtree_last) + max = subtree_last; + } + return max; +} + +static void augment_propagate(struct rb_node *rb, struct rb_node *stop) +{ + while (rb != stop) { + struct interval_tree_node *node = + rb_entry(rb, struct interval_tree_node, rb); + unsigned long subtree_last = compute_subtree_last(node); + if (node->__subtree_last == subtree_last) + break; + node->__subtree_last = subtree_last; + rb = rb_parent(&node->rb); } - return lowest_match; } -Finding exact match will be to first find lowest match and then to follow -successor nodes looking for exact match, until the start of a node is beyond -the hi value we are looking for. +static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct interval_tree_node *old = + rb_entry(rb_old, struct interval_tree_node, rb); + struct interval_tree_node *new = + rb_entry(rb_new, struct interval_tree_node, rb); + + new->__subtree_last = old->__subtree_last; +} + +static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) +{ + struct interval_tree_node *old = + rb_entry(rb_old, struct interval_tree_node, rb); + struct interval_tree_node *new = + rb_entry(rb_new, struct interval_tree_node, rb); + + new->__subtree_last = old->__subtree_last; + old->__subtree_last = compute_subtree_last(old); +} + +static const struct rb_augment_callbacks augment_callbacks = { + augment_propagate, augment_copy, augment_rotate +}; + +void interval_tree_insert(struct interval_tree_node *node, + struct rb_root *root) +{ + struct rb_node **link = &root->rb_node, *rb_parent = NULL; + unsigned long start = node->start, last = node->last; + struct interval_tree_node *parent; + + while (*link) { + rb_parent = *link; + parent = rb_entry(rb_parent, struct interval_tree_node, rb); + if (parent->__subtree_last < last) + parent->__subtree_last = last; + if (start < parent->start) + link = &parent->rb.rb_left; + else + link = &parent->rb.rb_right; + } + + node->__subtree_last = last; + rb_link_node(&node->rb, rb_parent, link); + rb_insert_augmented(&node->rb, root, &augment_callbacks); +} + +void interval_tree_remove(struct interval_tree_node *node, + struct rb_root *root) +{ + rb_erase_augmented(&node->rb, root, &augment_callbacks); +} diff --git a/Documentation/vm/unevictable-lru.txt b/Documentation/vm/unevictable-lru.txt index fa206cccf89f..a68db7692ee8 100644 --- a/Documentation/vm/unevictable-lru.txt +++ b/Documentation/vm/unevictable-lru.txt @@ -197,12 +197,8 @@ the pages are also "rescued" from the unevictable list in the process of freeing them. page_evictable() also checks for mlocked pages by testing an additional page -flag, PG_mlocked (as wrapped by PageMlocked()). If the page is NOT mlocked, -and a non-NULL VMA is supplied, page_evictable() will check whether the VMA is -VM_LOCKED via is_mlocked_vma(). is_mlocked_vma() will SetPageMlocked() and -update the appropriate statistics if the vma is VM_LOCKED. This method allows -efficient "culling" of pages in the fault path that are being faulted in to -VM_LOCKED VMAs. +flag, PG_mlocked (as wrapped by PageMlocked()), which is set when a page is +faulted into a VM_LOCKED vma, or found in a vma being VM_LOCKED. VMSCAN'S HANDLING OF UNEVICTABLE PAGES @@ -371,8 +367,8 @@ mlock_fixup() filters several classes of "special" VMAs: mlock_fixup() will call make_pages_present() in the hugetlbfs VMA range to allocate the huge pages and populate the ptes. -3) VMAs with VM_DONTEXPAND or VM_RESERVED are generally userspace mappings of - kernel pages, such as the VDSO page, relay channel pages, etc. These pages +3) VMAs with VM_DONTEXPAND are generally userspace mappings of kernel pages, + such as the VDSO page, relay channel pages, etc. These pages are inherently unevictable and are not managed on the LRU lists. mlock_fixup() treats these VMAs the same as hugetlbfs VMAs. It calls make_pages_present() to populate the ptes. @@ -651,7 +647,7 @@ PAGE RECLAIM IN shrink_*_list() ------------------------------- shrink_active_list() culls any obviously unevictable pages - i.e. -!page_evictable(page, NULL) - diverting these to the unevictable list. +!page_evictable(page) - diverting these to the unevictable list. However, shrink_active_list() only sees unevictable pages that made it onto the active/inactive lru lists. Note that these pages do not have PageUnevictable set - otherwise they would be on the unevictable list and shrink_active_list |