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 ==
As described in the [[User pagesaccounting|article about user pages]], this algorithm calculates the “fractions” of pages that are mapped to beancounter, in a tricky manner.
Naturally, if a page is shared between <math>N</math> beancounters, each UB must get <math>\frac {1} {N}</math>-th part of it. This approach would be the most precise, but also the worst, as adding a page to a new beancounter would require an update on all the beancounters between which the page is already shared.
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]]