Editing RSS fractions accounting

{{UBC toc}}

This article describes how fractions accounting algorithm used in [[User pages accounting|privvmpages accounting]] works.

== Introduction ==
The goal of 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 pages|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.

Instead of doing that, UBC charges parts of page equal to <math>2^{-shift(page, UB)}\,</math>, where <math>shift(page, UB)</math> is calculated so that

<center>
<math>
\sum _{UB} 2^{-shift(page, UB)} = 1 \,
</math>
</center>

Such fractions allow to build an O(1) algorithm, as described below.

== Algorithm description ==
The complete description of the algorithm consists of describing an objects used in it and two procedures — adding a page to beancounter and removing it.

=== Objects ===
The following objects are used in this algorithm:
; Page beancounter (PB)
: A tie between page and beancounter. This is the PB which holds the value of <math>shift(page, UB)</math>;
; Page
: A physical page. In Linux kernel each physical page is represented with <code>struct page</code>. What is important is that each page has its associated circular list of PBs and the head PB in this list has a special meaning;
; Beancounter
: A known object. To work with this algorithm beancounter has an auxiliary resource called “held pages”.

Page beancounters are stored in a large hash to hasten the lookup of a needed PB.

The next two sections describe the procedures of adding and removing of a reference.

=== Adding a new reference ===
When page is added to UB, one of the following scenarios is possible:
; There's already a tie between the page an the UB
: In this case just increment the reference count of the tie;
; A new reference must be created
: In this case the new PB is created. <math>shift</math>-s are recalculated for new PB and the page list head only so that one half of the page's fractions held by the head is moved to the new PB. After this new PB is added to the tail of the list and the second PB in list becomes the head.

In a C-like notation this would look like this:
<source lang="C">
pb = lookup_pb(page, UB);
if (pb != NULL) {
        pb.refcount++;
        return;
}       

pb = alloc_pb();
pb.refcount = 1;

head = page.pb_list.first;

head.shift++;
pb.shift = head.shift;
pb.tie = tie(page, UB);

list_add_tail(pb, page.pb_list);
page.pb_list.first = head.next;
</source>

Shift increment essentially means “take one half of the currently held fraction and give it to the newbie”.

=== Removing an existing reference ===
When the existing reference is removed, the following scenarios are possible:
; This page was referenced to BC more than once (e.g. by two tasks)
: In this case reference counter is decremented;
; 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.
<source lang="C">
pb = lookup_pb(page, UB);
pb.refcount--;
if (pb.refcount > 0)
        return;

list_del(pb);

tail = page.pb_list.last;
tail.shift--;
page.pb_list.first = tail;

if (pb.shift < tail.shift + 1) {
        tail = page.pb_list.last;
        tail.shift--;
        page.pb_list.first = tail
}
</source>

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]]