6,534
edits
Changes
m
kernel internals
{{UBC toc}}
This article describes how fractions accounting algorithm used in [[User pagesaccounting|privvmpages accounting]] works.
== Introduction ==
The goal of this the algorithm is to calculate the {{H:title|Resident Set Size|RSS}} for each beancounter. This is done by establishing so called many-to-many relation between physical pages and beancounters.
{{Note|the term “page is mapped to beancounter” used in this article means “there exists an <code>mm_struct</code>, the pages is mapped to and this <code>mm_struct</code> belongs to this beancounter”.}}
== Math model ==
In a C-like notation this would look like this:
<presource lang="C">
pb = lookup_pb(page, UB);
if (pb != NULL) {
list_add_tail(pb, page.pb_list);
page.pb_list.first = head.next;
</presource>
Shift increment essentially means <em>take “take one half of the currently held fraction and give it to the newbie</em>newbie”.
=== Removing an existing reference ===
; The last reference is removed
: In this case the PB that ties page and UB must give its shift back to other PBs and be removed from list. This “giving shift back” procedure may involve three PBs and it is better described by the code example below.
<presource lang="C">
pb = lookup_pb(page, UB);
pb.refcount--;
page.pb_list.first = tail
}
</presource>
Decrementing the shifts like this means “take the fraction held by the PB going out and give it to another one; if the fraction held is too large — share it between two PBs”.
{{Note|cases when <code>page.pb_list</code> is becoming empty on adding a reference, or becoming empty on removing references are skipped to simplify the code examples.}}
[[Category: Kernel internals]]