Abstract:
An address translation buffer system in which a searching time of an address translation buffer is shortened. The address translation buffer includes an address translation buffer connected to a translation table for translating a virtual address to a real address, the address translation buffer containing a plurality of columns holding a plurality of entries each having a pair of the virtual address and the real address translated based on the translation table and also having a virtual machine classification indicative of a type of the virtual address, a plurality of column control circuits for specifying columns of the address translation buffer with a combination of a lower part of the virtual address and the virtual machine classification as an entry, and circuits, in accordance with an invalidation instruction for purging one of the entries of the address translation buffer, for searching one of the columns of the address translation buffer having one of the entries of the address translation buffer coincided with the virtual machine classification entry of the invalidation instruction and for invalidating the entry including a specified field. It is unnecessary to search a group of columns having values other than the specified virtual machine classification.

Description:
BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1A is a diagram for explaining the conception of address translating operation in a virtual storage system; 
     FIG. 1B shows a relationship between virtual and real address spaces; 
     FIG. 2 is a diagram for explaining the conception of a virtual machine system; 
     FIG. 3A is a block diagram of a general arrangement of an address translation buffer system in accordance with the present invention; 
     FIG. 3B schematically shows how a real page address is obtained from a virtual page address field under an IPTE instruction in the present invention; 
     FIG. 3C shows set/reset states of a VM mode or class flag; 
     FIG. 3D shows a microprogram containing a VM class flag and a VM class operation flag; 
     FIG. 3E is a flowchart showing an execution state of an IPTE instruction; 
     FIGS. 4A and 4B show an example of division of an address translation buffer based on machine attributes or VM classes; 
     FIGS. 5A and 5B show block diagrams of an arrangement of an embodiment of the present invention; 
     FIGS. 6A and 6B are diagrams for explaining how the address translation buffer is invalidated by invalidation of a page table entry in the virtual machine system; and 
     FIGS. 7A and 7B show block diagrams of an arrangement of another embodiment of the present invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Embodiments of the present invention will be detailed below with reference to the accompanying drawings. 
     FIGS. 5A and 5B show block diagrams of an arrangement of a first embodiment of the present invention which includes an input register 20 to an address translation buffer. The input register 20 has a virtual address upper part 31, a virtual address lower part 32, a VM class field 30, an address translation buffer division enable bit 51, a real address 33, a validity bit 34 and an offset address 35. At the time of writing/reading data from the buffer, the contents of a VM mode flag shown in FIG. 3D is input to the VM class field 30. Also included in the first embodiment is an address translation buffer 21 which registers the virtual address upper parts 31, VM class (flag indicative of distinction between host and guest in the illustrated example) fields 30, real addresses 33 and validity bits 34 in its entries. Reference numeral 36 denotes an output of the virtual address upper part of the address translation buffer 21, and numeral 37 denotes an output of the real address of the address translation buffer 21. Numeral 22 denotes a real address output register 22, and a comparison circuit 23, in an address translation buffer reference, compares an output of the virtual address upper part 31 of the input register 20 with the output 36 of the virtual address upper part of the address translation buffer 21. Numeral 24 denotes a validity judgement circuit for the real page address. Numeral 41 denotes a column control circuit for addressing the host virtual address (host column control circuit), 42 a column control circuit for addressing the guest virtual address (guest column control circuit). It is assumed in the present embodiment that, when the value of the VM class is &#34;0&#34;, the then virtual address is treated as a host virtual address; whereas, when the value of the VM class is &#34;1&#34;, it is treated as a guest virtual address. 
     In FIG. 5A, more specifically, the address translation buffer 21 is divided into two zones each having an equal number of entries, that is, an entry zone (host zone) 21-1 where host virtual address lower parts are continually registered and an entry zone (guest zone) 21-2 where guest virtual address lower parts are continually registered, on the basis of the VM classes. Explanation will next be made as to the entry registering, reading operation and purging operations when the address translation buffer 21 is divided as shown in FIG. 5A. In this case, the address translation buffer division enable bit 51 has a value of &#34;1&#34; fixedly set. 
     When the address translating operation causes a real address corresponding to the virtual address to be found, the values of the VM class field 30, virtual address upper part 31, virtual address lower part 32 and real address 33 are set in the input register 20 in order to register an entry including a pair of the virtual and real addresses in the address translation buffer 21. When the VM class field 30 of the input register 20 has a value of &#34;0&#34;, the virtual address is handled as a host virtual address (refer to FIG. 3C) so that the host column control circuit 41 receives &#34;1&#34; from the address translation buffer division enable bit 51, &#34;0&#34; from the VM class field 30 and the virtual address lower part 32, whereby the values of the virtual address upper part 31, VM class field 30 and real address 33 of the input register 20 as well as &#34;1&#34; of the validity bit 34 indicative of the validity of the entry are written in a column specified by the virtual address lower part 32 within the host zone 21-1 of the address translation buffer 21, thus enabling reading from the entry. When the VM class field 30 of the input register 20 has a value of &#34;1&#34;, the virtual address is handled as a guest virtual address so that the guest column control circuit 42 receives &#34;1&#34; from the address translation buffer division enable bit 51, &#34;1&#34; from the VM class field 30 and the virtual address lower part 32, whereby the values of the virtual address upper part 31, VM class field 30 and real address 33 of the input register 20 as well as &#34;1&#34; as the validity bit 34 of the entry are written in a column specified by the virtual address lower part 32 within the guest zone 21-2 of the address translation buffer 21, thus enabling reading from the entry. The attribute and validity can be judged by the validity judgement circuit (28 in FIG. 3A) connected to the address translation buffer 21. When the validity bit of the read-out entry has a value of &#34;0&#34;, the value of the read-out entry is invalid. 
     In this way, when the VM class field 30 is used for the column control, the address translation buffer can be divided into the host and guest zones. 
     Even in the case where it is desired to read out the entry already registered in the address translation buffer 21, when the VM class field of the input register 20 has a value of &#34;0&#34;; &#34;1&#34; of the address translation buffer division enable bit 51, &#34;0&#34; of the VM class field 30 and the virtual address lower part 32 are input to the host column control circuit 41, so that the virtual address upper part output 36 and the real address output 37 can be read out from the column specified by the virtual address lower part 32 within the host zone 21-1 of the address translation buffer 21. When the VM class field of the input register 20 has a value of &#34;1&#34;, &#34;1&#34; of the address translation buffer division enable bit 51; &#34;1&#34; of the VM class field 30 and the virtual address lower part 32 are input to the guest column control circuit 42, so that the virtual address upper part output 36 and the real address output 37 can be read out from the column specified by the virtual address lower part 32 within the guest zone 21-2 of the address translation buffer 21. The read-out virtual address upper part output 36 is compared by the comparison circuit 23 with the virtual address upper part 31 of the input register 20. When finding a coincidence therebetween if an entry is valid, the comparison circuit 23 outputs &#34;1&#34; to the validity judgement circuit 24. At this time, the validity judgement circuit 24 sets the real address output 37 received from the address translation buffer 21 to be valid, thereby setting the valid real address output at the real address output register 22. When finding a non-coincidence between its inputs, the comparison circuit 23 performs such address translating operation as shown in FIG. 1 to register the address in the address translation buffer 21 based on the VM class and to later re-read it. 
     When the address translation buffer 21 is divided into two as shown in FIG. 5A, its total capacity does not vary compared to the non-division case, but the number of columns which can be input as the virtual address lower part 32 for either one of the host and guest will be reduced. Accordingly, it becomes necessary to add the number of bits in the address of the decreased lower part to the virtual address upper part 31 and then to write it into the address translation buffer 21. In the case of the two divisions of the address translation buffer 21, the capacity of the upper part is increased by an amount corresponding to one bit. However, since the address translation buffer 21 has originally a bit width of about 4 bytes per an entry, the above capacity increase is not so large compared to the entire capacity. 
     In the purging operation of the address translation buffer 21, when the virtual address lower part 32 is input as a column to the host column control circuit 41 or the guest column control circuit 42 to invalidate the both entries of the host and guest zone 21-1 and 21-2, &#34;0&#34; is written into the validity bit 34 of the entry. This results in that the entry cannot be read out until an entry is registered in the column in question. 
     The IPTE instruction for invalidating the host page table entry invalidates a host virtual address which is registered in the address translation buffer 21 as an entry (refer to FIG. 3B). When it is desired to perform entry searching operation to invalidate the guest virtual address as the entry registered in the address translation buffer 21, since the address translation buffer 21 is divided into the host and guest zones 21-1 and 21-2 based on the VM class field, it is merely required to perform searching operation over only the entries within the guest zone 21-2. 
     In the search of the guest zone; &#34;1&#34; of the address translation buffer division enable bit 51, &#34;1&#34; of the VM class field 30 and the virtual address lower part 32 are input to the guest column control circuit 42; while the virtual address lower part 32 is a value added sequentially by &#34;1&#34; from all &#34;0&#34;s to an upper limit of the number of entries as the specified attribute. And the real addresses registered in the respective entries are read out and compared with the real address of the invalidation page table entry in the comparator 25 as shown in FIG. 3A, and &#34;0&#34; is input to the validity bit 34 having the coincided entry. As a result, the searching operation is carried out only over the guest zone 21-2 of the address translation buffer 21. 
     In this way, since a zone to be searched can be identified within the address translation buffer 21 in FIG. 5A, the number of entries to be searched can be reduced compared to that in the prior art address translation buffer. 
     Explanation will next be made as to how to switch between the invalidation of the guest page table entry and the invalidation of the host page table entry. Referring to FIGS. 3D and 3E, the machine when the IPTE instruction is issued is determined to be put in its host mode if the VM mode flag is &#34;0&#34;, while the machine is determined to be put in its guest mode if the VM mode flag is &#34;1&#34; (step 301 in FIG. 3E). In the latter case, &#34;1&#34; is set at the VM mode operation flag in FIG. 3D so that the contents of the purging operation in place of the contents of the VM mode flag is sent to the VM class field 30 in FIG. 3A during the purging operation (step 303). In order to invalidate columns within the guest zone of the address translation buffer 21, the buffer virtual address specified by the IPTE instruction is sent from the input register 20 to the control circuit of the address translation buffer 21 and also to the comparison circuit 23 where the coincided column entry is purged (step 305). 
     In the former case, &#34;0&#34; is set at the VM mode operation flag for sending the VM mode field (step 302). In order to invalidate the host zone of the address translation buffer 21, the virtual address is sent to the address translation buffer 21 where the coincided column entry within the host mode zone is purged (step 304). After the purging operation, &#34;1&#34; is set at the VM mode operation flag (step 306), the buffer virtual address is set to invalidate the coincided entry within the guest zone, the virtual address lower part is counted up, whereby a series of searching operations is carried out (step 310) so that an output of the comparison circuit 23 causes the valid flag of the coincided entry to be reset (step 312). 
     Shown in FIG. 6A is how to invalidate the address translation buffer when it is desired to invalidate the aforementioned guest page table entry. In this case, the host real address (c) obtained through the address translating operation with use of both the invalidation guest page table entry (a→b) and the host translation table (b→c) is compared with the host real address (c) read out from the entry of the address translation buffer containing the guest virtual address indicated by the invalidation guest page table entry, so that a coincidence therebetween causes invalidation of the entry in question of the address translation buffer. In the case of a non-coincidence therebetween, it is judged that another new translation pair is already registered and the entry of the address translation buffer is not invalidated. In this connection, the host page table entry used in this address translating operation is not invalidated. 
     Shown in FIG. 6B is how to invalidate the address translation buffer when it is desired to invalidate the aforementioned host page table entry. In this case, the host real address (c) obtained through the address translating operation with use of the invalidation host page table entry (a→b) is compared with the host real address (c) read out from the entry of the address translation buffer, so that a coincidence therebetween causes invalidation of the entry of the address translation buffer. In this connection, the entries of the address translation buffer which are required for reading the host real address for comparison include the entry containing the host virtual address indicated by the invalidation host page table entry and also includes the entry which uses the host page table entry at the time of the 2 guest and host stages of address translating operation and which contains the guest virtual address registered in the address translation buffer. However, it is impossible for the address translation buffer to easily identify that one of the entries of the address translation buffer containing the guest virtual address which uses the invalidation host page table entry. 
     Explanation will then be made by referring to FIG. 5B as to the operation when the address translation buffer 21 is not divided according to the VM class. In this case, &#34;0&#34; is set at the address translation buffer division enable bit 51. At this time, the input of the VM class field 30 to the host and guest column control circuits 41 and 42 becomes invalid in such a manner that, when receiving an input from the virtual address lower part 32, the address translation buffer 21 operates as an address translation buffer which inputs a virtual address lower part 32. The registering, reading and purging operations over the entries of the address translation buffer 21 are the same as those in the prior art address translation buffer. 
     As shown in FIG. 5B, when the address translation buffer 21 is not divided into zones, the column input depends only on the virtual address lower part 32 and an entry as new as possible is stored therein, whereby an improved hit rate can be expected. 
     When the execution time of the all-entries searching operation in the purging operation becomes insignificant, it is desirable not to divide the address translation buffer based on the VM class, because the hit rate can be improved and therefore the effective processing time of the system can be shortened. The division (FIG. 5A) and non-division (FIG. 5B) of the address translation buffer 21 into address spaces can be controllably selected depending on the input of the address translation buffer division enable bit 51 thereto. Change-over between &#34;0&#34; and &#34;1&#34; of the address translation buffer division enable bit 51 is possible when the address translation buffer 21 is put in its fully empty state, that is, when the validity bits 34 of all entries of the address translation buffer 21 have all &#34;0&#34;. In particular, with respect to the purging operation, when the value of the address translation buffer division enable bit 51 is suitably selected depending on the characteristics of a system and program to be used, the effective processing time can be further shortened. 
     FIGS. 7A and 7B show block diagrams of an arrangement of another embodiment of the present invention. In the virtual machine system, further allocation of the OSs on the guests may be carried out, in which case the respective OSs to be managed by the guests are treated as sub-guests. The `sub-guests` will be referred to as the s-guests, while guests (main guests) having the s-guests placed thereunder will be referred to as the m-guests, hereinafter. A relationship in the address translating operation between the s- and m-guests is similar to that in the address translating operation between the m-guests and host, so that the real addresses of the s-guests obtained from the virtual addresses of the s-guests based on an s-guest translation table are allocated to an m-guest virtual address space. 
     In this case, as shown in FIG. 7A, the address translation buffer 21 is divided into a host zone 21-1, an m-guest zone 21-2 and an s-guest zone 21-3; whereas, the column control circuit is made up of 3 sets of column control circuits, that is, a host column control circuit 41 for the host virtual addresses, a m-guest column control circuit 42 for the m-guest virtual addresses, and an s-guest column control circuit 43 for the s-guest virtual addresses. It is assumed in this example that a value &#34;1&#34; is set at the address translation buffer, while, for example, &#34;00&#34; is set at the VM class field 30 for the host, &#34;10&#34; is set thereat for the m-guests, and &#34;01&#34; is set thereat for the s-guests. When the values of the address translation buffer division enable bit 51, VM class field 30 and virtual address lower part 32 are input to the host column control circuit 41, m-guest column control circuit 42 and s-guest column control circuit 43, the entries for the registering, reading and purging operations of the address translation buffer 21 can be specified to the respective divided zones, as in the FIG. 5A. 
     As shown in FIG. 7A, when the address translation buffer 21 is divided into the host, m-guest and s-guest zones, the purging operation of the address translation buffer which follows is only required to be carried out based on the VM class field 30 of the invalidation page table entry under control of the IPTE instruction. When it is desired to invalidate the s-guest page table entry, the entry within the s-guest zone 21-3 registered in the address translation buffer 21 with the s-guest virtual address is made invalid. When it is desired to invalidate the m-guest page table entry, the entry within the m-guest zone 21-2 registered in the address translation buffer 21 with the m-guest virtual address is made invalid, and also the searching operation is carried out over the s-guest zone 21-3. When it is desired to invalidate the host page table entry, the entry within the host zone 21-1 registered in the address translation buffer 21 with the host virtual address is made invalid, and the searching operation is also carried out over the m-guest zone 21-2 and s-guest zone 21-3. 
     In the searching operation to the m-guest zone 21-2, &#34;1&#34; of the address translation buffer division enable bit 51, &#34;10&#34; of the VM mode field 30 sending from VM operation flag and the virtual address lower part 32 are input to the m-guest column control circuit 42; while the value of the virtual address lower part 32 is input with values added sequentially by &#34;1&#34; from all &#34;0&#34;s to an upper limit of the number of entries as the specified attribute. And the real address outputs 37 registered in the respective entries are read out and compared with the real address of the invalidation page table entry, and &#34;0&#34; is input to the validity bit 34 having the coincided entry as a result of the comparison. As a result, the searching operation is carried out over only the m-guest zone 21-2 of the address translation buffer 21. In the searching operation over the s-guest zone 21-3, similarly, &#34;1&#34; of the address translation buffer division enable bit 51, &#34;01&#34; of the VM class field 30 and virtual address lower part 32 are input to the s-guest column control circuit 43; while the virtual address lower part 32 is input with a value added sequentially by &#34;1&#34; from all &#34;0&#34;s to an upper limit of the number of entries as the specified attribute. And the real address outputs 37 registered in the respective entries are read out and compared with the real address of the invalidation page table entry, and &#34;0&#34; is input to the validity bit 34 having the coincided entry as a result of the comparison. As a result, the searching operation is carried out only over the s-guest zone 21-3 of the address translation buffer 21. 
     In this way, when the searching zone of the address translation buffer 21 is specified, the number of entries to be searched over the m-guest and s-guest zones 21-2 and 21-3 in the purging operation of the host virtual address as well as the number of entries to be searched over the s-guest zone 21-3 in the purging operation of the m-guest virtual address under the IPTE instruction can be reduced when compared to those in the searching operation of all entries of the prior art. 
     When the address translation buffer 21 is not divided based on the VM class 30, the value of the address translation buffer division enable bit 51 is fixed at &#34;0&#34; as shown in FIG. 5B. This enables realization of the registering, reading and purging operations similar to those of the address translation buffer in the prior art. 
     In the case of the two types of attributes, i.e., guest and host; the VM class flag may comprise one bit. The present invention is not limited to such division examples as shown in FIGS. 5A, 5B, 7A and 7B. For example, when the configuration of the VM class is made to reflect on the arrangement of the host and guest column control circuits, the division ratio between the guest and host zones of the address translation buffer can be changed, a plurality of sub-guest zones (3 to N) can be provided, the number of divisions of the guest zone can be changed, or various patterns of divisions can be implemented.