Low level software engineer materials for study and questions

Yunseong Kim

Study

MIT 6.006 Introduction to Algorithms, Spring 2020

Leetcode interview crash course: https://leetcode.com/explore/featured/card/leetcodes-interview-crash-course-data-structures-and-algorithms/
C++ Algorithm Courses: https://neetcode.io/practice?tab=coreSkills
코드누리 Modern C++: https://www.ecourse.co.kr/

Question

1. Macro vs. Inline Function

In C, macros and inline functions serve similar purposes—reducing function call overhead—but they operate at very different stages of compilation.

The Pitfall of Macros

Macros use simple text substitution by the preprocessor. This can lead to unexpected side effects due to operator precedence.

#define SQUARE(b) b * b

// Unexpected behavior example:
int result = SQUARE(1 + 2); 
// Expands to: 1 + 2 * 1 + 2
// Evaluates to: 1 + 2 + 2 = 5 (Incorrect! Expected 9)

To fix this, you would need to wrap every argument in parentheses: #define SQUARE(b) ((b) * (b)). However, macros still suffer from double-evaluation issues (e.g., SQUARE(i++)).

The Inline Function Advantage

Inline functions are handled by the compiler. They provide type safety, respect scope, and evaluate arguments exactly once.

inline int square(int a) {
    return a * a;
}

// result = square(1 + 2); 
// Correctly evaluates 3 * 3 = 9.

2. Structure Packing and Alignment (64-bit)

On a 64-bit system, the CPU accesses memory in "words" (8 bytes). For performance, the compiler aligns data on boundaries matching the data size.

Padding and Size

Even if a struct contains small types, the compiler adds "padding" bytes to ensure the next member or the next struct in an array starts at an aligned address.

typedef struct {
    char r, g, b, alpha; // 4 bytes
} Pixel_s; // Total size: 4 bytes (naturally aligned)

typedef union {
     Pixel_s p;
     int not_used;
} Pixel; // 4 bytes

Linux Kernel Context & `size_t`

In the Linux kernel, using size_t (8 bytes on 64-bit) often triggers padding. If you place a char followed by a size_t, the compiler will insert 7 bytes of padding.

typedef struct {
       char r, g, b, alpha;
} __attribute__((aligned(4))) Pixel;

The __attribute__((aligned(4))) forces the starting address of the struct to be a multiple of 4. If you want to eliminate padding entirely to save memory or match hardware registers, you would use __attribute__((packed)).

3. Integer Promotion: Real-world Vulnerabilities

Integer Promotion is the C rule where types smaller than int (like char or short) are converted to int or unsigned int before performing operations.

Why it matters

This often leads to "silent" bugs, especially when mixing signed and unsigned types. A common case in the Linux Kernel involves length checks:

The Scenario: If an unsigned short is compared against a signed integer, or if an expression overflows during promotion, a security check can be bypassed.
CVE Examples: Many "Buffer Overflow" vulnerabilities (documented in Linux-CVE-Announce) stem from the kernel calculating a buffer size using promoted types, resulting in a wrap-around that passes a size < MAX check.

4. Spinlocks, Mutexes, and Semaphores

In a multi-core (SMP) environment, managing concurrency requires different strategies based on the context (Process vs. Interrupt).

Mechanism	Behavior	Multi-core/Interrupt Context
Spinlock	Busy-waits (loops) until the lock is free.	Safe for Interrupts. Does not sleep. Essential for multi-core synchronization where hold times are short.
Mutex	Puts the thread to sleep if the lock is held.	Process context only. You cannot sleep in an Interrupt Handler (ISR).
Semaphore	A counter-based lock that allows $N$ threads.	Similar to Mutex; results in context switching.

Linux Kernel Review

The kernel uses raw_spin_lock to disable preemption on the local core. On multi-core systems, other cores "spin" on the memory address. If an interrupt occurs, the kernel must ensure that the spinlock doesn't lead to a deadlock (e.g., using spin_lock_irqsave).

5. Reversing a String "The Right Way"

A "well-written" string reversal should be in-place, efficient (O(n/2)), and handle the null terminator correctly.

void reverse_string(char* s) {
    if (!s) return;
    
    char *start = s;
    char *end = s + strlen(s) - 1;
    char temp;

    while (start < end) {
        // Swap using a temp variable (or XOR trick, though temp is often faster)
        temp = *start;
        *start++ = *end;
        *end-- = temp;
    }
}

6. ARMv8 Exception Levels (EL) and Protection Rings

The ARMv8-A architecture replaces the traditional x86 "Protection Rings" with Exception Levels (EL).

EL0 (User): Restricted access. Where applications run (Ring 3 equivalent).
EL1 (Kernel): The Linux Kernel operates here. It manages memory (MMU) and hardware (Ring 0 equivalent).
EL2 (Hypervisor): Used for virtualization (KVM).
EL3 (Secure Monitor): Highest privilege; manages the switch between Secure and Non-secure worlds (TrustZone).

Linux Kernel `entry.S`

When a user app (EL0) makes a system call, the CPU transitions to EL1. The code in arch/arm64/kernel/entry.S is the "front door." It saves the user registers, switches the stack pointer, and routes the request to the appropriate kernel function. This transition is the hardware-enforced boundary that protects the system's integrity.

Previous questions

Arm

doubly linked list
spinlock vs mutex vs semaphore
RCU concept
Linux kernel VM, Virtual Memory Basic knoweldge. e.g. pgtable Page Table Concept in Aarch 64
MMU
volatile keyword
C Programming

Mavell

Technically focused on C, Linux system programming, and Linux kernel concepts. C - bitwise operators, DS, arrays, etc coding programs Linux system programming - threads and synchronization concept and coding examples Linux kernel - synchronization and locking, etc

Apple

How to implement a mutex in assembly

Qualcomm

Page Fault exception - what happens
How are signals handled in OS
write a 32byte aligned mem alloc
In a multiprocessor system, how will the L1/L2 caches (non-shared) know about the consistency of the shared data? (I was given a scenario which meant this.)
Write a shortest string copy function.
will you make sure in C to not include a header file which you have already included??
How do you check if 2 buffers overlap?

if(a + sizeof(a)) < b) && ((b+sizeof(b) < a))

Whats is Stack overflow attack??...then he gave me a scenario where there was a open source code at a server and you have your piece of code at that server. You as a client are allowed to invoke a method which takes in a array as a parameter which is not checked for overflow validation. I had to induce a buffer overflow attack and make the method to pass control to my piece of code in the server.
When does the control passes from user mode to kernel mode in a Linux System?

System calls ,H/w Interrupts and last which I did not mention was Exceptions
Well! Exceptions are software interrupts which are synchronous while HW interrupts are asynchronous and caused by hardware devices connected to machine. Both types of interrupts are taken care by their respective interrupt handlers, the top halves. In either case, to service interrupts, execution switches from user space to kernel space.

Write a shortest string copy function.

while(str++ = dst++) {}
I should be like the following. while (*str++ = *dst++) {}
or simplified to: while(*xptr++ = *yptr++);

Amazon

Print largest m number of U8 array- Time complexity =O(n)
using the default malloc/free you have to implement malloc_32/free_32 which supposed to return addresses aligned to 32.
implement heap memory using 1024 bytes + memory beginning address
Difference between threads and processes
implement memcpy, implement memcpy for complex types
Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.
You have array with length 1000001 that contains all the numbers 1..1M and one of the numbers exist twice find this number
Asked my approach to solving bottle necks and performance issue with Ethernet and USB drivers.
Check if a giving number power of 2
Print last n nodes of a linked list you only have pointer to Head

I suggest to create additional pointer which is the tail. Set a gap of the n nodes between the head and tail, move both, and once the tail points to null it’s the end of the list. Then, move only the head and print the node until it reaches the tail
Actually, that could work but it's too expensive. I suggest you to reverse the list which take O(n) time complexity afterward print first m element and reverse the list back which in total cost you O(n) time complexity and O(1) extra space
Use a queue. Traverse the list and add each element to the queue. Always check if the size of the queue is n, if so then remove the first element before adding a new one. When you finish traversing the list your queue will have exactly the last n elements of the list, just print them in order.

Hawei

binary tree, stack, sort algorithms

Oracle

1. How to debug memory leak in kernel.

Intel

What kind of experience have you had in the past working with linux What is an inline function/ volatile/static keywords (basic C functions to gauge your competency)

Google

Describe what happens when you press a key
You have 25 horses, what is the minimum number of races you can find the top 3. In one race you can race 5 horses, and you don't have a timer.

One of the first or second place horses could be 2nd fastest and/or 3rd fastest. I drew a grid to visualize the problem. First, run five races to establish 5 groups of internally ranked horses, and you can of course immediately eliminate 4 & 5 of each race. 1 2 3 x x 1 2 3 x x 1 2 3 x x 1 2 3 x x Then race 1st place horses, eliminate 4 & 5, and those they beat earlier. You can also eliminate the horses #3 beat, and the 3rd place horse from #2's first race. 1 ? ? X X 2 ? X X X 3 X X X X X X X X X X X X X X You know #1 is fastest. Race the remaining horses (2, 3 and ?'s), and the top two are 2nd and 3rd. After reading the above answers, this is the same as B's revised answer, but I found it easier to explain/visualize with the grid.
The answer is definitely 7, here is a fantastic explanation:http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/
It would be 7, mainly because since there only 5 racers each round, then it would be tournament style. As you can tell, tournament style never determines the rankings in the short term. (Imagine if a new tennis player played against Roger Federer and he loses. He's not bad, he's just really unlucky haha) So in order to determine the answer, you would have to use massive logic and reasoning. First step is obvious: you get 5 sets of horses to race through 5 races. So the number is already at 5. We get the top horse in each one and note them. However, one problem is that you have to consider if fastest horses could lie all in the first, second, third, fourth, or fifth group. But we can't determine that yet, so let's race one more time with the winners of each race. Second step: Race with each winner from their groups. That makes 6 total races so far. Ok, now we can get somewhere with this. So now, its a question of which horses we can eliminate to determine the next race. Who can we eliminate though? Well, we can get rid of: - All the horses in the group with the last race that were 4th and 5th place. This makes sense since if the winner of their groups only made 4th and 5th place in the tournament style race, then they are definitely not the fastest horses. 15 horses remaining. - Well, we can also get rid of the last two horses of each group since we are only looking for the top 3. 9 horses remaining. - We also can get rid of the first place winner since we already know he is definitely the best. 8 horses remaining. - Since we already determined who the fastest horse is, now we have to determine who the second and third fastest horse can be. In that case, the second place horse from the last round can get rid of the third horse of that group, since he definitely has no shot of being the first or second fastest horse of this new race. Also, in the third group, we can get rid of the second and third horse in the group due to the same reasoning above. 5 horses remaining. Oh wow! We now have 5 horses left! This means we can just have a clean race and find the second and third fastest horse. So overall, the answer is 7 races!

Etc

Q: What is Accumulator (computing)?
Search online for standard questions asked by Arista. Question 1: Space required for int, float, double etc...use sizeof(...) Question 2: Total space taken up by a struct...Memory alignment causes space to be in multiples of bytes. Question 3: Remove all nodes from a singly linked list that have a certain number. Use GDB for debugging. Question 4: Anagram/Palindrome (don't remember)
Suppose a driver crashed with a segfault. How would you go about debugging it and what tools would you use?
How to compile Linux kernel modules for ARM64?
there are 2 frogs that can jump just if the height of the next index is <= the current height, find the maximum space between them in O(n)
How long is the interrupt latency in Linux?
Describe the difference between a Mutex and a Spinlock and why you would use one instead of the other?
OS related questions, in depth. Interrupts, Context switching C Programs Cache,MMU,TLB's I2C,MDIO,SPI etc
Why not use Spinlocks for everything?
Write an algorithm to sort an array of integers in O(n) time?

As it is array of integers radix sort can be used which has runtime of O(n). On a computer the size of integer variable is fixed, or constant, hence it become O(n). Any comparative sort will take O(n log(n)) but, the radix and buck sort are not comparative. Lets say the integer size is 32bits, then it's run time will be 32 * O(n), which is same as O(n)
There are a number of algorithms to do this one is called bucket sort. The interview didn't indicate the answer to me, but it seemed like he was looking for heap sort (which is O(nlogn) ).
I believe your answer should be that no sort algorithm (on a sequential computer) can sort an array of numbers in less than O(n lg n) time. So his request couldn't be satisfied.

Linux Kernel Meet