DEV Community: dima853

Free Block Search Algorithms in Memory Managers

dima853 — Tue, 18 Aug 2026 17:48:47 +0000

FUNDAMENTAL PROBLEM STATEMENT

Definition: The task of allocating a memory block of size n from a pool of free blocks reduces to finding a block B in the set of free blocks F such that:

size(B) ≥ n (sufficiency)
B minimizes some cost function C(B, n) (optimality)

The set of free blocks is represented as:

F = {B_i = (addr_i, size_i) | B_i is free, 0 ≤ i < m}

where addr_i is the starting address, size_i is the block size.

But, first let's understand what stack and heap are.

1. Conceptual Division: Manager vs. Location

Memory is physically stored in RAM and the processor accesses it by addresses. The terms "stack" and "heap" are not physical areas on chips, but logical models for organizing memory access within the process's virtual address space.

Stack — is a LIFO (Last In, First Out) model, closely tied to the execution flow (thread). Its main task is to store function call context: arguments, local variables, return addresses. Its structure is predictable and managed by the compiler and hardware (stack pointer register — SP/ESP/RSP).
Heap — is a random access model. Its task is to provide memory blocks whose lifetime is not tied to the nesting of function calls. It is managed by the programmer (via malloc/free, new/delete) or the runtime environment (garbage collector).

2. Why does the allocator (memory manager) operate with the concept of "heap"?

Because "heap" is a pool of unstructured, free-for-allocation memory within the process's address space. The allocator is the manager of this pool.

The algorithms we will analyze later (First-Fit, Buddy System) are precisely strategies for managing this pool: finding a free chunk, splitting it, merging freed chunks (coalescence), fighting fragmentation.

The stack is managed according to fundamentally different rules that do not require such a "manager":

Allocation: When entering a function, the compiler calculates the total size of all local variables and simply moves the stack pointer (SP) down by the required number of bytes. This is one assembly instruction (SUB). No free block search.
Deallocation: When exiting the function, the stack pointer is moved back up (ADD or simply loading the saved value from the frame). No merging, no list of free blocks is maintained.
"Fragmentation" of the stack — is simply a "hole" between the SP and the end of the stack, which instantly disappears as soon as the SP moves up when returning from functions. This is not fragmentation in the classical sense, but simply an unused area at the moment.

The stack does not have the problem of finding a free block. It has only one "free" area — the one above the current SP.

3. Important Clarification: "Owns" — in what sense?

Here is a key nuance. When we say "the allocator owns the heap," it does not mean that the OS or the process has "given" it to it.

OS Level: When a process starts, the OS allocates a virtual address space for it. Part of this space is reserved for the stack(s) of each thread. Another large contiguous area (often growing) is allocated for the "process heap" (for example, the area from which sbrk or mmap can allocate memory).
Runtime Level (allocator): The standard library of the language (e.g., glibc's malloc) "digs under" the OS. On the first call to malloc(), it requests a large block of memory from the OS (e.g., 128KB via sbrk or mmap). This block becomes its primary pool, its "heap" in the context of the manager.
Program Level: When you call malloc(100), you are not accessing the OS, but this manager. It looks for free 100 bytes within its pool using those very algorithms (First-Fit, Segregated Lists). If there is no space in its pool, it goes to the OS for another large block to expand its pool.

Thus, the "heap" at the allocator level is its internal memory pool, which it organizes itself. The OS simply provides it with raw pages of virtual memory upon request.

2. CLASSIFICATION OF SEARCH STRATEGIES

2.1 First-Fit (First Suitable)

Essence: Free blocks are organized in a list (most often doubly linked). Metadata (pointers next/prev) is stored in the body of the free block. During the search, the allocator traverses the list from the head until the first block whose size size >= N. This block is removed from the free list. If size is significantly larger than N, splitting is performed: an allocated block of size N is created, and the remainder (a new free block) is inserted back into the list.

Pseudocode

function FIRST_FIT(F, n):
    for each B in F in address order:
        if size(B) ≥ n:
            return B
    return NULL

But, let's recall what a process and a thread are

Process and thread are different abstractions of the OS kernel for code execution.

Process

Technically — it is a resource container. Each process has:

Its own virtual address space (isolated page table).
A table of open files and descriptors (files, sockets, pipes).
Credentials and access rights (UID, GID, capabilities).
Signals and their handlers.
At least one execution thread.

The key point: Processes are isolated. The memory of one process is by default invisible to another (for exchange, IPC mechanisms are needed).

Moreover, if there were no hardware virtual memory, process isolation in its modern understanding would be impossible. That is, process isolation is fundamentally and hardware-guaranteed by virtual memory.

What is virtual memory?

Imagine that physical memory (RAM) is a huge warehouse with millions of identical cells (bytes).

Without virtual memory, all programs receive a single map of this warehouse with real cell numbers. If one program says "put a value in cell №12345", it will put it in the real cell №12345. Another program, reading "cell №12345", will get this value. No isolation.

Virtual memory is a fundamental abstraction that makes each process think that it alone owns all the computer's physical memory, although in reality the memory is shared among many processes and the OS.

Address abstraction:
- The process works with virtual addresses (for example, from 0x00000000 to 0xFFFFFFFF in a 32-bit system).
- The hardware (CPU + MMU — Memory Management Unit) translates these virtual addresses into physical addresses of real RAM modules.
- Each process has its own complete and independent virtual address area. The virtual address 0x1000 in Process A points to a different physical cell than the same address 0x1000 in Process B.
Page Table:
- Address translation occurs through hierarchical tables (Page Tables), unique for each process.
- An entry in the table (Page Table Entry, PTE) contains the physical address of the page and control bits (present in RAM, readable/writable, etc.).
Paging:
_ Memory is divided into fixed blocks — pages (usually 4 KiB). - KiB is a "kibibyte". 1 KiB = 1024 bytes.
This is an important clarification because in the context of memory and OS, powers of two are always used, not powers of ten. - Virtual address space is a linear sequence of virtual pages. Physical memory is a set of physical page frames.
_ The page table specifies the mapping: Virtual Page N → Physical Frame M.
Swapping/Paging Mechanism:
- If physical memory is insufficient, the OS kernel can swap out rarely used pages to disk (to a special area of a partition or a swap file).
- The PTE of such a page is marked "not present in memory". An attempt to access it causes an exception — page fault.
- The page fault handler in the kernel finds the required page on disk, loads it into a free physical frame (possibly swapping out another page), updates the PTE, and resumes the process execution.

Thread

Technically — it is a unit of scheduling on the CPU (CPU scheduling entity). Each thread has:

Its own register context (CPU register values, including stack pointer SP and instruction pointer IP).
Its own call stack (but within the process's address space).
Priority and scheduler state (running, waiting, ready).

The key point: Threads of the same process share the entire address space and resources from the list above. They share the heap, files, global variables.

Analogy

Imagine a computer with virtualization:

Process is a virtual machine (VM). It has its own virtual memory, its own virtual disks, its own network interfaces.
Thread is a virtual CPU core (vCPU) inside this VM. Several vCPUs work inside one VM, sharing all its resources.

2.2 Best-Fit (Best Suitable)

function BEST_FIT(F, n):
    best = NULL
    min_waste = ∞
    for each B in F:
        if size(B) ≥ n:
            waste = size(B) - n
            if waste < min_waste:
                min_waste = waste
                best = B
    return best

Worst-case theorem: Best-Fit minimizes external fragmentation in a static scenario, but:

Search complexity: O(m)
Creates the maximum number of residual blocks of minimal size

2.3 Worst-Fit (Worst Suitable)

function WORST_FIT(F, n):
    worst = NULL
    max_size = 0
    for each B in F:
        if size(B) ≥ n and size(B) > max_size:
            max_size = size(B)
            worst = B
    return worst

Invariant: Aims to leave large free blocks, which theoretically reduces the probability of allocation failure for large requests

Chunks/Arenas

1. Chunk — atomic unit of management

A chunk is not just a "piece of memory". It is a container with metadata, a unit of allocation and deallocation.

Chunk structure (using dlmalloc/ptmalloc as an example):

+----------------+ <-- Pointer returned to user (mem)
| size (with     |
| flags)         |   <-- Header (metadata). Hidden from user.
+----------------+ <-- Pointer managed by allocator (chunk)
| User data      |
| (user memory)  |
| ...            |
+----------------+
| size (with     |
| flags)         |   <-- Footer (only for free chunks)
+----------------+

Footer in the context of a memory manager is an additional metadata block placed at the end of a chunk (memory block).

Key features:

Size is stored in the header together with flags (for example, bit P — previous chunk is free, bit M — allocated via mmap, bit A — belongs to non-main arena).
Alignment: The chunk address is aligned (usually to 8/16 bytes). The user pointer (mem) is offset relative to it.
Boundary tags: Size is stored at the beginning and end of the chunk. Why at the end? So that during deallocation, having a pointer to the previous chunk, its size can be determined and checked if it's free — for coalescence.
In a free chunk, the "user data" field is used to store fd (forward) and bk (backward) pointers in a doubly linked list of free chunks of the corresponding size (bin).

2. Arena — memory domain for parallelism

An arena is an isolated memory pool (a set of chunks) managed by its own set of data structures (binned heaps, lists).

The problem that arenas solve:

In traditional malloc with a single global heap all threads synchronize on one lock. Thread 1 allocates memory → acquires the global mutex → threads 2, 3, ... wait → contention, performance degradation.

Solution: Split the heap into independent arenas. Threads working with different arenas do not interfere with each other.

Arena architecture (as in glibc's ptmalloc):

+---------------------+      +---------------------+
|   Main Arena        |      |   Arena 1           |
|  (Main Arena)       |      |  (Non-Main Arena)   |
|                     |      |                     |
|  +--------------+   |      |  +--------------+   |
|  | Heap         |   |      |  | Heap         |   |
|  | (sbrk/mmap)  |   |      |  |   (only      |   |
|  +--------------+   |      |  |    mmap)     |   |
|  | Binlists     |   |      |  +--------------+   |
|  | (bins)       |   |      |  | Binlists     |   |
|  +--------------+   |      |  | (bins)       |   |
|  | Mutex        |   |      |  +--------------+   |
|  | (lock)       |   |      |  | Mutex        |   |
|  +--------------+   |      |  | (lock)       |   |
+---------------------+      +---------------------+
         ^                              ^
         | (thread 1)                   | (thread 2)

Main Arena: The only one that uses sbrk() to expand the heap. Always exists.
Non-Main Arenas: Created as needed. Each is an independent memory region obtained via mmap() (usually 1MB or more).
Each arena has:
- Its own heap (one or several mmap regions).
- Its own binlists (arrays of free chunk lists sorted by size: fast bins, small bins, large bins, unsorted bin).
- Its own mutex.

Strategy for distributing threads across arenas:

On the first memory allocation in a thread, malloc() tries to find a free (unlocked) arena and bind the thread to it.
If there are no free arenas — a new one is created.
Subsequently, the thread when possible uses "its" arena, minimizing contention.
But if there is no free memory of the required size in "its" arena, the thread can steal memory from another arena (through global synchronization).

This is a trade-off: Complete isolation is impossible, as it would lead to inefficient memory use (one arena is full, another is empty). Therefore, there is periodic rebalancing.

there may be errors in the text*

What is a DAG? Arborescence (Part 2)

dima853 — Tue, 18 Aug 2026 17:48:16 +0000

Part 1: Arborescence (General Definition)

there may be inaccuracies or simplifications in this article

1.1. Intuitive Representation:
Imagine an ordinary undirected tree. Now assign a special role to one of its vertices — the root. Then orient all edges so that they point outward from the root, i.e., in the direction from the root to the leaves. The resulting structure is an arborescence.

Simple Example - Computer Folder Structure ⬇️

Root — C:\ (or / on Linux)
All folders are created via "New Folder"; there are no shortcuts or links.
Each folder has exactly one "parent" (the folder it resides in).
You can only go up to the parent. This is a classic tree (arborescence).

DAG with Potential Arborescence (real system with `mklink` or `.lnk`):

Let's say there is a structure:

C:\Projects\
├── SecretData\
└── CurrentProject\   <-- contains shortcut "Data" → C:\Projects\SecretData

Now this is a DAG, but not an arborescence, because:

SecretData has two "parents":
1. Direct: C:\Projects\
2. Via the shortcut: C:\Projects\CurrentProject\Data\
The condition indegree = 1 for an arborescence is violated.
But there are no cycles — it is a DAG.

"Arborescence(DAG)" in this analogy:

If the administrator strictly prohibits creating shortcuts, links, and mount points, then the file system is both a DAG (no cycles) and an Arborescence (a tree). This is precisely that simple case of a "simple folder tree".

1.2. Formal Definition:

explanation of notations at the end

Let G = (V, E) be a directed graph.

G is called an arborescence (oriented tree) with root r ∈ V if the following conditions are met:

Existence of a root: There exists exactly one vertex r into which no edge enters (i.e., its indegree deg⁻(r) = 0). This vertex is called the root.
Uniqueness of the path from the root: For any other vertex v ∈ V \ {r}, there exists exactly one directed path from r to v.
Absence of cycles: The graph G contains no directed cycles.

1.3. Key Corollaries and Properties:

Important and equivalent characteristics follow from the definition:

Structure of incoming edges: For each vertex v ≠ r, the indegree is 1 (deg⁻(v) = 1). For the root r, it is 0.

The root is also a vertex.

In graph theory, the terms "vertex" and "node" mean the same thing. The root is simply a special, designated vertex.

The indegree of the root is zero.

This means that no edge leads into the root — there is no arrow pointing to it. It is the starting point of all paths in the graph.

All other vertices have an indegree of one.

Every vertex except the root has exactly one incoming edge — one arrow coming into it from another vertex.

This is a direct consequence of the definition of an arborescence.

Precisely because the graph is an arborescence (directed tree), these rules hold: one root with no incoming edges, and every other vertex has exactly one "parent".

Thus, the structure of incoming edges in an arborescence is strictly defined:

0 → for the root, 1 → for all other vertices.

Connectivity (in the directed sense): The graph is weakly connected (if edge directions are ignored, it is connected) and reachable from the root (any vertex v can be reached from r).
Number of edges: If an arborescence has n vertices, then it has exactly n-1 edges.
Orientation from ancestor to descendant: For any edge (u, v), vertex u is an ancestor of vertex v, and v is a descendant of u. The root is an ancestor of all vertices.
Equivalence to a tree: If directed edges are replaced with undirected ones, the result is an ordinary connected acyclic undirected tree.

Part 2: Arborescence in a Directed Acyclic Graph (DAG)

Now consider a situation where an arborescence is a subgraph of a larger Directed Acyclic Graph (DAG).

2.1. Context and Motivation:

A DAG is a directed graph without cycles. Examples: task dependency (makefile), course order in a curriculum, partial ordering of events. In such a graph, a common task is to find a structure linking all or many vertices in the form of a tree.

2.2. Definition of Arborescence in a DAG:

Let G = (V, E) be a DAG. An arborescence in a DAG (often called a directed spanning tree) is a subgraph T = (V, E_T), where E_T ⊆ E, which itself is an arborescence (in the sense of Part 1) with some root r ∈ V.
Spanning is the key word, meaning "covering all vertices".

Key point: All edges of the arborescence T are taken from the original DAG G and retain their orientation. The arborescence "fits" into the topological order of the DAG.

Topological order (or topological sorting) is a way to linearly order the vertices of a directed graph such that for any edge from vertex A to vertex B, vertex A always comes before vertex B in the list.

Main condition: Works only in graphs without cycles (DAG). If it's possible to return from the end to the beginning, the order cannot be constructed.
Essence: If there is a path from A to B, then in the list A will always be to the left of B. This is a "timeline" or task execution queue.
Reachability vs. Order: If A→B, then A comes before B (always). If A comes before B in the list, this does not mean there is a path between them (they might simply be independent parallel tasks). Remember: Topological order is a to-do list where you will never encounter a situation where to perform the current step you need to do something that comes later in the list. (There are no cycles).

2.3. Existence and Construction:

In an arbitrary DAG, an arborescence covering all vertices (i.e., a spanning one) does not always exist.

Necessary conditions for the existence of a spanning arborescence in a DAG:

Existence of a unique root-source: The DAG must have exactly one node with zero indegree (a source). This node becomes a candidate for the root r of the arborescence. If there are several such nodes, constructing a single spanning tree is impossible (several disconnected trees will result).
Reachability from the root: This unique source r must be reachable from all other vertices of the DAG. This condition does not automatically follow from the first — there can be components isolated from r in the DAG, even if r is the only source in the entire graph.

Important note: Even if both conditions are met, not any choice of one incoming edge for each vertex will lead to a connected arborescence. A poor choice may create a forest (several trees) or violate reachability from the root.

Correct construction algorithm (traversal from the root):
If the conditions are met, a spanning arborescence can be guaranteed by traversal (BFS/DFS) starting from the root r and selecting parent edges.

Initialize an empty subgraph T.
Select the unique source r as the root and add it to T.
Start a traversal (e.g., BFS) from r along the edges of the original DAG G.
For each new vertex v reached during traversal via edge (u, v) ∈ E, add this edge (u, v) to T as the sole incoming edge for v in the arborescence.
After traversal is complete, check that T contains all vertices V. If yes, then T is the desired spanning arborescence. If some vertices were not reached, then despite the conditions being met, the choice of edges during traversal might have led to a dead end; in this case, a more complex algorithm for finding a spanning arborescence is required.

Alternative approach (parent selection):
A simpler-to-implement method that guarantees the construction of an arborescence if it exists:

Perform a topological sort of the DAG G.
For each vertex v ≠ r (in topological order), choose as its parent any vertex u for which there exists an edge (u, v) ∈ E. Thanks to the topological order, u will be processed before v, which guarantees the absence of cycles and reachability from the root (provided the root r is the first vertex in the order). All selected edges (u, v) form the desired arborescence T.

By definition, every arborescence is a DAG (directed acyclic graph).

Part 3: Comparison and Summary Table

Property	Arborescence (general)	Arborescence as a subgraph of a DAG	"Arborescence(Dag)" (as a property of a single graph)
Base Graph	It is a tree by itself.	It is a subgraph of a larger DAG.	The single graph considered possesses two properties.
Root	One, with `deg⁻ = 0`.	The root is the unique source in the DAG (if it's a spanning tree).	One, with `deg⁻ = 0`.
Indegree	`deg⁻(v) = 1` for all `v ≠ r`.	`deg⁻_T(v) = 1` in subgraph T, but in the original DAG `deg⁻_G(v)` can be >1.	`deg⁻(v) = 1` for all `v ≠ r`.
Cycles	No directed cycles (follows from the definition).	None (in both T and G).	None (follows from both properties).
Main Idea	Oriented tree-like hierarchy.	Extracting a tree-like hierarchy from a dependency graph.	Emphasizes that the graph is a strict hierarchical tree without cycles.

Example for DAG (constructing an arborescence):

Consider a DAG:

     A (source, deg⁻=0)
    / \
   B   C
    \ / \
     D   E

There is one source A. Let's try to construct an arborescence (spanning tree):

Root: A.
For B: Choose edge A -> B.
For C: Choose edge A -> C.
For D: There are two incoming edges (B->D, C->D). Choose, for example, B->D.
For E: There is an edge C->E. Choose it.

We get the arborescence: A -> B, A -> C, B -> D, C -> E. It covers all vertices.

Conclusion

Arborescence is a fundamental structure, the directed analogue of a tree.
Arborescence in a DAG is a way to select a "main ancestor" for each vertex in a dependency graph, turning it into a hierarchy.
The statement that a graph is both usually emphasizes its strict tree-like nature and acyclicity, which simplifies analysis (e.g., allowing root traversals and DP on DAGs simultaneously).

Notations:

V (from Vertices) — the set of vertices of a graph.

For example: V = {A, B, C, D}

E (from Edges) — the set of edges of a graph.

An edge is a pair of vertices.

For an undirected graph: E = {{A,B}, {B,C}}.

For a directed graph (arcs): E = {(A→B), (B→C), (C→A)} — where the order of vertices matters.

1. `r ∈ V`

r — denotes the root
∈ — the membership symbol ("belongs to")
V — the set of all vertices of the graph
Complete meaning: r is one of the vertices of the graph

2. `deg⁻(r) = 0`

deg⁻(v) — the indegree of a vertex (number of edges entering the vertex)
- Often denoted as deg^{-}(v) or d_in(v).
(r) — for vertex r
= 0 — equals zero
Complete meaning: no edge enters the root (there is no arrow pointing to this vertex)

3. `v ∈ V \ {r}`

v — an arbitrary vertex
∈ — belongs to
V \ {r} — the set of all vertices except the root r
Complete meaning: for each vertex that is not the root

4. Directed path from `r` to `v`

Directed path — a sequence of vertices r → ... → v, where each edge is directed from the previous vertex to the next
Exactly one — there exists only one such path; you cannot reach it in different ways

5. Directed cycle

Directed cycle — a path that starts and ends at the same vertex, following the direction of edges
Example: A → B → C → A
Absence of cycles — no such closed routes exist in the graph

In simple terms:

There is one special root vertex r
Nothing leads into it (like the source of a river)
From the root to any other vertex, you can go in only one way
You cannot go in circles — only from the root downwards

Solution for Problem 207. Course Schedule (Leetcode)

The meaning of the task is extremely simple:

Check if there are cycles in the list of dependencies.

If there are no cycles: You can create a study plan and complete all courses → true.
If there is a cycle: (for example, course 0 requires course 1, and course 1 requires course 0), you fall into a "vicious circle" and cannot even start → false.

Visually:

[[1,0]] — this is a straight line (0→1). All good.

[[1,0],[0,1]] — this is a ring (0↔1). Deadlock.

class Solution {
    public boolean canFinish(int num_courses, int[][] prerequisites) {
        // 1. BUILD THE GRAPH STRUCTURE
        // Create an adjacency list where each index represents a course,
        // and the inner list contains courses that depend on it.
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < num_courses; i++) adj.add(new ArrayList<>());

        // 2. FILL THE ADJACENCY LIST AND COUNTER "INDEGREE"
        // indegree[i] stores the number of prerequisites required before taking course i.
        int[] indegree = new int[num_courses];
        for (int[] pair : prerequisites) {
            int course = pair[0]; // The dependent course
            int pre = pair[1];    // The prerequisite course
            adj.get(pre).add(course); // Directed edge: pre -> course
            indegree[course]++;       // Increment the number of incoming edges for the target
        }

        // 3. INITIALIZE STARTING POINTS
        // The queue 'q' will store courses with NO prerequisites (indegree == 0).
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < num_courses; i++) {
            // If a course has no dependencies, it can be taken immediately.
            if (indegree[i] == 0) q.offer(i);
        }

        // 4. PROCESS THE COURSES (Kahn's Algorithm / BFS)
        int visited_count = 0; // Track how many courses we successfully completed
        while (!q.isEmpty()) {
            int curr = q.poll(); // Take a course from the queue
            visited_count++;     // Mark it as "taken"

            // Look at all courses that depend on the current finished course
            for (int neighbor : adj.get(curr)) {
                indegree[neighbor]--; // "Remove" the dependency (decrement indegree)

                // If all prerequisites are met (indegree is 0),
                // the neighbor course becomes available to take.
                if (indegree[neighbor] == 0) {
                    q.offer(neighbor);
                }
            }
        }

        // 5. FINAL CYCLE CHECK
        // If visited_count equals num_courses, it means we found a valid linear order (no cycles).
        // If not, there is at least one cycle (deadlock) in the graph.
        return visited_count == num_courses;
    }
}

What is a DAG? The Essence in a Nutshell (Part 1)

dima853 — Tue, 18 Aug 2026 17:47:54 +0000

You know what build scripts like Make, Git history, the IOTA blockchain, and AI in TensorFlow have in common? They all operate on the same foundation — the DAG! This isn't just abstract mathematics: from software builds to analyzing cause-and-effect in epidemiology, DAGs are everywhere you need to order dependencies without cycles.

*simplified article

A Directed Acyclic Graph (DAG) is a directed graph without cycles.

Let's break it down:

Graph: A structure consisting of vertices (nodes) and edges (arcs) connecting them.
Directed: Each edge has a direction — it goes from one vertex to another. Denoted by an arrow: A -> B.
Acyclic: The graph has no cycles. You cannot start from some vertex, follow the direction of the arrows, and return to the starting vertex. This is a fundamental property that establishes order and causality.

A simple analogy: Imagine one-way streets in a city where you cannot drive around the block and return to your starting point. Or a chain of tasks where some tasks must be strictly completed before others.

I. In-Depth Definitions and Mathematical Properties

1. Reachability Relation, Transitive Closure, and Transitive Reduction

These are key concepts for understanding the "power" of a DAG.

Reachability Relation: If there is a path from vertex u to vertex v (following the arrows), then we say v is reachable from u. This relation is a partial order on the set of vertices of a DAG.
Transitive Closure: A new graph built on the same vertices, where an edge u -> v is added for every pair of vertices where v is reachable from u. Simply put, it makes implicit connections explicit.
- Example from the article: If the original DAG has edges u -> v and v -> w, then the transitive closure will also include the edge u -> w.
- Why is it needed? To quickly answer the question "is one vertex reachable from another?" — now it can be checked in O(1) (by checking for a direct edge).
Transitive Reduction: The graph with the minimum number of edges that preserves the same reachability relation. This is the "skeleton" of the DAG, where all redundant edges (which duplicate longer paths) are removed.
- Example: In a graph with edges u -> v, v -> w, and u -> w, the edge u -> w is redundant because a path from u to w already exists via v. It can be removed.
- Why is it needed? Simplifies visualization and analysis by removing "noise." A Hasse diagram in order theory is precisely a drawing of the transitive reduction.

Key Takeaway: The same partial order (reachability relation) can be represented by different DAGs (e.g., the full one and its reduction). Transitive closure and transitive reduction are the canonical forms of this representation.

2. Topological Sorting

The cornerstone of DAG theory.

Topological — relating to topology, a branch of mathematics that studies properties of figures and spaces that remain unchanged under continuous deformations (stretching, compressing, bending) without tearing or gluing. It describes qualitative structure, connectedness, and neighborhood of elements, ignoring precise metric characteristics (distances, angles).

Here, the term "topological" is used in a narrower, figurative sense, but there is a connection to the general idea!

Analogy:

In general topology, we study the continuous order of points in space.
In a DAG, we study the partial order of vertices defined by directed edges.

Definition: A topological sort is a linear ordering of vertices such that for every edge u -> v, vertex u comes before v in this order. > A topological sort exists only for a Directed Acyclic Graph (DAG).
Fundamental Theorem: A directed graph is acyclic (a DAG) if and only if it has a topological ordering.
Non-Uniqueness: In general, there can be many topological sorts. It is unique only when the DAG is itself a single directed path (a Hamiltonian path).

Algorithms (two main approaches) ⬇️

Topological sorting algorithms are needed to process any system with dependencies where a correct execution order must be determined.

A) Kahn's Algorithm (1962) — "intuitive," based on in-degrees

Idea: Start with vertices that have no incoming edges (nothing depends on them). Remove them from the graph and repeat the process.

Steps:

For each vertex v, compute the number of incoming edges (in_degree[v]).
Find all vertices with in_degree[v] = 0 and place them in a queue (or list).
While the queue is not empty:
- Remove a vertex u from the front of the queue and append it to the result order result.
- For each neighbor v (where an edge goes from u to v):
  - Decrement in_degree[v] by 1 (as if "removing" the edge u → v).
  - If in_degree[v] becomes 0, add v to the queue.
If the length of result is less than the number of vertices in the graph — a cycle exists in the graph.

Example:
For graph (a,b,c,d,e) with edges (a,b), (a,c), (a,d), (a,e), (b,d), (c,d), (c,e), (d,e):

Step 0: Vertex a has no incoming edges (in_degree=0). Take a.
Step 1: After removing a, vertices b and c get in_degree of 0. We can take b or c. Possible orders: [a, b, c, d, e] or [a, c, b, d, e].

B) Tarjan's Algorithm (1976) — "elegant," based on DFS (Depth-First Search)

Idea: Run a depth-first traversal (DFS) of the graph. Add a vertex to the final list at the moment of finishing its processing (when all its descendants have been visited). The final list then needs to be reversed.

Steps (with coloring for cycle detection):

White — vertex not visited.
Gray — vertex is in the current recursive traversal stack (we started processing it but haven't finished).
Black — vertex fully processed (all its descendants visited).

For each white vertex u, run DFS-visit(u):
Color u gray.
Recursively visit all its neighbors v (via outgoing edges).
- If a gray vertex is encountered — a cycle is found! Sorting is impossible.
After processing all neighbors, color u black and prepend it to the list result.
At the end, reverse the result list (or equivalently, if vertices were prepended, no reversal is needed).

Why does this work? When we color a vertex black, all vertices reachable from it are already processed and black (i.e., they are in the result list). This guarantees that all "successors" of u will already be in the list before it, and after reversal will end up after it.

II. Families of Related Graphs

DAG is a general concept. Its special cases include:

Multitree (Mangrove): A DAG where between any pair of vertices there exists at most one directed path. No "crossroads" where different paths can converge and diverge.
Polytree: A directed tree. Obtained by taking an ordinary undirected tree and assigning directions to edges. A special case of a multitree.
Arborescence: A polytree with a designated root, from which all paths are directed. The classic "tree" in computer science (e.g., a filesystem).

III. Computational Problems and Algorithms (Practical Value)

The power of DAGs lies in the fact that some NP-hard problems for general graphs become efficiently solvable.

Topological Sorting and Cycle Detection: Solvable in O(V+E). For most real-world DAGs, which are sparse (E = O(V)), this effectively means linear time O(V). Used as a first step in many algorithms.
Finding Shortest and Longest Paths:
- In a General Graph: Shortest path (with non-negative weights) — Dijkstra's algorithm (O(E log V)). Longest path — NP-hard problem.
- In a DAG: Both are solvable in O(V+E) using topological sorting! It's enough to process vertices in topological order and update distances to neighbors using the standard relaxation rule.
- Application: The critical path in project management (PERT) is precisely the longest path in a DAG of tasks.
The Closure Problem: Given vertex weights (can be negative). Find a subset of vertices C with maximum total weight, such that no edges leave C (a closure). Solved by reduction to the maximum flow/minimum cut problem.
Construction from Cyclic Graphs:
- Condensation: Any directed graph can be transformed into a DAG by contracting its strongly connected components (SCCs) into a single "supervertex." This is the basis of many algorithms (e.g., Kosaraju's algorithm).
- Orientation as a DAG: For an undirected graph, one can try to assign directions to edges to form a DAG (this is always possible — simply order the vertices). The number of such acyclic orientations equals the value of the graph's chromatic polynomial at point (-1).

IV. DAG Applications (Where is all this used?)

Build Systems and Task Scheduling:
- Make, CMake, Gradle, etc.: Build files describe dependencies between modules. The DAG guarantees that each module is compiled after all its dependencies.
- Task Schedulers (Airflow, Luigi, Prefect): Modern data orchestration tools represent workflows precisely as DAGs. This allows for visualization, parallelization, and task restarting.
Distributed Systems and Cryptocurrencies:
- Version Control Systems (Git): Commit history is a DAG (due to branch merges), not a tree.
- Non-Chain-Based Blockchain: IOTA, Hedera Hashgraph use a DAG structure (Tangle) for transaction confirmation, where each new transaction confirms several previous ones. This is an alternative to a linear blockchain.
Data Processing and Parallel Computing:
- Dataflow Programming (Apache Spark, TensorFlow): Computations are represented as a graph of operations on data. The DAG allows optimization of execution order, identification of independent branches for parallelism, and avoidance of repeated computations (memoization).
Causal Models and Probabilistic Graphs:
- Bayesian Networks: A classic example of a DAG. Vertices are random variables, edges are causal links or direct influences. Acyclicity is critical for correct computation of joint probabilities.
- Structural Causal Models: The foundation of modern causal inference. The DAG encodes assumptions about the absence of hidden common causes for certain variables (the marginality assumption).
Compilers and Static Analysis:
- Control Flow Graph (CFG) is usually cyclic (due to loops in code). But many analyses (e.g., constant propagation) work on its dominance tree, which is a DAG.
- Data Dependency Graph (DDG): Shows which computations depend on which others. A pure DAG, used for vectorization and instruction scheduling.
Data Compression and Efficient Data Structures:
- Compressed Dictionaries (DAWG, CDAWG): Used for efficient storage of string sets (e.g., all words in a dictionary) with shared prefixes and suffixes, saving memory compared to a trie.
- Binary Decision Diagrams (BDD): A canonical representation of Boolean functions as a DAG. The basis for efficient digital circuit and model verification.

Conclusion

A DAG is not just an abstract mathematical structure, but a fundamental language for describing relations of order, dependency, and causality in computer science, engineering, and data science. Its magic lies in the combination of expressiveness (it can model complex dependencies) and computational "friendliness" (the existence of a topological sort opens the door to efficient algorithms).

Understanding DAGs allows one to see commonality in seemingly different things: from building software to drawing conclusions about cause-and-effect in epidemiology. It is a concept well worth mastering.

JVM, Memory Management и Performance

dima853 — Tue, 18 Aug 2026 17:47:31 +0000

JVM, Memory Management, and Performance

Explain the complete lifecycle of an object in the heap (Heap). From creation to garbage collection, including generations (Young Gen, Old Gen), Eden, S0, S1.
What is Garbage Collection (GC)? Explain the main algorithms (Mark-Sweep, Mark-Compact, Copying) and their trade-offs.
Describe the differences between Serial, Parallel, CMS, G1, and ZGC garbage collectors. In which scenarios is each preferable?
What are Stop-The-World (STW) pauses? How do different GCs affect their duration and frequency?
Explain what a "memory leak" is in Java. Provide concrete examples from practice (e.g., in static collections, caches, unclosed resources).
What is Metaspace (Java 8+) and how does it differ from PermGen? What causes OutOfMemoryError: Metaspace?
Explain the String Pool (String Table). How does the intern() method work and when is its use justified?
What is Escape Analysis and how does it help with optimization? (Connection to Stack Allocation and Scalar Replacement).
Describe the memory structure of a Java thread (Stack Memory). What is stored in a method frame (local variables, operand stack, reference to runtime constant pool)?
What is JIT compilation (C1, C2/C1 and C2 (Tiered Compilation))? What is code "profiling" and deoptimization?
Explain the principle of operation of a volatile variable. What is "happens-before" and how does it ensure visibility of changes between threads?
What is false sharing and how to avoid it? (For example, using @Contended).

Answers to Questions:

*this article contains simplifications

1. Lifecycle of an object in the heap: from allocation to reincarnation

Creation (Allocation):

The vast majority of objects are allocated in Eden Space (Young Generation). Allocation happens via the Pointer Bump mechanism (TLAB — Thread-Local Allocation Buffer), which reduces the operation to pointer increment — O(1), requiring almost no synchronization.
Large objects (threshold depends on JVM, often > 512KB-1MB) go directly into Old Generation (Humongous Region in G1), bypassing Young Gen, to avoid expensive copying.

Early life in Young Generation (Short-lived objects):

Eden: When Eden fills up, a Minor GC is initiated.
Minor GC is a fast, partial cleanup of RAM in Java that only affects the area called Young Generation.
Copying Algorithm: Live objects (reachable from GC Roots) are copied from Eden and one of the Survivor Spaces (S0 or S1) to the second Survivor Space.
Survivor Spaces (S0/S1, or From/To): Two identically sized spaces, always one is empty.
(If both Survivors contained data:
There would be nowhere to copy new live objects from Eden)
After each Minor GC, live objects are copied between them, and their age (age) is incremented. This space filters out short-lived objects with minimal overhead.
Promotion: Upon reaching the age threshold (MaxTenuringThreshold, usually 15), an object is considered long-lived and is moved (promoted) to Old Generation. (simplification)

Maturity in Old Generation (Long-lived objects):

Objects survive for a long time.
Filling up Old Gen (or reaching a certain threshold, InitiatingHeapOccupancyPercent) triggers a Major GC (or Full GC, depending on the collector), which works with the entire heap.
Algorithms in Old Gen are more complex: Mark-Sweep-Compact (Serial, Parallel), Concurrent Mark-Sweep (CMS), or mixed ones, as in G1/ZGC/Shenandoah.

Death and recycling (Garbage Collection):

An object becomes garbage when there is not a single reference from a live object (GC Root) via any reachability path.
GC Roots: Static variables, active Stack Frames, JNI References, loaded system classes.
Memory is freed by the collector. In Eden/Survivor — by copying live objects (dead ones are ignored). In Old Gen — by "sweeping" and subsequent "compaction" to combat fragmentation.

2. Garbage Collection: Basic algorithms and trade-offs

Garbage Collection is an automated dynamic memory management system that frees objects unreachable by the executing program.

Algorithms:

Mark-Sweep:
- Phase 1 (Mark): Traversing the reachability graph from GC Roots. Live objects are marked.
- Phase 2 (Sweep): Linear pass through the entire memory. Unmarked (dead) blocks are marked as free.
- Trade-offs: Causes fragmentation. Low overhead, but leads to a "holey" heap, degrading allocation performance and potentially causing OOM due to lack of contiguous space.
Copying:
- Divides memory into two semi-spaces (From and To).
- Live objects are copied from From to To. After copying, the entire From space is considered free.
- Trade-offs: Requires 2x more memory (half is always empty). Does not fragment memory. Extremely efficient if most objects die young. Used only in Young Generation.
Mark-Compact:
- Phase 1 (Mark): Same as Mark-Sweep.
- Phase 2 (Compact): Live objects are moved to the beginning of the region, forming a contiguous block of memory. All references to moved objects are updated.
- Trade-offs: Eliminates fragmentation. The most expensive operation due to the cost of moving and updating references. Used primarily in Old Generation.

Evolutionary conclusion: Young Gen uses Copying (high mortality, efficiency). Old Gen uses hybrids of Mark-Sweep/Compact (low mortality, combating fragmentation). Modern GCs (G1, ZGC) divide the heap into regions, applying algorithms precisely.

3. Garbage Collectors: Strategic Choice

Serial GC (-XX:+UseSerialGC): Single-threaded, for Mark, Sweep, Compact. STW only. Scenario: Single-threaded applications, microcontrollers, environments with minimal resources.
Parallel GC (Throughput Collector) (-XX:+UseParallelGC): Multi-threaded versions of Serial for Young and Old Gen. Maximizes throughput at the cost of more aggressive CPU usage and longer STW pauses. Scenario: Batch processing, computations, where pauses of hundreds of milliseconds to seconds are acceptable.
CMS – Concurrent Mark Sweep (-XX:+UseConcMarkSweepGC): Reduces STW pause duration by having the collector work concurrently with the application.
- Phases: Initial Mark (STW, fast), Concurrent Mark, Concurrent Preclean, Remark (STW), Concurrent Sweep.
- Trade-offs: Does not perform compaction by default → fragmentation, possible Concurrent Mode Failure (forced Full GC). High CPU consumption in background.
G1 – Garbage First (-XX:+UseG1GC, default from Java 9-11): Regional (-XX:G1HeapRegionSize), predictive.
- Divides the heap into ~2000 regions. Collects regions with the most garbage first (Garbage First). Has soft real-time goals (-XX:MaxGCPauseMillis).
- Scenario: Universal balance between throughput and latency. The main choice for most applications with heap >4-6GB.
ZGC (-XX:+UseZGC) and Shenandoah (-XX:+UseShenandoahGC): Low-latency (sub-millisecond goals) collectors.
- Key feature: Almost all phases, including object relocation, are performed concurrently with the application.
- Use colored pointers and read/write barriers (load barriers).
- Scenario: Latency-critical applications: financial transactions, high-load web services, large heaps (terabytes).

Selection strategy: The lower the acceptable latency, the more advanced and concurrent a collector is required. Throughput -> Latency gradient: Parallel -> G1 -> ZGC/Shenandoah.

4. Stop-The-World (STW): Anatomy of a Freeze

STW — a phase when all application threads are suspended to perform a GC operation safe against a changing object graph.
Causes: Root scanning (Root Scanning), the Remark phase in CMS/G1 (accounting for changes during concurrent marking), evacuation and compaction in non-concurrent phases.
GC Impact:
- Serial/Parallel: Dominant, long STW phases. Pauses grow with heap size.
- CMS: Significantly reduces STW (Initial Mark, Remark), but leaves the risk of Concurrent Mode Failure (long STW).
- G1: Predictable, manageable pauses (MaxGCPauseMillis). STW is limited to evacuating a selected set of regions.
- ZGC/Shenandoah: STW is reduced to microsecond root scanning (Root Scanning). Most of the work is concurrent.

5. Memory Leak in Java: Systematic Failure

Memory leak — a situation where objects are no longer used by the application but cannot be collected by GC due to remaining incorrect references stored in live data structures.
This is not a JVM bug, but a logical error in the code.

Canonical examples:

Static collections (Classic):

public class LeakyClass {
    private static final List<byte[]> STATIC_CACHE = new ArrayList<>();
    public void processData(byte[] data) {
        STATIC_CACHE.add(data); // The data object is forever reachable via the static field
    }
}

Uncontrolled caches (Guava Cache, Caffeine without eviction policy):

Cache<Key, Value> cache = Caffeine.newBuilder().build(); // No expireAfterWrite or maximumSize
// Cache grows indefinitely.

Unclosed resources (InputStream, Connection, Session):
Resources often hold references to internal buffers or objects in native memory. Solution: try-with-resources.
Event listeners (Listeners) and inner classes:
Not unsubscribing from a listener stored in a global context keeps a reference to the outer class.
ThreadLocal without cleanup (especially in thread pools):
The value in ThreadLocal lives as long as the thread lives. In web applications, a thread returns to the pool and lives for years.
```
private static final ThreadLocal<HeavyContext> threadLocal = new ThreadLocal<>();
// After use, it is necessary to: threadLocal.remove();
```

Diagnosis: Monitoring Old Gen (constant growth), analyzing heap dump (jmap -dump, MAT, VisualVM), searching for java.lang.Object[] with the largest retained size.

6. Metaspace vs PermGen: Evolution of Metadata

PermGen (up to Java 7) — a fixed heap segment for class metadata, causing frequent OutOfMemoryError and requiring manual size tuning.

Metaspace (since Java 8) — a dynamic area in native memory, automatically managed by the OS, eliminating PermGen problems and allowing efficient loading and unloading of classes.

PermGen (≤ Java 7): Fixed size (-XX:MaxPermSize). Stored class metadata, interned strings, static members. Frequent cause of OutOfMemoryError: PermGen space.
Metaspace (Java 8+): Native memory (not part of Java Heap).
- Managed by the OS, unlimited by default (limited by physical memory/swap).
- Automatic growth and cleanup. Class-loaders and their loaded classes are collected by GC.
- Divided: Klass Metaspace (non-droppable metadata), NoKlass Metaspace for other things.
OutOfMemoryError: Metaspace occurs when:
1. The limit is reached (-XX:MaxMetaspaceSize).
2. Metadata leak (ClassLoader Leak): A common cause — containers (Tomcat, OSGi) where applications are reloaded, but the old ClassLoader is held (e.g., via a thread or static reference), preventing its classes from being unloaded.

7. String Pool (String Table): Deduplication Mechanism

String Pool — a hash table (Hashtable) in the heap (previously in PermGen), storing canonical (interned) instances of String.
Rules:
1. String literals ("text") are added to the Pool during class loading.
2. String.intern(): Allows adding a string created at runtime to the Pool. Returns the canonical representation.
  - If the string is already in the Pool — returns a reference to it.
  - If not — adds the current object to the Pool and returns it.
When to use intern():
- Almost never in typical application code.
- Justified: When processing huge volumes of data with a high degree of string duplication (parsing CSV, tags, enum-like values), when it is required:
- Significant memory savings (one string for many identical values).
- Accelerated comparison via == (replacing .equals()).
- Danger: Uncontrolled use leads to growth of the Pool, which is never cleared (before Java 7). Since Java 7+, interned strings reside in the heap and can be collected by GC if the ClassLoader is unloaded.

8. Escape Analysis: Compiler Magic for Optimization

Escape Analysis (EA) — JIT compiler (C2) analysis determining the visibility scope of a created object.
- NoEscape: The object does not leave the method and/or thread bounds.
- ArgEscape: The object is passed to another method but does not "escape" the thread.
- GlobalEscape: The object is published (saved to a static field, passed to another thread).
Based on EA, JIT applies optimizations:
1. Scalar Replacement: If an object is NoEscape, JIT does not allocate it on the heap. Instead, its fields are transformed into local variables of the method (primitives/references) on the stack. Ideal optimization: zero allocation overhead, zero GC overhead.
```
  // Before optimization
  Point p = new Point(x, y);
  return p.x + p.y;
  // After Scalar Replacement
  int p_x = x, p_y = y;
  return p_x + p_y; // Point object is not created.
```

Stack Allocation: A special case of Scalar Replacement. Theoretical allocation on the stack, but in HotSpot it is implemented precisely as decomposition.
Lock Elision: If the monitor of an object is NoEscape (e.g., a synchronized block on a local object), the lock is removed, as it cannot be contended in another thread.

Activation: Enabled by default (-XX:+DoEscapeAnalysis). Effective for short-lived, local objects (DTOs, iterators, builders).

9. Thread Memory (Stack Memory): Frame Architecture

Each JVM thread has a private stack, created when it starts. The stack consists of stack frames, pushed on method call and popped on its completion (normal or exceptional).

Structure of a method frame:

Local Variable Array (LVA): Array of method variables, indexed from 0.
- this (for non-static methods) is stored in LVA[0].
- Method parameters — in LVA[1], LVA[2], ...
- Local variables — in subsequent slots.
- Each slot is 32 bits (int, float, reference). long/double occupy 2 slots.

Operand Stack (OS): Working area for computations (stack-architecture style). Bytecode instructions (iload, iadd, invokevirtual) operate on this stack (push/pop values).

int a = 5; int b = 3; int c = a + b;
// Bytecode:
iconst_5 // push 5 -> OS
istore_1 // pop OS -> LVA[1] (a)
iconst_3 // push 3 -> OS
istore_2 // pop OS -> LVA[2] (b)
iload_1  // push LVA[1] (a) -> OS
iload_2  // push LVA[2] (b) -> OS
iadd     // pop 2 values, add, push result -> OS
istore_3 // pop OS -> LVA[3] (c)

Reference to Runtime Constant Pool (RCP): Pointer to the class's Constant Pool, needed for resolving symbolic references (method names, classes, constants) at runtime.

Size: Set by the -Xss parameter (default ~1MB). Overflow → StackOverflowError. Dynamic expansion → OutOfMemoryError.

10. JIT Compilation: C1, C2, and Adaptive Optimization

JIT (Just-In-Time) — compilation of "hot" bytecode into native machine code at runtime.
Compilation levels in HotSpot (Tiered Compilation, -XX:+TieredCompilation):
- Interpreter: Executes bytecode. Zero startup overhead, but low speed.
- C1 (Client Compiler): Fast, lightweight compilation. Applies basic optimizations (inlining, simple data flow analysis). Goal — quickly get working native code.
- C2 (Server Compiler): Aggressive, heavy optimizing compiler. Uses complex static analysis (EA, scalar replacement, loop unrolling, macro- and micro-fusion, memory and barrier optimizations). Compiles the hottest methods.
Profiling: JVM collects data about code operation at runtime:
- Method invocation counters.
- Branching: Which if branch executes more often.
- Type Profile: Which concrete classes arrive at a polymorphic call (invokevirtual). This allows devirtualization — replacing a virtual call with a direct one, and then inlining.
Deoptimization: The reverse process. If the optimizer's assumptions are violated (e.g., a new type arrives, not accounted for in the profile), JVM rolls back the compiled native code back to interpreted bytecode.
- Triggers: "Stale" profile (class loading, new polymorphic types), debug points (breakpoint), dependency reset. (simplification)

Cycle: Interpreter → profiling → C1 → profiling → C2 → (deoptimization if necessary). This is Adaptive Optimization.

11. `volatile`: Guarantees of Visibility and Ordering

volatile — a variable modifier providing guarantees of visibility and ordering at the memory level, without atomicity for compound operations (i++).
Semantics:
1. Visibility: A write to a volatile variable by one thread is guaranteed to become visible to all subsequent reads of that variable from other threads.
2. Prevention of Reordering: JVM and processor cannot reorder read/write operations of a volatile variable with other memory operations in a way that violates the happens-before rule.
Happens-Before: The formal Java memory model defining guarantees of visibility of changes between threads.
- Rule for volatile (JLS 17.4.5): A write to a volatile field happens-before every subsequent read of the same field.
- Consequence (Transitivity): If thread A writes to volatile V, and then thread B reads V, then all memory changes made by thread A before writing to V become visible to thread B after reading V.
```
// Thread 1
sharedNonVolatileData = ...; // (1)
volatileFlag = true;          // (2) volatile write
// Thread 2
if (volatileFlag) {           // (3) volatile read (will see true)
    // Here, the value of sharedNonVolatileData from (1) is guaranteed to be visible
    use(sharedNonVolatileData);
}
```
Implementation: At the processor level, this is usually implemented via memory barriers (Memory Barrier or Fence). Writing volatile includes StoreStore + StoreLoad barriers. Reading — LoadLoad + LoadStore.

Usage: For completion flags, publishing results (safe publication), in patterns like double-checked locking (with volatile).

12. False Sharing: The Hidden Performance Enemy

False Sharing — performance degradation in multi-threaded systems, occurring when two independent frequently modified fields (M1 and M2), belonging to different objects (or different array elements), fall into the same cache line (cache line, usually 64 bytes) of the processor.
Mechanism: Processors maintain cache coherency via the MESI protocol. If a thread on core 1 modifies M1, the entire cache line is marked as "modified" (Modified), invalidating the same cache line on core 2, even if it only contains M2. Core 2, when accessing M2, is forced to re-read the line from memory, even though the value M2 itself hasn't changed. This causes cascading invalidation and a "race" for the cache line.
Consequence: Seemingly independent operations start competing synchronously, causing a sharp drop in scalability.

Solution — Alignment (Padding, @Contended):

Classic padding (pre-Java 8): Adding "empty" fields to separate critical fields into different cache lines.

class Counter {
    volatile long count1;
    private long p1, p2, p3, p4, p5, p6, p7; // Padding ~56 bytes
    volatile long count2;
}

@sun.misc.Contended (Java 8+): Annotation instructing JVM to automatically add padding around a field or the entire class.

import jdk.internal.vm.annotation.Contended;
public class StripedCounter {
    @Contended // JVM will add padding (~128 bytes) around each field
    volatile long cell1;
    @Contended
    volatile long cell2;
}

- Requires `-XX:-RestrictContended` for use outside `java.base`.
- Widely used in JDK internals (`LongAdder`, `Thread`, `ForkJoinPool`).

Alternatives: Designing data structures so that threads work with independent memory areas (local variables, ThreadLocal), or using thread-local structures like LongAdder.

Diagnosis: Profilers (VTune, perf) can track events like RESOURCE_STALLS.L1D_MISS_CYCLES or MEM_LOAD_RETIRED.L2_MISS. In Java — empirically, by performance degradation when adding seemingly independent operations.

Once again, and perhaps a bit more clearly ->

PART 1: JVM MEMORY ARCHITECTURE - MACRO LEVEL

Heap: The Dominant Structure in JVM

Physical organization (64-bit HotSpot JVM):

┌─────────────────────────────────────────────────────────────┐
│                     HEAP (Max: 32/64 TB)                    │
├──────────────┬─────────────────┬────────────────────────────┤
│  YOUNG GEN   │                 │        OLD GEN             │
│  (1-3 regions) │                 │       (2/3 of heap)        │
├──────────────┼─────────────────┼────────────────────────────┤
│    EDEN      │   SURVIVOR S0   │                            │
│   (80% YG)   │   SURVIVOR S1   │       Long-lived           │
│              │   (10% YG each) │       objects, survived    │
│              │                 │       many GCs             │
├──────────────┴─────────────────┴────────────────────────────┤
│                     METASPACE                               │
│  (Class metadata, methods, constants, annotations)          │
└─────────────────────────────────────────────────────────────┘

Quantitative parameters (default):

-Xms / -Xmx: Initial/Maximum heap size
-XX:NewRatio=2: OldGen:YoungGen = 2:1
-XX:SurvivorRatio=8: Eden:Survivor = 8:1 (each Survivor)
-XX:MaxTenuringThreshold=15: Maximum age for promotion

Object Lifecycle: Detailed Chronology

Phase 1: Allocation in Eden

public class AllocationPatterns {
    // TLAB (Thread-Local Allocation Buffer) - key optimization
    static void demonstrateTLAB() {
        // When creating an object:
        // 1. Check: is there enough space in the current TLAB?
        // 2. If yes: pointer bump allocation (pointer += size)
        // 3. If no: request a new TLAB from Eden

        // TLAB size is configurable:
        // -XX:TLABSize=512k (size)
        // -XX:+ResizeTLAB (automatic resize)

        for (int i = 0; i < 100_000; i++) {
            // 99% of objects are allocated here
            Object obj = new Object(); // ~12 bytes + overhead
        }
    }
}

Allocation mechanics:

Pointer Bump in TLAB: current_ptr += object_size
Zeroing memory: JVM zeroes memory for safety
Setting Mark Word: mark = hash/age/lock_bits
Setting Klass Pointer: reference to object's Class

Cost: 10-20 CPU cycles for a small object

Phase 2: First Minor GC

Trigger: Eden is 80-90% full (adaptive)

Copying Collector Algorithm:

// HotSpot pseudo-code (Young GC)
void youngGC() {
    // 1. Stop-The-World: suspend all threads
    stop_all_threads();

    // 2. Root scanning (very fast)
    scan_roots();

    // 3. Copy live objects from Eden and From-Survivor to To-Survivor
    for (Object obj : Eden + From_Survivor) {
        if (is_alive(obj)) {
            new_location = copy_to(obj, To_Survivor);
            forward_pointer(obj, new_location); // To update references
        }
    }

    // 4. Swap Survivor spaces
    swap_survivors();

    // 5. Age objects in Survivor
    for (Object obj in To_Survivor) {
        obj.age++;
        if (obj.age >= threshold) {
            promote_to_old_gen(obj);
        }
    }

    // 6. Resume
    resume_all_threads();
}

Critical details:

Card Table: Bitmap for tracking references from OldGen to YoungGen
Remembered Sets: In G1/ZGC for tracking inter-region references

Phase 3: Promotion to Old Generation

Promotion conditions:

Age threshold: age >= MaxTenuringThreshold (usually 15)
Survivor size: If Survivor overflows, oldest objects are promoted
Large objects: > -XX:PretenureSizeThreshold (usually 1MB) go directly to OldGen

// Example: creating long-lived objects
static void createLongLivedObjects() {
    List<byte[]> longLived = new ArrayList<>();

    // These objects will survive several Minor GCs
    for (int i = 0; i < 100; i++) {
        // 100KB - enough for promotion after several GCs
        byte[] data = new byte[102400];
        longLived.add(data);

        // Create garbage to provoke GC
        for (int j = 0; j < 1000; j++) {
            byte[] garbage = new byte[1024]; // Will be collected
        }
    }
}

Garbage Collector Models: Evolution of Algorithms

1. Serial Collector (Mark-Sweep-Compact)

Algorithm:
  1. Mark: Traverse reachability graph from GC Roots
  2. Sweep: Free unmarked areas
  3. Compact: Defragmentation (optional)

Features:
  - Single-threaded (STW for the entire time)
  - Simple, low overhead
  - Ideal for embedded and client applications

2. Parallel / Throughput Collector

Algorithm:
  - Multi-threaded versions of Serial for all phases
  - Goal: maximize throughput (application/GC)

Configuration:
  -XX:+UseParallelGC
  -XX:ParallelGCThreads=(CPU cores)
  -XX:MaxGCPauseMillis=200 (target)
  -XX:GCTimeRatio=99 (99% time for application)

Usage: batch processing, ETL, scientific computing

3. CMS - Concurrent Mark Sweep (deprecated)

// CMS phases:
1. Initial Mark (STW)      // Fast, only direct roots
2. Concurrent Mark         // Concurrent with application
3. Remark (STW)           // Account for changes during concurrent mark
4. Concurrent Sweep       // Cleanup

Problems:
  - Fragmentation (no compaction)
  - Concurrent Mode Failure on rapid filling
  - High CPU usage in concurrent phases

4. G1 - Garbage First (default since Java 9)

Architecture:
  - Heap divided into ~2000 regions (1-32MB)
  - Young generation = set of regions (not fixed)
  - Humongous regions for objects >50% region

Algorithm:
  1. Concurrent marking (like CMS)
  2. Evacuation: copying live objects from "garbage first" regions
  3. Compaction on-the-fly

Configuration:
  -XX:+UseG1GC
  -XX:G1HeapRegionSize={1,2,4,8,16,32}M
  -XX:MaxGCPauseMillis=200
  -XX:InitiatingHeapOccupancyPercent=45

5. ZGC / Shenandoah (Low-Latency)

Innovations:
  - Load barriers instead of write barriers
  - Colored pointers (metadata in pointers)
  - Region-based like G1, but all phases concurrent

ZGC pointer structure:
  ┌─────────┬──────┬──────┬──────────────────────┐
  │ 42 bits │ 4b   │ 4b   │ 14b                  │
  │ Address │ 0000 │ Mark │ Unused               │
  └─────────┴──────┴──────┴──────────────────────┘

Advantages:
  - STW < 1ms regardless of heap size
  - Support for terabyte heaps

PART 2: STOP-THE-WORLD - ARCHITECTURAL VIEW

Anatomy of a JVM Pause

// HotSpot VM safepoint operation
void SafepointSynchronize::begin() {
    // 1. Set safepoint flag
    _state = _synchronizing;

    // 2. Stop all threads at safe points
    for (JavaThread* thread = Threads::first(); thread; thread = thread->next()) {
        thread->safepoint_state()->examine_state_of_thread();

        // Thread must stop in one of:
        // - Between bytecode instructions (in interpreted)
        // - At safepoint polling page (in compiled code)
        // - Blocked in native code
    }

    // 3. All threads stopped
    _state = _synchronized;

    // 4. Perform operation (GC, deopt, etc.)
    do_operation();

    // 5. Resume
    _state = _not_synchronized;
}

Safepoint Polling in Compiled Code

; x86_64 generated JIT code
compiled_method:
    ; Prologue
    push   rbp
    mov    rbp, rsp

    ; Method body
    mov    rax, [rsi+0x10]  ; Load field
    add    rax, 0x1
    mov    [rsi+0x10], rax  ; Store

    ; Safepoint poll (every ~1000 instructions)
    test   byte ptr [rip+safepoint_page], 0xff
    jnz    safepoint_handler  ; Jump if safepoint

    ; Continue
    ret

safepoint_page:  ; Memory page, changed on safepoint
    .byte 0

PART 3: MEMORY LEAK - SYSTEMATIC ANALYSIS

Memory Leak Typology

1. Classic leak via statics

public class ClassicLeak {
    // Global cache without limits
    private static final Map<Key, Value> CACHE = new HashMap<>();

    // Leak: objects never removed
    public void processRequest(Request req) {
        Key key = extractKey(req);
        Value val = computeExpensiveValue(req);
        CACHE.put(key, val);  // Forever in memory
    }

    // Solution 1: WeakHashMap
    private static final Map<Key, Value> WEAK_CACHE =
        Collections.synchronizedMap(new WeakHashMap<>());

    // Solution 2: Guava Cache with policies
    private static final Cache<Key, Value> GUAVA_CACHE =
        CacheBuilder.newBuilder()
            .maximumSize(10000)
            .expireAfterWrite(10, TimeUnit.MINUTES)
            .weakKeys()
            .build();
}

2. ThreadLocal in thread pool

public class ThreadLocalLeak {
    private static final ThreadLocal<ByteBuffer> BUFFER_HOLDER =
        new ThreadLocal<ByteBuffer>() {
            @Override
            protected ByteBuffer initialValue() {
                return ByteBuffer.allocateDirect(1024 * 1024); // 1MB direct buffer
            }
        };

    // In web application (Tomcat):
    // Thread returns to pool after request
    // ThreadLocal is not automatically cleaned!
    // Memory accumulates: pool_size * buffer_size

    public void handleRequest(HttpServletRequest req) {
        ByteBuffer buffer = BUFFER_HOLDER.get();
        // use...
        // FORGET: BUFFER_HOLDER.remove();
    }
}

3. Incorrect event listeners

public class ListenerLeak {
    private final List<EventListener> listeners = new CopyOnWriteArrayList<>();

    public void registerListener(EventListener listener) {
        listeners.add(listener);
    }

    // NO unregisterListener method!
    // Listener holds reference to outer object
    // → leak of entire reference chain
}

4. JNI/Off-Heap leaks

public class NativeMemoryLeak {
    static {
        System.loadLibrary("native");
    }

    private native long allocateNativeMemory(int size);
    private native void freeNativeMemory(long pointer);

    public void leak() {
        long ptr = allocateNativeMemory(1024 * 1024); // 1MB native
        // Forget to call freeNativeMemory(ptr)
        // → leak in native heap (not visible in Java heap dump!)
    }
}

Leak Diagnostics:

# 1. Real-time monitoring
jstat -gc <pid> 1s  # Check OldGen growth after Full GC

# 2. Taking heap dump (production with caution!)
jmap -dump:live,format=b,file=heap.hprof <pid>

# 3. Analysis in Eclipse MAT
#    Key queries:
#    - "Leak Suspects Report"
#    - "Top Consumers"
#    - "Histogram grouped by class"
#    - "Path to GC Roots"

# 4. Command line analysis
jmap -histo:live <pid> | head -20  # Largest classes

# 5. JFR (Java Flight Recorder) for dynamic analysis
jcmd <pid> JFR.start duration=60s filename=leak.jfr

PART 4: METASPACE - CLASS METADATA

Evolution from PermGen to Metaspace

PermGen (≤ Java 7):

┌─────────────────────────────────┐
│           PERMGEN               │
│  (Fixed size, part of Heap)     │
├─────────────────────────────────┤
│ • Class metadata                │
│ • Bytecode                      │
│ • Runtime constant pool         │
│ • String intern table           │
│ • JIT code cache (partially)    │
└─────────────────────────────────┘
Problems: OOM, manual size tuning, inefficient GC

Metaspace (Java 8+):

┌─────────────────────────────────┐
│         NATIVE MEMORY           │
│  (Not Heap, managed by OS)      │
├─────────────────────────────────┤
│     METASPACE                   │
│  ┌─────────────────────────┐    │
│  │  Non-Class Metaspace    │    │
│  │  ┌───────────────────┐  │    │
│  │  │ Chunk (2MB)       │  │    │
│  │  │ • Constant Pool   │  │    │
│  │  │ • Annotations     │  │    │
│  │  │ • Methods         │  │    │
│  │  └───────────────────┘  │    │
│  │  ...                    │    │
│  └─────────────────────────┘    │
│                                 │
│  ┌─────────────────────────┐    │
│  │   Class Metaspace       │    │
│  │  (Compressed Class      │    │
│  │   Space, if enabled)    │    │
│  │  • Klass structures     │    │
│  │  • vtables              │    │
│  │  • itables              │    │
│  └─────────────────────────┘    │
└─────────────────────────────────┘

Metaspace Structure

// Simplified Metaspace structure in HotSpot
class Metaspace {
    // Arena-based allocator
    Metachunk* _chunks;  // List of chunks

    // Statistics
    size_t _used_words;
    size_t _capacity_words;
    size_t _committed_words;
};

// Metadata chunk
class Metachunk {
    // Header
    size_t _word_size;
    Metablock* _blocks;

    // Type: Non-Class (methods, constants) or Class (Klass)
    MetaspaceType _type;
};

ClassLoader Leak - Main Cause of OOM: Metaspace

public class ClassLoaderLeak {
    // Web application, reloaded in Tomcat
    public void leak() throws Exception {
        while (true) {
            // 1. Create isolated ClassLoader
            URLClassLoader loader = new URLClassLoader(
                new URL[]{new URL("file:///app.jar")},
                null  // Parent = null (isolation)
            );

            // 2. Load class
            Class<?> clazz = loader.loadClass("com.example.SomeClass");
            Object instance = clazz.newInstance();

            // 3. Store reference somewhere global
            GlobalCache.store(instance);  // LEAK!

            // 4. ClassLoader cannot be unloaded,
            //    because its classes are reachable through instance
            //    → Metaspace grows with each reload
        }
    }
}

ClassLoader leak diagnostics:

# 1. Check number of ClassLoaders
jcmd <pid> VM.classloader_stats

# 2. Dump classes
jmap -clstats <pid>

# 3. Enable class loading logging
-XX:+TraceClassLoading -XX:+TraceClassUnloading

# 4. Limit Metaspace
-XX:MaxMetaspaceSize=256m
-XX:MetaspaceSize=64m

PART 5: STRING POOL AND INTERNING

String Pool: Hash Table in Heap

// Internal String Pool implementation (StringTable)
class StringTable {
    // Hash table with separate chaining
    private static Entry[] table;

    static class Entry {
        final String str;
        final int hash;
        Entry next;
    }

    // Main intern() method
    static String intern(String str) {
        int hash = hashString(str);
        int index = hash & (table.length - 1);

        for (Entry e = table[index]; e != null; e = e.next) {
            if (e.hash == hash && str.equals(e.str)) {
                return e.str;  // Existing string
            }
        }

        // Adding new string
        Entry newEntry = new Entry(str, hash, table[index]);
        table[index] = newEntry;
        return str;
    }
}

String Pool Evolution

Java 6 and earlier: In PermGen, fixed size, not cleared

-XX:StringTableSize=1009  # Small and fixed

Java 7+: In Heap, dynamic size, cleared by GC

-XX:StringTableSize=60013  # Size can be configured

When to use intern()?

Anti-pattern:

// NEVER DO THIS
public void processLine(String line) {
    String interned = line.intern();  // All strings in pool!
    // Pool fills up, GC won't help
}

Possibly correct usage:

public class TokenProcessor {
    // Limited set of known tokens
    private static final Set<String> KNOWN_TOKENS =
        Set.of("GET", "POST", "PUT", "DELETE", "HEAD").stream()
            .map(String::intern)
            .collect(Collectors.toSet());

    // Frequently used enum-like values
    public void process(HttpMethod method) {
        String m = method.name().intern();  // Only 6 possible values
        // Fast comparison via ==
        if (m == "GET") {  // SAFE: "GET" guaranteed interned
            // ...
        }
    }
}

CSV parser optimization:

public class CSVParser {
    private final Map<String, String> pool = new HashMap<>();

    public String internIfFrequent(String value) {
        // Strategy: intern only frequently repeating values
        if (value.length() > 10) return value;  // Long strings not interned

        String cached = pool.get(value);
        if (cached != null) return cached;

        // Add only if occurs frequently
        if (shouldIntern(value)) {
            String interned = value.intern();
            pool.put(value, interned);
            return interned;
        }
        return value;
    }
}

PART 6: JIT COMPILATION - C1, C2, ADAPTIVE OPTIMIZATIONS

Three-Tier Compilation (Tiered Compilation)

┌─────────────────────────────────────────────────┐
│           INTERPRETER (Level 0)                 │
│  • Zero startup overhead                        │
│  • Slow execution                               │
│  • Profile collection: counters, types, branches│
└─────────────────┬───────────────────────────────┘
                  ↓ (1000+ method calls)
┌─────────────────────────────────────────────────┐
│           C1 (CLIENT) COMPILER                  │
│  • Fast compilation (level 1 optimizations)     │
│  • Inlining small methods                       │
│  • Local optimizations                          │
│  • Continue profile collection                  │
└─────────────────┬───────────────────────────────┘
                  ↓ (10000+ method calls)
┌─────────────────────────────────────────────────┐
│           C2 (SERVER) COMPILER                  │
│  • Aggressive optimizations (level 4)           │
│  • Global data flow analysis                    │
│  • Escape Analysis and Scalar Replacement       │
│  • Devirtualization and inlining                │
│  • Vectorization (Auto-Vectorization)           │
└─────────────────────────────────────────────────┘

Compilation Configuration

# Compilation levels (0-4)
-XX:CompileThreshold=10000        # Threshold for C2
-XX:Tier3InvocationThreshold=2000 # For C1->C2
-XX:Tier4InvocationThreshold=15000

# Cache sizes
-XX:ReservedCodeCacheSize=240m    # Native code cache
-XX:InitialCodeCacheSize=160m

# Compiler control
-XX:+TieredCompilation           # Enable multi-tier (default)
-XX:-TieredCompilation          # Only C2 (slower start)
-XX:CompileCommand=exclude,com/example/expensiveMethod

Profiling and Devirtualization

public class DevirtualizationExample {
    interface Shape {
        double area();
    }

    class Circle implements Shape {
        private final double radius;
        public double area() { return Math.PI * radius * radius; }
    }

    class Square implements Shape {
        private final double side;
        public double area() { return side * side; }
    }

    public double totalArea(List<Shape> shapes) {
        double total = 0;
        for (Shape shape : shapes) {
            total += shape.area();  // Virtual call
        }
        return total;
    }
}

Optimization process:

Interpreter: Collects type profile
- Shape#area(): 95% Circle, 5% Square
C1 compiler: Adds type check

   if (shape.getClass() == Circle.class) {
       total += ((Circle)shape).area();  // Direct call
   } else {
       total += shape.area();  // Virtual call
   }

C2 compiler: If profile is stable
- Creates two specialized loop versions
- For Circle: completely removes checks
- For Square: separate rare path

Escape Analysis and Scalar Replacement

public class Point {
    private final int x, y;
    public Point(int x, int y) { this.x = x; this.y = y; }
    public int getX() { return x; }
    public int getY() { return y; }
}

public int compute() {
    Point p = new Point(10, 20);  // NoEscape: doesn't leave method
    return p.getX() + p.getY();
}

// After Scalar Replacement:
public int compute_optimized() {
    // Point object not created!
    int p_x = 10;  // Field decomposed into local variable
    int p_y = 20;  // Second field decomposed
    return p_x + p_y;
}

Application conditions:

NoEscape: Object not passed outside method
ArgEscape: Passed, but not published
GlobalEscape: Published (not optimized)

Enable/Disable:

-XX:+DoEscapeAnalysis      # Enable (default)
-XX:+EliminateAllocations  # Scalar Replacement (default)
-XX:+PrintEscapeAnalysis   # Logging

PART 7: VOLATILE AND JAVA MEMORY MODEL

Java Memory Model (JMM)

Happens-before rules:

Program order: Actions in a thread happen in program order
Monitor lock: Releasing a monitor happens-before subsequent acquisition
Volatile: Write to volatile happens-before read of same field
Thread start: Thread.start() happens-before any actions in the thread
Thread join: All actions in a thread happen-before Thread.join()
Transitivity: If A happens-before B and B happens-before C, then A happens-before C

Volatile Implementation at Processor Level

public class VolatileExample {
    private volatile boolean flag = false;
    private int data = 0;

    public void writer() {
        data = 42;           // (1) Normal write
        flag = true;         // (2) Volatile write
    }

    public void reader() {
        if (flag) {          // (3) Volatile read
            System.out.println(data); // (4) Will see 42
        }
    }
}

Memory barriers for x86:

; writer()
mov    [data], 42        ; Store data
; StoreStore barrier (x86 doesn't require)
mov    [flag], 1         ; Store flag (volatile)
sfence                   ; StoreLoad barrier (x86 requires)

; reader()
lfence                   ; LoadLoad barrier (x86 requires)
mov    rax, [flag]       ; Load flag (volatile)
test   rax, rax
jz     .done
; LoadStore barrier (x86 doesn't require)
mov    rbx, [data]       ; Load data

False Sharing and @Contended

False sharing problem:

public class FalseSharing {
    // Two fields in one cache line (64 bytes)
    volatile long value1;  // [0-7]
    // ... 56 bytes ...
    volatile long value2;  // [56-63]

    // Thread 1: constantly writes to value1
    // Thread 2: constantly reads value2
    // RESULT: cache line constantly invalidated
    // → performance drops significantly
}

Solution with @Contended:

public class PaddedData {
    // JVM will add 128 bytes padding on each side
    @Contended
    volatile long value1;

    @Contended
    volatile long value2;

    // Memory layout:
    // [value1][128 bytes padding][... other fields ...][128 bytes padding][value2]
}

Manual solution (pre-Java 8):

public class ManualPadding {
    volatile long value1;
    // Explicit padding
    long p1, p2, p3, p4, p5, p6, p7; // 56 bytes

    volatile long value2;
    long p8, p9, p10, p11, p12, p13, p14; // Another 56 bytes
}

False sharing diagnostics:

# Linux: perf for cache miss monitoring
perf stat -e cache-misses,cache-references java -jar app.jar

# JVM flags for @Contended
-XX:-RestrictContended        # Allow use outside java.base
-XX:ContendedPaddingWidth=128 # Padding size (default 128)

PART 8: PROFILING AND OPTIMIZATION IN PRACTICE

Scenario: High-Load Service

Initial state:

100k RPS, 95th percentile 200ms, heap 8GB
Frequent Full GC pauses 2-3 seconds

Step 1: Data collection:

# 1. JFR for pause analysis
jcmd <pid> JFR.start duration=60s filename=gc.jfr

# 2. Detailed GC logs
-XX:+PrintGCDetails -XX:+PrintGCDateStamps -Xloggc:gc.log

# 3. Heap dump just before Full GC
-XX:+HeapDumpBeforeFullGC -XX:HeapDumpPath=/path/to/dumps

Step 2: Analysis:

// Typical problems:
// 1. Too large Young/Old ratio
// 2. Frequent promotions due to large Survivor
// 3. Memory leak in caches
// 4. Too aggressive allocation rate

Step 3: Optimization:

# Switch to G1 GC
-XX:+UseG1GC
-XX:MaxGCPauseMillis=100
-XX:InitiatingHeapOccupancyPercent=35  # Start concurrent cycle earlier

# Tune Young Gen
-XX:NewRatio=1                          # More Young for short-lived
-XX:SurvivorRatio=6                     # More Eden
-XX:MaxTenuringThreshold=5              # Faster promotion for medium-lived

# Monitoring
-XX:+PrintAdaptiveSizePolicy            # How JVM tunes sizes
-XX:+PrintTenuringDistribution          # Age distribution

Anti-patterns and Their Fixes

Anti-pattern 1: Manual System.gc()

// BAD
public void processBatch() {
    // ...
    System.gc();  // Full GC pause at unpredictable moment
    // ...
}

// Solution: rely on JVM or use
// -XX:+ExplicitGCInvokesConcurrent for G1
// -XX:+DisableExplicitGC in production

Anti-pattern 2: Large arrays in Young Gen

// BAD: 2MB array in Eden
byte[] buffer = new byte[2 * 1024 * 1024];

// Solution: direct allocator or tuning
-XX:PretenureSizeThreshold=3M  # Objects >3MB directly to OldGen

Anti-pattern 3: String concat in loop

// BAD: O(n²) memory
String result = "";
for (String item : items) {
    result += item;  // New StringBuilder each time
}

// Solution:
StringBuilder sb = new StringBuilder(estimatedSize);
for (String item : items) {
    sb.append(item);
}
String result = sb.toString();

PART 9: SPECIFIC CONFIGURATIONS FOR DIFFERENT SCENARIOS

Microservice (REST API, 4GB heap)

# G1 with aggressive latency goals
-XX:+UseG1GC
-XX:MaxGCPauseMillis=50
-XX:G1HeapRegionSize=4M
-XX:InitiatingHeapOccupancyPercent=30
-XX:ConcGCThreads=2
-XX:ParallelGCThreads=4

# Metaspace limits
-XX:MaxMetaspaceSize=128M
-XX:MetaspaceSize=64M

# JIT settings
-XX:ReservedCodeCacheSize=128M
-XX:InitialCodeCacheSize=64M

Batch Data Processing (32GB heap)

# Throughput oriented
-XX:+UseParallelGC
-XX:+UseParallelOldGC
-XX:ParallelGCThreads=8
-XX:GCTimeRatio=99
-XX:MaxGCPauseMillis=500

# Large objects
-XX:PretenureSizeThreshold=10M
-XX:SurvivorRatio=10

# Monitoring
-XX:+PrintGCDetails
-XX:+PrintGCApplicationStoppedTime

Low-Latency System (Financial Transactions)

# ZGC for sub-millisecond pauses
-XX:+UseZGC
-XX:MaxGCPauseMillis=1
-XX:ConcGCThreads=4
-Xmx16g
-Xms16g  # Fixed heap

# Disable bias locking for stability
-XX:-UseBiasedLocking

# Aggressive JIT compilation
-XX:-TieredCompilation  # Only C2
-XX:CompileThreshold=1000

PART 10: MONITORING AND DIAGNOSTICS IN REAL TIME

Utilities and Their Purpose

jcmd - universal command:

# Full list of available commands
jcmd <pid> help

# Heap dump
jcmd <pid> GC.heap_dump filename=heap.hprof

# Class status
jcmd <pid> GC.class_histogram

# JFR management
jcmd <pid> JFR.start duration=60s filename=recording.jfr

jstat - GC statistics:

# Every second, 10 times
jstat -gc <pid> 1s 10

# Key metrics:
# S0C/S1C: Survivor capacity
# S0U/S1U: Survivor used
# EC/EU: Eden capacity/used
# OC/OU: Old capacity/used
# YGC/YGCT: Young GC count/time
# FGC/FGCT: Full GC count/time

async-profiler - low-level profiler:

# CPU profiling
./profiler.sh -d 30 -f cpu.svg <pid>

# Allocation profiling
./profiler.sh -d 30 -e alloc -f alloc.svg <pid>

# Contended lock profiling
./profiler.sh -d 30 -e lock -f lock.svg <pid>

Configuring GC Logs for Analysis

# Detailed logs with timestamps
-Xlog:gc*,gc+age=trace,gc+heap=debug:file=gc.log:uptime,level,tags

# For G1 specifically
-Xlog:gc+g1*=debug,gc+phases=debug:file=g1.log

# Parsing logs with utilities
# 1. GCViewer: visualization
# 2. gceasy.io: online analysis
# 3. jClarity Censum: commercial tool

11 Fundamental Programming Concepts

dima853 — Tue, 18 Aug 2026 17:46:59 +0000

If you’re new to programming, the sheer number of new terms can feel overwhelming. But here’s the secret: every complex program is built from just a handful of simple ideas. Once you understand these 11 concepts, you’ll have a solid foundation for any language you decide to learn.

I’ve put together a set of interactive puzzles that let you play with each idea directly in the browser – no setup required. After reading each explanation, click the link to solve a quick puzzle and lock in your understanding.

Note: This post is a beginner-friendly introduction to the core concepts of programming. It's intentionally simplified to help you build a mental model without getting lost in details. In reality, each of these topics has depth and nuance that entire books are dedicated to. This is just the first step — a foundation that will make it easier to understand the more complex ideas later.

1. What is a Variable?

Think of a variable as a labeled box. You write a name on the box (like shoes or favoriteNumber) and then you can put something inside it, look inside, or change the contents – all without changing the label.

You declare the box by giving it a name.
You assign a value by putting something in it (like x = 10).
You can change the value later (like x = 20). The old value is gone, but the name stays the same.

That’s why it’s called a "variable" – its content can vary.

Solve the puzzle: What is a variable?

2. Numbers vs Strings: Why `1 + 1 = 2` but `"1" + "1" = "11"`

Computers treat different kinds of data differently. The two most basic kinds are numbers and strings (text).

Numbers are for math. If you write 5 without quotes, the computer knows it can add, subtract, multiply, and divide it. So 1 + 1 equals 2.
Strings are for text. They are always wrapped in quotes, like "hello" or "5". Even if there are digits inside the quotes, the computer sees them as characters, not numbers. The + sign with strings means "glue together". So "1" + "1" becomes "11".

If you put a number in quotes, you turn it into a string and it loses its mathematical powers.

Solve the puzzle: Numbers vs Strings

3. Conditionals: if/else – Making Decisions

Programs often need to choose between two paths. That's exactly what if and else do.

if checks a condition that is either true or false (like age >= 18).
If the condition is true, the computer runs the block of code inside the if.
If the condition is false, the computer skips the if block and runs the else block instead (if there is one).

It works just like a real‑life decision: "If it's raining, take an umbrella. Otherwise, leave it at home."

Solve the puzzle: if/else decisions

4. Loops: for and while – Repeating Actions

Doing the same thing over and over is what computers are best at. Loops let you repeat a block of code without writing it again.
Computers repeat actions perfectly because their processors consist of electronic switches that execute billions of mathematical commands per second without fatigue or errors.

for loop: Use this when you know exactly how many times you want to repeat something. It's like telling someone "count from 1 to 100".
while loop: Use this when you want to repeat something as long as a condition is true. It's like "keep eating soup while the bowl is not empty".

Be careful with while: if the condition never becomes false, the loop runs forever and your program freezes.

Solve the puzzle: for and while loops

5. What is a Function?

A function is a reusable block of code with a name. Instead of copying and pasting the same code everywhere, you write it once and then call it by its name whenever you need it.

It's like a "make coffee" button on a coffee machine. You press the button (call the function), and the machine runs through the whole process: grind beans, heat water, pour coffee. You don't need to know the details, you just use the button.

Define the function: def greet(): print("Hello!")
Call the function: greet()

Solve the puzzle: What is a function?

6. Function Arguments and Return Values

Functions become truly powerful when you can give them input and get output back.

Arguments (parameters) are the input you give to a function. They act like placeholders. When you call add(3, 4), 3 and 4 are the arguments.
Return value is what the function sends back. The return keyword stops the function and hands a value back to the caller.

Think of a blender: you put in fruit (arguments), it blends (the function body), and it returns a smoothie (the return value). You can then pour that smoothie into a glass (assign to a variable).

Solve the puzzle: arguments and return

7. What is an Array (List)?

A single variable holds one thing. But what if you need to store a whole shopping list? That's what an array (or list) is for.

It's a single name that holds multiple items in a numbered sequence. The items are stored in order, and you access them by their index (position number). Importantly, counting starts at 0, so the first item is at index 0.

fruits = ["apple", "banana", "cherry"]
print(fruits[0])  # "apple"
print(fruits[2])  # "cherry"

Arrays let you store, access, and modify collections of data in an organized way.

Solve the puzzle: What is an array?

8. What is an Algorithm?

An algorithm is simply a step‑by‑step recipe to solve a problem or accomplish a task. You follow algorithms all the time: a cooking recipe, the instructions to assemble furniture, or the process of doing laundry.

In programming, an algorithm is a sequence of clear, unambiguous steps that the computer can follow. To create one, you:

Define the goal (what should the result be?).
Break it down into the tiniest logical steps.
Order the steps correctly – some things must happen before others.
Execute them one by one.

The computer doesn't "think"; it just blindly follows your instructions, so every step must be precise.

Solve the puzzle: What is an algorithm?

9. Syntax Errors vs Logic Errors (Bugs)

Not all errors are created equal.

Syntax errors are like spelling and grammar mistakes. You forgot a quote, a bracket, or misspelled print. The computer immediately yells at you and refuses to run the program until you fix it.
Logic errors are the sneaky ones. The code runs perfectly – no error messages – but the result is wrong. For example, you wrote price + tax instead of price - tax. The computer did exactly what you told it, but your instruction was wrong.

Finding logic errors is called debugging – you play detective, check your variables, and trace through your steps until you find where your thinking went wrong.

Solve the puzzle: Syntax vs Logic errors

10. Compiler vs Interpreter

Your high‑level code (Python, JavaScript, C++) can't run directly on the processor. It needs a translator.

A compiler takes your entire program at once, translates it into a separate executable file (like an .exe), and then you run that file later. It's like translating a whole book and then printing it. Examples: C++, Go, Rust.
An interpreter translates your code line‑by‑line as it runs. There's no separate file; the translator is always there during execution. It's like a live interpreter at a meeting. Examples: Python, JavaScript.

Compiled programs usually run faster, while interpreted programs are easier to test quickly because you don't have to wait for a full build.

Solve the puzzle: Compiler vs Interpreter

11. What are Comments in Code?

Sometimes you want to leave a note for yourself or another developer without the computer trying to run it as code. That's a comment.

You mark a line as a comment with a special symbol (like # in Python or // in JavaScript). The translator completely ignores that line – it's only for humans.

Developers use comments to:

Explain why the code is written a certain way.
Leave reminders or warnings ("Don't change this formula!").
Temporarily disable a line of code while debugging (called "commenting out").

Good comments clarify intent; they don't just repeat what the code already says.

Solve the puzzle: What are comments?

Keep Exploring

These 11 concepts are the bedrock of every program you'll ever write. If you've read through them and solved the puzzles, you're already ahead of most beginners. Next, pick a language and start building small projects – you'll be surprised how much you can already do. Happy coding!

Why is all this needed? PRG | PRF | GGM

dima853 — Tue, 18 Aug 2026 17:46:35 +0000

This article may have inaccuracies, study this to get a general understanding of what it is.

There is a task: to encrypt data, random bits are needed. Lots of them. Generating true randomness is a slow and expensive thing.

...a slow and expensive thing.

Clarification: This is true for high-quality entropy. Modern CPUs have instructions like RDRAND, but for cryptography, multiple entropy sources (timings, ADC noise) are often combined, which indeed requires time to accumulate a sufficient number of bits.

At the same time, in many algorithms (encryption, authentication) we don't need randomness "in a vacuum" — we need the result to look random to anyone who doesn't have the secret key.

This gives rise to two basic concepts.

PRG — Stretching Randomness

Problem: we have a small amount of "true" randomness (e.g., 256 bits), but need a lot (gigabytes).

Solution: take a short random seed and pass it through a deterministic algorithm that outputs a long pseudorandom sequence.

Requirement: the output must be computationally indistinguishable from a truly random string for anyone who doesn't know the seed. No statistical anomalies, no patterns.

The key word is "computationally" - meaning there is no efficient algorithm that can distinguish them in polynomial time.

Analogy: if you are given two sheets with numbers — one with PRG output, the other with true randomness — you won't be able to tell which is which.

Remember: truly random bits are the gold standard we aim for when creating cryptographic keys and seeds. PRG and PRF are cryptographic primitives that must be computationally indistinguishable from this standard for anyone without the secret key.

Important: if the seed is known, the entire pseudorandom sequence can be reproduced. Security relies on the secrecy of the seed and the strength of the PRG itself. If the PRG is vulnerable, the output can be predicted even with a secret seed.

PRF — Pseudorandom Functions

Problem: we need not just to generate numbers, but to get a "random" result for each input. For example, for message authentication.

Solution: a function that, given a key and an arbitrary message, outputs a pseudorandom value.

Requirement: even knowing millions of "input-output" pairs, one cannot predict the value for a new input without the key.

Analogy: you have a magic box with a setting (the key). For each query, it gives a random-looking answer. Even if you've seen millions of answers to other queries, you won't guess the answer to a new one.

Important: PRF is a cryptographic function family that behaves almost indistinguishably from a perfectly random function for anyone without the key. MACs, key derivation schemes, and much more are built on PRFs.

GGM — The Bridge Between PRG and PRF

Intuition: if we have a PRG (can stretch randomness), can we make a PRF (a function with arbitrary input) from it?

It turns out, yes — via the Goldreich-Goldwasser-Micali tree.

How it works:

Take a PRG that turns one seed into two unpredictable ones
Build a binary tree where the root is our secret key
To compute the value for a message x, traverse the tree: each bit of x tells which branch to take
The result is the leaf we end up at

Simpler: turn the sequence of message bits into a path through the tree, applying the PRG at each step.

Conclusion: GGM is primarily a theoretical construction that proves in principle that any secure PRG can be used to build a secure PRF. In practice, more efficient constructions are used (HMAC, CMAC), but GGM is important for security proofs.

Clarification: In GGM, the tree is not built physically, but virtually — we compute the path on the fly, saving memory.

PRG is a static generator. You give it a seed, you get a long predetermined sequence. Everything is predictable in advance after initialization.

PRF is a function that can adapt. You give it a key and an arbitrary message — you get a unique result depending on that message.

GGM creates this adaptability from a PRG via a tree. Each bit of the input message tells the PRG which branch of the tree to go to next. Thus, different messages lead to different endpoints in the tree.

PRF is needed precisely for this adaptability — so that one key can generate different unpredictable results for different inputs, rather than just producing a static data stream like a PRG.

it's needed for variability

The Bottom Line

PRG is needed to make a lot of pseudorandom data from a small random seed
PRF is needed to get deterministic but random-looking results for any inputs
GGM shows that these concepts are related: having a PRG, you can build a PRF

All modern cryptography uses these ideas in one way or another. When you hear about HMAC, stream ciphers, authentication schemes — behind them are almost always either PRGs, PRFs, or their hybrids.

This is not abstract theory — it's the foundation upon which everything else is built.

Fundamental Principles of Proxy Server Operation

dima853 — Tue, 18 Aug 2026 17:46:02 +0000

Fundamental Principles of Proxy Server Operation

This article explains what proxies can and cannot do for your anonymity. You will learn the difference between HTTP/SOCKS/transparent proxies, learn how to choose the right type for your task, and understand why just changing an IP is not even close to sufficient for true anonymity.

Introduction: The Principle of Intermediation in Computer Networks

To understand what a proxy server is, one must first consider the standard model of interaction on the Internet without its participation. This model is known as the "direct connection client-server architecture."

Standard Model (without a proxy):

Your device (client), be it a computer, smartphone, or tablet, has a unique digital identifier — an IP address (Internet Protocol Address). This is your "network passport" that you present every time you go online.
When you type a website address (e.g., google.com) into your browser, your computer establishes a direct TCP connection with the server where that site is located.
Your browser sends an HTTP request to the target server. Important point: the IP address itself is not part of the HTTP headers. It is an element of a lower network layer (IP packet). However, a standard HTTP request contains headers such as Host, User-Agent, and, critically, when using a proxy, a service header X-Forwarded-For[1] is often added, which is precisely intended to convey the client's original IP address. When using HTTPS, the request content is encrypted, but the connection establishment information (IP addresses) remains visible at the network level.↙️

🔍 [1]X-Forwarded-For: This is a de facto standard header used by proxy servers and load balancers to convey the client's IP address. The first IP address in the list is usually the user's real IP address.

The server receives the request, processes it, and returns data back to your IP address, which the browser displays as a web page.

| ☠️ Problem |

The target server knows significantly more about you than it seems:

Network and system data: It receives your real IP address (and consequently your approximate geographical location and internet provider), as well as detailed information about your software, extracted from the HTTP request headers (e.g., User-Agent indicates the operating system, browser, and its version).
Digital Fingerprint (Browser Fingerprinting): This is a deeper and more insidious data collection technique. The server executes code on your browser's side (typically in JavaScript) that allows it to gather a unique "portrait":
- Complete list of installed fonts (which can be obtained via CSS or Canvas API).
- Screen dimensions and parameters (resolution, color depth, touch interface availability).
- List of plugins and MIME types.
- Temporal characteristics (graphics subsystem performance, clock frequency).
- Connection data (list of time zones, language settings).
- Data from browser local storage (Local Storage, Session Storage, Cookies). If you have visited the site before, it might have saved a unique identifier in your storage, which upon a revisit will uniquely link the new session to your old one, even if you changed your IP address.
- EXIF data — this is a metadata standard (Exchangeable Image File Format) stored in digital photos and contains information about the shot and camera settings.

Key takeaway: A proxy server ONLY effectively masks your IP address and, to some extent, your provider's data, hahah. However, it does not protect against digital fingerprinting methods and tracking through browser storage. Countering these threats requires additional tools: disabling JavaScript, using specialized anti-fingerprinting browsers, etc.

⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣⭣

Why a Proxy is NOT Anonymity (and often the illusion of it):

1. The Proxy Provider Knows EVERYTHING.

Your traffic goes through the chain: You -> Your ISP -> Proxy Server -> Target Site.
The owner of the proxy server sees:

Your real IP address.
All your unencrypted traffic (logins, passwords, browsing history).
Your connection times.
Metadata.

If it's a commercial or state-owned proxy, it keeps logs. You are simply swapping one "witness" (the target site) for another, often more centralized and dangerous one (the proxy provider).

2. DNS Leaks.

A classic mistake. You configured a proxy in your browser for HTTP/HTTPS traffic, but domain name resolution requests (e.g., converting google.com to an IP address) might bypass the proxy, going through your standard connection. In this case, your ISP and anyone listening on the network can see which sites you are visiting, even if the content itself loads through the proxy. SOCKS5 can proxy DNS, but this must be explicitly configured.

3. WebRTC Leaks.

This is a technology for video chats and P2P connections in the browser. Through a special JavaScript request, a site can force the browser to reveal your real, local (behind NAT)[2] and public IP address, completely ignoring the proxy settings. This can only be disabled manually in the browser settings.

🔒 Complete guide to protection against DNS and WebRTC leaks

[2] NAT (Network Address Translation) — is not a protocol or a service, but a mechanism used by routers to solve one of the biggest problems of the early internet.

Network address translation between a private network and the Internet

Briefly about the problem:

IPv4 addresses ran out. There are only about 4.3 billion of them, but there are many more devices.

NAT Solution:
The router creates a private network (home, office) with "internal" addresses (e.g., 192.168.1.x). The router itself goes out to the internet with one "public" IP address.

NAT substitutes the addresses of devices from the private network with its own "public" IP, remembering which internal device the connection belongs to in order to return the response.

Simple analogy:
It's like in an office of 100 employees, the secretary has one phone number. Everyone calls from the office through the secretary, and they know which employee to transfer an incoming call to.

4. Digital Fingerprint (Fingerprinting).

A site identifies you not by IP, but by a unique combination of:

Screen resolution, font list, plugins.
Browser and OS version.
Behavioral factors (typing rhythm, mouse movement). This "fingerprint" will be the same, whether through a proxy or without. The proxy is powerless here.

5. Behavioral Analysis.

Even if you logged in via a proxy, the analytics system on the site sees that "a user with IP 1.1.1.1 came from google.com via the query 'how to hack the pentagon', immediately logged into the account ivan_ivanov@mail.ru and started downloading instructions." The IP is different, but the person and their intentions are the same.

6. Cookies and Local Storage.

The browser, as it stored your cookies and data in Local Storage, continues to send them to the sites. The proxy again has nothing to do with it.

Conclusion:

"A proxy server changes the IP address visible to the target server. This creates a basic, primitive level of concealment, which is easily bypassed by modern tracking methods and is useless against targeted de-anonymization.

Effective anonymity is a set of measures:

Trustless model: Using systems like Tor (where several independent nodes do not know the full route) or high-quality VPNs with a No-Logs policy (which you are forced to trust).

Briefly:

"No-Logs" VPN is not a myth, but requires verification. The key principle: you cannot hand over what you don't have (i.e., if you don't collect it in the first place.).

Where to look:

Jurisdiction: Countries outside surveillance alliances (like the "14 Eyes"). Examples: Panama, British Virgin Islands, Seychelles.
Practical verification: Trust only those whose "No-Logs" has been confirmed in court or by an audit.

Examples (verified):

ExpressVPN (BVI) — when servers were seized, no logs were found. https://proprivacy.com/privacy-news/expressvpn-cannot-hand-over-logs
Mullvad VPN (Sweden) — police left empty-handed during a raid. https://myseldon.com/ru/news/index/282486389
Proton VPN (Switzerland) — strong jurisdiction and audits.

What to check (checklist):

Jurisdiction
Confirmed cases of no logs
Independent audit
Technologies like RAM-only servers
Clean reputation

Summary: There is no absolute guarantee, but choosing the right VPN minimizes the risk, as the provider physically and legally cannot provide non-existent logs.

Fighting fingerprinting: Using browsers like Tor Browser, which "pretend" to be the same for all users.
Changing behavior: Refraining from logging into your accounts, using separate sessions, being cautious with JavaScript.

Using just a public proxy for anonymity is like hiding your face with a paper bag while leaving a tag with your name and address on your back. It solves one narrow task (changing IP), but does not make you anonymous."

Detailed Breakdown of the Waiter in a Restaurant Analogy

You (the client) — is your computer with a running browser.
The Waiter (the proxy) — is the proxy server with its own IP address.
The Kitchen (the web server) — is the target server, for example, Google's servers.
The Order (the HTTP request) — is a technically formed data packet containing the URL, method (GET, POST), headers, etc.
The Dish (the HTTP response) — is the HTML code of the page, images, CSS styles, and JavaScript files.

The waiter can change the order. A proxy server is not always a "dumb" relay. It can modify the outgoing request. For example, it can:

Remove or change certain headers (e.g., Referer, which tells the server which page you came from).
Add its own headers.
Compress outgoing data to save traffic.
Block the request if it is directed to a prohibited resource (in corporate or ISP proxies).

The waiter can give you something you didn't ask for. The proxy server might return not the current data from the server, but a cached copy it has, if it exists and hasn't expired. This is the very "traffic saving" that is rarely used on the client side today but is actively used on the ISP side to offload channels.
Not all waiters are the same. The analogy does not account for fundamentally different types of proxies (HTTP, SOCKS, transparent), which operate at different layers of the OSI network model. A SOCKS proxy, for example, is not a "waiter" but more like a "courier service" that can deliver any cargo (any type of network traffic), not just "dishes from the restaurant" (web traffic).

Why is this needed? Detailed analysis of use cases

Using a proxy server is not a magical solution to all problems, but a specific tool for achieving certain network tasks.

1. Bypassing Blocks (IP-banning, geo-restrictions)

This is the most common and understandable use case.

Technical blocking mechanism: Most blocks on the internet are implemented based on IP addresses. A network administrator (in an office, school, country) or the owner of a web service (e.g., a streaming platform) compiles a blacklist of IP addresses or entire ranges. When a request comes from an IP address in this list, the server either does not respond or returns a blocking message.
How a proxy bypasses the block: Since your request comes from the proxy server's IP address, which is not on the blacklist, the block does not trigger. The request is processed successfully.
Important nuances:
IP address quality. If you use a public, free proxy, its IP address is highly likely already on the blacklists of many services, as it has been used for similar purposes before you.
Geolocation. To bypass geo-restrictions (e.g., to watch a service available only in the USA), you must use a proxy server with an IP address located in the required country. The service determines your "location" by the geolocation of the proxy's IP address.

2. Anonymity: Correcting the Understanding of the Term

Critically important: A proxy server does not make you an "invisible man" on the internet in an absolute sense. It provides a certain level of anonymity, which depends on its type and configuration.

What is hidden: Your real IP address from the target web server. This is the main thing.
What is NOT hidden or can be revealed:
The proxy server provider knows your real IP address, as you are the one establishing the connection with it.
If the connection between you and the proxy server is not encrypted (HTTPS or SOCKS5 with encryption is not used), then your internet provider or anyone eavesdropping on your network (e.g., on public Wi-Fi) can see that you are using a proxy and potentially intercept your unencrypted traffic.
There are different levels of proxy anonymity. Some types (transparent) do not hide the fact of using a proxy or your IP at all, while others (anonymous) hide the IP but do not hide the fact of using a proxy. Only elite (high anonymous) proxies do not inform the target server of their intermediation.
Your identity can be de-anonymized by behavioral factors ("digital fingerprint") — browser plugins used, screen resolution, fonts, even typing rhythm. A proxy does not protect against this.

Conclusion: A proxy is a tool for hiding an IP address from the end server, not a panacea for complete anonymity. For the latter, more complex systems like Tor are required.

3. Security: An Additional Barrier with Caveats

Using a proxy can enhance security, but this is not its primary or most reliable function.

Content filtering: Corporate or ISP proxies are often used to block access to malicious sites. The proxy server can check the requested URL against a database of phishing and malware resources and block the connection before it reaches your device.
Virus scanning: Some proxies can check downloaded files (e.g., .exe, .zip) using antivirus engines.
Limiting risks on public Wi-Fi: When connected through a proxy, all your web traffic is redirected through it. If an attacker on the same public network tries to redirect you to a fake website, a filtering proxy can prevent this.
Caution: The proxy server itself represents a point of vulnerability. If you use an unreliable (especially free) proxy, its owner has the technical ability to intercept and analyze all your unencrypted traffic, including logins and passwords. Therefore, you should only trust verified providers, and it is always preferable to use encryption (HTTPS) over the proxy.

4. Data Parsing (Web Scraping)

This is a professional task where the proxy ceases to be a tool for the average user and becomes a critically important infrastructure component.

The problem: When automatically collecting data from sites, you send a large number of requests from one IP address in a short period of time. The site's protection systems (e.g., Cloudflare) easily detect such behavior as non-human and block the IP address on suspicion of a DDoS attack or scraping.
The solution: Using a pool (rotator) of proxy servers. The parsing program sends requests in turn through different proxies, thus distributing the load across hundreds or thousands of different IP addresses. For the target server, this looks like normal traffic from different devices around the world, which does not raise suspicions.
Requirements for parsing proxies: High speed, reliability, a large number of IP addresses in the pool, and often residential IP addresses (the IP type will be covered in part 2) are required, which are harder to block.

5. SEO and SMM (Managing Multiple Accounts)

The principle here is similar to parsing, but applied in marketing.

The problem: Social media platforms (Instagram, Facebook, TikTok) and search engines (Google) strictly monitor account behavior. If several accounts log in from the same IP address, the system algorithms can link them together ("link by IP"). If one account is banned, there is a high probability of blocking all accounts linked to it.
The solution: Each account or group of accounts is assigned its own unique proxy server with a permanent (static) IP address. Thus, for the platform, each account exists in its own isolated network environment, as if it were managed from different apartments, offices, or cities. This significantly reduces the risk of mass blocking.

6. Traffic Saving (Caching) — Historical Context

This is a function that has lost its relevance for the end user but remains important at the infrastructure level.

How it worked: The proxy server saved (cached) copies of frequently requested resources: images, CSS files, even entire HTML pages. When the next user on the same network (e.g., a company employee) requested the same resource, the proxy server delivered the data from its cache without accessing the external internet. This saved external bandwidth and sped up loading.
Why it's rare now:

Encryption (HTTPS everywhere). The modern internet almost entirely operates over HTTPS. This means the connection between the browser and the server is encrypted. The proxy server cannot decrypt this traffic and, consequently, cannot analyze and cache its content. It can only cache unencrypted HTTP traffic, the share of which is negligible.
Dynamic content. Web pages have become dynamic and personalized. Social feeds, news streams, advertising — the content on the same URL is different for different users and at different times. Such content is pointless to cache.
CDN (Content Delivery Network). The caching function has been taken over by global content delivery networks (Cloudflare, Akamai, etc.), which place copies of content on servers worldwide, close to users.

Today, caching proxies are used mainly by internet providers to reduce load on backbone channels (caching popular video from YouTube) and in large corporate networks for caching operating system and program updates.

The Most Important Proxy Types: Classification by Protocol and Operation Level

Classifying proxies by protocol is the foundation, as it determines what specific network traffic the proxy can work with.

1. HTTP(S) Proxy — Specialized Web Inspectors

Operation Level: Application Layer of the OSI/TCP model. The key feature is that the proxy understands the structure and semantics of the HTTP protocol.
Principle of Operation: Deep understanding of HTTP allows such a proxy to:
- Analyze and modify HTTP headers (add, remove, change).
- Cache content — save copies of frequently requested resources to speed up access.
- Filter traffic based on URL, MIME types, or content.
- Require authentication from the user (login/password).
Critical Difference between HTTP and HTTPS:
- HTTP proxy: Works with unencrypted traffic. Sees everything: full URLs, sent data (logins, passwords), page contents. It is a "Man-in-the-Middle" by nature.
- HTTPS proxy (CONNECT mode): To protect content from being viewed, the CONNECT command is used. The proxy establishes an end-to-end TLS tunnel between the client and the server. Important: In this mode, the proxy cannot decrypt or modify the transmitted data. It only relays encrypted bytes, acting as a "dumb pipe." It only sees the hostname of the target server (specified in CONNECT), but not the full URL-path or data inside the session.
Hard Limitations: Work EXCLUSIVELY with HTTP/HTTPS traffic. Not suitable for FTP, game servers, VoIP, or torrents (with rare exceptions when the client can only proxy HTTP requests to trackers).
Scope of Application: Web browsers and applications using HTTP/HTTPS APIs (REST, GraphQL clients).

2. SOCKS Proxy — Universal Transport Relays

Operation Level: Session Layer or even between Session and Transport Layers. SOCKS operates below HTTP proxies and is abstracted from application layer protocols. For it, the transmitted data is an opaque byte stream.
Principle of Operation: A SOCKS proxy redirects TCP/UDP packets without delving into their content. It does not analyze headers, cache, or filter content. Its task is to create a "transport corridor."
Version Evolution:
- SOCKS4: Outdated standard. Supports only TCP, authentication is based on the client's IP address.
- SOCKS5: Modern standard. Key improvements:
- UDP support: Indispensable for DNS queries, VoIP (Zoom, Telegram), online games.
- Flexible authentication: Methods LOGIN/PASSWORD and NO AUTHENTICATION.
- IPv6 support.
- Remote DNS resolution (Remote DNS): Critically important option. When activated on the client, DNS queries are proxied through the SOCKS connection, preventing leaks. Without it, DNS queries bypass the proxy, revealing browsing history.
Scope of Application: Any applications not limited to web protocols: torrent clients, online games, messengers, SSH and FTP clients.

Excellent! Let's break down RFC 1928 — SOCKS Protocol Version 5 meticulously. This is not just a dry standard, but an elegant engineering solution that remains relevant almost 30 years later.

Architecture and Philosophy of SOCKS5 (RFC 1928)

Key Idea: SOCKS5 is a "shim-layer" between the Application (L7) and Transport (L4) layers, providing transparent traffic tunneling through firewalls.

[Application] → [SOCKS-client] → [SOCKS-server] → [Target Server]

Connection Establishment Process (3 Phases)

Phase 1: Greeting and Authentication Method Selection

The client connects to TCP port 1080 and sends:

+----+----------+----------+
|VER | NMETHODS | METHODS  |
+----+----------+----------+
| 0x05|    1     | 1 to 255 |
+----+----------+----------+

Breakdown:

VER = 0x05 — SOCKS5 version
NMETHODS — number of supported authentication methods
METHODS — list of methods:

0x00 - NO AUTHENTICATION REQUIRED
0x01 - GSSAPI (Kerberos)
0x02 - USERNAME/PASSWORD
0x03-0x7F - IANA ASSIGNED
0x80-0xFE - PRIVATE METHODS
0xFF - NO ACCEPTABLE METHODS

Server responds:

+----+--------+
|VER | METHOD |
+----+--------+
| 0x05| chosen |
+----+--------+

If the server returns 0xFF, the connection is terminated.

Phase 2: Authentication (method-dependent)

For method 0x02 (USERNAME/PASSWORD) — RFC 1929:

+----+-----+-------+------+----------+------+----------+
|VER | ULEN | UNAME | PLEN | PASSWD | VER | STATUS |
+----+-----+-------+------+----------+------+----------+
| 0x01|  1   |  var  |  1   |   var   | 0x01 |    1     |
+----+-----+-------+------+----------+------+----------+

Statuses: 0x00 — success, 0x01 — failure

Phase 3: Sending the Request

After successful authentication, the client sends the main request:

+----+-----+-------+------+----------+----------+
|VER | CMD |  RSV  | ATYP | DST.ADDR | DST.PORT |
+----+-----+-------+------+----------+----------+
| 1  |  1  | 0x00  |  1   | Variable |    2     |
+----+-----+-------+------+----------+----------+

Request Types (CMD)

CONNECT (0x01) — establish a TCP connection to the target server
BIND (0x02) — reverse connection (for FTP, P2P)
UDP ASSOCIATE (0x03) — work with UDP traffic

🌐 Address Types (ATYP)

0x01 - IPv4 (4 bytes)
0x03 - DOMAINNAME (1 byte length + string without NULL)
0x04 - IPv6 (16 bytes)

Important: For domain names, the first byte contains the name length, followed by the string WITHOUT a null terminator.

Server Response

+----+-----+-------+------+----------+----------+
|VER | REP |  RSV  | ATYP | BND.ADDR | BND.PORT |
+----+-----+-------+------+----------+----------+
| 1  |  1  | 0x00  |  1   | Variable |    2     |
+----+-----+-------+------+----------+----------+

Response Codes (REP)

0x00 - succeeded
0x01 - general SOCKS server failure
0x02 - connection not allowed by ruleset
0x03 - Network unreachable
0x04 - Host unreachable
0x05 - Connection refused
0x06 - TTL expired
0x07 - Command not supported
0x08 - Address type not supported

Special Scenarios

BIND Request (for FTP)

Client sends a BIND request
Server creates a socket and sends the first response with BND.ADDR/BND.PORT
Client communicates this data to the FTP server
When the FTP server connects, the SOCKS server sends a second response

UDP ASSOCIATE

Creates an association for UDP traffic
Client must send UDP packets to BND.ADDR:BND.PORT
Each datagram has a header:

+----+------+------+----------+----------+----------+
|RSV | FRAG | ATYP | DST.ADDR | DST.PORT |   DATA   |
+----+------+------+----------+----------+----------+
| 2  |  1   |  1   | Variable |    2     | Variable |
+----+------+------+----------+----------+----------+

💡 Critically Important Features

1. DNS Support at the Protocol Level

SOCKS5 can resolve domain names on the server side (ATYP=0x03), which prevents DNS leaks.

2. UDP Fragmentation

Supports fragmentation via the FRAG field:

0x00 — standalone datagram
1-127 — fragment position
High bit = 1 — last fragment

3. Security through Authentication

Unlike SOCKS4, it has a built-in authentication system.

Practical Significance Today

Bypassing blocks — the basis of most proxy services
Tor Network — uses SOCKS5 as an interface for applications
Mobile applications — many VPN applications use SOCKS5
Data parsing — IP rotation via SOCKS5 proxies

Limitations and Caveats

No encryption by default — traffic between client and SOCKS server is not encrypted
WebRTC leaks — SOCKS5 does not protect against WebRTC leaks
Requires client-side support — the application must be SOCKS-aware

Conclusion

SOCKS5 is an elegant, minimalist protocol that solves a specific task: transparently tunneling traffic through an intermediate node. Its strength lies in its simplicity and extensibility, which explains its longevity in the ever-changing world of network technologies.

The protocol is perfectly suited for situations where you need to change the source of an outgoing connection without modifying the application itself at the protocol level.

3. Transparent Proxies — The Coercive Network Overseer

This is not a protocol, but an implementation method, invisible to the end user.

Principle of Operation: Proxy settings are not configured in the OS or applications. The network gateway (router, firewall) using mechanisms like NAT (Destination NAT) or Policy-Based Routing (PBR) automatically redirects all outgoing traffic (ports 80, 443) to an internal proxy server.
What the end server sees: The configuration varies, but in the classic case, the proxy, while remaining "invisible" to the client, adds a special header (most often X-Forwarded-For) to the HTTP request, in which it passes the user's real IP address. Thus, the server knows both the fact of proxying and the original client IP.
Where it's found: Corporate and ISP networks, public Wi-Fi (airports, hotels). Goals — caching, content filtering, monitoring.
Hard Verdict: Absolutely useless for anonymity and bypassing geographical blocks, as it does not hide, and often directly reveals your IP address. Its purpose is control, not freedom.

🎯 Final Conclusion

A proxy is a tool for changing your IP, not for anonymity. It solves specific problems: bypassing blocks, parsing, and account management. True anonymity requires a combination of measures: Tor, anti-tracking browsers, and behavior modification (and a whole bunch of other things). Choose the proxy type based on your specific needs—there are no one-size-fits-all solutions.

What is SIMD? The Basic Concept

dima853 — Tue, 18 Aug 2026 17:45:38 +0000

SIMD (Single Instruction, Multiple Data) is a type of parallel data processing in which a single instruction is executed simultaneously on multiple data elements.

A simple analogy: Imagine you have 4 pairs of numbers, and you need to add each pair.

Scalar approach (SISD): You take the first pair (A1, B1), execute the "add" command and get C1. Then you take the second pair (A2, B2), execute "add" again and get C2, and so on. 4 instructions for 4 operations.
Efficiency: The text emphasizes that SIMD can provide an "order of magnitude increase in efficiency" (work per instruction) compared to scalar code.
SIMD approach: You load all 4 pairs of numbers into a special wide register. Then you execute ONE command "add all pairs simultaneously". As a result, you immediately get 4 results (C1, C2, C3, C4). 1 instruction for 4 operations.

This allows for significant acceleration in tasks where it is necessary to apply the same operation to a large array of data.

1. Key Characteristics of SIMD

Data Level Parallelism: SIMD does not create parallel command threads (like in multithreading), but uses the parallelism of the data itself. All processed elements go through the same operation "pipeline".

Let's go into more detail if it's not clear ⬇️⬇️⬇️

Data Parallelism (SIMD) vs Task Parallelism (Multithreading)

TASK Parallelism:
Different workers do DIFFERENT things with different data.
Example: 4 chefs cook 4 different dishes.

DATA Parallelism:
One boss gives ONE command, which everyone executes SIMULTANEOUSLY on their own data.
Example: Coach to the team: "EVERYONE squat!" — 20 people squat at once.

The Essence: SIMD is not "divide and conquer", but "do everything at once".

Not to be confused with ISA: SIMD is an architectural principle that can be implemented as an instruction set (like SSE or AVX), but it is not the entire instruction set architecture as a whole.

What is ISA? ⬇️⬇️⬇️

ISA (Instruction Set Architecture) is the language of communication between the processor and the programmer.

In a nutshell: ISA is the list of commands that the processor understands.

The Essence in Three Points:

"Contract" or "Interface"
ISA is not the processor itself, but its "instruction manual". It says: "Here are the commands (addition, copy, branch) I understand and here are the fast memory cells (registers) I have".
Separates "What" from "How"
- ISA defines WHAT the processor can do (which set of commands is available).
- Microarchitecture defines HOW it does it (the internal design, which can be different for different manufacturers).
Example: Intel and AMD processors have the same ISA (x86), but different internal design.
Compatibility Guarantee
Thanks to ISA, the same program will work on any processor that understands this "language", even if these processors are made by different companies or have different performance.

Analogy:
ISA is like traffic rules. All drivers (programs) know that a "Stop" sign (processor command) means to stop. It doesn't matter which exact car (microarchitecture) you are driving - Mercedes or BMW - the rule is the same.

but, let's see how exactly ISA defines something there

ISA = Table of Operation Codes (OPcode)

OPcode is a number that tells the processor WHAT TO DO

(simplified, figuratively)

Binary OPcode	Command	What it does
`001000`	`addi`	Add Immediate (constant)
`000000`	`add`	Add registers
`100011`	`lw`	Load Word (from memory)

How it works:

The processor sees 001000 → looks up the ISA table → understands: "need to add a register with a number"

ISA is a dictionary:

001000 = "addi"
000000 = "add"
100011 = "lw"

let's say there is also this

The processor doesn't think — it simply executes actions according to a pre-defined table (ISA)

2. Hardware

SIMD is implemented in most modern processors in the form of special execution units and registers.

Registers: These are special, very wide registers that can store multiple values simultaneously.
- Example: A 128-bit SSE register can store four 32-bit floating-point numbers or sixteen 8-bit integers.
- Modern standards, such as AVX-512, use 512-bit registers, allowing work with 16 floating-point numbers simultaneously.
Examples of SIMD extensions:
- Intel: MMX, SSE, SSE2, SSE3, AVX, AVX2, AVX-512.
- AMD: 3DNow!, and now also supports AVX.
- ARM: NEON (very common in mobile processors), Scalable Vector Extension (SVE).
- PowerPC/IBM: AltiVec.
Other devices: SIMD is actively used in GPUs (graphics processing units), specialized processors for video processing (for example, the Cell processor in PlayStation 3) and AI accelerators (for example, the Neural Engine in Apple chips).

3. Software / Programmer Interface

A programmer does not need to write code in assembly to use SIMD. There are more convenient ways:

Intrinsics: These are special functions in C/C++ languages that compile directly into SIMD instructions. They look like ordinary functions but give the programmer low-level control.
- Example: _mm_add_ps() for adding four floating-point numbers in SSE.
Auto-vectorization: Modern compilers (GCC, Clang, MSVC, ICC) can automatically analyze loops and transform scalar code into SIMD code. Compilation flags are often used for this, for example, -O3 or -ftree-vectorize.
Language Extensions and Libraries:
- In C/C++ there is an experimental header <std::simd>.
- In Rust there is the packed_simd crate.
- In .NET there is the System.Numerics.Vector namespace.
- OpenMP provides the #pragma omp simd directive to hint to the compiler.

4. Multi-versioning (SIMD Multi-versioning)

Since different generations of SIMD instructions exist, a program must work on different processors. For this, a method is used where several versions of the same code are created:

FMV (Function Multi-versioning): The same function is compiled multiple times for different instruction sets (for example, one version for SSE4, another for AVX2). During runtime, the program checks the CPU capabilities and selects the appropriate version.
LMV (Library Multi-versioning): An entire library is compiled in several variants, and the operating system or program loads the required version.

5. Disadvantages

Not for all tasks: SIMD is effective only for tasks with a high degree of data parallelism. Algorithms with strong dependencies between steps (for example, traversing a linked list) are poorly vectorized.
Complexity of manual optimization: Although compilers handle auto-vectorization well, achieving maximum performance often requires manual tuning using intrinsics, which requires deep knowledge (but this is a plus, not a minus).

6. Where is it used? (Commercial Applications)

SIMD is critically important for tasks requiring intensive computations on large data arrays:

Image and Video Processing: Changing brightness, contrast, applying filters, encoding/decoding (MPEG, H.264).
Audio Processing: Mixing, applying effects, equalizers.
Scientific Computing: Numerical modeling, matrix and vector calculations.
Games: 3D vertex transformations, physics calculations, artificial intelligence.
Cryptography: Many encryption and hashing algorithms can be accelerated using SIMD.
Artificial Intelligence: Matrix multiplication and convolutions in neural networks.

7. Confusion with SIMT

SIMD: A single instruction controls multiple processing elements in a CPU.
SIMT (Single Instruction, Multiple Threads): An architecture used in GPUs (NVIDIA). Here, a single instruction is also executed on multiple data elements, but it is delivered to multiple independent threads, which can have their own execution path (for example, conditional if/else statements are handled differently). The text from Wikipedia clarifies that SIMT is a subcategory of SIMD according to Flynn's taxonomy.

Summary

SIMD is a fundamental acceleration technology that has become an integral part of modern processors. It allows for a significant increase in performance in multimedia, scientific, and engineering tasks by parallelizing the execution of the same operation on a set of data. Despite some programming complexities, thanks to automatic vectorization in compilers and convenient libraries, the benefits of SIMD are becoming available to a wider range of developers.

SNMP Guide: What, Why, and How?

dima853 — Tue, 18 Aug 2026 17:44:15 +0000

🌐 What SNMP Actually Does:

SNMP = "WhatsApp for Network Devices" 💬

Think of it like this:

You (Manager) --WhatsApp--> Friend (Network Device)
"Hey, what's your status?" = GET request
"BRB, battery 5%" = TRAP notification
"Change your profile pic" = SET request

Real World Examples:

📱 Your phone monitoring Wi-Fi router signal strength
🖥️ IT department checking if servers are alive
🚨 Data center getting alerts when temperature spikes
📈 Monitoring system tracking network bandwidth usage

🔗 SNMP + MIB + LLDP = The Dream Team

You're absolutely right! Here's how they work together:

SNMP 🕵️‍♂️ - The Detective

Asks questions: "What's your CPU usage?"
Gives commands: "Shut down port 5!"
Listens for gossip: "Hey, I just crashed!"

MIB 📚 - The Phone Book

Contains all "questions" you can ask
Every device has its own phone book
Standardized "contact list" for all vendors

LLDP 📢 - The Town Crier

Shouts: "I'm Router-X, connected to Switch-Y!"
Like WhatsApp status: "Here's who I am and who I know"
SNMP reads LLDP info to map network topology

🎪 The "WhatsApp" Analogy:

SNMP Manager = You texting friends
SNMP Agent = Your friends' phones
MIB = Your contacts list 📞
OID = Phone numbers 📱
GET = "What's up?" ❓
SET = "Change your status!" ✏️
TRAP = "OMG emergency!" 🚨
LLDP = "I'm at Starbucks with Bob" 📍

🚀 Why You Should Care:

Without SNMP:

🕵️‍♂️ Manual checking of every device
😴 No alerts when things break
🤷 No historical data for troubleshooting

With SNMP:

📊 Dashboard showing everything
📱 Phone alerts when problems occur
📈 Trend analysis to predict issues
🤖 Automated responses to common problems

💡 TL;DR:

SNMP lets you remotely monitor and control network devices like you're texting friends on WhatsApp!

Manager = You texting
Agent = Your friends
MIB = Contacts list
OID = Phone numbers
LLDP = Location sharing

Result: You can manage thousands of devices without leaving your chair! 🪑✨

Now go impress your coworkers with your SNMP knowledge! 😎

📋 Header Overview

#pragma once
#ifndef SNMP_H
#define SNMP_H

#ifdef __cplusplus
extern "C"
{
#endif

Purpose: Standard C header guards to prevent multiple inclusions and ensure C++ compatibility.

This approach is widely considered a best practice.

The combination of #pragma once and the classic #ifndef provides a balanced approach to protect against multiple inclusion of header files, though the actual benefits may vary depending on the specific use case.

Why this approach is commonly recommended:

#pragma once - Potential speed and convenience
- May be faster in some scenarios: On projects with complex include hierarchies, some compilers can optimize file processing using filesystem metadata.
- Convenience factor: Avoids the need to maintain unique macro names across the codebase.
- Reduced naming conflicts: Eliminates potential macro name collisions between different headers.
#ifndef / #define - Portability and reliability
- Wide portability: The #ifndef directive is a C/C++ language standard that should work on any compliant compiler.
- Fallback protection: Provides a reliable alternative when #pragma once support is limited or encounters unusual filesystem situations.

but macros are not safe.

Performance Observations from Testing:

Our limited testing showed mixed results that may not be representative of all scenarios:

Small to medium files: Performance differences were generally minor (0.01-0.05s)
Larger inclusion scenarios: Some tests showed #pragma once with modest improvements
Combined approach: Performance was comparable to either method alone in most cases

Note: The actual performance impact likely depends on many factors including compiler implementation, filesystem characteristics, project structure, and build environment. The benefits may be more significant in very large projects with complex include graphs.

Practical Considerations:

Modern compiler behavior: Most contemporary compilers (GCC, Clang, MSVC) recognize #pragma once while maintaining #ifndef compatibility
Compiler variations: Some compilers may optimize the combined approach differently than others
Edge case handling: The dual approach may provide additional safety in unusual environments like network filesystems or with symbolic links

Conservative Recommendation:

This combined approach represents a reasonable compromise that prioritizes compatibility while potentially offering performance benefits in some situations. For maximum portability across diverse build environments, the additional #ifndef guard provides insurance against #pragma once limitations in edge cases.

The minimal overhead of including both directives appears to be acceptable for most practical purposes, though individual projects should consider their specific requirements and target environments.

Implementation Details & Testing - https://github.com/dima853/self_university/tree/main/network/c/compatibility/ifndef_pragmaonce

SNMP Header Documentation (Modernized Version)

📋 Header Overview

#pragma once
#ifndef SNMP_H
#define SNMP_H

#ifdef __cplusplus
extern "C" {
#endif

Purpose: Standard C header guards to prevent multiple inclusions and ensure C++ compatibility.

This approach is widely considered a best practice.

Why this approach is commonly recommended:

#pragma once - Potential speed and convenience
- May be faster in some scenarios: On projects with complex include hierarchies, some compilers can optimize file processing using filesystem metadata.
- Convenience factor: Avoids the need to maintain unique macro names across the codebase.
- Reduced naming conflicts: Eliminates potential macro name collisions between different headers.
#ifndef / #define - Portability and reliability
- Wide portability: The #ifndef directive is a C/C++ language standard that should work on any compliant compiler.
- Fallback protection: Provides a reliable alternative when #pragma once support is limited or encounters unusual filesystem situations.

Performance Observations from Testing:

Our limited testing showed mixed results that may not be representative of all scenarios:

Small to medium files: Performance differences were generally minor (0.01-0.05s)
Larger inclusion scenarios: Some tests showed #pragma once with modest improvements
Combined approach: Performance was comparable to either method alone in most cases

Practical Considerations:

Modern compiler behavior: Most contemporary compilers (GCC, Clang, MSVC) recognize #pragma once while maintaining #ifndef compatibility
Compiler variations: Some compilers may optimize the combined approach differently than others
Edge case handling: The dual approach may provide additional safety in unusual environments like network filesystems or with symbolic links

Conservative Recommendation:

The minimal overhead of including both directives appears to be acceptable for most practical purposes, though individual projects should consider their specific requirements and target environments.

Implementation Details & Testing - https://github.com/dima853/self_university/tree/main/network/c/compatibility/ifndef_pragmaonce

🌐 Network Constants

// ==================== Network Constants ====================
#define SNMP_PORT 161      // SNMP agent request port
#define SNMP_TRAP_PORT 162 // SNMP manager notification port

Purpose: Standard IANA-assigned ports for SNMP operations.

Port	Direction	Purpose
161	Manager → Agent	GET/SET requests to agents
162	Agent → Manager	Traps/Informs to managers

✅ OFFICIALLY CONFIRMED BY IANA:

Service Name: snmp (Port 161)

Port Number: 161
Transport Protocol: tcp, udp
Description: SNMP

Service Name: snmptrap (Port 162)

Port Number: 162
Transport Protocol: tcp, udp
Description: SNMPTRAP
Assignee: Marshall Rose

#define SNMP_MAX_MSG_SIZE 1500          // Ethernet MTU
#define SNMP_MIN_MSG_SIZE 484           // RFC 3416 minimum
#define SNMP_MAX_PACKET_SIZE 0x7FFFFFFF // Maximum theoretical size

But it's a shit code, here's the correct code.

    // ==================== SNMP Port Constants ====================
    extern const uint16_t SNMP_PORT;      // SNMP agent request port
    extern const uint16_t SNMP_TRAP_PORT; // SNMP manager notification port

    // ==================== SNMP Size Constants ====================
    extern const size_t SNMP_MAX_MSG_SIZE;     // Ethernet MTU
    extern const size_t SNMP_MIN_MSG_SIZE;     // RFC 3416 minimum
    extern const int32_t SNMP_MAX_PACKET_SIZE; // Maximum theoretical size

    // ==================== Protocol Version ====================
    static const int SNMP_VERSION_3 = 3; // SNMPv3

    // ==================== PDU Type Constants ====================
    typedef enum
    {
        SNMP_PDU_GET = 0xA0,      // 160 - GetRequest
        SNMP_PDU_GETNEXT = 0xA1,  // 161 - GetNextRequest
        SNMP_PDU_RESPONSE = 0xA2, // 162 - Response
        SNMP_PDU_SET = 0xA3,      // 163 - SetRequest
        SNMP_PDU_GETBULK = 0xA5,  // 165 - GetBulkRequest
        SNMP_PDU_INFORM = 0xA6,   // 166 - InformRequest
        SNMP_PDU_TRAP2 = 0xA7,    // 167 - SNMPv2-Trap
        SNMP_PDU_REPORT = 0xA8    // 168 - Report
    } SnmpPduType;

Cheat sheet: Macro vs Enum vs Constant

IMPORTANT ! https://gist.github.com/dima853/73ba55e23210efe880349a99fb6b904c

use it as a REMINDER, not as a guide!

1) 📄 From RFC 894 (IP over Ethernet):

Page 1:

"The maximum length of an IP datagram sent over an Ethernet is 1500 octets."

This corresponds to: #define SNMP_MAX_MSG_SIZE 1500

2) 📄 From RFC 3416 (SNMP Protocol Operations):

Section 4.2:

"The maximum size of an SNMP message is limited to the minimum of: (a) 484 octets (b) the maximum message size that the destination can accept"

This corresponds to: #define SNMP_MIN_MSG_SIZE 484

3) 📄 From RFC 3416 (SNMP Protocol Operations):

Page 9, section 4.1:

"A compliant implementation must support as many variable bindings in a PDU or BulkPDU as fit into the overall maximum message size limit of the SNMP engine, but no more than 2147483647 variable bindings."

This corresponds to: #define SNMP_MAX_PACKET_SIZE 0x7FFFFFFF = 2,147,483,647

Purpose: Message size limits for memory allocation and buffer management.

🔄 SNMP Version

// ==================== Protocol Version ====================
#define SNMP_VERSION_3 3 // SNMPv3

Purpose: This header focuses on SNMPv3 (the modern, secure version).

📨 PDU Types - SNMP Protocol Data Units

Modern Enum-Based Approach

// ==================== PDU Type Constants ====================
typedef enum {
    SNMP_PDU_GET = 0xA0,      // 160 - GetRequest
    SNMP_PDU_GETNEXT = 0xA1,  // 161 - GetNextRequest
    SNMP_PDU_RESPONSE = 0xA2, // 162 - Response
    SNMP_PDU_SET = 0xA3,      // 163 - SetRequest
    SNMP_PDU_GETBULK = 0xA5,  // 165 - GetBulkRequest
    SNMP_PDU_INFORM = 0xA6,   // 166 - InformRequest
    SNMP_PDU_TRAP2 = 0xA7,    // 167 - SNMPv2-Trap
    SNMP_PDU_REPORT = 0xA8    // 168 - Report
} SnmpPduType;

ASN.1 Encoding Explanation:

Context-specific tags: 0xA0-0xA8 range
Constructed types: All PDU types are constructed ASN.1 sequences
PDU type identifier: Lower nibble indicates specific PDU type

PDU Type	Value	Purpose
GET	0xA0	Retrieve specific variable values
GETNEXT	0xA1	Retrieve next variable in sequence
RESPONSE	0xA2	Response to any request
SET	0xA3	Modify variable values
GETBULK	0xA5	Efficient bulk data retrieval
INFORM	0xA6	Acknowledged notification
TRAPv2	0xA7	Unacknowledged notification
REPORT	0xA8	Error reporting between engines

⚙️ Internal Processing States

These are NOT network protocol values - they're internal state machine states for SET operation processing:

// ==================== Internal Processing States ====================
typedef enum {
    SNMP_STATE_SET_BEGIN = -1,
    SNMP_STATE_SET_RESERVE1 = 0,
    SNMP_STATE_SET_RESERVE2 = 1,
    SNMP_STATE_SET_ACTION = 2,
    SNMP_STATE_SET_COMMIT = 3,
    SNMP_STATE_SET_FREE = 4,
    SNMP_STATE_SET_UNDO = 5,

    SNMP_STATE_CHECK_VALUE = 17,
    SNMP_STATE_ROW_CREATE = 18,
    SNMP_STATE_UNDO_SETUP = 19,
    // ... etc
} SnmpProcessingState;

SET Operation State Flow:

RESERVE1 → RESERVE2 → ACTION → COMMIT → FREE
                    ↘ UNDO (if error)

Advanced Internal States:

CHECK_VALUE: Validate data before processing
ROW_CREATE: Dynamic row creation in tables
UNDO_SETUP: Prepare for potential rollback
IRREVERSIBLE_COMMIT: Changes cannot be rolled back

Purpose: These implement the transaction-like behavior for SNMP SET operations, allowing rollback on failure.

✅ Confirmed PDU Detection

// ==================== Confirmed PDU Detection ====================
static inline int snmp_is_confirmed_pdu(int pdu_type) {
    switch (pdu_type) {
    case SNMP_PDU_INFORM:
    case SNMP_PDU_GETBULK:
    case SNMP_PDU_GETNEXT:
    case SNMP_PDU_GET:
    case SNMP_PDU_SET:
        return 1;
    default:
        return 0;
    }
}

#define SNMP_CMD_CONFIRMED(c) snmp_is_confirmed_pdu(c)

Purpose: Identifies PDUs that require a response from the receiver.

Confirmed	Unconfirmed
GET, GETNEXT, GETBULK	TRAP
SET, INFORM	RESPONSE
(Expect response)	(No response expected)

❌ Exception Values (SNMPv2/v3)

// ==================== Exception Values ====================
typedef enum {
    SNMP_EXCEPTION_NO_SUCH_OBJECT = 0x80,   // 128
    SNMP_EXCEPTION_NO_SUCH_INSTANCE = 0x81, // 129
    SNMP_EXCEPTION_END_OF_MIB_VIEW = 0x82   // 130
} SnmpExceptionType;

Purpose: Special return values for variable binding exceptions.

Exception	Meaning
noSuchObject	Requested object doesn't exist
noSuchInstance	Requested instance doesn't exist
endOfMibView	No more variables in MIB tree

🚨 Error Status Codes

Modern Enum-Based Error Codes

// ==================== Error Codes ====================
typedef enum {
    SNMP_ERROR_NO_ERROR = 0,
    SNMP_ERROR_TOO_BIG = 1,
    SNMP_ERROR_NO_SUCH_NAME = 2,
    SNMP_ERROR_BAD_VALUE = 3,
    SNMP_ERROR_READ_ONLY = 4,
    SNMP_ERROR_GENERIC = 5,
    SNMP_ERROR_NO_ACCESS = 6,
    SNMP_ERROR_WRONG_TYPE = 7,
    // ... up to SNMP_ERROR_INCONSISTENT_NAME = 18
} SnmpErrorCode;

#define MAX_SNMP_ERROR SNMP_ERROR_INCONSISTENT_NAME

Error Validation Function

// ==================== Error Validation ====================
static inline SnmpErrorCode snmp_validate_error(int error_code) {
    if (error_code < SNMP_ERROR_NO_ERROR || error_code > MAX_SNMP_ERROR) {
        return SNMP_ERROR_GENERIC;
    }
    return (SnmpErrorCode)error_code;
}

#define SNMP_VALIDATE_ERR(x) snmp_validate_error(x)

Key Error Explanations:

NO_ACCESS: Authentication/authorization failure
AUTHORIZATION: VACM access control denial
INCONSISTENT_NAME: Row creation semantic error

Purpose: Sanitizes error codes to prevent invalid values.

Equivalent logic:

SnmpErrorCode validate_snmp_error(int error_code) {
    if (error_code > MAX_SNMP_ERROR) {      // More than 18
        return SNMP_ERROR_GENERIC;          // → 5
    } else if (error_code < SNMP_ERROR_NO_ERROR) {  // Less than 0
        return SNMP_ERROR_GENERIC;          // → 5
    } else {
        return (SnmpErrorCode)error_code;   // → as is
    }
}

🗃️ Row Status Values (For Table Operations)

// ==================== Row Management ====================
typedef enum {
    SNMP_ROW_NONEXISTENT = 0,
    SNMP_ROW_ACTIVE = 1,
    SNMP_ROW_NOT_IN_SERVICE = 2,
    SNMP_ROW_NOT_READY = 3,
    SNMP_ROW_CREATE_AND_GO = 4,
    SNMP_ROW_CREATE_AND_WAIT = 5,
    SNMP_ROW_DESTROY = 6
} SnmpRowStatus;

Purpose: Implements dynamic row creation/deletion in SNMP tables.

Usage Flow:

graph LR
    A[createAndGo] --> B[active]
    C[createAndWait] --> D[notInService] --> B
    B --> E[destroy] --> F[nonExistent]

💾 Storage Types

typedef enum {
    SNMP_STORAGE_NONE = 0,
    SNMP_STORAGE_OTHER = 1,
    SNMP_STORAGE_VOLATILE = 2,
    SNMP_STORAGE_NONVOLATILE = 3,
    SNMP_STORAGE_PERMANENT = 4,
    SNMP_STORAGE_READONLY = 5
} SnmpStorageType;

Purpose: Defines data persistence characteristics for MIB objects.

🛡️ Security Definitions (SNMPv3)

Modern Security Framework

// ==================== Security Framework ====================
#define SNMP_MP_MODEL_SNMPv3 3

typedef enum {
    SNMP_SEC_MODEL_ANY = 0,
    SNMP_SEC_MODEL_USM = 3,  // User-based Security Model
    SNMP_SEC_MODEL_TSM = 4   // Transport Security Model
} SnmpSecurityModel;

typedef enum {
    SNMP_SEC_LEVEL_NO_AUTH_NO_PRIV = 1,  // noAuthNoPriv
    SNMP_SEC_LEVEL_AUTH_NO_PRIV = 2,     // authNoPriv
    SNMP_SEC_LEVEL_AUTH_PRIV = 3         // authPriv
} SnmpSecurityLevel;

typedef enum {
    SNMP_MSG_FLAG_AUTH = 0x01,   // Message is authenticated
    SNMP_MSG_FLAG_PRIV = 0x02,   // Message is encrypted
    SNMP_MSG_FLAG_REPORT = 0x04  // Message is reportable
} SnmpMessageFlags;

Security Combinations:

// No security
flags = 0

// Authentication only
flags = SNMP_MSG_FLAG_AUTH

// Authentication + Encryption
flags = SNMP_MSG_FLAG_AUTH | SNMP_MSG_FLAG_PRIV

// Reportable message
flags = SNMP_MSG_FLAG_REPORT

🎛️ Control Flags (Implementation-Specific)

// ==================== Control Flags ====================
typedef enum {
    UCD_FLAG_RESPONSE_PDU = 0x100,
    UCD_FLAG_EXPECT_RESPONSE = 0x200,
    UCD_FLAG_FORCE_PDU_COPY = 0x400,
    UCD_FLAG_ALWAYS_IN_VIEW = 0x800,
    UCD_FLAG_PDU_TIMEOUT = 0x1000,
    // ... etc
} SnmpControlFlags;

Purpose: Internal implementation controls for message processing.

🌳 OID Base Definitions

// ==================== OID Base Definitions ===================
#define SNMP_OID_INTERNET 1, 3, 6, 1
#define SNMP_OID_ENTERPRISES SNMP_OID_INTERNET, 4, 1
#define SNMP_OID_MIB2 SNMP_OID_INTERNET, 2, 1
#define SNMP_OID_SNMPV2 SNMP_OID_INTERNET, 6
#define SNMP_OID_SNMPMODULES SNMP_OID_SNMPV2, 3

#define SNMP_ADMIN_STRING_LENGTH 255

OID Tree Structure:

1.3.6.1 (internet)
├── 2.1 (mib-2)
├── 4.1 (enterprises)
└── 6 (snmpV2)
    └── 3 (snmpModules)

🔧 Function Prototypes

Modern Function Declarations

// ==================== Function Declarations ====================
// Utility functions
NETSNMP_IMPORT char* snmp_uptime_to_string(unsigned long timeticks, char* buffer);
NETSNMP_IMPORT char* snmp_uptime_to_string_safe(unsigned long timeticks, char* buffer, size_t buffer_size);
NETSNMP_IMPORT void snmp_hex_dump(const void* data, size_t data_size, const char* prefix);

// ASN.1 BER encoding/decoding
NETSNMP_IMPORT unsigned char* snmp_decode_variable(
    unsigned char* input_data,
    unsigned int* object_id,
    size_t* object_id_length,
    unsigned char* value_type,
    size_t* type_length,
    unsigned char** value_data,
    size_t* value_length);

NETSNMP_IMPORT unsigned char* snmp_encode_variable(
    unsigned char* output_buffer,
    const unsigned int* object_id,
    size_t* object_id_length,
    unsigned char value_type,
    size_t value_length,
    const void* value_data,
    size_t* buffer_used);

Purpose: These functions implement the ASN.1 BER encoding/decoding for SNMP protocol data units.

🏁 Footer

#ifdef __cplusplus
}
#endif

#endif // SNMP_H

Purpose: Close the C++ extern "C" block and header guard.

📊 Summary

This modernized header provides:

Clean Protocol Constants - Enum-based PDU types, error codes, ports
SNMPv3 Security - Type-safe security models, levels, flags
Internal Processing - State machines for SET operations with proper types
ASN.1 Utilities - Encoding/decoding functions with clear parameter names
MIB Management - Row status, storage types, OID bases using modern C practices

Key Improvements:

✅ Replaced magic numbers with typed enums
✅ Replaced complex macros with inline functions
✅ Added proper parameter names to function declarations
✅ Improved readability and type safety
✅ Maintained backward compatibility with legacy macros

How It Works? (Super Briefly)

width="18804"
height="2464"
alt="Untitled diagram-2025-10-18-115602"
src="https://github.com/user-attachments/assets/905f9d59-bed6-468b-ab1a-08045f185ea2"
/>

🛡️ Security Levels (SNMPv3 Security Levels)

L31: noAuthNoPriv (Level 1)

#define SNMP_SEC_LEVEL_NOAUTH 1

What is it: Without authentication and encryption

How it works:

🤡 Anonymous access
Messages are not subscribed
🔓 Data is transmitted in clear text
💀 DANGEROUS! Only for test networks

L32: authNoPriv (Level 2)

#define SNMP_SEC_LEVEL_AUTHNOPRIV 2

What is it: Authentication without encryption
How it works:

✅ User verification (login/password)
🔐 HMAC-MD5 or HMAC-SHA for signature
📨 Data is NOT encrypted
Protection against spoofing, but the data is visible

L33: authPriv (Level 3)

#define SNMP_SEC_LEVEL_AUTHPRIV 3

What is it: Authentication + Encryption
How it works:

✅ User verification
🔐 Message signature
🚫 Data encryption (DES, AES)
💪 MAXIMUM PROTECTION

📨 PDU Types (Message Types)

Core Operations

E11: GET (160) - "Give the value of this variable"
E12: GETNEXT (161) - "Give the following variable in the MIB tree"
E14: SET (163) - "Change the value of a variable"
E13: RESPONSE (162) - "Reply to any request"

Advanced Operations

E21: GETBULK (165) - "Give a lot of data at once" (optimization)
E22: INFORM (166) - "Confirmation Notification"
E23: TRAPv2 (167) - "Notification without confirmation"
E24: REPORT (168) - "Error message between engines"

⚙️ Internal Processing (Internal SET Processing)

F1: SET State Machine - as a database transaction:

BEGIN → RESERVE1 → RESERVE2 → ACTION → COMMIT → FREE
                               UNDO (if an error occurs)

Why do I need to:

RESERVE1/RESERVE2 - booking resources
ACTION - making the change
COMMIT - confirm
UNDO - rollback if an error occurs
FREE - freeing up resources

❌ Exception Values

When the variable is not found:

H1: noSuchObject (128) - "There is no such object"
H2: noSuchInstance (129) - "There is no such instance"
H3: endOfMibView (130) - "There is nothing further in the tree"

🚨 Error Status Codes

Basic Errors

I11: noError (0) - Everything is ok
I12: tooBig (1) - The response is too big
I13: noSuchName (2) - Variable not found
I14: BadValue (3) - Incorrect value
I15: readOnly (4) - Attempt to change read-only
I16: genErr(5) - Common error

Extended Errors

I21: noAccess (6) - No access rights
I22: wrongType (7) - Incorrect data type
I23: wrongLength (8) - Wrong length
... etc. up to 18

🗃️ Row Status (Row statuses of tables)

For dynamic table management:

nonExistent → createAndWait → notInService → active → destroy
               createAndGo ────────────────┘

J1: nonExistent - The row does not exist
J4/J5: createAndWait/createAndGo - Create a string
J3: notInService - Created but not active
J2: active - Active and running
J7: destroy - Delete line

💾 Storage Types

How long does the data persist?:

K1: none - Is not saved at all
K3: volatile - In memory only (disappears after reboot)
K4: nonVolatile - Persists between reboots
K5: permanent - Cannot be deleted
K6: readonly - Read-only

🌳 OID Structure (Object Tree)

1.3.6.1 (internet)
├── 2.1 (mib-2) # Standard MIB objects
├── 4.1 (enterprises)     # Vendor extensions
6 (SNMPv2) # SNMPv2 features

Each variable in the network has a unique OID!

🔧 Core Functions

N11: uptime_string() - Converts time to beautiful text
N12: xdump() - Shows data in hex format
N21: snmp_parse_var_op() - Parses ASN.1 data
N22: snmp_build_var_op() - Creates an ASN.1 data

But these are all constants, let's go deeper into the work of snmp.

How SNMP Works ? (Super Briefly)

1. The basic architecture of SNMP

flowchart TD
    A[SNMP Manager] -->|UDP 161: GET/SET| B[SNMP Agent]
    B -->|UDP 162: TRAP/INFORM| A
    B --> C[MIB Database]
    C --> D[System Variables]
    C --> E[Network Interfaces]
    C --> F[IP Routing Tables]

Explanation:

SNMP Manager: The controlling system that initiates requests and receives notifications
SNMP Agent: The managed device (router, switch, server) that responds to requests
UDP 161: Port for Manager → Agent communication (GET/SET requests)
UDP 162: Port for Agent → Manager communication (TRAP/INFORM notifications)
MIB Database: Management Information Base - the database of managed objects
System Variables: Device information like system description, uptime, contact info
Network Interfaces: Interface statistics, status, configuration
IP Routing Tables: Routing information, neighbor relationships

2. The GET request process

sequenceDiagram
    participant M as SNMP Manager
    participant A as SNMP Agent
    participant D as MIB Database

    M->>A: GET 1.3.6.1.2.1.1.1.0
    A->>D: Lookup OID
    D->>A: Return: Linux Server 5.4.0
    A->>M: RESPONSE: Linux Server 5.4.0

Explanation:

SNMP Manager: Sends a GET request for a specific OID
GET 1.3.6.1.2.1.1.1.0: Request for system description (sysDescr.0)
SNMP Agent: Receives request and processes it
Lookup OID: Agent searches for the OID in its MIB database
MIB Database: Contains the actual values for all managed objects
Return: Linux Server 5.4.0: MIB returns the value for the requested OID
RESPONSE: Agent sends back the value to the Manager
Complete cycle: Shows the request-response pattern of SNMP operations

3. Types of SNMP messages

flowchart TD
    A[SNMP PDUs] --> B[Request Types]
    A --> C[Response Types]
    A --> D[Notification Types]

    B --> B1[GET<br/>Get specific variable]
    B --> B2[GETNEXT<br/>Get next variable]
    B --> B3[GETBULK<br/>Get multiple variables]
    B --> B4[SET<br/>Modify variable]

    C --> C1[RESPONSE<br/>Reply to request]

    D --> D1[TRAP<br/>Unsolicited notification]
    D --> D2[INFORM<br/>Acknowledged notification]

Explanation:

SNMP PDUs: Protocol Data Units - the message types in SNMP
Request Types: Messages sent from Manager to Agent
- GET: Retrieve a specific variable by OID
- GETNEXT: Get the next variable in MIB tree (for walking tables)
- GETBULK: Efficiently retrieve multiple rows from tables
- SET: Modify or write a variable value
Response Types:
- RESPONSE: Reply to any request, contains results or errors
Notification Types: Unsolicited messages from Agent to Manager
- TRAP: Unacknowledged notification (fire-and-forget)
- INFORM: Acknowledged notification (requires confirmation)

4. SNMP Security Levels

flowchart TD
    A[SNMPv3 Security] --> B[noAuthNoPriv<br/>No security]
    A --> C[authNoPriv<br/>Authentication only]
    A --> D[authPriv<br/>Auth + Encryption]

    B --> B1[No password<br/>Community string]
    C --> C1[HMAC-MD5/SHA<br/>Message integrity]
    D --> D1[DES/AES<br/>Data encryption]

Explanation:

SNMPv3 Security: The security framework introduced in SNMP version 3
noAuthNoPriv: No authentication, no encryption (least secure)
- Community string: Plain text password like "public" or "private"
authNoPriv: Authentication but no encryption
- HMAC-MD5/SHA: Hash-based Message Authentication Codes for verifying message integrity
- Provides identity verification but data is sent in clear text
authPriv: Both authentication and encryption (most secure)
- DES/AES: Data encryption standards to protect message confidentiality
- DES: Data Encryption Standard (older)
- AES: Advanced Encryption Standard (modern, recommended)

🎯 How does SNMP work in practice:

Manager

# Device request
snmpget -v 2c -c public 192.168.1.1 1.3.6.1.2.1.1.1.0

# Response
SNMPv2-MIB::sysDescr.0 = STRING: Cisco IOS Software, Version 15.1

Explanation:

snmpget: Command-line tool to send GET requests
-v 2c: SNMP version 2c (community-based security)
-c public: Community string "public" (like a password)
192.168.1.1: IP address of the SNMP agent
1.3.6.1.2.1.1.1.0: OID for system description
Response format: MIB::object = TYPE: value

Agent - Code

// The pseudo-code of the SNMP agent
while(1) {
// Waiting for a request on port 161
    packet = recvfrom(udp_socket);

    // Parsing the SNMP package
    pdu = parse_snmp_packet(packet);

    // Processing the request
    switch(pdu->type) {
        case GET:
            value = mib_lookup(pdu->oid);
            send_response(value);
            break;
        case SET:
            mib_update(pdu->oid, pdu->value);
            send_response(SUCCESS);
            break;
    }
}

Explanation:

Infinite loop: Agent continuously listens for requests
recvfrom(udp_socket): Receives UDP packets on port 161
parse_snmp_packet(): Decodes SNMP message (ASN.1 BER encoding)
pdu->type: Determines the type of request (GET, SET, etc.)
mib_lookup(): Searches for OID in the Management Information Base
mib_update(): Modifies variable value for SET operations
send_response(): Sends back the response to the manager

MIB Database

// Example of MIB variables
struct mib_entry {
oid: "1.3.6.1.2.1.1.1.0", // sysDescr
    type: STRING,
    value: "Linux Server 5.4.0",
    access: READ_ONLY
}

struct mib_entry {
    oid: "1.3.6.1.2.1.2.2.1.10.1", // ifInOctets.1
    type: COUNTER32,
    value: 154729,
    access: READ_ONLY
}

Explanation:

mib_entry: Structure representing one managed object
oid: Object Identifier - unique address in the MIB tree
- "1.3.6.1.2.1.1.1.0" = system.sysDescr.0 (system description)
- "1.3.6.1.2.1.2.2.1.10.1" = interfaces.ifInOctets.1 (input octets on interface 1)
type: Data type of the object
- STRING: Text data
- COUNTER32: Monotonically increasing counter (32-bit)
value: Current value of the object
access: Permission level
- READ_ONLY: Can only be read, not modified
- READ_WRITE: Can be both read and modified

🔥 Key points:

Manager - Initiates requests (GET, SET) and receives notifications
Agent - Responds to requests, sends traps/informs
MIB - Database of managed variables with hierarchical OID structure
OID - Unique addresses of variables in dotted decimal notation
PDUs - Message Formats for different types of SNMP operations
Security - Protection Levels (v3) providing authentication and encryption

In fact: SNMP allows remote control of network devices via a standardized protocol! 🌐

Static Single Assignment Form (SSA)

dima853 — Tue, 18 Aug 2026 17:43:24 +0000

Static Single Assignment Form (SSA) and Its Role in Compiler Optimizations

Abstract

Static Single Assignment (SSA) form is an intermediate representation of programs in which each variable is assigned a value only once. Developed in the 1980s by IBM researchers, this form has become a fundamental basis for most modern optimizing compilers, including LLVM, GNU Compiler Collection, and commercial compilers. This article discusses the principles of SSA, its advantages for compiler optimizations, as well as its connection with Escape Analysis and related optimizations such as stack allocation and scalar replacement.

Introduction

In traditional intermediate representations, variables can be reassigned multiple times, which complicates data flow analysis and the execution of optimizations. SSA solves this problem by introducing a rule: each variable is assigned a value exactly once. To achieve this, original variables are split into versions, typically denoted by the original name with a subscript. At control flow merge points, where different versions of a variable may reach a single point, special Φ-functions are introduced to select the appropriate version based on the execution path.

Historical Background

SSA was developed in the 1980s by IBM researchers, including Kenneth Zadeck. In 1986, the concept of birthpoints and variable renaming to ensure single static assignment was presented. In 1988, Barry Rosen, Mark Wegman, and Kenneth Zadeck introduced the term "Static Single Assignment form" and replaced identity operations with Φ-functions. An efficient algorithm for converting programs to SSA form was presented in 1989.

Advantages of SSA Form

Simplification of Data Flow Analysis

SSA form significantly simplifies data flow analysis because each use of a variable has a single definition. For example, in the code:

y := 1
y := 2
x := y

in SSA form it becomes clear that the value of y used in the third line comes from the second assignment:

y₁ := 1
y₂ := 2
x₁ := y₂

Optimizations Enhanced by SSA

Constant folding — evaluating expressions at compile time
Value range propagation — determining possible values of variables
Dead-code elimination — removing instructions that do not affect the result
Global value numbering — detecting redundant computations
Partial-redundancy elimination — eliminating duplicate computations

Connection with Escape Analysis

Principles of Escape Analysis

Escape Analysis determines whether references to objects can escape beyond a specific execution context. An object is considered "escaped" if it can be referenced from another thread, method, or external context after the method completes.

Interaction of SSA and Escape Analysis

SSA form simplifies Escape Analysis by making data flows explicit. In SSA, each object is created at a specific point, and all uses refer to a particular version. This allows precise tracking of whether references to an object are passed to potential escape points.

Example of using SSA for escape analysis:

// Original code
Object process() {
    Object local = new Object();  // Object creation
    return helper(local);          // Passing the reference
}

// SSA form:
local₁ = new Object()
result₁ = helper(local₁)
return result₁

In SSA form, it is explicit that local₁ is passed to the helper function, which allows analysis of whether helper can store this reference.

Optimizations Based on SSA and Escape Analysis

Stack Allocation

When escape analysis shows that an object does not leave the method, the compiler can place it on the stack frame instead of the heap. This eliminates the overhead of dynamic memory management and garbage collection.

Transformation to SSA allows precise determination of the object's lifetime:

// Without optimization (heap)
void example() {
    Point p = new Point(1, 2);  // Allocation on the heap
    use(p);
}

// With optimization (stack)
void example_optimized() {
    // In SSA: p₁.x = 1, p₁.y = 2
    // Fields are placed on the stack
    use(1, 2);
}

Scalar Replacement

Objects that do not escape can be decomposed into individual scalar variables. SSA form facilitates this transformation because each variable already has a single definition.

Example of scalar replacement:

// Original code
void compute() {
    Rectangle rect = new Rectangle(10, 20, 100, 200);
    int area = rect.width * rect.height;
}

// After scalar replacement (in SSA form):
void compute() {
    rect_width₁ = 100
    rect_height₁ = 200
    area₁ = rect_width₁ * rect_height₁
}

Algorithmic Aspects of SSA

Dominance and Dominance Frontiers Calculation

The concept of dominance frontiers is used for correct insertion of Φ-functions. Node A dominates node B if every path from the entry to B passes through A. The dominance frontier of node A is the set of nodes where A does not dominate directly but dominates an immediate predecessor.

The dominance frontier calculation algorithm proposed by Keith Cooper et al. efficiently determines the insertion points for Φ-functions.

Minimal and Pruned SSA

To reduce the number of Φ-functions, variants of SSA are used:

Minimal SSA — inserts only necessary Φ-functions
Pruned SSA — considers variable liveness, excluding Φ-functions for dead variables
Semi-pruned SSA — excludes Φ-functions for variables that are not live upon entry to a basic block

Practical Application in Compilers

Compilers with SSA Support

LLVM — uses SSA for all scalar values until the register allocation phase
GCC — applies SSA in the GIMPLE intermediate representation
HotSpot JVM — uses SSA in its JIT compiler
V8 JavaScript Engine — implements SSA in the Crankshaft compiler

Example of Optimizations in LLVM

LLVM uses SSA form to represent the program until the register allocation phase. This enables aggressive optimizations such as:

Escape Analysis to determine the possibility of stack allocation
Scalar replacement of objects
Synchronization removal for objects accessible to only one thread

Extensions of SSA Form

Static Single Use Form

In this form, variables are renamed at each use, which is useful for lazy evaluation analysis.

Static Single Information Form

Variables are renamed upon assignment and at post-dominance frontiers, providing more precise information about values.

Extensions for Specific Capabilities

SSA modifications allow modeling high-level programming language constructs (arrays, objects, pointer aliases) and low-level architectural features (speculative execution, predication).

Conclusion

Static Single Assignment form is a powerful tool for compiler optimization. Its ability to explicitly represent data flows significantly simplifies program analysis and the execution of optimizations, including escape analysis, stack allocation, and scalar replacement. The development of SSA and related technologies continues to be an active area of research in compiler construction, contributing to the creation of more efficient and performant programming systems.

The interaction of SSA form with modern optimization techniques demonstrates how fundamental concepts of compiler theory find practical application in real systems, providing significant performance gains while maintaining the semantic correctness of programs.

Steganography

dima853 — Tue, 18 Aug 2026 17:42:57 +0000

Steganography is the science and practice of hiding the fact that information is being transmitted, not the information itself (that's cryptography).

The same image viewed by white, blue, green, and red lights reveals different hidden numbers.

Definition

If cryptography is like sending a note in a safe that everyone sees but can't open (or in an incomprehensible language that everyone hears but doesn't understand), then steganography is like writing with invisible ink on the back of a regular postcard. The modern goal is not necessarily to achieve absolute invisibility, but to ensure that the stego-container is statistically indistinguishable from legitimate noise and doesn't attract targeted attention.

How It Works in Practice (Techniques)

The principle is always the same: hide a data container inside another, harmless carrier container without causing statistically significant anomalies.

1. In Images (Most Popular Method)

Basic Method: Replacing Least Significant Bits (LSB).
How it works: Each pixel's color is encoded with numbers (e.g., in RGB). Changing the least significant bit alters the color by such a small amount that the human eye won't notice.
Example: You want to hide the letter 'A' (ASCII code 65, which is 01000001 in binary) in 8 pixels. You replace the least significant bit of each pixel with one bit from the message.
Naive LSB replacement is a vulnerable and easily detectable method through statistical analysis (histogram analysis, Chi-square tests). Modern adaptive methods (e.g., syndrome coding, spreading across multiple bit planes) actively combat anomalies. Basic LSB is used only for Proof-of-Concept or against incompetent adversaries.

1) Histogram Analysis

What it is: A graphical representation of the distribution of values (e.g., pixel colors in an image).
Purpose in steganalysis: To detect statistical anomalies that arise after data embedding.
How it works:
- A "clean" image has a smooth, continuous histogram.
- Naive LSB method creates characteristic "steps" or paired values in the histogram because when replacing the least significant bit, pairs of values (0 and 1, 2 and 3, etc.) become almost equally probable. This is easily noticeable visually on a graph.

2) Chi-square Test (χ²)

Chi-squared distribution, showing χ2 on the first axis and p-value (right tail probability) on the second axis.

1. What is `k` (Degrees of Freedom)

In simple terms: k is a parameter that indicates the "complexity" or "dimensionality" of our analysis.

In the context of steganalysis (LSB checking):

Imagine we're analyzing an image's histogram.
We look at pairs of values (0 and 1, 2 and 3, 4 and 5, etc.) that might have aligned due to LSB replacement.
k is the number of such pairs we're checking.
The larger k, the more data we're analyzing.

On the graph: Each line (k=1, k=2, etc.) is a separate Chi-square distribution for a different number of degrees of freedom. Notice that as k increases, the curve "flattens" and shifts to the right. (need to look "from the side of zero" (left to right))

2. What is `p-value` (Probability / Significance Level)

In simple terms: p-value is the probability that the result we observed (alignment of pairs in the histogram) occurred by chance.

In the context of steganalysis:

High p-value (close to 1): High probability that the histogram looks like this simply by chance. Conclusion: Steganography is likely NOT present.
Low p-value (close to 0): It's extremely unlikely that such perfect alignment of pairs happened by chance. Conclusion: The file likely contains hidden data embedded using the LSB method.

On the graph: p-value is shown on the vertical axis as "right tail probability". When our calculated Χ² value falls far into the right "tail" of the distribution (shaded area), the p-value becomes very small. (p-value is determined by the horizontal axis (X²) from right to left, not by the vertical axis)

Simply put:

Histogram analysis is "look at the graph and see suspicious patterns".
Chi-square test is "calculate and get a number proving the file is suspicious".

3) Syndrome Coding

Essence: This is not a data embedding method, but a matching method. It allows embedding a message without changing some bits of the carrier.

Left Column: Syndromes (S)

These are all possible syndromes (3-bit checksums) that can be computed from a 7-bit block.

Right Column: "Coset Leaders" (e)

These are minimum weight error vectors (with the minimum number of ones) corresponding to each syndrome.

Note: Each vector e contains only one one - this is the minimal possible change!

The table shows the minimal impact needed to obtain the desired "fingerprint" (syndrome).

How This Works in Steganography (briefly):

STEP 1: Preparation

We have a cover block (7 bits from the image): C
We have a message (3 bits) we want to hide: M

STEP 2: Compute syndrome of the cover block

Compute the syndrome of the cover block: S_cover = H × C (where H is the parity-check matrix)
In the table, this corresponds to finding the syndrome S_cover

STEP 3: Compare syndromes

If S_cover = M → Already matches! Change nothing. Use e0 = (0,0,0,0,0,0,0)
If S_cover ≠ M → Need to find an error vector e to change the syndrome

STEP 4: Find error vector

Look in the table for a syndrome S equal to our target message M
Take the corresponding coset leader e

STEP 5: Embedding

Modify the cover block: C_stego = C + e
Now the syndrome of the new block: S_stego = H × (C + e) = H×C + H×e = S_cover + S = M
Advantage: Drastically reduces the number of carrier modifications. Ideally, only 1 bit per block is changed, making attacks based on LSB replacement statistics practically useless.

Spreading Across Multiple Bit Planes

Essence: Abandoning the naive approach where data is hidden only in the 1st least significant bit (LSB). Instead, the message is "spread" across several least significant bit planes.
How it works:
1. A pixel image can be represented as a "stack" of bit planes: from the most significant to the least significant.
2. Naive LSB uses only the bottommost plane.
3. Modern methods (e.g., HOLMES) embed data simultaneously into the 1st, 2nd, and sometimes 3rd bit planes, adapting the embedding depth to the image texture.
4. In complex textures (noise, grass), even higher-order bits can be changed, as the eye won't notice. In smooth areas (sky) — only the least significant ones.
Advantage: Drastically increases capacity and, more importantly, resistance to steganalysis. Statistical anomalies arising from replacing only the 1st LSB are blurred and become indistinguishable from the image's natural noise.

Bit Planes

Basic Concept

A bit plane of a digital discrete signal (such as an image or sound) is a set of bits corresponding to a specific bit position in each of the binary numbers representing the signal.

Simple example:
For 16-bit data representation, there are 16 bit planes:

The first bit plane contains the set of most significant bits (MSB)

The sixteenth contains the least significant bits (LSB)

The 8 bit-planes of a gray-scale image (the one on left). There are eight because the original image uses eight bits per pixel.

Significance of Bit Planes

It can be observed that:

The first bit plane gives the coarsest but most critical approximation of the medium's values
The higher the number of the bit plane, the less its contribution to the final result

Thus, adding each subsequent bit plane gives a better approximation to the original value.

Mathematical Contribution of Bit Planes

If a bit in the n-th bit plane in an m-bit dataset is set to 1, it contributes a value of 2^(m−n), otherwise it contributes nothing. Therefore, bit planes can contribute half the value of the previous bit plane.

Example with the 8-bit value 10110101 (181 in decimal):

Bit Plane	Value	Contribution	Cumulative Total
1st	1	1 × 2⁷ = 128	128
2nd	0	0 × 2⁶ = 0	128
3rd	1	1 × 2⁵ = 32	160
4th	1	1 × 2⁴ = 16	176
5th	0	0 × 2³ = 0	176
6th	1	1 × 2² = 4	180
7th	0	0 × 2¹ = 0	180
8th	1	1 × 2⁰ = 1	181

Technical Note

The term "bit plane" is sometimes used as a synonym for "bitmap", however technically:

The former refers to the location of data in memory
The latter refers to the data itself

Noise Analysis in Bit Planes

One aspect of using bit planes is determining whether a bit plane is random noise or contains meaningful information.

Calculation method:
Compare each pixel (X, Y) with three neighboring pixels:

(X − 1, Y)
(X, Y − 1)
(X − 1, Y − 1)

If a pixel matches at least two of the three neighboring pixels, it is not considered noise.

Criterion: A noisy bit plane will have between 49% to 51% of pixels that are noise.

Applications of Bit Planes

1) Media File Formats

Using PCM audio as an example:

The first bit in a sample denotes the sign of the function (determines half of the entire amplitude range)
The last bit determines the exact value

Important principle:

Changing more significant bits leads to greater distortion
Changing less significant bits is less critical

In lossy media compression using bit planes, this allows more freedom for encoding less significant bit planes, while more significant ones must be preserved as accurately as possible.

Pulse Code Modulation (PCM)

Pulse-code modulation (PCM) is used to digitize analog signals. Virtually all types of analog data (video, audio (voice, music), telemetry) allow the use of PCM.

PCM is like "digitizing" sound or any other analog signal for use in the digital world. Without PCM, we couldn't store music on computers or transmit voice over the internet.

Example of 4-bit (16-level) PCM. Shows quantization of an analog signal and bursts of impulses encoding the samples. Transmission in the channel is performed with the most significant bits first.

Modulation

Example of 4-bit (16-level) PCM. Shows quantization of an analog signal and bursts of impulses encoding the samples. Transmission in the channel is performed with the most significant bits first.

PCM Operating Principle

In pulse-code modulation, the analog transmitted signal is converted into digital form through three operations:

Time sampling (measuring the analog signal at equal time intervals (obtaining samples))
Amplitude quantization (rounding each sample to the nearest level from a finite set of values)
Encoding

Converting Analog Signal to Digital

An analog-to-digital converter (ADC) is used to convert an analog signal to digital. The ADC measures the amplitude of the analog signal at equal intervals - obtains instantaneous values or signal samples, then converts the samples into binary words.

The measured instantaneous value (sample) of the analog signal is quantized by levels (rounded to the nearest integer). The number of quantization levels is usually equal to or a multiple of an integer power of 2, for example:

2³ = 8 levels
2⁴ = 16 levels
2⁵ = 32 levels

The level number is encoded with binary words of length 3, 4, 5, etc. bits.

Forming Signal for Transmission

Then the ADC's output words in parallel code are encoded by feeding them to a shift register clocked by an auxiliary shift generator. At the output of the shift register, bursts of encoded impulses in serial code are formed. Then the impulse bursts are transmitted into the communication channel.

Note: An impulse burst is periodically repeating impulses over a fixed time interval.

Sampling Frequency

The signal sampling frequency (or digitization rate, sampling frequency) to avoid information loss, according to the Nyquist–Shannon sampling theorem, must be at least twice the maximum frequency in the analog signal's spectrum.

Technical Implementation

There are specialized integrated circuits designed for PCM, combining ADC, shift register, clock generators, and other devices.

Demodulation

A demodulator is installed at the receiving end of the communication channel. In the demodulator, impulse bursts are fed to the serial input of a shift register. After shifting all bits of the impulse burst into the shift register, the word from the shift register in parallel code is written to the input register of a digital-to-analog converter (DAC).

The DAC converts the encoded samples of the transmitted analog signal back into analog form. A stepped analog signal is formed at the DAC output. Smoothing of the steps is performed by a low-pass filter (LPF), at the output of which the transmitted analog signal is formed. The LPF cutoff frequency is chosen to be less than or equal to twice the sampling frequency.

Digital Codes in PCM

A wide variety of binary codes are used to encode samples in PCM:

Ordinary representation of numbers in the binary numeral system, with sequential transmission of bits of the binary number can be done either least significant bits first or most significant bits first
Various codes with error detection and correction in the transmission channel, for example, Hamming code, Reed–Solomon code, etc. The simplest of them is a redundant code with parity bit transmission
Codes that eliminate the DC component in the encoded two-level impulse signal, for example, self-synchronizing Manchester code

PCM Variants

Differential Pulse-Code Modulation (DPCM)

PCM combined with delta encoding, where the signal is encoded as the difference between the current and previous measured values. For audio data, this modulation method reduces the required number of bits per sample by about 25%.

Adaptive DPCM (ADPCM) — a variant of DPCM with variable quantization step size. Changing the step size allows reducing bandwidth requirements for a given signal-to-noise ratio.

LPCM (Linear pulse code modulation)

Linear pulse-code modulation.

Practical Application

In digital and IP telephony, PCM is used to convert voice audio signals into a digital stream transmitted at 64 kbit/s (primary digital channel)
PCM is used to convert analog audio signals to digital for storing signals on digital devices and media (digital audio recording). File formats: WAV, MP3, WMA, OGG, FLAC, APE
PCM was previously used in modem communication protocols ITU V.90 (only incoming signal to the client) and V.92 (incoming and outgoing signal) to provide a maximum connection speed of 56 kbit/s

2) Raster Displays

Some computers displayed graphics in bit plane format, specifically:

PCs with EGA video cards
Amiga
Atari ST

This contrasted with the more common packed format. This organization allowed performing certain classes of image operations using bitwise operations (especially with the blitter chip), as well as creating parallax scrolling effects.

3) Motion Estimation in Video

Some motion estimation algorithms can be performed using bit planes (e.g., after applying a filter to convert salient edge features into binary values).

This can sometimes provide a good enough approximation for correlation operations with minimal computational cost. This method is based on the observation that spatial information is more significant than actual values.

Technical detail:
Convolutions can be reduced to bit shift and popcount operations, or performed in specialized hardware.

4) Neural Networks

Bit plane formats can be used to feed images into:

Spiking neural networks
Neural networks/convolutional neural networks with low-precision approximations

5) Software

Many image processing packages can split an image into bit planes. Open-source tools include:

Pamarith from the Netpbm package
Convert from ImageMagick

2. In Audio and Video

Same principle: Making changes imperceptible to human hearing/vision in the audio track (masking in critical hearing bands, modifying phase spectrum) or in video frames. For example, adding quiet echo signals with specific delays that encode information.

3. In Text

Methods: Changing the number of spaces or tabs (difficult to detect visually but trivially revealed by analyzing source code), using invisible Unicode characters (Zero-Width Joiner, Zero-Width Non-Joiner), algorithmic synonymization.
Most primitive historical example: Pricking specific letters in text with a pin that form a secret message.

4. In Network Traffic (Network Steganography)

Methods: Hiding data in service fields of network packet headers (e.g., in IP ID, TTL field, or flags), in the time delay between packets (timing channels), or in "empty" TCP segments.
This is especially dangerous because detecting such traffic with standard protection tools (firewalls, IDS) is almost impossible, especially inside an encrypted channel (HTTPS), which hides the stego-carrier itself from deep packet inspection.

Steganography vs Cryptography

Parameter	Cryptography	Steganography
Main Goal	Hide the CONTENT of the message	Hide the VERY FACT of the message's existence
If Discovered	Enemy knows about the existence of a secret message. Its content (hopefully) is protected.	COMPLETE FAILURE. The very concept of secrecy is destroyed.
Attention	Can attract attention (encrypted correspondence is suspicious by itself)	Avoids attention (looks like normal traffic)
Protection	Mathematical strength of algorithms and key length	Statistical indistinguishability from the original carrier and resistance to steganalysis

Important conclusion: In serious systems, they are combined. First, the message is encrypted (cryptography), then hidden in a carrier (steganography). This way, even if the enemy discovers the hidden data, they cannot read it.

Real Threats and Applications

1. Cyber Espionage and APT Attacks

How it's used: Malware steals data and exfiltrates it, disguising it as normal traffic. Common scheme: data is hidden in an image uploaded to a public resource (forum, GitHub, cloud), and the malware on the compromised machine downloads it. Encrypted HTTPS connection hides the stego-carrier from inspection.

2. Circumventing Censorship in Totalitarian Regimes

How it's used: Activists and journalists use steganography to transmit information through blocked channels without attracting the attention of censors who look for keywords in plain text.

3. Concealing Criminal Activity

How it's used: Criminal communities exchange instructions and data by hiding them in files posted on public forums and cloud storage. Important clarification: using social media is problematic as they often recompress images, destroying the stego-container.

4. Digital Watermarks (the other side)

This is a legal application: Copyright holders embed invisible marks into their content to confirm authorship and track leaks. This is steganography where the goal is not to hide the fact of transmission, but to hide the mark itself until the moment of verification.

Detection (Steganalysis)

Steganalysis is the art of detecting steganography.

Methods: Statistical analysis of the carrier file for anomalies (histogram analysis, Chi-square tests), entropy analysis, searching for traces of specific steganography tools, machine learning to identify patterns.
Hard truth: A universal detector does not exist. Detection is difficult and often impossible without a hypothesis about the method used. However, against specific, known methods (like naive LSB), steganalysis can be highly effective. Channel capacity is low, but it's sufficient for transmitting keys, passwords, or control commands.

Final Verdict

Steganography is a powerful, dangerous, and often underestimated tool. In the cybersecurity arsenal, it represents a persistent and hard-to-detect threat because an attack based on it is practically invisible against the background of legitimate traffic. This is not a "zero-day vulnerability", but a fundamental technique leading to an eternal battle between concealment and detection methods. For an infosec specialist, understanding steganography is not an option but a necessity, especially during incident investigation and defense against targeted attacks.

Transaction Processing or Analytics?

dima853 — Tue, 18 Aug 2026 17:42:19 +0000

Introduction to Transactions

In the early days of business data processing, writing to a database typically corresponded to a commercial transaction: selling a product 🛍️, ordering from a supplier 📦, paying employee salaries 💰, etc. Over time, the term "transaction" became established even for operations not related to money and came to mean a group of read and write operations forming a logical unit.

💥 Atomicity — the minimum mandatory property of any transaction

🛡️ Full ACID — part of reliability for critical operations

⚖️ In practice — different systems choose a balance between reliability (ACID) and performance (weakened guarantees)

🔄 OLTP vs OLAP: Two Different Worlds

Online Transaction Processing (OLTP) — a type of database system used in transaction-oriented applications (banks, accounting systems (ERP, CRM), booking systems, payment systems, etc.), such as many operational (core) business systems.

Two contexts where the term "transaction" is often used:

Type 1: Computer Transactions 💻

Atomic data modification in a database
Example: BEGIN TRANSACTION → UPDATE → COMMIT

Type 2: Business Transactions 💰

Economic exchange between parties
Example: product sale, bank transfer

How they're related:
OLTP uses technical transactions (type 1) to record business operations (type 2).

For example:

💳 Store purchase (business transaction)
is recorded via 🖥️ SQL transaction in the database

In short: Technical transactions = tool for recording business transactions 🔧→📊

OLTP (Online Transaction Processing)

Even when databases started being used for various types of data (blog comments 📝, game actions 🎮, contacts in address books 👥, etc.), the main access model remained similar to business transaction processing.

OLTP Characteristics:

Searching for a small number of records by key 🔑
Inserting and updating data based on user input
Interactive mode of operation

C Example:

// Example OLTP operation: finding customer information by ID
#include <stdio.h>
#include <string.h>

struct Customer {
    int id;
    char name[50];
    double balance;
};

struct Customer find_customer_by_id(int customer_id) {
    // In a real system, there would be a database query here
    struct Customer customer;
    customer.id = customer_id;
    strcpy(customer.name, "Ivan Ivanov");
    customer.balance = 15000.75;
    return customer;
}

OLAP (Online Analytic Processing)

Online Analytical Processing (OLAP) — an approach for quickly answering multidimensional analytical queries.

Databases also started being used for data analytics, which implies a completely different access model.

*Data Warehousing
*OLAP Cube (from Online Analytical Processing) — a multidimensional data structure designed for fast and efficient analysis of large volumes of business data from various perspectives.
In simple terms, an OLAP cube can be compared to a pivot table in Excel, but much more powerful and capable of working with huge amounts of information and multiple parameters (dimensions).

Let's Look at OLAP-CUBE

OLAP data is typically stored in "star" or "snowflake" schemas in a relational data warehouse or specialized data management system. Metrics are derived from records in the fact table, and dimensions are from dimension tables.
but!
Classic OLAP cubes (like in Microsoft Analysis Services) often store data in proprietary multidimensional formats, not in relational "star" tables. The "star" itself is the raw data storage schema on which the cube is built. Additionally, modern MPP systems (Massively Parallel Processing) like ClickHouse or Amazon Redshift often don't use cubes in the classical sense but provide similar speed for OLAP queries directly to relational tables.

🧊 OLAP Cube (Data Cube)

🎲 The term "cube" refers to a multidimensional dataset sometimes called a hypercube if the number of dimensions is more than three.

Basic Concepts:

📦 Cube — a multidimensional generalization of a two-dimensional spreadsheet

# Example: 3D data cube
dimensions = ['Products', 'Time', 'Regions']
measures = ['Sales', 'Profit', 'Budget']

Slice

Slice - the process of selecting a rectangular subset of a cube by choosing a single value for one of its dimensions, creating a new cube with one less dimension.
The figure shows the slicing operation: sales metrics in all sales regions and all product categories of the company for 2005 and 2006 are "cut out" from the data cube.

Dice

Dice: The dice operation creates a subcube allowing the analyst to select specific values from multiple dimensions.
The figure shows the dice operation: the new cube displays sales data for a limited number of product categories, with time and region dimensions covering the same range as before.

Drill Down/Up

Drill down/up allows the user to navigate between data levels, from the most summarized (up) to the most detailed (down).
The figure shows the drill-down operation: the analyst moves from the summary category "Outdoor Protective Equipment" to sales metrics of individual products.

Roll-Up

Roll-up involves summarizing data along a dimension. The summarization rule can be an aggregate function, for example, to calculate totals along a hierarchy or apply a set of formulas such as "profit = sales - expenses". 📊💰

Computational Complexity

Common aggregate functions can be expensive to compute when rolling up: ❌

🐌 If they cannot be defined from the cube cells, they must be computed from the underlying data
⏳ Either compute them online (slowly)
💾 Or precompute them for possible roll-up (large volume)

✅ Efficient Aggregate Functions

Aggregate functions that can be defined from cells are known as decomposable aggregate functions and allow efficient computation.

💰 Cost of Aggregate Functions When Rolling Up

❌ Problematic Functions (expensive to compute):

📊 Median (MEDIAN)

Requires complete data sorting for each aggregation level
Lacks the composability property - median of subgroups ≠ median of entire group
On-the-fly computation requires storing all original values

🎯 Percentiles (PERCENTILE)

Similar to median, require access to the entire dataset
90th percentile cannot be computed from 90th percentiles of subgroups
Must store the complete data distribution

🔢 Mode (MODE)

Requires counting frequencies of all values
The most frequent value in subgroups may not match the overall mode
Requires complete recount for accurate determination

📈 Standard Deviation (STDDEV)

Not an additive function (In the context of aggregate functions, "additivity" means the ability to compute the overall result from partial results.)
Requires knowing the mean value and number of elements
For accurate calculation, need ∑x and ∑x² for all data

Examples:

✅ Easily supported:

COUNT 🔢
MAXIMUM ⬆️
MINIMUM ⬇️
SUM ➕

Because they can be computed for each OLAP cube cell and then rolled up, since the total sum (or count, etc.) is the sum of sub-sums.

❌ Difficult to support:

MEDIAN 📊

Because it must be computed for each view separately: the median of a set is not the median of medians of subsets.

🔢 Mathematical Definition

(simplified) Mathematically, an OLAP cube is a projection of an RDBMS relation:

f: (X, Y, Z) → W

Where:

X, Y, Z — cube axes (dimensions) 📐
W — data filling each cell 💾

Projection example:

g: (Product, Time) → Sales

💾 Data Storage

OLAP data is typically stored in:

🌟 Star Schema
❄️ Snowflake Schema
🗄️ Specialized data management systems

Explanation (briefly)

🌟 Star Schema

Denormalized schema
All dimension tables linked DIRECTLY to the fact table
Simpler and faster for queries
Easier to understand

❄️ Snowflake Schema

Normalized schema
Dimension tables SPLIT into sub-tables
More complex, but saves space
Slower due to more JOINs

What this means in practice:

Star → for analysis speed 📊⚡
Snowflake → for storage economy 💾📉

Practical Examples

💼 Business Intelligence:

# Business cube dimensions:
dimensions = [
    'Products 📦',
    'Time 📅',
    'Regions 🌍',
    'Sales_Channels 🏪',
    'Customers 👥'
]

# Measures (metrics):
measures = [
    'Sales_Volume 💰',
    'Profit 📈',
    'Order_Count 🔢',
    'Average_Check 💵'
]

🏪 Retail Example:

Cube: "Store Sales"
├── Dimensions:
│   ├── Time: Year → Quarter → Month → Day
│   ├── Products: Category → Brand → Model
│   ├── Stores: Region → City → Address
│   └── Customers: Segment → Demographics
└── Measures:
    ├── Sales Amount
    ├── Quantity Sold
    ├── Profit
    └── Returns

🔗 Related Technologies

🌐 Business Intelligence:

📊 Data Mining — data mining
🏪 Data Mart — data marts
📈 MDX — Multidimensional Expressions
🔍 XML for Analysis

🛠️ Popular OLAP Systems:

Microsoft Analysis Services
Oracle OLAP
Apache Kylin
ClickHouse

💡 Key Advantages of OLAP Cube

Advantage	Description
⚡ Fast Response	Instant answers to complex analytical queries
🔍 Multidimensionality	Data analysis from different perspectives
📊 Flexibility	Interactive data exploration
🎯 Intuitiveness	Visualization understandable to business users

📋 Comparison Table: OLTP vs OLAP

OLTP is typically contrasted with Online Analytical Processing (OLAP):

Characteristic	OLTP 🚀	OLAP 📊
Query Types	All types (read, insert, update, delete)	Mostly read-only
Complexity	Simple queries	Complex analytical queries
Volume	Large number of simple queries	Smaller number of complex queries
Purpose	Operation processing	Business analytics and reporting

🏢 Data Warehousing

Why do we need a data warehouse?

Large companies can have dozens of different transaction processing systems:

Customer websites 🌐
Point-of-sale systems (cash registers) in stores 🏪
Warehouse inventory tracking systems 📦
Transportation route planning systems 🚚
Human resources management systems 👥

Problem: OLTP systems must be highly available and process transactions with low latency. Analytical queries often require scanning large volumes of data and can interfere with transaction operations.

Solution: Data Warehouse — a separate database where analysts can run any queries without affecting OLTP operations.

🔄 ETL Process (Extract–Transform–Load)

Data enters the warehouse through the ETL process:

Extract - data is extracted from OLTP systems
Transform - data is transformed into a schema convenient for analysis
Load - data is loaded into the warehouse

Real-life example: A large bank 🏦 might have separate systems for:

Mobile banking 📱
Credit operations 💳
Mortgage products 🏠
Investment services 📈

All this data is combined in a data warehouse for end-to-end analytics.

⭐ Star and ❄️ Snowflake: Schemas for Analytics

🌟 Star Schema

At the center of the schema is a fact table, surrounded by dimension tables.

Example for retail:

fact_sales (sales fact table) - at the center
dim_product (product dimension) 📦
dim_store (store dimension) 🏪
dim_time (time dimension) ⏰
dim_customer (customer dimension) 👥

C Example:

// Structure for sales fact table
struct FactSale {
    int sale_id;
    int product_id;     // reference to dim_product
    int store_id;       // reference to dim_store
    int time_id;        // reference to dim_time
    int customer_id;    // reference to dim_customer
    double amount;
    int quantity;
    double profit;
};

// Structure for product dimension table
struct DimProduct {
    int product_id;
    char sku[20];
    char description[100];
    char brand[50];
    char category[50];
    double price;
};

❄️ Snowflake Schema

A more normalized version of the star schema where dimensions are further broken down into sub-dimensions.

Advantage of star schema: simpler for analysts!

💾 Data Warehouse Features

Wide tables: fact tables often have more than 100 columns 📋
Rich metadata: dimension tables contain all possible information for analysis
Optimized for analytical queries: special storage structures and algorithms

Quick Summary: OLTP vs OLAP

🎯 Key Differences

OLTP (Online Transaction Processing)

💰 Real-time operation processing
🔄 Short transactions (read/write)
⚡ High availability, instant response
🏦 Examples: bank transfers, orders, bookings

OLAP (Online Analytical Processing)

📊 Analytics and reporting
🔍 Complex queries on big data
📈 Multidimensional analysis (cubes, slices, drill-down)
🧠 Examples: business intelligence, forecasting

🏗️ Architectural Features

OLTP

ACID transactions 🛡️
Normalized schemas
Write optimization

OLAP

Denormalized schemas (🌟 Star/❄️ Snowflake)
Data warehouses
ETL processes
Read optimization

💡 What This Means in Practice

Aspect	OLTP	OLAP
Purpose	Business operations 🚀	Business analysis 📈
Data	Current operations	Historical data
Users	Operators	Analysts

Conclusion: OLTP ensures the company's daily operations, while OLAP helps understand trends and make strategic decisions. Both approaches are critically important but solve different problems.

DEV Community: dima853

Free Block Search Algorithms in Memory Managers

FUNDAMENTAL PROBLEM STATEMENT

But, first let's understand what stack and heap are.

1. Conceptual Division: Manager vs. Location

2. Why does the allocator (memory manager) operate with the concept of "heap"?

3. Important Clarification: "Owns" — in what sense?

2. CLASSIFICATION OF SEARCH STRATEGIES

2.1 First-Fit (First Suitable)

Pseudocode

But, let's recall what a process and a thread are

Process

Moreover, if there were no hardware virtual memory, process isolation in its modern understanding would be impossible. That is, process isolation is fundamentally and hardware-guaranteed by virtual memory.

What is virtual memory?

Virtual memory is a fundamental abstraction that makes each process think that it alone owns all the computer's physical memory, although in reality the memory is shared among many processes and the OS.

Thread

Analogy

2.2 Best-Fit (Best Suitable)

2.3 Worst-Fit (Worst Suitable)

Chunks/Arenas

1. Chunk — atomic unit of management

Chunk structure (using dlmalloc/ptmalloc as an example):

2. Arena — memory domain for parallelism

The problem that arenas solve:

Arena architecture (as in glibc's ptmalloc):

Strategy for distributing threads across arenas:

What is a DAG? Arborescence (Part 2)

Part 1: Arborescence (General Definition)

Simple Example - Computer Folder Structure ⬇️

DAG with Potential Arborescence (real system with mklink or .lnk):

"Arborescence(DAG)" in this analogy:

1.2. Formal Definition:

1.3. Key Corollaries and Properties:

Part 2: Arborescence in a Directed Acyclic Graph (DAG)

2.1. Context and Motivation:

2.2. Definition of Arborescence in a DAG:

2.3. Existence and Construction:

Part 3: Comparison and Summary Table

Example for DAG (constructing an arborescence):

Conclusion

Notations:

1. r ∈ V

2. deg⁻(r) = 0

3. v ∈ V \ {r}

4. Directed path from r to v

5. Directed cycle

Solution for Problem 207. Course Schedule (Leetcode)

What is a DAG? The Essence in a Nutshell (Part 1)

I. In-Depth Definitions and Mathematical Properties

1. Reachability Relation, Transitive Closure, and Transitive Reduction

2. Topological Sorting

Algorithms (two main approaches) ⬇️

A) Kahn's Algorithm (1962) — "intuitive," based on in-degrees

B) Tarjan's Algorithm (1976) — "elegant," based on DFS (Depth-First Search)

II. Families of Related Graphs

III. Computational Problems and Algorithms (Practical Value)

IV. DAG Applications (Where is all this used?)

Conclusion

JVM, Memory Management и Performance

JVM, Memory Management, and Performance

Answers to Questions:

1. Lifecycle of an object in the heap: from allocation to reincarnation

2. Garbage Collection: Basic algorithms and trade-offs

3. Garbage Collectors: Strategic Choice

4. Stop-The-World (STW): Anatomy of a Freeze

5. Memory Leak in Java: Systematic Failure

6. Metaspace vs PermGen: Evolution of Metadata

7. String Pool (String Table): Deduplication Mechanism

8. Escape Analysis: Compiler Magic for Optimization

9. Thread Memory (Stack Memory): Frame Architecture

10. JIT Compilation: C1, C2, and Adaptive Optimization

11. volatile: Guarantees of Visibility and Ordering

12. False Sharing: The Hidden Performance Enemy

Once again, and perhaps a bit more clearly ->

PART 1: JVM MEMORY ARCHITECTURE - MACRO LEVEL

Heap: The Dominant Structure in JVM

Object Lifecycle: Detailed Chronology

Phase 1: Allocation in Eden

Phase 2: First Minor GC

Phase 3: Promotion to Old Generation

DAG with Potential Arborescence (real system with `mklink` or `.lnk`):

1. `r ∈ V`

2. `deg⁻(r) = 0`

3. `v ∈ V \ {r}`

4. Directed path from `r` to `v`

11. `volatile`: Guarantees of Visibility and Ordering

2. Numbers vs Strings: Why `1 + 1 = 2` but `"1" + "1" = "11"`