RSS fractions accounting

User Beancounters Definition /proc/user_beancounters /proc/bc/ General information Units of measurement VSwap Parameters description Primary parameters numproc, numtcpsock, numothersock, vmguarpages Secondary parameters kmemsize, tcpsndbuf, tcprcvbuf, othersockbuf, dgramrcvbuf, oomguarpages, privvmpages Auxiliary parameters lockedpages, shmpages, physpages, numfile, numflock, numpty, numsiginfo, dcachesize, numiptent, swappages Internals User pages accounting RSS fractions accounting On-demand accounting UBC consistency Consistency formulae System-wide configuration vzubc(8) Configuration examples Basic Derived Intermediate configurations Tables List of parameters Parameter properties Consistency Config examples

This article describes how fractions accounting algorithm used in privvmpages accounting works.

Introduction

The goal of the algorithm is to calculate the 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 mm_struct the pages is mapped to and this mm_struct belongs to this beancounter”.

Math model

As described in the 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 $N$ beancounters, each UB must get ${\frac {1}{N}}$-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 $2^{-shift(page,UB)}\,$, where $shift(page,UB)$ is calculated so that

$\sum _{UB}2^{-shift(page,UB)}=1\,$

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 $shift(page,UB)$;

Page

A physical page. In Linux kernel each physical page is represented with struct page. 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. $shift$-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:

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;

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.

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
}

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 page.pb_list is becoming empty on adding a reference, or becoming empty on removing references are skipped to simplify the code examples.