Documentation/ckrm/mem_rc.design

   1 0. Lifecycle of a LRU Page:
   2 ----------------------------
   3 These are the events in a page's lifecycle:
   4    - allocation of the page
   5      there are multiple high level page alloc functions; __alloc_pages()
   6          is the lowest level function that does the real allocation.
   7    - get into LRU list (active list or inactive list)
   8    - get out of LRU list
   9    - freeing the page
  10      there are multiple high level page free functions; free_pages_bulk()
  11          is the lowest level function that does the real free.
  12
  13 When the memory subsystem runs low on LRU pages, pages are reclaimed by
  14     - moving pages from active list to inactive list (refill_inactive_zone())
  15     - freeing pages from the inactive list (shrink_zone)
  16 depending on the recent usage of the page(approximately).
  17
  18 In the process of the life cycle a page can move from the lru list to swap
  19 and back. For this document's purpose, we treat it same as freeing and
  20 allocating the page, respectfully.
  21
  22 1. Introduction
  23 ---------------
  24 Memory resource controller controls the number of lru physical pages
  25 (active and inactive list) a class uses. It does not restrict any
  26 other physical pages (slabs etc.,)
  27
  28 For simplicity, this document will always refer lru physical pages as
  29 physical pages or simply pages.
  30
  31 There are two parameters(that are set by the user) that affect the number
  32 of pages a class is allowed to have in active/inactive list.
  33 They are
  34   - guarantee - specifies the number of pages a class is
  35         guaranteed to get. In other words, if a class is using less than
  36         'guarantee' number of pages, its pages will not be freed when the
  37         memory subsystem tries to free some pages.
  38   - limit - specifies the maximum number of pages a class can get;
  39     'limit' in essence can be considered as the 'hard limit'
  40
  41 Rest of this document details how these two parameters are used in the
  42 memory allocation logic.
  43
  44 Note that the numbers that are specified in the shares file, doesn't
  45 directly correspond to the number of pages. But, the user can make
  46 it so by making the total_guarantee and max_limit of the default class
  47 (/rcfs/taskclass) to be the total number of pages(given in stats file)
  48 available in the system.
  49
  50   for example:
  51    # cd /rcfs/taskclass
  52    # grep System stats
  53    System: tot_pages=257512,active=5897,inactive=2931,free=243991
  54    # cat shares
  55    res=mem,guarantee=-2,limit=-2,total_guarantee=100,max_limit=100
  56
  57   "tot_pages=257512" above mean there are 257512 lru pages in
  58   the system.
  59
  60   By making total_guarantee and max_limit to be same as this number at
  61   this level (/rcfs/taskclass), one can make guarantee and limit in all
  62   classes refer to the number of pages.
  63
  64   # echo 'res=mem,total_guarantee=257512,max_limit=257512' > shares
  65   # cat shares
  66   res=mem,guarantee=-2,limit=-2,total_guarantee=257512,max_limit=257512
  67
  68
  69 The number of pages a class can use be anywhere between its guarantee and
  70 limit. CKRM memory controller springs into action when the system needs
  71 to choose a victim page to swap out. While the number of pages a class can
  72 have allocated may be anywhere between its guarantee and limit, victim
  73 pages will be choosen from classes that are above their guarantee.
  74
  75 Victim class will be chosen by the number pages a class is using over its
  76 guarantee. i.e a class that is using 10000 pages over its guarantee will be
  77 chosen against a class that is using 1000 pages over its guarantee.
  78 Pages belonging to classes that are below their guarantee will not be
  79 chosen as a victim.
  80
  81 2. Configuaration parameters
  82 ---------------------------
  83
  84 Memory controller provides the following configuration parameters. Usage of
  85 these parameters will be made clear in the following section.
  86
  87 fail_over: When pages are being allocated, if the class is over fail_over % of
  88     its limit, then fail the memory allocation. Default is 110.
  89     ex: If limit of a class is 30000 and fail_over is 110, then memory
  90     allocations would start failing once the class is using more than 33000
  91     pages.
  92
  93 shrink_at: When a class is using shrink_at % of its limit, then start
  94     shrinking the class, i.e start freeing the page to make more free pages
  95     available for this class. Default is 90.
  96     ex: If limit of a class is 30000 and shrink_at is 90, then pages from this
  97     class will start to get freed when the class's usage is above 27000
  98
  99 shrink_to: When a class reached shrink_at % of its limit, ckrm will try to
 100     shrink the class's usage to shrink_to %. Defalut is 80.
 101     ex: If limit of a class is 30000 with shrink_at being 90 and shrink_to
 102     being 80, then ckrm will try to free pages from the class when its
 103     usage reaches 27000 and will try to bring it down to 24000.
 104
 105 num_shrinks: Number of shrink attempts ckrm will do within shrink_interval
 106     seconds. After this many attempts in a period, ckrm will not attempt a
 107     shrink even if the class's usage goes over shrink_at %. Default is 10.
 108
 109 shrink_interval: Number of seconds in a shrink period. Default is 10.
 110
 111 3. Design
 112 --------------------------
 113
 114 CKRM memory resource controller taps at appropriate low level memory
 115 management functions to associate a page with a class and to charge
 116 a class that brings the page to the LRU list.
 117
 118 CKRM maintains lru lists per-class instead of keeping it system-wide, so
 119 that reducing a class's usage doesn't involve going through the system-wide
 120 lru lists.
 121
 122 3.1 Changes in page allocation function(__alloc_pages())
 123 --------------------------------------------------------
 124 - If the class that the current task belong to is over 'fail_over' % of its
 125   'limit', allocation of page(s) fail. Otherwise, the page allocation will
 126   proceed as before.
 127 - Note that the class is _not_ charged for the page(s) here.
 128
 129 3.2 Changes in page free(free_pages_bulk())
 130 -------------------------------------------
 131 - If the page still belong to a class, the class will be credited for this
 132   page.
 133
 134 3.3 Adding/Deleting page to active/inactive list
 135 -------------------------------------------------
 136 When a page is added to the active or inactive list, the class that the
 137 task belongs to is charged for the page usage.
 138
 139 When a page is deleted from the active or inactive list, the class that the
 140 page belongs to is credited back.
 141
 142 If a class uses 'shrink_at' % of its limit, attempt is made to shrink
 143 the class's usage to 'shrink_to' % of its limit, in order to help the class
 144 stay within its limit.
 145 But, if the class is aggressive, and keep getting over the class's limit
 146 often(more than such 'num_shrinks' events in 'shrink_interval' seconds),
 147 then the memory resource controller gives up on the class and doesn't try
 148 to shrink the class, which will eventually lead the class to reach
 149 fail_over % and then the page allocations will start failing.
 150
 151 3.4 Changes in the page reclaimation path (refill_inactive_zone and shrink_zone)
 152 -------------------------------------------------------------------------------
 153 Pages will be moved from active to inactive list(refill_inactive_zone) and
 154 pages from inactive list by choosing victim classes. Victim classes are
 155 chosen depending on their usage over their guarantee.
 156
 157 Classes with DONT_CARE guarantee are assumed an implicit guarantee which is
 158 based on the number of children(with DONT_CARE guarantee) its parent has
 159 (including the default class) and the unused pages its parent still has.
 160 ex1: If a default root class /rcfs/taskclass has 3 children c1, c2 and c3
 161 and has 200000 pages, and all the classes have DONT_CARE guarantees, then
 162 all the classes (c1, c2, c3 and the default class of /rcfs/taskclass) will
 163 get 50000 (200000 / 4) pages each.
 164 ex2: If, in the above example c1 is set with a guarantee of 80000 pages,
 165 then the other classes (c2, c3 and the default class of /rcfs/taskclass)
 166 will get 40000 ((200000 - 80000) / 3) pages each.
 167
 168 3.5 Handling of Shared pages
 169 ----------------------------
 170 Even if a mm is shared by tasks, the pages that belong to the mm will be
 171 charged against the individual tasks that bring the page into LRU.
 172
 173 But, when any task that is using a mm moves to a different class or exits,
 174 then all pages that belong to the mm will be charged against the richest
 175 class among the tasks that are using the mm.
 176
 177 Note: Shared page handling need to be improved with a better policy.
 178