RSS fractions accounting - Revision history

Kir: kernel internals

2008-01-24T12:54:48Z

kernel internals

Kir: use source tags

2008-01-24T12:03:04Z

use source tags

Kir: /* Removing an existing reference */ use source tag

2008-01-24T12:01:13Z

‎Removing an existing reference: use source tag

Kir: unify style -- use “” not

2006-09-05T14:13:53Z

unify style -- use “” not 

← Older revision Revision as of 14:13, 5 September 2006
Line 67: Line 67:

</pre>

</pre>

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

=== Removing an existing reference ===

=== Removing an existing reference ===

Kir: punctuation fix in /* Introduction */

2006-09-05T14:09:48Z

punctuation fix in ‎Introduction

← Older revision Revision as of 14:09, 5 September 2006
Line 6: Line 6:

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.

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”.}}
+
{{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 ==

Kir: fixed link, slight rewording

2006-09-04T15:23:05Z

fixed link, slight rewording

← Older revision Revision as of 15:23, 4 September 2006
Line 1: Line 1:

{{UBC toc}}

{{UBC toc}}

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

== Introduction ==

== Introduction ==

−
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.
+
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”.}}

{{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”.}}

Kir: link changed in /* Math model */

2006-09-04T15:22:14Z

link changed in ‎Math model

← Older revision Revision as of 15:22, 4 September 2006
Line 9: Line 9:

== Math model ==

== 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.
+
As described in the [[User pages accounting|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.

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.

Kir: spelling fixes

2006-09-04T15:17:01Z

spelling fixes

← Older revision Revision as of 15:17, 4 September 2006
Line 1: Line 1:

{{UBC toc}}

{{UBC toc}}

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

== Introduction ==

== Introduction ==

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.

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|article about user pages]], this algorithm calculates the “fractions” of pages, that are mapped to beancounter, in a tricky manner.
+
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 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
+
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>

<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) ~~algorith~~, as described below.
+
Such fractions allow to build an O(1) algorithm, as described below.

== Algorithm description ==

== Algorithm description ==

Line 25: Line 27:

=== Objects ===

=== Objects ===

−
The following objects are used in this ~~algo~~:
+
The following objects are used in this algorithm:

−
; ~~page~~ beancounter (PB)
+
; 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>;
+
: A tie between page and beancounter. This is the PB which holds the value of <math>shift(page, UB)</math>;

−
; ~~page~~
+
; 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;
+
: 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~~
+
; Beancounter

−
: ~~this is a~~ known object. To work with this algorithm beancounter has an auxiliary resource called “held pages”.
+
: 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 needed PB.
+
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 ~~references~~.
+
The next two sections describe the procedures of adding and removing of a reference.

=== Adding a new reference ===

=== Adding a new reference ===

−
When page is added to UB one of the following scenarios is possible.
+
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 68: Line 70:

=== Removing an existing reference ===

=== Removing an existing reference ===

−
When the existing reference is removed the following scenarios are possible.
+
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 ~~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.
+
: 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.

<pre>

<pre>

pb = lookup_pb(page, UB);

pb = lookup_pb(page, UB);

Line 92: Line 94:

</pre>

</pre>

−
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~~.
+
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 empty on adding reference or ~~becomes~~ empty on removing references are skipped to simplify the code examples}}
+
{{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.}}

Xemul: Description of rss accounting algorithm

2006-09-04T14:56:49Z

Description of rss accounting algorithm

New page
{{UBC toc}}

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

== Introduction ==
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”}}

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

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

Such fractions allow to build an O(1) algorith, 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 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 needed PB.

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

=== 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:
<pre>
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;
</pre>

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 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.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
}
</pre>

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 empty on adding reference or becomes empty on removing references are skipped to simplify the code examples}}

← Older revision		Revision as of 12:54, 24 January 2008
Line 97:		Line 97:

	{{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.}}		{{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]]

@@ Line 47: / Line 47: @@
 In a C-like notation this would look like this:
-<pre>
+<source lang="C">
 pb = lookup_pb(page, UB);
 if (pb != NULL) {
@@ Line 65: / Line 65: @@
 list_add_tail(pb, page.pb_list);
 page.pb_list.first = head.next;
-</pre>
+</source>
 Shift increment essentially means “take one half of the currently held fraction and give it to the newbie”.

@@ Line 75: / Line 75: @@
 ; 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.
-<pre>
+<source lang="C">
 pb = lookup_pb(page, UB);
 pb.refcount--;
@@ Line 92: / Line 92: @@
          page.pb_list.first = tail
+}
-</pre>
+</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.}}

@@ Line 67: / Line 67: @@
 </pre>
-Shift increment essentially means <em>take one half of the currently held fraction and give it to the newbie</em>.
+Shift increment essentially means “take one half of the currently held fraction and give it to the newbie”.
 === Removing an existing reference ===

@@ Line 6: / Line 6: @@
 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”.}}
+{{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 ==

@@ Line 1: / Line 1: @@
 {{UBC toc}}
-This article describes how fractions accounting algorithm used in [[User pages|privvmpages accounting]] works.
+This article describes how fractions accounting algorithm used in [[User pages accounting|privvmpages accounting]] works.
 == Introduction ==
-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.
+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”.}}

@@ Line 9: / Line 9: @@
 == 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.
+As described in the [[User pages accounting|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.

@@ Line 1: / Line 1: @@
 {{UBC toc}}
-This article describes how fractions accounting algorithm used in [[User pages|privvmpages accouting]] works.
+This article describes how fractions accounting algorithm used in [[User pages|privvmpages accounting]] works.
 == Introduction ==
 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 ==
-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.
+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 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
+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.
 <center>
 <math>
-\sum _{UB} 2^{-shift(page, UB)} = 1
+\sum _{UB} 2^{-shift(page, UB)} = 1 \,
 </math>
 </center>
-Such fractions allow to build an O(1) algorith, as described below.
+Such fractions allow to build an O(1) algorithm, as described below.
 == Algorithm description ==
@@ Line 25: / Line 27: @@
 === Objects ===
-The following objects are used in this algo:
+The following objects are used in this algorithm:
-; page beancounter (PB)
+; 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>;
+: A tie between page and beancounter. This is the PB which holds the value of <math>shift(page, UB)</math>;
-; page
+; 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;
+: 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
+; Beancounter
-: this is a known object. To work with this algorithm beancounter has an auxiliary resource called “held pages”.
+: 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 needed PB.
+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 references.
+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.
+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;
@@ Line 68: / Line 70: @@
 === Removing an existing reference ===
-When the existing reference is removed the following scenarios are possible.
+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 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.
+: 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.
 <pre>
 pb = lookup_pb(page, UB);
@@ Line 92: / Line 94: @@
 </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>.
+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 empty on adding reference or becomes empty on removing references are skipped to simplify the code examples}}
+{{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.}}