System and method for reducing the number of translation buffer invalidates an operating system needs to issue

[0001] The present invention relates to computer software and, more particularly, to enhancing the performance of a computer system.

[0002] The development of computer systems has allowed increasing complexity and size of software applications, which in turn placed higher demands on the performance of the computer systems. Consequently, techniques have been developed to expand the performance capacity of computer systems. For example, a computer system may include more than one central processing unit (“CPU”) to increase the computer system's processing power. FIG. 1 illustrates a single computer system 100. The computer system 100 includes a main memory 102, and one or more CPUs such as the representative CPU A 104A and CPU Z 104Z. The main memory 102 contains code and data necessary for the operation of the one or more CPUs in the computer system 100. The main memory 102 is only addressable by physical addresses.

[0003] The increasing demands placed on a computer system also have increased the amount of addressable memory available on a computer system. Increasing the amount of addressable memory enables a computer system to operate on more information and more complex software programs. One technique for increasing the addressable memory of a computer system is to provide a virtual memory system. A virtual memory system simulates an addressable memory that can be much larger than the main memory that a computer system actually has. A CPU produces virtual addresses that are translated, via hardware and software, to physical addresses, which can be used to access the main memory via a process of memory mapping.

[0004] The translation from a virtual address to a physical address is usually implemented by a memory management unit (“MMU”). As shown in FIG. 1, each CPU in the computer system 100 interfaces with the main memory 102 via a MMU. For example, the representative CPU A 104A communicates with the main memory 102 via a MMU A 106A. The MMU A 106A is capable of translating a virtual address issued by the CPU A 104A into a corresponding physical address, which is then used to access the original requested memory location in the main memory 102.

[0005] A MMU may translate a virtual address into a physical address by referencing data structures, such as translation tables, stored in main memory. FIG. 2 is a block diagram illustrating an exemplary conventional implementation of translating a virtual address 202 into its corresponding physical address by a MMU. FIG. 2 is discussed with reference to the computer system 100 illustrated in FIG. 1. Upon receiving the virtual address 202, a MMU in the computer system 100, such as the MMU A 106A, first references a page directory 204 in the main memory 102. A page directory 204 contains multiple entries, each of which maps to a page table. For example, an entry 208 in the page directory 204 maps to a page table 206. A page table contains the physical address information required to translate a virtual address to its corresponding physical address. Often, available physical memory is divided into a plurality of pages. Each entry of a page table is mapped with an individual physical page. For example, the page table entry (“PTE”) 210 in the page table 206 points to a physical page 212 in the main memory 102.

[0006] Consequently, to translate a virtual address 202 into its corresponding physical address, a MMU needs to have at least one reading of the page directory 204 and one reading of the page table 206. In some implementations, more layers of page directories and page tables may be provided. As a result, translating a virtual address into its corresponding physical address may consume a significant amount of system clock time as well as bus bandwidth; and therefore, may cause undesirable delay for the operation of a CPU.

[0007] Thus, alternatively, a MMU uses cache-like memories such as translation buffers (“TB”) to speed up the process of translating a virtual address into a physical address. For example, as shown in FIG. 1, each MMU in the computer system 100 contains a TB. For instance, the MMU A 106A includes a TB A 108A.

[0008] A TB is a cache that keeps track of recently used address mappings between a virtual address and a physical address. As shown in FIG. 3, a MMU can translate a virtual address 202 into its corresponding physical address 302 by first looking into a TB 304. If the virtual address 202 has been used recently, then the TB 304 probably holds information concerning the mapping between the virtual address 202 and its corresponding physical address 302. If the TB 304 does hold the needed information, the TB 304 can quickly provide the physical address 302 for the virtual address 202, thus eliminating the need for the MMU to spend several clock cycles accessing the page directory 204 and the page table 206 in the main memory 102. This occurrence is usually referred to as “TB hit.” On the other hand, when the TB 304 cannot provide a physical address 302 for the virtual address 202, a “TB miss” occurs. The MMU then needs to access the page directory 204 and the page table 206 in the main memory 102, as illustrated in FIG. 2, for the purpose of updating the TB 304. Such a process is usually referred to as a “TB fetch.” Referring back to FIG. 2, the PTE 210 also contains a V bit 214 and an A bit 216. The V bit (“Valid bit”) 214 indicates whether the mapping in the PTE 210 is valid. The A bit (“Access bit”) 216 indicates whether the PTE 210 has been accessed by, for example, a MMU in the computer system 100. At times, the mapping between a virtual address 202 and its corresponding physical page address 212 may change. For example, the PTE 210 may no longer be mapped to the physical address page 212. In such a case, the Valid bit 214 is cleared, signaling that the mapping between the virtual address 202 and the physical page address 212 is no longer valid. At times, the access right on the physical page address 212 is changed, for example, from a read-and-write permission to a read-only permission; and/or the virtual-physical address mapping changes, i.e., the virtual address 202 may be mapped to another physical page address in the main memory 102. In these two situations, the Valid bit 214 of the PTE 210 remains set.

[0009] Conventionally, when the PTE 210 becomes invalid, which occurs when, for example, its Valid bit 214 is cleared or its page permission and/or virtual-physical mapping changes, the operating system in the computer system 100 instructs the CPU(s) to invalidate any TB entry that caches the virtual-physical address mapping in the PTE 210, so to avoid page permission mismatches, stale virtual-physical address mappings, or the like. Such invalidation is usually referred to as a “TB invalidate” or “TB flush.” A TB flush is time-consuming and expensive, especially when multiple CPUs and, hence, multiple TBs, exist in a computer system.

[0010] Therefore, there exists a need for reducing the number of TB flushes that an operating system needs to issue in order to purge invalid virtual-physical address mapping information from TBs in a computer system.

[0011] The invention addresses the above-identified need by providing a method, computer system, and computer-readable medium for reducing the number of TB flushes that an operating system needs to issue in order to purge invalid virtual-physical address mapping information from TBs in a computer system.

[0012] One aspect of the invention utilizes the Access bit contained in a PTE to reduce the number of TB flushes and therefore improves the performance of a computer system. The Access bit is used to indicate whether the PTE has been used by the computer system. If the page table entry has been used by the computer system since it was last flushed, then at least one TB may contain an entry concerning the virtual-physical address mapping in the PTE. Only upon determining that the PTE is going to become invalid and that the Access bit in the PTE is set does the operating system of the computer system issue a TB flush to purge the invalid PTE information stored in a TB. Otherwise, if the Access bit is clear, even if the PTE becomes invalid, no TB flush is issued by the operating system of the computer system, because no TB can contain information concerning the PTE.

[0013] According to another aspect of the invention, upon determining that the PTE is to become invalid, an interlocked operation is used to update the PTE with valid content. The interlocked operation is to ensure that no processor may be simultaneously inserting a TB entry for this virtual address. If the interlocked operation fails, then the operating system can detect whether a CPU has accessed the PTE; and therefore, a TB flush may be required.

[0014] In accordance with a further aspect of the invention, the computer system includes at least one CPU and associated TB. The computer system includes memory. The CPU, coupled with the memory, executes computer-executable instructions that reduce the number of TB flushes issued for the computer system.

[0015] In summary, the invention reduces the number of TB flushes an operating system for a computer system needs to issue. The invention thus reduces the expenses associated with TB flushes and improves the performance of the computer system.

[0020] Referring back to FIG. 2, the PTE 210 in the page table 206 includes an Access bit 216. The value of the Access bit 216 indicates whether the PTE 210 has been accessed by the computer system 100. If the Access bit 216 is set, then the PTE 210 has been accessed by the computer system 100; as a result, at least one TB in the computer system 100 may contain an entry corresponding to the PTE 210. On the other hand, if the Access bit 216 is clear, then no access to the PTE 210 has occurred; as a result, no TB in the computer system 100 contains an entry concerning the virtual address 202 and its corresponding physical page address 212.

[0021] Exemplary embodiments of the invention utilize the Access bit in a PTE to reduce the number of TB flushes an operating system of a computer system needs to issue. The following pseudo code illustrates one exemplary usage of the Access bit in a PTE by an exemplary embodiment of the invention.

[0022]

	if (PTE Access bit == 0) AND (InterlockedSwap
	(new PTE, old PTE) == success) {
	No TB Flush
	}
	else {
	TB Flush.
	}

[0023] In the exemplary embodiment of the invention, when a PTE is to become invalid and the Access bit of the PTE is clear, an interlocked operation updates the old PTE content with the new and valid PTE content. As those of ordinary skill in the art will appreciate, an interlocked operation ensures atomic operation of a data structure, such as the PTE, that is shared by multiple processes or threads. The interlocked operation is to ensure that no CPU may be simultaneously inserting a TB entry for the virtual address contained in the PTE.

[0024] If the interlocked operation succeeds, then the PTE has not been accessed by a CPU in the computer system. Thus no corresponding TB entries exist in the TBs of the computer system and no TB flush is necessary.

[0025] On the other hand, as shown in the above pseudo code, if the Access bit of the PTE is set or the interlocked operation fails, a TB flush is required. When the Access bit of the PTE is set, at least one CPU in the computer system has accessed the PTE and therefore at least one TB in the computer system may contain an entry concerning the PTE; thus a TB flush is necessary. Meanwhile, when the interlocked operation fails, at least one CPU has accessed the PTE during the interlocked operation; hence a TB may contain the invalid virtual-physical memory mapping; therefore a TB flush may be necessary.

[0026] Consequently, in the exemplary embodiment of the invention, an operating system needs to issue a TB flush only when the Access bit of a PTE is set or an interlocked operation to update an invalid PTE fails.

[0027] While the preferred embodiments of the invention have been illustrated and described, it will be appreciated that various changes can be made therein without departing from the spirit and scope of the invention. For example, in some embodiments of the invention, the main memory 102 may contain a data structure not in the same form as the illustrated page table 210 or the illustrated PTE 210. Embodiments of the invention is applicable as long as the main memory 102 contains a data structure that includes information mapping a virtual address to a physical address and that includes an Access bit indicating whether the data structure has been accessed by a CPU.