Yet another male perspective on women in free software

O'Reilly has been running a series of articles on women in technology which has an emphasis on encouraging women to enter the field. LWN has, in its usual way, posted pointers to a subset of those articles; most of those pointers have resulted in lengthy conversations among LWN readers. Those readers, true to their usual form, have managed to hold a higher-level discussion than has been seen in other forums. That said, there have been a lot of bits expended on discussions of topics like relative brain sizes, differing approaches to family life, the true femininity of transsexuals, and so on. Your editor, not generally known for being short of opinions, could expound on many of these topics, but that is not going to happen here. Such discussions are not really relevant to the topic at hand.

The relevant discussion, it seems, can be much more simple and straightforward, concentrating on a few basic points:

• The participation by women in the free software community is strikingly low. It is not just far below the incidence of women in the wider world; it is also well below the percentage of women found in more traditional technical jobs.

• We would be better off if we could attract more women to our community. We are not so rich that we can afford to do without skilled developers, writers, artists, project managers, and so on. We are not so diverse that we can afford to do without a wider variety of points of view.

• We, as a community, behave in ways which drive women away. We are also good at repelling people with thin skins, people with different cultural expectations on how professionals talk to each other, and anybody else who does not easily fit in.

There is no need to get drawn into blind alleys about genetic links to mathematical ability or the demands of family life. There is no point in being distracted by strawmen, be they an outspoken feminist that somebody finds particularly obnoxious or the notion that somebody is calling for a quota of 50% female participation. There is no shortage of incredibly smart, talented, and interested women out there who have found our community unwelcoming; that, on its own terms, is a problem.

When comments (not on LWN, happily) respond to this year's kernel summit group photo by comparing the relative merits of the few female developers found there, our community as a whole becomes that much more hostile. When certain Linux publications run overtly demeaning ads, a clear view of how women should participate in free software is being communicated. When sexist idiots drive one of the most humorous and human diaries off the net, we all lose out. When well-intentioned commenters employ terms like "sausage fest," they show that we still clearly miss the point. When women are harassed at Linux events, there is a good chance that they will not come back. And when all of these things (and worse) drive people out of our community, we are all impoverished as a result.

Making things better does not require the establishment of some sort of police force to enforce extensive rules. We do not need to replicate Gentoo's "proctors" experiment. We do not have to establish official codes of conduct, though making it clear that a certain level of polite and respectful behavior is expected cannot hurt. But if we can recognize the problem - that our community's behavior is driving away women and many other potential contributors - without trying to bury it in irrelevant strawman arguments, we will be off to a good start. We are, as a community, good at solving problems once we realize that they need our attention. This one needs our attention.

Comments (79 posted)

Matt Domsch on Linux support at Dell

Curious about the state of Linux support at Dell, we asked Matt Domsch, Linux Technology Strategist there, some questions by email. Matt has been working to support Linux on Dell hardware for eight years and has broad knowledge of the kinds of issues hardware vendors face when supporting Linux. He was gracious enough to answer our questions at length, covering some history, challenges and the future for Linux at Dell.

LWN: Can you give us an overview of your Linux history? When did you get involved with Linux and why?

LWN: What is your history at Dell? And the history of Linux support at Dell?

LWN: What have been the biggest challenges with supporting Linux at Dell?

[PULL QUOTE: Dell expects our partner hardware vendors to provide fully open source / free software drivers, and to maintain them in the appropriate upstream project, kernel.org or x.org. This has been our policy since we started shipping Linux on servers in 1999, and continues to be our policy today. END QUOTE] LWN: Does Dell have plans to make hardware changes in the future to support more hardware with free drivers, specifically video and wireless cards?

LWN: You folks recently made a new version of Ubuntu with updated drivers and the like, can you give us an idea of what the aim of that effort was? What kind of problems were you trying to solve and what plans do you have to work with Ubuntu to avoid that in the future?

LWN: Can you tell us about the testing and support lab at Dell?

LWN: What is DKMS? What's the status of the project? What still remains to be done?

LWN: Where do you see Linux at Dell heading? More systems supported, more distributions supported, or other things entirely?

Our thanks to Matt for taking the time to respond in detail.

Comments (21 posted)

Memory part 2: CPU caches

[Editor's note: This is the second installment in Ulrich Drepper's "What every programmer should know about memory" document. Those who have not read the first part will likely want to start there. This is good stuff, and we once again thank Ulrich for allowing us to publish it.

One quick request: in a document of this length there are bound to be a few typographical errors remaining. If you find one, and wish to see it corrected, please let us know via mail to lwn@lwn.net rather than by posting a comment. That way we will be sure to incorporate the fix and get it back into Ulrich's copy of the document and other readers will not have to plow through uninteresting comments.]

CPUs are today much more sophisticated than they were only 25 years ago. In those days, the frequency of the CPU core was at a level equivalent to that of the memory bus. Memory access was only a bit slower than register access. But this changed dramatically in the early 90s, when CPU designers increased the frequency of the CPU core but the frequency of the memory bus and the performance of RAM chips did not increase proportionally. This is not due to the fact that faster RAM could not be built, as explained in the previous section. It is possible but it is not economical. RAM as fast as current CPU cores is orders of magnitude more expensive than any dynamic RAM.

If the choice is between a machine with very little, very fast RAM and a machine with a lot of relatively fast RAM, the second will always win given a working set size which exceeds the small RAM size and the cost of accessing secondary storage media such as hard drives. The problem here is the speed of secondary storage, usually hard disks, which must be used to hold the swapped out part of the working set. Accessing those disks is orders of magnitude slower than even DRAM access.

Fortunately it does not have to be an all-or-nothing decision. A computer can have a small amount of high-speed SRAM in addition to the large amount of DRAM. One possible implementation would be to dedicate a certain area of the address space of the processor as containing the SRAM and the rest the DRAM. The task of the operating system would then be to optimally distribute data to make use of the SRAM. Basically, the SRAM serves in this situation as an extension of the register set of the processor.

While this is a possible implementation, it is not viable. Ignoring the problem of mapping the physical resources of such SRAM-backed memory to the virtual address spaces of the processes (which by itself is terribly hard) this approach would require each process to administer in software the allocation of this memory region. The size of the memory region can vary from processor to processor (i.e., processors have different amounts of the expensive SRAM-backed memory). Each module which makes up part of a program will claim its share of the fast memory, which introduces additional costs through synchronization requirements. In short, the gains of having fast memory would be eaten up completely by the overhead of administering the resources.

So, instead of putting the SRAM under the control of the OS or user, it becomes a resource which is transparently used and administered by the processors. In this mode, SRAM is used to make temporary copies of (to cache, in other words) data in main memory which is likely to be used soon by the processor. This is possible because program code and data has temporal and spatial locality. This means that, over short periods of time, there is a good chance that the same code or data gets reused. For code this means that there are most likely loops in the code so that the same code gets executed over and over again (the perfect case for spatial locality). Data accesses are also ideally limited to small regions. Even if the memory used over short time periods is not close together there is a high chance that the same data will be reused before long (temporal locality). For code this means, for instance, that in a loop a function call is made and that function is located elsewhere in the address space. The function may be distant in memory, but calls to that function will be close in time. For data it means that the total amount of memory used at one time (the working set size) is ideally limited but the memory used, as a result of the random access nature of RAM, is not close together. Realizing that locality exists is key to the concept of CPU caches as we use them today.

A simple computation can show how effective caches can theoretically be. Assume access to main memory takes 200 cycles and access to the cache memory take 15 cycles. Then code using 100 data elements 100 times each will spend 2,000,000 cycles on memory operations if there is no cache and only 168,500 cycles if all data can be cached. That is an improvement of 91.5%.

The size of the SRAM used for caches is many times smaller than the main memory. In the author's experience with workstations with CPU caches the cache size has always been around 1/1000th of the size of the main memory (today: 4MB cache and 4GB main memory). This alone does not constitute a problem. If the size of the working set (the set of data currently worked on) is smaller than the cache size it does not matter. But computers do not have large main memories for no reason. The working set is bound to be larger than the cache. This is especially true for systems running multiple processes where the size of the working set is the sum of the sizes of all the individual processes and the kernel.

What is needed to deal with the limited size of the cache is a set of good strategies to determine what should be cached at any given time. Since not all data of the working set is used at exactly the same time we can use techniques to temporarily replace some data in the cache with other data. And maybe this can be done before the data is actually needed. This prefetching would remove some of the costs of accessing main memory since it happens asynchronously with respect to the execution of the program. All these techniques and more can be used to make the cache appear bigger than it actually is. We will discuss them in Section 3.3. Once all these techniques are exploited it is up to the programmer to help the processor. How this can be done will be discussed in Section 6.

3.1 CPU Caches in the Big Picture

Before diving into technical details of the implementation of CPU caches some readers might find it useful to first see in some more details how caches fit into the “big picture” of a modern computer system.

Figure 3.1: Minimum Cache Configuration

Figure 3.1 shows the minimum cache configuration. It corresponds to the architecture which could be found in early systems which deployed CPU caches. The CPU core is no longer directly connected to the main memory. {In even earlier systems the cache was attached to the system bus just like the CPU and the main memory. This was more a hack than a real solution.} All loads and stores have to go through the cache. The connection between the CPU core and the cache is a special, fast connection. In a simplified representation, the main memory and the cache are connected to the system bus which can also be used for communication with other components of the system. We introduced the system bus as “FSB” which is the name in use today; see Section 2.2. In this section we ignore the Northbridge; it is assumed to be present to facilitate the communication of the CPU(s) with the main memory.

Even though computers for the last several decades have used the von Neumann architecture, experience has shown that it is of advantage to separate the caches used for code and for data. Intel has used separate code and data caches since 1993 and never looked back. The memory regions needed for code and data are pretty much independent of each other, which is why independent caches work better. In recent years another advantage emerged: the instruction decoding step for the most common processors is slow; caching decoded instructions can speed up the execution, especially when the pipeline is empty due to incorrectly predicted or impossible-to-predict branches.

Soon after the introduction of the cache, the system got more complicated. The speed difference between the cache and the main memory increased again, to a point that another level of cache was added, bigger and slower than the first-level cache. Only increasing the size of the first-level cache was not an option for economical reasons. Today, there are even machines with three levels of cache in regular use. A system with such a processor looks like Figure 3.2. With the increase on the number of cores in a single CPU the number of cache levels might increase in the future even more.

Figure 3.2: Processor with Level 3 Cache

Figure 3.2 shows three levels of cache and introduces the nomenclature we will use in the remainder of the document. L1d is the level 1 data cache, L1i the level 1 instruction cache, etc. Note that this is a schematic; the data flow in reality need not pass through any of the higher-level caches on the way from the core to the main memory. CPU designers have a lot of freedom designing the interfaces of the caches. For programmers these design choices are invisible.

In addition we have processors which have multiple cores and each core can have multiple “threads”. The difference between a core and a thread is that separate cores have separate copies of (almost {Early multi-core processors even had separate 2^nd level caches and no 3^rd level cache.}) all the hardware resources. The cores can run completely independently unless they are using the same resources—e.g., the connections to the outside—at the same time. Threads, on the other hand, share almost all of the processor's resources. Intel's implementation of threads has only separate registers for the threads and even that is limited, some registers are shared. The complete picture for a modern CPU therefore looks like Figure 3.3.

Figure 3.3: Multi processor, multi-core, multi-thread

In this figure we have two processors, each with two cores, each of which has two threads. The threads share the Level 1 caches. The cores (shaded in the darker gray) have individual Level 1 caches. All cores of the CPU share the higher-level caches. The two processors (the two big boxes shaded in the lighter gray) of course do not share any caches. All this will be important, especially when we are discussing the cache effects on multi-process and multi-thread applications.

3.2 Cache Operation at High Level

To understand the costs and savings of using a cache we have to combine the knowledge about the machine architecture and RAM technology from Section 2 with the structure of caches described in the previous section.

By default all data read or written by the CPU cores is stored in the cache. There are memory regions which cannot be cached but this is something only the OS implementers have to be concerned about; it is not visible to the application programmer. There are also instructions which allow the programmer to deliberately bypass certain caches. This will be discussed in Section 6.

If the CPU needs a data word the caches are searched first. Obviously, the cache cannot contain the content of the entire main memory (otherwise we would need no cache), but since all memory addresses are cacheable, each cache entry is tagged using the address of the data word in the main memory. This way a request to read or write to an address can search the caches for a matching tag. The address in this context can be either the virtual or physical address, varying based on the cache implementation.

Since the tag requires space in addition to the actual memory, it is inefficient to chose a word as the granularity of the cache. For a 32-bit word on an x86 machine the tag itself might need 32 bits or more. Furthermore, since spatial locality is one of the principles on which caches are based, it would be bad to not take this into account. Since neighboring memory is likely to be used together it should also be loaded into the cache together. Remember also what we learned in Section 2.2.1: RAM modules are much more effective if they can transport many data words in a row without a new CAS or even RAS signal. So the entries stored in the caches are not single words but, instead, “lines” of several contiguous words. In early caches these lines were 32 bytes long; now the norm is 64 bytes. If the memory bus is 64 bits wide this means 8 transfers per cache line. DDR supports this transport mode efficiently.

When memory content is needed by the processor the entire cache line is loaded into the L1d. The memory address for each cache line is computed by masking the address value according to the cache line size. For a 64 byte cache line this means the low 6 bits are zeroed. The discarded bits are used as the offset into the cache line. The remaining bits are in some cases used to locate the line in the cache and as the tag. In practice an address value is split into three parts. For a 32-bit address it might look as follows:

With a cache line size of 2^O the low O bits are used as the offset into the cache line. The next S bits select the “cache set”. We will go into more detail soon on why sets, and not single slots, are used for cache lines. For now it is sufficient to understand there are 2^S sets of cache lines. This leaves the top 32 - S - O = T bits which form the tag. These T bits are the value associated with each cache line to distinguish all the aliases {All cache lines with the same S part of the address are known by the same alias.} which are cached in the same cache set. The S bits used to address the cache set do not have to be stored since they are the same for all cache lines in the same set.

When an instruction modifies memory the processor still has to load a cache line first because no instruction modifies an entire cache line at once (exception to the rule: write-combining as explained in Section 6.1). The content of the cache line before the write operation therefore has to be loaded. It is not possible for a cache to hold partial cache lines. A cache line which has been written to and which has not been written back to main memory is said to be “dirty”. Once it is written the dirty flag is cleared.

To be able to load new data in a cache it is almost always first necessary to make room in the cache. An eviction from L1d pushes the cache line down into L2 (which uses the same cache line size). This of course means room has to be made in L2. This in turn might push the content into L3 and ultimately into main memory. Each eviction is progressively more expensive. What is described here is the model for an exclusive cache as is preferred by modern AMD and VIA processors. Intel implements inclusive caches {This generalization is not completely correct. A few caches are exclusive and some inclusive caches have exclusive cache properties.} where each cache line in L1d is also present in L2. Therefore evicting from L1d is much faster. With enough L2 cache the disadvantage of wasting memory for content held in two places is minimal and it pays off when evicting. A possible advantage of an exclusive cache is that loading a new cache line only has to touch the L1d and not the L2, which could be faster.

The CPUs are allowed to manage the caches as they like as long as the memory model defined for the processor architecture is not changed. It is, for instance, perfectly fine for a processor to take advantage of little or no memory bus activity and proactively write dirty cache lines back to main memory. The wide variety of cache architectures among the processors for the x86 and x86-64, between manufacturers and even within the models of the same manufacturer, are testament to the power of the memory model abstraction.

In symmetric multi-processor (SMP) systems the caches of the CPUs cannot work independently from each other. All processors are supposed to see the same memory content at all times. The maintenance of this uniform view of memory is called “cache coherency”. If a processor were to look simply at its own caches and main memory it would not see the content of dirty cache lines in other processors. Providing direct access to the caches of one processor from another processor would be terribly expensive and a huge bottleneck. Instead, processors detect when another processor wants to read or write to a certain cache line.

If a write access is detected and the processor has a clean copy of the cache line in its cache, this cache line is marked invalid. Future references will require the cache line to be reloaded. Note that a read access on another CPU does not necessitate an invalidation, multiple clean copies can very well be kept around.

More sophisticated cache implementations allow another possibility to happen. If the cache line which another processor wants to read from or write to is currently marked dirty in the first processor's cache a different course of action is needed. In this case the main memory is out-of-date and the requesting processor must, instead, get the cache line content from the first processor. Through snooping, the first processor notices this situation and automatically sends the requesting processor the data. This action bypasses main memory, though in some implementations the memory controller is supposed to notice this direct transfer and store the updated cache line content in main memory. If the access is for writing the first processor then invalidates its copy of the local cache line.

Over time a number of cache coherency protocols have been developed. The most important is MESI, which we will introduce in Section 3.3.4. The outcome of all this can be summarized in a few simple rules:

• A dirty cache line is not present in any other processor's cache.

• Clean copies of the same cache line can reside in arbitrarily many caches.

If these rules can be maintained, processors can use their caches efficiently even in multi-processor systems. All the processors need to do is to monitor each others' write accesses and compare the addresses with those in their local caches. In the next section we will go into a few more details about the implementation and especially the costs.

Finally, we should at least give an impression of the costs associated with cache hits and misses. These are the numbers Intel lists for a Pentium M:

To Where	Cycles
Register	<= 1
L1d	~3
L2	~14
Main Memory	~240

These are the actual access times measured in CPU cycles. It is interesting to note that for the on-die L2 cache a large part (probably even the majority) of the access time is caused by wire delays. This is a physical limitation which can only get worse with increasing cache sizes. Only process shrinking (for instance, going from 60nm for Merom to 45nm for Penryn in Intel's lineup) can improve those numbers.

The numbers in the table look high but, fortunately, the entire cost does not have to be paid for each occurrence of the cache load and miss. Some parts of the cost can be hidden. Today's processors all use internal pipelines of different lengths where the instructions are decoded and prepared for execution. Part of the preparation is loading values from memory (or cache) if they are transferred to a register. If the memory load operation can be started early enough in the pipeline, it may happen in parallel with other operations and the entire cost of the load might be hidden. This is often possible for L1d; for some processors with long pipelines for L2 as well.

There are many obstacles to starting the memory read early. It might be as simple as not having sufficient resources for the memory access or it might be that the final address of the load becomes available late as the result of another instruction. In these cases the load costs cannot be hidden (completely).

For write operations the CPU does not necessarily have to wait until the value is safely stored in memory. As long as the execution of the following instructions appears to have the same effect as if the value were stored in memory there is nothing which prevents the CPU from taking shortcuts. It can start executing the next instruction early. With the help of shadow registers which can hold values no longer available in a regular register it is even possible to change the value which is to be stored in the incomplete write operation.

Figure 3.4: Access Times for Random Writes

For an illustration of the effects of cache behavior see Figure 3.4. We will talk about the program which generated the data later; it is a simple simulation of a program which accesses a configurable amount of memory repeatedly in a random fashion. Each data item has a fixed size. The number of elements depends on the selected working set size. The Y–axis shows the average number of CPU cycles it takes to process one element; note that the scale for the Y–axis is logarithmic. The same applies in all the diagrams of this kind to the X–axis. The size of the working set is always shown in powers of two.

The graph shows three distinct plateaus. This is not surprising: the specific processor has L1d and L2 caches, but no L3. With some experience we can deduce that the L1d is 2¹³ bytes in size and that the L2 is 2²⁰ bytes in size. If the entire working set fits into the L1d the cycles per operation on each element is below 10. Once the L1d size is exceeded the processor has to load data from L2 and the average time springs up to around 28. Once the L2 is not sufficient anymore the times jump to 480 cycles and more. This is when many or most operations have to load data from main memory. And worse: since data is being modified dirty cache lines have to be written back, too.

This graph should give sufficient motivation to look into coding improvements which help improve cache usage. We are not talking about a few measly percent here; we are talking about orders-of-magnitude improvements which are sometimes possible. In Section 6 we will discuss techniques which allow writing more efficient code. The next section goes into more details of CPU cache designs. The knowledge is good to have but not necessary for the rest of the paper. So this section could be skipped.

3.3 CPU Cache Implementation Details

Cache implementers have the problem that each cell in the huge main memory potentially has to be cached. If the working set of a program is large enough this means there are many main memory locations which fight for each place in the cache. Previously it was noted that a ratio of 1-to-1000 for cache versus main memory size is not uncommon.

3.3.1 Associativity

It would be possible to implement a cache where each cache line can hold a copy of any memory location. This is called a fully associative cache. To access a cache line the processor core would have to compare the tags of each and every cache line with the tag for the requested address. The tag would be comprised of the entire part of the address which is not the offset into the cache line (that means, S in the figure on Section 3.2 is zero).

There are caches which are implemented like this but, by looking at the numbers for an L2 in use today, will show that this is impractical. Given a 4MB cache with 64B cache lines the cache would have 65,536 entries. To achieve adequate performance the cache logic would have to be able to pick from all these entries the one matching a given tag in just a few cycles. The effort to implement this would be enormous.

Figure 3.5: Fully Associative Cache Schematics

For each cache line a comparator is needed to compare the large tag (note, S is zero). The letter next to each connection indicates the width in bits. If none is given it is a single bit line. Each comparator has to compare two T-bit-wide values. Then, based on the result, the appropriate cache line content is selected and made available. This requires merging as many sets of O data lines as there are cache buckets. The number of transistors needed to implement a single comparator is large especially since it must work very fast. No iterative comparator is usable. The only way to save on the number of comparators is to reduce the number of them by iteratively comparing the tags. This is not suitable for the same reason that iterative comparators are not: it takes too long.

Fully associative caches are practical for small caches (for instance, the TLB caches on some Intel processors are fully associative) but those caches are small, really small. We are talking about a few dozen entries at most.

For L1i, L1d, and higher level caches a different approach is needed. What can be done is to restrict the search. In the most extreme restriction each tag maps to exactly one cache entry. The computation is simple: given the 4MB/64B cache with 65,536 entries we can directly address each entry by using bits 6 to 21 of the address (16 bits). The low 6 bits are the index into the cache line.

Figure 3.6: Direct-Mapped Cache Schematics

Such a direct-mapped cache is fast and relatively easy to implement as can be seen in Figure 3.6. It requires exactly one comparator, one multiplexer (two in this diagram where tag and data are separated, but this is not a hard requirement on the design), and some logic to select only valid cache line content. The comparator is complex due to the speed requirements but there is only one of them now; as a result more effort can be spent on making it fast. The real complexity in this approach lies in the multiplexers. The number of transistors in a simple multiplexer grows with O(log N), where N is the number of cache lines. This is tolerable but might get slow, in which case speed can be increased by spending more real estate on transistors in the multiplexers to parallelize some of the work and to increase the speed. The total number of transistors can grow slowly with a growing cache size which makes this solution very attractive. But it has a drawback: it only works well if the addresses used by the program are evenly distributed with respect to the bits used for the direct mapping. If they are not, and this is usually the case, some cache entries are heavily used and therefore repeatedly evicted while others are hardly used at all or remain empty.

Figure 3.7: Set-Associative Cache Schematics

This problem can be solved by making the cache set associative. A set-associative cache combines the features of the full associative and direct-mapped caches to largely avoid the weaknesses of those designs. Figure 3.7 shows the design of a set-associative cache. The tag and data storage are divided into sets which are selected by the address. This is similar to the direct-mapped cache. But instead of only having one element for each set value in the cache a small number of values is cached for the same set value. The tags for all the set members are compared in parallel, which is similar to the functioning of the fully associative cache.

The result is a cache which is not easily defeated by unfortunate or deliberate selection of addresses with the same set numbers and at the same time the size of the cache is not limited by the number of comparators which can be implemented in parallel. If the cache grows it is (in this figure) only the number of columns which increases, not the number of rows. The number of rows only increases if the associativity of the cache is increased. Today processors are using associativity levels of up to 16 for L2 caches or higher. L1 caches usually get by with 8.

L2 Cache Size	Associativity
	Direct		2		4		8
	CL=32	CL=64	CL=32	CL=64	CL=32	CL=64	CL=32	CL=64
512k	27,794,595	20,422,527	25,222,611	18,303,581	24,096,510	17,356,121	23,666,929	17,029,334
1M	19,007,315	13,903,854	16,566,738	12,127,174	15,537,500	11,436,705	15,162,895	11,233,896
2M	12,230,962	8,801,403	9,081,881	6,491,011	7,878,601	5,675,181	7,391,389	5,382,064
4M	7,749,986	5,427,836	4,736,187	3,159,507	3,788,122	2,418,898	3,430,713	2,125,103
8M	4,731,904	3,209,693	2,690,498	1,602,957	2,207,655	1,228,190	2,111,075	1,155,847
16M	2,620,587	1,528,592	1,958,293	1,089,580	1,704,878	883,530	1,671,541	862,324

Table 3.1: Effects of Cache Size, Associativity, and Line Size

Given our 4MB/64B cache and 8-way set associativity the cache we are left with has 8,192 sets and only 13 bits of the tag are used in addressing the cache set. To determine which (if any) of the entries in the cache set contains the addressed cache line 8 tags have to be compared. That is feasible to do in very short time. With an experiment we can see that this makes sense.

Table 3.1 shows the number of L2 cache misses for a program (gcc in this case, the most important benchmark of them all, according to the Linux kernel people) for changing cache size, cache line size, and associativity set size. In Section 7.2 we will introduce the tool to simulate the caches as required for this test.

Just in case this is not yet obvious, the relationship of all these values is that the cache size is

cache line size × associativity × number of sets

The addresses are mapped into the cache by using

O = log₂ cache line size
S = log₂ number of sets

in the way the figure in Section 3.2 shows.

Figure 3.8: Cache Size vs Associativity (CL=32)

Figure 3.8 makes the data of the table more comprehensible. It shows the data for a fixed cache line size of 32 bytes. Looking at the numbers for a given cache size we can see that associativity can indeed help to reduce the number of cache misses significantly. For an 8MB cache going from direct mapping to 2-way set associative cache saves almost 44% of the cache misses. The processor can keep more of the working set in the cache with a set associative cache compared with a direct mapped cache.

In the literature one can occasionally read that introducing associativity has the same effect as doubling cache size. This is true in some extreme cases as can be seen in the jump from the 4MB to the 8MB cache. But it certainly is not true for further doubling of the associativity. As we can see in the data, the successive gains are much smaller. We should not completely discount the effects, though. In the example program the peak memory use is 5.6M. So with a 8MB cache there are unlikely to be many (more than two) uses for the same cache set. With a larger working set the savings can be higher as we can see from the larger benefits of associativity for the smaller cache sizes.

In general, increasing the associativity of a cache above 8 seems to have little effects for a single-thread workload. With the introduction of multi-core processors which use a shared L2 the situation changes. Now you basically have two programs hitting on the same cache which causes the associativity in practice to be halved (or quartered for quad-core processors). So it can be expected that, with increasing numbers of cores, the associativity of the shared caches should grow. Once this is not possible anymore (16-way set associativity is already hard) processor designers have to start using shared L3 caches and beyond, while L2 caches are potentially shared by a subset of the cores.

Another effect we can study in Figure 3.8 is how the increase in cache size helps with performance. This data cannot be interpreted without knowing about the working set size. Obviously, a cache as large as the main memory would lead to better results than a smaller cache, so there is in general no limit to the largest cache size with measurable benefits.

As already mentioned above, the size of the working set at its peak is 5.6M. This does not give us any absolute number of the maximum beneficial cache size but it allows us to estimate the number. The problem is that not all the memory used is contiguous and, therefore, we have, even with a 16M cache and a 5.6M working set, conflicts (see the benefit of the 2-way set associative 16MB cache over the direct mapped version). But it is a safe bet that with the same workload the benefits of a 32MB cache would be negligible. But who says the working set has to stay the same? Workloads are growing over time and so should the cache size. When buying machines, and one has to choose the cache size one is willing to pay for, it is worthwhile to measure the working set size. Why this is important can be seen in the figures on Figure 3.10.

Figure 3.9: Test Memory Layouts

Two types of tests are run. In the first test the elements are processed sequentially. The test program follows the pointer n but the array elements are chained so that they are traversed in the order in which they are found in memory. This can be seen in the lower part of Figure 3.9. There is one back reference from the last element. In the second test (upper part of the figure) the array elements are traversed in a random order. In both cases the array elements form a circular single-linked list.

3.3.2 Measurements of Cache Effects

All the figures are created by measuring a program which can simulate working sets of arbitrary size, read and write access, and sequential or random access. We have already seen some results in Figure 3.4. The program creates an array corresponding to the working set size of elements of this type:

  struct l {
    struct l *n;
    long int pad[NPAD];
  };

All entries are chained in a circular list using the n element, either in sequential or random order. Advancing from one entry to the next always uses the pointer, even if the elements are laid out sequentially. The pad element is the payload and it can grow arbitrarily large. In some tests the data is modified, in others the program only performs read operations.

In the performance measurements we are talking about working set sizes. The working set is made up of an array of struct l elements. A working set of 2^N bytes contains

2^N/sizeof(struct l)

elements. Obviously sizeof(struct l) depends on the value of NPAD. For 32-bit systems, NPAD=7 means the size of each array element is 32 bytes, for 64-bit systems the size is 64 bytes.

Single Threaded Sequential Access

The simplest case is a simple walk over all the entries in the list. The list elements are laid out sequentially, densely packed. Whether the order of processing is forward or backward does not matter, the processor can deal with both directions equally well. What we measure here—and in all the following tests—is how long it takes to handle a single list element. The time unit is a processor cycle. Figure 3.10 shows the result. Unless otherwise specified, all measurements are made on a Pentium 4 machine in 64-bit mode which means the structure l with NPAD=0 is eight bytes in size.

Figure 3.10: Sequential Read Access, NPAD=0

Figure 3.11: Sequential Read for Several Sizes

The first two measurements are polluted by noise. The measured workload is simply too small to filter the effects of the rest of the system out. We can safely assume that the values are all at the 4 cycles level. With this in mind we can see three distinct levels:

• Up to a working set size of 2¹⁴ bytes.

• From 2¹⁵ bytes to 2²⁰ bytes.

• From 2²¹ bytes and up.

These steps can be easily explained: the processor has a 16kB L1d and 1MB L2. We do not see sharp edges in the transition from one level to the other because the caches are used by other parts of the system as well and so the cache is not exclusively available for the program data. Specifically the L2 cache is a unified cache and also used for the instructions (NB: Intel uses inclusive caches).

What is perhaps not quite expected are the actual times for the different working set sizes. The times for the L1d hits are expected: load times after an L1d hit are around 4 cycles on the P4. But what about the L2 accesses? Once the L1d is not sufficient to hold the data one might expect it would take 14 cycles or more per element since this is the access time for the L2. But the results show that only about 9 cycles are required. This discrepancy can be explained by the advanced logic in the processors. In anticipation of using consecutive memory regions, the processor prefetches the next cache line. This means that when the next line is actually used it is already halfway loaded. The delay required to wait for the next cache line to be loaded is therefore much less than the L2 access time.

The effect of prefetching is even more visible once the working set size grows beyond the L2 size. Before we said that a main memory access takes 200+ cycles. Only with effective prefetching is it possible for the processor to keep the access times as low as 9 cycles. As we can see from the difference between 200 and 9, this works out nicely.

We can observe the processor while prefetching, at least indirectly. In Figure 3.11 we see the times for the same working set sizes but this time we see the graphs for different sizes of the structure l. This means we have fewer but larger elements in the list. The different sizes have the effect that the distance between the n elements in the (still consecutive) list grows. In the four cases of the graph the distance is 0, 56, 120, and 248 bytes respectively.

At the bottom we can see the line from the previous graph, but this time it appears more or less as a flat line. The times for the other cases are simply so much worse. We can see in this graph, too, the three different levels and we see the large errors in the tests with the small working set sizes (ignore them again). The lines more or less all match each other as long as only the L1d is involved. There is no prefetching necessary so all element sizes just hit the L1d for each access.

For the L2 cache hits we see that the three new lines all pretty much match each other but that they are at a higher level (about 28). This is the level of the access time for the L2. This means prefetching from L2 into L1d is basically disabled. Even with NPAD=7 we need a new cache line for each iteration of the loop; for NPAD=0, instead, the loop has to iterate eight times before the next cache line is needed. The prefetch logic cannot load a new cache line every cycle. Therefore we see a stall to load from L2 in every iteration.

It gets even more interesting once the working set size exceeds the L2 capacity. Now all four lines vary widely. The different element sizes play obviously a big role in the difference in performance. The processor should recognize the size of the strides and not fetch unnecessary cache lines for NPAD=15 and 31 since the element size is smaller than the prefetch window (see Section 6.3.1). Where the element size is hampering the prefetching efforts is a result of a limitation of hardware prefetching: it cannot cross page boundaries. We are reducing the effectiveness of the hardware scheduler by 50% for each size increase. If the hardware prefetcher were allowed to cross page boundaries and the next page is not resident or valid the OS would have to get involved in locating the page. That means the program would experience a page fault it did not initiate itself. This is completely unacceptable since the processor does not know whether a page is not present or does not exist. In the latter case the OS would have to abort the process. In any case, given that, for NPAD=7 and higher, we need one cache line per list element the hardware prefetcher cannot do much. There simply is no time to load the data from memory since all the processor does is read one word and then load the next element.

Another big reason for the slowdown are the misses of the TLB cache. This is a cache where the results of the translation of a virtual address to a physical address are stored, as is explained in more detail in Section 4. The TLB cache is quite small since it has to be extremely fast. If more pages are accessed repeatedly than the TLB cache has entries for the translation from virtual to physical address has to be constantly repeated. This is a very costly operation. With larger element sizes the cost of a TLB lookup is amortized over fewer elements. That means the total number of TLB entries which have to be computed per list element is higher.

To observe the TLB effects we can run a different test. For one measurement we lay out the elements sequentially as usual. We use NPAD=7 for elements which occupy one entire cache line. For the second measurement we place each list element on a separate page. The rest of each page is left untouched and we do not count it in the total for the working set size. {Yes, this is a bit inconsistent because in the other tests we count the unused part of the struct in the element size and we could define NPAD so that each element fills a page. In that case the working set sizes would be very different. This is not the point of this test, though, and since prefetching is ineffective anyway this makes little difference.} The consequence is that, for the first measurement, each list iteration requires a new cache line and, for every 64 elements, a new page. For the second measurement each iteration requires loading a new cache line which is on a new page.

Figure 3.12: TLB Influence for Sequential Read

The result can be seen in Figure 3.12. The measurements were performed on the same machine as Figure 3.11. Due to limitations of the available RAM the working set size had to be restricted to 2²⁴ bytes which requires 1GB to place the objects on separate pages. The lower, red curve corresponds exactly to the NPAD=7 curve in Figure 3.11. We see the distinct steps showing the sizes of the L1d and L2 caches. The second curve looks radically different. The important feature is the huge spike starting when the working set size reaches 2¹³ bytes. This is when the TLB cache overflows. With an element size of 64 bytes we can compute that the TLB cache has 64 entries. There are no page faults affecting the cost since the program locks the memory to prevent it from being swapped out.

As can be seen the number of cycles it takes to compute the physical address and store it in the TLB is very high. The graph in Figure 3.12 shows the extreme case, but it should now be clear that a significant factor in the slowdown for larger NPAD values is the reduced efficiency of the TLB cache. Since the physical address has to be computed before a cache line can be read for either L2 or main memory the address translation penalties are additive to the memory access times. This in part explains why the total cost per list element for NPAD=31 is higher than the theoretical access time for the RAM.

Figure 3.13: Sequential Read and Write, NPAD=1

We can glimpse a few more details of the prefetch implementation by looking at the data of test runs where the list elements are modified. Figure 3.13 shows three lines. The element width is in all cases 16 bytes. The first line is the now familiar list walk which serves as a baseline. The second line, labeled “Inc”, simply increments the pad[0] member of the current element before going on to the next. The third line, labeled “Addnext0”, takes the pad[0] list element of the next element and adds it to the pad[0] member of the current list element.

The naïve assumption would be that the “Addnext0” test runs slower because it has more work to do. Before advancing to the next list element a value from that element has to be loaded. This is why it is surprising to see that this test actually runs, for some working set sizes, faster than the “Inc” test. The explanation for this is that the load from the next list element is basically a forced prefetch. Whenever the program advances to the next list element we know for sure that element is already in the L1d cache. As a result we see that the “Addnext0” performs as well as the simple “Follow” test as long as the working set size fits into the L2 cache.

The “Addnext0” test runs out of L2 faster than the “Inc” test, though. It needs more data loaded from main memory. This is why the “Addnext0” test reaches the 28 cycles level for a working set size of 2²¹ bytes. The 28 cycles level is twice as high as the 14 cycles level the “Follow” test reaches. This is easy to explain, too. Since the other two tests modify memory an L2 cache eviction to make room for new cache lines cannot simply discard the data. Instead it has to be written to memory. This means the available bandwidth on the FSB is cut in half, hence doubling the time it takes to transfer the data from main memory to L2.

Figure 3.14: Advantage of Larger L2/L3 Caches

One last aspect of the sequential, efficient cache handling is the size of the cache. This should be obvious but it still should be pointed out. Figure 3.14 shows the timing for the Increment benchmark with 128-byte elements (NPAD=15 on 64-bit machines). This time we see the measurement from three different machines. The first two machines are P4s, the last one a Core2 processor. The first two differentiate themselves by having different cache sizes. The first processor has a 32k L1d and an 1M L2. The second one has 16k L1d, 512k L2, and 2M L3. The Core2 processor has 32k L1d and 4M L2.

The interesting part of the graph is not necessarily how well the Core2 processor performs relative to the other two (although it is impressive). The main point of interest here is the region where the working set size is too large for the respective last level cache and the main memory gets heavily involved.

Set Size	Sequential					Random
	L2 Hit	L2 Miss	#Iter	Ratio Miss/Hit	L2 Accesses Per Iter	L2 Hit	L2 Miss	#Iter	Ratio Miss/Hit	L2 Accesses Per Iter
220	88,636	843	16,384	0.94%	5.5	30,462	4721	1,024	13.42%	34.4
221	88,105	1,584	8,192	1.77%	10.9	21,817	15,151	512	40.98%	72.2
222	88,106	1,600	4,096	1.78%	21.9	22,258	22,285	256	50.03%	174.0
223	88,104	1,614	2,048	1.80%	43.8	27,521	26,274	128	48.84%	420.3
224	88,114	1,655	1,024	1.84%	87.7	33,166	29,115	64	46.75%	973.1
225	88,112	1,730	512	1.93%	175.5	39,858	32,360	32	44.81%	2,256.8
226	88,112	1,906	256	2.12%	351.6	48,539	38,151	16	44.01%	5,418.1
227	88,114	2,244	128	2.48%	705.9	62,423	52,049	8	45.47%	14,309.0
228	88,120	2,939	64	3.23%	1,422.8	81,906	87,167	4	51.56%	42,268.3
229	88,137	4,318	32	4.67%	2,889.2	119,079	163,398	2	57.84%	141,238.5

Table 3.2: L2 Hits and Misses for Sequential and Random Walks, NPAD=0

As expected, the larger the last level cache is the longer the curve stays at the low level corresponding to the L2 access costs. The important part to notice is the performance advantage this provides. The second processor (which is slightly older) can perform the work on the working set of 2²⁰ bytes twice as fast as the first processor. All thanks to the increased last level cache size. The Core2 processor with its 4M L2 performs even better.

For a random workload this might not mean that much. But if the workload can be tailored to the size of the last level cache the program performance can be increased quite dramatically. This is why it sometimes is worthwhile to spend the extra money for a processor with a larger cache.

Single Threaded Random Access Measurements

We have seen that the processor is able to hide most of the main memory and even L2 access latency by prefetching cache lines into L2 and L1d. This can work well only when the memory access is predictable, though.

Figure 3.15: Sequential vs Random Read, NPAD=0

If the access is unpredictable or random the situation is quite different. Figure 3.15 compares the per-list-element times for the sequential access (same as in Figure 3.10) with the times when the list elements are randomly distributed in the working set. The order is determined by the linked list which is randomized. There is no way for the processor to reliably prefetch data. This can only work by chance if elements which are used shortly after one another are also close to each other in memory.

There are two important points to note in Figure 3.15. First, the large number is cycles needed for growing working set sizes. The machine makes it possible to access the main memory in 200-300 cycles but here we reach 450 cycles and more. We have seen this phenomenon before (compare Figure 3.11). The automatic prefetching is actually working to a disadvantage here.

The second interesting point is that the curve is not flattening at various plateaus as it has been for the sequential access cases. The curve keeps on rising. To explain this we can measure the L2 access of the program for the various working set sizes. The result can be seen in Figure 3.16 and Table 3.2.

The figure shows that, when the working set size is larger than the L2 size, the cache miss ratio (L2 misses / L2 access) starts to grow. The curve has a similar form to the one in Figure 3.15: it rises quickly, declines slightly, and starts to rise again. There is a strong correlation with the cycles per list element graph. The L2 miss rate will grow until it eventually reaches close to 100%. Given a large enough working set (and RAM) the probability that any of the randomly picked cache lines is in L2 or is in the process of being loaded can be reduced arbitrarily.

The increasing cache miss rate alone explains some of the costs. But there is another factor. Looking at Table 3.2 we can see in the L2/#Iter columns that the total number of L2 uses per iteration of the program is growing. Each working set is twice as large as the one before. So, without caching we would expect double the main memory accesses. With caches and (almost) perfect predictability we see the modest increase in the L2 use shown in the data for sequential access. The increase is due to the increase of the working set size and nothing else.

Figure 3.16: L2d Miss Ratio

Figure 3.17: Page-Wise Randomization, NPAD=7

For random access the per-element time increases by more than 100% for each doubling of the working set size. This means the average access time per list element increases since the working set size only doubles. The reason behind this is a rising rate of TLB misses. In Figure 3.17 we see the cost for random accesses for NPAD=7. Only this time the randomization is modified. While in the normal case the entire list of randomized as one block (indicated by the label ∞) the other 11 curves show randomizations which are performed in smaller blocks. For the curve labeled '60' each set of 60 pages (245.760 bytes) is randomized individually. That means all list elements in the block are traversed before going over to an element in the next block. This has the effect that number of TLB entries which are used at any one time is limited.

The element size for NPAD=7 is 64 bytes, which corresponds to the cache line size. Due to the randomized order of the list elements it is unlikely that the hardware prefetcher has any effect, most certainly not for more than a handful of elements. This means the L2 cache miss rate does not differ significantly from the randomization of the entire list in one block. The performance of the test with increasing block size approaches asymptotically the curve for the one-block randomization. This means the performance of this latter test case is significantly influenced by the TLB misses. If the TLB misses can be lowered the performance increases significantly (in one test we will see later up to 38%).

3.3.3 Write Behavior

Before we start looking at the cache behavior when multiple execution contexts (threads or processes) use the same memory we have to explore a detail of cache implementations. Caches are supposed to be coherent and this coherency is supposed to be completely transparent for the userlevel code. Kernel code is a different story; it occasionally requires cache flushes.

This specifically means that, if a cache line is modified, the result for the system after this point in time is the same as if there were no cache at all and the main memory location itself had been modified. This can be implemented in two ways or policies:

• write-through cache implementation;
• write-back cache implementation.

The write-through cache is the simplest way to implement cache coherency. If the cache line is written to, the processor immediately also writes the cache line into main memory. This ensures that, at all times, the main memory and cache are in sync. The cache content could simply be discarded whenever a cache line is replaced. This cache policy is simple but not very fast. A program which, for instance, modifies a local variable over and over again would create a lot of traffic on the FSB even though the data is likely not used anywhere else and might be short-lived.

The write-back policy is more sophisticated. Here the processor does not immediately write the modified cache line back to main memory. Instead, the cache line is only marked as dirty. When the cache line is dropped from the cache at some point in the future the dirty bit will instruct the processor to write the data back at that time instead of just discarding the content.

Write-back caches have the chance to be significantly better performing, which is why most memory in a system with a decent processor is cached this way. The processor can even take advantage of free capacity on the FSB to store the content of a cache line before the line has to be evacuated. This allows the dirty bit to be cleared and the processor can just drop the cache line when the room in the cache is needed.

But there is a significant problem with the write-back implementation. When more than one processor (or core or hyper-thread) is available and accessing the same memory it must still be assured that both processors see the same memory content at all times. If a cache line is dirty on one processor (i.e., it has not been written back yet) and a second processor tries to read the same memory location, the read operation cannot just go out to the main memory. Instead the content of the first processor's cache line is needed. In the next section we will see how this is currently implemented.

Before we get to this there are two more cache policies to mention:

• write-combining; and
• uncacheable.

Both these policies are used for special regions of the address space which are not backed by real RAM. The kernel sets up these policies for the address ranges (on x86 processors using the Memory Type Range Registers, MTRRs) and the rest happens automatically. The MTRRs are also usable to select between write-through and write-back policies.

Write-combining is a limited caching optimization more often used for RAM on devices such as graphics cards. Since the transfer costs to the devices are much higher than the local RAM access it is even more important to avoid doing too many transfers. Transferring an entire cache line just because a word in the line has been written is wasteful if the next operation modifies the next word. One can easily imagine that this is a common occurrence, the memory for horizontal neighboring pixels on a screen are in most cases neighbors, too. As the name suggests, write-combining combines multiple write accesses before the cache line is written out. In ideal cases the entire cache line is modified word by word and, only after the last word is written, the cache line is written to the device. This can speed up access to RAM on devices significantly.

Finally there is uncacheable memory. This usually means the memory location is not backed by RAM at all. It might be a special address which is hardcoded to have some functionality outside the CPU. For commodity hardware this most often is the case for memory mapped address ranges which translate to accesses to cards and devices attached to a bus (PCIe etc). On embedded boards one sometimes finds such a memory address which can be used to turn an LED on and off. Caching such an address would obviously be a bad idea. LEDs in this context are used for debugging or status reports and one wants to see this as soon as possible. The memory on PCIe cards can change without the CPU's interaction, so this memory should not be cached.

3.3.4 Multi-Processor Support

In the previous section we have already pointed out the problem we have when multiple processors come into play. Even multi-core processors have the problem for those cache levels which are not shared (at least the L1d).

It is completely impractical to provide direct access from one processor to the cache of another processor. The connection is simply not fast enough, for a start. The practical alternative is to transfer the cache content over to the other processor in case it is needed. Note that this also applies to caches which are not shared on the same processor.

The question now is when does this cache line transfer have to happen? This question is pretty easy to answer: when one processor needs a cache line which is dirty in another processor's cache for reading or writing. But how can a processor determine whether a cache line is dirty in another processor's cache? Assuming it is just because a cache line is loaded by another processor would be suboptimal (at best). Usually the majority of memory accesses are read accesses and the resulting cache lines are not dirty. Processor operations on cache lines are frequent (of course, why else would we have this paper?) which means broadcasting information about changed cache lines after each write access would be impractical.

What developed over the years is the MESI cache coherency protocol (Modified, Exclusive, Shared, Invalid). The protocol is named after the four states a cache line can be in when using the MESI protocol:

• Modified: The local processor has modified the cache line. This also implies it is the only copy in any cache.

• Exclusive: The cache line is not modified but known to not be loaded into any other processor's cache.

• Shared: The cache line is not modified and might exist in another processor's cache.

• Invalid: The cache line is invalid, i.e., unused.

This protocol developed over the years from simpler versions which were less complicated but also less efficient. With these four states it is possible to efficiently implement write-back caches while also supporting concurrent use of read-only data on different processors.

Figure 3.18: MESI Protocol Transitions

The state changes are accomplished without too much effort by the processors listening, or snooping, on the other processors' work. Certain operations a processor performs are announced on external pins and thus make the processor's cache handling visible to the outside. The address of the cache line in question is visible on the address bus. In the following description of the states and their transitions (shown in Figure 3.18) we will point out when the bus is involved.

Initially all cache lines are empty and hence also Invalid. If data is loaded into the cache for writing the cache changes to Modified. If the data is loaded for reading the new state depends on whether another processor has the cache line loaded as well. If this is the case then the new state is Shared, otherwise Exclusive.

If a Modified cache line is read from or written to on the local processor, the instruction can use the current cache content and the state does not change. If a second processor wants to read from the cache line the first processor has to send the content of its cache to the second processor and then it can change the state to Shared. The data sent to the second processor is also received and processed by the memory controller which stores the content in memory. If this did not happen the cache line could not be marked as Shared. If the second processor wants to write to the cache line the first processor sends the cache line content and marks the cache line locally as Invalid. This is the infamous “Request For Ownership” (RFO) operation. Performing this operation in the last level cache, just like the I→M transition is comparatively expensive. For write-through caches we also have to add the time it takes to write the new cache line content to the next higher-level cache or the main memory, further increasing the cost.

If a cache line is in the Shared state and the local processor reads from it no state change is necessary and the read request can be fulfilled from the cache. If the cache line is locally written to the cache line can be used as well but the state changes to Modified. It also requires that all other possible copies of the cache line in other processors are marked as Invalid. Therefore the write operation has to be announced to the other processors via an RFO message. If the cache line is requested for reading by a second processor nothing has to happen. The main memory contains the current data and the local state is already Shared. In case a second processor wants to write to the cache line (RFO) the cache line is simply marked Invalid. No bus operation is needed.

The Exclusive state is mostly identical to the Shared state with one crucial difference: a local write operation does not have to be announced on the bus. The local cache copy is known to be the only one. This can be a huge advantage so the processor will try to keep as many cache lines as possible in the Exclusive state instead of the Shared state. The latter is the fallback in case the information is not available at that moment. The Exclusive state can also be left out completely without causing functional problems. It is only the performance that will suffer since the E→M transition is much faster than the S→M transition.

From this description of the state transitions it should be clear where the costs specific to multi-processor operations are. Yes, filling caches is still expensive but now we also have to look out for RFO messages. Whenever such a message has to be sent things are going to be slow.

There are two situations when RFO messages are necessary:

• A thread is migrated from one processor to another and all the cache lines have to be moved over to the new processor once.

• A cache line is truly needed in two different processors. {At a smaller level the same is true for two cores on the same processor. The costs are just a bit smaller. The RFO message is likely to be sent many times.}

In multi-thread or multi-process programs there is always some need for synchronization; this synchronization is implemented using memory. So there are some valid RFO messages. They still have to be kept as infrequent as possible. There are other sources of RFO messages, though. In Section 6 we will explain these scenarios. The Cache coherency protocol messages must be distributed among the processors of the system. A MESI transition cannot happen until it is clear that all the processors in the system have had a chance to reply to the message. That means that the longest possible time a reply can take determines the speed of the coherency protocol. {Which is why we see nowadays, for instance, AMD Opteron systems with three sockets. Each processor is exactly one hop away given that the processors only have three hyperlinks and one is needed for the Southbridge connection.} Collisions on the bus are possible, latency can be high in NUMA systems, and of course sheer traffic volume can slow things down. All good reasons to focus on avoiding unnecessary traffic.

There is one more problem related to having more than one processor in play. The effects are highly machine specific but in principle the problem always exists: the FSB is a shared resource. In most machines all processors are connected via one single bus to the memory controller (see Figure 2.1). If a single processor can saturate the bus (as is usually the case) then two or four processors sharing the same bus will restrict the bandwidth available to each processor even more.

Even if each processor has its own bus to the memory controller as in Figure 2.2 there is still the bus to the memory modules. Usually this is one bus but, even in the extended model in Figure 2.2, concurrent accesses to the same memory module will limit the bandwidth.

The same is true with the AMD model where each processor can have local memory. Yes, all processors can concurrently access their local memory quickly. But multi-thread and multi-process programs--at least from time to time--have to access the same memory regions to synchronize.

Concurrency is severely limited by the finite bandwidth available for the implementation of the necessary synchronization. Programs need to be carefully designed to minimize accesses from different processors and cores to the same memory locations. The following measurements will show this and the other cache effects related to multi-threaded code.

Multi Threaded Measurements

To ensure that the gravity of the problems introduced by concurrently using the same cache lines on different processors is understood, we will look here at some more performance graphs for the same program we used before. This time, though, more than one thread is running at the same time. What is measured is the fastest runtime of any of the threads. This means the time for a complete run when all threads are done is even higher. The machine used has four processors; the tests use up to four threads. All processors share one bus to the memory controller and there is only one bus to the memory modules.

Figure 3.19: Sequential Read Access, Multiple Threads

Figure 3.19 shows the performance for sequential read-only access for 128 bytes entries (NPAD=15 on 64-bit machines). For the curve for one thread we can expect a curve similar to Figure 3.11. The measurements are for a different machine so the actual numbers vary.

The important part in this figure is of course the behavior when running multiple threads. Note that no memory is modified and no attempts are made to keep the threads in sync when walking the linked list. Even though no RFO messages are necessary and all the cache lines can be shared, we see up to an 18% performance decrease for the fastest thread when two threads are used and up to 34% when four threads are used. Since no cache lines have to be transported between the processors this slowdown is solely caused by one or both of the two bottlenecks: the shared bus from the processor to the memory controller and bus from the memory controller to the memory modules. Once the working set size is larger than the L3 cache in this machine all three threads will be prefetching new list elements. Even with two threads the available bandwidth is not sufficient to scale linearly (i.e., have no penalty from running multiple threads).

When we modify memory things get even uglier. Figure 3.20 shows the results for the sequential Increment test.

Figure 3.20: Sequential Increment, Multiple Threads

This graph is using a logarithmic scale for the Y axis. So, do not be fooled by the apparently small differences. We still have about a 18% penalty for running two threads and now an amazing 93% penalty for running four threads. This means the prefetch traffic together with the write-back traffic is pretty much saturating the bus when four threads are used.

We use the logarithmic scale to show the results for the L1d range. What can be seen is that, as soon as more than one thread is running, the L1d is basically ineffective. The single-thread access times exceed 20 cycles only when the L1d is not sufficient to hold the working set. When multiple threads are running, those access times are hit immediately, even with the smallest working set sizes.

One aspect of the problem is not shown here. It is hard to measure with this specific test program. Even though the test modifies memory and we therefore must expect RFO messages we do not see higher costs for the L2 range when more than one thread is used. The program would have to use a large amount of memory and all threads must access the same memory in parallel. This is hard to achieve without a lot of synchronization which would then dominate the execution time.

Figure 3.21: Random Addnextlast, Multiple Threads

Finally in Figure 3.21 we have the numbers for the Addnextlast test with random access of memory. This figure is provided mainly to show to the appallingly high numbers. It now take around 1,500 cycles to process a single list element in the extreme case. The use of more threads is even more questionable. We can summarize the efficiency of multiple thread use in a table.

#Threads	Seq Read	Seq Inc	Rand Add
2	1.69	1.69	1.54
4	2.98	2.07	1.65

Table 3.3: Efficiency for Multiple Threads

The table shows the efficiency for the multi-thread run with the largest working set size in the three figures on Figure 3.21. The number shows the best possible speed-up the test program incurs for the largest working set size by using two or four threads. For two threads the theoretical limits for the speed-up are 2 and, for four threads, 4. The numbers for two threads are not that bad. But for four threads the numbers for the last test show that it is almost not worth it to scale beyond two threads. The additional benefit is minuscule. We can see this more easily if we represent the data in Figure 3.21 a bit differently.

Figure 3.22: Speed-Up Through Parallelism

The curves in Figure 3.22 show the speed-up factors, i.e., relative performance compared to the code executed by a single thread. We have to ignore the smallest sizes, the measurements are not accurate enough. For the range of the L2 and L3 cache we can see that we indeed achieve almost linear acceleration. We almost reach factors of 2 and 4 respectively. But as soon as the L3 cache is not sufficient to hold the working set the numbers crash. They crash to the point that the speed-up of two and four threads is identical (see the fourth column in Table 3.3). This is one of the reasons why one can hardly find motherboard with sockets for more than four CPUs all using the same memory controller. Machines with more processors have to be built differently (see Section 5).

These numbers are not universal. In some cases even working sets which fit into the last level cache will not allow linear speed-ups. In fact, this is the norm since threads are usually not as decoupled as is the case in this test program. On the other hand it is possible to work with large working sets and still take advantage of more than two threads. Doing this requires thought, though. We will talk about some approaches in Section 6.

Special Case: Hyper-Threads

Hyper-Threads (sometimes called Symmetric Multi-Threading, SMT) are implemented by the CPU and are a special case since the individual threads cannot really run concurrently. They all share almost all the processing resources except for the register set. Individual cores and CPUs still work in parallel but the threads implemented on each core are limited by this restriction. In theory there can be many threads per core but, so far, Intel's CPUs at most have two threads per core. The CPU is responsible for time-multiplexing the threads. This alone would not make much sense, though. The real advantage is that the CPU can schedule another hyper-thread when the currently running hyper-thread is delayed. In most cases this is a delay caused by memory accesses.

If two threads are running on one hyper-threaded core the program is only more efficient than the single-threaded code if the combined runtime of both threads is lower than the runtime of the single-threaded code. This is possible by overlapping the wait times for different memory accesses which usually would happen sequentially. A simple calculation shows the minimum requirement on the cache hit rate to achieve a certain speed-up.

The execution time for a program can be approximated with a simple model with only one level of cache as follows (see [htimpact]):

T_exe = N[(1-F_mem)T_proc + F_mem(G_hitT_cache + (1-G_hit)T_miss)]

The meaning of the variables is as follows:

N	=	Number of instructions.
Fmem	=	Fraction of N that access memory.
Ghit	=	Fraction of loads that hit the cache.
Tproc	=	Number of cycles per instruction.
Tcache	=	Number of cycles for cache hit.
Tmiss	=	Number of cycles for cache miss.
Texe	=	Execution time for program.

For it to make any sense to use two threads the execution time of each of the two threads must be at most half of that of the single-threaded code. The only variable on either side is the number of cache hits. If we solve the equation for the minimum cache hit rate required to not slow down the thread execution by 50% or more we get the graph in Figure 3.23.

Figure 3.23: Minimum Cache Hit Rate For Speed-Up

The X–axis represents the cache hit rate G_hit of the single-thread code. The Y–axis shows the required cache hit rate for the multi-threaded code. This value can never be higher than the single-threaded hit rate since, otherwise, the single-threaded code would use that improved code, too. For single-threaded hit rates below 55% the program can in all cases benefit from using threads. The CPU is more or less idle enough due to cache misses to enable running a second hyper-thread.

The green area is the target. If the slowdown for the thread is less than 50% and the workload of each thread is halved the combined runtime might be less than the single-thread runtime. For the modeled system here (numbers for a P4 with hyper-threads were used) a program with a hit rate of 60% for the single-threaded code requires a hit rate of at least 10% for the dual-threaded program. That is usually doable. But if the single-threaded code has a hit rate of 95% then the multi-threaded code needs a hit rate of at least 80%. That is harder. Especially, and this is the problem with hyper-threads, because now the effective cache size (L1d here, in practice also L2 and so on) available to each hyper-thread is cut in half. Both hyper-threads use the same cache to load their data. If the working set of the two threads is non-overlapping the original 95% hit rate could also be cut in half and is therefore much lower than the required 80%.

Hyper-Threads are therefore only useful in a limited range of situations. The cache hit rate of the single-threaded code must be low enough that given the equations above and reduced cache size the new hit rate still meets the goal. Then and only then can it make any sense at all to use hyper-threads. Whether the result is faster in practice depends on whether the processor is sufficiently able to overlap the wait times in one thread with execution times in the other threads. The overhead of parallelizing the code must be added to the new total runtime and this additional cost often cannot be neglected.

In Section 6.3.4 we will see a technique where threads collaborate closely and the tight coupling through the common cache is actually an advantage. This technique can be applicable to many situations if only the programmers are willing to put in the time and energy to extend their code.

What should be clear is that if the two hyper-threads execute completely different code (i.e., the two threads are treated like separate processors by the OS to execute separate processes) the cache size is indeed cut in half which means a significant increase in cache misses. Such OS scheduling practices are questionable unless the caches are sufficiently large. Unless the workload for the machine consists of processes which, through their design, can indeed benefit from hyper-threads it might be best to turn off hyper-threads in the computer's BIOS. {Another reason to keep hyper-threads enabled is debugging. SMT is astonishingly good at finding some sets of problems in parallel code.}

3.3.5 Other Details

So far we talked about the address as consisting of three parts, tag, set index, and cache line offset. But what address is actually used? All relevant processors today provide virtual address spaces to processes, which means that there are two different kinds of addresses: virtual and physical.

The problem with virtual addresses is that they are not unique. A virtual address can, over time, refer to different physical memory addresses. The same address in different process also likely refers to different physical addresses. So it is always better to use the physical memory address, right?

The problem here is that instructions use virtual addresses and these have to be translated with the help of the Memory Management Unit (MMU) into physical addresses. This is a non-trivial operation. In the pipeline to execute an instruction the physical address might only be available at a later stage. This means that the cache logic has to be very quick in determining whether the memory location is cached. If virtual addresses could be used the cache lookup can happen much earlier in the pipeline and in case of a cache hit the memory content can be made available. The result is that more of the memory access costs could be hidden by the pipeline.

Processor designers are currently using virtual address tagging for the first level caches. These caches are rather small and can be cleared without too much pain. At least partial clearing the cache is necessary if the page table tree of a process changes. It might be possible to avoid a complete flush if the processor has an instruction which specifies the virtual address range which has changed. Given the low latency of L1i and L1d caches (~3 cycles) using virtual addresses is almost mandatory.

For larger caches including L2, L3, ... caches physical address tagging is needed. These caches have a higher latency and the virtual→physical address translation can finish in time. Because these caches are larger (i.e., a lot of information is lost when they are flushed) and refilling them takes a long time due to the main memory access latency, flushing them often would be costly.

It should, in general, not be necessary to know about the details of the address handling in those caches. They cannot be changed and all the factors which would influence the performance are normally something which should be avoided or is associated with high cost. Overflowing the cache capacity is bad and all caches run into problems early if the majority of the used cache lines fall into the same set. The latter can be avoided with virtually addressed caches but is impossible for user-level processes to avoid for caches addressed using physical addresses. The only detail one might want to keep in mind is to not map the same physical memory location to two or more virtual addresses in the same process, if at all possible.

Another detail of the caches which is rather uninteresting to programmers is the cache replacement strategy. Most caches evict the Least Recently Used (LRU) element first. This is always a good default strategy. With larger associativity (and associativity might indeed grow further in the coming years due to the addition of more cores) maintaining the LRU list becomes more and more expensive and we might see different strategies adopted.

As for the cache replacement there is not much a programmer can do. If the cache is using physical address tags there is no way to find out how the virtual addresses correlate with the cache sets. It might be that cache lines in all logical pages are mapped to the same cache sets, leaving much of the cache unused. If anything, it is the job of the OS to arrange that this does not happen too often.

With the advent of virtualization things get even more complicated. Now not even the OS has control over the assignment of physical memory. The Virtual Machine Monitor (VMM, aka hypervisor) is responsible for the physical memory assignment.

The best a programmer can do is to a) use logical memory pages completely and b) use page sizes as large as meaningful to diversify the physical addresses as much as possible. Larger page sizes have other benefits, too, but this is another topic (see Section 4).

3.4 Instruction Cache

Not just the data used by the processor is cached; the instructions executed by the processor are also cached. However, this cache is much less problematic than the data cache. There are several reasons:

• The quantity of code which is executed depends on the size of the code that is needed. The size of the code in general depends on the complexity of the problem. The complexity of the problem is fixed.

• While the program's data handling is designed by the programmer the program's instructions are usually generated by a compiler. The compiler writers know about the rules for good code generation.

• Program flow is much more predictable than data access patterns. Today's CPUs are very good at detecting patterns. This helps with prefetching.

• Code always has quite good spatial and temporal locality.

There are a few rules programmers should follow but these mainly consist of rules on how to use the tools. We will discuss them in Section 6. Here we talk only about the technical details of the instruction cache.

Ever since the core clock of CPUs increased dramatically and the difference in speed between cache (even first level cache) and core grew, CPUs have been pipelined. That means the execution of an instruction happens in stages. First an instruction is decoded, then the parameters are prepared, and finally it is executed. Such a pipeline can be quite long (> 20 stages for Intel's Netburst architecture). A long pipeline means that if the pipeline stalls (i.e., the instruction flow through it is interrupted) it takes a while to get up to speed again. Pipeline stalls happen, for instance, if the location of the next instruction cannot be correctly predicted or if it takes too long to load the next instruction (e.g., when it has to be read from memory).

As a result CPU designers spend a lot of time and chip real estate on branch prediction so that pipeline stalls happen as infrequently as possible.

On CISC processors the decoding stage can also take some time. The x86 and x86-64 processors are especially affected. In recent years these processors therefore do not cache the raw byte sequence of the instructions in L1i but instead they cache the decoded instructions. L1i in this case is called the “trace cache”. Trace caching allows the processor to skip over the first steps of the pipeline in case of a cache hit which is especially good if the pipeline stalled.

As said before, the caches from L2 on are unified caches which contain both code and data. Obviously here the code is cached in the byte sequence form and not decoded.

To achieve the best performance there are only a few rules related to the instruction cache:

1. Generate code which is as small as possible. There are exceptions when software pipelining for the sake of using pipelines requires creating more code or where the overhead of using small code is too high.

2. Whenever possible, help the processor to make good prefetching decisions. This can be done through code layout or with explicit prefetching.

These rules are usually enforced by the code generation of a compiler. There are a few things the programmer can do and we will talk about them in Section 6.

3.4.1 Self Modifying Code

In early computer days memory was a premium. People went to great lengths to reduce the size of the program to make more room for program data. One trick frequently deployed was to change the program itself over time. Such Self Modifying Code (SMC) is occasionally still found, these days mostly for performance reasons or in security exploits.

SMC should in general be avoided. Though it is generally executed correctly there are boundary cases in which it is not and it creates performance problems if not done correctly. Obviously, code which is changed cannot be kept in the trace cache which contains the decoded instructions. But even if the trace cache is not used because the code has not been executed at all (or for some time) the processor might have problems. If an upcoming instruction is changed while it already entered the pipeline the processor has to throw away a lot of work and start all over again. There are even situations where most of the state of the processor has to be tossed away.

Finally, since the processor assumes - for simplicity reasons and because it is true in 99.9999999% of all cases - that the code pages are immutable, the L1i implementation does not use the MESI protocol but instead a simplified SI protocol. This means if modifications are detected a lot of pessimistic assumptions have to be made.

It is highly advised to avoid SMC whenever possible. Memory is not such a scarce resource anymore. It is better to write separate functions instead of modifying one function according to specific needs. Maybe one day SMC support can be made optional and we can detect exploit code trying to modify code this way. If SMC absolutely has to be used, the write operations should bypass the cache as to not create problems with data in L1d needed in L1i. See Section 6.1 for more information on these instructions.

Normally on Linux it is easy to recognize programs which contain SMC. All program code is write-protected when built with the regular toolchain. The programmer has to perform significant magic at link time to create an executable where the code pages are writable. When this happens, modern Intel x86 and x86-64 processors have dedicated performance counters which count uses of self-modifying code. With the help of these counters it is quite easily possible to recognize programs with SMC even if the program will succeed due to relaxed permissions.

3.5 Cache Miss Factors

We have already seen that when memory accesses miss the caches, the costs skyrocket. Sometimes this is not avoidable and it is important to understand the actual costs and what can be done to mitigate the problem.

3.5.1 Cache and Memory Bandwidth

To get a better understanding of the capabilities of the processors we measure the bandwidth available in optimal circumstances. This measurement is especially interesting since different processor versions vary widely. This is why this section is filled with the data of several different machines. The program to measure performance uses the SSE instructions of the x86 and x86-64 processors to load or store 16 bytes at once. The working set is increased from 1kB to 512MB just as in our other tests and it is measured how many bytes per cycle can be loaded or stored.

Figure 3.24: Pentium 4 Bandwidth

Figure 3.24 shows the performance on a 64-bit Intel Netburst processor. For working set sizes which fit into L1d the processor is able to read the full 16 bytes per cycle, i.e., one load instruction is performed per cycle (the movaps instruction moves 16 bytes at once). The test does not do anything with the read data, we test only the read instructions themselves. As soon as the L1d is not sufficient anymore the performance goes down dramatically to less than 6 bytes per cycle. The step at 2¹⁸ bytes is due to the exhaustion of the DTLB cache which means additional work for each new page. Since the reading is sequential prefetching can predict the accesses perfectly and the FSB can stream the memory content at about 5.3 bytes per cycle for all sizes of the working set. The prefetched data is not propagated into L1d, though. These are of course numbers which will never be achievable in a real program. Think of them as practical limits.

What is more astonishing than the read performance is the write and copy performance. The write performance, even for small working set sizes, does not ever rise above 4 bytes per cycle. This indicates that, in these Netburst processors, Intel elected to use a Write-Through mode for L1d where the performance is obviously limited by the L2 speed. This also means that the performance of the copy test, which copies from one memory region into a second, non-overlapping memory region, is not significantly worse. The necessary read operations are so much faster and can partially overlap with the write operations. The most noteworthy detail of the write and copy measurements is the low performance once the L2 cache is not sufficient anymore. The performance drops to 0.5 bytes per cycle! That means write operations are by a factor of ten slower than the read operations. This means optimizing those operations is even more important for the performance of the program.

In Figure 3.25 we see the results on the same processor but with two threads running, one pinned to each of the two hyper-threads of the processor.

Figure 3.25: P4 Bandwidth with 2 Hyper-Threads

The graph is shown at the same scale as the previous one to illustrate the differences and the curves are a bit jittery simply because of the problem of measuring two concurrent threads. The results are as expected. Since the hyper-threads share all the resources except the registers each thread has only half the cache and bandwidth available. That means even though each thread has to wait a lot and could award the other thread with execution time this does not make any difference since the other thread also has to wait for the memory. This truly shows the worst possible use of hyper-threads.

Figure 3.26: Core 2 Bandwidth

Compared to Figures 3.24 and 3.25 the results in Figures 3.26 and 3.27 look quite different for an Intel Core 2 processor. This is a dual-core processor with shared L2 which is four times as big as the L2 on the P4 machine. This only explains the delayed drop-off of the write and copy performance, though.

There are much bigger differences. The read performance throughout the working set range hovers around the optimal 16 bytes per cycle. The drop-off in the read performance after 2²⁰ bytes is again due to the working set being too big for the DTLB. Achieving these high numbers means the processor is not only able to prefetch the data and transport the data in time. It also means the data is prefetched into L1d.

The write and copy performance is dramatically different, too. The processor does not have a Write-Through policy; written data is stored in L1d and only evicted when necessary. This allows for write speeds close to the optimal 16 bytes per cycle. Once L1d is not sufficient anymore the performance drops significantly. As with the Netburst processor, the write performance is significantly lower. Due to the high read performance the difference is even higher here. In fact, when even the L2 is not sufficient anymore the speed difference increases to a factor of 20! This does not mean the Core 2 processors perform poorly. To the contrary, their performance is always better than the Netburst core's.

Figure 3.27: Core 2 Bandwidth with 2 Threads

In Figure 3.27, the test runs two threads, one on each of the two cores of the Core 2 processor. Both threads access the same memory, not necessarily perfectly in sync, though. The results for the read performance are not different from the single-threaded case. A few more jitters are visible which is to be expected in any multi-threaded test case.

The interesting point is the write and copy performance for working set sizes which would fit into L1d. As can be seen in the figure, the performance is the same as if the data had to be read from the main memory. Both threads compete for the same memory location and RFO messages for the cache lines have to be sent. The problematic point is that these requests are not handled at the speed of the L2 cache, even though both cores share the cache. Once the L1d cache is not sufficient anymore modified entries are flushed from each core's L1d into the shared L2. At that point the performance increases significantly since now the L1d misses are satisfied by the L2 cache and RFO messages are only needed when the data has not yet been flushed. This is why we see a 50% reduction in speed for these sizes of the working set. The asymptotic behavior is as expected: since both cores share the same FSB each core gets half the FSB bandwidth which means for large working sets each thread's performance is about half that of the single threaded case.

Because there are significant differences between the processor versions of one vendor it is certainly worthwhile looking at the performance of other vendors' processors, too. Figure 3.28 shows the performance of an AMD family 10h Opteron processor. This processor has 64kB L1d, 512kB L2, and 2MB of L3. The L3 cache is shared between all cores of the processor. The results of the performance test can be seen in Figure 3.28.

Figure 3.28: AMD Family 10h Opteron Bandwidth

The first detail one notices about the numbers is that the processor is capable of handling two instructions per cycle if the L1d cache is sufficient. The read performance exceeds 32 bytes per cycle and even the write performance is, with 18.7 bytes per cycle, high. The read curve flattens quickly, though, and is, with 2.3 bytes per cycle, pretty low. The processor for this test does not prefetch any data, at least not efficiently.

The write curve on the other hand performs according to the sizes of the various caches. The peak performance is achieved for the full size of the L1d, going down to 6 bytes per cycle for L2, to 2.8 bytes per cycle for L3, and finally .5 bytes per cycle if not even L3 can hold all the data. The performance for the L1d cache exceeds that of the (older) Core 2 processor, the L2 access is equally fast (with the Core 2 having a larger cache), and the L3 and main memory access is slower.

The copy performance cannot be better than either the read or write performance. This is why we see the curve initially dominated by the read performance and later by the write performance.

The multi-thread performance of the Opteron processor is shown in Figure 3.29.

Figure 3.29: AMD Fam 10h Bandwidth with 2 Threads

The read performance is largely unaffected. Each thread's L1d and L2 works as before and the L3 cache is in this case not prefetched very well either. The two threads do not unduly stress the L3 for their purpose. The big problem in this test is the write performance. All data the threads share has to go through the L3 cache. This sharing seems to be quite inefficient since even if the L3 cache size is sufficient to hold the entire working set the cost is significantly higher than an L3 access. Comparing this graph with Figure 3.27 we see that the two threads of the Core 2 processor operate at the speed of the shared L2 cache for the appropriate range of working set sizes. This level of performance is achieved for the Opteron processor only for a very small range of the working set sizes and even here it approaches only the speed of the L3 which is slower than the Core 2's L2.

3.5.2 Critical Word Load

Memory is transferred from the main memory into the caches in blocks which are smaller than the cache line size. Today 64 bits are transferred at once and the cache line size is 64 or 128 bytes. This means 8 or 16 transfers per cache line are needed.

The DRAM chips can transfer those 64-bit blocks in burst mode. This can fill the cache line without any further commands from the memory controller and the possibly associated delays. If the processor prefetches cache lines this is probably the best way to operate.

If a program's cache access of the data or instruction caches misses (that means, it is a compulsory cache miss, because the data is used for the first time, or a capacity cache miss, because the limited cache size requires eviction of the cache line) the situation is different. The word inside the cache line which is required for the program to continue might not be the first word in the cache line. Even in burst mode and with double data rate transfer the individual 64-bit blocks arrive at noticeably different times. Each block arrives 4 CPU cycles or more later than the previous one. If the word the program needs to continue is the eighth of the cache line, the program has to wait an additional 30 cycles or more after the first word arrives.

Things do not necessarily have to be like this. The memory controller is free to request the words of the cache line in a different order. The processor can communicate which word the program is waiting on, the critical word, and the memory controller can request this word first. Once the word arrives the program can continue while the rest of the cache line arrives and the cache is not yet in a consistent state. This technique is called Critical Word First & Early Restart.

Processors nowadays implement this technique but there are situations when that is not possible. If the processor prefetches data the critical word is not known. Should the processor request the cache line during the time the prefetch operation is in flight it will have to wait until the critical word arrives without being able to influence the order.

Figure 3.30: Critical Word at End of Cache Line

Even with these optimizations in place the position of the critical word on a cache line matters. Figure 3.30 shows the Follow test for sequential and random access. Shown is the slowdown of running the test with the pointer which is chased in the first word versus the case when the pointer is in the last word. The element size is 64 bytes, corresponding the cache line size. The numbers are quite noisy but it can be seen that, as soon as the L2 is not sufficient to hold the working set size, the performance of the case where the critical word is at the end is about 0.7% slower. The sequential access appears to be affected a bit more. This would be consistent with the aforementioned problem when prefetching the next cache line.

3.5.3 Cache Placement

Where the caches are placed in relationship to the hyper-threads, cores, and processors is not under control of the programmer. But programmers can determine where the threads are executed and then it becomes important how the caches relate to the used CPUs.

Here we will not go into details of when to select what cores to run the threads. We will only describe architecture details which the programmer has to take into account when setting the affinity of the threads.

Hyper-threads, by definition share everything but the register set. This includes the L1 caches. There is not much more to say here. The fun starts with the individual cores of a processor. Each core has at least its own L1 caches. Aside from this there are today not many details in common:

• Early multi-core processors had separate L2 caches and no higher caches.

• Later Intel models had shared L2 caches for dual-core processors. For quad-core processors we have to deal with separate L2 caches for each pair of two cores. There are no higher level caches.

• AMD's family 10h processors have separate L2 caches and a unified L3 cache.

A lot has been written in the propaganda material of the processor vendors about the advantage of their respective models. Separate L2 caches have an advantage if the working sets handled by the cores do not overlap. This works well for single-threaded programs. Since this is still often the reality today this approach does not perform too badly. But there is always some overlap. The caches all contain the most actively used parts of the common runtime libraries which means some cache space is wasted.

Completely sharing all caches beside L1 as Intel's dual-core processors do can have a big advantage. If the working set of the threads working on the two cores overlaps significantly the total available cache memory is increased and working sets can be bigger without performance degradation. If the working sets do not overlap Intel's Advanced Smart Cache management is supposed to prevent any one core from monopolizing the entire cache.

If both cores use about half the cache for their respective working sets there is some friction, though. The cache constantly has to weigh the two cores' cache use and the evictions performed as part of this rebalancing might be chosen poorly. To see the problems we look at the results of yet another test program.

Figure 3.31: Bandwidth with two Processes

The test program has one process constantly reading or writing, using SSE instructions, a 2MB block of memory. 2MB was chosen because this is half the size of the L2 cache of this Core 2 processor. The process is pinned to one core while a second process is pinned to the other core. This second process reads and writes a memory region of variable size. The graph shows the number of bytes per cycle which are read or written. Four different graphs are shown, one for each combination of the processes reading and writing. The read/write graph is for the background process, which always uses a 2MB working set to write, and the measured process with variable working set to read.

The interesting part of the graph is the part between 2²⁰ and 2²³ bytes. If the L2 cache of the two cores were completely separate we could expect that the performance of all four tests would drop between 2²¹ and 2²² bytes, that means, once the L2 cache is exhausted. As we can see in Figure 3.31 this is not the case. For the cases where the background process is writing this is most visible. The performance starts to deteriorate before the working set size reaches 1MB. The two processes do not share memory and therefore the processes do not cause RFO messages to be generated. These are pure cache eviction problems. The smart cache handling has its problems with the effect that the experienced cache size per core is closer to 1MB than the 2MB per core which are available. One can only hope that, if caches shared between cores remain a feature of upcoming processors, the algorithm used for the smart cache handling will be fixed.

Having a quad-core processor with two L2 caches was just a stop-gap solution before higher-level caches could be introduced. This design provides no significant performance advantage over separate sockets and dual-core processors. The two cores communicate via the same bus which is, at the outside, visible as the FSB. There is no special fast-track data exchange.

The future of cache design for multi-core processors will lie in more layers. AMD's 10h family of processors make the start. Whether we will continue to see lower level caches be shared by a subset of the cores of a processor remains to be seen. The extra levels of cache are necessary since the high-speed and frequently used caches cannot be shared among many cores. The performance would be impacted. It would also require very large caches with high associativity. Both numbers, the cache size and the associativity, must scale with the number of cores sharing the cache. Using a large L3 cache and reasonably-sized L2 caches is a reasonable trade-off. The L3 cache is slower but it is ideally not as frequently used as the L2 cache.

For programmers all these different designs mean complexity when making scheduling decisions. One has to know the workloads and the details of the machine architecture to achieve the best performance. Fortunately we have support to determine the machine architecture. The interfaces will be introduced in later sections.

3.5.4 FSB Influence

The FSB plays a central role in the performance of the machine. Cache content can only be stored and loaded as quickly as the connection to the memory allows. We can show how much so by running a program on two machines which only differ in the speed of their memory modules. Figure 3.32 shows the results of the Addnext0 test (adding the content of the next elements pad[0] element to the own pad[0] element) for NPAD=7 on a 64-bit machine. Both machines have Intel Core 2 processors, the first uses 667MHz DDR2 modules, the second 800MHz modules (a 20% increase).

Figure 3.32: Influence of FSB Speed

The numbers show that, when the FSB is really stressed for large working set sizes, we indeed see a large benefit. The maximum performance increase measured in this test is 18.2%, close to the theoretical maximum. What this shows is that a faster FSB indeed can pay off big time. It is not critical when the working set fits into the caches (and these processors have a 4MB L2). It must be kept in mind that we are measuring one program here. The working set of a system comprises the memory needed by all concurrently running processes. This way it is easily possible to exceed 4MB memory or more with much smaller programs.

Today some of Intel's processors support FSB speeds up to 1,333MHz which would mean another 60% increase. The future is going to see even higher speeds. If speed is important and the working set sizes are larger, fast RAM and high FSB speeds are certainly worth the money. One has to be careful, though, since even though the processor might support higher FSB speeds the motherboard/Northbridge might not. It is critical to check the specifications.

Continue to Part 3 (virtual memory).

Comments (69 posted)

What chroot() is really for

The chroot() system call is often misunderstood, as it can appear to do much more than it actually does. The confusion arises because it appears to some to be a security tool – there are limited security uses – when it is meant as a tool for isolating processes for installation, debugging, and legacy library usage.

What chroot() actually does is fairly simple, it modifies pathname lookups for a process and its children so that any reference to a path starting '/' will effectively have the new root, which is passed as the single argument, prepended onto the path. The current working directory is left unchanged and relative paths can still refer to files outside of the new root.

Calls to chroot() do not stack, with additional calls essentially overwriting the existing one. It can only be called by privileged programs and can be trivially bypassed by those who can call it as man 2 chroot describes:

    This  call does not change the current working directory, so that after
    the call '.' can be outside the tree rooted at '/'.  In particular, the
    superuser  can  escape from a 'chroot jail' by doing 'mkdir foo; chroot
    foo; cd ..'.

The use of the term "chroot jail" in the manpage is unfortunate as it may help perpetuate a common misconception about chroot(). It often gets mentioned in the same context as the "jail" calls for the BSDs, but it has little in common with them. A BSD jail is a mini-virtualization that partitions a system into multiple virtual systems each of which can have its own root account. chroot() has none of that sophistication.

A patch posted to the linux-kernel mailing list was aimed at fixing the "hole" described in the manpage, but led, instead, to a rather contentious thread. The patch changes chroot() by setting the current working directory to the new root if it was not already somewhere underneath it. This violates POSIX and other standards, which specify the current behavior, as well as numerous typical use cases for chroot(). In addition, as was forcefully pointed out in the thread, there are innumerable ways for a privileged process to access files that are not underneath the new root. Even if it did not run afoul of the standards, there is no point in fixing something that is so trivially bypassed in other ways.

The proponents of fixing the problem that they see – even if most of the kernel hackers disagree – seem to believe that, while you can circumvent a chroot() call, it should not be possible by using chroot() itself. It is an argument that didn't seem to get anywhere for a pretty simple reason: chroot() is not meant to be a security-oriented access control mechanism. It is, instead, a way to run processes with a partitioned view of the filesystem.

There are reasonable uses of chroot() for very limited security purposes. Daemons that do not run as root can be placed into their own filesystem subtree – bind/named and Apache are sometimes run this way – to prevent any access outside of it. That will work, even if the daemon gets exploited, as long as there is no way to elevate privileges after the exploit. For example, if there are vulnerable setuid() programs accessible from within the chroot(), full filesystem access is possible.

chroot() is a useful call, many install programs use it, as do programs that need to see a consistent set of older libraries, but it has very limited use in security applications. It does not provide a sandbox that can be used to test suspicious code, that code might escalate its privilege and access anything it wished. Maintaining an up-to-date chroot() environment adds an additional burden on administrators as well; update tools do nothing to help keep utilities secure if they live outside of the normal places. It is probably safest to avoid using it as any kind of security tool.

Comments (29 posted)

bugzilla: multiple vulnerabilities

Package(s):	bugzilla	CVE #(s):	CVE-2007-4543 CVE-2007-4538 CVE-2007-4539
Created:	October 1, 2007	Updated:	October 3, 2007
Description:	Masahiro Yamada found that from the 2.17.1 version, Bugzilla does not properly sanitize the content of the "buildid" parameter when filing bugs (CVE-2007-4543). The next two vulnerabilities only affect Bugzilla 2.23.3 or later, hence the stable Gentoo Portage tree does not contain these two vulnerabilities: Loic Minier reported that the "Email::Send::Sendmail()" function does not properly sanitise "from" email information before sending it to the "-f" parameter of /usr/sbin/sendmail (CVE-2007-4538), and Frédéric Buclin discovered that the XML-RPC interface does not correctly check permissions in the time-tracking fields (CVE-2007-4539).
Alerts:	Gentoo 200709-18 bugzilla 2007-09-30

Comments (1 posted)

kernel: ALSA returns incorrect write size

Package(s):	kernel	CVE #(s):	CVE-2007-4571
Created:	September 28, 2007	Updated:	June 20, 2008
Description:	The snd_mem_proc_read function in sound/core/memalloc.c in the Advanced Linux Sound Architecture (ALSA) in the Linux kernel before 2.6.22.8 does not return the correct write size, which allows local users to obtain sensitive information (kernel memory contents) via a small count argument, as demonstrated by multiple reads of /proc/driver/snd-page-alloc.
Alerts:	Ubuntu USN-618-1 linux-source-2.6.15/20/22 2008-06-19 Debian DSA-1505 alsa-driver 2008-02-22 Debian DSA-1479 linux-2.6 2008-01-29 Red Hat RHSA-2007:0993-01 kernel 2007-11-29 Red Hat RHSA-2007:0939-01 kernel 2007-11-01 SuSE SUSE-SA:2007:053 kernel 2007-10-12 Fedora FEDORA-2007-714 kernel 2007-10-08 Fedora FEDORA-2007-2349 kernel 2007-09-28 rPath rPSA-2007-0202-1 kernel 2007-09-27

Comments (none posted)

mplayer: heap-based buffer overflow

Package(s):	mplayer	CVE #(s):	CVE-2007-4938
Created:	October 2, 2007	Updated:	October 3, 2007
Description:	A heap-based buffer overflow in libmpdemux/aviheader.c in MPlayer 1.0rc1 and earlier allows remote attackers to cause a denial of service (application crash) or possibly execute arbitrary code via a .avi file with certain large "indx truck size" and nEntriesInuse values, and a certain wLongsPerEntry value.
Alerts:	Mandriva MDKSA-2007:192 mplayer 2007-10-01

Comments (none posted)

openssl: off-by-one error

Package(s):	openssl	CVE #(s):	CVE-2007-5135
Created:	October 3, 2007	Updated:	July 31, 2008
Description:	From the Debian advisory: An off-by-one error has been identified in the SSL_get_shared_ciphers() routine in the libssl library from OpenSSL, an implementation of Secure Socket Layer cryptographic libraries and utilities. This error could allow an attacker to crash an application making use of OpenSSL's libssl library, or potentially execute arbitrary code in the security context of the user running such an application.
Alerts:	Gentoo 201412-11 emul-linux-x86-baselibs 2014-12-11 rPath rPSA-2008-0241-1 openssl 2008-07-30 SuSE SUSE-SR:2008:005 acroread, asterisk, cacti, compat-openssl097g, icu, libcdio, wireshark/ethereal, Jakarta, perl-tk 2008-03-06 Red Hat RHSA-2007:1003-02 OpenSSL 2007-11-15 Red Hat RHSA-2007:0813-01 OpenSSL 2007-10-22 Fedora FEDORA-2007-2530 openssl 2007-10-18 Fedora FEDORA-2007-725 openssl 2007-10-15 SuSE SUSE-SR:2007:020 TK, openssl, hugin, lighttpd, novell-groupwise-gwclient, sylpheed-claws 2007-10-12 Red Hat RHSA-2007:0964-01 OpenSSL 2007-10-12 Debian DSA-1379-2 openssl097 2007-10-10 Gentoo 200710-06 openssl 2007-10-07 Mandriva MDKSA-2007:193 openssl 2007-10-04 rPath rPSA-2007-0206-1 openssl 2007-10-03 Foresight FLEA-2007-0058-1 dist 2007-10-03 Debian DSA-1379 openssl 2007-10-02

Comments (none posted)

pidgin: denial of service

Package(s):	pidgin	CVE #(s):	CVE-2007-4996
Created:	October 3, 2007	Updated:	November 2, 2007
Description:	Pidgin can be forced to crash by an MSN user sending "nudge" messages.
Alerts:	Fedora FEDORA-2007-2368 pidgin 2007-10-03 Slackware SSA:2007-275-01 pidgin 2007-10-03 Foresight FLEA-2007-0057-1 pidgin 2007-10-02

Comments (1 posted)

Kernel release status

The current 2.6 prepatch is 2.6.23-rc9, released on October 1. This -rc release was unexpected, but there were enough fixes added since -rc8 that Linus felt one more cycle was called for. The final 2.6.23 release should happen almost any time.

There have been about a dozen patches added to the mainline repository since -rc9.

The current -mm tree is 2.6.23-rc8-mm2. Recent changes to -mm include delayed allocation support for ext4 and a number of fixes. Andrew notes that -mm now has almost 32MB of patches relative to the mainline - an indication of what is to come once the 2.6.24 merge window opens.

Looking forward: it appears that the 2.6.24 cycle will begin with the i386/x86_64 merger. More information about 2.6.24 can be found in Andrew Morton's 2.6.24 merge plans document. It looks like 2.6.24 will include a bunch of memory management work, more anti-fragmentation patches, per-device write throttling, the LSM non-modules patch, file-based capabilities, more memory layout randomization, control groups (formerly containers), PID namespaces, kernel markers, and much more. Remember that this list covers only patches to be merged by Andrew; the bulk of the code going into 2.6.24 will get there directly from the subsystem maintainers.

Comments (none posted)

Quotes of the week

-- Ingo Molnar

Andrew Morton

-- Ted Ts'o

Comments (8 posted)

Linux driver project gets a full-time leader

The Linux Driver Project (LDP) just got a big boost, courtesy of Novell and Greg Kroah-Hartman. The project was announced last January to much acclaim, but has languished since, buried under Kroah-Hartman's "day job" and Linux kernel development work. Now, he will be able to devote much more time to the project as his employer, Novell, has shifted his job responsibilities to work full-time on the LDP.

The original project announcement was released in conjunction with the Freedom HEC conference and was described by Kroah-Hartman as a "lame publicity stunt", because it just reiterated the standard Linux driver development model: with some hardware and some information, a driver for your device will be written. There was a new wrinkle, though; an arrangement worked out with the Linux Foundation to allow driver developers to sign non-disclosure agreements (NDAs) with hardware vendors to get access to documentation and other information about the device. NDAs for driver development are controversial in some quarters, but are often required by hardware vendors.

There are numerous benefits for Linux: the drivers will all be licensed under the GPL, will get merged into the mainline tree, and be available for all Linux users. Other free operating systems may be able to use the source to write drivers for their systems, as well. Kroah-Hartman notes that a surprising added benefit is for new kernel developers:

Now that he has time to devote to LDP, Kroah-Hartman has put together two mailing lists along with a wiki to track the project. There is a mailing list for each of the two main roles, developers and project managers. The role of a project manager will be to facilitate the development, making sure that the driver hacker has what they need to get the job done and keeping the company, for whom the driver is being written, informed of the status. In short, they will shepherd an individual driver in much the same way that Kroah-Hartman is coordinating the LDP as a whole.

In less than a week since the project restart, there are five driver projects up for grabs, including a "clean-up and get merged" project that would be suitable as a first driver for someone just starting out in Linux driver development. Project managers are lining up to take on the drivers as well. The numbers of volunteers have grown, but as Kroah-Hartman notes, publicity is something the project still needs:

Already, there are drivers for many different kinds of devices in the pipeline:

Kroah-Hartman plans to reconnect with various companies that contacted him since January, but fell by the wayside. As that happens and the word gets out about the project, there should be driver development projects suitable for a wide range of interests and various levels of kernel experience. By providing a self-contained project that is targeted at inclusion in the mainline, more developers will be exposed to that process, which should expand the ranks of kernel hackers.

Linux already supports more hardware than any operating system has before and the LDP will only extend that lead. There are huge benefits for Linux, the developers and project managers, the companies whose devices will be supported, as well as for distributors like Novell. There may be complaints about signing NDAs, but the drivers will be free, not obfuscated; once companies see how easy it is to get a high-quality driver into the kernel, they will certainly come back for more. This can only be a good thing for all free software systems, not just Linux.

Comments (6 posted)

What's in the realtime tree

It has been almost exactly three years since Sven-Thorsten Dietrich posted a set of realtime improvements to the linux-kernel list. That particular body of code was upstaged by the realtime preemption work done by Ingo Molnar and others, but it deserves some credit for kicking off a development effort which continues to this day. After three years, many parts of the realtime preemption patch set have been merged into the mainline kernel, including dynamic tick support, a rewritten interrupt subsystem, mutexes, priority inheritance, high-resolution timers, and more. At this point, we are all running kernels which have benefited from the realtime preemption project.

The job of merging the realtime preemption work into the mainline is not complete, though. Indeed, a look at the 2.6.23-rc8-rt1 tree announcement shows that there are nearly 400 individual patches sitting there. This seems like a good opportunity to have a look at the realtime tree and see what remains to be merged.

The core of this patch set remains the realtime mutex code. When the kernel is configured for realtime operation, a bunch of (improved, but still scary) preprocessor magic causes normal spinlocks to be replaced by realtime mutexes, which have different properties. In particular, realtime mutexes are fully preemptible and have priority inheritance. With most kernel spinlocks replaced by these mutexes, there are few places in the kernel which are able to cause arbitrary latencies.

Merging realtime mutexes should, in theory, not be a problem; they are not actually used unless explicitly configured into the kernel, and it is assumed that most users will not configure things that way. Such a fundamental change to a core mutual exclusion mechanism will always raise eyebrows, though. So there have been no attempts to merge this code so far, and it is likely that most of the other parts of the realtime tree will find their way into the mainline first.

Code which could go in sooner is the threaded interrupt handlers patch. Putting interrupt handlers into threads allows them to be scheduled along with most other system activities and eliminates another potential source of latency. It also can improve the robustness of the system and make it easier to find bugs in interrupt code. So this patch could be merged and possibly even made the default - though there will always be a small number of interrupt handlers which must be run directly.

Also in the realtime tree is a patch which moves all software interrupt processing into dedicated threads. Then there is a patch which allows hardware interrupt handling threads to process any pending software interrupts before yielding the processor. This optimization avoids the need for a context switch to a separate software IRQ thread to get those interrupts delivered.

One of the sticking points with the realtime patches has been their interaction with the read-copy-update mechanism. The current code requires that preemption be disabled while references to RCU-protected data structures exist, but disabling preemption ruins the guarantees that the realtime code is trying to provide. The answer is a somewhat more complicated, preemptible RCU implementation. With luck, LWN will have an article on how preemptible RCU works in the near future.

Nick Piggin's lockless pagecache patches have found their way into the realtime tree. These patches make a number of low-level changes to the memory management and radix tree code so that some pagecache operations can be done without taking any locks. This code has been in circulation for some time without making it into the mainline, but it seems like a win in a number of scalability situations. Another patch (by Peter Zijlstra) gets rid of the locking in the kmap() code, improving latencies in systems using high memory.

The wisdom of allowing Java programs to mess with physical memory is not a topic which should need further discussion here. Another patch which has been out of the mainline for quite some time - and likely to remain that way - is Ted Ts'o's /dev/rmem facility. This device allows direct access to physical memory - a feature which is required on any system which wants to pass the realtime Java conformance tests. The wisdom of allowing Java programs to mess with physical memory is not a topic which should need further discussion here.

The realtime tree contains an extensive set of tools for tracking down parts of the kernel which cause excessive latencies. This code has, over the years, been put to good use in identifying and breaking up kernel code which hogs the processor unnecessarily. These patches would seem like a good match for the mainline, especially given recent discussions on the value of adding more instrumentation to the kernel. The first step in solving problems is being able to measure them.

For reasons which are unclear to your editor, the realtime tree contains the venerable realtime security module, which was definitively refused entry into the mainline a few years ago. The module is marked as being obsolete - but it is still there.

Quite a few other changes can be found in this tree. The SLUB allocator is not an option for realtime kernels. Instead, this tree uses a modified version of the slab allocator which replaces interrupt-based single-CPU locking with a set of specific per-CPU locks. The global files_lock has been removed in favor of tightly-locked per-CPU lists. To help with the creation of such lists, a new locked-list type has been added. The tasklet code has been reworked for better threading, but the tasklet elimination patch is not present. There's also quite a few architecture-specific patches adding various features (such as clockevents) needed by the realtime tree and fixing problems.

All told, there is a lot of code sitting in the realtime tree despite all of the mainline merging which has happened over the last couple of years or so. The stated plan is to merge most of this code in the not-too-distant future, but it is not clear when that will happen. In particular, some of the core realtime developers are likely to be severely distracted by the i386/x86_64 merger during the 2.6.24 cycle, so they may not manage to move much of the realtime code toward the mainline.

Comments (4 posted)

SMACK meets the One True Security Module

The Simplified Mandatory Access Control Kernel is a security module designed to harden Linux systems through the addition of mandatory access control policies; it was covered here last August. Like SELinux, SMACK works by attaching labels to processes, files, and other system objects and implementing rules describing what kinds of access are allowed by specific combinations of labels. Unlike SELinux, though, SMACK was designed specifically for simplicity of administration.

The posting of version 3 of the SMACK patch inspired a certain amount of discussion. Andrew Morton's take led things off:

Andrew concluded by suggesting that the SMACK patch should be merged for 2.6.24. There was some discussion about specific pieces of the patch (some developers are more impressed by CIPSO network labels than others), but there does not seem to be a whole lot of opposition to merging the SMACK security module. It is generally seen as being well-written code which makes sense from a security point of view.

There was one predictable exception, though: whenever a new security module is considered for merging the SELinux developers tend to oppose it. This time, James Morris voiced a more general complaint: SMACK would become the second in-kernel user of the Linux security module (LSM) framework. That, in turn, would make it almost impossible to remove LSM from the kernel. James claims:

The SELinux programmers, it seems, would rather that SELinux became the one security framework supported by Linux, with all development effort going into making SELinux better.

The problem, of course, is that, even after a few years with only SELinux in the kernel, there has not been a glut of application developers working to support it. The vision of each application shipping with an SELinux policy file has not come to be. Some progress has been made in the creation of higher-level tools for the management of SELinux policies, and the Fedora and Red Hat developers have come a long way toward making a general-purpose distribution work with a limited set of SELinux policies, but SELinux simply remains too complex for most people to deal with. SELinux may work out of the box on an RHEL system, but as soon as the system administrator runs into something which breaks, chances are that SELinux will be turned off.

The SELinux developers would presumably argue that the way to address these problems is to focus on a single security framework within the kernel. Rather than create competing, simplified frameworks, it would be better to implement approaches like AppArmor or SMACK within SELinux and, in the process, make SELinux better. Those developers argue that pluggable security modules, like pluggable schedulers, succeed only in splitting development effort and preventing the creation of a truly general solution:

The answering argument is that there are many security environments and differing sets of user needs; there is no sign that a single security approach can ever work in all situations. And, even if such a unified approach were possible, getting security developers to agree on it would still be a major challenge. Ted Ts'o writes:

The LSM architecture was a result of the very first kernel summit, where Linus stated that he had no wish to choose between the various security ideas in circulation and, instead, wanted the kernel to be able to support all of them. He has not changed his mind since; he still doesn't see any imminent consensus on security approaches, and still wants Linux to be flexible in this regard. So his pronouncement was:

So it looks like the way is clear for a merger of SMACK in 2.6.24. Once that happens, it would not be surprising to see another push made by the developers of security modules like AppArmor and TOMOYO Linux; in fact, the TOMOYO Linux patches have just been reposted. In the end, SELinux will, despite the apparent wishes of its developers, have to compete with other security approaches for attention from developers, distributors, and users. There will be no One True Security Module for Linux in the foreseeable future.

Comments (13 posted)

Unofficial Fedora Spins

Multimedia support has been and will continue to be an issue in the free software world, at least in those countries that allow software patents. Many multimedia codecs are patented. There are many small Linux distributions that include multimedia codecs and they all tend to be hosted in Europe or elsewhere in the world where software patents are not recognized.

Fedora is a U.S. company and the U.S. does recognize software patents. Therefore Fedora does not play many multimedia files. We still have Ogg and FLAC providing free audio/video formats. However some people, many coming from the Windows world, expect their MP3s, and MPEG files to "just work" and they get frustrated when they find that these things are difficult. These codecs are not in the main Fedora repository, and never will be unless the U.S. suddenly reverses its decision on software patents (which doesn't seem likely).

The Fedora-devel list had a lengthy discussion this week about creating a Fedora spin with multimedia support out of the box. The poster, Jóhann Guðmundsson of Iceland, wondered if such a spin (hosted in Iceland) could be considered an official Fedora spin, and if not how much work would be involved.

Since Iceland is one of those European Union countries that currently does not recognize software patents, such a spin would be legal there. However, the official word, summarized in this post from Jesse Keating, is that official Fedora spins can only use the packages in the main Fedora repository. Otherwise they must be called something other than Fedora and must not contain any Fedora trademarks or official artwork.

For those who still think that creating the Fedora-based "MyBlueCap" distribution would be a good idea, here's some places to start. A new wiki page on creating custom spins has been recently created. It only addresses official spins, of course, but it's a start. The Fedora Trademark Guidelines will help you figure out if your spin crosses the line into unofficial territory. More guidelines on redistributing Fedora can be found here.

Changing the name of the project and replacing the artwork so that the new spin is no longer "Fedora" would seem to be a daunting task. But work is underway to make this easier. Feature generic logos are targeted for Fedora 8. According to the wiki page: "We want to enable generic branding for Fedora, such that a tree built without fedora-logos is still reasonably functional if done right, without excessive developer attention."

Even with the Feature Generic Logos, the creator of "MyBlueCap" still has much work to do. It is nice of Fedora to supply some logos, but ultimately the Fedora developers have plenty to do and should not be expected to divert their efforts towards making it easy to create unofficial derivatives with software that is not free everywhere.

Later on this page there is an interview with Clement Lefebvre, the creator of Linux Mint. Linux Mint (hosted in France) is making a Ubuntu derivative with all the multimedia codecs installed and ready to use.

Comments (4 posted)

Fedora Unity releases updated Fedora 7 Re-Spins.

The Fedora Unity Project has announced the release of new ISO Re-Spins (DVD and CD Sets) of Fedora 7. These Re-Spin ISOs are based on Fedora 7 and all updates released as of September 12, 2007. The ISO images are available for i386 and x86_64 architectures via jigdo.

Full Story (comments: none)

Musix GNU+Linux 1.0 R3 Test1 released

Musix GNU+Linux 1.0 R3 test1 has been announced. "The Musix project has released the Musix GNU+Linux 1.0 R3 test1 Live-CD. This testing version was produced on the basis of the stable version 1.0 R2, based on Knoppix and Debian/Stable. Musix 1.0 R3 Test1 solves several problems, among them, the Inconsistent Filesystem Structure bug after an electrical shutdown. New functionalities were added, for instance: automount of CDs, DVDs and USB memories, or the "install" boot argument."

Full Story (comments: none)

Ubuntu 7.10 Beta released

A Beta release of Ubuntu 7.10 has been announced. "The Ubuntu team is proud to announce the beta release of Ubuntu 7.10 and its variants, Kubuntu, Edubuntu and Xubuntu. Codenamed "Gutsy Gibbon", 7.10 continues Ubuntu's proud tradition of integrating the latest and greatest open source technologies into a high-quality, easy-to-use Linux distribution. Ubuntu 7.10 on the desktop features a cutting-edge graphical experience with composited desktop effects, fully automated printer installation, and superior support for Firefox browser plugins. Ubuntu 7.10 server edition brings enhanced security-in-depth with AppArmor and easy install-time options for multiple common server configurations."

Full Story (comments: 18)

openSUSE is looking for a Chief Linux Evangelist

The openSUSE project is looking for an enthusiastic Chief Evangelist to promote and spread the adoption of openSUSE, be a public face for the project on conferences and events, act as voice of the community back to Novell's leadership team, develop and nurture the openSUSE communities and pro-actively drive openSUSE marketing.

Full Story (comments: none)

[openSUSE] YaST Survey Started

openSUSE is running a survey on YaST. "If you use any of the distributions openSUSE, SUSE Linux, SUSE Linux Enterprise Desktop or SUSE Linux Enterprise Server, I encourage you to participate in our survey to support us improving YaST. The survey will be online until mid November and the results will be published on openSUSE.org."

Full Story (comments: none)

Fedora-fr association is born !

The French Fedora Team has announced the creation of the association of French speaking Fedora users. "Why an association ? * In order to promote Free software in general and the Fedora distribution in particular. This promotion will lead to the creation of support for the Fedora promotion, from simple flyers to CD/DVD for the installation of Fedora."

Full Story (comments: none)

Second Call for votes for Constitutional amendment: reduce the length of DPL election process

The second and final call for votes has gone out on a constitutional amendment to reduce the length of the Debian Project Leader election process.

Full Story (comments: none)

Kiwi Linux

Kiwi Linux is a modified Ubuntu live CD for the i386 architecture. It includes Romanian and Hungarian localization, multimedia codecs, encrypted DVD support, Flash and Java plugins for Firefox, PPPoE GUI for accessing local internet services (Clicknet and RDS) and write support for NTFS partitions. Kiwi uses the same software repositories as Ubuntu with one additional source added for the handful of artwork related or slightly modified packages. Kiwi has released the Kiwi 7.10 beta live CD.

Comments (2 posted)

Fedora Weekly News Issue 103

The Fedora Weekly News for September 24, 2007 has the following announcements: "Cast your vote for the Fedora 8 Codename", "Fedora Unity releases updated Fedora 7 Re-Spins", plus several other topics.

Full Story (comments: none)

Gentoo Weekly Newsletter

The Gentoo Weekly Newsletter for September 24, 2007 covers the Council election results, Sparc team seeking AT's, KDE Tips and Tricks, and several other topics.

Comments (none posted)

Full Circle Magazine #5

The September edition of Full Circle Magazine (The FREE Independent Magazine for the Ubuntu Linux Community) is available in PDF format. This issue contains Fluxbuntu - Step-by-step Install, How-To : Report Bugs with LaunchPad, CoLoCo Edubuntu Presentation, From VMware to VirtualBox and Learning Scribus Pt.5, Review of Bridge Construction Kit, Preview of Gusty Gibbon, and more.

Comments (none posted)

Ubuntu Weekly Newsletter #59

The Ubuntu Weekly Newsletter for September 29, 2007 covers the Ubuntu 7.10 Beta release, newly approved LoCo team and Ubuntu members, LoCos participating in Ohio LinuxFest 2007, and much more.

Full Story (comments: none)

DistroWatch Weekly, Issue 222

The DistroWatch Weekly for October 1, 2007 is out. "PC-BSD is fast becoming a highly usable alternative to Linux on the desktop and the project's latest release, version 1.4, is the most feature-full desktop FreeBSD ever. But can it stand tall against Linux? Read our review to find out. In the news section: openSUSE begins uploading the 10.3 CD images, Mandriva abandons its "Club" subscription service, Clement Lefebvre defends multimedia codecs in Linux Mint, Sabayon promises more bleeding-edge features in version 3.5, and Ubuntu closes on the upcoming "Gutsy Gibbon" release with a bunch of interesting new features. Finally, we are pleased to announce that the DistroWatch.com September 2007 donation goes to Damn Small Linux."

Comments (none posted)

Interview with Colin Walters about the online desktop

The Fedora project has an interview with Colin Walters about the GNOME online desktop and its status for Fedora 8. "The Big Board is a part of the Online Desktop effort; it's a new panel type component that is intended to display more relevant things to your online life than the traditional panel. You could think of it as a collection of custom "widgets" for things like Google Calendar or Docs, except we're less interested in some things that might spring to mind with the term widgets, such as gigantic meticulously rendered clocks."

Comments (11 posted)

Interview: Clement Lefebvre of Linux Mint by Tony Mobily (Free Software Daily)

Tony Mobily talks with Clement Lefebvre, lead developer of Linux Mint. "TM: Clement, first of all please introduce yourself to our readers! Where are you from? What do you do? CL: My name is Clement Lefebvre--people usually refer to me as "Clem"--and I'm the founder of the Linux Mint distribution. I maintain the Main and Light Editions and also develop most of the mint tools (mintDisk, mintInstall, mintUpload..etc). I'm 29 years old and I'm passionate about Linux. I'm from Paris, France. I studied Computer Sciences over there and got a Masters Degree in IT. That was in 2001. Since then I basically worked for different companies in France and in Ireland, as a J2EE trainer, as a Web developer, as a Software Engineer and (at the moment) as a Java developer."

Comments (none posted)

The Open CD forks to OpenDisc

The Open CD project has been moved to the new OpenDisc project, according to Gerald Stone's blog. "OpenDisc is a collection of high quality open source software for the Microsoft Windows platform, aimed at users exclusively using said operating system. The two goals of the disc are to provide free alternatives to otherwise costly equivalents, and to educate people about the Linux operating system." (Thanks to Jim Welch).

Comments (6 posted)

How things are going (in Sabayon Linux)

Fabio Erculiani writes about Gentoo-based Sabayon Linux. "Even if I prefer coding rather than blogging about Entropy these days (eheh, let me keep this kind of secrecy for now), I can't hide the fact that today has been a great day for the whole project. I successfully upgraded a 3.4F installation to the current available binary packages using Equo (that contain X.Org 7.3 for example...). A lot of code is still missing (like etc-update alike function, env-update, post/pre install scripts and so on), but things are moving fast!"

Comments (none posted)

Photo Gallery: Ubuntu Gutsy Gibbon 7.10 (TuxJournal)

TuxJournal.net has a short article (in Italian) with lots of screen shots covering the first beta of Ubuntu Gutsy Gibbon 7.10.

Comments (none posted)

openSUSE 10.3 RC 1 Report (TuxMachines)

TuxMachines.org looks at the first release candidate of openSUSE 10.3. "OpenSUSE 10.3 final is due out in just a few days, so let's take a look at the progress. Folks have been testing this release candidate and posting their thoughts here and there. My own testing was delayed primarily due to the some of the joys of running Gentoo fulltime, but I was finally able to devote my full attention to openSUSE 10.3 RC1. As per my usual, I downloaded the DVD iso delta. This time it was 422 MB. I don't usually test everything with these developmental releases, but what I have tested is looking good."

Comments (none posted)

Ardour 2, a first look

Ardour is a long running multi-track audio workstation project by Paul Davis and others. Davis is also the lead developer behind JACK, the Jack Audio Connection Kit, which allows multiple applications to share the same sound card.

Ardour can be contrasted with Audacity, a much simpler multi-track capable recording application that was examined in the LWN article Multi-track recording with Audacity.

Installation of Ardour is a complicated process. Your author decided to take the easy path to getting the application running by installing the current version of the Ubuntu Studio distribution. Ubuntu Studio comes with Ardour 2 rev 1762 and includes a Linux kernel with real-time support, JACK, and numerous other useful audio applications:

A multi-track soundcard is highly recommended for getting the most out of Ardour. The M-Audio Delta 44 card was selected. The system uses an Asus A7V 333 motherboard with an Athlon 1800 CPU and 512 MB of system RAM. The system has two hard drives, one for the operating system and another for storing the audio data. The system's video card is an ATI Radeon 8500. Ardour will function with a 1024x768 resolution video display, but a 1280x1024 or higher resolution display is highly recommended so that the main window and mixer windows can be viewed simultaneously.

An external mixing board adds a lot of flexibility to the recording setup, a Behringer Eurorack UB1202 was connected to the Delta 44 card to provide microphone preamplification, tone control and an effects loop. The UB1202 only provides two outputs, a four channel mixer would be a better choice for use with the Delta 44. The first two channels from the Delta 44 were connected to a stereo's aux inputs to allow high fidelity monitoring of the audio.

These screenshots show the Ardour main window, mixer application and the qjackctl GUI interface to JACK.

With this system, Ardour 2 is able to do basic sound-on-sound recordings. Two primary tracks can be recorded, two more tracks can be added while listening to the first tracks, and more tracks can be added later. The Ardour user interface is fairly intuitive, it did not take long to figure out how to record tracks, add new tracks, extend existing tracks and zoom in and out with the audio waveform display. A nice feature is the automatic highlighting of clipped audio samples with red dots on the waveform display. Ardour takes a while to master, but that is to be expected is an application that takes on such a complicated list of tasks. Ardour has a good online manual that is helpful for learning the application.

Initially, it seemed that the system's hardware was not quite up to the task of running Ardour reliably. While playing previously recorded material, moving the mouse between windows on the screen caused small, but highly annoying clicks in the audio stream. Moving the mouse while recording resulted in clicks on the recorded tracks, badness 10,000. Adding another 256MB of RAM to the system did not change the behavior, the top utility supported this by showing 0MB of swap in use with the 512MB memory configuration. Switching to an Athlon 2200 processor reduced the clicking somewhat, but the problem was still present.

After much poking and prodding, the problem was eventually traced to JACK not being configured for realtime operation by default. The fix was easy, it involved clicking on the qjackctl setup button, selecting the realtime button, and restarting everything. No more obnoxious clicking.

Ardour's recorded audio quality using the Delta 44 sound card is quite good. In boutique audio lingo, you can hear lots of subtle nuances in the sound and the hiss is minimal. Ardour 2 shows many improvements over earlier versions, it is truly a nice application. Ubuntu Studio is also a huge step forward. It is possible to go from a blank box to a system with a functioning multi-track recorder in under an hour by answering a small number of installation questions and waiting for the installation to complete.

Comments (6 posted)

Areca Backup 5.3.5 is available (SourceForge)

Version 5.3.5 of Areca Backup has been announced. "Areca Backup is a file backup tool written in java. It supports data compression & encryption, incremental backup, file history explorer and many other features. Areca Backup also includes a transaction mechanism which guarantees your backups' integrity. This new version includes : Some mail report enhancements, A file permission recovery bug fix".

Comments (none posted)

Firebird 2.0.3 released

Sub-release 2.0.3 of the Firebird RDBMS has been announced. "This sub-release does not add any new functionality to the database engine. It contains a number of fixes to bugs discovered since the v.2.0.1 sub-release and corrects a regression that caused the withdrawal of the v.2.0.2 sub-release. Minor improvements include a port of Firebird 2.0.3 Classic for MacOSX on Intel and increased access security for the Firebird log."

Comments (none posted)

MySQL 5.1.22-rc has been released

Version 5.1.22-rc of the MySQL DBMS is available, it adds a new innodb_autoinc_lock_mode system variable and a large number of bug fixes. "we are proud to present to you the MySQL Server 5.1.22-rc release, the first 5.1 "release candidate" version of the popular open source database. Bear in mind that this is still a "candidate" release, and as with any other pre-production release, caution should be taken when installing on production level systems or systems with critical data."

Full Story (comments: none)

PostgreSQL Weekly News

The September 30, 2007 edition of the PostgreSQL Weekly News is online with the latest PostgreSQL DBMS articles and resources.

Full Story (comments: none)

BusyBox 1.7.2 announced

Version 1.7.2 of BusyBox, a collection of command line tools for embedded systems, has been announced. "This is a bugfix-only release, with fixes to install, find, login, httpd, runsvdir, chcon, setfiles, fdisk and line editing."

Comments (none posted)

First preview of Samba 3.2.0 announced

The first preview release of Samba 3.2.0 has been announced. "This is the first preview release of Samba 3.2.0. This is *not* intended for production environments and is designed for testing purposes only."

Full Story (comments: none)

CUPS 1.3.3 released

Version 1.3.3 of CUPS, the Common Unix Print System, has been announced. "CUPS 1.3.3 is now available for download from the CUPS web site and fixes some scheduler and localization issues."

Comments (none posted)

pam_mount 0.29 released (SourceForge)

Version 0.29 of pam_mount has been announced "pam_mount is a Pluggable Authentication Module that can mount volumes for a user session. Supports any filesystem your kernel is capable of, including tmpfs, FUSE, smbfs, cryptoloop, LUKS mounts, --bind and more. An uninitialized array and a copy-and-paste error were corrected in the recently introduced process spawn code."

Comments (none posted)

Linux-ready Firmware Developer Kit release 3

The third release of the Linux-ready Firmware Developer Kit is available. Some new test kernels have been added, the documentation has been improved, and a number of other enhancements have been made; click below for the details.

Full Story (comments: none)

Compiz 0.6.0 announced

Version 0.6.0 of Compiz, a 3D window manager, is out with an incredibly long list of improvements and bug fixes. Here are a few of the changes: "Better support for multiple X-screens. XML-based meta-data system for handling of various kinds for meta-data like plugin descriptions, default option values, etc. Major improvements to option initialization based on the new meta-data system. Extensible logging framework. Plugin plugins that make it possible to adjust and extend the behavior of existing plugins through new plugins. More dynamic handling of output devices, which allows the output device configuration used when rendering to be changed between frames."

Full Story (comments: none)

GNOME Software Announcements

The following new GNOME software has been announced this week:

• Conduit 0.3.4 (new features and bug fixes)
• Empathy 0.13 (new features and bug fixes)
• gcalctool 5.20.1 (bug fix and translation work)
• gedit-plugins 2.20.0 (new features, bug fixes and translation work)
• gnome-control-center 2.20.0.1 (bug fixes and translation work)
• gtk-doc 1.9 (new features and bug fixes)
• gtkmm-utils 0.2.1 (build fix)
• Hipo 0.5 (new features, bug fixes and translation work)
• iogrind 0.0.1 (initial release)
• MonoDevelop 1.0 beta 1 (new features and bug fixes)
• PyGTK 2.12.0 (new features)
• Tracker 0.6.3 (new features, bug fixes and translation work)

You can find more new GNOME software releases at gnomefiles.org.

Comments (none posted)

KDE Software Announcements

The following new KDE software has been announced this week:

• Amarok Atom Syndication 0.1.2 (unspecified)
• aMule kollection 0.2 (new features and installation improvements)
• eric4 4.0.2 (bug fixes)
• eric4 4.0.3 (bug fixes)
• KBarcode 2.0.6 (bug fix)
• KCheckGMail 0.5.7.2 (bug fixes and translation work)
• KDE Priority handler 0.2 Beta (new features and bug fixes)
• KGtk 0.9.1 (build system change and bug fixes)
• Kisa 0.32 (initial release)
• KMPlayer 0.10.0 (new features and bug fixes)
• Konversation Auto-replaces 0.0.1 (initial release)
• kputsite 0.1 (code cleanup)
• kReiSSy 0.1.1 (unspecified)
• KSniffer 0.3.1 (bug fixes and performance improvements)
• nmapsi4 0.0svn01 (unspecified)
• QBrew 0.4.0 (new features and bug fixes)
• QTGZManager Beta3 (new features and bug fixes)
• Transforme-me 0.1.2 (new features and bug fixes)
• Transforme-me 0.3 (bug fixes)
• Yakuake 2.8 (new features and bug fixes)
• Zhu3D 3.0.4 (new features, bug fixes and performance improvements)

You can find more new KDE software releases at kde-apps.org.

Comments (none posted)

Xorg Software Announcements

The following new Xorg software has been announced this week:

• xf86-video-ati 6.7.194 (new features and bug fixes)
• xf86-input-vmmouse 12.4.3 (bug fix)
• xf86-video-mga 1.9.100 (bug fixes and code cleanup)
• xf86-video-vmware 10.15.2 (bug fix)
• xfs 1.0.5 (new feature and bug fixes)

More information can be found on the X.Org Foundation wiki.

Comments (none posted)

LedgerSMB 1.2.8 Released

Version 1.2.8 of the LedgerSMB accounting package is out. Given that this release "corrects a number of security and accounting logic issues", most users will probably want to do the upgrade. In particular, it appears that there is a set of SQL injection vulnerabilities in previous releases.

Full Story (comments: none)

pyFltk2 1.0.0b1 announced

Version 1.0.0b1 of pyFltk2, a Python language binding for the FLTK2 toolkit, has been announced. "The first beta release of the Python bindings for FLTK2 is available for download from Sourceforge: http://pyfltk.sourceforge.net. This release supports and has been tested with fltk-2.0-r5940."

Comments (none posted)

wxWidgets 2.8.6 released

Version 2.8.6 of the wxWidgets GUI toolkit has been announced, it is mainly a bug fix release. "October 1st, 2007 -- the wxWidgets team is pleased to announce a new wxWidgets release. wxWidgets is a mature, open source, cross-platform application framework for C++ and other languages."

Comments (none posted)

Wine 0.9.46 announced

Version 0.9.46 of Wine has been announced. Changes include: A variety of fixes to improve Photoshop CS2 support, More complete support for device installation in setupapi, New Bidi text implementation that doesn't depend on libicu, The usual assortment of Direct3D improvements, Beginning of I/O completion ports support and Lots of bug fixes.

Comments (none posted)

Claws Mail 3.0.2 released

Version 3.0.2 of Claws Mail, a light weight GTK+ email client, has been announced, it features a number of bug fixes.

Comments (none posted)

PatientOS version 0.12 released (LinuxMedNews)

Version 0.12 of PatientOS has been announced. "PatientOS is an open source healthcare information system physicians, nursing, pharmacy, laboratory and ultimately all departments in a hospital, physician practice, or any other healthcare facility. Version 0.12 adds the foundation code to support the creation and maintenance of a formulary. Pharmacists can create medications, and associate rules for dose checking. Medications may be created defining dose and dispense details to build the formulary."

Comments (none posted)

HylaFAX 4.4.2/4.3.6 releases

Versions 4.4.2 and 4.3.6 of HylaFAX, a FAX modem interface application, has been announced. "These releases are maintenance releases, and do not contain any new features or functionality, but only contain bugfixes".

Comments (none posted)

Meeks on OpenOffice.org

Worth a read: this weblog entry by Michael Meeks on Sun's management of OpenOffice.org. "If OpenOffice was blessed (like other more sensibly structured projects) with a large, diverse and healthy developer-base, then perhaps we could expect to go around rejecting big chunks of code, offending developers and driving away potential contributors. To do this solely in order for Sun to retain total ownership of the code-base (and even loosely coupled components) - seems rather a betrayal of it's self-appointed stewardship role..." Many company-driven projects require transfer of copyright ownership from contributors, so OOo is not the only place issues like this will come up. (See also: this discussion of ooo-build from 2004. ooo-build was not a full fork of OpenOffice.org then and does not appear to be one now.)

Comments (48 posted)

OpenOffice.org Newsletter

The September, 2007 edition of the OpenOffice.org Newsletter is out with the latest OO.o office suite articles and events.

Full Story (comments: none)

Caml Weekly News

The October 2, 2007 edition of the Caml Weekly News is out with new Caml language articles.

Full Story (comments: none)

Joda-Time Hibernate support 1.0 (SourceForge)

Version 1.0 of hibernate support for Joda-Time has been announced. "Joda-Time provides a library of classes to replace the Java JDK Date and Time classes including formatting. It is based around the ISO8601 datetime standard, but also provides full support for other calendar systems, such as Gregorian and Buddhist. The new release of hibernate support for Joda-Time is now available. This supports persisting LocalDate, LocalTime, LocalDateTime, Period and Duration."

Comments (none posted)

SBCL 1.0.10 has been released

Version 1.0.10 of Steel Bank Common Lisp has been announced. "This version improves environment access, speeds up CLOS slot accesses, and fixes some bugs. SBCL is a native compiling Common Lisp implementation, under MIT/Public Domain licence. It purports to conform to the ANSI Common Lisp standard, and features several non-standard extensions."

Full Story (comments: none)

Python-URL! - weekly Python news and links

The October 1, 2007 edition of the Python-URL! is online with a new collection of Python article links.

Full Story (comments: none)

TclOO 0.1 released (SourceForge)

Version 0.1 of TclOO has been announced. "Donal Fellows is pleased to announce the release of version 0.1 of the TclOO package. This package (which requires Tcl 8.5b1 to work) provides an advanced high-speed Object Oriented system core for the Tcl programming language."

Comments (none posted)

Why GPLv3 Will Supplant GPLv2 (Linux Journal)

Glyn Moody muses on GPLv3 adoption in a Linux Journal article. He looks at the history of licensing and concludes that GPLv3 adoption is inevitable. "The interesting point here is that it was not legal issues that prompted the adoption of the GPL, but simply a desire to make it easier for MySQL to be included in distributions by simplifying the legal wrapping. MySQL is not alone in making the move to the GNU GPL for this reason."

Comments (none posted)

Finland's Summer Coders to Open their Minds (by Paul Sladen)

Paul Sladen covers [click below] the Finnish Summer of Code. "Google's Summer of Code may have taken the limelight, but in the north-east corner of Europe there has been another smaller (near) namesake taking place. Since 2006, Finland has had its very own Summer of Code—"Kesäkoodi", "summer code" in Finnish—organised and backed with the help of Finnish companies wanting to contribute to the community at a local level."

Full Story (comments: 1)

HP: Linux ready for mission-critical applications (ZDNet UK)

HP's Randy Hergett speaks at the Gelato Itanium Conference & Expo in Singapore. ""[Linux] is ready for most applications," he said, noting that there are telecommunications companies running mission-critical databases on Linux, and overall adoption levels are ramping up."

Comments (4 posted)

Announcing the KDE 4.0 Release Event (KDE.News)

KDE.News looks forward to the KDE 4.0 release media event, happening January 17 to 19 in Mountain View, California. "There will be plenty of time and opportunity for interaction between all attendees; but there will also be many interesting presentations, involving both technical and non-technical topics. We have invited over 200 members of the media, I.T. business, distributions and other Free Software groups, completed of course with many members from the North-American KDE community. Further, several international KDE hackers will attend to give talks or help organise the event."

Comments (none posted)

Red Hat Rises After New Linux Products Fuel Sales (Bloomberg)

Bloomberg covers the latest financial results from Red Hat, Inc. "Red Hat's Enterprise Linux 5 software, released in March, sold faster than expected last quarter, increasing cash flow. The Raleigh, North Carolina-based company also persuaded existing customers to use Red Hat software on more of their computers. ``Cash flow from operations was very solid compared to last quarter, and the revenue beat expectations,'' said Denny Fish, an analyst at JMP Securities in San Francisco. He has a ``market perform'' rating on the stock. Cash flow from operations rose 43 percent to $63.7 million last quarter from a year earlier. In the previous quarter, it declined 4 percent."

Comments (3 posted)

Red Hat faces stiff challenges to move beyond its core technology (LinuxWorld)

John Fontana writes about Red Hat. ""The big challenge for Red Hat is moving from an [operating system] distributor to becoming a distributor of an application platform, a virtualization platform, an SOA platform. Moving into those spaces is not an easy transition," says Denny Fish, senior analyst for infrastructure software and services for financial services firm JMP Securities. "They are selling to different people within an organization. The [operating system] is often an indirect sale, but with the middleware platform, for instance, you are selling to application developers and systems architects.""

Comments (none posted)

Kubuntu Takes Over the Canary Islands (Ubuntu Fridge)

The Ubuntu Fridge team reports that Kubuntu in taking over the Canary Islands. "The Canary Islands have two derivatives of Kubuntu, one which is being installed in all their schools and one used by the largest university. The Jornadas de Software Libre conference at The University of La Laguna, took place in Tenerife, Canary Islands, Spain, from the 18th-21st September 2007. It was organised by the university's Software Libre Office (OSL)." (Found on KDE.News)

Comments (none posted)

Microsoft, antitrust and innovation, by Georg Greve (Groklaw)

Free Software Foundation Europe president Georg Greve discusses the fallout from the recent EC antitrust ruling against Microsoft. "If one were to believe Microsoft, antitrust law is for sore losers who are too lazy to innovate, and the decision of the European Court of Justice against Microsoft was to the detriment of consumers around the world. One might even believe that any company with large enough market share would now have to fear the wrath of the European Commission and its anti-innovation bloodhounds. At first the notion seemed ludicrous, but then more and more blogs repeated it and serious media started picking it up. Even representatives of the US government spoke out on behalf of Microsoft, to the annoyance of Neelie Kroes, the European Union's antitrust commissioner."

Comments (1 posted)

Community interview: Novell answers 10 questions (BR-Linux.org)

BR-Linux.org presents a community interview with Novell, here's a summary of the responses: "One of the questions, sent by the reader semente, wasn't answered at all, other answers look evasive, some of them repeat known company policy without adding much more meat to it (the deal was about interoperability, you know), but most of them may reveal more than a glimpse of unfiltered opinion: “Novell believes there should be one open standard and that standard is ODF”, “We do not believe that Linux infringes on any Microsoft patents”, “We welcome GPLv3”, and so forth." (Thanks to Augusto Campos).

Comments (6 posted)

An Interview with ECIS's Thomas Vinje on the EU Microsoft Decision, by Sean Daly (Groklaw)

Sean Daly talks with Thomas Vinje about the EU Microsoft Decision and OOXML. "When the EU Court of First Instance announced its verdict on September 17, upholding the EU Commission's findings that Microsoft abused its market dominance, the media flocked to the lawyers representing the various parties for reactions to the ruling, Brad Smith for Microsoft, Carlo Piana for FSFE and Samba, and Thomas Vinje, who represented ECIS, the European Committee for Interoperable Systems."

Comments (none posted)

Linux Gazette #143

The October 2007 edition of Linux Gazette is out. Articles in this issue include An Ongoing Discussion of Open Source Licensing Issues, Linux Console Scrollback, Securing Apache Web Server with mod_security, Introducing Python Pickling, and more.

Comments (none posted)

Loop-based Music Composition With Linux, Pt. 2 (Linux Journal)

In this Linux Journal article, Dave Phillips completes his look at using Linux for loop-based composition. He looks at Ardour, Reaper, and Audacity to create and edit music from sampled sources. "Drummers are pattern-playing creatures, but to keep things interesting they vary those patterns from time to time. We can liven up our example by replacing every fourth loop with a variation of the groove or a fill taken from the same source loop collection. Simply load the new set of audio files as new tracks, edit as desired, then mix and match until you find the right combination of patterns (i.e. what pleases your ears)."

Comments (none posted)

High-performance network programming, Part 1 (developerWorks)

IBM developerWorks looks at squeezing the maximum usage out of your network resources. "Though bandwidth available to a particular protocol is limited by Shannon's law and other factors, such as network usage patterns, most of the time it is shoddy programming or naive coding that causes suboptimal utilization of network resources. Performance enhancement is also an art as much as it is a science. To get the best end-to-end throughput, you have to employ various tools to measure performance, identify bottlenecks, and eliminate them or minimize their impact. You can quickly get a huge performance boost by simple and straightforward scientific methods."

Comments (17 posted)

GNOME 2.22 planning: Empathy messaging client and toolkit proposed for inclusion (ArsTechnica)

ArsTechnica looks at the instant messaging client Empathy, which has been proposed for inclusion in GNOME 2.22. "Empathy is rapidly becoming an important part of the GNOME software ecosystem and is already packaged in several mainstream distributions, including the upcoming Ubuntu 7.10 release. Empathy integration features for Nautilus, Totem, Epiphany, and Jokosher and others are currently being developed. The Empathy toolkit is also being used by Intel as part of its new Linux-based mobile platform. Telepathy could eventually provide pervasive messaging and presence functionality throughout the entire desktop environment." (Found on GnomeDesktop)

Comments (3 posted)

The Mono Project: You Might Expect the Unexpected (Linux Journal)

Tom Adelstein looks at the Mono project. "Back in February, Ralph Green asked me to speak at the North Texas Linux Users' Group. I discussed Linux administration and then took questions. Some one in the audience asked me about Mono. I gave a cavalier answer having a bias against it. Then someone else in the audience said that I needed to get my facts straight."

Comments (42 posted)

To Sir, with Love: How To Get More Women Involved in Open Source (O'ReillyNet)

In this article from O'Reilly's Women in Technology series Selena Deckelmann shares some suggestions for how to get more women involved in open source. "We can learn from research about increasing diversity. I'm sure smart people have summarized, put together lists of bullet points, and made handbooks to show how to do it. Certainly, organizations dedicated to fixing inequalities will be touchstones for change. But we need more than leadership to change our culture. We each can take steps now to make women feel like there is a place for them in our communities."

Comments (205 posted)

EFF: Justice Department Withholds Records of Stealth Campaign to Block Surveillance Suits

The Electronic Frontier Foundation has announced the filing of a lawsuit against the U.S. Department of Justice. "The Electronic Frontier Foundation (EFF) filed suit against the Department of Justice (DOJ) today, demanding any records of a telecom industry lobbying campaign to block lawsuits over their compliance with illegal electronic surveillance. EFF's lawsuit comes as Congress debates letting telecommunications companies off scot-free as part of the hotly disputed "modernization" of the Foreign Intelligence Surveillance Act (FISA). EFF represents the plaintiffs in Hepting v. AT&T, a class-action lawsuit brought by AT&T customers accusing the telecommunications company of violating their rights by illegally assisting the National Security Agency in domestic surveillance."

Full Story (comments: none)

Linux Foundation Technical Advisory Board Election Results

James Bottomley has announced the results of the election for members of the Linux Foundation Technical Advisory Board which was held on September 5th at the kernel summit. Five people were elected: Arjan van de Ven, Greg Kroah-Hartman, Christoph Lameter, Olaf Kirch, and LWN's own Jonathan Corbet. The first three listed were re-elected to the board, while Olaf Kirch and Jonathan Corbet are new. Click below for a bit more information on the election.

Full Story (comments: 3)

Linux Foundation teams up with Japanese government

The Linux Foundation has signed a collaboration agreement with the Information-technology Promotion Agency of the Japanese government. The agreement is targeted at increasing participation of Japanese developers in Linux and open source software. "This announcement comes during a time of heightened interest in open source use in Japan. Recent examples include the increasing use of Linux in consumer electronics devices manufactured in Japan and the Tokyo Stock Exchange's decision to use Linux for its next generation enterprise system. In July 2007, the Japanese government made open standards adoption a priority for all government IT procurements. The government has stated it has budgeted JPY1.25 trillion, or US $10.4 billion, on IT spending over the next year and will also develop a Linux-based system for its legal registration system."

Comments (none posted)

Yet another ath5k pronouncement from the SFLC

The attempt to create a Linux driver for Atheros-based wireless adapters would appear to be enough to keep the Software Freedom Law Center in business all by itself. The SFLC has announced the availability of a new document on the provenance and copyright status of the Linux ath5k driver. "Ultimately, all the copyright holders of the Linux ath5k-driver code, derived from ar5k, have been contacted and have agreed to license their changes under the ISC license, thus allowing improvements to be re-incorporated into OpenBSD. One of the three historical branches of the code reviewed by SFLC, however, included portions that are only licensed under the GPL, and SFLC has determined that it would be very difficult to re-incorporate that code into OpenBSD." The full report is available on the SFLC web site.

Comments (2 posted)

Announcing CrossOver 6.2 for Linux and Mac

Version 6.2 of CrossOver Linux and CrossOver Mac have been announced. "Version 6.2 supports the upcoming Team Fortress 2 release from Valve software, right out of the Orange Box, as it were. This adds to our growing list of games that work well in CrossOver. We feel that CrossOver is now a viable way to play popular games on Linux and on the Mac. It also includes some major work on Outlook, particularly for use in corporate environments, along with a range of bug fixes for many other applications."

Full Story (comments: none)

Levanta 6.0 brings automation capabilities to Linux-based data centers

Levanta has announced a family of data center automation solutions for growing Linux environments. "Levanta 6.0 delivers fully-integrated system and application monitoring and policy-driven automation of Linux system management functions in easy to deploy appliances, resulting in significantly lower cost and shorter implementation time."

Full Story (comments: none)

Mexico's largest mortgage lender chooses Novell for key business system

Novell, Inc. has announced a new deal with Mexico's Fondo Nacional de la Vivienda. "The Instituto del Fondo Nacional de la Vivienda (INFONAVIT), Mexico's largest mortgage lender, has tapped SUSE(R) Linux Enterprise from Novell(R) as its platform for customer transactions. Providing services to more than 12 million people and 830,000 employers, INFONAVIT has deployed SUSE Linux Enterprise as the basis for its new payment collection system. With SUSE Linux Enterprise Server, INFONAVIT has a stable, flexible platform that enables it to provide a high-quality, easy to use service, while streamlining costs and administrative processes."

Comments (none posted)

Open Kernel Labs Delivers OKL4 for OpenMoko Smart Phone

Open Kernel Labs has announced the availability of the OKL4 advanced open source microkernel architecture. "Open Kernel Labs (OK), a global provider of embedded systems software and virtualization technology, announces the availability of OKL4 for FIC's OpenMoko Neo1973 smart phone and the FancyPants advanced GUI platform from Fluffy Spider Technologies (FST). The products will be demoed at the upcoming ARM Developers Conference (Booth 511)."

Full Story (comments: none)

OpenVZ virtualization software available with CentOS Live CD

OpenVZ is now available on the CentOS Live CD. "The OpenVZ project today announced availability of its operating system (OS) server virtualization software as a modified version of the CentOS 4.4 bootable Live CD so that users can test drive the OpenVZ software without changes to their computer or installing anything on their hard disk. "We're following on the success of our delivery of a Live CD for the Knoppix distribution, which is very popular with hobbyists," said Kir Kolyshkin, manager of the OpenVZ project."

Full Story (comments: none)

xTuple announces PostBooks 2.2.1

xTuple has announced the release of Version 2.2.1 of its PostBooks Accounting, Enterprise Resource Planning (ERP), and Customer Relationship Management (CRM) solution. "The release is a follow-up to the recent version 2.2.0, and offers the open source community a new data import and mapping tool called CSVimp, as well as enhanced documentation and examples supporting the new xTuple Application Programming Interface (API) for connecting to external systems. The release also contains bug fixes and features suggested and contributed by the xTuple community."

Full Story (comments: none)

Making Things Talk--New from Make

Maker Media has published the book Making Things Talk by Tom Igoe.

Full Story (comments: none)

Security Data Visualization--New from No Starch Press

No Starch Press has published the book Security Data Visualization by Gregory Conti.

Full Story (comments: none)

FOSS.IN and OpenOffice.org CFP

A call for papers has gone out for FOSS.IN. The event will take place in Bangalore, India on December 4-8, 2007. Submissions are due by October 8.

Full Story (comments: none)

LAC2008 Call for Papers, Music, etc.

A call for papers and materials has gone out for the 2008 Linux Audio Conference. The event will be held in Cologne, Germany on February 28 through March 2, 2008. Submissions are due by December 1.

Full Story (comments: none)

MySQL Conference and Expo 2008 CFP

The 2008 MySQL Conference and Expo will be held on April 15-18, 2008 in Santa Clara, California. "The event is expected to bring over 1,600 open source and database users together to harness the power of MySQL and celebrate the active MySQL ecosystem. The call for participation is now open for prospective speakers; submissions will be accepted until October 30, 2007."

Full Story (comments: none)

Akademy 2008 to be Held in Belgium (KDE.News)

KDE.News has posted an early announcement for the 2008 Akademy conference. "The annual KDE World Summit, Akademy, has found a home for 2008 in the heart of Europe, Belgium. The event is the most important conference for the contributors of the KDE project and will be held from Saturday August 9th to Saturday 16th at the De Nayer Institute, an associated campus of the University of Leuven. There are three sub-events: a contributors conference, the KDE e.V. annual general assembly and a week long hacking session."

Comments (none posted)

GNOME Boston Summit 2007

The GNOME Boston Summit will take place on October 6-8, 2007 in Boston, MA. "The Boston Summit is a three-day hackfest for GNOME developers and contributors. It is not primarily aimed at users or new contributors, but if you want to jump right into the deep end, it's a fantastic way to meet everyone and get involved. Unlike traditional conferences, the Boston Summit is all about getting developers together and getting things done. While there are some non-hacking sessions, they are geared heavily towards many-to-many, interactive discussion and planning, rather than one-to-many presentations."

Full Story (comments: none)

SugarCRM begins global CRM Acceleration world tour

SugarCRM has announced new dates and locations around the world for the CRM Acceleration Summit Series. Click below for a list of dates and places.

Full Story (comments: none)

Events: October 11, 2007 to December 10, 2007

The following event listing is taken from the LWN.net Calendar.

Date(s)	Event	Location
October 10 October 12	Plone Conference 2007	Naples, Italy
October 12	Legal Summit for Software Freedom	New York, NY, USA
October 13 October 14	T-DOSE 2007 (Technical Dutch Open Source Event)	Eindhoven, The Netherlands
October 13	The Ontario Linux Fest Conference	Toronto, Canada
October 13	Aka Linux Kernel Developer Conference	Beijing, China
October 16	Databases and the Web	London, England
October 17 October 19	2007 WebGUI Users Conference	Madison, WI, USA
October 17 October 19	Web 2.0 Summit	San Francisco, CA, USA
October 18 October 20	HackLu 2007	Kirchberg, Luxembourg
October 19 October 21	ToorCon 9	San Diego, CA, USA
October 20 October 21	Ubucon.de	Krefeld (Köln), Germany
October 20	PostgreSQL Conference Fall 2007	Portland, OR, USA
October 20	./freedom & opensource day - PERU	Lima, PERU
October 21 October 25	OOPSLA 2007	Montreal, Canada
October 21 October 26	Colorado Software Summit	Keystone, CO, USA
October 22 October 26	OpenGL Bootcamp with Rocco Bowling	Atlanta, GA, USA
October 22 October 23	She's Geeky - A Women's Tech (un)Conference	Mountain View, CA, USA
October 23 October 25	Open aLANtejo 07 - CNSL07	Évora, Portugal
October 23 October 26	Black Hat Japan	Tokyo, Japan
October 25 October 26	FSOSS 2007 - Free Software and Open Source Symposium	Toronto, Canada
October 27 October 28	FOSSCamp 2007	Cambridge, MA, USA
October 27	Linux Day Italy	many cities around country, Italy
October 28 November 2	Ubuntu Developer Summit	Cambridge, Massachusetts, USA
October 29	3rd International Workshop on Storage Security and Survivability	Alexandria, VA, USA
October 29 November 1	Fall VON Conference and Expo	Boston, MA, USA
October 30 October 31	BCS'07	Jakarta, Indonesia
October 31 November 1	LinuxWorld Conference & Expo	Utrecht, Netherlands
November 1 November 2	The Linux Foundation Japan Symposium	Tokyo, Japan
November 2	5th ACM Workshop on Recurring Malcode	Alexandria, VA, USA
November 2 November 3	Embedded Linux Conference, Europe	Linz, Austria
November 2 November 4	Real-Time Linux Workshop	Linz, Austria
November 3	Linux-Info-Tag Dresden	Dresden, Germany
November 5 November 9	Python Bootcamp with Dave Beazley	Atlanta, USA
November 7	NLUUG 25th anniversary conference	Beurs van Berlage, Amsterdam, The Netherlands
November 7	Alfresco North American Community Conference 2007	New York, NY, USA
November 8 November 9	Blog World Expo	Las Vegas, NV, USA
November 10 November 11	Linuxtage	Essen, NRW, Germany
November 11 November 17	Large Installation System Administration Conference	Dallas, TX, USA
November 12 November 16	Ruby on Rails Bootcamp with Charles B. Quinn	Atlanta, USA
November 12 November 15	OWASP & WASC AppSec 2007 Conference	San Jose, USA
November 12 November 16	ApacheCon US 2007	Atlanta, GA, USA
November 13 November 14	IV Latin American Free Software Conference	Foz do Iguacu, Brazil
November 15 November 18	Piksel07	Bergen, Norway
November 15	Alfresco European Community Conference	Paris, France
November 16 November 18	aKademy-es 2007	Zaragoza, Spain
November 20 November 23	DeepSec ISDC 2007	Vienna, Austria
November 22 November 23	Conferencia Rails Hispana	Madrid, Spain
November 24	LinuxDay in Vorarlberg (Deutschland, Schweiz, Liechtenstein und Österreich)	Dornbirn, Austria
November 26 November 29	Open Source Developers' Conference	Brisbane, Australia
November 28 November 30	Mono Summit 2007	Madrid, Spain
November 29 November 30	PacSec 2007	Tokyo, Japan
December 1	Django Worldwide Sprint	Online, World
December 1	London Perl Workshop 2007	London, UK
December 4 December 8	FOSS.IN 2007	Bangalore, India
December 7 December 8	Free Software Conference Scandinavia	Gotherburg, Sweden
December 7 December 8	PGCon Brazil	Sao Paulo, Brazil

If your event does not appear here, please tell us about it.

LinuxWorld video: Greg K-H on the Linux Driver Project

Online video is available from the May, 2007 FreedomHEC conference.

Full Story (comments: none)