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)