operating-systemvirtual-memory

What is the difference between address space size and the "bound" when using base and bounds?


Tool used: relocation.py

From the homework of chapter 15 - Operating Systems three easy pieces (last page):

  1. Run with these flags:-s 1 -n 10 -l 100. What is the maximum value that base can be set to, such that the address space still fits into physical memory in its entirety?

When running ./relocation.py -s 1 -n 10 -l 100 I get this output:

ARG seed 1
ARG address space size 1k
ARG phys mem size 16k

Base-and-Bounds register information:

  Base   : 0x00000899 (decimal 2201)
  Limit  : 100

Virtual Address Trace
  VA  0: 0x00000363 (decimal:  867) --> PA or segmentation violation?
  VA  1: 0x0000030e (decimal:  782) --> PA or segmentation violation?
  VA  2: 0x00000105 (decimal:  261) --> PA or segmentation violation?
  VA  3: 0x000001fb (decimal:  507) --> PA or segmentation violation?
  VA  4: 0x000001cc (decimal:  460) --> PA or segmentation violation?
  VA  5: 0x0000029b (decimal:  667) --> PA or segmentation violation?
  VA  6: 0x00000327 (decimal:  807) --> PA or segmentation violation?
  VA  7: 0x00000060 (decimal:   96) --> PA or segmentation violation?
  VA  8: 0x0000001d (decimal:   29) --> PA or segmentation violation?
  VA  9: 0x00000357 (decimal:  855) --> PA or segmentation violation?

For each virtual address, either write down the physical address it translates to
OR write down that it is an out-of-bounds address (a segmentation violation). For
this problem, you should assume a simple virtual address space of a given size.

From the output, I can see ARG address space size 1k and Limit : 100 which confuses me..

I'm not even sure what the question is asking about.

I can see that the physical memory is 16k, should the maximum base be 16k - 1k so that the process will have a maximum addressable address of 16k? But, in this case, I believe the maximum allowed address would be 16k - 1k + 100 since the limit is 100...

Is there a place in the address space that is not addressable? Meaning that I'm only allowed to address from base up to the address base + bound, no more no less, but the address space is actually from location x up to location y where x <= base && y >= base + limit?


Solution

  • The term address space appears to be overloaded in this problem. I raised an issue in the ostep-homework repo because I was as confused as you are. On the one hand, the (virtual) address space of the underlying process is the range of addresses between 0 and the value of the limit register. On the other hand, the phrase "address space size" is used to denote the range of virtual addresses the script randomly generates. In the example above, the "address space size" of 1K means that relocation.py will generate random virtual addresses in the range 0 - 1024. Some of these addresses will lie in the virtual address space of the process (as determined by the limit register) and some will not.

    To answer the question posed in the OSTEP book, since the value of limit is set to 100, the size of the process's virtual address space is 100. The maximum possible value of base that allows the process's address space to fit in physical memory in its entirety is 16K - 100 = 16284. Indeed, the script accepts a base value of 16284:

    $ ./relocation.py -s 1 -n 10 -l 100 -c -b 16284
    
    ARG seed 1
    ARG address space size 1k
    ARG phys mem size 16k
    
    Base-and-Bounds register information:
    
      Base   : 0x00003f9c (decimal 16284)
      Limit  : 100
    
    Virtual Address Trace
      VA  0: 0x00000089 (decimal:  137) --> SEGMENTATION VIOLATION
      VA  1: 0x00000363 (decimal:  867) --> SEGMENTATION VIOLATION
      VA  2: 0x0000030e (decimal:  782) --> SEGMENTATION VIOLATION
      VA  3: 0x00000105 (decimal:  261) --> SEGMENTATION VIOLATION
      VA  4: 0x000001fb (decimal:  507) --> SEGMENTATION VIOLATION
      VA  5: 0x000001cc (decimal:  460) --> SEGMENTATION VIOLATION
      VA  6: 0x0000029b (decimal:  667) --> SEGMENTATION VIOLATION
      VA  7: 0x00000327 (decimal:  807) --> SEGMENTATION VIOLATION
      VA  8: 0x00000060 (decimal:   96) --> VALID: 0x00003ffc (decimal: 16380)
      VA  9: 0x0000001d (decimal:   29) --> VALID: 0x00003fb9 (decimal: 16313)
    

    but throws an error when it is set to 16284 + 1:

    $ ./relocation.py -s 1 -n 10 -l 100 -c -b 16285
    
    ARG seed 1
    ARG address space size 1k
    ARG phys mem size 16k
    
    Base-and-Bounds register information:
    
      Base   : 0x00003f9d (decimal 16285)
      Limit  : 100
    
    Error: address space does not fit into physical memory with those base/bounds values.
    Base + Limit: 16385   Psize: 16384