Two-Level Page Table Mapping

Problem

Translate a virtual address to a physical address through a two-level page table.

va is the virtual address, offset_bits is the page-offset width, and l2_bits is the number of bits indexing the second-level table. l1_table maps a first-level index to an l2 table index (or -1), and l2_tables holds lists mapping a second-level index to a frame number (or -1).

Return frame * page_size + offset, or -1 when any entry is missing or invalid.

Hint

Extract the offset first, then the second-level index, then the first-level index.

Test cases

case 1

in: [9,2,2,[0],[[5,6,7,8]]]

expected: 29

case 2

in: [7,2,2,[0],[[5,6,7,8]]]

expected: 27

case 3

in: [0,2,2,[0],[[5,6,7,8]]]

expected: 20

case 4

in: [20,2,2,[0],[[5,6,7,8]]]

expected: -1

case 5

in: [4,2,2,[-1],[[5,6,7,8]]]

expected: -1

Starter codePython

def translate_address(va, offset_bits, l2_bits, l1_table, l2_tables):
    # Your code here
    pass

5 test cases · run your code against them in the editor