1""" 2A basic caching module for xnu debug macros to use. 3 4 5When to use caching? 6~~~~~~~~~~~~~~~~~~~~ 7 8Very often you do not need to: LLDB already provides extensive data caching. 9 10The most common things that need caching are: 11- types (the gettype() function provides this) 12- globals (kern.globals / kern.GetGlobalVariable() provides this) 13 14 15If your macro is slow to get some data, before slapping a caching decorator, 16please profile your code using `xnudebug profile`. Very often slowness happens 17due to the usage of CreateValueFromExpression() which spins a full compiler 18to parse relatively trivial expressions and is easily 10-100x as slow as 19alternatives like CreateValueFromAddress(). 20 21Only use caching once you have eliminated those obvious performance hogs 22and an A/B shows meaningful speed improvements over the base line. 23 24 25I really need caching how does it work? 26~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 27 28This module provides function decorators to easily cache the result of 29functions based on their parameters, while keeping the caches separated 30per lldb target. 31 32@cache_statically can be used to cache data once per target, 33because it won't change if the process is resumed and stopped again. 34For example: types, constant values, global addresses, ... 35 36@cache_dynamically can be used to cache data that is expensive to compute 37but which content depends on the state of the process. It will be 38automatically invalidated for you if the process is resumed and 39then stops or hits a breakpoint. 40 41@dyn_cached_property can be used on instances to turn a member into 42a per-target cached dynamic property that will be cleaned up when 43the object dies or if the process is resumed and then stops 44or hits a breakpoint. 45 46Functions using these decorators, must have a `target=None` named argument 47that no caller of those functions need to pass explicitly, the decorator 48will take care of passing the proper current target value (equivalent to 49LazyTarget.GetTarget() except more efficiently). 50 51 52Cache Invalidation 53~~~~~~~~~~~~~~~~~~ 54 55This module make the crucial assumption that no XNU lldb macro 56will step/resume/... processes as the invalidation only happens 57when a new command is being run. 58 59If some macro needs to step/resume it has to provide its own 60cache invalidation, by e.g. pushing its own ImplicitContext() 61around such process state manipulations. 62""" 63 64# Private Routines and objects 65from __future__ import absolute_import 66 67from builtins import ( 68 dict, 69 hash, 70 list, 71 object, 72 tuple, 73) 74from collections import namedtuple 75 76import functools 77import gc 78import inspect 79import sys 80import weakref 81 82import lldb 83 84from .compat import valueint 85from .configuration import config 86from . import lldbwrap 87 88 89class _Registry(list): 90 """ Private class that holds a list of _Cache instances """ 91 92 __slots__ = ('name') 93 94 def __init__(self, name): 95 super(_Registry, self).__init__() 96 self.name = name 97 98 @property 99 def size(self): 100 return sys.getsizeof(self) 101 102 def invalidate(self, pid): 103 for cache in self: 104 cache.invalidate(pid) 105 106 def clear(self): 107 for cache in self: 108 cache.clear() 109 110 def __repr__(self): 111 return "_Registry({}, {})".format( 112 self.name, super(_Registry, self).__repr__()) 113 114 def __str__(self): 115 return "_Registry({}, {} caches, size {})".format( 116 self.name, len(self), self.size) 117 118 119class _Cache(dict): 120 """ Private class that implements a given global function _Cache 121 122 Those are created with the @cache_statically/@cache_dynamically 123 decorators 124 """ 125 126 __slots__ = ('name') 127 128 def __init__(self, name, registry): 129 super(_Cache, self).__init__() 130 self.name = name 131 registry.append(self) 132 133 @property 134 def size(self): 135 return sys.getsizeof(self) 136 137 def invalidate(self, pid): 138 if pid in self: del self[pid] 139 140 def __repr__(self): 141 return "_Cache({}, {})".format( 142 self.name, super(_Cache, self).__repr__()) 143 144 def __str__(self): 145 return "_Cache({}, {} entries, size {})".format( 146 self.name, len(self), self.size) 147 148 149_static_registry = _Registry('static') 150_dynamic_registry = _Registry('dynamic') 151_dynamic_keys = {} 152 153_implicit_target = None 154_implicit_process = None 155_implicit_exe_id = None 156_implicit_dynkey = None 157 158 159class _DynamicKey(object): 160 """ Wraps a process StopID as a key that can be used as caches keys """ 161 162 def __init__(self, exe_id, stop_id): 163 self.exe_id = exe_id 164 self.stop_id = stop_id 165 166 def __hash__(self): 167 return id(self) 168 169 170class LazyTarget(object): 171 """ A common object that lazy-evaluates and caches the lldb.SBTarget 172 and lldb.SBProcess for the current interactive debugging session. 173 """ 174 175 @staticmethod 176 def _CacheUpdateAnchor(exe_id, process): 177 global _dynamic_keys, _dynamic_registry 178 179 stop_id = process.GetStopID() 180 dyn_key = _dynamic_keys.get(exe_id) 181 182 if dyn_key is None: 183 _dynamic_keys[exe_id] = dyn_key = _DynamicKey(exe_id, stop_id) 184 elif dyn_key.stop_id != stop_id: 185 _dynamic_registry.invalidate(exe_id) 186 _dynamic_keys[exe_id] = dyn_key = _DynamicKey(exe_id, stop_id) 187 gc.collect() 188 189 return dyn_key 190 191 @staticmethod 192 def _CacheGC(): 193 global _dynamic_keys, _dynamic_registry, _static_registry 194 195 exe_ids = _dynamic_keys.keys() - set( 196 tg.GetProcess().GetUniqueID() 197 for tg in lldb.debugger 198 ) 199 200 for exe_id in exe_ids: 201 _static_registry.invalidate(exe_id) 202 _dynamic_registry.invalidate(exe_id) 203 del _dynamic_keys[exe_id] 204 205 if len(exe_ids): 206 gc.collect() 207 208 @staticmethod 209 def _CacheGetDynamicKey(): 210 """ Get a _DynamicKey for the most likely current process 211 """ 212 global _implicit_dynkey 213 214 dyn_key = _implicit_dynkey 215 if dyn_key is None: 216 process = lldbwrap.GetProcess() 217 exe_id = process.GetUniqueID() 218 dyn_key = LazyTarget._CacheUpdateAnchor(exe_id, process) 219 220 return dyn_key 221 222 @staticmethod 223 def _CacheClear(): 224 """ remove all cached data. 225 """ 226 global _dynamic_registry, _static_registry, _dynamic_keys 227 228 _dynamic_registry.clear() 229 _static_registry.clear() 230 _dynamic_keys.clear() 231 232 @staticmethod 233 def _CacheSize(): 234 """ Returns number of bytes held in cache. 235 returns: 236 int - size of cache including static and dynamic 237 """ 238 global _dynamic_registry, _static_registry 239 240 return _dynamic_registry.size + _static_registry.size 241 242 243 @staticmethod 244 def GetTarget(): 245 """ Get the SBTarget that is the most likely current target 246 """ 247 global _implicit_target 248 249 return _implicit_target or lldbwrap.GetTarget() 250 251 @staticmethod 252 def GetProcess(): 253 """ Get an SBProcess for the most likely current process 254 """ 255 global _implicit_process 256 257 return _implicit_process or lldbwrap.GetProcess() 258 259 260class ImplicitContext(object): 261 """ This class sets up the implicit target/process 262 being used by the XNu lldb macros system. 263 264 In order for lldb macros to function properly, such a context 265 must be used around code being run, otherwise macros will try 266 to infer it from the current lldb selected target which is 267 incorrect in certain contexts. 268 269 typical usage is: 270 271 with ImplicitContext(thing): 272 # code 273 274 where @c thing is any of an SBExecutionContext, an SBValue, 275 an SBBreakpoint, an SBProcess, or an SBTarget. 276 """ 277 278 __slots__ = ('target', 'process', 'exe_id', 'old_ctx') 279 280 def __init__(self, arg): 281 if isinstance(arg, lldb.SBExecutionContext): 282 exe_ctx = lldbwrap.SBExecutionContext(arg) 283 target = exe_ctx.GetTarget() 284 process = exe_ctx.GetProcess() 285 elif isinstance(arg, lldb.SBValue): 286 target = lldbwrap.SBTarget(arg.GetTarget()) 287 process = target.GetProcess() 288 elif isinstance(arg, lldb.SBBreakpoint): 289 bpoint = lldbwrap.SBBreakpoint(arg) 290 target = bpoint.GetTarget() 291 process = target.GetProcess() 292 elif isinstance(arg, lldb.SBProcess): 293 process = lldbwrap.SBProcess(arg) 294 target = process.GetTarget() 295 elif isinstance(arg, lldb.SBTarget): 296 target = lldbwrap.SBTarget(arg) 297 process = target.GetProcess() 298 else: 299 raise TypeError("argument type unsupported {}".format( 300 arg.__class__.__name__)) 301 302 self.target = target 303 self.process = process 304 self.exe_id = process.GetUniqueID() 305 self.old_ctx = None 306 307 def __enter__(self): 308 global _implicit_target, _implicit_process, _implicit_exe_id 309 global _implicit_dynkey, _dynamic_keys 310 311 self.old_ctx = (_implicit_target, _implicit_process, _implicit_exe_id) 312 313 _implicit_target = self.target 314 _implicit_process = process = self.process 315 _implicit_exe_id = exe_id = self.exe_id 316 _implicit_dynkey = LazyTarget._CacheUpdateAnchor(exe_id, process) 317 318 if len(_dynamic_keys) > 1: 319 LazyTarget._CacheGC() 320 321 def __exit__(self, *args): 322 global _implicit_target, _implicit_process, _implicit_exe_id 323 global _implicit_dynkey, _dynamic_keys 324 325 target, process, exe_id = self.old_ctx 326 self.old_ctx = None 327 328 _implicit_target = target 329 _implicit_process = process 330 _implicit_exe_id = exe_id 331 332 if process: 333 _implicit_dynkey = LazyTarget._CacheUpdateAnchor(exe_id, process) 334 else: 335 _implicit_dynkey = None 336 337 338class _HashedSeq(list): 339 """ This class guarantees that hash() will be called no more than once 340 per element. This is important because the lru_cache() will hash 341 the key multiple times on a cache miss. 342 343 Inspired by python3's lru_cache decorator implementation 344 """ 345 346 __slots__ = 'hashvalue' 347 348 def __init__(self, tup, hash=hash): 349 self[:] = tup 350 self.hashvalue = hash(tup) 351 352 def __hash__(self): 353 return self.hashvalue 354 355 @classmethod 356 def make_key(cls, args, kwds, kwd_mark = (object(),), 357 fasttypes = {valueint, int, str}, tuple=tuple, type=type, len=len): 358 359 """ Inspired from python3's cache implementation """ 360 361 key = args 362 if kwds: 363 key += kwd_mark 364 key += tuple(kwd.items()) 365 elif len(key) == 0: 366 return None 367 elif len(key) == 1 and type(key[0]) in fasttypes: 368 return key[0] 369 return cls(key) 370 371 372def _cache_with_registry(fn, registry, maxsize=128, sentinel=object()): 373 """ Internal function """ 374 375 nokey = False 376 377 if hasattr(inspect, 'signature'): # PY3 378 sig = inspect.signature(fn) 379 tg = sig.parameters.get('target') 380 if not tg or tg.default is not None: 381 raise ValueError("function doesn't have a 'target=None' argument") 382 383 nokey = len(sig.parameters) == 1 384 cache = _Cache(fn.__qualname__, registry) 385 else: 386 spec = inspect.getargspec(fn) 387 try: 388 index = spec.args.index('target') 389 offs = len(spec.args) - len(spec.defaults) 390 if index < offs or spec.defaults[index - offs] is not None: 391 raise ValueError 392 except: 393 raise ValueError("function doesn't have a 'target=None' argument") 394 395 nokey = len(spec.args) == 1 and spec.varargs is None and spec.keywords is None 396 cache = _Cache(fn.__name__, registry) 397 398 c_setdef = cache.setdefault 399 c_get = cache.get 400 make_key = _HashedSeq.make_key 401 getdynk = LazyTarget._CacheGetDynamicKey 402 gettg = LazyTarget.GetTarget 403 404 if nokey: 405 def caching_wrapper(*args, **kwds): 406 global _implicit_exe_id, _implicit_target 407 408 key = _implicit_exe_id or getdynk().exe_id 409 result = c_get(key, sentinel) 410 if result is not sentinel: 411 return result 412 413 kwds['target'] = _implicit_target or gettg() 414 return c_setdef(key, fn(*args, **kwds)) 415 416 def cached(*args, **kwds): 417 global _implicit_exe_id 418 419 return c_get(_implicit_exe_id or getdynk().exe_id, sentinel) != sentinel 420 else: 421 def caching_wrapper(*args, **kwds): 422 global _implicit_exe_id, _implicit_target 423 424 tg_d = c_setdef(_implicit_exe_id or getdynk().exe_id, {}) 425 c_key = make_key(args, kwds) 426 result = tg_d.get(c_key, sentinel) 427 if result is not sentinel: 428 return result 429 430 # 431 # Blunt policy to avoid exploding memory, 432 # that is simpler than an actual LRU. 433 # 434 # TODO: be smarter? 435 # 436 if len(tg_d) >= maxsize: tg_d.clear() 437 438 kwds['target'] = _implicit_target or gettg() 439 return tg_d.setdefault(c_key, fn(*args, **kwds)) 440 441 def cached(*args, **kwds): 442 global _implicit_exe_id 443 444 tg_d = c_get(_implicit_exe_id or getdynk().exe_id) 445 return tg_d and tg_d.get(make_key(args, kwds), sentinel) != sentinel 446 447 caching_wrapper.cached = cached 448 return functools.update_wrapper(caching_wrapper, fn) 449 450 451def cache_statically(fn): 452 """ Decorator to cache the results statically 453 454 This basically makes the decorated function cache its result based 455 on its arguments with an automatic static per target cache 456 457 The function must have a named parameter called 'target' defaulting 458 to None, with no clients ever passing it explicitly. It will be 459 passed the proper SBTarget when called. 460 461 @cache_statically(user_function) 462 Cache the results of this function automatically per target, 463 using the arguments of the function as the cache key. 464 """ 465 466 return _cache_with_registry(fn, _static_registry) 467 468 469def cache_dynamically(fn): 470 """ Decorator to cache the results dynamically 471 472 This basically makes the decorated function cache its result based 473 on its arguments with an automatic dynamic cache that is reset 474 every time the process state changes 475 476 The function must have a named parameter called 'target' defaulting 477 to None, with no clients ever passing it explicitly. It will be 478 passed the proper SBTarget when called. 479 480 @cache_dynamically(user_function) 481 Cache the results of this function automatically per target, 482 using the arguments of the function as the cache key. 483 """ 484 485 return _cache_with_registry(fn, _dynamic_registry) 486 487 488def dyn_cached_property(fn, sentinel=object()): 489 """ Decorator to make a class or method property cached per instance 490 491 The method must have the prototype: 492 493 def foo(self, target=None) 494 495 and will generate the property "foo". 496 """ 497 498 if hasattr(inspect, 'signature'): # PY3 499 if list(inspect.signature(fn).parameters) != ['self', 'target']: 500 raise ValueError("function signature must be (self, target=None)") 501 else: 502 spec = inspect.getargspec(fn) 503 if spec.args != ['self', 'target'] or \ 504 spec.varargs is not None or spec.keywords is not None: 505 raise ValueError("function signature must be (self, target=None)") 506 507 getdynk = LazyTarget._CacheGetDynamicKey 508 gettg = LazyTarget.GetTarget 509 c_attr = "_dyn_key__" + fn.__name__ 510 511 def dyn_cached_property_wrapper(self, target=None): 512 global _implicit_dynkey, _implicit_target 513 514 cache = getattr(self, c_attr, None) 515 if cache is None: 516 cache = weakref.WeakKeyDictionary() 517 setattr(self, c_attr, cache) 518 519 c_key = _implicit_dynkey or getdynk() 520 result = cache.get(c_key, sentinel) 521 if result is not sentinel: 522 return result 523 524 return cache.setdefault(c_key, fn(self, _implicit_target or gettg())) 525 526 return property(functools.update_wrapper(dyn_cached_property_wrapper, fn)) 527 528 529ClearAllCache = LazyTarget._CacheClear 530 531GetSizeOfCache = LazyTarget._CacheSize 532 533__all__ = [ 534 LazyTarget.__name__, 535 ImplicitContext.__name__, 536 537 cache_statically.__name__, 538 cache_dynamically.__name__, 539 dyn_cached_property.__name__, 540 541 ClearAllCache.__name__, 542 GetSizeOfCache.__name__, 543] 544