qmemman_algo.py 12 KB

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