Xiao-Feng Li

Architecture Design of the Runtime Engine of Google A2A (Agent to Agent)

2025-08-24T20:04:00.000-07:00

The Google Agent-to-Agent (A2A) protocol enables collaboration between heterogeneous AI agents by exposing any server-side agent as a standardized interface to its clients. The A2A runtime engine is designed as a proxy agent: it does not need to know the internal implementation of the actual agent but instead provides a uniform way for clients to interact with it.

This proxy pattern is the foundation of the A2A server’s architecture:

It proxies responses from the underlying agent to the client.
It manages execution state and message history in a consistent manner.
It supports multiple communication modes (streaming, non-streaming, notifications).

The detailed analysis is given in my presentation in Architecture Design of the Runtime Engine of Google A2A [1].

[1] https://xiaofeng.info/presentations/Runtime-Engine-of-Google-A2A.pdf

Survey and discussions on trusted execution environment (TEE)

2020-05-26T21:09:00.000-07:00

I wrote a survey on current implementations of trusted execution environment (TEE), and discussed the properties of different technologies and proposed two newer approaches.

In the survey, I categorized the current technologies into the following groups:

TPM (trusted computing module) based solution, such as Intel TXT, AMD SKINIT
Coprocessor based solution, such as Intel ME, Apple secure enclave
Privileged mode based solution, such as Intel SMM, ARM TrustZone
Virtualization based solution, such as Microsoft VSM, seL4/NOVA
Total memory encryption based solution, such as AMD SEV, Intel MKTME
User secure enclave (regional memory encryption) based solution, such as Intel SGX, RISC-V Sanctum

To build a successful TEE, isolation is the fundamental approach. If isolation is unachievable, a component has to be introduced for authorization - this is the ultimate security solution, like in the web. Encryption is only a rescue when the end points do not trust each other, or the data path can be intercepted/snooped, which is known as authentication.

A hardware-based solution for authorization can be plausible in the end. Before that, one app per encrypted VM or one secure enclave per app is the most close solution.

One step back, unless an all-path encryption is available, all of the solutions for TEE need a kernel component in TCB, be it in the enclave, or hypervisor, or whatever.

For the kernel, a capability-based microkernel or the like is always desirable for the purpose of security, and a verified kernel can improve the security.

Design of next generation OS

2020-05-26T19:01:00.000-07:00

I put together my thoughts on the design of next generation OS towards a connected world - in sense of connected devices, connected services and connected people. There are already lots of good progresses in the right direction.

To facilitate the connected world, OS should be designed with mindset in the following three dimensions:

From individual-oriented to group-oriented, with a distributed and connected framework;
From application-oriented to service-oriented, with the full support of service-oriented API;
From traditional I/O-oriented UI to context-aware UI, with natural and intuitive interactions.

These are not just thoughts, but actually the OS trends seen in the reality, including my personal project experiences.

Discussions on Asynchronous Programming APIs

2019-10-22T18:26:00.002-07:00

I put together a slide deck discussing the Asynchronous Programming APIs, focusing on the rationalities of the APIs design and their evolutions from single async op blocking syscall through resumable function based synchronous programming, including select, epoll, kqueue, callback, promise, await, etc. Here is the content in the summary slide:

Asynchronous programming API design aims to improve both productivity and scalability:

Productivity is achieved largely through “synchronous” programming constructs;
Scalability is achieved by overlapping async operations with processor execution;
The key of the API design is to allow a single thread to issue multiple outstanding async operations so that any ready result can enable certain code execution, hence minimal processor idle time;
This enables pure user level solution that is platform agnostic, and then thread pool is largely an orthogonal multiplier;
The APIs have evolved from synchronous system call to synchronous user call while maintaining all the async benefits;
Two levels of scheduling: user coroutines and kernel threads, exploiting the best of green threads and async APIs

Asynchronous callback, and its relation with event-driven and coroutines

2019-10-09T20:57:00.000-07:00

(This is my answer to a question in stackoverflow.com regarding the general implementation techniques of asynchronous callback.)

TL;DR: To implement asynchronous callback is basically to allow the control flow to proceed without blocking for the callback. Before the callback function is finally called, the control flow is free to execute anything that has no dependence on the callback's result, e.g., the caller can proceed as if the callback function has returned (without using its result), or the caller may yield its control to other functions.

Since the question is for general implementation rather than a specific language, my answer tries to be as general as to cover the implementation commonalities.

Different languages have different implementations for asynchronous callbacks, but the principles are the same. The key is to decouple the control flow from the code executed. They correspond to the execution context (like a thread of control with a runtime stack) and the executed task. Traditionally the control flow of the program forms a linear (or contiguous) call chain. (Signal handler is an exception, but signal emission is already asynchronous.) With asynchronous callbacks, they are decoupled.

1. The principles

To decouple the control flow from the code, it is helpful to think of every asynchronous callback as a conditional task. When the code registers an asynchronous callback, it virtually installs the task's condition in the system. The callback function is then invoked when the condition is satisfied. To support this, a condition monitoring mechanism and a task scheduler are needed, so that,

The programmer does not need to track the callback's condition;
Before the condition is satisfied, the program may proceed to execute other code that does not depend on the callback's result, without blocking on the condition;
Once the condition is satisfied, the callback is guaranteed to execute. The programmer does not need to schedule its execution;
After the callback is executed, its result is accessible to the caller.

2. Implementation for Portability

For example, if your code needs to process the data from a network connection, you do not need to write the code checking the connection state. You only registers a callback that will be invoked once the data is available for processing. The dirty work of connection checking is left to the language implementation, which is known to be tricky especially when we talk about scalability and portability.

The language implementation may employ asynchronous io, nonblocking io or a thread pool or whatever techniques to check the network state for you, and once the data is ready, the callback function is then scheduled to execute. Here the control flow of your code looks like directly going from the callback registration to the callback execution, because the language hides the intermediate steps. This is the portability story.

3. Implementation for Scalability

To hide the dirty work is only part of the whole story. The other part is that, your code itself does not need to block waiting for the task condition. It does not make sense to wait for one connection's data when you have lots of network connections simultaneously and some of them may already have data ready. The control flow of your code can simply register the callback, and then moves on with other tasks (e.g., the callbacks whose conditions have been satisfied), knowing that the registered callbacks will be executed anyway when their data are available.

If to satisfy the callback's condition does not involve much of the CPU (e.g., waiting for a timer, or waiting for the data from network), and the callback function itself is light-weighted, then single CPU (or single thread) is able to process lots of callbacks concurrently, such as incoming network requests processing. Here the control flow may look like jumping from one callback to another. This is the scalability story.

4. Implementation for Parallelism

Sometimes, the callbacks are not pending for non-blocking IO condition, but for blocking operations such as page fault; or the callbacks do not rely on any condition, but are pure computation logics. In this case, asynchronous callback does not save you the CPU waiting time (because there is no idle waiting). But since asynchronous callback implies that the callback function can be executed in parallel either with the caller task or other callbacks (subject to certain data sharing and synchronization constraints), the language implementation can dispatch the callback tasks to different threads, achieving the benefits of parallelism, if the platform has more than one hardware thread context. It still improves scalability.

5. Implementation for Productivity

The productivity with asynchronous callback may not be very positive when the code need to deal with chained callbacks, i.e., when callbacks register other callbacks in recursive way, known as callback hell. There are ways to rescue.

The semantics of an asynchronous callback can be explored so as to substitute the hopeless nested callbacks with other language constructs. Basically there can be two different views of callbacks:

From data flow point of view: asynchronous callback = event + task. To register a callback essentially generates an event that will emit when the task condition is satisfied. In this view, the chained callbacks are just events whose processing triggers other event emission. It can be naturally implemented in event-driven programming, where the task execution is driven by events. Promise and Observable may also be regarded as event-driven concept. When multiple events are ready concurrently, their associated tasks can be executed concurrently as well.

From control flow point of view: to register a callback yields the control to other code, and the callback execution just resumes the control flow once its condition is satisfied. In this view, chained asynchronous callbacks are just resumable functions. Multiple callbacks can be written as one after another in traditional "synchronous" way, with yield/await operation in between. It becomes coroutine.

I haven't discussed the implementation of data passing between the asynchronous callback and its caller, but that is usually not difficult if using shared memory where caller and callback can share data. Actually Golang's channel can also be considered in line of yield/await but with its focus on data passing.

Differences between data race and race condition

2019-10-04T11:43:00.004-07:00

(This is my answer to the question in stackoverflow.com: "Are “data races” and “race condition” actually the same thing in context of concurrent programming?")

TL;DR: The distinction between data race and race condition depends on the nature of problem formulation, and where to draw the boundary between undefined behavior and well-defined but indeterminate behavior. The current distinction is conventional and best reflects the interface between processor architect and programming language.

1. Semantics

Data race specifically refers to the non-synchronized conflicting "memory accesses" (or actions, or operations) to the same memory location. If there is no conflict in the memory accesses, while there is still indeterminate behavior caused by operation ordering, that is a race condition. (If there is no memory shared by different threads that may run on multiple cores, the problem discussed here does not exist.)

Note "memory accesses" here have specific meaning. They refer to the "pure" memory load or store actions, without any additional semantics applied. For example, a memory store from one thread does not (necessarily) know how long it takes for the data to be written into the memory, and finally propagates to another thread. For another example, a memory store to one location before another store to another location by the same thread does not (necessarily) guarantee the first data written in the memory be ahead of the second. As a result, the order of those pure memory accesses are not (necessarily) able to be "reasoned" by program developers, and anything could happen, unless otherwise well defined.

When the "memory accesses" are well defined in terms of ordering through synchronization, additional semantics can ensure that, even if the timing of the memory accesses are indeterminate, their order can be "reasoned" through the synchronizations. Note, although the ordering between the memory accesses can be reasoned, they are not necessarily determinate, hence the race condition.

2. Why the difference?

But if the order is still indeterminate in race condition, why bother to distinguish it from data race? The reason is in practical rather than theoretical. It is because the distinction does exist in the interface between the programming language and processor architecture.

A memory load/store instruction in modern architecture is usually implemented as "pure" memory access, due to the nature of out-of-order pipeline, speculation, multi-level of cache, cpu-ram interconnection, especially multi-core, etc. There are lots of factors leading to indeterminate timing and ordering. To enforce ordering for every memory instruction incurs huge penalty, especially in a processor design that supports multi-core. So the ordering semantics are provided with additional instructions like various barriers (or fences).

Data race is the situation of processor instruction execution without additional fences to help reasoning the ordering of conflicting memory accesses. The result is not only indeterminate, but also possibly very weird, e.g., two writes to the same word location by different threads may result with each writing half of the word, or may only operate upon their locally cached values. -- These are undefined behavior, from the programmer's point of view. But they are (usually) well defined from the processor architect's point of view.

Programmers have to have a way to reason their code execution. Data race is something they cannot make sense, therefore should always avoid (normally). That is why the language specifications that are low level enough usually define data race as undefined behavior, different from the well-defined memory behavior of race condition.

3. Language memory models

Different processors may have different memory access behavior, i.e., processor memory model. It is awkward for programmers to study the memory model of every modern processor and then develop programs that can benefit from them. It is desirable if the language can define a memory model so that the programs of that language always behave as expected as the memory model defines. That is why Java and C++ have their memory models defined. It is the burden of the compiler/runtime developers to ensure the language memory models are enforced across different processor architectures.

Actually it is (almost) impossible for a programming language to support shared memory multithreading/multicore without a memory model defined implicitly or explicitly, because otherwise there is no defined way to reason the behavior of shared data accesses. It is possible to exert the memory model through a library (outside of the language itself), but that won't work without a very strict programming model that effectively permeates the memory model into the language.

That said, if a language does not want to expose the low level behavior of the processor (and is willing to sacrifice certain performance benefits of the modern architectures), they can choose to define a memory model that completely hide the details of "pure" memory accesses, but apply ordering semantics for all their memory operations. Then the compiler/runtime developers may choose to treat every memory variable as volatile in all processor architectures. For these languages (that support shared memory across threads), there are no data races, but may still be race conditions, even with a language of complete sequential consistence.

On the other hand, the processor memory model can be stricter (or less relaxed, or at higher level), e.g., implementing sequential consistency as early-days processor did. Then all memory operations are ordered, and no data race exists for any languages running in the processor.

4. Conclusion

Back to the original question, IMHO it is fine to define data race as a special case of race condition, and race condition at one level may become data race at a higher level. It depends on the nature of problem formulation, and where to draw the boundary between undefined behavior and well-defined but indeterminate behavior. Just the current convention defines the boundary at language-processor interface, does not necessarily mean that is always and must be the case; but the current convention probably best reflects the state-of-the-art interface (and wisdom) between processor architect and programming language.

Evolution of RNN network designs

2018-04-18T11:50:00.001-07:00

The following is my answer to a question in stackexchange: why LSTM uses two paths (from current time step to the next) well GRU uses only one.

To understand the intuition behind, one should probably know the evolution of the algorithms.

1. RNN

An RNN network initially wants to model the sequence of inputs. By sharing the network parameters between the individual inputs, and using the output of previous input as part of the input for next computation, the sequence state can be accumulated along with the sequence, virtually achieving a variable-depth network.

For this purpose, the most straightforward network design is to build a path between the hidden nodes (i.e., from the output of the hidden node to the input of it in the subsequent time-step).

Here, both

f

and

g

are parameters, hence single path suffices. This design is powerful enough to encode all the history information. But it has a problem of vanishing or exploding gradient.

2. Leaky Unit

One way among others to overcome the problem is to use the leaky unit that provides linear self-connection in following way:

c t = f \cdot c t - 1 + (1 - f) \cdot x ̂ t

Now since

c_{t} = f^{n} \cdot c_{t - n} + . . .

, with f being near one, the far distant history has no problem to be passed along. When f being near zero, the history can be quickly forgotten.

Leaky unit is a clever design. Then the problem is how to decide the value of f. It can be a constant, or a parameter, or a function of the history info. (It does not make much sense for f to be a function of the input.) When we use a function for f, the function is called a gating function. Depending on the choice of f, leaky unit can be single or two paths.

3. LSTM

The idea of using a gate function of the history info requires introducing another path between steps (i.e., from the output of hidden node to the input of the gating function.) So you have,

f t = σ (h t - 1, x t)

And you know this is LSTM, if you have,

c t h t = f t \cdot c t - 1 + i t \cdot x ̂ t = o t \cdot c t . . .

With gating functions, the network can control very well how long and how short the memory should be. LSTM uses the output

h_{t - 1}

to gate not only the hidden node connection, but also the input and, especially the output from $c_{t}$ to $h_{t}$ , which makes the two paths hard to be merged into one. Then

h_{t}

is supposed to encode best the information for both long and short memory.

4. GRU

As such, you definitely can use the cell state to compute the gating functions, but the original setup is more straightforward - with clean separation between gating and cell state. Inspired by the idea, one can come up with different designs.

GRU is then designed to use single path, by removing the output gating and output the cell state directly. Then the cell state can be used by the subsequent step for both state update and gating function computation. You can interpret it differently anyway. For example, the reset gate in GRU can be considered as a shifted output gate of LSTM: it shifts from the output of this step (in LSTM) to the input of next step (in GRU).

c t f t = f t \cdot c t - 1 + (1 - f t) \cdot x ̂ t = σ (c t - 1, x t) . . .

A figure is better than thousand words.

You can further simplify GRU with fewer gates, for example, with the same update gate for reset gate. The point is, from the viewpoint of "path", there is no essential difference no matter if it is one or two.

Managed Runtime Technology: General Introduction

2012-10-18T23:39:00.001-07:00

I gave a presentation to a software group on runtime technology: Managed Runtime Technology: General Introduction.[1] The main contents are:

Evolution of Virtual Machines and Runtime Systems
Modern Programming and Managed Runtime Systems
Differences between a managed runtime system and a traditional runtime system
Overview of Execution Engine (EE) and Memory Management (MM)

[1] http://people.apache.org/~xli/presentations/managed-runtime-introduction.pdf

Android overview - from a system design perspective

2012-10-18T23:32:00.003-07:00

I gave a presentation to a research lab on Android design: Android overview - from a system design perspective [1]. The summary bullets are:

Smartphone OS has to be open and elegant

Comprehensive and consistent API
Service oriented framework to back the API specification
App components are wired into the framework
HAL to hide hardware differences
UID/process based security support to apps - leverage the mature model
Traditional OS kernel for platform management

[1] http://people.apache.org/~xli/presentations/Android-design-overview.pdf

Comparison and Analysis of the Three Programming Models in Google Android

2012-07-03T01:18:00.000-07:00

Smartphone and tablet are becoming more like personal computer. It is important to understand the pros and cons of different programming models in these kinds of mobile devices. In order to fully understand their implications to the platform architecture and their technical correlation, we develop variants of the same representative Android application in all of the three sets of APIs provided in Google Android, i.e., the Java SDK, C++ NDK, and the new powerful Renderscript. Based on the same application, we conduct detailed apple-to-apple analysis, with focus on hands-on programming convenience, runtime behavior, and technical correlation of the different programming models. We find that the current programming models provided in Android can be improved. We propose a unified solution that we expect to satisfy the requirement of both programmability and performance as a programming model, and also maintain the applications’ security and portability when deployed in mobile devices.

The paper can be found at http://people.apache.org/~xli/papers/applc2012-android-programming-models.pdf [1]

[1] Xi Qian, Guangyu Zhu, Xiao-Feng Li, Comparison and Analysis of the Three Programming Models in Google Android, First Asia-Pacific Programming Languages and Compilers Workshop (APPLC), in conjunction with PLDI 2012, Beijing, China, June 14, 2012

Quantify and optimize the user experience of Google Android

2011-11-23T18:24:00.000-08:00

Traditional performance evaluation methodology has been quite mature and somehow sophisticated with hardware support in micro-architecture and lots of tools available. But the evaluation methodology for user experience is not yet well established. The root causes are two-fold:

Before mobile client prevails recently, the user experience of a computing system was basically just GUI + performance. When it came to user experience, people thought mostly about human-computer-interface with various media approaches such as speech, virtual reality etc. that had never become the mainstream or actual reality.
The traditional user experience research has been mostly focused on user subjective perception. So the academia on this front spent their efforts in perceptual model, eye-tracking, polls, sweating, etc. that are not directly useful to software engineering.

The community did not realize that, there have been already enough room for the industry to software engineering the user experience - based on the established industry principles in responsiveness, smoothness, coherence, accuracy/fuzziness, etc. I have recently prepared a series of slide decks on the software engineering methodology of "user experience optimization" with Google Android:

Overall methodology of quantify and optimize User Interactions with Android devices.
The Android Workload Suite used for Android user interactions evaluation.
The Android UXtune toolkit used to assist the analysis and optimization of Android user interactions.

The content is available in my homepage at Apache: http://people.apache.org/~xli/.

Transactional memory regarded not good programming model

2009-08-04T22:26:00.000-07:00

After I posted my blog entry Can "transactional memory" be a new programming model? two years ago, I have been watching closely on the opinions from academia on TM as a programming model. Recently I read two papers on the same topic, one from Bohem [2] arguing that TM should only be an implementation technique, the other from C. J. Rossbach, et al [3] demonstrated with experiments that programming with TM is not necessarily easier than with coarse-grained locks.

[1] Can "transactional memory " be a new programming model? http://xiao-feng.blogspot.com/2007/04/can-transactional-memory-be-new.html
[2] Hans-J. Boehm, Transactional Memory Should Be an Implementation Technique, Not a Programming Interface, HotPar, Berkeley, CA. March 30, 2009
[3] Christopher J. Rossbach, Owen S. Hofmann, and Emmett Witchel, Is Transactional Programming Actually Easier? 8th Annual Workshop on Duplicating, Deconstructing, and Debunking (WDDD), Austin, Texas June 2009

A quick guide on Tick - the Harmony concurrent GC

2009-04-14T19:15:00.000-07:00

I've written a slide deck on Tick [1], the Harmony concurrent GC we developed. Tick has been there in Harmony for about one year, now I got some time to put down its design and implementation. I do not expect people can immediately understand all the internals of Tick after reading the guide, but it should help those who want to dive into Tick or those who want to write their own concurrent GC. The immediate target of this document to help the GSoC2009 project with Tick.

Concurrent GC is a super-set of stop-the-world GC, in my opinion. It meets all the challenges in a STW GC and many beyond. The key challenges in my mind (based on my experience with Tick) are:

1. The interaction between mutators and collectors. Here in my slides I refer as the phase transition control. The idea was not so clear at the beginning of Tick development, but we then realized it is simply boiled down into a central state-machine control by mutator.

2. The termination control. It is easy to understand that to terminate the marking process, we need guarantee the global root set, collector local mark stacks, mutator local remember sets, and global remember set all be empty. But there are two subtleties in real implementations. a) the checks must be in order; b) concurrent access to mutator local remset by mutator and collector.

3. The collection triggering scheduler. It can not collect too early so as to waste the system resource when there are lots of free memory; also it can not be too late to become virtually STW collection, hence losing all the Tick design target. A proper triggering scheduler should consider both space and timing issues.

4. Keep collection overhead small. Concurrent GC wants to achieve short pause time, the expense is to lower the overall system throughput. It is a challenge to balance the design between pause time and system throughput. For example, to improve the performance, multiple collectors can be deployed in parallel.

I would like to spend more time to document the internals of Tick. Stay tuned.

[1] http://people.apache.org/~xli/presentations/harmony_tick_concurrent_gc.pdf

Two Harmony project proposals for GSoC 2009

2009-04-01T05:25:00.000-07:00

Check link below [1] for application process. For Harmony projects, it is required to discuss the proposal in the mailing list dev@harmony.apache.org .

1. Modularize Harmony JIT by separating JET as a standalone JIT compiler

So far the JIT component (called Jitrino) of Harmony has virtually two JIT implementations: JET and OPT. Jitrino.JET is a fast but non-optimizing JIT, and Jitrino.OPT is an optimizing JIT. The code base of JET and OPT shares lots of code hence they are mixed in one module. This is undesirable for situations where people need only JET, for fast compilation, for small footprint. This project proposes to create a standalone JET-based JIT module for Harmony. It does not require to remove JET from Jitrino, but to create a new JIT module with JET. This project is also a very good exercise to examine the JIT modularity design, the interface between JIT and other components, the interaction between multiple co-existing JIT modules.

2. Implement WeakReference support in Harmony concurrent GC

Harmony already has a concurrent GC (called Tick, with three concurrent GC algorithms). It runs well with standard benchmarks. The only remaining unfinished feature is WeakReference support . Weakly referenced object (i.e., referent) is accessed through get() interface. That means, get() operation can make a weakly reachable referent strongly reachable. During concurrent collection, the system must monitor the get() operation to catch this change of reachability, otherwise the referent could be reclaimed. This project also includes to integrate the WeakReference processing with Finalization process. Other optimizations in Tick are also desirable, such as to reduce the amount of floating garbage.

[1] http://wiki.apache.org/general/SummerOfCode2009

Thread mapping: 1:1 vs M:N

2008-08-23T06:11:00.000-07:00

This is an old essay I wrote about 7 years ago, when I was investigating what kind of thread mapping is better for a runtime system (especially the ORP [1] JVM I was working on). It is worth to put it here as one of the series of blog articles. I edited it a little bit to incorporate some new information.

I discussed the concept of thread mapping, 1:1 or M:N, in blog entry: What is a thread. [2] M:N thread binding is "conceivably" better than 1:1 because of cheap context switch. It is believed to be cheap because it does not need to involve OS kernel operations for user level thread switch. So an M:N threading normally has following setting: there are processor number pf kernel threads; unlimited number of user threads multiplexes over the kernel threads. Since kernel context switches are expensive, it's expected there are no kernel thread context switches at all except OS kernel process scheduling. All the context switches are expected to happen only in the user-level scheduler. As a comparison, in 1:1 threading all the context switches happen in kernel.

1. Context Switch
But this conception is not necessarily true. The kernel thread context switch has no more operations than user thread context switch, except that, kernel switch requires to trap into the kernel. So the only additional overhead is the system call. But if we study the real nature of context switch, we can see the truth is not so obvious.

Scenario 1: Blocking operations
Context switches mostly happen when a thread is doing some I/O operations and blocks in kernel. Since it blocks in kernel, it's natural to schedule on-site by the kernel to context switch to another kernel thread; this is the approach of 1:1 binding. The trapping overhead is there already.

In M:N mapping, there are two ways to continue another user thread in the same kernel thread context:

1. Scheduler activation implemented in kernel. When a blocking happens, kernel can vector the event to user scheduler via an upcall. Then the user scheduler can determine which user thread to schedule next. But this is cumbersome because it requires one upcall which is an extra overhead compared to the kernel scheduling; and the user scheduler is not necessarily as efficient as kernel scheduler due to the immaturity compared to the OS kernel shceudler;

2. Non-blocking system call. If OS doesn't provide scheduler activation, the only way to continue a user thread when another blocks is to use non-blocking system call. That is, whenever a thread is calling a possibly blocking syscall, it first polls it to check if it is going to block. If it is, the user scheduler will schedule another thread, and polls again in next scheduling cycle. This solution seems ok, but the polling itself is a system call, which involves everything in a blocking system call except the context switch. So user-level scheduling consists of a non-blocking system call + user thread context switch. The cost is equal to a blocking system call + kernel context switch.

Although it is no better, this is the ideal case of user-level scheduling. In common cases, the non-blocking simulation of blocking syscall involves much more than stated here. It usually requires a syscall to save the current blocking status of the file descriptor and another syscall to restore it, before and after the polling respectively. And the next scheduling cycle may repeat these operations again to check if the blocking condition is resolved. As a comparison, kernel scheduling is much simpler and cleaner, where the blocking thread is simply put into sleep, and then waken up till the blocking condition is known resolved.

The reason for this complexity of non-blocking syscall simulation is easy to understand: user scheduler knows nothing about kernel status. It has to use syscall to figure out the blocking status. Better asynchronous I/O support can help to solve the problem, where the user scheduler is notified by the kernel for the async processing, and a completion notification is sent by the kernel upon the processing is finished. This kind of interaction between user threads and kernel is implemented in Windows NT4.0 and Solaris10 and their later as I/O Completion Port.

Scenario 2: Synchronization
Another scenario of thread blocking is caused by the synchronizations among threads. This is the case where all the scheduling can be done at user level, since the synchronization implementation could all be in the user runtime. If the synchronization usage is extensive in the application and the contention is intensive, user level scheduling can bring some performance advantage. But again, it is not that simple.

1. Normally, in the application domain, a highly contending application is unusual and considered sub-optimal in its design. For example, the highly contended SPECpbob was substituted by rarely contended SPECjbb2000. (Note, lots of synchronization operations do not mean lots of contention. They are completely two different issues.) Actually, some source said the thread blockings caused by synchronization take only very minor ratio in all the blockings (< 5%).

2. Even it is good to use user-level scheduling for thread synchronization blocking, a threading library has to deal with process level mutex, which makes the thread synchronization implementation complicated and less efficient as expected. (Futexes helped here.)

This is the scenario supporting the idea of M:N mapping; well the benefits are not convincing enough.

Scenario 3: Uncaught exceptions
There are lots of situations where thread blockings are hard to be simulated with non-blocking operations, e.g. page fault. Page fault happens in kernel, and is hard to predict. Neither scheduler activation nor a non-blocking wrapper can work around it easily except just be blocked in kernel. This limits the concurrency achievable.

As stated earlier, the problem is due to the limited information known at user level. Lots of things like processor affinity, intelligent scheduling for hyperthreads or NUMA optimizations, scheduling based on system load outside of the process, etc. are almost impossible. Scheduler activation can help but not a complete solution.

Moreover, a problem is, all of the scheduling supports are always existing in kernel scheduler. To achieve the scheduling capability at user-level, those supports have to be duplicated at user-level.

2. Cooperative user threads
Even if the user-level scheduling is effective, is it really a good thing? People may think that user scheduler is better because the user threads are cooperative, and they guess that "cooperative" sounds like a better behavior pattern than preemptive.

Number of scheduling units
It is easy to believe that best performance is normally achieved when there are equal number of processors and scheduling units (kernel threads). User threads sharing a kernel thread are bound to a processor, and do not need preemptiveness. But this problem is, in nowadays operating system, there are always many running processes at the same time. So even if user threads are cooperative, the kernel thread containing them is already preempted from time to time.

Thread cooperation
It could really be a good thing if user threads are really cooperative without much extra cost. Unfortunately, since a non-preemptive scheduler depends on application behavior for scheduling, it normally requires the application be aware of the scheduling and yields voluntarily; Otherwise it is easy to be deadlocked or starved. But this awareness is burdensome to the developer and usually does not exist at all. The threading runtime can not always be able to insert yields properly.

Different from many people's expectation, the preemptive scheduling is more intuitive to application developer than the cooperative one. (The situation is different from the mechanism of stop-the-world for GC in runtime system. I will discuss it later).

More importantly, preemption might be necessary for any environment where real-time or soft real-time responsiveness is needed, both for rouge-thread cases and for cases where the processor resource has to be given up due to a higher priority thread needing it.

Resource sharing
An advantage of user threads in one kernel thread might be that, the threads can share everything of the system resource, esp. including the page table and TLB slots, which could lead to better performance due to less misses. Well, the situation is, kernel threads can share these resources too. (This feature needs architectural support. AFAIK, Linux does pretty good on IA32 processor.)

Thread creation/cancellation
One important claimed advantage of user thread is the creation and cancellation cost of user thread is low. This is mostly true if the thread runtime is implemented correctly. But its importance is largely reduced due to its user thread nature. Being not a separate system scheduling unit, it is unclear what is the intention to create tons of user threads that are only running within one kernel thread container. They will compete for the precious time slice of the single kernel thread.

In reality, most systems do not create or cancel lots of threads in short time. In cases when lots of threads are needed, the applications may want to reduce the creation overhead with thread pooling. Lots of threads creation doesn't necessarily mean lots of concurrency. They may just start and finish frequently. And even if there are lots of concurrency, it's hard to be leveraged because it has to be implemented by scheduling efficiency, which is not so good for user-level threading as we discussed above.

3. Obvious disadvantages
In spite of the suspicious "advantages" of M:N threading discussed above, user-level scheduler has some obvious disadvantages.

Duplication of the schedulers
M:N requires two schedulers which basically do same work, one at user level and one in kernel. This is undesirable. It requires frequent data communications between kernel and user space for scheduling information transference.

One subtler point is, the duplication takes more space in both Dcache and Icache for scheduling than a single scheduler. It is highly undesirable if cache misses are caused by the schedulers but the application, because a L2 cache miss could be more expensive than a kernel thread switch. Then the additional scheduler might become a trouble maker! In this case, to save kernel trappings does not justify a user-scheduler, which is more truen when the processors are providing faster and faster kernel trapping execution.

Thread local data maintenance
M:N has to maintain thread specific data, which are already provided by kernel for kernel thread, such as the TLS data, error number. To provide the same feature for user threads is not straightforward, because, for example, the error number is returned for system call failure and supported by kernel. User-level support degrades system performance and increases system complexity.

System info oblivious
Kernel scheduler is close to underlying platform and architecture. It can take advantage of their features. This is difficult for user thread library because it's a layer at user level. User threads are second-order entities in the system. If a kernel thread uses a GDT slot for TLS data, a user thread perhaps can only use an LDT slot for TLS data. With increasingly more supports available from the new processors for threading/scheduling (Hyperthreading, NUMA, many-core), the second order nature seriously limits the ability of M:N threading.

This is what I thought on the thread mapping issues. It is a long article, and thanks for reaching here. There are some contents in the original essay that I do not include here. Those are some considerations on the threading needs in a runtime system, such as whether we need suspend/resume API, better inter-thread signaling, etc. I might discuss them in future.

[1] Open Runtime Platform, http://orp.sourceforge.net
[2] What is a thread? http://xiao-feng.blogspot.com/2008/08/what-is-thread.html

What is thread escape analysis?

2008-08-17T06:39:00.000-07:00

In last blog entry, I discussed "thread local data" [1]. I mentioned that if some data are known to be thread local, some optimizations can be applied to the application manually or automatically.

One optimization is, we can put the thread local data into registers. Register is thread local anyway, so the semantics are kept. Register access is much faster than memory access, so this optimization can improve the performance. In compiler, this is done with register allocation, scalar replacement (i.e., use scalars to replace non-scalar data fields, such as array or class), etc.

Thread local data can be be put on runtime stack as well. Stack is also in memory as heap space, but stack has an advantage that data on it are freed automatically when the stack frame is cleared (when a method returns). In this case, the data actually are not only thread local, but also method local, which is more strict condition than thread local. (some people claim that stack-allocated data have better access locality, but my experience did not confirm that.)

Even if the thread local data can not be put into register or stack, there are still optimizations applicable. For example, garbage in thread local data can be recycled without stopping other threads for root enumeration. (Well, technique still needed to enumerate roots in global variables).

No matter where they are, all the thread local data have an important optimizing opportunity: They do not need any locking operations for mutual exclusive access. This is important because locking operation usually is very expensive.

Then the question is how the compiler can identify some data are thread local automatically. This is called escape analysis. The compiler analyzes the source code to find if the reference of an object is passed to other thread. This analysis has to be conservative to guarantee the correctness. For example, usually when a reference is written to a global variable, it is considered escaping, because the global variable could be read be other thread.

Escape analysis can also be conducted at runtime without compiler static analysis. That is, when an object is created, it is set thread local to its creating thread. Then the system monitors all the accesses to this object. If it detects any other thread tries to access the object, the system then marks the object to be escaping. This technique is called escape detection instead of escape analysis sometimes. Some of the thread local data optimizations can still be applied to the dynamically detected thread local data, but some static optimizations might not be suitable.

"Thread local" actually is not necessarily restricted to "accesses". Many operations can be the property of "thread local". For example, if an object is only locked by one thread, it is called thread local lock. Thread local lock can be eliminated, even the object itself is accessed by multiple threads. So thread local data is more restrictive than thread local object.

[1] What is thread local data? http://xiao-feng.blogspot.com/2008/08/what-is-thread-local-data.html

What is thread local data?

2008-08-17T03:03:00.000-07:00

Thread local data refer to those data owned by one thread. Normally "owned" here means the data are only accessed by that thread. Sometimes, it is also called thread-private data, thread-specific data, thread-local storage, etc. Thread local data are interesting because the property of being owned by a single thread can be utilized to improve the application's performance or the program design.

There are basically three kinds of thread local data. They are:

Registers. The registers can only be accessed by single thread (or process, depending on the context) normally. (Yes, some processors have global registers, and even the common registers can be accessed with tricks, but those are out of the scope of my discussion here.)
Stack. This is known to be associated with a specific thread. Sometimes a thread is identified by its stack.
Thread-local heap. Within the shared heap space, a region can be owned by a single thread.

Registers and stack are system-supported thread local data, as we discussed in "What is a thread?" [1]. They cannot be accessed by other threads by design.

Thread-local heap is different. It is supported not by design, but by convention, because heap is sharable to all threads. A heap region is local to one thread means either of the following two situations:
1. The region is not accessible to other threads. The region can be protected by virtual memory mechanism or whatever technique to enforce the convention, or it is simply a rule complied by all the threads.
2. The region is accessible to all threads, but only one thread actually accesses it (up to the moment). This property of the data is called "non-escape", i.e., they are confined to a single thread's territory. Once the data are accessed by other thread, it becomes "escape". (We will discuss "escape" and "escape analysis" later.)

Different from the registers or the stack, there is no default system support for thread local heap. Programmers need some way to define, to find, and to use thread local heap. Since every thread can claim thread local regions, they should be able to find its own regions with same API like my_region(). The solution is, we can put the region pointer into the same register or the same stack slot of different threads. Since the registers and the stack are system-supported thread local data, even using the same register name or stack slot, different threads will access their own registers or stack slots. So they can get their own region pointers from the same API my_region(). This is how the current thread libraries implement "thread local storage" or "thread specific data".

[1] What is a Thread? http://xiao-feng.blogspot.com/2008/08/what-is-thread.html

What is a thread?

2008-08-17T02:22:00.001-07:00

Some of my friends are confused by all kinds of concepts around thread, such as system thread, kernel thread, native thread, user-level thread, application thread, java thread, software thread, hardware thread, simultaneous multithread (SMT), hyperthread (HT), helper thread, etc, etc.

So what a thread is?

A thread is nothing but a control flow of execution. It is an concept only valid in control-flow machine, because only then is there control flow. Then what is control flow? Or in other words, how to represent a control flow. In my opinion, only two entities are essential to represent a control flow. They are the program counter and the stack.

Program counter points to next instruction to execute. Stack stores the temporary execution result. To be a meaningful stack, a stack pointer is needed pointing to the next location to store the execution result.

Program counter and the stack can uniquely identify a control flow of an execution. They cannot be shared with other threads (except for some extreme cases). All of other computing resources can be shared between threads, such as heap, code, processor, etc. Hence, program counter and the stack are called the thread context.

That means, if a system provides threading support, it should at least provide a way to distinct one thread context from another, be it in software, hardware or hybrid. If processor hardware provides thread context support, it is hardware thread. Different hardware threads can share same processor pipeline (SMT) or use different pipelines, depending on the design. HT is an implementation of SMT. Any control-flow processor must provide at least one thread context; otherwise, there would be no control flow.

If the processor has only one thread context, threading support still can be provided by software. That is, multiple software threads can multiplex over the same thread context. When a software thread is scheduled to run, its context is loaded from the memory into the hardware thread context. If it is scheduled off the processor, its context is saved into the memory.

Software thread design has an implication. Since the thread context loading/storing (or switch) is conducted by software, it requires the software thread design to guarantee that there are chances to conduct the switch operation (or thread scheduling). An easy way to implement is to leverage hardware interrupt. Once the software receives a hardware interrupt (timer or whatever), it executes the interrupt handler and within the handler, it schedules the threads.

Sometimes, the timer is too long to wait. For example, when a thread is sleeping, before a timer handler is executed, no other thread can be scheduled. This is not desirable. A straightforward solution is, if a thread wants to sleep, it always invokes the scheduler, then the scheduler can switch on another thread.

Now that multiple software threads can share the same hardware context, it is not hard to think that, a software thread context can also be multiplexed by another level of multiple software threads. This is true. So conceptually, software threads can be built with infinite levels, every higher level threads multiplex the contexts of its next level threads.

Also a natural corollary is, a thread is only a thread in your level of discussion. It could contain multiple threads in a higher-level of discussion. Well, although this is true, people do not really build many levels of software threading libraries. Usually there are only two levels, one level shares the hardware context, and the other level shares the software context.

This is reasonable. The most important reason is, all the software threads in one level are treated as a single thread in the next level, so they are scheduled as one thread in the next level. That means, they total only share the time slice of a single thread in the next level. If the next level thread is scheduled off the processor, none of them can be continuing. This is inconvenient.

More inconvenient is, sometimes, only one thread wants to sleep, but all the other threads have to sleep with it together, because they are treated as a single thread in the next level scheduler who sees the sleep operation. This issue can be partially solved with non-blocking sleep. That is, when a thread wants to sleep, it does not really sleep in the sense of the next level scheduler. It only sleeps in the eyes of its level's scheduler. This scheduler will schedule another thread at the same level. From the next-level thread scheduler's point of view, the thread is just continuing without sleep at all. In threading terminology, all the blocking operations (such as sleeping) in one level are implemented as non-blocking in its next level. (Well, this requires the system support for non-blocking operations, such as socket snooping, etc.)

Only operating system kernel really takes control of the execution engine (i.e., the processor or the pipeline). So the time slice concept is only really meaningful to the kernel. That means, only the threading at kernel level can really manipulate all the resources. Higher levels of software threads should always try to leverage the support of kernel threading. This is the fundamental reason why we want at most one additional level of threading above kernel threads.

Kernel threads are exposed to user applications through threading APIs. They are called native threads by the applications, such as NPTL or Linuxthreads in Linux, and WinThreads in Windows. The threading library implemented on top of native threads is called user-level threading. For the inconvenience we discussed above, not so many software today employ user-level threads.

User-level threads have its own advantages in certain scenarios. For example, multiple user threads never run in parallel on multiple processors/cores, because they are actually just single thread from OS' point of view.

Java thread is thread in another dimension. It is actually a language concept. It can implemented in any of threading mechanisms discussed above. Previously before Java, all the threading supports are kind of independent of programming languages. They are just system supports, and any languages can utilize if they want. Java takes a different approach that, it builds threading concept in its language. This is important for program semantic correctness. Hans had a PLDI paper with title "Threads Cannot be Implemented as a Library" [1]. And people are trying to introduce threading as a language construct into more languages.

[1] Hans Boehm, Threads Cannot be Implemented as a Library, www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf

Quick hacking guide for Harmony GC development

2008-04-09T08:09:00.000-07:00

I just wrote an introduction on Harmony GC source code. It serves as a quick hacking guide. It's subject to changes based on the comments or questions received. Hope this is useful for the students who are applying for GSoC projects related to GC.

The doc is at http://people.apache.org/~xli/presentations/harmony_gc_source.pdf

Parallel Garbage Collection

2008-04-04T02:29:00.000-07:00

Recently, I gave a talk on "Parallel Garbage Collection"[1] (2008-03-28) in Shanghai Many-Core Workshop 2008, arranged by gelato.org.

The presentation discussed some common issues in STW parallel GC algorithms:

Traversal of object connection graph
Order of object copying
Phases of heap compaction
Marking of live object

I also briefly mentioned several threading issues with garbage collection.

Thread local objects
Finalizer processing
Concurrent collection
GC and transactional memory

[1]http://people.apache.org/~xli/presentations/parallel_garbage_collection.pdf

Harmony project proposals for Google Summer of Code 2008

2008-03-23T18:45:00.001-07:00

Google Summer of Code 2008 is open for student applications. Harmony has following proposals together with other ASF projects:

======================================
Subject ID: harmony-gc-1

Title: Implement the "Compressor" GC proposed by Kermany and Petrank

Keywords: Java, memory management, GC

Description: The Compressor garbage collector [1] is a compacting GC that leverages virtual memory support in underlying OS. It compacts the heap in two passes.
[1] Haim Kermany, Erez Petrank: The Compressor: concurrent, incremental, and parallel compaction. PLDI 2006.

Possible Mentors: Xiao-Feng Li (xiaofeng.li (a) gmail com)

Status: Unassigned

======================================
Subject ID: harmony-gc-2

Title: Implement the "Mapping Collector" proposed by Wegiel and Krintz

Keywords: Java, memory management, GC

Description: The Mapping Collector [1] utilizes the virtual memory support in a novel way so that it can compact the heap without moving the objects or fixing the references.
[1] Michal Wegiel and Chandra Krintz, The Mapping Collector: Virtual Memory Support for Generational, Parallel, and Concurrent Compaction, ASPLOS 2008.

Possible Mentors: Xiao-Feng Li (xiaofeng.li (a) gmail com)

Status: Unassigned

======================================
Subject ID: harmony-gc-3

Title: Write a graphical front-end for Harmony memory management

Keywords:Java, memory management, GC

Description: Harmony runtime needs a graphic front-end visualizing the memory management activities and the runtime status. It can be standalone or better an Eclipse plugin. It can be online display of the runtime execution, or offline processing of the log.

Possible Mentors: Xiao-Feng Li (xiaofeng.li (a) gmail com)

Status: Unassigned

======================================
Subject ID: harmony-gc-4

Title: Unify the native memory management of Harmony DRLVM

Keywords: Java, virtual machine, memory management, GC

Description: DRLVM uses inconsistent APIs for native memory management, such as APR or malloc or mmap. It is desirable to have a unified API for native memory management. Hopefully the runtime native memory usage can be managed with a global view and then optimized. This layer could be extended to provide the API for Java heap native management as well.

Possible Mentors: Xiao-Feng Li (xiaofeng.li (a) gmail com)
Andrey Yakushev (andrey.yakushev (a) gmail com )

Status: Unassigned

======================================
Subject ID: harmony-gc-5

Title: Build a garbage collector for C/C++ programs on the top of Harmony

Keywords: C, C++, memory management, GC

Description: One may notice a lack of open source effective parallel GC implementation for C/C++ programs. For example, Parrot (Perl 6) community expressed an [WWW] interest in attaching our GC to their code base. If numbers would show some benefit, we might get other adopters of our code base. Successful completion of GC library on the top of Harmony would teach a person in refactoring skills and give a good background in garbage collection.

Possible Mentors: Alexei Fedotov; Xiao-Feng Li (xiaofeng.li (a) gmail com)

Status: Unassigned

======================================
Subject ID: harmony-tools-1

Title: Implement "Bundle Tool", a tool to make binary snapshots of Java applications with Harmony

Keywords: Java, tools

Description: There is no simple way for Harmony users to define the list of needed classes, jars and native libraries for their applications. Create a tool that creates a Harmony package with the classes and native libraries used by specific application or work flow. First of all this application should collect data from one or multiple application runs and then create a Harmony bundle without unneeded classes and native code.

Possible Mentors: Egor Pasko; Mark Hindess

Status: Unassigned

======================================
Subject ID: harmony-tools-2

Title: Implement a Java developer's command line tool

Keywords: Java, tools

Description: Harmony is missing several of the tools that ship with the JDK, including jar, jconsole, javaws and policytool. For this task you would implement one of these tools, either in Java or C/C++ if preferred.

Possible Mentors: Sian January; Mark Hindess

Status: Unassigned

======================================
Subject ID: harmony-vm-1

Title: Support invokedynamic bytecode instruction in Harmony VM and JIT

Keywords: C++, java, virtual machine, JIT, bytecode, dynamic languages

Description: Support the [WWW] invokedynamic instruction i.e. the ideas of [WWW] JSR 292 draft. And implement basic support for a dynamic language like Python, Ruby, JavaScript as a proof of concept. We want this language to have dynamic typing, reasonable user base, usable standard library, a set of compatibility tests. Students are free to choose the actual dynamic language. We will discuss the reasoning behind the choice. The code involved is C (VM part) C++ (JIT) and probably some class library part in Java. The task is rather challenging for the summer, hence, will require a lot of interaction with the team on the tricky details. Lots of fun guaranteed.

Possible Mentors: Egor Pasko

Status: Unassigned

======================================
Subject ID: harmony-vm-2

Title: Integrate Harmony and Jikes RVM

Keywords: Java, virtual machine, VM

Description: [WWW] Jikes RVM is a research virtual machine that has been a test bed for many JVM and GC developments. This project will look to integrate the Harmony class libraries with Jikes RVM. This will require work on the VM interfaces (the Jikes RVM is a Java-in-Java VM meaning that current VM interfaces are written in Java rather than native code) as well as exploring how Jikes RVM can be integrated with Harmony's threading and other runtime models.

Possible Mentors: Ian Rogers; Tim Ellison (t.p.ellison (a) gmail com)

Status: Unassigned

======================================
Subject ID: harmony-jit-1

Title: Refactor Java Bytecode Translator in Harmony JIT

Keywords: C++, JIT, bytecode, compilers, Java

Description: The optimizing JIT (Jitrino.OPT) parses Java bytecode on early stages of method compilation to produce Internal Representation to allow further stages to optimize it. This code is well-tested, but not easy to extend (for example, not easy to teach JIT to understand new types of instructions) The major inconvenience is that translator makes things too complicated by trying to optimize on the fly. The task is to refactor the Java-Bytecode-Translator in the Jitrino.OPT to make the code cleaner and simplify the data structures used. Move optimization to a separate stage. Take care of correctly mapping line number info from bytecode into JIT instructions. Code is C++, but not a tricky style. The student will get an in-depth knowledge of Java bytecode, overall knowledge of just-in-time compilation techniques.

Possible Mentors: Egor Pasko

Status: Unassigned

======================================
Subject ID: harmony-demo-1

Title: Make [WWW] FreeCol game playable on Harmony

Keywords: Java, games, graphics

Description: For someone who is interested in a graphical user interface development, enabling one of the most popular strategic games may be an interesting task. Since client API development is not finished, the one who would choose this task might learn designing of areas related to image processing, code development, bug fixing and refactoring. See for [WWW] details on the current status of the project. BTW, you may want to replace [WWW] FreeCol enabling with enabling of your favorite application, and this is welcome.

Possible Mentors: Alexei Fedotov

Status: Unassigned

Parallel Compacting Garbage Collectors and their phases

2008-03-23T17:33:00.000-07:00

I discussed several best known compacting GC sequential algorithm [1]. Now I'd like to focus on the phases of parallel compactors.

1. Parallel LISP2 Sliding Compactor

It has four main phases (or heap passes), as shown below.

The key to parallel LISP2 Compactor is to build a dependence list between a target block and its source blocks whose live objects are copied to the target block. The dependence list is built in the first phase when target address is computed.

LISP2 Compactor stores target address in object header. It has to update the references before moving objects. And it has to put the reference-fixing phase between object-repointing and object-moving phases.

2. IBM's Moving Compactor
It has three heap passes [2].

The key of Moving Compactor is, it uses an offset table, which stores the target address of the live objects. This avoids the overwriting of the target address info by a moved object, so that the references in heap can be updated any time (in any phase). Here it fixes the references after object moving phase.

A note added on 2009-1-15: Recently (2009-1-12), one of the authors of this compactor, Diab Abuaiadh, told me the following in his email: "It is simple to convert the algorithm to a one (heap) pass compaction by delaying moving the objects from first phase to second phase. This involves minor changes to the original algorithm. This change reduces the pause time while it has no negative impact on the locality of reference". Diab did not disclose the details about the "minor changes" required. It is unknown how similar it is to the STW Compactor of Compressor described below.

3. STW Compactor of Compressor
The Stop-the-world compactor of Compressor [3] has 2 heap passes and 1 mark-bit table pass, hence having 2.5 phases if we consider the mark table traversal much more light-weighted.

The key of Compressor is that it computes object target address without traversing the heap; instead, it goes through a separate mark table, which encodes the location and size of live objects.

Compressor combines the object-moving and reference-fixing phases into one. This is impossible in IBM's Moving compactor, because there the target address was not ready for all live object during object-moving.

Sliding Compactor and Moving Compactor do not need the separate mark-bit table.

Compressor is an improvement by combining the Sliding Compactor and Moving Compactor. Compared to Sliding Compactor, Compressor contracts the Object-repointing phase into a mark-bit table traversal by employing the mark-bit table. It writes the target address in an offset table. Then it can combine the object-moving and reference-fixing phases into one. So algorithm-wise, Compressor is similar to Sliding Compactor -- but optimized with two additional data structures (mark table and offset table).

4. Mapping Collector
Mapping collector optimizes the phases further [4]. It does not move objects, hence no reference-fixing either. The idea is to simply unmap the pages that hold only garbage. These pages can be found by traversing mark-bit table. So it has one heap pass for marking and a mark-bit table pass, might be considered as to have 1.5 phases.

The key of Mapping Collector is, it leverages OS's virtual memory support. It leverages a fact (or an important observation): object address is virtual address, to move a object means changing virtual address. But it is still virtual. While the goal of garbage collection is to free up the physical memory, it is good enough if we can free the memory occupied by the garbage. The only issue is, we should be able to expand the virtual space in one end of the heap to achieve a large contiguous free area. Then it attains the two goals of a compacting GC:
a) to squeeze the garbage space out of the heap; Mapping Collector implements by unmapping the pages holding garbage.
b) to get a contiguous free area; Mapping Collector implements by mapping the pages in one end of the heap.

The blog entry stops here. The last words I would put are: the phases of the compactors do not necessarily imply their performance in a linear way. There are some other factors impacting the overall achieved performance besides phases, such as space overhead.

[1] http://xiao-feng.blogspot.com/2007/04/sequential-compacting-garbage-collector.html
[2]Diab Abuaiadh, Yoav Ossia, Erez Petrank, and Uri Silbershtein. An efficient parallel heap compaction algorithm. In OOPSLA'04.
[3]Haim Kermany, Erez Petrank: The Compressor: concurrent, incremental, and parallel compaction. PLDI 2006.
[4]Michal Wegiel and Chandra Krintz, The Mapping Collector: Virtual Memory Support for Generational, Parallel, and Concurrent Compaction, ASPLOS 2008.

[Harmony GC Internal] SemiSpace garbage collector

2008-02-29T07:05:00.000-08:00

Harmony has implemented a variant of the semi-space garbage collector with dynamic from-space and to-space size so as to get the best possible performance.

The idea of the semi-space GC is to partition the space into two halves. Mutators always allocate in the from-space; when it is full, collectors copy the live objects from the from-space to the to-space, and then flip the roles of the two half spaces.

The advantage of the semi-space GC is that, it is a full copying GC, which is known to be efficient when the objects surviving ratio is low. There are basically two usage models of semi-space GC: one is to avoid the compacting collection, the other is to act as a generational collection.

To avoid the compacting collection requires to reserve to-space for copying. But it should be as small as possible to keep high heap utilization. We only need to reserve adequate to-space and leave the rest space to from-space.

To leverage the generational property requires to copy the survivors from from-space to to-space. But we do not want to copy the long-live objects back and forth between the two half-spaces many times. We should promote the long-live objects out of the semi-space generation to another mature object space.

The ideas above brought us the Harmony semi-space GC design. Below is the heap layout and minor collection illustrations.

NOS is always used for mutator allocation. Part of from-space is occupied by the survivors from last minor collection, the rest of the from-space is also used for mutator allocation. To-space is empty reserved for next minor collection. In a minor collection, the survivors of the newly allocated objects since last collection are copied to the to-space. The last-time survivors in from-space will be promoted to MOS, when they are older than a certain age. In current implementation, the age threshold is simply set to be one. That's good enough in our experiments.

When the survivors are promoted to MOS, the boundary between MOS and NOS is shifted to NOS size so as to reserve some MOS space for next time survivor promotion.

With careful design and tuning, we can give the MOS reserve space and the to-space only adequate sizes for copying accommodation. The problem is how about if the size is not enough in certain collection due to the application behavior change.

In Harmony GC, if the to-space is not enough to hold all the new survivors, they can be copied to MOS directly as the older survivors. If the MOS reserve space is not enough to hold all survivors (old or new) promoted, a fallback mechanism is used. That is, the minor collection will switch to a entire-heap compacting collection, which will compact all the live objects in heap to the low end of MOS.

Linux内核管理风格 (Linux kernel management style)

2008-02-06T23:28:00.000-08:00

（中文翻译：Xiao-Feng Li）

这个短文档介绍了Linux内核所偏爱的（或“造作的”--看你问谁了）管理风格。目的是与文档《CodingStyle》的内容在某种程度上相呼应，主要是为了避免一遍又一遍地回答[1]同样（或类似）的问题。

管理风格非常个人化，很难量化，比几条简单的关于编码风格的规定要难多了，因此这个文档与实际可能有联系，也可能没有联系。开始写时只是闹着玩的，不过也不能说它完全没用。这个只能由你自己决定了。

顺便说一句，当提到“内核管理者”时，指的是技术带头人，而不是公司里的那些传统的管理人员。如果你在你们公司里要签单、或者对你们部门的预算有点儿概念的话，那你基本上可以肯定不是内核管理者。因此这里的建议可能不一定对你有用。

首先，我建议你买一本《高度成功人士的七个习惯》，_不_要读它。烧掉它，这是一个很重要的象征性姿态。

[1] 本文档并没有真地回答什么问题，而是要让提问题的人不得不明白：我们并不知道答案是什么。

好吧，下面开讲：

第一章：决定

大家都以为是管理者在做决定，而且以为做决定很重要。以为决定越大、越难，管理者就一定越高层。这看起来很深刻也很明显，其实不一定正确。

问题的诀窍在于_避免_做决定。特别是当有人对你说“请选择(a)或(b)，我们真地需要你做出决定”时，你作为一个管理者就有麻烦了。因为你管理的人应该比你知道更多的细节，如果他们需要你来做出技术决定，你一定麻烦大了。显然你没有能力替他们做出决定。

（推论：如果你的手下不比你了解更多的细节，你一样死定了，尽管死的原因与前面完全不同。这种情况下，看起来你不适合这个管理工作，应该是_他们_来管理你的才华才对。）

因此问题的诀窍是_避免_做决定，至少避免做大的、难的决定。可以做一些小的、没有什么后果的决定，这会让你看起来象是知道你自己在做什么。所以内核管理者要做的就是把大的、难的决定转变成没人在意的小问题。

需要明白的是，大决定和小决定之间的真正区别在于：你是否可以在后来修正你的决定。任何决定都可以变成一个小决定，只要你能确保下面这条：即在你可能错了的时候（你_一定_会错的），你总能回过头将其影响消除。这样，突然之间，你变得具有两倍的管理才能：你做出了_两个_没有后果的决定--一个错误的_和_一个正确的。

而且人们甚至会认为这是真正的领袖素质（咳，狗屁，咳）。

这样，避免做决定的关键就变成了如何避免做任何不能挽回的事情。不要被堵在一个无处逃生的死胡同。死胡同里的耗子会很危险--而一个死胡同里的管理者就太可怜了。

实践证明，由于_在任何情况下_都没有人会蠢到真得让内核管理者去承担巨大的财政责任，因此Linux内核中的决定通常是很容易挽回的。既然你没有机会糟蹋掉一大笔你还不起的钱，你需要挽回的也就是一个技术决定而已；而对技术决定来说，挽回措施也相当容易：只需要告诉别人你是一个手生的笨蛋，说你很抱歉，然后去除那些你让大家在过去的一年里做的没用的东西。立刻，你一年前所做的决定就根本不是一个大决定了，因为它的影响可以被轻易地消除。

实践证明有些人对这个方法不是很适应，由于下面的两个原因：
- 承认自己是个白痴比想像的要难。我们都要维护自己的形象，到大庭广众之下说自己错了有时候的确非常困难。
- 对那些可怜的底层工程师来说，要别人告诉他们去年做的东西完全没用会有些难度。尽管实际的_工作_本身可以简单地删除掉，你却可能不可挽回地失去那个工程师的信任。记住：“不可挽回”是我们首要竭力避免的，因此你的决定最终还是成了一个大决定。

比较愉快的是，这两个问题的难度都可以被有效地降低：只要你实现承认自己不是特别明白；并在实施之前告诉大家，你的决定很初步，很有可能是错的。你应该一直保留改变主意的权利，并让大家非常_清楚_这一点。其实，在你还没有做蠢事之前承认自己愚蠢，要比做了之后要容易的多。

这样，当最终被证明是件蠢事时，人们最多也就转转眼睛，说“唉，他又犯傻了”。

这种事先承认没有把握的做法，也会让那些真正干活的人好好想想是否值得做这件事。千万记住，如果连_他们_都不能肯定，你一定不要用许诺的方法来鼓励他们，即承诺他们的工作会被加到Linux内核中。还是要让他们在启动一项大任务之前深思熟虑一下。

记住：他们会比你知道更多的细节，而且他们通常认为他们对一切相关问题都已了然于胸。这个时候，管理者最好不要再去给他们吃定心丸了，而是给他们一剂用挑剔的眼光审视任务的苦口良药。

顺便提一句，另一种避免做决定的办法是简单地嗔怪道：“我们不能两个都做吗？”并做出一副可怜相。相信我，这的确有效。如果还不清楚到底那个方法更好，他们最终一定会搞清楚的。很可能的结果是，两个小组都对结论感到失望并就此放弃。

放弃听起来似乎是个失败，但这通常是一个信号，表明两个项目都有问题，而两个小组的成员都不能下决定的原因可能就是因为他们都错了。这样你最后倒成了香饽饽，而且你还避免了又一个可能让你死菜的决定。

第二章：人

大多数人是白痴，做为管理者，你必须面对现实、和他们周旋。或许更重要的是，_他们_必须要和_你_周旋。

事实证明，虽然消除技术错误很容易，消除人性的混乱却不容易。你必须与别人的个性共处--以及与你自己的个性共处。

不过，要准备成为一个内核管理者，你最好记着不要断了自己的后路、殃及无辜、或与太多的内核开发者作对。事实证明，与人闹翻很容易，可再想和好就不容易了。因此“闹翻”立刻可以归类为“不可挽回”的行为；按照第一章，绝对应该避免。

有几条简单的规则：
(1) 不要称呼别人“蠢货” （至少不要在公开场合）
(2) 当你忘了(1)时，就学会道歉

(1)的问题是它太容易违反了。你可以有一万种不同的方式骂别人“蠢货”[2]，有时候你甚至都没有意识到，而且哪一次你都是不可抑制地义愤填膺。

而且你越是相信你是对的（面对现实吧，你其实可以称呼_任何人_“蠢货”，而且你总_会_是对的），事后道歉对你来说会越难。

要解决这个问题，你只有两个选择：
- 成为道歉高手
- 把你的“爱”均匀播洒，让大家觉得你的出手是公平的。你得有点儿创意，这样他们有时候可能还会觉得挺好玩儿的。

希望靠着礼貌把一切摆平是不可能的。没有人会信任一个明显隐藏自己真实性情的人。

[2]保罗西蒙过去唱《失去爱人方法五十种》，那是因为很明白，《告诉一个开发者是蠢货的方法一万种》听起来没有前者那么有韵味。不过我相信他考虑过后者。

第三章：人 II - 好的那类

既然事实表明大多数人都是白痴，那结论自然很可悲：你也是一位。另外，即使我们都暗自觉得自己高于普通人（承认吧，没有人认为自己是普通人甚至不如普通人），我们也要承认我们不是那只最锋利的刀子，总有人没有你那么白痴。

有些人容不下聪明人。有些人则会利用他们。

作为一个内核的维护者，你要确保你属于第二种。你要紧随聪明人，因为他们能让你的工作变得容易。特别是，他们能替你做决定。这就是问题所在。

因此，如果你发现有人比你聪明，那就顺水推舟吧。之后你的管理任务就变成诸如“听起来不错--去搞吧”，或者“这个听起来挺好，不过那个xxx怎么样？”。特别是第二种说法，你要么能跟着学点儿“xxx”的东西，要么能显示_额外_的管理才干，因为你指出了一些聪明人没有想过的东西。不管是哪种情况，你都是赢家。

值得提出的是，你要明白，在一个领域的牛人在另一个领域就不一定了。因此尽管你可能在几个不同的方向上给与引导激励，需要承认的是，他们可能只在他们自己的领域是专家，而在其它领域一无是处。值得庆幸的是，人们会自然地象被引力吸引一样被拉回他们擅长的领域。因此，只要你不是激励的太厉害，那么即使你真地在其它方向上引导了他们，也不至于造成不可挽回的后果。

第四章：责任追究

任何事情都回出错，因此人们需要找个人来承担责任。不好意思，你就是这个人。

承担责任其实并不困难，特别是当人们明白并不全是你的错。这给我们提醒了一种最好的承担责任的方式：承担他人的责任。你会因为替人受过而感觉高尚，他也会因为免于责任而感觉不错。那个由于你的过错而丢失了36GB色情收藏的家伙也不得不承认，你至少没有试图逃避责任。

然后你要_私下里_让那个真正把事情搞砸的人（如果你能找出他来）知道，是他把事情搞砸了。并不是说他因此就可以避免以后再出问题，而是因此他知道他欠你一个人情。而且，也许更重要的是，他很可能也是那个能修正问题的人；因为，我们得承认，那个人肯定不是你。

承担责任也是你能成为管理者的首要原因。这是别人愿意信任你、并给你可能的荣誉的部分原因，因为正是你能站出来说“是我搞砸了”。如果你已经遵循了前面的规则，现在说这句话对你来说应该很容易了。

第五章：需要避免的东西

有一件事比骂人“蠢货”更让人不能接受，那就是用假惺惺的口气叫人“蠢货”。前者还可以道歉，后者则没有机会。别人不会再听你的了，即使在你做的很漂亮的时候。

我们每个人都认为自己比别人强，当别人在充大个时，我们会错误地觉得自己_真地_被看扁了。因此，也许你在道德或智力上的确高于他人，但不要太显摆了，除非你是有意要惹恼某个人[3]。

同样，也不要太礼貌或太微妙了。礼貌很容易过度从而掩盖真正的问题，而且正如人们所说：“在互联网上，没人能听出来你的微妙”。因此，还是要大张旗鼓地摆明你的观点，不能寄望人们能揣摩出你的意思。

加点儿幽默能中和你的鲁直和说教。如果你过分到显得荒谬，反倒可以达到你的目的，且不会让接受者感到不爽，他只会觉得你傻的可爱。因此幽默可以帮助克服人性的障碍，而这个障碍这是我们在对待批评时所共有的。

[3]提示：互联网上那些与你的工作无直接关系的讨论组是发泄对他人不满的好地方。每隔一阵儿，带着嘲弄发些讨厌的帖子加入一场论战，会让你感到神清气爽。只是别把垃圾甩在自家门口了。

第六章：为什么是我？

既然你的主要任务是替人受过，并且还要痛苦地让所有的人看出来你是个生手，那么一个显然的问题是：当初干嘛要干这个？

本质上说，尽管可能不会有十来岁的小姑娘（或小男孩，这里我们不需要提出甄别或扮演性别主义者）尖叫着追到你的更衣室外敲门，你也_必将_由于是“负责人”而获得巨大的个人成就感。尽管你的所谓领导其实就是竭力追上别人并在其后尽力飞奔，你就不要太在意这些了，因为所有的人仍然会认为你就是负责人。

如果你能把这个问题搞定，那将是一项伟大的成就。

=======================================================================
Original from http://lwn.net/Articles/105375/
[Posted October 6, 2004 by corbet]

Linux kernel management style

This is a short document describing the preferred (or made up, depending on who you ask) management style for the linux kernel. It's meant to mirror the CodingStyle document to some degree, and mainly written to avoid answering (*) the same (or similar) questions over and over again.

Management style is very personal and much harder to quantify than simple coding style rules, so this document may or may not have anything to do with reality. It started as a lark, but that doesn't mean that it might not actually be true. You'll have to decide for yourself.

Btw, when talking about "kernel manager", it's all about the technical lead persons, not the people who do traditional management inside companies. If you sign purchase orders or you have any clue about the budget of your group, you're almost certainly not a kernel manager. These suggestions may or may not apply to you.

First off, I'd suggest buying "Seven Habits of Highly Successful People", and NOT read it. Burn it, it's a great symbolic gesture.

(*) This document does so not so much by answering the question, but by making it painfully obvious to the questioner that we don't have a clue to what the answer is.

Anyway, here goes:

Chapter 1: Decisions

Everybody thinks managers make decisions, and that decision-making is important. The bigger and more painful the decision, the bigger the manager must be to make it. That's very deep and obvious, but it's not actually true.

The name of the game is to _avoid_ having to make a decision. In particular, if somebody tells you "choose (a) or (b), we really need you to decide on this", you're in trouble as a manager. The people you manage had better know the details better than you, so if they come to you for a technical decision, you're screwed. You're clearly not competent to make that decision for them.

(Corollary:if the people you manage don't know the details better than you, you're also screwed, although for a totally different reason. Namely that you are in the wrong job, and that _they_ should be managing your brilliance instead).

So the name of the game is to _avoid_ decisions, at least the big and painful ones. Making small and non-consequential decisions is fine, and makes you look like you know what you're doing, so what a kernel manager needs to do is to turn the big and painful ones into small things where nobody really cares.

It helps to realize that the key difference between a big decision and a small one is whether you can fix your decision afterwards. Any decision can be made small by just always making sure that if you were wrong (and you _will_ be wrong), you can always undo the damage later by backtracking. Suddenly, you get to be doubly managerial for making _two_ inconsequential decisions - the wrong one _and_ the right one.

And people will even see that as true leadership (*cough* bullshit *cough*).

Thus the key to avoiding big decisions becomes to just avoiding to do things that can't be undone. Don't get ushered into a corner from which you cannot escape. A cornered rat may be dangerous - a cornered manager is just pitiful.

It turns out that since nobody would be stupid enough to ever really let a kernel manager have huge fiscal responsibility _anyway_, it's usually fairly easy to backtrack. Since you're not going to be able to waste huge amounts of money that you might not be able to repay, the only thing you can backtrack on is a technical decision, and there back-tracking is very easy: just tell everybody that you were an incompetent nincompoop, say you're sorry, and undo all the worthless work you had people work on for the last year. Suddenly the decision you made a year ago wasn't a big decision after all, since it could be easily undone.

It turns out that some people have trouble with this approach, for two reasons:
- admitting you were an idiot is harder than it looks. We all like to maintain appearances, and coming out in public to say that you were wrong is sometimes very hard indeed.
- having somebody tell you that what you worked on for the last year wasn't worthwhile after all can be hard on the poor lowly engineers too, and while the actual _work_ was easy enough to undo by just deleting it, you may have irrevocably lost the trust of that engineer. And remember: "irrevocable" was what we tried to avoid in the first place, and your decision ended up being a big one after all.

Happily, both of these reasons can be mitigated effectively by just admitting up-front that you don't have a friggin' clue, and telling people ahead of the fact that your decision is purely preliminary, and might be the wrong thing. You should always reserve the right to change your mind, and make people very _aware_ of that. And it's much easier to admit that you are stupid when you haven't _yet_ done the really stupid thing.

Then, when it really does turn out to be stupid, people just roll their eyes and say "Oops, he did it again".

This preemptive admission of incompetence might also make the people who actually do the work also think twice about whether it's worth doing or not. After all, if _they_ aren't certain whether it's a good idea, you sure as hell shouldn't encourage them by promising them that what they work on will be included. Make them at least think twice before they embark on a big endeavor.

Remember: they'd better know more about the details than you do, and they usually already think they have the answer to everything. The best thing you can do as a manager is not to instill confidence, but rather a healthy dose of critical thinking on what they do.

Btw, another way to avoid a decision is to plaintively just whine "can't we just do both?" and look pitiful. Trust me, it works. If it's not clear which approach is better, they'll eventually figure it out. The answer may end up being that both teams get so frustrated by the situation that they just give up.

That may sound like a failure, but it's usually a sign that there was something wrong with both projects, and the reason the people involved couldn't decide was that they were both wrong. You end up coming up smelling like roses, and you avoided yet another decision that you could have screwed up on.

Chapter 2: People

Most people are idiots, and being a manager means you'll have to deal with it, and perhaps more importantly, that _they_ have to deal with _you_.

It turns out that while it's easy to undo technical mistakes, it's not as easy to undo personality disorders. You just have to live with theirs - and yours.

However, in order to prepare yourself as a kernel manager, it's best to remember not to burn any bridges, bomb any innocent villagers, or alienate too many kernel developers. It turns out that alienating people is fairly easy, and un-alienating them is hard. Thus "alienating" immediately falls under the heading of "not reversible", and becomes a no-no according to Chapter 1.

There's just a few simple rules here:
(1) don't call people d*ckheads (at least not in public)
(2) learn how to apologize when you forgot rule (1)

The problem with #1 is that it's very easy to do, since you can say "you're a d*ckhead" in millions of different ways (*), sometimes without even realizing it, and almost always with a white-hot conviction that you are right.

And the more convinced you are that you are right (and let's face it, you can call just about _anybody_ a d*ckhead, and you often _will_ be right), the harder it ends up being to apologize afterwards.

To solve this problem, you really only have two options:
- get really good at apologies
- spread the "love" out so evenly that nobody really ends up feeling like they get unfairly targeted. Make it inventive enough, and they might even be amused.

The option of being unfailingly polite really doesn't exist. Nobody will trust somebody who is so clearly hiding his true character.

(*) Paul Simon sang "Fifty Ways to Lose Your Lover", because quite frankly, "A Million Ways to Tell a Developer He Is a D*ckhead" doesn't scan nearly as well. But I'm sure he thought about it.

Chapter 3: People II - the Good Kind

While it turns out that most people are idiots, the corollary to that is sadly that you are one too, and that while we can all bask in the secure knowledge that we're better than the average person (let's face it, nobody ever believes that they're average or below-average), we should also admit that we're not the sharpest knife around, and there will be other people that are less of an idiot that you are.

Some people react badly to smart people. Others take advantage of them.

Make sure that you, as a kernel maintainer, are in the second group. Suck up to them, because they are the people who will make your job easier. In particular, they'll be able to make your decisions for you, which is what the game is all about.

So when you find somebody smarter than you are, just coast along. Your management responsibilities largely become ones of saying "Sounds like a good idea - go wild", or "That sounds good, but what about xxx?". The second version in particular is a great way to either learn something new about "xxx" or seem _extra_ managerial by pointing out something the smarter person hadn't thought about. In either case, you win.

One thing to look out for is to realize that greatness in one area does not necessarily translate to other areas. So you might prod people in specific directions, but let's face it, they might be good at what they do, and suck at everything else. The good news is that people tend to naturally gravitate back to what they are good at, so it's not like you are doing something irreversible when you _do_ prod them in some
direction, just don't push too hard.

Chapter 4: Placing blame

Things will go wrong, and people want somebody to blame. Tag, you're it.

It's not actually that hard to accept the blame, especially if people kind of realize that it wasn't _all_ your fault. Which brings us to the best way of taking the blame: do it for another guy. You'll feel good for taking the fall, he'll feel good about not getting blamed, and the guy who lost his whole 36GB porn-collection because of your incompetence will grudgingly admit that you at least didn't try to weasel out of it.

Then make the developer who really screwed up (if you can find him) know _in_private_ that he screwed up. Not just so he can avoid it in the future, but so that he knows he owes you one. And, perhaps even more importantly, he's also likely the person who can fix it. Because, let's face it, it sure ain't you.

Taking the blame is also why you get to be manager in the first place. It's part of what makes people trust you, and allow you the potential glory, because you're the one who gets to say "I screwed up". And if you've followed the previous rules, you'll be pretty good at saying that by now.

Chapter 5: Things to avoid

There's one thing people hate even more than being called "d*ckhead", and that is being called a "d*ckhead" in a sanctimonious voice. The first you can apologize for, the second one you won't really get the chance. They likely will no longer be listening even if you otherwise do a good job.

We all think we're better than anybody else, which means that when somebody else puts on airs, it _really_ rubs us the wrong way. You may be morally and intellectually superior to everybody around you, but don't try to make it too obvious unless you really _intend_ to irritate somebody (*).

Similarly, don't be too polite or subtle about things. Politeness easily ends up going overboard and hiding the problem, and as they say, "On the internet, nobody can hear you being subtle". Use a big blunt object to hammer the point in, because you can't really depend on people getting your point otherwise.

Some humor can help pad both the bluntness and the moralizing. Going overboard to the point of being ridiculous can drive a point home without making it painful to the recipient, who just thinks you're being silly. It can thus help get through the personal mental block we all have about criticism.

(*) Hint: internet newsgroups that are not directly related to your work are great ways to take out your frustrations at other people. Write insulting posts with a sneer just to get into a good flame every once in a while, and you'll feel cleansed. Just don't crap too close to home.

Chapter 6: Why me?

Since your main responsibility seems to be to take the blame for other peoples mistakes, and make it painfully obvious to everybody else that you're incompetent, the obvious question becomes one of why do it in the first place?

First off, while you may or may not get screaming teenage girls (or boys, let's not be judgmental or sexist here) knocking on your dressing room door, you _will_ get an immense feeling of personal accomplishment for being "in charge". Never mind the fact that you're really leading by trying to keep up with everybody else and running after them as fast as you can. Everybody will still think you're the person in charge.

It's a great job if you can hack it.

GC safe-point (or safepoint) and safe-region

2008-01-26T03:12:00.000-08:00

Root references
An object is dead really means it is useless. Only the programmer knows if an object is useless or not. In order for the program to decide if an object is useless, we can use compiler analysis, reference counting, or reachability analysis.

Reachability analysis assumes an object is live as long as it is reachable by the mutator. If an object's reference is contained by a slot of the mutator's stack, it's directly reachable. Those objects reachable from reachable objects are also reachable. So the issue for reachability analysis is to find out the references that are directly reachable, which are root references. The set of root references is root set.

The mutator's context has the data that are directly reachable, so to get root set is to find object references in the context. The context of a mutator refers to its stack and its register file (and some other thread-specific data). Global data are also directly reachable.

Root set enumeration
Normally, if a GC uses reachability to determine an object's liveness, GC needs to get a consistent snapshot of the mutator's context, so as to enumerate the root references. This is true for both stop-the-world (STW) and concurrent GC (mostly). "Consistent" means the snapshot looks like taken at a single time point. A consistent snapshot of root references are necessary for correctness, otherwise some live objects might be lost. Then the question is how to get the consistent mutator's context snapshot.

To get the consistent snapshot, a simple way is that the mutator suspends its execution during the root references enumeration. The snapshot is also consistent if the root set does not change during the enumeration process.

When a mutator suspends its execution, it is not necessarily able to enumerate the root references in its context, unless it book-keeps the reference information in its context. That is, it should be able to tell which stack slots have references, and which registers hold references. If GC can accurately gets the information, it is called precise root set enumeration; or it's imprecise.

(For imprecise enumeration, GC has to use some heuristics to conservatively guess the references from the context. So the GC is called conservative GC. This essay only discusses precise enumeration.)

Harmony supports precise root set enumeration with GC safe-point and safe-region.

Safe-point (or safepoint)
In order to support precise enumeration, JIT compiler should do additional work, because only JIT knows exactly stack frame info and register contents. When JIT compiles a method, for every instruction, it can book-keep the root reference information in case the execution is suspended at that instruction.

But to remember the info for every instruction is too expensive. It requires substantial space to store the information. This is also unnecessary, because only a few instructions will have the chances to be the suspension points in real execution. JIT only needs to book-keep information for those instruction points -- they are called safe-points. Safe-point means it is a safe suspension point for root set enumeration.

Btw, the ability of a compiler to know exact stack slots' information is not universally available in all programming languages. Only safe languages have the ability. For example, C/C++ doesn't.

Mutator suspension
The question to safe-points is, how we can guarantee that the mutator is suspended at safe-point.

There are basically two kinds of approaches to suspend a mutator, preemptively or voluntarily. The preemptive approach is to suspend the mutator whenever GC needs to start a collection. If it finds the mutator is suspended at an unsafe point, it will resume the mutator, rolling it forward to a safe-point. This was implemented in ORP [1], the predecessor of Harmony. But currently almost no JVM takes this approach.

The approach used in Harmony is voluntary suspension. When GC wants to trigger a collection, it simply sets a flag; the mutators poll the flag periodically, and will suspend once they find the flag is set. Those polling points are safe-points. It's mostly JIT's responsibility to insert the pollings at proper positions. Sometimes VM also needs to have some polling points.

Polling point
So where are the right places for polling GC trigger event? As I discussed above, we do not want to have polling points for every instruction. For voluntary suspension, a more serious problem is the polling overhead. So the basic principles for polling point insertion are: Firstly, polling points should be frequent enough so that GC does not wait too long for a mutator to suspend, because other mutators might be waiting for GC to free the space in order to continue. Secondly, polling points should not be too frequent to introduce big runtime overhead.

The best result is to have only adequate polling points that are necessary and sufficient.
1. The mandatory polling points are the allocation sites. Allocation can trigger collection, so allocation site has to be a safe point.
2. Long-time execution are always associated with method call or loop. So call sites and loop back sites are also expected polling points.

Those are the sites for polling points in Harmony: allocation sites, call sites and loop back sites. Mostly the runtime overhead is smaller than 1%. Unfortunately we found safe-point alone is not sufficient.

Safe-region
Why is safe-point alone insufficient? The reason is we forgot the case of "long time execution". We forgot it because it's actually not "execution", but long time idle. There are situations when the application can not respond promptly to a GC trigger event, such as sleep, or being blocked in a system call. These operations are out of JVM's control. It can not respond to GC trigger event in that period. So we introduce safe-region to solve the problem.

Safe-region is the section of code that no references are mutated in it, then it is safe to enumerate roots at any points of that region. In other words, the safe region is a big extended safe-point.

In safe-point design, the mutator polling for GC event will respond if the event is triggered. It responds by setting a ready flag when it's sure to suspend. Then the GC can proceed with root set enumeration. This is a hand-shaking protocol.

Safe-region just follows this protocol. The mutator sets the ready flag when it enters a safe-region. Before it leaves the region, it checks if GC has finished its enumeration (or collection), and no longer needs the mutator under suspension state. If it's true, it goes ahead and leaves the region; otherwise, it suspends itself as in a safe-point.

In Harmony implementation, we insert suspend_enable and suspend_disable to delimit the scope of safe-region.

[1] ORP (Open Runtime Platform), http://orp.sf.net ;