Broadcast demap for deallocating memory pages in a multiprocessor system

• US 5,497,480 A
• Filed: 07/29/1994
• Issued: 03/05/1996
• Est. Priority Date: 12/31/1990
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Hayes, Norman M., Sindhu, Pradeep, Frailong, Jean-Marc, Nanda, Sunil
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US08/282,170
• Time in Patent Office: 585 Days
• Field of Search: 395/425, 395/417, 395/486, 395/462, 395/471, 395/493, 370/94.1
• US Class Current: 711/166
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines
• CPC Class Codes: G06F 2212/682 Multiprocessor TLB consistency

Abstract

A method and apparatus for removing a page table entry from a plurality of translation lookaside buffers ("TLBs") in a multiprocessor computer system. The multiprocessor computer system includes at least two processors coupled to a packet-switched bus. Page table entries are removed from a plurality of TLBs in the multiprocessor computer system by first broadcasting a demap request packet on the packet-switched bus in response to one of the processors requesting that a page table entry be removed from its associated TLB. The demap request packet includes a virtual address and context information specifying this page table entry. Controllers reply to the demap request packet by sending a first reply packet to the controller that sent the original demap request packet to indicate receipt of the demap request packet. If a controller removes the page table entry from its associated TLB, that controller sends a second demap reply packet to indicate that the page table entry has been removed from its associated TLB.

Claims

1. A method for removing an invalid page table entry from a plurality of translation lookaside buffers (TLBs) in a multiprocessor computer system having at least two processors coupled to a packet-switched bus, said invalid page table entry being specified by a virtual address and a process identification, said invalid page table entry being an invalid mapping between said virtual address and a physical address, said method comprising the steps of:

broadcasting a demap request packet on said packet-switched bus by a first controller via a first bus watcher in response to a first processor of said at least two processors requesting that said invalid page table entry be removed from a first TLB controlled by said first controller, wherein said demap request packet comprises data specifying said virtual address and process identification of said invalid page table entry;

receiving said demap request packet on said packet-switched bus by a second controller via a second bus watcher;

sending a first demap reply packet on said packet-switched bus to said first controller via said first and second bus watchers by said second controller to indicate that said second controller has received said demap request packet;

checking by said second controller to determine whether a second TLB controlled by said second controller contains said invalid page table entry by comparing said virtual address and said process identification to entries contained in said second TLB;

completing pending operations for a second processor of said at least two processors, wherein said second TLB stores page table entries for use by said second processor;

removing said invalid page table entry from said second TLB by said second controller if said invalid page table entry is contained in said second TLB;

sending a second demap reply packet on said packet-switched bus to said first controller via said second and first bus watchers by said second controller after removal of said invalid page table entry from said second TLB to indicate that said second controller has processed said demap request packet.

2. The method of claim 1, wherein the step of broadcasting further comprises the steps of:

broadcasting a header during a first cycle, said header specifying a destination and said first processor as a source;

broadcasting data during a second cycle, said data specifying said virtual address and said process identification of said invalid page table entry.

3. The method of claim 2, further comprising a step of snooping on said packet-switched bus by said first controller for reply packets identifying said first processor as their destination.

4. The method of claim 3, wherein said multiprocessor computer system further includes a third controller coupled to a third processor and to said packet-switched bus, said method further comprising a step of snooping on said packet-switched bus by said third controller for packets identifying said third processor as their destination.

5. The method of claim 4, said method further comprising a step of snooping on said packet-switched by said second controller for packets identifying said second one of said at least two processors as their destination.

6. The method of claim 5, wherein said step of sending said first demap reply packet is performed by both said second controller and said third controller when said second and third controllers snoop said demap request packet and said demap request packet specifies said destination as being equal to all logic 0'"'"'s.

7. An apparatus for removing an invalid page table entry from a plurality of translation lookaside buffers (TLBs) in a multiprocessor computer system having at least two processors coupled to a packet-switched bus, said invalid page table entry being specified by a virtual address and a process identification, said apparatus comprising:

a first controller, coupled to said packet switched bus and a first one of said at least two processors, said first controller for broadcasting a demap request packet on said packet-switched bus in response to said first one of said at least two processors requesting that said invalid page table entry be removed from a first TLB controlled by said first controller, wherein said demap request packet comprises data specifying said virtual address and process identification of said invalid page table entry; and

a second controller coupled to said packet-switched bus and a second one of said at least two processors, said second controller for receiving said demap request packet on said packet-switched bus, for sending a first demap reply packet on said packet-switched bus to said first controller to indicate that said second controller has received said demap request packet, for determining whether a second TLB controlled by said second controller contains said invalid page table entry by comparing said virtual address and said process identification to entries contained in said second TLB, for removing said invalid page table entry from said second TLB if said invalid page table entry is contained in said second TLB, and for sending a second demap reply packet on said packet-switched bus to said first controller after removal of said invalid page table entry from said second TLB to indicate that said second controller has processed said demap request packet, said second controller allowing said second one of said at least two processors to complete pending operations before said second controller removes said invalid page table entry from said second TLB.

8. The apparatus of claim 7, wherein said demap request packet is a two cycle packet in which a header is broadcast during a first cycle and data is broadcast during a second cycle, said header specifying a destination and said first one of said at least two processors as a source, said data specifying said virtual address and said process identification of said invalid page table entry.

9. The apparatus of claim 8, the apparatus further comprising a first bus watcher, coupled to said first controller and said packet-switched bus, for snooping on said packet-switched bus for reply packets having said first one of said at least two processors specified as their destination.

10. The apparatus of claim 9, wherein the multiprocessor computer system further includes:

a second bus watcher, coupled to said second controller and said packet-switched bus, for snooping on said packet-switched bus for reply packets having said second one of said at least two processors specified as their destination, for sending a reply packet if said demap request packet specifies said second one of at least two processors as said destination, and for sending a reply packet if said demap request packet specifies all logic 0'"'"'s as said destination; and

a third bus watcher, coupled to said third controller and said packet-switched bus, for snooping on said packet-switched bus for reply packets having said third processor specified as their destination, for sending a reply packet if said demap request packet specifies said third processor as said destination, and for sending a reply packet if said demap request packet specifies all logic 0'"'"'s as said destination.

11. A method for removing a page table entry from a plurality of cache memories in a multiprocessor computer system having at least two processors coupled to a packet-switched bus, the method comprising the steps of:

broadcasting a demap request packet on the packet-switched bus by a first controller via a first bus watcher in response to a first one of the at least two processors requesting that the page table entry be removed from a first cache memory controlled by a first cache controller, the demap request packet including a virtual address and context information specifying the page table entry;

receiving the demap request packet on the packet-switched bus by a second cache controller via a second bus watcher;

sending a first demap reply packet on the packet-switched bus to the first cache controller via the first and second bus watchers by the second cache controller to indicate that the second cache controller has received the demap request packet;

removing the page table entry from the second cache memory by the second cache controller if the page table entry is contained in the second cache memory; and

sending a second demap reply packet on the packet-switched bus to the first cache controller via the second and first bus watchers by the second cache controller to indicate that the second cache controller has processed the demap request packet.