🚀 go-pugleaf

 I'm working on a preparation on the IBM RS/6000 machine architecture,
particularly its storage control system.

I've read a few articles dealing with that subject, but I can't figure
out, how the hashing algorithm works. Let me give you a short explanation
how I see these things upto the point I don't understand.

 The effective address of 32 bit is extended, using the segment ID
addressed by the corresponding segment register, to a 52 bit wide
virtual address. This virtual address is divided into a 40 bit wide part,
(the 40 most significant bits, referred to as virtual pagenumber) and
a 12 bit wide part containing the offset in the page.

 The purpose of an inverted pagetable is to assign the real 
pagenumber to the virtual pagenumber. It contains one entry for
every real page, that means, for instance, entry No. 4711 contains
the virtual pagenumber of the virtual page currently mapped to the
4711st real page.

 During normal storage access you have to assign virtual pagenumbers to
real pagenumbers, i.e. to find out which page table entry contains
the virtual pagenumber you are referring to. This is done by hashing.
A hashvalue is computed from the virtual pagenumber, and in a hashtable
a possible index for the page frame table is looked up. Afterwards
the virtual pagenumber is compared with the virtual pagenumber found
in that entry of the page frame table with this looked up index.
In case of collision you must follow a chained list in the pagetable.

The problem is, that the page frame table entry contains only the
27 high order bits of the virtual page number (which is 40 bit wide).
How can you be sure, that the entry found in the hashtable contains the
right virtual pagenumber ?

 Or, is it perhaps guaranteed by the hashing algorithm, that addresses
with equal lower parts (the 13 low order bits) are always hashed to
different indices in that hashtable, therefore providing different 
anchors for these lists? This could probably be done by
using those bits as some kind of subindex for the hashtable, maybe
the least significant bits of the index. The remaining bits would be
computed by hashing the 27 most significant bits. But that's just
a supposition, I don't know it exact.

Another question is, how big the hashtable is, and if its size is fixed
or not, and from which parameters it depends.

Thanks to everybody who has read upto this point, I'm sure that my
german-style English must be quite difficult to understand.

Thank you very much in advance! Please e-mail reply.

Godmar