Editing RSS fractions accounting
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 1: | Line 1: | ||
{{UBC toc}} | {{UBC toc}} | ||
| − | This article describes how fractions accounting algorithm used in [[User pages | + | This article describes how fractions accounting algorithm used in [[User pages|privvmpages accouting]] works. |
== Introduction == | == Introduction == | ||
| − | The goal of | + | The goal of this 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” | + | {{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 == | == Math model == | ||
| − | As described in the [[User pages | + | 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 | + | 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 is the most precise, but also the worst, as adding a page to a new beancounter would require update on all the beancounters between which the page is already shared. Instead of doing this UBC charges parts of page equal to <math>2^{-shift(page, UB)}</math>, where <math>shift(page, UB)</math> is calculated so that |
| − | |||
| − | Instead of doing | ||
<center> | <center> | ||
<math> | <math> | ||
| − | \sum _{UB} 2^{-shift(page, UB)} = 1 | + | \sum _{UB} 2^{-shift(page, UB)} = 1 |
</math> | </math> | ||
</center> | </center> | ||
| − | Such fractions allow to build an O(1) | + | Such fractions allow to build an O(1) algorith, as described below. |
== Algorithm description == | == Algorithm description == | ||
| Line 27: | Line 25: | ||
=== Objects === | === Objects === | ||
| − | The following objects are used in this | + | The following objects are used in this algo: |
| − | ; | + | ; page beancounter (PB) |
| − | : | + | : this is a tie between page and beancounter. This is the PB which holds the value of <math>shift(page, UB)</math>; |
| − | ; | + | ; page |
| − | : | + | : page is actually a physical page. In linux kernel each physical page is represented with <code>struct page</code>. What is importaint is that each page has associated circular list of PBs and the head PB in this list has a special meaning; |
| − | ; | + | ; beancounter |
| − | : | + | : this is 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 | + | Page beancounters are stored in a large hash to hasten the lookup of needed PB. |
| − | The next two sections describe the procedures of adding and removing of | + | The next two sections describe the procedures of adding and removing of references. |
=== Adding a new reference === | === Adding a new reference === | ||
| − | When page is added to UB | + | When page is added to UB one of the following scenarios is possible. |
; There's already a tie between the page an the UB | ; There's already a tie between the page an the UB | ||
: In this case just increment the reference count of the tie; | : In this case just increment the reference count of the tie; | ||
| Line 47: | Line 45: | ||
In a C-like notation this would look like this: | In a C-like notation this would look like this: | ||
| − | < | + | <pre> |
pb = lookup_pb(page, UB); | pb = lookup_pb(page, UB); | ||
if (pb != NULL) { | if (pb != NULL) { | ||
| Line 65: | Line 63: | ||
list_add_tail(pb, page.pb_list); | list_add_tail(pb, page.pb_list); | ||
page.pb_list.first = head.next; | page.pb_list.first = head.next; | ||
| − | </ | + | </pre> |
| − | Shift increment essentially means | + | Shift increment essentially means <em>take one half of the currently held fraction and give it to the newbie</em>. |
=== Removing an existing reference === | === Removing an existing reference === | ||
| − | When the existing reference is removed | + | 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) | ; This page was referenced to BC more than once (e.g. by two tasks) | ||
: In this case reference counter is decremented; | : In this case reference counter is decremented; | ||
; The last reference is removed | ; The last reference is removed | ||
| − | : In this case the PB that ties page and UB must give | + | : In this case the PB that ties page and UB must give it's shift back to other PBs and be removed from list. This “giving shift back” procedure may involve three PBs and it is better described in the code example below. |
| − | < | + | <pre> |
pb = lookup_pb(page, UB); | pb = lookup_pb(page, UB); | ||
pb.refcount--; | pb.refcount--; | ||
| Line 92: | Line 90: | ||
page.pb_list.first = tail | page.pb_list.first = tail | ||
} | } | ||
| − | </ | + | </pre> |
| − | |||
| − | |||
| − | + | Decrementing the shifts like this means <em>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</em>. | |
| − | + | {{Note|cases when <code>page.pb_list</code> is empty on adding reference or becomes empty on removing references are skipped to simplify the code examples}} | |
