Base and Bounds, Segmentation

Base & bounds relocation:

• Two hardware registers: base address for process, bounds register that indicates the last valid address the process may generate.
  
  Each process must be allocated contiguously in real memory.
• On each memory reference, the virtual address is compared to the bounds register, then added to the base register. A bounds violation results in an error trap.
• Each process appears to have a completely private memory of size equal to the bounds register plus 1. Processes are protected from each other. No address relocation is necessary when a process is loaded.
• Typically, the OS runs with relocation turned off, and there are special instructions to branch to and from the OS while at the same time turning relocation on and off. Modification of the base and bounds registers must also be controlled.
• Base & bounds is cheap -- only 2 registers -- and fast -- the add and compare can be done in parallel.
• Explain how swapping can work.
• Examples: CRAY-1.

Problem with base&bound relocation:

• Only one segment. How can two processes share code while keeping private data areas (e.g. shared editor)? Draw a picture to show that it cannot be done safely with a single-segment scheme.

Multiple segments.

• Permit process to be split between several areas of memory. Each area is called a segment and contains a collection of logically-related information, e.g. code or data for a module.
  
  
• Use a separate base and bound for each segment, and also add a protection bit (read/write).
• Each memory reference indicates a segment and offset in one or more of three ways:
  1. Top bits of address select segment, low bits the offset. This is the most common, and the best.
  2. Or, segment is selected implicitly by the operation being performed (e.g. code vs. data, stack vs. data).
  3. Or, segment is selected by fields in the instruction (as in Intel x86 prefixes). (The last two alternatives are kludges used for machines with such small addresses that there is not room for both a segment number and an offset)

Show memory mapping procedure, involving table lookup + add + compare. Example: PDP-10 with high and low segments selected by high-order address bit. Segmentation example: 8-bit segment number, 16-bit offset.

• Segment table (use above picture -- all numbers in hexadecimal):
• Code in segment 0 (addresses are virtual):

   0x00242: mov  0x60100,%r1
   0x00246: st   %r1,0x30107
   0x0024A: b    0x20360
  

• Code in segment 2:

   0x20360: ld   [%r1+2],%r2
   0x20364: ld   [%r2],%r3
     ...
   0x203C0: ret
  

Advantage of segmentation: segments can be swapped and assigned to storage independently.
Problems:

• External fragmentation: segments of many different sizes.
• Segments may be large, have to be allocated contiguously.
• (These problems also apply to base and bound schemes)

Example: in PDP-10's when a segment gets larger, it may have to be shuffled to make room. If things get really bad it may be necessary to compact memory.

Segment table holds the bases and bounds for all the segments of a process.

Using electric-fence to debug malloc allocated memory issues

    While using malloc often we end up with some memory over run or under run issues. The compiler and OS can not detect these flaws most of the times when we build our application with standard libc.  However there is a handy tool available to catch up these flaws in run time.

    "electric-fence" or "efence" is a library and a malloc debugging tool which we can use to debug such buggy applications. It uses the virtual memory hardware of your computer to place an inaccessible memory page immediately after (or before, at the user's option) each memory allocation. When software reads or writes this inaccessible page, the hardware issues a segmentation fault, stopping the program at the offending instruction.


For example:

Check out the below program:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(void)
{
    char *ptr;
    ptr = (char *)malloc(5 * sizeof(char));
    strcpy(ptr, "Welcome to Little Embedded Things");
    printf("%s\n", ptr);
    return 0;
}

    This program over runs the memory allocated by malloc. But if we will build this program with standard libc (gcc prog.c -o prog) then the program runs without any error. It may or may not print the entire string but it runs without any error.

    We can catch up such over run condition by building the program with "efence" library.

For example:
    gcc prog.c -o prog -lefence

    One thing to note down that "efence" can only check either under run or over run one at a time.

    So we need to set the parameter by setting or resetting the variable "EF_PROTECT_BELOW"

For example:
    export EF_PROTECT_BELOW=0 (To check overrun)
    export EF_PROTECT_BELOW=1 (To check under run)

    Once we build the application with "efence" library and run the application, now the hardware issues a segmentation fault, stopping the program at the offending instruction.

You can check "man 3 efence" for more details.

Or you can check out the below links:

https://www.systutorials.com/docs/linux/man/3-efence/
https://linux.die.net/man/3/efence

Common error in makefile

If you're getting an error saying : 

"*** missing separator.  Stop."

then you should check the rules should be started by a tab instead of spaces. Sometimes people configured their editor like Vim to use 4 spaces instead of tabs. So if you are using Vim then you need to check your Vim configuration also.

How ro get rid of the error : undefined reference to `sqrt' in GCC

When we use "math.h" functions in our C program we often get error like "undefined reference to `sqrt' " while compiling the program using GCC.

We can get rid of the error by explicitly linking the math library while building the executable.

To do the same in Unix/Linux just add 'lm' at the the end of the command.
(Note: The '-lm' should be at the end)

For ex : gcc test.c -o test -lm

Some bitwise things

While doing multiplication using left shift operator we need to find out any of the operand must be multiple of 2.

 For ex : If we want to multiply (8 * 9) then we can left shift 9 by 3 as 8 is 2^3. We can consider any operand of the expression in case of multiplication but in case of division the denominator should be a multiple of 2 then only we can do the operation by right shifting the numerator.

For ex : If we want to divide (8 / 9), denominator (9) must be multiple of 2. Here we can not do this operation. But if we want to divide (9 / 8), now denominator (8) is a multiple of 2. Hence we can do the same operation by right shifting the numerator (9) by 3.

(8 * 9) == (9 << 3) and (9 / 8) == (9 >> 3)

You can do modulo operation as mentioned below :

Ex : (15 % 2) == (15 & 1),  (16 % 8) == (16 & 7) 

Note : Bitwise operators only works with integer type variables. (Ex : int, u_int, char, u_char, short)

Play with numbers

Source : EDX : UTAustinX: UT.6.10x Embedded Systems - Shape The World: Microcontroller Input/output



To solve problems using a computer, we need to understand numbers and what they mean. Each digit in a decimal number has a place and a value. The place is a power of 10 and the value is selected from the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. A decimal number is simply a combination of its digits multiplied by powers of 10.
In a similar manner, each digit in a binary number has a place and a value. In binary numbers, the place is a power of 2, and the value is selected from the set {0, 1}. A binary number is simply a combination of its digits multiplied by powers of 2. The powers of 2 are 1, 2, 4, 8, 16, ... For example, the decimal number 13 in binary is 1101₂, meaning 8+4+1.

Binary to Decimal Conversion

To eliminate confusion between decimal numbers and binary numbers, we will put a subscript 2 after the number to mean binary. Because the memory on most computers is 8 bits wide, most of the binary numbers stored in the computer will have 8, 16, or 32 bits. An 8-bit number is called a byte, and a 16-bit number is called a halfword. A 32-bit number is called a word. For example, the 8-bit binary number for decimal integer 106 is
01101010₂ = 0•2⁷ + 1•2⁶ + 1•2⁵ + 0•2⁴ + 1•2³ + 0•2² + 1•2¹ + 0•2⁰ = 64+32+8+2 = 106

Hexadecimal Notation 

Binary is the natural language of computers but a big nuisance for us humans. To simplify working with binary numbers, humans use a related number system called hexadecimal, which uses base 16. This simplification works because 16 itself is a power of 2, i.e., 16=2⁴.

Hexadecimal to Binary Conversion

Just like decimal and binary, each hexadecimal digit has a place and a value. In this case, the place is a power of 16 and the value is a digit selected from the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}. On most computers, it doesn't matter if the hexadecimal digit is written as upper case or lower case {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f}.
A hexadecimal number is often abbreviated as "hex". The basis for a hexadecimal number  is 16⁰, 16¹, 16², 16³,... or 1, 16, 256, 4096,... Hexadecimal is a combination of its digits multiplied by powers of 16. To eliminate confusion between various formats, we will put a 0x or a $ before the number to mean hexadecimal. In C, we will use the 0x prefix to specify hexadecimal.
A nibble is defined as 4 binary bits, or one hexadecimal digit. Each value of the 4-bit nibble is mapped into a unique hex digit, as shown in Table 2.1.


 

Table 2.1. There are 16 hexadecimal digits.

 

As illustrated in Figure 2.1, to convert from binary to hexadecimal we can:

       1) Divide the binary number into right justified nibbles,

       2) Convert each nibble into its corresponding hexadecimal digit.

Figure 2.1. Notice the mapping between 4 binary bits and one hex digit.

As illustrated in Figure 2.2, to convert from hexadecimal to binary we can:

       1) Convert each hexadecimal digit into its corresponding 4-bit binary nibble,

       2) Combine the nibbles into a single binary number.

 

Figure 2.2. Notice that each hex digit maps into 4 binary bits.

Precision and Bytes

Precision is the number of distinct or different values. We express precision in alternatives, bytes, or binary bits. Alternatives are defined as the total number of possibilities. For example, an 8-bit number format can represent 256 different numbers. An 8-bit digital to analog converter (DAC) can generate 256 different analog outputs. An 8-bit analog to digital converter (ADC) can measure 256 different analog inputs.

A byte contains 8 bits as shown in Figure 2.3, where each bit b₇,...,b₀ is binary and has the value 1 or 0. We specify b₇ as the most significant bit or MSB, and b₀ as the least significant bit or LSB.

Figure 2.3. A byte has 8 bits.

If a byte is used to represent an unsigned number, then the value of the number is
N = 128•b₇ + 64•b₆ + 32•b₅ + 16•b₄ + 8•b₃ + 4•b₂ + 2•b₁ + b<sub>0


Numbers are used outside of computers. Sometimes numbers are used in a continuous fashion with an infinite or near infinite number of possibilities. Time, distance, temperature are examples of a continuous and infinite or near infinite parameters. However, sometimes we use a finite number of discrete integers to count or label objects. There are 12 months in a year, we have 10 fingers, there are 52 cards in a deck, and 5000 men in a Roman legion. For each of these discrete examples, we can think of precision as the number of alternatives from which we can select an object. For example, if we wish to select a month, we can choose from 12 possibilities.</sub>

2's Complement

Observation: If the least significant binary bit is zero, then the number is even.

Observation: If the right-most n bits (least sign.) are zero, then the number is divisible by 2ⁿ.

Observation: Consider an 8-bit unsigned number system. If bit 7 is low, then the number is between 0 and 127, and if bit 7 is high then the number is between 128 and 255.

One of the first schemes to represent signed numbers was called one’s complement. It was called one’s complement because to negate a number, we complement (logical not) each bit.

For example, if 25 equals 00011001₂ in binary, then –25 is 11100110₂. An 8-bit one’s complement number can vary from ‑127 to +127. The most significant bit is a sign bit, which is 1 if and only if the number is negative. The difficulty with this format is that there are two zeros +0 is 00000000₂, and –0 is 11111111₂. Another problem is that one’s complement numbers do not have basis elements. These limitations led to the use of two’s complement.

The two’s complement number system is the most common approach used to define signed numbers. It is called two’s complement because to negate a number, we complement each bit (like one’s complement), then add 1.

For example, if 25 equals 00011001₂ in binary, then –25 is 11100111₂. If a byte is used to represent a signed two’s complement number, then the value of the number is

N = -128•b₇ + 64•b₆ + 32•b₅ + 16•b₄ + 8•b₃ + 4•b₂ + 2•b₁ + b₀

The basis elements of an 8-bit signed number are {-128, 64, 32, 16, 8, 4, 2, 1}.

Observation: The most significant bit in a two’s complement signed number will specify the sign.

Observation: To take the negative of a two’s complement signed number we first complement (flip) all the bits, then add 1.

Words and Halfwords

A word on the ARM Cortex M will have 32 bits. Consider an unsigned number with 32 bits, where each bit b₃₁,...,b₀ is binary and has the value 1 or 0. If a 32-bit number is used to represent an unsigned integer, then the value of the number is

N = 2³¹ • b₃₁ + 2³⁰ • b₃₀ + ... + 2•b₁ + b₀ = sum(2ⁱ • b_i) for i=0 to 31

There are 2³² different unsigned 32-bit numbers. The smallest unsigned 32-bit number is 0 and the largest is 2³²-1. This range is 0 to about 4 billion.

A halfword or double byte contains 16 bits, where each bit b₁₅,...,b₀ is binary and has the value 1 or 0, as shown in Figure 2.4.

Figure 2.4. A halfword has 16 bits.

Similar to the unsigned algorithm, we can use the basis to convert a decimal number into signed binary. We will work through the algorithm with the example of converting –100 to 8‑bit binary: We start with the most significant bit (in this case –128) and decide do we need to include it to make –100? Yes (without –128, we would be unable to add the other basis elements together to get any negative result), so we set bit 7 and subtract the basis element from our value. Our new value equals –100 minus –128, which is 28. We go the next largest basis element, 64 and ask, “do we need it?” We do not need 64 to generate our 28, so bit 6 is zero. Next we go the next basis element, 32 and ask, “do we need it?” We do not need 32 to generate our 28, so bit 5 is zero. Now we need the basis element 16, so we set bit 4, and subtract 16 from our number 28 (28-16=12). Continuing along, we need basis elements 8 and 4 but not 2, 1. Putting it together we get 10011100₂ (which means -128+16+8+4).

 

Table 2.2. Example conversion from decimal to signed 8-bit binary.

A second way to convert negative numbers into binary is to first convert them into unsigned binary, then do a two’s complement negate. For example, we earlier found that +100 is 01100100₂. The two’s complement negate is a two-step process. First we do a logical complement (flip all bits) to get 10011011₂. Then add one to the result to get 10011100₂.

A third way to convert negative numbers into binary uses the number wheel. Let n be the number of bits in the binary representation. We specify precision, M=2^n, as the number of distinct values that can be represented. To convert negative numbers into binary is to first add M to the number, then convert the unsigned result to binary using the unsigned method. This works because binary numbers with a finite n are like the minute-hand on a clock. If we add 60 minutes, the minute-hand is in the same position. Similarly if we add M to or subtract M from an n-bit number, we go around the number wheel and arrive at the same place. This is one of the beautiful properties of 2's complement: unsigned and signed addition/subtraction are same operation. In this example we have an 8-bit number so the precision is 256. So, first we add 256 to the number, then convert the unsigned result to binary using the unsigned method. For example, to find –100, we add 256 plus –100 to get 156. Then we convert 156 to binary resulting in 10011100₂. This method works because in 8-bit binary math adding 256 to number does not change the value. E.g., 256-100 has the same 8-bit binary value as –100.

When dealing with numbers on the computer, it will be convenient to memorize some Powers of 2 as shown in Table 2.3.

 

Table 2.3. Some powers of two that will be useful to memorize.

In C we can specify the number of bits used to store data using the data type. The number of bits used will vary from machine to machine, so it is wise to look up these specifications when developing code. The definition for char in C can vary, so with 8-bit variables we suggest using unsigned char or signed char, just be perfectly clear. On this Keil compiler for this Cortex M, we have these data types

Fixed-Point Numbers

We will use fixed-point numbers when we wish to express values in our computer that have noninteger values. A fixed-point number contains two parts. The first part is a variable integer, called I. The variable integer will be stored on the computer. The second part of a fixed-point number is a fixed constant, called the resolution Δ.

The fixed constant will NOT be stored on the computer. The fixed constant is something we keep track of while designing the software operations. The value of the number is the product of the variable integer times the fixed constant. The integer may be signed or unsigned. An unsigned fixed-point number is one that has an unsigned variable integer. A signed fixed-point number is one that has a signed variable integer.

Value = VariableInteger * FixedConstant = I*Δ

The precision of a number system is the total number of distinguishable values that can be represented. The precision of a fixed-point number is determined by the number of bits used to store the variable integer. On most microcontrollers, we can use 8, 16, or 32 bits for the integer. With binary fixed point the fixed constant is a power of 2.

For example, consider a binary fixed-point number system where the resolution is 2^-4. The resolution is not stored on the computer, just the integer I.

For example, consider a decmal fixed-point number system where the resolution is 10^-2. The resolution is not stored on the computer, just the integer I.

 

EX:

If the resolution is 0.01 volts, what does the unsigned decimal number 1234 mean?

Ans : value=integer*resolution, so the value is 12.34 volts

 

If the resolution is 1/8 cm, how do you store 2.25 cm in the computer?

Ans : value = integer*resolution, so the integer is 8*2.25 = 18,

 

If the value is 12.3 ohms, and the integer is 12300, what is the resolution of the fixed-point number system?

Ans : value = integer*resolution, so resolution is 12.3ohms/12300 = 0.001ohms.