Copy of `Kernel Newbies - Linux glossary`

The wordlist doesn't exist anymore, or, the website doesn't exist anymore. On this page you can find a copy of the original information. The information may have been taken offline because it is outdated.

Kernel Newbies - Linux glossary
Category: Agriculture and Industry
Date & country: 09/08/2014, USA
Words: 148

Application Binary Interface, the interface of passed structures between the user processes (and libraries) and the kernel. For compatibility, it is important that these remain as static as possible (i.e. making sure that variables and structure members have the same bytesize as before, and in the same ordering). Occasionally breakage is necessary, requiring re-compilation of the user-space sources (note that this does not affect source-compatibility; that is a separate issue).

Advanced Configuration and Power Interface, replacement for APM that has the advantage of allowing O/S control of power management facilities as well exporting the set of hardware currently present on the system.

Address Generation Interlocking, on x86. When execution of an instruction requires an address resulting from a non-completed instruction, the CPU must wait - this is known as an AGI stall.

Accelerated Graphics Port, on x86 boxes.

Asynchronous IO, IO that is performed without the issuing process blocking on IO completion.

Advanced Linux Sound Architecture.

Generally, used for something which doesn't have the usual associated object. For example an anonymous address space is not interested in user address space (that is, no process context). Some common ones are :

Anonymous buffer
The buffer cache contains buffers of data on their way to/from the disk. An anonymous buffer is not associated with a file. One example of this is data from a deleted file - it will not be written to any file, but is kept around until it is flushed.

Anonymous page
A page of memory that is not associated with a file on a file system. This can come from expanding the process's data segment with brk(), shared memory segments, or mmap() with a MAP_ANON or MAP_PRIVATE flag. MAP_PRIVATE, although it maps in data from a file, is considered anonymous because any changes do not get written back to the file (any dirty pages have to be moved to swap if the page is freed from main memory).

Anticipatory Scheduler
A disk IO scheduler that leaves the disk idle after a read, in anticipation of the next read.

See local APIC and IO-APIC.

Advanced Power Management, power management standard superseded by ACPI. APM and SMP just don't mix.

Adaptive Quality of Service Architecture.

Address Resolution Protocol and this is how a network machine associates an IP Address with a hardware address.

Abstract Syntax Notation, a protocol for structured data, used, for example, in the Q.3 management protocol.

Professor Andrew S. Tanenbaum, author of MINIX and several essential O/S books.

ATA Packet Interface, used by most CD-ROMs, and other devices.

Technique used in the VM code, referring to balancing various parameters such as the number of pages currently free, to avoid thrashing and other bad memory capacity artefacts. See zones, kswapd bug.

Base Address Registers, for PCI devices.

Binary-Coded Decimal - see a textbook.

big lock
kernel_lock, which locks the entire kernel from entry (no other task may run in the kernel code). It is recursive per process and dropped automatically when a process gives up the CPU, then regained on wake-up, in contrast to other spinlocks.

See highmem.

bit error
Used colloquially to mean a single bit error in some memory address. Often due to faulty memory (ECC memory can correct single bit errors). Often results in fake oopsen, with addresses like 0x0008000. Also seen are values some small offset from zero, plus a bit error, which is where the value passed a NULL check due to the bit error, and then the kernel tried to access a structure member by means of the pointer, leading to the offset.

block bitmap
In UNIX-like filesystems, the usage of disks blocks is recorded in the block bitmap, where each set bit indicates a specific allocated block.

Big-reader locks, used when there are many contending for read access to a resource, and very few contending for writes (thus the balance is towards very fast read locking, and very slow write locking).

BootStrap Processor, or the CPU which enables the other CPUs in an SMP system.

Branch Target Buffer, on x86 processors, the cache of recent conditional jump results.

buddy allocator
The memory allocation scheme used in the kernel. A vector of lists of free pages is kept, ordered by the size of the chunk (in powers of two). When a chunk is allocated, it is removed from the relevant list. When a chunk is freed back to the free pages pool, it is placed in the relevant list, starting from the top. If it is physically contiguous with a present chunk, they are merged and placed in the list above (i.e. where the chunks are twice the size), and this operation percolates up the vector. As regions are merged whenever possible, this design helps to reduce memory fragmentation. FIXME

buffer cache
The buffer cache is a hash table of buffers, indexed by device and block number. LRU lists are maintained for the buffers in the various states, with separate lists for buffers of different sizes. With 2.3's unification of the buffer and page caches, each buffer head points to part or all of a page structure, through which the buffer's actual contents are available. FIXME

buffer head
A structure containing information on I/O for some page in real memory. A buffer can be locked during I/O, or in several other states depending on its usage or whether it is free. Each buffer is associated with one page, but every page may have several buffers (consider the floppy on x86, where the I/O blocksize is 512 bytes, but each page is commonly 4096 bytes).

bus mastering
Giving a card on a bus (e.g. ISA,PCI) the ability to read/write directly to main memory. This is how DMA is performed on PCI busses.

byte sex

cache affinity
Where the cache of a CPU represents the current memory set used by a task, there is said to be cache affinity with that task. A good thing if the task is regularly scheduled on that CPU. See processor affinity.

cache line
A section of the hardware cache, around 32 bytes large. Kernel structures are often designed such that the commonly-accessed members all fit into one cache-line, which reduces cache pollution. Structures such as this are cache line aligned.

cache pollution
Where during execution of a task, another task is scheduled onto that CPU which disrupts useful lines of the current cache contents, which will be used soon. That is, cache pollution is a non-optimal situation where the other process would have been bettered scheduled on a different CPU or at a different time. The aim is to minimise the need to replace cache lines, obviously increasing efficiency.

call gate
x86 hardware support for mode switch to kernel (i.e. system call). In Linux, int 0x80 will trigger the call gate.

These are defined names of capabilities for specific tasks provided by the kernel, e.g. CAP_SYS_NICE.

Class Based Queueing, a hierarchical packet fair queueing qdisc. CBQ Homepage

Completely Fair Queueing, an alternative to the Anticipatory IO scheduler (and the default from 2.6.18 onwards) which allocates IO priority equally between processes.

Completely Fair Scheduler

chroot jail
A process under the aegis of a chroot() syscall is in a chroot jail, and cannot access the file system above its notion of root directory /.

(also: filter or tcf) classifies a network packet by inspecting it, used by QDiscs.

x86 assembler instructions for disabling and enabling interrupts, respectively. There are CPU-local and global variants of these. Code running with interrupts disabled must be fast, for obvious reasons (this is called interrupt latency).

Eric Raymond's proposal for a replacement to the current kernel build system. See

cold cache
A cache whose content is invalid or irrelevant with respect to some task to be run.

completion ports
I/O interface used in O/S's such as Windows NT. Userspace notifies the kernel of each file descriptor the program is interested. The O/S uses a callback for each fd to indicate that I/O is ready.

Where two tasks each want an exclusive resource. You may hear talk of, for example, spinlock contention, which is where one or more tasks is commonly busy-waiting for a spinlock to become unlocked, as it is being taken by other tasks.

Context switch
switching the CPU from running one thread to running another thread.

(also: COW) reuse and share existing objects and copy them not until a modification is required.

Current Privilege Level

critical path
A vital code path which should be optimised for the common case. Critical paths are executed frequently and form the important trunk routes of various kernel operations. An example would be buffer head manipulation during file I/O.

Code Storage Segment, aka text section. This is the memory mapping containing the executable code (text) for a binary image.

a kernel variable which points to the task_struct structure of the process currently running on this CPU.

Directed Acyclic Graph

The cache of dentry structures. Under UNIX an entry in a particular directory must be searched for linearly, so even if the disk block containing the directory entry list is in-core, there is an associated cost. The dcache stores recent results of these searches which in general speeds up these disk searches by a large factor. Recent 2.3 work uses the dentries to allow multiple mounting, union mount, and more.

Any of a number of situations where two or more processes cannot proceed because they are both waiting for the other to release some resource. FIXME(give good references).

delayed write
See write behind.

demand zero
In demand paging, where the page is to be zeroed when actually created (common case: bss segment of an executable image, which is uninitialised heap data for the executable). Also called ZFOD.

Directory entry, in-core structure defining a file's details: inode, parent dentry etc. Cached in a hash table indexed by hashed filename (see dcache).

Device Mapper
A technology for presenting arbitrary groupings of underlying sectors on physical devices in a consistent logical fashion usable by higher level algorithms. Heavily used by kernel technologies such as LVM.

IP packet bit indicating it should not be fragmented. The remote host will return ICMP notifications if the packet had to be split anyway, and these are used in MTU discovery.

Dial-On-Demand for net connections over POTS.

Data Storage Segment, aka data section. This is the memory mapping containing the initialised data for a binary image.

Processors such as the Pentium Pro, that can decode and execute two instructions simultaneously.

Abbrev. fr. duplication.

Debugging Information Format

Double word, i.e. 4 bytes on x86.

See extended attributes.

eager coalescing
What the buddy allocator currently does, i.e. merge adjacent blocks as soon as possible.

edge-triggered interrupt
The interrupt is triggered by the rising or falling edge of the interrupt line. This makes IRQ line sharing difficult, as an edge may occur whilst an ISR is running, and it could be easily missed; to allow sharing level-triggered interrupts are usually used.

Extended Instruction Pointer. This register contains the PC value of a task, that is, it points to the next instruction to be fetched, decoded etc.

elevator algorithm
This algorithm, often used in disk accesses, keeps an ordered list of requests. When the current request on the disk (e.g. the disk block) has been satisfied, the next strictly greater request on the list is dealt with. When a new request arrives, it is inserted into the ordered list in position (e.g. if the new requested block number is less than the current handled request, it goes before it in the list). When reaching the end of the list, the elevator changes direction, and the situation is reversed.

Executable Linkable Format, a popular binary format, the default for Linux on most architectures.

Extended Match, small classification helper attached to classifiers.

Explicitly-Parallel Instruction set Computing, an instruction set architecture where every dependency for an instruction is encoded into the instruction itself. This has the potential to be faster as the compiler can encode the data dependencies in the instructions.

exponential back-off
A general algorithm for dealing with contention cases; for example, collisions on a network bus, or contention for a spinlock.

fair scheduler
A scheduler which ensures fairness between users, such that a user's process count and associated cost only impacts that user, rather than the whole system as currently. Rik van Riel and Borislav Deianov have both produced different patches to implement this.

The code path most commonly taken, often optimised heavily at the expense of less frequently-taken blocks of code. This is the reason you see so many gotos in core functions - it produces common-path code far more efficient than an optimising compiler can manage.

file descriptor

The mapping of a file's contents into memory.

knobs filesystem-based manager of kernel objects, or config_items

devices (with various exceptions, contradictions, confusions, and hysterical raisins ...)

repository for all things task related,

guages filesystem-based view of kernel objects

fixed mmap
A user-space request for a mmap starting at a fixed virtual address. Generally not useful or guaranteed to work; a notable exception is overlayed mmaps, where a mmaped area has further mmaps of different types at fixed positions in the map.

Fully-Qualified Domain Name, e.g.

For AGP setups, Graphics Aperture Relocation Table.

GNOME's source documentation system (similar to javadoc). Available by CVS from gnome. Kernel driver interface descriptions, built from source using gdoc, are currently being written in 2.3.

Global Descriptor Table. A data structure (x86 arch) for defining segment descriptors (8-byte entries). See IDT.

Generalised Kernel Hook Infrastructure, an IBM patch to implement hooks into the kernel code.

I just had to point out that lkml is for Linux kernel development discussions. Please please don't engage in any threads concerning licensing issues, Microsoft, or Richard Stallman. Please.

group descriptor
On-disk filesystem structure, containing information for a block group, such as the inode bitmap and block bitmap.

GRand Unified Bootloader, a popular bootloader for Linux, BSD, and other OSes.

Global System Interrupt. Mainly used in the context of ACPI. Stupid acronym

high memory, or memory that is not permanently mapped into kernel memory. Common on 32 bit x86 systems. See HighMemory.

High Precision Event Timer (HPET) is a replacement timer for the 8254 Programmable Interval Timer and the Real-time clock's (RTC) periodic interrupt function. HPET is a successor to pmtimer, and is far more efficient to read.

Hierarchical Token Bucket, a qdisc based on TBF and CBQ. HTB Theory

Inter-Process Communication, a set of techniques for the exchange of data among multiple threads in one or more processes.

Interrupt Service Routine, the function in each device driver that gets called when an interrupt happens.

a kernel thread that frees up memory by evicting data from caches and paging out userspace memory, part of the virtual memory subsystem.