Implementing heap‐object behavior prediction efficiently and effectively

Heap‐allocated objects play an important role in many modern programs. Various results have shown the overall performance of these programs can be improved by increasing the reference locality of heap‐allocated objects. In this paper we describe an approach that improves the virtual memory performance of allocation‐intensive C programs by predicting the reference behavior and lifetime of heap objects as they are allocated. We further describe an implementation of our prediction algorithm and evaluate its performance on real programs. As part of our implementation, we present a low‐overhead algorithm to minimize the cost of gathering run‐time stack information. Finally, we show that an implementation of these algorithms has little overhead and can improve the virtual memory and TLB performance of programs substantially. Copyright © 2001 John Wiley & Sons, Ltd.     

基于空间扫描策略的3维相交检测算法

针对复杂虚拟场景中碰撞检测和空间分析等操作实时性差的问题,提出一种适用于3维空间对象间的快速相交检测算法——Space Sweep。该算法首先根据场景内空间对象分布特征,构建事件点及其列表;利用空间扫描策略,自适应地构建一系列假想的空间扫描面;在扫描面移动的过程中,将空间对象的状态分为死亡态、激活态和休眠态,通过只对当前处于激活态的空间对象进行相交测试,有效地减少了空间对象间不必要的相交计算。该算法提高了虚拟场景中3维空间对象间相交检测的效率,为3D GIS中实时空间分析提供了有力的技术支持。最后,通过对比测试验证了本文算法的实用性。     

Detecting memory leaks in managed languages with Cork

A memory leak in a managed language occurs when the program inadvertently maintains references to objects that it no longer needs. Memory leaks cause systematic heap growth that degrade performance and can result in program crashes after perhaps days or weeks of execution. Prior approaches for detecting memory leaks rely on heap differencing or detailed object statistics which store state proportional to the number of objects in the heap. These overheads preclude their use on the same processor for deployed long‐running applications. This paper introduces Cork as a tool that accurately identifies heap growth caused by leaks. It is space efficient (adding less than 1% to the heap) and time efficient (adding 2.3% on average to total execution time). We implement this approach of examining and summarizing the class of live objects during garbage collection in a class points‐from graph (CPFG). Each node in the CPFG represents a class and edges between nodes represent references between objects of the specific classes. Cork annotates nodes and edges with the corresponding volume of live objects. Cork identifies growing data structures across multiple collections and computes a class slice to identify leaks for the user. We experiment with two functions for identifying growth and show that Cork is accurate: it identifies systematic heap growth with no false positives in 4 of 15 benchmarks we tested. Cork's slice report enabled us to quickly identify and eliminate growing data structures in large and unfamiliar programs, something their developers had not previously done. Copyright © 2009 John Wiley & Sons, Ltd.     

A performance perspective on the Active Memory System

One major problem of using Java in real-time and embedded devices is the non-deterministic turnaround time of dynamic memory management systems (memory allocation and garbage collection). For the allocation, the non-determinism is often contributed by the time to perform searching, splitting, and coalescing. For the garbage collection, the turnaround time is usually determined by the size of the heap, the number of live objects, the number of object collected, and the amount of garbage collected. Even with the current state-of-the-art garbage collectors (generational and incremental schemes), they may or may not guarantee the worst-case latency. Moreover, such schemes often prolong overall garbage collection time.

In this paper, the performance analysis of the proposed Active Memory Module (AMM) for embedded systems is presented. Unlike the software counterparts, the AMM can perform a memory allocation in a predictable and bounded fashion (14 cycles). Moreover, it can also yield a bounded sweeping time regardless of the number of live objects or heap size. By utilizing the proposed system, the overall speedup can be as high as 23% compared to the garbage collection system of the JDK 1.2.2 running in classic mode.     

点间确定别名及其在Java程序数据依赖分析中的应用

堆内存的大量使用使得Java程序上数据依赖关系的精确提取仍存在许多困难.对于堆空间上的依赖提取,通常的做法是先对堆上空间进行命名,再据此分析依赖关系.然而该方法不能在多个定义间进行强更新,故分析精度不够理想.针对此问题,该文首先提出了一种点间确定别名的概念,然后用它生成强更新和相对更新来精化数据依赖分析.实验表明,与不进行强更新和相对更新的数据依赖分析方法相比,新算法能够在相对较少的额外时间消耗内,有效地提高堆空间上依赖分析的精度.     

Memory Mangement in the PoSSo Solver

A uniform general purpose garbage collector may not always provide optimal performance. Sometimes an algorithm exhibits a predictable pattern of memory usage that could be exploited, delaying as much as possible the intervention of the collector. This requires a collector whose strategy can be customized to the need of an algorithm. We present a dynamic memory management framework which allows such customization, while preserving the convenience of automatic collection in the normal case. The Customizable Memory Management (CMM) organizes memory in multiple heaps, each one encapsulating a particular storage discipline. The default heap for collectable objects uses the technique of mostly copying garbage collection, providing good performance and memory compaction. Customization of the collector is achieved through object orientation by specialising the collector methods for each heap class. We describe how the CMM has been exploited in the implementation of the Buchberger algorithm, by using a special heap for temporary objects created during polynomial reduction. The solution drastically reduces the overall cost of memory allocation in the algorithm.     

Connection Analysis: A Practical Interprocedural Heap Analysis for C

This paper presents a practical heap analysis technique, connection analysis, that can be used to disambiguate heap accesses in C programs. The technique is designed for analyzing programs that allocate many disjoint objects in the heap such as dynamically-allocated arrays in scientific programs. The method statically estimates connection matrices which encode the connection relationships between all heap-directed pointers at each program point. The results of the analysis can be used by parallelizing compilers to determine when two heap-allocated objects are guaranteed to be disjoint, and thus can be used to improve array dependence and interference analysis. The method has been implemented as a context-sensitive interprocedural analysis in the McCAT optimizing/parallelizing C compiler. Experimental results are given to compare the accuracy of connection analysis versus a conservative estimate based on points-to analysis.     

Efficient and formal generalized symbolic execution

Programs that manipulate dynamic heap objects are difficult to analyze due to issues like aliasing. Lazy initialization algorithm enables the classical symbolic execution to handle such programs. Despite its successes, there are two unresolved issues: (1) inefficiency; (2) lack of formal study. For the inefficiency issue, we have proposed two improved algorithms that give significant analysis time reduction over the original lazy initialization algorithm. In this article, we formalize the lazy initialization algorithm and the improved algorithms as operational semantics of a core subset of the Java Virtual Machine (JVM) instructions, and prove that all algorithms are relatively sound and complete with respect to the JVM concrete semantics. Finally, we conduct a set of extensive experiments that compare the three algorithms and demonstrate the efficiency of the improved algorithms.     

基于eBPF的内核堆漏洞动态缓解机制

内核堆漏洞是目前操作系统安全的主要威胁之一, 用户层攻击者通过触发漏洞能够泄露或修改内核敏感信息, 破坏内核控制流, 甚至获取root权限. 但是由于漏洞的数量和复杂性剧增, 从漏洞首次被报告到开发者给出修复补丁(patch)往往需要较长时间, 而内核现阶段采用的缓解机制均能被稳定绕过. 为此提出一种基于eBPF的内核堆漏洞动态缓解框架, 用于在修复时间窗口中降低内核安全风险. 动态缓解框架采取数据对象空间随机化策略, 在每次分配时为漏洞报告中涉及的数据对象分配随机地址, 并充分利用eBPF的动态、安全特性将空间随机化对象在运行时注入内核, 使得攻击者无法准确放置攻击负载, 堆漏洞几乎无法被利用. 评估40个真实内核堆漏洞, 并收集12个绕过现有缓解机制的攻击程序进行进一步分析和实验, 证实动态缓解框架提供充足的安全性. 性能测试表明, 即使在严苛情况下, 大量分配的4类数据对象仅对系统造成约1%的性能损耗和可以忽略不计的内存损耗, 同时增加保护对象的数量几乎不引入额外性能损耗. 所提机制对比相关工作适用范围更广, 安全性更强, 而且无需安全专家发布的漏洞补丁, 可以根据漏洞报告生成缓解程序, 具备广阔应用前景.     

Cold object identification in the Java virtual machine

Many Java applications instantiate objects within the Java heap that are persistent but seldom if ever referenced by the application. Examples include strings, such as error messages, and collections of value objects that are preloaded for fast access. This paper describes a stack‐based framework for detecting these ‘cold’ objects at runtime, with a view to marshaling and sequestering them in designated regions of the heap where they may be preferentially paged out to a backing store, thereby freeing physical memory pages for occupation by more active objects. Furthermore, we evaluate the correctness and efficiency of stack‐based approach with an access barrier. The experimental results from a series of SPECjvm2008 benchmarks are presented. Copyright © 2016 John Wiley & Sons, Ltd.     

Space-Reduction Strategies for Model Checking Dynamic Software

Effective model-checking of modern object-oriented software systems requires providing support for program features such as dynamically created threads, heap-allocated objects and garbage collection. These features have often proven problematic to treat using many previous model-checking frameworks that do not provide sophisticated heap representations and optimizations.In this paper, we define a flexible framework for combined heap and thread symmetry reductions in explicit-state model checking that can be tuned to trade run-time overhead for precision. In addition, we describe various strategies for duplication-reducing state-space encodings for object-oriented heap structures. We have implemented these techniques in Bogor (our extensible software model-checking framework), and we present empirical data to support the effectiveness of these memory reductions on a collection of realistic examples and to demonstrate that they improve upon previous approaches. These techniques, formalized in a group theoretic framework, can be applied to any non-deterministic heap object diagram.     

Visible Light and X-Ray Ray Tracing of Generalized Cylinders

A new algorithm for ray tracing generalized cylinders whose axis is an arbitrary three-dimensional space curve and whose cross-sectional contour can be varied according to a general sweeping rule is presented. The main restriction placed on the class of generalized cylinders that can be ray-traced is that the sweeping rule of the generalized cylinder must be invertible. This algorithm handles a broader class of generalized cylinders than any other reported ray tracer. It has been integrated into a general geometric modeling system that can render objects utilizing visible light as well as simulated X rays. Generalized cylinders are often used in modeling systems because they compactly represent objects. Many commonly occurring objects including snakes, horses, airplanes, flower vases, and organs of the human abdomen such as the stomach and liver can be described naturally and conveniently in terms of one or more generalized cylinder primitives. By extending the class of generalized cylinders that can be conveniently modeled, the presented algorithm enhances the utility of modeling systems based on generalized cylinders. X-ray images of the internal bone structure of a knee joint and a visible light image of a fan blade assembly are presented.     

数据流环境下基于距离的离群点检测算法

面向滑动窗口的连续离群点检测问题是数据流管理领域中的重要问题.该问题在信用卡欺诈检测、网络入侵防御,地质灾害预警等诸多领域发挥着重要作用.现有算法大多需要利用范围查询判断对象之间的位置关系,而范围查询的查询代价大,无法满足实时性要求.本文提出基于滑动窗口模型下的查询处理框架GBEH(grid-based excepted heap).首先,它以网格为基础构建索引GQBI(grid queue based index)管理数据流.该索引一方面维护数据流之间的位置关系,另一方面利用队列维护数据流的时序关系.其次, GBEH提出离群点检测算法PBH(priority based heap).该算法利用查询范围与网格单元格的相交面积计算该单元格中包含于查询范围对象数目的数学期望,并以此为基础构建基于小顶堆执行范围查询,从而有效降低范围查询代价,实现高效检测.理论分析和实验验证GBEH的高效性和稳定性.     

基于Realms的空间数据库系统实现技术

Realms是将所有空间元素定义在分辨率确定的网格上的数学模型,它提出所有空间对象共享一个空间元素集合及空间元素的排序规则。Realms可以对空间数据进行离散化和约束,使二维空间线性化为一维有序元素集,基于Realms的空间数据组织能有效地支持平面扫描算法,通过对空间对象的平面扫描高效简单地实现多数空间分析算法。文中阐述了Realms的概念,给出了基于Realms的空间数据库对空间对象的建模,并用扫描线技术实现空间分析算法。     

A top-k spatial join querying processing algorithm based on spark

Aiming at the problem of top-k spatial join query processing in cloud computing systems, a Spark-based top-k spatial join (STKSJ) query processing algorithm is proposed. In this algorithm, the whole data space is divided into grid cells of the same size by a grid partitioning method, and each spatial object in one data set is projected into a grid cell. The Minimum Bounding Rectangle (MBR) of all spatial objects in each grid cell is computed. The spatial objects overlapping with these MBRs in another spatial data set are replicated to the corresponding grid cells, thereby filtering out spatial objects for which there are no join results, thus reducing the cost of subsequent spatial join processing. An improved plane sweeping algorithm is also proposed that speeds up the scanning mode and applies threshold filtering, thus greatly reducing the communication and computation costs of intermediate join results in subsequent top-k aggregation operations. Experimental results on synthetic and real data sets show that the proposed algorithm has clear advantages, and better performance than existing top-k spatial join query processing algorithms.     

Distribution of distinguishable objects to bins: generating all distributions

In this paper we give an algorithm to generate all distributions of distinguishable objects to bins without repetition. Our algorithm generates each distribution in constant time. To the best of our knowledge, our algorithm is the first algorithm which generates each solution in O(1) time in the ordinary sense. As a byproduct of our algorithm, we obtain a new algorithm to enumerate all multiset partitions when the number of partitions is fixed and the partitions are numbered. In this case, the algorithm generates each multiset partitions in constant time (in the ordinary sense). Finally, we extend the algorithm to the case when the bins have priorities associated with them. Overall space complexity of the algorithm is O(mklgn), where there are m bins and the objects fall into k different classes. In a companion paper, the generation of all distributions of identical objects to bins is also considered.     

A semi-incremental garbage collection algorithm

Lisp is restricted in application because of d the unpredictable delays introduced by garbage collection. Incremental garbage collectors eliminate the delays, but are less efficient overall. We present a semi-incremental algorithm that reduces the delays and is, moreover more efficient than the mark-scan algorithm from which it is derived. The mark-scan algorithm is explained it consists of a mark phase followed by a sweep phase. The sweep phase can be performed incrementally, but the mark phase cannot. If this modification is made, our semi-incremental algorithm is derived. Using the new algorithm the delay on garbage collection is proportional to the amount of heap actually in use, not the size of the heap. Allocating a cell takes a variable amount of time, depending on the proportion of the heap in use. Comparing the number of operations in the old and new algorithms, we see that the new algorithm is more efficient. The new algorithm was used as part of a Lisp implementation on an LSI-11/03 and found to behave well.     

Deleting the root of a heap

Summary The average behavior of the familiar algorithm for root deletion is considered, when every heap has the same probability to occur. The analysis centers around the notion of a viable path in the tree representation, i.e. such a path the label which replaces the label of the root may be allowed to travel when the heap is reconstructed. In case the size of the heap is a power of 2 it is shown that both the expected number of comparisons and of interchanges are asymptotically equal to the respective numbers in the worst case.Some results were presented at the 19th Allerton Conference on Communications, Control, and Computing, University of Illinois, 1981, and the Second World Conference on Mathematics at the Service of Man, Las Palmas, Canary Islands, Spain, 1982Some of this work was done at the Fernuniversität, Hagen, West Germany     

内存泄漏对象检测与度量方法

程序运行过程中一些不再被使用的对象未及时释放会引发内存泄漏问题,泄漏对象经过长期累积会降低系统性能,甚至导致系统崩溃。针对Java程序中的内存泄漏问题,提出了一种内存泄漏对象检测与度量方法。通过动态跟踪源程序的执行过程,周期性记录堆栈信息,并分析堆中可疑的泄漏对象。定义内存泄漏度计算方法,度量不同对象对程序泄漏的影响程度,从而确定产生泄漏的对象。最后选取两个开源程序进行验证,并与两种现有方法进行对比,结果表明该方法的泄漏检测率较高。     

An optimistic implementation of the stack-heap

A stack-heap has been shown to be an efficient storage management scheme for programs containing both recursive and retentive control structures. The stack-heap uses a compile-time marking algorithm that determines those program modules that may need retention at run-time. Thus, instances of marked modules are allocated space in the heap during execution. All others are stored in a stack. In this paper, we present an optimistic implementation of the stack-heap in which each module instance is kept in the stack until it suspends. Upon suspension, the instance is copied into the heap where it remains for the lifetime of the instance. Some of the restrictions imposed on the programming language by the original stack-heap scheme are eliminated under this optimistic implementation. It is shown that when the original stack-heap cannot be used and both recursive and coroutine programs are likely, the optimistic implementation of the stack-heap is more efficient on the average than the heap.