Concurrency Control

* In order to create concurrent execution context, and control how they operate within the library and application, three facilities need to be provided:
- Execution context: the state of a concurrent entity.
- Scheduling: to determine which execution context and/or CPU
- Synchronization: to cooperate between concurrent execution contexts

* Thread
- All threads in one process would share all the resources, like virtual address space, file descriptor/pointer, working directory, etc..
- A thread's registers, PC, stack and heap memory are private for the thread unless the thread communicates pointer to that memory to other threads.
- A thread is fully synchronous with itself unless some asynchronous events happen, like ISR.

* Thread Working Modes
- Pipeline
A task is broken into a series of suboperations, each of which is handled in series, but concurrently, by a different thread.
- Client/Server
Multiple clients contact with an independent server for each job anonymously (Multiple to one).
- Manager/worker
A single thread, the manager assigns work to other threads, the workers(One to multiple). Typically, the manager handles all input and parcels out work to the other tasks. At least two forms of the manager/worker model are common: static worker pool and dynamic worker pool.
- Work Crew
Multiple threads work together independently. A special form of manager/worker mode since the manager would join the workers after it creates workers.

Memory Organization

* Memory Hierarchy
- Objective: Reduce the performace gap between memory and CPU
- Principle: The principle of locality (temporal and spatial)
- Why hierarchy? Trade-off between performance and cost
- Result: Program codes and data are spreaded among multiple locations in the memory hierarchy.
- Order in performace: Register, cache, main memory and disk
- Performance metric:
latency (response time, execution time): how fast to get?
throughput (bandwidth): how many/much to get?
for example, register has low latency and high throughput while cache has low latency but low throughput.
Sometimes, power consumption is important.
- Two things are very important in memory hierarchy: Cache and virtual memory

* Cache
- Basic unit
Block/line with multiple bytes. The address of first byte should be aligned to the stride of cache line.
- Where to put cache lines?
Directed mapping (one set associative, n sets), n/m set associative (m sets), and fully associative(one set).
- How to locate cache lines?
Memory address: Tag + Set index + Block offset
- Replacement rule
FIFO, LRU (least Recent Used), and Random
- Write policy
Write back and write through
Write allocate and non-write allocate
write buffer, Non-block cache operations
- Cache size
Cache line component = cache tag + state bits (valid, dirty for WB) + cache data
Cache size in bytes = block size * set associative * sets
- Cache Organization
Two logic dimensions:
Horizontal: Set associative
Vertical: Set
Each set associative could be one cache bank. Note large bulk of data with sequential addresses would be stored vertically not honrizontally.

* Virtual Memory
- Virtual address space
Each process has its own virtual address space, which is determined by the bus width of the system. The process could use this address space fully and its codes and data could be stored anywhere in the space. The organization of text, data, bss regions, stack and heap are in the virtual address space not in physical address space. Therefore the address the program could see is the virtual address but not physical address of main memory.
- Virtual memory
Virtual memory is to expand the concept of main memory to include the disk. The main memory could be considered the cache of the disk.
- Advantage of virtual memory
1) Make multiple processes share main memory
2) No need to worry about the size of main memory
3) Make it possible relocate the codes and data (swapping)
- Virtual address to physical address
Cache and memory are accessed with physical address. So virtual address need to be tranlated to physical address after it leaves CPU. TLB and page table for each process are used for this purpose. Page table would map the virtual address to physical address. Since the size of page table might be large and it is located in main memory, two memory accesses are needed for one address access. According to the principle of locality, TLB (translation buffer) is used to do this job fastly.
- Basic unit
Page or segment; the size of page could be the size of one cache bank (sets * block size)
- Where to put pages?
Fully associative
- How to locate pages?
TLB and Page Table for each process
- Replacement rule
LRU
- Write policy
Write back
- Virtual address format
Virtual address component = virtual address index + page offset
Virtual address index is used to look up the page table.
- TLB
TLB is the cache of process's page table in main memory. It has the same properties as cache. The exception is that cache is controlled completely by hardware, but once page fault happens, the OS needs to be in charge since the cost to access the disk is so high as to switch other process context.

* Main Memory Organization
Main memory could be divided into multiple contiguous address sections, or banks. Each memory bank could be mapped to memory chips. Inside the memory chip, bits could be organized in banks and address interleaves among banks in order to improve the access bandwidth. Two "banks" here are different in terms of address mapping.

L/R Values in C

Every expression in C and C++ is either an l-value or an r-value. An l-value is an expression that designates (refers to) an object. Every l-value is, in turn, either modifiable or non-modifiable. An r-value is any expression that isn't an l-value. Operationally, the difference among these kinds of expressions is this:
The address of each l-value is known at compile time and is where the variable will be kept at runtime, i.e., a modifiable lvalue is addressable (can be the operand of unary &) and assignable (can be the left operand of =). So if the compiler needs to do something with an address (add an offset to it, perhaps), it can do that directly and does not need to plant code to retrieve the address first. In contrast, an r-value is neither addressable nor assignable. For example, the followings are typical r-values and could not be modified.
- function return value
- the result of ? :

A non-modifiable l-value is addressable, but not assignable, like pointer to const value or the array name.

Endianness

* Memory Allocation Rule
In general, the memory is allocated for data starting from low address in the stack(grow from high address to low address) and the heap.

* Endianness
Most modern computer processors agree on bit ordering "inside" individual bytes (this was not always the case). This means that any single-byte value will be read the same on almost any computer one may send it to.

Integers are usually stored as sequences of bytes, so that the encoded value can be obtained by simple concatenation. The two most common of them are:
- increasing numeric significance with increasing memory addresses, known as little-endian, and
- its opposite, called big-endian.
The bit order of register in CPU is fixed for both endians and hardware would take charge of conversion between register and memory.

* Endianness in Networking
Data is transfered generally byte by byte from low address (char *buffer). Networks generally use big-endian order for BYTE transmission (maybe not in memory), and thus it is called network order when sending information over a network in a common format. Some routines are provided generally for these conversions between network and host.

* Bit-Level Endianness
Bit endianness is used to refer to the transmission order of bits over a serial medium. Most often that order is transparently managed by the hardware and is the bit-level analogue of little-endian (low-bit first), although protocols exist which require the opposite ordering (e.g. I2C). In networking, the decision about the order of transmission of bits is made in the very bottom of the data link layer of the OSI model.

* Bit-Shift and Endianness
Bit-shift has nothing with endianness. The results of these operations are defined by std and implemented by compiler.
Reference: Endianness in Wikipedia

Optimization in C

* Better Algorithm or Data Structure

* Mathematics Solution
- Get correct mathematics formula for the problem. For example, calculate N!.

* More Space Less Time
- Using macros for short functions
- Look-up Table

* Use Bit Operations (Be cautious)
- Shift and bit mask for division and module

* Language and compiler features
- Use pointer to operate an array
- No need to define useless return value
- Define a variable in the register instead of stack by using `register'
- Prefer post ++/-- to prefix ++/-- for usage without reference to the result
- Organize the order of cases in switch: The higher occurrence the higher its case number
- In some cases, an array of pointer to functions might be more efficient than switch statement. For example,
int handleMsg1(void);
int handleMsg2(void);
int handleMsg3(void);
int (*MsgFunction[])() = {handleMsg1, handleMsg2，handleMsg3};
status = MsgFunction[ReceiveMessage()]();

* Hardware features
- Copy codes and data from FLASH to RAM for running
- Fully use the UART buffer for data transfer
- Use DMA

* Embed Assembly
- However, it is non-portable

Std Library Functions

* Library Calls And System Calls
- Library calls are parts of the language or application while system calls are part of OS. A system call would be triggered by using trap or interrupt. The C library is the same on every ANSI C implementation. They are calls to routines in a library and linked with user program. They executes in the user address space with lower calling overhead and counts as part of user time. On the other hand, the system calls are different in each OS. They are calls to the kernal for a service. They are entry points to the OS. They executes in the kernal address space with high calling overhead and counts as part of system time.

In practice, many C library functions do their jobs by making system calls.

* getchar
- Its return value is integer instead of char.

* strcpy, strcat, strncpy and strncat
- strcpy and strcat do not check the buffer size and the ending condition is '\0'. So it might cause buffer boundary problem. Try to use strncpy and strncat.

* strlen
- Its return value does not include the character '\0'

* scanf
- It expects a pointer to an integer instead of char to read an integer. The formats of float and double are different. %f for the float and %lf for the double. In printf, %f for both.

* memcpy and memmove
- memcpy could not copy overlapped memory blocks of src and dst and memmove could at a cost of performance.

* setbuf
- When the main function returns, the library would FREE and clean up the memory setbuf used. Therefore, this buffer could not be one in the stack and it is supposed to be memory in the heap or static/global array.

* fread, fseek and fwrite
- fseek needs to be called between the callings of fread and fwrite. One file can not be read and write in sequence without the state change.

* errno
- This global variable would always be the last error number. The general usage should be:
if (error return value)
{
     check errno
}

Thumb of Rules

Function Interface Design
* Write function comment in the head of each function
* Give a good name to each function and avoid using undefined verbs
* Return a status and pass the desired return values by pointers
* The number of input paramters is no more than 7. Othrewise use struct
* Write function prototype and keep data types of input and return parameters match their declarations and no casting
* Const qualified read-only parameter to which input pointers point
* Follow some order of input parameters, like (dst, src, num)
* Check the legitimacy of input parameters and input global variables by using `assert'
* Avoid using input parameters, esp. pointers, as working variables. Use their local copies
* Check the legitimacy of function return value, esp. the return value of std library functions
* Use macros to replace variables of multiple references (i.e., of very long names)

Function Design
* Divide large scale codes to multiple level function calls.
* Design functions with high input fans and low output fans
* Write re-entrant function as much as possible
* Define only one logic task for each function as much as possible
* Keep the length of each function within 200~300 lines
* Separate implemention codes from control codes

Physical Structure of Code
* The basic code unit is a set of files, c/cpp file and its associated h files which might be more than one, like one for the public and another one for the private. The c/cpp file in one unit is supposed to include its h files.
* The h files should include non-std h files as few as possible. These non-std h files should be included in the c/cpp file. The h files could do forward declarations for type declarations within itself in its beginning to avoid including other h files.
* Each h file should be guarded with #ifndef/#define and its unique tag.
* Avoid using `extern' functions directly in c/cpp file but try to include the h files of their declarations.
* Use `static' to restrict the scope of functions and variables. Global variables should be `extern' declared in its h file and defined & initialized in the c/cpp files. Include the h file of global variables first before use them.

Misc
* Not do too much in ONE single statement.
* malloc and free
- Check the return pointer of malloc, reset the memory allocated to zeros with memset.
- Free the memory allocated by malloc at the same code level, assign NULL to the pointer finally.
* fopen and fclose
- Check the return handle of fopen
- Close the file handle in the end
* sizeof and size_t
- size_t == unsigned long int
- sizeof data type instead of variable name
- Prefer (num * sizeof data type) to (sizeof data type * num)
* Condition Check with Boolean, Int, Float and Pointer
- Boolean: if (!Flag)
- Int: if (0 == Flag)
- Float: if (Flag >= -EPSILON && Flag <= EPSILON)
- Pointer: if (NULL == p)
* Infinite Loop - while (1) {...}