Vector table relocation in ARM Architecture - Time & Space Complexity

Time Complexity: Vector table relocation

O(n)

Understanding Time Complexity

When relocating the vector table in ARM architecture, it's important to understand how the time taken grows as the number of vectors increases.

We want to know how the cost of moving or copying the vector table changes with its size.

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly snippet that copies a vector table to a new memory location.

    MOV   R0, #source_address    ; Load source address
    MOV   R1, #dest_address      ; Load destination address
    MOV   R2, #vector_count      ; Number of vectors to copy
copy_loop:
    LDR   R3, [R0], #4          ; Load word from source and increment source pointer
    STR   R3, [R1], #4          ; Store word to destination and increment destination pointer
    SUBS  R2, R2, #1            ; Decrement counter
    BNE   copy_loop             ; Repeat if not zero
    

This code copies each vector entry one by one from the old location to the new location.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying each vector entry (load and store instructions inside the loop)
• How many times: Exactly once per vector entry, repeated for all vectors in the table

How Execution Grows With Input

As the number of vectors increases, the number of copy operations grows proportionally.

Input Size (n)	Approx. Operations
10	About 10 load and 10 store operations
100	About 100 load and 100 store operations
1000	About 1000 load and 1000 store operations

Pattern observation: The total operations increase linearly as the vector count increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to relocate the vector table grows directly in proportion to the number of vectors.

Common Mistake

[X] Wrong: "Relocating the vector table takes the same time no matter how many vectors there are."

[OK] Correct: Each vector entry must be copied individually, so more vectors mean more work and more time.

Interview Connect

Understanding how copying memory scales with size is a useful skill. It shows you can reason about how low-level operations affect performance in real systems.

Self-Check

"What if the vector table was relocated using a hardware DMA controller instead of CPU instructions? How would the time complexity change?"

Practice

1. What is the primary purpose of relocating the vector table in ARM architecture?

easy

A. To increase the processor clock speed

B. To change the base address where interrupt handlers are located

C. To enable floating-point operations

D. To disable interrupts permanently

Solution

1. Step 1: Understand the vector table role

   The vector table contains addresses of interrupt handlers used by the processor.

2. Step 2: Purpose of relocation

   Relocation changes the base address so the processor knows where to find these handlers in memory.

3. Final Answer:

   To change the base address where interrupt handlers are located -> Option B

4. Quick Check:

   Vector table relocation = changing interrupt handler base address [OK]

Hint: Vector table relocation changes interrupt handler address base [OK]

Common Mistakes:

• Confusing relocation with clock speed changes
• Thinking relocation disables interrupts
• Assuming relocation enables floating-point

2. Which ARM register is used to relocate the vector table base address?

easy

A. VTOR (Vector Table Offset Register)

B. SP (Stack Pointer)

C. LR (Link Register)

D. PC (Program Counter)

Solution

1. Step 1: Identify the register for vector table base

   The VTOR register holds the base address of the vector table in ARM processors.

2. Step 2: Confirm other registers' roles

   PC controls instruction flow, LR stores return address, SP manages stack; none relocate vector table.

3. Final Answer:

   VTOR (Vector Table Offset Register) -> Option A

4. Quick Check:

   VTOR = vector table base register [OK]

Hint: VTOR register sets vector table base address [OK]

Common Mistakes:

• Confusing PC with VTOR
• Using LR or SP for vector table relocation
• Not knowing VTOR purpose

3. Given the following code snippet in ARM assembly, what is the effect of the instruction?
MOV R0, #0x20000000
STR R0, [VTOR]

medium

A. Enables interrupts globally

B. Resets the processor

C. Sets the vector table base address to 0x20000000

D. Clears the vector table

Solution

1. Step 1: Analyze MOV instruction

   MOV R0, #0x20000000 loads the address 0x20000000 into register R0.

2. Step 2: Analyze STR instruction

   STR R0, [VTOR] stores the value in R0 into the VTOR register, relocating the vector table base.

3. Final Answer:

   Sets the vector table base address to 0x20000000 -> Option C

4. Quick Check:

   STR to VTOR = relocate vector table base [OK]

Hint: STR to VTOR sets new vector table base address [OK]

Common Mistakes:

• Thinking it resets the processor
• Assuming it enables interrupts
• Believing it clears the vector table

4. A developer tries to relocate the vector table by writing to VTOR but the interrupts still point to the old addresses. What is the most likely cause?

medium

A. The stack pointer is incorrectly set

B. The processor clock is too slow

C. The interrupt handlers are missing

D. VTOR register is write-protected or not enabled for writing

Solution

1. Step 1: Understand VTOR write requirements

   VTOR may be write-protected or require special permissions to update its value.

2. Step 2: Check other options

   Clock speed or stack pointer issues do not affect vector table relocation; missing handlers cause faults but not relocation failure.

3. Final Answer:

   VTOR register is write-protected or not enabled for writing -> Option D

4. Quick Check:

   VTOR write protection blocks relocation [OK]

Hint: Check VTOR write permissions if relocation fails [OK]

Common Mistakes:

• Blaming clock speed for relocation issues
• Confusing stack pointer with vector table base
• Assuming missing handlers prevent relocation

5. In a system with multiple memory regions, how can vector table relocation improve system flexibility?

hard

A. By allowing the vector table to be moved to RAM for dynamic interrupt handler updates

B. By increasing the processor's clock frequency automatically

C. By disabling unused interrupts permanently

D. By encrypting the interrupt handlers for security

Solution

1. Step 1: Understand relocation benefits

   Relocating the vector table to RAM allows changing interrupt handlers at runtime, improving flexibility.

2. Step 2: Evaluate other options

   Clock frequency changes, disabling interrupts, or encryption are unrelated to vector table relocation.

3. Final Answer:

   By allowing the vector table to be moved to RAM for dynamic interrupt handler updates -> Option A

4. Quick Check:

   Relocation enables dynamic interrupt handler updates [OK]

Hint: Relocate vector table to RAM for flexible interrupt updates [OK]

Common Mistakes:

• Thinking relocation changes clock speed
• Assuming relocation disables interrupts
• Believing relocation encrypts handlers