Method and apparatus for accessing paged objects using a fast division technique

• US 6,401,185 B1
• Filed: 05/27/1999
• Issued: 06/04/2002
• Est. Priority Date: 05/27/1999
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Unietis, David, Sexton, Harlan
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US09/320,578
• Time in Patent Office: 1,104 Days
• Field of Search: 711/112, 711/200, 711/203, 711/209, 711/219, 711/220, 707/521, 707/525, 708/209, 708/103, 708/503, 708/504, 708/650, 710/49
• US Class Current: 711/209
• CPC Class Codes: G06F 12/04 Addressing variable-length words or parts of words
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: G06F 7/727 Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 G06F7/728 takes precedence

Abstract

A fast division technique is provided to calculate the address of a slot in a paged object, when the slot is located on a different page than the beginning of the object. The fast division technique employs arithmetical-logical operations of shifting and masking, that are faster than most hardware implementations of integer division and modulus, respectively. In one aspect, the use of these operations is facilitated by requiring the page size and the size of the page header to be a power of two.

Claims

1. A method of accessing a slot of an object allocated on a plurality of pages, wherein the slot is logically located at an excess displacement from an end of a page upon which a beginning of the object is allocated and each of the pages has a same page size and includes a page header having a same page header size, said method comprising the computer-implemented steps of:

calculating a number of page boundaries crossed by the excess displacement to determine which one of the pages the slot is located upon;

calculating a page offset for an address of the slot by adding a remainder of the excess displacement modulo the page size and the number of crossed page boundaries in units of the page header size; and

accessing the slot at the page offset from a beginning of the one of the pages.

2. The method of claim 1, wherein calculating a number of page boundaries crossed by the excess displacement includes the step of shifting the excess displacement.

3. The method of claim 1, further comprising the step of masking the excess displacement to calculate the remainder.

4. A method of managing memory in a paged memory system, said method comprising the computer-implemented steps of:

allocating memory for a plurality of pages, each of the pages comprising 2^M bytes;

padding respective page headers of the pages so that 2^K bytes are allocated for each of the pages; and

accessing a slot of an object allocated on a plurality of the pages, wherein the slot is located at an excess displacement from an end of a page upon which a beginning of the object is allocated, by calculating a quotient and remainder of the excess displacement modulo 2^M−

2^K, said quotient indicating a page containing the slot and said remainder indicating a logical offset on the page containing the slot.

5. The method of claim 4, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K includes the steps of;

shifting the excess displacement by K bits to produce a first partial quotient;

masking the excess displacement to retain the K least significant bits thereof to produce a first partial remainder;

calculating a second partial quotient and a second partial remainder of the first partial quotient by 2<sup>M−

K</sup>−

1;

shifting the second partial remainder by K bits and adding a result thereof and the first partial remainder to produce the remainder; and

establishing the second partial quotient as the quotient.

6. The method of claim 5, wherein the step of calculating a second partial quotient and a second partial remainder of the first partial quotient by 2^M−

K−

1 includes the steps of;

(a) establishing the first partial quotient as a current value;

(b) initializing the second partial quotient to zero;

(c) shifting the current value by M−

K bits to produce a first value;

(d) masking to retain the M−

K least significant bits of the current value to produce a second value;

(e) incrementing the second partial quotient by the first value;

(f) adding the first value and the second value to produce the current value; and

(g) establishing the current value as the second partial remainder.

7. The method of claim 6, wherein the step of calculating a second partial quotient and a second partial remainder of the first partial quotient by 2^M−

K−

1 further includes the steps of;

comparing the current value with 2<sup>M−

K</sup>−

1;

if the current value equals 2<sup>M−

K</sup>−

1, then setting the current value to zero and incrementing the second partial quotient by one.

8. The method of claim 6, wherein the step of calculating a second partial quotient and a second partial remainder of the first partial quotient by 2^M−

K−

1 further includes the step of performing steps (c), (d), (e), and (f) until the current value is less than 2<sup>M−

K</sup>.

9. The method of claim 4, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K includes the steps of;

comparing the excess displacement and 2^M−

2^K; and

if the excess displacement is less than 2^M−

2^K, then establishing zero as the quotient and the excess displacement as the remainder.

10. The method of claim 9, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K further includes the steps of;

(a) establishing the excess displacement as a current value;

(b) calculating a first value as a quotient of the current value divided by 2^M;

(c) calculating a second value as a remainder of the current value modulo 2^M;

(d) adding the second value and a product of the first value and 2^K to produce the current value; and

(e) establishing the current value as the remainder.

11. The method of claim 10, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K further includes the steps of;

comparing the current value with 2^M−

2^K; and

if the current value is greater than or equal to 2^M−

2^K, then subtracting 2^M−

2^K from the current value.

12. The method of claim 10, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K further includes the step of performing steps (b), (c), and (d) until the current value is less than 2^M.

13. A computer-readable medium bearing instructions for accessing a slot of an object allocated on a plurality of pages, wherein the slot is logically located at an excess displacement from an end of a page upon which a beginning of the object is allocated and each of the pages has a same page size and includes a page header having a same page header size, said instructions arranged, when executed by one or more processors, to cause the one or more processors to perform the steps of:

calculating a number of page boundaries crossed by the excess displacement to determine which one of the pages the slot is located upon;

calculating a page offset for an address of the slot by adding a remainder of the excess displacement modulo the page size and the number of crossed page boundaries in units of the page header size; and

accessing the slot at the page offset from a beginning of the one of the pages.

14. The computer-readable medium of claim 13, wherein calculating a number of page boundaries crossed by the excess displacement includes the step of shifting the excess displacement.

15. The method of claim 13, wherein said instructions are further arranged to cause the one or more processors to perform the step of masking the excess displacement to calculate the remainder.

16. A computer-readable medium bearing instructions for managing memory in a paged memory system, said instructions arranged, when executed by one or more processors, to cause the one or more processors to perform the steps of:

allocating memory for a plurality of pages, each of the pages comprising 2^M bytes;

padding respective page headers of the pages so that 2^K bytes are allocated for each of the pages; and

accessing a slot of an object allocated on a plurality of the pages, wherein the slot is located at an excess displacement from an end of a page upon which a beginning of the object is allocated, by calculating a quotient and remainder of the excess displacement modulo 2^M−

2^K, said quotient indicating a page containing the slot and said remainder indicating a logical offset on the page containing the slot.

17. The computer-readable medium of claim 16, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K includes the steps of;

shifting the excess displacement by K bits to produce a first partial quotient;

masking the excess displacement to retain the K least significant bits thereof to produce a first partial remainder;

calculating a second partial quotient and a second partial remainder of the first partial quotient by 2<sup>M−

K</sup>−

1;

shifting the second partial remainder by K bits and adding a result thereof and the first partial remainder to produce the remainder; and

establishing the second partial quotient as the quotient.

18. The computer-readable medium of claim 17, wherein the step of calculating a second partial quotient and a second partial remainder of the first partial quotient by 2^M−

K−

1 includes the steps of;

(a) establishing the first partial quotient as a current value;

(b) initializing the second partial quotient to zero;

(c) shifting the current value by M−

K bits to produce a first value;

(d) masking to retain the M−

K least significant bits of the current value to produce a second value;

(e) incrementing the second partial quotient by the first value;

(f) adding the first value and the second value to produce the current value; and

(g) establishing the current value as the second partial remainder.

19. The computer-readable medium of claim 18, wherein the step of calculating a second partial quotient and a second partial remainder of the first partial quotient by 2^M−

K−

1 further includes the steps of;

comparing the current value with 2<sup>M−

K</sup>−

1;

if the current value equals 2<sup>M−

K</sup>−

1, then setting the current value to zero and incrementing the second partial quotient by one.

20. The computer-readable medium of claim 18, wherein the step of calculating a second partial quotient and a second partial remainder of the first partial quotient by 2^M−

K−

1 further includes the step of performing steps (c), (d), (e), and (f) until the current value is less than 2<sup>M−

K</sup>.

21. The computer-readable medium of claim 16, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K includes the steps of;

comparing the excess displacement and 2^M−

2^K; and

if the excess displacement is less than 2^M−

2^K, then establishing zero as the quotient and the excess displacement as the remainder.

22. The computer-readable medium of claim 21, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K further includes the steps of;

(a) establishing the excess displacement as a current value;

(b) calculating a first value as a quotient of the current value divided by 2^M;

(c) calculating a second value as a remainder of the current value modulo 2^M;

(d) adding the second value and a product of the first value and 2^K to produce the current value; and

(e) establishing the current value as the remainder.

23. The computer-readable medium of claim 22, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K further includes the steps of;

comparing the current value with 2^M−

2^K; and

if the current value is greater than or equal to 2^M−

2^K, then subtracting 2^M−

2^K from the current value.

24. The computer-readable medium of claim 22, wherein the step of calculating a quotient and a remainder of the excess displacement modulo 2^M−

2^K further includes the step of performing steps (b), (c), and (d) until the current value is less than 2^M.