Dynamic Kernel memory tracking using Ftrace

Ftrace:

It is mainly used for kernel function traces and also used for kernel memory tracking.

CONFIGS to be enabled
1. CONFIG_FUNCTION_TRACER=y
2. CONFIG_DYNAMIC_FTRACE=y

It needs /sys/kernel/debug file system to be mounted

It traces memory allocation using events for below api calls

1. kmalloc()
2. kfree()
3. kmem_cache_alloc()
4. kmem_cache_free()

In the events, for each mem alloc call, we get who is the caller, what is requested size, what is allocated size.

Enable ftrace

echo 1 > /sys/kernel/debug/tracing_enabled

Disable

echo 0 > /sys/kernel/debug/tracing_enabled

How to access

/sys/kernel/debug/tracing

Kernel parameter :
trace_event=kmem:kmalloc, kmem:kmem_cache_alloc, kmem:kfree,kmem:kmem_cache_free

Avoiding event buffer over commit:
trace_buf_size=1000000

Enable events:
cd /sys/kernel/debug/tracing
echo "kmem:kmalloc" > set_events
echo "kmem:kmem_cache_alloc >> set_events
echo "kmem:kfree" >> set_events
echo "kmem:kmem_cache_free" >> set_events

Function Filtering:

echo <function name> set_ftrace_filter

Trace only apis of kernel module <MODULE> 

echo ':<MODULE>:tg3' > set_ftrace_filter

SL[OAU]B Allocator in linux Kernel

In linux kernel many kernel structures are created and destroyed in run time span of the kernel.
Without any special handling of  memory allocation/free for these very commonly used structures, over period of time, it will lead to memory fragmentation. Due to memory fragmentation it becomes difficult to get free contiguous memory of large size.

To avoid the above situation, pool of memory can be reserved which is used to allocate memory for these frequenctly used kernel strcutures. Remaining part of main memory remains unfragmented that can be used for catering the memory request of larger sizes..

SL[OAU] Allocator is framework provided by the linux kernel to facilatate the above goal.
It allowes to reserve pool of memory which will be used to cater the memory reqeust for structures(objects) of different sizes.


SLAB is contiguous free memory of 1 or more physical pages. It is used to allocate memory for particuler structure only for which it is created.
Ex. Slab for object 'struct task' is used to allocate memory request only for type 'struct task', not for any other types or size. When same allocated memory is freed, it is returned back to the same slab.
If the page size is 4KB, size of 'struct task' is 1KB, this slab can allocated memory for 4 objects of 'struct task'

SLAB Allocator:
 > It stores the meta data at the beginning of the page. Meta data contains the details of the free objects
 > After the metadat, slab objects are allocated.
 > If the page becomes full, new page is requested from main memory pool and this new page is used for new allocations
 > Any of the page of the slab becomes free, same can be returned to main memory pool for critical situations

Slab can full, partial full or empty.

Slab Allocator use cache colouring to maximise the HW cache performance.Cache Colouring means slabs leave small amount of memory of size which is in multiple of cache line size. After this space objects are allocated.
This essentially means that  different objects from multiple slabs do not map to same cache line
They occupy different cache lines and it will lead to more cache hits.


How Cache Work:

Kmem_cache_alloc - Here, your process keeps some copies of the some pre-defined size objects pre-allocated. Say you have struct that you know you will be requiring very frequently, so instead of allocating it from the main memory (kmalloc) when you need it, you already keep multiple copies of it allocated & when you want it, it returns the address of the block already allocated (saves a lot of time). Similarly, when you free it, you don't give it back, it actually isn't free'd, it goes back to the allocated pool so that if some process again asks for it, you can return this address of the already allocated struct.
Kmalloc - allocates contiguous region from the physical memory. But keep in mind, allocating and free'ing memory is a lot of work.

ARM Basics

ARM Basics

1. RICS architecure, Little endien
2. 32 bit address and 32 bi wide registers
3. OP codes are 32 bit wide in normak mode.
4. Also has 16 bit opcode which is called thumb mode
5. ALU( Arithmatic logic unit) - Takes source operands and one destination
6. One of the source operand passes through barrel shifter. Barrel shilter shifts the value by required number of positions in the same instruction cycle
7. It has 16 register set
8. r13 = Stack pointer
   r14 = link register( Store return address)
   r15 = PC
   CPSR = Current Program Status register
          - It has status flags like N- Negeitive,Z _ Zero, O-Overflow
          - Mode control bits - Tell what is the current mode of operation
          - Interrupt Enable/Disable bit
          - fast interrupt Enable/Disable
          - Thumb bit - Indicate in thumb mode  or not



9. Mode of operation
     - Privilaged Mode - In privilaged mode, mode control  bits of the CPSR can be modified
        1. Abort - If wrong address is accessed
        2. Super User Mode - Kernel is executed in this mode
        3. Undefined mode - When undefined instruction is encountered
        4. Interrupt mode - Used to process the interrupts
        5. Fast interrupt mode - Process fast interrupts
        6. System Mode

     - Non- Privilaged Mode
        1. User Mode - mode control  bits of the CPSR can NOT be modified


10. Register Bank
 Coloured registers are exclusive copy of registers for that mode. When mode change happens, contents of r0-r12 related to old mode should saved before start using them for the new mode

Work Queues

Work  Queue IMplementation

Work Queue Implementation in Linux Kernel



Major parts of work queue implementaiton

1. work queue threads - ALso called as worked threads, execute the handler functions
   - in SMP, for each CPU one worker thread exists.
   - JUst like another kernel thread, executed in process context so can sleep

2. Work_strcut - It represents each individual work that needs executed and completed
      - Handler API -> This hanlder is executed when that corresponding work is taken for execution by the worker thread.
      - Data-> specific to this work
      -


3.  cpu_workqueue_struct - Linux kerenl creates this structure for each worker thread
   
      - It holds linked list of all the works added to its queue.
      - Thread associated with this work queue

Worker kernle thread mainly parses the list of works added to its workqueue and executes their handlers one after the other

API:


To create the structure statically at run-time, use DECLARE_WORK:

DECLARE_WORK(name, void (*func)(void *), void *data);

Alternatively, you can create work at run-time via a pointer:

INIT_WORK(struct work_struct *work, void (*func)(void *), void *data);


Scheduling Work

Now that the work is created, we can schedule it. To queue a given work's handler function with the default events worker threads, simply call

schedule_work(&work);
schedule_delayed_work(&work, delay);



Creating New Work Queues

If the default queue is insufficient for your needs, you can create a new work queue and corresponding worker threads. Because this creates one worker thread per processor, you should create unique work queues only if your code really needs the performance of a unique set of threads.

You create a new work queue and the associated worker threads via a simple function:

struct workqueue_struct *create_workqueue(const char *name);

int queue_work(struct workqueue_struct *wq, struct work_struct *work)

int queue_delayed_work(struct workqueue_struct *wq,
                       struct work_struct *work,
                       unsigned long delay)

Aggragation in 11n

Aggregation in 80211n

-------------------------------

Aggregation is must feature of 80211n - Send mutiple MPDU  in a single packet. MPDUs received in this single bundled packet are acked using single Block Ack.

Aggragation related fields In HT Capabilites IE

Capability Info - 1 bit for max A-MSDU length 0 - 3895 bytes 1 - 7990 bytes
AMPDU Parameters - Max AMPDU Exponent - Max length = 2^(13 + exp) -1 bytes


Paramters that are negotiated for Aggregation in each direction
- TID
- Block Ack Policy
- is AMSDU supported
- Numbers of buffers allocated(10 bits, Max value 1023)
- Starting Sequence Number

Each buffer represents packet of max size MPDU  or less.

Implementation:

1. After STA is associated, when first unicast packet is received from the stack for the peer station
AP will send ADD BA action frame to the peer device. First packet is sent in non-aggragated format.
2. At AP, for each connected client it will create 17 software queues for storing the packets corresponding that particulaer TID.
3.  aggragate_schd() can be implemented which picks the highest priority non-empty TID queue for processing the packets aggregation
4. In aggragated list if there are any  packets which are to be sent at legacy rate or minrate, that packet is seperated out
5. Packets till Block Ack window are considered for aggregation
5. A-Packets are given to firmware for transmission at best possible rate

A-MPDU format

| ---- 4 bytes of Delimiter---|------MPDU_1----|---EOD Padding----|------ same for MPDU_2

Delimiter has MPDU length.

Block Ack:
------------

Linux Kernel

Interrupt Mechanism:

1. Interrupt line is asserted
2. CPU halts the current execution and jumps to the interrupt vector table
3. Interrupt vector table has the branching address of the correspnding INTR line

Before the execution of the ISR(Interrupt Service Routine), linux kernel masks that INR line across all the CPU in SMP environment, so that same interrupt does not occur again before current one is over


API to regrister the ISR to kernel: request_irq(interrupt number, flags, dev)
flags - DISABLE_INTERRUPTS -> Disabled all other interrupts on the CPU
        - SHARED - IF the interrupt number is shared with other devices

dev - This argument is important if the INTR line is shared, it helps to differentiate different handler functions

In the Linux kernel ISR need not reentrant as INTR line masked
Use spin lock to protect any shared resources


How to synchronize data between 'two interrupts' and 'interrupts and process'.
Between Interrupts: Use spin_locks
'interrupts and process'.: spin_lock_irqsave


Device Driver:
Device Driver

Completions

Completions - "wait for completion" barrier APIs - Provide very useful and efficient thread synchronization mechanism where thread has to wait till certain event or task is completed.

Can be used only in process context, as it sleep.  

wait_for_completion() calls spin_lock_irq() & spin_unlock_irq().

struct complete;

init_completion(&completion)

wait_for_completion(&complete) - Wait

complete(&complete);