Silicon Graphics, Incorporated

Silicon Graphics International Corporation

Curt F Schimmel

Steven C Miller

Martin M Deneroff

Charles E Leiserson

Bradley C Kuszmaul

Luis F Stevens

Krste Asanovic

Narayanan Ganapathy

Larry Rudolph

Lixin Zhang

John B Carter

Michael Parker

Bhanuprakash Subramanya

A processor may operate in one of a plurality of operating states. In a Normal operating state, the processor is not involved with a memory transaction. Upon receipt of a transaction instruction to access a memory location, the processor transitions to a Transaction operating state. In the Transaction operating state, the processor performs changes to a cache line and data associated with the memory location. While in the Transaction operating state, any changes to the data and the cache line is not visible to other processors in the computing system. These changes become visible upon the processor entering a Commit operating state in response to receipt of a commit instruction. After changes become visible, the processor returns to the Normal operating state. If an abort event occurs prior to receipt of the commit instruction, the processor transitions to an Abort operating state where any changes to the data and cache line are discarded.

System and method for performing memory operations in a computing system

An address translation unit generates a physical address for access to a memory from a virtual address using either a translation lookaside buffer or a segmentation buffer. If the virtual address falls within a predetermined range, the address translation unit will use the segmentation buffer to generate the physical address. Upon generation of the physical address, the memory will either receive data from or provide data to a processor in accordance with the instructions being processed by the processor.

System and method for performing address translation in a computer system

An scalable multi-reader/single-writer lock implementation that eliminates contention for lock data structures that can occur in large symmetric multi-processing (SMP) computer systems. The present invention includes a registry head data structure for each critical resource within the computer system. Linked to each of the registry head data structures are one or more client data structures that represent each client (i.e., process, thread, interrupt handler, and the like) that needs read and/or write access to the critical resource represented by the registry head data structure. Further, five operations&mdash;Initialization, Adding a Client, Deleting a Client, Obtaining Read Access, and Obtaining Write Access&mdash;are provided in order to achieve the goal of contention elimination.

System, method and computer program product for implementing scalable multi-reader/single-writer locks

In a method for providing concurrent access to virtual memory data structures, a lock bit for locking a virtual page data structure is provided in a page table entry of a page table. The page table is configured to map virtual pages to physical pages. Then, a first thread specifying an operation on the virtual page data structure is received. The first thread is provided exclusive access to the virtual page data structure by setting the lock bit in the page table entry such that other threads are prevented from accessing the virtual page data structure. A wait bit also may be provided in the page table entry to indicate that one or more of the other threads are in a wait queue when the first thread has exclusive access to the data structure. When the first thread no longer needs exclusive access to the data structure, a second thread is selected from among the other threads and is provided with exclusive access to the data structure.

Method for managing concurrent access to virtual memory data structures

A method, system and computer program product for dynamically allocating large memory pages of different sizes. Each process can select multiple page sizes. An algorithm referred to as a &ldquo;Coalescing Daemon&rdquo; is used to allocate large pages. &ldquo;High water marks&rdquo; are specified to the operating system. A high water mark is the maximum percentage of total system memory that the Coalescing Daemon coalesces for a given page size. The high water marks are used to allocate a number of free memory pages for each specified page size. Separate freelists are created and maintained for each page size. Each freelist comprises a linked list of data structures that represent free physical memory pages. A bitmap is set-up by the operating system to represent all memory available to processes. The bitmap is used for determining which memory pages are free during coalescing. The Coalescing Daemon allocates memory pages using a weak, mild and strong coalescing policy. The weak policy is performed first, followed by the mild and the strong policies. The mild and strong policies are performed only if the preceding policy or policies fail. The weak policy searches the bitmap for free contiguous areas of memory and inserts an entry into the associated freelist if found. If the weak policy is unsuccessful, the mild policy attempts to find a suitable chunk of memory which is used to create a contiguous chunk of free memory by migrating busy base pages to other areas. The mild coalescing policy searches the bitmap for a chunk of memory in which the set bits (i.e. the free base pages) are above a tunable predetermined threshold value. Thus, a limited amout of migration is performed according to predetermined threshold. If the mild coalescing policy fails the strong coalescing policy is performed. In the strong coalescing policy, base pages are migrated to create a free chunk, regardless of a threshold amount.

Method, system and computer program product for dynamically allocating large memory pages of different sizes

A system, method and computer program product for sharing memory between fault-isolated cells of a computer system. A page of memory is exported from an exporting cell to an importing cell by selectively opening a hole in a fire-wall that otherwise fault-isolates the exporting cell and the importing cell. The fire-wall opening permits the importing cell to access a specific page of memory in the exporting cell. Access to other memory cells is still prevented by the fire-wall. When a page of memory is exported, a record of the export is generated in the exporting cell. Export records are used to determine whether a requesting cell is permitted to access a requested page of memory and to terminate memory exports in a controlled fashion. When a page of memory is imported, an import record and a proxy page frame data structure are generated in the importing cell. Import records are used to access pages of memory in other cells and to terminate imports in a controlled fashion. Proxy page frame data records are used to maintain fault isolation between cells and to ensure that kernel data is never shared between cells.

System, method and computer program product for page sharing between

A system, method and computer program product for distributing page caches among memory objects and, in a DSM system, among memories in the DSM system. The system, method and computer program product provides a separate page cache for each memory object. Each separate page cache associates page frame data structures that represent pages of memory that store a portion of an associated memory object. A separate mutual exclusion mechanism is provided for each page cache for protecting the integrity of the page caches during page cache operations. Page cache operations, such as adding and deleting page frame data structures, checking and updating state information in page frame data objects, and identifying page frame data objects that correspond to particular memory objects or memory object logical offsets, can be performed for different memory objects in parallel.

System, method and computer program product for organizing page caches

A system, method and computer program product for virtual memory support for TLBs with multiple page sizes that require only minor revisions to existing operating system code and remains compatible with existing applications. The virtual memory support provided herein is transparent to many existing operating system procedures and application programs. Various page sizes such as 4 KB, 64 KB, 256 KB, 1 MB, 4 MB and 16 MB page sizes can be used by application programs and each process can use multiple page sizes. Base page sized PTEs and data structures associated with physical pages (PFDATs) are maintained. Maintaining PFDATs and PTEs at a base page level facilitates upgrading and downgrading of memory pages. In addition, different processes can have different views of the same data. Support is provided for upgrading and downgrading memory pages. Examples of operating system methods that can be used for virtual memory support for multiple page sized TLBs are provided herein. Such examples include downgrading and upgrading memory pages, large page faulting and prefaulting, large page validation and page table entry setup.

Method, system and computer program product for virtual memory support

A system, method and computer program product for reverse mapping a page of memory to one or more data structure references, such as page table entries, that reference the page of memory. A number m of fields of a page frame data structure are reserved for storing reverse mapping data for a page of memory. Each reserved field can store a reverse map entry for pointing to a data structure reference, such as a page table entry, that references the page of memory that is represented by the page frame data structure. Where a number n of references to the page of memory is greater than the number m of reserved fields, a reverse map table is generated for storing additional reverse map entries. When a reverse map table is generated, one of the reverse map entries in one of the reserved fields of the page frame data structure is moved to the reverse map table. A pointer to the reverse map table is placed in the now-vacant reserved field. Indexes in the page table entries are used to identify and remove the reverse map entries when a page table is deallocated. Reverse map tables can be generated as needed and can be dynamically sized to accommodate any number of reverse map entries.

Reverse mapping page frame data structures to page table entries

A system and method for maintaining consistency between translational look-aside buffers (TLB) and page tables. A TLB has a TLB table for storing a list of virtual memory address-to-physical memory address translations, or page table entries (PTES) and a hardware-based controller for invalidating a translation that is stored in the TLB table when a corresponding page table entry changes. The TLB table includes a virtual memory (VM) page tag and a page table entry address tag for indexing the list of translations The VM page tag can be searched for VM pages that are referenced by a process. If a referenced VM page is found, an associated physical address is retrieved for use by the processor. The TLB controller includes a snooping controller for snooping a cache-memory interconnect for activity that affects PTEs. The page table entry address tag can be searched by a search engine in the TLB controller for snooped page table entry addresses. The TLB controller includes an updating module for invalidating or updating translations associated with snooped page table entry addresses. Translations in TLBs are thus updated or invalidated through hardware when an operating system changes a PTE, without intervention by an operating system or other software.

System and method for maintaining translation look-aside buffer (TLB)

The present invention is a system, method, and computer program product for dynamically sizing a hash table when the average number of records per bucket in the hash table exceeds a maximum average number of records per bucket. In one embodiment, the hash table employs a modulo hashing function. In a second embodiment, the number of buckets is grown by a multiple of the previous number of buckets and records are re-hashed using a lazy re-hashing modulo algorithm that re-hashes records in a hash bucket only when those records are searched. In the second embodiment, when a hash table is re-sized, each new bucket is provided with a logical back pointer, or index, to a pre-existing bucket that potentially contains records that belong in the new bucket. When a search is directed at a new bucket, the logical back pointer, or index, directs the search to a pre-existing bucket. When a search of a pre-existing bucket finds a data record that belongs in a new bucket, the record is moved to the new bucket. When there are no more records in a pre-existing bucket that belong in a new bucket, the logical back pointer from the new bucket to the pre-existing bucket is removed. Preferably, the logical back pointer is stored in the bucket where a regular pointer would normally be stored so that no extra space is needed.

Growing community of inventors

San Ramon, CA, United States of America

Curt F Schimmel