algo.py 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295
  1. # pylint: skip-file
  2. #
  3. # The Qubes OS Project, http://www.qubes-os.org
  4. #
  5. # Copyright (C) 2010 Rafal Wojtczuk <rafal@invisiblethingslab.com>
  6. # Copyright (C) 2013 Marek Marczykowski <marmarek@invisiblethingslab.com>
  7. #
  8. # This program is free software; you can redistribute it and/or
  9. # modify it under the terms of the GNU General Public License
  10. # as published by the Free Software Foundation; either version 2
  11. # of the License, or (at your option) any later version.
  12. #
  13. # This program is distributed in the hope that it will be useful,
  14. # but WITHOUT ANY WARRANTY; without even the implied warranty of
  15. # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16. # GNU General Public License for more details.
  17. #
  18. # You should have received a copy of the GNU General Public License
  19. # along with this program; if not, write to the Free Software
  20. # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  21. #
  22. import logging
  23. import string
  24. # This are only defaults - can be overridden by QMemmanServer with values from
  25. # config file
  26. CACHE_FACTOR = 1.3
  27. MIN_PREFMEM = 200*1024*1024
  28. DOM0_MEM_BOOST = 350*1024*1024
  29. log = logging.getLogger('qmemman.daemon.algo')
  30. #untrusted meminfo size is taken from xenstore key, thus its size is limited
  31. #so splits do not require excessive memory
  32. def sanitize_and_parse_meminfo(untrusted_meminfo):
  33. if not untrusted_meminfo:
  34. return None
  35. # new syntax - just one int
  36. try:
  37. if int(untrusted_meminfo) >= 0:
  38. return int(untrusted_meminfo)
  39. except ValueError:
  40. pass
  41. # not new syntax - try the old one
  42. untrusted_dict = {}
  43. # split meminfo contents into lines
  44. untrusted_lines = string.split(untrusted_meminfo, "\n")
  45. for untrusted_lines_iterator in untrusted_lines:
  46. # split a single meminfo line into words
  47. untrusted_words = string.split(untrusted_lines_iterator)
  48. if len(untrusted_words) >= 2:
  49. untrusted_dict[string.rstrip(untrusted_words[0], ":")] = \
  50. untrusted_words[1]
  51. # sanitize start
  52. if not is_meminfo_suspicious(untrusted_dict):
  53. # sanitize end
  54. meminfo = untrusted_dict
  55. return meminfo['MemTotal'] - \
  56. meminfo['MemFree'] - meminfo['Cached'] - meminfo['Buffers'] + \
  57. meminfo['SwapTotal'] - meminfo['SwapFree']
  58. return None
  59. def is_meminfo_suspicious(untrusted_meminfo):
  60. log.debug('is_meminfo_suspicious('
  61. 'untrusted_meminfo={!r})'.format(untrusted_meminfo))
  62. ret = False
  63. # check whether the required keys exist and are not negative
  64. try:
  65. for i in ('MemTotal', 'MemFree', 'Buffers', 'Cached',
  66. 'SwapTotal', 'SwapFree'):
  67. val = int(untrusted_meminfo[i])*1024
  68. if val < 0:
  69. ret = True
  70. untrusted_meminfo[i] = val
  71. except:
  72. ret = True
  73. if untrusted_meminfo['SwapTotal'] < untrusted_meminfo['SwapFree']:
  74. ret = True
  75. if untrusted_meminfo['MemTotal'] < \
  76. untrusted_meminfo['MemFree'] + \
  77. untrusted_meminfo['Cached'] + untrusted_meminfo['Buffers']:
  78. ret = True
  79. # we could also impose some limits on all the above values
  80. # but it has little purpose - all the domain can gain by passing e.g.
  81. # very large SwapTotal is that it will be assigned all free Xen memory
  82. # it can be achieved with legal values, too, and it will not allow to
  83. # starve existing domains, by design
  84. if ret:
  85. log.warning('suspicious meminfo untrusted_meminfo={!r}'.format(untrusted_meminfo))
  86. return ret
  87. # called when a domain updates its 'meminfo' xenstore key
  88. def refresh_meminfo_for_domain(domain, untrusted_xenstore_key):
  89. domain.mem_used = sanitize_and_parse_meminfo(untrusted_xenstore_key)
  90. def prefmem(domain):
  91. #dom0 is special, as it must have large cache, for vbds. Thus, give it a special boost
  92. if domain.id == '0':
  93. return min(domain.mem_used*CACHE_FACTOR + DOM0_MEM_BOOST, domain.memory_maximum)
  94. return max(min(domain.mem_used*CACHE_FACTOR, domain.memory_maximum), MIN_PREFMEM)
  95. def memory_needed(domain):
  96. #do not change
  97. #in balance(), "distribute total_available_memory proportionally to mempref" relies on this exact formula
  98. ret = prefmem(domain) - domain.memory_actual
  99. return ret
  100. #prepare list of (domain, memory_target) pairs that need to be passed
  101. #to "xm memset" equivalent in order to obtain "memsize" of memory
  102. #return empty list when the request cannot be satisfied
  103. def balloon(memsize, domain_dictionary):
  104. log.debug('balloon(memsize={!r}, domain_dictionary={!r})'.format(
  105. memsize, domain_dictionary))
  106. REQ_SAFETY_NET_FACTOR = 1.05
  107. donors = list()
  108. request = list()
  109. available = 0
  110. for i in domain_dictionary.keys():
  111. if domain_dictionary[i].mem_used is None:
  112. continue
  113. if domain_dictionary[i].no_progress:
  114. continue
  115. need = memory_needed(domain_dictionary[i])
  116. if need < 0:
  117. log.info('balloon: dom {} has actual memory {}'.format(i,
  118. domain_dictionary[i].memory_actual))
  119. donors.append((i,-need))
  120. available-=need
  121. log.info('req={} avail={} donors={!r}'.format(memsize, available, donors))
  122. if available<memsize:
  123. return ()
  124. scale = 1.0*memsize/available
  125. for donors_iter in donors:
  126. id, mem = donors_iter
  127. memborrowed = mem*scale*REQ_SAFETY_NET_FACTOR
  128. log.info('borrow {} from {}'.format(memborrowed, id))
  129. memtarget = int(domain_dictionary[id].memory_actual - memborrowed)
  130. request.append((id, memtarget))
  131. return request
  132. # REQ_SAFETY_NET_FACTOR is a bit greater that 1. So that if the domain yields a bit less than requested, due
  133. # to e.g. rounding errors, we will not get stuck. The surplus will return to the VM during "balance" call.
  134. #redistribute positive "total_available_memory" of memory between domains, proportionally to prefmem
  135. def balance_when_enough_memory(domain_dictionary,
  136. xen_free_memory, total_mem_pref, total_available_memory):
  137. log.info('balance_when_enough_memory(xen_free_memory={!r}, '
  138. 'total_mem_pref={!r}, total_available_memory={!r})'.format(
  139. xen_free_memory, total_mem_pref, total_available_memory))
  140. target_memory = {}
  141. # memory not assigned because of static max
  142. left_memory = 0
  143. acceptors_count = 0
  144. for i in domain_dictionary.keys():
  145. if domain_dictionary[i].mem_used is None:
  146. continue
  147. if domain_dictionary[i].no_progress:
  148. continue
  149. #distribute total_available_memory proportionally to mempref
  150. scale = 1.0*prefmem(domain_dictionary[i])/total_mem_pref
  151. target_nonint = prefmem(domain_dictionary[i]) + scale*total_available_memory
  152. #prevent rounding errors
  153. target = int(0.999*target_nonint)
  154. #do not try to give more memory than static max
  155. if target > domain_dictionary[i].memory_maximum:
  156. left_memory += target-domain_dictionary[i].memory_maximum
  157. target = domain_dictionary[i].memory_maximum
  158. else:
  159. # count domains which can accept more memory
  160. acceptors_count += 1
  161. target_memory[i] = target
  162. # distribute left memory across all acceptors
  163. while left_memory > 0 and acceptors_count > 0:
  164. log.info('left_memory={} acceptors_count={}'.format(
  165. left_memory, acceptors_count))
  166. new_left_memory = 0
  167. new_acceptors_count = acceptors_count
  168. for i in target_memory.keys():
  169. target = target_memory[i]
  170. if target < domain_dictionary[i].memory_maximum:
  171. memory_bonus = int(0.999*(left_memory/acceptors_count))
  172. if target+memory_bonus >= domain_dictionary[i].memory_maximum:
  173. new_left_memory += target+memory_bonus - domain_dictionary[i].memory_maximum
  174. target = domain_dictionary[i].memory_maximum
  175. new_acceptors_count -= 1
  176. else:
  177. target += memory_bonus
  178. target_memory[i] = target
  179. left_memory = new_left_memory
  180. acceptors_count = new_acceptors_count
  181. # split target_memory dictionary to donors and acceptors
  182. # this is needed to first get memory from donors and only then give it to acceptors
  183. donors_rq = list()
  184. acceptors_rq = list()
  185. for i in target_memory.keys():
  186. target = target_memory[i]
  187. if (target < domain_dictionary[i].memory_actual):
  188. donors_rq.append((i, target))
  189. else:
  190. acceptors_rq.append((i, target))
  191. # print 'balance(enough): xen_free_memory=', xen_free_memory, 'requests:', donors_rq + acceptors_rq
  192. return donors_rq + acceptors_rq
  193. #when not enough mem to make everyone be above prefmem, make donors be at prefmem, and
  194. #redistribute anything left between acceptors
  195. def balance_when_low_on_memory(domain_dictionary,
  196. xen_free_memory, total_mem_pref_acceptors, donors, acceptors):
  197. log.debug('balance_when_low_on_memory(xen_free_memory={!r}, '
  198. 'total_mem_pref_acceptors={!r}, donors={!r}, acceptors={!r})'.format(
  199. xen_free_memory, total_mem_pref_acceptors, donors, acceptors))
  200. donors_rq = list()
  201. acceptors_rq = list()
  202. squeezed_mem = xen_free_memory
  203. for i in donors:
  204. avail = -memory_needed(domain_dictionary[i])
  205. if avail < 10*1024*1024:
  206. #probably we have already tried making it exactly at prefmem, give up
  207. continue
  208. squeezed_mem -= avail
  209. donors_rq.append((i, prefmem(domain_dictionary[i])))
  210. #the below can happen if initially xen free memory is below 50M
  211. if squeezed_mem < 0:
  212. return donors_rq
  213. for i in acceptors:
  214. scale = 1.0*prefmem(domain_dictionary[i])/total_mem_pref_acceptors
  215. target_nonint = domain_dictionary[i].memory_actual + scale*squeezed_mem
  216. #do not try to give more memory than static max
  217. target = min(int(0.999*target_nonint), domain_dictionary[i].memory_maximum)
  218. acceptors_rq.append((i, target))
  219. # print 'balance(low): xen_free_memory=', xen_free_memory, 'requests:', donors_rq + acceptors_rq
  220. return donors_rq + acceptors_rq
  221. #redistribute memory across domains
  222. #called when one of domains update its 'meminfo' xenstore key
  223. #return the list of (domain, memory_target) pairs to be passed to
  224. #"xm memset" equivalent
  225. def balance(xen_free_memory, domain_dictionary):
  226. log.debug('balance(xen_free_memory={!r}, domain_dictionary={!r})'.format(
  227. xen_free_memory, domain_dictionary))
  228. #sum of all memory requirements - in other words, the difference between
  229. #memory required to be added to domains (acceptors) to make them be at their
  230. #preferred memory, and memory that can be taken from domains (donors) that
  231. #can provide memory. So, it can be negative when plenty of memory.
  232. total_memory_needed = 0
  233. #sum of memory preferences of all domains
  234. total_mem_pref = 0
  235. #sum of memory preferences of all domains that require more memory
  236. total_mem_pref_acceptors = 0
  237. donors = list() # domains that can yield memory
  238. acceptors = list() # domains that require more memory
  239. #pass 1: compute the above "total" values
  240. for i in domain_dictionary.keys():
  241. if domain_dictionary[i].mem_used is None:
  242. continue
  243. if domain_dictionary[i].no_progress:
  244. continue
  245. need = memory_needed(domain_dictionary[i])
  246. # print 'domain' , i, 'act/pref', domain_dictionary[i].memory_actual, prefmem(domain_dictionary[i]), 'need=', need
  247. if need < 0 or domain_dictionary[i].memory_actual >= domain_dictionary[i].memory_maximum:
  248. donors.append(i)
  249. else:
  250. acceptors.append(i)
  251. total_mem_pref_acceptors += prefmem(domain_dictionary[i])
  252. total_memory_needed += need
  253. total_mem_pref += prefmem(domain_dictionary[i])
  254. total_available_memory = xen_free_memory - total_memory_needed
  255. if total_available_memory > 0:
  256. return balance_when_enough_memory(domain_dictionary, xen_free_memory, total_mem_pref, total_available_memory)
  257. else:
  258. return balance_when_low_on_memory(domain_dictionary, xen_free_memory, total_mem_pref_acceptors, donors, acceptors)